Re: [math-fun] Maximum orbit of an n-bit register with monotonic update rule
I don't know if this is relevant, but so-called 'Grey codes' have the property that they change only 1 bit for each 'increment'. I seem to recall that Grey codes can count through all 2^N states, although not in the usual order. Grey codes have another type of 'monotonic' property -- that, since only one bit changes on each increment, you don't need a clock to know when to sample the output of a 'counter' -- the change in any bit means that the output is available and stable. So these codes are 'self-clocking'.
----- Original Message ----- From: "Henry Baker" <hbaker1@pipeline.com> To: "Allan C. Wechsler" <acw@alum.mit.edu> Cc: <math-fun@mailman.xmission.com> Sent: Friday, November 29, 2002 9:32 PM Subject: Re: [math-fun] Maximum orbit of an n-bit register with monotonic update rule
I don't know if this is relevant, but so-called 'Grey codes' have the property that they change only 1 bit for each 'increment'. I seem to recall that Grey codes can count through all 2^N states, although not in the usual order.
Grey codes have another type of 'monotonic' property -- that, since only one bit changes on each increment, you don't need a clock to know when to sample the output of a 'counter' -- the change in any bit means that the output is available and stable. So these codes are 'self-clocking'.
They're "Gray Codes" but not named after me. They do go through all 2^N states, and there is a simple algorithm for conversion to/from binary. They are commonly used in shaft and position encoders where it is important not to have ambiguity about when the code changes, or to have false intermediate states. (Same as HB's last paragraph above.) They have a reflection quality which becomes readily apparent on playing with them. It's almost a self- similarity. 000 001 011 010 110 100 101 111 etc. Steve Gray
participants (2)
-
Henry Baker -
Steve Gray