Повышение помехоустойчивости передаваемой информации

Рассмотрим вопросы помехоустойчивости для равномерного кода. Для любого алфавита может быть составлена таблица кодовых комбинаций. При передаче сообщения по каналу связи каждая кодовая комбинация несет полученную информацию. Однако из-за внешних воздействий на канал связи (электромагнитные наводки, электрические разряды и т. д.) и внутренних сбоев в работе аппаратуры передачи появляются помехи, искажающие кодовые комбинации. В одной кодовой комбинации может быть искажено несколько сигналов, однако вероятность двойного (и более) искажения одной кодовой комбинации чрезвычайно мала, поэтому часто отстройка от таких помех не осуществляется. Будем считать, что возможно лишь однократное искажение кодовой комбинации (получение 0 вместо 1 или, наоборот, только в одном из разрядов слова).

Характерной особенностью рассмотренных кодов является их безызбыточность, т. е. максимальное использование комбинационной возможности из L сигналов (1 или 0). Однако помехоустойчивость их низка, так как любое искажение какого-либо сигнала приводит к образованию другой кодовой комбинации, также имеющейся в таблице кодов данного алфавита. Мощным средством повышения помехоустойчивости систем передачи информации является применение корректирующих кодов, использующих свойство избыточности, т. е. передачи дополнительных сигналов, не несущих полезной информации, но позволяющих обнаружить и исправить ошибки от помех. Хотя при этом снижается производительность приемопередающих систем, помехоустойчивость повышается.

Из общего числа возможных комбинации N= 2^L, где L — число символов в кодовой комбинации (длина равномерного кода), для построения кода используются только N' комбинаций N' < N, называемых разрешенными. Остальные N — /V'комбинации называются запрещенными и не используются. Получение на приемном конце запрещенной кодовой комбинации свидетельствует об искажении переданного сигнала, и, следовательно, факт искажения обнаруживается. Такие коды называются кодами с обнаружением ошибок.

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

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

Для оценки корректирующей способности кодов вводится понятие кодового расстояния (расстояние Хэмминга), соответствующего числу элементов, на которое отличаются друг от друга две кодовые комбинации. Кодовое расстояние определяется суммированием по модулю 2 (суммированием в двоичной системе счисления без переноса в старший разряд) рассматриваемых кодовых комбинаций. Например, для двух слов 1011 и 0110 кодовое расстояние равно 3, так как.

1011 © 0110= 1101.

В таблице кодовых комбинаций кодовые расстояния могут быть различными. Например, дтя равномерного кода алфавита а,…, а₅ (см. табл. 2) они имеют значения от 1 до 3. Корректирующие возможности кода характеризуются минимальным кодовым расстоянием D. Для безызбыточных кодов D = 1.

Принципы повышения помехоустойчивости кода поясним при помощи /.-мерного куба, в котором каждой вершине ставится в соответствие кодовая комбинация, а длина ребра равна единице. Кратчайший путь по ребрам от вершины к вершине характеризует кодовое расстояние. На рис. 15 дана геометрическая модель для трехразрядных кодов (L = 3). Все восемь вершин образуют непомехоустойчивый код, при этом D = 1. Обнаружение ошибки возможно лишь в кодах с D > 2.

Рис. 15. Геометрическая интерпретация трехразрядного кода.

Для трехразрядного кодирования из восьми вершин можно взять лишь четыре, т. е. четыре элемента алфавита закодировать:

а,…а₂…а,…а₄

000… 011…101…ПО На рис. 15 соответствующие вершины куба выделены белым цветом. Легко видеть, что здесь в каждой кодовой комбинации имеется четное число единиц. Если на приемном конце обнаруживается нечетное число единиц, то переданное сообщение об элементе алфавита ошибочно, и его следует повторить. Можно взять за основу другую группу кодов с нечетным числом единиц, тогда четное количество единиц будет свидетельствовать о помехе.

При кодировании восьми элементов алфавита для обеспечения D = 2 длина кодовой комбинации должна быть увеличена с трех до четырех:

а,…а₂…а,…а₄…а₅…а₆…а₇…a_s

1001…1010…ООН…ЦОО…0101…ОНО…ЦП… 0000.

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

Для исправления ошибки необходимо обеспечить D = 3, что приводит к еще большей избыточности. Например, для трехразрядного кода с D = 3 возможны лишь две кодовые комбинации с двумя элементами алфавита (табл. 2).

