RS-485: Imported from Wikipedia (overwrite)

2026-05-03T12:18:24Z

Imported from Wikipedia (overwrite)

New page

[[File:Locale_RS6_ΜPD485505G-25.jpg|thumb|Integrated circuit, 5,048 words by 8 bits FIFO ([[NEC]] D485505g-25)]]

In [[digital electronics]], a '''FIFO''' ([[acronym]] for ''first-in, first-out'') is a digital [[electrical circuit|circuit]] that stores incoming data in internal memory and outputs the stored data in the order it was received.<ref name="balch"/> Data is stored on demand and the oldest stored data is output on demand, with both operations occurring independently<ref name="ti"/> and at potentially different rates.<ref name="real"/> This is in contrast to a [[shift register]], which requires data to be concurrently stored and output, and for the oldest data to sequentially propagate through memory before it is output.<ref name="ti">{{cite web |title=FIFO Architecture, Functions, and Applications |url=https://www.ti.com/lit/an/scaa042a/scaa042a.pdf |publisher=Texas Instruments |access-date=25 March 2026}}</ref>

A FIFO primarily consists of a pair of counters that serve as read and write memory address registers, an addressable memory array, and status and control logic.<ref name="ganssle"/>

The data stored in a FIFO typically have a fixed [[word size]] (number of [[bit]]s), which is commonly referred to as the FIFO ''width''. The maximum possible number of stored datums is known as the FIFO ''depth''. Together, the width and depth determine the storage capacity of a FIFO.

FIFOs are used to exchange data between two hardware devices or between a hardware device and software.<ref name="herbert">{{cite web |last1=Herbert |first1=Tom |title=Hardware FIFOs — Device queues edition |url=https://medium.com/@tom_84912/hardware-fifos-device-queues-edition-b7b4ec16b0a9 |publisher=Medium |access-date=25 March 2026}}</ref> They are commonly used to exchange data between circuits that operate in different clock domains, and for buffering and [[flow control (data)|flow control]] between data producers and consumers which, over finite intervals, operate at different data rates.{{efn|name=fn2|The data producer and data consumer must operate at the same average data rate to prevent eventual FIFO overflow or underflow.<ref name="balch"/>}}<ref name="balch"/>

==Interface ports==

A FIFO has two electrical interfaces known as the ''write port'' and ''read port'', through which it exchanges data and status information with external circuits.<ref name="chipverify"/><ref name="real"/>

The external circuitry consists of a data producer that stores data in the FIFO and a data consumer that fetches the stored data.<ref name="chipverify"/> More specifically, the producer sends data to and receives status information from the write port, and the consumer receives both data and status from the read port.

===Clock domain===

Each port operates in the [[clock domain]] of the external circuit it is connected to, meaning that the port and external circuit share a common clock signal.{{efn|name=fn1|Some older FIFOs have no clock at all. These are less common and not the focus of this article.<ref name="balch">{{cite book |last1=Balch |first1=Mike |title=Complete Digital Design / A Comprehensive Guide to Digital Electronics and Computer System Architecture |isbn=0-07-143347-3 |publisher=McGraw-Hill Inc.}}</ref>}} The write port operates in the producer's clock domain and thus all write port signals are synchronized to the producer's clock. Similarly, the read port operates in the consumer's clock domain.

==FIFO types==

Every FIFO is categorized as either ''synchronous'' or ''asynchronous''.

===Synchronous FIFO <span class="anchor" id="Synchronous FIFO"></span>===

[[File:Fifo synchronous.svg|thumb|Symbolic representation of a synchronous FIFO. Both ports share a common clock, which allows them to also share status information.]]
A '''synchronous FIFO''' is an electronic FIFO that uses a common clock for the read and write ports.<ref name="Cummings"/><ref name="swathi">{{cite journal |last1=Swathi |last2=Keerthana |title=Design and Simulation of Asynchronous and Synchronous FIFO Using Verilog HDL |issn=2395-566X |journal=International Journal of Scientific Research & Engineering Trends, Volume 12, Issue 2}}</ref>

Since read and write operations take place in the same clock domain, the FIFO's status signals (buffer level, threshold flags) can be safely used by both the data producer and consumer without causing metastability. Consequently, a synchronous FIFO outputs a single, shared group of status signals.
{{clear}}

===Asynchronous FIFO <span class="anchor" id="Asynchronous FIFO"></span>===

[[File:Fifo asynchronous.svg|thumb|Symbolic representation of an asynchronous FIFO. Each port has a unique clock, thus requiring it to generate status signals specific to its clock domain.]]
An '''asynchronous FIFO''' is an electronic FIFO that uses different clocks for the read and write ports.<ref name="Cummings">{{cite web |last1=Cummings |first1=Clifford E. |title=Simulation and Synthesis Techniques for Asynchronous FIFO Design |url=https://www.researchgate.net/profile/Clifford-Cummings/publication/252160343_Simulation_and_Synthesis_Techniques_for_Asynchronous_FIFO_Design/links/54bfe9720cf28eae4a66418a/Simulation-and-Synthesis-Techniques-for-Asynchronous-FIFO-Design.pdf |publisher=Sunburst Design, Inc. |access-date=25 March 2026}}</ref><ref name="swathi"/>

To avoid errors due to [[metastability]], a dedicated set of status signals (buffer level, threshold flags) is output for each clock domain.<ref name="swathi"/> The circuitry used to circumvent metastability introduces additional latency (compared to synchronous FIFOs) into status flag updates when data is written to an empty FIFO or read from a full FIFO.<ref name="swathi"/>
{{clear}}

==Memory attributes==

To facilitate concurrent read and write operations, the memory in all asynchronous FIFOs<ref name="balch"/> and in many synchronous FIFOs is dual-ported, typically consisting of a [[register file]] or [[dual-ported RAM]] (random access memory). In asynchronous FIFOs, the memory is an asynchronous circuit that is accessible to logic operating in any clock domain.<ref name="balch"/>

===Width===

The data written to and read from a FIFO typically have the same, fixed [[word size]] (number of [[bit]]s) — commonly known as the FIFO ''width''<ref name="chipverify">{{cite web |title=Synchronous FIFO |url=https://www.chipverify.com/verilog/synchronous-fifo |website=ChipVerify |access-date=9 April 2026}}</ref> — which matches the native word size of the internal memory.

===Depth===

The maximum number of words that can be stored in a FIFO is known as the FIFO ''depth''.<ref name="chipverify"/> Although it is not required, the depth is usually an integer power of two, as this tends to simplify circuitry and improve speed performance.<ref name="aic">{{cite web |title=FIFO Design and Implementation / SystemVerilog Tutorial |url=https://aic-lab.com/systemverilog/FIFO/ |publisher=AICLAB |access-date=25 March 2026}}</ref>

To avoid overflow, the FIFO depth must be large enough to store the data resulting from the worst-case difference between data production and consumption rates,<ref name="campos"/> and the average bandwidths of the producer and consumer must match.<ref name="balch"/> Also, in asynchronous FIFOs, a small amount of additional depth is usually provided to allow for status latency.<ref name="campos"/>

==Memory address registers==

A FIFO is implemented as a [[circular buffer]] that employs two memory [[address register]]s (MARs) to store the addresses of (''[[Pointer (computer programming)|pointers]]'' to) the next memory locations to be accessed.<ref name="balch"/> The read MAR (RMAR) indicates the next location that data will be read from, and the write MAR (WMAR) indicates the next location that data will be written to.<ref name="vijay"/> Each MAR is associated with a particular port, and thus operates in that port's clock domain.

<gallery mode=packed heights="350px" widths="350px" style="text-align:left">
File:Basic synchronous FIFO.jpg|Schematic excerpt of a basic synchronous FIFO. The memory address registers (MARs) consist of binary counters that directly output memory addresses WADDR and RADDR, which designate the next words to be written to and read from memory.
</gallery>

Each MAR is implemented as a [[counter (digital)|counter]], with the count incremented every time data is transferred (WMAR incremented upon FIFO write; RMAR incremented upon FIFO read).<ref name="real">{{cite web |title=Managed Hardware FIFO, Typical FIFO circuit functions |url=https://www.realdigital.org/doc/6963618f4b9a6e5b24a1fc2417f6c5b1 |publisher=RealDigital |access-date=13 March 2026}}</ref> Initially both MARs point to the first memory location and the FIFO is empty.<ref name="vijay"/> A FIFO becomes full when the write address reaches the read address, and empty when the read address reaches the write address.<ref name="balch"/> When the MAR addresses the last location in memory, it will automatically roll over to the first memory address upon the next increment.<ref name="real"/>

For any particular FIFO, the MARs may be implemented as either binary or Gray code counters. Binary counters are usually preferred in synchronous FIFOs, as this simplifies the FIFO circuitry. [[Gray code]] counters, or Gray code-encoded binary counters, are used in asynchronous FIFOs to avoid errors due to metastability.

==Status signals==

===Buffer level===

Many FIFOs output a binary value that indicates the current buffer level (number of words stored).<ref name="vijay"/> Depending on its design, a FIFO may do this by either tracking the level with a counter or computing the level using pointer arithmetic. Synchronous FIFOs may use either method, whereas asynchronous FIFOs are restricted to using pointer arithmetic.<ref name="Cummings"/>

====Tracking via counter====

[[File:Fifo sync level counter.svg|thumb|Bidirectional (up/down) binary counter used to track buffer level. This method may be used in FIFOs in which write and read operations share a common clock, but is not suitable when reads and writes operate in different clock domains.]]

In a synchronous FIFO, the buffer level may be monitored by tracking it with a [[bidirectional counter|bidirectional binary counter]].<ref name="Cummings" /> The count is incremented when data is written to the FIFO, and decremented when data is read. The binary count value output by the counter directly indicates the buffer level.

This method is not suited to asynchronous FIFOs because the read and write ports operate in different clock domains, which would require the counter to be controlled by two different clocks.<ref name="Cummings" />

====Calculation via pointer arithmetic====

In asynchronous FIFOs, and in many synchronous FIFOs, the buffer level is calculated from the current memory addresses.
This is easily done when the FIFO is neither empty nor full because the level is equal to the difference between the write and read addresses. However, when the FIFO is empty or full, the addresses are equal and thus would be ambiguous if used to compute level.<ref name="vijay">{{cite web |last1=Nebhrajani |first1=Vijay |title=Asynchronous FIFO Architectures |url=https://fpga.eetrend.com/files-eetrend-xilinx/forum/201103/1750-3211-asynchronousfifoarchitectures1.pdf |access-date=25 March 2026}}</ref> Consequently, to distinguish between empty and full, it is common for each MAR to have one additional bit beyond what is needed to address memory. The resulting extended address (XADDR) is used to compute the FIFO level, while all bits of XADDR other than the [[Bit numbering#Most significant bit|most significant bit]] (MSB) (i.e., the LSBs) serve as the memory address.

<gallery mode=packed heights="150px" style="text-align:left">
File:Fifo binary mar bits.svg
</gallery>

In general, a MOD-<math>n</math> counter (a counter with <math>n</math> distinct output states) is used for a FIFO memory that can store <math>n/2</math> data words. For example, a MOD-32 MAR is used to generate addresses in a FIFO having a 16-word memory.

In cases where the MARs are binary counters, the buffer level is the difference between the MAR output values: <math>level=WMAR-RMAR</math>. For other output encodings (e.g., Gray code), the MAR outputs must be converted to binary before computing the difference. In either case, the difference is typically calculated by a MOD-<math>n</math> [[subtractor|binary subtractor]], with any resulting arithmetic borrow (i.e., carry out) discarded.

<gallery mode=packed heights="150px" style="text-align:left">
File:Fifo level subtractor.svg
</gallery>

===Buffer threshold flags===

A FIFO outputs individual status signals (flags) that indicate whether particular data level thresholds are met. All FIFOs output ''full'' and ''empty'' flags, and some may also output additional flags such as ''half full'', ''almost full'', and ''almost empty''.<ref name="balch"/>

Status signals may be generated by directly comparing the synchronized read and write addresses or, if available, from the FIFO level. In the latter case, status signals are derived from the FIFO level via combinational logic or, in the case of ''full'', by extracting the MSB. Depending on the FIFO design, the thresholds for ''almost full'' and ''almost empty'' flags (if implemented) may be application-specific constants or they may be programmable.<ref name="real" />

<gallery mode=packed heights="150px" widths="150px" style="text-align:left">
File:Fifo level generator.svg|Schematic diagram showing derivation of common threshold status flags. The level generator may be implemented as a binary subtractor performing pointer arithmetic, or as a level-tracking bidirectional counter.
File:Fifo programmable level detector.jpg|Programmable threshold detectors used to generate ''almost empty'' and ''almost full'' flags. Threshold levels are defined by the binary values applied to the magnitude comparator inputs.
</gallery>

====Usage====

The FIFO status flags are used to notify the external data producer and consumer that critical thresholds have been reached. Typically the producer and consumer will respond to such notifications by suspending or resuming FIFO writing and reading, respectively. The producer or consumer (or both) may be a processor that polls status or receives status via interrupts, or it may be a purely hardware entity that uses the status signals to manage flow control.

In many FIFOs, the ''full'' and ''empty'' flags are used internally to qualify the ''write enable'' and ''read enable'' signals. Writing is inhibited when ''full'' is asserted: data is not written to memory and the write MAR is not incremented. Similarly, reading is inhibited when ''empty'' is asserted: the read MAR is not incremented, and typically the previous read data is output.

==Address synchronization==

In FIFOs that compute buffer level via pointer arithmetic, the read and write addresses must be synchronized to a common clock to ensure stable inputs for the binary subtractor. This requirement is inherently satisfied in synchronous FIFOs because read and write ports use the same clock. However, asynchronous FIFOs use different clocks for read and write ports, and consequently the buffer level must be independently calculated for each port in its own clock domain. This requires the current address of each port to be synchronized to the other port's clock, a process known as [[clock domain crossing]].

Clock domain crossing is typically implemented by sequentially passing a port's current address through a series of two or more [[digital register|registers]] that are clocked by the other port. The first register synchronizes the address to the other port's clock, and subsequent register(s) mitigate any resulting [[metastability (electronics)|metastability]].

===Gray code encoding===

When incremented, a binary address will in many cases change by multiple bits at the same time (e.g., from 0111 to 1000}.<ref name="campos"/> If the changing bits happen to be sampled too close to the moment they change (and thereby violate the sampling register's setup or hold time), some may be sampled at their previous state and others at their new state, thus producing an invalid address in the destination clock domain which matches neither the previous nor the new address.<ref name="campos"/> When this happens, the buffer level calculated in the other clock domain will be incorrect.

To prevent such errors, the address is sent to the other clock domain as a Gray code value.<ref name="campos">{{cite web |last1=Campos |first1=Nelson |title=Synchronous and Asynchronous FIFOs in Hardware |url=https://sistenix.com/fifo_cdc.html |access-date=25 March 2026}}</ref> Since every address increment changes only one Gray code bit, the address received by the other clock domain is guaranteed to match either the previous or new address if sampled when the bit is changing.

In some FIFOs this is done by implementing the MAR as a Gray code counter that directly outputs Gray code addresses, as shown below:

<gallery mode=packed heights="150px" widths="350px" style="text-align:left">
File:Fifo clock domain crossing.svg|
</gallery>

Alternatively, a MAR with binary encoded outputs may be used in conjunction with a binary-to-Gray code converter. This requires the converter output to be reclocked before it crosses clock domains, to eliminate Gray code glitches caused by binary bits changing at different times.

<gallery mode=packed heights="150px" widths="350px" style="text-align:left">
File:Fifo clock domain crossing binary MAR.jpg|
</gallery>

===Address processing===

Each port sends its MAR address to the other port and receives the other port's address in Gray code via a clock domain synchronizer. Within each port, the received address is converted to binary and used to generate the buffer level and status flag signals in the port's clock domain. In FIFOs that use Gray code MARs, this is typically implemented as shown below:

<gallery mode=packed heights="400px" widths="450px" style="text-align:left">
File:Fifo async structure.svg|
</gallery>

===Status latency===

When a memory address register is incremented, the change is not immediately detected in the other clock domain.<ref name="campos"/> This is because in the process of clock domain crossing, the address must sequentially pass through a series of synchronization registers, thus delaying its arrival in the other domain. This delay, in turn, increases the status latency because the address is used to calculate FIFO status. More specifically, during this delay, the apparent FIFO level in the other clock domain remains unchanged, and consequently its threshold flags may also be stale.

Under certain conditions, this higher status latency can hinder the efficient flow of data through a FIFO.<ref name="campos"/> For example, when the consumer reads a word from a full FIFO, the write port's ''full'' flag is not immediately negated. This forces the producer to momentarily hold off new FIFO writes when it could be safely writing, resulting in a performance penalty if producer data is pending. Similarly, the read port's ''empty'' flag is not immediately negated when the producer writes to an empty FIFO, thus causing the consumer to hold off reading when data is actually available.

==Overflow==

An ''overflow'' will occur if the data producer (writer) writes to a FIFO whose memory is full.<ref name="balch"/><ref name="ganssle">{{cite web |last1=Ganssle |first1=Jack |title=What Goes In Must Come Out |url=https://www.ganssle.com/articles/afifo.htm |publisher=Embedded Systems Programming |access-date=25 March 2026}}</ref> If such a write is allowed to proceed normally, the new data word will overwrite the oldest stored word and, in the process, the write pointer (value output by the write MAR) will lap the read pointer, thus corrupting the FIFO level and making it appear that the FIFO contains only one word.<ref name="Cummings" /> To avoid this, FIFOs are usually designed to maintain the correct FIFO level by dropping (discarding) either the new word or the oldest stored word. In either case, a notification signal is usually output to inform external circuitry that data was lost.

===Mitigation by blocking===

Upon impending overflow, the new data word may be dropped by blocking FIFO writes.<ref name="ganssle"/> This is typically implemented by gating the FIFO's write enable with the ''full'' flag<ref name="Cummings" /> as shown below. In such implementations, the ''full'' flag indicates that the buffer will not accept new data. This circuit operates solely in the write port's clock domain and therefore is suited to both synchronous and asynchronous FIFOs.

<gallery mode=packed heights="130px" widths="130px" style="text-align:left">
File:Fifo overflow.svg|Typical circuit used to block writes when FIFO memory is full. A second gate outputs ''OVERFLOW'' to notify external circuitry that data has been lost.
</gallery>

===Mitigation by overwriting===

Alternatively, upon impending overflow, memory may be reallocated for the new data word by dropping the oldest stored word and reusing its memory location.<ref name="ganssle"/> This is done by writing the new word as usual (thus overwriting the oldest stored word) while concurrently incrementing the read MAR. Since both MARs are simultaneously incremented, the apparent buffer level remains unchanged. Both MARs are incremented by the write port clock; consequently this process is not suitable for asynchronous FIFOs, which require the read MAR to be incremented in the read port's clock domain.

==Applications==

===Clock domain crossing===

Many systems are composed of multiple logic circuits, each operating in a different clock domain, which must communicate with one another.<ref name="balch"/> To achieve this, every such circuit must exchange data with a circuit that is operating in a different clock domain. However, sending data directly to another clock domain is unreliable, because doing so could result in data corruption due to metastability.<ref name="aic"/> This problem is avoided by passing the data through an asynchronous FIFO, which eliminates metastability and thus ensures the integrity of the conveyed data.<ref name="aic"/>

<gallery mode=packed heights="300px" widths="300px" style="text-align:left">
File:Clock domain crossing.jpg|An asynchronous FIFO used to reliably send data from one clock domain to another. The data producer (circuit A) and consumer (circuit B) operate in clock domains CLKA and CLKB, respectively. Signal directions are left to right unless otherwise indicated by arrows.
</gallery>

===Data ingress timestamping===

Some systems require knowledge of the arrival times of words from a data producer.<ref name="ganssle"/> Common examples of this include [[radar]], [[sonar]], and [[data acquisition]] in [[control system]]s. Typically, such knowledge is acquired by timestamping each data word (associating it with the current time) when it arrives, effectively creating an [[ordered pair]] consisting of the data word and its arrival time.

In some cases, a processor cannot timestamp with sufficient accuracy (e.g., due to factors such as variable [[interrupt latency]]<ref name="ganssle"/> or data arriving faster than it can be processed). In such cases, a FIFO may be used to precisely timestamp incoming data. Upon arriving, each data word is concatenated with the current time and the result is written to the FIFO as a single, composite word. When the processor reads the composite word from the FIFO (at a convenient later time), it can easily split the composite into its component data word and timestamp.

<gallery mode=packed heights="300px" widths="300px" style="text-align:left">
File:Data ingress timestamping.jpg|A FIFO used to timestamp incoming data words. In the event of a FIFO overflow, the processor is notified via interrupt that data has been lost. Signal directions are left to right unless otherwise indicated by arrows.
</gallery>

===Pre-trigger data recording===

In some applications a FIFO must collect data preceding an event.<ref name="ti"/> For example, a [[digital storage oscilloscope|digital oscilloscope]] is commonly used to record the analog signal samples immediately preceding a trigger signal, thus allowing it to display the signal waveform that occurred prior to the trigger.

To facilitate such recording, the FIFO is designed to overwrite the oldest sample upon overflow. This allows the FIFO, when full, to continue to accept new data and to automatically retain only the newest data up to its maximum capacity.

In operation, recording is started and the FIFO begins filling with incoming samples. If allowed to record long enough, the FIFO will become full and, upon each new incoming sample, the oldest recorded sample will be discarded to make space for the new sample. When the trigger arrives, recording stops and the recorded samples may be read from the FIFO. Overflows are ignored because any lost (overwritten) data that predates the recorded data is irrelevant.

<gallery mode=packed heights="400px" widths="50px" style="text-align:left">
File:Pre-trigger recording.jpg|Example circuit illustrating how pre-trigger data is recorded using a FIFO. The [[flash ADC]] issues one sample per clock, which is stored in the FIFO when RECORD is active. Recording begins when START is asserted and ends upon TRIG. The processor is notified via [[interrupt]] (IRQ) that recording has ended, and may then read sample data until the FIFO is empty.
</gallery>

== See also ==
* [[Leaky bucket]] approach

==Notes==
{{Notelist}}

== References ==
{{Reflist}}

[[Category:Digital circuits]]

FIFO (electronic) - Revision history

RS-485: Imported from Wikipedia (overwrite)