- •Введение
- •1. Энтропия источников сообщений
- •1.1. Дискретные ансамбли и источники
- •1.2. Количество информации в дискретном сообщении. Энтропия ансамбля
- •1.3. Условная информация. Условная энтропия. Совместная энтропия дискретного источника
- •1.4. Энтропия дискретного стационарного источника на сообщение
- •1.5. Избыточность источника дискретных сообщений
- •1.6. Эффективное кодирование. Кодирование источника равномерными кодами
- •1.7. Высоковероятные множества постоянного дискретного источника
- •1.8. Энтропия источника без памяти как скорость создания информации
- •1.9. Избыточность источника непрерывных сигналов. Количество информации в непрерывном канале
- •1.10. Скорость передачи информации и пропускная способность в непрерывном канале
- •2. Кодирование информации
- •2.1. Неравномерное кодирование с однозначным декодированием
- •2.2. Оптимальные неравномерные двоичные коды
- •2.3. Кодирование для исправления ошибок: Основные положения
- •2.4. Постановка задачи кодирования
- •2.5. Прямая теорема о кодировании в канале с шумами
- •2.6. Обратная теорема кодирования
- •2.7. Основная теорема Шеннона, ограничение возможностей использования оптимального кодирования на практике
- •3. Коды, исправляющие ошибки
- •3.1. Блоковые и сверточные коды
- •3.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность
- •3.3. Линейные блоковые коды
- •3.4. Порождающая и проверочная матрицы. Кодирование с помощью матриц g и н
- •3.5. Декодирование по стандартной таблице
- •3.6. Циклические коды
- •3.7. Кодирующие устройства циклических кодов
- •3.8. Декодирование циклических кодов по синдрому
- •3.9. Мажоритарное декодирование
- •4. Энтропия в контексте защиты информации от помех при передаче по каналу связи
- •4.1. Меры искажения. Постановка задачи защиты информации от помех при передаче по каналу связи
- •4.2. Свойства функции скорость-искажение
- •4.3. Простые примеры вычисления функции скорость-искажение
- •4.4. Функция скорость-искажение для гауссовских последовательностей
- •4.5. Эпсилон-производительность источника
- •4.6. Дифференциальная энтропия
- •4.7. Свойства дифференциальной энтропии
- •4.8. Эпсилон - энтропия источника сообщений
- •4.9. Обратная теорема кодирования для дискретного постоянного источника при заданном критерии качества
- •4.10. Прямая теорема кодирования с заданным критерием качества
- •4.11. Аксиоматическое введение в теорию энтропии вероятностных схем
- •4.12. Энтропия и условная энтропия объединенной вероятностной схемы и их свойства
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
3. Коды, исправляющие ошибки
3.1. Блоковые и сверточные коды
В соответствии с тем, как вводится избыточность в сообщение, коды, исправляющие ошибки, могут быть разделены на два класса: блоковые и сверточные (convolutionalcode)коды. Обе схемы кодирования нашли практическое применение. Исторически сверточные коды имели преимущество главным образом потому, что для них известен алгоритм декодирования Витерби с мягким решением и в течение многих лет существовала убежденность в том, что блоковые коды невозможно декодировать с мягким решением. Однако последние достижения в теории и конструировании алгоритмов декодирования с мягким решением для линейных блоковых кодов помогли рассеять это убеждение. Более того, наилучшие ЕСС, известные сегодня (в начале двадцать первого века), являются блоковыми кодами (нерегулярными кодами с низкой плотностью проверок — irregularlow-densityparity-checkcodes).
При блоковом кодировании каждый блок информационных символов обрабатывается независимо от других. Другими словами, блоковое кодирование является операцией без памяти в том смысле, что кодовые слова не зависят друг от друга. Выход сверточного кодера, напротив, зависит не только от информационных символов в данный момент, но и от предыдущих символов на его входе или выходе. Чтобы упростить объяснения, мы начнем с изучения структурных свойств блоковых кодов. Многие из этих свойств являются общими для обоих типов кодов.
Следует заметить, что на самом деле блоковые коды обладают памятью, если рассматривать кодирование как побитовый процесс в пределах кодового слова. Сегодня это различие между блоковыми и сверточными кодами кажется все менее и менее ясным, особенно после недавних достижений в понимании решетчатой (trellis) структуры блоковых кодов и кольцевой (tail-biting) структуры некоторых сверточных кодов.
Дополнение переводчика. Название кольцевые сверточные коды еще не окончательно утвердилось в отечественной литературе, иногда tail-bitingconvolutionalcodesназывают циклически замкнутыми.
Специалисты по сверточным кодам иногда рассматривают блоковые коды как «коды с меняющейся во времени структурой решетки» (time-varyingtrellisstructure).Аналогично, специалисты в области блоковых кодов могут рассматривать сверточные коды как «коды с регулярной структурой решетки».
3.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность
Рассмотрим двоичный код С, исправляющий ошибки. Еслиневсе из 2n возможных двоичных векторов длины n будут передаваться по каналу связи, то этот код может обладать свойством помехоустойчивости. В действительности, код С является подмножеством n-мерного двоичного векторного пространства таким, что элементы этого подмножества максимально удалены друг от друга.
В двоичном пространствеV2расстояние определяется как число позиций, на которых два вектора не совпадают. Пусть и два вектора в V2. Тогда Хеммингово расстояние между векторами х, и х2, обозначаемое какdH(x1,х2), равно
(3.1)
где через обозначено число элементов в множестве А.
Для заданного кода С минимальное Хеммингово расстояние, dmin,определяется как минимум Хеммингова расстояния по всем возможным парам различных кодовых слов,
(3.2)
Повсюду в книге обозначение (n,k, dmin)используется для параметров блокового кода длины n, который используется для кодирования сообщений длиныk, и имеет минимальное Хеммингово расстояниеdmin.Предполагается, что число кодовых слов этого кода равно
Пример. Простейшим примером является код-повторение длины 3. Каждый информационный бит повторяется три раза. Таким образом, сообщение «О» кодируется вектором (ООО), а сообщение «1», вектором (111). Так как два вектора различаются в трех позициях, Хеммингово расстояние между ними равно 3. На рисунке 3.1 показано графическое представление этого кода. Трехмерное двоичное векторное пространство соответствует 23=8 вершинам трехмерного единичного куба. Хеммингово расстояние между кодовыми словами (ООО) и (111) равно числу вершин, через которые проходит соединяющий их путь. Это эквивалентно числу координат, которые необходимо изменить, чтобы преобразовать (ООО) в (111) и наоборот. Таким образом, . Так как в этом коде только два кодовых слова, тоdmin= 3.
Двоичное векторное пространствоV2обычно называют Хемминговым пространством. Пустьvкодовое слово кода С. Хемминговой сферой St(v) радиусаtс центром в точкеvявляется множество векторов (точек) вV2на расстоянии меньше или равномtот центраv,
(3.3)
Рис. 3.1. (3,1,3) код-повторение в трехмерном векторном пространстве
Рис. 3.2. Хемминговы сферы радиусаt= 1, окружающие кодовые слова (3,1,3) двоичного кода-повторения
Заметим, что число слов (число векторов) в St(v) равно
(3.4)
Пример. На рис. 3.2 показаны Хемминговы сферы радиусаt= 1, окружающие кодовые слова (3,1,3) двоичного кода-повторения.
Заметим, что Хемминговы сферы для этого кода не пересекаются, т.е. в пространстве V2 нет векторов (или вершин в единичном трехмерном кубе), принадлежащих одновременно и (000), и (111). В результате, если изменить любую одну позицию кодового слова то получится вектор, который, тем не менее, останется внутри Хемминговой сферы с центром в v. Эта идея является принципиальной для понимания и определения корректирующей способности кода С.
Корректирующей способностью (errorcorrectingcapability) t кода С называют наибольший радиус Хемминговой сферы St(y) для всех кодовых слов v С такой, что для любых различных пар V соответствующие им Хемминговы сферы не пересекаются, т.е.
(3.5)
Это соответствует более распространенному определению
(3.6)
где [x]обозначена целая часть х, т.е. целое число меньше или равное х.
Заметим, что для определения минимального кодового расстояния произвольного блокового кода С в соответствии с (1.4), необходимо вычислить все2k{2k— 1) расстояний между различными парами кодовых слов. Это практически невозможно даже для сравнительно коротких кодов, например, с к = 50. Одним из важных преимуществ линейных блоковых кодов является то, что для вычисления dmm достаточно знать только Хемминговы веса 2к - 1 ненулевых кодовых слов.