Полиномиальная арифметика

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

(краткий пересказ)

Что это такое

Циклические коды относятся к линейным кодам. Специфические свойства данного вида кодов помогают как при кодировании/декодировании, так и при аппаратной реализации этих процессов.

Одно из определений циклического кода

Определение

Линейный код называют циклическим, если для любого кодового слова [x_nx₀x₁...x_n-1] циклическая перестановка символов [x₀x₁...x_n-1x_n] также дает кодовое слово.

Процедура построения таких кодов гораздо более управляемая. Однако, нам потребуется перейти от векторного описания кодов к полиномиальному. Последовательность символов основного алфавита (0'ки и 1'ки в простейшем случае), составляющие сообщения и кодовые слова мы будем интерпретировать как коэффициенты полиномов. Например, считая, что коэффициенты записаны в порядке возрастания степени, сообщение [1010] запишем в виде многочлена 1 + x². Кодирование сообщения в более "длинное" кодовое слово будет проводится умножением этого многочлена на другой, что дает в результате многочлен более высокой степени.

Рассмотрим операции с многочленами подробнее.

Полиномиальная арифметика

Рассмотрим многочлены с коэффициентами из поля Z₂. Сложение, умножение и деление полиномов проводится как обычно.

Для тех, кто это подзабыл, приведем пример на деление.

Дата добавления: 2015-07-16