Главная > Помехоустойчивое кодирование > Теория кодирования
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.5. Самоортогональные коды

5.5.1. Определение самоортогонального кода

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

Определение 5.2. (Месси.) Сверточный код, для которого при любом система проверок, контролирующая

шумовой символ воздействующий на информационный символ в момент времени О, ортогональна относительно называется самоортогональным кодом.

Все самоортогональные коды допускают полную ортогонализацию, т. е. с помощью мажоритарного декодирования могут быть исправлены все ошибки, исправление которых гарантируется минимальным расстоянием. Коды этого типа первым исследовал Месси [2]. Метод построения таких кодов с высокой корректирующей способностью, а именно кодов, имеющих при заданном небольшое кодовое ограничение был предложен Робинсоном и Бернстейном [3]. Декодирование самоортогональных кодов осуществляется крайне просто, и это связано с тем, что соответствующим образом выбранные символы синдромов ортогональны относительно и при декодировании нет необходимости проводить линейное преобразование символов синдромов для получения составных проверок. Следующая теорема дает необходимые и достаточные условия того, что код является самоортогональным.

Теорема 5.3. (Месси.) Код является самоортогональным тогда и только тогда, когда совокупность символов синдромов, контролирующих каждый информационный шумовой символ ортогональна относительно

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

5.5.2. Простой пример

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

Пример 5.6. Рассмотрим самоортогональный код со скоростью передачи задаваемый порождающими многочленами

Проверочная матрица этого кода для интервала времени

имеет следующий вид:

Можно построить следующие три составные проверки, ортогональные относительно

и три составные проверки, ортогональные относительно

Очевидно, что для этого кода

Как можно видеть из формул (5.42) и (5.43), символами синдромов, ортогональными относительно являются

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

Пусть показатели степеней неизвестного с ненулевыми коэффициентами порождающего многочлена. Рассмотрим совокупность

разностей этих показателей степеней. А именно для введенных выше многочленов и рассмотрим совокупности чисел Совокупность представляет собой совокупность значений индексов и информационных шумовых символов входящих в проверки (5.42) и отличных от Точно так же совокупность совпадает с совокупностью значений индексов и информационных шумовых символов входящих в проверки (5.73) и отличных от Следовательно, необходимым условием ортогональности систем проверок (5.42) и (5.43) относительно соответственно и является отсутствие в каждой из указанных выше совокупностей одинаковых чисел. Кроме того, если обозначить совокупности через то целые числа оказываются значениями индексов и шумовых символов входящих в формулы (5.42). Аналогично целые числа, получающиеся в результате вычитания из каждого числа каждого числа являются значениями индексов и шумовых символов входящих в (5.43). Следовательно, другим необходимым условием ортогональности систем проверок (5.42) и (5.43) относительно соответственно является также отсутствие одинаковых чисел и в последних указанных совокупностях. В действительности, как легко видеть, эти условия являются и достаточными, а именно если совокупности целых чисел удовлетворяют указанным выше условиям, то задаваемый ими код является самоортогональным.

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

имеющем ненулевых коэффициентов, т. е. пусть

Множество из разностей целых чисел будем называть совокупностью разностей порождающего многочлена

Теорема 5.4. (Маси и Робинсон.) Сверточные коды с или являются самоортогональными тогда и только тогда, когда совокупности разностей их порождающих многочленов не пересекаются, а кроме того, ни одна из них не содержит одно и то же число дважды.

Доказательство. Рассмотрим случай когда существует только один синдром Пусть показатели степеней неизвестного с ненулевыми коэффициентами порождающих многочленов Согласно формулам (5.11) и (5.13), символами синдрома, контролирующими шумовой символ являются символы, появляющиеся в моменты времени Индексы символов информационных шумовых последовательностей, контролируемых этими символами синдромов, могут быть найдены с помощью следующей таблицы:

(см. скан)

Эти символы синдромов ортогональны относительно тогда и только тогда, когда выполняются следующие два условия:

1) Никакой индекс, отличный от и, не входит сразу в две строки второго столбца таблицы. Действительно, если при некоторых имеет место равенство и то а это означает, что некоторое число входит в совокупность разностей по крайней мере дважды.

2) Никакой индекс не входит сразу в две строки третьего столбца таблицы. Действительно, если при некоторых имеет место равенство то и совокупности разностей содержат одно и то же целое число.

Это доказывает теорему в случае Аналогично теорема доказывается и в случае

Из этой теоремы непосредственно следует, что после определения по — 1 порождающих многочленов, для которых все совокупности разностей состоят из различных чисел и не пересекаются, сразу получаем самоортогональный код.

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

Простое совершенное разностное множество порядка представляет собой совокупность целых чисел каждая из разностей которой сравнима по модулю с одним из чисел . Сингер [37] доказал существование простых совершенных разностных множеств любого порядка являющегося степенью простого числа, и более того, указал метод их построения. Например, как показано ниже, при совокупность целых чисел является простым совершенным разностным множеством:

<< Предыдущий параграф Следующий параграф >>
Оглавление