Codul de eliminare treptată l; alt cod binar trunchiat Connect - Diamond Editions
Codurile de eliminare treptată sunt derivate din codurile de introducere treptată, care mi-au fost sugerate în 2003 de Steven Pigeon [1], autorul unei teze (în franceză) despre codificarea binară [2] (a se vedea în special secțiunea 5.3.4.2 „Coduri de introducere treptată”). Acestea rezolvă o mică problemă întâlnită atunci când se utilizează coduri binare clasice: când știți limita pe care o poate lua un număr, până la jumătate din coduri pot fi neutilizate. Figura 1 arată că, în medie, se pierde un sfert din spațiul de codare, ceea ce reprezintă până la jumătate de bit pe număr.
Smochin. 1: Spațiul de codare neutilizat în codarea binară clasică este reprezentat de triunghiuri albe.
1. Unele repere
Pentru a seta contextul, să specificăm mai întâi că dorim să creăm un flux de date, care în cazul nostru reprezintă semnale eșantionate, cum ar fi sunete sau imagini. Fiecare eșantion este transformat într-o secvență de biți, care va fi apoi concatenată în fluxul binar, pentru a fi scrisă într-un fișier sau transmisă.
Sportul de aici constă în reducerea dimensiunii totale pe care o ocupă acest flux de biți, fără a pierde nicio informație: fiecare număr codificat trebuie să dea aceeași ieșire după decodare. Există multe tehnici cu procesare mai mult sau mai puțin complicată, dar aici vom considera că fiecare număr pe care trebuie codat (numit n) este independent de vecini. Tratăm fiecare eșantion în acest fel fără a ne face griji cu privire la precedent sau la următor, ceea ce face din n un număr oarecum abstract, dar în scopul experimentului, este întotdeauna un număr întreg mai mare sau egal cu zero.
În cazul în care experimentul începe să devină interesant este faptul că decodificarea biților numărului nostru n necesită să cunoaștem în prealabil, într-un fel sau altul, o informație auxiliară: limita (numită L) care indică ce valoare maximă poate lua numărul nostru n. Prin urmare, putem scrie următoarea ecuație:
Arta entropistului (sau a entropologului?) Este, prin urmare, de a transmite această limită fără a ocupa mai mult spațiu decât originalul, dar acest articol se concentrează asupra modului în care aceste două valori n și L se pot combina, astfel încât n doar să folosească idealul numărul de biți.
Un cod binar clasic folosește k biți pentru a reprezenta un număr între 0 și 2 k -1. De exemplu, cu k = 4, putem reprezenta 24 = 16 simboluri, care sunt cel mai adesea asociate cu numerele de la 0 la 15. Dacă limita noastră este 15, atunci numărul nostru n va folosi 4 biți, nici mai mult, nici mai puțin. Ca regulă generală, dacă limita L este egală cu 2 k -1, atunci se utilizează k biți. În schimb, când știm L, atunci putem calcula numărul de biți k = log2 (L) .
Dar o limită exact egală cu o putere de doi este un caz destul de rar. De cele mai multe ori, limita noastră L va fi între două puteri de două: 2k -1k. Atunci trebuie să alocăm întotdeauna k biți, dar vor rămâne 2 k-L coduri neutilizate, coduri care vor ocupa un loc virtual, o fracțiune de bit care ajunge să cântărească pe toate datele. Acest spațiu de codare pierdut este reprezentat de triunghiurile albe din Figura 1, deoarece un bit nu este divizibil.
Există tehnici apropiate de ideal, cum ar fi codurile aritmetice [3] și codarea intervalului [4] cu care se găsește un simbol amestecat cu cele precedente, care eliberează numerele de limita arbitrară a biților individuali. Dezavantajul este că acest tip de cod este relativ complex și dificil de implementat. În special, codurile aritmetice efectuează calcule pe numere întregi cu multiplicări, care ocupă resurse materiale substanțiale în cazul unei realizări materiale. Și în timp ce dezvolt un CODEC destinat să folosească cât mai puține porți logice posibil, acest tip de abordare este exclus.