Continue to Site

# Designing asynchronous FIFO with odd number depth

Status
Not open for further replies.

#### fragnen

##### Full Member level 4
How can we design an asynchronous FIFO with depth size in odd number?

FIFO IP has usually power-of-two size, but no principle problem to implement arbitrary size.

How can it be done ?

Hi,

from your question I assume you know how a FIFO works.
When you know that it work for an even number....why do you think it does not work for an odd number?
Where exactly do you see a problem and need help for this?

Klaus

Hi,

from your question I assume you know how a FIFO works.
When you know that it work for an even number....why do you think it does not work for an odd number?
Where exactly do you see a problem and need help for this?

Klaus
I am not getting a way to design an asynchronous FIFO with odd number depth. Can anybody please provide an example showing how for a particular odd number depth an asynchronous FIFO can be designed?

I am not getting a way to design an asynchronous FIFO with odd number depth. Can anybody please provide an example showing how for a particular odd number depth an asynchronous FIFO can be designed?
You probably can't figure it out as you likely don't have enough of an understanding on how a FIFO works. You should learn how a FIFO is implemented first. There are papers you can find on the subject.

The only difference between a FIFO that doesn't use all of the RAM depth is the calculation for FULL, otherwise you will have issues with the gray coding of the address if you try reducing the address range.

You probably can't figure it out as you likely don't have enough of an understanding on how a FIFO works. You should learn how a FIFO is implemented first. There are papers you can find on the subject.

The only difference between a FIFO that doesn't use all of the RAM depth is the calculation for FULL, otherwise you will have issues with the gray coding of the address if you try reducing the address range.
I have good understanding of it.

Hi,
I am not getting a way to design an asynchronous FIFO with odd number depth. Can anybody please provide an example showing how for a particular odd number depth an asynchronous FIFO can be designed?
The design is identical to a even count FIFO.
Where do you see a difference? Please explain clearly.

Show your design with even number....then we can discuss how to make it odd number.

Klaus

Hi,

The design is identical to a even count FIFO.
Where do you see a difference? Please explain clearly.

Show your design with even number....then we can discuss how to make it odd number.

Klaus
Like I said in my previous post the only difference should be the Full calculation. The rest of the logic should stay identical to a 2**N RAM depth FIFO.

Like I said in my previous post the only difference should be the Full calculation. The rest of the logic should stay identical to a 2**N RAM depth FIFO.
What about the grey code? We cannot get a grey code sequence for an odd depth. That is producing diffi ulty in designing g an asynchronous FIFO with odd number depth.

The Gray code (not "grey" because the name refers to Frank Gray and not a colour) is for safely transferring the write/read pointers between clock domains.
This can be done without Gray coding, but the latency in the FIFO will probably be higher.

What about the grey code? We cannot get a grey code sequence for an odd depth. That is producing diffi ulty in designing g an asynchronous FIFO with odd number depth.
Hmm, I already pointed out this issue in post #6. You don't really read the responses do you?

That is also why I mentioned that none of the logic changes between a 2**N depth FIFO and something less than a power of 2 FIFO. The pointers will cycle through all 2**N addresses and can therefore still be Gray code. Only the logic used to compute full needs to change as it will stop at some earlier address before it wraps around to the read pointer.

Last edited:

Hmm, I already pointed out this issue in post #6. You don't really read the responses do you?

That is also why I mentioned that none of the logic changes between a 2**N depth FIFO and something less than a power of 2 FIFO. The pointers will cycle through all 2**N addresses and can therefore still be Gray code. Only the logic used to compute full needs to change as it will stop at some earlier address before it wraps around to the read pointer.
I responded to post #10, because the OP apparently still thought that Gray coding is necessary for an asynchronous FIFO.
What you mention about "Full" is also true for calculation of the "Empty"/"read data available" signals, which must be done in the read clock domain.

Edit:
What do you mean with " The pointers will cycle through all 2**N addresses and can therefore still be Gray code " when the depth isn't a power of 2?
It doesn't sound correct.

Last edited:

You can use the entire RAM for the FIFO as the pointers just move through all the addresses as you write to the RAM (or read) so the clock domain crossing of the pointers using gray code can still be done with the N-bit addresses.

The depth is artificially set to something less than a power of 2 by not allowing the write pointer to catch up to the read pointer.

e.g.
can't gray code this sequence of 5 depth between the two clock domains, so requires another way to reliably transfer the address pointer.
write 0,1,2,3,4 (full)
write 0,1,2,3,4 (full)

can gray code this sequence of 5 depth as the addresses go through all 2**N addresses
write 0,1,2,3,4 (full)
write 5,6,7,0,1 (full)
only the calculations for the flags is more complex and doesn't have the issues with trying to transfer the pointer addresses.

I've also used an up/down counter to generate flags for non-power of 2 FIFOs. This avoids the need for gray code, but typically uses more flip-flops and logic.

