RLE-Codierung für Samplingkompression

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)

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)

Jakob schrieb:
> 1. Byte = 128 + n
Sehr gute Idee: Offset abziehen. Danke!

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.

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.