Codificación Chen – Ho - Chen–Ho encoding

La codificación Chen – Ho es un sistema alternativo de codificación binaria para dígitos decimales que ahorra memoria .

El sistema tradicional de codificación binaria para dígitos decimales, conocido como decimal codificado en binario (BCD), utiliza cuatro bits para codificar cada dígito, lo que resulta en un desperdicio significativo de ancho de banda de datos binarios (ya que cuatro bits pueden almacenar 16 estados y se utilizan para almacenar solo 10), incluso cuando se utiliza BCD empaquetado .

La codificación reduce los requisitos de almacenamiento de dos dígitos decimales (100 estados) de 8 a 7 bits, y los de tres dígitos decimales (1000 estados) de 12 a 10 bits utilizando solo transformaciones booleanas simples evitando operaciones aritméticas complejas como una conversión de base .

Historia

En lo que parece haber sido un descubrimiento múltiple , algunos de los conceptos detrás de lo que más tarde se conocería como codificación Chen-Ho fueron desarrollados independientemente por Theodore M. Hertz en 1969 y por Tien Chi Chen (陳 天機) (1928–) en 1971.

Hertz of Rockwell presentó una patente para su codificación en 1969, que fue otorgada en 1971.

Chen discutió por primera vez sus ideas con Irving Tze Ho (何宜慈) (1921-2003) en 1971. Chen y Ho trabajaban para IBM en ese momento, aunque en diferentes ubicaciones. Chen también consultó con Frank Chin Tung para verificar los resultados de sus teorías de forma independiente. IBM presentó una patente a su nombre en 1973, que fue concedida en 1974. Al menos en 1973, el trabajo anterior de Hertz debe haber sido conocido por ellos, ya que la patente cita su patente como técnica anterior .

Con el aporte de Joseph D. Rutledge y John C. McPherson, la versión final de la codificación Chen-Ho circuló dentro de IBM en 1974 y se publicó en 1975 en la revista Communications of the ACM . Esta versión incluyó varias mejoras, principalmente relacionadas con la aplicación del sistema de codificación. Constituye un código de prefijo similar a Huffman .

La codificación se denomina esquema de Chen y Ho en 1975, la codificación de Chen en 1982 y se hizo conocido como Chen-Ho codificación o algoritmo de Chen-Ho desde el año 2000. Después de haber presentado una patente para ello en 2001, Michael F. Cowlishaw publicaron un mayor refinamiento de la codificación Chen-Ho conocida como codificación decimal densamente empaquetada (DPD) en IEE Proceedings - Computers and Digital Techniques en 2002. Posteriormente, DPD se adoptó como la codificación decimal utilizada en IEEE 754-2008 e ISO / IEC / IEEE 60559: Estándares de punto flotante de 2011 .

Solicitud

Chen notó que los dígitos del cero al siete simplemente se codificaron usando tres dígitos binarios del grupo octal correspondiente . También postuló que se podría usar una bandera para identificar una codificación diferente para los dígitos ocho y nueve, que se codificarían usando un solo bit.

En la práctica, se aplica una serie de transformaciones booleanas al flujo de bits de entrada, comprimiendo dígitos codificados en BCD de 12 bits por tres dígitos a 10 bits por tres dígitos. Las transformaciones invertidas se utilizan para decodificar el flujo codificado resultante en BCD. También se pueden lograr resultados equivalentes mediante el uso de una tabla de consulta .

La codificación Chen – Ho se limita a codificar conjuntos de tres dígitos decimales en grupos de 10 bits (los denominados declets ). De los 1024 estados posibles mediante el uso de 10 bits, solo deja 24 estados sin usar (con los bits de indiferencia generalmente se establecen en 0 en escritura e ignorados en lectura). Con solo un 0,34% de desperdicio, proporciona una codificación un 20% más eficiente que BCD con un dígito en 4 bits.

Tanto Hertz como Chen también propusieron esquemas de codificación similares, pero menos eficientes, para comprimir conjuntos de dos dígitos decimales (que requieren 8 bits en BCD) en grupos de 7 bits.

Los conjuntos más grandes de dígitos decimales se pueden dividir en grupos de tres y dos dígitos.

Las patentes también discuten la posibilidad de adaptar el esquema a dígitos codificados en cualquier otro código decimal que no sea 8-4-2-1 BCD , como fe Exceso-3 , Exceso-6 , Saltar en 2 , Saltar en 8 , Código Gray , Glixon , O'Brien tipo I y Gray-Stibitz . Los mismos principios también podrían aplicarse a otras bases.

En 1973, una cierta forma de Chen Ho-codificación parece haber sido utilizado en el hardware de conversión de direcciones de la opcional IBM 7070 / 7074 función de emulación para el IBM System / 370 modelo 165 y 370 Modelo 168 ordenadores.

Una aplicación destacada utiliza un registro de 128 bits para almacenar 33 dígitos decimales con un exponente de tres dígitos, efectivamente no menos de lo que se podría lograr usando codificación binaria (mientras que la codificación BCD necesitaría 144 bits para almacenar el mismo número de dígitos).

Codificaciones para dos dígitos decimales

Codificación Hertz

Codificación de datos decimales en hercios para una sola heptada (formulario de 1969)
Codificación binaria Dígitos decimales
Espacio de código (128 estados) b6 b5 b4 b3 b2 b1 b0 d1 d0 Valores codificados Descripción Ocurrencias (100 estados)
50% (64 estados) 0 a B C D mi F 0 abc 0 def (0–7) (0–7) Dos dígitos más bajos 64% (64 estados)
12,5% (16 estados) 1 1 0 C D mi F 100 c 0 def (8–9) (0–7) Un dígito más bajo,
un dígito más alto
16% (16 estados)
12,5% (16 estados) 1 0 1 F a B C 0 abc 100 f (0–7) (8–9) 16% (16 estados)
12,5% (16 estados, 4 usados) 1 1 1 C X X F 100 c 100 f (8–9) (8–9) Dos dígitos más altos 4% (4 estados)
12,5% (16 estados, 0 usados) 1 0 0 X X X X 0% (0 estados)
  • Esta codificación no preserva la paridad .

Codificación temprana de Chen-Ho, método A

Codificación de datos decimales para una sola heptada (formulario de principios de 1971, método A)
Codificación binaria Dígitos decimales
Espacio de código (128 estados) b6 b5 b4 b3 b2 b1 b0 d1 d0 Valores codificados Descripción Ocurrencias (100 estados)
50% (64 estados) 0 a B C D mi F 0 abc 0 def (0–7) (0–7) Dos dígitos más bajos 64% (64 estados)
25% (32 estados, 16 usados) 1 0 x (b) C D mi F 100 c 0 def (8–9) (0–7) Un dígito más bajo,
un dígito más alto
16% (16 estados)
12,5% (16 estados) 1 1 0 F a B C 0 abc 100 f (0–7) (8–9) 16% (16 estados)
12,5% (16 estados, 4 usados) 1 1 1 C x (a) x (b) F 100 c 100 f (8–9) (8–9) Dos dígitos más altos 4% (4 estados)
  • Esta codificación no preserva la paridad.

Codificación temprana de Chen-Ho, método B

Codificación de datos decimales para una sola heptada (formulario de principios de 1971, método B)
Codificación binaria Dígitos decimales
Espacio de código (128 estados) b6 b5 b4 b3 b2 b1 b0 d1 d0 Valores codificados Descripción Ocurrencias (100 estados)
50% (64 estados) 0 a B C D mi F 0 abc 0 def (0–7) (0–7) Dos dígitos más bajos 64% (64 estados)
12,5% (16 estados) 1 0 C 0 D mi F 100 c 0 def (8–9) (0–7) Un dígito más bajo,
un dígito más alto
16% (16 estados)
12,5% (16 estados, 4 usados) 1 0 C 1 X X F 100 c 100 f (8–9) (8–9) Dos dígitos más altos 4% (4 estados)
12,5% (16 estados) 1 1 F 0 a B C 0 abc 100 f (0–7) (8–9) Un dígito más bajo,
un dígito más alto
16% (16 estados)
12,5% (16 estados, 0 usados) 1 1 X 1 X X X 0% (0 estados)
  • Esta codificación no preserva la paridad.

Codificación Chen-Ho patentada y final

Codificación de datos decimales para una sola heptada (formulario patentado de 1973 y formulario final de 1975)
Codificación binaria Dígitos decimales
Espacio de código (128 estados) b6 b5 b4 b3 b2 b1 b0 d1 d0 Valores codificados Descripción Ocurrencias (100 estados)
50% (64 estados) 0 a B C D mi F 0 abc 0 def (0–7) (0–7) Dos dígitos más bajos 64% (64 estados)
25,0% (32 estados, 16 usados) 1 0 x (b) C D mi F 100 c 0 def (8–9) (0–7) Un dígito más bajo,
un dígito más alto
16% (16 estados)
12,5% (16 estados) 1 1 1 C a B F 0 abc 100 f (0–7) (8–9) 16% (16 estados)
12,5% (16 estados, 4 usados) 1 1 0 C x (a) x (b) F 100 c 100 f (8–9) (8–9) Dos dígitos más altos 4% (4 estados)

Codificaciones para tres dígitos decimales

Codificación Hertz

Codificación de datos decimales en hercios para un solo delet (formulario de 1969)
Codificación binaria Dígitos decimales
Espacio de código (1024 estados) b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 d2 d1 d0 Valores codificados Descripción Ocurrencias (1000 estados)
50,0% (512 estados) 0 a B C D mi F gramo h I 0 abc 0 def 0 ghi (0–7) (0–7) (0–7) Tres dígitos más bajos 51,2% (512 estados)
37,5% (384 estados) 1 0 0 C D mi F gramo h I 100 c 0 def 0 ghi (8–9) (0–7) (0–7) Dos dígitos más bajos,
un dígito más alto
38,4% (384 estados)
1 0 1 F a B C gramo h I 0 abc 100 f 0 ghi (0–7) (8–9) (0–7)
1 1 0 I a B C D mi F 0 abc 0 def 100 i (0–7) (0–7) (8–9)
9.375% (96 estados) 1 1 1 F 0 0 I a B C 0 abc 100 f 100 i (0–7) (8–9) (8–9) Un dígito más bajo,
dos dígitos más altos
9,6% (96 estados)
1 1 1 C 0 1 I D mi F 100 c 0 def 100 i (8–9) (0–7) (8–9)
1 1 1 C 1 0 F gramo h I 100 c 100 f 0 ghi (8–9) (8–9) (0–7)
3,125% (32 estados, 8 usados) 1 1 1 C 1 1 F ( 0 ) ( 0 ) I 100 c 100 f 100 i (8–9) (8–9) (8–9) Tres dígitos más altos, a los bits b2 y b1 no les importa 0,8% (8 estados)
  • Esta codificación no preserva la paridad.

Codificación temprana de Chen-Ho

Codificación de datos decimales para un solo delet (formulario de principios de 1971)
Codificación binaria Dígitos decimales
Espacio de código (1024 estados) b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 d2 d1 d0 Valores codificados Descripción Ocurrencias (1000 estados)
50,0% (512 estados) 0 a B C D mi F gramo h I 0 abc 0 def 0 ghi (0–7) (0–7) (0–7) Tres dígitos más bajos 51,2% (512 estados)
37,5% (384 estados) 1 0 0 C D mi F gramo h I 100 c 0 def 0 ghi (8–9) (0–7) (0–7) Dos dígitos más bajos,
un dígito más alto
38,4% (384 estados)
1 0 1 F gramo h I a B C 0 abc 100 f 0 ghi (0–7) (8–9) (0–7)
1 1 0 I a B C D mi F 0 abc 0 def 100 i (0–7) (0–7) (8–9)
9.375% (96 estados) 1 1 1 0 0 F I a B C 0 abc 100 f 100 i (0–7) (8–9) (8–9) Un dígito más bajo,
dos dígitos más altos
9,6% (96 estados)
1 1 1 0 1 I C D mi F 100 c 0 def 100 i (8–9) (0–7) (8–9)
1 1 1 1 0 C F gramo h I 100 c 100 f 0 ghi (8–9) (8–9) (0–7)
3,125% (32 estados, 8 usados) 1 1 1 1 1 C F I ( 0 ) ( 0 ) 100 c 100 f 100 i (8–9) (8–9) (8–9) Tres dígitos más altos, a los bits b1 y b0 no les importa 0,8% (8 estados)
  • Esta codificación no preserva la paridad.

Codificación Chen-Ho patentada

Codificación de datos decimales para un solo delet (formulario patentado de 1973)
Codificación binaria Dígitos decimales
Espacio de código (1024 estados) b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 d2 d1 d0 Valores codificados Descripción Ocurrencias (1000 estados)
50,0% (512 estados) 0 a B D mi gramo h C F I 0 abc 0 def 0 ghi (0–7) (0–7) (0–7) Tres dígitos más bajos 51,2% (512 estados)
37,5% (384 estados) 1 0 0 D mi gramo h C F I 100 c 0 def 0 ghi (8–9) (0–7) (0–7) Dos dígitos más bajos,
un dígito más alto
38,4% (384 estados)
1 0 1 a B gramo h C F I 0 abc 100 f 0 ghi (0–7) (8–9) (0–7)
1 1 0 D mi a B C F I 0 abc 0 def 100 i (0–7) (0–7) (8–9)
9.375% (96 estados) 1 1 1 1 0 a B C F I 0 abc 100 f 100 i (0–7) (8–9) (8–9) Un dígito más bajo,
dos dígitos más altos
9,6% (96 estados)
1 1 1 0 1 D mi C F I 100 c 0 def 100 i (8–9) (0–7) (8–9)
1 1 1 0 0 gramo h C F I 100 c 100 f 0 ghi (8–9) (8–9) (0–7)
3,125% (32 estados, 8 usados) 1 1 1 1 1 ( 0 ) ( 0 ) C F I 100 c 100 f 100 i (8–9) (8–9) (8–9) Tres dígitos más altos, a los bits b4 y b3 no les importa 0,8% (8 estados)
  • Esta codificación no preserva la paridad.

Codificación final Chen-Ho

Codificación de datos decimales Chen-Ho para un solo delet (formulario final de 1975)
Codificación binaria Dígitos decimales
Espacio de código (1024 estados) b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 d2 d1 d0 Valores codificados Descripción Ocurrencias (1000 estados)
50,0% (512 estados) 0 a B C D mi F gramo h I 0 abc 0 def 0 ghi (0–7) (0–7) (0–7) Tres dígitos más bajos 51,2% (512 estados)
37,5% (384 estados) 1 0 0 C D mi F gramo h I 100 c 0 def 0 ghi (8–9) (0–7) (0–7) Dos dígitos más bajos,
un dígito más alto
38,4% (384 estados)
1 0 1 C a B F gramo h I 0 abc 100 f 0 ghi (0–7) (8–9) (0–7)
1 1 0 C D mi F a B I 0 abc 0 def 100 i (0–7) (0–7) (8–9)
9.375% (96 estados) 1 1 1 C 0 0 F a B I 0 abc 100 f 100 i (0–7) (8–9) (8–9) Un dígito más bajo,
dos dígitos más altos
9,6% (96 estados)
1 1 1 C 0 1 F D mi I 100 c 0 def 100 i (8–9) (0–7) (8–9)
1 1 1 C 1 0 F gramo h I 100 c 100 f 0 ghi (8–9) (8–9) (0–7)
3,125% (32 estados, 8 usados) 1 1 1 C 1 1 F ( 0 ) ( 0 ) I 100 c 100 f 100 i (8–9) (8–9) (8–9) Tres dígitos más altos, a los bits b2 y b1 no les importa 0,8% (8 estados)
  • Esta codificación no preserva la paridad.

Eficiencia de almacenamiento

