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

российская академия наук

ИНСТИТУТ ПРОБЛЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ

—т од

У ч М«л . м,.л На правах рукописи

с 0 по,] &33

АШИХМИН АЛЕКСЕЙ ЕВГЕНЬЕВИЧ

УДК 621. 391. 15

РАЗРАБОТКА АЛГОРИТМОВ БЫСТРОГО ДЕКОДИРОВАНИЯ ДЛЯ БЛОКОВЫХ И СВЕРТОЧНЫХ кодов В ДИСКРЕТНЫХ И ПОЛУНЕПРЕРЫВНЫХ КАНАЛАХ

.Специальность 05. 13. 01 Управление в технических системах

АВТОРЕФЕРАТ

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

Москва — 1993

Работа выполнена в Институте проблем передачи информации Российской Академии Наук

Научный руководитель: доктор технических наук,

В. В.Зяблов

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

Ю. Л. Сагалович

кандидат технических наук, А. А. Давыдов

Ведущая организация: Московский технический

университет связи и информатики

Защита диссертации состоится « » -199 г.

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

Д. 003. 29. 01 в Институте проблем передачи информации РАН по адресу: 101447, Москва, ГСП-4, ул. Ермоловой, 19.

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

Автореферат разослан « »---1993 г.

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

С. Н. СТЕПАНОВ

Общая характеристика работы

Актуальность темы.

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

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

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

внутреннего кола используется сигнальная решетка Ее, актуальной является задача разработки эффективного алгоритма декодирования данной решетки, что эквивалентно разработке эффективного алгоритма декодирования кода Рида-Маллера первого порядка [8,4,4]. Код Нордстрома- Робинсона используется как в системах помехоустойчивого кодирования, так и в векторных квантователях случайных сигналов.

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

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

- разработка и исследование алгоритмов декодирования кодов Рида-Маллера первого, порядка, определение обобщенных весов Хэмминга кодов Рнда-Маллера над полем сг(3);

- разработка и исследование алгоритмов декодирования кода Нордстрома-Робинсона, определение обобщенных весов Хэмминга .кода Нордстрома-Робиисона и кода Кердока длины л=64, построенных в виде линейных кодов нал кольцом 2 .

4

- построение новых сверточных кодов с частичной единичной памятью и с частичной памятью два;

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

Научная новизна

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

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

алгоритма в малых шумах.

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

4. Найдены обобщенные веса Хэмминга кодов Рида-Маллера над полем

GF(3) и обобщенные веса Хэмминга кода Нордстрома-Робинсона и кода

Кердока длины л=64, построенных в виде линейных кодов над кольцом

Z . t

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

6. Разработаны к исследованы по критерию энергетического выигрыша сигналыш-кодоЕые конструкции на базе сверточных кодов и сигналов KAM. Исследованы различные алгоритмы декодирования разработанных сигналыю-кодовых конструкций.

Положения выносимые на защиту

1. Новый алгоритм декодирования по максимуму правдоподобия кодов Рида-Маллера первого .порядка и результаты анализа корректирующей способности рекурсивного алгоритма декодирования кодов Рида-Маллера первбго порядка.

2.'Новые алгоритмы декодирования по максимуму правдоподобия кода Нордстрома-Робинсона в дискретном и гауссовском каналах связи.

3. Точные выражения для обобщенных весов Хэмминга кодов Рида-Маллера над полем gf(3) и точные значения обобщенных весов Хэмминга' кода Нордстрома-Робинсона и кода Кердока длины л.64 построенных в виде линейных кодов над кольцом Z^.

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

сверточными кодами с частичной памятью.

5. Оптимизированная по критерию' максимального энергетического выигрыша сигналыю-кодовая конструкция на базе сварточных кодов и сигналов KAM.

Практическая значимость работы ■■

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

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

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

- Для разработанной сигналыю-кодовой конструкции на. базе сверточных кодов и ■ сигналов KAM написан пакет программ, реализующих кодирование и различные алгоритмы декодирования сигнально-кодовой конструкции. Проведено моделирование разработанной сигнально-кодовой конструкции с различными алгоритмами декодирования. Результаты моделирования показывают, что предложенная сигналыю-кодовая конструкция дает энергетический выигрыш равный 4.8 'dB при вероятности ошибки на бит равной ю"6. При списочном декодировании данная конструкция дает дополнительный энергетический выигрш равный 0.4 при вероятности ошибки на бит равной Ю"5.

Практическая значимость работы подтверждена актами о внедрении.

Апробация работы

Результаты раОоты докладывались на х-й Всесоюзном симпозиуме по проблемам избыточнрсти в информационных системах (Летшград-1989), на советско-французском международном семинаре по теории алгебраического кодирования (Париж-1991), на международном симпозиума по теории связи и ее приложениям (Великобритания 1993), на научных семинарах в ИПШ1 РАН. Публикации

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

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

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

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

Первая глава посвящена разработке и анализу алгоритмов декодирования кодов Рида-Маллера первого порядка (РМ-1), а также определению обобщенных весов Хэмминга для кодов Рида-Маллера над снз).

В-§1.1 предлагается новый алгоритм декодирования кодов РМ-1 по максимуму правдоподобия с мягким решением, сложность которого на .величину порядка л (л-длина кода) меньше, сложности известных алгоритмов [1].

Коды РИ-1 имеют следующие параметры: длина кода п=2т, число информационных символов- 1, минимальное расстояние д=2т"1. Хорошо известен алгоритм декодирования кодов .РМ-1 по максимуму правдоподобия на основе быстрого преобразования Уолта (БИУ). Этот алгоритм заключается в вычислении коэффициентов БПУ принятого вектора и с определении номера максимального по абсолютной величине коэффициента. . Основная идея предложенного в работе алгоритма заключается, в . том, что для определения переданного кодового слова не требуется нахождения всех коэффициентов БНУ, а достаточно найти , лишь максимальный по абсолгтной величине коэффициент БПУ. На этапе 1 -предложенного алгоритма выполняются

первые (ш—з) итерации БПУ, в результате чего получаются некоторые

величины и ■ Каждой четверке элементов • ы , и ,

О п- 1 ^ 4й»0' 4ЙМ '

"«л.г' 'с=0»п/4_1 соответствуют четыре элемента спектра БПУ:

4 А + О

(г.

' г»ЫЗ '

- г , г )•=.(>/ | < г э 4й» о

(«•О ' ' 4*»2' 4Й»Э' " '4й»0' 4 А ♦ 1 ' 4г>»2

где //4-матрица Адамара размерности 4x4. Пусть р р = | г I , р = 12 |

*4к»0 <4»0 4 А♦О 4Л»0

максимальный по абсолютной

V )Н ,

43>«3 4 '

величине

I. Обозначим через у.

р

коэффициент БПУ. Для

определения коэффициента у^ необходимо вычислить величины

у =шах{р

,}, Л=0,л/4-1,

Тогда коэффициент у. может бить найден по формуле у„=гоах{у ,..., р р о

у }. Прямой путь поиска величин у . , который реализуется в

п/4 - 1 Л

алгоритме основанном на БПУ, заключается в вычислении всех величин

4 >»♦ О ' 4 Ь* 1 '

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

Л

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

1. Вычислить величины

тах { к

4 А» Л,.

т!п ( и . ч .

2. Вычислить величины

(1 > у ■ ы

' I. л

4 й.р

где 1л,рЛ€{0,'1,2,3), lb.Pt,'1iг>^

3. Вычислить величину "'•р'!' ' +

В работе показано, что эта процедура требует 3 операции сложения, 4 операции сравнения и 2 операции взятия модуля действительного числа, что позволяет уменьпить сложность декодирования без потери корректирующей способности алгоритма. Сложность всего алгоритма определяется следующими выражениями: п*.1од2 л-1.25л+2 сложений действительных чисел.

«НИ

1.25л+1 сравнений действительных чисел и л/2+1 операций взятия

модуля действительного числа. Всего п- 1одггч л/2* 4 операций с

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

основанный на БПУ требует п-1одгп сложений действительных чисел, л

сравнений действительных чисел и л операций взятия модуля

действительного числа. Всего п-1одгп*2п операций с действительными

числами. Таким образом, сложность предложенного алгоритма на 1.5л

операций меньше сложности алгоритма основанного на БПУ.

В §1.2. определяются области правильного декодирования

рекурсивного алгоритма декодирования кодов РМ-1 в гауссовскои и

дискретном каналах связи [2J, выводится верхняя граница для

вероятности ошибки рекурсивного алгоритма [3,4].

Рекурсивный алгоритм декодирования кодов РМ-1 имеет лкноПнуп

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

алгоритм но -является 'алгоритмом декодирования по максимуму

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

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

.рекурсивного алгоритма. В работе доказаны следуюаие утверждения.

Утверждение' 1.1. Обозначим через р отношение сигнал/пум. Тогда

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

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

I о »1 2J X я*

Р' < Т [ ttin (2е хр (Л2 яг / 2)) Ф (А а l/expfA 2J )ф( - --■'-■•'-]♦

«г- L. J-1 » Л >0 J J ■> J \ ■> V 3j I

, -2J+\ s2U)n/2J + exp<-Aj2^(-^j}) ,

где ф ( > "f—aW— I exp( -x2 / 2) dx, s2-2Jl[2Rfl), Я-Л/п, n-длинл кода.

-со

Обозначая Л«ллз и выбирая х^-2J"1/з2 получаем при

Кг-* ехр(-Лг/2)[ £ Jml* 2"" .0(1)].

Отметим, что вероятность овибки декодирования по максимуму правдоподобия при р-«я задается неравенством

ехр( -Л1 / 2 ).

Утйерждение 1.2. Рекурсивный алгоритм дает правильное роионнч яо

всех случаях когда вектор пуна е=(е ,е ,...,с ) удовлетворяет

0 2 п

неравенству: ^

2 Iе |<л/2, (1)

1 <

где £с{0,2,...,п-1 ), |Ь|=л/2.

Кроне того показано, что есл1^ выполняется неравенство (1) то вектор пума е также удовлетворяет неравенству 1(£1.е*<л/2. Таким образом, алгоритм осуществляет правильное декодирование в области, определяемой выражением (1), которая включает в себя евклидопую сферу радиуса Ул/2^.

В §1.3 выводится точная формула для расчета обобщенных весов Хэмминга кодов Рида-Маллера над ср(3).

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

кода с.

Обозначим через я(и,га)-код Рпда-Маллора порядка и длины и через к(и,в)-число информационных символов кода я(и,т). В работе доказаш! следующие утверждения. Утворадение 1.3^

Для данных и,га, и г, 1<т%к(и,т), число г может быть представлено единственным образом, в виде следующей суммы:

Г "= X Ми( ,ш ),

I»1

где и равно первому а'. такому что к(и1 ,т' )<г, и и -тах(0,

1

и-(ст-1) (ш-га 'VI)}, га -ш , и «и +1 если Г к{ и ,ст )<г. Если же

* I « -1 ' < 1-1 и J'J

1 1

£ /с(и )>г, то в равно первому я'т , такому, что

J*l < -1

£ ,а')<г, И и(-тах{0, (и( 1+1 )-(д-1) (т( ^га')).

Утверхдение 1.2. Пусть /с(и ), тогда

г

т

I -1

где

1 -1

(<7-1 ) (Л1( _ 1 -Л!( ) ) + 1, т

Ч -1

<т

( '

Вторая глава посвящена разработке и анализу алгоритмов декодирования кода Нордстрома-Робинсона, а также определению обобщенных весов Хэмминга кода Нордстрома-Робинсона и кода Кердока длины п=64, построенных над кольцом 2 .

4

В §2.1. описан алгоритм декодирования по максимуму правдоподобия кода Нордстрома-Робинсона в гауссовском канале связи [5].

Нелинейный двоичный (16,8)-код Нордстрома-Робинсона имеет максимальную мощность (число кодовых слов) среди двоичных кодов длины л=1б с минимальным расстоянием с?*б. Этот код является 'систематическим. Число к информационных символов равно 0 и связано с мощностью м соотношением №2*. Любой другой систематический код с л=1б и <2-6 имеет не более семи информационных символов. Во многих случаях это обстоятельство имеет решающие значение при выборе кода для обеспечения • надежной работы систем передачи и хранения информации. Так, например, код Нордстрома-Робинсона используется в качестве внутреннего кода в обобщенных-каскадных кодах используемых для исправления ошибок в полупроводниковой памяти ЭВМ. Он также используется в векторных квантователях случайных сигналов, таких как ошибка линейного предсказания речевого сигнала.

Известно, что код Нордстрома-Робинсона может быть представлен в виде объединения восьми смежных классов по коду Рида-Маллера [16,5,8]. Таким образом, для декодирования кода Нордстрома-Робинсона мы можем использовать в каждом смежном классе декодер кода РМ-1 [16,5,8). Предложенный в работе алгоритм заключается в следующем. В каждом смежном классе проводится декодирование кода

РМ-1 по алгоритму описанному ц §1.1, "при этом операции повторяющиеся в^ различных смежных классах выполняются только один раз. Результатом декодирования в каждом смежном классе i, 1=0,1, являются следующие величины: номер максимального по абсолютной величина коэффициента БПУ и гзначение этого коэффициента,

т.о. \г l-naxcl*'" I, 1*«" |, * 1., I • * |>. где z'*-' -

в ^ О 1 15 О 15

коэффициенты БПУ i-го смежного класса. Затем из восьми смежных классов выбираем смежный класс t, в котором получен максимальный коэффициент \z I«шах{Iz \,\г z I). Величина t определяет

t в в в

О 1 7

значение трех информационных символов, а величины st ■ и у-bslgnlz ), гдо baign(x)-| определяют значения оставшихся

в ^ ^ — I f Х\ U _

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

Робинсона по максимуму правдоподобия в гауссовском канале связи и требует 146 сложений действительных чисел, 161 сравнений действительных чисел и 65 операций взятия модуля действительного числа. Всего 372 операций с действительными числами. Отметим, что лучиий из ранее известных алгоритмов требует 550 операций с действительными числами.

В §2.2. разработан алгоритм декодирования по максимуму ^ правдоподобия кода Нордстрома-Робинсона в дискретном .канале связи.

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

можем оценить вероятность того, что переданный вектор принадлежит данному смежному классу и на основании этой оценки исключить часть смежных классов из дальнейшего декодирования, что также позволяет уменьиить сложность декодирования кода Нордстрома-Робинсона. D работо показано, что поело выполнения первой итерации по рекурсивному алгоритму дальнейшее декодирование необходимо проводить самое больнее в четырех смежных классах. Предложенный в работе алгоритм требуот 93 операций сложения, 43 операций сравнений и 65 операций пзятия модуля. Всего 201 операция.

В §2.3 найдены обобщенные веса Хэмминга кода Нордстрома-Робинсона и кода Кердока длины п-64, построенных над кольцом Z4.

Пусть С некоторый Z^-линейный код. Определим обобсонный пес Хэмминга порядка г кода С выражением

(C)-nin{ IX(D) I : D - подкод кода си г=1одг I £>| }. В предлагаемой работо доказываются следуюкие свойства обобщенным весов Хэмминга Z линейных кодов.

1. Для произвольного Z -линейного кода С выполняются Перапонстпа

1 <d (С) <d (С) . . . <d . АС)<п;

t 2 I о ч \с i

если d (С) =d (С), ТО d (С) <d (С), jt»1 , log I С| .

г- г*1 г» 1 г* 2 2

2. Пусть СХ- код дуальный Z4-линейному коду С. Тогда

{cí_ (С): r=1,log2 | С| ) = {1,1,2, 2, ..'.,n,n) Hd[ (С) , log2 I С I ).

Также как и в случае кодов построенных над Полем, обобценпыо леса Хэмминга кодов построенных над кольцом Za определяют характеристики этих кодов в капало с частичным подслупиванием. Для определения г бит информации необходимо получить а канальных символов", где d^(c) обобщенный вес Хэмминга порядка г

кода с построенного над 2f.

Известно, что код Нордстрома-Робинсона и кода Кердока могут быть построены как Z4-линейные коды. В работо доказаны следуюиие утверждения.

Утверждение 2.3. Обобщенные веса Хэмминга кода Нордстрош-Робипсона задаются следуюаим упорядоченным мнохостпоа: {4,5,6,6,7,7,8,3).

Утверждение 2.4. Обобщенные веса Хэмминга кода Кердока длины л»64 задаются следующим упорядоченным множеством: {16,22,26,27,28,29,30,30,31,31,32,32).

Отметим, что лучший известный линейный код над gf(4) длины л»8 и размерности к= 4 имеет <3=4. Таким образом, при использовании этого кода для определения двух бит информации достаточно получить четыре символа передаваемого сообщения. Если же используется код Нордстрома-Робинсона, то, как следует из утверждения 2.3, для определения двух бит информации необходимо получить по крайней мере пять символов передаваемого сообщения.

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

В §3.1 построен высокоскоростной, некатастрофическй код с частичной единичной памятью [л,k lie ) = [2",2°'-m-l |т-1 ], с d =4.

О 1 fr»«

Введем последовательность информационных слов длины

к:х ,х ,...,х ,х ,х , где индекс обозначает момент времени i. 12' ' i -1 ' i' I ♦ 1

Тогда последовательность кодовых слов длины л есть

У ,У ,■.•,у ,у ,у , где Ф(х ,х )«=у =х G +х G , х -0, а '|"г' " i -1 '' i' ■* i«i i-i' i •*« to <-i i' о

Go-kxn невырожденная матрица, с -некоторая кхп матрица irank(Gi)<k). Если rank{Gi)-k. то соответствующий код есть код с полной единичной памятью (ПЕП). Если же ranklG )<к, то получаем ЧЕЛ код. Пусть матрицы Go и с представляются в виде

Гс

00 , G = 1 1 0

G G

Ol Ii

где G и G - к *п невырожденные матрицы, G и g - к хл матрицы, 01111 00100

причем, к-к *к . В случае ЧЕП кодов G »[0] и, следовательно,

О 1 __I о

гал*(с . Соответствующий ЧЕП код будем обозначать через ln,*ol*].

Введем следующие обозначения: g*0' (о)-матрица размера 1x2" из одних единиц: g" 1 (m)-матрица размера га.2". столбцами которой являются все различные комбинации длины т: с1 " (т)-мдтрица размера

|™|х2ст, строки которой получены из строк с11' (га) как все возможные посимвольные произведения i строк.

Тогда матрица воа искомого ЧЕП кода задается равенством

С,0,(т)

с = с1 "(я»

оо '

„( т-2 ) . ,

О (Ш)

Пусть С(т~1 ' (т) = ( д ,д ,...,д )т, т.е. д ,д ,...,д -строки матрицы

12 гч 1 2 п

С1 (/л). Тогда матрицы искомого ЧЕП кода задаются равенствами: С = (д ,д...... )т, С =(д ,...,д )т.

0 1 I 2 ш- 1 112 п

Утверждение 3.1. Описанная конструкция приводит к

некатастрофическому ЧЕП коду [ 2"*, 2т-т-1 |га-1 ], с с?Ггвв=4» кодовая регаетка которого имеет 2™"1 состояний.

В §3.2 рассматриваются вопросы построения кодов с частичной единичной памятью (ЧЕП) и кодов с частичной памятью два па осноео подколов нелинейных кодов Лдамара [7].

Нн будем строить нелинейные коду с частичной памятью на основе регулярных решеток обладающих следующими свойствами. Каждый узел в х-ой колонке соединяется ветвями с некоторыми узлами в (а+1)-ой колонке. Каждая ветвь помечается двоичным вектором длины п. Набор ветБей соединяющих какие-либо два узла будем называть пучком, число ветвей в пучке является постоянным для всех пучков в данной реиетке. Векторы - соответствующие ветвям выходящим из некоторого узла могут быть получены как сумма некоторого вектора с векторами соответствующими ветвям ■ выходящим из нулевого узла. Каждый путь в реиетке будет соответствовать кодовому слову нелинейного кода с частичной памятью.

Обозначим нелинейный ЧЕП код через 1п,И \м ), где л - длина векторов на ветвях, н - число ветвей выходяпих из одного узла, и - число узлов в колонке. Таким образом м - число ветвей б одном пучке.

Обозначим через СМч'01' } - (л,м) нелинейный блоковый код длины л, мощности н. я'01 ,...»д'""11 - кодовые слова этого кода. Введем операцию отображения индекса х е(0,.,. ,я-1} о

соответствуюцее кодовое слово е о, т.е. х -

.....о,

Определим сумму кодов {?,£?, выражением

О,

Пусть

(п,« ), (п,ма),..., (л,) нелинейные блоковые коды.

(О)

(и и ...I)

12 I .

)

'(Ч

( 1 ) (J) (К) ,

+Чг +-.-+Ч, Ь

(2)

1-0,... -1; >0,...,м-1; .../ Л-о,.. .,^-1. Тогда операция -» отображающая индексы х'1' е (О, ..., м -1}, х(а|€ {О,... ,мг -1),... ,х( г 1 е СО, . ) в кодовое слово кода о

определяется следующим образом:

и,п.*,г'.....х'п ) - О - и*11- 0) )+(х121 -» ............. о,).

Знак '+' обозначает покомпонентное сложение векторов по модулю два. Матрицы типа (2) будем называть квази-порождающими матрицами. Тогда квази-порохдаюаая матрица нелинейного ЧЕЛ кода на основе

• кодов ооо - (л, мо //г ), £?01 - (л, м ), 1 = (л, мх ) имеет вид

О О

"о 1 "11

(3)

Векторы V соответствующие пучку соединяющему узлы i Ь

определяются следующим образом: ví ! ''11. i,j*0,...,мl-^^; а-о,.. .,но/мг-1. Текущий выходной вектор . длины л вычисляется по формуле

, , ( О ) (II.

0„

Квази-порождаювая матрица.нелинейного кода с частичной памятью два

имеет вид

на основе нелинейных кодов о , о ,о , о ,0

о о ' "о 1 ' "о 2 ' "11 ' "г 2

о й

"о 1 "11

<? о

оа "г 2

(4)

Текущий выходной вектор длины а вычисляется по формуле

Конструкция 1

Пусть А - матрица размерности 11x11. полученная из матрицы Ад'амара типа Пейли порядка 12 выкидыванием первой строкой и первого столбца и заменой единиц нулями и минус единиц единицами. Пусть л -[а а .,а), где а - 1-я колонка матрицы л. Сформируем два различные матрицы Адамара

Го О

я

о

от

коды

я

Теперь сформируем

• ={0Ч2) ,(121 }

*0 0

матрицы я я . Нетрудно видеть, что код с имеет <1 =12.

Уг во

О ,0 ,0 0 0 0111

О А

следующим образом: кодовыми словами кода р являются строки а кодовыми словами кода являются строки матрицы квази-порождающей матрицей (3) Минимальное расстояние кода

0=

О 1

равняется двум. Таким образом,

следовательно <*=2. мы получили (12,24)12)

нелинейный ЧЕП код

с3 =12 и ¿=2. Отметим, что невозможно построить линейный ЧЕП код

/рее

ЧЕП

код

с такими параметрами. Более того, линейный (12,16(0) стен.

матрицы Адамара сформированные по правилу

(} =12 также неизвестен.

/ре

Пусть я ,я

Сильвестра

Пусть

24

Я

Я

я -я 12 12

Я

коды о ,0

о о 1 1 1

0ооз{0 • • 1 >■ кодовыми

2 <

формируются словами кода

* *

Гя ' II

1 2 1 2

* *

я -Я

1 2 I 2

следующим

образом:

О 1

являются строки

матрицы я , а кодовыми словами кода ¡? являются строки матрицы * __ 2 4 11,

яг . Нетрудно видеть, что описанный код Очевидно,

что мы можем продолжить

имеет с? «24 и а-4.

/г*«»

эту процедуру и получить 121 II 4-21, .¿>1.

(12.1,24.il 12.1) нелинейные ЧЕП коды с <3

Конструкция 2. Рассмотрим построение нелинейного кода с два. Пусть н - матрица Адамара порядка 12. Обозначим 1-ю стоку матрицы я. Сформируем кош £>00 ,0О1 ,(?02 ,<?,, '022

частичной памятью через Л( -следующим

образом: ö00 = io'1 2 1 ,1«12' ). ß0l-(VVW' Oa2-lh0 ,h4 ,/r ,/»6 >.

0n"(WW' Qzz:={ho'bio'h11'hio*hllh B Работе показано, что код с квази-порождающей матрицей (4) является (12,32|1б) кодом с d =12 и <¿=8/5. Отметим, что лучший из известных линейный

/гее

сверточный код с частичной памятью два длины л-12 с d =12 имеет

/г* е «

в два раза меньше кодовых слов.

В §3.3 рассматриваются вопросы разработки и оптимизации по критерию максимального энергетического выигрыша сигнально-кодовых конструкций на основе сверточных кодов и сигналов KAM [8].

Использование сигнально кодовых, конструкций (СКК) позволяет получать значительный энергетический выигрыш в различных каналах связи, особенно в каналах с ограниченной полосой частот, например, в телефонном канале. Вследствие этого, в настоящее время ведутся интенсивные исследования по построению оптимальных СКК. Сверточные коды, коды с частичной единичной памятью и блоковые коды предлагались в качестве внешних кодов для СКК. В данной работе рассматривается вопрос построения и оптимизации по критерию максимального энергетического выигрыша СКК, . где в ■качестве внутренних кодов используются сигналы с ■ квадратурно-амплитудной модуляцией (KAM-16),-а в качестве внешних используются сверточные коды с длиной кодового ограничения >>'=6. Вследствие того; что существует большое количество различных интегральных схем (ИС) для кодирования и декодирования сверточных кодов, сложность аппаратной реализации такой СКК может быть значительно упрощена. В частности ИС французской фирмы 'soper' позволяет проводить декодирование Витерби различающихся по скоростям сверточных кодов с длиной кодового ограничения 4

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

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

Построение и оптимизация СКК Рассмотрим следующие две конструкции. В конструкции 1 (базовая конструкция) используются следующие четыре внешних кода: (4,1,20)-сверточный код, (2,1,10)-сверточный код,

(4,3,5)-выколотый сверточный код и код с проверкой на четность. Все коды имеют длину №=208. В качестве внутренних кодов используются сигналы ЮШ-16. Число информационных символов данной СКК ;с=501. Для данной конструкции было проведено имитационное моделирование, которое показало, что первая пара внешнего и внутреннего кодов вносит решающий вклад в вероятность ошибки декодирования. Следовательно можно увеличить число информационных символов во втором и третьем внешних кодах, увеличивая при этом вероятность их опибочного декодирования, но липь незначительно увеличивая вероятность ошибки декодирования всей СКК.

В конструкции 2, первый и четвертый внешние коды остаются без изменения. Второй внешний код строится' следующим образом. Обозначим^- (2,1,10) сверточный код, сг~ (4,3,5) выколотый сверточный код, коды с , С2, зшбют длину №104. Тогда кодовые слова второго внешнего кодов формируются по правилу лг2г'1гг.1 1*2(г)-(а|а+Ь), аеС.,, ЬеС^ , Третий внешний код строятся следующим образом. Обозначим р -(4,3,5) выколотый сверточный код, р - код с проверкой на четность, коды о ,р имеют длину №52. Тогда кодовые слова третьего

внешнего кодов формируются по правилу

Т3-<Т3,1,У3,21Т3.3,У3..'',Г3*,а1 ' а2 ' аз ' а1 1 +а2 • аз ♦ Ь) '

а1,аг'азеС1' ЬбС2-

Число информационных символов данной СКК к*557.

Сложность декодирования вышеприведенных конструкций может бить оценена как сложность декодирования трех сверточных кодов по алгоритму Витерби и сложность декодирования кода с проверкой на четность. Это значительно ниже сложности декодирования по максимуму правдоподобия всей конструкции в целом. Кроме того, все сверточные коды использованные в вышеописанных конструкциях ' имеют одну и ту-же длину кодового ограничения \>=6. Следовательно, при декодировании всех сверточных кодов можно обойтись использованием одной интегральной схемой.

Результаты моделирования показывают, что по сравнению с передачей сигналов КАМ-16 без кодирования базовая конструкция дает энергетический выигрыш равный 3.8 <3в. конструкция 2 дает энергетический выигрыш равный 4.6 ав при вероятности ошибки на бит равной Ю"6. Таким образом, конструкция 2 дает энергетический выигрыш равный 0.8 <1в по сравнению с базовой конструкцией. Отметим

• также, что использование списочного декодирования сверточных кодов при декодировании ИСК дает дополнительный энергетический выигрыш равный 0.4 ав при вероятности ошибки на бит равной Ю~5.

Выводы

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

2. Исследована корректирующая способность рекурсивного алгоритма декодирования кода Рида-Маллера первого порядка в гауссовском и дискретном каналах связи, получена верхняя граница для

• вероятности ошибки рекурсивного алгоритма.

3. Разработаны алгоритмы декодирование по максимуму правдоподобия кода Нордстрома-Робинсона в дискретном и гауссовском каналах связи имеющих меньшую сложность по сравнению с известными алгоритмами.

4. Найдены обобщенные веса Хэмминга кодов Рида-Маллера над полем от(Э) и обобщенные веса Хэмминга кода Нордстрома-Робинсона и кода Кердока длины п-64, построенных над кольцом Т.

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

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

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

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

1. А. Е. ляихниа, с.Н.Лицып, с. л. Портной. Декодер кодов Рида-Маллера первого порядка по максимуму правдоподобия/7 Л/0 N1775857.

2. A.E.Ashikhmin, S.ll.Litsyn. A fast search for the maximum element of the fourier spectrum.// Algebraic Coding. Lecture Notes in Computer Science, v.573, G.Cohen, S.Litsyn, Л.Lobstein, G.Zemor (Editors), 1992, P.134-141.

3. А. E. Ашихмин, • с.Н.Лицып. Анализ квазиоптимальных алгоритмов декодирования биортогоналышх кодов// Радиоэлектроника.' Изв. вузов СССР. - 1980. - N11. - Т.31 - С.30-34.

4. л.Е.Апихнин, с.Н.Лицып. Анализ квазиоптималышх алгоритмов декодирования биортогоналышх кодов// Радиоэлектроника. Изв. вузов СССР. - 1990. - ИЗ. - Т.32 -С.15-22.

5. А. Е. Апихнин, С.Н.Лицып, с. Л. Портной. Декодер кода Нордстрома-Робинсона// А/0 N1797164.

6. л. Е. Ашиххин, В. л. Зиновьев, с.Н.Лииип, с:Л. Портной. Устройство для декодирования кода Нордстрома-Робинсона в дискретном канале// А/0 N1736008. _

7. в. в. Зябпов, а. е. Алихнин. Нелинейные ЧЕ11 коды на основв нелинейных кодов Адамара.//28 конференция молодых ученых ИППИ РАН, С.8-12.

8. V. V. Zyablov, A.E.Ashikhmin, V.R.Sldornnko, L'.Dottnar, U.Sorger. Coded modulation schemes on the Ьазо ' of convolutional codes and 15 . quadrature amplitude-shift keying (QASK) signals.// Proceedings of the second international symposium on communication theory and applications. United Kingdom, 11-16 July 1993, P.185-188.