METHOD FOR FILTERING A NUMERICAL INPUT SIGNAL AND ASSOCIATED FILTER

Abstract

A signal filtering method for filtering a numerical input signal that is sampled at a sampling frequency in order to obtain a filtered signal, the method including a first operation of application of a discrete Fourier transform to M points on a processed signal in order to obtain M points of the spectrum of the processed signal, each point of the spectrum of the processed signal corresponding to the even-numbered indices of a spectral analysis at 2*M points of the processed signal and a second operation of application of a discrete Fourier transform to M points on the processed signal in order to obtain M points of the spectrum of the processed signal, each point of the spectrum of the processed signal corresponding to the odd-numbered indices of a spectral analysis at 2*M points of the processed signal.

Claims

1. A signal filtering method for filtering a numerical input signal that is sampled at a sampling frequency in order to obtain a filtered signal, the method including: the provision of an input signal, the transmission of the input signal over two channels, the obtaining of a first output signal through the implementation of the following first operations on the first channel: first processing of the input signal in order to obtain a processed signal application of a discrete Fourier transform to M points on the processed signal in order to obtain M points of the spectrum of the processed signal, M being an integer that is strictly greater than 2, each point of the spectrum of the processed signal corresponding to the even-numbered indices of a spectral analysis at 2*M points of the processed signal and being indicated in a bijective manner by an index k, with k being an even number occurring between 0 and 2*M−1; second processing of the points of the spectrum of the processed signal in order to obtain the first selected points application of the inverse discrete Fourier transform to M points on the first selected points in order to obtain a first signal third processing of the first signal in order to obtain a first output signal the obtaining of a second output signal through the implementation of the following second operations on the second channel: first processing of the input signal in order to obtain a processed signal application of a discrete Fourier transform to M points on the processed signal in order to obtain M points of the spectrum of the processed signal, M being an integer that is strictly greater than 2, each point of the spectrum of the processed signal corresponding to the odd-numbered indices of a spectral analysis at 2*M points of the processed signal and being indicated in a bijective manner by an index k, with k being an odd number occurring between 0 and 2*M−1; second processing of the points of the spectrum of the processed signal in order to obtain the second selected points application of the inverse discrete Fourier transform to M points on the second selected points in order to obtain a second signal third processing of the second signal in order to obtain a second output signal the recombination of the first output signal and the second output signal in order to obtain the filtered signal.

2. A signal filtering method according to claim 1, in which: the second operation of first processing includes the carrying out of a frequency translation of a value equal to the ratio between the frequency of sampling and the number 2*M and the second operation of third processing includes the carrying out of a frequency translation applied to the second signal of a value equal to the opposite of the ratio between the frequency of sampling and the number 2*M.

3. A signal filtering method according to claim 1, in which: the first operation of second processing includes the implementation of the shifting of points of the spectrum of the processed signal by M samples in order to obtain shifted points and the calculation of the sum of points of the spectrum of the processed signal and the shifted points and the second operation of second processing includes the implementation of the shifting of points of the spectrum of the processed signal by M samples in order to obtain shifted points and the calculation of the sum of points of the spectrum of the processed signal and the shifted points.

4. A signal filtering method according to claim 1, in which: the first operation of first processing includes the implementation of the shifting of the input signal by M samples in order to obtain a shifted signal and the calculation of the sum of the input signal and the shifted signal and the second operation of first processing includes the implementation of the shifting of the input signal by M samples in order to obtain a shifted signal and the calculation of the difference between the input signal and the shifted signal.

5. A signal filtering method according to claim 1, in which the step of recombination is carried out by calculation of the difference between the first output signal and the second output signal.

6. A signal filtering method according to claim 1, in which the step of recombination is carried out by: calculation of the difference between the first output signal and the second output signal, in order to obtain a first calculation signal calculation of the sum of the first output signal and the second output signal in order to obtain a second intermediate calculation signal shifting of the second intermediate calculation signal by M samples in order to obtain a second calculation signal and calculation of the sum of the first calculation signal and the second calculation signal in order to obtain the filtered signal.

7. A filter that is capable of filtering a numerical input signal that is sampled at a sampling frequency in order to obtain a filtered signal, the filter including: an input terminal that is capable of receiving an input signal a first channel that is capable of obtaining a first output signal through the implementation of the first operations a second channel that is capable of obtaining a second output signal through the implementation of the second operations a transmitter that is capable of transmitting the input signal on the first channel and the second channel. a mixer that is capable of recombining the first output signal and the second output signal in order to obtain the filtered signal the first channel being capable of implementing the following first operations: first processing of the input signal in order to obtain a processed signal application of a discrete Fourier transform to M points on the processed signal in order to obtain M points of the spectrum of the processed signal, M being an integer that is strictly greater than 2, each point of the spectrum of the processed signal corresponding to the even-numbered indices of a spectral analysis at 2*M points of the processed signal and being indicated in a bijective manner by an index k, with k being an even number occurring between 0 and 2*M−1; second processing of the points of the spectrum of the processed signal in order to obtain the first selected points application of the inverse discrete Fourier transform to M points on the first selected points in order to obtain a first signal third processing of the first signal in order to obtain a first output signal and the second channel is capable of implementing the following second operations: first processing of the input signal in order to obtain a processed signal application of a discrete Fourier transform to M points on the processed signal in order to obtain M points of the spectrum of the processed signal, M being an integer that is strictly greater than 2, each point of the spectrum of the processed signal corresponding to the odd-numbered indices of a spectral analysis at 2*M points of the processed signal and being indicated in a bijective manner by an index k, with k being an odd number occurring between 0 and 2*M−1; second processing of the points of the spectrum of the processed signal in order to obtain the second selected points application of the inverse discrete Fourier transform to M points on the second selected points in order to obtain a second signal third processing of the second signal in order to obtain a second output signal.

8. A processing chain that comprises at least one filter according to claim

9. A processing chain according to claim 8, the processing chain being a programmable logic circuit or an application-specific integrated circuit.

10. A radar that includes a processing chain according to claim 8.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0025] Other characteristic features and advantages of the invention will become apparent upon reviewing the description that follows of embodiments of the invention, provided by way of example only and with reference being made to the drawings, which include:

[0026] FIG. 1, a schematic view of an example of a radar including a plurality of filters

[0027] FIG. 2, a block diagram showing the operations carried out by an example of a filter;

[0028] FIG. 3, a block diagram showing the operations carried out by another example of a filter;

[0029] FIG. 4, a block diagram showing the operations carried out by yet another example of a filter; and

[0030] FIG. 5, a block diagram illustrating the proper operation of the filter shown in FIG. 4.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0031] A radar 10 is schematically illustrated in FIG. 1.

[0032] The radar 10 is capable of receiving an input signal 10E and of converting the input signal 10E into an output signal 10S that may be exploited for future uses.

[0033] The radar 10 includes an antenna 12 and a processing chain 14.

[0034] The antenna 12 is capable of receiving the input signal 10E.

[0035] The processing chain 14 is capable of ensuring the conversion of the input signal 10E into the output signal 10S.

[0036] The processing chain 14 is capable of carrying out the filtering of the input signal 10E.

[0037] According to the example shown in FIG. 1, the processing chain 14 includes three filters 16, 18 and 20 arranged in series.

[0038] In fact, the first 16 filter includes an input terminal 16E connected to the antenna 12 by a first wire 22 and an output terminal 16S connected to the second filter 18 by a second wire 24.

[0039] The second filter 18 includes an input terminal 18E connected to the output terminal 16S of the first filter 16 by the second wire 24 and an output terminal 18S connected to the third filter 20 by a third wire 26.

[0040] The third filter 20 includes an input terminal 20E connected to the output terminal 18S of the second filter 18 by the third wire 26 and an output terminal 20S connected to the fourth wire 28 that transmits the output signal 10S.

[0041] According to another embodiment, the processing chain 14 includes a single filter.

[0042] By way of a variant, the processing chain 14 includes any number whatsoever of filters, for example 2, 4 or 6.

[0043] The processing chain 14 is, for example, a programmable logic circuit. Such a circuit is often referred to by the abbreviation FPGA, abbreviating the commonly accepted term “field-programmable gate array”, gate array that is capable of being reprogrammed in the field after manufacture.

[0044] According to another example, the processing chain 14 is an integrated circuit specific to a given application. Such a circuit is often referred to by the acronym ASIC (abbreviating the commonly accepted term “application-specific integrated circuit”, meaning “an integrated circuit specific to a given application”).

[0045] Each filter 16, 18 and 20 is capable of filtering a numerical input signal that is sampled at a sampling frequency in order to obtain a filtered signal.

[0046] To simplify the description, it is assumed that the filters 16, 18 and 20 are identical to each other.

[0047] By way of a variant, each filter in the processing chain 14 is different.

[0048] An example of a second filter 18 is more precisely illustrated in FIG. 2.

[0049] The filter 18 includes a first channel 181, a second channel 182, a transmitter 183 and 184 a mixer.

[0050] The input terminal 18E is capable of receiving an input signal.

[0051] The first channel 181 is capable of obtaining a first output signal through the implementation of the first operations.

[0052] The first channel 181 is capable of carrying out a first operation of first processing of the input signal in order to obtain a processed signal.

[0053] According to the example represented in FIG. 2, the first processing is the sending of the input signal.

[0054] The first channel 181 is also capable of applying a discrete Fourier transform to M points on the processed signal in order to obtain M points of the spectrum of the processed signal, M being an integer that is strictly greater than 2, each point of the spectrum of the processed signal corresponding to the even-numbered indices of a spectral analysis at 2*M points of the processed signal and being indicated in a bijective manner by an index k, with k being an even number occurring between 0 and 2*M−1. In this case, the points are numbered from 0 to 2*M−1.

[0055] This amounts to calculating the even-numbered coefficients from the spectral analysis at 2*M points of the processed signal.

[0056] For example, the discrete Fourier transform computed is a noted fast Fourier transform denoted as FFT.sub.M. This is illustrated schematically in FIG. 2 by a box in which FFT.sub.M is inscribed and by a multiplier on which is shown an incoming arrow arriving with the inscription “ρ2 m”.

[0057] The first channel 181 is also capable of carrying out a first operation of second processing of the points of the spectrum of the processed signal in order to obtain the first selected points.

[0058] The first channel 181 is capable of carrying out the shifting of points of the spectrum of the processed signal by M samples in order to obtain shifted points and the calculation of the sum of points of the spectrum of the processed signal and the shifted points.

[0059] The shifting is illustrated schematically in FIG. 2 by a box in which “z.sup.M ” is inscribed by way of reference to a technique of shifting by use of the Z transform.

[0060] A sum sign on which two incoming arrows are shown arriving, one corresponding to a path that passes through the box in which “z.sup.M ” is inscribed and the other corresponding to a path that does not pass there-through schematically shows the first operation of second processing.

[0061] The first channel 181 is also capable of carrying out a first operation of application of the inverse discrete Fourier transform to M points on the first selected points in order to obtain a first signal.

[0062] For example, the discrete Fourier transform computed is a Fast Fourier transform denoted as IFFT.sub.M.

[0063] This is illustrated schematically in FIG. 2 by a box in which IFFT.sub.M is inscribed.

[0064] The first channel 181 is also capable of carrying out a first operation of third processing of the first signal in order to obtain a first output signal.

[0065] In this case, the first operation of the third processing consists of transmitting the first output signal to the mixer 184.

[0066] The second channel 182 is capable of obtaining a second output signal through the implementation of second operations.

[0067] The second channel 182 is capable of implementing a second operation of first processing of the input signal in order to obtain a processed signal.

[0068] In this case, the second channel 182 is capable of implementing a frequency translation of a value equal to the ratio between the frequency of sampling and the number 2*M.

[0069] Such an operation is symbolized by an arrow on a multiplier, this being an arrow on which is inscribed “e .sup.−jπn/M” by way of reference to a commonly used translation technique that consists of multiplying the signal by a complex exponential that is appropriately chosen.

[0070] The second channel 182 is capable of implementing a second operation of application of a discrete Fourier transform to M points on the processed signal in order to obtain M points of the spectrum of the processed signal, each point of the spectrum of the processed signal corresponding to the odd-numbered indices of a spectral analysis at 2*M points of the processed signal and being indicated in a bijective manner by an index k, with k being an odd number occurring between 0 and 2*M−1.

[0071] The second channel 182 is capable of implementing a second operation of second processing of the points of the spectrum of the processed signal in order to obtain the second selected points.

[0072] The second channel 182 is capable of carrying out the shifting of points of the spectrum of the processed signal by M samples in order to obtain shifted points and the calculation of the sum of the points of the spectrum of the processed signal and the shifted points. From the point of view of the signal, the shifting is a time delay.

[0073] The shifting is illustrated schematically in FIG. 2 by a box in which “z.sup.M” is inscribed by way of reference to a technique of shifting by use of the Z transform.

[0074] A sum sign on which two incoming arrows are shown arriving, one corresponding to a path that passes through the box in which “z.sup.M” is inscribed and the other corresponding to a path that does not pass there-through schematically shows the second operation of second processing.

[0075] The second channel 182 is also capable of carrying out a second operation of application of the inverse discrete Fourier transform to M points on the second selected points in order to obtain a second signal.

[0076] The second channel 182 is also capable of carrying out a second operation of third processing of the second signal in order to obtain a second output signal.

[0077] In this case, the second channel 182 is capable of carrying out of a frequency translation of a value equal to the opposite of the ratio between the frequency of sampling and the number 2*M.

[0078] Such an operation is symbolized by an arrow on a multiplier, this being an arrow on which is inscribed “e.sup.juπn/m” by way of reference to a common used translation technique that consists of multiplying the signal by a complex exponential that is appropriately chosen.

[0079] The transmitter 183 is capable of transmitting the input signal on the first channel 181 and the second channel 182.

[0080] The mixer 184 is capable of recombining the first output signal and the second output signal in order to obtain the filtered signal.

[0081] In this case, since the recombination is achieved by computing a difference between the first output signal and the second output signal, the mixer 184 is represented by a circle with a +sign and a −sign.

[0082] The operation of the second filter 18 will now be described with reference made to an example of implementation of a signal filtering method for filtering a numerical input signal that is sampled at a sampling frequency in order to obtain a filtered signal.

[0083] The method includes a step of provision, a step of transmission, a signal obtaining step for obtaining a first output signal, a signal obtaining step for obtaining a second output signal, and a step of recombination.

[0084] During the step of provision, the input signal is supplied on the input terminal 18 of the second filter 18.

[0085] During the step of transmission, the input signal is transmitted by the transmitter 183 on the two channels 181 and 182.

[0086] During the signal obtaining step for obtaining the first output signal, it is necessary to calculate the fast Fourier transform at M points of the input signal in order to obtain the even order coefficients of a spectral analysis at 2*M points of the input signal.

[0087] Thereafter the process involves a first operation of carrying out the shifting of points of the spectrum of the processed signal by M samples in order to obtain shifted points and the calculation of the sum of points of the spectrum of the processed signal and the shifted points. The first selected points are thereby obtained.

[0088] This is then followed by a subsequent application of the inverse discrete Fourier transform to M points on the first selected points in order to obtain a first output signal.

[0089] The first output signal is sent to the transmitter 183.

[0090] During the step of obtaining the second output signal, it is necessary to carry out a frequency translation of a value equal to the ratio between the frequency of sampling and the number 2*M. A processed signal is thus obtained.

[0091] It is necessary to calculate the fast Fourier transform at M points of the processed signal in order to obtain the odd order coefficients of a spectral analysis at 2*M points of the input signal.

[0092] It is then necessary to carry out a second operation of implementation of the shifting of points of the spectrum of the processed signal by M samples in order to obtain shifted points and the calculation of the sum of points of the spectrum of the processed signal and the shifted points. The second selected points are thus obtained.

[0093] This is then followed by a subsequent application of the inverse discrete Fourier transform to M points on the second selected points in order to obtain a second signal.

[0094] This is then followed by subsequently carrying out the implementation of a frequency translation applied to the second signal of a value equal to the opposite of the ratio between the frequency of sampling and the number 2*M. This makes it possible to obtain an output signal.

[0095] The recombination step is then carried out with the use of the mixer 184 in order to obtain the filtered signal by computing the difference between the first output signal and the second output signal.

[0096] The method provides the ability to obtain a filtered signal in an easier manner.

[0097] In fact, the said method, as compared to a method known in the state of the art, provides the ability to limit the memory space required by 40% as is demonstrated in commenting on FIG. 5.

[0098] In addition, it is also possible to consolidate the calculations since the two channels 181 and 182 are synchronous.

[0099] By way of a variant, the second filter 18 is in accordance with the embodiment represented in FIG. 3.

[0100] The elements that are identical to those in the embodiment represented in FIG. 2 have not been described again. Only the differences have been highlighted.

[0101] The second filter 18 according to the embodiment represented in FIG. 3 differs from the second filter 18 according to the embodiment represented in FIG. 2 by way of the operations that first channel 181 and the second channel 182 are capable of carrying out and in terms of the nature of the operations carried out during the step of recombination.

[0102] In the case of FIG. 3, each of the first operations of first processing and second processing consists of transmitting the relevant signal being considered.

[0103] In the case of FIG. 3, the second operation of first processing includes the carrying out of a frequency translation of a value equal to the ratio between the frequency of sampling and the number 2*M.

[0104] The second processing consists of transmitting the relevant signal being considered.

[0105] The second operation of third processing includes the carrying out of a frequency translation applied to the second signal of a value equal to the opposite of the ratio between the frequency of sampling and the number 2*M.

[0106] During the step of recombination, calculation is performed to obtain the difference between the first output signal and the second output signal, in order to obtain a first calculation signal.

[0107] Calculation is then performed to obtain the sum of the first output signal and the second output signal in order to obtain a second intermediate calculation signal.

[0108] This is also accompanied by implementation of a shifting of the second intermediate calculation signal by M samples in order to obtain a second calculation signal.

[0109] Calculation is then also performed to obtain the sum of the first calculation signal and the second calculation signal in order to obtain the filtered signal.

[0110] The same advantages are applicable to the embodiment according to FIG. 3.

[0111] According to another variant embodiment, the second filter 18 is in accordance with the embodiment represented in FIG. 4.

[0112] The elements that are identical to those in the embodiment represented in FIG. 2 have not been described again. Only the differences have been highlighted.

[0113] The second filter 18 according to the embodiment represented in FIG. 4 is different from the second filter 18 according to the embodiment represented in FIG. 2 by way of the operations that first channel 181 and the second channel 182 are capable of carrying out.

[0114] The similar elements

[0115] In the case of FIG. 4, the first operation of first processing implements the shifting of the input signal by M samples in order to obtain a shifted signal and the calculation of the sum of the input signal and the shifted signal.

[0116] Every first operation of second processing and third processing consists of transmitting the signal.

[0117] According to the example in FIG. 4, the second operation of first processing implements the shifting of the input signal by M samples in order to obtain a shifted signal and the calculation of the sum of the input signal and the shifted signal. The second operation of first processing then implements a frequency translation of a value equal to the ratio between the frequency of sampling and the number 2*M.

[0118] The second operation of second processing consists of transmitting the signal.

[0119] The second operation of third processing implements a frequency translation applied to the second signal of a value equal to the opposite of the ratio between the frequency of sampling and the number 2*M.

[0120] The same advantages are applicable to the embodiment according to FIG. 4.

[0121] In the section that follows, with reference being made to FIG. 5, it is shown that the proposed calculations provide the ability to obtain the desired filtering.

[0122] In order to compute a tranche of M output points, use is made of a tranche of 2 million points a.sub.n for indices n which, by convention, will be for example 0 n 2M−1.

[0123] In order to understand the remainder of the calculation, it is necessary to explain the generalities with respect to the decomposition of a discrete Fourier transform (DFT) in Radix (x being the number of factorisable points).

[0124] The discrete Fourier transform at N points of a sequence of N points x.sub.n (where N is an integer) amounts to:

[00001]$X_m=\underset{n=0}{\overset{N-1}{.Math.}}.Math.x_n.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n\times m}{N}}$

[0125] In the case where N is the product N=N.sub.1 N x.sub.2 of two whole numbers or integers N.sub.1 and N.sub.2, it may be written as follows:

[00002]$X_{m_1.Math.N_2+m_2}=\underset{n_1=0}{\overset{N_1-1}{.Math.}}.Math.\underset{n_2=0}{\overset{N_2-1}{.Math.}}.Math.x_{n_2.Math.N_1+n_1}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{\left(n_2.Math.N_1+n_1\right)\times \left(m_1.Math.N_2+m_2\right)}{N_1.Math.N_2}}=\underset{n_1=0}{\overset{N_1-1}{.Math.}}.Math.\underset{n_2=0}{\overset{N_2-1}{.Math.}}.Math.x_{n_2.Math.N_1+n_1}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n_1\times m_2}{N_1.Math.N_2}}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n_1\times m_1}{N_1}}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n_2\times m_2}{N_2}}$

[0126] There are two ways of decomposing the discrete Fourier transform, the two ways corresponding to the cascade of a discrete Fourier transform at n.sub.1 points and a discrete Fourier transform at n.sub.2 points. This is the order to be followed for performing these differing discrete Fourier transforms.

[0127] One of the discrete Fourier transforms that is implemented is weighted by a local oscillator that is used to perform an end shifting of the spectrum the exponential term that makes possible this translation is known as “twiddle factor”:

[00003]$\mathrm{twiddle}.Math..Math.\mathrm{factor}=e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n_1\times m_2}{N_1.Math.N_2}}$

[0128] In principle, the fastest varying output index is m.sub.1 since it corresponds to the ‘fast’ discrete Fourier transform that is to say not multiplexed. Thus, the output order of the frequencies is not the natural order: in fact, first to be output are the m′s having a value of 0 modulo N.sub.1 then the m′s having a value of 1 and so on until the m's having a value of N.sub.1−1 still with 0 modulo N.sub.1, this order is known as “bit reverse” because this corresponds to reversing the binary representation of the index in order to obtain the output tier (for a number of power of 2 points).

[0129] The execution of the inverse discrete Fourier transform, which retrieves the frequency data in “bit reverse”, is carried out in a dual manner, by reversing the operations.

[0130] According to a first case, the discrete Fourier transform at N.sub.1 points (“fast”) is followed of the Fourier transform at N.sub.2 points (“multiplexed”), which corresponds to:

[00004]$X_{m_1.Math.N_2+m_2}=\underset{n_1=0}{\overset{N_1-1}{.Math.}}.Math.\underset{n_2=0}{\overset{N_2-1}{.Math.}}.Math.x_{n_2.Math.N_1+n_1}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{\left(n_2.Math.N_1+n_1\right)\times \left(m_1.Math.N_2+m_2\right)}{N_1.Math.N_2}}=\underset{\underset{\begin{array}{c}\mathrm{FFT}.Math..Math.\mathrm{at}.Math..Math.N_1.Math..Math.\mathrm{points}\\ \mathrm{multiplexed}.Math..Math.\mathrm{by}.Math..Math.N_1\\ \left({\mathrm{RadixN}}_2\right)\end{array}}{}}{\underset{n_2=0}{\overset{N_2-1}{.Math.}}.Math.e^{-j.Math..Math.2.Math..Math.\pi +\frac{n_2\times m_2}{N_2}}\times \begin{array}{c}\underset{n_1=0}{\overset{N_1-1}{.Math.}}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n_1\times m_1}{N.Math..Math.1}}.Math.\underset{\stackrel{\mathrm{twiddle}}{\mathrm{factor}}}{\underset{}{e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n_1\times m_2}{N_1.Math.N_2}}}}\times x_{n_2.Math.N_1+n_1}\\ \underset{\mathrm{FFT}.Math..Math.\mathrm{at}.Math..Math.N_1.Math..Math.\mathrm{points}.Math..Math.\left({\mathrm{RadixN}}_1\right)}{}\end{array}}$

[0131] The execution of the Fourier transform is carried out as the cascade of a Fourier transform at N.sub.1 points that is not multiplexed and a Fourier transform at N.sub.2 points that is multiplexed by N.sub.1. The “twiddle factor” is placed on top in front of the first stage of Fourier transform.

[0132] According to a second case, the discrete Fourier transform at N.sub.2 points (“multiplexed”) is followed by the Fourier transform at N.sub.1 points (“fast”), which corresponds to:

[00005]$X_{m_1.Math.N_2+m_2}=\underset{n_1=0}{\overset{N_1-1}{.Math.}}.Math.\underset{n_2=0}{\overset{N_2-1}{.Math.}}.Math.x_{n_2.Math.N_1+n_1}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{\left(n_2.Math.N_1+n_1\right)\times \left(m_1.Math.N_2+m_2\right)}{N_1.Math.N_2}}=\underset{\underset{\begin{array}{c}\underset{\left({\mathrm{RadixN}}_1\right)}{\mathrm{FFT}.Math..Math.\mathrm{at}.Math..Math.N_1.Math..Math.\mathrm{points}}\\ \end{array}}{}}{\underset{n_1=0}{\overset{N_1-1}{.Math.}}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n_1\times m_1}{N_1}}\times \underset{\underset{\mathrm{twiddle}.Math..Math.\mathrm{factor}}{}}{e^{-j.Math..Math.2.Math..Math.\pi .Math.\frac{n_1\times m_2}{N_1.Math.N_2}\times }}.Math.\underset{\underset{\mathrm{FFT}.Math..Math.\mathrm{at}.Math..Math.N_2.Math..Math.\mathrm{points}.Math..Math.\mathrm{multiplexed}.Math..Math.\mathrm{by}.Math..Math.N_1.Math.\left({\mathrm{RadixN}}_2\right)}{}}{\underset{n_2=0}{\overset{N_2-1}{.Math.}}.Math.e^{-j.Math..Math.2.Math..Math.\pi +\frac{n_2\times m_2}{N_2}}.Math.x_{n_2.Math.N_1+n_1}}}$

[0133] The execution of the Fourier transform is carried out this time as the cascade of a discrete Fourier transform at N.sub.2 points that is multiplexed by N.sub.1 and a discrete Fourier transform at N.sub.1 points that is not multiplexed. The “twiddle factor” is placed between the two stages of discrete Fourier transform. The first discrete Fourier transform carried out being multiplexed, this decomposition is adapted to parallelized input data the multiplexing thus then is transformed into parallel processing.

[0134] According to one of the conventional versions of decomposition in radix2, the FFT at 2 M points of this suite a.sub.n is written as:

[00006]$b_m=\underset{n=0}{\overset{2.Math.M-1}{.Math.}}.Math.a_n.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math.\mathrm{nm}/\left(2.Math.M\right)}=\underset{n=0}{\overset{M-1}{.Math.}}.Math.a_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}/\left(2.Math.M\right)}+{\left(-1\right)}^m.Math.\underset{n=0}{\overset{M-1}{.Math.}}.Math.a_{M+n}.Math.e^{-j.Math..Math.2.Math..Math.\pi .Math..Math.\mathrm{nm}/\left(2.Math.M\right)}$

[0135] In particular:

