автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему: Характеристики и алгоритмы декодирования сверточных кодов в системах связи
Автореферат диссертации по теме "Характеристики и алгоритмы декодирования сверточных кодов в системах связи"
На правах рукописи
Кудряшов Борис Давидович
Характеристики и алгоритмы декодирования сверточных кодов в системах связи
05.13.01 - Системный анализ, управление и обработка информации 05.13 13 - Телекоммуникационные системы и компьютерные сети
Диссертация в виде доклада на соискание ученой степени доктора технических наук
Работа выполнена в государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения»
Доктор технических наук профессор Зяблов В. В. Доктор технических наук профессор Габидулин Э. М. Доктор физико-математических наук профессор Дьячков А. Г.
Санкт-Петербургский институт информатики и автоматизации РАН
Защита состоится ^ ^ 2004 г. на заседании диссертационного совета Д.002.077.01 Института проблем передачи информации Российской академии наук, по адресу: 127994, Москва, ГСП-4, Большой Каретный, 19
С диссертацией в виде научного доклада можно ознакомиться в библиотеке Института проблем передачи информации РАН.
Диссертация в виде научного доклада разослана
Ученый секретарь диссертационного совета Д.002.077.01 доктор физико-математических наук
Тема работы - анализ характеристик и методы декодирования сверточных кодов. Сверточные коды в последние десятилетия все шире применяются в различных системах помехоустойчивой передачи и надежного хранения информации. Среди важных приложений сверточных кодов достаточно отметить их применение в модемах для телефонных линий и для сотовой связи, в магнитных накопителях информации с высокой плотностью записи, в системах дальней космической связи.
Вместе с тем, продолжается научный поиск в области построения эффективных сверточных кодов и каскадных конструкций на их основе. Развитие технологии реализации устройств кодирования и декодирования на базе интегральных микросхем и сигнальных процессоров существенно расширяет круг технически реализуемых решений. Этим стимулируется интерес к исследованиям в данной области. Таким образом, тема работы весьма актуальна.
Данный доклад подводит итог многолетней работы автора над задачами, связанными с теорией и практикой применения сверточных кодов в системах связи. Во введении приведен краткий обзор результатов. Первый раздел посвящен исследованию характеристик сверточных кодов в системах с обратной связью. Основной метод исследования - метод случайного кодирования Эта техника развивается во втором разделе, где мы рассматриваем широковещательные системы связи.
В разделе 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) для оптимальной мультипликативной метрики, конечно, невозможно. Метрика была получена аналитически максимизацией показателя экспоненты средней по множеству кодов вероятности ошибки по множеству всевозможных мультипликативных метрик.
Алгоритм декодирования сверточных кодов в системе с обратной связью состоит в следующем. Ярус за ярусом решетка сверточного кода размечается приписыванием узлам решетки меток (7 (хороший узел) либо В (плохой узел). Метка С? приписывается узлу, если для одного из путей, сходящихся в узле, введенная выше функция <р превышает пороговое значение. В противном случае узлу приписывается метка В. Если на достаточном удалении т от данного яруса сохранились узлы, помеченные б, пути, ведущие в эти узлы, используются для принятия решения о данном символе. Параметр г определяет задержку декодирования. Если же все узлы на глубине г помечены В, происходит передача запроса на повторение условленного числа кодовых символов и возвращение декодера на заданное число ярусов назад.
Асимптотический анализ данного алгоритма приводит к следующему результату.
Теорема 1.1. Для любого е>0 существуют т0(е) и у„(е) такие, что при т > т0(е) и V >у„(£-) существуют сверточные коды с кодовым ограничением у и скоростью Л такие, что при использовании описанного выше алгоритма с задержкой декодирования т вероятность ошибки декодирования Ре и средняя скорость передачи Я удовлетворяют неравенствам
Соотношение между показателем экспоненты вероятности ошибки для систем с обратной связью с использованием сверточных кодов £/е (Л) и полученным Форни показателем экспоненты для систем на основе блоковых кодов Ег (Л) показано на рис 1.1. Эти кривые соответствуют двоичному симметричному каналу с переходной вероятностью р = 0,1.
Рис. 1.1. Показатели экспоненты вероятности ошибки для систем с решающей
Отметим примечательный факт: экспоненты Е/с(Я) и связаны
графическим построением аналогичным тому, которое связывает обычные экспоненты блоковых и сверточных кодов (для систем без обратной связи). Эту связь называют «обратной каскадной конструкцией», поскольку впервые она была получена в связи с каскадными кодами. Точки кривой Е/с(К) являются правыми верхними вершинами прямоугольников, две грани которых
совпадают с осями координат, а диагонали - касательные к ЕР(К). Заметим также, что Е/с(К) - выпуклая вверх функция, принимающая достаточно
большие значения при скорости близкой к пропускной способности канала.
Асимптотические результаты, сформулированные в Теореме 1.1 и представленные на рис. 1.1, получены на основе экспоненциально сложного алгоритма декодирования. Естественное направление развития исследований -поиск алгоритмов, которые, сохраняя потенциальные преимущества неблоковых методов, допускали бы простую практическую реализацию. Решение этой задачи было получено в работе [6].
Сверточно-блоковое кодирование, предложенное в [6], построено по каскадному принципу. «Внутренним» методом передачи является обычная система с решающей обратной связью на основе блоковых кодов. «Внешний» метод - передача сверточным кодом с декодированием, похожим на последовательное декодирование сверточных кодов. Декодер сверточного кода, когда он обнаруживает, что выбранный им путь в кодовом дереве неудачен, посылает по каналу обратной связи сигнал запроса. При этом кодер и декодер возвращаются назад на заданное число ребер, и повторяется передача некоторого числа ранее переданных ребер (кодовых слов блокового кода).
Опишем этот метод более точно на примере симметричного канала с двоичным входом. Предположим, что в качестве блокового кода используется некоторый линейный (иД)-код. Обозначим через и1,и2. подлежащие передаче двоичные блоки из к информационных символов. Последние Г поступивших от источника и переданных по каналу блоков информационных символов хранятся в памяти кодера и декодера, а последние у из них определяют текущее состояние сверточного кодера. Сверточный кодер после получения от источника очередного блока информационных символов и, вычисляет соответствующее кодовое слово линейного (п,к)-кода с,. Помимо этого кодер вычисляет блок Ь,, состоящий из п кодовых символов сверточного кода. Сумма по модулю два х, = с, © Ь, передается по каналу.
Таким образом, результатом кодирования всякий раз является последовательность из смежного класса данного кода. Лидер смежного класса зависит от текущего состояния сверточного кодера.
Рассмотрим работу декодера. Декодеру известна оценка состояния кодера. В соответствии с этой оценкой декодер вычисляет оценку лидера смежного класса. По известной оценке лидера и принятому вектору на выходе канала выполняется декодирование, по результатам которого либо принимается решение в пользу некоторой оценки информационного блока и,, либо происходит отказ от декодирования (стирание) и передача сигнала запроса. По сигналу запроса кодер и декодер возвращаются на шаг назад.
Суть метода состоит в том, что до тех пор, пока декодер вычисляет оценки сообщений правильно, кодер и декодер двигаются по одной и той же траектории в диаграмме состояний сверточного кода. В случае ошибки декодер сворачивает на неправильный путь. На последующих шагах передачи
множество кодовых слов блокового кода кодера отличается от предполагаемого множества кодовых слов декодера, благодаря этому обстоятельству вероятность стираний увеличивается.
Важным параметром кодера и декодера является их объем памяти, измеряемый числом информационных блоков т. Код и правило декодирования должны быть выбраны такими, чтобы при движении по правильному пути вероятность стирания была близка к нулю, а при движении по ошибочному пути вероятность стирания была близка к 1. При этих условиях вероятность ошибки, обусловленной ограничением на память кодера и декодера, будет экспоненциально убывать с увеличением т. В свою очередь вероятность необнаружения ошибки определяется кодовым ограничением сверточного кода, выраженным в числе блоков V. Более точно асимптотические характеристики рассматриваемой схемы сформулируем в виде следующей теоремы.
Теорема 1.2. Для любых положительных е и 3 существует п0 такое, что при при длине внутреннего кода п>и„ возможна передача со средней скоростью Ч ^ Я-З при вероятности ошибки
где С - пропускная способность канала.
Как видно из приведенной н Теореме 2.1 оценки, вероятность ошибки содержит две составляющих. Одна из них связана с ограничением на задержку декодирования г, вторая определяется величиной кодового ограничения внешнего сверточного кода. Если принять задержку декодирования произвольно большой и исследовать зависимость вероятности ошибки только от величины кодового ограничения (в символах канала) уп , то из утверждения теоремы получим
Таким образом, показатель экспоненты остается положительным при всех скоростях меньших пропускной способности канала. Более того, при Я С показатель экспоненты примерно такой же, как и для рассмотренного выше оптимального алгоритма. Важная особенность данного алгоритма состоит в том, что для уменьшения вероятности ошибки достаточно увеличивать объем памяти кодера и декодера, сложность реализации при этом увеличивается по линейному закону. Следовательно, в данном случае вероятность ошибки при увеличении сложности убывает по экспоненциальному (а не показательному, как это обычно бывает) закону.
Графики экспонент вероятности ошибки для различных алгоритмов представлены на рис. 1.1 для двоичного симметричного канала с переходной вероятностью 0,1. Показателю экспоненты ЕДЯ) на рисунке соответствует кривая Е\К).
Итак, основными результатами исследования систем с обратной связью на основе сверточных кодов являются
• аддитивная метрика для декодирования сверточных кодов со стираниями;
• асимптотическая верхняя граница экспоненты вероятности ошибки декодирования при использовании сверточных кодов в системах с обратной связью;
• асимптотически эффективный конструктивный алгоритм кодирования для систем с обратной связью, имеющий низкую сложность практической реализации.
2. Сверточные коды в широковещательных каналах
Идея исследования асимптотических характеристик блоковых и сверточных кодов в широковещательных каналах возникла в связи с опубликованием в 1974 г. в журнале «Проблемы передачи информации» работы Р. Галлагера, в которой были получены границы вероятности ошибки, с показателями экспонент положительными во всей области допустимых скоростей широковещательного канала Г. Ш. Полтырев воспользовался границами Галлагера для того, чтобы определить область пар вычислительных скоростей и получил неожиданный результат. Эта область, в отличие от области допустимых скоростей, не оказалась выпуклой, из чего следует, что в интересном с точки зрения практики диапазоне скоростей наилучшими способом кодирования остается тривиальное кодирование по принципу «разделения времени» между пользователями.
Опыт применения метода случайного кодирования приучил исследователей в области теории информации к тому, что среди множества случайных кодов «почти все» - хорошие. Напрашивался вывод о том, причиной такого поведения оценок Галлагера является неудачный выбор ансамбля кодов. Так возникла задача поиска ансамбля кодов эффективных в широковещательном канале. При исследовании систем неблокового кодирования для систем с бесшумной информационной обратной связью [1,3] было установлено, что в некоторых приложениях коды с фиксированной композицией лучше случайных кодов. Использование кодов с фиксированной композицией для построения нового ансамбля кодов и развитая в работах [2,4] техника анализа этих кодов привели к значительному улучшению границ вероятности ошибки для широковещательных каналов.
Рассмотрим сначала идеи, лежащие в основе анализа кодов с фиксированной композицией.
Введенная Р. Галлагером в 1965 г. техника построения границ вероятности ошибки усреднением по ансамблю кодов существенно опирается на то, что случайные коды получены независимым выбором символов кодовых слов. Поскольку именно при независимых символах на входе канала достигается максимум взаимной информации и максимум показателя экспоненты вероятности ошибки, в отсутствие каких-либо ограничений на
множества кодовых слов техника Галлагера приводит к асимптотически точным результатам.
В случае кодов с фиксированной композиции входные символы канала зависимы. Выполнить усреднение вероятности ошибки по множеству случайных кодов с фиксированной композиции помогает сформулированная ниже Лемма 2.1. Введем необходимые обозначения.
Пусть X- - входной и выходной алфавиты дискретного канала без памяти. Композицией последовательности х длины п назовем вектор т = , в котором т, - число элементов в х равных /, ^^г, = п. Через А, обозначим множество всех последовательностей с одинаковой композицией т. Код, все слова которого принадлежат А,, называется кодом с фиксированной композицией т. Через q обозначим произвольное распределение вероятностей на X, символами Мг[-], [•] обозначим операторы усреднения по множеству равновероятных последовательностей из Ат и по множеству последовательностей, полученных независимым выбором символов из X в соответствии с распределением вероятностей q.
Лемма 2.1. Для неотрицательной функции р(х,у), определенной на множестве X" х У", имеегг место неравенство
где Рч() обозначает вероятность, вычисленную в соответствии с распределением q.
Лемма 2.1. сводит усреднение по множеству последовательностей с фиксированной композицией к привычному усреднению по множеству последовательностей из независимых одинаково распределенных символов. Платой за упрощение анализа является необходимость оптимизации оценки по вспомогательным распределениям q.
Сформулируем кратко результаты работы [4].
Широковещательный канал без памяти задается двумя матрицами переходных вероятностей , где X -общий входной алфавит каналов Р и 0, а У к 2 - выходные алфавиты этих каналов. Рассматривается частный случай общей постановки задачи, в котором предполагается, что по широковещательному каналу передается «общая» информация, предназначенная для пользователей обоих каналов (скорость передачи этой информации обозначим через Р0) и «частная» информация, предназначенная только для пользователя канала Р (скорость ее передачи обозначаем через Л,, имеется в виду, что пропускная способность канала Р выше пропускной способности канала 2) .
Пусть и0 = = и = представляют собой
множества сообщений, предназначенных соответственно для обоих
получателей и для получателя канала Р, Л/0 = 2""°, М1 = 2"*1. Через иор = > &1Г
(%> и ^п, = ("о,> обозначаются множества решений, принимаемых декодерами двух каналов, через Р^ и Р - вероятности ошибок декодирования на выходе каналов Р и £ соответственно, = тах|Рг(м0;, ф"0),Рг(й1р *«[)>, =Рг(% *мо)- Опишем ансамбль
блоковых кодов для широковещательного канала.
Блоковый код длины п с парой скоростей (Ло,Л,) представляет собой множество последовательностей V = >, г = 1 . Л/0, у' = 1 . Л/,, М0 = 2"*°, Л/, = , V с. X". Для описания ансамбля кодов вводится вспомогательный алфавит 5 =, на множестве задается распределение /(в), и помимо этого вводится «тест-канал» (/(х 5 я)>, х е X", . Сначала в соответствии с распределением /(в) из множества 5" независимо выбираются М0 последовательностей в,, /= 1. Л/„, затем для каждого г в соответствии с распределением '(яЮ из множества X" независимо выбираются Л/, последовательностей . Каждая из них - кодовое слово, сопоставляемое паре сообщений О',./).
Для описания декодирования вводятся две неотрицательные функции: Лр(у,з) и с!ч(г,я). Декодер каждого из каналов Р и б сначала принимает решение в пользу одного из сообщений множества 1/0. Это решение принимается по принципу максимума соответствующей «декодирующей» функции с/. После этого декодер канала Р принимает решение в пользу одного из сообщений множества ¡7,. Это решение принимается по принципу максимума условной вероятности р(у | у1;) по всем ] при уже известном значении /.
Теорема 2.1. Для передачи в дискретном широковещательном канале без памяти в рамках описанной выше постановки задачи существует блоковый код, вероятности ошибок декодирования которого удовлетворяют неравенствам