BCH코드.1

도입

BCH 코드는 순회부호(Cyclic codes)의 하위 분야이며, 다중 에러 검출 능력과 인코딩, 디코딩 과정의 편의성으로 잘 알려져있다. BCH 코드는 먼저 정정하고자하는 오류의 개수를 지정한 뒤, 해당 코드의 생성 다항식을 구성한다.

원시 원소(Primitive Element)

GF(q)에서 원시 원소 α란 0을 제외한 GF(q)의 모든 원소가 α의 거듭제곱 형태로 표현될 수 있는 것을 의미한다.

예를 들어 GF(5) = {0,1,2,3,4}에서
$2^0 = 1(mod 5) = 1$
$2^1 = 2(mod 5) = 2$
$2^2 = 4(mod 5) = 4$
$2^3 = 8(mod 5) = 3$
GF(5)의 0을 제외한 모든 원소가 2의 거듭제곱 형태로 표현되므로, GF(5)의 2는 원시원소이다.

$3^0 = 1(mod 5) = 1$
$3^1 = 3(mod 5) = 3$
$3^2 = 9(mod 5) = 4$
$3^3 = 27(mod 5) = 2$
마찬가지로 GF(5)의 0을 제외한 모든 원소가 3의 거듭제곱 형태로 표현되므로, 3도 원시원소이다.

원시 다항식(Primitive Polynomial)

GF(q)상의 원시 다항식 p(x)은 GF(q)상의 기약 다항식이다. 이 다항식은 확장체(extension field)를 구성하는데 사용된다.

• 기약 다항식(Prime polynomial):더이상 인수분해 되지 않는 즉, 1과 자기 자신 외에는 나눌 수 없는 다항식.
• 확장체(extension field): 갈루아 체에서 위수가 소수가 아닌, 소수의 거듭제곱 형태인 갈루아 체.

또한 GF(q)상에서 모든 차수에 대하여 원시 다항식이 존재한다. 즉 차수를 m이라 할때, GF($q^m$)을 구성할 수 있는 원시다항식이 모든 m에 대하여 존재한다는 것을 의미한다.

예를 들어 원시다항식을 이용해 GF(8) = GF($2^3$)을 생성할 수 있다.
차수가 3인 원시 다항식 $p(x) = x^3 + x + 1$ 일 때, GF(8)의 원시 원소를 $\alpha$라 한다면,
GF(8)상의 모든 원소를 $\alpha$의 거듭제곱 형태로 표현할 수 있다.

$\alpha$의 거듭제곱	GF(8)의 원소
$\alpha^1$	$z$
$\alpha^2$	$z^2$
$\alpha^3$	$z + 1$
$\alpha^4$	$z^2 + z$
$\alpha^5$	$z^2 + z + 1$
$\alpha^6$	$z^2 + 1$
$\alpha^7$	$1$

ex)
$\alpha^3$ 일 때, $\alpha^3$= $z^3$이지만, mod p(x)를 하면 $z + 1$이 된다.
$\alpha^5$ 일 때, $\alpha^5$ = $\alpha^4 \times z$이고 $\alpha^4 = z^2 + z$ 이므로 $\alpha^5 = z^3 + z^2$이며, $(z^3 + z^2) mod p(x) = z^2+z+1$이다.

원시 원소 $\alpha$와 모듈러 연산으로 GF(8)의 모든 원소를 구성하였다. 즉 확장체 GF(8)을 생성하였다. 위의 연산에서 $\alpha^7$의 값은 1로 순환한 것을 확인할 수 있다.

$x^{q-1} -1$의 인수분해

$\beta$를 GF(q)의 비영 원소라 할때, GF(q)에서 $x^{q-1} -1$의 인수분해는 다음과 같다.
$x^{q-1} -1$ = ($x-\beta_1$)($x-\beta_2$)...($x-\beta_{q-1}$)

증명:

$\beta$는 비영 원소이므로 앞서 말했듯이, 원시 원소$\alpha$의 거듭제곱 형태로 표현될 수 있다.

