Wed Jan 11, 2017 5:52 pm
I spent some time on this and got my head around it finally. I would
like to point out that the set of gray codes typically used are
reflected binary codes and are just one type of gray codes. They are
easy to work with in conversion routines.
Converting binary to gray only requires searching for all changes of bit
value in adjacent bits. In the binary word a bit pair where the value
is different, the rightmost bit in the gray word will be a '1'. So the
logic is just an XOR gate for each output bit other than the msb which
doesn't change. If you are going to use the gray code to increment or
decrement directly, having the parity bit will simplify the logic
greatly so this is also calculated easily by inverting the binary lsb.
The gray to binary conversion is similar, but requires the calculation
of the msb first which is then used to XOR with the next gray bit to
obtain that binary bit. This is just the reverse of the process to
create the gray word from the binary word. However, this results in a
chain calculation from msb to lsb.
If a gray word needs to be incremented or decremented the process is
also not complex. If you consider how a gray code is generated from
binary and how incrementing works for binary, you will see the only
change in a gray word is defined by either the lsb changing or the bit
defined by the ripple carry will change. When the parity of the gray
word is even, the lsb of the binary word is zero and so the lsb in the
binary word will change from a zero to a one and the *only* bit to
change. So likewise, the lsb in the gray word will change. Otherwise,
when the binary lsb is a one (odd parity in the gray word) the ones are
followed and the first zero bit will become a one with all the lower
bits becoming zeros. Looking at the binary to gray conversion rules
you'll see the bit that then changes is the first bit to the left of the
series of one bits or in the gray word the bit to the left of the first
one bit from the lsb end.
This sets up a chain of checking for all zeros from the lsb up in the
gray word. This is simple logic and potentially can make use of a
ripple carry chain. Decrementing the gray code is exactly the same, but
the polarity of the parity bit is inverted. A gray up/down counter only
requires the parity be inverted by the direction bit.
When these algorithms were synthesized using Lattice Diamond/Synplify
Pro for an N bit word N-1 LUTs were used for the two conversions, binary
to gray and gray to binary. For incrementing or decrementing it used 22
LUTs for a 16 bit counter, 16 for the final calculation of each bit and
six chained LUTs to help calculate the cascade of zeros. Adding a
signal to control the up/down mode increases the LUT count by one to 23.
A funny thing though. When I modified the logic so instead of passing
the signals in and out of the chip to a counter that simply starts at
zeero and counts up/down, the logic blew up to using 51 LUTs. No change
to the logic, simply routing the output of the FF back to the input to
the incrementer. If I set the speed target to just 10 MHz the LUT
counts dropped back too the above numbers. The speed did drop off a lot
from over 200 MHz to a bit over 100 MHz. I suppose the big increase in
LUTs got rid of the chain calculation.
I wonder what it takes to get the tools to use a carry chain?