Priority encoder: Difference between revisions

Revision as of 02:31, 29 February 2020

Revision as of 11:27, 29 February 2020

Line 26:

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<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-05|title=Modular SRAM-Based Binary Content-Addressable Memories|url=https://ieeexplore.ieee.org/document/7160073/|journal=2015 IEEE 23rd Annual International Symposium on Field-Programmable Custom Computing Machines|pages=207–214|doi=10.1109/FCCM.2015.69}}</ref><ref>{{Cite journal|last=Abdelhadi|first=Ameer M. S.|last2=Lemieux|first2=Guy G. F.|date=December 2014-12|title=Deep and narrow binary content-addressable memories using FPGA-based BRAMs|url=https://ieeexplore.ieee.org/document/7082808/|journal=2014 International Conference on Field-Programmable Technology (FPT)|pages=318–321|doi=10.1109/FPT.2014.7082808}}</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 33:

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>{{Cite web|url=https://github.com/AmeerAbdelhadi/Indirectly-Indexed-2D-Binary-Content-Addressable-Memory-BCAM/blob/master/pe|title=https://github.com/AmeerAbdelhadi/Indirectly-Indexed-2D-Binary-Content-Addressable-Memory-BCAM/blob/master/pe|last=|first=|date=|website=|url-status=live|archive-url=|archive-date=|access-date=}}</ref>.

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

A behavioral description of priority encoder in Verilog is as follows .<ref>{{Cite web|url=https://github.com/AmeerAbdelhadi/Indirectly-Indexed-2D-Binary-Content-Addressable-Memory-BCAM|title=AmeerAbdelhadi/Indirectly-Indexed-2D-Binary-Content-Addressable-Memory-BCAM|website=GitHub|language=en|access-date=2020-02-29}}</ref>.<syntaxhighlight lang="verilog" line="1">

A behavioral description of priority encoder in Verilog is as follows <ref>{{Cite web|url=https://github.com/AmeerAbdelhadi/Indirectly-Indexed-2D-Binary-Content-Addressable-Memory-BCAM|title=AmeerAbdelhadi/Indirectly-Indexed-2D-Binary-Content-Addressable-Memory-BCAM|website=GitHub|language=en|access-date=2020-02-29}}</ref>.<syntaxhighlight lang="verilog" line="1">

// behavioural description of priority enconder;

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