基于非对齐双字节读机制的单模式串匹配算法

在线精确单模式匹配问题在几乎所有涉及文本和符号处理的领域中均有广泛应用。SBNDMq是目前该领域性能最高的算法之一。通过向其引入非对齐双字节读机制,对SBNDMq算法进行改进,从而提出SBNDMqShortb系列算法。该系列算法拥有与SBNDMq算法一致的跳跃能力,但核心循环的内存访问次数降低为原来的50％,算法性能更高。实验结果表明,在大多匹配条件下,SBNDMqShortb系列算法性能优于其他已知算法。     

Unified Parallel Systolic Multiplier Over GF（2^m）

In general, there are three popular basis representations, standard （canonical, polynomial） basis, normal basis, and dual basis, for representing elements in GF（2^m）. Various basis representations have their distinct advantages and have their different associated multiplication architectures. In this paper, we will present a unified systolic multiplication architecture, by employing Hankel matrix-vector multiplication, for various basis representations. For various element representation in GF（2^m）, we will show that various basis multiplications can be performed by Hankel matrix-vector multiplications. A comparison with existing and similar structures has shown that time complexities. the proposed architectures perform well both in space and     

Bit-Parallel Witnesses and Their Applications to Approximate String Matching

We present a new bit-parallel technique for approximate string matching. We build on two previous techniques. The first one, BPM (Myers, 1999), searches for a pattern of length m in a text of length n permitting k differences in $O(\lceil m/w \rceil n)$ time, where w is the width of the computer word. The second one, ABNDM (Navarro and Raffinot, 2000), extends a sublinear-time exact algorithm to approximate searching. ABNDM relies on another algorithm, BPA (Wu and Manber, 1992), which makes use of an $O(k \lceil m/w \rceil n)$ time algorithm for its internal workings. BPA is slow but flexible enough to support all operations required by ABNDM. We improve previous ABNDM analyses, showing that it is average-optimal in number of inspected characters, although the overall complexity is higher because of the $O(k \lceil m/w \rceil )$ work done per inspected character. We then show that the faster BPM can be adapted to support all the operations required by ABNDM. This involves extending it to compute edit distance, to search for any pattern suffix, and to detect in advance the impossibility of a later match. The solution to those challenges is based on the concept of a witness, which permits sampling some dynamic programming matrix values to bound, deduce or compute others fast. The resulting algorithm is average-optimal for m ≤ w, assuming the alphabet size is constant. In practice, it performs better than the original ABNDM and is the fastest algorithm for several combinations of m, k and alphabet sizes that are useful, for example, in natural language searching and computational biology. To show that the concept of witnesses can be used in further scenarios, we also improve a recent variant of BPM. The use of witnesses greatly improves the running time of this algorithm too.     

New Bit-Parallel Systolic Architectures for Computing Multiplication,Multiplicative Inversion and Division in GF(2<Superscript>m</Superscript>) Under Polynomial Basis and Normal Basis Representations

A new bit-parallel systolic multiplier over GF(2^m) under the polynomial basis and normal basis is proposed. This new circuit is constructed by m ² identical cells, each of which consists of one two-input AND gate, one three-input XOR gate and five 1-bit latches. Especially, the proposed architecture is without the basis conversion as compared to the well-known multipliers with the redundant representation. With this proposed multiplier, a parallel-in parallel-out systolic array has also been developed for computing inversion and division over GF(2^m). The proposed architectures are well suited to VLSI systems due to their regular interconnection pattern and modular structure.

改进的中文近似字符串匹配算法

BPM-BM算法在针对汉字等大字符集的近似字符串匹配时取得了很好的实际效果,但该算法在最差情况下的总体时间复杂度为O(!+nm)。而提出的IBPM-BM算法由于具有记忆的能力,保证了过滤阶段的无回溯,可以在理论上保证最差情况下的总体时间复杂度为O(!+n),而在最佳情况下的时间复杂度与BPM-BM算法一致。     

基于FPGA的比特并行DWDM光动态包交换系统

设计了一种全新的光路由器。采用单独的100Mb／s的低速控制通道用来交换承载于波带（比特并行机制）带宽速率为80Gb／s的包,这种基于现场可编程门阵列（FPGA）实现的机制使得宽带交换可以应用在具备低时延、低成本特点的本地网（LAN）中,商用化的FPGA用于驱动带宽的Mach-Zehnder干涉仪（MZI）和半导体光放大器（s0A）交换机。详细描述了为控制通道和数据通道设计的2种不同的时钟数据恢复模块（CDR）系统及其相关测试分析。对控制通道所有8个通道进行测试表明,在需要路由选址的情况下,测试结果稳定,且没有误码,和噪音层面出现。对于1552．6nm数据通道进行的背靠背和需要路由选址情况下,通过对MZI光交叉和SOA光交叉测量,得到额外的因为路由操作而导致的2．3dB功率代价。     

一种面向间隙核函数的快速算法

间隙核是一种应用非常广泛的字符串核,在文本分类和蛋白质分类中都取得了很好的效果.本文提出了一种应用在入侵检测领域的间隙核,称为长度加权核.并且提出了一种基于后缀核的动态规划算法,能够有效计算变长度加权核.另外,本文提出了一种位并行算法,能够加速定长度加权核的计算.实验表明在满足位并行的条件下这种快速算法比现有的几种计算间隙核的算法更为快速,而且应用在入侵检测中能够取得较好的效果.     

Modelling for the current-voltage characteristics of SOI submicrometre gate controlled hybrid transistors

An improved physical model for the collector current in the SOI submicrometre gate-controlled hybrid transistor (GCHT) is presented in this paper, with the bias-dependent dynamic threshold voltage of the GCHT redefined and evaluated, considering the impact of carrier injection on the inversion degree of the surface in the base. Many physical effects are taken into account in this model, including channel length modulation effect, mobility degradation effect, as well as high injection effect, source/drain series resistance and body-contact resistance effect, which may result in additional gate-body bias. The model is verified by comparison between calculated results, PISCES simulated results and experimental data.     

Efficient Reconfigurable Implementation of Canonical and Normal Basis Multipliers Over Galois Fields GF(2m) Generated by AOPs

Galois fields GF(2^m) are used in modern communication systems such as computer networks, satellite links, or compact disks, and they play an important role in a wide number of technical applications. They use arithmetic operations in the Galois field, where the multiplication is the most important and one of the most complex operations. Efficient multiplier architectures are therefore specially important. In this paper, a new method for multiplication in the canonical and normal basis over GF(2^m) generated by an AOP (all-one-polynomial), which we have named the transpositional method, is presented. This new approach is based on the grouping and sharing of subexpressions. The theoretical space and time complexities of the bit-parallel canonical and normal basis multipliers constructed using our approach are equal to the smallest ones found in the literature for similar methods, but the practical implementation over reconfigurable hardware using our method reduces the area requirements of the multipliers. José Luis Ima?a is Assistant Professor of Computer Architecture in the Department of Computer Architecture, Complutense University of Madrid (Spain). He received the Ph.D. degree in Physics from the Complutense University in 2003. His current research interests are computer architectures, VLSI technologies, logic design and verification, finite field arithmetic and cryptography. Juan M. Sánchez-Pérez is Professor of Computer Architecture in the Department of Computer Science, University of Extremadura, Spain. He received a PhD degree in Physics from the University Complutense of Madrid in 1976. His research interests are modern computer architectures, VLSI technologies and logic design.