Раздел: Документация
0 ... 57 58 59 60 61 62 63 ... 78   Далее результат {z} 128-точечной циклической свертки {xJn} и {h1 вычисляется с использованием ЧПФ. Последовательность \у1Л для 1 <i<4 получается отбрасыванием первой половины и сохранением второй половины каждой циклической свертки [zl }, вычисленной ранее. Наконец, желаемая выходная последовательность {ук\ равна арифметической сумме \у для 1</<4. В результате линейная свертка {хп} и {hm\ вычисляется по следующему алгоритму. 1.Расчленить {hm J на последовательности \h\jB соответствии с (20.6). 2.Вычислить линейную свертку {h}) и{х с помощью стандартного метода перекрытий с накоплением следующим образом: а)разделить {хп} на последовательности {xJn } , как указано в (20.7); б)вычислить циклическую свертку {z}k] последовательностей {х} г и mil с использованием ЧПФ; в)получить {уЦ отбрасыванием первой половины и сохранением второй половины каждой свертки {z}k } , вычисленной на шаге б. 3.Определить последовательность \Ук\ .как арифметическую сумму {у 1к] . На рис. 20.10 показан пример обобщенного метода перекрытий с накоплением. Для простоты на диаграмме рис. 20.10 данные показаны, как если бы они являлись непрерывными. Для других случаев обобщенного метода перекрытий с накоплением построение аналогично. Ввод t, /У,м,ад I Вычисление длины преобразования L Расщепление h(m) на Ь1(ш) для ЫЫ2МЦ=1 Вычисление Hl(k) = (1/н) чпФ(в1(ш)) для 0Ы1 0k<L-1 I Разделение х(п) на xJ(n) для 0j2N/L = J I Вычисление XJ(k) = чПФ(хШ для 0£/4J, 0£K*L-1 I у(к)<-0 для 0<kN + M-2 ЦК) -е-н1(к) XJ(k), OzkL-f z(k) +*г-члф-1 (Z(k)) t Р +-(i-t)L/2+(j-l)L/2 y(K+P)+-y(k+P) + z(k), L/2kL-f  Рис. 20.11. Блок-схема программы моделирования обобщенного метода перекрытий с накоплением 6Ь- 63 127 190 к Рис. 20Л2. Свертка двух прямоугольных импульсов над кольцом целых чисел по модулю числа Ферма с использованием метода обобщенных перекрытий с накоплением Для проверки корректности обобщенного метода перекрытий с накоплением была написана моделирующая программа. На блок-схеме этой программы (рис. 20.11) через t,MnNобозначены Ft, длина импульсной характеристики фильтра и длина последовательности данных соответственно. Длина преобразования L = 2т, если а = уД для ЧПФ над полем Ft ,иЬ= 2t+l, если х п 128-точечное ЧПФ 128-точечное обратное ЧПФ  -64 128-точечное обратное ЧПФ hi 128-точечное обратное ЧПФ и; ,-128 -н8Нг-* 128-точечное обратное чпф -54 Ш> импульсной характеристики фильтра а=2 для ЧПФ над полем Ft. По программе выполнялся расчет для нескольких примеров. Результаты расчета свертки, полученные с использованием метода перекрытий с накоплением, точно совпадают с результатами, полученными непосредственным вычислением. Результаты свертки двух последовательностей единичной амплитуды каждая, полученные по программе моделирования перекрытий с накоплением для ЧПФ, приведены на рис. 20.12. Длина этих двух последовательностей равна 64 и 128 соответственно. Схема цифрового фильтра параллельной архитектуры, реализующего описанный обобщенный метод перекрытий с накоплением, приведена на рис. 20.13. Последовательность{щ }на рис. 20.13 есть ЧПФ последовательности {hlm}, умноженной на 1/N, где 1 </<4. Начиная с шага 2в представленного алгоритма, один из двух результатов операции обратного ЧПФ не нужен. Следовательно, последняя бабочка ЧПФ в обратной схеме ЧПФ является вырожденной и элементов задержки, ассоциированных с этой "бабочкой", не требуется. Сумматор на рис. 20.13 выполняет обычное двоичное сложение, а не сложение по модулю Ft. 20.5. ЗАКЛЮЧЕНИЕ Для вычисления 128-точечного числового преобразования Ферма разработана конвейерная структура. В этом 128-точечном ЧПФ требуются только операции сложения и циклического сдвига. Схема циклического сдвигового регистра модифицирована для выполнения умножения целых чисел на степень числа 2 по модулю числа Ферма. Аппаратная реализация "бабочки. ЧПФ для 32-точечного ЧПФ над полем F4 показана на рис. 20.14. Обобщен метод перекрытий с накоплением для вычисления линейной свертки в цифровом фильтре с произвольной длиной входной последовательности данных и импульсной характеристики фильтра. Разработана архитектура, реализующая этот обобщенный метод простой комбинацией одного элемента 128-точечного ЧПФ и нескольких элементов обратных ЧПФ. Преимущества реализации цифрового фильтра с помощью обобщенного метода перекрытий с накоплением и ЧПФ перед более распространенным  а. ЯЛ * . *4 Л. V it: Щ if-i g . g; ; WWiЙ Рис. 20.14. Аппаратная реализация операции бабочка ЧПФ для 32-точечного ЧПФ над полем F4 БПФ состоят в следующем: 1) не требуются операции умножения; 2) преодолевается противоречие между длиной преобразования и шириной динамического диапазона; 3) длина слова является приемлемой для многих практических задач, так как слово большего размера необходимо только на последнем шаге алгоритма; 4) длины входных данных и импульсной характеристики фильтра могут быть различны и произвольны; 5) архитектура является регулярной, расширяемой и, следовательно, удобной для исполнения в виде СБИС. СПИСОК ЛИТЕРАТУРЫ [1] L. R. Rabiner and В. Gold, Theory and Application of Digital Signal Processing, Prentice-Hall, Englewood Cliffs, N.J., 1975. [2] J. H. McClellan and С. M. Rader, Number Theory in Digital Signal Processing, Prentice-Hall, Englewood Cliffs, N.J., 1979. [3] С. M. Rader, "Discrete Convolutions via Mersenne Transforms," IEEE Trans. Comput*, Cr2/(12):1269-1273 (Dec. 1972). [4] R. C. Agarwal and C. S. Burrus, "Fast Convolution Using Fermat Number Transforms with Applications to Digital Filtering," IEEE Trans. Acoust. Speech Signal Process., ASSP-22(2):Sl-97 (Apr. 1974a). [5] R. C. Agarwal and C. S. Burrus, "Number Theoretical Transforms to Implement Fast Digital Convolution," Proc. IEEE, 65(4) :550-560 (Apr. 1975). £6] I. S. Reed and Т. K. Truong, "The Use of Finite Field to Compute Convolutions," IEEE Trans. Inf. Theory, /T-2/(2):208-213 (Mar. 1975). [7] J. M. Pollard, "The Fast Fourier Transform in a Finite Field," Math. Сотр., 25:365-374 (Apr. 1971). [8] I. S. Reed, Т. K. Truong, Y. S. Kwoh, and E. L. Hall, "Image Processing by Transforms over a Finite Field," IEEE Trans. Comput., C-26(9):874-881 (Sept. 1977). [9] С. M. Radar, "On the Application of the Number Theoretic Methods of High Speed Convolution to Two-Dimensional Filtering," IEEE Trans. Circuits Syst.9 CAS-22(6):575 (June 1975). [10] I. S. Reed, Y. S. Kwoh, Т. K. Truong, and E. L. Hall, "X-Ray Reconstruction by Finite Field Transforms," IEEE Trans. Nuclear Sci., NS-2¥(l):843-849 (Feb. 1977). [11] I. S. Reed, Т. K. Truong, and L. R. Welch, "The Fast Decoding of Reed-Solomon Codes Using Fermat Number Transforms," IEEE Trans. Inf. Theory, /T-2¥(4):497-499 (July 1978). [12] H. F. A. Roots and M. R. Best, "Concatenated Coding on a Spacecraft-to-Ground Telemetry Channel Performance," Process. ICC 81, Denver, Colo., 1981. [13] J. H. McClellan, "Hardware Realization of a Fermat Number Transform," IEEE Trans. Acoust. Speech Signal Process., ASSP-24(3):216-225 (June 1976). [14] L. M. Leibowitz, "A Simplified Binary Arithmetic for the Fermat Number Transform," IEEE Trans. Acoust. Speech Signal Process., ASSP-24(5):356-359 (Oct. 1976). [15] C. A. Mead and L. A. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass., 1980. Г. Травассос1 21.1. ВВЕДЕНИЕ Оценка частоты и угла прихода волны от точечного источника может рассматриваться как одна из областей применения кал маков ской фильтрации. Принятые на линейную решетку датчиков сигналы (рис. 21.1) несут информацию как об угле прихода волны, так и о частоте. Оценщик на рис. 21.1 может рассматриваться как система с пространственно-временным квантованием, где число датчиков m и число элементов памяти на датчик п определяют размер двумерного окна в пространстве сигнала. К двумерным сигналам применялись методы линейного прогнозирования [1,2]. В этих методах осуществляется предсказание наблюдаемых данных по методу наименьших квадратов и результаты используются для экстраполяции данных вне обозреваемого интервала наблюдения. Затем к полученным данным применяется двумерное быстрое преобразование Фурье. Хотя эти методы дают высокое разрешение как по частоте, так и по углу, при наличии аддитивного белого шума оценки получаются смещенными. Датчики v(k)Устройство, Оценки  Устройство оценивания Калманов-скиа фильтр X k/(dj Вычисление Калманов-ский фильтр /л Xk/U)z CK/Q)2 Вычисление Калманов-ский фильтр т ХК/ыт к/ц Вычисление РтМ Виковый детектор xz(k) Рис . 21.1. Схема определения максимального правдоподобия синусоидальных сигналов 1 Фирма Systolic Systems, Сан-Хосе, Калифорния. 369 ПРИМЕНЕНИЕ СИСТОЛИЧЕСКИХ МАТРИЦ В РЕКУРСИВНЫХ ФИЛЬТРАХ 0 ... 57 58 59 60 61 62 63 ... 78
|
