Содержание к диссертации
Введение
Глава I. Введение 4
1.1. Принципы сверточного кодирования 8
1.2. Декодирование сверточных кодов 21
1.3« Потенциальные корректирующие свойства свер точных и блочных кодов 27
1.4. Сложность реализации помехоустойчивого кодирования 35
1.5. Каскадное кодирование 37
1.6. Задачи исследования 40
Глава 2. Построение сверточно-блочных каскадных кодов на базе сверточных кодов с единичной памятью 41
2.1. Построение сверточно-блочных каскадных кодов и нижняя граница свободного кодового расстояния 42 /
2.2. Алгоритмы декодирования сверточно-блочных каскадных кодов по расстоянию 45
2.3. Обменные соотношения вероятности ошибки и стирания для сверточных кодов с единичной
памятью. ' 55
2.4. Алгоритм декодирования сверточно-блочных каскадных кодов по вероятности 63
2.5. Оценка сложности задания, кодирования и декодирования сверточно-блочных каскадных кодов. 76
2.6. Заключение 84
Глава 3. Построение блочно-сверточных каскадных кодов на базе сверточных кодов с максимальным достижимым свободным расстоянием 86
3.1. Построение блочно-сверточных каскадных кодов и нижняя граница свободного кодового рассто яния 86
3.2. Алгоритм декодирования блочно-сверточных каскадных кодов и оценка экспоненты вероятности неправильного декодирования 90 /
3.3. Оценка сложности задания, кодирования и декодирования блочно-сверточных каскадных кодов 99 ^
3.4. Алгебраическое построение недвоичных сверточ-ных кодов при малых длинах кодового ограничения 109
3.5. Сравнение сложности декодирования усеченных сверточных и блочных кодов 114
3.6. Заключение 124
Глава 4. Использование многопозинионных сигналов и сверточных кодов Е каскадных системах кодирования 131
4.1. Использование ортогональных сигналов в каскадной сигнально-кодовои системе связи 132
4.2. Теоретическое и экспериментальное исследование проблемы группирования ошибок на выходе сверточного декодера Битерби 147
4.3. Оценка обнаруживающей способности для класса блочных кодов Ї63
4.4. Сверточно-блочиые каскадные системы кодирования 177 ^
4.5. Совмещение сигналов с амплитудно-Фазовой модуляцией с недвоичным сверточным кодом 192
4.6. Заключение 198
Глава 5. Заключение 200
Приложение I. Документы о внедрении 204
Приложение 2. Програтлма моделирования каскадных сигнально-кодовых систем связи 213
Приложение 3. Программа расчета вероятности ошибки и стирания для недвоичных обобщенных каскадных кодов. * 223
Литература
- Принципы сверточного кодирования
- Построение сверточно-блочных каскадных кодов и нижняя граница свободного кодового расстояния
- Построение блочно-сверточных каскадных кодов и нижняя граница свободного кодового рассто яния
- Использование ортогональных сигналов в каскадной сигнально-кодовои системе связи
Введение к работе
Дальнейшее развитие народного хозяйства страны невозможно без полного удовлетворения его потребностей в услугах связи. Поэтому в основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года, утвержденных на ХХУІ съезде КПСС, в качестве одной из основных задач в области связи выдвинута задачи создания "единой автоматизированной сети связи страны на базе новейших систем передачи информации". Решение этой проблемы немыслимо без создания высококачественных линий связи и без увеличения эффективности и качества действующих систем связи, В решении этой проблемы значительную роль призвано сыграть помехоустойчивое кодирование в каналах связи, которое позволяет увеличивать скорость передачи информации при одновременном повышении надежности передачи данных. Особенно перспективным является использование методов кодовой защиты в высокоскоростных спутниковых каналах связи, где для достижения высокой эффективности необходимо использовать все возможные методы повышения надежности передачи информации.
Необходимыми предпосылками для эффективного использования методов кодовой защиты являются: во-первых, разработка новых методов помехоустойчивого кодирования, направленная на значительное упрощение реализации кодирования и декодирования и на возможно большее согласование реализуемых корроктирующих свойств с характером ошибок в реальных каналах; во-вторых, развитие электронной и вычислительной техники, расширение производства интегральных схем и увеличение степени интеграции последних. Это позволит создавать компактную аппаратуру кодовой защиты передаваемой информации, способную существенно увеличить эффек-
тивность использования каналов связи.
В настоящее время известно большое число классов кодов, исправляющих ошибки (корректирующих кодов), которые можно разделить на две группы: блочные и непрерывные. В первом случае непрерывная последовательность информационных символов разбивается на блоки по И.0 символов. Операции кодирования производятся над каждым блоком отдельно независимо от других в соответствии с выбранным кодом. Каждому возможному информационному блоку при кодировании сопоставляется блок из ҐІ кодовых символов, flo>h-o Этот ^0K передается по каналу связи, искажается шумом, а затем декодируется независимо от всех других переданных блоков. Кодовый блок называется кодовым словом, а величина /2 - длиной блочного кода. При использовании непрерывных (сверточных) кодов информационная последовательность подвергается кодированию без разбиения ее на независимые блоки. Информация обрабатывается непрерывно и каждой полубесконечной информационной последовательности сопоставляется полубесконечная кодовая последовательность. Информационная последовательность образуется следующими друг за .прутом блоками из / информационных символов, а кодовая последовательность - блоками из Иі кодовых символов, /2 ?-№ , На выходе кодирующего устройства блок длины tl из символов кодовой последовательности появляется при поступлении на его вход данного информационного блока и некоторого числа предыдущих блоков из Ы. информационных символов. Как показывают исследования [36, 23, 38, 39] , кодирующие и декодирующие устройства сверточных кодов реализуются проще аналогичных устройств блочных кодов при одинаковых корректирующих свойствах. С другой стороны, при одинаковой сложности реаяизаыди блочного и сверточного кодирования - декодирования сверточные коды могут обеспечить меньшую вероятность ошибочного декодирования на двоичный символ (бит) [36] .
Хорошо известно [8?, что большинство реальных каналов связи (в том числе космические и спутниковые каналы) наиболее слизки к модели канала с аддитивным белым гауссовским шумом. Основной выигрыш, достигаемый при использовании кодов в таких каналах,
может быть оценен в терминах уменьшения показателя і (отно-
/Уо
шение энергии сигнала на бит к спектральной плотности мощности
шума), необходимого для обеспечения заданноЁ вероятности ошибки на двоичный символ. Уменьшение этой величины дает возможность уменьшить мощность передатчика, либо увеличить скорость передачи. Однако, использование корректирующих кодов для уменьшения величины - часто ограничивается сложностью реализации их коди-рования и декодирования, особенно при больших длинах блочных кодов и больших длинах кодовых ограничений сверточных кодов. (Понятие длины кодового ограничения сверточных кодов будет дано ниже). В то же время значительное уменьшение -^ достигается именно в этих условиях [I6J. Таким образом, на первый план выдвигается задача построения таких схем кодирования и декодирования, сложность реализации которых с ростом длины кода (длины кодового ограничения) увеличивалась бы как можно медленнее, а сам код при этом обладал бы хорошими корректирующими свойствами. Этим требованием в значительной мере отвечают блочные каскадные коды, исследуемые в работах [28, 5, б]. Они строятся на основе других блочных кодов меньших длин. Использование в качестве составляющих в каскадных конструкциях сверточных кодов позволило увеличить возможности кодов исправлять ошибки 24, 25J.
Б последнее время очень интенсивно стали изучаться сверточ-ные коды с единичной памятью [44* 45, 46* 5l], где передаваемый кодовый блок зависит только от двух информационных блоков: поступившего на кодер и хранившегося там. Как показывают исследо-
вания, такие коды, во-первых, обладают лучшими корректирующими свойствами, чем обычные сверточные коды ["44, 5lj, и, во-вторых, они более приспособлены к каскадным схемам кодирования [45, 46].
Исходя из всего вышесказанного, актуальной задачей современной теории помехоустойчивого кодирования является дальнейшее усовершенствование каскадных схем кодирования, которые объединили бы в себе лучшие свойства сверточных и блочных кодов.
На решение этой проблемы и направлено настоящее исследование.
Целью данной работы, посвященной построению каскадных систем кодирования с использованием сверточных кодов, является:
Разработка алгебраических методов построения, комбинаторных оценок кодового расстояния, алгоритмов кодирования и декодирования и оценок вероятности неправильного декодирования различных систем каскадных кодов на базе блочных и сверточных кодов.
Разработка вопросов сложности реализации сверточного кодирования, сверточно-блочного каскадного кодирования и блочно-сверточного каскадного кодирования,
Разработка рекомендаций по практическому использованию каскадных систем кодирования на базе сверточных кодов и много-позшцюнных сигналов в каналах с аддитивным белым гауссовским шумом, а также в каналах с более сложным характером помех.
Во введении мы сформулируем основные задачи исследования, соответствующие поставленным выше целям- Для этого в параграфе I.I опишем различные классы сверточных кодов, а также дадим ряд определений и понятий, необходимых для дальнейшего изложения. В параграфе 1.2 будут исследованы вопросы декодирова-
ния сверточных кодов. Б параграфе І.З приведем потенциальные корректирующие свойства сверточных и блочных кодов. В параграфе 1.4 введем основные понятия сложности реализации сверточно-го кодирования и декодирования. Б параграфе 1.5 на эврестичес-ком уровне продемонстрируем принцип каскадного кодирования. Основываясь на введенных в этих параграфах понятиях, в параграфе 1.6 дадим развернутую формулировку задачи исследования.
Принципы сверточного кодирования
Рассмотрим передачу информации по линии связи, схема которой в укрупненном виде представлена на рис. І.І. При этом, в данном параграфе ограничимся лишь кругом вопрсов, связанных с помехоустойчивом кодированием.
Пусть на кодер сверточного кода, который состоит из регистра сдвига, содержащего /d Q -ичных ячеек памяти, ж линейной логической схемы (рис. 1.2) поступает информационная полубесконечная последовательность L-LotLxM - (I.I.I) где t г - О,0о t _ информаыионный блок из /t CL -ичных символов, т.е. tzCtltt tt tH, (I.I.2) ttjeGPfy), j=IJi,
Линейная логическая схема осуществляет линейные векторные операции в поле GF( p) и посылает в канал полубесконечную кодовую последовательность Учитывая то обстоятельство, что кодовый блок t свер-точного кода зависит от поступившего в момент на кодер информационного блока І и от хранящегося в регистре сдвига предыдущего информационного блока -i введенные сверточ-ные коды называются сверточными кодами с единичной памятью 45JH
Кодирование линейным сверточным кодом с единичной памятью MOJKHO записать в виде следующего уравнения dt -Lt Gb() + Lt-iGi()} -0, (I.I.5) где Go(6) ж Gt(i) матрицы с размерами H h . Если и &1 не зависят от t , то код будем называть постоянным.
В дальнейшем также будут рассматриваться и меняющиеся во времени коды (т.е. такие, кодер которых содержит линейную логическую схему с меняющимися во времени связями). Мы будем называть их периодическими, с периодом Тп , если Geti n) = Ge(t), 2=0,1- t otit?t... . Скорость передачи описанного сверточного кода будем определять как /? = тг Если информационная последовательность - 0 t . . кодируется в кодовую последовательностьd-do,с/л,.. - (I.I.5) можно переписать так
Здесь и в дальнейшем всюду будем считать, что все свободные места в матрице заполняются нулями.
Сверточные коды с единичной памятью называются катастрофическими, если для них конечное число ошибок в канале мо&ет вызвать бесконечное число ошибок при декодировании (вопросы связанные с декодированием будут подробно рассмотрены в параграфе 1.2). Коды, свободные от описанного выше эффекта, получили название некатострофических сверточных кодов [48J . Для того, чтобы сверточный код с единичной памятью был катастрофическим, должна существовать информационная последовательность С с бесконечным числом ненулевых блоков 6 , которая кодируется в последовательность о( с конечным числом ненулевых блоков с&і С51] Заметим, что как теоретическим, так и практический интерес представляют только некатастрофические коды.
Назовем весом Хэмминга последовательности Ы ,, число ее ненулевых компонент [27J. Обозначим этот вес через VtC (Ы) .
Расстоянием Хэмминга между последовательностями ос и of , которое мы будем обозначать через , назовем чис ло позиции, в которых с и ОС отличаются друг от друга [27]. (Так как в данном параграфе будем рассматривать только хеммингово расстояние, слово "хеммингово" будем опускать). Минимальное расстояние кода - это шшимальное расстояние между двумя кодовыгли последовательностями. Учитывая, что рассматриваются линейные коды, расстояние медду двумя кодовыми после дователъностямн равно весу некоторой третьей кодовой последовательности и, следовательно, минимальное расстояние для линейного кода равно минимальному весу его ненулевых компонент. Это свойство очень помогает при анализе возможности исправления ошибок линейными кодами. Различные свойства минимального расстояния сверточных кодов с единичной памятью можно исследовать, рассматривая блочные коды, порождаемые матрицами
Построение сверточно-блочных каскадных кодов и нижняя граница свободного кодового расстояния
Настоящая глава посвящена всестороннему теоретическому исследованию асимптотических возможностей нового класса сверточно-блочиых каскадных кодов и разработке алгоритмов кодирования и декодирования имеющих малую сложность и полностью реализующих корректирующие свойства этих кодов.
В параграфе 2.1 построены СЕК коды и получена нижняя граница их свободного кодового расстояния. В параграше 2.2 описаны алгоритмы декодирования СЕК кодов по расстоянию и даны оценки реализуемых корректирующих свойств кодов при этих алгоритмах. В параграфе 2.3 получены обменные соотношения вероятности ошибки и стирания сверточных кодов с единичной памятью. В параграфе 2.4 описан алгоритм декодирования СЕК кодов по вероятности, разработана методика анализа реализуемых корректирующих свойств и получена оценка реализуемой экспоненты вероятности неправильного декодирования. В параграфе 2.5 даны оценки сложности задания, кодирования и декодирования СЕК кодов.
Результаты настоящей главы вошли составной частью:в итоговый отчет в книгу [32] , а также опубликованы в работах [18, 29І.
Рассмотрим схему каскадного кодирования, где в качестве внутренних кодов используются двоичные сверточнне кодн с единичной памятью, а в качестве внешних кодов - блочные коды Рида-Соломона (рис. 2.1).
Двоичную информационную полубесконечную последовательность Л представим в виде прямоугольной полубесконечной матрицы, ко-торая с помощью горизонтальных линий разбита на подматрицы J , J l,CO # Каждая подматрица, содержащая лУ строк и №g стобцов, кодируется кодом PC над полем СРП ) . Назовем этот код внешним и обозначим его через B/7QJ Rf3)Of# J , где Ґ1$ - длина кодового слова, fc/з - скорость передачи кода, a Offe - кодовое расстояние. Б результате от полубесконечной Й І J - 1,00 . Каждая подматрица содержит информационной последовательности J переходим к вспомогательной полубесконечной последовательности О , которая представлена в виде прямоугольной полубесконечной матрица состоящей из подматриц гсд строк и /2уз столбцов.
Каждый из /2/з полубесконечных столбцов матрицы }f кодируем линейным двоичным периодически меняющимся во времени (с периодом Т"п ) сверточным кодом с единичной памятью L "А А) &А J гДе hflZfy-}) - длина входного кодового ограничения (так как рассматриваются сверточнне коды с единичной памятью, то % = J и таким образом, ид-Ґ2д ), /гдг-т скорость передачи кода, a Of А - свободное кодовое расстояние. Этот сверточный код будем называть внутренним.
Полученную в результате кодирования полубесконечнуто кодовую последовательность линейного двоичного сверточно-блочного Очевидно, что входное кодовое ограничение СЕК кода L- иАУ2д} а скорость передачи R = / /?g .
Обозначим свободное кодовое расстояние СЕК кода через с/ . Теорема 2,1.1. Свободное кодовое расстояние СЕК кода удовлетворяет соотношению с/г с/ -сґА- /& і (2.І.І) где Of нижняя граница свободного кодового расстояния СЕК. кода.
Доказательство. Б любой ненулевой кодовой последовательности имеется минимум с/в ненулевых столбцов (в силу кодирования внешним кодов). Каждый ненулевой столбец есть кодовая последовательность оверточного кода с единичной памятью, а поэтому имеет вес не менее Of А , что и завершает доказательство.
Рассмотрим асимптотику кодового расстояния СЕК кода. Зафиксируем скорость передачи /? . Пусть иА ОЭjftg- co и соответственно и — со .В этом случае асимптотическая нижняя граница (/Z) i— свободного кодового расстояния определя и ется следующей теоремой.
Построение блочно-сверточных каскадных кодов и нижняя граница свободного кодового рассто яния
В настоящей главе исследуется класс блочно-сверточных каскадных (БСК) кодов с внутренними блочными кодами и с внешними сверточными кодами с максимальным достижимым свободным расстоянием.
В параграфе 3.1 построены БСК коды и получена нижняя граница свободного кодового расстояния этих кодов. Б параграфе 3.2 описан алгоритм каскадного декодирования БСК кодов и дана оценка реализуемой экспоненты вероятности неправильного декодирования. Б параграфе 3.3 выведены оценки сложности задания, кодирования и декодирования БСК кодов. Б параграфе 3.4 алгебраическими методами построены недвоичные сверточные коды, для которых свободное кодовое расстояние равно длине выходного кодового ограничения. В параграфе 3.5 проведено сравнение сложности декодирования блочных кодов с лучшими на сегодняшний день методами декодирования по максимуму правдоподобия со сложностью декодирования по алгоритму Витерби усеченных сверточных (блочных) кодов.
Результаты настоящей главы опубликованы в работах [ 17, 19, 30 j.
Рассмотрим схему блочно-сверточного каскадного кодирования, где в качестве внутренних кодов используются двоичные блочные коды, а в качестве внешних кодов - недвоичные сверточные коды с максимально достижимым свободным расстоянием (рис, 3.1).
Информационную последовательность с нулями на проверочных позициях запишем с помощью ) _ преобразования, т.е. №Q . W.1.-W где LeG№k ). Пусть їїл-%-1 - длина кода PC над полем GPf J , где г2 , и пусть /2/э - делитель / . Тогда, как показано в 42? , если Q (х) является пороздающим многочленом кода PC с параметрами (flnj n) наД GPfy) , то -ичный свер точный код со скоростью Рп - - порождаемый с помощью
Gr(X/-Q [X] t является некатастрофическим и имеет свободное кодовое расстояние ?7?ги/з /2,е" & & +1 , где 1 /з - выходное кодовое ограничение сверточного кода, т.е. число кодовых символов, на которые влияет один информационный символ.
Информационная последовательность (3.1,1) кодируется вышеописанным сверточным кодом. Назовем этот код внешнигл и обозначим через В [ h&j &jGrtf] . Как указано в [ 42J , код В является несистематическим постоянным сверточным кодом. об) - преобразование закодированной внешним кодом последовательности можно записать в виде
Каждый из символов гге над GFte ) представляется как двоичный вектор длины Уд и кодируется внутренним линейным двоичным блочным кодом А1 &А)РА &А] » где /2А - длина кодового слова, IP А = -jf - скорость передачи кода и Ofa - кодовое расстояние.
Полученную в результате кодирования кодовую последовательность линейного двоичного блочно-сверточного каскадного (БСК) кода запишем в виде = fo/0jo/djo/2 . . .} , (3.1.3) где о/е, Є=0;С&, - блок- ., длины /2А двоичных символов.
Очевидно, что выходное кодовое ограничение БСК кода Ьо-Ґ2А-и$ , а скорость передачи R.-RA $B Заметим, также, что если для всех внутренних кодов выбирать одну и ту же кодирующую матрину, то полученный БСК код будет постоянным.
Обозначим свободное кодовое расстояние БСК кода через Or . Теорема 3.I.I. Свободное кодовое расстояние БСК кода удовлетворяет соотношению о/ с/СН)=С С з (3.1.4) /(к) где с - нинняя граница свободного кодового расстояния БСК кода.
Доказательство теоремы 3.1.1 аналогично доказательству теоремы 2.1.I и поэтому здесь не приводится.
Рассмотріш асимптотику кодового расстояния БСК кода. Зафик сируем скорость передачи л? . Пусть /2д +оо , Ь@ Со и со ответственно /j0—оо .Б этом случае асимптотическая нижняя гра ница 0 ($)z-@L свободного кодового расстояния опре деляется теоремой.
Наилучшая из известных асшлптотических оценок (приПд-+ со) достижимого при фиксированной скорости передачи кодового расстояния блочных кодов - это граница Баршамова-Гилберта (БГ) (13.12), согласно которой для двоичных кодов
Оценка для внешних кодов, представляющих собой недвоичные сверточные коды над Є г (z А) и являющихся максимальными, т.е. наилучшими для своих длин и скоростей передачи, определяется равенством [42J
Использование ортогональных сигналов в каскадной сигнально-кодовои системе связи
В данном параграфе будет рассмотрена каскадная сигнально-кодовая система связи (рис, 1.7), которая состоит из кодера и декодера сверточного кода, а такзае расширенного канала А .В начале рассмотрим модель расширенного канала А . Эта модель состоит из модулятора, аддитивного канала связи с белым гауссов-ским шумом tl( ) и синусоидальной помехой %() (последняя монет быть, например, обусловлена работой второго источника сигналов), линии задєрлїки с задержкой Г и демодулятора (рис. 4.1),
Модулятор работает следующим образом: если в момент времени к. с выхода кодера поступает % -ичный символ N(w (в дальнейшем всюду будем считать, что % 1б ), то модулятор посылает на интервале времени [н, Id+l в канал связи один из шестнадцати ортогональных сигналов Аосп\2іїШ //и\ \ » где Ао - амплитуда сигнала, а (Л. х ІОО+#(#) " круговая частота, /tf(\ ) d,i6 При прохождении по каналу связи передаваемый сигнал, во-первых, испытывает задержку 2" и, во-вторых, к нему добавляется белый гауссовский шум /ZfcJ с нулевым средним и с односторонней спектральной плотностью р , а также синусоидальная помеха cfc(e) .
Таким образом, на вход демодулятора поступает сигнал Х[6) f который можно записать в виде (t)-s(t Zhn(6) ()} t[OJ], (4.I.I) где 5(С/ - передаваемый сигнал, ҐІ\І/ _ белый гауссовский ШУМ» %( - синусоидальная помеха, a Z временная задержка передаваемого сигнала. При этом будем считать, что как модулятор, так и демодулятор имеют довольно точные эталоны времени и их работа может быть синхронизирована с помощью этих эталонов.
Кроме того, предположим, что довольно точно известно расстояние между модулятором и демодулятором и известна скорость распространения передаваемого сигнала. Эти условия накладывают ограничения на величину задержки. В рассматриваемой нами системе связи можно считать, что 10
Предположим также, что синусоидальная помеха имеет ту же структуру, что и передаваемый сигнал. То есть, на интервале времени Н К+1 j функция %() имеет вид BoSCft&nUfefe ?)] где Во - амплитуда синусоидальной помехи, U/e - круговая частота сигнала ( у - случайная величина, принимающая с равными вероятностями значения I, 2, ... 16), а Ср - равномерно распределенная на отрезке времени [ofIO J случайная величина.
Моделирование расширенного канала связи будет основано на анализе статистических свойств логарифма отношения правдоподобия (Ж)П). символ, в действительности поступающий на вход модулятора в момент времени J ; J(J - последовательность независшлых, одинаково распределенных случайных величин, принимающих значения из множества 1,2,...,16 с равными вероятностями; _ - отношение амплитуды помехи %() к амплитуде принимаемого сигнала S[) (при отсутствии синусоидальной помехи 52-0 )» Р - равномерно распределенная на отрезке [о,10 ] случайная величина.
Перейдем теперь к описанию различных методов приема ортогональных сигналов. Б начале рассмотрим случай отсутствия синусоидальной помехи, При когерентном приеме для декодирования используется следу ющая величина При некогерентном приеме для декодирования используется величина J-О
При оптимальном некогерентном приеме возникает задача оценивания неизвестной задержки . Точнее при декодировании должна быть использована следующая величина 7 Ггі л -гт "( i J- V) IJ вычисление максимума требует значительного времени. Для его уменьшения была использована 5-ти точечная аппроксимация величины Результаты численного моделирования показывают довольно хорошие свойства такой аппроксимации»
При наличии синусоидальной помехи осуществляется ее простая фильтрация. При когерентном приеме вместо,величины Хдууі Ы) в (4.1.9) используется величина
