JP2008158855A - Correlation computing element and correlation computing method - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a correlation computing element, calculating a correlation value with less computational complexity, and a correlation computing method applicable to such a correlation computing element. <P>SOLUTION: The correlation computing element calculates a normalized correlation factor Corr (n, k) for two kinds of discrete time signals X(n) and Y(n) which have a time difference k. The computing element comprises a first binary coding means for converting the discrete time signal X(n) to a 1-bit signal X<SB>bin</SB>(n) according to whether it is less than an intermediate value of the dynamic range, equal to the intermediate value, or exceeds the intermediate value; a second binary coding means for converting the discrete time signal Y(n) to a 1-bit signal Y<SB>bin</SB>(n) according to whether it is less than an intermediate value of the dynamic range, equal to the intermediate value or exceeds the intermediate value; and a computing means for calculating a correlation value between the 1-bit signals X<SB>bin</SB>(n) and Y<SB>bin</SB>(n) from the first and second binary coding means, and outputting it as the correlation factor Corr (n, k). <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention relates to a correlation calculator and a correlation calculation method, and can be applied to, for example, a correlation calculation of a discrete value system used in an immediacy system in the field of communication and measurement.

[Definition of discrete normalized cross-correlation coefficient]
The correlation calculation for calculating the similarity between two kinds of signals is frequently performed in a wide range of scientific and technical fields, and it is known that its application range is extremely wide.

In general, the normalized cross-correlation coefficient Corr (n, k) of two discrete-time signals X (n) and Y (nk) is defined by the following equation.

  Here, the time signals X (n) and Y (n) in the discrete value system are sampled in unit time, and the index n represents the current time. Further, 0 ≦ k <M.

The qualitative meaning of the formula (1) will be described. When the time n is fixed, the similarity of the signal X (n−i), 0 ≦ i <N and Y (n−k−i), 0 ≦ i <N, which is composed of N samples, is calculated. The search range is 0 ≦ k <M. That is, since M normalized cross-correlation coefficients Corr (n, 0), Corr (n, 1),..., Corr (n, M−1) are obtained at the current time n, Corr (n , the absolute value of k) | Corr (n, k ) | when referred to k when the maximum value and _{k max, X (n-i} ), the highest similarity signal to 0 ≦ i <n Is Y (n−k _max −i), where 0 ≦ i <N.

  The above procedure is repeated every time time n is updated.

[Amount of calculation]
A precondition is provided for estimating the amount of calculation of the discrete normalized cross-correlation coefficient Corr (n, k) represented by the equation (1).

(Precondition 1) Every time the discrete time n is updated, the variable k in the equation (1) is changed in the range of 0 ≦ k <M. Therefore, the equation (1) is calculated M times. In order to simplify the calculation of the amount of correlation calculation using conversion, M = N is set. Therefore, the calculation amount when calculating the expression (1) N times is calculated.

(Precondition 2) The product-sum operation that can be expressed in the form of a × b + c can be calculated in one machine cycle (one clock period) by hardware.

  Based on the above preconditions, the amount of calculation when the calculation of equation (1) is repeated N times is calculated.

First, the numerator of equation (1) requires N product-sum operations. Furthermore, since this is performed for 0 ≦ k <N, N ² product-sum operations are required.

Next, a calculation amount is obtained for the square root on the left side of the denominator. Since the variable k does not appear in this term, it may be calculated once every time n is updated. If the sum of squares S _X at time n−1 is defined as shown in equation (2), the calculation shown in equation (3) is required when the time is updated from n−1 to n. Let's assume that the amount of calculation in the equation can be calculated α times by converting it to the number of product-sum operations. Similarly, for the square root on the right side of the denominator, the same processing as in equation (3) is required every time k is updated.

From the above, the processing amount required to calculate the expression (1) N times is N ² + αN + α when converted by the number of product-sum operations. Here, primary and 0-order term of when N is large, N is negligible, amount of processing required to compute N times (1) is proportional to N ^2. That is, the order of the processing amount is O (N ² + αN + α) = N ² .

[Reduction of calculation amount by conventional technology]
According to Non-Patent Document 1, with the advent of Fast Fourier Transform (FFT), the calculation of Equation (1) is temporarily performed in the time domain signals X (n) and Y (n) rather than being realized in the time domain. ) Is converted into frequency domain signals X (r) and Y (r) using FFT to calculate Z (r) = X (r) Y ^* (r) ( ^* represents a conjugate complex number), Next, it is known that if Z (r) is subjected to inverse Fourier transform using FFT, a correlation calculation in the time domain can be obtained, and this can reduce the calculation amount. For example, the calculation amount when calculating the expression (1) N times can be reduced to a processing amount proportional to Nlog ₂ N by using FFT. Since the order of the processing amount is reduced from N ² to Nlog ₂ N, the advantage of using FFT increases as the value of N increases.

A specific implementation example of FFT is described in Patent Document 1.
Japanese Patent Laid-Open No. 5-174046 E. By ORAN BRICHAM / Translated by Miyagawa, “Fast Fourier Transform”, Chapter 13

  As described above, the amount of calculation can be reduced by using the fast Fourier transform (FFT) in the correlation calculation of equation (1). This is an effective method when there is a request to calculate equation (1) as accurately as possible and in a short time.

  However, from an application point of view, there is a demand for obtaining a correlation coefficient in a short time and using an arithmetic unit with a small hardware scale, rather than calculating the correlation coefficient mathematically accurately. There are many. In particular, such demands tend to be strong in the field of signal processing that is severe in immediacy.

This will be explained by a specific example. When the radar system is to obtain the distance to the object to be measured, the transmission signal is S (n−k), the reflection signal is R (n), and both signals S (n−k). ) And R (n) normalized cross-correlation coefficients, and k when the absolute value of the correlation coefficient is the _maximum is expressed as k _max , k _max is the round-trip propagation delay time to the object to be measured. Correspondingly, this makes it possible to calculate the distance to the object to be measured. In this case, we want to know the value of k _max that maximizes the correlation coefficient, and it is not necessary to know the exact value of the correlation coefficient itself. In other words, if the relative magnitude relationship of a plurality of correlation coefficients obtained by changing k is kept moderate, the correlation coefficient value itself does not need to be determined accurately.

  Under such requirements, the correlation calculation using FFT may result in excessive quality in the calculation accuracy, and it does not necessarily meet the requirement to further reduce the calculation amount even at the expense of the calculation accuracy. I can't.

  Further, even if the correlation operation is performed by FFT, a product-sum operation unit and a memory for holding data are still required, and the hardware scale is not much different from that when performing the correlation operation in the time domain.

  This leads to an increase in device volume, power consumption and cost, especially when the correlation calculator is incorporated into a small device such as a sensor used in remote sensing.

  The present invention has been made in view of the above points, and intends to provide a correlation calculator capable of calculating a cross-correlation value with a small amount of calculation and a correlation calculation method applicable to such a correlation calculator. It is a thing.

The first aspect of the present invention calculates a normalized cross-correlation coefficient Corr (n, k) when there is a time difference k between the two types of discrete time signals X (n) and Y (n). In the correlation calculator, (1) a first to convert the discrete time signal X (n) into a 1-bit signal X _bin (n) corresponding to whether the dynamic range is less than the intermediate value, the intermediate value, or the intermediate value (2) a second encoding means for converting the discrete time signal Y (n) into a 1-bit signal Y _bin (n) corresponding to whether the dynamic range is less than an intermediate value, an intermediate value, or an intermediate value; 2 binary encoding means, and (3) based on the 1-bit signals X _bin (n) and Y _bin (n) from the first and second binary encoding means, an operation according to the equation (A) is performed. An operation that is executed and outputs the calculation result as the cross-correlation coefficient Corr (n, k). And having a stage.

  Here, N is the number of samples of each signal used for calculating the correlation, and a symbol in which + is circled represents an exclusive OR operation.

