BCH 부호

부호 이론에서 BCH 부호(Bose–Chaudhuri–Hocquenghem Code)는 유한체 (또는 갈루아 체)에 대한 다항식을 사용하여 구성되는 순환 오류 정정 부호의 한 종류이다. BCH 부호는 1959년 프랑스 수학자 알렉시 오캥겜이 발명했으며, 1960년 라지 찬드라 보스와 D. K. 레이-초두리가 독립적으로 발명했다. Bose–Chaudhuri–Hocquenghem (및 약어 BCH)라는 이름은 발명가들의 성(姓) 첫 글자에서 유래했다 (레이-초두리의 경우 잘못된 것).

BCH 부호의 주요 특징 중 하나는 부호 설계 중에 부호로 수정 가능한 심볼 오류 수에 대해 정밀하게 제어할 수 있다는 것이다. 특히, 여러 비트 오류를 수정할 수 있는 이진 BCH 부호를 설계할 수 있다. BCH 부호의 또 다른 장점은 추상대수학적 방법인 신드롬 디코딩을 통해 쉽게 디코딩할 수 있다는 점이다. 이는 작고 저전력 전자 하드웨어를 사용하여 이러한 부호에 대한 디코더 설계를 단순화한다.

BCH 부호는 위성 통신, 콤팩트 디스크 플레이어, DVD, 디스크 드라이브, USB 플래시 드라이브, 솔리드 스테이트 드라이브, 2차원 바코드와 같은 응용 분야에 사용된다.

정의 및 설명

원시 협의의 BCH 부호

소수 q와 양의 정수 m, d가 주어지고 d ≤ q^m − 1을 만족할 때, 유한체 (또는 갈루아 체) GF(q)에 대한 원시 협의의 BCH 부호는 코드 길이 n = q^m − 1와 최소 거리 d를 가지며 다음 방법으로 구성된다.

α를 GF(q^m)의 원시 원소라고 하자. 모든 양의 정수 i에 대해, m_i(x)를 αⁱ에 대한 GF(q)의 계수를 갖는 최소 다항식이라고 하자. BCH 부호의 생성 다항식은 최소 공배수 g(x) = lcm(m₁(x),…,m_{d − 1}(x))로 정의된다. g(x)는 GF(q)의 계수를 갖는 다항식이며 xⁿ − 1을 나눔을 알 수 있다. 따라서 g(x)로 정의된 다항식 부호는 순환 부호이다.

예시

q = 2 및 m = 4 (따라서 n = 15)라고 하자. 원시 원소 α(z) = z를 사용하여 감소 다항식 z⁴ + z + 1을 기반으로 GF(16) = GF(2⁴)에 대한 d의 다른 값을 고려할 것이다. GF(2)의 계수를 갖는 최소 다항식 m_i(x)는 다음을 만족하는 14개가 있다.

$m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+1\right)}}=0.$

최소 다항식은 다음과 같다.

${\begin{aligned}m_{1}(x)&=m_{2}(x)=m_{4}(x)=m_{8}(x)=x^{4}+x+1,\\m_{3}(x)&=m_{6}(x)=m_{9}(x)=m_{12}(x)=x^{4}+x^{3}+x^{2}+x+1,\\m_{5}(x)&=m_{10}(x)=x^{2}+x+1,\\m_{7}(x)&=m_{11}(x)=m_{13}(x)=m_{14}(x)=x^{4}+x^{3}+1.\end{aligned}}$

$d=2,3$인 BCH 부호는 생성 다항식

$g(x)={\rm {lcm}}(m_{1}(x),m_{2}(x))=m_{1}(x)=x^{4}+x+1.\,$

를 갖는다.

최소 해밍 거리는 3 이상이며 최대 한 개의 오류를 수정한다. 생성 다항식의 차수가 4이므로 이 부호는 11개의 데이터 비트와 4개의 체크섬 비트를 갖는다. 이 부호는 (15, 11) BCH 부호로도 표기된다.

$d=4,5$인 BCH 부호는 생성 다항식

${\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x))=m_{1}(x)m_{3}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)=x^{8}+x^{7}+x^{6}+x^{4}+1.\end{aligned}}$

을 갖는다.

최소 해밍 거리는 5 이상이며 최대 두 개의 오류를 수정한다. 생성 다항식의 차수가 8이므로 이 부호는 7개의 데이터 비트와 8개의 체크섬 비트를 갖는다. 이 부호는 (15, 7) BCH 부호로도 표기된다.

$d=6,7$인 BCH 부호는 생성 다항식

${\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x),m_{5}(x),m_{6}(x))=m_{1}(x)m_{3}(x)m_{5}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1.\end{aligned}}$

을 갖는다.

최소 해밍 거리는 7 이상이며 최대 세 개의 오류를 수정한다. 생성 다항식의 차수가 10이므로 이 부호는 5개의 데이터 비트와 10개의 체크섬 비트를 갖는다. 이 부호는 (15, 5) BCH 부호로도 표기된다. (이 특정 생성 다항식은 QR 코드의 "형식 정보"에 실제 응용된다.)

$d=8$ 이상인 BCH 부호는 생성 다항식

${\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),...,m_{14}(x))=m_{1}(x)m_{3}(x)m_{5}(x)m_{7}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)\left(x^{4}+x^{3}+1\right)=x^{14}+x^{13}+x^{12}+\cdots +x^{2}+x+1.\end{aligned}}$

을 갖는다.

이 부호는 최소 해밍 거리가 15이고 7개의 오류를 수정한다. 1개의 데이터 비트와 14개의 체크섬 비트를 갖는다. 이 부호는 (15, 1) BCH 부호로도 표기된다. 실제로 이 부호는 000000000000000과 111111111111111 (자명한 반복 부호) 두 개의 코드워드만 갖는다.

일반 BCH 부호

일반 BCH 부호는 원시 협의의 BCH 부호와 두 가지 면에서 다르다.

첫째, $\alpha$가 $\mathrm {GF} (q^{m})$의 원시 원소여야 한다는 요구사항은 완화될 수 있다. 이 요구사항을 완화하면 코드 길이는 $q^{m}-1$에서 원소 $\alpha$의 차수 $\mathrm {ord} (\alpha )$로 변경된다.

둘째, 생성 다항식의 연속적인 근은 $\alpha ,\ldots ,\alpha ^{d-1}$ 대신 $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$일 수 있다.

정의. 소수 거듭제곱인 유한체 $GF(q)$를 고정하자. $2\leq d\leq n,$ ${\rm {gcd}}(n,q)=1,$ 그리고 $m$이 $n$을 법으로 하는 $q$의 곱셈 위수인 양의 정수 $m,n,d,c$를 선택하자.

이전과 같이, $\alpha$를 $GF(q^{m})$에서 원시 $n$제곱근이라고 하고, 모든 $i$에 대해 $m_{i}(x)$를 $GF(q)$에 대한 $\alpha ^{i}$의 최소 다항식이라고 하자. BCH 부호의 생성 다항식은 최소 공배수 $g(x)={\rm {lcm}}(m_{c}(x),\ldots ,m_{c+d-2}(x))$로 정의된다.

참고: 간략화된 정의에서처럼 $n=q^{m}-1$이면 ${\rm {gcd}}(n,q)$는 1이고, $n$을 법으로 하는 $q$의 차수는 $m$이다. 따라서 간략화된 정의는 실제로 일반 정의의 특별한 경우이다.

특수 경우

• $c=1$인 BCH 부호는 협의의 BCH 부호라고 불린다.
• $n=q^{m}-1$인 BCH 부호는 원시라고 불린다.

BCH 부호의 생성 다항식 $g(x)$는 $\mathrm {GF} (q)$의 계수를 갖는다. 일반적으로 $g(x)$를 생성 다항식으로 하는 $\mathrm {GF} (q^{p})$에 대한 순환 부호는 $\mathrm {GF} (q^{p})$에 대한 BCH 부호라고 불린다. $\mathrm {GF} (q^{m})$에 대한 BCH 부호와 $\alpha$의 연속적인 거듭제곱을 근으로 하는 생성 다항식 $g(x)$는 디코더(신드롬) 알파벳이 채널(데이터 및 생성 다항식) 알파벳과 동일한 리드 솔로몬 부호의 한 유형이다. 이는 $\mathrm {GF} (q^{m})$의 모든 원소이다. 다른 유형의 리드 솔로몬 부호는 BCH 부호가 아닌 원래 관점 리드 솔로몬 부호이다.

속성

BCH 부호의 생성 다항식은 차수가 최대 $(d-1)m$이다. 또한 $q=2$이고 $c=1$이면 생성 다항식의 차수는 최대 $dm/2$이다.

이 글을 보려면 오른쪽 ‘펼치기’ 버튼 클릭

각 최소 다항식 $m_{i}(x)$의 차수는 최대 $m$이다. 따라서 $d-1$개의 최소 공배수의 차수는 최대 $(d-1)m$이다. 또한, $q=2$이면 모든 $i$에 대해 $m_{i}(x)=m_{2i}(x)$이다. 따라서 $g(x)$는 홀수 인덱스 $i$에 대한 최대 $d/2$개의 최소 다항식 $m_{i}(x)$의 최소 공배수이며, 각 다항식의 차수는 최대 $m$이다.

BCH 부호는 최소 해밍 거리가 최소 $d$이다.

이 글을 보려면 오른쪽 ‘펼치기’ 버튼 클릭

$d$개 미만의 비영항을 가진 코드워드 $p(x)$가 있다고 가정하자. 그러면

$p(x)=b_{1}x^{k_{1}}+\cdots +b_{d-1}x^{k_{d-1}},{\text{ 여기서 }}k_{1}<k_{2}<\cdots <k_{d-1}.$

$\alpha ^{c},\ldots ,\alpha ^{c+d-2}$가 $g(x)$의 근이므로 $p(x)$의 근임을 기억하자. 이는 $b_{1},\ldots ,b_{d-1}$이 $i\in \{c,\dotsc ,c+d-2\}$에 대해 다음 방정식을 만족함을 의미한다.

$p(\alpha ^{i})=b_{1}\alpha ^{ik_{1}}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0.$

행렬 형태로 표현하면 다음과 같다.

${\begin{bmatrix}\alpha ^{ck_{1}}&\alpha ^{ck_{2}}&\cdots &\alpha ^{ck_{d-1}}\\\alpha ^{(c+1)k_{1}}&\alpha ^{(c+1)k_{2}}&\cdots &\alpha ^{(c+1)k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(c+d-2)k_{1}}&\alpha ^{(c+d-2)k_{2}}&\cdots &\alpha ^{(c+d-2)k_{d-1}}\\\end{bmatrix}}{\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{d-1}\end{bmatrix}}={\begin{bmatrix}0\\0\\\vdots \\0\end{bmatrix}}.$

이 행렬의 행렬식은 다음과 같다.

$\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det {\begin{pmatrix}1&1&\cdots &1\\\alpha ^{k_{1}}&\alpha ^{k_{2}}&\cdots &\alpha ^{k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(d-2)k_{1}}&\alpha ^{(d-2)k_{2}}&\cdots &\alpha ^{(d-2)k_{d-1}}\\\end{pmatrix}}=\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det(V).$

행렬 $V$는 방데르몽드 행렬이며, 그 행렬식은

$\det(V)=\prod _{1\leq i<j\leq d-1}\left(\alpha ^{k_{j}}-\alpha ^{k_{i}}\right),$

는 0이 아니다. 따라서 $b_{1},\ldots ,b_{d-1}=0$이고 $p(x)=0$이다.

BCH 부호는 순환 부호이다.

이 글을 보려면 오른쪽 ‘펼치기’ 버튼 클릭

길이 $n$의 다항식 부호가 순환 부호인 것은 그 생성 다항식이 $x^{n}-1$을 나눌 때뿐이다. $g(x)$가 근 $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$를 갖는 최소 다항식이므로, $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ 각각이 $x^{n}-1$의 근인지 확인하는 것으로 충분하다. 이는 $\alpha$가 정의에 따라 $n$제곱근이라는 사실에서 즉시 도출된다.

인코딩

생성 다항식의 배수인 모든 다항식은 유효한 BCH 코드워드이므로, BCH 인코딩은 단순히 생성 다항식을 인수로 갖는 다항식을 찾는 과정이다.

BCH 부호 자체는 다항식 계수의 의미에 대해 규정하지 않는다. 개념적으로 BCH 디코딩 알고리즘의 유일한 관심사는 수신된 코드워드에 대한 최소 해밍 거리를 가진 유효한 코드워드를 찾는 것이다. 따라서 BCH 부호는 구현자가 메시지를 인코딩된 다항식에 어떻게 포함하느냐에 따라 체계적인 부호로 구현되거나 그렇지 않을 수 있다.

비체계적 인코딩: 메시지를 인수로

생성 다항식의 배수인 다항식을 찾는 가장 간단한 방법은 임의의 다항식과 생성 다항식의 곱을 계산하는 것이다. 이 경우, 임의의 다항식은 메시지의 심볼을 계수로 사용하여 선택할 수 있다.

$s(x)=p(x)g(x)$

예를 들어, POCSAG 등에서 사용되는 (31, 21) 이진 BCH 부호에 사용하도록 선택된 생성 다항식 $g(x)=x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1$을 고려해 보자. 21비트 메시지 {101101110111101111101}을 인코딩하기 위해 먼저 $GF(2)$에 대한 다항식으로 나타낸다.

$p(x)=x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1$

그런 다음 (또한 $GF(2)$에 대해) 계산한다.

${\begin{aligned}s(x)&=p(x)g(x)\\&=\left(x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1\right)\left(x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1\right)\\&=x^{30}+x^{29}+x^{26}+x^{25}+x^{24}+x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{2}+1\end{aligned}}$

따라서 전송된 코드워드는 {1100111010010111101011101110101}이다.

수신기는 이 비트를 $s(x)$의 계수로 사용하고, 오류 정정을 통해 유효한 코드워드를 확인한 후, $p(x)=s(x)/g(x)$를 다시 계산할 수 있다.

체계적 인코딩: 메시지를 접두사로

체계적 부호는 메시지가 코드워드 내 어딘가에 그대로 나타나는 부호이다. 따라서 체계적 BCH 인코딩은 먼저 메시지 다항식을 코드워드 다항식 내에 삽입한 다음, 나머지 (메시지가 아닌) 항의 계수를 조정하여 $s(x)$가 $g(x)$로 나누어떨어지도록 한다.

이 인코딩 방법은 피제수에서 나머지를 빼면 제수의 배수가 된다는 사실을 활용한다. 따라서 이전과 같이 메시지 다항식 $p(x)$를 $x^{n-k}$로 곱하여 (메시지를 나머지에서 "이동"시키기 위해), 다항식의 나눗셈 정리를 사용하여 다음을 얻을 수 있다.

$p(x)x^{n-k}=q(x)g(x)+r(x)$

여기서 $q(x)g(x)$는 유효한 코드워드임을 알 수 있다. $r(x)$는 항상 $n-k$($g(x)$의 차수)보다 작은 차수를 가지므로, 메시지 계수를 변경하지 않고 $p(x)x^{n-k}$에서 안전하게 뺄 수 있으므로, $s(x)$는 다음과 같다.

$s(x)=q(x)g(x)=p(x)x^{n-k}-r(x)$

$GF(2)$ (즉, 이진 BCH 부호)에 대해, 이 과정은 순환 중복 검사를 추가하는 것과 구별할 수 없으며, 체계적 이진 BCH 부호가 오류 감지 목적으로만 사용되는 경우, BCH 부호는 순환 중복 검사의 일반화임을 알 수 있다.

체계적 코딩의 장점은 수신기가 오류 정정을 수행한 후 처음 $k$개 계수 이후의 모든 것을 버림으로써 원본 메시지를 복구할 수 있다는 것이다.

디코딩

BCH 부호를 디코딩하는 데는 여러 알고리즘이 있다. 가장 일반적인 알고리즘은 다음 일반적인 개요를 따른다.

1. 수신된 벡터에 대한 신드롬 s_j를 계산한다.
2. 신드롬으로부터 오류 수 t와 오류 위치 다항식 Λ(x)를 결정한다.
3. 오류 위치 다항식의 근을 계산하여 오류 위치 X_i를 찾는다.
4. 해당 오류 위치에서 오류 값 Y_i를 계산한다.
5. 오류를 정정한다.

이러한 단계 중 일부에서 디코딩 알고리즘은 수신된 벡터에 너무 많은 오류가 있어 수정할 수 없다고 판단할 수 있다. 예를 들어, 적절한 t 값이 발견되지 않으면 정정이 실패한다. 잘린(원시가 아닌) 코드에서는 오류 위치가 범위를 벗어날 수 있다. 수신된 벡터에 코드가 수정할 수 있는 것보다 더 많은 오류가 있는 경우, 디코더는 알 수 없는 사이에 전송된 메시지가 아닌 겉보기에 유효한 메시지를 생성할 수 있다.

신드롬 계산

수신된 벡터 $R$은 올바른 코드워드 $C$와 알 수 없는 오류 벡터 $E$의 합이다. 신드롬 값은 $R$을 다항식으로 간주하고 $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$에서 평가하여 형성된다. 따라서 신드롬은

$s_{j}=R\left(\alpha ^{j}\right)=C\left(\alpha ^{j}\right)+E\left(\alpha ^{j}\right)$

$j=c$부터 $c+d-2$까지.

$\alpha ^{j}$는 $g(x)$의 영점이며, $C(x)$는 그 배수이므로, $C\left(\alpha ^{j}\right)=0$이다. 따라서 신드롬 값을 조사하면 오류 벡터가 분리되어 이를 해결하기 시작할 수 있다.

오류가 없으면 모든 $j$에 대해 $s_{j}=0$이다. 모든 신드롬이 0이면 디코딩이 완료된다.

오류 위치 다항식 계산

비영 신드롬이 있으면 오류가 있는 것이다. 디코더는 오류가 몇 개인지, 그리고 그 오류의 위치를 파악해야 한다.

단일 오류가 있는 경우, 이를 $E(x)=e\,x^{i}$로 작성하며, 여기서 $i$는 오류의 위치이고 $e$는 그 크기이다. 그러면 처음 두 신드롬은 다음과 같다.

${\begin{aligned}s_{c}&=e\,\alpha ^{c\,i}\\s_{c+1}&=e\,\alpha ^{(c+1)\,i}=\alpha ^{i}s_{c}\end{aligned}}$

따라서 이들을 함께 사용하면 $e$를 계산하고 $i$에 대한 일부 정보를 제공한다 (리드 솔로몬 부호의 경우 완전히 결정).

두 개 이상의 오류가 있는 경우,

$E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,$

결과 신드롬을 미지수 $e_{k}$와 $i_{k}$에 대해 어떻게 풀기 시작할지는 즉시 명확하지 않다.

첫 번째 단계는 계산된 신드롬과 가능한 최소 $t$에 호환되는 위치 다항식을 찾는 것이다.

$\Lambda (x)=\prod _{j=1}^{t}\left(x\alpha ^{i_{j}}-1\right)$

이 작업을 위한 세 가지 인기 있는 알고리즘은 다음과 같다.

1. 피터슨–고렌스타인–지얼러 알고리즘
2. 벌러캠프-매시 알고리즘
3. 스기야마 유클리드 알고리즘

피터슨-고렌스타인-지얼러 알고리즘

피터슨의 알고리즘은 일반화된 BCH 디코딩 절차의 2단계이다. 피터슨의 알고리즘은 다항식의 오류 위치 다항식 계수 $\lambda _{1},\lambda _{2},\dots ,\lambda _{v}$를 계산하는 데 사용된다.

$\Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.$

이제 피터슨–고렌스타인–지얼러 알고리즘의 절차를 설명한다. 최소 2t개의 신드롬 s_c, …, s_c+2t−1이 있다고 가정하자. v = t로 설정한다.

1. 신드롬 값을 원소로 하는 $S_{v\times v}$ 행렬을 생성한다.

   $S_{v\times v}={\begin{bmatrix}s_{c}&s_{c+1}&\dots &s_{c+v-1}\\s_{c+1}&s_{c+2}&\dots &s_{c+v}\\\vdots &\vdots &\ddots &\vdots \\s_{c+v-1}&s_{c+v}&\dots &s_{c+2v-2}\end{bmatrix}}.$

2. 다음 원소를 갖는 $c_{v\times 1}$ 벡터를 생성한다.

   $C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.$

3. $\Lambda$는 알려지지 않은 다항식 계수를 나타내며, 다음과 같이 주어진다.

   $\Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.$

4. 행렬 방정식을 형성한다.

   $S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}.$

5. $S_{v\times v}$ 행렬의 행렬식이 0이 아니면, 이 행렬의 역행렬을 찾고 알려지지 않은 $\Lambda$ 값을 풀 수 있다.
6. 만약 $\det \left(S_{v\times v}\right)=0$이면, 다음을 따른다. 만약 $v=0$ 이면 빈 오류 위치 다항식을 선언한다. 피터슨 절차를 중지한다. 종료 $v\leftarrow v-1$로 설정한다. 더 작은 $S_{v\times v}$를 만들어서 피터슨 디코딩의 시작부터 다시 계속한다.
7. $\Lambda$ 값을 얻은 후에는 오류 위치 다항식을 얻은 것이다.
8. 피터슨 절차를 중지한다.

오류 위치 다항식 인수분해

이제 $\Lambda (x)$ 다항식을 얻었으므로, 예를 들어 치앙 검색 알고리즘을 사용하여 무차별 대입 방식으로 $\Lambda (x)=\left(\alpha ^{i_{1}}x-1\right)\left(\alpha ^{i_{2}}x-1\right)\cdots \left(\alpha ^{i_{v}}x-1\right)$ 형식으로 그 근을 찾을 수 있다. 원시 원소 $\alpha$의 지수 거듭제곱은 수신된 단어에서 오류가 발생하는 위치를 나타낸다. 따라서 '오류 위치' 다항식이라고 불린다.

Λ(x)의 영점은 α^−i₁, …, α^−i_v이다.

오류 값 계산

오류 위치가 알려지면 다음 단계는 해당 위치의 오류 값을 결정하는 것이다. 오류 값은 해당 위치에서 수신된 값을 수정하여 원래 코드워드를 복구하는 데 사용된다.

이진 BCH의 경우 (모든 문자가 읽을 수 있는 경우) 이것은 사소하다. 해당 위치에서 수신된 단어의 비트를 뒤집으면 수정된 코드워드를 얻을 수 있다. 더 일반적인 경우, 오류 가중치 $e_{j}$는 선형 시스템을 풀어 결정할 수 있다.

${\begin{aligned}s_{c}&=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\cdots \\s_{c+1}&=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \\&{}\ \vdots \end{aligned}}$

포니 알고리즘

그러나 포니 알고리즘으로 알려진 더 효율적인 방법이 있다.

다음을 가정하자.

$S(x)=s_{c}+s_{c+1}x+s_{c+2}x^{2}+\cdots +s_{c+d-2}x^{d-2}.$

$v\leqslant d-1,\lambda _{0}\neq 0\qquad \Lambda (x)=\sum _{i=0}^{v}\lambda _{i}x^{i}=\lambda _{0}\prod _{k=0}^{v}\left(\alpha ^{-i_{k}}x-1\right).$

그리고 오류 평가 다항식

$\Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}$

마지막으로:

$\Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},$

