Кодирование информации. 2

СОДЕРЖАНИЕ

Введение…………………………………….....2

1. Кодирование информации…………………3

1. Задача кодирования……………………...3

2. Экономичное кодирование……………...8
3. Помехоустойчивое кодирование………16

2. Практическая реализация кодирования….22

1. Реализация программы кодирования

по методу Хаффмана………………………...22

2. Реализация программы – эмулятора

терминала азбуки Морзе…………………….28

Заключение…………………………………...32

Список литературы…………………………..33

Приложения…………………………………..34 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ

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

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

       Теоретической основой кодирования информации явились фундаментальные работы в области математической теории информации Клода Шеннона, а так  же Дэвида Хаффмана, Ричарда Хемминга и др.

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

       Объект  исследования: кодирование информации.

       Предмет исследования: основные алгоритмы экономичного и помехоустойчивого кодирования.

       Целью нашего исследования является изучение теоретических основ и процесса кодирования информации, формирования экономичных и помехоустойчивых кодов на примере алгоритмов Хемминга, Хаффмана и Шеннона – Фано.  
 
 
 
 

1. КОДИРОВАНИЕ ИНФОРМАЦИИ 
 

1. Задача кодирования

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

     Код –  правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита;[1; c.32] - знаки вторичного алфавита, используемые для представления знаков или их сочетаний первичного алфавита.

     Кодирование – перевод информации, представленной посредством первичного алфавита, в  последовательность кодов.

     Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном  алфавите по полученной последовательности кодов. [4;c. 190]

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

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

     Таким образом, кодирование предшествует передаче и хранению информации. [3, c. 50]

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

     Пусть первичный алфавит A содержит N знаков со средней информацией на знак, определенной с учетом вероятностей их появления, I₁^(A) (нижний индекс отражает то обстоятельство, что рассматривается первое приближение, а верхний индекс в скобках указывает алфавит). Вторичный алфавит B пусть содержит M знаков со средней информационной емкостью I₁^(B). Пусть также исходное сообщение, представленное в первичном алфавите, содержит n знаков, а закодированное сообщение – m знаков. Если исходное сообщение содержит I^(A) информации, а закодированное – I^(B), то условие обратимости кодирования, т.е. неисчезновения информации при кодировании, очевидно, может быть записано следующим образом: 

     I^(A) ≤ I^(B), 

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

     n*I₁^(A) ≤ m*I₁ ^(B),  

     или  

     I₁^(A) ≤ m/n*I₁ ^(B) 

     Отношение m/n, очевидно, характеризует среднее  число знаков вторичного алфавита, которое приходится использовать для  кодирования одного знака первичного алфавита – будем называть его  длиной кода или длиной кодовой цепочки и обозначим K^(B) (верхний индекс указывает алфавит кодов).

     В частном случае, когда появление  любых знаков вторичного алфавита равновероятно, согласно формуле Хартли I₁^(B)=log₂M, и тогда  

       I₁^(A) /log₂M≤ K^(B) (1) 

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

     Q= 1 – I^(A) / I^(B) = 1- I₁^(A) / K^(B)*I₁^(B) (2) 

     Данная  величина показывает, насколько операция кодирования увеличила длину  исходного сообщения. Очевидно, чем  меньше Q (т.е. чем ближе она к 0 или, что то же, I^(B) ближе к I^(A)), тем более выгодным оказывается код и более эффективной операция кодирования. Выгодность кодирования при передаче и хранении – это экономический фактор, поскольку более эффективный код позволяет затратить на передачу сообщения меньше энергии, а также времени и, соответственно, меньше занимать линию связи; при хранении используется меньше площади поверхности (объема) носителя. При этом следует сознавать, что выгодность кода не идентична временной выгодности всей цепочки кодирование – передача – декодирование; возможна ситуация, когда за использование эффективного кода при передаче придется расплачиваться тем, что операции кодирования и декодирования будут занимать больше времени и иных ресурсов (например, места в памяти технического устройства, если эти операции производятся с его помощью). [1; c. 34]

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

     При блочном кодировании слову из знаков внешнего алфавита ставиться  в соответствие кодовое слово  из знаков внутреннего алфавита.

     Cлова  из знаков внутреннего алфавита  В, сопоставленные словам из  знаков внешнего алфавита А  по правилу G, называются кодовыми комбинациями. Если ArE A и G(Ar)= Br, то говорят, что слову Ar соответствует кодовая комбинация Br. Совокупность кодовых комбинаций используемых для передач заданного количества дискретных сообщений называют кодовым словарем.

     Процесс, обратный кодированию, заключается в восстановлении из кодовой комбинации Br=b1b2…bmr слова Ar=a1a2…anr из входного алфавита и называется декодированием. Если процесс кодирования осуществляется с использованием правила G, то процесс декодирования основан на применении правила G-1, где G-1 есть отображение, обратное отображению G.

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

     Пусть Ar — слово в алфавите А и Br =G(Ar) — слово в алфавите В. Код называется обратимым, если для любого слова Br =G(Ar) в алфавите В существует единственное преобразование G-1(Br)= Ar . То есть, по слову Br в алфавите В, всегда однозначно восстанавливается слово Ar в алфавите А, из которого было образовано слово Br. [5; c. 14]

     Примером  обратимого кодирования является представление  знаков в телеграфном коде при  передаче сообщений и восстановление их при приеме.

     Примером  необратимого кодирования является перевод текста с одного естественного языка на другой. (Обратный перевод побуквенно обычно не соответствует исходному тексту.)

     Чтобы код был обратимым, необходимо:

     1) чтобы разным символам входного  алфавита А были сопоставлены  разные кодовые комбинации;

     2) чтобы никакая кодовая комбинация не составляла начальной части какой-нибудь другой кодовой комбинации.

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

     Итак, под кодированием в общем случае понимают преобразование алфавита сообщения A{ λ_i }, ( i = 1,2…K ) в алфавит некоторым образом выбранных кодовых символов Â{ x_j }, ( j = 1,2…N ). Обычно (но не обязательно) размер алфавита кодовых символов dim Â{ x_j } меньше или намного меньше размера алфавита источника dimA{ λ_i }.

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

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

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

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

2. Экономичное кодирование

      Впервые теоретическое исследование эффективного кодирования предпринял К. Шеннон.

     Прежде  чем перейти к вопросу экономного кодирования, кратко поясним суть самой процедуры кодирования.

     Любое дискретное сообщение l_i из алфавита источника A{ λ_i } объемом в K символов можно закодировать последовательностью соответствующим образом выбранных кодовых символов x_j из алфавита Â{x_j}.

     Например, любое число (а l_i можно считать числом) можно записать в заданной позиционной системе счисления следующим образом:

     l_i = M = x_n-1×m ^n-1 + x_n-2×m ^n-2 +… + x₀×m ⁰,        (1)

     где m - основание системы счисления; x₀ … x_n-1 - коэффициенты при степенях m; x Ì 0, m - 1.

     Пусть, к примеру, значение l_i = M = 59 , тогда его код по основанию m = 8, будет иметь вид

     M = 59 = 7·8¹ + 3·8⁰ =73₈ .

     Код того же числа, но по основанию m = 4 будет выглядеть следующим образом:

     M = 59 = 3×4² + 2×4¹+ 3×4⁰ = 323₄ .

     Наконец, если основание кода m = 2,  то

     M = 59 = 1×2⁵ + 1×2⁴ + 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 111011₂ .

     Таким образом, числа 73, 323 и 111011 можно считать, соответственно, восьмеричным, четверичным и двоичным кодами числа M = 59.

     В принципе основание кода может быть любым, однако наибольшее распространение  получили двоичные коды, или коды с основанием 2, для которых размер алфавита кодовых символов Â{ x_j } равен двум, x_j Ì 0,1. Двоичные коды, то есть коды, содержащие только нули и единицы, очень просто формируются и передаются по каналам связи и, главное, являются внутренним языком цифровых ЭВМ, то есть без всяких преобразований могут обрабатываться цифровыми средствами. Поэтому, когда речь идет о кодировании и кодах, чаще всего имеют в виду именно двоичные коды. В дальнейшем будем рассматривать в основном двоичное кодирование. [3, c. 51]

     Самым простым способом представления  или задания кодов являются кодовые  таблицы, ставящие в соответствие сообщениям l_i соответствующие им коды (табл. 1). 

     Таблица 1  

     Другим  наглядным и удобным  способом описания кодов  является их представление  в виде кодового дерева (рис..1).  

     Рис. 1 

     Для того, чтобы построить кодовое  дерево для данного кода, начиная  с некоторой точки - корня кодового дерева - проводятся ветви - 0 или 1. На вершинах кодового дерева находятся буквы алфавита источника, причем каждой букве соответствуют своя вершина и свой путь от корня к вершине. К примеру, букве А соответствует код 000, букве В – 010, букве Е – 101 и т.д.

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

     Равномерные коды очень широко используются в  силу своей простоты и удобства процедур кодирования-декодирования: каждой букве  – одинаковое число бит; принял заданное число бит – ищи в кодовой таблице соответствующую букву.

     Наряду  с равномерными кодами могут применяться  и неравномерные коды, когда каждая буква из алфавита источника кодируется различным числом символов, к примеру, А - 10, Б – 110, В – 1110 и т.д.

     Кодовое дерево для неравномерного кодирования  может выглядеть, например, так, как  показано на рис. 2. 

     Рис. 2 

     При использовании этого кода буква  А будет кодироваться, как 1, Б - как 0, В – как 11 и т.д. Однако можно  заметить, что, закодировав, к примеру, текст АББА = 1001 , мы не сможем его однозначно декодировать, поскольку такой же код дают фразы: ЖА = 1001, АЕА = 1001 и ГД = 1001. Такие коды, не обеспечивающие однозначного декодирования, называются приводимыми, или непрефиксными, кодами и не могут на практике применяться без специальных разделяющих символов. Примером применения такого типа кодов может служить азбука Морзе, в которой кроме точек и тире есть специальные символы разделения букв и слов. Но это уже не двоичный код.

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

     Рис..3 

     Прием и декодирование неравномерных  кодов - процедура гораздо более  сложная, нежели для равномерных. При этом усложняется аппаратура декодирования и синхронизации, поскольку поступление элементов сообщения (букв) становится нерегулярным. Так, к примеру, приняв первый 0, декодер должен посмотреть в кодовую таблицу и выяснить, какой букве соответствует принятая последовательность. Поскольку такой буквы нет, он должен ждать прихода следующего символа. Если следующим символом будет 1, тогда декодирование первой буквы завершится – это будет Б, если же вторым принятым символом снова будет 0, придется ждать третьего символа и т.д.

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

     Рассмотрим  пример кодирования сообщений l_i из алфавита объемом K = 8 с помощью произвольного n-разрядного двоичного кода.

     Пусть источник сообщения  выдает некоторый текст с алфавитом от А до З и одинаковой вероятностью букв Р(l_i ) = 1/8.

     Кодирующее  устройство кодирует эти буквы  равномерным трехразрядным кодом (см. табл. 1).

     Определим основные информационные характеристики источника с таким алфавитом:

     - энтропия источника    , ;

     - избыточность источника    ;

     - среднее число символов в коде   ;

     - избыточность кода    .

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

     Пусть теперь вероятности появления в  тексте различных букв будут разными (табл. 2). 

     Таблица 2

     Энтропия  источника  в этом случае, естественно, будет меньшей и составит _{= 1.781.}

     Среднее число символов на одно сообщение при  использовании того же равномерного трехразрядного кода

     Избыточность  кода в этом случае будет 

      ,

     или довольно значительной величиной (в  среднем 4 символа из 10 не несут никакой  информации).

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

     Такое кодирование называется статистическим.

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

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

     Таблица 3