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

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

Полный декодер декодирует каждое принятое слово в ближайшее кодовее слово. Геометрически это представляется следующим образом: полный декодер разрезает промежуточные области на куски и присоединяет их к сферам так, что каждая точка попадает в ближайшую сферу. Обычно некоторые точки находятся на равных расстояниях от нескольких сфер; тогда одна из этих сфер произвольно объявляется ближайшей. Если происходит более t ошибок, то полный декодер часто декодирует неправильно, но бывают и случаи попадания в правильное кодовое слово. Полный декодер используется в тех случаях, когда лучше угадывать сообщение, чем вообще не иметь никакой его оценки.

Мы будем также рассматривать каналы, в которых кроме ошибок происходят и стирания. Это значит, что конструкцией приемника предусмотрено объявление символа стертым, если он получен ненадежно или если приемник распознал наличие интерференции или сбой. Такой канал имеет входной алфавит мощности q и выходной алфавит мощности + 1; дополнительный символ называется стиранием. Например, стирание символа 3 в сообщении 12345 приводит к слову 12-45. Это не следует путать с другой операцией, называемой выбрасыванием, которая дает 1245.

3 таких каналах могут использоваться коды, контролирующие ошибки. В случае когда минимальное расстояние кода равно d*, любая конфигурация из р стираний может быть восстановлена, если d* -(- 1. Далее, любая конфигурация из v ошибок и р стираний может быть декодирована при условии, что

d* 2v + 1 + р.

Для доказательства выбросим из всех кодовых слов те р компонент, в которых приемник произвел стирания. Это даст новый код, минимальное расстояние которого не меньше d* - р; следовательно, V ошибок могут быть исправлены при условии, что выполняется выписанное выше неравенство. Таким образом, можно восстановить укороченное кодовое слово с р стертыми компонентами. Наконец, так как d* > р + 1, существует только

1.5. ПРОСТЕЙШИЕ КОДЫ 23

одно кодовое слово, совпадающее с полученным в нестертых компонентах; следовательно, исходное кодовое слово может быть восстановлено.

1.5. ПРОСТЕЙШИЕ КОДЫ

Некоторые коды настолько просты, что их можно описать в самом начале.

Простые коды с проверкой на четность. Это высокоскоростные коды с плохими корректирующими характеристиками. К заданным k информационным битам дописывается {k + 1)-й бит так, чтобы полное число единиц в кодовом слове было четным ). Таким образом, например, для й = 4

0000--0000 0, 0 0 0 1 0 00 1 1, 00 1000 10 1, 001100110

и т. д. Этот код является + 1, й)-кодом или (п, п- 1)-кодом. Минимальное расстояние кода равно двум, и, следовательно, никакие ошибки не могут быть исправлены. Простой код с проверкой на четность используется для обнаружения (но не исправления) одной ошибки.

Простые коды с повторением. Это низкоскоростные коды с хорошими корректирующими характеристиками. Один заданный информационный символ повторяется п раз (обычно п нечетно). Таким образом,

0-00000, 1 1 1 1 1 1.

Это (п, 1)-код. Для него минимальное расстояние равно п, и при предположении, что большинство принятых битов совпадает с переданным информационным битом, может быть исправлено (п - 1)/2 ошибок.

Коды Хэмминга. Эти коды позволяют исправлять одну ошибку. Сейчас мы введем эти коды с помощью непосредственного описания. Для каждого т существует (2"-1, 2" - 1 -/п)-код Хэмминга. При больших т скорость кода близка к 1, но доля общего числа битов, которые могут быть искажены, очень мала. (7, 4)-код Хэмминга можно описать с помощью приведенной на рис. 1.4, а реализации. При заданных четырех информационных битах (tl, ta, tg, Q полагаем первые четыре бита кодового слова

В дальнейшем этот дополнительный бит назычаегся битом проверки на четность. - Прим. ред.

4-битовое слово ионных

Сумматор по мобулю 1

Проверка на 1Лгъ

Сумматор по мооулга 2

Проверка на /,3,4

Сумматор по мойулю I

Проверка на i,lz>

7-Битовое койовое слово

7- Битовое KoSoBoe слово

Сложение по мойулн) г

4-6umoBoe

слово

йанныл

Корректирующая логика

Сумматор по мойулю 2.

Ошибка utiu Pi

Сумматор 710 моЗулю г

Ошибка или

Сумматор ло мойулю 2.

Ошибка в ii.z.k или Pi

Рис. 1.4. Кодер/декодер для простого (7, 4)-кода Хэмминга. в - кодер; б - декодер.