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

Введение

Представленная курсовая работа посвящена теме: «Способы кодирования данных»

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

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

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

Глава 1. Теория кодирования данных

1.1 История возникновения.

Рассмотрим более подробно исторические этапы кодирования, обратимся к истории Древней Греции. В Древней Греции был историк Полибий, живший во втором веке до нашей эры. Он предложил кодировать буквы греческого алфавита различными наборами факелов. Самым первым способом символьной шифровки считается метод Гая Юлия Цезаря, который жил в первом веке до нашей эры. Он основывается на методе замены букв сообщения, подлежащего шифрованию, на другие, отстоящие в алфавите от шифруемой буквы на определённое число элементов. При этом алфавит может считываться по замкнутому кругу. Например, если взять слово «байт», то при сдвиге на две буквы вперёд получится код «гвлф». Процесс декодирования выполняется в обратном порядке. В 1791 году учёный Клод Шапп предложил использовать оптический семафор-телеграф. В нём разные положения планки семафора кодировали буквы алфавита. Оптический семафор К Шаппа и его телеграфный алфавит. Затем уже в 1832-33 годах русским физиком П.Л. Шиллингом и профессорами Гёттингенского университета Вебером и Гауссом было предложено кодировать буквы движением электромагнитной стрелки. Это был электромагнитный телеграф. И уже затем, как развитие этой идеи, в 1837 году появился наиболее сегодня известный телеграфный аппарат Морзе. В1861году был разработан международный код для передачи оптических сообщений с помощью двух флажков в руках человека. Изобрёл его морской капитан Фредерик Марьят, используя набор корабельных сигналов. Морская азбука сигнальных флажков. Далее, как развитие проводного телеграфа Морзе, был изобретён беспроводной радиотелеграф. Его независимо друг от друга изобрели А.С. Попов в 1895 году, и И. Маркони в 1897 году. Дальнейшим развитием коммуникаций и кодирования стал беспроволочный телефон и изобретение телевидения в 1935 году. Вскоре появились и электронные вычислительные машины, новые средства кодирования и связи двадцатого века. По сути, с этого началась новейшая эра информационного общества. Но вместе с необходимостью передачи информационных потоков, появилась и потребность сделать невозможным доступ к этой информации посторонних людей. Если вернуться назад в историю, то ещё в 1580 году Френсис Бэкон, так изложил основные необходимые моменты шифрования (кодирования) информации: Необходимо, чтобы шифр был достаточно прост в использовании. Шифрование должно быть надёжным и трудным для дешифрации посторонними. Шифровка должна быть скрытной и не подозрительной. Замечание 2 Кодирование по принципу Бэкона заключалось в использовании сочетания зашифрованного текстового сообщения с дезинформирующими символами, которыми были нули. То есть, двузначное шифрование применялось гораздо раньше появления электронных вычислительных машин. В 1948 году Клод Шеннон сформулировал теорию информации, что стало новым импульсом в развитии принципов кодирования. Мысли, приведённые им в работе «Математическая теория связи», стали теоретической базой анализа, транслирования и сохранения информационных данных. Итогом его научной работы стало создание и развитие устойчивых к помехам способов кодирования и возможности простого декодирования информации.

1.2 Основные понятия

Рассмотрим основные понятия, связанные с кодированием информации. Для передачи в канал связи сообщения преобразуются в сигналы. Символы, при помощи которых создаются сообщения, образуют первичный алфавит, при этом каждый символ характеризуется вероятностью его появления в сообщении. Каждому сообщению однозначно соответствует сигнал, представляющий определенную последовательность элементарных дискретных символов, называемых кодовыми комбинациями. Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации. Код - система соответствия между элементами сообщений и кодовыми комбинациями. Кодер- устройство, осуществляющее кодирование. Декодер - устройство, осуществляющее обратную операцию, т.е. преобразование кодовой комбинации в сообщение. Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) X = {x_i}, где i = 1, 2,..., m. Количество элементов кода - m называется его основанием. Для двоичного кода x_i = {0, 1} и m = 2. Конечная последовательность символов данного алфавита называется кодовой комбинацией (кодовым словом). Число элементов в кодовой комбинации - n называется значностью (длиной комбинации). Число различных кодовых комбинаций (N = mⁿ) называется объемом или мощностью кода.

Если N₀ - число сообщений источника, то N ³ N₀. Множество состояний кода должно покрывать множество состояний объекта. Полный равномерный n - значный код с основанием m содержит N = mⁿ кодовых комбинаций. Такой код называется примитивным.

1.3 Цели и задачи

Прежде  чем рассмотреть задачу кодирования, необходимо рассмотреть ряд определений, использующихся в теории кодирования:
     Код –правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита; - знаки вторичного алфавита, используемые для представления знаков или их сочетаний первичного алфавита. 
     Кодирование – перевод информации, представленной посредством первичного алфавита, в  последовательность кодов.
     Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном  алфавите по полученной последовательности кодов. 
     Операции  кодирования и декодирования  называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь. 
     Информационная  энтропия - в теории связи энтропия используется как мера неопределенности ожидаемого сообщения, т.е. энтропия источника  информации с независимыми сообщениями  есть среднее арифметическое количеств информации сообщений
     Примером  обратимого кодирования является представление  знаков в телеграфном коде и их восстановление после передачи. Примером кодирования необратимого может  служить перевод с одного естественного  языка на другой – обратный перевод, вообще говоря, не восстанавливает исходного текста. Безусловно, для практических задач, связанных со знаковым представлением информации, возможность восстановления информации по ее коду является необходимым условием применения кода, поэтому в дальнейшем изложении будет рассматриваться только обратимое кодирования. 
     Таким образом, кодирование предшествует передаче и хранению информации. При этом, как указывалось ранее, хранение связано с фиксацией некоторого состояния носителя информации, а передача – с изменением состояния с течением времени (т.е. процессом). Эти состояния или сигналы будем называть элементарными сигналами – именно их совокупность и составляет вторичный алфавит.
     Без технических сторон передачи и хранения сообщения (т.е. того, каким образом фактически реализованы передача-прием последовательности сигналов или фиксация состояний), математическая постановка задачи кодирования, дается следующим образом.
     Пусть первичный алфавит A содержит N знаков со средней информацией на знак, определенной с учетом вероятностей их появления, I₁^(A) (нижний индекс отражает то обстоятельство, что рассматривается первое приближение, а верхний индекс в скобках указывает алфавит). Вторичный алфавит B пусть содержит M знаков со средней информационной емкостью I₁^(A). Пусть также исходное сообщение, представленное в первичном алфавите, содержит n знаков, а закодированное сообщение – m знаков. Если исходное сообщение содержит I^(A) информации, а закодированное – I^(B), то условие обратимости кодирования, т.е. неисчезновения информации при кодировании, очевидно, может быть записано следующим образом: 

     I^(A) ? I^(B), 

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

     n*I₁^(A) ? n*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.Обеспечение экономичности передачи  информации посредством устранения  избыточности.
     2. Обеспечение надежности (помехоустойчивости) передачи информации
     3.Согласование скорости передачи  информации с пропускной способностью канала
     Соответствие  между элементами дискретных сообщений  и видом кодирования обеспечивается выбором:
     1. длительности сигналов 
     2. Длины кодового слова 
     3.Алфавита знаков и способа  кодирования (побуквенного, блочного)
     Полагается, что сообщение источника информации формируется из знаков аi, i=1,2,.. Na внешнего (входного, первичного) алфавита А объемом Na. Сообщения представляют собой слова, образованные последовательностью nr знаков: Ar =a1a2…anr. В кодирующем устройстве слово Ar преобразуется в кодовое слово Br=b1b2…bmr, составленное из mr знаков b_j, j=1,2,..Nb внутреннего (выходного, вторичного) алфавита В. Число знаков кодового алфавита называют основанием кода. Число знаков в кодовом слове называют длиной кодового слова. Отображение G множества слов в алфавите А на множество слов в алфавите В называют кодирующим отображением или кодом. Применение кодирующего отображения G к любому слову из входного алфавита называется кодированием. То есть код - это правило отображения знаков одного алфавита в знаки другого алфавита, кодирование – это преобразование одной формы сообщения в другую посредством указанного кода. 
     Различают побуквенное и блочное кодирование. При побуквенном кодировании  каждому знаку внешнего алфавита ставиться в соответствие кодовое слово из знаков внутреннего алфавита.
     При блочном кодировании слову из знаков внешнего алфавита ставиться  в соответствие кодовое слово  из знаков внутреннего алфавита.
     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.
     Примером  обратимого кодирования является представление  знаков в телеграфном коде при  передаче сообщений и восстановление их при приеме. 
     Примером  необратимого кодирования является перевод текста с одного естественного языка на другой. (Обратный перевод побуквенно обычно не соответствует исходному тексту.) 
     Чтобы код был обратимым, необходимо:
     1)чтобы разным символам входного  алфавита А были сопоставлены  разные кодовые комбинации;
     2)чтобы никакая кодовая комбинация  не составляла начальной части  какой-нибудь другой кодовой комбинации.
     Наиболее  простым правилом кодирования является сопоставление каждому символу  входного алфавита А слова конечной длины в выходном алфавите В. Код  может быть задан в форме таблицы, графа, аналитического выражения, то есть в тех же формах, что и отображение.
     Выражение пока следует воспринимать как  соотношение оценочного характера, из которого неясно, в какой степени  при кодировании возможно приближение к равенству его правой и левой частей. По этой причине для теории связи важнейшее значение имеют две теоремы, доказанные Шенноном. Первая – затрагивает ситуацию с кодированием при передаче сообщения по линии связи, в которой отсутствуют помехи, искажающие информацию. Вторая теорема относится к реальным линиям связи с помехами.

Глава 2. Способы кодирования данных

2.1 Классификация кодов

Коды можно классифицировать по различным признакам:

1. По основанию (количеству символов в алфавите): бинарные (двоичные m=2) и не бинарные (m ¹ 2).

2. По длине кодовых комбинаций (слов):

равномерные - если все кодовые комбинации имеют одинаковую длину;

неравномерные - если длина кодовой комбинации не постоянна.

3. По способу передачи:

последовательные и параллельные;

блочные - данные сначала помещаются в буфер, а потом передаются в канал и бинарные непрерывные.

4. По помехоустойчивости:

простые (примитивные, полные) - для передачи информации используют все возможные кодовые комбинации (без избыточности);

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

5. В зависимости от назначения и применения условно можно выделить следующие типы кодов:

Внутренние коды – это коды, используемые внутри устройств. Это машинные коды, а также коды, базирующиеся на использовании позиционных систем счисления (двоичный, десятичный, двоично-десятичный, восьмеричный, шестнадцатеричный и др.). Наиболее распространенным кодом в ЭВМ является двоичный код, который позволяет просто реализовать аппаратного устройства для хранения, обработки и передачи данных в двоичном коде. Он обеспечивает высокую надежность устройств и простоту выполнения операций над данными в двоичном коде. Двоичные данные, объединенные в группы по 4, образуют шестнадцатеричный код, который хорошо согласуется с архитектурой ЭВМ, работающей с данными кратными байту (8 бит).

Коды для обмена данными их передачи по каналам связи. Широкое распространение в ПК получил код ASCII (American Standard Code for Information Interchange). ASCII - это 7-битный код буквенно-цифровых и других символов. Поскольку ЭВМ работают с байтами, то 8-й разряд используется для синхронизации или проверки на четность, или расширения кода. В ЭВМ фирмы IBM используется расширенный двоично-десятичный код для обмена информацией EBCDIC (Extended Binary Coded Decimal Interchange Code).

В каналах связи широко используется телетайпный код МККТТ (международный консультативный комитет по телефонии и телеграфии) и его модификации (МТК и др.).

При кодировании информации для передачи по каналам связи, в том числе внутри аппаратным трактам, используются коды, обеспечивающие максимальную скорость передачи информации, за счет ее сжатия и устранения избыточности (например: коды Хаффмана и Шеннона-Фано), и коды обеспечивающие достоверность передачи данных, за счет введения избыточности в передаваемые сообщения (например: групповые коды, Хэмминга, циклические и их разновидности).

Коды для специальных применений - это коды, предназначенные для решения специальных задач передачи и обработки данных. Примерами таких кодов является циклический код Грея, который широко используется в АЦП угловых и линейных перемещений. Коды Фибоначчи используются для построения быстродействующих и помехоустойчивых АЦП.

2.2 Первая теорема Шеннона

 Ранее отмечалось, что при передаче сообщений  по каналам связи могут возникать  помехи, способные привести к искажению  принимаемых знаков. Так, например, если вы попытаетесь передать речевое сообщению в ветреную погоду человеку, находящемуся от вас на значительном расстоянии, то оно может быть сильно искажено такой помехой как ветер. Вообще, передача сообщений при наличии помех является серьезной теоретической и практической задачей. Ее значимость возрастает в связи с повсеместным внедрением компьютерных телекоммуникаций, в которых помехи неизбежны.
     При работе с кодированной информацией, искажаемой помехами, можно выделить следующие основные проблемы: установления самого факта того, что произошло искажение информации; выяснения того, в каком конкретно месте передаваемого текста это произошло; исправления ошибки – хотя бы с некоторой степенью достоверности.
     Помехи  в передачи информации - свойство отнюдь не только технических систем. Это - вполне обычное дело в быту. Пример был выше; другие примеры - разговор по телефону, в трубке которого "трещит", вождение автомобиля в тумане и т.д. Чаще всего человек вполне прилично справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большой избыточностью (в европейских языках - до 70%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение "в словох всо глосноо зомононо боквой о". Здесь 26% символов "поражены", однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством. 
     Например, каждый фрагмент текста ("предложение") передается трижды, и верным считается  та пара фрагментов, которая полностью  совпала. Однако, большая избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Отсюда следует задача устранения избыточности, или эффективного кодирования. Впервые теоретическое исследование такого рода проблем предпринял К.Шеннон.
     Первая  теорема Шеннона о передаче информации, которая называется также основной теоремой о кодировании при отсутствии помех, формулируется следующим  образом:
     При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак кодируемого алфавита, будет сколь угодно близко к отношению средних информаций на знак первичного и вторичного алфавитов. 
     Используя понятие избыточности кода, можно  дать более короткую формулировку теоремы: 
     При отсутствии помех передачи всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет  сколь угодно близкой к нулю. 
     Данные  утверждения являются теоремами  и, следовательно, должны доказываться, однако доказательства мы опустим. Для нас важно, что теорема открывает принципиальную возможность оптимального кодирования. Однако необходимо сознавать, что из самой теоремы никоим образом не следует, как такое кодирование осуществить практически – для этого должны привлекаться какие-то дополнительные соображения, что и станет предметом последующего обсуждения. 
     Таким образом, оптимальное кодирование  принципиально возможно.
     Наиболее  важна для практики ситуация, когда  М=2, то есть информацию кодируют лишь двумя  сигналами 0 и 1.
     Шенноном  была рассмотрена ситуация, когда  при кодировании сообщения в  первичном алфавите учитывается  различная вероятность появления  знаков, а также равная вероятность  появления знаков вторичного алфавита. Тогда: 

     К_min (А, В)= I ^(A) / log₂ M= I ^(A) , 

     здесь I ^(A) - средняя информация на знак первичного алфавита.
     Ограничим себя ситуацией, когда M = 2, т.е. для представления  кодов в линии связи используется лишь два типа сигналов – наиболее просто реализуемый вариант. Подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать "0" и "1. Удобство двоичных кодов и в том, что каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log₂M = 1); тогда из (1), теоремы Шеннона:  

     I₁^(A)? K⁽²⁾ 

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

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

 
     В случае использования неравномерного кодирования или сигналов разной длительности (ситуации (2), (3) и (4)) для отделения кода одного знака от другого между ними необходимо передавать специальный сигнал – временной разделитель (признак конца знака) или применять такие коды, которые оказываются уникальными, т.е. несовпадающими с частями других кодов. При равномерном кодировании одинаковыми по длительности сигналами (ситуация (1)) передачи специального разделителя не требуется, поскольку отделение одного кода от другого производится по общей длительности, которая для всех кодов оказывается одинаковой (или одинаковому числу бит при хранении). 
     Длительность  двоичного элементарного импульса показывает, сколько времени требуется  для передачи 1 бит информации. Очевидно, для передачи информации, в среднем приходящейся на знак первичного алфавита, необходимо время. Таким образом, задачу оптимизации кодирования можно сформулировать в иных терминах: построить такую систему кодирования, чтобы суммарная длительность кодов при передаче (или суммарное число кодов при хранении) данного сообщения была бы наименьшей.
     Если  имеется источник информации с энтропией  Н(х) и канал связи с пропускной способностью С, то если С > H(X), то всегда можно закодировать достаточно длинное сообщение таким образом, что оно будет передано без задержек. Если же, напротив, С < H(X), то передача информации без задержек невозможна. 
     Первая  теорема Шеннона декларирует возможность создания системы эффективного кодирования дискретных сообщений, у которой среднее количество двоичных символов на один символ сообщения асимптотически стремится к энтропии источника сообщений (в отсутствии помех).
     Первая  теорема Шеннона (переформулировка).
     При отсутствии помех средняя длина  двоичного кода может быть сколь  угодно близкой к средней информации, приходящейся на знак первичного алфавита.
     Какие же могут быть особенности вторичного алфавита при кодировании:
     Элементарные  коды 0 и 1 могут иметь одинаковые длительности (t0=t1) или разные (?).
     Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код)
     Коды  могут строиться для отдельного знака первичного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов).