Priority encoder: Difference between revisions

Revision as of 06:19, 3 October 2023

Latest revision as of 16:42, 19 May 2025

(5 intermediate revisions by 5 users not shown)

Line 4:

Applications of priority encoders include their use in [[Programmable interrupt controller|interrupt controllers]] (to allow some [[interrupt request]]s to have higher priority than others), decimal or [[binary encoding]], and [[Analog-to-digital converter|analog-to-digital]] / [[Digital-to-analog converter|digital to-analog]] conversion.<ref>{{cite book |title=The TTL Applications Handbook |date=August 1973 |publisher=Fairchild Semiconductor |page=4-4}}</ref>

==Implementation==

[[File:A 4-2 Priority Encoder .jpg|alt=Gate-level diagram of a single bit 4-to-2 Priority Encoder|thumb|486x486px|[[Logic gate|Gate-level]] diagram of a single bit 4-to-2 priority encoder. I(3) has the highest priority.|center]]

A [[truth table]] of a single bit 4-to-2 priority encoder is shown, where the inputs are shown in decreasing order of priority left-to-right, and "x" indicates a [[don't care term]] - i.e. any input value there yields the same output since it is superseded by a higher-priority input. The (usually-included{{efn|For instance, the [[List of 7400-series integrated circuits|74x147]] 10-to-4 [[BCD (character encoding)|BCD]] priority encoder does not have a dedicated output valid signal. However, invalid is indicated by all outputs simultaneously high. https://www.ti.com/lit/ds/symlink/sn74ls148.pdf}}) "v" output indicates if the input is valid.

Line 33 ⟶ 32:

|style="background:#bfd; color:black; border-left:2px solid #000;"|1 || {{yes2|1}} || {{yes2|1}}

|}

[[File:A 4-2 Priority Encoder .jpg|alt=Gate-level diagram of a single bit 4-to-2 Priority Encoder|thumb|486x486px|[[Logic gate|Gate-level]] diagram of a single bit 4-to-2 priority encoder. I(3) has the highest priority.|center]]

Priority encoders can be easily connected in arrays to make larger encoders, such as one 16-to-4 encoder made from six 4-to-2 priority encoders – four 4-to-2 encoders having the signal source connected to their inputs, and the two remaining encoders take the output of the first four as input.

== Recursive construction of priority encoders ==

== Recursive construction of priority encodersSources:<ref>{{Cite thesis|title=Architecture of block-RAM-based massively parallel memory structures : multi-ported memories and content-addressable memories|url=https://open.library.ubc.ca/cIRcle/collections/ubctheses/24/items/1.0314219|publisher=University of British Columbia|date=2016|first=Ameer M. S.|last=Abdelhadi}}</ref><ref>{{Cite book|last1=Abdelhadi|first1=Ameer M.S.|last2=Lemieux|first2=Guy G.F.|title=2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines |chapter=Modular SRAM-Based Binary Content-Addressable Memories |date=May 2015|pages=207–214|doi=10.1109/FCCM.2015.69|isbn=978-1-4799-9969-9|s2cid=16985129 }}</ref><ref>{{Cite book|last1=Abdelhadi|first1=Ameer M. S.|last2=Lemieux|first2=Guy G. F.|title=2014 International Conference on Field-Programmable Technology (FPT) |chapter=Deep and narrow binary content-addressable memories using FPGA-based BRAMs |date=December 2014|pages=318–321|doi=10.1109/FPT.2014.7082808|isbn=978-1-4799-6245-7|s2cid=2074456 }}</ref> ==

A priority-encoder, also called leading zero detector (LZD) or leading zero counter (LZC), receives an <math>n</math>-bit input vector and detects the index of the first binary ‘1’ in the input vector. A valid signal indicates if any binary ‘1’ was detected in the input vector, hence the index is valid.

Line 43 ⟶ 46:

The depth of the proposed structure is <math>\lceil\log_kn\rceil</math>, while the hardware area complexity is <math>\mathcal{O}(n)</math>. If Altera's Stratix V or equivalent device is used, <math>k=4</math> is recommended to achieve higher performance and area compression, since the mux can be implemented using 6-LUT, hence an entire ALM.

An open-source [[Verilog]] generator for the recursive priority-encoder is available online.<ref name=II2DCAM>{{Cite web|url=https://github.com/AmeerAbdelhadi/Indirectly-Indexed-2D-Binary-Content-Addressable-Memory-BCAM/blob/master/pe |first1=A.M.S. |last1=Abdelhadi |first2=G.G.F. |last2=Lemieux |title=Modular SRAM-based Indirectly-indexed 2D Binary Content Addressable Memory II2DCAM |publisher=The University of British Columbia |date=2014 }}<br/>

{{cite book |first1=A.M.S. |last1=Abdelhadi |first2=G.G.F. |last2=Lemieux |chapter=Modular SRAM-Based Binary Content-Addressable Memories |chapter-url=http://www.ece.ubc.ca/~lemieux/publications/abdelhadi-fccm2015.pdf |title=2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines |publisher=IEEE |___location= |date=2015 |isbn=978-1-4799-9969-9 |pages=207–214 |doi=10.1109/FCCM.2015.69|s2cid=16985129 }}</ref>

[[File:PE-recursion.svg|alt=Priority-encoder (left) symbol (right) recursive definition.|center|thumb|416x416px|Priority-encoder (left) symbol (right) recursive definition.]]

A behavioral description of priority encoder in Verilog is as follows.<ref name=II2DCAM/> In this case, the LSB has the highest priority.<syntaxhighlight lang="verilog" line="1">

// behavioural description of priority enconder;

// https://github.com/AmeerAbdelhadi/Indirectly-Indexed-2D-Binary-Content-Addressable-Memory-BCAM

Line 81 ⟶ 84:

==Notes==

{{Portal|Electronics}}

{{notelist}}