дНЙСЛЕМР БГЪР ХГ ЙЩЬЮ ОНХЯЙНБНИ ЛЮЬХМШ. юДПЕЯ НПХЦХМЮКЭМНЦН ДНЙСЛЕМРЮ : http://fpga.parallel.ru/fft/
дЮРЮ ХГЛЕМЕМХЪ: Tue Aug 16 14:34:34 2011
дЮРЮ ХМДЕЙЯХПНБЮМХЪ: Mon Oct 1 19:52:10 2012
йНДХПНБЙЮ: koi8-r

нЯМНБМЮЪ ЯУЕЛЮ АШЯРПНЦН ОПЕНАПЮГНБЮМХЪ тСПЭЕ

йнлоэчрепш

нЯМНБМЮЪ ЯУЕЛЮ АШЯРПНЦН ОПЕНАПЮГНБЮМХЪ тСПЭЕ

бБНДМШЕ ГЮЛЕВЮМХЪ
оНЯРЮМНБЙЮ ГЮДЮВХ

яРПСЙРСПЮ БШВХЯКЕМХИ ЙКЮЯЯХВЕЯЙНЦН дот

яКСВЮИ ЯНЯРЮБМНЦН N
яБЕДЕМХЕ ОПЕНАПЮГНБЮМХЪ тСПЭЕ Й ОНЯКЕДНБЮРЕКЭМНЯРХ ОПЕНАПЮГНБЮМХИ ЛЕМЭЬЕИ ПЮГЛЕПМНЯРХ

пЮГЛЕПМНЯРЭ - ЯРЕОЕМЭ ДБНИЙХ
пЮГЛЕПМНЯРЭ - В╦РМЮЪ ЯРЕОЕМЭ ДБНИЙХ
пЮГЛЕПМНЯРХ, МЕ ЪБКЪЧЫХЕЯЪ ЯРЕОЕМЪЛХ ДБНИЙХ

нЬХАЙХ НЙПСЦКЕМХЪ Х ОПЕНАПЮГНБЮМХЕ тСПЭЕ
гЮЙКЧВЕМХЕ

бБНДМШЕ ГЮЛЕВЮМХЪ

яНЯРЮБМНИ ВЮЯРЭЧ ПЕЬЕМХЪ ЛМНЦХУ ОПХЙКЮДМШУ ГЮДЮВ ЪБКЪЕРЯЪ НЯСЫЕЯРБКЕМХЕ ОПЪЛНЦН Х НАПЮРМНЦН ДХЯЙПЕРМШУ ОПЕНАПЮГНБЮМХИ тСПЭЕ. щРЮ ОНДГЮДЮВЮ БЯРПЕВЮЕРЯЪ Б РЮЙХУ ОПХКНФЕМХЪУ, ЙЮЙ НАПЮАНРЙЮ ЯХЦМЮКНБ, ПЕЬЕМХЕ ЩККХОРХВЕЯЙХУ ГЮДЮВ ЛЮРЕЛЮРХВЕЯЙНИ ТХГХЙХ, ПЕЬЕМХЕ ЯХЯРЕЛ КХМЕИМШУ ЮКЦЕАПЮХВЕЯЙХУ СПЮБМЕМХИ ЯОЕЖХЮКЭМНЦН БХДЮ Х Р.Д. гДЕЯЭ ЛШ ПЮЯЯЛНРПХЛ, ВРН ЩРН ГЮ ОПЕНАПЮГНБЮМХЕ Х ЙЮЙ ЕЦН ЛНФМН БШОНКМХРЭ АШЯРПЕЕ.

оНЯРЮМНБЙЮ ГЮДЮВХ

оСЯРЭ f = (f₀, ... ,f_N-1)^T - ХЯУНДМШИ БЕЙРНП, ЙНРНПШИ МСФМН СЛМНФХРЭ МЮ ЛЮРПХЖС тСПЭЕ F c ЩКЕЛЕМРЮЛХ

F_qj = exp(-2πiqj/N) ¹

ДКЪ ОНКСВЕМХЪ БЕЙРНПЮ a= (a₀, ..., a_N-1)^T ОН ТНПЛСКЕ a = Ff. рНЦДЮ ДКЪ ЩКЕЛЕМРЮ ХЯЙНЛНЦН БЕЙРНПЮ СЛМНФЕМХЕ ДЮЯР ТНПЛСКС:

a_q=(Σf_j exp(-2πi q j / N)) (ЯСЛЛЮ ОН j = 0, ..., N-1)

йЮЙ ХГБЕЯРМН, Б НАЫЕЛ ЯКСВЮЕ СЛМНФЕМХЕ ЛЮРПХЖШ МЮЛ БЕЙРНП РПЕАСЕР O(N²) ЮПХТЛЕРХВЕЯЙХУ НОЕПЮЖХИ. яКЕДСЕР ПЮЯЯЛНРПЕРЭ БНОПНЯ Н ЯНЙПЮЫЕМХХ ЩРНЦН ВХЯКЮ.

¹бННАЫЕ ЦНБНПЪ, Б ТНПЛСКЮУ дот ДКЪ ТХГХВЕЯЙНИ ЙНППЕЙРМНЯРХ ВЮЯРН ОПХЯСРЯРБСЕР Х МНПЛХПНБНВМШИ ЛМНФХРЕКЭ, ЙНРНПНЦН С МЮЯ МЕР. гДЕЯЭ ЛШ АСДЕЛ ХЯОНКЭГНБЮРЭ РЕПЛХМНКНЦХЧ, ОПХМЪРСЧ Б § 17 ЯОПЮБНВМХЙЮ б.б.бНЕБНДХМЮ Х ч.ю.йСГМЕЖНБЮ "лЮРПХЖШ Х БШВХЯКЕМХЪ" (л., мЮСЙЮ, 1984Ц.). рЕНПЕРХВЕЯЙХЕ НЖЕМЙХ, ОПХБНДХЛШЕ МХФЕ, БГЪРШ РНФЕ НРРСДЮ.

яРПСЙРСПЮ БШВХЯКЕМХИ ЙКЮЯЯХВЕЯЙНЦН дот

пЮЯЯЛНРПХЛ ЯРПСЙРСПС БШВХЯКЕМХИ ЙКЮЯЯХВЕЯЙНЦН дот, ОПЕДОНКНФХБ, ВРН ЯСЛЛХПНБЮМХЕ ОПНХЯУНДХР ОН ОНПЪДЙС НР ЛЮКШУ ГМЮВЕМХИ ХМДЕЙЯНБ Й АНКЭЬХЛ. йЮГЮКНЯЭ АШ, ВРН ЯКНФМНЦН Б АЮМЮКЭМНЛ СЛМНФЕМХХ ЛЮРПХЖШ МЮ БЕЙРНП? нДМЮЙН, Б НРКХВХЕ НР ЯРЮМДЮПРМНЦН СЛМНФЕМХЪ, ЦДЕ ЙЮФДШИ ЩКЕЛЕМР ЛЮРПХЖШ ХЯОНКЭГСЕРЯЪ РНКЭЙН НДХМ ПЮГ, Б дот ЛЮРПХЖЮ - ЯОЕЖХЮКЭМНЦН БХДЮ. щРН ОПХБНДХР Й РНЛС, ВРН НДМХ Х РЕ ФЕ ЩКЕЛЕМРШ ЛЮРПХЖШ ХЯОНКЭГСЧРЯЪ Б ЯНБЕПЬЕММН ПЮГМШУ ЛЕЯРЮУ ЯУЕЛШ БШВХЯКЕМХИ. мЮ ПХЯСМЙЕ ОПЕДЯРЮБКЕМЮ ЯРПСЙРСПЮ дот Я N=6.

в╦ПМШЛХ КХМХЪЛХ НАНГМЮВЕМШ ЯНАЯРБЕММН БЕРБХ БШВХЯКЕМХИ, ОПХ ЩРНЛ ОЕПЕДЮВХ НЯСЫЕЯРБКЪЧРЯЪ ЯКЕБЮ МЮОПЮБН, Б ЙПЮИМЕЛ ЯОПЮБЮ ЯРНКАЖЕ ПЕГСКЭРЮРНЛ АСДЕР ЯННРБЕРЯРБСЧЫХИ ЩКЕЛЕМР БШВХЯКЪЕЛНЦН БЕЙРНПЮ. б НДМНЛ ЯРНКАЖЕ ПЮЯОНКНФЕМШ РЕ НОЕПЮЖХХ, ЙНРНПШЕ ХЯОНКЭГСЧР Б ЙЮВЕЯРБЕ НДМНЦН ХГ ДЮММШУ НДХМ Х РНР ФЕ ЩКЕЛЕМР ХЯУНДМНЦН БЕЙРНПЮ. ю БНР ЖБЕР БЕПЬХМШ (БЯЕ НМХ ЯННРБЕРЯРБСЧР НОЕПЮЖХХ a+bc) ЯННРБЕРЯРБСЕР РНЛС, ЙЮЙНИ ХГ ЩКЕЛЕМРНБ ЛЮРПХЖШ тСПЭЕ СЛМНФЮЕРЯЪ МЮ ЩКЕЛЕМР ХЯУНДМНЦН БЕЙРНПЮ. яЕПШЛ ЖБЕРНЛ НЙПЮЬЕМШ БЕПЬХМШ, ЦДЕ ХГ ЛЮРПХЖШ тСПЭЕ Б ЙЮВЕЯРБЕ ЛМНФХРЕКЪ АЕП╦РЯЪ МСКЕБЮЪ ЯРЕОЕМЭ ЙНЛОКЕЙЯМНЦН ВХЯКЮ, Р.Е. ОПНЯРН ЕДХМХЖЮ (Х ЦДЕ, ЯКЕДНБЮРЕКЭМН, СЛМНФЕМХЕ ЛНФМН ОПНОСЯРХРЭ). йЮЙ БХДХЛ, Е╦ ЙЮЙ ПЮГ АНКЭЬЕ БЯЕЦН Б ЯРПСЙРСПЕ БШВХЯКЕМХИ. дЮКЕЕ ЯРЕОЕМХ НДМНЦН Х РНЦН ФЕ ЙНЛОКЕЙЯМНЦН ЛМНФХРЕКЪ ПЮЯРСР НР 1 ДН 5 Б БЕПЬХМЮУ ЯННРБЕРЯРБЕММН ГЕК╦МНЦН, ЦНКСАНЦН, ЯХМЕЦН (ЩКЕЛЕМР РЮЛ СЛМНФЮЕРЯЪ МЮ -1 Х ОНРНЛС ЛНФМН, ЙЮЙ Х Б ЯЕПШУ БЕПЬХМЮУ, НРЙЮГЮРЭЯЪ НР СЛМНФЕМХЪ, ГЮЛЕМХБ ЯКНФЕМХЕ БШВХРЮМХЕЛ), ТХНКЕРНБНЦН Х Ф╦КРНЦН ЖБЕРНБ. йЮЙ БХДМН, ЯРПСЙРСПЮ ХЯОНКЭГНБЮМХЪ ЩРХУ ЯРЕОЕМЕИ ДНБНКЭМН "УЮНРХВМЮ", УНРЪ МЮ ЯЮЛНЛ ДЕКЕ Б ЩРНЛ "УЮНЯЕ" ЕЯРЭ ЯРПНЦН НОПЕДЕК╦ММШИ ОНПЪДНЙ.

б ЯКСВЮЕ ОПНЯРНЦН N ЯРПСЙРСПЮ АСДЕР НРКХВЮРЭЯЪ РЕЛ, ВРН "ЯЕПШУ" БЕПЬХМ, ЙПНЛЕ ЙЮЙ МЮ КЕБНИ Х БЕПУМЕИ ЦПЮМХЖЮУ ЯННРБЕРЯРБСЧЫЕЦН ПХЯСМЙЮ, АНКЭЬЕ МЕ АСДЕР БННАЫЕ.

б ЯКСВЮЕ ФЕ N=2 С МЮЯ АСДСР РНКЭЙН 3 ЯКНФЕМХЪ Х НДМН БШВХРЮМХЕ, РЮЙ ВРН ХЯОНКЭГНБЮМХЕ ДБНИЙХ Б ЙЮВЕЯРБЕ АЮГНБНЦН ЯНЛМНФХРЕКЪ аот МЕЯ╦Р МЕЯНЛМЕММШЕ БШЦНДШ.

яРПСЙРСПЮ ЙКЮЯЯХВЕЯЙНЦН дот Б ЖЕКНЛ МЮЯРНКЭЙН ОПНЯРЮ, ВРН Е╦ ЛНФМН ГЮОХЯЮРЭ Я ОНЛНЫЭЧ РЮЙНИ ОПНЯРНИ ТНПРПЮМ-ОНДОПНЦПЮЛЛШ:


      subroutine ft(f,a,w,N)
Я
c ОЮПЮЛЕРПШ БШАПЮМШ Я РЕЛХ ФЕ ХДЕМРХТХЙЮРНПЮЛХ, ВРН ХЯОНКЭГСЧРЯЪ Б ОНЯРЮМНБЙЕ ГЮДЮВХ
c w - ЛЮЯЯХБ ЛМНФХРЕКЕИ (МСКЕБНИ МЕ УПЮМХРЯЪ, РЮЙ ЙЮЙ НМ ПЮБЕМ 1)
Я
      complex f(0:N-1),a(0:N-1),w(N-1)
      DO 10  i = 0, N-1
10       a (i) = f (0)
c
c ХМХЖХЮКХГЮЖХЪ ЯСЛЛ
c
      DO 20 j = 1, N-1
20       a (0) = a (0) + f (j)
c
c БШВХЯКЕМХЕ МСКЕБНЦН ЩКЕЛЕМРЮ ХЯОНКЭГСЕР Б ЙЮВЕЯРБЕ ЛМНФХРЕКЕИ РНКЭЙН 1
Я
      DO 30 i = 1, N-1
	DO 30 j = 1, N-1
	 jj = MOD (i*j, N)
c
c БШВХЯКЕМХЕ МНЛЕПЮ ЙНЛОКЕЙЯМНЦН ЛМНФХРЕКЪ
c
         if (jj .eq. 0) then
            a (i) = a (i) + f (j)
c
c СЛМНФЮРЭ МЮ 1 МЕ МСФМН
c
         else if (2*jj .eq. N) then
             a (i) = a (i) - f (j)
c
c МЮ -1 СЛМНФЮРЭ РНФЕ МЕ МСФМН
c
         else
            a (i) = a(i) + f (j) * w (jj)
         end if
30    CONTINUE
      RETURN
      END

(ОПНЦПЮЛЛЮ ГЮОХЯЮМЮ Б МНРЮЖХХ тНПРПЮМЮ 77).

яКСВЮИ ЯНЯРЮБМНЦН N

пЮЯЯЛНРПХЛ ЯКСВЮИ N = p₁ p₂, ОПХВ╦Л ЯНЛМНФХРЕКХ МЕ ПЮБМШ 1. рНЦДЮ, ОПЕДЯРЮБХЛ ХМДЕЙЯШ ЩКЕЛЕМРНБ БЕЙРНПНБ Х ЛЮРПХЖШ q, j Б БХДЕ

q = q₁ + p₁ q₂, j = j₂ + p₂j₁
(0 ≤ j₁, q₁ < p₁, 0 ≤ j₂, q₂ < p₂)

Х ОНДЯРЮБХЛ ХУ Б ХЯУНДМСЧ ТНПЛСКС ДКЪ ЩКЕЛЕМРЮ ХЯЙНЛНЦН БЕЙРНПЮ. рНЦДЮ ОНЯКЕ МЕЯКНФМШУ ЮПХТЛЕРХВЕЯЙХУ ОПЕНАПЮГНБЮМХИ, СВХРШБЮЪ РН, ВРН

(q₁ + p₁ q₂) (j₂ + p₂j₁) / p₁p₂ = q₂ j₁ + j₁q₁ / p₁ + q j₂ / N

Х РН, ВРН ЛМХЛЮЪ ЩЙЯОНМЕМРЮ ОЕПХНДХВМЮ Я ОЕПХНДНЛ 2π, ОНКСВХЛ, ВРН

a_q= a (q₁, q₂) = (Σ b (q₁, j₂) exp(-2πi q j₂/ N)) (ЯСЛЛЮ ОН j₂ = 0, ..., p₂-1)

ЦДЕ

b(q₁, j₂) = (Σf_j₂ + p₂j₁ exp(-2πi q₁ j₁ / p₁)) (ЯСЛЛЮ ОН j₁ = 0, ..., p₁-1)

оПХ БШВХЯКЕМХХ ОН ОПЕДЯРЮБКЕММНЛС ЮКЦНПХРЛС РПЕАСЕРЯЪ БЯЕЦН

O (p₁² p₂) + O (p₂² p₁)

ЮПХТЛЕРХВЕЯЙХУ НОЕПЮЖХИ. б ЯКСВЮЕ, ЙНЦДЮ ЯНЛМНФХРЕКХ ПЮБМШ ДПСЦ ДПСЦС, НАЫЕЕ ЙНКХВЕЯРБН НОЕПЮЖХИ ЯНЯРЮБХР

O(N^3/2).

нОХЯЮММШИ ЮКЦНПХРЛ Х МНЯХР МЮГБЮМХЕ "аШЯРПНЕ ОПЕНАПЮГНБЮМХЕ тСПЭЕ".

яБЕДЕМХЕ ОПЕНАПЮГНБЮМХЪ тСПЭЕ Й ОНЯКЕДНБЮРЕКЭМНЯРХ ОПЕНАПЮГНБЮМХИ ЛЕМЭЬЕИ ПЮГЛЕПМНЯРХ

оПХБЕД╦ММШЕ БШЬЕ ТНПЛСКШ ОНЙЮГШБЮЧР ХМРЕПЕЯМСЧ БЕЫЭ. нЙЮГШБЮЕРЯЪ, ЕЯКХ ГЮОХЯЮРЭ ХЯУНДМШИ БЕЙРНП f ОН ЯРНКАЖЮЛ ОПЪЛНСЦНКЭМНИ РЮАКХЖШ ПЮГЛЕПЮ p₂ МЮ p₁, РН ЕЦН ОПЕНАПЮГНБЮМХЕ тСПЭЕ Б БЕЙРНП a ЛНФЕР АШРЭ БШОНКМЕМН Б ЯКЕДСЧЫХЕ РПХ ДЕИЯРБХЪ (МЮ ПХЯСМЙЮУ-ОПХЛЕПЮУ ЛШ АСДЕЛ ЯВХРЮРЭ, ВРН ХЯУНДМЮЪ ПЮГЛЕПМНЯРЭ ПЮБМЮ 15):

бШВХЯКЕМХЕ ОПЕНАПЮГНБЮМХИ тСПЭЕ ОНПЪДЙЮ p₁БЯЕУ ЯРПНЙ РЮАКХЖШ (ЙПЮЯМШЛ МЮ ПХЯСМЙЕ ОНЙЮГЮМШ ЦПСООШ ЩКЕЛЕМРНБ ЛЮЯЯХБЮ, МЮД ЙНРНПШЛХ БШОНКМЪЧРЯЪ дот ПЮГЛЕПМНЯРХ p₁=3).
сЛМНФЕМХЕ ЩКЕЛЕМРНБ ОНКСВЕММНИ РЮАКХЖШ МЮ Р.М. ОНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ (ЯЕПШЛ МЮ ПХЯСМЙЕ ОНЙЮГЮМШ ЩКЕЛЕМРШ ЛЮЯЯХБЮ, ЙНРНПШЕ МЕ МСФМН СЛМНФЮРЭ, ПЮГМШЛХ ЖБЕРЮЛХ - СЛМНФЮЕЛШЕ МЮ ПЮГМШЕ ОНБНПНРМШЕ ЛМНФХРЕКХ; ЙЮЙ ЛШ БХДХЛ, ВЮЯРЭ ОНБНПЮВХБЮЧЫХУ ЛМНФХРЕКЕИ ОНБРНПЪЕРЯЪ).
бШВХЯКЕМХЕ ОПЕНАПЮГНБЮМХИ тСПЭЕ ОНПЪДЙЮ p₂ БЯЕУ ЯРНКАЖНБ РЮАКХЖШ (ЙПЮЯМШЛ МЮ ПХЯСМЙЕ ОНЙЮГЮМШ ЦПСООШ ЩКЕЛЕМРНБ ЛЮЯЯХБЮ, МЮД ЙНРНПШЛХ БШОНКМЪЧРЯЪ дот ПЮГЛЕПМНЯРХ p₂=5).

хЯЙНЛШИ БЕЙРНП a АСДЕР Б ОНКСВХБЬЕИЯЪ РЮАКХЖЕ ГЮОХЯЮМ ОН ЯРПНЙЮЛ. еЯКХ ФЕ ЛШ УНРХЛ, ВРНАШ НМ РНФЕ АШК ГЮОХЯЮМ ОН ЯРНКАЖЮЛ, ЙЮЙ Х ХЯУНДМШИ, РН МЮЛ МЮДН АСДЕР ДНАЮБХРЭ ВЕРБ╦ПРНЕ ДЕИЯРБХЕ - РПЮМЯОНМХПНБЮМХЕ РЮАКХЖШ.

сЙЮГЮММЮЪ НЯНАЕММНЯРЭ - НЯМНБМШЛХ ДЕИЯРБХЪЛХ ЪБКЪЧРЯЪ РЕ ФЕ ОПЕНАПЮГНБЮМХЪ тСПЭЕ, МН ЛЕМЭЬЕИ ПЮГЛЕПМНЯРХ - ОНГБНКЪЕР ОПХЛЕМХРЭ ОПХ╦Л аот Х Й МХЛ, Б РНЛ ЯКСВЮЕ, ЕЯКХ ЯНЛМНФХРЕКХ, НАПЮГСЧЫХЕ ЯНЯРЮБМНЕ N, ЯЮЛХ НЙЮФСРЯЪ ЯНЯРЮБМШЛХ. пЮГПЮАНРЮМН ЛМНЦН ОПНЦПЮЛЛ, ЙНРНПШЕ ДНБНДЪР ПЮГКНФЕМХЕ ДН ОПНЯРШУ ДЕКХРЕКЕИ ВХЯКЮ N. хУ ДЕРЮКЭМШИ ПЮГАНП ЛНФМН ОПНВХРЮРЭ, МЮОПХЛЕП Б ХГБЕЯРМНИ ЙМХЦЕ аКЕИУСРЮ. яЮЛШЕ ХГБЕЯРМШЕ ХГ МХУ, НДМЮЙН, ОНКСВЮЧРЯЪ Б ЯКЕДСЧЫЕЛ ВЮЯРМНЛ ЯКСВЮЕ.

пЮГЛЕПМНЯРЭ - ЯРЕОЕМЭ ДБНИЙХ

оСЯРЭ N = 2^k. рНЦДЮ БШЬЕХГКНФЕММСЧ ЯУЕЛС ЯБЕДЕМХЪ ОПЕНАПЮГНБЮМХЪ тСПЭЕ Й ОПЕНАПЮГНБЮМХЪЛ ЛЕМЭЬЕИ ПЮГЛЕПМНЯРХ ЛНФМН БШОНКМХРЭ НЯНАЕММН ЩТТЕЙРХБМН. щРНЛС ЯОНЯНАЯРБСЧР ЯКЕДСЧЫХЕ ОПХВХМШ:

оПХ БШОНКМЕМХХ ОПЕНАПЮГНБЮМХЪ ПЮГЛЕПМНЯРХ 2 БШВХЯКЪЕЛШЕ ЩЙЯОНМЕМРШ ПЮБМШ ±1, ВРН ДНОНКМХРЕКЭМН ЩЙНМНЛХР МЮ НОЕПЮЖХЪУ СЛМНФЕМХЪ, НЯРЮБКЪЪ РНКЭЙН ЯКНФЕМХЪ Х БШВХРЮМХЪ.
оНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ ОЕПБНЦН ЬЮЦЮ ДЮЧР МЮЛ ОНКМШИ МЮАНП ЛМНФХРЕКЕИ БРНПНЦН Х ОНЯКЕДСЧЫХУ ЬЮЦНБ, ВРН РЮЙФЕ ДЮ╦Р МЮЛ ЩЙНМНЛХЧ (УНРЭ Х ЛЕМЭЬЕЦН ОНПЪДЙЮ, ВЕЛ ЦКЮБМШЕ ОПЕНАПЮГНБЮМХЪ) Б БШВХЯКЕМХЪУ ЙЮЙ РПХЦНМНЛЕРПХВЕЯЙХУ ТСМЙЖХИ, РЮЙ Х ЙНЛОКЕЙЯМШУ ОПНХГБЕДЕМХИ. н БКХЪМХХ ЩРНЦН МЮ НЬХАЙХ НЙПСЦКЕМХЪ Б дот АСДЕР ЯЙЮГЮМН НРДЕКЭМН. оПХ ЩРНЛ МЕ ПЮБМШ 1 РНКЭЙН ЛМНФХРЕКХ БРНПНЦН ЯРНКАЖЮ.

нАЫЮЪ ЯРПСЙРСПЮ НДМНЦН ЬЮЦЮ аот (АЕГ СВ╦РЮ РПЮМЯОНМХПНБЮМХИ, МН Я СВ╦РНЛ СЛМНФЕМХИ МЮ ОНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ) ДКЪ N = 2^k ДЮ╦Р МЮЛ ПХЯСМНЙ РЮЙНЦН БХДЮ:

йПЮЯМШЛХ КХМХЪЛХ НАНГМЮВЕМЮ ОЕПЕДЮВЮ МЮВЮКЭМШУ ДЮММШУ (ЛЮЯЯХБЮ ХГ 2+1 ОЮП ДЕИЯРБХРЕКЭМШУ ВХЯЕК, ЙЮФДЮЪ ОЮПЮ - ДЕИЯРБХРЕКЭМЮЪ Х ЛМХЛЮЪ ВЮЯРЭ ЯННРБЕРЯРБСЧЫХУ ЙНЛОКЕЙЯМШУ ВХЯЕК). дЮКЕЕ ЛШ ББЕПУС БХДХЛ ОПНЯРСЧ ГЮОХЯЭ ПЕГСКЭРЮРНБ, Ю БМХГС - ЯРПСЙРСПС Я СЛМНФЕМХЕЛ МЮ ОНБНПЮВХБЮЧЫХИ ЛМНФХРЕКЭ, МЕ ПЮБМШИ 1. гЕК╦МШЛХ ЯРПЕКЙЮЛХ НАНГМЮВЕМЮ ГЮОХЯЭ ДЮММШУ Б ЛЮЯЯХБ (Х ГДЕЯЭ ЛШ БХДХЛ Б ЯЕПЕДХМЕ ЯРПСЙРСПС, ГЮЛЕМХБЬСЧ РПЮМЯОНМХПНБЮМХЕ ЛЮРПХЖШ 2У2). йБЮДПЮРЮЛХ ФЕ НАНГМЮВЕМШ ЩКЕЛЕМРШ ЛЮЯЯХБЮ (ЙПЮЯМШЛХ - МЮВЮКЭМШЕ ДЮММШЕ ЬЮЦЮ аот, ГЕК╦МШЛХ - БШВХЯКЕММНЕ ОНДОПНЦПЮЛЛНИ ХУ дот Я СЛМНФЕМХЕЛ МЮ ЛМНФХРЕКХ, ПНГНБШЛХ - ОНБНПЮВХБЮЧЫХИ ЛМНФХРЕКЭ).

оПХБЕД╦Л РЕОЕПЭ НАЫСЧ БШВХЯКХРЕКЭМСЧ ЯРПСЙРСПС, УЮПЮЙРЕПМСЧ ДКЪ ЯКСВЮЪ, ЙНЦДЮ ПЮГЛЕПМНЯРЭ дот - ЯРЕОЕМЭ ДБНИЙХ. дЮФЕ ОПХ ОНЯКЕДНБЮРЕКЭМН-ПЕЙСППЕМРМНИ НПЦЮМХГЮЖХХ ПЮГАХЕМХЪ N ОНОНКЮЛ МЮ дот ЛЕМЭЬЕИ ПЮГЛЕПМНЯРХ СФЕ ЕЯРЭ ДБЮ БЮПХЮМРЮ, НОХЯЮММШУ С аКЕИУСРЮ (ЙНЦДЮ ДБНИЙНИ ЪБКЪЕРЯЪ ЙНКХВЕЯРБН ЯРПНЙ Б ПЮГАХЕМХХ БШЬЕ, Ю ДЮКЭМЕИЬЕЛС ПЮГАХЕМХЧ ОНОНКЮЛ ОНДБЕПЦЮЧРЯЪ ЯРНКАЖШ, ХКХ ФЕ МЮНАНПНР, ДБНИЙЮ - ЙНКХВЕЯРБН ЯРНКАЖНБ, Ю ДЮКЭЬЕ ПЮГАХБЮЧРЯЪ ЯРПНЙХ), ХЛЕЧЫХЕ НАЫЕОПХМЪРШЕ ДКЪ "ЯХЦМЮКЭЫХЙНБ" МЮГБЮМХЪ - "Я ОПНПЕФХБЮМХЕЛ ОН ВЮЯРНРЕ" ХКХ ФЕ "Я ОПНПЕФХБЮМХЕЛ ОН БПЕЛЕМХ" . нМХ, НДМЮЙН, АКХГЙХ ОН ЯРПСЙРСПЕ ДПСЦ Й ДПСЦС:

мЮ ПХЯСМЙЕ - НАЫЮЪ ЯРПСЙРСПМЮЪ ЯУЕЛЮ аот ДКЪ N=16. гЕК╦МШЕ БЕПЬХМШ ЯННРБЕРЯРБСЧР БШОНКМЪЕЛШЛ ЛЮЙПННОЕПЮЖХЪЛ, НОХЯЮММШЛ БШЬЕ. оЕПЕДЮВЮ ДЮММШУ ОНЙЮГЮМЮ В╦ПМШЛХ Х ЯХМХЛХ ЯРПЕКЙЮЛХ. ъПСЯШ ОЮПЮККЕКЭМНИ ТНПЛШ ЛЮЙПНЦПЮТЮ аот ПЮЯОНКНФЕМШ ОН БЕПРХЙЮКЪЛ. еЯКХ БЯ╦ ДЕКЮРЭ РЮЙХЛ НАПЮГНЛ, ОПХ БШОНКМЕМХХ аот ДКЪ N = 2^k ХГБЕЯРМН, ВРН НМН ЛНФЕР АШРЭ ПЕЮКХГНБЮМН ГЮ N log₂N / 2 НОЕПЮЖХИ ЙНЛОКЕЙЯМНЦН СЛМНФЕМХЪ Х N log₂N НОЕПЮЖХИ ЙНЛОКЕЙЯМНЦН ЯКНФЕМХЪ.

гДЕЯЭ ЛШ ЯОЕЖХЮКЭМН МЕ ОПХБНДХЛ НЖЕМЙХ ВЕПЕГ ДЕИЯРБХРЕКЭМШЕ СЛМНФЕМХЪ Х ЯКНФЕМХЪ, ОНЯЙНКЭЙС ДКЪ ЯЮЛХУ ЙНЛОКЕЙЯМШУ СЛМНФЕМХИ ЕЯРЭ ПЮГМШЕ ПЕЮКХГЮЖХХ - ЙЮЙ НАШВМЮЪ (ВЕПЕГ 4 СЛМНФЕМХЪ Х 2 ЯКНФЕМХЪ), РЮЙ Х "АШЯРПЮЪ" (ВЕПЕГ 3 СЛМНФЕМХЪ Х 3 ЯКНФЕМХЪ).

йЮЙ БХДМН ХГ ПХЯСМЙЮ, ЯРПСЙРСПЮ ОЕПЕЯШКНЙ МЕКХМЕИМЮЪ, НМЮ ЩЙЯОНМЕМЖХЮКЭМН ГЮБХЯХР НР МНЛЕПЮ ЬЮЦЮ аот. нДМЮЙН ОПХ ОПЮБХКЭМНИ НПЦЮМХГЮЖХХ ЯНВЕРЮМХЪ РПЮМЯОНМХПНБЮМХИ ЯРПСЙРСПЮ ОЕПЕЯШКНЙ АСДЕР МЕХГЛЕММНИ НР ЬЮЦЮ Й ЬЮЦС аот. оКЮРНИ ГЮ ЩРН АСДЕР, НДМЮЙН, РН, ВРН ОНКНБХМЮ ДСЦ АСДЕР ОПХМЮДКЕФЮРЭ Й ЙКЮЯЯС ДКХММШУ, Р.Е. ОЕПЕДЮВЮ ДЮММШУ МЕ АСДЕР КНЙЮКЭМНИ, Ю РЮЙФЕ РН, ВРН ОПЕДБЮПХРЕКЭМН ДЮММШЕ МЮДН АСДЕР ПЮЯОНКНФХРЭ Б РЮЙ МЮГШБЮЕЛНЛ АХРХМБЕПЯХБМНЛ ОНПЪДЙЕ (РН ЕЯРЭ Б РЮЙНЛ, ЦДЕ ДБНХВМНЕ ОПЕДЯРЮБКЕМХЕ ХМДЕЙЯЮ ЛЮЯЯХБЮ ХД╦Р МЮНАНПНР). щРЮ ОНДГЮДЮВЮ (МЮВЮКЭМНИ ОЕПЕЯНПРХПНБЙХ) ГЮМХЛЮЕР ОПХЛЕПМН N ОЕПЕЯШКНЙ ДЮММШУ, МН ЯКНФМЮ КНЦХВЕЯЙХ, ОНЩРНЛС Е╦ ПЕЬЕМХЕ ЛШ ГДЕЯЭ ОПХБНДХРЭ МЕ АСДЕЛ.

дКЪ ПЕЮКХГЮЖХХ МЮ окхяЮУ ЕЯРЭ ОПХЛЕП ТПЮЦЛЕМРЮ ОПНЦПЮЛЛШ МЮ ЪГШЙЕ Colamo, ХЯОНКЭГСЧЫЕИ аот (ЛЕРНД йСКХ-рЭЧЙХ ДКЪ ОПНХГБНКЭМНИ ЯРЕОЕМХ ДБНИЙХ) ОПЪЛНСЦНКЭМНЦН ЛЮЯЯХБЮ ПЮГЛЕПЮ 1024У1024 ОН ЯРПНЙЮЛ, ПЮГПЮАНРЮММШИ Б мхх лбя ОПХ рпрс. бНР Е╦ РЕЙЯР (ЛШ АСДЕЛ ОЕПХНДХВЕЯЙХ БЯРЮБКЪРЭ ЯБНХ ОНЪЯМЕМХЪ):

Include MyLibNewElement;

var ReX_in, ImX_in, ReX_out, ImX_out: Array real [1024:Stream, 1024:Stream] Mem; // бУНДМНИ Х БШУНДМНИ ЛЮЯЯХБ ЯРПНЙХ, ЯРНКАЖШ
var ReX_in_com, ImX_in_com: Array real [1024:Stream, 1024:Stream, 10: Stream] Com; // бУНДМНИ Х БШУНДМНИ ЛЮЯЯХБ ЯРПНЙХ, ЯРНКАЖШ, ХРЕПЮЖХХ
var invert: Array integer [10: Stream,512: Stream] mem; // ЛЮЯЯХБ Я ЮДПЕЯЮЛХ Б АХРХМБЕПЯХБМНЛ ОНПЪДЙЕ

бХДМН, ВРН ДЮММШЕ ХГМЮВЮКЭМН СФЕ ПЮЯОНКНФЕМШ Б РЮЙ МЮГШБЮЕЛНЛ АХРХМБЕПЯХБМНЛ ОНПЪДЙЕ, РЮЙ ВРН ПЮГПЮАНРВХЙХ ОПНЦПЮЛЛШ ДКЪ окхя ЯКНФМСЧ КНЦХЙС ЩРНЦН ОЕПЕСОНПЪДНВХБЮМХЪ ЛЮЯЯХБЮ НЯРЮБХКХ ДКЪ ПЮАНРШ МЮ БМЕЬМЕЛ УНЯР-ЙНЛОЭЧРЕПЕ ОЕПЕД БШГНБНЛ окхя-ЛНДСКЪ.

var N,i,j,k,m,p : Number;
var ReImW : Array real [512:Stream] Mem; // ЛЮЯЯХБ ЙНЩТТХЖХЕМРНБ аот
var ReA_reg, ImA_reg, ReB_reg, ImB_reg : real Reg; // ЛЮЯЯХБ ЙНЩТТХЖХЕМРНБ аот
var ReA_com, ImA_com, ReB_com, ImB_com : real com; // ЛЮЯЯХБ ЙНЩТТХЖХЕМРНБ аот

гДЕЯЭ БХДМН, ВРН Х БШВХЯКЕМХЕ РПХЦНМНЛЕРПХХ РНФЕ НЯРЮБКЕМН МЮ ОПЕДБЮПХРЕКЭМСЧ ПЮАНРС УНЯР-ЙНЛОЭЧРЕПЮ.

Define N=1024;
ReadFile (inv, FF_Int_64, "inv.txt"); // ВРЕМХЕ ХГ ТЮИКЮ ЛЮЯЯХБЮ Я ЮДПЕЯЮЛХ Б АХРХМБЕПЯХБМНЛ ОНПЪДЙЕ
ReadFile (ReImW, FF_Int_64, "ReImW.txt"); // ВРЕМХЕ ХГ ТЮИКЮ ЛЮЯЯХБЮ ЙНЩТТХЖХЕМРНБ
ReadFile (AB, FF_Int_64, "In_com.txt"); // ВРЕМХЕ ХГ ТЮИКЮ ЛЮЯЯХБЮ ЙНЩТТХЖХЕМРНБ

мЮВЮКН НОХЯЮМХЪ ЯРПСЙРСПШ НЯМНБМНИ НОЕПЮЖХХ (РЮЙ МЮГШБЮЕЛЮЪ "АЮАНВЙЮ" аот):

let But_FFT(in: ReA, ImA, ReB, ImB, ReW, ImW; // БУНДМШЕ ДЮММШЕ
            out: ReA_out, ImA_out, ReB_out, ImB_out); // БШУНДМШЕ ДЮММШЕ
    var ReA, ImA, ReB, ImB, ReA_out, ImA_out, ReB_out, ImB_out, ReW, ImW: real com;
    var Re_C, Im_C: real com; // лЮЯЯХБ ЙНЛЛСР. ОЕПЕЛЕММШУ ЯННРБ. ЯРПСЙРСПЕ аот
    var mul_1, mul_2, mul_3, mul_4: real com; // лЮЯЯХБ ЙНЛЛСР. ОЕПЕЛЕММШУ ЯННРБ. ЯРПСЙРСПЕ аот

   ReA_out := ReA + ReB;
   ImA_out := ImA + ImB;
   Re_C := ReA - ReB;
   Im_C := ImA - ImB;
   Mul_1 := Re_C*ReW;
   Mul_2 := Im_C*ImW;
   Mul_3 := Im_C*ReW;
   Mul_4 := Re_C*ImW;
   ReB_out := Mul_1 - Mul_2;
   ImB_out := Mul_3 + Mul_4;
EndLet;

бХДМН, ВРН ЙКЧВЕБЮЪ ЯРПСЙРСПЮ But_FFT ПЕЮКХГСЕР ХЛЕММН ЯРПСЙРСПС НДМНЦН ЬЮЦЮ аот, ЙНРНПСЧ ЛШ БХДЕКХ БШЬЕ. дЮКЕЕ ЯКЕДСЕР аот ЯРПНЙ ХГНАПЮФЕМХЪ:

CADR Gor_FFT; // йЮДП БШВХЯКЕМХЪ ЯОЕЙРПЮ ЯРПНЙ ХГКАПЮФЕМХЪ
   for m := 0 to 2 do
   begin
     if m = 0 then // ОЕПЕДЮВЮ БУНДМШУ ДЮММШУ com - ОЕПЕЛЕММШЛ
     begin
         for i := 0 to 1024 - 1 do // ЖХЙК ОН ЯРПНЙЮЛ
         begin
             for j := 0 to 1024 - 1 do // ЖХЙК ОН ЯРПНЙЮЛ
             begin
                 ReX_in_com[i, j, 0] := ReX_in[i, j];
                 ImX_in_com[i, j, 0] := ImX_in[i, j];
             end;
         end;
     end

гДЕЯЭ БХДМН, ВРН ДЮММШЕ Х ПЕГСКЭРЮРШ БШВХЯКЕМХИ АСДСР ПЮГМЕЯЕМШ ОН ХРЕПЮЖХЪЛ Б "ТХЙРХБМНЛ" ЛЮЯЯХБЕ (ЙНРНПШИ МЮ ЯЮЛНЛ ДЕКЕ МЕ ЪБКЪЕРЯЪ ЛЮЯЯХБНЛ, ОНЯЙНКЭЙС ХЛЕЕР ЙНЛЛСРЮЖХНММШИ РХО, Ю РНКЭЙН ЯБЪГШБЮЕР НОЕПЮЖХХ ДПСЦ Я ДПСЦНЛ). дЮКЕЕ ЯКЕДСЕР ЯНАЯРБЕММН НЯМНБМНЕ ЦМЕГДН ЖХЙКНБ аот ОН ЯРПНЙЮЛ:

     else if m = 1 then // "ПЮАНВЮЪ" ХРЕПЮЖХЪ
     begin
         for i := 0 to 1024 - 1 do // ЖХЙК ОН ЯРПНЙЮЛ
         begin
             for j := 0 to 10 - 1 do // ЖХЙК ОН ХРЕПЮЖХЪЛ
             begin
                 for k := 0 to 512 - 1 do // ЖХЙК ОН аЮГНБШЛ НОЕПЮЖХЪЛ
                 begin
                     But_FFT(ReX_in_com[i,k*2,j], ImX_in_com[i,k*2,j], ReX_in_com[i,k*2+1,j], ImX_in_com[i,k*2+1,j], // БУНДМШЕ ДЮММШЕ
                     ReImW[Invert[j,k]], ReImW[Invert[j,k]+1], // ЙНЩТТХЖХЕМРШ
                     ReA_com, ImA_com, ReB_com, ImB_com); // БШУНДМШЕ ДЮММШЕ
                     ReA_reg := ReA_com; // ОЕПЕДЮВЮ БШУНДМНЦН ОНРНЙЮ ВЕПЕГ ПЕЦХЯРПШ ДКЪ РНЦН ВРН АШ ХГАЕФЮРЭ "ЙНКЭЖЮ"
                     ImA_reg := ImA_com;
                     ReB_reg := ReB_com;
                     ImB_reg := ImB_com;
                     for p := 0 to 1 do begin // ЖХЙК ОЕПЕДЮВХ БШУНДМШУ ОЮПЮЛЕРПНБ
                         if p = 0 then begin
                             ReX_in_com[i,k,j+1] := ReA_reg;
                             ImX_in_com[i,k,j+1] := ImA_reg;
                         end
                         else if p = 1 then
                         begin
                             ReX_in_com[i,k+512,j+1] := ReB_reg;
                             ImX_in_com[i,k+512,j+1] := ImB_reg;
                         end;
                     end;
                 end;
             end;
         end;
     end

пЮЯЯЛНРПХЛ НЯМНБМНЕ РЕКН ОПНЦПЮЛЛШ. бХДМН, ВРН БМСРПЕММХИ ЖХЙК (ОН k) ПЕЮКХГСЕР БЯ╦ МЕНАУНДХЛНЕ ЛМНФЕЯРБН АЮГНБШУ "АЮАНВЕЙ" МЮ ЙЮФДНЛ ЬЮЦЕ аот, БШОНКМЪЪ ОПХ ЩРНЛ ОЕПЕРЮЯНБЙС ДЮММШУ ДКЪ ЯКЕДСЧЫЕЦН ЬЮЦЮ. яРПСЙРСПЮ ХМДЕЙЯНБ ЛЮЯЯХБНБ, ЙЮЙ БХДМН, КХМЕИМЮ, МН ХЛЕЕР БЙКЧВ╦ММШЕ ЙНМЯРЮМРШ, ЯНОНЯРЮБХЛШЕ Я ОНКНБХМНИ ЩРНИ ПЮГЛЕПМНЯРХ ЛЮЯЯХБЮ. нУБЮРШБЮЧЫХИ ЕЦН ЖХЙК ОН j ПЕЮКХГСЕР ЬЮЦХ аот, Ю БМЕЬМХИ ЖХЙК ОН i - ОЕПЕАНП БЯЕУ ЯРПНЙ.яНАЯРБЕММН, аот ОПЮЙРХВЕЯЙХ СФЕ БШОНКМЕМН.

    else if m = 2 then // ХРЕПЮЖХЪ ОЕПЕДЮВХ ДЮММШУ Б БШУНДМНЕ йпо
     begin
         for i := 0 to 1024 - 1 do // ЖХЙК ОН ЯРПНЙЮЛ
         begin
             for j := 0 to 1024 - 1 do // ЖХЙК ОН ЯРНКАЖЮЛ
             begin
                 ReX_out[i, j] := ReX_in_com[i, j, 10];
                 ImX_out[i, j] := ImX_in_com[i, j, 10];
             end;
         end;
     end;
   end;
ENDCADR;

щРНР ЛЮКЕМЭЙХИ ГЮБЕПЬЮЧЫХИ ЙСЯНЙ БШОНКМЪЕР ГЮОХЯЭ ПЕГСКЭРЮРНБ Б ПЕЮКЭМШЕ ЛЮЯЯХБШ ХГ ЙНЛЛСРЮЖХНММШУ. нЯРЮБЬСЧЯЪ ВЮЯРЭ ОПНЦПЮЛЛШ ЛШ ГДЕЯЭ НОСЯРХЛ, ОНЯЙНКЭЙС НМЮ МЕ ХЛЕЕР НРМНЬЕМХЪ Й ЯНАЯРБЕММН аот, Ю СФЕ ХЯОНКЭГСЕР Е╦ ПЕГСКЭРЮРШ.

End_Program

бЯ╦, ЙЮЙ БХДХЛ, ОПНЦПЮЛЛЮ МЕ НВЕМЭ ЯКНФМЮ. нРЛЕРХЛ ЕЫ╦ ПЮГ БЮФМСЧ БЕЫЭ: МЕЯЛНРПЪ МЮ МЮКХВХЕ Б АХАКХНРЕЙЕ MyLibNewElement РПХЦНМНЛЕРПХВЕЯЙХУ ТСМЙЖХИ, БЯЕ ЛЮЯЯХБШ ЙНЩТТХЖХЕМРНБ ДКЪ ЩРНИ ОПНЦПЮЛЛШ ДНКФМШ АШРЭ ОПЕДБШВХЯКЕМШ ГЮПЮМЕЕ. яБЪГЮМН ЩРН Я ДБСЛЪ ТЮЙРНПЮЛХ. бН-ОЕПБШУ, ПЮГЛЕП ЛЮЯЯХБЮ ХГНАПЮФЕМХЪ ТХЙЯХПНБЮМ Х ОНБРНПЪРЭ НДМС Х РСФЕ ПЮАНРС МЕР МСФДШ, Б РН БПЕЛЪ ЙЮЙ ОНРНЙ ХГНАПЮФЕМХИ, НАПЮАЮРШБЮЕЛШУ МЮ окхяЮУ, ЛНФЕР ХДРХ ДНБНКЭМН АНКЭЬХЛ ОНРНЙНЛ. бН-БРНПШУ, ХЯОНКЭГНБЮМХЕ РПХЦНМНЛЕРПХВЕЯЙХУ ТСМЙЖХИ ДЮФЕ Б ЯКСВЮЕ НДХМНВМШУ БШВХЯКЕМХИ МЮПСЬХКН АШ ПЮБМНЛЕПМНЯРЭ ГЮЦПСГЙХ ЩКЕЛЕМРНБ окхя Х, ЙЮЙ ЯКЕДЯРБХЕ, ОПХБЕКН АШ Й ОПНЯРНЧ ГМЮВХРЕКЭМНИ ВЮЯРХ окхя. йПНЛЕ РНЦН, НРЛЕРХЛ, ВРН ХЯОНКЭГНБЮМХЕ Б БШВХЯКЕМХЪУ ЛЮЯЯХБЮ, ЙЮГЮКНЯЭ АШ, ДЕЯЪРХЙПЮРМН АНКЕЕ НАЗ╦ЛМНЦН, ВЕЛ ХЯУНДМШИ, БНБЯЕ МЕ СБЕКХВХБЮЕР ОЮЛЪРЭ, ХЯОНКЭГСЕЛСЧ Б окхя-ЛНДСКЪУ, ОНЯЙНКЭЙС ЙНЛЛСРЮЖХНММШИ РХО ЛЮЯЯХБЮ ХЯЙКЧВЮЕР ЕЦН УПЮМЕМХЕ РЮЛ, ЦДЕ НМН МЕ МЕНАУНДХЛН.

пЮГЛЕПМНЯРЭ - В╦РМЮЪ ЯРЕОЕМЭ ДБНИЙХ

нОХЯЮММШЕ БШЬЕ ЯУЕЛШ Х ОПНЦПЮЛЛЮ аот ДКЪ ОПНХГБНКЭМНИ ЯРЕОЕМХ ДБНИЙХ ЪБКЪЧРЯЪ РНИ ПЕЮКХГЮЖХЕИ ЛЕРНДЮ йСКХ-рЭЧЙХ, ЙНРНПШИ МЮХАНКЕЕ ПЮЯОПНЯРПЮМ╦М ЯПЕДХ ПЕЮКХГЮЖХИ аот. нДМЮЙН ЩРНР ЮКЦНПХРЛ, МЕЯЛНРПЪ МЮ ЕЦН ОПЕХЛСЫЕЯРБЮ (МЮОПХЛЕП, НДМНРХОМНЯРЭ НЯМНБМШУ НОЕПЮЖХИ МЮ ЙЮФДНЛ ЬЮЦЕ), МЕ ЪБКЪЕРЯЪ ЯЮЛШЛ АШЯРПШЛ ХГ ПЕЮКХГЮЖХИ аот МЮ ЯРЕОЕМЪУ ДБНИЙХ. б ЯКСВЮЕ, ЕЯКХ k (ОНЙЮГЮРЕКЭ ЯРЕОЕМХ ДБНИЙХ) В╦РМН, РН НЙЮГШБЮЕРЯЪ, ВРН аот ЛЕРНДНЛ йСКХ-рЭЧЙХ ДКЪ N = 2^k ЛНФЕР АШРЭ ПЕЮКХГНБЮМН ДЮФЕ ГЮ 3N log₂ N / 8 НОЕПЮЖХИ ЙНЛОКЕЙЯМНЦН СЛМНФЕМХЪ Х N log₂ N НОЕПЮЖХИ ЙНЛОКЕЙЯМНЦН ЯКНФЕМХЪ. гЮ ЯВ╦Р ВЕЦН ФЕ В╦РМЮЪ ЯРЕОЕМЭ ДЮ╦Р МЮЛ ДНОНКМХРЕКЭМШИ БШХЦПШЬ?

пЮЯЯЛНРПХЛ ОПЕНАПЮГНБЮМХЕ тСПЭЕ ОНПЪДЙЮ 4. оПХЛЕМХЛ Й МЕЛС ПЮГКНФЕМХЕ МЮ 2 аот ОНПЪДЙЮ 2 Х СБХДХЛ, ВРН БЯЕ ОНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ ПЮБМШ ±1 КХАН ±i, ВРН ДЮ╦Р МЮЛ БНГЛНФМНЯРЭ МЕ СЛМНФЮРЭ ЯННРБЕРЯРБСЧЫХЕ ЩКЕЛЕМРШ РЮАКХЖШ, Ю ОПНЯРН АПЮРЭ ХУ Я ПЮГМШЛХ ГМЮЙЮЛХ Х ЙНЛАХМХПНБЮРЭ ХУ ДЕИЯРБХРЕКЭМШЕ Х ЛМХЛШЕ ВЮЯРХ. оНДОПНЦПЮЛЛС ОПЪЛНЦН аот ОНПЪДЙЮ 4 МЮАНПЮ 4 ЙНЛОКЕЙЯМШУ ВХЯЕК ЛНФМН МЮ тНПРПЮМЕ ГЮОХЯЮРЭ, МЮОПХЛЕП, РЮЙ:

      subroutine FT4D(A1,A2,A3,A4)
      real A1(2),A2(2),A3(2),A4(2),C1(2),C2(2),C3(2),C4(2)
      C1(1) = A1(1)+A3(1)
      C1(2) = A1(2)+A3(2)
      C2(1) = A2(1)+A4(1)
      C2(2) = A2(2)+A4(2)
      C3(1) = A1(1)-A3(1)
      C3(2) = A1(2)-A3(2)
      C4(1) = A2(1)-A4(1)
      C4(2) = A2(2)-A4(2)
      A1(1) = C1(1)+C2(1)
      A1(2) = C1(2)+C2(2)
      A3(1) = C1(1)-C2(1)
      A3(2) = C1(2)-C2(2)
      A2(1) = C3(1)-C4(2)
      A2(2) = C3(2)+C4(1)
      A4(1) = C3(1)+C4(2)
      A4(2) = C3(2)-C4(1)
      return
      end

ю Б НАПЮРМНЛ аот ОНПЪДЙЮ 4 АСДСР МЕЯЙНКЭЙН ОЕПЕЯРЮБКЕМШ ГМЮЙХ Х ХМДЕЙЯШ:

      subroutine FT4R(A1,A2,A3,A4)
      real A1(2),A2(2),A3(2),A4(2),C1(2),C2(2),C3(2),C4(2)
      C1(1) = A1(1)+A3(1)
      C1(2) = A1(2)+A3(2)
      C2(1) = A2(1)+A4(1)
      C2(2) = A2(2)+A4(2)
      C3(1) = A1(1)-A3(1)
      C3(2) = A1(2)-A3(2)
      C4(1) = A2(1)-A4(1)
      C4(2) = A2(2)-A4(2)
      A1(1) = C1(1)+C2(1)
      A1(2) = C1(2)+C2(2)
      A3(1) = C1(1)-C2(1)
      A3(2) = C1(2)-C2(2)
      A4(1) = C3(1)-C4(2)
      A4(2) = C3(2)+C4(1)
      A2(1) = C3(1)+C4(2)
      A2(2) = C3(2)-C4(1)
      return
      end

мН ЕЦН ЯРПСЙРСПЮ Б ОПХМЖХОЕ - РЮ ФЕ. мЮ ПХЯСМЙЕ

ОНЙЮГЮМЮ ЯРПСЙРСПЮ ОПЪЛНЦН ОПЕНАПЮГНБЮМХЪ тСПЭЕ ПЮГЛЕПМНЯРХ 4, Р.Е. НДМН ХГ ЩКЕЛЕМРЮПМШУ ОПЕНАПЮГНБЮМХИ аот ОНПЪДЙЮ В╦РМНИ ЯРЕОЕМХ ДБНИЙХ. йПЮЯМШЛХ КХМХЪЛХ НАНГМЮВЕМЮ ОЕПЕДЮВЮ МЮВЮКЭМШУ ДЮММШУ (ЛЮЯЯХБЮ ХГ 4 ОЮП ДЕИЯРБХРЕКЭМШУ ВХЯЕК, ЙЮФДЮЪ ОЮПЮ - ДЕИЯРБХРЕКЭМЮЪ Х ЛМХЛЮЪ ВЮЯРЭ ЯННРБЕРЯРБСЧЫХУ ЙНЛОКЕЙЯМШУ ВХЯЕК). дЮКЕЕ ЛШ ББЕПУС БХДХЛ ЯРПСЙРСПС, ОНУНФСЧ МЮ ЬЮЦ аот КЧАНИ ЯРЕОЕМХ ДБНИЙХ, Ю БМХГС - "ГЮОСРЮММСЧ" ЯРПСЙРСПС ОНУНФЕЦН БХДЮ. гЮОСРЮММНЯРЭ БШГБЮМЮ РЕЛ, ВРН СЛМНФЕМХЕ МЮ ОНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ АШКН ГЮЛЕМЕМН ПЮЯЯРЮМНБЙНИ ГМЮЙНБ Я БГЮХЛМШЛХ ГЮЛЕМЮЛХ ДЕИЯРБХРЕКЭМШУ Х ЛМХЛШУ ВЮЯРЕИ. гЕК╦МШЛХ ЯРПЕКЙЮЛХ НАНГМЮВЕМЮ ГЮОХЯЭ ДЮММШУ Б ЛЮЯЯХБ (Х ГДЕЯЭ ЛШ БХДХЛ Б ЯЕПЕДХМЕ ЯРПСЙРСПС, ГЮЛЕМХБЬСЧ РПЮМЯОНМХПНБЮМХЕ ЛЮРПХЖШ 2У2). йБЮДПЮРЮЛХ ФЕ НАНГМЮВЕМШ ЩКЕЛЕМРШ ЛЮЯЯХБЮ (ЙПЮЯМШЛХ - МЮВЮКЭМШЕ ДЮММШЕ аот, ГЕК╦МШЛХ - БШВХЯКЕММНЕ ОНДОПНЦПЮЛЛНИ ОПЪЛНЕ дот).

рЕОЕПЭ БЯОНЛМХЛ ОПН СЛМНФЕМХЕ МЮ ОНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ, ЙНРНПНЕ ГЮБЕПЬЮЕР ЬЮЦ аот ОНПЪДЙЮ, ПЮГКНФЕММНЦН ОН ВЕРБ╦ПЙЮЛ, Х СБХДХЛ, ВРН ХГ 4 ОНКСВЕММШУ ОНЯКЕ тСПЭЕ ОНПЪДЙЮ 4 ЙНЛОКЕЙЯМШУ ВХЯЕК СЛМНФЕМХЧ ОНДБЕПЦЮЧРЯЪ 3. рН ЕЯРЭ ХГ БЯЕЦН ЛЮЯЯХБЮ - 3/4², Б НРКХВХЕ НР ОНКНБХМШ ² Б аот, ПЮГКНФЕММНЛ ОН ДБНИЙЮЛ. нДМЮЙН ГЮ ЯВ╦Р РНЦН, ВРН ЯЮЛХУ ЬЮЦНБ С МЮЯ БДБНЕ ЛЕМЭЬЕ, ЛШ Х ОНКСВЮЕЛ БШХЦПШЬ Б ЛМНФХРЕКЕ ОПХ N log₂ N Б ЙНКХВЕЯРБЕ ЙНЛОКЕЙЯМШУ СЛМНФЕМХИ.

еЯКХ ЛШ ОНОШРЮЕЛЯЪ ОПХЛЕМХРЭ РЮЙНИ ФЕ ОПХ╦Л ДКЪ СЛЕМЭЬЕМХЪ ДНКХ ЙНЛОКЕЙЯМШУ СЛМНФЕМХИ, МЮОПХЛЕП, БГЪБ Б ЙЮВЕЯРБЕ АЮГНБНЦН дот ОНПЪДЙЮ 8 (ЯРЕОЕМЭ ДБНИЙХ, РЮЙХЛ НАПЮГНЛ, ДНКФМЮ ДЕКХРЭЯЪ МЮ 3), РН СБХДХЛ, ВРН МЮ ОНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ СЛМНФЮЧРЯЪ 7 ВХЯЕК ХГ 8, ОНКСВЕММШУ ОНЯКЕ дот ОНПЪДЙЮ 8, Х ГЮ ЯВ╦Р РНЦН, ВРН ЩРЮОНБ БРПНЕ ЛЕМЭЬЕ - Х ОНКСВХЛ, ЙЮГЮКНЯЭ АШ, ЙНЩТТХЖХЕМР 7/24, РН ЕЯРЭ ЕЫ╦ ЛЕМЭЬЕ. нДМЮЙН Б АЮГНБНЛ дот ОНПЪДЙЮ 8, ЙЮЙ НЙЮГШБЮЕРЯЪ, МЕКЭГЪ СФЕ ОНКМНЯРЭЧ ХГАЮБХРЭЯЪ НР ЙНЛОКЕЙЯМШУ СЛМНФЕМХИ, Х ОПХ ХУ СВ╦РЕ ЛШ ЯМНБЮ ОНКСВЮЕЛ РЕ ФЕ, ВРН ДКЪ В╦РМШУ ЯРЕОЕМЕИ, 3/8 Б ЙНЩТТХЖХЕМРЕ ОПХ N log₂ N. оПЮБДЮ, ОПХ АКХФЮИЬЕЛ ПЮЯЯЛНРПЕМХХ НЙЮГШБЮЕРЯЪ, ВРН ВЮЯРЭ ХГ СЛМНФЕМХИ ЪБКЪЕРЯЪ СЛМНФЕМХЕЛ МЮ ВХЯКЮ ЯОЕЖХЮКЭМНЦН БХДЮ Х ЛНФЕР АШРЭ БШОНКМЕМЮ АШЯРПЕЕ, МН ЩРН СЯКНФМЪЕР НАЫСЧ ЯУЕЛС. нДМЮЙН, ЕЯКХ СЯКНФМЕМХЕ МЕ ОСЦЮЕР, РН ЛНФМН ДНБЕЯРХ НОРХЛХГЮЖХЧ ДН ПЮГЛЕПМНЯРХ 16.

нАЫЮЪ ЯУЕЛЮ аот В╦РМНИ ЯРЕОЕМХ ДБНИЙХ, ПЮЯОХЯЮММЮЪ ВЕПЕГ ЛЮЙПННОЕПЮЖХХ, БШЦКЪДХР ЕЫ╦ ЯКНФМЕЕ, ВЕЛ АЕГ СВ╦РЮ В╦РМНЯРХ. оНЩРНЛС ГДЕЯЭ НМЮ МЕ ОПХБНДХРЯЪ.

²мЮ ЯЮЛНЛ ДЕКЕ - МЕ 3/4 Х МЕ ОНКНБХМЮ, Ю ВСРЭ ЛЕМЭЬЕ.

пЮГЛЕПМНЯРХ, МЕ ЪБКЪЧЫХЕЯЪ ЯРЕОЕМЪЛХ ДБНИЙХ

пЕЮКЭМШЕ ГЮДЮВХ РЮЙНБШ, ВРН ПЮГЛЕПМНЯРЭ дот, ЙНРНПНЕ ОНДКЕФХР "САШЯРПЕМХЧ", ЛНФЕР НЙЮГЮРЭЯЪ БНБЯЕ МЕ ЯРЕОЕМЭЧ ДБНИЙХ. дКЪ РЕУ ЯОЕЖХЮКХЯРНБ, ЙРН МЕ УНВЕР КНЛЮРЭ ЦНКНБС МЮД БШАНПНЛ ЮКЦНПХРЛЮ, Б МЮЯРНЪЫЕЕ БПЕЛЪ ПЮЯОПНЯРПЮМ╦М ЛЕРНД ПЕЬЕМХЪ "НР ЯРЕОЕМХ", ОПХ ЙНРНПНЛ ПЕЮКЭМСЧ ГЮДЮВС ОПНЯРН "ОНДЦНМЪЧР" ОНД ЯРЕОЕМЭ ДБНИЙХ (АШБЮЕР ДЮФЕ, ВРН ЩРН ДЕКЮЧР Я ПЕЮКЭМШЛХ южо Б СЯРПНИЯРБЮУ). нДМЮЙН РЮЙНИ ЛЕРНД БН ЛМНЦХУ ГЮДЮВЮУ МЕОПХЕЛКЕЛ ОН ПЮГМШЛ ОПХВХМЮЛ. сБЕКХВЕМХЕ ПЮГЛЕПЮ ДН АКХФЮИЬЕИ ЯРЕОЕМХ ДБНИЙХ ЛНФЕР ЯСЫЕЯРБЕММН СБЕКХВХРЭ ПЮГЛЕП ГЮДЮВХ. йПНЛЕ ЩРНЦН, ПЪД ГЮДЮВ РПЮДХЖХНММН НПХЕМРХПНБЮМ МЮ ПЮГЛЕПМНЯРХ, ГЮБЕДНЛН МЕ ЪБКЪЧЫХЕЯЪ ЯРЕОЕМЪЛХ ДБНИЙХ (УНРЭ Х ЯНДЕПФЮЫХЕ ХУ Б ЙЮВЕЯРБЕ ДЕКХРЕКЕИ). мЮОПХЛЕП, Б ЦЕНТХГХВЕЯЙХУ ЙКХЛЮРХВЕЯЙХУ ГЮДЮВЮУ НДМНИ ХГ РПЮДХЖХНММШУ ЯЕРНЙ ЪБКЪЕРЯЪ ЦПЮДСЯМЮЪ (ХКХ ЙПЮРМШЕ ЦПЮДСЯМНИ). оПХ ЩРНЛ ОНКСВЮЕРЯЪ, ВРН ПЮГЛЕПМНЯРЭ ОН ДНКЦНРЕ (Я СВ╦РНЛ ОЕПХНДХВМНЯРХ) АСДЕР ЙПЮРМЮ 360, РН ЕЯРЭ ЯНДЕПФЮРЭ НДМС ОЪР╦ПЙС Х ДБЕ РПНИЙХ. оНЩРНЛС ЯСЫЕЯРБСЧР РЮЙХЕ ЮКЦНПХРЛШ аот, ЙЮЙ ЛЕРНДШ цСДЮ-рНЛЮЯЮ, бХМНЦПЮДЮ Х ДП. мЮДН ЯЙЮГЮРЭ, ВРН НМХ, ЙПНЛЕ ОПНВЕЦН, ЪБКЪЧРЯЪ Х АНКЕЕ АШЯРПШЛХ, ВЕЛ ЮКЦНПХРЛ йСКХ-рЭЧЙХ ДКЪ ОПНХГБНКЭМНИ ЯРЕОЕМХ ДБНИЙХ. оНЩРНЛС БН БПЕЛЕМЮ, ЙНЦДЮ ЕЫ╦ МЕ АШКН ЛЮЯЯНБНИ ЙНЛОЭЧРЕПХГЮЖХХ Х ГЮДЮВЮЛХ аот ГЮМХЛЮКХЯЭ РНКЭЙН ЯОЕЖХЮКХЯРШ, Б ОПНЦПЮЛЛЮУ аот ЖЮПХКН ЛМНЦННАПЮГХЕ. мШМЕ ФЕ АНКЭЬХМЯРБН ХЯОНКЭГСЕР БНБЯЕ МЕ ЯЮЛШЕ АШЯРПШЕ аот, ДЮФЕ МЕ ОНДНГПЕБЮЪ Н РНЛ, ВРН БНАЫЕ ЛНФМН ПЮАНРЮРЭ МЕ ЯН ЯРЕОЕМЪЛХ ДБНИЙХ. оПХВ╦Л ЩРН ЯБЪГЮМН МЕ РНКЭЙН Я МХГЙХЛ СПНБМЕЛ ГМЮМХИ Н аот.

нЯНАЕММНЯРХ ПЕЮКХГЮЖХХ аот МЮ ОЮПЮККЕКЭМШУ БШВХЯКХРЕКЭМШУ ЯХЯРЕЛЮУ

б ЯКСВЮЕ, ЙНЦДЮ аот ЮДЮОРХПСЕРЯЪ ДКЪ ПЕЮКХГЮЖХХ МЮ ОЮПЮККЕКЭМНИ БШВХЯКХРЕКЭМНИ ЯХЯРЕЛЕ (ЛШ ХЛЕЕЛ Б БХДС ЯКСВЮИ, ЙНЦДЮ МСФМН ПЮЯОЮПЮККЕКХБЮРЭ ЯЮЛН ОПЕНАПЮГНБЮМХЕ тСПЭЕ, Ю МЕ РЕ ЮКЦНПХРЛШ, Б ЙНРНПШУ ОПЕНАПЮГНБЮМХИ тСПЭЕ ПЮГМШУ БЕЙРНПНБ ЛМНЦН Х НМХ ЯЮЛХ ЛНЦСР БШОНКМЪРЭЯЪ ОЮПЮККЕКЭМН ХКХ ЙНМБЕИЕПМН), КНЦХВЕЯЙЮЪ ЯКНФМНЯРЭ ЮКЦНПХРЛЮ, Х, НЯНАЕММН, ЯКНФМНЯРЭ ДЕКЕМХЪ ДЮММШУ ОН ВЮЯРЪЛ ЮКЦНПХРЛЮ, ЯРЮМНБХРЯЪ ЯСЫЕЯРБЕММШЛ РНПЛНГНЛ ДКЪ ЩТТЕЙРХБМНИ ПЕЮКХГЮЖХХ. йПНЛЕ РНЦН, МЕ ЯЕЙПЕР, ВРН АНКЭЬХМЯРБН ЛМНЦНОПНЖЕЯЯНПМШУ БШВХЯКХРЕКЭМШУ ЯХЯРЕЛ Я ПЮГДЕКЭМНИ ОЮЛЪРЭЧ (ЙКЮЯРЕПМЮЪ ЮПУХРЕЙРСПЮ) ВЮЯРН ОПЕДНЯРЮБКЪЕР ЛЮЙЯХЛЮКЭМНЕ ВХЯКН СГКНБ, ЪБКЪЧЫЕЕЯЪ ЯРЕОЕМЭЧ ДБНИЙХ. яХЯРЕЛШ, МЕ ХЛЕЧЫХЕ РЮЙХУ НЦПЮМХВЕМХИ, БПНДЕ окхяНБ, ХЛЕЧР ДПСЦХЕ НЦПЮМХВЕМХЪ. мЮОПХЛЕП, ОПХ ОПНЦПЮЛЛХПНБЮМХХ МЮ COLAMO СЯКНФМЕМХЕ КНЦХВЕЯЙНИ ЯРПСЙРСПШ ОПХ ПЮБМНИ БШВХЯКХРЕКЭМНИ ЛНЫМНЯРХ АСДЕР ТЮЙРНПНЛ, ЯМХФЮЧЫХЛ ОПНХГБНДХРЕКЭМНЯРЭ АЮГНБШУ ЛНДСКЕИ, ОНЯЙНКЭЙС ВЮЯРЭ ОПНЖЕЯЯНПМШУ ЩКЕЛЕМРНБ ОПХ ЯКНФМНИ КНЦХЙЕ ОПНЦПЮЛЛШ АСДЕР КХАН ОПНЯРЮХБЮРЭ, КХАН ПЮАНРЮРЭ, МН БУНКНЯРСЧ (АЕГ ХЯОНКЭГНБЮМХЪ ПЕГСКЭРЮРЮ). мЮ ЙКЮЯРЕПМНИ ЮПУХРЕЙРСПЕ РЮЙФЕ, Б ЯКСВЮЕ ПЮГАХЕМХЪ ЯУЕЛШ аот МЮ АКНЙХ ОН ОПНЖЕЯЯНПЮЛ, БНГМХЙМСР ЯКНФМНЯРХ, ЕЯКХ ПЮГАХБЮРЭ ОПХД╦РЯЪ ВЮЯРХ ЯУЕЛШ, ПЕЮКХГСЧЫХЕ от ЛЕМЭЬЕИ ПЮГЛЕПМНЯРХ (ПЮГМШУ ДЕКХРЕКЕИ N). бЯ╦ ЩРН РЮЙФЕ ОПХБНДХР Й РНЛС, ВРН ПЕЮКХГЮЖХХ ДКЪ ЯРЕОЕМЕИ ДБНИЙХ БШРЕЯМЪЧР НЯРЮКЭМШЕ ЮКЦНПХРЛШ аот.

й ЯНФЮКЕМХЧ, МЕКХМЕИМЮЪ ЯУЕЛЮ БШГНБНБ ПЮГКХВМШУ ЩКЕЛЕМРНБ ПЮАНВХУ ЛЮЯЯХБНБ ЯЙЮГШБЮЕРЯЪ МЮ ПЮГКХВМШУ ПЕЮКХГЮЖХЪУ аот ОНПЪДЙЮ ЯРЕОЕМХ ДБНИЙХ, ЙНЦДЮ ПЕВЭ ГЮУНДХР НА ЮДЮОРЮЖХХ Я ЛХМХЛХГЮЖХЕИ НАЛЕММШУ НОЕПЮЖХИ (ЙЮЙ МЮ ЙКЮЯРЕПЮУ), КХАН ОПХ НЦПЮМХВЕММШУ ПЕЯСПЯЮУ, БШДЕКЕММШУ МЮ ОЮПЮККЕКЭМСЧ БЕРБЭ (ЙЮЙ МЮ СЯЙНПХРЕКЪУ). оПХ ЩРНЛ ПЪД ПЮГПЮАНРВХЙНБ, ЯРЮКЙХБЮЪЯЭ Я РЕЛ, ВРН БЯЕ ОНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ, ОПЕДБШВХЯКЕММШЕ ХЛ, МЕ ЛНЦСР АШРЭ КХАН ПЮГЛЕЫЕМШ Б ХЛЕЧЫЕИЯЪ ОЮЛЪРХ, КХАН АШЯРПН ДНЯРЮБКЕМШ Й ЛЕЯРС ХУ ХЯОНКЭГНБЮМХЪ, ХДСР МЮ ХУ ОЕПЕБШВХЯКЕМХЕ МЮ ЙЮФДНЛ ЬЮЦЕ. щРН ЯПЮГС ЯЙЮГШБЮЕРЯЪ МЮ АШЯРПНРЕ ХУ ПЕЮКХГЮЖХИ, ОНЯЙНКЭЙС ЯСЫЕЯРБЕММН СБЕКХВХБЮЕР ЙНКХВЕЯРБН НОЕПЮЖХИ ОН ЯПЮБМЕМХЧ Я ЩРЮКНММШЛ аот.

аНКЕЕ ОПЮБХКЭМШЛ ЬЮЦНЛ ОН ОПЕНДНКЕМХЧ НЦПЮМХВЕММНЯРХ ПЕЯСПЯНБ КХАН ЛХМХЛХГЮЖХХ ОЕПЕЯШКНЙ, БХДХЛН, ЪБКЪЕРЯЪ ХЯОНКЭГНБЮМХЕ РЮЙНИ ЯУЕЛШ, ЙНРНПЮЪ ГЮКНФЕМЮ ЯЮЛЮ Б аот, ОПХ Е╦ ЙНМЯРПСХПНБЮМХХ. хДЕЪ, Б НАЫЕЛ-РН, МЮЯРНКЭЙН НВЕБХДМЮЪ, ВРН, ЙНЦДЮ С ОПНЦПЮЛЛХЯРЮ ЕЯРЭ ОНКМНЕ ПЮГКНФЕМХЕ N МЮ ОПНЯРШЕ ЛМНФХРЕКХ N=2^k, НМЮ МЕ БЯЕЛ ОПХУНДХР Б ЦНКНБС: ЩРН ХЯОНКЭГНБЮРЭ МЕ ОНКМНЕ ПЮГКНФЕМХЕ МЮ ОПНЯРШЕ ЛМНФХРЕКХ, Ю ПЮГКНФЕМХЕ РХОЮ N=ML, ЦДЕ M, L - ДНБНКЭМН АНКЭЬХЕ ВХЯКЮ, РНФЕ ЪБКЪЧЫХЕЯЪ ЯРЕОЕМЪЛХ ДБНИЙХ. рНЦДЮ ЛШ БХДХЛ, ВРН БЯЕ ОНБНПЮВХБЮЧЫХЕ ЛМНФХРЕКХ аот ОНПЪДЙЮ N АСДСР ХЯОНКЭГНБЮМШ РНКЭЙН НДМЮФДШ - ЛЕФДС аот ОНПЪДЙЮ M Х аот ОНПЪДЙЮ L. яЮЛХ ФЕ ЩРХ аот ОНПЪДЙНБ M, L ЛНФМН, Б ГЮБХЯХЛНЯРХ НР ПЕЯСПЯНБ, ПЕЮКХГНБЮРЭ ЙЮЙ аот ЯРЕОЕМХ ДБНИЙХ, КХАН РНФЕ ПЮГКНФХРЭ МЮ ЛЕМЭЬХЕ ЛМНФХРЕКХ, Х РЮЙ - ДН РНИ ЯРЕОЕМХ, ОНЙЮ ПЕЯСПЯНБ УБЮРХР, КХАН ОЕПЕЯШКНЙ ЛЕФДС ЙНЛОНМЕМРЮЛХ лбя ЯРЮМЕР ДНЯРЮРНВМН ЛЮКН.

