Жылдам Фурье түрлендіру алгоритмдеріндегі «көбелек» схемалары
Butterfly diagram
Жылдам Фурье түрлендіру (FFT) алгоритмдеріндегі "көбелек" схемасы – бұл DFT нәтижелерін біріктіретін немесе бөлетін есептеу бөлігі. Cooley-Tukey алгоритмінде маңызды.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
FFT алгоритмдеріндегі көбелек диаграммалар
butterfly diagrams in FFT algorithms
Жылдам Фурье түрлендіру алгоритмдерінде көбелек – кіші дискретті Фурье түрлендірулерінің (DFT) нәтижелерін үлкен DFT-ге біріктіретін есептеу бөлігі немесе керісінше (үлкен DFT-ді кіші түрлендірулерге бөлу) болып табылады. "Көбелек" атауы радикс 2 жағдайындағы дерек ағыны диаграммасының пішінінен шыққан, осы туралы төменде сипатталған. Бұл терминнің басылымда алғаш рет 1969 жылы MIT техникалық есебінде кездескен деп есептеледі. Осындай құрылымды жасырын күйлердің ең мүмкін тізбегін анықтауға қолданылатын Витерби алгоритмінде де табуға болады. Көбінесе "көбелек" термині Кули-Туки FFT алгоритмі аясында қолданылады, ол композиттік өлшемі n = rm DFT-ді рекурсивті түрде r өлшемді m кіші түрлендіруге бөледі, мұнда r – түрлендірудің "радикс"і. Бұл кіші DFT-лер r өлшемді көбелектер арқылы біріктіріледі, олардың өзі r өлшемді DFT-лер (кіші түрлендірулердің сәйкес нәтижелері бойынша m рет орындалады) және бірлік түбірлерімен (бұрылыс факторлары деп аталады) көбейтіледі. (Бұл "уақыт бойынша азайту" жағдайы; сондай-ақ "жиілік бойынша азайту" деп аталатын кері қадамдарды орындауға болады, онда көбелектер бірінші болып келеді және бұрылыс факторларымен көбейтіледі. Сондай-ақ Кули-Туки FFT мақаласын қараңыз.)
In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms). The name "butterfly" comes from the shape of the data flow diagram in the radix 2 case, as described below. The earliest occurrence in print of the term is thought to be in a 1969 MIT technical report. The same structure can also be found in the Viterbi algorithm, used for finding the most likely sequence of hidden states. Most commonly, the term "butterfly" appears in the context of the Cooley–Tukey FFT algorithm, which recursively breaks down a DFT of composite size n = rm into r smaller transforms of size m where r is the "radix" of the transform. These smaller DFTs are then combined via size r butterflies, which themselves are DFTs of size r (performed m times on corresponding outputs of the sub transforms) pre multiplied by roots of unity (known as twiddle factors). (This is the "decimation in time" case; one can also perform the steps in reverse, known as "decimation in frequency", where the butterflies come first and are post multiplied by twiddle factors. See also the Cooley–Tukey FFT article.)
Басқа қолданыстар
Көбелек әдісі ішінара кездейсоқ сандардың үлкен массивтерінің кездейсоқтығын жақсарту үшін де қолданылуы мүмкін. Бұл үшін, қалаулы хеш алгоритмі арқылы әрбір 32 немесе 64 биттік сөзді басқа барлық сөздермен себеп-салдар байланысына келтіріп, массивтегі кез келген бір биттің өзгеруі барлық биттерге әсер ету мүмкіндігін қамтамасыз ету керек.
The butterfly can also be used to improve the randomness of large arrays of partially random numbers, by bringing every 32 or 64 bit word into causal contact with every other word through a desired hashing algorithm, so that a change in any one bit has the possibility of changing all the bits in the large array.