Synthesis of Index Generation Function Using Linear and Functional Decomposition
Lecture Notes in Networks and Systems
First page number:
Last page number:
© 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.
Functional decomposition; Index generation function; Linear decomposition; Logic cell
Electrical and Computer Engineering
Synthesis of Index Generation Function Using Linear and Functional Decomposition.
Lecture Notes in Networks and Systems, 182