Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Improved First-In First-Out

IP.com Disclosure Number: IPCOM000117582D
Original Publication Date: 1996-Apr-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 88K

Publishing Venue

IBM

Related People

Schrum Jr, SB: AUTHOR

Abstract

Disclosed is an improved method of constructing a First-In First-Out (FIFO) buffer. The Improved FIFO may be implemented using digital circuitry or software programming. Hardware implementations are particularly suitable for resynchronization of data from one clock system to another, due to the simple, glitch-free full/empty detection.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Improved First-In First-Out

      Disclosed is an improved method of constructing a First-In
First-Out (FIFO) buffer.  The Improved FIFO may be implemented using
digital circuitry or software programming.  Hardware implementations
are particularly suitable for resynchronization of data from one
clock system to another, due to the simple, glitch-free full/empty
detection.

      Advantages of the Improved FIFO include: straightforward
hardware implementation which avoids asynchronous logic, delay lines,
and special clocking; utilization of all data storage locations; and
simple, glitch-free determination of the state of the FIFO.

      The Improved FIFO consists of a Data Storage Array constructed
of fixed addressable storage locations, which is utilized as a
circular queue.  For hardware implementations, the Data Storage Array
may be implemented using either flip-flops, transparent latches, or a
Random Access Memory (RAM).  "Get" and "Put" counters are used to
index into the  Data Storage Array, and they control which locations
are to be read and  written respectively.  The Get and Put counters
are independently advanced after reading/writing data into/out of the
FIFO.

      The Get and Put counters utilize either one or two additional
bits, depending upon the type of Improved FIFO, beyond that required
to address the Data Storage Array.  These additional bits are called
"Roll-over bits".  The use of these bits allows all storage locations
to be utilized (if all of the locations contain valid data then the
FIFO is in a "full" state).  Also, they simplify the task of
determining the state (i.e., empty/full/underflow/overflow) of the
FIFO, which may be derived by comparing the Get and Put counters,
incl...