КОДИРОВАНИЕ ИНФОРМАЦИИ Информационные технологии, доц. Колыбанов К.Ю.

2 Кодирование vs Шифрование Кодирование и шифрование информации – достаточно близкие по смыслу термины. Тем не менее, они имеют существенные отличия. Шифрование – смысл текста должен быть ясен только определенным лицам, но скрыт от остальных. Кодирование – смысл текста должен быть ясен всем. Любой, кто знает способ кодирования, может понять смысл закодированной информации. КоДиРоВаНие RjLbHjDfYbt КоДиРоВаНие

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

4 Знак Знак – элемент конечного множества, обладающий информационным содержанием, отличающийся от других знаков данного множества. Запас знаков – конечное множество знаков. B = { ; ; ; ; ; ;} +–/*= A = { + ; – ; / ; * ; =}

5 Алфавит Алфавит – конечное и линейно упорядоченное множество знаков. A = { A ; B ; C ; D ; E ; F ; G ; H ; I ; J ; K ; L ; M ; N ; O ; P ; Q ; R ; S ; T ; U ; V ; W ; X ; Y ; Z } Z = { ; ; ; ; ; ; ; ; ; ; ; }

6 Подмножества знаков Множество А может включать подмножества, которые могут образовывать запасы знаков меньших алфавитов. A 16 = { 0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ; A ; B ; C ; D ; E ; F } D 10 = { 0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 } O 8 = { 0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 }

7 Бинарное множество Бинарное множество B содержит только два знака. B = { 0 ; 1 }

8 Слово Слово – конечная последовательность знаков. Множество слов над А – множество конечных последовательностей знаков А* над запасом знаков А. A = {а ; д ; м ; о} мода A* = {мода ; дама ; дома ; мама ; а ; да ; дом ; ад ; мадам}

9 Двоичные слова В – двоичный алфавит. n=3 { 000 ; 001 ; 010 ; 011 ; 100 ; 101 ; 110 ; 111 } B = { 0 ; 1 } B* = { 0 ; 1 }* В* – множество двоичных слов. Элементы множества В* называются двоичными словами длины n или n-битовыми словами.

10 Системы счисления Представление числа в позиционной системе счисления с основанием В имеет вид: Цифры а i входят в алфавит {a 1, a 2, a 3, …, a i }, содержащий ровно В элементов =1* * * =1* * *16 0 = =291 10

11 Непозиционные системы В римской системе счисления каждый знак имеет строго определенное числовое значение. MCLXVI = = = = I=1 V=5 X=10 L=50 C=100 M=1000

12 Кодировка ASCII ASCII – стандартная кодировка букв английского алфавита (American Standard Code for Information Interchange – Американский стандартный код для обмена информацией). Буквы других алфавитов (кроме латинского) представлены в расширенном 8-битном коде (исходный код – семибитный).

13 Многобайтовые кодировки Многобайтовые кодировки необходимы для кодирования текстов на языках, имеющих более 255 знаков в алфавите. Наиболее распространенной многобайтовой кодировкой является кодировка Unicode, поддержка которой включена во все современные операционные системы.

14 Кодирование информации Кодирование – отображение, переводящее множество символов (запас знаков) А в множество символов (запас знаков) В. Аналогично обозначается кодирование слов.

15 Декодирование информации Декодирование – обратное отображение символов множества В в множество А. В общем случае предполагается, что кодирование является обратимой операцией.

КОДЫ ПОСТОЯННОЙ ДЛИНЫ

17 Код постоянной длины Код постоянной длины – двоичное кодирование, отображающее каждый кодируемый знак на двоичное слово одинаковой длины. Если число знаков в алфавите А равно n, то можно построить код постоянной длины l (где l – наименьшее натуральное число, удовлетворяющее условию).

18 Пример кода постоянной длины Наиболее компактное кодирование достигается в том случае, когда число букв в алфавите равняется целой степени двойки. Для кодирования 32-х заглавных букв русского алфавита (за исключением буквы Ё) будет достаточно кода длины L = log 2 32 = 5

19 Расстояние Хэмминга Расстояние Хэмминга h(a,b) – количество позиций, в которых отличаются двоичные слова a и b одинаковой длины. Расстоянием Хэмминга h кода называется наименьшее расстояние Хэмминга между его кодовыми словами.

20 Код Грэя Код Грэя (одношаговый код) – код постоянной длины, в котором коды двух последовательных знаков из линейно упорядоченного алфавита А различаются точно в одном бите. Циклический код Грэя – код Грэя, в котором коды первого и последнего знаков из линейно упорядоченного алфавита А различаются точно в одном бите.

21 Надежность кодирования ТЕОРЕМА. Если код имеет расстояние Хэмминга h, то все ошибки, которые встречаются меньше чем в h битах, могут быть обнаружены. Все ошибки, появившиеся менее чем в h/2 битах, могут быть успешно устранены. Код с добавлением бита четности позволяет обнаружить единичную ошибку, поскольку для него h(a,b)=2. Бит четности равен нулю, если количество единиц в исходном слове четно (как в коде слова a= ), и равен единице, если нечетно (как в коде слова b= ).

22 Исправление единичных ошибок К исходному 4-битному коду слова b=b 1 b 2 b 3 b 4 добавляются три контрольных бита b 5 b 6 b 7. При декодировании вычисляются 3 бита, образующие код позиции ошибки.

КОДЫ ПЕРЕМЕННОЙ ДЛИНЫ

24 Коды переменной длины Код Морзе строится из трех знаков: (.) точка – короткая передача; (–) тире – длинная передача; (_) пробел – пауза в передаче. Код телефонных систем для импульсного набора цифр:

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

26 Полные префиксные коды При прочих равных условиях полные префиксные коды более компактны, чем неполные. Префиксный код называется полным, если добавление к нему любого нового кодового слова нарушает свойство префиксности. Так, например, с(х) является префиксом с(А) и с(В), а с(С) является префиксом с(у) и с(z).

ТЕОРЕМА КОДИРОВАНИЯ

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

29 Энтропия источника сообщений Количество информации, приносимое в среднем одним элементом сообщения (текста), по определению равно энтропии источника. Энтропия источника H является непрерывной функцией от p(i). При фиксированном n энтропия максимальна и равна log 2 n в случае, если все p(i) равны между собой.

30 Длина кодового слова l – длина i-го кодового слова. Средняя длина кодовых слов может быть определена следующим образом:

31 Теорема кодирования Для любого двоичного кодирования L H. Каждый источник может быть закодирован так, что разность L–H будет сколь угодно малой. Эффективность кода H / L 1 Избыточность кода (L – H) / L 0 При выборе метода кодирования следует стремиться к тому, чтобы разность (L–H) 0

32 Построение эффективных кодов Общее правило построения наиболее эффективного кода неизвестно. Однако, предложен ряд алгоритмов, приводящих к построению двоичных кодов с эффективностью, близкой к максимальной. Для повышения эффективности двоичного кода необходимо соблюдение следующих условий: 1. вероятности появления двоичных символов «0» и «1» должны быть равны; 2. вероятности появления «0» и «1» не должны зависеть от того, какие символы им предшествовали.