A Phase-Out kód l; egyéb csonka bináris kód Connect - Diamond Editions
A kivezetési kódok a bevezetési kódokból származnak, amelyeket Steven Pigeon javasolt nekem 2003-ban [1], a bináris kódolásról szóló tézis szerzője (francia nyelven) [2] (lásd különösen az 5.3.4.2. „Bevezetési kódok” szakaszt). Megoldják a klasszikus bináris kódok használatakor felmerült kis problémát: ha ismeri a szám által elérhető korlátot, a kódok legfeljebb fele használhatatlan. Az 1. ábra azt mutatja, hogy átlagosan a kódolási tér egynegyede elvész, ami legfeljebb fél bitet jelent számonként.
Ábra. 1: A klasszikus bináris kódolásban a fel nem használt kódolási helyet fehér háromszögek képviselik.
1. Néhány referenciaérték
A kontextus beállításához először adjuk meg, hogy létre akarunk hozni egy adatfolyamot, amely esetünkben mintavételezett jeleket, például hangokat vagy képeket képvisel. Minden mintát átalakítunk egy bit sorozattá, amelyet azután összefűzünk a bináris folyammal, hogy fájlba írjuk vagy továbbítsuk.
A sport itt abból áll, hogy csökkenti a teljes adatfolyam méretét, anélkül, hogy bármilyen információt veszítene: minden kódolt számnak ugyanazt a kimenetet kell adnia a dekódolás után. Számos technika létezik, többé-kevésbé bonyolult feldolgozással, de itt figyelembe vesszük, hogy a kódolandó számok (amelyeket n-nek nevezünk) függetlenek a szomszédoktól. Így minden egyes mintát kezelünk anélkül, hogy aggódnánk az előző vagy a következő miatt, ami n-t kissé absztrakt számgá tesz, de a kísérlet szempontjából mindig egy nullánál nagyobb vagy egyenlő egész szám.
A kísérlet kezd érdekessé válni abban, hogy az n számunk bitjeinek dekódolásához előzetesen, ilyen vagy olyan módon tudnunk kell egy kiegészítő információt: azt a határt (L-nek nevezzük), amely jelzi, hogy az n számunk melyik maximális értékre tehet szert. Ezért felírhatjuk a következő egyenletet:
Az entropista (vagy az entropológus?) Művészetének tehát ezt a határt kell közvetítenie anélkül, hogy az eredetinél több helyet foglalna el, de ez a cikk arra összpontosít, hogy ez a két n és L érték hogyan kombinálható úgy, hogy n csak az ideált használja bitek száma.
A klasszikus bináris kód k bitet használ 0 és 2 k -1 közötti szám képviseletére. Például k = 4 esetén 24 = 16 szimbólumot képviselhetünk, amelyek leggyakrabban a 0–15 számokhoz vannak társítva. Ha a határértékünk 15, akkor az n számunk 4 bitet fog használni, sem többet, sem kevesebbet. Általános szabály, hogy ha az L határ 2 k -1, akkor k biteket használunk. Ezzel szemben, ha ismerjük L-t, akkor kiszámíthatjuk a bitek számát k = log2 (L) .
De a kettő hatványával pontosan megegyező határ meglehetősen ritka eset. Legtöbbször az L határunk két kettő hatványa között lesz: 2k -1k. Ezután mindig k bitet kell kiosztanunk, de marad 2 k -L használatlan kód, kód, amely virtuális helyet foglal el, egy bit töredéke, amely végül az összes adatot mérlegeli. Ezt az elveszett kódolási helyet az 1. ábra fehér háromszögei képviselik, mert egy bit nem osztható.
Vannak az ideálhoz közel álló technikák, például számtani kódok [3] és intervallumkódolás [4] amellyel egy szimbólum található az előzőekkel összekeverve, amely megszabadítja a számokat az egyes bitek tetszőleges határától. Hátránya, hogy az ilyen típusú kódok viszonylag összetettek és bonyolultan megvalósíthatók. Különösen az aritmetikai kódok végzik a szorzásokkal rendelkező egész számításokat, amelyek jelentős megvalósítás esetén jelentős anyagi erőforrásokat foglalnak el. És mivel olyan CODEC-et fejlesztek, amelynek célja a lehető legkevesebb logikai kapu használata, ez a fajta megközelítés kizárt.