5.4. НЕКОТОРЫЕ РАЗНОВИДНОСТИ СИСТЕМАТИЧЕСКИХ КОДОВ

В поисках более простой техники кодирования и декодирования был найден подкласс линейных систематических двоичных кодов, называемых циклическими и нашедшими широкое применение в технике связи. Название этих кодов связано с тем, что каждый вектор, получаемый из кодового путем циклической перестановки его символов, также принадлежит коду. Примером циклического кода является код (7, 4), определяемый матрицами (5.18) и (5.19). Так, например, циклические перестановки вектора 1000101 являются также кодовыми векторами

Теория циклических кодов основана на изоморфизме пространства двоичных -последовательностей и пространства полиномов степени не выше внда

где коэффициенты а принимают значения 0 и 1. Множество таких полиномов образует линейное пространство, если определить сложение полиномов как суммирование коэффициентов при соответствующих степенях х по модулю 2. Переменная х является символической, и ее значение иикак не влияет на свойства пространства.

Легко видеть, что между полиномами (5.21) и -последовательностями имеется изоморфизм, причем полиному (5.21) соответствует -последовательность

Любой полином степени который делит без остатка двучлен может служить порождающим полиномом циклического -кода, где . В этот код входят те полиномы (5.21), которые без остатка делятся на . В частности, для кода (7, 4) порождающим полиномом является

Среди циклических кодов особое значение имеет класс кодов, предложенных Боузом и Рой-Чоудхури и независимо от них Хоквингемом. Коды Боуза — Чоудхури — Хоквингема (обозначаемые сокращением БЧХ) отличаются специальным выбором порождающего полинома, вследствие чего для них существуют сравнительно просто реализуемые процедуры декодирования. Доказано, что для

любой пары натуральных чисел можно построить двоичный код исправляющий любую конфигурацию ошибок с кратностью, меньшей или равной А.

Относительно простой является процедура мажоритарного декодирования, применимая для некоторого класса двоичных линейных, в том числе циклических кодов. Основана она на том, что в этих кодах каждый информационный символ можно несколькими способами выразить через другие символы кодовой комбинации. Если, для некоторого символа эти способы проверки дают неодинаковые результаты (одни дают результат а другие — «1», что может быть только в случае ошибочного приема), то окончательное решение по каждому из информационных символов принимается по мажоритарному принципу, т. е. по большинству. Мажоритарное декодирование осуществляется относительно просто, посредством регистров сдвига.

Примером кода, допускающего мажоритарное декодирование, является код двойственный рассмотренному ранее коду Для него матрица (5.19) является образующей. Ее удобнее записать, переставив столбцы, так:

Символ в этом коде связан с другими символами следующими соотношениями: Обозначим принятые после демодуляции символы Если бы они все были приняты верно, то для переданного символа были бы верны следующие четыре равенства (проверки):

Каждый из символов принятого блока входит только в одну из этих проверок для Код, для которого выполняется это условие, называется кодом с разделенными проверками.

Предположим, что один из символов блока принят с ошибкой. Тогда три из проверок (5.23) дадут одно (правильное) значение а одна проверка, в которой участвует ошибочный символ, даст другое, ошибочное значение. Принимая решение по большинству, получим правильное значение Если бы ошибок было три или больше, то мажоритарное решение могло бы дать ошибочный результат. При двух ошибочно принятых символах может получиться одинаковое (верное) значение для во всех проверках (например; при ошибочно принятых либо в двух проверках а в двух других (например, при ошибочно принятых В последнем случае можно только констатировать наличие ошибок.

После принятия решения о символе аналогичным образом проверяются значения Поскольку рассматриваемый код

(7, 3) — циклический, соответствующие проверки получаются из (5.23) циклической перестановкой.

Мощные коды (т. е. коды с длинными блоками и большим кодовым расстоянием при сравнительно простой процедуре декодирования можно строить, объединяя несколько коротких кодов. Так строится, например, итеративный код из двух линейных систематических кодов Вначале сообщение кодируется кодом 1-й ступени Пусть блоков кода 1-й ступени записаны в виде строк матрицы. Ее столбцы содержат по символов, которые будем считать информационными для кода 2-й ступени и допишем к ним проверочных символов. В результате получится блок (матрица щупъ), содержащий символов, из которых являются информационными:

Процесс построения кода можно продолжить в измерении и т. д.

При декодировании каждого блока 1-й ступени производятся обнаружение и исправление ошибок. После того как принят весь двумерный блок, осуществляется вновь исправление ошибок и стираний, но уже по столбцам, кодом 2-й ступени, причем приходится исправлять только те ошибки, которые не были исправлены (или были ложно «исправлены») кодом 1-й ступени. Легко убедиться, что минимальное кодовое расстояние для двумерного итеративного кода где соответственно минимальные кодовые расстояния для кодов 1 и 2-й ступеней.

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

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

Все операции с матрицами и полиномами над конечным полем, составляющие процедуру кодирования и декодирования, осуществляются средствами вычислительной техники. Для коротких систематических кодов они довольно просты и выполняются с помощью триггеров, объединенных в цепочки (регистры сдвига) и логические схемы. С увеличением длины кода эти операции усложняются. Хотя благодаря особой алгебраической структуре кодов БЧХ сложность растет медленно, тем не менее, при использовании эффективных длинных кодов приходится применять в качестве декодера электронную вычислительную машину специализированную или универсальную.

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

где информационный символ, принимающий значение 0 или 1 в соответствии с передаваемым сообщением, проверочный символ, определяемый уравнёнием

причем сложение производится по модулю 2.

Цепной код, содержащий на символов информационных, часто обозначают в частности, код (5.24) обозначают (1/2). Ошибка при приеме одного информационного символа приводит к тому, что (5.25) не выполняется для двух проверочных символов: Поэтому алгоритм декодирования можно выразить так: если (5.25) не выполняется для двух соседних проверочных символов, то следует изменить находящийся между ними информационный символ на противоположный.

Цепной код (5.24) позволяет исправлять ошибки, расположенные на любом месте, при условии, что между двумя любыми ошибочно принятыми имеются, но крайней мере, три правильно принятых символа. Это легко показать, исследуя алгоритмы проверки (5.25).

В последние годы начали находить применение предложенные довольно давно сверточные коды, представляющие другую разновидность рекуррентных кодов. Для них разработаны специальные алгоритмы так называемого последовательного декодирования, позволяющие эффективно исправлять ошибки при относительно небольшой сложности. Описание этих кодов и алгоритмов [4] выходит за рамки данного учебника.

Правило декодирования по наименьшему расстоянию, как уже отмечалось, обеспечивает максимальную верность декодирования только в симметричном канале без памяти. Для несимметричных каналов и каналов с памятью (с которыми очень часто приходится встречаться на практике) оптимальными могут оказаться другие правила. Так, в каналах с памятью вероятность возникновения ошибок кратностью зависит от того, как расположены разряды с ошибочными символами. Смежные ошибки в этих каналах могут быть более вероятны, чем ошибки, разделенные большим числом правильно принятых символов. Для таких каналов с группированием ошибок разработаны коды и методы декодирования с обнаружением или исправлением «пачек» ошибок, т. е. ошибок большой кратности, расположенных в пределах относительно небольшого числа разрядов. В частности, пачки ошибок хорошо обнаруживаются некоторыми циклическими кодами.

Для каналов с группированием ошибок часто применяют метод перемежения символов, или декорреляции ошибок. Он заключается в том, что символы, входящие в одну кодовую комбинацию, передаются не непосредственно друг за другом, а перемежаются символами других кодовых комбинаций. Если интервал между символами, входящими в одну комбинацию, сделать длиннее «памяти» (интервала корреляции) канала, то в пределах комбинации группирования ошибок не будет и можно декодировать, как в канале без памяти. Простой пример представляет дискретный канал, образованный при передаче сигналов с ОФМ. Как было указано в § 4.5, в таком канале ошибки имеют тенденцию сдваиваться, так что вероятность появления двух смежных ошибок больше, чем вероятность появления двух несмежных ошибок, и даже больше, чем вероятность одиночной ошибки. Если в таком канале объединить в один блок символы, а в другой блок символы, то в этих блоках ошибки будут независимы (если нет других причин, вызывающих память) и декодирование по минимуму кодового расстояния будет оптимальным.

Очень часто «память» канала оказывается очень длинной и приходится расставлять символы, связанные кодом, на большие расстояния. Это сравнительно просто достигается при использовании цепного кода (5.24), если его несколько видоизменить. С этой целью символы, входящие в уравнение (5.25), расставляются на большое расстояние и проверочные символы связаны не с соседними информационными, а с удаленными на некоторый шаг В этом случае вместо (5.25) имеем

Величина выбирается в соответствии с длиной памяти канала.

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

могут гарантированно только обнаруживать одиночные ошибки. Однако они используются обычно в несимметричных каналах, в которых вероятность перехода значительно больше вероятности перехода или наоборот. В таких каналах очень маловероятно, чтобы в одном блоке были переходы обоих видов, и поэтому почти все ошибки приводят к изменению веса блока и, следовательно, обнаруживаются. В прежние годы эти коды широко использовались (а иногда используются и сейчас) в системах с управляющей обратной связью (см. § 5.6).