[00007]$b_{2.Math.m+p}=\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.a_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{np}.Math.\text{/}.Math.\left(2.Math.M\right)}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}+{\left(-1\right)}^p.Math.\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.a_{M+n}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{np}.Math.\text{/}.Math.\left(2.Math.M\right)}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}$$.Math.\mathrm{Where}.Math..Math.p=\{\begin{array}{c}0\\ 1\end{array}$

[0136] That is:

b.sub.2m+p=FFT.sub.m(α.sub.ne.sup.−jπnp/M)+(−1).sup.pFFT.sub.M(α.sub.M+ne.sup.−jπnp/M)

[0137] where FFT.sub.M denotes the FFT at M points.

[0138] It is to be noted that this spectral density is also written in the two following ways that will serve to simplify the implementation thereof:

b.sub.2m+p=FFT.sub.m(α.sub.ne.sup.−jπnp/M)+FFT.sub.M(α.sub.M+ne.sup.−jπ(m+n)p/M)

and

b.sub.2m+p=FFT.sub.M(└(−1).sup.pα.sub.n+α.sub.M+n┘e.sup.−jπ(M+n)p/M)

[0139] By denoting as ρ.sub.m the spectral response of the filter, the response filtered by inverse transformation is obtained as follows:

[00008]$c_k=\underset{p=0}{\overset{1}{.Math.}}.Math..Math.\underset{m=0}{\overset{M-1}{.Math.}}.Math..Math.b_{2.Math.m+p}.Math.{\rho }_{2.Math.m+p}.Math.e^{j.Math..Math.2.Math.\pi .Math..Math.k\left(2.Math.m+p\right).Math.\text{/}.Math.\left(2.Math.M\right)}=\underset{p=0}{\overset{1}{.Math.}}.Math..Math.e^{j.Math..Math.2.Math.\pi .Math..Math.\mathrm{kp}.Math.\text{/}.Math.\left(2.Math.M\right)}.Math.\underset{m=0}{\overset{M-1}{.Math.}}.Math..Math.b_{2.Math.m+p}.Math.{\rho }_{2.Math.m+p}.Math.e^{j.Math..Math.2.Math.\pi .Math..Math.\mathrm{km}.Math.\text{/}.Math.M}$

[0140] The response is calculated only for the points 0≦k≦M−1 (on account of the aliasing inherent in the FFT) in order to finally obtain:

[00009]$c_k=\underset{p=0}{\overset{1}{.Math.}}.Math..Math.e^{j.Math..Math.\pi .Math..Math.\mathrm{kp}.Math.\text{/}.Math.M}.Math.{\mathrm{IFFT}}_M\left(b_{2.Math.m+p}.Math.{\rho }_{2.Math.m+p}\right)$

[0141] where the IFFT.sub.M denotes the inverse FFT at M points.

[0142] The formulas giving b.sub.2m+p and c.sub.k it is possible to obtain the preceding block diagrams that provide the ability to perform convolutions with responses of twice the size by using the same size of FFT and IFFT, by means of saving to memory once on M points.

[0143] The block diagram shown in FIG. 2 is thus then obtained. Such a block diagram corresponds to the first formulation of the spectral density b.sub.2m+p.

[0144] By moving the save-memory function towards the output it is possible to reduce it by half, which results in the block diagram shown in FIG. 3.

[0145] Finally, the moving of the save-memory function towards the input, which corresponds to the second formulation of the spectral density b.sub.2m+p, results in the block diagram shown in FIG. 4 which can be considered as a dual version of the block diagram represented in FIG. 3.

[0146] The operations involved in these block diagrams correspond to the first tier (for the FFT) or the last tier (for the IFFT) of “twiddle factors” not taken into account, in principle, in the FFT at M points. Theoretically, these digital operations are to be reinitialised at each frame of FFT.

[0147] It is however to be noted that this is in fact not necessary in practice because, in the absence of reinitialisation, the sign of these operations changes at each frame, so that the two sign changes offset each other.

[0148] It may be demonstrated that such filtering is more economical in terms of memory resources in the event where a floating-point implementation is required.

[0149] When the filtering corresponds to the filtering adapted to a given signal (a pulse received for example), the complex gain of the matched filter is the conjugate of the pulse spectrum. If this spectrum is obtained by FFT at 2M points of a pulse starting at n=0 and ending before n=M, then the time response of the matched filter thus happens to be placed in the negative time.

[0150] If r.sub.n is the impulse and if x.sub.n is the signal received, the matched filtering carries out the following operation, which is the calculation of the autocorrelation of the pulse when the received signal x.sub.n is equal to the pulse r.sub.n , with the correlation peak arriving at the beginning of the pulse:

[00010]$y_q=\underset{k=0}{\overset{M-1}{.Math.}}.Math..Math.r_k^{*}.Math.x_{q+k}$

[0151] The conjugate of the complex gain of the matched filter is as follows:

[00011]$\{\begin{array}{c}{\rho }_{2.Math.m}^{*}=\underset{n=0}{\overset{2.Math.M-1}{.Math.}}.Math..Math.r_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.n\left(2.Math.m\right).Math.\text{/}.Math.\left(2.Math.M\right)}=\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.r_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}+\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.r_{M+n}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}.Math.\\ {\rho }_{2.Math.m+1}^{*}=\underset{n=0}{\overset{2.Math.M-1}{.Math.}}.Math..Math.r_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.n\left(2.Math.m+1\right).Math.\text{/}.Math.\left(2.Math.M\right)}=\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.r_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.n.Math.\text{/}.Math.\left(2.Math.M\right)}.Math.e^{-k.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}-\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.r_{M+n}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.n.Math.\text{/}.Math.\left(2.Math.M\right)}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}\end{array}\hspace{1em}$

[0152] Given that the impulse is zero for negative times, the result that is then obtained of two FFT at M points is:

[00012]${\rho }_{2.Math.m}^{*}=\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.r_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}$$\mathrm{and}$${\rho }_{2.Math.m+1}^{*}=\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.r_n.Math.e^{-j.Math..Math.\pi .Math..Math.n.Math.\text{/}.Math.M}.Math.e^{-j.Math..Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}$

[0153] This leads to the verification block diagram shown in FIG. 5 having a more symmetrical view that makes it possible to verify directly that each implementation of the second filter 18 effectively enables the achievement of the desired result.

[0154] At the input of the IFFT of the first channel 181, the following is obtained:

[00013]$\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}.Math.\underset{k=0}{\overset{M-1}{.Math.}}.Math..Math.r_k^{*}.Math.e^{+j.Math..Math.2.Math.\pi .Math..Math.\mathrm{km}.Math.\text{/}.Math.M}=\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.\underset{k=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.r_k^{*}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{qm}.Math.\text{/}.Math.M}=\underset{q=0}{\overset{M-1}{.Math.}}.Math..Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{qm}.Math.\text{/}.Math.M}.Math.\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.r_{\mathrm{mod}\left(n-q,M\right)}^{*}$

[0155] At the output of this IFFT of the first channel 181, the following is obtained:

[00014]$\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.r_{\mathrm{mod}\left(n-q,M\right)}^{*}$

[0156] For the second channel 182, at the input of the IFFT, the following is obtained:

[00015]$\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.n.Math.\text{/}.Math.M}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{nm}.Math.\text{/}.Math.M}.Math.\underset{k=0}{\overset{M-1}{.Math.}}.Math..Math.r_k^{*}.Math.e^{+j.Math..Math.2.Math.\pi .Math..Math.k.Math.\text{/}.Math.M}.Math.e^{+j.Math..Math.2.Math.\pi .Math..Math.\mathrm{km}.Math.\text{/}.Math.M}=\underset{k-n=-n}{\overset{-n+M-1}{.Math.}}.Math..Math.\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.r_k^{*}.Math.e^{-j.Math..Math.\pi \left(n-k\right).Math.\text{/}.Math.M}.Math.e^{-j.Math..Math.2.Math.\pi \left(n-k\right).Math.m.Math.\text{/}.Math.M}$

