3.5.3 Single-Error-Correcting Hamming Codes

R. W. Hamming found an optimum class of single-error correcting codes in 1950 [6]. The code was used for long-distance telephony. For some integers c ? 2, the family of binary Hamming codes has the following parameters:

• Block length:	n = 2 c ? 1
  Information digits:	k = 2 c ? c ? 1
  Number of check digits:	c = n ? k
  Minimum distance:	d min = 3
  Error correcting capability:	t' = 1.

To construct the parity-check matrix of an ( n, k) binary Hamming code, we simply place all nonzero binary c-tuples in the columns of the c-by- n parity-check matrix in any order.

For example, the parity-check and the corresponding generator matrices of a (7, 4) single-error-correcting binary Hamming code are

(3.27)

and

(3.28)

If the input information sequence is U = [0 1 1 1], the encoded code sequence is V = UG = [0 1 1 1 0 1 0].