Файл: Методы кодирования данных.pdf

В зависимости от целей кодирования, различают следующие его виды:

- кодирование по образцу - используется всякий раз при вводе информации в компьютер для её внутреннего представления;

- криптофафическое кодирование, или шифрование, — используется, когда нужно защитить информацию от несанкционированного доступа;

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

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

Первая теорема Шеннона о передаче информации, называемая также основной теоремой о кодировании при отсутствии помех, формулируется таким образом:

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

Используя понятие избыточности кода, можно интерпретировать более короткую формулировку теоремы:

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

Данная теорема дает принципиальную возможность оптимального кодирования. Но она не дает представление, как такое кодирование осуществить на практике — для решения этой задачи необходимо применение иных соображений.^[[19]]

Далее в работе ограничимся ситуацией, когда М - 2, т.е. для представления кодов в линии связи используется лишь два типа сигналов - с практической точки зрения это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть это импульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать «О» и «1», но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log₂M=l); тогда из теоремы Шеннона:

I_i^(A) ≤ K ⁽²⁾

и первая теорема Шеннона получает следующую интерпретацию:

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

В двоичной системе кодирования:

Установление объема переданной информации при двоичном кодировании сводится к обычному подсчету числа импульсов (единиц) и пауз (нулей). В этом случае возникает проблема выделения из потока сигналов (последовательности импульсов и пауз) отдельных кодов. Приемное устройство фиксирует интенсивность и длительность сигналов. Элементарные сигналы (0 и 1) могут иметь одинаковые или разные длительности. Их количество в коде (длина кодовой цепочки), который ставится в соответствие знаку первичного алфавита, также может быть тождественным (в этом случае код называется равномерным) или разным (неравномерный код). Наконец, коды могут строиться для каждого знака исходного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов). В результате при кодировании (алфавитном и словесном) возможны следующие варианты сочетаний:

Табл. 2.3 Варианты сочетаний

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

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

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

3. Методы кодирования информации

Ранее средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения, но с появлением компьютеров ситуация радикально изменилась. К примеру десятичная позиционная система счисления — это универсальный способ кодирования чисел, в том числе натуральных. Римские цифры — другой способ кодирования небольших натуральных чисел, причём гораздо более наглядный и естественный: палец — I, пятерня — V, две пятерни — X. Однако при этом способе кодирования трудно выполнять арифметические операции над большими числами, поэтому он был вытеснен позиционной десятичной системой.^[[21]]

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

представление данных произвольной природы (например чисел, текста, графики) в памяти компьютера;

защита информации от несанкционированного доступа;

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

сжатие информации в базах данных.

Не ограничивая общности, задачу кодирования можно сформулировать следующим образом:

Пусть заданы алфавиты А = {a₁,... ,a_n}, В = {b₁,..., b_m} и функция F: А* → В*, причём Dom f = S, где S — некоторое множество слов в алфавите A, S А*. Тогда функция F называется кодированием, элементы множества S — сообщениями, а элементы = F(), S, В* — кодами (соответствующих сообщений). Обратная функция F^-1 (если она существует!) называется декодированием. Если |В| — m, то F называется m-ичным кодированием. Наиболее распространенный случай В = {0,1} — двоичное кодирование. Именно этот случай рассматривается в последующих разделах; слово «двоичное» опускается. Типичная задача теории кодирования формулируется следующим образом: при заданных алфавитах А, В и множестве сообщений S найти такое кодирование F, которое обладает определёнными свойствами (то есть удовлетворяет заданным ограничениям) и оптимально в некотором смысле. Критерий оптимальности, как правило, связан с минимизацией длин кодов. Свойства, которые требуются от кодирования, бывают самой разнообразной природы:

Существование декодирования, или однозначность кодирования: функция кодирования F обладает тем свойством, что ₁ ≠ ₂ => F(₁) ≠ (₂). Это очень естественное свойство, несмотря на это даже оно требуется не всегда. К примеру, трансляция программы на языке высокого уровня в машинные команды — это кодирование, для которого не требуется однозначного декодирования.

Помехоустойчивость, или исправление ошибок: продолжение функции декодирования F^-l обладает таким свойством, что F^-1() = F^-1( '), где ImF, В* \ Im F, если ' в определённом смысле близко к .

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

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

теоретико-множественное описание, например S={ | А* & | | = n };

вероятностное описание, например S = А*, и заданы вероятности p_i появления букв a_i в сообщении,

логико-комбинаторное описание, например S задано порождающей формальной грамматикой.^[22]

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

3.1. Алфавитное кодирование

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

Таблица кодов.

Алфавитное (или побуквенное) кодирование задается схемой (или таблицей кодов) :

( _{1 1},..., _{n n}), _i A, _i В*.

Множество кодов букв V {_i } называется множеством элементарных кодов (множеством кодовых слов). Алфавитное кодирование пригодно для любого множества сообщений S:

F: А* В*, _i1 .. ._1k = A*, F() _i1, ... _ik.

Рассмотрим алфавиты А: ={0,1,2,3,4,5, б, 7,8,9}, В: ={0,1} и схему

₁: = 0,1 1,2 10,3 11,4 100,5 101,6 110,7 111,8 1000,9> .

Эта схема однозначна, но кодирование не является взаимно-однозначным:

F₁ (333) = 111111 = F₁ (77),

а значит, декодирование невозможно. С другой стороны, схема

₂: = 0000,1 0001,2 0010,3 0011,4 0100,5 0101,6 0110,7 0111,8 1000,9> .

известная под названием «двоично-десятичное кодирование», допускает однозначное декодирование.

Разделимые схемы.^[[23]]

Рассмотрим схему алфавитного кодирования и различные слова, составленные из элементарных кодов. Схема называется разделимой, если

… = … => k = l & t 1…k (i₁…i_t),

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

Префиксные схемы.

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

Пример. Разделимая, но не префиксная схема:

A = {а,b}, В = {0,1}, = .

Неравенство Макмиллана.

Чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли определённому соотношению, известному как неравенство Макмиллана.

Азбука Морзе.^[[24]]

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

Этот код Морзе изобрел в 1838 г., т.е. задолго до исследований относительной частоты появления различных букв в текстах. Однако им был правильно выбран принцип кодирования — буквы с наибольшей частотой появления должны иметь более короткие коды, чтобы сократить совокупное время передачи. Относительные частоты букв английского алфавита он оценил простым подсчетом символов в ячейках типографской наборной машины. Поэтому самая распространенная английская буква «Е» получила код «точка». При составлении кодов Морзе для букв русского алфавита учёт относительной частоты появления букв не производился, что, конечно, повысило его избыточность. На подобии рассмотренных ранее вариантах кодирования, осуществим оценку избыточности. По-прежнему для удобства сопоставления данные представим в приведенном ниже формате. Признак конца буквы («0») в их кодах не отображается, но учтён в величине k_i, - длине кода буквы i.