BCH 코드

부호화 이론에서, BCH 코드 또는 Bose-Chaudhuri-Hocquenghem 코드는 유한 필드(Galois 필드라고도 함)에 대한 다항식을 사용하여 구성된 순환 오류 수정 코드의 한 부류를 형성한다. BCH 코드는 1959년 프랑스의 수학자 알렉시스 호크켄헴에 의해 발명되었고, 1960년 라지 보세와 D. K. 레이-하우드후리에 의해 독자적으로 발명되었다.^[1][2][3] 보세-하우드후리-호켄헴(및 약자 BCH)은 발명가 성(레이-하우드후리의 경우 잘못)의 이니셜에서 유래한다.

BCH 코드의 주요 특징 중 하나는 코드 설계 중에 코드로 교정 가능한 기호 오류의 수를 정밀하게 제어한다는 것이다. 특히 다중 비트 오류를 수정할 수 있는 바이너리 BCH 코드 설계가 가능하다. BCH 코드의 또 다른 장점은 디코딩이 쉽다는 것, 즉 디코딩이라고 알려진 대수적 방법을 통해 디코딩할 수 있다는 것이다. 이것은 소형 저전력 전자 하드웨어를 사용하여 이러한 코드의 디코더 설계를 단순화한다.

BCH 코드는 위성 통신,^[4] 컴팩트 디스크 플레이어, DVD, 디스크 드라이브, 솔리드 스테이트 드라이브,^[5] 양자 내성 암호^[6] 및 2차원 바코드 등의 응용 프로그램에 사용된다.

정의 및 일러스트레이션

원시 협센스 BCH 코드

d ≤ q^m - 1과 같은 양의 정수 m과 d를 가진 prime number q와 prime power q를^m 가진 경우, 코드 길이 n = q^m - 1을 가진 유한장(또는 Galois field) GF(q)에 대한 원시 좁은 의미의 BCH 코드는 다음과 같은 방법으로 구성된다.

α를 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(2)에⁴ 대한 d 값을 다르게 고려한다. GF(2) 만족 계수를 갖는 최소 다항식 m_i(x)이 14개 있다.

${\displaystyle m_{i}\좌(\mod ^{i}\우){\bmod {\좌(z^{4}+z+1\우)}}}=0.}$

최소 다항식은

${\displaystyle {\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{정렬}}}$

$d{\displaystyle }$= ${\displaystyle 2}$,${\displaystyle 3}$ ${\displaystyle d=2,3}$을(를) 사용하는 BCH 코드에는 제너레이터 다항식이 있음$$

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

해밍 거리는 최소 3개 이상이며 최대 1개의 오차를 보정한다. 제너레이터 다항식이 도 4이므로 이 코드는 11개의 데이터 비트와 4개의 체크섬 비트를 가진다.

$d{\displaystyle }$= ${\displaystyle 4}$,${\displaystyle 5}$ ${\displaystyle d=4,5}$의 BCH 코드에는 제너레이터 다항식이 있음$$

${\displaystyle {\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{정렬}}}$

해밍 거리는 최소 5개, 최대 2개의 오류를 보정한다. 제너레이터 다항식이 도 8이므로 이 코드는 7개의 데이터 비트와 8개의 체크섬 비트를 가진다.

$d{\displaystyle }$= ${\displaystyle 6}$,${\displaystyle 7}$ ${\displaystyle d=6,7}$의 BCH 코드에는 제너레이터 다항식이 있음$$

${\displaystyle {\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{정렬}}}$

해밍 거리는 최소 7개, 오류는 최대 3개까지 교정한다. 제너레이터 다항식이 도 10이기 때문에 이 코드는 5개의 데이터 비트와 10개의 체크섬 비트가 있다. (이 특정 제너레이터 다항식에는 QR 코드의 형식 패턴으로 실제 응용 프로그램이 있다.)

$d{\displaystyle }$= ${\displaystyle 8}$ ${\displaystyle d=8}$ 이상의$$ BCH 코드에는 제너레이터 다항식이 있음

${\displaystyle {\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{정렬}}}$

이 코드는 해밍 거리 15를 최소화하고 7개의 오류를 수정한다. 1개의 데이터 비트와 14개의 체크섬 비트를 가지고 있다. 실제로 이 코드에는 000000000000000과 11111111111111111111의 두 가지 암호만 있다.

일반 BCH 코드

일반 BCH 코드는 두 가지 측면에서 원시적인 좁은 의미의 BCH 코드와 다르다.

첫째, $\alpha {\displaystyle }$ ${\displaystyle \alpha}$이(가) ${\displaystyle \mathrm{G}}$ F${\displaystyle }$(${\displaystyle q^{}}$ m${\displaystyle {}^{}}$) ${\displaystyle \matrmat {GF} (q^{m})$의 원시 요소라는$$ 요건은 완화할 수 있다$$. 이 요구 사항을 완화함으로써 코드 길이는 ${\displaystyle \mathrm{q}}$ -${\displaystyle {}^{}}$1 ${\displaystyle q^{m}-1}$에서 ${\displaystyle \mathrm{o}}$ r ${\displaystyle \mathrm{d}(\alpha }$)${\displaystyle }$, ${\displaystyle \mathrm {ord}(\alpha$ ),$$$\alpha {\displaystyle }$ 원소의 순서${\displaystyle .}$ ${\displaysty \alpha .}$로 변경된다.

둘째, 발전기 다항식의 연속 루트는 $\alpha {\displaystyle }$ ,${\displaystyle {}^{}}$…${\displaystyle }$,${\displaystyle {}^{}}$ c , , α ${\displaystyle c^{}}$+ ${\displaystyle {\mathrm{d}}^{}}$+ 2 ${\$$alpha$$$^{${\displaystyle {\mathrm{c}}^{}}$$+d-2}},$ ${\displaystyle \dots ,}$ ${\displaystyle {}^{}{d.}^{}}$ . . . .$\displaystylepha \lapa ,\d-1$}에서$$ 실행될 수 있다$.$$}$

