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

Стр.1 Арифметическое кодирование. Алфавит источника A={a1,…,an}, на котором задана вероятностная схема . В рассматриваемых методах использовались схемы кодирования (кодовые слова сопоставлялись отдельным буквам или блокам букв). В арифметическом кодировании кодирование осуществляется всей поступающей на вход кодера информацией ai1….al, где l — длина поверхности. Принцип арифметического кодирования заключается в том, что поверхности ai1….ail сопоставляется некоторый интервал I (I1…Il) единичного отрезка [0,1) (замкнутого слева, открытого справа). При l=1строятся интервалы I(1), I(2), …, I(n), являющиеся непересекающимися подмножителями вари единичного отрезка [0,1) При l строятся n интервалов I (i1…il-11) I (i1…il-12) …….. I (i1…il-1n) Являющихся непересекающимися подинтервалами интервала I (i1…il-1). Естественно при этом предполагать, что на каждом шаге эти подинтервалы дают разбиение исходного интервала, то есть Unj=1 I(j) = [0,1). Unj=1 I(i1…il-1j) = I(i1…il-j) Длины подинтегралов выбираются пропорциональными (принадлежащими величинам вероятностей P1…Pn Стр.2 Как только построен интервал I (I1…Il) для всех типов длины l, в качестве кодового слова для ai1...aiz выбирается число zI(i1…,il), двойное разложение которого объявляется кодовым словом и передается в линию. При этом для механизации времени передачи естественно взять такое z, двойное разложение которого имеет минимум двоичных разрядов. Чем меньше длина интервала I (I1…Il), тем (как правило) большая разрядность z используется. Следовательно, чем больше длина интервала, тем меньше (в среднем) будет длина кодового слова и тем больше степень сжатия. Это оправдывает необходимость выбирать длины интервалов пропорционально вероятностям P При этом более вероятным текстам будут соответствовать интервалы большей длины, следовательно, средняя длина кодового слова оказывается меньше. В качестве кодового слова z возьмем некоторую двойную дробь z = , где p — нечетное число (либо p = 0, если z = 0), а показатель степени k — минимален, zI(i1…,il). Таким образом, декодирование — как можно поступить? Двоичное разложение z это запись двоичной дроби наименьшей длины. Считаем, что в декодер поступает длина исходного текста l, и кодовое слово z является двоичным разложением. Как кодер, так и декодер знают алгоритм истечения A={a1,…,an} и заданную на нем вероятностную схему. В таком случае для заданного l возможно (по крайней мере, теоретически) вычислить все интервалы вида I(i1…,il) и найти тот, которому принадлежит z, на выходе декодера a1,…,an. Конечно, мы будем вычислять более эффективным методом. Стр.3? (номер страницы?) Пример 3 иллюстрирует случай, когда кодирование с масштабированием дают не такой результат как без него. Кодируем пример 3: (aaaa) (неоднозначность числа 0) Начало кодирования п-ти Левый угол Длина Правый угол Начало кодирования a α=1 1 β=1 — a α=0=(0,00…)z α =0 l=0,4 l=0,4 2=0,8 β=0,4=(0,0110...)2 β=(0,110...)2=0,8 +(0)2 = 0 a α=0=(0,00…)z α =0 l=0,80,4=0,32 l=0,322=0,64 β=0,32=(0,01010...)z β=(0,1010...)z=0,64 +(0)z=0 00 a α=0=(0,00…)z α =0 l=0,640,4=0,256 l=0,2562=0,512 β=0,256=(0,0100...)z β=(0,100...)z =0,512 00 +(0)z=0 000 a α=0=(0,000…)z α =0 l=0,5120,4=0,2048 l=0,20484=0,8192 β=0,2048=(0,0011010...)z β=(0,11010...)z =0,8192 000 +(00)z=00 00000 Имеем конечный интервал: [α =0; β=0,11010). Случай z= α =0, имеем код 000000. Стр.4 Если первая буква кодируемого текста равна аi, то исходный интервал [0,1) заменяется на I(i) = (P1+…+ P1-1+ P1+ Pi), который используется в качестве исходного на следующем шаге. Пусть на некотором шаге (после кодирования М букв), в качестве исходного выступает интервал [), где 0. Пусть его длина равна l==. Как и ранее разбиваем его на n подинтервалов вида I(i1, …, Im, 1)=[, I(i1, …, Im, 2)=[,l, +(p1+p2), l) ….. I(i1, …, Im, n-1 )=[α+(p1+…pn-2)l,α+(pin…+pn-2+pn-1)l I(i1,…lm, n)= [α+(p1+…+pm)l,β) Заметим: требование, что все значения pi0 здесь существенно, иначе некоторые интервалы могут получиться нулевой длины. Если (m+1)-я буква кодируемого текста есть aj, то в качестве нового интервала выбирается интервал I(i1, …, im, j) После того как найден интервал I(i1,…,iz), соответствующий всему тексту ai,…aiz, в этом интервале выбирается рациональное число, двоичное разложение которого содержит наименьшее число разрядов (такие всегда есть!) z=0, b1...bk-1 1 (Единица обязана быть на конце, если только z ≠ 0 Кодовым вектором для нашего текста объявляется поверхность (b1...bk-1 1), который передается по каналу связи вместе с длиной кодируемого текста (длина сначала)??? Стр.5 Так если взять двоичную дробь в нашем интервале как … = 0.b1 bt = p՛/2z где k ≤ q ≤ t (q < t если поверхность оканчивается нулями) При этом k ≤ q так как по условию z= p/2k двоичная дробь, запись которой имеет наименьшую длину. Таким образом, z=0.z1…zk-1 1 дает двоичное разложение наименьшей длины из нашего интервала по которому можно восстановить исходную поверхность. Алгоритм разбиения на интервалы. Итак, вероятностную схему А= для конечного алфавита, ∑pi=1, можно не ограничивать общности, предполагать, что буквы упорядочены по убыванию их вероятностей p1≥ p2≥ …≥ pn>0, хотя, вообще говоря, в данном методе это не обязательно. Алгоритм начинает работу с полуоткрытого интервала [0,1). Мы разобьем его на n непересекающихся полуоткрытых интервалов, соответствующих буквам a1,…,an, а именно а1 → [0,p1) = I(1) а2 → [p1,p1+p2) = I(2) а3 → [p1+p2, p1+ p2+p3) = I(3) ….. An-1→[pi+…+pn-z, pi+…+pn-2+pn-1) = I(n-1) An→[pi+…+pn-1, 1) = I(n) Их объединение дает весь интервал [0,1). Длина i-го интервала соответствует букве ai, т обр, пропорциональна ее вероятности Pi Стр.6 Пример процесса кодирования Пусть кодируем последовательность bacb Буква Начало Длина 1 b↑ 0,4 0,3 а↑ 0,4 0,30,12 с↑ 0,4 + 0,12(0,4+0,3)=0,484 0,120,2=0,024 b↑ 0,484+0,0240,4=0,4936 0,0240,3=0,0072 Таким образом в итоге получаем интервал I(bacb) = [0.4936, 0.4936+0.072) ­-[0.4936,0.5008). Поскольку число z = = (0.1)2 I(bacb), то кодовое слово равно 1. В канал связи передаем длину l=4, затем код в.р «1» Пусть кодируем последовательность ccda Буква Начало Длина 1 c↑ 0,7 0,2 c↑ 0,7+020,7=0,84 0,20,04 d↑ 0,84 + 0,040,9=0,876 0,040,1=0,004 a↑ 0,876 0,0016 I(ccda) = [0.876, 0.876+0.0016) = [0.876, 0,8776) Теперь надо найти двоичное число из интервала I(ccda), запись которого имеет минимальную длину. Стр.7 Пример. Пусть задана вероятностная схема на …. из четырех букв Тогда разбиение на интервалы выглядит следующим образом A(a) A(b) A(c) A(d) [ )•[ )•[ )•[ )• 0 0,4 0,7 0,9 1 A(ba) A(cc) A(bc) A(bd) [ )•[ )•[ )•[ )• 0,4 0,52 0,61 0,67 0,7 A(baa) A(bab) A(bac) A(bad) [ )•[ )•[ )•[ )• 0,4 0,448 0,484 0,808 0,52 A(aa) A(ab) A(ac) A(ad) [ )•[ )•[ )•[ )• 0 0,16 0,28 0,36 0,4 A(da) A(db) A(dc) A(dd) [ )•[ )•[ )•[ )• 0,9 0,94 0,97 0,99 1 Процесс кодирования можно представить в виде таблички Буква Начало Длина 1 Si1 Si2 …. Pi +…+ Pi-1 (Pi +…+ Pi-1) + Pi1(Pi +…+ Pi-1) …. Pi1 Pi1 Pi2 …. Стр.8 Пример кодирования продолжение. Кодируя bacb получили интервал [0.4936, 0.5008) Длина интервала l=0.0072 Ищем t: 2-t ≤ 0,0072 < 2-(t-1) Получаем t=8 (2-1 = 0.5, 2-2 = 0.25, 2-3 = 0.125, 2-4 = 0.0625, 2-5 = 0.3125, 2-6 = 0.015625, 2-7 = 0.0078125, 2-8 = 0.0039625) Решаем относительно x неравенства 0,4936 ≤ < 0,5008 или 126,3616 ≤ x < 128,2048 Имеем два решения x1 = 127 и x2 = 128 Для x1 получаем z1 = 127/2-8 = 0.01111111 Для x2 получаем z2 = 128/2-8 = 0.10000000 Во втором примере, кодируя ccda, получился интервал [0.876, 0.8776) Длина l = 0,0016 (2-9= 0.001953125, 2-10 = 0,0009765625) t =10 Решаем относительно x неравенства 0,876 ≤ x/210 ≤ 0,8776 897,024≤ x < 898,6624 Получаем решение x = 898 Находим z = = = = (0,111000001)2 → код 111000001 Стр.9 Нахождение двоичной дроби минимальной разрядности Метод 1 ] l = β – α – длина интервала [ α, β ) Найдем минимальное целое цисло t: 2-t ≤ l, то есть такое t, что 2-t ≤ l < 2-(t-1) Зная это t ищем решение неравенства α ≤ x - 2-t < β относительно x. Всегда существует решение (по крайней мере одно) в некоторых случаях может быть две последовательности числа, в таком случае выбираем четное. Неравенство можно переписать так: α 2t ≤ x < β 2t Так как 2-t ≤ lα-β < 2-(t-1) , то 1 ≤ l2t < 2, То есть 1 ≤ β2t - α 2t < 2, откуда α 2t + 1 ≤ β2t < α 2t + 2 Поэтому │ • │ • [ │ )• │ ↑α 2t ↑α 2t+1 ↑α 2t+2 Имеем два случая: 1 решение Целочисленное x↓ ↓β2t │ •[ │ • •)│ ↑α 2t ↑α 2t+1 В первом случае находим x (единственное) Полагаем наше z = x/2t 2 решение x1↓ x2 = x1+1↓ ↓β2t │ •[ • │ •)•│ │ ↑α 2t ↑α 2t+1 ↑α 2t+2 Во втором случае из двух решений x1 и x2 = x1+1 выбираем четное число (дает меньше разрядов в двоичной записи) Стр.10 В этом случае рассмотрим двоичное разложение x: α = 0, a1...at-1 0…0 1…1 0 и что-то еще в конце l0 – длина одних нулей начиная с t-го места (l0 ≥ 1) l1 – длина следующей серии из единиц (l0 ≥ 1 согласно предположению) В этом случае имеем цепочку неравенств: На действительной прямой это выглядит так • │ •[ • )• ↑0 ↑α՛=0,a1…at-10 ↑α=0,a1…at 00  11 0 Длина интервала l = β – α < 2t = β – α՛ 1•] Если l0 > 0, то α = 0, a1...at-1 00…01…1… β = 0, a1...at-1 10………0… и число z = 0, a1...at-1 01 разрядностью t+1 знак лежит в интервале α < z < β, длина которого 2-t > l = (β – α)/2-t ≥ 2-(t+1) так как ↓z = a1..at-101 ↓ β= α=0,a1…at-110…(все нули) │ •[ • )• ↑α՛=0,a1…at-10 ↑α=0,a1…at-1 00…0  1..1 0 Берем выбранное z 2•] Если l0 = 1, то α = 0, 0,a1…at-1 01…10  Если все разряды после t + l1 – го равны нулю, то z = α (нижняя граница интервала), если нет, то меняем ноль на t + l1+1– м месте на единицу и берем t + l1+1– разрядное число z = 0,a1…at-1 01…11  Стр.11 Метод 2. Решать неравенства ….. Лучше искать используемое двоичное разложение числа. Выпишем двоичные разложения границ интервала α и β и найдем минимальный разряд, в котором они отражаются] различие начинается с t-го разряда. Тогда имеем всегда: x=(0,a1…at-1 0 at+1… β=0,a1…at-1 1 bt+1 Возможны следующие случаи: Обозначим α՛ = 0,a1…at-1 0(0) β՛ = 0,a1…at-1 1(0) а) α = 0,a1…at-1 (то есть все знаки после t – го в двоичном разложении α равны нулю). Это значит, что α = (а1 – аt-1)/2k-1 и α есть двоичная дробь со знаменателем 2k где k < t , тогда z = α, так как в этом случае длина интервала 2-(t-1) > l = β – α ≥ 2-t а число a1…at-1 0 является решением неравенства α ≥ x2-t < β, притом оно четное (на тот случай если найдется второе решение). Берем его. б) α > 0,a1…at-10 = α՛ (то есть среди значений at+1, at+2 … есть единица) β > 0,a1…at-11 = β՛ (то есть среди значений b t+1, b t+2 … есть единица) Тогда число C < 0,..a1,..at-11< β (принадлежит интервалу [α ,β)) и имеет t разрядов (дает решение неравенств α ≥ x2-t < β), а t–1– разрядное число