Кодът за постепенно премахване l; друг пресечен двоичен код Connect - Diamond Editions
Кодовете за постепенно премахване са получени от кодове за въвеждане, които ми бяха предложени през 2003 г. от Стивън Пиджън [1], автор на дисертация (на френски език) за двоично кодиране [2] (вижте по-специално раздел 5.3.4.2 „Кодове за въвеждане“). Те решават малък проблем, с който се сблъскват при използването на класически двоични кодове: когато знаете ограничението, което даден номер може да вземе, до половината от кодовете могат да бъдат неизползвани. Фигура 1 показва, че средно се губи една четвърт от пространството за кодиране, което представлява до половин бит на число.
Фиг. 1: Неизползваното пространство за кодиране в класическото двоично кодиране е представено от бели триъгълници.
1. Някои критерии
За да зададем контекста, нека първо уточним, че искаме да създадем поток от данни, който в нашия случай представлява извадкови сигнали, като звуци или изображения. Всяка извадка се трансформира в последователност от битове, които след това ще бъдат обединени в двоичния поток, за да бъдат записани във файл или предадени.
Спортът тук се състои в намаляване на общия размер, който този битов поток заема, без да се губи никаква информация: всяко кодирано число трябва да дава същия изход след декодирането. Има много техники с повече или по-малко сложна обработка, но тук ще вземем предвид, че всяко число за кодиране (наречено n) е независимо от съседите. Ние третираме всяка проба по този начин, без да се притесняваме за предишната или следващата, което прави n малко абстрактно число, но за целите на експеримента това винаги е цяло число, по-голямо или равно на нула.
Когато експериментът започва да става интересен, е, че декодирането на битовете на нашето число n изисква по един или друг начин предварително да се знае помощна информация: границата (наречена L), която показва коя максимална стойност може да вземе нашето число n. Следователно можем да напишем следното уравнение:
Следователно изкуството на ентрописта (или на ентрополога?) Е да предаде тази граница, без да заема повече място от оригинала, но тази статия се фокусира върху това как тези две стойности n и L могат да се комбинират, така че n просто да използва идеала брой битове.
Класически двоичен код използва k бита, за да представлява число между 0 и 2 k -1. Например, с k = 4, можем да представим 24 = 16 символа, които най-често се свързват с числата от 0 до 15. Ако ограничението ни е 15, тогава нашето число n ще използва 4 бита, нито повече, нито по-малко. Като общо правило, ако границата L е равна на 2 k -1, тогава се използват k бита. И обратно, когато знаем L, тогава можем да изчислим броя на битовете k = log2 (L) .
Но ограничение, точно равно на степен на две, е доста рядък случай. По-голямата част от времето, нашата граница L ще бъде между две степени на две: 2k -1k. След това винаги трябва да разпределяме k бита, но ще останат 2 k -L неизползвани кодове, кодове, които ще заемат виртуално място, част от бита, която в крайна сметка претегля всички данни. Това изгубено пространство за кодиране е представено от белите триъгълници на фигура 1, тъй като битът не се дели.
Има техники, близки до идеала, като аритметични кодове [3] и интервално кодиране [4] с който се намира символ, смесен с предходните, който освобождава числата от произволната граница на отделните битове. Недостатъкът е, че този тип код е относително сложен и труден за изпълнение. По-специално аритметичните кодове извършват изчисления на цели числа с умножения, което заема значителни материални ресурси в случай на реализация на материал. И тъй като разработвам CODEC, предназначен да използва възможно най-малко логически порти, този тип подход е изключен.