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} + \dots + c_2x^2 + c_1x+c_0, \
  \mbox{상수 }c_i(i=1, 2, ..., n)\mbox{ 은 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)=\mbox{rem}\left[\frac{m(x)x^{n-k}}{g(x)}\right]
  $$
• 오류 다항식을 e(x)라고 표현하면 수신 신호 다항식과 Syndrome 다항식 간의 관계는 다음과 같음
  $$
  s(x)=\mbox{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) = \mbox{rem}\left[\frac{m(x)x^{n-k}}{g(x)}\right] = \mbox{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^10+x^8+1,\quad 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) = \mbox{rem}\left[\frac{m(x)x^4}{g(x)}\right]\
  = \mbox{rem}\left[\frac{x^{14}+x^{12}+x^4}{x^4+x+x}\right]\
  = x^2 + 1
  $$
• 따라서 c(x)를 구하는 식을 이용하면 아래와 같은 coder를 얻을 수 있음