Go Down

### Topic: Convert ring counter to binary (Read 1 time)previous topic - next topic

#### privateRob

##### Jul 19, 2012, 10:53 pmLast Edit: Jul 20, 2012, 01:17 pm by privateRob Reason: 1
Hi everbody!

I just wanted to know if there is a single hardware component or simple hardware solution to convert a ring counter value to a binary value. Here is an example:

Input -> Output
0001 -> 00
0010 -> 01
0100 -> 10
1000 -> 11

My project uses much higher input values (Input is 16bits, therefore Output must be 4bits). OR'ing the right bits and link them together would be a solution in the example (only 2 ORs needed) but not in my project (32 ORs needed = much to connect).

Thanks for helping, Rob!

#### Grumpy_Mike

#1
##### Jul 19, 2012, 11:24 pm
The input is not a binary count, it is called a ring count.
To convert shift the input one place to the right and keep doing it until the number is zero. Then the number of shifts you had to make is the binary value.

#### MichaelMeissner

#2
##### Jul 19, 2012, 11:45 pmLast Edit: Jul 20, 2012, 12:54 am by MichaelMeissner Reason: 1
GCC/G++ has a builtin function to count the number of leading zeros of an int (__builtin_clz), and long/long long versions (__builtin_clzl and __builtin_clzll).  In looking at the compiler code, it looks like __builtin_clz and friends calls into the library, and there they have assembly versions of the routines.

So you would want something like:

Code: [Select]
`n = 16 - __builtin_clz (x);`

Now, if you ever plan to move your code to a different machine, such as an ARM, you probably should use this instead:

Code: [Select]
`n = (sizeof (int) * 8) - __builtin_clz (x);`

As I said, AVR doesn't seem to have an instruction built in that does count leading zero in one operation, but other machines do, such as x86, powerpc, and arm5.  Given the library routine is written in assembler, it is probably faster than the shift and loop function.

#### privateRob

#3
##### Jul 20, 2012, 01:14 pm
Stupid me!
I forgot to say that I'm looking for a hardware solution. Best without any clock cycles.

... and thanks for the help so far!

#### Grumpy_Mike

#4
##### Jul 20, 2012, 01:44 pm
You will ave to post the schematic of what you have before we can consider a hardware solution.

#### MichaelMeissner

#5
##### Jul 20, 2012, 02:05 pm

Stupid me!
I forgot to say that I'm looking for a hardware solution. Best without any clock cycles.

... and thanks for the help so far!

My sense is for a lot of the computers that have a count leading zeros instruction, internally the processor does a combination of if and loop type operations.  You can throw more logic at the problem, depending on the usual cost/benefit analysis.  On the server powerpc's that I deal with for work, the CNTLZ instruction is a 2 cycle instruction, while the normal integer operations are 1 cycle.

#### Grumpy_Mike

#6
##### Jul 20, 2012, 02:12 pm
Quote
My sense is for a lot of the computers that have a count leading zeros instruction

No they don't, the instruction you referanced is an increment or decrement with a branch if the result is less than zero.
I know of no instructions that count zeros in a word.

#### Grumpy_Mike

#7
##### Jul 20, 2012, 02:18 pm
If all you have is the 16 ring counter inputs, you can use a pair of 74LS348 priority Encoders.

#### privateRob

#8
##### Jul 20, 2012, 09:42 pm

If all you have is the 16 ring counter inputs, you can use a pair of 74LS348 priority Encoders.

Yes, yes, YES! Thank you very much!

#### Gorgus

#9
##### Jul 25, 2012, 09:26 pm
...or one 74LS150...?

#### Grumpy_Mike

#10
##### Jul 25, 2012, 11:26 pm
Quote
or one 74LS150...

No that is a multiplexer chip not a priority Encoder. The two are totally different things.

#### Gorgus

#11
##### Jul 26, 2012, 07:33 am
After one more readthrough I see what you mean. Sorry.

Go Up

Please enter a valid email to subscribe

To complete the subscription, please click the link in the email we just sent you.

Thank you for subscribing!

Arduino
via Egeo 16
Torino, 10131
Italy