Вычислить наиболее экономичным методом коэффициенты Фурье дискретной последовательности: Х={1, 2, 3, 4, 5, 6, 7, 8, 9}.
Решение:
Последовательность коэффициентов, образующих дискретное преобразование Фурье (ДПФ) рассматриваемой последовательности = = определяется по формуле ([1] 3.11):
(1)
где k – номер функции, k = 0, 1, …, N–1; n – номер отсчета, n = 0, 1, …, N–1; N количество отсчетов; – поворачивающий множитель, который представляет собой вектор на комплексной плоскости, . (2) Последовательность представляет собой отсчеты сигнала, а последовательность – дискретный спектр. Выражение (1) называется прямым преобразованием Фурье. Поскольку количество отсчетов заданной дискретной последовательности является составным числом N = 9, то необходимо использовать алгоритм быстрого преобразования Фурье с произвольным основанием (БПФ-алгоритм Кули-Тьюки). В нашей задаче N = N1 ∙ N2 = 3∙ 3 = 9. Тогда в выражении (1) для преобразования Фурье преобразуем индексы n и k следующим образом ([1] 3.33 и 3.34): n = n1+N1n2, n1 = 0,1,…,N1−1, n2 = 0,1,…,N2−1, (3)
n = n1+3n2, n1 = 0,1,2, n2 = 0,1,2;
k = k2+N2k1, k1 = 0,1,…,N1−1, k2 = 0,1,…,N2−1, (4)
k = k2+3k1, k1 = 0,1,2, k2 = 0,1,2.
Подставив (3) и (4) в (1), получим: (5)
При этом в выражении (5) учтено, что в силу периодичности дискретных экспоненциальных функций. Отобразим данные в матрицу 3×3. Для этого определим двумерные переменные, задавая их равенствами:
s(n1,n2) = s(n1+N1n2) = s(n1+3n2) (6)
f(k1,k2) = f(k2+N2k1) = f(k2+3k1) (7)
При этом векторы входных и выходных данных преобразуются в двумерные массивы. Переиндексация на входе производится в соответствии с формулой (6). Аналогично на выходе по формуле (7) получаем, что f(k1,k2) соответствует f(k2+3k1). Обозначим: (8) (9) С учетом этого можно записать
Из этого выражения следует, что N1 N2 – точечное ДПФ можно вычислить в три этапа. Сначала для нашей задачи осуществляется 3-х кратный вызов 3-точечного преобразования:
Затем величины , которые представляют собой матрицу размером 3×3, умножаются на поворачивающие множители . Конечный результат получается вычислением N1 N2 –точечных преобразований ([1] 3.35), то есть осуществляется 3-кратный вызов 3-точечного преобразования:
После чего осуществляется отображение матрицы 3×3 содержащей элементы в 9-точечный вектор .
Таким образом, получим коэффициенты Фурье для заданной дискретной последовательности:
;
Задача № 55
При каком виде свертки (апериодической, периодической, диадной) может быть применена теорема о корреляции? Дать аргументированный ответ.
Решение:
Теорема о корреляции: взаимная корреляция двух сигналов конечного периода в непрерывной временной области определяется формулой:
(1)
Дискретной циклической корреляционной функцией двух последовательностей {s(n)} и {u(n)} называется последовательность {R ®}, элементы которой определяются по формуле: (2) В матричном виде:
. Спектр корреляционной функции является произведением коэффициентов ДПФ одной последовательности {s(n)} на комплексно-сопряженные коэффициенты другой последовательности {u(n)}, то есть . (3) Следует заметить, что в общем случае , и поэтому к выбору комплексно-сопряженного спектра надо подходить осмотрительно. ОДПФ от дает значения корреляционной функции. Циклическую корреляционную функцию можно рассматривать как циклическую свертку двух сигналов, один из которых обращен во времени (все отсчеты, за исключением нулевого, записаны в обратном порядке). Понятие даидного сдвига позволяет обобщить понятия свертки и корреляционной функции. Так как суммирование и вычитание по модулю два совпадают, то диадная свертка совпадает с диадной корреляцией и определяется выражением (4) Здесь номера отсчетов представляются в двоичной системе счисления, арифметические операции над числами выполняются посимвольно по модулю два, а длина сворачиваемых последовательностей равна N = 2v, v − целое число. При этом сдвиг функции фактически заключается в перестановке отсчетов. Таким образом, коэффициентами свертки являются суммы произведений , полученные при различных перестановках функции Теорема о свертке утверждает, что спектр свертки равен произведению спектров сворачиваемых последовательностей: (5) Это позволяет для вычисления диадной свертки и корреляционной функции использовать преобразование Адамара: (6) где B = HS − прямое преобразование Уолша-Адамара в матричной форме; N − порядок матрицы Адамара; Н − матрица Адамара; Н-1 − матрица, обратная матрице Н; , − векторы-столбцы отсчетов сигнала и спектральных коэффициентов. Матрицей Адамара называется ортогональная квадратная матрица порядка N, элементами которой являются действительные числа ±1. Матрица Адамара порядка N обозначается НN. Простейшей матрицей Адамара является матрица второго порядка:
Для построения матриц порядка N=2l, l=2, 3, … (матрица типа Сильвестра) используется следующая теорема: если НN − матрица Адамара порядка N, то матрица
является матрицей Адамара порядка 2N. Основным свойством преобразования Уолша-Адамара является инвариантность к диадному сдвигу. Сущность диадного сдвига заключается в перестановке отсчетов исходной функции. В частности на место отсчета с номером n ставится отсчет с номером .
Литература
1. Лосев В. В. Микропроцессорные устройства обработки информации. Алгоритмы цифровой обработки: Учебное пособие для вузов. – Мн.: Высшая школа, 1990. 2. Лосев В. В. Учебное пособие по спецкурсу «Цифровые методы формирования импульсных сигналов». – Мн.: Ротапринт МРТИ, 1979.
