METHOD AND SYSTEM FOR ESTIMATING PARAMETERS OF A MULTI-TONE SIGNAL

CROSS-REFERENCE TO RELATED APPLICATION

[0001] The present application claims the benefits of U.S. provisional patent application No. 60/996,891 filed December 10, 2007, which is hereby incorporated by reference.

TECHNICAL FIELD

[0002] The present invention is generally concerned with a method and system for estimating parameters of a multi-tone signal, and more particularly with estimating frequencies and amplitudes of single-tone signals making up a multi-tone signal.

BACKGROUND

[0003] Multi-tone signals are encountered in various fields, such as speech processing, telecommunications, radar and sonar technologies, remote controlling, seismology, geophysical morphology, estimation of arrival direction, the characterization of biological tissues, music, vibration control and astronomy.

[0004] A multi-tone signal s(t) is a signal that is made up of M tones, each tone being characterized by a frequency / and a complex amplitude A .

For the case of a real signal, the complex amplitude A can also be characterized by a real amplitude E and a phase φ .

[0005] Indeed, either in real or complex form, a multi-tone signal comprising M tones is described by M complex parameters and M real parameters.

[0006] However, most of the time, the 2M parameters are not known; instead, time samples of the signal are available, from which the parameters are to be estimated.

[0007] Estimating parameters of a multi-tone signal is a well known problem [1], the complexity of which arises as a result of the multi-tone signal's model being a nonlinear model, since an inversion method of such a model can often be tedious or even unknown or unavailable.

[0008] Various approaches for estimating the parameters have been used in order to circumvent the inversion problem, for example methods using the covariance matrix [2] [3] [4], linear prediction [5] [6], ARMA models [7] and Discrete Fourier Transform (DFT).

[0009] A major drawback for the existing methods for estimating the parameters of a multi-tone signal is that the computing time increases with the precision required for the estimated parameters. As a result, real-time applications that have to estimate the parameters of a multi-tone signal typically have to make a compromise between precision and resolution time. Moreover, such real-time applications typically are performed in a context where computing power is limited, for example because processors pertaining thereof are limited or many signals are simultaneously processed, and a result thereof must be provided rapidly.

[0010] Therefore, there is a need for a method for estimating parameters of a multi-tone signal that is precise and requires little computing time, i.e. CPU time.

SUMMARY

[0011] According to the present invention, there is provided a method and system for estimating parameters of a multi-tone signal made up of at least one

single-tone signal, each single-tone signal being characterized by a frequency and a complex amplitude.

[0012] More specifically, in accordance with the present invention, there is provided a method for estimating the frequency and the amplitude of each single-tone signal making up a multi-tone signal, comprising the steps of:

generating time samples of the multi-tone signal;

calculating Discrete Fourier Transform frequency samples from the time samples;

building a system of linear equations from the frequency samples;

defining an intermediate vector from a solution of the system of linear equations;

defining coefficients of a polynomial from components of the intermediate vector;

calculating roots of the polynomial;

calculating an amplitude-related vector from at least the roots of the polynomial;

calculating the estimate of the frequency of each single-tone signal from the roots of the polynomial;

calculating the estimate of the amplitude of each single-tone signal from the amplitude-related vector; and

as an optional feature, calculating the reconstructed DFT frequency samples from the estimated frequencies and amplitudes of the multi-tone signal.

[0013] According to a second aspect of the present invention, there is provided a system for estimating the frequency and the amplitude of each single-tone signal making up a multi-tone signal, the system comprising:

a sampler for generating time samples of the multi-tone signal;

an input/output interface; and

a processing unit operatively connected to the sampler and the input/output interface, the processing unit being so configured as to:

calculating Discrete Fourier Transform frequency samples from the time samples generated by the sampler;

building a system of linear equations from the frequency samples;

defining an intermediate vector from a solution of the system of linear equations;

defining coefficients of a polynomial from components of the intermediate vector;

calculating roots of the polynomial;

calculating an amplitude-related vector from at least the roots of the polynomial;

calculating the estimate of the frequency of each single-tone signal from the roots of the polynomial;

calculating the estimate of the amplitude of each single-tone signal from the amplitude-related vector;

providing the estimated frequencies and the estimated amplitudes to the input/output interface; and

as an optional feature, calculating and providing the reconstructed DFT frequency samples from the estimated frequencies and amplitudes of the multi-tone signal.

[0014] The multi-tone signal can be either a real signal or a complex signal. In the former case, the multi-tone signal is typically made up of real single-tone signals, each of which is characterized by a real frequency and a complex amplitude or, alternatively, by a real frequency, a real amplitude and a real phase; in the latter case, the multi-tone signal is typically made up of complex single-tone signals, each of which is characterized by real frequency and a complex amplitude.

[0015] As used in this specification and claim(s), the words "comprising"

(and any form of comprising, such as "comprise" and "comprises"), "having" (and any form of having, such as "have" and "has"), "including" (and any form of including, such as "include" and "includes") or "containing" (and any form of containing, such as "contain" and "contains"), are inclusive or open-ended and do not exclude additional, unrecited elements or process steps.

[0016] The foregoing and other objects, advantages and features of the present invention will become more apparent upon reading of the following non- restrictive description of illustrative embodiments.

BRIEF DESCRIPTION OF THE DRAWINGS

[0017] Non-limitative illustrative embodiments of the invention will now be described by way of example only with reference to the accompanying drawings, in which:

[0018] Figure 1 is a schematic representation of a system for estimating parameters of a multi-tone signal according to an illustrative embodiment of the present invention;

[0019] Figure 2 is a flow diagram of a general process for estimating parameters of a multi-tone signal according to an illustrative embodiment of the present invention;

[0020] Figure 3 is a flow diagram of a first illustrative embodiment of the general process of Figure 2 applied to a complex multi-tone signal;

[0021] Figure 4 is a flow diagram of a second illustrative embodiment of the general process of Figure 2 applied to a real multi-tone signal;

[0022] Figure 5 is a flow diagram of a third illustrative embodiment of the general process of Figure 2 applied to a complex multi-tone signal; and

[0023] Figure 6 is a flow diagram of a fourth illustrative embodiment of the general process of Figure 2 applied to a real multi-tone signal.

NOTATION

[0024] Throughout the specification pertaining to the present invention, the notation presented hereinbelow will be used.

[0025] A superscript " ^* " indicates a complex conjugate and the superscript " ^r " indicates the transpose of a matrix or a vector. For a complex number z , Re{z} and Im{z} are respectively the real part and the imaginary part of z . The notation O = diag{d ₀ d _λ ...} indicates a diagonal matrix D , the values on the diagonal of which are d ₀ , d _v ... , all other elements of the matrix being zero.

u _k = cos(^) v _t = sin(^-) λ _m = e ^j2πf»τ μ _m = cos(2πfj) = Re{λ _m } v _m = ύn(2πf _m T) = \m{λ _m } [0026] , Equation 1 q _m = M ^p _m ) S _r (k) = Re{S(k)} Sχk) = lm{S(k)}

wherein j = V^T .

[0027] Furthermore, the notation S(k,l) means the Discrete Fourier

Transform (DFT) frequency sample of index & of a DFT of length N associated with time frame / using time samples s(h),s([l + .

DETAILED DESCRIPTION

[0028] Generally stated, the non-limitative illustrative embodiment of the present invention provides a method and system for estimating parameters of a multi-tone signal, and more particularly with estimating frequencies and amplitudes of single-tone signals making up a multi-tone signal.

[0029] A multi-tone signal is made up of at least one single-tone signal, each of which being characterized by a real frequency / and a complex amplitude A .

[0030] More specifically, for a complex single-tone signal: s(t) = Ae ^j2πβ . Equation 2

[0031] A real single-tone signal s(t) can be viewed as the sum of a first complex signal and a second complex signal, wherein to a given complex single-tone signal corresponds another complex single-tone signal, the amplitude of which is the conjugate of the given single-tone signal and the frequency of which is the negative of the frequency of the given single-tone signal.

[0032] More specifically, for a real single-tone signal: s(t) = Ae ^l2πβ + A ^* e-' ^2πβ . Equation 3

[0033] A real single-tone signal can also be characterized by a real frequency / , a real amplitude E and a phase φ :

s(t) = E cos(2π ft + φ) . Equation 4

[0034] The real parameters E and φ and the complex parameter A are related by:

Equation 5

Re{.4} =— costø)

77 Im [A) = — sin [φ)

[0035] Referring to Figure 1 , there is shown a schematic representation of a system 10 for estimating parameters 11 of a multi-tone signal 1 according an the illustrative embodiment of the present invention. The system 10 comprises a sampler 12 for sampling a multi-tone signal 1 , a processing unit 14 for performing the parameters estimation process, an optional storage unit 16

for storing results of intermediate calculations or the estimated parameters 11 of the multi-tone signal 1 , and an input/output interface 18 for providing the estimated parameters 11 to, for example, another device for further treatment, a display, etc. The parameters 11 , namely frequencies f _m and amplitudes A _1n , can then be used for reconstructing the multi-tone signal 1.

[0036] Referring now to Figure 2, there is shown a flow diagram of an illustrative embodiment of a general process 100 that can be executed by the processing unit 14 to estimate the parameters of the multi-tone signal 1. The steps of the process 100 are indicated by blocks 102 to 114.

[0037] The process 100 starts at block 102 where time samples of the multi-tone signal 1 are generated by using the sampler 12 and the Discrete Fourier Transform (DFT) frequency samples of the time samples are calculated.

[0038] At block 104, a system of linear equations is built from the calculated DFT frequency samples, the solution of the system of linear equations is calculated and an intermediate vector is defined from the solution of the system of linear equations.

[0039] At block 106, the coefficients of a polynomial are defined from the components of the intermediate vector and the roots of the polynomial are calculated.

[0040] At block 108, estimates of the frequencies are calculated from the roots of the polynomial.

[0041] At block 110, an amplitude-related vector is calculated from the roots of the polynomial or from the intermediate vector of block 104 and the roots of the polynomial, depending on the specific implementation.

[0042] At block 112, estimates of the amplitudes are calculated from the amplitude-related vector.

[0043] At block 114, as an optional feature, the DFT frequency samples of the multi-tone signal can be reconstructed from the estimated frequencies and amplitudes of the multi-tone signal.

[0044] The general process 100 will be further detailed using four non- restrictive illustrative embodiments. The first and third illustrative embodiments are concerned with a complex multi-tone signal, whereas the second and fourth illustrative embodiments are concerned with a real multi-tone signal.

[0045] However, it is to be understood that a real multi-tone signal, as it is known by those skilled in the art, can be represented as the sum of complex single-tone signals, each real single-tone signal being the sum of two complex single-tone signals. Therefore, it is possible to also use the first and third alternative illustrative embodiments for estimating parameters of a real multi-tone signal.

[0046] Referring to Figure 3, the process 200 for estimating parameters of a complex multi-tone signal s(t) made up of at least one single-tone signal will now be described according to the first non-restrictive illustrative embodiment of process 100. The steps of the process 200 are indicated by blocks 202 to 214.

[0047] It is to be understood that blocks 202 to 214 of process 200 are specific implementations of the associated general blocks 102 to 114 of process 100 from Figure 2.

[0048] The process 200 starts at block 202 where a sampling period T for sampling the signal s(t) is chosen. From an arbitrary reference time t = 0 , the sampling can be made at times ..., - 2T, - T, 0, T, 2T, ... so as to get the signal time samples s(nT) , wherein n = ..., - 2, -1, 0, 1, 2, ... .

[0049] Accordingly, using N time samples s(nT) , with /i = 0, 1, 2,..., N -\ ,

DFT frequency samples S(A:) are calculated for integer values of k, 0≤k<N, wherein:

JV-I Iπkn

S(k) = ∑s(nT)e ^~J~ Equation 6

«=0

[0050] In the present illustrative embodiment, N is chosen so that

N≥2M .

[0051] At block 204, a system of linear equations is built. 2M DFT frequency samples are selected from the N possible DFT frequency samples of block 202 hereinabove. The 2M frequency samples are indexed by k _ϋ ,k _λ ,...,k _m _ _λ . It is to be noted that in general, an index of the 2M frequency samples is denoted by k _l .

[0052] More specifically, the resulting system of linear equations is: g = [Y θY]h Equation 7

wherein:

g = [S(* ₀ ) Stø) ... S{k _m _S[

θ _kι =-S(k,)w _kι

-I ₁ T / = 0,l,...,2M-l y*. = [i W, W, W ₁ ,

[0053] The solution of the system of linear equations is then calculated

and the intermediate vector [a b] is defined such that:

= h = [Y θYj-' g Equation 8

wherein:

[0054] It is to be noted that indices of vector a range from 0 to M -I , whereas indices of vector b range from 1 to M .

[0055] The components of vector b are to be used as coefficients for defining a complex polynomial.

[0056] At block 206, the coefficients of the polynomial are defined and the roots of the polynomial are calculated. From the vector b as defined hereinabove in block 204, the following complex polynomial is defined, wherein z is a complex variable:

M z ^M +γb _n z ^M→ = 0. Equation 9

«=1

[0057] The roots z _m of the complex polynomial are then calculated, wherein m = 0, 1, ... , M -I .

[0058] Then, at block 208, estimates of the frequencies f _m , wherein m = 0, 1, ... , M - 1 , are calculated from the following equation:

_{Zm = λm} = _e ^j w . Equation 10

[0059] At block 210, a vector p pertaining to amplitudes is calculated, such that:

C a = p , Equation 11

wherein vector a is defined at block 204 and C is a MxM matrix, the elements of which are each defined by:

fl n = 0 c"> » ⁼ \ u _í * i o _{M 1} • Equation 12

Iλ ⁺ V _m ,n-i « = 1,2,...,M -1

wherein c _m „ is an element of C on line n column m ; and

[0060] At block 212, from the components of vector p calculated in block

210 hereinabove, estimates of the M complex amplitudes A _1n , wherein m - 0, 1, ... , M -1 , are calculated from the following equation:

^A _m = ^~ 7W - Equation 13

[0061] At this point, all the parameters of the complex multi-tone signal have been estimated, i.e. the M real frequencies f _m and the M complex amplitudes A _m have been calculated.

[0062] At block 214, as an optional feature, the DFT frequency samples can be reconstructed from the estimated frequencies and amplitudes of the multi-tone signal. For each complex single-tone signal s _m (t) = A _m e ^j2πfm ' ,

m = 0, 1, ... , M - 1 , of a multi-tone signal s(t) = ]T s _m (t) , the N DFT frequency m=0 samples S _m (k) , k = 0, 1, ... , N - 1 , are reconstructed using:

S _m ⁽ k) = — ^ — . Equation 14

1 - w ¹ Vλ

[0063] S _m (k) as defined hereinabove is the projection of the complex single-tone of index m on the k _lh vector of the transformation matrix of the DFT of length N .

[0064] For a complex multi-tone signal, the N DFT frequency samples

S(k) , k = 0, 1, ... , N-I can be reconstructed using:

M-I m=0 M-X

∑ a _m w _k ^m Equation 15

S(k) = - m=0

M

1 + ∑A, JV,. m=l

wherein S _n , (k) is defined hereinabove, a _m are the elements of vector a and b _m+] are the elements of vector b , m = 0, 1, ... , M - I , vector a and vector b being defined at block 204.

[0065] S(k) as defined hereinabove for a multi-tone signal is the projection of the complex multi-tone signal on the k _lh vector of the transformation matrix of the DFT of length N .

[0066] For the case of a complex single-tone signal with frequency / , using DFT frequency samples of index & ₀ and £, , with k _ϋ < k _} , the frequency / can be obtained using:

cot(π[%-fr]) = γ- ^ι g ; Equation 16

[0067] A second non-restrictive illustrative embodiment of the process

100 of Figure 2 will now be described in Figure 4 as process 300. Process 300 is used for estimating parameters of a real multi-tone signal s(t) made up of at least one single-tone signal.

[0068] It is to be noted that process 300 is adapted from process 200, since a real single-tone signal s(t) can always be viewed as the sum of a first complex signal and a second complex signal, wherein to a given complex single-tone signal corresponds another complex single-tone signal, the amplitude of which is the conjugate of the given single-tone signal and the frequency of which is the negative of the frequency of the given single-tone signal.

[0069] Referring to Figure 4, the process 300 for estimating parameters of a real multi-tone signal s(t) made up of at least one single-tone signal will now be described according to the second non-restrictive illustrative embodiment of process 100. The steps of the process 300 are indicated by blocks 302 to 314.

[0070] It is to be understood that blocks 302 to 314 of process 300 are specific implementations of the associated general blocks 102 to 114 of process 100 from Figure 2.

[0071] The process 300 starts at block 302 where time samples of the multi-tone signal are generated and the DFT frequency samples are calculated. This is accomplished similarly to block 202 of process 200 of Figure 3 with the exception that the signal s(t) is a real signal made up of M real single-tone signals, each of which is characterized by a real frequency f _m and a complex amplitude A _1n , and N is chosen so that N > 3M .

[0072] At block 304, a system of linear equations is built and an intermediate vector is defined. The calculated DFT frequency samples of block

302 are divided into two sets β _re and β _ιm of real values: a first set is made up of the real parts of the calculated DFT frequency samples, whereas the second set is made up of the imaginary parts of the calculated DFT frequency samples.

[0073] More specifically, in the case of N being even,

β _n :{Re{5(0)},Re{S(l)},...,Re{5(f)}} β _m :{lm{S(l)},Im{S(2)},...,Im{S(f -1)}} '

and in the case of N being odd,

A.:{Re{5(0)},Re{Sα)},...,Re{S(^ ^L )}} β _m :{lxn{S{\)}M{S(2)},...,lm{S{^)}\

[0074] Process 300 can be put into practice by choosing elements either from β _re or β _m , as described hereinbelow.

[0075] M _re elements are chosen from β _re and M _11n elements are chosen from β _m , wherein M _re +M _ιm =3M . The 3M elements are indexed by k _o ,k _x ,..., yt _3M _, . It is to be noted that in general, an index of the 3M elements is denoted by k, .

[0076] From the 3M elements, a system of linear equations is built:

g = [θ ₀ Y θ,Y θ ₂ Y]h, Equation 17

wherein:

It = [H ₀ \ ... /^ ₁ ]' θ ₀ =diag{θ ₀₀ 6> ₀₁ ... 0 _0>3W _,} ® _x =diag{θ _Xfi θ _lλ ... 6» _13W _,} ' θ ₂ =diag{θ ₂₀ θ _2λ ... θ _2m _,}

^Y = [n, y*. ,τ

^0,, = «4, for the elements chosen from β _re ,

θ _2ι = -Re {S(k,)}

g, =lm{S(k,)}u _k for the elements chosen from β _m , θ _υ =0

^,=-Im{^,)}

for / = 0,l,...,3M-l.

[0077] The solution of the system of linear equations is then calculated and an intermediate vector [a b c] ^r is defined, such that:

[θ ₀ Y θ,Y θ ₂ Y] ^" 'g, Equation 18

wherein:

a = [a ₀ a _x - «*,-ι] b = [h - v,r

C =h C ₂

[0078] At block 306, the coefficients of a polynomial are defined and the roots of the polynomial are calculated. From the vector c as defined in block 304, the following real polynomial is defined, wherein z is a real variable:

M z ^M + ∑c _n z ^M -" = 0 . Equation 19 n=\

[0079] The real roots z _m of the real polynomial are then calculated, wherein m = 0, 1, ... , M - 1.

[0080] Then, at block 308, estimates of the frequencies f _m , wherein m = 0, 1, ... , M - 1 , are calculated from the following equation:

z _m = μ _m = cos(2πfj) . Equation 20

[0081] At block 310, the amplitude-related vector p is calculated from vectors q and r , using:

D

[0082] - ' u -a - = n ⁱ q .. Equation 21

D ^] b = r

r =fo - ^r M~l f wherein: vector a and vector b are defined at block 304, and D is a M xM matrix, the element d _{m n} of line n and column m being defined as:

[0083] Then,

, s r -a u ■ Equation 22

[0084] At block 312, from the components of the vector p calculated in block 310, estimates of the M amplitudes A _1n , wherein m = 0, 1, ... , M - I , are calculated from the following equation:

λ, = r Dr- ^E <hτήγ- Equation 23

[0085] At block 314, as an optional feature, the DFT frequency samples can be reconstructed from the estimated frequencies and amplitudes of the multi-tone signal. For each real single-tone signal s _m (t) = A _m e' ^2πIm ' + A _m ^* e ^~ ' ^2πim ' ,

m = 0, 1, ... , M - 1 , of a multi-tone signal s(t) = ]T s _m (t) , the N DFT frequency

samples S _1n (k) , k = 0, \, ... , N-\ , are reconstructed using:

s , _k \ ₌ <M»k - ^r _m . Equation 24

wherein q _m are elements of vector q , r _m are elements of vector r , q and r being defined at block 310.

[0086] S _m (k) as defined hereinabove is the projection of the real single- tone of index m on the k _th vector of the transformation matrix of the DFT of length N .

[0087] For a real multi-tone signal, the N DFT frequency samples S(k) ,

£ = 0, 1, ... , 7V-I can be reconstructed using:

M-I m=0

M-I M-I

<∑°λ ^m -∑bλ ^m Equation 25

S(k) = u _k M m=l

wherein S _m (k) is defined hereinabove, a _m are the elements of vector a , b _m are the elements of vector b and c _m+1 are the elements of vector c , m = 0, 1, ... , M -1 , vector a , vector b and vector c being defined at block 304.

[0088] S(k) as defined hereinabove for a multi-tone signal is the projection of the complex multi-tone signal on the k _lh vector of the transformation matrix of the DFT of length N .

[0089] A third non-restrictive illustrative embodiment of the process 100 of Figure 2 will now be described in Figure 5 as process 400. Process 400 is used for estimating parameters of a complex multi-tone signal s(t) made up of at least one single-tone signal.

[0090] Referring to Figure 5, the process 400 for estimating parameters of a complex multi-tone signal s(t) made up of at least one single-tone signal will now be described according to the third non-restrictive illustrative embodiment of process 100. The steps of the process 400 are indicated by blocks 402 to 414.

[0091] It is to be understood that blocks 402 to 414 of process 400 are specific implementations of the associated general blocks 102 to 114 of process 100 from Figure 2.

[0092] The process 400 starts at block 402 where time samples of the multi-tone signal are generated. A total of N _T =N + M + L + L ₀ samples s(lT), l _o ≤l<l _o +N _τ are generated wherein: I ₀ =...,-2,-1,0,1,2,..., I ₀ is the index of the first time frame used, M is the number of tones in the signal, N is the length of the DFT, and L and L ₀ are integers with L ≥ 0 and L ₀ ≥ 0.

[0093] Using successive time frames S[(/ + M)γ], « = 0,1,..., N-I, the

DFT frequency samples S(k,l) for time frames l _o ≤l≤l _o +N _τ -N are calculated, wherein:

N- ^] Iπkn

-J-

S(*,0 = ∑s([/ + n]r)e ^{~ N} ■ Equation 26 n=0

[0094] The DFT frequency samples S(k,l) for successive time frames are calculated using recursions:

S(k,l + \) = w _k [S{k,l) + s((l + N)T) -S(IT)]

¹ Equation 27

S(k, 1 -1) = w _k S(k, l) + s([l- I]T) -sφ + N- I]T).

[0095] The process 400 uses auto-correlations of the DFT frequency samples S(k,l) over successive time frames /. More specifically:

l _o +M-m+L

C(k,m,τ)= ∑ S'(k,l)S(k,l + τ). Equation 28 l=l _o +M -tn

[0096] At block 404, a system of linear equations is built. From the N

