* Ентропно кодиране
Публикувано на 10 септември 2017 в раздел Информатика.
Дотук се запознахме само отчасти с компресирането на определен тип данни - изображения - при това прекалено общо. Сега ще разгледаме по-подробно компресиране без загуба на информация, като основно ще се фокусираме върху примери с текст, но основите ще са приложими към всякакви данни.
Преди да започнем ще развенчаем един от най-силно натрапваните митове свързани с компресирането на данни. Не може да съществува универсален алгоритъм за компресиране без загуба на информация. Ако такъв алгориъм съществува и с него компресираме всички [mathi]2^N[/mathi] различни файла, които са с дължина точно [mathi]N[/mathi] бита, ще трябва да получим [mathi]2^N[/mathi] файла, които са с най-много [mathi]N-1[/mathi] бита (иначе те няма да са компресирани). При подобна компресия ще можем да имаме най-много [mathi]2^{N-1}[/mathi] компресирани файла от [mathi]N-1[/mathi] бита, [mathi]2^{N-2}[/mathi] файла от [mathi]N-2[/mathi] бита, и т.н. of 1 файл с големина 0 бита. Ако ги съберем, ще получим:
[math]\sum\limits_{x=0}^{N - 1} 2^x = 2^N - 1 < 2^N[/math]
Тоест ще имаме поне два различни текста, чийто компресирани поредици ще са едни и същи. Това означава, че алгоритъмът е със загуба на информация, защото няма как да вземем решение кой е първоизточника на тези две идентични компресирани поредици.
Поради тази причина е крайно неправилно да се говори за по-добър или по-лош алгоритъм за компресиране по принцип. Можем да говорим за по-добър или по-лош алгоритъм за компресиране на определен тип данни. Повечето компресиращи програми, които познавате, ще дадат не само пренебрежими, но често дори и отрицателни резултати с произволни поредици от битове. Те обаче ще се справят повече от отлично когато им подадете файл, чието съдържание е предимно най-обикновен текст в позната за тях кодировка - например електронна книга, HTML документ, т.н. Не може да се говори за компресиране на произволни данни - може да има само и единствено такова, което работи по точно определен модел. Почти всички тестови низове са произволни от гледна точка на познатите алгоритми, но тези, които не са, т.е. смислените текстови низове от човешка гледна точка, са част от моделите, по които популярните алгоритми работят.
Дотук можем да обобщим, че компресирането изисква моделиране. Ключът към създаването на добър модел е да можем да разберем информацията, с която работим - да можем да започнем да откриваме закономерности, повтарящи се поредици и дори да можем да предсказваме нейното разширение. Трябва ли обаче да се ограничаваме само до обикновен текст?
Естествено е, че с вдигането на нивото на абстракция можем да се досетим, че по аналогия могат да се създават модели за компресиране на картинки, видео и всякакъв друг тип данни. Често обаче се прибягва до една друга техника, която предхожда моделирането - т.нар. трансформиране. То представлява преобразуване на различни типове данни към поредици от символи така, че впоследствие да може да бъдат компресирани с добре познат алгоритъм за компресиране на текст. Естествено то трябва да бъде обратимо, защото в противен случай не бихме могли да възстановим оригиналните данни. В нередки случаи обаче се прибягва нарочно до трансформиране със загуба на информация - нарочно губим част от данните, за да постигнем максимална компресия. Засега ще пропуснем този момент.
Накрая се стига до последния етап, който се нарича кодиране. С него превръщаме некомпресирания текст в компресирана поредица от битове, която се ръководи от правилата, зададени от преди това съставения модел.
С тази статия ще започнем отзад-напред. Първо ще се запознаем с кодирането, а в следващи статии ще преминем към другите етапи.
Кодиране на Хъфман
Буква ще наричаме символ или поредица от символи. Азбука ще наричаме множество от букви.
Нека за всяка буква в дадена азбука да имаме съпоставена вероятност за нейното срещане в стандартен текст (именно тази информация ще ни е предоставена според модела, по който работим). При кодирането на Хъфман се построява бинарно дърво по следния принцип:
- Всяка буква започва със свое собствено дърво от единствен елемент;
- Двете букви с най-малка вероятност за срещане се комбинират в общо дърво;
- Предишната точка се повтаря докато не се получи едно голямо дърво, което обхвяща всички букви.
Ще демонстрираме алгоритъма с пример. Нека е дадена азбуката с десет букви ABCDEFGHIJ, всяка от които е с равна вероятност за срещане от 0.1. На стъпка 1 ще започнем с:
A(0.1) B(0.1) C(0.1) D(0.1) E(0.1) F(0.1) G(0.1) H(0.1) I(0.1) J(0.1)
На стъпка 2 ще изберем два елемента, които имат най-малка вероятност. Понеже всички са с равна вероятност, можем да изберем кои да е 2, т.е. например последните:
(0.2)
0 / \ 1
/ \
A(0.1) B(0.1) C(0.1) D(0.1) E(0.1) F(0.1) G(0.1) H(0.1) I(0.1) J(0.1)
Сега трябва да изберем нови два върха, които са с най-малка вероятност. Очевидно (0.2) няма да участва. Следващото обединение ще е на G и H, после на E и F, после на C и D и накрая на A и B. Тоест стъпки 3, 4, 5 и 6 ще доведат до:
(0.2) (0.2) (0.2) (0.2) (0.2) 0 / \ 1 0 / \ 1 0 / \ 1 0 / \ 1 0 / \ 1 / \ / \ / \ / \ / \ A(0.1) B(0.1) C(0.1) D(0.1) E(0.1) F(0.1) G(0.1) H(0.1) I(0.1) J(0.1)
Вероятно вече се досещате, че следващите две стъпки ще обединят четири от върховете по следния начин:
____(0.4)____ ____(0.4)____
0 / \ 1 0 / \ 1
/ \ / \
(0.2) (0.2) (0.2) (0.2) (0.2)
0 / \ 1 0 / \ 1 0 / \ 1 0 / \ 1 0 / \ 1
/ \ / \ / \ / \ / \
A(0.1) B(0.1) C(0.1) D(0.1) E(0.1) F(0.1) G(0.1) H(0.1) I(0.1) J(0.1)
Следващото обединение трябва да е между останалия връх (0.2) и съседния до него (0.4):
_______(0.6)_______
0 / \ 1
/ \
/ ____(0.4)____ ____(0.4)____
/ 0 / \ 1 0 / \ 1
/ / \ / \
(0.2) (0.2) (0.2) (0.2) (0.2)
0 / \ 1 0 / \ 1 0 / \ 1 0 / \ 1 0 / \ 1
/ \ / \ / \ / \ / \
A(0.1) B(0.1) C(0.1) D(0.1) E(0.1) F(0.1) G(0.1) H(0.1) I(0.1) J(0.1)
Финално съставяме крайното дърво за кодиране:
_________________(1.0)__________________
0 / \ 1
/ \
_______(0.6)_______ \
0 / \ 1 \
/ \ \
/ ____(0.4)____ ____(0.4)____
/ 0 / \ 1 0 / \ 1
/ / \ / \
(0.2) (0.2) (0.2) (0.2) (0.2)
0 / \ 1 0 / \ 1 0 / \ 1 0 / \ 1 0 / \ 1
/ \ / \ / \ / \ / \
A(0.1) B(0.1) C(0.1) D(0.1) E(0.1) F(0.1) G(0.1) H(0.1) I(0.1) J(0.1)
Вече можем да построим следната кодираща таблица:
A <-> 000 B <-> 001 C <-> 0100 D <-> 0101 E <-> 0110 F <-> 0111 G <-> 100 H <-> 101 I <-> 110 J <-> 111
Разбира се при реално компресиране ще имаме доста по-голяма азбука (всъщност тя трябва да е такава, че съдържанието на целия файл да може да се опише чрез нея). Кодирането на Хъфман се използва при моделите за компресиране deflate (zip, bzip2), JPEG, и др. Трябва да се отбележи специално, че при по-къса азбука (нещо, което търсим заради значително по-голямата бързина) и неравномерни вероятности за буквите (получава се често именно при къси азбуки) се получава неефективно разпределение на дължините на кодовете, което води до неоптималност на компресията. Проблемът се разрешава с увеличение на дължината на азбуката, но това води до експоненциално забавяне. При компресиращите програми може да видите често, че при създаване на архивен файл има "ниво на компресия", например при архивиране в ZIP - повишаването му е именно разширяване на азбуката, което води и до забавяне на компресирането;
Друго нещо, което не споменахме, е отбелязването на "край на файл". Нужно е да се измисли специален код, който да дефинира "край на компресирания файл". Обикновено се прави чрез въвеждането на специална буква в азбуката.
Адаптивно (динамично) кодиране на Хъфман
Допълнително към казаното, кодирането на Хъфман може да е статично или динамично. При статичното кодиране компресиращият алгоритъм първо минава през текста и пресмята вероятностите за срещане на всяка буква, след което строи дървото и записва това дърво като част от компресирания текст. При динамичното кодиране дървото не се записва като част от компресирания текст, а се пресъздава (дообогатява и преизчислява) отново и отново с всяка компресирана/декомпресирана поредица. Обикновено в практиката се използва предимно статично компресиране, защото рядко спестеното място от запазване на дървото води до по-голяма компресия (при динамичното компресиране имаме значителна загуба на КПД в началото на текста), но в същото време строенето на тези поредици от бинарни дървета прави динамичното компресиране много по-бавно. Тук обаче има една важна уговорка - ако компресираме кратки текстове, статичното кодиране е по-неефективно, защото не си заслужава записването на информацията за дървото.
Аритметично кодиране
Аритметичното кодиране е основата на почти всички по-нови алгоритми за компресиране. Измислено е отдавна, но е било патентовано и това е попречило на по-широкото му разпространение до средата на 90-те. При него на всеки текст, който искаме да компресираме, се съпоставя едно единствено число с плаваща запетая. Разбира се не говорим за стандартен тип float или double, а за много голямо число (заемащо много повече битове). Процесът на компресиране се прави постъпково. С всяка нова буква от съобщението се добавят допълнителни битове към крайното число. Както и при кодирането на Хъфман, тук също зависим от модел на компресирането, т.е. в частност трябва предварително да са зададени вероятностите за това дадена буква да се срещне в текста.
Нека приемем, че за всяка буква x имаме вероятност за срещане P(x). Ясно е, че сумата от вероятностите за всички букви, които се срещат в текста, който ще кодираме, трябва да е равна на 1. Следващото нещо, което ще направим е да подредим тези низове в някакъв определен ред, например за удобство ще вземем лексикографски, но не е проблем да е какъвто и да е друг (например по реда на срещане на буквите), стига компресиращия и декомпресиращия алгоритъм да използват един и същ ред.
Нека например имаме съобщение DCAB, което е изградено от букви D, C, A и B. Очевидно е, че техните вероятности вероятности за срещане в текста са, т.е. P(D)=0.25, P(C)=0.25, P(A)=0.25 и P(B)=0.25. Лексикографската подребда на азбуката ще бъде {A,B,C,D}. Така ще разграфим интервала [0,1) (търсеното число, което ще представлява компресирания текст, ще бъде в този инвервал) в тези четири точки:
A B C D 0-------0.25-------0.50-------0.75-------1.00
От тук нататък кодирането на поредни низове от съобщението се прави, както написахме по-горе, постъпково. Ако в самото начало интервала е бил [0,1], то при прочитането на буква D на първа стъпка, интервала се скъсява до [0.75, 1], в смисъл, че крайното число (компресирания текст във вид на число с плаваща запетая) ще бъде в този интервал! Преди постъпването на следващия низ, разделяме новия интервал пропорционално по същият начин, както го направихме първоначално:
A B C D 0.75-------0.8125-------0.875-------0.9375-------1.00
На следващата стъпка постъпва буква C. Тоест новият интервал става [0.875,0.9375):
A B C D 0.875-------0.890665-------0.90625-------0.921875-------0.9375
Следващата буква е A, т.е. интервалът се скъсява до [0.875,0.890665):
A B C D 0.875-------0.87891625-------0.8828325-------0.88674875-------0.890665
Финално постъпва буква B, т.е. крайния интервал е [0.87891625,0.8828325). Компресираният текст ще бъде число с праваща запетая в този интервал.
За да достигнем до по-формална дефиниция, ще дефинираме P(<x) да е сумата от вероятностите на всички букви, които са лексикографски по-малки от x. От примера P(<A)=0, P(<B)=0.25, P(<C)=0.50 и P(<D)=0.75. Нека дефинираме и P(≤x) = P(<x)+P(x). От примера P(≤A)=0.25, P(≤B)=0.50, P(≤C)=0.75 и P(≤D)=1.00.
Всяко число с плаваща запетая, което попада в интервала от примера, би било достатъчно за да определи еднозначно входящото съобщение по дадения модел, т.е. би могло да го декомпресира. Ние обаче търсим оптималност - максимална компресия, - т.е. търсим такова число с плаваща запетая от получения интервал, че да заеме минимално количество битове. Тоест можем да кажем формално, че аритметичното кодиране на буква x е най-късото бинарно число y, такова че P(<x) ≤ y < P(≤x). От тук и аритметичното кодиране на текста ще бъде натрупване на кодиранията на всяка буква. Първата ще определи грубо границите на интервала, втората ще прецизира малко, третата още малко, и т.н.
Намирането на най-късото бинарно число в случая е лесно като се сетим, че просто трябва да намерим сума от рационални числа от вида 1/x, където x е степен на двойката. Причината да търсим степени на двойката в знаменателя е, че именно те представляват най-късата бинарна поредица. Например в интервала [0.1; 0.3) най-късата бинарна поредица ще е числото 0.25, което всъщност е 1/4. Ето една програма на Java, която намира числото, което представлява най-къса бинарна поредица в интервал [0.1), но с тип данни double, т.е. доста слаба прецизност спрямо това, което се търси в задачата:
public class ShortestBinaryInInterval {
public static void main(String[] args) throws Exception{
double test = shortest(0.3,0.5);
System.out.println("Double: "+test);
}
static double nextHigherInteger(double current) {
double next = Math.ceil(current);
if(Double.compare(current, next) == 0) {
next++;
}
return current;
}
static double shortest(double low, double high) throws Exception{
double result = nextHigherInteger(high);
double intervalFraction = 1;
while (Double.compare(intervalFraction, 0)!=0) {
intervalFraction /= 2;
if (result <= low) {
result += intervalFraction;
} else if (result >= high) {
result -= intervalFraction;
} else {
return result;
}
}
throw new Exception("Интервалът е прекалено къс за тип double");
}
}
Проследете кода и ще разберете основната идея - започваме да наситняваме интервал и съответно добавяме или изваждаме 1/2, 1/4, 1/8 и т.н., докато в един момент ни удовлетвори. Ако интервалът е прекалено къс, ние няма да можем да влезем с него с тип double, поради което хвърляме изключение. При реално действащ алгоритъм, ще бъде използван съответен тип данни с увеличаваща се точност, за да може винаги да се достигне до краен резултат.
Единствен по-сериозен проблем, който остана, е отново края на файла. За да го обясним ще ни трябва по-подробен пример с реално действащ алгоритъм. Обикновено или се кодира дължината на файла отделно (допълнително), или се отделят допълнителни битове за специален EOF символ.
Адаптивно аритметично кодиране
За разлика от кодирането на Хъфман, където се строяха бинарни дървета, аритметичното кодиране подлежи на изключително лесно и бързо реализиране на адаптивен режим (припомняме: без статична таблица на вероятностите, а динамично изграждаща се такава). Единственото, което трябва да се направи е на всяка следваща стъпка да се представя ново разграфяване на поредния интервал. Това предимство прави адаптимното аритметично кодиране значително по-приемливо за реална употреба.
Асиметрична числена система на Дуда
Едно от най-новите кодирания в областта на компресирането е измислената през 2007 г. "асиметрична числена система" на Джарек Дуда (която, както и предишните две, има свои вариации, които не разглеждаме). Основната идея зад измислянето на това кодиране е да се избегне операцията "умножение" - тя не е проблемна за модерните централни процесори, но отнема време при маломощни и специализирани emembed системи.
Асиметричната числена система взаимства идеята за съпоставяне на уникално число за кодирания текст, но в случая то не е число с плаваща запетая, а е от целочислен тип. На входа както обикновено имаме поредица символи, всеки от който има съответна вероятност за срещане. Алгоритъмът е направен така, че на по-вероятните за срещане поредици от символи се дават по-малки числа (т.е. заемат по-малко битове) - по този начин се постига компресия.
Ще дадем няколко опростени практически примери. Първият ще е крайно елементарен. Нека е дадена азбука от две букви A и B, за които е изчислено, че P(A)=0.25 и P(B)=0.75. Да се направи кодиране с асиметрична числена система.
Най-лесно ще покажем практическия пример чрез таблица, която ще показва десетични числа. Реалният алгоритъм естествено работи с бинарни и не е задължен да я запазва. Въпросната таблица трябва да отговаря на следните критерии:
- По колони изписваме буквите от нашата азбука, като са сортирани във възходящ ред според техните вероятности;
- По редове в най-лявата колона се изписват поредни естествени числа - 1, 2, 3, ... ();
- Всички числа в останалите клетки трябва да са уникални (без повторения);
- Всички числа в даден ред трябва да са по-големи от най-лявото число в този ред;
- Ако разделим най-лявото число в даден ред с някое съседно на него, трябва да се получи равна или максимално близка стойност до вероятността за буквата в съответната колона.
Ето как би изглеждала примерната таблица (буквата S идва от "state"):
| S | B | A |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 3 | 8 |
| 3 | 5 | 12 |
| 4 | 6 | 16 |
| 5 | 7 | 20 |
| 6 | 9 | 24 |
| 7 | 10 | 28 |
| 8 | 11 | 32 |
| ... | ... | ... |
Ако се вгледате по-внимателно, ще забележите и формулата, по която са генерирани числата в клетките. За числата в колона B сме закръглили S/0.75, а за колона A съответно S/0.25. Ако обаче числото вече присъства някъде в таблицата нагоре, взимаме най-близкото възможно до него. Запълването естествено започва от първи ред нататък.
Сега да видим как ще се кодира нашият примерен текст BAB. Започвайки от първи ред имаме буква B. В нейната клетка стои числото 2. Това означава, че следващият ред, с който ще работим, е №2. Идва буква A - в нейния ред №2 стои числото 8. Следващия ред, с който ще работим, е №8. Накрая идва последната буква B - в нейния ред №8 стои числото 11. Това е кодираният текст! Текстът BAB се компресира с числото 11!
Декомпресията ще върви отзад-напред (от последния символ към първия). Намираме числото 11 в таблицата (сега вероятно се досетихте защо всички числа трябва да са уникални). Вече знаем, че последната буква е B. Знаем също и кое е било предишното число - то е 8, защото се намираме на ред №8. Намираме числото 8 - то се намира на ред №2 в колона A, следователно предпоследната буква е A. Накрая намираме и двойката - тя е в ред №1 в колона B, следователно първата буква от текста е B.
В началото казахме, че "на по-вероятните за срещане поредици от символи се дават по-малки числа". Това действително ще бъде така. Нека вземем текста BBBBB. Този низ е с два символа по-дълъг от BAB, но ще се кодира с по-малко число - 10, Причината е именно, че в колона B числата нарастват по-бавно отколкото в колона A. По този начин срещането на по-вероятната буква B ще добавя по-малко битове спрямо по-малко вероятната A.
За упражнение направете таблица за трибуквена азбука A, B и C с вероятности P(A)=0.45, P(B)=0.35 и P(C)=0.20 до 10-ти ред.
Внимание: в изложената от тук надолу информация има техническа (дано не фундаментална) грешка, поради което нещо в сметките ми не излиза (кодираното не се декодира с точност една буква). Възможно е да има някаква тънкост, която ми е убягнала от теорията. Все пак общата картина изглежда горе долу по този начин, по който е изложено...
Досетихте ли се обаче до какъв проблем достигнахме? Възможно ли е таблицата ни да бъде безкрайно голяма? Естествено, че не. Тя със сигурност ще бъде ограничена от дисковото ни пространство, а всъщност ние едва ли бихме искали да го хабим с лека ръка (все пак целта на компресирането на информация е да пестим дисково пространство). Какво да правим ако получим закодирано много голямо число, което е извън нашата таблица? Ще представим техниката без доказателство, но със сигурност ще харесате нейната простота.
Нека вземем отново първия ни пример, но този път нашата таблица ще бъде повече от скромна - тя ще е само до 11-ти ред:
| S | B | A |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 3 | 8 |
| 3 | 5 | 12 |
| 4 | 6 | |
| 5 | 7 | |
| 6 | 9 | |
| 7 | 10 | |
| 8 | 11 | |
| 9 | 13 | |
| 10 | 14 | |
| 11 | 15 |
Забележете, че ако достигнем до число по-голямо от 11, това ще е края на възможността ни да кодираме чрез таблицата - ще сме се изчерпали откъм редове и при пристигане на нова буква на този етап няма какво да правим. Също така вероятно са ви направили впечатление празните клетки. Причината за тях е, че в таблицата включваме само числата от 1 до 15, а 15 представено в бинарен вид е 1111. Тоест искаме с тази таблица да кодираме максимално до 4 битови числа.
В началото ще демонстрираме доста по-простата техника - декомпресирането. Нека сме получили кодиран текст като числото 118. В двоичен вид то представлява 1110110. Знаем, че можем да кодираме максимално 4 битови числа. Процедурата ще бъде следната:
- Взимаме последните четири бита на числото 118, т.е. това са битовете 0110. В оригиналното число ги задраскваме и остават само първите три: 111;
- Битовете 0110 са числото 6 в десетична бройна система. Намираме го - това е буква B на ред №4. Вече знаем, че последната буква на текста е B;
- Числото 4 (поради това, че предишната буква се намираше в ред №4) в бинарен вид е 100 - трибитово. Нашата таблица работи с четирибитови числа, а след предишното "задсраскване" ни останаха битовете 111 (стъпка 1). От остатъка взимаме последния бит и го добавяме накрая на 100 - получаваме 1001. От оригиналното число задраскваме последния бит и остава само 11;
- Битовете 1001 са числото 9. Намираме го в таблицата. Това отново е буквата B. Тя се намира на ред №6, което в бинарен вид е 110;
- Към бинарното число 110 отново взимаме един бит от остатъка - получаваче 1101. Остатъка, след задраскване на последния бит, ще бъде само 1.
- Битовете 1101 са числото 13. В таблицата това е буквата B. Тя се намира на ред №9, което в бинарен вид е 1001;
- 1001 си е четирибитово число. Значи към него няма да добавяме остатък, а направо ще го извлечем. Числото 9 отговаря на буква B на ред №6, което в бинарен вид е 110;
- Към бинарното число 110 добавяме последния остатък - получааме 1101. Вече нямаме остатък;
- Битовете 1101 са числото 13. В таблицата това е буквата B. Тя се намира на ред №9;
- Понеже нямаме повече остатъци, продължаваме напред - 9 е буква B на ред №6;
- 6 е буква B на ред №4;
- 4 е буква A на ред №1. Край.
Декодираното съобщение ще бъде ABBBBBBB.
Процесът на кодиране, когато се излиза извън таблицата, е по-сложен. Нека за удобство сложим отново същата таблица, но вече в скоби да посочим и бинарния вид на числата, защото вече вероятно излезе доста назад на екрана:
| S | B | A |
|---|---|---|
| 1 | 2 (10) | 4 (100) |
| 2 | 3 (11) | 8 (1000) |
| 3 | 5 (101) | 12 (1100) |
| 4 | 6 (110) | |
| 5 | 7 (111) | |
| 6 | 9 (1001) | |
| 7 | 10 (1010) | |
| 8 | 11 (1011) | |
| 9 | 13 (1101) | |
| 10 | 14 (1110) | |
| 11 | 15 (1111) |
Нека да пожелаем да кодираме текста ABABAB. Първите две стъпки са ясни:
- За първата буква A получаваме ред 4. Бинарната поредица е 100;
- За B на ред №4 получаваме 6. Бинарната поредица е 110;
- За следващата буква A спираме, защото на ред №6 нямаме налично нейно състояние. Числото 6 в бинарен вид е 110. Трябва да му добавим допълнителни битове накрая така, че да надхвърли максималното число в таблицата, което е четирибитово. Значи трябва да добавим поне 2 бита. За да определим кои точно са те, се досещаме какво правихме при декодирането - взимахме последните четири бита и оставяхме старшия като остатък. Значи към 110 трябва да добавим два допълнителни бита така, че при взимането на последните четири да имаме кодирана в таблицата буква A. Ще видите, че единственият начин да се получи това е да добавите 00. Поредицата става 11000;
- За следващата буква B взимаме последните 4 бита на текущата поредица - това са 1000. Можем ли да добавим един бит така, че да се получи позната буква B от последните четири? Не, няма как да стане - последните 3 бита са 000 и в допълнение с още един ще стане 0000 или 0001 - такова състояние нямаме в таблицата. Значи трябва да добавим два бита. Добавяме 10 и поредицата става 1100010;
- За следващата буква A взимаме последните 4 бита от текущата поредица - това са 0010. Можем ли да добавим един бит така, че да се получи позната буква А от последните четири? Да, имаме такава буква А - това ще е 0100. Значи добавяме 0 и поредицата става 11000100;
- За последната буква B взимаме последните 4 бита на текущата поредица - това са 0100. Можем ли да добавим един бит така, че да се получи позната буква B от последните четири? Да, имаме такава буква B - това ще е 1001. Значи добавяме 1 и поредицата финално става 110001001.
Значи успяхме да кодираме ABABAB с бинарната поредица 110001001, което е десетичното число 393.
Добави коментар