순환 코드

순환 코드는 정보 k와 제어 기호가 항상 동일하도록 각 조합이 독립적으로(블록의 형태로) 인코딩되는 블록 체계적 코드 중 하나입니다.

특정 장소에서 옷을 입으십시오. 다른 코드에 비해 상대적으로 낮은 중복성으로 거의 모든 오류를 감지하고 수정할 수 있는 능력과 인코딩 및 디코딩 장비의 회로 구현의 단순성으로 인해 이러한 코드가 널리 퍼졌습니다. 순환 코드 이론은 그룹 이론과 갈루아 장(Galois field)에 대한 다항식 대수학을 기반으로 합니다.

순환 코드는 임의의 조합에서 이웃 조합으로 이동할 때마다 해밍 코드 거리가 일정하게 유지되는 방식으로 코드 조합의 분포 순서가 수행되는 코드입니다.

순환 코드는 다양한 오류 방지 코드 중 하나인 해밍 코드를 포함하는 전체 오류 방지 코드 제품군이지만 일반적으로 코드 조합을 전송할 때 발생하는 오류를 감지하고 수정하는 데 필요한 기능을 갖춘 코드를 구현하는 기능 측면에서 더 큰 유연성을 제공합니다. 통신 채널을 통해. 순환 코드(Cyclic Code)는 체계적 블록(n, k) 코드를 말하는데, 처음 k 자리는 기본 코드의 조합을 나타내고 그 다음의 (n ? k) 자리는 체크 번호입니다.

순환 코드의 구성은 전송된 코드 조합을 r차의 생성 기약 다항식으로 나누는 동작을 기반으로 합니다. 나눗셈의 나머지 부분은 체크 숫자를 형성하는 데 사용됩니다. 이 경우, 나눗셈 연산에 앞서 k 비트의 정보 코드 조합을 r 비트만큼 왼쪽으로 이동시키는 곱셈 연산이 수행된다.

더 낮은 차수의 다항식의 곱으로 표현될 수 있는 다항식(다항식)을 환원 가능(주어진 필드에서)이라고 하며 그렇지 않으면 환원 불가능하다고 합니다. 기약다항식은 정수론에서 소수와 비슷한 역할을 합니다. 기약 다항식 P(X)는 십진수 또는 이진수또는 대수 다항식의 형태로 나타납니다.

순환 코딩 프로세스

순환 코딩은 순환 코드와 관련하여 생성기, 생성기 또는 생성 다항식(다항식)이라고 불리는 환원 불가능한 다항식 P(X)의 사용을 기반으로 합니다.

모든 조합에 대한 이진코드의 조합을 순환코드 구성을 위한 정보기호 k로 취한다. 일반적인 경우, 주어진 코드 조합 Q(x)에 생성 다항식 P(x)를 곱하면 그 결과는 P(x)의 선택에 따라 특정 수정 속성을 갖는 순환 코드가 됩니다. 그러나 이 코드에서는 제어 기호 m이 코드 조합의 다양한 위치에 위치하게 됩니다. 이러한 코드는 체계적이지 않아 회로 구현이 어렵습니다. 제어 기호를 끝, 즉 정보 기호 뒤에 추가하면 상황이 상당히 단순화될 수 있습니다. 이를 위해서는 다음 방법을 사용하는 것이 좋습니다.

우리는 생성 다항식 P(x)와 동일한 차수를 갖는 단항식 Xm으로 인코딩되어야 하는 코드 조합 G(x)를 곱합니다.

우리는 곱 G(x)Х m을 생성 다항식 Р(х m)으로 나눕니다.

여기서 Q(x)는 나눗셈의 몫입니다. R(x) - 나머지.

식 (2.1)에 P(x)를 곱하고 R(x)를 부호를 반전시키지 않고 등식의 다른 부분으로 옮기면 다음을 얻습니다.

따라서 등식(2.2)에 따르면 순환 코드, 즉 인코딩된 메시지 F(x)는 두 가지 방식으로 형성될 수 있습니다.

생성 다항식 P(x)에 의한 모든 조합에 의한 이진 코드의 하나의 코드 조합의 곱셈;

주어진 코드 조합 G(x)에 생성 다항식 P(x)와 동일한 차수를 갖는 단일 다항식 X m을 곱하고, 곱 G(x)X m을 생성 다항식으로 나눈 나머지 R(x)를 더합니다. 다항식 P( X).

메시지 인코딩

P(x)=x 3 +x+1을 사용하여 G(x)=x 3 +x 2 에 해당하는 코드 조합 1100을 인코딩해야 합니다.

G(x)에 Xm을 곱하면 다음과 같은 결과를 얻습니다.

(2.1)에 따라 곱 G(x)Х m을 생성 다항식 Р(х m)으로 나누면 다음을 얻습니다.

또는 이에 상응하는 이진수로:

따라서 결과적으로 G(x)와 동일한 차수의 몫 Q(x)를 얻습니다.

Q(x)=x3 +x2 +x>1110

그리고 나머지:

결과적으로 (2.2)에 따라 순환 코드로 인코딩된 이진 코드 조합은 다음과 같은 형식을 취합니다.

F(x)=1110 1011=1100010

각각의 허용된 순환 코드 조합은 생성 다항식 G(x)의 가능한 모든 합을 나타내기 때문에 나머지 없이 P(x)로 나누어져야 합니다. 따라서 허용된 코드 조합의 정확성을 확인하는 것은 이를 생성 다항식으로 나눌 때 나머지를 식별하는 것으로 귀결됩니다.

잔액을 받았다는 것은 오류가 있음을 나타냅니다. 순환 코드의 나머지 분할은 신드롬의 역할을 합니다.

예를 들어, 전송된 코드 조합 F(x)=1100010은 생성 다항식 P(x)=1011을 사용하여 구성됩니다. 간섭의 영향으로 코드 조합이 F"(x)=1000010 조합으로 변환되었습니다.

허용된 조합을 생성 다항식으로 나눕니다.

나머지 R(x)=001이 있으면 오류가 있음을 나타냅니다. 그러나 조합에서 오류 위치를 직접적으로 나타내지는 않습니다. 오류를 확인하기 위해 증후군 분석을 기반으로 하는 여러 가지 방법이 있습니다.

오류의 위치를 알아내려면 임의의 개수의 0을 P(x) = 1011로 나눕니다.

요소 번호에서 오류가 발생했습니다:

잔기수 -2>4-2=2

즉, 오류는 두 번째 요소에 있습니다.

순환 코드는 이를 형성하는 코드 벡터의 순환 시프트 연산에 따라 닫히는 유한 집합인 선형 코드입니다. 주어지게 하라 N-차원 벡터 V = ㅏ 0 ㅏ 1 …앤-1은 최종 필드의 좌표입니다. 에프. 순환 이동을 벡터라고 합니다. V"=a N-1 0 1 … 앤 -2 .

고려해 봅시다 N-갈루아장 위의 차원 산술 공간 GF(2). 각 벡터 ㅏ 0 ㅏ 1 …앤-1개 GF(2) 다항식을 일대일로 비교할 수 있습니다. ㅏ 0 +ㅏ 1 엑스+…+앤 -1 xn-1의 확률 GF(2). 두 벡터의 합 ㅏ 0 ㅏ 1 …앤-1 및 비 0 비 1 …비엔-1은 이에 해당하는 다항식의 합, 벡터에 의한 필드 요소의 곱-이 벡터에 해당하는 다항식의 요소에 대한 곱에 해당합니다.

다항식을 생각해 봅시다 g(엑스) 설명된 선형 공간에서. 나머지 없이 나누어질 수 있는 이 부분 공간의 모든 다항식 집합은 다음과 같습니다. g(엑스)는 선형 부분공간을 형성합니다. 선형 부분공간은 일부 선형 코드를 정의합니다.

다항식 클래스로 구성된 선형 코드 씨(g(엑스)), 일부 다항식의 배수 g(엑스)을 생성 다항식이라고 하며 다항식이라고 합니다.

다항식 코드가 어떻게 관련되어 있는지 보여 드리겠습니다. 씨(g(엑스)) 및 순환 코드. 허락하다 ㅏ = ㅏ 0 …n-1은 일부 코드 단어이고 해당 코드 다항식입니다. ㅏ(엑스) = ㅏ 0 +...+앤 -1 xn-1 . 순환교대 ㅏ"는 코드 다항식에 해당합니다. ㅏ"(엑스) = 앤 -1 +ㅏ 0 엑스+…+앤 -2 엑스 n -1 , 이는 원본의 관점에서 표현될 수 있습니다:

