Synchronized FIFO memory circuit

Details Synchronized FIFO memory circuit Synchronized FIFO memory circuit

1999-05-27

2002-11-12

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Control technique

C365S189070, C365S189080, C710S056000, C710S310000, C711S204000, C711S219000

Reexamination Certificate

active

06480942

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to a FIFO (First-In First-Out) memory circuit, and more particularly, to a synchronized FIFO memory circuit.
The term FIFO is an acronym for a First-In/First-Out memory, meaning a memory outputting data which was inputted first.
The FIFO is a functional storage device that is interposed between two apparatuses wherein data produced in a time series from one of the apparatuses is inputted to the other apparatus. The FIFO is placed between the two apparatuses as a memory buffer for absorbing a difference in processing speed and/or processing timing between the two apparatus.
Generally, FIFO memories are roughly divided into two types depending upon the configuration of a storage element of the FIFO.
One of the FIFO memories employs a random access memory as a storage element. In order to allow a random access memory to operate as a FIFO, it is combined with a FIFO controller to construct a FIFO. As a random access memory, an SRAM or a register file is used. The FIFO controller is a sequential circuit that includes a write pointer, i.e. a register indicating a write position for input data and a read pointer, i.e. a register indicating a read position for output data.
The other one of the FIFO memories employs a shift register including a plurality of registers connected at the same plurality of stages. The registers have a sequential relationship among them and transfer all pieces of data at a time from each register nearer to the input to an adjacent register nearer to the output.
Further, the FIFO memories are roughly divided into two types from a functional point of view.
One of the FIFO memories is generally called an asynchronous FIFO with the write timing and the read timing thereof different from each other. Writing is performed in synchronism with a signal called a write clock, and reading is performed in synchronism with a signal called a read clock.
The other one of the FIFO memories is generally called a synchronized FIFO with the write timing and the read timing thereof matching each other. Writing and reading are performed in response to a common input clock. A write enable signal and a read enable signal determine whether writing should be or should not be performed and whether reading should be or should not be performed respectively.
1) FIFO with no Input/Output Registers
A block diagram of a conventional synchronized FIFO of the random access memory type and a FIFO controller thereof is shown in FIG.
1
.
Referring to
FIG. 1
, a block denoted by 1R1W MEMORY is a typical 1-read/1-write random access memory having no input register and no output register. The 1-read/1-write random access memory has data input/output terminals, a write address input terminal/read address input terminal and a write enable (Write Enable) signal input terminal/read enable (Read Enable) signal input terminal.
The FIFO controller controls write/read addresses and write/read enable signals to cause the random access memory to operate as a FIFO. For this reason, the FIFO controller includes a Write Pointer Counter for holding and updating a write address and a Read Pointer Counter for holding and updating a read address.
Generally, two kinds of operation, namely, writing and reading, are performed on the FIFO. For this reason, the FIFO controller has a Write Enable signal input for requesting writing and a Read Enable signal input for requesting reading. Further, the FIFO controller has signals indicating status of the FIFO. The status signals are a Full signal output indicating whether or not a write operation is enabled (a write operation is disabled when Full==0) and an Empty signal output indicating whether or not a read operation is enabled (a read operation is disabled when Empty==1). Or, since a write operation is enabled when Full==0 and a read operation is enabled when Empty==0, the FIFO controller may output a signal of Write Ready (=~Full) or Read Ready (=~Empty). The signals are all managed by the FIFO controller.
The Write Pointer (hereinafter referred to as a WP) indicates a position into which input data is to be written, and the Read Pointer (hereinafter referred to as an RP) indicates a position from which data is to be read out. If the WP and the RP indicate the same position, this represents that no valid entry (a register in which data is stored) is present. In this instance, the Empty signal is 1.
The number of valid entries is the number of pieces of valid data present in the FIFO and is given by (WP−RP). This, however, is limited to a case wherein the maximum number of entries in the FIFO is 2{circumflex over ( )}n (where n is a natural number).
The number of entries that can be stored in the FIFO may be equal to the maximum number of entries, or may be equal to the maximum number of entries −1, depending upon the manner of control of the FIFO. When as many pieces of data as all entries are simply written into the FIFO at a point of time, then a WP=RP state is reached at the point of time, and this full state cannot be distinguished from the condition of an empty FIFO. Accordingly, a 1-bit register needs to be provided separately to allow discrimination between the Empty and Full states of the FIFO depending upon whether or not WP=RP.
Another method is available wherein WP=RP−1 is regarded as a condition of a full FIFO. In this instance,
WP=RP+n−
1(
mod n
)=
RP−
1(
mod n
)
where the symbol n represents the maximum number of entries, and the number of entries that can be stored in the FIFO is given by the maximum number of entries −1. Here, RP+1−n(mod n) signifies a remainder that is obtained when RP+n−1 is divided by n. Similarly, RP-1(mod n) is a remainder that is obtained when RP-1 is divided by n. The transformation of the expression above is obvious. In
FIG. 1
, an example wherein the number of entries that can be stored in the FIFO is equal to maximum number of entries −1 is shown.
Further, depending upon the application of the FIFO, the FIFO controller may have Almost Full and Almost Empty signals.
The Almost Full and Almost Empty signals have the value 1 when the number of remaining empty entries is smaller than a number of entries i and the number of valid entries is smaller than a number of entries j, respectively. In order to implement the FIFO controller with this feature, suitable constants should be inputted to comparators as seen from FIG.
1
.
2) FIFO with Input/Out Registers
The FIFO memory having no input register and no output register provided therefor has been described above. However, if the capacity of the memory becomes so large that a considerable time is required to write and read out data into and from the memory, then a state in which input data has to be delivered at the beginning of a cycle and read data is received at the end of the cycle becomes inevitable. Generally, in such a case, a data input register, i.e. Input Register, and a data output register, i.e. Output Register, are provided for the data input and output terminals of the memory respectively as seen in FIG.
2
.
Where no such input/output registers are provided, the relationships of Write Ready=~Full and Read Ready−~Empty are satisfied. On the other hand, if the input register has valid data therein and the memory is Full while the output register is empty, the FIFO as a whole is not Full since the output register is one of entries of the FIFO. Nevertheless, the FIFO is not Read Ready. This is because the valid data in the input register cannot be transferred to the memory. Further, although the memory is not Empty, it is not Read Ready. This is because the output register has no valid data. In this instance, it is possible merely to read out data in the memory designated by the RP and transfer it to the output register. Thereafter, since one empty entry appears, the data in the input register is transferred to the memory and input data

Affiliated with

Also associated with

Rating

Synchronized FIFO memory circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Synchronized FIFO memory circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Synchronized FIFO memory circuit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2916068