Общие сведения о циклических кодах

↑

Стр 1 из 4Следующая ⇒

         1 ОБЩИЕ СВЕДЕНИЯ О ЦИКЛИЧЕСКИХ КОДАХ

         1.1 Определение циклических кодов

Важнейшим недостатком СЛБК (систематических линейных блоковых кодов) является высокая трудоемкость их построения при длине кодовой последовательности n ≥ 31 двоичный символ и коррекции ошибок кратностью t_ош ≥ 3 двоичных символов. Поиск более простых принципов построения СЛБК привел к открытию нового широкого класса групповых линейных блоковых кодов, получивших название циклических кодов (ЦК). Основоположником ЦК является Прейндж. Дальнейшее развитие теория построения ЦК получила в работах Боуза, Чоудхури, Хоквингейма, Файра, Рида-Соломона, Гоппы и др [1 - 4].

Циклические коды являются подклассом в классе линейных блоковых кодов, удовлетворяющих определенным требованиям. Свое название данные коды получили по причине того, что основной операцией построения кодовых последовательностей, обозначаемых как F_i(x), является цикл, а точнее циклическая перестановка двоичных символов разрешенных кодовых последовательностей. Циклическим кодом называется линейный блоковый код, который представляет собой конечное множество, замкнутое относительно операции циклического сдвига кодовых последовательностей, образующих данный код. Для данных групповых кодов F_i,p(x) в результате циклического сдвига кодовых символов разрешенной КП влево или вправо на один, два, (k-1) символ вновь получается разрешенная КП.

В соответствии с теорией высшей алгебры ЦК – циклический код является идеалом в линейной коммутативной алгебре многочлена (полинома) n-го порядка по модулю двучлена xⁿ – 1 над полем коэффициентов. Это означает, что кодовые последовательности ЦК имеют длину n двоичных кодовых символов и описываются полиномами степени (n – 1), в которых коэффициентами при соответствующих степенях формальной переменной, обозначаемой через x, являются двоичные символы кодовой последовательности. Формальная переменная «x» которая носит название оператора Хаффмана или оператора задержки не оказывает никакого влияния на свойства кода. Таким образом, кодовую последовательность ЦК в общем виде можно записать так:

        F_i(x) = c _n-1 · x ^n-1 + c _n-2 · x ^n-2 + … + c₁ · x¹ + c₀ · x⁰,      (1.1)

где x – формальная переменная;

n-1, n-2,…,1,0 – показатели степеней, в которые возводятся основания кодов, и одновременно порядковые номера, которые занимают двоичные символы (разряды) кодовой последовательности, начиная со старшего и заканчивая последним;

c_i – коэффициенты формальной переменной, которые могут принимать значения или быть равными логической 1 (ненулевой член F_i(x)) или логического 0 (нулевой член F_i(x)). Например,

         F_i(x) = 1 · x⁴ + 0 · x² + 1 · x¹ + 0 · x⁰ = x⁴ + x = 10010. (1.2)

Представление кодовых последовательностей в виде полиномов позволяет установить однозначное соответствие между ними и свести действия над кодовыми последовательностями к действиям над полиномами: умножение, сложение, деление и вычитание этих полиномов производится по обычным правилам алгебры, но коэффициенты с одинаковыми показателями степени «x» суммируются по модулю два. Например, F_i(x) = (x³ + x² +1) · F_j(x)= = (x + 1) = x⁴ + x³ + x³ + x² + x + 1 = x⁴ + (1⊕1) · x³ + x² + x +1= x⁴ + 0 · x³ + x² + +x +1 = x⁴ + x² + x + 1.

Уточним сущность понятия циклического сдвига или циклической перестановки двоичных символов кодовой последовательности. Пусть        F_i(x) = c _n-1 x ^n-1 + c _n-2 x ^n-2 + … +c₁ x¹ + c₀ x⁰, то циклический сдвиг на один разряд дает F_i(x) = c _n-1 x ⁿ + c _n-2 x ^n-1 + … +c₁ x¹ + c₀ x⁰. Чтобы степень новой кодовой последовательности F_i(x) не превышала (n-1), член c _{n-1 ·} x ⁿ заменяется единицей, поэтому F_i(x) = c _n-2 x ^n-1 + c _n-3 x ^n-2 + … + c₁x² + c₀x⁰ + c _n-1 x ⁰ [1,2].

Заметим, что запись кодовой последовательности в виде многочлена, а затем перевода ее в двоичную форму записи, не всегда определяет длину кодовой последовательности n. Например, при n=5, многочлен F(x)= =x²+1=101, т.е. n=3, что неверно. В таких случаях надо дописать старшие нулевые символы, т.е. F(x)= x²+1=00101, что дает n=5 двоичным символам. Пусть F(x)= x⁵ + x³ + x² + x и n=7. Перевод в двоичную форму записи F(x)=0101110.

Сдвигаем F(x) на один разряд (символ) влево, и получаем F(x)=1011100= x⁶ + x⁴ + x³ + x². Очевидно, что x¹(x⁵ + x³ + x² + x)= x⁶ + x⁴ + x³+ +x²=1011100.

Следовательно, циклическую перестановку двоичных символов разрешенной кодовой последовательности можно рассматривать как умножение F(x) на x при первом сдвиге, на x² при втором сдвиге и т.д., что можно в общем виде записать или представить так:

                                              (1.3)

Так как при сложении по модулю два двучлен xⁿ-1можно записать как xⁿ=1, то замена xⁿ на 1 в произведении  дает новый многочлен, коэффициенты которого образуют новую разрешенную кодовую последовательность. Следовательно, в кодовой последовательности, имеющей длину n двоичных кодовых символов, степень полинома не может превышать n-1, так как в противном случае длина кодовой последовательности превысит n, а поэтому xⁿ заменяется логической 1.

Таким образом, можно сделать следующие выводы:

- ЦК – это такой линейный код, который обладает свойством цикличности кодовых последовательностей, т.е. когда каждая разрешенная кодовая последовательность содержит ее циклическую перестановку;

- ЦК относятся к групповым линейным кодам, если они образуются путем умножения каждой последовательности равнодоступного (простого) кода, выраженных в виде многочлена Q(x) с максимальной степенью (k-1), на некоторой полином P(x) степени l=n-k. Приведение подобных членов производится по модулю два; порядок поля кодирования преобразуется с K_раз=2^k до K_общ=2ⁿ, но число разрешенных кодовых последовательностей кода при этом остается равным K_раз=2^k, и они образуют циклическую подгруппу группы K_общ=2ⁿ, отличающуюся тем, что все элементы подгруппы имеют общее свойство делимости на полином P(x), получивший название образующего или порождающего полинома.

В качестве образующего полинома используются полиномы, обладающие следующими свойствами:

- образующий полином P(x) должен быть делителем двучлена xⁿ+1;

- образующий полином не должен раскладываться на сомножители более низких степеней, и должен делиться без остатка на самого себя и на 1, т.е. на x⁰;

- максимальная степень образующего полинома должна быть равной l=n-k, т.е. соответствовать количеству проверочных символов используемого кода.

В общем виде ЦК записывается как (n; k; d₀), что полностью определяет его параметры.

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии