The explanation of gray code “quadrant” technique

[Altera_Forum]

Many articles discuss about the benefits of using gray counter to design a FIFO. 

One of the advantage is we can use the quadrant coding method to determine the FIFO empty and full condition.  Yes, i can easily see how the downloaded code works through my simulation. Looking at the code for 2 days, i still not able to decode the logic behind :(  How is this quadrant gray counter technique to determine is the FIFO empty or full?  Any hint or guideline to this technique?  I'm more interested to the logic behind, how is this technique working instead to have working code. I could not see the clue of xor / xnor the read and write gray counter value to meet 1 of the empty of full criteria. Of course another criteria is write counter = read counter! Hope you guys can help me.  Thanks, fpga89

[Altera_Forum]

--- Quote Start ---  Many articles discuss about the benefits of using gray counter to design a FIFO. One of the advantage is we can use the quadrant coding method to determine the FIFO empty and full condition.  Yes, i can easily see how the downloaded code works through my simulation. Looking at the code for 2 days, i still not able to decode the logic behind :(  How is this quadrant gray counter technique to determine is the FIFO empty or full?  Any hint or guideline to this technique?  I'm more interested to the logic behind, how is this technique working instead to have working code. I could not see the clue of xor / xnor the read and write gray counter value to meet 1 of the empty of full criteria. Of course another criteria is write counter = read counter! Hope you guys can help me.  Thanks, fpga89  --- Quote End ---    Below is my understanding but have never designed one.   firstly, The dc fifo is usually ready made from vendors. In fact its design details is an ASIC specialty and varies. It might seem waste of time to redesign one but it is useful to know what goes into it and yes to design your own such as in the following case.  Many of us rush for vendor's dc fifo whenever we face clock domain transfer. This could be overkill because dc fifo's main extra logic and speed troubles can be avoided completely by designing your own if your rate of write/read is predetermined by design and simple. In other words you just use one dc ram without any cross domain logic then you write and read under your own control without need for reading empty/full flags.  For a commercial dc fifo, the main issue is deciding empty/full flags for the user to control the transfer.    dc fifos use one write and one read binary counters that are incremented for addressing, plus one write and one read gray counter followers for comparison.   imagine 8 words deep fifo with 3 bit counters,   -at start both counters = 000 so this equality means empty,   -when both are 001 then it means one word was written then read so is empty,  -When write counter > read counter or the reverse then it is neither full nor empty,  -eventually the write or read counters will roll over to 000 and re-increment,  - A full flag is decided if write count rolled to 000 and read count is 000    Thus both empty or full are decided from equality but we need to know the previous direction of fifo. This can be done by adding one extra bit to counters to become four bits. So 1000 and 0000 means full while 0000 and 0000 means empty. i.e. unequal msb but other bits equal = full and equal msb and other bits equal = empty.    An alternative to the extra bit is no extra bit but instead read two msbs to decide which quadrant of address space was each pointer in when equality occurred now. Thus if write pointer was 00- and read pointer was 10- and then when both became 100 then it means it was heading towards full and so full flag is asserted.    Similarly if write pointer was 10- and read pointer was 00- then both became 100 then it was heading towards empty and so empty flag is asserted.     This quadrant comparison is done asynchronously and so is not sensitive to clocks.    In all cases grey counter is used for comparison because only one bit changes per increment. If this bit goes wrong across domains then it doesn’t cause trouble because it implies one count value wrong (either previous count stays or new count arrived) and fifo space plus synchroniser delays should accommodate this event.    If however timing is so bad(large skew) that grey counter changes two bits or more at arrival then fifo will fail as the two pointers lose track of each other.

[Altera_Forum]

Thanks Kaz for the explanation. It's help :) 

I understand that gray counter is being used is because only 1 bit change at once time.  Another question is if i insist to use binary counter in my FIFO implementation and i manage to close all the timing through STA. Does this indicate it is safe to use binary counter? :p

[Altera_Forum]

--- Quote Start ---   Another question is if i insist to use binary counter in my FIFO implementation and i manage to close all the timing through STA. Does this indicate it is safe to use binary counter? :p  --- Quote End ---    If your fifo is dual clock and its two clocks are unrelated then your assumption of closing timing can't be true across clock domain.  BTW, if you set megawizard to fifo with no flag detection then you are done a simple fifo that does not care about clock domain and leaves control to you. I assume we will get a fifo with just binary addressing for write and read.

[Altera_Forum]

Thanks again Kaz. I just try to design a asynchronous dcfifo from scratch. 

Of course, hope to improve my coding skill throughout my work. That is why i keep reading papers and try to understand why they do in such ways. :)  Appreciate your sharing!

[Altera_Forum]

Don't. Just use the one provided by Altera. 

If you need to cross two unrelated clock domains, select a DCFIFO with 2 or more synchronization stages. If you need to cross two related clock domains, select a DCFIFO with 1 synchronization stage.

[Altera_Forum]

Just for sharing purpose: 

 This 2 papers provide a very good idea and fundamental explanation to the asynchronous dcfifo design. 1) http://www.sunburst-design.com/papers/cummingssnug2002sj_fifo1.pdf (Conventional Method) 2) http://www.sunburst-design.com/papers/cummingssnug2002sj_fifo2.pdf (Quadrant Selection Method)