基于非重叠前缀集合的并行路由查找系统

快速的路由查找机制是高性能路由器设计的关键.最长匹配查找是路由查找的难点所在.本文提出一个并行路由查找系统.它使用一种路由表划分方法,可将路由表中的前缀划分为若干个集合,集合内前缀没有重叠.从而把路由表前缀的最长匹配查找转化为若干个集合内前缀的唯一匹配查找.基于这种方法,本文还提出一个通用的并行路由查找框架,框架适用于大多数路由查找算法.并行查找框架可简化查找算法的设计,提高查找算法的速度.使用二分查找算法,并行查找系统可以达到log₂(2N/B)的查找复杂度 (N为路由表前缀数目,B为大于4的整数).同时,并行查找系统对IPv6也具有很好的扩展性.     

一种基于有限域求逆的S-Box实现算法

S-Box是AES密码算法硬件实现的关键，目前主要有两种实现方法：一种是基于查找表，一种是基于有限域求逆。文章首先经过数学变换将有限域GF（2^8）上的元素映射到有限域GF（2^4）^2上，并把GF（2^4）^2上的一个元素变换为GF（2^4）上的两个元素的线性运算。在此基础上，把GF（2^8）上的求逆问题转化为GF（2^4）上的求逆，从而提出了一种基于有限域求逆的低硬件开销的S-Box实现算法。该算法和查找表实现相比，面积减少了57％，适用于诸如智能卡、移动设备等对面积要求比较严格的场合。     

基于前缀区间集合的IPv6路由查找算法

对IPv6相关的通用型与特定型路由算法进行了分析,重点研究了以BSR为基础的IPv6路由算法在查找和更新时的不平衡问题,提出了基于前缀区间集合的IPv6路由算法。通过对路由前缀（N）进行范围（K）、集合（M）划分以及更新节点自修复提高查询速度、降低不平衡性的影响,具有O(log2N/K)和O(log2N/K+2M)的查询与更新时间复杂度,空间复杂度为O(K+2N)。实验表明,该算法具有良好的查询性能,降低了更新不平衡性的影响。     

基于父节点的XML查询优化算法

本文提出了基于父节点的XML查询优化算法,它主要利用关键词的顺序循环查找父节点,把查找出来的父节点集合求交集,所得的父节点交集集合中的元素即为最小子树根节点,最后根据所得出的最小子树根节点得到用户所需的最紧致片段。通过选取经典的INEX数据集算法进行测试。实验结果表明,与传统的XML查询优化算法相比,基于父节点的XML查询优化算法有较高的准确率,更能满足用户需求。     

联合多维布鲁姆过滤器查询算法

分析了现有多维布鲁姆过滤器查询算法(MDBF)工作原理,提出了一种改进的两步表示和查询的联合多维布鲁姆过滤器(CMDBF)查询算法.CMDBF新增一个用于表示元素整体的联合布鲁姆过滤器CBF,CMDBF中元素表示和查找分两步进行.将MDBF的各属性的表示和查询作为第一步,第二步联合元素所有属性域,利用CBF完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,CMDBF能够支持多维集合元素的简洁表示和查询,相比MDBF查询误判率降低明显.     

快速路由查找算法的研究

首先给出了现有的路由查找算法以及这些算法的优缺点,在此基础上提出了基于二分查找Trie的路由查找算法.另外,文章给出了算法在IPv6T 实现方案.该算法具有查找、更新速度快的特点,由于算法简单,容易实现,因此具有较高的实用价值.     

P2P层网格资源查询及消息路由算法

首先将网格资源进行分层管理的方式,提出了网格分层体系构架.针对资源查询的处理,提出了3个相关算法IE(information exchange)算法、ID(information discovery)算法和IR(information routing)算法,通过实验在查找失败率、查找速度以及信息复杂度上与传统算法进行了对比,结果表明其性能有了一定的提高.     

IPv6快速路由查找算法分析与研究

分析了IPv6路由结构的特点,介绍了IPv6中的各种路由查找技术,提出了基于聚集位向量的快速路由查找算法,并对该算法和常用二分查找算法的性能进行了分析比较,实验结果表明该算法较好地提高了查找速度,减少了对内存的消耗.     

H.264中CAVLC解码算法的改进

对H.264中CAVLC解码算法进行了研究,提出了一种改进的CAVLC变长表格查找算法.先根据码字前缀中0的个数将变长的二维表格分解成两个表,再分别转换为哈夫曼树,大大提高了查找速度.     

高速IP路由查找中改善更新性能的方法

现有的高速IP路由查找算法更多地强调路由表的查找,却忽视了路由表的更新。而路由表的更新对整个路由查找算法的性能和实际应用有不可忽视的影响。分段式查找树(Multibittrie)查找算法作为常用的IP路由查找算法,具有算法简单、有效等特点,但是更新速率较慢。作者提出一种在分段式查找树中控制路由表更新时间的方法,此方法能够较大地改善分段式查找树的更新性能。文章对更新性能的改善作了论述。     

VLSI版图设计中的一种优化总体布线方法

本文针对国际上已有的多种BBL总体布线方法进行了研究,提出了一种更有效的基于多子图定向合并生成的布线算法,并在国家重点工程“熊猫系统中实现.实验结果比较表明:我们的总体布线优化技术优于已有的BBL总体布线工具.     

A coherent acquisition method for a PN sequence using binary searchand an auxiliary sequence

Direct sequence spread spectrum systems require a local replica of the pseudonoise (PN) sequence to be synchronized with the received signal's spreading code. A method is proposed to improve the PN sequence acquisition time and decrease the acquisition time variability. The proposed method is based on a binary search algorithm. At each stage of the algorithm, an auxiliary signal is used to formulate a new search region within the PN sequence, and at each stage the search region is reduced by half. The region containing the incoming PN phase is therefore obtained within O(log₂ (N+1)) steps. A closed loop coherent PN acquisition algorithm presented by Salih and Tantaratana (1996) motivated the use of the auxiliary signal, and the algorithm of Salih et al. is also used for comparison. Results indicate the algorithm presented in this paper can achieve a factor of two to three times improvement in the mean acquisition time with a significant decrease in the acquisition time variability     

A translation-invariant wavelet representation algorithm withapplications

We address the time-varying problem of wavelet transforms, and a new translation-invariant wavelet representation algorithm is proposed. Using the algorithm introduced by Beylkin (see SIAM J. Numer. Anal., vol. 29, p.1716-1740, 1992), we compute the wavelet transform for all the circular time shifts of a length-N signal in O(N log N) operations. The wavelet coefficients of the time shift with minimal cost are selected as the best representation of the signal using a binary tree search algorithm with an appropriate cost function. We apply the translation-invariant representation algorithm to a geoacoustic data compression application. The results show that the new algorithm can reduce the distortion (the squared error in our case) substantially, if the input signals are transients that are sensitive to time shifts     

任意两序列公共元素的并行查找

对于处理器数为log_2n的共享存储多处理器系统,本文探讨了查找长度为n的任意两序列公共元素的并行算法。     

Speed improvement of B-snake algorithm using dynamic programming optimization

This paper presents a novel approach to contour approximation carried out by means of the B-snake algorithm and the dynamic programming (DP) optimization technique. Using the proposed strategy for contour point search procedure, computing complexity is reduced to O(N×M(2)), whereas the standard DP method has an O(N×M(4)) complexity, with N being the number of contour sample points and M being the number of candidates in the search space. The storage requirement was also decreased from N×M(3) to N×M memory elements. Some experiments on noise corrupted synthetic image, magnetic resonance, and computer tomography medical images have shown that the proposed approach results are equivalent to those obtained by the standard DP algorithm.     

改进型自适应多叉树防碰撞算法研究

 文章在自适应多叉树防碰撞算法的基础上,通过优化阅读器所发送前缀的方法,提出了一种改进型自适应多叉树(IAMS)防碰撞算法.该算法通过计算碰撞因子来动态地选择搜索树的叉数,并对四叉树的查询前缀进行优化,从而避免了大量的空闲时隙.文章通过数学分析,准确地描述了IAMS算法识别标签所需的时隙数.仿真结果表明,改进型自适应多叉树防碰撞算法具有更快的识别速度和更高的系统吞吐率.     

基于二进制树分解的动态防碰撞算法

针对现有的无线射频识别系统（RFID）二进制树防碰撞算法所需的搜索时隙较多,系统识别速率较低,提出了一种基于二进制树分解的动态防碰撞算法。该算法利用标签EPC的唯一性,对发生碰撞的比特位进行深度分解,根据碰撞位调整搜索状态,从而进一步减少搜索时隙数并提高了系统的呑吐量。通过对算法的分析和仿真结果表明：基于二进制树分解的动态防碰撞算法相对于动态二进制搜索算法有明显的优势。     

A Content-Based Search Algorithm for Motion Estimation

1　ＩｎｔｒｏｄｕｃｔｉｏｎＨ .2 63ｓｔａｎｄａｒｄ[1 ] ｉｓａｂｌｏｃｋ ｂａｓｅｄｖｉｄｅｏｃｏｄｉｎｇｓｃｈｅｍｅａｎｄｄｅｓｉｇｎｅｄｆｏｒｌｏｗｂｉｔ ｒａｔｅａｐｐｌｉｃａｔｉｏｎｓ.ＭＥｉｓａｋｅｙｃｏｍｐｏｎｅｎｔｉｎｔｈｅＨ .2 63ｅｎｃｏｄｅ     

基于行为规律的搜索资源分配新算法

针对具有行为规律的目标搜索问题,提出一种搜索资源分配算法。该方法以目标在各搜索区域的概率分布为基础,利用最优搜索理论分配区域搜索时长;以目标在各搜索区域的行为规律为基础,利用包络检测等方法决定区域开始搜索的时刻。针对网站关键词搜索的实验显示,根据目标行为规律在时间上相关程度的不同,本算法相对于最优搜索算法的性能提升在15%~50%之间,在对大量信息源进行信息搜索时具有应用价值。     

Fast codeword search algorithm for real-time codebook generation inadaptive VQ

Adaptive vector quantisation is used in image sequence coding where the code-book is updated continuously to keep track with the changing source statistics. Hence, for real-time video coding applications, both the processes of quantising the input vectors and updating the codebook are required to be fast. Since the nearest codeword search is involved in both these processes, a fast codeword search algorithm can make the coding process time efficient. The authors describe a proposed codeword search algorithm with reduced search space. The algorithm uses the mean value and the sum of the absolute differences as the two criteria to reject unlikely codewords, thereby saving a great deal of computational time, while introducing no more distortion than the conventional full search algorithm. Simulation results obtained confirm the effectiveness of the proposed algorithm in terms of computational complexity