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

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

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

    Код (от лат. с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

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

                                                                                 _

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

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

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

                             _    k                            k

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

                                   i=1                         i=1

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

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

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

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

    Согласно теореме Шеннона для кодирования сообщений из табл.1. может использоваться код, средняя длина которого п ≥ 1,781.

В табл. 2 представлен  один из возможных вариантов кодирования, где наиболее вероятным сообщениям присвоены наиболее короткие кодовые слова.

                                                                                                              Таблица 2

                       Произвольное кодирование сообщений

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

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

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

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

       Следует, еще раз отметить, что эффективное кодирование широко применяется в цифровой сотовой связи стандартов GSМ и СDМА, в системах цифрового спутникового телевидения, сети Intrnеt и др. цифровых радиотехнических системах.

                        Кодирование длин повторений

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

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

            Модели каналов передачи с криптографическим кодированием информации

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

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

Рис.3. Модель канала передачи с криптографическим кодированием

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

     Законный получатель, приняв криптограмму Е, декодирует (расшифровывает) ее с помощью обратного преобразования Sк ^-1  и получает исходное сообщение в виде открытого сообщения

                                           М: Sк (Е) = Sк ^-1 ( Sк (М)) = М.

     Преобразование Sк выбирается из семейства криптографических преобразований, называемых криптографической системой или общей системой.

     Параметр, выбираемый в качестве отдельного преобразования, называется криптографическим ключом или просто ключом. Общая система - это набор инструкций (часть аппаратуры или программа ЭВМ), с помощью которой можно закодировать открытый текст и декодировать шифрованный текст различными способами, один из которых выбирается с помощью конкретного ключа. Формально, криптографическая система - это однопараметрическое семейство обратимых преобразований кодирования Sк: М → Е из пространства М сообщений открытых данных в пространство Е (закодированных шифрованных сообщений). Причем ключ Ki выбирается из конечного множества К, называемого пространством ключей.

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

    Поскольку вся секретность сосредоточена в секретности ключа, то его надо передавать отправителю и получателю по защищенному каналу распространения ключей. На рис. 4.1 этот канал показан экранированной линией.

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

    •   симметричные (одноключевые) криптосистемы;

    •  асимметричные (двухключевые) криптосистемы (с открытым ключом).

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

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

                 Рис. 4. Обобщенная схема асимметричной криптосистемы

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

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

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

   Любая попытка со стороны перехватчика расшифровать криптограмму Е для получения открытого текста М или зашифровать свой собственный текст М' для получения приемлемой криптограммы Е' без получения ключа из канала распространения ключей называется криптоанализом.

                   Общие сведения о линейных кодах

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

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

Рассмотренный код позволяет  передать шестнадцать различных  сообщений. Из рассмотрения кодовых  слов можно видеть, что минимальное  расстояние Хэмминга dmin⁼3, т.е. код позволяет исправлять любую одиночную ошибку. Если передаваемые сообщения представляют собой k-разрядные двоичные числа, то групповой код всегда может быть построен таким образом, что эти сообщения будут являться первыми k символами кода, как это сделано для рассмотренного выше примера. Код, построенный таким образом, обозначается (п; k); иногда код обозначается как (n; k; d). Первое число в скобках показывает общее число символов в коде (длину кода), второе - число информационных символов, третье - кодовое расстояние кода. Для вышеприведенного примера обозначение кода будет таким: (7; 4; 3). Оставшиеся r=п-k символов называются проверочными. В групповых кодах проверочные символы образуются путем суммирования по модулю два символов, стоящих на определенных позициях кодового слова. Поскольку операция суммирования по модулю два является линейной, то коды, образованные таким образом, называются линейными. Для рассмотренного примера правила образования проверочных символов будут следующие