Gibt es eine Möglichkeit, Halbbits zu verwenden?

19

Wie die meisten Leute hier wissen, können wir mit 4 Bits von 0 bis 15 zählen (0123456789ABCDEF in hexadezimaler Schreibweise). Wenn wir jedoch nur bis 9 zählen würden, würden wir immer noch 4 Bits verwenden, und die Ziffern von A bis F würden verschwendet.

Auf der QR-Code-Seite von Wikipedia heißt es jedoch, dass bei der Verwendung von Ziffern von 0 bis 9 3⅓ Bits pro Zeichen verwendet werden, was statistisch korrekt ist. Und dennoch ist ein Drittel eines Bits kein physisches Objekt, und das Senden einer Zahl von 0 bis 9 verwendet meines Wissens mindestens 4 Bits.

Gibt es eine Möglichkeit, die verschwendeten Kombinationen zu verwenden, um ein Zeichen mit Brüchen von Bits effektiv zu senden?

OK, lassen Sie mich ein Beispiel geben: Die zwei Ziffern "27" müssen gesendet werden. Bei normalen Codierungstechniken wären die gesendeten Bits 00100111. Wir könnten uns dann ein System vorstellen, das die Ziffer '2' durch die Ziffer 'E' oder 'F' ersetzt, abhängig vom nächsten Bit. In diesem Fall ist das nächste Bit 0, daher wird die '2' durch 'E' ersetzt. Die resultierende Bitfolge wäre dann 1101 0 111. Wenn andererseits die Ziffern "28" gesendet werden müssen, ist das erste Bit nach der "2" eine 1, so dass es stattdessen durch die Ziffer "F" ersetzt wird. Nachgeben der Zeichenfolge 1111 1 000.

In beiden Fällen wurde eine Einsparung von 1 Bit bewirkt, da ein Halbbyte für zwei verschiedene Zeichen verwendet wurde. Mit anderen Worten, dreieinhalb Bits werden für jedes Zeichen verwendet.

Galahad78
quelle
2
Weitere Informationen zum Packen von Werten in einen kleineren Ziffernbereich finden Sie unter Ternäre Computer ( de.wikipedia.org/wiki/Ternäre_Computer ). Wenn es für Knuth gut genug ist, ist es für mich gut genug!
RLH
3
Besser noch zu erkennen, dass Sie dies berechnen (10 * first_digit) + second_digitund in 7 Bits codieren können, die 0 ... 99 darstellen, wobei die Codes 100-127 für andere Dinge übrig bleiben. Und es gibt noch mehr Einsparungen mit 3 Stellen, die auf 10 Bits komprimiert sind.
Hot Licks
Um alle 100 verschiedenen Werte separat zu senden, können Sie am besten in 7 Bits packen. Wenn Sie mehr Ziffern haben, ist das Packen effizienter. Wenn Sie weniger als 64 Werte zu senden haben, können Sie diese mit nur 6 Bits senden
phuclv

Antworten:

22

Sie können kein halbes Bit senden, aber Sie können effektiv zwei halbe Bits in ein Bit packen, bevor Sie übertragen oder speichern.

Sie geben selbst ein Beispiel und haben Ihre eigene Frage effektiv mit JA beantwortet.

Eine vielleicht etwas einfachere Möglichkeit besteht darin, den Wert von zwei Dezimalstellen in 7 Bits zu codieren. (Art der binär codierten Dual-Dezimalzahl).

Wouter van Ooijen
quelle
1
Ein nützlicher Anwendungsfall für das Packen von Ziffernpaaren in sieben Bits ist die Übertragung von ASCII-Dateien, die überwiegend aus numerischen Daten bestehen. Jeder Byte-Wert unter 128 steht für ein einzelnes ASCII-Zeichen, während 128-227 zwei ASCII-Ziffern darstellen. Einfach zu codieren oder zu decodieren und erfordert nicht, dass die Daten hauptsächlich Ziffern (oder sogar Ziffern) enthalten, sondern kann Ziffernfolgen sehr einfach um 50% komprimieren.
Supercat
Oder das PDP11-Format, das 3 alphanumerische Zeichen in 16 Bit mit einem Bit Reserve packte ...
Brian Drummond
@BrianDrummond: Man könnte 16 Bits verwenden, um genau drei Zeichen aus einem Satz von 40 oder bis zu drei aus einem Satz von 39 zu speichern, aber es würde kein Ersatzbit geben. Normalerweise würde "alphanumerisch" eine Menge von mindestens 36 implizieren, aber die einzige Möglichkeit, ein
Ersatzbit zu erhalten,
Ich dachte, es wären 5 Bits / Zeichen. Alphanumerisch wurde auf zwei Codesätze aufgeteilt, wobei ein Symbol für "Schaltercodesatz" reserviert war. Ich habe mich geirrt: en.wikipedia.org/wiki/DEC_Radix-50 Ist zwar seltsam , aber ich habe es nur eines Nachts gesehen, als ich einen Bericht entschlüsseln musste, den mir jemand auf einer 8-Zoll-Diskette auf einem CP / M-System mit nur schwachem Inhalt gegeben hat Erinnerung an Z80 Asm.
Brian Drummond
19

Sie können die Huffman-Codierung verwenden, damit die Zahlen eine unterschiedliche Bitlänge haben. Wenn Sie wissen, dass eine Ziffer häufiger vorkommt als andere, hilft dies.

Beispiel (bei gleichem Vorkommen):

0 - 1111

1 - 1110

2 - 110

3 - 101

4 - 100

5 - 011

6 - 010

7 - 001

8 - 000

Beispiel für das Empfangen der Nummer 1:

Das erste Bit kommt rein und lässt als Option nur 0 bis 4 übrig.

Das zweite Bit kommt rein und lässt nur 0 bis 2 als Optionen übrig.

Das dritte Bit kommt rein und lässt als Option 0 zu 1.

Das vierte Bit kommt herein und die eingehende Nummer ist 1

markg
quelle
12

Vielleicht suchen Sie nach einer arithmetischen Codierung, die eine Zeichenfolge effizient codieren kann, für die im Prinzip jeweils eine gebrochene (nicht ganzzahlige) Anzahl von Bits erforderlich sein kann. (obwohl die Gesamtnachricht eine ganze Anzahl von Bits sein muss)

Wikipedia zitieren :

Die arithmetische Codierung unterscheidet sich von anderen Formen der Entropiecodierung wie der Huffman-Codierung darin, dass die arithmetische Codierung nicht die Eingabe in Komponentensymbole trennt und jedes durch einen Code ersetzt, sondern die gesamte Nachricht in eine einzelne Zahl, einen Bruchteil n mit (0.0 ≤ n < 1,0).

Hugh Allen
quelle
10

Das neue IEEE P754 für Gleitkomma-Arithmetik definiert jetzt zusätzlich zu Binär auch Dezimalformate. Eine der Kodierungen schlägt vor, digitale Ziffern durch 3 in 10 Bits zu gruppieren.

Die Codierung von 0 bis 999 mit 10 Bit = 1024 möglichen Codes ist sehr effizient, und Dezimalstellen werden häufig ohnehin zu drei gruppiert.

Dicht gepackte Dezimalzahl : http://en.wikipedia.org/wiki/Densely_packed_decimal

TEMLIB
quelle
Selbst wenn Dezimalstellen durch drei gruppiert werden, kann eine korrekte Dezimal-Gleitkommasemantik erfordern, dass entweder (1) eine Mantisse durch eine Zehnerpotenz skaliert wird, indem alle Bestandteile multipliziert oder durch 10 oder 100 dividiert werden; (2) einige Bits können abhängig von (Exponent mod 3) entweder für den oberen oder den unteren Teil der Zahl verwendet werden; (3) Wenn der Exponent mit der Basis 1000 gespeichert ist, muss die unterste Gruppe von drei Stellen manchmal auf die nächsten 10 oder die nächsten 100 gerundet werden, anstatt auf die nächste Einheit.
Supercat
Ich persönlich glaube, dass Typen wie BigDecimalfür viele Zwecke effizienter wären, wenn jedes Wort 9 Dezimalstellen anstatt 32 Bit enthalten würde, aber das Rundungsverhalten sollte nicht durch die Zifferngruppierung beeinflusst werden.
Supercat
4

Eine 1: 1-Entsprechung von binär (oder hexadezimal) ist nur eine Symbolcodierung für Bits. Also ja, wie Sie gezeigt haben, ist es möglich. Ein anderer Ort, an dem dies verwendet wird, ist (jedoch geringfügig anders) die Trellis-Codierung / -Decodierung in Kommunikationssystemen, in denen Bitübergänge weiter voneinander entfernt gehalten werden, um die Decodierung zu erleichtern. Und natürlich ist das Codieren von 8b / 10b und 64b / 66b usw. usw. eine ähnliche Idee, bei der ein kleinerer Symbolraum in einem etwas redundanten größeren Raum codiert wird, um Gleichstromausgleich, Symboltrennung und Steuercodes in Teilbändern zu erhalten.

Platzhalter
quelle
4

Die Darstellung der Daten hängt von der Interpretation ab, die Sie oder Ihr Programm geben.

Wir könnten '27' auch als ASCII-Zeichen senden, um zum Beispiel zu ergeben 0x3237 = 0b0011001000110111.

xn(x)Log2n(x)

x1,x2n(x1),n(x2)Log2n(x1)+Log2n(x2)Log2(n(x1)n(x2)) Bits.

2Log2(10)=24=8Log2(1010)=7 Bits.

Dies hängt immer von der Anwendung ab. Wenn Sie jedoch Variablen wie vorgeschlagen verbinden, wird dies mehr Rechenleistung kosten, wenn Sie Operationen mit diesen Variablen ausführen möchten. Das Hinzufügen und Subtrahieren von Operationen für 'verknüpfte' Variablen ist komplexer als normalerweise und erfordert möglicherweise mehr Platz in der Hardware oder führt zu längeren Verzögerungen.


ist die Notation zum Aufrunden .


quelle
2

Die übliche Art, Werte zu packen, besteht darin, jeden Wert mit seinem Bereich zu multiplizieren, sodass Sie eine große Zahl erhalten, die Sie effizient in Bits darstellen können. Beim Auspacken ist der Rest die Ziffer, und das Ergebnis sind die verbleibenden gepackten Ziffern.

Wenn Sie 5 Werte im Bereich von 0 bis 2 haben, können Sie dies in 8 Bits darstellen (Sie benötigen mindestens 7,92 Bits, um die Werte darzustellen) anstatt der 10 Bits, die von der naiven Art der Verwendung von 2 Bits für jeden Wert verwendet werden. durch Ausführen von (((n 1 · 3 + n 2 ) · 3 + n 3 ) · 3 + n 4 ) · 3 + n 5

Smits waschen
quelle
Gibt es einen Namen für diese Codierungsmethode?
Keegan Jay
1

Theoretisch können Sie, wenn Sie Platz und Strom für den hochohmigen Detektor aufwenden möchten, drei Zustände über eine digitale Leitung senden (1, 0 und High-Z). Haftungsausschluss: Dies funktioniert hervorragend im Simulator. Ich weiß nicht, ob die Schaltung Probleme hat, die sie unpraktisch machen, zum Beispiel, dass sie nicht so schnell schalten kann wie ein normales Paar Tore.

Meine normale Bezeichnung für einen Signalübergang von High-Z zu Signal (wobei das Signal normalerweise in Silizium geerdet ist) ist ein Halb-Bit-Signal.

Joshua
quelle
1

Sie möchten eine Dezimalstelle senden, die 3⅓ Bits benötigt. Sie müssen jedoch 4 Bits verwenden, da Sie kein Drittel eines Bits senden können.

Um herauszufinden, was 3⅓ Bits wirklich bedeuten, benötigen Sie zwei (oder drei) Ziffern mit jeweils 3⅓ Bits. Wenn Sie 2 (3) Dezimalstellen zwischen 0 und 9 senden möchten, die jeweils etwas weniger als 3⅓ Bits benötigen, können Sie dies mit 7 (10) Bits tun. Konstruktiver Beweis ist einfach:

Mit 7 (10) Bits können Sie eine Zahl zwischen 0 und 128 (1023) codieren. Sie benötigen jedoch nur 00 (000) bis 99 (999), alles mögliche Codierungen mit zwei (drei) Dezimalstellen. QED

Alexander
quelle
1

Ich denke, Sie verstehen falsch, was im verlinkten Wiki-Artikel gemeint ist. Was ist gemeint , dass für eine Reihe von Zeichen , die vollständig numerisch ist (ohne Leerzeichen, Kommas oder Punkte), ideal Kompression verwenden, können Sie jedes Zeichen mit 3 darstellen können 1 / 3 Bits im Durchschnitt . Eigentlich ist es ein bisschen besser, da die Mathematik besagt, dass man auf lange Sicht log 2 (10) = 3.3219 Bits / Zeichen bekommen kann .

In ähnlicher Weise benötigen Sie für den Satz alphanumerischer Zeichen plus einige Symbole (nur Großbuchstaben und 9 Symbole) oder 45 Zeichen log 2 (45) = 5.4918 Bits / Zeichen, was im Artikel auf 5,5 aufgerundet wird.

Das reduzierte Bit / Zeichen wird durch Komprimierung erreicht, entweder mit einer voreingestellten Codierung oder einem durch den QR-Standard festgelegten Komprimierungsschema (ich bin nicht sicher, welches verwendet wird). Es stellt die durchschnittliche Anzahl von Bits dar, die ein Zeichen benötigt, um codiert zu werden, sodass ein einzelnes Zeichen mit mehr oder weniger Bits codiert wird. Beachten Sie auch, dass die oben aufgeführten Werte die idealen Werte für unendliche, zufällige Zeichenfolgen sind. Es ist möglich, Komprimierungsverhältnisse zu erhalten, die für speziell gestaltete Saiten besser oder schlechter sind.

MBraedley
quelle