First-in, first-out memory with counter address pointers for generating multiple memory status flags

Claims

What is claimed is:

1. A first-in, first-out memory, comprising:

a memory having a plurality of write-addressable and read-addressable memory locations;

a data input coupled to a plurality of data latches for writing data into at least one write-addressed memory location of said memory;

a data output coupled to a plurality of output buffers for reading data from at least one read-addressed memory location of said memory;

a write pointer for write-addressing said at least one write-addressed memory location, said at least one write-addressed location having an address represented by a plurality of write address digits, a write address digit register of said write pointer provided for storing each write address digit, said write pointer operable to address said write-addressed location responsive to said write address digit registers storing said respective write address digits;

a read pointer for read-addressing said at least one read-addressed memory location, said at least one read addressed memory location having an address represented by a plurality of read address digits, a read address digit register in said read pointer provided for storing each of said read address digits, said read pointer operable to address said read-addressed location responsive to said read address read address digit registers storing respective read address digits;

a status flag generator circuit receiving outputs from the read and write pointers operable to determine how many of the memory locations are presently storing data and to generate a plurality of status flags, each status flag generated responsive to the number of memory locations addressed by the read and write pointers.

2. The first-in, first-out memory of claim 1, wherein said status flag generator comprises a pointer comparator for comparing said write address digits to said read address digits, and operable to generates a plurality of intermediate signals based on selected numerical differences between said write address digits and said read address digits; and

a flag decoder for receiving said intermediate signals and operable to generate therefrom a plurality of memory status flags, said status flags transmitted to said data latches and said output buffers for control of write and read operations.

3. The first-in, first-out memory of claim 2 wherein said flag decoder is operable to generate a HALF-FULL status flag for indicating that at least half of the memory locations in said memory have data stored therein.

4. The first-in, first-out memory of claim 2 wherein said write address digit registers comprise a lower-order write address digit register for storing a lower-order write address digit and a higher-order write address digit registers for storing a higher-order address digit;

said read address digit registers comprising a higher-order read address digit register for storing a higher-order read address digit, and a lower-order read address digit register for storing a low-order read address digit;

said pointer comparator operable to generate said intermediate signals based on comparisons between said lower-order write address digit and said lower-order read address digit, and between said higher-order write address digit and said higher-order read address digit.

5. The first-in, first-out memory of claim 4 wherein said flag decoder comprises a HALF-FULL status flag generator operable to generate a HALF-FULL status flag for indicating that at least half of said memory locations have data stored therein;

said HALF-FULL flag generator comprising a first intermediate signal input from said pointer comparator that is in an active state responsive to said lower-order write address digit exceeding said lower-order read address digit by one;

a second intermediate signal from said pointer comparator input into said HALF-FULL flag generator and assuming an active state responsive to said lower-order write address digit being less than said lower-order read address digit by one;

a third intermediate signal from said pointer comparator input into said HALF-FULL flag generator and assuming an active state responsive to said higher-order write address digit displaced from the value of said higher-order read address digit by half of the possible range of said higher-order address digits;

a fourth intermediate signal from said pointer comparator input into said HALF-FULL flag generator and assuming an active state responsive to said lower-order write address digit equaling said lower-order read address digit;

a HALF-FULL equality signal generator receiving said third and fourth intermediate signals and outputting an active state of a HALF-FULL equality signal responsive to both said third and fourth intermediate signals being in an active state;

an inactive state of said second intermediate signal and a subsequent active state of said half-full equality signal causing said HALF-FULL flag to go from an inactive state to an active state, an active sate of said second intermediate signal and a subsequent inactive state of said HALF-FULL equality signal causing said HALF-FULL flag to go from an active state to an inactive state.

6. The first-in, first-out memory of claim 4 wherein said flag decoder comprises an ALMOST-FULL flag signal generator operable to generate an ALMOST-FULL flag signal for indicating that most of said memory locations have data stored therein;

