Priority encoder: Difference between revisions

Revision as of 22:03, 16 January 2023

Latest revision as of 16:42, 19 May 2025

(11 intermediate revisions by 8 users not shown)

Line 1:

{{Short description|Digital electronic circuit}}

A '''priority encoder''' is a [[Electronic circuit|circuit]] or [[algorithm]] that compresses multiple [[Binary code|binary]] inputs into a smaller number of outputs. The output of a priority encoder is the binary representation of the index of the most significant activated line, starting from zero. They are often used to control [[interrupt request]]s by acting on the highest priority interrupt input.

A '''priority encoder''' is a [[Electronic circuit|circuit]] or [[algorithm]] that compresses multiple [[Binary code|binary]] inputs into a smaller number of outputs, similar to a [[Encoder (digital)|simple encoder]]. The output of a priority encoder is the binary representation of the [[Zero-based numbering|index]] of the [[Bit numbering|most significant]] activated line. In contrast to the simple encoder, if two or more inputs to the priority encoder are active at the same time, the input having the highest priority will take [[:wikt:precedence|precedence]]. It is an improvement on a simple encoder because it can handle all possible input combinations, but at the cost of extra logic.<ref>{{cite book |last1=Mano |first1=Moshe Morris |last2=Ciletti |first2=Michael D. |title=Digital Design |date=2007 |publisher=Pearson Prentice Hall |___location=Upper Saddle River, NJ |isbn=978-0-13-198924-5 |page=156 |edition=Fourth}}</ref>

[[File:A 4-2 Priority Encoder .jpg|alt=A 4:2 Priority Encoder|thumb|486x486px|A 4:2 Priority Encoder|center]]

