METHOD FOR APPLYING A DISCRETE FOURIER TRANSFORM, DFT, TO A SEQUENCE OF SAMPLES OF A SENSOR SIGNAL, PROCESSOR CIRCUIT FOR PERFORMING THE METHOD, RADAR SENSOR AND MOTOR VEHICLE

Abstract

A method for applying a Discrete Fourier Transform (DFT) to a sequence of N samples of a sensor signal, with N>2. The resulting DFT spectral coefficients are updated iteratively whenever a new one of the samples or a sub-group of consecutive new samples, comprising a predefined number J of samples, with 1<J<N, is received.

Claims

1. A method for applying a P-dimensional discrete Fourier transform (DFT) to a sequence of N samples of a sensor signal, with P, N>2, comprising: receiving one of the samples at a time at a processor circuit; and performing the following in response to receiving a new one of the samples or a group of consecutive new samples, comprising a predefined number J of samples, with 1<J<N providing, for each new sample x.sub.n, an order index n indicating which one of the 1 to N samples has been received, wherein n in 1, . . . , N, proving, for each new sample, a corresponding DFT vector {right arrow over (d)}.sup.(n), wherein the DFT vector {right arrow over (d)}.sup.(n) is selected or generated depending on the order index n of the sample, wherein the DFT vector {right arrow over (d)}.sup.(n) comprises P phasor values that are derived from frequency points f.sub.p of the P-dimensional DFT by S*exp(i 2 f.sub.p t.sub.n) with p in 1, . . . , P the index of the phasor value in the DFT vector {right arrow over (d)}.sup.(n) and S a scaling factor and t.sub.n the sampling time of the new sample x.sub.n and i the imaginary unit with i.sup.2=1; applying the respective new sample x.sub.n as a multiplication factor to its corresponding DFT vector {right arrow over (d)}.sup.(n) for generating a respective spectral contribution vector {right arrow over (y)}.sup.(n)={right arrow over (d)}.sup.(n) x.sub.n; adding the respective spectral contribution vector {right arrow over (y)}.sup.(n) to an accumulation vector {right arrow over (y)}.sup.(n)={right arrow over (y)}.sup.(n)+{right arrow over (y)}.sup.(n-1), when for all N samples their corresponding resulting contribution vector has been added to the accumulation vector, providing the accumulation vector {right arrow over (y)}.sup.(N) as DFT spectral coefficients of the N samples.

2. The method according to claim 1, further comprising deleting the respective new sample when the corresponding contribution vector for that sample is calculated and deleting the respective contribution vector after adding it to the accumulation vector, such that at no point in time all N samples x.sub.n, with n in 1, . . . , N, nor their resulting contribution vector {right arrow over (y)}.sup.(n) are stored together in the processor circuit.

3. The method according to claim 1, further comprising: generating at least some or all of the samples at sampling times with constant sampling period t.sub.0, resulting in t.sub.n=t.sub.n-1+t.sub.0 for n in 2, . . . N and t.sub.1 an initial time value, in particular t.sub.1=0; and generating the respective DFT vector {right arrow over (d)}.sup.(n) for the respective sample x.sub.n of order index n using a P-dimensional base DFT vector {right arrow over (d)}.sup.(0) and the DFT vector {right arrow over (d)}.sup.(n-1) by applying an element-wise multiplication {right arrow over (d)}.sup.(n)=diag{{right arrow over (d)}.sup.(0)}{right arrow over (d)}.sup.(n-1), if n>1 and diag{} the diagonal matrix, wherein {right arrow over (d)}.sup.(0) comprises phasor elements exp(i 2 f.sub.p t.sub.0) with p in 1, . . . , P.

4. The method according to claim 1, further comprising: generating at least some or all of the samples at non-equidistant sampling times t.sub.n; providing a rasterized time pattern by defining a minimum time step width {circumflex over (t)}.sub.0; and generating the respective DFT vector {right arrow over (d)}.sup.(n) for the respective sample of order index n using a P-dimensional base DFT vector {right arrow over ({circumflex over (d)})}.sup.(0) and the DFT vector {right arrow over (d)}.sup.(n-1) by applying a element-wise multiplication, wherein {right arrow over ({circumflex over (d)})}.sup.(0) comprises phasor elements exp(i 2 f.sub.p {circumflex over (t)}.sub.0) with p in 1, . . . , P and a time difference t.sub.nt.sub.n-1 of sampling time of the last sample x.sub.n and the preceding sample x.sub.n-1 is expressed as the integer multiple or the next larger integer multiple or the next smaller integer multiple $=\left[\frac{t_n-t_{n-1}}{{\hat{t}}_0}\right]$ of {circumflex over (t)}.sub.0, with [] the rounding operator, such that {right arrow over (d)}.sup.(n)=diag{{right arrow over ({circumflex over (d)})}.sup.(0)}.sup. {right arrow over (d)}.sup.(n-1).

5. The method according to claim 1, further comprising: generating at least some or all of the samples at non-equidistant sampling times t.sub.n; and keeping stored M>1 pre-calculated vectors diag{{right arrow over ({circumflex over (d)})}.sup.(m)} for different time values {{circumflex over (t)}.sub.1, . . . , {circumflex over (t)}.sub.M} are kept stored in memory as {right arrow over ({circumflex over (d)})}.sup.(m), m=1 . . . M, with phasor elements exp(i 2 f.sub.p {circumflex over (t)}.sub.m), p=1, . . . , P, and for a given sample x.sub.n at sampling time t.sub.n the vector for index m=arg min|{t.sub.nt.sub.n-1{circumflex over (t)}.sub.m}| with the closest time-difference is applied by element-wise multiplication to the preceding DFT vector for providing the DFT vector {right arrow over (d)}.sup.(n)=diag{{right arrow over ({circumflex over (d)})}(m)}{right arrow over (d)}.sup.(n-1) for n>1.

6. The method according to claim 1, further comprising receiving the new sample x.sub.n from a first channel .sub.1 giving a new first-channel sample x(t.sub.n, .sub.1) and receiving together with this new first-channel sample at least one further new sample x(t.sub.n, .sub.c) for at least one further channel c, such that overall a respective new sample of C channels are received and transforming the new samples x(t.sub.n, .sub.c), c=1, . . . , C, together for each channel, c=1, . . . , C.

7. The method according to claim 1, further comprising: generating at least some or all of the samples at non-equidistant sampling times t.sub.n; and providing for M>1 a set of possible time step widths $\left\{{\stackrel{}{t}}_1,.Math.,{\stackrel{}{t}}_M\right\}$ and for sample x.sub.n it is taken that time step {circumflex over (t)}.sub.m that is closest to the time difference t.sub.nt.sub.n-1 of two consecutive samples ${\stackrel{.fwdarw.}{d}}^{\left(n\right)}=\mathrm{diag}\left\{\stackrel{\widehat{.fwdarw.}}{d}\left(m\right)\right\}{\stackrel{.fwdarw.}{d}}^{\left(n-1\right)}\mathrm{for}n>1\mathrm{and}m=1,.Math.,M$ with ${\stackrel{\widehat{.fwdarw.}}{d}}^{\left(m\right)}=\left(\begin{array}{c}\exp \left(-i2f_1{\hat{t}}_m\right)\\ \exp (-i2f_2{\hat{t}}_m\\ .Math.\\ \exp \left(-i2f_P{\hat{t}}_m\right)\end{array}\right)\mathrm{and}$ $m=\arg \min .Math.\left\{t_n-t_{n-1}-{\hat{t}}_m\right\}.Math..$

8. The method according to claim 1, further comprising: generating at least some or all of the samples at non-equidistant sampling times t.sub.n; and successively approximating the respective time difference t.sub.nt.sub.n-1 of two consecutive samples x.sub.n-1 and x.sub.n, wherein for a maximum time difference max {t.sub.nt.sub.n-1}={circumflex over (t)} for the respective order index n and a time difference resolution of M bits, a minimum time step becomes $\frac{\hat{t}}{2^M}$ and for given time difference t.sub.nt.sub.n-1{circumflex over (t)}, a combination of predefined time steps is obtained in that the time difference between the current and the previous sample is t.sub.n=t.sub.nt.sub.n-1 and t.sub.n is quantised with M bits, wherein m=1 represents the most significant bit and m=M the least significant bit, wherein the approximations starts with a time difference of .sub.1=t.sub.n, the quantisation level is defined by $T_m=\frac{\stackrel{}{t}}{2^m},$ for m=1, it becomes $T_1=\frac{\hat{t}}{2},$ and the m-th bit follows from $w_m=.Math.\frac{{}_m}{T_m}.Math.$ with ${}_m={}_{m-1}-w_{m-1}{T}_{m-1}\mathrm{for}m>1$ ${}_m=t_n\mathrm{for}m=1$ the quantised time difference. denotes the floor operator and for m=1, $w_1=.Math.\frac{t_n}{T_1}.Math..$ with all bits computed, the binary word is represented by vector $\stackrel{.fwdarw.}{w}={\left(\begin{array}{cccc}{w}_1& w_2& .Math.& w_M\end{array}\right)}^T$ with w.sub.m{0,1} for m=1, . . . , M and for a set of possible step widths following from T.sub.m $\left\{{\stackrel{}{t}}_1,.Math.,{\stackrel{}{t}}_M\right\}=\left\{T_1,T_2,.Math.,T_M\right\}$ the quantised time difference is calculated as $=\left(\begin{array}{cccc}{T}_1& T_2& .Math.& T_M\end{array}\right)\stackrel{.fwdarw.}{w}={.Math.}_{m=1}^M{w}_m{T}_m,$ which is mapped to the sub-set of predefined DFT vectors (37) needed to obtain the DFT vector {right arrow over (d)}.sup.(n) for the current time instant t.sub.n: ${\stackrel{.fwdarw.}{d}}^{\left(n\right)}={.Math.}_{w_m}\mathrm{diag}\left\{w_m\stackrel{\widehat{.fwdarw.}}{d}\left(m\right)\right\}{\stackrel{.fwdarw.}{d}}^{\left(n-1\right)}\mathrm{for}{w}_m=1\mathrm{and}m=1,.Math.,M,$ wherein only those predefined vectors {right arrow over ({circumflex over (d)})}.sup.(m) are selected for which w.sub.m=1.

9. The method according to claim 1, further comprising providing the DFT as a IIR filter-bank implementation of the sample-wise DFT.

10. The method according to claim 1, further comprising: providing the radar signal by a radar sensor; and providing, by the processor circuit, the DFT spectral coefficients to a assistance system that controls driving motions of a vehicle and that detects at least one object in an environment of the vehicle based on the DFT spectral coefficients.

11. A processor circuit for applying a P-dimensional discrete Fourier transform (DFT) to a sequence of N samples of a sensor signal, with P, N>2, and configured to: receive one of the samples at a time; and perform the following in response to receiving a new one of the samples or a group of consecutive new samples, comprising a predefined number J of samples, with 1<J<N provide, for each new sample x.sub.n, an order index n indicating which one of the 1 to N samples has been received, wherein n in 1, . . . , N, prove, for each new sample, a corresponding DFT vector {right arrow over (d)}.sup.(n), wherein the DFT vector {right arrow over (d)}.sup.(n) is selected or generated depending on the order index n of the sample, wherein the DFT vector {right arrow over (d)}.sup.(n) comprises P phasor values that are derived from frequency points f.sub.p of the P-dimensional DFT by S*exp(i 2 f.sub.p t.sub.n) with p in 1, . . . , P the index of the phasor value in the DFT vector {right arrow over (d)}.sup.(n) and S a scaling factor and t.sub.n the sampling time of the new sample x.sub.n and i the imaginary unit with i.sup.2=1; apply the respective new sample x.sub.n as a multiplication factor to its corresponding DFT vector {right arrow over (d)}.sup.(n) for generating a respective spectral contribution vector {right arrow over (y)}.sup.(n)={right arrow over (d)}.sup.(n)x.sub.n; and add the respective spectral contribution vector {right arrow over (y)}.sup.(n) to an accumulation vector {right arrow over (y)}.sup.(n)={right arrow over (y)}.sup.(n)+{right arrow over (y)}.sup.(n-1), when for all N samples their corresponding resulting contribution vector has been added to the accumulation vector, provide the accumulation vector {right arrow over (y)}.sup.(N) as DFT spectral coefficients of the N samples.

12. A RADAR device, comprising: a sensor for generating a sensor signal; and a processor circuit for applying a P-dimensional discrete Fourier transform (DFT) to a sequence of N samples of the sensor signal, with P, N>2, and configured to receive one of the samples at a time, and perform the following in response to receiving a new one of the samples or a group of consecutive new samples, comprising a predefined number J of samples, with 1<J<N provide, for each new sample x.sub.n, an order index n indicating which one of the 1 to N samples has been received, wherein n in 1, . . . , N, prove, for each new sample, a corresponding DFT vector {right arrow over (d)}.sup.(n), wherein the DFT vector {right arrow over (d)}.sup.(n) is selected or generated depending on the order index n of the sample, wherein the DFT vector {right arrow over (d)}.sup.(n) comprises P phasor values that are derived from frequency points f.sub.p of the P-dimensional DFT by S*exp(i 2 f.sub.p t.sub.n) with p in 1, . . . , P the index of the phasor value in the DFT vector {right arrow over (d)}.sup.(n) and S a scaling factor and t.sub.n the sampling time of the new sample x.sub.n and i the imaginary unit with i.sup.2=1; apply the respective new sample x.sub.n as a multiplication factor to its corresponding DFT vector {right arrow over (d)}.sup.(n) for generating a respective spectral contribution vector {right arrow over (y)}.sup.(n)={right arrow over (d)}.sup.(n) x.sub.n; and add the respective spectral contribution vector {right arrow over (y)}.sup.(n) to an accumulation vector {right arrow over (y)}.sup.(n)={right arrow over (y)}.sup.(n)+{right arrow over (y)}.sup.(n-1), when for all N samples their corresponding resulting contribution vector has been added to the accumulation vector, provide the accumulation vector {right arrow over (y)}.sup.(N) as DFT spectral coefficients of the N samples.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0055] In the following an exemplary implementation of the invention is described. The figures show:

[0056] FIG. 1 a schematic illustration of a signal flow of an embodiment of the inventive streaming discrete fourier transform (DFT);

[0057] FIG. 2 a schematic illustration of an implementation as IIR filter;

[0058] FIG. 3 a schematic illustration of an implementation as a IIR filter-bank implementation of the sample-wise DFT;

[0059] FIG. 4 a schematic illustration of an example data flow for a streaming DFT implementation;

[0060] FIG. 5 a schematic illustration of data a flow for a streaming DFT implementation when the DFT vectors are recursively computed;

[0061] FIG. 6 a schematic illustration of a memory usage for streaming DFT implementations;

[0062] FIG. 7 a schematic illustration of a data flow for a streaming with column-wise DFT implementation;

[0063] FIG. 8 a schematic illustration of a data flow for a streaming, column-wise DFT implementation;

[0064] FIG. 9 a schematic illustration of an M-bit successive approximation of time difference;

[0065] FIG. 10 a schematic illustration of a sequence chart for dynamic computation of DFT coefficients suited for non-equidistant sampling;

[0066] FIG. 11 a schematic illustration of a dynamic computation of DFT coefficients suited for non-e-quidistant sampling (split into FIG. 11a, 11b, 11c); and

[0067] FIG. 12 a schematic illustration of a motor vehicle according to the invention.

DETAILED DESCRIPTION

[0068] In the embodiment described below, the described components of the embodiment each represent individual features which are to be considered independently of each other and which each develop the disclosure also independently of each other and thereby are also to be regarded as a component of the disclosure in individual manner or in another than the shown combination. Furthermore, the described embodiment can also be supplemented by further features of the disclosure already described.

[0069] In the figures elements that provide the same function are marked with identical reference signs.

1. General Setup

[0070] FIG. 1 shows an example implementation as a high-level signal flow of the streaming discrete fourier transform (DFT). The stream of time samples comprises Sample 1 to Sample N. The spectral contribution of each time sample is added to the spectrum obtained until current time instant. The illustrated steps can be performed by an processor circuit and implemented by computer-readable instructions and/or by hard-wired processing logic (e.g. as ASIC).

[0071] FIG. 1 depicts an abstract signal flow of the streaming DFT. The basic operation is a follows: [0072] A signal sample 1 at time t.sub.1 is fed to an outer-product component. This multiplies the sample 1 with a DFT vector at time t.sub.1. The DFT vector comprises one complex element per frequency, i.e., for P frequencies, the DFT vector is of length P. The output of the outer-product operation is then added to the initial spectrum, which can be a zero vector or any other preloaded vector with one complex element per frequency. It results in a spectrum that represents the time period until t.sub.1. [0073] When a 2nd signal sample 2 at time t.sub.2 arrives, the corresponding DFT vector at time t.sub.2 is multiplied with the signal sample 2 by the outer-product component. The output is then added to the spectrum that has been computed for the period until time t.sub.1 to eventually represent the spectrum for the time period until t.sub.2

[0074] This is repeated as long as all time samples 1, 2, . . . , N of consideration are processed to obtain the DFT-transformed signal for the period t.sub.1, t.sub.2, . . . , t.sub.N.

2. Description: From DFT to Streaming DFT

[0075] A signal sampled at time instants t.sub.1, . . . , t.sub.N as given by vector

[00015]$\begin{array}{cc}\stackrel{.fwdarw.}{x}=\left(\begin{array}{c}x\left(t_1\right)\\ x\left(t_2\right)\\ .Math.\\ x\left(t_N\right)\end{array}\right)=\left(\begin{array}{c}{x}_1\\ x_2\\ .Math.\\ x_N\end{array}\right)& \left(1\right)\end{array}$

shall be transformed over the given period via a DFT. With the DFT matrix

[00016]$\begin{array}{cc}\tilde{D}=\frac{1}{N}\left(\begin{array}{cccc}\exp \left(-i2f_1{t}_1\right)& \exp \left(-i2f_1{t}_2\right)& .Math.& \exp \left(-i2f_1{t}_N\right)\\ \exp \left(-i2f_2{t}_1\right)& \exp \left(-i2f_2{t}_2\right)& .Math.& \exp \left(-i2f_2{t}_N\right)\\ .Math.& .Math.& & .Math.\\ \exp \left(-i2f_P{t}_1\right)& \exp \left(-i2f_P{t}_2\right)& .Math.& \exp \left(-i2f_P{t}_N\right)\end{array}\right)& \left(2\right)\end{array}$

with N the number of time samples, t.sub.1, . . . , t.sub.N the sampling time instants, P the number of frequencies and f.sub.1, . . . , f.sub.p the frequency points, the DFT of {right arrow over (x)}(1) follows from

[00017]$\begin{array}{cc}\stackrel{.fwdarw.}{y}=\tilde{D}\stackrel{.fwdarw.}{x}.& \left(3\right)\end{array}$

This, however, requires the full vector {right arrow over (x)}, i.e., all signal samples have to be stored until the last sample N is available before invoking the DFT computation.

[0076] In lieu of capturing firstly all time samples, the contribution of each sample to the DFT spectrum can be computed per each time instant separatelyor per subset of all time samples as discussed later. The individual samples Sample 1 to Sample N of a signal sampled in time are consecutively fed to an outer-product component. It consecutively multiplies each sample x.sub.n=x(t.sub.n) with the respective DFT vector

[00018]$\begin{array}{cc}\begin{array}{c}{\stackrel{.fwdarw.}{d}}^{\left(n\right)}=\stackrel{.fwdarw.}{d}\left(t_n\right)\\ =\frac{1}{N}\left(\begin{array}{c}{d}_1^{\left(n\right)}\\ d_2^{\left(n\right)}\\ .Math.\\ d_P^{\left(n\right)}\end{array}\right)\\ =\frac{1}{N}\left(\begin{array}{c}d\left(f_1,t_n\right)\\ d\left(f_2,t_n\right)\\ .Math.\\ d\left(f_P,t_N\right)\end{array}\right)\\ =\frac{1}{N}\left(\begin{array}{c}\exp \left(-i2f_1{t}_n\right)\\ \exp \left(-i2f_2{t}_n\right)\\ .Math.\\ \exp \left(-i2f_P{t}_n\right)\end{array}\right)\end{array}& \left(4\right)\end{array}$

with n=1, . . . , N. The DFT vector {right arrow over (d)}.sup.(n) corresponds with the n-th column of the DFT matrix {tilde over (D)}(2). The output vector

[00019]$\begin{array}{cc}{\stackrel{.fwdarw.}{y}}^{\left(n\right)}={\stackrel{.fwdarw.}{d}}^{\left(n\right)}{x}_n& \left(5\right)\end{array}$

is then added to the spectrum {right arrow over (y)}.sup.(n-1) that has been obtained for the period t.sub.1 . . . t.sub.n-1. Thus

[00020]$\begin{array}{cc}{\stackrel{.fwdarw.}{y}}^{\left(n\right)}={\stackrel{.fwdarw.}{y}}^{\left(n\right)}+{\stackrel{.fwdarw.}{y}}^{\left(n-1\right)}={\stackrel{.fwdarw.}{d}}^{\left(n\right)}{x}_n+{\stackrel{.fwdarw.}{y}}^{\left(n-1\right)}& \left(6\right)\end{array}$

yields the spectrum for the period t.sub.1 . . . t.sub.n with {right arrow over (y)}.sup.(0)={right arrow over (0)}.

[0077] FIG. 2 illustrates an implementation as IIR filter (IRRinfinite impulse response) in transposed direct-form II implementation of the sample-wise DFT for frequency point f.sub.p using an adaptive feedfoward coefficient

[00021]$d_p^{\left(n\right)}$

in (4).

[0078] Equation (6) can be considered a difference equation of an infinite impulse response (IIR) filter bank. Each frequency point f.sub.p corresponds with an IIR filter that comprises an adaptive filter coefficient in the forward branch. For each element in

[00022]$\begin{array}{cc}{\stackrel{.fwdarw.}{y}}^{\left(n\right)}=\left(\begin{array}{c}{y}_1^{\left(n\right)}\\ y_2^{\left(n\right)}\\ .Math.\\ y_P^{\left(n\right)}\end{array}\right)=\left(\begin{array}{c}y\left(f_1,t_n\right)\\ y\left(f_2,t_n\right)\\ .Math.\\ y\left(f_P,t_n\right)\end{array}\right)& \left(7\right)\end{array}$

represents a frequency point of the spectrum, the p-th frequency point is obtained from

[00023]$\begin{array}{cc}{y}_p^{\left(n\right)}=d_p^{\left(n\right)}{x}_n+y_p^{\left(n-1\right)}.& \left(8\right)\end{array}$

[0079] FIG. 2 shows the implementation of difference equation (8) as an IIR filter of feedback order 1. The feedforward coefficients read

[00024]$\begin{array}{cc}{\stackrel{.fwdarw.}{b}}_{p,n}=\left(d_p^{\left(n\right)}\right),& \left(9\right)\end{array}$

which reduce to a single adaptive coefficient and the feedback coefficients read

[00025]$\begin{array}{cc}\stackrel{.fwdarw.}{a}=\left(\begin{array}{c}1\\ -1\end{array}\right).& \left(10\right)\end{array}$

[0080] FIG. 3 illustrates an implementation as a IIR filter-bank implementation of the sample-wise DFT (6) with one IIR filter element per frequency. Each IIR filter comprises an adaptive feedforward coefficient.