said ALMOST-FULL flag signal generator comprising first intermediate signal input from said pointer comparator and that is in an active state when said lower-order write address digit exceeds said lower-order read address digit by one;

a second intermediate signal from said pointer comparator input into said ALMOST-FULL flag signal generator and assuming an active state responsive to said lower-order write address digit being less than said lower-order read address digit by one;

a third intermediate signal from said pointer comparator input into said ALMOST-FULL flag signal generator and assuming an active state responsive to said higher-order write address digit exceeding the value of said higher-order read address digit by one;

a fourth intermediate signal from said pointer comparator input into said ALMOST-FULL flag signal generator and assuming an active state responsive to said lower-order write address digit equaling said lower-order read address digit;

an ALMOST-FULL equality signal generator of said ALMOST-FULL flag signal generator coupled to said third and fourth intermediate signals and outputting an active state of an ALMOST-FULL equality signal responsive to both the third and fourth intermediate signals being in an active state;

an inactive state of said second intermediate signal and a subsequent active state of said ALMOST-FULL equality signal causing said ALMOST-FULL flag signal to go from an inactive state to an active state, an active state of said second intermediate signal and a subsequent inactive state of said ALMOST-FULL equality signal causing said ALMOST-FULL flag signal to go from an active state to an inactive state.

7. The first-in, first-out memory of claim 4, wherein said flag decoder comprises an ALMOST-EMPTY flag signal generator operable to generate an ALMOST-ENTRY flag signal for indicating that most of said memory locations do not have data stored therein;

said ALMOST-EMPTY flag generator comprising a first intermediate signal input from said pointer comparator and assuming an active state responsive to said lower-order write address digit exceeding said lower-order read address digit by one;

a second intermediate signal input from said pointer comparator into said ALMOST-EMPTY flag generator and assuming an active state responsive to said lower-order write address digit being less than said lower-order read address digit by one;

a third intermediate signal from said pointer comparator into said ALMOST-EMPTY flag generator and assuming an active state responsive to said higher-order write address digit being less than the value of said higher-order read address digit by one;

a fourth intermediate signal input from said pointer comparator into said ALMOST-EMPTY flag generator and assuming an active state responsive to said lower-order write address digit equalling said lower-order read address digit;

an ALMOST-EMPTY equality signal assuming an active state responsive to both the third and fourth intermediate signals being in an active state;

an active state of said first intermediate signal and a succeeding inactive state of said ALMOST-EMPTY equality signal causing said ALMOST-EMPTY flag signal output to go from an active state to an inactive state, an inactive state of said first intermediate signal and an active state of said ALMOST-EMPTY equality signal causing said ALMOST-EMPTY flag signal output to go from an inactive state to an active state.

8. The first-in, first-out memory of claim 2 wherein said flag decoder is operable to generator an ALMOST-FULL flag signal for indicating that most of said memory locations have data stored therein.

9. The first-in, first-out memory of claim 8 wherein said ALMOST-FULL flag signal is generated responsive to predetermined states of a plurality of intermediate signal inputs from said pointer comparator.

10. The first-in, first-out memory of claim 8 wherein said write address digits include a lower-order write address digit, an active state of said ALMOST-FULL flag signal generated responsive to said write address equaling said read address minus a number within the possible range of said lower-order write address digit.

11. The first-in, first-out memory of claim 2 wherein said flag decoder is operable to generate an ALMOST-EMPTY flag signal for indicating that most of said memory locations do not have data stored therein.

12. The first-in, first-out memory of claim 11 wherein said ALMOST-EMPTY flag signal is generated responsive to predetermined state of a plurality of intermediate signals from said pointer comparator.

13. The first-in, first-out memory of claim 11 wherein said read address digits include a lower-order read address digit, said ALMOST-EMPTY flag signal generated responsive said write address exceeding said read address by a number within the possible range said lower-order read address digit.

