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

Кодирование информации - процесс формирования определенного представления информации. Конкретнее, под термином «кодирование» понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки.

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

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

Шифрование - разновидность кодирования.

Шифр - код, значение и правила использования которого известно ограниченному кругу лиц.

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

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

Следовательно, кодирование предшествует передаче и хранению информации. При этом хранение связано с фиксацией некоторого состояния носителя информации, а передача — с изменением состояния во времени (т.е. процессом). Эти состояния или сигналы будем называть элементарными сигналами - именно их совокупность и составляет вторичный алфавит. ^[[10]]

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

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

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

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

• А - первичный алфавит. Состоит из N знаков со средней информацией на знак I^A.

• В- вторичный из М знаков со средней информацией на знак I^B.

• Сообщение в первичном алфавите содержит m знаков, а закодированное - m знаков.

• I_s(A) - информация в исходном сообщении. I_f(B) - информация в закодированном сообщении.

• I_s(A) ≤ I_f(B) – условие обратимости кодирования, т.е. не исчезновения информации.

• n * I(A) ≤ m * I(B) (заменили произведением числа знаков на среднее информационное содержание знака).

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

• K (A, B) ≥ I(A) / I(B) Обычно K (A, B) > 1.

• K^min (A, B) = I^(A) / I^(B) – минимальная длина кода.

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

Кодер - одна из двух компонент кодека (пары кодер - декодер).

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

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

Кодирование информации распадается на определенные этапы:

1. Определение объёма информации, подлежащей кодированию.
2. Классификация и систематизация информации.
3. Выбор системы кодирования и разработка кодовых обозначений.
4. Непосредственное кодирование.

2.2. Алфавит в теории информации

Несмотря на то, что естественной для органов чувств человека является аналоговая форма, универсальной все же следует считать дискретную форму представления информации с помощью некоторого набора знаков. Например, именно представленная в дискретной форме информация обрабатывается компьютером, передаётся по компьютерным и многим другим каналам связи. Сообщение - последовательность знаков алфавита. При их передаче возникает вопрос распознавания знака: каким образом прочитать сообщение, т.е. по полученным сигналам установить первоначальную последовательность знаков первичного алфавита. В устной речи это достигается использованием различных фонем (основных звуков разного звучания), по которым мы и отличает знаки речи. В письменности это достигается различным начертанием букв и дальнейшим анализом написанного. ^[[12]] Можно реализовать некоторую процедуру, посредством которой выделить из сообщения тот или иной знак. Но появление конкретного символа (буквы) в конкретном месте сообщения — событие случайное. Поэтому, узнавание (отождествление) знака требует получения некоторой порции информации. Можно связать эту информацию с самим знаком и предполагать, что знак несет в себе некоторое количество информации.

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

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

Тогда:

К^min (А, В)= I ^(А) / log₂ М= I ^(А), здесь I – средняя

Алфавит [alphabetos], от названий первых двух букв греческого А. - альфа и бета; аналогично: азбука — от «аз» и «буки», совокупность графических знаков — букв (например, латинский, русский) или слоговых знаков (например, индийский, деванагари), расположенных в традиционно установленном порядке.

Знак - соглашение (явное или неявное) о приписывании чему-либо (означающему) какого-либо определённого смысла (означаемого). Знак — это материально выраженная подмена предметов, явлений, понятий в процессе обмена информацией в обществе. Знаком также называют конкретный случай использования такого соглашения для передачи информации. Знак может быть составным, то есть состоять из нескольких других знаков. Буквы и слова человеческого языка являются знаками. Цифры и числа являются знаками. Наука о знаковых системах называется семиотикой.^[[13]]

Рассмотрим символы, применяемые непосредственно в компьютере - цифры, буквы, иероглифы и т.п.

Начнём с самого грубого приближения (будем называть его нулевым) предположим, что появление всех знаков (букв) алфавита в сообщении равновероятно. Тогда для английского алфавита n_e=27 (с учетом наличия пробела как самостоятельного знака); для русского алфавита n_r=34. Из формулы Хартли

I = log₂ n (2.1)

находим:

I₀^(e)= log₂27 = 4,755 бит.

I₀^(r)= log₂34 = 5,087 Сит.

В результате получаем, что в нулевом приближении со знаком русского алфавита в среднем связано больше количество информации, чем со знаком английского языка. Например, в русской букве «а» информации больше, чем в «а» английской! Это, безусловно, не означает, что английский язык - язык Шекспира и Диккенса — беднее, чем язык Пушкина и Достоевcкого. Лингвистическое богатство языка определяется количеством слов и их сочетаний, а это никак не связано с числом букв в алфавите. С точки зрения техники это означает, что сообщения из равного количества символов будет иметь разную длину (и соответственно, время передачи) и большими они окажутся у сообщений на русском языке.

В качестве следующего (первого) приближения, уточняющего «нулевое», попробуем учесть то обстоятельство, что относительная частота или вероятность появления различных букв в тексте (или сообщении) неодинакова. Рассмотрим таблицу средних частот (вероятностей) появления букв для русского алфавита, в который включен также знак «пробел» для разделения слов; с учетом неразличимости букв «е» и «ё», а также «ь» и «ъ» (так принято в телеграфном кодировании), получим алфавит из 32 знаков со следующими вероятностями их появления в русских текстах:

Табл. 2.1 Частота появления букв

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

I = (2.2)

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

Из неё, к примеру, следует, что если р, — вероятность (относительная частота появления) знака номер i данного алфавита из N знаков, то среднее количество информации, приходящейся на один знак, равно:

(2.3)

- формула К. Шеннона.

Теорема Шеннона (переформулировка).

При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.^[[14]]

Применение формулы (2.3) к алфавиту русского языка дает значение средней информации на знак I_i^(r) = 4,36 бит, а для английского языка I_i^(e) = 4,04 бит, для французского I_i^(f) = 3,96 бит, для немецкого I_i^(d) = 4,10 бит, для испанского I_i^(s) = 3,98 бит. Как мы видим, и для русского, и для английского языков учёт вероятностей появления букв в сообщениях приводит к уменьшению среднего информационного содержания буквы, что, кстати, подтверждает справедливость формулы (2.3). Несовпадение значений средней информации для английского, французского и немецкого языков, основанных на одном алфавите, связано с тем, что частоты появления одинаковых букв в них различаются.

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

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

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