Abstract Algebra: Theory and Applications · Problem 8.6.26

Isomorphisms — Thomas Judson

Mathematics — Abstract Algebra · hamming-codes

Problem

Let

H

be an

m \times n

matrix over

\mathbb{Z}_2

, where the

i

th column is the number

i

written in binary with

m

bits. The null space of such a matrix is called a Hamming code. ((a)) Show that the matrix

H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{pmatrix}

generates a Hamming code. What are the error-correcting properties of a Hamming code? ((b)) The column corresponding to the syndrome also marks the bit that was in error; that is, the

i

th column of the matrix is

i

written as a binary number, and the syndrome immediately tells us which bit is in error. If the received word is

(101011)

, compute the syndrome. In which bit did the error occur in this case, and what codeword was originally transmitted? ((c)) Give a binary matrix

H

for the Hamming code with six information positions and four check positions. What are the check positions and what are the information positions? Encode the messages

(101101)

and

(001001)

. Decode the received words

(0010000101)

and

(0000101100)

. What are the possible syndromes for this code? ((d)) What is the number of check bits and the number of information bits in an

(m,n)

-block Hamming code? Give both an upper and a lower bound on the number of information bits in terms of the number of check bits. Hamming codes having the maximum possible number of information bits with

k

check bits are called perfect. Every possible syndrome except

\mathbf{0}

occurs as a column. If the number of information bits is less than the maximum, then the code is called shortened. In this case, give an example showing that some syndromes can represent multiple errors.

Browse the problem library