• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    A fast Hadamard transform device is provided which prevent from increasing of circuit scale and shorten a developing TAT even if the number of bits to be operated. The device includes n of shift register units and n/2 of butterfly computation units. Input data are entered to the shift register units in response to a signal and data stored in the shift register units are supplied as quantized data by providing a signal for each “log2n*(p+log2n)” clocks.
    公开号:US20010007110A1
    申请号:US09/745,649
    申请日:2000-12-22
    公开日:2001-07-05
    发明作者:Takashi Shoji
    申请人:NEC Corp；
    IPC主号:H04B1-7093
    专利说明:
    [0001] 1. Field of the Invention [0001]
    [0002] 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. [0002]
    [0003] 2. Description of the Related Art [0003]
    [0004] 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. [0004]
    [0005] 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”. [0005]
    [0006] 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. [0006]
    [0007] 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[0007] 2n) bits adders while the subtraction is performed by using n/2 of (p−1+log2n) 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.
    [0008] 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”. [0008]
    [0009] 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. [0009]
    [0010] 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[0010] 2n), but also each of latches should include a bit number of register stages which is equal to (p−1+log2n).
    [0011] 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. [0011] SUMMARY OF THE INVENTION
    [0012] 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. [0012]
    [0013] 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. [0013]
    [0014] 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[0014] 2n) signals from one of the butterfly computation units at the predetermined output timing, and operates as (p+log2n) steps of shift registers in response to entering the input data and signals from one of the butterfly computation units at the other timing.
    [0015] 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. [0015]
    [0016] 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[0016] 2n*(p+log2n)) shift timings.
    [0017] 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. [0017] BRIEF DESCRIPTION OF THE DRAWINGS
    [0018] FIG. 1 shows a block diagram of a conventional fast Hadamard transform device; [0018]
    [0019] FIG. 2 shows a timing chart representing operation timings of the conventional fast Hadamard transform device; [0019]
    [0020] FIG. 3 shows a block diagram of a fast Hadamard transform device according to an embodiment of the invention; [0020]
    [0021] FIG. 4 shows a diagram representing a main part of a shift register unit of the fast Hadamard transform device of the invention; [0021]
    [0022] FIG. 5 shows a diagram representing a main part of a butterfly computation unit of the fast Hadamard transform device of the invention; [0022]
    [0023] FIG. 6 shows a diagram representing a combination of patterns of logic level of adders in the fast Hadamard transform device of the invention; [0023]
    [0024] FIG. 7 shows a diagram representing a combination of patterns of logic level of subtractors in the fast Hadamard transform device of the invention; and [0024]
    [0025] FIG. 8 shows a diagram representing transition of operation timing of the fast Hadamard transform device of the invention. [0025] DESCRIPTION OF THE PREFERRED EMBODIMENT
    [0026] At first, illustration is made about the above-described conventional fast Hadamard transform device with reference to FIGS. 1 and 2. [0026]
    [0027] In FIG. 1, the conventional fast Hadamard transform device can carry out the n-th order of the Hadamard transform. Herein, it is assumed that the illustrated device carries out an eighth order of the Hadamard transform, that is, n is equal to eight and the number of quantization bits is equal to p. The device receives eight elements (or dimension) of input vector X in a bit serial manner and each of the elements x[0027] 1-x8 of the vector X is successively latched by each of a first input latch 10 1 through an eighth input latch 10 8 in the illustrated manner.
    [0028] Each of output terminals of the first input latch [0028] 10 1 through the eighth input latch 10 8 can be put into a high impedance state in response to an input latch output enable signal (not shown). Both the output terminals of the first input latch 10 1 and the second latch 10 2 are connected to an adder 11 1 and a subtractor 12 1. Herein, adders and subtractors concerned with the conventional fast Hadamard transform device can carry out addition and subtraction in response to the (p−1+log2n) of bits, and therefore each of the adders may be denoted as (p− 1+log2n) adder and each of the subtractors may be denoted as (p−1+ log2n) subtractor.
    [0029] Similarly, both the output terminals of the third input latch [0029] 10 3 and the fourth latch 10 4 are connected to an adder 11 2 and a subtractor 12 2. Both the output terminals of the fifth input latch 10 5 and the sixth latch 10 6 are connected to an adder 11 3 and a subtractor 12 3. Both the output terminals of the seventh input latch 10 7 and the eighth latch 10 8 are connected to an adder 11 4 and a subtractor 12 4.
    [0030] An output terminal of the adder [0030] 11 1 is connected to a first output latch 13 1 and a first latch 14 1 with no selector. An output terminal of the subtractor 12 1 is connected to a fifth output latch 13 5 and a first latch 15 1 with selector. An output terminal of the adder 11 2 is connected to a second output latch 13 2 and a second latch 15 2 with selector. An output terminal of the subtractor 12 2 is connected to a sixth output latch 13 6 and a third latch 15 3 with selector.
    [0031] An output terminal of the adder [0031] 11 3 is connected to a third output latch 13 3 and a fourth latch 15 4 with selector. An output terminal of the subtractor 12 3 is connected to a seventh output latch 13 7 and a fifth latch 15 5 with selector. An output terminal of the adder 11 4 is connected to a fourth output latch 13 4 and a sixth latch 15 6 with selector. An output terminal of the subtractor 12 4 is connected to an eighth output latch 13 8 and a second latch 14 2 with no selector.
    [0032] A butterfly computation unit is configured by a pair of an adder and a subtractor (such as the adder [0032] 11 1 and the subtractor 12 1), both of which are given the same inputs.
    [0033] The first latch [0033] 14 1 with no selector and the second latch 14 2 with no selector latch an output of an adder or a subtractor in response to a selector latch signal (not shown). Also, an output terminal of the first latch 14 1 with no selector and an output terminal of the second latch 14 2 with no selector are connected to an output terminal of the first input latch 10 1 and an output terminal of the eighth input latch 10 8, respectively. Both of them are kept at high impedance states in response to entire latch output enable signals (not shown) which are delivered to all of the latches with and without selectors, as will become clear later.
    [0034] The first latch with selector [0034] 15 1 through the sixth latch with selector 15 6 latch an output of an adder or a subtractor in response to a selector latch signal (not shown). Each of the first latch 15 1 with selector through the sixth latch 15 6 with selector has two output terminals A and B, and outputs latched data from one of the terminals according to a “latch with selector” switch signal (not shown). The “latch with selector” switch signal serves to selectively switch only the firth through the sixth latches with selector, with the first and the second latches 14 1 and 14 2 kept intact, and therefore will be referred to as a selective switch signal. Also, these terminals are connected to one of output terminals of the second input latch 10 2 through the seventh input latch 10 7 and are kept at high impedance states by the above-mentioned entire latch output enable signal.
    [0035] The first output latch [0035] 13 1 through the eighth output latch 13 8 latch output of the corresponding adder or the corresponding subtractor in according to an output latch signal (not shown) and outputs elements y1-y8 of the output vector Y.
    [0036] Next, operation of the device illustrated in FIG. 1 will be described with reference to FIG. 2. At timing t[0036] 1, each of the first input latch 10 1 through the eighth input latch 10 8 latches each of the corresponding elements ((a) in FIG. 2) of the eight elements of the input vector X by an input latch clock ((b) in FIG. 2). At this point, the input-latch output enable signal is turned to a low level signal “L” ((c) in FIG. 2) and the entire latch output enable signal is turned to a high level signal “H” ((e) in FIG. 2) and is sent to all of the latches 14 1, 14 2, 15 1 to 15 6 to put them into the high impedance states. Under the circumstances, latch signals which are latched in all the input latches are supplied to the adders 11 1-11 4 or the subtractors 12 1-12 4, with all of the latches 14 1, 14 2, 15 1 to 15 8 kept in the high impedance states. In this event, output terminals A of the first through the sixth latches 15 1-15 6 with selectors are selected by the selective switch signal ((d) in FIG. 2). At this time instant t1, the adders and subtractors generate and feed, back to the latches, output signals w1 to w8 given by:
    [0037] Next, at timing t[0037] 2, the feedback signal w1(t1) is stored to the first latch 14 1 with no selector and w8(t1) is stored to the second latch 14 2 with no selector in response to a selector latch signal ((f) in FIG. 2). Further, the remaining feedback signals w2(t1), w3(t1), w4(t1), w5(t1), w6(t1), and w7(t1) are stored to the first latch 15 1 with selector, the second latch 15 2 with selector, the third latch 15 3 with selector, the fourth latch 15 4 with selector, the fifth latch 15 5 with selector, and the sixth latch 15 6 with selector, respectively ((f) in FIG. 2). At this time point t2, the input-latch output enable signal is turned back to the high level signal “H” ((c) in FIG. 2) while the entire latch output enable signal is turned to the low level signal “L” ((e) in FIG. 2). Under the circumstances, latch signals which are latched by the latches 14 1, 14 2, and 15 1-15 6 are supplied to the adders 11 1-11 4 or the subtractors 12 1-12 4. As a result, the adders and subtractors produce, at the time point t2, output signals represented by:
    [0038] Next, at timing t[0038] 3, the feedback signal w1(t2) is stored to the first latch 14 1 with no selector and w8(t2) is stored to the second latch 14 2 with no selector in response to the selector latch signal ((g) in FIG. 2). Further, the feedback signals w2(t2), w3(t2), w4(t2), w5(t2), w6(t2), and w7(t2) are stored to the first latch 15 1 with selector, the second latch 15 2 with selector, the third latch 15 3 with selector, the fourth latch 15 4 with selector, the fifth latch 15 5 with selector, and the sixth latch 15 6 with selector, respectively ((g) in FIG. 2). After the timing t2, output terminals B of the latches 15 1-15 6 are selected by the selective switch signal ((d) in FIG. 2), and each of feedback signals of the adders and subtractors is given by:
    [0039] After that, by the output latch clock which is coincident with an input latch clock at the next timing t[0039] 1, the feedback signals w1(t3)−w8(t3) are latched by the corresponding output latches 13 1-13 8, and elements y1-y8 of output data Y are given by:
    [0040] The illustrated conventional fast Hadamard transform device has shortcomings as mentioned in the preamble of the instant specification. [0040]
    [0041] Next, description is made about a fast Hadamard transform device according to an embodiment of the invention. [0041]
    [0042] In FIG. 3, the fast Hadamard transform device of the invention includes shift register units [0042] 20 1-20 n, n in number, and butterfly computation units 21 1-21 n/2, n/2 in number, to perform n-th order fast Hadamard transform of p of quantization bits.
    [0043] Each of shift register units [0043] 20 1-20 n includes two input terminals DIN and LIN, and two output terminals DOUT and LOUT. To the DIN, n elements of input data V1-Vn are supplied, and from the DOUT, n elements of output data W1-Wn are supplied. The input data V1−Vn which are supplied to the DIN are then supplied to the butterfly computation unit as serial data bit by bit. The bit computed by the butterfly computation unit is supplied to the LIN.
    [0044] Each of the shift register units [0044] 20 1-20 n shares an input latch and an output latch by preparing a selector and inputs the input data V1-Vn from DIN at a predetermined input timing. The input data are then transformed to serial data at the shift register unit and addition or subtraction is performed on the serial data by the butterfly computation unit bit by bit. Consequently, the result from the operation is supplied from the DOUT at predetermined output timing as output data W1-Wn.
    [0045] The butterfly computation unit includes two input terminals ADDIN and SUBIN, and two output terminals ADDOUT and SUBOUT. The unit performs butterfly computation on the input data from the LOUT of the shift register unit and supplies the result to the LIN of the shift register unit. [0045]
    [0046] Next, description is made about main parts of the fast Hadamard transform device of the invention. Herein, it is assumed that the number of quantized bits is four and order is eight. In this connection, the illustrated fast Hadamard transform device includes shift register units [0046] 20 1-20 8 and butterfly computation units 21 1-21 4.
    [0047] Herein, it is to be noted that all the shift register units [0047] 20 1-20 8 have the same configuration. Each of Input signals V1-V8 is supplied to the corresponding DIN of the shift register units 20 1-20 8 and each of output signals W1-W8 is supplied from the corresponding DOUT of the shift register units 20 1-20 8.
    [0048] The LOUT of the shift register unit [0048] 20 2q−1 (1≦q≦4, q is a natural number) is connected to the ADDIN of the butterfly computation unit 21 q. Also, the LOUT of the shift register unit 20 2q is connected to the SUBIN of the butterfly computation unit 21 q.
    [0049] The ADDOUT of the butterfly computation unit [0049] 21 r (1≦r≦4, r is a natural number) is connected to the LIN of the shift register unit 20 r. Also, SUBOUT of the butterfly computation unit 21 r is connected to the LIN of the shift register unit 20 r+4.
    [0050] The shift register unit [0050] 20 shown in FIG. 4 includes m of 1 bit flip flop circuits 30 1-30 m, m of input switches 31 1-31 m, and m of output switches 32 1-32 m. Herein, it is assumed that m is “p+log2n”.
    [0051] Each of the flip flop circuits [0051] 301-30 m latches an input signal of a D terminal at a predetermined latch clock and outputs the signal from a Q terminal. Each of the input switches 31 1-31 m outputs an input signal entered from an IN terminal to an O1 terminal or an O2 terminal in according to a predetermined input switch signal. Each of the output switches 32 1-32 m inputs an input signal from an I1 terminal or an I2 terminal in according to a predetermined output switch signal and outputs the signal from an OUT terminal.
    [0052] A signal from LIN is supplied to an IN terminal of the input switch [0052] 31 1. From an O1 terminal of the input switch 31 1, a bit of DOUT is supplied. An O2 terminal of the input switch 31 1 is connected to an I2 terminal of the output switch 32 1. A most significant bit (MSB) of DIN is supplied to an I1 terminal of the output switch 32 1. An OUT terminal of the output switch 32 1 is connected to a D terminal of the flip flop circuit 30 1.
    [0053] To each of IN terminals of the input switches [0053] 31 2-31 7, the corresponding Q terminal of the flip flop circuits 30 1-30 6, which reside the former step of the input switches, is connected. Signal from each of O1 terminals of the input switches 31 2-31 7 are supplied as a bit of the DOUT. Each of O2 terminals of the input switches 31 2-31 7 is connected to the corresponding I2 terminal of the output switches 32 2-32 7. Each of bits from the next to the MSB to the least significant bit (LSB) of the DIN is entered to one of I1 terminals of the output switches 32 2-32 7 in order. OUT terminals of the output switches 32 2-32 7 are connected to the corresponding D terminal of the flip flop circuits 30 2-30 7. A Q terminal of the flip flop circuit 30 7 is supplied as LOUT.
    [0054] Such configuration of flip flop circuit keeps transform result bit by bit at each step of n-th order fast Hadamard transform. The input switch and the output switch controls flow of signals when the signals are supplied to the fast Hadamard transform device of the embodiment or when the signals are supplied as operation results. That is, each of the output switches [0054] 32 1-32 7 connects the I1 terminal to the OUT terminal by the input switch signal at the predetermined signal input timing, and supplies an input signal from the DIN to one of the flip flop circuits 30 1-30 7. Also, each of the input switches 31 1-31 7 connects the IN terminal to the O1 terminal by the output switch signal at the predetermined signal output timing, and supplies a result from the butterfly computation entered from the LIN as DOUT. In the other timing, each of the input switches 311-317 connects the IN terminal to the O2 terminal, each of the output switches 32 1-32 7 connects the I2 terminal to the OUT terminal, signals are shifted at the flip flop circuits 301-307 by a bit for each predetermined latch clock and consecutively supplied to the butterfly computation unit as LOUT.
    [0055] The butterfly computation unit [0055] 21 shown in FIG. 5 includes an adder 40 having a bit of carry input/output, a subtractor 41 having a bit of borrow input/output, a flip flop circuit 42 having a bit of reset, and a flip flop circuit 43 having a bit of set.
    [0056] A signal which is supplied from the shift register unit to an ADDIN is supplied to an ADD[0056] 0 terminal of the adder 40 and to an ADD0 terminal of the subtractor 41. Also, a signal which is supplied from the shift register unit to a SUBIN is supplied to an ADD1 terminal of the adder 40 and to an SUB0 terminal of the subtractor 41.
    [0057] As shown in FIG. 5, the adder [0057] 40 outputs to the OUT terminal a result from adding of a bit from the ADD0 terminal, a bit from the ADD1 terminal, and a carry bit from the CIN terminal, and outputs an output carry bit to the COUT terminal. The result of adding from the OUT terminal is supplied to the shift register unit as ADDOUT. The COUT terminal is connected to a D terminal of the flip flop circuit 4 2, and a Q terminal of the circuit 42 is connected to the CIN terminal of the adder 40.
    [0058] As shown in FIG. 7, the subtractor [0058] 41 subtracts using a bit from the ADD0 terminal, a bit from the SUB0 terminal, and a borrow bit from the BIN terminal and outputs the subtracting result to the OUT terminal. Further, the subtractor 41 outputs a borrow bit to the BOUT terminal. The subtracting result from the OUT terminal is supplied to the shift register unit as SUBOUT. The BOUT terminal is connected to a D terminal of the flip flop circuit 43, and a Q terminal of the flip flop circuit 43 is connected to the BIN terminal of the subtractor 41.
    [0059] The flip flop circuit [0059] 42 outputs “0” in response to a reset signal entered into an R terminal at an initial status, and performs, at a normal status, carry computation of a bit by delaying a carry bit by a clock of a latch clock and supplying the carry bit to the adder 40.
    [0060] The flip flop circuit [0060] 43 outputs “1” in response to a set signal entered into an S terminal at an initial status, and performs, at a normal status, borrow computation of a bit by delaying a borrow bit by a clock of a latch clock and supplying the borrow bit to the subtractor 41.
    [0061] Next, description is made about operations of the above fast Hadamard transform device with reference to FIG. 8. [0061]
    [0062] In FIG. 8, five lines (a) to (e) are shown. The top line (a) shows a timing of latch clock and the second line (b) shows an input timing of an input vector. The third line (c) shows an output timing of signals from the fast Hadamard transform device, and the forth line (d) shows a switching timing between an input switch and an output switch. The last line (e) shows a reset timing of the adder of the butterfly computation unit and a set timing of the subtractor of the butterfly computation unit. [0062]
    [0063] When eighth order fast Hadamard transform is performed on data series in which the number of quantized bits p is four, input signals [0063] 50 including eight elements of input vectors V0-V7 are entered to the DIN of the corresponding shift register unit of the fast Hadamard transform device of the invention at a timing shown in the line (b) in FIG. 8.
    [0064] Each of the input vectors V[0064] 0-V7 include bits b3, b2, b1, and b0 from the MSB side. The input signals 50 are then entered from LOUT of the corresponding shift register unit to the corresponding butterfly computation unit from the LSB side.
    [0065] Specifically, b[0065] 3 of the DIN is entered into an I1 terminal of the input switch 32 4, b2 of the DIN is entered into an I1 terminal of the input switch 32 5, b1 of the DIN is entered into an I1 terminal of the input switch 32 6, and b0 of the DIN is entered into an I1 terminal of the input switch 32 7.
    [0066] Seven input switches are prepared for seven bits, this is because that carry occurs by the butterfly computation unit, thus, when the signals are entered, zero is given to each high order three bits including MSB. Therefore, when the signals are entered, zero is set to the I[0066] 1 terminals of the input switches 32 1-32 3.
    [0067] In response to entering of the signals, at a timing as shown in FIG. 8, line (d), the input switch signal [0067] 51 is entered into the input switches 32 1-32 7. When the input switch signal 51 is low level “L”, in each of the input switches 32 1-32 7, the I1 terminal and the OUT terminal are connected, and an input signal supplied to the I1 terminal is entered to the D terminal of the corresponding one of the flip flop circuits 30 1-30 7. Also, the output switch signal is supposed to be entered to the output switches 31 1-31 7 at the same timing as the input switch signal 51, when the output signal is low level “L”, in each of the output switches 31 1-31 7, the IN terminal and the O1 terminal are connected, and an input signal supplied to the IN terminal is entered to the DOUT terminal.
    [0068] The signals of the DOUT terminal are supplied as output signals [0068] 52 of results from the fast Hadamard transform of the last cycle. Also, as shown in FIG. 8, line (e), the flip flop circuits 42 and 43 of the butterfly computation unit are initialized since the reset signal and the set signal are entered into the butterfly computation unit (clear 53).
    [0069] As described above, when the input switch signal is high level “H”, each of the shift register units [0069] 20 1-20 8 is composed of seven steps of shift register. While the input switch signal is “H”, since the output switch signal is also high level “H”, a bit of signal is supplied from the ADDOUT or the SUBOUT of the butterfly computation unit to the LIN, a result from the shift register unit is supplied from the LOUT to the ADDIN or the SUBIN of the butterfly computation unit bit by bit. And when shift is performed seven times, that is, an input signal is passed a round of the shift register unit, the first step of computation of the fast Hadamard transform which performs three (=log2n) steps is completed.
    [0070] That is, for signals which are stored in the flip flop circuits [0070] 30 1-30 7 of the shift register unit at a predetermined input timing, addition is performed about an LSB at the first clock. For example, as a result of the adding, result “V1+V2” is supplied from the ADDOUT of the butterfly computation unit 21 1. On the other hand, result “V1−V2” is supplied from the SUBOUT of the butterfly computation unit 21 1.
    [0071] Herein, for V[0071] 1 and V2 (each of which can be represented as b3−b1, (b7, b6, and b5 are zero)), “V1+V2” supplied from the ADDOUT is shown as follows.
    [0072] At first clock: V[0072] 1(b0)+V2(b0)
    [0073] At second clock: V[0073] 1(b1)+V2(b1)+(carry in adding b0)
    [0074] At third clock: V[0074] 1(b2)+V2(b2)+(carry in adding b1)
    [0075] At fourth clock: V[0075] 1(b1)+V2(b3)+(carry in adding b2)
    [0076] At fifth clock: V[0076] 1(b4)+V2(b4)+(carry in adding b3)
    [0077] At sixth clock: V[0077] 1(b5)+V2(b5)+(carry in adding b4)
    [0078] At seventh clock: V[0078] 1(b6)+V2(b6)+(carry in adding b5)
    [0079] It is assumed that operation results stored in the flip flop circuits [0079] 30 1-30 7 of the shift register unit at the seventh clock from the entering of the input signal are quantized data in which the bit stored in the flip flop 30 1 corresponds to the MSB and the bit stored in the flip flop 30 7 corresponds to the LSB, these feedback data w1(1)-w8(1) are shown as follows.
    [0080] Then, after the seventh clock from the entering of the input signal, as shown in FIG. 8, line (e), the reset signal and the set signal are entered into the butterfly computation unit, the adder and the subtractor of the butterfly computation unit are initialized. After that, the similar operation on the signal in the shift register unit is repeated bit by bit. As a result, in the next seven clocks (after the fourteenth clock from the entering of the input signal), the feedback data w[0080] 1(2)-w8(2) are changed as follows.
    [0081] Similarly, for each seven clocks, the reset signal and the set signal are entered into the butterfly computation unit and the unit is initialized. Therefore, when still the next seven clocks are passed, the feedback data w[0081] 1(3)-w8(3) are changed as follows.
    [0082] As mentioned above, parallel-serial transform is performed by the flip flop of the shift register, and addition/subtraction is performed in “log[0082] 2n*(p+log2n))” clocks. For example, if the number of quantized bits is four, and input vector has eight elements, eighth order Hadamard transform of the input vector can be completed in twenty one clocks. As shown in FIG. 8, line (d), for each twenty one clocks, switching between the input switches and the output switches is performed in response to the switch signal, quantized data stored in the flip flop circuit of the shift register are supplied as DOUT and next input vector is entered.
    [0083] Therefore, the fast Hadamard transform device of the invention includes n of shift register units each of which is the same configuration for each n elements of input data having quantized bit number p, and is composed of “p+log[0083] 2n” steps of one bit shift registers with switches capable of sharing the input latches and the output latches, and n/2 butterfly computation units each of which performs addition/subtraction bit by bit.
    [0084] Thereby, the number of latches is reduced to ⅓, scale of circuits can be reduced to 1/“3*the number of quantized bits”, although the conventional device requires a plurality of sets each of which includes a plurality of adders and subtractors, and a plurality of bits of latch register. [0084]
    [0085] Therefore, even if the number of bits to be operated is increased, increase of scale of circuits can be suppressed to the minimum. Also, it is possible to reduce the developing man-hour and developing TAT and to provide a suitable configuration of fast Hadamard transform device since each block which configures a part of the fast Hadamard transform device has the same configuration. [0085]
    [0086] Further, in the fast Hadamard transform device of the invention, higher speed operation can be performed since a circuit configuration of the device is sophisticatedly simplified and operation can be performed bit by bit. Thereby, the device can be operated at higher latch clock. [0086]
    权利要求:
    Claims (5)
    [1" id="US-20010007110-A1-CLM-00001] 1. A fast Hadamard transform device which transforms n elements of input data each of which is composed of p bits, comprising:
    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.
    [2" id="US-20010007110-A1-CLM-00002] 2. The fast Hadamard transform device of
    claim 1 , wherein each of the shift register units operates as output latches holding (p+log2n) signals from one of the butterfly computation units at the predetermined output timing, and operates as (p+log2n) steps of shift registers in response to entering the input data and signals from one of the butterfly computation units at the other timing.
    [3" id="US-20010007110-A1-CLM-00003] 3. The fast Hadamard transform device of
    claim 2 , wherein 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; and
    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.
    [4" id="US-20010007110-A1-CLM-00004] 4. The fast Hadamard transform device of
    claim 3 , wherein each of the carry bit and the borrow bit is stored in a delay circuit which is initialized every (log2n*(p+log2n)) shift timings.
    [5" id="US-20010007110-A1-CLM-00005] 5. The fast Hadamard transform device of
    claim 3 , wherein 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.
    类似技术:
    公开号 | 公开日 | 专利标题
    US6732130B2|2004-05-04|Fast hadamard transform device
    EP1078457B1|2002-03-20|Sequence generator
    US6009259A|1999-12-28|Emulation System
    US5761265A|1998-06-02|Parallel architecture for generating pseudo-random sequences
    US5689450A|1997-11-18|Parallel processor
    US4325129A|1982-04-13|Non-linear logic module for increasing complexity of bit sequences
    US6292926B1|2001-09-18|Functional module model, pipelined circuit synthesis and pipelined circuit device
    CA2238294C|2000-12-26|Pn sequence generator with bidirectional shift register and eulerian-graph feedback circuit
    US7028062B2|2006-04-11|FIR filter, method of operating the same, semiconductor integrated circuit including FIR filter, and communication system for transmitting data filtered by FIR filter
    US6240062B1|2001-05-29|Fast fourier transform calculating apparatus and fast fourier transform calculating method
    US7024606B2|2006-04-04|Method of generating test pattern for integrated circuit
    EP0656583A1|1995-06-07|Series parallel converter including pseudorandom noise generation
    KR100913467B1|2009-08-25|System And Method For Generating Parallel Cyclic Redundancy Codes
    Abbaszadeh et al.1988|VLSI implementation of a maximum-likelihood decoder for the Golay | code
    US6067331A|2000-05-23|System and method for binary correlation
    US5896308A|1999-04-20|Combinational logic circuit
    US6516333B1|2003-02-04|Sticky bit value predicting circuit
    WO2004044731A2|2004-05-27|Device and method for performing shift/rotate operations
    KR100307404B1|2001-09-26|Serial data combiner of channel card in radio port of the mobile communication system
    US6470369B1|2002-10-22|Euclid mutual division arithmetic circuit and processing circuit
    KR100292067B1|2001-07-12|Cell for discrete time cellular neural networks
    JPH06301711A|1994-10-28|High speed hadamard converter
    Bucholc1997|A circuit for high-speed time switching
    JPH07334345A|1995-12-22|Shifting device
    EP0105258A1|1984-04-18|Non-linear logic module for increasing complexity of bit sequences
    同族专利:
    公开号 | 公开日
    CN1302126A|2001-07-04|
    KR100354285B1|2002-09-28|
    BR0006539A|2001-07-24|
    JP3716695B2|2005-11-16|
    US6732130B2|2004-05-04|
    KR20010062661A|2001-07-07|
    JP2001184337A|2001-07-06|
    EP1111804A2|2001-06-27|
    EP1111804A3|2003-09-24|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US5561618A|1993-12-22|1996-10-01|Qualcomm Incorporated|Method and apparatus for performing a fast Hadamard transform|
    US5784293A|1994-11-03|1998-07-21|Motorola, Inc.|Apparatus and method for determining transmitted modulation symbols|
    US5726925A|1994-11-23|1998-03-10|Electronics And Telecommunications Research Institute|Hadamard transformer using memory cell|
    US6311202B1|1999-03-12|2001-10-30|Lucent Technologies Inc.|Hardware efficient fast hadamard transform engine|US20040034676A1|2002-08-15|2004-02-19|Comsys Communication & Signal Processing Ltd.|Reduced complexity fast hadamard transform and find-maximum mechanism associated therewith|
    US20070192396A1|2006-02-13|2007-08-16|Ronny Pedersen|Packed add-subtract operation in a microprocessor|
    KR100846485B1|2002-04-09|2008-07-17|삼성전자주식회사|Method and apparatus of hadamard transform|
    US20100027592A1|2008-07-29|2010-02-04|Agere Systems Inc.|Technique for searching for a preamble signal in a spread spectrum signal using a fast hadamard transform|JPS6214133B2|1980-08-14|1987-03-31|Matsushita Electric Ind Co Ltd||
    JPH05233681A|1992-02-21|1993-09-10|Sony Corp|Hadamard conversion circuit|
    JPH06301711A|1993-04-14|1994-10-28|Mitsubishi Electric Corp|High speed hadamard converter|CN1320478C|2001-08-21|2007-06-06|皇家菲利浦电子有限公司|Discrete conversion operational apparatus|
    KR100800897B1|2001-10-27|2008-02-04|삼성전자주식회사|Apparatus and method for performing fast hadamard transform|
    US7188132B2|2001-12-25|2007-03-06|Canon Kabushiki Kaisha|Hadamard transformation method and apparatus|
    CN1561595A|2002-06-21|2005-01-05|连宇通信有限公司|Method of spread spetrum of code channels for LS codes|
    JP3902990B2|2002-07-02|2007-04-11|キヤノン株式会社|Hadamard transform processing method and apparatus|
    US6996163B2|2003-03-27|2006-02-07|Arraycomm, Inc.|Walsh-Hadamard decoder|
    CN1937451B|2005-09-19|2010-05-12|中兴通讯股份有限公司|Quick Hadamard transform device|
    US20080288568A1|2007-05-14|2008-11-20|Hou Hsieh S|Low power Fast Hadamard transform|
    JP4933405B2|2007-11-13|2012-05-16|キヤノン株式会社|Data conversion apparatus and control method thereof|
    CN101894095B|2010-02-08|2015-08-12|北京韦加航通科技有限责任公司|Fast Hadama changer and method|
    CN101841711B|2010-04-17|2012-01-04|上海交通大学|Inverse quantization device for video decoding and implementation method thereof|
    CN105552755B|2012-06-25|2017-11-28|重庆欧荣莱汽车配件有限公司|Transformer radiator tube butterfly valve maintenance unit|
    US8842665B2|2012-08-17|2014-09-23|Lsi Corporation|Mixed radix fast hadamard transform for communication systems|
    法律状态:
    2000-12-22| AS| Assignment|Owner name: NEC CORPORATION, JAPAN Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:SHOJI, TAKASHI;REEL/FRAME:011397/0083 Effective date: 20001219 |
    2007-10-12| FPAY| Fee payment|Year of fee payment: 4 |
    2011-12-19| REMI| Maintenance fee reminder mailed|
    2012-05-04| LAPS| Lapse for failure to pay maintenance fees|
    2012-06-04| STCH| Information on status: patent discontinuation|Free format text: PATENT EXPIRED DUE TO NONPAYMENT OF MAINTENANCE FEES UNDER 37 CFR 1.362 |
    2012-06-26| FP| Expired due to failure to pay maintenance fee|Effective date: 20120504 |
    优先权:
    申请号 | 申请日 | 专利标题
    JP36585799A|JP3716695B2|1999-12-24|1999-12-24|Fast Hadamard transformer|
    JP11-365857||1999-12-24||
    JP365857/1999||1999-12-24||
    [返回顶部]