Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-12-22
2004-05-04
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S410000
Reexamination Certificate
active
06732130
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a fast hadamard transform device and, in particular, to the transform device which is adapted to perform quadrature modulation of spread signals in a CDMA (Code Division Multiple Access) mobile communication system.
2. Description of the Related Art
In a mobile communication system which employs a communication method, CDMA, which is focused as the next generation standard mobile communication method, mobile communication terminals in the system can simultaneously communicate among a plurality of channels by using the same frequency band. Furthermore, a spread spectrum communication method is used in the CDMA mobile communication system.
The spread spectrum communication method can be realized, for example, by a Walsh quadrature modulation technique which uses a Walsh code such that a correlation function becomes zero at every channel. Herein, it is to be noted that the Walsh code can be expressed by a Hadamard transform matrix which is composed of elements of “+1” and “−1”.
In the Walsh quadrature modulation, high speed or fast processing based on a butterfly computation can be achieved by carrying out Hadamard transform using the Hadamard transform matrix. A device which enables such high speed or fast Hadamard transform based on the butterfly computation may be called a fast Hadamard transform (FHT) device.
A conventional fast Hadamard transform device performs both addition and subtraction in the butterfly computation. Specifically, the addition is performed by using n/2 of (p−1+log
2
n) bits adders while the subtraction is performed by using n/2 of (p−1+log
2
n) bits subtractors. For brevity of description, it will be assumed that the number of quantization bits is represented by p and an n-th order Hadamard transform is carried out in the following. Especially, the description will be mainly made about an eighth-order fast Hadamard transform.
Now, a technology related to the conventional fast Hadamard transform device is disclosed in Japanese Laid Open Publication No. H06-301711 (namely, 301711/1994) “Fast Hadamard transform device”.
However, in the conventional fast Hadamard transform device, if the number of bits used for calculation is increased to k times, the device has to be enlarged in size to 3k times. This is because three latches, that is, an input latch, a latch with selector, and an output latch should be prepared for each bit in the conventional fast Hadamard transform.
Further, since addition and subtraction are carried out in parallel with each other in the butterfly computation, not only each of adders and subtractors should process the number of bits equal to (p−1+log
2
n), but also each of latches should include a bit number of register stages which is equal to (p−1+log
2
n).
It is not desirable to fabricate such a fast Hadamard transform device as a gate array since a cost of the fabrication is increased due to an increase of scale of the device. Also, a great deal of times and labor are required to develop and prove each block and to repetitively arrange wiring in the same block for integration. This is because such blocks have different functions from one another and are structured by different circuit elements, such as a latch with selector, a latch with no selector, and the like.
SUMMARY OF THE INVENTION
It is, therefore, an object of the invention to provide a fast Hadamard transform device which can be configured in a small scale and developed in a short time, that is, within short developing TAT (Turn Around Time), even if the number of bits to be processed is increased.
According to a first aspect of the invention, there is provided a fast Hadamard transform device which transforms n elements of input data each of which is composed of p bits. The device comprises n of shift register units each of which inputs the corresponding element of the input data at the predetermined input timing and outputs the bits in the input data serially, and n/2 of butterfly computation units each of which receives a bit from each two of the n shift register units and performs addition and subtraction on the two bits to supply each operation result to a determined shift register unit.
According to a second aspect of the invention, there is provided a fast Hadamard transform device of the first aspect of the invention, and in the device, each of the shift register units operates as output latches holding (p+log
2
n) signals from one of the butterfly computation units at the predetermined output timing, and operates as (p+log
2
n) steps of shift registers in response to entering the input data and signals from one of the butterfly computation units at the other timing.
According to a third aspect of the invention, there is provided a fast Hadamard transform device of the second aspect of the invention, and in the device, each of the butterfly computation units includes an adder which performs addition on two bits which are shifted from the different shift register units and a carry bit which is stored in the former addition, a subtractor which performs subtraction on two bits which are shifted from the different shift register units and a borrow bit which is stored in the former subtraction.
According to a fourth aspect of the invention, there is provided a fast Hadamard transform device of the third aspect of the invention, and in the device, each of the carry bit and the borrow bit is stored in a delay circuit which is initialized every (log
2
n*(p+log
2
n)) shift timings.
According to a first aspect of the invention, there is provided a fast Hadamard transform device of the fourth aspect of the invention, and in the device, serial output of the shift register unit corresponding to the 2q−1-th (1≦q≦4, q is a natural number) order is connected to an input to the adder of the q-th butterfly computation unit, serial output of the shift register unit corresponding to the 2q-th order is connected to an input to the subtractor of the q-th butterfly computation unit, an output from the adder of the r-th (1≦r≦4, r is a natural number) butterfly computation unit is connected to the serial input of the r-th shift register unit, and an output from the subtractor of the r-th butterfly computation unit is connected to the serial input of the r+4-th shift register unit.
REFERENCES:
patent: 4446530 (1984-05-01), Tsuboka
patent: 5561618 (1996-10-01), Dehesh
patent: 5726925 (1998-03-01), Hyun et al.
patent: 5784293 (1998-07-01), Lipa
patent: 6311202 (2001-10-01), Hahm
patent: 5-233681 (1993-09-01), None
patent: 6-301711 (1994-10-01), None
Bi et al., Electronics Letters, vol. 34, No. 21, pp. 2005-2006, 1998.
Dickstein Shapiro Morin & Oshinsky LLP.
NEC Corporation
Ngo Chuong Dinh
LandOfFree
Fast hadamard transform device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast hadamard transform device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast hadamard transform device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205706