Synthesis of Index Generation Function Using Linear and Functional Decomposition
Document Type
Conference Proceeding
Publication Date
1-7-2021
Publication Title
Lecture Notes in Networks and Systems
Volume
182
First page number:
115
Last page number:
127
Abstract
© 2021, Springer Nature Switzerland AG. Researchers have thoroughly studied decomposition in many different contexts, such as switching theory or data mining. In recent years, a renewed interest in this problem was caused by memory-based pattern matching circuits, particularly in the synthesis of Index Generation Functions. In this case, function is a composition of a linear function L and a general function G. The function L is implemented using ExOR gates, while G is usually realized using embedded memories. In this paper, we show that the linear function reduces the number of variables to represent an index generation function, thus reducing memory size. However, as another efficient technique for logic synthesis using memories, a functional decomposition can be applied. The decomposition is a methodology of expressing a function of n variables as a bunch (collection) of functions of fewer variables. This paper presents an exact method of searching for a functional decomposition with a minimum number of variables by using the theory of r-admissibility. Therefore, the method proposed can be used for ROM-based synthesis, particularly for pattern matching and communication circuits.
Keywords
Functional decomposition; Index generation function; Linear decomposition; Logic cell
Disciplines
Electrical and Computer Engineering
Language
English
Repository Citation
Borowik, G.,
Łuba, T.,
Wąsicki, D.,
Chmaj, G.
(2021).
Synthesis of Index Generation Function Using Linear and Functional Decomposition.
Lecture Notes in Networks and Systems, 182
115-127.
http://dx.doi.org/10.1007/978-3-030-65796-3_11