17. ГОЛОСОВАНИЕ

Хотя в процедуре принятия решения большин­ством голосов нет для нас ничего необычного, может все же показаться неожиданным, что метод голосования исполь­зуется при декодировании помехоустойчивых кодов. Отча­сти мы уже коснулись этого вопроса в § 8, когда рассказы­вали о коде с повторением,— решение о посланном симво­ле принималось там как раз большинством голосов. Теперь же мы покажем, как применяется голосование в случае произвольного линейного кода.

Обратимся сначала к примеру. Здесь нам поможет не­однократно упоминавшийся ранее (7,3)-код, получающий­ся из (7,4)-кода Хемминга добавлением общей проверки на рртнпгть. Р.го пповепочная мятпина имеет вил:

 

 

Удобнее, однако, рассмотреть эквивалентный циклический код с порождающим многочленом и с проверочной матрицей

 

 

Эта матрица получена способом, указанным в дополнение 9 к § 11. В том, что коды с проверочными матрицами Н и Ну действительно эквивалентны, читатель может убедить- ел самостоятельно.Пусть принято некоторое слово а0 а2 а3 а4 се5 ав, со­держащее, быть может, ошибочные символы. Для каждо­го символа а,- будем в отдельности решать, верен он или нет, используя те соотношения, которыми этот символ свя­зан с остальными. Начнем с символа а0 и выпишем некото­рые содержащие его проверки. Первой строке матрицы Нг отвечает проверочное соотношение а0+а!+а3=0, сумме первой, второй и третьей строк — соотношение а0+а4+ -1-а,,=0. а сумме пеовой. втопой и четвептой стоок — соотношение

 

Итак, имеем:

 

 

 

 

 

 

Если ошибки при передаче отсутствовали, то в приня­том слове будет выполняться каждое из соотношений (1)в а правые их части дадут верное значение для а0. Соотноше­ния (1) для символа а0 выбраны с таким расчетом, что вся­кий другой символ входит в правую часть ровно одной про­верки. Поэтому если лишь один из них ошибочен, то толь­ко в одном из соотношений (1) будет нарушено равенство. Учитывая это, можно предложить следующее правило для определения верного значения символа а0: если среди зна­чений а1+а8, а4+аь, а2-Ьас, а0 большинство составляют нули, то полагаем, что нуль и есть верное значение для а0, если же большинство из них — единицы, то верным значением для а0 считаем единицу. Такое голосование га­рантирует верное решение, если принятое слово содержит не более одной ошибки. Возможно и равенство голосов (на­пример, в случае двойной ошибки), и в этом случае прихо­дится довольствоваться ее обнаружением.

Аналогичные проверки могут быть составлены и для других символов. Например, для имеем соотношения:

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

Анализируя указанным способом каждый символ при­нятого слова, мы правильно восстановим посланное кодо­вое слово, если произошло не более одной ошибки, и обнаружим любую двойную ошибку. Тем самым полно­стью используются корректирующие способности дан­ного кода — ведь его кодовое расстояние равно 4.

 

 

Разобранный нами метод исправления и обнаружения ошибок называют мажоритарным декодированием (т. е. декодированием по принципу большинства). Применим он тогда, когда — как в нашем примере — для каждого сим­вола а,- существует система проверок обладающая тем свойством, что в правую часть каждой проверки входят символы, отличные от а,у, и всякий такой символ входит не более чем в одну проверку. Такая систе­ма проверок называется ортогональной (или разделенной). Если число проверок, входящих в каждую ортогональную систему, не меньше 5, то путем голосования могут быть ис­правлены любые I ошибок, где /<(5+1)/2. В самом деле, ошибка в одном символе влияет в силу ортогональности не более чем на одну проверку, следовательно, среди значе­ний символа осу, которые даются всеми соотношениями (2), неправильными могут оказаться не более I, т. е. не более половины значений. Тогда, сравнивая значения правых частей проверок, а также значение самого символа ау-, мы по большинству голосов определяем верное значение этого символа. Если же (при нечетном 5) ^=(5+1)/2, то имеет место равенство голосов, ошибка при этом хотя и об­наруживается, но не исправляется.

Случай, когда число 5 проверок в каждой ортогональной системе на единицу меньше кодового расстояния й, т. е. когда 8=с1—1, является в известном смысле идеальным. В этом случае голосование позволяет, как и в рассмотренном примере, полностью реализовать корректирующие свойст­ва кода. Код, для каждого символа которого существует система из (с1—1) ортогональных проверок, называется пол­ностью ортогонализуемым.

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

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

Вот как устроена принципиальная схема мажоритарно­го декодирования для (7,3)-кода, упомянутого выше (рис. 24, а).

В этой схеме М — мажоритарный элемент, осуществ­ляющий голосование, К — переключатель, находящийся в положении 0 во время приема сообщения и в положении 1 при его декодировании. Рис. 24, а соответствует моменту, когда сообщение полностью поступило в запоминающий ре­гистр и ключ К переводится в положение 1. Начинается де­кодирование. На первом его шаге (первый такт) на вход мажоритарного элемента подаются значения сс0, с^+йд, а2+ + ае, а4+а3. На выходе его появляется символ а,', являю­щийся итогом голосования. В следующем такте происходит сдвиг сообщения в регистре, а символ ссэ поступает в по­следнюю ячейку памяти. Этому моменту соответствует рис. 24, б.Теперь уже голосование осуществляется по значениям «1, а2+а4, а3+ао.            и в результате получается значение а[ следующего символа сообщения. Дальнейшие так­ты работы схемы совершенно аналогичны. Если произошло не более одной ошибки, то последовательность (а„, а[,. . . . . ., а'в) и есть верное кодовое слово.

Как мы видим, в схеме используется только информа­ция о принятом слове; никакой дополнительной информации не требуется. А это очень важно, потому что именно необ­ходимость хранения большого объема данных служит ос­новным препятствием для применения некоторых методов декодирования (например, синдромного декодирования).

Еще одно немаловажное достоинство голосования по сравнению с другими методами декодирования заключается в том, что этот метод зачастую позволяет исправлять или обнаруживать многие ошибки, кратность которых превы­шает (й—1)/2.

 

 

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

1. Доказать, что код из примера § 8 с проверками на четность по строкам и по столбцам является полностью оргогонализуе- мым, составив для каждого из символов систему из трех ортогональных пповегюк (наппимег). поовевки

 

образуют требуемую систему для символа а^.

Проверить, что (7,4)-код Хемминга не является полностью ор- тогонализуемым, показав, что для символа ол не существует пары орто­гональных проверок.

Будет ли полностью ортогонализуемым расширенный (8,4)-код Хемминга?

Решить те же вопросы, что и в задаче 2, для произвольного дво­ичного кода Хемминга и его расширенного варианта.

Построить систему ортогональных проверок и мажоритарный декодер для троичного циклического (13,6)-кода с порождающим мно­гочленом