精华内容
下载资源
问答
  • 重叠相加法和重叠保留法的原理

    万次阅读 2017-11-09 22:31:58
    重叠相加法和重叠保留法的原理

    重叠相加法和重叠保留法的原理

    DFT(FFT)的一个应用,就是计算线性卷积。

    h(n)x(n)长度分别为NM,对于L点循环卷积,若满足L>=N+M1,则有yc(n)=yl(n)

    对于两个序列长度相差很大的情况,例如M>>N,为了节省存储空间并实现实时处理,则需要采取将长序列分段的方法。因为可以通过求循环卷积来得到线性卷积,所以以下先讨论循环卷积的情况。

    仍然对于上述的h(n)x(n),当M>>N时,计算每一个yc(n)最多只需要N次(较短序列的长度)计算,即从x(nN+1)~x(n)之间的N个值。所以即便将x(n)分解也可以得到卷积结果。

    现将x(n)分解为许多长度为KKN的短序列x0(n),x1(n),x2(n)...。例如对于

    x2(n),0nK1
    N1nK1时,求得y2(n)所需的x(nN+1)~x(n)之间的N个值可完全由x2(n)提供,但是当0nN2时则无法只由x2(n)提供全部所需的x(n),为了解决这个问题便提出了重叠相加法和重叠保留法。
    1. 重叠相加法
      根据

      y(n)=h(n)x(n)=h(n)m=0xk(n)=m=0h(n)xk(n)=m=0yk(n)
      yk(n)求和即可得到原本的y(n),其本质就是对不完全的yk(n)进行补全,而原本就满足N1nK1yk(n)则实际上不改变其值。
    2. 重叠保留法
      此方法需x(n)分段时每两段之间需要重叠N1个值(实际上大于该值都可以,但取N1时最节省运算量),然后对所求的yk(n)去除前N1个点。本质就是直接删去0nN2yk(n),只保留N1nK1yk(n),因此在对分段时需要对x(n)重叠分段,保证对于每个n都有满足N1nK1xk(n)

    综上,对于两种方法,都是为了解决相同的问题,即x(n)分段后每段内前N1yk(n)不完全的问题。

    展开全文
  • DFT计算线性卷积——重叠保留法

    万次阅读 2016-09-25 23:07:45
    DFT计算线性卷积——重叠保留法引入设h(n)和x(n)都是有限长序列,长度分别为N和M。它们的线性卷积和循环卷积分别表示如下: yc(n)=h(n)∗x(n)=∑m=0N−1h(m)x(n−m)y_c(n)=h(n)*x(n)=\sum_{m=0}^{N-1}h(m)x(n-m) ...

    DFT计算线性卷积——重叠保留法

    引入

    设h(n)和x(n)都是有限长序列,长度分别为N和M。它们的线性卷积和循环卷积分别表示如下:

    yc(n)=h(n)x(n)=m=0N1h(m)x(nm)

    yl(n)=h(n)x(n)=[m=0L1h(m)x((nm))L]RL(n)

    其中 Lmax[N,M]x((n))L=i=x(n+iL)

    只有当循环卷积长度LN+M1时,线性卷积等于循环卷积

    yc(n)=[i=yl(n+iL)]RL(n)

    否则时域混叠

    重叠保留法

    所谓重叠保留法,就是对输入序列进行分段 (设长度为M),但相邻两段必须重叠V个点,然后计算各段与h(n) (设长度为N) 的L(L≥M)点循环卷积,得到输出序列ym(n),m表示第m段的循环卷积计算输出。最后,从ym(n)中选取B个样值顺序连接得到y(n)
    其中 V=N-1,B=M-V=M-N+1,B应取ym(n)中第V+1 ~ V+B共计B个样值,若记n=0,1,……,M-1,则B的取值为n=N-1,N,……,M-1时的ym(n)的值。

    由线性卷积的定义可以看出,当计算n=n0时的线性卷积时,与x(n0)及其前N-1个值有关。所以计算h(n)xm(n)时,结果(共N+M-1个数值)的前N-1个值与后N-1个值是有误的,只有中间的M-N-1个值是正确的,即是应当选取的B个样值。因为计算h(n)xm(n)时,n<0及n>M-1时认为xm(n)=0,而实际xm(n)的前面xm1(n)与后面xm+1(n)是不一定为零的。故对输入序列进行分段时,相邻两段必须重叠V个点,有误点的卷积值要再次计算。

    实际中计算机计算循环卷积要快于线性卷积,当L=M时,ym(n)=h(n)xm(n)yml(n)=h(n)xm(n),由线性卷积与循环卷积的关系式可以看出yml(n)在做以L为周期的延拓时相邻两次延拓重叠了N-1个点,即L点循环卷积的结果(长度为M)与线性卷积结果(长度为N+M-1,取前M项比较)相比,前N-1个值有误(混叠),后M-(N-1)个值相等。恰好与实际相比yml(n)结果的前N-1项也是有误的(见上一段分析),故循环卷积与直接计算线性卷积的分析结果一致,都舍去前N-1个值而保留接下来的M-(N-1)个值。

    当取L>M时,yml(n)在做以L为周期的延拓时相邻两次延拓重叠小于N-1个点,但由于受限仍然应舍去前N-1个值而保留接下来的M-(N-1)个值。原因见直接计算线性卷积的分析。

    Ⓛ:代表L点循环卷积
    * :代表线性卷积

    部分内容参考《数字信号处理(第三版)》高西全,丁玉美编著
    ISBN 978-7-5606-0922-5/TN•0160
    博主学习时的一点见解,欢迎斧正。

    展开全文
  • 重叠相加法&重叠保留法

    万次阅读 多人点赞 2017-09-07 15:28:29
    1.问题 上一篇中介绍了利用循环卷积计算线性卷积,但是当两个卷积项长度相差很大时,短序列需要补的0非常多,这样无助于计算量的减小,并且这种方法需要等长序列全部输入完之后才开始计算,这会造成输出有很大的...

    1.问题

      上一篇中介绍了利用循环卷积计算线性卷积,但是当两个卷积项长度相差很大时,短序列需要补的0非常多,这样无助于计算量的减小,并且这种方法需要等长序列全部输入完之后才开始计算,这会造成输出有很大的延时。
      但是实际中这种现象很长见,比如对音频信号进行数字滤波,滤波器抽头系数点数较少,而MIC一直在录音,需要滤波的信号可以认为是无限长的,如果等录很久后才开始进行滤波,则会造成需要存储的数据量急剧增大,同时输出的信号也会有较长的延时,这个时候怎样保证延时小的同时输出的结果跟对长信号滤波的结果相同呢

    滤波器系数h(n),h(n),长度为NN,输入信号x(n)x(n),长度为无限长,输出y(n)y(n)即为它们的卷积


     y(n)=Mm=0x(nm)h(m) y(n)=∑m=0Mx(n−m)h(m)

    那怎么利用频域计算呢,两种方法,重叠相加(overlap-add)和重叠保留(overlap-save)

    重叠相加法(OLA)

    1. x(n)x(n)分段,每段长为MM,保证MM接近NN即可,然后将xk(n)xk(n)补零延长到L=M+N1L=M+N−1,计算LLFFTFFT得到XK(K)XK(K)
    2. h(n)h(n)补零延长至L=M+N1L=M+N−1,计算LLFFTFFT得到H(K)H(K)。
    3. 计算ykk=XK(K)H(K)yk(k)=XK(K)∗H(K),然后求LL点的IFFT,IFFT,得到yk(K)yk(K)

    观察可以发现,每段xk(n)xk(n)长为MM,恢复得到的yk(K)yk(K)长为LL>ML,L>M,那怎么将每段yk(K)yk(K)拼接起来呢,方法为在还原的时候将重叠部分相加就可以了,这也是重叠相加法名字的由来。

    用matlab验证一下,很简单,因为matlab的FFTFFT指定长度后会自动补零,那么上述过程几行代码就可以验证了

    close all
    clear all
    h = [1,7,8];
    N = length(h);
    
    x = [5,8,9,6,3,4,8,2,1,7,5,6];
    M = 4;
    
    L = M+N-1;
    
    
    x1 = x(1:4);
    x2 = x(5:8);
    x3 = x(9:12);
    
    H = fft(h,L);
    
    Y1 = fft(x1,L).*H;
    Y2 = fft(x2,L).*H;
    Y3 = fft(x3,L).*H;
    
    y1 = ifft(Y1,L);
    y2 = ifft(Y2,L);
    y3 = ifft(Y3,L);
    
    y_conv = conv(h,x)
    y_ola = [y1(1:4),y1(5:6)+...
                    y2(1:2),y2(3:4),y2(5:6)+...
                                     y3(1:2),y3(3:6)]

    上面代码为了看的更清楚,循环都不用了,可以对比看看结果直接计算的y_conv与y_ola是不是相等的

    重叠保留法(OLS)

    1. x(n)x(n)分段,每段长为MM,保证MM接近NN即可,然后 将每段xk(n)xk(n)向前多取N1N−1个点,第一段前面补N1N−1个0,则每段xk(n)xk(n)长为L=M+N1L=M+N−1,计算LLFFTFFT得到XK(K)XK(K)
    2. h(n)h(n)补零延长至L=M+N1L=M+N−1,计算LLFFTFFT得到H(K)H(K)。
    3. 计算ykk=XK(K)H(K)yk(k)=XK(K)∗H(K),然后求LL点的IFFT,IFFT,得到yk(K)yk(K)

    分析下上面的步骤,对比下线性卷积与圆周卷积:
    线性卷积:
    xk(n)xk(n):L=M+N1L=M+N−1
    h:Nh:N
    yk(n):M+2N2yk(n):M+2N−2
    圆周卷积:
    XK(K)XK(K):L=M+N1L=M+N−1
    H(K)L=M+N1H(K):L=M+N−1
    Yk(K):L=M+N1Yk(K):L=M+N−1
    可以看到线性卷积的长度(M+2N2M+2N−2)>圆周卷积长度(M+N1M+N−1),由线性卷积与圆周卷积的关系可知当圆周卷积长度小于线性卷积长度时会发生混叠,那就在恢复的时候,丢掉前面混叠的部分(M+2N2M+2N−2)-(M+N1M+N−1=N1=N−1,每段仅保留后面MM点就行,这也是重叠保留名字的由来。
    代码如下:

    close all
    clear all
    h = [1,7,8];
    N = length(h);
    
    x0 = [5,8,9,6,3,4,8,2,1,7,5,6];
    M = 4;
    
    x = [zeros(1,N-1),x0];
    
    L = M+N-1;
    
    
    x1 = x(1:6);
    x2 = x(5:10);
    x3 = x(9:14);
    x4 = [x(13:14),zeros(1,4)];
    
    H = fft(h,L);
    
    Y1 = fft(x1,L).*H;
    Y2 = fft(x2,L).*H;
    Y3 = fft(x3,L).*H;
    Y4 = fft(x4,L).*H;
    
    
    y1 = ifft(Y1,L);
    y2 = ifft(Y2,L);
    y3 = ifft(Y3,L);
    y4 = ifft(Y4,L);
    
    
    y_conv = conv(h,x0)
    y_ols = [y1(3:6),y2(3:6),y3(3:6),y4(3:6)]
    
    
    

    可以对比看看y_conv与y_ols是否相同

    参考链接:

    Frequency-Domain FIR Filter

    卷积

    展开全文
  • 重叠相加法和重叠保留法

    千次阅读 2020-12-02 20:25:14
    重叠相加(OLA) 1、将x(n)分段,每段长为M,保证M接近N即可,然后将xk(n)补零延长到L=M+N−1,计算L点FFT得到XK(K) 2、将h(n)补零延长至L=M+N−1,计算L点FFT得到H(K)。 3、计算yk(k)=XK(K)∗H(K),然后求L点的...

    参考链接:https://blog.csdn.net/u010592995/article/details/77882183
    https://blog.csdn.net/Biegeda/article/details/78494881

    重叠相加法(OLA)

    1、将x(n)分段,每段长为M,保证M接近N即可,然后将xk(n)补零延长到L=M+N−1,计算L点FFT得到XK(K)
    2、将h(n)补零延长至L=M+N−1,计算L点FFT得到H(K)。
    3、计算yk(k)=XK(K)∗H(K),然后求L点的IFFT,得到yk(K)

    观察可以发现,每段xk(n)长为M,恢复得到的yk(K)长为L,L>M,那怎么将每段yk(K)拼接起来呢,方法为在还原的时候将重叠部分相加就可以了,这也是重叠相加法名字的由来。

    圆周卷积

    也叫循环卷积,两个长度为N的有限场序列x(n)和h(n)的循环卷积定义为在这里插入图片描述
    即循环卷积相当于周期延拓后的序列x˜(n)和h˜(n)做周期卷积后再取主值区间,若x(n)和h(n)的离散傅里叶变换为X(K)和H(K),则有
    在这里插入图片描述
    即时域中的循环卷积对应于其离散傅里叶变换的乘积,循环卷积的结果y(n)长度为N。

    时域中的循环卷积对应于其离散傅里叶变换的乘积

    线性卷积

    通常所说的卷积就是指线性卷积,设x(n)、h(n)长度分别为M和N,则它们的线性卷积结果为
    在这里插入图片描述

    重叠保留法(OLS)

    将x(n)分段,每段长为M,保证M接近N即可,然后 将每段xk(n)向前多取N−1个点,第一段前面补N−1个0,则每段xk(n)长为L=M+N−1,计算L点FFT得到XK(K)
    将h(n)补零延长至L=M+N−1,计算L点FFT得到H(K)。
    计算yk(k)=XK(K)∗H(K),然后求L点的IFFT,得到yk(K)。分析下上面的步骤,对比下线性卷积与圆周卷积:
    线性卷积
    xk(n):L=M+N−1
    h:N
    yk(n):M+2N−2
    圆周卷积:
    XK(K):L=M+N−1
    H(K):L=M+N−1
    Yk(K):L=M+N−1
    可以看到线性卷积的长度(M+2N−2)>圆周卷积长度(M+N−1),由线性卷积与圆周卷积的关系可知当圆周卷积长度小于线性卷积长度时会发生混叠,那就在恢复的时候,丢掉前面混叠的部分(M+2N−2)-(M+N−1)=N−1。

    总结来说,此方法需x(n)分段时每两段之间需要重叠N−1个值(实际上大于该值都可以,但取N−1时最节省运算量),然后对所求的yk(n)去除前N−1个点。本质就是直接删去0≤n≤N−2的yk(n),只保留N−1≤n≤K−1的yk(n),因此在对分段时需要对x(n)重叠分段,保证对于每个n都有满足N−1≤n≤K−1的xk(n)

    展开全文
  • #include<cmath> #include<iostream> #include<cstdio>...//循环链表的创建 typedef struct circular_lnode{ int data; struct circular_lnode *next; }circular_lnode,*circula...
  • 循环buffer

    千次阅读 2017-08-27 16:52:03
    循环buff即循环缓冲区,顾名思义,就是可以不断写不断读的一个局域,在缓冲区写满...重点代码分析:1、计算空闲空间/数据空间大小:设定总空间为size-1,始终保留1个字节来表示buff已满。先看看负数的二进制我们来求-
  • BigDecimal除保留两位小数

    万次阅读 2016-07-31 08:54:20
    BigDecimal numBigDecimal=new BigDecimal(5.33); numBigDecimal=ConvertNumber...//调用,5.33/3后保留两位小数1.7766666=1.78 //BigDecimal 截取小数位,四舍五入 public BigDecimal ConvertNumber(BigDecimal bi
  • 循环结构

    千次阅读 2015-07-20 13:58:35
    步长型循环(For语句) for 语句用来描述已知重复次数的循环结构。 for 语句有两种形式: (1) for 循环变量:=初值 to 终值 do 语句; (2) for 循环变量:=初值 downto 终值 do 语句; 例:计算1+2+3+...
  • c语言循环优化

    千次阅读 2014-01-13 11:53:27
    往往是循环语句,特别是多层嵌套的循环语句。因此,掌握循环优化的各种实用技术是提高程序效率的 利器,也是一个高水平程序必须具备的基本功。 本节有关各种循环优化技术的讨论基本上以下面的一个程序段为对象,...
  • 科学计数保留两位小数。 输入 无 输出 无 样例输入 无 样例输出 无 分析:题目本身不是很难,只是需要思考需要如何循环。明白两点即可,一是循环,一个数的阶乘结果是建立在前一个数的阶乘结果之上的,...
  • 分数化小数(decimal)(C语言描述) 分数化小数四舍五入情况
  • 两个有限长的序列,当一个序列的长度远大于另外一个序列的时候,如果仍采用常规的处理方法,效率会很低,所以引入了重叠相加法和重叠保留法。下面我们就利用MATLAB来实现这两种方法。 在下面的代码中,我使用了一个...
  • BigDecimal的divide方法进行除时当不整除,出现无限循环小数时,就会抛异常的,异常 如下:java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result. 应用...
  • 循环神经网络(RNN)简介

    万次阅读 2018-09-01 17:05:51
    人工神经网络介绍参考: https://blog.csdn.net/fengbingchun/article/details/50274471  ... 这里在以上两篇基础上整理介绍循环神经网络: 前馈网络可以分为若干”层”,各层按信号传输先后顺序依次排列...
  •  //1 } 4.5、科学计数 有些项目可能会涉及到从Excel导入数据,但如果Excel里单元格类型为数值,但内容数据太长时(如银行账号),导入时,会默认读取为科学计数,用以下代码便轻松解决。 [java] view plain...
  • statsby: 不用循环语句的循环

    千次阅读 2019-08-25 15:24:35
    命令执行后,除了在屏幕上以表格或图形的方式呈现一些核心结果,内存中还保留了大量的结果。这些结果统称为返回值,包括 统计量 (如 样本数,R-square,F 统计量等)、文件路径、命令名称,甚至还包括 矩阵 和 函数 ...
  • 在计算机科学中,分治是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解...
  • 将一张100元的钞票换成1元、5元和10元的钞票,每种钞票至少一张,编写程序输出所有的换循环次数需要尽可能地少。 看到这个题就是个水题,但是最后这一句话把难度加大了一点点,虽然还是有点低。但是看别人写完...
  • 第一个状态: 当线程一刚刚扩容好数组,此时刚要准备进行rehash,但是此时线程二...此时他又会把节点5放在线程一中的首部此时也就是5---->9----5(后面这部分的9–>5是保留的第三个状态留下的),到这里就形成了死循环
  • 深度学习之RNN(循环神经网络)

    万次阅读 多人点赞 2018-05-28 20:49:09
    ”的信息,实现了对重要内容的保留和对不重要内容的去除. 通过 Sigmoid 层输出一个0到1之间的概率值,描述每个部分有多少量可以通过,0表示“不允许任务变量通过”,1表示“运行所有变量通过 ”.  用于遗忘的门...
  • 循环删除数组中元素的正确方法

    千次阅读 2018-09-12 11:03:27
    循环删除数组中元素的正确方法 提起循环删除数组中的元素,最先想到的就是使用for循环和数组的splice方法来实现(正序循环删除方法),如下代码用来实现删除数组中大于2的元素: let arr = [1, 2, 3, 4, 5, 4,...
  • C语言将循环小数/有限小数转换为分数

    千次阅读 多人点赞 2018-12-24 01:18:19
    早在小学的时候我就对循环小数非常感兴趣,加上初中和高中对循环小数可以说有一定基础研究,因此想到写一个将循环下小数转换为分数的程序,非常有意思,并且对初学者来说,它的输入输出格式的转换也是一大难点。...
  • 循环链表(Circular Linked List)

    千次阅读 2016-05-03 00:42:13
    循环链表(Circular Linked List) 1. 循环链表的概念 1.1 循环链表的定义 循环链表是另一种形式的表示线性表的链表。 1.2 循环链表的结点结构 循环链表的结点包括两个部分:数据域和指针域。 (1)数据域(data),...
  • LSTM和循环网络RNN学习简记

    千次阅读 2017-07-29 11:24:39
    前馈网络回顾要理解循环网络,首先需要了解前馈网络的基础知识。这两种网络的名字都来自于它们通过一系列网络节点数学运算来传递信息的方式。前馈网络将信息径直向前递送(从不返回已经过的节点),而循环网络则将...
  • 循环队列的基本操作-C语言

    千次阅读 多人点赞 2019-06-24 11:54:45
    循环队列的基本操作一、循环队列二、循环队列的理解 一、循环队列 为充分利用向量空间,克服上述“假溢出”现象的方法是:将为队列分配的向量空间看成为一个首尾相接的圆环,并称这种队列为循环队列(Circular Queue)...
  • 循环神经⽹络中的梯度计算⽅中,我们发现,当时间步数较⼤或者时间步较小时,**循环神经⽹络的梯度较容易出现衰减或爆炸。虽然裁剪梯度可以应对梯度爆炸,但⽆解决梯度衰减的问题。**通常由于这个原因,循环...
  • 时间 2017-06-27 15:57:39 机器之心 原文 ... 主题 LSTM ...在 LSTM 循环神经网络面临长序列输入时,我们应该怎样应对?Jason Brownlee 给了我们 6 种解决方案。 长短期记忆(LSTM)循
  • Attention和增强循环神经网络

    千次阅读 2016-12-26 20:12:42
    本文重点讲述的是一种被称为attention的方法,有的人将其译为“聚焦”,但觉得这种翻译将原文对神经网络拟人化的手法给扔掉了,因此保留了原来的称谓。Attention,顾名思义,就是让神经网络对部分内容引起注意,而...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 85,649
精华内容 34,259
关键字:

循环保留法