Выбор поворачивающих множителей в алгоритме монобитного быстрого преобразования Фурье

УДК 621.37

ВЫБОР ПОВОРАЧИВАЮЩИХ МНОЖИТЕЛЕЙ В АЛГОРИТМЕ МОНОБИТНОГО БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

А.Н. Николаев

Приводятся результаты исследования алгоритма монобитного быстрого преобразования Фурье. Рассматриваются варианты реализации алгоритма на основе различных наборов поворачивающих множителей. Выбор поворачивающих множителей влияет на качество результата монобитного быстрого преобразования Фурье и на ресурсы ПЛИС, необходимые для реализации алгоритма. Количественная оценка такого влияния в открытой литературе не приводится. Предметом исследования является уровень нежелательных составляющих в спектре анализируемого сигнала. Приводятся результаты расчетов числа ресурсов ПЛИС, требуемых для реализации различных вариантов алгоритма монобитного быстрого преобразования Фурье. Расчеты проведены для 1024-точечного преобразования. Результаты исследований могут быть использованы при разработке и практической реализации устройств цифровой обработки сигналов на ПЛИС, использующих алгоритм монобитного быстрого преобразования Фурье.

Ключевые слова: монобитное БПФ, ПЛИС.

Введение

Алгоритм монобитного быстрого преобразования Фурье (БПФ), предложенный и исследованный в [1-8], позволяет сократить число требуемых ресурсов при реализации на ПЛИС за счет исключения операций умножения. Поворачивающие множители в алгоритме монобитного БПФ могут принимать значения из наборов:

{1,7, -1, -Л

или

{1 + Л, -1 + Л, -1 - Л, 1 - Л}.

Автор [1, 3] отмечает, что объединение этих наборов значений поворачивающих множителей в один набор {1, 1 + 7, 7, -1 + 7, -1, -1 -7, -7, 1 -7} позволит улучшить качество преобразования, выраженное в уменьшении уровня нежелательных (паразитных) составляющих в спектре анализируемого сигнала. Однако количественных показателей такого улучшения не приводится.

В настоящей статье приведена оценка влияния выбора набора поворачивающих множителей на уровень нежелательных составляющих в спектре анализируемого сигнала, а также результаты расчета ресурсов ПЛИС, необходимых для реализации различных вариантов алгоритма.

1. Постановка задачи

Суть алгоритма монобитного БПФ сводится к следующему. В дискретном БПФ

- 72 ккп

Х(Ю = !"=о Х(п)е N поворачивающие множители Жкп = ехр(-]пкп/К) заменяются наборами:

Жкп = 1 + 7, 0 < 0 < п/2;

Жкп = -1 + 7, п/2 < 0 < п;

Жкп = -1 -7, п < 0 < 3п/24;

Жкп = 1 -7, 3п/2 < 0 < 2п

или:

Жкп = 1, -п/4 < 0 < п/4;

Жкп = 7, 3п/2 < 0 < п/4;

Жкп = -1, -3п/4 < 0 < 3п/4;

Жкп = -7, -3п/4 < 0 < -п/4.

Графически это можно представить так как показано на рис. 1. Объединение этих наборов в один иллюстрирует рис. 2.

_ „ „ рачивающих множителей моно-

Рис. 1. Графическое представление поворачивающих множителей битного бпф

монобитного БПФ

Сигнал на входе исследуемого алгоритма представляется последовательностью знаков его отсчетов:

sign(x) = X / |х|,

где х = cos(2п/Cn At) - отсчеты тестового гармонического сигнала.

В ходе исследований была поставлена задача оценки уровня нежелательных составляющих в спектре анализируемого сигнала для различных вариантов наборов поворачивающих множителей. Была разработана программа на языке VHDL для исследования требуемых для реализации алгоритма ресурсов ПЛИС.

2. Результаты моделирования и расчетов

Результаты оценки уровня нежелательных составляющих в спектре анализируемого сигнала, полученные с применением пакета МаЙаЬ, приведены в табл. 1.

Таблица 1

Результаты моделирования

Набор поворачивающих множителей Уровень нежелательных составляющих, дБ, относительно полезной составляющей

{1,7, -1, -7} -10,075

{1 + 7,-1 + 7,-1 - 7, 1 - 7} -10,71

{1, 1 + 7,7, -1 + 7, -1, -1 -7, -7, 1 -7} -16,33

Результаты расчета ресурсов ПЛИС, необходимых для реализации различных вариантов алгоритма (число точек преобразования - 1024), приведены в табл. 2.

Таблица 2

Результаты расчетов

Набор поворачивающих множителей Число логических элементов ПЛИС

{1,7, -1, -7} 49 155

{1 + 7,-1 + 7,-1 - 7, 1 - 7} 61 955

{1, 1 + 7,7, -1 + 7, -1, -1 -7, -7, 1 -7} 82 504

Заключение

Анализ полученных результатов позволяет сделать следующие выводы.

1. С точки зрения уровня нежелательных составляющих в спектре анализируемого сигнала, первые два варианта наборов поворачивающих множителей дают практически одинаковые результаты. Использование объединенного набора поворачивающих множителей улучшает соотношение полезной и нежелательных составляющих на 6 дБ.

Выбор поворачивающих множителей в алгоритме монобитного быстрого преобразования Фурье

2. При одинаковом уровне нежелательных составляющих набор {1, j, -1, —} поворачивающих множителей требует наименьшего числа ресурсов при реализации на ПЛИС. Улучшение соотношения полезной и нежелательных составляющих в спектре анализируемого сигнала, которое можно достичь путем применения объединенного набора {1, 1 + j, j, -1 + j, -1, -1 - j, -j, 1 - j} поворачивающих множителей, требует увеличения числа ресурсов ПЛИС на 40 % по сравнению с первым вариантом.

Литература

1. Tsui, J.B.Y. Digital Techniques for Wideband Receivers / J.B.Y. Tsui - 2nd ed. - SciTech Publishing Inc, 2004. - 571 p.

2. Flynn, J.E. GPS coarse acquisition using the monobit FFT algorithmin a broadband receiver / J.E. Flynn. - Wrighte state university, 2008. - 97p.

3. US Patent No. 7,440,989 B1, Kernel function approximation and receiver / J. Tsui, J.M. Emmert, S.L. Hary, D.M. Lin, N.A. Requignot, K.M. Graves. - 21 Oct., 2008.

4. US Patent No. 5,917,737, Fourier transform mechanization using one bit Kernel function / J. Tsui, J. Schamus. - 29 June 1999.

5. US Patent No. 5,963,164, Monobit Kernel function electronic warfare receiver for characterizing two input signals / J. Tsui, D.H. Kaneshiro, J. Schamus. - 5 Oct., 1999.

6. US Patent No. 6,448,921 B1, Channelized monobit electronic warfare radio receiver / J. Tsui, J.N. Hedge, V.D. Chakravathy, K.M. Graves. -10 Sept., 2002.

7. US Statutory Invention Registration No. H2109 H, Passive microwave direction finding with monobit Fourier transformation receiver and matrix coupled antenna / J. Tsui, K.M. Graves. -7 Sept., 2004.

8. US Patent No. 5,793,323, Two signal monobit electronic warfare receiver / J.B.Y. Tsui. - 11 Aug. 1998.

Николаев Андрей Николаевич, старший преподаватель кафедры инфокоммуникационных технологий, Южно-Уральский государственный университет (г. Челябинск); Andrew.N@rambler.ru.

Bulletin of the South Ural State University Series “Computer Technologies, Automatic Control, Radio Electronics”

2013, vol. 13, no. 3, pp. 137-140

SELECTION OF A ROTATION FACTORS IN MONOBIT FAST FOURIER TRANSFORM

A.N. Nikolaev, South Ural State University, Chelyabinsk, Russian Federation,

Andrew. N@rambler. ru

The article presents the results of a study of the monobit fast Fourier transform algorithm. Variants of the algorithm on the basis of different sets of rotation factors. Choosing rotation factors affect the quality of the result monobit fast Fourier transform on FPGA resources needed to implement the algorithm. Quantitative assessment of this impact in the open literature are given. The subject of the study is the rate of unwanted components in the spectrum of the analyzed signal. The results of calculation of the number of the FPGA resources required for the implementation of different versions of the monobit fast Fourier transform algorithm. The calculations were made for the 1024-point conversion. The research results can be used in the development and practical implementation of digital signal processing on FPGA, using an monobit fast Fourier transforms algorithm.

Keywords: monobit FFT, FPGA.

References

1. Tsui J.B.Y. Digital Techniques for Wideband Receivers. 2nd ed. SciTech Publishing Inc, 2004. 571 p.

2. Flynn J.E. GPS Coarse Acquisition Using the Monobit FFT Algorithmin a Broadband Receiver. Wrighte state university, 2008. 97 p.

3. Tsui J., Emmert J.M., Hary S.L., Lin D.M., Requignot N.A., Graves K.M. US Patent

No. 7,440,989 B1. Kernel Function Approximation and Receiver, 21 October, 2008.

4. Tsui J.B.Y., Schamus J. US Patent No. 5,917,737, Fourier Transform Mechanization Using One Bit Kernel Function, 29 June 1999.

5. Tsui J., Kaneshiro D.H., Schamus J. US Patent No. 5,963,164, Monobit Kernel Function Electronic Warfare Receiver for Characterizing Two Input Signals, 5 October, 1999.

6. Tsui J., Hedge J.N., Chakravathy V.D., Graves K.M.US Patent No. 6,448,921 B1, Channelized

Monobit Electronic Warfare Radio Receiver, 10 September, 2002.

7. Tsui J.B.Y., Graves K. M. US Statutory Invention Registration No. H2109 H, Passive Microwave Direction Finding with Monobit Fourier Transformation Receiver and Matrix Coupled Antenna, 7 September, 2004.

8. Tsui, J.B.Y., US Patent No. 5,793,323, Two Signal MonobitElectronic Warfare Receiver, 11 August 1998.

Поступила в редакцию 8 мая 2013 г.