| 主权项 |
一种任意点数快速傅利叶转换之计算与定址方法，其特征在于包含下列步骤：(1)将长点数离散傅立叶转换的计算分解为数个短点数的离散傅立叶转换，并同时将其指标由单一维度映射成多维度指标向量；(2)藉由控制这些多维度指标向量，把原始输入资料分散存放到数个记忆体里，使得在不产生记忆体存取冲突的情况下同时达到计算期间的资料置换与记忆体完整蝴蝶点数一次存取的目的；(3)当资料置换使用在已计算完成的旧资料依序输出与新资料依序输入时，为了往后计算期间可以继续保持资料存取时没有记忆体冲突，对于新资料的计算采取与先前资料计算时的反序操作来达成目的；依此方法，对于设计任意点数的以记忆体为基础的快速傅立叶转换处理器，可以减少处理器面积与所需的操作时脉。一种使用如专利范围第1项所述之计算与定址方法之以记忆体为基础之正/逆向快速傅立叶转换处理器，其系包含：一用以存放资料之主要记忆体、一进行分解后短点数快速傅立叶转换之处理元件以及一控制单元，其中该控制单元具有控制以下项目之功能：(1)输入输出资料与蝴蝶运算用之记忆体，(2)分解后之短点数快速傅立叶转换之计算顺序，及(3)以资料置换方式进行资料存取所需之记忆体定址。如申请专利范围第2项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，该主要记忆体包含二记忆区块，为MEM_1与MEM_2，当MEM_1用于快速傅立叶转换运算时，MEM_2则用于输入输出资料，当MEM_2用于快速傅立叶转换运送时，MEM_1则用于输入输出资料。如申请专利范围第3项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，每一记忆区块包含M个记忆库，且每一记忆库之大小为i>N/i>/M，其中i>N/i>为快速傅立叶转换之点数长度，M为由系统设计者自行设定之记忆库数量。如申请专利范围第2项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，该处理器系设计为可对分解后之短点数快速傅立叶转换进行个别计算。如申请专利范围第2项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，该控制单元之第(1)项控制功能系控制如申请专利范围第3项所述之该两记忆区块，以将其功能切换为快速傅立叶转换计算或输入输出资料。如申请专利范围第2项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，该控制单元之第(2)项控制功能系控制该处理元件来依照申请专利范围第1项第(3)点之步骤执行，使其利用与同一记忆区块之前次快速傅立叶转换符元分解顺序相反之顺序进行短点数快速傅立叶转换计算，从而取得快速傅立叶转换符元；亦即，若该快速傅立叶转换符元于一记忆区块中系以i>N/i>1点快速傅立叶转换、i>N/i>2点快速傅立叶转换......至i>N/i>k点快速傅立叶转换之顺序计算，则储存于同一记忆区块中之次一快速傅立叶转换符元之计算顺序为i>N/i>k点快速傅立叶转换、i>N/i>(k-1)点快速傅立叶转换......至i>N/i>1点快速傅立叶转换。如申请专利范围第2项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，该控制单元之第(3)项控制功能系记忆体定址并控制以资料置换之方式进行资料存取，从而进行每一记忆区块之蝴蝶运算与资料输入输出，此项控制功能为申请专利范围第1项第(2)点之实施。如申请专利范围第8项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，执行资料存取之记忆库系由指标向量(i>n/i>1,i>n/i>2,...,i>n/i>k)与方程式(a1)所决定，其中方程式(a1)之i>c/i>为一常量整数，而该指标向量对应每一短点数快速傅立叶转换，亦即如申请专利范围第7项所述之i>N/i>1点快速傅立叶转换、i>N/i>2点快速傅立叶转换......至i>N/i>k点快速傅立叶转换；i>bank/i>=i>n/i>1+i>n/i>2+...+i>n/i>k+i>c/i>mod M (a1)。如申请专利范围第9项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，方程式(a1)将所有资料分为M个群组以存入每一记忆区块之M个记忆库，该方程式可为该指标向量(i>n/i>1,i>n/i>2,...,i>n/i>k)之任一函数，该指标向量可将同一群组中任两笔资料置入两个不同位址；当记忆库数量M=i>N/i>t，i>N/i>t为i>N/i>1，i>N/i>2，...，i>N/i>k其中之一，而(i>U/i>1，i>U/i>2，...，i>U/i>k-1)=(i>N/i>1，i>N/i>2，...，i>N/i>t-1，i>N/i>t+1，...，i>N/i>k)，(i>u/i>1，i>u/i>2，...，i>u/i>k-1)=(i>n/i>1，i>n/i>2，...，i>n/i>t-1，i>n/i>t+1，...，i>n/i>k)，而分解与计算顺序为i>N/i>1点快速傅立叶转换、i>N/i>2点快速傅立叶转换......至i>N/i>k点快速傅立叶转换或其逆向顺序，系以公式(a3)来决定资料位址；@sIMGTIF!d10012.TIF@eIMG!如申请专利范围第9项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，该指标向量系由分解下列方程式(a4)与(a5)于各阶段产生，其中i>N/i>=i>N/i>1i>N/i>2为例，离散傅立叶转换之定义为@sIMGCHAR!d10027.TIF@eIMG!，分解方程式(a4)与(a5)可将i>N/i>点离散傅立叶转换分解为两个较短点数之离散傅立叶转换，即i>N/i>1点离散傅立叶转换与i>N/i>2点离散傅立叶转换；分解方程式(a4)与(a5)中之系数i>A/i>2及i>B/i>1为正整数，输入及输出指标分别由该输入及输出方程式(a4)与(a5)转换；i>n/i>=i>N/i>2i>n/i>1+i>A/i>2i>n/i>2modi>N n/i>1,i>k/i>1=0,1,...,i>N/i>1-1 (a4)i>k/i>=i>B/i>1i>k/i>1+i>N/i>1i>k/i>2modi>N n/i>2,i>k/i>2=0,1,...,i>N/i>2-1 (a5)。如申请专利范围第9项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，对应于如申请专利范围第10项所述输入及输出方程式之该指标向量(i>n/i>1,i>n/i>2,...,i>n/i>k)可经由累加器之硬体运用而取得。如申请专利范围第9项所述之以记忆体为基础之正/逆向快速傅立叶转换处理器，其中，以该指标向量(i>n/i>1,i>n/i>2,...,i>n/i>k)而言，用以于第i>j/i>阶段计算i>N/i>i>j/i>点离散傅立叶转换而被存取之i>N/i>i>j/i>笔资料的每一群组系对应(i>n/i>1,i>n/i>2,...,i>n/i>i>j/i>-1,0,i>n/i>i>j/i>+1,...,i>n/i>k),(i>n/i>1,i>n/i>2,...,i>n/i>i>j/i>-1,1,i>n/i>i>j/i>+1,...,i>n/i>k),...,(i>n/i>1,i>n/i>2,...,i>n/i>i>j/i>-1，i>N/i>i>j/i>-1,i>n/i>i>j/i>+1,...,i>n/i>k)，且计算完成之输出资料系于计算后写回其原来位置，而上述所需之指标向量可由累加器之硬体运用而取得。 |
