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

Стр.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 … есть единица) Тогда число α < 0,..a1,..at-11< β (принадлежит интервалу [α ,β)) и имеет t разрядов (дает решение неравенств α ≥ x2-t < β), а t–1– разрядное число 0,..a1,..at-1 = 0,..a1,..at-1 0 < α следовательно оно не принадлежит интервалу [α ,β) и значит оно не годится. Берем z =( a1,..at-1 1)/2t в) α > 0, a1…at-10 = α՛ (at+I = 1 для некоторого i >0 ) β = 0, a1…at-11 = β՛ (то есть bt+1 + bt+2 = …=0) Тогда надо было бы взять 0, a1…at-11 = β, но правый конец полуоткрытого интервала [α ,β) не принадлежит ему (самый сложный случай). Стр. 12 На действительной прямой выглядит так: ↓0,a1…at-1 0 1..1 1… │ •[ • )• ↑α՛=0,a1…at-10 ↑α=0,a1…at-1 0 1..1 0… ↑β= 0,a1…at-11 Эти случаи соответствуют возможностям, когда возникают два или одно решение в методе 1 соответственно. Подпункты 1.] и 2.] можно объединить следующим образом: сканируем двоичное разложение α начиная с t+1– го разряда. Пусть первый нуль в п-ть разрядов at+1, at+2, … располагается на t+i – м месте. at+i = 0 at+j = 1 для всех 1≤ j ≤ i-1 i ≥ 1 Если at+i+1 = at+i+ =…=0, то z = 0,a1…at-1 0 at+1… at+i-1, то есть z = α Если же нет, то z = 0,a1…at-1 0 at+1… at+i-11 И при этом α < z < β Примеры: а) α = 0,1101(0) β = 0,11011 б) α = 0,110101 β = 0,110111 в) 1.] α1 = 0,11010011(0) β = 0,11011 в) 2.] α1 = 0,1101011(0) β = 0,11011 α2 = 0,11010101 = z = 0,1101011 (z2 > α2) Стр.13 Масштабирование В изложенном выше подходе вычисляются текущие границы интервала [α ,β) а затем внутри этого интервала ищется число z, двоичное разложение которого имеет минимальную разрядность. При этом мы 1) Вынуждены все увеличивать и увеличивать точность вычислений в то время как хранящиеся в памяти ЭВМ числа имеют ограниченную разрядность. 2) Держать в памяти обе границы α и β начала двоичного разложения которых могут совпадать в большом числе разрядов (a1…at-1 в наших предыдущих рассуждениях) как следствие, память расходуется неэкономно. 3) При таком подходе для нахождения кодового слова необходимо просмотреть всю кодируемую последовательность. От всех этих недостатков можно избавиться, применив масштабирование. А именно, пусть α = 0, a1…at-10 at+1… β = 0, a1…at-10 bt+1… Тогда начало двоичного разложения, задающего все числа в интервале [α ,β) , равно (a1…at-1) вне зависимости от того, что идет дальше в кодируемой последовательности. Мы можем сразу дописать вектор a1…at-1 в качестве продолжения кодового вектора и убрать его из записи границ α и β α → = 0at+1… β → = 1βt+1… • •[ • •)• )• 0 ↑α=0,a1…at-1 0 at+1 … ↑β= a1…at-11bt+1 1 • •[ │ )[• )• 0 ↑=0,0at+1 … 1/2 ↑= 01bt+1… 1 Это эквивалентно умножению α и β на число 2t-1 с последующим вычитанием из результата целого числа, имеющего двоичную запись (a1…at-1)2 В результате получаем новый масштабированный интервал [ ,) Стр.14 Заметим, что несмотря на более сложное изложение, метод 2 лучше метода 1 в плане его реализации на компьютере. При этом для всех рассматриваемых выше случаев подстрока a1…at-1 является частью конструируемого кодового вектора. При этом если мы не попадаем на границу интервала, то мы можем даже утверждать, что такой частью будет a1…at-11 Применим метод 2 к примерам, рассмотренным в примере 1. 1. (bacb) [α = 0.4936, β = 0.5008) Записываем в двоичной форме: α = 0,0111111001; β =100000000011… Отличие в первом разряде (t=1 последовательность a1…at-1 пустая) так как α > α՛, β > β՛ α՛ = 0, β՛ = (0,1)2 = ½ имеем случай б) В качестве кода выбираем единицу z = (0,1)2 = 1/2 2. (ccda) [α = 0.876, β = 0.8776) Записываем в двоичной форме: α = 0,11100000010…11… β =11100000101… Отличие в девятом разряде ( 0 для α, 1 для β ) α՛ = 0,11100000 < α β՛ =111000001(0) < β Снова имеем случай б) в качестве кода выбираем 111000001 Z = (0,111000001)2/29 = ½ + ¼ +1/8+ 1/29 = (256+128+64+1)/512 = 449/512 Стр.15 Начало кодирования п-ти Левая граница Длина Правая граница Кодовый вектор α=0 1 β=1 — c α =0,7=(0,10110…)2 =(0,0110…)2 = 0,72–1= 0,4 l=0,2 =0,4=(0,2 2) β=0,9=(0,1110...)2 =(0,110...)2= 0,9 -1 =0,8 (1)2 = 1 1= (1)2 c α=0,4 + 0,40,7 = 0,68 = (0,10101110…)2 = (0,0101110…)2 = 0,68 2 -1 = 0,36 l=0,40,2=0,08 =0,082=0,16 β=0,68+ 0,08= 0,76 = (0,1100001...)2 =(0,10000.1..)2=0,762-1= 0,52 1 (1)2=1 11 d α=0,36+0,160,9 = 0,504 = (0,10000001000…)2 =(0,001000…)2 = 0,50425-16 = 0,128 l=0,160,1= 0,016 =0,0162=0,512 β=0,504+0,016=0,52=(0,1000010...)2 =0,64 11 +(10000)2=16 1110000 a α=0,128=(0,000100000110…)z =0,1282= 0,256=(0,010000…) l=0,5120,4=0,2048 =0,20482=0,4096 β=0,128+0,2048=0,3328 = (0,010101...)z =0,33282 = 0,6656 =(0,10101...)z 1110000 +(0)z=0 11100000 Последний шаг – нахождение минимального двоичного разложения в интервале = [0,0100…2, =0,10101…2). Видно, что оно равно (0,1)2 = ½ . Получаем итоговый код вектор 111000001 Стр.16 В двоичной (машинной) записи мы сдвигаем двоичные разряды чисел α и β влево на t-1 позиции, перед этим записав t-1-мерный двоичный вектор a1…at-1 в результирующую кодовую последовательность (информация об абсолютных значениях α и β таким образом хранится там, а найденные новые границы и являются относительными значениями, масштабированными относительно этого абсолютного положения) При применении масштабирования получается тот же самый результирующий кодовый вектор, что и без него, так как мы, во-первых, каждый раз вычисляем новые границы подинтервалов, делая их пропорциональными частотам встречаемости знаков, и во-вторых, так как умножение числа на степень двойки не меняет его двоичной записи, сдвигаем лишь запятую, отделяющую целую часть от дробной. Пример кодирования с масштабированием. Как и ранее кодируем последовательность ccda. Оформляем процесс кодирования в виде таблички (1 столбец – кодируемый символ, следующие два столбца – текущие границы интервала и , последний столбец содержит выписанный фрагмент кодового вектора. Стр.17 В получившемся примере каждый из шагов несколько более сложен, чем в варианте без масштабирования, однако это есть плата за то, чтобы избавиться от необходимости оперировать с числами очень большой разрядности (в первоначальном варианте пришлось для последовательности всего в четыре символа оперировать числами с 10 двоичными разрядами, а здесь мы обошлись максимальной разницей в пять разрядов (на третьем шаге). К сожалению, масштабирование не всегда бывает возможно. Если в двоичной записи левая и правая границы интервала отличаются, начиная с самого старшего разряда, то осуществить его нельзя. Иногда такое может происходить на протяжении нескольких последовательных шагов, что чревато неприятными последствиями в виде потери точности, а следовательно, худшего сжатия. Если в результате потери точности окажется, что α = β, то длина интервала l = β - α = 0, а это означает ошибку кодера. Вернемся к примеру 2: bacba (масштабирование невозможно на протяжении 4-х шагов) Начало кодирования п-ти Левая граница Длина Правая граница Кодовый вектор b α=0 1 β=1 — a α =0,4=(0,0110…)2 l=0,3 β=0,7 =(0,1011...)2 — c α =0,4=(0,0110…)2 l=0,30,4=0,12 β=0,4+ 0,12= 0,52 = (0,100001...)2 — b α=0,4+0,120,7 = 0,484 = (0,011110…)2 l=0,120,2= 0,024 β=0,484+0,024=0,508= (0,1000001...)2 — α=0,484+0,0240,4=0,4936 = (0,01111110…)2 l=0,0240,3= 0,0072 β=0,4936+0,0072=0,5008= (0,1000000000110...)2 — a —/— 0,0720,4=0,00288 β=0,49648= (0,011111110…)2 0,01111111 Если бы мы для кодирования α и β использовали 7-битовые ячейки памяти, то уже после пятой буквы получили бы… Стр.18 Как показывает процесс кодирования примера 2՛, масштабирование не происходит на протяжении первых четырех шагов. Если на пятом шаге поступает буква «а», то α и β начинают сразу совпадать в семи разрядах. Например, при использовании 7-битовой арифметики это означало бы потерю точности, так как получилось бы, что α = β. Конечно, в реальном кодере разрядность гораздо больше, но идлина кодируемой последовательности обычно >> чем 5 букв. Поэтому необходимо предусмотреть механизм, позволяющий бороться с возникновением такой ситуации (она возникает как раз в том случае, когда интерполяция снижается хорошо в силу того, что в интервале лежит число, которое записывается малым числом двоичных разрядов). «The underflow expansion» - «Расширение срединного интервала» Допустим, что число ½ лежит внутри интервала [α,β), так, что масштабирование невыполнимо. Предположим также, что [α,β) ≤ [¼ , ¾), так что выполнена цепочка неравенств: ¼ ≤ α < ½ < β ≤ ¾ . Двоичное число наименьшей разрядности z [α,β) лежит либо в интервале [α, ½) либо в [½ ,β). В первом случае двоичное разложение начинается с (0,01…)2, во втором случае с (0,10…)2. Таким образом, второй бит двоичного разложения всегда является инверсией первого (если известен один из них, то знаем и другой). Далее рассмотрим преобразование интервала вида x→2x – ½ , (интервал [α,β) → [2α – ½ ,2β – ½)). Если [α,β) ≤ [¼,¾), то [2α,2β) ≤ [1/2 ,3/2) ⇒ [2α – ½ ,2β – ½)≤ [0 ,1) Если z [α,β) z = 0, a1…at двоичное разложение минимальной разрядности, то 2z = a1,a2,a3…at Стр.19 Приведенный пример показывает, что в процессе масштабирования необходимо вычислить число разрядов t, в которых совпадают границы α и β, чтобы затем применить к интервалу преобразование вида x→x2t – (a1…at-1). Это требует вычислительных ресурсов. К такому результату можно прийти и без подсчета t и a1…at-1, если делать все тоже самое пошагово. Так, если α и β совпадают в t ≥ 1 разрядах, то и старший разряд a1 у них совпадает. Разобьем масштабирование на t шагов, на каждом шаге выписывая единственный совпадающий старший разряд a1 и применяя к интервалу преобразование вида x→2x – (a1). По этой схеме закодируем шаг 3 предыдущего примера (после кодирования буквы d) Преобразование α=0,504= (0,10000001000…)2 l=0,016 β= 0,504+0,016=0,52 =(0,1000010)2 → 1 x→2x – 1 α=0,5042–1 =0,008= (0,0000001…)2 l=0,032 β= 0,522–1=0,04 =(0,000010)2 → 0 x→2x α=0,082=0,16= (0,000001…)2 l=0,064 β= 0,08=(0,00010)2 → 0 x→2x α=0,162=0,32= (0,00001…)2 l=0,128 β= 0,16=(0,0010)2 → 0 x→2x α=0,322=0,64= (0,0001…)2 l=0,256 β= 0,32=(0,010)2 → 0 x→2x α=0,642=0,128= (0,001…)2 l=0,512 β= 0,64=(0,10)2 → 0 Стр.20 Таким образом, приходим к …… расширения: 1) Заводим счетчик числа операций расширения, прошедших со времени последней операции масштабирования, который изначально равен нулю, и его обнуляем при каждой операции масштабирования. 2) Если текущий интервал удовлетворяет … 1/4≤α<1/2<β≤3/4, выполнить над ним преобразование [α,β) → [2α –1/2, 2β– 1/2) и увеличить счетчик числа операций расширения на единицу. 3) Выполнять это до тех пор, пока неравенство не перестанет выполняться. При выполнении операции масштабирования на один бит счетчик числа расширений равен k. Тогда если добавляемый бит кодируемого слова равен нулю, добавляем к этому биту последовательность, 11…1 k раз (итого 011…1), а если бит равен единице, то добавляем последовательность 00…0 (итого 100…0). После этого обнуляем счетчик числа ….. Стр.21 При этом, если а) z=0,01a3…at (z < ½), то а1=0, а1=1, 2z – ½ = a1, a2 a3…at –0,1 = 0,1a3…at –0,1= 0,0 a3…at, б) а если z=0,10a3…at (z ≥ ½, то есть а1=1 а2=0), то 2z – ½ = a1, a2 a3…at –0,1 = 1,0a3…at –0,1=0,1 a3…at. Таким образом, преобразование x→2x – ½ всегда удаляет второй бит из двоичной записи числа. Этот второй бит является инверсией первого бита, который будет определен при следующей операции масштабирования. Эти случаи на действительной оси. α ≤ z1 < ½ │ │ •[ • │ )• │ │ 0 ¼ α z1 ½ β ¾ 1 x→2x–1 α ≤ z1 < ½ │ │ •[ • │ )• │ 0 ½ 2α 2z1 1 2β x→2x–½ │ [ • │ )• │ 0 2α–½ 2z1–½ ½ 2β–½ 1 ½ ≤ z2 < β │ │ [ │ • )• │ │ 0 ¼ α ½ 2z2 β ¾ 1 x→2x │ [ │ • ) │ 0 2α –½ ½ 2z2 –½ 2β–½ 1 x→x–½ Таким образом, если α ≤ z < ½ , то и после преобразования x→2x – 1, значение 2z1 – ½ окажется в левой части интервала (< ½). А если ½ ≤ z < β, то и 2z1 – ½ также будет ≥ ½ Если новые границы = 2α – ½ и = 2β – ½ снова удовлетворяют неравенству ¼ ≤ < ½ < ≤ ¾ то новое = 2z – ½ имеет вид =0,01…2, если z = 0,01…2 (в этом случае обязано быть z = 0,011…2). Либо = 0,10…2, если z = 0,10…2 (в этом случае обязано быть z = 0,100…2). Стр.22 Букв. преобраз. Левая граница Длина Правая граница Код Счетчик 2x–½ 2x–½ = 0,39762 –0,5 =0,2952≥0,25=0,25+ 0,03125+0,01395= (0,010010…)2 =20,2952–0,5= 0,0904= 0,0625+0,015625= (0,000101….)2 =0,11522= 0,2304 =0,23042= 0,4608 =0,5256=0,5+ 0,015625+…= (0,10000…)2 =0,5572=0,5+ 0,03125+…= (0,10001…)2 — — 5 6 Масштаби-рование x→2x α= 0,904= (0,000101…)2 = 0,9042=0,1808 = (0,00101…)2 l=0,46080,4= 0,1872 =0,18722= 0,3744 β=0,2776=0,25 +0,015625+… =(0,010001…)2 =0,5552= (0,10001…)2 — 111111 6 После завершающего масштабирования находим двоичную дробь минимальной разрядности в интервале [0,00101…, 010001…), то есть 0,5 = ½ ⇒ код «1». Итого: 01111111 Замечание. Если при кодировании последней буквы получается интервал α < ½< β b и при этом счетчик числа расширений k > 0, то к уже имеющейся к этому моменту кодовой последовательности а1…аt надо добавить битовую строку 100…0 ⇒получим a1…at10…0, а в оригинальном (исходном) методе получим а1…аt1. Заметим, что это две эквивалентные записи одного и того же вида (можно записать и так и так – это не ошибка, а особенность конкретной реализации метода). Стр.23 6acba a b c d 0,4 0,3 0,2 0,1 Начало посл-ти Левая граница Длина Правая граница Добавленный код Счетчик расширений 6 Расшир. 2x–½ a =0 0,25 ≤ α =0,4= 0,25+0,125+0,025= (0,0110…)2 = 0,4– ½ = 0,8 – 0,5=0,3= 0,25+0,05=(0,010…)2 l=1 l=0,3 l=0,3=0,6 β=1 β=0,7=0,5+ 0,125+0,0625+ 0,0125=(0,01011…)2 ≤ 0,75 =0,3+0,6= 0,9=0,5+0,25+0,125+0,025= (0,1110…)2 > 0,75 — — — 1 Расшир. 2x–½ c α =0,3=(0,010…)2≥ 0,25 = 0,3– 0,5= 0,1=(0,0001…)2≤ 0,25 l=0,6= 0,24 l=20,24= 0,48 β=0,3+ 0,24=0,54=0,5+0,04=(0,100…)2 ≤ 3/4 =0,1+0,48=0,58=0,5+0,08= (0,1001…)2 — — 1 2 Расшир. 2x–½ b α =0,1+0,7= 0,336+0,1= 0,436= 0,25+0,125+0,061= (0,01101…)2 = 0,436– 0,5= 0,372=0,25+0,0625+0,03125+ 0,015625+… = (0,010111…)2 =2– 0,5= 0,244= 0,125+0,0625+0,03125+…=(0,00111)2 l=0,48= 0,096 =2= 0,192 =2= 0,384 β=0,436+0,096=0,532=0,5+0,03125+0,00075=(0,1000100…)2 =0,372+0,192=0,564=0,5+0,0625+0,015= (0,10010…)2 =0,244+0,384=0,628=0,5+ 0,125+0,003= (0,10100…)2 — — — 2 3 4 α =0,244+0,384=0,3976=0,25+0,125+0,015625+…= (0,011001…)2 l=0,384= 0,1152 =0,3976+0,1152=0,5128=0,5+0,0128= (0,1000001…)2 — 4 Стр.24 Эти интервалы выглядят так: а1→[α, α+P1l) а2→[α+P1l, α+(P1+ P2)l ) … αi→[α+j )l, α+j) l) … αn→[α+j )l, α+l) Таким образом, искомое значение ik+1=j находится из неравенств α+k )l ≤ z < α+k )l Последнее неравенство можно переписать k ≤ < k Таким образом, для нахождения ik+1, необходимо, последовательно вычислив суммы вида P1, P1+P2, …, P1+P2+…+ Pn-1, P1+P2+…+ Pn= 1, найти тот индекс j,для которого впервые выполняется неравенство < k Тогда I(i1, …,ik,ik+1)=k)l,k)l Стр.25 Декодирование Допустим, что на декодер поступает … кодовое слово…число n знаков исходной последовательности. Необходимо восстановить последовательность аi1…ain по значению z и N. Если кодовое слово z = 0, то исходная последовательность есть =