Results 1 to 4 of 4

Math Help - Vectors, Hamming Distance, Coding Theory

  1. #1
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Haven View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    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.
    Last edited by Haven; September 16th 2010 at 02:36 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Coding Theory Problem.
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 16th 2011, 07:49 PM
  2. Coding Theory- help with polynomials
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: May 13th 2011, 12:01 PM
  3. Coding theory question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 8th 2008, 07:26 PM
  4. Coding theory question
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 13th 2008, 06:31 PM
  5. Coding Theory Help Needed!
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 8th 2008, 05:52 PM

/mathhelpforum @mathhelpforum