Hi, geg. ist ein alternierendes Bitsignal, die zeitl. Differenz zwischen zwei Bitwechseln gehen von 1 Zeiteinheit bit ca. 200k Zeiteinheiten (d.h. binär von 1 Bit bis ca. 18 Bits). Aufgabe ist jetzt, jeden Wert mit möglichst wenig Bits zu erfassen. Welche Binärformate eignen sich dafür?
Was mir so auf die Schnelle eingefallen ist: Pre-Info: 0 => 1 Bit 10 => 2 Bits 110 => 4 Bits 1110 => 8 Bits 11110 => 18 Bits Length-Info: je nach Anz. Bits: Länge binär codiert. Damit hat man dan iE ein O(log(n))-Codierungsaufwand. (UND: lässt sich leicht in Software/HDL beschreiben)
Sigi schrieb: > Aufgabe ist jetzt, jeden Wert mit möglichst wenig > Bits zu erfassen. Welche Binärformate eignen sich > dafür? Gegenfrage: Wie sind die Bits verteilt, welche Hardware hast Du zur Verfügung? Bei ausreichender Hardware hätte ich einfach gzip genommen.
1 bis 200.000 kann man EXAKT nur mit 18 Bit darstellen. Wenn es nur um Größenordnungen geht, kann man zur Basis 2 logarithmieren: Einfach nur die Position ((0...17) +1) des höchsten gesetzten Binärbits übermitteln. (Keines gesetzt: NULL) Braucht 5 Bit. Wenn der Wert sich nur wenig ändert, kann man die Differenz zum vorherigen Wert übertragen. (Z.B. 8 Bit für 0...255.) Gibt aber Fehler, wenn sich doch mal was zu schnell ändert.
Jim M. schrieb: > Gegenfrage: Wie sind die Bits verteilt, welche Hardware hast Du zur > Verfügung? Bei ausreichender Hardware hätte ich einfach gzip genommen. Bei den Bits handelt es sich um GCR-codierte Bits auf einer Uraltfloppy. IdR sind die Abstände bei 1-10, selten über 10. 200k entspricht einer leeren Spur auf der Floppy (kommt selten vor!). GZip scheidet aus, soll ja später ein sehr einfacher Emulator bzw. Simulator auf FPGA-Basis werden.
Jakob schrieb: > ... > Gibt aber Fehler, wenn sich doch mal was zu schnell ändert. Ja, und genau das ist bei der nachfolgenden Analyse (bzw. meiner Simulation) das Problem. In der nachfongenden Simulation wird ein Timer-IC (9602 bzw. LS123) angesteuert, der wiederum weitere ICs (Shift-Register) ansteuert etc. Da muss es möglichst genau sein.
Ja nun? 0...10 = OK, oder auch 0...127 = OK? Dann wird >= 128 eben Sonderfall... Kostet 8 Bit. Sonst: 18 Bit. Es sei denn, du codierst nach dem relativ SELTEN (!?) auftretenden Wert > 127 eine ESCAPE-Folge mit 4 Byte: 1. Byte = 255, dann 3 Byte mit dem gemessenen Wert zwischen 128 und 200.000. Das könnte vielleicht was bringen...
Jakob schrieb: > Ja nun? 0...10 = OK, oder auch 0...127 = OK? > Dann wird >= 128 eben Sonderfall... Eine genaue Statistik habe ich zZ nicht, gehe aber davon aus, dass 1..10 der Standardfall ist und grössere Werte selten vorkommen und von daher auch mit mehr Bits kodiert werden können (so wie s.B. bei Entropiecodierung).
Ließe sich noch mehr optimieren, wenn Längen > 127 wirklich selten sind: Byte <= 127: Wert zwischen 0 und 127 Sonst: 1. Byte = 128 + n n = 0: Wert von 128...255 folgt (1 Byte) n = 1: Wert von 256...65.535 folgt (2 Byte) n = 2: Wert von 65.535...16.777.215 folgt (3 Byte)
Wenns byteweise sein soll: Man kann auch das oberste Bit immer dafür nehmen, das noch ein weiteres Byte folgt, also immer 7 Bit pro Byte + 1 Bit. Braucht 1 Byte für <= 127, 2 für <= 16384 und 3 Byte für <= 2097152. Mehr Bytes sind möglich für größere Zahlen. (Hat man auch negative Zahlen, bietet es sich an, ein Signbit im ersten Byte einzubauen. Dann passen da nur noch <64 rein, aber dafür lassen sich negative Zahlen kürzer speichern, als wenn man ein Zweierkomplement nehmen würde.) Wenn es eh auf 18 Bit beschränkt ist, und die meisten Werte <64, dann kann man nur 6 Bit für die Zahl und dafür ein Bit als Paritätsbit nutzen, das macht es dann etwas robuster. UTF8 ist auch sowas..
bastel_ schrieb: > Wenns byteweise sein soll: Danke für Deine Mühe, bei mir muss es aber idR viel kürzer sein, schon ein Bit macht sehr viel Speicherplatz aus (und der ist bei mir verdammt knapp:(). Meine bisheriger Ansatz liefert für die Std.fälle nur 2-6 Bits.
Sigi schrieb: > Bei den Bits handelt es sich um GCR-codierte Bits > auf einer Uraltfloppy. IdR sind die Abstände bei > 1-10, selten über 10. 200k entspricht einer leeren > Spur auf der Floppy (kommt selten vor!). Nicht realistisch. Leere Spuren sind selten leer, und FDC Schreib/Leseverstärker sind wechselspannungsgekoppelt. 200000 kommt nicht vor, es sind immer Wechsel von 1 bis 10 Zeiteinheiten, auch leere formatierte Srktoren, und wen du wegen Kopierschutzverfahren auch leerräume codieren willst die länger sind, nutze für den Sondergall einen Escape (Sondercode + folgende Sonderdaten) GCR vom Apple ist sogar noch einfacher, es erlaubt einen Flankenwechsel nur im Abstand 1, 2 oder 3, man kann das in 2 bit codieren und nimmt 0 als Escape, wenn man nicht sowieso die resulierenden 6 bit speichert.
MaWin schrieb: > Nicht realistisch. 200K bezieht sich auch nur auf meine Simulation, auf realer HW ist das total unwahrscheinlich. Irgendwie muss ich ja "total leere" Disketten handeln. MaWin schrieb: > GCR vom Apple ist sogar noch einfacher, es erlaubt einen Flankenwechsel > nur im Abstand 1, 2 oder 3 Bei mir ist es eine Vic1541, da verhällt es sich ähnlich. Allerdings kommt noch hinzu, dass die Lese/Schreibgeschwindigkeit per CPU in 4 Schritten eingestellt werden kann, d.h. es sind extrem "dreckige" Tricks möglich, die ich alle erfassen will (ansonsten müsste ich ja nur einen Bitvektor im Speicher ablegen). Aber schön zu sehen, dass es noch viele gibt, die sich mit alter HW noch bestens auskennen.
Mal ganz davon abgesehen, daß das mit 200K Zyklen bei GCR nicht vorkommt, für die platzsparende Speicherung der Zahlen kannst du ein längencodiertes Format verwenden. MySQL verwendet so etwas auf Protokoll-Ebene, es heißt da length-encoded integer https://dev.mysql.com/doc/dev/mysql-server/latest/page_protocol_basic_dt_integers.html Die Effizienz des Codierungsschemas beruht darauf, daß kleine Zahlen tendenziell häufiger vorkommen als lange. Diese werden direkt gespeichert. Zahlen die mehr Bits brauchen, werden als mehrere Worte gespeichert und das erste Wort nimmt einen speziellen Wert (ein ESCAPE-Zeichen) vom Ende des ein-Wort Wertebereichs an. Solche Codes kann man nach Bedarf für beliebige Basis-Wortlängen bilden. Mal ein Beispiel. Die Wortlänge sei 6 Bit. Damit kannst du Werte von 0..63 direkt speichern. Zwei Worte ergeben 12 Bit = 0..4095, 3 Worte dann 0 .. 262144. Für dich reichen also maximal 3 Worte und du brauchst zwei ESCAPE Werte, die du vom Ende des 0..63 Wertebereichs nimmst. Also:
1 | Zahl Code |
2 | ------------------------------------------------------- |
3 | 0 .. 61 direkt in 6 Bits |
4 | 62 .. 4095 62 + Wert in 2x 6 Bit (18 Bits gesamt) |
5 | 4096 .. 200000 63 + Wert in 3x 6 Bit (24 Bits gesamt) |
Das kann man nach Belieben verkomplizieren. Z.B. könnte man die höchstwertigen Bits im ersten Wort für die Codierung der Länge verwenden, so wie das z.B. UTF-8 tut. Beispielsweise die ersten beiden Bits:
1 | 00 -> Wert steht direkt in den 4 niederwertigen Bits |
2 | 01 -> Wert ist 10 Bit lang, die 4 niederwertigen + die nächsten 6 |
3 | 10 -> Wert ist 16 Bit lang, die 4 niederwertigen + die nächsten 12 |
4 | 11 -> Wert ist 22 Bit lang, die 4 niederwertigen + die nächsten 18 |
Der Vorteil einer solchen Codierung ist, daß sie weniger Overhead für mehr-Wort Kombinationen ergibt (2 Bits statt 6). Dafür ist der direkt speicherbare Wertebereich kleiner.
Gestern fiel mir noch ein, dass man die gebrauchten Datenbits
auch nur in 4-Bit-Schritten erhöhen kann.
Wenn 0...10 der hauptsächlich auftretende Wert ist, etwa so:
Wert belegte Halb-Bytes (4-Bit-Gruppen)
----------------------------------------------------------
0 0x0 0,5 Byte
1 0x1 0,5 Byte
: : 0,5 Byte
9 0x9 0,5 Byte
10 0xA 0,5 Byte
11...15 0xB? 1,0 Byte
16...255 0xC?? 1,5 Byte
256...4.095 0xD??? 2,0 Byte
4.095...65.535 0xE???? 2,5 Byte
65.536 .. 1.048.575 oxF????? 3,0 Byte
Jedes '?' entspricht 4 Bits zur Speicherung des Werts
der entprechenden Größe.
Ist (für einen ASM-Liebhaber) jedenfalls sehr einfach zu
kodieren und dekodieren - und sollte ein guter Kompromiss
zwischen Programmieraufwand und Platzbedarf sein, wenn Werte
> 10 recht selten auftreten.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.