Исправление пакетных ошибок (т5-4)

Адрес

http://90.189.213.191:4422/temp/nkpsis/tema_tec_tc23/lek15/lek15.doc инд: 2-124-6-15 пример

Образующие многочлены кодов, способных обнаруживать одиночные, двойные и тройные ошибки, можно определить, базируясь на следующем указании Хэмминга. Если известен образующий многочлен р(хт) кода длины п, позволяющего обнаруживать ошибки некоторой кратности z, то образующий многочлен g(x) кода, способного обнаруживать ошибки следующей кратности (z + 1), может быть получен умножением многочлена р(хт) на многочлен х + 1, что соответствует введению дополнительной проверки на четность. При этом число символов в комбинациях кода за счет добавления еще одного проверочного символа увеличивается до n + l.

В таблице ниже приведены основные характеристики некоторых кодов, способных обнаруживать ошибки кратности три и менее.

Показатель неприводимого многочлена	Образующий многочлен	Число информационных символов	Длина кода
3 4 5	(x+1)(x^3 + x + 1) (x+1)(x^4+ x + 1) (x+1)(x^5+ x + 1)	4 11 26	8 16 32

Пример исправления блочной ошибки по коду хеминга

Функциональная схема:

Принципиальная схема

Выбор образующего полинома

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

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

Образующий полином нужно выбирать, как уже отмечалось ранее, с учетом того, что его степень должна быть равна числу проверочных символов.

Помимо этого полином должен входить в качестве сомножителя в разложение двучлена

(4.5)

Доказано , что любой двучлен Типа (4,5) может быть представлен произведением всех без исключения непроводимых многочленов, степени которых являются делителями числа (от 1 до включительно). Следовательно, для любого существует, по крайней мере, один неприводимый многочлен степени входящий сомножителем в разложение двучлена Боуз и Чоудхури показали, что для любых целых положительных чисел существует циклический код значности.

с кодовым расстоянием

Более подробно значение кодов для поиска ошибок смотрите в прилагаемой литературе.

На модели Протеус-7 используем элемент «pattgen», «генератор(модель) точек» и проверим формирование ошибки с исправлением.

Ниже на рисунке-gif показан набор сигналов в «pattgen» для отображения на 7-сегментном индикаторе последовательного отображения цифр 0.1..9

Формируются сигналы для точки-1,2. В результате выполняется отображение от 0..9 последовательного сигнала.

Возможно, формировать отображение и без счетчика, в этом случае индикатор надо подключить , например Q0.3 и установить точки, в соответствии отображению.

В каждый тактовый интервал, устанавливая «точки» можно сформировать любой байт на передачу.

Контрольные вопросы по теме «Исправление пакетных ошибок» ответы представлять в формате Word документа и файла проекта dsn.

Оценка на 3= рассказать о «блочности» ошибок, пояснить понятие «блочности».

· Рассказать о методе Хемминга и принципе «деления/умножения на полином».

· Привести пример передачи 4-х байт и проверки по контрольной сумме по байтно.

· Используя пример koder_pat1.DSN добавить еще один индикатор (если потребуется) и построить отображение «точками» для счетчика от 0 до своего номера по списку. Третий индикатор ошибки и должен отображать 0-если код четный и 1-если передаваемый код нечетный.

· Разрешается использовать все разряды «генератора точек»

Оценка на 4= Дополнительно, добавить в модель Протеус-7 схему определения синдрома ошибки по коду Хемминга

Выбрать свой вариант КР по таблице

КР-А = Nпо_списку- 1,5,9 и тд.

КР-B =Nпо_списку - 2,6,10 и т.д.

КР-С =Nпо_списку - 3,7,11

КР-D= Nпо_списку-4,8,12 и т.д.

Оценка на 5= Дополнительно, построить схему циклического полинома x1+x7 для передаваемого байта.

Электронные источники:

1. Обнаружение ошибок кратности три и ниже
2. Основные принципы обнаружения и исправления ошибок
3. Помехоустойчивое кодирование с иcпользованием различных кодов

Подготовил Шабронов А.А.  тс +7-913-905-8839  shabronov@ngs.ru 10