Сигнал о некоторых понятиях кибернетики - Полетаев И.А.
Скачать (прямая ссылка):
Самокорректирующиеся коды
Понижение вероятности ошибок при передаче достигается разумным использованием избыточности при кодировании сообщений. Чем выше уровень шумов в канале, тем больше вероятность ошибки при передаче и тем больше лишних символов нужно применить для того, чтобы устранить ошибки. Именно этим ценна высокая избыточность человеческого языка. Отдельные опечатки в тексте делают слова бессмысленными, т. е. такими, которые ничему не соответствуют и не применяются. Это позволяет без труда обнаружить их и исправить.
То же свойство используется при составлении помехоустойчивых или, как их еще называют, самокорректирующихся кодов. Простейшим способом защиты от помех является многократное повторение передачи. При достаточном числе повторений правильный вариант сигнала будет приниматься несколько чаще, чем любой из искаженных. Есть,
* Мы опускаем рассмотрение вопроса о количестве информации, содержащейся в сообщении, которое закодировано в непрерывном алфавите. Исчерпывающее изложение вопроса читатель найдет у А. Н. Колмогорова [5].
89
Рис. 4.2. Ненадежность принятого сигнала в зависимости от энтропин на входе канала.
однако, и более тонкие методы составления самокорректирующихся кодов. Рассмотрим примеры.
Пусть мы передаем сигнал в-алфавите (0,1), причем символы следуют группами, по N символов в группе. Вероятность появления в группе более одной ошибки достаточно мала и ею можно пренебречь. Иначе говоря, в группе может появиться только одна ошибка (0 вместо
1 или 1 вместо 0), но почти никогда не появится две или больше таких ошибок.
Припишем к каждой группе из N символов еще один, который не несет информации, а служит контрольным. Будем выбирать его для каждой группы так, чтобы вся группа изЛ^+1 символов при суммировании нулей и единиц, в нее входящих, давала бы, скажем, четное число. На приемном конце канала все группы проверяются на четность суммы и та группа, в которой ошибочно изменен один символ, немедленно будет опознана как ошибочная. Мы получили код, обнаруживающий одиночную ошибку. Его недостаточно для того, чтобы указать место ошибки в группе и, следовательно, исправить ее.
Можно составить код и для исправления ошибки, только для этого придется увеличить избыточность и приписать дополнительные символы. Пусть в предыдущем примере Л; = 4; припишем к каждой группе из 4 символов еще 3 контрольных. Пусть символы, стоящие на 3, 5, 6 и 7-.м местах, используются для передачи информации, а символы, стоящие на 1, 2 и 4-м местах — для контроля. Их мы выбираем по следующим правилам: составляем три вспомогательные суммы, в каждую из которых входит один контрольный символ, выбранный так, чтобы сделать её четной:
выбор Хх: ХзА'й —|— А'у —[— X, = у четное; выбор Х2: + Х6 +-^7 +-^2 = Р четное; (4.25)
выбор Х3: Х5-\- Х6-\~Х7-\-ХА — а четное.
Группы из 7 символов передаются по каналу с искажением. На приемном конце канала вычисляются суммы а, р и у. Четные обозначаются нулем, нечетные—единицей. Двоичное число а р у дает номер неверно переданного символа в данной группе.
Пусть, например, Лз=0, Xs=l, Х6 = 1, Х7=0. Тогда Хх = 1, Х2=1, Х*=0. Передается группа 1100110. Пусть в третьем символе произошла ошибка и группа принята в следующем виде: 1110110. Вычислив по принятой груп-90
пе величины контрольных сумм а=0, р=1, у=1, получим число 011 *, которое в двоичном начертании равно трем. Это индекс ошибочно принятого символа. Ошибка в любом другом символе была бы исправлена подобным же образом.
В самокорректирующемся коде не все слова «имеют смысл», т. е. являются допущенными к употреблению. Проверка принятого сигнала на наличие ошибок сводится к опознаванию недопущенных слов и к определению, из какого допущенного слова вероятнее всего получилось в результате искажения данное недопущенное. Это, по-види-мому, тем легче сделать, чем большим числом символов отличаются друг от друга допущенные слова.
Пример кода, который мы приводили выше, носит название кода типа Голей — Хемминга. Коды этого типа применимы, когда вероятность ошибки -невелика. При больших вероятностях ошибки, когда в слове из N символов достаточно часто появляется более одной ошибки, код Хемминга оставляет без изменений слова, в которых нет ошибок, корректирует одиночные ошибки, не исправляет слова с четным числом ошибок и может внести одну дополнительную ошибку, если число ошибок больше одной и нечетное.
В таких случаях можно применять более сложные коды, например с повторным применением кодирования. Так, например, после исправления одиночных ошибок избыточные контрольные символы отбрасываются и из оставшихся символов составляются новые группы, состоящие из информационных и контрольных символов, и т.д. В результате достигается возможность передать некоторую информацию почти без ошибок, несмотря на значительную вероятность ошибок в отдельном символе, правда ценой значительной задержки во времени. Задержка при кодировании—общее явление для всех сложных кодов.
