Coding with linear codes: Appendix

Share this page

Proof that a string can't occur in more than one column of the standard array

First note that adding a string to itself will always give you the string consisting only of 0s, for which we write $\bar{0}$. That’s because for each digit you either add 0 to 0 or 1 to 1. For example, 11000 + 11000 = 00000. Also, adding the zero string to any other string clearly leaves that string unchanged, e.g. 11000 + 00000 = 11000.

Now suppose a string occurs in more than one column. This means that there are two code words, call them $c_1$ and $c_2$, and two other strings that occur in the first column, call them $a_1$ and $a_1$, so that

  \[ c_1+a_1 = c_2+a_2. \]    
......c1...c2...
..................
a1...c1+a1.........
..................
a2.........c2+a2...

Adding $a_1$ to each side of the equation above gives

  \[ c_1 + a_1 + a_1 = c_2+a_2+a_1, \]    

which simplifies to

  \[ c_1 = c_2+a_2+a_1. \]    

Adding $c_2$ to each side gives

  \[ c_1+c_2 = c_2+a_2+a_1+c_2, \]    

which simplifies to

  \[ c_1+c_2 = c_2+c_2+a_2+a_1=a_2+a_1. \]    

Since we are dealing with a linear code, we know that the sum of two code words is itself a code word. This means that $c_1 + c_2$, and therefore $a_2+a_1$, is a code word and therefore appears somewhere in the first row of the array.

......c1...c2...a2+a1...
........................
a1...c1+a1...............
........................
a2.........c2+a2.........

Now suppose that out of $a_1$ and $a_2$, the string $a_1$ appears first in the array. The entry defined by the row corresponding to $a_1$ and the column corresponding to the code word $a_2+a_1$ is

  \[ a_2+a_1+a_1=a_2. \]    
......c1...c2...a2+a1...
........................
a1...c1+a1.........a2...
........................
a2.........c2+a2.........

In other words, string $a_2$ occurs in the row corresponding to $a_1$, as well as further down as an entry in the first column. This is a contradiction, as we would not have chosen $a_2$ as an entry of the first column if it had already occurred further up the table. Therefore, the string $c_1+a_1=c_2+a_2$ only occurs once in the table.

Back to the main article

Code 2 has the same chance of success as code 1

Code 1 consists of code words of length two. The probability of transmitting one code word correctly is

  \[ (1-p)^2. \]    

For code 2 the probability of decoding a single code word correctly is

  \[ (1-p)^3+p(1-p)^2. \]    

This can be rewritten as

  \[ (1-p)^3+p(1-p)^2 = (1-p)^2(1-p+p)=(1-p)^2, \]    

which is the same as for code 1.

Since for both codes two code words need to be transmitted correctly, the probability of reaching the treasure is, in both cases,

  \[ 1-((1-p)^2)^2 = (1-p)^4. \]    

Back to the main article