A Puzzle for Today

Whenever the sum threatens to become too large, the iteration can begin on it, reducing it to a single byte, then the original process can continue. However, since nybbles are alternately added and subtracted, the likelihood of the sum going very large is remote.

Jerry

Interesting. I once had to design such a code for an RF modem that required DC balanced modulation. I didn't need DC balance over a short distance, so ended up using two groups of codes, one DC balanced and the other off by one. If an off by one code was sent, then the next off by one code would always be off in the opposite direction.

LOL! How well is that going to run from ROM? I haven't seen self- modifying code since my Apple II programming days.

That code also might have a problem with a number longer than 256 bytes. ;-)

Mark Borgerson

That is also what some forms of ethernet do.

-- glen

Actually I think if you are working with n bits then anything 2^n - 1 is divisible by can be tested.

If the input number is summed n bits at a time the n bit result will be divisible by the number if the input was.

For bytes that would be 3, 5, 15, 17, 51, 85 ?

High nibble = low nibble is just an easy test for divisible by 17

Heh. I did that just for grins.

True, but I did say "something like". Alter as necessary for actual requirements.

Scott

Vladimir Vassilevsky ha escrito:

I'd encrypt the data with a modern stream or block cipher with a randomly selected key. That makes it indistinguishable from random, which is DC balanced.

This approach gives the full 256 combinations per byte.

Best regards, Marc

Doesn't that cause a bit of a problem if the data happens to match the 'random' encrytion. Being random it is possible (if unlikely) that a significant stream of data could turn into a long string of 1s or 0s.

1. Random is balanced only over the infinite time.

1. There is a possibility of matching the data and the key stream, although unlikely.

Not a solution.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

The puzzle didn't specify any maximum time. My solution balances already very well over runs as short as a few bytes.

As specifically said, the key must be randomly selected. The likelyhood of a match can be minimized arbitrarily by choosing a bigger cipher blocksize. It's sufficient to push it below the error rate of the other components of your system.

For example, with AES256 you get a collision resistance of 2^128. Use it to transfer data on a serial 1gbit/s link and you find that your link must have a MTBF of >2^56 million hours. Only then the DC balancer is likely to fail first. If you build the link from realworld parts, then the link will fail for other reasons long before.

To put this into context: Professional ethernet equipment comes with MTBF between 300K to 2M hours. And there's quite a difference between

Please explain why.

Regards, Marc

Just because an event has a 1:N proability of failing does not mean that one has to wait for N events for it to fail. It does not even mean that a failure is guaranteed after N events. The failure could occur on the 1st event or the 1st few events.

If a string of 20 of the same bit is enough to cause errors, then your perfectly random crypto on your 1 Gbit/s serial link will fault a thousand times a second.

The puzzle didn't specify a maximum time, but a 1 ms MTBF is rarely acceptable in the real world.