| |
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
|
|
| |
Krill
Registered: Apr 2002 Posts: 2980 |
Impressive.
Is that initial decoder state (let me call it seed) required for each encoded 8-byte chunk, or for a whole block?
If the former, then the actual ratio is 7/9, which is slightly worse than GCR's 4/5. If the latter, then i guess those additional 7 bits to determine a whole block can very well be optimized away.
What is the actual theoretical limit, as in entropy of a bitstream under the 3-zeros/10-ones condition? I had thought about computing it but never found a computationally feasible method, the naive approach being to count all valid bit combinations in a chunk of N bytes and to log2 that count. |
| |
Oswald
Registered: Apr 2002 Posts: 5094 |
I've no idea how that works, but impressively short indeed. trick question: does it arrange the result so that the data can be sent in 2 bit style right away to c64 ? :) |
| |
Krill
Registered: Apr 2002 Posts: 2980 |
Reordering and flipping the bits in a data byte does not change the coding scheme, so yeah, perfectly possible. |
| |
doynax Account closed
Registered: Oct 2004 Posts: 212 |
Quoting KrillWhat is the actual theoretical limit, as in entropy of a bitstream under the 3-zeros/10-ones condition? I had thought about computing it but never found a computationally feasible method, the naive approach being to count all valid bit combinations in a chunk of N bytes and to log2 that count. Interesting problem. I believe it's about 7.01948 bits/byte.
Imagine recursively producing all legal codes via the naive approach. You'd always be in one out of eleven coder states deciding what the options for the next state (and bit) are. Except work backwards from the end of the track and memoize the counts for each possible state at the subsequent bit.
E.g.:future[1..N] = 1;
for(bits = 1 to M) {
present[O1] = future[O2] + future[Z1];
present[O2] = future[O3] + future[Z1];
present[O3] = future[O4] + future[Z1];
present[O4] = future[O5] + future[Z1];
present[O5] = future[O6] + future[Z1];
present[O6] = future[O7] + future[Z1];
present[O7] = future[O8] + future[Z1];
present[O8] = future[O9] + future[Z1];
present[O9] = future[Z1];
present[Z1] = future[O1] + future[Z2];
present[Z2] = future[O1];
future = present;
}
result = log2(present[O1]) / bits; At least I think that should do it.
Anyone care to show me how to solve it properly? That is analytically, for an infinite bitstream. |
| |
Kabuto Account closed
Registered: Sep 2004 Posts: 58 |
@doynax: that's what I did as well, just the other way round, but results are the same.
I don't think this is solveable analytically. To make an equation out of it multiply all left side parts of those assignments with a variable (to express that values grow constantly for every step taken). Also you should fix one of the values to 1 (to avoid 0 for everything but f being a valid solution). Example for maxima: algsys([O1*f = O2 + Z1,O2*f = O3 + Z1,O3*f = O4 + Z1,O4*f = O5 + Z1,O5*f = O6 + Z1,O6*f = O7 + Z1,O7*f = O8 + Z1,O8*f = O9 + Z1,O9*f = Z1,Z1*f = O1 + Z2,Z2*f = O1,O1=1],[f,O1,O2,O3,O4,O5,O6,O7,O8,O9,Z1,Z2]);
In fact I didn't use sequences of 9 '1' bits in a row for technical reasons (because when you get a GCR byte of value $FF you won't be able to determine whether you can add another '1' bit without looking at the byte before as well) so I get just 7.0078 bits per byte.
@Krill: The "initial decoder state" is required for each sequence of GCR-coded values which can have any length you want. You can think about it as follows: each GCR-coded byte contributes its information content to 2 adjacent raw 7-bit values each. So e.g. with 10 GCR bytes you get 9 raw 7-bit values and one incomplete value at start and end each. |
| |
Urban Space Cowboy
Registered: Nov 2004 Posts: 45 |
Kabuto, could you please edit your first post so the code part isn't a hundred columns wide and causing the entire page to have to be scrolled horizontally? |
| |
Frantic
Registered: Mar 2003 Posts: 1648 |
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: 11386 |
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 !!! ;) |
... 16 posts hidden. Click here to view all posts.... |
Previous - 1 | 2 | 3 - Next |