FIFO memory system and method with improved determination of full and empty conditions and amount of data stored

• US 6,434,642 B1
• Filed: 10/07/1999
• Issued: 08/13/2002
• Est. Priority Date: 10/07/1999
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Alfke, Peter H., Ebeling, Christopher D., Camilleri, Nicolas J.
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US09/414,987
• Time in Patent Office: 1,041 Days
• Field of Search: 710/52, 710/57, 711/109, 711/110, 711/156, 365/221, 365/189.07, 377/34
• US Class Current: 710/57
• CPC Class Codes: G06F 2205/102 Avoiding metastability, i.e. preventing hazards, e.g. by using Gray code counters
• CPC Class Codes: G06F 2205/126 Monitoring of intermediate fill level, i.e. with additional means for monitoring the fill level, e.g. half full flag, almost empty flag
• CPC Class Codes: G06F 5/12 Means for monitoring the fill level; Means for resolving contention, i.e. conflicts between simultaneous enqueue and dequeue operations
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags
• CPC Class Codes: G11C 19/287 Organisation of a multiplicity of shift registers

Abstract

A structure and method for operating an asynchronous first in, first out (FIFO) memory system in which the full or empty condition of the memory is determined by comparing a currently-generated write address with a currently-generated read address and a next-to-be-used read address. The current write address and current read address are transmitted from a write address counter and a read address counter, respectively, to a flag control circuit. The flag control circuit includes registers for storing Gray-code versions of the current write address, the current read address, and the next-to-be-used read address, which is determined from the current read address. The flag control circuit generates intermediate ALMOST_EMPTY and ALMOST_FULL signals when the FIFO memory is one data value from being “empty” and “full”, respectively. These intermediate signals are used to generate FULL and EMPTY control signals immediately after the FIFO memory enters a “full” or “empty” condition. A status circuit re-synchronizes a binary read address to the write clock signal, then subtracts the write-synchronized read address from the binary write address to accurately determine the amount of data in the FIFO memory.

Claims

1. A first in, first out (FIFO) memory system, comprising:

a memory having a plurality of locations each having an address;

a write address counter coupled to the memory for generating a sequence of write addresses in accordance with a circular counting sequence, wherein each write address of the sequence of write addresses accesses an associated location within the memory into which data is written during a write operation, and wherein a current write address is generated at a selected moment in time;

a read address counter coupled to the memory for generating a sequence of read addresses in accordance with the circular counting sequence, wherein each read address of the sequence of read addresses accesses an associated location within the memory from which data is read during a read operation, and wherein a current read address is generated at the selected moment in time; and

a flag control circuit coupled to receive the sequence of read addresses and the sequence of write addresses from the read and write address counters, wherein the flag control circuit includes a comparator circuit for generating an EMPTY control signal when the current read address equals the current write address at the selected moment in time, and for generating a FULL control signal when the current write address is equal to a last-used read address at the selected moment in time, wherein the last-used read address immediately precedes the current read address in the circular counting sequence,

wherein the flag control circuit further comprises;

a read address register section including a first binary-to-Gray-code converter for converting the current read address into a next-to-be-used Gray-code read address value, and a plurality of registers for storing a current Gray-code read address value and a last-used Gray-code read address value, wherein the last-used, current, and next-to-be-used Gray-code read address values are sequential values in a Gray-code counting sequence; and

a write address register section including a second binary-to-Gray-code converter for converting the current write address into a next-to-be-used Gray-code write address value, and a plurality of registers for storing a current Gray-code write address value, wherein the current and next-to-be-used Gray-code write address values are sequential values in the Gray-code counting sequence;

wherein the comparator circuit generates the EMPTY control signal by comparing the current Gray-code read address value and a the current Gray-code write address value, and generates the FULL control signal by comparing the current Gray-code write address value and the last-used Gray-code read address value.

2. The FIFO memory system according to claim 1, wherein the memory, write address counter, read address counter, and flag control circuit are implemented in a field programmable gate array.

3. The FIFO memory system according to claim 1, wherein the memory is a dual-port memory.

4. The FIFO memory system according to claim 1, wherein the write address counter and the read address counter operate synchronously.

5. The FIFO memory system according to claim 1, wherein the write address counter and the read address counter operate asynchronously.

6. The FIFO memory system according to claim 1, wherein the comparator circuit comprises:

a dual comparator including;

a first logic circuit for comparing the current Gray-code read address value and the current Gray-code write address value,

a second logic circuit for comparing the next-to-be-used Gray-code read address value and the current Gray-code write address value,

a mode control multiplexer having a first input terminal connected to an output terminal of the first logic circuit, and a second input terminal connected to an output terminal of the second logic circuit, and

a carry chain multiplexer having a select input terminal connected to an output terminal of the mode control multiplexer, a first input terminal connected to a first source maintained at a first logic level, and a second input terminal connected to a second source maintained at a second logic level; and

a register storing the EMPTY control signal and having a data input terminal connected to a carry chain that includes an output terminal of the carry chain multiplexer, and further having an output terminal connected to a select terminal of the mode control multiplexer.

7. The FIFO memory system according to claim 6, wherein the comparator circuit further comprises an OR gate having a first input terminal connected to the output terminal of the register storing the EMPTY control signal, and a second input terminal connected to receive an externally generated READ_ENABLE signal, and an output terminal connected to a clock enable terminal of the register storing the EMPTY control signal.

8. The FIFO memory system according to claim 1, wherein the comparator circuit comprises:

a dual comparator including;

a first logic circuit for comparing the last-used Gray-code read address value and the current Gray-code write address value,

a second logic circuit for comparing the last-used Gray-code read address value and the next-to-be-used Gray-code write address value,

a mode control multiplexer having a first input terminal connected to an output terminal of the first logic circuit, and a second input terminal connected to an output terminal of the second logic circuit, and

a carry chain multiplexer having a select input terminal connected to an output terminal of the mode control multiplexer, a first input terminal connected to a first source maintained at a first logic level, and a second input terminal connected to a second source maintained at a second logic level; and

a register storing the FULL control signal and having a data input terminal connected to a carry chain that includes an output terminal of the carry chain multiplexer, and further having an output terminal connected to a select terminal of the mode control multiplexer.

9. The FIFO memory system according to claim 8, wherein the comparator circuit further comprises an OR gate having a first input terminal connected to the output terminal of the register storing the FULL control signal, a second input terminal connected to receive an externally generated WRITE_ENABLE signal, and an output terminal connected to a clock enable terminal of the register storing the FULL control signal.

10. The FIFO memory system according to claim 1, further comprising:

a first logic circuit for generating a READ_ALLOW control signal in response to the EMPTY control signal and an externally generated READ_ENABLE signal, wherein the READ_ALLOW signal is generated at a first logic level only when the EMPTY control signal is low and the READ_ENABLE signal is high; and

a second logic circuit for generating a WRITE_ALLOW control signal in response to the FULL control signal and an externally generated WRITE_ENABLE signal, wherein the WRITE_ALLOW signal is generated at the first logic level only when the FULL control signal is low and the WRITE_ENABLE signal is high;

wherein the READ_ALLOW control signal is applied to clock enable terminals of the plurality of registers in the read address register section, and

wherein the WRITE_ALLOW control signal is applied to clock enable terminals of the plurality of registers in the write address register section.

11. The FIFO memory system according to claim 10, wherein the comparator circuit comprises:

a first comparator for receiving the current Gray-code read address value and the current Gray-code write address value, and for generating an output signal having the first logic level when the current Gray-code read address value is equal to the current Gray-code write address value;

a second comparator for receiving the next-to-be-used Gray-code read address value and the current Gray-code write address value, and for generating an output signal having the first logic level when the next-to-be-used Gray-code read address value is equal to the current Gray-code write address value;

an AND gate having a first input terminal connected to an output terminal of the second comparator, and a second input terminal connected to receive the READ_ALLOW signal;

an OR gate having a first input terminal connected to an output terminal of the first comparator, and a second input terminal connected to an output terminal of the AND gate; and

a register storing the EMPTY control signal and having a data input terminal connected to an output terminal of the OR gate, and a clock terminal connected to receive a read clock signal.

12. The FIFO memory system according to claim 10, wherein the comparator circuit comprises:

a first comparator for receiving the last-used Gray-code read address value and the current Gray-code write address value, and for generating an output signal having the first logic level when the last-used Gray-code read address value is equal to the current Gray-code write address value;

a second comparator for receiving the last-used Gray-code read address value and the next-to-be-used Gray-code write address value, and for generating an output signal having the first logic level when the last-used Gray-code read address value is equal to the next-to-be-used Gray-code write address value;

an AND gate having a first input terminal connected to an output terminal of the second comparator, and a second input terminal connected to receive the WRITE_ALLOW signal;

an OR gate having a first input terminal connected to an output terminal of the first comparator, and a second input terminal connected to an output terminal of the AND gate; and

a register storing the FULL control signal and having a data input terminal connected to an output terminal of the OR gate, and a clock terminal connected to receive a write clock signal.

13. A method of operating a first in, first out (FIFO) memory system including a memory having a plurality of locations each having an address, the method comprising the steps of:

at a selected moment in time, generating a current write address associated with a location within the memory to which a write operation is to be performed, and a current read address associated with a location within the memory from which a read operation is to be performed, wherein the current write address and the current read address are generated in accordance with a circular counting sequence;

generating an EMPTY control signal when the current write address is equal to the current read address at the selected moment in time; and

generating a FULL control signal when the current write address is equal to a last-used read address at the selected moment in time, wherein the last-used read address immediately precedes the current read address in the circular counting sequence,

wherein generating the EMPTY control signal comprises;

converting the current read address into a series of sequential Gray-code read address values including a next-to-be-used Gray-code read address value, a current Gray-code read address value, and a last-used Gray-code read address value;

converting the current write address into a series of sequential Gray-code write address values including a next-to-be-used Gray-code write address value and a current Gray-code write address value;

comparing the next-to-be-used Gray-code read address value and the current Gray-code write address value, and generating an ALMOST_EMPTY control signal when the next-to-be-used Gray-code read address value is equal to the current Gray-code write address value during a read operation; and

generating the EMPTY control signal within one clock cycle following the generation of the ALMOST_EMPTY control signal.

14. A method of operating a first in, first out (FIFO) memory system including a memory having a plurality of locations each having an address, the method comprising the steps of:

at a selected moment in time, generating a current write address associated with a location within the memory to which a write operation is to be performed, and a current read address associated with a location within the memory from which a read operation is to be performed, wherein the current write address and the current read address are generated in accordance with a circular counting sequence;

generating an EMPTY control signal when the current write address is equal to the current read address at the selected moment in time; and

generating a FULL control signal when the current write address is equal to a last-used read address at the selected moment in time, wherein the last-used read address immediately precedes the current read address in the circular counting sequence,

wherein generating the FULL control signal comprises;

converting the current read address into a series of sequential Gray-code read address values including a next-to-be-used Gray-code read address value, a current Gray-code read address value, and a last-used Gray-code read address value;

converting the current write address into a series of sequential Gray-code write address values including a next-to-be-used Gray-code write address value and a current Gray-code write address value;

comparing the next-to-be-used Gray-code write address value and the last-used Gray-code read address value, and generating an ALMOST_FULL control signal when the next-to-be-used Gray-code write address value is equal to the last-used Gray-code read address value during a write operation; and

generating the FULL control signal within one clock cycle following the generation of the ALMOST_FULL control signal.

15. A method of operating a first in, first out (FIFO) memory system including a memory having a plurality of locations each having an address, the method comprising the steps of:

at a selected moment in time, generating a current write address associated with a location within the memory to which a write operation is to be performed, and a current read address associated with a location within the memory from which a read operation is to be performed, wherein the current write address and the current read address are generated in accordance with a circular counting sequence;

generating an EMPTY control signal when the current write address is equal to the current read address at the selected moment in time; and

generating a FULL control signal when the current write address is equal to a last-used read address at the selected moment in time, wherein the last-used read address immediately precedes the current read address in the circular counting sequence,

wherein generating the EMPTY control signal comprises;

converting the current read address into a series of sequential Gray-code read address values including a next-to-be-used Gray-code read address value, a current Gray-code read address value, and a last-used Gray-code read address value;

converting the current write address into a series of sequential Gray-code write address values including a next-to-be-used Gray-code write address value and a current Gray-code write address value;

generating first and second logic signals, the first logic signal having a logic value determined by comparing the next-to-be-used Gray-code read address value and the current Gray-code write address value, and the second logic signal having a logic value determined by comparing the current Gray-code read address value and the current Gray-code write address value; and

selectively passing one of the first logic signal and the second logic signal to control a carry chain, wherein the first logic signal is passed to control the carry chain when the EMPTY control signal has a first logic level, and the second logic signal is passed to control the carry chain when the EMPTY control signal has a second logic level.

16. A method of operating a first in, first out (FIFO) memory system including a memory having a plurality of locations each having an address, the method comprising the steps of:

at a selected moment in time, generating a current write address associated with a location within the memory to which a write operation is to be performed, and a current read address associated with a location within the memory from which a read operation is to be performed, wherein the current write address and the current read address are generated in accordance with a circular counting sequence;

generating an EMPTY control signal when the current write address is equal to the current read address at the selected moment in time; and

generating a FULL control signal when the current write address is equal to a last-used read address at the selected moment in time, wherein the last-used read address immediately precedes the current read address in the circular counting sequence,

wherein generating the FULL control signal comprises;

converting the current read address into a series of sequential Gray-code read address values including a next-to-be-used Gray-code read address value, a current Gray-code read address value, and a last-used Gray-code read address value;

converting the current write address into a series of sequential Gray-code write address values including a next-to-be-used Gray-code write address value and a current Gray-code write address value;

generating first and second logic signals, the first logic signal having a logic value determined by comparing the last used Gray-code read address value and the next-to-be-used Gray-code write address value, and the second logic signal having a logic value determined by comparing the last-used Gray-code read address value and the current Gray-code write address value; and

selectively passing one of the first logic signal and the second logic signal to control a carry chain, wherein the first logic signal is passed to control the carry chain when the FULL control signal has a first logic level, and the second logic signal is passed to control the carry chain when the FULL control signal has a second logic level.