Gray counter

Discussion in 'VHDL' started by ast, Sep 13, 2007.

  1. ast

    ast Guest

    Hi,

    Do you know how to design a gray counter in VHDL ?

    Better without a lookup table

    The difficulty is to find a mathematical relation between the next state
    and the current state.

    thx
     
    ast, Sep 13, 2007
    #1
    1. Advertising

  2. ast wrote:
    > Do you know how to design a gray counter in VHDL ?
    > Better without a lookup table
    > The difficulty is to find a mathematical relation between the next state
    > and the current state.


    Why not use a normal counter, and then do a binary to Gray conversion? Just
    Googling on binary to gray conversion should give you all the information you
    need. Alternatively, you could convert from Gray to binary, add 1, and then
    convert back to binary.

    Regards,

    Pieter
     
    Pieter Hulshoff, Sep 13, 2007
    #2
    1. Advertising

  3. On Thu, 13 Sep 2007 15:00:38 +0200, "ast" <> wrote:

    >Do you know how to design a gray counter in VHDL ?


    Just a thought: If you have an N-bit Gray counter, you
    can make an (N+1)-bit Gray counter by induction:

    * write out the states of the N-bit counter as a linear
    sequence
    * set the N+1'th bit to zero
    * count up the linear sequence
    * when you're in the last state of the sequence, and
    the N+1'th bit is zero, don't wrap around to the
    first state but instead toggle the N+1'th bit to 1,
    keeping the other bits' value frozen...
    * ... and flip the count direction so that you then
    start to count down towards the first state
    * when you're in the first state and the N+1'th bit
    is 1, don't count down but instead toggle the N+1#th
    bit to zero, keeping the other bits frozen

    So you need only detect the start and finish values
    of the N-bit counter's linear sequence, and the
    value of the N+1'th bit. And if you make the
    low and high limits of the N-bit counter be
    1000....000 and 0000...000 respectively, it all
    becomes rather easy.
    --
    Jonathan Bromley, Consultant

    DOULOS - Developing Design Know-how
    VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

    Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK

    http://www.MYCOMPANY.com

    The contents of this message may contain personal views which
    are not the views of Doulos Ltd., unless specifically stated.
     
    Jonathan Bromley, Sep 13, 2007
    #3
  4. ast

    Andy Guest

    On Sep 13, 8:04 am, Pieter Hulshoff <> wrote:
    > ast wrote:
    > > Do you know how to design a gray counter in VHDL ?
    > > Better without a lookup table
    > > The difficulty is to find a mathematical relation between the next state
    > > and the current state.

    >
    > Why not use a normal counter, and then do a binary to Gray conversion?


    Because the binary to gray conversion would be "glitchy". For many
    applications of a gray counter, this would not be acceptable. If a
    latency of one clock cycle is acceptable, registering the output of
    the conversion would work.

    > Just
    > Googling on binary to gray conversion should give you all the information you
    > need. Alternatively, you could convert from Gray to binary, add 1, and then
    > convert back to binary.


    Err... "then convert back to gray". Yes, that would work. Not sure it
    is optimal, since one of the directions is expensive (can't remember
    which one, but I think it is gray->binary), especially for long
    counters.

    >
    > Regards,
    >
    > Pieter
     
    Andy, Sep 13, 2007
    #4
  5. ast

    ast Guest

    "ast" <> a écrit dans le message de news: 46e93478$0$5074$...
    > Hi,
    >
    > Do you know how to design a gray counter in VHDL ?
    >
    > Better without a lookup table
    >
    > The difficulty is to find a mathematical relation between the next state
    > and the current state.
    >
    > thx


    I found a very interesting article in wikipedia about Gray code.

    http://en.wikipedia.org/wiki/Gray_code

    As Pieter Hulshoff, they say:

    "Probably the most obvious way to increment a Gray code number is to convert it
    into ordinary binary code, add one to it with a standard binary adder, and then convert
    the result back to Gray code."

    They provide algoritms for the conversion

    Here is an algorithm in pseudocode to convert natural binary codes to Gray code (encode):

    Let B[n:0] be the input array of bits in the usual binary representation, [0] being LSB
    Let G[n:0] be the output array of bits in Gray code

    G[n] = B[n]
    for i = n-1 downto 0
    G = B[i+1] XOR B

    This algorithm can be rewritten in terms of words instead of arrays of bits:
    G = B XOR (SHR(B))

    Here is an algorithm to convert Gray code to natural binary codes (decode):

    Let G[n:0] be the input array of bits in Gray code
    Let B[n:0] be the output array of bits in the usual binary representation

    B[n] = G[n]
    for i = n-1 downto 0
    B = B[i+1] XOR G

    This can be easily translated in VHDL.
     
    ast, Sep 13, 2007
    #5
  6. Andy wrote:
    > On Sep 13, 8:04 am, Pieter Hulshoff <> wrote:
    >> ast wrote:
    >>> Do you know how to design a gray counter in VHDL ?
    >>> Better without a lookup table
    >>> The difficulty is to find a mathematical relation between the next state
    >>> and the current state.

    >> Why not use a normal counter, and then do a binary to Gray conversion?

    >
    > Because the binary to gray conversion would be "glitchy". For many
    > applications of a gray counter, this would not be acceptable. If a
    > latency of one clock cycle is acceptable, registering the output of
    > the conversion would work.


    I would expect the need for a Gray counter to already indicate that an extra
    clock cycle should not be a huge issue, but I guess the OP will have to answer
    that one. :) Signal transfer between clock areas should always be FF2FF IMHO,
    and of course an extra FF to take care of meta stability issues.

    Regards,

    Pieter
     
    Pieter Hulshoff, Sep 13, 2007
    #6
  7. "ast" <> writes:

    > Do you know how to design a gray counter in VHDL ?
    >
    > Better without a lookup table


    Why? If you have excess ROM (or even LUT's) available, why not use it.

    > The difficulty is to find a mathematical relation between the next
    > state and the current state.


    Your synthesis tool should be good at that. I usually feed it a table
    so it can figure out the next states itself.

    Usually I have some other requirements like it has to be circular or
    that certain bit toggle in some specific order etc.


    Petter
    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is top-posting such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Petter Gustad, Sep 13, 2007
    #7
  8. ast

    KJ Guest

    KJ, Sep 13, 2007
    #8
  9. "ast" <> writes:

    > "ast" <> a écrit dans le message de news: 46e93478$0$5074$...
    >> Hi,
    >>
    >> Do you know how to design a gray counter in VHDL ?
    >>
    >> Better without a lookup table
    >>
    >> The difficulty is to find a mathematical relation between the next state
    >> and the current state.

    >
    > I found a very interesting article in wikipedia about Gray code.
    >
    > http://en.wikipedia.org/wiki/Gray_code
    >
    > As Pieter Hulshoff, they say:
    >
    > "Probably the most obvious way to increment a Gray code number is to convert it
    > into ordinary binary code, add one to it with a standard binary adder, and then convert
    > the result back to Gray code."
    >
    > They provide algoritms for the conversion


    [snip]

    A few years back, I spent a weekend figuring out how to do this
    directly, and generically.

    The result was smaller, faster, and synthesized quicker than the
    normal way of computing
    next <= bin2gray(gray2bin(current)+1)


    Kai
    --
    Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>
     
    Kai Harrekilde-Petersen, Sep 13, 2007
    #9
  10. ast

    Zara Guest

    On Thu, 13 Sep 2007 15:00:38 +0200, "ast" <> wrote:

    >Hi,
    >
    >Do you know how to design a gray counter in VHDL ?
    >
    >Better without a lookup table
    >
    >The difficulty is to find a mathematical relation between the next state
    >and the current state.
    >



    the relation is simple to express ;-)

    Every bit changes when:

    a) the parity of the higher bits equals the bit
    AND
    b) Next lower bit is 1
    c) Next lower bits all 0

    Try it!


    Best regards,

    Zara
     
    Zara, Sep 14, 2007
    #10
  11. ast

    Zara Guest

    On Fri, 14 Sep 2007 07:41:29 +0200, Zara <>
    wrote:

    >On Thu, 13 Sep 2007 15:00:38 +0200, "ast" <> wrote:
    >
    >>Hi,
    >>
    >>Do you know how to design a gray counter in VHDL ?
    >>
    >>Better without a lookup table
    >>
    >>The difficulty is to find a mathematical relation between the next state
    >>and the current state.
    >>

    >
    >
    >the relation is simple to express ;-)
    >
    >Every bit changes when:
    >
    >a) the parity of the higher bits equals the bit
    >AND
    >b) Next lower bit is 1
    >c) Next lower bits all 0
    >



    There is one correction to this rule:

    (b) condition should be next lower bit is the contrary to the bit in
    question!

    Sorry

    Zara
     
    Zara, Sep 14, 2007
    #11
  12. "Zara" <> wrote in message
    news:...

    >>the relation is simple to express ;-)
    >>
    >>Every bit changes when:
    >>
    >>a) the parity of the higher bits equals the bit
    >>AND
    >>b) Next lower bit is 1
    >>c) Next lower bits all 0
    >>

    >
    >
    > There is one correction to this rule:
    >
    > (b) condition should be next lower bit is the contrary to the bit in
    > question!


    Maybe I don't understand your description, but what happens after "0110"?
    Looking at the last '1' it satisfies all your conditions. Similarly, the
    last '0' satisfies them too. So your description is not unique. BTW, we
    agree that the next state should be "0111", right?

    -Michael.
     
    Michael Jørgensen, Sep 14, 2007
    #12
  13. ast

    Zara Guest

    On Fri, 14 Sep 2007 10:14:15 +0200, "Michael Jørgensen"
    <> wrote:

    >
    >"Zara" <> wrote in message
    >news:...
    >
    >>>the relation is simple to express ;-)
    >>>
    >>>Every bit changes when:
    >>>
    >>>a) the parity of the higher bits equals the bit
    >>>AND
    >>>b) Next lower bit is 1
    >>>c) Next lower bits all 0
    >>>

    >>
    >>
    >> There is one correction to this rule:
    >>
    >> (b) condition should be next lower bit is the contrary to the bit in
    >> question!

    >
    >Maybe I don't understand your description, but what happens after "0110"?
    >Looking at the last '1' it satisfies all your conditions. Similarly, the
    >last '0' satisfies them too. So your description is not unique. BTW, we
    >agree that the next state should be "0111", right?
    >



    OOps, you are right. I'll take a look to correct it
     
    Zara, Sep 14, 2007
    #13
  14. ast

    Zara Guest

    On Fri, 14 Sep 2007 10:14:15 +0200, "Michael Jørgensen"
    <> wrote:

    >
    >"Zara" <> wrote in message
    >news:...
    >
    >>>the relation is simple to express ;-)
    >>>
    >>>Every bit changes when:
    >>>
    >>>a) the parity of the higher bits equals the bit
    >>>AND
    >>>b) Next lower bit is 1
    >>>c) Next lower bits all 0
    >>>

    >>
    >>
    >> There is one correction to this rule:
    >>
    >> (b) condition should be next lower bit is the contrary to the bit in
    >> question!

    >
    >Maybe I don't understand your description, but what happens after "0110"?
    >Looking at the last '1' it satisfies all your conditions. Similarly, the
    >last '0' satisfies them too. So your description is not unique. BTW, we
    >agree that the next state should be "0111", right?
    >



    You are right.

    The conditions rally are:

    (a) the parity of the higher bits equals the bit
    (b) No lower bit will change

    Regards,

    Zara


    PS Now I have taken the time to test the algorithm (using Haskell), it
    works at least up to 8 bits....
     
    Zara, Sep 14, 2007
    #14
  15. ast

    Charles, NG Guest

    I hope this is what you are looking for. It is based on a C-solution I
    found on the web many many years ago (so long ago I have lost the link).
    I have used it in many designs since:

    -- cval : current value
    -- pval : the 'parity'. Since the gray parity changes state on
    -- each increment, this is just an external toggle-FF
    -- initialised to '0'
    function f_gray_increment(cval : std_logic_vector; pval : std_logic)
    return std_logic_vector is
    constant c_low_bits_zero : std_logic_vector(cval'left - 1
    downto 0)
    := (others => '0');
    variable i : integer;
    variable v_accumulate : std_logic;
    variable v_par1 : std_logic_vector(cval'length - 1
    downto 0);
    variable v_toggle_sel : std_logic_vector(cval'left downto
    cval'right);

    begin
    v_par1 := cval;
    if ((pval = '1') and (v_par1(v_par1'left) = '1') and
    (v_par1(v_par1'left - 1 downto 0) = c_low_bits_zero)) then
    return '0' & c_low_bits_zero;
    else
    v_accumulate := '1';
    v_toggle_sel := (others => '0');
    if (pval = '0') then
    v_toggle_sel(v_toggle_sel'right) := '1';
    else
    for i in (v_toggle_sel'right + 1) to (v_toggle_sel'left)
    loop
    v_toggle_sel(i) := v_par1(i - 1) and v_accumulate
    and pval;
    v_accumulate := v_accumulate and not v_par1(i - 1);
    end loop;
    end if;
    return v_toggle_sel xor v_par1;
    end if;
    end f_gray_increment;


    Here the same in Verilog:
    // Function: f_gray_increment
    function [pAddrSize - 1:0] f_gray_increment;
    input [pAddrSize - 1:0] pGray;
    input pPar;
    reg vAccumulate;
    reg [pAddrSize - 1:0] vResult;
    reg [pAddrSize - 1:0] vToggleSel;
    integer i;
    begin
    if ((pPar == 1'b1) && (pGray[pAddrSize - 1] == 1'b1)
    && (pGray[pAddrSize - 2:0] == 0))
    f_gray_increment = 0;
    else
    begin
    if (pPar == 1'b0)
    vToggleSel = 1;
    else
    begin
    vAccumulate = 1'b1;
    vToggleSel = 0;
    for (i = 1; i < pAddrSize; i = i + 1)
    begin
    vToggleSel = pGray[i - 1] & vAccumulate & pPar;
    vAccumulate = vAccumulate & ~pGray[i - 1];
    end
    end
    f_gray_increment = vToggleSel ^ pGray;
    end
    end
    endfunction
     
    Charles, NG, Sep 14, 2007
    #15
  16. ast

    Zara Guest

    On Fri, 14 Sep 2007 11:46:34 +0200, Zara <>
    wrote:

    >On Fri, 14 Sep 2007 10:14:15 +0200, "Michael Jørgensen"
    ><> wrote:
    >
    >>
    >>"Zara" <> wrote in message
    >>news:...
    >>

    <...>
    >
    >The conditions rally are:
    >
    >(a) the parity of the higher bits equals the bit
    >(b) No lower bit will change
    >



    Should anyone want to test the algotihm, there it is, in VHDL:

    <VHDL>
    library IEEE;
    use IEEE.STD_LOGIC_1164.ALL;

    entity gray is
    Generic ( BITS : integer :=5 );
    Port (
    clock : in std_logic;
    reset : in std_logic;
    gray_code : out std_logic_vector(0 to BITS-1)
    );
    end gray;

    architecture Behavioral of gray is

    signal
    counter,
    changes_a,no_changes_b,
    final_change :std_logic_vector(0 to BITS-1);

    signal parities : std_logic_vector(1 to BITS-1);

    begin

    -- Calculates parities of higher bits
    parities(1)<=counter(0);
    par:for i in 2 to BITS-1 generate
    parities(i) <= parities(i-1) xor counter(i-1);
    end generate;

    -- Compares against corresponding bit
    changes_a <= '1' &
    ( not ( parities xor counter( parities'range ) ) );

    -- Isolates lowest change
    no_changes_b(BITS-1) <= '0';
    noch:for i in 0 to BITS-2 generate
    no_changes_b(i) <= no_changes_b(i+1) or changes_a(i+1);
    end generate;
    final_change <= changes_a and not no_changes_b;

    -- The counter itself
    process(reset,clock)
    begin
    if reset='1' then
    counter <= (others=>'0');
    elsif rising_edge(clock) then
    counter <= counter xor final_change;
    end if;
    end process;

    gray_code<=counter;

    end Behavioral;
    </VHDL>

    You may compress all these calculations to a few complex expressions,
    of course, but the result will be the same


    For 5 bit counter, Xilinx reports 5 flip-flops used and 6 4-input
    LUTS.
    For 8 bit, counter, it is 8 flip-flops and 18 4-input LUTS


    Best regards,


    Zara
     
    Zara, Sep 14, 2007
    #16
  17. ast

    Andy Guest

    > You may compress all these calculations to a few complex expressions,
    > of course, but the result will be the same
    >
    > For 5 bit counter, Xilinx reports 5 flip-flops used and 6 4-input
    > LUTS.
    > For 8 bit, counter, it is 8 flip-flops and 18 4-input LUTS
    >
    > Best regards,
    >
    > Zara


    Interesting... for a binary shadow counter implementation (xilinx v4),
    synplify reports 15 flops and 15 luts for an 8 bit gray counter.

    main : PROCESS (clk, rst) IS
    VARIABLE cnt_b : unsigned(count'range);
    BEGIN
    IF rst = '1' THEN
    cnt_b := (OTHERS => '0');
    count <= (OTHERS => '0');
    ELSIF rising_edge(clk) THEN
    cnt_b := cnt_b + 1;
    count <= to_gray(cnt_b);
    END IF;
    END PROCESS main;

    Andy
     
    Andy, Sep 14, 2007
    #17
  18. ast

    ast Guest

    "Andy" <> a écrit dans le message de news: ...
    >> You may compress all these calculations to a few complex expressions,
    >> of course, but the result will be the same
    >>
    >> For 5 bit counter, Xilinx reports 5 flip-flops used and 6 4-input
    >> LUTS.
    >> For 8 bit, counter, it is 8 flip-flops and 18 4-input LUTS
    >>
    >> Best regards,
    >>
    >> Zara

    >
    > Interesting... for a binary shadow counter implementation (xilinx v4),
    > synplify reports 15 flops and 15 luts for an 8 bit gray counter.
    >
    > main : PROCESS (clk, rst) IS
    > VARIABLE cnt_b : unsigned(count'range);
    > BEGIN
    > IF rst = '1' THEN
    > cnt_b := (OTHERS => '0');
    > count <= (OTHERS => '0');
    > ELSIF rising_edge(clk) THEN
    > cnt_b := cnt_b + 1;
    > count <= to_gray(cnt_b);
    > END IF;
    > END PROCESS main;
    >
    > Andy
    >


    hum ...

    cnt_b should be implemented with 8 flip flop and count too.
    So 16 flops

    It is stange if you only have 15 flops
     
    ast, Sep 14, 2007
    #18
  19. ast

    Andy Guest

    On Sep 14, 1:47 pm, "ast" <> wrote:
    > "Andy" <> a écrit dans le message de news: ...
    >
    >
    >
    > >> You may compress all these calculations to a few complex expressions,
    > >> of course, but the result will be the same

    >
    > >> For 5 bit counter, Xilinx reports 5 flip-flops used and 6 4-input
    > >> LUTS.
    > >> For 8 bit, counter, it is 8 flip-flops and 18 4-input LUTS

    >
    > >> Best regards,

    >
    > >> Zara

    >
    > > Interesting... for a binary shadow counter implementation (xilinx v4),
    > > synplify reports 15 flops and 15 luts for an 8 bit gray counter.

    >
    > > main : PROCESS (clk, rst) IS
    > > VARIABLE cnt_b : unsigned(count'range);
    > > BEGIN
    > > IF rst = '1' THEN
    > > cnt_b := (OTHERS => '0');
    > > count <= (OTHERS => '0');
    > > ELSIF rising_edge(clk) THEN
    > > cnt_b := cnt_b + 1;
    > > count <= to_gray(cnt_b);
    > > END IF;
    > > END PROCESS main;

    >
    > > Andy

    >
    > hum ...
    >
    > cnt_b should be implemented with 8 flip flop and count too.
    > So 16 flops
    >
    > It is stange if you only have 15 flops


    One bit is identical in both encodings. Thus two flops are optimized
    to one.

    Andy
     
    Andy, Sep 14, 2007
    #19
  20. ast

    Eric Smith Guest

    Pieter Hulshoff wrote:
    > I would expect the need for a Gray counter to already indicate that an extra
    > clock cycle should not be a huge issue, but I guess the OP will have to answer
    > that one. :) Signal transfer between clock areas should always be FF2FF IMHO,
    > and of course an extra FF to take care of meta stability issues.


    If the reason for using gray code counters is to compare FIFO pointers
    where the read and write pointers are in different clock domains, you
    don't want to do it by introducing synchronizers. The synchronizers will
    avoid metastability, but will not guarantee that you get a correct coherent
    synchronized result. That's the reason for wanting gray code counter.

    The simplest approach that doesn't add extra latency to the output is to use
    a register that holds the current gray code count, and have that drive a
    gray-to-binary converter, incrementer, and binary-to-gray converter, which
    feeds the inputs of the register.

    Wikipedia has references to other methods:
    http://en.wikipedia.org/wiki/Gray_code#Gray-code_counters_and_arithmetic
     
    Eric Smith, Sep 14, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. The Eeediot
    Replies:
    3
    Views:
    2,307
    =?Utf-8?B?UnVsaW4gSG9uZw==?=
    Dec 22, 2004
  2. Olaf
    Replies:
    4
    Views:
    3,140
    Ahmed Samieh
    Apr 30, 2007
  3. George2
    Replies:
    1
    Views:
    852
    Alf P. Steinbach
    Jan 31, 2008
  4. baigsku
    Replies:
    1
    Views:
    1,532
    joris
    Dec 14, 2009
  5. fofo

    A gray counter

    fofo, Dec 19, 2011, in forum: VHDL
    Replies:
    3
    Views:
    1,304
    eliascm
    Dec 20, 2011
Loading...

Share This Page