I've never come across a design where I had to physically limit the addresses used by a FIFO to a subset of the power of 2 address range. Perhaps you have a specific use case in mind where that is a requirement that you can only use 2**N-an_odd_number of RAM locations and have that an_odd_number of locations reserved for something else?
--- Updated ---

std_match, I noticed I also added the wrong quote (yours #11) by mistake as I was trying to quote #10. I went back and fixed that.

Last edited:

can gray code this sequence of 5 depth as the addresses go through all 2**N addresses
write 0,1,2,3,4 (full)
write 5,6,7,0,1 (full)
only the calculations for the flags is more complex and doesn't have the issues with trying to transfer the pointer addresses.
Ok, you mean that there are "real" read/write pointers wrapping from 4 to 0 for accessing the memory, and "virtual" Gray-coded 2**N read/write pointers to detect full/empty?
I now see how it can work. Normal logic for calculating "empty" and some slightly modified arithmetic for calculating "full" (basically subtracting a constant from the read pointer before comparing with the write pointer).

Ok, you mean that there are "real" read/write pointers wrapping from 4 to 0 for accessing the memory, and "virtual" Gray-coded 2**N read/write pointers to detect full/empty?
I don't mean real pointers into the RAM that are 0 to 4 addresses accessing memory (that is what the OP is trying to find a Gray-coding solution for).

Instead I suggest using real pointers into memory that are the normal 0 to 7 addresses (0 to 2**N-1) and just adjusting the calculation like you suggested to subtract out the unused space to limit the FIFO to the correct size. Limiting the FIFO depth this way doesn't change the standard clock domain crossing methodology of the FIFO pointers using binary-to-Gray and Gray-to-binary conversions and just modifies how the Full flag is computed.

I don't see the point in limiting the RAM a FIFO uses, as a FIFO can be any size as long as the aggregate rate in and out of the FIFO can be met without overflowing the FIFO. I wonder if the OP has some requirement to detect when some specific amount of data is in the FIFO before reading and is taking a naive approach to the problem (instead of just adding another level flag to the FIFO to report that enough data is in the FIFO).

I'll admit I've never used this type of addressing scheme for a FIFO but instead have used it on circular buffers that had some unusual requirements that called for programmable buffer depths.

You want a physical FIFO that exceeds the maximum
depth anticipated. There is no value at all (other than
a passing grade for a stupid homework assignment)
in an odd-number-of-bits dual port RAM block. It is
much more efficient of design and layout, and hardly
impactful to layout area, to go smaller than a M*N
array and using binary counters to index read and
write position, means at least one of the dimension
will "want" a straight binary field.

You can put the write-index-counter-overflow limit
at an odd number if you like. That's as much thought
as -I'd- spend on it.

I thought the thread was about creating an asynchronous FIFO from a memory area that actually has a size that isn't a power of 2,
not using a 2**N area but make the the FIFO look smaller.

Both for ASICs and FPGAs, it is easy to create memory areas with a size that isn't a power of 2, but there is often no good reason for it.

Thread was to design an asynchronous FIFO with odd number of depth. For example to design a FIFO of depth 33 where we do not want to design the asynchronous FIFO of depth 34 and use it for depth 33. We want to save area so that if my requirement was up to depth 33 , we shall design uptown depth 33 only and not at all uptown depth 34 as we want to save area and not to loose area for an extra 34th location. Hope it clarifies the question in the thread.

Target is not to design an asynchronous FIFO of depth 34 and then derive an asynchronous FIFO of depth 33 as it waste the area for the 34th location.

Thread was to design an asynchronous FIFO with odd number of depth. For example to design a FIFO of depth 33 where we do not want to design the asynchronous FIFO of depth 34 and use it for depth 33. We want to save area so that if my requirement was up to depth 33 , we shall design uptown depth 33 only and not at all uptown depth 34 as we want to save area and not to loose area for an extra 34th location. Hope it clarifies the question in the thread.

Target is not to design an asynchronous FIFO of depth 34 and then derive an asynchronous FIFO of depth 33 as it waste the area for the 34th location.
Ok, so you literally meant "odd". I think "odd size FIFO" for most designers mean that the size isn't a power of 2.
I don't think "odd" or "even" has any effect on the clock domain crossing problem in your case.
Memory size 32 and 64 is easy with Gray-coding. Other sizes are more difficult, but I don't see a difference between 33 and 34. Even if you manage to design a Gray-similar coding for an even size like 34, you still have the problem of converting it to the address range 0-33.
I think you should forget Gray-coding as the solution when the memory size isn't a power of 2, and then it doesn't matter if the size is odd or even.

Edit:
or use "real" pointers 0-32 (for size=33) to access the RAM and "virtual" Gray-coded pointers 0-63 for the empty/full calculation like I suggested in post #15.

Status
Not open for further replies.