CN103885922A - Parallel processing method and system for correlation operation of discrete signals - Google Patents

Abstract

The invention is suitable for the field of processing of digital signals and provides a parallel processing method for correlation operation of discrete signals. The method includes the following steps that first, discrete signals are acquired; second, whether the signals can be directly subjected to parallel operation processing or not is judged, and the third step is executed if the signals can be directly subjected to parallel operation processing; if the signals can not be directly subjected to parallel operation processing, a long sequence is divided into two parts, one part is subjected to parallel operation processing, the third step is executed, and the other part is directly processed; third; the discrete signals are equally divided to form partitioned sequences, and the partitioned sequences are sequentially sent to corresponding parallel machines; fourth; in the parallel machines, the discrete signals are processed and subjected to operation, and weighing operation is performed on the output results; fifth, the results are merged to obtain correlation operation values. Through parallel operation processing, one problem is divided into a plurality of sub tasks, the sub tasks are allocated to different processors, the processors cooperate with one another to execute the sub tasks, and speed of correlation operation is improved, and complexity of operation is reduced.

Description

Parallel processing method and system for discrete signal correlation operation

Technical Field

The invention belongs to the field of digital signal processing, and particularly relates to a processing method and a system capable of performing parallel computation on discrete signal correlation operation.

Background

In digital signal processing, detection, identification, extraction, etc. of signals often require studying the similarity of two signals (i.e. cross-correlation), or studying the similarity of one signal to itself after a delay (i.e. auto-correlation). Correlation is a description of the degree of similarity of two sequences. The correlation operation includes linear correlation and circular correlation. The linear correlation is a degree describing synchronization or similarity or same phase between two signals or whether the change rules of the two signals have a linear relation or a nearly linear relation; circular correlation is a correlation operation with respect to a cyclic shift of a sequence. Fig. 1 illustrates the process of directly performing linear correlation operation on two sequences, and fig. 2 illustrates the process of performing a common circular correlation operation on two sequences. The complexity of the direct linear correlation operation on the sequences of respective lengths is, and the complexity of the direct circular correlation operation is. The correlation operation of two discrete time signals in the time domain is equivalent to the conjugate multiplication of the discrete Fourier transform of the two signals in the frequency domain. The complexity of performing linear correlation operation in the frequency domain using discrete fourier transform on the sequences of the respective lengths is the complexity of performing cyclic correlation, where the complexity is the same as that of performing a fast algorithm of discrete fourier transform.

Therefore, the computational complexity of the discrete fourier transform directly affects the complexity of the correlation operation.

Currently, the following methods are mainly included for calculating the discrete fourier transform:

(1) calculating discrete Fourier transform by solving simultaneous equations;

(2) calculating a discrete Fourier transform by a correlation method;

(3) calculating discrete Fourier transform by direct method (DFT);

(4) fast Fourier Transform (FFT) computing a discrete fourier transform;

(5) the sparse fourier transform (sFFT) computes a discrete fourier transform.

The method (3) is a direct algorithm, the calculation principle is easy to master, but the calculation efficiency is low, and the calculation complexity is not favorable for large-scale operation.

The method (4) is a fast and efficient implementation method of the method (3), and the calculation complexity is that the method is the mainstream method for calculating the discrete fourier transform at present.

The method (5) is a faster and more efficient discrete fourier transform calculation method than the method (4), and is due to the latest research result issued by MIT, and the calculation complexity is as follows.

Disclosure of Invention

The invention provides a parallel processing method for discrete signal correlation operation, aiming at solving the problem of low correlation operation speed.

The invention is realized in such a way that a parallel processing method of discrete signal correlation operation comprises the following steps:

A. collecting discrete signals;

B. judging whether the signals can be directly subjected to parallel computing processing, and if so, executing the step C; if the parallel computing processing can not be carried out, the longer sequence is divided into two parts, one part is carried out with the parallel computing processing, the step C is carried out, and the other part is directly processed;

C. carrying out equal division processing on the discrete signals to form component sequences, and sequentially transmitting the component sequences to corresponding parallel machines;

D. processing and calculating discrete signals in a parallel machine, and performing weighted calculation on output results;

E. and combining the results to obtain the value of the correlation operation.

The further technical scheme of the invention is as follows: the step A comprises the following steps:

a1, collecting a discrete time signal sequence and acquiring a related sequence;

and A2, carrying out zero filling operation on the two sequences in the step A1 to obtain the sequences with equal length.

The further technical scheme of the invention is as follows: the step B comprises the following steps:

b1, judging whether the two sequences need to be processed by parallel computing, if so, executing the step B2; if the parallel computing processing is not needed, executing step B3;

b2, judging whether the two sequences in B1 can be subjected to parallel computing processing, if so, executing the step C; if the parallel computing process cannot be performed, step B5 is executed;

b3, directly using discrete Fourier transform, conjugating the sequence of discrete Fourier transform to obtain corresponding elements of the result, multiplying, and executing the step B4;

b4, directly using the inverse discrete Fourier transform to calculate, and executing the step E;

b5, segmenting the longer sequence, carrying out zero filling operation on the two sequences, and executing the step B6;

b6, judging whether the calculated sequence can be processed by parallel computing, if so, executing the step C; if the parallel computing process cannot be performed, step B3 is executed;

the further technical scheme of the invention is as follows: the step D comprises the following steps:

d1, directly performing discrete Fourier transform on each sub-sequence in a parallel machine and outputting a result;

