n потенциальных кодовых слов используются. Более того, при r контрольных битов допустимыми считаются лишь 2m/2n или 1/2r кодовых слов, а не все возможные 2m. Именно разреженность данных в кодовой комбинации позволяет получателю распознавать и исправлять ошибки.
Способность блочного кода находить и исправлять ошибки зависит от расстояния Хэмминга. Чтобы гарантированно обнаружить d ошибок, необходим код с минимальным кодовым расстоянием, равным d + 1, поскольку d однобитовых ошибок не смогут превратить одну допустимую комбинацию в другую. Когда приемник встречает запрещенную кодовую комбинацию, он «понимает», что при передаче произошла ошибка. Аналогично для исправления d ошибок требуется код с минимальным кодовым расстоянием 2d + 1, так как в этом случае даже при d однобитных ошибок результат окажется ближе к исходному кодовому слову, чем к любому другому. Это означает, что исходную кодовую комбинацию можно однозначно определить, основываясь на предположении, что возникновение большего числа ошибок менее вероятно.
В качестве простейшего примера корректирующего кода рассмотрим код, в котором всего четыре допустимые комбинации:
0000000000, 0000011111, 1111100000 и 1111111111
В этом коде минимальное кодовое расстояние равно 5, а значит, он может исправлять двойные и обнаруживать четверные ошибки. Если принимающая сторона получит кодовое слово 0000000111, ожидая только однобитовые или двухбитовые ошибки, она «поймет», что оригинал должен быть равен 0000011111. Однако если тройная ошибка изменит 0000000000 на 0000000111, она будет исправлена неверно. Если же ожидаются все перечисленные ошибки, то их можно распознавать. Ни одна из полученных кодовых комбинаций не входит в список допустимых. Следовательно, произошла ошибка. Очевидно, что в данном примере невозможно одновременно исправлять двойные ошибки и распознавать четверные, потому что для этого полученное кодовое слово нужно будет интерпретировать двумя разными способами.
В нашем примере задачу декодирования, то есть поиск допустимого кодового слова, наиболее близкого к полученному, можно выполнить простым просмотром. К сожалению, в более общем случае, когда приходится оценивать все кодовые слова, это заняло бы очень много времени. Вместо этого разрабатываются практические коды, которые по определенным подсказкам ищут наиболее подходящее исходное кодовое слово.
Попробуем создать код, состоящий из m информационных и r контрольных битов, способный исправлять одиночные ошибки. Каждому из 2m допустимых сообщений будет соответствовать n недопустимых кодовых слов, с кодовым расстоянием 1. Их можно получить инвертированием каждого из n битов n-битного кодового слова. Таким образом, любому из 2m допустимых сообщений должны соответствовать n + 1 кодовых комбинаций. Поскольку общее количество возможных кодовых комбинаций равно 2n, то (n + 1)2m ≤ 2n. Так как n = m + r, получаем:
(m + r + 1) ≤ 2r (3.1)
При заданном m формула описывает нижний предел контрольных битов, необходимых для исправления одиночных ошибок.
Кроме того, этот теоретический нижний предел может быть достигнут с помощью метода Хэмминга (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.
Чтобы декодировать сверточный код, нужно найти последовательность входных битов, которая с наибольшей вероятностью породила наблюдаемую последовательность выходных битов (включая любые ошибки). Для небольших значений 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-битовых символов. Разумеется, математика здесь намного сложнее, поэтому мы используем аналогию.