Patent Abstract:
An error detection system for detecting errors in data output from a FIFO memory includes a first CRC generator for receiving an inbound data stream and generating a first CRC value based on a data block in the inbound data stream. A device coupled to the first CRC generator selectively inputs the data block and the first CRC value into the FIFO. A second CRC generator generates a second CRC value based on the data block after being output from the FIFO in an outbound data stream. The second CRC value indicates whether the data block contains an error.

Full Description:
THE FIELD OF THE INVENTION  
         [0001]    The present invention generally relates to error detection systems, and more particularly to an error detection system for a First In First Out (FIFO) memory.  
         BACKGROUND OF THE INVENTION  
         [0002]    In a First In First Out (FIFO) memory, data entered at the input appear at the output in the same order. Input and output in a FIFO are typically controlled by two separate clocks. FIFO&#39;s are typically used for buffering data. Some FIFO&#39;s are based on random access memory (RAM) technology, which is susceptible to both short term and long term errors.  
           [0003]    In existing systems that employ FIFO memory elements, either no error checking of data flowing through the FIFO is provided, or a simple parity check of bits on a per word basis is used. With parity checking, when a data word is output from the FIFO, the parity of the data word is checked against an expected value (i.e., even or odd). If the data word does not match the expected parity value, an error is determined to have occurred. Although this method works for determining single bit errors, it does not always work well for determining multiple bit errors.  
           [0004]    It is desirable to provide a more robust system for detecting data corruption in data streams passing through FIFO memory elements.  
         SUMMARY OF THE INVENTION  
         [0005]    One form of the present invention provides an error detection system for detecting errors in data output from a FIFO memory. The system includes a first CRC generator for receiving an inbound data stream and generating a first CRC value based on a data block in the inbound data stream. A device coupled to the first CRC generator selectively inputs the data block and the first CRC value into the FIFO. A second CRC generator generates a second CRC value based on the data block after being output from the FIFO in an outbound data stream. The second CRC value indicates whether the data block contains an error. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0006]    [0006]FIG. 1 is a block diagram illustrating a FIFO and an error detection system for detecting errors in data output from the FIFO according to one embodiment of the present invention.  
         [0007]    [0007]FIG. 2 is a block diagram illustrating a FIFO and an error detection system for detecting errors in data output from the FIFO according to an alternative embodiment of the present invention.  
         [0008]    [0008]FIG. 3 is a block diagram illustrating a FIFO and an error detection system for detecting errors in data output from the FIFO according to another alternative embodiment of the present invention. 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0009]    In the following detailed description of the preferred embodiments, reference is made to the accompanying drawings, which form a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural or logical changes may be made without departing from the scope of the present invention. The following detailed description, therefore, is not to be taken in a limiting sense, and the scope of the present invention is defined by the appended claims.  
         [0010]    [0010]FIG. 1 is a block diagram illustrating a First In First Out (FIFO) memory  118  and an error detection system  100  for detecting errors in data output from the FIFO  118  according to one embodiment of the present invention. Error detection system  100  includes cyclic redundancy code (CRC) generator  104 , frame control logic  110 , multiplexer (MUX)  114 , CRC generator  124 , and frame control logic  130 . In one embodiment, error detection system  100  detects errors occurring in data passing through a protection domain  119 , which includes multiplexer  114  and FIFO  118 .  
         [0011]    Inbound data stream  102  is received by CRC generator  104  and multiplexer  114 . In one embodiment, inbound data stream  102  is a stream of binary values (e.g., 0 or 1). As the bits of inbound data stream  102  are received, CRC generator  104  begins accumulating a CRC value  112 . In one embodiment, CRC value  112  is determined from the polynomial division shown in the following Equation I:  
         [0012]    Equation I  
           CRC =remainder of  M[x]/G[x]   
         [0013]    where:  
         [0014]    M[x] is a message block (m-bits long) presented to the CRC generator  104 ; and  
         [0015]    G[x] is a generator polynomial.  
         [0016]    M[x] represents a block of data from inbound data stream  102 . Frame control logic  110  controls the size of each block of data (message block) processed by CRC generator  104 . Accumulation of a running CRC  112  begins when frame control logic  110  asserts start line  106 , and ends when frame control logic  110  asserts stop line  108 . The start and stop signals generated by frame control logic  110  delimit the data block to be checked. In one embodiment, an external controller (not shown) sends signals to frame control logic  110  that indicate when start line  106  and stop line  108  should be asserted.  
         [0017]    M[x] is a polynomial representation of the bits in the message block, with each bit being a coefficient of the polynomial. An m-bit message block is regarded as a coefficient list for a polynomial with m terms, ranging from x m−1  to x 0 . Such a polynomial is said to be of degree m−1, with the highest order bit in the message block being the coefficient of x m−1 . For example, the message block “1110001” has six bits, and M[x] for this stream of bits would represent a six term polynomial with coefficients 1, 1, 0, 0, 0, and 1: x 5 +x 4 +x 0 .  
         [0018]    For the generator polynomial, G[x], in Equation I, both the high order and the low order coefficients are 1. The generator polynomial G[x] is one bit longer than the desired bit length of the CRC  112 . In one embodiment, G[x] is an international standard generator polynomial (e.g., CRC-12=x 12 +x 11 +x 3 +x 2 +x 1 +1; CRC-16=x 16 +x 15 +x 2 +1; or CRC-CCITT=x 16 +x 12 +x 5 +1). Although a few examples of generator polynomial G[x] have been provided, the CRC  112  can be generated by any number of standard CRC algorithms that use a special polynomial divisor to produce a unique signature based on the content of a data block.  
         [0019]    In one form of the invention, a “proper” generator polynomial G[x] has the following properties: (1) The probability of undetected error as a function of the bit error probability, p, never exceeds the probability of undetected error at p=0.5, which is 1½ n *100%, or 99.9985% (for n=16), where n=the highest power in the generator polynomial (e.g., n=16 for the CRC-16 polynomial); and (2) the single burst error detecting performance is much larger (order of magnitude) than a non-proper polynomial, so n should chosen such that the number of bits in the message block M[x] to be checked does not exceed 2 n , where n is the highest order term in the generator polynomial.  
         [0020]    As mentioned above, M[x] and G[x] represent polynomials with binary coefficients. The polynomial arithmetic performed by CRC generator  104  is done Modulo 2 with no carry. The following Example I shows how polynomial division is performed according to one embodiment:  
       EXAMPLE I  
       [0021]    [0021]                                                             Message M:   1101011011           Message M after appending w bits:   11010110110000           Generator Polynomial G:   10011 (width w = 4)                                                                       
         [0022]    The above Example I does not take into account a seed value that might be used in certain implementations. It may be assumed for this Example I that the message M also incorporates a seed value. As shown in Example I, four binary zeros are appended to the end of the message M prior to division. The number of zeros that are appended on a message M is the same as the degree of the generator polynomial, which is four in Example I. The number of appended zeros also matches the width of the desired CRC  112 . The CRC  112  is the remainder of the division M[x]/G[x], which is 1110 in Example I.  
         [0023]    Once the CRC  112  has been calculated for a data block by CRC generator  104 , in one embodiment, the CRC  112  is then appended to the data block with multiplexer  114 . As shown in FIG. 1, multiplexer  114  includes a first input for receiving the inbound data stream  102 , and a second input for receiving the CRC  112  from CRC generator  112 . Multiplexer  114  initially outputs the message block from the inbound data stream  102  to FIFO  118 . After outputting the message block, frame control logic  110  sends an append signal  116  to multiplexer  114 , which causes multiplexer  114  to output the CRC  112  for the message block to FIFO  118 .  
         [0024]    FIFO  118  outputs an output data stream  120 , which is analyzed by CRC generator  124 . After passing through the FIFO  118 , the message block with the appended CRC  112  in output data stream  120  is analyzed by CRC generator  124  to determine if the message block was corrupted. Frame control logic  130  asserts a start line  126  to indicate to CRC generator  124  the beginning of the message block, and asserts stop line  128  to indicate the end of the block. Accumulation of a CRC (e.g., remainder)  132  by CRC generator  124  begins when frame control logic  130  asserts start line  126 , and ends when frame control logic  130  asserts stop line  128 . In one embodiment, an external controller (not shown) sends signals to frame control logic  130  that indicate when start line  126  and stop line  128  should be asserted.  
         [0025]    In one embodiment, CRC generator  124  validates the integrity of the received data block by dividing the received data block with the appended CRC  112  by the same generator polynomial G[x] that was used to generate the CRC  112 , as represented by the following Equation II:  
         [0026]    Equation II  
           CRC =remainder of ( M[x]+CRC )/ G[x]   
         [0027]    where:  
         [0028]    M[x] is the message block presented to the CRC generator  124 ; and  
         [0029]    G[x] is the generator polynomial that was used to generate the CRC  112 .  
         [0030]    In one form of the invention, system  100  is used to validate the integrity of data blocks where a CRC  112  is appended directly at the end of each data block. In this case, the polynomial G[x] is an exact multiple of the data block with the appended CRC  112 , and the CRC  132  calculated by CRC generator  124  will be a constant number if no corruption occurred. If no corruption occurred, CRC  132  will be 0 if the appended CRC  112  is not inverted, but if the CRC  112  is inverted to provide additional error protection, the CRC  132  will be a distinct constant, or “magic” number that indicates that the data and embedded CRC  112  have passed through the FIFO  118  uncorrupted.  
         [0031]    [0031]FIG. 2 is a block diagram illustrating a FIFO  118  and an error detection system  200  for detecting errors in data output from the FIFO  118  according to an alternative embodiment of the present invention. In one embodiment, system  200  may be used when CRC  112  is embedded in the message block, but not at the exact end of the message block. This case may occur if the FIFO  118  data output width is not the same as the data width on the inbound side, and padding is used (the padding bits are not included in the CRC).  
         [0032]    In one embodiment, blocks  104 ,  110 ,  114 ,  118 ,  124 , and  130 , in FIG. 2 operate in substantially the same manner as described above with reference to FIG. 1. After passing through the FIFO  118 , the message block with the appended CRC  112  in output data stream  120  is analyzed to determine if the message block was corrupted. The CRC  112  embedded in the message block is extracted from output data stream  120  and stored in CRC register  204 . Frame control logic  130  (or an external controller) keeps track of the location of the CRC  112  in the message block, and outputs a “Load CRC” signal  206  to CRC register  204  at the appropriate time to load the CRC  112  from output data stream  120  into the register  204 .  
         [0033]    CRC generator  124  calculates a CRC  214  based on the received message block (without the embedded CRC  112 ) using the same generator polynomial G[x] that was used by CRC generator  104  to generate the CRC  112 . Frame control logic  130  outputs a start signal  126  to CRC generator  124  to indicate the beginning of the message block, and outputs a stop signal  128  to indicate the end of the block. Accumulation of a CRC  214  begins when frame control logic  130  asserts start line  126 , and ends when frame control logic  130  asserts stop line  128 .  
         [0034]    Comparator  210  receives the extracted CRC  112  from CRC register  204 , and receives the newly calculated CRC  214  from CRC generator  124 . Since the two CRC values  112  and  214  were generated from the same message block using the same generator polynomial P[x], the two values  112  and  214  should match if no error occurred in the message block as it passed through FIFO  118 . Comparator  210  compares the two CRC&#39;s  112  and  214 , and outputs an error signal  212  if the two values  112  and  214  are not equal. In one embodiment, system  200  is also configured to generate a CRC  132  in the same manner as described above with reference to FIG. 1, such as for data blocks having the CRC  112  appended at the end of the data blocks.  
         [0035]    [0035]FIG. 3 is a block diagram illustrating a FIFO  118  and an error detection system  300  for detecting errors in data output from the FIFO  118  according to another alternative embodiment of the present invention. System  300  includes the same blocks  104 ,  110 ,  114 ,  118 ,  204 ,  210 ,  124 , and  130 , as system  200  shown in FIG. 2, and also includes registers  302  and  304 . In one embodiment, registers  302  and  304  each store a plurality of different types of generator polynomials G[x]. In one embodiment, an appropriate generator polynomial G[x] is loaded into CRC generator  104  from register  302 , and the same generator polynomial is loaded into CRC generator  124  from register  304 . CRC calculations are then performed as described above using the generator polynomial loaded from registers  302  and  304 .  
         [0036]    In one form of the invention, the generator polynomials G[x] used by CRC generators  104  and  124  are changed “on the fly” during operation of system  300  to provide varying error detection properties. In one embodiment, the various generator polynomials G[x] stored in registers  302  and  304  have different properties (e.g., different lengths, different coefficients, etc.). As is known to persons of ordinary skill in the art, certain types of generator polynomials are better able to detect certain classes of errors than other generator polynomials. In addition, longer polynomials may be needed to accurately detect errors in longer blocks of data, while shorter polynomials may be used for shorter blocks of data. In one form of the invention, appropriate generator polynomials G[x] are automatically loaded from registers  302  and  304  into CRC generators  104  and  124 , respectively, based on the length of data blocks that are to pass through FIFO  118 , and/or based on the content of such data blocks or types of errors desired to be detected.  
         [0037]    It will be understood by a person of ordinary skill in the art that functions performed by systems  100 ,  200 , and  300  may be implemented in hardware, software, firmware, or any combination thereof. The implementation may be via a microprocessor, programmable logic device, or state machine. Components of the present invention may reside in software on one or more computer-readable mediums. The term computer-readable medium as used herein is defined to include any kind of memory, volatile or non-volatile, such as floppy disks, hard disks, CD-ROMs, flash memory, read-only memory (ROM), and random access memory.  
         [0038]    In one embodiment, the CRC calculations performed by systems  100 ,  200 , and  300 , for both inbound  102  and outbound  120  sides of the data path happen in parallel with the shifting of data into the data path, so no latency penalty is imposed.  
         [0039]    One embodiment of the present invention provides a robust system for detecting data corruption in data streams flowing through a FIFO using a CRC algorithm. Unlike conventional FIFO error detection processes based on parity, embodiments of the present invention can detect multiple bit errors, and can detect errors in blocks of data of varying sizes, rather than detecting errors only on a per word basis. Embodiments of the present invention are far more robust than existing parity-based error detection systems in terms of ability to detect various types of bit errors that may occur in data blocks that pass through a FIFO.  
         [0040]    Although specific embodiments have been illustrated and described herein for purposes of description of the preferred embodiment, it will be appreciated by those of ordinary skill in the art that a wide variety of alternate and/or equivalent implementations may be substituted for the specific embodiments shown and described without departing from the scope of the present invention. Those with skill in the chemical, mechanical, electromechanical, electrical, and computer arts will readily appreciate that the present invention may be implemented in a very wide variety of embodiments. This application is intended to cover any adaptations or variations of the preferred embodiments discussed herein. Therefore, it is manifestly intended that this invention be limited only by the claims and the equivalents thereof.

Technology Classification (CPC): 7