Основные методы кодирования декодирования информации. Кодирование и декодирование — это сложно? Как выполняется процесс кодирования

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

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

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

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

Пусть 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

Сумма сверху		Сумма снизу

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

В настоящее время понятие "код" трактуют по-разному. Ряд авторов (Р. Бландел, А. Б. Зверинцев, В. Г. Корольке, А. П. Панфилова и др.) понимают коды в самом широком плане - как любую форму представления информации либо как набор однозначных правил, посредством которых сообщение может быть представлено в той или иной форме. Человеческая речь также представляет собой один из кодов.

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

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

Декодирование - в техническом смысле - это процесс, обратный процессу кодирования. В более широком плане это: - процесс придания определенного смысла полученным сигналам;

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

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

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

Модель кодирования/декодирования С. Холла

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

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

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

Теория С. Холла была сформулирована на примере работы телевидения и применима к любым видам СМИ. Она состоит в том, что медиасообщение проходит на своем пути от источника до получателя (интерпретатора) ряд трансформаций. Стадии, которые проходит информационное сообщение на пути к получателю, проспи. Коммуникация инициируется медиаинститутами, которые передают сообщения, конформные или оппозиционные по отношению к доминирующим структурам власти, различным общественным, политическим и экономическим социальным институтам. Эти сообщения кодируются, часто в форме устоявшихся содержательных жанров ("новости", "спорт", "поп-музыка", "мыльная опера", "детективный сериал" и пр.), имеющих очевидный содержательный смысл, актуализированную направленность и встроенные руководства для их интерпретации заинтересованной целевой аудиторией. Зритель подходит к содержанию, предлагаемому СМИ, с другими "смысловыми структурами", которые коренятся в его собственных здравом смысле, идеях и опыте.

Различные группы людей (или субкультуры) занимают разные социальные и культурные ниши этнопространства и по-разному воспринимают сообщения СМИ. Общий вывод С. Холла заключается в том, что декодированный смысл не обязательно должен совпадать с тем смыслом, который был закодирован, хотя он и опосредуется уже сложившимися медиажанрами и общей языковой системой. Однако важнее то, что декодирование может принимать направление, отличное от предполагаемого: получатели могут читать между строк и даже "переворачивать" изначальный смысл сообщения.

Теория Холла содержит ряд принципиальных положений, а именно:

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

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

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

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

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

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

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

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

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

Рис. 1. Процесс передачи сообщения от источника к приемнику

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

Рассмотрим основные принципы кодирования информации в компьютере.

5. Кодирование текстовой информации

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

Для кодирования одного символа требуется один байт информации. Учитывая, что каждый бит принимает значение 1 или 0, получаем, что с помощью 1 байта можно закодировать 256 различных символов. (2 8 =256) Кодирование заключается в том, что каждому символу ставиться в соответствие уникальный двоичный код от 00000000 до 11111111 (или десятичный код от 0 до 255). Важно, что присвоение символу конкретного кода – это вопрос соглашения, которое фиксируется кодовой таблицей.

Например, вы нажимаете на компьютере латинскую букву S. В этом случае в память компьютера записывается код 01010011. Для вывода буквы S на экран в компьютере происходит декодирование – по этому двоичному коду строится его изображение.

Обратите внимание!

Цифры кодируются по стандарту ASCII в двух случаях – при вводе-выводе и когда они встречаются в тексте. Если цифры участвуют в вычислениях, то осуществляется их преобразование в другой двоичный код.

Возьмем число 57. При использовании в тексте каждая цифра будет представлена своим кодом в соответствии с таблицей ASCII. В двоичной системе это – 00110101 00110111. При использовании в вычислениях код этого числа будет получен по правилам перевода в двоичную систему и получим – 00111001.

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

