Теоретические основы информатики

Теоретические основы информатики Основы теории кодирования Теория кодирования информации является одним из разделов теоретической информатики. К её основным задачам относятся следующие: • разработка принципов наиболее экономичного кодирования; • согласование параметров передаваемой информации с особенностями канала связи; • разработка приемов, обеспечивающих надёжность передачи информации по каналам связи, то есть отсутствие потерь. Для представления дискретной информации используется некоторый алфавит. Однозначное соответствие между информацией и алфавитом отсутствует. Другими словами, одна и та же информация может быть представлена посредством различных алфавитов. Поэтому возникает проблема перехода от одного алфавита к другому, причем без потерь информации. Алфавит, с помощью которого представляется информация до преобразования — первичный, алфавит конечного представления — вторичный. Введем ряд определений: Код — правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита, а также сами знаки вторичного алфавита. Кодирование — перевод информации, представленной посредством первичного алфавита, в последовательность кодов. Декодирование — операция, обратная кодированию, то есть восстановление информации в первичном алфавите по полученной последовательности кодов. Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо её потерь. Виды кодирования В зависимости от целей кодирования, различают следующие его виды: 1) Кодирование по образцу — каждый знак дискретного сигнала представляется знаком или набором знаков того алфавита, в котором выполняется кодирование. Используется, в частности, всякий раз для ввода информации в компьютер для ее внутреннего представления. 2) Эффективное (оптимальное) кодирование — для устранения избыточности данных путем снижения среднего числа символов кодового алфавита для представления одного исходного символа. Именно этот вид кодирования используется для сжатия. 3) Помехоустойчивое (помехозащитное) кодирование — для обеспечения заданной достоверности в случае, когда на сигнал накладывается помеха. Используется для защиты от помех при передаче информации по каналам связи. 4) Криптографическое кодирование (шифрование) — используется, когда нужно защитить информацию от несанкционированного доступа. Приведём математическую постановку задачи кодирования. Пусть первичный алфавит A содержит N знаков со средней информацией на знак, определённой с учетом вероятностей их появления, I1 ( A) (нижний индекс отражает то обстоятельство, что рассматривается первое приближение, а буква в скобках указывает алфавит). Вторичный алфавит B пусть содержит M знаков со средней информационной ёмкостью I1 ( B ) . Пусть также исходное сообщение, представленное в первичном алфавите, содержит n знаков, а закодированное сообщение — m знаков. Если исходное сообщение содержит I ( A) информации, а закодированное — I ( B ) , то условие обратимости кодирования, то есть неисчезновения информации при кодировании, очевидно, может быть записано следующим образом: I ( A)  I ( B ) . Смысл неравенства в том, что операция обратимого кодирования может увеличить количество формальной информации в сообщении, но не может его уменьшить. Каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднюю информационную емкость знака: N m I1 ( A)  I1 ( B ) , I1 ( A) = −  pi log 2 pi . n i =1 Отношение K ( B ) = m / n , очевидно, характеризует среднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита — будем называть его длиной кода. В частном случае, когда появление любых знаков вторичного алфавита равновероятно, согласно формуле Хартли I1 ( B ) = log 2 M , и тогда I 1 ( A)  K ( B) . log 2 M Введем относительную избыточность кода ( Q ): I ( A) I 1 ( A) . Q =1− =1− I ( B) K ( B ) I1 ( B ) Данная величина показывает, насколько операция кодирования увеличила длину исходного сообщения. Очевидно, чем меньше Q (то есть чем ближе она к 0 или, что тоже, I ( B ) ближе к I ( A) ), тем более выгодным оказывается код и более эффективной операция кодирования. Отметим, что на практике для оценки средней длины кода пользуются формулой из теории вероятностей: N K ( B ) =  pi ki , i =1 где ki — длина кода для символа с частотой pi . 2 Эффективное кодирование. Методы Шеннона-Фано, Хаффмана Для теории связи важнейшее значение имеет следующая теорема. Первая теорема Шеннона о передаче информации, которая называется также основной теоремой о кодировании при отсутствии помех, формулируется следующим образом: При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю. Важно, что теорема открывает принципиальную возможность оптимального кодирования. Однако необходимо сознавать, что из теоремы никоим образом не следует, как такое кодирование осуществить практически. С практической точки зрения наиболее просто реализуемый вариант – ситуация, когда M = 2 , то есть для представления кодов в линии связи используется лишь два типа сигналов. Подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать «0» и «1», но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации ( log 2 M = 1 ); тогда I1 ( A) = K (2) , и первая теорема Шеннона получает следующую интерпретацию: При отсутствии помех передачи средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита. Тогда формула избыточности для двоичного кодирования дает: I ( A) Q =1− 1 . K (2) Итак, первая теорема Шеннона открывает возможность эффективного кодирования. Рассмотрим подходы к построению эффективных кодов. Согласно теории информации Шеннона, количество получаемой с сообщением информации тем больше, чем неожиданнее данное сообщение. Этот тезис использован при эффективном кодировании кодами переменной длины: исходные символы, имеющие большую вероятность (или частоту), имеют код меньшей длины и наоборот. Таким образом, эффективное кодирование предполагает использование кодов разной длины — коротких для часто встречающихся символов и более длинных — для редких. Но в таком случае возникает проблема отделения кодов разных символов друг от друга — нужно знать, когда закончился один код и начался другой. Для этого можно вести специальный код-разделитель (например, в коде Морзе для этого используется пауза), но это понизит эффективность кода, так как увеличит его длину. Однако очевидно, что эффективность данного способа кодирования невелика. Легко заметить, что одной из причин 3 этого является присутствие в коде каждого символа «лишних» бит — разделителя, не несущего информации. Можно найти такой вариант кодирования сообщения, при котором последующее выделение из него каждого отдельного знака (то есть декодирование) оказывается однозначным без специальных указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условие Фано): Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом какого-либо иного более длинного кода. Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при прочтении (расшифровке) закодированного сообщения путём сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой. Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков. Однако условие Фано не устанавливает способа формирования префиксного кода и, в частности, наилучшего из возможных. Метод Шеннона-Фано Один из первых методов построения префиксных кодов. Для построения кода методом Шеннона-Фано можно использовать таблицу или кодовое дерево. Опишем процесс построения кода с помощью таблицы. Исходное множество символов упорядочивается по невозрастанию частот (вероятностей) их встречаемости в тексте, и выполняются следующие шаги. 1. Список символов делится на две части так, чтобы суммы частот обеих частей были точно или примерно равны. 2. Кодовым комбинациям первой части дописываются единицы, второй части — нули. 3. Если первая часть содержит только один символ, работа с ней заканчивается, и осуществляется переход к шагу 4, иначе — переход к шагу 1 и алгоритм применяется к первой части как к целому алфавиту. 4. Если вторая часть содержит только один символ, работа с ней заканчивается, и осуществляется переход к шагу 5, иначе — переход к шагу 1 и алгоритм применяется ко второй части как к целому алфавиту. 5. Если оставшийся список пуст (в каждой группе по одному символу) — код построен, работа алгоритма заканчивается. Иначе — выполняется шаг 1 для оставшейся группы символов. Рассмотрим пример. 4 Пусть даны символы с частотами f a = 0.3 ; a, b, c, d f b = 0.4 ; f c = 0.1 ; f d = 0.2 . Построим эффективный код методом ШеннонаФано. Процесс построения кода представлен в таблице. Исходные Частоты I II III Код fs символы s 0.4 1 1 b 0.3 1 01 a 0.2 1 001 d 0.1 000 c Метод Хаффмана Метод кодирования Хаффмана относится к префиксным кодам и является неулучшаемым, то есть невозможно построить префиксный код символьного кодирования с большей эффективностью. Опишем алгоритм кодирования Хаффмана. Исходное множество символов упорядочивается по невозрастанию частот (вероятностей) их встречаемости в тексте, и выполняются следующие шаги. 1. Объединение частот: • две последние (самые маленькие) частоты складываются, а соответствующие символы исключаются из списка; • оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается; • предыдущие шаги повторяются до тех пор, пока не получится единица в результате суммирования и список не уменьшится до одного символа. 2. Построение кодового дерева: • строится двоичное кодовое дерево: корнем его является вершина, равная 1; остальные вершины соответствуют либо суммарным, либо исходным частотам, причём для каждой вершины левая подчинённая вершина соответствует большему слагаемому, а правая — меньшему; • рёбра дерева кодируются: каждое левое кодируется единицей, каждое правое — нулем. 3. Формирование кода: для получения кодов листьев (исходных кодируемых символов) продвигаются от корня к нужной вершине и записывают веса проходимых ребер. Рассмотрим пример. Пусть даны символы с частотами f a = 0.3 ; a, b, c, d f b = 0.4 ; f c = 0.1 ; f d = 0.2 . Построим эффективный код методом Хаффмана. 5 1. Объединение частот. Исходные Частоты Этапы объединения fs первый второй третий символы s 0.4 0.4 0.6 1 b 0.3 0.3 0.4 a 0.2 0.3 d 0.1 c 2. Построение кодового дерева. 3. Формирование кода. 1 0; b: 11; a: 1 0.6 0.4 d : 101; 1 b 100. c: 0.3 a 0.3 1 0.2 d 6 c 0.1 Помехоустойчивое кодирование. Вторая теорема Шеннона. Код Хэмминга Под помехой понимается любое воздействие, накладывающееся на полезный сигнал и затрудняющее его прием. Кодирование, устойчивое к помехам, должно осуществляться так, чтобы сигнал, соответствующий принятой последовательности символов, после воздействия на него предполагаемой в канале помехи, оставался ближе к сигналу, соответствующему конкретной переданной последовательности символов, чем к сигналам, соответствующим другим возможным последовательностям. Это достигается ценой введения при кодировании избыточности, которая позволяет так выбрать передаваемые последовательности символов, чтобы они удовлетворяли дополнительным условиям, проверка которых на приемной стороне дает возможность обнаружить и исправить ошибки. Коды, обладающие таким свойством, получили название помехоустойчивых. Они используются как для исправления ошибок (корректирующие коды), так и для их обнаружения. Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных им в виде основной теоремы для дискретного канала с шумом (Вторая теорема Шеннона): при любой скорости передачи двоичных символов меньшей, чем пропускная способность канала, существует такой код, при котором вероятность ошибочного декодирования будет сколь угодно мала. Как видно, в теореме не затрагивается вопрос о путях построения кода, обеспечивающего указанную идеальную передачу. Тем не менее, значение ее огромно, поскольку, обосновав принципиальную возможность такого кодирования, она мобилизовала усилия ученых на разработку конкретных кодов. Код Хэмминга Код Хэмминга представляет собой один из важнейших классов помехоустойчивых кодов, нашедших широкое применение на практике и имеющих простой и удобный для технической реализации алгоритм обнаружения и исправления одиночной ошибки. Предположим, необходимо исправить одиночную ошибку двоичного кода. Такой код состоит из nи символов, несущих информацию, и nk контрольных (избыточных) символов. Всего символов в коде n = nи + nк . При передаче кода может быть искажен любой информационный символ. Однако может быть и такой вариант, что ни один из символов не будет искажен, то есть если всего в коде n символов, то с помощью контрольных символов, входящих в это число, должно быть создано такое n число комбинаций 2 к , чтобы свободно различить n + 1 вариант. 7 Поэтому nк должно удовлетворять неравенству 2 nк  n + 1 . Тогда 2 n = 2 nк +nи = 2 nк  2 nи , 2n  (n + 1)  2nи , где 2 n — полное число комбинаций кода. Следовательно, число информационных символов кода, обнаруживающего и корректирующего одиночную ошибку, может быть оценено из соотношения: 2 nи  2n . ( n + 1) Для вычисления основных параметров кода Хэмминга задается количество либо информационных символов, либо информационных комбинаций N = 2 nи . При помощи приведённых выше формул вычисляют n и nk . Зная основные параметры корректирующего кода, определяют, какие позиции сигналов будут рабочими, а какие — контрольными. Практика показала, что номера контрольных символов удобно выбирать по закону 2i , где i = 0,1, 2, 3, . Номера контрольных символов в этом случае равны 1, 2, 4, 8,…. Затем определяют значения контрольных коэффициентов 0001 a1 (0 или 1), руководствуясь следующим правилом: сумма единиц 0010 a2 на проверочных позициях должна быть чётной. Если эта сумма 0011 a3 чётна — значение контрольного коэффициента ноль, в 0100 a4 противном случае — единица. Проверочные позиции выбирают следующим образом. 0101 a5 0110 a6 Составляют таблицу для ряда натуральных чисел в двоичном коде. Число её строк n = nk + nи . Первой строке этой таблицы 0111 a7 соответствует проверочный коэффициент a1 , второй a2 и т.д. 1000 a8 Пример таблицы для определения проверочных позиций 1001 a9 при n = 11 приведён рядом. 1010 a10 Проверочные позиции выявляют, выписывая 1011 a11 коэффициенты по следующему принципу: в первую проверку входят коэффициенты, которые содержат единицу в младшем разряде ( a1 , a3 , a5 , a7 , a9 , a11 и т.д.); во вторую — во втором разряде ( a2 , a3 , a6 , a7 , a10 , a11 и т.д.); в третью — в третьем разряде и т.д. 8 Пример построения кода Хэмминга Пусть необходимо построить макет кода Хэмминга и определить значения корректирующих разрядов для кодовой комбинации ( nи = 4 ) 0101. Согласно полученной выше формуле минимальное число контрольных символов nк = 3 , при этом n = 7 . Контрольные коэффициенты будут расположены на позициях 1, 2, 4. Составим Позиция Кодовое слово макет корректирующего кода и запишем его во символов Макет Итог вторую колонку таблицы. K1 1 Пользуясь правилом о чётности K2 элементов в проверочных позициях, определим 2 1 значения коэффициентов K1 , K 2 и K 3 . 3 Первая проверка: сумма K3 4 П1 + П3 + П5 + П 7 должна быть четной, а сумма 5 1 1 K1 + 0 + 1 + 1 будет четной при K1 = 0 . 6 7 1 1 Вторая проверка: сумма П 2 + П3 + П6 + П7 должна быть четной, а сумма K 2 + 0 + 0 + 1 будет четной при K 2 = 1 . Третья проверка: сумма П 4 + П5 + П6 + П7 должна быть четной, а сумма K 3 + 1 + 0 + 1 будет четной при K 3 = 0 . Окончательное значение искомой комбинации корректирующего кода записываем в третью колонку таблицы. Обнаружение и исправление ошибок в коде Хэмминга Предположим, в канале связи под действием помех произошло искажение и вместо 0100101 было принято 0100111. Для обнаружения ошибки производят уже знакомые нам проверки на чётность. Первая проверка: сумма П1 + П3 + П5 + П7 = 0 + 0 + 1 + 1 четна. В младший разряд номера ошибочной позиции запишем 0. Вторая проверка: сумма П 2 + П3 + П6 + П7 = 1 + 0 + 1 + 1 нечетна. Во второй разряд номера ошибочной позиции запишем 1. Третья проверка: сумма П 4 + П5 + П6 + П7 = 0 + 1 + 1 + 1 нечетна. В третий разряд номера ошибочной позиции запишем 1. Получили двоичный номер ошибочной позиции: 1102 или 610. Следовательно, символ шестой позиции следует изменить на обратный, и получим правильную кодовую комбинацию. Если номер ошибочно позиции равен нулю — при передаче кода не было допущено ошибок. Построенный код позволяет обнаружить и исправить одиночную ошибку. 9