Eficiencia de almacenamiento
BCD Bits necesarios Diferencia de bits
Dígitos Estados Bits Espacio de código binario Codificación binaria [A] Codificación de 2 dígitos [B] Codificación de 3 dígitos [C] Codificación mixta Mixto vs binario Mixto vs.BCD
1 10 4 dieciséis 4 (7) (10) 4 [1 × A] 0 0
2 100 8 128 7 7 (10) 7 [1 × B] 0 −1
3 1000 12 1024 10 (14) 10 10 [1 × C] 0 −2
4 10 000 dieciséis 16 384 14 14 (20) 14 [2 × B] 0 −2
5 100 000 20 131 072 17 (21) (20) 17 [1 × C + 1 × B] 0 −3
6 1 000 000 24 1 048 576 20 21 20 20 [2 × C] 0 −4
7 10 000 000 28 16 777 216 24 (28) (30) 24 [2 × C + 1 × A] 0 −4
8 100 000 000 32 134 217 728 27 28 (30) 27 [2 × C + 1 × B] 0 −5
9 1 000 000 000 36 1 073 741 824 30 (35) 30 30 [3 × C] 0 −6
10 10 000 000 000 40 17 179 869 184 34 35 (40) 34 [3 × C + 1 × A] 0 −6
11 100 000 000 000 44 137 438 953 472 37 (42) (40) 37 [3 × C + 1 × B] 0 −7
12 1 000 000 000 000 48 1 099 511 627 776 40 42 40 40 [4 × C] 0 −8
13 10 000 000 000 000 52 17 592 186 044 416 44 (49) (50) 44 [4 × C + 1 × A] 0 −8
14 100 000 000 000 000 56 140 737 488 355 328 47 49 (50) 47 [4 × C + 1 × B] 0 −9
15 1 000 000 000 000 000 60 1 125 899 906 842 624 50 (56) 50 50 [5 × C] 0 −10
dieciséis 10 000 000 000 000 000 64 18 014 398 509 481 984 54 56 (60) 54 [5 × C + 1 × A] 0 −10
17 100 000 000 000 000 000 68 144 115 188 075 855 872 57 (63) (60) 57 [5 × C + 1 × B] 0 −11
18 1 000 000 000 000 000 000 72 1 152 921 504 606 846 976 60 63 60 60 [6 × C] 0 −12
19 10 000 000 000 000 000 000 76 18 de 446 744 073 709 551 616 64 (70) (70) 64 [6 × C + 1 × A] 0 −12
20 ... 80 ... 67 70 (70) 67 [6 × C + 1 × B] 0 −13
21 ... 84 ... 70 (77) 70 70 [7 × C] 0 −14
22 ... 88 ... 74 77 (80) 74 [7 × C + 1 × A] 0 −14
23 ... 92 ... 77 (84) (80) 77 [7 × C + 1 × B] 0 −15
24 ... 96 ... 80 84 80 80 [8 × C] 0 −16
25 ... 100 ... 84 (91) (90) 84 [8 × C + 1 × A] 0 −16
26 ... 104 ... 87 91 (90) 87 [8 × C + 1 × B] 0 −17
27 ... 108 ... 90 (98) 90 90 [9 × C] 0 −18
28 ... 112 ... 94 98 (100) 94 [9 × C + 1 × A] 0 −18
29 ... 116 ... 97 (105) (100) 97 [9 × C + 1 × B] 0 −19
30 ... 120 ... 100 105 100 100 [10 × C] 0 −20
31 ... 124 ... 103 (112) (110) 104 [10 × C + 1 × A] +1 −20
32 ... 128 ... 107 112 (110) 107 [10 × C + 1 × B] 0 −21
33 ... 132 ... 110 (119) 110 110 [11 × C] 0 −22
34 ... 136 ... 113 119 (120) 114 [11 × C + 1 × A] +1 −22
35 ... 140 ... 117 (126) (120) 117 [11 × C + 1 × B] 0 −23
36 ... 144 ... 120 126 120 120 [12 × C] 0 −24
37 ... 148 ... 123 (133) (130) 124 [12 × C + 1 × A] +1 −24
38 ... 152 ... 127 133 (130) 127 [12 × C + 1 × B] 0 −25
... ... ... ... ... ... ... ... ... ...

Ver también

Notas

Referencias

Otras lecturas