Re: A Puzzle for Today

Tim Wescott wrote:

> You have a Very Large Number, expressed as an binary integer, in the
> memory of a machine that allows for byte-wide operations. For some
> unfathomable reason, you need to determine if this number is evenly
> divisible by 17.

Perhaps you meant (a<<4) + a; good question for job interview.

Here is the question I like:

We have to transmit RS-232 by the AC coupled line. Hence the signal has
to be DC balanced, i.e. have equal amount of ones and zeroes. How many
bit combinations like that can be made of one byte? How about the
general case of the block of N bytes?

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Sun, 05 Apr 2009 19:01:43 -0500, Vladimir Vassilevsky
<> wrote:

>Tim Wescott wrote:
>
>> You have a Very Large Number, expressed as an binary integer, in the
>> memory of a machine that allows for byte-wide operations. For some
>> unfathomable reason, you need to determine if this number is evenly
>> divisible by 17.
>
>Perhaps you meant (a<<4) + a; good question for job interview.
>
>Here is the question I like:
>
>We have to transmit RS-232 by the AC coupled line. Hence the signal has
>to be DC balanced, i.e. have equal amount of ones and zeroes. How many
>bit combinations like that can be made of one byte? How about the
>general case of the block of N bytes?

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

Vladimir Vassilevsky wrote:

> We have to transmit RS-232 by the AC coupled line. Hence the signal has
> to be DC balanced, i.e. have equal amount of ones and zeroes. How many
> bit combinations like that can be made of one byte? How about the
> general case of the block of N bytes?

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:

http://www.research.att.com/~njas/sequences/A000984

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)))

--
Frank Buss,
http://www.frank-buss.de, http://www.it4-systems.de

Vladimir Vassilevsky wrote:
>
>
> Tim Wescott wrote:
>
>> You have a Very Large Number, expressed as an binary integer, in the
>> memory of a machine that allows for byte-wide operations. For some
>> unfathomable reason, you need to determine if this number is evenly
>> divisible by 17.
>
> Perhaps you meant (a<<4) + a; good question for job interview.
>
> Here is the question I like:
>
> We have to transmit RS-232 by the AC coupled line. Hence the signal has
> to be DC balanced, i.e. have equal amount of ones and zeroes. How many
> bit combinations like that can be made of one byte? How about the
> general case of the block of N bytes?

Use even parity.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

> Vladimir Vassilevsky wrote:
>
>>We have to transmit RS-232 by the AC coupled line. Hence the signal has
>>to be DC balanced, i.e. have equal amount of ones and zeroes. How many
>>bit combinations like that can be made of one byte? How about the
>>general case of the block of N bytes?

[...]

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
http://www.abvolt.com

In article <ffoCl.25951$>,
says...
>
>
>
> > Vladimir Vassilevsky wrote:
> >
> >>We have to transmit RS-232 by the AC coupled line. Hence the signal has
> >>to be DC balanced, i.e. have equal amount of ones and zeroes. How many
> >>bit combinations like that can be made of one byte? How about the
> >>general case of the block of N bytes?
>
> [...]
>
> 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.
>
>
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

In article <ffoCl.25951$>,
says...
>
>
>
> > Vladimir Vassilevsky wrote:
> >
> >>We have to transmit RS-232 by the AC coupled line. Hence the signal has
> >>to be DC balanced, i.e. have equal amount of ones and zeroes. How many
> >>bit combinations like that can be made of one byte? How about the
> >>general case of the block of N bytes?
>
> [...]
>
> 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.
>
>
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

"Mark Borgerson" <> wrote in message
news: g...
>>
> 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! ;-)

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

Vladimir Vassilevsky wrote:
>
>
>
>> Vladimir Vassilevsky wrote:
>>
>>> We have to transmit RS-232 by the AC coupled line. Hence the signal
>>> has to be DC balanced, i.e. have equal amount of ones and zeroes. How
>>> many bit combinations like that can be made of one byte? How about
>>> the general case of the block of N bytes?
>
> [...]
>
> 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
> http://www.abvolt.com

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
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Mark Borgerson wrote:
> In article <ffoCl.25951$>,
> says...
>>
>>
>>> Vladimir Vassilevsky wrote:
>>>
>>>> We have to transmit RS-232 by the AC coupled line. Hence the signal has
>>>> to be DC balanced, i.e. have equal amount of ones and zeroes. How many
>>>> bit combinations like that can be made of one byte? How about the
>>>> general case of the block of N bytes?
>> [...]
>>
>> 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.
>>
>>
> 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! ;-)

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
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