2.6. Алгоритмы эффективного кодирования неравновероятных взаимозависимых символов сообщений

Устранение взаимной зависимости символов источника сообщения может быть осуществлено путем укрупнения алфавита исходного источника сообщения. Для этого подлежащие кодированию сообщения последовательно разбиваются на двух-, трех- или n-знаковые сочетания (блоки), вероятности которых известны, а затем эти сочетания кодируются в соответствии с алгоритмами Шеннона-Фено или Хаффмена.

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

Этот недостаток может быть устранен кодированием по методу диаграмм, триграмм или в общем случае k-грамм. k-граммой называют последовательность из k смежных символов сообщения. При k=2 сочетание смежных знаков называют диаграммой, при k=3 — триграммой и т.д.

В процессе кодирования по методу k-грамм производят непрерывное последовательное перемещение k-граммы по сообщению с шагом равным одному символу. Этот процесс (получение 3-х k-грамм) иллюстрируется рис. 2.3, где x_i - символы сообщения.

Рис 2.3. Процесс непрерывного последовательного перемещения k-граммы по сообщению.

Если вероятности появления различных k-грамм известны, то их эффективное кодирование, в частности, может быть выполнено по алгоритмам Шеннона-Фено или Хаффмена. Конкретное значение k выбирается исходя из степени взаимозависимости между символами сообщения и сложности технической реализации кодирующих и декодирующих устройств.

2.7. Недостатки алгоритмов эффективного кодирования.

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

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

2.8. Помехоустойчивое (корректирующее) кодирование. Общие понятия

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

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

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

Все алгебраические коды можно разделить на два больших класса: блочные (блоковые) и непрерывные.

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

Непрерывные (древовидные) коды представляют собой непрерывную последовательность кодовых символов, причем введение проверочных элементов производится непрерывно, без разделения ее на независимые блоки.

Как блочные коды, так и непрерывные могут быть разделимыми и неразделимыми.

В разделимых кодах информационные и проверочные элементы символов кода отчетливо разграничены и всегда занимают одни и те же определенные позиции (разряды). Такие коды часто называют (n,k) коды, где n — длина кодового символа, k — число информационных элементов в нем.

При кодировании неразделимыми кодами разделение кодового символа на информационные элементы и проверочные невозможно.

Среди разделимых кодов выделяют систематические (линейные) и несистематические. Систематическими кодами называют коды, в которых проверочные элементы являются линейными комбинациями информационных. Эти коды наиболее распространены, т.к. их использование существенно упрощает техническую реализацию кодирующих и декодирующих устройств.