여기서

$i\cdot x:=\sum _{k=1}^{i}x.$

신드롬이 위치 $i_{k}$에서만 0이 아닐 수 있는 오류 단어로 설명될 수 있다면, 오류 값은 다음과 같다.

$e_{k}=-{\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right) \over \alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}.$

협의의 BCH 부호의 경우, c = 1이므로 표현식은 다음과 같이 단순화된다.

$e_{k}=-{\Omega \left(\alpha ^{-i_{k}}\right) \over \Lambda '\left(\alpha ^{-i_{k}}\right)}.$

포니 알고리즘 계산 설명

이것은 라그랑주 보간법과 생성 함수의 기술을 기반으로 한다.

$S(x)\Lambda (x)$를 고려하고, 간단히 하기 위해 $k>v$인 경우 $\lambda _{k}=0$이고 $k>c+d-2$인 경우 $s_{k}=0$이라고 가정하자. 그러면

$S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+1}\lambda _{i}x^{j}.$

${\begin{aligned}S(x)\Lambda (x)&=S(x)\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{i=0}^{d-2}\sum _{j=1}^{v}e_{j}\alpha ^{(c+i)\cdot i_{j}}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\sum _{i=0}^{d-2}\left(\alpha ^{i_{j}}\right)^{i}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\left(\left(x\alpha ^{i_{j}}\right)^{d-1}-1\right)\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right)\end{aligned}}$

우리는 미지수 $e_{j}$를 계산하려고 하며, $\left(x\alpha ^{i_{j}}\right)^{d-1}$ 항을 제거하여 맥락을 단순화할 수 있다. 이는 오류 평가 다항식으로 이어진다.

$\Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}.$

$v\leqslant d-1$ 덕분에 우리는 다음을 얻는다.

$\Omega (x)=-\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right).$

$\Lambda$ (라그랑주 보간 트릭) 덕분에 $x=\alpha ^{-i_{k}}$에 대한 합은 하나의 합항으로 퇴화된다.

$\Omega \left(\alpha ^{-i_{k}}\right)=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).$

$e_{k}$를 얻으려면 곱을 제거해야 한다. 이미 계산된 $\Lambda$의 근 $\alpha ^{-i_{j}}$에서 곱을 직접 계산할 수도 있지만, 더 간단한 형태를 사용할 수도 있다.

형식 미분으로

$\Lambda '(x)=\lambda _{0}\sum _{j=1}^{v}\alpha ^{i_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right),$

우리는 다시 하나의 합항만 얻는다.

$\Lambda '\left(\alpha ^{-i_{k}}\right)=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).$

그래서 마지막으로

$e_{k}=-{\frac {\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right)}{\alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}}.$

이 공식은 $\Lambda$ 형태의 형식 미분을 계산할 때 유리하다.

$\Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}$

다음 결과를 산출한다.

$\Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},$

여기서

$i\cdot x:=\sum _{k=1}^{i}x.$

확장 유클리드 알고리즘 기반 디코딩

다항식 Λ과 오류 위치 다항식을 찾는 다른 과정은 야스오 스기야마(Yasuo Sugiyama)의 확장 유클리드 알고리즘 변형을 기반으로 한다. 읽을 수 없는 문자 보정은 알고리즘에 쉽게 통합될 수 있다.

$k_{1},...,k_{k}$를 읽을 수 없는 문자의 위치라고 하자. 이 위치를 국소화하는 다항식 $\Gamma (x)=\prod _{i=1}^{k}\left(x\alpha ^{k_{i}}-1\right)$을 생성한다. 읽을 수 없는 위치의 값을 0으로 설정하고 신드롬을 계산한다.

포니 공식에서 이미 정의했듯이 $S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}$라고 하자.

다항식 $S(x)\Gamma (x)$와 $x^{d-1}$의 최소 공약수를 찾기 위해 확장 유클리드 알고리즘을 실행해 보자. 목표는 최소 공약수를 찾는 것이 아니라, 차수가 최대 $\lfloor (d+k-3)/2\rfloor$인 다항식 $r(x)$와 $r(x)=a(x)S(x)\Gamma (x)+b(x)x^{d-1}$을 만족하는 다항식 $a(x),b(x)$를 찾는 것이다. $r(x)$의 낮은 차수는 $a(x)$가 $\Lambda$에 대한 확장된( $\Gamma$에 의해) 정의 조건을 만족할 것을 보장한다.

$\Xi (x)=a(x)\Gamma (x)$를 정의하고 포니 공식에서 $\Lambda (x)$ 대신 $\Xi$를 사용하면 오류 값을 얻을 수 있다.

이 알고리즘의 주요 장점은 포니 공식에서 필요한 $\Omega (x)=S(x)\Xi (x){\bmod {x}}^{d-1}=r(x)$를 동시에 계산한다는 것이다.

디코딩 과정 설명

목표는 수신된 단어와 읽을 수 있는 위치에서 가능한 최소한의 차이가 있는 코드워드를 찾는 것이다. 수신된 단어를 가장 가까운 코드워드와 오류 단어의 합으로 표현할 때, 우리는 읽을 수 있는 위치에서 0이 아닌 수가 최소인 오류 단어를 찾으려고 노력한다. 신드롬 $s_{i}$는 다음 조건에 의해 오류 단어를 제한한다.

$s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.$

이러한 조건을 따로 작성할 수도 있고, 다항식을 생성할 수도 있다.

$S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}$

그리고 거듭제곱 $0$에서 $d-2$까지의 계수를 비교한다.

$S(x){\stackrel {\{0,\cdots ,\,d-2\}}{=}}E(x)=\sum _{i=0}^{d-2}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}\alpha ^{cj}x^{i}.$

$k_{1}$ 위치에 읽을 수 없는 문자가 있다고 가정하자. 신드롬 집합 $\{s_{c},\cdots ,s_{c+d-2}\}$를 방정식 $t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}$로 정의된 신드롬 집합 $\{t_{c},\cdots ,t_{c+d-3}\}$으로 대체할 수 있다. 오류 단어에 대해 원래 신드롬 집합 $\{s_{c},\cdots ,s_{c+d-2}\}$의 모든 제한이 유효하다고 가정하자. 그러면

