Abstract:
A system for detecting during write/read operations the status of a FIFO memory having N memory locations includes a first and a second Gray-code counter each configured to take values out of 2*N possible values. The first and second Gray-code counters are configured to be initialized to a value J, and incremented on each write operation and each said read operation. The first and second Gray-code counters are configured to be set to the value 0 if their count values reach 2*N. A comparator block monitors the distance of the value of the first counter to the value of said second counter and detects the full status of the FIFO memory if that distance is equal to N. The comparator block may similarly detect the empty status of the FIFO memory if the distance in question is equal to 0.

Description:
RELATED APPLICATION 
       [0001]    The present application claims priority of European Patent Application No. 06116947.0 filed Jul. 11, 2006, entitled METHOD AND SYSTEM FOR CONTROLLING DATA SYNCHRONIZATION IN FIFO MEMORIES, AND RELATED SYNCHRONIZER, which is incorporated herein in its entirety by this reference. 
       FIELD OF THE INVENTION 
       [0002]    The present invention relates to techniques for controlling data synchronization in FIFO (First-In First-Out) memories. More particularly, the invention relates to use in FIFO memories having two separate interfaces, one to insert data (write interface) and the other one to extract data (read interface) running in general at different clock frequencies. 
       DESCRIPTION OF THE RELATED ART 
       [0003]    In digital logic circuits, FIFO memories are often used to exchange data, commands or any other kind of information between two asynchronous clock domains. 
         [0004]    Usually, FIFO memories have two separate interfaces: the first one is used for inserting data (write interface) and the other one for extracting data (read interface). In general, these interfaces run at different clock frequencies. Preferably, each interface is composed of an address bus and a data bus, plus additional control signals such as an enable signal used to activate the related read or write operation. 
         [0005]    In such systems two pointers, usually implemented using registers, are present: 
         [0006]    a write pointer in the write clock domain points to the first location available to accept new data, and 
         [0007]    a read pointer in the read clock domain points to the first element of the FIFO containing valid data. 
         [0008]    The FIFO is often addressed in a circular way by means of pointers that advance from the current address location to the next memory location “wrapping” to the first memory address location when the current address location is the last FIFO memory location. 
         [0009]    The current FIFO status can easily be derived from a comparison of these two pointers. The FIFO is considered “EMPTY” when the write pointer and the read pointer point to the same FIFO location (i.e. both have the same value). When the write pointer points to the memory location immediately preceding the read pointer and new data is inserted, the insertion of data will cause the write pointer to be incremented and get the same value as the read pointer: the FIFO will thus be “FULL”, but this condition is—per se—identical to the one used to identify the “EMPTY” status, therefore an extra flag must be used to distinguish between the “EMPTY” and “FULL” FIFO status. 
         [0010]    The main issue to address in such systems is the difficulty to compare two multi-bit values across the two clock-domain boundaries. Due to different “slacks” of the different signals comprising the value to be compared, a change in the source clock domain can be wrongly sampled in the destination clock domain, leading to a wrong comparison. 
         [0011]    Various solutions exist in the prior art to address this meta-stability problem. Some of these make use of a synchronization mechanism based on pointers coded with the Gray-Coding scheme and/or counters re-synchronized across the two clock domains and used to track the FIFO status such as “FIFO_FULL”, “FIFO_EMPTY”, “ALMOST_FULL”, and “ALMOST_EMPTY”. 
         [0012]    One of the main advantages of the Gray-code is that a Gray-code counter always advances with one bit change, and therefore the value sampled in the destination clock domain can only be the preceding value or the current source value. Both values are in any case valid and do not compromise the correct behavior of the system. 
         [0013]    Additionally, this property of Gray-code based counters to increment or decrement only by a single bit change reduces the switching activity and therefore the dynamic power consumption. 
         [0014]    However, in order to “wrap” from the last Gray-coded value of a given sequence to the first one, preserving the property to have only one bit change, the number of elements of the Gray-sequence must be even. Current implementations of Gray-code based data synchronization systems for FIFO memories have been therefore based so far on an even number of FIFO locations. 
         [0015]    To overcome this limitation, other solutions abandoned the use of Gray-code moving towards different coding scheme. This often entails an increase in the number of bits required to encode a given number of memory locations with respect to the one obtained using the Gray-code. 
         [0016]    As an example, a “TWO-HOT” encoding requires N bits to encode each pointer of a FIFO having N memory locations with N being any positive integer, while the same system using Gray-code pointers would only require a number of bits equal to (log 2 N, i.e. the basis-2 logarithm of N) rounded to the next valid integer value.  FIG. 1  shows a comparison of bit consumption in the TWO-HOT bit encoding and the Gray-code. 
       SUMMARY OF THE INVENTION 
       [0017]    The object of the present invention is to provide an improved arrangement for applying Gray-coding techniques in a more efficient manner to the control of FIFO memories of any size. 
         [0018]    According to the present invention, that object is achieved by means of a method having the features set forth in the claims that follow. The invention relates also to a corresponding system (i.e. a FIFO memory device) and to a digital logic circuit (essentially a synchronizer) where the FIFO memory is used to allow data exchange between two asynchronous clock domains. 
         [0019]    The claims are an integral part of the disclosure of the invention provided herein. 
         [0020]    An embodiment of a method of the present invention relating to the status of a FIFO memory having N memory locations includes the steps of providing first and second Gray-code counts each configured to take values out of 2*N possible values, initializing the first and second Gray-code counts to a value J, incrementing the first Gray-code count on each such write operation, setting the first count to if the value of the first count reaches 2*N, incrementing the second Gray-code count on each such read operation and setting the second count to 0 if the value of the second counter reaches 2*N, monitoring the distance of the value of the first count to the value of the second count, and detecting the full status of the FIFO memory if the distance of the value of the first count to the value of the second count is equal to N. 
         [0021]    In another embodiment of the method of detecting the status of a FIFO memory, the method includes the steps of providing first and second Gray-code counts each, initializing the first and second Gray-code counts, incrementing the first Gray-code count on a write operation, incrementing the second Gray-code count on a read operation, monitoring the distance of the value of the first count to the value of the second count, and detecting the full status of the FIFO memory if the distance of the value of the first count to the value of the second count is equal to N, where N is the number of memory locations in the FIFO memory. 
         [0022]    An embodiment of a system or detecting the status of a FIFO memory (having N memory locations) during write/read operations includes a first and a second Gray-code counter each configured to take values out of 2*N possible value, configured to be initialized to a value J, configured to be incremented on each such read and write operation, and configured to be set to the value 0 if their count values reach 2*. The embodiment also includes a comparator block for monitoring the distance of the value of the first counter to the value of the second counter and detecting the full status of the FIFO memory if the distance of the value of the first counter to the value of the second counter is equal to N. 
         [0023]    Preferred embodiments of the arrangement described herein may take the form of a FIFO memory implemented either as a hardware FIFO implemented by using a memory array (such as e.g. a RAM) or as a “soft” FIFO implemented using flip-flops. 
         [0024]    Preferably, in the first type of FIFO memory the Gray-code is used only to generate the “FULL” and/or “EMPTY” flags while the read and write memory pointers are implemented by two different counters (one for each clock domain). 
         [0025]    Instead, for the second type of FIFO memory the Gray-code could be used for both generating the read and write memory pointers and implementing the “FULL” and/or “EMPTY” flags. The second solution is preferable for a small FIFO memory size. 
         [0026]    In both cases the FIFO can have any number of lines of memories (either odd or even numbers). 
         [0027]    In a preferred embodiment, the invention uses three Gray-code counters for generating the “FULL” and/or “EMPTY” flags for both hard and soft FIFO memories. 
         [0028]    For instance, in a FIFO memory with N elements, the three Gray-code counters may have a bit size of log 2 (2*N)=(log 2 N)+1 (once again rounded to the next integer). Each counter will count 2*N values and then will wrap to its initial state. Being this number even for any positive integer N, it can be encoded with a set of Gray-code symbols that can wrap respecting the principle of having only one bit changing between one value and the next one. 
         [0029]    Preferably, two of the three Gray-code counters will be initialized to the same initial Gray-code symbol value corresponding to position J (any of the 2*N symbols can be chosen as starting point); instead, the third Gray counter will be initialized to the symbol value corresponding to position J+N. 
         [0030]    In such an exemplary embodiment, the first Gray-code counter will lie in the read clock domain and will be referred to in the following as “read_gray_counter”, while the second counter will lie in the write clock domain and will be referred to as the “write_gray_counter”. The third counter can be placed either in the read clock domain and named “shifted_read_gray_counter” or in the write clock domain and named “shifted_write_gray_counter”, as will be explained in the following. The two solutions give rise to a dual implementation of the same underlying principle. 
         [0031]    In such an exemplary embodiment, the read_gray_counter is incremented after each read operation, and the write_gray_counter is incremented after each write operation. The third counter is incremented either on read operation if the counter is placed in the read clock domain (shifted_read_gray_counter) or on write operation if counter is placed in the write clock domain (shifted_write_gray_counter). 
         [0032]    Preferably, the FIFO “EMPTY” status is obtained in the read clock domain when the read_gray_counter value is equal to the synchronized write_gray_counter value in the same domain. 
         [0033]    The FIFO FULL status can be obtained in the write clock domain either when the shifted_write_gray_counter value is equal to the synchronized read_gray_counter value or when the write_gray_counter value is equal to the synchronized shifted_read_gray_counter value. 
         [0034]    Regardless of the solution chosen, in order to detect the FIFO “FULL” and/or “EMPTY” condition only two out of the three Gray-code counters must be synchronized and made visible to the other clock domain. In any case, it is possible to detect the “FULL” status without the third Gray-code counter for example for FIFO memories with limited size by substituting the third Gray-code counter by e.g. a shifter and two 1-hot encoders. The shifter might operate an N bit shift-left operation with wrapping on the 1-hot encoded value of the write_gray counter. If this value is equal to the 1-hot encoded value of the synchronized read_gray_counter value in the write clock domain, in this case the FIFO memory can be considered as “FULL”. 
         [0035]    The preferred choice of addressing the FIFO memory, as described in the foregoing, depends mainly on the FIFO type. For example, for hard FIFO memories it is preferable to have separate write and read pointer counters that will maintain the current write/read address location inside the memory. 
         [0036]    For soft FIFO memories it is possible to directly decode the 2*N Gray-coded symbols to N physical FIFO memory selections. In this way, the symbol at position J and the symbol at position (J+N) will point to the same FIFO memory location. This second option avoids the third counters, but requires an additional complex decoding logic, which is only suitable for small FIFO memories. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0037]    The invention will now be described, by way of example only, by referring to the enclosed representations, wherein: 
           [0038]      FIG. 1 , already discussed in the foregoing, is a chart showing the different bit consumptions of Gray-coding and TWO-HOT encoding, 
           [0039]      FIG. 2  shows a table of the Full-Gray-Code, 
           [0040]      FIG. 3  shows a table containing the Gray-Coded symbols associated to certain FIFO memory dimension, 
           [0041]      FIG. 4  is a block diagram illustrating an embodiment of a hard FIFO memory using a shifted write Gray-code counter, 
           [0042]      FIG. 5  is a block diagram illustrating an alternative embodiment of a hard FIFO memory using a shifted read Gray-code counter, 
           [0043]      FIG. 6  is a block diagram illustrating an embodiment of a soft FIFO memory using a shifted write Gray-code counter, 
           [0044]      FIG. 7  is a block diagram illustrating an alternative embodiment of a soft FIFO memory using a shifted read Gray-code counter, and 
           [0045]      FIG. 8  is a block diagram illustrating an embodiment of a soft FIFO memory using a 1-hot encoder and a shifter. 
       
    
    
       [0046]    In order to improve comprehensibility of the figures, the same numbers will be maintained for the same functional blocks in subsequent figures. 
       DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       [0047]    The arrangement described herein is based on the usage of a Gray-code, which includes 2*N symbols for a FIFO memory having either an odd or an even number of FIFO memory lines N. Preferably, this Gray-code is obtained by a standard full Gray-code of log 2 (2*N) bits as can be seen in  FIG. 2 . 
         [0048]    In a preferred embodiment, the full Gray-coded symbols are obtained from the immediately preceding Gray-coded symbols (i.e. having N−1 bits) mirroring all values at a “Mirror line” ( 100 ) and then adding a column of zeros on the left for the original set of symbols and a column of ones for the mirrored symbols. 
         [0049]    In  FIG. 2 , a table is shown containing the Gray-coded symbols GCS for 1, 2, 3 and 4 bits, including also the respective “Mirror Lines”  100 . 
         [0050]    For a certain number of FIFO memory lines not necessarily all available Gray-coded symbols will be required. For instance, for the encoding of N=3 FIFO memory lines only 6 (2*N) Gray-Coded symbols are necessary, while 8 (2 3 ) Gray-coded symbols are available. In order to guarantee that only a single bit value changes in the case of “wrapping” from the last to the first Gray-coded symbol the central 2*N Gray coded symbols are selected. In that respect,  FIG. 3  shows exemplary associations of Gray-coded symbols (GCS) to certain numbers of FIFO memory lines N. 
         [0051]    Those of skill in the art will appreciate that other methods for obtaining such Gray-code symbols can be used to provide 2N symbols with correct “wrapping” from the last to first element while respecting the rule of having only one single bit change. 
         [0052]    In that respect, throughout this description (and, more to the point, in the claims that follow) reference will be repeatedly made to counts/counters being reset to the value 0 when the count/counter “reaches the value 2*N”. Those of skill in the art will promptly appreciate that the count/counter “reaching” the value 2*N will typically involve the count/counter switching directly from ((2*N)−1)) to 0, without the count/counter properly taking on the value 2*N. 
         [0053]    A Gray-code counter, which provides the desired wrapping on these 2N symbols and that can be reset to an initial specific symbol is implemented and used in several instances of the FIFO memory control. It will be appreciated that Gray-code counters per se are well known in the art, which makes it unnecessary to provide a more detailed description herein, since any implementation of Gray-code counters will be generally satisfactory for the purposes of the arrangement described herein. 
         [0054]    As indicated, the arrangement described herein has the primary aim of detecting the “FULL” and “EMPTY” conditions of FIFO memories by using a set of such Gray-code counters. 
         [0055]    Instead of using N values to encode the current FIFO memory status, a total of 2*N values are used. In this way, the symbol at position J and the symbol at position (J+N) will represent the same memory location, but will be different symbols. This is important for detecting the FULL condition as will be explained in the following. 
         [0056]    Generally, two Gray-code counters are used to initially hold the same value of one of the 2*N Gray-coded symbols. The first read Gray-code counter increments on each read operation, the second write Gray-code counter increments on each write operation. 
         [0057]    The “EMPTY” condition can be obtained when the distance between the read counter and the write counter is equal to zero, in other words when the two counters hold the same value. 
         [0058]    The “FULL” condition is obtained when the distance between the write counter and the read counter is equal to N (i.e. the FIFO memory contains N elements). In a preferred embodiment, in order to calculate the distance between the two wrapping Gray-code counters a comparison is performed between the value of one of the two counters respect to the value of the other counter increased by N. In this way, the fact that the two values are equal implies that the distance between the write and read counters was actually N and therefore the FIFO memory has to be considered as “FULL”. 
         [0059]    In one embodiment the value is encoded with a third Gray-code counter initialized to symbols at position (J+N) and incremented either on a read or a write operation. 
         [0060]    In another embodiment the value can be derived from 1-hot encoding the Gray-coded symbols and then using a shift of N bit to derive from the 1-hot encoded value of the symbol at position J the 1-hot encoded value of the symbol at position (J+N). Those of skill in the art will appreciate that other methods, not described explicitly herein, will permit to derive the value of the symbol at distance N providing the same effect. 
         [0061]      FIG. 4  shows a block diagram of an embodiment of a hard FIFO memory. As better detailed in the following, this embodiment includes a third shifted Gray-coded counter, which is incremented on each write operation. 
         [0062]    In the embodiment of  FIG. 4  two clock domains are present. The write clock domain  20  is shown on the left hand side, and the read clock domain  40  is shown on the right hand side. 
         [0063]    A dual port FIFO memory  10  is used to synchronize a data flow. To that end, incoming data on a data-in bus DI will be recorded in a FIFO memory location pointed by a write-address counter  204  when a write-enable signal WE is active on a write clock W_CLK rising edge. Out-coming data on a data-out bus DO will reflect the value of the FIFO memory location pointed by the read-address counter  404 . 
         [0064]    Three counters are present in the write clock domain  20 . 
         [0065]    The write-address counter  204  is a simple binary counter, which counts from 0 to N−1 and then wraps again to zero each time the write-enable signal WE is active on a write clock W_CLK rising edge. 
         [0066]    The second counter is a write Gray-code counter  202  and the last counter is a shifted write Gray-code counter  208 . The write Gray-code counter  202  is initialized to the first Gray-coded symbol selected as Gray-code starting point (i.e. J), while the shifted write Gray-code counter  208  is initialized to the symbol at distance N (i.e. symbol at position J+N). 
         [0067]    Both counters  202  and  208  are incremented each time a new value is written, i.e. each time the write-enable signal WE is active on a write clock W_CLK rising edge. 
         [0068]    In the read clock domain  40  two counters are present. The read address counter  404  is a simple binary counter, which counts from 0 to N−1 and then wraps again to zero each time the read-enable signal RE is active on a read-clock R_CLK rising edge. 
         [0069]    The second counter is a read Gray-code counter  402  initialized to the first Gray-coded symbol selected as Gray-code starting point (i.e. symbol J). The counter will be incremented each time a new value is read, i.e. each time the read-enable signal RE is active on a read clock R_CLK rising edge. 
         [0070]    In order to generate the “EMPTY” flag the write Gray-code counter  202  is synchronized through a synchronization logic  406  that can be implemented in manner known per se e.g. by using a cascade of two or more flip-flops depending on the read clock R_CLK frequency and on the physical characteristic of the devices. 
         [0071]    The synchronized value is then compared at  410  against the value of the read Gray-code counter  402 . If the two values are equal then the “EMPTY” flag FE is asserted. 
         [0072]    In order to generate the “FULL” flag FF the read Gray-code counter  402  is synchronized by using a synchronization logic  206 . Typically, this is implemented using e.g. a cascade of two or more flip-flops depending on the write clock W_CLK frequency and on the physical characteristic of the devices used. 
         [0073]    The synchronized value is then compared at  210  against the value of the shifted write Gray-code counter. 
         [0074]    An alternative circuit for generating the FIFO “FULL” flag FF is shown in  FIG. 5 . In this embodiment the shifted Gray-code counter  408  is placed in the read clock domain  40  and is incremented each time data is read from the FIFO, i.e. when the read enable signal RE is active on a read clock R_CLK rising edge. 
         [0075]    In this case, the value of the shifted read Gray-code counter  408  is synchronized at  206  as explained in the foregoing and compared at  210  with the value of the write Gray-code counter  202 . The “FULL” flag FE is asserted if the two values match. 
         [0076]      FIG. 5  shows an implementation of the shifter write Gray-code counter  208  of  FIG. 4  wherein the shifted read Gray-code counter  408  is in the read clock domain  40 . 
         [0077]    It will be recalled that throughout the figures annexed and relating to different embodiments, the same references are used to indicate elements that are identical or equivalent: as a consequence, the description of these elements is not repeated for each embodiment. 
         [0078]      FIGS. 6 and 7  show alternative embodiments that are preferred for soft FIFO memories. In these implementations the hardware has been optimized by dispensing with the two binary counters  204 ,  404  used in the previous embodiments to address the FIFO memory location. 
         [0079]    In  FIGS. 6 and 7 , the read and write addresses are generated directly by decoding the read and write Gray-code counters  202 ,  402  by taking into account that symbols at position J and J+N will point to the same FIFO address location. 
         [0080]    This solution is preferred for small FIFO memories as it may increase the number of symbols to be decoded and thus become more complex than an embodiment with two independent read and write address counters  204 ,  404 . 
         [0081]    Specifically, in  FIGS. 6 and 7 , a set of registers  30  driven by the write clock W_CLK plays the role of the FIFO memory  10 . 
         [0082]    In these embodiments, the write and read address pointers are Gray-coded, and they are preferably converted into binary signals. This can be achieved e.g. by using two Gray-code decoders. 
         [0083]    A first Gray-code decoder  218  is used to decode the value of the write Gray-code counter  202  into the write address of the soft FIFO memory. Accordingly the second Gray-code decoder  418  is used to decode the value of the read Gray-code counter  402  into the read address of the soft FIFO memory. 
         [0084]    In order to decode the write address into the memory location of a write operation, an address decoder  32  is used. This address decoder preferably lies in the write clock domain  20  and can be realized e.g. by a simple demultiplexer. 
         [0085]    In order to decode the read-address into the memory location of a read operation, a second address decoder  34  is used. This address decoder preferably lies in the read clock domain  40  and can be realized e.g. by a simple multiplexer. 
         [0086]    Those of skill in the art will appreciate that this Gray-code decoder  218 ,  418  and the address decoder  32 ,  34  may take the form of a single decoder, which decodes the respective Gray-coded values directly into the related memory locations. 
         [0087]    In the embodiment of  FIG. 6 , the “FULL” status of the FIFO memory is generated by comparing at  210  the value of the shifted write Gray-code counter  208  with the value of a synchronizer  206  that reads the contents of the Gray-code counter  402 . 
         [0088]      FIG. 7  shows an alternative embodiment where the “FULL” status of the FIFO memory is generated by comparing at  210  the value of the write Gray-code counter  202  with the value of the synchronizer  206 , i.e. the shifted read Gray-code counter  408 . 
         [0089]    A further possible embodiment is shown in  FIG. 8 . In this case, the third Gray-code counter  208 ,  408  used to detect the “FULL” status of the FIFO memory has been removed and the symbol at distance N is obtained by using a 1-hot encoder  212  and a shifter  214 . 
         [0090]    The 2*N Gray-coded symbols are encoded with the 1-hot encoding technique. 
         [0091]    The first Gray-coded symbol of the given set of 2*N symbols will be mapped to the 2*N bit vector having the bit at position 0 set to ‘1’. 
         [0092]    The subsequent Gray-coded symbols will be mapped to the vectors obtained by shifting to the left by one bit the previous 1-hot encoded vector. 
         [0093]    Accordingly, the 1-hot encoded value of a Gray-coded symbol at distance N from a given Gray-coded symbol can be detected by shifting the 1-hot encoded value of the given Gray-coded symbol by N bit to the left. 
         [0094]    With these premises, the “FULL” flag of the FIFO memory can be obtained by comparing at  210  the 1-hot encoded  212  value of the write Gray-code counter  202  shifted by N bit to the left  214  with the 1-hot encoded  216  value of the synchronizer  206  representative of the value of the read Gray-code counter  402 . 
         [0095]    Those of skill in the art will appreciate that this type of control can be applied also in the read-clock domain  40  following the same principles of the previous described alternative embodiments. 
         [0096]    Of course, without prejudice to the underlying principles of the invention, the details and the embodiments may vary, even significantly, with respect to what has been described and illustrated, just by way of example, without departing from the scope of the invention as defined in the annexed claims.