Classification and properties of fast linearly independent logic transformations

Abstract

The existence of numerous number of linearly independent (L1) transformations in GF(2) algebra finds application in the design of exclusive-or based polynomial expansions. For a chosen L1 matrix transformation, such expansion gives a canonical representation of an arbitrary completely specified logical function. In this paper, family of L1 transformations is introduced which possesses fast forward and inverse butterfly diagrams. These transforms are recursively defined and grouped into classes where consistent formulas relating forward and inverse transform matrices are obtained. The classification is further extended into various L1 transforms with horizontal and vertical permutations. The possibility of easy implementation of polynomial expansions based on classified L1 logic transformations in the form of readily available fine grain FPGAs and EPLDs is also illustrated.