| Русский Русский | English English |
   
Главная Архив номеров
18 | 06 | 2019
10.14489/vkit.2016.07.pp.041-047

DOI: 10.14489/vkit.2016.07.pp.041-047

Чкан А. В.
МЕТОД ПОИСКА ИТЕРАЦИЙ С ПЕРЕПОЛНЕНИЕМ РАЗРЯДНОЙ СЕТКИ В АЛГОРИТМАХ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ПРИ ОБРАБОТКЕ ДАННЫХ В ФОРМАТЕ С ФИКСИРОВАННОЙ ЗАПЯТОЙ
(pp. 41-47)

Аннотация. Предложен метод, позволяющий на основе анализа входных данных с высокой достоверностью определять номера итераций с возможным переполнением разрядной сетки в алгоритмах быстрого преобразования Фурье с прореживанием по частоте и времени при обработке данных в формате с фиксированной запятой. Приведено обоснование использования операции масшта-бирования данных только на выявленных итерациях с возможным переполнением, что минимизирует число итераций, требующих масштабирования, и существенно снижает связанные с этим погрешности.

Ключевые слова:  быстрое преобразование Фурье; согласованная фильтрация; фиксированная запятая; методы устранения переполнений; масштабирование; конвейерная обработка.

 

Chkan A. V.
METHOD OF BIT OVERFLOW ITERATION SEARCH IN ALGORITHMS OF THE FAST FOURIER TRANSFORM FOR FIXED-POINT DATA PROCESSING
(pp. 41-47)

Abstract. Use of the algorithms of fast Fourier transform for fixed-point data processing requires application of methods that provide identification of possible overflow during performing arithmetic operations and their elimination with the help of scaling operation which consists in shifting bits to low-order positions and further suppression of the least significant digit. Here loss of a digit leads to total error increasing of the FFT algorithm. Therefore, to reduce the total error of the FFT algorithm it is necessary to minimize the number of iterations with scaling. That is why we have developed a new method of overflow elimination, which, on the base of analysis of input data of the FFT iterations, provides highly reliable identification of the iteration numbers that require scaling of output data. The sense of the method is to find a value with the maximum module in the input data array of the current iteration of the FFT algorithm. It is supposed that this value enters all inputs of the current iteration. Then, taking into account the maximum possible representation of the value within the allowed bit grid of the device that implements the FFT algorithm, we figure out the number of iteration with possible overflow that will require scaling. Using such approach we guarantee that all FFT iterations up to the one, which was figured out, have no overflows. In comparison with existing methods, the suggested method provides rather precise identification of iteration numbers with possible overflow with minimum hardware burden. The result of application of the method is considerable reduction of the calculation error and acceptable ratio “signal/noise” in the output of the FFT algorithm. Also, it is possible to implement FFT algorithms in pipeline computational devices. Besides, the suggested approach of identification of overflow iterations can be used in other methods of overflow elimination for search of iterations that require scaling.

Keywords: Fast Fourier transform; Matched filtering; Fixed point; Methods of overflow elimination; Scaling; Pipeline processing.

Рус

А. В. Чкан (ООО «Научно-исследовательский центр супер-ЭВМ и нейрокомпьютеров», Таганрог, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript  

Eng

A. V. Chkan (Supercomputers and Neurocomputers Research Center, Taganrog, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript  

Рус

1. Реконфигурируемые мультиконвейерные вычислительные структуры / И. А. Каляев и др.; под общ. ред. И. А. Каляева. 2-е изд., перераб. и доп. Ростов н/Д: Изд-во ЮНЦ РАН, 2009. 344 с.
2. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов: пер. с англ. М.: Мир, 1978. 848 с.
3. Масштабирование данных с фиксированной точкой в процедуре быстрой свертки / О. В. Ершова и др. // Радиотехника. 2015. № 4. С. 66 – 72.

Eng

1. Kaliaev I. A. (Ed.), Levin I. I., Semernikov E. A., Shmoilov V. I. (2009). Reconfigurable multi pipelined computational patterns. 2nd Ed. (revised and supplemented). Rostov-on-Don: Izdatel'stvo IuNTs RAN. [in Russian lan-guage]
2. Rabiner L., Gould B. (1978). Theory and application of digital signal processing. Moscow: Mir. [in Russian language]
3. Ershova O. V. et al. (2015). Scaling data from a fixed point in the fast convolution procedure. Radiotekhnika, (4), pp. 66-72. [in Russian language]

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2016.07.pp.041-047}

.

Eng

This article  is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2016.07.pp.041-047}

 

 

 

 

 

.

.

 

 

 
Поиск
Журнал КОНТРОЛЬ. ДИАГНОСТИКА
Баннер
Баннер
Баннер
Rambler's Top100 Яндекс цитирования