3: Процесс преобразования информации. Кодирование информации - shikardos.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
3: Процесс преобразования информации. Кодирование информации - страница №1/1

Тема 3: Процесс преобразования информации. Кодирование информации.
Процесс преобразования информации

Информация

Сообщение

Сигнал


Кодирование – преобразование информации в сообщение.

Более широко под кодированием понимают процесс преобразования информации из одной формы в другую.


Примеры кодов


  • Обычный толковый словарь – разновидность кода;

  • Звуки издаваемые при произнесении слова – это код мы называем речью;

  • Письменность (алфавит) или рисунок;

  • Десятичная позиционная система счисления - это способ кодирования нату­ральных чисел. Римские цифры - другой способ кодирования натуральных чисел, причем гораздо более наглядный и естественный: палец - I, пятерня - V, две пятерни -X.

  • Декартовы координаты - способ кодирования геометрических объектов числами;

  • Код Морзе;

  • Кодирование Брайля;

  • Штрих коды.


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

  1. представление данных произвольной природы (например чисел, текста, гра­фики) в памяти компьютера;

  2. защита информации от несанкционированного доступа;

  3. обеспечение помехоустойчивости при передаче данных по каналам связи;

  4. сжатие информации в базах данных.


Свойства, которые требуются от кодирования, бывают самой разнообразной природы:

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

  • помехоустойчивость, или исправление ошибок;

  • заданная сложность (или простота) кодирования и декодирования.


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

Кодирование может сопоставлять код всему сообщению из множества S как единому целому или же строить код сообщения из кодов его частей. Элемен­тарной частью сообщения является одна буква алфавита А.



Алфавитное (или побуквенное) кодирование задается схемой (или таблицей ко­дов).

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

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

Равномерные и неравномерные коды. Разделимые и неразделимыекоды. Оптимизация длины кода. Алгоритм Фано. Алгоритм Хаффмена.
Пример1. Код Морзе:

Сэмюэл Финли Бриз Морзе (Samuel Finley Breese Morse) (1791 – 1872.).



Код Морзе – неравномерный, двоичный неразделимый код.

А

A

∙ ─

К

K

─ ∙ ─

Ф

F

∙ ∙ ─ ∙

Б

B

─ ∙ ∙ ∙

Л

L

∙ ─ ∙ ∙

Х

H

∙ ∙ ∙ ∙

В

W

∙ ─ ─

М

M

─ ─

Ц

C

─ ∙ ─ ∙

Г

G

─ ─ ∙

Н

N

─ ∙

Ч




─ ─ ─ ∙

Д

D

─ ∙ ∙

О

O

─ ─ ─

Ш




─ ─ ─ ─

Е

E



П

P

∙ ─ ─ ∙

Щ

Q

─ ─ ∙ ─

Ж

V

∙ ∙ ∙ ─

Р

R

∙ ─ ∙

Ъ,Ь

X

─ ∙ ∙ ─

З

Z

─ ─ ∙ ∙

С

S

∙ ∙ ∙

Ы

Y

─ ∙ ─ ─

И

I

∙ ∙

Т

T



Ю




∙ ∙ ─ ─

Й

J

∙ ─ ─ ─

У

U

∙ ∙ ─

Я




∙ ─ ∙ ─


Пример 2. Код Брайля (код для слепых):

Луи Брайль (Louis Braille) родился в 1809 г. во Франции.

В шрифте Брайля символы письменного языка - буквы, цифры и знаки препинания - кодируются комбинациями от одной до шести выпуклых точек, расположенных в ячейке раз­мерами 2×3. Точки в ячейке нумеруются с 1 по 6:

1 О О 4


2 О О 5

3 О О 6


Для выдавливания точек используются специальные пишущие машинки и станки.

Для нас самое интересное в шрифте Брайля то, что он яв­ляется двоичным (равномерным, разделимым). Любая точка может пребывать в одном из двух состояний: плоская или выпуклая. и комбинаторном анализе. Общее число комбинаций шести точек, каждая из которых может быть плоской или выпуклой, равно 2x2x2x2x2x2 = 2'' = 64.

Следовательно, система Брайля содержит 64 различных кода. Вот как они выглядят:

Шрифт Брайля для строчных букв латинс­кого алфавита:





Помехоустойчивое кодирование

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



Кодирование с исправлением ошибок. Возможность исправления ошибок. Кодовое расстояние. Код Хемминга.
Сжатие данных

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



Предварительное построение словаря. Алгоритм Лемпела-Зива
Шифрование

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



Шифрование - это кодирование данных с целью защиты от несанкционирован­ного доступа.

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

Область знаний о шифрах, методах их создания и раскрытия называется кри­птографией (или тайнописью).

Свойство шифра противостоять раскрытию называется криптостойкостъю (или надежностью) и обычно измеряется сложностью алгоритма дешифрации.



Рекомендуемая литература:

  1. Информатика. Базовый курс / Сименович С.В. и др. – СПб: Питер, 2001. – 640 с.

  2. Вычислительные системы, сети и телекоммуникации / В.Л. Бройдо – СПб.: Питер, 2002. - 688 с.

  3. Введение в компьютерные науки. Общий обзор, 6-е издание / Брукшир, Дж., Гленн.: Пер. С англ. – М.: Издательский дом «Вильямс», 2001. – 688 с.

  4. Код. / Петцольд Ч. – М.: Издательско-торговый дом «Русская Редакция». 2001.- 512 с.

  5. Дискретная математика для программистов / Ф.А. Новиков. – СПб.: Питер, 2001.– 304с.