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

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

Самый незатейливый способ, позволяющий исправлять ошибки, состоит в том, что каждый информационный сим- иол поьторяется несколько раз, скажем, символ 0 заменяет­ся блоком из п нулей, а символ 1 — блоком из п единиц. При декодировании /г-буквенного блока, содержащего, быть может, ошибочные символы, решение принимается «большинством голосов». Если в принятом блоке нулей боль­ше, чем единиц, то он декодируется как 00...О (т. е. счи­тается, что был послан нулевой симеол), в противном слу­чае— как 11...1. Такое правило декодирования позволяет верно восстановить посланные символы, ссли помехи в ка­нале искажают менее половины символов в каждом пере­даваемом блоке. Если длину блока п выбрать достаточно большой, то мы практически обезопасим себя от возможных ошибок, однако передача сообщений будет идти черепашь­ими темпами. По этой причине указанный код (его называют кодом с повторением) не имеет большого практического значения, однако правило его декодирования («голосова­ние») содержит в себе весьма полезную идею, которая с ус­пехом применяется в других, практически более интересных помехоустойчивых кодах. Об этом речь дойдет дальше (см.§§ 17, 18), а сейчас постараемся выяснить, на что мы можем рассчитывать при минимальной избыточности, когда к каж­дому кодовому слову добавляется всего лишь один прове­рочный символ. Пусть ai<x₂. . .ct_n — двоичное кодовое сло­во. Выберем проверочный символ а„₊, с таким расчетом, чтобы на его значение одинаково влиял каждый из символов данного слова. Это естественное требование будет выпол­нено, если, например, положить a_n+i=ai+a₂+. . .+а_п (mod 2). Тогда проверочный символ a_n+i будет равен нулю, если в кодовом слове а_уа₂. . ,а_п содержится четное число единиц, и единице — в противном случае. Например, присоединяя таким образом проверочный символ к слову 1010, получаем слово 10100, а из слова 1110 получим слово 11101.

Нетрудно видеть, что все удлиненные кодовые слова а_га₂. . .a,_ta_{n +} i содержат четное число единиц, т. е.

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

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

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

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

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

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

Таблица 14

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

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

Обе эти суммы равны 0, если в слове c^ag. . .a₉ четное число единиц, в противном случае обе они равны 1. Это дает возможность поместить в таблице 15 еще один проверочный символ равный

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

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

Таблица 16

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

Добавим к сказанному, что данный код позволяет обна­руживать многие, хотя и не все, ошибки более высокой кратности (в трех, четырех и т. д. символах). Например/ обнаруживаются тройные ошибки в символах а*, а₂, а₃ или в символах а_ь а₂, а₆. А вот тройная ошибка в символах а_ь «2, ^не может быть обнаружена, она будет воспринята как одиночная.

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

Предлагаю ознакомиться с аналогичными статьями: