h1

Puzzle #5 – Binary-Gray

June 12, 2007

Assuming 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

13 comments

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


  2. I 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?


  3. Didn’t you forget to tell what n is?
    :-))


  4. The answer is irrelevant of n …


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


  6. Your 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!


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


  8. I 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).
    You 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…


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


  10. Easy 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!


    • a small error: the MSB only toggle once if you go through the 2^n counts. so total toggles of binary = 2*2^n – 1


  11. correct solution!
    in 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…


  12. […] 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 […]



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: