¿Hay alguna forma de usar medios bits?

19

Como la mayoría de las personas aquí saben, al usar 4 bits, podemos contar de 0 a 15 (0123456789ABCDEF en hexadecimal). Pero si solo tuviéramos que contar hasta 9, seguiríamos usando 4 bits, y los dígitos de la A a la F se desperdiciarían.

Sin embargo, página de códigos QR de Wikipedia indica que usar solo dígitos numéricos del 0 al 9 usa 3⅓ bits por carácter, que es correcto desde un punto de vista estadístico. Y, sin embargo, un tercio de un bit no es un objeto físico, y el envío de un número del 0 al 9 utiliza al menos 4 bits, que yo sepa.

¿Hay alguna forma de usar las combinaciones desperdiciadas para enviar efectivamente un personaje con fracciones de bits?

Bien, déjeme dar un ejemplo: los dos dígitos "27" deben enviarse. Con las técnicas de codificación normales, los bits enviados serían 00100111. Entonces podríamos 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 1101 0 111. Por otro lado, si se deben enviar los dígitos "28", el primer bit después de '2' es un 1, por lo que se reemplaza por el dígito 'F', dando como resultado la cadena 1111 1 000.

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

    
pregunta Galahad78

10 respuestas

22

No puede enviar la mitad de un bit, pero puede empacar efectivamente dos mitades en un bit antes de la transmisión o el almacenamiento.

Usted mismo da un ejemplo, por lo que efectivamente ha respondido su propia pregunta con un SÍ.

Una forma quizás más fácil es codificar simplemente el valor de dos dígitos decimales en 7 bits. (Tipo de decimal codificado en binario).

    
respondido por el Wouter van Ooijen
19

Puede usar la codificación huffman para que los números tengan una longitud de bits variable. si conoce un dígito que ocurrirá con más frecuencia que otros, será útil.

ejemplo (con igual ocurrencia):

0 - 1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

Ejemplo de final de recepción para obtener el número 1:

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

el segundo bit entra y deja solo de 0 a 2 como opciones.

el tercer bit entra y deja 0 a 1 como opciones.

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

    
respondido por el markg
12

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

Cotizando Wikipedia :

  

La codificación aritmética difiere de otras formas de codificación de entropía, como la codificación de Huffman, en lugar de separar la entrada en símbolos componentes y reemplazar cada uno por 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).

    
respondido por el Hugh Allen
10

El nuevo IEEE P754 para la aritmética de punto flotante ahora define formatos decimales además de binarios. Una de las codificaciones propone agrupar dígitos digitales por 3 en 10 bits.

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

Densely Packed Decimal : enlace

    
respondido por el TEMLIB
4

Una correspondencia 1: 1 de binario (o Hexadecimal) es solo una codificación de símbolo para bits. Así que sí, como lo demostraste es posible. Otro lugar en el que se utiliza es (pero de manera ligeramente diferente) es la codificación / decodificación en trellis en sistemas de comunicación en los que las transiciones de bits se mantienen más separadas para facilitar la decodificació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 más grande ligeramente redundante para obtener el equilibrio de CC, la separación de símbolos y los códigos de control en subbandas. / p>     

respondido por el placeholder
4

La representación de datos depende de la interpretación que usted o su programa le brinden.

Podríamos enviar '27' también como caracteres ASCII, por ejemplo, dando 0x3237 = 0b0011001000110111 .

La forma en que desea representar los datos en bits depende de su aplicación. Al final, con una variable \ $ x \ $ con \ $ n (x) \ $ diferentes valores posibles, necesitará \ $ {\ lceil \ log_2 {n (x)} \ rceil} \ $ bits .

Ahora suponga que tiene dos variables \ $ x_1, x_2 \ $ con \ $ n (x_1), n (x_2) \ $ valores posibles. Si los almacena por separado, necesitará \ $ \ lceil \ log_2n (x_1) \ rceil + \ lceil \ log_2n (x_2) \ rceil \ $ bits. Sin embargo, si los almacena juntos, solo necesitará \ $ \ left \ lceil \ log_2 \ left (n (x_1) \ cdot n (x_2) \ right) \ right \ rceil \ $ bits.

