LTE物理层信道检测算法总结文档

第一篇：LTE物理层信道检测算法总结文档

信道均衡算法总结

信道均衡技术研究的焦点主要集中在计算复杂度与误码性能的折中，即用最小的计算代价获得最优的检测效果。

为了恢复信号放送方的信息，接收端必须知道如下信息： 1)信道的增益矩阵H。2)加性高斯白噪声n。

信号接收信息Y可以表示：

YHxn

一、传统检测方法： 1.1、线性检测算法：

线性检测思想：在MIMO系统的接收信号中，存在不同的发射天线间的信号的相互干扰。相对于某一根发射天线的信号子流，其他天线上信号则看成干扰。相对于某一根发射天线的信号子流，其他发射天线上信号则看成干扰，将接收信号乘以一个线性滤波矩阵，使得干扰信号从被检测信号中消除，这就是“干扰置零”的主要思想。

线性检测要求系统中的接收天线数N不小于发射天线数M，否则对于线性检测而言，即使在没有噪声的情况下也无法获得好的技术检测效果。

1.1.1 ZF算法

线性迫零ZF算法是利用信道传输矩阵H的伪逆矩阵H+作为线性运算组合器来实现信号分离的一种检测算法。迫零的译码算法就是找到一个加权矩阵W，使其满足以下关系：

WiHj1,ij

WiHj0,i!j

其中Wi,Hj分别表示加权矩阵W的第i行与信道矩阵H的第j列(满足这个条件的加权矩阵就是H的伪逆矩阵H+)；

ZF算法步骤如下：

1)先根据上述原则得到并计算加权矩阵H(HHH)1HH； 2)将加权矩阵左乘接收信号，式子变为HrsHn；

3)直接利用公式SQ(Hr)进行量化，从而对信号进行译码。

ZF算法把来自每个发送天线的信号当作希望得到的信号，而剩下的部分当作干扰，所以能够完全禁止各个之间的互扰。

1.1.2 MMSE算法

为了改善ZF算法的性能，可以在设计滤波器矩阵的时候将噪声的影响考虑进去，这就是MMSE检测。MMSE检测是通过滤波矩阵G的设计使得实际传输的信号和滤波输出信号之间均方误差MSE保持最小。

MMSE算法在一定程度上改善了迫零算法的性能，它是用一个新的矩阵HMMSE来代替迫零算法中的H.利用以下原则得到加权矩阵: ^HMMSEargmin(E{||HMMSErs||2})，其中E代表期望值。

MMSE算法步骤如下：

21H1)先根据上述原则得到并计算加权矩阵HMMSE(HHI)H，其中：2为噪声方

差；为发送信号功率。如果对每根发射天线信号能量进行归一化，则在公式中可以省略，此时=1.2)将加权矩阵左乘以接收信号，式子变为HMMSErHMMSEHsHMMSEn。

H3)直接利用公式SQ(HMMSEr)进行量化，从而对信号进行译码． ^

1.2、干扰消除检测算法

线性检测没有利用多天线的分集增益，为了得到分集增益可以利用判决反馈的思想，将已判决的信号反馈回去，提高检测的可靠性。判决反馈可以用于同一符号的检测。干扰消除是将判决反馈用于不同符号间的检测，将从待检测信号中消除已检测出信号的影响，从而降低了检测信号中的干扰量，提高判决的可靠性，同时积累了分集增益。

干扰消除包括干扰消除SIC、并行干扰消除PIC以及可以进一步提高性能的排序串行干扰消除OSIC。这几种检测方法的基础都是基于不同准则的线性检测。并行干扰消除是采用并行的方式来消除符号间的干扰，即在所有的信号被解调之后，同时将干扰接收信号去除。

1.2.1 串行干扰消除(SIC)串行干扰消除在检测到干扰信号波形时，一次一次地将干扰从接收信号中去除，核心思想是通过对接收信号进行递归估计，即先选择一种线性检测算法(ZF算法或者MMSE算法)对某一种发射天线符号进行检测，然后抵消该信号对其他天线上信号的干扰，再依次对各个发射天线上的发送信号进行线性检测、干扰抵消，直到估计出全部的发送符号。

SIC处理过程步骤：

1)干扰置零。从剩余未检测的符号中任选一个进行检测，方便起见，可以每次选择第一个符号作为待检测符号。

X1GY1（1）

X1Q(X1)（2）

式(1)中G1为基于某种线性检测准则(ZF、MMSE)的滤波矩阵的第一行，X1为第一层发送符号的滤波输出，Q(.)为判决操作，判断出的符号作为第一层所发送符号的估计值。

2)干扰消除。假设判决正确，从接收信号中消除掉该信号的影响，产生一个新的系统模型。

~~YYH1X1HXN(3)其中式(3)中H1为信道矩阵H(Nr*Nt)的第一列，表示第一根发送天线到所有接收天线的信道响应。H[H2,H3,...HNT]表示删除了第一列后的NR(NT1)维的等效信道矩阵，~~~~X[X2,X3,...XNT]T表示删除了第一个发送天线上发送符号后(NT1)1维等效发送符号，Y表示消除第一层符号的影响的接收信号。

然后返回步骤(1),接着进行下一个符号的检测，每一次检测出的符号对应不同的发射天线，直至检测出所有的发送符号。

1.2.2 OSIC OSIC检测算法是一类改进的SIC检测算法，它在传统未排序SIC算法干扰置零和干扰消除操作的基础上，增加了符号检测的排序操作，可以有效地降低SIC检测过程中误差传播的可能性，从而大大提高系统的检测性能。

OSIC检测算法的基本思想在于执行多级的、优化排序的迭代干扰消除。OSIC的操作步骤是：排序、干扰置零和干扰消除。1)首先根据一定的排序准则，从当前所有剩余未检测的发送数据流中选择出一个待检测数据流；

2)然后通过采用某种零化准则的滤波完成该数据流检测；

3)最后从接收信号中消除被检测数据流的干扰，准备进入下一级。

4)排序、干扰置零和干扰消除操作不断重复、直至经过多级处理以后，所有发送数据符号均被检测为止。~~1.3 最优检测算法

最大似然(ML)算法是MIMO系统中最优的信号均衡算法，其基本原理是：将接收信号对所有的可能的发送符号域进行全局搜索，找到与接收信号距离最小的发射符号作为原始的发送符号，即使给定r的情况下x的最大似然估计值达到最大，其实现方法是由所有调制星座图的点计算得出的。

最大似然检测算法其计算公式为：

Xargmax(y|x)

其中：

(y|x)(det(R))1exp((yHx)HR1(yHx))()2NRexp(yHx/)22

这里，RE(H)2I。由上式最大似然检测算法可简化为:

XargminyHx

由上式可知，最大似然准则等效于最小欧式距离准则。由此可知最大似然检测算法的复杂度与候选的x的数目成正比，换句话说其复杂度随着发射天线数目、每天线平均传输速率的增长呈指数增长，因此当发射天线数目较多、传输速率较高时最大似然检测算法的复杂度极高，难以实现。

二、新算法

2.1 球形译码算法(SD算法)球形译码算法是一种性能接近于最大似然检测而复杂度低的检测方法，将系统实数话后用球形检测进行译码，复杂度明显降低。SD算法和ML算法不同是：ML算法是在整个向量空间上搜索最有可能的发送向量，使得该向量经过信道后于接收信号向量欧式距离最小，SD算法是在以接收信号点Y为圆心，r为半径的空间内搜索最有可能的发送向量。

算法思路：球形译码的作用就是判断Hs空间中的点是否在以x为球心、半径为d的超球体里面，下面讨论具体如何接收信号x是否在半径为d的超球体内，条件如下所示：

2d2||xHs||2（4）

其中x为接收信号矢量，s为发送信号矢量，H为冲击响应矩阵，d为搜索半径，d其实为允许的误差范围，如果d太大就增加了搜索范围，从而增加复杂度。

对冲击响应矩阵H进行QR分解，H矩阵大小为n行m列，其中nm，m为发送天线，n为接收天线。

HQR（5）

其中R是mm的上三角矩阵，并且Q=[Q1Q2]是一个nn正交矩阵，矩阵Q1和Q2分别为矩阵Q的前m列和nm列，因此公式(4)可变换为：

Q1*2RR2**2dx[Q1Q2]s*xsQ1xRsQ2x(6)

00Q2式(6)中*表示共轭转置，将右侧移项得到： dQ2x*令yQ1x，ddQ2x，公式改写为： '22*22*222Q1*xRs(7)

2d(yiri,jsj)(8)

'2i1jim2其中ri,j是矩阵R的元素，R是上三角矩阵。公式(8)可展开如下：

d'2(ymrm,msm)2(ym1rm1,msmrm1,m1sm1)2...(9)式(9)中右边第一项只与sm有关，第二项只有sm，sm1有关。后面各项以此类推。因此Hs在超球体里面的一个必要条件是： d'2(ymrm,msm)2，将该条件写成区间的形式为：

d'ymd'ymsm(10)rm,mrm,m式(10)中符号分别表示向上和向下取整数，由(10)可以解得sm的值，但是我们知道式(10)还不是Hs在超球体内的充分条件，当选中满足条件的sm时，计算下一个值sm1，'2'22这时需要更新半径。令dmm1,msm，根据公1d(ymrm,msm)，并且ym1|mym1r式(9)可知：

''dmdm1ym1|m1ym1|msm1(11)

rm1,m1rm1,m1由此再确定一个sm1，继续计算下一个值sm2，直到s1。

以上分析了球形译码算法寻找内点的过程，下面给出SD算法的伪代码步骤：

*1)输入参数Q=[Q1Q2],R，x，yQ1x，d。'22*2)设置km，dmdQ2x，ym|m1ym。

''3)计算sk的界限，设置上界UB(sk)(dkyk|k1)/rk,k，sk(dym)/rk,k1。

24)sksk1.判断如果skUB(sk)，那么跳至步骤6，否则跳至步骤5。5)kk1，如果km1，终止计算，否则，跳至步骤4。6)如果k1，跳至7；否则kk1，yk|k1yk2dk'2dk'21(yk1|k2rk1,k1sk1)跳转至步骤3。

jk1rmk,jsj，'2'22Hsysdd(yrs)7)找到结果，将数组，以及与接收信号的差距m111,11保存并跳转至步骤4.算法sd.m文件见matlab程序

算法性能比较: ZFSD>MMSE-SIC、ZF-SIC>MMSE>ZF

第二篇：LTE常见故障总结

LTE-FZHA（RL25）常见故障总结

目录

LTE-FZHA（RL25）常见故障总结............................................................................................1

1.System module failure(0010)........................................................................................3 2.BTS reference clock missing(1898)................................................................................3 3.Configuration error: Unit initialization failure(0012).....................................................3 4.Configuration error: Not enough HW for LCR(1868).....................................................4 5.Configuration error: Power level not supported(4008).................................................4 6.Cell configuration data distribution failed(6253)..........................................................4 7.Failure in optical RP3 interface(4064)...........................................................................5 8.Failure in optical RP3 interface(0010)...........................................................................5 9.Baseband bus failure(3020,1906).................................................................................5 10.RF module failure(6259，1911、1711、1712)..........................................................5 11.Cell power failure(4090)..............................................................................................6 12.GPS Receiver alarm: Control Interface not available（4011）..................................6 13.X2 interface setup failure（6304）.............................................................................6 14.Transport layer connection failure in X2 interface.......................................................6 15.Failure in replaceable baseband unit...........................................................................7 16.Temperature alarm(0002)............................................................................................7

17.VSWR（1838）............................................................................................................7 18.Failure in optical RP3 interface(2004).........................................................................8 19.GPS时钟盒闪断，时钟信号不正常，无法识别RRU...............................................8 20.Failure in optical RP3 interface（2000）.....................................................................8 21.光纤交叉连接..............................................................................................................8 22.基站始终无法建立S1连接，只到configed状态....................................................9 23.GPS时钟盒闪断，时钟信号不正常，无法识别RRU...............................................9 24.某一个小区的RRU无法识别.....................................................................................9 25.BBU版本无法识别....................................................................................................10 26.校准初步排查............................................................................................................10 27.本地IP地址和路由正常，ping不通MME和网关................................................11 28.TRS文件始终无法生效.............................................................................................11 29.三种疑难告警............................................................................................................12 30.远程ping不通基站...................................................................................................12 31.风扇告警....................................................................................................................12 32.BTSlog有link消息，但是pinger始终不亮............................................................12 33.驻波问题....................................................................................................................13 34.pinger正常，但是SM里小区显示橙黄色告警.....................................................13 35.几个特列....................................................................................................................13 36.FOSI 和FOSN的光功率范围....................................................................................13 37.不同频段RRU类型...................................................................................................13 1 38.MAC绑定及载波冲突...............................................................................................14 39.传输不通....................................................................................................................14 40.升级完成后出现驻波告警........................................................................................14 1.System module failure(0010)引起原因：

由于天气温度过高或者机房温度过高，导致BBU的热量散发不出去，引起的告警，一般表现是第三小区挂死，严重的可能会整站挂死，甚至会烧坏BBU。抑或是光模块出现问题导致出现此告警。处理方法：

1、由于是高温引起，基站要降温并重启BBU.若是BBU长期处于高温状态，会导致BBU内部的芯片烧坏，到最后只能替换BBU

2、若是因为光模块导致，则可以更换光模块，则可以解决此问题。

2.BTS reference clock missing(1898)引起原因：一般导致此故障有两个原因：

1、高温导致比较常见，由于高温时间过长，光模块过热，导致BBU和RRU失去连接，而后会出现此告警。

2、时钟盒出现故障。

3、时钟线与GPS头的连接线接头（避雷器接口）没有做好，接收不到时钟信号。

4、时钟线和时钟盒的连接不好。处理方法：

1、高温引起，基站要降温，等待一段时间后并重启BBU.2、时钟盒故障，更换时钟盒；

3、GPS线头没有接好，重新做一下从GPS引下来的馈线到避雷器的头子，使其能够正常接触。

4、若是时钟线损坏，则更换时钟线；若是时钟线和时钟盒接头没有接好，则接好接头。

3.Configuration error: Unit initialization failure(0012)引起原因：

1、高温导致小区挂死，软重启后会出现此告警

2、高温导致基站自动重启出现此告警 处理发法：

1、高温引起，基站要降温并重启BBU。

2、重新COMISSION基站，即重新把基站的集成文件（SCFC）和传输文件（Config）重新传入BBU内，重启后一般可以恢复正常。4.Configuration error: Not enough HW for LCR(1868)引起原因：以3小区基站配置来说明，由于集成文件已经配置好了，若是某一小区丢失或两个、三个小区的RRU都识别不到，则会出现此告警。

1、高温导致光模块过热，跟光纤的连接中断

2、光纤没有插好

3、光纤断了

4、RRU坏了

5、SCFC文件配置有问题 处理方法：

1、高温引起，基站要降温并重启BBU。

2、将光纤拔下来，重新插好

3、更换损坏的光纤

4、更换RRU

5、重新配置SCFC文件，如果是二小区的基站，不能将SCFC文件做成三小区的配置，否则也会出此告警。

5.Configuration error: Power level not supported(4008)引起原因：

1、BBU上的FSMF到FBBA之间的电源连接线没有插好，导致供电不足

2、BBU自身的问题 处理方法：

1、重新拔插这些电源线，使之接触正常

2、说是BBU自身的问题，则是有些可以不用拔插，直接重启基站就可以解决此问题。

6.Cell configuration data distribution failed(6253)引起原因：

基站运行一段时间由于自身问题导致，在此也说不清楚为什么会出现此问题，最大的可能性就是BBU加载好的文件一般存储在它的FLASH芯片里面，运行一段时间后文件出错，未能成功读取到SCFC文件，导致基站出现此告警

处理方法：

由于重启基站后此问题即可消失，所以一般处理的方式为重启基站，在重启的过程中，基站会重新读取索引目录Filedirectory，重新加载基站的配置文件，此过程会擦除原先在Flasn里面的数据，这样基站就能正常工作了。7.Failure in optical RP3 interface(4064)引起原因：

1、光模块损坏导致辅口读不到光纤消息

2、温度过高，导致辅口光模块故障，读取不到光纤消息

3、辅口的光纤断了 处理方法：

1、更换辅口的光模块，问题得到解决

2、下电直接重启，或是下电后将光模块拔出，冷却一阵再插入卡槽内，加好光纤，加电起来后此告警消失

3、光纤损坏导致此问题，需要更换光纤，此问题最为麻烦，需要工程队配合，一般更换光纤后都能好（前提是把1、2都做过一遍了，告警得不到解决的情况下，更换光纤）。

8.Failure in optical RP3 interface(0010)引起原因：

1、高温导致小区两光纤传输中断，BBU读不到RRU消息

2、高温导致小区两光模块出现问题

处理方法：

此问题处理的方法一般为下点重启，问题都可以得到解决，但是如果机房或者综合柜的温度还是很高的话，过不了多久，大概10分钟左右，此告警还会出现，所以需要做的是打开综合柜的门，进行散热处理，或是增加空调设备，降低室内温度，如果基站在室外，则没有什么好的办法，只能将BBU拿出来，放在综合柜外面。

9.Baseband bus failure(3020,1906)引起原因：

1、BUS线没有插好

2、BBU内部主板的问题 处理方法：

1、重新拔插BUS线，使之连接正常

2、BBU内部主板的问题有的可以通过下电重启解决此问题，但是有的只能更换BBU，此问题才能得到解决。

10.RF module failure(6259，1911、1711、1712)引起原因：

1、光模块损坏导致

2、RRU出现故障导致

处理方法：

1、若是告警号为1711（主）或1712（辅），则分别更换主辅侧的光模块即可解决问题。

2、告警号为1911或者是6259的时候，则需要更换RRU，一般都可以解决此类故障。

11.Cell power failure(4090)引起原因：

1、高温导致供给FBBA的电流减少，导致功率不足

2、Vendor文件不匹配 处理方法：

1、高温引起，基站要降温并重启BBU

2、更换跟天线匹配的正确的Vendor文件

12.GPS Receiver alarm: Control Interface not available（4011）

引起原因：

GPS时钟盒工作不正常

处理方法：

1、重启时钟盒

2、拔插连接BBU和时钟盒的时钟线

13.X2 interface setup failure（6304）

引起原因：

X2链路连接建立失败，需要建立X2链路连接

处理方法：

1、如果邻基站存在，则邻基站好了以后，此告警自然消失

2、如果邻基站不存在，则需要在邻区关系表里面讲此链路的连接配置删除，既可以消除此告警。

14.Transport layer connection failure in X2 interface 引起原因：

邻小区没有Onair,即基站未能正常起来工作 处理方法：

1、删除邻区关系

2、是邻小区正常工作

15.Failure in replaceable baseband unit 引起原因：

1、FSMF和FBBA之间连接不好导致

2、FBBA硬件问题 处理方法：

1、重启BBU

2、检查FSMF和FBBA之间的连线

3、更换FBBA板件

16.Temperature alarm(0002)引起原因：

1、机房或者综合柜温度过高

2、BBU风扇转速过快或者过慢

处理方法：

1、检查机房空调是否正常工作，温度是否正常。

2、检查综合柜是否散热良好

3、检查BBU的风扇转速是否正常，一般可以看到此类告警，若是不正常，则需要更换风扇。

17.VSWR（1838）

引起原因：

1、RRU内部的耦合器脱落，倒是发射端口出现驻波

2、天线跟BBU内的Vendor文件不匹配，出现驻波

3、馈线头子没有做好，进水了，出现驻波

4、馈线有问题，出现驻波

5、光模块也会导致驻波（很少见，我没见过，但是听说过）处理方法：

1、对于RRU损坏导致的驻波，则更换RRU，只能如此解决

2、若是天线和Vendor文件不匹配导致的告警，则更换相对应的Vendor文件

3、进水了则需要晾干或者更换馈线

4、馈线有问题则直接更换

5、光模块有问题，可以通过更换光模块来解决。

18.Failure in optical RP3 interface(2004)引起原因：

1、软件问题

2、硬件问题

处理方法：

1、更换软件版本，此告警有的基站可以消失

2、更换硬件，此告警可以消失

对于此告警，实在是难以有一个定论，曾经研发的人为此告警一天打了5个补丁还是解决不了，到现在也不知道怎么办，只有不停的更换软件包，更换硬件，更换光模块来消除此告警。

19.GPS时钟盒闪断，时钟信号不正常，无法识别RRU 正常情况下，小的时钟盒信号灯为常绿，如果出现绿色指示灯不断闪烁则GPS信号不正常。

如果灯闪的情况为一长二短，则为GPS馈线短路，如果灯闪的情况为一长一短，则为GPS馈线开路。

20.Failure in optical RP3 interface（2000）

引起原因：此告警基本是因为温度过高，但是光模块还能工作，但又受到影响，出现的告警，或者是光模块故障导致

解决办法：

1、更换光模块

2、下电重启，若是基站处于正常温度下，则可以保持正常，不再出此告警。

21.光纤交叉连接

对于室外型宏基站（FZHA，s111），开通后正常的FZHA的框号为1.1.1、1.3.1、1.4.1(normal FZHA rack no.png)。已发现有部分基站开通后的FZHA的框号为1.1.1、1.2.1、1.3.1(abnormal FZHA rack no.png)。

对于这种情况，基站无告警，但对于第一、二小区的业务测试会造成影响。原因可能是第一小区的辅光纤与第二小区的主光纤交叉错接。1、3、4代表主光口

22.基站始终无法建立S1连接，只到configed状态

这种情况一般是基站发了S1连接请求，但是核心网侧没有回，在SM里面会有6308的告警（S1 interface setup failure），这个时候我们会误认为是核心网侧没有配这个站的数据或没配对，其实核心网侧不需要配置任何数据。所有的information都由ENB上报。下面是MME的输出：

MCC MNCENB ID ENB IP S1 CONN AMOUNT === === ===== ======================================= 460 08 13 172.16.2.16 3 460 08 106 172.16.2.137 0 460 08 108 172.16.2.139 16 S1口通了之后，ENB正常接入网络，MME侧就能看见有关的信息。所以，基站侧开通时，不外乎2个问题：

1.传输不通：需要核对传输侧数据是否配对。比如：ENB IP地址，网关，S1-C控制地址，VLAN ID等。

2.传输通了，S1口不通：需要核对ENB侧 MCC,MNC,ENBID是否正确。特别是ENBID，不能与其它站冲突。截止到现在，99%的ENB S1口不通，是由于ENBID冲突造成的。SCTP的端口号36412如果都是诺西的设备，就不会出问题。

总之，在ENB接入EPC的过程中，MME只是起着等待接入，接入确认的作用。

23.GPS时钟盒闪断，时钟信号不正常，无法识别RRU 正常情况下，时钟盒信号灯为常绿，如果出现绿色指示灯不断闪烁则GPS信号不正常。如果灯闪的情况为一长二短，则为GPS馈线短路；如果灯闪的情况为一长一短，则为GPS馈线开路。这两种情况一般只需重做GPS头子就行。

还有一种情况是灯闪的时间间隔相同，则为时钟盒模式选择错误，只需把时钟盒上的模式开关拨到GNSS就行。

24.某一个小区的RRU无法识别

现象是：该小区的RRU能ping通，但是在BTSlog里面无法读出RRU的版本，SiteManger里面也无法识别RRU。

既然小区光纤同步没问题，而BTSlog和SM却又同时识别不到RRU的版本，按照RL15时的经验只可能是RRU的productCode丢失，所以从RRU里面，通过log –a提取RRU的log（F01_startup.zip和F01_runtime.zip），从该RRU的启动log里面，可以看到如图1-1显示的信息：

图1-1 该小区RRU启动log 而正常RRU启动log里面，应为如图1-2所示的信息：

图1-2 正常RRU启动log 对比可以看出，原因应该是productCode和Serial number丢失造成。在RRU里面，使用eeprom命令，手动写入productCode和Serial number，重启基站后，小区恢复正常。

25.BBU版本无法识别

BBU版本无法识别主要表现在SM读到的版本为“?”，这个问题也是在1800之后出现的，主要是因为往BBU里传文件时出错引起系统切换，重启后就识别不到版本了。

对此尝试过很多手段，包括重升PS、重传fs1、重灌基站包和重刷flash都不行。既然这个问题是系统切换时造成的那能不能再让它切换一次？于是问研发要了一条关于切换的命令，具体步骤如下：

1)通过将FileDirectory里面的“?”写回版本号，再放回flash里面 2)保证备区的FileDirectory里版本号不是“?” 3)在FCTB里执行命令：uboot_env get，查看正在运行的区域，如果是fs1，则执行命令: uboot_env set active_partition=2，将系统切换至fs2 4)重启BBU，重启后一般情况下能恢复正常版本，不行的话可以再次尝试以上方法。

26.校准初步排查

如果发现某个小区的校准有问题，比如说2小区的校准有问题，那么我们更换小区110 和小区2的光纤位置（也就是OptIF1和OptIF3更换，OptIF2和OptIF6更换），看看校准不好的小区是否有变化：

（1）如果校准不好的小区变到了第1小区，那么可能是RRU或者射频连线的问题（2）如果校准不好的小区还是第2小区，那么可能就是eNB的问题 对于(1)类问题，我们要继续看看是哪个path有问题，如下面的log：

AntIdx(7)值偏大，则须检查对应第8通道的跳线是否接好。如果所有path都不好的话，则可以尝试sitemanager block、unblock这个小区，看是否恢复正常，如果没有校准打印，则直接重启。以下是各个参数的定义：

Timeoff 波动不要太大，能稳定就可以

Ampratio 是原始天线信号计算出的天线x对参考天线的幅度比 Finalampratio 是最后ULPHY给出的调整幅度比，不会>1 Maxtxantampratio 是7组幅度比中最大值，代表了RRU 8个通道之间幅度的差异

27.本地IP地址和路由正常，ping不通MME和网关

先检查光电转换器上面是否有5个绿灯。如果电口灯未亮，检查eNB到光电转换器的网线；

如果光口灯未亮，检查光电转换器到PTN的光纤是否连接正确； 如果1000M灯未亮，检查网线的质量；

如果指示灯都正常的话，则致电PTN工程师核对PTN的端口和传输数据，尤其是VLAN和容量。

28.TRS文件始终无法生效

当传完fs1文件或升完级后，TRS文件在SM里始终无法sending出去，将其上传至runfs1trs_datadb根目录下重启基站也不生效；

此时可以尝试重刷PS来解决，生效后BBU上的传输指示灯会变绿！29.三种疑难告警

（1）Cell power failure 原因：RF received low power from BTS 解决方法：1.Check Pmax and txPowerScaling value 2.Check vendor file 3.Replace FSMF or FBBA（2）RF module failure 原因：LNA burned 解决方法：Replace RRU HW或BBU HW或FBBA（3）Baseband bus failure 原因：基带总线配置被硬件，软件，DSP或LTX拒绝 解决方法：更换BBU到两块FBBA的数据线或直接更换BBU 30.远程ping不通基站

远程ping不通有以下几种可能：（1）网管IP没配或配错

