이산수학

제 10 장 암호이론과 그 응용

3. HAMMING ONE-ERROR CORRECTING CODES I

3. HAMMING 1-ERROR CORRECTING CODES I

one-error correcting code를 어떻게 하면 만들 수 있는가 생각하여 보시오. 또, 암호이론에 관한 표준적인 교재를 참고하여 생각한 방법의 타당성을 생각하여 보시오.

본 강의에서는 암호이론(coding theory) 중에서 Hamming one-error correcting code에 관한 기초적인 이론과 방법에 대하여 학습한다.

HAMMING ONE-ERROR CORRECTING

BINARY CODES

HAMMING ONE-ERRORCORRECTING BINARY CODE를 활용하는 방법에 관하여 학습하도록 합시다.

다음의 강의는 R. C. Bose & B. Manvel 저서인

Introduction to Combinatorial Theory

John Wiley & Sons Inc., 1984.

의 7장의 내용을 참고하여 학습하기 바랍니다.

In a binary code, the alphabet consists of

only two symbols 0 & 1, which may be regarded

as elements of GF₂, the Galois Field of order

2. Let Ω be the set of all binary r-vectors other

than the null vector Then there are n=2^r-1

vectors in Ω.

For example, if r = 2, then

Ω={ (1, 1), (1, 0), (0, 1)};

if r = 3, then

Ω={ (1, 1, 1), (0, 1, 1,), (1, 0, 1), (1, 1, 0),

(1, 0, 0), (0, 1, 0), (0, 0, 1)}.

Let H be the matrix whose columns of Ω. Thus

if r = 3, then H is given by

………(1)

단지 두 기호 0, 1로 되어있는 이항코드에서 GF₂의

원소들로 생각할 수 있다. Ω를 영 vector

0 (0, 0, …, 0)과 다른 모든 이항 r차원 vector들의

집합이라 합시다.

그러면 Ω에는 n=2^r-1 의 vector들이 있다. H를

열(column)이 Ω의 원소인 행렬이라 하자.

r=3 이면, H 는

로 주어진다.

C를 H' 은 H 로, x 는 x' 으로 치환한 방정식

x'H' = 0 또는 Hx = 0 ………(2)

를 만족하는 모든 이항(binary) n-vector들

x' = (x₁ , x₂ , ... , x_n)

의 code 언어를 취해서 얻어지는 Hamming code

라고 하자. 또, 행렬식 H는 Hamming 코드 C의

parity check matrix 라고 불린다. H의 차수는

r이다.

H는 r개의 줄(row)을 가지므로 차수는 r을 초과할 수

없다.

한편, 마지막 r 번째 열(column) vector들은 분명히

독립이므로 차수는 r보다 작을 수 없다.

그러므로 방정식 (2)에는 k = n- r= 2^r-1-r 개의

독립적인 해가 있다.

따라서 code C는 k 개의 서로 독립인 해들의 모든

가능한 선형결합이라는 2^k개의 단어(word)를

포함한다.

C의 어떤 두 code 언어사이의 거리는 적어도 3

이다.

그러므로 앞의 정리로부터 code C 는 one-error

correcting code이다. 이제 C 에서 두개의 서로

다른 코드언어는 distance 1 또는 2로 할 수 없음을

보이도록 합시다.

u' 과 v' 이 두 별개의 code언어라 하자. 그러면 식

(2) 로부터 u'H'=0, v'H'=0

따라서 (u' - v' )H'=0 ………(3)

만약 d(u',v') = 1 , u' - v' 의 i 번째 좌표가

1이고 다른 좌표는 0 이라 하자.

(3)의 좌변은 H' 의 i 번째 행이 a_i' 인 a_i' 이다.

null-vector는 Ω의 원소가 아니므로

모순(contradiction)이다. 그러므로 의 H' 행이

아니다. 만일 d(u',v') = 2 이고, u' - v'

의 i 번째와 j 번째 좌표( I≠j ) 가 1이고 다른

좌표가 0 이라 하자. 그러면

식 (3)으로부터 a_i' = a_j' (a_i' & a_j' 는 H' 의

i 번째와 j 번째의 행)

H' 의 행들이 모두 다르므로 이에 모순된다.

따라서 d(u',v') ≥ 3 이고 code C는 one-error

correcting code 이다. Q.E.D.

Here we note that the code C obtained here is perfect. Because

q = 2 , t = 1 , n=2^r-1 , N = 2^k ,

where k = n - r. Hence

Example 1. Let r= 3; then for corresponding

Hamming code, H is given by (1); and let

x'=(x₁, x₂, x₃, x₄, x₅, x₆, x₇). Find the

Hamming one-error correcting code.

Solution. x'H' = 0 or Hx = 0 … (3)

free variable x₁, x₂, x₃, x_{4 ;}

Hence we get the 2⁴=16 words of the code :

(0, 0, 0, 0, 0, 0, 0) (1, 1, 1, 1, 1, 1, 1)

(1, 0, 0, 0, 1, 1, 1) (0, 1, 1, 1, 0, 0, 0)

(0, 1, 0, 0, 0, 1, 1) (1, 0, 1, 1, 1, 0, 0)

(0, 0, 1, 0, 1, 0, 1) (1, 1, 0, 1, 0, 1, 0)

