Разработка системы сжатия эхо-сигналов различной длительности
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? целесообразно рассмотреть структурную схему фильтра, функционирующего по алгоритму быстрой свертки (БС-фильтр) двух последовательностей с применением поточного быстрого преобразования Фурье. Блок - схема БС-фильтра приведена на рисунке 2.2.
Рисунок 2.2 Блок-схема фильтра быстрой свертки
Целесообразно заметить, что последовательность отсчетов x(n) может оказаться на много длиннее чем h(n). В этом случае рекомендуется производить секционирование линейной свертки, то есть разбить более длинную последовательность на секции, вычислить частичные свертки, из которых затем сформировать искомую выходную последовательность y(n). Существует несколько методов вычисления свертки при выполнении которых количество операций будет примерно одинаковым, однако логичнее всего выбрать метод перекрытия с накоплением, так как он больше всего подходит для вычисления свертки с применением алгоритмов поточного БПФ и ОБПФ.
iелью пояснения последнего утверждения рассмотрим сущность метода перекрытия с накоплением. Для примера рассмотрим последовательность HH(n) содержит Nh =256 отсчетов, а последовательность x(n) состоит из Nх = 128 и дополнена количеством N0 = 128 нулевых отсчетов. Таким образом, две следующие друг за другом последовательности x(n) перекрываются друг с другом на участках длиной по N0 отсчетов. Участок перекрытия находится в конце секции, что и является удобством при применении алгоритмов поточного БПФ и ОБПФ. В рассматриваемом методе нет никаких операций сложения отсчетов частичных сверток, в отличие от метода перекрытия с суммированием.
Теперь необходимо оценить количество операций на всех трех этапах вычисления. При вычислении БПФ по алгоритму с основанием 2 необходимо, чтобы количество обрабатываемых отсчетов было равно 2b, где b - целое число и не меньше, чем N = Nх + N0. Тогда БПФ будет N=256 - точечным. Нетрудно показать, что количество вычислений базовых операций [2], необходимых для выполнения любого алгоритма БПФ будет равно:
(N/2)log2N. (2.18)
Если учесть, что последовательность отсчетов x(n) комплексная, то для вычисления одной базовой операции необходимо произвести четыре умножения числами и шесть сложений/вычитаний, где все операции с действительными числами. Таким образом, для вычисления N - точечного БПФ необходимо произвести
сл БПФ = 4.(N/2)log2N = 2.N.log2N (2.19)
умножений и
умн БПФ = 6.(N/2)log2N = 3.N.log2N (2.20)
сложений/вычитаний.
При выполнении обратного преобразования Фурье количество производимых операций будет таким же. Это утверждение следует из того, что ОБПФ можно вычислить следующим образом [2]:
, (2.21)
где символ * означает комплексно - сопряженное число, которое получается путем простого изменения знака мнимой части отсчета. Деление на N производится путем отбрасывания необходимого количества младших разрядов. Таким образом, для выполнения БПФ и ОБПФ потребуется произвести
умн БПФ ? = 2. Pумн БПФ (2.22)
умножений и
сл БПФ ? = 2. Pсл БПФ (2.23)
сложений/вычитаний.
При выполнении умножения отсчетов X(k) на отсчеты H(k) потребуется 4N операции умножения и 2N операции сложения/вычитания.
Итак, количество операций, необходимых для вычисления одной секции быстрой свертки, потребуется выполнить:
умн ? = Pумн БПФ ? + 4.N =4.N.log2N + 4.N = 4.N.(log2N + 1) (2.24)
умножений и
сл ? = Pсл БПФ ? + 2.N = 6.N.log2N + 2.N = 2.N.(3.log2N + 1) (2.25)
сложений/вычитаний с действительными числами.
Следует заметить, что количество перемножителей и сумматоров для БС фильтра будет равняться:
перемн ? = (4.N.log2N)/(N/2) + 4.N = 8.N.log2N + 4.N (2.26)
умножений и
Рсум ? = (6.N.log2N)/(N/2) + 2.N = 2.N.(3.log2N + 1) (2.27)
сумматоров. Такое количество можно объяснить тем, что при использовании алгоритма поточного БПФ количество базовых операций не будет соответствовать выражению (2.18), а будет в N/2 раз меньше.
Таким образом была получена оценка количества операций, необходимых для обработки БС-фильтром комплексной последовательности отсчетов. Однако полученный результат не отображает количество задействованных аппаратных ресурсов, которые будут использованы при построении рассматриваемого фильтра.
Как видно из рисунке 2.2, количество линий задержек для осуществления поточного БПФ и ОБПФ будет одинаковым. Количество затраченных ЛЗ на один тактовый интервал для БПФ и ОБПФ хорошо аппроксимируется выражением
Рлз ? = 4.(N -1). (2.28)
Учтем размерность задействованных ПЗУ, которая складывается из:
1)ПЗУ для хранения значений поворачивающих множителей объемом N для БПФ и объемом N для ОБПФ
2)ПЗУ для хранения значений отсчетов импульсной характеристики, над которыми выполнено преобразование Фурье, объемом N.
Таким образом, информационная емкость слов ПЗУ соответствующей разрядности составит
Рпзу ? = 3.N. (2.29)
Теперь, после оценки количества аппаратурных ресурсов, можно оценить время, за которое будет происходить обработка отсчета одним АУ:
ТАУ=2.ТСУММ+ТУМН=3.Тт . (2.30)
Время вычисления ТБС - время, через которое n-й отсчет появится на выходе БС-фильтра, будет определяться суммой задержек ЛЗ - ТЛЗ, арифметических устройств - ТАУ, умножителей - ТУМН и сумматоров/вычитателей - ТСУММ:
ТБС =2.ТЛЗ+2.log2N.ТАУ +ТУМН+ТСУММ =(N/2).Тт+2.(N -1)Тт+6(log2N).Тт +2.Тт (2.31)
Таким образом, были получены оценки количества операций, необходимых для обработки цифрового сигнала, количе