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

12
)
(
)
(
)
(
)
(
1 1
x
P
x
E
x
P
x
H
r
r
=
Каждый вектор ошибок, число единиц в котором не превышает исправляющую способность циклического кода, будет иметь свой уникальный остаток от деления на образующий полином. Причем, этот остаток не будет зависеть от передаваемой разрешенной комбинации. Данное свойство позволяет по остатку однозначно определить вектор ошибок и провести инвертирование ошибочных разрядов.
Рассмотренный подход предполагает хранение остатков всех векторов ошибок, подлежащих исправлению данным кодом и последующее их сравнение с текущим остатком. С ростом длины кодовой комбинации и исправляющей способности кода такой подход требует большой объем памяти для хранения остатков и много времени для проведения сравнения. Изучение свойств циклических кодов позволило синтезировать методы, дающие возможность сократить количество хранимых остатков.
Рассмотрим алгоритм определения ошибочного разряда на примере циклического кода (9,5) с кодовым расстоянием равным 3. Данный алгоритм позволяет исправить все однократные ошибки и при этом требует сохранения только одного остатка.
Алгоритм исправления однократной ошибки
Положим, для передачи используется циклический код длиной n элементов, порожденный образующим полиномом P
r
(x).
1. Получим остаток от деления вектора ошибок Е(х), соответствующего ошибке в старшем разряде
1
−
n
x
, на образующей полином P
r
(x)
)
(
)
(
0 1
x
R
x
P
x
r
n
=
−
2.
Поделим полином принятой комбинации Н(х) на P
r
(x) и получим текущий остаток R(x).
Если R(x)=0, то в принятой кодовой комбинации ошибок нет. Если же текущий остаток ненулевой – определяем местоположение ошибки в кодовой комбинации (п.3).
3. Сравним остатки R
0
(x) и R(x).
–
Если они равны, то ошибка произошла в старшем разряде.
–
Если "нет", то увеличиваем степень принятого полинома на единицу и снова проводим деление и сравнение текущего остатка с R
0
(x).

13
)
(
)
(
)
(
x
R
х
Р
х
х
Н
r
=
•
(
здесь умножение на x производится без циклического
сдвига)
Если остатки совпали, то ошибка во втором разряде.
Если нет, то продолжаем увеличивать степень принятого многочлена и делить до тех пор, пока R(x) не будет равен R
0
(x).
При этом номер ошибочного разряда не единицу больше числа, на которое повысили степень принятого многочлена. То есть если,
)
(
)
(
)
(
0
x
R
x
P
х
х
Н
r
Y
=
то номер ошибочного разряда
N
ош
=Y+1.
Например: если
)
(
)
(
)
(
0 3
x
R
x
P
х
х
Н
r
=
то номер ошибочного разряда N
ош
=3+1=4
Пример декодирования комбинации циклического кода (9,5)
Положим принятая комбинация H(х)=111011010.
Проведем анализ данной комбинации по приведенному выше алгоритму.
В соответствии с первым пунктом алгоритма, определим остаток от деления вектора соответствующего ошибке в старшем разряде x
8
на производящий полином
1
)
(
4
+
+
=
x
x
x
P
r
Проведем деление принятой комбинации
111011010
)
(
=
x
H
на образующий полином.
H(x)
•
x
111011010 0
10011 10011 111111 5- т 11101 10011 6- т 11100

14 10011 7- т 11111 10011 8- т 11000 10011 9- т 1011 0
= R(X)
≠ R
0
(X)
10011 10- т 0101=
R(X) =
R
0
(x)
Полученный после 9-го такта остаток [1011] ненулевой и не равен R
0
(X).
Значит, в комбинации есть ошибка, но не в первом разряде.
Умножим принятую комбинацию на х (т.е. допишем один ноль со стороны младшего разряда) и продолжим деление до тех пор, пока в остатке не будет
R
0
(Х). В нашем случае это произойдет на 10 такте, при повышении степени на 1. Значит ошибка во втором разряде. Для исправления инвертируем второй разряд и получим исправленную комбинацию 101011010.
2.4.3
Декодер циклического кода с исправлением однократной ошибки
Декодер с исправлением ошибки состоит из регистра задержки, число ячеек которого равно числу элементов кодовой комбинации, устройства деления на образующий полином, дешифратора остатка и сумматора, играющего роль управляемого инвертора. Дешифратор построен на базе элемента логического умножения с инверторами на входах. Инверторы расставляются таким образом, что бы при появлении в ячейках остатка R
0
(Х) на выходе дешифратора формировалась логическая единица. На рисунке 2.6 в ячейках устройства деления записан ожидаемый остаток R
0
(Х) (старший разряд справа). Как видим, инверторы на входах дешифратора ставятся после тех ячеек регистра, где ожидаются нули остатка.
Рисунок 2.6 – Декодер циклического кода с исправлением однократной ошибки

15
Девять тактов происходит заполнение ячеек регистров задержки и деление принятой комбинации на полином. После девятого такта старший разряд принятой комбинации занимает последнюю (правую) ячейку регистра задержки, а в ячейках ФПГ сформирован остаток. Если данный остаток совпадает с ожидаемым, то на выходе дешифратора формируется логическая единица, которая поступает на вход сумматора. При этом на десятом такте старший разряд, проходя через сумматор – инвертируется. В рассмотренном примере после девятого такта остаток не совпадает с R
0
(Х), поэтому инверсии старшего разряда не произойдет. Ожидаемый остаток появится в ФПГ после десятого такта, что приведет к исправлению второго разряда на одиннадцатом такте.
2.5
Качественные показатели корректирующих кодов
Очевидно, что эффективность корректирующего кода тем выше, чем большую кратность ошибки он может обнаруживать и исправлять, и чем меньше для этого необходимо проверочных разрядов. Для оценки эффективности корректирующего кода часто используются такие качественные показатели как коэффициент обнаружения ошибок K
о.ош
, коэффициент исправления ошибок K
и.ош и избыточность кода f [1].
Коэффициент обнаружения ошибок определяется отношением вероятности появления на выходе дискретного канала комбинаций с обнаруживаемыми кодом ошибками P
о.ош к вероятности появления искаженных комбинаций, содержащих ошибки любой кратности P
ош
:
∑
∑
=
=
=
=
n
t
n
t
t
n
ош
ош
о
ош
о
t
P
t
P
Р
Р
К
об
1 1
)
(
)
(
Коэффициент исправления ошибок определяется отношением вероятности появления на выходе дискретного канала комбинаций с исправленными кодом ошибками P
и.ош к вероятности появления искаженных комбинаций P
ош
:
∑
∑
=
=
=
=
n
t
n
t
t
n
ош
ош
и
ош
и
t
P
t
P
Р
Р
К
ош
и
1 1
)
(
)
(
Коэффициент избыточности
n
r
f
=
определяет степень удлинения кодовой комбинации за счет добавления проверочных разрядов для достижения необходимой корректирующей способности.

16
Очевидно, что эффективность применения в конкретном канале циклического кода тем выше, чем ближе к единице K
о.ош
, K
и.ош и ближе к нулю
f.
В общем случае для конкретных значений n можно найти несколько различных кодов с разной исправляющей способностью t
и.ош и, соответственно, разными значениями r и f. Как правило, код, исправляющий ошибки большей кратности, т.е. с большим K
и.ош
, имеет и большую избыточность, а значит, меньшую долю информационных разрядов. Очевидно, что такой код будет с меньшей скоростью передавать символы сообщения. Таким образом, скорость правильной передачи символов зависит от двух характеристик кода, влияющих на нее противоположным образом.
Для сравнения корректирующих кодов можно использовать интегральный показатель, одновременно учитывающий избыточность и исправляющую способность кода. Таким показателем может быть относительная скорость передачи, являющаяся произведением скорости кода на вероятность правильного исправления ошибок в кодовой комбинации
∑
=
=
ош
и
t
m
n
m
P
n
k
E
0
)
,
(
Вопросы выбора образующих полиномов подробно изложены в [1,3,7].

17
3 Выполнение лабораторной работы
Добрый совет! He выполняйте действий, не предусмотренных данным
описанием. Это приводит к увеличению показаний счетчика ошибок и, как
следствие, снижению Вашей оценки. Операции отмены действия в
программе не предусмотрено.
3.1.
Изучите основные теоретические сведения к данной лабораторной работе по приведенной в пункте 6 литературе и данным методическим указаниям.
3.2.
Перед выполнением работы, получите у преподавателя номер варианта, который вводится в первом окне программы.
3.3
. Запустите обучающую программу, двойным щелчком мыши на ярлыке
«Циклические коды».
На экране появится входное окно программы (рисунок 3.1).
Рисунок 3.1 – Входное окно программы
- после ввода варианта, программа выдает соответствующий полином и предлагает студенту ответить на серию вопросов связанных с построением кодера по виду полинома.
- после того как студент правильно ответит на заданные вопросы, на экран выводится первая структурная схема кодирующего устройства (рисунок 3.2).

18
Рисунок 3.2 – Интерфейс программы
В верхней части окна присутствуют номер варианта, образующий полином, счетчик ошибок при ответах и текущее время, затраченное на выполнение работы.
При неверном ответе программа выдает сообщение и в верхнем правом углу увеличивает показания счетчика ошибок на единицу (рисунок 3.3), при этом программа предлагает следующий вопрос только в случае верного ответа на предыдущий вопрос.
Рисунок 3.3 – Интерфейс программы

19
- далее программа генерирует группу вопросов, отражающих динамику работы кодера, содержимого ячеек и положения ключей. Типовое окно для данной части работы показано на рисунке 3.4.
Рисунок 3.4 – Типовое окно программы
Содержимое ячеек по тактам приводится в правом окне программы.
После окончания процесса кодирования, предлагается второй вариант кодера для заданного полинома.
Рисунок 3.5 – Структурная схема второго варианта кодера

20
- для данного типа кодера генерируются вопросы и отображаются соответствующие действия, касающиеся содержимого ячеек и состояния ключей по тактам.
- далее в динамике рассматриваются вопросы декодирования. Студенту предлагается декодировать две кодовых комбинации, одна из которых содержит ошибку.
Рисунок 3.6 – Декодер циклического кода
В процессе деления можно проследить изменение содержимого ячеек и положения ключей. Результат деления комбинации с ошибкой показан на рисунке 3.7
Рисунок 3.7 – Остаток от деления принятой комбинации на образующий полином

21
- по окончанию работы на экран выводится окно результата, которое необходимо показать преподавателю.
Рисунок 3.8 – Окно результатов
В данном окне отображается число заданных вопросов, количество допущенных ошибок и время, затраченное на выполнение задания. Данные показатели позволяют преподавателю объективно оценить качество знаний студента по данной теме.
- по окончании выполнения лабораторной работы следует закрыть программу, затем выключить компьютер.
4
Требования к оформлению отчета
Отчет должен содержать:
1. титульный лист с соответствующими атрибутами (ФИО студента и преподавателя, номер группы, номер варианта, наименование работы и др.);
2.
Цель работы;
3.
Производящий полином;
4.
Исходную информационную комбинацию;
5.
Структурные схемы кодеров и декодеров;
6.
Содержимое ячеек памяти на каждом такте;
7.
Выводы по результатам проделанной работы.
Первые два пункта оформляются дома при подготовке к выполнению работы, а пункты с 3 по 6 – в процессе выполнения работы в лаборатории.
Выводы по результатам проделанной работы делаются дома при подготовке к защите лабораторной работы.

22
5 Контрольные вопросы
1.
Классификация корректирующих кодов.
2.
Назовите основные свойства циклических кодов.
3.
Какое свойство дало название циклическим кодам.
4.
Двоичное и полиномиальное представление кодовых комбинаций.
5.
Пояснить суть двух способов получения циклических кодов, чем отличаются полученные при этом коды.
6.
Объясните, как строится структурная схема кодера циклического кода по образующему полиному.
7.
Поясните принцип работы кодера.
8.
Нарисуйте структурную схему декодера с обнаружением ошибок и поясните принцип его работы.
9.
Алгоритм определения ошибочного разряда.
10.
Нарисуйте структурную схему декодера с исправлением однократной ошибки и поясните принцип его работы.
11.
Какими свойствами должны обладать полиномы, которые можно использовать в качестве образующих.
12.
Из каких соображений выбирается образующий полином.
13.
Что такое коэффициенты обнаружения ошибок, исправления ошибок и избыточности.
14.
Исходя из чего выбирается исправляющая способность кода.
15.
Построение укороченных циклических кодов.
16.
Построить структурную схему кодера циклического кода и пояснить его работу, если задан образующий полином.
17.
Построить структурную схему кодера циклического кода и показать что будет на каждом такте в ячейках ФПГ, если задан образующий полином и исходная информационная комбинация.
18.
Построить структурную схему декодера циклического кода с обнаружением ошибок и пояснить его работу, если задан образующий полином.
19.
Получить разрешенную кодовую комбинацию циклического кода (k,r), если заданы комбинация исходного простого кода и образующий полином.
20.
Определить, в общем виде, вероятность неправильного приема кодовой комбинации
НП
P
, если для передачи используется корректирующий код с кодовым расстоянием
0
d
=5 в режиме исправления ошибок. Длина кодовой комбинации n=12 и вероятность ошибочного приема элемента
ош
P
=3*10
-3

23
6
Список литературы
1.
Передача дискретных сообщений: Учебник для вузов/ под редакцией
Шувалова В. П. – М.: Радио и связь, – 1990. – 464 с.
2.
Телекоммуникационные системы и сети: Уч. пособие. В 3 томах. Том 1
–
Современные технологии/ Б.И. Крук, В.Н. Попантонопуло, В.П. Шувалов; под ред. профессора В.П. Шувалова. – Изд. 3-е, испр. и доп. – М.: Горячая линия – Телеком, 2003. – 647 с.: ил.
3.
Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е испр.:Пер. с англ. –М.: Издательский дом «Вильямс»,
2003.–
1104 с.:ил. – Парал. тит. Англ.
4.
Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ.–М.: Радио и связь, 1987.–392с
5.
Блейхут Р. Теория и практика кодов, контролирующих ошибки: Пер. с англ.– М.: Мир, 1986. – 576 с.
6.
Макаров А.А., Прибылов В.П. Помехоустойчивое кодирование в системах телекоммуникаций: Учеб. Пособ./ Сиб. гос. ун-т телекоммуникаций и информатики.– Новосибирск. 2004.– 142с.

24
О.Г. Мелентьев, И.Е. Шевнина
Циклические коды
Методические указания к лабораторной работе
Редактор: В.П. Шувалов
Корректор: Д.С. Шкитина
Лицензия ЛР_020475, январь 1998 г. Подписано в печать ________
Формат бумаги 62x84 1/16, отпечатано на ризографе, шрифт № 10,
Изд. л. , заказ № ____, тираж – 300 экз, СибГУТИ
630102, г. Новосибирск, ул. Кирова, 86.