[0081] The implementation of the vector difference equation (6) as an adaptive IIR filter bank is depicted in FIG. 3. Each frequency f.sub.p with p=1, . . . , P is mapped to its respective IIR filter with an adaptive feedforward coefficient

[00026]$d_p^{\left(n\right)}$

(9).

3. Algorithmic Implementation

[0082] FIG. 4 illustrates an example data flow for a streaming DFT implementation when the DFT matrix as a whole is given. The syntax for the indices is for DFT matrix {tilde over (D)} and DFT vectors {right arrow over (d)}.sup.(n), for {right arrow over (x)} and for the spectral vectors {right arrow over (y)}.sup.(n), {right arrow over (y)}.sup.(0) and {right arrow over (y)}.sup.(n) with p=1, . . . , P and n=1, . . . , N.

[0083] The data flow of an embodiment of the streaming DFT algorithm is portrayed in FIG. 4. It relies on the following procedure: [0084] t=t.sub.1: Select 1st column of the DFT matrix {right arrow over (d)}.sup.(1) and multiply it with the 1st signal sample x.sub.1 to obtain the spectral contribution {right arrow over (y)}.sup.(1). [0085] Add {right arrow over (y)}.sup.(1) to the initial vector {right arrow over (y)}.sup.(0) to obtain the spectrum {right arrow over (y)}.sup.(1) at frequencies f.sub.1, . . . , f.sub.p for the 1st time sample. [0086] t=t.sub.2: Select 2nd column of the DFT matrix {right arrow over (d)}.sup.(2) and multiply it with the 2nd signal sample x.sub.2 to obtain the spectral contribution {right arrow over (y)}.sup.(2). [0087] Add {right arrow over (y)}.sup.(2) to the spectrum {right arrow over (y)}.sup.(1) to obtain the spectrum {right arrow over (y)}.sup.(2) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.2. [0088] . . . [0089] t=t.sub.n: Select n-th column of the DFT matrix {right arrow over (d)}.sup.(n) and multiply it with the n-th signal sample x.sub.n to obtain the spectral contribution {right arrow over (y)}.sup.(n). [0090] Add {right arrow over (y)}.sup.(n) to the spectrum {right arrow over (y)}.sup.(n-1) to obtain the spectrum {right arrow over (y)}.sup.(n) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.n. [0091] . . . [0092] t=t.sub.N: Select N-th (last) column of the DFT matrix {right arrow over (d)}.sup.(N) and multiply it with the N-th (last) signal sample x.sub.N to obtain the spectral contribution {right arrow over (y)}.sup.(N). [0093] Add {right arrow over (y)}.sup.(N) to the spectrum {right arrow over (y)}.sup.(N-1) to obtain the spectrum {right arrow over (y)}.sup.(N) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.N. [0094] {right arrow over (y)}.sup.(N) can then be used as the DFT of {right arrow over (x)}.

[0095] The advantage of a step-wise DFT computation lies in the reduced memory consumption needed for the signal samples x.sub.1, . . . , x.sub.N. As the spectral contribution of each sample is computed upon its availability, only a single value x.sub.n needs to be stored. Yet the total memory consumption is still high for storing PN elements of the DFT matrix.

[0096] The memory usage can be further reduced if an equi-distant sampling is given, i.e.,

[00027]$\begin{array}{cc}{t}_n=t_{n-1}+t_0& \left(11\right)\end{array}$

with t.sub.0 the sampling period. Then, the DFT vector {right arrow over (d)}.sup.(n) for a certain time instant t.sub.n can be obtained from the previous DFT vector {right arrow over (d)}.sup.(n-1) for the previous time instant t.sub.n-1 by

[00028]$\begin{array}{cc}{\stackrel{.fwdarw.}{d}}^{\left(n\right)}=\mathrm{diag}\left\{{\stackrel{.fwdarw.}{d}}^{\left(0\right)}\right\}{\stackrel{.fwdarw.}{d}}^{\left(n-1\right)}\mathrm{if}n>1& \left(12\right)\end{array}$

with {right arrow over (d)}.sup.(1) the initial DFT vector and the phasor's vector

[00029]$\begin{array}{cc}{\stackrel{.fwdarw.}{d}}^{\left(0\right)}=\left(\begin{array}{c}{d}_1^{\left(0\right)}\\ d_2^{\left(0\right)}\\ .Math.\\ d_P^{\left(0\right)}\end{array}\right)=\left(\begin{array}{c}\exp \left(-i2f_1{t}_0\right)\\ \exp \left(-i2f_2{t}_0\right)\\ .Math.\\ \exp \left(-i2f_P{t}_0\right)\end{array}\right).& \left(13\right)\end{array}$

diag{} denotes the diagonal matrix. {right arrow over (d)}.sup.(n) (12) basically follows from {right arrow over (d)}.sup.(n-1) by element-wise multiplication with {right arrow over (d)}.sup.(0) or

[00030]$\begin{array}{cc}{d}_p^{\left(n\right)}=d_p^{\left(n-1\right)}{d}_p^{\left(0\right)}\mathrm{if}n>1.& \left(14\right)\end{array}$

[0097] The initial or 1st DFT vector {right arrow over (d)}.sup.(1) can be set for an arbitrary time instant t.sub.1.

[0098] FIG. 5 illustrates an example data flow for a streaming DFT implementation when the DFT vectors are recursively computed, assuming an equi-distant sampling. As of t=t.sub.2, the respective DFT vector follows from the element-wise multiplication of the previous vector and the phasor's vector {right arrow over (d)}.sup.(0). The syntax for the indices is for DFT vectors {right arrow over (d)}.sup.(n), for {right arrow over (x)} and for the spectral vectors {right arrow over (y)}.sup.(n), {right arrow over (y)}.sup.(0) and {right arrow over (y)}.sup.(n) with p=1, . . . , P and n=1, . . . , N.

[0099] FIG. 5 depicts the data flow for a streaming DFT implementation leveraging an equi-distant sampling with period t.sub.0.

[0100] The algorithm works as follows: [0101] t=t.sub.1: Select the initial DFT vector {right arrow over (d)}.sup.(1) for an arbitrary time t.sub.1. For example,

[00031]$t_1=0,i.e.,{\stackrel{.fwdarw.}{d}}^{\left(1\right)}=\stackrel{.fwdarw.}{1}$$\mathrm{or}$$t_1=t_0,i.e.,{\stackrel{.fwdarw.}{d}}^{\left(1\right)}={\stackrel{.fwdarw.}{d}}^{\left(0\right)}.$ [0102] Multiply {right arrow over (d)}.sup.(1) with the 1st signal sample x.sub.1 to obtain the spectral contribution {right arrow over (y)}.sup.(1). [0103] Add {right arrow over (y)}.sup.(1) to the initial vector {right arrow over (y)}.sup.(0) to obtain the spectrum {right arrow over (y)}.sup.(1) at frequencies f.sub.1, . . . , f.sub.p for the 1st time sample. [0104] t=t.sub.2=t.sub.1+t.sub.0: Compute 2nd DFT vector {right arrow over (d)}.sup.(2) by element-wise multiplication of {right arrow over (d)}.sup.(1) and {right arrow over (d)}.sup.(0) (13). [0105] Multiply {right arrow over (d)}.sup.(2) with the 2nd signal sample x.sub.2 to obtain the spectral contribution {right arrow over (y)}.sup.(2). [0106] Add {right arrow over (y)}.sup.(2) to the spectrum {right arrow over (y)}.sup.(1) to obtain the spectrum {right arrow over (y)}.sup.(2) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.1+t.sub.0. [0107] . . . [0108] t=t.sub.n=t.sub.1+(n1)t.sub.0: Compute n-th DFT vector {right arrow over (d)}.sup.(n) by element-wise multiplication of {right arrow over (d)}.sup.(n-1) and {right arrow over (d)}.sup.(0) (13). [0109] Multiply {right arrow over (d)}.sup.(n) with the n-th signal sample x.sub.n to obtain the spectral contribution {right arrow over (y)}.sup.(n). [0110] Add {right arrow over (y)}.sup.(n) to the spectrum {right arrow over (y)}.sup.(n-1) to obtain the spectrum {right arrow over (y)}.sup.(n) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.1+ (n1)t.sub.0. [0111] . . . [0112] t=t.sub.N=t.sub.1+ (N1)t.sub.0: Compute N-th DFT vector {right arrow over (d)}.sup.(N) by element-wise multiplication of {right arrow over (d)}.sup.(N-1) and {right arrow over (d)}.sup.(0) (13). [0113] Multiply {right arrow over (d)}.sup.(N) with the N-th (last) signal sample x.sub.N to obtain the spectral contribution {right arrow over (y)}.sup.(N). [0114] Add {right arrow over (y)}.sup.(N) to the spectrum {right arrow over (y)}.sup.(N-1) to obtain the spectrum {right arrow over (y)}.sup.(N) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.1+ (N1)t.sub.0.
{right arrow over (y)}.sup.(N) can then be used as the DFT of {right arrow over (x)}.

