7.4 Код Цезаря

Код k каждого символа заменяется кодом k+n, где n – константа кодирования. Следует иметь в виду, что среди символов кодовой таблицы имеются «странные» символы, которые не имеют собственного изображения, а при попытке их отображения на экране происходят странные вещи…

Коды 0..255, например.

«Странные» символы – с 0 до 20 в шестнадцатеричной системе

7.5 Упаковка текста

В нашем задачнике задача:

III.4.3. Написать программу, которая упаковывает (и восстанавливает упакованный) текст. Упаковка производится заменой всех повторяющихся более трех раз символов комбинацией #АВС, где А и В - цифры, составляющие целое положительное К, С - символ, который в исходном тексте был повторен ровно К раз.

Проблемы упаковки:

Если символ повторяется более 99 раз, он кодируется блоками по 99 + остаток.

Если символ # имеется в кодируемом тексте…

7.6 Код Хаффмана

Пример: Закодировать сообщение: АВАССДАСА

Способ 1:

А=00, В=01, С=10, Д=11

получаем 000100101011001000 (18)

Убедиться, что закодированный текст однозначно восстанавливается.

Любой ли код соответствует некоторому тексту?

Способ 2 (Код Хаффмана):

Частота: А(3)=0, С(2)=10, В(1)=110, Д(1)=111

получаем 0110010101110100 (16)

Принцип: наиболее часто используемые символы кодируются наиболее короткими кодами.

Убедиться, что закодированный текст однозначно восстанавливается.

Любой ли код соответствует некоторому тексту?

Сформулировать условие эффективности кодирования по Хаффману.

Сообщение – последовательность байт (8 бит) рассматриваем как последовательность пар бит (00, 01, 10, 11), пусть их (пар бит) n штук.

Статистика: Х1 – к1 раз, Х2 – к2, Х3 – к3, Х4 – к4, причем к1>=к2>=к3>=к4

Кодируем Х1 – 0, Х2 – 10, Х3 – 110, Х4 – 111.

Хотим, чтобы длина кода к1+2*к2+3*к3+3*к4 < 2*n;

Причем к1+к2+к3+к4=n. Откуда 2*к1+к2>n – условие реального сжатия.

1. При к1>n/2 – всегда происходит сжатие;

2. При к1<n/3 – сжатия не будет.

Задача: Испытать этот метод сжатия на файлах различного типа.

7.7 Код Хемминга

Для передачи 11-битного кода используется 15 бит.

Плюсиками обозначены номера столбцов в двоичном коде.

Знаки вопроса – это 1, если четное число единиц в позициях, помеченных знаком +, 0, если нечетное.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

?

+

+

+

+

+

+

+

2

?

+

+

+

+

+

+

+

4

?

+

+

+

+

+

+

+

8

?

+

+

+

+

+

+

+

Сумма номеров контрольных кодов (подчеркнуты) с нарушением четности дает номер разряда со сбоем.

Пусть нужно передать сообщение: 10101010101

Передаем ??1?010?1010101, с учетом четности 011101011010101.

Пусть при передаче изменился 13 бит (вместо 1 – 0), тогда по таблице нарушение четности произойдет в строках, помеченных числами 1, 4 и 8, их сумма – 13!