Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Shortening LInear Codes

  1. Sep 28, 2006 #1
    I'm not sure if this is the right forum for this question, but it is a form of linear algebra, so I'll give it a shot. It's about coding theory.

    The problem is given a q-ary [n,k,d] linear code, fix an arbitrary column number and then collect all the code words that have 0 in that column. Make a new code from these words by deleting this column.

    Show that this new code is a linear [n-1, k', d'] code, where k'=k or k'=k-1 and d'>=d.

    Showing it is a linear code was easy.
    Showing it was n-1 was also easy, as was the constraints on d'.

    However, I can't see a good way to show the constraints on k'. I have an intuitive understanding of why this is true, but I can't figure out how to formulate it rigorously.

    I can find a proof for binary codes in a round about way, but I don't see a trivial way to generalize it to other fields.

    Any tips would be appreciated.
  2. jcsd
  3. Sep 28, 2006 #2
    I may have just come up with a constructive proof on my own. I am a little unsure of it, so would like some feedback if anyone thinks it is solid:

    Start with the case where the column in question in the generator matrix is all 0's, and thus all the code words have a 0 in that location. In this case we can just delete that column from the generator matrix and we keep the same dimension for the code. This is the trivial case.

    Now assume at least one of the rows has a non-zero element in that column.

    Since you can perform elementary row operations on a generator matrix and still have another generator matrix for a linear code, we can always zero all the rows in our column except for one of them ... and we can always say this is the bottom row for convenience.

    In this case the words that generate our subcode are all the generating words of the initial code that have a zero in the last location. This means we can just delete this last row to end up with a one smaller dimension code that still generates all the words in our subcode.

    We are then back to the first case with a column of all zeros which we can remove without worry. Giving us our n-1, k-1 code, as well as a way of creating a new generator matrix for it.
  4. Oct 2, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    It looks solid to me.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook