DIT-FFT运算流程ppt

学到这里啊，嗯，大家并不能完全的去这个卡尔沃所有的习题啊，但是啊，大家听完拓展之后啊，就可以呃，做完做出来这一张所有的习题啊， 好，那我们知道我们刚才推倒了 g 二 d i t f l t 对吧？那 g 三 g 四 g 五可不可以啊 啊，实际上也是可以的，而且推导的方式也是完全类似的啊，这里面就教大家如何去，他给了你一个这种即三即四的啊， g 三 g 四的时候，你该怎么样去推导啊？首先我就拿 g 四 d i t f f t 给大家举个例子啊，因为我相信他应该不会出 g 六 g 八这种的啊，我感觉他也就是 g 三 g 四啊，因为再多的话其实没有什么考察的意义，而且，呃，而且就是算起来会非常的麻烦啊，所以 g 三 g 四大家一定要掌握，然后这种方法和技巧大家要掌握啊， 那击杀呢？是术后题啊，所以说这里面就拿集四给大家举个例子，如果我们来推击四的 d i t f f t， 首先我们第一步 啊，第一步是给它把 x n 分段分成四段，因为我们是什么？因为我们是 d i t， 我们在时代食欲进行抽取的对不对？所以我们要分 x n 啊，如果它是 d i f 呢？同学们举一反三啊， d i f f d i f 的话，我们就分 s k， 对吧啊，所以 d i t 的话，我们 首先给它分成四段，那四段怎么分呢？当然是要每段分成四分之 n 点，对吧啊，每段分成四分之 n 点，均匀的分成四段，所以第一段就是 s 零 n 等于 s 四 n， 第二段 s n 加一。第二第三段 s n 加二。第四段 s n 加三。 我们发现啊，这这个这四段加在一起刚好可以拼凑成一个完整的 s n， 对吧？ 如果他是分，他是几五，这个几五七六呢？怎么分啊？一样的啊，如果是几五七六的话就是五恩，然后五恩加一，五恩加二，五恩加三，五恩加四，对吧？ g 六呢？就是六万六万加一，六万加二，六万加四，六万加五。啊，啊，是六段啊，好，然后我们分成四段之后， 我们要分别计算它每一段的，是吧？四分之间点 d f t， 对不对？我们计算出它每一段的四分之间点 d f t 之后，假如说它是 x， 呃，零 k x 一 k x 二 k x 三 k， 对吧？那仿照我们的 g 二 d i t f f t， 我们就知道下一步我们该怎么做了，对不对？因为我们的核心的目标是求什么？求 s k， 所以我们在我们分段，先分段，然后第二步给他进行 dft 之后，我们得到了他，之后我们第三步是什么？就是进行线性组合，对吧？肯定有一种线性组合是可以让这四个东西 现在组合之后得到 s k 了，肯定会存在这样一种，呃，这样一种组合的方式，对吧？啊，这就是我们的一个目标啊，然后 我们来看一下啊，第二步分别是计算它的一个，呃， s 零 k s 一还 s r k 嘛，对吧？那这里要注意啊，我们计算 s 零 k s 一 k 的这这样一个过程的时候啊， 我们这里带的是 x 零 n， 对吧？然后 s 应该是等于 x 四 n， 那这里面需要大家非常容易错的一个点是在这啊，这里面我们我们是把 x 零 n 给它换成了 x 四 n， 而不是把后面这个东西， 会有同学把这个东西也变成四 n 了啊，这就是错了，因为我们在这是在做他的四分之 n 点 d f t， 那这一步呢，只不过进行了一个这种替换啊，只是把 x 零 n 换成 x 四 n， 而不是我们之前的那个过程，是把什么 n 变成四 n 啊，不是这样一个过程啊，所以这这一步大家一定要注意， 我们只是把它换成它，看这个 n 是没有变的，大家好好去理解一下这个地方，然后下面呢也是一样的道理啊，大家看这个四 n 加一直变到这了，这上面还是 kn 啊。然后第二步算完之后，我们来看一下它的线性组合是什么样的啊？ 我这里直接给大家结果了啊，因为它的推导过程是跟 g r 的算法是完全一致的，这给大家留一个作业啊，大家去推导一下 x 零 k s 一 k s 二 k s 三 k 它和 s k 之间的关系，这个推导的计算量很大 啊，这个推导计算量很大，但是如果你把它能够完整的推导出来呢？这一张你至少至少说你 d i t f f t 是没有什么这个能难住你的了。那我们发现我们推导之后，我们发现 啊，这四段这个 k 是等于零到我们的呃，四分之 n 减一的啊，啊，通过这四段的话，我们发现通过他的线组合，我们得到整个的 s k 啊， 那他是怎么推倒的？再给大家提示一下啊， 就是跟我们的积压是完全相似吗？我们原来是零端减一 x n， 对吧？所以我们给它拆成四端，给它零到这个四分之 n 减一，然后 x 四 n 啊，然后加上 x， 什么三加一啊，一，一直加到后面啊，然后再给它化减，给它表示成 s 零 k s 一 k s 二 k 的这样一个形式。因为我们前面已经有 s 零 k s 一 pk s r k 了吗？我们给它凑配，凑出这种形式，然后把这个东西给它替换进去，我们就得到我们最后的一个这样一个结果啊，跟 g r 算法是完全相似的， g r 要掌握， g 四也要掌握啊，然后 啊，然后还有就是 g 三的 g 三的这个频抽啊，频率抽取 g 三 d n f f f t 啊， f f t。 刚才我给大家点拨了一下啊，它是频域抽取的，所以我们在频域的话要给它拆成什么样啊？ x 三 k x 三 k 加一， x 三 k 加二啊，如果它是频率的抽取的 哈，还有这样的，对吧？要频率给他分成三段，然后我们的目的是什么？我们的目的是，哎，我们能不能把这个食欲 xn 给他进行一些线性组合，比如说 什么 s n 加三分之 n 啊， x n 加三分之二 n 啊，给它进行一些线性组合之后，给它拼凑出一个三分之 n 点的一个序列那呃，三个啊，三个三分之 n 点序列， 然后每一段的话刚好给他进行三分之点 d f t 能得到 s 三 k， 然后 s 三 k 加一， s 三 k 加二，这就是 g 三 d i f f f t 的一个原理啊。有一道术后例题，就是讲的这个，我相信大家听了我，我讲的这个过程已经可以自己推导出来了啊， 因为这个过程非常重要啊，就是你，你可能就是会有这种感觉啊，就是你看了过程 之后，包括你做了题之后，如果你没有自己从头到尾默认就是不看答案去推导出来的话，你第二遍你还是不会啊，这是很正常的一件事啊，所以大家一定要自己去把这个推导出来。 好，这就是呃，关于呃计三计四的一些，呃， d i d i t f f t d i f f f t。 我们当我们碰到这些情况的时候该怎么处理啊？大家听懂的扣一。

大家好，最终我们来看一下这个 fft 就是快速复利液变化，快速复利液变化的根本目的其实就是为了解决 dft， 也就是离散妇利业变化的计算量 过大的问题。这个是一些说明啊，自己看一下这个算法效率，然后我们看一下这个一个有线长 n 点 dft， 他就是这样的公式。那我们看，你看这个假设是假， 假设是 n 个点， n 个点，那么我们从这里看到这个 k， 当 k 固定的时候啊，当 k 固定的时候，那 n 从零变到 n 减一，那就是总共变血变 变化了大大 n 次，对吧？那那 n 从零变到大 n 的时候，他总共就要做，因为 n 等于零，没等于一个数字，要做一次惩罚，所以他变化了 n 次，那就要做 n 个惩罚。 n 个惩罚。问题是这个 k 它是固定的，就是说对每一个固定的 k 来说，就有一个就有 n 次惩罚，那那那 k 如果也从零算到 n 减一的话，如果 k 本身哈计算 从零计算到 n 减一的话，也就是也就是有 n 个 k， 那么一个 k 就要算 n 次， n 个 k， 那就是 n 乘以 n 次，那就是 n n 平方次乘法，这都是都可以把他们看到这，这个是负数吗？如果这个信号也是负信号的话，那就是 n 平方次负数乘法 加法呢？那因为这个当开固定的时候，我们这里 n 变到变，从零变到 n 减一，也就是有大写的 n 个 n 的时候，那他加法就是 n 减一次吗？对吧？ n 减一次，因为两个才有加呀， 比如三个，三个 n， 三个 n， 他只有两次加法，所以他加法次数是当一个固定的 k， 他有 n 减一次加法，那，那当哎有 n 个 k 的时候，他就是 n 乘 n 减一次加法，负数加，所以这个计算量是很大的哈， n 平方次乘法， n 乘 n 减一次加法， 现在他是怎么来简化这个运算呢？这里说明了哈大，那这个因为这个他都是有周期性的，那我们作为哈，他 wn， 他是等于这个东西的哈，这个东西，这个这个有个负极啊，有个负号，他明显就是有这个周期，对吧？那根据这个周期性呢？ 我们就可以得出他一些特点，这个去这个他不是就，就我们自己去推一下这个他就就就有这样的特点。你比如这个我们把 m 加上二分之 n， 你看 我们把 m 加上二分之 n 带进来，带进来他就会有这个，这就有这个这个等式哈， m， 这还是这些加二分之 n， 二跟二消掉了， n 个 n 消掉了，那不就剩下一个一的负结派吗？一的负结派他就是负一啊，所以他就会 有有这个等式。这个呢，这个前面也说过很多次了，他其实就是一个一个圆周顺顺着一个那个单位员的那个负数单位员进行，那个啊， n 等分 就是这个圆周对称线，就就就我们从这里就可以看得出来哈，那刚才我们说了这个啊， dft 那个计算量太大了，一个 n 平方，对吧？ nn 乘以 n 减一，那么为了减少他的计算量啊，他现在就就根据这个这些性质 以及他的这个这个周期性，来来来，来减少他的运算运算量，想办法减少他的运算量。 怎么减少呢？首先把我们所要计算的所有的点啊，采集的那些点，把它分成激素偶数部分和激素部分。我们注意哈，这里都是到二分之 n 减一， 从零出发到二分之 n 减一为止，那那那 n 的要满足这个关系是二的指数次方，二的指数指数次次方，比如这个啊，八呀，对吧？比如八，那这个就是零到四减一，零到三，对吧？这个嘞也是零到三， 所以呢，那么 x n 他就可以分分为偶数跟激素，把它写出，把它这样带进去就得出这这这部分来，那同时呢，又因为 他们这个这个满足这个关系可以推出这个来啊，这个注意这个是，嗯，这个是二分之，嗯，然后整个人那个是 k， 他等于这个这个表达时代表的意思是什么呢？我们看到哈这个这一部分，这一部分，这个 x 一啊代表的是 手速点，这个 xrr 呢代表的是激素点，所以呢，这个 k 我们他他是一个固定值吗？对吧？当 k 是一个固定值的时候，那么他由他的 偶数点的复列变化，再加上激素点的复列变化得出来，就得出这一个点的复列变化。每一个点哈， 就是不管是偶受点还是技术点，到 k 固定的时候，每一个点都要对这个 k 为固定值的。那那那那那个那个频谱啊做出贡献的。我们看这个 四个点的时候哈，四个点，二个三是四个点，那么他的这个算，这个四个点的 dft 就是这样算的。我们看到对，这个是代表频谱啊，当 k 等于零的时候，四个点都要为这个频谱做贡献。一也是一样的，都有四个点，每一个频谱都有四个点跟他做出贡献来 啊，这是四个点，我们再看两个点的两个点，他就是这样啊。啊，阿姨，这两个点怎么来的呢？你看我们把这个这个 n 换成啊， 你看这个，因为 k 等于零嘛， k 等于零，那就是 w 二零，这个也是 w 二零， k 等于，那 k 等于一的时候呢？这个 x 零 w 二零， 为什么呢？因为第一个点是 x 零，这个零乘一还是零，所以是 x 零， w 二零加上 x 一，那这个时候 n 等于一啦，天也等于， 那就变成了 s 一 w 二一，所以两个点的时候是这样的。然后那么我们从两个点计算两个点的时候啊，他，他要这是两次加法，对吧？两次加法，几次惩罚呢？四次乘法， n 平方吗？ n 等于二吗？二的平方是四， 那个加法呢？是 n 乘 n 减一，二乘以二减一，对吧？所以这个两个点呢，就是四次惩罚，两次加法。那如果把四个点，把四个点分成两个， 两个两个点来算，就是两部分，一部分是两个点，分成两，两部分，两个点来算，那么他总共需要的运算，那就是四次加法，还有八次惩罚。那相比这个我们刚才说的这个是十二次加法， 十六次惩罚，那那那这个运算量就减少了很多啊，那那那在这个这个基础上啊，就是这个我们就知道了，这个这个就是把它这个四个点分成两个点，他那个运算量可以降低很多。但是呢，我们要理解的是是什么东西呢？ 从这里我们看到，当开为任任何一个数的时候哈，这个这个 xn 里面的每一个点都为这个 xk 做出了贡献，但是呢，我们如果把它四个点分成两个点来算的话呢？我们我们能不能保证这一点呢？ 就是每一个数据点都为每一个 xk 的 k 值做那个那个做出了自己的贡献呢？这里我们主要从这个推倒出来的这个公式来计算。你看当 k 固定的时候，那么这里这里 x 一这一部分是代表所 所有的偶数点，代表所有的偶数点，这个已经已经被计算进来了，这个呢 x 二呢是代表所有的基数点他都被计算进来了，所以这个是没有问题的。 也就说 x 一 k 是代表了所有的这个这个偶数点已经被算进来了。 x 二 k 了，代表所有的激素点 已经被算算进来了，说两者加起来就是得出了 xk。 所以有了这个思想之后啊，我们就可以理解这个东西啊。你看 x 零对于 k 等于零来说， x 零如果是四个点哈，如果是四个点，那么这个 x 零呢？它是就代表的是所有的偶数点，这个 x 一呢就代表的是所有的激素点， 同样的这里也是一样，我们看这个这个这个这个这个叠形，你看这里是一个叠形，对吧？然后到这一步，到这一步我们看的是 x 零 x 二加起来的得到的这个这个偶数点得到的那一部分，这里呢是这个基数点得到的那一部分。然后对于 x 零来说，他又是两个偶数点 跟那个两个。到这里哈，到这里已经是两个激素点之和了，所以到到这里来是两个偶数点加上两个激素点之和加起来，所以没有问题， 这个叠形他就是这样画，这个表示加法，这个呢表示减法，就这这个表示加法，这个表示减法，那这个四个点，我们你比如他，因为他是四十二的二次方吗？那八呢？八十二的三次方， 那你就要一直分解，先分解为四，然后再分解到二，一直一直要分解到二为止，这个就叫基于二的 fft 算法，基于两点的 fft 算法， 所以我们看到这是八个点，那八个点，那先把它分成偶数部分和激素部分，那么对于 x 一零来说，他代表的是所有偶数点对于 k 等于零，这个这个这个频谱啊做出了做出的贡献运算的结果。然后呢这个 x 二零呢， 就代表所有的基数点对于这个 k 等于零这个频谱点做出的这个贡献，然后再把两者加起来，就得到了这个所我们所要算的这个八个点的 x 零啊，其他的也是一样，那这个到这里呢？因为这是八个点，这个还不行，然后那要继续把它按照激素跟偶数分解， 要分解成这个样子，这不是零二四六吗？所以这个是第一个点，第三个点，这个呢是第二个，第二个点，第四个点就就继续这样分下去，直直到分到两 个点为止。二的比如二的二次方分解一次，对吧？二的三次方就要分解两次，就是二的 k 次方啊，他就分解 k 减一次吧，就这样最后就算出来了，这个呢就把那个那个运算的强度降低了。 从这个分解过程我们还看到这个基数点相对于偶数点来说，由于他是这样的二加一啊，他在这个表达史里面，他就多了一个这样的东西啊， 多了一个这样的，这里来说的是这个 n 分解为二 n 点，他他那个乘法次数的降低降到了这么多， 然后加法次数也降到了这么多，所以在他这个这个分解这个降低了这个复杂度哈，那二分之 n 点呢？他又可以分成四分之 n 点，就继续这样分下去哈，那这这个过程呢？这个自己看一下啊，这个就是这样，这样算算下去，同样的方， 这样这样一直弄下去就行，这个就是这个八个点经过两次分解就分解为两个四分之恩典哈，将二分之恩典就分解为四分之恩典，就这样一直分下去哈， 所以这整个 fft 运算的原理啊，它其实很简单，它的唯一的目的就是降低这个这个 dft 的运算复杂度，然后它采用的方法是什么呢？ 就是一半一半那样分积分成激素部分，偶数部分，然后一直分解到哪里为止呢？分解到两点两个点的 fft 为止，这样就就降低了他的这个整个整个计算的复杂。

大家好，这个上个视频我们讲了这个十月抽起法，这个它基本的基本的原则就是把这个序列啊，那个分解成这个构数和激素。 这次呢我们再看一下这个平域抽其法，跟食欲抽其法相比，它不是分成偶数和基数，而是而是分成 前半部分和后半部分，这个前半部分是零到二分之一减一，后半部分是这个二分之一，到到到最后一个，那然后就按照这个推 推成就就就成了这个样子。然后这个这里这个二分之 kn 啊，他他有这个关系，开始偶数的时候是一开始激素的时候是负一，那这个意思我们 我们要搞清楚了，这个 k， 我们看到是是这个频率点代表这个频率点的 k， 哈，所以这个这个这个频率点，当频率点这个是偶数的时候，他是一个表达时，是激素的时候呢，又是一个表达时，也就说 x 零 x 零二四六八，这个他的表达是是一个，这个一三五七九呢，他的表达是又是另外一个，那就是说这个这个频率抽起的时候啊，他把这个频率点 由于这个表达时的问题，把这些频率点分成了偶数组和基数组，这个跟食欲抽起的是把那个那，那 这个数据点哈，时间系，时间系列分成偶数组跟基数组，这个这个不一样，这个是把频率点分成偶数、偶数组和基数。所以我们看到这个偶数的时候，他是这个 表达时，这个激素的时候，他是这个表达时，在这这在这里哈频率点，这是频率点分成偶数和激素。 好，现在我们看到这个假设 x e n 是，是这个 x r n 是这个，那这个 x 一 x 二代表的意义是什么呢？我们看到这他有这个表达时， 这个 x 一 nxrn 在这里出现了，那这个 x 一 n 代表的意义就是这个系列的前半部分和后半部分对对偶数频率点啊做出的贡献。 xrn 呢？同样的他是代表 这个序列的前半部分和后半部分对这个对那个激素的频率点做出的贡献。也就是说他其实 x 一 x 二代表的都是 全部的实践，实践系列那些点呐，那些点对对这个频率点做做出的贡献。只不过呢，这个 x 一代表的是对偶数频率点做出的贡献。 x 二呢，代表的是对激素的频率点做出的贡献。 也就说他这样做了以后，其实也是把这个 x 零到 x n n， 这个 x 零这个序列啊，也分成了两部分，像那个时间一一样，他是分成激素组，分成偶数组， 那这个呢，他是分成前半部分，后半部分也是，也是同样的是一分为二，所以也降低了这个这个 dft 的运算运算复杂度。那同样的呢，也把这个叠形运算图画出来了，那这个叠形运算图跟那个啊，这个前面的那个 按时间抽取的那个叠形图啊，我们来注意一下它的区别，这里哈，这个叠形图，你看它是代表这一个跟这个相乘，然后相加啊，这一个呢，这一个跟这个相乘，然后再乘以这一个，它是相结。 像上面这个叠形图是加，下面这个叠形图是减。好，那么我们来比较一下他跟那个时间时间与的这个这个这个频率点的区别，时间抽起的这个叠形图的区别， 我们只看到这个按时间抽取的这个这个叠形图啊，他这个 a 其实是代表偶数部分， b 代表基数部分，这个 c 注意相乘的这个音质，他在这个地方，但是呢，我们这个平 绿抽起的这个这个相承的音质在哪里呢？我们看到他他相承的这个音质，他在这里，他不是在这里，这个是不是在这里哈，而是在这里，所以这个还有这个按频率抽取，他这个上面的这个这部分呢，他代表的是 前半部分，下面的这一部分呢，是代表的是后半部分，所以时间序列那个时间抽取的它上面的这个是代表啊基偶数点，下半部分呢是代表基数点，这个就是他们这个一个按时间抽取，一个按频率抽取的不同的地方， 就是不管按时间抽起还是按频率抽起，这个是食欲抽起哈，他都要保证这个这个系列中的每一个点呐，都对每一个频率点，这是每一个食欲的点 都对每一个频率的点，那个那个要要要要做出贡献。所以这这个呢，在十月这个点呢，他他这个这个这个 x 一零，他代表的是 所有的偶数点对 k 等于零这个频率点来做出的贡献。这个前面已经说过了，这个 x 一一啊，他代表的是也是所有的偶数点对 k 等于一所做出的这个这个频率点， k 等于一这个这个这个 频率点做出的贡献。这个零一零一二三跟这个的零一二三他代表的是不同的意思哈，一个这个是代表频率的点，这个是代表食欲的点，同样的这里也是一样，这个是二，这个二代表的是所有的基数点，这个一代表的是所有偶数点啊。在 按频率抽取里面的这个图标设置的意思就是你看这个，这个是代表前半部分，食欲的前半部分数据点以及食欲中的后半部分的数据点，这个对对于偶数、偶数位的频率点做出的贡献。这个呢？也同样的，这个是 时时间遇的这个前半部分数据点，以及时间遇的这个后半部分数据点对激素位的频率点做出的贡献，所以他们是这样划分的，那当然还可以继续分下去哈，能看到还可以继续这样分下去，那大体的思想就是这样， 这个简单区分食按食欲抽起还是按平欲抽起的话，如果按食欲抽起，他就是把食欲的这些数据点 分成激素部分和偶数部分，如果按频率抽取了，他就是把频率的这些点分成了偶数部分和激素部分。简单，气氛就是这样啊。

八点的副列变换六十四次乘法，我们用四个嗯，四点的副列变换用两个四点的副列变换代替啊。八点的用两个四点的啊，两个四点的。得到几个 h 之后几个 h 再组合成我们 f 零至 f 七的值，八个值。 那么呃代替完之后，我们的计算次数，呃，每个四碘伏列变换，它是十六次，所以说计算就是十六乘以二。然后呃用 g 和 h 组成 f 的话是八次乘法，所以说是十六乘二加八次。 那么我们就可以继续啊，把负累变换用他的二分之 n 点啊来替负累变换替代啊。这里有呃，两个四点， 我们就由四个两点的费变换替代掉啊，替代掉之后啊，计算量这个每个两点是四，所以是十六。然后由于这个组合有两次，所以说是两次八啊。 然后再用八个一点负累变换题的。其实一点负累变换计本身就是他本身了啊。那我们的计算量还是要统计的。一点负累变化是一乘一，所以说八个一点的就是八次。那么这里面你可以看到这里乘法是八次啊，这里是八次八次，所以说是八加八加八加。然后计算八个一点负累变换的值。哎，完了。 那么直接拉到最后吧。啊，直接到最后我们把它给讲一下，计算八个一点负累变换的值，然后直接 f 零。其实它的负累一点负累变换就是 f 零本身啊，就是 f 零本身。所以说这个值应该填 f 零的。 f 零 f 四啊， f 六啊，这直接填的。 那么这也直接代替完之后，这就是八次八次八次啊。你看这个是他们俩组合是机灵啊，机灵加上 h 零乘以啊。哎呦，还是这样，不太清楚。在这里 g 零加上 h 零乘以 amiga 八零啊，乘以一等于 f 零啊。 g 零加上 h 零乘以 amiga 八零乘以负一等于 f 四啊。那么 amiga 八零是一的负 i 八分之二拍乘以零啊的意思啊。我们一个八一是一的负二。呃，负 i 二分之二拍，那乘以八分之一啊。是这个意思。那这是他们组 和计算，所以说这一组合计算每次都是机零加上 h 零乘以某值啊。所以说他只是一次乘法啊这是。呃，所以 f 零一次乘法， f 一一次乘法，所以 f 零至七一共是八次乘法。那么这个同理的。 那么这个机零是由机机零和 h g 零两个组合得到的。就是机机零加上 h g 零乘以阿威嘎四零乘一啊。那么这个乘一其实就可以啊，可以先不算它是一次乘法对吧？ 啊，那其他的也是啊。那么这是四点的，然后这是两点的话，也就是那么积积零就行，积积积零啊，加上我们一个二零乘以 hgg 啊这是。这也是的。后面这个一点呢，其实就可以直接写了啊，这里应该把这个删掉 啊，这个删掉，这个 f 零直接写到这里的啊， f 零直接写到这里，因为它直接就是这个。

f f t 快速护理液变换运算操作第一步点击 max 通道标签，进入 max 菜单。第二步点击 f f t， 执行 f f t 运算。 第三步选择数据源，点击箭头选择 ch 一至 ch 四。 第四步选择垂直单位，点击箭头选择分贝或电压有效值。 第五步选择 fft 函数，点击箭头选择 不同的窗函数。 第六步设置对应于屏幕水平中心的频域波形的频率，点击箭头进行微调，或者点击数据，弹出数字键盘直接输入数据。 第七步设置频率跨度， 点击箭头选择六十二点五零 k 赫兹或三十一点二五 k 赫兹。 八设置参考电瓶，点击箭头进行微调，或者点击数据，弹出数字键盘直接输入数据。

dft 的话啊，那它的运算复杂度呢？是肯定是 n 平方次的，因为所有的参数呢，都会被我们的旋转因子矩阵呢去扫描一遍 啊，也就是说这是我们的手这个频率啊，那我们这个会用恩呢去进行一个局部的积分，所以这样的一个剧情运算呢，他的复杂度呢？是恩品方式，这个不用说了 啊，那我们改进到 fft 以后呢，我们实际上呢是把这样的一个原来是 n 个的数据呢，把它拆分成二分之 n 啊，两个二分之 n， 那么拆分以后呢，实际上再去做这个啊，福利变换的时候呢，所以我们实际上是经历了这样的一个事情， 那就说我们分成这个藕藕刺的和这个鸡刺的这个啊副列变化，那，那我们从前序的，比如说二分之 n 次 d f t 啊，二分之 n 次的 d f t 拆成两个二分之 n， 那么那么它在后集的时候呢，最后一集的运算呢？实际上它是说啊，我们在这边假如说 这是，这是机次的啊运算，这是偶次的运算，这是 ft 啊，那我们我们的输出呢，实际上来说 啊，我们需需要用到藕刺和鸡翅呢来做这个啊运算，所以实际上我们经历了这样的一个事情，那么这是藕刺的时候 的一个输出，那么几次的输出呢，实际上是经历了一个这样的一个过程， 那所以他也用到了这个来自藕刺的这样的一个呃呃，二分之 n 的 d f t， 那么在这边呢，大家可以看到呢，实际上算法呢？最后一集呢，来自这这一个地方的一个乘法，因为因为在鸡翅的 dft 呢，我们需要乘一个什么啊？东西呢？需要乘以一个 w n k 啊，需要成一个 w n k， 所以我们利用了 w n k 的对称性和这个周期性呢，来进行这个投机取巧啊，投机取巧啊，也就说在最后一集呢，这 只在这呢做了 n 次的 n 次的这个乘法，其他地方都是做的加法，大家注意啊，其他注意做其他地方都是做的加法，那么这个地方呢？是啊，减法，因为，因为旋转因字句真的对称性，所以，所以大家可以看到 那是这样的一个一个做法，所以经过以第一次拆分以后呢，运算复杂度变成，你看两个二分之 n， 他的运算复杂度呢？是 d f t 的运算复杂度是二分之 n 平方 啊，二分之 n 平方，那么是两个嘛，所以是两个二分之 n 平方啊，那么后集呢？还有最后一集呢？有，因为拆分以后呢，我们还有 n 次乘法，所以我们需要加上一个 n 加，所以这是拆分第一次以后的啊， 运算复杂度啊，那么那么以此类推呢？拆分第二集以后呢，运算复杂度是多少呢？我们，我们实际上把二分之 n 再拆成四分之 n 码，所以我们是二倍的，我们拆成四分之 n 码，所以是四分之 n 的啊，平方 啊，做完之后呢？ dft 做完之后呢，还有一个二分之 n 的运算复杂度啊，那，所以，所以我们整个呢，是一个二倍的一个关系，加上这样的一个关系，然后再加上一个 n， 那大家注意看这个，你实际上把二分之 n 呢，当成未开发的，未简化的，这是 d f t， 你把它变成四分之 n 以后呢？那么它的运算复杂度呢？就变成这个值了， 所以你要变成八分之 n 呢，实际上你相当于把四分之 n 呢，再变成八分之 n， 所以你再把它展开就可以了，所以你看这个就等于啊，等于复杂度是二分之 n 平方加 n 啊，这个呢，就等于啊，大家可以看到是四分之 n 平方加二，那所以一直拆分下去的话，一直拆分下去的话，大家可以看到这一块的运算复杂度是在不断降低的，一直降低到这个底数，这个分母等于 n， 那么等于 n 以后呢？如果拆分多少次呢？拆分二的 p 次方等于等于你的那个大 n 的时候就可以，所以这个拆分次数呢， p 呢，就等于 log 二维 d， n 的 对数，所以他拆分到 log 二维 dn 的对数的时候呢，那么这个这个分母呢，就等于 n 了，所以拆分到批次以后呢，运算复杂度就等于 n， 加上 log 二维 dn 的对数， 那因为如果说 n 很大的时候，那么可以省略 n， 所以呢，我们说 f f t 最终的运算复杂都是那个二为底 n 的对数，乘以一个 n， 这样就啊，这里还有一个 n， 这样就分析出说啊， f t 的运算复杂度呢？最后是啊，那个二为底 n 的对数呢啊，乘以一个 n， 这样的一个复杂度。

t 是一种 d ft 的高效算法，成为快速复利业变换。复利业变换是食欲一频欲变换分析中最基本的方法之一。 在数字处理领域应用的离散负离液变换是许多数字信号处理方法的基础。由于计算机技术的快速发展，在七十年代中期，美国和日本的一些电子设备企业开始设计和生产数字是负离液分析仪。 但是由于离散副理业变换的计算量较大，直到 dft 的快速算法发现之后，有限离散负离业变换才真正获得了广泛的应用。 f t 基本上可分为两类，时间抽取法和频率抽取法。而一般的时间抽取法和频率抽取法只能处理长度 n 等于二 m 的情况，另外还有组合数 g。 四 f f t 来处理一般长度。

那我们继续啊，那后啊，我们就要引入今天的正式的一个内容了，就是 f f t f f t， 然后它是怎么通过一些优化的手段来降低我们 d f t 的运源次数的，对吧？我们刚才已经计算了 d f t 的运源次数，我们发现啊，大家看 这个用的次数是我们我们只先只看他这个浮乘啊，因为其实呃算十乘的话，也不过，也不过就是一些固定的一些这个乘一些比例就好了嘛。我们看一下他浮乘，浮乘 n 点 d f t 是有 n 方次，对吧？附加呢？它是有 n 乘减一次，我们一般来优化优化的是浮乘的这个次数啊，因为优化浮乘的次数下去了，它这个附加次数也下去了，我们发现 d f t， 它 n 点 d f t， 它的这个浮乘 的次数是 n 方，对吧？他以 n 方这样一个呃速度去去增加的，我们来看一下啊，我们来看一下，那如果哈，如果我们能够就把这个 n 点 d f t 啊，给它拆成 两个二分之间点的 d f t 啊，如果我们如果我们把可以把这个一个 s n 哈给它拆成两个二分点二分之 n 点的 d f t 的话，我发现实际上我们 就是已经把它的运算次数给它优化了，对不对？因为如果你做一次 n 点的 d f t， 它的运算次数是 n 方，那你做两次二分之 n 点的 d f t 的话， 它是二分之 n 方乘二，对吧？所以实际上啊，实际上它的 后面的这个东西已经是啊小于我们前面的这样一个运算次数了啊，那这个实际上就是我们 f f t 它的一个里边的一个基本的一个原理啊，就是我们给它拆，拆分给它不断的给它一半一半对半拆啊。 那介绍完这个 f f t 的原理之后啊，我们首先我们先不着急去推导啊，不得不着急推导，为什么？因为这张的推导是非常多的啊，啊？我们首先要知道我们在干什么啊，首先我们来看一下，就是第一个， 这个第一个啊，我们要学的是 g 二 d i t f f t 算法，这个 d i t 就是代表按时间抽取的 f f t 算法，我们刚才 已经已经提到了，就是如果我们把这个按键 d f t 给它对半拆的话，那已经可以优化了，对吧？那我们再继续再对半拆，再对半啊，给它拆到就是一个极限的时候啊，那它说明它的这个运算次数会一点一点缩小，对吧？啊？ 那想要这么拆实际上是有条件的啊，就是我们做 f f t， 我们必须要求这个信号的长度是 n 等于二的 m c 蜜的啊，就它必须是符合这样一个条件，其中 m 为整数， 如果这个我们带做的这个信号的长度不满足这个条件的话，那我们要通过补零来满足这个要求，那这个会体现在哪里呢？就有很多同学，嗯，会盲目的去学这一章的知识啊，然后他学完之后，他做题 发现，哎，我推到这么多东西，我发现非常简单的一个东西，我不不明白，就是说假如说有一个序列哈，我们通过 很多的一个推导，我们发现这个序列的长度是假设是九百八十七点 啊，然后他问你，那我们做多少点的 f f t 啊？啊，那这个同学会发现他他不知道，然后这就是你推倒，推倒的时候你已经忘了你的，你最最开始你要干什么了 啊？我们就是本着这种对半分对半分、对半分的这样一个概念啊，就是引出了 f f t 嘛。所以 f f t 它是有一个要求的啊，它只能做一零二四点的，这样一个 f f t 就必须必须符合二的 me 那一点二四点和九这个九百八十七点啊，还差了很多点，怎么办？补零，我们把它补零，把它后尾就末尾的这些值给它补零，补到一点二四点再去做 f f t。 如果一个序列不符合二的 m c 密的话，它是无法去做 f f t 的，它只能做 d f t 啊。

哈喽哈喽，小伙伴们大家好，我是你们的工程师，东东如何输出一个方波信号呢？东东就带大家一块去演示一下，那今天呢主要用到的设备呢？信号源还有我们的一个试播器，那下面呢东东就带大家一块去实地的去操作一下。 首先呢模型这一块我们可以选择方波，这是我们的一个频率，点击频率 我们设个十 k， 合资，我们直接在这里面选就可以了，我们设置为五幅，下面把我们一个占空笔设置一下，设个百分之五十好了，校园这一块的一个设置已经设置好了，设置好之后呢，我们一定要去点击我们那个通道的一个输出，把我们的通道输出打开， 那此时呢我们的一个防波信号就是从我们的信号员已经开始输出了，在我们的一个试播机上呢，点击 自动出发，那此时发现我们的一个放播信号已经显现出来，那么下面去对我们那个波形进行一个调整，打开我们的 mace 按钮，然后选择我们那个 fmt， 把我们这个平铺进行一个调整好，此刻我们那个平铺也可以更加直观的看到了，下面呢把我们那个平铺的位置再去调一下， 那么此时根据我们那个 b 的一个标记点，我们看一下我们第一个峰值十 k 赫兹，我们看 第二个，第二话就是三十 k 盒子，那相应的第三个呢就是我们那个五四 k 盒子。好了，我们今天呢就是简单的去教会大家如何去使用信号员输出一个方波信号，如何在我们拨机上查看具体的一个参数，那如果说你感觉我们那个视频呢？对你有帮助，欢迎积极留言。

