¿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 tuviéramos que contar solo hasta 9, seguiríamos usando 4 bits, y los dígitos de A a F se desperdiciarían.

Sin embargo, la página de códigos QR de Wikipedia establece que el uso de solo dígitos numéricos del 0 al 9 usa 3⅓ bits por carácter, lo cual es correcto desde un punto de vista estadístico. Y sin embargo, un tercio de un bit no es un objeto físico, y enviar un número del 0 al 9 usa 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, permítanme dar un ejemplo: se deben enviar los dos dígitos "27". Con 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 1101 0 111. Por otro lado, si se deben enviar los dígitos "28", el primer bit después del '2' es un 1, por lo que se reemplaza por el dígito 'F' en su lugar, produciendo la cadena de 1.111 1 000.

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

Galahad78
fuente
2
Para obtener una perspectiva diferente sobre los valores de empaque en un espacio de dígitos más pequeño, consulte las computadoras Ternary ( en.wikipedia.org/wiki/Ternary_computer ). Si es lo suficientemente bueno para Knuth, ¡es lo suficientemente bueno para mí!
RLH
3
Mejor aún reconocer que puede calcular (10 * first_digit) + second_digity codificar eso en 7 bits, que representa 0 ... 99, con los códigos 100-127 restantes para otras cosas. Y aún hay más ahorros con 3 dígitos comprimidos en 10 bits.
Hot Licks
Para enviar los 100 valores diferentes por separado, lo mejor que puede obtener es empacar en 7 bits. Si tiene más dígitos, el embalaje será más eficiente. Si tiene menos de 64 valores para enviar, puede enviarlo usando solo 6 bits
phuclv

Respuestas:

22

No puede enviar medio bit, pero puede empaquetar efectivamente dos medios bits 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 más fácil es codificar el valor de dos dígitos decimales en 7 bits. (Una especie de código binario con doble decimal).

Wouter van Ooijen
fuente
1
Un buen caso de uso para empaquetar pares de dígitos en siete bits es cuando se transmiten archivos ASCII que consisten principalmente en datos numéricos. Cualquier valor de byte por debajo de 128 representa un solo carácter ASCII, mientras que 128-227 representa dos dígitos ASCII. Fácil de codificar o decodificar, y no requiere que los datos contengan principalmente dígitos (o incluso cualquier dígito), pero puede comprimir cadenas de dígitos en un 50% con mucha facilidad.
supercat
O ese formato PDP11 que contenía 3 caracteres alfanuméricos en 16 bits con un bit de repuesto ...
Brian Drummond
@BrianDrummond: Uno podría usar 16 bits para almacenar exactamente tres caracteres de un conjunto de 40, o hasta tres de un conjunto de 39, pero no habría un bit de repuesto. Normalmente "alfanumérico" implicaría un conjunto de al menos 36, pero la única forma de que hubiera un poco de repuesto sería si el conjunto se limitara a 32.
supercat
Pensé que era 5 bits / char. Alfanumérico se dividió en dos conjuntos de códigos, con un símbolo reservado para "cambiar el conjunto de códigos". Estaba equivocado: en.wikipedia.org/wiki/DEC_Radix-50 Aunque lo suficientemente extraño, solo lo vi una noche cuando tuve que decodificar un informe que alguien me dio en un disquete de 8 ", en un sistema CP / M, con solo una luz tenue recuerdo de Z80 asm.
Brian Drummond
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 recepción para obtener el número 1:

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

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

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

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

markg
fuente
12

Quizás lo que está 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 componentes 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)

Hugh Allen
fuente
10

El nuevo IEEE P754 para aritmética de coma flotante ahora define formatos decimales además de binarios. Una de las codificaciones propone agrupar los dígitos digitales por 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 por tres de todos modos.

Decimal empaquetado densamente : http://en.wikipedia.org/wiki/Densely_packed_decimal

TEMLIB
fuente
Incluso si los dígitos decimales se agrupan por tres, la semántica correcta de coma flotante decimal puede requerir que (1) escalar una mantisa por una potencia no múltiple de tres de diez implica multiplicar o dividir todos los componentes por 10 o 100; (2) algunos bits se pueden usar para la parte superior o inferior del número, dependiendo de (exponente mod 3); (3) Si el exponente se almacena en base 1000, entonces el grupo inferior de tres dígitos a veces debe redondearse al 10 más cercano o al 100 más cercano, en lugar de la unidad más cercana.
supercat
Personalmente, creo que los tipos como BigDecimalserían, para muchos propósitos, más eficientes si cada palabra tuviera 9 dígitos decimales en lugar de 32 bits, pero los comportamientos de redondeo no deberían verse afectados por la agrupación de dígitos.
supercat
4

Una correspondencia 1: 1 de binario (o hexadecimal) no es más que un símbolo que codifica bits. Entonces sí, como lo demostró es posible. Otro lugar en el que se usa esto es (pero de manera ligeramente diferente) es en la codificación / decodificación enrejada 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 un poco más grande y redundante para obtener el equilibrio de CC, la separación de símbolos y los códigos de control en sub-bandas.

marcador de posición
fuente
4

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

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

Xnorte(X)Iniciar sesión2norte(X)

X1,X2norte(X1),norte(X2)Iniciar sesión2norte(X1)+Iniciar sesión2norte(X2)Iniciar sesión2(norte(X1)norte(X2)) 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, necesita2Iniciar sesión2(10)=24 4=8bits Sin embargo, si los almacena juntos, necesitaIniciar sesión2(1010)=7 7 bits

Siempre depende de la aplicación, pero normalmente cuando 'une' variables como sugiere, le costará más potencia computacional si desea realizar operaciones en estas variables. Las operaciones de sumar y restar en variables 'unidas' son más complejas de lo normal, y pueden requerir más espacio en el hardware o causar retrasos más largos.


Nota: ...es la notación para redondear .


fuente
2

La forma habitual de empaquetar valores es multiplicando cada valor con su rango, de modo que termine con un gran número que pueda representar eficientemente en bits. Al desempacar, divide por rango, el resto es el dígito y el resultado son los dígitos empacados restantes.

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

Rinze Smits
fuente
¿Hay un nombre para este método de codificación?
Keegan Jay
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 alta 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 puede cambiar tan rápido como un par de puertas normales.

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

Joshua
fuente
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.

Entonces, 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 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 codificaciones posibles de dos (tres) dígitos decimales. QED

Alejandro
fuente
1

Creo que estás malinterpretando lo que se entiende en el artículo wiki vinculado. Lo que se quiere decir es que para una cadena de caracteres que es completamente numérico (sin espacios, comas o puntos), utilizando la compresión ideales, puede representar cada carácter utilizando 3 1 / 3 bits de promedio . En realidad, es un poco mejor que esto, ya que las matemáticas dicen que puedes obtener log 2 (10) = 3.3219 bits / carácter a largo plazo.

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

Los bits / caracteres reducidos se logran mediante compresión, ya sea con una codificación preestablecida o un esquema de compresión especificado por el estándar QR (no estoy seguro de cuál se usa). Representa el número promedio de bits que necesitará un carácter para poder codificarse, 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 mejores o peores para cadenas especialmente diseñadas.

MBraedley
fuente