¡¡Ä̾ï FFT ¤Ï¡¤Î¥»¶ Fourier ÊÑ´¹¤ò¹â®¤Ë¹Ô¤¦µ»Ë¡¤Ç¤¹¡¥¤³¤Î Î¥»¶ Fourier ÊÑ´¹¤ÏÄ̾ï¤Î Fourier ÊÑ´¹¤È¤Ï°Û¤Ê¤ê¡¤¾¯¤·ÊʤΤ¢¤ë ÊÑ´¹¤Ç¤¹¡¥FFT ¤ò°ÂÁ´¤ËÍøÍѤ¹¤ë¤¿¤á¤Ë¤Ï¤Þ¤º¡¤Î¥»¶ Fourier ÊÑ´¹¤Î À¼Á¤òÃΤäƤ¤¤Ê¤±¤ì¤Ð¤Ê¤ê¤Þ¤»¤ó¡¥
¡¡Î¥»¶ Fourier ÊÑ´¹ - Discrete Fourier Transform ¤Ï¡¤ Ä̾ï¤Î Fourier ÊÑ´¹¤Î̵¸Â¶è´ÖÀÑʬ¤ò͸¤ÎϤǽñ¤´¹¤¨¤¿¤â¤Î¤Ç¡¤ »þ´ÖÎΰ衤¼þÇÈ¿ôÎΰè¤È¤â¤ËÎ¥»¶²½¤µ¤ì¤¿ Fourier ÊÑ´¹¤Î¤³¤È¤Ç¤¹¡¥ °ø¤ß¤Ë¡¤Fourier µé¿ôŸ³«¤Ï¡¤¼þÇÈ¿ôÎΰè¤Ç¤Î¤ßÎ¥»¶²½¤µ¤ì¤¿ÊÑ´¹¤Ë ÁêÅö¤·¤Þ¤¹¡¥
¡¡¤³¤³¤Ç¤Ï°Ê¸å¡¤»þ´ÖÎΰè¤ÎÎ¥»¶¥Ç¡¼¥¿ (£á_0, £á_1, ..., £á_N-1) ¤«¤é ¼þÇÈ¿ôÎÎ°è¤Ø¤ÎÎ¥»¶¥Ç¡¼¥¿ (£Á_0, £Á_1, ..., £Á_N-1) ¤Ø¤Î Ťµ N ¤Î DFT ¤ò
¡¡ ¡¡ N-1¡¡¡¡ ¡¡ jk¡¡ ¡¡ ¡¡ ¡¡ -2¦Ði / N £Á ¡á ¦² £á £× ¡¤ £× ¡á £å ¡¡ ¡¡k ¡¡ j=0¡¡¡¡j ¡¡N ¡¡ ¡¡N ¡¡ ¡¡ ¡¡
¤ÇÄêµÁ¤·¤Þ¤¹¡¥¤³¤ÎÊÑ´¹¤ÎµÕÊÑ´¹¤Ï
¡¡ ¡¡ 1 N-1¡¡¡¡ ¡¡-jk £á ¡á --- ¦² £Á £× ¡¡k ¡¡ N j=0¡¡¡¡j ¡¡N
¤È¤Ê¤ê¤Þ¤¹¡¥
¡¡DFT ¤ÎÄêµÁ¤Ï¡¤½ñʪ¤Ë¤è¤Ã¤Æ°Û¤Ê¤ë¤Î¤ÇÃí°Õ¤·¤Æ¤¯¤À¤µ¤¤¡¥ ¾¯¤·Ä´¤Ù¤¿¸Â¤ê¤Ç¤Ï¡¤µ¬³Ê²½Äê¿ô (1/N, sqrt(1/N)) ¤ÎÉÕ¤±Êý¤È¡¤ »Ø¿ô´Ø¿ô¤ÎÉ乿¤Î¤È¤êÊý¤Ï¡¤¹Í¤¨¤é¤ì¤ë¤¹¤Ù¤Æ¤ÎÁȹ礻¤¬¤¢¤ê¤Þ¤·¤¿¡¥ FFT ¤Î»ÈÍѤǤο¤¯¤Î¥È¥é¥Ö¥ë¤Ï¤³¤Î¤³¤È¤Ëµ¯°ø¤·¤Æ¤¤¤ë¤è¤¦¤Ç¤¹¡¥
¡¡°ìÈ̤ˡ¤DFT ¤Ç¤Ï¡¤Éé¤Î¼þÇÈ¿ô¥Ç¡¼¥¿ £Á_-k ¤ä¡¤Åº»ú¤¬ N ¤è¤êÂ礤¤ ¥Ç¡¼¥¿¤Ï½ü³°¤µ¤ì¤Þ¤¹¡¥¤Ê¤¼¤Ê¤é¤Ð¡¤£×^N = 1 ¤È¤¤¤¦¼þ´üÀ¤«¤é¡¤ Éé¤Î¼þÇÈ¿ô¥Ç¡¼¥¿ £Á_-k ¤Ï £Á_N-k ¤Ë°ìÃפ·¡¤£Á_N+k ¤Ï £Á_k ¤Ë °ìÃפ¹¤ë¤Î¤Ç¡¤Ï¢Â³¤Ê N ¸Ä¤Î¥Ç¡¼¥¿¤µ¤¨¤¢¤ì¤Ð¡¤¤¢¤È¤Ï¼þ´üŪ¤Ë ³ÈÄ¥¤Ç¤¤ë¤«¤é¤Ç¤¹¡¥¤½¤Î¤³¤È¤«¤é¡¤Éé¤Î°ú¿ô¤Î¥Ç¡¼¥¿¤ò°·¤¦¾ì¹ç¤Ë¡¤ DFT ¤ÎÄêµÁ¤È¤·¤Æ¡¤¥Ç¡¼¥¿¤Îź»ú¤ò 0 ¤«¤é N-1 ¤Ç¤Ï¤Ê¤¯¡¤ -N/2 ¤«¤é N/2-1 ¤Þ¤Ç¤È¤¹¤ë¤³¤È¤¬¤è¤¯¤¢¤ê¤Þ¤¹¡¥¤³¤Î¾ì¹ç¡¤ ¥Ç¡¼¥¿¤òŬÅö¤ËʤÙÂØ¤¨¤ë(¤¢¤ë¤¤¤ÏÉ乿¤òÉÕ¤±ÊѤ¨¤ë)¤³¤È¤¬ ɬÍפˤʤê¤Þ¤¹¡¥
¡¡¤Þ¤¿¡¤ÂоÎÀ¤ò¤è¤¯¤¹¤ë¤¿¤á¤Ë¡¤DFT ¤ò¼¡¤Î¤è¤¦¤Ë³ÈÄ¥¤¹¤ë¤³¤È¤¬ ¤¢¤ê¤Þ¤¹¡¥
¡¡ ¡¡ N-1¡¡¡¡ ¡¡(j+¦Ä1)(k+¦Ä2) £Á ¡á ¦² £á £× ¡¡ ¡¡ ¡¡k ¡¡ j=0¡¡¡¡j ¡¡N ¡¡ ¡¡
Äê¿ô ¦Ä1, ¦Ä2, ¤Ï¡¤ÊÒÊý¤ò 1/2 ¤Ë¤¹¤ë¤³¤È¤¬Â¿¤¯¡¤¤³¤ì¤Ï¡¤Odd DFT ¤È ¤¤¤ï¤ì¤ë¤â¤Î¤Ç¤¹¡¥¤³¤Î³ÈÄ¥ DFT ¤Ï¡¤Ä̾ï¤Î DFT ¤ÎÊÑ´¹Á°¤ÈÊÑ´¹¸å¤Î ¥Ç¡¼¥¿¤ËŬÅö¤Ê·¸¿ô¤ò³Ý¤±¤¿¤â¤Î¤Ë¤¹¤®¤Ê¤¤¤Î¤Ç¤¹¤¬¡¤¼ÂÂÐ¾Î¤Ê ¥Ç¡¼¥¿¤Ê¤É¤ÎÊÑ´¹¡ÊÎ¥»¶¥³¥µ¥¤¥óÊÑ´¹¤Ê¤É¡Ë¤Ç¤Ï¡¤¥Ç¡¼¥¿¤ÎÂоÎÀ¤¬¤è¤¯¤Ê¤ê¡¤ FFT ¥¢¥ë¥´¥ê¥º¥à¤¬Ä¾ÀÜŬÍѤǤ¤ë¤è¤¦¤Ë¤Ê¤ê¤Þ¤¹¡¥
¡¡DFT ¤ò¼ÂºÝ¤Ë±þÍѤ¹¤ë¤È¤¤ËÃí°Õ¤·¤Ê¤±¤ì¤Ð¤¤¤±¤Ê¤¤¤³¤È¤¬¤¢¤ê¤Þ¤¹¡¥ ¤½¤ì¤Ï¡¤DFT ¤ÈÉáÄ̤ΠFourier ÊÑ´¹¤È¤Ï»÷¤¿À¼Á¤Ï¤¢¤ë¤¬¡¤°Û¤Ê¤ë¤â¤Î ¤Ç¤¢¤ë¤È¤¤¤¦¤³¤È¤Ç¤¹¡¥°ã¤¤¤Î°ì¤Ä¤Ï¡¤DFT ¤ÏÎ¥»¶Åª¤À¤È¤¤¤¦¤³¤È¤Ç¤¹¡¥ Ϣ³¤Ê´Ø¿ô¤Î Fourier ÊÑ´¹¤òÎ¥»¶Åª¤Ê DFT ¤Ç¶á»÷¤¹¤ë¤È¤¡¤Î¥»¶²½¸íº¹¤¬ ȯÀ¸¤·¤Þ¤¹¡¥°ìÈ̤ˡ¤m ³¬Èùʬ¤¬Í¸Â¤Ê´Ø¿ô¤òÎ¥»¶²½¤¹¤ë¤È¡¤Ã±°Ì¶è´Ö¤Î ¥Ç¡¼¥¿¿ô N ¤ËÂФ·¤Æ¡¤DFT ¤ÎÎ¥»¶²½¸íº¹¤Ï¡¤¤Û¤Ü N^{-m-1} ¤ËÈæÎ㤷¤¿ Â礤µ¤Ë¤Ê¤ê¤Þ¤¹¡¥¤Þ¤¿¡¤Î¥»¶²½¤¹¤ë´Ø¿ô¤¬Ìµ¸Â³¬Èùʬ²Äǽ¤Ç¡¤¤¢¤ë¾ò·ï¤ò Ëþ¤¿¤¹¤Ê¤é¤Ð¡¤Î¥»¶²½¸íº¹¤Ï¥Ç¡¼¥¿¿ô N ¤ËÂФ·¤Æ e^{-C N} ¤È¤Ê¤ê¡¤N ¤ò ¾¯¤·Â礤¯¤¹¤ë¤È»Ø¿ô´Ø¿ôŪ¤ËµÞ·ã¤Ë¸º¾¯¤·¤Þ¤¹¡¥¤µ¤é¤Ë¡¤Î¥»¶²½¤¹¤ë ´Ø¿ô¤¬À°´Ø¿ô¤Ç¡¤¤½¤Î Fourier ÊÑ´¹¤Î¼þÇÈ¿ôÀ®Ê¬¤¬ £æmax °Ê¾å¤ò´Þ¤Þ¤Ê¤¤ ¤Ê¤é¤Ð¡¤Ã±°Ì¶è´Ö¤Î¥Ç¡¼¥¿¿ô N ¤ò 2£æmax °Ê¾å¤Ë¤¹¤ì¤Ð¡¤Î¥»¶²½¸íº¹¤Ï ´°Á´¤Ë¥¼¥í¤Ë¤Ê¤ê¤Þ¤¹(¤¤¤ï¤æ¤ëɸËܲ½ÄêÍý)¡¥Íפ¹¤ë¤Ë¡¤´Ø¿ô¤¬½½Ê¬³ê¤é¤«¤Ç ¤¢¤ì¤Ð¡¤É¸ËÜ¿ô¤ò¿¤¯¤¹¤ì¤ÐÎ¥»¶²½¸íº¹¤Ï½½Ê¬¾®¤µ¤¯¤Ê¤ë¤È¤¤¤¦¤³¤È¤Ç¤¹¡¥ ¤â¤·¡¤´Ø¿ô¤¬³ê¤é¤«¤Ç¤Ê¤¯ÉÔϢ³¤Ê¾ì¹ç¤Ï¡¤¤¤¤¯¤é N ¤òÂ礤¯¤·¤Æ¤â ¤Û¤È¤ó¤É¶á»÷¤Ï¤è¤¯¤Ê¤é¤º¡¤ÉáÄ̤ΠFourier ÊÑ´¹¤È DFT ¤È¤Ï¤Þ¤Ã¤¿¤¯ ÊÌʪ¤Ë¤Ê¤Ã¤Æ¤·¤Þ¤¤¤Þ¤¹[»²¹Íʸ¸¥]¡¥
¡¡DFT ¤È Fourier ÊÑ´¹¤È¤Î¤â¤¦°ì¤Ä¤Î°ã¤¤¤Ï¡¤Ä̾ï¤Î Fourier ÊÑ´¹¤Ï ̵¸Â¶è´Ö¤ÎÀÑʬ¤Ê¤Î¤ËÂФ·¤Æ DFT ¤Ï͸¶è´Ö¤À¤È¤¤¤¦¤³¤È¤Ç¤¹¡¥ Ä̾ï¤Î Fourier ÊÑ´¹¤ò DFT ¤ÇÃÖ¤´¹¤¨¤ë¾ì¹ç¡¤ÀÑʬ¤ò͸¤ÇÂǤÁÀÚ¤é ¤Ê¤±¤ì¤Ð¤Ê¤é¤º¡¤ÅöÁ³¸íº¹(ÂǤÁÀÚ¤ê¸íº¹)¤¬È¯À¸¤·¤Þ¤¹¡¥¤µ¤é¤Ë¡¤ DFT ¤ÏÎ¥»¶Åª¤Ê´Ø¿ô¤Î Fourier µé¿ôŸ³«¤ËÁêÅö¤¹¤ë¤Î¤Ç¡¤DFT ¤µ¤ì¤ë´Ø¿ô¤Ï ñ¤Ê¤ëŤµ N ¤Î´Ø¿ô¤Ç¤Ï¤Ê¤¯¡¤¼þ´üŪ¤Ë³ÈÄ¥¤µ¤ì¤¿´Ø¿ô¤È¤ß¤Ê¤µ¤ì¤Þ¤¹¡¥ DFT ¤ò»È¤Ã¤Æ¼þÇÈ¿ô²òÀϤò¹Ô¤¦¾ì¹ç¡¤Ä¹¤µ N ¤Î¥Ç¡¼¥¿¤Ï¡¤¤³¤Î N ¤Î ¼þ´ü¤Ç̵¸Â¤Ë³¤¯¥Ç¡¼¥¿¤Ë²þ¤¶¤ó¤µ¤ì¤Æ¤·¤Þ¤¤¤Þ¤¹¡¥¤³¤Î¼þ´üŪ¤Ë³ÈÄ¥ ¤µ¤ì¤¿´Ø¿ô¤Ï°ìÈ̤ˡ¤¤Ä¤Ê¤®ÌܤÇÉÔϢ³¤È¤Ê¤ë¤¿¤á¡¤DFT ¤Ë¤Ï Â礤ÊÎ¥»¶²½¸íº¹¤¬È¯À¸¤·¤Þ¤¹¡¥¤³¤ÎÌäÂê¤Ï¡¤Áë´Ø¿ô¤ò³Ý¤±¤¿¤ê¤¹¤ë¤Ê¤É¤Î ¥Ç¡¼¥¿¤ò³ê¤é¤«¤Ê¼þ´ü´Ø¿ô¤Ë¤¹¤ëÁàºî¤ÇÂçÉý¤Ë²þÁ±¤Ç¤¤Þ¤¹¡¥¤Þ¤¿¡¤ ÂǤÁÀÚ¤ê¸íº¹¤Ï¡¤ÊÑ´¹¤¹¤ë´Ø¿ô¤¬¸º¾¯´Ø¿ô¤Ê¤é¤Ð¡¤¶è´Ö¤ÎŤµ¤ò½½Ê¬¤Ë Â礤¯¤È¤ë¤³¤È¤Ç¾®¤µ¤¯¤Ç¤¤Þ¤¹¡¥¤â¤·¡¤´Ø¿ô¤ÎÀ¼Á¤¬¤ï¤«¤Ã¤Æ¤¤¤ì¤Ð¡¤ DFT ¤òÊݸ¤¹¤ë¤è¤¦¤ÊÀþ·Á¤Î²Ã®ˡ¤¬»È¤¨¤ë¾ì¹ç¤â¤¢¤ê¤Þ¤¹¡¥
¡¡Î¥»¶²½¤Î´Êñ¤Ê¶ñÂÎÎã¤ò¼¡¤Ë¼¨¤·¤Þ¤¹¡¥Ä̾ï¤Î Fourier ÊÑ´¹
¡¡ ¡¡ ¡¡ 1¡¡ -¡ç ¡¡ ¡¡-i¦Øx £Æ(¦Ø) ¡á ---¡¡¢é £æ(x) £å ¡¡ dx ¡¡ ¡¡ ¡¡ 2¦Ð ¡ç ¡¡ ¡¡ ¡¡
¤òÀÑʬ¶è´Ö ¡ÞT ¤ÇÂǤÁÀڤꡤŤµ N ¤Î DFT ¤ÇÎ¥»¶²½¤¹¤ë¤È
¡Á ¡¡¡¡¡¡¡¡ ¡¡ ¦¤x k N-1¡¡¡¡ ¡¡ ¡¡¡¡ ¡¡ jk £Æ(¦¤¦Ø¡¦£ë) ¡á ---¡¡(-1) ¦² £æ(-T + ¦¤x¡¦£ê) £× ¡¡ ¡¡¡¡¡¡¡¡ ¡¡ 2¦Ð j=0¡¡¡¡ ¡¡ ¡¡¡¡ ¡¡N ¡¡ ¡¡ ¡¡ -2¦Ði / N ¡¡ ¡¡ 2T ¡¡ ¡¡¡¡ ¦Ð £× ¡á £å ¡¡ ¡¤ ¦¤x = ---- ¡¤ ¦¤¦Ø = ----¡¡ ¡¡N ¡¡ ¡¡ ¡¡ ¡¡ ¡¡ N ¡¡ ¡¡¡¡ T¡¡
¤È¤Ê¤ê¤Þ¤¹¡¥Î¥»¶Åª¤Ê¶á»÷´Ø¿ô £Æ¡Á() ¤Ë¤ÏÎ¥»¶²½¸íº¹¤ÈÂǤÁÀÚ¤ê¸íº¹¤ÎξÊý¤¬ ´Þ¤Þ¤ì¤Þ¤¹¡¥¤µ¤é¤ËÃí°Õ¤·¤Ê¤±¤ì¤Ð¤¤¤±¤Ê¤¤¤Î¤Ï¡¤£Æ¡Á(¦Ø) ¤Ï¼þ´ü ¦ÐN/T ¤Î ¼þ´ü´Ø¿ô¤Ë¤Ê¤ë¤È¤¤¤¦¤³¤È¤Ç¤¹¡¥¤·¤¿¤¬¤Ã¤Æ¡¤£Æ¡Á(¦¤¦Ø¡¦£ë) ¤Ç¤ÎÎ¥»¶¤Î ´Ö³Ö ¦¤¦Ø ¤Ï¼«Æ°Åª¤Ë ¦Ð/T ¤È¤Ê¤ê¡¤¶á»÷¤È¤·¤ÆÍ¸ú¤Ê ¦Ø ¤ÎÈϰϤϰì¼þ´üʬ ¤Î¤ß¤Ç -¦ÐN/(2T) ¤«¤é +¦ÐN/(2T) ¤È¤¤¤¦¤³¤È¤Ë¤Ê¤ê¤Þ¤¹¡¥¤³¤Î¤³¤È¤«¤é¡¤ Î¥»¶Éý¤ÏǤ°Õ¤Ë¤ÏÁª¤Ù¤º¡¤¤¤¤ï¤æ¤ëÉÔ³ÎÄêÀ´Ø·¸¤È¤¤¤¦¤â¤Î¤¬Â¸ºß¤·¤Þ¤¹¡¥ ¼þÇÈ¿ô¤ÎÎ¥»¶Éý ¦¤¦Ø ¤È»þ´ÖÉý T ¤ÎÀѤϾï¤Ë ¦Ð ¤È¤Ê¤ê¡¤»þ´Ö¤ÎÎ¥»¶Éý ¦¤x ¤È ͸ú¤Ê¼þÇÈ¿ôÉý ¦ÐN/(2T) ¤ÎÀѤâ¾ï¤Ë ¦Ð ¤È¤Ê¤ê¤Þ¤¹¡¥Íפ¹¤ë¤Ë¡¤DFT ¤Ç¤Ïû¤¤ »þ´Ö¤Î¥Ç¡¼¥¿¤ÇºÙ¤«¤¤¼þÇÈ¿ô¤Îʬ²òǽ¤ò½Ð¤¹¤Î¤ÏÉÔ²Äǽ¤Ç¡¤»þ´ÖÉý¤«¼þÇÈ¿ô¤Î ʬ²òǽ¤Î¤É¤Á¤é¤«¤òµ¾À·¤Ë¤·¤Ê¤±¤ì¤Ð¤¤¤±¤Ê¤¤¤È¤¤¤¦¤³¤È¤Ç¤¹¡¥
¡¡¤³¤³¤Ç¤ÎÎ¥»¶ Fourier ÊÑ´¹¤Ï¡¤Ê£ÁÇ¿ô¥Ç¡¼¥¿¤«¤éÊ£ÁÇ¿ô¥Ç¡¼¥¿¤Ø¤Î ÊÑ´¹¤Ç¤¹¡¥¤·¤«¤·¡¤¼ÂºÝ¤Î±þÍѤǤϡ¤¼Â¿ô¤Î¥Ç¡¼¥¿¤¬¤Û¤È¤ó¤É¤Ç¤¹¡¥ ¤½¤³¤Ç¡¤¼ÂÎ¥»¶FourierÊÑ´¹/µÕÊÑ´¹¤ÎÀ¼Á¤ò¾¯¤·¤À¤±¹Í¤¨¤Æ¤ß¤Þ¤¹¡¥ ¤â¤·¡¤£á_j ¤¬¼Â¿ô¤Ê¤é¤Ð¡¤£Á_k ¤ÏÊ£ÁǶ¦ÌòÂоÎ
¡¡ ¡¡ ¡² £Á ¡á £Á ¡¡N-k ¡¡ ¡¡k
¤È¤Ê¤ë¤³¤È¤¬´Êñ¤Ë¤ï¤«¤ë¤È»×¤¤¤Þ¤¹¡¥¤È¤¯¤Ë¡¤£Á_0, £Á_N/2 ¤Ï¼Â¿ô¤Ë ¤Ê¤ê¤Þ¤¹¡¥¤³¤ÎÊÑ´¹¸å¤Î¥Ç¡¼¥¿¤ÏȾʬ¤¬¾éĹ¤Ë¤Ê¤ê¤Þ¤¹¡¥µÕ¤Ë¡¤£á_j ¤¬ Ê£ÁǶ¦ÌòÂоΤʤé¤Ð¡¤£Á_k ¤Ï¼Â¿ô¤È¤Ê¤ê¤Þ¤¹¡¥¤µ¤é¤Ë¡¤£á_j ¤¬¼ÂÂоΠ(£á_j = £á_N-j)¤Ê¤é¤Ð¡¤£Á_k ¤â¼ÂÂоΤȤʤꡤ£á_j ¤¬¼ÂÈ¿ÂоΠ(£á_j = -£á_N-j)¤Ê¤é¤Ð¡¤£Á_k ¤Ï½ãµõ¿ô¤ÇÈ¿ÂоΤȤʤê¤Þ¤¹¡¥¤³¤ì¤é¤Ï¡¤ ¥¿¥¤¥×µ¤ÎÎ¥»¶¥³¥µ¥¤¥óÊÑ´¹¡¤Î¥»¶¥µ¥¤¥óÊÑ´¹¤È¤¤¤ï¤ì¤ë¤â¤Î¤Ç¤¹¡¥
Fourier ÊÑ´¹¤ÎÂоÎÀ | |
---|---|
ÊÑ´¹Á° | ÊÑ´¹¸å |
¼Â¿ô | Ê£ÁǶ¦ÌòÂоΠ|
½ãµõ¿ô | Ê£ÁǶ¦ÌòÈ¿ÂоΠ|
Ê£ÁǶ¦ÌòÂоΠ| ¼Â¿ô |
Ê£ÁǶ¦ÌòÈ¿ÂоΠ| ½ãµõ¿ô |
ÂоΠ| ÂоΠ|
È¿ÂоΠ| È¿ÂоΠ|
¼ÂÂоΠ| ¼ÂÂоΠ|
¼ÂÈ¿ÂоΠ| ½ãµõ¿ôÈ¿ÂоΠ|
¤³¤ì¤é¤Î DFT ¤ÎÂоÎÀ¤Ï¡¤Ä̾ï¤Î Fourier ÊÑ´¹¤Ç¤ÎÂоÎÀ¤ÈÁ´¤¯Æ±¤¸¤Ç¤¹¡¥
¡¡DFT ¤Ë´ØÏ¢¤¹¤ë½ÅÍפʱ黻¤Ë¡¤¾ö¤ß¹þ¤ß(Digital Convolution)¤¬¤¢¤ê¤Þ¤¹¡¥ ¤³¤³¤Ç¤Ï¡¤Î¥»¶¥Ç¡¼¥¿ £á_j ¤È £è_j ¤ÎŤµ N ¤Î½ä²ó¾ö¤ß¹þ¤ß¤ò
¡¡ ¡¡ N-1¡¡¡¡ ¡¡ £ù ¡á ¦² £á £è ¡¡k ¡¡ j=0¡¡¡¡j ¡¡k-j
¤Ë¤è¤êÄêµÁ¤·¤Þ¤¹¡¥Ä¾´ÑŪ¤Ë¤Ï¡¤£á_j ¤Ï¿®¹æ¤Ç £è_j ¤Ï¥Õ¥£¥ë¥¿¤Î·¸¿ô¤Ë ÁêÅö¤·¡¤£ù_j ¤Ï¥Õ¥£¥ë¥¿¤µ¤ì¤¿¿®¹æ¤ËÁêÅö¤·¤Þ¤¹¡¥¤³¤³¤Ç¤Î¾ö¤ß¹þ¤ß¤Ï ½ä²ó¤Ç¡¤£á_j ¤È £è_j ¤ÏŤµ N ¤Ç¼þ´üŪ¤Ë³ÈÄ¥¤µ¤ì¤Æ¤¤¤Þ¤¹¡¥Ä̾ï¤Î Fourier ÊÑ´¹¤ÎÀ¼Á¤ÈƱÍͤˡ¤½ä²ó¾ö¤ß¹þ¤ß¤Ï DFT ¤ò¹Ô¤¦¤Èñ¤Ê¤ëÀÑ¤Ë ÊÑ´¹¤µ¤ì¤Þ¤¹¡¥¤¹¤Ê¤ï¤Á¡¤£ù_j ¤Î DFT ¤µ¤ì¤¿¥Ç¡¼¥¿ £Ù_k ¤Ï £á_j, £è_j ¤Î DFT ¤µ¤ì¤¿¥Ç¡¼¥¿ £Á_k, £È_k ¤òÍѤ¤¤Æ
¡¡ ¡¡ ¡¡ ¡¡ £Ù ¡á £Á £È ¡¡k ¡¡ ¡¡k ¡¡k
¤Èɽ¤µ¤ì¤Þ¤¹¡¥¤·¤¿¤¬¤Ã¤Æ¡¤½ä²ó¾ö¤ß¹þ¤ß¤Ï¡¤£Ù_k ¤òµÕ DFT ¤¹¤ì¤Ð·×»»¤Ç ¤¤ë¤³¤È¤Ë¤Ê¤ê¡¤FFT ¤Ë¤è¤ë¹â®»»Ë¡¤¬ÍøÍѤǤ¤Þ¤¹¡¥¤³¤ÎÊýË¡¤Ï¡¤ ½ä²ó¾ö¤ß¹þ¤ß¤ò·×»»¤¹¤ëºÇ¤â¶¯ÎϤÊÊýË¡¤È¤·¤ÆÃΤé¤ì¤Æ¤¤¤Þ¤¹¡¥¤·¤«¤·¡¤ Èæ³ÓŪû¤¤Ä¹¤µ¤Î½ä²ó¾ö¤ß¹þ¤ß¤Î·×»»¤Ë¤Ï¡¤°ì¼¡¸µ¾ö¤ß¹þ¤ß¤ò¤è¤êû¤¤Ä¹¤µ¤Î ¿¼¡¸µ¾ö¤ß¹þ¤ß¤ËÊÑ´¹¤¹¤ëľÀÜ»»Ë¡¤¬Å¬¤·¤Æ¤¤¤ë¾ì¹ç¤¬¤¢¤ê¤Þ¤¹¡¥¤³¤ÎÊýË¡¤Ï¡¤ ¸å¤Ë¼¨¤¹ Prime Factor ·¿ FFT ¤Îź»ú¤ÎÊÑ´¹¤Ç¼Â¸½¤Ç¤¤Þ¤¹ [»²¹Íʸ¸¥]¡¥