Циклические коды
Республика Казахстан
АО «Казахская академия транспорта и коммуникаций имени М.
Тынышпаева»
Кафедра «Радиотехника и телекоммуникации»
Доклад
по дисциплине «Элементы теории информации»
на тему: Циклические коды
Выполнил:
Жанабаева Назимгуль
Группа
МП-РЭТ-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 - Таблица образующих
полиномов
r
|
P(x)
|
Двоичная запись P(x)
|
2
|
x2+x+1
|
111
|
3
|
x3+x+1
|
1101
|
4
|
x4+x+1
|
10011
|
5
|
x5+x2+1 x5+x4+x3+x2+1 x5+x4+x2+x+1
|
100101 111101 110111
|
6
|
x6+x+1 x6+x5+x2+x+1
|
1000011 1100111
|
7
|
x7+x3+1 x7+x3+x2+x+1 x7+x4+x3+x2+1
|
10001001 10001111 10011101
|
8
|
x8+x7+x6+x5+x2+x +1 x8+x4+x3+x2+1 x8+x6+x5+x+1
|
111100111 100011101 101100011
|
Построение разрешенной кодовой
комбинации циклического кода сводится к следующему:
. Представляем информационную часть
кодовой комбинации длиной k в виде полинома Q(x).
. Делим многочлен 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.