- •В.Г. Ланских теория информации
- •Предисловие
- •Содержание
- •Лекция 1 введение
- •Глава 1.
- •1.1. Случайные события и их вероятности
- •Случайные величины и процессы
- •1.2.1. Дискретные случайные величины и процессы
- •1.2.2. Непрерывные случайные величины и процессы
- •1.3. Методы спектрального описания случайных процессов
- •1.3.1. Понятие спектра детерминированного процесса
- •1.3.2. Спектральное описание случайных процессов
- •1.4. Дискретизация и квантование
- •1.4.1. Дискретизация
- •1.4.2. Квантование
- •1.5. Классификация помех
- •1.6. Модели каналов
- •1.6.1. Модели дискретных каналов
- •1.6.2. Модели непрерывных каналов
- •1.7. Методы модуляции
- •1.7.1. Непрерывные методы модуляции и манипуляции
- •1.7.2. Методы импульсной модуляции
- •1.7.3. Методы цифровой модуляции
- •1.8. Согласование характеристик сигнала и канала
- •Глава 2 количественные оценки информационных объектов и процессов
- •2.1. Подходы к определению количества информации
- •Основы статистического подхода к определению количества информации
- •2.3. Энтропия объединения (ансамбля)
- •2.4. Основная теорема Шеннона для дискретного канала
- •2.5. Энтропийные характеристики непрерывных информационных
- •Глава 3 основы теории кодирования
- •3.1. Назначение и классификация кодов
- •3.2. Эффективное кодирование
- •3.3. Помехоустойчивое кодирование
- •3.3.2. Классификация избыточных двоичных кодов
- •3.3.3 Простейшие блоковые коды с обнаружением ошибок
- •3.3.4. Групповые коды с обнаружением и исправлением ошибок
- •Важнейшие классы полиномиальных кодов
- •3.3.5. Сверточные коды
- •3.3.6. Каскадные коды
- •3.3.7. Оценка эффективности применения корректирующих кодов
3.3.2. Классификация избыточных двоичных кодов
Из сказанного ранее следует, что код приобретает свойства обнаруживать и исправлять ошибки только в том случае, если он обладает избыточностью.
Рассмотрим одну из возможных классификаций избыточных корректирующих кодов (рис. 3.8):
1. Так же как и неизбыточные, избыточные коды могут быть подразделены на равномерные и неравномерные. Признаком равномерности является то, что в каждой кодовой комбинации содержится n = const разрядов. Неравномерные коды получили существенно меньшее распространение.
2. Если каждый символ сообщения кодируется, т.е. превращается в кодовую комбинацию (блок) независимо от других символов сообщения, так, что закодированная последовательность символов представляет собой последовательность независимых кодовых комбинаций одинаковой длины, то такой код называют блоковым. Если кодирование каждого символа сообщения зависит от предшествующих или последующих символов, так, что закодированная последовательность представляет собой одно полубесконечное слово, то такой код называется непрерывным. Эти коды появились сравнительно недавно, но бурно развиваются.
|
Рис. 3.8. Классификация избыточных корректирующих кодов |
3. Если в каждой кодовой комбинации длины n блокового кода можно выделить k разрядов, предназначенных собственно для передачи информации и называемых информационными, и n-k разрядов, избыточно введенных для увеличения кодового расстояния кода с целью придания ему корректирующих свойств, то такой код называется разделимым. Эти n-k разрядов называются контрольными или проверочными. Если такого разделения разрядов кодовой комбинации по их функциональному назначению произвести нельзя, то такой код называется неразделимым.
4. Если в разделимом коде при кодировании информационные символы не изменяются, то такой код называется систематическим. В противном случае, т.е. когда при кодировании изменяются не только проверочные, но и информационные разряды, код называется несистематическим. Характерной особенностью большинства систематических кодов является то, что проверочные n-k разрядов кодовой комбинации представляют собой результаты определенных линейных операций над k информационными разрядами. Такие коды называются линейными. Линейные коды образуют векторное пространство и обладают следующим важным свойством: две кодовые комбинации можно сложить (для двоичных кодов - по модулю два), в результате чего получится третья кодовая комбинация этого же кода. Это свойство приводит к двум важным следствиям. Первое - каждая кодовая комбинация выражается в виде линейной комбинации небольшого числа выделенных кодовых комбинаций, называемых базисными векторами. Это существенно упрощает как описание кода (см.далее - матричное описание), так и процедуры кодирования и декодирования. Второе - линейность существенно упрощает вычисление параметров кода, в частности, кодового расстояния. Расстояние Хэмминга между данной кодовой комбинацией и нулевой кодовой комбинацией равно числу ненулевых элементов в данной кодовой комбинации. Это число часто называют весом Хэмминга данной кодовой комбинации. Список, содержащий число кодовых комбинаций каждого веса, называют спектром кода.
5. Из класса систематических кодов можно выделить еще один подкласс кодов, называемых циклическими. Характерной особенностью циклических кодов, при сохранении всех свойств систематических кодов, является то, что если комбинация принадлежит циклическому коду, то комбинация, полученная из первой путем циклического сдвига, тоже будет принадлежать этому коду.
Все рассмотренные выше коды являются избыточными, т.е. такими, у которых d 2. В зависимости от величины d коды подразделяются на коды, только обнаруживающие ошибки, и коды исправляющие ошибки.