Hamming Code

Hamming(7,4) Code

부호화에 사용하는 생성 행렬 G

(Canonical) generator matrix G of a linear (n, k) code

G = (I_k | -A) = ( {{1, 0, 0, 0, 0, 1, 1}, {0, 1, 0, 0, 1, 0, 1}, {0, 0, 1, 0, 1, 1, 0}, {0, 0, 0, 1, 1, 1, 1}} )

G = ({{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}, {0, 1, 1, 1}, {1, 0, 1, 1}, {1, 1, 0, 1}})

오류를 감지하고 바로 잡는 데 쓰는 확인 행렬 H

parity - check matrix H

H = (A | I_ (n - k)) ({{0, 1, 1, 1, 1, 0, 0}, {1, 0, 1, 1, 0, 1, 0}, {1, 1, 0, 1, 0, 0, 1}})

H G=0,an all-zeros matrix[Moon]

(7, 4, 3) = (n, k, d) =[2^m - 1, 2^m - 1 - m, m]

부호화 과정

자료 비트 p

p = ({{1}, {0}, {1}, {1}})

패리티 확인

받은 내용 r

r = ({{1}, {0}, {1}, {1}, {0}, {1}, {0}})

H . r = Mod[({{0, 1, 1, 1, 1, 0, 0}, {1, 0, 1, 1, 0, 1, 0}, {1, 1, 0, 1, 0, 0, 1}}) . ({{1}, {0}, {1}, {1}, {0}, {1}, {0}}), 2] = ( {{0}, {0}, {0}} )

오류 정정

r = x + e_i (Mod 2)

e_i : 단위 벡터

H r = H (x + e_i) = H x + H e_i

H x + H e_i = 0 + H e_i = H e_i

r = x + e_2 = ({{1}, {0}, {1}, {1}, {0}, {1}, {0}}) + ({{0}, {1}, {0}, {0}, {0}, {0}, {0}}) = ( {{1}, {1}, {1}, {1}, {0}, {1}, {0}} )

H . r = Mod[({{0, 0, 0, 1, 1, 1, 1}, {0, 1, 1, 0, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 1}}) . ({{1}, {1}, {1}, {1}, {0}, {1}, {0}}), 2] = ( {{0}, {1}, {0}} )

Creating a parity check matrix

(n, k, d)

Generator matrix

G =[I_k | P]

I_k is a k×k identity matrix, P is of dimension k× (n - k) .

Parity check matrix

H =[-P | I_ (n - k)]

G . H = P - P = 0

G = ({{1, 0, |, 1, 0, 1}, {0, 1, |, 1, 1, 0}})

H = ({{1, 1, |, 1, 0, 0}, {0, 1, |, 0, 1, 0}, {1, 0, |, 0, 0, 1}})

G . H = ({{1, 0, 1, 0, 1}, {0, 1, 1, 1, 0}}) . ({{1, 1, 1, 0, 0}, {0, 1, 0, 1, 0}, {1, 0, 0, 0, 1}}) //MatrixForm = ( {{2, 0, 2}, {2, 2, 0}} )

Hamming(8,4) Code

G = ({{1, 1, 1, 0, 0, 0, 0, 1}, {1, 0, 0, 1, 1, 0, 0, 1}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 1, 0, 1, 0, 0, 1, 0}})

H = ({{1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 1, 0, 0, 1, 1, 0}, {0, 0, 0, 1, 1, 1, 1, 0}, {1, 1, 1, 1, 1, 1, 1, 1}})

(8, 4, 4)

G = ({{1, 0, 0, 0, 0, 1, 1, 1}, {0, 1, 0, 0, 1, 0, 1, 1}, {0, 0, 1, 0, 1, 1, 0, 1}, {0, 0, 0, 1, 1, 1, 1, 0}})

H = ({{0, 1, 1, 1, 1, 0, 0, 0}, {1, 0, 1, 1, 0, 1, 0, 0}, {1, 1, 0, 1, 0, 0, 1, 0}, {1, 1, 1, 0, 0, 0, 0, 1}})