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

Республика Казахстан

АО «Казахская академия транспорта и коммуникаций имени М. Тынышпаева»

Кафедра «Радиотехника и телекоммуникации»

Доклад

по дисциплине «Элементы теории информации»

на тему: Циклические коды

Выполнил: Жанабаева Назимгуль

Группа МП-РЭТ-14-1

Руководитель: к.т.н. Туякбаев А.А.

Алматы 2014

Содержание

Введение

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

Операции над циклическими кодами

Принцип построения циклических кодов

Укороченные циклические коды

Обнаружение и исправление пачек ошибок

Заключение

Список литературы

Введение

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

Данный доклад содержит информацию о циклических кодах: определение, операции производимые над ними, а также принципы построения циклических кодов.

В настоящее время широчайшее распространение в телекоммуникациях получили циклические коды. На практике, как правило, применяются циклические коды, корректирующие ошибки невысокой кратности t<3. Это обусловлено высокими аппаратурными и временными затратами на схемы коррекции (вычислительные затраты), которые резко возрастают при увеличении кратности исправляемых ошибок t>2.

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

Код, в котором кодовая комбинация, полученная путем циклического сдвига разрешенной кодовой комбинации является также разрешенной кодовой комбинацией называется циклическим (полиномиальным, кодом с циклическими избыточными проверками-ЦИП).

Сдвиг осуществляется справа налево, при этом крайний левый символ переносится в конец комбинации.

Циклический код относится к линейным, блочным, корректирующим, равномерным кодам.

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

Циклические коды являются разновидностью систематических кодов и поэтому обладают всеми их свойствами. Первоначально они были созданы для упрощения схем кодирования и декодирования. Их эффективность при обнаружении и исправлении ошибок обеспечила им широкое применение на практике.

Циклические коды используются в ЭВМ при последовательной передаче данных.

(1)

где x - основание системы счисления;

- цифры данной системы счисления;

n-1, n-2,... - показатель степени, в которую возводится основание, и одновременно порядковые номера, которые занимают разряды, начиная от старшего и заканчивая нулевым.

Операции над циклическими кодами

Сложение двоичных многочленов осуществляется по модулю 2 коэффициентов при равных степенях переменной Х. Умножение - по обычному правилу умножения степенных функций. Но когда осуществляется приведение подобных членов коэффициенты складываются по модулю 2. Деление как обычные многочлены. Вычисление - по модулю 2.

. Сдвиг справа налево осуществляется путем умножения полинома на x:(x)=x4+x2+1 Û 0010101;(x)×x=x5+x3+x Û 0101010.

. Операции сложения и вычитания выполняются по модулю 2 .

Они являются эквивалентными и ассоциативными :(x)+G2(x)=>G3(x);(x) -G2(x)=>G3(x);(x)+G1(x)=>G3(x);

Пример:(x)= x5 +x3+x;(x)=x4 +x3 +1;(x)=G1(x) Å G2(x) = x5 +x4+x+1.

. Операция деления является обычным делением многочленов, только вместо вычитания используется сложение по модулю 2:(x)=x6+x4+x3;(x)=x3+x2+1.

Принцип построения циклических кодов

Особую роль в теории циклических кодов играют неприводимые многочлены. Такой многочлен делится только на самого себя и на единицу. В теории кодирования неприводимые многочлены называются образующими полиномами, поскольку они «образуют» разрешенные кодовые комбинации. В таблице 1 приведены некоторые образующие полиномы.

Таблица 1 - Таблица образующих полиномов

rP(x)Двоичная запись P(x)2x2+x+11113x3+x+111014x4+x+110011 5x5+x2+1 x5+x4+x3+x2+1 x5+x4+x2+x+1100101 111101 1101116x6+x+1 x6+x5+x2+x+11000011 1100111 7x7+x3+1 x7+x3+x2+x+1 x7+x4+x3+x2+110001001 10001111 10011101 8x8+x7+x6+x5+x2+x +1 x8+x4+x3+x2+1 x8+x6+x5+x+1111100111 100011101 101100011

