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.