Here is Coding Theory Part 2 by Anandaswarup Gadde, introducing simple ideas in coding theory. As is the case with Part 1, I have made minor editing and addition of links etc. with the original version. Read on, beneath the fold…Arunn
Coding Theory Part 2 by Anandaswarup Gadde
In Part 1, we saw what is a triple repetition code, which gave rise to the notion of Hamming distance. For Hamming codes, the minimum distance is three and thus we can only detect and correct single errors. If we want to use triple code with larger vocabulary, say strings of four symbols, we have to send strings of 12 symbols.
However, Richard Hamming found a way of manufacturing just 3 more symbols (from the actual 4 required for the 4 symbols) so that it is enough to send strings of 7 symbols. It gets better; for strings of 11 symbols it is enough to send strings of 15 symbols. The extra three bits are called ‘check bits’ or ‘parity bits’.
The way to obtain the first parity symbol is that if we add it to the first, second and fourth of our original string, we should get an even number (that is why the name parity bits). Similarly, the second parity bit is obtained by checking parity against first, third and fourth of the original string and finally the third parity bit is obtained by checking parity against second, third and fourth bits of the original string. These checks give a unique seven letter string and a code with minimum distance three so that single errors can be corrected.
The actual method involves the use of matrices with entries in mod 2 numbers (with only symbols 0 and 1 with rules like 0+1=1, 1+1=0, 1.0=0, 1.1=1, so called binary arithmetic) and a matrix can be thought of as a means of converting a string to another string possibly of different length. This is explained in a bit more detail in the next paragraph. Hamming’s main ideas seems to be Hamming distance, parity checks and Hamming matrices and the neat interpretations in terms of Linear Algebra are due to D. E. Slepian.
In this paragraph, we explain in a bit more detail the ideas of the previous paragraph; those who are satisfied with the ideas above can skip this.
If [x1 x2…xn] is a row of 0′s and 1′s written one after the other from left to right, then [x1 x2…xn]t is the same string written as a column, one below the other. The superscript ‘t‘ stands for transpose.
Write the numbers 1,2,3…7 in binary notation and put the corresponding column vectors [001]t, [010]t, [011]t, [100]t, [101]t, [110]t, [111]t together to obtain a 3 by 7 (three rows and seven columns) matrix H.
If we apply H to the column vector [x1 x2…x7]t we obtain the column vector:
[x4+x5+x6+x7, x2+x3+x6+x7, x1+x3+x5+x7]t
In these additions, if the number is even we substitute 0 and if it is odd we substitute 1 (mod 2 arithmetic). In the matrix, the first, second and fourth columns correspond to check bits or parity bits and x3, x5, x6, x7 are free variables. Substituting 0,1 for these variables, we get 16 message words [x3x5x6x7].
Equating the three words in
[x4+x5+x6+x7, x2+x3+x6+x7, x1+x3+x5+x7]t
to zero, we obtain values for the check bits x1 x2 x4 and thus the code word [x1 x2…x7] corresponding to the message word [x3x5x6x7].
Note that the numbering of the check bits and message bits is different from that of the previous paragraph; the check bits 1, 2, 3 now have subscripts 1, 2, 4 and the message bits 1, 2, 3, 4 now have subscripts 3, 5, 6, 7.
For example the message word [1011] gives the code word [0110011].
Many books (see Hungerford’s “Abstract Algebra“, Saunder’s College Publishing, 1990) use a 4 by 7 matrix which automatically does this but writing the matrix is not as transparent as the above.
Suppose that the code word is sent and a mistake is made in the fifth place, that is, we receive [0110111]. From the way we formulated the code words, H [x1 x2…x7]t should give the zero vector (a three column vector consisting of zeroes). But H [0110011]t is [101]t.
Thus we know a mistake has been made.
Notice that we have obtained the fifth column of H. If only one mistake has been made in the transmission, this indicates that the mistake has been made in the fifth place (this is called the “syndrome’ of error) and thus we can go to the correct word and thus to the original message. The problem with this is as strings get longer, it is difficult to assume that only one or no mistake is made. Hence Hamming codes were used only for a short period but the ideas led to multiple error correcting codes in which two Indians played an important part.
The strange system with 0,1 and operations like 1+1=0 is called a field of two elements. It turns out that there is exactly one field of any given prime power order. These are called Galois fields in honor of a French mathematician Evariste Galois who invented new concepts in algebra in the process of showing that in general equations cannot be solved by radicals. He was also a social activist and died in a duel at the age of twenty.
Surprisingly, there is an Indian connection to Galois fields. Raj Chandra Bose studied Abstract Algebra under F. W. Levi who left Germany during Hitler’s time and joined Calcutta University as a Professor of Mathematics. Bose was one of the early group of pioneers assembled by P. C. Mahalanobis prior to the formation of Indian Statistical Institute. Bose found that the abstract algebra he learnt under Levi (in particular Galois fields) was useful in coding theory and constructed multiple error correcting codes with Ray-Choudhuri in 1960. These are called BCH codes (BCH codes are discussed in the Abstract Algebra book of Hungerford). A particular case of these are the Reed-Solomon (error correcting) codes which are used in CDs. Though these are more difficult, the original ideas of Richard Hamming are simple and keep coming again and again.
End Notes
- There are several popular books including “Great Ideas in Information Theory, Language and Cybernetics” by Jagjit Singh (Dover, 1966) discussing some of these ideas.
- F. W. Levi published important papers in Journal of Indian Math. Society and Bulletin of Calcutta Math. Soc. Apparently, C.R.Rao published a paper in the later journal in the forties which is supposed to have initiated differential geometric techniques in Statistics.
- I (Swarup) added a couple of applications like this in a course on Algebra to sell the course, but I am not an expert in these areas.
Tags: Abstract Algebra, Binary Numbers, Claude Shannon, coding theory, cryptology, Evariste Galois, Hamming distance, Hamming matrix, Raj Chandra Bose, Richard Hamming, Signal Processing
Hanuman (a. k. a. Anjaneya), the mythological character from the Epic Ramayana, is worshipped as the Monkey God in most parts of India, especially by the Hindus. Just to meet mythology with modern science, there is a species of monkeys, the Gray Langur, also known as the Hanuman Langur.
