1.1.2 Основы теории помехоустойчивого кодирования

[1, с. 131–158]; [2, с. 168–193].

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

Теоретическую основу помехоустойчивого кодирования составляет теорема К. Шеннона для канала с шумами, в которой утверждается, что для указанного канала можно найти такую систему оптимального кодиро­вания, при которой сообщения будут переданы со сколь угодно большой степенью верности, если только производительность источника не превы­шает пропускной способности канала связи. Другой важный результат теории оптимального кодирования состоит в том, что принципиально сколь угодно малая вероятность неправильного декодирования может быть достигнута при использовании кодов, имеющих весьма длинные ко­довые комбинации ( кодовые слова).

Следует чётко усвоить, что результаты К. Шеннона указывают на предельные возможности при оптимальном кодировании и декодировании дискретных сообщений, но не дают рекомендаций по их конкретной реали­зации. Поэтому основной задачей теории корректирующих кодов, опреде­лившей последующие пути её развития, является нахождение практически реализуемых (конструктивных) методов построения кодеров и декодеров (кодеков).

Для понимания принципов кодирования и декодирования дискрет­ных сообщений необходимо усвоить следующие основные понятия. Коди­рование – это процесс преобразования элементов дискретного сообщения в соответствующие числа, представленные кодовыми символами. Например, любое десятичное число можно представить в m_k -ичной системе счисления. Кодовая комбинация ( кодовое слово) – это последовательность кодовых символов, соответствующих одному элементу дискретного сообщения. Ко­дом называют полную совокупность кодовых комбинаций, применяемую для кодирования сообщений. Значность кодовой комбинации – это число n символов в ней (длина кодовой комбинации). Если все кодовые комбинации кода имеют одинаковую значимость (длину) – код называется равномерным, например телеграфный код (Бодо, М–2 и т.д.); в противном случае код является неравномерным, например код Морзе, статис­тический код Шеннона–Фано–Хаффмена и др. Число различных символов в коде называют основанием кода m_k. Если m_k = 2 – код называется двоичным, при m_k  2 – код многопозиционный.

Корректирующая способность кода – это способность кода обнару­живать или исправлять ошибки. Ошибки при передаче кодированного сообщения сводятся к тому, что некоторые из переданных кодовых символов на приёме заменяются другими – неверными из-за действия помех в канале. Число t искаженных кодовых символов в пределах одной кодовой комбинации называют кратностью ошибок. В теории помехоустойчивого кодирования пользуются понятием расстояния между двумя кодовыми комбинациями и понятием кодового расстояния кода. Расстояние d_ между двумя  -й и  -й кодовыми комбинациями кода – это суммарный результат сложения по модулю m_k их одноимённых кодовых символов (расстояние Хэмминга). Для двоичных кодов расстояние d_ – есть число разрядов, в которых символы этих кодовых комбинаций не совпадают. Кодовое расстояние кода, содержащего более двух кодовых комбинаций, есть минимальное расстояние d = min{d_} из совокупности расстояний между различными парами кодовых комбинаций кода. Число d определяет корректирующую способность кода. Если d = 1, код называется примитивным (некорректирующим). Такой код не способен обнаруживать и исправлять на приёме возникающие при передаче в канале связи ошибки. Код - корректирующий (помехоустойчивый), если d  1. Чем больше кодовое расстояние, тем лучше корректирующая способность кода. Кратность гарантированно обнаруживаемых и исправляемых кодом ошибок определяется соотношениями

t_обн = d - 1 и t_исп = (d - 1)/2.

В настоящее время на практике используются как блочные коды, так и непрерывные (сверточные) коды. При блочном кодировании последовательность информационных кодовых символов разбивается на блоки (кодовые комбинации) по k символов в каждом. Затем каждому такому k-значному блоку сопоставляется n-значный блок, в котором k кодовых символов называются информационными, а добавочные (избыточные) r=(n–k) – корректирующими или проверочными. Такой код называют блочным (n,k) кодом. Двоичный блочный (n,k) код содержит N_р=2^k разрешённых n–значных кодовых комбинаций. Всего же двоичных n-значных кодовых комбинаций можно образовать N_о=2ⁿ. Неиспользуемые N_з = N_о – N_р кодовые комбинации называют запрещёнными, они по каналу связи не передаются, но необходимы для обнаружения ошибок на приёме.

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

Декодирование корректирующего кода на основе хранения всех разрешенных кодовых комбинаций не является конструктивным. С целью упрощения декодеров был разработан класс линейных корректирующих кодов, когда в памяти декодера достаточно хранить только k = log₂ N_р линейно независимых кодовых комбинаций кода. Двоичный код называется линейным, если сумма по модулю 2 любых разрешенных кодовых комбинаций кода также принадлежит данному коду. При этом любая разрешенная кодовая комбинация линейного кода образуется путём суммирования по модулю 2 линейно независимых кодовых комбинаций.

В поисках более простой техники кодирования и декодирования был найден подкласс линейных двоичных кодов, названных циклическими. В циклическом коде каждая новая комбинация, получаемая путём циклической перестановки кодовых символов разрешенной комбинации, также является разрешенной комбинацией. Кроме циклических кодов в технике связи получили широкое распространение и другие коды: итеративные, непрерывные, свёрточные и т.п.

Вопросы для самопроверки

1. Как оценить количество информации, содержащееся в случайной величине, появляющейся с заданной вероятностью?

2. Как оценить энтропию источника дискретных сообщений?

3. Как оценить энтропию источника непрерывных сообщений?

4. Что такое условная энтропия и как она определяется?

5. Как вычислить производительность и избыточность источника?

6. Что такое взаимная информация и скорость передачи информации?

7. Как определить пропускную способность и коэффициент использования канала связи?

8. В чём состоит принцип построения эффективного кода?

9. В чём состоит принцип построения корректирующего кода?

10. В чём состоит принцип декодирования с обнаружением ошибок?

11. В чём состоит принцип декодирования с исправлением ошибок?

12. В чём состоит принцип построения линейного корректирующего кода?

13. Дайте определение расстояния между двумя кодовыми комбинациями и ко-дового расстояния кода.

14. Как определить число разрешенных, число запрещённых и общее число кодовых комбинаций блочного (n, k) кода?

15. Каким должно быть кодовое расстояние кода, обнаруживающего ошибки заданной кратности?

16. Каким должно быть кодовое расстояние кода, исправляющего ошибки заданной кратности?

17. В чём состоит синдромный принцип декодирования линейного корректирующего кода?

18. Что такое порождающая и проверочная матрицы линейного корректирующего кода и их взаимосвязь?

19. Как оценить помехоустойчивость корректирующего кода?

20. Приведите разновидности помехоустойчивого кодирования.