# Vectors, Hamming Distance, Coding Theory

• Sep 15th 2010, 10:14 PM
Haven
Vectors, Hamming Distance, Coding Theory
This problem is causing me some trouble, and I fear that I am overthinking it.

Prove that a binary $[n,M]$-code C of distance $d=2t+1$ exists if and only if a binary $[n+1,M]$-code C' of distance $d'=2t+2$ 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 $A=\left{0,1\right}$. So, a binary $[n,M]$-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 $c_i,c_j \in C$ such that $d(c_i,c_j)=d$, and for all other pairs $a,b \in C, d(c_i,c_j)>d$
==================================================

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.
• Sep 16th 2010, 01:09 AM
Swlabr
Quote:

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

Prove that a binary $[n,M]$-code C of distance $d=2t+1$ exists if and only if a binary $[n+1,M]$-code C' of distance $d'=2t+2$ 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 $A=\left{0,1\right}$. So, a binary $[n,M]$-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 $c_i,c_j \in C$ such that $d(c_i,c_j)=d$, and for all other pairs $a,b \in C, d(c_i,c_j)>d$
==================================================

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, $d$, apart and one starts at one of these vectors, $v_0$, then change $d$ entries to get to another element of the code, $v_1$, and do this again to $d$ entries to get to $v_2$, and again and again to get to $v_i$ then if $v_i = v_0$ one must have that $i=2n$ for some $n$ (i.e. $i$ is even. In general, $i$ divides the order of your alphabet).

Can you see why this is sufficient?
• Sep 16th 2010, 09:40 AM
Haven
So, let me get this straight I should prove that if a sequence of vectors $v_1, \dots v_i$ 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.
• Sep 16th 2010, 10:43 PM
Haven
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.