Компьютерные сети. 6-е изд.

Кроме того, этот теоретический нижний предел может быть достигнут с помощью метода Хэмминга (Hamming, 1950). В кодах Хэмминга биты кодового слова нумеруются последовательно слева направо, начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4, 8, 16 и т.д.), являются контрольными. Остальные биты (3, 5, 6, 7, 9, 10 и т.д.) заполняются m битами данных. Такой шаблон для кода Хэмминга (11, 7) с 7 битами данных и 4 контрольными битами показан на илл. 3.6. Каждый контрольный бит обеспечивает сумму по модулю 2 или четность некоторой группы битов, включая себя самого. Один бит может входить в несколько вычислений контрольных битов. Чтобы определить, в какие группы контрольных сумм будет входить бит данных в k-й позиции, следует разложить k на степень двойки. Например, 11 = 8 + 2 + 1, а 29 = 16 + 8 + 4 + 1. Каждый бит проверяется только теми контрольными битами, номера которых входят в этот ряд разложения (например, 11-й бит проверяется битами 1, 2 и 8). В нашем примере контрольные биты вычисляются для проверки на четность суммы в сообщении, представляющем букву «A» в кодах ASCII.

Илл. 3.6. Пример кода Хэмминга (11, 7), исправляющего однобитную ошибку

Расстояние Хэмминга этого кода равно 3, то есть он позволяет исправлять одиночные ошибки (или распознавать двойные). Причина такой сложной нумерации битов данных и контрольных битов становится очевидной, если рассмотреть процесс декодирования. Когда приходит кодовое слово, приемник учитывает значения полученных контрольных битов и заново вычисляет их. Их называют результатами проверки. Если контрольные биты верны, то для четных сумм все результаты проверки должны быть равны нулю. В этом случае кодовое слово принимается как правильное.

Если не все результаты проверки равны нулю, это означает, что обнаружена ошибка. Набор результатов проверки формирует синдром ошибки (error syndrome), с помощью которого ошибка выявляется и исправляется. На илл. 3.6 в канале произошла ошибка в одном бите. Результаты проверки равны 0, 1, 0 и 1 для k = 8, 4, 2 и 1 соответственно. Таким образом, синдром равен 0101 или 4 + 1 = 5. Согласно схеме, пятый бит содержит ошибку. Поменяв его значение (а это может быть контрольный бит или бит данных) и отбросив контрольные биты, мы получим правильное сообщение: букву «A» в кодах ASCII.

Кодовые расстояния полезны для понимания блочных кодов, а коды Хэмминга применяются в физических модулях оперативной памяти RAM. Однако в большинстве сетей используются более надежные коды. Второй тип кода, с которым мы познакомимся, — сверточный код (convolutional code). Из всех кодов, представленных в данной книге, только он не относится к блочному типу. Кодировщик обрабатывает последовательность входных битов и генерирует последовательность выходных битов. В отличие от блочного кода, никакие ограничения на размер сообщения не накладываются, также не существует границы кода. Значение выходного бита зависит от значения текущего и предыдущих входных битов — если у кодировщика есть возможность использовать память. Число предыдущих битов, от которого зависит выход, называется длиной кодового ограничения (constraint length) для данного кода. Сверточные коды описываются с учетом кодовой нормы и длины кодового ограничения.

Сверточные коды широко применяются в существующих сетях, например, они входят в систему GSM, спутниковые сети и сети 802.11. В качестве примера можно рассмотреть популярный сверточный код, представленный на илл. 3.7. Он называется сверточным кодом NASA с r = 1/2 и k = 7. Впервые этот код был использован при подготовке полета космического корабля Voyager, запущенного в 1977 году. С тех пор он применяется повсюду, к примеру, в сетях 802.11.

Илл. 3.7. Двоичный сверточный код NASA, применяемый в сетях 802.11

На илл. 3.7 для каждого входного бита слева создается два выходных бита справа. Эти выходные биты получаются путем применения операции XOR к входному биту и внутреннему состоянию. Так как кодирование работает на уровне битов и использует линейные операции, это двоичный линейный сверточный код. Поскольку один входной бит создает два выходных бита, кодовая норма r равна 1/2. Этот код не систематический, так как входные биты никогда не передаются на выход напрямую без изменений.

Внутреннее состояние хранится в шести регистрах памяти. При поступлении на вход очередного бита значения в регистрах сдвигаются вправо. Например, если на вход подается последовательность 111, а в первоначальном состоянии в памяти только нули, то после подачи первого, второго и третьего бита оно будет меняться на 100000, 110000 и 111000 соответственно. На выходе получатся значения 11, затем 10 и затем 01. Чтобы полностью подавить первоначальное состояние регистров (тогда оно не будет влиять на результат), требуется 7 сдвигов. Таким образом, длина кодового ограничения для данного кода равна 7: k = 7.