The second aspect of the present invention calculates a normalized cross-correlation coefficient Corr (n, k) when there is a time difference k between the two types of discrete time signals X (n) and Y (n). The correlation calculation method includes (0) first binary encoding means, second binary encoding means, and calculation means. (1) The first binary encoding means is discrete. The time signal X (n) is converted into a 1-bit signal X _bin (n) corresponding to whether the dynamic range is less than the intermediate value, the intermediate value, or the intermediate value, and (2) the second binary encoding The means converts the discrete time signal Y (n) into a 1-bit signal Y _bin (n) depending on whether the dynamic range is less than an intermediate value, an intermediate value or an intermediate value, and (3) , based on the 1-bit signal _{X bin} (n) and _{Y bin} (n) from the first and second binary coding means , And outputs the (B) performs an operation according to equation above cross-correlation coefficient Corr the calculation result (n, k).

  Here, N is the number of samples of each signal used for calculating the correlation, and a symbol in which + is circled represents an exclusive OR operation.

  According to the present invention, since the cross-correlation value is calculated by converting the input signal into a 1-bit signal, the cross-correlation value can be calculated with a small amount of calculation.

(A) Main embodiment
Hereinafter, an embodiment of a correlation calculator and a correlation calculation method according to the present invention will be described with reference to the drawings.

(A-1) Technical idea in the embodiment In this embodiment, the two types of signals to be correlated are encoded into binary values of +1 and -1, respectively, thereby reducing the amount of calculation and the hardware scale required for the correlation calculation. It is intended to greatly reduce.

[Normalized cross-correlation algorithm for binary signals]
First, a normalized cross-correlation calculation algorithm for signals binarized to ± 1 will be described.

In general, the normalized cross-correlation coefficient Corr (n, k) of two discrete-time signals X (n) and Y (nk) is defined by equation (4).

  Here, 0 ≦ k <M. In general, the numerical format of the signals X (n) and Y (n) is a floating point or a fixed point composed of a plurality of bits.

Next, signals obtained by encoding the signals X (n) and Y (n) into binary values of ± 1 are expressed as X _sgn (n) and Y _sgn (n), respectively, and defined as in equation (5) To do.

Here, when the signal X (n) is 0 immediately after the operation starts, X (n−1) and X _sgn (n−1) do not exist yet, so the value of X _sgn (n) is +1 Either -1 or -1 is acceptable. The same applies to the signal Y (n).

The normalized cross-correlation coefficient Corr _sgn (n, k) of both signals X _sgn (n) and Y _sgn (n) can be expressed by equation (6). In the equation (6), 0 ≦ k <M.

As shown in equation (5), each signal X _sgn (n), Y _sgn (n) is a binary value of ± 1, but it is handled as 1-bit binary data on an actual implementation (product). Here, according to the general definition of the sign bit representing positive and negative, the numerical value +1 is made to correspond to the binary number “0”, and the numerical value −1 is made to correspond to the binary number “1”. FIG. 2 shows the binary representation of the binary signals X _sgn (n) and Y _sgn (n) as X _bin (n) and Y _bin (n) and shows the correspondence.

Next, the multiplication X _sgn ( _ni ) Y _sgn ( _ni ) in the equation (6) will be considered using the correspondence relationship of FIG. There are only four such multiplications, and the correspondence with binary numbers at this time is as shown in FIG. In FIG. 3, a symbol in which + is surrounded by a white circle represents an exclusive OR. In the specification, such a symbol cannot be used. Therefore, in the specification, “∧” is used as an exclusive OR.

As is apparent from FIG. 3, the multiplication of the signal binarized to ± 1 corresponds to an exclusive OR in the binary number. _{Thus, X bin (n-i)} ∧Y bin sum of (n-k-i) from i = 0 for up to _{N-1 ΣX bin (n-} i) ∧Y bin (n-k-i) is , ΣX _sgn (n−i) Y _sgn (n−k−i) (the sum is from i = 0 to N−1), X _sgn (n−i) Y _sgn (n−k−i) is −1 Will be expressed. Conversely, the number of X _sgn (n−i) Y _sgn (n−k−i) that is 1 is N−ΣX _bin (n−i) ∧Y _bin (n−k−i). Therefore, equation (7) is established. Here, when the normalized cross-correlation coefficient Corr _sgn (n, k) is expressed using binary notation X _bin (n), Y _bin (n), equation (8) is obtained. In equation (8), 1 / N, which is a normalization process, is simply a constant, and is not worth computing in application, so equation (8) is transformed into equation (9).

(A-2) Correlation Calculator of Embodiment FIG. 1 is a block diagram showing the overall configuration of the correlation calculator of the embodiment. The correlation calculator 100 of the embodiment calculates a correlation coefficient between two input signals according to the equation (9).

  In FIG. 1, the correlation calculator 100 according to the embodiment includes two code bit extractors 101 and 102, two shift registers 103 and 104, an exclusive OR gate group 105, an adder 106, and a subtractor 107. .

A discrete time signal X (n) is input to the sign bit extractor 101, and the sign bit extractor 101 is in accordance with the expression (10) according to the positive value, the negative value, and 0 of the input signal X (n). A 1-bit signal X _bin (n) is output. The addition of the upper bar in equation (10) represents the negation of the assigned bit value, that is, the bit inversion of the assigned bit value. In this specification, bit inversion is represented by adding “/” in front of a sign representing a value to be inverted.

  When the discrete time signal to be processed is a signal having a range of 0 and a positive value, the median of the dynamic range is subtracted from the processing target signal to obtain a positive and negative discrete time signal X ( n) and input to the sign bit extractor 101.

Similarly, the sign bit extractor 102 determines the 1-bit signal Y _bin (n) according to the expression (11) according to the positive value, the negative value, and 0 of the discrete time signal Y (n) that is the other input signal. Is output.

  FIG. 4 shows a specific configuration example of the sign bit extractor 101 when the numerical format of the discrete time signal X (n) is 2's complement. Although not described, the code bit extractor 102 is the same.

  In FIG. 4, the sign bit extractor 101 includes a NOR gate 201, a 2-1 selector 202, a NOT gate 203, and a register 204.

  Since the numerical format of the input signal X (n) is 2's complement, the MSB bit is a sign bit. The sign bit is 0 when 0 ≦ X (n) and 1 when X (n) <0. When the input signal X (n) = 0, all the bits of the input signal X (n) are 0.

  All bits of the input signal X (n) are input to the NOR gate 201. The output of the NOR gate 201 is 1 only when X (n) = 0, and 0 otherwise, and this output signal is The signal is supplied to the selection control terminal of the 2-1 selector 202.

The MSB bit, which is the sign bit of the input signal X (n), is input to one input terminal of the 2-1 selector 202, and the output from the sign bit extractor 101 is input to the other input terminal of the 2-1 selector 202. signal _X signal before one unit time of the _{bin (n) X bin (n} -1) and the bit inversion _{/ X} bin (n-1) is input. 2-1 selector 202, in response to the output signal of the NOR gate 201, select when the input signal X (n) is 0 only _{/ X bin (n-1)} , the output of the 2-1 selector 202 _{X bin} ( n), otherwise, the sign bit of the input signal X (n) is selected and appears as X _bin (n) in the output of the selector 202.

The register 204 is a register for storing the output signal Xbin (n) of the 2-1 selector 202, and the stored value is updated in synchronization with the sampling rate of the input signal X (n). Therefore, the output of the register 204 is X _bin (n−1) which is a value one unit time before the output signal X _bin (n).

The output signal X _bin (n−1) from the register 204 is input to the NOT gate 203, and the NOT gate 203 bit-inverts this signal X _bin (n−1) to / X _bin (n−1) as 2- 1 is given to the selector 202.

The configuration example of the code bit extractor 101 shown in FIG. 4 is merely an example for realizing the above-described equation (10). For example, when it is desirable to update the output signal X _bin (n) from the sign bit extractor 101 in synchronization with the sampling rate, the output of the register 204 is used as the output signal Xbin (n) from the sign bit extractor 101. It is also good. Even when the numerical format is not 2's complement, the sign bit extractor may be designed in accordance with the numerical format so as to satisfy the expression (10).

  The two shift registers 103 and 104 and the exclusive OR gate group 105 in FIG. 1 perform the exclusive OR operation shown in the equation (12), which is the element operation of the above equation (9), with respect to i. In the range of ≦ i <N, it is executed in parallel in one machine cycle, and k is executed in the range of 0 ≦ k <M in M machine cycles.

