автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Характеристики и алгоритмы декодирования сверточных кодов в системах связи

На правах рукописи

Кудряшов Борис Давидович

Характеристики и алгоритмы декодирования сверточных кодов в системах связи

05.13.01 - Системный анализ, управление и обработка информации 05.13 13 - Телекоммуникационные системы и компьютерные сети

Диссертация в виде доклада на соискание ученой степени доктора технических наук

Москва 2004

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения»

Официальные оппоненты:

Доктор технических наук профессор Зяблов В. В. Доктор технических наук профессор Габидулин Э. М. Доктор физико-математических наук профессор Дьячков А. Г.

Ведущая организация:

Санкт-Петербургский институт информатики и автоматизации РАН

Защита состоится ^ ^ 2004 г. на заседании диссертационного совета Д.002.077.01 Института проблем передачи информации Российской академии наук, по адресу: 127994, Москва, ГСП-4, Большой Каретный, 19

С диссертацией в виде научного доклада можно ознакомиться в библиотеке Института проблем передачи информации РАН.

Диссертация в виде научного доклада разослана

Ученый секретарь диссертационного совета Д.002.077.01 доктор физико-математических наук

И.И. Цитович

/

4912Г

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

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

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

В разделе 3 сформулирован алгоритм списочного декодирования сверточных кодов и приведен анализ его характеристик.

Метод случайных кодов эффективен при анализе потенциальной помехоустойчивости классов кодов. При исследовании характеристик конкретных систем связи на смену этому методу приходит техника описания моделей каналов и систем с помощью цепей Маркова и функций цепей Маркова. Некоторые результаты по построению и анализу этих моделей приведены в разделе 4.

Разделы 5 и 6 связаны с исследованиями последних лет в области теории представления сверточных и блоковых кодов с помощью решеток. Практическое значение такого представления в большой степени связано с возможностью применения алгоритма Витербн для декодирования решетчатых кодов по максимуму правдоподобия в каналах с мягкими решениями. В разделе 5 строятся сверточные кодов с заданной сложностью декодирования. Далее в разделе 6 дается обзор результатов по построению блоковых кодов, имеющих решетчатую структуру аналогичную структуре сверточных кодов и, следовательно, допускающих эффективное декодирование в каналах с мягкими решениями. Наконец, в последнем разделе работы приведен алгоритм анализа и декодирования сверточных кодов более эффективный, чем алгоритм Витерби. Этот алгоритм получил название BEAST (двусторонний эффективный алгоритм поиска по дереву). Применение этого метода дало возможность построить новые блоковые и сверточные коды, найти

эффективные решетчатые представления многих известных блоковых кодов и тем самым упростить их декодирование.

Результаты исследований опубликованы в 90 научных работах, среди которых статьи в журналах «Проблемы передачи информации» (10 статей), «Радиотехника» (3 статьи), IEEE Transactions on Information Theory (7 статей).

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

Помимо этого, материалы работы обсуждались на семинарах в ГУАП, ИППИ, ЛЭИС, НТОРЭС им. Попова, в фирме IBM, США, в институте математики и информатики Болгарской Академии Наук, в университетах г. Лунд и г. Линчопинг, Швеция Получены авторские свидетельства и патенты, опубликованы методические материалы для обучения студентов информационных специальностей.

Работа в большей части выполнена на кафедре информационных систем в Государственном университете аэрокосмического приборостроения (ГУАП), г. С.-Петербург. Некоторые результаты последних лет получены в результате сотрудничества с Техническим университетом (ЛТУ) г. Лунд, (Швеция).

Некоторые из приводимых в докладе результатов получены в результате совместной работы с коллегами. Так, например, исследование широковещательных каналов было выполнено совместно с Г. Ш. Полтыревым, работы по моделям каналов с памятью вначале выполнялись совместно с В. Д. Колесником и затем были продолжены с И.Е. Бочаровой. Соавтором списочного декодирования является В.Б. Балакирский. Спектры сигнально-кодовых конструкций на основе решетчатых кодов были вычислены в совместной работе с А.Н.Трофимовым. Результаты в области построения блоковых кодов из сверточных были опубликованы в совместной работе с Т. Г. Захаровой. Последующие теоретические результаты в этой области, а также алгоритм BEAST разрабатывались совместно с Бочаровой И. Е. и шведскими коллегами Р. Йоханнессоном, П. Сталом, М. Хандлери, М. Лончар. Считаю своим приятным долгом выразить искреннюю признательность моим коллегам и соавторам за увлекательное и плодотворное сотрудничество.

Введение

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

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

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

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

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

• асимптотические оценки достижимой вероятности ошибки в системах с обратной связью при различных ограничениях на сложность декодирования;

• асимптотические оценки вероятности ошибки и пар вычислительных скоростей для широковещательных каналов связи;

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

• верхние границы сложности решетчатого представления блоковых кодов и сложности их декодирования по максимуму правдоподобия;

• верхние границы сложности декодирования циклически усеченных сверточных кодов;

• нижние границы сложности решетчатого представления блоковых кодов.

Разработаны следующие методики и способы анализа сверточных кодов и методов передачи информации:

• формулы для вычисления списочного расстояния кодов;

• методика вычисления минимального расстояния и спектров сигнально-кодовых конструкций на основе решетчатых кодов;

• методика построения моделей каналов связи на основе функций цепей Маркова;

• алгоритмы быстрого компьютерного поиска сверточных кодов с заданной сложностью декодирования;

• алгоритм BEAST для вычисления свободного расстояния и спектральных характеристик сверточных кодов;

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

Решены следующие задачи, связанные с построением кодов и методов их декодирования:

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

• найдены эффективные решетчатые представления для большого числа блоковых кодов;

• построены новые блоковые квазициклические и линейные коды, минимальное расстояние которых превышает минимальное расстояние лучших ранее известных кодов из этих классов, причем некоторые из вновь найденных кодов имеют лучшие характеристики, чем все известные ранее лучшие блоковые коды, в том числе нелинейные;

• разработан алгоритм списочного декодирования сверточных кодов;

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

1. Сверточные коды в каналах с обратной связью

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

Из классической работы А.Витерби (1967 г.) известно, что при кодировании в отсутствие обратной связи асимптотические соотношения между сложностью декодирования по максимуму правдоподобия и вероятностью ошибки для сверточных кодов существенно лучше, чем для блоковых, причем особенно значительный выигрыш имеет место при скорости кодов близкой к пропускной способности канала. В 1986 г. Д.Форни были установлены обменные соотношения между вероятностью ошибки и вероятностью стирания для блоковых кодов. На основе этих соотношений выведена асимптотическая граница вероятности ошибки как функции средней скорости передачи при передаче с автоматическим переспросом (или с решающей обратной связью). Естественным развитием этой работы было бы

применение результатов Форни к сверточным кодам. Однако непосредственный перенос результатов на сверточные коды оказался невозможным.

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

Решение данной задачи было найдено в работе [5]. Результаты этой работы были затем улучшены в [19]. Чтобы сформулировать результаты этих работ, нам понадобятся следующие обозначения.

Рассматривается дискретный стационарный канал без памяти (ДКБП), задаваемый входным алфавитом X = {*}, выходным алфавитом У = {у} и переходными вероятностями {р(у | х),х е Х,у е У}.

Мы начнем с введения аддитивной метрики для декодирования блоковых кодов. Применительно к блоковым кодам эта метрика столь же эффективна, что и неаддитивная метрика Форни. Затем применим метрику к декодированию сверточных кодов. Итак, пусть на множестве X" входных последовательностей канала введен код С = (с) с. X"длины п объема \С\=М со скоростью К = \о%М1п.

Предположим, что в результате передачи одного из кодовых слов на выходе канала принята последовательность у = (у,,-;у„). Работа декодера может быть описана разбиением множества У" на решающие области Д„, соответствующие кодовым словам с,„ е С, т-1,...,М. Решение в пользу слова с номером т принимается в том случае, когда у Если же у е У" \ ,

принимается решение о «стирании». В случае стирания получателю решение не выдается, а вместо этого по обратному каналу направляется запрос на повторную передачу того же кодового слова.

Для описания разбиения У" на области решений £>„ введем на множестве X распределение вероятностей р = {р(х),хеХ} и распространим

его на множество X", положив р(х) = ]П[^1р(х,), х = (х|,...,д:(1)е Л"" Положим А» = для всех т'^т},

где

= -Р(У|° -. (1-1)

а параметры А и р и распределение р должны быть выбраны в зависимости от параметров кода и канала.

Поясним смысл введенной метрики. Прежде всего, она аддитивна и может быть использована в рамках алгоритма Витерби. Из определения метрики формально следует, что при заданном у нужно вычислить метрику <р для всевозможных пар кодовых слов хт и хт. Нетрудно заметить, что в действительности декодирование последовательности у сводится к отысканию кодового слова х(л с максимальной функцией правдоподобия и кодового слова хт. со следующей по величине функцией правдоподобия. Метрика представляет собой логарифм максимальной функции правдоподобия деленной на «взвешенное» следующее по величине значение функции правдоподобия и на число, зависящее только от у. Результат сравнивается с порогом. Если порог превышен, принимается решение в пользу в противном случае производится стирание.

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

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

Алгоритм декодирования сверточных кодов в системе с обратной связью состоит в следующем. Ярус за ярусом решетка сверточного кода размечается приписыванием узлам решетки меток (7 (хороший узел) либо В (плохой узел). Метка С? приписывается узлу, если для одного из путей, сходящихся в узле, введенная выше функция <р превышает пороговое значение. В противном случае узлу приписывается метка В. Если на достаточном удалении т от данного яруса сохранились узлы, помеченные б, пути, ведущие в эти узлы, используются для принятия решения о данном символе. Параметр г определяет задержку декодирования. Если же все узлы на глубине г помечены В, происходит передача запроса на повторение условленного числа кодовых символов и возвращение декодера на заданное число ярусов назад.

Асимптотический анализ данного алгоритма приводит к следующему результату.

Теорема 1.1. Для любого е>0 существуют т0(е) и у„(е) такие, что при т > т0(е) и V >у„(£-) существуют сверточные коды с кодовым ограничением у и скоростью Л такие, что при использовании описанного выше алгоритма с задержкой декодирования т вероятность ошибки декодирования Ре и средняя скорость передачи Я удовлетворяют неравенствам

где

ЕЛЩ = шах

тах

£0/(Р.Р)>

£О/(Р.Р) = ££/>(*) КУ I

р(у!х)

ир ■

Соотношение между показателем экспоненты вероятности ошибки для систем с обратной связью с использованием сверточных кодов £/е (Л) и полученным Форни показателем экспоненты для систем на основе блоковых кодов Ег (Л) показано на рис 1.1. Эти кривые соответствуют двоичному симметричному каналу с переходной вероятностью р = 0,1.

в.М С в.«

Рис. 1.1. Показатели экспоненты вероятности ошибки для систем с решающей

обратной связью

Отметим примечательный факт: экспоненты Е/с(Я) и связаны

графическим построением аналогичным тому, которое связывает обычные экспоненты блоковых и сверточных кодов (для систем без обратной связи). Эту связь называют «обратной каскадной конструкцией», поскольку впервые она была получена в связи с каскадными кодами. Точки кривой Е/с(К) являются правыми верхними вершинами прямоугольников, две грани которых

совпадают с осями координат, а диагонали - касательные к ЕР(К). Заметим также, что Е/с(К) - выпуклая вверх функция, принимающая достаточно

большие значения при скорости близкой к пропускной способности канала.

Асимптотические результаты, сформулированные в Теореме 1.1 и представленные на рис. 1.1, получены на основе экспоненциально сложного алгоритма декодирования. Естественное направление развития исследований -поиск алгоритмов, которые, сохраняя потенциальные преимущества неблоковых методов, допускали бы простую практическую реализацию. Решение этой задачи было получено в работе [6].

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

Опишем этот метод более точно на примере симметричного канала с двоичным входом. Предположим, что в качестве блокового кода используется некоторый линейный (иД)-код. Обозначим через и1,и2,... подлежащие передаче двоичные блоки из к информационных символов. Последние Г поступивших от источника и переданных по каналу блоков информационных символов хранятся в памяти кодера и декодера, а последние у из них определяют текущее состояние сверточного кодера. Сверточный кодер после получения от источника очередного блока информационных символов и, вычисляет соответствующее кодовое слово линейного (п,к)-кода с,. Помимо этого кодер вычисляет блок Ь,, состоящий из п кодовых символов сверточного кода. Сумма по модулю два х, = с, © Ь, передается по каналу.

Таким образом, результатом кодирования всякий раз является последовательность из смежного класса данного кода. Лидер смежного класса зависит от текущего состояния сверточного кодера.

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

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

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

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

Теорема 1.2. Для любых положительных е и 3 существует п0 такое, что при при длине внутреннего кода п>и„ возможна передача со средней скоростью Ч ^ Я-З при вероятности ошибки

Ре £ ехр2 {-тп[С - Я - г]} + ехр2 {-ул[С - г]},

где С - пропускная способность канала.

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

УП

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

Графики экспонент вероятности ошибки для различных алгоритмов представлены на рис. 1.1 для двоичного симметричного канала с переходной вероятностью 0,1. Показателю экспоненты ЕДЯ) на рисунке соответствует кривая Е\К).

Итак, основными результатами исследования систем с обратной связью на основе сверточных кодов являются

• аддитивная метрика для декодирования сверточных кодов со стираниями;

• асимптотическая верхняя граница экспоненты вероятности ошибки декодирования при использовании сверточных кодов в системах с обратной связью;

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

2. Сверточные коды в широковещательных каналах

Идея исследования асимптотических характеристик блоковых и сверточных кодов в широковещательных каналах возникла в связи с опубликованием в 1974 г. в журнале «Проблемы передачи информации» работы Р. Галлагера, в которой были получены границы вероятности ошибки, с показателями экспонент положительными во всей области допустимых скоростей широковещательного канала Г. Ш. Полтырев воспользовался границами Галлагера для того, чтобы определить область пар вычислительных скоростей и получил неожиданный результат. Эта область, в отличие от области допустимых скоростей, не оказалась выпуклой, из чего следует, что в интересном с точки зрения практики диапазоне скоростей наилучшими способом кодирования остается тривиальное кодирование по принципу «разделения времени» между пользователями.

Опыт применения метода случайного кодирования приучил исследователей в области теории информации к тому, что среди множества случайных кодов «почти все» - хорошие. Напрашивался вывод о том, причиной такого поведения оценок Галлагера является неудачный выбор ансамбля кодов. Так возникла задача поиска ансамбля кодов эффективных в широковещательном канале. При исследовании систем неблокового кодирования для систем с бесшумной информационной обратной связью [1,3] было установлено, что в некоторых приложениях коды с фиксированной композицией лучше случайных кодов. Использование кодов с фиксированной композицией для построения нового ансамбля кодов и развитая в работах [2,4] техника анализа этих кодов привели к значительному улучшению границ вероятности ошибки для широковещательных каналов.

Рассмотрим сначала идеи, лежащие в основе анализа кодов с фиксированной композицией.

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

множества кодовых слов техника Галлагера приводит к асимптотически точным результатам.

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

Пусть X-{1, ..К), У = ¡1,..-/} - входной и выходной алфавиты дискретного канала без памяти. Композицией последовательности х длины п назовем вектор т = {г,,-,тк}, в котором т, - число элементов в х равных /, ^^г, = п. Через А, обозначим множество всех последовательностей с одинаковой композицией т. Код, все слова которого принадлежат А,, называется кодом с фиксированной композицией т. Через q обозначим произвольное распределение вероятностей на X, символами Мг[-], [•] обозначим операторы усреднения по множеству равновероятных последовательностей из Ат и по множеству последовательностей, полученных независимым выбором символов из X в соответствии с распределением вероятностей q.

