Блоковое кодирование, перемежение,  расстояние Хемминга и декодирование

 

Структурная схема процесса передачи сообщений в системе связи с блоковым кодированием изображена на рис. 3.1.

Рис. 3.1. Структурная схема системы связи с блоковым кодированием.

 

Структура кодового слова (n, k) на выходе кодера и входе декодера дана на рис.3.2:

 

Рис.3.2. Структура кодового слова (n, k) на выходе кодера и входе декодера, расстояние Хемминга равно 4.

Рассмотрим принцип передачи сообщений в системе связи. Источник двоичных сообщений вырабатывает последовательность символов сообщения со скоростью R симв./сек. Символы группируются в блоки длиной k символов. В каждый блок добавляется (n - k) избыточных (проверочных) символов и образуется кодовое слово (n, k) избыточного блокового кода рис. 3.2. Скорость передачи информации на выходе кодера называется кодовой скоростью и равна k / n (бит/символ),а электрическая скорость равна   R ∙ n / k.

Таким образом, в кодере осуществляется преобразование информационной последовательности из   k бит:

                                  (3.4)

в двоичное кодовое слово длиной n бит

                                (3.5)

путем добавления (n - k) сформированных проверочных символов.

В декодере реализуется обратная операция: по принятой последовательности символов

                                  (3.6)

определяется переданное кодовое слово.                                                  Если все передаваемые кодовые слова равновероятны, а канал связи не имеет памяти, то согласно алгоритму МП в качестве наиболее вероятного выбирается то слово, которое ближе всего в смысле расстояния Хемминга находится к принятому кодовому слову.

Расстояние Хемминга между последовательностями и (рис. 3.2) оценивается весом слова вектора ошибок (числом двоичных единиц), образованного путем посимвольного сложения по модулю 2 последовательностей и.

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

Перемежение заключается в ''рассеянии'' символов передаваемых кодовых слов. При этом рассеянные символы должны находиться друг от друга на расстоянии, обеспечивающем независимые замирания. Перемежение преобразует статистику группирующихся в пакеты ошибок и разрушает ''память'' канала. Поэтому последовательно принимаемые двоичные символы после обратной операции перемежения независимы.

Различают диагональное, сверточное, межблоковое  перемежение. Например, при межблоковом перемежении рис. 3.3 l кодовых слов исходного кода размещаются в виде l строк прямоугольной матрицы.

                Рис.3.3. Принцип межблокового перемежения.

 

Считывание для передачи осуществляется по столбцам. Независимо от начала возникновения пакета ошибок длиной l он будет поражать только один символ каждой строки. Параметр l называют глубиной перемежения.

При приеме производится считывание по строкам, т.е. кодовых слов исходного кода. Тогда отдельные символы пораженных пакетов ошибок будут принадлежать различным кодовым словам.

Таким образом, если исходный код обладает способностью исправлять одиночные ошибки в пределах кодового слова, то этот же код с перемежением будет исправлять одиночные пакеты ошибок длиной l или менее. Недостаток перемежения - задержка информации на l слов.

Если же исходный код может исправлять одиночные пакеты ошибок длиной l или менее, то этот же код с перемежением будет исправлять одиночные пакеты длиной l l  или менее.

Эффективность кода оценивают показателем качества кода.

Пусть мощность передатчика дискретных сообщений ограничена и равна Р, а длительность сообщения, содержащего k символов, равна Т _k. Тогда энергия сигнала, приходящаяся на слово сообщения, равна Р Т _k, а энергия на символ сообщения равна Р Т _k / k.

При блоковом избыточном кодировании имеющаяся энергия распределяется между всеми символами. Поэтому энергия, приходящаяся на кодовый символ, равна Р Т _k / n.

Так как n > k, то при кодировании энергия, приходящаяся на символ кода, уменьшается. Это приводит к тому, что в системе с избыточным кодированием вероятность ошибки на символ избыточного кода больше, чем в системе без такого кодирования. Если код обладает высокой корректирующей способностью, то (n - k) проверочных символов ''отыгрывают'' эти потери, обеспечивая дополнительный энергетический выигрыш кодирования (ЭВК).

Предположим, что код имеет минимальное расстояние Хемминга   d_min (3.1)  и исправляет все ошибки согласно рис.3.4 кратности

.                                            (3.7)

 

              Рис. 3.4. Иллюстрация исправления ошибок кратности l.

Если обозначить вероятность ошибки в символе в системах с кодированием и без кодирования соответственно q _с и q_u, то вероятность ошибки в слове без кодирования и с кодированием  будет определяться выражениями:

                                  (3.8)

,               (3.9)

где - число возможных комбинаций из n символов, содержащих i ошибок.

Коды, для которых (3.9) выполняется строго, называются совершенными. Примером совершенных кодов служит код Хемминга, исправляющий одиночные ошибки, и код Голея.

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

Найдем более простой алгоритм реализации декодирования линейных блоковых кодов по правилу МП.