정의. $q{\displaystyle }$ ${\displaystyle q}$이(가) 기본 전원인$$ 유한$$ 필드 ${\displaystyle \mathrm{GF}(q}$ ${\displaystyle )}$, ${\displaystyle GF(q)$를 수정하십시오. Choose positive integers ${\displaystyle m,n,d,c}$ such that ${\displaystyle 2\leq d\leq n,}$ ${\displaystyle {\rm {gcd}}(n,q)=1,}$ and ${\displaystyle m}$ is the multiplicative order of ${\displaystyle q}$ modulo ${\displaystyle n.}$

As before, let ${\displaystyle \alpha }$ be a primitive ${\displaystyle n}$th root of unity in ${\displaystyle GF(q^{m}),}$ and let ${\displaystyle m_{i}(x)}$ be the minimal polynomial over ${\displaystyle GF(q)}$ of ${\displaystyle \alpha ^{i}}$ for all ${\displaystyle i}$${\displaystyle$$$ BCH 코드의 발생기 다항식은 최소공통 복수 $g{\displaystyle (}$ ${\displaystyle x}$)${\displaystyle }$= l ${\displaystyle c_{}}$ ${\displaystyle \mathrm{m}}$(${\displaystyle {}_{}}$x${\displaystyle }$)${\displaystyle }$,${\displaystyle {}_{}{c}_{}}$+ ${\displaystyle {\mathrm{d}}_{}}$- ${\displaystyle 2_{}}$(${\displaystyle }$x${\displaystyle }$)${\displaystyle }$. ${\displaystyle g(x)={\rm {lcm}(m_{c})(x),\ldots ,m_{c+d-2}(x)$로 정의된다.$}$

Note: if ${\displaystyle n=q^{m}-1}$ as in the simplified definition, then ${\displaystyle {\rm {gcd}}(n,q)}$ is 1, and the order of ${\displaystyle q}$ modulo ${\displaystyle n}$ is ${\displaystyle m.}$ Therefore, the simplified definition is indeed a special case of the gen에를 바르다

특례

• $c{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle c=1$}을$($를) 가진 BCH 코드를 좁은 의미의 BCH 코드라고 한다$$.
• $n{\displaystyle }$ =${\displaystyle {}^{}}$ ${\displaystyle m^{}}$- ${\displaystyle 1}$ ${\displaystyle n=q^{m}-1$}을$($를) 갖는 BCH 코드를 primary라고 한다$$.

BCH 코드의$$ 제너레이터 ${\displaystyle \mathrm{다항식}}$ $g{\displaystyle (}$ x${\displaystyle }$) ${\displaystyle g(x)}$에 $G{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{F}(q}$ )${\displaystyle }$. ${\displaystyle \mathrmatrm {GF}(q$)의 계수가 있다$.$$}}$ 일반적으로$$ G ${\displaystyle \mathrm{F}}$( ${\displaystyle {}^{}}$ ${\displaystyle p^{}}$) ${\displaystyle \mathrm {GF} (q^{p})$를 g${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle g(x)}$을(를) 사용한 순환 코드를 ${\displaystyle \mathrm{G}}$ F (${\displaystyle {}^{}{q}^{}}$ ) .${\displaystysty \mathrmatrm {GF}$ ($q^{p})$라고 한다.$}$ The BCH code over ${\displaystyle \mathrm {GF} (q^{m})}$ and generator polynomial ${\displaystyle g(x)}$ with successive powers of ${\displaystyle \alpha }$ as roots is one type of Reed–Solomon code where the decoder (syndromes) alphabet is the same as the channel (data and generator polynomial) alpHabet, $G{\displaystyle \mathrm{}}$ ${\displaystyle \mathrm{F}}$ (${\displaystyle q^{}}$ m${\displaystyle {}^{}}$) ${\displaystyle \matrm {GF}(q^{m})$의 모든 요소.$$^[7] 리드 솔로몬 코드의 다른 유형은 BCH 코드가 아닌 원래 뷰 리드 솔로몬 코드다.

특성.

BCH 코드의 제너레이터 다항식은 최대${\displaystyle }$(${\displaystyle \mathrm{d}}$- 1${\displaystyle }$) ${\displaystyle m}$ ${\displaystyle (d-1)m}$을(를) 가지고 있다$.$ 더욱이 ${\displaystyle \mathrm{q}}$= 2 ${\displaystyle q=2} 및$ $c{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle c=1}$일 경우 제너레이터 다항식은 최대 ${\displaystyle \mathrm{dm}/2\mathrm{}}$ ${\dm/2$}을(를$)$한다$.$

BCH 코드는 최소 해밍 거리를 가지고 있다. 적어도 $d{\displaystyle }$ ${\displaystyle d}$.

BCH 코드는 주기적이다.

인코딩

발전기 다항식의 배수인 모든 다항식은 유효한 BCH 코드 워드이기 때문에, BCH 인코딩은 발전기를 인자로 하는 일부 다항식을 찾는 과정일 뿐이다.

BCH 코드 자체는 다항식 계수의 의미에 대해 규범적이지 않다. 개념적으로, BCH 디코딩 알고리즘의 유일한 관심사는 수신된 코드 워드에 대한 최소 해밍 거리를 가진 유효한 코드 워드를 찾는 것이다. 따라서 BCH 코드는 구현자가 인코딩된 다항식 안에 메시지를 포함하도록 선택하는 방법에 따라 체계적인 코드로 구현될 수도 있고 그렇지 않을 수도 있다.

비시스템적 인코딩: 요소로서의 메시지

제너레이터의 배수인 다항식을 찾는 가장 간단한 방법은 일부 임의 다항식과 제너레이터의 곱을 계산하는 것이다. 이 경우 메시지 기호를 계수로 사용하여 임의 다항식을 선택할 수 있다.

${\displaystyle s(x)=p(x)g(x)}$

예를 들어 제너레이터 다항식 $g{\displaystyle (x}$ ${\displaystyle )}$ = ${\displaystyle {}^{}}$ ${\displaystyle {10}^{}}$+ ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}}$+ x ${\displaystyle {6\mathrm{}}^{}}$+ ${\displaystyle {}^{}}$ ${\displaystyle {5\mathrm{}}^{}}$+ x ${\displaystyle {3\mathrm{}}^{}}$+ ${\displaystyle 1}$ ${\displaystyle g(x)=x^{10}+x^{9$를 고려하십시오.$}}+x^{8}+x^{6}+x^{5}+x^{3}+1},$ POCSAG 등이 사용하는 (31, 21) 바이너리 BCH 코드에 사용하기 위해 선택됨$.$ 21비트 메시지 {101011101111011101101}을(를) 인코딩하려면 먼저 ${\displaystyle \mathrm{GF}(2}$) ${\displaystyle GF(2)}$을(를) 통한 다항식으로 표시한다$.$

${\displaystyle 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}$

그런 다음(${\displaystyle G}$ F${\displaystyle }$( ${\displaystyle 2}$) ${\displaystyle GF(2)}$을(를) 통해 계산하십시오.$$

${\displaystyle {\displaysty}s(x)&=p(x)g\\&=\왼쪽(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\오른쪽)\왼쪽(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{정렬}}}}}$

따라서 전송된 암호어는 {1100111010010111101110101010101010101010101010101010101}이다.

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

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

체계적 코드는 메시지가 코드 워드 내의 어딘가에서 말 그대로 나타나는 코드다. 따라서 체계적 BCH 인코딩은 먼저 코드워드 다항식 안에 메시지 다항식을 내장한 다음, $s{\displaystyle }$(${\displaystyle x}$ ) ${\displaystyle s(x)}$이(가)${\displaystyle }g{\displaystyle }$ (${\displaystyle x)}${\$displaystyle$ g$(x)}$로 구분되도록$$ 나머지 (메시지 이외의) 용어의 계수를 조정하는 것을 포함한다$.$

이 인코딩 방법은 배당금에서 나머지를 빼면 디비저의 배수가 된다는 사실을 활용한다. 따라서 만약 우리가 우리의 메시지 다항식 $p{\displaystyle }$($){\displaystyle p(x)}$을 이전과 같이$$ 취하여 ${\displaystyle x^{}}$ ${\displaystyle n^{}}$ -${\displaystyle {}^{}}$k ${\$ x$^{n-k}}}$로 곱한다면,$$ (그 메시지를 나머지 방법으로 "전환"하기 위해) 다항식의 유클리드 분할을 사용하여 다음과 같이 산출할 수 있다.

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

여기서 ${\displaystyle q}$( ${\displaystyle x}$) g${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle q(x)g(x)}$이(가) 유효한 암호어임을 알$$ 수 있다. As ${\displaystyle r(x)}$ is always of degree less than ${\displaystyle n-k}$ (which is the degree of ${\displaystyle g(x)}$), we can safely subtract it from ${\displaystyle p(x)x^{n-k}}$ without altering any of the message coefficients, hence we have our ${\displaystyl$$e$ $s(x)}:$

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

$G{\displaystyle }$ ${\displaystyle F}$(${\displaystyle 2}$ ) ${\displaystyle GF(2)($즉, 바이너리 BCH 코드가 있는 경우)에 대해 이 프로세스는 주기적 중복성 검사를 추가하는 것과 구별할 수 없으며, 체계적 바이너리 BCH 코드가 오류 검출 목적으로만 사용되는 경우, 우리는 BCH 코드가 주기적 중복성 검사의 수학의 일반화에 불과하다는 것을 알게 된다.

체계적 코딩의 장점은 수신기가 오류 수정을 수행한 후 첫 번째 $k{\displaystyle }$ ${\displaystyle k}$ 계수$$ 이후의 모든 것을 버림으로써 원래의 메시지를 복구할 수 있다는 것이다.

디코딩

BCH 코드를 해독하는 알고리즘은 많다. 가장 일반적인 내용은 다음과 같은 일반적인 개요를 따른다.

1. 수신된 벡터에 대한 신드롬 계산_j
2. syndromes의 오류 수 t 및 오류 로케이터 다항식 λ(x) 결정
3. 오류 위치 다항식의 루트를 계산하여 오류 위치 X 찾기_i
4. 해당 오류 위치에서 오류 값 Y를_i 계산하십시오.
5. 오류 수정

이러한 일부 단계에서 디코딩 알고리즘은 수신된 벡터에 오류가 너무 많아 수정할 수 없다고 판단할 수 있다. 예를 들어, 적절한 t 값을 찾지 못하면 보정이 실패할 것이다. 잘린(원시적이지 않은) 코드에서 오류 위치가 범위를 벗어났을 수 있다. 수신된 벡터에 코드가 수정할 수 있는 오류보다 더 많은 오류가 있는 경우 디코더는 자신도 모르게 전송된 메시지가 아닌 명백한 유효 메시지를 생성할 수 있다.

신드롬 계산

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

${\displaystyle s_{j}=R\왼쪽(\알파 ^{j}\오른쪽)=C\왼쪽(\알파 ^{j}\오른쪽)+E\left(\alpha ^{j}\오른쪽)}$

$j{\displaystyle }$${\displaystyle }$= ${\displaystyle c}$ ${\displaystyle j=c}$ ~ c$$${\displaystyle }$+ ${\displaystyle d}$- 2${\displaystyle c+d-2.$$}$

Since ${\displaystyle \alpha ^{j}}$ are the zeros of ${\displaystyle g(x),}$ of which ${\displaystyle C(x)}$ is a multiple, ${\displaystyle C\left(\alpha ^{j}\right)=0.}$ Examining the syndrome values thus isolates the error vector so one can begin to solve for it.

$오류$가 없으면 s ${\displaystyle j_{}}$= 0 ${\displaystyle s_{j}=0}$ 모든 ${\displaystyle \mathrm{j}}$${\displaystyle }$. ${\displaystyle$ j$.}$ 신드롬이 모두 0이면$$ 디코딩이 완료된다.

오류 위치 다항식 계산

만약 0이 아닌 신드롬이 있다면, 오류가 있는 것이다. 디코더는 얼마나 많은 오류와 그 오류의 위치를 알아낼 필요가 있다.

단일 오류가 있는 경우 $E{\displaystyle (}$ x${\displaystyle }$)${\displaystyle }$= e ${\displaystyle x^{}}$ ${\displaystyle i{}^{}}$ ${\displaystyle E(x)=e\,x^{i}$로 입력하십시오. $여기$서 i ${\displaystyle i}$는 오류의 위치이고 e ${\displaystyle$ e}은($으)$의 ${\displaystyle \mathrm{크기}}$입니다. 그럼 처음 두 신드롬은

${\displaystyle {\i1}s_{c}&=e\,\c\nfline ^{c\,i}\s_{c+1}=e\,\nfline ^{i}s_{c}\light}}}$

$따라서{\displaystyle }$ 함께 e ${\displaystyle e}$을(를) 계산하고$$ i ${\displaystyle i}$에 대한 정보를 제공할 수 있다($$Red-Solomon 코드의 경우 완전히 결정).

오류가 두 개 이상일 경우

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

미지의 $e{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$ 및 $i$ ${\displaystyle k_{}}$. ${\displaystyle i_{k}$에 대해 결과적인 신드롬을 해결하는 방법을 시작하는 방법은 즉시 명확하지 않다.$}$

첫 번째 단계는 가능한 최소 $t{\displaystyle }$, ${\displaystyle t,}$ 로케이터$$ 다항식:

${\displaystyle \Lambda(x)=\prod _{j=1}^{t}\왼쪽(x\알파 ^{i_{j}-1\right)}$

이 작업에 널리 사용되는 알고리즘은 다음과 같다.

1. 피터슨-고렌슈타인-지얼러 알고리즘
2. Berlekamp-Massey 알고리즘
3. 스기야마유클리드 알고리즘

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

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

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

이제 피터슨-고렌슈타인-지얼러 알고리즘의 절차.^[9] 적어도 2t_c 신드롬, …, s. let_c+2t−1 v = t.

인자 오류 로케이터 다항식

Now that you have the ${\displaystyle \Lambda (x)}$ polynomial, its roots can be found in the form ${\displaystyle \Lambda (x)=\left(\alpha ^{i_{1}}x-1\right)\left(\alpha ^{i_{2}}x-1\right)\cdots \left(\alpha ^{i_{v}}x-1\right)}$ by b예를 들어 Chien 검색 알고리즘을 사용한 rute 힘. 원시 요소 $\alpha {\displaystyle }$ ${\displaystyle \alpha$}의 지수적인 힘은 수신된 단어에서 오류가 발생하는 위치를 산출하므로$$ '오류 로케이터' 다항식 이름이다.

λ(x)의 0은 α^−i₁, …, α이다^−i_v.

오류 값 계산

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

바이너리 BCH의 경우 (모든 문자를 읽을 수 있는 경우) 이것은 사소한 것이다. 수신된 단어의 비트를 이 위치에서 뒤집기만 하면 수정된 코드 워드가 나온다. 보다 일반적인 경우, 오류 가중치 $e{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$는 선형 시스템을 풀어서 결정할 수 있다$$.

${\displaystyle {\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}}}$

포니 알고리즘

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

내버려두다

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

${\displaystyle 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).}$

그리고 오류 평가자 다항식^[10]

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

마지막으로:

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

어디에

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

syndrome이 ${\displaystyle i_{}}$ k {\$displaystyle i_{k}}$ 위치에서만 0이 아닐 수 있는 오류 워드로 설명될 수 있는 경우보다, 오류 값은 다음과 같다$.$

${\displaystyle e_{k}=-{\alpha ^{i_{k}}\오메가 \left(\alpha ^{-i_{k}}\right) \open \alpha ^{cdot i_{k}}\lambda '\좌(\alpha ^{-i_{-i_{k}).}$

좁은 의미의 BCH 코드의 경우 c = 1로 표현하면 다음과 같이 간단해진다.

${\displaystyle e_{k}=-{\Oomega \left(\alpha ^{-i_{k}\right) \lambda '\left(\alpha ^{-i_{k}}\right)}.}$

Forney 알고리즘 계산 설명

라그랑주 보간과 함수 생성 기법에 근거한다.

Consider ${\displaystyle S(x)\Lambda (x),}$ and for the sake of simplicity suppose ${\displaystyle \lambda _{k}=0}$ for ${\displaystyle k>v,}$ and ${\displaystyle s_{k}=0}$ for ${\displaystyle k>c+d-2.$${}$ 그러면

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

${\displaystyle{\begin{정렬}())\Lambda())&, =S())\left\{\lambda_{0}\prod _ᆰ^ᆱ\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^{나는}\right\}\left\{\lambda_{0}\prod _ᆺ^ᆻ\left(\alpha ^{i_{\ell}}x-1\right)\right\}\\&, =\left\{\sum_{j=1}^{v}e_{j}\alp.하 ^{ci_{j}}\sum _ᆬ^ᆭ\left(\alpha ^{i_{j}}\right)^{나는}x^{나는}\right\}\left\{\lambda_{0}\prod _ᆱ^ᆲ\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 _ᆺ^ᆻ\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 ${\displaystyle j_{}}$, ${\displaystyle e_{j}}$을(를) 계산하려고 하며$$$,{\displaystyle {}^{}}$ (${\displaystyle x^{}}$ ${\displaystyle {{}^{}}^{}}$ ${\displaystyle {{i_{}}^{}}^{}}$ ${\displaystyle {{j{}_{}}^{}}^{}}$) ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$)^{$d-1}$ 항을$$제거하여 컨텍스트를 단순화할 수 있다. 이는 오류 평가자 다항식으로 이어진다.

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

$v{\displaystyle }$ ${\displaystyle ⩽}$ ${\displaystyle d}$ -${\displaystyle 1}$ ${\displaystyle v\leqslant d-1}$ 덕분에$$

${\displaystyle \Oomega(x)=-\lambda_{0}\sum _{j=1}{j}\alpha ^{ci_{j}}\prod_{\ell \in \{1,\cdots,v\}\setminus \{j\}}}}}}}\lftep(\na \i_{x-1\{x-1\l)\lipriftepriftefteprift.}$

$\lambda {\displaystyle \mathrm{}}$ ${\displaystyle \Lambda }($라그랑주 보간술) 덕분에 합은 $x{\displaystyle }$= ${\displaystyle {}^{}}$- ${\displaystyle {i_{}}^{}}$ k ${\$에 대해 하나의 합계만 변질된다.

${\displaystyle \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).}$

${\$를 받으려면 제품을 제거해야 한다$$. $이미{\displaystyle \mathrm{}}$ 계산된 루트 $\alpha {\displaystyle {}^{}}$- ${\displaystyle {{}_{}}^{}}$ ${\displaystyle {j_{}}^{}}$ ${\$${\displaystyle \Lambda}$에서 직접 제품을 계산할 수는 있지만$$, 더 간단한 형태를 사용할 수는 있다.

형식파생상품으로

${\displaystyle \lambda '(x)=\lambda _{0}\sum_{j=1}^{v}\알파 ^{i_{j}}\prod _{\ell \in \{1,\cdots,v\}\setminus \{j\}}}}\좌(\alpha }{{i_{x-1\{x1\l)})}})}}}}}}}}}}}}}}}}}}$

우리는 단지 하나의 summand를 다시 얻는다.

${\displaystyle \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).}$

그래서 마침내

${\displaystyle e_{k}=-{\frac ^{i_{k}}\오메가 \left(\alpha ^{-i_{k}\right)}{\alpha ^{cdot i_{k}}}\lambda '\좌(\alpha ^{-i_{k}).}$

이 공식은 $\lambda {\displaystyle \mathrm{}}$ ${\displaystyle \Lambda }$ 형식의$$ 공식 파생 모델을 계산할 때 유리하다.

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

항복:

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

어디에

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

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

다항식 Ⅱ와 오차 로케이터 다항식을 모두 찾는 대체 과정은 스기야마 야스오의 확장 유클리드 알고리즘 적응에 기초한다.^[11] 읽을 수 없는 문자의 수정도 알고리즘에 쉽게 통합될 수 있다.

${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$.${\displaystyle }$.${\displaystyle }$. . ${\displaystyle k_{}}$ ${\$을(를) 읽을 수 없는 문자의 위치가 되도록$$ 한다. 이러한 위치 $\gamma {\displaystyle \mathrm{}(x}$)${\displaystyle }$= ${\displaystyle \underset{}{\overset{}{}}}$ i${\displaystyle \underset{}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle \underset{}{\overset{}{}}}$( ${\displaystyle x}$ ${\displaystyle {{\alpha k}_{}}^{}}$ ${\displaystyle \mathrm{i}{{}_{}}^{}}$- 1${\displaystyle }$)${\displaystyle }$. ${\displaystyle \감마(x)=\prod \{i=1}^{k}\좌측(x\alpha ^{k_{i}-1\right$)을 생성한다$.$$}$ 읽을 수 없는 위치의 값을 0으로 설정하고$$ 신드롬을 계산한다.

우리가 이미 Forney 공식에 대해 정의한 바와 같이, Let $S{\displaystyle }$(${\displaystyle x}$)${\displaystyle }$=${\displaystyle \underset{}{\overset{}{}}}$ i =${\displaystyle \underset{}{\overset{}{0}}}$ d${\displaystyle \underset{}{\overset{}{}}}$- 2 ${\displaystyle {초}_{}}$ ${\displaystyle \underset{}{\overset{}{}}{}_{}}$+ ${\displaystyle i^{}}$ ${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.$$}$

Let us run extended Euclidean algorithm for locating least common divisor of polynomials ${\displaystyle S(x)\Gamma (x)}$ and ${\displaystyle x^{d-1}.}$ The goal is not to find the least common divisor, but a polynomial ${\displaystyle r(x)}$ of degree at most ${\d$$isplaystyle \lfloor (d+k-3)/2\rfloor }$ and polynomials ${\displaystyle a(x),b(x)}$ such that ${\displaystyle r(x)=a(x)S(x)\Gamma (x)+b(x)x^{d-1}.}$ Low degree of ${\displaystyle r(x)}$ guarantees, that ${\displaystyle a(x)}$ would satisfy extended ($EX{\displaystyle \mathrm{}}${\$displaystyle \Gamma }$)에 대한 $조건{\displaystyle \mathrm{}}$ 정의${\displaystyle .}$ ${\displaystyle \Lambda .}$

${\displaystyle \mathrm{four}}$ ( x${\displaystyle )}$ = ${\displaystyle a}$( ${\displaystyle x}$)${\displaystyle \mathrm{\gamma }}$(${\displaystyle x}$ ${\displaystyle )}$\$displaystyle$\Xi$(x$)=a$(x)\Gamma(x)}$를 정의하고$$ Fourney 공식에서$$ $\lambda {\displaystyle \mathrm{}(x}$) ${\displaystyle \Lambda(x)}$ 대신 $\xi {\displaystyle \mathrm{}}$ ${\displaystyty}$을 사용하면 오류 값이 나온다.

알고리즘의 주요 장점은 한편 Forney 공식에 필요한$$ $\Omega {\displaystyle \mathrm{}}$(${\displaystyle x}$)${\displaystyle }$= ${\displaystyle S}$( x${\displaystyle }$) ${\displaystyle \mathrm{\xi }}$(${\displaystyle x}$) ${\displaystyle {mod}^{}}$ x ${\displaystyle d^{}}$- ${\displaystyle 1{}^{}}$= ${\displaystyle r}$( x${\displaystyle }$) ${\displaystyle \Oomega(x)=S(x)\Xi(x){\bmod{d-1}^{$d-1}=$r(x)}$을 계산한다는 것이다.

디코딩 프로세스에 대한 설명

목표는 수신된 단어와 가능한 한 읽기 쉬운 위치에서 다른 코드 워드를 찾는 것이다. 수신된 단어를 가장 가까운 코드 워드와 오류 워드의 합으로 표현할 때, 가독 가능한 위치에서 0이 아닌 최소 개수의 오류 워드를 찾으려고 노력하고 있다. 신드롬 $s{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$ 조건별로 오류 단어 제한$$

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

이 조건들을 따로 쓰거나 다항식을 만들 수도 있다.

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

검정력 $0{\displaystyle \mathrm{}}$ ${\displaystyle 0}$에 가까운 계수를 $d{\displaystyle }$- 2${\displaystyle d-2$와 비교하십시오$.$$}$

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

Suppose there is unreadable letter on position ${\displaystyle k_{1},}$ we could replace set of syndromes ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$ by set of syndromes ${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$ defined by equation ${\displaystyle t_i={\alpha }^{}}$${\displaystyle t_{i}=\cHB ^{k_{1}s_{i}-s_{i+1}.}$$$ 오류 워드에 대해 원본 세트${\displaystyle }${${\displaystyle s_{}}$,${\displaystyle {}_{},}$, s ${\displaystyle c_{}}$+ d${\displaystyle {}_{}}$- ${\displaystyle 2_{}}$ ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}}$에 의한 모든 제한은 다음보다 작다고 가정하십시오.

${\displaystyle 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}.}$

새로운 신드롬 집합이 오류 벡터를 제한함

${\displaystyle f_{j}=e_{j}\왼쪽(\reft ^{k_{1}-\reft ^{j}\right)}$

the same way the original set of syndromes restricted the error vector ${\displaystyle e_{j}.}$ Except the coordinate ${\displaystyle k_{1},}$ where we have ${\displaystyle f_{k_{1}}=0,}$ an ${\displaystyle f_{j}}$ is zero, if ${\displaystyle e_{j}=0.}$ For t그는 오류 위치를 찾는 것을 목표로 우리는 읽을 수 없는 모든 문자를 반영하기 위해 비슷한 방식으로 신드롬 세트를 변경할 수 있다. 이렇게 하면 신드롬 집합이 $k{\displaystyle }$ . {\$displaystyle$ k$.}$ 단축된다.

In polynomial formulation, the replacement of syndromes set ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$ by syndromes set ${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$ leads to

${\displaystyle 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}.}$

그러므로

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

$S{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle S($${\displaystyle x}$$)}$을 S${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle \mathrm{\gamma }}$ ( x${\displaystyle }$)${\displaystyle S(x)\Gamma (x$로 교체한 후에는 power $k{\displaystyle }$ ,${\displaystyle \cdots }$, ${\displaystyle d}$ - 2.$$\$displaysty k,\codots ,d-2$에 가까운 계수에 방정식이 필요하다$.$$}$

판독 불가능한 문자와 유사하게 주어진 위치의 영향력을 제거하는 관점에서 오류 위치를 찾는 것을 고려할 수 있다. $v{\displaystyle }$ ${\displaystyle v}$ 위치를$$ 찾은 경우, 이러한 좌표에만 오류가 있는 오류 벡터가 있는 경우보다 모든 0으로 구성된 신드롬 세트를 획득할 수 있다. $\lambda {\displaystyle \mathrm{}}$( ${\displaystyle x}$) ${\displaystyle \Lambda (x)}$이(가) 이러한 좌표의 영향을 제거하는 다항식을 나타내는$$ 경우, 당사는

${\displaystyle S(x)\감마(x)\램바(x){\stackrel {\{k+v,\cdots,d-2\}{=}}}0.}$

유클리드 알고리즘에서는 오류 카운트가 클수록 수신 단어로부터 같은 거리에 더 많은 코드 워드가 있을 수 있기 때문에 최대 ${\displaystyle \frac{1}{}}$ $2{\displaystyle \frac{\mathrm{}}{}}$(${\displaystyle \mathrm{d}}$- 1${\displaystyle }$- ${\displaystyle k}$) ${\displaystyle {\tfrac${1$}{1$}:{$1}:{$1}($d-1-k)$ 오류$$(읽을 수 있는 위치에서)를 수정하려고 한다. 따라서, 우리가$$ 찾고 $있는{\displaystyle \mathrm{}}$ ${\displaystyle (}$ (${\displaystyle x}$ )$${\$displaystyle \Lambda (x)}$의 경우, 방정식은 다음에서 시작하는 역량에 가까운 계수에 대해 유지되어야 한다.

${\displaystyle k+\좌측\l바닥 {\frac {1}{1}:{2}}(d-1-k)\우측\표시장치 .}$

Forney 공식에서 ${\displaystyle \lambda }$( x${\displaystyle }$) ${\displaystyle \Lambda (x)}$에 동일한 결과를 제공하는 스칼라를 곱할 수 있다$$.

It could happen that the Euclidean algorithm finds ${\displaystyle \Lambda (x)}$ of degree higher than ${\displaystyle {\tfrac {1}{2}}(d-1-k)}$ having number of different roots equal to its degree, where the Fourney formula would be able to correct errors in all its roots, anyway correcting such many errors는 위험할 수 있다(특히 수신된 단어에 대한 다른 제한이 없다). 보통 $\lambda {\displaystyle \mathrm{}}$( ${\displaystyle x}$) ${\displaystyle \Lambda (x)}$을(를) 더 높은 등급으로$$ 받은 후에는 오류를 수정하지 않기로 한다. $\lambda {\displaystyle \mathrm{}}$( ${\displaystyle x}$) ${\displaystyle \Lambda (x)}$이(가) 다중성이 높거나$$ 루트 수가 그 정도보다 작은 경우 보정이 실패할 수 있다. Fail 역시 Forney 수식이 전송된 알파벳 외부의 오류를 반환함으로써 감지될 수 있다.

오류 수정

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

예제 디코딩

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

Consider a BCH code in GF(2⁴) with ${\displaystyle d=7}$ and ${\displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$. (This is used in QR codes.) 전송할 메시지를 [1 1 ${\displaystyle 0}$ 1 1]로 하거나 다항식 표기법으로 $M{\displaystyle (}$ x${\displaystyle }$) =${\displaystyle {}^{}}$ ${\displaystyle {4\mathrm{}}^{}}$+ ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}}$+ ${\displaystyle x}$+ 1${\디스플레이스타일 M(x)=x^{4}+x^{3}+x+1$로 한다$.$$}}$ "체크섬" $기호$는 x ${\displaystyle {}^{}}$M (${\displaystyle x}$ )$${\$displaystyle$ x$^{10(x)}M($$x{\displaystyle )\}}$을 g$$( x ) {\$displaystyle$ g(x$$$)}$로 나누고 나머지를 취함으로써 $계산$되며,${\displaystyle {}^{}{그\mathrm{}}^{}}$ ${\displaystyle {결과\mathrm{}}^{}}$ x 9 + ${\displaystyle {x\mathrm{}}^{}}$ 4${\displaystyle {}^{}}$+$$x 2 {\$displaystyle$ x$^{9}+x^{$4}+x^{4}+x^{4}+x^{4}+$x^{$x^{$2가$ 된다.$}}}$ 또는$$ [ 1 0 0 0 0 1 0 0 ] 이것들은 메시지에 첨부되기 때문에, 전송된 코드 워드는 [1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 ]이다.

이제 전송에 두 개의 비트 오류가 있으므로 수신된 코드 워드는 [1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]이라고 상상해 보십시오. 다항식 표기법:

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

오류를 수정하려면 먼저 신드롬을 계산하십시오. Taking ${\displaystyle \alpha =0010,}$ we have ${\displaystyle s_{1}=R(\alpha ^{1})=1011,}$ ${\displaystyle s_{2}=1001,}$ ${\displaystyle s_{3}=1011,}$ ${\displaystyle s_{4}=1101,}$ ${\displaystyle s_{5$$}}=0001,}$ 및 ${\displaystyle s_{}}$ $6{\displaystyle {}_{}}$= ${\displaystyle 1001.}$${\displaystyle s_{6}=1001.$$}}$ 다음에는$$ 다음의 증강 매트릭스를 줄여서 피터슨 절차를 적용한다.

${\displaystyle \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}}$

0행으로 인해 S는_3×3 단수인데, 단 두 개의 오류만 암호문에 유입되었기 때문에 놀랄 일도 아니다. 그러나 매트릭스의 왼쪽 상단 모서리는 [S_2×2 C_2×1]와 동일하며, 이로 인해 솔루션 ${\displaystyle {\lambda \mathrm{}}_{}}$2 = ${\displaystyle 1000,}$ ${\displaystyle \lambda _{$2}=$1000,}$ ${\displaystyle 1_{}}$ 1 = ${\displaystyle 1011}$이 발생한다${\displaystyle \mathrm{.}}$$\displaystyle \lambda _{1}=1011.$$}$ The resulting error locator polynomial is ${\displaystyle \Lambda (x)=1000x^{2}+1011x+0001,}$ which has zeros at ${\displaystyle 0100=\alpha ^{-13}}$ and ${\displaystyle 0111=\alpha ^{-5}.}$ The exponents of ${\displaystyle \alpha }$ correspo오류 위치에 연결하십시오. 이 예에서는 유일한 값이 1이므로 오류 값을 계산할 필요가 없다.

읽을 수 없는 문자로 디코딩

동일한 시나리오를 가정하지만 수신된 단어에는 읽을 수 없는 두 개의 문자[1 0 0 ? 1 ? 0 0 1 0 0 0 0 0 0 ? 0 0 0 ]가 있다고 가정하십시오. 읽을 수 없는 문자는 0으로 대체하고 위치 $\gamma {\displaystyle \mathrm{}(x}$)${\displaystyle }$=${\displaystyle }$(${\displaystyle {\mathrm{\alpha }}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$- ${\displaystyle 1}$)${\displaystyle }$. ${\$디스플레이 스타일$$\$감마$(x$)=\좌측(\alpha$^{$8}x-1\$우측$)\$좌측(\$alpha ^{11}x-1\우측).$$}$ We compute the syndromes ${\displaystyle s_{1}=\alpha ^{-7},s_{2}=\alpha ^{1},s_{3}=\alpha ^{4},s_{4}=\alpha ^{2},s_{5}=\alpha ^{5},}$ and ${\displaystyle s_{6}=\alpha ^{-7}.}$ (Using log notation which is indeGF(2⁴) 이소모르퍼스(pendent on GF(2) 계산 검사에서 우리는 이전 예제에서 사용된 것과 동일한 표현을 추가에 사용할 수 있다. $\alpha {\displaystyle }$ ${\displaystyle \alpha }$의 힘에 대한 16진수 설명은 비트 xor에 기반한 추가와 함께 연속적으로 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9이다$$.)

신드롬 다항식을 만들자.

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

계산하다

${\displaystyle 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}.}$

확장 유클리드 알고리즘 실행:

${\displaystyle{\begin{정렬}&,{\begin{pmatrix}())\Gamma())\\x^{6}\end{pmatrix}}\\[6pt]={}&,{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{)}x^{2}+\alpha ^{6}x^{3}+\alpha ^{)}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{pmatr.ix}}{\begin{pmatrix}X^{6}\\\alpha ^{-7}+\alpha ^{4}x+\alpha ^{)}x^{2}+\alpha ^{6}x^{3}+\alpha ^{)}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}(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 ^{)}x^{2}+\alpha ^{6}x^{3}+\alpha ^{)}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\alpha ^{-2}x+\alph.한 ^{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^ᆮ\\\left(\alpha ^{7}+\alpha ^{-7}\right)+\left(2\alpha ^{-7}+\alpha ^{4}\right)x+\left(\alpha ^{-5}+\alpha ^{-6}+\alpha ^{-1}\right)x^ᆯ+\left(\alpha ^{-7}+\alpha ^{4}+\alpha ^{6}\right)x^ᆰ+\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}+\alp.^ 떨어지지{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{정렬}}}$

우리는 다항식 학위학위학위학위학위학위학위학위학위학위학위학위

${\displaystyle{\begin{pmatrix}(\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}+\cHB ^{-5}x+\nd{pmatrix}{6}x^{2}&\nd{4}+\nd{pmatrix}={-5}x\end{pmatrix}1&0\0&1\end{pmatrix},},}$

우리는 얻는다.

${\displaystyle{\begin{pmatrix}(\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}())\Gamma())\\x^{6}\end{pmatrix}}^{0}x^{2^{-3}+\alpha ^{-2}x+\alpha ={\begin{pmatrix}\alpha.}+\alpha ^{-2}x^{3}+\nd{-6}x^{4}\\\cHB^{-4}+\cHB^{4}x+\cHB^{2}x^{5}x^{3}\end{pmatrix}}}}}.}$

