Many Faces of Hamming Code
PARTHA PRATIM DEY
Department of Computer Science & Engineering
North South University
12 Kemal Ataturk Rd., Banani, Dhaka
Abstract:- In this paper, we present three alternative constructions of the- Hamming code. This error correcting code was developed by Richard W. Hamming in the 1950s when he was working in the Bell Laboratories. It improved the practical applications of early computers by substantially improving their reliability. But it is even more remarkable that many modern computers still use this or similar code to correct errors in main memory. It is not an exaggeration to say that modern graphical computing, which requires large memories and computers in critical control applications, which can not afford any significant probability of an erroneous result would be impractical without this Hamming code. Besides that this code has made a penetration into the quantum world too. It has currently been proposed by A. M. Steane [1] for quantum error correction.
Key-words:- Linear Code, Hamming Matrix, Encoder, Parity Check Matrix, Hadamard Matrix, Polynomial.
1 Introduction
We begin with a couple of definitions.
DefinitionLetbe the vector spaceof dimension overso that a typical vectorhas the shape
.
Acodeoveris a linear subspace of of dimension.
DefinitionA matrixwith elements fromand of full row rank is called a generator matrix of acodeif is the linear subspace spanned overby the rows of considered as vectors in.
Letandwith. We assumeto be a matrix overof full row rank. Thenfor someis a subspace ofof dimension . Therefore,is a linear code of withcode-words, and is a generator matrix of. Notice that, besides spanning the code, also appends or encodes a bit message of into a bit code-word ofwhen the message is multiplied by. This is why, a generator matrix is also known as encoder and the multiplication of message set by matrix is called encoding.
Let us consider anmatrixof full row rank overwith. Since, we obtainfor any. Hencei.e.for all. And sincehas full row rank, it can be shown thatif and only if. Thuscan be used to identify code-words in as follows:
.
The matrixis called a parity check matrix.
TheoremGiven a generator matrixwe can always construct a parity check matrix, and vice versa.
Proof. Supposeis given. Find the null spaceof. Find a basis of this null space. Let each element of the basis be a row of the. Since each row ofis in, we have. By taking transposition of this equality, we get. Thusis indeed a parity check matrix.
We now prove the converse. Supposeis given. We find a basis forand let each element of the basis be a row of. Then the sub-space spanned by the rows ofoveris indeed. Thusis a generator matrix of the code, given by parity check matrix■
Next we consider a matrixwhere the columns of the matrixare the numbersexpressed in binary. The code, having such a parity check matrix, is called a-Hamming code. Actually for anyamatrix is called a Hamming matrix if the columns ofcontain the binary equivalents of the integers from to , and the corresponding code is called a Hamming code.
2 The Hamming Scheme of Information Transmission and Error Correction
Richard W. Hamming is best known for his pioneering work on error correcting codes for computer systems. Before accepting a chair of computer science at the Naval Postgraduate School at Monterey, California, he spent thirty years from 1946 to 1976, working for the Bell Telephone Laboratories. It was there where he came in contact with primitive computers of that early era. Frustrated by their lack of fundamental reliability, he puzzled over the problem of how a computer might check and correct its own results. This led him to devise the- code and other error correcting codes and publish his results as “Error Detecting and Error Correcting Codes” in the Bell System Technical Journal, vol 29, pp. 147-160.These codes are a special type of linear codes which are capable of not only detecting errors, but also capable of correcting them. In Hamming's scheme of error correction, a symmetric binary channel is used i.e., information is transmitted in the form of strings ofand. Moreover when a transmitter sends a signalor in such a channel, associated with each signal there is a constant common probabilityfor incorrect transmission due to noise in the channel. To improve the accuracy of transmission in such a channel, a messageis appended by extra signalsto form the codeword. Recall from our discussion in Section 1 that this appending is carried out through multiplication by a generator matrixand the whole process is called encoding. However, the coded message is then transmitted through some channel. If the received vectorcontains a corrupt bit, it is detected and corrected. We discuss in next paragraph how in a Hamming scheme, these error detection and correction are accomplished.
Suppose , a codeword of a - Hamming code is transmitted and we receive the vector. Thenfor some error vectorthat contains one in the position whereand differ and zeros elsewhere. Note that, so we can determineby computingSince error vector contains all zeros except a single one,will be one of the columns of. Letbe theth column of. Then surely, theth bit of the received word must have been corrupted.
Finally, after correction of the received vector, a decoding mapis applied on it to retrieve the original message.
3 Polynomial Construction
Let be the integral domain of polynomials over. Thenis an irreducible polynomial of degreein and the principal idealconsists of all polynomials inof which is a factor. Moreover, polynomials inof degree less than, is a field. On the other hand, is a primitive polynomial inof degree. We letbe multiples ofinof degree less than. This is a vector space inwith basis. Each polynomial in the basis can be identified with a -dimensional vector. For example, can be rewritten as, and therefore can be identified with the-dimensional vector. The same can be done with other elements of . Thuscan be looked as a basis in. We will show that the code spanned byis a- Hamming code.
Letbe the matrix whoseth row is theth vector in , from left i.e.,
Applying elementary row operations on, after a couple of steps, we obtain the following matrix.
If is used as encoder, then the corresponding parity check matrixis given by
Clearlyis a Hamming matrix.
4 Hadamard Matrix Construction
An matrixis called a Hadamard matrix if the entries in H are all or, andfor theidentity matrix. A Hadamard matrixis said to be normalized if the first row and column ofcontain only positive ones. The only normalized Hadamard matrices of orders one and two i.e., of sizesandare
and
.
Also,
and
are normalized Hadamard matrices of ordersandrespectively.
We delete the first row and column from, change all negative ones into zeros, and call the resulting matrixThus
Note that each row and column of containsones. It is because each row and column ofexcept the first contains ones. Hence, the dot product of any row or column ofwith itself will be equal to. Furthermore, in any pair of distinct rows ofexcluding the first, there are positions in which the rows differ,positions in which the rows both have a, andpositions in which the rows both have a . Thus, in the corresponding pair of rows of, there will be position in which the rows both have, so the dot product of any two distinct rows ofwill be equal to. Therefore, whereis theidentity matrix, andis thematrix of all ones. Since alsothen we knowis the incidence matrix of Fano's plane [2][3]. Singer [4] has proved that the rank of this matrix isover
We will show that the code spanned by its rows is a- Hamming code.
We take the first four independent rows ofto form
Applying elementary row operations on, we obtain:
.
As in Sectionthe parity check matrix for such ais
,
which is clearly a Hamming matrix.
3 Venn Diagram Construction
This method uses three circles. When drawn as in the Figure, these circles split one another intoregions numbered one through seven.
A -bit message, such as , is encoded into a-bit code-word as follows:
a. The bit is assigned to region for each .
b. A bit,or, is assigned to each of the remaining regions of the circles so that the total number ofs in each circle is even.
c. The code-word is then taken to be the-bit string, whereis the bit which the th region was assigned as in Fig.
Fig
Fig
Notice that condition b. above implies the following.
The parity check matrix here is
,
which is clearly a Hamming matrix.
References:
[1] A. M. Steane, Error Correcting Codes in Quantum Theory, Physics Review Letters, 74, pp. 793-804,
1996.
[2] P. Dembowskii, Finite Geometries, New York: Springer Verlag, 1968.
[3] H. L. Dorwart, The Geometry of Incidence, Englewood Cliffs, N.J. : Prentice-Hall, 1966.
[4] J. A. Singer, Theorem in Finite Projective Geometry and Some Applications to Number Theory, Trans. Amer.Math. Soc., 43, pp. 377-385, 1938.