8. КОДЫ - АНТИПОДЫ

Мы выяснили, что при построении помехо­устойчивых кодов не обойтись без дополнительных симво­лов, которые должны быть присоединены к кодовым словам безызбыточного кода. Эти символы уже не несут информа-1 ции о передаваемых сообщениях, но могут дать информа-1 цию о происшедших при передаче ошибках. Иными словами, I их назначение — контролировать правильность передачи! кодового слова. Вводимые дополнительные символы так и| называют контрольными (или проверочными).

Самый незатейливый способ, позволяющий исправлять! ошибки, состоит в том, что каждый информационный сим-1 вол повторяется несколько раз, скажем, символ 0 заменяет-1 ся блоком из п нулей, а символ 1 — блоком из п единиц.I При декодировании п-буквенного блока, содержащего,! быть может, ошибочные символы, решение принимается! «большинством голосов». Если в принятом блоке нулей боль-1 ше, чем единиц, то он декодируется как 00...О (т. е. счи-1 тается, что был послан нулевой симеол), в противном слу-| чае — как 11...1. Такое правило декодирования позволяет! Еерно восстановить посланные символы, если помехи в ка-1 нале искажают менее половины символов в каждом пере-1 даваемом блоке. Если длину блока п выбрать достаточно! большой, то мы практически обезопасим себя от возможных I ошибок, однако передача сообщений будет идти черепашь- I ими темпами. По этой причине указанный код (его называют! кодом с повторением) не имеет большого практического! значения, однако правило его декодирования («голосова-И ние») содержит в себе весьма полезную идею, которая с ус-Я нехом применяется в других, практически более интересных! помехоустойчивых кодах. Об этом речь пойдет дальше (см.И §§ 17, 18), а сейчас постараемся выяснить, на что мы можем рассчитывать при минимальной избыточности, когда к каж­дому кодовому слову добавляется всего лишь один прове­рочный символ. Пусть а&г. . ,ап — двоичное кодовое сло­во. Выберем проверочный символ ап+1 с таким расчетом, чтобы на его значение одинаково влиял каждый из символов данного слова. Это естественное требование будет выпол­нено, если, например, положить ап+1=а,+а2+. . .+а„ (той 2). Тогда проверочный символ ап+1 будет равен нулю, если в кодовом слове а^а. . ,а„ содержится четное число единиц, и единице — в противном случае. Например, присоединяя таким образом проверочный символ к слову 1010, получаем слово 10100, а из слова 1110 получим слово 11101.

Нетрудно видеть, что все удлиненные кодовые слова . .а„ап+1 содержат четное число единиц, т. е.

 

 

Допустим, что в процессе передачи в удлиненно к довсе слово а,а2. . ,апап+1 вкралась одна ошибка (или даже любое нечетное число ошибок). Тогда в искаженном слове а[<х'2. . .а'па,1+1 число единиц станет нечетным. Это и служит указанием на искажение в переда :е слова. В конечном итоге все сводится к проверке соотношения (1) для си шолов принятого слова, что легко сделает простейшее вычисли­тельное устройство — сумматор по модулю 2. Итак, прави­ло приема следующее: если равенство (1) выполняется, счи­таем, что сообщение передано правильно, в противном слу­чае отмечаем, что произошла ошибка и, когда это возможно, требуем повторить передачу кодового слова. Понятно, что иначе ошибки не исправить. Например, если принято «не­правильное слово» 11100, то одинаково возможно, что было послано любое из кодовых слов:

01100, 10100, 11000, 11110, 11101.

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

Еще большая неприятность подстерегает нас в случае двойной ошибки или вообще четного числа ошибок. Ведь тогда соотношение (1) не нарушится, и мы воспримем иска­женное слово как верное.Описанный код, который называют кодом с общей про­веркой на четность, позволяет, следовательно, обнаружитьлюбое нечетное число ошибок, но «пропускает» искажения, если число ошибок четно.

Код с повторением и код с общей проверкой на чет­ность — до некоторой степени антиподы. Возможности первого исправлять ошибки теоретически безграничны, но он крайне «медлителен». Второй очень быстр (всего один дополнительный символ), но зачастую «легкомыслен». В ре­альных каналах связи, как правило, приходится считаться с возможностью ошибок более чем в одном символе, поэтому в чистом виде код с общей проверкой на четность приме­няется крайне редко. Гораздо чаще применяют коды с не­сколькими проверочными символами (и, соответственно, с несколькими проверками на четность). Они позволяют не только обнаруживать, но и исправлять ошибки, и не только одиночные, но и кратные, и притом делать это гораздо эффективнее, чем упоминавшийся нами код с повторением. Это можно проиллюстрировать на одном красноречивом и в то же время простом примере.

Рассмотрим множество всех двоичных слов длины 9 (с их помощью можно закодировать 2В=512 сообщений). Расположим символы каждого слова ага2. . .ав в квадратной таблице следующим образом:

 

 

и аналогично для остальных строк и столбцов. Заметим, что

 

ОК каждой строке и к каждому столбцу этой таблицы до­бавим еще по одному (проверочному) символу с таким рас­четом, чтобы в строках и столбцах получившейся таблицы (таблица 15) было четное число единиц.

При этом, например, для первой строки и первого столб­ца будут выполняться проверочные соотношения:

Зти «маленькие хитрости» позволяют, оказывается, испра­вить любую одиночную ошибку, возникшую в процессе передачи, а сверх того и обнаружить любую двойную ошибку. В самом деле, если произошла одна ошибка, то на­рушаются проверочные соотношения ровно для одной стро­ки и ровно для одного столбца, как раз той строки и того столбца, на пересечении которых стоит ошибочный символ. Если же произошла двойная ошибка, то это приводит к на­рушению проверок на четность либо в двух строках, либо в двух столбцах, либо сразу в двух строках и двух столб­цах. По этим признакам мы и обнаруживаем двойную ошибку. (Однако исправить ее мы не можем — почему?) можность поместить в таблице 15 еще один проверочный символ р„ равный

 

Например, слову 011010001 отвечает следующая таблица:

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

кратности (в трех, четырех и т. д. символах). Например/ обнаруживаются тройные ошибки в символах аь ая или в символах аи ав. А вот тройная ошибка в символах а,, а2, а5 не может быть обнаружена, она будет воспринята как одиночная.

Продемонстрированное в этом примере сочетание про­верок на четность по строкам и столбцам допускает широ­кие обобщения. О простейшем из них говорится в дополне­нии 3.

Задачи и дополнения

1. Для разобранного в данном параграфе примера най­ти число необнаруживаемых тройных ошибок. Какую часть онн состав­ляют от общего числа тройных ошибок?

Кодовые слова в примере иа стр. 42 содержат 9 информацион­ных символов и 7 проверочных, так что общая длина кодового слова равна 16. Такого числа символов достаточно, чтобы исправлять любые одиночные и обнаруживать любые двойные ошибки. Чтобы достичь того же эффекта для кода с повторением, нужно каждый информацион­ный символ повторить 4 раза, так что общая длина кодового слова будет равна 36. Сравнение явно не в пользу кода с повторением. Справедли­вости ради надо все же отметить, что код с повторением обладает по сравнению с использованным в примере кодом некоторыми преимущест­вами в смысле обнаружения ошибок более высокой кратности. Предла­гаем читателю найти, например, долю необнаруживаемых тройных оши­бок для указанного кода с повторением и сравнить ответ с результатом задачи I. Интересно найти также долю исправимых (!) тройных ошибок для этого кода.

Пример из данного параграфа обобщается следующим образом (смотри также дополнение 12 к § 11). Пусть каждое сообщение кодиру­ется двоичным словом длины тп. Расположим все символы в прямоуголь­ную таблицу (матрицу) с т строками и п столбцами:

 

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