DFT frequency samples S(k,l) of any time frames /, K DFT frequency samples are selected and auto-correlations of S(k,l) over successive time frames are calculated for each selected frequency sample. The K frequency samples are indexed by k _o ,k _λ ,...,k _κ _ _x . It is to be noted that in general, an index

of the K frequency samples is denoted by k, .

[0097] More specifically, the resulting system of linear equations is:

b = Ra Equation 29

wherein:

B = [Oi ₁ a ₂ ... a _M ]' b = tø ^b 2 - b _u ] ^τ

R, 1, ,1 R 1,2 R \,M

R

R = 2,1 λ 2,2 R -2,M

R λ/,1 R 2, M R ^■ M M

K-I

R _m,n = ∑C(k, ,L _o + m - n) ι=0

L ≥ O and L ₀ ≥ 0 .

[0098] The solution of the system of linear equations is then calculated, such that:

R b = a , Equation 30

defining the intermediate vector a .

[0099] The components of vector a are to be used as coefficients for defining a complex polynomial.

[00100] At block 406, the coefficients of the polynomial are defined and the

roots of the polynomial are calculated. From the vector a as defined hereinabove in block 404 and α _o = -l , the following complex polynomial is defined, wherein z is a complex variable:

M

∑a _n z ^~ " = 0 Equation 31 n=0

[00101] The roots z _m of the complex polynomial are then calculated, wherein m = 0, 1, ... , M - 1.

[00102] Then, at block 408, estimates of the frequencies f _m , wherein m = 0, 1, ... , M - 1 , are calculated from the following equation:

z_ _ = _o e)'2πf _m T Equation 32

[00103] At block 410, using the roots z _m = λ _m calculated at block 406, a vector c pertaining to amplitudes is calculated, such that:

P d = c , Equation 33

wherein:

C = [C ₁ C ₂ ^C M ] ⁷

1,1 1,2 ^p υ M

P = 2,1 ' 2,2 ¹ 2 M

I=]

[00104] At block 412, from the components of vector c calculated in block 410 hereinabove and the roots z _m = λ _m calculated at block 406, estimates of the

M complex amplitudes A _1n , wherein m = 0, 1, ... , M - 1 , are calculated from the following equation:

A _m Equation 34

[00105] At block 414, as an optional feature, the DFT frequency samples S _m (k) , /w = 0, 1, ... , M - I ₁ of each complex single-tone signal making up the complex multi-tone signal and the DFT frequency samples S(k) of the multi- tone signal can be reconstructed. This is accomplished similarly to block 214 of process 200 of Figure 3.

[00106] For the case of a complex single-tone signal with frequency / , with m, > 0 , m ₂ ≥ 0 and m _λ ≠ m ₂ , m _x and m ₂ integers, the frequency / can be obtained using: e, ² ^-^ ^)β - _{= R} - ^\ _b . Equation 35

κ-\

1=0 I _{0 +} L ₂

C(λ _l ,τ) = ∑ 5 ^* (* _I ,/)5(* ₁ ,/ + τ)

/=/,,

wherein L ₂ ≥ 0 .

[00107] A fourth non-restrictive illustrative embodiment of the process 100 of Figure 2 will now be described in Figure 6 as process 500. Process 500 is

used for estimating parameters of a real multi-tone signal s(t) made up of at least one single-tone signal.

[00108] It is to be noted that process 500 is adapted from process 400, since a real single-tone signal s(t) can always be viewed as the sum of two complex single-tone signals.

[00109] Referring to Figure 6, the process 500 for estimating parameters of a real multi-tone signal s(t) made up of at least one single-tone signal will now be described according to the fourth non-restrictive illustrative embodiment of process 100. The steps of the process 500 are indicated by blocks 502 to 514.

[00110] It is to be understood that blocks 502 to 514 of process 500 are specific implementations of the associated general blocks 102 to 114 of process 100 from Figure 2.

[00111] The process 500 starts at block 502 where time samples of the multi-tone signal are generated. A total of N ₇ = N + 2M + L + L ₀ samples s(lT) , I ₀ ≤ l < l _o +N _r are generated wherein: M is the number of tones in the signal, N is the length of the DFT and L and L ₀ are integers with L ≥ 0 and L ₀ ≥ 0 .

[00112] From the time samples, the DFT frequency samples S(Jc ₁ J) , k ₀ , Jt ₁ , ..., k _κ ^ , are calculated for successive time frames /. This is accomplished similarly to block 402 of process 400 of Figure 5 with the exception that the signal s{t) is a real signal made up of M real single-tone signals.

[00113] The process 500 uses mixed auto-correlations of the DFT frequency samples S(k,l) over successive time frames / . More specifically:

/„+/,

C(k,m,n,τ) = Y ^x ¥(k,l + M,m)ψ ^t (k,l + M + τ,n) t _k , . Equation 36 ψ(k,i,m) = S(k,i + m) + S(k,i -m)

[00114] At block 504, a system of linear equations is built. From the N DFT frequency samples S(k,l) of any time frames / , K DFT frequency samples are selected and mixed auto-correlations of S(k,l) over successive time frames are calculated for each selected frequency samples. The K frequency samples are indexed by k ₀ , k _v ..., k _κ _ _λ . It is to be noted that in general, an index of the K frequency samples is denoted by k _t .

[00115] More specifically, the resulting system of linear equations is:

b = Ra Equation 37

wherein:

a = [α, α ₂ ... a _u \

R, 1,1 R, 1,2 R \,M

R 2 1 ^ ₂ 2.2 R

R = ^■ 2,M

b _m =±-∑Re{C(k,,m,0,L _Q )}

^ ,=0 κ-\

^., _n = ∑Re{C(λ _I , ^/ _W , ^M λ)}

I _{0 +} L

C(k _l ,m,n,τ) = ∑ψ(k _ι ,l + M,m)ψ (k _l J + M + τ,n)

I=I ₀ ψ(k,,h,m) = S(k _ι ,h + m) + S(k,,h-m)

and L ≥ 0 and L ₀ ≥ 0 .

[00116] The solution of the system of linear equations is then calculated, such that:

R ^" 'b = a , Equation 38

defining the intermediate vector a .

[00117] The components of vector a are to be used as coefficients for defining a complex polynomial.

[00118] At block 506, the coefficients of the polynomial are defined and the roots of the polynomial are calculated. From the vector a as defined hereinabove in block 504, the following complex polynomial is defined, wherein z is a complex variable:

M

J] a _n z-" = 0 Equation 39 n=-M

with a_ _n = a _n and α ₀ = -1.0.

[00119] The roots z _m of the complex polynomial are then calculated, wherein m = 0, 1, ... , 2M - I . As it is known by those skilled in the art, because the signal is real, roots always come in pairs: for any root z _m , there is a root z _m which is the conjugate of z _m .

[00120] Then, at block 508, estimates of the frequencies f _m , wherein m = 0, 1, ... , M - 1 , are calculated from the following equation:

z _m = χ _m = _e ^J2 * ^f - ^T Equation 40

wherein the roots z _m used are those with positive imaginary part.

[00121] At block 510, using the frequencies f _m calculated at block 508, a

vector c pertaining to amplitudes is calculated, such that:

P d = C, Equation 41

wherein:

