[09] Cyclic Codes

[n,k] linear code가 cyclic shift해도 codeword를 유지하면, cyclic code라고 한다.

 

Code는 두 가지 형식으로 표현이 가능하다.

• Vector representation : $ c = (c_0, c_1, ..., c_{n-1})$
• Polynomial representation : $ c(x) = c_0 + c_1x + c_2x^2 + ... + c_{n-1}x^{n-1} $

두 표현 모두 일대일 대응이다.

 

먼저 Polynomial representation을 가정한다. $c(x)$에 $x^kc(x)$를 하고 $(x^n -1)$로 mod 연산을 해주면 cyclic을 구현할 수 있게 된다. 쉽게 말하면 다음과 같다.

• $a(x)c(x) mod x^n-1 $도 codeword이다.

$c(x)$는 $m(x)$와 $g(x)$, generator로 생성되며 cyclic code의 $g(x)$는 smallest degree의 unique한 성질을 가지고 있다. 기본적으로 $x^n-1$ 연산이 지원되야 하기 때문에 ${x^n-1 \over g(x)}=h(x)$로 구현한다.

• $c(x) = m(x)g(x)$
• $g(x)$의 degree r= n-k
• $g(x) = x^{n-k} + ... +a_1x+a_0$, $a_0 != 0$
• $m(x) = m_0 + m_1x+ ... + m_{k-1}x^{k-1}$
• 따라서, $c(x)$의 degree = k-1+n-k = n-1

 

그래서 $g(x)$ 한번 구해보자. n=7이라고 하면 $g(x)$는 $x^7-1$의 인수 중에 하나이다.

• $x^7-1=(x+1)(x^3+x+1)(x^3+x^2+1)$

 

만약 $x^3+x+1$을 $g(x)$로 쓴다고 생각하면, (두 개의 인수를 조합해서 써도 된다.)

• n=7
• r=3=n-k
• 따라서, k=4

 

그래서 모든 가능한 code 중 일부는 다음과 같다.

GF(2)는 binary를 의미하며, 1+1=2 mod 2 = 0을 의미하게 된다.

 

그래서 진짜 generator matrix, $G$는 다음처럼 만든다.

 

 

Parity check matrix는 아까 $x^n-1 = g(x)h(x)$를 이용해 $H$를 구한다.

• $c(x)h(x) = m(x)g(x)h(x) = m(x)(x^n-1) = m(x)x^n - m(x)$
• $m(x)$의 degree가 $k$ 였으므로, $x^k$부터는 계산에 포함이 안된다.
• 그래서 syndrome을 구할 수 있게 된다.

 

그래서 $g(x)=x^3+x+1$이고 n=7이라면, $h(x)=x^4+x^2+x+1$이니까 다음처럼 G와 H를 구할 수 있다.

 

Systematic encoding이란 message가 codeword에 포함되며 n-k bit는 parity bit로 채워지는 것을 말한다. 그래서 $m(x)$를 n-k shift하고 $g(x)$로 나누어 몫 $Q(x)$와 나머지 $r(x)$를 구한다. 그러고 나서 $r(x)$를 parity check bit로 이용한다. 그러면 cyclic code를 구현할 수 있다.

• $m(x)x^{n-k} = Q(x)g(x) + r(x)$
• $Q(x)g(x) = r(x) + m(x)x^{n-k}$
• 그래서 $c(x) = r(x) + m(x)x^{n-k}$

 

(HWJ 설명 들을 예정)

Message = $x^3 + x^2 + 1$ // $g(x) = x^3+x+1$

 

1 / 2

3 / 4

 

이런식으로 parity-bit를 채우면 된다.

 

Decoding은 이렇게 한다.

 

아니 이걸 ?