Priority encoder

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 74x147 10-to-4 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.

class="wikitable" style="margin:1em auto 1em auto; text-align:center;" |+ 4 to 2 Priority Encoder
style="background:#def; font-weight:bold" | colspan=4 | Input	colspan=3 style="border-left:2px solid #000;" | Output
style="border-bottom:2px solid #000; background:#def; font-weight:bold" |I3	I2	I1	I0 |style="border-left:2px solid #000;"| O1	O0	v
{{no|0}}	{{no|0}}	{{no|0}}	{{no|0}} |colspan=2 style="background: #ececec; color: #2C2C2C; border-left:2px solid #000;"|x	{{no|0}}
{{no|0}}	{{no|0}}	{{no|0}}	{{yes2|1}} |style="background: #FFC7C7; color: black; border-left:2px solid #000;"|0	{{no|0}}	{{yes2|1}}
{{no|0}}	{{no|0}}	{{yes2|1}}	{{n/a|x}} |style="background: #FFC7C7; color: black; border-left:2px solid #000;"|0	{{yes2|1}}	{{yes2|1}}
{{no|0}}	{{yes2|1}} |colspan=2 {{n/a|x}} |style="background:#bfd; color:black; border-left:2px solid #000;"|1	{{no|0}}	{{yes2|1}}
{{yes2|1}} |colspan=3 {{n/a|x}} |style="background:#bfd; color:black; border-left:2px solid #000;"|1	{{yes2|1}}	{{yes2|1}}

File:A 4-2 Priority Encoder .jpg 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.

Sources:{{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}}{{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 }}{{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 }}

A priority-encoder, also called leading zero detector (LZD) or leading zero counter (LZC), receives an $n$-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 $k$ equal fragments with $n/k$ bits. A priority encoder $\backslash textrm\{PE\}\_\{n/k\}$ with a narrower width of 𝑛/𝑘 is applied for each fragment. The valid bit of each of the $k$ $\backslash textrm\{PE\}\_\{n/k\}$‘s goes to a $k$ bit $\backslash textrm\{PE\}\_\{n/k\}$ 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 $\backslash lceil\backslash log\_kn\backslash rceil$, while the hardware area complexity is $\backslash mathcal\{O\}(n)$. If Altera's Stratix V or equivalent device is used, $k=4$ 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.{{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 }}

{{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 }}

File:PE-recursion.svg

A behavioral description of priority encoder in Verilog is as follows. In this case, the LSB has the highest priority.

// behavioural description of priority enconder;

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

module pe_bhv

#( parameter OHW = 512 ) // encoder one-hot input width

( input clk , // clock for pipelined priority encoder

input rst , // registers reset for pipelined priority encoder

input [ OHW -1:0] oht , // one-hot input / [ OHW -1:0]

output reg [`log2(OHW)-1:0] bin , // first '1' index/ [`log2(OHW)-1:0]

output reg vld ); // binary is valid if one was found

// use while loop for non fixed loop length

// synthesizable well with Intel's QuartusII

always @(*) begin

bin = {`log2(OHW){1'b0}};

vld = oht[bin] ;

while ((!vld) && (bin!=(OHW-1))) begin

bin = bin + 1 ;

vld = oht[bin];

end

end

endmodule

File:A Simple 4-2 encoder using or gate.jpg

{{Main|Encoder (digital)}}

A simple encoder circuit is a one-hot to binary converter. That is, if there are 2ⁿ input lines, and at most only one of them will ever be high, the binary code of this 'hot' line is produced on the n-bit output lines.

{{Portal|Electronics}}

{{notelist}}

{{Reflist}}

{{DEFAULTSORT:Priority Encoder}}

Category:Digital circuits