10.19. Поточный свертыватель с тактовой частотой 10 МГц

Рассмотрим радиолокатор, в котором эхо-сигналы необходимо обрабатывать в полосе 10 МГц с помощью фильтра, согласованного с разнообразными зондирующими сигналами (типа ЛЧМ-сигналов, равномерных или неравномерных пачек импульсов и т. д.). Для обеспечения требуемой гибкости фильтра нужно предусмотреть возможность простого изменения его частотной характеристики. Допустим,  что  максимальная длительность сигнала  составляет около 100 мкс, так что произведение полосы сигнала на его длительность равно 1000. Это означает, что если фильтр построен, например, на основе многоотводной цифровой линии задержки, то число отводов должно быть равно 1000, причем каждые 100 нс нужно выполнять 1000 комплексных умножений. Решить эту задачу при использовании современных микросхем вряд ли удастся. По видимому, это тот случай, когда построение цифровой системы можно   осуществить,   только   вычисляя  свертку  методом  БПФ. С учетом предыдущего примера можно сделать вывод, что при вычислении свертки с использованием БПФ нужно за 102,4 мкс выполнить два 2048-точечных преобразования. Общее число базовых операций, выполняемых за это время, равно , т. е. 22 528, так что каждые 100 нс приходится выполнять 22 базовые операции. Только недавно появились устройства, способные выполнить комплексное   умножение  за   100  нс,  поэтому  в данном  случае потребуется 22 таких устройства,  т. е. ровно столько,   сколько необходимо  при  построении  поточной схемы БПФ, описанной в разд. 10.10. Блок-схема свертывателя и его временные диаграммы приведены на фиг. 10.41. Свертыватель содержит два поточных блока БПФ и блок формирования частотной характеристики согласованного фильтра.  Все три блока работают параллельно. Поскольку при поточной обработке можно одновременно выполнять два БПФ, целесообразно ввести двукратное перекрытие сигналов, что полностью согласуется  с  режимом работы  поточной схемы и позволяет довести эффективность системы до 100%. Для каждого массива из 2048 отсчетов на двух выходах первого поточного блока БПФ   появляются две  последовательности   сигналов.   На  двух выходах второго поточного блока БПФ появляются «правильная» половина отфильтрованного массива и «неправильная» (первая) половина следующего массива свертки. Таким образом, отфильтрованный  сигнал   формируется  в  реальном времени по методу перекрытия с накоплением из половины выходных отсчетов.

Фиг. 10.41. Блок-схема свертывателя, использующего БПФ.

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

Фиг. 10.42. Относительные эффективности при различных размерах БПФ.

Уменьшим, например, полосу входного сигнала от 10 до 0,8 МГц. Заменим в обоих поточных блоках БПФ 11 АУ буферными регистрами, которые будут поочередно подключаться к одному быстродействующему АУ. Таким образом, ори использовании только двух АУ (по одному на каждый поточный блок БПФ) работоспособность всего устройства сохранится, но теперь базовые операции всех этапов поточного блока будут выполняться с помощью одного и того же АУ. Если же необходимо обрабатывать сигнал с полосой 3,2 МГц, для каждого из поточных блоков БПФ придется использовать по 4 АУ, три из которых будут обслуживать по три этапа БПФ и одно — два этапа. Таким образом, поточная схема обработки сохраняет высокую эффективность в широком диапазоне тактовых частот.

После выбора основных характеристик системы можно перейти к более детальному проектированию. В системе фиг. 10.41, например, могут использоваться до 5 ЗУ. К ним относятся:

1)  ЗУ, входящие в состав поточных блоков БПФ;

2)  ЗУ для хранения коэффициентов, используемых в поточных схемах;

3)  ЗУ частотной характеристики фильтра;

4)  входной буферный накопитель;

5)  выходной буферный накопитель.

Кроме того, нужно выбрать систему счисления, используемую в АУ, разрядность ячеек памяти, а также методику масштабирования и предотвращения переполнений.

Свертка методами БПФ не обязательно выполняется при двукратном перекрытии. Действительно, увеличивая размер БПФ, можно повысить эффективность свертывателя. Это обусловлено тем, что при вычислении свертки методом БПФ объем бесполезной информации зависит как от длины свертываемых последовательностей, так и от размера БПФ.

Данное положение проиллюстрировано тремя примерами (фиг. 10.42). Предположим, что во всех случаях длина импульсной характеристики равна  (что соответствует единичному отрезку на фиг. 10.42), но размер БПФ в первом примере равен , во втором — , а в третьем — .

Как уже было показано, в первом случае для получения  полезных отсчетов после выполнения каждой пары преобразований (размером по  отсчетов) приходится отбрасывать половину конечных результатов (см. четвертую строку первого примера). Во втором примере (при размере преобразований по ) остается  полезных отсчетов. Это означает, что для выполнения -точечного БПФ можно отвести время, пропорциональное . Аналогично в третьем примере для -точечного преобразования можно отвести время, пропорциональное . Таким образом, в примерах 1, 2 и 3 относительные эффективности вычислений равны 1:2, 3:4 и 7:8. В системах с очень большим быстродействием увеличение размера преобразования с  до  может привести к существенному упрощению аппаратуры.

ЛИТЕРАТУРА

1.  Bergland G. D., Fast Fourier Transform Hardware Implementations — An Overview, IEEE Trans, on Audio and Electroacoustics, AU-17, 104—108 (June 1969).

2.   Groginsky H. L., Works G. A., A Pipeline Fast Fourier Transform, IEEE Trans,  on Computers, C-19, 1015—1019 (Nov. 1970).

3.   Klahn R., Shively R. R., Gomez E., Gilmartin M. J., The Time-Saver: FFT Hardware, Electronics, 92—97 (June 1968); есть русский перевод: Клан, Шайвли, Гонец, Гилмартин, Специализированный процессор для быстрого решения задач гармонического анализа, Электроника, т. 41, №   13   (1968).

4.   Pease M. С, An Adaptation of the Fast Fourier Transform for Parallel Processing, JACM, 15, 252—264 (April 1968).

5.  Shively R. R., A Digital Processor to Generate Spectra in Real Time, IEEE Trans, on Computers, C-17, 485—491 (May 1968).

6.   Bergland G. D. Wilson D. E., An FFT Alorithm for a Global Highly-Parallel Processor, IEEE Trans, on Audio and Electroacoustics, AU-17, 125—127   (June 1969).

7.   Bergland G. D., Fast Fourier Transform Hardware Implementations — A Survey, IEEE Trans, on Audio and Electroacoustics, AU-17, 109—119 (June 1969).

8.   Theilheimer F., A Matrix Version of the Fast Fourier Transform, IEEE Trans, on Audio and Electroacoustics, AU-17, No. 2, 158—161 (June 1969).

9.  O'Leary G. C., Nonrecursive Digital Filtering Using Cascade Fast Fourier Transformers, IEEE Trans, on Audio and Electroacoustics, AU-18, No. 2, 177—183  (June 1970).

10. Veenkant R. L., A Serial Minded FFT, IEEE Trans, on Audio and Electroacoustics, AU-20, No. 3, 180—184 (Aug 1972).

11. Gold В., Bially Т., Parallelism in Fast Fourier Transform Hardware, IEEE Trans,  on Audio and Electroacoustics,  AU-21, No. 1,  5—16  (Feb-   1973).

Эффекты,  возникающие при БПФ вследствие конечной разрядности чисел

1.   Oppenheim A. VM Weinstein С. J., Effects of Finite Register Length in Digital Filtering and the Fast Fourier Transform, Proc. IEEE, 60, No. 8, 957—976 (Aug. 1972); есть русский перевод: Оппенгейм, Вайнштейн, Влияние конечной длины регистра при цифровой фильтрации и быстром преобразовании Фурье, ТИИЭР, т. 60, № 8, стр. 41—65 (1969).

2.  Welch P. D., A Fixed-Point Fast Fourier Transform Error Analysis, IEEE Trans. Audio and Electroacoustics, AU-17,  No. 2, 151—157  (June 1969).

3.   Weinstein C. J., Roundoff Noise in Floating Point Fast Fourier Tranform Computation, IEEE Trans, on Audio and Electroacoustics, AU-17, No. 3, 209—215 (Sept. 1969).

4.   Kaneko Т., Liu В., Accumulation of Round-Off Errors in Fast Fourier Transforms, /. Assn. Сотр. Mack., 17, No. 4, 637—654 (Oct. 1970).