Hamming Code Basics

In the late 1940s Richard Hamming recognized that the further evolution of computers required greater reliability, in particular the ability to detect and correct errors. (At the time, parity checking was being used to detect errors, but was unable to correct any errors.) He created the, Hamming Codes, perfect 1-error correcting codes, and the extended Hamming Codes, 1-error correcting and 2-error detecting codes. Hamming Codes are still widely used in computing, telecommunication, and other applications including data compression, popular puzzles, and turbo codes. At the time, Hamming worked at Bell Telephone Laboratories and was frustrated with the error-prone punched card reader, which is why he started working on error-correcting codes.

Hamming(7,4)

The Hamming code adds three additional check bits to every four data bits of the message. Hamming’s (7,4) algorithm can correct any single-bit error, or detect all single-bit and two-bit errors.

The Goal: parity bits

The goal of the Hamming codes is to create a set of parity bits that overlap such that a single-bit error (the bit is logically flipped in value) in a data bit or a parity bit can be detected and corrected.

Hamming Matrices

Hamming codes can be computed in linear algebra terms through matrices because Hamming codes are linear codes. For the purposes of Hamming codes, two Hamming matrices can be defined: the code generator matrix G and the parity-check matrix H:

The code generator matrix G

G=matrix(c(1,1,1,0,0,0,0,1,0,0,1,1,0,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1),nrow=7,ncol=4)
G
##      [,1] [,2] [,3] [,4]
## [1,]    1    1    0    1
## [2,]    1    0    1    1
## [3,]    1    0    0    0
## [4,]    0    1    1    1
## [5,]    0    1    0    0
## [6,]    0    0    1    0
## [7,]    0    0    0    1

The parity-check matrix H:

H=matrix(c(1,0,0,0,1,0,1,1,0,0,0,1,1,0,1,0,1,1,1,1,1),ncol=7,nrow=3)
H
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,]    1    0    1    0    1    0    1
## [2,]    0    1    1    0    0    1    1
## [3,]    0    0    0    1    1    1    1

Example: Transmitting data matrix D: (1,0,1,1)

d1=1
d2=0
d3=1
d4=1
D=matrix(c(d1,d2,d3,d4),nrow=4,ncol=1)
D
##      [,1]
## [1,]    1
## [2,]    0
## [3,]    1
## [4,]    1

Channel Coding to add parity

X1=G%*%D
X1
##      [,1]
## [1,]    2
## [2,]    3
## [3,]    1
## [4,]    2
## [5,]    0
## [6,]    1
## [7,]    1
# Mod 2
X=X1%%2
X
##      [,1]
## [1,]    0
## [2,]    1
## [3,]    1
## [4,]    0
## [5,]    0
## [6,]    1
## [7,]    1

The coded information will be transmitted instead of orignial (1,0,1,1)

Checking Error at Receiver

If there is no error

# This means that 0110011 would be transmitted instead of transmitting 1011
R=X
Z1=H%*%R
Z=Z1%%2
Z
##      [,1]
## [1,]    0
## [2,]    0
## [3,]    0
# Since the syndrome z is the null vector, the receiver can conclude that no error has occurred. 
# This conclusion is based on the observation that when the data vector is multiplied by G, a change of basis occurs into a vector subspace that is the kernel of H. As long as nothing happens during transmission, r will remain in the kernel of H and the multiplication will yield the null vector.

If there is an error

FX=matrix(c(0,1,1,0,1,1,1),nrow=7,ncol=1)
Z2=H%*%FX
ZZ=Z2%%2
ZZ
##      [,1]
## [1,]    1
## [2,]    0
## [3,]    1
# which corresponds to the fifth column of H.

mine <- as.vector(ZZ)
col.is.a.match <- apply(H, 2, identical, mine)
match.idx <- which(col.is.a.match)
match.idx
## [1] 5
total.matches <- sum(col.is.a.match)
total.matches
## [1] 1
FX
##      [,1]
## [1,]    0
## [2,]    1
## [3,]    1
## [4,]    0
## [5,]    1
## [6,]    1
## [7,]    1
FX[match.idx,]=FX[match.idx,]+1
FX
##      [,1]
## [1,]    0
## [2,]    1
## [3,]    1
## [4,]    0
## [5,]    2
## [6,]    1
## [7,]    1
FXX=FX%%2
FXX
##      [,1]
## [1,]    0
## [2,]    1
## [3,]    1
## [4,]    0
## [5,]    0
## [6,]    1
## [7,]    1

Decode the information after the error correction

R=matrix(c(0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1),nrow=4,ncol=7)

FR=R%*%FXX

FR
##      [,1]
## [1,]    1
## [2,]    0
## [3,]    1
## [4,]    1