What is a FIFO cache queue?
FIFO is the abbreviation of English First In First Out, which is a first-in first-out data buffer. The difference between FIFO and ordinary memory is that there is no external address line for reading and writing, so it is very simple to use. But the disadvantage is that data can only be written in sequence, and the data address is automatically added by the internal read-write pointer with 1 Unlike ordinary memory, it cannot read or write the specified address through the address line. FIFO is generally used for data transmission between different clock domains, such as AD data acquisition at one end and PCI bus of computer at the other end. Assuming that the AD acquisition rate is 16 bit 100K SPS, the data volume per second is100k×16bit =1.6mbps, and the speed of PCI bus is 33MHz Mbps. The bus width is 32 bits, and the maximum transmission rate is 1056Mbps. FIFO can be used as a data buffer between two different clock domains. In addition, FIFO can also be used for data interfaces with different widths, such as 8-bit data output of single chip microcomputer and 16-bit data input of DSP. When the single chip microcomputer is connected with DSP, FIFO can be used to achieve the purpose of data matching. 3. Some important parameters of FIFO: width, which is often seen in English materials, are just the data bits of a FIFO reading and writing operation, just like MCU has 8 bits and 16 bits, ARM 32 bits and so on. In monolithic integrated circuits, the width of FIFO is fixed and optional. If a FIFO is implemented by FPGA, its data bits, that is, its width, can be defined by itself. Depth of FIFO: Depth refers to how much N-bit data can be stored in FIFO (if the width is n). For example, an 8-bit FIFO with a depth of 8 can store 8 8 8-bit data and a depth of 12 can store 12 8-bit data. The depth of FIFO can be large or small. Personally, there is no fixed formula for calculating FIFO depth. In the actual work of FIFO, the full/empty flag of its data can control the continued writing or reading of data. In practical application, it is also impossible to calculate the exact required FIFO depth through some parameters, which is feasible in the ideal state that the writing speed is greater than the reading speed, but the actual FIFO depth is often greater than the calculated value. Generally speaking, according to the specific situation of the circuit, it is enough to estimate an approximate width and depth while taking into account the system performance and FIFO cost. For applications where the writing speed is slower than the reading speed, the depth of FIFO should be determined according to the data structure and the specific requirements of reading data. Full flag: When the FIFO is full or about to be full, the state circuit of the FIFO sends a signal to prevent the write operation of the FIFO from continuing to write data into the FIFO and causing overflow. Empty flag: When the FIFO is empty or about to be empty, the state circuit of the FIFO sends a signal to prevent the FIFO from reading data from the FIFO and causing invalid data to overflow. Reading clock: the clock after reading operation, which temporarily reads data at each clock edge. Write clock: the clock that the write operation follows, and data is temporarily written at each clock edge. Read pointer: points to the next read address. Automatically add 1 after reading it. Write pointer: points to the next address to be written, and automatically adds 1 after writing. The read-write pointer is actually the address of reading and writing, but this address cannot be chosen arbitrarily, but is continuous. 4. The classification of FIFO is based on the clock domain of FIFO, which can be divided into synchronous FIFO and asynchronous FIFO. Synchronous FIFO means that the read clock and the write clock are the same clock. When the clock edge comes, read and write operations occur simultaneously. Asynchronous FIFO means that the read clock and the write clock are inconsistent and independent of each other. 5. The difficulty of FIFO design is how to judge the empty/full state of FIFO. In order to ensure the correct writing or reading of data without generating benefits or empty reading, it is necessary to ensure that the FIFO is full and cannot be written. Cannot read in empty state. How to judge whether FIFO is full/empty has become the core problem of FIFO design. Because synchronous FIFO is rarely used, only the generation of empty/full flag of asynchronous FIFO is described here. Supplement: In the design of flip-flops, it is inevitable to encounter the problem of metastability (metastability is not introduced here, you can refer to relevant materials). In circuits involving flip-flops, metastability cannot be completely eliminated, so we can only try to minimize the probability of its occurrence. One way is to use gray code. Gray code only transforms one bit between two adjacent symbols (binary code is that many symbols change at the same time in many cases). This will avoid the metastable phenomenon when the counter is synchronized with the clock. However, the Gray code has a disadvantage that it can only define the depth of 2 n, but can't define the depth of FIFO at will like a binary code, because the Gray code must cycle a 2 n, otherwise it can't guarantee the condition that two adjacent symbols are one bit apart, so it is not a real Thunder code. The second is to use redundant flip-flops, assuming that the metastable probability of one flip-flop is p, then the metastable probability of two parallel flip-flops is the square of p, but this time it leads to an increase in delay. The occurrence of metastable state will make FIFO error, and the address pointer sampled by read/write clock will be different from the real value, resulting in the wrong address for writing or reading. Due to the delay, when the FIFO is really empty/full, the empty/full flag does not necessarily appear. Maybe the empty/full flag appears before the FIFO is empty/full. This is no problem as long as the FIFO does not overflow or underflow. Many articles about FIFO actually discuss different algorithms of empty/full flag. In Vijay A. Nebhrajani's article "Asynchronous FIFO Structure", the author proposed two algorithms about FIFO empty/full flag. The first algorithm: construct a FIFO with a pointer width of N+ 1 and a depth of 2 n bytes (to facilitate the conversion of gray code pointers into binary pointers). When the most significant bit in the pointer binary code is inconsistent and the other n bits are equal, the FIFO is full (in Clifford E. Cummings' article, the first two bits are inconsistent, and the last two lsbs are full, which is different from the MSB in binary representation, and all others are full). When the pointers are completely equal, the FIFO is empty. This may not be easy to see. Let's give an example to illustrate how a FIFO with a depth of 8 bytes works (using a pointer that has been converted to binary). FIFO_WIDTH=8, supplemented by FIFO _ depth = 2 n = 8, N = 3, and the pointer width is N+ 1=4. At first, rd_ptr_bin and wr_ptr_bin were both "0000". At this time, 8 bytes of data are written into the FIFO. Wr_ptr_bin =" 1000 ",rd_ptr_bin="0000". Of course, this is a sufficient condition. Now suppose that the read operation is performed 8 times, so that rd _ ptr _ bin = "1000", which is an empty condition. Eight other write operations will make wr_ptr_bin equal to "0000", but rd_ptr_bin is still equal to "1000", so the FIFO is full. Obviously, the start pointer need not be "0000". Suppose it is "0 100" and the FIFO is empty, then 8 bytes will make WR _ PTR _ bin = "1 100" and rd_ptr_bin still be "0 100". This again means that the FIFO is full. If the upper two msbs of the write pointer are greater than the upper two msbs of the read pointer, the FIFO is almost empty. In the article of the third part of Vijay A. Nebhrajani's Asynchronous FIFO Structure, a method is also mentioned, that is, direction sign and threshold. 75% of FIFO capacity is set as the upper limit and 25% of FIFO capacity is set as the lower limit. When the direction symbol exceeds the threshold, the full/empty symbol is output, which is similar to the style #2 mentioned in Clifford E. Cummings' article. All belong to conservative empty judgment. In fact, the output empty flag FIFO is not necessarily empty/full at this time. Having said that, we have clearly seen that the key of FIFO design is that different empty/full flag generation algorithms generate different FIFO.