Файл: Методические указания к лабораторной работе Сибирский государственный университет телекоммуникации и информатики 1.pdf

0
Министерство связи и массовых коммуникаций
Российской Федерации
О.Г. Мелентьев
И.Е. Шевнина
Циклические коды
Методические указания к лабораторной работе
Сибирский государственный университет телекоммуникации и информатики

1
Федеральное агентство связи
Государственное образовательное учреждение
высшего профессионального образования
Сибирский государственный университет
телекоммуникаций и информатики
(ГОУ ВПО «СибГУТИ»)
О.Г. Мелентьев, И.Е. Шевнина
Циклические коды
Методические указания к лабораторной работе
Новосибирск
2009

2
УДК 621.394.
О.Г. Мелентьев, И.Е. Шевнина. Циклические коды: Практикум /
СибГУТИ. – Новосибирск, 2009. – 24с.
Практикум предназначен для выполнения лабораторных работ по курсам
«
Основы построения телекоммуникационных систем и сетей» и «Основы передачи дискретных сообщений» для изучения студентами принципов построения циклических кодов. В практикуме приведена классификация корректирующих кодов, рассмотрены вопросы построения циклических кодов, кодеров и декодеров циклических кодов. Практическая часть методических указаний наглядно иллюстрирована, и поясняет ход выполнения работы.
Кафедра передачи дискретных сообщений и метрологии
Ил. 14, табл. 1, список лит. – 6 наименований
Рецензент: И.И. Резван
Для студентов старших курсов, обучающихся по специальностям: 210406 –
«Сети связи и системы коммутации» (различных форм обучения); 210403 –
«Защищенные системы связи, 240404 – «Многоканальные телеком- муникационные системы», 210401 – «Физика и техника оптической связи».
Утверждено редакционно-издательским советом СибГУТИ в качестве практикума
© ГОУ ВПО «Сибирский государственный университет телекоммуникаций и информатики», 2009 г.

3
Оглавление
1 Цель работы ..................................................................................................... 4 2 Краткие теоретические сведения ................................................................... 4 2.1 Классификация корректирующих кодов ................................................. 4 2.2
Способы построения циклических кодов ............................................... 5 2.3
Построение кодера циклического кода ................................................... 7 2.4
Декодирование циклических кодов ....................................................... 10 2.4
.1 Декодер циклического кода с обнаружением ошибки ................ 10 2.4.2
Декодирование с исправлением ошибок ....................................... 11 2.4
.3 Декодер циклического кода с исправлением однократной ошибки ........................................... 14 2.5
Качественные показатели корректирующих кодов ............................. 15 3 Выполнение лабораторной работы .............................................................. 17 4 Требования к оформлению отчета ............................................................... 21 5 Контрольные вопросы................................................................................... 22 6 Список литературы ....................................................................................... 23

4
1
Цель работы
1.1.
Изучение принципов построения циклических кодов;
1.2.
Получение практического навыка построения кодеров и декодеров циклических кодов.
2 Краткие теоретические сведения
2.1 Классификация корректирующих кодов
Корректирующие коды это коды, обеспечивающие обнаружение и (или) исправление ошибок. В соответствии с классификацией, приведенной в
[2, стр.213] (рисунок 2.1) корректирующие коды делятся на блочные и непрерывные.
Рисунок 2.1 – Классификация корректирующих кодов
К блочным относятся коды, в которых каждому сообщению алфавита соответствует блок (кодовая комбинация) из n(i) элементов, где i – номер сообщения. Если n(i) = n, т.е. длина блока постоянна и не зависит от номера сообщения, то код называется равномерным. Такие коды чаще применяются на практике. Если длина блока зависит от номера сообщения, то блочный код называется неравномерным. В непрерывных кодах передаваемая информационная последовательность не разделяется на блоки, а проверочные элементы размещаются в определенном порядке между информационными
(
Проверочные элементы формируются по определенным правилам, что позволяет обнаруживать и исправлять ошибки).
Равномерные блочные коды делятся на разделимые и неразделимые. В

5 разделимых кодах информационные и проверочные элементы занимают определенные места в кодовой комбинации, в неразделимых – деление элементов кодовых комбинаций на информационные и проверочные отсутствует. К последним относится код с постоянным весом, например рекомендованный ITU-T, семиэлементный телеграфный код № 3 с весом каждой кодовой комбинации, равным трем.
Характерной особенностью систематических кодов является то, что информационные и проверочные элементы связаны между собой зависимостями, описываемыми линейными уравнениями. Отсюда возникает и второе название систематических кодов – линейные.
Блочный, равномерный, систематический корректирующий код представляет собой совокупность разрешенных кодовых комбинаций длиной n элементов. Разрешенными называются комбинации, использующиеся на передаче для кодирования сообщений. Все разрешенные комбинации удовлетворяют некоторым свойствам, отличающим их от остальных комбинаций такой же длины, которые называют запрещенными.
Широкое распространение на практике получил класс линейных кодов, которые называются циклическими. Разрешенные комбинации такого кода удовлетворяют следующим свойствам:
1)
комбинация, полученная циклической перестановкой элементов
разрешенной комбинации (циклическим сдвигом), также является разрешенной
1 2
1 1
2 1
,...
,
,
;
,
,...
,
−
−
→
n n
n n
a a
a a
a a
a a
;
2)
все разрешенные комбинации делятся без остатка на некоторый
выбранный полином, называемый производящим (образующим).
Ненулевой остаток от деления указывает на то, что кодовая комбинация является запрещенной, а значит в ней присутствуют ошибки. Остаток от деления кодовой комбинации на производящий полином называют синдромом
ошибки.
Вопросы выбора образующего полинома изложены в [1].
2.2
Способы построения циклических кодов
Пусть задан образующий полином
( )
1 1
2 1
+
+
+
=
−
−
−
r
r
r
r
r
x
a
x
a
x
P
, определяющий корректирующую способность кода, и задан простой код, который требуется преобразовать в корректирующий циклический код.
Обозначим многочлен, соответствующий комбинации простого кода, Q(x).
Возьмем произведение
( )
r x
x
Q
и разделим его на Р(х). В результате получим многочлен целой части G(x) и остаток от деления R(x)/P
r
(x):

6
)
(
)
(
)
(
)
(
)
(
x
P
x
R
x
G
x
P
x
x
Q
r
r
r
+
=
(2.1)
Умножим левую и правую части выражения (2.1) на P
r
(x)
( )
( ) ( ) ( )
x
R
x
P
x
G
x
x
Q
r
+
=
Перепишем данное равенство в виде
( ) ( )
( )
( )
x
R
x
x
Q
x
P
x
G
r
+
=
(2.2)
(Следует заметить, что сложение выполняется по модулю два, поэтому в
правой части выражения (2.2) стоит знак «+»)
Очевидно, что левая часть (2.2) делится без остатка на P
r
(x)
, значит, без остатка делится и правая часть. Из (2.2) вытекают два способа формирования комбинаций циклического кода.
Способ 1. Разрешенная комбинация может быть получена путем умноже- ния многочлена исходной информационной комбинации G(x) на образующий полином P
r
(x).
Полученный таким способом код будет являться неразделимым.
Способ 2. Основной алгоритм получения разрешенной кодовой
комбинации циклического кода
1.
Выбираем примитивный образующий полином степени равной числу проверочных разрядов – P
r
(x).
2.
Повышаем степень многочлена исходной информационной кодовой комбинации
( )
x
Q
k 1
−
на максимальную степень образующего полинома r (данная операция в двоичном виде эквивалентна дописыванию к исходной комбинации
r нулей со стороны младшего разряда)
( )
r
k
x
x
Q
⋅
−1 3.
Определяем проверочные разряды, как остаток от деления, на образующий полином
( )
( )
( )
x
R
x
P
x
x
Q
r
r
k
⇒
⋅
−1 4.
Для получения разрешенной кодовой комбинации циклического кода прибавляем полученные на третьем шаге проверочные разряды к многочлену, полученному на втором шаге
( )
( )
( )
x
R
x
x
Q
x
A
r
k
n
+
=
−
−
1 1
В данном случае получается разделимый код.
Проиллюстрируем работу алгоритма на примере. Все преобразования будем проводить как в полиномиальной, так и в двоичной форме.

7
Рассмотрим циклический код (9,5), образованный полиномом четвертой степени
1
)
(
4 4
+
+
=
x
x
x
P
Двоичная комбинация, соответствующая образующему полиному –
10011
(старший разряд слева).
Пусть исходная информационная комбинация
10101 1
)
(
2 4
=
+
+
=
x
x
x
Q
, тогда, согласно второго пункта алгоритма:
101010000
)
1
(
)
(
4 6
8 4
2 4
4
=
+
+
=
+
+
=
x
x
x
x
x
x
x
x
Q
Для определения проверочных разрядов проведем деление и получим остаток.
Разрешенная кодовая комбинация, представленная в полиномиальном и двоичном виде, соответственно
( )
x
x
x
x
x
x
A
+
+
+
+
=
3 4
6 8
( )
101011010
=
x
A
2.3
Построение кодера циклического кода
Кодер циклического кода состоит из двух частей: регистра задержки (РЗ) и устройства, производящего деление на образующий полином.
Образующий полином однозначно определяет схему устройства, производящего деление. Назовем данное устройство формирователем проверочных групп и рассмотрим правила его построения.
Правила построения формирователя проверочных групп (ФПГ)
1.
Число ячеек памяти равно степени образующего полинома r.
2.
Число сумматоров на единицу меньше веса двоичной комбинации образующего полинома. Под весом следует понимать количество единиц в двоичной комбинации (число ненулевых элементов).

8 3.
Сумматоры ставят
после ячейки памяти, (начиная с нулевой, которой в схеме нет) для которой существует соответствующий НЕнулевой член полинома. Сумматор не ставят после ячейки, соответствующей старшему разряду.
В цепь обратной связи необходимо поставить ключ, обеспечивающий правильный ввод исходных элементов и вывод результатов деления.
Рисунок 2.2 – Формирователь проверочной группы для
1
)
(
4 4
+
+
=
x
x
x
P
Число ячеек памяти регистра задержки кодера равно максимальной степени образующего полинома.
Кроме формирователя проверочных групп и регистра задержки кодер содержит ключ (K
1
)
, предназначенный для своевременного вывода на выход информационных и проверочных элементов.
Схема кодера циклического кода (9,5) представлена на рисунке 2.3.
Рисунок 2.3 – Кодер циклического кода (9,5) для
1
)
(
4 4
+
+
=
x
x
x
P
Работа кодера циклического кода (9,5)
Исходное положение ключей: К
1
– коммутирует выход ФПГ(положение 2),
К
2
– разомкнут.
1.
Первые четыре такта идет одновременное заполнение ячеек памяти регистра задержки и ФПГ информационными элементами (старший разряд впереди).

9 2.
После четвертого такта К
2
– замыкается а К
1
– переключается к выходу регистра задержки(положение 1). С этого момента, в течение следующих пяти тактов, в ФПГ формируется остаток.
Одновременно из регистра задержки на выход кодера поступают задержанные информационные разряды.
3.
После девятого такта ключи вновь меняют свои положения (К
1
– в положении 2, К
2
– разомкнут) и в след за информационными в канал уходят проверочные элементы, соответствующие остатку от деления полинома
4
)
(
x
x
Q
на
)
(
4
x
P
Одновременно идет заполнение обоих регистров информационными элементами новой кодовой комбинации.
Содержимое ячеек памяти на каждом такте в процессе формирования разрешенной кодовой комбинации для кодера циклического кода
(
1
)
(
4 4
+
+
=
x
x
x
P
;
10101
)
(
=
x
Q
) представлено в таблице 2.1.
Таблица 2.1 – Процесс формирования разрешенной кодовой комбинации
№ такта Вход
№ ячейки ФПГ
№ ячейки РЗ Выхо д
Положение ключей
1 2
3 4
1 2
3 4
0
–
0 0
0 0
0 0
0 0
–
К
1
– в положении
2, К
2
– разомкнут
1 1
1 0
0 0
1 0
0 0
–
2 0
0 1
0 0
0 1
0 0
–
3 1
1 0
1 0
1 0
1 0
–
4 0
0 1
0 1
0 1
0 1
–
5 1
0 1
1 0
1 0
1 0
1
К
1
– в положении
1, К
2
– замкнут
6 0
0 0
1 1
0 1
0 1
0 7
0 1
1 0
1 0
0 1
0 1
8 0
1 0
1 0
0 0
0 1
0 9
0
0
1
0
1
0 0
0 0
1 10 0
0 0
1 0
–
–
–
–
1
К
1
– в положении
1, К
2
– разомкнут
11 0
0 0
0 1
–
–
–
–
0 12 0
0 0
0 0
–
–
–
–
1 13 0
0 0
0 0
–
–
–
–
0
Рассмотренный выше кодер очень наглядно отражает процесс деления двоичных чисел. Однако можно построить кодер, содержащий меньшее число элементов, т.е. более экономичный, позволяющий сформировать проверочные элементы за меньшее число тактов. Данный кодер строится по тем же правилам, что и рассмотренный выше. Отличие заключается в обратном порядке расположения ячеек.

10
Рисунок 2.4 – экономичный кодер циклического кода (9,5)
Исходное состояние ключ К
1
коммутирует вход с выходом кодера
(положение 1), К
2
замкнут, ячейки обнулены.
Первые пять тактов информационные элементы проходят на выход кодера и одновременно в ячейках делителя формируются проверочные элементы.
После пятого такта ключ 2 размыкается (разрывается обратная связь), а ключ 1 переключается к выходу ячейки 4 (положение 2).
Следующие четыре такта на выход передаются сформированные проверочные разряды. Ячейки при этом заполняются нулями, и схема возвращается в исходное состояние.
2.4
Декодирование циклических кодов
При декодировании принятая комбинация делится на образующий полином. В результате деления получается некоторый остаток, называемый синдромом. Если синдром нулевой, то считается, что принята разрешенная комбинация и ошибок нет. Если в остатке есть хотя бы одна единица, то комбинация не является разрешенной, а значит, в ней есть ошибки.
Если количество ошибок в комбинации не превышает исправляющую способность кода, то по виду синдрома можно найти ошибочные разряды и исправить их.
2.4
.1 Декодер циклического кода с обнаружением ошибки
На рисунке 2.5 приведена схема декодера с обнаружением ошибок.
Декодер состоит из регистра задержки, число ячеек которого равно числу информационных разрядов в кодовой комбинации, устройства деления на образующий полином (аналогичного ФПГ), ключей и элемента логического сложения «ИЛИ», который анализирует содержимое ячеек ФПГ.

11
Рисунок 2.5 – декодер циклического кода с обнаружением ошибки для
1
)
(
4 4
+
+
=
x
x
x
P
Исходное положение: ключ К
1
замкнут, К
3
разомкнут.
Деление в данной схеме производится за девять тактов. Первые четыре такта заполняются ячейки ФПГ, после чего пять тактов производится деление.
При этом регистр задержки заполняется информационными элементами за первые пять тактов, после чего ключ К
1
размыкается. После девятого такта замыкается ключ К
3
и сигнал с выхода элемента «ИЛИ» поступает на вход
«Reset» регистра задержки. Если в ячейках ФПГ присутствует хотя бы одна единица, то на выходе элемента «ИЛИ» формируется логическая единица, которая, поступая на вход «Reset» стирает содержимое регистра задержки.
Если остаток от деления нулевой, то на вход «Reset» поступит сигнал низкого уровня, информационные элементы в регистре задержки сохранятся и будут выданы получателю.
2.4.2
Декодирование с исправлением ошибок
Для указания ошибочных элементов в кодовой комбинации используют вектор ошибок. Вектор ошибок это двоичная комбинация длиной равной длине кодовой комбинации, единицы в которой указывают на ошибочные разряды.
Вектору ошибки однозначно соответствует многочлен ошибки E(x). Принятая комбинация является результатом сложения по модулю два переданной разрешенной комбинации и случайного вектора ошибок H(x) =A(x)
⊕
E(x).
Задача исправления ошибок в двоичных кодах сводится к определению вектора ошибок и последующего его сложения по модулю два с принятой комбинацией.
Так как разрешенная кодовая комбинация по определению делится на образующий полином без остатка, то остаток от деления принятой комбинации будет равен остатку, полученному при делении соответствующего вектора ошибки на образующий полином