$t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}=\alpha ^{k_{1}}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}-\sum _{j=0}^{n-1}e_{j}\alpha ^{j}\alpha ^{ij}=\sum _{j=0}^{n-1}e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)\alpha ^{ij}.$

새로운 신드롬 집합은 오류 벡터를 제한한다.

$f_{j}=e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)$

원래 신드롬 집합이 오류 벡터 $e_{j}$를 제한한 것과 같은 방식으로. 좌표 $k_{1}$을 제외하고, 여기서 $f_{k_{1}}=0$이며, $e_{j}=0$이면 $f_{j}$는 0이다. 오류 위치를 찾는 목적으로 모든 읽을 수 없는 문자를 반영하기 위해 신드롬 집합을 유사한 방식으로 변경할 수 있다. 이는 신드롬 집합을 $k$만큼 단축시킨다.

다항식 공식에서 신드롬 집합 $\{s_{c},\cdots ,s_{c+d-2}\}$를 신드롬 집합 $\{t_{c},\cdots ,t_{c+d-3}\}$으로 대체하면

$T(x)=\sum _{i=0}^{d-3}t_{c+i}x^{i}=\alpha ^{k_{1}}\sum _{i=0}^{d-3}s_{c+i}x^{i}-\sum _{i=1}^{d-2}s_{c+i}x^{i-1}.$

따라서,

$xT(x){\stackrel {\{1,\cdots ,\,d-2\}}{=}}\left(x\alpha ^{k_{1}}-1\right)S(x).$

$S(x)$를 $S(x)\Gamma (x)$로 대체한 후, 거듭제곱 $k,\cdots ,d-2$ 근처의 계수에 대한 방정식이 필요하다.

주어진 위치의 영향을 제거하면 모두 0으로 구성된 신드롬 집합을 얻게 되는 $v$개 위치를 찾을 수 있다면, 이 좌표에만 오류가 있는 오류 벡터가 존재할 수 있다. $\Lambda (x)$가 이러한 좌표의 영향을 제거하는 다항식을 나타낸다면, 우리는 다음을 얻는다.

$S(x)\Gamma (x)\Lambda (x){\stackrel {\{k+v,\cdots ,d-2\}}{=}}0.$

유클리드 알고리즘에서 우리는 최대 ${\tfrac {1}{2}}(d-1-k)$개의 오류를 수정하려고 한다 (읽을 수 있는 위치에서). 왜냐하면 더 큰 오류 수에서는 수신된 단어로부터 같은 거리에 있는 코드워드가 더 많을 수 있기 때문이다. 따라서 우리가 찾는 $\Lambda (x)$에 대해, 방정식은 다음으로부터 시작하는 거듭제곱 근처의 계수에 대해 유효해야 한다.

$k+\left\lfloor {\frac {1}{2}}(d-1-k)\right\rfloor .$

포니 공식에서 $\Lambda (x)$는 스칼라로 곱해져도 같은 결과를 준다.

유클리드 알고리즘이 ${\tfrac {1}{2}}(d-1-k)$보다 높은 차수를 가진 $\Lambda (x)$를 찾았고, 그 차수와 동일한 수의 서로 다른 근을 가질 수 있지만, 포니 공식은 그 모든 근의 오류를 수정할 수 있다. 어쨌든 그렇게 많은 오류를 수정하는 것은 위험할 수 있다 (수신된 단어에 대한 다른 제한이 없는 경우 특히). 일반적으로 더 높은 차수의 $\Lambda (x)$를 얻은 후에는 오류를 수정하지 않기로 결정한다. $\Lambda (x)$가 높은 중복도를 가진 근을 가지거나 근의 수가 그 차수보다 작은 경우 수정이 실패할 수 있다. 실패는 포니 공식이 전송된 알파벳 외부의 오류를 반환함으로써 감지될 수도 있다.

오류 정정

오류 값과 오류 위치를 사용하여 오류를 정정하고 오류 위치에서 오류 값을 빼서 정정된 코드 벡터를 형성한다.

디코딩 예시

읽을 수 없는 문자가 없는 이진 부호 디코딩

$d=7$이고 $g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1$인 GF(2⁴)의 BCH 부호를 고려해 보자. (이것은 QR 코드에서 사용된다.) 전송될 메시지가 [1 1 0 1 1] 또는 다항식 표기법으로 $M(x)=x^{4}+x^{3}+x+1$이라고 하자. "체크섬" 심볼은 $x^{10}M(x)$를 $g(x)$로 나누고 나머지를 취하여 계산되며, 결과는 $x^{9}+x^{4}+x^{2}$ 또는 [ 1 0 0 0 0 1 0 1 0 0 ]이다. 이것들은 메시지에 추가되므로 전송된 코드워드는 [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ]이다.

이제 전송에 두 개의 비트 오류가 발생하여 수신된 코드워드가 [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]이라고 상상해 보자. 다항식 표기법:

$R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x^{5}+x^{4}+x^{2}$

오류를 수정하기 위해 먼저 신드롬을 계산한다. $\alpha =0010$을 취하면 $s_{1}=R(\alpha ^{1})=1011$, $s_{2}=1001$, $s_{3}=1011$, $s_{4}=1101$, $s_{5}=0001$, $s_{6}=1001$을 얻는다. 다음으로, 다음 첨가 행렬을 행렬-축소하여 피터슨 절차를 적용한다.

$\left[S_{3\times 3}|C_{3\times 1}\right]={\begin{bmatrix}s_{1}&s_{2}&s_{3}&s_{4}\\s_{2}&s_{3}&s_{4}&s_{5}\\s_{3}&s_{4}&s_{5}&s_{6}\end{bmatrix}}={\begin{bmatrix}1011&1001&1011&1101\\1001&1011&1101&0001\\1011&1101&0001&1001\end{bmatrix}}\Rightarrow {\begin{bmatrix}0001&0000&1000&0111\\0000&0001&1011&0001\\0000&0000&0000&0000\end{bmatrix}}$

