Prufer编解码的最优算法

讨论标号树的Prufer编码的编解码算法.文献中常见的Prufer编解码算法需要O(n log n)时间.文献[1,2,4,9]提出了Prufer编解码的线性时间算法.这些算法都用到了整数排序算法,利用待排序整数的取值特殊性,得到线性时间整数排序算法.由此将Prufer编解码问题的计算归结为整数排序问题.本文从更直接的角度考察Prufer编解码问题,从简单算法出发,挖掘问题的本质特征,逐步简化,得到Prufer编码的一个非常简单实用的线性时间最优编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴.     

人工智能中求解八数码问题算法的实现与分析

针对八数码问题的求解,给出了深度优先搜索、广度优先搜索和启发式搜索(譬如A*算法)之间的算法比较,通过实验验证各种算法并得出结论:在通常情况下,采用启发式搜索算法来进行状态空间的搜索更为方便、高效。     

四种最短路径算法实例分析

通过理论分析,结合实际应用,在GIS节点数很大的数字地形图中,从完备性、最优性、时间复杂度、空间复杂度几种性能问题实例分析,较系统地总结出深度优先搜索(DFS)、广度优先搜索(BFS)、双向广度优先搜索(DBFS)、A★算法四种算法代价及优缺点.     

哈林网络中Steiner树问题的线性时间算法

设计一个在哈林网络中求解Steiner树的线性时间算法,提出伪扇的概念并在伪扇扩充至扇的过程中对Steiner树在扇中可能出现的状态进行枚举,递归压缩哈林图中的扇,通过还原所有扇得到Steiner树。算法的正确性证明、复杂度分析及应用实例分析证明,该算法对于哈林网络的多播选路具有重要的参考价值。     

N皇后问题的启发式算法探讨

搜索策略的选择与设计是人工智能领域问题求解的核心问题之一,直接影响到问题求解过程中存储空间的占用和计算的复杂性,影响到问题求解的效率。在给出N皇后问题形式化描述和现有搜索算法的基础上,设计了3种解决N皇后问题的启发式算法,并将其与深度优先和宽度优先等搜索策略进行了分析和比较,得出了几点关于设计启发式算法的启示。     

基于宽度优先搜索的路径生成算法

宽度优先搜索和深度优先搜索是图论中常用的两种搜索算法.两者各有优势,但深度优先搜索算法的效率在低连通度图中会大大降低,这时更适合采用宽度优先搜索算法.本文提出了一种基于宽度优先搜索的路径生成算法,具有较好的时间复杂性和空间复杂性.     

迷宫最短路径问题新算法

提出了求解迷宫最短路径问题的新算法,该算法抛弃了经典算法(深度优先搜索和广度优先搜索)中繁杂低效的递归、回溯思想。通过合理的变换,将原问题转化为迷宫路径深度图的生成问题。最后对算法进行了严谨的分析和实例测试,显示出该算法易于理解、易于编程、时间空间复杂度低等优点。     

一种线性时间排序算法的实现

提出一种不依赖关键字的分布,数据位数不受限制的整型或实型数的内部排序算法,其时间和空间复杂度均为O(n).给出了算法思想和算法分析结果.     

求强分图图的算法

由于如文献［１］［２］等的实际需要，对基于ＤＦＳ技术的求强分图算法进行扩充、改进，使之更完整。而算法的时间复杂性仍保持不变。     

公交网络线路查询算法的设计与实现

在大中城市中,城市交通网络错综复杂,游客或市民从城市的一个地方到另一个地方,往往要换车才能到达目的地。如何选择换车线路、站点,才是最少的换车次数、最经济的乘车方案?本文针对这个问题,提出了实现最少换车次数的算法,解决了换车情况下的查询算法的难点。     

一种LDPC码的两步混合译码算法

本文介绍了一种LDPC码的两步混合译码算法，并在AWGN信道下进行了仿真。仿真结果表明，与传统的BP算法相比，在中高信噪比区域，混合译码算法可以提供更低的误码平台。     

一种新颖的LDPC编码系统码率识别方法

LDPC码编码识别是信道编码识别中的难点。随着LDPC码在通信领域的广泛应用,LDPC码编码识别技术也引起越来越多的关注。针对在低信噪比条件下,现有算法对LDPC码编码参数识别率低的问题,首先利用信道输出的软信息,将编码校验关系映射到对数似然比域,并定义编码校验对数似然比（Check log-likelihood ratio,CLLR）。然后,分析CLLR模值的统计特性,建立CLLR与待识别LDPC码参数之间的联系。最后,充分利用在不同校验矩阵下CLLR统计特性的区别,设计一种综合CLLR均值和方差特征的最大均方比判决器。从仿真结果看,在给定先验编码集合的闭集应用模式下,本文算法明显优于已有算法,识别增益在低信噪比环境下可达2~5 dB。而且对于高码率LDPC码的识别,本算法可以显著提高识别性能。     

RM码的一种并行最大似然译码算法

根据Chase译码算法和分阶统计译码（OSD）算法在纠错能力上的互补性,提出一种新的针对RM码的OSD-Chase并行译码算法,其中,OSD算法对接收序列的高可信相互独立符号集合（MRIPs）进行处理,并产生候选码字,若MRIPs中有超过i个错误,则order-i的OSD算法译码失败。Chase算法对接收序列的低可信度符号集合（LRPs）进行处理,若有过多的错误出现在LRPs中,超过代数译码的纠错能力,则Chase译码失败,同时设计一种并行最大似然译码算法。仿真实验结果表明,该算法能够获得较高的译码性能。     

LT码的BPML译码算法

采用置信度传播算法(BP)对LT码进行译码时,停止集是影响译码效率的重要因素。对LT码停止集的大小进行了理论分析和仿真,提出了置信度传播-最大似然联合译码算法(BPML)。该算法首先采用BP算法译码,当遇到停止集时再采用最大似然译码算法(ML)对停止集进行处理,能够有效消除停止集的影响,提高LT码的译码效率。仿真结果表明,BPML算法结合了BP算法复杂度低和ML算法译码效率高的优点。研究结果对提高计算机网络中数据分发应用的分发效率具有重要的实用价值。     

FFFIS编解码算法与实现

在对FFFIS(Form Fit Function Interface Specification)的Eurobalise报文特点进行简单介绍的基础上,对其编解码算法进行了探讨,并根据FFFIS标准提出了高速算法以及系统软硬件实现方案,最后对其应用进行了简单介绍。     

规则低密度校验码的比特翻转解码算法研究

本文提出一种规则低密度校验码的比特翻转迭代解码算法。在解码算法的每一次迭代运算过程中,解码运算可以从总体上分为两个阶段：首先,满足可靠性要求的校验节点从与其相邻接的信息节点中选择一个信息比特作为翻转候选比特;然后,解码算法采用投票的方法对于这些候选翻转比特进行进一步的筛选。本算法由于对于最终翻转比特的选择结果是通过两次筛选而得到的,从而极大地降低了误翻的概率,加快了迭代解码算法的收敛速度,提高了系统的性能。另外,在第一阶段的比特选择过程中,我们综合校验节点所提供的校验检测信息和信道输出所提供的可靠性信息,提出了新的翻转比特选择标准。仿真结果表明,本文所提出的解码算法有着较好的性能,在解码运算复杂度和纠错性能之间提供了另外一个均衡。     

空时分组码的简化译码方法

实际无线通信应用中,译码方法的简化一定程度上降低了移动端的功率消耗。文章根据星座图的几何结构,从数学角度出发,描述了一种8进制相移键控(8PSK)下空时分组码的简化最大似然(ML)译码方法,并将该方法推广到幅度相移键控(APSK)映射情况下的译码。对最大似然译码方法和文中简化最大似然方法的仿真结果及译码计算复杂度进行了分析和比较,结果表明简化最大似然译码算法只是降低了计算复杂度,并没有影响误码率。     

基于分段模型的信源容错译码算法

针对无损信源编码存在误码扩散的问题,建立了以最大后验概率估计为基础的信源序列分段译码模型,设计了基于统计模型的容错译码算法。该算法充分利用了信源编码数据的残留冗余,较好地消除了无损压缩数据对误码的敏感性,为文本压缩数据的容错译码提供了新思路。实验结果表明,该算法具有纠正信源数据中误码的能力,能够显著减少信息损失。     

网络加解密算法AES分析

随着计算机网络的发展,社会对网络安全的要求也越来越紧迫.文章介绍了我国在网络安全的所遇到的挑战,重点分析了业界Ⅰ较新的先进加密标准AES算法RIJNDAEL.首先描述了AES算法的背景和框架,并对其进行了详细分析,包括加密解密流程,并给出了部分伪C代码实现.