Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
2000-07-21
2002-11-12
Peikari, B. James (Department: 2186)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S053000, C710S056000
Reexamination Certificate
active
06480912
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data memories, and more particularly, to first-in first-out (FIFO) memories.
BACKGROUND OF THE INVENTION
FIFOs (or circular buffers), for example, allow communications between two systems when both systems cannot communicate at the same speed. A FIFO memory has a plurality of serially arranged storage cells (or memory locations) which are sequentially written into and read from. A write address pointer holds the write binary address of the storage cell in which data will be written into during the next write operation, and a read address pointer holds the read binary address of the storage cell which will be read from during the next read operation. For the FIFO memory to operate without creating bit errors, each storage cell must be alternately written into and then read from, i.e., no storage cell is written into twice in succession without an intermediate read operation and no storage cell is read from twice in succession without an intermediate write operation.
To prevent a bit error from occurring, FIFO memories typically detect if the write address pointer and the read address pointer are separated by a predetermined number of storage cells and provide status flags at output terminals which indicate whether the memory is full or empty. It is noted that the write address pointer will always lead the read address pointer since the data cannot be read until it is written. When a particular boundary condition is present, the status flags may disable the reading and/or writing of information to or from the memory.
Conventional approaches for detecting overrun and underrun conditions typically use some type of counting scheme. A counter may be updated dynamically as data is written to or read from the memory. For example, a counter may keep track of the number of unoccupied storage cells in the memory. If the number of occupied storage cells falls to a predetermined value approaching zero, a signal indicating that the memory is “almost empty” is presented. If the number of occupied storage cells becomes large, reaching a predetermined value close to the storage capacity of the memory, a signal indicating that the memory is “almost full” is presented.
An example of a system for generating buffer status flags is disclosed in U.S. Pat. No. 5,978,868 to Maas. The Maas system determines the direction of progression of the read and write pointers by using a gray code counting sequence, comparing the pointers, and using a phase shifter and logic circuit.
However, the read and write pointers of a typical FIFO may wrap around the memory address range. Thus, the logic circuit for determining the number of empty storage cells becomes relatively complex and increases the amount of area required in the integrated circuit. Accordingly, there is a need for a reduced complexity method and circuit for determining the number of empty storage cells in a FIFO memory.
SUMMARY OF THE INVENTION
In view of the foregoing background, it is therefore an object of the invention to provide a determination of the number of empty memory locations with reduced logic and complexity.
This and other objects, features and advantages in accordance with the present invention are provided by a method for determining a number of empty memory locations in a first-in first-out (FIFO) memory device including a plurality of memory locations having sequential binary addresses, a write address pointer for sequentially accessing the memory locations to write data therein, and a read address pointer for sequentially accessing the memory locations for reading data therefrom. The method includes determining a read binary address R of the read address pointer and a write binary address W of the write address pointer, inverting the write binary address W to generate an inverted write binary address W
inv
, and adding W
inv
, R and one to produce a first binary value. The most significant bit (MSB) of the first binary value is discarded to define a second binary value, and the number of empty memory locations is determined based upon the second binary value.
The plurality of memory locations may equal 2
n
, and determining the number of empty memory locations may comprise determining if the second binary value is not zero, and, if so, the number of empty memory locations equals the second binary value. Also, if the second binary value is equal to zero, the number of empty memory locations equals 0 or 2
n
. Here, the method includes distinguishing between a totally full and totally empty condition of the FIFO memory device when the second binary value is equal to zero. This may be done by comparing the MSBs of the read and write address pointers and may include the use of n+1 bit wide counters. Additionally, if the plurality of memory locations equals 2
n
, the read binary address R is an n-bit binary value, the write binary address W is an n-bit binary value, and the second binary value is an n-bit binary value.
Objects, features and advantages in accordance with the present invention are also provided by a first-in first-out (FIFO) memory device including a plurality of memory locations having sequential binary addresses, a write address pointer for sequentially accessing the memory locations to write data therein, and a read address pointer for sequentially accessing the memory locations for reading data therefrom. The FIFO memory device also includes a logic circuit for receiving a read binary address R of the read address pointer and a write binary address W of the write address pointer, inverting the write binary address W to generate an inverted write binary address W
inv
, adding W
inv
, R and one to produce a first binary value, discarding a most significant bit (MSB) of the first binary value to define a second binary value, and outputting the number of empty memory locations based upon the second binary value.
Preferably, the logic circuit includes a logic gate for inverting the write binary address W to generate the inverted write binary address W
inv
, and an adder including a first input connected to the logic gate for receiving the inverted write binary address W
inv
. The adder also includes a second input for receiving the read binary address R, and an output for outputting the number of empty memory locations. The adder may also include a carry-in input for adding the one, and a carry-out output for discarding the MSB of the first binary value.
Again, the plurality of memory locations may equal 2
n
, and the logic circuit outputs the second binary value as the number of empty memory locations when the second binary value is not zero. When the second binary value is equal to zero, the logic circuit outputs
0
as the number of empty memory locations. The FIFO memory device may also include a state device for controlling the read and write address pointers and for distinguishing between a totally full and totally empty condition of the FIFO memory device when the second binary value is equal to zero. Also, a comparing circuit may be included for comparing MSBs of the read and write address pointers and for distinguishing between a totally full and totally empty condition of the FIFO memory device when the second binary value is equal to zero.
REFERENCES:
patent: 4833651 (1989-05-01), Seltzer et al.
patent: 4891788 (1990-01-01), Kreifels
patent: 4935719 (1990-06-01), McClure
patent: 4942553 (1990-07-01), Dalrymple et al.
patent: 5121346 (1992-06-01), McClure
patent: 5506809 (1996-04-01), Csoppenszky et al.
patent: 5765187 (1998-06-01), Shimizu et al.
patent: 5978868 (1999-11-01), Maas
patent: 6304936 (2001-10-01), Sherlock
patent: 0 321 089 (1989-06-01), None
patent: 0 579 375 (1994-01-01), None
patent: 0 752 642 (1997-01-01), None
Jorgenson Lisa K.
Peikari B. James
Regan Christopher F.
STMicroelectronics Inc.
LandOfFree
Method and apparatus for determining the number of empty... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining the number of empty..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining the number of empty... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2969913