信号处理整序算法程序设计与调试.docVIP

实验1 整序算法程序设计与调试 一、实验目的 使学生掌握整序算法的基本原理，为实现基2时域抽选的快速傅立叶变换算法做好准备，了解快速傅立叶变换算法的基本原理。 二、实验原理 1．原位计算 从基2时域抽选FFT运算流图可知，在某列进行蝶形运算的任意两个节点（行）k和j的节点变量就完全可以确定蝶形运算的结果，与其它行(节点)无关。这样，蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中，即实现所谓原位运算。 2．倒位序规律 由基2时域抽选FFT运算流图可知，输出X(k)按正常顺序排列在存储单元，而输入是按顺序：x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)，这些数据表面上是乱序的，实际上是有规律的，恰为二进制意义下的倒序，这种顺序称作倒位序。 设N=8点FFT运算，输入序列的序号为n，二进制为(n2n1 n0)2 ，倒位序顺序用n’表示，其倒位序二进制为(n0 n1 n2)2，如下表： 自然顺序n 二进制n2n1 n0 倒位序二进制n0 n1 n2 倒位顺序n’ 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 整序算法原理 输入序列先按自然顺序存入存储单元A，然后经整序（变址运算）来实现倒位序排列。 存储单元 A(0) A(1) A(2) A(3) A(4) A(5) A(6) A(7) 自然顺序I x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) 变址 倒位序 J x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) 图1：变址处理方法 其中I表示顺码，J表示倒码。从上图可以看出，只要按图中连线指示换位，就可以实现整序。可以看出I=J时不用换位，I≠J时换位。若IJ时已换位，IJ就不需要再换位了。通常把倒码和换位两个过程总称为整序。 三、实验内容 1．编写一个函数，求某个数的二进制倒码。 int IBR(int i，int m) 即求i的二进制倒码。其中m表示二进制位数。 例：若i=1,m=3；则1的3位二进制编码为001，001的倒码为100，100的十进制值为4，所以m=3时1的二进制倒码为4，即IBR（1，3）的值为4。 2．编写一个函数，实现整序功能。 void ReverseOrder(flaot A[],int m) 即实现将序列A中的数据按倒位序重新排列。其中m表示二进制位数。 例：若数组A中原有数据依次为：A0、A1、A2、A3、A4、A5、A6、A7，经过调用函数ReverseOrder（A，3）后，数组A中的数据依次为A0、A4、A2、A6、A1、A5、A3、A7，此时A中的数据表面上是乱序的，实际上是有规律的，恰为二进制意义下的倒序。 3．实验的测试 编写测试用的主程序，对已编写的IBR和ReverseOrder函数进行测试并给出测试结果。 实验代码 #include stdio.h #include math.h #define SCALE 2 #define LEN 8 int IBR(int i,int m); void ReverseOrder(float A[],int m); main() { int i,j,m; float A[LEN]; printf(Input the number and m:); scanf(%d%d,i,m); printf(\n%d\n,IBR(i,m)); printf(Input array A:); for (j=0;jLEN;j++) { scanf(%f,A[j]); } printf(Input m:); scanf(%d,m); ReverseOrder(A,m); } int IBR(int i,int m) { int a,b,c=-1,num[100]; int length=0; int result=0; b=i; i=i*SCALE; do { a=b%SCALE; c++; b=(b-a)/SCALE; i=i/SCALE; num[c]=a; length=c; }while(i/SCALE0); printf(reverse:); for(c=0;c=length;c++) { printf(%d,num[c]); re