# Context-adaptive binary arithmetic coding

Context-adaptive binary arithmetic coding o CABAC és un dels dos algoritmes que inclou l'estàndard de codificació H.264 en el seu bloc de codificació entròpica. El primer s'anomena Context-adaptive variable-length coding (CAVLC), el qual utilitza una taula VLC fixa per tots els elements sintàctics, i el segon és el CABAC.
El codificador CABAC presenta una millora en la dimensió del bitstream respecte a CAVLC, donat que aconsegueix bitstreams un 10% més petits. L'arquitectura de CABAC demostra que és bastant bona, ja que pot comprimir eficientment el senyal original. Tot i així, el rendiment es podria millorar considerant que cada coeficient és estadísticament dependent dels seus veïns. Aquesta dependència podria utilitzar-se per a refinar el model estadístic de l'arquitectura original de CABAC.

## Procés de Codificació

El procés de codificació es pot resumir en les següents tres etapes:

### Binarització

L'estratègia de codificació de CABAC es basa a trobar un mètode de codificació eficient utilitzant un esquema binari com un tipus de preprocessat per als passos posteriors.
En el procés de binarització, quan entra un element no binari aquest es posa en una seqüència binaria de longitud variable (bin-string). Aquest nou dígit s'anomena bin. Amb aquest pas s'aconsegueix la conversió a binari de l'element. En contraposició, quan entra un valor binari no es necessita cap mena de conversió i, per tant, es pot saltar el pas de binarització. D'aquesta manera, els símbols d'entrada pel codificador aritmètic són sempre valors binaris, independentment de les característiques de la sintaxi de l'element.
Existeixen tres tipus diferents de binarització:
* Unary
* Truncated unary (TU)
* K-th order Exp-Golomb code (EGk)
* Fixed length Code

### Modelat de context

Un model de context és un model de probabilitat per un o més bins del símbol binaritzat. Aquest model es pot escollir d'entre una selecció de models disponibles en funció de les estadístiques de la informació dels símbols recentment codificats. Existeixen dos tipus de modes: el regular o el bypass. El mode bypass s'escull quan la distribució dels bins és uniforme, permetent doncs saltar-se tot el procés de codificació binari-aritmètic (BAC), ja que la probabilitat que el valor del bin sigui '0' ó '1' és pràcticament la mateixa.
En canvi, en el mode regular, és necessari conèixer amb quina probabilitat obtindrem un '0' ó '1'. Per tant, necessitem crear un model de context, ja que aquest emmagatzema la probabilitat que cada bin sigui '0' o '1'. Aquest mode de decisió s'aplica als bins observats amb més freqüència.
Finalment, el valor del bin, amb la seva probabilitat, s'envia al codificador binari aritmètic.

### Codificació Binari Aritmètic(BAC)

En l'últim nivell del codificador, cada valor del bin entra en el codificador binari aritmètic, ja sigui a través del mode regular o del mode bypass.
La codificació dels bins que entren pel mode bypass és molt més ràpida, ja que la complexitat de l'algoritme de codificació és molt més reduïda, mentre que la codificació dels bins entrats pel mode regular depèn del model de probabilitat associat a aquell bin. El codificador, per tant, codifica cada bin depenent del model de probabilitat seleccionat i finalment, l'actualitza en funció del valor real del bin codificat.

## Exemple

1. Binaritza el valor Mvdx:
El primer bit del codi va al primer contenidor, el segon al contenidor posterior, i així successivament.
2. S'ha d'escollir un model de context per a cada contenidor. Un dels tres models seleccionats per al primer contenidor està basada en els valors del MVD codificat anteriorment. Es calcula la norma L1 de dos valors prèviament codificats, ek:
Si el valor ek és petit, hi ha una alta probabilitat que el MVD corresponent tingui una magnitud petita. D'altra banda, si ek és un valor gran es és probable que el valor MVD corresponent tingui una magnitud més gran. Nosaltres seleccionem una taula de probabilitat acord a aquest fet. Els contenidors restants es codifiquen utilitzant un dels 4 models de context més:
3. Es codifica cada contenidor. El model de context seleccionat genera dos estimacions de probabilitat: que el primer contenidor contingui un "1" o un "0". Aquestes estimacions determinen els dos sub-rangs que utilitza el codificador aritmétic per codificar el contenidor.
4. S'actualitzen els models de context. Per exemple, si el model de context 2 havia sigut seleccionat per al primer contenidor i el valor del contenidor 1 és "0", el recompte de la freqüència "0" s'incrementa. Això vol dir que la propera vegada que aquest model sigui seleccionat, la probabilitat d'un "0" serà una mica més alta. Quan el nombre total d'aparicions d'un model supera un valor llindar, el recompte de la freqüència de "0" i "1" es reduirà, això li dona major prioritat als valors recents.