| |
Kabuto
Account closed
Registered: Sep 2004
Posts: 58 |
Theoretically optimal 1541 GCR encoding scheme
I did some research on GCR encoding and ended up getting 7 data bits stored into 8 data bits each without violating GCR constraints (no 3 "0" bits in a row and no 10 "1" bits in a row).
This is barely above the theoretical limit.
And interestingly decoding is very fast using this scheme - but encoding is a more difficult.
This scheme uses arithmetic coding similar to what arithmetic packers use, just the other way round (storing constant-entropy 7-bit values in variable-entropy GCR bytes).
Here's a simple javascript implementation to show the idea:
http://kabuto.untergrund.net/files/c64stuff/gcrTest.js
EDIT: here's a sketched decoder loop, lacking drive sync stuff, though, that reads and decodes 8 raw bytes to 7 data bytes.
; initially A contains the arithmetical decoder state (up to 7 bits) and C might contain a carry to be added to it
loop:
LDX databyte
ADC ari_lo, X ; these table entries contain 7 bits each, too - erroneous entries contain $FF and thus might set C
ROL ; since we used bits 0..6 so far bit 7 contains the carry. Shift it into the C flag.
; (And shift the C flag, which is hopefully set upon errors due to adding $FF (TODO change offsets to ensure that's actually the case), into the now-unused bit 0 of tmp.)
STA tmp ; Don't store the first decoded 7 bits but use them for filling the next 7-bit values
LDA ari_hi, X ; Fetch upper 7 arith bits
; repeat the following block 7 times
LDX databyte
ADC ari_lo, X ; Same here - add 7 lower bits of table entry for GCR byte
ROL tmp ; Get a data bit and store error bit
; in the last iteration tmp contains error flags from each of the 8 steps so we could thus BNE to an error handler
ROL ; Combine the 7 decoded data bits with the additional bit, also push the carry from bit 7 to flag C
STA result+i, Y ; and store decoded byte
LDA ari_hi, X ; Get 7 upper bits of table entry
; end repeat
|
|
... 16 posts hidden. Click here to view all posts....
|
| |
Frantic
Registered: Mar 2003
Posts: 1627 |
I believe you can't edit any posts on CSDb except the ones which are last in a thread. |
| |
Kisiel
Account closed
Registered: Jul 2003
Posts: 56 |
Yes I can confirm, it works. I tested this idea near 1995 with my 1541-II drive (with burst). In 2013 there is no room for new hardware ideas ... Ultimate rules ;) |
| |
chatGPZ
Registered: Dec 2001
Posts: 11116 |
isnt this a pure software issue (which applies to 1541u just aswell) ? |
| |
Kisiel
Account closed
Registered: Jul 2003
Posts: 56 |
IMO 1541U have no GCR chip emulation it is only table of GCR value, stream of correct data for software with correct time (e.g.26cycles).
If Ultimate emulates GCR chip is possible to copy disk by nibbler (copy protected disk). I can not check it, I don't have 1541U.
My idea was to pack as much bytes as possible by changing GCR conversion table (as above by skipping "wrong" combination of bits), the Idea is correct, but for this days.... you can simply ask Gideon to change GCR table to none it will improve conversion time, loading time or "size" of track.
NO GCR ANY MORE !!! ;) |
| |
chatGPZ
Registered: Dec 2001
Posts: 11116 |
where did you get the impression this is somehow related to "GCR chip" (whatever that is) ? |
| |
Kisiel
Account closed
Registered: Jul 2003
Posts: 56 |
GCR conversion is inside chip to 1541 header. In other word 1541 Ultimate does not emulate "header". Sorry for short cut, I thought this topic is not "academic" implementation but the real one. |
| |
chatGPZ
Registered: Dec 2001
Posts: 11116 |
WAT
its about writing software dude. |
| |
Kisiel
Account closed
Registered: Jul 2003
Posts: 56 |
shame on me :) |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
I told myself I'd work out how this scheme works but I think it's time to admit defeat. For the record it seems to work in practice, though admittedly I haven't yet to managed to dump a G64 image.
Quoting KabutoThis scheme uses arithmetic coding similar to what arithmetic packers use, just the other way round (storing constant-entropy 7-bit values in variable-entropy GCR bytes). You say that as if the details ought to naturally follow from the realization of (ab-)using arithmetic coding in reverse but there seems to be some deep voodoo going on here. Hell, the 8-bit repacking code alone is remarkable as far as I'm concerned.
My first impulse would be to use a regular range coder. A standard implementation should certainly work but would be dog-slow. With care multiplication and dynamic renormalization may apparently be avoided [1] albeit at the cost of huge tables (they even carry overflows which would seem to defeat the purpose of the fixed-rate refinement.)
A second look at your code reveals that you're not actually doing traditional arithmetic coding at all but rather some backwards LIFO variant. Most everything on the subject seems to be hiding behind IEEE/ACM paywalls but [2] contains a quick recap on enumerative coding in this context.
Apparently enumerative coding is the fancy name for generating all valid "GCR" strings in order and interpreting the binary data to be encoded as an index into this set. The clever bit is that for simple run-length limited codes (e.g. at most two zeroes in a row in our case) the number of possible suffixes codes following a one-bit depends only on the bits remaining to be filled. Therefore all possible strings above a certain sequence may be counted simply by adding up a fixed weight per bit position for every zero encountered.
In our case the weight table is the tribonacci series for which the ratio between terms tends to ~1.83929. Rounding down to 7 bits/byte and applying some fixed-point the approximate implementation eventually reduces down to your code with an alternate table and appears to work well enough. Unfortunately there just isn't enough redundancy to avoid long strings of ones even with your brute-force encoder.
Of course your actually table looks nothing like this, for one thing it is ordered by the number of trailing zeroes/ones.
Any chance you might enlighten us as to how this thing actually works?
1. "A general fixed-rate arithmetic coding method for constrained channels" (Todd, Langdon & Martin)
2. "Effects of floating-point arithmetic in enumerative coding" (Immink & Jansen) |
| |
Krill
Registered: Apr 2002
Posts: 2845 |
Quoting doynaxAny chance you might enlighten us as to how this thing actually works?
But seriously, i'm interested to know, too. Honestly haven't spent much time and thought on the topic yet, but if even a coder of your calibre fails to wrap his head around it... *returns to thesis at hand* |
| Previous - 1 | 2 | 3 - Next |
