Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-12-14
2001-04-24
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S603000, C708S493000
Reexamination Certificate
active
06223195
ABSTRACT:
TECHNICAL FIELD
The present invention relates to an arithmetic unit of a computer system, and in particular, to a discrete cosine high-speed arithmetic unit suitable for achieving calculation of a sum of products using a plurality of constant function values and compressing and decompressing data at a high speed. Moreover, the present invention relates to a high-speed Hartley transform arithmetic unit suitable for calculating a sum of products using a plurality of constant function values and thereby executing the Hartley transform processing, which is related to a Fourier transform, at a high speed. Additionally, the present invention relates to image processing, and in particular, to a Hough transform circuit to achieve a Hough transform in which straight line components of an image are detected, the circuit being suitable for calculating a sum of products using a plurality of constant function values and executing the Hough transform processing at a high speed.
BACKGROUND ART
In voice and image processing, there has been widely employed a discrete Fourier transform (DFT) and its variations such as a discrete cosine transform and a discrete Hartley transform. In these transform processes, a plurality of trigonometric functions are utilized to primarily calculate sums of products between the trigonometric functions and data items. In general, the calculation cost of multiplication is higher than that of addition and subtraction. Consequently, there have been devised several high-speed calculation algorithms in which the number of multiplications are advantageously reduced using relationships between trigonometric functions, e.g., the formula of double angle and the formula of half-angle. These algorithms have been briefly described in pages 115 to 142 of the “Nikkei Electronics” No. 511 published on October 15, 1990. In practice, the trigonometric functions are stored as constants in a memory. Particularly, due to the relatively small number of figures of the values, there has been also adopted a method in which the results of products between data items and trigonometric functions are stored in a memory. In addition, it is possible to utilize a known method in which each trigonometric function value is calculated in a CORDIC method using the principle of rotation of coordinates and/or a formula of approximate expression of function.
In image processing, the Hough transform is often employed because the transform is advantageously applicable even when the data contains noises due to the detection of straight lines in the image. When the coordinates of an arbitrary pixel are expressed as (x,y), the Hough transform is defined as
R=x
cos &thgr;+
y
sin &thgr;=
x
cos &thgr;+
y
cos(&pgr;/2−&thgr;).
FIG. 23
shows the geometric relationship of the transform. R stands for the length of a perpendicular drawn from the origin of the coordinate system to a straight line passing the pixel (x,y). Letter &thgr; denotes the angle between the perpendicular and the positive direction of the x axis. In an actual application, for an arbitrary pixel, the angle &thgr; takes a plurality of discrete values ranging from 0 to &pgr; such that R of expression (1) is calculated for each value of &thgr;. R is also discretized and its frequency of occurrence is attained in the form of voting for all pixels so that (R, &thgr;) having the highest number of votes obtained is detected as a straight line component.
A plurality of trigonometric functions are stored as constants in a memory for use in calculation later. Or, in the conventional method in which the value of each trigonometric function is directly calculated using, e.g., the CORDIC method, even when the number of multiplications is reduced by a clever algorithm, a considerable amount of multiplications are still necessary. Furthermore, it is not practical to provide a multiplier for each of the multiplications, namely, the multiplier is to be sequentially used. This is cause of hindrance to the high-speed operation. Additionally, since an arbitrary input is assumed in a multiplier, even when a value at a digit place of binary input data is zero, a partial product is uselessly calculated for the digit place. When there is used the method in which all of the results of products between data items and trigonometric function values are stored in the memory, although the arithmetic unit can be easily designed, the memory capacity is increased and hence the chip size becomes larger.
Moreover, to count the votes for the discrete (R, &thgr;), there is required a large volume of memory.
DISCLOSURE OF INVENTION
It is therefore an object of the present invention to provide a discrete cosine high-speed arithmetic unit, a high-speed Hartley transform arithmetic unit, and a high-speed Hough transform circuit in which considering that each trigonometric function value is constant, to possibly minimize the number of non-zero coefficients in the binary value obtained by expanding the trigonometric function value, the value is beforehand recoded into a redundant binary representation of {−1,0,+1}. The resultant values are shifted such that a pair of non-zero coefficients is optimally grouped. For each digit position, associated data pairs are subjected to addition or subtraction according to the signs of the coefficients. Moreover, the resultant values are shifted to be aligned to a fixed position and are then inputted to a group of adders to thereby obtain partial products therebetween, thereby attaining the sum of the partial products. In consequence, the arithmetic units and circuit above are efficiently configured in a compact structure to operate at a high speed.
Since the number of non-zero coefficients is reduced in the constant and the pair of non-zero coefficient values are grouped for each digit position to commonly effect the addition in an optimal manner, the number of adders is decreased and the number of stages of gates is also minimized.
REFERENCES:
patent: 4791598 (1988-12-01), Liou et al.
patent: 5249146 (1993-09-01), Uramoto et al.
patent: 5357453 (1994-10-01), Kim et al.
patent: 5477469 (1995-12-01), Motomura
patent: 5598361 (1997-01-01), Nagamatsu et al.
patent: 5737256 (1998-04-01), Nakagawa et al.
patent: 60-218168 (1985-10-01), None
patent: 2-125366 (1990-05-01), None
patent: 3-35353 (1991-02-01), None
patent: 5-20457 (1993-01-01), None
patent: 5-268481 (1993-10-01), None
Potkonjak et al., “Efficient Substitution of Multiple Constant Multiplications by Shifts and Additions Using Iterative Pairwise Matching”, 31stDesign Automation Conference, San Diego, CA, Proceedings 1994, Jun. 6-10, 1994, pp. 189-194.
Japanese Journal, “Nikkei Electronics”, No. 511, Oct. 15, 1990, pp. 115-142.
Technical Report of The Institute of Electronics, Information and Communication Engineers, Sep. 1994, pp. 39-46.
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E78-A, No. 8, Aug. 1995, pp. 957-962.
Transactions of Information Processing Society of Japan, vol. 31, No. 8 (Tokyo), Oct. 15, 1993, pp. 1242-1250.
Antonelli Terry Stout & Kraus LLP
Hitachi , Ltd.
Mai Tan V.
LandOfFree
Discrete cosine high-speed arithmetic unit and related... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Discrete cosine high-speed arithmetic unit and related..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrete cosine high-speed arithmetic unit and related... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2487890