2.3.Кодирование информации

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

2.3.1.Оптимальное основание кода

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

Например для кодирования сигнала, уровень которого изменяется от 0 до 10 В, с погрешностью 10 мВ можно предложить различные варианты выбора и : 1) =1000, =1; 2) =2, =10 ( ) и т.д.

Для определения оптимальных значений и воспользуемся критерием минимума произведения .

Как было отмечено ранее , где - заданное число сообщений (число различных комбинаций сигнала). Логарифмируя, получим

Следовательно,

Используя формулу , получим

Условие минимума примет вид:

Воспользовавшись тождествами , , , , получим

.

Далее, используя тождество , окончательно получим

Из последнего тождества следует, что оптимальное значение Т.к. должно быть целое, то оптимальным значением является 3 или 2. На практике чаще используется основание кода .

2.3.2.Запись натурального числа в двоичной системе

Примером двоичного кода является запись натурального числа в позиционной системе счисления с основанием 2

Пусть - последовательность двоичных кодовых слов длины . Тогда рекурсивное определение последовательности кодовых слов в порядке двоичного счета будет следующее:

Наиболее прямым способом порождения данной последовательности кодовых слов является счет в системе счисления с основанием 2, что реализует алгоритм, представленный укрупненной блок-схемой на рис.2.2.

Укрупненная блок-схема показывает идеи алгоритма и не расскрывает многие детали реализации. В рассматриваемом алгоритме из укрупненной блок-схемы видно, что двоичные наборы длины n формируются в ячейках B[n-1],B[n-2],...,B[0], массива B. Ячейка B[n] массива B служит для организации завершения работы алгоритма. Ячейка B[n] принимает значение 1, когда все 2ⁿ наборов выданы. Также видно, что для реализации двоичного счета, т.е. для организации перехода от текущего кодового слова к следующему, используется простой прием:

• просматривается текущее кодовое слово в направлении от младшего разряда к старшему с целью поиска первого разряда, равного нулю (на укрупненной блок-схеме номер такого разряда сохраняется в переменной i);.

• найденному первому разряду, равному нулю, присваивается значение 1, а все «более младшие» разряды, значение которых равно 1, обнуляются.

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

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

Еще один способ порождения последовательности кодовых слов в порядке двоичного счета заключается в переборе всех целых чисел от 0 до 2ⁿ-1 и обращением двоичного представления каждого из чисел в набор (b_n-1,b_n-2,...,b₀). Обращение осуществляется с помощью битовых операций или с помощью операций целочисленного деления и получения остатка от деления.

Укрупненная блок схема алгоритма реализующего данный подход показана на рис.2.4.