Apparatus with selective fixed-coefficient filter for...

Details Apparatus with selective fixed-coefficient filter for... Apparatus with selective fixed-coefficient filter for...

1999-03-09

2002-01-29

Malzahn, David H. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06343304

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to an apparatus with a selective fixed-coefficient filter, and more particularly to an apparatus with a selective fixed-coefficient filter for recursively computing N points discrete cosine transforms (DCTs).
BACKGROUND OF THE INVENTION
The discrete cosine transforms (DCTs) are widely applied to processing and compression of video and audio signals and other fields related to spectral analyses and parameter estimations. Therefore, the development of a simple implementation of discrete cosine transform becomes very important. Recently, the recursive implementation of orthogonal transforms gains a lot of attentions since they are characterized in a simple structure and local communication. Goertzel first used the periodicity of finite trigonometric sequences to realize the discrete Fourier transform in a simple recursive structure. Goertzel's recursive structure not only reduces the number of computation, but also simplifies the complexity of implementation. After that, there are several recursive algorithms innovated to achieve regular implementation of DCTs, for example, the recursive algorithms for the DCT and inverse DCT with arbitrary length, the structures of recursive algorithms of normal and inverse DCT, the DCT with the power of two length in the recursive structures of several groups, a general discrete sinusoidal transform, and a two dimensional DCT/IDCT VLSI design characterized in formulation, regularization, and rank modulation.
U.S. Pat. No. 4,023,028 disclosed the operation and the recursive structure of fully digital recursive computation DFT. U.S. Pat. No. 4,058,715 indicated that the algebraic manipulation units for computing FFT are serially combined and each of them is a recursive computation structure. U.S. Pat. No. 4,080,661 disclosed the algebraic manipulation unit in a type of recursive without needing a multiplier. A common type of second order recursive digital filter is disclosed in U.S. Pat. No. 4,569,030. In U.S. Pat. No. 4,612,626, two FFT computations of real number sequence inputs are implemented with two recursive FFT structures. These recursive computation algorithms provide some advantages for VLSI implementation.
A fixed-coefficient recursive structure for computing the prime length DCT has been proposed. However, the most common length of DCTs is power of two. A fixed-coefficient recursive structure for realizing the time domain aliasing cancellation (TDAC) filtering processes has also been discussed.
As the discrete cosine transform with the recursive algorithms are obtained by the above-mentioned method, the filter coefficients vary along with the corresponding frequency-index components in the recursive structures. Each set of filter coefficients can only compute a specific transformed output. Accordingly, a variable-coefficient multiplier in a recursive IIR filter is required to obtain all desirable transformed results. Therefore, a variable-coefficient multiplier needs a generally typical multiplier with N deposited multiplicands for a transformation length of N. Besides, some filter coefficients can shift an IIR filter to a nearly unstable state, resulting in several inaccurately recursive results, particularly in finite-word-length machines. This problem can be solved by increasing the word length in a processor. However, to own a high-speed multiplier with a long word length is pretty expensive. Practically, the shortcoming of a recursive structure is that it requires a very high speed and accurate processing unit, such as IIR filter multiplier.
Therefore, it is tried by the applicant to deal with the situation encountered with the prior art.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a new category of fixed-coefficient recursive structures for computing discrete cosine transforms in power-of two length. By using number theorems, the fixed-coefficient recursive structures are developed from exploration of periodicity embedded in transform bases which form a complete residue system or a complete odd residue system. Based on permutation, sign change, and zero insertion of original inputs, the proposed filtering structures required fixed multipliers are better than the previous recursive methods which need general multipliers. In finite length machines, properly selected filter coefficients can avoid previous unstable state upon accessing and achieve low round-off errors in their transformations.
According to one aspect of the present invention, the apparatus with a selective fixed-coefficient filter for recursively computing N points discrete cosine transform (DCT) is provided. The apparatus includes a data manipulation unit for obtaining 2N new inputs through permutation, sign change, and zero insertion of original inputs for computing coefficient values of the N points discrete cosine transformn, and a second order filter electrically connected to the data manipulation unit for selecting a fixed-coefficient so as to perform the N points discrete cosine transform through 2N recursive operations based on the permuted 2N new inputs.
In a preferred embodiment, the N is a power of two.
In another preferred embodiment, the N points discrete cosine transform is a second type of discrete cosine transform (DCT-II).
Preferably, the second order filter has a fixed loop coefficient and a fixed output coefficient in accordance with the computation of the second type of discrete cosine transform.
Preferably, the fixed loop coefficient is 2 cos(q&pgr;/2N) and the fixed output coefficient is −cos(q&pgr;/4N).
Preferably, the q and the 2N are relatively prime and the q is a selected relatively larger positive integer but not greater than N−1.
Preferably, the data manipulation unit reads y[n] in sequence according to m, in which n and m satisfy q(2m+1)=(2n+1)(2k+1)mod 4N and a dummy zero data is appended to the y[n] which has a sign of (−1)
r4
if n is greater than N−1, where r
4
=┌(2n+1)(2k+1)/4N┐.
Preferably, the second type of discrete cosine transform is commonly called discrete cosine transform (DCT).
In a preferred embodiment, the N points discrete cosine transform is a third type of discrete cosine transform (DCT-III).
Preferably, the second order filter has a fixed loop coefficient and a fixed output coefficient in accordance with the computation of the third type of discrete cosine transform.
Preferably, the fixed loop coefficient is 2 cos(q&pgr;/2N) and the fixed output coefficient is cos(q&pgr;/2N).
Preferably, the q and the 2N are relatively prime and the q is a selected relatively larger positive integer but not greater than N−1.
Preferably, the data manipulation unit reads y[n] in sequence according to m in accordance with the computation of the third type of discrete cosine transform, in which n and m satisfy n(2k+1)mod 2N=qm mod 2N, and a dummy zero data is appended to the y[n] which has a sign of (−1)
r3
if n is greater than N−1, where r
3
=┌n(2k+1)/2N┐.
Preferably, the third type of discrete cosine transform is commonly called inverse discrete cosine transform (IDCT).
Preferably, the data manipulation unit includes an address generator based on a read only memory (ROM).
Preferably, the ROM contains computed data of n(2k+1)mod 2N=qm′ mod 2N and the mapping sequence and the sign change from n to m′ for completing an index mapping from m′ to n.
Preferably, the ROM contains computed data of (2n+1) (2k+1) mod 2N=q(2 m′+1)mod 2N and the mapping sequence and sign change from n to m′ for completing an index mapping from m′ to n.
Preferably, the data manipulation unit includes an address generator having a read only memory (ROM), an adder, a counter, a shifter, a comparator, and a first-in-first-out (FIFO) buffer.
In a preferred embodiment, the N points discrete cosine transform is a fourth type of discrete cosine trans

Affiliated with

Also associated with

Rating

Apparatus with selective fixed-coefficient filter for... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus with selective fixed-coefficient filter for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus with selective fixed-coefficient filter for... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2835166