Таблица 2.

Трехразрядный код с возможностью исправления ошибок

Получение на приемном конце трех нулей или кодовой комбинации с двумя нулями и одной единицей свидетельствует о передаче элемента а, получение комбинаций с тремя или двумя единицами свидетельствует о передаче а. Для кодирования четырех элементов алфавита с D = 3 длина каждой кодовой комбинации должна быть не менее 5, например: а, -> 0, а₂— 10 011, а,-> 11 100, а₄-1 111.

При построении системы передачи информации с исправлением ошибок наибольшее распространение получили коды Хэмминга. Опишем способы кодирования для алфавита, содержащего не более 16 элементов. В этом случае при D = 1 длина равномерного кода без обнаружения и исправления ошибки L = 4. Обозначим символы четырехразрядного кода через a, b, с, d. Соответствующие кодовые комбинации для части алфавита приведены в табл. 3.

При формировании кода Хэмминга символы а, b, с, d будем называть информационными (несущими полезную информацию) и дополним их контрольными символами Х[, х₂, х₃ так, чтобы кодовая комбинация имела вид [ХХ₂&х_гЬ с d.

Таблица 3.

Комбинации четырехразрядного алфавита

Для заданных значений a, b, с, d контрольные символы х_ьх₂, х₃должны быть такими, чтобы в табл. 4 сумма у,• по модулю 2 всех элементов каждой из трех строк была равной 0 (все у, = 0).

Таблица 4.

Определение контрольных сумм для кода Хэмминга

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

что эквивалентно дополнению до четности кодовых комбинаций abd, acd и bed.

При получении кодовой комбинации без искажения в канале связи все контрольные суммы у, = 0. Искажение кодовой комбинации приведет к получению у, * 0. Элементы у, могут быть составлены в двоичное число Z — УзУ2У[]> указывающее на номер разряда, в котором произошло искажение информации, и на необходимость инверсии сигнала в этом разряде. Это следует из заполнения приведенной выше таблицы.

Искажение первого по счету сигнала х_] отразится лишь в контрольной сумме у, в результате получится число z = 001 ₍₂₎ = 1 _(|0). Здесь индексы (2) и (10) показывают, в какой системе счисления (двоичной или десятичной) сделана соответствующая запись. Искажение второго сигнала х₂ вызывает появление числа z = 010 ₍₂₎ = 2_(|0), искажение третьего сигнала а отразится в контрольных суммах у, и у₂, что приводит к образованию числа z = 011 ₍₂₎ = 3_(Ю). Искажение, например, в последнем разряде элемента с/ кодовой комбинации отразится во всех контрольных суммаху₍, у₂, у₃, в результате получится число Z = 111 ₍2) = 7₍ю), указывающее на ошибку в седьмом разряде. В табл. 5 приведены коды Хэмминга для элементов алфавита.

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

Характерной особенностью кодов является следующее: циклический сдвиг любой кодовой комбинации на один шаг приводит к получению другой комбинации, принадлежащей данному коду.

Таблица 5.

Коды Хэмминга для четрыхразрядного алфавита

