В нашем примере задачу декодирования, то есть поиск допустимого кодового слова, наиболее похожего на полученное, можно выполнить простым осмотром. К сожалению, в более общем случае, когда в качестве кандидатов приходится оценивать все кодовые слова, это заняло бы очень много времени. Вместо этого разрабатываются практические коды, которые по определенным подсказкам ищут наиболее подходящее исходное кодовое слово.
Попробуем создать код, состоящий из
При заданном
Этот теоретический нижний предел может быть достигнут на практике с помощью метода Хэмминга (1950). В кодах Хэмминга биты кодового слова нумеруются последовательно слева направо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4, 8, 16 и т. д.), являются контрольными. Остальные биты (3, 5, 6, 7, 9, 10 и т. д.) заполняются
Расстояние этого кода равно 3, то есть он позволяет исправлять одиночные ошибки (или распознавать двойные). Причина такой сложной нумерации бит данных и контрольных бит становится очевидной, если рассмотреть процесс декодирования. Когда
прибывает кодовое слово, приемник повторяет вычисление контрольных бит, учитывая значения полученных контрольных бит. Их называют результатами проверки. Если контрольные биты правильные, то для четных сумм все результаты проверки должны быть равны нулю. В таком случае кодовое слово принимается как правильное.
Рис. 3.6. Пример кода Хэмминга (11,7), исправляющего однобитную ошибку
Если не все результаты проверки равны нулю, это означает, что обнаружена ошибка. Набор результатов проверки формирует синдром ошибки (error syndrome), с помощью которого выделяется и исправляется ошибка. На рис. 3.6 в канале произошла ошибка в одном бите. Результаты проверки равны 0, 1, 0 и 1 для
Кодовые расстояния полезны для понимания блочных кодов, а коды Хэмминга применяются в самокорректирующейся памяти. Однако в большинстве сетей используются более надежные коды. Второй тип кода, с которым мы познакомимся, называется сверточным кодом. Из всех рассмотренных в данной книге только он не относится к блочному типу. Кодировщик обрабатывает последовательность входных бит и генерирует последовательность выходных бит. В отличие от блочного кода, никакие ограничения на размер сообщения не накладываются, также не существует грани кодирования. Значение выходного бита зависит от значения текущего и предыдущих входных бит — если у кодировщика есть возможность использовать память. Число предыдущих бит, от которого зависит выход, называется длиной кодового ограничения для данного кода. Сверточные коды описываются в терминах кодовой нормы и длины кодового ограничения.
Сверточные коды широко применяются в развернутых сетях. Например, входят в мобильную телефонную систему GSM, спутниковые сети и сети 802.11. В качестве примера можно рассмотреть популярный сверточный код, показанный на рис. 3.7. Он называется сверточным кодом NASA с