[0115] FIG. 6 illustrates a memory usage for streaming DFT implementations: a-priori known DFT matrix (FIG. 4) (left-hand side) and DFT vector computed per n-th time instant (FIG. 5) (right-hand side). The size is given in slices of a certain data type.

[0116] FIG. 6 compares the memory usage of the implementation with a-priori known DFT coefficients as depicted in FIG. 4 and the implementation with the DFT vectors computed per n-th time instant as depicted in FIG. 5. For practically meaningful number of time samples N>2, the latter needs less memory. In both cases it is presumed that the delta vector {right arrow over (y)} and the output vector {right arrow over (y)} are overwritten for each new x.sub.1 when updated. The DFT vector {right arrow over (d)}.sup.(n) on the right-hand side of FIG. 6 is presumed to overwrite the previous vector {right arrow over (d)}.sup.(n-1) when multiplied by {right arrow over (d)}.sup.(0). The memory usage shown in FIG. 6 is given in slices of a certain data type. Data can be floating or fixed point and of any numeric type such as float or signed integer. The type can represent complex-valued or real-valued data.

4. Application to Sequences of Channel Impulse Responses

[0117] Let the input signal be a matrix

[00032]$\begin{array}{cc}\stackrel{}{x}=\left(\begin{array}{cccc}x\left(t_1,{}_1\right)& x\left(t_1,{}_2\right)& .Math.& x\left(t_1,{}_C\right)\\ x\left(t_2,{}_1\right)& x\left(t_2,{}_2\right)& .Math.& x\left(t_2,{}_C\right)\\ x\left(t_3,{}_1\right)& x\left(t_3,{}_2\right)& .Math.& x\left(t_3,{}_C\right)\\ .Math.& .Math.& & .Math.\\ x\left(t_N,{}_1\right)& x\left(t_N,{}_2\right)& .Math.& x\left(t_N,{}_C\right)\end{array}\right)=\left(\begin{array}{cccc}{x}_{1,1}& x_{1,2}& .Math.& x_{1,C}\\ x_{2,1}& x_{2,2}& .Math.& x_{2,C}\\ x_{3,1}& x_{3,2}& .Math.& x_{3,C}\\ .Math.& .Math.& & .Math.\\ x_{N,1}& x_{N,2}& .Math.& x_{N,C}\end{array}\right)& \left(15\right)\end{array}$

with channel index c=1, . . . , C. In the following, without lack of generality, {tilde over (x)} is considered a matrix of sampled channel impulse responses. .sub.c hence is the delay of the c-th path in a multipath environment. Each row of {tilde over (x)}

[00033]$\begin{array}{cc}{\stackrel{.fwdarw.}{x}}_n^T=\left(\begin{array}{cccc}{x}_{n,1}& x_{n,2}& .Math.& x_{n,C}\end{array}\right)& \left(16\right)\end{array}$

represents the channel impulse response at time instant t.sub.n.

[0118] The spectrum of {tilde over (x)} along the time dimension t follows from

[00034]$\begin{array}{cc}\stackrel{}{y}=\tilde{D}\stackrel{}{x},& \left(17\right)\end{array}$

which is the equivalent to (3) in matrix notation with D given by (2). The sample-wise DFT per time instant t.sub.n can therefore computed by means of {right arrow over (d)}.sup.(n) (4) and the matrix' equivalent to (5) and (6):

[00035]$\begin{array}{cc}{\stackrel{}{y}}^{\left(n\right)}={\stackrel{.fwdarw.}{d}}^{\left(n\right)}{\stackrel{.fwdarw.}{x}}_n^T& \left(18\right)\end{array}$$\mathrm{and}$$\begin{array}{cc}{\stackrel{}{y}}^{\left(n\right)}={\stackrel{}{y}}^{\left(n\right)}+{\stackrel{}{y}}^{\left(n-1\right)}={\stackrel{.fwdarw.}{d}}^{\left(n\right)}{\stackrel{.fwdarw.}{x}}_n^T+{\stackrel{}{y}}^{\left(n-1\right)}.& \left(19\right)\end{array}$

For an equidistant sampling with period t.sub.0 along t, {right arrow over (d)}.sup.(n) in (19) is obtained from (12) and (13).

[0119] {tilde over (y)}.sup.(n) (19) represents the spectrum of {tilde over (x)} for the period t.sub.1, . . . , t.sub.N with {tilde over (y)}.sup.(0)={tilde over (0)} for all path delays .sub.1, . . . , .sub.c. As {tilde over (x)} is considered a matrix of channel impulse responses, {tilde over (y)} becomes the path-delay Doppler spectrum, which is also known as scattering function or range-Doppler map. Nevertheless, the sample-wise DFT can be applied to any other signal matrix.

5. Algorithmic Implementation: Matrix

[0120] FIG. 7 illustrates an example data flow for a streaming, column-wise DFT implementation applied to a signal matrix {tilde over (x)} when the DFT vectors are recursively computed, assuming an equi-distant sampling. As of t=t.sub.2, the respective DFT vector follows from the element-wise multiplication of the previous vector and the phasor's vector {right arrow over (d)}.sup.(0). The syntax for the indices is for DFT vectors {right arrow over (d)}.sup.(0) and {right arrow over (d)}.sup.(n), for {tilde over (x)} and

[00036]${\stackrel{.fwdarw.}{x}}_n^T$

and for the spectral matrices {tilde over (y)}.sup.(n) and {tilde over (y)}.sup.(n) with p=1, . . . , P, n=1, . . . , N and j=1, . . . , J.

[0121] The data flow of an embodiment of the streaming DFT algorithm applied to a signal matrix is portrayed in FIG. 7. It relies on the following procedure: [0122] t=t.sub.1: Select the initial DFT vector {right arrow over (d)}.sup.(1) for an arbitrary time t.sub.1. For example,

[00037]$t_1=0,i.e.,{\stackrel{.fwdarw.}{d}}^{\left(1\right)}=\stackrel{.fwdarw.}{1}$$\mathrm{or}$$t_1=t_0,i.e.,{\stackrel{.fwdarw.}{d}}^{\left(1\right)}={\stackrel{.fwdarw.}{d}}^{\left(0\right)}.$ [0123] Multiply {right arrow over (d)}.sup.(1) with the 1st row

[00038]${\stackrel{.fwdarw.}{x}}_1^T$ of signal matrix {tilde over (x)} to obtain the spectral contribution {tilde over (y)}.sup.(1). [0124] Add {tilde over (y)}.sup.(1) to the initial matrix {tilde over (y)}.sup.(0) to obtain the spectrum {tilde over (y)}.sup.(1) at frequencies f.sub.1, . . . , f.sub.p for the 1st time sample. [0125] t=t.sub.2=t.sub.1+t.sub.0: Compute 2nd DFT vector {right arrow over (d)}.sup.(2) by element-wise multiplication of {right arrow over (d)}.sup.(1) and {right arrow over (d)}.sup.(0) (13). [0126] Multiply {right arrow over (d)}.sup.(2) with the 2nd row

[00039]${\stackrel{.fwdarw.}{x}}_2^T$ of signal matrix {tilde over (x)} to obtain the spectral contribution {tilde over (y)}.sup.(2). [0127] Add {tilde over (y)}.sup.(2) to the spectrum {tilde over (y)}.sup.(1) to obtain the spectrum {tilde over (y)}.sup.(2) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.1+t.sub.0. [0128] . . . [0129] t=t.sub.n=t.sub.1+(n1)t.sub.0: Compute n-th DFT vector {right arrow over (d)}.sup.(n) by element-wise multiplication of {right arrow over (d)}.sup.(n-1) and {right arrow over (d)}.sup.(0) (13). [0130] Multiply {right arrow over (d)}.sup.(n) with the nth row

[00040]${\stackrel{.fwdarw.}{x}}_n^T$ of signal matrix {tilde over (x)} to obtain the spectral contribution {tilde over (y)}.sup.(n). [0131] Add {tilde over (y)}.sup.(n) to the spectrum {tilde over (y)}.sup.(n-1) to obtain the spectrum {tilde over (y)}.sup.(n) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.1+(n1)t.sub.0. [0132] . . . [0133] t=t.sub.N=t.sub.1+(N1)t.sub.0: Compute N-th DFT vector {right arrow over (d)}.sup.(N) by element-wise multiplication of {right arrow over (d)}.sup.(N-1) and {right arrow over (d)}.sup.(0) (13). [0134] Multiply {right arrow over (d)}.sup.(N) with the N-th (last) row.

[00041]${\stackrel{.fwdarw.}{x}}_N^T$ of signal matrix {tilde over (x)} to obtain the spectral contribution {tilde over (y)}.sup.(N). [0135] Add {tilde over (y)}.sup.(N) to the spectrum {tilde over (y)}.sup.(N-1) to obtain the spectrum {tilde over (y)}.sup.(N) at frequencies f.sub.1, . . . , f.sub.p for the time period from t.sub.1 to t.sub.1+(N1)t.sub.0.
{tilde over (y)}.sup.(N) can then be used as the column-wise DFT of {tilde over (x)}.

6. Consideration of Multiple Samples in Time

[0136] FIG. 8 illustrates a data flow for a streaming, column-wise DFT implementation applied to the signal {tilde over (x)} when multiple samples (rows) are selected and the DFT matrix per time interval is recursively computed, assuming an equi-distant sampling. The syntax for the indices is for DFT phasor {right arrow over (d)}.sup.(0), for initial DFT matrix {tilde over (D)}.sup.(1) and for the spectral matrices {right arrow over (y)}.sup.(n) and {tilde over (y)}.sup.(n) with p=1, . . . , P, n=1, . . . , {circumflex over (n)} and j=1, . . . , J.

[0137] A generalisation of the streaming DFT as discussed in Sec. 2, 3 and 4 can be done for a time period of more than one sample. That is, not of single but multiple rows of {tilde over (x)}(15) are selected to compute their contribution to the spectrum {tilde over (y)}(17).

[0138] Let {circumflex over (n)} be the window size, i.e., the number of consecutive samples. Then the input signal matrix (15) can written as

[00042]$\begin{array}{cc}\tilde{x}=\left(\begin{array}{cccc}{x}_{1,1}& x_{1,2}& .Math.& x_{1,J}\\ x_{2,1}& x_{2,2}& .Math.& x_{2,J}\\ .Math.& .Math.& & .Math.\\ x_{\hat{n},1}& x_{\hat{n},2}& .Math.& x_{\hat{n},J}\\ x_{\hat{n}+1,1}& x_{\hat{n}+1,2}& .Math.& x_{\hat{n}+1,J}\\ x_{\hat{n}+2,1}& x_{\hat{n}+2,2}& .Math.& x_{\hat{n}+2,J}\\ .Math.& .Math.& & .Math.\\ x_{2\hat{n},1}& x_{2\hat{n},2}& .Math.& x_{2\hat{n},J}\\ .Math.& .Math.& & .Math.\\ x_{\left(L-1\right)\hat{n}+1,1}& x_{\left(L-1\right)\hat{n}+1,2}& .Math.& x_{\left(L-1\right)\hat{n}+1,J}\\ x_{\left(L-1\right)\hat{n}+2,1}& x_{\left(L-1\right)\hat{n}+2,2}& .Math.& x_{\left(L-1\right)\hat{n}+2,J}\\ .Math.& .Math.& & .Math.\\ x_{L\hat{n},1}& x_{L\hat{n},2}& .Math.& x_{L\hat{n},J}\end{array}\right)& \left(20\right)\end{array}$$\mathrm{or}$$\begin{array}{cc}\tilde{x}=\left(\begin{array}{c}{\tilde{x}}_1\\ {\tilde{x}}_2\\ .Math.\\ {\tilde{x}}_L\end{array}\right)& \left(21\right)\end{array}$

with

[00043]$\begin{array}{cc}{\tilde{x}}_l=\left(\begin{array}{cccc}{x}_{\left(l-1\right)\hat{n}+1,1}& x_{\left(l-1\right)\hat{n}+1,2}& .Math.& x_{\hat{n}+1,J}\\ x_{\left(l-1\right)\hat{n}+2,1}& x_{\left(l-1\right)\hat{n}+2,2}& .Math.& x_{\left(l-1\right)\hat{n}+2,J}\\ .Math.& .Math.& & .Math.\\ x_{l\hat{n},1}& x_{l\hat{n},2}& .Math.& x_{l\hat{n},J}\end{array}\right),& \left(22\right)\end{array}$$l=1,.Math.,L\mathrm{and}$$\begin{array}{cc}L=.Math.\frac{N}{\hat{n}}.Math..& \left(23\right)\end{array}$

N is assumed to be an integral multiple of {circumflex over (n)}.

[0139] The contribution of each {tilde over (x)}.sub.l to the spectrum is obtained by

[00044]$\begin{array}{cc}{\stackrel{}{y}}^{\left(l\right)}={\tilde{D}}^{\left(l\right)}{\stackrel{}{x}}_l.& \left(24\right)\end{array}$

Assuming an equidistant sampling with period t.sub.0, the DFT matrices {tilde over (D)}.sup.(l) can be computed from an initial matrix

[00045]$\begin{array}{cc}{\tilde{D}}^{\left(l\right)}=\frac{1}{N}\left(\begin{array}{cccc}\exp \left(-i2f_1{t}_0\right)& \exp \left(-i2f_{1}2t_0\right)& .Math.& \exp \left(-i2f_1\hat{n}{t}_0\right)\\ \exp \left(-i2f_2{t}_0\right)& \exp \left(-i2f_{2}2t_0\right)& .Math.& \exp \left(-i2f_2\hat{n}{t}_0\right)\\ .Math.& .Math.& & .Math.\\ \exp \left(-i2f_P{t}_0\right)& \exp \left(-i2f_{P}2t_0\right)& .Math.& \exp \left(-i2f_P\hat{n}{t}_0\right)\end{array}\right)& \left(25\right)\end{array}$

and the phasor's vector {right arrow over (d)}.sup.(0) (13). With (25) and (13), the l-th DFT matrix reads

[00046]$\begin{array}{cc}{\tilde{D}}^{\left(l\right)}=\mathrm{diag}{\left\{{\stackrel{.fwdarw.}{d}}^{\left(0\right)}\right\}}^{\left(l-1\right)\hat{n}}{\tilde{D}}^{\left(1\right)}& \left(26\right)\end{array}$

or in recursive form

[00047]$\begin{array}{cc}{\tilde{D}}^{\left(l\right)}=\mathrm{diag}{\left\{{\stackrel{.fwdarw.}{d}}^{\left(0\right)}\right\}}^{\hat{n}}{\tilde{D}}^{\left(l-1\right)}\mathrm{for}l>1.& \left(27\right)\end{array}$

The spectrum at l-th time window therefore becomes with (22)

[00048]$\begin{array}{cc}{\stackrel{}{y}}^{\left(l\right)}={\stackrel{}{y}}^{\left(l\right)}+{\stackrel{}{y}}^{\left(l-1\right)}=\mathrm{diag}{\left\{{\stackrel{.fwdarw.}{d}}^{\left(0\right)}\right\}}^{\left(l-1\right)\hat{n}}{\tilde{D}}^{\left(1\right)}{\stackrel{}{x}}_l+{\stackrel{}{y}}^{\left(l-1\right)}\mathrm{for}l>1\left(28\right)& \left(28\right)\end{array}$$\mathrm{or}$$\begin{array}{cc}{\stackrel{}{y}}^{\left(l\right)}=\mathrm{diag}{\left\{{\stackrel{.fwdarw.}{d}}^{\left(0\right)}\right\}}^{\hat{n}}{\tilde{D}}^{\left(l-1\right)}{\stackrel{}{x}}_l+{\stackrel{}{y}}^{\left(l-1\right)}\mathrm{for}l>1& \left(29\right)\end{array}$

with {tilde over (y)}.sup.(1)={tilde over (D)}.sup.(1) {tilde over (x)}.sub.1.

[0140] FIG. 8 portrays an implementation of the streaming DFT over multiple samples in time. It works as follows: [0141] t=t.sub.0, 2t.sub.0, . . . , {circumflex over (n)} t.sub.0: Select the initial DFT matrix {tilde over (D)}.sup.(1). Multiply {tilde over (D)}.sup.(1) with the 1st sub-matrix {tilde over (x)}.sub.1 of signal matrix {tilde over (x)} to obtain the spectral contribution {tilde over (y)}.sup.(1). Add {tilde over (y)}.sup.(1) to the initial matrix {tilde over (y)}.sup.(0) to obtain the spectrum {tilde over (y)}.sup.(1) at frequencies f.sub.1, . . . , f.sub.p for the 1st {circumflex over (n)} samples. [0142] t=({circumflex over (n)}+1)t.sub.0, ({circumflex over (n)}+2)t.sub.0, . . . , 2{circumflex over (n)} t.sub.0: Compute 2nd DFT matrix {tilde over (D)}.sup.(2) by multiplication of diag{{right arrow over (d)}.sup.(0)}.sup.{circumflex over (n)} and {tilde over (D)}.sup.(1) from the previous time interval. [0143] Multiply {tilde over (D)}.sup.(2) with the 2nd sub-matrix {tilde over (x)}.sub.2 of signal matrix {tilde over (x)} to obtain the spectral contribution {tilde over (y)}.sup.(2). [0144] Add {tilde over (y)}.sup.(2) to the spectrum {tilde over (y)}.sup.(1) to obtain the spectrum {tilde over (y)}.sup.(2) at frequencies f.sub.1, . . . , f.sub.p for the 2nd {circumflex over (n)} samples. [0145] . . . [0146] t=((l1)+1)t.sub.0, ((l1)+2)t.sub.0, . . . , l t.sub.0: Compute l-th DFT matrix {tilde over (D)}.sup.(l) by multiplication of diag{{right arrow over (d)}.sup.(0)}.sup.{circumflex over (n)} and {tilde over (D)}(l1) from the (l1)-th time interval. [0147] Multiply {tilde over (D)}.sup.(l) with the l-th sub-matrix {tilde over (x)}.sub.l of signal matrix {tilde over (x)} to obtain the spectral contribution {tilde over (y)}.sup.(l). [0148] Add {tilde over (y)}.sup.(l) to the spectrum {tilde over (y)}.sup.(l-1) to obtain the spectrum {tilde over (y)}.sup.(l) at frequencies f.sub.1, . . . , f.sub.p for the l-th {circumflex over (n)} samples. [0149] t=((L1){circumflex over (n)}+1)t.sub.0, ((L1){circumflex over (n)}+2)t.sub.0, . . . , L{circumflex over (n)} t.sub.0: Compute L-th DFT matrix {tilde over (D)}.sup.(L) by multiplication of diag{{right arrow over (d)}.sup.(0)} and {tilde over (D)}.sup.(L-1) from the (L1)-th time interval. [0150] Multiply {tilde over (D)}.sup.(L) with the L-th sub-matrix {tilde over (x)}.sub.L of signal matrix {tilde over (x)} to obtain the spectral contribution {tilde over (y)}(L). [0151] Add {tilde over (y)}.sup.(L) to the spectrum {tilde over (y)}.sup.(L-1) to obtain the spectrum {tilde over (y)}.sup.(L) at frequencies f.sub.1, . . . , f.sub.p for the L-th {circumflex over (n)} samples.

[0152] {tilde over (y)}.sup.(L) can then be used as the column-wise DFT of {tilde over (x)}.

7. Implementation for Non-Equidistant Sampling

FIG. 9 illustrates an M-bit successive approximation of time difference t.sub.n (40). Based on the output vector {right arrow over (w)} (45), the sub-set of predefined DFT vectors (37) is selected and combined to compute the contribution of the sample at time instant t.sub.n to the DFT.
The DFT matrix as defined by {tilde over (D)}(2) does not imply an equidistant sampling, i.e., in general

[00049]$\begin{array}{cc}{t}_n-t_{n-1}\mathrm{const}\mathrm{for}n=1,.Math.,N.& \left(30\right)\end{array}$

For a given period t.sub.1 to t.sub.N the full DFT matrix has to be stored in memory.

[0153] Alternatively, the DFT vector {right arrow over (d)}.sup.(n) (4) can be computed based on its predecessor {right arrow over (d)}.sup.(n-1) as pointed out for the equidistant case in Sec. 3. This can basically be done in two ways: [0154] A minimum step width {circumflex over (t)}.sub.0 is set and {right arrow over (d)}.sup.(n) is obtained from

[00050]$\begin{array}{cc}{\stackrel{.fwdarw.}{d}}^{\left(n\right)}=\mathrm{diag}{\left\{{\stackrel{.fwdarw.}{d}}^{\left(0\right)}\right\}}^{}{\stackrel{.fwdarw.}{d}}^{\left(n-1\right)}\mathrm{for}n>1& \left(31\right)\end{array}$

with

[00051]$\begin{array}{cc}\stackrel{\stackrel{.Math.}{.fwdarw.}}{d^{\left(0\right)}}=\left(\begin{array}{c}\exp \left(-i2f_1{\hat{t}}_0\right)\\ \exp \left(-i2f_2{\hat{t}}_0\right)\\ .Math.\\ \exp \left(-i2f_P{\hat{t}}_0\right)\end{array}\right)& \left(32\right)\end{array}$$\mathrm{and}$$\begin{array}{cc}=\left[\frac{t_n-t_{n-1}}{{\hat{t}}_0}\right]& \left(33\right)\end{array}$

the integer multiple of the time difference t.sub.nt.sub.n-1 over the step width {circumflex over (t)}.sub.0; [] denotes the rounding operator. As a consequence of rounding, the time step {circumflex over (t)}.sub.0, can differ from the actual time difference t.sub.nt.sub.n-1, leading to computation errors in the DFT. {circumflex over (t)}.sub.0, is therefore assumed to be a little fractional of the minimum time difference expected, for example,

[00052]$\begin{array}{cc}{\stackrel{}{t}}_0<<\min \left\{t_n-t_{n-1}\right\}n>1.& \left(34\right)\end{array}$

[0155] Whilst in this case {right arrow over ({circumflex over (d)})}.sup.(0) (32) is the only DFT vector to be permanently stored in memory, the computation effort can become high for large . [0156] For reduced computation effort, a set of possible step width

[00053]$\begin{array}{cc}\left\{{\stackrel{}{t}}_1,.Math.,{\stackrel{}{t}}_M\right\}& \left(35\right)\end{array}$

can be put. Then

[00054]$\begin{array}{cc}{\stackrel{.fwdarw.}{d}}^{\left(n\right)}=\mathrm{diag}\left\{\stackrel{\stackrel{.Math.}{.fwdarw.}}{d^{\left(m\right)}}\right\}{\stackrel{.fwdarw.}{d}}^{\left(n-1\right)}\mathrm{for}n>1\mathrm{and}m=1,.Math.,M& \left(36\right)\end{array}$

with

[00055]$\begin{array}{cc}\stackrel{\stackrel{.Math.}{.fwdarw.}}{d^{\left(m\right)}}=\left(\begin{array}{c}\exp \left(-i2f_1{\hat{t}}_m\right)\\ \exp \left(-i2f_2{\hat{t}}_m\right)\\ .Math.\\ \exp \left(-i2f_P{\hat{t}}_m\right)\end{array}\right)& \left(37\right)\end{array}$$\begin{array}{cc}m=\mathrm{argmin}.Math.\left\{t_n-t_{n-1}-{\stackrel{}{t}}_m\right\}.Math..& \left(38\right)\end{array}$

[0157] Descriptively speaking, it is taken that time step {circumflex over (t)}.sub.m that is closest to the time difference t.sub.nt.sub.n-1 of two consecutive samples.

[0158] Compared to the former cases, M DFT vectors need to be permanently stored in memory in favour of reduced computation effort.

[0159] Also combinations of both abovementioned approaches can be applied.

[0160] A certain implementation is based on a successive approximation to the time difference t.sub.nt.sub.n-1 of two consecutive samples. Suppose a maximum time difference

[00056]$\begin{array}{cc}\max \left\{t_n-t_{n-1}\right\}=\stackrel{}{t}n& \left(39\right)\end{array}$

and a time difference resolution of M bits, i.e., the minimum time step becomes

[00057]$\frac{\stackrel{}{t}}{2^M}.$

[0161] For a certain time difference t.sub.n-t.sub.n-1<{circumflex over (t)}, a combination of predefined time steps can be obtained. FIG. 9 shows the implementation: [0162] The time difference between the current and the previous sample is denoted as

[00058]$\begin{array}{cc}{t}_n=t_n-t_{n-1}.& \left(40\right)\end{array}$

t.sub.n is to be quantised with M bits. m=1 represents the most significant bit, m=M the least significant bit. [0163] The approximations starts with a time difference of .sub.1=t.sub.n. [0164] The quantisation level is defined by

[00059]$\begin{array}{cc}{T}_m=\frac{\stackrel{}{t}}{2^m}.& \left(41\right)\end{array}$

For m=1, it becomes

[00060]$T_1=\frac{\stackrel{}{t}}{2}.$ [0165] The m-th bit follows from

[00061]$\begin{array}{cc}{w}_m=.Math.\frac{{}_m}{T_m}.Math.& \left(42\right)\end{array}$

with

[00062]$\begin{array}{cc}{}_m={}_{m-1}-w_{m-1}{T}_{m-1}\mathrm{for}m>1& \left(43\right)\end{array}$$\begin{array}{cc}{}_m=t_n\mathrm{for}m=1& \left(44\right)\end{array}$

the quantised time difference. denotes the floor operator. For m=1,

[00063]$w_1=.Math.\frac{t_n}{T_1}.Math..$ [0166] With all bits computed, the binary word is represented by vector

[00064]$\begin{array}{cc}\stackrel{.fwdarw.}{w}={\left(\begin{array}{cccc}{w}_1& w_2& .Math.& w_M\end{array}\right)}^T& \left(45\right)\end{array}$

with w.sub.m{0,1} for m=1, . . . , M.

[0167] For a set of possible step widths (35) following from (41)

[00065]$\begin{array}{cc}\left\{{\stackrel{}{t}}_1,.Math.,{\stackrel{}{t}}_M\right\}=\left\{T_1,T_2,.Math.,T_M\right\}& \left(46\right)\end{array}$

the quantised time difference follows from

[00066]$\begin{array}{cc}=\left(\begin{array}{cccc}{T}_1& T_2& .Math.& T_M\end{array}\right)\stackrel{.fwdarw.}{w}={.Math.}_{m=1}^M{w}_m{T}_m.& \left(47\right)\end{array}$

This can be mapped to the sub-set of predefined DFT vectors (37) needed to obtain the DFT vector {right arrow over (d)}.sup.(n) for the current time instant t.sub.n:

[00067]$\begin{array}{cc}{\stackrel{.fwdarw.}{d}}^{\left(n\right)}={.Math.}_{w_m}\mathrm{diag}\left\{w_m{\stackrel{\widehat{.fwdarw.}}{d}}^{\left(m\right)}\right\}{\stackrel{.fwdarw.}{d}}^{\left(n-1\right)}& \left(48\right)\end{array}$$\mathrm{for}{w}_m=1\mathrm{and}m=1,.Math.,M.$

That is, only those predefined vectors {right arrow over ({circumflex over (d)})}.sup.(m) are selected for which w.sub.m=1.

[0168] An implementation for dynamically DFT coefficient calculations for non-equidistant sampling is depicted in FIG. 10 and FIG. 11.

[0169] FIG. 10 illustrates a sequence chart for dynamic computation of DFT coefficients suited for non-equidistant sampling.

[0170] FIG. 11 (split into FIG. 11a, FIG. 11b, FIG. 11c) illustrates a dynamic computation of DFT coefficients suited for non-e-quidistant sampling.

[0171] FIG. 12 illustrates motor vehicle 10 that can be, e.g., a passenger vehicle, that is driving on a road. In an environment 11 of the vehicle 10, objects 12, like, e.g. other traffic participant, can be detected by a sensor device 13 of the vehicle 10. The sensor device 13 can be a radar device that can emit radar waves 14 which may be reflected by one or more of the objects 12 and may then return as reflected radar waves 15 to the sensor device 13. A radar sensor 16 may receive the reflected radar waves 15 and may generate a sensor signal 17 from the received radar waves. An analog-to-digital conversion 18 may convert the sensor signal 17 into single samples 19 that one after another may be received by a processor circuit 20. It is also possible to provide a multi-channel version as described above. The generation of the samples 19 from reflected radar waves 15 can be implemented as is known from the prior art.

[0172] Whenever the processor circuit 20 receives a new sample 19, a timestamp may be associated with the sample 19 indicating, e.g., the time of reception or generation. The processor circuit 20 can transform the samples 19 into DFT coefficients 21 using one or more of the described procedures thus applying the SDFT.

[0173] An assistance system 22, e.g. an autonomous driving function or a driver assistance system, can use the DFT coefficients 21 for detecting the objects 12 and/or for analyzing the relative distance and/or velocity of the objects 12 with regard to the sensor 16. Using the DFT coefficients 21 and by a procedure known from the prior art the assistance system 22 can calculate a driving trajectory 23 for avoiding a collision with the objects 12. For controlling the vehicle 10 such that it follows the trajectory 23, the assistance system 22 can generate control commands 24 that control or influence at least one actuator 25 of the vehicle 10, e.g. a brake and/or a steering and/or an engine.

[0174] Overall, the example shows how an implementation of a Streaming Discrete Fourier Transform, SDFT, is provided by the invention.

REFERENCE SIGNS

[0175] 10 vehicle [0176] 11 environment [0177] 12 objects [0178] 13 sensor device [0179] 14 emitted radar waves [0180] 15 received radar waves [0181] 16 sensor [0182] 17 sensor signal [0183] 18 analog-to-digital conversion [0184] 19 sample [0185] 20 processor circuit [0186] 21 DFT coefficients [0187] 22 assistance system [0188] 23 driving trajectory [0189] 24 control commands [0190] 25 actuator