Пусть имеются информационные символы а, b, с, d, из которых, как было отмечено выше, можно образовать 16 кодовых комбинаций (см. табл. 4). Контрольные символы х_ь х_ъ х₃ приписываются справа и получается в общем виде запись семиразрядной кодовой комбинации F=[abc dx_x x₂xj. Для формирования контрольных символов используется некоторое вспомогательное четырехразрядное двоичное число Р (по количеству информационных символов), например, Р_х = 1011 ₍₂₎ = 11 ₍₁₀₎ или Р₂ = 1101 ₍₂₎ = 13₍₁₀₎. Здесь индексы в скобках, как и ранее, показывают, в какой системе счисления записано число. Как видно, Р_х и Р₂ соответствуют простым числам в десятичной системе счисления, и в теории кодирования они называются образующими, так как делятся без остатка только на себя и на единицу. При кодировании пятиразрядных комбинаций используются следующие образующие числа:

Вернемся к обсуждению семиразрядного циклического кода F. Всего при длине слова L = 7 может быть 128 комбинаций. Из них выберем лишь те, которые делятся без остатка на образующее число. При этом под делением в двоичной системе будем понимать процедуру, которая выполняется с использованием арифметического действия сложения 0 по модулю 2, т. е. без взаимодействия соседних разрядов. Представим число Fкак.

Теперь можно сформулировать следующий вопрос. Чему должно быть равно число /?, чтобы число /'делилось на образующее число Р без остатка? Нетрудно видеть, что число R равно остатку от деления С на Р. Например, в десятичном исчислении к числу С = 39₍₁₀₎ для Р = 11 ₍₁₀₎ необходимо прибавить 5, чтобы получить число 44, дающее при делении нулевой остаток.

Поскольку все 16 кодовых слов С, могут быть получены как комбинация чисел С, = 1 000, С₂ = 10 000, С₄ = 100 000, С₈ = 1 000 000, то достаточно найти остатки только для них: R_x = 011, R₂ = 110, R₄ = 111, Л₈ = 101. Процесс получения чисел R_x и R₂ показан на рис. 16.

Рис. 16. Процесс получения остатков отделения.

Как видим, деление в каждом цикле проводится до тех пор, пока не получится текущий остаток, число разрядов в котором меньше или равно 3 (по количеству контрольных символов). Таким образом, определяются четыре образующие кодовые комбинации: Я, = 1 011, F₂ = 10 110, /^ = 100 111, F_g= 1 101 001. Все остальные получаются как комбинации указанных чисел, например: Я₃ = F_t + F₂ — 11 101, F_n = Я, + Я₄ + Я₈ = = 1 101 001.

На приемном конце канала связи кодовая комбинация Fподвергается контролю. Если при делении на образующее число Р остаток равен нулю, то первые четыре информационных символа а, b, с, d без исправления используются по назначению. Если же Я, * 0, необходимо внести коррекцию в переданное двоичное слово.

Ошибка при передаче сообщения приводит к получению некоторой кодовой комбинации Я, вместо F,. Например, если вместо F= 1 101 001 имеем Н= 1 001 001, то остаток R= 111 при делении Яна Р= 1011 свидетельствует о том, что F * Я. Для выявления и исправления ошибки выполняются действия по следующему алгоритму:

• 1) подсчитывается вес tv, исходного остатка /?," показывающий количество единиц в /?₀ (в рассматриваемом примере w₀ = 3). Если w₀ = 1, то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию;
• 2) если w₀ >1,то производят циклический сдвиг числа Я на один символ влево и полученную комбинацию (число) снова делят на Р. Если при этом новый вес остатка w, = 1, то остаток складывают с комбинацией и сдвигают в обратную сторону на 1 символ. В результате получается исправленная кодовая комбинация F. Если же снова w₀ > 1, то повторно осуществляют сдвиг влево и деление на Р до получения остатка весом 1. Остаток складывается с последней циклической кодовой комбинацией, результат сдвигается вправо на соответствующее число циклов.

Продемонстрируем работу алгоритма на предложенном примере, в котором Я₀ = 1 001 001, остаток R₀ = 111 и вес и>₀ = 3. Сдвигаем Я_ц на один разряд влево (единица старшего разряда переходит в младший разряд), т. е. имеем Я, = 10 011. Деление на Р дает остаток Л, = 101, w, = 2. Сдвигаем Я, влево и получаем Я₂ = 100 110. Теперь деление на Р дает остаток R₂ = 001 с весом w₂= 1. Складываем Я₂ и Л₂, получаем число 100 111, циклический сдвиг которого вправо на 2 разряда дает искомую кодовую комбинацию F = 11 001 001. Последнее число делится на Я без остатка.

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

Для обеспечения высокой достоверности передачи информации в некоторых случаях используют принцип «переспроса». В том случае, если полученная информация признается недостоверной, на передающую сторону по специальному обратному каналу связи направляется сигнал запроса на повторную передачу информации. При этом вся передаваемая информация равномерно разделяется на отдельные блоки. Очевидно, для работы с блоками необходима на обоих концах передачи специальная буферная память для временной фиксации информации в блоке.

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

Большую роль в современных АСУ играют вычислительные сети, по которым осуществляется межмашинный обмен информацией. Присоединение П ВК к каналам связи выполняется через модемы (модулятор-демодулятор) — устройства передачи данных по выделенным или коммутируемым каналам связи. Информационный обмен между взаимодействующими объектами определяется так называемыми протоколами (программами, реализующими заданный алгоритм), предусматривающими как управление форматами сообщений, способом формирования контрольной информации, потоком команд, так и действия, необходимые в случае обнаружения ошибок.