Gray counter

[ast]

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

 

[Pieter Hulshoff]

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

 

[Jonathan Bromley]

On Thu, 13 Sep 2007 15:00:38 +0200, "ast" <ast@ast.com> 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
jonathan.bromley@MYCOMPANY.com
http://www.MYCOMPANY.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Andy]

On Sep 13, 8:04 am, Pieter Hulshoff <phuls...@xs4all.nl> 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

 

[ast]

"ast" <ast@ast.com> a écrit dans le message de news: 46e93478$0$5074$ba4acef3@news.orange.fr...

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.

 

[Pieter Hulshoff]

Andy wrote:

On Sep 13, 8:04 am, Pieter Hulshoff <phuls...@xs4all.nl> 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

 

[Petter Gustad]

"ast" <ast@ast.com> 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?

 

[KJ]

On Sep 13, 9:00 am, "ast" <a...@ast.com> 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.

thx

Besides the usual 'Google', you might want to read the following
couple of articles for inspiration
http://www.pldesignline.com/196604078
http://www.pldesignline.com/showArticle.jhtml?articleID=201002340

KJ

 

[Kai Harrekilde-Petersen]

"ast" <ast@ast.com> writes:

"ast" <ast@ast.com> a écrit dans le message de news: 46e93478$0$5074$ba4acef3@news.orange.fr...
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>

 

[Zara]

On Thu, 13 Sep 2007 15:00:38 +0200, "ast" <ast@ast.com> 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]

On Fri, 14 Sep 2007 07:41:29 +0200, Zara <me_zara@dea.spamcon.org>
wrote:

On Thu, 13 Sep 2007 15:00:38 +0200, "ast" <ast@ast.com> 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

 

[Michael Jřrgensen]

"Zara" <me_zara@dea.spamcon.org> wrote in message
news:uuake3da61rtmp18u3q4bcrolqk3v5f1ot@4ax.com...

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.

 

[Zara]

On Fri, 14 Sep 2007 10:14:15 +0200, "Michael Jřrgensen"
<ingen@ukendt.dk> wrote:

"Zara" <me_zara@dea.spamcon.org> wrote in message
news:uuake3da61rtmp18u3q4bcrolqk3v5f1ot@4ax.com...

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]

On Fri, 14 Sep 2007 10:14:15 +0200, "Michael Jřrgensen"
<ingen@ukendt.dk> wrote:

"Zara" <me_zara@dea.spamcon.org> wrote in message
news:uuake3da61rtmp18u3q4bcrolqk3v5f1ot@4ax.com...

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

 

[Charles, NG]

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

 

[Zara]

On Fri, 14 Sep 2007 11:46:34 +0200, Zara <me_zara@dea.spamcon.org>
wrote:

On Fri, 14 Sep 2007 10:14:15 +0200, "Michael Jřrgensen"
ingen@ukendt.dk> wrote:


"Zara" <me_zara@dea.spamcon.org> wrote in message
news:uuake3da61rtmp18u3q4bcrolqk3v5f1ot@4ax.com...

...

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

 

[Andy]

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

 

[ast]

"Andy" <jonesandy@comcast.net> a écrit dans le message de news: 1189780824.417965.211270@o80g2000hse.googlegroups.com...

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

 

[Andy]

On Sep 14, 1:47 pm, "ast" <a...@ast.com> wrote:

"Andy" <jonesa...@comcast.net> a écrit dans le message de news: 1189780824.417965.211...@o80g2000hse.googlegroups.com...



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

 

[Eric Smith]

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