Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-04-06
2004-08-03
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06772183
ABSTRACT:
The invention relates to a device for converting series of a first number of input data elements to series of the first number of output data elements, said device being provided with a memory means for containing the series of input and output data elements, and said device further being provided with a converter for converting a second number of input data elements to the second number of 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 multiplying 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 multiplying 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 into 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 comprises a relatively large number of components, causing said device to be relatively intricate and expensive.
It is an object of the invention to provide a device of the type mentioned in the opening paragraph, which is relatively simple and cheap.
To achieve this, the device in accordance with the invention is characterized in that the device is also provided with at least one further converter, the converter and the further converter being arranged so as to be parallel to each other, and the first number being larger than the second number. By using, instead of a single radix-B converter, a plurality of parallel-arranged radix-A converters, A being smaller than B, a simpler and cheaper device is obtained. This can be attributed to the fact that the complexity and cost of a butterfly increase exponentially with the radix of the butterfly. For example, the complexity and cost of a radix-4 butterfly are higher than the complexity and cost of two radix-2 butterflies. In addition, if use is made of a plurality of parallel radix-A converters instead of a single radix-B converter, use can be made of a permutation network of a simpler construction.
An embodiment of 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.
A further 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 multiplying factors required in the butterflies remain constant for as long as possible. If these multiplying factors are stored in a memory, it is achieved by means of this measure that the device has to read a multiplying factor from the memory only a minimum number of times. If, however, the multiplying factors have to be computed by the device, it is achieved by this measure that the device has to compute a multiplying 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.
Another embodiment of the device in accordance with the invention is characterized in that the converters comprise Viterbi butterflies. 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 Viterbi butterflies, the device in accordance with the invention can also suitably be used to realize a Viterbi decoder.
A last 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: 3702393 (1972-11-01), Fuss
patent: 3871577 (1975-03-01), Avellar et al.
patent: 4298950 (1981-11-01), Smith, Jr.
patent: 4491910 (1985-01-01), Caudel et al.
patent: 4587626 (1986-05-01), Gray
patent: 4689762 (1987-08-01), Thibodeau, Jr.
patent: 4831574 (1989-05-01), Duhamel
patent: 4868776 (1989-09-01), Gray et al.
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.
patent: 0259231 (1988-03-01), None
“Theory and Application of Digital Signal Processing”,
Bekooij Marco J. G.
Gruijters Paulus W. F.
Koninklijke Philips Electronics , N.V.
Malzahn David H.
LandOfFree
Device for converting input data to output data using plural... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Device for converting input data to output data using plural..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Device for converting input data to output data using plural... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3278593