X _bin (n−i) ∧Y _bin (n−k−i) (12)
The shift register 103 forms the element X _bin (n−i) on the left side of the equation (12) by an amount necessary for the summation of the equation (9), and the shift register 104 has the right side of the equation (12). Elements Y _bin (n−k−i) are formed as much as necessary for the summation of equation (9), and the exclusive OR gate group 105 has N exclusive gates related to the summation of equation (9). A value of logical sum is formed.

  FIG. 5 is a block diagram illustrating a specific configuration example of the shift registers 103 and 104 and the exclusive OR gate group 105.

As will be described below, in the configuration example of FIG. 5, k is changed to 0 while decrementing with M−1 as an initial value, and this should be noted for understanding the operation. is there. Further, in FIG. 5, in order to simplify the notation, with respect to the output from the exclusive OR gate group 105, where X _bin (n) and Y _bin (n) should be described, simply X (n) , Y (n).

  One shift register 103 is an N-bit shift register having a serial input parallel output function. The shift register 103 includes a serial input terminal SI, a shift enable input terminal SE, a clock input terminal CK, and a parallel output terminal (a storage unit corresponding to the parallel output terminal is appropriately referred to as a register) Q (0) to Q (N− 1). In the following description, signals related to the input / output terminals are also described using the same reference numerals as the input / output terminals.

In the shift register 103, when the shift enable signal SE is active, the bit information of the register Q (N-2) is shifted to the register Q (N-1) in synchronization with the clock signal CK synchronized with the sampling rate. , The bit information of the register Q (N-3) is shifted to the register Q (N-2). Similarly, the bit information of the register Q (0) is shifted to the register Q (1), and the sign bit extractor 101 The signal X _bin (n) input from is stored in the register Q (0) via the serial input terminal SI.

Accordingly, at time n, the parallel output terminals Q (0) to Q (N−1) of the shift register 103 are connected to the signals X _bin (n) to X _bin (n− (N−1)). While N bits appear and are held until the next input signal X _bin (n + 1) is input, these N bits X _bin (n) to X _bin (n− (N−1)) are exclusive. This is supplied to the OR gate group 105.

  The other shift register 104 is an N + M−1 bit shift register having a serial input parallel output function, a parallel input loading function, and a rotate shift function (cyclic shift function).

  The shift register 104 holds 1-bit information output from the sign bit extractor 102, is bit-shifted time-sequentially in a sampling period, and is rotated by a fixed number of times within one sampling period, and When the 1-bit information output from the code bit extractor 102 is input again after the rotate shift, the loading function is provided that can shift the state by 1 bit from the previous input.

  The shift register 104 includes a serial input terminal SI, a shift enable input terminal SE, a load enable input terminal LE, a clock input terminal CK, parallel input terminals D (0) to D (N + M−2), and a parallel output terminal Q (0 ) To Q (N + M−2).

  The N bits of the parallel output terminals (registers) Q (M−1) to Q (N + M−2) are connected to the exclusive OR gate group 105, and the serial output terminal SI outputs the register output of the last stage of the shift register 104. Q (N + M−2) is input.

The signal Y _bin (n) output from the sign bit extractor 102 is input to the parallel input terminal D (0), and the parallel output terminal Q (M−1) of the shift register 104 is input to the parallel input terminal D (1). ) Are connected, and the parallel output terminal Q ((2M-5) mod (N + M-1)) of the shift register 104 is connected to the parallel input terminal D (M-3), and the parallel input terminal D (M -2) is connected to the parallel output terminal Q ((2M-4) mod (N + M-1)) of the shift register 104, and the parallel input terminal D (M-1) is connected to the parallel output terminal of the shift register 104. Q ((2M−3) mod (N + M−1)) is connected, and the parallel output terminal Q ((2M−2) mod (N + M) of the shift register 104 is connected to the parallel input terminal D (M). 1)) is connected to the parallel input terminal D (N + M-3) and the parallel output terminal Q (M-4) of the shift register 104 is connected to the parallel input terminal D (N + M-2). The parallel output terminal Q (M-3) of the shift register 104 is connected.

  Here, s mod t represents the remainder of s when t is modulo. For example, 9 mod 8 = 1. When the feedback path from the parallel output terminal to the parallel input terminal of the shift register 104 described above is generally expressed using this mod, the parallel output terminal Q ((x + M−2) is connected to the parallel input terminal D (x). mod (N + M-1)) is connected. However, x ≠ 0. The reason for connecting the shift register 104 as described above will be described later.

  When the load enable signal LE of the shift register 104 is active, the parallel input terminals D (0) to D (N + M−2) are connected to the parallel output terminals Q (0) to Q (N + M−2) in synchronization with the clock signal CK. ) Loaded. On the other hand, when the shift enable signal SE of the shift register 104 is active, the bit information of the register Q (0) is shifted to the register Q (1) in synchronization with the clock signal CK, and the register Q (1) Bit information is shifted to the register Q (2). Similarly, the bit information of the register Q (N + M-3) is shifted to the register Q (N + M-2). However, the bit information of the final stage register Q (N + M−2) is rotated and shifted to the register Q (0) via the serial input terminal SI. Note that the load enable signal LE and the shift enable signal SE do not become active at the same time.

At time n, the load enable signal LE of the shift register 104 is activated, and the output signal Y _bin (n) from the sign bit extractor 102 is loaded into the register Q (0) of the shift register 104. Next, the load enable signal LE of the shift register 104 is made inactive, the shift enable signal SE is made active, and is shifted about M-1 times in synchronization with the clock signal CK. This operation must be completed before the next signal Y _bin (n + 1) from the sign bit extractor 102 is input. Therefore, when the frequency of the clock signal CK of the shift register 104 is set to f _ck and the sampling frequency of the signal Y _bin (n) is set to f _s , the relationship expressed by the equation (13) must be established. By doing so, it is possible to perform the calculation for each element of the equation (12) in M machine cycles for 0 ≦ i ≦ N−1 and M−1 ≧ k ≧ 0 within one sampling period. Become.

f _ck ≧ (M + 1) · f _s (13)
Note that when the shift register 104 is shifted by M−1 bits, the signal Y _bin (n) has moved to the register Q (M−1). This signal Y _bin (n) needs to be loaded into the register Q (1) when the next signal (bit information) Y _bin (n + 1) arrives. This is the reason why the parallel output terminal of the shift register 104 is twisted and connected to its parallel input terminal.

  Incidentally, as described above, since the N bits of the parallel output terminals (M−1) to Q (N + M−2) of the shift register 104 are output to the exclusive OR gate group 105, the loading of the shift register 104 is performed. Sometimes this corresponds to k = M−1 in equation (12), and then every time the shift register 104 is bit shifted, the order of K = M−2, M−3,. Thus, the parallel logic operation for 0 ≦ i <N−1 in the equation (12) is executed a total of M times.

  The exclusive OR gate group 105 shown in FIG. 5 includes N exclusive OR gates, and receives N-bit signals output from the two shift registers 103 and 104, respectively. (12) An exclusive OR operation for 0 ≦ i <N−1 in the equation is performed in parallel, and N-bit operation result information is supplied to the adder 106 in FIG.

The adder 106 shown in FIG. 1 calculates the number of bits with a logical value of 1 in the N-bit information output from the exclusive OR gate group 105 as an unsigned integer, and doubles the calculation result. Further, by adding a sign bit to make a signed integer, the value of the second term on the right side of the above-described expression (9) as shown in the expression (14) is calculated. The calculation result by the adder 106 is provided to the subtractor 107.

FIG. 6 is a block diagram illustrating a specific configuration example of the adder 106. In FIG. 6, the adder 106 includes a first stage to an r-th unsigned integer adder and an MSB / LSB adding unit. Here, r = F (log ₂ N), the function F (x) is a sailing function, and represents the smallest integer not less than x.

  First, in the first stage, two pairs of N-bit signals are taken, input to an unsigned integer adder, and added. In FIG. 6, N is drawn as an even number, but in the case of an odd number, the remaining 1 bit after pairing is input to the next second stage. This difference in configuration due to odd / even is the same in the second and subsequent stages. Note that the number of unsigned integer adders in the first stage is N / 2 when N is an even number, and (N-1) / 2 when N is an odd number.

  The addition results of the first stage are respectively input to the unsigned integer adder of the second stage, and two pairs of additions are executed as in the first stage. Thereafter, such a process is repeatedly executed up to one r-th unsigned integer adder belonging to the stage.

