Go Down

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

privateRob

Jul 19, 2012, 10:53 pm Last 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!

edit: Corrected thread.

Grumpy_Mike

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

Stupid me!  :smiley-red:
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

You will ave to post the schematic of what you have before we can consider a hardware solution.

MichaelMeissner


Stupid me!  :smiley-red:
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

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

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

privateRob


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! :)


Grumpy_Mike

Quote
or one 74LS150...

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

Gorgus

After one more readthrough I see what you mean. Sorry.

Go Up