Техносфера - Искусство помехоустойчивого кодирования

Содержание

Предисловие автора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14

Глава 1.

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17

1.1.

Кодирование для исправления ошибок:

Основные положения . . . . . . . . . . . . . . . . . . . . . . . . . .18

1.1.1.

Блоковые и сверточные коды . . . . . . . . . . . .19

1.1.2.

Хеммингово расстояние, Хемминговы сферы

и корректирующая способность . . . . . . . . . .20

1.2.

Линейные блоковые коды . . . . . . . . . . . . . . . . . . . . . . .23

1.2.1.

Порождающая и проверочная матрицы . . . .24

1.2.2.

Вес как расстояние . . . . . . . . . . . . . . . . . . . . .25

1.3.

Кодирование и декодирование

линейных блоковых кодов . . . . . . . . . . . . . . . . . . . . . .26

1.3.1.

Кодирование с помощью матриц G и H . . . .26

1.3.2.

Декодирование по стандартной таблице . . . .26

1.3.3.

Хемминговы сферы, области

декодирования и стандартная таблица . . . . .32

1.4.

Распределение весов и вероятность ошибки . . . . . . .34

1.4.1.

Распределение весов и вероятность

необнаруженной ошибки в ДСК . . . . . . . . . .34

1.4.2.

Границы вероятности ошибки в ДСК,

каналах с АБГШ и с замираниями . . . . . . . .36

1.5

Общая структура жесткого

декодера для линейных кодов . . . . . . . . . . . . . . . . . . . .47

Глава 2.

Коды Хемминга, Голея и Рида-Маллера . . . . . . . . . . . . . . .49

2.1.

Коды Хемминга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49

Содержание

-Contents.qxd 22/11/2004 12:58 PM Page 3 (Black plate)

2.1.1.

Процедуры кодирования и декодирования .50

2.2.

Двоичный код Голея . . . . . . . . . . . . . . . . . . . . . . . . . . .53

2.2.1

Кодирование . . . . . . . . . . . . . . . . . . . . . . . . . .54

2.2.2.

Декодирование . . . . . . . . . . . . . . . . . . . . . . . .55

2.2.3.

Арифметическое декодирование

расширенного (24,12,8) кода Голея . . . . . . . .55

2.3.

Двоичные коды Рида-Маллера . . . . . . . . . . . . . . . . . . .57

2.3.1.

Булевы полиномы и РМ коды . . . . . . . . . . . .58

2.3.2.

Конечные геометрии

и мажоритарное декодирование . . . . . . . . . .60

Глава 3

Двоичные циклические коды и коды БЧХ . . . . . . . . . . . . . .67

3.1.

Двоичные циклические коды . . . . . . . . . . . . . . . . . . . .67

3.1.1.

Порождающий и проверочный полиномы . .67

3.1.2.

Порождающий многочлен . . . . . . . . . . . . . . .69

3.1.3.

Кодирование и декодирование

двоичных циклических кодов . . . . . . . . . . . .70

3.1.4.

Проверочный полином . . . . . . . . . . . . . . . . .71

3.1.5.

Укороченные циклические коды

и CRC коды . . . . . . . . . . . . . . . . . . . . . . . . . . .74

3.2.

Общий алгоритм декодирования

циклических кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . .77

3.2.1.

Арифметика GF(q) . . . . . . . . . . . . . . . . . . . . .80

3.3.

Двоичные коды БЧХ . . . . . . . . . . . . . . . . . . . . . . . . . . .86

3.4.

Полиномиальные коды . . . . . . . . . . . . . . . . . . . . . . . . .88

3.5.

Декодирование двоичных БЧХ кодов . . . . . . . . . . . . .90

3.5.1.

Общий метод декодирования

для БЧХ кодов . . . . . . . . . . . . . . . . . . . . . . . . .92

3.5.2.

Алгоритм Берлекемпа-Мэсси (BMA) . . . . . .93

3.5.3.

Декодер PGZ . . . . . . . . . . . . . . . . . . . . . . . . . .98

3.5.4.

Евклидов алгоритм (ЕА) . . . . . . . . . . . . . . .100

3.5.5.

Метод Ченя и исправление ошибок . . . . . .102

3.5.6.

Исправление стираний и ошибок . . . . . . . .103

3.6.

Распределение весов

и границы вероятности ошибки . . . . . . . . . . . . . . . . .105

Предисловие

-Contents.qxd 22/11/2004 12:58 PM Page 4 (Black plate)

3.6.1.

Оценка вероятности ошибки . . . . . . . . . . . .107

Глава 4

Недвоичные БЧХ коды – коды Рида-Соломона . . . . . . . .111

4.1.

Коды РС как полиномиальные коды . . . . . . . . . . . . .111

4.2.

От двоичных кодов БЧХ к РС кодам . . . . . . . . . . . . .112

4.3.

Декодирование кодов РС . . . . . . . . . . . . . . . . . . . . . .113

4.3.1.

Комментарий

к алгоритмам декодирования . . . . . . . . . . . .119

4.3.2.

Исправление ошибок и стираний . . . . . . . .121

4.4.

Распределение весов . . . . . . . . . . . . . . . . . . . . . . . . . .127

Глава 5

Двоичные сверточные коды . . . . . . . . . . . . . . . . . . . . . . . .129

5.1.

Основные структуры . . . . . . . . . . . . . . . . . . . . . . . . . .129

5.1.1.

Рекурсивные систематические

сверточные коды . . . . . . . . . . . . . . . . . . . . . .136

5.1.2.

Свободное расстояние . . . . . . . . . . . . . . . . .138

5.2.

Связь с блоковыми кодами . . . . . . . . . . . . . . . . . . . . .138

5.2.1.

Терминированная конструкция

(нулевой хвост) . . . . . . . . . . . . . . . . . . . . . . .139

5.2.2.

Усеченная конструкция

(direct truncation) . . . . . . . . . . . . . . . . . . . . . .140

5.2.3.

Кольцевая (циклическая или циклически

замкнутая) (tail-biting) конструкция . . . . . .140

5.2.4.

Распределение весов . . . . . . . . . . . . . . . . . . .141

5.3.

Нумераторы весов

и границы вероятности ошибки . . . . . . . . . . . . . . . . .143

5.4.

Декодирование: Алгоритм Витерби

в Хемминговой метрике . . . . . . . . . . . . . . . . . . . . . . .147

5.4.1.

Декодирование по максимуму

правдоподобия и метрики . . . . . . . . . . . . . .148

5.4.2.

Алгоритм Витерби . . . . . . . . . . . . . . . . . . . .149

5.4.3.

Проблемы реализации . . . . . . . . . . . . . . . . .152

5.5.

Перфорированные сверточные коды . . . . . . . . . . . . .162

Предисловие 5

-Contents.qxd 22/11/2004 12:58 PM Page 5 (Black plate)

5.5.1.

Соображения по реализации

перфорированных сверточных кодов . . . . .166

5.5.2.

RCPC коды . . . . . . . . . . . . . . . . . . . . . . . . . .167

Глава 6

Модификация и комбинирование кодов . . . . . . . . . . . . . . .169

6.1.

Модификация кодов . . . . . . . . . . . . . . . . . . . . . . . . . .169

6.1.1.

Укорочение кодов . . . . . . . . . . . . . . . . . . . . .169

6.1.2.

Расширение . . . . . . . . . . . . . . . . . . . . . . . . . .172

6.1.3.

Перфорация (выкалывание) . . . . . . . . . . . .173

6.1.4.

Пополнение и выбрасывание . . . . . . . . . . . .174

6.2.

Комбинирование кодов . . . . . . . . . . . . . . . . . . . . . . . .176

6.2.1.

Последовательное соединение

(time-sharing) кодов . . . . . . . . . . . . . . . . . . .176

6.2.2.

Прямые суммы кодов . . . . . . . . . . . . . . . . . .178

6.2.3.

Произведения кодов . . . . . . . . . . . . . . . . . . .182

6.2.4.

Каскадные коды . . . . . . . . . . . . . . . . . . . . . .191

6.2.5.

Обобщенные каскадные коды . . . . . . . . . . .194

Глава 7

Декодирование с мягким решением . . . . . . . . . . . . . . . . . .201

7.1.

Передача двоичных сигналов по каналам с АБГШ .203

7.2.

Алгоритм Витерби с Евклидовой метрикой . . . . . . .204

7.3.

Декодирование двоичных линейных

блоковых кодов с помощью решетки . . . . . . . . . . . . .209

7.4.

Алгоритм Чейза . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210

7.5.

Декодирование по упорядоченным статистикам . . .213

7.6.

Декодирование по минимуму

обобщенного расстояния . . . . . . . . . . . . . . . . . . . . . .216

7.6.1

Оптимизированные

условия достаточности . . . . . . . . . . . . . . . . .218

7.7.

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

7.8.

Алгоритмы декодирования