C = =[ I<C ₁ "M .

d _m =^∑∞ _S (2π{l ₊ L _o )fj)ψ(k,,l _{o +} L _{2 +} M,l)

P _n , _n =£cos (2π (I ₊ L ₀ ) fj) cos {2π If _n T) ι=\ ψ(k,,h,l) = S(k _l ,h + l) + S(k,,h-l)

and L ₁ ≥ 1

[00122] At block 512, from the components of vector c calculated in block 510 hereinabove and the frequencies f _m calculated at block 508, the parameter

P _1n is calculated such that:

Equation 42

[00123] Then, estimates of the M complex amplitudes A _1n , wherein m = 0, 1, ... , M - 1 , are calculated from the following equation:

Equation 43

[00124] At block 514, as an optional feature, the DFT frequency samples S _m (k) , m = 0, 1, ... , M -I , of each real single-tone signal making up the real multi-tone signal and the DFT frequency samples S(k) of the multi-tone signal can be reconstructed. This is accomplished similarly to block 314 of process 300 of Figure 4.

[00125] For the case of a real single-tone signal with frequency / , with /n, > 0 , m ₂ > 0 and m _x ≠ m ₂ , m _x and m ₂ integers, the frequency / can be obtained using:

cos(2πmJT)_ _{=i R} -ι _b . Equation 44 cos(2τrm ₂ /r)

C(k,,m) = ∑ ψ(k,,l,m)ψ (k,,l,θ) l=l _o +m

ψ(k _l J,m) = S(k _l ,l + m) + S(k _l ,l -m)

wherein L ₂ ≥ 0 .

[00126] It is to be understood that although the reconstruction of the DFT frequency samples at block 214, 314, 414 and 514 uses the estimated frequencies and amplitudes of the multi-tone signal, the exact values of the frequencies and amplitudes, as well as estimates of the frequencies and amplitudes obtained from other methods or means, may also be used.

Theoretical background

[00127] In the present invention, the DFT is used as a linear transformation as defined in vector space theory [8]. As a linear transformation, the DFT of length N can be represented by a transformation matrix composed of N vectors:

w,, = [l w _k w _k ² ... wf ¹ J Equation 45

wherein k = 0,1,...,N-I and w _k = e ^~J~ * ^~ is defined in Equation 1.

[00128] The set of N vectors w _{t l} k = 0,1,...,N-I , of the DFT transformation matrix forms an orthogonal basis of the vector space

τ [N, m = n _ w w _n H . Equation 46

[ 0, m ≠ n

[00129] The time samples s(nT) of the signal s(t) are projected on vector k of the DFT transformation matrix to give the DFT frequency sample S(k) :

N-I

S(k) = ∑s(nT)w _k " Equation 47 n=0

[00130] For a complex single-tone signal with frequency / and amplitude A , the time samples s(nT) and the DFT frequency samples are given by:

s(nT) = Ae ^j2πnβ' S(k) = ∑Ae ^JlπnfT w _k " , Equation 48

«=0

_ P

\ - w _k λ

wherein: λ = e ^]2πfτ and p = A[\ -λ ^N ) .

[00131] Multiplying both side of Equation 48 by the denominator, it is

possible to set the following linear equation:

S(k) = [l S(k)w _k ] Equation 49 λ

[00132] Using two DFT frequency samples S(k _Q ) and S(^ ₁ ) , it is possible to build the following system of linear equations:

Equation 50

[00133] Providing the matrix is non-singular, intermediate vector [p λf can be calculated from which the frequency / and the amplitude A can be obtained.

[00134] For a complex multi-tone signal, using the linearity property of the DFT, the DFT frequency sample S(k) is given by:

M-I

*« = σ Equation 51 to l -wλ

[00135] It is possible to show that the DFT frequency sample S(k) in Equation 51 is also given by:

M-I a w'

S(k) = - /1=0

M-X Equation 52

^{1 + w} * ∑δ» ₊ 1 ^W * n=0

[00136] Multiplying both side of Equation 52 with the denominator on the right and rearranging the equation gives:

M-I M-X s(k) = ∑ a _n w; -s(k)w _k ∑ b _n+ y _k Equation 53

/1=0 n=0

and the DFT value on the left is a linear combination of the unknown parameters a _n and b _n+] for « = O,1,...,M -1. The complete system of 2M linear equations with IM unknowns of block 204 of Figure 3 can be established, and providing the matrix is non-singular, the intermediate unknown parameters a _n and b _n+x for n = 0,\,...,M -\ can be calculated. It can be shown that all the frequencies f _m and amplitudes A _1n , m - 0,\,...,M -1 , can be recovered from the intermediate parameters a _n and b _n+λ .

[00137] The DFT frequency sample S(k) of a real single-tone signal is given by:

,ST(Ar) = ^p + ^p , . Equation 54 v ^; l - w,λ \ -w, λ

[00138] Merging the two rational functions, the DFT frequency sample S(k) of a real single-tone signal is given by:

S(k) = ^{Wkq r} , Equation 55 u _k -μ

wherein: q , r , μ and u _k are given in Equation 1.

[00139] Multiplying both side of Equation 55 by the denominator and rearranging the equation gives:

q

S(k)u _k = [w _k -1 S(k)] r Equation 56 μ

[00140] The vector of unknown parameters on the right being real, the last complex linear equation can be split into two real linear equations:

Equation 57

[00141] A set of three linear equations can be built to have a complete system of linear equations. The solution of this system of linear equations gives intermediary parameters q , r and μ from which it is possible to get the real frequency / and the complex amplitude A of the real single-tone signal.

[00142] With the linearity property of the DFT, it is possible to show that the system of linear equations of block 304 of Figure 4 can be built.

[00143] Although the present invention has been described by way of illustrative embodiments and examples thereof, it should be noted that it will be apparent to persons skilled in the art that modifications may be applied to the present particular embodiment without departing from the scope of the present invention.

REFERENCES

[1] R. Prony, "Essa : Experimentale et analytique," J. Ecole Polytechnique, pp. 24-76, 1795.

[2] V. Pisarenko, "The retrieval or harmonies from a covariance function," Geophys. J. R. Astron. Soc, vol. 33, pp. 347-366, 1973.

[3] R. Schmidt, "Multiple emitter location and signal parameter estimation," IEEE Trans. Antennas and Propagation, vol. AP34, pp. 276-280, Mar. 1986.

[4] R. Roy, A. Paulraj, and T. Kailath, "Esprit : A subspace rotation approach to estimation of parameters of cisoids in noise," IEEE Trans. Acoustics, Speech and Signal Processing, vol. ASSP34, pp. 1340-1342, Oct. 1986.

[5] H. So and F. W. Chan, "A generalized weighted linear predictor frequency estimation approach for a complex sinusoid," IEEE Trans, on Signal Processing, vol. 54, pp. 1304- 1315, Apr. 2006.

[6] S. Kay, "A fast and accurate single frequency estimator," IEEE Trans. Acoustics, Speech and Signal Processing, vol. ASSP37, pp. 1987-1989, Dec. 1989.

[7] P. Stoica, R. Moses, T. Soderstrom, and J. Li, "Optimal high-order Yule- Walker estimation of sinusoidal frequencies," IEEE Trans, on Signal Processing, vol. 39, pp. 1350-1368, June 1991.

[8] K. Hoffman and R. Kunze, "Linear Algebra," Englewood Cliffs, NJ: Prentice- Hall, 1971.