基于网格的资源查找算法分析

文章对网格环境下已有的资源查找算法，通过建模分别在时间复杂度、空间复杂度上进行对比分析，指出了这些算法各自存在的优势和不足。     

基于三元组表表示的稀疏矩阵的快速转置算法及其改进

介绍基于三元组表表示的稀疏矩阵的快速转置算法,此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置,在此使用2个数组作为辅助空间,为了减少算法所需的辅助空间,通过引入2个简单变量提出一种改进算法。该改进算法在时间复杂度保持不变的情况下,空间复杂度比原算法节省一半。     

改进的双向选择排序算法

详细分析了双向选择排序算法的设计思路,给出了两种设计方案的C语言描述,指出了部分参考文献中关于该算法描述存在的疏漏.经过对比分析各算法的时间复杂度和空间复杂度,总结出两种算法设计方案的优劣,为简单选择排序算法的优化提供了一定的理论依据.     

快速排序算法研究

排序是计算机科学中最重要的研究问题之一，2000年被列为20世纪对科学和工程计算的研究与实践影响最大的10大问题之一。文章介绍了基本的快速排序算法及三种枢轴元素的选取方法，全面深入地分析了快速排序算法最坏情况下的时间复杂度，平均情况下的时间复杂度，随机情况下的时间复杂度，并对快速排序算法和堆排序算法进行了比较，理论和实验结果表明，快速排序算法仍然是目前最好的排序算法之一。     

一种基于DFT的低复杂度虚子载波OFDM信道估计算法

该文针对采用虚子载波的OFDM通信系统,提出了一种基于DFT的低复杂度信道估计算法,并与最小二乘(Least Square,LS)估计算法和线性最小均方误差(Linear Minimum Mean Square Error,LMMSE)算法进行了详细的性能和复杂度比较。所提DFT算法较好地降低了高斯白噪声的影响,相对于LS算法获得了较大的性能增益。该算法在复杂度与性能之间取得了较好的折衷,具有很好的实用价值。     

一种基于非完备决策表的核特征计算方法

本文基于相容关系构造了非完备决策表的可辨别矩阵，并设计了非完备决策表的核特征快速计算方法．由于算法仅利用核特征在可辨别矩阵中的性质，而并不存储矩阵元素，使算法的空间复杂度得到显著降低，算法的时间复杂度和空间复杂度分别为O（｜C｜｜u｜2）和O（｜u｜）．     

OFDM系统基于二维核回归算法的衰落信道估计

提出了一种低复杂度的基于二维核回归平滑的时间频率双衰落信道估计算法.该方法首先采用LS算法估计导频处的信道增益并利用分段线性插值方法得到数据子载波处的信道增益,然后分别利用两个级联的一维核回归平滑器在时域和频域对信道矩阵进行二维平滑,以消除由信道噪声、ICI和插值误差等引入的估计误差.对插值和平滑分别进行优化处理,因此具有计算复杂度低、性能优良等优点.数值仿真表明:该算法性能较LS算法和1维DFT算法有较大的改进;与1维LMMSE算法相比性能相差很小,在低信噪比时甚至超过了后者.     

H.264/AVC算术编码的优化实现

在H．264视频压缩标准中采用了高效的算术编码CABAC方案，CABAC提高了编码效率，但同时增加了编码复杂度。分析CABAC的复杂度，指出CABAC优化方向，提出其低复杂度实现算法。主要从上下文模型、重要图和宏块类型的CABAC编码3个方面对CABAC软件算法进行了优化，并在JM参考软件中进行了验证，实验结果表明CABAC的编码复杂度降低了40％。     

一种DOA估计的快速子空间算法

MUSIC算法是一种属于特征结构的子空间超分辨方法，该算法性能优良，但需要估计协方差矩阵并对其进行特征分解，运算量大，很费计算时间。本文对波这方向估计问题进行了研究并提出了一种采取降维处理的快速子空间算法，该算法利用阵列协方差矩阵的一个子矩阵快速得到信号子空问，无需特征分解，且无需估计整个协方差矩阵，只需估计该子矩阵，故快速算法运算复杂度远低于MUSlC算法，而性能损失并不太大。理论分析和计算机仿真结果表明此方法是有效的。     

随机排序的优化算法

随机排序经常出现在数字信号处理的分析和仿真中,尤其用于交织器的比较分析和优化设计中,它的算法优劣直接影响到计算仿真的效率.针对原有算法,本文提出了优化算法,大大改善它的时间和空间复杂度.定量的理论分析和实际的仿真测试都表明,优化算法能够有效提高计算效率和节省存储空间.     

伪叠加Zadoff-Chu序列的LTE下行信道估计

分析了正交频分复用系统中基于叠加训练序列的最小二乘和线性最小均方误差信道估计算法,在此基础上针对LTE信道的结构特征,提出了一种利用伪叠加Zadoff-Chu序列进行信道估计的最小二乘算法。该方法可以大大降低算法复杂度,并且不需要信道先验信息、不占用带宽资源。仿真结果验证了该方法的有效性,其性能比频域的离散傅里叶变换算法和线性最小均方误差算法性能更优。     

Reduced‐rank space–time adaptive interference suppression for navigation systems based on QR decomposition and approximations of basis functions

