Discrete signals and discrete Fourier transform. Discrete Fourier transform

From the previous section on sampling continuous signals, it follows that real signals can be described by samples in both the spectral and time domains. Both the discrete spectrum and the discrete signal completely describe the original continuous (continuous) signal. However, in order to find a discrete spectrum from a given discrete signal, it is necessary to perform time-consuming calculations: first, reconstruct a continuous signal from a discrete signal, then use the Fourier transform to find a continuous spectrum, then discretize it. A similar procedure must be followed for the reverse conversion. Direct transition from a discrete signal to a discrete spectrum and vice versa is possible using a discrete Fourier transform.

Let us consider a continuous signal of finite duration with a number of degrees of freedom equal to For this signal we can write the expansion in a Kotelnikov series:

By using normal conversion Let's find the Fourier spectrum of this signal:

Direct calculation of the integral in this formula is a labor-intensive procedure. However, this is not difficult to do in another way.

Consider the spectrum which is determined by the expression

Applying the inverse Fourier transform to it, we find that it corresponds to the time function

Obviously, the inverse relation is also true

Using the delay theorem, we can write

Substituting (3.2) into (3.1), we obtain the final expression for the spectrum

To go to the discrete Fourier transform, the spectrum values ​​in expression (3.3) need to be calculated not for all frequency values, but for discrete (sampled) ones:

As a result, we obtain the final formula for the discrete Fourier transform

The properties of the discrete Fourier transform are in many ways similar to the properties of the conventional Fourier transform. Let us note only one specific property, which

can be called the periodicity of the discrete Fourier transform.

Consider the value determined by formula (3.4) for where is an integer:

Thus, the discrete Fourier transform is a periodic function of frequency with a period equal to This property is similar to the property of periodicity of the spectrum of sampled signals, which was discussed in Chapter. 2.

Let us now move on to the derivation of the inverse discrete Fourier transform, which allows us to determine signal samples from spectrum samples. To do this, we use the usual inverse Fourier transform

We write the spectral density of the signal in the form of a Kotelnikov series

and substitute into the integral of the inverse Fourier transform

The integral in the expression is similar to the previously calculated integral (3.2). Using this analogy, we write

Substituting (3.6) into (3.5), we obtain an expression for the time function

Assuming in the relation, we obtain a formula for determining the values ​​of a discrete signal, i.e., we arrive at the inverse discrete Fourier transform

where A takes values ​​from 0 to

Sometimes, for convenience of notation, using the periodicity property of the discrete Fourier transform, the limits of summation in expression (3.8) are changed and the inverse discrete Fourier transform is written in the form

To illustrate, apply the discrete Fourier transform to a sampled triangular pulse (described by five sample values ​​in Fig.

Let's substitute this expression for the discrete signal into the formula for the discrete Fourier transform (3.4)

For comparison, let's find spectral density initial triangular pulse:

It is easy to see that the discrete spectrum (3.11) does not accurately describe the spectral density of the triangular pulse (3.12). The values ​​differ slightly from the corresponding values ​​of the triangular pulse spectrum (Fig. 3.1, b).

Now let’s substitute the discrete values ​​of the spectrum (3.11) into the expression for the inverse discrete Fourier transform (3.8):

Despite the difference between the values ​​of the discrete spectrum and the values ​​of the continuous spectrum, the obtained result completely coincides with the formula of the original discrete signal (3.11).

The considered example shows that the discrete Fourier transform does not always accurately describe the spectrum of the original continuous signal, just as

Rice. 3.1. Discrete conversion Fourier of a sampled triangular pulse

the sampled signal does not always accurately describe the original continuous signal. However, the relationship between a discrete signal and its discrete Fourier transform is always one-to-one and the formula for the direct and inverse Fourier transforms is strict for any number discrete values. Therefore, the apparatus of discrete Fourier transforms has independent significance and can be applied to any numerical sequences.

In this case, the formulas for the discrete Fourier transform must be slightly modified, since for the abstract number sequence The values ​​for sampling interval and signal duration are meaningless. Therefore, the coefficient in front of the sum in formula (3.4) is omitted, replaced by the reference values ​​of the signal and spectrum, denoted by and the formula for the discrete Fourier transform is written in the form

In this case, the inverse discrete Fourier transform has the form

The values ​​calculated using formula (3.14) differ from the sample values ​​of the continuous oscillation spectrum by a factor. To determine sample values, you need to multiply the values ​​calculated using formula (3.14) by the value of the time sampling interval:

Let us show that transformations (3.14), (3.15) are mutually inverse. To do this, take an arbitrary numerical sequence using the discrete Fourier transform (3.14), find the sequence and apply the inverse discrete transform to it

Fourier (3.15). We denote the resulting sequence

Let's change the order of summation and slightly transform this expression:

The internal sum of expression (3.16) is equal to zero if and equal to if Therefore, when i.e., the number sequences coincide with each other. Thus, when successively applying the direct and inverse discrete Fourier transform to any numerical sequence, the result is the same sequence.

Let us illustrate this point with the simplest examples.

1. Consider the simplest discrete signal, consisting of one sample value equal to a. Substituting this simplest sequence into the discrete Fourier transform formula (3.14), we obtain Thus, the discrete Fourier transform of an individual numerical value equal to the same value.

Another important application of the discrete Fourier transform is the calculation of the signal at the output of a filter with a given frequency response. If an input signal is given, then a discrete Fourier transform can be calculated for it. If we now multiply by the frequency response of the filter, we obtain a discrete Fourier transform of the output signal: After this, using the inverse discrete Fourier transform, we can find the signal at the output of the filter.

If the input signal has a long duration, it can be processed using the discrete Fourier transform in parts. To do this, take the first N samples of the input signal, calculate their discrete Fourier transform and, after multiplying by the frequency response of the filter, use the inverse discrete Fourier transform to calculate the first N samples of the output signal. After this, the next N samples of the input signal are processed in a similar way, etc. To increase the accuracy of signal processing, the processed series of samples may partially overlap.

The advantage of this method of signal processing is the absence of any restrictions on the type of frequency response of the filter. For example, the frequency response may be a perfect rectangular shape, which cannot be achieved using conventional filters.

Signal processing using discrete Fourier transform cannot be called digital filtering in in every sense words. Conventional digital filters operating in real time process the signal continuously as it arrives, and the calculation of the output signal using a discrete Fourier transform can be done only after the entire input signal or at least the first series of N samples is known . Therefore, when using the discrete Fourier transform, the output signal can only be obtained with a certain

delay relative to the input signal. However, in a number practical applications such a delay of the output signal does not play a significant role, and then signal processing using the discrete Fourier transform turns out to be appropriate.

Modern communication technology cannot be imagined without spectral analysis. Representation of signals in frequency domain necessary both for the analysis of their characteristics and for the analysis of blocks and units of transceivers of radio communication systems. To convert signals into the frequency domain, a direct Fourier transform is used. The generalized formula for the direct Fourier transform is written as follows:

As can be seen from this formula for frequency analysis, the calculation is made correlation dependence between a signal represented in the time domain and a complex exponential at a given frequency. In this case, according to Euler’s formula, the complex exponential is decomposed into a real and imaginary part:

A signal represented in the frequency domain can be converted back into a time domain using an inverse Fourier transform. The generalized formula for the inverse Fourier transform is written as follows:

The direct Fourier transform formula uses time integration from minus infinity to infinity. Naturally this is a mathematical abstraction. IN real conditions we can integrate from at this moment time, which we can denote as 0, before time T. The formula for the direct Fourier transform will be transformed to the following form:

As a result the properties of the Fourier transform change significantly. Signal spectrum instead continuous function becomes a discrete series of values. Now the minimum frequency and at the same time the step of frequency values ​​of the signal spectrum becomes:

Only functions sin and cos with frequencies k/T will be mutually orthogonal, and this is an indispensable condition for the Fourier transform. The set of the first functions of the Fourier series expansion is shown in Figure 1. In this case, the duration of the functions coincides with the duration of the analysis T.

Now the signal spectrum will look as shown in Figure 2.

IN in this case the formula for calculating the direct Fourier transform (4) is transformed to the following form:

The formula for the inverse Fourier transform for the case of determining the spectrum over a limited period of time will look like this:

In a similar way, you can determine the formula for the direct Fourier transform for digital signal samples. Considering that instead of a continuous signal its digital samples are used, in expression (6) the integral is replaced by a sum. In this case, the duration of the analyzed signal is determined by the number of digital samples N. The Fourier transform for digital signal samples is called the discrete Fourier transform and is written as follows:

Now let's look at how the properties of the discrete Fourier transform (DFT) have changed compared to the direct Fourier transform over a limited time interval. When we looked at analog signal sampling, we learned that the input signal spectrum must be frequency limited. This requirement limits the number of discrete components of the signal spectrum. Initially it may seem that we can limit the spectrum of the signal to the frequency f d/2, which corresponds to the number of frequency components K=N/2. However, this is not true. Although the signal spectrum for real signal samples for positive frequencies and negative frequencies is symmetrical about 0, negative frequencies may be required for some spectrum algorithms, such as . The difference is even greater when performing a discrete Fourier transform on complex samples of the input signal. As a result for full description spectrum digital signal required N frequency samples ( k = 0, ..., N/2).

Fourier transforms

It is convenient to analyze many signals by decomposing them into sinusoids (harmonics). There are several reasons for this. For example, the human ear works in a similar way. It decomposes sound into individual vibrations of different frequencies. Additionally, it can be shown that sinusoids are " own functions» linear systems (since they pass through linear systems, without changing the shape, but can only change the phase and amplitude). Another reason is that Kotelnikov's theorem is formulated in terms of the signal spectrum.

Fourier transform ) is the decomposition of functions into sinusoids (hereinafter we also call cosine functions sinusoids, since they differ from “real” sinusoids only in phase). There are several types of Fourier transform.

1. A non-periodic continuous signal can be expanded into a Fourier integral.

2. A periodic continuous signal can be expanded into an infinite Fourier series.

3. A non-periodic discrete signal can be expanded into a Fourier integral.

4. A periodic discrete signal can be expanded into a finite Fourier series.

A computer can only work with a limited amount of data, therefore, it can really only calculate the last type of Fourier transform. Let's take a closer look at it.

Real signal DFT

Let a discrete signal x have a period of N points. In this case, it can be represented as a finite series (i.e., a linear combination) of discrete sinusoids:

Equivalent notation (we decompose each cosine into sine and cosine, but now without a phase):

Rice. 6. Fourier series basis functions for an 8-point discrete signal. On the left are cosines, on the right are sines. Frequencies increase from top to bottom.

Basic sinusoids have multiple frequencies. The first term of the series (k =0) is a constant called constant component(DC offset) signal. The very first sinusoid (k = 1) has such a frequency that its period coincides with the period of the original signal itself. The highest frequency component (k =N /2) has such a frequency that its period is equal to two counts. CoefficientsA k and

B k is called the signal spectrum (spectrum). They show the amplitudes of the si-

nusoids that make up the signal. The frequency step between two adjacent sinusoids from the Fourier expansion is called frequency resolution spectrum

In Fig. Figure 6 shows the sinusoids used to decompose a discrete signal from 8 points. Each of the sinusoids consists of 8 points, that is, it is an ordinary discrete signal. Continuous sinusoids are shown in the figure for clarity.

convert the original signal by calculating the sum of the Fourier series at each point. Decomposing a signal into sinusoids (i.e. obtaining coefficients) is called direct Fourier transform. The reverse process - signal synthesis using sinusoids - is called inverse Fourier transform(inverse Fourier transform).

