pri_cod2

Избыточность этой схемы равна 3814 = 197 ¼ 2:71. В результате кодированиия сообщения кодом Хаффмана получим последовательность из 14 ¢ 197 = 38 двоичных разрядов.

Отметим, что соответствующий равномерный код для имеет избыточность 3 (все слова в этом коде имеет длину 3). При кодировании с помощью азбуки Морзе избыточность равна 3914 ¼ 2:79; если же учесть, что после каждого кодового слова следует пауза (как признак конца буквы), то избыточность возрастает до 3:79 . Отметим также, что если различать буквы “П“ и “п“, то результаты изменятся.

Сжатие файлов с помощью метода Хаффмана особенно эффективно, когда небольшая группа символов встречается в файле часто, а остальные символы редко (так бывает, например, в графических файлах).

Пример 14. Пусть имеется соообщение S из 200 символов алфавита

A = fa; b; c; d; e; f; g; hg и K = (22; 3; 60; 1; 5; 3; 2; 4) вектор относительных частот символов. Тогда код Хаффмана имеет такую схему кодирования:

Избыточность этой схемы равна 1:85. Закодрованное сообщение будет состоять из 200 ¢ 1:85 = 370 двоичных разрядов. Отметим, что соответствующий равномерный бинарный код имеет избыточность, не меньшую 3, поэтому при кодировании сообщения S равномерным бинарным кодом получим не менее 600 двоичных разрядов.

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

21

Пример 15. Пусть задано сообщение

S = \01001110010101010111011101011101101\;

состоящее из 35 двоичных разрядов. Разобьем его на блоки длины 2:

S = \01 00 11 10 01 01 01 01 01 11 01 11 01 01 11 01 10 1\:

Последний неполный блок имеет длину 1. За входной алфавит примем A = f\00\; \01\; \10\; \11\; \1\g. Подсчитав, сколько раз каждый блок входит в сообщение, получим вектор относительных частот K = (1; 10; 2; 4; 1). Применив алгоритм Хаффмана, получим оптимальную схему кодирования:

00 - 1110, 01 - 0, 10 - 110, 11 - 10, 1 - 1111.

При кодировании сообщения S получим последовательность длины 32 из нулей и единиц. Поэтому коэффициент сжатия равен 3532 ¼ 1:09.

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

S = \01001110000110010111011101111101101\;

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

Опишем еще один метод сжатия данных. Этот метод являются разновидностью так называемого “кодера с памятью“. При кодировании очередного символа в этом методе учитывается предыдущий символ.

Пусть S кодируемое сообщение и A = fa1; a2; : : : ; arg множество различных символов, входящих в S. Пусть в сообщении S символ ai предшествует символу aj kij раз, где 1 · i; j · r. Обозначим через A(ai) множество тех символов aj 2 A, для которых kij > 0. Из чисел kij составляем вектор частот K(ai) появления символов aj сразу после символа ai.

Наконец, по вектору частот K(ai) строим схему кодирования (§(ai)) (обычно методом Хаффмана).

22

В закодированном сообщении должно быть также указано с какого символа начинается исходное сообщение (например, в начале сообщения можно поместить ascii-код первого символа кодируемого сообщения). Если в кодируемом тексте за символом x непосредственно следует символ , то код символа y выбирается из алфавита A(x). Поясним сказанное примером:

Пример 16. Построим набор схем кодирования для сообщения S = “Мелкооптоваяtторговля“,

где \t\ символ пробела. Ясно, что A = fМ, е, л, к, о, п, т, в, а, я,t, р, гg. Первая буква “М“ алфавита A встречаются в сообщении только один раз. После нее может встретиться только буква е, поэтому A(“М“) = fеg. Схема кодирования §(“М“) содержит только одну запись

e ¡ 0:

Аналогично устроены схемы кодирования для букв, которая встречается в S только один раз (и для символа t).

Буква “е“ встречается два раза. За ней может следовать или буква “к“ или буква “я“, поэтому A(“е“) = fк, яg, а схема кодирования §(“е“) выглядит так:

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

23

“М“), а затем перечислить все нули и единицы из третьей строки (слева направо и без пробелов).

Поясним почему символы с номерами 5 и 6 получают разные коды, хотя в обоих случаях кодируется буква “о“. Дело в том, что код пятой буквы выбирается из схемы (§(\к\)), а код шестой буквы из схемы (§(\о\)).

Проверить:

Построить для сообщения из примера 14 13 код Хаффмана и найти его избыточность. Какую длину будует иметь закодрованное сообщение?

– Ссылки!!! http://ru.wikipedia.org/wiki/Сжатие_данных

Книга - Методы сжатия данных compression.ru/book/Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ ...

2Задачи

1. Построить оптимальный бинарный код для сообщения “Литература“ а) методом Шеннона-Фано; б) упрощенным методом Шеннона-Фано; в) методом Хаффмана. Построить теми же методами тернарный и четверичный коды.

2.Построить равномерный код для сообщения “Информация“ и найти избыточность этого кода.

3.Будет ли оптимальным код со следующей схемой кодирования

n a - 1011, b - 0, c - 11, d - 100, e - 1011.

24

2.Линейные коды над конечными полями

Валгебре полем называют множество P с операциями сложения и умножения, если выполнены следующие свойства:

(1)Сложение и умножение коммутативно и ассоциативно: a + b = b + a, ab = ba, (a + b) + c = a + (b + c) и (ab)c = a(bc) для любых элементов a; b; c 2 P .

(2)Умножение дистрибутивно относительно сложения: (a + b)c = ac + bc для любых a; b; c 2 P .

(3)Для любых элементов a; b 2 P уравнение a + x = b имеет в P единственное решение.

(4)Если a; b 2 P и a 6= 0, то уравнение ax = b имеет в P единственное решение.

Всвойстве (4) символом “0“ обозначен нулевой элемент поля, который можно определить как такой (единственный) элемент поля, для которого c + 0 = c при всех c 2 P . Поле всегда содержит также единицу, которая

обозначается символом “1“ и удовлетворяет равенству c ¢ 1 = c при любом c 2 P .

Полями являются множества R, Q и C действительных, рациональных

икомплексных чисел соответственно с обычными операцияи сложения и умножения. Множество Z целых чисел поля не образует поскольку в нем не выполнено свойство (4) например, уравнение 3x = 7 с элементаами из Z не имеет корня в Z.

Втеории кодирования важную роль играют конечные поля, то есть поля, состоящие из конечного числа элементов. Простейшим (но очень важным) примером конечного поля является поле Zp = f0; 1; 2; : : : ; p ¡ 1g, где pпростое число.

Конечные поля называют также полями Галуа (по имени создателя теории конечных полей Эвариста Галуа [1811-1832]). Поле, состоящее из q элементов, обозначается GF (q). Доказано, что такие поля существуют тогда

итолько тогда, когда q = pr, где p простое и r ¸ 1 целое. Для построения

25

поля из pr элементов необходимо выбрать неприводимый над полем Zp многочлен g(x) степени r. Этот многочлен называется порождающим-образующим

N

многочленом поля F . Обычно g(x) выбирают так, чтобы его старший коэффициент равнялся единице (многочлены с таким свойством называют нормированными).

Напомним, что многочлен называется неприводимым над данным полем, если его нельзя представить в виде произведения двух многочленов положительной степени с коэффициентами из этого поля. Если указанное представление возможно, то многочлен называют приводимым. Например, многочен x2 ¡ 3 приводим над полем R действительных чисел (поскольку x2 ¡3 = (x ¡p3)(x + p3)), но неприводим над полем Q рациональных чисел (так как его нельзя представить в виде (ax + b)(cx + d), где a; b; c; d 2 Q).

Элементами конечного поля F = GF (pr) являются многочлены от переменной x, степень которых меньше r, а каждый коэффициент является целым неотрицательным числом, меньшим p. Таким образом, любой элемент поля F имеет вид

где ai целое число и 0 · ai < p при любом i. Элементы поля F обозначаются a(x), b(x), : : : (или, более коротко, a, b, : : :).

Сопоставляя элементу a(x) вектор a = (a0; a1; : : : ; ar¡1), получим взаимно однозначное отображение поля F на множество упорядоченных наборов длины r с компонентами из множества f0; 1; 2; : : : ; p ¡ 1g. Отсюда несложно заключить, что число элементов F равно pr. Запись элемента a(x) поля F

в виде вектора a называют его векторным представлением или векторной формой этого элемента. Например, векторным представлением элемента 3x4 + 2x3 + x + 4 поля GF (76) является вектор (0; 3; 2; 0; 1; 4). При этом неважно по какому неприводимому над Z7 многочлену g(x) шестой степени построено это поле. Отметим, что нулю поля соответствует нулевой вектор, а единице вектор (0; 0; : : : ; 0; 1).

Операции сложения и умножения в поле F можно ввести следующим образом:

26

(1)Рассматривая a(x) и b(x) как многочлены с целыми коэффициентами, находим сумму a(x) + b(x) этих многочленов (по обычным правилам сложения многочленов), а затем каждый коэффициент этой суммы заменяем его остатком при делении на число p. Полученный многочлен принимаем за сумму a(x) © b(x) элементов a(x) и b(x).

(2)Рассматривая a(x) и b(x) как многочлены с целыми коэффициентами, находим произведение a(x) ¢ b(x) этих многочленов (по обычным правилам умножения многочленов), затем делим с остатком это произведение на многочлен g(x) и в полученном остатке каждый коэффициент заменяем его остатком при делении на число p. Полученный многочлен принимаем за произведение a(x) ¯ b(x) элементов a(x) и b(x).

Ясно, что введенный выше нулевой элемент 0 можно определить как многочлен, тождественно равный нулю. Анлогично, единицу 1 поля определя как постонный многочлен, тождественно равный 1. Легко видеть, что для любого элемента a(x) 2 F выполнены равенства

a(x) © 0 = a(x) и a(x) ¯ 1 = a(x):

Пусть a(x) элемент поля F = GF (pr). Обратным элементом для a(x) называют такой элемент b(x) этого поля, для которого a(x) ¯ b(x) = 1. Этот элемент обозначается (a(x))¡1. Обратный элемент существует и единстнен для любого ненулевого элемента поля.

Обратный элемент (a(x))¡1 можно вычислить так:

(1)Используя расширенный алгоритм Евклида для многочленов, находим многочлены u(x), v(x) и h(x) с целыми коэффициентами, для которых a(x)u(x) + g(x)v(x) = h(x), причем h(x) такой многочлен, все коэффициенты которого делятся на p, а свободный член C не делится на p. Кроме того, степень многочлена u(x) должна быть меньше r.

(2)Находим такое целое число D, что произведение C ¢ D при

делении на p дает остаток 1 (иными словами D = C¡1 (mod p)

мультипликативное обратное для элемента C в поле Zp).

(3)Все коэффициенты многочлена D¢u(x) заменяем их остатками при делении на число p. Полученный многочлен и является обратным для a(x) элементом поля F .

27

28

Остаток при делении a(x)(¡x2 ¡ x + 1) на g(x) равен 3, поэтому

a(x) ¯ (¡x2 ¡ x + 1) = 3

Умножая последнее равенство на элемент 2 = 3¡1(mod 5), получим

a(x) ¯ (¡2x2 ¡ 2x + 2) = 3 ¢ 2 ´ 1(mod 5);

Заменяя в многочлене ¡2x2 ¡ 2x + 2 все коэффициенты их остатками при делении на 5, придем к сравнению

a(x) ¯ (3x2 + 3x + 2) = 1;

откуда

(a(x))¡1 = 3x2 + 3x + 2

.

Полученные результаты в векторной форме можно записать так:

Пример 2. Построим конечное поле F = G(24) из 16 элементов. Его элементами являются многочлены вида a0x3 + a1x2 + a2x + a3, где ai равно 0 или 1 при любом i. В качестве порождающего многочлена выберем неприводимый над полем Z2 многочлен g(x) = x4 + x + 1. Теперь можно находить суммы и произведения элементов поля F . Пусть, например, a(x) = x2 + x + 1

иb(x) = x3 + x + 1. Найдем их сумму, произведение и обратный для a(x) элемент.

1)Вычисляя сумму a(x)+b(x) = (x2+x+1)+(x3+x+4) = x3+x2+2x+2

изаменяя каждый коэффициент этой суммы его остатком при делении на 2, получаем многочлен x3 + x2, который и будет суммой a(x) © b(x) элементов a(x) и b(x) поля F .

2)Находим произведение

f(x) = a(x) ¢ b(x) = (x2 + x + 1) ¢ (x3 + x + 1) = x5 + x4 + 2x3 + 2x2 + 2x + 1

29

30