Построение разрешенной кодовой комбинации циклического кода сводится к следующему:

. Представляем информационную часть кодовой комбинации длиной k в виде полинома Q(x).

. Производим сдвиг k -разрядной кодовой комбинации на r разрядов, путём умножения Q(x) на одночлен xr.

. Делим многочлен Q(x) xr на образующий полином Р(x), степень которого равна r. В результате деления образуется остаток R(x).

. Разрешенная кодовая комбинация циклического кода имеет следующий вид:

(2)

Обнаружение ошибок при циклическом кодировании сводится к делению принятой кодовой комбинации на тот же образующий полином Р(х), который использовался при кодировании. Если ошибок в принятой кодовой комбинации нет, то деление на образующий полином производится без остатка. Если при делении получится остаток, то это свидетельствует о наличии ошибки. Остаток от деления в циклических кодах играет роль «синдрома».

Для определения местоположения ошибки в циклическом коде существует ряд методов, основанных на анализе «синдрома» R(x).

Основным функциональным узлом кодирующих и декодирующих устройств циклических кодов является схема деления, структура которой приведена на рис. 1.

В состав схемы деления входят сдвигающий регистр (ячейки 1 - 4), сумматоры по модулю 2 (М2) и ключ (Кл). Число ячеек сдвигающего регистра выбирается равным степени образующего полинома, а число сумматоров по модулю 2 на единицу меньше его веса. Делимое в виде двоичного кода подается на вход сдвигающего регистра, а полином Р(х) вводится в регистр в виде соответствующим образом подобранной структуры обратных связей через сумматоры по модулю 2. Ключ замыкает обратную связь, что обеспечивает работу схемы деления.

Рисунок 1 - Схема деления на Р(х)

Укороченные циклические коды

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

Если, например, необходимо исправить единичные ошибки при k = 5, то нельзя взять образующий многочлен третьей степени, поскольку он даст только семь остатков, а общее число разрядов получится равным 8.

Следовательно, необходимо брать многочлен четвертой степени и тогда n= 15. Такой код рассчитан на 11 информационных разрядов.

Однако можно построить код минимальной разрядности, заменив в (n, k) -коде j первых информационных символов нулями и исключив их из кодовых комбинаций. Код уже не будет циклическим, поскольку циклический сдвиг одной разрешенной кодовой комбинации не всегда приводит к другой разрешенной комбинации того же кода. Получаемый таким путем линейный (n-j, k-j)-код называют укороченным циклическим кодом. Минимальное расстояние этого кода не менее, чем минимальное кодовое расстояние (n, k)-кода, из которого он получен. Матрица укороченного кода получается из образующей матрицы (n, k)-кода исключением j строк и столбцов, соответствующих старшим разрядам. Например, образующая матрица кода (9,5), полученная из матрицы кода (15,11), имеет вид

Обнаружение и исправление пачек ошибок

Для произвольного линейного блокового (п, k)-кода, рассчитанного на исправление пакетов ошибок длины b или менее, основным соотношением, устанавливающим связь корректирующей способности с числом избыточных символов, является граница Рейджера: n - k ? 2b

При исправлении линейным кодом пакетов длины b или менее с одновременным обнаружением пакетов длины l ? b или менее требуется по крайней мере b + l проверочных символов.

Из циклических кодов, предназначенных для исправления пакетов ошибок, широко известны коды Бартона, Файра и Рида-Соломона.

Первые две разновидности кодов служат для исправления одного пакета ошибок в блоке.

Коды Рида-Соломона способны исправлять несколько пачек ошибок.

Заключение

Циклические коды получили довольно широкое применение благодаря их эффективности при обнаружении и исправлении ошибок. Схемы кодирующие и декодирующих устройств для этих кодов чрезвычайно просты и строятся на основе обычных регистров сдвига.

Список литературы

циклический код многочлен ошибка

Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. - М.: Издательский дом «Вильямс», 2003 г. - 1104 с.

Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. - 120с.

Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. -368 с.

С.И. Баскаков: «Радиотехнические цепи и сигналы» - М.: Высшая школа, 2005.