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

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

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

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

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

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

                                                                                                              Таблица 2

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

 

Буква	P( λi )	Код
а	0.6	1
б	0.2	011
в	0.1	110
г	0.04	101
д	0.025	1001
е	0.015	10001
ж	0.01	100001
3	0.01	110000

       Однако если, например, принята последовательность (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, т.е. имеется группа семиразрядных двоичных чисел. Среди этих чисел можно выделить следующие шестнадцать, которые удовлетворяют всем аксиомам группы, т.е. образуют подгруппу

 

k	п-k	k	п-k	k	п-k
0001	011	0111	010	1101	001
0010	110	1000	101	1110	100
0011	101	1001	110	1111	111
0100	111	1010	011	0000.	000.
0101	100	1011	000
0110	001	1100	010

 

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