[CSDb] - User Forums - Tape loaders using more than two pulse widths for data

Welcome to our latest new user maak ! (Registered 2024-04-18)

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Tape loaders using more than two pulse widths for data

2018-12-08 20:16

ChristopherJam

Registered: Aug 2004
Posts: 1370

Tape loaders using more than two pulse widths for data

I’ve been thinking a bit about a novel tape encoding, but it would rely on (among other things) having more than two pulse widths. So far as I can see, none of the old turbo loaders used a long pulse for anything beyond end of byte/end of block - the bitstream itself was just a sequence of short and medium pulses (usually around 200 cycles for short, 300 to 450 for long).

Is there any particular reason none of the popular loaders used (eg) four pulse widths for each bitpair? Even using quite widely separated durations of 210/320/450/600 would then lead to an average time per bit of just 197 cycles, a massive improvement on the 265 cycles per bit you’d get for 210/320.

(The idea I’ve been working on is a bit more complex than that, but if a simple bitpair scheme wouldn’t work for some reason, then the idea I have would need to be scaled back somewhat. Promising that long pulses were used for framing, mind..)

... 23 posts hidden. Click here to view all posts....

2018-12-12 12:47

enthusi

Registered: May 2004
Posts: 674

Ah good to see you here :)
I, too, was/am impressed, hehe.

2018-12-15 00:39

ChristopherJam

Registered: Aug 2004
Posts: 1370

I've managed to verify my hypothesis that the optimal weights to use for an arithmetic encoding based loader are those that ensure each symbol outputs the same number of bits per cycle.

Approximating the arithmetic encoder with a huffman code only loses one or two percent of efficiency, so that would probably be a somewhat saner path to take.

On the way, I found a marginally faster encoding using thrust64's pulse lengths. Using output words of { 11, 01, 101, 100, 000, 0011, 0010 } results in an average cost per bit of 102.9 cycles, compared
to thrust64's 108.8

Have some pretty graphs, and the script that generated them.

Each graph covers a family of pulse lengths, as given by the equations in the titles. The two lines show optimal cost per output bit, as a function of the number of pulse lengths used for the encoding.
This is purely for the data rate within each word; framing bits and error correction are outside the scope of this investigation, and would in practice add an overhead of 10-20%

There's a table after each graph giving the optimal encoding for the case where seven distinct pulse lengths are used. Note that if the gap is comparable to the shortest pulse length, the
optimal huffman encoding is isomorphic to transition=1, no transition=0, with some extra transitions inserted after long runs of zeros. This changes when the gap is relatively
small compared to the shortest length.

Using Thomas Jentzsch's pulse spacing (167+50*n cycles)
but optimising the encoding for that spacing

+----------------+-----------------+--------------+
| Pulse duration | arithmetic code | huffman code |
+----------------+-----------------+--------------+
| 167 cycles     | 0.31886         | 11           |
| 217 cycles     | 0.22645         | 01           |
| 267 cycles     | 0.16083         | 101          |
| 317 cycles     | 0.11422         | 100          |
| 367 cycles     | 0.08112         | 000          |
| 417 cycles     | 0.05761         | 0011         |
| 467 cycles     | 0.04091         | 0010         |
+----------------+-----------------+--------------+
mean cycles per bit, arithmetic code = 101.3
mean cycles per bit,    huffman code = 102.9

Using AR Turbo's short pulse, Fast Evil's spacing
(150+80*n cycles)

+----------------+-----------------+--------------+
| Pulse duration | arithmetic code | huffman code |
+----------------+-----------------+--------------+
| 150 cycles     | 0.39979         | 0            |
| 230 cycles     | 0.24517         | 10           |
| 310 cycles     | 0.15035         | 110          |
| 390 cycles     | 0.09220         | 1110         |
| 470 cycles     | 0.05654         | 11111        |
| 550 cycles     | 0.03468         | 111101       |
| 630 cycles     | 0.02127         | 111100       |
+----------------+-----------------+--------------+
mean cycles per bit, arithmetic code = 113.4
mean cycles per bit,    huffman code = 116.2

Using AR Turbo's short pulse, Fast Evil's min spacing,
increasing gap for longer pulses (150+80*n**1.1 cycles)

+----------------+-----------------+--------------+
| Pulse duration | arithmetic code | huffman code |
+----------------+-----------------+--------------+
| 150 cycles     | 0.41389         | 0            |
| 230 cycles     | 0.25856         | 10           |
| 320 cycles     | 0.15230         | 110          |
| 416 cycles     | 0.08660         | 1110         |
| 516 cycles     | 0.04810         | 11111        |
| 618 cycles     | 0.02640         | 111101       |
| 724 cycles     | 0.01415         | 111100       |
+----------------+-----------------+--------------+
mean cycles per bit, arithmetic code = 117.9
mean cycles per bit,    huffman code = 119.7

something a bit more conservative (180+ 90*n)

+----------------+-----------------+--------------+
| Pulse duration | arithmetic code | huffman code |
+----------------+-----------------+--------------+
| 180 cycles     | 0.38997         | 0            |
| 270 cycles     | 0.24352         | 10           |
| 360 cycles     | 0.15207         | 110          |
| 450 cycles     | 0.09497         | 1110         |
| 540 cycles     | 0.05930         | 11110        |
| 630 cycles     | 0.03703         | 111111       |
| 720 cycles     | 0.02313         | 111110       |
+----------------+-----------------+--------------+
mean cycles per bit, arithmetic code = 132.5
mean cycles per bit,    huffman code = 136.4

https://jamontoads.herokuapp.com/csdb/201812/compare_encodings...

No, I'm not going to go and write a loader based on this investigation in the near future. But, I hope this is useful or at least interesting to someone else out there.

Many thanks to SLC, Enthusi, thrust64 & tlr for their assistance.

2018-12-16 14:52

thrust64

Registered: Jun 2006
Posts: 8

Cool stuff. I remember that I did some similar research back then.

You limited your research to 7 different pulse lengths. Depending on the shortest pulse and the spacing, this may not be the optimal solution. E.g. for the last, conservative approach, I am pretty sure that a lower number of pulse lengths would give a better result.

Also, what sample data did you base your pattern distribution on? E.g uncompressed data must result into pretty different values depending on the content and very different than compressed one. For the latter, all bits and combinations should have about the same probability.

2018-12-16 21:18

ChristopherJam

Registered: Aug 2004
Posts: 1370

Quoting thrust64

Cool stuff. I remember that I did some similar research back then.

Thanks! I assumed as much.

Quote:

You limited your research to 7 different pulse lengths. Depending on the shortest pulse and the spacing, this may not be the optimal solution. E.g. for the last, conservative approach, I am pretty sure that a lower number of pulse lengths would give a better result.