영행 때문에 S_3×3은 특이 행렬인데, 이는 코드워드에 두 개의 오류만 도입되었으므로 놀라운 일이 아니다. 그러나 행렬의 왼쪽 위 모서리는 [S_2×2 | C_2×1]과 동일하며, 이는 해 $\lambda _{2}=1000$, $\lambda _{1}=1011$을 제공한다. 결과 오류 위치 다항식은 $\Lambda (x)=1000x^{2}+1011x+0001$이며, 이는 $0100=\alpha ^{-13}$ 및 $0111=\alpha ^{-5}$에서 영점을 갖는다. $\alpha$의 지수는 오류 위치에 해당한다. 이 예에서는 오류 값을 계산할 필요가 없는데, 유일하게 가능한 값이 1이기 때문이다.

읽을 수 없는 문자가 있는 디코딩

동일한 시나리오를 가정하되, 수신된 단어에 읽을 수 없는 문자가 두 개 있다고 가정하자 [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. 읽을 수 없는 문자를 0으로 바꾸고 그 위치를 반영하는 다항식 $\Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right)$을 생성한다. 신드롬 $s_{1}=\alpha ^{-7},s_{2}=\alpha ^{1},s_{3}=\alpha ^{4},s_{4}=\alpha ^{2},s_{5}=\alpha ^{5},$ 및 $s_{6}=\alpha ^{-7}$을 계산한다. (GF(2⁴) 동형사상에 독립적인 로그 표기법을 사용한다. 계산 확인을 위해 이전 예에서 사용된 것과 동일한 표현 방식을 덧셈에 사용할 수 있다. $\alpha$의 거듭제곱에 대한 십육진법 설명은 비트별 XOR을 기반으로 하는 덧셈과 함께 순서대로 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9이다.)

신드롬 다항식을 만들어 보자.

$S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{5}x^{4}+\alpha ^{-7}x^{5},$

계산한다.

$S(x)\Gamma (x)=\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}.$

확장 유클리드 알고리즘을 실행한다.

${\begin{aligned}&{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+2\alpha ^{7}x^{6}+2\alpha ^{-3}x^{7}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{-5}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\left(\alpha ^{-7}+\alpha ^{3}\right)x+\left(\alpha ^{3}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-5}+\alpha ^{-6}\right)x^{3}+\left(\alpha ^{3}+\alpha ^{1}\right)x^{4}+2\alpha ^{-6}x^{5}+2x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\left(1+\alpha ^{-4}\right)+\left(\alpha ^{1}+\alpha ^{2}\right)x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-5}+\alpha ^{-4}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\left(\alpha ^{7}+\alpha ^{-7}\right)+\left(2\alpha ^{-7}+\alpha ^{4}\right)x+\left(\alpha ^{-5}+\alpha ^{-6}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-7}+\alpha ^{-4}+\alpha ^{6}\right)x^{3}+\left(\alpha ^{4}+\alpha ^{-6}+\alpha ^{-1}\right)x^{4}+2\alpha ^{5}x^{5}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}{\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.\end{aligned}}$

차수가 3 이하인 다항식에 도달했으며,

${\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},$

다음이 된다.

${\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.$

따라서,

$S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}\right)-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)x^{6}=\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}.$

$\Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}$라고 하자. $\lambda _{0}\neq 1$이라는 점은 신경 쓰지 마라. 무차별 대입 방식으로 $\Lambda$의 근을 찾는다. 근은 $\alpha ^{2}$과 $\alpha ^{10}$이다 (예를 들어 $\alpha ^{2}$를 찾은 후 해당 단항식 $\left(x-\alpha ^{2}\right)$으로 $\Lambda$를 나눌 수 있으며, 결과 단항식의 근은 쉽게 찾을 수 있다).

다음을 가정하자.

${\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{-5}x^{4}\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}{\bmod {x^{6}}}\end{aligned}}$

오류 값 공식을 사용하여 오류 값을 찾아보자.

$e_{j}=-{\frac {\Omega \left(\alpha ^{-i_{j}}\right)}{\Xi '\left(\alpha ^{-i_{j}}\right)}},$

여기서 $\alpha ^{-i_{j}}$는 다항식 $\Xi (x)$의 근이다. $\Xi '(x)=\alpha ^{2}x^{2}.$ 우리는 다음을 얻는다.

${\begin{aligned}e_{1}&=-{\frac {\Omega (\alpha ^{4})}{\Xi '(\alpha ^{4})}}={\frac {\alpha ^{-4}+\alpha ^{-7}+\alpha ^{-5}+\alpha ^{7}}{\alpha ^{-5}}}={\frac {\alpha ^{-5}}{\alpha ^{-5}}}=1\\e_{2}&=-{\frac {\Omega (\alpha ^{7})}{\Xi '(\alpha ^{7})}}={\frac {\alpha ^{-4}+\alpha ^{-4}+\alpha ^{1}+\alpha ^{1}}{\alpha ^{1}}}=0\\e_{3}&=-{\frac {\Omega (\alpha ^{10})}{\Xi '(\alpha ^{10})}}={\frac {\alpha ^{-4}+\alpha ^{-1}+\alpha ^{7}+\alpha ^{-5}}{\alpha ^{7}}}={\frac {\alpha ^{7}}{\alpha ^{7}}}=1\\e_{4}&=-{\frac {\Omega (\alpha ^{2})}{\Xi '(\alpha ^{2})}}={\frac {\alpha ^{-4}+\alpha ^{6}+\alpha ^{6}+\alpha ^{1}}{\alpha ^{6}}}={\frac {\alpha ^{6}}{\alpha ^{6}}}=1\end{aligned}}$

$e_{3}=e_{4}=1$이라는 사실은 놀라운 일이 아니다.

따라서 정정된 코드는 [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0]이다.

적은 수의 오류가 있는 읽을 수 없는 문자 디코딩

오류 수가 적은 경우 알고리즘 동작을 살펴보자. 수신된 단어가 [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ]이라고 하자.

다시, 읽을 수 없는 문자를 0으로 바꾸고 그 위치를 반영하는 다항식 $\Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right)$을 생성한다. 신드롬 $s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1},s_{5}=\alpha ^{0},$ 및 $s_{6}=\alpha ^{2}$를 계산한다. 신드롬 다항식을 생성한다.

${\begin{aligned}S(x)&=\alpha ^{4}+\alpha ^{-7}x+\alpha ^{1}x^{2}+\alpha ^{1}x^{3}+\alpha ^{0}x^{4}+\alpha ^{2}x^{5},\\S(x)\Gamma (x)&=\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}.\end{aligned}}$

확장 유클리드 알고리즘을 실행해 보자.

${\begin{aligned}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}&={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}\\x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+2\alpha ^{-1}x^{6}+2\alpha ^{6}x^{7}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{3}+\alpha ^{1}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\left(\alpha ^{-5}+\alpha ^{5}\right)x+2\alpha ^{-7}x^{2}+2\alpha ^{6}x^{3}+2\alpha ^{4}x^{4}+2\alpha ^{2}x^{5}+2x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\left(1+\alpha ^{2}\right)+\left(\alpha ^{0}+\alpha ^{-6}\right)x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}\end{aligned}}$

차수가 3 이하인 다항식에 도달했으며,

${\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},$

다음이 된다.

${\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}.$

따라서,

$S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{1}x\right)-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)x^{6}=\alpha ^{7}+\alpha ^{0}x.$

$\Lambda (x)=\alpha ^{3}+\alpha ^{1}x$라고 하자. $\lambda _{0}\neq 1$이라는 점은 신경 쓰지 마라. $\Lambda (x)$의 근은 $\alpha ^{3-1}$이다.

다음을 가정하자.

${\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{-7}x+\alpha ^{-4}x^{2}+\alpha ^{5}x^{3},\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{7}+\alpha ^{0}x{\bmod {x^{6}}}\end{aligned}}$

오류 값 공식 $e_{j}=-\Omega \left(\alpha ^{-i_{j}}\right)/\Xi '\left(\alpha ^{-i_{j}}\right)$를 사용하여 오류 값을 찾아보자. 여기서 $\alpha ^{-i_{j}}$는 다항식 $\Xi (x)$의 근이다.

$\Xi '(x)=\alpha ^{-7}+\alpha ^{5}x^{2}.$

우리는 다음을 얻는다.

${\begin{aligned}e_{1}&=-{\frac {\Omega \left(\alpha ^{4}\right)}{\Xi '\left(\alpha ^{4}\right)}}={\frac {\alpha ^{7}+\alpha ^{4}}{\alpha ^{-7}+\alpha ^{-2}}}={\frac {\alpha ^{3}}{\alpha ^{3}}}=1\\e_{2}&=-{\frac {\Omega \left(\alpha ^{7}\right)}{\Xi '\left(\alpha ^{7}\right)}}={\frac {\alpha ^{7}+\alpha ^{7}}{\alpha ^{-7}+\alpha ^{4}}}=0\\e_{3}&=-{\frac {\Omega \left(\alpha ^{2}\right)}{\Xi '\left(\alpha ^{2}\right)}}={\frac {\alpha ^{7}+\alpha ^{2}}{\alpha ^{-7}+\alpha ^{-6}}}={\frac {\alpha ^{-3}}{\alpha ^{-3}}}=1\end{aligned}}$

$e_{3}=1$이라는 사실은 놀라운 일이 아니다.

따라서 정정된 코드는 [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0]이다.

참고 문헌

1차 자료

• Hocquenghem, A. (September 1959), “Codes correcteurs d'erreurs” (프랑스어), 《Chiffres》 (Paris) 2: 147–156 
• Bose, R. C.; Ray-Chaudhuri, D. K. (March 1960), “On A Class of Error Correcting Binary Group Codes” (PDF), 《Information and Control》 3 (1): 68–79, doi:10.1016/s0019-9958(60)90287-4, ISSN 0890-5401, 2022년 10월 9일에 원본 문서 (PDF)에서 보존된 문서 

2차 자료

• Gill, John (n.d.), 《EE387 Notes #7, Handout #28》 (PDF), Stanford University, 42–45쪽, 2022년 10월 9일에 원본 문서 (PDF)에서 보존된 문서, 2010년 4월 21일에 확인함  Course notes are apparently being redone for 2012: http://www.stanford.edu/class/ee387/ 보관됨 2013-06-05 - 웨이백 머신
• Gorenstein, Daniel; Peterson, W. Wesley; Zierler, Neal (1960), “Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect”, 《Information and Control》 3 (3): 291–294, doi:10.1016/s0019-9958(60)90877-9 
• Lidl, Rudolf; Pilz, Günter (1999), 《Applied Abstract Algebra》 2판, John Wiley 
• Reed, Irving S.; Chen, Xuemin (1999), 《Error-Control Coding for Data Networks》, Boston, MA: Kluwer Academic Publishers, ISBN 0-7923-8528-4 

추가 자료

• Blahut, Richard E. (2003), 《Algebraic Codes for Data Transmission》 2판, 케임브리지 대학교 출판부, ISBN 0-521-55374-1 
• Gilbert, W. J.; Nicholson, W. K. (2004), 《Modern Algebra with Applications》 2판, John Wiley 
• Lin, S.; Costello, D. (2004), 《Error Control Coding: Fundamentals and Applications》, Englewood Cliffs, NJ: Prentice-Hall 
• MacWilliams, F. J.; Sloane, N. J. A. (1977), 《The Theory of Error-Correcting Codes》, New York, NY: North-Holland Publishing Company 
• Rudra, Atri, 《CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications》, University at Buffalo, 2012년 12월 18일에 원본 문서에서 보존된 문서