Transformation de Fourier rapide

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="fr" dir="ltr"> <head> <meta charset="UTF-8"> <title>Transformation de Fourier rapide — Wikipédia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )frwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy","wgMonthNames":["","janvier","février","mars","avril","mai","juin","juillet","août","septembre","octobre","novembre","décembre"],"wgRequestId":"07fa2dca-5c19-4453-a490-3f9247178981","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Transformation_de_Fourier_rapide","wgTitle":"Transformation de Fourier rapide","wgCurRevisionId":223976180,"wgRevisionId":223976180,"wgArticleId":15688,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Article contenant un appel à traduction en anglais","Portail:Mathématiques/Articles liés","Portail:Sciences/Articles liés","Projet:Mathématiques/Articles","Portail:Informatique théorique/Articles liés","Portail:Informatique/Articles liés","Théorie de Fourier","Algorithme numérique","Transformée du signal"],"wgPageViewLanguage":"fr","wgPageContentLanguage":"fr","wgPageContentModel":"wikitext","wgRelevantPageName":"Transformation_de_Fourier_rapide","wgRelevantArticleId":15688,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"fr","pageLanguageDir":"ltr","pageVariantFallbacks":"fr"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q623950","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGELevelingUpEnabledForUser":false}; RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ArchiveLinks","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=fr&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.21"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Transformation de Fourier rapide — Wikipédia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//fr.m.wikipedia.org/wiki/Transformation_de_Fourier_rapide"> <link rel="alternate" type="application/x-wiki" title="Modifier" href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipédia (fr)"> <link rel="EditURI" type="application/rsd+xml" href="//fr.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://fr.wikipedia.org/wiki/Transformation_de_Fourier_rapide"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr"> <link rel="alternate" type="application/atom+xml" title="Flux Atom de Wikipédia" href="/w/index.php?title=Sp%C3%A9cial:Modifications_r%C3%A9centes&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Transformation_de_Fourier_rapide rootpage-Transformation_de_Fourier_rapide skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Aller au contenu</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Menu principal" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Menu principal" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Menu principal</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Menu principal</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">masquer</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_principal" title="Accueil général [z]" accesskey="z"><span>Page d’accueil</span></a></li><li id="n-thema" class="mw-list-item"><a href="/wiki/Portail:Accueil" title="Regroupements d'articles par thématiques"><span>Portails thématiques</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Page_au_hasard" title="Affiche un article au hasard [x]" accesskey="x"><span>Article au hasard</span></a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Contact" title="Qui contacter"><span>Contact</span></a></li> </ul> </div> </div> <div id="p-Contribuer" class="vector-menu mw-portlet mw-portlet-Contribuer" > <div class="vector-menu-heading"> Contribuer </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-aboutwp" class="mw-list-item"><a href="/wiki/Aide:D%C3%A9buter" title="Guide pour apprendre à contribuer à Wikipédia"><span>Débuter sur Wikipédia</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Aide:Accueil" title="Accès à l’aide"><span>Aide</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_de_la_communaut%C3%A9" title="À propos du projet, ce que vous pouvez faire, où trouver les informations"><span>Communauté</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_sp%C3%A9ciales" title="Outils pour contribuer à Wikipédia"><span>Pages spéciales</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Modifications_r%C3%A9centes" title="Liste des modifications récentes sur le wiki [r]" accesskey="r"><span>Modifications récentes</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Wikip%C3%A9dia:Accueil_principal" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipédia" src="/static/images/mobile/copyright/wikipedia-wordmark-fr.svg" style="width: 7.4375em; height: 1.125em;"> <img class="mw-logo-tagline" alt="l'encyclopédie libre" src="/static/images/mobile/copyright/wikipedia-tagline-fr.svg" width="120" height="13" style="width: 7.5em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Sp%C3%A9cial:Recherche" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Rechercher sur Wikipédia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Rechercher</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Rechercher sur Wikipédia" aria-label="Rechercher sur Wikipédia" autocapitalize="sentences" title="Rechercher sur Wikipédia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Spécial:Recherche"> </div> <button class="cdx-button cdx-search-input__end-button">Rechercher</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Outils personnels"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Apparence"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Modifier l'apparence de la taille, de la largeur et de la couleur de la police de la page" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Apparence" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Apparence</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=fr.wikipedia.org&uselang=fr" class=""><span>Faire un don</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Transformation+de+Fourier+rapide" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire." class=""><span>Créer un compte</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Transformation+de+Fourier+rapide" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o" class=""><span>Se connecter</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Plus d’options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Outils personnels" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Outils personnels</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu utilisateur" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=fr.wikipedia.org&uselang=fr"><span>Faire un don</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Transformation+de+Fourier+rapide" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire."><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Créer un compte</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Transformation+de+Fourier+rapide" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Se connecter</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages pour les contributeurs déconnectés <a href="/wiki/Aide:Premiers_pas" aria-label="En savoir plus sur la contribution"><span>en savoir plus</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_contributions" title="Une liste des modifications effectuées depuis cette adresse IP [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_discussions" title="La page de discussion pour les contributions depuis cette adresse IP [n]" accesskey="n"><span>Discussion</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Sommaire" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Sommaire</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">masquer</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">Début</div> </a> </li> <li id="toc-Histoire" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Histoire"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Histoire</span> </div> </a> <ul id="toc-Histoire-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Formulation_mathématique" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Formulation_mathématique"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Formulation mathématique</span> </div> </a> <ul id="toc-Formulation_mathématique-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Algorithme_de_Cooley-Tukey" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Algorithme_de_Cooley-Tukey"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Algorithme de Cooley-Tukey</span> </div> </a> <button aria-controls="toc-Algorithme_de_Cooley-Tukey-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Algorithme de Cooley-Tukey</span> </button> <ul id="toc-Algorithme_de_Cooley-Tukey-sublist" class="vector-toc-list"> <li id="toc-Détail_d'un_cas_classique_:_'"`UNIQ--postMath-0000001B-QINU`"'" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Détail_d'un_cas_classique_:_'"`UNIQ--postMath-0000001B-QINU`"'"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Détail d'un cas classique : '"`UNIQ--postMath-0000001B-QINU`"'</span> </div> </a> <ul id="toc-Détail_d'un_cas_classique_:_'"`UNIQ--postMath-0000001B-QINU`"'-sublist" class="vector-toc-list"> <li id="toc-Principe_de_l'algorithme" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Principe_de_l'algorithme"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1.1</span> <span>Principe de l'algorithme</span> </div> </a> <ul id="toc-Principe_de_l'algorithme-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Pseudo-code" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Pseudo-code"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1.2</span> <span>Pseudo-code</span> </div> </a> <ul id="toc-Pseudo-code-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Schéma_explicatif" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Schéma_explicatif"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1.3</span> <span>Schéma explicatif</span> </div> </a> <ul id="toc-Schéma_explicatif-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Autres_algorithmes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Autres_algorithmes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Autres algorithmes</span> </div> </a> <ul id="toc-Autres_algorithmes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Algorithmes_spécialisés_dans_le_traitement_de_données_réelles_ou/et_symétriques" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Algorithmes_spécialisés_dans_le_traitement_de_données_réelles_ou/et_symétriques"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Algorithmes spécialisés dans le traitement de données réelles ou/et symétriques</span> </div> </a> <ul id="toc-Algorithmes_spécialisés_dans_le_traitement_de_données_réelles_ou/et_symétriques-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Problèmes_numériques_et_approximations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Problèmes_numériques_et_approximations"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Problèmes numériques et approximations</span> </div> </a> <ul id="toc-Problèmes_numériques_et_approximations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Exemple_d'application_:_la_multiplication_de_polynômes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Exemple_d'application_:_la_multiplication_de_polynômes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Exemple d'application : la multiplication de polynômes</span> </div> </a> <ul id="toc-Exemple_d'application_:_la_multiplication_de_polynômes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes_et_références" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes_et_références"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Notes et références</span> </div> </a> <ul id="toc-Notes_et_références-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Voir_aussi" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Voir_aussi"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>Voir aussi</span> </div> </a> <button aria-controls="toc-Voir_aussi-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Voir aussi</span> </button> <ul id="toc-Voir_aussi-sublist" class="vector-toc-list"> <li id="toc-Bibliographie" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bibliographie"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.1</span> <span>Bibliographie</span> </div> </a> <ul id="toc-Bibliographie-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Articles_connexes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Articles_connexes"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.2</span> <span>Articles connexes</span> </div> </a> <ul id="toc-Articles_connexes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Vidéographie" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Vidéographie"> <div class="vector-toc-text"> <span class="vector-toc-numb">9.3</span> <span>Vidéographie</span> </div> </a> <ul id="toc-Vidéographie-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Sommaire" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table des matières" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Basculer la table des matières" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Basculer la table des matières</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Transformation de Fourier rapide</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Aller à un article dans une autre langue. Disponible en 29 langues." > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-29" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">29 langues</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%AA%D8%AD%D9%88%D9%8A%D9%84_%D9%81%D9%88%D8%B1%D9%8A%D9%8A%D9%87_%D8%A7%D9%84%D8%B3%D8%B1%D9%8A%D8%B9" title="تحويل فورييه السريع – arabe" lang="ar" hreflang="ar" data-title="تحويل فورييه السريع" data-language-autonym="العربية" data-language-local-name="arabe" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/S%C3%BCr%C9%99tli_Furye_%C3%A7evirm%C9%99si" title="Sürətli Furye çevirməsi – azerbaïdjanais" lang="az" hreflang="az" data-title="Sürətli Furye çevirməsi" data-language-autonym="Azərbaycanca" data-language-local-name="azerbaïdjanais" class="interlanguage-link-target"><span>Azərbaycanca</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Transformada_r%C3%A0pida_de_Fourier" title="Transformada ràpida de Fourier – catalan" lang="ca" hreflang="ca" data-title="Transformada ràpida de Fourier" data-language-autonym="Català" data-language-local-name="catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Rychl%C3%A1_Fourierova_transformace" title="Rychlá Fourierova transformace – tchèque" lang="cs" hreflang="cs" data-title="Rychlá Fourierova transformace" data-language-autonym="Čeština" data-language-local-name="tchèque" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Fast_Fourier_Transform" title="Fast Fourier Transform – danois" lang="da" hreflang="da" data-title="Fast Fourier Transform" data-language-autonym="Dansk" data-language-local-name="danois" class="interlanguage-link-target"><span>Dansk</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Schnelle_Fourier-Transformation" title="Schnelle Fourier-Transformation – allemand" lang="de" hreflang="de" data-title="Schnelle Fourier-Transformation" data-language-autonym="Deutsch" data-language-local-name="allemand" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Fast_Fourier_transform" title="Fast Fourier transform – anglais" lang="en" hreflang="en" data-title="Fast Fourier transform" data-language-autonym="English" data-language-local-name="anglais" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Transformada_r%C3%A1pida_de_Fourier" title="Transformada rápida de Fourier – espagnol" lang="es" hreflang="es" data-title="Transformada rápida de Fourier" data-language-autonym="Español" data-language-local-name="espagnol" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Fourier%27_kiirteisendus" title="Fourier' kiirteisendus – estonien" lang="et" hreflang="et" data-title="Fourier' kiirteisendus" data-language-autonym="Eesti" data-language-local-name="estonien" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%A8%D8%AF%DB%8C%D9%84_%D9%81%D9%88%D8%B1%DB%8C%D9%87_%D8%B3%D8%B1%DB%8C%D8%B9" title="تبدیل فوریه سریع – persan" lang="fa" hreflang="fa" data-title="تبدیل فوریه سریع" data-language-autonym="فارسی" data-language-local-name="persan" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%94%D7%AA%D7%9E%D7%A8%D7%AA_%D7%A4%D7%95%D7%A8%D7%99%D7%99%D7%94_%D7%9E%D7%94%D7%99%D7%A8%D7%94" title="התמרת פורייה מהירה – hébreu" lang="he" hreflang="he" data-title="התמרת פורייה מהירה" data-language-autonym="עברית" data-language-local-name="hébreu" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-hi mw-list-item"><a href="https://hi.wikipedia.org/wiki/%E0%A4%A4%E0%A5%8D%E0%A4%B5%E0%A4%B0%E0%A4%BF%E0%A4%A4_%E0%A4%AB%E0%A5%81%E0%A4%B0%E0%A4%BF%E0%A4%85%E0%A4%B0_%E0%A4%B0%E0%A5%82%E0%A4%AA%E0%A4%BE%E0%A4%A8%E0%A5%8D%E0%A4%A4%E0%A4%B0" title="त्वरित फुरिअर रूपान्तर – hindi" lang="hi" hreflang="hi" data-title="त्वरित फुरिअर रूपान्तर" data-language-autonym="हिन्दी" data-language-local-name="hindi" class="interlanguage-link-target"><span>हिन्दी</span></a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Transformasi_Fourier_cepat" title="Transformasi Fourier cepat – indonésien" lang="id" hreflang="id" data-title="Transformasi Fourier cepat" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonésien" class="interlanguage-link-target"><span>Bahasa Indonesia</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Trasformata_di_Fourier_veloce" title="Trasformata di Fourier veloce – italien" lang="it" hreflang="it" data-title="Trasformata di Fourier veloce" data-language-autonym="Italiano" data-language-local-name="italien" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B" title="高速フーリエ変換 – japonais" lang="ja" hreflang="ja" data-title="高速フーリエ変換" data-language-autonym="日本語" data-language-local-name="japonais" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%ED%91%B8%EB%A6%AC%EC%97%90_%EB%B3%80%ED%99%98" title="고속 푸리에 변환 – coréen" lang="ko" hreflang="ko" data-title="고속 푸리에 변환" data-language-autonym="한국어" data-language-local-name="coréen" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Fast_Fourier_transform" title="Fast Fourier transform – néerlandais" lang="nl" hreflang="nl" data-title="Fast Fourier transform" data-language-autonym="Nederlands" data-language-local-name="néerlandais" class="interlanguage-link-target"><span>Nederlands</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Szybka_transformacja_Fouriera" title="Szybka transformacja Fouriera – polonais" lang="pl" hreflang="pl" data-title="Szybka transformacja Fouriera" data-language-autonym="Polski" data-language-local-name="polonais" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Transformada_r%C3%A1pida_de_Fourier" title="Transformada rápida de Fourier – portugais" lang="pt" hreflang="pt" data-title="Transformada rápida de Fourier" data-language-autonym="Português" data-language-local-name="portugais" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5" title="Быстрое преобразование Фурье – russe" lang="ru" hreflang="ru" data-title="Быстрое преобразование Фурье" data-language-autonym="Русский" data-language-local-name="russe" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Brza_furijeova_transformacija" title="Brza furijeova transformacija – serbo-croate" lang="sh" hreflang="sh" data-title="Brza furijeova transformacija" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="serbo-croate" class="interlanguage-link-target"><span>Srpskohrvatski / српскохрватски</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%91%D1%80%D0%B7%D0%B0_%D0%A4%D1%83%D1%80%D0%B8%D1%98%D0%B5%D0%BE%D0%B2%D0%B0_%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D1%98%D0%B0" title="Брза Фуријеова трансформација – serbe" lang="sr" hreflang="sr" data-title="Брза Фуријеова трансформација" data-language-autonym="Српски / srpski" data-language-local-name="serbe" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Snabb_fouriertransform" title="Snabb fouriertransform – suédois" lang="sv" hreflang="sv" data-title="Snabb fouriertransform" data-language-autonym="Svenska" data-language-local-name="suédois" class="interlanguage-link-target"><span>Svenska</span></a></li><li class="interlanguage-link interwiki-ta mw-list-item"><a href="https://ta.wikipedia.org/wiki/%E0%AE%B5%E0%AE%BF%E0%AE%B0%E0%AF%88%E0%AE%B5%E0%AF%81_%E0%AE%83%E0%AE%AA%E0%AF%82%E0%AE%B0%E0%AE%BF%E0%AE%AF%E0%AF%87_%E0%AE%89%E0%AE%B0%E0%AF%81%E0%AE%AE%E0%AE%BE%E0%AE%B1%E0%AF%8D%E0%AE%B1%E0%AE%AE%E0%AF%8D" title="விரைவு ஃபூரியே உருமாற்றம் – tamoul" lang="ta" hreflang="ta" data-title="விரைவு ஃபூரியே உருமாற்றம்" data-language-autonym="தமிழ்" data-language-local-name="tamoul" class="interlanguage-link-target"><span>தமிழ்</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/H%C4%B1zl%C4%B1_Fourier_d%C3%B6n%C3%BC%C5%9F%C3%BCm%C3%BC" title="Hızlı Fourier dönüşümü – turc" lang="tr" hreflang="tr" data-title="Hızlı Fourier dönüşümü" data-language-autonym="Türkçe" data-language-local-name="turc" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%A8%D0%B2%D0%B8%D0%B4%D0%BA%D0%B5_%D0%BF%D0%B5%D1%80%D0%B5%D1%82%D0%B2%D0%BE%D1%80%D0%B5%D0%BD%D0%BD%D1%8F_%D0%A4%D1%83%D1%80%27%D1%94" title="Швидке перетворення Фур'є – ukrainien" lang="uk" hreflang="uk" data-title="Швидке перетворення Фур'є" data-language-autonym="Українська" data-language-local-name="ukrainien" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Bi%E1%BA%BFn_%C4%91%E1%BB%95i_Fourier_nhanh" title="Biến đổi Fourier nhanh – vietnamien" lang="vi" hreflang="vi" data-title="Biến đổi Fourier nhanh" data-language-autonym="Tiếng Việt" data-language-local-name="vietnamien" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2" title="快速傅里叶变换 – chinois" lang="zh" hreflang="zh" data-title="快速傅里叶变换" data-language-autonym="中文" data-language-local-name="chinois" class="interlanguage-link-target"><span>中文</span></a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E5%82%85%E7%AB%8B%E8%91%89%E8%AE%8A%E6%8F%9B" title="快速傅立葉變換 – cantonais" lang="yue" hreflang="yue" data-title="快速傅立葉變換" data-language-autonym="粵語" data-language-local-name="cantonais" class="interlanguage-link-target"><span>粵語</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623950#sitelinks-wikipedia" title="Modifier les liens interlangues" class="wbc-editpage">Modifier les liens</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Espaces de noms"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Transformation_de_Fourier_rapide" title="Voir le contenu de la page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discussion:Transformation_de_Fourier_rapide" rel="discussion" title="Discussion au sujet de cette page de contenu [t]" accesskey="t"><span>Discussion</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Modifier la variante de langue" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">français</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Affichages"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Transformation_de_Fourier_rapide"><span>Lire</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=history" title="Historique des versions de cette page [h]" accesskey="h"><span>Voir l’historique</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Outils" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Outils</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Outils</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">masquer</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Plus d’options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Transformation_de_Fourier_rapide"><span>Lire</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=history"><span>Voir l’historique</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Général </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_li%C3%A9es/Transformation_de_Fourier_rapide" title="Liste des pages liées qui pointent sur celle-ci [j]" accesskey="j"><span>Pages liées</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Suivi_des_liens/Transformation_de_Fourier_rapide" rel="nofollow" title="Liste des modifications récentes des pages appelées par celle-ci [k]" accesskey="k"><span>Suivi des pages liées</span></a></li><li id="t-upload" class="mw-list-item"><a href="//fr.wikipedia.org/wiki/Aide:Importer_un_fichier" title="Téléverser des fichiers [u]" accesskey="u"><span>Téléverser un fichier</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&oldid=223976180" title="Adresse permanente de cette version de cette page"><span>Lien permanent</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=info" title="Davantage d’informations sur cette page"><span>Informations sur la page</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Citer&page=Transformation_de_Fourier_rapide&id=223976180&wpFormIdentifier=titleform" title="Informations sur la manière de citer cette page"><span>Citer cette page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:UrlShortener&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FTransformation_de_Fourier_rapide"><span>Obtenir l'URL raccourcie</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:QrCode&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FTransformation_de_Fourier_rapide"><span>Télécharger le code QR</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Imprimer / exporter </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Livre&bookcmd=book_creator&referer=Transformation+de+Fourier+rapide"><span>Créer un livre</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:DownloadAsPdf&page=Transformation_de_Fourier_rapide&action=show-download-screen"><span>Télécharger comme PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Transformation_de_Fourier_rapide&printable=yes" title="Version imprimable de cette page [p]" accesskey="p"><span>Version imprimable</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> Dans d’autres projets </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:FFT" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q623950" title="Lien vers l’élément dans le dépôt de données connecté [g]" accesskey="g"><span>Élément Wikidata</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Apparence"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Apparence</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">masquer</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">Un article de Wikipédia, l'encyclopédie libre.</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="fr" dir="ltr"><div class="bandeau-container metadata homonymie hatnote"><div class="bandeau-cell bandeau-icone" style="display:table-cell;padding-right:0.5em"><span class="noviewer" typeof="mw:File"><a href="/wiki/Aide:Homonymie" title="Aide:Homonymie"><img alt="Page d’aide sur l’homonymie" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png" decoding="async" width="20" height="15" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/30px-Logo_disambig.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/40px-Logo_disambig.svg.png 2x" data-file-width="512" data-file-height="375" /></a></span></div><div class="bandeau-cell" style="display:table-cell;padding-right:0.5em"> <p>Pour les articles homonymes, voir <a href="/wiki/FFT" class="mw-disambig" title="FFT">FFT</a>. </p> </div></div> <p>La <b>transformation de Fourier rapide</b> (sigle anglais : <i>FFT</i> ou <i><span class="lang-en" lang="en">fast Fourier transform</span></i>) est un <a href="/wiki/Algorithmique" title="Algorithmique">algorithme</a> de calcul de la <a href="/wiki/Transformation_de_Fourier_discr%C3%A8te" title="Transformation de Fourier discrète">transformation de Fourier discrète</a> (TFD). </p><p>Sa <a href="/wiki/Complexit%C3%A9_en_temps" title="Complexité en temps">complexité</a> varie en <a href="/wiki/Comparaison_asymptotique#Domination" title="Comparaison asymptotique">O(<i>n</i> log <i>n</i>)</a> avec le nombre <i>n</i> de points, alors que la complexité de l’<a href="/wiki/Transformation_de_Fourier_discr%C3%A8te" title="Transformation de Fourier discrète">algorithme « naïf »</a> s'exprime en O(<i>n</i><sup>2</sup>). Ainsi, pour <i>n</i> = 1 024, le temps de calcul de l'algorithme rapide peut être 100 fois plus court que le calcul utilisant la formule de définition de la TFD. </p><p>C'est en <a href="/wiki/1965_en_science" title="1965 en science">1965</a> que <a href="/wiki/James_Cooley" title="James Cooley">James Cooley</a> et <a href="/wiki/John_Tukey" title="John Tukey">John Tukey</a> publient l’article qui « lance » définitivement l'adoption massive de cette méthode en <a href="/wiki/Traitement_du_signal" title="Traitement du signal">traitement du signal</a> et dans les <a href="/wiki/T%C3%A9l%C3%A9communications" title="Télécommunications">télécommunications</a>. On a découvert par la suite que l'algorithme avait déjà été imaginé par <a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Carl Friedrich Gauss</a> en <a href="/wiki/1805" title="1805">1805</a>, et adapté à plusieurs reprises (notamment par <a href="/wiki/Cornelius_Lanczos" title="Cornelius Lanczos">Lanczos</a> en 1942) sous des formes différentes. L'algorithme a aussi été découvert indépendamment par le chanoine <a href="/wiki/Georges_Lema%C3%AEtre" title="Georges Lemaître">Lemaître</a><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>. </p><p>Cet algorithme est couramment utilisé en <a href="/wiki/Traitement_num%C3%A9rique_du_signal" title="Traitement numérique du signal">traitement numérique du signal</a> pour transformer des données discrètes du domaine temporel dans le <a href="/wiki/Domaine_fr%C3%A9quentiel" title="Domaine fréquentiel">domaine fréquentiel</a>, en particulier dans les oscilloscopes numériques (les analyseurs de spectre utilisant plutôt des filtres analogiques, plus précis). Son efficacité permet de réaliser des filtrages en modifiant le spectre et en utilisant la transformation inverse (<a href="/wiki/Filtre_%C3%A0_r%C3%A9ponse_impulsionnelle_finie" title="Filtre à réponse impulsionnelle finie">filtre à réponse impulsionnelle finie</a>). Il est également à la base des <a href="/wiki/Algorithme_de_Sch%C3%B6nhage-Strassen" title="Algorithme de Schönhage-Strassen">algorithmes de multiplication rapide</a> (<a href="/wiki/Arnold_Sch%C3%B6nhage" title="Arnold Schönhage">Schönhage</a> et <a href="/wiki/Volker_Strassen" title="Volker Strassen">Strassen</a>, 1971), et des techniques de <a href="/wiki/Compression_d%27image" title="Compression d'image">compression numérique</a> ayant mené au format d'image <a href="/wiki/JPEG" title="JPEG">JPEG</a> (1991). </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Histoire">Histoire</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=1" title="Modifier la section : Histoire" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=1" title="Modifier le code source de la section : Histoire"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Le développement d'algorithmes rapides pour la FFT remonte au travail non publié de <a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Carl Friedrich Gauss</a> en 1805, alors qu'il en avait besoin pour interpoler l'orbite des astéroïdes <a href="/wiki/(2)_Pallas" title="(2) Pallas">Pallas</a> et <a href="/wiki/(3)_Junon" title="(3) Junon">Junon</a> à partir d'observations d'échantillons. Sa méthode était très similaire à celle publiée en 1965 par James Cooley et John Tukey, à qui l'on attribue généralement l'invention de l'algorithme générique moderne de la FFT. Bien que les travaux de Gauss soient antérieurs aux résultats de <a href="/wiki/Joseph_Fourier" title="Joseph Fourier">Joseph Fourier</a> en 1822, il n'a pas analysé le temps de calcul et a finalement utilisé d'autres méthodes pour atteindre son objectif. </p><p>Entre 1805 et 1965, certaines versions de la FFT ont été publiées par d'autres auteurs. En 1932, <a href="/wiki/Frank_Yates" title="Frank Yates">Frank Yates</a> a publié sa version, qui permettait un calcul efficace des <a href="/wiki/Transform%C3%A9e_de_Hadamard" title="Transformée de Hadamard">transformées de Hadamard</a> et de <a href="/wiki/Transform%C3%A9e_de_Walsh" title="Transformée de Walsh">Walsh</a>. L'algorithme de Yates est toujours utilisé dans le domaine de la conception statistique et de l'analyse des expériences. En 1942, <a href="/w/index.php?title=G._C._Danielson&action=edit&redlink=1" class="new" title="G. C. Danielson (page inexistante)">G. C. Danielson</a> et Cornelius Lanczos ont publié leur version permettant de calculer la FFT pour la <a href="/wiki/Cristallographie_aux_rayons_X" title="Cristallographie aux rayons X">cristallographie aux rayons X</a>, un domaine où le calcul des transformées de Fourier présentait un formidable goulot d'étranglement. Dans le passé, de nombreuses méthodes s'étaient concentrées sur la réduction de la constante <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.355ex; height:2.176ex;" alt="{\displaystyle \lambda }" /></span> pour laquelle le nombre d'opérations était équivalent à <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda n^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>λ</mi> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda n^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f2a1d00960056ab3f611734039ebe20b2811c99" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.804ex; height:2.676ex;" alt="{\displaystyle \lambda n^{2}}" /></span> en tirant parti des "symétries". Mais Danielson et Lanczos ont réalisé que l'on pouvait utiliser la "périodicité" pour réduire encore cette constante, bien que, comme Gauss, ils n'aient pas analysé que cela conduisait à un algorithme en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85994022c28e938772bd858cd8281328643e8b3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.54ex; height:2.843ex;" alt="{\displaystyle O(n\log(n))}" /></span>. </p><p>James Cooley et John Tukey ont redécouvert de manière indépendante ces algorithmes antérieurs et ont publié en 1965 une version plus générale de la FFT applicable lorsque <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" /></span> est composite et pas nécessairement une puissance de 2, ainsi qu'une analyse de complexité en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85994022c28e938772bd858cd8281328643e8b3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.54ex; height:2.843ex;" alt="{\displaystyle O(n\log(n))}" /></span>. Tukey a eu cette idée lors d'une réunion du comité consultatif scientifique du président <a href="/wiki/John_Fitzgerald_Kennedy" title="John Fitzgerald Kennedy">Kennedy</a>, où l'on discutait de la détection des essais nucléaires de l'<a href="/wiki/Union_des_r%C3%A9publiques_socialistes_sovi%C3%A9tiques" title="Union des républiques socialistes soviétiques">Union soviétique</a> en installant des capteurs pour encercler le pays de l'extérieur. Les essais nucléaires avaient en effet lieu sous terre<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>, et la seule manière de les détecter était d'utiliser une transformée de Fourier. En discutant avec Tukey, <a href="/wiki/Richard_Garwin" title="Richard Garwin">Richard Garwin</a> a reconnu l'applicabilité générale de l'algorithme non seulement aux problèmes de sécurité nationale, mais aussi à un large éventail de problèmes, dont un qui l'intéressait immédiatement, à savoir la détermination des périodicités des orientations du spin dans un cristal tridimensionnel d'<a href="/wiki/H%C3%A9lium_3" title="Hélium 3">hélium 3</a><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>. Comme Tukey ne travaillait pas chez <a href="/wiki/IBM" title="IBM">IBM</a>, la brevetabilité de l'idée a été mise en doute et l'algorithme est tombé dans le domaine public, ce qui, grâce à la révolution informatique de la décennie suivante, a fait de la FFT l'un des algorithmes indispensables du traitement numérique du signal. </p> <div class="mw-heading mw-heading2"><h2 id="Formulation_mathématique"><span id="Formulation_math.C3.A9matique"></span>Formulation mathématique</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=2" title="Modifier la section : Formulation mathématique" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=2" title="Modifier le code source de la section : Formulation mathématique"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Soit <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{0},\dots ,\lambda _{n-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{0},\dots ,\lambda _{n-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87b9a52bc575f0ca5aadb8b8a741638232371559" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.262ex; height:2.509ex;" alt="{\displaystyle \lambda _{0},\dots ,\lambda _{n-1}}" /></span>des <a href="/wiki/Nombre_complexe" title="Nombre complexe">nombres complexes</a>. La <a href="/wiki/Transform%C3%A9e_de_Fourier_discr%C3%A8te" class="mw-redirect" title="Transformée de Fourier discrète">transformée de Fourier discrète</a> de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda _{0},\dots ,\lambda _{n-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lambda _{0},\dots ,\lambda _{n-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87b9a52bc575f0ca5aadb8b8a741638232371559" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.262ex; height:2.509ex;" alt="{\displaystyle \lambda _{0},\dots ,\lambda _{n-1}}" /></span> est définie par la formule suivante : <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle TFD(j)=\sum _{k=0}^{n-1}\lambda _{k}\mathrm {e} ^{-{\frac {2\mathrm {i} jk\pi }{n}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mi>F</mi> <mi>D</mi> <mo stretchy="false">(</mo> <mi>j</mi> <mo stretchy="false">)</mo> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">e</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">i</mi> </mrow> <mi>j</mi> <mi>k</mi> <mi>π</mi> </mrow> <mi>n</mi> </mfrac> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle TFD(j)=\sum _{k=0}^{n-1}\lambda _{k}\mathrm {e} ^{-{\frac {2\mathrm {i} jk\pi }{n}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/43dd199856131059e46dcb4e7764368288fa49df" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:23.781ex; height:7.509ex;" alt="{\displaystyle TFD(j)=\sum _{k=0}^{n-1}\lambda _{k}\mathrm {e} ^{-{\frac {2\mathrm {i} jk\pi }{n}}}}" /></span> </p><p>pour <i>j</i> = 0, ... , <i>n</i> –1. De manière équivalente, soit <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e681afbcd4457e5fd79d74b999d958345eff132" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:14.115ex; height:7.509ex;" alt="{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}" /></span> un polynôme à coefficients <a href="/wiki/Nombre_complexe" title="Nombre complexe">complexes</a>. La <a href="/wiki/Transform%C3%A9e_de_Fourier_discr%C3%A8te" class="mw-redirect" title="Transformée de Fourier discrète">transformée de Fourier discrète</a> de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" /></span> est définie par la formule suivante : </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (P(\omega ^{j}))_{0\leq j\leq n-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msup> <mo stretchy="false">)</mo> <msub> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> <mo>≤</mo> <mi>j</mi> <mo>≤</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (P(\omega ^{j}))_{0\leq j\leq n-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4be855997889e5470e02060151dd5b7fa12788dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.095ex; height:3.343ex;" alt="{\displaystyle (P(\omega ^{j}))_{0\leq j\leq n-1}}" /></span>, où <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega =\mathrm {e} ^{-{\frac {2\mathrm {i} \pi }{n}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ω</mi> <mo>=</mo> <msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">e</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">i</mi> </mrow> <mi>π</mi> </mrow> <mi>n</mi> </mfrac> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \omega =\mathrm {e} ^{-{\frac {2\mathrm {i} \pi }{n}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f6e9781200312aaabd17caa5ba92152444ec1387" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.727ex; height:3.343ex;" alt="{\displaystyle \omega =\mathrm {e} ^{-{\frac {2\mathrm {i} \pi }{n}}}}" /></span></dd></dl> <p>ou en notation matricielle : </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{l}{\begin{pmatrix}f_{0}\\f_{1}\\f_{2}\\\vdots \\f_{n-1}\end{pmatrix}}={\begin{pmatrix}1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\cdots &\omega ^{n-1}\\1&\omega ^{2}&\omega ^{4}&\cdots &\omega ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots &\\1&\omega ^{n-1}&\omega ^{2(n-1)}&\cdots &\omega ^{(n-1)^{2}}\end{pmatrix}}\end{array}}{\begin{pmatrix}\lambda _{0}\\\lambda _{1}\\\lambda _{2}\\\vdots \\\lambda _{n-1}\end{pmatrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="left" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <mo>⋮</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>⋯</mo> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mi>ω</mi> </mtd> <mtd> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mtd> <mtd> <mo>⋯</mo> </mtd> <mtd> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mtd> <mtd> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msup> </mtd> <mtd> <mo>⋯</mo> </mtd> <mtd> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> </mtd> </mtr> <mtr> <mtd> <mo>⋮</mo> </mtd> <mtd> <mo>⋮</mo> </mtd> <mtd> <mo>⋮</mo> </mtd> <mtd> <mo>⋱</mo> </mtd> <mtd> <mo>⋮</mo> </mtd> <mtd></mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> </mtd> <mtd> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> </mtd> <mtd> <mo>⋯</mo> </mtd> <mtd> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mrow> </msup> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> </mtable> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <mo>⋮</mo> </mtd> </mtr> <mtr> <mtd> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{array}{l}{\begin{pmatrix}f_{0}\\f_{1}\\f_{2}\\\vdots \\f_{n-1}\end{pmatrix}}={\begin{pmatrix}1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\cdots &\omega ^{n-1}\\1&\omega ^{2}&\omega ^{4}&\cdots &\omega ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots &\\1&\omega ^{n-1}&\omega ^{2(n-1)}&\cdots &\omega ^{(n-1)^{2}}\end{pmatrix}}\end{array}}{\begin{pmatrix}\lambda _{0}\\\lambda _{1}\\\lambda _{2}\\\vdots \\\lambda _{n-1}\end{pmatrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/665de11c25d7929ac68a04c459009a019447cd0a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.671ex; width:61.698ex; height:18.509ex;" alt="{\displaystyle {\begin{array}{l}{\begin{pmatrix}f_{0}\\f_{1}\\f_{2}\\\vdots \\f_{n-1}\end{pmatrix}}={\begin{pmatrix}1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\cdots &\omega ^{n-1}\\1&\omega ^{2}&\omega ^{4}&\cdots &\omega ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots &\\1&\omega ^{n-1}&\omega ^{2(n-1)}&\cdots &\omega ^{(n-1)^{2}}\end{pmatrix}}\end{array}}{\begin{pmatrix}\lambda _{0}\\\lambda _{1}\\\lambda _{2}\\\vdots \\\lambda _{n-1}\end{pmatrix}}}" /></span>où l'on reconnaît une <a href="/wiki/Matrice_de_Vandermonde" title="Matrice de Vandermonde">matrice de Vandermonde</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(1,\omega ,...,\omega ^{n-1})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mi>ω</mi> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V(1,\omega ,...,\omega ^{n-1})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6f9b17e9666335fac94b367afa0072bc057ea00c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.173ex; height:3.176ex;" alt="{\displaystyle V(1,\omega ,...,\omega ^{n-1})}" /></span>.</dd></dl> <p>Évaluer naïvement <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" /></span> coûte (<i>n</i> – 1)<sup>2</sup> produits complexes et <i>n</i>(<i>n</i> – 1) sommes complexes alors que seuls <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{2}}\left(\log _{2}(n)-2\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>n</mi> <mn>2</mn> </mfrac> </mrow> <mrow> <mo>(</mo> <mrow> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>−</mo> <mn>2</mn> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {n}{2}}\left(\log _{2}(n)-2\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6aa09fe67447e96f70e652189f5e5ffd2f6b32f8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:15.66ex; height:4.676ex;" alt="{\displaystyle {\frac {n}{2}}\left(\log _{2}(n)-2\right)}" /></span> produits et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\log _{2}(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\log _{2}(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e5333607e44af6161b4c47219053002712a99d3a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.012ex; height:2.843ex;" alt="{\displaystyle n\log _{2}(n)}" /></span> sommes sont nécessaires avec la version rapide. En général, de tels algorithmes dépendent de la <a href="/wiki/D%C3%A9composition_en_produit_de_facteurs_premiers" title="Décomposition en produit de facteurs premiers">factorisation</a> de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" /></span> mais contrairement à une idée répandue, il y a des transformées de Fourier rapides de complexité <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85994022c28e938772bd858cd8281328643e8b3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.54ex; height:2.843ex;" alt="{\displaystyle O(n\log(n))}" /></span> pour tous les <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" /></span>, même pour les nombres premiers. </p><p>Il est possible de générer la transformation inverse de la même manière pour la version rapide. En effet l'inverse de la matrice de Vandermonde <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(1,\omega ,...,\omega ^{n-1})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>V</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mi>ω</mi> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle V(1,\omega ,...,\omega ^{n-1})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6f9b17e9666335fac94b367afa0072bc057ea00c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.173ex; height:3.176ex;" alt="{\displaystyle V(1,\omega ,...,\omega ^{n-1})}" /></span> est simplement <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{n}}V(1,\omega ^{-1},...,\omega ^{-n+1})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>n</mi> </mfrac> </mrow> <mi>V</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{n}}V(1,\omega ^{-1},...,\omega ^{-n+1})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e663bc2ac95b9c3f68a068c3f850bd2d4bcad39c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:23.015ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{n}}V(1,\omega ^{-1},...,\omega ^{-n+1})}" /></span>. Il suffit donc d'appliquer l'algorithme à cet inverse. </p> <div class="mw-heading mw-heading2"><h2 id="Algorithme_de_Cooley-Tukey">Algorithme de Cooley-Tukey</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=3" title="Modifier la section : Algorithme de Cooley-Tukey" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=3" title="Modifier le code source de la section : Algorithme de Cooley-Tukey"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="bandeau-container bandeau-section metadata bandeau-niveau-information"><div class="bandeau-cell bandeau-icone-css loupe">Article détaillé : <a href="/w/index.php?title=Algorithme_FFT_de_Cooley-Tukey&action=edit&redlink=1" class="new" title="Algorithme FFT de Cooley-Tukey (page inexistante)">Algorithme FFT de Cooley-Tukey</a> <a href="https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm" class="extiw" title="en:Cooley–Tukey FFT algorithm"><span class="indicateur-langue" title="Article en anglais : « Cooley–Tukey FFT algorithm »">(en)</span></a>.</div></div> <p>Il s'agit d'un algorithme fréquemment utilisé pour calculer la transformation de Fourier discrète. Il se base sur une approche de type <a href="/wiki/Diviser_pour_r%C3%A9gner_(informatique)" title="Diviser pour régner (informatique)">« diviser pour régner »</a> par le biais d'une <a href="/wiki/Algorithme_r%C3%A9cursif" title="Algorithme récursif">récursion</a>. Celle-ci subdivise une transformation de Fourier discrète d'une taille composite <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=n_{1}n_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n=n_{1}n_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dd591c10fc6b75c202481a0b66a5718b5ecfaea4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.391ex; height:2.009ex;" alt="{\displaystyle n=n_{1}n_{2}}" /></span> en plusieurs transformées de Fourier discrètes de tailles inférieures <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ee784b70e772f55ede5e6e0bdc929994bff63413" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{1}}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/840e456e3058bc0be28e5cf653b170cdbfcc3be4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{2}}" /></span>. Cet algorithme nécessite <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" /></span> multiplications par des racines d'unité, plus communément appelés <i>facteurs de rotation</i>. En général, les mises en code essaient d'éviter une récursion pour des questions de performance. Il est aussi possible de mélanger plusieurs types d'algorithme lors des subdivisions. </p><p>C'est en 1965 que <a href="/wiki/James_Cooley" title="James Cooley">James Cooley</a> et <a href="/wiki/John_Tukey" title="John Tukey">John Tukey</a> publient cette méthode<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup class="reference cite_virgule">,</sup><sup id="cite_ref-Cooley_5-0" class="reference"><a href="#cite_note-Cooley-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> mais il a été découvert par la suite que l'algorithme avait déjà été inventé par <a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Carl Friedrich Gauss</a> en <a href="/wiki/1805" title="1805">1805</a><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> et adapté à plusieurs reprises sous des formes différentes<sup id="cite_ref-Owners_Manual_7-0" class="reference"><a href="#cite_note-Owners_Manual-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>. </p> <div class="mw-heading mw-heading3"><h3 id="Détail_d'un_cas_classique_:_'"`UNIQ--postMath-0000001B-QINU`"'"><span id="D.C3.A9tail_d.27un_cas_classique_:_.7F.27.22.60UNIQ--postMath-0000001B-QINU.60.22.27.7F"></span>Détail d'un cas classique : <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{1}=2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n_{1}=2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3d78e0d9d3fa3ffa0401a62e2be14b009da6e6db" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.71ex; height:2.509ex;" alt="{\displaystyle n_{1}=2}" /></span></h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=4" title="Modifier la section : Détail d'un cas classique : '"`UNIQ--postMath-0000001B-QINU`"'" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=4" title="Modifier le code source de la section : Détail d'un cas classique : '"`UNIQ--postMath-0000001B-QINU`"'"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>L'utilisation la plus classique de l'algorithme de Cooley-Tukey est une division de la transformation en deux parties de taille identique <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n/2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n/2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/95c3931a3fa03cc98cfacd2c49a7ca35b96eaa9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.72ex; height:2.843ex;" alt="{\displaystyle n/2}" /></span> et ceci à chaque étape. Cette contrainte limite les tailles possibles, puisque celles-ci doivent être des puissances de deux. Néanmoins on peut traiter n'importe quel polynôme puisqu'un polynôme de degré <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" /></span> peut être vu comme un polynôme de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {C} _{2^{n}}[X]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </msub> <mo stretchy="false">[</mo> <mi>X</mi> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {C} _{2^{n}}[X]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/906799fc65196f68a78aa9892007c69e56d5d1fa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.971ex; height:2.843ex;" alt="{\displaystyle \mathbb {C} _{2^{n}}[X]}" /></span> où <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\leq 2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>≤</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k\leq 2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/15eaf64472c1caf6226c2a4e7e94dab886a2d122" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.691ex; height:2.509ex;" alt="{\displaystyle k\leq 2^{n}}" /></span>. </p> <div class="mw-heading mw-heading4"><h4 id="Principe_de_l'algorithme"><span id="Principe_de_l.27algorithme"></span>Principe de l'algorithme</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=5" title="Modifier la section : Principe de l'algorithme" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=5" title="Modifier le code source de la section : Principe de l'algorithme"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>On décompose le polynôme <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e681afbcd4457e5fd79d74b999d958345eff132" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:14.115ex; height:7.509ex;" alt="{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}" /></span> en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=P_{pair}(X^{2})+X\cdot P_{impair}(X^{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>=</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>+</mo> <mi>X</mi> <mo>⋅</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P=P_{pair}(X^{2})+X\cdot P_{impair}(X^{2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4aeac9a99ba7c6fea6140d3ac1c7e8a3cfc02952" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:32.534ex; height:3.343ex;" alt="{\displaystyle P=P_{pair}(X^{2})+X\cdot P_{impair}(X^{2})}" /></span>, où <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{pair}=\sum _{k=0}^{\frac {n-1}{2}}\lambda _{2k}X^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> </munderover> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mi>k</mi> </mrow> </msub> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{pair}=\sum _{k=0}^{\frac {n-1}{2}}\lambda _{2k}X^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2050eaa6a0051457e3551a2257d2776b463e672f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:17.922ex; height:8.843ex;" alt="{\displaystyle P_{pair}=\sum _{k=0}^{\frac {n-1}{2}}\lambda _{2k}X^{k}}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{impair}=\sum _{k=0}^{\frac {n-2}{2}}\lambda _{2k+1}X^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> <mn>2</mn> </mfrac> </mrow> </munderover> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{impair}=\sum _{k=0}^{\frac {n-2}{2}}\lambda _{2k+1}X^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d23a5d408c485761c189b547a454c859c0831f59" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:22.033ex; height:8.843ex;" alt="{\displaystyle P_{impair}=\sum _{k=0}^{\frac {n-2}{2}}\lambda _{2k+1}X^{k}}" /></span>. On applique ensuite l'algorithme en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{pair}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{pair}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8045d301cf77da27342b076bcab4bcf4348885c7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.73ex; height:2.843ex;" alt="{\displaystyle P_{pair}}" /></span> et en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{impair}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{impair}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2fc813811bb6ab2c73a3a014fc2f515d495e899" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.74ex; height:2.843ex;" alt="{\displaystyle P_{impair}}" /></span>, pour en déduire l'évaluation de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" /></span> en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega ^{j},0\leq j\leq n-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msup> <mo>,</mo> <mn>0</mn> <mo>≤</mo> <mi>j</mi> <mo>≤</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \omega ^{j},0\leq j\leq n-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5891cbddbae769deb7525daf3732fdb77fc370e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.104ex; height:3.009ex;" alt="{\displaystyle \omega ^{j},0\leq j\leq n-1}" /></span>. </p> <div class="mw-heading mw-heading4"><h4 id="Pseudo-code">Pseudo-code</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=6" title="Modifier la section : Pseudo-code" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=6" title="Modifier le code source de la section : Pseudo-code"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <pre>Entrée : un polynôme <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msub> <mi>λ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e681afbcd4457e5fd79d74b999d958345eff132" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:14.115ex; height:7.509ex;" alt="{\displaystyle P=\sum _{k=0}^{n-1}\lambda _{k}X^{k}}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ω</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \omega }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48eff443f9de7a985bb94ca3bde20813ea737be8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.446ex; height:1.676ex;" alt="{\displaystyle \omega }" /></span> une <a href="/wiki/Racine_primitive_modulo_n" title="Racine primitive modulo n">racine primitive</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" /></span>-ième de l'unité. Sortie : <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(\omega ^{0}),...,P(\omega ^{n-1})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>P</mi> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P(\omega ^{0}),...,P(\omega ^{n-1})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfddca5f545115f59f935d39f7a1df93385845f2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.544ex; height:3.176ex;" alt="{\displaystyle P(\omega ^{0}),...,P(\omega ^{n-1})}" /></span>. <b>fonction</b> FFT(<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P,\omega }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>,</mo> <mi>ω</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P,\omega }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fdaa5a9dc5c017afa7fdac6faf8c4989ac35b116" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.225ex; height:2.509ex;" alt="{\displaystyle P,\omega }" /></span>) : | <b>si</b> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" /></span> est constant : | | <b>retourner <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1fdf0a9cc2b05be736085c7422ebe1d8d019329a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.717ex; height:2.843ex;" alt="{\displaystyle P(1)}" /></span></b> | <b>sinon</b> | | calculer <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{pair}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{pair}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8045d301cf77da27342b076bcab4bcf4348885c7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.73ex; height:2.843ex;" alt="{\displaystyle P_{pair}}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{impair}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{impair}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2fc813811bb6ab2c73a3a014fc2f515d495e899" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.74ex; height:2.843ex;" alt="{\displaystyle P_{impair}}" /></span> | | calculer <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{pair}(\omega ^{0}),P_{pair}(\omega ^{2}),...,P_{pair}(\omega ^{n-2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>,</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{pair}(\omega ^{0}),P_{pair}(\omega ^{2}),...,P_{pair}(\omega ^{n-2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ba8dc5d42559d56f4ce25f954fbed82e0f51d550" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:35.586ex; height:3.343ex;" alt="{\displaystyle P_{pair}(\omega ^{0}),P_{pair}(\omega ^{2}),...,P_{pair}(\omega ^{n-2})}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{impair}(\omega ^{0}),P_{impair}(\omega ^{2}),...,P_{impair}(\omega ^{n-2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>,</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{impair}(\omega ^{0}),P_{impair}(\omega ^{2}),...,P_{impair}(\omega ^{n-2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fc9c55e9f7861bf2e468ba579492bb31ae93a1ba" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:41.617ex; height:3.343ex;" alt="{\displaystyle P_{impair}(\omega ^{0}),P_{impair}(\omega ^{2}),...,P_{impair}(\omega ^{n-2})}" /></span> via FFT(<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{pair},\omega ^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo>,</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{pair},\omega ^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8e3fa22603e5206353829d9b846ef88b21bd7def" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.264ex; height:3.343ex;" alt="{\displaystyle P_{pair},\omega ^{2}}" /></span>) et FFT(<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{impair},\omega ^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo>,</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{impair},\omega ^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aa3de5c5def6ab269d0571afae2ed77478c6dcc6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.274ex; height:3.343ex;" alt="{\displaystyle P_{impair},\omega ^{2}}" /></span>) respectivement | | <b>pour</b> k allant de 0 à n-1 : | | | <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(\omega ^{k})=P_{pair}(\omega ^{2k})+\omega ^{k}\cdot P_{impair}(\omega ^{2k})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> <mo>+</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo>⋅</mo> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P(\omega ^{k})=P_{pair}(\omega ^{2k})+\omega ^{k}\cdot P_{impair}(\omega ^{2k})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5ff821d8e37bcae67a7d91f937c17241a6c6a00c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:38.044ex; height:3.343ex;" alt="{\displaystyle P(\omega ^{k})=P_{pair}(\omega ^{2k})+\omega ^{k}\cdot P_{impair}(\omega ^{2k})}" /></span> | | <b>retourner</b> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(\omega ^{0}),...,P(\omega ^{n-1})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> <mo stretchy="false">)</mo> <mo>,</mo> <mo>.</mo> <mo>.</mo> <mo>.</mo> <mo>,</mo> <mi>P</mi> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P(\omega ^{0}),...,P(\omega ^{n-1})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bfddca5f545115f59f935d39f7a1df93385845f2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.544ex; height:3.176ex;" alt="{\displaystyle P(\omega ^{0}),...,P(\omega ^{n-1})}" /></span> </pre> <p>Cet algorithme a une complexité en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85994022c28e938772bd858cd8281328643e8b3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.54ex; height:2.843ex;" alt="{\displaystyle O(n\log(n))}" /></span>. </p> <div class="mw-heading mw-heading4"><h4 id="Schéma_explicatif"><span id="Sch.C3.A9ma_explicatif"></span>Schéma explicatif</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=7" title="Modifier la section : Schéma explicatif" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=7" title="Modifier le code source de la section : Schéma explicatif"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/Fichier:DIT-FFT-butterfly.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/78/DIT-FFT-butterfly.svg/220px-DIT-FFT-butterfly.svg.png" decoding="async" width="220" height="217" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/78/DIT-FFT-butterfly.svg/330px-DIT-FFT-butterfly.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/78/DIT-FFT-butterfly.svg/440px-DIT-FFT-butterfly.svg.png 2x" data-file-width="302" data-file-height="298" /></a><figcaption>Schéma correspondant à la FFT (DFT en anglais) d'un polynôme de degré 7.</figcaption></figure> <p>Dans le schéma ci-contre, on a représenté la FFT d'un polynôme <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=\sum _{k=0}^{7}x[k]X^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>7</mn> </mrow> </munderover> <mi>x</mi> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> <msup> <mi>X</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P=\sum _{k=0}^{7}x[k]X^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/72864bfd598cbddc44ed65666cdd255141aae4da" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:15.506ex; height:7.509ex;" alt="{\displaystyle P=\sum _{k=0}^{7}x[k]X^{k}}" /></span>. On obtient à la fin des valeurs <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X[k]=P(\omega ^{k})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mi>P</mi> <mo stretchy="false">(</mo> <msup> <mi>ω</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X[k]=P(\omega ^{k})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8e4f525d2bde8d4489fd9204b7c16843aa09585c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.673ex; height:3.176ex;" alt="{\displaystyle X[k]=P(\omega ^{k})}" /></span> Les polynômes intermédiaires obtenus sont <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" /></span> (pour <i>even</i>) et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.773ex; height:2.176ex;" alt="{\displaystyle O}" /></span> (pour <i>odd</i>) qui représentent <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{pair}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{pair}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8045d301cf77da27342b076bcab4bcf4348885c7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.73ex; height:2.843ex;" alt="{\displaystyle P_{pair}}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{impair}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>P</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mi>m</mi> <mi>p</mi> <mi>a</mi> <mi>i</mi> <mi>r</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P_{impair}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2fc813811bb6ab2c73a3a014fc2f515d495e899" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.74ex; height:2.843ex;" alt="{\displaystyle P_{impair}}" /></span><i>.</i> </p><p>On obtiendra ensuite des polynômes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{e}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>e</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E_{e}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ad0071ee83b9d8052de06309324c86f5a8387a40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.714ex; height:2.509ex;" alt="{\displaystyle E_{e}}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{o}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>o</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E_{o}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ef2d4b4edc43606f7089febdbb929bfcc4044ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.745ex; height:2.509ex;" alt="{\displaystyle E_{o}}" /></span> à partir de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" /></span>, ainsi que <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O_{e}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>O</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>e</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O_{e}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c832f32f43758f79d3dd0737d8eefab6a0afdbbb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.772ex; height:2.509ex;" alt="{\displaystyle O_{e}}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O_{o}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>O</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>o</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O_{o}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/56d34f7cb982e87270de247fc0d935b75163d8e7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.803ex; height:2.509ex;" alt="{\displaystyle O_{o}}" /></span> à partir de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d70e1d0d87e2ef1092ea1ffe2923d9933ff18fc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.773ex; height:2.176ex;" alt="{\displaystyle O}" /></span>, et on itérera le procédé. Ainsi <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{e}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>e</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E_{e}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ad0071ee83b9d8052de06309324c86f5a8387a40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.714ex; height:2.509ex;" alt="{\displaystyle E_{e}}" /></span> est formé des coefficients <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[0]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo stretchy="false">[</mo> <mn>0</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x[0]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f1fa8bd2c3dfa6f0cec1039627bd956f8651c14c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.786ex; height:2.843ex;" alt="{\displaystyle x[0]}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[4]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo stretchy="false">[</mo> <mn>4</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x[4]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/482f5588c19926cc426ff3b533f9add835f1e302" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.786ex; height:2.843ex;" alt="{\displaystyle x[4]}" /></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E_{o}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>E</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>o</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E_{o}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ef2d4b4edc43606f7089febdbb929bfcc4044ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.745ex; height:2.509ex;" alt="{\displaystyle E_{o}}" /></span> des coefficients <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[2]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo stretchy="false">[</mo> <mn>2</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x[2]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6e73506a39ff0e1119ac97ee76c57ddc2c68ac57" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.786ex; height:2.843ex;" alt="{\displaystyle x[2]}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[6]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo stretchy="false">[</mo> <mn>6</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x[6]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fd1dd1788f1640870c19b6220d30bfa395499aa6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.786ex; height:2.843ex;" alt="{\displaystyle x[6]}" /></span>, et de même pour les impairs. </p><p>Les flèches vers les valeurs <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X[k]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X[k]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b44d31b5739397a3a3a58892804677840e85bb2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.485ex; height:2.843ex;" alt="{\displaystyle X[k]}" /></span> signifient que la valeur de départ de la flèche influence la valeur de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X[k]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X[k]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b44d31b5739397a3a3a58892804677840e85bb2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.485ex; height:2.843ex;" alt="{\displaystyle X[k]}" /></span> : par exemple la valeur de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X[1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> <mo stretchy="false">[</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X[1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2fa7cd015d3671f178fffe1585fb8d426427e3d5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.436ex; height:2.843ex;" alt="{\displaystyle X[1]}" /></span> dépend de celles de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E[1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>E</mi> <mo stretchy="false">[</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle E[1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9b3f412cfb3e1b6d2e5f94d23a401e1b5eef6dd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.232ex; height:2.843ex;" alt="{\displaystyle E[1]}" /></span> et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O[1]}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">[</mo> <mn>1</mn> <mo stretchy="false">]</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O[1]}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f6993594c93b2106b10fd08958b5902fb5b1e68e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.229ex; height:2.843ex;" alt="{\displaystyle O[1]}" /></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Autres_algorithmes">Autres algorithmes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=8" title="Modifier la section : Autres algorithmes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=8" title="Modifier le code source de la section : Autres algorithmes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Il existe d'autres algorithmes qui permettent de calculer la transformée de Fourier discrète. Pour une taille <i>n</i> = <i>n</i><sub>1</sub><i>n</i><sub>2</sub>, avec des nombres premiers entre eux <i>n</i><sub>1</sub> et <i>n</i><sub>2</sub>, il est possible d'utiliser l'algorithme PFA (Good-Thomas) basé sur le <a href="/wiki/Th%C3%A9or%C3%A8me_des_restes_chinois" title="Théorème des restes chinois">théorème des restes chinois</a>. Le PFA est similaire à celui de Cooley-Tukey. </p><p>L'algorithme de Rader-Brenner<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> est aussi une variante de Cooley-Tukey avec des <i>facteurs de rotation</i> purement imaginaires qui améliorent les performances en réduisant le nombre de multiplications mais au détriment de la <a href="/wiki/Stabilit%C3%A9_num%C3%A9rique" title="Stabilité numérique">stabilité numérique</a> et une augmentation du nombre d'additions. Les algorithmes qui procèdent aussi par des factorisations successives sont <a href="/w/index.php?title=Algorithme_de_Bruun&action=edit&redlink=1" class="new" title="Algorithme de Bruun (page inexistante)">celui de Bruun</a> <a href="https://en.wikipedia.org/wiki/Bruun%27s_FFT_algorithm" class="extiw" title="en:Bruun's FFT algorithm"><span class="indicateur-langue" title="Article en anglais : « Bruun's FFT algorithm »">(en)</span></a> et l'<a href="/w/index.php?title=Algorithme_QFT&action=edit&redlink=1" class="new" title="Algorithme QFT (page inexistante)">algorithme QFT</a>. Les versions originales travaillent sur des fenêtres dont la taille est une puissance de 2 mais il est possible de les adapter pour une taille quelconque. L'algorithme de Bruun considère la transformée de Fourier rapide comme une factorisation récursive du <a href="/wiki/Polyn%C3%B4me" title="Polynôme">polynôme</a> <i>z<sup>n</sup></i> – 1 en des polynômes à coefficients réels de la forme <i>z<sup>m</sup></i> – 1 et <i>z</i><sup>2<i>m</i></sup> + <i>az<sup>m</sup></i> + 1. </p><p>L'algorithme de <a href="/wiki/Terry_Winograd" title="Terry Winograd">Winograd</a> factorise <i>z<sup>n</sup></i> – 1 en un <a href="/wiki/Polyn%C3%B4me_cyclotomique" title="Polynôme cyclotomique">polynôme cyclotomique</a>, dont les coefficients sont souvent –1, 0 ou 1, ce qui réduit le nombre de multiplications. On peut voir cet algorithme comme la version optimale en termes de multiplications. Winograd a montré que la transformée de Fourier discrète peut être calculée avec seulement O(<i>n</i>) multiplications, et ce <a href="/wiki/Minorant" class="mw-redirect" title="Minorant">minorant</a> est atteint pour les tailles qui sont des puissances de 2. Toutefois, des additions supplémentaires sont nécessaires, ce qui peut être pénalisant sur les <a href="/wiki/Processeur" title="Processeur">processeurs</a> modernes comportant des <a href="/wiki/Unit%C3%A9_de_calcul_en_virgule_flottante" title="Unité de calcul en virgule flottante">unités arithmétiques</a> performantes. </p><p>L'<a href="/w/index.php?title=Algorithme_de_Rader&action=edit&redlink=1" class="new" title="Algorithme de Rader (page inexistante)">algorithme de Rader</a> <a href="https://en.wikipedia.org/wiki/Rader%27s_FFT_algorithm" class="extiw" title="en:Rader's FFT algorithm"><span class="indicateur-langue" title="Article en anglais : « Rader's FFT algorithm »">(en)</span></a> est quant à lui destiné aux <a href="/wiki/Fen%C3%AAtrage" title="Fenêtrage">fenêtres</a> dont la taille est un <a href="/wiki/Nombre_premier" title="Nombre premier">nombre premier</a>. Il profite de l'existence d'une génératrice pour le <a href="/wiki/Groupe_(math%C3%A9matiques)" title="Groupe (mathématiques)">groupe</a> multiplicatif modulo <i>n</i>. La transformation discrète dont la taille est un nombre premier s'exprime ainsi comme une <a href="/wiki/Analyse_harmonique_sur_un_groupe_ab%C3%A9lien_fini#Produit_de_convolution" title="Analyse harmonique sur un groupe abélien fini">convolution cyclique</a> de taille <i>n</i> – 1. On peut ensuite la calculer par une paire de transformation de Fourier rapide. </p><p>Finalement, un autre algorithme destiné aux transformations avec des tailles qui sont des nombres premiers est due à Leo Bluestein, en 1968. On l'appelle plus souvent l'<a href="/w/index.php?title=Transformation_chirp_Z&action=edit&redlink=1" class="new" title="Transformation chirp Z (page inexistante)">algorithme chirp Z</a> <a href="https://en.wikipedia.org/wiki/Chirp_Z-transform" class="extiw" title="en:Chirp Z-transform"><span class="indicateur-langue" title="Article en anglais : « Chirp Z-transform »">(en)</span></a>. Ici encore, la transformation est vue comme une convolution dont la taille est identique à la fenêtre originale. On utilise à cet effet l'<a href="/wiki/Identit%C3%A9_de_polarisation" title="Identité de polarisation">identité de polarisation</a> : <i>jk</i> = –(<i>j – k</i>)<sup>2</sup>/2 + <i>j</i><sup>2</sup>/2 + <i>k</i><sup>2</sup>/2. </p> <div class="mw-heading mw-heading2"><h2 id="Algorithmes_spécialisés_dans_le_traitement_de_données_réelles_ou/et_symétriques"><span id="Algorithmes_sp.C3.A9cialis.C3.A9s_dans_le_traitement_de_donn.C3.A9es_r.C3.A9elles_ou.2Fet_sym.C3.A9triques"></span>Algorithmes spécialisés dans le traitement de données réelles ou/et symétriques</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=9" title="Modifier la section : Algorithmes spécialisés dans le traitement de données réelles ou/et symétriques" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=9" title="Modifier le code source de la section : Algorithmes spécialisés dans le traitement de données réelles ou/et symétriques"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Dans beaucoup d'applications, les données en entrée de la transformation discrète de Fourier sont uniquement des <a href="/wiki/Nombre_r%C3%A9el" title="Nombre réel">nombres réels</a>. Dans ce cas, les sorties satisfont la symétrie suivante : <span style="display: block; margin-left:1.6em;"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f_{n-j}=f_{j}^{*},}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mi>j</mi> </mrow> </msub> <mo>=</mo> <msubsup> <mi>f</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>∗</mo> </mrow> </msubsup> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f_{n-j}=f_{j}^{*},}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e91d580dc5d56b2f71249144a60be54c852c3b46" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:10.434ex; height:3.176ex;" alt="{\displaystyle f_{n-j}=f_{j}^{*},}" /></span></span> et des algorithmes efficaces ont été conçus pour cette situation, par exemple celui de Sorensen en 1987<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>. Une approche possible consiste à prendre un algorithme classique comme celui de Cooley-Tukey et à enlever les parties inutiles dans le calcul. Cela se traduit par un gain de 50 % en mémoire et en vitesse de calcul. Alternativement, il est possible d'exprimer une transformation discrète sur des nombres réels (avec une taille paire) en une transformation avec des nombres complexes mais dont la taille a été divisée par deux (les parties imaginaires sont les éléments impairs et les parties réelles sont les éléments pairs) suivie d'un décodage dont la complexité est de l'ordre de O(<i>n</i>) opérations. </p><p>On pensait que les transformations avec des nombres réels pouvaient être plus efficacement calculées via une <a href="/w/index.php?title=Transform%C3%A9e_de_Hartley_discr%C3%A8te&action=edit&redlink=1" class="new" title="Transformée de Hartley discrète (page inexistante)">transformation de Hartley discrète</a> <a href="https://en.wikipedia.org/wiki/Discrete_Hartley_transform" class="extiw" title="en:Discrete Hartley transform"><span class="indicateur-langue" title="Article en anglais : « Discrete Hartley transform »">(en)</span></a> mais il a été prouvé par la suite qu'une transformation de Fourier discrète modifiée pouvait être plus efficace que la même transformation de Hartley. L'algorithme de Bruun était un candidat pour ces transformations mais il n'a pas eu la popularité escomptée. </p><p>Il existe encore d'autres variantes pour les cas où les données sont symétriques (c’est-à-dire des fonctions paires ou impaires) avec un gain supplémentaire de 50%. Dans ce cas, on utilise une <a href="/wiki/Transform%C3%A9e_en_cosinus_discr%C3%A8te" title="Transformée en cosinus discrète">transformée en cosinus discrète</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Problèmes_numériques_et_approximations"><span id="Probl.C3.A8mes_num.C3.A9riques_et_approximations"></span>Problèmes numériques et approximations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=10" title="Modifier la section : Problèmes numériques et approximations" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=10" title="Modifier le code source de la section : Problèmes numériques et approximations"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Par leur nature analytique, tous les algorithmes proposés ci-dessus calculent la transformée sans aucune erreur. Toutefois, il existe des algorithmes qui peuvent s'accommoder d'une marge d'erreur pour accélérer les calculs. En 1999, Edelman <i><abbr class="abbr" title="et alii (« et d’autres »)" lang="la">et al.</abbr></i> proposent une approximation à la transformée de Fourier rapide<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>. Cette version est destinée à une mise en œuvre en <a href="/wiki/Parall%C3%A9lisme_(informatique)" title="Parallélisme (informatique)">parallèle</a>. Une approximation basée sur les <a href="/wiki/Ondelette" title="Ondelette">ondelettes</a> est proposée en 1996 par Guo et Burrus<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> et tient compte de la répartition dans les entrées/sorties. Un autre algorithme a encore été proposé par Shentov <i><abbr class="abbr" title="et alii (« et d’autres »)" lang="la">et al.</abbr></i> en 1995<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>. Seul l'algorithme de Edelman fonctionne bien avec n'importe quel type de données, il profite de la redondance dans la matrice de Fourier plutôt que de la redondance dans les données initiales. </p><p>Toutefois, même les algorithmes décrits de manière analytique présentent des erreurs lorsqu'ils sont codés avec des virgules flottantes dont la précision est limitée. L'erreur est cependant limitée. Une borne supérieure d'erreur relative pour Cooley-Tukey est donnée par <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\epsilon \log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\epsilon \log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c7446bd149e47957862357c26fee85fdfe33aa46" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.09ex; height:2.843ex;" alt="{\displaystyle O(\epsilon \log(n))}" /></span> alors qu'elle est de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\epsilon n^{3/2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\epsilon n^{3/2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4982cda7477ffebc57ea1d39ff49a7643035bed9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.62ex; height:3.343ex;" alt="{\displaystyle O(\epsilon n^{3/2})}" /></span> pour la formulation triviale de la transformée de Fourier discrète<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>. Le terme <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ϵ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3837cad72483d97bcdde49c85d3b7b859fb3fd2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" /></span> représente ici la précision relative en <a href="/wiki/Virgule_flottante" title="Virgule flottante">virgule flottante</a>. En fait, l'erreur quadratique moyenne est encore plus limitée avec seulement <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\epsilon {\sqrt {\log(n)}})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </msqrt> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\epsilon {\sqrt {\log(n)}})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9dee58672f4ea6b8bb5f3e9f27bbad500e969be0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.026ex; height:4.843ex;" alt="{\displaystyle O(\epsilon {\sqrt {\log(n)}})}" /></span> pour Cooley-Tukey et <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\epsilon {\sqrt {n}})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>n</mi> </msqrt> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\epsilon {\sqrt {n}})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/33ea8ca2345fc063e07426c23b8fbe36a055678b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.857ex; height:3.009ex;" alt="{\displaystyle O(\epsilon {\sqrt {n}})}" /></span> pour la version triviale. Il ne faut malgré tout pas oublier que la stabilité peut être perturbée par les différents facteurs de rotation qui interviennent dans les calculs. Un manque de précision sur les fonctions trigonométriques peut fortement augmenter l'erreur. L'algorithme de Rader est par exemple nettement moins stable que celui de Cooley-Tukey en cas d'erreurs prononcées. </p><p>Avec une arithmétique en <a href="/wiki/Virgule_fixe" title="Virgule fixe">virgule fixe</a>, les erreurs s'accumulent encore plus vite. Avec Cooley-Tukey, l'augmentation de l'erreur quadratique moyenne est de l'ordre de <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\epsilon {\sqrt {n}})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>n</mi> </msqrt> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\epsilon {\sqrt {n}})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/33ea8ca2345fc063e07426c23b8fbe36a055678b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.857ex; height:3.009ex;" alt="{\displaystyle O(\epsilon {\sqrt {n}})}" /></span>. De plus, il faut tenir compte de la magnitude des variables lors des différentes étapes de l'algorithme. </p><p>Il est possible de vérifier la validité de l'algorithme grâce à une procédure qui vise à déterminer la linéarité et d'autres caractéristiques de la transformation sur des entrées aléatoires<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup>. </p> <div class="mw-heading mw-heading2"><h2 id="Exemple_d'application_:_la_multiplication_de_polynômes"><span id="Exemple_d.27application_:_la_multiplication_de_polyn.C3.B4mes"></span>Exemple d'application : la multiplication de polynômes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=11" title="Modifier la section : Exemple d'application : la multiplication de polynômes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=11" title="Modifier le code source de la section : Exemple d'application : la multiplication de polynômes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Quand on veut multiplier deux polynômes représentés par la liste de leurs coefficients, la multiplication se fait en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}" /></span>. En revanche, si on les représente par une liste <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{k},P(x_{k}))_{0\leq k\leq n-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo>,</mo> <mi>P</mi> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo stretchy="false">)</mo> <msub> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (x_{k},P(x_{k}))_{0\leq k\leq n-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/715e1b38b527230a9828289a6556a4e60d09d41b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.789ex; height:2.843ex;" alt="{\displaystyle (x_{k},P(x_{k}))_{0\leq k\leq n-1}}" /></span> d'évaluations en des points tous distincts, la multiplication se fait en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" /></span> (en supposant que l'on a assez de valeurs pour avoir <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>P</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle P}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" /></span> défini de manière unique). On a donc intérêt à chercher un algorithme permettant de passer rapidement d'une de ces représentations à l'autre. </p><p>Or la FFT permet l'évaluation d'un polynôme en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85994022c28e938772bd858cd8281328643e8b3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.54ex; height:2.843ex;" alt="{\displaystyle O(n\log(n))}" /></span> et, inversement, son interpolation en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a135e65a42f2d73cccbfc4569523996ca0036f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n+1}" /></span> points (comme explicité dans la partie « Formulation mathématique »). Ainsi, la multiplication de deux polynômes représentés par la liste de leurs coefficients s'effectue en <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85994022c28e938772bd858cd8281328643e8b3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.54ex; height:2.843ex;" alt="{\displaystyle O(n\log(n))}" /></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Notes_et_références"><span id="Notes_et_r.C3.A9f.C3.A9rences"></span>Notes et références</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=12" title="Modifier la section : Notes et références" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=12" title="Modifier le code source de la section : Notes et références"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div style="font-size:85%; padding-left:1.6em; margin:0.3em 0;"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé <span class="plainlinks">« <a class="external text" href="https://en.wikipedia.org/wiki/Fast_Fourier_transform?oldid=13258072">Fast Fourier transform</a> » <small>(<a class="external text" href="https://en.wikipedia.org/wiki/Fast_Fourier_transform?action=history">voir la liste des auteurs</a>)</small></span>.</div> <div class="references-small decimal" style=""><div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a> </span><span class="reference-text"><span class="ouvrage">« <a rel="nofollow" class="external text" href="https://cdn.uclouvain.be/groups/cms-editors-irmp/Qui%20e%CC%81tait%20Georges%20Lemaitre.pdf"><cite style="font-style:normal;">Qui était Georges Lemaître?</cite></a> », sur <span class="italique">uclouvain.be</span></span>.</span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Lund_Jacobsen"><span class="ouvrage" id="Lif_Lund_Jacobsen"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Lif Lund Jacobsen, <cite class="italique" lang="en">The seismograph as a diplomatic object: The Soviet–American exchange of instruments, 1958–1964</cite> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="https://ve42.co/Jacobsen2021">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+seismograph+as+a+diplomatic+object%3A+The+Soviet%E2%80%93American+exchange+of+instruments%2C+1958%E2%80%931964&rft.au=Lif+Lund+Jacobsen&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Cooley"><span class="ouvrage" id="James_W._Cooley"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> James W. Cooley, <cite class="italique" lang="en">The Re-Discovery of the Fast Fourier Transform Algorithm</cite> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="https://carmamaths.org/resources/jon/Preprints/Talks/CARMA-CE/FFT.pdf">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+Re-Discovery+of+the+Fast+Fourier+Transform+Algorithm&rft.aulast=Cooley&rft.aufirst=James+W.&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a> </span><span class="reference-text"><span class="ouvrage" id="CooleyTukey1965"><span class="ouvrage" id="James_W._CooleyJohn_W._Tukey1965"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> James W. Cooley et John W. Tukey, « <cite style="font-style:normal" lang="en">An algorithm for the machine calculation of complex Fourier series</cite> », <i><span class="lang-en" lang="en"><a href="/wiki/Liste_des_journaux_scientifiques_en_math%C3%A9matiques#M" title="Liste des journaux scientifiques en mathématiques">Math. Comp.</a></span></i>, <abbr class="abbr" title="volume">vol.</abbr> 19,‎ <time>1965</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">297-301</span> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=An+algorithm+for+the+machine+calculation+of+complex+Fourier+series&rft.jtitle=Math.+Comp.&rft.aulast=Cooley&rft.aufirst=James+W.&rft.au=John+W.+Tukey&rft.date=1965&rft.volume=19&rft.pages=297-301&rft_id=http%3A%2F%2Fwww.ams.org%2Fjournals%2Fmcom%2F1965-19-090%2FS0025-5718-1965-0178586-1%2F&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span>.</span> </li> <li id="cite_note-Cooley-5"><span class="mw-cite-backlink"><a href="#cite_ref-Cooley_5-0">↑</a> </span><span class="reference-text">D'après <span class="ouvrage" id="Cooley1990"><span class="ouvrage" id="James_W._Cooley1990"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> James W. Cooley, <cite style="font-style:normal" lang="en">« How the FFT Gained Acceptance »</cite>, dans Stephen G. Nash, <cite class="italique" lang="en">A History of Scientific Computing</cite>, ACM Press, <time>1990</time> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://history.siam.org/pdf/jcooley.pdf">lire en ligne</a>)</small>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">133-140</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.btitle=A+History+of+Scientific+Computing&rft.atitle=How+the+FFT+Gained+Acceptance&rft.pub=ACM+Press&rft.aulast=Cooley&rft.aufirst=James+W.&rft.date=1990&rft.pages=133-140&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span>.</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><a href="#cite_ref-6">↑</a> </span><span class="reference-text"><span class="ouvrage" id="Carl_Friedrich_Gauss1866"><span class="nom_auteur">Carl Friedrich Gauss</span>, <cite class="italique">Annexe: Theoria interpolationis methodo nova tractata</cite>, <abbr class="abbr" title="volume">vol.</abbr> 3 : <span class="italique">Werke</span>, Göttingen, <a href="/wiki/K%C3%B6nigliche_Gesellschaft_der_Wissenschaften" class="mw-redirect" title="Königliche Gesellschaft der Wissenschaften">Königliche Gesellschaft der Wissenschaften</a>, <time>1866</time> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://lseet.univ-tln.fr/~iaroslav/Gauss_Theoria_interpolationis_methodo_nova_tractata.php">lire en ligne</a>)</small>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">265-327</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Annexe%3A+Theoria+interpolationis+methodo+nova+tractata&rft.place=G%C3%B6ttingen&rft.pub=K%C3%B6nigliche+Gesellschaft+der+Wissenschaften&rft.aulast=Carl+Friedrich+Gauss&rft.date=1866&rft.volume=3&rft.pages=265-327&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span>.</span> </li> <li id="cite_note-Owners_Manual-7"><span class="mw-cite-backlink"><a href="#cite_ref-Owners_Manual_7-0">↑</a> </span><span class="reference-text">Cf. l'article de <span class="ouvrage" id="HeidemanJohnsonSidney_Burrus1993"><span class="ouvrage" id="Michael_T._HeidemanDonald_H._JohnsonC._Sidney_Burrus1993"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Michael T. Heideman, Donald H. Johnson et <a href="/wiki/Charles_Sidney_Burrus" title="Charles Sidney Burrus">C. Sidney Burrus</a>, « <cite style="font-style:normal" lang="en">Gauss and the History of the Fast Fourier Transform</cite> », <i><span class="lang-en" lang="en"><a href="/wiki/Archive_for_History_of_Exact_Sciences" title="Archive for History of Exact Sciences">Arch. Hist. Exact Sci.</a></span></i>, <abbr class="abbr" title="volume">vol.</abbr> 34, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 3,‎ <time>1993</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">265-277</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Gauss+and+the+History+of+the+Fast+Fourier+Transform&rft.jtitle=Arch.+Hist.+Exact+Sci.&rft.issue=3&rft.aulast=Heideman&rft.aufirst=Michael+T.&rft.au=Donald+H.+Johnson&rft.au=C.+Sidney+Burrus&rft.date=1993&rft.volume=34&rft.pages=265-277&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span> cité par <span class="ouvrage" id="Briggsvan_Emden1995"><span class="ouvrage" id="William_L._BriggsHenson_van_Emden1995"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> William L. Briggs et Henson van Emden, <cite class="italique" lang="en">The DFT : An owner's manual for the Discrete Fourier Transform</cite>, <a href="/wiki/Society_for_Industrial_and_Applied_Mathematics" title="Society for Industrial and Applied Mathematics">SIAM</a>, <time>1995</time>, 436 <abbr class="abbr" title="pages">p.</abbr> <small style="line-height:1em;">(<a href="/wiki/International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> <a href="/wiki/Sp%C3%A9cial:Ouvrages_de_r%C3%A9f%C3%A9rence/0898713420" title="Spécial:Ouvrages de référence/0898713420"><span class="nowrap">0898713420</span></a>)</small><span class="lang-en" lang="en">, « Introduction: A Bit of History »</span>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">5-7</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=The+DFT&rft.pub=SIAM&rft.stitle=An+owner%27s+manual+for+the+Discrete+Fourier+Transform&rft.aulast=Briggs&rft.aufirst=William+L.&rft.au=Henson+van+Emden&rft.date=1995&rft.pages=5-7&rft.tpages=436&rft.isbn=0898713420&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span>. Voir aussi <abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> M. T. Heideman, D. H. Johnson et C. S. Burrus, « Gauss and the history of the fast Fourier transform », <i>IEEE ASSP Magazine</i>, vol. 1, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 4, 1984, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">14-21</span>.</span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><a href="#cite_ref-8">↑</a> </span><span class="reference-text"><span class="ouvrage" id="BrennerRader1976"><span class="ouvrage" id="N._BrennerC._Rader1976"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> N. Brenner et C. Rader, « <cite style="font-style:normal" lang="en">A new principle for Fast Fourier Transformation</cite> », <i><span class="lang-en" lang="en">IEEE Acoustics, Speech & Signal Processing</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 24, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 3,‎ <time>1976</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">264-266</span> <small style="line-height:1em;">(<a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <span class="plainlinks noarchive nowrap"><a rel="nofollow" class="external text" href="https://dx.doi.org/10.1109/TASSP.1976.1162805">10.1109/TASSP.1976.1162805</a></span>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=A+new+principle+for+Fast+Fourier+Transformation&rft.jtitle=IEEE+Acoustics%2C+Speech+%26+Signal+Processing&rft.issue=3&rft.aulast=Brenner&rft.aufirst=N.&rft.au=C.+Rader&rft.date=1976&rft.volume=24&rft.pages=264-266&rft_id=info%3Adoi%2F10.1109%2FTASSP.1976.1162805&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span>.</span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><a href="#cite_ref-9">↑</a> </span><span class="reference-text"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> H. V. Sorensen, D. L. Jones, M. T. Heideman et C. S. Burrus, « Real-valued fast Fourier transform algorithms », <i>IEEE Trans. Acoust. Speech Sig. Processing</i>, vol. ASSP-35, 1987, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">849-863</span>.</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><a href="#cite_ref-10">↑</a> </span><span class="reference-text"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Alan Edelman, Peter McCorquodale et Sivan Toledo, « The future fast Fourier transform? », <i><a href="/wiki/Liste_des_journaux_scientifiques_en_math%C3%A9matiques#S" title="Liste des journaux scientifiques en mathématiques">SIAM J. Sci. Comput.</a></i>, vol. 20, 1999, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">1094-1114</span>, <small class="plainlinks noarchive"><a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1137%2FS1064827597316266">10.1137/S1064827597316266</a></small>.</span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><a href="#cite_ref-11">↑</a> </span><span class="reference-text"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> H. Guo et <a href="/wiki/Charles_Sidney_Burrus" title="Charles Sidney Burrus">C. S. Burrus</a>, « Fast approximate Fourier transform via wavelets transform », <i>Proc. SPIE Intl. Soc. Opt. Eng.</i>, vol. 2825, 1996, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">250-259</span>.</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><a href="#cite_ref-12">↑</a> </span><span class="reference-text"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> O. V. Shentov, S. K. Mitra, U. Heute et A. N. Hossen, « Subband DFT. I. Definition, interpretations and extensions », <i>Signal Processing</i>, vol. 41, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 3, 1995, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">261-277</span>, <small class="plainlinks noarchive"><a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1016%2F0165-1684%2894%2900103-7">10.1016/0165-1684(94)00103-7</a></small>.</span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><a href="#cite_ref-13">↑</a> </span><span class="reference-text"><span class="ouvrage" id="GentlemanSande1966"><span class="ouvrage" id="W._M._GentlemanG._Sande1966"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> W. M. Gentleman et G. Sande, « <cite style="font-style:normal" lang="en">Fast Fourier transforms — for fun and profit</cite> », <i><span class="lang-en" lang="en">Proc. AFIPS</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 29,‎ <time>1966</time> <small style="line-height:1em;">(<a rel="nofollow" class="external text" href="http://www.cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf">lire en ligne</a>)</small><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Fast+Fourier+transforms+%E2%80%94+for+fun+and+profit&rft.jtitle=Proc.+AFIPS&rft.aulast=Gentleman&rft.aufirst=W.+M.&rft.au=G.+Sande&rft.date=1966&rft.volume=29&rft_id=http%3A%2F%2Fwww.cis.rit.edu%2Fclass%2Fsimg716%2FFFT_Fun_Profit.pdf&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span>.</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><a href="#cite_ref-14">↑</a> </span><span class="reference-text"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Funda Ergün, « Testing multivariate linear functions: overcoming the generator bottleneck », dans <i>Proc. 27th ACM Symposium on the Theory of Computing</i>, 1995, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">407-416</span>, <small class="plainlinks noarchive"><a href="/wiki/Digital_Object_Identifier" title="Digital Object Identifier">DOI</a> <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1145%2F225058.225167">10.1145/225058.225167</a></small>.</span> </li> </ol></div> </div> <div class="mw-heading mw-heading2"><h2 id="Voir_aussi">Voir aussi</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=13" title="Modifier la section : Voir aussi" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=13" title="Modifier le code source de la section : Voir aussi"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Bibliographie">Bibliographie</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=14" title="Modifier la section : Bibliographie" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=14" title="Modifier le code source de la section : Bibliographie"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>F. Schwartzentruber, <a rel="nofollow" class="external text" href="https://people.irisa.fr/Francois.Schwarzentruber/algo1/04diviserpourregner.pdf">« Diviser pour régner »</a>, cours d'informatique niveau L3 à l'ENS de Rennes</li> <li><span class="ouvrage" id="DuhamelVetterli1990"><span class="ouvrage" id="P._DuhamelM._Vetterli1990"><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> P. Duhamel et M. Vetterli, « <cite style="font-style:normal" lang="en">A Fast Fourier transforms: a tutorial review and a state of the art</cite> », <i><span class="lang-en" lang="en">Signal Processing</span></i>, <abbr class="abbr" title="volume">vol.</abbr> 19,‎ <time>1990</time>, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">259-299</span><span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=A+Fast+Fourier+transforms%3A+a+tutorial+review+and+a+state+of+the+art&rft.jtitle=Signal+Processing&rft.aulast=Duhamel&rft.aufirst=P.&rft.au=M.+Vetterli&rft.date=1990&rft.volume=19&rft.pages=259-299&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ATransformation+de+Fourier+rapide"></span></span></span></li> <li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> H. Guo, G. A. Sitton et C. S. Burrus, « The Quick Discrete Fourier Transform », <i>Proc. IEEE Conf. Acoust. Speech and Sig. Processing (ICASSP)</i>, vol. 3, 1994, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">445-448</span></li> <li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> James C. Schatzman, « Accuracy of the discrete Fourier transform and the fast Fourier transform », <i>SIAM J. Sci. Comput.</i>, vol. 17, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 5, 1996, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">1150-1166</span></li> <li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> A. V. Oppenheim et R. Schafer, <i>Digital Signal Processing</i>, Englewood Cliffs, NJ, Prentice-Hall, 1975</li> <li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> Matteo Frigo et Steven G. Johnson, <a rel="nofollow" class="external text" href="http://fftw.org/fftw-paper-ieee.pdf">« The Design and Implementation of FFTW3 »</a>, <i>Proceedings of the IEEE</i>, vol. 93, <abbr class="abbr" title="numéro">n<sup>o</sup></abbr> 2, 2005, <abbr class="abbr" title="pages">p.</abbr> <span class="nowrap">216-231</span> — Une version libre (<a href="/wiki/Licence_publique_g%C3%A9n%C3%A9rale_GNU" title="Licence publique générale GNU">GPL</a>) de la transformée de Fourier rapide (bibliothèque C) pour des données de taille et de dimensions arbitraires.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Articles_connexes">Articles connexes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=15" title="Modifier la section : Articles connexes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=15" title="Modifier le code source de la section : Articles connexes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/%C3%89chantillonnage_(signal)" title="Échantillonnage (signal)">Échantillonnage</a></li> <li><a href="/wiki/Fen%C3%AAtrage" title="Fenêtrage">Fenêtrage</a></li> <li><a href="/wiki/Transform%C3%A9e_de_Fourier" class="mw-redirect" title="Transformée de Fourier">Transformée de Fourier</a></li> <li><a href="/wiki/Transform%C3%A9e_en_Z" class="mw-redirect" title="Transformée en Z">Transformée en Z</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Vidéographie"><span id="Vid.C3.A9ographie"></span>Vidéographie</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&veaction=edit&section=16" title="Modifier la section : Vidéographie" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Transformation_de_Fourier_rapide&action=edit&section=16" title="Modifier le code source de la section : Vidéographie"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><span class="ouvrage">« <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=nmgFG7PUHfo"><cite style="font-style:normal;">The Most Important Algorithm Of All Time</cite></a> » <small style="line-height:1em;">(consulté le <time class="nowrap" datetime="2022-11-08" data-sort-value="2022-11-08">8 novembre 2022</time>)</small></span></li></ul> <ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Math%C3%A9matiques" title="Portail des mathématiques"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/40px-Racine_carr%C3%A9e_bleue.svg.png" decoding="async" width="24" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/60px-Racine_carr%C3%A9e_bleue.svg.png 2x" data-file-width="128" data-file-height="128" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Math%C3%A9matiques" title="Portail:Mathématiques">Portail des mathématiques</a></span> </span></li> <li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail de l'informatique théorique"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/30px-Max-cut.svg.png" decoding="async" width="30" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/45px-Max-cut.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/60px-Max-cut.svg.png 2x" data-file-width="200" data-file-height="160" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail:Informatique théorique">Portail de l'informatique théorique</a></span> </span></li> </ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Ce document provient de « <a dir="ltr" href="https://fr.wikipedia.org/w/index.php?title=Transformation_de_Fourier_rapide&oldid=223976180">https://fr.wikipedia.org/w/index.php?title=Transformation_de_Fourier_rapide&oldid=223976180</a> ».</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Cat%C3%A9gorie:Accueil" title="Catégorie:Accueil">Catégories</a> : <ul><li><a href="/wiki/Cat%C3%A9gorie:Th%C3%A9orie_de_Fourier" title="Catégorie:Théorie de Fourier">Théorie de Fourier</a></li><li><a href="/wiki/Cat%C3%A9gorie:Algorithme_num%C3%A9rique" title="Catégorie:Algorithme numérique">Algorithme numérique</a></li><li><a href="/wiki/Cat%C3%A9gorie:Transform%C3%A9e_du_signal" title="Catégorie:Transformée du signal">Transformée du signal</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Catégories cachées : <ul><li><a href="/wiki/Cat%C3%A9gorie:Article_contenant_un_appel_%C3%A0_traduction_en_anglais" title="Catégorie:Article contenant un appel à traduction en anglais">Article contenant un appel à traduction en anglais</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Math%C3%A9matiques/Articles_li%C3%A9s" title="Catégorie:Portail:Mathématiques/Articles liés">Portail:Mathématiques/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Sciences/Articles_li%C3%A9s" title="Catégorie:Portail:Sciences/Articles liés">Portail:Sciences/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Projet:Math%C3%A9matiques/Articles" title="Catégorie:Projet:Mathématiques/Articles">Projet:Mathématiques/Articles</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique_th%C3%A9orique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique théorique/Articles liés">Portail:Informatique théorique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique/Articles liés">Portail:Informatique/Articles liés</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> La dernière modification de cette page a été faite le 17 mars 2025 à 13:32.</li> <li id="footer-info-copyright"><span style="white-space: normal"><a href="/wiki/Wikip%C3%A9dia:Citation_et_r%C3%A9utilisation_du_contenu_de_Wikip%C3%A9dia" title="Wikipédia:Citation et réutilisation du contenu de Wikipédia">Droit d'auteur</a> : les textes sont disponibles sous <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">licence Creative Commons attribution, partage dans les mêmes conditions</a> ; d’autres conditions peuvent s’appliquer. Voyez les <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/fr">conditions d’utilisation</a> pour plus de détails, ainsi que les <a href="/wiki/Wikip%C3%A9dia:Cr%C3%A9dits_graphiques" title="Wikipédia:Crédits graphiques">crédits graphiques</a>. En cas de réutilisation des textes de cette page, voyez <a href="/wiki/Sp%C3%A9cial:Citer/Transformation_de_Fourier_rapide" title="Spécial:Citer/Transformation de Fourier rapide">comment citer les auteurs et mentionner la licence</a>.<br /> Wikipedia® est une marque déposée de la <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a href="/wiki/501c" title="501c">501(c)(3)</a> du code fiscal des États-Unis.</span><br /></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/fr">Politique de confidentialité</a></li> <li id="footer-places-about"><a href="/wiki/Wikip%C3%A9dia:%C3%80_propos_de_Wikip%C3%A9dia">À propos de Wikipédia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikip%C3%A9dia:Avertissements_g%C3%A9n%C3%A9raux">Avertissements</a></li> <li id="footer-places-contact"><a href="//fr.wikipedia.org/wiki/Wikipédia:Contact">Contact</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code de conduite</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Développeurs</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/fr.wikipedia.org">Statistiques</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Déclaration sur les témoins (cookies)</a></li> <li id="footer-places-mobileview"><a href="//fr.m.wikipedia.org/w/index.php?title=Transformation_de_Fourier_rapide&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Version mobile</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://www.wikimedia.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Rechercher</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Rechercher sur Wikipédia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Spécial:Recherche"> </div> <button class="cdx-button cdx-search-input__end-button">Rechercher</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Sommaire" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Basculer la table des matières" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Basculer la table des matières</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Transformation de Fourier rapide</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>29 langues</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Ajouter un sujet</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-585dc88b6-vmnpb","wgBackendResponseTime":191,"wgPageParseReport":{"limitreport":{"cputime":"0.236","walltime":"0.534","ppvisitednodes":{"value":1946,"limit":1000000},"postexpandincludesize":{"value":39288,"limit":2097152},"templateargumentsize":{"value":2039,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":5,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":20559,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 225.356 1 -total"," 35.07% 79.022 1 Modèle:Références"," 20.06% 45.215 1 Modèle:Portail"," 12.97% 29.226 1 Modèle:Homonyme"," 11.80% 26.596 1 Modèle:Méta_bandeau_de_note"," 11.19% 25.215 1 Modèle:Méta_bandeau"," 10.53% 23.741 2 Modèle:Lien_web"," 8.76% 19.742 1 Modèle:Catégorisation_badges"," 8.74% 19.689 1 Modèle:Langue"," 7.04% 15.856 1 Modèle:Suivi_des_biographies"]},"scribunto":{"limitreport-timeusage":{"value":"0.076","limit":"10.000"},"limitreport-memusage":{"value":4787122,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-585dc88b6-w7z4q","timestamp":"20250326233314","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Transformation de Fourier rapide","url":"https:\/\/fr.wikipedia.org\/wiki\/Transformation_de_Fourier_rapide","sameAs":"http:\/\/www.wikidata.org\/entity\/Q623950","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q623950","author":{"@type":"Organization","name":"Contributeurs aux projets Wikimedia"},"publisher":{"@type":"Organization","name":"Fondation Wikimedia, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-05-12T15:13:38Z","dateModified":"2025-03-17T12:32:48Z","headline":"algorithme de calcul"}</script> </body> </html>

CINXE.COM

Transformation de Fourier rapide — Wikipédia