Коды с выявлением ошибок

Лекция

Появление одиночной ошибки в одном из разрядов 4-разрядного двоичного кода может привести к неправильному, но допустимому кодовому набору. Если код такой, что появление любой одиночной ошибки превращает допус­тимый кодовый набор в недопустимый кодовый набор, то его называют ко­дом с выявлением (одиночной) кодовой ошибки. Два таких кода приведены в табл. 1.5.

Выявление ошибки в любом из этих кодов проводится проверкой на четность. Эта проверка основана на присоединении к каждому набору дополни­тельного разряда с тем, чтобы количество единиц в любом кодовом наборе данного кода было нечетным или четным. Более целесообразно число единиц в кодовом наборе с выявлением одиночной ошибки выбирать нечетным. То­гда любое кодовое представление, в том числе и для нуля, будет иметь хотя бы одну 1. Это даст возможность отличить полное отсутствие информации от передачи нуля в том случае, если 1 отражает наличие электрического сигна­ла, а 0 — его отсутствие.

Таблица 1-. Коды с выявлением ошибки

Десятичное число

Двоично-десятичный код с проверкой на четность

Код 2 из 5"

р

Десятичное число

Двоично-десятичный код с проверкой на четность

Код "2 из 5"

Дополнительный разряд р называется контрольным разрядом четности. Код, который состоит из всех 10 возможных комбинаций 5-разрядных кодовых наборов с двумя единицами, называется кодом "2 из 5".

При построении корректирующих кодов часто прибегают к геометрической моде­ли. Допустим, есть алфавит, который состоит из трех символов. Из них можно со­ставить следующие комбинации: 000, 001, 010, 011, 100, 101, 110, 111. В трехмерном пространстве на осях найдем точки с координатами кода (рис. 1.1). Помеха может исказить сигнал, т. е. вместо 0 появится 1 или наоборот. Очевидно, что если кодовые комбинации отличаются одна от одной длиной ребра d = 1, то помеха переведет один сигнал в другой и обнаружить ошибку в этом случае нельзя. Ее можно обнаружить, если кодовые комбинации отстоят одна от одной на два ребра, т. е. 000, 011, 101, 110. Для исправления необходимо, чтобы комбинации отлича­лись на три единицы: 000, 111. Пространство, представленное на рис. 1.1, назы­вается пространством Хемминга, а величина d — расстоянием по Хеммингу или минимальным кодовым расстоянием. Например, минимальное кодовое расстояние для кодов из табл. 1.5 равняется двум. Очевидно, что это расстояние всегда целое число, равное числу разрядов, в которых отличаются двоичные числа, соответст­вующие точкам в пространстве Хемминга. В общем случае пространство Хеммин­га имеет n координат и изображается n-мерным кубом.

Для построения n-разрядного кода с выявлением ошибок нужно не больше половины от 2" возможных комбинаций разрядов. Выбор кодовых наборов проводится таким образом, чтобы при преобразовании одного допустимого кодового набора в другой допустимый кодовый набор по крайней мере два разряда имели противоположные значения.

Рис. 1.1. Геометрическая интерпретация корректирующих кодов

Лекция

Дата добавления: 2015-07-08