[ Erasure Coding ] 통신/부호 이론 Ch.2

● 블록 부호

:고정된 수의 비트를 갖는 단어의 집합

 이러한 단어를 부호어 라고 한다.

 

 

위 그림과 같이

길이 n인 블록부호가 있다면

1) 길이 k 만큼은 정보가 담긴 info bits

2) 나머지 n-k 만큼은 Parity bits 로 구성된다.

 

이런 블록 부호가 만들어지는 방법은

 

1. 정보원에서 원본 데이터 k 비트를 받아온다.

2. 그 k비트를 부호기(Encoder) 에 넣는다.

3. Encoder에서 Parity bits가 추가되면서 길이 n인 bits가 생성된다. 

 

원본 메시지는 m

Parity가 붙은 결과의 길이는 n이 나온다.

그리고 그렇게 Parity가 붙은 건 c로 표기한다.

 

원본 메시지와 부호 결과의 비율을 R(부효율) 이라고 하며

이는 k / n  로 나타낸다.

 

이를 송신하는 경우에는 오류 벡터가 추가된다.

c+e

 

여기에서 

(n,k) 블록일 땐 길이가 n이니까

2^n개의 부호 중에서 2^k가 부호어로만 사용되고

나머지 2^n - 2^k 는 부호어로 사용되지 않는다. 대신 오류를 검출하고 정정하는 데에 사용된다.

여기서 알아야 하는 개념으로는 해밍중(Hamming weight) 와 해밍거리(Hamming Distance)가 있다.

 

[ 해밍중 ]

길이 n인 부호어 c에서 '0이 아닌 성분의 개수'를 w(c) 로 표현한다.

ex) c=(1110010) 부호어의 해밍중은 'w(c)=4' 이다.

 

 

 

 

[ 해밍 거리 ]

길이가 n인 부호어 u와 v사이의 해밍거리는
두 부호어의 대응하는 성분 중 서로 다른 성분 쌍의 개수

 

 

 

 

---

2 - 1 
패리티 검사 부호

종류는 두 가지가 있다.

• 짝수 Parity 검사 부호 = 1의 개수가 짝수가 되도록 하는 Parity
  ex) 1100P : 1의 개수는 2개 : 이미 짝수 = 1의 개수가 짝수가 되도록 하기 위해서는 P = 0 
        1110P : 1의 개수는 3개 : 홀수 = 1의 개수가 짝수가 되도록 하려면 P=1
  
  
• 홀수 Parity 검사 부호 = 1의 개수가 홀수가 되도록 하는 Parity
  ex) 1100P : 1의 개수는 2개 : 짝수 = 1의 개수가 홀수가 되도록 하려면 P = 1
         1110P : 1의 개수는 3개 : 홀수 = 1의 개수가 홀수가 되도록 하려면 P = 0

 

 

● 특징

  1) 오류 검출에만 사용된다. ( 어디에서 발생했는가는 알 수 없다. )

  2) 그리고 1001 에서 첫 두 비트가 뒤집어진다면 오류를 검출할 수 없을 수도 있다.

  

 

 

하지만! 한 비트를 추가해서 오류 검출 능력을 갖춘다는 것만해도 큰 의미가 있다.

---

2 - 2
반복 부호

정보 비트의 길이 : 1

패리티 비트 : n-1 인 것을 (n,1) 반복 부호라고 한다.

 

(5,1) 일 때

정보 비트가 0 일 때 부호어는 00000

정보 비트가 1 일 때 부호어는 11111

 

사실상 5비트면 경우의 수는 2^5 이지만

정보비트가 1이라면 2개만 부호어로 사용된다. 

 

이 때 에러가 나온다면 검출과 정정까지 가능하다.

 

'00000을 전송'했다.

'수신 : 11000' 이라면
수신단은 11111보다는 00000에 가깝다고 판단한다.

3개의 위치가 다른 것보다는 
2개의 위치가 다른 것이 원본에 더 가깝다고 여기기 때문이다.

따라서, 원본은 0이라는 것도 알 수 있다.

이런 방법처럼, 더 많은 비트를 원본으로 취급하는 것이 '다수결 원칙'이라고 부른다.

 

 

하지만, 3개에 위치에서 에러가 났을 수도 있다.

그럼 원본을 1로 판단하게 되며, 이를 복호 오류라고 한다. 

 

 

반복 부호의 길이가 길어지면 

부호율은 작아지고 ,  오류 정정은 더 잘 할 수 있다. 

---

2 - 3 
부호 이득

 

같은 정보량을 보낼 때, 최대한 더 적은 오류가 발생하도록 하는 방법

 

예제)

원본 Message : '1011'
수신한 Message : '1001' (오류 발생)

세 번째 비트에서 에러가 발생했다.

 

 

이 상황에서 오류 발생을 확인할 수 있는 방법 중에 하나는

각 비트를 2배로 늘리는 것이다.

 

 

예제)

원래 Message : '1011'
부호화된 Message : '10111011'
수신한 Message   : '10100111'

 

= 부호화를 했을 때의 전송 오류 확률과

부호화를 하지 않았을 때 전송 오류 확률이 다르다.

 

부호화를 함으로써 줄어드는 전송 오류 확률

= 부호 이득

 

 

---

2 - 4
정의 및 한계식

 

코드의 길이 : n

정보 비트의 개수 : k

최대 거리 :d min 이라고 하였을 때

아래와 같은 식이 나온다.

 

즉, 코드의 최소 거리는 [ 정보 비트의 개수 + 코드의 총 길이 ] 에 의해 결정된다.

 

 

 

 

 

 

 

ㅡㅡㅡ