Asynchronous FIFO: counting number of elements

[googler]

Hi,

For asynchronous FIFO implementation, I usually use the technique with
gray-coded read and write pointers. To elaborate, it uses n+1 bit
pointers (instead of the n bits) for both read and write and these are
stored in registers as gray codes, synchronized over to the other
clock domain and compared with the gray pointer there. For empty, all
bits in gray-coded read and write pointers should be equal. For full,
2 MSBs of the gray-coded pointers should be inverted with respect to
the other, but the other bits should match.

Now, I have read a few papers on this topic (including Cliff
Cummings'). I didn't find any explanation on how to calculate the
number of elements in the FIFO (which can also help with finding
'almost full/empty' statuses). I have the following questions.

1. Is it a viable option to convert the synchronized gray read pointer
to binary value and subtract it from the binary value of the write
pointer to calculate the number of elements in the fifo (on the write
side)? (Similarly for the other side)
2. If it is, then I would think we can use this number to determine
whether the fifo is almost full (with respect to a programmable value)
on the write side. However, I do not see this is getting done
anywhere. Instead, I read some papers that say using gray-coded
pointers restrict the generation of 'almost full/empty' flags (when
using arbitrary programmable numbers). Is that true, or is it possible
to generate 'almost full/empty' statuses using this approach?

Thanks.

 

[Mark Curry]

In article <dd9dac9d-9a62-4ff9-9b87-3574fddc13d7@h4g2000pbe.googlegroups.com>,
googler <pinaki_m77@yahoo.com> wrote:

Hi,

For asynchronous FIFO implementation, I usually use the technique with
gray-coded read and write pointers. To elaborate, it uses n+1 bit
pointers (instead of the n bits) for both read and write and these are
stored in registers as gray codes, synchronized over to the other
clock domain and compared with the gray pointer there. For empty, all
bits in gray-coded read and write pointers should be equal. For full,
2 MSBs of the gray-coded pointers should be inverted with respect to
the other, but the other bits should match.

Now, I have read a few papers on this topic (including Cliff
Cummings'). I didn't find any explanation on how to calculate the
number of elements in the FIFO (which can also help with finding
'almost full/empty' statuses). I have the following questions.

1. Is it a viable option to convert the synchronized gray read pointer
to binary value and subtract it from the binary value of the write
pointer to calculate the number of elements in the fifo (on the write
side)? (Similarly for the other side)
2. If it is, then I would think we can use this number to determine
whether the fifo is almost full (with respect to a programmable value)
on the write side. However, I do not see this is getting done
anywhere. Instead, I read some papers that say using gray-coded
pointers restrict the generation of 'almost full/empty' flags (when
using arbitrary programmable numbers). Is that true, or is it possible
to generate 'almost full/empty' statuses using this approach?

It's certainly possible to do what you're suggesting. You'll likely
have some large critical paths in the calculations.

Another option to consider for specific almost full/empty (i.e. within say 1,
or 2 slots from begin empty/full). Have the comparisons done against another
ptr - ptr_plus_one, ptr_plus_two - where those values are the next
values of your respective counters. I.e. compare rd_ptr_plus_one == wr_ptr
you're one slot from begin empty. Similar on write side.

This way you're critical path doesn't get worse (you have to maintain
another set of ptrs however).

--Mark