Existe-t-il un moyen d'utiliser des demi-bits?

19

Comme la plupart des gens ici le savent, en utilisant 4 bits, nous pouvons compter de 0 à 15 (0123456789ABCDEF en hexadécimal). Mais si nous devions seulement compter jusqu'à 9, nous utiliserions toujours 4 bits et les chiffres de A à F seraient gaspillés.

Cependant, la page QR-Code de Wikipedia indique que l'utilisation uniquement de chiffres numériques de 0 à 9 utilise 3⅓ bits par caractère, ce qui est correct d'un point de vue statistique. Et pourtant, un tiers de bit n'est pas un objet physique, et l'envoi d'un nombre de 0 à 9 utilise au moins 4 bits à ma connaissance.

Existe-t-il un moyen d'utiliser les combinaisons gaspillées pour envoyer efficacement un caractère avec des fractions de bits?

OK, permettez-moi de donner un exemple: les deux chiffres "27" doivent être envoyés. Avec des techniques de codage normales, les bits envoyés seraient 00100111. On pourrait alors imaginer un système qui remplacerait le chiffre «2» par le chiffre «E» ou «F», selon le bit suivant; dans ce cas, le bit suivant est 0, donc le «2» est remplacé par «E». La chaîne de bits résultante serait alors 1101 0 111. En revanche, si les chiffres "28" doivent être envoyés, le premier bit après le "2" est un 1, il est donc remplacé par le chiffre "F" à la place, donnant la chaîne 1111 1 000.

Dans les deux cas, une économie de 1 bit a été effectuée, car un quartet a été utilisé pour deux caractères différents. En d'autres termes, trois bits et demi sont utilisés sur chaque caractère.

Galahad78
la source
2
Pour une perspective différente sur le regroupement des valeurs dans un espace numérique plus petit, consultez les ordinateurs ternaires ( en.wikipedia.org/wiki/Ternary_computer ) Si c'est assez bon pour Knuth, c'est assez bon pour moi!
RLH
3
Mieux vaut encore reconnaître que vous pouvez calculer (10 * first_digit) + second_digitet encoder cela en 7 bits, représentant 0 ... 99, avec les codes 100-127 laissés pour d'autres choses. Et il y a encore plus d'économies avec 3 chiffres compressés en 10 bits.
Hot Licks
Pour envoyer les 100 valeurs différentes séparément, le mieux que vous puissiez obtenir est de les regrouper en 7 bits. Si vous avez plus de chiffres, l'emballage sera plus efficace. Si vous avez moins de 64 valeurs à envoyer, vous pouvez l'envoyer en utilisant seulement 6 bits
phuclv

Réponses:

22

Vous ne pouvez pas envoyer un demi-bit, mais vous pouvez effectivement emballer deux demi-bits en un seul bit avant la transmission ou le stockage.

Vous donnez vous-même un exemple, vous avez donc effectivement répondu à votre propre question par un OUI.

Un moyen peut-être un peu plus simple consiste à coder simplement la valeur de deux chiffres décimaux en 7 bits. (Sorte de codage binaire à deux décimales).

Wouter van Ooijen
la source
1
Un bon cas d'utilisation pour regrouper des paires de chiffres en sept bits est lors de la transmission de fichiers ASCII qui se composent principalement de données numériques. Toute valeur d'octet inférieure à 128 représente un seul caractère ASCII, tandis que 128-227 représentent deux chiffres ASCII. Facile à coder ou à décoder, et ne nécessite pas que les données contiennent principalement des chiffres (ou même des chiffres), mais peut compresser les chaînes de chiffres de 50% très facilement.
supercat
Ou ce format PDP11 qui comprenait 3 caractères alphanumériques en 16 bits avec un bit de rechange ...
Brian Drummond
@BrianDrummond: On pourrait utiliser 16 bits pour stocker exactement trois caractères d'un ensemble de 40, ou jusqu'à trois d'un ensemble de 39, mais il n'y aurait pas de bit de rechange. Normalement, "alphanumérique" impliquerait un ensemble d'au moins 36, mais la seule façon qu'il y aurait un bit de rechange serait si l'ensemble était limité à 32.
supercat
Je pensais que c'était 5 bits / caractère. Alphanumérique a été divisé en deux jeux de codes, avec un symbole réservé pour "jeu de codes de commutation". J'avais tort: en.wikipedia.org/wiki/DEC_Radix-50 Assez bizarre cependant, je ne l'ai vu qu'une nuit quand j'ai dû décoder un rapport que quelqu'un m'a donné sur une disquette de 8 ", sur un système CP / M, avec seulement une dim souvenir de Z80 asm.
Brian Drummond
19

