State-controlled half-parallel array walsh transform

Abstract

A matrix multiplier for performing a Fast Walsh Transform (FWT) is disclosed, based on Good's factorization of the FWT. The matrix multiplier has a plurality of N inputs for receiving N input signals. A first plurality of multiplexers is provided, which includes a first group of n multiplexers, where n=pth root of N, and a second group of each other multiplexer. Each multiplexer of the first and second groups, has first and second inputs. The first input is connected to a corresponding input of the matrix multiplier for receiving one of the N input signals. A plurality of (N/2) adder/subtractor units are connected to the multiplexers of the first group. A plurality of flip-flop circuits are provided, each being connected to one of the adder/subtractor units. A second plurality of multiplexers is provided. Each multiplexer of the second plurality is connected to a first group of at least two of the flip-flop circuits. The multiplexers of the first group of the first plurality of multiplexers receive an output of a corresponding one of second plurality of multiplexers as a second input. The multiplexers of the second group of the first plurality of multiplexers receive an output of a corresponding one of a second group of the flip-flops as a second input. A signal generating circuit is also provided for outputting a first signal to a select input of each of the first plurality of multiplexers, a second signal to a switch input of each first adder/subtractor circuit, a third signal to a switch input of each second adder/subtractor circuit, a fourth signal to a clock input of each flip-flop, and a fifth signal to a select input of each of the second plurality of multiplexers.