Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

ЗАНЯТИЕ № 9 (суббота)

Итоговый контроль: экзамен

2 этап: Устное собеседование по билету.

3 этап: Проверка практических навыков и умений.

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

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

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

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

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

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

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

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