En su ejemplo con el envío de dos dígitos, ambos dígitos pueden tener 10 valores diferentes. Si los almacena por separado, necesita \ $ 2 \ cdot \ lceil \ log_2 (10) \ rceil = 2 \ cdot4 = 8 \ $ bits. Sin embargo, si los almacena juntos, necesita \ $ \ lceil \ log_2 (10 \ cdot10) \ rceil = 7 \ $ bits.

Siempre depende de la aplicación, pero normalmente cuando 'une' variables como sugiere, costará más potencia de cálculo si desea realizar operaciones en estas variables. Las operaciones de suma y resta en las variables "unidas" son más complejas de lo normal y pueden requerir más espacio en el hardware o causar retrasos más prolongados.

Nota: \ $ \ lceil \ dots \ rceil \ $ es la notación para redondear .

    
respondido por el Keelan
1

La forma habitual de empaquetar valores es multiplicar cada valor con su rango, por lo que terminas con un gran número que puedes representar de manera eficiente en bits. Al desempaquetar, se divide por rango, el resto es el dígito y el resultado son los restantes dígitos empaquetados.

Si tiene 5 valores en el rango de 0 a 2, puede representar eso en 8 bits (necesita al menos 7,92 bits para representar los valores) en lugar de los 10 bits utilizados por la forma ingenua de usar 2 bits para cada valor, haciendo ((((n 1 * 3 + n 2 ) * 3 + n 3 ) * 3 + n 4 ) * 3 + n 5

    
respondido por el Rinze Smits
1

En teoría, si está dispuesto a gastar espacio en el circuito y energía para el detector de alta impedancia, puede enviar 3 estados por un cable digital (1, 0 y alto-Z). Descargo de responsabilidad: esto funciona muy bien en el simulador. No sé si el circuito tiene algunos problemas que lo hacen poco práctico, como decir que realmente no se puede cambiar tan rápido como un par de puertas normales.

Mi término normal para una transición de señal de alto-Z a señal (donde la señal generalmente se conecta a tierra en silicio) es una señal de medio bit.

    
respondido por el Joshua
1

Desea enviar un dígito decimal, necesitando 3⅓ bits. Pero tendrá que usar 4 bits, porque no puede enviar un tercio de un bit.

Por lo tanto, para descubrir qué significa realmente 3⅓ bits, necesita dos (o tres) dígitos de 3⅓ bits cada uno. Si desea enviar 2 (3) dígitos decimales entre 0 y 9, cada uno de los cuales necesita un poco menos de 3⅓ bits, puede hacerlo utilizando 7 (10) bits. La prueba constructiva es fácil:

Los 7 (10) bits le permiten codificar un número entre 0 y 128 (1023), pero solo necesitará 00 (000) a 99 (999), que son todas las codificaciones posibles de dos (tres) dígitos decimales. Q.E.D.

    
respondido por el Alexander
1

Creo que no entiendes lo que significa el artículo de wiki vinculado. Lo que se quiere decir es que para una cadena de caracteres que es completamente numérica (sin espacios, comas o puntos), utilizando la compresión ideal, puede representar cada carácter utilizando 3 1 / 3 bits en promedio . En realidad, es un poco mejor que esto, ya que los cálculos matemáticos indican que puede obtener el registro 2 (10) = 3.3219 bits / carácter a largo plazo.

De manera similar, para el conjunto de caracteres alfanuméricos más algunos (solo en mayúsculas y 9 símbolos), o 45 caracteres, necesita el registro 2 (45) = 5.4918 bits / carácter, que se redondea a 5.5 en el artículo.

Los bits / caracteres reducidos se logran mediante la compresión, ya sea con una codificación predeterminada o un esquema de compresión especificado por el estándar QR (no estoy seguro de cuál se utiliza). Representa el número promedio de bits que necesitará un carácter para ser codificado, por lo que un carácter individual se codificará utilizando más o menos bits. También tenga en cuenta que los valores enumerados anteriormente son los valores ideales para cadenas infinitas y aleatorias. Es posible obtener relaciones de compresión que sean mejores o peores para cuerdas especialmente diseñadas.

    
respondido por el MBraedley

Lea otras preguntas en las etiquetas