LOOK-AHEAD COMPUTATION: IMPROVING ITERATION BOUND IN LINEAR RECURSIONS.

A technique of look-ahead computation applicable to any linear recursive algorithm to achieve equivalent realizations with reduced iteration period and higher sampling rate is introduced. The concurrency created by the use of look-ahead computation can be used to obtain pipelined and/or block implementations. The authors illustrate the applicability of the look-ahead computation technique to obtain high-speed VLSI realizations of linear time-invariant and time-varying systems. A generalized look-ahead computation technique theorem for arbitrary interleaving is also presented. Finally, it is shown that the iteration period in certain synchronous data flow graphs can also be reduced by the use of look-ahead computation.