с мягким выходом (soft-output) . . . . . . . . . . . . . . . . . .219

7.8.1.

Алгоритм Витерби с мягким выходом . . . . .220

Предисловие

-Contents.qxd 22/11/2004 12:58 PM Page 6 (Black plate)

7.8.2.

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

апостериорной вероятности (MAP) . . . . . . .224

7.8.3.

Log-MAP алгоритм . . . . . . . . . . . . . . . . . . . .227

7.8.4.

Max-Log-MAP алгоритм . . . . . . . . . . . . . . . .228

7.8.5.

OSD алгоритм с мягким выходом . . . . . . . .229

Глава 8

Итеративно декодируемые коды . . . . . . . . . . . . . . . . . . . .231

8.1.

Итеративное декодирование . . . . . . . . . . . . . . . . . . . .234

8.2.

Составные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .237

8.2.1.

Параллельная схема: турбо коды . . . . . . . . .237

8.2.2.

Последовательная схема . . . . . . . . . . . . . . . .246

8.2.3.

Произведение блоковых кодов . . . . . . . . . .250

8.3.

Коды с низкой плотностью проверок на четность . .255

8.3.1.

Графы Таннера . . . . . . . . . . . . . . . . . . . . . . .256

8.3.2.

Итеративное декодирование

с жестким решением:

алгоритм с перевертыванием бита . . . . . . . .258

8.3.3.

Итеративное вероятностное

декодирование: распространение доверия .262

Глава 9

Комбинирование кодов и цифровой модуляции . . . . . . . . .269

9.1.

Мотивация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .269

9.1.1.

Примеры сигнальных множеств . . . . . . . . .271

9.1.2.

Кодовая модуляция . . . . . . . . . . . . . . . . . . .274

9.1.3.

Расстояние . . . . . . . . . . . . . . . . . . . . . . . . . .275

9.2.

Решетчатая кодовая модуляция (TCM) . . . . . . . . . . .277

9.2.1.

Разбиение множества точек

и отображение на решетку . . . . . . . . . . . . . .277

9.2.2.

Декодирование по максимуму

правдоподобия . . . . . . . . . . . . . . . . . . . . . . .281

9.2.3.

Расстояние и вероятность ошибки . . . . . . .281

9.2.4.

Практические конструкции ТСМ

и двухэтапное декодирование . . . . . . . . . . .283

9.3.

Многоуровневая кодовая модуляция (МСМ) . . . . . .288

Предисловие 7

-Contents.qxd 22/11/2004 12:58 PM Page 7 (Black plate)

9.3.1.

Конструкции и многоуровневое

декодирование . . . . . . . . . . . . . . . . . . . . . . .289

9.3.2.

Неравная защита в системах

многоуровневой кодовой модуляции . . . . .294

9.4.

Кодовая модуляция с побитовым

перемешиванием (BICM) . . . . . . . . . . . . . . . . . . . . . .300

9.4.1.

Отображение Грея . . . . . . . . . . . . . . . . . . . . .301

9.4.2.

Генерация метрик: обратное отображение .302

9.4.3.

Перемешивание . . . . . . . . . . . . . . . . . . . . . .303

9.5.

Турбо кодовая модуляция на решетке (TTCM) . . . . .303

9.5.1.

Практическая турбо ТСМ . . . . . . . . . . . . . . .303

9.5.2.

Турбо ТСМ с посимвольным

перемешиванием . . . . . . . . . . . . . . . . . . . . . .304

9.5.3.

Турбо ТСМ с побитовым

перемешиванием . . . . . . . . . . . . . . . . . . . . . .305

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .307

Приложение A

Распределение весов расширенных кодов БЧХ . . . . . . . . .316

