Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-04-06
2002-08-20
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06438568
ABSTRACT:
The invention relates to a device for converting series of input data elements to series of output data elements, the device being provided with a memory means for containing the series of input and output data elements.
Such a device is known from paragraph 10.10 in the book entitled “Theory and application of digital signal processing” by the authors Lawrence R. Rabiner and Bernard Gold. In digital signal processing the discrete Fourier transform (DFT) plays an important part. By means of this transform, a description of a signal in the time domain can be converted to a description of the same signal in the frequency domain. This has the advantage that subsequently specific signal processing operations, which can only be performed in a very complex manner in the time domain, can be performed in a relatively simple manner.
Since performing a DFT requires very many arithmetical processes, through the years many devices have been designed by means of which a DFT can be calculated rapidly and efficiently. Often these devices are provided with a number of so-called butterflies, which are capable of rapidly performing specific sub-processes necessary for the DFT. In such a butterfly, a number of input data elements are converted to an equally large number of output data elements by doing additions and multiplications, said multiplications being performed by means of a multiplying factor. These multiplication factors are alternatively referred to as twiddle factors or W
N
k
.
The device mentioned in said book is provided with a RAM-memory, a butterfly and a permutation network. The RAM-memory is embodied so that each memory word can contain a series of data elements, the number of data elements in the series being equal to the number of data elements which can be converted by the butterfly. If, for example, in the known device a radix-4 butterfly is employed, that is a butterfly capable of converting four input data elements to four output data elements, then the RAM-memory is organized so that each memory word can contain a series of four data elements.
From the RAM-memory, a series of all necessary input data elements is supplied to the butterfly by reading a memory word. In the butterfly, these input data elements are converted to output data elements. The multiplication factors necessary for this purpose are read from a ROM-memory. Subsequently, in the permutation network, these output data elements and other output data elements computed by the butterfly are distributed over a number of series of output data elements. These series of output data elements are finally written in the RAM-memory and can be used at a later stage as series of input data elements. By repeatedly performing a radix-B butterfly, in which the output data elements of the butterfly serve in a different order as input data elements for the butterfly, an N-point DFT can be calculated, B being smaller than N. In this manner, for example, a 32-point DFT can be calculated by means of a radix-4 butterfly.
The known device is relatively slow.
It is an object of the invention to provide a device of the type mentioned in the opening paragraph, which is capable of performing the operation of converting the series of input data elements to series of output data elements more rapidly.
To achieve this, the device in accordance with the invention is characterized in that the memory means is embodied so as to read a series of input data elements and write a series of output data elements during a single clock cycle. During the calculation of an N-point DFT, frequently series of input data elements must be read from the memory means and series of output data elements must be written in the memory means. Generally, this takes up one clock cycle for each read or write operation. By embodying the memory means so that during a single clock cycle both a series of input data elements can be read and a series of output data elements can be written, for example by providing the memory means with a so-called read-modify-write function, the access to the memory means is accelerated. This has the additional advantage that the device consumes less energy.
An embodiment of the device in accordance with the invention is characterized in that an order in which the series of input data elements are converted to series of output data elements is selected so that multiplication factors required in the butterfly remain constant for as long as possible. If these multiplication factors are stored in a memory, it is achieved by means of this measure that the device has to read a multiplication factor from the memory only a minimum number of times. If, however, the multiplication factors have to be computed by the device, it is achieved by this measure that the device has to compute a multiplication factor only a minimum number of times. In either case, this may lead to a reduced energy consumption by the device and an increase of the speed with which the device converts input data elements to output data elements.
A further embodiment of the device in accordance with the invention is characterized in that the device comprises at least a Viterbi butterfly. The way in which a DFT is computed has many similarities to the way in which a so-called Viterbi decoding algorithm is computed. By using at least one Viterbi butterfly, the device in accordance with the invention can also suitably be used to realize a Viterbi decoder.
Another embodiment of the device in accordance with the invention is characterized in that an order in which the series of input data elements are converted to series of output data elements is chosen so that writing a series of output data elements after reading a necessary series of input data elements occurs as much as possible. By choosing the order in which the series of input data elements are converted to series of output data elements to be such that reading a series of input data elements and writing a series of output data elements during a single clock cycle occurs as much as possible, it is achieved that the memory means must be accessed a minimum number of times. This measure too can lead to a reduction of the energy consumption by the device and an increase of the speed with which the device converts input data elements to output data elements.
These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.
REFERENCES:
patent: 4393457 (1983-07-01), New
patent: 4491910 (1985-01-01), Caudel et al.
patent: 4689762 (1987-08-01), Thibodeau, Jr.
patent: 5546569 (1996-08-01), Proebsting et al.
patent: 5845093 (1998-12-01), Fleming
patent: 5890098 (1999-03-01), Kozaki et al.
patent: 6058409 (2000-05-01), Kozaki et al.
“Theory and Application of Digital Signal Processing”, by Lawerence R. Rabiner and Bernard Gold. paragraph 10.10.
Bekooij Marco J. G.
Gruijters Paulus W. F.
Biren Steven R.
Koninklijke Philips Electronics , N.V.
Malzahn David H.
LandOfFree
Method and apparatus for optimizing conversion of input data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for optimizing conversion of input data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for optimizing conversion of input data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2920191