US5426756A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Memory controller and method determining empty/full status of a FIFO memory using gray code counters
Assignee: Altera Corp
•
Filing: 1992-08-11
•
Granted: 1995-06-20
•
Expires: 2012-08-11
Abstract
Abstract A controller for asynchronous configurable FIFO (first-in-first-out) memory includes, in addition to two binary counters for the read pointer and write pointer, two Gray code counters for determining whether the FIFO is full or empty by a comparison of the read pointer and write pointer values expressed in Gray code. The Gray code counters avoid the problem of asynchronicity of read and write signals. The Gray code counters determine if the FIFO is full or empty depending on whether the pointer values match (indicating empty) or differ in accordance with particular Gray code patterns (indicating full). The Gray code counters each have an extra bit which allows determination of the full or empty condition from a straightforward comparison of the read pointer and write pointer values, while the Gray code eliminates the problem of multiple bit transition providing an incorrect indication of the pointer location. The controller is implemented in logic circuitry which is configurable depending on the FIFO configuration and system configuration considerations.
Inventors
- 👤 Jonathan Shyi
- 👤 Kenny Shen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 19:36
CPC Classifications
G; G06; G06F; G06F5/00; G06F5/06; G06F5/10; G06F5/12; G06F5/14; H; H03; H03K; H03K23/00; H03K23/004; H03K23/005; G06F2205/00; G06F2205/10; G06F2205/102
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
208 words
A memory controller for controlling a reading of data from and a writing of data to a memory having a plurality of locations, where the reading of data is asynchronous to the writing of data, comprising: two counters for indicating respectively which of the locations is currently being read from and written to; first and second Gray code counters, each having at least one more bit than needed for respectively indicating, in Gray code, which of the locations is currently being read from and written to the memory controller including a first synchronizer for synchronizing an output signal of the first Gray code counter to a system clock signal; comparator circuitry for comparing contents of the second Gray code counter to the synchronized output signal, and if the contents of the second Gray code counter and the synchronized output signal of the first Gray code counter are identical, indicating that all the locations of the memory are empty, and if the contents of tile second Gray code counter and the synchronized output signal of the first Gray code counter differ by a quantity equal to the number of locations in the memory as determined solely by the comparison indicating that all the locations of the memory are full.
Claim 2
Dependent Claim
208 words
A memory controller for controlling a reading of data from and a writing of data to a memory having a plurality of locations, where the reading of data is asynchronous to the writing of data, comprising: two counters for indicating respectively which of the locations is currently being read from and written to; first and second Gray code counters, each having at least one more bit than needed for respectively indicating, in Gray code, which of the locations is currently being read from and written to the memory controller including a first synchronizer for synchronizing an output signal of the first Gray code counter to a system clock signal; comparator circuitry for comparing contents of the second Gray code counter to the synchronized output signal, and if the contents of the second Gray code counter and the synchronized output signal of the first Gray code counter are identical, indicating that all the locations of the memory are empty, and if the contents of tile second Gray code counter and the synchronized output signal of the first Gray code counter differ by a quantity equal to the number of locations in the memory as determined solely by the comparison indicating that all the locations of the memory are full.
Claim 3
Dependent Claim
34 words
The memory controller of claim 1, wherein the memory is a first-in-first-out (FIFO) memory and the memory controller controls the reading of data from and the writing of data to the first-in-first-out (FIFO) memory.
Claim 4
Dependent Claim
23 words
The memory controller of claim 1, wherein each of the full and empty indications are control signal flags generated by the memory controller.
Claim 5
Dependent Claim
35 words
The memory controller of claim 1, wherein the comparator circuitry includes a plurality of exclusive OR gates, there being one such gate for each bit in each of the first and second Gray code counters.
Claim 6
Dependent Claim
28 words
The memory controller of claim 1, the comparator circuitry further comprising a portion for indicating that some but not all of the locations of the memory are occupied.
Claim 7
Dependent Claim
23 words
The memory controller of claim 1, wherein the memory controller receives configuration information and the number of locations in the memory is configurable.
Claim 8
Dependent Claim
57 words
The memory controller of claim 6, further comprising a plurality of terminals for receiving configuration signals as the configuration information for indicating the number of locations in the memory, and a multiplexer controlled by the configuration signals for determining which of a plurality of outputs of the comparator circuitry will be used to generate a full indication.
Claim 9
Dependent Claim
57 words
The memory controller of claim 1, wherein the comparator circuitry includes two portions, the first portion comparing the synchronized output signal to the contents of the second Gray code counter, and providing the full indication, the second portion comparing the synchronized output signal to the contents of the second Gray code counter and providing the empty indication.
Claim 10
Dependent Claim
59 words
The memory controller of claim 8, the second Gray code counter further comprising a second synchronizer for synchronizing an output signal from the second Gray code counter to a read clock signal, and wherein the comparator circuitry includes a third portion for comparing the synchronized output signal from the second synchronizer to contents of the first Gray code counter.
Claim 11
Independent Claim
254 words
A method for controlling a reading of data from and a writing of data to a memory having a plurality of locations, where the reading of data is asynchronous to the writing of data, comprising: indicating which of the locations is currently being read from and written to; providing two Gray code counters, each having at least one more bit than needed for respectively indicating in Gray code which of the plurality of locations is currently being read from and written to; indicating in a first of the two Gray code counters which of the locations is currently being read from; indicating in a second of the two Gray code counters which of the locations is currently being written to; synchronizing an output signal of the first of the Gray code counters to a system clock signal; comparing contents of the second of the Gray code counters to the synchronized output signal from the first of the Gray code counters; if the contents of the second of the Gray code counters and the synchronized output signal of the first of the Gray code counters are identical, providing a signal indicating that all the locations of the memory are empty of data; and if the contents of the second of the Gray code counters and the synchronized output signal of the first of the Gray code counters differ by a quantity equal to the number of locations in the memory, providing a signal indicating that all the locations of the memory are full of data.
Claim 12
Independent Claim
254 words
A method for controlling a reading of data from and a writing of data to a memory having a plurality of locations, where the reading of data is asynchronous to the writing of data, comprising: indicating which of the locations is currently being read from and written to; providing two Gray code counters, each having at least one more bit than needed for respectively indicating in Gray code which of the plurality of locations is currently being read from and written to; indicating in a first of the two Gray code counters which of the locations is currently being read from; indicating in a second of the two Gray code counters which of the locations is currently being written to; synchronizing an output signal of the first of the Gray code counters to a system clock signal; comparing contents of the second of the Gray code counters to the synchronized output signal from the first of the Gray code counters; if the contents of the second of the Gray code counters and the synchronized output signal of the first of the Gray code counters are identical, providing a signal indicating that all the locations of the memory are empty of data; and if the contents of the second of the Gray code counters and the synchronized output signal of the first of the Gray code counters differ by a quantity equal to the number of locations in the memory, providing a signal indicating that all the locations of the memory are full of data.
Claim 13
Dependent Claim
35 words
The method of claim 10, further comprising the step of inputting configuration information to the memory controller, wherein the number of locations and the width of data at each location of the memory is configurable.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-06-19 | 1998-12-19 | 1999-06-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-06-19 | 2002-12-19 | 2003-06-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-06-19 | 2006-12-19 | 2007-06-20 | $7700.00 | Window Closed / Lapsed |