ПРЕДИСЛОВИЕ АВТОРА
Эта книга появилась в результате общения с коллегами из ака-
демии и промышленности по всему миру, присылавших сотни
электронных писем с вопросами по теории и применению ко-
дов, исправляющих ошибки (ЕСС). Больше всего вопросов
поступало от инженеров и научных работников по компьютер-
ным системам, которым необходимо было выбрать, реализо-
вать или промоделировать конкретные схемы кодирования.
Все вопросы высвечивались на ЕСС интернет-странице, кото-
рая предварительно была создана в лаборатории проф. Имаи
в Институте технических исследований Университета Токио
в начале 1995. Читатель сразу заметит отсутствие в тексте тео-
рем и доказательств. Мой подход состоит в том, чтобы обучать
основам на простых примерах. Ссылки на теоретические рабо-
ты делаются по мере надобности. Эта книга создавалась как
справочное пособие для аспирантов и специалистов, интере-
сующихся изучением основных методов и применением ЕСС.
Компьютерные программы, реализующие основные алгорит-
мы кодирования и декодирования практических схем кодиро-
вания, доступны на интернет-сайте
http://the-art-of-ecc.com
Повсюду в тексте этот сайт упоминается как ЕСС интер-
нет-сайт. Эта книга уникальна тем, что основные идеи помехо-
устойчивого кодирования вводятся с помощью простых иллю-
стративных примеров. Компьютерные программы, написан-
ные на языке программирования С и доступные на ЕСС ин-
тернет-сайте, позволяют продемонстрировать реализацию
и применение в системах кодовой модуляции основных алго-
ритмов кодирования и декодирования важнейших кодовых
схем, таких как сверточные коды, коды Хемминга и БЧХ, ко-
ды Рида-Соломона и турбо коды. Материал книги сосредото-
чен на основных алгоритмах для анализа и реализации кодов,
00-Preface01.qxd 22/11/2004 12:59 PM Page 9 (Black plate)
исправляющих ошибки (ЕСС). Существует обширная теория
помехоустойчивого кодирования, прикосновение к которой
осуществляется через ссылки к соответствующему материалу.
Известно много хороших книг, посвященных теории кодиро-
вания, как например [LC], [MS], [PW], [Blah], [Bos], [Wic]. Чи-
татели могут пролистать их прежде чем обратиться к материа-
лам этой книги. В каждой ее главе рассматриваются базовые
идеи какой-либо из схем кодирования или декодирования на
простых и легко проверяемых численных примерах, вместо
погружения в детали теории, лежащей в основании этих идей.
Повсюду в книге даются основные инструменты, необходимые
для оценки вероятности ошибки (эффективности) конкрет-
ным схем кодирования для некоторых основных моделей ка-
налов передачи сигналов. Поддержка материала этой книги
программами на ЕСС интернет-сайте делает ее уникальной.
Книга посвящена искусству помехоустойчивого кодирова-
ния в том смысле, что она ориентирована на проблемы выбо-
ра, реализации и моделирования алгоритмов кодирования
и декодирования кодов, исправляющих ошибки. Книге орга-
низована следующим образом. В первой главе дается введение
в базовые концепции исправления ошибок и технику кодиро-
вания и декодирования. В главе 2 рассматриваются важные и,
вместе с тем, простые для понимания классы кодов, такие как
коды Хемминга, Голея и Рида-Маллера. В главе 3 изучаются
циклические коды и важное семейство кодов Боуза-Чоудхури-
Хоквингема (БЧХ). Здесь дается введение в арифметику ко-
нечных полей и классические алгоритмы декодирования, та-
кие как алгоритмы Берлекэмпа-Мэсси, Евклида и Питерсона-
Горенстейна-Цирлера (PGZ), с простыми для понимания
и проверки примерами. Глава 4 посвящена кодам Рида-Соло-
мона и исправлению ошибок и стираний. Дается подробное
исследование возможных алгоритмов вместе с примерами их
работы. В главе 5 вводятся двоичные сверточные коды. Мате-
риал этой главы концентрируется на понимании основной
структуры этих кодов вместе с объяснением алгоритма Витер-
10 Предисловие
00-Preface01.qxd 22/11/2004 12:59 PM Page 10 (Black plate)
би в Хемминговой метрике. Вводятся и обсуждаются важней-
шие проблемы реализации. В главе 6 даются некоторые спосо-
бы модифицирования отдельного кода и комбинирования не-
скольких кодов вместе с простыми примерами. Глава 7 посвя-
щена алгоритмам мягкого декодирования. Некоторые из них,
как например, мягкое декодирование по упорядоченным ста-
тистикам, еще не нашли должного отражения в литературе.
В главе 8 представлена уникальная трактовка турбо кодов (па-
раллельного и последовательного типа) и блоковых кодов-
произведений с точки зрения теории кодирования. В этой же
главе исследуются коды с малой плотностью проверок на чет-
ность. Для всех этих классов кодов описываются основные ал-
горитмы декодирования с простыми примерами. Наконец,
глава 9 посвящена весьма эффективной технике комбинирова-
ния кодов, исправляющих ошибки, с цифровой модуляцией.
Рассматриваются остроумные алгоритмы их декодирования.
Книга включает всеобъемлющую библиографию для читате-
лей, которые хотят знать больше о красивой теории. Я наде-
юсь, что эта книга станет ценным и необходимым инструмен-
том как для студентов, так и для практиков, интересующихся
этой интересной, увлекательной и никогда не кончающейся
областью теории информации.
Я хотел бы выразить благодарность всем, кто повлиял на
работу с этой книгой. Профессору Франциско Гарсиа Угалде,
Национальный Университет Мехико, который ввел меня в ув-
лекательный мир кодов, исправляющих ошибки. Часть этой
книги основана на моей бакалаврской диссертации. Профес-
сору Эдварду Бертраму, Университет Гаваи, за обучение меня
основам абстрактной алгебры. Профессору Давиду Муньозу,
Технологический институт высшей школы Монтерей, Мекси-
ка, за его доброту и поддержку. Профессорам Тадео Касами,
Университет г. Хиросима, Тору Фудживара, Университет
г. Осака, и Хидеки Имаи, Университет г. Токио, за поддержку
моего пребывание в Японии в качестве приглашенного науч-
ного сотрудника-исследователя. Дану Лати и Эдвайту Могре,
Предисловие 11
00-Preface01.qxd 22/11/2004 12:59 PM Page 11 (Black plate)
корпорация больших интегральных схем, за бесконечные об-
суждения проблем моделирования и возможность приобрести
опыт реализации идей в интегральных схемах. Профессору
Марку Фоссоуриеру, Гавайский Университет, за помощь. Мое-
му коллеге доктору Мише Михалевичу, Лаборатория компью-
терных систем, корпорация Сони, за объяснение связи между
декодированием и криптоанализом. Я хотел бы также выра-
зить искреннюю благодарность доктору Марио Токоро, Пре-
зиденту лаборатории компьютерных систем корпорации Со-
ни, и профессору Райю Коно, Национальный университет Йо-
кагамы, за предоставленную мне возможность использования
превосходного оборудования для написания этой книги. В ча-
стности, я хочу выразить бесконечную благодарность профес-
сору Шу Лин, который находится теперь в Калифорнийском
университете в Дависе, который поддерживал меня, пока я
был аспирантом на Гаваях, и убедил меня продолжить исследо-
вания по этой увлекательной теме. Наконец, но ничуть не ме-
нее, я хочу поблагодарить студентов и коллег, которые все эти
годы слушали лекции в Мексике, Японии и США.
Я посвящаю эту книгу памяти Ричарда Хемминга, Клода
Шеннона и Густава Соломона, трем выдающимся ученым, ко-
торые оказали огромное влияние на жизнь и работу современ-
ного поколения людей.
Роберт Морелос-Сарагоса
Токио, Япония, Апрель 2002.
Глава 1
ВВЕДЕНИЕ
История кодов, исправляющих ошибки, началась с изобрете-
ния кодов Хемминга [Ham] почти одновременно с появлением
основополагающей работы Шеннона [Sha]. Чуть позже были
предложены коды Голея [Gol]. Эти классы кодов являются оп-
тимальными. Понятие оптимальности кода мы рассмотрим
в последующих разделах.
На Рисунке 1 показана блок-схема канонической цифро-
вой системы передачи или хранения информации. Это знаме-
нитый Рисунок 1, с которого начинаются почти все книги по
теории помехоустойчивого кодирования (в дальнейшем будет
использоваться авторское сокращение ЕСС со значением –
помехоустойчивое кодирование, или кодирование с исправлением
ошибок, или коды, исправляющие ошибки). Источник и получа-
тель информации обычно включают какое-либо кодирование
(преобразование) источника, соответствующее природе ин-
формации. Кодирующее устройство (кодер канала) системы
помехоустойчивого кодирования получает информационные
символы от источника и добавляет к ним избыточные симво-
лы таким образом, чтобы могла быть исправлена большая
часть ошибок, возникающих в процессе модуляции сигналов,
их передачи по каналу с шумом и демодуляции.
Рис. 1. Каноническая цифровая система связи.
Источник
информации
Кодер Модуляция
Канал
с шумом
Декодер Демодуляция
Получатель
информации
Кодовая
модуляция
01-Glava01.qxd 22/11/2004 1:12 PM Page 15 (Black plate)
Обычно предполагается, что в канале связи отсчеты адди-
тивного шумового процесса прибавляются к модулированным
символам (рассматривается узкополосное комплексное пред-
ставление сигналов). Отсчеты шума предполагаются независи-
мыми от источника символов. Эту модель сравнительно легко
исследовать. Она легко позволяет включить каналы с гауссовым
шумом (АБГШ), каналы с общими Релеевскими замираниями,
а также двоичный симметричный канал (ДСК). На приемной
стороне декодирующее устройство (декодер канала) использует
избыточные символы для исправления ошибок, внесенных ка-
налом связи. В режиме обнаружения ошибок декодер ведет себя
как кодер полученного из канала сообщения и проверяет совпа-
дение вычисленных избыточных символов с принятыми.
В классической теории кодов, исправляющих ошибки,
комплекс, включающий модулятор, демодулятор и шумовую
среду распространения сигналов, называется дискретным ка-
налом без памяти с входом v и выходом r. Примером такого ка-
нала является система передачи двоичных сигналов по каналу
с АБГШ (аддитивным белым гауссовым шумом), который мо-
делируется как двоичный симметричный канал с вероятностью
ошибки (или вероятностью перехода) p, равной вероятности
ошибки на бит для двоичного сигнала в АБГШ,
(1.1)
где
(1.2)
является гауссовой Q-функцией
1
и Eb / N0 есть отношение сиг-
нал-шум (SNR) на бит. Этот случай будет исследован ниже
в этой главе.
16 Глава. 1. Введение
1 Заметим, что в стандартном определении функции ошибок
01-Glava01.qxd 22/11/2004 1:12 PM Page 16 (Black plate)
В 1974 Мэсси [Mas3] предложил рассматривать помехоус-
тойчивое кодирование (ЕСС) и модуляцию как единое целое,
известное в современной литературе как кодовая модуляция
(coded modulation) (Часто используется и несколько более точ-
ный термин – сигнально кодовая конструкция). Совместное
конструирование кода и множества сигнальных точек обеспе-
чивает более высокую эффективность и больший (энергетиче-
ский) выигрыш от кодирования (coding gain)2, чем последова-
тельное применение ЕСС и модуляции. В этой книге рассмот-
рены некоторые методы комбинирования кодирования
и модуляции, включая: решетчатую кодовую модуляцию
(ТСМ – trellis-coded modulation) [Ung1] и многоуровневую кодо-
вую модуляцию (МСМ – multilevel coded modulation) [IH]. В сис-
темах кодовой модуляции «мягкое решение» (soft decision) на
выходе канала вводится непосредственно в декодер и обраба-
тывается им. Напротив, в классической системе с помехоус-
тойчивым кодированием в декодер вводится «жесткое реше-
ние» (hard decision) демодулятора.
Коды, исправляющие ошибки, можно комбинировать раз-
личными способами. Примером последовательного каскадиро-
вания (serial concatenation, т.е. каскадная конструкция в класси-
ческом смысле) является следующая конструкция. Многие го-
ды наиболее популярной каскадной схемой ЕСС была
комбинация внешнего кода Рида-Соломона (РС), промежу-
точного перемежения (или перемешивания – interleaving)
и внутреннего сверточного кода. Эта конструкция была ис-
пользована во многих приложениях от систем космической
связи до цифровых широковещательных систем телевидения
высокой четкости. Основная идея состоит в том, что пакеты
ошибок, которые появляются на выходе декодера сверточного
кода с мягким решением, могут быть разбиты на мелкие части
с помощью интерливинга и затем полностью исправлены де-
Введение 17
2 Выигрыш от кодирования определен как разность между отношениями сиг-
нал-шум системы с кодированием и системы без кодирования при одинако-
вой скорости (и одинаковой вероятности ошибки).
01-Glava01.qxd 22/11/2004 1:12 PM Page 17 (Black plate)
кодером кода РС. Коды Рида-Соломона являются недвоичны-
ми кодами, каждый символ которых состоит из нескольких
двоичных бит. Эти коды способны исправлять многократные
пакеты ошибок. Преимуществом каскадной конструкции яв-
ляется то, что для нее требуются раздельные декодеры внут-
реннего и внешнего кодов вместо одного, но очень сложного
декодера для каскадного кода в целом.
В книге изучаются разные типы систем с ЕСС. Сначала
рассматриваются базовые кодовые конструкции и алгоритмы
их декодирования в Хемминговом пространстве (т.е. работаю-
щие с битами). Затем, во второй части книги, вводятся алгорит-
мы декодирования с мягким решением для передачи двоичных
сигналов, работающие в Евклидовом пространстве. В системах
этого типа необходимая мощность передаваемых сигналов сни-
жается на 2 дБ/бит по сравнению с декодерами в Хемминговом
пространстве (с жестким решением). Рассматриваются декоде-
ры с мягким решением нескольких типов. При этом основное
внимание уделяется собственно алгоритмам (тому, как они ра-
ботают), а не теоретическим вопросам (почему они работают).
Наконец, последняя часть книги посвящена комбинированию
кодов и перемежителей в конструкциях с итеративным декоди-
рованием, а также комбинированию помехоустойчивого коди-
рования и дискретной модуляции.
1.1. Кодирование для исправления
ошибок: Основные положения
Все коды, исправляющие ошибки, основаны на одной общей
идее: для исправления ошибок, которые могут возникнуть
в процессе передачи или хранения информации, к ней добав-
ляется некоторая избыточность. По основной схеме (исполь-
зуемой на практике), избыточные символы дописываются
вслед за информационными, образуя кодовую последователь-
ность или кодовое слово (codeword). В качестве иллюстрации на
Рисунке 2 показано кодовое слово, сформированное процеду-
18 Глава. 1. Введение
01-Glava01.qxd 22/11/2004 1:12 PM Page 18 (Black plate)
рой кодирования блокового кода (block code). Такое кодирова-
ние называют систематическим (systematic). Это означает, что
информационные символы всегда появляются на первых k по-
зициях кодового слова. Символы на оставшихся n-k позициях
являются различными функциями от информационных сим-
волов, обеспечивая тем самым избыточность, необходимую
для обнаружения или исправления ошибок. Множество всех
кодовых последовательностей называют кодом, исправляющим
ошибки (error correcting code), и обозначают через С.
1.1.1. Блоковые и сверточные коды
В соответствии с тем, как вводится избыточность в сообщение,
коды, исправляющие ошибки, могут быть разделены на два
класса: блоковые и сверточные (convolutional code) коды. Обе
схемы кодирования нашли практическое применение. Исто-
рически сверточные коды имели преимущество главным обра-
зом потому, что для них известен алгоритм декодирования Ви-
терби с мягким решением и в течение многих лет существова-
ла убежденность в том, что блоковые коды невозможно
декодировать с мягким решением. Однако последние достиже-
ния в теории и конструировании алгоритмов декодирования
с мягким решением для линейных блоковых кодов помогли
рассеять это убеждение. Более того, наилучшие ЕСС, извест-
ные сегодня (в начале двадцать первого века), являются блоко-
выми кодами (нерегулярными кодами с низкой плотностью про-
верок – irregular low-density parity-check codes).
При блоковом кодировании каждый блок информацион-
ных символов обрабатывается независимо от других. Другими
1.1. Кодирование для исправления ошибок 19
Рис. 2. Систематическое блоковое кодирование для исправления
ошибок.
n символов
k символов n-k символов
информация избыточность
01-Glava01.qxd 22/11/2004 1:12 PM Page 19 (Black plate)
словами, блоковое кодирование является операцией без памя-
ти в том смысле, что кодовые слова не зависят друг от друга.
Выход сверточного кодера, напротив, зависит не только от ин-
формационных символов в данный момент, но и от предыду-
щих символов на его входе или выходе. Чтобы упростить объ-
яснения, мы начнем с изучения структурных свойств блоковых
кодов. Многие из этих свойств являются общими для обоих
типов кодов.
Следует заметить, что на самом деле блоковые коды обла-
дают памятью, если рассматривать кодирование как побито-
вый процесс в пределах кодового слова. Сегодня это различие
между блоковыми и сверточными кодами кажется все менее
и менее ясным, особенно после недавних достижений в пони-
мании решетчатой (trellis) структуры блоковых кодов и кольце-
вой (tail-biting) структуры некоторых сверточных кодов.
Дополнение переводчика. Название кольцевые сверточные ко-
ды еще не окончательно утвердилось в отечественной литерату-
ре, иногда tail-biting convolutional codes называют циклически за-
мкнутыми.
Специалисты по сверточным кодам иногда рассматривают
блоковые коды как «коды с меняющейся во времени структу-
рой решетки» (time-varying trellis structure). Аналогично, специ-
алисты в области блоковых кодов могут рассматривать свер-
точные коды как «коды с регулярной структурой решетки».
1.1.2. Хеммингово расстояние, Хемминговы сферы
и корректирующая способность
Рассмотрим двоичный код С, исправляющий ошибки. Если не
все из 2n возможных двоичных векторов длины n будут переда-
ваться по каналу связи, то этот код может обладать свойством
помехоустойчивости. В действительности, код С является под-
множеством n-мерного двоичного векторного пространства
V2 = {0, 1}n таким, что элементы этого подмножества макси-
мально удалены друг от друга.
20 Глава. 1. Введение
01-Glava01.qxd 22/11/2004 1:12 PM Page 20 (Black plate)
В двоичном пространстве V2 расстояние определяется как
число позиций, на которых два вектора не совпадают. Пусть
x1=(x1,0, x1,1,…, x1,n–1) и x2=(x2,0, x2,1,…, x2,n–1) два вектора в V2.
Тогда Хеммингово расстояние между векторами x1 и x2, обозна-
чаемое как dH(x1, x2), равно
(1.3)
где через |A| обозначено число элементов в множестве A.
Для заданного кода С минимальное Хеммингово расстояние,
dmin, определяется как минимум Хеммингова расстояния по
всем возможным парам различных кодовых слов,
(1.4)
Повсюду в книге обозначение (n, k, dmin) используется для па-
раметров блокового кода длины n, который используется для
кодирования сообщений длины k, и имеет минимальное Хем-
мингово расстояние dmin. Предполагается, что число кодовых
слов этого кода равно |C|=2k.
Пример 1. Простейшим примером является код-повторе-
ние длины 3. Каждый информационный бит повторяется три
раза. Таким образом, сообщение «0» кодируется вектором
(000), а сообщение «1», вектором (111). Так как два вектора
различаются в трех позициях, Хеммингово расстояние между
ними равно 3. На Рисунке 3 показано графическое представле-
ние этого кода. Трехмерное двоичное векторное пространство
соответствует 2
3
= 8 вершинам трехмерного единичного куба.
Хеммингово расстояние между кодовыми словами (000)
и (111) равно числу вершин, через которые проходит соединя-
ющий их путь. Это эквивалентно числу координат, которые
необходимо изменить, чтобы преобразовать (000) в (111) и на-
оборот. Таким образом, dH = ((000),(111)) = 3. Так как в этом
коде только два кодовых слова, то dmin = 3.
Двоичное векторное пространство V2 обычно называют
Хемминговым пространством. Пусть v кодовое слово кода C. Хем-
минговой сферой St(v) радиуса t с центром в точке v является
1.1. Кодирование для исправления ошибок 21
01-Glava01.qxd 22/11/2004 1:12 PM Page 21 (Black plate)
множество векторов (точек) в V2 на расстоянии меньше или рав-
ном t от центра v,
(1.5)
Заметим, что число слов (число векторов) в St(v) равно
(1.6)
Пример 2. На Рисунке 4 показаны Хемминговы сферы ра-
диуса t = 1, окружающие кодовые слова (3,1,3) двоичного кода-
повторения.
Заметим, что Хемминговы сферы для этого кода не пересе-
каются, т.е. в пространстве V2 нет векторов (или вершин в еди-
ничном трехмерном кубе), принадлежащих одновременно
и S1(000), и S1(111). В результате, если изменить любую одну
позицию кодового слова v, то получится вектор, который, тем
22 Глава. 1. Введение
Рис. 4. Хемминговы сферы радиуса t = 1, окружающие кодовые слова
(3,1,3) двоичного кода-повторения.
Рис. 3. (3,1,3) код-повторение в трехмерном векторном пространстве.
01-Glava01.qxd 22/11/2004 1:12 PM Page 22 (Black plate)
не менее, останется внутри Хемминговой сферы с центром в v.
Эта идея является принципиальной для понимания и опреде-
ления корректирующей способности кода C.
Корректирующей способностью (error correcting capability) t
кода С называют наибольший радиус Хемминговой сферы St(v)
для всех кодовых слов v ⊆ С такой, что для любых различных
пар vi , vj ⊆ С соответствующие им Хемминговы сферы не пере-
секаются, т.е.
(1.7)
Это соответствует более распространенному определению
(1.8)
где ⎣x⎦ обозначена целая часть x, т.е. целое число меньше или
равное x.
Заметим, что для определения минимального кодового
расстояния произвольного блокового кода С в соответствии
с (1.4), необходимо вычислить все 2k(2k – 1) расстояний между
различными парами кодовых слов. Это практически невоз-
можно даже для сравнительно коротких кодов, например,
с k = 50. Одним из важных преимуществ линейных блоковых
кодов является то, что для вычисления dmin достаточно знать
только Хемминговы веса 2k – 1 ненулевых кодовых слов.
1.2. Линейные блоковые коды
Как уже упоминалось выше, построение хорошего кода озна-
чает поиск в V2 подмножества элементов в наибольшей степе-
ни удаленных друг от друга. Это очень трудная задача. Более
того, если даже это сделано, то остается неясным как назна-
чить кодовые слова информационным сообщениям.
Линейный код (т.е. множество кодовых слов) является век-
торным подпространством в пространстве V2. Это означает, что
1.2. Линейные блоковые коды 23
01-Glava01.qxd 22/11/2004 1:12 PM Page 23 (Black plate)
операция кодирования может быть представлена умножением
на матрицу. В терминах цифровой электроники простое коди-
рующее устройство может быть построено на элементах
«исключающее ИЛИ», «И» и триггерах типа D. В этой главе
операциями сложения и умножения в двоичном векторном
пространстве являются «исключающее ИЛИ» (сложение по
модулю 2) и «И», соответственно. Таблицы сложения и умно-
жения двоичных элементов имеют следующий вид:
a b a+b ab
0 0 0 0
0 1 1 0
1 0 1 0
1 1 1 1
1.2.1. Порождающая и проверочная матрицы
Пусть С двоичный линейный (n, k, dmin) код. Так как С есть
k-мерное подпространство, то оно имеет базис, например, (v0,
v1,…, vk–1) такой, что любое кодовое слово v ∈ C может быть за-
писано как линейная комбинация элементов этого базиса:
(1.9)
где ui ∈ {0, 1}, 0 ≤ i < k. Уравнение (1.9) может быть записано
в матричной форме через порождающую матрицу G и вектор-
сообщение u = (u0, u1,…, uk–1):
(1.10)
где
(1.11)
24 Глава. 1. Введение
01-Glava01.qxd 22/11/2004 1:12 PM Page 24 (Black plate)
Так как C является k-мерным векторным пространством в V2,
то существует (n-k)-мерное дуальное пространство (dual space)
С⊥, которое порождается строками матрицы H, называемой
проверочной матрицей (parity-check matrix), такой, что GH =0,
где через H обозначена транспонированная матрица H. Заме-
тим, в частности, что любое кодовое слово v∈C удовлетворяет
условию
(1.12)
Как будет показано в разделе 1.3.2 уравнение (1.12) является
фундаментальным для декодирования линейных кодов.
Линейный код С⊥, который генерируется матрицей H, яв-
ляется двоичным линейным (n, n – k, d⊥
min) кодом, который
называют обычно дуальным коду С.
1.2.2. Вес как расстояние
Как упоминалось в разделе 1.1.2, линейные коды отличаются
тем, что для определения минимального расстояния кода доста-
точно знать минимум Хеммингова веса ненулевых кодовых слов.
Ниже этот факт будет доказан. Определим вес Хемминга wtH(x)
вектора, x ∈ V2, как число ненулевых элементов в x. Из опреде-
ления Хеммингова расстояния ясно, что wtH(x) = dH(x, 0).
Для двоичного линейного кода С получаем
(1.13)
Наконец, из свойства линейности кода имеем v1+ v2∈C. Отсю-
да следует, что минимальное расстояние кода C равно и может
быть вычислено как минимальный вес по всем 2k – 1 ненуле-
вым кодовым словам. Эта задача существенно проще, чем пол-
ный перебор по всем парам кодовых слов, хотя и остается
очень сложной даже для кодов среднего размера (или размер-
ности k).
1.2. Линейные блоковые коды 25
01-Glava01.qxd 22/11/2004 1:12 PM Page 25 (Black plate)
1.3. Кодирование и декодирование
линейных блоковых кодов
1.3.1. Кодирование с помощью матриц G и H
Равенство (1.10) определяет по существу правило кодирования
для линейного блокового кода, которое может быть использо-
вано непосредственно. Если кодирование должно быть систе-
матическим, то произвольная порождающая матрица G линей-
ного блокового (n, k, dmin) кода C может быть преобразована
к систематической форме Gsys (иначе, к канонической форме)
с помощью элементарных операций и перестановок столбцов
матрицы. Матрица Gsys состоит из двух подматриц: k × k еди-
ничной матрицы, обозначаемой Ik, и k × (n – k) проверочной
подматрицы P. Таким образом,
(1.14)
где
(1.15)
Так как GH = 0, то отсюда следует, что систематическая фор-
ма проверочной матрицы имеет вид
(1.16)
Пример 3. Рассмотрим двоичный линейный (4,2,2) код
с порождающей матрицей
Перестановкой второго и четвертого столбцов преобразуем эту
матрицу в систематическую форму
26 Глава. 1. Введение
01-Glava01.qxd 22/11/2004 1:12 PM Page 26 (Black plate)
Таким образом, проверочная подматрица равна
Интересно отметить, что в данном случае выполняется со-
отношение3 P = P . Из (1.16) следует, что систематическая
форма проверочной матрицы имеет вид
В дальнейшем будет использовано обозначение u = (u0, u1,…,
uk–1) для информационного сообщения и обозначение v = (v0,
v1,…, vn–1) для соответствующего кодового слова кода С.
Если параметры С таковы, что k<(n – k) или, эквивалент-
но, скорость кода k/n < 1/2, то кодирование с помощью порож-
дающей матрицы более экономно по числу логических опера-
ций. В этом случае
(1.17)
где vp = uP = (vk, vk+1,…, vn–1) представляет проверочную часть
кодового слова.
Однако, если k > (n – k) или k/n > 1/2, тогда кодирование
с помощью проверочной матрицы H требует меньшего коли-
чества вычислений. Этот вариант кодирования основан на
уравнении (1.12) (u, vp)H = 0. Проверочные позиции (vk,
vk+1,…, vn – 1) вычисляются следующим образом:
(1.18)
Можно сказать, что элементами систематической формы про-
верочной матрицы являются коэффициенты проверочных
уравнений, из которых вычисляются проверочные символы.
1.3. Кодирование и декодирование линейных блоковых кодов 27
3 В этом случае код называют самодуальным. См. Раздел 2.2.3 .
01-Glava01.qxd 22/11/2004 1:12 PM Page 27 (Black plate)
Этот факт будет использован в Разделе 8.3 при обсуждении ко-
дов с низкой плотностью проверок.
Пример 4. Рассмотрим двоичный линейный (4,2,2) код из
примера 3. Пусть сообщение и кодовые слова обозначены u =
= (u0, u1) и v = (v0, v1, v2, v3), соответственно. Из уравнения
(1.18) получаем
Соответствие между 22 = 4 двух битными сообщениями
и кодовыми словами имеет следующий вид:
(1.19)
1.3.2. Декодирование по стандартной таблице
В этом разделе представлена процедура декодирования, кото-
рая находит кодовое слово v, ближайшее к принятому с иска-
жениями слову r = v + e, где вектор ошибок e ∈ {0, 1}n создан
двоичным симметричным каналом (ДСК) в процессе передачи
кодового слова. Модель ДСК показана на Рисунке 5. По пред-
положению переходная вероятность p (или параметр ДСК)
меньше 1/2.
Стандартной таблицей (или стандартной расстановкой)
[Sle] для двоичного линейного (n, k, dmin) кода С называется
таблица всех возможных принятых из канала векторов r, орга-
28 Глава. 1. Введение
Рис. 5. Модель двоичного симметричного канала.
передано принято
01-Glava01.qxd 22/11/2004 1:12 PM Page 28 (Black plate)
низованная таким образом, что может быть найдено ближай-
шее к r кодовое слово v.
Таблица 1. Стандартная таблица двоичного линейного блоко-
вого кода.
s u0 = 0 u1 … u2k–1
0 v0 v1 … v2k–1
s1 e1 e1 + v1 … e1 + v2k–1
s2 e2 e2 + v1 … e2 + v2k–1
...
s2n–k–1 e2n–k–1 e2n–k–1 + u2k–1 … e2n–k–1 + v2k–1
Стандартная таблица содержит 2n – k строк и 2k + 1 столбцов.
Правые 2k столбцов таблицы содержат все вектора из прост-
ранства V2 = {0, 1}n.
Для описания процедуры декодирования необходимо вве-
сти понятие синдрома. Определение синдрома произвольного
слова из V2 следует из уравнения (1.12),
(1.20)
где H проверочная матрица кода C. Покажем, что синдром яв-
ляется индикатором вектора ошибок. Предположим, что кодо-
вое слово v ∈ C, переданное по ДСК, принято как r = v + e.
Синдром принятого слова равен
(1.21)
Таким образом, вычисление синдрома можно рассматривать
как линейное преобразование вектора ошибок.
Процедура построения стандартной таблицы
1. Правые столбцы первой строки заполним кодовыми слова-
ми кода С, начиная с нулевого кодового слова. В первую
ячейку первого столбца запишем нулевой синдром. Поло-
жим j = 0.
2. Для j = j + 1, найдем слово ej ∈ V2 минимального веса
Хемминга, не являющееся кодовым и не включенное
в предыдущие строки таблицы. Соответствующий синдром
1.3. Кодирование и декодирование линейных блоковых кодов 29
01-Glava01.qxd 22/11/2004 1:12 PM Page 29 (Black plate)
sj = ejHT запишем в первый (крайний левый) столбец j-ой
строки. В оставшиеся 2k ячеек этой строки запишем сум-
мы ej и содержимого первой строки (т.е. кодового слова).
3. Повторяем шаг 2 процедуры, пока все вектора из V2 не ока-
жутся включенными в таблицу. Эквивалентно, повторяем
шаг 2 пока j < 2n – k, иначе Стоп.
Пример 5. Стандартная таблица двоичного линейного
(4,2,2) кода:
s 00 01 10 11
00 0000 0110 1011 1101
11 1000 1110 0011 0101
10 0100 0010 1111 1001
01 0001 0111 1010 1100
Декодирование с помощью стандартной таблицы выпол-
няется следующим образом. Пусть r = v +e принятое слово.
Найдем это слово в таблице и возьмем в качестве результата де-
кодирования сообщение u, записанное в верхней (первой)
ячейке того столбца, в котором лежит принятое слово r.
По идее, этот процесс требует хранения в памяти всей таблицы
и поиска в ней заданного слова.
Однако, возможно некоторое упрощение процедуры де-
кодирования, если заметить, что все элементы одной и той
же строки имеют один и тот же синдром. Каждая строка
Rowi, 0 ≤ i < 2n – k, этой таблицы представляет смежный класс
кода С, а именно, Rowi = {ei + v|v ∈ C}. Вектор ei называется ли-
дером смежного класса.
Синдром всех элементов i-ой строки равен
(1.22)
и не зависит от конкретного значения кодового слова v ∈ C.
Упрощенная процедура декодирования состоит в следующем:
вычислить синдром принятого слова r = ej + v
и найти его в левом столбце стандартной таблице;
30 Глава. 1. Введение
01-Glava01.qxd 22/11/2004 1:12 PM Page 30 (Black plate)
взять лидер смежного класса ej′ из второго столбца той же стро-
ки и прибавить его к принятому слову, получив ближайшее
к принятому r = ej′ + v′ кодовое слово v′.
Таким образом, вместо таблицы n × 2n бит для декодирова-
ния достаточно использовать таблицу лидеров смежных клас-
сов n × 2n – k бит.
Пример 6. Снова рассмотрим двоичный линейный (4, 2, 2)
код из Примера 3. Положим, что передано было кодовое слово
(0110) , а принято слово (0010). Тогда синдром равен
Находим в стандартной таблице лидер смежного класса
(0100) и получаем декодированное кодовое слово
(0010)+(0100)=(0110). Одиночная ошибка в слове исправлена!
Это может показаться странным, так как минимальное кодо-
вое расстояние равно 2 и, согласно условию (1.8), исправление
однократных ошибок невозможно. Однако объяснение этому
может быть найдено в стандартной таблице (Пример 5). Заме-
тим, что третья строка таблицы содержит два различных дво-
ичных вектора веса 1. Это означает, что только три из возмож-
ных четырех одиночных ошибок могут быть исправлены.
В Примере 6 дана одна из исправляемых ошибок.
Оказывается, что данный (4, 2, 2) код является простей-
шим примером линейного кода с неравной защитой от ошибок
(linear unequal error protection – LUEP код) [Wv, Van]. Данному
LUEP коду соответствует разделяющий вектор (3,2), который
показывает, что минимальное кодовое расстояние равно трем,
если различаются первые биты сообщений и равно двум, если
различаются вторые биты сообщений.
В случае систематического кодирования рассмотренная
выше процедура находит оценку переданного сообщения на
первых k позициях декодированного слова. Это может быть
1.3. Кодирование и декодирование линейных блоковых кодов 31
01-Glava01.qxd 22/11/2004 1:12 PM Page 31 (Black plate)
одной из возможных причин применения систематического
кодирования.
1.3.3. Хемминговы сферы, области
декодирования и стандартная таблица
Стандартная таблица предоставляет удобный способ объясне-
ния понятий Хемминговой сферы и корректирующей способ-
ности линейного кода С, введенной в Разделе 1.1.2.
Из конструкции стандартной таблицы видно, что j-ый
столбец из 2k правых столбцов таблицы, обозначаемый Colj,
1 ≤ 2k, содержит кодовое слово vj ∈ C и множество 2n – k слов,
ближайших к нему по Хеммингову расстоянию, т.е.
(1.23)
Каждый столбец (1.23) представляет собой область декодирова-
ния j-ого кодового слова в Хемминговом пространстве. Таким
образом, если по ДСК передано кодовое слово vj ∈ C и приня-
тое слово r принадлежит столбцу Colj , то оно будет успешно
декодировано в переданное слово vj.
Граница Хемминга
Множество столбцов Colj и корректирующая способность t ко-
да C связаны между собой через Хеммингову сферу St(vj) следу-
ющим образом: двоичный линейный (n, k, d) код C имеет кор-
ректирующую способность t, если каждая область декодирова-
ния Colj содержит Хеммингову сферу радиуса t, т.е. St(vj) ⊆ Colj.
Учитывая, что каждая область декодирования содержит
2n – k слов, и, используя уравнение (1.6), получаем знаменитую
границу Хемминга
(1.24)
Граница Хемминга имеет несколько комбинаторных ин-
терпретаций. Вот одна из них:
32 Глава. 1. Введение
01-Glava01.qxd 22/11/2004 1:12 PM Page 32 (Black plate)
Число синдромов, 2n – k, должно быть больше или равно числу
исправляемых комбинаций ошибок, .
Пример 7. Двоичный код (3,1,3) имеет порождающую мат-
рицу G = (111) и проверочную матрицу
Соответственно, стандартная таблица имеет вид:
s 0 1
00 000 111
11 100 011
10 010 101
01 001 110
Четыре вектора во втором столбце таблицы (т.е. лидеры
смежных классов) являются элементами Хемминговой сферы
S1(000), показанной на Рисунке 4. Этот столбец содержит все
векторы длины 3 и веса 1 или меньше. Аналогично, третий
столбец (правый) содержит все элементы S1(111). Для этого
кода граница Хемминга выполняется с равенством.
Блоковые коды, удовлетворяющие границе (1.24) с равен-
ством, называются совершенными кодами. Нетривиальными со-
вершенными кодами являются следующие:
– двоичные (2m – 1, 2m – m – 1, 3) коды Хемминга,
– недвоичные ((qm – 1)/(q – 1), (qm – 1)/(q – 1) – m – 1, 3) ко-
ды Хемминга, q > 2,
– коды-повторения (n,1,n),
– коды с проверкой на четность (n,n-1,2),
– двоичный (23,12,7) код Голея и
– троичный (11,6,5) код Голея.
Расширенные, т.е. дополненные общей проверкой на чет-
ность, коды Хемминга и Голея тоже совершенны.
Для недвоичных кодов граница Хемминга имеет вид:
1.3. Кодирование и декодирование линейных блоковых кодов 33
01-Glava01.qxd 22/11/2004 1:12 PM Page 33 (Black plate)
(1.25)
1.4. Распределение весов
и вероятность ошибки
При выборе конкретной схемы кодирования очень важно
иметь представление об ее помехоустойчивости. Известны не-
сколько характеристик помехоустойчивости систем с исправ-
лением ошибок. В этом разделе вводятся оценки для линейных
кодов и трех базовых моделей каналов: модель ДСК, модель
с аддитивным белым гауссовым шумом (АБГШ) и модель ка-
нала с общими Релеевскими замираниями.
1.4.1. Распределение весов и вероятность
необнаруженной ошибки в ДСК.
Распределение весов W(C) = {Ai, 0 ≤ i ≤ n} кода C, исправляюще-
го ошибки, определено как совокупность n + 1 целых Ai, где
Ai – количество кодовых слов Хеммингова веса i.
В следующем ниже разделе выводится оценка вероятности
необнаруженной ошибки линейного кода в ДСК. Заметим,
прежде всего, что вес wt(v) слова v равен Хеммингову расстоя-
нию до нулевого слова, т.е. wt(v) = dH(v,0). Напомним также,
что Хеммингово расстояние между кодовыми словами v1 и v2
равно весу их разности,
где из линейности кода следует, что v3 ∈ C.
Вероятность необнаруженной ошибки Pu(C) равна вероятно-
сти того, что принятое из канала связи слово отличается от пе-
реданного, но имеет нулевой синдром, т.е.
34 Глава. 1. Введение
01-Glava01.qxd 22/11/2004 1:12 PM Page 34 (Black plate)
Таким образом, вероятность того, что синдром принятого не-
нулевого слова равен нулю, есть вероятность того, что вектор
ошибок совпадает с одним из ненулевых кодовых слов.
В ДСК вектор ошибок веса i возникает с вероятностью,
равной вероятности того, что i символов приняты с ошибкой,
а остальные n-i приняты правильно. Обозначим вероятность
этого события через P(e, i). Тогда
Для того чтобы возникла необнаруженная ошибка, вектор
ошибок должен быть ненулевым кодовым словом. Имеется Ai
кодовых слов веса i в кодовом множестве C. Следовательно,
(1.26)
Формула (1.26) дает точное значение Pu(C) в ДСК. К сожалению,
для большинства кодов, имеющих практическое значение, рас-
пределение весов неизвестно. В таких случаях, можно использо-
вать тот факт, что число кодовых слов веса i меньше (или равно)
общего числа слов веса i в двоичном векторном пространстве V2.
Следовательно, справедлива следующая верхняя граница:
(1.27)
Дополнение переводчика. На самом деле допустима и более
сильная оценка:
В уравнении eHT = 0 матрица H имеет ранг ρ=dmin–1 и, по мень-
шей мере, ρ неизвестных элементов любого вектора ошибок e оп-
ределяются однозначно. Следовательно, средняя вероятность
того, что произвольный вектор ошибок совпадает с некоторым
кодовым словом, не превосходит 2 –ρ.
Формулы (1.26) и (1.27) полезны в системах, использую-
щих помехоустойчивое кодирование только для обнаружения
ошибок таких, как системы связи с обратной связью и автома-
1.4. Распределение весов и вероятность ошибки 35
01-Glava01.qxd 22/11/2004 1:12 PM Page 35 (Black plate)
тическим запросом (ARQ) на повторную передачу сообщения
с обнаруженными ошибками. Оценки помехоустойчивости
для случая, когда кодирование используется для исправления
ошибок, выводятся в следующем ниже разделе.
Пример 8. Для двоичного линейного (4,2,2) кода из Приме-
ра 4 W(C)=(1,0,1,2,0). С помощью (1.26) находим
На Рисунке 6 показана зависимость Pu(C) вместе с правой час-
тью границы (1.27).
1.4.2. Границы вероятности ошибки в ДСК,
каналах с АБГШ и с замираниями
Целью этого раздела является введение в базовые модели кана-
лов связи, которые будут рассматриваться в книге, и вывод
формул для оценки помехоустойчивости линейных кодов.
Первым рассматривается ДСК.
Модель ДСК
Для двоичного линейного кода процедура декодирования с по-
мощью стандартной таблицы состоит в выборе кодового слова,
36 Глава. 1. Введение
Рис. 6. Точное значение и верхняя граница вероятности необнару-
женной ошибки для двоичного линейного (4,2,2) кода в ДСК.
«Pu(4,2,2)»
«Pu(4,2,2)_граница»
01-Glava01.qxd 22/11/2004 1:12 PM Page 36 (Black plate)
ближайшего к принятому слову. Ошибка декодирования воз-
никает всякий раз, когда принятое слово оказывается вне пра-
вильной области декодирования.
Обозначим Li число лидеров смежных классов веса i
в стандартной таблице линейного кода C. Вероятность пра-
вильного декодирования равна вероятности того, что вектор
ошибок совпадает с одним из лидеров смежных классов,
(1.28)
где это максимальный вес лидера смежного класса e. Для со-
вершенных кодов = t ,
и из границы Хемминга (1.24) следует, что
В общем случае для двоичных кодов выражение (1.28) дает
нижнюю границу Pc(C), так как существует хотя бы один лидер
смежного класса веса более t.
Вероятность неправильного декодирования Pe(C) или веро-
ятность ошибки декодирования равна вероятности того, что
вектор ошибок принадлежит дополнению множества исправ-
ляемых ошибок, т.е. Pe(C) = 1 – Pc(C). Из (1.28) получаем,
(1.29)
Наконец, учитывая обсуждение оценки (1.28), получаем верх-
нюю границу
(1.30)
которую можно записать и в следующем виде
(1.31)
1.4. Распределение весов и вероятность ошибки 37
01-Glava01.qxd 22/11/2004 1:12 PM Page 37 (Black plate)
Эти границы удовлетворяются с равенством только для совер-
шенных кодов (когда и граница Хемминга удовлетворяется
с равенством).
Пример 9. На Рисунке 7 показана зависимость Pe(C) по
оценке (1.31) от переходной вероятности ДСК p для двоичного
(совершенного) кода-повторения (3,1,3).
Модель канала с АБГШ
Пожалуй, наиболее важной моделью для систем цифровой
связи является модель канала с аддитивным белым гауссовым
шумом (АБГШ – additive white Gaussian noise (AWGN)). В этом
разделе выводятся оценки вероятности ошибки декодирова-
ния и вероятности ошибки на бит для линейных кодов в кана-
ле с АБГШ. Хотя аналогичные выражения оказываются спра-
ведливыми и для сверточных кодов, они будут выведены в по-
следующих разделах, вместе с обсуждением декодирования
с «мягким решением» по алгоритму Витерби. Следующие ни-
же результаты содержат необходимые инструменты для оцен-
ки помехоустойчивости двоичных систем кодирования в гаус-
совом канале.
Рассмотрим двоичную систему передачи сигналов, в кото-
рой кодовые символы {0,1} отображаются в действительные
38 Глава. 1. Введение
Рис. 7. Вероятность ошибки декодирования для двоичного (3,1,3)
кода.
«Pe(3,1,3)_граница»
01-Glava01.qxd 22/11/2004 1:12 PM Page 38 (Black plate)
числа {+1,–1}, соответственно, как показано на Рисунке 8.
В дальнейшем, вектора имеют размерность n и обозначение
x = (x0, x1,…, xn–1). Условная функция плотности вероятности
(ф.п.в.) последовательности y на выходе канала при условии,
что на его входе передавалась последовательность x, равна
(1.32)
где pn(n) есть ф.п.в. n статистически независимых и одинаково
распределенных (i.i.d.) отсчетов шума, каждый из которых
имеет Гауссово распределение с нулевым средним и дисперси-
ей, раной N0/2. Величина N0 называется односторонней спек-
тральной плотностью мощности шума. Легко показать, что де-
кодирование по максимуму правдоподобия (м.п.) линейного кода
в таком канале соответствует выбору последовательности x′,
минимизирующей квадрат Евклидова расстояния между при-
нятой последовательностью y и x′, т.е.
(1.33)
см. [WJ], [Wil], [BM]. Следует заметить, что декодер, использу-
ющий (1.33) как метрику, называется декодером с мягким реше-
нием не зависимо от того, используется или нет принцип мак-
симума правдоподобия. Методы декодирования с мягким ре-
шением рассматриваются в Главе 7.
1.4. Распределение весов и вероятность ошибки 39
Рис. 8. Система двоичной передачи с кодированием по каналу
с АБГШ.
Источник
информации
Двоичный
кодер
Отображение
Декодер
с мягким
решением
Получатель
информации
01-Glava01.qxd 22/11/2004 1:12 PM Page 39 (Black plate)
Вероятность ошибки для МП декодирования, Pe(С), равна
вероятности того, что при передаче последовательности x век-
тор шума оказался таким, что принятая последовательность
y = x + n ближе к другой кодовой последовательности x″ ∈ C,
x″ ≠ x. Для линейного кода можно предположить, что переда-
ется нулевое кодовое слово. Тогда вероятность Pe(С) может
быть ограничена сверху с помощью границы объединения [Cla]
и распределения весов W(С) следующим образом:
(1.34)
где R = k/n скорость кода, Eb/N0 отношение энергии сигнала на
бит к мощности шума или (SNR на бит) и Q(x) определено
в (1.2).
На Рисунке 9 показаны оценки вероятности ошибки для
жесткого декодирования (1.30) и для мягкого декодирования
(1.34) для двоичного (3,1,3) кода. Декодирование с жестким
решением (или жесткое декодирование) означает, что декодер
40 Глава. 1. Введение
Рис. 9. Вероятность ошибки декодирования для жесткого декодирова-
ния (Pt(3,1,3)_HDD) и мягкого декодирования (Pe(3,1,3)_SDD)
двоичного (3,1,3) кода при передаче двоичных сигналов в кана-
ле с АБГШ.
01-Glava01.qxd 22/11/2004 1:12 PM Page 40 (Black plate)
для ДСК использует выход двоичного демодулятора. Экви-
валентный ДСК имеет переходную вероятность равную
[Pro, WJ]
Заметим, что в данном частном случае, обе оценки вероятнос-
ти ошибки являются точными, т.е. не оценками сверху, так как
используется совершенный код, содержащий только два кодо-
вых слова. Рисунок 9 показывает также, что мягкое декодиро-
вание обеспечивает большую эффективность, чем жесткое де-
кодирование, в том смысле, что одинаковое значение Pe(С)
при меньшей мощности передачи сигналов. Разность (в дБ)
между соответствующими отношениями SNR на бит обычно
называют выигрышем от кодирования.
В [FLR] показано, что для вероятности ошибки на бит,
обозначаемой Pb(C) двоичного систематического кода при пе-
редаче двоичных сигналов по каналу с АБГШ, справедлива
следующая верхняя граница:
(1.35)
Эта граница справедлива только для систематического кода.
Кроме того, результаты в [FLR] показывают, что системати-
ческое кодирование минимизирует вероятность ошибки на бит.
Это означает, что систематическое кодирование не только
желательно, но и оптимально в рассматриваемом выше
смысле.
Пример 10. Рассмотрим двоичный линейный (6,3,3) код
с порождающей и проверочной матрицами
1.4. Распределение весов и вероятность ошибки 41
01-Glava01.qxd 22/11/2004 1:12 PM Page 41 (Black plate)
соответственно. Распределение весов этого кода равно W(C) =
{1,0,0,4,3,0,0}, которое может быть проверено непосредствен-
ным вычислением для всех кодовых слов v = (u,vp):
u v
000 000
001 101
010 011
011 110
100 110
101 011
110 101
111 000
В этом частном случае, МП декодирование состоит в вычисле-
нии квадрата Евклидова расстояния по формуле (1.33) между
принятым словом и каждым из восьми возможных кодовых
слов. В качестве решения выбирается слово с наименьшим
расстоянием. На Рисунке 10 показаны результаты моделирова-
ния и границы объединения для жесткого и мягкого декодиро-
42 Глава. 1. Введение
Рис. 10. Моделирование и границы объедиения для двоичного (6,3,3)
кода при передаче двоичных сигналов в канале с АБГШ.
01-Glava01.qxd 22/11/2004 1:12 PM Page 42 (Black plate)
вания по максимуму правдоподобия для передачи двоичных
сигналов в канале с АБГШ.
Модель канала с общими Релеевскими замираниями.
Другой важной моделью канала является модель с общими Ре-
леевскими замираниями. Замирания сигналов происходят
в системах беспроводной связи в виде меняющихся во време-
ни искажений передаваемых сигналов. В этой книге рассмат-
риваются только общие замирания (flat fading). Термин «общие»
(или «гладкие») означает, что канал не является частотно-се-
лективным, т.е. передаточная функция канала в полосе пропу-
скания равна константе [BM, WJ, Pro].
Модель канала с покомпонентными мультипликативными
искажениями показана на Рисунке 11. Мультипликативные
искажения представлены случайным вектором α размерности
n, компоненты которого являются независимыми, одинаково
распределенными случайными величинами (i.i.d.), αi, 0 ≤ i < n,
имеющими плотность вероятности Релея,
(1.36)
При такой плотности вероятностей множителей среднее зна-
чение отношения сигнал-шум (SNR) на бит равно Eb/N0 (как
и для АБГШ без замираний), так как второй момент коэффи-
циентов замирания равен E{αi
2} = 1.
1.4. Распределение весов и вероятность ошибки 43
Рис. 11. Передача двоичных кодированных сообщений в канале
с гладкими Релеевскими замираниями
Источник
информации
Двоичный
кодер
Отображение
Декодер
с мягким
решением
Получатель
информации
01-Glava01.qxd 22/11/2004 1:12 PM Page 43 (Black plate)
Оценки эффективности двоичных линейных кодов в кана-
ле с общими Релеевскими замираниями находятся из оценок
условной вероятности ошибки декодирования, Pe(C| ),
или условной вероятности ошибки на бит, Pb(C| ). Безуслов-
ные вероятности ошибки находятся интегрированием услов-
ных вероятностей с весами αi, имеющими плотность вероят-
ности (1.36).
Условные вероятности ошибки идентичны безусловным
в канале с АБГШ. Существенное различие имеется только
в аргументах функции Q(x), которые теперь взвешены на коэф-
фициенты замирания αi. Рассматривая передачу двоичных ко-
дированных сообщений при отсутствии (внешней) информа-
ции о состоянии канала, находим, что
(1.37)
где
44 Глава. 1. Введение
Рис. 12. Двоичная передача по Релеевскому каналу. Результаты моде-
лирования (SIM), оценка границы объединения методом
Монте-Карло (Pe(3,1,3)_MC) и граница Чернова
(Pe(3,1,3)_EXP) для двоичного (3.1,3) кода.
01-Glava01.qxd 22/11/2004 1:12 PM Page 44 (Black plate)
(1.38)
Окончательно, вероятность ошибки декодирования при
передаче двоичных сигналов в канале с Релеевскими замира-
ниями получается как математическое ожидание относитель-
но случайной величины Δw,
(1.39)
Известны несколько методов оценивания выражения
(1.39). Один из них состоит в применении метода Монте-Кар-
ло численного интегрирования с использованием следующей ап-
проксимации:
(1.40)
где Δw( ) равно сумме квадратов w независимых одинаково
распределенных (i.i.d.) случайных величин с Релеевской плот-
ностью вероятностей (1.38), выданных на -ом обращении
к компьютерной программе генерации, и N достаточно боль-
шое целое число, зависящее от ожидаемого диапазона значе-
ний Pe(C). Хорошим правилом, которое следует запомнить, яв-
ляется следующее: величина N должна быть, по меньшей мере,
в 100 раз больше обратной величины Pe(C). (См. [Jer],
стр. 500–503)
Другим методом является экспоненциальная аппроксима-
ция сверху функции Q (см. [WJ], стр. 82-84), которая позволя-
ет проинтегрировать выражение или воспользоваться границей
Чернова. Этот подход хоть и несколько ухудшает результат, за-
то дает замкнутое выражение ([Wil], стр. 526, и [BM], стр. 718):
(1.41)
1.4. Распределение весов и вероятность ошибки 45
01-Glava01.qxd 22/11/2004 1:12 PM Page 45 (Black plate)
Граница (1.41) полезна в случаях, когда достаточно знать пер-
вое приближение в оценке помехоустойчивости кода.
Пример 11. На Рисунке 12 показаны результаты компью-
терного моделирования двоичного (3,1,3) кода в канале
с общими Релеевскими замираниями. Заметим, что интег-
рирование методом Монте-Карло дает точное значение по-
мехоустойчивости кода, так как граница (1.40) содержит
только один член. Заметим также, что граница Чернова дает
результат, смещенный почти на 2дБ, относительно результа-
та моделирования при отношении сигнал-шум на бит
Eb/N0 > 18 дБ.
Пример 12. На Рисунке 13 показаны результаты компью-
терного моделирования двоичного (6,3,3) кода из примера 10
в Релеевском канале. В этом случае граница объединения теря-
ет точность при малых значениях Eb/N0 из-за присутствия до-
полнительных членов в формуле (1.40). Как и раньше, граница
46 Глава. 1. Введение
Рис. 13. Двоичная передача по Релеевскому каналу. Результаты моде-
лирования (SIM_(6,3,3)),оценка границы объединения мето-
дом Монте-Карло (Pe(6,3,3)_MC) и граница Чернова
(Pe(6,3,3)_EXP) для двоичного (6,3,3) кода.
01-Glava01.qxd 22/11/2004 1:12 PM Page 46 (Black plate)
Чернова проигрывает около 2 дБ в отношении сигнал – шум
на бит при Eb /N0>18 дБ.
1.5 Общая структура жесткого
декодера для линейных кодов
В этом разделе проводится итоговое обсуждение структуры де-
кодера с жестким решением. На Рисунке 14 показана упро-
щенная блок-схема процесса декодирования. Так как обсужда-
ется жесткое решение, то решения демодулятора поступают на
вход декодера, рассчитанного на работу с ДСК.
Обозначим v ∈ C переданное кодовое слово. На вход деко-
дера подается принятое искаженное слово r = v + e. Процеду-
ра декодирования состоит из следующих шагов:
• Вычисляется синдром s = r HT. Согласно свойству линейно-
го кода синдром является линейным преобразованием векто-
ра ошибок, возникшего в канале,
(1.42)
• Для вычисленного синдрома s найти наиболее вероятный
вектор ошибок e и вычесть его (по модулю два в двоичном
случае) из принятого вектора.
Несмотря на то, что большинство практических декодеров
не реализуют процедуру декодирования так, как она сформу-
лирована выше, имеет смысл рассматривать процедуру жест-
1.4. Распределение весов и вероятность ошибки 47
Рис. 14. Общая структура жесткого декодера для линейных блоковых
кодов для ДСК.
Вычислить
синдром
Найти
вектор
ошибок
Буфер хранения
принятого вектора
01-Glava01.qxd 22/11/2004 1:12 PM Page 47 (Black plate)
кого декодирования как метод решения уравнения (1.42). За-
метим, что любой метод решения этого уравнения является
методом декодирования. Например, можно попытаться ре-
шать это (ключевое) уравнение с помощью псевдо-обратной
матрицы (HT)+ матрицы HT такой, что HT(HT)+ = In и для ко-
торой результат декодирования
(1.42)
имеет наименьший вес Хемминга. Как легко бы это не казалось,
задача эта очень сложна. Мы вернемся к этому соображению
при обсуждении методов декодирования кодов БЧХ и Рида-
Соломона.