Көбелектер диаграммасы - Butterfly diagram

Сигнал-ағын графигі кірістерді қосу х (сол жақта) шығысқа ж оларға байланысты (оң жақта) radix-2 Cooley-Tukey FFT радиалының «көбелегі» қадамы үшін. Бұл диаграмма а көбелек (сияқты морфо көбелегі салыстыру үшін көрсетілген), демек, кейбір елдерде ол сағаттық диаграмма деп те аталады, дегенмен атау.

Контекстінде жылдам Фурье түрлендіруі алгоритмдер, а көбелек кішірек нәтижелерді біріктіретін есептеу бөлігі дискретті Фурье түрлендірулері (DFT) үлкен DFT-ге, немесе керісінше (үлкен DFT-ні субтрансформаға бөлу). «Көбелек» атауы төменде сипатталғандай radix-2 жағдайындағы мәліметтер ағынының диаграммасы формасынан шыққан.[1] Терминнің басылымында ең ерте пайда болуы 1969 ж. Деп есептеледі MIT техникалық есеп.[2][3] Дәл осындай құрылымды Viterbi алгоритмі, жасырын күйлердің ықтимал ретін табу үшін қолданылады.

Көбінесе «көбелек» термині контексте пайда болады Cooley – Tukey FFT алгоритмі, бұл рекурсивті DFT бұзады құрама өлшемі n = rm ішіне р өлшемнің кішігірім түрлендірулері м қайда р түрлендірудің «радиусы» болып табылады. Осы кішігірім DFT өлшемдер арқылы біріктіріледір көбелектер, олар өздері өлшемді DFT болып табылады р (орындалды м қосалқы түрлендірулердің сәйкес нәтижелеріндегі уақыт) алдын-ала көбейтіледі бірліктің тамыры (белгілі твит факторлары ). (Бұл «уақыт бойынша бөлшектеу» жағдайы; көбінесе көбелектер бірінші болып келетін және оларды орамал факторларымен көбейтетін «жиіліктегі декимация» деп аталатын қадамдарды керісінше орындауға болады. Кули-Туки ФФТ мақала.)

Радикс-2 көбелегінің сызбасы

Radix-2 Cooley-Tukey алгоритмі жағдайында көбелек жай екі өлшемді қабылдайтын өлшемі-2 болатын DFT болып табылады (х0х1) (екі кіші түрлендірудің сәйкес нәтижелері) және екі нәтижені береді (ж0ж1) формула бойынша (ескерілмеген) твит факторлары ):

Егер осы амалдар жұбы үшін мәліметтер ағынының сызбасын салатын болса, (х0х1) дейін (ж0ж1) сызықтар қиылысады және а-ның қанаттарына ұқсайды көбелек, демек, атау (оң жақтағы суретті қараңыз).

Уақытында бөлінетін радикс-2 FFT ұзындығын бұзады -N DFT екі ұзындыққаN/ 2 DFT, содан кейін көптеген көбелектер операцияларынан тұратын біріктіру кезеңі.

Нақтырақ айтсақ, radix-2 деформациясы уақытында FFT алгоритмі қосулы n = 2 б примитивке қатысты мәліметтер n-бірліктің тамыры O-ға (n журнал2 n) формадағы көбелектер:

қайда к - есептелетін түрлендіру бөлігіне байланысты бүтін сан. Ал сәйкесінше кері түрлендіруді математикалық тәсілмен ауыстыру арқылы жүзеге асыруға болады ω бірге ω−1 (және, мүмкін, нормалану конвенциясына байланысты жалпы масштабты коэффициентке көбейту), көбелектерді тікелей төңкеруге болады:

жиіліктегі FFT алгоритміне сәйкес келеді.

Басқа мақсаттар

Сондай-ақ, көбелек ішінара кездейсоқ сандардың үлкен жиілігін кездейсоқтықты жақсарту үшін қолданыла алады, әр 32 немесе 64 биттік сөздерді қалаған хэштеу алгоритмі арқылы барлық басқа сөздермен себептік байланысқа келтіреді, осылайша кез келген бір биттің өзгеруі мүмкін. массивтің барлық биттерін өзгерту.[4]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Алан В. Оппенгейм, Рональд В. Шафер және Джон Р. Бак, Дискретті-уақыттық сигналды өңдеу, 2-ші басылым (Жоғарғы седла өзені, NJ: Prentice Hall, 1989)
  2. ^ C. J. Weinstein (1969-11-21). Сандық сүзгілердегі кванттау әсері (Есеп). MIT Линкольн зертханасы. б. 42. Алынған 2015-02-10. «Көбелек» деп аталатын бұл есептеу
  3. ^ Cipra, Барри А. (2012-06-04). «FFT және көбелектер диаграммасы». mathoverflow.net. Алынған 2015-02-10.
  4. ^ *Press, WH; Теукольский, SA; Веттерлинг, ВТ; Flannery, BP (2007), «7.2-бөлім. Үлкен массивті толығымен хэштеу», Сандық рецепттер: ғылыми есептеу өнері (3-ші басылым), Нью-Йорк: Кембридж университетінің баспасы, ISBN  978-0-521-88068-8

Сыртқы сілтемелер