Дәріс.Дискретті Фурье түрленуі

 

Дәріс мазмұны: спектралды анализ, тура және кері дискретті Фурье түрленуі (ДФТ), жылдам ДФТ-ның базалық операциясы, уақыт және жиілік бойынша сиректік алгоритмдері.

Дәріс мақсаты: тура және кері дискретті Фурье түрленуінің базада қолдануында Фурье-сараптама көмегімен спектр компонентінің бағалау әдісін және де уақытпен жиілік бойынша сиректікпен жылдам ДФТ алгоритмін үйрену, олардың есептеу мүмкіндігін бағалай алу.

Сандық өңдеудің тапсырмалар қатарында сигнал спектрінің параметрлерін бағалау қажет, яғни спектралды анализды орындау. Спектралды анализ тапсырмасы өзіндік мінезге ие бола алады, мысалы, сейсмологияда сейсмикалық оқиға типін анықтау үшін немесе геофизикада пайда болу орнын іздеу үшін, қосымша мінезі, мысалы, суреттік және тілдік компрессия жүйелерінде, фильтрация және бөгеуіл компенсациясында.

Шығыс мәліметтерін өңдеу үшін сигналының есептемесі болып табылады, яғни уақыттық функция ретінде соңғы дискретті (сандық) тізбек. Бұл тізбектің жиіліктік құрамын зерттеу үшін Фурье - сараптамасын қолдана отырып оны түрлендіру керек. Аналитикалық тұрғыдан қарасақ, Фурье-сараптамасы уақыттық аумақ кезіндегі сигнал және жиіліктік аумақ кезіндегі спектр арасындағы байланысты орнатуға мүмкіндік береді. Және де дискретті Фурье түрленуі (ДФТ) негізінде спектр компоненттерін есептеп шығарады.

ДФТ – бұл өзара бірмағыналы түрлендіргіш жұбы, жинақы түрде былай көрінеді:

1) тура , (5.1)

2) кері (5.2)

мұндағы - шығыс тізбегінің ұзындығы;

- жиілік бойынша есептемелер саны;

-уақыт бойынша есептемелер саны;

-бұрылғыш көбейткіш(салмақты, периодты функция), бұлай аталуының себебі, экспонент аргументікомплексті z -жазықтығының бірлік шеңберіндегі бұрылыс бұрышын көрсетеді.

бұрылғыш көбейткіштің периодтылық қасиетін қолдана отырып ДФТ есептеуіші үшін арифметикалық операциялардың санын азайтуға болады. Жылдам ДФТ үшін толық алгоритмдер жинағы бар: 2 негізімен, 4 негізімен, Виноградова және тағы басқа.

Ең көп таралымға ие болған алгоритм 2 негізімен, жүзеге асыру үшін N шығыс тізбегінің ұзындығы 2-ге қысқы болу керек, яғни ,мұндағы - бүтін оң сан.

Бірінші алгоритм 1965 жылы АҚШ-та жарияланды және негізін салушы Кули-Тьюки есімімен аталды. Бұл алгоритмнің екі нұсқасы бар:

1) уақыт бойынша сиректілігімен, жүзеге асыру кезінде шығыс тізбекті қайта қою (сиректік) есептемесін қажет етеді;

2) жиілік бойынша сиректілігімен, жүзеге асыру кезінде шығыс тізбекті қайта қою (сиректік) есептемесін қажет етеді.

Бірінші нұсқа мағынасы ол N-нүктелік ДФТ-ны этаптарға бөледі, оның саны келесідей анықталады

Бірінші этапта N/ 22 нүктелік ДФТ анықталады, біреуінде тақ санды есептеме, екіншісінде – жұп санды есептеме болады. Онда, (5.1) өрнегінде көрсетілген қосындыны екіге бөлуге болады

, (5.3)

 

мұндағы ;

X( 2 n) и X( 2 n+ 1 ) – N/ 2 – сәйкесінше жұп және тақ есептемелердің нүктелік тізбегі.

болғандықтан

өрнегін аламыз. (5.4)

Егер периодты нүктесімен периодтыекенін ескерсек, онды

, (5.5)

мұндағы .

Онда шығыс тізбекті ДФТ екі - нүктелік ДФТ-ға түрленеді:

(5.6)

 

Көрсетілген қатынас «көбелек» деп аталатын Фурье жылдам түрлендіргішінің (ФЖТ) базалық операциясын бейнелейді. Графикалық түрде бұл операцияны 8 суретте көрсетілген бағытталған түрдегі граф түрінде көруге болады.

 

 

8 сурет

 

8 суретте көрсетілген бағытталған граф – бұл 2 нүктелік ДФТ үшін алгоритм құрылымы, бұл кезде . Екінші этапта N/4 4 нүктелік ДФТ анықталады, үшінші этапта – N/8 8нүктелік ДФТжәне тағы сол сияқты.

Бірінші этап алдында N -нүктелік тізбек шынайытүрде емес, бастапқы шарт алгоритмін қамтамасыз ететін екілік-инверстік қатарда берілу керек. 3 кестеде N =8 үшін екілік-инверстік қатар көрсетілген.

3 к е с т е

Шынайықатар
Екілік-инверстік қатар	(0)	(4)	(2)	(6)	(1)	(5)	(3)	(7)

 

10 суретте 8-нүктелік (N = 8) ЖФТ реттелген сұлбасы көрсетілген.

 

Екілік- біріншіекіншіүшінші

инверстікэтаптан этаптан этаптан

Бастапқыкейінкейінкейін

X(0)

X(1)

X(2)

X(3)

X94)

X(5)

X(6)

X(7)

X(0)

X(4)

X(2)

X(6)

X(1)

X(5)

X(3)

X(7)

X0(0)

X0(1)

X1(0)

X1(1)

X2(0)

X2(1)

X3(0)

X3(1)

+

----

+

-

+

-

+

-

X0(0)

X0(1)

X0(2)

X0(3)

X1(0)

X1(1)

X1(2)

X1(3)

W0

W1

W0

W1

+

+-

-

-

+

+

-

-

X0(0)

X0(1)

X0(2)

X0(3)

X0(4)

X0(5)

X0(6)

X0(7)

W0

W1

W2

W3

+

+-

+

+

-

-

-

-

 

 

10 сурет

2 суретте көрсетілгендей 8-нүктелік ДФЖТ-ны реттеу үшін болғандықтан ДФТ-ны үш этапқа бөлу керек, бірінші этапта кезіндегі төрт көбелек болады, екінші этапта және кезіндегі төрт көбелек болады, үшінші этапта , , , кезіндегі тағы да төрт көбелек болады. Алгоритм шығысында есептемесі шынайы қатарға сәйкестенетін 8-нүктелік ДФТ-ны аламыз.

Уақыт бойынша сиректік алгоритмінде есептеуді орын ауыстыру әдісі бойынша орындауға болады. Кіріс тізбегі N ұяшықтағы массивте орналасады. Есептеуден кейін бірінші баспалдақта кіріс сигналының есептемелері кажет емес болады және көрсетілген ұяшықта «көбелектің» шығыс мәліметтері жазылған болуы мүмкін. Келесі баспалдақта бастапқы массивке «көбелектің» қайтаданесептелген шығыс мәндері жазылады және тағы сол сияқты. Есептеу соңында бастапқы массивте номерлеріне сәйкес шынайы қатармен орналасқан X(k) спектр компоненті мәні болады, яғни k = 0,1,2,…, N-1 кезіндегі ДФТ _N мәні.

Жиілік бойынша сиректік ФЖТ алгоритм жүзеге асыру этапы бойынша орындалады, бірақ кері бағытта болады, яғни екі есе үлкен өлшем жағында (… 8 → 4 →2). Бұл кезде бірінші этап алдында N-нүктелік тізбек есептемелері нөмердің шынайы қатарын сақтап (n = 0,1,…,N-1), қайта қойылмайды. Бірақ та, алгоритм шығысында ДФТ алынады, есептемелері екілік нөмермен екілік-инверстті қатарға бағынған.

Тәжірибеде жиілік бойынша сиректік ФЖТ алгоритмі уақыт бойынша сиректік алгоритміне қарағанда сирек қолданылады, себебі уақыт бойынша сиректік алгоритмі шығысында ФЖТ есептемесін анықтаудашынайы қатарын қамтамасыз етеді.

ФЖТ алгоритмінің есептеу қиындығының тәртібі сияқты бағаланады, сол кезде ДФТ-ның тура есептеуі сияқты ол тең болады. 4 кестеде N бастапқы тізбектің ұзындығына байланысты есептеу көлемінде алынған ұтыс бағасы көрсетілген.

4 к е с т е

	Есептеу қиындығының бағасы	Ұтыс бағасы
ДФТ тура есептеуі	ФЖТ көмегімен есептеу
			2,7
			4,0
			6,4
			10,7
			18,3
			32,0
			56,9
			102,4