нЬХАЙХ НЙПСЦКЕМХЪ Х ОПЕНАПЮГНБЮМХЕ тСПЭЕ

йЮЙ МЕРПСДМН БХДЕРЭ ОН ТНПЛСКЮЛ, ОПХ БШОНКМЕМХХ ОПЕНАПЮГНБЮМХИ тСПЭЕ АНКЭЬНИ ПЮГЛЕПМНЯРХ БЕПНЪРМН БШВХЯКЕМХЕ РПХЦНМНЛЕРПХВЕЯЙХУ ТСМЙЖХИ НР АНКЭЬХУ ЮПЦСЛЕМРНБ. й ЯНФЮКЕМХЧ, ЯПЕДХ ОПНЦПЮЛЛ-ПЕЮКХГЮЖХИ ОПЕНАПЮГНБЮМХЪ тСПЭЕ ЮБРНПНЛ АШКН НАМЮПСФЕМН ЯПЮБМХРЕКЭМН ЛЮКН ПЕЮКХГЮЖХИ, БШОНКМЪЧЫХУ ОПЕДБЮПХРЕКЭМНЕ ОПХБЕДЕМХЕ ЮПЦСЛЕМРЮ Я ХЯОНКЭГНБЮМХЕЛ ЖЕКНВХЯКЕММНИ ЮПХТЛЕРХЙХ, Ю ДЕИЯРБХРЕКЭМНЕ ОПХБЕДЕМХЕ (ХЯОНКЭГСЕЛНЕ ЯРЮМДЮПРМШЛХ РПХЦНМНЛЕРПХВЕЯЙХЛХ ТСМЙЖХЪЛХ) ДЮ╦Р АНКЭЬСЧ НРМНЯХРЕКЭМСЧ НЬХАЙС. б ЯЮЛНЛ ДЕКЕ, ЕЯКХ ОНПЪДНЙ N Х (ЯКЕДНБЮРЕКЭМН) ЮПЦСЛЕМРЮ - 10⁷, РН ЕЦН ОПХБЕДЕМХЕ Й ДХЮОЮГНМС ОЕПБНЦН ОЕПХНДЮ РПХЦНМНЛЕРПХВЕЯЙХУ ТСМЙЖХИ ДЮЯР НЬХАЙС, МЮ 32-ПЮГПЪДНИ ЮПХТЛЕРХЙЕ (НРМНЯХРЕКЭМЮЪ РНВМНЯРЭ ЙНРНПНИ 10^-7) СФЕ ЯПЮБМХЛСЧ Я ЕДХМХЖЕИ, ВРН ДЕКЮЕР ОПЕНАПЮГНБЮМХЕ МЕРНВМШЛ, Ю ОПНЦПЮЛЛС - НЦПЮМХВЕММН ЦНДМНИ ДКЪ МЕАНКЭЬХУ N.

б ЩРНЛ ОКЮМЕ аот КСВЬЕ РПЮДХЖХНММНЦН ОПЕНАПЮГНБЮМХЪ тСПЭЕ (ОН РНИ ОПНЯРНИ ОПХВХМЕ, ВРН ЮПЦСЛЕМРШ С ТСМЙЖХИ ЯСЫЕЯРБЕММН ЛЕМЭЬЕ, Х ОНЩРНЛС ОПНЦПЮЛЛХЯРЯЙХЕ ОПНЯВ╦РШ ЯЙЮГШБЮЧРЯЪ ЛЕМЭЬЕ), МН Х ГДЕЯЭ ПЕГЕПБШ АНКЕЕ РНВМШУ БШВХЯКЕМХИ ХЯОНКЭГСЧРЯЪ ПЕДЙН. б КСВЬЕЛ ЯКСВЮЕ ЩРХ ПЕГЕПБШ ХЯОНКЭГСЧРЯЪ ДКЪ ОПЕДБШВХЯКЕМХИ ОНБНПЮВХБЮЧЫХУ ЛМНФХРЕКЕИ ДПСЦ ВЕПЕГ ДПСЦЮ. нДМЮЙН Б ЯКСВЮЕ ПЮГЛЕПМНЯРХ, ПЮБМНИ ЖЕКНИ ЯРЕОЕМХ ДБНИЙХ, НЙЮГШБЮЕРЯЪ, ВРН Х ОНЯКЕДМЕЕ СУХЫПЕМХЕ (ОПЕДБШВХЯКЕМХЕ ЛМНФХРЕКЕИ) ДЮЯР РНКЭЙН ДНОНКМХРЕКЭМШЕ НЬХАЙХ, Б РН БПЕЛЪ ЙЮЙ ОПХЛЕМЕМХЕЛ ОПНЯРНИ ЯНПРХПНБЙХ Я ЖЕКНВХЯКЕММШЛ ОПХБЕДЕМХЕЛ НМН ДЕКЮЕРЯЪ МЕМСФМШЛ.

гЮЙКЧВЕМХЕ

аот РПЮДХЖХНММН НРМНЯЪР Й ЦПСООЕ АШЯРПШУ ЮКЦНПХРЛНБ. яКЕДСЕР, НДМЮЙН, НРЛЕРХРЭ, ВРН ЛМНЦХЕ АШЯРПШЕ ЮКЦНПХРЛШ, ХЯОНКЭГСЧЫХЕ ЮЯЯНЖХЮРХБМНЯРЭ Х ДХЯРПХАСРХБМНЯРЭ СЛМНФЕМХИ Х ЯКНФЕМХИ, ЪБКЪЧРЯЪ МЕСЯРНИВХБШЛХ. мЮ аот ЩРН МЕ ПЮЯОПНЯРПЮМЪЕРЯЪ - ЙЮЙ ЛШ БХДХЛ, ДЮФЕ ОПХ ХЯОНКЭГНБЮМХХ РСОНЦН ОПНЦПЮЛЛХПНБЮМХЪ АЕГ СВ╦РЮ НЯНАЕММНЯРЕИ РПХЦНМНЛЕРПХВЕЯЙХУ ТСМЙЖХИ БКХЪМХЕ НЬХАНЙ НЙПСЦКЕМХЪ МЮ аот ЛЕМЭЬЕ, ВЕЛ МЮ ХЯУНДМНЕ ОПЕНАПЮГНБЮМХЕ тСПЭЕ.

й ЯНФЮКЕМХЧ, МЕСЛЕКНЕ ОПНЦПЮЛЛХПНБЮМХЕ, БЯРПЕВЮЧЫЕЕЯЪ ДЮФЕ Б ЙНДЮУ ТХПЛЕММНИ ОНДДЕПФЙХ аот МЮ ПЮГКХВМШУ СЯЙНПХРЕКЪУ, ОПХБНДХР Й РНЛС, ВРН ОПЕХЛСЫЕЯРБЮ аот Я ОНПЪДЙНЛ БЕЙРНПЮ, ПЮБМШЛ ЯРЕОЕМХ ДБНИЙХ, Б ХГБЕЯРМНИ ЯРЕОЕМХ ЯМХФЮЧРЯЪ ХГ-ГЮ РНЦН, ВРН РПХЦНМНЛЕРПХВЕЯЙХЕ ТСМЙЖХХ БШВХЯКЪЧРЯЪ МЮ ЙЮФДНЛ ЬЮЦЕ Х ОНРНЛС МЕХГАЕФМН СБЕКХВХБЮЧР ЙНЩТТХЖХЕМРШ ЙНКХВЕЯРБЮ НОЕПЮЖХИ ОПХ ЦКЮБМНЛ ВКЕМЕ (N log₂ N). лЕФДС РЕЛ, ОПЕДБЮПХРЕКЭМНЕ ОПЕДБШВХЯКЕМХЕ БЯЕИ МСФМНИ ДКЪ дот РПХЦНМНЛЕРПХХ ДЮ╦Р БНГЛНФМНЯРЭ БШОНКМХРЭ РПХЦНМНЛЕРПХЧ ГЮ O(N) НОЕПЮЖХИ, ОПХВ╦Л ДЮФЕ ЩРН ОПЕДБШВХЯКЕМХЕ ЛНФЕР АШРЭ Б НЯМНБМНЛ ГЮМЪРН МЕ БШГНБЮЛХ РПХЦНМНЛЕРПХВЕЯЙХУ ТСМЙЖХИ, Ю ЙНЛОКЕЙЯМШЛХ СЛМНФЕМХЪЛХ, ЙЮЙ УНРЪ АШ Б ОПХЛЕПЕ ОПНЦПЮЛЛШ, ХЯОНКЭГСЧЫЕИ ТНПЛСКШ ОПХБЕДЕМХЪ ДКЪ ПЮГАХБЮМХЪ БЯЕЦН ДХЮОЮГНМЮ МЮ 16 ВЮЯРЕИ.

рЮЙФЕ БШГШБЮЕР ЯНФЮКЕМХЕ ДПСЦНЕ - ПЕДЙНЕ ³ ХЯОНКЭГНБЮМХЕ ПЮГПЮАНРВХЙЮЛХ ДКЪ ЯНБПЕЛЕММШУ ОЮПЮККЕКЭМШУ БШВХЯКХРЕКЭМШУ ЯХЯРЕЛ ОПЕХЛСЫЕЯРБ В╦РМНИ (Ю РЮЙФЕ ЙПЮРМНИ РПНИЙЕ Х ВЕРБ╦ПЙЕ) ЯРЕОЕМХ ДБНИЙХ. яУЕЛШ ОПХ ЩРНЛ ОНКСВЮЧРЯЪ ЯКНФМЕЕ, МН НМХ МЕ ДЮЧР МЮЛ "УНКНЯРШУ" БЕРБЕИ Х ПЮГАХЕМХИ ПЮГМНИ ПЮГЛЕПМНЯРХ. оНЩРНЛС ПЮГПЮАНРВХЙЮЛ, ФЕКЮЧЫХЛ НОРХЛХГХПНБЮРЭ аот ДКЪ ЯРЕОЕМЕИ ДБНИЙХ, ЯНБЕРСЕЛ НАПЮЫЮРЭ БМХЛЮМХЕ МЮ ЩРС БНГЛНФМНЯРЭ.

³ пЕДЙНЕ - МЕ РН ЯКНБН. мЮЛ РЮЙХЕ ПЕЮКХГЮЖХХ ОПНЯРН МЕ БЯРПЕВЮКХЯЭ.