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

Чтобы декодировать сверточный код, нужно найти последовательность входных битов, которая с наибольшей вероятностью породила наблюдаемую последовательность выходных битов (включая любые ошибки). Для небольших значений 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, в кабельных и спутниковых сетях, а также для исправления ошибок на CD, DVD и Blu-ray. Поскольку работа идет на базе m-битных символов, однобитные ошибки и m-битные пакеты ошибок обрабатываются одинаково — как одна символьная ошибка. При добавлении 2t избыточных символов код Рида — Соломона способен исправить до t ошибок в любом из переданных символов. Это означает, например, что код (255, 233) с 32 избыточными символами исправляет до 16 символьных ошибок. Так как символы могут быть последовательными, а размер их обычно составляет 8 бит, то возможно исправление пакетов ошибок в 128 битах. Еще лучше, если модель ошибок связана с удалением данных (например, царапина на компакт-диске, уничтожившая несколько символов). В таком случае возможно исправление до 2t ошибок.

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