下一个，那就是我们已经呃知道了这个计算量该怎么算了，对不对？但我们只只知道这个 d f t 的计算量该怎么算，那我们的 f f t 改进之后的 f f t 该它的计算量该怎么去算呢？ 呃，因为 d i t f f t 和 d i f f t 啊，它是一个转制的关系，所以 我们知道啊，他应该是计算量是完全相同的，那一个叠形的基本单元，他是有两次附加和一次复成的，大家可以看这个是这个这个图像啊，这就是最基本的一个叠叠型单元，他这是一次复加，这是一次复加，对吧？然后这是一次复成， 这是 d i t 的，然后 d i f 呢？它这是一次附加啊，这是 一次附加，这是一次复成，所以它是每一个最基本的叠形，它是有两次附加和一次复成的 啊，两次附加和一次复成的啊。然后我们发现啊，我们之前已经讲过了，他是如果他的 n， 他是有 n 点的话，那他的这个级数就是二的 m， 私密 m 就是他的 m 级，分解他会有 m 栏这样的一个叠型的一个概念啊。然后对于 m 级的这个叠型的运算，他每一级 都有二分之 n 个叠形单元，对不对？那我们已经看了，就如果他是个八点的，那他有四点，他有四四个叠形单元，对吧？ 当然这个是都是建立在 g 二的一个基础上的啊，如果他是 g 三 g 四的，这个大家自己再去看了啊，因为 g 三 g 四，他每次叠行的浮乘和浮加的次数也会改变 啊，所以他的整体的一个都会都会去变化啊。然后大家画出他叠形图之后，再根据他每次叠形的一个符乘和附加的次数，再去计算他的改进后的运算量就可以了。这里讲的是基于其二的一个这样一个计算啊。 然后他每一集都有二分之 n 个电信基本单元，对吧？所以他总共就有 m 乘二分之 n 个电信基本单元。我们有知道每次电信基本单元他是有两次负正和一次附加的 啊。然后 m 是等于多少的？ m 等于 log 二点 n 的，对吧？因为这个式子吗， m 等于二 log 二点，所以改进后的运算量，它的浮乘次数就等于 log 二点乘，二分之 n， 附加次数呢？就等于 n 乘乘 log 二点 n， 对吧？没有问题吧。然后如果你再想乘，再想求那个十加和十乘 的话，就利用我们课程最开始讲的那个关于计算量呃，十乘十加计算的那个技巧去算就可以了啊，大家坚持一下，马上就结束了啊。然后 接下来哈，我给大家这个，把这个表格放在这里了，呃，给大家一个直观的一个感受，就是我们的 f f t 啊，纠正能提高提升我们的计算量提升多少倍啊？首先这个 n 就是， 呃，它是二的这个 m c 密码，对吧？它是按照这个点数，第一列是它的点数，第二列这个 n 方，它是 d f t， 它的符乘的次数。我们知道，在最开始我们知道了哈，就 d f t n 点 d f t， 它的符乘的次数是 n 方， 然后这个呢？二分之 n 乘 log 二零，我们这刚上刚算完啊，它是改进后的 f f t 的符乘的次数，它是二分之 n 改进后 f f t 的这样一个浮乘的次数啊，我们发现哈他已经我们这样这样看出已经他也是已经有一定的这样一个减小了。然后我们用 d f t 的这样运算次数除以 f f t 的运算次数啊，就是代表我们这个 呃，运，呃这个计算效率哈，这个它的一个优化的一个指标，呃，发现 当这个点数越多的时候，我们优化的这个效果越明显，对不对？当他当我们做这个二零四八点的时候，我们发现哈我们这个 f m t 已经优化了三百多位了，他的计算次数啊， 这个 d f t 它原来岁数是四百一十九万次，但是呢 f f t 它只有一万多次，对吧？这就是我们一个核心的一个这个 f f t 它是有多么强大啊？

冰冰，你不是跟着 dit 老师去现场的吗？有没有遇到爱豆啊？年轻，本来还以为可以去偶遇爱豆的，结果这一趟下来差点没把我累死。 dit， 不就是烤烤素材吗？有这么累吗？哪里是烤素材，简直就是给人素菜找了个保姆！ 素材出问题是所有后期剪辑师的终极噩梦，因为综艺节目几乎无法补拍，素材一旦丢失损毁，造成的经济损失是无法估量的。所以专业的后期公司都会给素材安排一个王牌保姆，也就是 vip 数字影像工程师。 vip 在拍摄现场就要搭建素材管理站点，拍摄时要监督画面质量，减少费篇，确保拍回来的素材都是能用的。每天拍摄结束后，还要把各类素材考进塞满硬盘的 卡机，并在现场进行数据备份。一般来说， dnt 会在卡机中进行两次备份，运用回后续机房上载时，还要在呼吸中进行一次备份，一式三份。为的就是在任何情况下都可以万无一失。 b 站可以崩，但我们的服务器不能出问题。

下一个啊？下一个叫做什么？一个二 n 点的实信号的 f f t。 那给他，我们再给他升华一下啊， 就是我们来用一次二分之 n 点的 d f t 来求一个 n 点的十对称和一个 n 点的反对称。好，我们先不看这个啊，我们刚才是不是已经就是把一个二分之点的序列啊？给他，呃，用一次 n 点的 d f t 给它求出来了，对吧？啊？意思 n 点 f f t 给它求出来了，那我们知道任何一个信号，任何一个信号 都可以给它分解成一个共和对称型号和加上一个共和反对称的一个相加的形式，对吧？加上一个反对称相加的形式， 如果它的原始信号，这个原始信号是 n 点的，那我们分解出来的这个共和对称和共和反对称，它也分别都是 n 点的，对不对啊？然后如果我们这么分解之后， 实际上我们还是可以通过 s n， 呃，就是 s n， 它的一个 s k 来表示出我们的这个共和反对称的一个它的一个 d f t 和共和对称和共和反对称的它这个 d f t。 啊。所以如果我们进行升华，我们把 这个二二 n 点的实信号再继续给他拆，又能给他拆成两个二 n 点的两个二 n 点的工作对称，工作反对称，对吧？啊？所以就这这就变成了什么？这就变成了 我们用一次 n 点的 f f t 实现了两个二 n 点的实信号， 对吧？用一个 n 点的 f f t 实现了两个二 n 点的信号的 f f t。 虽然看起来很酷炫的样子，但是实际上他就是拆来拆去的，对吧？又把这个实信号给他细分成了共和对称和共和反对称，所以才会导致， 哎，他把这个点数增加了，对吧？其实其实哈，我觉得就是在玩这个计算上的一些游戏啊，在这在这里，那我们来用用一道实力来给大家举个例子啊， 大家看，那这个就是如何用疑似的二分之 n 点的 d f、 t 来求一个 n 点的十对称和一个 n 点的反对称，那跟我们刚才的例子不是一样的吗？对吧？我只不过这儿变成了这儿是 n， 然后这是二恩，对吧？你看，如果把这个题改成用一次恩点来求一个二恩点和一个二恩点十对称和一个二恩点反对称，那不就是这个吗？一个恩点求两个二恩点 啊，所以我们把所有而这这里面，我们把所有的这个点数都除以二啊，就是用一次二分之人点来求一个 n 点式对称，一个 n 点反对称。 首先啊，由于哈，由于我刚才给大家讲到了，由于我们这个实信号哈是从这个实信号拆出来的共和对称和共和反对称，所以我们再给它组合回去啊，我们把这个一个 n 点的实对称和一个 n 点的反对称给它组合成 这个圆信号，一个 n 点的这个 y e n 啊，就把两个 n 点的序列给它变成了一个 n 点的变成了一个 n 点的序列，对吧？啊？还， 而而且他还是十序列，对吧？我们我们只是拆攻和对称和攻的反对称吗？然后 啊，然后我们发现哈，我们这个已经得到了这个 n 点的一个时序列了，对吧？那我们用上面的我们这个这个方法就是一个 n 点的序列时序列，用一次二分之一的 d f t 就可以求出来吗？那实际上它不就是这个吗？对吧？ 这个是一个二 n 点的实信号，用一次 n 点，那我给他说就是一个 n 点的实信号，用一次二分之 n 点的 d f t f f t， 对吧？一次 n 点的 一个按点的，实际上用一次二分之点的 f f t， 就是用我们第七个这种方法，所以大家看，当我们把它重新组合之后，然后就我们用第七种这种方法 就可以得到我们的 y e k， 对吧？我们直接，哎，我们直接用一四二分之 a d f t 就可以得到我们的 y e k， 那得到 y e k 之后 啊，得到我们的 yek 之后哈，我们想想要的是什么？想要的是里面的 sen 和 srn， 很简单啊，对吧？他只不过是把实际上他就是在 yen 这块给他硬生生的拆出了一个供货对称和供货反对称吗？任何一个东西都可以这么拆啊， 对吧？而且我们背过这个公式啊，就不过这个公式你也可以推导出来了。 y e k 和 s e k s r k 有什么关系，对吧？那怎么推啊？ y e n 啊？我们的 s e n 啊，它是等于什么的啊？等于二分之一 y e n 加上 y e 共个符文，对吧？啊？然后给它 这个求这个，呃，因为，因为这个是实数啊，都是实数，所以工作可以拿掉啊，所以我们给直接给他求反面换的话，那就是二分之一 y 一 k 加上 y e k 公鄂，对吧？所以 x 一 k， 它就是等于 r e y e k 的十步 s 二 k 呢？它就是等于 i m y e k 的这样一个虚步成之要， 呃，然后我们就求出来了这个通过 y e k 和 y， 呃，通过 y e k 和，呃我们的这个它的虚实关系啊，我们就表示出来了 s e k 和 s l k 啊， 好，这就是第八个啊，我们怎么怎么样去对它进行一个升华啊？大家看，实际上就是从 y e n 推导出 s e 还是 r n 啊？好，大家听懂的扣一，关于这个。

好，下一个是对两个 n 点实信号的一个 f f t 的一个升华，其实上是一样的嘛，对不对？我们两个 n 点的实信号，它可以拆成什么？ 拆成四个 n 点的啊？用这个一个实线号可以拆成共额对称和这个共额反对称吗？对吧？一个 end 的实信号可以拆成这个两个 n 点的，一个是跟我对称，一个是跟我反对称，所以说两个 n 点就可以拆成四个，他跟那个刚才原理是一模一样的啊。所以我们用一次 n 点 就可以求出四个长度为 n 的序列，不过它有条件的啊，一个是十对称，一个是反对称 啊，所以我们第一步就是构造啊，构造 y e n， 它是等于 s e n 加上 s n y r n 等于 s r n 加 s 四 n 啊，然后两个长度为 n 的十序列， 这两个就是 y in 和 y r n， 对吧？我们把四个 n 点的序序列给它构造成了两个 n 点的式序列，对不对啊？然后两个，那接下来的问题就转换成了什么？两个 n 点的式序列 如何用一次 n 点 d f t 来求出，对吧？呃，一次 f f t 来求出啊？两个 n 点于一次，一次 f f t 求出，这就是第六个方法， 大家看第六个两个 n 点的实信号用一次 n 点 f f d 求出，就是下面 一个过程，所以说第六个和第七个大家一定要完全去掌握，然后第八、第八个和第九个，然后就很简单了，第八个第九个就是利用这个他给他， 呃，给他拆成十十对称和十反对称的时候，然后我们再利用他这个虚实部的一个关系， 我们就可以通过我们求出的 y 一 k 和 y 二 k 来表示出我们的 s 一 k、 s 二 k、 s 三 k、 s 四 k。 啊，这就是这个第九个啊，第九个，一个这样一个技巧。