8552

Лабораторная работа №10. Исследование принципов

помехоустойчивого кодирования

Цель работы:изучение и исследование принципов помехоустойчивогокодирования на примере линейных двоичных блочных кодов.

Теоретические сведения

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

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

Пусть источник выдает дискретные символы ai; i=1,2,...K.При их кодировании каждому символу ai ставится в соответствие некотораяпоследовательность кодовых символов длиной n: bi=(bi1,bi2,...bin), называемая кодовой комбинацией. Основание кода - m, в общем случае, но мы будем рассматривать двоичные коды, для которых m=2 и множество кодовых символов: b1=0; b2=1.

Общее число возможных кодовых комбинаций: N=2n. Длякорректирующих кодов число кодовых комбинаций должно удовлетворятьнеравенству: N>K. Таким образом, число кодовых комбинаций большечисла сообщений и только часть комбинаций являются закодированнымисообщениями. Они называются разрешенными комбинациями и их числоNр=K. Остальные N-K комбинаций называются запрещенными ииспользуются для обнаружения и исправления ошибок.

В n-разрядной кодовой комбинации k=log2K кодовых символовявляются информационными, а r=n-k символов – проверочными(избыточными). Легко заметить, что число разрешенных кодовыхкомбинаций Nр=2k. Например, источник выдает 16 различных сообщений(K=16). Их кодируют простым кодом (код у которого все комбинацииявляются разрешенными). Длина простого кода составит в нашем случаеk=log216=4 символа. Затем по определенным правилам (о которых сказанониже) к каждой комбинации простого кода добавляют несколько(например 3) избыточных символа, которые служат для обнаружения иисправления возникающих ошибок. Таким образом получаюткорректирующий код, длиной n=7 символов. Число всех

кодовыхкомбинаций N=2n=128. И только 16 из них являются разрешенными. Такойкод кратко обозначают: (7,4) или (n,k).

Ошибки, возникающие в канале, принято характеризовать параметромq, называемом кратностью ошибки. Если при передаче комбинации 3разряда изменили свое значение (с 1 на 0 или наоборот), то говорят, чтопроизошла ошибка кратностью 3. Помехоустойчивые кодыхарактеризуются различной обнаруживающей и разрешающейспособностью. Это есть максимальная кратность qогарантированнообнаруживаемых ошибок и максимальная кратность qигарантированноисправляемых ошибок. Если q>qоили q>qи, то одни ошибки могут бытьобнаружены или исправлены а другие - нет.Значения qои qизависят от основного параметра избыточного кода -минимального кодового расстояния по Хэммингу - dmin.

Расстоянием по Хэммингу d(b1,b2) между двумякодовыми комбинациями b1 и b2 называется число позиций этихкомбинаций, в которых кодовые символы b1i и b2i не совпадают (i=1,2,...n).

Минимальным кодовым расстоянием dminдлязаданного кода называется минимальное расстояние по Хэммингу междувсеми парами разрешенных кодовых комбинаций.Пусть код обладает определенным dmin. Тогда он позволяетобнаруживать ошибку кратностью q<dmin. Таким образом, максимальнаякратность обнаруживаемых ошибок - qо=dmin-1. Тот же код позволяетисправлять ошибки кратностью q<dmin/2. Максимальная кратностьисправляемых ошибок:

qи=(dmin-1)/2 при нечетном dmin, qи=dmin/2-1 при четном dmin.

Все ошибки кратностью q<=qобудут гарантированно обнаружены, аошибки q<=qибудут гарантированно исправлены. Что же касается ошибок,превосходящих кратностью данные пороги, то одни из них могут бытьобнаружены или исправлены, а другие - нет.

Таким образом, для гарантированного обнаружения ошибки хотя бы в одномразряде dminкода должно быть не меньше 2; для гарантированногоисправления ошибки хотя бы в одном разряде dminдолжно быть не меньше3.

При избыточном кодировании ошибки обнаруживаются, еслипереданная разрешенная кодовая комбинация превращается в одну иззапрещенных, если же переданная комбинация превращается в другуюразрешенную, то ошибки не могут быть обнаружены. Для декодирования собнаружением ошибок множество B кодовых комбинаций разбивается наK+1 подмножество, из которых подмножества B1,B2,...BK содержат поодной разрешенной комбинации, а подмножество BK+1 все остальные(запрещенные) комбинации. Принятая кодовая комбинацияидентифицируется с одним из подмножеств и, таким образом,декодируется.

Задание для лабораторной работы

1.Построить простой код (k=4), и, пользуясь матрицей коэффициентовпостроить помехоустойчивый код (7,4).

2.Определить для данногокода минимальное кодовое расстояние dmin, обнаруживающуюспособность кода qо, исправляющую способность кода qи.Полученный код (7,4) а также его параметры занести в отчет.

3.Запустить программу моделирования. В соответствии с заданнымвариантом ввести кодовую комбинацию и затем ввести ошибку взаданный разряд. Нажать клавишу Enter (запустится программадекодирования). Записать в отчет результат - синдром. По видусиндрома сделать вывод - была ли ошибка и в каком она разряде.

4.Повторить п. 3, последовательно увеличивая кратность ошибок (q=2и q=3). Ошибочные разряды брать в соответствии с вариантомзадания.

5. По результатам выполнения пп. 3 и 4 сделать вывод обобнаруживающей и исправляющей способности кода (какие ошибкибыли обнаружены, какие - исправлены, а какие - нет). Проверить,соответствуют ли вычисленные вранееqои qирезультатамэксперимента пп. 3 и 4.

Варианты задания

Примечание: при q=1 необходимо ввести последовательно 3ошибочных кода; при q=2 и q=3 - по 2 кода.

Контрольные вопросы.

1. Какова задача помехоустойчивого кодирования?

2.Что такое линейный блочный код?

3.Дайте определение расстояния по Хэммингу для кодовых комбинаций.

4.Что такое параметры кода dmin, qо, qи, кратность ошибки q?

5.Каковы алгоритмы декодирования при обнаружении ошибок и исправлении ошибок?

6.Как с помощью порождающей матрицы G строится помехоустойчивый

код?

7.Что такое синдром? Как с его помощью определяются и исправляютсяошибки в принятой кодовой комбинации?

Ольга Яновна Родькина

ТЕОРИЯ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ И СИСТЕМ

Учебно-методическое пособие

по выполнению лабораторных работ для обучающихся по дисциплине

«Теория информационных процессов и систем» по направлению подготовки 09.03.02 Информационные системы

и технологии, без профиля

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Нижегородский государственный архитектурно-строительный университет» 603950, Нижний Новгород, ул. Ильинская, 65.

http://www.nngasu.ru, srec@nngasu.ru