ПРИЛОЖЕНИЕ Б. ПОРОЖДАЮЩИЕ МНОГОЧЛЕНЫ СВЕРТОЧНЫХ КОДОВ

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

Б.1. Декодирование Витерби

В табл. перечислены оптимальные сверточные коды с небольшой длиной кодового ограничения для значений [91]. Порождающие многочлены даются в восьмеричной форме. Для каждого кода приводятся

Таблица Б.1. (см. скан) Порождающие многочлены (в восьмеричной форме) и спектры наилучших кодов с

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

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

Таблица Б.3. (см. скан) Порождающие многочлены (в восьмеричной форме) и спектры выколотых кодов с имеющих только два различных порождающих многочлена

Таблица Б.4. (см. скан) Порождающие многочлены (в восьмеричной форме) и спектры выколотых кодов с имеющих только два различных порождающих многочлена

При построении этих таблиц принято соглашение, по которому выходные символы, соответствующие первым двум порождающим многочленам, передаются по одному и тому же ребру, а выходные символы, соответствующие каждому из следующих порождающих многочленов, передаются последовательно по различным ребрам. В табл. приведены порождающие многочлены, которые можно использовать для построения кодов или 3/4 в зависимости от способа отсчета. Эти множества порождающих многочленов могут служить для построения декодера с переменной скоростью (1/2, 2/3 или 3/4), сложность которого лишь незначительно превышает сложность декодера с В литературе можно найти и другие коды. Ларсен (113) привел список порождающих многочленов кодов с и 1/4, имеющих максимальное свободное расстояние для Для более высоких скоростей порождающие многочлены кодов с максимальным свободным расстоянием при содержатся в работе Пааске [114]. Обычно эти коды примерно на лучше выколотых кодов, однако они не обладают достоинствами выколотых кодов по реализации.

Таблица Б.5. (см. скан) Наборы из двух различных порождающих многочленов, задающих хорошие коды с и 3/4

Оптимальные коды для ортогональных сигналов не совпадают с кодами из предыдущих таблиц, поскольку расстояние Хемминга уже не является адекватным критерием оптимальности. В табл. содержатся порождающие многочлены и спектры некоторых оптимальных кодов, а в табл. Б.7 - порождающие многочлены некоторых близких к оптимальным кодов и 8) [115].

Таблица Б.6. Порождающие многочлены (в восьмеричной форме) и спектры некоторых оптимальных кодов для ортогональных сигналов

Таблица Б.7. (см. скан) Близкие к оптимальным порождающие многочлены (в восьмеричной форме) для ортогональных сигналов

Таблица Б.8. (см. скан) Наилучшие коды с для нечетных значений

Заметим, что одним из кодов в табл. является -дуальный код [106, 116]. При его использовании двоичные символы поступают в декодер группами по три символа (или в виде одного -ичного символа). Значение для этого кода равно одному 8 ичному символу. Для каждого поступающего в кодер символа

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

Б.2. Декодирование с табличным поиском

Критерием оптимальности для декодера с табличным поиском является величина равная минимальному расстоянию между нулевым путем и путем длины из нижней половины кодового дерева. Если, однако, для данного значения имеется несколько кодов с одинаковым значением среди них нужно выбрать код с минимальным числом путей веса Этот критерий был использован Буссгангом [69] для нахождения кодов из табл. Б.8. В этой таблице приведен только один порождающий многочлен, поскольку рассматриваемые коды являются систематическими.

Б.3. Пороговое декодирование

Порождающие многочлены для самоортогональных сверточных кодов легко построить исходя из разностных треугольников, как описано в подразд. 7.1.3.1. Подробные таблицы таких разностных треугольников были составлены Робинсоном и Бернстайном [71] и Клибером [72]. Наиболее интересные разностные треугольники приведены в табл. Используя эти треугольники, можно построить коды с и коды с Приведено значение I для кода с Соответствующее значение для кода с есть

Таблица Б.9. (см. скан) Разностные треугольники, порождающие канонический самоортогональный код

Таблица Б.10. (см. скан) Разностные треугольники для

Таблица Б.11. (см. скан) Разностные треугольники для

(см. скан)

Таблица Б. 16. (см. скан) Коды, построенные методом проб и ошибок при

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

Другим интересным классом кодов являются так называемые ПО-коды, найденные Месси [13] и приведенные в табл. Эти коды достигают такого же значения при меньшей длине кодового ограничения, чем самоортогональные коды. Их использование описано в подразд. 7.1.3.1.

Б.4. Последовательное декодирование

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

Таблица Б. 17. (см. скан) Хорошие сверточные коды с большой длиной кодового ограничения

Первым в этой таблице приведен систематический код с найденный Форни [78]. Поскольку код является систематическим, достаточно, конечно, указать только один порождающий многочлен Для построения этого кода был взят известный хороший короткий код, и к его порождающему многочлену последовательно добавлялись дополнительные члены таким образом, чтобы кодовое расстояние быстро росло. На каждом шаге вычислялось кодовое расстояние построенного кода, для чего использовалась некоторая модификация алгоритма Фано В этом методе используется метрика Хемминга, начало работы декодера соответствует верхней половине кодового дерева, а переход в его нижнюю половину запрещен. Заметим, что при использовании приращения метрики, равного —1 при каждом несовпадении, и 0 при каждом совпадении, и расстояния между порогами, равного 1, для каждой глубины в дереве находится первый путь данной глубины с минимальным весом. Кодовое расстояние кода равно минимальному весу при Построенный порождающий многочлен является вложенным. Это означает, что порождающий многочлен можно оборвать в любом месте (оставляя левую часть) и полученный код по-прежнему будет хорошим.

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

Другим полезным несистематическим кодом является так называемый быстрый код, найденный Месси и Костелло [79]. Такие коды исправляют один из недостатков, присущих несистематическим кодам: трудность восстановления информационной последовательности по принятой последовательности. Вероятность ошибки восстановленной оценки лишь вдвое превышает вероятность ошибки в канале («коэффициент усиления ошибок» равен 2). Заметим, что, с другой стороны, спектр этого кода хуже спектра кода Бала-Джелинека.

Код, найденный Лейлендом и Лашбо имеет большое свободное расстояние при При аппаратном моделировании этот код привел к вероятности необнаруженной ошибки двоичного символа, равной примерно при (использовалось мягкое решение с квантованием на восемь уровней). В [118] показано, что почти такие же характеристики имеет код Месси и Костелло из [79]).

Иоханнессон [119] построил ряд кодов, имеющих оптимальный профиль расстояний Для каждого из этих кодой оптимизировался рост пути минимальной длины для каждой глубины Это свойство оказывается полезным при последовательном декодировании, поскольку облегчает раннее отбрасывание декодером плохих путей. Это уменьшает объем вычислений, производимых декодером. По вложенным порождающим многочленам, найденным Кейном [73], строятся коды с 2/3 или 3/4. Аналогично с помощью строятся проверочные последовательности по при а с помощью проверочная последовательность при Поскольку эти коды являются систематическими, использование несистематических кодов может привести к сущестевнно большему значению для кодов с большими скоростями при данном значении