그러므로

${\displaystyle 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}.}$

Let ${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}.}$ Don't worry that ${\displaystyle \lambda _{0}\neq 1.}$ Find by brute force a root of ${\displaystyle \Lambda .}$ The roots are ${\displaystyle \alpha ^{2},}$ and ${\displaystyle {\alpha }^{}}$${\displaystyle {10}^{}}$ ${\$예: ${\displaystyle {\alpha \mathrm{}}^{}}$ 2 ${\$}}:$$${\$$displaystyle \$$Lambda }$을(를$)$ 해당 모놈(x$\alpha ^{2}\오른쪽)$으로 나눌 수 있으며$$, 결과 모놈의 뿌리를 쉽게 찾을 수 있다.

내버려두다

${\displaystyle {\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}}}$

공식을 사용하여 오류 값을 찾도록 함

${\displaystyle e_{j}=-{\frac {\Oomega \left(\alpha ^{-i_{j}}\오른쪽)}}{\Xi '\왼쪽(\alpha ^{-i_{j}}\오른쪽)}}},}$

여기서 $\alpha {\displaystyle {}^{}}$- i ${\displaystyle {j_{}}^{}}$ ${\$는 ${\displaystyle \xi }$ ( ) .${\displaystyle \Xi (x$)의 루트다$.$$}$ $\xi$${\displaystyle {\mathrm{}}^{}(x}$) =${\displaystyle {}^{}}$ 2 ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$. ${\displaystyle \Xi '(x)=\alpha ^{2}x^{2}.$${\$cHBFFFFF$$}우리는

${\displaystyle{\begin{정렬}e_{1}&, =-{\frac{\Omega)}{\Xi '(\alpha ^{4})}}={\frac{\alpha ^{-4}+\alpha ^{-7}+\alpha ^{-5}+\alpha ^{7}}{\alpha ^{-5}}}={\frac{\alpha ^{-5}}{\alpha ^{-5}}}=1\\e_{2}&, =-{\frac{\Omega)}{\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{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$= e ${\displaystyle {4\mathrm{}}_{}}$= ${\displaystyle 1}$,${\displaystyle e_{3}=e_{4}=1,}$는 놀랄 일이 아니다$$.

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

소수의 오류가 있는 읽을 수 없는 문자로 디코딩

오류 수가 적은 사례에 대한 알고리즘 동작을 보여줍시다. 수신된 단어는 [ 1 0 ? 1 ? 0 0 0 0 0 0 ]으로 한다.

다시, 읽을 수 없는 문자를 0으로 교체하고 위치 $\gamma {\displaystyle \mathrm{}(x}$)${\displaystyle }$=${\displaystyle }$(${\displaystyle {\mathrm{\alpha }}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle \mathrm{x}}$- ${\displaystyle 1}$)${\displaystyle }$.${\displaystyle \Gamma(x)=\left(\alpha ^{8}x-1\right)\left$(\alpha$^{11x-1\$right)\$right.$$}$ Compute the syndromes ${\displaystyle s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1},s_{5}=\alpha ^{0},}$ and ${\displaystyle s_{6}=\alpha ^{2}.}$ Create syndrome polynomial

${\displaystyle {\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{정렬}}}$

확장된 유클리드 알고리즘을 실행합시다.

${\displaystyle{\begin{정렬}())\Gamma())\\x^{6}\end{pmatrix}}&={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{)}x^{5}+\alpha ^{)}x^{6}+\alpha ^{6}x^{7}\\x^{6}\end{pmatrix}}\\&, ={\begin{pmatrix}\alpha ^{)}+\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 ^{)}x^{5}+2\alpha ^{)}x^{6}+2\alpha ^{6}x^{7}\end{pmatrix}}\\&, ={\begin{pmatrix}\alpha ^{)}+\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}}\\&, =ᆫ\left(1+\alpha ^{2}\right)+\left(\alpha ^{0}일 경우+\alpha ^{-6}\right)x+\alpha ^{7}x^{2}&,\alpha ^{)}+\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 ^{)}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}\end.{정렬}}}$

우리는 다항식 학위학위학위학위학위학위학위학위학위학위학위학위

${\displaystyle {\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}},}$

우리는 얻는다.

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

그러므로

${\displaystyle S(x)\Gamma(x)\왼쪽(\alpha ^{3}+\alpha ^{1}x\right)-\왼쪽(\alpha ^{7}+\alpha ^{7}x^{7}}\lapa ^{0x}).$

Let ${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{1}x.}$ Don't worry that ${\displaystyle \lambda _{0}\neq 1.}$ The root of ${\displaystyle \Lambda (x)}$ is ${\displaystyle \alpha ^{3-1}.$$}$

내버려두다

${\displaystyle {\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}}}$

Let us look for error values using formula ${\displaystyle e_{j}=-\Omega \left(\alpha ^{-i_{j}}\right)/\Xi '\left(\alpha ^{-i_{j}}\right),}$ where ${\displaystyle \alpha ^{-i_{j}}}$ are roots of polynomial ${\displaystyle \Xi (x).$$}$

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

우리는 얻는다.

${\displaystyle {\begin}e_{1}=-{\frac {\Oomega \left(\alpha ^{4}\오른쪽)}}{\Xi '\왼쪽(\알파 ^{4}\오른쪽)}}}={\frac{\alpha^{7}+\alpha^{4}{\alpha^{-7}+\alpha^{-2}}}={\fraca ^{3}}}}=1\\e_&={\frac {\Oba \좌측(alpha ^7}\)}{\Xi '\왼쪽(\알파 ^{7}\오른쪽)}}}={\frac {\alpha ^{7}+\alpha ^{7}{\alpha ^{-7}+\alpha ^{4}}=0\\\e_}=-{\frac {\frac \좌(\alpha ^{2}\오른쪽)}{\Xi '\왼쪽(\알파 ^{2}\오른쪽)}}}={\frac {\frac}{7}+\fraged ^{2}}:{\precent ^{-7}+\flaim ^{-6}}}={\frac {\frac ^{-3}}}}}}=1\end{aigned}}}}}}}}}}}}}}$

$e{\displaystyle {}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$= ${\displaystyle 1}$ ${\displaystyle e_{3}=1}$이라는 사실이 놀랍지 않아야$$ 한다.

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

인용구

참조

일차 출처

• Hocquenghem, A. (September 1959), "Codes correcteurs d'erreurs", Chiffres (in French), 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

이차 출처

• Gill, John (n.d.), EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, retrieved April 21, 2010^{[dead link]} 코스 노트는 2012년에 다시 작성될 것으로 보인다: http://www.stanford.edu/class/ee387/ 2013-06-05 Wayback Machine에 보관
• 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 (2nd ed.), 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 (2nd ed.), Cambridge University Press, ISBN 0-521-55374-1
• Gilbert, W. J.; Nicholson, W. K. (2004), Modern Algebra with Applications (2nd ed.), 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, archived from the original on 2010-07-02, retrieved April 21, 2010