Vous pouvez utiliser le codage Huffman pour que les nombres soient de longueur variable. si vous connaissez un chiffre qui se produira plus souvent que d'autres, cela vous aidera.

exemple (avec occurrence égale):

0 - 1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

exemple de réception pour obtenir le numéro 1:

Le premier bit entre et ne laisse que 0 à 4 en option.

le deuxième bit entre et ne laisse que 0 à 2 en option.

le troisième bit entre et laisse 0 à 1 en option.

le quatrième bit entre et le nombre entrant est 1

markg
la source
12

Peut-être que vous recherchez un codage arithmétique, qui peut encoder efficacement une chaîne de symboles, dont chacun peut en principe nécessiter un nombre fractionnaire (non entier) de bits. (bien que le message total doive être un nombre entier de bits)

Citant Wikipédia :

Le codage arithmétique diffère des autres formes de codage entropique comme le codage Huffman en ce que, plutôt que de séparer l'entrée en symboles de composants et de les remplacer par un code, le codage arithmétique code le message entier en un seul numéro, une fraction n où (0,0 ≤ n < 1.0).

Hugh Allen
la source
10

Le nouvel IEEE P754 pour l'arithmétique à virgule flottante définit désormais les formats décimaux en plus du binaire. L'un des encodages propose de regrouper les chiffres numériques de 3 en 10 bits.

encoder de 0 à 999 en utilisant 10 bits = 1024 codes possibles est assez efficace, et les chiffres décimaux sont souvent groupés par trois de toute façon.

Décimal emballé de façon dense : http://en.wikipedia.org/wiki/Densely_packed_decimal

TEMLIB
la source
Même si les chiffres décimaux sont regroupés par trois, une sémantique décimale à virgule flottante correcte peut nécessiter que (1) la mise à l'échelle d'une mantisse par une puissance non multiple de trois implique de multiplier ou de diviser tous les constituants par 10 ou 100; (2) certains bits peuvent être utilisés pour la partie supérieure ou inférieure du nombre, selon (exposant mod 3); (3) Si l'exposant est stocké en base-1000, le groupe inférieur de trois chiffres peut parfois devoir être arrondi au 10 ou au 100 le plus proche, plutôt qu'à l'unité la plus proche.
supercat
Personnellement, je crois que les types comme BigDecimalseraient à plusieurs fins plus efficaces si chaque mot contenait 9 chiffres décimaux plutôt que 32 bits, mais les comportements d'arrondi ne devraient pas être affectés par le regroupement des chiffres.
supercat
4

Une correspondance 1: 1 de binaire (ou hexadécimal) n'est qu'un codage de symbole pour les bits. Alors oui, comme vous l'avez montré, c'est possible. Un autre endroit utilisé (mais légèrement différent) est le codage / décodage en treillis dans les systèmes de communication dans lesquels les transitions de bits sont maintenues plus éloignées pour faciliter le décodage. Et bien sûr, l'encodage 8b / 10b et 64b / 66b etc.

espace réservé
la source
4

La représentation des données dépend de l'interprétation que vous ou votre programme lui donne.

Nous pourrions envoyer «27» également sous forme de caractères ASCII, par exemple, en donnant 0x3237 = 0b0011001000110111.

xn(x)log2n(x)

x1,x2n(x1),n(x2)log2n(x1)+log2n(x2)Journal2(n(X1)n(X2)) bits.

2Journal2(dix)=24=8Journal2(dixdix)=sept bits.

