Comparative analysis of the computational efficiency of the fast Fourier transform in the discrete exponential functions and Vilenkin-Crestenson functions bases

Размещено на http://www.allbest.ru/

Comparative analysis of the computational efficiency of the fast Fourier transform in the discrete exponential functions and Vilenkin-Crestenson functions bases

Vitaliy Klobukov

Assistant of the Department of Information Security, Faculty of Cybersecurity, Computer and Software Engineering, National Aviation University, Kyiv, Ukraine

Anatoliy Biletsky

Full Professor,Dr.Sc.,Ph.D (Engineering) of the Department of the Department of Electronics, Robotics, Monitoring and IoT Technologies, Faculty of Air Navigation, Electronics & Telecommunications,, National Aviation University, Kyiv, Ukraine

Abstract

Research object: efficiency of fast Fourier transform in discrete- exponential functions and Vilenkin-Chrestenson functions bases. The problem to be solved: increasing the computational efficiency (speed) of the fast Fourier transform in the spectral analysis of signals Main scientific results: It has been analysed that the structures of FFT graphs in the VCF bases do not differ in complexity from the FFT graphs in the DEF bases. In this case, the calculation of the spectrum in the VCF basis (for some values of the basis parameter m) requires fewer hardware costs or computer time (the processing speed increases by almost an order of magnitude). This property can be used to implement devices that estimate the frequency of the received discrete- exponential signal in the VCF basis, which have a higher speed than a similar device operating with the DEF basis. The area of practical use of the research results:

The spectral analysis algorithm in the VCF bases can be used in high-speed radar devices (in particular, household ones: the onboard system of a car, alarm systems, etc.) to estimate the target speed.

Keywords: fast Fourier transform, spectral analysis, computational efficiency, speed, discrete-exponential functions, Vilenkin-Chrestenson functions.

Сравнительный анализ вычислительной эффективности быстрого преобразования Фурье в базисах дискретно-экспоненциальных функций и функций Виленкина-Крестенсона

Виталий Клобуков

ассистент кафедры средств защиты информации, факультета

кибербезопасности компьютерной и программной инженерии, Национальный Авиационный Университет, г. Киев, Украина

Анатолий Билецький

доктор технических наук, профессор кафедры электроники, робототехники, технологий мониторинга и интернета вещей, факультет аэронавигации, электроники и телекоммуникаций, Национальный Авиационный Университет, г. Киев, Украина

Аннотация. Объект исследования: эффективность быстрого преобразования Фурье в базисах дискретно-экспоненциальных функций и функций Виленкина-Крестенсона. Решаемая проблема: повышение вычислительной эффективности (быстродействия) быстрого преобразования Фурье при спектральном анализе сигналов. Основные научные результаты: Проанализировано что структуры графов БПФ в базисах ВКФ по сложности не отличаются от графов БПФ в базисах ДЭФ. При этом вычисление спектра в базисе ВКФ (при некоторых значениях параметра базиса m) требует меньше аппаратурных затрат либо машинного времени (скорость обработки возрастает почти на порядок). Это свойство может быть использовано для реализации устройств, оценивающих частоту принятого дискретно-экспоненциального сигнала в базисе ВКФ, обладающих более высоким быстродействием, чем аналогичное устройство, работающее с базисом ДЭФ. Область практического использования результатов исследования:

Алгоритм спектрального анализа в базисах ВКФ может быть использован в быстродействующих радиолокационных устройствах (в частности, бытовых: бортовая система автомобиля, сигнализационные системы и т.д.) для оценки скорости цели.

Ключевые слова: быстрое преобразование Фурье, спектральный анализ, вычислительная эффективность, быстродействие, дискретно-экспоненциальные функции, функций Виленкина-Крестенсона.

Problem resolution. The object of the research is the process of analysing the computational efficiency of the fast Fourier transform in the discrete-exponential functions and Vilenkin-Chrestenson functions bases. The development of modern radar systems, which contributes to improving the accuracy of determining the coordinates and speeds of targets, requires improving the performance of radar signal processing systems. At the same time, an increase in the number and power of devices operating at high and ultra-high frequencies creates additional interference, which increases the interference created by the reflected signal and natural electromagnetic oscillations. This fact, in turn, requires an increase in the noise immunity of radar systems, which is provided not only by an increase in the power of probing radiation, an improvement in the hardware of the radar station but also by algorithms for processing a noisy signal, which helps to separate the useful signal from noise [10].

One of the families of useful signal filtering methods is a family of algorithms based on the analysis of the spectrum of the received signal [1, 2, 9, 10]. These methods involve receiving a signal and converting it to obtain its spectrum in one of the bases. After that, the parameters of the received signal are estimated by analysing not the signal itself, but by analysing its spectrum. Further, the operation of extracting the spectrum of the received signal will be called generalized Fourier transforms.

A special case of generalized Fourier transforms are the classical Fourier transforms [3, 4, 5, 6, 7]. In the case of discrete signal processing, the classical Fourier transforms basis is a set of Discrete Exponential Functions (DEF). This basis has been widely used in many branches of technology related to signal to process. Radar was no exception. The main factors in the popularity of the DEF bases for processing radar signals are the harmonic nature of many signals that have to be dealt with in radar [4, 11], and the emergence of digital Fast Fourier Transform (FFT) methods [3, 4, 8]. The first factor, because the DEFs bases are also harmonic in nature, provides a high concentration of signal energy in the vicinity of one or more output frequency channels of the FFT processor. The second factor makes it possible to perform classical Fourier transforms at a speed that modern computing systems can easily handle.

However, the Fourier basis is far from the only basis in which orthogonal transformations are possible.

Analysis of recent research and publications. Many domestic and foreign scientists, namely: V. I. Shchetinin, V.N. Maloziemov, S.M. Masharskyi, A. Ya. Beletskyi and S.N. Ahiievich and others write about the possibilities of using spectral analysis of radio signals in the VCF bases.

Purpose of the article: To determine some aspects of the efficiency of the fast Fourier transform in the discrete-exponential functions and Vilenkin-Chrestenson functions bases.

Statement of the basic material. For example, the Vilenkin-Chrestenson functions (VCF) basis provides higher performance when performing the FFT than the DEF basis. In addition, this basis does not accumulate the rounding error that the DEF basis gives for large sample sizes [7]. Therefore, the study of this basis for the purpose of its applicability for spectral analysis of radar signals is relevant and promising.

In this paper, cases are considered when the order of the FFT and the number of samples in the received sequence is a binary rational number (N = 2^m) only.

Consider a graph of an 8-point FFT in the DEF basis in Fig.

1.

Figure 1: Graph of 8-point FFT in the DEF mother basis

Based on Figure 1 that the samples of the input signal are located at the inputs of the FFT graph in binary-inverse order.

When forming FFT graphs in the VCF basis, there will be a sequence obtained by an m-arypermutation of a natural sequence.

If N is an m-rational number, then the number of elementary transformation graphs (the FFT processors in the DEF basis with the m inputs) in the FFT graphs in the DEF and VCF bases is the same. Accordingly, the number of multiplications of numbers by the degree of the phase-shifting factor is the same. In this case, all elementary graphs that make up the FFT scheme in the DEF basis can be divided into the following two groups: the first, consisting of elementary graphs, the coefficients of which repeat the coefficients of the elementary graphs of the transformation scheme in the VCF basis, the second: with different coefficients. If the elementary graphs of the second group require more computer time than the graphs of the first group, the FFT in the VCF basis will run faster than the FFT in the DEF basis. In this case, the payoff will depend on the ratio between the numbers of graphs in the first and second groups, as well as on the ratio of the execution time of these graphs. If only addition operations are required to execute the graphs of the first group, then the graphs of the second group require multiplication of irrational numbers.

Let us estimate the relations between the number of members of these two groups for the general case. Let the FFT dimension be N = mⁿ. The first of these transformations in the DEF basis consists of __?1 elementary graphs of the first group. At the second stage, each of the m graphs belongs to the first group, at the third - each and _2, at the fourth - each of them _3, etc. Having calculated the sum of this geometric progression, we come to the result:

In this case, the total number of elementary graphs in the FFT scheme is mⁿ~¹n. Accordingly, the relative number of elementary graphs of the first group will be as follows:

The relative number of elementary graphs of the second group is equal to the following:

Let us estimate the time required to execute the graphs of both groups. Let us denote by the t₁ time required for the execution of the graphs of the first group, by t₂ as the time for the graphs of the second group, by K as the number of elementary graphs in the FFT scheme. Then the total time to execute the FFT will be equal to

Consider a special case at the base _ = 4, then the elementary FFT graph in the VCF basis is a multiplication by a matrix of size 4 Ч 4 :

To perform multiplication by such a matrix of a column vector consisting of 4 complex elements, it is required to perform 24 addition operations of real numbers. Let us denote in t+ terms of the time required to complete the addition, and t_x in terms of - the time of multiplication. Herewith t₁ - 24t+. The total execution time of the FFT in the VCF basis will be as follows:

The graphs of the second group correspond to the transformation matrix, as follows:

where the q means coefficient that depends on the dimension of the FFT and the number of the transformation stage.

In general, the execution of such a graph will require 36 multiplication and 42 addition operations. Respectively, t₂ - 36t_x + 42t+. And the total time to complete the FFT operation in the DEF basis will be as follows:

Taking into account (1) - (3), (5), (6), we arrive at an expression for estimating the gain in time when passing from the DEF basis to the VCF basis with the m = 4 basis:

In modern computing, when performing a fixed-point multiplication operation, it is considered that t_x = 5t+, for floating-point operations - t_x = t+. Taking these estimates into account, we rewrite expression (7):

For floating point multiplication,

For fixed-point multiplication.

The dependence of the gain in the f amount of computations in the transition from FFT-DEF to FFT-VCF on the order of the FFT in floating-point multiplications is shown in Fig. 2. The maximum possible (atn ^ от) value f is 3.5, the actually achievable value is about three.

Figure 2: Dependence of the gain on the dimension of the FFT If the FFT algorithm in the VCF basis takes into account the factorization of the matrix (4), then the final expression for estimating the speed gain in the case of floating-point multiplication will take the following form:

In this case, the f maximum possible value will be 5. Its realistically achievable value will be about 4. When using fixed point multiplication, the payoff is about 11. fourier signals spectral

The comparative analysis of the computational efficiency of the fast Fourier transform in the bases of discrete-exponential functions and the bases of Vilenkin- Chrestenson functions proves the promising and expedient use of the VCF bases. In the spectral analysis of signals, for certain classes of applied problems of spectral analysis of signals, where the priority factor is the speed of the operation of the fast Fourier transform, the use of the VCF bases is an effective solution. A promising direction for further research of the effectiveness of the use of the VCF bases in the spectral analysis of signals is the issue of a hardware implementation of a specialized digital device (a special computer), taking into account the peculiarities of the architecture of the digital element base.

Conclusions

The structures of the FFT graphs in the VCF bases do not differ in complexity from the FFT graphs in the DEF bases. In this case, the calculation of the spectrum in the VCF basis (for some values of the m basis parameter) requires fewer hardware costs or computer time (the processing speed increases by almost an order of magnitude). This property can be used to implement devices that estimate the frequency of the received discrete-exponential signal in the VCF basis, which have a higher speed than a similar device working with the DEF basis.

References

1 Tryz, V., (1972), Theory of Detection, Estimation and Modulation, Moscow: The Soviet Radio.

2 Goldenberg, L.M., Matiushkin, B.D., Poliak, M.N. (1985) Digital Signal Processing, Moscow: The Radio and Communication.

3 Trakhtman, A.M. (1972) Introduction to the Generalized Spectral Theory of Signals, Moscow: The Soviet Radio.

4 Manovtsev, A.P. (1975) Optimal Bases in Problems of Message Representation and Filtering, Kyiv: The Radiotekhnika, No. 7, P. 26-34.

5 Trakhtman, A.M., Trakhtman, V.A. (1975) Foundations of the Theory of Discrete Signals at Finite Intervals, Moscow: The Soviet Radio.

6 Beletskyi, A. Ya., Beletskyi, A.A., Beletskyi, Ye.A. (2007) Grey's Transformations, Kyiv: The NAU Book Publishing House.

7 Kalmykov, I.A. (2007) Generalized Discrete Fourier Transform for Rings of Irreducible Polynomials, The Advances in Modern Natural Science, No.5, P. 87-98.

8 Tarakanov, A.V. (2008) Assessment of the Possibilities for the Resolution of Radar Signals by Classical and "Modern" Methods of Spectral Estimation, Ulianovsk: USTU, P. 128-136.

9 Hemming, R.V. (1980) Digital Filters, Moscow: The Soviet Radio.

10 Marple Jr., S.L. (1990) Digital Spectral Analysis and Its Applications, Moscow: The Mir.

11 Maksimov, M.V. (1976) Protection Against Interference, Moscow: The Soviet Radio.

Литература:

1 Триз В., (1972), Теория обнаружения, оценок и модуляции, Москва: Советское радио.

2 Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. (1985) Цифровая обработка сигналов, Москва: Радио и связь.

3 Трахтман А.М. (1972) Введение в обобщенную спектральную теорию сигналов, Москва: Советское радио.

4 Мановцев А.П. (1975) Оптимальные базисы в задачах представления и фильтрации сообщений, Киев: Радиотехника №7, 26-34.

5 Трахтман А.М., Трахтман В.А. (1975) Основы теории дискретных сигналов на конечных интервалах, Москва: Советское радио.

6 Белецкий А.Я., Белецкий А.А., Белецкий Е.А. (2007) Преобразования грея, Киев: Книжное издательство НАУ.

7 Калмыков И.А. (2007) Обобщённое дискретное преобразование Фурье для колец неприводимых полиномов, Успехи современного естествознания №5, 87-98.

8 Тараканов А.В. (2008) Оценка возможностей по разрешению радиолокационных сигналов классическими и "современными" методами спектрального оценивания, Ульяновск: УГТУ, 128-136.

9 Хемминг Р.В. (1980) Цифровые фильтры, Москва: Советское радио.

10 Марпл-младший С.Л. (1990) Цифровой спектральный анализ и его приложения, Москва: Мир.

11 Максимов М.В. (1976) Защита от помех, Москва: Советское радио.

Размещено на Allbest.ru