$\beta$ = $\alpha^r$이라고 하면,
$\beta^{q-1} = ((\alpha)^r)^{q-1} = ((\alpha)^{q-1})^r = 1^r = 1$이다.
따라서 모든 비영 원소인 $\beta$는 $x^{q-1} -1 = 0$의 근이다.

예를 들어 GF(5) = {0,1,2,3,4}라고 할 때, 비영 원소는 {1,2,3,4}이므로
$x^4 - 1 = (x-1)(x-2)(x-3)(x-4)$이다.

원시 블록의 길이(Primitive Blocklength)

원시 블록의 길이는 유한체에서 원시 원소의 주기(Period)를 뜻한다. 원시 원소의 거듭제곱이 다시 1이 되기까지 필요한 거듭제곱의 수를 의미한다. 즉 유한체에서 비영 원소의 개수와 같다.

원시 블록 길이를 n이라 할때, n = $q^m-1$ 이다. (q: 위수, m: 차수)
ex)GF(8) = GF($2^3$)이므로 n = $2^3 - 1 = 7$이며 앞서 $\alpha^7 = 1$ 임을 확인하였다.

확장체(Extension Field)

유한체 GF($q^m$)은 GF(q)의 확장체이다.
원시 블록 길이를 n이라 할때, n = $q^m-1$ 이다. (q: 위수, m: 차수)
이때 $x^n -1$ 을 인수분해하면,

$x^n - 1 = x^{q^m-1} -1 = f_1(x)f_2(x)..f_p(x)$ 이다.

예를들어, GF(2)와 그 확장체인 GF(8)을 생각해보자.
q = 2이고, m = 3이다.

$x^{q^m-1} -1 = x^7 -1$의 인수분해는
$x^7 -1 = (x-1)(x^3+x+1)(x^3+x^2+1)$이다.

다음으로 GF(8)의 원소들은 아래 표에 따라

$GF(8)$ = {$0,1,z,z+1,z^2,z^2+1,z^2+z,z^2+z+1$}이다.

그러므로
$x^{q^m-1} -1 = x^7 -1$
= $(x-1)(x-z)(x-z-1)(x-z^2)(x-z^2-1)(x-z^z-z)(x-z^2-z-1)$
= $(x-1)[(x-z)(x-z^2)(x-z^2-z)] \times[(x-z-1)(x-z^2-1)(x-z^2-z-1)]$ 이다.

$(x^3 + x+ 1) = (x-z)(x-z^2)(x-z^2-z)$
$(x^3 +x^2+1) =(x-z-1)(x-z^2-1)(x-z^2-z-1)$

---

위의 다항식을 계산하는 방법..

$(x^3 + x+ 1) = (x-z)(x-z^2)(x-z^2-z)$
$(x-z)(x-z^2)(x-z^2-z)$을 전개하면

$x^3-2x^2z^2-2x^2z+xz^4+3xz^3+xz^2-z^5-z^4$ 이다.

여기서

• $xz^4 = x(z^2 + z)$
• $3xz^3 = 3x(z + 1)$
• $z^5 =z^2 +z + 1$
• $z^4 = z^2 + z$

이다. (위의 변환 표 참고)

이를 대입하여 식을 다시 써보면
$x^3-2x^2z^2-2x^2z+xz^4+3xz^3+xz^2-z^5-z^4 =$
$x^3-2x^2z^2-2x^2z+xz^2 + xz +3xz + 3x +xz^2-z^2 -z -1 -z^2 -z$이다.

GF(8)은 GF(2)의 확장체이므로 기본적으로 modulo-2연산을 적용한다.

즉 같은 원소를 짝수 번 더하면 0, 홀수 번 더하면 자기 자신이며, 덧셈과 뺄셈 연산은 동일하다.

예를 들어

• $-2x^2z^2 = -(x^2z^2 + x^2z^2) = -1 \times 0 = 0$이 되어 사라진다.

• $3x = x + (x + x) = x + 0 = x$이다.

또한 $-1$은 $+1$과 같다.

이를 바탕으로 식을 정리하면
$x^3 + x + 1$을 구할 수 있다.