Gibt es eine Möglichkeit, Halbbits zu verwenden?

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.

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).

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

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).

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

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.

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.

$x$$n(x)$${\lceil\log_2{n(x)}\rceil}$

$x_1,x_2$$n(x_1),n(x_2)$$\lceil\log_2n(x_1)\rceil+\lceil\log_2n(x_2)\rceil$$\left\lceil\log_2\left(n(x_1)\cdot n(x_2)\right)\right\rceil$ Bits.

$2\cdot\lceil\log_2(10)\rceil=2\cdot4=8$$\lceil\log_2(10\cdot10)\rceil=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.

$\lceil\dots\rceil$ist die Notation zum Aufrunden .

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 ₁ · 3 + n ₂ ) · 3 + n ₃ ) · 3 + n ₄ ) · 3 + n ₅

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.

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

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 ¹ / ₃ Bits im Durchschnitt . Eigentlich ist es ein bisschen besser, da die Mathematik besagt, dass man auf lange Sicht log ₂ (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 ₂ (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.