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

СОДЕРЖАНИЕ

Введение…………………………………….....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)