다항식 코드는 다음으로 나누어져야 하기 때문에 g(엑스), 순환이 되도록 다항식은 다음과 같습니다. ㅏ"(엑스)는 다음으로 나누어야 합니다. g(엑스). 이러한 고려로부터 우리는 다음 정리를 공식화할 수 있습니다. 다항식 코드는 다음과 같은 경우에만 순환적입니다. g(엑스)는 다항식의 제수입니다. xn-1. 이 경우 다항식 g(엑스)를 순환 코드의 생성 다항식이라고 합니다.

코딩 이론에서는 다음 정리가 입증됩니다. g(엑스) 학위가 있다 N–케이그리고 제수이다 xn–1, 그러면 씨(g(엑스))는 선형 순환( N, 케이)-암호.

다항식 xn–1 인수분해 xn–1 = (엑스–1)(xn -1 +xn-1 +…+1). 그러므로 어떤 경우에도 순환 코드가 존재합니다. N. 순환 수 N-비트 코드는 다항식의 제수 수와 같습니다. xn-1. 순환 코드를 구성하기 위해 다항식 확장 테이블이 개발되었습니다. xn-1은 환원 불가능한 다항식으로, 즉 단위와 자기 자신에 의해서만 나누어질 수 있는 다항식으로 변환됩니다.

예를 들어 다항식을 기반으로 어떤 코드를 만들 수 있는지 생각해 봅시다. 엑스필드 위 7 –1 GF(2). 다항식을 환원 불가능한 요소로 확장하는 형식은 다음과 같습니다.

다항식의 약수 6개를 만드는 것이 가능하기 때문에 엑스그림 7-1, 기약약수를 결합하면 6개의 이진 순환 코드가 있습니다. ( N, 케이)-코드는 먼저 값에 의해 결정됩니다. N, 둘째, 값 케이 = N – 에스, 에스– 제수 다항식의 정도 xn–1은 코드를 정의합니다. 다음은 다항식 제수와 해당 값입니다. 케이:

엑스 – 1, 에스=1, 케이=6;

엑스 3 +x 2 +1, 에스=3, 케이=4;

엑스 3 +x+1, 에스=3, 케이=4;

(엑스–1)(엑스 3 +x 2 +1)=엑스 4 +x 2 +x+1, 에스=4, 케이=3;

(엑스–1)(엑스 3 +x+1)=엑스 4 +x 3 +x 2 +1, 에스=4, 케이=3;

(엑스 3 +x 2 +1)(엑스 3 +x+1)=엑스 6 +엑스 5 +엑스 4 +엑스 3 +엑스 2 +엑스, 에스=6, 케이=1.

(7, 6) 코드에는 체크 기호가 하나만 있고, (7, 1) 코드에는 정보 기호가 하나만 있습니다. 이들은 각각 패리티 검사 코드와 반복 코드입니다.

일반 선형 코드와 마찬가지로 순환 코드도 생성기 행렬로 지정할 수 있습니다. 따라서 임무는 그러한 행렬을 찾는 것, 즉 다음을 찾는 것입니다. 케이이를 형성하는 선형적으로 독립적인 코드 조합입니다. 이를 위해 순환천이 연산에 대해 순환코드가 닫혀 있는 성질을 이용한다. 오른쪽으로 한 자리씩 순환 이동하는 것은 다음 다항식을 곱하는 것과 같습니다. g(엑스) 에 엑스. 그런 다음 생성 다항식을 취하여 생성 행렬을 구성할 수 있습니다. 케이주기적 변화:

이제 생성 다항식을 사용하는 방법을 고려해 보겠습니다. g(엑스) = 1+엑스+엑스 3 인코딩은 (7, 4) 코드로 수행됩니다. 예를 들어 다항식에 해당하는 4비트 워드(0101)를 생각해 보십시오. 에프(엑스) = 엑스 + 엑스삼. 이 두 다항식을 곱합니다.

이 단어에 해당하는 형식 변수에서 엑스. 이 대응은 단지 일대일 대응이 아니라 동형 대응임을 알 수 있습니다. "단어"는 필드의 문자로 구성되므로 요소별로 더하고 곱할 수 있으며 결과는 동일한 필드에 표시됩니다. 한 쌍의 단어의 선형 조합에 해당하는 다항식은 이러한 단어의 다항식의 선형 조합과 같습니다.

이를 통해 유한 필드에서 길이가 n인 단어 집합을 필드에서 최대 n-1 차수를 갖는 다항식의 선형 공간으로 간주할 수 있습니다.

대수적 설명

워드에서 오른쪽으로 한 비트씩 주기적으로 이동하여 얻은 코드워드인 경우 해당 다항식은 다음과 같습니다. 씨 1 (엑스)는 x를 곱하여 이전 것에서 얻습니다.

이라는 점을 이용하여

오른쪽과 왼쪽으로 각각 이동합니다. 제이순위:

만약에 중(엑스) - 필드에 대한 임의의 다항식 G에프(큐) 그리고 씨(엑스) - 순환 코드워드( N,케이) 코드를 입력한 다음 중(엑스)씨(엑스)중영형디(엑스 N − 1) 또한 이 코드에 대한 코드 워드입니다.

다항식 생성

정의순환의 다항식 생성( N,케이) 코드 씨이러한 0이 아닌 다항식을 호출합니다. ~에서 씨, 그 차수가 가장 작고 가장 높은 차수의 계수 g 아르 자형 = 1 .

정리 1

만약에 씨- 순환 ( N,케이) 코드 및 g(엑스)는 생성 다항식이고 차수는 다음과 같습니다. g(엑스) 동일하다 아르 자형 = N − 케이 각 코드 단어는 다음 형식으로 고유하게 표현될 수 있습니다.

씨(엑스) = 중(엑스)g(엑스) ,

학위는 어디에 있습니까? 중(엑스) 이하 케이 − 1 .

정리 2

g(엑스) - 순환 다항식 생성( N,케이) 코드는 이항식의 제수입니다. 엑스 N − 1

결과:따라서 모든 다항식, 제수를 생성 다항식으로 선택할 수 있습니다. 엑스 N- 1 . 선택한 다항식의 차수에 따라 테스트 기호의 수가 결정됩니다. 아르 자형, 정보 기호 수 케이 = N − 아르 자형 .

생성기 매트릭스

다항식은 선형독립입니다. 그렇지 않으면 중(엑스)g(엑스) = 0 0이 아닌 경우 중(엑스) 불가능합니다.

이는 선형 코드와 마찬가지로 코드 단어를 다음과 같이 작성할 수 있음을 의미합니다.

, 어디 G~이다 행렬 생성, 중(엑스) - 정보 제공다항식.

행렬 G기호 형식으로 작성할 수 있습니다.

체크 매트릭스

순환 코드의 각 코드워드에 대해 . 그렇기 때문에 체크 매트릭스다음과 같이 쓸 수 있습니다:

코딩

비체계적

비체계적 코딩의 경우, 코드워드는 생성 다항식에 의한 정보 다항식의 곱 형태로 획득됩니다.

씨(엑스) = 중(엑스)g(엑스) .

다항식 승수를 사용하여 구현할 수 있습니다.

체계적인

체계적 코딩을 사용하면 코드워드가 정보 서브블록의 형태로 형성되고 검증이 수행됩니다.

정보 단어가 코드 단어의 더 높은 힘을 형성하게 하십시오.

씨(엑스) = 엑스 아르 자형 중(엑스) + 에스(엑스),아르 자형 = N − 케이

그러면 다음과 같은 조건에서

이 방정식은 체계적인 코딩에 대한 규칙을 설정합니다. 다중 주기 선형 필터(MLF)를 사용하여 구현할 수 있습니다.

예

바이너리(7,4,3) 코드

분배기로 엑스 7 − 1 우리는 3차 생성 다항식을 선택합니다. g(엑스) = 엑스 3 + 엑스 + 1 , 결과 코드의 길이는 다음과 같습니다. N= 7, 테스트 기호 수(다항식 생성 정도) 아르 자형= 3, 정보 기호의 수 케이= 4, 최소 거리 디 = 3 .

생성기 매트릭스암호:

여기서 첫 번째 줄은 다항식 표기법입니다. g(엑스) 계수는 증가하는 순서로 나타납니다. 나머지 라인은 첫 번째 라인의 순환 이동입니다.

매트릭스를 확인하세요:

여기서 0부터 시작하는 i번째 열은 나눗셈의 나머지 부분을 나타냅니다. 엑스 나다항식으로 g(엑스) 위에서부터 오름차순으로 작성됩니다.

예를 들어 세 번째 열을 얻거나 벡터 표기법으로 얻습니다.

그 사실을 확인하는 것은 쉽습니다. G시간 티 = 0 .

바이너리(15,7,5) BCH 코드

생성 다항식으로서 g(엑스) 두 약수의 곱을 선택할 수 있습니다 엑스 15 − 1 ^

g(엑스) = g 1 (엑스)g 2 (엑스) = (엑스 4 + 엑스 + 1)(엑스 4 + 엑스 3 + 엑스 2 + 엑스 + 1) = 엑스 8 + 엑스 7 + 엑스 6 + 엑스 4 + 1 .

그런 다음 정보 다항식의 곱을 사용하여 각 코드 단어를 얻을 수 있습니다. 중(엑스) 학위 있음 케이− 1 따라서:

씨(엑스) = 중(엑스)g(엑스) .

예를 들어, 정보 단어는 다항식에 해당합니다. 중(엑스) = 엑스 6 + 엑스 5 + 엑스 4 + 1 , 그 다음에는 코드 워드 씨(엑스) = (엑스 6 + 엑스 5 + 엑스 4 + 1)(엑스 8 + 엑스 7 + 엑스 6 + 엑스 4 + 1) = 엑스 14 + 엑스 12 + 엑스 9 + 엑스 7 + 엑스 5 + 1 또는 벡터 형식

또한보십시오

연결

위키미디어 재단. 2010.

음악의 순환 형식
순환 경계 조건

다른 사전에 "순환 코드"가 무엇인지 확인하십시오.

단축된 순환 코드- - [L.G.수멘코. 정보 기술에 관한 영어-러시아어 사전. M.: 국영 기업 TsNIIS, 2003.] 주제 정보 기술일반적으로 EN 단축 순환 코드...

리드 솔로몬 코드- 데이터 블록의 오류를 수정할 수 있는 비이진 순환 코드입니다. 코드 벡터의 요소는 비트가 아니라 비트 그룹(블록)입니다. 바이트(옥텟)로 작동하는 리드 솔로몬 코드는 매우 일반적입니다. 리드 솔로몬의 코드는... Wikipedia

골레이 코드- 오류 수정 기능을 갖춘 완벽한 선형 블록 코드 제품군입니다. 가장 유용한 것은 Golay 바이너리 코드입니다. 삼항 Golay 코드도 알려져 있습니다. Golay 코드는 순환 코드로 간주될 수 있습니다. … … 기술 번역가 가이드

오류 수정 코드

오류 수정 코드- 통신 기술의 오류 탐지, 정보를 기록/재생할 때 또는 통신 회선을 통해 전송할 때 데이터의 무결성을 모니터링하기 위한 조치입니다. 이후 정보 복원을 위한 오류 정정(오류 정정) 절차... ... 위키피디아

벨로루시 주립 정보 과학 및 무선 전자 대학

RES학과

주제에 대한 초록:

"순환 코드. BCH 코드"

민스크, 2009

순환 코드

순환 코드(Cyclic Code)는 선형 블록(n,k) 코드로, 순환 특성을 특징으로 합니다. 허용된 코드워드를 한 단계만큼 왼쪽으로 시프트하면 동일한 코드에 속하고 코드워드 세트가 일부 다항식 g( x) r = n-k 차수, 이는 이항식 x n +1의 인수입니다.

다항식 g(x)를 생성이라고 합니다.

정의에 따르면 다음과 같이 순환코드에서 코드워드는 다항식으로 표현된다.

여기서 n은 코드 길이입니다. - GF(q) 필드의 계수.

코드가 GF(2) 필드 위에 구축되면 계수는 0 또는 1 값을 취하고 코드를 바이너리라고 합니다.
예.순환 코드의 코드워드인 경우

그러면 해당 다항식

예를 들어 코드가 기약 다항식 f(z)=z 3 +z+1인 GF(2) 모듈로의 확장인 GF(q)=GF(2 3) 필드 위에 구축된 경우 요소는 다음과 같습니다. 이 필드의 형식은 표 1에 제시된 형식을 갖습니다.

그런 다음 계수

이 필드의 요소 값을 취하므로 그 자체는 다음 형식의 다항식 형식으로 표시됩니다.
여기서 m은 필드 확장 GF(2)가 얻어지는 다항식의 차수입니다. a i - GF(2)의 요소 값을 취하는 계수, 즉 0과 1. 이러한 코드를 q-th라고 합니다.

순환 코드의 길이를 프리미티브(Primitive)라고 하며 코드 자체의 길이가 GF(q)에서 n=q m -1이면 프리미티브(Primitive)라고 합니다.

코드의 길이가 기본 코드의 길이보다 작으면 해당 코드를 단축 코드 또는 비원시 코드라고 합니다.

정의에서 다음과 같이 순환 코드의 코드워드의 일반적인 특성은 생성기라고 불리는 일부 다항식 g(x)에 의해 나머지 없이 나누어지는 것입니다.

이항식 xn +1을 다항식 g(x)로 나눈 결과는 테스트 다항식 h(x)입니다.

순환 코드를 디코딩할 때 오류 다항식 e(x)와 신드롬 다항식 S(x)가 사용됩니다.

(n-1) 이하의 오차 다항식은 다음 식으로 결정됩니다.

여기서 는 수신된(오류가 있는) 코드워드와 전송된 코드워드를 각각 나타내는 다항식입니다.

e(x)의 0이 아닌 계수는 오류에 해당하는 위치를 차지합니다.

예.

순환 코드를 디코딩할 때 사용되는 신드롬 다항식은 수신된 코드워드를 생성 다항식으로 나눈 나머지로 정의됩니다.

또는

결과적으로 신드롬 다항식은 오류 다항식 e(x)에 직접적으로 의존하며, 이 조항은 디코딩 프로세스에 사용되는 신드롬 테이블을 구성하는 데 사용됩니다. 이 표에는 오류 다항식 목록과 표현식에서 결정된 해당 신드롬 목록이 포함되어 있습니다.

(표 2 참조)

디코딩 과정에서 신드롬은 수신된 코드워드로부터 계산되고, 해당 다항식 e(x)가 테이블에서 발견되며, 수신된 코드워드와의 합은 수정된 코드워드를 제공합니다.

나열된 다항식은 알려진 대수학 규칙을 사용하여 덧셈, 곱셈 및 나눗셈을 할 수 있지만 결과는 mod 2로 주어지고 결과의 차수가 차수(n-1)를 초과하면 mod x n +1이 됩니다.

코드 길이가 n=7이라고 가정하고 결과 mod x 7 +1을 제시합니다.

다항식을 나눈 결과로 순환 코드를 구성하고 디코딩할 때 일반적으로 나눗셈의 몫이 아니라 나머지가 필요합니다.
따라서 다항식이 아닌 계수만 사용하는 더 간단한 분할 방법이 권장됩니다(예제에서는 옵션 2).

예.

매트릭스 코드 할당

순환 코드는 생성기와 검사 행렬에 의해 지정될 수 있습니다. 이를 구성하려면 g(x)를 생성하고 다항식 h(x)를 테스트하는 것만으로도 충분합니다. 비체계적 순환 코드의 경우 행렬은 생성 및 검사 다항식을 순환적으로 이동하여 구성됩니다. x를 곱해서

그리고

행렬 H(n,k)를 구성할 때 다항식 h(x)의 선행 계수는 오른쪽에 위치합니다.

예.생성 다항식 g(x)=x 3 +x+1을 갖는 순환(7.4) 코드의 경우 행렬 G(n,k) 및 H(n,k)는 다음 형식을 갖습니다.

어디

체계적인 순환 코드의 경우 행렬 G(n,k)는 다음 식으로 결정됩니다.

여기서 I k는 단위 행렬입니다. R k,r은 직사각형 행렬입니다. 행렬 R k,r의 행은 다음 식으로 결정됩니다. 여기서 a i (x)는 행렬 I k의 i 번째 행 값입니다. i는 행렬 R k,r의 행 번호입니다.

예.생성 다항식 g(x)=x 3 +x+1에 기초한 (7.4) 코드에 대한 행렬 G(n,k)는 다음 순서로 구성됩니다.

또는

R 4.3은 다음을 사용하여 결정됩니다.

왜냐하면

비슷한 방식으로 결정