(0, 0, 0, 1, 1, 1, 0) (1, 1, 1, 0, 0, 0, 1)

(1, 1, 0, 0, 1, 0, 0) (0, 0, 1, 1, 0, 1, 1)

(1, 0, 1, 0, 0, 1, 0) (0, 1, 0, 1, 1, 0, 1)

(1, 0, 0, 1, 0, 0, 1) (0, 1, 1, 0, 1, 1, 0)

문제 1. Let r= 4. For corresponding Hamming code, H is given by the above method, find the Hamming one-error correcting code.

Decoding rule

전송된 code는 여러 가지 noise 요인에 의하여

원래의 code와 다를 수 있다. 이 때, decode하는

과정에서 가능한한 원래의 code로 복원하기 위하여

우리는 Minimum distance rule에 의한 error

correcting을 하여야 한다. 이에 관하여는 다음

강의에서 학습하기로 한다.

본 강의에서는 암호이론(coding theory) 중에서 Hamming one-error correcting code에 관한 기초적인 이론과 방법에 대하여 학습한다.

제 10 장 암호이론과 그 응용

4. HAMMING ONE-ERROR CORRECTING CODES II

Hamming one-error correcting code를 어떻게 만들었는가 확인하여 보시오. 또, 암호이론에 관한 표준적인 교재를 참고하여 또다른 one-error correcting code를 만드는 방법에 관하여 생각하여 보시오.

본 강의에서는 암호이론(coding theory) 중에서 Hamming one-error correcting code에 관한 기초적인 이론과 방법에 대하여 학습한다.

HAMMING ONE-ERROR CORRECTING

BINARY CODES

HAMMING ONE-ERRORCORRECTING BINARY CODE를 활용하는 방법에 관하여 학습하도록 합시다.

다음의 강의는 R. C. Bose & B. Manvel 저서인

Introduction to Combinatorial Theory

John Wiley & Sons Inc., 1984.

의 7장의 내용을 참고하여 학습하기 바랍니다.

앞에서 학습한 바와 같이, 전송된 code는 여러 가지 noise

요인에 의하여 원래의 code와 다를 수 있다. 이 때,

decode하는 과정에서 가능한한 원래의 code로 복원하기

위하여 우리는 Minimum distance rule에 의한 error

correcting을 하여야 한다.

Minimum distance rule

(I) x' = (x₁, x₂,..., x_n) : transmitted word

y' = (y₁, y₂,..., y_n) : received word.

C : Hamming code

Compare y' with all the code words in C and

There is no error( x' matches y') ⇒ x' = y'

(2) 위의 Example 1의 code인 경우에

y' = (1, 0, 1, 0, 1, 0, 0)가 received word 라면,

y'은 code 모음에 없다. 따라서 minimum distance

rule에 의하여 y' 에서 최소거리 1인 x' 를 C

code에서 찾으면 x' = (1, 0, 1, 1, 1, 0, 0).

따라서, x'이 transmitted word 이다.

REMARK. The number of comparisons needed

for the minimum distance decoding rule

is . increases rapidly with r.

Thus, when r=3 ,=2⁴=16

r=4, N = 2¹¹ = 2048

r=5, N = 2²⁶ = 77,108,864

Thus the minimum distance rule becomes

impractical when r is moderately large.

(3) x' = (x₁, x₂,..., x_n) : transmitted word

y' = (y₁, y₂,..., y_n) : received word.

e' = (e₁, e₂,... e_i,..., e_n) : error vector (where e_i=1)

e₁= 0 ⇔ i- th coordinate has been correctly transmitted.

w(e') : number of errors in the transmission.

Now y' = x' + e'

Therefore, y'H' = x'H' + e'H'

x'H' = 0 (x' : code word from (2))

Hence y'H' = e'H'

We define y'H' to be the syndrome of the

received word y' .

(1) y'H' = 0 (null vector) ⇔ no error

⇔ y' : transmitted word(x' )

(2) If there is one error, say in the I-th

coordinate, then the syndrome is h_i' , the I-th

row of H'.

If the syndrome matches the i-th row of H'

conclude that there is an error in the I-th

coordinate and the transmitted word

is x' = y'- e_i' , where

e_i' = (0, 0, … , 1, …, 0)

[in the th coordinate is 1, & the other coordinates are zero］

In the above Example 1,

(ⅰ) y' = ( 1, 1, 0, 0, 1, 0, 0) : received word

y' H' = (0, 0, 0, 0, 0, 0, 0) : null vector

thus x' = y'

(ⅱ) y' =(1, 0, 1, 0, 1, 0, 0) : received word

y' H' = Hy

Since this matches the fourth row of H' ,

then e' =(0, 0, 0, 1, 0, 0, 0). Thus

x' = y'-e' =

(1, 0, 1, 0, 1, 0, 0) - (0, 0, 0, 1, 0, 0, 0)

= (1, 0, 1, 1, 1, 0, 0)

Once the syndrome has been calculated the

number of comparisons needed is n=2^r-1,

which is 15 for r = 4, & 31 for r = 5.

Example 2. The parity check matrix of a

one-error correcting binary Hamming code is

taken as



Answer the following questions :

(a) Supply the missing coodinate in code word

    (1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0,…)

(b) What is the conclusion regarding the

transmitted word if the received word is

(1) (1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1)

(2)  (1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1)

(3) (1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1)