[정보이론] 단일 패리티 검사부호, (n,k)조직부호, 선형부호

단일 패리티 검사부호

단일 오류의 검출과 정정에 사용

 

 

단일 패리티 검사 부호 w

가정

0,1로 구성되는 길이 k인 계열 $ x_{1}, x_{2}, ... , x_{k} $ 를 2원 통신로로 보냄

 

계열에 포함되는 1의 수가 짝수가 되도록 하나의 기호를 부가

오류가 1개 발생하면 1의 수가 홀수가 됨

(반대로, 1의 수가 홀수가 되도록 기호를 부가해도됨)

 

부가하는 기호 C

$ C = x_{1} + x_{2} + ... + x_{k} $

(단, +는 배타적 논리합 또는 mod2 연산)

 

$ x_{1}, x_{2}, ... , x_{k} $ 에 포함되는 1의 수가 홀수 일 때,

$ x_{1} + x_{2} + ... + x_{k} = 1 $

 

$ x_{1}, x_{2}, ... , x_{k} $ 에 포함되는 1의 수가 짝수 일 때, 

$ x_{1} + x_{2} + ... + x_{k} = 0 $

 

단일 패리티 검사 부호

$ w = x_{1}x_{2}...x_{k}c $

 

또는

통신로를 통해 송신되는 기호 w

$w = (x_{1}, ... , x_{k}, c)$

$x_{1}, x_{2}, ... , x_{k}$는 정보기호, c는 검사기호

 

k개의 정보 비트로부터 1개의 검사 비트 계산, 부가하여 부호화

1의 수가 짝수인 모든 2원 계열로 구성되는 부호 길이가 n = k + 1,

부호어 수가 $ M = 2^{k} $인 부호 이용

 

예시) 

K = 2일 때,

정보비트 2개 {00, 01, 10, 11} , 검사비트 1개 {0, 1}

부호길이 n = 3, 부호어 수 M = 4가 된다.

그러면 C = {000, 011, 101, 110}

 

 

패리티 검사 방정식

단일 패리티 검사 부호 c의 부호어를 $ w = (w_{1}, w_{2}, ... , w_{n}) $이라 하면

$ w_{n} = w_{1} + w_{2} + ... + w_{n-1} $

 

패리티 검사 방정식

$ w_{1} + w_{2} + ... + w_{n-1} + w_{n} = 0 $

 

배터적 논리합

 

C의 부호어가 되기 위한 필요충분 조건

패리티 검사 방정식이 성립해야만 부호어가 됨

 

오류 패턴

부호어 w를 전송하여 $y = (y_{1}, y_{2}, ... , y_{n}) $이 수신되었다고 가정

y 는 w 에 오류 $ e = (e_{1}, e_{2}, ... , e_{n}) $이 더해진 것

$y = w + e = (w_{1} + e_{1}, w_{2} + e_{2}, ... , w_{n} + e_{n}) $

$e_{i} ( i = 1, 2, ... , n) $

i 성분에 오류가 발생하면, $e_{i} = 1$

i 성분에 오류가 발생하지 않을 경우, $e_{i} = 0$

여기서 $ e =(e_{1}, e_{2}, ... , e_{n})$ 는오류 패턴

 

 

신드롬

수신어 y를 패리티 검사 방정식에 대입

 

$ s = y_{1} + y_{2} + ... + y_{n} $

 

$ s = w_{1} + e_{1} + .... + w_{n} + e_{n} $

$    = w_{1} + w_{2} + ... + w_{n} + e_{1} + ... + e_{n} $

$    = 0 + e_{1} + ... + e_{n} $

 

오류가 있다면, s = 1

오류가 없다면, s = 0

 

패리티 검사 방정식

$ w_{1} + w_{2} + ... + w_{n-1} + w_{n} = 0 $

 

 

조직 부호 (Systematic code)

k개의 정보 기호로부터 n - k개의 검사 기호를 일정한 방법으로 구하여 부가함으로써 부호 길이가 n인 부호로 부호화

 

 

(n, k) 부호

부호 길이가 n, 정보 기호수가 k인 조직 부호

 

효율

$\eta = \frac{k}{n}$

 

부가된 길이

n - k 

 

 

선형 부호 (Linear code)

검사 기호가 정보 기호의 선형식으로 주어지는 부호

예시)

단일 패리티 검사 부호 $ c = x_{1} + x_{2} + ... + x_{k}$

 

임의의 두 가지 부호어에 관해 그 성분마다의 합을 취하면 그것이 또한 부호어가 됨

예시)

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

동일한 위치에 있는 성분끼리의 합을 하면 그것 또한 '부호어'