EDAboard.com | EDAboard.de | EDAboard.co.uk | WTWH Media

elektroda.net NewsGroups Forum Index - Verilog Language - **Asynchronous FIFO with depth that is not a power of 2**

Guest

Wed May 14, 2008 8:42 pm

I am trying to design an asynchronous FIFO that works with two clock

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

Can this be done using binary pointers instead of using Gray pointers?

Maybe we can use handshaking technique, exchanging 'ready' and

'acknowledge' between the two sides whenever the write/read pointer is

to be sent across clock domain. So suppose we want to send the write

pointer from clk_A domain to clk_B domain. When write pointer in clk_A

domain changes, it generates a 'ready' that goes to clk_B domain. This

'ready' is synchronized in clk_B domain and then clk_B reads the value

of the write pointer. Then clk_B domain sends 'acknowledge' back to

clk_A domain (where it is synchronized). Only after clk_A domain gets

this 'acknowledge' back, it can change the write pointer value. Is

this concept correct? If yes, then I guess there is still a problem.

In the above example, the write side is on faster clock. If the write

pointer cannot change until write side gets back 'acknowledge', then

we probabaly need to stall writes to the FIFO, correct?

Please advise how this can be done. Thanks.

Guest

Wed May 14, 2008 10:27 pm

googler wrote:

I am trying to design an asynchronous FIFO that works with two clock

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

snip

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

snip

You can use a Gray pointer but with one slight change. Increment from

Gray 343 to Gray -344. There is still only one bit (the MSbit)

change.

Gray counters are often easier to design as binary counters with a

binary-to-gray conversion such that you make the increment from binary

343 to binary -344 and let the Gray conversion do its stuff.

If your depth was an odd number of elements, it wouldn't work with

this Gray adjustment. Since you're even, you're set.

- John_H

Guest

Wed May 14, 2008 11:35 pm

googler wrote:

I am trying to design an asynchronous FIFO that works with two clock

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

Please advise how this can be done. Thanks.

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

Please advise how this can be done. Thanks.

You can make any even-numbered Graycoded sequence. Instead of counting

from Gray(0) to Gray(2^N-1), where Gray(x) is the Gray version of the

sequential number x and N = ceil(log2(FIFO_DEPTH)), count from:

Gray(2^N/2 - FIFO_DEPTH/2) to Gray(2^N/2 + FIFO_DEPTH/2 - 1)

So in your case, FIFO_DEPTH=688 and N=10, so you would count from

Gray(168) to Gray(855)

and then roll over back to Gray(168).

Gray(168)=0011111100 and Gray(855)=1011111100

which you can see differ only in bit 9, so there is a smooth Gray-like

transition when you roll over.

In case you don't know the Gray conversion,

Gray(x[y]) = x[y]^x[y+1]

where [y] is bit y and ^ is an XOR.

-Kevin

Guest

Thu May 15, 2008 5:20 am

googler wrote:

[snip]

Thank you Kevin and John_H for your replies. I will try your ideas and

I hope it will solve my problem (it is a little more complicated than

I described but that was the main problem I was facing).

Since we are discussing this particular topic, I will take this

opportunity to get some concepts clear. Basically I am not totally

clear on why gray pointers are being used instead of just using binary

pointers and synchronizing them in the other clock domain. I have done

some reading on this and they say that if multiple bits in a pointer

change at the same time on a clock edge, then the data obtained after

synchronization may not be correct. My first question is, why will the

synchronized data not be correct? Is it because of the fact that there

is always a chance (however small) that the output of a synchronizer

may not be stable, which means it can be any value 0 or 1?

-------------

Thank you Kevin and John_H for your replies. I will try your ideas and

I hope it will solve my problem (it is a little more complicated than

I described but that was the main problem I was facing).

Since we are discussing this particular topic, I will take this

opportunity to get some concepts clear. Basically I am not totally

clear on why gray pointers are being used instead of just using binary

pointers and synchronizing them in the other clock domain. I have done

some reading on this and they say that if multiple bits in a pointer

change at the same time on a clock edge, then the data obtained after

synchronization may not be correct. My first question is, why will the

synchronized data not be correct? Is it because of the fact that there

is always a chance (however small) that the output of a synchronizer

may not be stable, which means it can be any value 0 or 1?

-------------

The problem isn't whether it's a one or zero, the problem is catching

them all on the same side of the transition. Imagine a bunch of people

lined up in the hallway against the walls. When a whistle blows, one or

more of those against each wall must race to the other side and wait

until the next whistle just like bits changing state in a counter.

Pictures are taken at regular intervals with no knowledge of when the

whistle blows. Most of the pictures show people lined up on both sides

of the hallway. Occasionally you see the motion of someone still racing

from one side to the other. You can decide pretty quickly if someone is

considered on the right or the left side of the hallway but the players

don't all have the same reflexes so a photo may show one person on the

other side of the hallway while another hasn't yet gotten very far.

They *should* all be pre-journey or post-journey but sometimes you get a

mixed set.

It's because bits don't change at the same attosecond (or get sampled at

the same point for that matter) that the occasional sample has some bits

that have transitioned and some that haven't yet though they were all

supposed to run on the same whistle.

The Gray counter (thanks, Frank Gray of Bell Labs) gives you just one

person running from one side of the hall to the other for any one

whistle blow. Since only one bit changes, the photo can always say

right or left side even if it rarely takes a moment longer to figure out

which side.

-------------

If the above is true, then even in case of gray pointer the

synchronizer output may be erroneous. True, the error will be only in

one bit, but it is still an error and may cause things to fail, right?

For example, if the write pointer increments and causes the FIFO to

become full, and at the same time the value of the write pointer is

read incorrectly on the other side as the old value, then the read

side will not know that the FIFO has become full, which is wrong.

(Well, people may argue that read side usually does not need the

'full' flag, but there might be some logic there that needs it.. or

the read side may need to calculate the number of current entries,

etc.)

synchronizer output may be erroneous. True, the error will be only in

one bit, but it is still an error and may cause things to fail, right?

For example, if the write pointer increments and causes the FIFO to

become full, and at the same time the value of the write pointer is

read incorrectly on the other side as the old value, then the read

side will not know that the FIFO has become full, which is wrong.

(Well, people may argue that read side usually does not need the

'full' flag, but there might be some logic there that needs it.. or

the read side may need to calculate the number of current entries,

etc.)

The read side doesn't need to know that the FIFO is full, just that

there's data available since it's the write side that needs to avoid

overfilling the FIFO. Having the read side be a cycle late in knowing

that there's more data is not a problem in any system I've ever seen or

imagined. The write side of the FIFO similarly doesn't need nanosecond

accurate empty (or fill level) information but needs to know when it

should stop providing data. If you want a burst scheme of a certain

size and want to make sure two bursts butt up against each other to

avoid any possibility of read gaps, it's not an issue of providing the

flags faster, it's an issue of sizing your FIFO so the delays inherent

in an asynchronous system are part of your latency/bandwidth budget.

Asynchronous crossings are where green engineers often demonstrate the

greatest trouble. Getting to understand and work around those

asynchronous boundaries makes life in this digital world much easier.

Happy coding,

- John_H

Guest

Thu May 15, 2008 6:34 am

On May 14, 5:35 pm, Kevin Neilson

<kevin_neil...@removethiscomcast.net> wrote:

googler wrote:

I am trying to design an asynchronous FIFO that works with two clock

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

Please advise how this can be done. Thanks.

You can make any even-numbered Graycoded sequence. Instead of counting

from Gray(0) to Gray(2^N-1), where Gray(x) is the Gray version of the

sequential number x and N = ceil(log2(FIFO_DEPTH)), count from:

Gray(2^N/2 - FIFO_DEPTH/2) to Gray(2^N/2 + FIFO_DEPTH/2 - 1)

[snip]

I am trying to design an asynchronous FIFO that works with two clock

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

Please advise how this can be done. Thanks.

You can make any even-numbered Graycoded sequence. Instead of counting

from Gray(0) to Gray(2^N-1), where Gray(x) is the Gray version of the

sequential number x and N = ceil(log2(FIFO_DEPTH)), count from:

Gray(2^N/2 - FIFO_DEPTH/2) to Gray(2^N/2 + FIFO_DEPTH/2 - 1)

[snip]

Thank you Kevin and John_H for your replies. I will try your ideas and

I hope it will solve my problem (it is a little more complicated than

I described but that was the main problem I was facing).

Since we are discussing this particular topic, I will take this

opportunity to get some concepts clear. Basically I am not totally

clear on why gray pointers are being used instead of just using binary

pointers and synchronizing them in the other clock domain. I have done

some reading on this and they say that if multiple bits in a pointer

change at the same time on a clock edge, then the data obtained after

synchronization may not be correct. My first question is, why will the

synchronized data not be correct? Is it because of the fact that there

is always a chance (however small) that the output of a synchronizer

may not be stable, which means it can be any value 0 or 1?

If the above is true, then even in case of gray pointer the

synchronizer output may be erroneous. True, the error will be only in

one bit, but it is still an error and may cause things to fail, right?

For example, if the write pointer increments and causes the FIFO to

become full, and at the same time the value of the write pointer is

read incorrectly on the other side as the old value, then the read

side will not know that the FIFO has become full, which is wrong.

(Well, people may argue that read side usually does not need the

'full' flag, but there might be some logic there that needs it.. or

the read side may need to calculate the number of current entries,

etc.)

Guest

Sat Oct 28, 2017 11:04 am

On Thursday, 15 May 2008 04:05:03 UTC+5:30, Kevin Neilson wrote:

googler wrote:

I am trying to design an asynchronous FIFO that works with two clock

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

Please advise how this can be done. Thanks.

You can make any even-numbered Graycoded sequence. Instead of counting

from Gray(0) to Gray(2^N-1), where Gray(x) is the Gray version of the

sequential number x and N = ceil(log2(FIFO_DEPTH)), count from:

Gray(2^N/2 - FIFO_DEPTH/2) to Gray(2^N/2 + FIFO_DEPTH/2 - 1)

So in your case, FIFO_DEPTH=688 and N=10, so you would count from

Gray(168) to Gray(855)

and then roll over back to Gray(168).

Gray(168)=0011111100 and Gray(855)=1011111100

which you can see differ only in bit 9, so there is a smooth Gray-like

transition when you roll over.

In case you don't know the Gray conversion,

Gray(x[y]) = x[y]^x[y+1]

where [y] is bit y and ^ is an XOR.

-Kevin

I am trying to design an asynchronous FIFO that works with two clock

domains clk_A and clk_B. Writes to the FIFO happen on clk_A and reads

happen on clk_B. clk_A is faster than clk_B. I thought about using

gray-coded write and read pointers that is usually recommended for

designing async fifos, but the problem is that in this case the depth

of the FIFO is 688, which is not a power of 2. So it seems I cannot

use the Gray pointer technique. Is that right?

Please advise how this can be done. Thanks.

You can make any even-numbered Graycoded sequence. Instead of counting

from Gray(0) to Gray(2^N-1), where Gray(x) is the Gray version of the

sequential number x and N = ceil(log2(FIFO_DEPTH)), count from:

Gray(2^N/2 - FIFO_DEPTH/2) to Gray(2^N/2 + FIFO_DEPTH/2 - 1)

So in your case, FIFO_DEPTH=688 and N=10, so you would count from

Gray(168) to Gray(855)

and then roll over back to Gray(168).

Gray(168)=0011111100 and Gray(855)=1011111100

which you can see differ only in bit 9, so there is a smooth Gray-like

transition when you roll over.

In case you don't know the Gray conversion,

Gray(x[y]) = x[y]^x[y+1]

where [y] is bit y and ^ is an XOR.

-Kevin

Hi Kevin,

In your method How can we generated Full and Empty signals?

Thanks in advance

Regards,

Ketan

Guest

Wed Nov 01, 2017 8:02 pm

Hi Kevin,

In your method How can we generated Full and Empty signals?

Thanks in advance

Regards,

Ketan

Ketan,

First, let me say, if you can get a FIFO from somewhere else, do so. I know it's not always easy to find one, but there are a lot of little things that can go wrong when you make your own. Also, I would just round the depth up to a power of 2, especially if you are using FPGA blockRAM.

From my recollection the empty logic would be something like below. Note that you don't have to do Gray-to-binary conversion, which can use many levels of logic. Only binary-to-Gray is used.

always@(posedge rd_clk) begin

// Update pointers on FIFO read

if (rd_en) begin

// next_next_rd_ptr is the pointer 2 ahead of rd_ptr

if (next_next_rd_ptr==855) next_next_rd_ptr <= 168; // ptr rolls from 855 to 168

else next_next_rd_ptr <= next_next_rd_ptr + 1;

// You can use rd_ptr as the read address to the RAM.

// You use rd_ptr_gray for empty and full flag logic.

next_rd_ptr <= next_next_rd_ptr;

rd_ptr <= next_rd_ptr;

next_rd_ptr_gray <= Gray(next_next_rd_ptr); // Gray() is the fcn described previously

rd_ptr_gray <= Gray(next_rd_ptr);

end

// The empty flag is asserted if the pointers match or if you are reading

// the FIFO and the pointers will match after the read.

// Please note that you may re-register wr_ptr_gray in this clock

// domain to be extra-safe. That would add a little latency.

empty <= rd_ptr_gray==wr_ptr_gray || rd_en && next_rd_ptr_gray==wr_ptr_gray;

// The almost-empty flag would require an extra pointer:

almost_empty <= next_rd_ptr_gray==wr_ptr_gray || rd_en && next_next_rd_ptr_gray==wr_ptr_gray;

end

elektroda.net NewsGroups Forum Index - Verilog Language - **Asynchronous FIFO with depth that is not a power of 2**