Re: A Puzzle for Today

Guest
Posts: n/a

 04-06-2009, 12:01 AM

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?

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

Jon Kirwan
Guest
Posts: n/a

 04-06-2009, 04:00 AM
On Sun, 05 Apr 2009 19:01:43 -0500, Vladimir Vassilevsky
<(E-Mail Removed)> 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

Frank Buss
Guest
Posts: n/a

 04-06-2009, 04:58 AM

> 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, (E-Mail Removed)
http://www.frank-buss.de, http://www.it4-systems.de

Jerry Avins
Guest
Posts: n/a

 04-06-2009, 02:02 PM
>
>
> 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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Guest
Posts: n/a

 04-06-2009, 02:23 PM

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

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

Mark Borgerson
Guest
Posts: n/a

 04-06-2009, 02:55 PM
In article <ffoCl.25951\$(E-Mail Removed)>,
(E-Mail Removed) says...
>
>
>
> >
> >>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

Mark Borgerson
Guest
Posts: n/a

 04-06-2009, 03:00 PM
In article <ffoCl.25951\$(E-Mail Removed)>,
(E-Mail Removed) says...
>
>
>
> >
> >>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

Alun
Guest
Posts: n/a

 04-06-2009, 03:51 PM
"Mark Borgerson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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.

Jerry Avins
Guest
Posts: n/a

 04-06-2009, 04:18 PM
>
>
>
>>
>>> 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.
>
>
> 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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Jerry Avins
Guest
Posts: n/a

 04-06-2009, 04:32 PM
Mark Borgerson wrote:
> In article <ffoCl.25951\$(E-Mail Removed)>,
> (E-Mail Removed) says...
>>
>>
>>>
>>>> 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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Habib Bouaziz-Viallet Embedded 9 04-09-2009 10:15 PM Jon Kirwan Embedded 2 04-06-2009 06:45 AM Jerry Avins Embedded 2 04-06-2009 04:56 AM Vladimir Vassilevsky Embedded 0 04-05-2009 11:43 PM sk Hardware 3 07-18-2004 02:50 AM

All times are GMT. The time now is 03:55 PM.

Welcome!