h1

Puzzle #5 – Binary-Gray counters – solution

July 5, 2007

The binary-Gray puzzle from last week generated some flow of comments and emails.
Basically, the important point to notice is the amount each counter toggles while going through a complete counting cycle.

For Gray coded counter, by definition only one bit changes at a time. Therefore, for an n stage counter we get 2^n toggling events for a complete counting cycle.

For binary coded n-bit counter, we have 2^(n+1)-2 toggling events for a complete counting cycle. you could verify this by

  1. Taking my word for it (don’t – check it yourself)
  2. Writing down manually the results for a few simple cases and convince yourself it is so
  3. Calculate the general case, but you have to remember something about how to calculate the sum of a simple series (best way)

Anyways, given the above assumptions and the fact that per bit the Gray counter consumes 3 times more power (2 times more would also just work, but the difference would be a constant), the Gray counter will always consume more power.
3*2^n > 2^(n+1) – 2

Advertisements

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: