DSP技术

https://www.cnblogs.com/kanite/category/1318278.html

滤波器稳定性与极点

　　在数字信号处理种，系统的稳定性是一个很重要的问题，比如说在滤波器的设计种，都要求系统必须稳定，否则是无法实用的。那么如何判断系统是否稳定呢？

　　从定义上说，如果输入有界，则输出必定有界的系统是稳定的。从数学上可以推导出，因果系统冲击响应Z变换的收敛域包含单位元的系统是稳定的。从零点极点的角度，则是系统函数的所有极点都在单位元内的系统是稳定的。如何来理解呢？

　　我们先以一个简单的单极点系统为例来理解系统的稳定性。比如有一个单极点系统：

　　H(z)=1/(1-2z-1)

　　表示的是如下的信号处理过程：系统当前输出是当前输出加上2陪的系统上一个时刻输出。这个系统是不稳定的，因为当前输出需要放大上一个时刻的输出，这也就是说，系统存在自激的过程，直观上我们就可以很好理解，自激系统是不稳定的。从分析极点的角度看，这个系统的极点为2，在单位圆外，与数学上的分析是一致的。极点在单位圆内的要求，对一阶极点而言，实际上就是直观上要求系统不能自激。

　　对于高阶极点的情况，由代数知识可知，高阶极点可进行分式分解，也就是高阶极点可以分解为多个一阶极点并联（并联串联都可以构成高阶系统），在并联系统中，只要有一个系统不稳定，整个系统就是不稳定的。这与数学上要求的所有极点都在单位圆内是对应的。对于更一般的即包含零点又包含极点的系统，可以看成一个全零点系统和全极点系统串联而成，零点和系统的稳定性无关，分析和结论与高阶全极点系统完全一致。

数字滤波器

　　1、FIR数字滤波器的设计要点

　　http://blog.sina.com.cn/s/blog_74504f8f0100p5ub.html

　　https://www.cnblogs.com/alifpga/p/7902759.html

　　2、数字滤波器之低通滤波器的设计

　　https://www.cnblogs.com/amanlikethis/p/3508387.html

TMS320C67xx DSP启动过程

　　一、复位后的启动流程

讨论数字滤波器系统稳定性
在数字信号处理中，系统的稳定性是一个很重要的问题，比如说在滤波器的设计中，都要求系统必须稳定，否则是无法使用的。那么，如何判断系统是否稳定呢？
从定义上说，如果输入有界，则输出必定有界的系统是稳定的。从数学上可以推导出，因果系统冲击响应 Z 变换的收敛域包含单位圆的系统是稳定的。从零点极点的角度，则是系统函数的所有极点都在单位圆内的系统是稳定的。如何来理解呢？
我们先以一个简单的单极点系统为例来理解系统的稳定性。比如有一个单极点系统
$H(z)=\frac{1}{1-2 z^{-1}}$

表示的是如下的如下的信号处理过程：系统当前输出是当前的输入加上 2 倍的系统上一时刻输出之和。这个系统是不稳定的，因为当前输出需要放大上ー个时刻的输出，这也就是说，系统存在的自激的过程，直观上我们就可以很好地理解，自激系统是不稳定的。从分析极点的角度看，这个系统的极点为 2, 在单位圆外，与数学上的分析是一致的。极点在单位圆内的要求，对一阶极点而言，实际上也就是直观上要求系统不能自激。
对于高阶极点的情况，由代数学可知，高阶极点可进行分式的分解，也即是高阶极点可以分解成多个一阶极点并联而成的系统，在并联系统中，只要有一个系统不稳定，整个系统就是不稳定的。这与数学上要求的所有极点都在单位圆内是对应的。对于更一般的既包含零点又包含极点的系统，可以看成一个全零点系统和全极点系统串接而成，零点与系统的稳定性无关，分析和结论与高阶全极点系统完全一致。
在滤波器的设计中，可以很方便地通过调整极点改变滤波器的特性。而在许多设计精巧的滤波器中，极点往往在单位圆上或单位圆附近，在实际中还要考虑量化及数的精度等问题，确保系统的稳定性。

对系统稳定性的一些理解

 在数字信号处理中，系统的稳定性是一个很重要的问题，比如说在滤波器的设计中，都要求系统必须稳定，否则是无法使用的。那么，如何判断系统是否稳定呢？
 从定义上说，如果输入有界，则输出必定有界的系统是稳定的。从数学上可以推导出，因果系统冲击响应Z变换的收敛域包含单位圆的系统是稳定的。从零点极点的角度，则是系统函数的所有极点都在单位圆内的系统是稳定的。如何来理解呢？
 我们先以一个简单的单极点系统为例来理解系统的稳定性。比如有一个单极点系统：
 H(z)=1/(1-2z-1)
表示的是如下的如下的信号处理过程：系统当前输出是当前的输入加上2倍的系统上一时刻输出之和。这个系统是不稳定的，因为当前输出需要放大上一个时刻的输出，这也就是说，系统存在的自激的过程，直观上我们就可以很好地理解，自激系统是不稳定的。从分析极点的角度看，这个系统的极点为2，在单位圆外，与数学上的分析是一致的。极点在单位圆内的要求，对一阶极点而言，实际上也就是直观上要求系统不能自激。
 对于高阶极点的情况，由代数学可知，高阶极点可进行分式的分解，也即是高阶极点可以分解成多个一阶极点并联而成的系统，在并联系统中，只要有一个系统不稳定，整个系统就是不稳定的。这与数学上要求的所有极点都在单位圆内是对应的。对于更一般的既包含零点又包含极点的系统，可以看成一个全零点系统和全极点系统串接而成，零点与系统的稳定性无关，分析和结论与高阶全极点系统完全一致。
 在滤波器的设计中，可以很方便地通过调整极点改变滤波器的特性。而在许多设计精巧的滤波器中，极点往往在单位圆上或单位圆附近，在实际中还要考虑量化及数的精度等问题，确保系统的稳定性。

分析
树的直径+二分+multiset有序多重集

(其实可以把multiset换成vector 不过要慢一些)
先用树形DP(或者两次DFS)求树的直径，作为二分的右边界r；树上最短的边作为二分的左边界l

二分最短赛道的长度mid=(l+r)/2

check(mid)函数中判断是否有至少m条赛道满足长度>=mid
如何判断？

把1号点作为根节点(选取任意一条点作为根节点都可以),向子树dfs，从叶节点向上递归。
举个例子：

假设当前节点为x，它的一个子节点为y。x,y构成的边长为w，dfs(y,x,k)表示以y为根的子树中与y相连的长度小于mid的最长链的长度

若dfs(y,x,k)+w>=mid 则ans++

否则将这一条连接x链的长度加到multiset集合s中

(因为这一条链与其他连接x的链相连后长度才有可能>=mid，这也解释了为什么dfs()返回的值总是小于mid)
接下来处理s集合中的链:

找出最短的一条。因为这个集合是从小到大排序，找出s.begin()指向的链即可。

再用lower_bound查找第一个长度>=(mid-*s.begin())的链。

若这样的两条链存在，则这两条链可以配对（长度和>=mid），ans++，并删除这两个数。

否则不断更新长度小于的mid的最长链，最后返回这个值。
感觉思路还挺简单的是不是?   考场上只能打暴力的蒟蒻两行泪
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50050,inf=1e9;
int n,m,head[N],tot=0,ans=0;
int d[N],v[N];
multiset<int>s[N];
multiset<int>::iterator it;
struct edge{
	int ver,to,w;
}e[N*2];
ll read(){
	ll sum=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-')f=-1;
		ch=getchar();
	} 
	while(ch>='0'&&ch<='9'){
		sum=(sum<<3)+(sum<<1)+ch-'0';
		ch=getchar();
	} 
	return sum*f;
}
void add(int x,int y,int z){
	e[++tot].ver=y;
	e[tot].w=z; 
	e[tot].to=head[x];
	head[x]=tot;
}
int dfs(int x,int pre,int k){
	s[x].clear();
	int now;
	for(int i=head[x];i;i=e[i].to)
	{
		int y=e[i].ver;
		if(y==pre)continue;
		now=e[i].w+dfs(y,x,k);
		if(now>=k)ans++;
		else{
		s[x].insert(now);	
		}
    }
    int maxi=0;
    while(!s[x].empty()){
       if(s[x].size()==1){
      return max(maxi,*s[x].begin());
	   }
       it=s[x].lower_bound(k-*s[x].begin());
       if(it==s[x].begin()&&s[x].count(*it)==1){ it++;}
       if(it==s[x].end()){
       	maxi=max(maxi,*s[x].begin());
       	s[x].erase(s[x].begin());
	   }
	   else{
	   	ans++;
	    s[x].erase(it);
	    s[x].erase(s[x].begin());
	   }
	}
	return maxi;
}
int check(int k){
    ans=0;
    dfs(1,0,k);
    if(ans>=m)return 1;
    return 0;
}
int up=0;
void dp(int x){
	v[x]=1;
	for(int i=head[x];i;i=e[i].to){
		int y=e[i].ver;
		if(v[y])continue;
		dp(y);
		up=max(up,d[x]+d[y]+e[i].w);
	    d[x]=max(d[x],d[y]+e[i].w);
	}
}
int main(){
//	freopen("track.in","r",stdin);
//	freopen("track.out","w",stdout);
	n=read();
	m=read();
	int x,y,z,l=inf,r=0,mid,res;
	for(int i=1;i<n;i++)
    {
      x=read();
      y=read();
	  z=read();
      if(z<l)l=z;
      add(x,y,z);
      add(y,x,z);
	}
	dp(1);
	r=up; 
    while(l<=r){
    	int mid=l+(r-l)/2;
    	if(check(mid)){
    		res=mid;
    		l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	cout<<res;
	return 0;
}