Кодирование инф. Курс лекций по темам раздела Кодирование информации, методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки
 Скачать 1.18 Mb.
|
|
безусловно обратимое кодирование, в случае которого обратное преобразование не требует знания какой-то дополнительной информации. В подавляющем большинстве случаев для хранения паролей к внешним ресурсам используется именно этот способ. К примеру, почтовому клиенту для получения почты необходимо передать на РОР3-сервер логин и пароль пользователя, который решил доверить их хранение клиенту, поставив соответствующую галочку. Пароль уходит на сервер в открытом виде, какие-то дополнительные пароли при его сохранении взять неоткуда 17 (бессмысленно требовать от пользователя какой-то дополнительный пароль, если он захотел избавиться от ввода основного пароля). В этом случае единственный вариант - использовать как можно более запутанные алгоритмы кодирования и декодирования, которые обеспечат относительную защиту данных. Запишем условие обратимости кодирования в формализованном (математическом) виде. Введем некоторые обозначения: • Пусть I 1 – это количество информации в исходном сообщении, состоящем из символов первичного алфавита А. • Пусть I 2 – это количество информации в том же сообщении, записанном с помощью символов вторичного алфавита В, т.е. количество информации в сообщении после кодирования. Тогда условие обратимости кодирования запишется в следующем виде: I 1 ≤ I 2 На практике при построении обратимого кода необходимо придерживаться следующих правил: • разным символам первичного алфавита А должны быть сопоставлены разные кодовые комбинации; • никакая кодовая комбинация не должна составлять начальную часть какой-нибудь другой кодовой комбинации. Вопросы для самопроверки: 1. Является ли обратимым кодирование при помощи азбуки Морзе? 18 2. Классифицируйте кодирование информации на дорожных знаках с точки зрения его обратимости. 3. Определите возможный код символа «Г» в первичном алфавите {«А», «Б», «В», «Г»}, если в качестве вторичного алфавита используется двоичный алфавит и известны следующие коды: «А» - 00, «Б» - 010, «В» - 101. Код. Средняя длина кода. Относительная избыточность кода. При ответе на этот вопрос необходимо дать определение средней длины кода, рассказать об относительной избыточности кода и записать ее математическую формулу. Условие обратимости кодирования имеет вид: I 1 ≤ I 2 , Здесь I 1 – это количество информации в исходном сообщении, состоящем из n знаков первичного алфавита А, а I 2 – это количество информации в том же сообщении, записанном с помощью m знаков вторичного алфавита В. Будем считать, что символы появляются на выходе источника независимо друг от друга. Тогда полученное соотношение можно переписать: nI A ≤ mI B , Здесь I A – информационный вес одного символа в алфавите А, а I B – количество информации, приходящейся на один символ вторичного алфавита В. Проведем дальнейшие преобразования условия 19 обратимости кодирования. Отношение m n ≥ I A I B характеризует среднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита. Частота каждого символа в любом сообщении бесконечной длины будет одинаковой и будет стремиться к вероятности появления этого символа на выходе источника. Средняя длина кода для некоторого источника, первичного алфавита А, состоящего из N символов, вторичного алфавита В и кода φ определяется как сумма произведений длины кода символа первичного алфавита на соответствующую вероятность появления этого символа в сообщении: K ℘ ,A,B = ∑ i=1 N n i p i Здесь n i – это длина кодового слова для i-го символа первичного алфавита, p i — вероятность появления i-го символа на выходе источника. Если предположить постоянство поведения источника сообщений во времени, то предел отношения числа знаков вторичного алфавита к числу знаков первичного алфавита, кодирующих одно и то же сообщение, длина которого стремится к бесконечности, будет стремиться к средней длине кода: Здесь l i (n) – количество i-х символов первичного алфавита в произвольном сообщении, длина n которого стремится к бесконечности. Длину кодового слова, кодирующего i-ый символ 20 lim n ∞ m n = lim n ∞ ∑ i =1 N n i l i n n = = ∑ i=1 N n i lim n∞ l i n n = ∑ i=1 N n i p i = K , A , B первичного алфавита, мы обозначили через n i . Так как nI A ≤ mI B , минимально возможное значение длины кода будет: K min ℘ ,A,B = I A I B В качестве меры превышения длины кода будем использовать относительную избыточность кода. Относительной избыточностью кода назовем величину Q ℘ ,A,B = K ℘ ,A,B − K min ℘ ,A,B K min ℘ ,A,B Относительная избыточность кода показывает насколько операция кодирования увеличивает длину сообщения по отношению к первоначальной. Достаточно часто эту величину выражают в процентах. Так, если относительная избыточность некоторого кода равна 10%, то это означает, что при данном способе кодирования мы будем вынуждены передавать по каналу связи на 10% больше информации, чем содержится в исходном сообщении. Вопросы для самопроверки: 1. Определите среднюю длину кода для символов первичного алфавита {«А», «Б», «В», «Г»}, если при кодировании получены следующие коды этих символов: «А»- 0, «Б»- 10, «В»- 110, «Г»- 111. 2. Определите минимально возможную длину кода при двоичном кодировании символов первичного алфавита {«А», «Б», «В», «Г»} с известными вероятностями появления символов { 0,45; 0,15; 0,05; 0,35}. 21 3. Определите относительную избыточность кода задания 1 с учетом вычисленной в задании 2 минимально возможной длины кода. Асимптотически оптимальный код. Первая теорема Шеннона. При ответе на этот вопрос необходимо дать определение асимптотически оптимального кода и рассказать о практических способах его построения, сформулировать основную теорему о кодировании при отсутствии шумов как для общего случая, так и для случая двоичного кодирования. Для фиксированного первичного алфавита А и фиксированного вторичного алфавита В существует множество различных способов построения кода, ставящего символам из алфавита А символы или комбинации символов алфавита В. Относительная избыточность кода – характеристика кода, показывающая, во сколько раз требуется удлинить сообщение, чтобы обеспечить его надежную (безошибочную) передачу или хранение. Для разных вариантов построения относительная избыточность кода тоже может быть различной. Кроме того ресурсы (машинная память, время работы), необходимые для кодирования/декодирования разных кодов могут быть различны. Возникает вопрос: «Какой же из построенных кодов лучше? Какой код является более оптимальным?» Для некоторого первичного алфавита А и вторичного алфавита В асимптотически оптимальным кодом будем называть такой способ кодирования, при котором избыточность кодирования стремится к нулю, если длина сообщений стремится к бесконечности. Насколько хороший код можно построить? На этот вопрос 22 дает ответ первая теорема Шеннона (основная теорема о кодировании при отсутствии шумов): При отсутствии шумов всегда возможен такой вариант кодирования сообщения, при котором относительная избыточность кода будет сколь угодно близка к нулю. Теорема Шеннона не указывает конкретного способа кодирования, но из нее следует, что при выборе каждого символа кодовой комбинации необходимо стараться, чтобы он нес максимальную информацию. По определению K min ℘ ,A,B = I A I B . Известно, что сообщения, записанные символами первичного алфавита генерируются некоторым источником S, который характеризуется вероятностями появления отдельных символов алфавита А на выходе источника. Из этого следует, что уменьшить K min можно либо уменьшив числитель I А , либо увеличив знаменатель I B . Уменьшения информационного веса символа алфавита А можно достичь, если учесть различие частот появления символов первичного алфавита. Увеличить информационный вес символов алфавита В можно используя такой способ кодирования, при котором появление знаков вторичного алфавита было бы равновероятным, то есть I B = log 2 | В |. Будем учитывать различные вероятности появления отличных символов первичного алфавита на выходе источника, считая при этом, что корреляций между символами, генерируемыми источником нет. То есть, источник не запоминает, какие символы он уже выдавал, и генерирует новые символы независимо от прошлого. Такие источники называют источниками без памяти. Тогда, минимальное значение средней длины кода можно записать следующим образом: 23 K min ℘ ,A,B = I A log 2 B На практике почти повсеместно в цифровой технике используется двоичное кодирование, то есть |B| = 2, а сам вторичный алфавит В состоит из нуля и единицы (В = {0, 1}). Такое кодирование проще всего реализовать. Например, информацию можно хранить как последовательность намагниченных или не намагниченных участков жесткого диска. Нетрудно видеть, что в этом случае имеем: K min ℘ ,A, 2 = I A log 2 2 =I A Таким образом, для двоичного кодирования первая теорема Шеннона может быть переформулирована. Теорема Шеннона для двоичного кодирования: При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на один символ первичного алфавита. Формула относительной избыточности кодирования в случае двоичного кода принимает вид: Q ℘ ,A,2 = K ℘ ,A,2 I A − 1 Вопросы для самопроверки: 1. Сформулируйте основную теорему кодирования при отсутствии шумов. 2. Влияет ли наличие шумов в канале связи на значение относительной избыточности кода? 3. Определите в каком случае для символов первичного 24 алфавита {«А», «Б», «В», «Г»}, обладающих одинаковой частотой появления, будет получен более оптимальный код: а) в качестве вторичного алфавита выбран двоичный алфавит; б) в качестве вторичного алфавита выбран алфавит троичных цифр. Классификация способов кодирования. При ответе на этот вопрос необходимо произвести классификацию способов кодирования по различным критериям, привести примеры различных видов кода, дать сравнительную оценку различных способов кодирования в рамках одного критерия. Существует множество способов классификации способов кодирования. Критерий классификации: Условие построения кодовых комбинаций По условию построения кодовых комбинаций коды делят на равномерные и неравномерные. В равномерных кодах все сообщения передаются кодовыми группами с одинаковым числом элементов (длина кода n = const). Примером такого кода может служить телеграфный код Бодо, который является равномерным пятибитным кодом (n=5). Первоначально код, разработанный Эмилем Бодо (1845 -1903) в 1870 году для своего телеграфа, вводился прямо клавиатурой, состоящей из пяти клавиш, нажатие или ненажатие клавиши соответствовало передаче или непередаче одного бита в пятибитном коде. В 1901 году Дональд Мюррей (1866 - 1945) переработал код, изменил порядок знаков и добавил некоторые дополнительные знаки, адаптировав код Бодо к раскладке современной клавиатуры 25 QWERTY. Однако общие принципы — пятибитная кодировка и использование буквенного и цифрового регистров — остались неизменными (см. Приложение 1). При использовании неравномерных кодов разные сообщения могут передаваться кодовыми группами, содержащими неодинаковое число элементов (n = var). Типичным представителем неравномерного кода является код Морзе, созданный в 1838 году Самюэлем Морзе и подвергавшийся впоследствии неоднократным изменениям. В настоящее время кодом Морзе называют способ знакового кодирования, в котором для представления букв алфавита, цифр, знаков препинания и других символов используется последовательность троичных сигналов, например, длинных и коротких: «тире» и «точек» (см. рис. 4). За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между элементами одного знака — одна точка, между знаками в слове — три точки, между словами — семь точек. Равномерный код обладает большими возможностями с точки зрения обеспечения помехозащищенности передачи, так как потеря элементов или возникновение новых элементов в кодовых комбинациях с п = const могут быть легко обнаружены. Неравномерные коды могут обеспечить наибольшую экономичность построения кодов и наибольшее быстродействие передачи сообщений. Такие коды используются при так называемом статистическом кодировании. Вместе с тем неравномерные коды менее помехозащищенные, чем равномерные. Потеря или возникновение новых элементов в комбинации в результате действия помех могут привести к созданию новой ложной комбинации, воспринимаемой на приемной стороне как истинная. Неравномерные коды требуют 26 при передаче либо специальных разделительных символов, указывающих конец одной и начало другой кодовой комбинации (например, код Морзе требует наличия разделительного символа), либо же должны строиться так, чтобы никакая кодовая комбинация не явилась началом другой. Критерий классификации: Число различных символов в кодовых комбинациях (значность кода) По числу уникальных символов, используемых в кодовых комбинациях различают единичные, двоичные и многопозиционные коды. В единичном коде используются одинаковые символы. Кодовые комбинации отличаются друг от друга лишь количеством символов (импульсов). Такие коды называют еще числоимпульсными. Единичные коды используются в машине Поста (для кодирования целых положительных чисел), машине Тьюринга, в цифровых электронных счетчиках, в которых измеряемая величина преобразуется в пропорциональное ей число импульсов. Единичный код отличается своей простотой. Однако вследствие того, что он неравномерен, помехозащищенность его низкая. Кроме того, при передаче большого количества сообщений происходит изменение в широких пределах длины кода, что вызывает определенные неудобства. В связи с этим единичный код практически не используется для передачи информации по каналу связи, а используется лишь при промежуточных преобразованиях сигналов на передающей и приемной сторонах. Наибольшее распространение получили двоичные коды. Это обусловлено следующим. Формирование кодовых сигналов и их дешифрация производятся с помощью релейных устройств, 27 способных занимать ряд устойчивых состояний. Количество таких состояний определяется основанием кода. Очевидно, что простейшими релейными устройствами являются устройства с двумя состояниями. К такого типа устройствам принадлежит большинство электромагнитных, электронных, магнитных и других типов бесконтактных реле. Кроме того, следует также учитывать простоту хранения информации и выполнения арифметических и логических операций при двоичном кодировании. Многопозиционные коды, алфавит которых состоит из большого числа символов, пока не нашли широкого применения в информационных системах. Критерий классификации: Форма представления в канале передачи данных По форме представления сигнала в канале передачи данных различают последовательные и параллельные коды. В последовательных кодах элементарные сигналы, составляющие кодовую комбинацию, посылаются в канале передачи последовательно во времени. Как правило, они разделены между собой определенным временным интервалом. В параллельных кодах элементарные сигналы посылаются одновременно по нескольким электрическим цепям, число которых соответствует количеству элементов кода. Параллельная форма представления кода, хотя и связана с меньшей затратой времени для передачи сообщений, используется для передачи информации по каналу связи редко, так как требует значительных материальных затрат на многопроводные линии связи. Практически параллельная форма кода при передаче информации по однопроводной линии связи используется лишь в тех случаях, когда в качестве импульсного признака применяется частота и на приемной стороне элементы 28 кодовой комбинации можно легко разделить с помощью частотных фильтров. Параллельная форма представления кода часто используется при преобразовании аналоговых величин в код и обратных преобразованиях, в устройствах памяти, регистрации, при логической и математической обработке информации, когда важную роль играет быстродействие. Критерий классификации: |