Motherboard Forums


Reply
Thread Tools Display Modes

Re: A Puzzle for Today

 
 
Vladimir Vassilevsky
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?

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com
 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
Frank Buss
Guest
Posts: n/a
 
      04-06-2009, 04:58 AM
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, (E-Mail Removed)
http://www.frank-buss.de, http://www.it4-systems.de
 
Reply With Quote
 
Jerry Avins
Guest
Posts: n/a
 
      04-06-2009, 02:02 PM
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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
 
Reply With Quote
 
Vladimir Vassilevsky
Guest
Posts: n/a
 
      04-06-2009, 02:23 PM



> 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

 
Reply With Quote
 
Mark Borgerson
Guest
Posts: n/a
 
      04-06-2009, 02:55 PM
In article <ffoCl.25951$(E-Mail Removed)>,
(E-Mail Removed) 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


 
Reply With Quote
 
Mark Borgerson
Guest
Posts: n/a
 
      04-06-2009, 03:00 PM
In article <ffoCl.25951$(E-Mail Removed)>,
(E-Mail Removed) 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


 
Reply With Quote
 
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.


 
Reply With Quote
 
Jerry Avins
Guest
Posts: n/a
 
      04-06-2009, 04:18 PM
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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
 
Reply With Quote
 
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...
>>
>>
>>> 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.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
 
Reply With Quote
 
 
 
Reply

Thread Tools
Display Modes

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


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


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


Welcome!
Welcome to Motherboard Point
 

Advertisment