Компьютерные сети. 6-е изд. - Эндрю Таненбаум Страница 80

Если не все результаты проверки равны нулю, это означает, что обнаружена ошибка. Набор результатов проверки формирует синдром ошибки (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.

Чтобы декодировать сверточный код, нужно найти последовательность входных битов, которая с наибольшей вероятностью породила наблюдаемую последовательность выходных битов (включая любые ошибки). Для небольших значений k это делается с помощью широко распространенного алгоритма, разработанного Витерби (Viterby), см. работу Форни (Forney, 1973). Алгоритм проходит по наблюдаемой последовательности, сохраняя для каждого шага и для каждого возможного внутреннего состояния входную последовательность, которая породила бы наблюдаемую последовательность с минимальным числом ошибок. Входная последовательность, которой соответствует минимальное число ошибок, и есть наиболее вероятное исходное сообщение.

Сверточные коды очень популярны на практике, так как в декодировании легко учесть неопределенность значения бита (0 или 1). Предположим, что –1 В соответствует логическому уровню 0, а +1 В — логическому уровню 1. Мы получили для двух битов значения 0,9 В и –0,1 В. Вместо того чтобы сразу определять соответствие: 1 для первого бита и 0 для второго, — можно принять 0,9 В за «очень вероятную единицу», а –0,1 В за «возможный ноль» и скорректировать всю последовательность. Для более надежного исправления ошибок к неопределенностям можно применять различные расширения алгоритма Витерби. Такой подход к обработке неопределенности значения битов называется декодированием с мягким принятием решений (soft-decision decoding). И наоборот, если мы решаем, какой бит равен нулю, а какой единице, до последующего исправления ошибок, такой метод называется декодированием с жестким принятием решений (hard-decision decoding).

Третий тип корректирующего кода, с которым мы познакомимся, называется кодом Рида — Соломона (Reed–Solomon code). Как и коды Хэмминга, коды Рида — Соломона относятся к линейным блочным кодам и часто являются систематическими. Но в отличие от кодов Хэмминга, которые применяются к отдельным битам, коды Рида — Соломона работают на группах из m-битовых символов. Разумеется, математика здесь намного сложнее, поэтому мы используем аналогию.

Коды Рида — Соломона основаны на том факте, что каждый многочлен n-й степени однозначно определяется n + 1 точками. Например, если линия задается формулой ax + b, то восстановить ее можно по двум точкам. Дополнительные точки, лежащие на той же линии, излишни, но они полезны для исправления ошибок. Предположим, что две точки данных представляют линию. Мы отправляем их по сети. Также мы передаем еще две контрольные точки, лежащие на той же линии. Если в значение одной из точек по пути закрадывается ошибка, то точки данных все равно можно восстановить, подогнав линию к полученным правильным точкам. Три точки окажутся на линии, а одна, ошибочная, будет лежать вне ее. Обнаружив правильное положение линии, мы исправим ошибку.

В действительности коды Рида — Соломона определяются как многочлены на конечных полях. Для m-битовых символов длина кодового слова составляет 2m – 1 символов. Очень часто выбирают значение m = 8, то есть одному символу соответствует один байт. Тогда длина кодового слова — 255 байт. Широко используется код (255, 233), он добавляет 22 дополнительных символа к 233 символам данных. Декодирование с исправлением ошибок выполняется при помощи алгоритма, разработанного Берлекэмпом и Мэсси (Berlekamp, Massey). Он эффективно осуществляет подгонку для кодов средней длины (Massey, 1969).

Коды Рида — Соломона широко применяются на практике благодаря эффективности в исправлении ошибок, особенно последовательных. Они используются в сетях DSL, в кабельных и спутниковых сетях, а также для исправления ошибок на