Thread: Vectors, Hamming Distance, Coding Theory

This problem is causing me some trouble, and I fear that I am overthinking it.

Prove that a binary -code C of distance exists if and only if a binary -code C' of distance exists.

Skip this if you understand the notation above
==================================================
For those unfamiliar with the notation of coding theory. A code is merely a subset of M vectors in the vector space A^n, where A defines the alphabet of the code. In this problem the alphabet is . So, a binary -code is a set of M n-tuples such that, each entry is either 0 or 1

The Hamming distance of two vectors, is the number of entries where the two vectors differ. So taking all possible Hamming distances of the vectors in the code, the distance of an [n,M]-code C, is the minimum of these distances. So, if a code C has distance d, then there exist a pair of vectors such that , and for all other pairs
==================================================

What i am attempting to do for the direction from left to right, is to assume the existence of a code with distance d=2t+1 and then show that I can construct a new code C' such that the distance is 2t+2. So, I do the natural thing and append all the old vectors with new vectors. However no matter what I try, I cannot get a construction to work out.

Any help would be greatly appreciated.

Originally Posted by Haven

This problem is causing me some trouble, and I fear that I am overthinking it.

Prove that a binary -code C of distance exists if and only if a binary -code C' of distance exists.

Skip this if you understand the notation above
==================================================
For those unfamiliar with the notation of coding theory. A code is merely a subset of M vectors in the vector space A^n, where A defines the alphabet of the code. In this problem the alphabet is . So, a binary -code is a set of M n-tuples such that, each entry is either 0 or 1

The Hamming distance of two vectors, is the number of entries where the two vectors differ. So taking all possible Hamming distances of the vectors in the code, the distance of an [n,M]-code C, is the minimum of these distances. So, if a code C has distance d, then there exist a pair of vectors such that , and for all other pairs
==================================================

What i am attempting to do for the direction from left to right, is to assume the existence of a code with distance d=2t+1 and then show that I can construct a new code C' such that the distance is 2t+2. So, I do the natural thing and append all the old vectors with new vectors. However no matter what I try, I cannot get a construction to work out.

Any help would be greatly appreciated.

I apologise if this is wrong, it's been a while since I though about this stuff. However, I believe this comes down to proving the following:

If two vectors are the minimum distance, , apart and one starts at one of these vectors, , then change entries to get to another element of the code, , and do this again to entries to get to , and again and again to get to then if one must have that for some (i.e. is even. In general, divides the order of your alphabet).

Can you see why this is sufficient?

So, let me get this straight I should prove that if a sequence of vectors in my code. has the property that d(v_j,v_{j+1})=2t+1. Then there must be an even amount of vectors.

I understand that he evenness of i would allow me to append and alternating sequence of 1's and 0's in the last entry without having that d(v_1,d_i)=d. However, i'm not sure how i would go about proving this.
I would appreciate any hints.

Is it that in order for v0 to be the end of the sequence, every change in the sequence must be changed back. Since there is only two possible entries in each vector, a change in merely changing a 0 to 1 or vice versa.
So if a 1 is changed to a 0, it eventually has to be changed back to 1, hence we get two steps.
What i have is intuitive, but I'm not sure it's valid since i didn't use the fact that d is odd.