Лемма 2.1. Для неотрицательной функции р(х,у), определенной на множестве X" х У", имеегг место неравенство

где Рч() обозначает вероятность, вычисленную в соответствии с распределением q.

Лемма 2.1. сводит усреднение по множеству последовательностей с фиксированной композицией к привычному усреднению по множеству последовательностей из независимых одинаково распределенных символов. Платой за упрощение анализа является необходимость оптимизации оценки по вспомогательным распределениям q.

Сформулируем кратко результаты работы [4].

Широковещательный канал без памяти задается двумя матрицами переходных вероятностей {Р,0 = {р(_у|х),д(г|х},хеХ,уеУ,гег}, где X -общий входной алфавит каналов Р и 0, а У к 2 - выходные алфавиты этих каналов. Рассматривается частный случай общей постановки задачи, в котором предполагается, что по широковещательному каналу передается «общая» информация, предназначенная для пользователей обоих каналов (скорость передачи этой информации обозначим через Р0) и «частная» информация, предназначенная только для пользователя канала Р (скорость ее передачи обозначаем через Л,, имеется в виду, что пропускная способность канала Р выше пропускной способности канала 2) .

Пусть и0 = {«„} = {1, ..,М0} и = представляют собой

множества сообщений, предназначенных соответственно для обоих

получателей и для получателя канала Р, Л/0 = 2""°, М1 = 2"*1. Через иор = {»<),,}> &1Г ~ (%} и ^п, = ("о,} обозначаются множества решений, принимаемых декодерами двух каналов, через Р^ и Р - вероятности ошибок декодирования на выходе каналов Р и £ соответственно, = тах|Рг(м0;, ф"0),Рг(й1р *«[)}, =Рг(% *мо)- Опишем ансамбль

блоковых кодов для широковещательного канала.

Блоковый код длины п с парой скоростей (Ло,Л,) представляет собой множество последовательностей V = }, г = 1 ,...,Л/0, у' = 1 .....Л/,, М0 = 2"*°, Л/, = , V с. X". Для описания ансамбля кодов вводится вспомогательный алфавит 5 ={5}, на множестве задается распределение /(в), и помимо этого вводится «тест-канал» (/(х 5 я)}, х е X", . Сначала в соответствии с распределением /(в) из множества 5" независимо выбираются М0 последовательностей в,, /= 1,...,Л/„, затем для каждого г в соответствии с распределением '(яЮ из множества X" независимо выбираются Л/, последовательностей . Каждая из них - кодовое слово, сопоставляемое паре сообщений О',./).

Для описания декодирования вводятся две неотрицательные функции: Лр(у,з) и с!ч(г,я). Декодер каждого из каналов Р и б сначала принимает решение в пользу одного из сообщений множества 1/0. Это решение принимается по принципу максимума соответствующей «декодирующей» функции с/. После этого декодер канала Р принимает решение в пользу одного из сообщений множества ¡7,. Это решение принимается по принципу максимума условной вероятности р(у | у1;) по всем ] при уже известном значении /.

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

Р* ^ехр^-иттдаДОД)},

/^ехр^-яад)},

Е[{К) = тах(-рД0 + Е'т(р)) + о,(п), р«10,1Г

£7(Л, ) = тах(-рЯ, +Щ,(р))+о2(П), Е2(Ъ) = тах(-р110 + ЕО2(р)) + о1(п),

££,(/>)= «ах

'<*> , у

¿ГСм)

Е'аг(р) = шах

Е/^ЧСм)

ям

=| А-11о/ и, о2(») =| XIIГ11о8(жл)/и,

« х ' I

где 10(х\я) - произвольные переходные вероятности, -

произвольное распределение вероятностей.

Отметим, что при соответствующем выборе вспомогательных распределений ?'(-»ф'), /0(в) и декодирующих функций с1р и <1Ч

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

В^ /0.223, С010 368

Прямая разделения

Л.,/0.632, С,/0.685

Рис. 2.2. Нормированные пропускные способности и вычислительные скорости широковещательного канала

Далее вводится ансамбль решетчатых кодов для широковещательного канала. Для этого строится решетка кода тест-канала со скоростью и затем -решетка кода канала Р со скоростью R, Широковещательный код определятся как множество кодовых слов, задаваемое решеткой-произведением. Связь экспонент вероятностей ошибок для решетчатых кодов с соответствующими экспонентами блоковых кодов аналогична подобным соотношениям для обычных однонаправленных каналов. Иллюстрацией точности полученных оценок может служить нижняя граница множества пар вычислительных скоростей. Это множество определяется соотношением

ma* mm {£02(1), £;,(])}.

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

На рис. 2.2 представлены графики нормированной функции R^iR^), нормированной пропускной способности С0(С,) и нормированной функции получаемой при использовании оценок Галлагера. Графики построены для пары двоичных симметричных каналов с переходными вероятностями 1(Г3 и 10"'. Величины 0,632 и 0,223 - вычислительные скорости каналов, 0,685 и 0,368 - их пропускные способности (в натуральных единицах информации).

Заметим, что вычисленная оценка пар вычислительных скоростей, в отличие от кривой Я^с(Ло|С), целиком лежит выше прямолинейной границы, достижимой при использовании принципа разделения времени. Больше того, выпуклость выражена более сильно, чем выпуклость области

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

Итак, основными результатами исследования характеристик кодирования в широковещательных каналах с применением сверточных кодов являются

• оценки вероятностей ошибок ансамбля кодов с фиксированной композицией;

• асимптотические верхние границы вероятностей ошибок декодирования в широковещательных каналах;

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

• ансамбль сверточных кодов для широковещательных каналов и асимптотические границы вероятностей ошибок декодирования для этого ансамбля кодов.

3. Списочное декодирование сверточных кодов

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

В совместной работе автора с Балакирским В.Б. [9] задача решается в другой постановке. Рассматриваемый списочный декодер (точнее говоря, декодер, основанный на списочном декодировании) сам принимает окончательное решение о передаваемой информационной последовательности. Он является альтернативой наиболее часто используемым алгоритмам декодирования - алгоритму последовательного декодирования и алгоритму Витсрби. Как будет показано ниже, алгоритм декодирования, основанный на списках, обеспечивает лучшее соотношение между сложностью и вероятностью ошибки, чем другие известные алгоритмы. Это справедливо в асимптотике при увеличении кодового ограничения сверточного кода, а также при использовании конкретных конструкций кодов конечной длины.

Заметим, что другой списочный декодер несколько раньше (в 1980 г.) был предложен К.Ш.Зигангировым и В.Д.Колесником и еще один алгоритм разработан в 1987 г. Т. Хашимото. Рассматриваемый ниже способ декодирования имеет тс же асимптотические характеристики, что и другие списочные декодеры, в то же время его реализация заметно проще, чем реализация алгоритма Зигангирова-Колесника. Алгоритмы [9] и алгоритм Хашимото по сути совпадают и были получены независимо друг от друга (первые результаты работы [9] были опубликованы в 1986 г в форме доклада на Всесоюзном симпозиуме по проблеме избыточности в информационных системах [7]). Опубликованное в [9] доказательство эффективности алгоритма представляется более простым, чем доказательство Хашимото. Кроме того, полученные в [9] и последующих работах характеристики конкретных кодов имеют самостоятельное значение.

Опишем алгоритм списочного декодирования. Для простоты рассмотрим сверточный кодер, входом которого на каждом такте работы служит q -ичный информационный символ и на выходе формируется последовательность из п символов канала. Скорость кода равна (\ogq)!n бит/символ канала, через v обозначаем длину кодового ограничения кода. Текущим состоянием кодера в момент t являются последние v символов, поступивших на его вход, а, = (и,_+1,.- Общее число состояний кодера равно д".

Параметрами алгоритма являются L - объем списка, т - задержка декодирования, v0 - параметр, определяющий сложность декодирования, v0<v. Назовем псевдо-состоянием декодера сг, последовательность из v0 информационных символов, раньше других поступивших на вход кодера, т.е. сг, = Общее число различных псевдосостояний равно 2"'.

Алгоритм ярус за ярусом обрабатывает узлы кодовой решетки рассматриваемого кода. На первых шагах с номерами t = 1,2,...,v0 +Mog? ¿J в

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

Заметим, что работа декодера связана с поиском наилучшего пути в решетке узлов-псевдосостояний. Эта решетка имеет ту же структуру, что и решетка кода, но кодовые символы, приписываемые ребрам, не фиксированы, они зависят от конкретных путей, выбранных декодером в качестве наилучших путей, ведущих в каждое конкретное исевдосостяние.

Вычислительная сложность и объема памяти декодера определяются числом путей, обрабатываемых на каждом ярусе. Это число равно Lqv° и, следовательно, асимптотически этот декодер по сложности эквивалентен декодеру Витерби кода с кодовым ограничением v0 + log, L.

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

Асимптотическое исследование вероятности ошибки списочного декодера в канале без памяти с переходными вероятностями {р(у\х)} приводит к следующему результату.

Теорема 3.1. Для любого е > 0 в ансамбле случайных решетчатых кодов существуют коды, для которых зависимость вероятности ошибки Ре от сложности декодирования Я при достаточно больших г, v и v0 определяется соотношением

Ре<Н-<р'"\

где Рц е [0,1] - решение уравнения

Я = Е0(рк)/р11,

Е0(р) =

Хр(х)р»>(у}х)

{р{х),х^Х} - распределение вероятностей на входных символах канала, обеспечивающее максимум функции Ей{р).

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

В таблице 3.1 приведены два примера кодов со скоростью 1/2. В этой таблице и всюду в дальнейшем используется двоично-восьмеричная запись кодовых многочленов. Например, код с многочленами О+О+О'д+О2) записывается как (7,5). Для каждого из приведенных в таблице кодов в терминах свободного расстояния демонстрируется выигрыш от применения списков при декодировании. Приравнивая списочный декодер декодеру Витерби по сложности декодирования либо по числу гарантированно исправляемых ошибок, мы видим, что списочный декодер эффективнее декодера Витерби.

Таблица 3.1

Примеры кодов для декодирования с использованием списков

Параметры списочного декодера, Эквивалентный Эквивалентный

Ь-2 код по код по числу

сложности декодирования исправляемых ошибок

Код V "о г 'о V V *, 'о

32600,36645 14 6 27 5 1 10 4 8 12 5

456362000,510777401 27 8 37 6 9 12 5 10 14 6

Исследование дистанционных свойств списочного декодирования было продолжено в работах [10,14]. В работе [14] в общем виде выведены формулы для списочного расстояния блокового кода над евклидовым пространством и подсчитаны расстояния некоторых интересных с точки зрения практики кодов.

Рассмотрим блоковый код С = {хт =(*„,, ..,хтг),т = \,...,М}с.Х" длины и объема |С|=М, кодовые символы которого хт, ¡-1т = 1,...,М, для передачи по каналу с аддитивным белым гауссовским шумом (АБГШ)

преобразуются в векторы 8т1, N -мерного евклидова пространства. Обозначим через г = (г,,...,г„) вектор, наблюдаемый на выходе канала. Декодирование по максимуму правдоподобия в канале с АБГШ сводится к декодированию по минимуму расстояния Евклида между принятым вектором г и передаваемой сигнальной последовательностью $,

-|1/2

ЕКг0'-^')2

М /«!

Если передавалась сигнальная последовательность 50, то при декодировании списком объема I ошибка декодирования произойдет в том случае, когда неравенства

будут выполнены для всех последовательностей из некоторого списка

В работе [14] доказано следующее экспоненциально точное неравенство для вероятности ошибки декодирования последовательности $„ в пользу заданного списка последовательностей 5

= 0, если = 0 для некоторого Ь > О,

[^ехр!-^^)/-}^} в противном случае,

где Л^ - спектральная плотность мощности шума, XV= {%}>''■ 7'= 1,...,£ -матрица корреляции сигнальных последовательностей,

Ч) = («, - «„,8, - 80) = « + <¡1 -¿¡)/2, с!у = </£Му),

и через обозначен квадрат "списочного" евклидова расстояния между

$„ и списком 5.

Если векторы («,-$„) линейно независимы, то списочное расстояние вычисляется по формуле

где вектор-строка IV - главная диагональ матрицы \У, Т - символ транспонирования. Если же векторы («, -«„) линейно зависимы, то списочное расстояние вычисляется как максимум списочного расстояния по подмножествам линейно независимых векторов.

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

совместно с Кирилюком В.Н. [10]. Были подсчитаны списочные расстояния для многих сверочных кодов и сигнально-кодовых конструкций.

Например, для сверточного кода с кодовым ограничением 2 со скоростью 1/2 с порождающими многочленами (5,7) свободные расстояния при декодировании списком объема /. = 1,2,3 равны соответственно 5, 7,14 и 9,39. При этом имеется 6 списков объема 2 на минимальном расстоянии от нулевого слова.

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

• основанный на списках алгоритм декодирования сверточных кодов;

• асимптотическая оценка вероятности ошибки списочного декодирования сверточных кодов;

• примеры сверточных кодов, обеспечивающих эффективное применение списочного декодирования;

• формулы для вычисления списочного расстояния в евклидовой метрике.

4. Анализ характеристик кодов в каналах с памятью

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

В совместных работах с В.Д. Колесником [8,17] и позднее в совместной работе с Бочаровой И.Е. [15] изучались методы построения моделей каналов и их применение для решения практических задач. Рассмотрим кратко основные результаты, полученные в этом направлении.

Сначала мы рассмотрим специальный класс моделей каналов - функции марковской цепи и функции псевдомарковской цепи. Эти классы моделей описаны, в частности, в монографии Турина В Я. (1977 г.). Затем применим этот подход к задаче построения модели дискретного отображения канала с релеевскими замираниями.

Обозначим через Е={е} множество значений ошибок в дискретном канале и каждому элементу множества сопоставим квадратную матрицу А(е) размерности г. Введем также вектор-строку а = (at,...,ar) и вектор-столбец b = (b„...,br)T. Если при всех п соотношения

Pie,.....0 = аПА(е,)Ь

задают распределения вероятностей на множествах Е", то случайная последовательность е,,е2,... называется функцией псевдомарковской цепи. Если при этом матрица А = £ А(е) стохастическая, а каждая из матриц А(е)

неотрицательна, то процесс представляет собой функцию цепи Маркова.

Условием стационарности псевдомарковской цепи является выполнение тождеств

а А = а, АЬ = Ь.

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

Известны формулы для вычисления параметров стационарного процесса ранга г по его известным (2г -1) -мерным распределениям. Чтобы применить их к задаче построения аппроксимации дискретного отображения канала с замираниями, введем следующие обозначения.

Рассмотрим канал с двоичным входным и двоичным выходным алфавитами, будем использовать запись а' для серии из у одинаковых элементов а, а е {0,1}, и введем специальный символ г для обозначения позиции, на которой значение символа не определено.

По вероятностям р( 1'), / = 1,2,3, р(\г'\), /=1,...2г-3, и р(Ъ'1гу1), = 1,...,г - 2 вычисляются вспомогательные матрицы

Q =

1 Kl) № рО О

Р( 1) ... Р(1) р(Ы) ... pilz'-1))

Q(i)=

Q(z) =

p{\)p(\z"1\)p{\z"%..p{\z2'-i\)

p{ 1) p(ll) p(lzl) ... p(lzr'2\) p( 11) p(lll) p(llzl) ... p(l lzr'2l)

p(lzr-2l) pQzr-211) p{\z"2\z\)...p(\zr-4z'-2\)

Pü) PO) P( 1) P( 1) />(1) p(\z\) p(lz2l)

р(Х)р(\гг'*\)р(\г'\)

Р(1г-Ч) p(lz2'3l)

и по ним - матричное представление модели канала:

Ь = (1,0,...0)г, А(1) = 0-42(1), А = СГ,<}(г), А(0) = А-А(1).

(Если ранг процесса больше или равен г, то матрица Q невырожденная и определена).

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

р(е) = Д-'(е)ехр{-ЛЛе)/Д(е)}, причем для требуемых комбинаций ошибок А(1) = й„ + 2, Г(1) = 1;

Д(1г'-'1) = (й, + 2)2-йу, Г(1гм1) = 2 + Нр-крР',

Д(1/-V4) = (А, + 2)3 - Ъ\{Ьр + 2 Хру + РЪ + Р2(/+") + 2 Ау*, Г(1г'-'1гу"') = Щ + 2 )3 - 2ЙДА, + 2)(р> + р' + р^) +

Щ(рг» + р'*»+рП- а>2' + ръ + />2('">),

где р - коэффициент корреляции квадратурных компонент коэффициента передачи канала,

Йр=£/[ЛГ0(*2 + О]. К = Екг /[М0(к2 +1)],

- соответственно случайная и регулярная составляющие отношения сигнал/шум, Е - энергия сигнала, - спектральная плотность мощности

аддитивного гауссовского шума, к - параметр, определяющий отношение энергий регулярной и случайной составляющих коэффициента передачи.

Понятно, что полученная форма представления дискретной модели заведомо не является функцией цепи Маркова. Больше того, возможно, что получаемая функция псевдомарковской цепи не эквивалентна никакой функции марковской цепи. Однако, в [15] показано, что при аппроксимации релеевского канала моделью ранга 2 всегда существует представление дискретного отображения в виде функции цепи Маркова, то есть, в виде модели Гилберта-Элиотта. Явные формулы для параметров модели приведены в [15].

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

р(т,п) = ах р(т,п),

в которой р(т,л) - вектор-столбец условных вероятностей т ошибок при передаче п символов при известном начальном состоянии канала. Вектор р(т,я) вычисляется рекуррентно по формуле

р(/и,и)= А(0)хр(/я,я-1)+ А(1)хр(тя-1,л-1), т-0,...,п,п = 1,2,... с начальными условиями

р(-1,п) = 0, п = 0,1,2,... Р(0,0) = Ь.

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

Известно, что расчет характеристик сверточных кодов выполняется с использованием аддитивных границ. В формулы для оценок входят спектр кода и вероятность ошибки для кода из двух слов с заданным расстоянием между ними. Таким образом, методика расчетов и формулы работы [15] могут быть использованы для оценки вероятности ошибки декодирования как блоковых, так и сверточных кодов, при условии, что декодирование выполняется по критерию минимума расстояния Хэмминга.

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

• разработана техника построения матричной модели дискретного канала с памятью на основе функции цепи Маркова либо функции псевдомарковской цепи;

• выведены формулы для параметров дискретного отображения широкого

класса моделей каналов с замираниями; ■ получены точные формулы для вычисления параметров модели Гилберта-Элиотта через оценки вероятностей комбинаций длины 3 либо через параметры модели соответствующего канала с замираниями.

5. Построение и анализ сверточных кодов с заданной сложностью декодирования в канале с мягкими решениями

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

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

Еще более сложной является задача декодирования и поиска кодов со скоростью к! п. Традиционная схема кодирования таких кодов предполагает наличие к регистров сдвига и п сумматоров по модулю 2. На каждом такте на вход кодера поступает к информационных символов и с выходов сумматоров считываются п кодовых символов Состояние кодера определяется содержимым всех ячеек регистров сдвига. Их суммарная длина v задает кодовое ограничение кода. Решетчатая диаграмма, описывающая код, содержит на каждом ярусе 2" узлов и из каждого узла исходит 2* ребер. Такое представление кода слишком громоздко и соответствующий декодер имел бы слишком большую сложность.

Уменьшение сложности декодирования высокоскоростных сверточных кодов может быть достигнуто использованием так называемых «выколотых» кодов. Высокоскоростной код получается периодическим удалением кодовых символов низкоскоростного кода. В работах по выколотым кодам преимущественно рассматривались коды со скоростью вида к/(к +1). Для их построения использовались два порождающих многочлена. Выколотый код -периодически изменяющийся код с периодом к. На первом такте работы на выход кодера поступают выходы двух сумматоров. На каждом из следующих (к-1) тактов используются попеременно то один сумматор, то другой. Порядок использования сумматоров определяется специальной матрицей -матрицей выкалывания. Такой класс кодов был введен 1979 г. в совместной работе Кларка, Кейна и Гейста. Позже другими авторами исследовались коды, получаемые из большего, чем 2, числа генераторов.

Отметим главное преимущество выколотых кодов, определяющее их практическую важность. Решетка выколотого кода, заданного генераторами максимальной степени v, содержит на каждом ярусе 2" узлов и из каждого узла исходит 2 ребра. Мягкое декодирование такого кода имеет ту же сложность, что и для кода со скоростью 1/2.

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

Пусть, например, рассматриваются коды со скоростью к/п = 3/5. Для таких кодов множество генераторов {§|,...^3}может быть разбито на подмножества двумя неэквивалентными способами: (gt,g2,gs),(.g4)>(gs) яш (gi>g2)'(g3'g4)-(gs)- Все другие способы сводятся к одному из этих двух перенумерацией генераторов либо изменением номера ребра, считающегося первым. Эти два разбиения удобно записать в виде последовательностей длин ребер (3,1,1) и (2,2,1) соответственно.

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

• Всегда ли «антиподальные» коды (коды, задаваемые генераторами имеющими ненулевой свободный член и ненулевой коэффициент при старшей степени) являются наилучшими?

• Существует ли для заданной скорости кода оптимальное разбиение?

Положительный ответ на эти вопросы позволил бы заметно сократил бы

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

В [23] приведены таблицы кодов со скоростями kin для значений к = 1,...,7 и п-к +1,...,8 для значений длин кодового ограничения v = 2,...,8. В число найденных кодов входят и коды с «сократимыми» скоростями вида (kl)l(nl), /=2,3... Эти коды называют периодически изменяющимися во времени или просто переменными кодами. В качестве лучших в таблицы включались коды с наибольшим свободным расстоянием d^. Для кодов с одинаковым расстоянием предпочтение отдавалось коду с меньшим первым коэффициентом порождающей функции спектра для подсчета вероятности ошибки на бит (меньшим общим числом ненулевых информационных символов в информационных последовательностях, порождающих слова веса d&ec). При равенстве первых коэффициентов сравнивались вторые и т.д..

Подсчет характеристик кодов выполнялся с помощью рекурсивного алгоритма, идея которого принадлежит Балакирскому В. Б- Матричная форма этого алгоритма описана в работе [21]. Однако вычислительная эффективность алгоритма поиска кодов определяется, главным образом, не сложностью подсчета характеристик кода (эта сложность пропорциональна 2"), а тем, насколько быстро алгоритм отвергает заведомо неперспективные коды (общее число кодов имеет порядок 2Ш).

Отметим основные способы, использованные для ускорения поиска кодов:

• отбрасывались эквивалентные коды, т.е. коды, отличающиеся от уже рассмотренных только порядком следования генераторов в пределах ребер;

• свободное расстояние оценивалось сверху как сумма весов генераторов;

• быстрые тесты на катастрофичность, в частности, если все генераторы имеют четный вес, код катастрофический:

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

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

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

Таблица 5.1

Примеры новых переменных во времени кодов

V к п Параметры нового кода Параметры известного кода

I ¿ш

5 1 2 3 8 2/3 8 2

6 1 2 3 10 27 10 36

7 1 2 2 11 47/2 10 2

8 1 2 2 12 24 12 33

6 1 3 2 15 4 15 7

7 1 3 2 16 1/2 16 1

2 1 4 2 10 1/2 10 1

2 2 3 2 4 33 3 1

3 2 3 2 4 3 4 5

5 2 3 2 6 43 6 56

В Таблице 5.1. представлены некоторые примеры вновь найденных кодов с сократимыми скоростями (А/)/(и/) и для сравнения приведены ранее известные лучшие коды с такой же по величине скоростью к!п

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

Итак, поиск сверточных кодов для эффективного применения в каналах с мягкими решениями привел к следующим результатам:

• введен класс высокоскоростных выколотых кодов, задаваемых набором генераторов и разбиением ребер, исследована зависимость характеристик кодов от разбиения;

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

• построены таблицы кодов для широкого диапазона скоростей кодов и длин кодовых ограничений.

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

Возможность использования решетчатого представления блоковых кодов для уменьшения сложности декодирования по максимуму правдоподобия рассматривалась в 1974 г. в совместной работе Л.Бала, Дж. Кука, Ф.Джелинека, Дж. Равива. В 1988 г. Д. Мудером была формализована задача построения решеток с минимальной сложностью и получена нижняя граница сложности решетки блокового кода.

Новый класс решеток для блоковых кодов был введен в 1979 г. Г. Соломоном и X. Ван-Тилборгом. Позже в 1986 г независимо от них такие же решетки были построены Дж.Ма и Дж. Вулфом. Благодаря Ма и Вулфу за этими решетками и соответствующими кодами закрепилось название «коды с нейтрализацией хвостов» (tail-biting codes). В последние годы в литературе на русском языке эти коды называют циклически усеченными (ЦУ) кодами и соответствующие решетчатые диаграммы ЦУ решетками. Различие между обычными решетками и циклически усеченными заключается в том, что обычная решетка содержит ровно один начальный узел и один конечный узел. В циклически усеченной решетке число начальных узлов совпадает с числом конечных узлов и может быть любым. Для одного и того же кода сложность его представления циклически усеченной решеткой может быть существенно меньше сложности представления с помощью обычной решетки.

Исследованию характеристик циклически усеченных решеток посвящена совместная работа с Захаровой Т. Г. [11]. В этой работе методом случайного кодирования получена оценка минимального расстояния ЦУ кодов и установлена граница сложности ЦУ решетки, при которой существуют ЦУ коды, удовлетворяющие асимптотической границе Варшамова-Гилберта на минимальное расстояние кода. Помимо этого, были построены таблицы ЦУ

кодов. Найденные коды имели лучшие параметры, чем коды, представленные в работе Ма и Вулфа.

Исследование ЦУ кодов было продолжено в работе [12], где для этих кодов был предложен алгоритм их асимптотически оптимального декодирования и затем в [24,26], где получен ряд теоретических результатов и обширные таблицы кодов.

Рассмотрение ЦУ кодов мы начнем в подразделе 6.1 с описания их конструкции и форм представления. В подразделе 6.2 приведена нижняя граница сложности решеток. Далее в подразделе 6.3 обсуждаются результаты исследования асимптотических характеристик ЦУ кодов и затем в подразделе 6.4 приведены результаты поиска решеток с минимальной сложностью для линейных блоковых кодов. Декодирование ЦУ кодов описано в подразделе 6.5.

6.1. Минимальные ЦУ решетки блоковых кодов

Рассмотрим задачу эффективного представления линейного блокового (л, А-) -кода с помощью ЦУ решетки. Заметим, что наиболее естественный путь описания ЦУ кодов и их решеток связан с конструированием этих кодов из сверточных кодов. Именно на этом пути были получены конструктивные результаты работы [11]. В то же время для получения нижних границ сложности решеток и минимального расстояния соответствующих кодов нужно точно описать все множество кодовых решеток и установить для них критерии сложности. Для этого, следуя [26], введем необходимые определения и обозначения.

ЦУ решетка длины Ь представляет собой направленный граф, множество узлов которого разбито на I непересекающихся подмножеств (ярусов) 5, с номерами 01 таких, что каждое ребро соединяет некоторый узел яруса / с узлом яруса г +1, причем число /' +1 вычисляется по модулю I.

Из этого определения следует, что ЦУ решетка имеет циклическую структуру. Для удобства графического изображения вводится дополнительный ярус с номером Ь. Множество узлов этого яруса совпадает с множеством узлов нулевого яруса 50.

Для описания кодов решетками ребрам приписывают кодовые символы. Если множество последовательностей, соответствующих всевозможным путям с яруса 0 на ярус Ь, совпадает с множеством кодовых слов линейного (п,к)-кода, код называют ЦУ кодом.

Оговорим, что мы рассматриваем только двоичные коды и только решетки, в каждый узел которых входит не более 2 ребер и из каждого узла исходит не более двух ребер.

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

длиной секции с номером t. Имеет место равенство ^^с, = п. При L<n

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

Набор чисел fi, = log2[S,|, / = 0,...,L-1 называют профилем сложности решетки, а величину

ц = max ¡л,

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

Рассмотрим линейный (п,к) -код, заданный порождающей матрицей G = {г,}, / = 1,...,к. Напомним некоторые термины, используемые для описания обычных (не ЦУ) несекционированных решеток. Для каждой строки г, обозначим через start(r) и end(r) номера позиций первого и последнего ненулевого элемента соответственно. Эти позиции называются началами и концами строк. Позиции между start(r) и end(r) включительно мы называем нетривиальными. Интервал [start(r), end(r)) называют также интервалом активности строки.

Произвольная строка г вместе с нулевой строкой образуют линейный код, который можно представить с помощью решетки, имеющей сложность 0 на интервале [0,start(r)), сложность 1 на интервале [start(r),end(r)) и сложность 0 на интервале (end(r) ,п] . Эту решетку называют элементарной решеткой, позиции из интервала [start(r),end(r)) называются активными.

Произведением двух произвольных решеток мы называем решетку, множеству узлов которой на ярусе i сопоставляется декартово произведение SU) = S{° X S$n множеств состояний Sl°,S{0, соответствующих узлам двух решеток-сомножителей. Узел яруса /', соответствующий состоянию в

решетке-произведении соединяется с узлом яруса / + 1 в том случае,

если в первой решетке узел s*'1 был связан с и во второй решетке узел был связан с sl'*l>.

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

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

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

частности, началу строки может соответствовать позиция с большим номером, чем концу строки. Например, для строки 1000001 в качестве начала может быть выбрана последняя, а в качестве конца - первая позиция.

Обозначим через §1аП(г) номер ненулевой позиции строки г, выбранной в качестве начала строки. Тогда (циклическим) концом строки называется наименьшее число 5»а!Т(г) такое, что интервал фаг^г), епё(г)+п]гаойп накрывает все множество ненулевых позиций строки г. Аналогично трансформируются понятия нетривиальных позиций, активных позиций, интервалов активности и элементарных решеток.

Матрица в представлена в ЦУ приведенной форме, если все ее (циклические) начала строк различны и все концы строк также различны

Минимальность для ЦУ кодовых решеток понимается иначе, чем для обычных решеток. Минимальной ЦУ решеткой называется решетка, минимизирующая максимальную сложность (а не значения сложности для каждой позиции).

Смысл представления решеток в ЦУ приведенной форме проясняется следующей теоремой.

Теорема 6.1. Пусть порождающей матрице С произвольного линейного кода соответствует ЦУ решетка со сложностью ц и пусть С" - матрица, задающая эквивалентный код и имеющая ЦУ приведенную форму и сложность соответствующей решетки равна /и . Тогда имеет место неравенство м < М ■

Иными словами, приведение матрицы к ЦУ приведенной форме минимизирует сложность соответствующей ЦУ решетчатой диаграммы.

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

Пусть в задана в ЦУ приведенной форме и ее строки упорядочены по возрастанию номеров начальных секций строк. Если при этом концы строк также упорядочены, будем говорить, что С имеет регулярную ЦУ приведенную форму. Упорядоченность понимается здесь в циклическом смысле.

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

// = тах{4} = тах{В,}-1,

где Д и В1 обозначают соответственно число активных строк и число нетривиальных строк в / -й секции кода.

Введенные определения поясним двумя примерами порождающих матриц кода Хэмминга (8,4)

11010100 1111000 0»

00110101 0101 1 0 1 01 С = С — 1

1 _ 0 1 0 О I 1 0 1 ' 2 0011 1100 '

01010011 1 1 0 0 0 0 1 1 |

Если в этих матрицах заменить тривиальные позиции звездочками, разбив матрицы на секции, получим

1 1 0 1 0 1 * • 1 1 1 1 * * * *

* * 1 1 0 1 0 1 * 1 0 1 1 0 1 0

0 1 * * 1 1 0 1 * 2 * * 1 1 1 1 * *

0 1 0 1 * * 1 1 1 1 * * * • 1 1

Номера начальных секций равны 1,2,3 и 4 для первой матрицы и 1,2,3 и 5 для второй. Заканчиваются строки соответственно в 3,4, 1 и 2 секциях в, и в 3, 5, 4 и 2 секциях С2. Первая матрица имеет регулярную форму, вторая -нерегулярную Максимальная сложность одинакова и равна 2, хотя профиль сложности для двух матриц различается Соответствующие решетки показаны на рис.6.1 и 6.2. Отметим, что без секционирования сложность в обоих случаях была бы равна 3.

... \4

у'

УуУЧ

/

м

X

/\/Х \

Чп Ч

А ^ чкч

*Т—--*

Рис.6.1. Решетка, соответствующая матрице С,

Рис.6.2. Решетка, соответствующая матрице в2

Представление ЦУ решеток матрицами в регулярной приведенной форме имеет следующую интерпретацию, тесно связанную со сверточным кодированием.

Кодер ЦУ кода в общем случае состоит из к0 двоичных регистров содержащих по L двоичных ячеек памяти. Первые v разрядов каждого регистра вместе с п0 сумматорами по модулю два образуют сверточный кодер со скоростью R0 = k0/n0. В момент начала работы кодера первые £0 разрядов каждого регистра заполняются нулями, в остальные £-£„ разрядов записываются информационные символы. Далее на каждом из L тактов работы кодера осуществляется циклический сдвиг всех регистров на одну позицию. При этом с выхода кодера всякий раз считываются п0 кодовых символов. Всего за L тактов будет считано п = Ln0 кодовых символов, соответствующих k = {L-La)ka информационным символам. Множество кодовых слов на выходе этого кодера образует линейный (п,к) -код со скоростью R = (L- L0)k0/(n0L).

Представленная на рис. 6.1 решетка кода (8,4) соответствует ЦУ сверточному коду с генераторами (100, 111) с кодовым ограничением 2, со скоростью 1/2, с параметрами L = 4, 1^ = 0.

6.2. Верхние границы на минимальное расстояние циклически усеченных кодов

В работе [26] получена следующая граница, связывающая минимальное расстояние ЦУ кода со сложностью решетчатой диаграммы.

Теорема 6.2. Минимальное расстояние dmlt ЦУ линейного (п,к) -кода с максимальной сложностью ц удовлетворяет неравенствам

к

где nma(j\daa) обозначает минимально возможную длину линейного кода размерности j с минимальным расстоянием ётй.

Из теоремы вытекает оценка снизу на сложность ЦУ решетки линейного кода с заданным минимальным расстоянием:

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

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

£

j = l,..,k

порождающей матрицы в кода со сложностью ц имеется не более // + 1 нетривиального элемента. Рассмотрим матрицы, составленные из у (циклически) последовательных строк матрицы в, начиная со строки с номером р, ре {1,...,£}. Множество линейных комбинаций их строк образует линейный код размерности у. Подсчитаем эффективную длину пр этого кода (число ненулевых столбцов в его порождающей матрице). Величина пр определяется числом позиций между началом первой и концом последней из у строк. Ясно, что пр<п, т.е. не все столбцы будут в ней представлены.

Нетрудно заметить, с другой стороны, что каждый столбец будет представлен в /х + у кодах. Значит, суммарная длина всех кодов равна п(ц + у), средняя длина равна п(р + у)/к и по меньшей мере для одного из кодов длина будет не больше этой величины. Поскольку каждый код имеет расстояние £/то, получаем первое неравенство теоремы, второе неравенство - граница Грайсмера.

Доказательство теоремы для произвольной (нерегулярной) структуры матрицы С несколько сложнее.

Точность границы для конечных длин кодов иллюстрируется приведенными ниже таблицами ЦУ кодов. Как показывают представленные в таблице 6.1 данные, в большинстве случаев удается найти коды, удовлетворяющие границе с равенством или отличающиеся от нее на 1. В последнем случае это часто означает, что граница точна в этой точке для несекционированных решеток. Примечательны примеры кодов (24,12), (28,14), (32,16) и (48,24). Для них граница сложности существенно ниже сложности наилучшего ЦУ кода, полученного усечением постоянного во времени сверточного кода. Однако поиск среди изменяющихся во времени кодов показывает, что и в этих случаях граница точна.

6.3. Асимптотические границы сложности решетчатого представления циклически усеченных кодов

Начнем с нижней границы сложности ЦУ решеток. Эта граница получена в совместной работе с Захаровой Т.Г. [11] усреднением по множеству случайных ЦУ кодов. Остановимся подробнее на описании ансамбля кодов.

Рассмотрим описанный выше способ порождения ЦУ кода с помощью сверточного кодера со скоростью Я„ = к01па с кодовым ограничением V, длиной регистров Ь и с /,„ нулями в каждом из регистров в начальном состоянии кодера. Обозначим через / = 0,...,V, у' = 1,...,1 матрицы

размерности кахп0, описывающие связи /-х разрядов регистров с сумматорами на у -м такте работы кодера. Порождающая матрица линейного кода, порождаемого таким кодером, имеет вид

С«" С™ ... С<"" 0 0 ООО

о с<? . с';;11 с'г7" о ... о о о

о о

с= о о

с<" о

0 0 0.. С'^1 С'1-'*" о 0 0 ... О С'1-"*"

... с™....

- с<"

С<£Г ..о о о ... о о с'"*' ... с(4'

где 0 обозначают нулевые матрицы размерности к0хп0.

На рис. 6.3 структура матрицы показана более наглядно. Заштрихованные области соответствуют нетривиальным элементам, на остальных позициях располагаются нули.

Рис. 6.3. Структура порождающей матрицы ЦУ кода из ансамбля случайных кодов

Коды случайного ансамбля ЦУ кодов получаются случайным независимым равновероятным выбором двоичных элементов матриц .

Понятно, что рассматриваемый ансамбль кодов является подмножеством ансамбля равновероятных двоичных кодов, у которых все элементы порождающей матрицы принимают значения 0 и 1 с равными вероятностями. Чем больше кодовое ограничение сверточного кода V, тем шире полоса нетривиальных элементов порождающей матрицы и тем ближе характеристики кодов к характеристикам случайных кодов общего вида. Можно ожидать, что при уменьшении кодового ограничения до определенной величины минимальное расстояние кодов будет таким же, как и для случайных кодов общего вида, но сложность ЦУ решетки (и, соответственно, сложность декодирования) будет уменьшаться. Обменные соотношения между минимальным расстоянием и кодовым ограничением устанавливает следующая теорема.

Теорема 6.3. Для любых положительных сколь угодно малых е, и ег существует натуральное число N такое, что при п > N в ансамбле случайных блоковых ЦУ кодов длины п со скоростью Л, получаемых из сверточного кода с длиной кодового ограничения V = Д£. при Ц, = вЬ и

(6.1)

существуют коды с минимальным расстоянием = 8п таким, что

3 =

где

= *-'(!-Я).

соответственно асимптотическая граница Варшамова-Гилберта на минимальное расстояние блоковых кодов и асимптотическая граница Костелло на свободное расстояние сверточных кодов, й(.х:) = -;ск^2(х)-(1-;с)к^2(1-;<:) - энтропия двоичного ансамбля.

Иными словами, в ансамбле случайных ЦУ кодов существуют коды, удовлетворяющие асимптотической границе Варшамова-Гилберта, если нормированное кодовое ограничение исходного кода удовлетворяет соотношению (6.1). Из этой теоремы выводятся две важные оценки - верхняя оценка сложности ЦУ решетки и верхняя оценка сложности декодирования ЦУ кодов.

Обозначим через £ = ¿//и нормированную сложность ЦУ решетчатой диаграммы линейного блокового кода. В обозначениях приведенной выше теоремы сложность решетки ц совпадает с к0у. Из теоремы 6.3 следует, что при достаточно большой длине кода существуют коды с нормированной сложностью

Забегая вперед, приведем асимптотическую оценку показателя экспоненты к(Л) сложности декодирования ЦУ кодов по максимуму правдоподобия:

где 5-к '(1-У?). Эта же величина к(К) является верхней границей сложности обычной решетки линейного кода. Этот факт можно доказать, используя алгоритм Кпшшчанга-Сорокина (1995 г.) для приведения матрицы в ЦУ приведенной форме к обычной матрице в минимальной форме.

Итак, (6.2) и (6.3) представляют собой верхние границы сложности соответственно ЦУ решеток и обычных решеток для линейных кодов, минимальное расстояние которых удовлетворяет асимптотической границе Варшамова-Гилберта. Отметим, что формулы (6.2) и (6.3) были известны до

£(Д) <! -¿то(Я)1о^(2'"*-1) = #„<*).

(6.2)

(6.3)

опубликования работы [11] как верхние оценки сложности декодирования обобщенных каскадных кодов (А. Барг, И. Думер, 1986 г.). Помимо этого, (6.3) совпадает с оценкой сложности декодирования но методу «ближайших соседей». Возможно, такое совпадение оценок объясняется как раз тем, что различные конструкции кодов и методы их декодирования по сути сводятся к поиску представления кода с помощью решетки с минимальной сложностью.

Рассмотрим теперь нижние границы сложности ЦУ решеток.

Из теоремы 6 2 получаем следующую асимптотическую оценку:

где Ят„(3) представляет собой верхнюю оценку скорости блокового кода с нормированным минимальным расстоянием 8 = (1тп / п. В качестве такой оценки можно использовать границу МакЭлиса-Родемича-Рамсея-Уелча. До границы (6.4) не было известно нижней границы сложности ЦУ решеток, однако, можно легко получить такую границу из границы Лафокардье-Варди (1995 г.) для обычных решеток. Эта граница всюду за исключением счетного числа значений скорости Я уступает в точности границе (6.4). Дело в том, что она совпадает с (6.4) по форме с той разницей, что параметру в разрешено принимать только значения обратные целым числам.

Рис. 6.4. Границы сложности решеток: 1 - граница Бала-Кука-Джелинека-Равива, 2 - граница /с(Я) (6.3), 3 - верхняя граница £,„ (Л) (6.2), 4 -нижняя граница (Я) (6.4), 5 - нижняя граница Лафокардье-Варди.

£(*) * шЖ* - Л™ (*'*))}=Ш).

(6.4)

06

■-1_I-' _

01 04 0£ 06 01 0» Щ гаи Р.

Верхние и нижние границы сложности решеток представлены на рис. 6.4.

Интересно отметить, что полученные границы сложности ЦУ решеток асимптотически точны в том смысле, что они не могут быть улучшены без улучшения известных верхних либо нижних границ на минимальное расстояние линейных кодов. Если в нижнюю границу сложности ЦУ решеток (6.4) вместо подставить границу Варшамова-Гилберта, то максимум

может быть вычислен аналитически и результат в точности совпадает с (6.2).

Больше того, граница (6.3) на сложность обычных решеток также асимптотически точна при условии асимптотической точности границы Варшамова-Гилберта. Этот факт доказан в 1983 г. В.В. Зябловым и В.Р.Сидоренко.

Заметим, что приведенные на рис. 6.4. границы представляют теоретический интерес как границы на сложность решеток, но не как границы на асимптотическую сложность декодирования. Оптимальное в смысле асимптотической сложности декодирование не обязательно выполняется с помощью эффективного представления кодов решетками. Наиболее точные оценки и обзоры методов декодирования для каналов с мягкими решениями приведены в работе Думера (2001 г.), а для декодирования в метрике Хэмминга - в работе Барга, Крука и Ван-Тилборга (1999 г.).

6.4. Поиск циклически усеченных кодов с заданным минимальным

расстоянием

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

Первая небольшая таблица кодов была приведена в работе [11]. Значительное продвижение в этом направлении было достигнуто в последующих работах [24,26-29] за счет усовершенствования алгоритмов поиска кодов и оценки их характеристик. Как и при поиске наилучших сверточных кодов, задача перебора по множеству всех генераторов имеет высокую вычислительную сложность. Поэтому среди двух задач: сокращение перебора по множеству кодов и вычисление минимального расстояния конкретного кода, первая оказывается более важной.

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

Использовались два класса способов сокращения множества генераторов-кандидатов на построение хорошего блокового кода. Первый класс

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

Тесты для отбора сверточных кодов.

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

• С помощью границы Грайсмера оцениваются минимально допустимые степени генераторов кодов и коды с меньшими степенями генераторов не рассматриваются.

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

• Вычисляется точное значение свободного расстояния <4« и коды с ^ггес < не рассматриваются.

Тесты для выбора ЦУ кодов.

• Вычисляются оценки весов коротких циклов в решетчатой диаграмме. На основании оценки веса цикла рассчитывается верхняя оценка минимального расстояния. Код отбрасывается, если оценка меньше требуемого

• Выбираются начальные состояния решетки подозрительные на то, что в этих состояниях начинаются пути минимального веса. Для этого всем начальным состояниям приписываются нулевые метрики, а ребрам нулевого пути приписываются бесконечные веса. Строим периодически повторяющуюся решетку, повторив J раз решетку исходного кода, и в этой периодической решетке находим пути минимального веса из произвольных узлов начального яруса на последний ярус. Небольшое число узлов с наименьшей метрикой (до 10) рассматриваем как узлы-кандидаты.

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

В результате поиска ЦУ кодов были не только найдены эффективные ЦУ решетки известных блоковых кодов, но и целый ряд новых линейных кодов и квазициклических кодов. Некоторые результаты приведены в Таблице 6.1.

В этой таблице в графе «Примечание» аббревиатурой ОС помечены новые квазициклические коды, IX - новые линейные коды, КС - новые линейные КЦ коды, параметры которых лучше параметров ранее известных (как линейных, так и нелинейных) кодов. Примечание ТУ(^) означает, что для данного кода существует представление с помощью изменяющегося во времени сверточного кода и сложность соответствующего ЦУ кода равна ¡л. В

частности, такое представление для кода (28,14) было найдено в [26] и оно приведено в таблице в квадратных скобках.

Таблица 6.1.

Примеры ЦУ кодов

(«.М„) Сложность Оценка Д Порождающие многочлены Примечание

Коды со скоростью Уг

(8,4,4) 2 2 1,7

(16,8,5) 3 2 3,13

(24,12,8) 6 4 37,105 ТУ(4)

(28,14,8) 6 4 37,153 [(13,15),(57,75)] ТУ(5)

(32,16,8) 5 4 13,75 ТУ(4)

(40,20,9) 6 6 115,171

(48,24,12) 12 8 717,14537 ТУ(8)

(56,28,12) 9 8 477,1505 ОС

(64,32,12) 8 8 235,557 ОС

(82,41,14) 10 10 1157,3455 ОС

(92,46,16) 13 11 5447,21675 N0

(110,55,18) 14 14 56235,63337 ОС

Коды со скоростью 1/3

(74,28,22) И 10 2215,5467,7647 ос

(96,32,24) 12 11 2153,11625,17557 ос

(9933,24) 11 И 4467,5725,6373 ОС

11°2-34.24) 11 11 4465,5357,6373 ОС

(105,35,25) 13 13 20447,25315,37317 КС

(108,36,26) 13 13 20465,31327,34773 ыс

(111,37,26) 13 13 20445,31527,35757 ьс

(114,38,26) 13 13 20445,31653,37673 ос

(114,38,27) 15 14 102165,65763,62467 ис

(120,40,28) 14 14 41127,63663,72575 ос

(150,50,33) 18 18 1716765,1626531,411233 ьс

КОДЫ СО СКОРОСТЬЮ '/4

(104,26,32) 12 И 4457,7715,13047,16565 КС

(112,28,32) 11 11 4447,5277,6335,7533 ос

(116,29,33) 12 12 15071,14477,13553,12355 ьс

(120,30,34) 13 13 23045,23053,24637,37557 ос

(136,34,37) 14 14 77673,62505,61535,44547 ьс

(140,35,37) 14 14 77673,51615,50631,45527 ьс

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

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

Часть представленных в таблице результатов получена в работе [27] при изучении кодов с большим средним весом циклов (большим наклоном касательной активного расстояния). Сужение множества рассматриваемых кодов и использование более совершенных методов анализа кодов (алгоритм BEAST) позволили увеличить длины кодовых ограничений сверточных кодов до 20.

Дальнейшие результаты поиска новых кодов с помощью BEAST были опубликованы в [33] В этой работе исследовался также вопрос о том, сколько различных начальных состояний нужно исследовать для точного определения минимального расстояния ЦУ кода. Нижняя граница числа начальных состояний для кодера с длиной регистра v определяется числом различных циклических представителей, содержащихся во множестве двоичных последовательностей длины v, т.е. числом двоичных последовательностей, циклические сдвиги которых порождают все множество последовательностей. Известная тачная формула для этого числа. В [33] предложена стратегия выбора начальных состояний (01-алгоритм), при которой число попыток ненамного отличается от нижней границы. Несколько новых линейных кодов было найдено благодаря применению BEAST и 01-алгоритма.

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

6.5. Декодирование циклически усеченных кодов

Проблема декодирования ЦУ кодов затрагивалась в самых первых работах Соломона, Ван-Тилборга и Ма и Вулфа, в которых впервые был предложен способ описания линейных кодов с помощью ЦУ решеток. Напомним, что кодовая решетка ЦУ кода содержит некоторое число начальных узлов (больше 1) и кодовыми словами являются последовательности, соответствующие путям, начинающимся и заканчивающимся в узлах с одинаковыми номерами.

Рассмотрим для простоты ЦУ код, получаемый из постоянного во времени сверточного кода с кодовым ограничением v со скоростью 1/и0. Сложность решетки также будет постоянной для всех ярусов и равной ju = v. Для того, чтобы воспользоваться алгоритмом Витерби, необходимо знать начальное состояние кодера или иными словами, нужно знать номер узла начального

яруса решетки. Поэтому естественным представляется следующий алгоритм декодирования.

Декодер поочередно выбирает в качестве гипотезы о начальном состоянии каждое из 2" начальных состояния кодера, и каждый раз находит наилучший путь в решетке в конечное состояние с тем же номером. Из всех 2" найденных таким образом решений выбирается наилучшее и выдается в качестве решения о персдшгном кодовом слове. Сложность такого алгоритма декодирования пропорциональна 22". Применительно к кодам из Таблицы 6.1 такое декодирование в большинстве случаев заметно проще перебора по множеству всех кодовых слов. Тем не менее, хотелось бы уменьшить показатель экспоненты сложности декодирования.

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

В подразделе 6.1. была описана конструкция ЦУ кода на основе сверточного кода. Одним из параметров кода было число нулей записываемых в регистры кодера в момент начала работы. От параметра зависит соотношение между максимальной сложностью решетки и сложностью на нулевом ярусе (числом стартовых узлов в ЦУ решетке). Анализ ЦУ кодов при произвольном значении 10 методом усреднения по ансамблю случайных кодов показывает, что минимум максимальной сложности достигается при ¿„=0. Однако минимум сложности декодирования по максимуму правдоподобия (с учетом перебора по множеству начальных узлов) достигается при ¿„>0. Минимизация показателя экспоненты вероятности ошибки по приводит к асимптотической оценке сложности декодирования (б.З). Как уже отмечалось, эгга граница совпадает с верхней границей сложности представления линейных кодов с помощью решеток.

Рассмотрим теперь алгоритмы неопгимального декодирования ЦУ кодов. Интуиция подсказывает, что возможность описания кода ЦУ решеткой с 2" узлами на каждом ярусе должна допускать декодирование со сложностью пропорциональной этой величине пусть за счет некоторого (незначительного) увеличения вероятности ошибки декодирования. Поиску алгоритмов декодирования ЦУ кодов со сложностью пропорциональной числу узлов его ЦУ решетки было посвящено большое число публикаций. Один из алгоритмов описан в работе [12].

Для описания алгоритма введем некоторые определения.

По-прежнему п - 1и0 обозначает длину кода, Ь - число ярусов решетки, щ - длину ребра. Скорость кода в данном случае считаем совпадающей со скоростью сверточного кода, порождающего блоковый ЦУ код, т.е. Я = Я0=к0/п. Число ребер, исходящих из каждого узла и входящих в узел решетки равно д - 2*° и общее число узлов на одном ярусе решетки равно д".

Обозначим через у = .....,>>„) последовательность на выходе канала,

полученную в результате передачи по каналу кодового слова х = (>,,...,*„). Декодирование по максимуму правдоподобия в канале без памяти с переходными вероятностями {р(у|зс)},;сеЛ_,>>бК предполагает отыскание среди кодовых слов кода слова, для которого максимальна функция правдоподобия или минимальна метрика

¿(х) = -1ойр(у | х) = -¿1о&р(у, | *,).

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

Для заданной последовательности у на выходе канала рассмотрим бесконечную периодическую решетчатую диаграмму, получаемую повторением исходной решетки. Ярусы решетки с номерами / и _/ такими, что г = ] гпос! Ь, полностью совпадают. Более того, периодической решетке соответствует периодически повторенная выходная последовательность канала у, поэтому при 1 - у то<1 £ совпадают также все метрики ребер ярусов / к ].

Распространим теперь понятие проверки узла на узлы произвольного яруса. При проверке узла с номером 1 яруса с номером I данному узлу приписывается нулевая метрика, остальным узлам этого яруса приписываются бесконечные метрики. Далее по алгоритму Витерби обрабатываются ярусы с номерами г+ 1,...,/ + £ и отыскивается путь с наименьшей метрикой в узел с номером I яруса с номером г + £. Метрика этого пути является результатом проверки данного узла.

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

Алгоритм.

Всем узлам нулевого яруса периодической решетки приписываются нулевые метрики. Последовательно обрабатываются с помощью алгоритма Витерби ярусы с номерами 1, 2, ..., М1. Тем самым для каждого из узлов яруса М- выявляется путь с минимальной метрикой, связывающий этот узел с одним из узлов нулевого яруса. Обозначим через Л(1) метрику узла с номером I. Для каждого из ц" путей длины М. ребер выполняются следующие вычисления.

Производится поиск таких отрезков путей, которые, имея длину А£, где И -целое число, начинаются и заканчиваются в узлах с одинаковыми номерами. Вычисляются метрики отрезков и нормируются делением на И. Максимальную

из полученных величин для пути, ведущего в узел /, обозначим через Я'(1). Если ни одного отрезка не найдено, полагаем Л*(/) = 0.

Лучшим узлом яруса МЬ считаем тот, для которого минимальна величина тах|л*(/)Д(/)/Л/}. Поочередно проверяются все узлы пути, ведущего в

лучший узел. Выбирается узел пути, при проверке которого получена наименьшая метрика. Если г - номер яруса, на котором располагается лучший узел, а и - соответствующая информационная последовательность, то решением декодера является циклический сдвиг и влево на <тоИ позиций.

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

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

Вычисление метрик л(1) имеет сложность порядка ЬМду, вычисление Л'(1) потребует не более Смъ<{ операций, анализ выигравшего пути потребует приблизительно 1}Мц" операций. С учетом того, что величины I и М пропорциональны V, общая вычислительная сложность пропорциональна у5д". Таким образом, показатель экспоненты сложности определяется сложностью ЦУ решетки кода.

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

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

Теорема 6.4. Для дискретного канала без памяти с переходными вероятностями \р(у\х)} существуют коды со скоростью Л = (1о%д)/п0<С длины п - Ьп„ с кодовым ограничением V, удовлетворяющим соотношению

ад/ад

при декодировании которых по описанному выше алгоритму вероятность ошибки удовлетворяет неравенству

P^K(n)txpl-nEb(R)},

где K(n) - степенная функция длины кода п.

В условиях теоремы Eb(R) и EC(R) - показатели экспонент случайного кодирования соответственно для блоковых и сверточных кодов, С -пропускная способность канала.

Итак, согласно теореме, декодирование «почти» по максимуму правдоподобия возможно с показателем экспоненты сложности, определяемым сложностью ЦУ решетки кода. Интересно, что в точности таким же оказывается полученный Баргом и Думером (1986 г.) показатель экспоненты сложности декодирования «почти» по максимуму правдоподобия для обобщенных каскадных кодов.

Мы вернемся к вопросу о декодировании ЦУ кодов еще раз ниже при рассмотрении алгоритма BEAST. Применение этого алгоритма позволяет дополнительно уменьшить сложность декодирования ЦУ кодов. Более того, оказывается, что при использовании этого подхода целесообразно перейти от ЦУ решетки к обычной решетке кода. При этом сложность обычной решетки примерно вдвое превышает сложность ЦУ решетки. Даже если представление кода ЦУ решетками не используется для декодирования, исследование этих решеток остается важной задачей, поскольку как было показано выше, в классе ЦУ кодов много хороших кодов с малой сложностью декодирования по максимуму правдоподобия.

Завершая раздел, перечислим основные результаты исследования ЦУ кодов:

• введены понятия минимальных секционировнных и несекционированных решеток для ЦУ кодов и установлена связь структуры порождающей матрицы кода со сложностью решетки;

• получены нижние границы сложности ЦУ решеток блоковых кодов;

• введен ансамбль случайных ЦУ кодов и получены асимптотические границы сложности ЦУ решеток и сложности декодирования ЦУ кодов;

• разработаны методы анализа ЦУ кодов и способы ускоренного перебора по множеству ЦУ кодов;

• построены новые квазициклические и линейные коды с характеристиками лучшими характеристик лучших известных блоковых кодов;

• предложены эффективные алгоритмы декодирования ЦУ кодов.

7. Алгоритм BEAST и его применение для анализа характеристик и для декодирования сверточных и блоковых кодов

В данном разделе мы рассматриваем новый алгоритм анализа характеристик сверточных кодов. Этот алгоритм был впервые описан в работе [25] и был назван BEAST как аббревиатура от "Bidirectional Efficient Algorithm for Searching Trees" (Двусторонний эффективный алгоритм для исследования деревьев). Первоначально он предназначался для нахождения минимального

расстояния и спектральных коэффициентов сверточных кодов. Позже этот же алгоритм был модифицирован применительно к задачам исследования ЦУ кодов и декодирования блоковых кодов, представленных решетками. В подразделе 7.1 мы рассмотрим сам алгоритм, затем в подразделе 7.2 будут представлены результаты, связанные с поиском новых сверточных кодов. Далее мы рассмотрим применение алгоритма для поиска новых ЦУ кодов. Последние разделы посвящены задачам декодирования с использованием BEAST Мы приведем результаты моделирования декодирования по максимуму правдоподобия и декодирования с ограничением на сложность или объем памяти декодера.

7.1. Описание алгоритма BEAST

Начнем с описания алгоритма вычисления свободного расстояния и первых коэффициентов спектра сверточного кода на примере кода с кодовым ограничением 2, скоростью 1/2 с порождающими многочленами в восьмеричной форме (7,5).

На рис.7.1 иллюстрируется прямолинейный подход к подсчету свободного расстояния и двух первых коэффициентов cneiopa. Мы строим дерево, корень которого - начальный узел решетки. Первое ребро одно - это ненулевое ребро, исходящее из начального узла. Далее дерево «выращивается» до тех пор, пока существуют ненулевые узлы веса меньше dtm +1. На рис.7.1 узлы дерева соответствуют состояниям кодера, ребрам сопоставлены кодовые символы, в узлах курсивом написаны веса путей, ведущих в эти узлы.

Сложность поиска расстояния можно характеризовать числом обследованных узлов кодового дерева В данном случае для поиска числа путей веса d!la - 5 и веса dhcc +1 = 6 потребовалось обследовать 19 узлов. Число обследуемых узлов можно уменьшить, если для описания кода вместо кодового дерева использовать решетчатую диаграмму. В этом случае достаточно обследовать 13 узлов.

Идея алгоритма двустороннего поиска состоит в том, что для поиска путей веса d строится 2 дерева, прямое и обратное, причем каждое из них продолжается до тех пор, пока веса путей не превысят порог приблизительно равный d! 2. Действительно, при длине ребра 2 вес ребра не превышает 2 Следовательно, в любом пути веса d есть некоторый узел такой, что вес пути, ведущего в узел, не больше dl2, а вес оставшейся части пути не больше dl 2+1. Таким образом, вместо одного большого дерева строим 2 маленьких дерева. Если в числе концевых вершин обоих деревьев есть пути, соответствующие одинаковым состояниям кодера, подсчитываем их суммарный вес и сравниваем с требуемым значением. При большом кодовом ограничении поиск согласованных узлов в двух деревьях может быть ускорен с помощью сортировки номеров состояний, соответствующих концевым вершинам обоих деревьев.

Вернемся к рассмотрению кода (7,5). Для поиска слов веса 5 и 6 достаточно рассмотреть в прямом и обратном дереве пути веса 2 и 3. Соответствующие деревья показаны на рис. 7.2. Согласованными в этих деревьях являются: состояние 10, через которое проходит путь веса 5 и состояния 01 и 11, через которые проходят пути веса 6. Заметим, что в построенных деревьях можно найти «лишние» пути веса 5 и 6. Ниже алгоритм будет сформулирован таким образом, чтобы избежать неоднозначности в подсчете числа слов заданного веса. Отметим, что даже в данном очень простом примере для отыскания всех путей веса 5 и 6 потребовалось обследовать всего 6 узлов С увеличением кодового ограничения выигрыш по сложности быстро увеличивается.

Рис.7.1. Кодовое дерево сверточного кода (7,5)

ооЛ(оо

Jljул,

\f®^ f^i/

\/ ll\ 10/ ^^ х ю /"

V/ №>io\ (oi< 00 X/

Л®)xi^(®М

V ; УV 2 J

fix

чА/

Рис. 7.2. Иллюстрация алгоритма BEAST на примере кода (7,5)

Итак, сформулируем точно алгоритм BEAST для поиска числа слов заданного веса d. Для этого для произвольного узла s обозначим через ^(i) вес пути из начального узла в узел s, через w<(i) - вес пути из заданного узла s в нулевой узел. При заданном d введем в рассмотрение два множества узлов, принадлежащих, вообще говоря, различным ярусам решетки:

где через sp обозначен узел, предшествующий узлу s, а через / обозначен потомок узла s.

Алгоритм BEAST

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

2. Выполнить сортировку узлов обоих множеств по возрастанию номеров состояний.

3. Подсчитать число узлов s таких, что w>(s) + w<(s) = d. Это число равно числу кодовых слов веса d.

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

оценка d"B свободного расстояния, например, как сумма весов генераторов. Далее проверяются гипотезы о том, что свободное расстояние равно dUB~\,

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

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

dm-2.

Наиболее распространенным методом анализа сверточных кодов является предложенный в 1989 г. М. Цедервалом и Р. Йоханнесоном алгоритм FAST. На рис. 7.3 показана зависимость числа обрабатываемых узлов от длины кодового ограничения для кодов со скоростью 1/2 при использовании двух алгоритмов. Графики показывают, что применение BEAST позволяет при одинаковой сложности анализировать коды с кодовым ограничением на 5-6 единиц больше, чем FAST.

Рис. 7.3. Зависимость числа обрабатываемых узлов от длины кодового ограничения

В действительности, ближайшим прототипом алгоритма BEAST является алгоритм Руана-Костелло (1989 г.). Алгоритм Руана-Костелло (РК) также является алгоритмом двунаправленного поиска. Узлы двух деревьев, прямого и обратного, хранятся в виде списков узлов, сортированных по убыванию веса ведущих в эти узлы путей. На каждом шаге выбирается узел минимального веса и обрабатывается. Сам узел удаляется из списка, а вместо него записываются его потомки. При этом список должен быть переупорядочен. Принципиальное различие между алгоритмами BEAST и РК состоит в том, что сортировка в алгоритме BEAST делается один раз - в конце работы алгоритма. В работе [33] приведены результаты моделирования и подсчета сложности двух алгоритмов при вычислении спектров одинаковых кодов. В частности, при вычислении 11 коэффициентов спектра кода с кодовым ограничением 19 алгоритм РК потребовал в 14000 раз большего числа сравнений, чем BEAST.

Наглядным подтверждением эффективности BEAST являются результаты поиска новых сверточных кодов, представленные в работах [27] и [33]. Таблица 7.1 представляет собой таблицу лучших известных сверточных кодов с

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

В таблице 7.1 примечание (ЮР означает, что данный код был найден перебором по множеству кодов с оптимальным профилем расстояний. Этот класс кодов введен в рассмотрение Р. Йоханнессном. Как известно, этот класс кодов содержит большинство сверточных кодов с максимальным свободным расстояний и наилучшим спектром. Примечание ОГО означает, что код не принадлежит классу ООР-кодов и является наилучшим в смысле свободного расстояния и спектра при заданном свободном расстоянии. Записанная в квадратных скобках цифра 2 указывает на коды, опубликованные ранее в монографии Зигангирова-Йоханнессона. Коды, помеченные цифрой 4 в квадратных скобках, получены в работе [27].

Таблица 7.1.

Сверточные коды со скоростью 1/2

III <11 ''f. rr Weight spectrum Remarks

15 126723 152711 19 30,67,54,167,632 OFD [2]

16 313327 231721 20 43,0,265,0,1341 OFD [2]

17 573443 636055 20 4,24,76,150,354 OFD

18 1132317 1473071 22 65,0,349,0,1903, OFD [2]

19 2312737 3642215 22 5,52,116,163,456 OFD

20 6717423 5056615 24 145,0,225,0,3473 OFD [4]

21 12531363 16424475 24 17,95,136,138,679 OFD

22 31147141 23665613 25 47,88,137,313,912 OFD [4]

23 41502757 63462531 26 51,0,360,0,1925 OFD

24 107132303 164227731 26 2,52,149,163,477 OFD

25 361730635 224433277 27 24,57,121,279,609 ODP [2]

26 625323525 447550513 28 24,56,131,273,736 ODP

27 1625677267 1230732361 28 1,24,78,142,328 ODP

28 2667445037 3454256175 30 54,0,356,0,2148 ODP

29 6371263067 5573103645 30 5,47,97,211,514 ODP

30 14361445777 11650553351 31 12,53,103,265,658 ODP

31 20162726673 32242417377 32 17,92,157,345,874 ODP

32 42272202625 71430067567 32 1,38,77,164,401 ODP

33 156573157111 126512623243 34 53,0,377,0,2357 ODP

34 224760463227 364537330525 34 6,39,113,253,570 ODP

35 653621462151 506520556617 35 11,49,132,322,710 ODP

36 1334721177325 1723154676607 36 31,0,291,0,1619 ODP

37 3203477047427 2063312237025 36 2,26,73,195,403 ODP

38 7021157014311 5027177127057 38 62,0,454,0,2378 ODP

39 11553101500241 17766535140727 38 11,29,122,264,573 ODP

40 33007476704105 25153315275027 39 15,41,117,292,686 ODP

7.2. Использование BEAST для декодирования блоковых кодов

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

Мы рассмотрим два варианта постановки задачи. В первом случае мы будем требовать, чтобы решение, принимаемое декодером, в точности совпадало с решением по критерию максимума правдоподобия. В этих условиях на примерах конкретных кодов мы оценим вычислительную сложность и объем памяти декодера. Исследование этого декодера выполнено в работе [33].

Вторая постановка задачи предполагает, что на объем памяти декодера наложено ограничение и в случае переполнения памяти декодер принимает решение, даже если путь с максимальной функцией правдоподобия еще не найден. Такой декодер, строго говоря, уже не является декодером максимального правдоподобия, но обменные соотношения между вероятностью ошибки и сложностью для такого декодера лучше, чем в первом варианте постановки задачи. Результаты исследования BE AST-декодера с ограничением на сложность опубликованы в [32].

Предположим, что двоичный блоковый код используется для передачи информации двоичными противоположными сигналами по каналу с аддитивным белым гауссовским шумом. Обозначим через Е энергию элементарного сигнала, через А^ спектральную плотность мощности шума. Двоичной кодовой последовательности с = (с,,...,с„) соответствует сигнальная последовательность вида х = (х,,...,х„), где х, =(1-2c,)Ve. На выходе канала наблюдается последовательность г = (/;,...,гп), элементы которой равны г, = xi + п,. Слагаемые п, представляют собой значения шума.

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

Удобно представить принятую последовательность г в виде двух последовательностей: последовательности «жестких решений» у1 =51яп(дг,) и их надежностей а, = . С помощью несложных преобразований

(7.1)

декодирование по максимуму скалярного произведения (7.1) сводится к декодированию по минимуму «взвешенного расстояния Хэмминга»

м*, г).';).

(7.2)

где

встх,*у„ если*, = у¡.

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

Алгоритм BEAST для декодирования с мягкими решениями.

1. По принятой последовательности г выбираем начальное значение расстояния d и величину приращения расстояния 5.

2. Строим два древовидных множества узлов (прямое F и обратное В) по

правилу

F = {i:A(i)> |>A(,')<|J,

Вш

где обозначает метрику пути из начального узла решетки в узел i, а

^(s) - метрику пути из конечного узла решетки в узел s.

3. Выполняем поиск согласованных узлов (узлов, соответствующих одинаковым состояниям кодера и таких, что сумма длин путей, ведущих в узлы, равна длине кода п). Если такие узлы найдены, находим узел с наименьшей метрикой и соответствующий ему путь считаем решением о переданном кодовом слове. Если решение не найдено, увеличиваем d на величину приращения 5 и возвращаемся к шагу 2.

Пусть х - кодовая последовательность, на которой достигается минимум взвешенного расстояния при заданной последовательности г на выходе канала. При некотором d> /*(х,г) и правильно выбранном (достаточно малом) S алгоритм найдет правильное решение х. Число итераций зависит от выбора параметров db и 8. Точнее говоря, от этих параметров зависит число попыток сортировки и поиска согласованных путей. Число обрабатываемых узлов от этих параметров практически не зависит. Оно определяется кодом и последовательностью г на выходе канала.

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

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

Теорема 7.1. Предположим, что декодер BEAST используется для декодирования последовательности г по критерию минимума некоторой метрики /j(v), удовлетворяющей аксиомам метрики. Если расстояние г до ближайшего кодового слова х удовлетворяет неравенству

где - минимальное расстояние кода в метрике //(-,-)> то число узлов, обрабатываемых при декодировании по алгоритму BEAST, не превышает числа узлов, обрабатываемых по алгоритму Витерби.

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

Теорема утверждает, что, если принятая последовательность г находится в сфере радиуса вокруг некоторого кодового слова, то BEAST найдет ближайшее к г кодовое слово, обработав не больше узлов, чем декодер Витерби. Указанное ограничение на расстояние между г и кодом не является существенным по двум причинам. Во-первых, известно, что декодирование в радиусе d^ лишь незначительно проигрывает по вероятности ошибки декодированию по максимуму правдоподобия. Во-вторых, для «хороших» кодов радиус покрытия в метрике //(,-) не превышает d^, поскольку в противном случае объем кода может быть увеличен без увеличения длины и уменьшения минимального расстояния.

Более детальный анализ вычислительной сложности алгоритма BEAST является предметом дальнейших исследований.

Сложность декодирования конкретных блоковых кодов по максимуму правдоподобия проиллюстрируем на примере линейного кода (92,46) с минимальным расстоянием 16. Этот код был построен как ЦУ код в работе [26]. Сложность его ЦУ решетки равна 13, следовательно, для него можно построить обычную решетку со сложностью 26. Графики зависимости сложности декодирования по максимуму правдоподобия от отношения сигнал/шум для различных алгоритмов декодирования представлены на рис. 7.4. Максимальная сложность декодирования не зависит от характеристик канала, она однозначно определяется свойствами кода. Как видно из графиков, BEAST обрабатывает примерно в 16 раз меньше узлов, чем декодер Витерби. При этом среднее число вычислений, выполняемых декодером, во много раз меньше максимального числа.

24

22

. 2

21

IX

16

14

12

10

—>— Simulated average of logo Чл

0 0.3 1 1.5 2 2.0 3 3.5 Еь/No [dB]

Рис 7.4. Логарифм числа обрабатываемых узлов как функция отношения сигнал/шум для кода (92,46,16). Кривая (1) - сложность декодирования по алгоритму Витерби, (2) - максимальная сложность декодирования (92,46,16) как ЦУ кода, (3) - максимальная сложность декодирования (92,46,16) как обычного решетчатого кода, (4) - средняя сложность декодирования (92,46,16) как ЦУ кода, (5) - средняя сложность декодирования (92,46,16) как обычного решетчатого кода

Сложность декодирования конкретных блоковых кодов по максимуму правдоподобия проиллюстрируем на примере линейного кода (92,46) с минимальным расстоянием 16. Этот код был построен как ЦУ код в работе [26]. Сложность его ЦУ решетки равна 13, следовательно, для него можно построить обычную решетку со сложностью 26. Графики зависимости сложности декодирования по максимуму правдоподобия от отношения сигнал/шум для различных алгоритмов декодирования представлены на рис. 7.4. Максимальная сложность декодирования не зависит от характеристик канала, она однозначно определяется свойствами кода. Как видно из графиков, BEAST обрабатывает примерно в 16 раз меньше узлов, чем декодер Витерби. •

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

Рис. 7.5. Зависимость вероятности ошибки декодирования кода (48,24,12) от ограничений на объем памяти декодера

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

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

Переформулируем алгоритм декодирования с учетом ограничения на максимальную сложность.

Алгоритм BEAST для декодирования с ограничением на объем памяти декодера

1. По принятой последовательности г выбираем начальные пороги Tf и Тв и величину приращения расстояния S. Множества F и В в начале работы декодера содержат по одному узлу, соответствующему нулевому состоянию кодера.

2. Если |f|>]B|, выбираем для продолжения множество В и увеличиваем порог Тв на (У, в противном случае выбираем для продолжения множество F и увеличиваем порог TF на 5.

3. Расширяем выбранное множество, дополняя его узлами в соответствии с правилом

если выбрано и правилом

В = {*://;(*) <Г,,Л(^)> Г,},

если выбрано В. Операция может быть закончена раньше, чем сформировано множество, если суммарное число узлов в множествах превысит порог Л^ 4. Сортируем узлы построенного множества и проверяем на наличие согласованных узлов с узлами второго множества. Если согласованных узлов нет и допустимый объем памяти не превышен, возвращаемся на шаг 2. Если согласованные пути есть, кодовое слово, соответствующее пути с наилучшей метрикой, выбирается в качестве результата декодирования. Если же превышен объем памяти, выдаются информационные символы, соответствующие наиболее «длинным» путям деревьев В.

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

N N

Рис.7.6. Структура порождающей матрицы и профиль сложности кода (48,24)

Исследование обменных соотношений между сложностью декодирования и вероятностью ошибки в работе [33] выполнено с помощью моделирования работы декодера на примерах нескольких конкретных кодов. На рис. 7.5. показана зависимость вероятности ошибки от ограничений на объем памяти для кода (48,24). Как показали результаты моделирования, при объеме памяти 2'2 вероятность ошибки ВЕАвТ-декодера совпадает с вероятностью ошибки декодирования по максимуму правдоподобия, а при памяти 2" проигрыш несущественен. Известно, что линейная сложность кода (48,24) равна 16. Более детально структура порождающей матрицы и профиль сложности кода

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

На рис. 7.7 представлены результаты моделирования работы BEAST-декодера кода (48,24). При максимальной сложности решетки равной 16 декодер Витерби обрабатывает приблизительно 2'5 узлов в расчете на один информационный символ. Максимальное количество узлов, обрабатываемых BE AST-декодером, не превышает 7ю. С увеличением отношения сигнал/шум сложность декодера становится еще меньше, а среднее количество вычислений в расчете на информационный символ чрезвычайно мало.

Подведем итоги исследования алгоритма BEAST:

• предложен эффективный алгоритм поиска свободного расстояния и спскгра сверточных кодов;

• построены таблицы сверточных кодов с большой длиной кодового ограничения;

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

Рис. 7.7. Зависимость количества обрабатываемых узлов от ограничений на память декодера и от отношения сигнал/шум в канале

Заключение

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

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

За рамками данного доклада остались результаты также связанные с приложениями сверточных кодов и опубликованные автором в различных изданиях. Отметим некоторые из них:

— Недвоичные сверточные коды для каналов с ортогональными сигналами [16].

— Вычисление спектров расстояний для сигнально-кодовых конструкций [21].

— Вычисление оценок радиусов покрытия сверточных кодов [20].

— Сверточные коды с большим наклоном касательной активного расстояния (с большим средним весом циклов в решетке) [27,29].

— Построение блоковых кодов с малой сложностью решетки [30,31,34].

— Применение сверточных кодов в задачах сжатия информации [22].

Некоторые новые результаты не вошли в данный доклад, но содержатся в работах уже представленных к опубликованию. В частности, на симпозиум ISIT-2004 представлены тезисы доклада о новом алгоритме декодирования блоковых кодов по максимуму апостериорной вероятности [35]. Этот алгоритм основан на списочном декодировании блокового кода, которое, в свою очередь, эффективно выполняется с помощью модификации алгоритма BEAST.

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

получение аналитических оценок сложности декодирования блоковых кодов с помощью BEAST1;

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

комбинаторные методы построения сверточных кодов с заданными характеристиками;

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

Список литературы

1. Кудряшов БД. Блоковое и неблоковое кодирование в каналах с обратной связью. Вопросы кибернетики. Вып.34,1977

2. Кудряшов Б. Д., Полтырев Г. Ш. Границы вероятности ошибки для кодов с фиксированной композицией. VII Всесоюзная конференция по теории кодирования и передачи информации. Доклады. Часть 2. с. 87-92, 1978.

3 Кудряшов Б Д. О передаче сообщений по дискретному каналу с бесшумной обратной связью. Проблемы передачи информации, 1979, у.15,1,4-15.

4. Кудряшов Б. Д., Полтырев Г. Ш.. Верхние границы вероятностей ошибок декодирования в некоторых широковещательных каналах. Проблемы передачи информации, 1979, Т. 15,3,3-17.

5. Кудряшов Б. Д. Применение алгоритма Витерби для декодирования сверточных кодов в системе с решающей обратной связью. Проблемы передачи информации, 1984, Т. 20,2,18-26.

6. Кудряшов Б Д. Сверточно-блоковое кодирование в системах с решающей обратной связью. Проблемы передачи информации, 1985, у.21,1,17-27.

7. Балакирский В Б., Кудряшов Б Д Составные сверточные коды. IX Симпозиум по проблеме избыточности в информационных системах. Л., 1986,4.1., 73-76.

8. Кудряшов Б Д., Колесник В. Д. Некоторые функции от Марковских

1 К моменту опубликования данного доклада в совместной работе с И.Е Бочаровой, Р.Йоханнесоном, M.Handlery получены асимптотические оценки сложности декодирования по алгоритму BEAST. Доказано, что в широком диапазоне скоростей кодов сложность BEAST меньше, чем сложность других известных алгоритмов. Результаты работы представлены в виде доклада на 42 конференцию по связи, управлению и вычислительной технике,. Allerton, Illinois, USA, October, 2004 и представлены к опубликованию в виде статьи в журнал IHEH Transactions on Information Theory

цепей и определяемые ими случайные блуждания с поглощающими экранами. Проблемы передачи информации, 1988, Т. 24,3, 83-93.

9. Балакирский В. Б , Кудряшов Б. Д. Декодирование сверточных кодов с использованием списков. Проблемы передачи информации, 1989, Т 25, 1,16-23.

10. Кудряшов Б.Д., Кирилкж В.Н. Эффективность списочного декодирования сверточных кодов. Тр. X симпозиума по проблеме избыточности в информационных системах. 4.1, Л., 1989, С. 137-140.

11. Кудряшов Б. Д., Захарова Т. Г. Блоковые коды, получаемые из сверточных. Проблемы передачи информации, 1989, Т. 25, 1,16-23.

12. Кудряшов Б. Д., Декодирование блоковых кодов, получаемых из сверточных. Проблемы передачи информации, 1990, v.26, 2,18-26.

13. Бочарова И. Е., Кудряшов Б Д Сверточные коды для передачи информации ортогональными сигналами. Спутниковая связь. Реальность и перспективы. Тр. Междун. Симп. 1-5 Окт., 1990, В.12.1-В.12.10.

14. Кудряшов Б. Д. Списочное декодирование в канапе с гауссовским шумом. Проблемы передачи информации, 1991, Т. 27,1,30-38.

15. Бочарова И. Е., Кудряшов Б. Д. Построение модели дискретного отображения для каналов с замираниями. Проблемы передачи информации, 1993, Т. 29,1, 58-67.

16. Бочарова И. Е., Кудряшов Б. Д. Сложность декодирования и спектры недвоичных сверточных кодов. Радиотехника, 1996, № 12.

17 Kolesnik V.D., Kudryashov B.D. On model constructing problem for some discrete channels. Forth Joint Swedish-Soviet International Workshop on Information Theory, Gotland, Sweden, 1989,127-131

18 Kudryashov B.D., Soft decoding for block codes obtained from convolutional codes. Lecture notes in computer science, 573. Algebraic Coding, 1991, 113119.

19. Kudryashov B. D. Error probability for repeat request systems using convolutional codes. IEEE Transactions on Information Theory, 1993. v.39, No. 5, 1680-1684.

20. Bocharova I.E., Kudryashov B.D. On the covering radius of convolutional codes. Lecture Notes in Computer Science, 781. 1994, 56-62.

21. Trofimov A. N., Kudryashov B. D. Distance spectra and upper bound on error probability for trellis codes. ŒEE Transactions on Information Theory, v.41, No. 2, 561-572, 1995.

22 Bocharova I.E., Kolesmk V.D., Krachkovsky V.Yu., Kudryashov B.D., Ovsyjannikov E.P., Trojanovsky B.K. On trellis codes for linear predictive speech coding. Lecture Notes in Computer Science, 829. 1993, 115-121.

23 Bocharova I. E., Kudryashov B. D. Rational rate punctured convolutional codes for soft-decision Viterbi decoding. ŒEE Transactions on Information Theory, v.43, No. 4,1305-1314,1997.

24. Bocharova I.E., Johannesson R, Kudryashov B.D., Stâhl P. Searching for tailbiting codes with large minimum distances. International Symposium on Information Theory ISIT-2000, Italy, Sorento, June, 2000, p.341.

25. Bocharova I. E., Handlety M., Johannesson R, Kudryashov B. D.. Prowling with the BEAST. 39th Annual Allerton Conf. On Communications, Control and Computing. Allerton House, Montichello, Illinois, 3-5, October, 2001.

26. Bocharova I. E., Johannesson R., Kudryashov B. D., Stâhl P. Tailbiting codes: bounds and search results IEEE Transactions on Information Theory, v.48, No. 1,137-148,2002.

27. Bocharova I. E., Hardlery M., Johannesson R., Kudryashov B. D. Tailbiting codes: obtained via convolutional codes with large active distance-slopes. IEEE Transactions on Information Theory, v.48, No.9, 2577-2587,2002.

28. Bocharova I. E., Handlery M., Johannesson R., Kudryashov B. D. How to efficiently find the minimum distance of tailbiting codes. International Symposium on Information Theory ISIT-2002, Lausanne, Switzerland, June30-July,5, 2002.

29. Bocharova I. E., Handlery M., Johannesson R., Kudryashov B. D. Convolutional codes with large slopes yield better tailbiting codes. International Symposium on Information Theory ISIT-2002, Lausanne, Switzerland, June30-July,5, 2002

30. Bocharova I. E., Handlery M., Johannesson R., Kudryashov B. D. Trellis representation for quasi-cyclic codes. 8th International workshop on algebraic and combinatorial coding theory Proceedings, 8 -14 September, 2002, Tsarskoe Selo, Russia

31 Bocharova I. E., Johannesson R., Kudryashov B. D. Low state complexity block codes via convolutional codes. International Symposium on Information Theory ISIT 2003, June 29 - July 4, Yokohama, Japan, 2003.

32 Bocharova I. E., Johannesson R., Kudryashov B. D., Loncar M. BEAST decoding for block codes. 5th International ITG Conference on Channel and Source coding. January 14-16, Erlangen, 2004.

33. Bocharova I. E., Handlery M., Johannesson R., Kudryashov B. D. A BEAST for prowling in trees. IEEE Transactions on Information Theory, v. 50, pp.1295-1300, June 2004.

34. Bocharova I. E., Johannesson R., Kudryashov B. D. Low state complexity block codes via convolutional codes, IEEE Transactions on Information Theory, v. 50, Sept. 2004.

35 Bocharova I. E., Johannesson R., Kudryashov B. D., Lonôar M. On APP-decoding using BEAST. International Symposium on Information Theory ISIT 2004, June 27 - July 2, Chicago, Illinois, USA, 2004.

СОДЕРЖАНИЕ

Введение 4

1. Сверточные коды в каналах с обратной связью 6

2. Сверточные коды в широковещательных каналах 12

3. Списочное декодирование сверточных кодов 17

4. Анализ характеристик кодов в каналах с памятью 21

5. Построение и анализ сверточных кодов с заданной сложностью декодирования в канапе с мягкими решениями 25

6. Построение и асимптотические границы сложности декодирования блоковых кодов, получаемых из сверточных 28

6.1 .Минимальные ЦУ решетки блоковых кодов 29

6.2.Верхние границы на минимальное расстояние циклически усеченных кодов 33

6.3. Асимптотические границы сложности решетчатого представления циклически усеченных кодов 34

6.4. Поиск циклически усеченных кодов с заданным минимальным расстоянием 38

6.5. Декодирование циклически усеченных кодов 41

7. Алгоритм BEAST и его применение для анализа характеристик и для декодирования сверточных и блоковых кодов 45

7.1. Описание алгоритма BEAST 46

7.2. Использование BEAST для декодирования блоковых кодов 51

Заключение. 58

Список литературы 59

Формат 60x841/16. Бумага офсетная. Печать офсетная. Тираж 100 экз. Заказ № 334 Отдел оперативной полиграфии ГОУ ВПО «СПбГУАП» 190000, Санкт-Петербург, ул. Б. Морская, 67

РНБ Русский фонд

2006^4 19125