Gray Code

[rickman]

I was reading up on Gray codes and figured out a fairly simple algorithm
for counting up or down with Gray codes directly rather than using a
binary counter which is converted to Gray code. It has not been
extensively tested. I don't think it will work for vectors declared
with a "to" range rather than a "downto" range. I should have used
'left and 'right instead of 'high and 'low, but I don't know how to
construct a loop that goes in either direction. I'll need to dig around
to see how that might be done.

I got the idea from a verbal description of a Gray code that defined the
bit to change as the least significant bit that gives even parity with
all the higher bits. They didn't say it just like that, but once I
thought about it I realized that was what they should have said.
Counting down is the same rule, but odd parity. I didn't synthesize it
to see how complex the logic is, but I don't think it should be too bad.

Here is the code. Any suggestions are welcome.

Function CalcGray (cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrHigh : natural := cntr'high;
variable CntrLow : natural := cntr'low;
variable Result : unsigned (cntr'range) := cntr;
variable ParityWord : unsigned (CntrHigh downto CntrLow)
:= (others => '0');
begin
ParityWord(CntrHigh) := Result(CntrHigh);
for i in CntrHigh-1 downto CntrLow loop
ParityWord(i) := ParityWord(i+1) xor Result(i);
end loop;
for i in CntrLow to CntrHigh loop
if ((UpDwn = not ParityWord(i)) or (i = CntrHigh)) then
Result(i) := not Result(i);
exit;
end if;
end loop;
return Result;
end CalcGray;

Function NextGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '1');
end NextGray;

Function PrevGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '0');
end PrevGray;

--

Rick C

 

[rickman]

On 6/13/2016 1:36 AM, rickman wrote:

I was reading up on Gray codes and figured out a fairly simple algorithm
for counting up or down with Gray codes directly rather than using a
binary counter which is converted to Gray code. It has not been
extensively tested. I don't think it will work for vectors declared
with a "to" range rather than a "downto" range. I should have used
'left and 'right instead of 'high and 'low, but I don't know how to
construct a loop that goes in either direction. I'll need to dig around
to see how that might be done.

I got the idea from a verbal description of a Gray code that defined the
bit to change as the least significant bit that gives even parity with
all the higher bits. They didn't say it just like that, but once I
thought about it I realized that was what they should have said.
Counting down is the same rule, but odd parity. I didn't synthesize it
to see how complex the logic is, but I don't think it should be too bad.

Here is the code. Any suggestions are welcome.

Function CalcGray (cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrHigh : natural := cntr'high;
variable CntrLow : natural := cntr'low;
variable Result : unsigned (cntr'range) := cntr;
variable ParityWord : unsigned (CntrHigh downto CntrLow)
:= (others => '0');
begin
ParityWord(CntrHigh) := Result(CntrHigh);
for i in CntrHigh-1 downto CntrLow loop
ParityWord(i) := ParityWord(i+1) xor Result(i);
end loop;
for i in CntrLow to CntrHigh loop
if ((UpDwn = not ParityWord(i)) or (i = CntrHigh)) then
Result(i) := not Result(i);
exit;
end if;
end loop;
return Result;
end CalcGray;

Function NextGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '1');
end NextGray;

Function PrevGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '0');
end PrevGray;

Here is an improved version of the main routine that works for ascending
or descending ranges of the input signal.

