Принципы кодирования информации

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

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

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

Объем алфавита определяет количество информации, доставляемой одним символом сообщения. Если алфавит имеет объем А и в любом месте в сообщении равновероятно появление любого символа, то доставляемое символом количество информации можно определить как I₀ =log₂ A (бит). В случае отсутствия равновероятности I₀ =- log₂ P, где Р - вероятность появления элемента сообщения.

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

Минимальной единицей объема информации является бит. Бит -символ двоичного алфавита, имеющего лишь два символа - 0 и 1. Один бит - это очень малый объем информации. Слова из 2 битов позволяют закодировать 4 состояния, 3 бита - 8 состояний. При помощи восьмиразрядного слова можно закодировать 256 различных символов (букв, цифр, знаков препинания и т.д.). 8 бит имеют специальное название - байт. Байт используется как основная единица измерения объема информации. Более крупными единицами объема информации являются килобайт, мегабайт, гигабайт, терабайт.

В теории кодирования выделяют:

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

* примитивное или безызбыточное кодирование, используемое для преобразование одного алфавита в другой с целью согласования, например, источника и канала. Примитивное кодирование используется также в целях шифрования передаваемой информации в так называемых скремблерах (от английского «scramble» - перемешивать);

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

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

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

Сжатие данных осуществляется либо на прикладной уровне с помощью программ сжатия, таких, как ARJ, либо с помощью устройств защиты от ошибок (УЗО) непосредственно в составе модемов по протоколам типа V.42bis.

Существует два основных метода архивации без потерь:

· алгоритм Хаффмана (англ. Huffman), ориентированный на сжатие последовательностей байт, не связанных между собой, Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный объем файла уменьшится.

· алгоритм Лемпеля-Зива (англ. Lempel, Ziv), ориентированный на сжатие любых видов текстов, то есть использующий факт неоднократного повторения "слов" – последовательностей байт. Он формулируется следующим образом: "если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность".

Практически все популярные программы архивации без потерь (ARJ, RAR, ZIP и т.п.) используют объединение этих двух методов – алгоритм LZH.

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

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

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

Поиск по сайту: