Когда необходимо кодирование и декодирование информации. Кодирование информации

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

Что означает понятие «кодирование»?

Код представляет собой совокупность символов, соответствующих определенным элементам информации либо характеристикам. Что касается самого процесса, при котором этот код составляется, он имеет название кодирования. Кодирование информации осуществляется с той целью, чтобы представить данные компактно и удобно, что необходимо при передаче и обработки на вычислительной технике. В ходе кодирования обработка состоит в поиске, сортировании, а также упорядочении существующих данных. Результатом этих процессом выступают выходные коды. После декодирования они являются конечной целью в обмене информацией между различными ЭВМ.

Что означает понятие «декодирование»?

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

Как выполняется процесс кодирования?

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

Большое распространение получил автоматический метод кодирования. В ходе данного процесса все записывается при помощи слов, общепринятых обозначений, а также цифр в созданный на ЭВМ документ. Итоговый файл поступает для обработки в специальный автомат. Он осуществляет кодирование та, что получается максимально короткий машинный код. Он представляет удобство при поиске, сортировке и обработке данных. Автоматическое кодирование выполняется при условии наличия словаря, где конкретному коду соответствует одно слово.

Такой подход ведет к отсутствию необходимости в разделения информации по ее смыслу. Ее обработка происходит в понятном машинам виде. Таким образом, с ней можно уверенно работать, акцентируя процессорную мощь на более необходимые действия. Работа ЭВМ с такой информацией происходит за счет наличия ключевого кода. Он представляет собой единый массив информации, которая используется для всех решаемых задач. Процесс поиска выполняется на основании однозначности отношения признаков к предмету. Обычно он происходит по битовому адресу, однако способен применяться и порядковый регистрационный номер при отсутствии дополнительной информации. Стоит также указать на еще один способ кодирования, при котором происходит сортировка данных по их содержанию. Иными словами, осуществляется классификация, где роль играют только основные определяющие признаки.

Как происходит декодирование?

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

Декодирование представляет собой достаточно сложный процесс, поскольку в ходе передачи данных могут быть потери сигналов, что ведет к негативным последствиям. Если получен утвердительный ответ, техника на основе определенных признаков проводит декодирование полученной информации в соответствии с существующими каталогами данных. Когда это невозможно, ЭВМ имеется процедура игнорирования, дающая возможность отсортировывать множество ненужной для него информации.

Виды кодов

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

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

2. Двоичное кодирование текстовой информации .

Двоичное кодирование графической информации.

4. Двоичное кодирование звуковой информации .

Двоичное кодирование видеоинформации.

Сжатие информации.

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

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

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

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

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

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

Для представления дискретной информации используется некоторый алфавит. Однако однозначное соответствие между информацией и алфавитом отсутствует.

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

Алфавит, с помощью которого представляется информация до преобразования называется первичным; алфавит конечного представления – вторичным.

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

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

Конечная последовательность кодовых знаков называется словом.

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

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

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

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

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

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

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

Кодирование может быть равномерное и неравномерное. При равномерном кодировании все символы кодируются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование Закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова; закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова. Условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

Например, для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа. 1) для буквы Б – 01 2) это невозможно 3) для буквы В – 01 4) для буквы Г – 01

Для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано. Проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);

1). проверяем вариант 1: А–00, Б–01, В–011, Г–101, Д–111. «прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В); «обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;

2). проверяем вариант 3: А–00, Б–010, В–01, Г–101, Д–111. «прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б); «обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;

3). проверяем вариант 4: А–00, Б–010, В–011, Г–01, Д–111. «прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит. Правильный ответ – 4.

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

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

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

Кодирование - это переход от одного алфавита (буквенного кода) к другому.

Пусть A = {а 1 ,а 2 ,...,а т) и В = {b l ,b 2 ,...,b n) - алфавиты.

Элементы алфавита называются буквами.

Последовательность букв некоторого алфавита называют словом в этом алфавите.

Л*, В* - множество слов в алфавите Ли В соответственно.

Кодированием будем называть функцию F: В* где S с А*.

S называется множеством сообщений.

Образы сообщений называют кодами , т. е. р е В *: (3 = F{ а),а е S.

Измерением кодирования является количество букв в алфавите В, т. е. это п-ичное кодирование.

Двоичное кодирование ^>В = 2,В = {0,1}.

Декодирование - это F~ { .

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

Свойства кодирования

• 1. Существование декодирования (компиляция, трансляция программ не требует декодирования).
• 2. Помехоустойчивость или исправление ошибок Ф" близок к коду Р) => (F -1 (р) = F~ l (р")).
• 3. Сложность или простота кодирования и декодирования (криптографический алфавит: F - простая, a F~" сложная).

Алфавитное кодирование

Количество букв в слове называется длиной слова.

Пусть а = а. а, 2 ...д 4 - слово. |а| = к - длина слова а.

Пустое слово - слово нулевой длины. |л| = О, Л g А.

Пусть а = а,а 2 - слово, полученное склеиванием слов а (и а 2 .

Тогда а, - начало, префикс слова а, а 2 - окончание, постфикс слова а. Алфавитное (побуквенное) кодирование задается схемой а:Р, я 2 ->Р 2 , ..., >> где а к е Д р Л е 2Г.

Т. е. частный случай кодирования, когда задаются коды каждой буквы алфавита А, кодами являются слова алфавита В.

V = {р А }” ч - элементарные коды.

Алфавитное кодирование определяет кодирование для любого множества сообщений S из А*.

Примеры

Л = {°,1,-,9} ^ = {0,1}

1. ст: 1,2 -> 10,3 -> 11,4 -? 100, ..., 9-> 1001 > - схема алфавитного кодирования.

/г(123) = 11011

Это кодирование не взаимнооднозначное, т. к. ДЗОЗ) = 11011, т. е. а, = 123 * а 2 = 303, но F(a,) = /’(a 2).

2. ст: 0000,1->0001,2->0010, ...,9 -> 1001 >.

Это двоично-десятичное кодирование. Эта схема является взаимнооднозначной. Следовательно, существует декодирование.

разделимой, если любое слово, составленное из элементарных кодов, единственным образом разделяется на элементарные коды.

Схема алфавитного кодирования называется префиксной, если элементарный код одной буквы не является префиксом элементарного кода другой буквы.

Примеры (предыдущий)

1. Неразделимая схема кодирования (11 1/1 и 11);

не префиксная (элементарный код 1 является элементарным кодом 2).

2. Разделимая и префиксная.

Теорема

Любая префиксная схема является разделимой.

Допустим, что схема префиксная, но неразделимая.

Тогда существует два разных представления одного слова: р. ...р^ = р У| ...р^ . Пусть Р,. * Р Л.

Тогда либо Р (. является началом слова р у. (р. р = Р у.), либо наоборот (р у. р = Р (.). Следовательно, схема не префиксная. Получили противоречие.

Обратное утверждение неверно!!!

Не любая разделимая схема является префиксной.

Достаточное условие разделимости (но не является необходимым): префиксная => разделимая.

Пример

А = {а,Ь) й = {0,1}

а:0, Z>->01> - не префиксная, разделимая.

Теорема (необходимое условие разделимости)

о:-^ Ь к >" =1 - разделимая, то выполняется неравенство:

Обратное неверно!!!

Теорема

Если для чисел /, ...,1 т выполняется неравенство то существует разделимая схема алфавитного кодирования о:Ь к >“ =1 , где В = {0,1}, такая, что

IPJ = К’ к= 1 ’ т

Пример

1. а:а -» 0,Ь -» 01 > - не префиксная, разделимая.

По теореме выполняется неравенство:

2. а:0,6-»1 > - разделимая, т. к.

Если неравенство не выполняется, то схема не является разделимой.

Если неравенство выполняется, то ничего нельзя сказать про разделимость схемы.

Минимизация длины кода сообщения

Рассмотрим задачу построения кодов по возможности наименьшей длины. Для этого используется дополнительная информация о множестве сообщений S, например, распределение вероятностей букв алфавита А

Очевидно:

Если схема алфавитного кодирования о: разделимая, то и разделима любая схема а", полученная перестановкой набора элементарных кодов.

Если длины всех элементарных кодов равны, то перестановка элементарных кодов не изменит длину кода любого сообщения.

Если длины элементарных кодов различны, то длина кода сообщения зависит от состава букв в сообщении и от того, какие элементарные коды каким буквам назначены.

Пусть задан вектор p = (p i ,...,p m) распределения вероятностей букв в сообщении, причем р х > р 2 >...>р т >0 (упорядочены не по возрастанию).

Пусть дана схема алфавитного кодирования о: Ъ к >“ =1 . Определим для этой схемы математическое ожидание коэффициента увеличения длины сообщения, или среднюю длину кода одного символа:

которая называется средней ценой (длиной) алфавитного кодирования а для распределения вероятностей р.

Схема алфавитного кодирования, для которой длины всех элементарных кодов равны, называется равномерной.

Минимальная длина кода каждой буквы при условии разделимости при этом равна

Для равномерного кодирования средняя цена кодирования равна

L(p) - минимальная длина разделимой схемы алфавитного кодирования при распределении вероятностейр.

Среди схем алфавитного кодирования, средняя длина которых не превосходит конечное количество / 0 , существует схема с минимальной длиной а» (р), для которой /„.(/>) = inf/„(/>).

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

Свойства оптимального кодирования

1. Пусть ст, - схема оптимального кодирования.

Тогда

Доказательство (от противного)

Пусть это свойство не выполняется, т. е. p t > Pj & |(3, | > |р у |).

а/ , полученная из а, перестановкой кодов (3,. и р у, т.е. а/ : a j -» р у; а } -» Р (..

Тогда

Получили противоречие с тем, что а, - схема оптимального кодирования.

2. Пусть а, - схема оптимального кодирования.

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

3. Пусть стГ 1 : ->р Л >"“/ - схема оптимального кодирования. р.Р>р 2 >...>р т _> 0, Pj = q x + q 2 , гдер т _ х >q x >q 2 > 0.

Тогда схема алфавитного кодирования

является оптимальной для распределения вероятностей

Самокорректирующиеся коды

Помехоустойчивый код

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

Кодирование F называется помехоустойчивым , или кодированием с исправлением ошибок, или самокорректирующимся, если выполняется следующее условие:

где S с A*, KgB А = В = {0,1}.

Виды ошибок:

• 1. Ошибка замещения разряда: 0 -> 1; 1^0.
• 2. Ошибка выпадения разряда: 0 -> Л; 1 -> Л.
• 3. Ошибка вставки разряда: Л -» 0; Л ^ 1.

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

Рассмотрим канал связи с характеристикой. Возможна единичная ошибка замещения разряда в сообщении длины п.

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

Код с обнаружением ошибок

Нужно добавить бит четности - контрольная сумма:

а = а 1 а 2 ...а т - бит четности - сумма по модулю 2 всех остальных - контрольная сумма.

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

Код Хаффмана

Код Хаффмана является оптимальным кодированием.

Правила построения

Построение кода Хаффмана основано на сжатии алфавита.

Пусть есть алфавит А = {а х,а 2 ,...,а т) с вероятностями р х > р 2 >...> р т.

Условимся не различать две наименее вероятные буквы а т _ х и а т.

Переупорядочим буквы алфавита А х по не возрастанию вероятностей. Полученный алфавит снова подвергнем однократному сжатию. Получим алфавит А 2:А 2 = т-2 и т. д., сжимаем до алфавита А т _ 2 :|Д т _ 2 | = 2. Двум буквам этого алфавита приписываем коды 0 и 1.

Пусть определены коды всех букв алфавита А } _ х, определим коды букв алфавита Aj_ 2 .

Буквы алфавита Aj_ 2 , которые входят в алфавит А у._ х , имеют тот же код.

Пусть буквы а" и а" при сжатии объединяются в одну букву Ь, имеющую код р и вероятность р(я")> р(я").

Тогда а" р0 , а" -> pi.

Следовательно, А т _ 2 ,...,А.

Таким образом, начиная с А т _ 2 , строится код исходного алфавита А По построению этот код будет префиксным и, следовательно, разделимым. Набор кодов {0,1} является оптимальным для алфавита из двух букв А т _ 2 . На каждом шаге из оптимальной схемы кодирования снова строится оптимальная схема кодирования, и полученный код является оптимальным.

Код Хаффмана используется для упорядоченных вероятностей.

Пример

Построить схему оптимального кодирования для алфавита с распределением вероятностей /? = (0,2;0,2;0,19;0,12;0,11;0,09;0,09) (вероятности не возрастают). Решение

• 1. Выписываем вероятности в порядке убывания в первый столбец таблицы.
• 2. Складываем две последние вероятности: 0,09 + 0,09 = 0,18.
• 3. Упорядочиваем оставшиеся вероятности в порядке убывания и записываем результат в третий столбец.
• 4. Опять складываем две последние вероятности и, упорядочивая, записываем в пятый столбец и т. д., пока не останется всего два числа: 0,6 и 0,4, которые в сумме дают единицу.
• 5. Верхнему числу присваиваем код «0», нижнему - «1».
• 6. Теперь двигаемся справа налево: тем числам, которые присутствуют, присваиваем тот же самый код (0,4 - «1»), а тем, которые в сумме дают число 0,6, присваиваем коды «00» (верхнему) и «01» (нижнему).
• 7. Аналогично доходим до самого первого столбика и формируем коды для всех элементов вектора р (см. табл. 11).

Таблица 11

Ответ: а 2 -»11; а 3 000; я 4 -» 010; а 5 -> 011; я 6 0010; я 7 -> 0011 >. Оптимальная длина кодирования:

/.=0,2-2 + 0,2-2 + 0,19-3 + 0,12-3 + 0,11-3 + 0,09-4 + 0,09-4 = 2,78 / 0 = 3 - длина равномерного кодирования

Код Фано

При кодировании по Фано все сообщения записываются в таблицу по степени убывания вероятности и разбиваются на две группы примерно (насколько это возможно) равной вероятности. Соответственно этой процедуре из корня кодового дерева исходят два ребра, которым в качестве весов присваиваются полученные вероятности. Двум образовавшимся вершинам приписываются кодовые символы 0 и 1. Затем каждая из групп вероятностей вновь делится на две подгруппы примерно равной вероятности. В соответствии с этим из каждой вершины 0 и 1 исходят по два ребра с весами, равными вероятностям подгрупп, а вновь образованным вершинам приписывают символы 00 и 01, 10 и 11.

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

Пример (табличный способ)

Построить схему оптимального кодирования для алфавита с распределением вероятностей р = (0,2; 0,2; 0,19; 0,12; 0,11; 0,09; 0,09) (вероятности не возрастают). Решение

Смысл: выделяем две группы в зависимости от разности суммы, которая должна быть минимальной. Верхней группе чисел присваиваем «0», а нижней «1». Алгоритм:

• 1. Посчитать суммы сверху и суммы снизу (см. табл. 12).
• 2. Найти модуль разности сумм сверху и сумм снизу:

3. Выбрать наименьший модуль разности:

|0,59-0,41| = 0,18

• 4. Разбить группу на две подгруппы: получается, что в первую подгруппу входят первые три элемента, а во вторую - все остальные.
• 5. Присваиваем верхним трем элементам коды «О», а остальным нижним коды «1».
• 6. Теперь разбиваем первую подгруппу, состоящую из трех элементов, на две подгруппы (см. пункты 1-4):

Таблица 12

|0,2 - 0,39| = 0,19 - наименьший модуль разности |0,4 - 0,19| = 0,21

Значит, эта группа разбивается на две подгруппы, в первую входит всего один первый элемент, а во вторую - остальные два элемента.

7. Присваиваем код первой подгруппе, т. е. одному элементу - «00» (это итоговый код первого элемента), а второй подгруппе, состоящей из двух элементов, код «01». Когда группа состоит из двух элементов, то можно сразу присвоить итоговые коды: «010» и «011».

Аналогично разбиваем вторую подгруппу и получаем итоговые коды.

Таблица 13

КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ

Процесс представления информации в определенной стандартной форме и обратный процесс восстановления информации по ее такому представлению. В математич. литературе кодированием наз. произвольного множества Ав конечных последовательностей (слов) в нек-ром алфавите В, а декодированием - . Примерами кодирования являются: представление натуральных чисел в r-ичной системе счисления, при к-ром каждому числу N=i, 2, ... ставится в слово b 1 b 2 ... b l в алфавите В r = {0, 1, ..., r-1} такое, что b 1 неравно 0 и b 1 r l -1 +...+ b l -1 r+b l =N; текстов на русском языке с помощью телеграфного кода в последовательности, составленные из посылок тока и пауз различной длительности; отображение, применяемое при написании цифр почтового индекса (см. рис.). В последнем случае каждой десятичной цифре соответствует слово в алфавите В 2 = {0, 1} длины 9, в котором символами 1 отмечены номера использованных линий (напр., цифре 5 соответствует слово 110010011). Исследование различных свойств К. и д. и построение эффективных в определенном смысле кодирований, обладающих требуемыми свойствами, составляет проблематику теории кодирования. Обычно критерий эффективности кодирования так или иначе связан с минимизацией длин кодовых слов (образов

элементов множества А), а требуемые свойства кодирования связаны с обеспечением заданного уровня помехоустойчивости, понимаемой в том или ином смысле. В частности, под помехоустойчивостью понимается возможность однозначного декодирования при отсутствии или допустимом уровне искажений в кодовых словах. Помимо помехоустойчивости, к кодированию может предъявляться дополнительных требований. Напр., при выборе кодирования для цифр почтового индекса необходимо согласование с обычным способом написания цифр. В качестве дополнительных требований часто используются ограничения, связанные с допустимой сложностью схем, осуществляющих К. и д. Проблематика теории кодирования в основном создавалась под влиянием разработанной К. Шенноном (С. Shannon, ) теории передачи информации. Источником новых задач теории кодирования служат создание и совершенствование автоматизированных систем сбора, хранения, передачи и обработки информации. Методы решения задач теории кодирования главным образом комбинаторные, теоретико-вероятностные и алгебраические. Произвольное кодирование f множества (алфавита) Асловами в алфавите Вможно распространить на множество А* всех слов в А(сообщений) следующим образом:

где i=1, 2, . . ., k. Такое отображение f: наз. побуквенным кодированием сооб. щений. Более общий кодирований сообщений образуют автоматные кодирования, реализуемые инициальными асинхронными автоматами, выдающими в каждый времени нек-рое (быть может, пустое) слово в алфавите В. Содержательный смысл этого обобщения заключается в том, что в разных состояниях реализует различные кодирования букв алфавита сообщений. Побуквенное кодирование - это автоматное кодирование, реализуемое автоматом с одним состоянием: Одним из направлений теории кодирования является изучение общих свойств кодирования и построение алгоритмов распознавания этих свойств (см. Кодирование алфавитное ). В частности, для побуквенных и автоматных кодирований найдены необходимые и достаточные условия для того, чтобы:

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

Большинство задач теории кодирования сводится к изучению конечных или счетных множеств слов в алфавите В r . Такие множества наз. кодами. В частности, каждому однозначному кодированию f: (и побуквенному кодированию ) соответствует Одно из основных утверждений теории кодирования состоит в том, что условие взаимной однозначности побуквенного кодирования накладывает следующее ограничение на длины li=l,if )кодовых слов f(i):

Справедливо и обратное утверждение: если (l 0 , .. ., l m -1)- набор натуральных чисел, удовлетворяющих (1), то существует взаимно однозначное побуквенное кодирование такое, что слово f(i)имеет длину l i ;. При этом, если числа l i упорядочены по возрастанию, то в качестве f(i) можно взять первые после запятой l i символов разложения числа в r-ичную (метод Шеннона).

Наиболее законченные результаты в теории кодирования связаны с построением эффективных взаимно однозначных кодирований. Описанные здесь конструкции используются на практике для сжатия информации и выборки информации из памяти. Понятие эффективности кодирования зависит от выбора критерия стоимости. При определении стоимости L(f)взаимно однозначного побуквенного кодирования предполагается, что каждому числу поставлено в соответствие положительное р i и Р= {р 0 , ..., P m-1 ). Исследованы следующие варианты определения стоимости L(f):

причем предполагается, что в первых двух случаях р i - вероятности, с к-рыми некоторый бернуллиевый порождает соответствующие буквы алфавита В т а в третьем случае р i - заданные длины кодовых слов. При первом определении стоимость равна средней длине кодового слова, при втором определении с ростом параметра tболее длинные кодовые слова оказывают все большее влияние на стоимость ( при и при ), при. третьем определении стоимость равна максимальному превышению длины l i кодового слова над заданной длиной р i . Задача построения взаимно однозначного побуквенного кодирования f: В* т ->В* r , минимизирующего стоимость L(f), равносильна задаче минимизации функции L(f) на наборах (l 0 , ..., 1 т-1 )из натуральных чисел, удовлетворяющих (1). Решение этой задачи известно при каждом из указанных определений стоимости. Пусть величины L(f)на наборах (l 0 , . . ., l m-1 )из произвольных (не обязательно натуральных) чисел равен L r (P)и достигается на наборе (l 0 (Р), ..., l т-1 (Р)). Неотрицательная I(f) = L (f) - L r (P)наз. избыточностью, а величина I(f)/L (f)- относительной избыточностью кодирования f. Для избыточности взаимно однозначного кодирования построенного по методу Шеннона для длин справедливо I(f)<1. При первом, наиболее употребительном, определении стоимости как среднего числа кодовых символов, приходящихся на одну букву порождаемого источником сообщения, величина L r (P)равна энтропии Шеннона

источника, вычисленной по основанию r, a l i (P)=-log r p i . Граница избыточности I(f) = L ср (f)- Н r (P)< 1 может быть улучшена с помощью так наз. кодирования блоками длины k, при к-ром сообщения длины k(а не отдельные буквы) кодируются по методу Шеннона. Избыточность такого кодирования не превышает 1/k. Этот же прием используется для эффективного кодирования зависимых источников. В связи с тем, что определение длин l i при кодировании по методу Шеннона основано на знании статистики источника, для нек-рых классов источников разработаны методы построения универсального кодирования, гарантирующего определенную верхнюю границу избыточности для любого источника из этого класса. В частности, построено кодирование блоками длины к, избыточность к-рого для любого бернуллиевого источника асимптотически не превышает (при фиксированных ), причем эта асимптотическая не может быть улучшена.

продолжение Кодирование и декодорование...

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

При исследовании задач построения эффективных помехоустойчивых кодирований обычно рассматривают кодирования к-рым соответствуют коды {f(0), . .., f(m-1)}, принадлежащие множеству слов длины пв алфавите В r , и предполагают, чтo буквы алфавита сообщений В т равновероятны. Эффективность такого кодирования оценивают избыточностью I(f)= п-log r m или скоростью передачи В(f)= При определении помехоустойчивости кодирования формализуется понятие ошибки и вводится в рассмотрение нек-рая образования ошибок. Ошибкой типа замещения (или просто ошибкой) наз. преобразование слова, состоящее в замещении одного из его символов другим символом алфавита В r . Напр., проведение лишней линии при написании почтового индекса приводит к замещению в кодовом слове символа 0 символом 1, а отсутствие нужной линии - к замещению символа 1 символом 0. Возможность обнаружения и исправления ошибок основана на том, что для кодирования f, обладающего ненулевой избыточностью, декодирование f -1 может быть произвольным образом доопределено на r п -тсловах из не являющихся кодовыми. В частности, если множество разбито на тнепересекающихся подмножеств D 0 , . . ., D m-1 таких, что а декодирование f -1 доопределено так, что f -1 (D i )=i, то при декодировании будут исправлены все ошибки, преобразующие кодовое слово f(i) в D i , i=0, ..., т-1. Аналогичная возможность имеется и в случае ошибок других типов таких, как стирание символа (замещение символом другого алфавита), изменение числового значения кодового слова на b=1, ..., r-1, i=0, 1, ... (арифметическая ошибка), выпадение или вставка символа и т. п.

В теории передачи информации (см. Информации передача )рассматриваются вероятностные модели образования ошибок, называемые каналами. Простейший задается вероятностями р ij замещения символа iсимволом j. Для канала определяется величина (пропускная способность)

где максимум берется по всем наборам (q 0 , . . ., q m-1 )таким, что и Эффективность кодирования f характеризуется скоростью передачи R(f), а помехоустойчивость - средней вероятностью ошибки декодирования Р(f) (при наилучшем разбиении. В n r на подмножества D i ). Основной результат теории передачи информации ( Шеннона) состоит в том, что пропускная способность Сявляется верхней гранью чисел Rтаких, что для любого е>0 при всех п, начиная с нек-рого, существует кодирование

для к-рого и Р(f)

Другая модель образования ошибок (см. Код с исправлением ошибок, Код с исправлением арифметических ошибок, Код с исправлением выпадений и вставок )характеризуется тем, что в каждом слове длины ппроисходит не более заданного числа tошибок. Пусть E i (t)- множество слов, получаемых из f(i)в результате tили менее ошибок. Если для кода

множества E i (t), i=0, ..., m-1, попарно не пересекаются, то при декодировании таком, что E i (t)Н D i , будут исправлены все ошибки, допустимые рассматриваемой моделью образования ошибок, и такой код наз. кодом с исправлением tошибок. Для многих типов ошибок (напр., замещений, арифметич. ошибок, выпадений и вставок) d( х, у ), равная минимальному числу ошибок данного типа, преобразующих слово в слово является метрикой, а множества E i (t)- метрическими шарами радиуса t. Поэтому задача построения наиболее эффективного (т. е. максимального по числу слов т)кода в В n r с исправлением tошибок равносильна задаче плотнейшей упаковки метрического пространства шарами радиуса t. Код для цифр почтового индекса не является кодом с исправлением одной ошибки, так как d(f(0), f (8))=1 и d(f(5), f (8)) = 2, хотя все другие расстояния между кодовыми словами не менее 3.

Задача исследования величины I r (n, t )- минимальной избыточности кода в с исправлением tошибок типа замещения распадается на два основных случая. В первом случае, когда tфиксировано, а справедлива асимптотика

причем достигается "мощностная" граница, основанная на подсчете числа слов длины пв шаре радиуса t. Асимптотика величины I r (n, t )при г>2, а также при r=2 для многих других типов ошибок (напр., арифметич. ошибок, выпадений и вставок) не известна (1978). Во втором случае, когда t= [pn ], где р - некоторое фиксированное число, 0<р<(r-1)/2r, а "мощностная" граница

где T r (p)=-p log r (p/ (r- 1))-(1-р)log r (l- p), существенно улучшена. Имеется предположение, что верхняя граница

полученная методом случайного выбора кода, является асимптотически точной, т. е. I r ( п, [ рп ])~пТ r (2р ). Доказательство или опровержение этого предположения - одна из центральных задач теории кодирования.

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

Еще одно исследований в теории кодирования связано с тем, что многие результаты (напр., теорема Шеннона и граница (3)) не являются "конструктивными", а представляют собой теоремы существования бесконечных последовательностей {К п } кодов В связи с этим предпринимаются усилия, чтобы доказать эти результаты в классе таких последовательностей {К п } кодов, для к-рых существует Тьюринга, распознающая принадлежность произвольного слова длины lмножеству за время, имеющее медленный роста относительно l(напр., llog l).

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

Лит. : Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963; Берлекэмп Э., Алгебраическая кодирования, пер. с англ., М., 1971; Питерсон У., Уэлдон Э., Коды, исправляющие ошибки, пер. с англ., 2 изд., М., 1976; Дискретная и математические вопросы кибернетики, т.1, М., 1974, раздел 5; Бассалыго Л. А., Зяблов В. В., Пинскер М. С, "Пробл. передачи информации", 1977, т. 13, № 3, с. 5-17; [В] Сидельников В. М., "Матем. сб.", 1974, т. 95, в. 1, с. 148 - 58.

В. И. Левенштейн.

Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .

Смотреть что такое "КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ" в других словарях:

См. Кодирование и декодирование … Математическая энциклопедия

- (от франц. code – свод законов, правил) – отображение (преобразование) нек рых объектов (событий, состояний) в систему конструктивных объектов (называемых кодовыми образами), совершаемое по определ. правилам, совокупность к рых наз. шифром К.,… … Философская энциклопедия

Кодирование - Encoding Отождествление квантованного сигнала электросвязи с кодовыми словами Примечания: 1. Под кодовым словом понимается упорядоченная последовательность символов некоторого алфавита. 2. В конкретных устройствах квантование сигнала электросвязи … Словарь-справочник терминов нормативно-технической документации

Установление соответствия между элементами сообщения и сигналами, при помощи к рых эти элементы могут быть зафиксированы. Пусть В, множество элементов сообщения, А алфавит с символами, Пусть конечная последовательность символов наз. словом в… … Физическая энциклопедия

Декодировка, дешифрование, дешифровка, дешифрирование, расшифровка, расшифровывание. Ant. кодирование Словарь русских синонимов. декодирование сущ., кол во синонимов: 8 декодировка (8) … Словарь синонимов

декодирование - Восстановление дискретного сообщения по сигналу на выходе дискретного канала, осуществляемое с учетом правила кодирования. [Сборник рекомендуемых терминов. Выпуск 94. Теория передачи информации. Академия наук СССР. Комитет технической… … Справочник технического переводчика

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

В теории передачи данных - преобразование знаков в сигналы.

Перекодирование видео - преобразование видеофайла из одного формата в другой или изменение его свойств (разрешение, битрейт) исходного.

В цифровом телевидении и радио.

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

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

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

13. Когда применяется кодирование по образцу?

Кодирование по образцу - каждый знак дискретного сигнала представляется знаком или набором знаков того алфавита, в котором выполняется кодирова­ние. Кодирование по образцу используется, например, для ввода информации в компьютер с целью ее внутреннего представления. Пример. Для перевода символов, вводимых с клавиатуры, в числовой код, хра­нящийся в памяти компьютера, используется кодовая таблица ASCII (American Standard Code for Information Interchange - американский стандартный код для обмена информацией), в которой каждому символу алфавита, а также множеству специальных управляющих команд соответствует числовой код.

14. Какие типы шифрования вам известны?

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