El código Even-Rodeh es un código universal que codifica los enteros no negativos desarrollados por Shimon Even y Michael Rodeh . [1]
Codificación
Para codificar un entero N no negativo en la codificación Even-Rodeh:
- Si N no es menor que 4, establezca el valor codificado en un solo
0
bit. De lo contrario, el valor codificado está vacío. - Si N es menor que 8, anteponga al valor codificado 3 bits que contengan el valor de N y deténgase.
- Anteponer el valor codificado con el binario representación de N .
- Almacenar el número de bits antepone en el paso 3 como el nuevo valor de N .
- Regrese al paso 2.
Para decodificar un número entero codificado en Even-Rodeh:
- Leer 3 bits y almacenar el valor en N .
- Si se lee el primer bit
0
, deténgase. El número decodificado es N . - Si se leyó el primer bit
1
, continúe con el paso 2.
- Si se lee el primer bit
- Examine el siguiente bit.
- Si el bit es
0
, lea 1 bit y pare. El número decodificado es N . - Si el bit se
1
lee N bits, almacene el valor como el nuevo valor de N y vuelva al paso 2.
- Si el bit es
Ejemplos de
Número | Codificación | Probabilidad implícita |
---|---|---|
0 | 000 | 1/8 |
1 | 001 | 1/8 |
2 | 010 | 1/8 |
3 | 011 | 1/8 |
4 | 100 0 | 1/16 |
5 | 101 0 | 1/16 |
6 | 110 0 | 1/16 |
7 | 111 0 | 1/16 |
8 | 100 1000 0 | 1/256 |
9 | 100 1001 0 | 1/256 |
︙ | ||
15 | 100 1111 0 | 1/256 |
dieciséis | 101 10000 0 | 1/512 |
︙ | ||
2761 | 100 1100 101011001001 0 | 1 / 1.048.576 |
︙ |
Ver también
Referencias
- ^ Incluso, Shimon ; Rodeh, Michael (abril de 1978). "Codificación económica de comas entre cadenas". Comunicaciones de la ACM . 21 (4): 315–317. doi : 10.1145 / 359460.359480 .