Since the output of the unsigned integer adder of the r-th stage as the final stage is half of the value shown in the equation (14), and the maximum value of this value is N, this is the number of unsigned integer bits R Is converted to R = G (log ₂ N) +1. Here, G (x) is a floor function and represents the maximum integer that does not exceed x.

  By adding an LSB of “0” to the R-bit output of the r-th stage unsigned integer adder, the R-bit output of the r-th stage unsigned integer adder is doubled, and the r-th stage An MSB consisting of “0” is added to the R bit output of the unsigned integer adder of the stage to convert it to a signed integer.

  Incidentally, it is assumed that the operation of the adder 106 shown in FIG. 6 can be performed in one machine cycle from the first stage to the final stage (rth stage). However, when r increases, the processing delay in the adder 106 increases, and there is a possibility that it cannot be implemented in one machine cycle. In such a case, a register capable of holding the input signal in synchronization with the clock signal may be provided at an appropriate stage interval. That is, by using the pipeline operation in this way, the processing delay increases, but the processing throughput does not decrease, and it is possible to execute the expression (9) in M machine cycle periods.

  The subtractor 107 in FIG. 1 subtracts the output of the adder 106 (the second term on the right side of the equation (9)) from N, without particularly giving a specific configuration example. ) Expression is completely calculated.

(A-3) Effect of Embodiment [Effect 1] Small Computation A Normalized Cross-Correlation Coefficient Corr (n, k) Represented by Expression (4) of Two Discrete Time Signals X (n) and Y (n) And the normalized cross-correlation coefficient N · Corr _sgn (in equation (9) when the two discrete time signals X (n) and Y (n) are binarized in the embodiment. The calculation amount of n, k) is compared under the condition of 0 ≦ i <N and 0 ≦ k <N.

  Regarding the related art and the embodiment, when the calculation amount of the normalized cross-correlation coefficient is converted by the number of product-sum operations, it is as shown in FIG.

In FIG. 7, α appearing in the amount of calculation in the frequency domain of the prior art is a proportionality constant. This is because the calculation amount in the frequency domain is proportional to Nlog ₂ N as described in the related art. In contrast, the embodiment is exactly N times and the proportionality constant is 1.

Therefore, the above embodiment achieves a reduction of 1 / N for the calculation in the time domain of the prior art and 1 / (αlog ₂ N) for the calculation in the frequency domain, and N increases. As a result, the calculation amount becomes relatively small. For example, for N = 1024 = 2 ^10, thousandths of relative calculation in the time domain in the prior art, thereby reducing the calculation amount to several tenths of a relative calculation of the frequency domain.

[Effect 2] Elimination of Multiplication / Division / Square Root In general, when multiplication, division, and square root operations are compared with an addition operation, both the hardware scale and the processing time are smaller in the addition operation. Since the above embodiment is processed according to the equation (9), multiplication, division, and square root calculation are unnecessary, and the hardware scale, processing time, and power consumption can be reduced.

(B) Other Embodiments In the above-described embodiment, the correlation calculator is configured by hardware. However, the correlation calculator may be configured as software (correlation calculation program) executed by the CPU. Even in this case, the same effects as those of the above-described embodiment can be obtained except for the reduction of the hardware scale.

  In the description of the above embodiment, the use of the correlation calculator is not mentioned, but the present invention can be applied to various communication apparatuses and measurement apparatuses that calculate normalized cross-correlation coefficients of two types of discrete time signals.

The correlation calculator of the present invention is not limited to the one constituted by the set of components as in the above-described embodiment. In short, the input signals X (n) and Y (n) are converted into 1-bit signals X _bin (n ), Y _bin (n) after the conversion, any configuration that can execute the above-described expression (9) may be used.

