04-03. Channel Coding and Error Control

4.3 순환 부호 (Cyclic Code)

---

개념

• Linear Block Code의 종속 부류로 보다 실용적인 구현을 가증하게 하는 순환 구조를 가지고 있음
• 장점
  • 부호화가 쉬움
• 순방향 오류 정정(FEC, Forward Error Check) 시스템에서 사용되는 coding과 decoding가 shift register로 수행되는 cyclic code로 구성됨
• Cyclic code에서 한 code(임의의 cyclic)의 shift는 다른 code를 만들게 되므로, 다항식 형태의 수학적 표현이 사용

Theorem

기본 정의

• n bit의 coder는 다음과 같이 다항식으로 표현 됨
  $$c(x)=c_{n-1}{x}^{n-1}+c_{n-2}{x}^{n-2}+\cdots +c_2{x}^2+c_{1}x+c_0,\text{상수 }{c}_i(i=1,2,...,n)\text{ 은 0 또는 1의 값을 가짐}$$

연산 과정

• Coder는 데이터 다항식 m(x)와 checksum 다항식 c_p(x)의 함수로 표현
  $$c(x)=m(x)x^{n-k}+c_p(x)$$
• 여기서 checksum 다항식 c_p(x)는 m(x)x^(n-k)를 생성 다항식 g(x)로 나눈 나머지를 의미
  $$c_p(x)=\text{rem}\left[\frac{m(x)x^{n-k}}{g(x)}\right]$$
• 오류 다항식을 e(x)라고 표현하면 수신 신호 다항식과 Syndrome 다항식 간의 관계는 다음과 같음
  $$s(x)=\text{rem}\left[\frac{c(x)+e(x)}{g(x)}\right]$$
• 오류가 없는 경우 s(x) = 0 으로 계산 됨
• (n, k) code는 n - k의 linear feedback shift register를 이용하여 쉽게 생성 됨
• Syndrome s(x)도 동린한 linear feedback shift register을 통하여 생성 됨

예시

(7, 4)의 Cyclic code를 구하는 과정

m(x)와 g(x)는 다음과 같이 주어짐

$$m(x)=1+x+x^2+0\cdot x^{3}g(x)=1+x+x^3$$

• 다항식 c_p(x)는 다음과 같이 구할 수 있음

$$c_p(x)=\text{rem}\left[\frac{m(x)x^{n-k}}{g(x)}\right]=\text{rem}\left[\frac{(0\cdot x^3+x^2+x+1)x^3}{x^3+x+1}\right]=x$$

• 이 경우 Cyclic code는 다음과 같이 구해짐
  $$c(x)=m(x)+c_p(x)=x^5+x^4+x^3+x$$

문제

$$m(x)=x^{1}0+x^8+1,g(x)=x^4+x+x$$

로 주어진 Cyclic code 시스템을 고려할 때 c(x)를 구하시오.

• 데이터 다항식 m(x)와 checksum 다항식 c_p(x)는 아래와 같이 구해짐
  $$m(x)x^{n-k}=m(x)x^4=x^{14}+x^{12}+x^4$$
• $$c_p(x)=\text{rem}\left[\frac{m(x)x^4}{g(x)}\right]=\text{rem}\left[\frac{x^{14}+x^{12}+x^4}{x^4+x+x}\right]=x^2+1$$
• 따라서 c(x)를 구하는 식을 이용하면 아래와 같은 coder를 얻을 수 있음