Hamming Code in Digital Electronics
Hamming codes belong to the class of LBCs, generally designated as (n, k) codes, where n represents the total number of bits in its code words, k represents the number of bits in its data words, and r represents the number of parity bits in its parity words. For example, in the (6, 3) LBC, let ith code word ci = 100101. Then we find that ith data word di = 100, and ith parity word pi = 101. The relation among n, k, and r is given by the expression.
n = k + r (1.1)
Parity bits are generated using the relation
[C] = [D] ´ [G] (1.2)
where C is the code vector, G is the generator matrix, and D is the data vector (or, data word). Here the term vector means the row or column of a matrix. G matrix is generated arbitrarily by the designer at his will. For the Hamming code, the following rules are to be observed:
· Total number of bits in the code word and the number of parity bits are related by the expression
n = 2r – 1 (1.3)
· Hamming code also must obey the basic LBC rule
n = k + r (1.4)
· No rows or columns must contain all zeros.
· The first part of G must be the identity matrix I. For example, for the (n, k) block code, G must contain a (k ´ k) block of I.
· The remaining part of G will be a k ´ (n ‒ k) block. This block is called the parity-matrix P and contains the parity bits. This parity block will be different for different generator matrices. However, for a given set of codes, G will be a constant. It may be noted that G can also be constructed by writing P] first and then adding I.
· For the Hamming code, one condition to be stipulated is that any row of the parity block in G must contain two or more 1s.
· No columns of the parity block must contain elements of any row of I. That is, the columns of the parity block should not contain elements of the type 1000, 0100 etc.
· Hamming codes are single error-correcting codes.