A Puzzle for Today

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.

Duh!

Jerry

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

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]: 
            Try the download section.

What if the input is 0xFF or 0x00 ?

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

... snip ...

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]: 
            Try the download section.

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"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com

Le Sun, 05 Apr 2009 18:36:35 -0500, Tim Wescott a écrit :

Is the % operator (modulus) of the C language can do the trick ?

HBV

First, the underlying operation is a divide, which I ruled out, and second the % operator only works for data that is within the word size of the machine.

Good thinking, though.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

oooh i see, may be you're focused on performance/size code to achieve this ?

A very large number ... what is a very large number ? (long long int) type (64bits) seems as large as a universe for me :-)

Habib

No, it's a _puzzle_.

Name a number of bytes -- it's at least one longer than that.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

Not possible. The number can only be as large as (N-X) where N is the memory available and X is the amount the machine needs to run the algorithm.

A search for "divisibility 17" will yeld a number of algorithms. The all seem to require either recursive or repetitive operations and=20 operations on the last digit of a number in decimal representation. I don't know if the algorithms can be rewritten to work on binary numbers.

Mark Borgerson

Possible, if you don't mind not storing the number. It can come in as a stream, go out as a stream, and the divisibility by 17 can be determined at any time that the number is declared "done".

Read the thread.

You haven't read the rest of the thread, then.

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

Le Wed, 08 Apr 2009 20:16:36 -0700, Tim Wescott a écrit :

Ok. 17 is a prime number so google find out for me the divibility test by

17 :

Unfortunately this wiki page is in French may be you could find the same in English.

Habib

This is a puzzle for embedded engineers. Where do you get the '%' operator from if you're coding for a Z80? A PIC? A 8051? Don't say "I let the compiler do it". Someone has to make the compiler.

Even if you have a 32-bit CPU with divide instruction, testing 64 bits for divisibility by 17 requires a little thinking.

Stefan

he

e y

ze

=20

=20

That doesn't match the original puzzle, then. "You have a Very Large Number, expressed as an binary integer, in the=20 memory of a machine that allows for byte-wide operations. For some=20 unfathomable reason, you need to determine if this number is evenly=20 divisible by 17."

I answered the question about the number of bytes based on the memmory of the machine as originally specified. If the puzzle has changed, since your original post, I missed that part.

I caught the beginning, but may have missed a few in between. I did catch and respond to the switch to DC-balanced transmissions, though.

I have now, and you didn't change the rules to allow streamed=20 input and output until now.

Mark Borgerson

You sum all the bytes mod 256 incrementing the sum on any overflow.

If the high and low nibbles of the result are equal the number was divisible by 17.

beats me.

In comp.dsp Stefan Reuther wrote: (snip)

A little, but not so much. A little more if you only have a signed 32 bit divide. Modulo arithmetic problems seem to be a favorite for math contests (middle school and high school level, at least).

-- glen

Why do you assume that the number needs to be in RAM?

I described a simple method using HEX digits that translates to binary with only a shift in viewpoint. "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."

Jerry

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

he

e y

ze

I didn't. I carefully chose the word 'memory'. That could include RAM, ROM, even external memory such as virtual memory on disk or some other storage medium.

As I said, the algorithms seems to involve iteration. In the case of your algorithm, it seems to also require enough memory for both the number and the sum---which could be arbitrarily large.

Mark Borgerson