Как известно, работа, а также распространение ЭВМ нуждается в более основательном подходе к системам передачи данных. Однако в данном случае наблюдается проблема, которая связана с тем, как изменить обыкновенную информацию, понятную человеку, чтобы с ней могла работать машина.
Определенной частью решения данной задачи выступает кодирование и декодирование информации.
Что означает понятие «кодирование»?
Код представляет собой совокупность символов, соответствующих определенным элементам информации либо характеристикам. Что касается самого процесса, при котором этот код составляется, он имеет название кодирования. Кодирование информации осуществляется с той целью, чтобы представить данные компактно и удобно, что необходимо при передаче и обработки на вычислительной технике. В ходе кодирования обработка состоит в поиске, сортировании, а также упорядочении существующих данных. Результатом этих процессом выступают выходные коды. После декодирования они являются конечной целью в обмене информацией между различными ЭВМ.
Что означает понятие «декодирование»?
Декодирование представляет собой операцию, процесс которой обратный кодированию. Таким образом, при нем по заранее указанному коду происходит поиск соответствующей информации или объекта. В качестве примера можно предложить ситуацию с телефонами. Когда выполняется набор номера, он поступает на автоматизированную телефонную станцию, где и декодируется,. В результате техника понимает, что требуется абоненту. Стоит отметить, что декодирование является достаточно сложным процессом, однако если задуматься, понять, как все происходит, несложно.
Как выполняется процесс кодирования?
Нужно сразу заметить, что он может осуществляться вручную или автоматически. Таким образом, при ручном кодировании применяются заранее составленные каталоги, где обозначается, что чему соответствует. После этого знаки наносятся на перфокарту либо перфоленту, они вводятся в ЭВМ, а информация перекодируется в машинный код.
Большое распространение получил автоматический метод кодирования. В ходе данного процесса все записывается при помощи слов, общепринятых обозначений, а также цифр в созданный на ЭВМ документ. Итоговый файл поступает для обработки в специальный автомат. Он осуществляет кодирование та, что получается максимально короткий машинный код. Он представляет удобство при поиске, сортировке и обработке данных. Автоматическое кодирование выполняется при условии наличия словаря, где конкретному коду соответствует одно слово.
Такой подход ведет к отсутствию необходимости в разделения информации по ее смыслу. Ее обработка происходит в понятном машинам виде. Таким образом, с ней можно уверенно работать, акцентируя процессорную мощь на более необходимые действия. Работа ЭВМ с такой информацией происходит за счет наличия ключевого кода. Он представляет собой единый массив информации, которая используется для всех решаемых задач. Процесс поиска выполняется на основании однозначности отношения признаков к предмету. Обычно он происходит по битовому адресу, однако способен применяться и порядковый регистрационный номер при отсутствии дополнительной информации. Стоит также указать на еще один способ кодирования, при котором происходит сортировка данных по их содержанию. Иными словами, осуществляется классификация, где роль играют только основные определяющие признаки.
Как происходит декодирование?
Декодирование информации находится в зависимости от способа кодирования, а также его типа и характеризующих особенностей. Таким образом, получить требуемую информацию, когда в качестве указателя выбрана другая техника, достаточно сложно. В данном случае важным является степень защищенности, а также защита данных. При получении электрических импульсов техника выполняет проверку, способна ли она их обработать.
Декодирование представляет собой достаточно сложный процесс, поскольку в ходе передачи данных могут быть потери сигналов, что ведет к негативным последствиям. Если получен утвердительный ответ, техника на основе определенных признаков проводит декодирование полученной информации в соответствии с существующими каталогами данных. Когда это невозможно, ЭВМ имеется процедура игнорирования, дающая возможность отсортировывать множество ненужной для него информации.
Виды кодов
Когда символы соответствуют конкретному предмету или характеристике, данный код является прямым. Если он имеет информацию о требуемом адресе, указывающем на местоположение нужных сведений, такой код называется адресным. Он используется при поиске больших массивов информации. Код может быть представлен в виде двоичного кодирования, машинного слова, байта, страницы и блока.
Теория кодирования информации является одним из разделов теоретической информатики. К основным задачам, решаемым в данном разделе, необходимо отнести следующие:
- разработка принципов наиболее экономичного кодирования информации;
- согласование параметров передаваемой информации с особенностями канала связи;
- разработка приемов, обеспечивающих надежность передачи информации по каналам связи, т. е. отсутствие потерь информации.
Первая задача - кодирование информации - касается не только передачи, но и обработки, и хранения информации, т. е. охватывает широкий круг проблем; частным их решением будет представление информации в компьютере.
Кодирование - это переход от одного алфавита (буквенного кода) к другому.
Пусть 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 минуты .
Для выполнения задания 5 по информатике необходимо знать:
Кодирование - это перевод информации из одной формы представления в другую.
Декодирование - это обратный процесс кодированию.
Кодирование бывает равномерное и неравномерное ;
- при равномерном кодировании все символы кодируются кодами равной длины; Например : ASCII или Unicode.
- при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование, связанные с появлением неоднозначности кода. Например : Символ А кодируется цифрой 0, Б - последовательностью 01, а В - последовательностью 1. Итак, например, сообщение "011" может быть раскодировано, как AВВ или БВ. При неоднозначность кода информацию можно декодировать по разному.
Для однозначного декодирования код должен удовлетворять условию Фано : никакое кодовое слово не может быть началом другого кодового слова.
Но голосом ведь всем её не донесёшь. Поэтому с давних времён был важен момент кодирования данных, чтобы они могли был прочитаны теми, для кого предназначалось. Постепенно также стало актуальным их шифрование. Необходимо было поместить в сообщение информацию, которая была понятна своим и не раскрыла смысла перед чужими. Обо всём этом мы и поговорим, выясняя, что такое кодирование и декодирование.
Разбираемся с терминологией
Без этого никак. Когда говорят о закодированном тексте, то это значит, что ему был сопоставлен другой набор символов. Это может быть использовано для увеличения надежности или же по той простой причине, что канал может использовать только ограниченное количество символом. Например, двоичный код, на котором работают современные компьютеры, построен на нулях и единицах.
Информация может быть закодирована в определённые символы и для того, чтобы её сохранить. В качестве примера можно привести результаты анализов, где содержатся показатели организма человека. Но наиболее популярным вопросом является такой: "Что такое кодирование и декодирование в информатике?" Искать ответ на него мы и будем.
О значении
Ранее процесс кодирования и декодирования информации играл вспомогательную роль и не рассматривался как отдельное направление математики. Но с появлением электронно-вычислительных машин ситуация существенно изменилась. Сейчас кодирование является центральным вопросом во время решения широкого спектра практических задач в программировании и поэтому пронизывает все информационные технологии. Так, с его помощью:
- Защищается информация от несанкционированного доступа.
- Обеспечивается помехоустойчивость при передаче по каналам связи данных.
- Представляется информация произвольной природы (графика, текст, числа) в памяти компьютера.
- Сжимается содержимое баз данных.
Об алфавите
Говоря о том, что такое кодирование и декодирование, сложно обойти вниманием основу всего этого. А именно, алфавит. Выделяют два вида - исходный и кодовый. В первом имеется начальная информация. Под кодовым подразумеваются изменённые данные, которые тем не менее могут при наличии ключа передать нам зашифрованное содержимое. В информатике для этого используется двоичный код, в основу которого положен алфавит, состоящий из нуля и единицы.
Давайте рассмотрим небольшой пример. Допустим, у нас есть два алфавита (А и Б), что состоят из конечного числа символов. Допустим, они выглядят следующим образом: А = {А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 В, то в соответствующую ячейку памяти будет записана единица. При этом необходимо добиться согласования источника информации с каналом связи. Вообще, при создании электроники необходимо учитывать большое количество различных моментов. Это и энергетические требования, и вид передаваемой информации (дискретная или непрерывная), и многое другое. При этом данные постоянно должны преобразовываться таким образом, чтобы они могли передаваться по каналам связи. Так, в случае с двоичной техникой сигналы представлены в виде напряжения, подаваемого на вход транзисторов или иных компонентов. Во время декодирования данные переводят сообщение в понятный для получателя вид.
Минимальная избыточность
На практике оказалось, что чрезвычайно важным является, чтобы код сообщения имел минимальную длину. Первоначально может показаться, какая разница - шесть, восемь или шестнадцать бит используется для кодирования? Но различия несущественны, если используется одно слово. А если миллиарды? Благо, можно подстроить алфавитное кодирование под все выдвигаемые требования. Но если про множество ничего неизвестно, то в таком случае сформулировать задачу оптимизации довольно трудно. Но на практике, как правило, всё же можно получить дополнительную информацию. Рассмотрим небольшой пример. Допустим, у нас есть сообщение, представленное на естественном языке. Но оно закодировано, и мы не можем прочитать его. Что нам поможет в задаче расшифровки? Как один из возможных вариантов - листок бумаги, на котором распределена вероятность появления букв. Благодаря этому построение оптимального кода в плане де/кодирования становится возможным с использованием точной математической формулировки и строгого решения.
Разбираем пример
Допустим, что у нас есть определённая разделимая схема алфавитного кодирования. Тогда все производные, что представляют собой упорядоченный набор, тоже будет иметь это свойство. При этом если длина элементарных кодов равна, то их перестановка не влияет на длину всего сообщения. Но если размер передаваемой информации напрямую зависит от того, какая последовательность букв, то, значит, были использованы составляющие различной протяженности. При этом, если есть конкретное сообщение и схема его кодирования, то можно подобрать такое решение задачи, когда его длина будет минимальной. Как этого достичь? Давайте рассмотрим подход с использованием алгоритма назначения элементарных кодов, позволяющего результативно подойти к решению задачи эффективности:
- Следует отсортировать буквы в порядке убывания количественного вхождения.
- Нужно разместить элементарные коды в порядке увеличения их длины.
- И как завершение, необходимо разместить составляющие в оптимальном порядке, чтобы наиболее частые символы занимали меньше всего места.
В целом система несложная. Если работать с небольшими объемами данных. Но с современными компьютерами такое реализовать довольно проблематично из-за значительного количества информации.
Заключение
Вот мы и рассмотрели, что такое система кодирования и декодирования информации, какой она может быть, что сейчас существует в информатике, а также множество иных вопросов. Но всё же следует понимать, что эта тема является чрезвычайно объемной, одной статьи для этого недостаточно. Как продолжение темы можно рассмотреть шифрование данных, криптографию, изменение отображения информации в различной электронике, уровни её обработки и множество других моментов. Но отрасль компьютерных наук по праву считается одной из самых сложных, поэтому изучить всё это быстро не получится. К тому же теоретические знания здесь ой как не равны практическим умениям. А именно последние и обеспечивают качественный результат.
Описание презентации по отдельным слайдам:
1 слайд
Описание слайда:
Кодирование и декодирование информации Выполнила: учитель информатики МОУ Сургутской СОШ Плешанова Татьяна Сергеевна *
2
слайд
Описание слайда:
Кодирование и декодирование Для обмена информацией с другими людьми человек использует естественные языки. Наряду с естественными языками были разработаны формальные языки для профессионального применения их в какой-либо сфере. Представление информации с помощью какого-либо языка часто называют кодированием. Код - набор символов (условных обозначений) для представления информации. Код - система условных знаков (символов) для передачи, обработки и хранения информации(со общения). Кодирование - процесс представления информации (сообщения) в виде кода. Все множество символов, используемых для кодирования, называется алфавитом кодирования. Например, в памяти компьютера любая информация кодируется с помощью двоичного алфавита, содержащего всего два символа: 0 и1. Декодирование- процесс обратного преобразования кода к форме исходной символьной системы, т.е. получение исходного сообщения. Например: перевод с азбуки Морзе в письменный текст на русском языке. В более широком смысле декодирование - это процесс восстановления содержания закодированного сообщения. При таком подходе процесс записи текста с помощью русского алфавита можно рассматривать в качестве кодирования, а его чтение - это декодирование. *
3
слайд
Описание слайда:
Способы кодирования информации Для кодирования одной и той же информации могут быть использованы разные способы; их выбор зависит от ряда обстоятельств: цели кодирования, условий, имеющихся средств. Если надо записать текст в темпе речи - используем стенографию; если надо передать текст за границу - используем английский алфавит; если надо представить текст в виде, понятном для грамотного русского человека, - записываем его по правилам грамматики русского языка. «Здравствуй, Саша!» «Zdravstvuy, Sasha!» *
4
слайд
Описание слайда:
Способы кодирования информации Выбор способа кодирования информации может быть связан с предполагаемым способом ее обработки. Покажем это на примере представления чисел - количественной информации. Используя русский алфавит, можно записать число "тридцать пять". Используя же алфавит арабской десятичной системы счисления, пишем «35». Второй способ не только короче первого, но и удобнее для выполнения вычислений. Какая запись удобнее для выполнения расчетов: "тридцать пять умножить на сто двадцать семь" или "35 х 127"? Очевидно - вторая. *
5
слайд
Описание слайда:
Шифрование сообщения В некоторых случаях возникает потребность засекречивания текста сообщения или документа, для того чтобы его не смогли прочитать те, кому не положено. Это называется защитой от несанкционированного доступа. В таком случае секретный текст шифруется. В давние времена шифрование называлось тайнописью. Шифрование представляет собой процесс превращения открытого текста в зашифрованный, а дешифрование - процесс обратного преобразования, при котором восстанавливается исходный текст. Шифрование - это тоже кодирование, но с засекреченным методом, известным только источнику и адресату. Методами шифрования занимается наука под названием криптография. *
6
слайд
Описание слайда:
Оптический телеграф Шаппа В 1792 году во Франции Клод Шапп создал систему передачи визуальной информации, которая получила название «Оптический телеграф». В простейшем виде это была цепь типовых строений, с расположенными на кровле шестами с подвижными поперечинами, которая создавалась в пределах видимости одно от другого. Шесты с подвижными поперечинами - семафоры - управлялись при помощи тросов специальными операторами изнутри строений. Шапп создал специальную таблицу кодов, где каждой букве алфавита соответствовала определенная фигура, образуемая Семафором, в зависимости от положений поперечных брусьев относительно опорного шеста. Система Шаппа позволяла передавать сообщения на скорости два слова в минуту и быстро распространилась в Европе. В Швеции цепь станций оптического телеграфа действовала до 1880 года. *
7
слайд
Описание слайда:
Первый телеграф Первым техническим средством передачи информации на расстояние стал телеграф, изобретенный в1837 году американцем Сэмюэлем Морзе. Телеграфное сообщение - это последовательность электрических сигналов, передаваемая от одного телеграфного аппарата по проводам к другому телеграфному аппарату. Изобретатель Сэмюель Морзе изобрел удивительный код(Азбука Морзе, код Морзе, «Морзянка»), который служит человечеству до сих пор. Информация кодируется тремя «буквами»: длинный сигнал (тире), короткий сигнал (точка) и отсутствие сигнала (пауза) для разделения букв. Таким образом, кодирование сводится к использованию набора символов, расположенных в строго определенном порядке. Самым знаменитым телеграфным сообщением является сигнал бедствия "SOS" (Save Our Souls - спасите наши души). Вот как он выглядит: « – – – » *
8
слайд
Описание слайда:
Азбука Морзе A − И P − Ш − − − − Б − Й − − − С Щ − − − В − − К − − Т − Ъ − − − Г − − Л − У − Ь − − Д − М − − Ф − Ы − − − Е H − Х Э − Ж − О − − − Ц − − Ю − − З − − П − − Ч − − − Я − − *
9
слайд
Описание слайда:
Азбука Морзе 1 − − − − 9 − − − − 2 − − − 0 − − − − − 3 − − Точка 4 − Запятая − − − 5 / − − 6 ? − − 7 − − ! − − − − 8 − − − @ − − − *
10
слайд
Описание слайда:
Неравномерность кода − − − − − − Характерной особенностью азбуки Морзе является переменная длина кода разных букв, поэтому код Морзе называют неравномерным кодом. Буквы, которые встречаются в тексте чаще, имеют более короткий код, чем редкие буквы. Это сделано для того, чтобы сократить длину всего сообщения. Но из-за переменной длины кода букв возникает проблема отделения букв друг от друга в тексте. Поэтому для разделения приходится использовать паузу (пропуск). Следовательно, телеграфный алфавит Морзе является троичным, т.к. в нем используются три знака: точка, тире, пропуск. *
11
слайд
Описание слайда:
Первый беспроводной телеграф (радиоприемник) 7 мая 1895 года российский ученый Александр Степанович Попов на заседании Русского Физико-Химического Общества продемонстрировал прибор, названный им "грозоотметчик", который был предназначен для регистрации электромагнитных волн. Этот прибор считается первым в мире аппаратом беспроводной телеграфии, радиоприемником. В 1897 году при помощи аппаратов беспроводной телеграфии Попов осуществил прием и передачу сообщений между берегом и военным судном. В 1899 году Попов сконструировал модернизированный вариант приемника электромагнитных волн, где прием сигналов (азбукой Морзе) осуществлялся на головные телефоны оператора. В 1900 году благодаря радиостанциям, построенным на острове Гогланд и на российской военно-морской базе в Котке под руководством Попова, были успешно осуществлены аварийно-спасательные работы на борту военного корабля "Генерал-адмирал Апраксин", севшего на мель у острова Гогланд. В результате обмена сообщениями, переданным методом беспроводной телеграфии, экипажу российского ледокола Ермак была своевременно и точно передана информация о финских рыбаках, находящихся на оторванной льдине. *
12
слайд
Описание слайда:
Телеграфный аппарат Бодо Равномерный телеграфный код был изобретен французом Жаном Морисом Бодо в конце XIX века. В нем использовалось всего два разных вида сигналов. Не важно, как их назвать: точка и тире, плюс и минус, ноль и единица. Это два отличающихся друг от друга электрических сигнала. Длина кода всех символов одинаковая и равна пяти. В таком случае не возникает проблемы отделения букв друг от друга: каждая пятерка сигналов - это знак текста. Поэтому пропуск не нужен. Код называется равномерным, если длина кода всех символов равна. Код Бодо - это первый в истории техники способ двоичного кодирования, информации. Благодаря этой идее удалось создать буквопечатающий телеграфный аппарат, имеющий вид пишущей машинки. Нажатие на клавишу с определенной буквой вырабатывает соответствующий пятиимпульсный сигнал, который передаетсяпо линии связи. В честь Бодо была названа единица скорости передачи информации - бод. В современных компьютерах для кодирования текста также применяется равномерный двоичный код. Telex Это интересно: Отель, не имеющий телекса, не может иметь рейтинг "пять звезд". *