Cela dépend toujours de l'application, mais normalement lorsque vous «joignez» des variables comme vous le suggérez, cela coûtera plus de puissance de calcul si vous souhaitez effectuer des opérations sur ces variables. L'ajout et la soustraction d'opérations sur des variables «jointes» sont plus complexes que d'habitude et peuvent nécessiter plus d'espace dans le matériel, ou entraîner des délais plus longs.



la source
2

La façon habituelle de compresser les valeurs consiste à multiplier chaque valeur par sa plage, de sorte que vous vous retrouvez avec un grand nombre que vous pouvez représenter efficacement en bits. Lors du déballage, vous divisez par plage, le reste est le chiffre et le résultat est le reste des chiffres compressés.

Si vous avez 5 valeurs dans la plage de 0 à 2, vous pouvez représenter cela sur 8 bits (vous avez besoin d'au moins 7,92 bits pour représenter les valeurs) au lieu des 10 bits utilisés par la manière naïve d'utiliser 2 bits pour chaque valeur, en faisant (((n 1 * 3 + n 2 ) * 3 + n 3 ) * 3 + n 4 ) * 3 + n 5

Rinze Smits
la source
Y a-t-il un nom pour cette méthode d'encodage?
Keegan Jay
1

En théorie, si vous êtes prêt à dépenser de l'espace de circuit et de l'énergie pour le détecteur à haute impédance, vous pouvez envoyer 3 états sur un fil numérique (1, 0 et Z élevé). Avertissement: cela fonctionne très bien dans le simulateur. Je ne sais pas si le circuit a des problèmes qui le rendent impraticable, comme dire qu'il ne peut pas vraiment commuter aussi vite qu'une paire normale de portes.

Mon terme normal pour une transition de signal d'un Z élevé au signal (où le signal est généralement mis à la terre dans du silicium) est un signal demi-bit.

Joshua
la source
1

Vous souhaitez envoyer un chiffre décimal, nécessitant 3⅓ bits. Mais vous devrez utiliser 4 bits, car vous ne pouvez pas envoyer un tiers de bit.

Donc, pour savoir ce que signifie réellement 3⅓ bits, vous avez besoin de deux (ou trois) chiffres de 3⅓ bits chacun. Si vous souhaitez envoyer 2 (3) chiffres décimaux entre 0 et 9, chacun nécessitant un peu moins de 3⅓ bits, vous pouvez le faire en utilisant 7 (10) bits. La preuve constructive est facile:

7 (10) bits vous permettent d'encoder un nombre compris entre 0 et 128 (1023) - mais vous n'aurez besoin que de 00 (000) à 99 (999), qui sont tous des encodages possibles de deux (trois) chiffres décimaux. QED

Alexandre
la source
1

Je pense que vous ne comprenez pas bien ce que signifie l'article wiki lié. Qu'est - ce que l' on entend est que pour une chaîne de caractères qui est complètement numérique (sans espaces, virgules, ou périodes), en utilisant la compression idéale, vous pouvez représenter chaque caractère en utilisant 3 1 / 3 des bits en moyenne . En fait, c'est un peu mieux que cela, car les calculs disent que vous pouvez obtenir le journal 2 (10) = 3,3219 bits / caractère à long terme.

De même, pour l'ensemble alphanumérique plus certains symboles (majuscules uniquement et 9 symboles) ou 45 caractères, vous avez besoin du journal 2 (45) = 5,4918 bits / caractère, qui est arrondi à 5,5 dans l'article.

Les bits / caractères réduits sont obtenus en utilisant la compression, soit avec un encodage prédéfini, soit avec un schéma de compression spécifié par la norme QR (je ne sais pas lequel est utilisé). Il représente le nombre moyen de bits dont un caractère aura besoin pour être codé, donc un caractère individuel sera codé en utilisant plus ou moins de bits. Sachez également que les valeurs répertoriées ci-dessus sont les valeurs idéales pour des chaînes infinies et aléatoires. Il est possible d'obtenir des taux de compression meilleurs ou pires pour les cordes spécialement conçues.

MBraedley
la source