Existe alguma maneira de usar meio bits?

19

Como a maioria das pessoas sabe, usando 4 bits, podemos contar de 0 a 15 (0123456789ABCDEF em hexadecimal). Mas se contássemos até 9, ainda estaríamos usando 4 bits, e os dígitos de A a F seriam desperdiçados.

No entanto, a página QR-Code da Wikipedia afirma que o uso apenas de dígitos numéricos de 0 a 9 usa 3⅓ bits por caractere, o que é correto do ponto de vista estatístico. E, no entanto, um terço de um bit não é um objeto físico, e o envio de um número de 0 a 9 usa pelo menos 4 bits, pelo que sei.

Existe alguma maneira de usar as combinações desperdiçadas para enviar efetivamente um personagem com frações de bits?

OK, deixe-me dar um exemplo: Os dois dígitos "27" devem ser enviados. Com técnicas normais de codificação, os bits enviados seriam 00100111. Poderíamos então imaginar um sistema que substituísse o dígito '2' pelo dígito 'E' ou 'F', dependendo do próximo bit; neste caso, o próximo bit é 0, então o '2' é substituído por 'E'. A sequência de bits resultante seria 1101 0 111. Por outro lado, se os dígitos "28" tiverem que ser enviados, o primeiro bit após o '2' será 1, sendo substituído pelo dígito 'F', produzindo a sequência 1111 1 000.

Nos dois casos, uma economia de 1 bit foi efetuada, porque uma mordidela foi usada para dois caracteres diferentes. Em outras palavras, três bits e meio são usados ​​em cada caractere.

Galahad78
fonte
2
Para uma perspectiva diferente sobre como empacotar valores em um espaço de dígito menor, consulte Computadores ternários ( pt.wikipedia.org/wiki/Ternary_computer ) Se é bom o suficiente para Knuth, é bom o suficiente para mim!
RLH
3
Melhor ainda reconhecer que você pode calcular (10 * first_digit) + second_digite codificar isso em 7 bits, representando 0 ... 99, com os códigos 100-127 restantes para outras coisas. E há ainda mais economia com 3 dígitos compactados em 10 bits.
Hot Licks
Para enviar todos os 100 valores diferentes separadamente, o melhor que você pode obter é compactar em 7 bits. Se você tiver mais dígitos, a embalagem será mais eficiente. Se você tem menos de 64 valores para enviar você pode enviá-lo usando apenas 6 bits
phuclv

Respostas:

22

Você não pode enviar meio bit, mas pode efetivamente empacotar dois meio bits em um bit antes da transmissão ou armazenamento.

Você mesmo dá um exemplo e efetivamente respondeu sua própria pergunta com um SIM.

Uma maneira talvez um pouco mais fácil é codificar o valor de dois dígitos decimais em 7 bits. (Tipo de decimal decimal com código binário).

Wouter van Ooijen
fonte
1
Um bom caso de uso para empacotar pares de dígitos em sete bits é ao transmitir arquivos ASCII que consistem principalmente em dados numéricos. Qualquer valor de bytes abaixo de 128 representa um único caractere ASCII, enquanto 128-227 representam dois dígitos ASCII. Fácil de codificar ou decodificar e não exige que os dados contenham principalmente dígitos (ou mesmo quaisquer dígitos), mas pode compactar cadeias de dígitos em 50% com muita facilidade.
Supercat
Ou aquele formato PDP11 que empacotou 3 caracteres alfanuméricos em 16 bits com um bit de reserva ... #
Brian
@BrianDrummond: Pode-se usar 16 bits para armazenar exatamente três caracteres de um conjunto de 40 ou até três de um conjunto de 39, mas não haveria um pouco de sobra. Normalmente "alfanumérico" implicaria um conjunto de pelo menos 36, mas a única maneira de haver um bit de reposição seria se o conjunto fosse limitado a 32. #
3089
Eu pensei que era 5 bits / char. O alfanumérico foi dividido em dois conjuntos de códigos, com um símbolo reservado para "alternar conjunto de códigos". Eu estava errado: en.wikipedia.org/wiki/DEC_Radix-50 Muito estranho , no entanto, só vi uma noite em que tive que decodificar um relatório que alguém me deu em um disquete de 8 ", em um sistema CP / M, com apenas uma luz fraca. lembrança de Z80 asm.
Brian Drummond
19

Você pode usar a codificação huffman para que os números tenham diferentes tamanhos de bits. se você estiver ciente de um dígito que ocorrerá com mais frequência do que outros, isso ajudará.

exemplo (com igual ocorrência):

0 - 1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

exemplo de recebimento final para obter o número 1:

O primeiro bit entra e deixa apenas 0 a 4 como opções.

o segundo bit entra e deixa apenas 0 a 2 como opções.

o terceiro bit entra e deixa 0 a 1 como opções.

o quarto bit entra e o número recebido é 1

markg
fonte
12

Talvez o que você esteja procurando seja a codificação aritmética, que pode codificar com eficiência uma sequência de símbolos, cada um dos quais em princípio pode exigir um número fracionário (não inteiro) de bits. (embora a mensagem total deva ser um número inteiro de bits)

Citando a Wikipedia :

A codificação aritmética difere de outras formas de codificação de entropia, como a codificação de Huffman, em vez de separar a entrada em símbolos componentes e substituir cada uma por um código, a codificação aritmética codifica a mensagem inteira em um único número, uma fração n onde (0,0 ≤ n < 1.0).

Hugh Allen
fonte
10

O novo IEEE P754 para aritmética de ponto flutuante agora define formatos decimais além de binários. Uma das codificações propõe agrupar dígitos digitais por 3 em 10 bits.

codificar de 0 a 999 usando 10bits = 1024 códigos possíveis é bastante eficiente, e os dígitos decimais geralmente são agrupados por três.

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

TEMLIB
fonte
Mesmo que os dígitos decimais sejam agrupados por três, a semântica correta de ponto flutuante decimal pode exigir que: (1) dimensionar uma mantissa por uma potência não-múltipla de três de dez, multiplique ou divida todos os constituintes por 10 ou 100; (2) alguns bits podem ser usados ​​para a parte superior ou inferior do número, dependendo de (expoente mod 3); (3) Se o expoente for armazenado na base 1000, o grupo inferior de três dígitos poderá às vezes ter que ser arredondado para o 10 mais próximo ou o 100 mais próximo, em vez da unidade mais próxima.
Supercat 22/11
Pessoalmente, acredito que tipos como BigDecimalpara muitos propósitos seriam mais eficientes se cada palavra contivesse 9 dígitos decimais em vez de 32 bits, mas os comportamentos de arredondamento não devem ser afetados pelo agrupamento de dígitos.
Supercat 22/11
4

Uma correspondência 1: 1 de binário (ou hexadecimal) é apenas um símbolo de codificação para bits. Então sim, como você mostrou, é possível. Outro local usado é (mas um pouco diferente) na treliça de codificação / decodificação em sistemas de comunicação em que as transições de bits são mantidas mais afastadas para facilitar a decodificação. E, é claro, a codificação 8b / 10b e 64b / 66b etc. etc. é uma idéia semelhante, na qual um espaço menor de símbolo é codificado em um espaço maior ligeiramente redundante para obter equilíbrio de DC, separação de símbolos e códigos de controle em sub-bandas.

espaço reservado
fonte
4

A representação dos dados depende da interpretação que você ou seu programa fornece.

Poderíamos enviar '27' também como caracteres ASCII, por exemplo, produzindo 0x3237 = 0b0011001000110111.

xn(x)log2n(x)

x1,x2n(x1),n(x2)log2n(x1)+log2n(x2)log2(n(x1)n(x2))

2log2(10)=24=8log2(1010)=7

Sempre depende da aplicação, mas normalmente quando você 'junta' variáveis ​​como você sugere, custará mais poder computacional se você quiser executar operações nessas variáveis. As operações de adição e subtração de variáveis ​​'unidas' são mais complexas do que o normal e podem exigir mais espaço no hardware ou causar atrasos maiores.



fonte
2

A maneira usual de empacotar valores é multiplicando cada valor pelo seu intervalo, para que você tenha um número grande que possa representar eficientemente em bits. Ao desembalar, você divide por faixa, o restante é o dígito e o resultado são os demais dígitos empacotados.

Se você tiver 5 valores no intervalo de 0 a 2, poderá representá-lo em 8 bits (você precisa de pelo menos 7,92 bits para representar os valores) em vez dos 10 bits usados ​​pela maneira ingênua de usar 2 bits para cada valor, fazendo (((n 1 * 3 + n 2 ) * 3 + n 3 ) * 3 + n 4 ) * 3 + n 5

Rinze Smits
fonte
Existe um nome para esse método de codificação?
Keegan Jay
1

Em teoria, se você estiver disposto a gastar espaço em circuito e energia no detector de alta impedância, poderá enviar três estados por um fio digital (1, 0 e Z alto). Isenção de responsabilidade: isso funciona muito bem no simulador. Não sei se o circuito tem alguns problemas que o tornam impraticável, como dizer que ele não pode realmente mudar tão rápido quanto um par de portas normal.

Meu termo normal para a transição de um sinal de Z alto para um sinal (onde o sinal geralmente é aterrado em silício) é um sinal de meio bit.

Joshua
fonte
1

Você deseja enviar um dígito decimal, precisando de 3 bits. Mas você terá que usar 4 bits, porque não pode enviar um terço de um bit.

Portanto, para descobrir o que realmente significa 3 bits, você precisa de dois (ou três) dígitos de 3 bits cada. Se você quiser enviar 2 (3) dígitos decimais entre 0 e 9, cada um precisando um pouco menos de 3⅓ bits, poderá fazê-lo usando 7 (10) bits. A prova construtiva é fácil:

7 (10) bits permitem codificar um número entre 0 e 128 (1023) - mas você precisará apenas de 00 (000) a 99 (999), que são todas possíveis codificações de dois (três) dígitos decimais. QED

Alexander
fonte
1

Acho que você está entendendo mal o que se entende no artigo wiki vinculado. O que se entende é que para uma cadeia de caracteres que é completamente numérico (sem espaços, vírgulas ou períodos), usando compressão ideal, pode representar cada caractere usando 3 1 / 3 pedaços , em média . Na verdade, é um pouco melhor que isso, pois a matemática diz que você pode obter o log 2 (10) = 3,3219 bits / caractere a longo prazo.

Da mesma forma, para o conjunto de alfanuméricos mais alguns símbolos (somente maiúsculas e 9 símbolos) ou 45 caracteres, é necessário registrar 2 (45) = 5,4918 bits / caractere, arredondado para 5,5 no artigo.

Os bits / caracteres reduzidos são alcançados usando a compactação, com uma codificação predefinida ou um esquema de compactação especificado pelo padrão QR (não sei ao certo qual é usado). Ele representa o número médio de bits que um caractere precisará para ser codificado; portanto, um caractere individual será codificado usando mais ou menos bits. Observe também que os valores listados acima são os valores ideais para seqüências infinitas e aleatórias. É possível obter taxas de compactação melhores ou piores para cadeias especialmente criadas.

MBraedley
fonte