d2, carrying out weighting operation on the result output by the parallel machine in the step D1, and carrying out corresponding element multiplication operation in a frequency domain after conjugation of a sequence of the result;

d3, equally dividing the sequence processed in the step D2, transmitting the sequence to a corresponding parallel machine, and outputting the result by using inverse discrete Fourier transform;

d4, performing weighted operation on the results output by each parallel machine in the step D3.

The further technical scheme of the invention is as follows: and when the sum of the length of the discrete time signal sequence and the length of the correlation sequence minus 1 is larger than the maximum sequence length which can be processed by the system, or the correlation operation time of a new sequence with the calculated length of the discrete time signal sequence and the sum of the length of the correlation sequence minus 1 exceeds a preset time threshold, judging whether the sequence can carry out parallel operation.

The further technical scheme of the invention is as follows: the weighting operation time is in direct proportion to the number of segments of the sequence and the length of the segment sequence.

It is another object of the present invention to provide a parallel processing system for discrete signal correlation operations, the parallel processing system comprising:

the acquisition module is used for acquiring discrete signals;

the judging module is used for judging whether the signals can be directly subjected to parallel computing processing or not, and if the signals can be directly subjected to the parallel computing processing, executing the step C; if the parallel computing processing can not be carried out, the longer sequence is divided into two parts, one part is carried out with the parallel computing processing, the step C is carried out, and the other part is directly processed;

the dividing module is used for dividing the discrete signals into constituent sequences and sequentially transmitting the constituent sequences to the corresponding parallel machines;

the calculation module is used for carrying out processing operation on the discrete signals in the parallel machine and carrying out weighting operation on output results;

and the result module is used for combining the results to obtain the value of the correlation operation.

The further technical scheme of the invention is as follows: the acquisition module comprises:

the sequence acquisition unit is used for acquiring a discrete time signal sequence and acquiring a related sequence;

and a sequence zero padding unit, configured to perform zero padding operation on the two sequences in step a1 to obtain equal-length sequences.

The further technical scheme of the invention is as follows: the judging module comprises:

a primary judging unit, configured to judge whether the two sequences need to be subjected to parallel computing, and if so, execute step B2; if the parallel computing processing is not needed, executing step B3;

a secondary judgment unit, configured to judge whether the two sequences in B1 can be subjected to parallel computing processing, and if so, execute step C; if the parallel computing process cannot be performed, step B5 is executed;

a multiplication operation unit for directly using discrete Fourier transform and conjugating a sequence thereof to multiply corresponding elements of the result, and executing step B4;

a transform calculation unit for directly using the inverse discrete fourier transform calculation and performing step E;

a sequence segmentation unit, configured to segment a longer sequence, perform zero padding operation on the two sequences, and execute step B6;

a third judging unit for judging whether the calculated sequence can be processed by parallel computing, if so, executing step C; if the parallel computing process cannot be performed, step B3 is executed.

The further technical scheme of the invention is as follows: the calculation module comprises:

the discrete Fourier transform unit is used for directly carrying out discrete Fourier transform on each subsequence in the parallel machine and outputting a result;

a first weighting operation unit, configured to perform weighting operation on the result output by the parallel machine in step D1, conjugate a sequence of the first weighting operation unit, and perform multiplication operation on corresponding elements in the frequency domain;

a sequence equally dividing processing unit, which is used for equally dividing the sequence processed in the step D2, and transmitting the equally divided sequence to a corresponding parallel machine to output the result by using inverse discrete Fourier transform;

and a second weighting calculation unit, configured to perform a weighting operation on the results output by the parallel machines in step D3.

The invention has the beneficial effects that: through parallel operation processing, a problem is decomposed into a plurality of subtasks which are distributed to different processors, and the subtasks are executed by the processors in cooperation with each other, so that the speed of related operation is improved, and the complexity of operation is reduced.

Drawings

FIG. 1 is a diagram illustrating the operational process of direct linear correlation;

FIG. 2 is a flowchart illustrating a circular correlation operation;

FIG. 3 is a schematic diagram illustrating the linear correlation equivalent operation process of the present invention;

fig. 4 is a flowchart of a parallel processing method of discrete signal correlation operation according to an embodiment of the present invention.

Detailed Description

Parallel computing means that a problem is decomposed into a plurality of subtasks in a parallel machine, and the subtasks are distributed to different processors, and the processors cooperate with each other to execute the subtasks in parallel. The parallel computation is mainly to achieve the purpose of improving the speed of solving the same application or improving the problem scale of solving the same application.

Three essential conditions that can be successfully carried out by parallel computing are:

(a) a parallel machine capable of communicating with the customer service end;

(b) the application problem must be able to be decomposed into multiple subtasks, and these subtasks can be executed in parallel;

(c) parallel programming is implemented and capable of running programs that solve application problems.

At present, the calculation speed of the correlation operation is improved mainly by the calculation speed of the discrete fourier transform.

The discrete Fourier transform in the embodiment of the invention is realized by adopting a fast Fourier transform function fft in matlab; the inverse discrete Fourier transform is realized by adopting a fast inverse Fourier transform function ifft in matlab.

Fig. 4 shows a flowchart of a parallel processing method for discrete signal correlation operation provided by the present invention, which is detailed as follows:

in step S301, a discrete time signal sequence and a correlation sequence are acquired in a parallel processing system; most discrete times result from sampling a continuous-time signal, where the sampling of the continuous-time signal should satisfy the nyquist sampling theorem; such as a discrete-time signal sequence [ x (0), x (1),.., x (130) ], a related isometric sequence [ y (0), y (1),.., y (14) ].

In step S302, zero padding operation is carried out on the two sequences in the parallel processing system to obtain sequences with equal length; in the linear correlation operation, the tail of the other sequence is not added with zero of 1 number, and the cyclic correlation operation value is added with zero of the longer sequence length minus the shorter sequence length, so that only 116 zeros are added to the tail of the correlation sequence, namely the correlation sequence becomes [ y (0), x (1),.., x (14), zeros (1,116) ].

In step S303, it is determined whether the discrete time signal sequence and the correlation sequence need to be subjected to parallel computation, and if the discrete time signal sequence and the correlation sequence need to be subjected to parallel computation, step S304 is executed; if the parallel computing process is not necessary, step S305 is executed.

In step S304, it is determined whether the discrete-time signal sequence and the correlation sequence in step S303 can be subjected to parallel computing processing, and if so, step S306 is executed; if the parallel computing process cannot be performed, step S307 is executed. Whether the sequence can be subjected to parallel computing processing or not is determined according to whether the discrete-time signal sequence and the length of the correlation sequence can be equally divided, if the sequence length is 131, the sequence is a prime number and cannot be equally divided, so that the parallel computing processing cannot be directly performed.

In step S305, a discrete fourier transform is directly used and a sequence thereof is conjugated to multiply corresponding elements of the result, and step S308 is performed. Namely, it is

fft([x″(0),x″(1),...,x″(46)]).*fft([y″(0),y″(1),...,y″(46)]) The results obtained are denoted as [ W (0), W (1),. ], W (46)]. Wherein

Here N' 47.

In step S306, the discrete time signal sequence and the related sequence collected by the parallel processing system are equally divided, and the processed sequences are sequentially transmitted to corresponding parallel machines; namely, the sequence part1 and the corresponding related sequence are divided into 3 parts respectively, <math> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>0</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>3</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mrow> <mo>,</mo> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>123</mn> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>4</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>124</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>2</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>5</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>x</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>125</mn> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> </math> is marked as

<math> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msub> <mi>x</mi> <mn>0</mn> </msub> <mrow> <mo>(</mo> <mn>0</mn> <mo>)</mo> </mrow> <mo>,</mo> <msub> <mi>x</mi> <mn>0</mn> </msub> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msub> <mi>x</mi> <mn>0</mn> </msub> <mrow> <mo>(</mo> <mn>41</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>x</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mn>0</mn> <mo>)</mo> </mrow> <mrow> <mo>,</mo> <msub> <mi>x</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msub> <mi>x</mi> <mn>1</mn> </msub> <mrow> <mo>(</mo> <mn>41</mn> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>x</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mn>0</mn> <mo>)</mo> </mrow> <mo>,</mo> <msub> <mi>x</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msub> <mi>x</mi> <mn>2</mn> </msub> <mrow> <mo>(</mo> <mn>41</mn> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>,</mo> <mtable> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>0</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>3</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>123</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>4</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>124</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>2</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>5</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>125</mn> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> </mrow> </mtable> </mrow> </math> Is marked as $\left[\begin{array}{c}{y}_0\left(0\right),y_0\left(1\right),...,y_0\left(41\right)\\ y_1\left(0\right),y_1\left(1\right),...,y_1\left(41\right)\\ y_2\left(0\right),y_2\left(1\right),...,y_2\left(41\right)\end{array}\right]$ And inputting the matrixes into corresponding parallel machines respectively according to a sequence of behaviors.

In step S307, the discrete time signal sequence and the longer sequence in the correlation sequence which are determined in step S304 to be incapable of performing parallel computation are subjected to segment processing, and zero padding computation processing is performed on the two sequences; i.e. a discrete-time signal sequence is divided into two parts part1:

[ x (0), x (1),. ·, x (111), zeros (1,14) ], denoted as [ x ' (0), x ' (1),. ·, x ' (125) ], part2:

[ zeros (1,14), x (112), x (113),.., x (130), zeros (1,14) ], denoted [ x "(0), x" (1),.., x "(46) ]; the correlation sequence corresponding to part1 is zero-padded to [ y (0), y (1),. ·, y (14), zeros (1,111) ], denoted as [ y ' (0), y ' (1),.., y ' (125) ], and the conduit sequence corresponding to part2 is zero-padded to [ y (0), y (1),..,. y (14), zeros (1,32) ], denoted as [ y "(0), y" (1),. y "(46) ].

In step S308, the result of multiplying the corresponding elements in step S305 is calculated by using the inverse discrete fourier transform as it is.

In step S309, in the parallel machine, discrete fourier transform is directly performed on each subsequence; i.e. the pair sequence $\left[\begin{array}{c}{x}_0\left(0\right),x_0\left(1\right),...,x_0\left(41\right)\\ x_1\left(0\right),x_1\left(1\right),...,x_1\left(41\right)\\ x_2\left(0\right),x_2\left(1\right),...,x_2\left(41\right)\end{array}\right];$ The corresponding parallel machine processing result is $\left[\begin{array}{c}{X}_0\left(0\right),X_0\left(1\right),...,X_0\left(41\right)\\ X_1\left(0\right),X_1\left(1\right),...,X_1\left(41\right)\\ X_2\left(0\right),X_2\left(1\right),...,X_2\left(41\right)\end{array}\right]$ Sequence of $\left[\begin{array}{c}{y}_0\left(0\right),y_0\left(1\right),...,y_0\left(41\right)\\ y_1\left(0\right),y_1\left(1\right),...,y_1\left(41\right)\\ y_2\left(0\right),y_2\left(1\right),...,y_2\left(41\right)\end{array}\right]$ The corresponding parallel machine processing result is $\left[\begin{array}{c}{Y}_0\left(0\right),Y_0\left(1\right),...,Y_0\left(41\right)\\ Y_1\left(0\right),Y_1\left(1\right),...,Y_1\left(41\right)\\ Y_2\left(0\right),Y_2\left(1\right),...,Y_2\left(41\right)\end{array}\right]$ Wherein <math> <mrow> <msub> <mi>X</mi> <mi>m</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> <mo>)</mo> </mrow> <mo>=</mo> <munderover> <mi>&Sigma;</mi> <mrow> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mo>-</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>x</mi> <mi>m</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <mo>)</mo> </mrow> <msubsup> <mi>W</mi> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mrow> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> </mrow> </msubsup> <mo>,</mo> <mo>=</mo> <msub> <mi>Y</mi> <mi>m</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> <mo>)</mo> </mrow> <mo>=</mo> <munderover> <mi>&Sigma;</mi> <mrow> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mo>-</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>y</mi> <mi>m</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <mo>)</mo> </mrow> <msubsup> <mi>W</mi> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mrow> <mo>-</mo> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> </mrow> </msubsup> <mo>,</mo> </mrow> </math> Here, the <math> <mrow> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mo>=</mo> <mn>42</mn> <mo>,</mo> <mi>m</mi> <mo>=</mo> <mn>0,1,2</mn> <mo>,</mo> <msubsup> <mi>W</mi> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mrow> <mo>-</mo> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> </mrow> </msubsup> <mo>=</mo> <msup> <mi>e</mi> <mrow> <mi>j</mi> <mfrac> <mrow> <mn>2</mn> <mi>&pi;</mi> </mrow> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> </mfrac> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> </mrow> </msup> <mo>,</mo> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> <mo>=</mo> <mn>0,1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mo>-</mo> <mn>1</mn> <mo>.</mo> </mrow> </math>

In step S310, it is determined whether or not the sequence processed in step S307 can be subjected to parallel computing processing; the process proceeds to step S306 where parallel computation of part1 and its corresponding correlation sequence is possible in step S307, and proceeds to step S305 where parallel computation of part2 and its corresponding correlation sequence is not possible.

In step S311, the result output by the parallel machine in step S309 is subjected to weighting operation, and a sequence thereof is conjugated to multiply the corresponding elements; if [ x ' (0), x ' (1),...., x ' (125) ] and

the result of the direct discrete fourier transform of [ y '(0), y' (1),. ·, y '(125) ] is denoted as [ X' (0), X '(1),. ·, X' (125) ] and

[ Y ' (0), Y ' (1),.. and.Y ' (125) ], then in the weighting operation, there are

<math> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>0</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mrow> <mo>,</mo> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>42</mn> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>43</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>44</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>84</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>85</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>86</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>X</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>125</mn> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mtext>=</mtext> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <mi>sum</mi> <mrow> <mo>(</mo> <mi>X</mi> <mo>.</mo> <mo>*</mo> <msup> <mi>W</mi> <mn>0</mn> </msup> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>sum</mi> <mrow> <mo>(</mo> <mi>X</mi> <mo>.</mo> <mo>*</mo> <msup> <mi>W</mi> <mn>1</mn> </msup> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>sum</mi> <mrow> <mo>(</mo> <mi>X</mi> <mo>.</mo> <mo>*</mo> <msup> <mi>W</mi> <mn>2</mn> </msup> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>,</mo> </mrow> </math>

<math> <mrow> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>0</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>1</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mrow> <mo>,</mo> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>42</mn> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>43</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>44</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>84</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>85</mn> <mo>)</mo> </mrow> <mo>,</mo> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>86</mn> <mo>)</mo> </mrow> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>Y</mi> <mo>&prime;</mo> </msup> <mrow> <mo>(</mo> <mn>125</mn> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mtext>=</mtext> <mfenced open='[' close=']'> <mtable> <mtr> <mtd> <mi>sum</mi> <mrow> <mo>Y</mo> <mi>Y</mi> <mo>.</mo> <mo>*</mo> <msup> <mi>W</mi> <mn>0</mn> </msup> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>sum</mi> <mrow> <mo>Y</mo> <mi>Y</mi> <mo>.</mo> <mo>*</mo> <msup> <mi>W</mi> <mn>1</mn> </msup> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mi>sum</mi> <mrow> <mo>Y</mo> <mi>Y</mi> <mo>.</mo> <mo>*</mo> <msup> <mi>W</mi> <mn>2</mn> </msup> <mo>,</mo> <mn>1</mn> <mo>)</mo> </mrow> </mtd> </mtr> </mtable> </mfenced> <mo>,</mo> </mrow> </math> Where sum is the sum of the matrix columns,

$X=\left[\begin{array}{c}{X}_0\left(0\right),X_0\left(1\right),...,X_0\left(41\right)\\ X_1\left(0\right),X_1\left(1\right),...,X_1\left(41\right)\\ X_2\left(0\right),X_2\left(1\right),...,X_2\left(41\right)\end{array}\right].*\left[\begin{array}{c}{\left(W_{126}^0\right)}^0,{\left(W_{126}^1\right)}^0,...,{\left(W_{126}^{41}\right)}^0\\ {\left(W_{126}^0\right)}^1,{\left(W_{126}^1\right)}^1{,...,\left(W_{126}^{41}\right)}^1\\ {\left(W_{126}^0\right)}^2,{\left(W_{126}^1\right)}^2{,...,\left(W_{126}^{41}\right)}^2\end{array}\right],$

$Y=\left[\begin{array}{c}{Y}_0\left(0\right),Y_0\left(1\right),...,Y_0\left(41\right)\\ Y_1\left(0\right),Y_1\left(1\right),...,Y_1\left(41\right)\\ Y_2\left(0\right),Y_2\left(1\right),...,Y_2\left(41\right)\end{array}\right].*\left[\begin{array}{c}{\left(W_{126}^0\right)}^0,{\left(W_{126}^1\right)}^0,...,{\left(W_{126}^{41}\right)}^0\\ {\left(W_{126}^0\right)}^1,{\left(W_{126}^1\right)}^1{,...,\left(W_{126}^{41}\right)}^1\\ {\left(W_{126}^0\right)}^2,{\left(W_{126}^1\right)}^2{,...,\left(W_{126}^{41}\right)}^2\end{array}\right],$

$W^k=\left[\begin{array}{c}{\left(W_{126}^{42}\right)}^0,{\left(W_{126}\right)}^0,...,{\left(W_{126}^{42}\right)}^0\\ {\left(W_{126}^{42}\right)}^1,{\left(W_{126}^1\right)}^1,...,{\left(W_{126}^{42}\right)}^1\\ {\left(W_{126}^{42}\right)}^2,{\left(W_{126}^{42}\right)}^2,...,{\left(W_{126}^{42}\right)}^2\end{array}\right],k=\mathrm{0,1,2};$ is marked as

[Z(0),Z(1),...,Z(125)][X′(0),X′(1),...,X′(125)].*conj([Y′(0),Y′(1),...,Y′(125)])。

In step S312, the sequence of the multiplication results in step S311 is equally divided, and the processed sequence is transmitted to the corresponding parallel machine for processing by using the discrete fourier transform; equally divide the sequence in step S311 into $\left[\begin{array}{c}Z\left(0\right),Z\left(3\right),...,Z\left(123\right)\\ Z\left(1\right),Z\left(4\right),...,Z\left(124\right)\\ Z\left(2\right),Z\left(5\right),...,Z\left(125\right)\end{array}\right],$ Is marked as $\left[\begin{array}{c}{Z}_0\left(0\right),Z_0\left(1\right),...,Z_0\left(41\right)\\ Z_1\left(0\right),Z_1\left(1\right),...,Z_1\left(41\right)\\ Z_2\left(0\right),Z_2\left(1\right),...,Z_2\left(41\right)\end{array}\right],$ The corresponding parallel machine processing result is $\left[\begin{array}{c}{z}_0\left(0\right),z_0\left(1\right),...,z_0\left(41\right)\\ z_1\left(0\right),z_1\left(1\right),...,z_1\left(41\right)\\ z_2\left(0\right),z_2\left(1\right),...,z_2\left(41\right)\end{array}\right];$ Wherein <math> <mrow> <msub> <mi>z</mi> <mi>m</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> <mo>)</mo> </mrow> <mo>=</mo> <mfrac> <mn>1</mn> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> </mfrac> <munderover> <mi>&Sigma;</mi> <mrow> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mo>-</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>Z</mi> <mi>m</mi> </msub> <mrow> <mo>(</mo> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <mo>)</mo> </mrow> <msubsup> <mi>W</mi> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mrow> <mo>-</mo> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> </mrow> </msubsup> <mo>,</mo> </mrow> </math> Herein, the <math> <mrow> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mo>=</mo> <mn>42</mn> <mo>,</mo> <mi>m</mi> <mo>=</mo> <mn>0,1,2</mn> <mo>,</mo> <msubsup> <mi>W</mi> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mrow> <mo>-</mo> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> </mrow> </msubsup> <mo>=</mo> <msup> <mi>e</mi> <mrow> <mi>j</mi> <mfrac> <mrow> <mn>2</mn> <mi>&pi;</mi> </mrow> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> </mfrac> <msup> <mi>n</mi> <mo>&prime;</mo> </msup> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> </mrow> </msup> <mo>,</mo> <msup> <mi>k</mi> <mo>&prime;</mo> </msup> <mo>=</mo> <mn>0,1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>N</mi> <mo>&prime;</mo> </msup> <mo>-</mo> <mn>1</mn> <mo>.</mo> </mrow> </math>

In step S313, the results output from the parallel machines in step S312 are subjected to a weighting operation, for example, $\left[\begin{array}{c}z\left(0\right),z\left(1\right),...,z\left(42\right)\\ z\left(43\right),z\left(44\right),...,z\left(84\right)\\ z\left(85\right),z\left(86\right),...,z\left(125\right)\end{array}\right]=\left[\begin{array}{c}\frac{1}{3}\mathrm{sum}(z.*W^0,1)\\ \frac{1}{3}\mathrm{sum}(z.*W^{-1},1)\\ \frac{1}{3}\mathrm{sum}(z.*W^{-2},1)\end{array}\right];$ wherein

$z=\left[\begin{array}{c}{z}_0\left(0\right),\left(1\right),...,z_0\left(41\right)\\ z_1\left(0\right),\left(1\right),...,z_1\left(41\right)\\ z_2\left(0\right),\left(1\right),...,z_2\left(41\right)\end{array}\right].*\left[\begin{array}{c}{\left(W_{126}^0\right)}^0,{\left(W_{126}^{-1}\right)}^0,...,{\left(W_{126}^{-41}\right)}^0\\ {\left(W_{126}^0\right)}^1,{\left(W_{126}^{-1}\right)}^1,...,{\left(W_{126}^{-41}\right)}^1\\ {\left(W_{126}^0\right)}^2,{\left(W_{126}^{-1}\right)}^2,...,{\left(W_{126}^{-41}\right)}^2\end{array}\right].$

In step S314, the result in step S313 and the result in step S308 are merged to obtain a value of correlation operation; performing a merging operation on the results output in step S313 and step S308, where the sequences [ z (0), z (1),.. times, z (125) ] and [ w (0), w (1),. times, w (46) ] are merged to obtain:

[z(0),z(1),...,z(97),z(98)＋w(0),z(99)＋w(1),...,z(111)＋w(13),w(14),...,w(18),z(112)＋w(19),z(113)＋z(20),...,z(125)＋z(32)]is denoted as [ r (0), r (1),.. ], r (130)](ii) a Wherein,

the cyclic correlation value is a value which is equivalent to the direct cyclic correlation of the discrete time signal sequence and the correlation sequence; where mod denotes k + N modulo N.

The invention provides a parallel algorithm for calculating correlation operation from the aims of improving the correlation operation speed and aiming at the performance limitation of the existing processor, thereby realizing the correlation operation of the signal sequence and the correlation sequence with the minimum calculation amount.

When the sum of the length of the discrete time signal sequence to be processed and the length of the correlation sequence minus 1 is larger than the maximum sequence length which can be processed by the system, or the correlation operation time of a new sequence with the calculated length of the system being the sum of the length of the discrete time signal sequence and the length of the correlation sequence minus 1 exceeds a preset time threshold, judging whether the sequence can directly carry out parallel operation; if the parallel computing processing can be directly carried out, the sequence is subjected to segmentation processing by using discrete Fourier parallel computing to obtain sequences with preset number of segments and equal length, wherein the length of the segments cannot exceed the maximum sequence length which can be processed by the system, and the processing time cannot exceed a time threshold;

directly carrying out discrete Fourier transform on the sequence in the discrete Fourier parallel computation;

the discrete fourier transform can be calculated by using a conventional Fast Fourier Transform (FFT) or a sparse fourier transform (sFFT) as required.

The parallel processing system carries out weighting operation on the corresponding discrete Fourier transform result of the segmented sequence by using a weighting operation module to obtain a corresponding segmented weighting result; in addition, the weighting operation needs to use the corresponding segmentation information output in all the parallel machines, so the operation time of the weighting operation module is proportional to the number of segments of the sequence and the length of the segment sequence.

The parallel processing system uses a point multiplication operation module to conjugate the transformation result of the corresponding related sequence of the two sequences output by the weighting operation module, and then multiplies the corresponding elements in the two sequences to obtain a new sequence, wherein the length of the new sequence is the sum of the length of the discrete time signal sequence and the length of the related sequence minus 1.

The parallel processing system directly performs inverse discrete Fourier transform on the sequence by using an inverse discrete Fourier parallel computing module for the result output by the point multiplication operation module;

the Discrete Fourier Transform (DFT) calculation formula for the sequence x (n) is:

<math> <mrow> <mi>X</mi> <mrow> <mo>(</mo> <mi>k</mi> <mo>)</mo> </mrow> <mo>=</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>n</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>N</mi> <mo>-</mo> <mn>1</mn> </mrow> </munderover> <mi>x</mi> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> <msubsup> <mi>W</mi> <mi>N</mi> <mi>nk</mi> </msubsup> <mo>,</mo> <mi>k</mi> <mo>=</mo> <mn>0,1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>N</mi> <mo>-</mo> <mn>1</mn> <mo>,</mo> </mrow> </math> wherein <math> <mrow> <msubsup> <mi>W</mi> <mi>N</mi> <mi>nk</mi> </msubsup> <mo>=</mo> <msup> <mi>e</mi> <mrow> <mo>-</mo> <mi>j</mi> <mfrac> <mrow> <mn>2</mn> <mi>&pi;</mi> </mrow> <mi>N</mi> </mfrac> <mi>nk</mi> </mrow> </msup> <mo>,</mo> </mrow> </math> And its corresponding Inverse Discrete Fourier Transform (IDFT) calculation formula is: <math> <mrow> <mi>x</mi> <mrow> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> <mo>=</mo> <mfrac> <mn>1</mn> <mi>N</mi> </mfrac> <munderover> <mi>&Sigma;</mi> <mrow> <mi>n</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>N</mi> <mo>-</mo> <mn>1</mn> </mrow> </munderover> <mi>X</mi> <mrow> <mo>(</mo> <mi>k</mi> <mo>)</mo> </mrow> <msubsup> <mi>W</mi> <mi>N</mi> <mi>nk</mi> </msubsup> <mo>,</mo> <mi>k</mi> <mo>=</mo> <mn>0,1</mn> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>N</mi> <mo>-</mo> <mn>1</mn> <mo>,</mo> </mrow> </math> wherein

<math> <mrow> <msubsup> <mi>W</mi> <mi>N</mi> <mrow> <mo>-</mo> <mi>nk</mi> </mrow> </msubsup> <mo>=</mo> <msup> <mi>e</mi> <mrow> <mo>-</mo> <mi>j</mi> <mfrac> <mrow> <mn>2</mn> <mi>&pi;</mi> </mrow> <mi>N</mi> </mfrac> <mi>nk</mi> </mrow> </msup> <mo>,</mo> </mrow> </math> Therefore, the inverse discrete fourier transform also includes a commonly used fast inverse fourier transform (IFFT) or sparse inverse fourier transform (sfft) calculation method.

And after the result output by the inverse discrete Fourier parallel computing module passes through the weighting operation module, the obtained result is the related operation value of the two sequences. If the two sequences can not be directly processed by parallel computing, the longer sequence is divided into two parts, one part is processed by parallel computing, and the other part is directly processed. The equivalent partial operations describing the related operations are mature at present, and related data can be consulted. Two discrete signals are utilized to carry out correlation operation in a time domain, namely after the two signals are subjected to discrete Fourier transform, one sequence is subjected to conjugation, and then multiplication operation is carried out in a frequency domain.

Thus, the equivalent operation of linear correlation between the sequences x and y is:

IDFT (DFT ([ x, zeros (1, M-1) ])) conj (DFT ([ y, zeros (1, N-1) ])), wherein N, M represents the length of sequences x and y, respectively, [ x, zeros (1, M-1) ] represents the M-1 zeros added after sequence x,

[ y, zeros (1, N-1) ] indicates that N-1 zeros are added after the sequence y, conj indicates the conjugation operation on the sequence, and.

The equivalent fourier transform operation process of the direct linear correlation operation is described as fig. 3, so that the result of the equivalent fourier transform operation needs to be processed by a combining operation to be completely equivalent to the direct linear correlation operation, and the processing process of the combining operation is given by a specific embodiment.

The equivalent operation of circular correlation of the sequences x and y is as follows:

IDFT (DFT (x) · conj (DFT ([ y, zeros (1, N-M) ])), where N ≧ M.

The equivalent fourier transform operation process of the direct circular correlation operation is as described in fig. 2, and the two are completely equivalent.

The equivalent operation of linear convolution by the sequences x and y is:

the equivalent operation of IDFT (DFT ([ x, zeros (1, M-1) ])) versus DFT ([ y, zeros (1, N-1) ]), cyclic convolution is: IDFT (DFT (x) · DFT ([ y, zeros (1, N-M) ])) here only uses the parallel computing property of DFT, so the present invention is equally applicable to convolution operations.

The invention provides a parallel algorithm for calculating correlation operation, aiming at improving the correlation operation speed and aiming at the performance limitation of the existing processor, thereby realizing the correlation operation of the sequence with the minimum calculation amount.

It is another object of the present invention to provide a parallel processing system for discrete signal correlation operations, the parallel processing system comprising:

the acquisition module is used for acquiring discrete signals;

the judging module is used for judging whether the signals can be directly subjected to parallel computing processing or not, and if the signals can be directly subjected to the parallel computing processing, executing the step C; if the parallel computing processing can not be carried out, the longer sequence is divided into two parts, one part is carried out with the parallel computing processing, the step C is carried out, and the other part is directly processed;

the dividing module is used for dividing the discrete signals into constituent sequences and sequentially transmitting the constituent sequences to the corresponding parallel machines;

the calculation module is used for carrying out processing operation on the discrete signals in the parallel machine and carrying out weighting operation on output results;

and the result module is used for combining the results to obtain the value of the correlation operation.

The acquisition module comprises:

the sequence acquisition unit is used for acquiring a discrete time signal sequence and acquiring a related sequence;

and a sequence zero padding unit, configured to perform zero padding operation on the two sequences in step a1 to obtain equal-length sequences.

The judging module comprises:

a primary judging unit, configured to judge whether the two sequences need to be subjected to parallel computing, and if so, execute step B2; if the parallel computing processing is not needed, executing step B3;

a secondary judgment unit, configured to judge whether the two sequences in B1 can be subjected to parallel computing processing, and if so, execute step C; if the parallel computing process cannot be performed, step B5 is executed;

a multiplication operation unit for directly using discrete Fourier transform and conjugating a sequence thereof to multiply corresponding elements of the result, and executing step B4;

a transform calculation unit for directly using the inverse discrete fourier transform calculation and performing step E;

a sequence segmentation unit, configured to segment a longer sequence, perform zero padding operation on the two sequences, and execute step B6;

a third judging unit for judging whether the calculated sequence can be processed by parallel computing, if so, executing step C; if the parallel computing process cannot be performed, step B3 is executed.

The calculation module comprises:

the discrete Fourier transform unit is used for directly carrying out discrete Fourier transform on each subsequence in the parallel machine and outputting a result;

a first weighting operation unit, configured to perform weighting operation on the result output by the parallel machine in step D1, conjugate a sequence of the first weighting operation unit, and perform multiplication operation on corresponding elements in the frequency domain;

a sequence equally dividing processing unit, which is used for equally dividing the sequence processed in the step D2, and transmitting the equally divided sequence to a corresponding parallel machine to output the result by using inverse discrete Fourier transform;

and a second weighting calculation unit, configured to perform a weighting operation on the results output by the parallel machines in step D3.

The above description is only for the purpose of illustrating the preferred embodiments of the present invention and is not to be construed as limiting the invention, and any modifications, equivalents and improvements made within the spirit and principle of the present invention are intended to be included within the scope of the present invention.

Claims (10)

1. A method for parallel processing of discrete signal correlation operations, the method comprising the steps of:

A. collecting discrete signals;

B. judging whether the signals can be directly subjected to parallel computing processing, and if so, executing the step C; if the parallel computing processing can not be carried out, the longer sequence is divided into two parts, one part is carried out with the parallel computing processing, the step C is carried out, and the other part is directly processed;

C. carrying out equal division processing on the discrete signals to form component sequences, and sequentially transmitting the component sequences to corresponding parallel machines;

D. processing and calculating discrete signals in a parallel machine, and performing weighted calculation on output results;

E. and combining the results to obtain the value of the correlation operation.

2. A parallel processing method according to claim 1, wherein said step a comprises the steps of:

a1, collecting a discrete time signal sequence and acquiring a related sequence;

and A2, carrying out zero filling operation on the two sequences in the step A1 to obtain the sequences with equal length.

3. A parallel processing method according to claim 2, wherein said step B comprises the steps of:

b1, judging whether the two sequences need to be processed by parallel computing, if so, executing the step B2; if the parallel computing processing is not needed, executing step B3;

b2, judging whether the two sequences in B1 can be subjected to parallel computing processing, if so, executing the step C; if the parallel computing process cannot be performed, step B5 is executed;

b3, directly using discrete Fourier transform, conjugating the sequence of discrete Fourier transform to obtain corresponding elements of the result, multiplying, and executing the step B4;

b4, directly using the inverse discrete Fourier transform to calculate, and executing the step E;

b5, segmenting the longer sequence, carrying out zero filling operation on the two sequences, and executing the step B6;

b6, judging whether the calculated sequence can be processed by parallel computing, if so, executing the step C; if the parallel computing process cannot be performed, step B3 is executed.

4. A parallel processing method according to claim 2, wherein said step D comprises the steps of:

d1, directly performing discrete Fourier transform on each sub-sequence in a parallel machine and outputting a result;

d2, carrying out weighting operation on the result output by the parallel machine in the step D1, and carrying out corresponding element multiplication operation in a frequency domain after conjugation of a sequence of the result;

d3, equally dividing the sequence processed in the step D2, transmitting the sequence to a corresponding parallel machine, and outputting the result by using inverse discrete Fourier transform;

d4, performing weighted operation on the results output by each parallel machine in the step D3.

5. A parallel processing method according to claim 4, wherein when the sum of the length of the discrete time signal sequence and the length of the correlation sequence minus 1 is greater than the maximum sequence length that can be processed by the system, or the correlation operation time of a new sequence whose calculated length is the sum of the length of the discrete time signal sequence and the length of the correlation sequence minus 1 exceeds a preset time threshold, it is determined whether the sequence can be operated in parallel.

6. A parallel processing method according to claim 5, wherein the weighting operation time is proportional to the number of segments of the sequence and the length of the sequence of segments.

7. A parallel processing system for discrete signal correlation operations, the parallel processing system comprising:

the acquisition module is used for acquiring discrete signals;

the judging module is used for judging whether the signals can be directly subjected to parallel computing processing or not, and if the signals can be directly subjected to the parallel computing processing, executing the step C; if the parallel computing processing can not be carried out, the longer sequence is divided into two parts, one part is carried out with the parallel computing processing, the step C is carried out, and the other part is directly processed;

the dividing module is used for dividing the discrete signals into constituent sequences and sequentially transmitting the constituent sequences to the corresponding parallel machines;

the calculation module is used for carrying out processing operation on the discrete signals in the parallel machine and carrying out weighting operation on output results;

and the result module is used for combining the results to obtain the value of the correlation operation.

8. A parallel processing system according to claim 7, wherein the acquisition module comprises:

the sequence acquisition unit is used for acquiring a discrete time signal sequence and acquiring a related sequence;

and a sequence zero padding unit, configured to perform zero padding operation on the two sequences in step a1 to obtain equal-length sequences.

9. A parallel processing system according to claim 8, wherein said determining module comprises:

a primary judging unit, configured to judge whether the two sequences need to be subjected to parallel computing, and if so, execute step B2; if the parallel computing processing is not needed, executing step B3;

a secondary judgment unit, configured to judge whether the two sequences in B1 can be subjected to parallel computing processing, and if so, execute step C; if the parallel computing process cannot be performed, step B5 is executed;

a multiplication operation unit for directly using discrete Fourier transform and conjugating a sequence thereof to multiply corresponding elements of the result, and executing step B4;

a transform calculation unit for directly using the inverse discrete fourier transform calculation and performing step E;

a sequence segmentation unit, configured to segment a longer sequence, perform zero padding operation on the two sequences, and execute step B6;

a third judging unit for judging whether the calculated sequence can be processed by parallel computing, if so, executing step C; if the parallel computing process cannot be performed, step B3 is executed.

10. A parallel processing system according to claim 9, wherein the computation module comprises:

the discrete Fourier transform unit is used for directly carrying out discrete Fourier transform on each subsequence in the parallel machine and outputting a result;

a first weighting operation unit, configured to perform weighting operation on the result output by the parallel machine in step D1, conjugate a sequence of the first weighting operation unit, and perform multiplication operation on corresponding elements in the frequency domain;

a sequence equally dividing processing unit, which is used for equally dividing the sequence processed in the step D2, and transmitting the equally divided sequence to a corresponding parallel machine to output the result by using inverse discrete Fourier transform;

and a second weighting calculation unit, configured to perform a weighting operation on the results output by the parallel machines in step D3.

Images