My apologies, the tables are results for 7 pulse lengths, but the graphs show average cycles per bit as a function of the number of pulse lengths used, from 2 to 8. If you look at those, you can see that the more pulses lengths you use, the better your throughput (though admittedly you're most of the way to optimal by five or six).

Quote:

Also, what sample data did you base your pattern distribution on? E.g uncompressed data must result into pretty different values depending on the content and very different than compressed one. For the latter, all bits and combinations should have about the same probability.

I'm assuming random data - compression helps a *lot* if your raw speed is this low.

2018-12-16 21:55

thrust64

Registered: Jun 2006
Posts: 8

> ...but the graphs show average cycles per bit as a function of the number of pulse lengths used, from 2 to 8

Ah, my bad. Interesting that 8 is still the best even with conservative timing.

> I'm assuming random data...

Hm... With random data all shouldn't arithmetic data be 0.5 for single bits and 0.25 for two bit combinations? How did you get to these different values? I am sure I am missing something (again).

2018-12-17 09:08

ChristopherJam

Registered: Aug 2004
Posts: 1370

Quoting thrust64

With random data all shouldn't arithmetic data be 0.5 for single bits and 0.25 for two bit combinations? How did you get to these different values? I am sure I am missing something (again).

It's a bit inside out - the loaded file is effectively a compressed representation of the stream of pulses from the tape (something of a headfuck, I know) - so it's the probabilities of the pulses arriving in the stream that's the pertinent factor.

The key point is that longer pulses (by definition) contribute more to the length of the recording than the short pulses, so unless they contain as much information per second as the shorter pulses, they're not pulling their weight.

I initially wasn't entirely sure of my intuition on that count, so I also wrote a function that just incrementally adjusts the weights for a set of symbols and runs simulated encodings.

That took a bit more to implement but got identical results in the end; I left the code for that in the script I linked above (it's just commented out).

Short version:

If r is the optimal transmission rate in bits per second, then each symbol needs to encode d*r bits, where d is the duration of the symbol in question. The sum of the probabilities of the symbols is one, so you just need to solve sum(0.5^(d*r))=1 to find r, then you can use r to find the bits per symbol

2018-12-17 09:44

thrust64

Registered: Jun 2006
Posts: 8

I could be wrong, but I think your math is slightly incorrect.

Simple example:

Cycles|Bits| Prob.| Cycles per bit and probability
------+----+------+-------------------------------
  100 | 0  | 0.5  | 50.00
  150 | 10 | 0.25 | 18.75
  200 | 11 | 0.25 | 25.00
------+----+------+------
            Total:  93,75

That's easy to verify: 0 takes 100 cycles and 1 takes (150+200)/2/2 = 87,5 cycles on average. So the average length per bit is (100+87.5)/2 = 93.75 cycles.

Using the same math for my own loader I get:

Cycles|Bits| Prob.| Cycles per bit and probability
------+----+------+-------------------------------
  167 |11  |0,25  | 20.875
  217 |01  |0,25  | 27.125
  267 |101 |0,125 | 11.125
  317 |100 |0,125 | 13.208
  367 |000 |0,125 | 15.292
  417 |0011|0,0625|  6.516
  467 |0010|0,0625|  7.297
------+----+------+--------
            total: 101.4375

So that would be ~101.4 cycles/bit vs ~102.9 as in your math (both using Huffman).

2018-12-17 11:00

ChristopherJam

Registered: Aug 2004
Posts: 1370

You're making the same mistake I was a few days ago :)

Symbols that output longer bit sequences consume more of the original file when it's being converted to a pulse stream, so they need to be weighted accordingly when you're computing the expected cycles per bit.

I just encoded a sequence of 1000 random bits with the [0,10,11]=>[100,150,200] encoding, and found 322 bare zeros, 165 "10" pairs, and 174 "11" pairs;
total duration 322*100+165*150+174*200=91750 cycles, or 91.75 cycles per bit, quite close to the 91.667 I get from the python snippet below:

from math import log
def log2(x):  return log(x)/log(2)

def cycles_per_bit_given_arithmetic_code(code):
    den = num = 0
    for dur,p in code:
        bits = -log2(p)
        weight = p*bits         # this is critical
        num += weight*dur/bits
        den += weight
    cycles_per_bit = num/den
    return cycles_per_bit

def hc_to_ac(hc_code):  # convert a huffman code to corresponding arithmetic code
    return [(d,0.5**len(s)) for d,s in hc_code]

hccode = [
        (100, '0'),
        (150, '10'),
        (200, '11'),
        ]

print(cycles_per_bit_given_arithmetic_code(hc_to_ac(hccode)))

or in table form:

+-----+----+------+-----------+--------+-------+
Cycles|Bits| Prob.|  w = p*b  |  c/b   | c/b*w |  (b=len(Bits))
+-----+----+------+-----------+--------+-------+
| 100 | 0  | 0.50 |    0.5    |  100.0 |  50.0 |
| 150 | 10 | 0.25 |    0.5    |   75.0 |  37.5 |
| 200 | 11 | 0.25 |    0.5    |  100.0 |  50.0 |
+-----+----+------+-----------+--------+-------+

total weighted rates = 137.5
total weights        =   1.5
weighted average     =  91.667

2018-12-17 11:25

thrust64

Registered: Jun 2006
Posts: 8

On average, I would expect ~333 0 bits plus ~167 01 and ~167 10 bits. Then we would have 333*100 + 167*150 + 167*200 = 91,750 for 1001 bits. Which about matches your number.

Quote:

You're making the same mistake I was a few days ago :)

Looks so. :)

Quote:

Symbols that output longer bit sequences consume more of the original file when it's being converted to a pulse stream, so they need to be weighted accordingly when you're computing the expected cycles per bit.

I stand corrected. You are right.

Thanks for explaining again.

2018-12-17 11:56

thrust64

Registered: Jun 2006
Posts: 8

So when we look at the results and graphs (also from enthusi), what would be the best way for a fast but still robust solution?

There a lots of factors we can play with:
1. short pulse length
2. pulse gap
3. number of pulse lengths (a result of 1. + 2.)
4. ???

And what is causing the inaccuracies?
- the varying tape speed (how much? +/-5%?) (increasing pulse gaps can cope with that)
- frequencies? E.g high frequencies have a lower amplitude than lower ones, causing less correct reads (then we would need decreasing pulse gaps to handle that)
- enthusi's graph shows some intervals of heavy distortions, what is causing these?
- varying frequencies? (e.g. a low frequency followed by a high one give less accurate results than two high ones)
- aging?
- what else?

This is really tricky. :)

Previous - 1 | 2 | 3 | 4 - Next

Refresh

Subscribe 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

Flex/Artline Designs
Ax!s/Onslaught - TND
Mason/Unicess
kbs/Pht/Lxt
CA$H/TRiAD
Guests online: 170

Top Demos

1 Next Level  (9.8)
2 Mojo  (9.7)
3 Coma Light 13  (9.7)
4 Edge of Disgrace  (9.6)
5 Comaland 100%  (9.6)
6 No Bounds  (9.6)
7 Uncensored  (9.6)
8 Wonderland XIV  (9.6)
9 The Ghost  (9.6)
10 Bromance  (9.6)

Top onefile Demos

1 It's More Fun to Com..  (9.8)
2 Party Elk 2  (9.7)
3 Cubic Dream  (9.6)
4 Copper Booze  (9.5)
5 Rainbow Connection  (9.5)
6 Wafer Demo  (9.5)
7 TRSAC, Gabber & Pebe..  (9.5)
8 Onscreen 5k  (9.5)
9 Dawnfall V1.1  (9.5)
10 Quadrants  (9.5)

Top Groups

1 Oxyron  (9.3)
2 Nostalgia  (9.3)
3 Booze Design  (9.3)
4 Censor Design  (9.3)
5 Crest  (9.3)

Top Crackers

1 Mr. Z  (9.9)
2 S!R  (9.9)
3 Mr Zero Page  (9.8)
4 Antitrack  (9.8)
5 OTD  (9.8)

Page generated in: 0.057 sec.