A Puzzle for Today

That's simple: X must be (a

Express the bytes as hex pairs. Subtract each high digit from the corresponding low digit and add the result to a running sum. When the entire number has been processed, repeat the operation on the sum, iteratively until the sum is just one digit. The value of that digit is the original number mod 17.

Add all digits instead of subtracting alternate ones. the result is the original number mod 15.

In any base, the alternate difference of the digits yields N mod base+1, while the sum of the digits yields N mod base-1.

Work in octal, and get divisibility by 7 and 9.

I once proved it. Can you?

Jerry

Perhaps you meant (a

Yes. As you say it works on the same basis as proving divibility by

0x0001 0x0000 + 0x0001 0x00 x 0x11 + 1

A number is divisible by 17 iff the alternating sum of its hexadecimal digits is a multiple of 17.

Jon

If I gather that you can permit the entire 8 bit field to be out of balance so long as it comes out balanced on 8 bit boundaries, it's just combinatorial stuff. 70 ways to select 4 '1's out of 8 bits. (n!/[r!*(n-r!)]) The notation is usually just a big paren with n on top and r on bottom.

Since this is RS-232 signaling I might also assume it's asynch, and then the start and stop bits plus the long mark times that may intervene between byte transmissions may need accounting for. But then you said it's not RS-232 signaling since it is AC coupled, which isn't RS-232 which specifies a DC path, so all bets are off.

Jon

Wow. I didn't know about the N mod base+1 rule; I was thinking add all the bytes together (to get the number mod 255), then check the resulting one-byte number for divisibility by 17 ('cause 255 is 15 * 17).

Live and learn.

(but note that on my proposed machine, my method's probably faster because you don't have to shift and mask for 8-bit access the way you would for 4-bit access).

I once proved the N mod base-1 rule, but I can't remember the details; I'm going to look at Jon's proof.

If both start and stop bits are one long they'll balance; you'll be left with just needing to balance your data.

If you could allow one bit of imbalance either way you could have 156 combinations; that's gotta be better.

^^^^^^ woops...

Typo thing easily seen and fixed. Sorry about that.

Jon

This is an interesting problem from a mathematical point of view. I'm a programmer, so I have hacked a small program (see below), which calculates it for n bits, because this was faster and more safe than when I try to derive it mathematically. Then I searched the sequence at NJAS and found this one:

So for N bytes there are (8*N)!/((4*N)!)^2 possible combinations.

For practical reasons (would be bad to have 10 bytes with 0 and 10 bytes with 0xff) I would simply use some standard bi-phase encoding, like AES-3 or Manchester.

(loop for bit from 1 to 24 with number = 2 do (loop for i to (1- number) with test = 0 finally (format t "~a ~a~%" bit test) do (loop for j to bit with sum = 0 and b = i finally (when (= sum (/ bit 2)) (incf test)) do (when (= (logand b 1) 1) (incf sum)) (setf b (truncate b 2)))) (setf number (* 2 number)))

The techniques are very broadly applied. I mentioned the alternating approach. But just find the first multiple of the desired divisor that yields a '1' in the units position of any base you want to work in. For example, with the case of the base-10 value of 17, but working in base-16, it's just a factor of 1 since 1 times 0x11 produces a value that has a '1' in the units digit. (We want stuff that goes modulo to the base we are working in, resulting in 1.) Because it's just a factor 1, a number is divisible by 0x11 iff taking the least digit times 1 from what remains is itself divisible by 0x11.

Examine 0x58BB3:

Current Last Digit Without last digit Subtract last digit

divisible!

But this continued subtraction is the same as:

Subtract last digit

or, 0x5 - 0x5 + 0xB - 0xB + 0x3

Which is just what was mentioned at the outset -- alternating addition and subtraction of hexadecimal digits.

...........

This works for most anything you want to play with.

For any N, think of N = Z*x + 1*y, where Z is the system base and y is a digit in that base. x is what remains on the left side after removing y. If W is your divisor, you want to find a multiplier that when multiplied by W produces a '1' in the units digit. (The reason will be obvious in a moment.) Call that number P. Then for N to be divisible by W, it must be the case that N-P*y is also divisible by W. (Think about it.) If that is the case, and we already have N=Z*x+y, then Z*x+y-P*y must be divisible by W. But this is just Z*x-(P-1)*y and we've already asserted that P has a '1' in its units digit. So this means that P-1 must be Z*p (where p is just (P-1)/Z.) So this means Z*x-Z*p*y must be divisible by W, which means that Z*(x-p*y) must also be divisible. Assuming we don't have the confusion that D has a common factor with Z (and that can be handled as well), then it must be the case that (x-p*y) is the part that divisible by W, since Z isn't divisible by W. So we just need to look at that part. But that part has 'b' which is the part of the number without the units digit minus the units digit times p. And then this can repeat.

For example, take the factor 27, which is 0x1B. What multiple of 0x1B yields a '1' in the units? 0x51 is a multiple of 0x1B. Following the logic here, p is 0x5 (0x51 - 1 divided by the base which is 0x10). So we just need to take the upper digits and subtract 0x5 times the units digit. Then repeat.

Examine N=0xB03D and D=0x1B. P=0x51, p=0x5:

Current Last Digit Without last digit Subtract last digit

............

Now try out a few in base 10.

Jon

I mean, "Assuming we don't have the confusion that W...

Sorry.

Jon

Sorry, this is also messed up. Should be:

or, 0x5 - 0x8 + 0xB - 0xB + 0x3

...

Jon

Use even parity.

Jerry

You guys are professionals, so the quiz appeared to be too basic for you. Here is more complicated: Suggest a systematic procedure to map the natural numbers 0...N into the abovementioned DC balanced code and back for the general case of M bit words. LUT is not a solution.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

If you're not worried about channel bandwidth, why not simply transmit N, followed by N^0xFFFF (to as many bytes width as required)? You balance the line and you get a simple method to check for single-byte transmission errors.

Mark Borgerson

One major problem with DC balance and async comms is that you can't let the line sit idle. You have to have continuous transmission or the stop bits destroy the balance. In situations like this hardware helps! ;-)

Mark Borgerson

ISTR that this was solved many years ago by the Post Office / BT with its HDB3 format.

RS-232 is a partial connector specification (25 pins) and a voltage specification (respond to so-and-so, withstand such-and-such) amd stuff about start and stop bits. The number of data bits is not part of the specification, nor is the inclusion of parity or any other error control. This is an interesting problem, but poorly put. As posed, 256 codes can be achieved by using one start bit (space), one stop bit (mark), eight data bits, and even parity. Many UARTs can be so configured.

Jerry

Just send even-parity SYNC when there's no other data. That costs one symbol, but it's no words than synchronous communication. DEL might be a better choice to help recovery from framing errors.

Jerry