[0157] These last equations may be written as follows:

[00016]$\underset{n-k=n+1-M}{\overset{n}{.Math.}}.Math..Math.\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.r_k^{*}.Math.e^{-j.Math..Math.\pi \left(n-k\right).Math.\text{/}.Math.M}.Math.e^{-j.Math..Math.2.Math.\pi \left(n-k\right).Math.m.Math.\text{/}.Math.M}=\underset{q=0}{\overset{M-1}{.Math.}}.Math..Math.e^{-j.Math..Math.\pi .Math..Math.j.Math.\text{/}.Math.M}.Math.e^{-j.Math..Math.2.Math.\pi .Math..Math.\mathrm{jm}.Math.\text{/}.Math.M}.Math.\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.r_{\mathrm{mod}\left(n-q,M\right)}^{*}.Math.\mathrm{sign}\left(n-q\right)$$.Math.\mathrm{où}.Math..Math.\mathrm{sign}\left(n-q\right)=\{\begin{array}{cc}-1& \mathrm{si}.Math..Math.n<q\\ +1& \mathrm{si}.Math..Math.n\ge q\end{array}$

[0158] At the output of this IFFT of the second channel 182, and after multiplication by the “twiddle factor”, the following is obtained:

[00017]$\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.{\xi }_n.Math.r_{\mathrm{mod}\left(n-q,M\right)}^{*}.Math.\mathrm{sign}\left(n-q\right)$

[0159] However: [0160] on the upper channel: ξ.sub.n=x.sub.n+x.sub.n-M [0161] on the lower channel: ξ.sub.n=x.sub.n−x.sub.n-M

[0162] The overall output thus is:

[00018]$y_q=\underset{n=0}{\overset{M-1}{.Math.}}.Math..Math.r_{\mathrm{mod}\left(n-q,M\right)}^{*}\times \left[\left(x_n+x_{n-M}\right)-\left(x_n-x_{n-M}\right)\times \mathrm{sign}\left(n-q\right)\right]$

[0163] That is to say:

[00019]$y_q=2\times \left(\underset{n=0}{\overset{q-1}{.Math.}}.Math..Math.x_n.Math.r_{\mathrm{mod}\left(n-q,M\right)}^{*}+\underset{n=1}{\overset{M-1}{.Math.}}.Math..Math.x_{n-M}.Math.r_{\mathrm{mod}\left(n-q,M\right)}^{*}\right)=2\times \left(\underset{n=0}{\overset{q-1}{.Math.}}.Math..Math.x_n.Math.r_{n-q,M}^{*}+\underset{n=1}{\overset{M-1}{.Math.}}.Math..Math.x_{n-M}.Math.r_{n-q}^{*}\right)$

[0164] Which is:

[00020]$y_q=2\times \left(\underset{n=0}{\overset{q-1}{.Math.}}.Math..Math.x_n.Math.r_{n-q+M}^{*}+\underset{n=q-M}{\overset{-1}{.Math.}}.Math..Math.x_n.Math.r_{n-q+M}^{*}\right)=2.Math.\underset{n=q-M}{\overset{q-1}{.Math.}}.Math..Math.x_n.Math.r_{n-q+M}^{*}=2.Math.\underset{k=0}{\overset{M-1}{.Math.}}.Math..Math.r_k^{*}.Math.x_{q+k-M}$

[0165] In fact, it has been shown that the desired result is obtained at a time shift of M points (ensuring the causality of the process) and to within a multiplicative factor of 2:

[00021]$y_{q+M}=2.Math.\underset{k=0}{\overset{M-1}{.Math.}}.Math..Math.r_k^{*}.Math.x_{q+k}$

[0166] This demonstration carried out for the block diagram shown in FIG. 4 converts easily for the two other block diagram shown in the FIGS. 2 and 3.

[0167] In any case, this reasoning shows that the major interest of the proposed method is the economy of memory resources. In fact, an FFT requires a depth of memory storage that is equal to its size.

[0168] In the case of a method according to the state of the art, the required memory space is therefore equal to four times the resources required for a FFT (2 FFT and 2 IFFT): 4×2M=8M points. In contrast, in the case of the proposed method, the FFTs being half the size, the size required by the FFTs and IFFTs therefore drops to 4M points to which should be added M points for effecting the specific memory save performed at the top this corresponds to a computation of 5M points. The savings in memory storage space achieved is therefore close to 40%.

[0169] The second interesting benefit of the proposed method lies in the fact that the two channels 181 and 182 are synchronous, whereas these channels are shifted by a half frame in the case of a method according to the state of the art. Indeed, if the twiddle factors of the FFT and the IFFT are calculated instead of being stored in the tables (which is desirable for FFT of large sizes), this provides the ability to consolidate this computation between the two channels 181 and 182 of the method, whereas this was not possible in a method according to the state of the art.

[0170] In other words, it has been demonstrated that the proposed method makes possible the easier implementation of filtering of a numerical input signal.