Циклические коды

Циклические коды – это разновидность линейных блочных кодов и предназначены они для обнаружения и исправления ошибок.

Любое m разрядное число можно представить в виде многочлена

F(x) = a_m-1x^m-1 + a_m-2x^m-2 + … + a₁x¹ + a₀x⁰.

Здесь коэффициенты a₁, a₂, …, a_m-1 равны "0" или "1".

Для двоичных кодов это будет иметь вид

F(x) = a_m-12^m-1 + a_m-22^m-2 + … + a₁2¹ + a₀2⁰.

Например, кодовую комбинацию 1111 можно записать

F₁ = x³ + x² + x + 1,

а для 1001

F₂ = x³ + 1.

Такое представление двоичных чисел более компактно. Над многочленами можно производить любые алгебраические операции (умножение, деление и т.д.) за исключением сложения и вычитания, которые заменяются на суммирование по модулю два.

F₁(x) Å F₂(t) = x² + x.

В основе построения циклических кодов лежит представление их в виде указанных многочленов. Широкое применение таких кодов обусловлено их способностью обнаруживать и исправлять ошибки различной конфигурации, удобством математического аппарата для их описания и простотой технической реализации кодеров и декодеров.

Построение циклических кодов основано на представлении первичного кода в виде многочлена степени m-1 f(x) и представления в виде многочлена степени r-1 r(x) проверочного кода. Тогда многочлен циклического кода равен

F(x) = f(x)x^r + r(x).

Умножение f(x) на x^r необходимо, чтобы сдвинуть информационные элементы на r разрядов влево и тем самым освободить справа r разрядов для записи r проверочных элементов.

Построенный таким образом многочлен F(x) должен делиться без остатка на образующий многочлен M(x) степени r, т.е.

,

или с учетом правил двоичной алгебры

.

Отсюда видно, что многочлен проверочных элементов r(x) является остатком от деления f(x)x^r на М(х). Так как максимальная степень остатка всегда по крайней мере на единицу меньше степени делителя, становится ясно, почему степень образующего многочлена выбирается равной r.

Пример: пусть задана m=5 пятиэлементная комбинация первичного кода 10000 = f(x) = x⁴. Требуется построить циклический код, имея в виду возможность исправления однократных ошибок (т.е. d₀=3). Этому условию удовлетворяет r=4. Возьмем в качестве образующего многочлена М(х)=х⁴+х+1 и разделим на

Тогда циклический код F(x)=f(x)x^r+r(x)=100000101.

При приеме комбинации циклического кода f(x) ее принадлежность к разрешенной или запрещенной определяется отсутствием или наличием остатка от ее деления на образующий многочлен М(х). Для исправления ошибок нужно, чтобы остатки от деления, т.е. r(x) служили синдромами ошибки. То есть каждому варианту ошибки должен соответствовать свой остаток. Для этого необходимо правильно выбрать образующий многочлен М(х). Обычно в качестве М(х) выбирают неприводимые многочлены, которые могут быть представлены в виде произведения многочленов низших степеней. Пример таких многочленов показан в таблице 1.2.

Таблица 1.2.

r	Неприводимые многочлены
	х + 1
	х^2 + х + 1
	х^3 +х + 1 х^3 +х^2 + 1
	х^4 +х + 1 х^4 +х^3 + 1 х^4 +х^3 + х^2 +х + 1

Однако не всегда неприводимый многочлен сможет служить в качестве образующего многочлена. Это можно продемонстрировать на примере.

Рассмотрим пример построения циклического кода (9,5) для комбинации первичного кода х⁴=10000=f(x). Число проверочных элементов r=4 при d₀=3. Следовательно образующий многочлен М(х) имеет степень r=4. Для r=4 из таблицы имеются три неприводимых многочлена. Построим для каждого из них циклический код.

F(x) = f(x) x^r + r(x) = 100000101 – циклический код.

F(x) = 100001110.

F(x) = 100001000.

Как видно для примера 1 вес кодовой комбинации V₁ = 3 = d₀, для 2 – V₂ = 4 > d₀, а для 3 – V₃ = 2 < d₀. Это значит, что третий неприводимый многочлен М₃(х) не может быть использован в качестве образующего для циклического кода, исправляющего одиночные ошибки (d₀=3).

Дата добавления: 2014-01-11