Введение в теорию кодирования информации

 

     ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ ИНФОРМАЦИИ

 

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

    Код (от лат. сodех — свод законов) есть совокупность условных сигналов, обозначающих дискретные сообщения.

    Кодовая последовательность (комбинация) - представление дискретного сигнала.

Целью кодирования сообщений обычно являются:

• передача по общему каналу связи  нескольких или многих сообщений  для кодового разделения сигналов;

• повышение помехоустойчивости и  достоверности передачи сообщений;

• более экономное использование  полосы частот канала связи, т.е. уменьшение избыточности;

• уменьшение стоимости передачи и хранения сообщений;

• обеспечение скрытности передачи и хранения информации;

• преобразование любой  информации независимо от ее происхождения  и назначения в единую систему  символов;

• приведение исходных символов в  соответствие с характеристиками канала связи.

 

               Обобщенна модель канала передачи информации

    В самом общем виде модель канала передачи информации можно представить следующим образом  рис.1

 

     

          Рис. 1. Общее представление модели канала передачи информации

 

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

Значительно более полной в этом смысле является классическая модель канала передачи (хранения, обработки, распределения) информации, подобная приведенной  на рис. 2.

Кратко охарактеризуем назначение и функции элементов  этой модели.

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

    Само сообщение - это значение или изменение некоторой физической величины, отражающие состояние объекта (системы или явления).

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

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

     Под эффективностью в данном случае понимается степень сокращения объема данных, обеспечиваемая кодированием.

 

 

               Рис.2. Классическая модель канала передачи, хранения, обработки и   распределения информации

 

Криптографический кодер выполняет  криптографическое кодирование (шифрование) для обеспечения секретности передачи информации.

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

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

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

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

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

    Криптографический декодер выполняет декодирование зашифрованной информации по специальным алгоритмам.

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

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

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

 

          Количественная оценка информации, энтропия источника                 сообщений

 

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

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

     Рассмотрим источник, выдающий последовательность независимых дискретных сообщений { λ_i }, каждое из которых случайным образом (выбирают из алфавита сообщения А (λ_i) = λ_1, λ_2, λ_3,… λ_n, где - размер алфавита источника. Такой источник будем называть источником без памяти с конечным дискретным алфавитом. Сообщения, вырабатываемые таким источником, называются простыми сообщениями. В каждом элементарном сообщении λ_i для его получателя содержится некоторая информация. Количество информации, содержащейся в элементарном сообщении λ_i,является некоторой функцией от вероятности передачи этого сообщения Р( λ_i ) и определяется

                                  J( λ_i )= a log P( λ_i )

при этом как коэффициент а, так и основание логарифма могут быть выбраны произвольно. Указанная мера была предложена Р. Хартли в 1928 г. для количественной оценки способности системы хранить или передавать информацию. Однако для удобства (чтобы количественная мера информации была положительной) принимают а = - 1. Если основание логарифма равно двум, то количество информации, содержащееся в элементарном сообщении, определяется

                                 J( λ_i )= - log2 P( λ_i )

 

     Определенная таким образом единица измерения информации называется двоичной единицей или битом информации.

     Количество информации, содержащееся в одном элементарном сообщении λ_i, еще никак не характеризует источник. Одни элементарные сообщения могут нести много информации, но передаваться очень редко, другие - передаваться чаще, но нести меньше информации. Поэтому источник может быть охарактеризован средним количеством информации, приходящимся на одно элементарное сообщение, носящим название «энтропия источника» и определяемым следующим образом

                                    _    k

                                 H(λ)=∑ P( λ_i )·log P( λ_i ),             i=1,K.

                                      i=1 

     Энтропия как количественная мера информативности источника обладает следующими свойствами:

      1. Энтропия есть величина вещественная, ограниченная и неотрицательная. Эти ее свойства вытекают из вида выражения для H( λ ), а также с учетом того, что 0 < P( λ_i ) < 1.

      2. Энтропия детерминированных сообщений равна нулю H( λ ) =0, если хотя бы одно из сообщений имеет вероятность, равную единице.

      3. Энтропия максимальна, если сообщения ( λ_i ) , равновероятны

 

                                P( λ₁ ) = P( λ₂)=........P( λ _к) =1/K,

Тогда

                                                    k

                               H( λ )= -1∕K∑  log 1∕K= logK                                               

                                                  i=1

      Как видно из последнего выражения, в случае равновероятных сообщений энтропия растет с увеличением объема алфавита источника (ростом числа сообщений). При неравновероятных элементарных сообщениях λ_i энтропия, соответственно, уменьшается.

      4. Энтропия двоичного источника (К = 2) может изменяться от нуля до единицы. Действительно, энтропия системы из двух сообщений λ₁ и λ₂

                               H( λ )= P( λ₁ ) ∙ log P( λ₁ ) - P( λ₂)∙ log P( λ₂)=

                              = - P( λ₁ ) ∙ log P( λ₁ )-{- P( λ₁ )} ∙ log{1- P( λ₁ )}.

 

      Из последнего выражения видно, что энтропия равна нулю при P( λ₁ )=0; P( λ₂)=1 или P( λ₁ )= 1;  P( λ₂)= 0; при этом максимум энтропии будет иметь место, когда P( λ₁ )= P( λ₂)=1/2 и ее максимальное значение будет равно 1бит.

 

 

                         Основы статистического кодирования

 

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

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

      Пример.

      Пусть вероятности появления в тексте различных букв будут разными (табл.1)

                                                                                                               Таблица 1

Вероятность появления  букв в сообщении

 

а	б	в	г	д	е	ж	3
Ра=0,6	Рб=0,2	Рв=0,1	Рг=0,04	Рд=0,025	Ре=0,015	Рж=0,01	Рз=0,01

                                                                                 _

     Энтропия источника в этом случае составит Н(λ)= 1,781

     Среднее число символов на одно сообщение при использовании

равномерного трехразрядного кода

                             _    k                            k

                            п =∑n ( λ_i )Р( λ_i ) = п∑Р(λ_i ) = п = 3.

                                   i=1                         i=1

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