Conference paper

MIKUŠEK Petr and DVOŘÁK Václav. On Lookup Table Cascade-Based Realizations of Arbiters. In: 4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Znojmo: Masaryk University, 2008, pp. 261-261. ISBN 978-80-7355-082-0.
Publication language:english
Original title:On Lookup Table Cascade-Based Realizations of Arbiters
Title (cs):Realizace arbitrů pomocí LUT kaskád
Proceedings:4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Conference:MEMICS'08 -- 4th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Place:Znojmo, CZ
Publisher:Masaryk University
+Type Name Title Size Last modified
iconmikusek_memics2008.pdf40,3 KB2008-12-02 20:13:47
^ Select all
With selected:
LUT cascades, Multi-Terminal BDDs, iterative disjunctive decomposition, arbiter circuits
Design of digital systems with a degree of regularity in physical placement of subsystems and in their interconnection has always been a much desired goal and is even more so at present. A regular logic has advantages which make it more attractive: short development time, better utilization of chip area, easy testability and easy modifications all end up in a lower cost. A one-dimensional cascade of look-up tables (LUT cells) is such a regular structure.

LUTs are in fact multiple-input, multiple-output universal logic blocks. LUTs in block RAMs may provide support for reconfigurable architectures, asynchronous cascades or clocked pipelines; speed is competitive with other FPGA designs, layout and wiring are very easy. The LUT cascade is a promising reconfigurable logic device for future sub-100nm LSI technology. Sequential processing of LUT cascades by means of micro-engines with multi-way branching can improve firmware performance a great deal.

In this presentation we will present a new algorithm of iterative decomposition for multiple-output Boolean functions with an embedded heuristics to order variables. The algorithm produces a cascade of look-up tables that implements the given function and simultaneously a sub-optimal Multi-Terminal Binary Decision Diagram (MTBDD). Its main contribution is that the bottom-up synthesis of MTBDD/LUT cascade does not require knowledge of optimum ordering of variables, because the order of variables is generated concurrently. The LUT cascade can be used for pipelined processing on FPGAs with BRAMs or at a non-traditional synthesis of large combinational and sequential circuits. On the other hand, suboptimal MTBBDs can serve as prototypes for efficient firmware implementation, especially when a micro-programmed controller that firmware runs on supports multi-way branching. A novel technique is illustrated on practical examples of three types of arbiters. It may be quite useful as a more flexible alternative implementation of digital systems with increased testability and improved manufacturability.

The presentation will be based on a paper we have presented recently at DSD 2008.

   author = {Petr Miku{\v{s}}ek and V{\'{a}}clav Dvo{\v{r}}{\'{a}}k},
   title = {On Lookup Table Cascade-Based Realizations of Arbiters},
   pages = {261--261},
   booktitle = {4th Doctoral Workshop on Mathematical and Engineering
	Methods in Computer Science},
   year = {2008},
   location = {Znojmo, CZ},
   publisher = {Masaryk University},
   ISBN = {978-80-7355-082-0},
   language = {english},
   url = {}

Your IPv4 address:
Switch to IPv6 connection

DNSSEC [dnssec]