Общие сведения. Циклические коды (ЦК) являются подклассом в классе линейных блочных кодов

Циклические коды (ЦК) являются подклассом в классе линейных блочных кодов, удовлетворяющим дополнительному свойству цикличности. Циклические коды вместе с каждым кодовым словом (а₁а₂…а _n) содержат также и его циклическую перестановку (а₂а₃…а_nа₁). Для построения кода достаточно задать всего лишь одно кодовое слово. Остальные кодовые слова образуются из исходного путем циклического сдвига влево или вправо на один, два, …, (k-1) символов. При этом упрощаются процедуры кодирования и декодирования. Например, если в ЦК (7;4) входит кодовое слово А₁=0001011, то кодовые слова А₂=0010110 и А₃=0101100 также относятся к данному ЦК. Кодовые слова ЦК имеют длину n двоичных кодовых символов и описываются полиномами степени (n-1), в которых коэффициентами при соответствующих степенях формальной переменной, обозначаемой через х, являются двоичные символы кодовой последовательности. В общем виде кодовую последовательность ЦК можно записать так:

, (19)

где х - формальная переменная;

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

Коэффициенты а_i формальной переменной, могут быть равными логической " 1 " (ненулевой член) или логическому " 0 " (нулевой член). Обычно запись полинома упрощают, опуская сомножители а_i = 1 и вычеркивая слагаемые, в которые входит а_i=0. Например,

а(х)=1∙х⁴+0 ∙х³+1∙х²+0 ∙х¹+1∙х⁰=х⁴+х²+1 (20)

В двоичном коде полиному (6.2) соответствует кодовая последовательность А₁=10101. В приведенном примере кодовое слово имеет длину n=5. Если кодовая комбинация должна иметь большую длину, например, n=7, необходимо дописать в старшие разряды недостающие нулевые символы. Тогда 7-ми разрядная кодовая комбинация, соответствующая полиному (20), примет вид: А₂=0010101. Арифметические действия над полиномами выполняются по обычным правилам, только вычитание заменяется суммированием, а коэффициенты членов полинома с одинаковыми степенями " х " (подобные члены) суммируют по модулю два.

Пример 10 Необходимо выполнить операцию вычитания и операцию умножения с полиномами а₁(х)=х⁵+х³+х² и а₂(х)=х⁴+х²+х. Учитывая особенности арифметических правил при работе с полиномами, получаем:

а₁(х) - а₂(х)=а₁(х)+а₂(х)= х⁵+х³+х²+ х⁴+х²+х= х⁵+х⁴+х³+х,

поскольку х²+х²= х²(1 ;

а₁(х)∙а₂(х)=(х⁵+х³+х²)∙(х⁴+х²+х)= х⁹+х⁷+х⁶+ х⁷+х⁵+х⁴+ х⁶+х⁴+х³= х⁹+х⁵+х³.

Формирование новых разрешенных кодовых последовательностей по одной заданной комбинации а(х) (10) можно рассматривать, как умножение а(х) на " х " при первом сдвиге, на х² при втором сдвиге и т.д. Чтобы степень новой кодовой последовательности не превышала (n-1), член полинома необходимо заменить единицей. Это допустимо, поскольку при сложении по модулю два двучлен (х ⁿ-1) можно записать как хⁿ=1=х⁰. Поэтому, в результате первого сдвига с учетом (10), получаем:

В результате второго сдвига а(х) умножается на х², то есть полученное при первом сдвиге произведение а(х)∙х вновь умножается на х и т.д.

Дата добавления: 2015-08-13