Gray counter

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

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

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

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

Andy

"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[i] = B[i+1] XOR B[i]

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[i] = B[i+1] XOR G[i]

This can be easily translated in VHDL.

ast

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

Pieter Hulshoff

"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

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/showArti...leID=201002340

KJ

KJ

"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

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