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

ОГР

I I и

САНКТ-ПЕТЕРБУРГСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

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

о и

-) •) г - .-

<:- ! ;, С-:.-,;

КИРИЛШ Валерий Николаевич

ДЕКОДИРОВАНИЕ ОБЕРТОЧНЫХ КОДОВ С ИСПОЛЬЗОВАНИЕМ СПИСКОВ

Специальность 05.13.01 - Управление в технических системах

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

С.-Петербург 1993

Работа выполлена в Государственной академии еэрокосмического приборостроения, г. Санкт-Петербург.

Научный руководитель - доктор технических наук, профессор Е.Т. Мирончиков

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

доктор технических наук, профессор В.Д. Колесник кандидат технических наук И.Н. Оков

Ведущая организация - Научно-производственный комплекс "Красная Заря"

Защита диссертации состоится " /" ¿З^Д^ .. 4993 г>

в _ час. _ мин. на заседании специализированного совета

К 063.21.03 Государственной академии аэрокосмического приборостроения по адресу:

190000, Санкт-Петербург, ул. Герцена, 67

С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан " _ "__" 1993 г.

Ученый секретарь к.т.н., доцент

специализированного совета < в,в- Фильчаков

- I -

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

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

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

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

- г -

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

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

Для достижения поставленной цели представляется необходимым решение следующих задач:

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

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

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

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

Новые результаты и положения, выносимые на защиту : -методика расчета помехоустойчивости сверточных кодов, декодируемых по алгоритму с использованием списков;

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

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

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

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

Практическая ценность работы. Практическая ценность работы состоит в следующем:

-построены таблицы двоичных сверточных кодов, предназначенных для списочного декодирования при объеме списка равном 2;

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

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

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

Апробация работы.Основные результаты диссертационной работы докладывались, обсуждались и получили одобрение на: .

-X всесоюзном симпозиуме по проблемам избыточности в информационных системах (Ленинград, 1989);

-V советско-шведском международном симпозиуме по теории информации (Москва, 1991);

-научном семинаре НТО РЭС им А.С.Попова (Ленинград, 1991); а также семинарах по теории информации и кодирования кафедры АСУ СПИАП (С-Петербург 1989, 1990, 1991, 1992).

Публикации■ По теме диссертации опубликовано 6 печатных трудов

В сборниках докладов, научно-технических сборниках и научно-практических журналах.

Структура и объем диссертации. Диссертация состоит из введения, четырех разделов, заключения, списка литературы и приложений. Работа содержит 122 страницы основного текста, 28 рисунков, список использованой литературы содержит 50 наименований.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Пусть дан двоичный сверточный код с величиной кодового ограничения V в скоростью Д=1/п0 где п0- число символов формируемых кодером на одном такте работы. Работа списочного декодера, как и работа декодера Витерби может быть интерпретирована как поиск кратчайших путей по решетчатой диаграмме. Выберем величину v0, определяющую сложность декодирования, из условия v0 < ю . На первых г>0 тактах работы декодер осуществляет декодирование аналогично обычному декодеру Витерби. Начиная с шага vQ+í декодер сохраняет для каждого из 2 ^ узлов решетки по I путей с наилучшими метриками. Заметим, что начиная с этого шага декодирования, символы ребер решетки определяются путями, ведущими в рассматриваемый узал, и для вычисления символов ребер декодер использует аналог кодера.

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

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

Поскольку декодирование осуществляется по решеткэ с 2°о узлами и для каждого из узлов производится вычисление метрики для Ь путей, то сложность списочного декодера пропорциональна величине 12уо. Отметим, что при 1=2 списочный декодер эквивалентен по сложности декодеру Витерби для кода с Таким образом, код с длиной

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

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

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

V рет + рег. + ре£- ( 1 >

где Рет- вероятность ошибок обусловленных ограничением на величину задержки декодирования т; .Р^- вероятность ошибки декодирования но максимуму правдоподобия (без укрупнения решетки и использования списков), Ре1вероятность отбрасывания правильного кодового слова при формировании списка.

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

рег> < 1Аа V а >' (2)

где А^ - число кодовых слов, находящихся на расстояшш (1 от фиксированного кодового слова, а Ре(с1) - вероятность ошибки для кода из двух слов с расстоянием <2.

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

Будем рассматривать случай когда параметр v0, определяющий сложность списочного декодирования, удовлетворяет условию: у0< v.B этом случав число узлов кодовой, решетки, используемой списочным декодером, будет меньше числа узлов исходной кодовой решетки. Назовем такую решетку усеченной.

Полным кодом назовем код с длиной кодового ограничения к. Число слов данного кода веса й обозначим через А^ , а множество тесел (А^), 6*1,2... назовем спектром полного кода.

Пусть ХфНулевое кодовое слово.Усеченными кодовыми словами назовем слова кода, которые, отличаясь от х0в первом ребре, сливаются с *0в усеченной кодовой решетке и не сливаются в исходной решетке.Число слов усеченного кода веса <3 обозначим через А^ , а множество чисел (А^), й=1,2... назовем спектром усеченного кода.

Из выражения (2) следует, что вклад слов полного кода в вероятность ошибки учтен в слагаемом Р^ и для при вычислении

достаточно учесть только усеченные кодовые слова.

Рассмотрим списочное декодирование в ДСК. Известно, что декодирование по максимуму правдоподобия в ДСК эквивалентно декодированию по минимуму расстояния Хемминга. Ограничимся анализом случая, когда объем списка 1=2.

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

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

е Г<1( х,.у > < г ( з )

(Ж х2,у ) * г .

где у принятое кодовое слово, а <1(х,у)-расстояние между словами х и у в метрике Хемминга.

Введем следующие обозначения: ш^число единичных позиций, по' которым кодовые слова х(и х2 совпадают, и^число единичных символов на. несовпадающих позициях в слове х(и ц^число несовпадающих единичных позиций слова х^.

Аналогично X ошибок можно представить в виде суммы г - V г,+ г2 .

где х0- ошибки на «^позициях слов х(и х2, ошибки на ш(позициях слова х(и х2~ на и>2 единичных позициях слова х2.

Таким образом, вероятность ошибки для двух конкретных слов списка х(и х2, характеризующихся тройкой величин (»0,ш(,ш2), в ДСК с переходной вероятностью р запишется следующим образом

г t г г п> + т + и> - г

Ре^о^.^ХЕС^ р <1-р> 0 ' 2

Х0' Ь' г2:

V V V «

2í - 2г ^ 1В0+ 2х - гг2ъ ш0+ ш2

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

Утвервдение 1.

Для списка из двух кодовых слов, корреляционные характеристики которых определяются тройкой чисел (ш0,ш(,ш2), максимальное число ошибок, исправляемым данным списком, равно

,!У + Ю.+ ?, 0 + VI + 7,

и = ¡}' ] * ] - V 1 •

где через [с^ обозначено наибольшее целое число, меньшее или равное а.

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

( 4 )

где параметр определяет максимальное число ошибок,

исправляемыхданным кодом при использовании списков: гх = т1п г(ш0,ш1,и>г),

и минимум отыскивается по таким тройкам (ш0,ш(,ш2), для которых

Для случая больших отношений сигнал/шум, т.е. при р О величина Рв определяется максимальным членом одной из сумм (2) и (4).

Утвервдение 2.

Вероятность ошибки декодирования сверточного кода по алгоритму с использованием списков, с параметрами v0 и Ь=2, в ДСК при р -» О, при условии что <1^ > й^ 2, где свободное расстояние полного кода, а <1^5 усеченного, определяется выражением

Ре< В^р Ч 1+о(х) ) , ( 5 )

где коэффициент В^пре делен следующим образом

го Л

Вь= №0.т,.юг) Ц С " Сш' С,

о

ш

гт

а через о(х) обозначена величина большего порядка малости чем х.

Предположим, что передача кодовых символов осуществляется по каналу с АБП2 с отношением сигнал/шум Л2 и на вход декодера поступают мягкие решения с канала демодулятора.

Пусть %0- переданное кодовое слово. Для заданного списка Хь={х{> ,1=1,Ъ пуъэй можно сформировать матрицу { w^J },

-1 элементы которой определены соотношением

т1Г ( йо1 + " йи } / 2-где расстояние Хемминга между кодовыми словами х( и х^ .Легко

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

число совпадающих единичных позиций слов х{ и х^.

Обозначим через N(4) число таких списков Х^из Ь путей,

которые характеризуются одинаковой матрицей Я. Нетрудно убедиться в

том, что вероятность того что функция правдоподобия переданного

пути х будет меньше функций правдоподобия всех путей списка

Х^однозначно определяется матрицей Я. Таким образом, оценка .для

Реьпредставима в виде:

РеЬС 2 Ж Я )Ре(Я), (6)

я

где Ре(Я) - вероятность отбрасывания правильного пути для списка,который характеризуется матрицей Я. Обозначим через *г главную диагональ матрицы Я. Можно показать, что величина

(¿(Я) = * я" и1

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

Ре(И) « ехр{ -Л2й(Я) ).

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

определим таким образом

йт = тШС с2(Я) }. ( 7 )

ь щ

Можно показать, что оценка (6) для величины Ре^ , с учетом спектра усеченного кода и введенного понятия списочного расстояния (7), представима также в виде

А5ре< 1 >■ (8)

<* > йь

Следовательно, обобщенная аддитивная оценка для вероятности ошибки при списочном декодировании (1) в канале с АБГШ представима

в виде

hd

ре * 2 Td D I „ ( 9 >

cßdj I D=ejp{ -hz >,

где коэффициенты Td рассчитываются по формуле

fH = mini 2 N(W) , Aj ) + A.,. a w: й(т)=й a a

Набор пар ( d.T^J назовем L-списочным спектром сверточного кода при

списочном декодировании. Заметим, что не все индексы в (9) целые.

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

Будем называть сверточный код с длиной кодового ограничения к, предназначенный для декодирования по списочному алгоритму с параметрами vjn L - (v0,v,D-кодом. Будем называть также код, задаваемый отводами от первых vQ ячеек регистра кодера г^кодом.

В работе предлагается процедура построения (v0,v ,Ь)-кодов на основе У0-кода с заданными спектральными свойствами, в качестве у^кода обосновывается использование оптимальных сверточных кодов, декодируемых по Витерби. Код с параметрами (vQ,v ,L) строится путем перебора возможных отводов от v-v0 разрядов кодера, таким образом, чтобы полученный код не был катастрофическим и чтобы величина свободного расстояния полученного кода не ухудшала характеристик помехоустойчивости, обеспечиваемых использованием списков. Анализ сложности поиска кодов с использованием предлагаемой методики показывает, что для двоичных кодов и списка L=2 максимальное число вычислительных операции, затрачиваемых на поиск ограничено сверху величиной

3

Н « £ п /угтр(7-р1 ~\expz{(Un0j(v-v0)+3m(p)logze }.

где р= (v0- 1)/п , H(p)=-plnp-(1-p)ln(1-p), а величина п лежит в пределах 3v..5v и ее значение определяется требуемым числом спектральных коэффициентов.

В то же время при поиске полным перебором общее число вычислительных операций пропорционально величине Н - ехрг { nQ( V + 1) + Зп >.

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

С использованием предлагаемой методики получены коды, применение которых обеспечивает выигрыш в сложности реализации по сравнение») с кодами декодируемыми по Витерби. В таблице I приведены некоторые полученные коды, предназначенные для списочного декодирования иканале с гауссовским шумом и мягкими решениями, при объеме списка 1=2. Для сравнения в этой же таблице приводятся характеристики сверточных кодов, декодируемых по Витерби и обеспечивающих приблизительно эквивалентную сложность. Величина Кг показывает значение отношения сигнал/шум, начиная с которого код .декодируемый с использованием списков, обеспечивает выигрыш по помехоустойчивости.

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

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

обеспечивается

слеедует, что декодирования

достигается в системах связи с ортогональным набором сигналов.

Таблица I.

Списочное декодирование

Декодирование по Витерби

V Код <4 ч v КОД Ч 1хг

2 5 73,51 7. ИЗ 6 3 15,17 6 1 1.8

5 73,71, 10.667 3 3 13,15, 10 3 1.5

52 17

3 7 263, 8.909 10 4 23,35 7 2 1.7

322

3 7 361, 13.333 5 4 25,33, 12 5 1.8

323, 37

263

4 8 160, 9.8 2 5 53,75 8 1 1.8

727

Таблица 2.

Списочное декодирование

V Код Ч Ч V Код ь ч

2 6 173, 5.45 5 4 15,42 5 2

046

3 7 256, 7.143 40 5 56,23 6 2

323

4 9 0462, 8.077 19 6 122, 7 4

1335 155

Декодирование по Витерби

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

Рассматривается известный метод кодирования авторегрессиошшх гауссовских источников, основанный на. использовании декодера Витерби в сочетании с кодами, решетки которых аналогичны решеткам кодов Унгерооека для амплитудной модуляции, а кодовый алфавит для скорости Я бит/отсчет строится на основе алфавита оптимального неравномерного квантователя Ллойда-Макса для скорости ."+1 бит/отсчет.

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

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

списочного алгоритма при объеме списка 2 позволяет повысить эффективность кодирования данным методом гауссовских авторегрессионных источников по сравнению с использованием декодера Витерби. Наибольший выигрыш обеспечивается для кодов с малой длиной кодового ограничения и эквивалентен выигрышу в сложности на величину порядка 30-40%.

В данном разделе также рассмотрен метод кодирования речевых сигналов, основанный на использовании линейного предсказания в сочетании с решетчатым кодированием. Данный метод может быть рассмотрен как известный метод CELP (Coded Exited Linear Prediction) с решётчатым кодером вместо стохастической кодовой книги. Сложность реализации рассматриваемого метода существенно ниже сложности CELP, а качество восстановленного речевого сигнала сопоставимо с качеством CELP.

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

По результатам экспериментальных исследований показано, что применение алгоритма с использованием списка объема 2 позволяет повысить эффективность кодирования за счет увеличения отношения сигнал/шум на величину 1-2.5 dB и улучшить субъективное качество восстановленного речевого сигнала по сравнению с использованием декодера Витерби.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты диссертационной работы можно сформулировать следующим образом:

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

2. В.Н.Кирилюк, Б.Д.Кудряшов. Списочный декодер двоичных сверточных кодов.// Алгоритмы и программы,1990,N 9.

3 В.Н.Кирилюк, Б.Д.Кудряшов. Вычисление оценки числа ошибок при декодировании сверточных кодов по списочному алгоритму в ДСК.// Алгоритмы и программы, 1990, N 11.

4. V.N.Klrlliuk, B.D.Kudrlashov. Perfomances оГ baeed-on-llats «involutional codes decoding for gausslan channel.//Proc. of Fifth Joint Soviet- Sredlsh International Workshop on Information Theory, January 13-19, 1991, Moscow, pp.37-38.

5. В.Н.Кирилюк. Характеристики основанного на списках алгоритма декодирования сверточных кодов в гауссовском канале.Проблемы обработки и передачи информации : Межвуз. сб. научи, тр.,ЛИАП.,СПб., 1991, с. 23-29.

6. В.Н.Кирилюк. Спектральные характеристики сверточных кодов при списочном декодировании.//Радиоэлектроника и связь,1992, Ä2-3, с. 44-49.

л

Подписано к печати ¿6 ог. 93, Формат 60«84 I/I6

Печ. л. 1,0; уч. -изд. л. 1,0. Тираж 100 экз. Зах. N69

Бесплатно.

Офсетная печать.

Ротапринт ГААП Ii'OOOO, Сашст -Петербург, ул. Герцена, 67