1. This forum section is a read-only archive which contains old newsgroup posts. If you wish to post a query, please do so in one of our main forum sections (here). This way you will get a faster, better response from the members on Motherboard Point.

Re: A Puzzle for Today

Discussion in 'Embedded' started by Vladimir Vassilevsky, Apr 6, 2009.

1. Vladimir VassilevskyGuest

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

Vladimir Vassilevsky, Apr 6, 2009

2. Jon KirwanGuest

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

Jon Kirwan, Apr 6, 2009

3. Frank BussGuest

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

Frank Buss, Apr 6, 2009
4. Jerry AvinsGuest

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

Jerry Avins, Apr 6, 2009
5. Vladimir VassilevskyGuest

> 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

Vladimir Vassilevsky, Apr 6, 2009
6. Mark BorgersonGuest

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

Mark Borgerson, Apr 6, 2009
7. Mark BorgersonGuest

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, Apr 6, 2009
8. AlunGuest

"Mark Borgerson" <> wrote in message
news:...
>>

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

Alun, Apr 6, 2009
9. Jerry AvinsGuest

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

Jerry Avins, Apr 6, 2009
10. Jerry AvinsGuest

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

Jerry Avins, Apr 6, 2009
11. Spehro PefhanyGuest

On Mon, 6 Apr 2009 07:55:29 -0700, 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.
>>
>>

>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

That scheme essentially groups bits into pairs. Not surprisingly, the
more bits you group together, the higher the efficiency:-

2/4 => 0.50
6/16 => 0.64
20/64 => 0.72
70/256 => 0.77
252/1024 => 0.80
924/4096 => 0.82
3432/16384 => 0.84
12870/65536 => 0.85
48620/262144 => 0.86
etc.

Spehro Pefhany, Apr 6, 2009
12. Jerry AvinsGuest

Tim Wescott wrote:
> On Mon, 06 Apr 2009 12:18:55 -0400, Jerry Avins wrote:
>
>> 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

>
> But the one parity bit won't DC balance the other eight bits. You'd need
> eight bits to DC balance an arbitrary 8-bit pattern.

Duh!

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

Jerry Avins, Apr 6, 2009
13. CBFalconerGuest

Mark Borgerson wrote:
> 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.

Why all that trouble? I am assuming constant bit speed, as in the
most normal RS232 transmissions. Simply differentiate the signal,
and transmit that. That way each 0..1 transition is balanced by a
1..0 transition. Considering the stop and start bits means that
each byte signal is a balanced set of 0..1 and 1..0 transitions.
The receiver just sets/resets a single bit with the differentiated
signals.

You can avoid most high speed problems over the transmission line
by shaping the differentiated pulses into 1/2 bit period pulses of
the appropriate sign.

input __------______------------------____________------____

din/dt __|_____ _____|_________________ ___________|_____ ___
| | |
shaped __---___ ___---_______________ _________---___ _
--- --- ---
Bits start 0 1 1 1 0 0 1 stop

Note that the asynchronous operation of RS232 is preserved.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

CBFalconer, Apr 6, 2009
14. Vladimir VassilevskyGuest

CBFalconer wrote:
> Mark Borgerson wrote:
>
>> says...
>>
>>>>Vladimir Vassilevsky wrote:
>>>>
>>>>
>>>>>We have to transmit RS-232 by the AC coupled line.

> Simply differentiate the signal, and transmit that.

What if the input is 0xFF or 0x00 ?

> That way each 0..1 transition is balanced by a
> 1..0 transition. Considering the stop and start bits means that
> each byte signal is a balanced set of 0..1 and 1..0 transitions.
> The receiver just sets/resets a single bit with the differentiated
> signals.

There is a crude way for recovering the unbalanced binary signal from
the AC channel using a Schmidt trigger in the receiver. If the
hysteresis is set properly, the signal can be recovered by 0/1 and 1/0
transitions. However this is very unreliable and prone to noise.

> You can avoid most high speed problems over the transmission line
> by shaping the differentiated pulses into 1/2 bit period pulses of
> the appropriate sign.

You can make all kinds of diffent things but a simple UART is something
that is always available and already there.

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

Vladimir Vassilevsky, Apr 7, 2009
15. CBFalconerGuest

Vladimir Vassilevsky wrote:
> CBFalconer wrote:
>> Mark Borgerson wrote:
>>> says...
>>>

.... snip ...
>>>>
>>>>> We have to transmit RS-232 by the AC coupled line.

>
>> Simply differentiate the signal, and transmit that.

>
> What if the input is 0xFF or 0x00 ?

Look at the diagram (which you snipped). Each character is
separated by a quiet period, minimum length the stop-bit. So the
transitions always match.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

CBFalconer, Apr 7, 2009
16. Spehro PefhanyGuest

On Mon, 06 Apr 2009 13:46:46 -0400, Spehro Pefhany
<> wrote:

>On Mon, 6 Apr 2009 07:55:29 -0700, 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.
>>>
>>>

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

>
>That scheme essentially groups bits into pairs. Not surprisingly, the
>more bits you group together, the higher the efficiency:-
>
>2/4 => 0.50
>6/16 => 0.64
>20/64 => 0.72
>70/256 => 0.77
>252/1024 => 0.80
>924/4096 => 0.82
>3432/16384 => 0.84
>12870/65536 => 0.85
>48620/262144 => 0.86
>etc.
>

In general, for a word with 2n bits and the same number of 0's and
1's, there are (2*n)!/(n!*n!) possible numbers, so you can approach
efficiency of 1 arbitrarily closely. An 2048-byte number should only
need one extra byte to be DC balanced, when optimally mapped.

Of course a LUT would not be practical for this, in most cases ;-)

Best regards,
Spehro Pefhany
--
"it's the network..." "The Journey is the reward"
Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog Info for designers: http://www.speff.com

Spehro Pefhany, Apr 7, 2009
17. Thad SmithGuest

Vladimir Vassilevsky wrote:

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

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.

--
Thad

Thad Smith, Apr 10, 2009
18. glen herrmannsfeldtGuest

In comp.dsp Thad Smith <> wrote:

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

That is also what some forms of ethernet do.

-- glen

glen herrmannsfeldt, Apr 10, 2009
19. Guest

Vladimir Vassilevsky ha escrito:
> 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?

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

, Apr 15, 2009
20. RockyGuest

On Apr 15, 12:40 pm, wrote:
> Vladimir Vassilevsky ha escrito:
>
> > 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?

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

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.

Rocky, Apr 15, 2009

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.