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

Размещено на http://www.allbest.ru/

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

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

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

Доклад

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

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

Выполнил:

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

Жанабаева Назимгуль

Руководитель:

к.т.н. Туякбаев А.А.

Алматы 2014

Содержание

Введение

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

1. Сдвиг справа налево осуществляется путем умножения полинома на x:

G(x)=x4+x2+1 0010101;

G(x)x=x5+x3+x 0101010.

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

Они являются эквивалентными и ассоциативными:

G1(x)+G2(x)=>G3(x);

G1(x) -G2(x)=>G3(x);

G2(x)+G1(x)=>G3(x);

Пример:

G1(x)= x5 +x3+x;

G2(x)=x4 +x3 +1;

G3(x)=G1(x) G2(x) = x5 +x4+x+1.

3. Операция деления является обычным делением многочленов, только вместо вычитания используется сложение по модулю 2:

G1(x)=x6+x4+x3;

G2(x)=x3+x2+1.

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

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

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

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

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особенности декодирования циклических кодов, исправляющих пакеты ошибок, рассмотрены далее на примере кодов Файра.

Заключение

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

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

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

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

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

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

Размещено на Allbest.ru