Классификация кодов, их представление, свойства кодов без избыточности

Под кодированием (в узком смысле или дискретом кодировании) понимают процедуру сопоставления дискретному (или дискретизированному непрерывному) сообщению яД/ = 1, 2, 3,К) определенной последовательности кодовых символов, выбираемых из конечного множества различных (отличающихся друг от друга) элементарных кодовых символов a, (i = 1,2,3,т). Применяя приемлемый способ кодирования, можно в той или иной степени согласовать дискретный источник с каналом связи.

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

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

При помехоустойчивом кодировании чаще всего считают, что избыточность источника на входе кодера р_и = 0. Дш этого имеются следующие основания: во-первых, очень многие дискретные источники (например, информация на выходе многих ЭВМ) обладают малой избыточностью; во-вторых, если избыточность первичных источников существенна, она обычно порождается сложными связями, которые в месте приема затруднительно использовать для повышения верности. Поэтому в таких случаях разумно сначала, но возможности, уменьшить избыточность первичного источника, а затем методами помехоустойчивого кодирования внести в сигнал такую избыточность, которая позволяет достаточно простыми средствами поднять верность. Из сказанного следует, что экономное кодирование вполне может сочетаться с помехоустойчивым.

Теория кодирования за последние годы развивалась весьма интенсивно на основе современных математических методов. В данной главе затронуты лишь общие принципы теории кодирования. Вопросы построения используемых на практике кодов, а также технической реализации кодирующих и декодирующих устройств рассматриваются в специальных курсах. Коды можно классифицировать по весьма различным признакам. Одним из основных является основание кода т или число различных используемых в нем символов. Наиболее простыми являются двоичные (бинарные) коды, у которых т = 2. Коды с т > 2 называют многопозиционными. Представляют интерес в основном двоичные коды, нашедшие широкое применение на практике.

Далее коды можно разделить на блочные и непрерывные. Блочными называют коды, в которых каждый элемент («буква») сообщения а_к(к = 1,2, 3,…, К) преобразуется в определенную последовательность (блок) кодовых символов {Ь;}, называемую кодовой комбинацией b_k{k = 1, 2, 3, …, К). Непрерывные коды образуют последовательность символов {Ъ,}, неразделяемую на последовательные кодовые комбинации: здесь в процессе кодирования символы определяются не одним, а целой группой элементов сообщения.

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

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

Если объем (число возможных элементов — букв) алфавита источника сообщений равен К, то каждую букву можно закодировать с помощью /?-разрядного равномерного кода с основанием т при Если в предыдущей формуле имеет место равенство, т. е. все возможные кодовые комбинации используются для передачи сообщений, то в этом случае код называется безызбыточным или примитивным. Если же число возможных кодовых комбинаций больше числа различных букв и, следовательно, часть из них можно не задействовать при передаче сообщений, код называется избыточным или корректирующим. Избыточность кода р_н (сигнала на выходе кодера) можно оценить формулой:

Полагая избыточность источника на входе кодера р_и = О, а m-позиционный код равномерным длиной п, можно написать следующую формулу для избыточности кода:

При кодировании удобно совокупность элементов (букв) источника сообщений а_к представить совокупностью чисел: 0, 1,2, 3, 4,.

К — 1 (К — объем алфавита источника).

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

где а" — коэффициенты, принимающие при отдельных разрядах числа М значения 0, 1, …, т — 1. Число разрядов п, которое необходимо удержать в выражении, зависит от объема (числа уровней) источника К и от позиционности (основания) системы счисления (кода) п.

В системе счисления число 59 запишется следующим образом:

— в десятичной (код с основанием 10).

M=59 = 5−10'+9−10°;

— в четверичной (код с основанием 4).

М= 59 = 3−4² + 2−4' + 3−4°.

в двоичной (код с основанием 2).

М= 59= 1−2⁵+ 1−2⁴+ 1*2³+ 0*2²+ 1−2‘+ 1−2°.

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

Рис. 5.3. Сигналы кодовой последовательности: а — при десятипозиционном двухразрядном коде; б — при четырехпозиционном трехразрядном коде; в — при двухпозиционном шестиразрядном коде Всякий блочный код можно представить в виде таблицы, в которой каждой букве (цифре) алфавита источника сопоставляется определенная кодовая комбинация.

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

Помимо представления таблицей, код очень часто представляют графически с помощью так называемого «кодового дерева».

Рассмотрим построение кодового дерева для наиболее простого и распространенного двоичного кода, для чего, начиная с определенной точки («корня»), будем проводить отрезки прямой (ветви), наклоненные влево или вправо, если кодовым символом является соответственно «О» или «1». На рис. 5.4 построено «кодовое дерево» дня двоичного кода из табл. 5.1. На вершинах этого дерева написаны буквы алфавита источника, соответствующие данным кодовым комбинациям. Обратим внимание на то, что здесь каждой букве соответствует своя вершина «кодового дерева», с помощью которого можно однозначно декодировать любую последовательность символов, если только она принята с самого начала. Это справедливо для любого равномерного кода.

Рис. 5.4. Кодовые деревья для кодов: а — равномерного; б — неравномерного приводимого; в — неравномерного неприводимого.

Рассмотрим теперь неравномерный двоичный код. Пусть он, например, задан «кодовым деревом». В данном случае некоторым буквам сообщения соответствуют нс вершины, а узловые точки дерева. Но тогда декодирование будет неоднозначным. Действительно, приняв в начале кодовой последовательности символ «О», не знаем, означает ли он букву «Б» или является началом кодовой комбинации, означающей буквы «Д» или «Е». Однако можно построить неравномерные коды, допускающие однозначное декодирование, для чего достаточно, чтобы в кодовом дереве всем буквам источника соответствовали бы только вершины. Тогда ни одна кодовая комбинация не будет являться началом другой, более длительной комбинации.

Таблица 5.1

Рассмотрим теперь свойства кодов без избыточности и прежде всего равномерного безызбыточного кода. Такой код, особенно двоичный, широко применяется в дискретных системах связи. Основные его достоинства — простота кодирования и декодирования. Пусть дискретный источник объема К выдает v_H «букв» в секунду и характеризуется энтропией Н (А). Тогда его производительность.

Равенство имеет место только тогда, когда «буквы» выбираются источником с равными вероятностями и независимо друг от друга. Если считать, что в канале связи нет помех (все символы принимаются безошибочно) и он позволяет передавать н_к символов в секунду, то пропускная способность такого канала

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

В примитивном коде всякая кодовая комбинация соответствует определенной «букве». Если хотя бы один из символов, образующих кодовую комбинацию, будет принят ошибочно, то будет регистрироваться кодовая комбинация, соответствующая другой «букве» сообщения. Таким образом, вероятность ошибочного приема кодовой комбинации (буквы).

При р₀ «1, воспользовавшись формулой бинома Ньютона, имеем.

Следовательно, используя примитивный код в канале с помехами, принципиально нельзя обеспечить сколько угодно малую вероятность ошибки, о которой говорится в основной теореме К. Шеннона. Такой код применяется в канале с помехами, если достигаемая вероятность ошибочного приема «буквы» не превышает допустимой для данной системы связи величины.

Видно, что примитивный равномерный код не может обеспечить эффективного согласования источника с избыточност ью с каналом связи. Для каналов без помех кодирование, которое позволило бы приблизиться к предельному соотношению, может быть достигнуто при использовании неравномерного кода, длительность кодовых комбинации которого должна быть согласована с вероятностью выбора источником отдельных букв (первичных «символов»). Такое кодирование называют статистическим.

Неравномерный код при статистическом кодировании выбирается так, чтобы вероятные буквы передавались с помощью более коротких кодовых комбинаций, а менее вероятные — при помощи более длинных комбинаций кода. В итоге уменьшается средняя длина кодовой комбинации по сравнению со случаем равномерного кодирования и необходимая пропускная способность канала.

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

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

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

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