다항식 코드

코딩 이론에서, 다항식 코드는 유효한 코드 워드의 집합이 주어진 고정 다항식(길이 단축, 발전기 다항식이라고 함)으로 분할할 수 있는 다항식(일반적으로 일부 고정 길이의)으로 구성되는 선형 코드의 한 유형이다.

정의

유한 필드 $G{\displaystyle }$ ${\displaystyle F}$ (${\displaystyle q}$ ) ${\displaystyle GF(q)}$을(를) 수정하십시오$.$ 이 요소를 기호라고 부릅니다. 다항식 코드를 구성하기 위해, 우리는 다항식을 $사용$하여 n$${\$displaystyle$$n$$}$ $기호$ a - ${\displaystyle {}_{}}$을 $식별한다.$

${\displaystyle a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}\,}$

정수 $m{\displaystyle }$ ${\displaystyle \le n}$ ${\displaystyle m\leq n}$을(를) 수정하고$$ $g{\displaystyle (x}$) ${\displaystyle g(x)}$을(를) 도 $m{\displaystyle }$ ${\displaystyle m}$의 고정 다항식으로 두십시오$$$($생성 다항식이라고 함). $g{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle g(x)}$이(가) 생성한 다항식 코드는 코드 워드가 ${\displaystyle \mathrm{정확}}$하게${\displaystyle }$g${\displaystyle }$( x$$) {\$displaystyle g(x)}$이(가) g로 구분할 수 있는$$ $n{\displaystyle }$ ${\displaystyle n}$보다 작은 다항식인 코드 입니다$.$

예

Consider the polynomial code over ${\displaystyle GF(2)=\{0,1\}}$ with ${\displaystyle n=5}$, ${\displaystyle m=2}$, and generator polynomial ${\displaystyle g(x)=x^{2}+x+1}$. 이 코드는 다음과 같은 코드 워드로 구성된다.

${\displaystyle 0\cdot g(x),\properties 1\cdot g(x),\properties x\cdot g(x),\put (x+1)\cdot g(x),}$

${\displaystyle x^{2}\cdot g(x),\cdot g(x^{2}+1)\cdot g(x),\cdot g(x^{2}+x),\cdot g(x)\cdot g(x).}$

또는 명시적으로 다음과 같이 쓰십시오.

${\displaystyle 0,\displaystyle x^{2}+x+1,\display x^{3}+x^{2}+2x^{2},}$

${\displaystyle x^{4}+x^{3}+x^{3},\cHB x^{3}+2x^{2}+x^{2}+2x^{4}+2x^{3}+2x}+2x,\cHB x^{4}+2x^{3}+2x^{3}+2}+2x+2x+1}+1}+2x+1}+2x+1}+1}+1}+1}+1}+1}+1}+1}+1}+1}}$

다항식 코드는 바이너리 갈루아 필드 $G{\displaystyle }$ ${\displaystyle F(2}$)${\displaystyle }$=${\displaystyle }${ 0${\displaystyle ,}$ ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle GF(2)=\{0,1\}$에 걸쳐 정의되므로 다항식 요소는 모듈로-2 합으로 표현되며 최종 다항식은 다음과 같다$.$

${\displaystyle 0,\displaystyle x^{2}+x+1,\display x^{3}+x^{2}+x,\display x^{3}+1,}$

${\displaystyle x^{4}+x^{3}+x^{2},\message x^{4}+x^{3}+1,\message x^{4}+x,\message x^{4}+x^{2}+1+1}}$

2진수 문자열로 표현되는 동등하게 코드 워드는 다음과 같다.

${\displaystyle 00000,\display 00111,\display 01110,\display 01001,}$

$11100, 11011, 10010, 10101}$

이것은, 모든 다항식 코드처럼, 실제로 선형 코드, 즉, 코드 워드의 선형 조합은 다시 코드 워드다. 필드가 GF(2)인 이와 같은 경우, 이진 형태로 표현된 암호어의 XOR(예: 00111 XOR 10010 = 10101)를 취함으로써 선형 결합을 발견한다.

인코딩

