8 Сурет

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

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

3 к е с т е

Шынайықатар	000	001	010	011	100	101	110	111
Екілік-инверстік қатар	000 (0)	100 (4)	010 (2)	110 (6)	001 (1)	101 (5)	011 (3)	111 (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)

X₀(0)

X₀(1)

X₁(0)

X₁(1)

X₂(0)

X₂(1)

X₃(0)

X₃(1)

+

----

+

-

+

-

+

-

X₀(0)

X₀(1)

X₀(2)

X₀(3)

X₁(0)

X₁(1)

X₁(2)

X₁(3)

W⁰

W¹

W⁰

W¹

+

+-

-

-

+

+

-

-

X₀(0)

X₀(1)

X₀(2)

X₀(3)

X₀(4)

X₀(5)

X₀(6)

X₀(7)

W⁰

W¹

W²

W³

+

+-

+

+

-

-

-

-

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 к е с т е

	Есептеу қиындығының бағасы		Ұтыс бағасы
	ДФТ тура есептеуі	ФЖТ көмегімен есептеу
8	64	24	2,7
16	256	64	4,0
32	1024	160	6,4
64	4096	384	10,7
128	16384	896	18,3
256	65536	1024	32,0
512	262144	4096	56,9
1024	1048576	10240	102,4