14. The first-in, first-out memory of claim 11 wherein said flag decoder is operable to generator an ALMOST-FULL flag signal for indicating that most of said memory locations have data stored therein;

said flag decoder operable to generate a HALF-FULL status flag responsive to at least half of said memory locations having data stored therein;

an ALMOST FULL/EMPTY status flag output of said flag decoder being in an active state responsive to either an active state of said ALMOST-FULL flag signal or an active state of said ALMOST-EMPTY flag signal.

15. The first-in, first-out memory of claim 14 wherein said flag decoder is operable to generate an EMPTY status flag and a FULL status flag, said EMPTY status flag generated responsive to all of said memory locations having no data stored therein, said FULL flag signal generated responsive to all of said memory locations having data stored therein;

said write address digits and said read address digits each comprising lower-order and higher-order address digits, said point comparator operable to compare a higher-order write address digit to a higher-order read address digit, and a lower-order write address digit to a lower-order read address digit, a higher-order equality intermediate signal generated by said pointer comparator responsive to the equality of said higher-order write address digit with said higher-order read address digit, a lower-order equality intermediate signal generated by said pointer comparator responsive to said lower-order write address digit being equal to said lower-order read address digit;

an equality signal generated by said flag decoder responsive to active states of both said higher-order intermediate equality signal and said lower-order intermediate equality signal, said EMPTY status flag generated responsive to simultaneous active states of said equality signal and said ALMOST-EMPTY flag signal, said FULL flag generated responsive to simultaneous active states of said equality signal and said ALMOST-FULL flag signal.

16. The first-in, first-out memory of claim 1 wherein said read address digits and said write address digits each comprise lower-order and higher-order address digits, said write pointer and said read pointer each comprising:

a lower-order counter for storing a lower-order address bit at one of a plurality of address locations therein, each said address location representing a value of said lower-order digit;

a higher-order counter for storing a higher-order address bit at one of a plurality of higher-order address locations therein, each higher-order address location representing a value of said higher-order digit;

said higher-order address bit transferred form a current address location to a next address location responsive to a signal form said lower-order counter, said lower-order counter transmitting said signal upon said lower-order address bit being transferred to a predetermined one of said lower-order address locations;

a plurality of registers each for addressing a respective memory location, a first input of each said register receiving an output from a higher-order address location, a second input of each said register receiving an output from a lower-order address location, each of said registers operable to address said respective memory location responsive to sensing said lower-order address bit and said higher-order address bit at its inputs.

17. The FIFO memory of claim 1 wherein said write pointer and said read pointer each include:

a plurality of counters each of a different order and including at least a low-order counter and a high-order counter, each counter provided for storing an address digit of particular order, said address digits in combination representing one of a plurality of memory locations in said memory;

each counter having a plurality of stages, each corresponding to an address digit value, an address bit stored in one of said plurality of stages for indicating the value of the respective address digit;

said counters coupled in cascading fashion in ascending order with said high-order counter coupled to said low-order counter, a high-order address bit of said high-order counter incremented from a current stage to a next stage responsive to a signal from said low-order counter, said low-order counter operable to transmit said signal responsive to a low-order address bit thereof being incremented to a predetermined one of said lower-order stages; and

a plurality of registers each for addressing a respective memory location, each register having a plurality of inputs each coupled to an output of a stage in each counter;

each stage in each said counters operable to transmit an address bit signal responsive to having an address bit stored therein, each said register operable to address a respective memory location responsive to receiving address bit signals on all its inputs.

18. The read and write pointers further of claim 16 further including a clock signal source operable to transmit clock pulses, each clock pulse having first and second transitions;

said respective lower-order counter and said respective higher-order counter coupled to said clock signal source, said lower-order counter operable to increment from a first address location to a next address location responsive to said first transition of a clock pulse;

each respective said register including a latch coupled to said lower-order counter and said higher-order counter, said latch operable to store an address signal responsive to said second transition of a prior clock pulse;

