Gate based decomposition of index generation functions

Authors: Tadeusz Łuba, Grzegorz Borowik, Cezary Jankowski

An Index Generation Function (IGF) is adapted for special applications of incompletely specified Boolean function. IGF is used in many universal areas, e.g., in the Internet as IP filtering circuits, or in memory circuits as pattern matching circuits. The problem is also related to data mining and perfect hashing. The development of the mentioned research areas faces the problem of effective IGF hardware realization. In this paper, we propose new methods for implementation of index generation functions with memories of fewer number of inputs. In contrary to the traditional approaches, where the basic components of the network are EXOR gates, the functional decomposition allows us developing the structure that use any kind of gates.