專利名稱：信息處理設(shè)備、其控制方法、程序及計(jì)算機(jī)可讀存儲(chǔ)媒體的制作方法
技術(shù)領(lǐng)域：
本發(fā)明涉及信息處理設(shè)備及其控制方法、程序和計(jì)算機(jī)可讀存儲(chǔ)媒體，并且具體涉及但不限于使用小容量存儲(chǔ)器來提供快速傅立葉變換。
背景技術(shù)：
快速傅立葉變換(FFT)是計(jì)算離散傅立葉變換(DFT)及其逆的有效算法。假設(shè)
權(quán)利要求
1.一種用于對(duì)數(shù)據(jù)序列執(zhí)行基2快速傅立葉變換(FFT)的信息處理設(shè)備，包括 存儲(chǔ)部件，用于包括多個(gè)存儲(chǔ)區(qū)域，其中每個(gè)存儲(chǔ)要處理的多個(gè)數(shù)據(jù)元素并被指派存儲(chǔ)地址； 讀取部件，用于從所述存儲(chǔ)部件讀取多個(gè)集，每個(gè)集包括在相同存儲(chǔ)區(qū)域中存儲(chǔ)的多個(gè)數(shù)據(jù)元素； 多個(gè)蝶式運(yùn)算部件，用于對(duì)多個(gè)數(shù)據(jù)元素分別通過預(yù)確定的系數(shù)執(zhí)行蝶式運(yùn)算以分別計(jì)算多個(gè)結(jié)果數(shù)據(jù)，每個(gè)數(shù)據(jù)元素被包括在從所述存儲(chǔ)部件讀取的多個(gè)集中； 寫入部件，用于將包括所述多個(gè)結(jié)果數(shù)據(jù)的集寫入所述存儲(chǔ)部件中；以及控制部件，用于在FFT運(yùn)算的每一級(jí)控制所述部件中的每個(gè)部件以對(duì)所述存儲(chǔ)媒體中存儲(chǔ)的所有數(shù)據(jù)元素執(zhí)行所述蝶式運(yùn)算， 其中所述FFT運(yùn)算的每個(gè)級(jí)包括多個(gè)運(yùn)算步驟，并且在每一運(yùn)算步驟，所述控制部件控制所述部件中的每個(gè)部件，使得 所述讀取部件從所述存儲(chǔ)部件讀取第一存儲(chǔ)地址J指引的數(shù)據(jù)元素的第一集、第二存儲(chǔ)地址J+1指引的數(shù)據(jù)元素的第二集、第三存儲(chǔ)地址指引的數(shù)據(jù)元素的第三集及第四存儲(chǔ)地址J+2"+l指引的數(shù)據(jù)元素的第四集， 所述多個(gè)蝶式運(yùn)算部件對(duì)所述第一集中包括的數(shù)據(jù)元素和所述第三集中包括的數(shù)據(jù)元素執(zhí)行基2蝶式運(yùn)算，以計(jì)算所述結(jié)果數(shù)據(jù)的第一和第三集，并且對(duì)所述第二集中包括的數(shù)據(jù)元素和所述第四集中包括的數(shù)據(jù)元素執(zhí)行基2蝶式運(yùn)算，以計(jì)算所述結(jié)果數(shù)據(jù)的第二和第四集，以及 所述寫入部件將所述結(jié)果數(shù)據(jù)的第一集寫入所述第一存儲(chǔ)地址^指引的存儲(chǔ)區(qū)域中，將所述結(jié)果數(shù)據(jù)的第二和第三集之一寫入所述第二存儲(chǔ)地址J+1指引的存儲(chǔ)區(qū)域中，以及將所述結(jié)果數(shù)據(jù)的第二和第三集中的另一集寫入所述第三存儲(chǔ)地址J+f指引的存儲(chǔ)區(qū)域中，以及將所述結(jié)果數(shù)據(jù)的第四集寫入所述第四存儲(chǔ)地址J+2"+l指引的存儲(chǔ)區(qū)域中， 其中d是為每個(gè)運(yùn)算步驟確定的零或正整數(shù)，以及 是為每個(gè)級(jí)確定的正整數(shù)。
2.根據(jù)權(quán)利要求I所述的信息處理設(shè)備，其中所述讀取部件包括用于保留從所述存儲(chǔ)部件讀取的數(shù)據(jù)元素的集的第一保留部件，以及其中所述寫入部件包括用于保留所述結(jié)果數(shù)據(jù)的集的第二保留部件。
3.根據(jù)權(quán)利要求2所述的信息處理設(shè)備，其中所述讀取部件包括用于所述數(shù)據(jù)元素的每個(gè)集的多個(gè)所述第一保留部件，并且所述寫入部件包括用于所述結(jié)果數(shù)據(jù)的每個(gè)集的多個(gè)所述第二保留部件。
4.一種用于對(duì)數(shù)據(jù)序列執(zhí)行混合基或單基快速傅立葉變換(FFT)的信息處理設(shè)備，包括 存儲(chǔ)部件，用于包括多個(gè)存儲(chǔ)區(qū)域，其中每個(gè)存儲(chǔ)要處理的多個(gè)數(shù)據(jù)元素并被指派存儲(chǔ)地址； 讀取部件，用于從所述存儲(chǔ)部件讀取多個(gè)集，每個(gè)集包括在相同存儲(chǔ)區(qū)域中存儲(chǔ)的多個(gè)數(shù)據(jù)元素； 多個(gè)蝶式運(yùn)算部件，用于對(duì)多個(gè)數(shù)據(jù)元素分別通過預(yù)確定的系數(shù)執(zhí)行蝶式運(yùn)算以分別計(jì)算多個(gè)結(jié)果數(shù)據(jù)，每個(gè)數(shù)據(jù)元素被包括在從所述存儲(chǔ)部件讀取的多個(gè)集中； 寫入部件，用于將包括所述多個(gè)結(jié)果數(shù)據(jù)的集寫入所述存儲(chǔ)部件中；以及控制部件，用于在FFT運(yùn)算的每一級(jí)控制所述部件中的每個(gè)部件以對(duì)所述存儲(chǔ)媒體中存儲(chǔ)的所有數(shù)據(jù)元素執(zhí)行所述蝶式運(yùn)算， 其中所述FFT運(yùn)算的每個(gè)級(jí)包括多個(gè)運(yùn)算步驟，并且在每一運(yùn)算步驟，所述控制部件控制所述部件中的每個(gè)部件，使得 其中^是為每個(gè)運(yùn)算步驟確定的零或正整數(shù)，A是大于一且為每個(gè)級(jí)確定的整數(shù)，/7是作為要在每個(gè)級(jí)中執(zhí)行的蝶式運(yùn)算的基數(shù)的且為每個(gè)級(jí)確定的整數(shù)，以及7是作為要在所述級(jí)之一中執(zhí)行的蝶式運(yùn)算的基數(shù)的整數(shù)， 所述讀取部件為所有整數(shù)
5.一種用于對(duì)數(shù)據(jù)序列執(zhí)行基2快速傅立葉變換(FFT)的信息處理設(shè)備的控制方法，其中所述信息處理設(shè)備包括存儲(chǔ)部件，用于包括多個(gè)存儲(chǔ)區(qū)域，每個(gè)存儲(chǔ)區(qū)域存儲(chǔ)要處理的多個(gè)數(shù)據(jù)元素并被指派存儲(chǔ)地址，所述控制方法包括以下步驟 在讀取部件，從所述存儲(chǔ)部件讀取多個(gè)集，每個(gè)集包括在相同存儲(chǔ)區(qū)域中存儲(chǔ)的多個(gè)數(shù)據(jù)元素； 在執(zhí)行部件，對(duì)多個(gè)數(shù)據(jù)元素分別通過預(yù)確定的系數(shù)執(zhí)行蝶式運(yùn)算以分別計(jì)算多個(gè)結(jié)果數(shù)據(jù)，每個(gè)數(shù)據(jù)元素被包括在從所述存儲(chǔ)部件讀取的多個(gè)集中； 在寫入部件，將包括所述多個(gè)結(jié)果數(shù)據(jù)的集寫入所述存儲(chǔ)部件中；以及
6.一種用于使計(jì)算機(jī)充當(dāng)根據(jù)權(quán)利要求I到4中任一項(xiàng)所述的信息處理設(shè)備的程序。
7.一種存儲(chǔ)根據(jù)權(quán)利要求6所述程序的計(jì)算機(jī)可讀存儲(chǔ)媒體。
全文摘要
本發(fā)明提供用于通過小的存儲(chǔ)器實(shí)現(xiàn)高速快速傅立葉變換(FFT)算法的技術(shù)。用于對(duì)數(shù)據(jù)序列執(zhí)行基2FFT的信息處理設(shè)備包括存儲(chǔ)部件、讀取部件、多個(gè)蝶式運(yùn)算部件、寫入部件及控制部件，其中，F(xiàn)FT運(yùn)算的每一級(jí)包括多個(gè)運(yùn)算步驟，并且在每個(gè)運(yùn)算步驟，控制部件控制每個(gè)部件，使得讀取部件從存儲(chǔ)部件讀取存儲(chǔ)地址A、A+1、A+2m和A+2m+1指引的數(shù)據(jù)元素集，多個(gè)蝶式運(yùn)算部件對(duì)集中的數(shù)據(jù)元素執(zhí)行基2蝶式運(yùn)算，以及寫入部件將結(jié)果數(shù)據(jù)集寫入存儲(chǔ)地址A、A+1、A+2m和A+2m+1指引的存儲(chǔ)區(qū)域。
文檔編號(hào)G06F17/14GK102652315SQ20098016296
公開日2012年8月29日 申請(qǐng)日期2009年12月16日 優(yōu)先權(quán)日2009年12月16日
發(fā)明者淺中和典 申請(qǐng)人:瑞典愛立信有限公司