$코드{\displaystyle }$ 길이 $n{\displaystyle }$ ${\displaystyle n}$ 및$$ 제너레이터 다항식 $g{\displaystyle (x)}$ ${\$$displaystyle g(x)}$ 도 m {\$displaystyle m}$을$($를) 초과하는 다항식 코드에는 정확히 ${\displaystyle {qn}^{}}$ ${\displaystyle -}$$$m {\$displaystystyle q^{n-m$} 코드 워드가 있을 것이다$.$ Indeed, by definition, ${\displaystyle p(x)}$ is a code word if and only if it is of the form ${\displaystyle p(x)=g(x)\cdot q(x)}$, where ${\displaystyle q(x)}$ (the quotient) is of degree less than ${\displaystyle n-m}$. Since there are ${\displaystyle q^{$$n-m}}$의 해당 인용문, 가능한 코드 워드의 개수는 동일하다. 따라서 일반(인코딩되지 않은) 데이터 워드의 길이는 ${\displaystyle n}$ -${\displaystyle }$m ${\displaystyle n-m}$이어야 한다.

(Lidl & Pilz, 1999)와 같은 일부 저자는 데이터 워드에서 코드 워드로의 할당으로$$ 맵핑 ${\displaystyle q}$(${\displaystyle x}$ ${\displaystyle )}$ ${\displaystyle \mapsto }$ g${\displaystyle }$(${\displaystyle x}$) ${\displaystyle \cdot }$ q ($x$) ${\$ 스타일$q(x)\mapsto g(x)\cdot q(x)}$에 대해서만 논한다. 단, 이것은 데이터 워드가 코드 워드의 일부로 나타나지 않는다는 단점을 가지고 있다.

대신 체계적 코드를 생성하기 위해 종종 다음과 같은 방법을 사용한다: $길이{\displaystyle }$ ${\displaystyle n}$-$$m {\$displaystyle n-m$}의$$ d${\displaystyle (}$ $){\$$displaystyle d(x$$)\}$를 $d{\displaystyle {}^{}}$${\displaystyle (}$ ${\displaystyle x}$ ) ${\$ x$^{m$에 먼저 $곱하면{\displaystyle }$ $d{\displaystyle }$${\displaystyle (}$ x${\displaystyle }$) ${\$$displaystystystyled(x)}$의 효과가 있다.왼쪽의 표시 $스타일 m}$자리$$. 일반적으로 $x{\displaystyle {}^{}}$ m ${\displaystyle {}^{}}$( ${\displaystyle x}$) ${\displaystyle$ x$^{m}d(x)}$은(는) $g{\displaystyle }$( x${\displaystyle }$) ${\displaystyle g(x)},$즉 유효한 코드 워드로 구분되지 않는다$$. 그러나 $x{\displaystyle {}^{}}$ ${\displaystyle m^{}}$ ${\displaystyle {}^{}(x}$) ${\displaystyle$ x$^{m(x)}}$의 가장 오른쪽 $m{\displaystyle }$ ${\displaystyle$ $m$$}$ 기호를$$ 조정하여 얻을 수 있는 고유한 코드 워드가 있다$.$ 이를 $계산$하려면 x ${\displaystyle {}^{}}$ d${\displaystyle (x)}${\$displaystyle$ $x$$^{m}d(x)$를 $(x)$: ${\d$)로$$ 나눈 나머지를 계산한다.

${\displaystyle x^{m^(x)d=g(x)\cdot q(x)+r(x)\,}$

${\displaystyle \mathrm{여기}}$서 $r{\displaystyle }$( x${\displaystyle }$) ${\displaystyle r(x)}$은(는) $m{\displaystyle }$ ${\displaystyle m}$보다 낮은 수준이다$.$ 그런 다음 $데이터{\displaystyle \mathrm{워드}}$ d${\displaystyle (}$ x$$) {\$displaystyle d($x)}에 해당하는 코드 워드를 다음과 같이 정의한다$$.

${\displaystyle p(x):=x^{m}d(x)-r(x),\,}$

다음 속성을 참고하십시오.

1. ${\displaystyle }$$p{\displaystyle }$${\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$= g${\displaystyle }$( x${\displaystyle }$) ${\displaystyle \cdot }$ ${\displaystyle q}$ (${\displaystyle x}$)$\$ q (x ) {\$displaystyle p($x)=g$(x)\$cdot$$${\displaystyle q}$$($$x$)}로 나눌 수 있는 p (${\displaystyle }$${\displaystyle x}$ )${\displaystyle }$${\displaystystyle g$$(x$ 특히 p${\displaystyle }$($)$는 유효한$$ 코드 단어다.
2. Since ${\displaystyle r(x)}$ is of degree less than ${\displaystyle m}$, the leftmost ${\displaystyle n-m}$ symbols of ${\displaystyle p(x)}$ agree with the corresponding symbols of ${\displaystyle x^{m}d(x)}$. In other words, the first ${\displaystyle n-m}$ symbols 코드 워드는 원래 데이터 워드와 동일하다. 나머지 $m{\displaystyle }$ ${\displaystyle m}$ 기호를$$ 체크섬 자릿수 또는 체크 비트라고 한다.

예

$n{\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle n=5$ $m{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle m=2$ 생성기 $다항식{\displaystyle }$ g${\displaystyle ({}^{}}$) = 2 +${\displaystyle {}^{}\mathrm{x}}$+ 1 ${\displaystyle g(x)={2}+x+1}$을 가진 위의 코드에 대해 데이터 워드에서 코드 워드로 다음과 같은 할당이 할당된다$.$

• 000 ↦ 00000
• 001 ↦ 00111
• 010 ↦ 01001
• 011 ↦ 01110
• 100 ↦ 10010
• 101 ↦ 10101
• 110 ↦ 11011
• 111 ↦ 11100

디코딩

잘못된 메시지는 발전기 다항식 분리에 의한 다항식 분리를 통해 직설적으로 감지되어 0이 아닌 나머지가 발생할 수 있다.

$코드{\displaystyle }$ 워드에 오류가 없다고 가정할 경우 m$${\$displaystyle$m} 체크섬$$ 자릿수를 제거하기만 하면 체계적 코드를 디코딩할 수 있다.

오류가 있는 경우 디코딩하기 전에 오류 수정을 수행해야 한다. BCH 코드와 같은 특정 다항식 코드에 대한 효율적인 디코딩 알고리즘이 존재한다.

다항식 코드의 속성

모든 디지털 코드의 경우, 다항 코드의 오류 감지 및 수정 능력은 코드의 최소 해밍 거리에 의해 결정된다. 다항식 코드는 선형 코드이므로 최소 해밍 거리는 0이 아닌 코드 워드의 최소 중량과 동일하다. 위의 예에서 해밍 거리는 최소 2로, 01001은 암호어이고, 1비트만 설정된 비제로 코드어는 없기 때문이다.

다항 코드의 보다 구체적인 특성은 종종 발전기 다항식의 특정한 대수적 특성에 의존한다. 이러한 속성의 몇 가지 예는 다음과 같다.

• 다항식 코드는 발전기 다항식이 $x{\displaystyle {}^{}}$ n${\displaystyle {}^{}}$- $1$을 분할하는 $경우에만 순환$된다$.$
• 제너레이터 다항식이 원시인 경우 $n{\displaystyle }$ ${\displaystyle \le }$ ${\displaystyle \mathrm{2m}{}^{}}$- 1 ${\displaystyle n\leq 2^{m}-1$인 경우 결과 코드의 해밍 거리는 최소 3이다$.$
• BCH 코드에서 발전기 다항식은 높은 해밍 거리를 달성하는 방식으로 확장 필드에 특정 루트를 갖도록 선택된다.

영리하게 선택된 발전기 다항식 코드의 대수적 특성 또한 효율적인 오류 수정 알고리즘을 찾는 데 악용될 수 있다. BCH 코드의 경우는 이렇다.

다항식 코드의 특정 패밀리

• 순환 코드 – 모든 순환 코드 역시 다항식 코드다. 대표적인 예는 CRC 코드다.
• BCH 코드 – 해밍 거리가 높고 효율적인 대수 오류 보정 알고리즘을 가진 순환 코드 제품군.
• Reed-Solomon 코드 – 특히 효율적인 구조를 가진 BCH 코드의 중요한 하위 집합.

참조

• W.J. 길버트와 W.K. 니콜슨: 응용을 사용한 현대 대수학, 2004년 2판 Wiley.
• R. Lidl과 G. Pilz. 응용 추상 대수학, 제2판. 1999년 와일리