Под графической информацией можно понимать рисунок, чертеж, фотографию, картинку в книге, изображения на экране телевизора или в кинозале и т. д. Для обсуждения общих принципов кодирования графической информации в качестве конкретного, достаточно общего случая графического объекта выберем изображение на экране телевизора. Это изображение состоит из некоторого количества горизонтальных линий – строк. А каждая строка в свою очередь состоит из элементарных мельчайших единиц изображения – точек, которые принято называть пикселами (picsel – PICture"S ELement – элемент картинки). Пиксел на цветном дисплее может иметь различную окраску, поэтому одного бита на пиксел недостаточно. Для кодирования 4-цветного изображения требуются два бита на пиксел, поскольку два бита могут принимать 4 различных состояния. Может использоваться, например, такой вариант кодировки цветов: 00 - черный, 10 - зеленый, 01 - красный, 11 - коричневый. На RGB-мониторах все разнообразие цветов получается сочетанием базовых цветов - красного (Red), зеленого (Green), синего (Blue), из которых можно получить 8 основных комбинаций:

R	G	B	цвет	R	G	B	цвет
0	0	0	черный	1	0	0	красный
0	0	1	синий	1	0	1	розовый
0	1	0	зеленый	1	1	0	коричневый
0	1	1	голубой	1	1	1	белый

Весь массив элементарных единиц изображения называют растром (лат. rastrum – грабли). Степень четкости изображения зависит от количества строк на весь экран и количества точек в строке, которые представляют разрешающую способность экрана или просто разрешение. Чем больше строк и точек, тем четче и лучше изображение. Достаточно хорошим считается разрешение 640x480, то есть 640 точек на строку и 480 строчек на экран.

Строки, из которых состоит изображение, можно просматривать сверху вниз друг за другом, как бы составив из них одну сплошную линию. После полного просмотра первой строки просматривается вторая, за ней третья, потом четвертая и т. д. до последней строки экрана. Так как каждая из строк представляет собой последовательность пикселов, то все изображение, вытянутое в линию, также можно считать линейной последовательностью элементарных точек. В рассматриваемом случае эта последовательность состоит из 640x480=307200 пикселов. Вначале рассмотрим принципы кодирования монохромного изображения, то есть изображения, состоящего из любых двух контрастных цветов – черного и белого, зеленого и белого, коричневого и белого и т. д. Для простоты обсуждения будем считать, что один из цветов – черный, а второй – белый. Тогда каждый пиксел изображения может иметь либо черный, либо белый цвет. Поставив в соответствие черному цвету двоичный код “0”, а белому – код “1” (либо наоборот), мы сможем закодировать в одном бите состояние одного пикселя монохромного изображения. А так как байт состоит из 8 бит, то на строчку, состоящую из 640 точек, потребуется 80 байтов памяти, а на все изображение – 38 400 байтов.

Однако полученное таким образом изображение будет чрезмерно контрастным. Реальное черно-белое изображение состоит не только из белого и черного цветов. В него входят множество различных промежуточных оттенков – серый, светло-серый, темно-серый и т. д. Если кроме белого и черного цветов использовать только две дополнительные градации, скажем светло-серый и темно-серый, то для того чтобы закодировать цветовое состояние одного пикселя, потребуется уже два бита. При этом кодировка может быть, например, такой: черный цвет – 002, темно-серый – 012, светло-серый – 102, белый – 112.

Общепринятым на сегодняшний день, дающим достаточно реалистичные монохромные изображения, считается кодирование состояния одного пикселя с помощью одного байта, которое позволяет передавать 256 различных оттенков серого цвета от полностью белого до полностью черного. В этом случае для передачи всего растра из 640x480 пикселов потребуется уже не 38 400, а все 307 200 байтов.

При записи изображения в память компьютера кроме цвета отдельных точек необходимо фиксировать много дополнительной информации – размеры рисунка, яркость точек и т. д. Конкретный способ кодирования всей требуемой при записи изображения информации образует графический формат. Форматы кодирования графической информации, основанные на передаче цвета каждого отдельного пикселя, из которого состоит изображение, относят к группе растровых или BitMap форматов (bit map – битовая карта). Растровое изображение представляет собой совокупность точек (пикселей) разных цветов. Наиболее известными растровыми форматами являются BMP, GIF и JPEG форматы.

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

Растровая же графика обладает существенным недостатком – изображение, закодированное в одном из растровых форматов, очень плохо “переносит” увеличение или уменьшение его размеров – масштабирование. Для решения задач, в которых приходится часто выполнять эту операцию, были разработаны методы так называемой векторной графики. В векторной графике, в отличие от основанной на точке – пикселе – растровой графики, базовым объектом является линия. При этом изображение формируется из описываемых математическим, векторным способом отдельных отрезков прямых или кривых линий, а также геометрических фигур – прямоугольников, окружностей и т. д., которые могут быть из них получены. Фирма Adobe разработала специальный язык PostScript (от poster script – сценарий плакатов, объявлений, афиш), служащий для описания изображений на базе указанных методов. Этот язык является основой для нескольких векторных графических форматов. В частности, можно указать форматы PS (PostScript) и EPS, которые используются для описания как векторных, так и растровых изображений, а также разнообразных текстовых шрифтов. Изображения и тексты, записанные в этих форматах, большинством популярных программ не воспринимаются, они могут просматриваться и печататься только с помощью специализированных аппаратных и программных средств. Итак, любое графическое изображение на экране можно закодировать c помощью чисел, сообщив, сколько в каждом пикселе долей красного, сколько - зеленого, а сколько - синего цветов.

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

Разбираемся с терминологией

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

Информация может быть закодирована в определённые символы и для того, чтобы её сохранить. В качестве примера можно привести результаты анализов, где содержатся показатели организма человека. Но наиболее популярным вопросом является такой: "Что такое кодирование и декодирование в информатике?" Искать ответ на него мы и будем.

О значении

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

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

Об алфавите

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

Давайте рассмотрим небольшой пример. Допустим, у нас есть два алфавита (А и Б), что состоят из конечного числа символов. Допустим, они выглядят следующим образом: А = {А0, А1, А2….А33}, Б = {Б0, Б1, Б3…Б34}. Элементы алфавита - это буквы. Тогда как их упорядоченный набор называется словом. У него есть определённая длина. Первая буква слова называется началом (префиксом), тогда как последняя - окончанием (постфиксом). Могут существовать различные правила построения конструкций. Например, одни системы кодирования информации требуют, чтобы был пропуск между словами, вторые обходятся без него. В целом алфавит необходим для построения универсальной системы отображения информации, её хранения, обработки и передачи. При этом предусматривается определённое соответствие между различными сигналами и элементами сообщений, которые в них зашифрованы.

Работа с данными

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

Допустим, что у нас есть А0 = {А, Б, В, Г} и Б0 = {1, 0}. Каким образом это можно представить компьютеру? А используя вот такую последовательность: А = 00, Б = 01, В = 10, Г = 11. Как видите, каждый символ имеет определённую кодировку. В компьютерную технику заносится справочная информация про алфавит кодирования, и она начинает ждать поступающих сигналов. Приходит нуль, за ним ещё один - ага, значит, это буква А. Если проводить параллели с набором слова в текстовом редакторе, то следует отметить, что будет передана не только одна буква, но и запущена соответствующая реакция на неё. Например, загорится определённая последовательность светодиодов монитора, где отображаются все введённые символы.

Специфика работы

Говоря про примеры кодирования и декодирования информации, следует отметить, что рассматриваемая система не является взаимно-однозначной. Например, букве А может соответствовать комбинация не только 00, но и 11, 10 или 01. Но при этом следует учитывать, что может быть только что-то одно. То есть за комбинацией закрепляется исключительно только определённый символ. Если схема кодирования подразумевает разделение любого слова на элементарные составляющие, то она называется разделимой. В случаях, когда одна буква не выступает в качестве начала другой, это префиксный подход. Это относится к вопросам программно-аппаратной составляющей. Определённое влияние на кодирование оказывает и архитектура, но из-за большого количества вариантов реализации рассматривать её довольно проблематично.

Побуквенное кодирование

Это наиболее простой подход. Если говорить про языки кодирования информации, то, пожалуй, это наиболее популярный вариант. В ограниченном варианте он был рассмотрен выше. Давайте узнаем, как выглядит код без разделителей. Допустим, у нас есть алфавит (исходный), в который помещены все русские буквы. Для кодирования используются десятичные цифры. Здесь А = 1, а Я = 33. Таким образом, последовательность букв АЯЯА можно передать как 133331. Если есть желание сделать алфавит равномерным, то необходимо внести определённые изменения. Так, для первых девяти букв придётся добавить по нулю. И рассмотренный нами пример АЯЯА превращается в 01333301.

Неравномерное кодирование

Рассмотренный ранее вариант считается удобным. Но в определённых случаях более умно сделать ставку на неравномерные коды. Это имеет смысл тогда, когда разные буквы в исходном тексте встречаются с различной частотой. Поэтому более частые символы имеет смысл кодировать короткими обозначениями, а редкие - длинными. Давайте построим бинарное дерево из букв русского алфавита. А на дополнение возьмём спецсимволы. Наиболее часто используются буквы, поэтому начинать мы будем с них: А - 0, Б - 1, В - 10, Г - 11 и так далее. И только после них уже будут использоваться знаки вопроса, процентов, двоеточия и прочие. Хотя, пожалуй, на первое место всё же следует поставить запятые и точки.

Об условии Фано

Теорема гласит, что любой код (префиксный и равномерный) допускает возможность однозначного кодирования. Допустим, что мы используем рассмотренный ранее пример с 01333301. Начинаем двигаться вправо. 0 ничего нам не даёт. А вот 01 позволяет идентифицировать букву А. Немного изменим начальный код и представим его как 01 333301. Далее выделяем первую Я, вторую и ещё одну А. В результате мы имеем 01 33 33 01. Хотя первоначально код был слитным, но сейчас мы можем с легкостью его декодировать, поскольку знаем, что в нём есть. А именно - А Я Я А. При этом заметьте, что он всегда расшифровывается однозначно, и никаких толкований в рамках принятой системы нет, благодаря чему можно обеспечить высокую достоверность передаваемой информации. Но как работают компьютеры?

Функционирование электронно-вычислительных машин

Кодирование и декодирование сигналов компьютерной техники базируется на использовании так называемых низких и высоких сигналов, которым в логическом измерении соответствуют нуль и единица. Что это значит? Допустим, у нас есть микроконтроллер. Если на один его вход поступает низкое напряжение в 1,5 В, то считается, что было передано значение логического нуля. Но если будет передано 5 В, то в соответствующую ячейку памяти будет записана единица. При этом необходимо добиться согласования источника информации с каналом связи. Вообще, при создании электроники необходимо учитывать большое количество различных моментов. Это и энергетические требования, и вид передаваемой информации (дискретная или непрерывная), и многое другое. При этом данные постоянно должны преобразовываться таким образом, чтобы они могли передаваться по каналам связи. Так, в случае с двоичной техникой сигналы представлены в виде напряжения, подаваемого на вход транзисторов или иных компонентов. Во время декодирования данные переводят сообщение в понятный для получателя вид.

Минимальная избыточность

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

Разбираем пример

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

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

В целом система несложная. Если работать с небольшими объемами данных. Но с современными компьютерами такое реализовать довольно проблематично из-за значительного количества информации.

Заключение

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

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

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.