目录
FFT实现高精度乘法 (2)
绪论 (2)
DFT（离散傅里叶变换） (4)
Cooley-Tukey算法实现FFT（快速傅里叶变换） (4)
位元反转（Bit reversal） (7)
C++算法实现 (8)
参考资料： (12)
FFT实现高精度乘法
绪论
对于这个课题，我们先从多项式开始一步一步进行分析。一个度数为n的多项式A(x)可以表示为：
一个多项式可以有不同的表示方式，一种是我们常见的系数表示，另一种是点值表示。例如上面的多项式就是以系数表示形式定义的。它展开之后可以写成下面这样：
这种方式的优点是很直观，也是我们最常用的表示多项式的方法，但是采用这种方式表示的多项式在进行大数值的乘法运算的时候，如果采用直接乘法方式，假设两个多项式的度数都为n, 那么乘法计算的时间复杂度为O(n2).
如果采用另一种不那么直观的点值表示法，对于多项式的度数比较大的情况，采用点值表示法进行乘法运算可以获得较大的性能提升。对于上面提到的多项式A(x), 它的点值表示法大概像下面这样子：
其中x0~x n-1是A(x)上面取的不同的点，而且
可以看出，多项式从系数表示形式直接转化为点值表示形式需要选取n（多项式的度数）个不同的值，进行n次的带入求值运算。那么转化为点值表示形式有什么好处呢？好处在于两个满足一定要求的点值表达式进行乘法运算的时间复杂度为O(n). 相对于系数表示法直接进行乘法运算，点值表达式在计算乘法的性能是很理想的。
现在我们来看看点值表达式是如何快速地进行多项式乘法的。假设有两个多项式A(x), B(x)，它们的乘积为一个新的多项式C(x)。在计算乘法的时候，多项式的项数可能会增加，因此乘法运算得到的新的多项式C(x)的度数是degree(C) = degree(A) + degree(B). 因为这个原因，在计算乘法的时候，需要对A(x)和B(x)进行点值表达式的扩张。也就是说多项式A(x), B(x)的点值表示形式要分别扩张为：
和
还有一点要注意的是上面两个式子中的x0~x2n-1是要一一对应的，否则不能直接进行乘法运算。这样C(x)就可以转化为A(x), B(x)的点值表达式的对应项相乘的结果：
这样，我们就能以O(n)的时间复杂度（不考虑点值表达式的扩张运算，只需要计算2n次乘法）进行多项式A(x)和B(x)之间的乘法运算。
那么接下来，我们要讨论的是如何进行多项式的点值表示形式和系数表示形式之间的转换，这里涉及到一个问题，就是多项式的插值转换的唯一性。也就是说你要确定从点值形式转化为系数形式是唯一的，这个问题已经被数学证明，插值转换是唯一的，这个是利用线性代数的范德蒙德矩阵（下图左方的矩阵）的可逆性来证明的，具体的证明就不贴上来了。而系数形式转化为点值形式可以有很多种不同的方案，因此不存在唯一性。
对于系数表达式转化为点值表达式，[1]称它为求值(evaluate)，我们可以利用秦九韶算法对给定的n个点进行代入多项式A(x)运算，这种方法的时间复杂度为O(n2). 对于点值表达式转化为系数表达式，[1]称它为插值(interpolate)，我们可以直接利用上图给出的线性代数方程，求出范德蒙德矩阵的逆矩阵，然后与向量上图右方的y向量相乘，计算出系数向量a, 用这种方法计算的时间复杂度从上图就能看出来，为O(n3). 也可以利用拉格朗日公式进行插值运算。
按拉格朗日公式计算系数表达式的时间复杂度为O(n2).
采用以上提到的方法进行系数表示形式和点值表示形式之间的转化的效率并不理想，因此我们要考虑如何快速进行两者之间的转化，这就是FFT需要解决的问题。
以下这张图就是解决这个问题的总体概览，我们不妨一窥全豹：
DFT（离散傅里叶变换）
上图中的求值(evaluation)和插值(interpolation)是分别通过DFT和反向DFT实现的。DFT是傅里叶分析的一种，它将一组有限的，均匀分布的函数样本值转化为一组复变正弦函数的系数。因为我看的资料大部分都是英文的，有些专业的词汇好像没有对应的翻译，为了严谨，这部分我就简单地说说DFT是怎么做的，尽力避免陈述其它的数学知识。
假定我们要进行对度数为n的多项式A(x)进行DFT，我们要将下列的值
代入A(x)分别求值，得到一个y向量，这个向量就是原先多项式的系数向量
的DFT，可以写为。
上式出现的叫做principal n th root of unity, 它的值为
这是最原始的计算DFT的方法，按这种方法计算的话，时间复杂度是O(n2). 接下来我们讨论如何进行反向DFT，其实反向DFT是很简单的，根据我们上面提到的插值转换的唯一性理论(Uniqueness of an interpolating polynomial)，我们进行DFT的运算实质是下面这样：
这样，我们只要求出中间的范德蒙德矩阵的逆矩阵，然后将与向量
相乘，就能得出系数向量，这就是反向DFT，计算的时间复杂度为O(n3)。能这样计算的前提是上图的范德蒙德矩阵是可逆的，当然它的可逆性已经被证明了，我这里就不写了。从上面的讨
论可以看到无论是DFT还是反向DFT，直接计算的时间复杂度都不是很理想，接下来我们就来讨论一下FFT 是如何降低计算DFT的时间复杂度的。
Cooley-Tukey算法实现FFT（快速傅里叶变换）
上文提到了DFT是什么以及如何进行DFT和反向DFT运算，现在我们来讨论FFT是如何快速进行DFT 的。我们在上文提到过一个数值，这个数值有个有意思的特性，根据Halving lemma, 下式是成立的：
其中k为非负整数。这个等式是FFT得以实现的关键。值得一提的是FFT的实现的算法有多种，我们这里讨论的FFT算法是基于[1]的。这本书上提到的FFT算法叫做Cooley-Tukey算法，它是目前为止应用得最广泛的FFT算法。从现在开始，如果没有别的说明，我们就以FFT算法来称呼Cooley-Tukey算法。
假设我们有一个以系数形式表示的多项式A(x)，它的度数为n，n为2的幂。那么它可以表示为
现在我们将它分成更小的两个多项式和，它们分别满足如下关系：
那么拆分出来的两个多项式和原来的多项式有如下关系：
这样的处理就是分治的基本步骤，将代入进行DFT的问题就可以转化为：
1、将代入度数为n / 2的和分别求值；
2、将计算出来的结果根据上文提到的递归关系合并成最终的结果。
根据Halving lemma，并不是n个各不相同的值，它有一半是重复的。这样我们就能将问题的规模缩小成原来的二分之一，这是能够利用递归提升效率的关键。现在我们就能够根据上面的分析写出FFT的递归算法了，但递归算法的效率不高，接下来我们要讨论FFT算法的非递归实现。
我们来分析一下递归形式的FFT的步骤是怎么样的，假设我们要对元素个数为8的向量进行FFT运算，下面是自顶向下的递归的步骤：
运算的逻辑步骤是一颗树，而且我们猜想叶子结点的元素排列序号与根节点的元素排列序号应该有一定的联系。我们只要找出两者之间的联系，就可以通过它们之间的关系直接计算出递归最深层的元素排列序列，然后直接从最底层开始进行运算，用计算出的DFT替换掉上一层的节点，重复这个步骤直到根节点为止。这样我们就能将自顶向下的递归形式的FFT算法改进成自底向上的迭代形式的算法了。
为了分析它们之间的关系，我们打算从元素的下标着手，原始序列是0, 1, 2, 3, 4, 5, 6, 7, 它们的二进制表示分别为000, 001, 010, 011, 100, 101, 110, 111. 最底层的元素排列序列的下标是0, 4, 2, 6, 1, 5, 3, 7. 它们的二进制
从表中可以看出原始的序列和最终的序列的对应位置的下标是互为相反位。也就是说原始序列的对应位置的下标进行位元反转运算就能得到最终序列。这样我们就能够利用这个关系着手实现FFT算法的迭代形式了。
算法实现的伪代码如下：
其中BIT-REVERSE-COPY将我们要进行FFT的a向量按照位元反转位置复制到另一个向量A，复制完成之后的A就是我们要进行递归运算的最终序列。它的伪代码如下：
其中rev实现位元反转，关于位元反转的具体问题我们在后面还会提到，现在我们来分析一下FFT非递归算法解决问题的步骤。在ITERA TIVE-FFT中按照树形结构的运算逻辑从底层开始往上运算，第3行控制整个迭代的次数；第4行确定当前层数的元素对大小；第5行确定该层的螺旋因子；第8行~第13行是主要的运算逻辑，称为“蝶形运算”，在这里完成被分割为左右两部分的元素组的DFT运算。
以上就是FFT的大体叙述，FFT在计算大整数乘法中是一个比较重要的部分，它为大整数乘法提供了优化方案，是目前实现大整数乘法的一种优秀算法。接下来我们要讨论在C++下，利用FFT实现大整数乘法要考虑的细节问题。
位元反转（Bit reversal）
我们回顾一下之前在非递归形式的FFT中提到的位元反转问题，[1]中并没有给出位元反转的伪代码，但有提到我们可以实现时间复杂度为O(log n)的位元反转算法。更进一步，如果我们采用表映射的方式，我们还能以近乎O(1)的时间复杂度实现位元反转，只是我们可能需要比较多的内存空间，具体需要多少空间取决于计算机硬件和编译器。
进行位元反转的简单算法可以用伪代码描述如下：
这种通过移位来完成位元反转的时间复杂度为O(k), k为整数的位数。假如我们采用这种方法进行位元反转的话，那么在上面的FFT的非递归算法中BIT-REVERSE-COPY的时间复杂度就是O(nk)。一般来说，在大整数乘法中，要进行位元反转的元素个数是很多的，因此n远大于k，可以将k看成一个对效率影响不大的常数，BIT-REVERSE-COPY的时间复杂度可以认为是O(n).
我们在上面做的只是按照传入的数值进行一次位元反转，假如要进行反转的数有n个，那么就要调用n次上面的方法，不过我们在实现时可以将上述算法改写成内联函数以提高效率。如果不采用上面那种逐个计算的方法的话，还有下面这种方法。
其中a是长度为length的数组，算法执行完后，从a[0]到a[lengt-1]都保存了与下标对应的位反转的值。这种方法计算的次数会减少很多，但是需要O(n)的空间来保存计算出的数据。我们可以通过直接读取a数组中的数据来获得位反转的值，这就是表映射的基本思想。
因为要计算位元反转的元素的个数很多，假如我们能提高位元反转算法的效率的话，将会带来一定程度的性能提升。高效的位元反转算法要综合考虑计算机硬件和编译器的优化策略，在进行编程时我们可以根据具体情况，对位元反转进行相关的优化。一般来说，采用表映射的方法来实现位元反转已经能够满足性能需求了，在下面的算法实现中我们就采用了这种方案。如果要追求极致的性能的话，我们还可以进行C++代码内嵌汇编，根据CPU的指令集进行更进一步的优化。相关问题的讨论已经超出了本文的范围，如果你有兴趣，可以参考[8].
C++算法实现
以下是C++算法实现的清单，代码在Visual Studio Community 2015下编译通过。
#define_USE_MATH_DEFINES
#include
using namespace std;
// 复数类
class Complex
{
public:
// 构造器
Complex(long double real = 0.0, long double imaginary = 0.0) {
this->real = real;
this->imaginary = imaginary;
}
// 重载运算符
inline Complex operator +(const Complex &anotherComplex) {
return Complex(this->real + anotherComplex.real, this->imaginary + anotherComplex.imaginary);
}
inline Complex operator -(const Complex &anotherComplex) {
return Complex(this->real - anotherComplex.real, this->imaginary - anotherComplex.imaginary);
}
inline Complex operator *(const Complex &anotherComplex) {
return Complex(((this->real*anotherComplex.real) - (this->imaginary*anotherComplex.imaginary)), ((this->real*anotherComplex.imaginary) + (this->imaginary*anotherComplex.real)));
}
// 为了操作方便和提高效率，就不把它们声明为私有了
long double real, imaginary;
};
/// 这些变量放在外面是为了方便，编译器会自动帮我们分配堆空间
const int MAX_LENGTH = 200010;
char str1[MAX_LENGTH / 2], str2[MAX_LENGTH / 2];
Complex aPointValues[MAX_LENGTH], bPointValues[MAX_LENGTH];
long long sum[MAX_LENGTH];
unsigned long long *bitReverseLookupTable;
// 以2的幂为基准进行对齐
size_t alignByPowerOf2(const size_t lengthOfStr1, const size_t lengthOfStr2) { size_t roof = 1;
while ((roof < (lengthOfStr1 << 1)) || (roof < (lengthOfStr2 << 1))) {
roof <<= 1;
}
for (size_t i = 0; i < lengthOfStr1; i++) {
aPointValues[i] =Complex(str1[i] - '0', 0);
}
for (size_t i = 0; i < lengthOfStr2; i++) {
bPointValues[i] =Complex(str2[i] - '0', 0);
}
return roof;
}
// 点值表达式乘法运算
void pointValueMultiply(size_t length) {
for (size_t i = 0; i < length; i++) {
aPointValues[i] = aPointValues[i] * bPointValues[i];
}
}
// 计算位元反转映射表
void computeBitReverseLookupTable(size_t size) {
bitReverseLookupTable[0] = 0, bitReverseLookupTable[1] = size >> 1;
for (int k = 2; k < size; k += 2) {
bitReverseLookupTable[k] = bitReverseLookupTable[k >> 1] >> 1;
bitReverseLookupTable[k + 1] = bitReverseLookupTable[k] ^ bitReverseLookupTable[1];
}
}
// 位元反转交换
void bitReverseShuffle(Complex values[], size_t length) {
for (size_t i = 0; i < length; i++) {
// 避免元素自身交换和再次交换
if (i < bitReverseLookupTable[i]) {
swap(values[i], values[bitReverseLookupTable[i]]);
}
}
}
// 迭代形式的FFT，基本上按照算法导论的来做
void FFT(Complex sampleValues[], size_t length, bool inverse) {
bitReverseShuffle(sampleValues, length);
for (int i = 2; i <= length; i <<= 1) {
// DFT和反向DFT中e的幂不同，根据欧拉公式需要进行正负转换
long double tempValue = ((inverse) ? (1) : (-1)) * 2 * M_PI / i;
// 根据欧拉公式做出的变换
Complex wn(cos(tempValue), sin(tempValue));
for (size_t j = 0; j < length; j += i) {
Complex w(1, 0);
// Butterfly operation
for (size_t k = j; k < j + (i >> 1); k++) {
Complex u = sampleValues[k];
Complex t = w*sampleValues[k + (i >> 1)];
sampleValues[k] = u + t;
sampleValues[k + (i >> 1)] = u - t;
w = w*wn;
}
}
}
// 反向DFT
if (inverse) {
for (int i = 0; i < length; i++) {
sampleValues[i].real /= length;
}
}
}
void adjustResult(size_t size) {
// 取整
for (size_t i = 0; i < size; i++) {
sum[i] = llroundl(aPointValues[i].real);
}
// 进位
for (size_t i = size - 1; i > 0; i--) {
sum[i - 1] += sum[i] / 10;
sum[i] %= 10;
}
}
void outputResult(size_t resultSize) {
// 关闭流同步以提升输出效率
ios::sync_with_stdio(false);
for (size_t i = 0; i < resultSize; i++) {
cout << sum[i];
}
cout << endl;
}
// 输入两个大整数，以十进制表示，位长度均不超过100000
bool inputString() {
return !(cin >> str1 >> str2).fail();
}
// 清理点值表达式数组
void flushPointValues() {
memset(aPointValues, 0, MAX_LENGTH*sizeof(Complex));
memset(bPointValues, 0, MAX_LENGTH*sizeof(Complex));
}
int main() {
size_t length;
size_t lengthOfStr1, lengthOfStr2;
// 输入数据
while (inputString())
{
lengthOfStr1 = strlen(str1), lengthOfStr2 = strlen(str2);
length = alignByPowerOf2(lengthOfStr1, lengthOfStr2);
// 申请位元反转映射表的存储空间
bitReverseLookupTable = new u nsigned long long[length];
// 计算位元反转映射表
computeBitReverseLookupTable(length);
// 利用FFT算法进行DFT
FFT(aPointValues, length, false);
FFT(bPointValues, length, false);
// 点值乘法运算
pointValueMultiply(length);
// 利用FFT算法进行反向DFT
FFT(aPointValues, length, true);
// 调整结果
adjustResult(length);
// 输出结果
outputResult(lengthOfStr1 + lengthOfStr2 - 1);
// 清理
flushPointValues();
}
}
参考资料：
[1]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Third
Edition, the MIT press, 2009
[2]Richard J. Fateman. Exact polynomial multiplication using approximate FFT, University of California Berkeley, 2006
[3]Richard J. Fateman. When is FFT multiplication of arbitrary-precision polynomials practical, University of California
Berkeley, 2006
[4]Multiplication algorithm.https://https://www.doczj.com/doc/7a10968264.html,/wiki/Multiplication_algorithm#Fourier_transform_methods
[5]Sch?nhage–Strassen algorithm.https://https://www.doczj.com/doc/7a10968264.html,/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm
[6]Discrete Fourier transform.https://https://www.doczj.com/doc/7a10968264.html,/wiki/Discrete_Fourier_transform#Polynomial_multiplication
[7]快速傅里叶变换. https://www.doczj.com/doc/7a10968264.html,/iamzky/article/details/22712347
[8]Best Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C.
https://www.doczj.com/doc/7a10968264.html,/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c
多项式乘多项式试题精选（二） 一．填空题（共13小题） 1．如图，正方形卡片A类、B类和长方形卡片C类各若干张，如果要拼一个长为（2a+b），宽为（a+b）的长方形，则需要C类卡片_________张． 2．（x+3）与（2x﹣m）的积中不含x的一次项，则m=_________． 3．若（x+p）（x+q）=x2+mx+24，p，q为整数，则m的值等于_________． 4．如图，已知正方形卡片A类、B类和长方形卡片C类各若干张，如果要拼成一个长为（a+2b）、宽为（a+b）的大长方形，则需要A类卡片_________张，B类卡片_________张，C类卡片_________张． 5．计算： （﹣p）2?（﹣p）3=_________；=_________；2xy?（_________）=﹣6x2yz；（5﹣a）（6+a）=_________． 6．计算（x2﹣3x+1）（mx+8）的结果中不含x2项，则常数m的值为_________． 7．如图是三种不同类型的地砖，若现有A类4块，B类2块，C类1块，若要拼成一个正方形到还需B类地砖 _________块． 8．若（x+5）（x﹣7）=x2+mx+n，则m=_________，n=_________． 9．（x+a）（x+）的计算结果不含x项，则a的值是_________． 10．一块长m米，宽n米的地毯，长、宽各裁掉2米后，恰好能铺盖一间房间地面，问房间地面的面积是_________平方米． 11．若（x+m）（x+n）=x2﹣7x+mn，则﹣m﹣n的值为_________． 12．若（x2+mx+8）（x2﹣3x+n）的展开式中不含x3和x2项，则mn的值是_________． 13．已知x、y、a都是实数，且|x|=1﹣a，y2=（1﹣a）（a﹣1﹣a2），则x+y+a3+1的值为_________．
一、计算 1．a2·(-a)5·(-3a)3 2．[(a m)n]p 3．(-mn)2(-m2n)3 4．(-a2b)3·(-ab2) 5．(-3ab)·(-a2c)·6ab2 6．(-ab)3·(-a2b)·(-a2b4c)27．(3m-n)(m-2n)． 8．(x+2y)(5a+3b)． 9．5x(x2+2x+1)-(2x+3)(x-5) 10. (－2x－5)(2x－5) 11. －(2x2+3y)(3y－2x2) 12. (a－5) 2－(a+6)(a－6)
13. (2x －3y )(3y +2x )－(4y － 3x )(3x +4y ) 14. 3(2x +1)(2x －1)－2(3x +2)(2－ 3x ) 15. (31x +y )(31x －y )(9 1x 2+y 2) 16. )1)(1)(1)(1(42x x x x ++-+ 二、基础训练 1．多项式8x 3y 2-12xy 3z 的公因式是_________． 2．多项式-6ab 2+18a 2b 2-12a 3b 2 c 的公因式是（ ） A ．-6ab 2c B ．-ab 2 C ．-6ab 2 D ．-6a 3b 2c 3．下列用提公因式法因式分解正确的是（ ） A ．12abc-9a 2b 2 =3abc （4-3ab ） B ．3x 2y-3xy+6y=3y （x 2-x+2y ） C ．-a 2+ab-ac=-a （a-b+c ） D ．x 2y+5xy-y=y （x 2+5x ） 4．下列多项式应提取公因式5a 2b 的是（ ） A ．15a 2b-20a 2b 2 B ．30a 2b 3-15ab 4-10a 3b 2 C ．10a 2b-20a 2b 3+50a 4b D ．5a 2b 4-10a 3b 3+15a 4b 2 5．下列因式分解不正确的是（ ） A ．-2ab 2+4a 2b=2ab （-b+2a ） B ．3m （a-b ）-9n （b-a ）=3（a-b ）（m+3n ） C ．-5ab+15a 2bx+25ab 3y=-5ab （-3ax-5b 2y ）; D ．3ay 2-6ay-3a=3a （y 2-2y-1） 6．填空题： （1）ma+mb+mc=m （________）； （2）多项式32p 2q 3-8pq 4m 的公因式是_________； （3）3a 2-6ab+a=_________（3a-6b+1）；（4）因式分解：km+kn=_________； （5）-15a 2+5a=________（3a-1）； （6）计算：21××=_________． 7．用提取公因式法分解因式： （1）8ab 2-16a 3b 3； （2） -15xy-5x 2； （3）a 3b 3+a 2b 2-ab ； （4） -3a 3m-6a 2m+12am ． 8．因式分解：-（a-b ）mn-a+b ． 三、提高训练 9．多项式m （n-2）-m 2（2-n ）因式分解等于（ ） A ．（n-2）（m+m 2） B ．（n-2）（m-m 2） C ．m （n-2）（m+1） D ．m （n-2）（m-1）
班级：学号：姓名 实验二FFT算法的MATLAB实现 （一）实验目的： （1）掌握用matlab进行FFT在数字信号处理中的高效率应用。 （2）学习用FFT对连续信号和时域离散信号进行谱分析。 （二）实验内容及运行结果： 题1：若x(n)=cos(nπ/6)是一个N=12的有限序列，利用MATLAB计算它的DFT 并进行IDFT变换同时将原图与IDFT变换后的图形进行对比。当求解IFFT变换中，采样点数少于12时，会产生什么问题。 程序代码： N=12; n=0:11; Xn=cos(n*pi/6); k=0:11; nk=n'*k; WN=exp(-j*2*pi/N) WNnk=WN.^nk XK=Xn*WNnk; figure(1) stem(Xn) figure(2) stem(abs(XK)) 运行结果：
IFFT变换中，当采样点数少于12时图像如下图显示：
分析：由图像可以看出，当采样点数小于12时，x(n)的频谱不变，周期为6，而XK 的频谱图发生改变。 题2：对以下序列进行谱分析 132()()103()8470x n R n n n x n n n =+≤≤?? =-≤≤??? 其他n 选择FFT 的变换区间N 为8和16点两种情况进行频谱分析，分别打印其幅频特 性曲线并进行对比、分析和讨论。 ㈠ 程序代码： x=ones(1,3);nx=0:2; x1k8=fft(x,8); F=(0:length(x1k8)-1)'*2/length(x1k8); %进行对应的频率转换 stem(f,abs(x1k8));%8点FFT title('8点FFTx_1(n)'); xlabel('w/pi'); ylabel('幅度'); N=8时：
5．多项式与多项式相乘 一、选择题 1.计算(2a－3b)(2a＋3b)的正确结果是() A．4a2＋9b2B．4a2－9b2C．4a2＋12ab＋9b2D．4a2－12ab＋9b2 2.若(x＋a)(x＋b)＝x2－kx＋ab，则k的值为() A．a＋b B．－a－b C．a－b D．b－a 3.计算(2x－3y)(4x2＋6xy＋9y2)的正确结果是() A．(2x－3y)2B．(2x＋3y)2C．8x3－27y3D．8x3＋27y3 4.(x2－px＋3)(x－q)的乘积中不含x2项，则() A．p＝q B．p＝±q C．p＝－q D．无法确定 5.若0＜x＜1，那么代数式(1－x)(2＋x)的值是() A．一定为正B．一定为负C．一定为非负数D．不能确定6.计算(a2＋2)(a4－2a2＋4)＋(a2－2)(a4＋2a2＋4)的正确结果是() A．2(a2＋2)B．2(a2－2)C．2a3D．2a6 7.方程(x＋4)(x－5)＝x2－20的解是() A．x＝0 B．x＝－4 C．x＝5 D．x＝40 8.若2x2＋5x＋1＝a(x＋1)2＋b(x＋1)＋c，那么a，b，c应为() A．a＝2，b＝－2，c＝－1 B．a＝2，b＝2，c＝－1 C．a＝2，b＝1，c＝－2 D．a＝2，b＝－1，c＝2 9.若6x2－19x＋15＝(ax＋b)(cx＋d)，则ac＋bd等于() A．36 B．15 C．19 D．21 10.(x＋1)(x－1)与(x4＋x2＋1)的积是() A．x6＋1 B．x6＋2x3＋1 C．x6－1 D．x6－2x3＋1 二、填空题 1.(3x－1)(4x＋5)＝_________． 2.(－4x－y)(－5x＋2y)＝__________． 3.(x＋3)(x＋4)－(x－1)(x－2)＝__________． 4.(y－1)(y－2)(y－3)＝__________． 5.(x3＋3x2＋4x－1)(x2－2x＋3)的展开式中，x4的系数是__________．
3．多项式与多项式相乘 一、选择题 1.计算(2a－3b)(2a＋3b)的正确结果是() A．4a2＋9b2B．4a2－9b2C．4a2＋12ab＋9b2D．4a2－12ab＋9b2 2.若(x＋a)(x＋b)＝x2－kx＋ab，则k的值为() A．a＋b B．－a－b C．a－b D．b－a 3.计算(2x－3y)(4x2＋6xy＋9y2)的正确结果是() A．(2x－3y)2B．(2x＋3y)2C．8x3－27y3D．8x3＋27y3 4.(x2－px＋3)(x－q)的乘积中不含x2项，则() A．p＝q B．p＝±q C．p＝－q D．无法确定 5.若0＜x＜1，那么代数式(1－x)(2＋x)的值是() A．一定为正B．一定为负C．一定为非负数D．不能确定 6.计算(a2＋2)(a4－2a2＋4)＋(a2－2)(a4＋2a2＋4)的正确结果是() A．2(a2＋2)B．2(a2－2)C．2a3D．2a6 7.方程(x＋4)(x－5)＝x2－20的解是() A．x＝0 B．x＝－4 C．x＝5 D．x＝40 8.若2x2＋5x＋1＝a(x＋1)2＋b(x＋1)＋c，那么a，b，c应为() A．a＝2，b＝－2，c＝－1 B．a＝2，b＝2，c＝－1 C．a＝2，b＝1，c＝－2 D．a＝2，b＝－1，c＝2 9.若6x2－19x＋15＝(ax＋b)(cx＋b)，则ac＋bd等于() A．36 B．15 C．19 D．21 10.(x＋1)(x－1)与(x4＋x2＋1)的积是() A．x6＋1 B．x6＋2x3＋1 C．x6－1 D．x6－2x3＋1 二、填空题 1.(3x－1)(4x＋5)＝__________． 2.(－4x－y)(－5x＋2y)＝__________． 3.(x＋3)(x＋4)－(x－1)(x－2)＝__________． 4.(y－1)(y－2)(y－3)＝__________．
#include a[i]=0; len_align=len_b; } return len_align; } //该函数通过删去大整数前面无意义的0来得到其真实的数字位数 int Adjust(int a[],int len) { while(a[0]==0) { int j=1; do{ a[j-1]=a[j]; j++; }while(j 1 引言 CCS(Code Composer Studio)是TI公司的DSP集成开发环境。它提供了环境配置、源文件编辑、程序调试、跟踪和分析等工具,帮助用户在一个软件环境下完成编辑、编译链接、调试和数据分析等工作。与TI提供的早期软件开发工具相比,利用CCS能够加快软件开发进程,提高工作效率。CCS一般工作在两种模式下:软件仿真器和与硬件开发板相结合的在线编程。前者可以脱离DSP芯片,在PC机上模拟DSP指令集与工作机制,主要用于前期算法实现和调试。后者实时运行在DSP芯片上,可以在线编制和调试应用程序。 2 C语言和汇编语言的混合编程 TMS320 C5000系列的软件设计通常有三种方法: (1) 用C语言开发; (2) 用汇编语言开发; (3) C和汇编的混合开发。 其中用C语言开发具有兼容性和可移植的优点,有利于缩短开发周期和减少开发难度,但是在运算量较大的情况下,C代码的效率还是无法和手工编写的汇编代码的效率相比,比如FFT运算,用汇编语言开发的效率高,程序执行速度快,而且可以合理利用芯片的硬件资源,但是开发难度较大,开发周期长,而且可读性和可移植性差。C和汇编的混合编程则可以充分利用前两者的优点,以达到最佳利用DSP资源的目的。但是,采用C和汇编语言混合编程必须遵循相关函数调用规则和寄存器调用规则,否则会给程序的开发带来意想不到的问题。 2.1 C语言和汇编语言混合编程的四种方法 (1) 独立编写汇编程序和C程序,分开编译或汇编成各自的目标代码模块,再用链接器将二者链接起来。这种方法比较灵活,但是设计者必须自己维护各汇编模块的入口和出口代码,自己计算传递的参数在堆栈中的偏移量,工作量较大,但是能做到对程序的绝对控制。 (2) 在C程序中使用汇编程序中定义的变量和常数。 (3) 在C程序中内嵌汇编语句。这种方法可以实现C语言无法实现的一些硬件控制功能,如修改中断控制寄存器。 (4) 将C语言编译生成相应的汇编代码,手工修改和优化C编译器生成的汇编代码。采用这种方法可以控制C编译器,从而产生具有交叉列表的汇编程序,而设计者可以对其中的汇编语句进行修改,然后对汇编程序进行编译,产生目标文件。 整式乘法：多项式乘多项式习题（4） 一、选择题 1.计算(2a－3b)(2a＋3b)的正确结果是() A．4a2＋9b2B．4a2－9b2C．4a2＋12ab＋9b2D．4a2－12ab＋9b2 2.若(x＋a)(x＋b)＝x2－kx＋ab，则k的值为() A．a＋b B．－a－b C．a－b D．b－a 3.计算(2x－3y)(4x2＋6xy＋9y2)的正确结果是() A．(2x－3y)2B．(2x＋3y)2C．8x3－27y3D．8x3＋27y3 4.(x2－px＋3)(x－q)的乘积中不含x2项，则() A．p＝q B．p＝±q C．p＝－q D．无法确定 5.若0＜x＜1，那么代数式(1－x)(2＋x)的值是() A．一定为正B．一定为负C．一定为非负数D．不能确定6.计算(a2＋2)(a4－2a2＋4)＋(a2－2)(a4＋2a2＋4)的正确结果是() A．2(a2＋2)B．2(a2－2)C．2a3D．2a6 7.方程(x＋4)(x－5)＝x2－20的解是() 8.A．x＝0 B．x＝－4 C．x＝5 D．x＝40 9.若2x2＋5x＋1＝a(x＋1)2＋b(x＋1)＋c，那么a，b，c应为() A．a＝2，b＝－2，c＝－1 B．a＝2，b＝2，c＝－1 C．a＝2，b＝1，c＝－2 D．a＝2，b＝－1，c＝2 10.若6x2－19x＋15＝(ax＋b)(cx＋b)，则ac＋bd等于() A．36 B．15 C．19 D．21 11.(x＋1)(x－1)与(x4＋x2＋1)的积是() A．x6＋1 B．x6＋2x3＋1 C．x6－1 D．x6－2x3＋1 二、填空题 1.(3x－1)(4x＋5)＝__________． 2.(－4x－y)(－5x＋2y)＝__________． 3.(x＋3)(x＋4)－(x－1)(x－2)＝__________． 4.(y－1)(y－2)(y－3)＝__________． 5.(x3＋3x2＋4x－1)(x2－2x＋3)的展开式中，x4的系数是__________． 大整数乘法问题 一、问题分析 （1）采用分治法的思想，将一个多位的二进制数分成几个位数较少的二进制数进行计算。这样不断地往下分，直到分出的二进制数相对简单，可以直接算出来。 （2）对于这个算法，上课时讲过了时间复杂度为O（n^1.59）。 二、问题解决 （1）具体程序代码（c++） #include int a[M],b[M],c[M],d[M]; int wy[M],xz[M],wz[M],xy[M]; int *aa,*bb,*cc,*dd; int mid; int i,j; int Ji[M],k=0; if(n==1) { Ji[k]=u[0]*v[0]; k++; return(Ji); } else { mid=(n+1)/2; for(i=0;i 单元测验 一、判断题1.x 5·x 5=2x 5.( )2.a 2·a 3=a 6.( ) 3.( 21 xy 2)3=2 1x 3y 6.( )二、填空题(每小题2分，共20分) 2.(－b )2·(－b )3·(－b )5= . 3.3. －2a (3a －4b )= . 4. (9x +4)(2x －1)= . 5. (3x +5y )· = 9x 2－25y 2. 6. (x +y )2－ = (x －y )2. 7. 若x 2+x +m 是一个完全平方式，则m = . 8. 若2x +y =3,则4x ·2y = . 9.若x (y －1)－y (x －1)=4, 则2 2 2y x －xy = . 10. 若m 2+m －1=0,则m 3+2m 2+2001= . 三、选择题(每小题3分，共24分) 1. 下列计算正确的是( ) A.2x 3·3x 4=5x 7 B.3x 3·4x 3=12x 3 C.2a 3+3a 3=5a 6 D.4a 3·2a 2=8a 5 2. 下列多项式中是完全平方式的是( ) A.2x 2+4x －4 B.16x 2－8y 2+1 C.9a 2－12a +4 D.x 2y 2+2xy +y 2 4. 两个连续奇数的平方差是( ) A. 6的倍数 B. 8的倍数 C. 12的倍数 D. 16的倍数 5. 已知x +y =7,xy =－8,下列各式计算结果不正确的是( ) A. (x －y )2=81 B. x 2+y 2=65 C. x 2+y 2=33 D. x 2－y 2=±63 7. (－135)1997×(－253 )1997等于( ) A.－1 B.1 C.0 D.1997 8. 已知a －b =3,那么a 3－b 3－9ab 的值是( ) A.3 B.9 C.27 D.81 四、计算(每小题5分，共20分) 1.(x －2)2(x +2)2·(x 2+4) 2. 2.(5x +3y )(3y －5x )－(4x －y )(4y +x ) 五、解方程(组)(每小题5分，共10分) (3x +2)(x-1)=3(x +1)(x +1) 六、求值题(每小题5分，共10分) 1.已知(x －y )2=6 x +y =5求xy 的值. 3.(a -b )2=(a +b )2+_____. 4.化简：4(a +b )+2(a +b )－5(a +b )=_____. 5.x +y =－3,则32－2x －2y =_____. 12.若3x =12，3y =4，则27x －y =_____. 6.(x +2)(3x －a )的一次项系数为－5，则a =_____. 第3课时 多项式与多项式相乘 要点感知 多项式与多项式相乘，先用一个多项式的_____乘另一个多项式的_____，再把所得的积_____.(a +b )(p +q )=_____. 预习练习1－1 填空：(1)(a +4)(a +3)=a ·a +a ·3+4·_____+4×3=_____; (2)(2x －5y )(3x －y )=2x ·3x +2x ·_____+(－5y )·3x +(－5y )·_____=_____. 1－2 计算:(x +5)(x －7)=_____；(2x －1)·(5x +2)=_____. 知识点1 直接运用法则计算 1.计算： (1)(m +1)(2m －1)； (2)(2a －3b )(3a +2b )； (3)(2x －3y )(4x 2+6xy +9y 2)； (4)(y +1)2； (5)a (a －3)+(2－a )(2+a ). 2.先化简，再求值：(2x －5)(3x +2)－6(x +1)(x －2),其中x =5 1. 知识点2 多项式乘以多项式的应用 3.若一个长方体的长、宽、高分别是3x －4,2x －1和x ，则它的体积是( ) －5x 2+4x －11x 2+4x －4x 2 －4x 2+x +4 4.为参加市里的“灵智星”摄影大赛，小阳同学将同学们参加“义务献爱心”活动的照片放大为长为a 厘米，宽为 43a 厘米的长方形形状，又精心在四周加上了宽2厘米的装饰彩框，那么小阳同学的这幅摄影作品照片占的面积是_____平方厘米. 5.我校操场原来的长是2x 米，宽比长少10米，现在把操场的长与宽都增加了5米，则整个操场面积增加了_____平方米. 知识点3 (x +p )(x +q )=x 2+(p +q )x +pq 6.下列多项式相乘的结果为x 2+3x －18的是( ) A.(x －2)(x +9) B.(x +2)(x －9) C.(x +3)(x －6) D.(x －3)(x +6) 7.已知(x +1)(x －3)=x 2+ax +b ，则a ,b 的值分别是( ) =2，b =3 =－2，b =－3 =－2，b =3 =2，b =－3 8.计算： (1)(x +1)(x +4) (2)(m －2)(m +3) (3)(y +4)(y +5) (4)(t －3)(t +4). 9.计算： (1)(m －2n )(－m －n )； (2)(x 3－2)(x 3+3)－(x 2)3+x 2·x ； 大数乘法算法 实际上也可以拿相似的思想做大数相乘，只是把输入源从链表变为数组即可。 基本原理： 1，把两个数字a和b转换成字符，放到字符数组里；或者把数字的每一位隔离开分别放到数组里作为一位，这样更方便乘法处理。这样做的根本好处是：相乘的时候不会造成溢出。 2，结果数组的长度，最大应该是a的长度+b的长度+1，所以定义一个这样的数组； 3，过程很简单了：a中的第i位乘以b中的第j位，保存在c中的第i+j位； 4，后期处理。注意，经过第三步处理过的c中的结果，每一位都可能向高位进位；比如说，c[8]=24.这时候就要从低位开始把进位部分向高位加，一次循环即可： for(i=0;i A1=str2double(get(handles.edit8,'String')); A2=str2double(get(handles.edit9,'String')); F1=str2double(get(handles.edit10,'String')); F2=str2double(get(handles.edit11,'String')); Fs=str2double(get(handles.edit12,'String')); N=str2double(get(handles.edit13,'String')); t=[0:1/Fs:(N-1)/Fs]; x=A1*sin(2*pi*F1*t)+A2*sin(2*pi*F2*t); %信号x的离散值 axes(handles.axes1) %在axes1中作原始信号图 plot(x); grid on m=nextpow2(x);N=2^m; % 求x的长度对应的2的最低幂次m if length(x) 多项式乘多项式:（a+b)(c+d)= (x+a)(x+b)= 平方差公式： (a+b)(a-b)= 完全平方公式：(a+b)2= (a-b)2= 1．化简()()()a b c b c a c a b ---+-的结果是（ ） A ．222ab bc ac ++ B ．22ab bc - C ．2ab D ．2bc - 2．下列各式中计算错误的是（ ） A ．3 4 2 2(231)462x x x x x x -+-=+- B ．2 3 2 (1)b b b b b b -+=-+ C ．231 (22)2 x x x x - -=-- D ． 342232(31)2323 x x x x x x -+=-+ 3．若（8×106）（5×102）（2×10）＝M ×10a ，则M 、a 的值为（ ） A ．M ＝8，a ＝8 B ．M ＝8，a ＝10 C ．M ＝2，a ＝9 D ．M ＝5，a ＝10 4、若2x 2＋5x ＋1＝a (x ＋1)2＋b (x ＋1)＋c ，那么a ，b ，c 应为( ) A ．a ＝2，b ＝－2，c ＝－1 B ．a ＝2，b ＝2，c ＝－1 C ．a ＝2，b ＝1，c ＝－2 D ．a ＝2，b ＝－1，c ＝2 5、.若))((b x a x +-的乘积中不含x 的一次项,则b a ,的关系是( ) A.互为倒数 B.相等 C.互为相反数 D.b a ,都为0 6、.下列各式中,不能用平方差公式计算的是( ) A.)43)(34(x y y x --- B.)2)(2(2 222y x y x +- C.))((a b c c b a +---+ D.))((y x y x -+- 7、.下列各式中，相等关系一定成立的是 （ ） A 、22)()(x y y x -=- B 、6)6)(6(2 -=-+x x x C 、2 22)(y x y x +=+ D 、)6)(2()2()2(6--=-+-x x x x x 8．若9x 2＋4y 2＝（3x ＋2y ）2＋M ，则 M 为（ ） A ．6xy B ．－6xy C ．12xy D ．－12xy 9．下列等式不能恒成立的是（ ） A ．（3x －y ）2＝9x 2－6xy ＋y 2 B ．（a ＋b －c ）2＝（c －a －b ）2 C ．（0.5m －n ）2＝0.25m 2－mn ＋n 2 D ．（x －y ）（x ＋y ）（x 2－y 2）＝x 4－y 4 10、已知（x+3）（x-2）=x 2 +ax+b ，则a 、b 的值分别是（ ） A ．a=-1，b=-6 B ．a=1，b=-6 C ．a=-1，b=6 D ．a=1，b=6 11. 观察下列算式：12=2，22=4，32=8，42=16，52=32，62=64，72=128，8 2=256，…… 根据其规律可知10 8的末位数是（ ） A 、2 B 、4 C 、6 D 、8 《多项式乘以多项式》教学设计 朱宾琪教学目标： 知识与技能： 1、探索多项式与多项式相乘的乘法法则。 2. 能灵活地进行整式的乘法运算。 过程与方法： 1、经历探索多项式与多项式相乘的乘法法则的过程，体会乘法分配律的作用以及“整体”和“转化”的数学思想； 2、通过对乘法法则的探索，归纳与描述，发展有条理思考的能力和语言表达能力； 情感、态度与价值观 体验学习和把握数学问题的方法，树立学好数学的信心，培养学习数学的兴趣。 教学重点：多项式的乘法法则及其应用。 教学难点：探索多项式的乘法法则，灵活地进行整式的乘法运算。关键：多项式的乘法应先转化为单项式与多项式相乘进行运算，进一步转化为单项式的乘法，紧紧扣住这一线索。 教学方法：小组合作，自主学习 教学过程： 一、课前提问 师：1、多项式与多项式相乘的法则是什么？ 依据是什么？ 2、多项式与多项式相乘，结果的项数与原多项式的项数有何关系？ 3、积的每一项的符号由谁决定？ 计算： )32(3)4() 53(2)3() 35(4)2() 32(7)1(23322222xy xy y x b a a ax a ax b ab a +---- 生：交流答案 师：同学们看这道题怎样做？())()5(b n a m ++（多媒体展示）他和我们以前所学的有何不同？ 生：现在是多项式乘多项式 师：那多项式乘多项式如何去计算呢？这节课我们一起来探究吧！ 二、 学习目标（多媒体） 师：看到这个课题你想学习哪些知识呢？ 生：交流 师：（多媒体呈现） 1、探究并了解多项式与多项式相乘的法则 2、熟练的运用法则进行运算 三、探求新知 问题助学一： 文文帮爸爸把原长为m 米,宽为b 米的菜地加长了n 米，拓宽了a 米，聪明的你能迅速表示出这块菜地现在的总面积吗？ 你还能用更多的方法表示吗? (学生活动)小组内展评作品，推选出最优秀的同学的作品给全班学生展示。 算法设计与分析实验报告 姓名：XXX 班级：XXX 学号：XXX 一、实验名称：大整数的乘法 时间：2012年3月7日，星期三，第四节 地点：12#311 二、实验目的及要求 实现大整数相乘，需要处理很大的整数，它无法在计算机硬件能直接表示的整数范围内进行处理。若用浮点数来表示它，则只能近似的表示它的大小，计算结果中的有效数字也受到限制。如要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。 三、实验环境 Vc++。 四、实验内容 从键盘上输入两个大整数，实现两个大整数相乘，并输出结果。 例如：在键盘上输入两个数a，b。 a=9876543210； b=369852147； 五、算法描述及实验步骤 定义三个数组a[100]，b[100]，c[199]。 用数组a来存放大整数a，a[0]=9,a[1]=8,a[2]=7,a[3]=6,a[4]=5,a[5]=4,a[6]=3, a[7]=2,a[8]=1,a[9]=0； 用数组b来存放大整数b，b[0]=3,b[1]=6,b[2]=9,b[3]=8,b[4]=5,b[5]=2,b[6]=1 b[7]=4,b[8]=7。 用数组c来存放数组a和b每一位的乘积， c[0]=a[0]*b[0]; c[1]=a[1]*b[0]+a[0]*b[1]; c[2]=a[2]*b[0]+a[1]*b[1]+a[0]*b[2]; …… …… c[17]=a[9]*b[8]; 六、调试过程及实验结果 void make(int a[],int aa,int b[],int bb,int c[]){ int i,j; for(i=0;i 求最大元和次大元 1.问题描述 从多个数中一次性查找出元素最大的值和最小值，查找元素规模即元素的个数n,用分治的思想编制程序，实现分治的最大元和最小元求法。进一步改进算法，使之能一次性求出最大和和次大元（即第二大元素）。 2.算法设计思想及描述 分治发的基本思想是将一个规模为n 的问题分解为k 个规模较小的子问题，这些子问题相互独立与原问题相同。递归地解决这些问题，然后将各个子问题的解合并得到原问题的解。基于课堂的分析知道，对于本问题k 的值取为2，这样可以使子问题的规模是相同的，有利于算法实现。 为平衡分治时子问题的规模，这里约定需要查找元素的规模n 是2的幂次方。 用数组存储需要查找的元素，用结构体存储返回的最大元和最小元。每次得到局部的最大元和局部次大元，然后局部最大元和最大元比较得到新的局部最大元，次大元和次大元比较得到新的局部次大元。深入分析，这种方式局部次大元是错误的。如两组元素中，a1>b1,a2>b2,当然a1和a2中较大的是新的局部最大元，但是b1和b2中较大的元素不是这四个元素中第二大的。 这样的方法漏掉了b1可能是次大元的情况，也就是说所有的元素中的次大元可能在与最大元比较的时候被漏掉了。弥补的方法就是每次将每个元素比自身小的元素都用一个淘汰数组保存起来，最后次大元就是最大元的淘汰数组中第二大的那个元素。 3.算法分析 运用分治算法解决此问题，是因为这种方法的优越行，下面通过时间复杂度的比较来说明。 通常算法，设置一个变量，等于需要比较的数组的第一个元素，然后依次与后面的n-1经行比较，需要比较n-1次得到最大元。同理，求得最小元的比较次数仍然是n-1次。设()n T 表示比较的次数则对于这种算法得到()n T 的值为 ()22n T n =- 分治算法求最大元比较 1 ()2()22 T n n T ??=?+?? 解方程结果为() 1.52T n n =-,虽然二者都是线性增长的，可是增长率要小一些。实际编程 实验2 FFT 算法实现 2.1 实验目的 1、 加深对快速傅里叶变换的理解。 2、 掌握FFT 算法及其程序的编写。 3、 掌握算法性能评测的方法。 2.2 实验原理 一个连续信号)(t x a 的频谱可以用它的傅立叶变换表示为 dt e t x j X t j a a Ω-+∞ ∞-?= Ω)()( （2-1） 如果对该信号进行理想采样，可以得到采样序列 )()(nT x n x a = （2-2） 同样可以对该序列进行z 变换，其中T 为采样周期 ∑+∞∞--=n z n x z X )()( （2-3） 当ωj e z =的时候，我们就得到了序列的傅立叶变换 ∑+∞∞-=n j j e n x e X ωω)()( （2-4） 其中ω称为数字频率，它和模拟域频率的关系为 s f T /Ω=Ω=ω （2-5） 式中的s f 是采样频率。上式说明数字频率是模拟频率对采样率s f 的归一化。同模拟域的情况相似，数字频率代表了序列值变化的速率，而序列的傅立叶变换称为序列的频谱。序列的傅立叶变换和对应的采样信号频谱具有下式的对应关系。 ∑+∞∞--=)2(1)(T m j X T e X a j πωω （2-6） 即序列的频谱是采样信号频谱的周期延拓。从式（2-6）可以看出，只要分析采样序列的频谱，就可以得到相应的连续信号的频谱。注意：这里的信号必须是带限信号，采样也必须满 足Nyquist 定理。 在各种信号序列中，有限长序列在数字信号处理中占有很重要的地位。无限长的序列也往往可以用有限长序列来逼近。对于有限长的序列我们可以使用离散傅立叶变换（DFT ），这一变换可以很好地反应序列的频域特性，并且容易利用快速算法在计算机上实现当序列的长度是N 时，我们定义离散傅立叶变换为： ∑-===10)()]([)(N n kn N W n x n x DFT k X （2-7） 其中N j N e W π 2-=，它的反变换定义为： ∑-=-==10)(1)]([)(N k kn N W k X N k X IDFT n x （2-8） 根据式（2-3）和（2-7）令k N W z -=，则有 ∑-====-10)]([)(|)(N n nk N W z n x DFT W n x z X k N （2-9） 可以得到k N j k N e W z z X k X π2|)()(===-,k N W -是z 平面单位圆上幅角为k N πω2=的点，就是将单位圆进行N 等分以后第k 个点。所以，X(k)是z 变换在单位圆上的等距采样，或者说是序列傅立叶变换的等距采样。时域采样在满足Nyquist 定理时，就不会发生频谱混淆；同样地，在频率域进行采样的时候，只要采样间隔足够小，也不会发生时域序列的混淆。 DFT 是对序列傅立叶变换的等距采样，因此可以用于序列的频谱分析。在运用DFT 进行频谱分析的时候可能有三种误差，分析如下： （1）混淆现象 从式（2-6）中可以看出，序列的频谱是采样信号频谱的周期延拓，周期是2π/T ，因此当采样速率不满足Nyquist 定理，即采样频率T f s /1=小于两倍的信号（这里指的是实信号）频率时，经过采样就会发生频谱混淆。这导致采样后的信号序列频谱不能真实地反映原信号的频谱。所以，在利用DFT 分析连续信号频谱的时候，必须注意这一问题。避免混淆现象的唯一方法是保证采样的速率足够高，使频谱交叠的现象不出现。这就告诉我们，在确定信号的采样频率之前，需要对频谱的性质有所了解。在一般的情况下，为了保证高于折叠频率的分量不会出现，在采样之前，先用低通模拟滤波器对信号进行滤波。 （2）泄漏现象 实际中的信号序列往往很长，甚至是无限长序列。为了方便，我们往往用截短的序列来近似它们。这样可以使用较短的DFT 来对信号进行频谱分析。这种截短等价于给原信号序列乘以一个矩形窗函数。而矩形窗函数的频谱不是有限带宽的，从而它和原信号的频谱进行卷积以后会扩展原信号的频谱。值得一提的是，泄漏是不能和混淆完全分离开的，因为泄露导致频谱的扩展，从而造成混淆。为了减小泄漏的影响，可以选择适当的窗函数使频谱的扩散减到最小。 （3）栅栏效应 因为DFT 是对单位圆上z 变换的均匀采样，所以它不可能将频谱视为一个连续函数。FFT的定点DSP实现
多项式乘多项式练习题
大整数乘法问题
多项式的乘法练习试题一
多项式与多项式相乘同步练习(含答案)
大数乘法算法
用matlab实现fft算法
多项式的乘法练习题
多项式乘以多项式教学设计
大整数的乘法实验报告
两个n位大整数相乘算法
实验2FFT算法实现
相关主题
文本预览