Function CalcGray (Cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrLeft : natural := Cntr'LEFT;
variable Result : unsigned (cntr'RANGE) := cntr;
variable ParityWord : unsigned (Cntr'RANGE);
variable PrevParity : std_logic := '0';
begin
for i in ParityWord'RANGE loop
ParityWord(i) := PrevParity xor Result(i);
PrevParity := ParityWord(i);
end loop;
for i in Result'REVERSE_RANGE loop
if ((i = CntrLeft) or (UpDwn /= ParityWord(i))) then
Result(i) := not Result(i); -- found the bit to toggle
exit;
end if;
end loop;
return Result;
end CalcGray;

--

Rick C

 

[KJ]

On Monday, June 13, 2016 at 1:36:25 AM UTC-4, rickman wrote:

Here is the code. Any suggestions are welcome.

Here is a relevant link that might be similar to what you're describing.
https://groups.google.com/forum/#!topic/comp.lang.vhdl/Zqq03Hj_N7k

I don't remember if I benchmarked it relative to converting/unconverting but I'll take a look.

Kevin Jennings

 

[rickman]

On 6/13/2016 8:18 AM, KJ wrote:

On Monday, June 13, 2016 at 1:36:25 AM UTC-4, rickman wrote:

Here is the code. Any suggestions are welcome.

Here is a relevant link that might be similar to what you're describing.
https://groups.google.com/forum/#!topic/comp.lang.vhdl/Zqq03Hj_N7k

I don't remember if I benchmarked it relative to converting/unconverting but I'll take a look.

Interesting. Toward the end of that thread I see mention of two ripple
chains, "one chain going up, the other down". This sounds like a
similar method as my approach. The parity is calculated from the top
down for each bit while a lower bit being flipped disables all upper
bits from being considered.

Rather than enter equations, my approach is to use loops to describe
these chains. It seems to result in a much simpler description.

I have used Altera devices enough to know they contain a chain of gates
which may be a bit faster than using the 4 LUTs for the disable chain.
This would be similar to the carry chain in adders. I don't know if
this chain of gates sill appears in the more recent parts.

I have a file which I think is from Altera with an extra LSB in the
counter used to control the counting in the otherwise LSB of the
counter. Then the rule is to increment the least significant bit where
the bits below are of the form "100...". The extended counter is
initialized to "0..01". This would seem to only require one chain
direction plus the extra bit in the register. The code is pretty clean
other than the "fixup" needed to make the msb work properly. This is
likely an optimal solution.

Choose your poison.

--

Rick C

 

[rickman]

On 6/13/2016 3:31 AM, rickman wrote:

On 6/13/2016 1:36 AM, rickman wrote:
I was reading up on Gray codes and figured out a fairly simple algorithm
for counting up or down with Gray codes directly rather than using a
binary counter which is converted to Gray code. It has not been
extensively tested. I don't think it will work for vectors declared
with a "to" range rather than a "downto" range. I should have used
'left and 'right instead of 'high and 'low, but I don't know how to
construct a loop that goes in either direction. I'll need to dig around
to see how that might be done.

I got the idea from a verbal description of a Gray code that defined the
bit to change as the least significant bit that gives even parity with
all the higher bits. They didn't say it just like that, but once I
thought about it I realized that was what they should have said.
Counting down is the same rule, but odd parity. I didn't synthesize it
to see how complex the logic is, but I don't think it should be too bad.

Here is the code. Any suggestions are welcome.

Function CalcGray (cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrHigh : natural := cntr'high;
variable CntrLow : natural := cntr'low;
variable Result : unsigned (cntr'range) := cntr;
variable ParityWord : unsigned (CntrHigh downto CntrLow)
:= (others => '0');
begin
ParityWord(CntrHigh) := Result(CntrHigh);
for i in CntrHigh-1 downto CntrLow loop
ParityWord(i) := ParityWord(i+1) xor Result(i);
end loop;
for i in CntrLow to CntrHigh loop
if ((UpDwn = not ParityWord(i)) or (i = CntrHigh)) then
Result(i) := not Result(i);
exit;
end if;
end loop;
return Result;
end CalcGray;

Function NextGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '1');
end NextGray;

Function PrevGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '0');
end PrevGray;

Here is an improved version of the main routine that works for ascending
or descending ranges of the input signal.

Function CalcGray (Cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrLeft : natural := Cntr'LEFT;
variable Result : unsigned (cntr'RANGE) := cntr;
variable ParityWord : unsigned (Cntr'RANGE);
variable PrevParity : std_logic := '0';
begin
for i in ParityWord'RANGE loop
ParityWord(i) := PrevParity xor Result(i);
PrevParity := ParityWord(i);
end loop;
for i in Result'REVERSE_RANGE loop
if ((i = CntrLeft) or (UpDwn /= ParityWord(i))) then
Result(i) := not Result(i); -- found the bit to toggle
exit;
end if;
end loop;
return Result;
end CalcGray;

Yet another version based on the Altera example code I found somewhere.
They added an lsb to the gray counter register and only need one ripple
chain linking upward in the calculation. When I synthesized it I didn't
see much difference in speed, both reaching a bit over 200 MHz in a not
so fast XP3C-5 with a 16 bit register. I wonder if speed could be
improved by using a carry chain? It would likely take some very special
code to infer that. Sometimes a small piece of code is not estimated
well in an otherwise empty part. The tool can pick a poor pin placement
that requires a long route which dominates the path timings. I didn't
check that.

The component count was different. The previous CalcGray code used 63
LUT4 elements and 16 FFs. That's nearly 4 LUT4s per FF. I expect this
ratio goes up with register length. The "fast" version used 45 LUT4s
and 22 FFs. I would guess some of the registers are being duplicated to
optimize performance, but I'm not sure. The simulation seems to give
the right results so I don't think there is an error. I did not test
this version with bit reversed parameters. Here is the "fast" code.

Function CalcGray (Cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrLeft : natural := Cntr'LEFT;
variable Result : unsigned (cntr'RANGE) := cntr;
variable one_found : std_logic;
variable ones_below : std_logic;
begin

for i in Result'REVERSE_RANGE loop
if (i = Result'right) then
ones_below := '0';
one_found := UpDwn xor Result(0);
Result(0) := not Result(0);
elsif (i /= CntrLeft) then
Result(i) := Result(i) xor (one_found and not ones_below);
ones_below := ones_below or one_found;
one_found := Result(i);
else
one_found := Result(i) or one_found;
Result(i) := Result(i) xor (one_found and not ones_below);
end if;
end loop;
return Result;
end CalcGray;

--

Rick C

 

[rickman]

On 6/13/2016 8:22 PM, rickman wrote:

On 6/13/2016 3:31 AM, rickman wrote:
On 6/13/2016 1:36 AM, rickman wrote:
I was reading up on Gray codes and figured out a fairly simple algorithm
for counting up or down with Gray codes directly rather than using a
binary counter which is converted to Gray code. It has not been
extensively tested. I don't think it will work for vectors declared
with a "to" range rather than a "downto" range. I should have used
'left and 'right instead of 'high and 'low, but I don't know how to
construct a loop that goes in either direction. I'll need to dig around
to see how that might be done.

I got the idea from a verbal description of a Gray code that defined the
bit to change as the least significant bit that gives even parity with
all the higher bits. They didn't say it just like that, but once I
thought about it I realized that was what they should have said.
Counting down is the same rule, but odd parity. I didn't synthesize it
to see how complex the logic is, but I don't think it should be too bad.

Here is the code. Any suggestions are welcome.

Function CalcGray (cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrHigh : natural := cntr'high;
variable CntrLow : natural := cntr'low;
variable Result : unsigned (cntr'range) := cntr;
variable ParityWord : unsigned (CntrHigh downto CntrLow)
:= (others => '0');
begin
ParityWord(CntrHigh) := Result(CntrHigh);
for i in CntrHigh-1 downto CntrLow loop
ParityWord(i) := ParityWord(i+1) xor Result(i);
end loop;
for i in CntrLow to CntrHigh loop
if ((UpDwn = not ParityWord(i)) or (i = CntrHigh)) then
Result(i) := not Result(i);
exit;
end if;
end loop;
return Result;
end CalcGray;

Function NextGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '1');
end NextGray;

Function PrevGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '0');
end PrevGray;

Here is an improved version of the main routine that works for ascending
or descending ranges of the input signal.

Function CalcGray (Cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrLeft : natural := Cntr'LEFT;
variable Result : unsigned (cntr'RANGE) := cntr;
variable ParityWord : unsigned (Cntr'RANGE);
variable PrevParity : std_logic := '0';
begin
for i in ParityWord'RANGE loop
ParityWord(i) := PrevParity xor Result(i);
PrevParity := ParityWord(i);
end loop;
for i in Result'REVERSE_RANGE loop
if ((i = CntrLeft) or (UpDwn /= ParityWord(i))) then
Result(i) := not Result(i); -- found the bit to toggle
exit;
end if;
end loop;
return Result;
end CalcGray;

Yet another version based on the Altera example code I found somewhere.
They added an lsb to the gray counter register and only need one ripple
chain linking upward in the calculation. When I synthesized it I didn't
see much difference in speed, both reaching a bit over 200 MHz in a not
so fast XP3C-5 with a 16 bit register. I wonder if speed could be
improved by using a carry chain? It would likely take some very special
code to infer that. Sometimes a small piece of code is not estimated
well in an otherwise empty part. The tool can pick a poor pin placement
that requires a long route which dominates the path timings. I didn't
check that.

The component count was different. The previous CalcGray code used 63
LUT4 elements and 16 FFs. That's nearly 4 LUT4s per FF. I expect this
ratio goes up with register length. The "fast" version used 45 LUT4s
and 22 FFs. I would guess some of the registers are being duplicated to
optimize performance, but I'm not sure. The simulation seems to give
the right results so I don't think there is an error. I did not test
this version with bit reversed parameters. Here is the "fast" code.

Function CalcGray (Cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrLeft : natural := Cntr'LEFT;
variable Result : unsigned (cntr'RANGE) := cntr;
variable one_found : std_logic;
variable ones_below : std_logic;
begin

for i in Result'REVERSE_RANGE loop
if (i = Result'right) then
ones_below := '0';
one_found := UpDwn xor Result(0);
Result(0) := not Result(0);
elsif (i /= CntrLeft) then
Result(i) := Result(i) xor (one_found and not ones_below);
ones_below := ones_below or one_found;
one_found := Result(i);
else
one_found := Result(i) or one_found;
Result(i) := Result(i) xor (one_found and not ones_below);
end if;
end loop;
return Result;
end CalcGray;

If anyone cares about the reversed range parameters (to instead of
downto) change the two assignments using Result(0) to use Result(i).

one_found := UpDwn xor Result(i);
Result(i) := not Result(i);


--

Rick C

 

[Ilya Kalistru]

On Monday, June 13, 2016 at 10:31:06 AM UTC+3, rickman wrote:

On 6/13/2016 1:36 AM, rickman wrote:
I was reading up on Gray codes and figured out a fairly simple algorithm
for counting up or down with Gray codes directly rather than using a
binary counter which is converted to Gray code. It has not been
extensively tested. I don't think it will work for vectors declared
with a "to" range rather than a "downto" range. I should have used
'left and 'right instead of 'high and 'low, but I don't know how to
construct a loop that goes in either direction. I'll need to dig around
to see how that might be done.

I got the idea from a verbal description of a Gray code that defined the
bit to change as the least significant bit that gives even parity with
all the higher bits. They didn't say it just like that, but once I
thought about it I realized that was what they should have said.
Counting down is the same rule, but odd parity. I didn't synthesize it
to see how complex the logic is, but I don't think it should be too bad.

Here is the code. Any suggestions are welcome.

Function CalcGray (cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrHigh : natural := cntr'high;
variable CntrLow : natural := cntr'low;
variable Result : unsigned (cntr'range) := cntr;
variable ParityWord : unsigned (CntrHigh downto CntrLow)
:= (others => '0');
begin
ParityWord(CntrHigh) := Result(CntrHigh);
for i in CntrHigh-1 downto CntrLow loop
ParityWord(i) := ParityWord(i+1) xor Result(i);
end loop;
for i in CntrLow to CntrHigh loop
if ((UpDwn = not ParityWord(i)) or (i = CntrHigh)) then
Result(i) := not Result(i);
exit;
end if;
end loop;
return Result;
end CalcGray;

Function NextGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '1');
end NextGray;

Function PrevGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '0');
end PrevGray;

Here is an improved version of the main routine that works for ascending
or descending ranges of the input signal.

Function CalcGray (Cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrLeft : natural := Cntr'LEFT;
variable Result : unsigned (cntr'RANGE) := cntr;
variable ParityWord : unsigned (Cntr'RANGE);
variable PrevParity : std_logic := '0';
begin
for i in ParityWord'RANGE loop
ParityWord(i) := PrevParity xor Result(i);
PrevParity := ParityWord(i);
end loop;
for i in Result'REVERSE_RANGE loop
if ((i = CntrLeft) or (UpDwn /= ParityWord(i))) then
Result(i) := not Result(i); -- found the bit to toggle
exit;
end if;
end loop;
return Result;
end CalcGray;

--

Rick C

I've always used the simplest possible way to do that:

B <= Bin2Gray(Gray2Bin(A) + 1);

And I've never have had any performance problems with it. Vivado manage to optimize it quite well and employs carry chain for that.

And it's look like it's even better than Rick's sophisticated method:
http://imgur.com/Hu2MuMr

 

[rickman]

On 8/5/2016 3:11 PM, Ilya Kalistru wrote:

On Monday, June 13, 2016 at 10:31:06 AM UTC+3, rickman wrote:
On 6/13/2016 1:36 AM, rickman wrote:
I was reading up on Gray codes and figured out a fairly simple algorithm
for counting up or down with Gray codes directly rather than using a
binary counter which is converted to Gray code. It has not been
extensively tested. I don't think it will work for vectors declared
with a "to" range rather than a "downto" range. I should have used
'left and 'right instead of 'high and 'low, but I don't know how to
construct a loop that goes in either direction. I'll need to dig around
to see how that might be done.

I got the idea from a verbal description of a Gray code that defined the
bit to change as the least significant bit that gives even parity with
all the higher bits. They didn't say it just like that, but once I
thought about it I realized that was what they should have said.
Counting down is the same rule, but odd parity. I didn't synthesize it
to see how complex the logic is, but I don't think it should be too bad.

Here is the code. Any suggestions are welcome.

Function CalcGray (cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrHigh : natural := cntr'high;
variable CntrLow : natural := cntr'low;
variable Result : unsigned (cntr'range) := cntr;
variable ParityWord : unsigned (CntrHigh downto CntrLow)
:= (others => '0');
begin
ParityWord(CntrHigh) := Result(CntrHigh);
for i in CntrHigh-1 downto CntrLow loop
ParityWord(i) := ParityWord(i+1) xor Result(i);
end loop;
for i in CntrLow to CntrHigh loop
if ((UpDwn = not ParityWord(i)) or (i = CntrHigh)) then
Result(i) := not Result(i);
exit;
end if;
end loop;
return Result;
end CalcGray;

Function NextGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '1');
end NextGray;

Function PrevGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '0');
end PrevGray;

Here is an improved version of the main routine that works for ascending
or descending ranges of the input signal.

Function CalcGray (Cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrLeft : natural := Cntr'LEFT;
variable Result : unsigned (cntr'RANGE) := cntr;
variable ParityWord : unsigned (Cntr'RANGE);
variable PrevParity : std_logic := '0';
begin
for i in ParityWord'RANGE loop
ParityWord(i) := PrevParity xor Result(i);
PrevParity := ParityWord(i);
end loop;
for i in Result'REVERSE_RANGE loop
if ((i = CntrLeft) or (UpDwn /= ParityWord(i))) then
Result(i) := not Result(i); -- found the bit to toggle
exit;
end if;
end loop;
return Result;
end CalcGray;

--

Rick C

I've always used the simplest possible way to do that:

B <= Bin2Gray(Gray2Bin(A) + 1);

Uh, don't you have to write the two conversion routines? How did you
do those?


> And I've never have had any performance problems with it. Vivado manage to optimize it quite well and employs carry chain for that.

Performance "problems" depend on the performance requirements.

And it's look like it's even better than Rick's sophisticated method:
http://imgur.com/Hu2MuMr

What were the sizes and envelope code you used?

--

Rick C

 

On Saturday, August 6, 2016 at 8:57:10 AM UTC+12, rickman wrote:

On 8/5/2016 3:11 PM, Ilya Kalistru wrote:
On Monday, June 13, 2016 at 10:31:06 AM UTC+3, rickman wrote:
On 6/13/2016 1:36 AM, rickman wrote:
I was reading up on Gray codes and figured out a fairly simple algorithm
for counting up or down with Gray codes directly rather than using a
binary counter which is converted to Gray code. It has not been
extensively tested. I don't think it will work for vectors declared
with a "to" range rather than a "downto" range. I should have used
'left and 'right instead of 'high and 'low, but I don't know how to
construct a loop that goes in either direction. I'll need to dig around
to see how that might be done.

I got the idea from a verbal description of a Gray code that defined the
bit to change as the least significant bit that gives even parity with
all the higher bits. They didn't say it just like that, but once I
thought about it I realized that was what they should have said.
Counting down is the same rule, but odd parity. I didn't synthesize it
to see how complex the logic is, but I don't think it should be too bad.

Here is the code. Any suggestions are welcome.

Function CalcGray (cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrHigh : natural := cntr'high;
variable CntrLow : natural := cntr'low;
variable Result : unsigned (cntr'range) := cntr;
variable ParityWord : unsigned (CntrHigh downto CntrLow)
:= (others => '0');
begin
ParityWord(CntrHigh) := Result(CntrHigh);
for i in CntrHigh-1 downto CntrLow loop
ParityWord(i) := ParityWord(i+1) xor Result(i);
end loop;
for i in CntrLow to CntrHigh loop
if ((UpDwn = not ParityWord(i)) or (i = CntrHigh)) then
Result(i) := not Result(i);
exit;
end if;
end loop;
return Result;
end CalcGray;

Function NextGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '1');
end NextGray;

Function PrevGray (cntr : unsigned) return unsigned is
begin
return CalcGray(cntr, '0');
end PrevGray;

Here is an improved version of the main routine that works for ascending
or descending ranges of the input signal.

Function CalcGray (Cntr : unsigned; UpDwn : std_logic)
return unsigned is
variable CntrLeft : natural := Cntr'LEFT;
variable Result : unsigned (cntr'RANGE) := cntr;
variable ParityWord : unsigned (Cntr'RANGE);
variable PrevParity : std_logic := '0';
begin
for i in ParityWord'RANGE loop
ParityWord(i) := PrevParity xor Result(i);
PrevParity := ParityWord(i);
end loop;
for i in Result'REVERSE_RANGE loop
if ((i = CntrLeft) or (UpDwn /= ParityWord(i))) then
Result(i) := not Result(i); -- found the bit to toggle
exit;
end if;
end loop;
return Result;
end CalcGray;

--

Rick C

I've always used the simplest possible way to do that:

B <= Bin2Gray(Gray2Bin(A) + 1);

Uh, don't you have to write the two conversion routines? How did you
do those?


And I've never have had any performance problems with it. Vivado manage to optimize it quite well and employs carry chain for that.

Performance "problems" depend on the performance requirements.


And it's look like it's even better than Rick's sophisticated method:
http://imgur.com/Hu2MuMr

What were the sizes and envelope code you used?

Both of the shown schematics have 16 bit inputs/outputs. The noticeable difference is you have an up/down control while the smaller only increments.

Yours resembles the combinatorial portion of an up/down gray counter. You can throw out around half the logic by only providing increment (or making UpDwn a static value allowing optimization).

 

[Ilya Kalistru]

Uh, don't you have to write the two conversion routines? How did you
do those?

Gray encoding is ubiquitous and I just have this functions in my "frequently used functions" package.

function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0');
Bin_var(Gray'high) := Gray(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

> What were the sizes and envelope code you used?

...
entity Add is
Port (
clk : in std_logic;
A : in unsigned(15 downto 0);
B : out unsigned(15 downto 0);
C : in unsigned(15 downto 0);
D : out unsigned(15 downto 0)
);
end Add;

architecture Behavioral of Add is
....
begin
B <= Bin2Gray(Gray2Bin(A) + 1) when rising_edge(clk);
D <= CalcGray(C, '1') when rising_edge(clk);
end Behavioral;

 

[rickman]

On 8/6/2016 6:59 AM, Ilya Kalistru wrote:

Uh, don't you have to write the two conversion routines? How did you
do those?

Gray encoding is ubiquitous and I just have this functions in my "frequently used functions" package.

function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0');
Bin_var(Gray'high) := Gray(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

What were the sizes and envelope code you used?

...
entity Add is
Port (
clk : in std_logic;
A : in unsigned(15 downto 0);
B : out unsigned(15 downto 0);
C : in unsigned(15 downto 0);
D : out unsigned(15 downto 0)
);
end Add;

architecture Behavioral of Add is
....
begin
B <= Bin2Gray(Gray2Bin(A) + 1) when rising_edge(clk);
D <= CalcGray(C, '1') when rising_edge(clk);
end Behavioral;

Thanks. What about Bin2Gray? I'd like to try your code in my synthesis.

In general, I don't find optimization to work all that well for many
functions. It can work ok for smaller code sections, so maybe this is
one that happens to do well with many synthesizers, or maybe the
description you use turns out to be optimal in spite of the apparent
simplicity of the description I used. For example, your code above
would use an adder chain along with the explicit chain described in
Gray2Bin (don't know about Bin2Gray) while my code has two explicit
chains. This could be simpler since the adder carry chain is embedded
in the logic elements in most FPGA families.

I've wondered just how much complexity the exit in the second loop adds.
Coding without the exit might simplify the logic.

--

Rick C

 

[Ilya Kalistru]

On Saturday, August 6, 2016 at 9:57:40 PM UTC+3, rickman wrote:

On 8/6/2016 6:59 AM, Ilya Kalistru wrote:

Uh, don't you have to write the two conversion routines? How did you
do those?

Gray encoding is ubiquitous and I just have this functions in my "frequently used functions" package.

function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0');
Bin_var(Gray'high) := Gray(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

What were the sizes and envelope code you used?

...
entity Add is
Port (
clk : in std_logic;
A : in unsigned(15 downto 0);
B : out unsigned(15 downto 0);
C : in unsigned(15 downto 0);
D : out unsigned(15 downto 0)
);
end Add;

architecture Behavioral of Add is
....
begin
B <= Bin2Gray(Gray2Bin(A) + 1) when rising_edge(clk);
D <= CalcGray(C, '1') when rising_edge(clk);
end Behavioral;

Thanks. What about Bin2Gray? I'd like to try your code in my synthesis.

In general, I don't find optimization to work all that well for many
functions. It can work ok for smaller code sections, so maybe this is
one that happens to do well with many synthesizers, or maybe the
description you use turns out to be optimal in spite of the apparent
simplicity of the description I used. For example, your code above
would use an adder chain along with the explicit chain described in
Gray2Bin (don't know about Bin2Gray) while my code has two explicit
chains. This could be simpler since the adder carry chain is embedded
in the logic elements in most FPGA families.

I've wondered just how much complexity the exit in the second loop adds.
Coding without the exit might simplify the logic.

--

Rick C

function Bin2Gray (Bin : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable Gray_var : STD_LOGIC_VECTOR(Bin'range);
begin
Gray_var(Gray_var'high) := Bin(bin'high);
for i in 0 to bin'high - 1 loop
Gray_var(i) := Bin(i) xor Bin(i + 1);
end loop;
return Gray_var;
end function Bin2Gray;

function Bin2Gray (Bin : in unsigned) return unsigned is
begin
return unsigned(Bin2Gray(std_logic_vector(Bin)));
end function Bin2Gray;


function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0');
Bin_var(Gray'high) := Gray(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

function Gray2Bin (Gray : in unsigned) return unsigned is
begin
return unsigned(Gray2Bin(std_logic_vector(Gray)));
end function Gray2Bin;

 

[Allan Herriman]

On Sat, 06 Aug 2016 14:57:38 -0400, rickman wrote:

On 8/6/2016 6:59 AM, Ilya Kalistru wrote:

Uh, don't you have to write the two conversion routines? How did you
do those?

Gray encoding is ubiquitous and I just have this functions in my
"frequently used functions" package.

function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return
STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0'); Bin_var(Gray'high) := Gray
(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

What were the sizes and envelope code you used?

...
entity Add is
Port (
clk : in std_logic;
A : in unsigned(15 downto 0); B : out unsigned(15 downto 0);
C : in unsigned(15 downto 0); D : out unsigned(15 downto 0) );
end Add;

architecture Behavioral of Add is ....
begin
B <= Bin2Gray(Gray2Bin(A) + 1) when rising_edge(clk);
D <= CalcGray(C, '1') when rising_edge(clk);
end Behavioral;

Thanks. What about Bin2Gray? I'd like to try your code in my
synthesis.

Here's my one that I've been using (variants of) since last century:


function binary_to_gray ( b : unsigned ) return std_logic_vector is
variable bcopy : std_logic_vector(b'length-1 downto 0) :=
std_logic_vector(b);
begin
return std_logic_vector(bcopy xor ('0' & bcopy(bcopy'high downto 1)));
end function binary_to_gray;


Note that (unlike gray to binary) this one doesn't need long chains of
logic.

Allan

 

[rickman]

On 8/7/2016 3:18 AM, Ilya Kalistru wrote:

On Saturday, August 6, 2016 at 9:57:40 PM UTC+3, rickman wrote:
On 8/6/2016 6:59 AM, Ilya Kalistru wrote:

Uh, don't you have to write the two conversion routines? How did you
do those?

Gray encoding is ubiquitous and I just have this functions in my "frequently used functions" package.

function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0');
Bin_var(Gray'high) := Gray(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

What were the sizes and envelope code you used?

...
entity Add is
Port (
clk : in std_logic;
A : in unsigned(15 downto 0);
B : out unsigned(15 downto 0);
C : in unsigned(15 downto 0);
D : out unsigned(15 downto 0)
);
end Add;

architecture Behavioral of Add is
....
begin
B <= Bin2Gray(Gray2Bin(A) + 1) when rising_edge(clk);
D <= CalcGray(C, '1') when rising_edge(clk);
end Behavioral;

Thanks. What about Bin2Gray? I'd like to try your code in my synthesis.

In general, I don't find optimization to work all that well for many
functions. It can work ok for smaller code sections, so maybe this is
one that happens to do well with many synthesizers, or maybe the
description you use turns out to be optimal in spite of the apparent
simplicity of the description I used. For example, your code above
would use an adder chain along with the explicit chain described in
Gray2Bin (don't know about Bin2Gray) while my code has two explicit
chains. This could be simpler since the adder carry chain is embedded
in the logic elements in most FPGA families.

I've wondered just how much complexity the exit in the second loop adds.
Coding without the exit might simplify the logic.

--

Rick C

function Bin2Gray (Bin : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable Gray_var : STD_LOGIC_VECTOR(Bin'range);
begin
Gray_var(Gray_var'high) := Bin(bin'high);
for i in 0 to bin'high - 1 loop
Gray_var(i) := Bin(i) xor Bin(i + 1);
end loop;
return Gray_var;
end function Bin2Gray;

function Bin2Gray (Bin : in unsigned) return unsigned is
begin
return unsigned(Bin2Gray(std_logic_vector(Bin)));
end function Bin2Gray;


function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0');
Bin_var(Gray'high) := Gray(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

function Gray2Bin (Gray : in unsigned) return unsigned is
begin
return unsigned(Gray2Bin(std_logic_vector(Gray)));
end function Gray2Bin;

Nice illustrations of these algorithms.

http://ncalculators.com/digital-computation/binary-gray-code-converter.htm

--

Rick C

 

[rickman]

On 12/22/2016 2:58 PM, rickman wrote:

On 8/7/2016 3:18 AM, Ilya Kalistru wrote:
On Saturday, August 6, 2016 at 9:57:40 PM UTC+3, rickman wrote:
On 8/6/2016 6:59 AM, Ilya Kalistru wrote:

Uh, don't you have to write the two conversion routines? How did you
do those?

Gray encoding is ubiquitous and I just have this functions in my
"frequently used functions" package.

function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return
STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0');
Bin_var(Gray'high) := Gray(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

What were the sizes and envelope code you used?

...
entity Add is
Port (
clk : in std_logic;
A : in unsigned(15 downto 0);
B : out unsigned(15 downto 0);
C : in unsigned(15 downto 0);
D : out unsigned(15 downto 0)
);
end Add;

architecture Behavioral of Add is
....
begin
B <= Bin2Gray(Gray2Bin(A) + 1) when rising_edge(clk);
D <= CalcGray(C, '1') when rising_edge(clk);
end Behavioral;

Thanks. What about Bin2Gray? I'd like to try your code in my
synthesis.

In general, I don't find optimization to work all that well for many
functions. It can work ok for smaller code sections, so maybe this is
one that happens to do well with many synthesizers, or maybe the
description you use turns out to be optimal in spite of the apparent
simplicity of the description I used. For example, your code above
would use an adder chain along with the explicit chain described in
Gray2Bin (don't know about Bin2Gray) while my code has two explicit
chains. This could be simpler since the adder carry chain is embedded
in the logic elements in most FPGA families.

I've wondered just how much complexity the exit in the second loop adds.
Coding without the exit might simplify the logic.

--

Rick C

function Bin2Gray (Bin : in STD_LOGIC_VECTOR) return
STD_LOGIC_VECTOR is
variable Gray_var : STD_LOGIC_VECTOR(Bin'range);
begin
Gray_var(Gray_var'high) := Bin(bin'high);
for i in 0 to bin'high - 1 loop
Gray_var(i) := Bin(i) xor Bin(i + 1);
end loop;
return Gray_var;
end function Bin2Gray;

function Bin2Gray (Bin : in unsigned) return unsigned is
begin
return unsigned(Bin2Gray(std_logic_vector(Bin)));
end function Bin2Gray;


function Gray2Bin (Gray : in STD_LOGIC_VECTOR) return
STD_LOGIC_VECTOR is
variable Bin_var : STD_LOGIC_VECTOR(Gray'range);
begin
Bin_var := (others => '0');
Bin_var(Gray'high) := Gray(Gray'high);
for i in Gray'high-1 downto 0 loop
Bin_var(i):= Bin_var(i+1) xor Gray(i);
end loop;
return Bin_var;
end function Gray2Bin;

function Gray2Bin (Gray : in unsigned) return unsigned is
begin
return unsigned(Gray2Bin(std_logic_vector(Gray)));
end function Gray2Bin;

Nice illustrations of these algorithms.

http://ncalculators.com/digital-computation/binary-gray-code-converter.htm

I came across this thread by accident yesterday when my news reader
hiccuped and marked all threads in this group as unread. On reviewing
all the info and finding a couple of new web pages with good
presentations of the problem I see why only one chain is needed. The
extra bit added as the new lsb is in essence the parity bit. It changes
on every clock and the single rule of, flip the bit to the left of the
rightmost set bit unless that rightmost set bit is the msb in which case
the msb is flipped, covers the full operation of the gray code bits.

So directly incrementing the gray code is likely to be faster and
simpler than converting to binary, incrementing and converting back.
This method needs only one chain since the parity is not calculated by a
word wide function. I will have to check which is better... and I need
to reread this thread fully to make sure this hasn't been done
already... after the holidays I think.

BTW, why can hiccuped be spelled with only 1 'p'?

--

Rick C

 

[rickman]

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?

--

Rick C