Лабораторная работа 5
Циклическое кодирование
Цели работы:
приобретение практических навыков построения циклического кода по заданным характеристикам и проверка его свойства по обнаружению и исправлению ошибок;
программная реализация соответствующих алгоритмов кодирования.
Теоретические сведения
Циклические коды широко применяются при передаче данных в сетях и системах телеобработки данных. По способу и системе коррекции ошибок они относятся к блочным неразделимым кодам.
Основной принцип использования основывается на формировании ком бинации кода путем циклического сдвига разрядов влево образующего многочлена. Эта операция аналогична процедуре умножения на Х:
(Х4 + Х3 + Х2 + 1) X = X5 + X4 + X3 + X
0011101 0111010
Таким образом, при соответствующем выборе образующего многочле на любая разрешенная комбинация может быть получена в результате умножения образующего многочлена на некоторый другой многочлен.
Основная идея обнаружения и исправления ошибок заключается в делении комбинации кода на образующий многочлен, т. е.:
где G(X) – комбинация кода;
K(X) – образующий многочлен;
Q(X) – результат деления;
R(X) – остаток.
Если остаток равен нулю, то исследуемая комбинация – разрешенная, и код не содержит ошибки. В противном случае имеется ошибка.
Пример. Найти образующий многочлен для следующих параметров кода: d0 = 3, п = 7.
Решение. Вычислим число проверочных m и информационных k сим волов.
m = log (n + 1) = 3 k = n – m = 7 – 3 = 4.
По таблице неприводимых многочленов найдем для m = 3 и d = 3 обра зующий многочлен вида 1101 или: K(X) = X3 + X2 + 1.
Вычислим проверочные разряды и получим образующую матрицу путем умножения всех комбинаций кода на образующий многочлен.
-
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
|
(1101)=
|
0000000
0001101
0011010
0010111
0110100
0111001
0101110
0100011
1101000
1100101
1110010
|
|
|
|
1011
1100
1101
1110
|
|
1111111
1001110
1010001
1000110
1001011
|
Проверим возможность кода на обнаружение и исправление ошибок. Возьмем комбинацию 0111001. Разделим ее на образующий многочлен:
-
0111001
|
1101
|
1101
|
101
|
|
0001101
1101
|
|
0000
|
|
Остаток равен 0, следовательно, это разрешенная комбинация. Исказим третий разряд:
-
0111101
|
1101
|
1101
|
101
|
|
0001001
1101
|
|
0000
|
|
Остаток свидетельствует об обнаружении ошибки.
Правила построения циклических кодов, исправляющих
одну ошибку
1. Расчет соотношения между разрядами:
n = m + k,
где m – число проверочных разрядов;
k – число информационных разрядов;
m = [log (n + 1)]
или:
m = [log {(k + 1) + [log (k + 1)]}].
Выбор образующего многочлена производится по таблицам непри водимых двоичных многочленов, где m – степень многочлена, d – число еди ниц в комбинации.
Выбор параметров единичной матрицы производится исходя из условия, что число столбцов матрицы определяется числом информаци онных разрядов.
Определение элементов дополнительной матрицы производится по остаткам от деления последней строки транспонированной матрицы на об разующий многочлен (это еще один способ формирования образующей мат рицы).
Образующая матрица составляется путем дописывания элементов дополнительной матрицы справа от единичной матрицы или путем умно жения элементов единичной матрицы на образующий многочлен.
Комбинациями исходного кода являются строки образующей мат рицы и всевозможные суммы по модулю 2 различных сочетаний строк обра зующей матрицы.
Обнаружение и исправление ошибок происходит по остаткам от деления принятой комбинации G(X) на образующий многочлен К(Х). Если деление без остатка, то ошибки нет. Для исправления ошибки:
а) принятая комбинация делится на образующий многочлен;
б) подсчитывается вес остатка.
Если W S, где S – допустимое число исправляемых ошибок, то принятая комбинация складывается по модулю 2 с полученным остатком. Сумма даст исправленную комбинацию.
Если W > S, то делим полученную в результате циклического сдвига ком бинацию на образующий многочлен. Если в остатке W S, то складыва ем делимое с остатком. Затем производим циклический сдвиг вправо комби нации, полученной в результате суммирования последнего делимого с остатком. Если после первого циклического сдвига и последующего деле ния остаток получается таким, что его вес W > S, то процедура повторяется до тех пор, пока W S. Затем производится циклический сдвиг вправо на столько разрядов, на сколько была сдвинута принятая комбинация. В результате получаем исправленную комбинацию.
Задание
Получить у преподавателя задание и ознакомиться с ним.
Вычислить параметры кода d, m, k, p, l, S. Найти образующий многочлен, воспользовавшись таблицей неприводимых многочленов.
Проверить, имеются ли ошибки в исследуемой комбинации, при на личии ошибок – исправить их.
Провести программный контроль выполнения 4, 5 пунктов на при мере случайных кодовых комбинаций.
Подготовить отчет и сдать работу.
Контрольные вопросы
1. В чем заключаются основные идеи обнаружения и исправления ошибок циклическим кодом?
2. Что такое кодовое расстояние?
Чем отличается представление циклическим кодом для d = 3 и d = 5, где d – кодовое расстояние?
Какие существуют способы формирования комбинаций циклическо го кода?
5. В чем достоинство циклических кодов?
6. Что такое транспонированная матрица для циклического кода и ее размерность?
Литература
Цымбал В. П. Задачник по теории информации и кодированию. Киев: Вища школа, 1976. 275 с.
Цымбал В. П. Теория информации и кодирование: Учебник. – 4-е изд., перераб. и доп. Киев: Вища шк., 1992. 263 с.
Кудряшов Б. Д. Теория информации: Учебное пособие для вузов. СПб.: Питер, 2009. 322 с.
Вернер М. Основы кодирования: Учеб. для вузов: Пер. с нем. М.: Техносфера, 2004. 286 с.
Сэломон Д. Сжатие данных, изображений и звука: [Учеб. пособие для вузов]: Пер. с англ. / Д. Сэломон. М.: Техносфера, 2004. 365 с.
Методы сжатия данных: Устройство архиваторов, сжатие изображений и видео / Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. М.: ДИАЛОГ МИФИ, 2002. 381 с.
Чернавский Д. С. Синергетика и информация: Динамическая теория информации / 3-е изд., доп. М.: Книжный дом "ЛИБРОКОМ", 2009. 300 с.
Орлов В. А. Теория информации в упражнениях и задачах: Учебное пособие для студентов втузов. М.: Высшая школа, 1976. 136 с.
Хэмминг Ричард В. Теория кодирования и теория информации М.: Радио и связь, 1983. 174 с.
Приложение
Пример оформления титульного листа
отчета по лабораторной работе
Министерство образования и науки РФ
ФГБОУ ВПО «Северо-Кавказский горно-металлургический институт (государственный технологический университет)»
Кафедра автоматизированной обработки информации
ОТЧЕТ
по лабораторной работе № 5
«Циклическое кодирование»
по дисциплине «Теория информации»
Выполнил:
___________________
Проверил:
___________________
Владикавказ 2015
|
