¿Hay alguna forma de usar medias bits?

Question

Como la mayoría de la gente aquí sabe, utilizando 4 bits, podemos contar de 0 a 15 (0123456789ABCDEF en hexadecimal). Pero si solo contáramos hasta 9, todavía estaríamos usando 4 bits, y los dígitos de la A a la F se desperdiciarían.

Sin embargo, la página de Código QR de Wikipedia afirma que al utilizar solo dígitos numéricos del 0 al 9 se utilizan 3 bits por carácter, lo cual es correcto desde un punto de vista estadístico. Y aún así un tercio de un bit no es un objeto físico, y enviar un número del 0 al 9 utiliza al menos 4 bits según tengo entendido.

¿Hay alguna manera de utilizar las combinaciones desperdiciadas para enviar un carácter con fracciones de bits de manera efectiva?

De acuerdo, permíteme dar un ejemplo: Los dos dígitos "27" deben ser enviados. Con técnicas normales de codificación, los bits enviados serían 00100111. Podríamos entonces imaginar un sistema que reemplazaría el dígito '2' por el dígito 'E' o 'F', dependiendo del siguiente bit; en este caso, el siguiente bit es 0, por lo que el '2' se reemplaza por 'E'. La cadena de bits resultante sería entonces 11010111. Por otro lado, si los dígitos "28" deben ser enviados, el primer bit después del '2' es un 1, por lo que se reemplaza por el dígito 'F' en su lugar, dando como resultado la cadena 11111000.

En ambos casos, se ha logrado una economía de 1 bit, porque un nibble se utilizó para dos caracteres diferentes. En otras palabras, se utilizan tres y medio bits en cada carácter.

Answer 1

No se puede enviar medio bit, pero se pueden empaquetar efectivamente dos medias bits en un bit antes de la transmisión o almacenamiento.

Tú mismo das un ejemplo, así que efectivamente has respondido a tu propia pregunta con un SÍ.

Una forma quizás un poco más sencilla es codificar simplemente el valor de dos dígitos decimales en 7 bits. (Una especie de codificación binaria de doble decimal).

Answer 2

Puedes usar codificación Huffman para que los números tengan longitudes de bits variables. Si conoces un dígito que ocurrirá más a menudo que los demás, te ayudará.

ejemplo (con ocurrencia igual):

0 - 1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

ejemplo en el extremo receptor para obtener el número 1:

El primer bit entra y deja solo las opciones de 0 a 4.

El segundo bit entra y deja solo las opciones de 0 a 2.

El tercer bit entra y deja las opciones de 0 a 1.

El cuarto bit entra y el número entrante es 1.

Answer 3

Tal vez lo que estás buscando es la Codificación Aritmética, que puede codificar eficientemente una cadena de símbolos, cada uno de los cuales en principio podría requerir un número fraccional (no entero) de bits. (aunque el mensaje total debe ser un número entero de bits)

Citando Wikipedia:

La codificación aritmética difiere de otras formas de codificación de entropía como la codificación Huffman en que en lugar de separar la entrada en símbolos individuales y reemplazar cada uno con un código, la codificación aritmética codifica el mensaje completo en un solo número, una fracción n donde (0.0 ≤ n < 1.0).

Answer 4

El nuevo IEEE P754 para aritmética de punto flotante ahora define formatos decimales además de binarios. Uno de los códigos propone agrupar dígitos decimales en conjuntos de 3 en 10 bits.

codificar de 0 a 999 usando 10 bits = 1024 códigos posibles es bastante eficiente, y los dígitos decimales a menudo se agrupan de tres de todas formas.

Decimal Densamente Empaquetado : http://en.wikipedia.org/wiki/Densely_packed_decimal

Answer 5

Una correspondencia 1:1 de binario (o hexadecimal) es solo una codificación de un símbolo para bits. Así que sí, como lo mostraste, es posible. Otro lugar donde se utiliza esto es (pero ligeramente diferente) en la codificación/descodificación de tramas en sistemas de comunicación en los que las transiciones de bits se mantienen más alejadas para facilitar la descodificación. Y, por supuesto, la codificación 8b/10b y 64b/66b, etc., etc., es una idea similar, en la que un espacio de símbolos más pequeño se codifica en un espacio ligeramente redundante más grande para obtener equilibrio DC, separación de símbolos y códigos de control en subbandas.