Question : Gray Code Generator 
Author Message
 Question : Gray Code Generator

Hi,
I am looking for a Gray code generator that is purely combinatorial which
will output the next Gray value depending on the current value at its
input.
Does anyone know how to code it in VHDL.
Thanks in advance for any help.

KP Chua



Tue, 13 Jun 2000 03:00:00 GMT  
 Question : Gray Code Generator


Quote:
> Hi,
> I am looking for a Gray code generator that is purely combinatorial which
> will output the next Gray value depending on the current value at its
> input.
> Does anyone know how to code it in VHDL.
> Thanks in advance for any help.
> KP Chua

I bet you can write one yourself in 5 mins: a very, very nested
if..then..else statement:

if ([code value]) then [output] <= [(code value +1) ] else
if ([code value +1] then [output <= [next (code value +2) else
...etc.

you have to "hardwire" all the codes (a bit of typing skills required..)

thomas



Tue, 13 Jun 2000 03:00:00 GMT  
 Question : Gray Code Generator

Quote:

> > I am looking for a Gray code generator that is purely combinatorial which
> > will output the next Gray value depending on the current value at its
> > input.
> > Does anyone know how to code it in VHDL.
> > Thanks in advance for any help.
> I bet you can write one yourself in 5 mins: a very, very nested
> if..then..else statement:
> if ([code value]) then [output] <= [(code value +1) ] else
> if ([code value +1] then [output <= [next (code value +2) else
> ...etc.

That is the brute force approach, and incidentally an approach which
synthesizes in a less than elegant way. The code is also unreadable
and big for any usable bit sizes.

I have been looking at the same problem recently. The simplest
approach (both by way of design time and synthesized result) seems to
be to convert the gray number to a binary representation, add one, and
then convert it back to a gray representation. The conversions contain
a limited number of xor gates, and the incrementer should be
trivial. When the whole thing is flattened during synthesis, the
synthesizer should be capable of doing the necessary boolean
optimizations.

Making a new type similar to the "unsigned" type is the way I will be
going. That way, the conversions are all packed away neatly into a
package somewhere, and I will never need to worry about anything else
than using the correct types and casts where appropriate.

Geir



Thu, 15 Jun 2000 03:00:00 GMT  
 Question : Gray Code Generator

Quote:

> I have been looking at the same problem recently. The simplest
> approach (both by way of design time and synthesized result) seems to
> be to convert the gray number to a binary representation, add one, and
> then convert it back to a gray representation. The conversions contain
> a limited number of xor gates, and the incrementer should be
> trivial.

I did exactly this, just this morning, using synopsys FPGA-compiler.
However, the resulting design is very slow, that is (for width = 8)
up to 7
logic levels (LUT) are passed with target archtitecture
ALTERA FLEX10K,
for -3 speed grade this results in around 30 ns delay, way
too much.
For a fast gray counter I would prefer a pipelined design with a
redundand representation.
Andreas


Fri, 16 Jun 2000 03:00:00 GMT  
 Question : Gray Code Generator


Quote:

>Hi,
>I am looking for a Gray code generator that is purely combinatorial which
>will output the next Gray value depending on the current value at its
>input.
>Does anyone know how to code it in VHDL.

Simple case statement:

process (CODE)
begin
   case (CODE) is
   when "000" => NEXT <= "001";
   when "001" => NEXT <= "011";
   when "011" => NEXT <= "010";
   when "010" => NEXT <= "110";
   when "110" => NEXT <= "111";
   when "111" => NEXT <= "101";
   when "101" => NEXT <= "100";
   when "100" => NEXT <= "000";
   when others => null;
   end case;
end process;

Fancier way to do it:

process (CODE)
   type GRAY_SEQ_TYP is array (0 to 7) of STD_LOGIC_VECTOR(2 downto 0);
   constant GRAY_SEQ: GRAY_SEQ_TYP :=
       ("000", "001", "011", "010", "110", "111", "101", "100");
begin
   for I in GRAY_SEQ'range loop
      if (CODE = GRAY_SEQ(I)) then
         NEXT <= GRAY_SEQ((I + 1) rem 8);
      end if;
   end loop;
end process;

As a previous poster mentionned, that might generate a long
decode logic chain. No big deal if that still meets your timing
and area constaints.

Alternatively:

process (CODE)
   type GRAY_SEQ_TYP is array (0 to 7) of STD_LOGIC_VECTOR(2 downto 0);
   constant GRAY_SEQ: GRAY_SEQ_TYP :=
       ("000", "001", "011", "010", "110", "111", "101", "100");
begin
   case (CODE) is
   when GRAY_SEQ(0) => NEXT <= GRAY_SEQ(1);
   when GRAY_SEQ(1) => NEXT <= GRAY_SEQ(2);
   when GRAY_SEQ(2) => NEXT <= GRAY_SEQ(3);
   when GRAY_SEQ(3) => NEXT <= GRAY_SEQ(4);
   when GRAY_SEQ(4) => NEXT <= GRAY_SEQ(5);
   when GRAY_SEQ(5) => NEXT <= GRAY_SEQ(6);
   when GRAY_SEQ(6) => NEXT <= GRAY_SEQ(7);
   when GRAY_SEQ(7) => NEXT <= GRAY_SEQ(0);
   end case;
end process;

That's for a 3-bit gray code.
Cliff Cummings taught me a neat trick for generating gray code
for any number of bits (of course, his was in Verilog ;-)

Take the n-1 bit gray code, prepend a 0.
Then take the n-1 bit gray code in the reverse order
and prepend a 1: voila! a n-bit gray code.

1-bit gray code: 0
                 1

2-bit gray code: 00
                 01
                 11
                 10
                 ^^
                 ||
prepended bit ---++-- 1-bit gray code

It should be possible to write a recursive VHDL function/procedure
to compute a N-bit gray code on the fly. Your decoder could then
be made to handle any number of bits either though a generic
or unconstrainted ports.

--
Janick Bergeron       Qualis Design Corporation          Main : (503) 670-7200
Director of          5535 SW Meadows,  Suite 450         Dirct: (503) 968-8544
Technology              Lake Oswego, OR 97035              Fax: (503) 670-0809



Fri, 16 Jun 2000 03:00:00 GMT  
 Question : Gray Code Generator

On Mon, 29 Dec 1997 11:43:19 +0100, Andreas Doering

Quote:

>I did exactly this, just this morning, using synopsys FPGA-compiler.
>However, the resulting design is very slow, that is (for width = 8)
>up to 7
>logic levels (LUT) are passed with target archtitecture
>ALTERA FLEX10K,
>for -3 speed grade this results in around 30 ns delay, way
>too much.

If you are using FLEX10K, why not implement the 8 bit next state
conversion with an EAB configured as an 8 bit wide ROM?

I tried exactly the same brute force attempt as yourself, except I
wrote 256 case statements :
        when "00000000" => result <= "00000001" ;
        when "00000001" => result <= "00000011" ;
etc.

Synthesised to ORCA 2CxxA -3 speed grade and with a rough place &
route gave the register to register performance of 72 MHz.

Combinatorially, the critical path synthesised as a mux delay (two 5
input LUT's feeding a 2 input mux) followed by routing, followed by a
5 input function. So that's 2 levels of logic. (but the mux does do an
11 input function)

Quote:
>For a fast gray counter I would prefer a pipelined design with a
>redundand representation.

I thought a bit over this one, and the best I could come up with for
large length counters was to take an n-bit binary counter and generate
pre-calculators for where the gray bits change. Fortunately, the MSB
of the gray counter is just the MSB of your binary counter, but I
generated it anyway for completeness of the VHDL.

Maybe it's not the most elegant, but it works, (Modelsim says so after
running through the entire 16 bit count), is relatively extensible,
and seems to give reasonable speeds. (code at end of this post)

I put this to ORCA again, and got 54 MHz in a -3 speed grade, which
doesn't seem too bad for a 16 bit Gray count.

Hope this helps.

Stuart

-- 16 bit Gray counter using inversion selection.

library IEEE ;
use     IEEE.Std_Logic_1164.ALL ;
use     IEEE.Std_Logic_Arith.ALL ;
use     IEEE.Std_Logic_Unsigned.ALL ;

entity gray IS
        port (  clk, reset      : IN bit ;
                result          : OUT std_logic_vector(15 downto 0) )
;
end gray ;

architecture behavioural of gray is
        signal counter : std_logic_vector(15 downto 0) ;
        signal invert : std_logic_vector(15 downto 0) ;
        signal gray : std_logic_vector(15 downto 0) ;
begin
main_counter : process ( reset, clk )
        begin
        if (reset = '0') then
                counter <= (others => '0') ;
        elsif (clk'event and clk = '1') then
                counter <= counter + '1' ;
        end if ;
        end process ;

inversion_generation : process ( counter )
        begin
        invert <= (others => '0') ;
        if counter(0) = '0' then invert(0) <= '1' ;
        end if ;
        if counter(1 downto 0) = "01" then invert(1) <= '1' ;
        end if ;
        if counter(2 downto 0) = "011" then invert(2) <= '1' ;
        end if ;
        if counter(3 downto 0) = "0111" then invert(3) <= '1' ;
        end if ;
        if counter(4 downto 0) = "01111" then invert(4) <= '1' ;
        end if ;
        if counter(5 downto 0) = "011111" then invert(5) <= '1' ;
        end if ;
        if counter(6 downto 0) = "0111111" then invert(6) <= '1' ;
        end if ;
        if counter(7 downto 0) = "01111111" then invert(7) <= '1' ;
        end if ;
        if counter(8 downto 0) = "011111111" then invert(8) <= '1' ;
        end if ;
        if counter(9 downto 0) = "0111111111" then invert(9) <= '1' ;
        end if ;
        if counter(10 downto 0) = "01111111111" then invert(10) <= '1'
;
        end if ;
        if counter(11 downto 0) = "011111111111" then invert(11) <=
'1' ;
        end if ;
        if counter(12 downto 0) = "0111111111111" then invert(12) <=
'1' ;
        end if ;
        if counter(13 downto 0) = "01111111111111" then invert(13) <=
'1' ;
        end if ;
        if counter(14 downto 0) = "011111111111111" then invert(14) <=
'1' ;
        end if ;
        if counter(14 downto 0) = "111111111111111" then invert(15) <=
'1' ;
        end if ;
        end process ;

output_result : process ( reset, clk )
        begin
        if (reset = '0') then
                gray <= (others => '0') ;
        elsif (clk'event and clk = '1') then
                gray <= ( gray xor invert ) ;
        end if ;
        end process ;

result <= gray ;

end behavioural ;

--
For Email remove "die.spammer." from the address



Tue, 20 Jun 2000 03:00:00 GMT  
 Question : Gray Code Generator

Hi ,
I made another design where I looked deeper into the details
of the gray code.
While a binary counter requires one prefix computation
from the lower end (LSB) up, a gray counter needs two
prefix computations
p(i)=(NOT a(0)) AND (NOT a(1)) AND ...AND (NOT a(i))
and
s(i)=a(n-1) XOR a(n-2) XOR ... XOR a(i)

Thus, one chain going up, the other down.
Using a good (by far not optimal ) algorithm an 8-bit gray counter takes
16 4-input lookup-tables and depth 3.
Here it is:
(synthesizable by synopsys, therefor
 good old VHDL'87 style)
USE IEEE.std_logic_arith.ALL;
ARCHITECTURE syn2 OF incgray IS
-- improved version without using explicit arithmetics

-- the prefix computation - here shown in a recursive version is
-- not optimal, but for FPGAs just use the chains

 FUNCTION Fxorprefix(a:std_logic_vector) RETURN std_logic_vector IS
  VARIABLE Vlow: std_logic_vector((a'HIGH+a'LOW)/2 DOWNTO a'LOW);
  VARIABLE Vhigh: std_logic_vector(a'HIGH DOWNTO (a'HIGH+a'LOW)/2+1);
  VARIABLE i:INTEGER;
 BEGIN
  IF a'length = 1 THEN RETURN a;
  ELSIF a'length = 2 THEN RETURN (a(a'LOW) xor a(a'HIGH),a(a'LOW));
  ELSE
   Vlow:=Fxorprefix(a((a'HIGH+a'LOW)/2 DOWNTO a'LOW));
   Vhigh:=Fxorprefix(a(a'HIGH DOWNTO (a'HIGH+a'LOW)/2+1));
   FOR i IN Vhigh'RANGE LOOP
    Vhigh(i):=Vhigh(i) xor Vlow(Vlow'HIGH);
   END LOOP;
   RETURN Vhigh & Vlow;
 END IF;
 END Fxorprefix;

 FUNCTION Fandprefix(a:std_logic_vector) RETURN std_logic_vector IS
  VARIABLE Vlow,Vlowh: std_logic_vector((a'HIGH+a'LOW)/2 DOWNTO a'LOW);
  VARIABLE Vhigh,Vhighh: std_logic_vector(a'HIGH DOWNTO
(a'HIGH+a'LOW)/2+1);
  VARIABLE i:INTEGER;
 BEGIN
  IF a'length = 1 THEN
   RETURN a;
  ELSIF a'length = 2 THEN
   RETURN (a(a'LOW) and a(a'HIGH),a(a'LOW));
  ELSE
   Vlowh:=a((a'HIGH+a'LOW)/2 DOWNTO a'LOW);
   Vlow:=Fandprefix(Vlowh);
   Vhigh:=Fandprefix(a(a'HIGH DOWNTO (a'HIGH+a'LOW)/2+1));
   FOR i IN Vhigh'RANGE LOOP
    Vhigh(i):=Vhigh(i) and Vlow(Vlow'HIGH);
   END LOOP;
   RETURN Vhigh & Vlow;
 END IF;
 END Fandprefix;

FUNCTION Freverse(a:std_logic_vector) RETURN std_logic_vector IS
VARIABLE t:std_logic_vector(a'RANGE);
BEGIN
  FOR i IN t'RANGE LOOP
   t(i):=a(a'HIGH+a'LOW-i);
  END LOOP;
 RETURN t;
END Freverse;

SIGNAL Ssums,Sprods,Sreverse,Srevsum,Snota:std_logic_vector(width-1
DOWNTO 0);

BEGIN

Sreverse<=Freverse(a);
Ssums<=Freverse(Srevsum);
Srevsum<=Fxorprefix(Sreverse);
Snota<= NOT a;
Sprods<= Fandprefix(Snota);

Pdriveap1: PROCESS(a,Ssums,Sprods)
VARIABLE i:integer;
BEGIN
 FOR i IN width-1 DOWNTO 2 LOOP
  ap1(i)<=a(i) xor (Sprods(i-2) AND (a(i-1) xor (Ssums(i) AND a(i-1))));
 END LOOP;
 ap1(0)<= not Ssums(1);
 ap1(1)<=a(1) xor a(0) xor (a(0) and Ssums(1));
END PROCESS Pdriveap1;

END syn2;

Am I sure it can be improved in elegance efficiency and
generality.
Hints are welcome.
Andreas



Sat, 24 Jun 2000 03:00:00 GMT  
 Question : Gray Code Generator

ing.
: Hi,
: I am looking for a Gray code generator that is purely combinatorial which
: will output the next Gray value depending on the current value at its
: input.
: Does anyone know how to code it in VHDL.
: Thanks in advance for any help.

: KP Chua

I've been using gray code counters for several years, though I haven't
designed any in VHDL. Here's the best algorithm I've come up with that
works with any word width. Assuming that the counter is n bits wide,

A is A[n-1] A[n-2] ... A[2] A[1] A[0] and is the current value.
B is B[n-1] B[n-2] ... B[2] B[1] B[0] and is the next value.

First, calaulate a parity bit P of A.

     P = A[0] XOR A[1] XOR A[2] ... XOR A[n-1].

Then,

     B[0] = NOT A[0] XOR P
     B[1] = A[1] XOR (A[0] AND P)
     B[2] = A[2] XOR (A[1] AND NOT A[0] AND P)
     B[3] = A[3] XOR (A[2] AND NOT A[1] AND NOT A[0] AND P)

The pattern that emerges is

     B[k] = A[k] XOR (A[k-1] AND NOT A[k-2] AND NOT A[k-3] ... AND NOT A[0] AND P)

except for k = n-1 where the A[k-1] term is left out so that

     B[n-1] = A[n-1] XOR (NOT A[n-3] AND NOT A[n-4] ... AND NOT A[0] AND P) .

I have limited VHDL experience and have not yet needed to code this algorithm.
I'll leave that to you experts.

Ken Williams    



Sun, 25 Jun 2000 03:00:00 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. Binary Gray Code - code example

2. help: binary code -> gray code convertation

3. Gray - a parser generator in ANS Forth

4. gray: a parser generator in forth

5. Reflected Gray Codes

6. How to implement a Gray Code counter?

7. gray code counter in asyn FIFO design

8. Do gray code counters comsume less power

9. One-Hot or Gray-Code State Machine

10. One-Hot or Gray-Code State Machine?

11. Gray Code Counter - Comments?

12. Gray code counters

 

 
Powered by phpBB® Forum Software