Сверточные коды очень популярны на практике, так как в декодировании легко учесть неопределенность значения бита (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 ошибок.

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

Наконец, рассмотрим код LDPC (Low-Density Parity Check — код с малой плотностью проверок на четность). Коды LDPC — это линейные блочные коды, изобретенные Робертом Галлагером и описанные в его докторской диссертации (Gallager, 1962). О ней быстро забыли, как и о большинстве других диссертаций. Однако в 1995 году, когда вычислительные мощности сделали огромный скачок вперед, представленный в ней код был изобретен заново.

В коде LDPC каждый выходной бит формируется из некоторого подмножества входных битов. Это приводит нас к матричному представлению кода с низкой плотностью единиц — отсюда и название. Полученные кодовые слова декодируются алгоритмом аппроксимации, который итеративно ищет наилучшее приближение, составленное из полученных данных, пока не получает допустимое кодовое слово. Так происходит устранение ошибок.

Коды LDPC удобно применять для блоков большого размера. Они превосходно справляются с ошибками — лучше, чем многие другие коды (включая те, с которыми мы уже познакомились). По этой причине коды LDPC активно добавляются в новые протоколы. Они являются частью стандарта цифрового телевидения, сетей Ethernet 10 Гбит/с, ЛЭП, а также последней версии 802.11. Очевидно, что эти коды обязательно будут использоваться и в новых сетях, которые еще находятся на стадии разработки.

3.2.2. Коды для обнаружения ошибок

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

Мы рассмотрим три кода для обнаружения ошибок. Все они относятся к линейным систематическим блочным кодам: