FIFO memory including a comparator circuit for determining full/empty conditions using mode control and carry chain multiplexers

• US 6,405,269 B1
• Filed: 05/09/2000
• Issued: 06/11/2002
• Est. Priority Date: 10/07/1999
• Status: Expired due to Fees

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Ebeling, Christopher D., Camilleri, Nicolas J.
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US09/568,556
• Time in Patent Office: 763 Days
• Field of Search: 710/52, 710/57, 711/109, 711/110, 365/221, 365/189.07
• 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 comparator circuit for detecting full and empty conditions in a first-in first-out (FIFO) memory system. The comparator circuit includes two-input logic circuits for comparing selected read and write addresses. An almost-empty condition is detected by comparing a next-to-be-used read address value with a currently-used write address value. When these address values are equal, high logic signals are passed by a set of mode control multiplexers to the select terminals of a series of carry chain multiplexers, thereby causing a high logic value to be transmitted to a data input terminal of a first register. The first register latches the high logic signal at the next rising edge of the read clock signal, thereby generating a high EMPTY control signal immediately after a final data value is read from the memory. The high EMPTY control signal causes the mode control multiplexers to pass logic signals generated by comparing a current read address value and a current write address value, which are equal when the memory is in the empty condition. The full condition is determined in a similar fashion, using a second carry chain to transmit logic signals related to both an almost-full and the full condition.

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 port for receiving a sequence of write address values during write operations, and a read address port for receiving a sequence of read address values during read operations; and

a comparator circuit for detecting an empty condition of the memory by comparing a write address value with first and second read address values, the comparator circuit comprising;

first and second logic circuits for respectively generating first and second logic signals, the first logic signal having a value determined by comparing a first bit of the first read address value and a first bit of the write address value, and the second logic signal having a value determined by comparing a first bit of the second read address value and the first bit of the write address value,

a first mode control multiplexer having a first input terminal connected to receive the first logic signal, and a second input terminal connected to receive the second logic signal,

a first carry chain multiplexer having a select input terminal connected to an output terminal of the first 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 for storing an EMPTY control signal;

wherein a data input terminal of the register is coupled to an output terminal of the first carry chain multiplexer, and an output terminal of the register is connected to a select terminal of the first mode control multiplexer.

2. The FIFO memory system according to claim 1, wherein the first and second logic circuits are exclusive-NOR gates.

3. The FIFO memory system according to claim 1,

wherein read operations are enabled by an externally-generated READ_ENABLE control signal;

wherein the register includes a clock enable terminal; and

wherein the comparator further comprises a logic gate having a first input terminal connected to receive the READ_ENABLE signal, a second input terminal connected to the output terminal of the register, and an output terminal connected to the clock enable terminal of the register.

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

third and fourth logic circuits for respectively generating third and fourth logic signals, the third logic signal having a value determined by comparing a second bit of the first read address value and a second bit of the write address value, and the fourth logic signal having a value determined by comparing a second bit of the second read address value and the second bit of the write address value;

a second mode control multiplexer having a first input terminal connected to receive the third logic signal, and a second input terminal connected to receive the fourth logic signal; and

a second carry chain multiplexer coupled between the output terminal of the first carry chain multiplexer and the data input terminal of the register, the second carry chain multiplexer having a select input terminal connected to an output terminal of the second mode control multiplexer, a first input terminal connected to the output terminal of the first carry chain multiplexer, and a second input terminal connected to the second source;

wherein the data input terminal of the register is coupled to the output terminal of the second carry chain multiplexer, and

wherein the output terminal of the register is connected to a select terminal of the second mode control multiplexer.

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

a read address register section, including a first binary-to-Gray-code converter, for generating the first and second read address values by converting binary read address values of the sequence of read address values into Gray-code read address values; and

a write address register section, including a second binary-to-Gray-code converter, for generating the write address value by converting a binary write address value of the sequence of write address values into a Gray-code write address value.

6. The FIFO memory system according to claim 1, wherein the memory and comparator circuit are implemented using a field programmable gate array.

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

8. The FIFO memory system according to claim 1, wherein the sequence of write addresses and the sequence of read addresses are generated synchronously.

9. The FIFO memory system according to claim 1, wherein the sequence of write addresses and the sequence of read addresses are generated asynchronously.

10. A first-in first-out (FIFO) memory system comprising:

a memory having a plurality of locations each having an address, a write address port for receiving a sequence of write address values-during write operations, and a read address port for receiving a sequence of read address values during read operations; and

a comparator circuit for detecting a full condition of the memory by comparing a read address value with first and second write address values, the comparator circuit comprising;

first and second logic circuits for respectively generating first and second logic signals, the first logic signal having a value determined by comparing a first bit of the read address value and a first bit of the first write address value, and the second logic signal having a value determined by comparing the first bit of the read address value and the first bit of the second write address value,

a first mode control multiplexer having a first input terminal connected to receive the first logic signal, and a second input terminal connected to receive the second logic signal,

a first carry chain multiplexer having a select input terminal connected to an output terminal of the first 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 for storing a FULL control signal;

wherein a data input terminal of the register is coupled to an output terminal of the first carry chain multiplexer, and an output terminal of the register is connected to a select terminal of the first mode control multiplexer.

11. The FIFO memory system according to claim 10, wherein the first and second logic circuits are exclusive-NOR gates.

12. The FIFO memory system according to claim 10,

wherein write operations are enabled by an externally-generated WRITE_ENABLE control signal;

wherein the register includes a clock enable terminal; and

wherein the comparator further comprises a logic gate having a first input terminal connected to receive the WRITE_ENABLE signal, a second input terminal connected to the output terminal of the register, and an output terminal connected to the clock enable terminal of the register.

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

third and fourth logic circuits for respectively generating third and fourth logic signals, the third logic signal having a value determined by comparing a second bit of the read address value and a second bit of the first write address value, and the fourth logic signal having a value determined by comparing the second bit of the read address value and a second bit of the second write address value;

a second mode control multiplexer having a first input terminal connected to receive the third logic signal, and a second input terminal connected to receive the fourth logic signal; and

a second carry chain multiplexer coupled between the output terminal of the first carry chain multiplexer and the data input terminal of the register, the second carry chain multiplexer having a select input terminal connected to an output terminal of the second mode control multiplexer, a first input terminal connected to the output terminal of the first carry chain multiplexer, and a second input terminal connected to the second source;

wherein the data input terminal of the register is coupled to the output terminal of the second carry chain multiplexer, and

wherein the output terminal of the register is connected to a select terminal of the second mode control multiplexer.

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

a read address register section, including a first binary-to-Gray-code converter, for generating the read address value by converting a binary read address value of the sequence of read address values into a Gray-code read address value; and

a write address register section, including a second binary-to-Gray-code converter, for generating the first and second write address values by converting binary write address values of the sequence of write address values into Gray-code write address values.

15. The FIFO memory system according to claim 10, wherein the memory and comparator circuit are implemented using a field programmable gate array.

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

17. The FIFO memory system according to claim 10, wherein the sequence of write addresses and the sequence of read addresses are generated synchronously.

18. The FIFO memory system according to claim 10, wherein the sequence of write addresses and the sequence of read addresses are generated asynchronously.

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

a memory having a plurality of locations each having an address, a write address port for receiving a sequence of write address values during write operations, and a read address port for receiving a sequence of read address values during read operations; and

a comparator circuit for detecting a full condition and an empty condition of the memory by comparing selected read address values with selected write address values, the comparator circuit comprising;

means for comparing the selected read address values and the selected write address values, and for generating logic signals having values dependent on whether the selected read address values are equal to the selected write address values,

a plurality of mode control multiplexers having input terminals connected to receive selected pairs of the plurality of logic signals,

a plurality of carry chain multiplexers having select input terminals connected to associated output terminals of the plurality of mode control multiplexers, and first input terminals connected to a first source maintained at a first logic level,

a first register for storing an EMPTY control signal, and

a second register for storing a FULL control signal,

wherein the carry chain multiplexers of a first group of the plurality of carry chain multiplexers respectively include second input terminals and output terminals that form a first carry chain connected between a second source maintained at a second logic level and a data input terminal of the first register, and

wherein the carry chain multiplexers of a second group of the plurality of carry chain multiplexers respectively include second input terminals and output terminals that form a second carry chain connected between the second source maintained at the second logic level and a data input terminal of the second register.

20. The memory system according to claim 19,

wherein the mode control multiplexers of a first group of the plurality of mode control multiplexers respectively include select terminals connected to a data output terminal of the first register, and

wherein the mode control multiplexers of a second group of the plurality of mode control multiplexers respectively include select terminals connected to a data output terminal of the second register.