Enumerating bit sequences with isolated zero-bits via the Fibonacci recurrence


Today's Little Program enumerates bit sequences of a particular length subject to the constraint that you cannot have consecutive 0-bits. This may sound kind of arbitrary, but it is important in magnetic media storage, because you cannot go too long without a flux reversal (traditionally represented by a 1); otherwise, the read head's clock starts to drift and gets out of sync with the data. (The read head uses flux reversals both for signaling and for clock synchronization.)

Let's say that an allowable bit sequence is one that contains no consecutive 0-bits.

The recurrence for enumerating these types of constrained bit sequence is the Fibonacci recurrence:

F(n) = F(n − 1) + F(n − 2)

The way to see this is to study the last digit in an allowable bit sequence.

If the last digit is a 1, then if you delete it, you have an allowable bit sequence that is one digit shorter. Conversely, you can take any allowable bit sequence of length n − 1 and tack a 1 onto it, and you'll have an allowable sequence.

If the last digit is a 0, then if you delete it, you also have an allowable bit sequence that is one digit shorter, but not all allowable bit sequences of length n − 1 can be reached in this way. Allowable bit sequences that end in 0 cannot be reached because adding another 0 would result in two consecutive 0-bits, which is disallowed. Therefore, the last digit of the truncated bit sequence must be 1, and what you really have is an allowable bit sequence of length n − 2, followed by a hard-coded 1.

Okay, now that we understand the enumerative justification for the recurrence, we can proceed to write the code that generates it.

function GCR(n, f) {
 if (n == 0) { f(""); return; }
 if (n < 0) { return; }
 GCR(n-1, function(s) { f(s + "1"); });
 GCR(n-2, function(s) { f(s + "10"); });
}

GCR(8, console.log);

The test run calculates all 8-bit allowable sequences. But wait, there's a bug: It shows only the sequences that begin with a 1.

If you're Steve Wozniak, then this bug is a feature, because the Apple II floppy drive also required the first bit to be set, so our bug exactly matches the hardware requirements.

But let's fix our bug. Where did it come from?

Our recursive step missed a base case: The single-digit bit sequence 0 is allowable, but we rejected it because we thought that it needed to be separated from the null string by a 1, to protect against the null string ending in 0. But the null string doesn't end in zero, so this protection was unnecessary.

Repairing our base case:

function GCR(n, f) {
 if (n == 0) { f(""); return; }
 if (n == 1) { f("0"); f("1"); return; }
 GCR(n-1, function(s) { f(s + "1"); });
 GCR(n-2, function(s) { f(s + "10"); });
}
Comments (22)
  1. Mark says:

    What's wrong with Manchester coding?

  2. Brian_EE says:

    Mark – Twice the bandwidth is required for starters.

    As I am not well-versed in mag-media technology, what I don't understand is the distinction of why consecutive 1's are allowed but not consecutive 0's. It seems to me that too many of any one level would cause clock synchronization (no transitions to phase lock to). I am familiar with 8B10B etc on comms link, these are specifically designed to maintain DC balance.

    Maybe I should go read up on drive encoding basics…

    [You're thinking about it wrong. 0 and 1 are not levels. They are transitions. Staying at the same level = 0. Changing levels = 1. Consecutive 0's means "staying at the same level for a long time", which means that you lose the clock. -Raymond]
  3. y says:

    You can store 0 as "no change" and 1 as "change". Then multiple 1's are changes, for example 0 -> 1 -> 0 would be 11 and clock can be synchronized as head go. For 0 it would be 0 -> 0 -> 0 for 00, no change and no synchronization.

  4. VinDuv says:

    @Brian_EE: Storing many consecutive zeros on a drive is probably much more frequent than storing many consecutive ones, since people tend to initialize unused stuff to 0. Not sure if it is the real reason though.

  5. Antonio &#39;Grijan&#39; says:

    @Mark: that's how Wozniak got the Apple II to store 140 KB in single density, single sided 5.25" floppies, where other systems, which were using FM (similar to Manchester Coding) only attained 90 KB in the same disks.

  6. alegr1 says:

    @Brian EE:

    Yes, more effective encoding schemes (such as RLL 2,7) allow flux reversals only every 3 to 8 clocks (2 to 7 clocks without reversal).

  7. Joshua says:

    There must be some reason why they don't use a non-seeking head on a clock track. Oh wait removable media.

  8. alegr1 says:

    @Joshua:

    You're kidding, right? "a non-seeking head on a clock track" doesn't make any sense whatsoever, for removable or fixed media.

    [Um, you do realize that all floppy disks had a clock track. (The index hole.) It's just that the resolution of that track was 1 bit per revolution, which is too coarse for maintaining accurate clocking. Joshua is proposing that one track on the drive be a dedicated clock track, and that there be a dedicated head for reading it. -Raymond]
  9. alegr1 says:

    [You're thinking about it wrong. 0 and 1 are not levels. They are transitions. Staying at the same level = 0. Changing levels = 1. Consecutive 0's means "staying at the same level for a long time", which means that you lose the clock. -Raymond]

    YOU're thinking about it wrong. There is no reason to not allow transition in a few consecutive clocks. You don't also want to allow transitions next to each other.

  10. alegr1 says:

    >There is no reason to not allow transition in a few consecutive clocks.

    Make it "to not allow NO transition for a few consecutive clocks". Means you can have a string of zeros (of limited length).

    Clock recovery PLLs can do a good job.

    [Go tell Steve Wozniak that he designed his floppy drive wrong. -Raymond]
  11. alegr1 says:

    [Um, you do realize that all floppy disks had a clock track. (The index hole.) It's just that the resolution of that track was 1 bit per revolution, which is too coarse for maintaining accurate clocking. Joshua is proposing that one track on the drive be a dedicated clock track, and that there be a dedicated head for reading it. -Raymond]

    The index hole is not needed for reading. The sector number is in the header. The hole only provides the start of track for formatting.

    Using a separate track for clock is a) impossible because of mecanical jitter and impredictable skew which would change because of temperature; b) impossible because different zones use different bit clock rate; c) not necessary because the clock recovery is a solved problem, which works in all fields of digital communications.

    [Right. Nobody actually used the index hole for clocking, but it demonstrated the point: A dedicated track for clocking. Wikipedia says that there is a limit to how long you can go without a transition, so if it's a solved problem, you need to update Wikipedia. -Raymond]
  12. alegr1 says:

    [Go tell Steve Wozniak that he designed his floppy drive wrong. -Raymond]

    The magnetic recording technology went a long way since then. The next step after MFM was so called group recording (first RLL version), which used up to two clocks with no flux transition. Later RLL variants allowed for even longer no-transition runs.

  13. alegr1 says:

    [Wikipedia says that there is a limit to how long you can go without a transition, so if it's a solved problem, you need to update Wikipedia. -Raymond]

    You're citing the article on clock recovery technology to counteract an argument that clock recovery is an existing technology?

    Oh, and by the way, in 8/10 encoding (used in many applications, such as CD, Ethernet, FC, IB) 6 clocks can go without a transition. A clock recovery circuit can handle that OK.

    [Sorry, I thought you were claiming that "you cannot have too many 0's in a row" was a solved problem. -Raymond]
  14. Roger Lipscombe says:

    Er, guys, the Apple II came out in 1977. I wonder whether, back then, the issues with clock sync hadn't been completely figured out? Raymond's post is an example of an interesting recurrence caused when you don't allow consecutive zero bits. More advanced circuitry and logic (possibly even before 1977) would allow strings of zero bits, but that's not the central point of the post.

    (Is there the opposite of the nitpicker's corner around here?)

  15. Mark says:

    Exactly what Roger said – PLLs were cutting edge in the 70s, and didn't really become prevalent until the next decade.

  16. lefty says:

    "Okay, now that we understand the enumerative justification for the recurrence…"

    For groups of 'we' that don't include me.  I barely understand the snippet I quoted.

    [As I noted some time ago, when you see a recurrence of the form A + B, that means do A, followed by B. The previous two paragraphs described the two cases. Now we just need to do one, followed by the other. -Raymond]
  17. Paul says:

    I copied the code into a ".js" file and executed it with a double click, but it says "'console' is undefined". What am I doing wrong?

  18. acq says:

    Paul, if you're running the script from the windows scripting host add the line:

    function pr( s ) { WScript.Echo( s ); }

    and replace GCR(8, console.log); with GCR( 8, pr );

    Still I don't know how to run from the Windows command line the code from here: blogs.msdn.com/…/10516909.aspx apart from installing node.js. Maybe somebody knows.

  19. Mark says:

    Just paste it into the console of your browser.

    I needed to do GCR(8, function(x) {console.log(x)}); on Chrome.

  20. Action<string> s => f(s++) says:

    I translated it to C# and executed it. Then I changed 8 to 4000000000 (uint arg) to be a silly ***. It stack overflowed.

  21. smf says:

    @alegr1

    "The next step after MFM was so called group recording"

    Wozniak's floppy was group recording. MFM added a clock bit between each data bit that guaranteed there was always a transition between the data bits. Giving you 4 actual bits for 8 bits on the disk. Group recording was developed at Apple and commodore simultaneously, Apple had 5 data bits for 8 bits on the disk while commodore had 4 data bits for 5 bits on disk.

    @Raymond

    "[Go tell Steve Wozniak that he designed his floppy drive wrong. -Raymond]"

    commodore achieved an extra 25% storage, so arguably he did. He later improved it by storing 6 data bits in 8 bits on disk, commodore still beat them by 6-7%.

    commodore designed their floppy drives wrong in other ways (especially the later consumer models), it's all ancient history now though.

  22. Querulous says:

    What is the programming language being used here to define the GCR function? Is it Javascript? If so, how do I execute it using some online javascript engine like http://www.compileonline.com/try_javascript_online.php

Comments are closed.