## Puzzle #5 – Binary-Gray

June 12, 2007Assuming you have an n-bit binary counter, made of n identical cascaded cells, which hold the corresponding bit value. Each of the binary cells dissipates a power of P units only when it toggles.

You also have an n-bit Gray counter made of n cascaded cells, which dissipates 3P units of power per cell when it toggles.

You now let the counters run through an entire cycle (2^n different values) until they return to their starting position. Which counter burns more power?

Advertisements

obvious binary counter burns more power.gary counter changes 1 bit change in that pattern but binary all bits pattern r changing..so more toggle more power.

by Kubendr June 13, 2007 at 11:38 amI don’t want to give the answer so quickly, but did you consider the ratio of toggling between the counters to the overhead per bit for power consumption for the gray cell?

by nirdahan June 13, 2007 at 12:25 pmDidn’t you forget to tell what n is?

by edoardo June 14, 2007 at 5:47 am:-))

The answer is irrelevant of n …

by nirdahan June 14, 2007 at 7:20 amGray Counter consumes more power.

Assume 4 bit counter.

Gray Counter takes (3P+6P+12P+24P) = 45P

Binary Counter takes(1P+3P+7P+15P) = 26P

You can list the Truth Table for both counters and list down, how many times each bit toggles.

by Santhosh K,R June 27, 2007 at 7:12 pmYour end result is right but the numbers are wrong.

The 4 bit Gray counter will have by definition 2^4 bits toggle and thus will consume 3*16=48 units of power.

The Binary counter will toggle 30 times through a complete counting cycle and thus will consume 30 units of power.

can you prove why, given the assumptions in the puzzle, the Gray counter will always consume more power? regardless of the number of bits!

by nirdahan June 27, 2007 at 9:32 pmIn binary encoding, for ‘n’ bit wide counter, number of toggles will be around 2*2^n+(n!) [Approximately]. So it is slightly more than two times the gray counter togglings. Given the Gray counter consuming three times more power – Gray counter will always consume one third more power than binary counter[approximate].

by ASHWATH BL June 28, 2007 at 9:00 amI think you are way off regarding the amount of toggling in a binary counter. n! grows by far faster (it actually explodes) than 2*2^n = 2^(n+1).

by nirdahan June 28, 2007 at 2:54 pmYou are on the right track – try to identify precisely how much does a binary counter toggle through a single cycle. You could basically list the values for 1 to 6 bits, it will give you an idea if not the general rule exactly.

If you are into sum of a series calculation you could get the precise info by doing some maths…

4 bit binary code will take 30P pwer because

for counter from 0000 to 1111 it takes (1P+3P+7P+15P)

and counter resets from 1111 to 0000 so 4P

so totally 26P+4P

by Santhosh K.R June 29, 2007 at 4:24 amEasy enough …

Gray counter: Toggles 1-bit and there are 2^n counts to go through. So total power for gray = 3P * (2^n)

Binary counter: Bit-0 toggles every count. Bit-1 toggles half-rate, bit-2 toggles quarter-rate and so on. So total power = total toggles * P

total toggles = (2^n)*(1 + (1/2) + (1/4) + … + (1/(2^n-1)))

total toggles = 2^n * ( 1 * (1 – 1/(2^n))/(1/2) ) (using formula for geometric progression sum).

total toggles = 2*(2^n – 1)

total_binary_power = 2P * (2^n – 1)

total_gray_power = 3P * 2^n

So total_binary_power is ALWAYS smaller than total gray power regardless of value of n!

by Sriram S July 2, 2007 at 5:51 pma small error: the MSB only toggle once if you go through the 2^n counts. so total toggles of binary = 2*2^n – 1

by zhuoli October 10, 2012 at 5:50 amcorrect solution!

by Nir Dahan July 3, 2007 at 9:52 amin this specific case the binary counter is cheaper regarding power consumption.

This puzzle was inspired by a “true story” btw, maybe I will write about it sometime…

[…] Layout Considerations Puzzle #5 – Binary-Gray counters – solution July 5th, 2007 The binary-Gray puzzle from last week generated some flow of comments and emails. Basically, the important point to notice […]

by Puzzle #5 - Binary-Gray counters - solution « Adventures in ASIC Digital Design July 5, 2007 at 1:50 pm