# Coding with linear codes: Appendix

### 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 . 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 and , and two other strings that occur in the first column, call them and , so that

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

Adding to each side of the equation above gives

which simplifies to

which simplifies to

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 , and therefore , 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 and , the string appears first in the array. The entry defined by the row corresponding to and the column corresponding to the code word is

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

In other words, string occurs in the row corresponding to , as well as further down as an entry in the first column. This is a contradiction, as we would not have chosen as an entry of the first column if it had already occurred further up the table. Therefore, the string 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

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

This can be rewritten as

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,

Back to the main article