（2）该站之前正常，但是后来上站发现vlan数据又被做到PTN2-5口，导致远程ping不通；

（3）光电转换器到BBU的网线有问题，诺西采购的这批网线还不如地摊上卖的靠谱，运行一段时间后，竟然会导致传输中断

（4）PTN上的光模块突然之间出问题了

（5）基站正常运行一段时间后TRS文件丢失（6）PTN被托管了

（7）机房断电、BBU或光电转换器被下电

以上可能大多数都需去现场结合实际情况来判断，并采取相应的解决方法！

31.风扇告警

风扇告警可能是风扇过速、低速或不转，一半是风扇本身的问题，可以通过更换风扇来解决，一半是由于BBU出了问题，而不转也可能是因为风扇电源未插好。

另外有些风扇告警时有时无，需结合实际情况来判断。

32.BTSlog有link消息，但是pinger始终不亮

这个问题在18630版本下很常见，据说是因为该版本对光口质量要求高，因为我试过将版本降到16200时问题就消失了，升上来后又复现了，解决方法如下：

（1）整站下电（2）更换光模块

（3）单独上电问题小区

（4）将问题小区一根光纤拔掉 33.驻波问题

驻波问题很常见，主要有以下几种：

（1）跳线未插或未插好

（2）RRU耦合器脱落，导致驻波固定在RRU某一通道（3）天线问题

（4）Vendor文件没有和天线型号对应

SM里面显示的某通道驻波比告警是指RRU上对应的某通道，不是天线的，而校准+1则和RRU对应！

34.pinger正常，但是SM里小区显示橙黄色告警

岳峰镇台中这个站之前很正常，运行一段时间后二小区无法识别，远程重启基站后该小区报4064告警。

上站下电重启基站后该小区光纤同步正常，但是SM里小区显示橙黄色告警，更换BBU侧光模块后问题依旧，最后更换RRU侧光模块问题解决。

35.几个特列

（1）金榜食府->温度告警->整站挂掉 :温度过高会导致光口异常，小区退服；

（2）传输数据做好后，PTN网管确认vlan、ip也添加了，但是就是ping不通网关：后来才知道对应的网关没添加；

（3）有个小区始终不报link消息：后来发现是RRU侧光纤未插；

（4）琅岐便携->将BBU下电6-8分钟后，pinger能正常识别，但是SM识别不到该小区->重启几次后SM能识别，但是报RP3-2000:更换光模块后问题解决。

36.FOSI 和FOSN的光功率范围

（1）RTXM228-601 输出光功率:-8.2dBm~+0.5dBm（FOSN）输入光功率：-14.4dBm~+0.5dBm（2）RTXM228-618 输出光功率:-5.2dBm~+0.5dBm（FOSI）输入光功率：-14.4dBm~+0.5dBm 37.不同频段RRU类型

室分只有一种频段：

E频段，2.3G(6通道FZNC 和2通道FZND)宏站有两种频段：

F频段，1.9G(8通道FZFA和8通道FZFD)13 D频段，2.6G(8通道FZHA)38.MAC绑定及载波冲突

更换BBU后传输需在网管做一个MAC地址的绑定

铁路旅社：TD第三小区11个载波，所以LTE的第三小区只能到configing状态，到不了configed的状态，也ONair不了！

39.传输不通

1，网管IP没配或配错，按规划重新做数据； 2，该站之前正常，但是后来上站发现vlan数据又被做到PTN2-5口，导致远程ping不通，将PTN尾纤插到正确位置；

3，光电转换器到BBU的网线有问题，直接更换； 4，PTN上的光模块出问题，直接更换；

5，基站正常运行一段时间后TRS文件丢失，重做数据； 6，PTN被托管，联系PTN侧处理；

7，机房断电、BBU或光电转换器被下电、空开跳闸，上电或联系移动处理；

40.升级完成后出现驻波告警

此故障出现在最新升级的版本247_16，升级完成后，由于Vendor文件未能同步更新名称，导致出现驻波，这时候就需要通过Fileziler登陆到BBU里面，将Vendor文件的后面几位改成升级以后版本的名称，比如说升级前，Vendor名称为vendor_GZ818630，这时候就需要该为vendor_GZ824716。

第三篇：LTE填空题总结

3.UE通过E-UTRAN广播消息获取AS和NAS系统消息。

4、随机接入实现的基本功能：申请上行资源、与eNodeB间的上行时间同步。

5、RLC实体传输数据有三种模式：透明模式（TM）、无确认模式（UM）、确认模式（AM）。

6、LTE测量分为3类：同频测量(Intra frequency measurement，不需要改变收发频率）、异频测量(Inter frequency measurement，需要改变收发频率）、异技术测量(Inter-RAT measurement，需要改变收发频率）

1、室内覆盖指标要求_90_%的区域达到_-105__dBm以上。

2、室内单点测试中好点下行测试要求TM3达到_50__Mbps，TM1达到__35__Mbps。

3、室内信号泄漏到室外指标要求为__建筑物外10m要求满足室外室内信号

比>10dB,或者室内信号<-110dBm __。

4、室内小区基本参数核查包括__PCI、频点、BW、子帧配置、天线间距、CELL ID、eNB ID、TAC等____。

5、子帧配置1的上下行时隙配置为__DSUUD___。

1.CMCC测试规范规定，计算赋型增益时需要用到的数据有CRS RSRP和DRS RSRP

2.中移动TD-LTE试验局要求默认采用上下行配置 1，特殊子帧配置 7

3.目前TD-LTE所用的频段为 Band 38 和Band 40。

1.无线网络规划结束后应输出文档

2.OFDMA从频域对载波资源划分成多个正交的载波，小区内间无干扰，同频组网时，不同小区使用相同时频资源，存在小区间干扰。

3.影响小区吞吐量主要因素有，发射功率，其它

4.链路预算包括上下链路的发射机的各项和损耗，接收机的各项增益和损耗，以及各项增益和最大路径损耗

5.PDSCH信道的TM3模式在信道质量好的时候为，信道质量差的时

候回落到单流波束赋型。

6.LTE组网中，如果采用室外D频段组网，一般使用的时隙配比为，特

殊时隙配比为10:2:2；如果采用室外F频段组网，一般使用的时隙配比为3:1:1，特殊时隙配比为3:9:2。

第四篇：算法总结

算法分析与设计总结报告

71110415 钱玉明

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。

下面我将谈谈我对这门课程的心得与体会。

一、数学是算法的基础

经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。

①主定理

本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。

②随机算法中的许多定理的运用

在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。

这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。

二、算法的核心是思想

我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。

①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。

动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。

贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。

周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。

回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。

分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。

②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。

这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。

三、算法与应用紧密相关

我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。

这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。

四、对计算模型和NP问题的理解

由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。

首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。

NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。

最后谈谈对这门课程的建议

①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。

②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。

③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。

第五篇：算法总结

算法分块总结

为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。

图论模型的应用

分层图思想的应用：

用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。

这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用：

最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用：

容量有上下界的最大流的应用：

欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树：

求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树：

抽象成数学模型就是：

设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k

首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。

假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。

状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树；

2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。

加边和去边过程，利用动态规划优化特别值得注意。

次小生成树：

加边和去边很值得注意。

每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法：

首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。

最短路径的应用：

Dijkstra 算法应用： Folyed 算法应用：

Bellman-Ford 算法的应用：

差分约束系统的应用：

搜索算法

搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用：

IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索：

部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索：

可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。

动态规划

动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。

状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP：

状态划分比较困难的题目： 树形DP：

四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2)

高档数据结构的应用

并查集的应用：

巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用：

总结用线段树解题的方法

根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等

树的每个节点根据题目所需，设置变量记录要求的值

用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。

在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。

Trie的应用：；

Trie图的应用探索： 后缀数组的应用研究：

在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。

树状数组的应用探索：；

计算几何

掌握基本算法的实现。凸包的应用：；

半平面交算法的应用：；

几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：；

转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：；

经典算法：找平面上的最近点对。

贪心

矩形切割

二分思想应用

活用经典算法

利用归并排序算法思想求数列的逆序对数：

利用快速排序算法思想，查询N个数中的第K小数：

博弈问题

博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。

第一类：推结论。典型题目： 第二类：递推。典型题目：

比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质：

1． 所有的结束位置都是P位置。

2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。

这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。

与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为：

1． 将所有的结束位置标为P位置。

2． 将所有能一步到达P位置的点标为N位置。

3． 找出所有只能到达N位置的点，将它们标为P位置。

4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。

关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为

g(x)min{n0,ng(y)对于所有yF(x)}

1． 对于所有的结束位置x，g(x)= 0。

2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。

3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。

定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn)

第四类：极大极小法。

典型题目：ZOJ 1155：Triangle War

ZOJ 1993：A Number Game

矩阵妙用

矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目：

数学模型举例

向量思想的应用：

UVA 10089：注意降维和向量的规范化 ；

利用复数思想进行向量旋转。

UVA 10253：

递推

数代集合

数代集合的思想：

ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。

组合数学

Polya定理则是解决同构染色计数问题的有力工具。

补集转化思想

ZOJ 单色三角形：

字符串相关

扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀；

填充问题

高精度运算

三维空间问题专题

无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。

其它问题的心得

解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广