Electrical computers and digital processing systems: support – Digital data processing system initialization or configuration
Reexamination Certificate
1998-10-30
2001-03-13
Lee, Thomas C. (Department: 2182)
Electrical computers and digital processing systems: support
Digital data processing system initialization or configuration
C713S100000, C712S229000
Reexamination Certificate
active
06202148
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a commutator circuit. In particular, the present invention relates to a commutator circuit for reorganizing sequences of digital data between computational processing stages of a hardware digital processing system.
BACKGROUND OF THE INVENTION
In many areas of digital signal and image processing there is a need to reorganize sequences of digital data between the computational processing stages of a digital processing system. One particularly important area is in the computation of fast Fourier transforms. The fast Fourier transform (FFT) is a well known mathematical algorithm for performing Fourier transform operations. The Fourier transform is widely used in Digital Signal Processing (DSP) applications to determine the frequency spectral content of digital signals or data. Similar digital data reorganization is also required in the computation of other mathematical operations such as the discrete cosine and sine transforms and in many image processing applications where computations are first performed on a row of pixels followed by a column of pixels or vice versa.
Such mathematical operations, including the FFT, are often implemented in hardware. When so implemented, the data reorganization is commonly effected using a commutator circuit. Existing commutator circuits are, however, application specific. For example, in the case of an FFT processor, which would comprise a number of commutator circuits, each commutator circuit is individually devised according to a number of application requirements such as: the size of the transform; the data word-lengths; the data word-widths; and the level of pipelining in the FFT processor. The transform size relates to the number of data samples in one data block, or data set, and is commonly expressed as the ‘point’ of the transform. Furthermore, there are a considerable number of known algorithms which may be used to implement any particular FFT and the structure of the commutator circuit is also dependent on which algorithm is used for the application in question. It will be appreciated therefore, that there are a considerable number of permutations of factors which determine the structure of the commutator circuit. Conventionally, once a commutator circuit is designed in accordance with a particular combination of application requirements, the circuit is dedicated for use with that particular combination of requirements. The design of commutator circuits for an FFT processor by conventional methods is a labour intensive procedure, typically requiring months of design time.
It is an object of the present invention to provide a commutator circuit based on a generalised commutator architecture characterised by a set of parameters, which commutator architecture allows a commutator circuit to be constructed for any specific application requirements upon selection of the values of said parameters to suit said specific application requirements.
SUMMARY OF THE INVENTION
Accordingly, the present invention provides a commutator circuit comprising at least one data transposition circuit connected between a pair of data inputs and a pair of data outputs, the data transposition circuit including two 2-to-1 selector switches each having two inputs connected to respective ones of the pair of data inputs and a single output connected to a respective one of the pair of data outputs, and a delay element connected in series with one of the data inputs and/or one of the data outputs, the commutator circuit further comprising an input for synchronizing signals and means for deriving from the synchronizing signals a control signal for the selector switches. The commutator circuit comprises a plurality of stages connected in series, each stage having a plurality of data inputs and a like plurality of data outputs with the data outputs of each stage except the last being connected in one-to-one correspondence to the data inputs of the next stage, and wherein each stage comprises a plurality of the said data transposition circuits each connected between a respective pair of the data inputs and a respective pair of the data outputs for that stage, the commutator circuit further comprising means associated with each stage for deriving from the synchronizing signals a control signal for the selector switches of that stage.
Preferably, in at least one stage each data transposition circuit includes a first delay element connected between one of the data inputs and the two selector switches, and a second delay element connected to the output of one of the selector switches.
Preferably, a synchronizing signal is supplied to the first stage each time a fresh set of data is present at the data inputs of the first stage, wherein the synchronizing signal is passed from each stage to the next via a further delay element, and wherein each stage includes a counter which counts the synchronizing signals and provides a control signal for the selector switches of that stage according to the state of the counter.
Preferably, the commutator circuit further includes means for re-mapping the data outputs of each stage to the data inputs of the next stage.
The invention further provides an FFT processor including at least one commutator circuit as claimed in any preceding Claim.
For the purposes of this specification a 2-to-1 selector switch is any device, such as the 2-to-1 multiplexers mentioned herein, which permits either one of two data inputs to be selectively connected to a single data output as determined by an applied control signal.
REFERENCES:
patent: 3644027 (1972-02-01), Bennett
patent: 3899667 (1975-08-01), Simone
patent: 4127805 (1978-11-01), Lukashov et al.
patent: 4366738 (1983-01-01), Howell
patent: 4928068 (1990-05-01), Main
patent: 5347548 (1994-09-01), Messerges et al.
patent: 5497263 (1996-03-01), Masuda et al.
patent: 5517493 (1996-05-01), Uekama et al.
patent: 5724278 (1998-03-01), Ohgose et al.
patent: 5838817 (1998-11-01), Funada
Ding Tiong Jiu
Hu Yi
McCanny John Vincent
Harrington Curtis L.
Integrated Silicon Systems Limited
Lee Thomas C.
Mai Rijue
LandOfFree
Commutator circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Commutator circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Commutator circuit will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2501744