6. Кодирование

1. Теория информации

Кодирование

2. Кодирование

Кодирование в общем случае - это преобразование
алфавита исходного сообщения U{ui}, где i = 1 . . . M в
алфавит кодовых символов R{rj}, где j = 1 . . . K.
При этом обычно, но не обязательно, K < M или даже
K << M
Кодирование — преобразование дискретной
информации одним из следующих способов:
шифрование, сжатие, защита от шума.

3. Преобразующее кодирование

4. Код Грея

Комбинации кода Грея для десятичных чисел от 0 до 15

5. Статистическое кодирование

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

6. Статистическое кодирование

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

7.

Для случая оптимального статистического кодирования среднее время
передачи одного символа, при котором обеспечивается пропускная
способность канала Ck равно:

8. Кодирование Шеннона-Фано

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

9. Кодирование Шеннона-Фано

Пример построения кода Шеннона-Фано с помощью кодового дерева

10. Кодирование Шеннона-Фано

Для полученного кода среднее число двоичных символов,
приходящихся на одну букву, равно:

11. Кодирование по Хаффману

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

12. Кодирование по Хаффману

Все символы алфавита выписываются в ряд в порядке возрастания
(либо убывания) вероятности их появления в исходном сообщении.
Два символа с наименьшими вероятностями появления объединяются в
новый составной символ, вероятность которого полагается равной
сумме вероятностей составляющих символов. В результате
итеративного рекурсивного выполнения данного пункта строится
кодовое дерево, каждый узел которого имеет суммарную вероятность
всех узлов, находящихся ниже него.
От вершины дерева прослеживается путь к каждому листу, помечая
направление на каждом разветвлении (например – вниз - 0; вверх - 1).
Полученные последовательности для каждого листа и есть кодовые
слова, соответствующие исходным символам.

13. Кодирование по Хаффману

Пример построения кода Хаффмана с помощью кодового дерева

14. Кодирование по Хаффману

Пример построения кода Хаффмана с помощью кодового дерева

15. Арифметическое кодирование

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

16. Арифметическое кодирование

Введем понятие рабочего интервала – полуинтервала [a; b) с
расположенными на нем точками; при этом точки расположены таким
образом, что длины образованных ими отрезков равны вероятностям
появления исходных символов. На первом шаге алгоритма a = 0; b = 1.
Основной шаг алгоритма: для кодируемого символа ищется
соответствующий участок на рабочем интервале. Указанный участок
рекурсивно становится новым рабочим интервалом (т.е. мы
переразбиваем с использованием известных значений вероятностей
символов). Данная операция выполняется до конца исходного сообщения.
Результатом кодирования исходного сообщения является любое число (а
также длина его битовой записи), выбранное из финального рабочего
интервала12 При декодировании происходит сначала определение
первого символа, затем нормализация рабочего интервала,
соответствующего второму символу, затем нормализация рабочего
интервала для третьего символа и т.д.

17. Арифметическое кодирование. Пример

Пусть необходимо закодировать входное сообщение SWISS MISS с
заданными вероятностями появления символов, показанными на рис.
ниже:

18. Арифметическое кодирование. Пример

Процесс кодирования начинается со считывания первого символа
входного потока и выбора нового рабочего интервала,
соответствующего данному символу. В данном случае для первого
символа S получаем диапазон [0.5, 1).
После этого считывается новый символ W, которому соответствует
поддиапазон [0.4, 0.5) уже во втором рабочем интервале и т.д.

19. Арифметическое кодирование. Пример

Схема преставления новых границ символа W представлена на рис.
ниже.

20. Арифметическое кодирование. Пример

Указанная схема может быть записана в виде следующих формул:
NewHigh = OldLow + (OldHigh-OldLow)*HighRange(X)
NewLow = OldLow + (OldHigh-OldLow)*LowRange(X)
где OldLow – нижняя граница интервала, в котором представляется
текущий символ; OldHigh – верхняя граница интервала; HighRange(X) –
исходная верхняя граница кодируемого символа; LowRange(X) –
исходная нижняя граница кодируемого символа.

21. Арифметическое кодирование. Пример

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

22. Арифметическое кодирование. Пример

Теперь рассмотрим возможность восстановления закодированной
информации по восьми цифрам 71753375 и известным интервалам
символов. Первая из восьми цифр – это 7, т.е. 0,7. Она принадлежит
одному из заданных интервалов [0.5, 1), который соответствует символу
S. Поэтому первый декодированный символ – это S.

23. Арифметическое кодирование. Пример

Теперь вернемся к исходным интервалам и заметим, что второй
символ был представлен в интервале символа S, т.е. [0.5, 1). Но для
удобства декодирования его лучше представить в исходном интервале
[0, 1). Для этого достаточно интервал [0.5, 1) увеличить до начального,
т.е. умножить на два и границы сдвинуть на величину 0.5 · 2 = 1
Применяя данную схему к числу 0.71753375, получаем нижнюю границу
следующего закодированного символа как будто он был начальным
при кодировании: 0.71753375 ∗ 2 − 1 = 0.4350675.

24. Арифметическое кодирование. Пример

Полученное значение принадлежит диапазону [0.4, 0.5), который
соответствует символу W. Затем, также полученное число 0.4350675
следует нормировать, что в общем случае выполняется по формуле:
Code = (Code-LowRange(X))/(HighRange(X)-LowRange(X)), где Code –
текущее значение кода.

25. Арифметическое кодирование. Пример

Общая схема декодирования для исходного сообщения

26. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

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

27. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

28. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

29. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

Здесь L1(ACCBCAAABC) = 4.1 бит/сим.
Если не использовать сжатия, то L1(ACCBCAAABC) = 8 бит/сим. Для
рассматриваемой д. с.в. ранее были получены значения ML1(X) = 1.6
бит/сим и HX ≈ 1.523 бит/сим.

30. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

Теперь рассмотрим процесс декодирования сообщения ’A’0’C’100
’B’1001010100101. Здесь и далее символ в апостофах означает восемь
бит, представляющих собой запись двоичного числа, номера символа,
в таблице ASCII+. В начале декодирования дерево Хаффмена
содержит только escape-символ с частотой 0. С раскодированием
каждого нового символа дерево заново перестраивается.

31. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

32. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

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

33. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

34. Адаптивные алгоритмы сжатия. Кодирование Хаффмена

35. Криптография

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

36. Криптография

Простейшая система шифрования — это замена каждого знака
письма на другой знак по выбранному правилу. Юлий Цезарь,
например, заменял в своих секретных письмах первую букву
алфавита на четвертую, вторую — на пятую, последнюю — на третью и
т.п., т.е. A на D, B на E, Z на C и т.п.

37. Криптография

Шифры простой замены легко поддаются расшифровке, при знании
исходного языка сообщения, т.к. каждый письменный язык
характеризуется частотой встречаемости своих знаков. Например, в
английском языке чаще всего встречается буква E, а в русском — О.
Таким образом, в шифрованном подстановкой сообщении на
русском языке самому частому знаку будет с большой вероятностью
соответствовать буква О. Вероятность будет расти с ростом длины
сообщения.

38. Криптография

В шифрах-перестановках знаки сообщения специальным образом
переставляются между собой. Сообщение “ТЕОРИЯИНФОРМАЦИИ”,
используя строки длины 4, будет в шифрованном таким методом виде
выглядеть как “ТИФАЕЯОЦОИРИРНМИ”, потому что при шифровании
использовался следующий прямоугольник:
ТЕОР
ИЯИН
ФОРМ
АЦИИ

39. Криптография

Модификацией шифров-перестановок являются шифры-перестановки
со словомключом, которое определяет порядок взятия слов-столбцов.
Например, если для рассмотренного шифра взять ключ “РЫБА”, то
шифрованное сообщение будет выглядеть как
“РНМИОИРИТИФАЕЯОЦ”.

40. Криптография

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

41. Криптография

Например, рассмотренное ранее сообщение с ключом
“КИБЕРНЕТИКА” в шифрованном виде будет выглядеть как
“ЮОРЦЪНОБЮЪСШЙШОЪ”. Процесс шифровки описывается схемой:

42. Криптосистема с открытым\закрытым ключом

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

43. Криптосистема с открытым ключом

Пусть абоненты A и B решили организовать для себя возможность
секретной переписки. Для этого каждый из них независимо выбирает
два больших простых числа (pA1 , pA2 и pB1 , pB2 ), находит их
произведение (rA и rB), функцию Эйлера от этого произведения (ϕ(rA) и
ϕ(rB)) и случайное число (a и b), меньшее вычисленного значения
функции Эйлера и взаимно простое с ним. Кроме того, A из
уравнения aα ≡ 1 (mod ϕ(rA)) находит α (0 < α < ϕ(rA)), а B из уравнения
bβ ≡ 1 (mod ϕ(rB)) находит β (0 < β < ϕ(rB)). Затем A и B печатают
доступную всем книгу паролей вида:

44. Криптосистема с открытым ключом

Например, если пользователь книги паролей хочет отправить
сообщение m для B, то он использует ключ b из книги паролей для
получения шифрованного сообщения m1 по формуле m1 ≡ m^b 73
(mod rB), которое и отправляется B. B для дешифровки m1 использует
ключ β в формуле m1^β ≡ mb^β ≡ m (mod rB), т. к. bβ ≡ 1 (mod ϕ(rB)),
следовательно, bβ = kϕ(rB) + 1 для некоторого целого k и m^(kϕ(rB) +1) ≡
(m^ϕ(rB))^km ≡ m (mod rB), т.к. mϕ(rB) ≡ 1 (mod rB) по теореме ЭйлераФерма.

45. Криптосистема с открытым ключом

Пример. Пусть для A pA1 = 7 и pA2 = 23, тогда rA = pA1 pA2 = 161, ϕ(161) = 6 ∗
22 = 132, a = 7, α= 19 (из уравнения 7α ≡ 1 (mod 132)). Следовательно,
запись в книге паролей для A будет иметь вид A: 161, 7. Если кто-то
захочет отправить A секретное сообщение m = 3, то он должен
сначала превратить его в шифровку m1 по формуле m1 ≡ 3^7 ≡ 94
(mod 161). Когда A получит m1 = 94 он дешифрует его по формуле m ≡
94^19 ≡ 3 (mod 161).