JPH0148583B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to a multivalued Walsh transform device that converts a Walsh function system into a multivalued and complex function system. Conventionally, methods for orthogonally transforming signals include Fourier transform and Walsh transform. The commonly used Fourier transform is an orthogonal transform using a trigonometric function system, and its operation requires a multiplier. On the other hand, the Walsh transform is an orthogonal transform using a Walsh function system, and since the Walsh function system has only +1 and -1 elements, the Walsh transform has the advantage that calculations can be performed only by addition and subtraction, and it is used as an approximation of the Fourier transform. However, the drawback was that the approximation was rough. Next, this Walsh function will be explained. (1)
A matrix of 2 ⁱ rows and 2 ⁱ columns (called Hadamard matrix) defined by the formula H _i = H _i-1 H ₁ ...(1) where H ₁ = (1 1-1), and is the Kronecka product. means. As shown in Figure 1, each row of
Considering it as a waveform, 2 ⁱ waveforms can be generated from Hi. These waveforms are Walsh functions. The number of times the Walsh function crosses zero is called the number of alternations, and the 2 ⁱ Walsh functions generated from equation (1) have the number of alternations from 0 to 2 ⁱ -1. This Walsh function system constitutes a complete orthonormal function system, and just as Fourier transform is called frequency analysis, Walsh transform is called alternating number analysis. Further, the result of Fourier transform is called a Fourier spectrum, and the result of Walsh transform is called a Walsh spectrum. Furthermore, the fast Walsh transform (abbreviated as FWT), which calculates the Walsh transform at high speed, is known, and a method of expressing it in a matrix corresponding to the fast Fourier transform (abbreviated as FFT) was developed in December 1975. It is described in "Study on Fourier transform and Walsh transform" on pages 1134 to 1135 of IEICE Transactions Vol. 59-A, No. 12. If the column vector of the input time series arranged in reverse binary order is X, the transformation matrix is A, and the Fourier spectrum is F, then FFT is F=A・X=P _o・P _o-1・…P ₁・X … ...(2) and n times of matrices. Here each P _i
is determined from equations (3), (4), and (5). However, a _i =exp(−jπ/2 ⁱ ), I _i is a unit matrix with 2 ⁱ rows and 2 ⁱ columns, and diag(·) is a diagonal matrix with diagonal elements in parentheses. Here, reverse binary ordering means expressing natural numbers in binary, considering numbers with their digits reversed, and arranging them in the order of that number. In the case of n=3, X=(x ₀ , x ₄ , x ₂ ,
x ₆ , x ₁ , x ₅ , x ₃ , x ₇ ). Also, P _i is FFT
It expresses the i-th operation of
P ₁ , P ₂ , P ₃ are Therefore, each row has two non-zero elements, representing a butterfly operation. Similarly, if the column vector of the input time series arranged in reverse binary order is X, the transformation matrix is C, and the column vector of the Walsh spectrum is W, then the FWT is W=C・X=C _o・G _o-1・...G ₁・X ...(7) It can be expressed as the product of n times of matrices. Here each G _i
is determined from equations (8), (9), and (10). When n=3, the Walsh spectrum is W=
(W ₀ , W ₂ , W ₄ , W ₆ , W ₇ , W ₅ , W ₃ , W ₁ ). Furthermore, the calculations G ₁ , G ₂ , and G ₃ at each stage are G ₁ = P ₁ becomes. As explained above, in FWT, element a ^k _i of D _i in FFT is set as a ^k _i =exp(-jθ), and when 0Θ<π/2, replace a _i ^k →1, and when π/2Θ<π, a It can be thought of as replacing _i ^k →−1. In this way, the Walsh transform can be considered as quantizing the trigonometric function values in the Fourier transform to ±1, and an approximation of the Fourier spectrum can be obtained by calculations without multiplication. However, due to the rough quantization, a good approximation of the Fourier spectrum cannot be obtained. SUMMARY OF THE INVENTION An object of the present invention is to provide a multi-value Walsh transform device that can obtain a multi-value Walsh spectrum using only an adder/subtractor or a shifter and an adder/subtracter, and which is closer to a Fourier spectrum than a Walsh spectrum. The multi-level Walsh transform device of the present invention includes a buffer memory section that holds input time-series data, and an adder/subtracter or a shifter and an adder/subtracter for obtaining a multi-level Walsh spectrum using the data read out from the buffer memory section. It has a value processor, a buffer memory section, and a control section for controlling the multivalue processor. The multivalued Walsh transform device of the present invention can be configured by simple operations using an adder/subtractor or a shifter and an adder/subtracter by limiting the number of elements to 1 or 1/2 to convert the Walsh function into a multivalued and complex number. . Furthermore, the multi-value Walsh transform device has the advantage of being able to obtain a multi-value Walsh spectrum that has a higher degree of approximation to the Fourier spectrum than the Walsh spectrum. Next, multilevel Walsh transform, which is the principle of the present invention, will be explained. The Walsh function is a trigonometric function ±
Since it is quantized to 1, it can be made closer to the Fourier spectrum by introducing a multivalued Walsh function with finer quantization. As a method of multi-value conversion, it is possible to correspond to several points on a unit circle of a complex plane. For example, as shown in Figure 2 A multivalued Walsh function with eight elements is considered. However, since the multivalued Walsh function according to the above method has elements such as e〓 ^/4j , the conversion requires multiplication. Here e〓 1+j instead of ^/4j
We propose a method using That is, as shown in Figure 3 (1, 1+j, j, -1+j, -1, -1-j, -
We propose an 8-valued Walsh function with 8 elements of j, 1-j). The 8-value Walsh transform operation using this function system is a multiplication operation with (±1, ±j), so it can be executed only by addition and subtraction. The specific calculation method is the FFT calculation procedure shown in equations (2), (3), (4), and (5), with equation (5) changed to equation (11). Di=diag(1, [a _i ], [a _i ² ],…, [a _i ^2i-1 ])…
…(11) However, when a _i = exp(jπ/2 ⁱ ), a _i ^k = e ^j 〓, [e ^j 〓] = 1, 0Θ<π/4, =1+j, π/4Θ<π/2 When = j, π/2Θ < 3π/4 = -1+j, 3π/4Θ < π We propose a 16-value Walsh function that can further improve the degree of approximation of the Fourier spectrum. That is, as shown in Figure 4 (1, 1+1/2j, 1+j, 1/2+j, j, -1
/2 +j, -1+j, -1+1/2j, -1, -1-1/2
j, -1-j, -1/2-j, -j, 1/2-j, 1-j,
We propose a 16-valued Walsh function with 16 elements of 1 - 1/2j). The calculation of 16-value Walsh transform using this function system is a calculation of the product of (±1/±1/2, ±j/±1/2j), so it can be executed only by halving using a shifter and addition/subtraction. be. The specific calculation method is the same as the 8-value Walsh transform method, and instead of formula (11), formula (12) is used.
Use the formula. Di=diag(1, [a _i ], [a _i ² ],…, [a _i ^2i-1 ])…
…(12) However, [e ^j 〓]=1, when 0Θ<π/8 =1+1/2j, when π/8Θ<π/4 =1+j, when π/4Θ<3π/8 =1/2+j , when 3π/8Θ<π/2 j=, when π/2Θ<5π/8 =-1/2+j, when 5π/8Θ<3π/4 =-1+j, when 3π/4Θ<7π/8 =-1+1/2j, when 7π/8Θ<π Next, a specific configuration of the apparatus of the present invention will be described with reference to the drawings. The first embodiment of the present invention is as shown in FIG.
Buffer memory unit 1, multivalued Walsh calculation unit 2,
This device is composed of a control section 3 and executes 8-value Walsh conversion using equations (2), (3), (4), and (11). First, time-series data of complex numbers is generally input to the buffer memory section 1 and temporarily stored. FIG. 8a is a flowchart of the calculation when n=4, and the calculation is sequentially advanced from the first stage to the nth stage by control signals from the control section 3 according to this diagram. The process of the k-th stage is to execute 2 ^n-1 butterfly operations of the k-th stage shown in FIG. 8a, and P _k in equation (2)
This means multiplying the matrix of . The processing at each stage reads data from the buffer memory section 1, performs a butterfly operation, and the result is written to the buffer memory section 1 again. The butterfly operation is as shown in Fig. 8b, y _i = x _i + x _j・a _k ...(13) y _j = x _i −x _j・a _k ...(14), and as shown in Fig. 6 It is determined by the multivalued Walsh calculation unit 2. In the butterfly operation, x _i and x _j are first read from buffer memory unit 1, and the real and imaginary parts of x _i are temporarily stored in registers 201 and 202, and the real and imaginary parts of x _j are temporarily stored in registers 203 and 204, respectively. Stored. Complex number multiplication of x _j · a _k is performed by the following four types of addition and subtraction. If (Z _R + jZ _I ) = (x _jR + jx _jI )・a _k , then in the case of 8-value Walsh transform, a ₀ = a ₁ = 1, a ₂ = a ₃ = 1 + j, a ₄ = a ₅ = j, a ₆ =
Considering that a ₇ = -1 + j, when a ₀ = a ₁ = 1, Z _R = x _jR ... (15) Z _I = x _jI ... (16) when a ₂ = a ₃ = 1 + j Z _R ＝x _jR −x _jI ……(17) Z _I ＝x _jR ＋x _jI ……(18) When a ₄ = a ₅ = j Z _R ＝−x _jI ……(19) Z _I ＝x _jR ...(20) When a ₆ = a ₇ = -1 + j, Z _R = -x _jR -x _jI ... (21) Z _I = x _jR -x _jI ... (22). These calculations are performed by a switch 211 and adders/subtractors 221 and 222 under control signals from the control section 3. In other words, the switch 211 is the adder/subtractor 2
The inputs of 21 and 222 are selected from x _jR , x _jI , and 0, and the adder/subtractors 221 and 222 perform addition, subtraction, addition, and sign inversion to perform the calculations of equations (15) to (22) above. . Next, addition and subtraction in equations (13) and (14) are as follows:
It is executed separately for the real part and the imaginary part, and the adder 231
and 232 and subtracters 233 and 234. The obtained results y _i and y _j are buffer memory part 1
x _i and x _j of are written to the location where they were stored. The result of the processing at the n-th stage, which is the final stage, is an 8-value Walsh spectrum F _i that has been subjected to 8-value Walsh transform. Next, the second embodiment of the present invention includes (2), (3), (4), (12)
This device executes 16-value Walsh conversion using the formula, and is obtained by changing the multi-value Walsh calculation section 2 of the first embodiment to the configuration shown in FIG. The calculation proceeds in the same manner as in the first embodiment. The difference between the second embodiment and the first embodiment is that the control unit 3 outputs a control signal according to the calculation flowchart shown in FIG. 9, and that the value of the multiplication element a _k in the butterfly calculation is 8. There are different types. The butterfly calculation in the second embodiment is obtained by the multivalued Walsh calculation unit 2 shown in FIG. In the butterfly operation, x _i and x _j are first read from buffer memory section 1, and the real and imaginary parts of x _i are stored in register 2.
01 and 202, the real part and imaginary part of x _j are temporarily stored in registers 203 and 204, respectively. By the way, the complex number multiplication of x _j · a _k is executed by the following eight operations. (Z _R + jZ _I ) = (x _jR + jx _jI )・a _k , and when a ₀ = 1, Z _R = x _jR ... (23) Z _I = x _jI ... (24) a ₁ = 1 + 1/2j When Z _R = x _jR −1/2x _jI …(25) Z _I =1/2x _jR +x _jI …(26) When a ₂ =1+j Z _R =x _jR −x _jI …(27) Z _I = x _jR + x _jI ...... (28) When a ₃ = 1/2 + j Z _R = 1/2x _jR -x _jI ... (29) Z _I = x _jR -1/2x _jI ... (30) When a ₄ = j, Z _R = -x _jI ... (31) Z _I = x _jR ... (32) When a ₅ = -1/2 + j, Z _R = -1/2x _jR -x _jI ... ( 33) Z _I =x _jR −1/2x _jI ……(34) When a ₆ =−1+j Z _R =−x _jR −x _jI ……(35) Z _I ＝x _jR −x _jI ……(36 ) When a ₇ = -1 + 1/2j, Z _R = -x _jR -1/2x _jI ... (37) Z _I = 1/2x _jR -x _jI ... (38) These calculations are controlled by the control unit 3. Under the signal
It is obtained by shifters 241 and 242, switch 212, and adder/subtractors 221 and 222. That is, the shifters 241 and 242 can obtain 1/2x _jR and 1/2x _jI by shifting one bit to the right, and the switch 212 changes the inputs of the adders/subtracters 221 and 222 to x _jR , x _jI , 1/2x _{jR .} Next, addition and subtraction in equations (13) and (14) are as follows:
It is executed separately for the real part and the imaginary part, and the adder 231
and 232 and subtracters 233 and 234. The obtained results y _i and y _j are buffer memory part 1
x _i and x _j of are written to the location where they were stored. The result of the processing at the n-th stage, which is the final stage, is a 16-value Walsh spectrum F _i that has been subjected to 16-value Walsh transform. Next, FIG. 10 is a block diagram of a third embodiment of the present invention, which is an 8-value Walsh transform device that directly multiplies the matrix A of equation (2), and is a DFT that is one method for obtaining a Fourier spectrum. Find it in the same way as. Now, the element in the k row and i column of the matrix A in equation (2) is
If a _ki and X = (x ₀ , x ₁ , ..., x _i , ..., x _2o-1 ), then F _k = _2o-1 〓 ⁱ⁼⁰ a _ki・x _i ...(39) A multivalued Walsh spectrum F _k is obtained by calculating the product sum of a _ki and the input time series x _i . Here, A=P ₁・P ₂ ...・P _o , so a _ki is shown in Figure 3 in the case of 8-level Walsh transformation (1, 1 +
j, j, -1+j, -1, -1-j, -j, 1-j)
It is one of the eight. Therefore, the product in equation (39) can be calculated using an adder/subtractor. First, the signal Cl from the control section 3 clears the accumulators 261 and 262 according to the time chart shown in FIG. Subsequently, input time series data x _i is sequentially read out from the buffer memory section in accordance with the signal i varying from 0 to 2 ⁿ -1. Here, the multivalued Walsh calculation unit 2
As shown in Figure 2, the real part accumulator 261, the imaginary part accumulator 262, _the real part adder/subtractor 251, the imaginary part adder/subtracter 252, and the data It is composed of a switch 213 that inputs input to an adder/subtracter 252, and performs the following eight operations under the control of a control section. Letting the contents of the real part accumulator 261 and the imaginary part accumulator 262 be ACC _R and ACC _I , respectively, when a _ki = 1, ACC _R +x _i →ACC _R ACC _I +0 → ACC _I , when a _ki = 1 + j, ACC _R +x _i →ACC _R ACC _I +x _i →ACC _I a _ki When = j ACC _R +0 → ACC _R ACC _I +x _i →ACC _I a _ki When =-1+j ACC _R −x _i →ACC _R ACC _I +x _i → When ACC _I a _ki =-1 ACC _R −x _i →ACC _R ACC _I −0→ACC _I a When _ki =-1−j ACC _R −x _i →ACC _R ACC _I −x _i →ACC _I a When _ki = -j ACC _R +0 → ACC _R ACC _I -x _i →ACC _I a When _ki = 1-j, switch 213 to perform the calculation ACC _R +x _i →ACC _R ACC _I -x _i →ACC _I and adder/subtractor 25
1 and 252 are controlled. When the signal i becomes 2 ⁿ −1, the accumulator 26
The real part and imaginary part of _Fk , which is the k-th order term of the multilevel Walsh spectrum, are obtained at 1 and 262, respectively. Next, the fourth embodiment is a 16-value Walsh transform device that directly calculates the sum of products of a _ki and the input time series x _i according to equation (39). In the case of 16-value Walsh transform, a _ki in equation (39) is shown in Figure 4 (1, 1+1/2j, 1 +j, 1/2+j, j, -1/2+j, -1+j, -1
+ 1/2j, -1, -1-1/2j, -1-j, -1/2
-j, -j, 1/2-j, 1-j, 1-1/2j), and the product of equation (39) is obtained using a shifter and an adder/subtracter. For this reason, the multi-valued Walsh calculation unit 2 in the fourth embodiment has a configuration in which a shifter 243 is inserted in front of the switch 214, as shown in FIG. . As in the third embodiment, the following 16 operations are performed under the control of the control section 3.

