[정보이론] 순회 부호 (Cyclic code)

순회 부호 (Cyclic code)

특징

- 선형부호 중 실용상 가장 중요한 부분

- 부호화, 신드롬 계산이 간단함

- 복호 간단함

 

벡터 v

0, 1을 성분으로 하는 n차원 벡터

$ v = (v_{n-1}, v_{n-2}, ... , v_{1}, v_{0}) $

 

 

부호다항식 : 각 부호어에 대응하는 다항식

벡터 v의 다항식 표현

부호 길이 n인 부호는 n-1차 '이하'의 다항식

( v = (0, 0, ... , 1) -> 성분의 값이 0이면 차수가 낮아질 수 있어서 '이하' )

 

 

 

순시 부호의 생성

생성 다항식

(단 , $g_{i}$ 는 0 또는 1)

생성 다항식의 차수 = 검사 기호수

 

 

부호

(단, A(x)는 n - m - 1 차 이하의 임의의 다항식)

W(x) : n - 1 차 이하 다항식

G(x) : m 차 이하 다항식

따라서, A(x)는 n -1 - m 차 이하 다항식

 

G(x) | $(x^{n} - 1)$ 이 만족되어야 함

- $(x^{n} - 1)$ 가 G(x)로 나누어 떨어짐

- G(x) | $(x^{n} - 1)$ 이 성립하는 최소의 양의 정수를 G(x)의 주기라고 함 

 

순회 부호의 예

순회 부호는 선형 부호

 

선형 부호

- 임의의 부호어의 합이, 또 다른 부호어가 되는 부호

$W_{1}(x) = A_{1}(x)G(x)$

$W_{2}(x) = A_{2}(x)G(x)$

 

$W_{1}(x) + W_{2}(x) = [ A_{1}(x) + A_{2}(x)]G(x)$

 

A(x)G(x) = > 다른 부호어 생성 = 선형 부호

 

순시 부호의 예

부호길이 n = 7

생성 다항식의 차수 m = 4 일때,

 

생성 다항식 $G(x) = x^{4} + x^{3} + x^{2} + 1$

부호 다항식 $W(x) = w_{6}x^{6} + ... + w_{1}x + w_{0}$

 

A(x) = x 인 경우,

$A(x)G(x) = x(x^{4} + x^{3} + x^{2} + 1) = x^{5} + x^{4} + x^{3} + x = 0111010 $

$0x^{6} + x^{5} + x^{4} + x^{3} + 0x^{2} + x + 0$

 

 

 

부호 성분의 치환

부호어 성분을 순회 치환하여도 부호어

 

순회 부호에 의한 오류 검출

오류의 검출

수신어가 y 부호어인지 검사하는 것

 

y(x)가 G(x)로 나누어 떨어지는지 검사

- 나눗셈 회로에 넣어 나머지가 0이 되는지 확인

w(x) = A(x)G(x) 송신하여 

y(x) = A(x)G(x) 수신

y(x)를 G(x)로 나누었을 때 나머지가 0이 되면 부호어임