said address signal transmitted from said latch to a respective address location in said memory responsive to said first transition.

19. The FIFO memory of claim 1 wherein each said read pointer and said write pointer include:

a respective lower-order ring counter having a plurality of lower-order stages each operable to store a lower-order address bit, said lower-order stages each having an output and an input, the outputs of each said lower-order stage coupled to the input of a next lower-order stage in an endless ring, each lower-order stage having a clock input;

a respective higher-order ring counter having a plurality of higher-order stages each operable to store a higher-order address bit, said higher-order stages each having an output and an input, the output of each said higher-order stage coupled to the input of a next higher-order stage in an endless ring, each higher-order stage having a clock input;

a respective last lower-order stage having an output coupled to said clock inputs of said higher-order stages, the receipt by said last lower-order stage of said lower-order address bit actuating the transmission of a higher-order clock signal to said higher-order clock inputs, said higher-order address bit incrementing from a current higher-order stage to a next higher-order stage responsive thereto;

a respective plurality of product gates, each product gate receiving as inputs an output from a selected one of said higher-order stages and an output from a selected one of said lower-order stages, each product gate having a combination of inputs different from the combination of inputs of each other gate; and

a respective plurality of registers each selectively coupled to an output of a respective product gate for addressing a respective memory location responsive to said respective product gate sensing said lower-order and said higher-order address bits.

20. The FIFO memory of claim 19 wherein said product gates further include a plurality of last product gates having an input coupled to said last lower-order stage, said product gates further including a plurality of first product gates each having an input connected to a first lower-order stage, said last lower-order stage operable to increment said lower-order address bit to said first lower-order stage responsive to a clock signal;

an output of each last product gate coupled to an inverter, said last product gates arranged in an array wherein successive ones of said higher-order stage outputs are coupled to successive ones of said last product gates, an output of each last product gate inverter coupled to an input of a successive last product gate input, said output of said last product gate inverter further coupled to an input of a first product gate coupled to the same higher-order stage output;

each responsive inverter preventing the addressing by a respective first product gate or a respective next successive last product gate of memory locations corresponding thereto.

21. The FIFO memory of claim 19 wherein each product gate has a read power-up output coupled to a respective address memory location for enabling a read operation of said memory location.

22. The FIFO memory of claim 19 wherein each product gate has a write select output and a write power-up output;

each respective register having a latch for storing a write select signal, a sum gate coupled to an output of said latch for generating a write enable signal on a first sum gate output, said sum gate further connected to a clock signal source;

said sum gate having a second output connected to a write power-up gate, said write power-up gate receiving as an input a respective write power-up output from a respective product gate and outputting a write power-up signal responsive to an active stage of either said write power-up signal from said product gate line or said second output from said sum gate.

23. The FIFO memory of claim 1 further including:

a write/read controller for generating a write pulse responsive to an external write command and for generating a read pulse responsive to an external read command, said write pointer addressing a write memory location of a plurality of memory locations responsive to said write pulse, said read pointer addressing a read memory location of said plurality of memory locations responsive to said read pulse, said write/read controller comprising:

a write pulse generator for generating said write pulse responsible to said external write command;

a read pulse generator for generating said read pulse responsible to said external read command;

a register coupled to said write and read pulse generators for determining whether a write pulse or a read pulse was last generated;

a pointer equality input for indicating that said write memory location is equal to said read memory location; and

a disabler for disabling said write pulse generator and said read pulse generator, said disabler coupled to said pointer equality input and said register, said disabler disabling said write pulse generator responsive to an active state of said equality input and the last generated pulse being a write pulse, said disabler disabling said read pulse generator responsive to an active state of said equality input and the last generated pulse being a read pulse.

24. The FIFO memory of claim 23 further including:

a data bit storage circuit for storing a binary data bit therein;

at least one data input coupled to said data storage circuit for writing a data bit therein;