[Table] 2
2
The switch 214 and shifter 243
and the adders/subtractors 251 and 252 are controlled. The shifter 27 outputs 1/2 x _i . When the signal i becomes 2 ⁿ -1, the real part and imaginary part of the multilevel Walsh spectrum F _k are obtained in the accumulators 261 and 262, respectively. Although the present invention has been described above based on Examples, these descriptions do not limit the scope of the present invention. In particular, in the embodiment of the present invention, the FFT algorithm rearranges the input time series in reverse binary order,
This is a method of multiplying P _o by P ₁ and obtaining the results in positive order, but the input time series is multiplied by P ^T _o by P ^T ₁ in the same order.
It is obvious that the method of multiplying , and obtaining the results in binary reverse order can also be adopted. Up to this point, we have explained 8-value and 16-value Walsh transformations, but as an extension of 8-value and 16-value conversion, a multi-value conversion using points on a unit square centered on the origin shown in Figure 4 with 32 values, 64 values, etc. Walsh functions are considered, and these are 1/2 by shifter,
It is obvious that it can be obtained by addition and subtraction such as 1/4, . . .

[Brief explanation of drawings]

Figure 1 is a diagram showing the Walsh transformation matrix and the Walsh function, Figure 2 is a diagram showing the function values of the multivalued Walsh function of the present invention, and Figure 3 is a diagram showing the function values of the 8-valued Walsh function. FIG. 4 is a diagram showing the function values of the 16-value Walsh function, and FIG. 5 is a diagram showing the first and second functions of the present invention.
FIG. 6 is a block diagram of the multivalued wallet calculation unit 2 of the first embodiment, and FIG. 7 is a block diagram of the multivalued waterfall calculation unit 2 of the second embodiment. 8a is a calculation flowchart of the first embodiment, FIG. 8b is a calculation flowchart of the butterfly operation, and FIG. 9 is a calculation flowchart of the second embodiment. FIG. 10 is a block diagram of the third and fourth embodiments, FIG. 11 is a time chart of control signals in the third and fourth embodiments, and FIG. 12 is a block diagram of the third embodiment. 13 is a block diagram of the value wallet calculation unit 2;
The figure is a block diagram of the multivalued Walsh calculation unit 2 of the fourth embodiment. Figure 5, Figure 6, Figure 7, Figure 10, Figure 12
13, 1 is a buffer memory section;
2 is a multivalued Walsh calculation unit, 3 is a control unit, 20
1, 202, 203, 204 are registers, 21
1,212,213,214 are switches, 22
1, 222, 251, 252 are adders and subtracters, 23
1,232 is an adder, 233,234 is a subtracter,
241, 242, 243 are shifters, 261, 26
2 is an accumulator.

Claims (1)

[Scope of Claims] 1. A multi-value Walsh transform device that transforms an input time-series signal using a multi-value Walsh function obtained by converting a Walsh function into a multi-value and complex number, comprising: a buffer memory section that holds input time-series data; a multivalued wallet calculation unit that multiplies the ^data read from the buffer memory unit by a complex constant given from the control unit; ) A multi-valued Walsh transform device, comprising a control section that gives complex numbers of divided points and controls the buffer memory section and the multi-valued Walsh calculation section. 2. The multi-value Walsh transform device according to claim 1, wherein multiplication with a complex constant in the multi-value Walsh calculation unit is performed by an adder/subtractor. 3. The multi-value Walsh transform device according to claim 1, wherein the multi-value Walsh calculation unit performs multiplication with a complex constant by an adder/subtractor and a shifter.