# Gray counter

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

1. ### astGuest

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

2. ### Pieter HulshoffGuest

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

3. ### Jonathan BromleyGuest

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
4. ### AndyGuest

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
5. ### astGuest

"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
6. ### Pieter HulshoffGuest

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

"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?

8. ### KJGuest

KJ, Sep 13, 2007
9. ### Kai Harrekilde-PetersenGuest

"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
10. ### ZaraGuest

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
11. ### ZaraGuest

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
12. ### Michael JørgensenGuest

"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
13. ### ZaraGuest

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
14. ### ZaraGuest

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
15. ### Charles, NGGuest

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
input pPar;
reg vAccumulate;
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
16. ### ZaraGuest

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
17. ### AndyGuest

> 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
18. ### astGuest

"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
19. ### AndyGuest

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
20. ### Eric SmithGuest

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