Multiplex communications – Communication techniques for information carried in plural... – Combining or distributing information via time channels
Reexamination Certificate
1998-04-07
2002-10-08
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Communication techniques for information carried in plural...
Combining or distributing information via time channels
C370S537000, C708S316000
Reexamination Certificate
active
06463081
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a Very Large Scale Integration (VLSI) hardware structure. and more particular to a method and an apparatus for fast rotation, in which each rotation is performed by using only few shift-addition operation.
2. Description of the Related Art
Conventionally, the basic arithmetic of Digital Signal Processing (DSP) is a summation of multiplication performed by a multiplier. The arithmetic is called “multiplication-accumulation arithmetic”. The disadvantages of this arithmetic are: 1) a large word width of resultant data is needed to guarantee the accuracy because of numerical sensitivity: and 2) a problem in system stability or robustness is caused, so that more digits are reserved for calculation. The consequence of the above two disadvantages are that the additional consumption of hardware for internal bus and storage.
Orthogonal Transform (OT) is an important content of DSP and has been broadly applied in data compression and analysis. It has been proved in mathematics that a very good robustness is obtained by employing Givens rotation sequence to perform OT. Givens rotation is a unit matrix based on planar rotation. Assuming that G
n
(k, l, &thgr;) is a Givens rotation, and
G
n
(
k
,
l
,
θ
)
=
[
I
k
-
1
cos
θ
-
sin
θ
I
l
-
k
-
1
sin
θ
cos
θ
I
n
-
1
]
&LeftBracketingBar;
θ
&RightBracketingBar;
≤
π
wherein (k, l) represents rotation for kth and lth columns and rows. The rotation is an orthogonal matrix, so that value of the rotation matrix or the vector is kept constant before and after rotation.
To perform the above Givens rotation, Cordic algorithm is conventionally adopted. In Cordic algorithm, simple “right shift-addition & subtraction” calculation is used for planar rotation with infinitesimal angle. Through reiteratively calculation such as multiplication, division, trigonometry, and hyperbolic functions, Cordic algorithm has been broadly applied in palmar calculators. However, since Cordic algorithm is much more complex than “multiplication-accumulation arithmetic”, this kind of rotation arithmetic cannot be performed in OT for further application.
To solve the above problem, A. Lightenberg, et. al. have developed an image processing chip in which Givens rotator is adapted to perform a two-dimensional 8×8 discrete cosine transform (DCT). Yet, four multipliers are used to calculation the rotation.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a method and an apparatus for fast rotation for fast realization of Givens rotation. A fast rotator is developed in which each rotation with an arbitrary angle is performed by only one or few times of “shift-addition”. The fast rotator can be cascaded in pipelines for high throughput. This fast rotator can be used as the arithmetic core for the new VLSI-DSP to perform various OT by Givens rotation sequences. Therefore, a very good robustness is obtained, and furthermore, the computing complexity for the fast rotator is comparable to the conventional “multiplication-accumulation arithmetic”. By employing the fast rotator according to the invention as a computing kernel in digital image processing, especially in high definition television (HDTV) images and high resolution medical X-ray images, the total amount of image data can be transformed and reduced to an acceptable amount.
To achieve these objects and advantages, and in accordance with the purpose of to the invention, as embodied and broadly described herein, the invention is directed towards an apparatus of fast rotation, including, a plurality of pipelines. Each of the pipelines comprises: a plurality of multiplexes, for data filtering and selecting; a plurality of shifters, to perform fast rotation of data selected by the multiplexes; and a plurality of adders/subtractors, to complete computation after the fast rotation and to obtain a resultant data.
To achieve these objects and advantages, and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention is directed toward a method of fast rotation. A pipeline comprising a plurality of multiplexes, a plurality of shifters, to perform fast rotation of data selected by the multiplexes, and a plurality of adders/subtractors is provided. A plurality sets of data is input to be filtered and selected by the multiplexes. Fast rotation is performed to the data selected by the multiplexes. A final computation is performed a set of resultant data is output through the adder/subtractors.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.
REFERENCES:
patent: 5214654 (1993-05-01), Oosawa
patent: 5226125 (1993-07-01), Balmer et al.
patent: 5239654 (1993-08-01), Ing-Simmons et al.
patent: 5355462 (1994-10-01), Rousseau et al.
patent: 5712999 (1998-01-01), Guttag et al.
A. Ligtenberg et al., “A Single Chip Solution for an 8 by 8 Two Dimensional DCT”, IEEE 1987, pp. 1128-1131.
Chen Hongyi
Zeng Zhiqiang
Hsu Alpus H.
J.C. Patents
Nguyen Toan
United Microelectronics Corp.
LandOfFree
Method and apparatus for fast rotation 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 fast rotation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for fast rotation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2928118