Can Column Deletion Create a New Linear Code?

  • Thread starter gonzo
  • Start date
  • Tags
    Linear
It is shown that if we start with a q-ary [n,k,d] linear code and delete a column with all zeros, we get a new linear [n-1, k', d'] code with k' being either k or k-1 and d' being greater than or equal to d. This can be shown by first considering the case where the deleted column is all zeros, and then generalizing to the case where there is at least one non-zero element in the column. The proof also demonstrates how to construct a new generator matrix for the subcode.
  • #1
gonzo
277
0
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.
 
Physics news on Phys.org
  • #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.
 
  • #3
It looks solid to me.
 

FAQ: Can Column Deletion Create a New Linear Code?

What is a linear code?

A linear code is a type of error-correcting code used in communication systems to detect and correct errors that occur during transmission. It is a systematic code where the encoded message is a linear combination of the original message and a set of error-correcting bits.

What is shortening in linear codes?

Shortening in linear codes refers to the process of reducing the length of the codewords in a linear code while still maintaining its error-correcting capabilities. This is typically done to improve the efficiency of the code and reduce the decoding complexity.

How does shortening affect the error-correcting capabilities of a linear code?

Shortening a linear code can decrease the code's error-correcting capabilities, as the shorter codewords may not be able to correct as many errors as the original code. However, the decrease in error-correcting capability is usually minimal and can be offset by the benefits of having a more efficient code.

What are the advantages of using shortened linear codes?

Using shortened linear codes can provide several advantages, such as reducing the decoding complexity, increasing the transmission rate, and improving the overall efficiency of the communication system. Additionally, shorter codewords can also reduce the chances of burst errors, which can occur in longer codewords.

How is shortening implemented in linear codes?

Shortening is typically implemented by removing specific bits from the original codewords and replacing them with parity bits. The selection of which bits to remove and how many to remove is based on the code's design and the desired length of the shortened codewords. This process can be done manually or using algorithms to optimize the code's performance.

Back
Top