Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Theoretically optimal 1541 GCR encoding scheme
2012-11-14 00:28
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
2012-11-14 02:23
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.
2012-11-14 07:24
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 ? :)
2012-11-14 09:10
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.
2012-11-14 21:47
doynax
Account closed

Registered: Oct 2004
Posts: 212
Quoting Krill
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.
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.
2012-11-14 22:49
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.
2012-11-24 15:06
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?
2012-11-24 18:11
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.
2013-01-30 17:50
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 ;)
2013-01-30 18:07
chatGPZ

Registered: Dec 2001
Posts: 11386
isnt this a pure software issue (which applies to 1541u just aswell) ?
2013-01-30 19:02
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
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
Metal Maniac/Dual Crew
Brataccas/HF
csabanw
El Jefe/Slackers^sidD
Morpheus/IPC+C64.COM
Icon/TRIAD
Mythus/Delysid
Guests online: 118
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 Edge of Disgrace  (9.6)
6 What Is The Matrix 2  (9.6)
7 The Demo Coder  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 Layers  (9.6)
2 No Listen  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 Dawnfall V1.1  (9.5)
7 Rainbow Connection  (9.5)
8 Onscreen 5k  (9.5)
9 Morph  (9.5)
10 Libertongo  (9.5)
Top Groups
1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Triad  (9.3)
5 Censor Design  (9.3)
Top Webmasters
1 Slaygon  (9.6)
2 Perff  (9.6)
3 Sabbi  (9.5)
4 Morpheus  (9.4)
5 CreaMD  (9.1)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.049 sec.