The algorithm for the inverse Fourier transform is obvious (it is contained in the formula of the Fourier series; to carry out the synthesis, you just need to substitute the coefficients into it). Let's consider the direct Fourier transform algorithm, i.e. finding the coefficients A k and B k .

togonal basis in the space of periodic discrete signals with period N. This means that to decompose any element of space (signal) into it, you need to calculate dot products this element with all the functions of the system, and the resulting coefficients are normalized. Then the basis expansion formula with coefficients A k and B k will be valid for the original signal.

So, the coefficients A k and B k are calculated as scalar products (in non-

in the discontinuous case – integrals of the product of functions, in the discrete case

– sums from the product of discrete signals):

We explore the features of the spectral representation of a discrete signal, which is specified on a segment by its own readings
, taken respectively at times
; total number of samples
(- sampling interval).

The technique for studying such discrete signals is that the resulting sample of reference values ​​is mentally repeated an infinite number of times. As a result, the signal becomes periodic.

By associating a certain mathematical model with such a signal, you can use the Fourier series expansion and find the corresponding amplitude coefficients. The combination of these coefficients forms the spectrum of a discrete periodic signal.

Let's use the model in the form of a sequence of delta pulses. Then the initial vibration will be expressed by the formula:

(5.1)

Where
– sample values ​​of the analog signal.

- discrete Fourier transform (DFT) (5.4)

Basic properties of DFT

1. DFT - linear transformation i.e. the sum of the signals corresponds to the sum of their DFT

2. Number of different coefficients
, calculated using formula (5.4), is equal to the number N per period; at coefficient

3. Coefficient (constant component) is the average value of all readings:

5. Let the reference values – real numbers. Then the DFT coefficients, the numbers of which are located symmetrically with respect to /2, form conjugate pairs:

The problem of discrete spectral analysis can be formulated in another way. Let us assume that the coefficients , forming the DFT, are given. Let us put in formula (5.2)
and take into account that only a finite number of terms of the series are summed, which correspond to the harmonics contained in the spectrum of the original signal.

Thus, we obtain a formula for calculating reference values

(5.5)

Obviously, (5.5) is the inverse discrete Fourier transform (IDFT) formula.

11 Fast Fourier transform algorithm. Number of computational operations. Comparison of discrete and fast Fourier transforms.

=0, 1, 2,…,( /2)-1 (5.7)

Let us take into account that the sequences of coefficients related to the even and odd parts of the input array are periodic with a period of N/2:

In addition, the factor included in formula (5.7) at
can be converted like this:

From here we find the expression for the second half of the set of DFT coefficients

(5.8)

Formulas (5.7) and (5.8) form the basis of the FFT algorithm. Further calculations are carried out according to the iterative principle: sequences of samples with even and odd numbers are again divided into two parts. The process is continued until a sequence consisting of a single element is obtained. The DFT of this element coincides with itself.

The number of operations required to calculate the FFT is estimated as
.

The gain in computation speed compared to traditional DFT reaches hundreds and even thousands if the input arrays are of sufficient length.

12.. Z - transformation and its properties. Application Z - transformations.

In the analysis and synthesis of discrete and digital devices, the Z-transform plays the same role as Fourier integral transforms with respect to continuous signals.

Let
– a numerical sequence, finite or infinite, containing the reference values ​​of a certain signal. Let us put it in a unique correspondence with the sum of the series in negative powers complex variable Z:

(5.9)

This sum is called the Z-transform of the sequence
. The properties of discrete sequences of numbers can be studied by studying their Z-transformations using conventional methods of mathematical analysis.

This expression makes sense when |Z|> .

Inverse Z-transform

Let x(z) be a function of the complex variable Z. A remarkable property of the Z-transform is that the function x(z) defines the entire infinite set of samples (
).

Indeed, let us multiply both sides of the series (5.9) by the factor
:

The integrals of all terms on the right side will vanish, with the exception of the term with number m, therefore:

(5.11)

This expression is called the inverse Z-transform.

The most important properties Z -conversions:

1. Linearity. If
And
- some discrete signals, and the corresponding Z-transformations x(z) and y(z) are known, then the signal
will correspond to the transformation for any constant And . The proof is carried out by substituting the sum into formula (5.9).

2. Z-conversion of the shifted signal. Consider a discrete signal
, resulting from a discrete signal
by shifting one position towards the delay, i.e. When
. Directly calculating the Z-transform, we obtain the following result:

So the symbol
serves as a unit delay operator (per sampling interval) in the Z-domain.

3. Z-convolution transformation. Let x(z) and y(z) be continuous signals, for which the convolution is defined:

(5.13)

In relation to discrete signals by analogy with (5.13) it is customary to introduce discrete convolution
– a sequence of numbers whose common term is:

Such a discrete convolution is called linear

Let's calculate the Z-transform of discrete convolution:

(5.15)

So, the convolution of two discrete signals corresponds to the product of Z-transforms.

Introduction

On laboratory lesson possibilities for discrete trigonometric transformation(road accident) from the following points of view:

1. We checked the reversibility property of the given accident.

2. The linearity of the proposed accident was investigated.

3. We studied the features of the repeat spectrum of the tested accident.

4. We determined the presence of symmetrical reflection of the spectrum in an accident, namely

4.1. availability central symmetry,

4.2. the presence of axial (vertical) symmetry.

5. We considered the influence of phase shifts of the signal on the resulting accident.

6. Checked the presence of the similarity property for the given transformation.

7. We investigated the possibility of filtering signals using a given accident.

8. We tested experimentally the conservation of energy in the road accident under study.

9. We discovered a connection between this accident and the discrete Fourier transform.

Various input signals were also considered for a more representative analysis.

The most famous among discrete functional transformations is the discrete Fourier transform (DFT)

Discrete Fourier transform

The discrete Fourier transform determines line spectrum discretized periodic function of time. The inverse discrete Fourier transform allows you to reconstruct the time function from its spectrum. These transformations are usually abbreviated as DFT and ODFT, respectively.

The DFT is used to analyze periodic functions and can be obtained from the theory of Fourier series. Let x0(t) be a continuous periodic function with period P and frequency f0 = 1/P so

The function x0(t) can be expanded into a Fourier series:

where the expansion coefficients X0(n) are given by the formula

Usually x0(t) is real function, and then X0(n) are complex (but this restriction is not necessary). Since we consider x0 as a function of time, X0(n) can be called the complex spectrum of x0(t). Using the real and imaginary parts of X0(n), one can find the amplitude and phase of the components that form the oscillation x0(t).

Let us consider the discretization of the periodic function x0(t). In order for this function to be discretized unambiguously, its spectrum should not contain components with a frequency higher than a certain frequency f1, i.e.

where n1 is an integer value of n specifying the frequency f1.

In fig. 1 shows such a limited spectrum and the vibration to which it corresponds.

sampling interval T is equal to

so the number of samples per period will be

Fig. 1. Periodic function x0(t) with a limited frequency band and its spectrum X0(n).

1As a result of discretization, we obtain a periodic oscillation normalized relative to T of the form

This oscillation is defined over an interval equal to its period, i.e.

Since x(t/T) is a periodic function, relation (2) is used to calculate the coefficients of the Fourier series

(Replacing P with /V in the divisor and the limits of integration corresponds to the transition to a normalized variable.) Substituting expression (3), we obtain

It is known that

Finally, taking into account the fact that by definition

The relationship connecting x(k) with X(n) can be obtained directly from formula (1), if we substitute t=kT and take into account that with a limited width of the spectrum of the function x0(t), the sum contains a finite number of terms. So,

It should be noted that x(k) is a periodic function, i.e.

and similarly

The fact that the spectrum is periodic is explained by the periodicity of the spectrum of any discretized function, and its discrete nature is due to the fact that the discretized function itself is also periodic.

