一种基于信噪比的HARQ自适应合并算法

目前无线通信中广泛使用的HARQ合并技术主要是Chase合并和递增冗余（IR）合并。针对Chase合并在低信噪比下性能受限,递增冗余（IR）合并实际应用复杂的问题,提出了一种基于信噪比的自适应合并算法,通过实时估计信道的信噪比,综合使用Chase合并和递增冗余（IR）合并,实现了系统性能和实现复杂度的统一。仿真结果表明,算法是切实可行的。     

一种MIMO-OTFS低复杂度信号检测算法

由于高速多径环境下频率色散现象严重破坏正交频分复用（OFDM）系统子载波正交性,为解决高速多径环境下的频率色散问题,正交时频空调制技术技术（OTFS）应运而生;而多输入多输出技术（MIMO）具有可以有效提升信道容量和系统可靠性的特点,文章采用了MIMO技术与OTFS技术结合的方法,推导了MIMO-OTFS系统中最大比合并信号检测算法（MRC）理论并加以仿真;针对MIMO-OTFS系统中MRC信号检测算法复杂度过高的情况,提出了一种低复杂度信号检测算法;该算法的基本思想是利用最大比合并方法对时延—多普勒网格中传输符号的接收多径分量进行提取和相干合并,以提高合并信号的信噪比,同时利用Cholesky矩阵分解理论,对信道增益矩阵进行求逆运算的优化,降低了算法复杂度,为MIMO-OTFS系统的实际应用做出贡献;     

空间调制系统下改进的QRD-M检测算法

空间调制（SM）系统中性能最优的最大似然（ML）检测算法复杂度很高,用基于信道矩阵QR分解的M算法（QRD-M）可以降低复杂度,但传统QRD-M算法检测时,每层都保留固定的M个节点,仍会造成额外的计算量。针对传统QRD-M算法中存在的问题,提出一种低复杂度的动态M值QRD-M检测算法——LC-QRD-dM。LC-QRD-dM算法利用设计的阈值与累积分支度量值进行比较,每层自适应地选择不超过M的保留节点数,相对于传统QRD-M算法以牺牲少量性能为代价大大降低了复杂度。接着又针对该改进算法在信道衰落较深时会产生较大误码率的问题,进一步提出一种基于信道状态的动态M值QRD-M检测算法——CS-QRD-dM。CS-QRD-dM利用LC-QRD-dM的原理,在低信噪比（SNR）时,每层根据阈值选择不小于M的保留节点数;在高信噪比时,每层则选择不超过M的保留节点数。理论分析和仿真结果表明：相比传统QRD-M,CS-QRD-dM在低信噪比时有约1.3 dB的信噪比增益（误码率为10^-2）,以增加少量复杂度为代价,显著地改善了检测性能;在高信噪比时,其检测性能及复杂度与LC-QRD-dM相同。     

平衡分组选择网络

自从1968年Batcher的排序网络发表后,已经有很多文章对它作了进一步的研究。然而有关从n个数中选出m个最小的所谓选择网络却很少有研究。本文提出了一种基于双调(bitonic)序列和分组原理的并行选择算法,并给出了相应的使用Batcher的基本比较元件实现的具体选择网络。所提出的选择网络分别具有O(n·log~2m)和O(logn·logm)~2的硬件和时间的复杂度。与Alekseyev的选择网络相比,平均加速是O(logm)。并且首次表明了:使用Batcher的基本比较元件所构成的选择网络,其硬件和时间复杂度将小于相应的Batcher的排序网络的复杂度。     

MIMO-GFDM系统中低复杂度动态禁忌搜索检测算法的改进

针对多输入多输出的广义频分复用（MIMO-GFDM）系统的等效信道矩阵维度极大，传统的MIMO检测算法复杂度高且性能不佳的问题，将大规模MIMO系统中的动态禁忌搜索（RTS）检测算法运用到MIMO-GFDM系统中，并解决了RTS算法初始值的求解复杂度高的问题。首先利用最小均方误差（MMSE）检测算法所用到矩阵的正定对称性将矩阵Cholesky分解，并结合Sherman-Morrison公式迭代计算初始值，降低了初始值求逆的高复杂度；然后以改进的MMSE检测结果作为RTS算法的初始值，从初始值逐步全局搜索最优解；最后通过仿真，对不同算法的迭代次数和误码率（BER）性能进行了研究。理论分析与仿真结果表明：在MIMO-GFDM中，所提改进RTS信号检测算法误码率远低于传统信号检测算法。在4QAM时，RTS算法大约有低于MMSE检测6 dB的信噪比性能增益（误码率在10^-3时）；在16QAM时，RTS算法大约有低于MMSE检测4 dB的信噪比性能增益（误码率在10^-2时）。与传统RTS算法性相比，所提改进算法在不影响误码率性能的同时降低了算法复杂度。     

任意类型的分类数据的快速排序

快速排序在数据部分相等或有序时,时间复杂度最坏为O（n2）。针对于任意类型的分类数据的排序,文章在快速排序的基础上,提出一种新的排序算法,具有快速排序算法的简洁性,但是不使用递归算法,时间复杂度为O（n）,空间复杂度为O（1）。通过理论分析和实验表明,该算法的性能明显优于其它排序算法,特别适合于数据量大的场合。     

一种改进的中文字符串排序方法

对中文字符串排序,最快算法的时间复杂度是O（nlgn）。基数排序算法是目前最快的排序方法之一,时间复杂度是O（dn）,但其一般适用于相同长度的整型数据排序。提出了一种快速的变换方法,将字符串转换为与之等长的整型数组,使用基数排序算法对代表字串的整型数组排序,用以实现对字符串的快速排序。实验表明,提出的算法能快速地进行中文字符串排序,比快速排序算法具有更好的性能,且排序时间与数据规模之间是线性关系,算法的时间复杂度为O（dn）。     

多入多出系统中改进的QRD-M检测算法

在研究传统QRD-M检测算法的基础上,提出一种用于多入多出系统的改进的QRD-M检测算法。该算法通过累积分支度量排序和终止门限设置,合理减少搜索树的分支数。仿真结果表明,当信噪比为10 dB、调制方式为16QAM、天线配置为4×4时,改进算法在无检测性能损失的情况下可使传统QRD-M检测算法的复杂度降低30%。     

一种新的二次分"档"链接排序算法

提出了一种谓之二次分“档”链接的新排序方法（以下简称为二次分“档”链接排序）,并给出了该排序算法的描述、时间复杂度分析、空间复杂度分析及用Ｃ语言编写程序进行算法比较的实验结果,算法分析和实验结果都表明：在待排序数据满足Ｏ（△Ｍ）≤Ｏ（Ｎ）（这里,Ｎ为待排序数据个数,△Ｍ为关键字的变化范围）的情况下,二次分“档”链接排序方法与待排序数据分布无关且时间复杂度仅为Ｏ（Ｎ）,而附加在存储空间开销仅为Ｎ＋√     

一种低复杂度MIMO球形检测算法

针对球形译码检测算法在信噪比较低时复杂度大的问题,提出一种新型球形检测算法。通过使用一个压缩因子对低信噪比时的球半径进行抑制,同时结合最小均方误差检测算法降低算法复杂度。仿真结果表明,在信噪比低于10 dB时,该算法相对传统球形译码算法,复杂度平均降低10%左右,并且性能损失较少。     

程序设计中常用的排序算法

针对程序设计中常出现的排序问题，介绍了六种常用的排序算法：插入排序、希尔排序、堆排序、归并排序、冒泡排序、快速排序，以及每种排序所需的时间复杂度，当对大量的数据排序时，以选择适应的算法，提高程序的执行速度。     

程序设计中常用的排序算法

针对程序设计中常出现的排序问题,介绍了六种常用的排序算法:插入排序、希尔排序、堆排序、归并排序、冒泡排序、快速排序,以及每种排序所需的时间复杂度,当对大量的数据排序时,以选择适应的算法,提高程序的执行速度。     

深度优先稳定原地归并排序的高效算法

基于分治策略,使用深度优先的方法,提出了一种用于线性表的稳定原地归并排序算法,其时间复杂度为O(n lb n),辅助空间复杂度为O(1),递归栈空间复杂度为O(lb n),同时进行了算法分析和实验测试。实验结果表明,该算法效率较STL中的稳定原地归并排序算法有67.51%的提升,解决了稳定排序算法中要么时间复杂度高要么空间复杂度高的问题。     

多符号差分检测的低复杂度球形译码设计

在多符号差分检测系统中,深度优先的球形译码是一种典型的次优的检测算法。然而从复杂度角度来说,它仍有较高的计算复杂度,且存在流水线和并行操作困难等缺点。针对这些问题,目前主要从两个方面对该算法进行改进：一是通过选择合适的约束半径来降低复杂度;二是与K-Best（M）算法结合来解决并行操作问题。主要研究前者,并在现有的理论基础上,提出了两种半径选择方法,即线性半径和非线性半径。仿真结果表明,两种半径约束下的球形译码在复杂度上低于最大似然检测却同时能保证它们的性能损失小于0.5 dB。     

基于FPGA的KLT特征点多层次归并排序

KLT算法已在多个领域得到成功的应用,其中特征点的排序是用来选择好的特征点跟踪的关键。针对传统排序算法计算耗时、实时性差的缺点,提出一种可并行的多层次归并排序算法并在FPGA中实现了其并行计算,同时分析了其周期精确的计算时间。结果表明该归并排序算法可以[O(N)]的时间复杂度完成特征点的排序,能够满足高清分辨率的图像/视频数据中KLT特征点排序的实时性要求。     

基于C语言的冒泡排序算法探讨

冒泡排序算法是一种简单实用的排序方法,但传统的冒泡排序算法比较次数多,时间复杂度大。经过对传统的冒泡排序算法进行深入分析,从减少比较次数的角度出发,提出改进算法,并利用C语言予以实现,提高算法的效率。     

基于C语言的冒泡排序算法探讨

冒泡排序算法是一种简单实用的排序方法．但传统的冒泡排序算法比较次数多．时间复杂度大。经过对传统的冒泡排序算法进行深入分析．从减少比较次数的角度出发．提出改进算法,并利用C语言予以实现,提高算法的效率。     

Generalized algorithm for parallel sorting on product networks

We generalize the well-known odd-even merge sorting algorithm, originally due to Batcher (1968), and show how this generalized algorithm can be applied to sorting on product networks. If G is an arbitrary factor graph with N nodes, its r-dimensional product contains N^r nodes. Our algorithm sorts N^r keys stored in the r-dimensional product of G in O(r^rF(N)) time, where F(N) depends on G. We show that, for any factor graph G, F(N) is, at most, O(N), establishing an upper bound of O(r² N) for the time complexity of sorting N^r keys on any product network. For product networks with bounded r(e.g. for grids), this leads to the asymptotic complexity of O(N) to sort N^r keys, which is optimal for several instances of product networks. There are factor graphs for which F(N)=O(log² N), which leads to the asymptotic running time of O(log² N) to sort N^r keys. For networks with bounded N (e.g. in the hypercube N=2, fixed), the asymptotic complexity becomes O(r²). We show how to apply the algorithm to several cases of well-known product networks, as well as others introduced recently. We compare the performance of our algorithm to well-known algorithms developed specifically for these networks, as well as others. The result of these comparisons led us to conjecture that the proposed algorithm is probably the best deterministic algorithm that can be found in terms of the low asymptotic complexity with a small constant     

基于特定范围的关键字的快速排序算法

本文给出了一种对关键字在特定范围内的数据记录不用进行数据的比较交换的快速排序算法、算法思想、算法描述、时间复杂度及空间复杂度分析,并用C＋＋语言编写程序进行算法比较。结果表明：在关键字范围远远小于记录数的情况下,此算法的时间复杂度仅为O（n）,并且明显优于其他排序算法。     

基于DCT域和纹理复杂度的图像水印算法

水印的鲁棒性受背景、纹理、边缘等条件影响较大。为此,提出基于离散余弦变换(DCT)域和纹理复杂度的图像水印算法。对水印信息进行预处理,计算每个图像块的方差并将其按大小排序,对各子块进行离散余弦变换,计算变换后每个图像块的方差并将其按大小排序,根据中频系数将经过方差值排序的水印图像块嵌入载体图像中。测试结果表明,该算法比原始基于DCT的水印算法具有更好的鲁棒性和图像可见性。