NEW DIGIT-SERIAL IMPLEMENTATIONS OF STACK FILTERS

We propose several new ways to find the tradeoff between throughput an d complexity of stack filter implementations using digit-serial proces sing. First, we consider the problem in general for lexicographic repr esentations of input data and suggest a digit-serial procedure to calc ulate the stack filter output. This procedure is a generalization of t he bit-serial algorithm for stack filters (Chen, 1989) and we show als o that this digit-serial procedure can be used for stack filters if an d only if the data representation is lexicographic. Next, we consider the digit-serial case based on multiple-value representations with rad ix r. We show that stack filters can be realized with an arbitrary num ber r of positive Boolean function units varying from one in the bit-s erial case (Chen, 1989) to M - 1 in the parallel threshold decompositi on structure (Wendt et al., 1986). This class of parallel implementati ons parametrized by r allows us to choose the fastest possible archite cture when the complexity is bounded by application requirements. Thes e parallel architectures reduce both the delay and the cycle time of t he circuit, a property that cannot be achieved systematically by the o ther methods. (C) 1997 Elsevier Science B.V.