a write enable line coupled to said storage circuit for initiating the writing of a data bit into said storage circuit;

a write power-up line coupled to said storage circuit for enabling the writing of a data bit into said storage circuit, said write power-up line activating only a predetermined number of cells out of a plurality of cells in said memory;

a read circuit having an input coupled to said storage circuit, a read enable line coupled to said read circuit for addressing said memory cell for initiating the reading of a data bit from said storage circuit; and

a read power-up line coupled to said read circuit for enabling the data bit storage in said cell to be read out on said data output, said read power-up line enabling only selected ones of said plurality of memory cells in said memory.

TECHNICAL FIELD OF THE INVENTION

The present invention relates in general to first-in, first-out (FIFO) memories, and more particularly relates to FIFO memories capable of storing a large number of words and generating ALMOST-FULL/ALMOST-EMPTY and HALF-FULL status flags.

BACKGROUND OF THE INVENTION

In digital systems, it is frequently necessary to interface different parts of the system which handle data at different rates. For example, it is often desirable to interface a disk drive to a central processing unit (CPU). Commonly, a first-in, first-out (FIFO) memory is used to perform this interface. A FIFO memory is a storage device that allows data to be written into it and read from it at different data rates.

Certain recent FIFO memories have the capability to store sixteen words, and use a write pointer to latch a current write address. While the write occurs to a memory location in the memory, the write pointer increments to the next location. This architecture, called a simultaneous memory write architecture, allows for a shorter write cycle time. An example of such a FIFO memory is described in our co-pending application Ser. No. 892,228, filed Aug. 1, 1986. Now U.S. Pat. No. 4,829,475. This memory employs a write address ring counter and a read address ring counter. The write address ring counter sequentially addresses each memory word location in response to input write commands. The read address ring counter operates similarly to sequentially read memory word locations responsive to input read commands. A comparator is provided for this device for comparing the current address of the write address ring counter with that of the read address ring counter. When equality exists between the counters, and if the last memory operation was a read operation, the next read operation will be inhibited by an EMPTY flag. On the other hand, if the write and read address ring counters point to the same memory location, and the last operation was a write operation, a further write operation without an intervening read will be inhibited by a FULL flag.

More recently, there has been a demand in the industry for one-chip FIFO memories with more capacity, such as a 64-word size. In addition, the industry has begun to specify that the FIFO memory outputs include, in addition to the EMPTY and FULL flags already mentioned, an ALMOST-FULL/ALMOST-EMPTY flag and a HALF-FULL flag.

Several schemes have been developed in order to select which of the words in a 64-word FIFO will be written into or read out of. One such scheme is to employ an n stage ring counter, where n is the number of memory words. The n ring counter method requires 64 flip-flops but no decoding circuitry. Another scheme is the log.sub.2 n stage binary counter. This scheme requires six flip-flops, but also requires 64 6-input AND gates for decoding purposes.

Certain recent FIFO memories use a monostable multivibrator or one-shot generator in order to originate a WRITE CLOCK pulse for actuating the write address ring counter. As will be described in more detail below, one conventional approach is to input a non-delayed input signal into a NAND gate, and to also input the signal into a delay path including an RC circuit. The delay path inverts the delayed signal at its output, which is connected as an input to the NAND gate. Therefore, this one-shot generator will produce a signal as long as the inverted, delayed input has yet to be received by the NAND gate.

The dependence of this one-shot generator on an RC time constant causes problems in regulating the width of the one-shot output pulse. This output pulse must be wide enough for the pointers to successfully increment to a new location and to complete a memory write, but not so wide that the maximum clocking rate suffers. This one-shot circuit also produces a pulse width that is variable with the voltage swing of the signal. Both the RC delay and the voltage swing can substantially vary due to processing variations.

Conventional FIFO memories have a plurality of cell locations that are continuously powered up and enabled for either a memory write operation or a memory read operation. Where TTL logic is used, this requires a large amount of power consumption.

From the above, it can be seen that a need has arisen in the industry for a FIFO memory that: (a) has a larger-than-sixteen-word capacity, but is not unduly complex in its pointer and decoder circuitry; (b) is capable of generating FULL, EMPTY, ALMOST-FULL/ALMOST-EMPTY, and HALF-FULL flags with a minimum of extra circuitry; (c) incorporates a monostable multivibrator or one-shot generator with a more precisely controlled pulse width; and (d) has a memory cell design with decreased power consumption.

SUMMARY OF THE INVENTION

One aspect of the present invention comprises a first-in, first-out (FIFO) memory. The memory has a plurality of write- and read-addressable memory locations for storing data. A data input of the FIFO is coupled to a first connected device for writing data into at least one write-addressed memory location. A data output of the FIFO is coupled to a second connected device for reading data from at least one read-addressed memory location.

Circuitry is provided for determining how many of the memory locations are presently storing data. One technical advantage of the invention results in the inclusion in this circuitry of a first circuit for generating an ALMOST-EMPTY/ALMOST-FULL status flag when either most of the memory locations have no data stored therein, or when most of the memory locations do have data stored therein. Another advantage results from the provision of a second circuit of this circuitry for generating a HALF-FULL flag responsive to at least half of the memory locations having data stored therein. Outputs are provided for transmitting the ALMOST-EMPTY/ALMOST-FULL and the HALF-FULL status flags to the first and second connected devices. The circuitry preferably also includes circuits for generating FULL and EMPTY status flags.

Another aspect of the invention comprises an address pointer for a FIFO memory. One technical advantage inheres in the address pointer comprising a lower-order counter for storing a lower-order address bit at one of a plurality of address locations therein, and a higher-order counter for storing a higher-order address bit at one of a plurality of higher-order address locations therein. The higher-order address bit is operable to be incremented from a current address location to a next address location responsive to a signal from the lower-order counter. The lower-order counter transmits the signal responsive to a lower-order address bit being incremented to a predetermined one of the lower-order address locations.

A plurality of addressers are provided, each for addressing a respective memory location in the memory. A first input of each addresser receives an output from a higher-order address location. A second input of each said addresser receives an output from a lower-order address location. Each of the addressers operates to address a respective memory location responsive to sensing lower-order and higher-order address bits at its inputs.

The dual-tier or higher-order and lower-order architecture of the address pointer of the invention provides an advantage in that it reduces the number of gates, flip-flops and gate inputs required for decoding a selected one of the memory locations.

The two-tier ring counter structure minimizes the number of flip-flops and the number of the decoding gates. Flip-flops are required to obtain the simultaneous memory write technical advantage, as will be described in greater detail below. Only 16 flip-flops and 128 two-input AND gates are required in the illustrated embodiment.

The dual-tier approach also has advantages in generating the above-described memory status flags, as will be described below.

Yet another aspect of the invention comprises a FIFO memory register that comprises a plurality of read-addressable memory locations. A data output is provided for coupling at least one read-addressed memory location to a connected device. A read pointer of the FIFO comprises a plurality of read-addressers that are each operable to address at least one selected location of the memory. A technical advantage of the invention is provided by a read power-up output of each addresser that is operable to supply sufficient power to the addressed location to enable data at the location to be read. A read addressing output of each addresser is operable to cause the selected location to be read out to the data output. The addressable read power-up feature of the invention presents a technical advantage in that a first, low power consumption of each memory cell is all that is required to keep data stored therein. A second, higher power necessary to read out the cells in an addressed word can be selectively applied to the addressed word only, without powering up the remainder of the memory.

A further aspect of the invention comprises a FIFO memory register that has a plurality of write-addressable memory locations. A data input is provided for coupling at least one write-addressed memory location to a connected device. A write pointer of the FIFO comprises a plurality of write-addressers that are each operable to address at least one selected memory location. A write power-up output of each addresser is operable to supply sufficient power to the addressed memory location to enable data to be written into that location. A write addressing output of each addresser is operable to cause data to be written into the selected location from the data input. Preferably, a write power-up pulse begins to be delivered from the selected write-addresser at a time previous to delivering a pulse on the write addressing output. This insures that each memory cell so addressed will be completely powered up before the write addressing operation begins.

The addressable write power-up feature of the invention presents a technical advantage in that a low-power consumption of each non-addressed memory cell can be maintained, while spending a larger amount of power only on those cells selected for a write (or read) operation. The addressable read power-up and write power-up features of the invention together substantially reduce the power consumption of the FIFO memory.

In another aspect of the invention, outputs from a read pointer and a write pointer are advantageously used to generate memory status flags for output to connected devices. The read pointer comprises a register for storing a higher-order read address digit and a register for storing a lower-order read address digit. The write pointer similarly has a register for storing a higher-order write address digit and a register for storing a lower-order write address-digit.

The write pointer is operable to address a selected write-addressed location in the FIFO memory responsive to the value of the stored write address digit, and the read pointer is operable to address a selected read-addressed location responsive to the value of the stored read address digit. A status flag generator compares the write address digits to the read address digits and is operable to generate selected ones of a plurality of status flags responsive thereto. Each status flag is generated responsive to a selected numerical difference between the write address digits and the read address digits.

Preferably, the status flag generator is comprised of a pointer comparator that compares the higher-order write address digit to the higher-order read address digit, and the lower-order write address digit to the lower-order read address digit. These comparisons are used to generate a plurality of intermediate signals.

The status flag generator is further preferably comprised of a flag decoder that receives the intermediate signals and is operable to generate the memory status flags. The intermediate signals preferably comprise a plurality of higher-order intermediate signals that include: an HE signal that is in an active state responsive to the higher-order read address digit equalling the higher-order write address digit; an HM1 signal generated responsive to the higher-order read address digit exceeding the higher-order write address digit by one; an HP1 intermediate signal that is generated when the higher-order read address digit is less than the higher-order write address digit by one; and a further higher-order intermediate signal that is generated when the higher-order read address digit is displaced from the higher-order write address digit by half of the possible range of the higher-order address digits. A plurality of lower-order intermediate signals are also generated, and these preferably include LM1, LE and LP1. These signals are generated in a manner analogous to the generation of their higher-order intermediate signal counterparts.

The generation of the intermediate signals confers the advantage of being able to in turn generate HALF-FULL, FULL, ALMOST-FULL/EMPTY and EMPTY status flags with a very small number of logic gates. The LP1, LM1, HP4 and LE intermediate signals are used as into a HALF-FULL status flag generator. LP1, LM1, HM1 and LE are used as inputs to an ALMOST-FULL flag signal generator. LP1, LM1, LE and HP1 are used as inputs to an ALMOST-EMPTY flag signal generator. The ALMOST-FULL and ALMOST-EMPTY flag signals are used to generate an ALMOST FULL/ALMOST EMPTY status flag, and are further in turn used together with the HE and LE signals to generate FULL and EMPTY status flags.

One technical advantage of the invention is conferred by the pointers being organized into higher-order and lower-order address digit registers or ring counters. This represents a significant savings in the number of logic gates necessary to generate the status flags. For example, given a FIFO of 64 words controlled by a 64-stage, single-tier write pointer and a 64-stage, single-tier read pointer, a total of 320 gates would have to be included to generate HALF-FULL, FULL, ALMOST-EMPTY, and EMPTY signal flags. These 320 gates would be apart from further gates that would be required to latch in conditions such that, for example, the HALF-FULL status flag would last longer than a single clock cycle, so that the HALF-FULL flag would continue to be in an active state when the write pointer was more than 50% of the memory ahead of the read pointer.

In contrast, the lower-order pointer comparator of the preferred embodiment uses 24 gates; the higher-order pointer comparator uses 32 gates; and the status flag decoder uses 21 further gates, for a total of 87 gates.

Another aspect of the invention comprises a novel one-shot generator or monostable multivibrator. The one-shot generator comprises a NAND gate, a latch and a delay path. The NAND gate is coupled to an input of the one-shot generator and its output is coupled to the output of the one-shot generator, and also to the input of the delay path. The latch has one input coupled to the input of the generator and an output coupled to an input of the NAND gate. A second input of the latch is coupled to the output of the delay path. The latch is initialized to store and transmit a first high signal, which in turn enables the NAND gate to output a low-going transition of a low pulse responsive to the multivibrator input going high. The low-going transition is output from the multivibrator and is further input into the delay path. The delay path in turn delivers the delayed low-going transition to the latch, which stores and transmits a low signal in response. The low signal causes the NAND gate to output a high-going transition, ending the output pulse. A succeeding low-going transition on the multivibrator input sets up the NAND gate and the latch to issue the next pulse responsive to the next high-going transition on the multivibrator input.

The one-shot generator of the invention provides a significant technical advantage in that the width of the pulses that it produces are not affected by RC time constant considerations or variations in load capacitance, both of which were problems with prior art one-shot circuits.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other aspects of the invention and their advantages will be more fully understood by referring to the Detailed Description that follows in conjunction with the appended drawings in which:

FIG. 1 is a schematic logic block diagram of a first-in, first-out (FIFO) memory according to the invention;

FIG. 2 is a detailed schematic logic diagram of a write/read control section of the FIFO memory shown in FIG. 1;

FIG. 3 is a schematic electrical diagram of a prior art one-shot generator;

FIG. 4 is a timing diagram illustrating the operation of the prior art one-shot generator shown in FIG. 3;

FIG. 5 is a schematic logic diagram of a one-shot generator according to the invention;

FIG. 6 is a timing diagram illustrating the operation of the one-shot generator shown in FIG. 5;

FIG. 7 is a detailed schematic electrical diagram of the write pointer shown in FIG. 1;

FIG. 8 is a timing diagram illustrating the operation of the write pointer shown in FIG. 7;

FIG. 9 is a detailed schematic electrical diagram of the read pointer shown in FIG. 1;

FIG. 10 is a timing diagram illustrating the operation of the read pointer shown in FIG. 9;

FIG. 11a is an electrical schematic diagram of a read enable NAND gate for use with the read pointer shown in FIG. 9;

FIG. 11b is an electrical schematic diagram of another read enable NAND gate for use with the read pointer shown in FIG. 9;

FIG. 12 is an electrical schematic diagram of a write select and power-up NAND gate for use with the write pointer shown in FIG. 7;

FIG. 13 is a logic diagram of a preferred memory cell for use with the invention;

FIG. 14 is a schematic electrical diagram corresponding to the logic diagram of FIG. 13;

FIG. 15a is a logic diagram of a lower-order address digit comparator according to the invention;

FIG. 15b is a logic diagram of a higher-order address digit comparator according to the invention;

FIG. 16 is a detailed logic diagram of the status flag decoder shown in FIG. 1; and

FIG. 17 is a timing diagram showing the operation of the flag decoder illustrated in FIG. 16.

DETAILED DESCRIPTION

Referring first to FIG. 1, a logic block diagram of a preferred FIFO memory 10 according to the invention is shown. Memory 10 comprises a memory array 12 that in a preferred embodiment has 64 rows and nine columns. The illustrated memory array 12 is capable of storing 64 words, each word having nine bits. Array 12 has a plurality of data inputs indicated generally at 14 and a plurality of data outputs indicated generally at 16. Inputs 14 are output from a plurality of data latches 18, which are in turn connected to a plurality of external data inputs indicated generally at 20. External data or external write inputs 20 are in turn output f