Преобразование Фурье в цифровой информации


Быстрое преобразование Фурье



Download 1,57 Mb.
bet3/3
Sana14.07.2022
Hajmi1,57 Mb.
#798560
TuriСамостоятельная работа
1   2   3
Bog'liq
Сам.работа

Быстрое преобразование Фурье
Формула преобразования Фурье может быть разделена на:

который может быть представлен в виде графика:


Рис.11. Разложение ДПФ на четные и нечетные отсчеты.

Обратите внимание, что элементы:



можно вычислить таким же образом: элементы x (0), x (4), x (1) и x (5) являются в своих диаграммах четными индексами, тогда как x (2), x (6), x (3) и x (7) являются нечетными. Объединив их в упорядоченные пары, приведенные выше графики можно перерисовать:

Рис.12. Быстрое преобразование Фурье (RADIX-2) для сигнала N = 8.

Обозначая определение DFT для сигнала N = 8, мы должны были выполнить 64 операции умножения, но из-за вышеприведенного наблюдения мы сделали их только 12. Чем больше количество отсчетов в сигнале, тем больше преимущество в количестве вычислений с использованием алгоритма БПФ, так как объем вычислений для N-кратного сигнала может быть определен как:

N/2*log2(N)
N/2*log2(N)
Базовый элемент такого расчета называется "бабочка":




Быстрое преобразование Фурье на практике
Правильное количество выборок
Самый простой способ обработки сигнала имеет количество выборок, которое является степенью 2, просто заполните недостающие выборки нулями. В зависимости от структуры сигнала дополнения могут быть сделаны как правосторонними, так и левосторонними или обеими сторонами.

Рис.13. Дополненный сигнал из рис.2


Сортировка выборок
Для соединения последовательных отсчетов сигналов в соответствующих парах используются алгоритмы предварительной сортировки. Однако алгоритм БПФ может быть выполнен на несортированных выборках, а операция сортировки (таким же образом) может быть выполнена на выборках спектра.

В аппаратных анализаторах спектра и низкоуровневых языках программирования сортировка выборок намного проще, поскольку операция основана на простой инверсии битов в двоичном представлении индексной выборки.

В нашем сигнале N = 8 мы можем заметить, что:

public >returns<
Sorted signal samples///>
name="x" param< Original input signal samples
///>
summary summary<
// Double[] FFTDataSort(Double[] x)
{
int N = x.Length; // длина сигнала

if (Math.Log(N, 2) % 1 != 0)


{
бросить новое исключение ("Количество выборок в сигнале должно быть мощностью 2");
}

Double[] y = new Double[N]; // output (sorted) vector

int BitsCount = (int)Math.Log(N, 2); // maximum number of bits in index binary representation
for (int n = 0; n < N; n++)
{
string bin = Преобразовать.toString(n, 2).PadLeft(BitsCount, '0'); // двоичное представление индекса
Отражение StringBuilder = new StringBuilder(new string('0', bin.Длина));

for (int i = 0; i < bin.Длина; i++)


{
reflection[bin.Length - i - 1] = bin[i]; // двоичное отражение
}

int number = Преобразовать.ToInt32 (отражение.toString(),2); // новый индекс

y[число] = x[n];

}

возврат y;



}
Однако эта операция может быть выполнена намного быстрее, без необходимости преобразования номера индекса в двоичную форму:

public >returns<


Sorted signal samples
///>
name="x" param< Original input signal samples
///>
summary summary<
// Double[] FFTDataSort2(Double[] x)
{
int N = x.Length; // длина сигнала

if (Math.Log(N, 2) % 1 != 0)


{
бросить новое исключение ("Количество выборок в сигнале должно быть мощностью 2");
}

int m = 1; // исходный индекс


для (int n = 0; n < N - 1; n++) // n - новый индекс
{
если (n < m)
{
Double T = x[m-1];
x[m-1] = x[n];
x[n] = T;
}

int s = N / 2; // оператор сдвига

while (s < m)
{
m = m - s;
s = s / 2;
}

m = m + s;


}

возврат x;



}

Download 1,57 Mb.

Do'stlaringiz bilan baham:
1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish