 # Gray Code

## Ask a question - edaboard.com

Goto page 1, 2  Next

rickman
Guest

Mon Jun 13, 2016 11:36 am

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
Guest

Mon Jun 13, 2016 1:31 pm

On 6/13/2016 1:36 AM, rickman wrote:
Quote:
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
Guest

Mon Jun 13, 2016 2:18 pm

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

Here is the code. Any suggestions are welcome.

Here is a relevant link that might be similar to what you're describing.

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

Kevin Jennings

rickman
Guest

Mon Jun 13, 2016 8:06 pm

On 6/13/2016 8:18 AM, KJ wrote:
Quote:
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.

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
Guest

Tue Jun 14, 2016 6:22 am

On 6/13/2016 3:31 AM, rickman wrote:
Quote:
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
Guest

Tue Jun 14, 2016 7:39 am

On 6/13/2016 8:22 PM, rickman wrote:
Quote:
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
Guest

Fri Aug 05, 2016 9:11 pm

On Monday, June 13, 2016 at 10:31:06 AM UTC+3, rickman wrote:
Quote:
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
Guest

Sat Aug 06, 2016 2:57 am

On 8/5/2016 3:11 PM, Ilya Kalistru wrote:
Quote:
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.

Quote:
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

Guest

Sat Aug 06, 2016 4:08 am

On Saturday, August 6, 2016 at 8:57:10 AM UTC+12, rickman wrote:
Quote:
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
Guest

Sat Aug 06, 2016 12:59 pm

Quote:
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?

...
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)
);

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
Guest

Sun Aug 07, 2016 12:57 am

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

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?

...
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)
);

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
Guest

Sun Aug 07, 2016 9:18 am

On Saturday, August 6, 2016 at 9:57:40 PM UTC+3, rickman wrote:
Quote:
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?

...
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)
);

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
Guest

Sun Aug 07, 2016 1:05 pm

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

Quote:
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?

...
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) );

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
Guest

Fri Dec 23, 2016 2:58 am

On 8/7/2016 3:18 AM, Ilya Kalistru wrote:
Quote:
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?

...
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)
);

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
Guest

Sat Dec 24, 2016 2:09 am

On 12/22/2016 2:58 PM, rickman wrote:
Quote:
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?

...
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)
);

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

Goto page 1, 2  Next