If two or more inputs are given at the same time, the input having the highest priority will take [[:wikt:precedence|precedence]].<ref>M. Morris Mano, Michael D. Ciletti, "Digital Design", 4th Edition, Prentice Hall, 2006, {{ISBN|978-0-13-198924-5}}.</ref> An example of a single bit 4 to 2 encoder is shown, where highest-priority inputs are to the left and "x" indicates an irrelevant value - i.e. any input value there yields the same output since it is superseded by higher-priority input. The (optionally-included{{efn|For instance, the [[List_of_7400-series_integrated_circuits|74x148]] priority encoder does not have a dedicated output valid signal. However, all outputs high indicates invalid. https://www.ti.com/lit/ds/symlink/sn74ls148.pdf}}) "v" output indicates if the input is valid.

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>

{| class="wikitable"

==Implementation==

If two or more inputs are given at the same time, the input having the highest priority will takeA [[:wikt:precedence|precedencetruth table]].<ref>M. Morris Mano, Michael D. Ciletti, "Digital Design", 4th Edition, Prentice Hall, 2006, {{ISBN|978-0-13-198924-5}}.</ref> An example of a single bit 4 -to-2 2priority encoder is shown, where highest-prioritythe inputs are toshown thein decreasing order of priority left-to-right, and "x" indicates ana irrelevant[[don't valuecare term]] - i.e. any input value there yields the same output since it is superseded by a higher-priority input. The (optionallyusually-included{{efn|For instance, the [[List_of_7400List of 7400-series_integrated_circuitsseries integrated circuits|74x14874x147]] 10-to-4 [[BCD (character encoding)|BCD]] priority encoder does not have a dedicated output valid signal. However, invalid is indicated by all outputs highsimultaneously indicates invalidhigh. https://www.ti.com/lit/ds/symlink/sn74ls148.pdf}}) "v" output indicates if the input is valid.

{| class="wikitable" style="margin:1em auto 1em auto; text-align:center;"

|+ 4 to 2 Priority Encoder

|- style="background:#def; font-weight:bold"

!style="border-bottom:2px solid #000;"|I₃

!| colspan=4 | Input || colspan=3 style="border-bottomleft:2px solid #000;" |I₂ Output

!|- style="border-bottom:2px solid #000; background:#def; font-weight:bold"|I₁

!style="border-bottom:2px solid #000;"|I₃||I₂||I₁||I₀

!|style="border-bottom:2px solid #000; border-left:2px solid #000;"| O₁ || O₀ || v

!style="border-bottom:2px solid #000;"|O₀

!style="border-bottom:2px solid #000;"|v

|-

| 0 {{no|| 0}} || 0 {{no|| 0}} ||style="border-left:2px solid #000;"{{no| x0}} || x |{{no|0}} 0

|colspan=2 style="background: #ececec; color: #2C2C2C; border-left:2px solid #000;"|x || {{no|0}}

|-

| {{no|0}} || 0 {{no|| 0}} || 1 {{no||style="border-left:2px solid #000;"| 0}} || 0 |{{yes2|1}} 1

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

|-

| 0 {{no|| 0}} || 1 {{no|| x0}} ||style="border-left:2px solid #000;"{{yes2| 01}} || 1 |{{n/a|x}} 1

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

|-

| {{no|0}} || {{yes2|1}}

| 0 || 1 || x || x ||style="border-left:2px solid #000;"| 1 || 0 || 1

|colspan=2 {{n/a|x}}

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

|-

| {{yes2|1}}

| 1 || x || x || x ||style="border-left:2px solid #000;"| 1 || 1 || 1

|colspan=3 {{n/a|x}}

| 1 || x || x || x ||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. The priority encoder is an improvement on a simple encoder circuit, in terms of handling all possible input [[Computer configuration|configurations]].

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. The priority encoder is an improvement on a simple encoder circuit, in terms of handling all possible input [[Computer configuration|configurations]].

== 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 journalbook|lastlast1=Abdelhadi|firstfirst1=Ameer M.S.|last2=Lemieux|first2=Guy G.F.|date=May 2015|title=Modular SRAM-Based Binary Content-Addressable Memories|journal=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 journalbook|lastlast1=Abdelhadi|firstfirst1=Ameer M. S.|last2=Lemieux|first2=Guy G. F.|datetitle=December 2014 International Conference on Field-Programmable Technology (FPT) |titlechapter=Deep and narrow binary content-addressable memories using FPGA-based BRAMs |journaldate=December 2014 International Conference on Field-Programmable Technology (FPT)|pages=318–321|doi=10.1109/FPT.2014.7082808|isbn=978-1-4799-6245-7|s2cid=2074456 }}</ref> ==

== Recursive construction of priority encoders<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 journal|last=Abdelhadi|first=Ameer M.S.|last2=Lemieux|first2=Guy G.F.|date=May 2015|title=Modular SRAM-Based Binary Content-Addressable Memories|journal=2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines|pages=207–214|doi=10.1109/FCCM.2015.69|isbn=978-1-4799-9969-9}}</ref><ref>{{Cite journal|last=Abdelhadi|first=Ameer M. S.|last2=Lemieux|first2=Guy G. F.|date=December 2014|title=Deep and narrow binary content-addressable memories using FPGA-based BRAMs|journal=2014 International Conference on Field-Programmable Technology (FPT)|pages=318–321|doi=10.1109/FPT.2014.7082808|isbn=978-1-4799-6245-7}}</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.

Priority-encoders can be efficiently constructed by recursion. The input vector is split into <math>k</math> equal fragments with <math>n/k</math> bits. A priority encoder <math>\textrm{PE}_{n/k}</math> with a narrower width of 𝑛/𝑘 is applied for each fragment. The valid bit of each of the <math>k</math> <math>\textrm{PE}_{n/k}</math>‘s goes to a <math>k</math> bit <math>\textrm{PE}_{n/k}</math> to detect the first valid fragment. The ___location of this fragment is the higher part of the overall index, and steers the exact ___location within the fragment itself to produce the lower part of the overall index.

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’sAltera'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 |firstfirst1=A.M.S. |lastlast1=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 |firstfirst1=A.M.S. |lastlast1=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 71 ⟶ 84:

==Notes==

{{Portal|Electronics}}

{{notelist}}