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

государственный университет телекоммуникаций

им.проф. М.А. БОНЧ-БРУЕВИЧА

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

УДК 621.396.36

БЕЛОУС Сергей Анатольевич

ИССЛЕДОВАНИЕ МЕТОДОВ СОКРАЩЕНИЯ ВЫЧИСЛШ'ЕЛЬНЫХ ЗАТРАТ В АЛГОРИТМАХ ПРИЕМА ДИСКРЕТНЫХ СООБЩЕНИЙ

Специальность 05.12.02 - системы и устройства передачи информации по каналам связи

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 1993

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

Научный руководитель - заслуженный деятель науки и техники РФ

доктор технич'еских наук, профессор Д.Д. Кловский.

Официальные оппоненты: доктор технических наук,

профессор В.И. Коржик; кандидат технических наук, доцент А.Л. Вяткин.

Ведущее предприятие -/10НИИР.

Защита диссертации состоится 994 г>

заседании специализированного совета К 118.01.01 при Государс венном университете телекоммуникаций им. проф. Бонч-Бруевича адресу: 191065, Санкт-Петербург, наб. р. Мойки, д.61.

С диссертацией можно ознакомиться в библиотеке института.

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

Автореферат разослан " ^" ¿¿^^"¿хи йЯ4 г.

Ученый секретарь специализированного совета, р

к.т.н.,доцент в.Х. ХАРИТОНОВ

-3-

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальной для исследования в настоящее время является пробна синтеза алгоритмов обработки, экономных в вычислительном ношении и приемлемых по требуемому объему памяти. Алгоритм Ви-5би обладает рядом достоинств, но из-за экспоненциального уверения вычислительных затрат и необходимого объема памяти с рос-4 размерности задачи (длины кодового ограничения сверточного }а(СК), длины импульсного отклика модулятора или канала связи, шчества проверочных символов в кодовом слове блочного кода 1)) неприменим к задачам большой размерности. Указанное ограните на размерность задач сдерживает рост качественных показате-) систем передачи дискретных сообщений. Сложность алгоритмов юдирования удается уменьшить, используя коды со специальной >уктурой (например, декодирование кодов БЧХ и мажоритарное де-[ирование ).

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

Цель диссертационной работы состоит в разработке на осно! методов комбинаторной оптимизации алгоритмов приема дискрета сообщений с уменьшенными вычислительными затратами и необходим; объемом памяти.

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

Методы исследования основаны на использовании статистиче«' теории связи, комбинаторной оптимизации, теории алгоритмичес* сложности задач. В работе применяются аппараты теории множес линейной алгебры, теории вероятностей и моделирование на ЭВМ.

Научная новизна. В диссертации задача приема дискрет] сообщений рассматривается как задача отыскания экстремума фу: ции, заданной на конечном множестве, и для ее решения использу ся методы комбинаторной оптимизации.

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

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

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

- метод динамического программирования (алгоритм Вите распространен на решение задачи декодирования линейного БК использовании решетчатых сигналов (РС); описана проц< построения объединенной решетки Витерби-Вольфа, применение ] рой позволяет решать указанную задачу;

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

-5- на основе метода ветвей и границ разработан алгоритм поис-глубину с порогом (ПГП) для приема PC;

- разработана процедура генерации дерева кодовых комбинаций ее основе построен алгоритм ПГП для мягкого декодирования Зных БК (или CK с нейтрализацией хвостов, если они рассматри-:я как БК); показано, что усеченные версии данного алгоритма известные алгоритмы декодирования Л.Ф. Бородина и A.C. Нау-

i

- разработаны алгоритмы последовательного декодирования для на PC и мягкого декодирования линейных БК, использующие идео-

0 алгоритма Фаяо и некоторые компонента метода ветвей и гра-

- на основе алгоритма отыскания минимального разреза в спортной сети разработан алгоритм демодуляции в канале с МСИ некоторых ограничениях на вид импульсной реакции.