This paper presents a novel reduced‐rank space–time adaptive processing (STAP) algorithm for interference suppression in global positioning system (GPS) receivers with low computational complexity for protection against the multipath and jamming interferences. The proposed STAP algorithm is based on the least‐squares (LS) criterion to jointly optimize a projection matrix, which is used for dimensionality reduction, and the reduced‐rank filter. The main novelties are the design of the projection matrix based on approximations of basis functions, the pattern matching between the projection matrix and the received data, and the derivation of a QR decomposition‐based reduced‐rank recursive LS algorithm for practical implementations. The proposed scheme works on an instantaneous basis, i.e. at each time instant, the most suitable pattern and the rank of the projection matrix are selected to reduce the dimensionality of the received data aiming at minimizing the squared error, while using an improved search algorithm to save the effort in finding the best projection matrix. Simulation results in a GPS system show that compared to existing reduced‐rank and full‐rank algorithms, the proposed algorithm has a much lower computational complexity, and remarkably better performance for interference suppression. Copyright © 2011 John Wiley & Sons, Ltd.     

OFDM系统中信道估计方法的研究

LS算法是OFDM系统信道估计方法中计算复杂度最低性能最差的方法.根据有限长度h的能量分布,提出了一种改进算法.通过仿真,与LS算法和性能较好的LMMSE比较,验证了改进后的LS算法性能优于最初的LS算法,并可在实际中得到较好的应用.     

一种改进的基于导频的OFDM信道估计算法

文中对OFDM（正交频分复用）系统中基于导频的信道估计技术进行了研究。MMSE（最小均方误差估计）算法有很好的性能但复杂度大,LS（最小二乘法估计）算法复杂度低但性能受到限制,在综合考虑性能和复杂度的情况下介绍了两种改进方法。并针对基于梳状导频的二项插值算法的缺陷,提出了一种改进的算法,计算机仿真证明了改进算法的误码率性能在高信噪比条件下高于原算法。     

Low-Complexity DOA Estimation Based on Constraint Solution Space

The Weighted Subspace Fitting (WSF) algorithm is one of the universal algorithms in Direction-Of-Arrival (DOA) estimation, which is of high accuracy. However, it involves the multi-dimensional nonlinear optimization problem, and the computational complexity is usually high. In this paper, we propose a low-complexity DOA estimation algorithm based on constraint solution space. Firstly, we use ESPRIT algorithm to limit the solution space around the best solution and reduce the computational range. Then, we find the best solution in a smaller solution space constraint by Cramr-Rao Bound (CRB), and seek repeatedly until reaching the global optimal solution of WSF algorithm by using the space of the best solution. By limiting the searching process in smaller solution space, this strategy controls the direction of convergence and reduces computational complexity. The experimental results show that this algorithm needs less iterations when the same DOA accuracy is required, and the computational complexity is apparently reduced.

     

区域分割包分类算法的优化实现

包分类就是根据到达数据包的包头信息将包按一定规则进行分类的过程，包分类技术是下一代路由器、防火墙、QoS保证机制实现、网络信息检测等设备的关键技术。区域分割包分类算法是目前多种分类算法中较为有效的算法之一。根据给定分类规则集的特点对算法进行优化实现是区域分割包分类算法的核心研究内容，它包括高效率的区域优化分割准则和在分割后小区域内的单域化线性查找两部分。优化实现不仅保证算法具有良好的时间和空间性能，而且极大地降低了规则数增加对算法性能的影响。仿真实验结果表明区域分割包分类算法在一定规则数范围内每秒能处理3-6M个IP包头，具有O(d）的时间复杂度(d为域的个数)和O(dN)的空间复杂度(N为规则数)。区域分割包分类算法支持规则集的实时更新。     

广义空间调制系统的正则化OMP检测算法

在广义空间调制（GSM）系统中,最大似然（ML）检测可以取得最优的检测性能,然而其计算复杂度随激活天线数的增加急剧增长。针对这一问题,提出了一种基于稀疏重构理论的低复杂度检测算法——正则化正交匹配追踪（ROMP）算法。该算法首先根据信道矩阵和当前残差的内积选取多个候选激活天线索引,接着对候选天线索引按正则化标准进行可靠性验证,剔除错误索引,缩小信号的搜索空间,最后通过求解最小二乘问题估计信号。仿真结果表明,与经典的正交匹配追踪（OMP）算法相比,所提算法以少许复杂度的增加为代价极大提升了检测性能,能够在检测性能与复杂度之间取得更好的折中。     

MC-CDMA系统中基于DFT的信道估计改进算法研究

LS信道估计算法运算量小,实现简单,但估计值对噪声影响敏感,算法精度低。为降低噪声对精度的影响,文章提出一种新的基于DFT的LS信道估计改进算法。该算法利用并行PN序列信号特性,通过时延点信息获取算法得到多径信道的时延点信息,并在改进的信道估计算法中利用此信息,最大程度地抑制噪声。仿真结果表明,与现有的基于DFT的LS改进算法相比,本算法可进一步提高估计精度,在低信噪比条件下性能更好。     

高斯马尔可夫随机场模型的递归最小二乘参数估计

本文首次提出应用阶递归最小二乘算法来估计高斯马尔可夫随机场模型参数。利用模型参数关于领域的对称性质,我们将一个非因果对称邻域支持的高斯马尔可夫随机场模型转化成一个因果非对称半平面部域支持的模型,从而使递归计算成为可能。利用规范方程中系数矩阵的近似Toeplitz性质,导出了运算量为O(m~3)+O(M~2m)MADP的阶递归最小二乘算法,而直接采用解方程法的计算量为O(m~3)+O(M~2m~2),这里M~2表示一幅图象的尺寸,m代表模型参数的个数。