So, when discretizing a periodic function x0(t), relation (4) allows using samples x0(t) to find the spectrum X(n), which in the interval 0 ≤ n ≤ N - 1 is exactly equal to the spectrum X0(n) of the original periodic function. The function x(k) and its spectrum are graphically presented in Fig. 2. Since relation (5.4) is obtained on the basis of the sampling theorem, it is an accurate and economical (in calculations) equivalent of the original integral relation (2) and can be used to calculate expansion coefficients on a computer. We will call relations (4) and (5) the discrete Fourier transform (DFT) and the inverse discrete Fourier transform (IDFT), respectively. Note that the variable n varies here from zero to N-1. The resulting spectrum can be interpreted as follows. The first (N/2-1) points X(n) - correspond to (N/2 - 1) spectral lines X0(n) at positive frequencies, as shown in Fig. 5.3, and the last (N/2-1) points X(n) correspond to (N/2-1) spectral lines at negative frequencies.

A couple of transformations given by the relations(4) and (5), also occurs in another form. For example, the multiplier 1 / N and the minus sign of the exponent can be written both in direct and in inverse conversion, general meaning it does not change.

Naturally, the spectrum in this case cannot be directly identified with the one defined by formula (2). Sometimes both transformations are given with the same factors (1 / N)1/2.

Fig. 2. Discretized periodic function x(k) and its periodic spectrum X(n).

Fig. 3. The relationship between the coefficients of the Fourier series and the DFT.

Properties of DFT

Some properties of the DFT play into practical issues Signal processing plays an important role.

Linearity

If xp(n) and ur(n) are periodic sequences (with a period of N samples each), and Xp(k) and Yp(k) are their DFTs, then the discrete Fourier transform of the sequence xp(n) + + ur(n ) is equal to Хр(k) + Yp(k). This is also true for sequences of finite length.

Shift

If the sequence xp(n) is periodic with a period of N samples, and its DFT is equal to Xp(k), then the DFT of a periodic sequence of the form xp(n-n0) will be equal.

Fig. 4. Towards the definition of the DFT of a shifted sequence.

When analyzing sequences of finite length, it is necessary to take into account the specific nature of the time shift of the sequence. So, in FIG. 4, a shows a finite sequence x(n) of length N samples. There, crosses also show samples of the equivalent periodic sequence xp(n), which has the same DFT as x(n). To find the DFT of the shifted sequence x(n - n0), and n0< N, следует рассмотреть сдвинутую периодическую последовательность Хр(n - n0) и в качестве эквивалентной сдвинутой finite sequence(having a DFT j, accept a segment of the sequence xp(n - n0) in the interval 0 ≤ n ≤ N - 1. Thus, from the point of view of the DFT, the sequence x(n – n0) is obtained by circularly shifting the elements of the sequence x(n) by n0 samples

Properties of symmetry

If a periodic sequence xp(n) with a period of v/V samples is real, then its DFT xp(k) satisfies following conditions symmetry:

Similar equalities are valid for a finite real sequence x(n) having an N-point DFT X(k). If you enter additional condition symmetry of the sequence xp(n), i.e. assume that

then it turns out that Xp(k) can only be real.

Since we most often have to deal with real sequences, by calculating one DFT, we can obtain the DFT of two sequences using symmetry properties (6). Let us consider real periodic sequences xp(n) and yp(n) with periods of N samples and N-point DFTs Хр(k) and Yp(k), respectively. Let us introduce a complex sequence zp(n) of the form

Its DFT is equal to

Isolating the real and imaginary parts of equality (10), we obtain

The real parts Xp(k) and Yp(k) are symmetrical, and the imaginary parts are antisymmetric, so they can be easily separated using addition and subtraction operations:

So, by calculating one N-point DFT, it is possible to transform two real sequences of length N samples at once. If these sequences are also symmetric, then the number of operations required to obtain their DFT can be reduced even further.

Related information.