Получена рекуррентная форма алгоритма полного перебора с обой связью по решению (алгоритма Кловского-Николаева! для ма PC.

Разработан алгоритм оптимального поветвевого приема PC, полный обобщением рекуррентного алгоритма Абенда и Фритчмена мальной,поэлементной демодуляции в канале с МСИ.

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

1 систем передачи дискретных сообщений:

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

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

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

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

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

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

Реализация результатов работы. Часть результатов диссе^ отражена в отчетах по госбюджетным и хоздоговорным НИР, выпс ным в Отраслевой научно-исследовательской лаборатории "С\ эффективной передачи сообщений по каналам связи" Поволжское статута информатики, радиотехники и связи.

Апробация работы. Результаты работы докладывались и обе лись на Всесоюзной конференции по теории кодирования (г. 0; 1988), на научно-технических конференциях профессс преподавательского состава и научных сотрудников ПИИРС, на них семинарах кафедры теоретических основ радиотехники и ПИИРС (1987*1993).

Публикации. По теме диссертации автором опубликовано 1; бот, в том числе 3-й изобретения.

Структура и объем работы. Диссертационная работа состо! введения, шести глав, заключения и списка литературы, включе 139 наименований. Она содержит 201 страницу машинописного т< 46 страниц рисунков, 3 страницы таблиц.

Основные положения, выносимые на защиту.

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

ной оптимизации и последовательность его применения для синтеза алгоритмов приема РС и декодирования БК.

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

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

На основе анализа компонентов метода ветвей и границ предложен алгоритм поиска в глубину с порогом (ПГШ. Описано его использование для приема РС и декодирования БК.

Алгоритм ПГП можно интерпретировать как процедуру поиска путей с минимальным весом на неотрицательно взвешенном дереве кодовых комбинаций. Указанный алгоритм основан на стратегии поиска в глубину: для продолжения выбирается самый длинный из исследованных частичных путей (с наибольшим числом ребер), а при равенстве числа ребер выбирается путь с минимальным весом. Для отбраковки "неперспективных" частичных путей используется следующее 7равило (граница) : не подлежат продолжению те частичные пути, вес которых превосходит вес некоторого уже исследованного полного (из <орня в вершину) пути на дереве (в силу неотрицательности весов >ебер вес частичных путей при их продолжении может только возрас-■и). Среднее число операций на бит оценивалось путем моделирова-[ия алгоритма ПГП и близких к нему алгоритмов (стек-алгоритма и ¡ервой версии сгеерег-алгоритма с метрикой максимального правдо-одобия) применительно к задаче демодуляции в канале с МСИ. Из езультатов моделирования следует, что алгоритм ПГП по вычисли-ельной сложности лучше, чем сгеерег-алгоритм, требующий прибли-ительно такого же объема памяти, и уступает стек-алгоритму, ра-

ботащему с экспоненшэjmo большим объемом памяти. В алгоритме ПГП необходимый объем памяти пропорционален D (при приеме PC) или N^ (при декодировании БК). При вероятности ошибки на выходе демодулятора Рощ s 10"1 алгоритм ПГП обеспечивает выигрыш по среднему числу операций на бит по сравнению с алгоритмом Вигерби более 50 раз (длина импульсного отклика канала связи L+l=10), причем указанный выигрыш достигается при значительно меньшем, чем в алгоритме Витерби, объеме памяти.

Рассмотрены вопросы построения приближенных (субоптимальных) алгоритмов, в част:'.ости, показано, что усечением алгоритма ПГП для декодирования БК можно получить известные алгоритмы декодирования Л.Ф. Бородина и A.C. Наумова.

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

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

В алгоритме ЛГФ (поиск в глубину с отбраковкой Фано) при движении назад не требуется (в отличие от алгоритма Фано) вычислять метрики узлов, т.к. они сохраняются в памяти декодера пр^ движении вперед. Благодаря разанной особенности алгоритм ПГФ п< количеству операций вычисления метрики в 2 раза быстрее алгоритма Фано. Алгоритм ПГФ при более простой блок-схеме, приблизительно в два раза меньшем объеме памяти и равной вероятности сти рания быстрее второй версии сгеерег-алгоритма (А.А.Безрук и др. Пробл. перед, инф., 1991г. Вып.2).

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

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

'дереву) сохранение ствола позволяет начинать повторный поиск (с более низким значением порога) с того узла, в котором был впервые нарушен предыдущий порог, а не с того узла, где он был понижен. По результатам моделирования двухпороговый алгоритм Фано с хранением ствола при вероятности стирания Р =10-1 в 1,3 раза быстрее обычного алгоритма Фано, а алгоритм ПГФ с хранением ствола при более простой блок-схеме, примерно в два раза меньшем объеме памяти и одинаковой вероятности стирания быстрее, чем третья версия сгеерег-алгоритма (С.А.Попов, Пробл. перед, инф., 1993г., вып.2).

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

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

Проведено моделирование предложенных в четвертой главе алгоритмов, а также стек-алгоритма, алгоритма Фано и сгеерег-алгоритмов применительно к задаче декодирования сверточ-ного кода в двоичном симметричном канале без памяти. Проведено также моделирование алгоритмов ПГП и ПГФ в режиме мягкого декодирования линейных блочных кодов. Результатом моделирования являются построенные эвм графики распределения числа операций на декодированный бит при 1? = Явич (I? - относительная скорость кода, Квыч ~ вычислительная скорость калала), а также зависимости среднего числа операций на бит (с учетом стертых блоков) от вероят-

ности стирания.

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

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

В заключении сформулированы основные научные и практически' результаты работы, которые состоят в следующем:

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

2.Описана процедура построения объединенной решетки Витерби Вольфа, на основе которой может быть выполнено мягкое декодирове ние по максимуму правдоподобия линейного БК при использовании Г и, в частности, в канале с МСИ. Тем самым область применения ей горитма Витерби расширена на новый класс задач,

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

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

| БК. Моделированием подтверждено, что предложенный алгоритм пр

J

восходит близкие к нему алгоритмы по совокупности двух параметров : вычислительной сложности и необходимому объему памяти. Показано, что усечением предложенного алгоритма можно получить эффективные субоптимальные алгоритмы, в частности, известные алгоритмы декодирования Л.Ф. Бородина и A.C. Наумова.

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

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

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

8.Показана возможность использования алгоритмов последовательного декодирования для декодирования линейных БК и CK с нейтрализацией хвостов, если последние интерпретируются как БК.

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

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

11.Полученные в диссертации и наиболее употребительные из известных алгоритмов приема дискретных сообщений классифицированы по использованному в них методу дискретной оптимизации. Приведены практические рекомендации' по выбору алгоритма для приема PC или декодирования БК.

Материалы диссертационной работы отражены в следующих публикациях :

1.Кловский Д.Д., Карташевский В.Г., Белоус С.А. Сверточное кодирование в канале с МСИ при использовании СШП. // VIII всесо-

юзная конференция по теории кодирования, Одесса, Октябрь 1988. Тезисы докладов, часть 2, с.204+206.

2.Кловский Д.Д. Карташевский В.Г., Белоус С.А. Рекуррентная модификация алгоритма приема в целом с поэлементным принятием решения. // Радиотехника, 1991, №1, с. 58+59.

3.Кловский Д.Д., Картаиевский В.Г., Белоус С.А. Прием сигналов со сверточным кодированием в канале с межсимвольной интерференцией. // Пробл.перед, информ.,1991,том 27,выпуск 2, с.97+100.

4.Белоус С.А. Применение методов дискретной оптимизации для мягкого декодирования линейных блочных кодов. // Обработка сигналов в системах связи: Сб. научн. трудов учебн. завед. связи. / ЭИС. СПб. 1992, №156, с.8+14.

5.Белоус С.А. Непереборный алгоритм оптимальной демодуляции в канале с межсимвольной интёрференцией. // Обработка сигналов I системах связи: Сб. научн. трудов учебн. завед. связи. / ЭИС, СПб. 1992, №156, с. 15+20.

6.Белоус С.А., Кловский Д.Д. Применение метода ветвей и границ для синтеза алгоритмов приема рекуррентных сигналов. // Проб лемы передачи информации, 1993, том 29, выпуск 2. с.56+63.

?.Белоус С.А., Кловский Д.Д. Применение метода ветвей и гра ниц для мягкого декодирования линейных блочных кодов. // Радис техника, (в печати).

8.Кловский Д.Д., Белоус С.А. Алгоритм мягкого декодирован! линейных блочных кодов// Радиотехника (в печати).

9.Белоус С.А. Алгоритм приема блока рекуррентных сигнало] // Сб. научн. трудов учебн. завед. связи, (в печати).

10.А.С.1653172. Устройство для приема дискретных сообщений каналах с памятью. Кловский Д.Д., Карташевский В.Г., Белоус С. Н041 27/06. Приор. 29.04.87. Опубл. 30.05.91. Бюл.М°20.

11.А.С.1538270. Устройство для демодуляции дискретных сигн лов. Кловский Д.Д., Карташевский В.Г., Белоус С,А. Н04Ь 27/С Приоритет 08.07.87. Опубл. 23.01.90. Бюл.Н°3.

12.А.С.1720165. Устройство для приема дискретных сигналов каналах с памятью. Кловский Д.Д., Карташевский В.Г., Белоус С Н041. 27/06. Приор. 05.01.89. Опубл. 15.03.92. Бюл.№10.