In the above embodiment, after the input signals X (n) and Y (n) are converted into 1-bit signals X _bin (n) and Y _bin (n), the time difference k for calculating the correlation is considered. However, the input signal X (n), Y (n) is converted to a 1-bit signal after performing a process (for example, a process of delaying one of them) for giving a time difference k between signals for which correlation is obtained. May be. The expression of the claims does not necessarily include such a modification, but the claim covers such a modification.

It is a block diagram which shows the structure of the correlation calculator 100 of embodiment. Binary signal _X sgn embodiment _{(n), Y sgn (n} ) a and binary representation _X bin _(n), is a table illustrating the correspondence between the _{Y bin} (n). It is a _{table | surface} explaining the corresponding | compatible relationship with the binary number expression in multiplication _Xsgn ( _ni ) _Ysgn ( _nki ) of embodiment. It is a block diagram which shows the example of a specific structure of the code bit extractor 101 (and 102) in embodiment. FIG. 3 is a block diagram illustrating a specific configuration example of shift registers 103 and 104 and an exclusive OR gate group 105 in the embodiment. It is a block diagram which shows the specific structural example of the adder 106 in embodiment. It is explanatory drawing of the effect of the performance surface in embodiment.

Explanation of symbols

  100: correlation calculator, 101, 102: sign bit extractor, 103, 104: shift register, 105: exclusive OR gate group, 106: adder, 107: subtractor.

Claims (3)

In a correlation calculator for calculating a normalized cross-correlation coefficient Corr (n, k) when there is a time difference k between the two types of discrete time signals X (n) and Y (n),
First binary encoding means for converting the discrete time signal X (n) into a 1-bit signal X _bin (n) according to whether the dynamic range is less than an intermediate value, an intermediate value or an intermediate value,
Second binary encoding means for converting the discrete time signal Y (n) into a 1-bit signal Y _bin (n) depending on whether the dynamic range is less than an intermediate value, an intermediate value, or an excess of the intermediate value;
Based on the 1-bit signals X _bin (n) and Y _bin (n) from the first and second binary encoding means, an operation according to the equation (A) is executed, and the operation result is expressed as the cross-correlation coefficient. A correlation computing unit comprising: computing means for outputting as Corr (n, k).

Here, N is the number of samples of each signal used for calculating the correlation, and a symbol in which + is circled represents an exclusive OR operation. The computing means is
A first N-bit signal holding unit that holds and outputs the 1-bit signal X _bin (n) from the first binary encoding means for at least N bits required by the equation (A);
A second N-bit signal holding unit that holds and outputs the 1-bit signal Y _bin (n) from the second binary encoding means for at least N bits required by the equation (A);
An exclusive OR operation unit that performs an exclusive OR operation on a bit-by-bit basis for a total of 1-bit signals output from the first and second 1-bit signal holding means;
Converting the number of logical “1” bits from the output of the exclusive OR operation of N bits into an integer value, and a summation / doubling unit for doubling the integer value;
The correlation calculator according to claim 1, further comprising: a subtracting unit that subtracts an integer value from the sum / doubling unit from N. In the correlation calculation method for calculating the normalized cross-correlation coefficient Corr (n, k) when there is a time difference k between the two types of discrete time signals X (n) and Y (n),
A first binary encoding means, a second binary encoding means, and an arithmetic means;
The first binary encoding means converts the discrete time signal X (n) into a 1-bit signal X _bin (n) according to whether the dynamic range is less than the intermediate value, the intermediate value, or the intermediate value. ,
The second binary encoding means converts the discrete time signal Y (n) into a 1-bit signal Y _bin (n) corresponding to whether the dynamic range is less than the intermediate value, the intermediate value, or the intermediate value. ,
The arithmetic means executes an arithmetic operation according to the equation (B) based on the 1-bit signals X _bin (n) and Y _bin (n) from the first and second binary encoding means, and the arithmetic result is obtained. A correlation calculation method characterized by outputting the cross-correlation coefficient Corr (n, k).

Here, N is the number of samples of each signal used for calculating the correlation, and a symbol in which + is circled represents an exclusive OR operation.

Images