PCB板+可编程器件+单片机+PC软件

概念:

在计算机学科中，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题、推销员旅行问题、（命题表达式）可满足问题这类，至今没有找到多项式时间算法解的一类问题，称之为NP类问题。
　　

拿推销员旅行问题为例，假设推销员亨利有向6个城市推销公司产品的任务，并规定了一个旅行预算。他手中有一张航班票价表，他要从A城开始走遍图中的6个城市后返回A城，并且不超出预算，请你帮他找出应走的路线。如果给出的预算宽裕，则任务很简单；如果预算比较紧张，你就得认真设计路线了。你得考虑每一种可能的次序，以使旅费最少。
　　
　　推销员旅行问题
　　
如果有3个城市A，B和C，互相之间都有往返的飞机，而且起始城市是任意的，则有6种访问每个城市的次序：ABC,ACB,,BAC,BCA,CAB,CBA。如果有4个城市，则有24种次序，可以用阶乘来表示：4！=4×3！=4×3×2×1=24；若有5个城市，则有5！=5×4！=120，类似的有6！=720等等。即使用计算机来计算，这种急剧增长的可能性的数目也远远超过计算资源的处理能力，对此，算法复杂性专家史蒂芬.库克（Stephen Cook）评论：”如果有100个城市，需要求出100！条路线的费用，没有哪一台计算机能够胜任这一任务。打个比方，让太阳系中所有的电子以它旋转的频率来计算，就算太阳烧尽了也算不完。问题的关键是某些东西在实践中行不通。”
　　
而NP问题中最困难的问题称之为NP完全问题，已经证明的包括：电话网络的最优几何设计、格子棋的最佳走法。根据库克定理，任意一个NP完全问题如果能够在多项式时间内解决，则所有的NP问题都能在多项式时间内解决，而至今这一问题仍无答案。

争议:

NP并不是NON-POLYNOMIAL，把NP说成是NON-POLYNOMIAL，是望文生义，读书不求甚解。事实上，如果你能够证明某个NP问题是个NON-POLYNOMIAL的问题，你就可以去领那七个百万美元数学大奖中间的一个了。

数学上著名的NP问题，完整的叫法是NP完全问题，也即“NP COMPLETE”问题，简单的写法，是 NP=P？的问题。问题就在这个问号上，到底是NP等於P，还是NP不等於P。证明其中之一，便可以拿百万美元大奖。这个奖还没有人拿到，也就是说，NP问题到底是Polynomial，还是Non-Polynomial，尚无定论。

P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。

什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。

这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间（多项式时间： 运行时间最多是输入量的多项式函数）内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。

完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。

解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。

前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。

NP完全性问题

虽然是计算机系的学生，但自己对于什么是NP问题，什么是NPC问题也并不能很好的解答，就更不用说构造怎样的一种方式来证明一个

问题是不是NP问题了。但算法中涉及了很多这样的问题，压力之下，尽我所能弄懂了，把自己的理解记录下来。

P(Polynomial问题)。在计算机里面，对一个问题寻求一种多项式的算法是一个很好的解答。从理论上来说，如果一个问题能够有多翔

实的解法的话，就算是一个很好的算法了。这种问题总可以找到一个DTM（Deterministic Turing Machine）

NP(Nondeterministic Polynomial问题)。但是对于很多问题来说，他们找不到一个多项式的解决方法，他们只能对应一个NDTM

（Nondeterministic Turing Machine）来解决。可以这样想想：对于下一步的动作，他们也不知道确切的应该怎么办，只能“尝试”很多种方案

才能够得出一个答案，这显然是很费时的，这种问题未NP问题。

NPC(NP Complete)问题，可以这么认为，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难

的问题，这种问题就是NPC问题。

一般说来，如果要证明一个问题是NPC问题的话，可以拿已经是NPC问题的一个问题经过多项式时间的变化变成所需要证明的问题，那

么索要证明的问题就是一个NPC问题了。

NPC问题是一个问题族，如果里面任意一个问题有了多项式的解，那么所有的问题都可以有多项式的解。

电容器的基础知识及检测方法

　　 阻抗匹配是指信号源或者传输线跟负载之间的一种合适的搭配方式。
　　
　　 阻抗匹配分为低频和高频两种情况讨论。我们先从直流电压源驱动一个负载入手。由于实际的电压源，总是有内阻的，我们可以把一个实际电压源，等效成一个理想的电压源跟一个电阻r串联的模型。假设负载电阻为R，电源电动势为U，内阻为r，那么我们可以计算出流过电阻R的电流为：I=U/(R+r)，可以看出，负载电阻R越小，则输出电流越大。
　　 负载R上的电压为：Uo=IR=U*[1+(r/R)]，可以看出，负载电阻R越大，则输出电压Uo越高。
　　 再来计算一下电阻R消耗的功率为： P=I*I*R=[U/(R+r)]*[U/(R+r)]*R=U*U*R/(R*R+2*R*r+r*r)=U*U*R/[(R-r)*(R-r)+4*R*r] =U*U/{[(R-r)*(R-r)/R]+4*r}
　　 对于一个给定的信号源，其内阻r是固定的，而负载电阻R则是由我们来选择的。注意式中[(R-r)*(R-r)/R]，当R=r时，[(R-r)*(R-r)/R]可取得最小值0，这时负载电阻R上可获得最大输出功率Pmax=U*U/(4*r)。即，当负载电阻跟信号源内阻相等时，负载可获得最大输出功率，这就是我们常说的阻抗匹配之一。
　　 对于纯电阻电路，此结论同样适用于低频电路及高频电路。当交流电路中含有容性或感性阻抗时，结论有所改变，就是需要信号源与负载阻抗的的实部相等，虚部互为相反数，这叫做共厄匹配。
　　 在低频电路中，我们一般不考虑传输线的匹配问题，只考虑信号源跟负载之间的情况，因为低频信号的波长相对于传输线来说很长，传输线可以看成是“短线”，反射可以不考虑（可以这么理解：因为线短，即使反射回来，跟原信号还是一样的）。
　　 从以上分析我们可以得出结论：如果我们需要输出电流大，则选择小的负载R；如果我们需要输出电压大，则选择大的负载R；如果我们需要输出功率最大，则选择跟信号源内阻匹配的电阻R。
　　 有时阻抗不匹配还有另外一层意思，例如一些仪器输出端是在特定的负载条件下设计的，如果负载条件改变了，则可能达不到原来的性能，这时我们也会叫做阻抗失配。
　　 在高频电路中，我们还必须考虑反射的问题。当信号的频率很高时，则信号的波长就很短，当波长短得跟传输线长度可以比拟时，反射信号叠加在原信号上将会改变原信号的形状。如果传输线的特征阻抗跟负载阻抗不匹配（相等）时，在负载端就会产生反射。为什么阻抗不匹配时会产生反射以及特征阻抗的求解方法，牵涉到二阶偏微分方程的求解，在这里我们不细说了，有兴趣的可参看电磁场与微波方面书籍中的传输线理论。
　　 传输线的特征阻抗（也叫做特性阻抗）是由传输线的结构以及材料决定的，而与传输线的长度，以及信号的幅度、频率等均无关。例如，常用的闭路电视同轴电缆特性阻抗为75欧，而一些射频设备上则常用特征阻抗为50欧的同轴电缆。另外还有一种常见的传输线是特性阻抗为300欧的扁平平行线，这在农村使用的电视天线架上比较常见，用来做八木天线的馈线。因为电视机的射频输入端输入阻抗为75欧，所以300欧的馈线将与其不能匹配。实际中是如何解决这个问题的呢？不知道大家有没有留意到，电视机的附件中，有一个300欧到75欧的阻抗转换器（一个塑料包装的，一端有一个圆形的插头的那个东东，大概有两个大拇指那么大的）？它里面其实就是一个传输线变压器，将300欧的阻抗，变换成75欧的，这样就可以匹配起来了。
　　 这里需要强调一点的是，特性阻抗跟我们通常理解的电阻不是一个概念，它与传输线的长度无关，也不能通过使用欧姆表来测量。为了不产生反射，负载阻抗跟传输线的特征阻抗应该相等，这就是传输线的阻抗匹配。
　　 如果阻抗不匹配会有什么不良后果呢？如果不匹配，则会形成反射，能量传递不过去，降低效率；会在传输线上形成驻波（简单的理解，就是有些地方信号强，有些地方信号弱），导致传输线的有效功率容量降低；功率发射不出去，甚至会损坏发射设备。如果是电路板上的高速信号线与负载阻抗不匹配时，会产生震荡，辐射干扰等。
　　 当阻抗不匹配时，有哪些办法让它匹配呢？第一，可以考虑使用变压器来做阻抗转换，就像上面所说的电视机中的那个例子那样。第二，可以考虑使用串联/并联电容或电感的办法，这在调试射频电路时常使用。第三，可以考虑使用串联/并联电阻的办法。一些驱动器的阻抗比较低，可以串联一个合适的电阻来跟传输线匹配，例如高速信号线，有时会串联一个几十欧的电阻。而一些接收器的输入阻抗则比较高，可以使用并联电阻的方法，来跟传输线匹配，例如，485总线接收器，常在数据线终端并联120欧的匹配电阻。
　　 为了帮助大家理解阻抗不匹配时的反射问题，我来举两个例子：假设你在练习拳击——打沙包。如果是一个重量合适的、硬度合适的沙包，你打上去会感觉很舒服。但是，如果哪一天我把沙包做了手脚，例如，里面换成了铁沙，你还是用以前的力打上去，你的手可能就会受不了了——这就是负载过重的情况，会产生很大的反弹力。相反，如果我把里面换成了很轻很轻的东西，你一出拳，则可能会扑空，手也可能会受不了——这就是负载过轻的情况。另一个例子，不知道大家有没有过这样的经历：就是看不清楼梯时上/下楼梯，当你以为还有楼梯时，就会出现“负载不匹配”这样的感觉了。当然，也许这样的例子不太恰当，但我们可以拿它来理解负载不匹配时的反射情况。

特性阻抗（Characteristic Impedance）

当某讯号方波，在传输线组合体的讯号线中，以高准位（High Level）的正压讯号向前推进时，则距其最近的参考层（如接地层）中，理论上必有被该电场所感应出来的负压讯号伴随前行（等于正压讯号反向的回归路径Return Path），如此将可完成整体性的回路（Loop）系统。该“讯号”前行中若将其飞行时间暂短加以冻结，即可想象其所遭受到来自讯号线、介质层与参考层等所共同呈现的瞬间阻抗值（Instantanious Impedance），此即所谓的“特性阻抗”。　　是故该“特性阻抗”应与讯号线之线宽（w）、线厚（t）、介质厚度（h）与介质常数（Dk）都扯上了关系。

阻抗匹配不良的后果　　由于高频讯号的“特性阻抗”（Z0）原词甚长，故一般均简称之为“阻抗”。读者千万要小心，此与低频AC交流电（60Hz）其电线（并非传输线）中，所出现的阻抗值（Z）并不完全相同。数位系统当整条传输线的Z0都能管理妥善，而控制在某一范围内（±10﹪或 ±5﹪）者，此品质良好的传输线，将可使得杂讯减少，而误动作也可避免。　　但当上述微带线中Z0的四种变数（w、t、h、 r）有任一项发生异常，例如讯号线出现缺口时，将使得原来的Z0突然上升（见上述公式中之Z0与W成反比的事实），而无法继续维持应有的稳定均匀（Continuous）时，则其讯号的能量必然会发生部分前进，而部分却反弹反射的缺失。如此将无法避免杂讯及误动作了。例如浇花的软管突然被踩住，造成软管两端都出现异常，正好可说明上述特性阻抗匹配不良的问题。

阻抗匹配不良造成杂讯　　上述部分讯号能量的反弹，将造成原来良好品质的方波讯号，立即出现异常的变形（即发生高准位向上的Overshoot，与低准位向下的Undershoot，以及二者后续的Ringing）。此等高频杂讯严重时还会引发误动作，而且当时脉速度愈快时杂讯愈多也愈容易出错。

在设计高速PCB电路时，阻抗匹配是设计的要素之一。而阻抗值跟走线方式有绝对的关系， 例如是走在表面层(microstrip)或内层(stripline/double stripline)，与参考层(电源层或地层)的距离，走线宽度，PCB材质等均会影响走线的特性阻抗值。也就是说要在布线后才能确定阻抗值。一般仿真软件会因线路模型或所使用的数学算法的限制而无法考虑到一些阻抗不连续的布线情况，这时候在原理图上只能预留一些terminators(端接)，如串联电阻等，来缓和走线阻抗不连续的效应。真正根本解决问题的方法还是布线时尽量注意避免阻抗不连续的发生。 IBIS模型的准确性直接影响到仿真的结果。基本上IBIS可看成是实际芯片I/O buffer等效电路的电气特性资料，一般可由SPICE模型转换而得 (亦可采用测量， 但限制较多)，而SPICE的资料与芯片制造有绝对的关系，所以同样一个器件不同芯片厂商提供，其SPICE的资料是不同的，进而转换后的IBIS模型内之资料也会随之而异。也就是说，如果用了A厂商的器件，只有他们有能力提供他们器件准确模型资料，因为没有其它人会比他们更清楚他们的器件是由何种工艺做出来的。如果厂商所提供的IBIS不准确， 只能不断要求该厂商改进才是根本解决之道。

这里给出自由空间传播时的无线通信距离的计算方法：所谓自由空间传播系指天线周围为无限大真空时的电波传播，它是理想传播条件。电波在自由空间传播时，其能量既不会被障碍物所吸收，也不会产生反射或散射。

通信距离与发射功率、接收灵敏度和工作频率有关。

[Lfs](dB)=32.44+20lgd(km)+20lgf(MHz)

式中Lfs为传输损耗，d为传输距离，频率的单位以MHz计算。

由上式可见，自由空间中电波传播损耗（亦称衰减）只与工作频率f和传播距离d有关，当f或d增大一倍时，［Lfs］将分别增加6dB.

下面的公式说明在自由空间下电波传播的损耗

Los = 32.44 + 20lg d(Km) + 20lg f(MHz)

Los 是传播损耗，单位为dB

d是距离，单位是Km

f是工作频率，单位是MHz

下面举例说明一个工作频率为433.92MHz，发射功率为＋10dBm(10mW)，接收灵敏度为-105dBm的系统在自由空间的传播距离：

1. 由发射功率+10dBm，接收灵敏度为-105dBm

Los = 115dB

2. 由Los、f

计算得出d =30公里

这是理想状况下的传输距离，实际的应用中是会低于该值，这是因为无线通信要受到各种外界因素的影响，如大气、阻挡物、多径等造成的损耗，将上述损耗的参考值计入上式中，即可计算出近似通信距离。

假定大气、遮挡等造成的损耗为25dB，可以计算得出通信距离为：

d =1.7公里

结论: 无线传输损耗每增加6dB, 传送距离减小一倍。