一种快速有限域乘法器结构及其VLSI实现

提出了一种快速有限域乘法器结构.将多项式被乘数与乘数各自平分成两个子多项式,并使用数字乘法结构计算这些子多项式的乘积.通过改变数字乘法结构的数字大小D,来均衡乘法器性能和实现复杂度.为了简化模不可约多项式f(x)运算,采用特殊多项式AOP(all one polynomials)和三项式,产生有限域GF(2m).这种乘法器与LSD乘法器相比,在数字大小D相同时,可将运算速度提高1倍.这种乘法器结构适合高安全度密码算法的VLSI设计.     

冗余余数系统低复杂度快速纠错算法设计

余数系统由于具有增强传输信息在并行系统中鲁棒性的优势,已被广泛应用在无线局域网(WLAN)以及码分多址通信技术(CDMA)等领域。而余数系统中的纠错检错是保证传输数据可靠性和高效性的关键问题。该文根据有限环上剩余类的性质提出溢出判定定理,不重复判断定理和唯一性区间搜索定理,并在此基础上进一步提出采用模运算代替传统中国剩余定理进行快速恢复的单错误纠错算法,将复杂度降低为O(k,r);提出不重复判定纠错算法;并对于一般错误情形,设计通过比较算子实现的搜索纠错算法。其中搜索纠错算法能直接实现系统最大纠错能力,且避免依靠复杂模运算算子实现,系统吞吐率得以提高;与传统算法相比,计算复杂度由多项式级降低至对数级。     

支持同态算术运算的数据加密方案算法研究

针对在计算服务中,对用户信息加密以保护隐私时,无法对密文进行计算的问题,提出一种高效的支持密文四则算术运算的同态加密方案CESIL, 包括密钥生成、加密、解密及密文运算4个算法。该方案首先借助多项式环重新定义向量的加法和乘法运算,构建多项式系数向量环;然后利用理想格在向量环上划分剩余类,建立商环及其代表元集合;最后,将整数明文映射为代表元,并用代表元所在剩余类的其他元素替换该代表元,以对明文进行加密。商环的运算特性保证CESIL方案支持对密文的加法和乘法运算。在实现CESIL方案时,利用快速傅里叶变换(FFT)算法进一步提高运算效率、减少密钥长度。理论分析及实验结果表明,CESIL是语义安全的,且相比已有的一些同态加密方案,CESIL支持更多的运算类型,拥有较高的运行效率和较小的密钥及密文长度,能更好地满足实际应用需求。     

广义自缩序列的一种比较快速的密码学分析方法

对广义自缩序列生成器,利用猜测攻击的思想给出了一种比较快速的初态重构算法。得到了:(1)当线性反馈移位寄存器(LFSR)的特征多项式与线性组合器均已知时,算法的复杂度为O((L/2)32L-2)),lL/2;(2)当线性组合器未知时,算法的复杂度为O(L322L-1),lL;(3)当LFSR的特征多项式未知时,算法的复杂度为O((2L-1)L-122L-l),lL.其中L为LFSR的长度,为欧拉函数。     

基于Craig插值的线性混成系统符号化模型检测

最强后件的计算是模型检测算法的核心.本文使用一阶逻辑可满足性模线性算术理论给出线性混成自动机的有界模型检测表示公式,利用一阶逻辑公式不可满足情况下的插值存在性定理,对线性混成自动机的有界模型检测公式进行指定的划分,使用支持线性算术插值计算的可满足性模理论后端证明引擎的线性时间复杂度的消解反证技术获得这两部分公式间的插值公式,按一阶逻辑Craig插值的性质,所得到的插值公式就是模型检测过程中最强后件公式的上近似表示.有效地避免了使用逻辑编码方案实现线性混成自动机模型检测过程中需要双指数时间复杂度的量词消去操作求取最强后件公式,也不需像有界模型检测按步长展开变迁公式进行可满足性判定.最后本文在此最强后件计算的基础上,以有界模型检测技术作为反例确认方法,实现了一种无假反例的混成系统近似可达集计算算法.实验证明该算法与目前已经得到广泛工业应用的有界模型检测算法相比具有更优的性能.     

一种新的快速幂剩余算法

本文提出了一种新的快速幂剩余算法，这种算法利用平方剩余和乘同余的对称特性，减少了幂剩余算法的求模运算量，并缩短了乘法和求平方的计算时间．从而提高了整个幂剩余算法的速度．     

多维DFT的多维多项式变换与离散W变换算法

本文首先通过引进一种序列的重排技术将m(m2) 维离散Fourier变换 (m-D DFT)转化为一系列的一维广义离散Fourier变换(GDFT)的多重和.然后引入一维离散W变换(DWT)以及多维多项式变换(MD-PT)计算该多重和以减少冗余的算术运算,从而得到了高效的多维DFT算法,该算法与常用的行-列DFT算法相比,乘法仅约为行-列法的1/2m,而加法仅约为行-列法的(2m+1)/4m.对于2维DFT的计算,本文方法同单纯的多项式变换方法相比,乘法与加法分别减少50%与40%左右.另外,本文算法计算结构简单,易于编程实现,通过数值实验验证了本文算法的高效性.     

一个优化的低阶多项式累加和问题求解算法

本文针对低阶多项的多项式累加和问题∑n k=1 f(k),其中f(x)=c0+c1 x+…+cm-1 xm-1+cm xm,当多项式幂次m较小,累加项数n较大的情况下,根据二分求解思想,设计了一种高效的递推求解方法,其时间复杂度为O(m2 log n),而采用Horner格式计算多项式在每点的取值,再进行累加的朴素算法时间复杂度为O(mn),从而解决了在n>>m时,大大提高了低阶多项的多项式累加求和的效率.     

一种OFDM系统利用预编码进行峰均比降低的算法

为了降低OFDM系统峰均比,本文提出了一种低复杂度的预编码方案.该方案利用快速傅立叶变换取代原始方案中的乘法操作,极大地降低了计算复杂度.在此低复杂度方案的基础上,给出了一个基于通用平方根升余弦的预编码矩阵.理论分析和计算机仿真结果表明,与原始预编码算法相比,本文提出的方案具有更好的峰均比降低性能,同时计算复杂度有极大的降低.     

离散傅里叶变换的算术傅里叶变换算法

离散傅里叶变换(DFT)在数字信号处理等许多领域中起着重要作用.本文采用一种新的傅里叶分析技术—算术傅里叶变换(AFT)来计算DFT.这种算法的乘法计算量仅为O(N);算法的计算过程简单,公式一致,克服了任意长度DFT传统快速算法(FFT)程序复杂、子进程多等缺点;算法易于并行,尤其适合VLSI设计;对于含较大素因子,特别是素数长度的DFT,其速度比传统的FFT方法快;算法为任意长度DFT的快速计算开辟了新的思路和途径.     

Galois field arithmetic over GF(p/sup m/) for high-speed/low-power error-control applications

This paper presents a very large-scale integration implementation of Galois field arithmetic for high-speed error-control coding applications that is based on the field GF(p/sup m/) with m a small integer such as 2 or 3 and p a prime of sufficient value to generate the required field size. In this case, the Galois field arithmetic operations of addition, multiplication, and inversion are based on architectures using blocks that perform integer arithmetic modulo p. These integer arithmetic operations modulo p have previously been implemented with low delay power products through the use of one hot coding and barrel shifters circuits based on transistor arrays. In this paper, the same one hot coding and barrel shifters circuits are used to construct circuits that implement addition, multiplication, and inversion over GF(p/sup m/). The circuits for GF(p/sup m/) addition and multiplication with p/spl ne/2, achieve a lower power-delay product than designs based on GF(2/sup m/). Also, the architecture for GF(p/sup m/) inversion can be efficiently implemented when m=2 or m=3.     

有效的模(2n+1)乘算法及其VLSI设计

模乘运算在剩余数值系统、数字信号处理系统及其它领域都具有广泛的应用,模乘法器的硬件实现具有重要的作用。提出了一种改进的模(2~n 1)余数乘法器的算法及其硬件结构,其输入为通常的二进制表示,因此无需另外的输人数据转换电路而可直接用于数字信号处理应用。通过利用模(2~n 1)运算的周期性简化其乘积项并重组求和项,以及采用改进的进位存储加法器和超前进位加法器优化结构以减少路径延时和硬件复杂度。比较其它同类设计,新的结构具有较好的面积、延时性能。     

SIGMA: a VLSI systolic array implementation of a Galois field GF(2m) based multiplication and division algorithm

Finite or Galois fields are used in numerous applications like error correcting codes, digital signal processing and cryptography. The design of efficient methods for Galois field arithmetic such as multiplication and division is critical for these applications. A new algorithm based on a pattern matching technique for computing multiplication and division in GF(2^m) is presented. An efficient systolic architecture is described for implementing the algorithm which can produce a new result every clock cycle and the multiplication and division operations can be interleaved. The architecture has been implemented using 2-μm CMOS technology. The chip yields a computational rate of 33.3 million multiplications/divisions per second     

Two-dimensional polynomial residue number system

The polynomial residue number system (PRNS) has been considered as a useful tool for digital signal processing (DSP) since it can support parallel, carry-free, high speed arithmetic with minimum multiplication count provided that an appropriate modular ring is chosen. In this paper, the properties of two-dimensional (2-D) PRNS are investigated in detail. It is shown that in the 2-D PRNS system, the theoretical lower bound for multiplication count of polynomial products can be achieved in some carefully chosen ring. Application of the proposed 2-D PRNS for computing 2-D circular convolution, which involves intensive multiplication operations, is also presented.     

A Fast VLSI Multiplier for GF(2m)

Multiplication in the finite fieldGF(2^{m}) has particular computational advantages in data encryption systems. This paper presents a new algorithm for performing fast multiplication inGF(2^{m}), which isO(m)in computation time and implementation area. The bit-slice architecture of a serial-in-serial-out modulo multiplier is described and the circuit details given. The design is highly regular, modular, and well-suited for VLSI implementation. The resulting multiplier will have application in algorithms based on arithmetic in large finite fields of characteristic 2, and which require high throughput.     

LFSR multipliers over GF(2) defined by all-one polynomial

This paper presents two bit-serial modular multipliers based on the linear feedback shift register using an irreducible all one polynomial (AOP) over GF(2^m). First, a new multiplication algorithm and its architecture are proposed for the modular AB multiplication. Then a new algorithm and architecture for the modular AB² multiplication are derived based on the first multiplier. They have significantly smaller hardware complexity than the previous multipliers because of using the property of AOP. It simplifies the modular reduction compared with the case of using the generalized irreducible polynomial. Since the proposed multipliers have low hardware requirements and regular structures, they are suitable for VLSI implementation. The proposed multipliers can be used as the kernel architecture for the operations of exponentiation, inversion, and division.     

模为合数时多值模代数的模减与模除运算

本文提出并分析了模为合数时多值逻辑中模加与模乘运算的逆运算－模减与模除运算。它的引入使模减，模除运算的基数（模）的取值域从素数扩展到合数，从而完善了对模代数中的模减、模除运算的研究。     

3-D vector radix algorithm for the 3-D new Mersenne numbertransform

Three-dimensional convolutions and correlations are used for three-dimensional image-processing applications. Their calculation involves extensive computation, which makes the use of fast transforms very advantageous. As the number of arithmetic operations is very large, the accumulation of rounding or truncation errors arising in the use of the fast Fourier and Hartley transforms tends to increase. Number theoretic transforms are calculated modulo an integer and hence they are not subject to these errors. Previously, a one-dimensional transform called the new Mersenne number transform (NMNT) was introduced and applied successfully to the calculation of 1-D convolutions/correlations. Unlike other Mersenne number transforms, the NMNT can handle long data sequences and has fast algorithms. In the paper, the 1-D definitions are first extended to the 3-D case in detail for use in 3-D image processing applications. The concept and derivation of the 3-D vector radix algorithm is then introduced for the fast calculation of the 3-D NMNT. The proposed algorithm is found to offer substantial savings over the row-column approach in terms of arithmetic operations. Examples are given showing the validity of both transform and algorithm     

优化扩域上椭圆曲线标量乘的一个新算法

提出了一种优化扩域上椭圆曲线标量乘的新算法.算法基于Frobenius映射和二进制串的逻辑操作.文中对这个算法给出了细致精确的分析,而且在此基础上对新算法作了进一步改进.最后从理论分析和实际仿真两个方面就新算法和传统算法进行了比较.指出新算法执行时间比传统的φ-adic算法要少20%到40%.     

Carry-save architectures for high-speed digital signal processing

Carry-save arithmetic, well known from multiplier architectures, can be used for the efficient CMOS implementation of a much wider variety of algorithms for high-speed digital signal processing than, only multiplication. Existing architectural strategies and circuit concepts for the realization of inner-product based and recursive algorithms are recalled. The two's complement overflow behavior of carry-save arithmetic is analyzed and efficient overflow correction schemes are given. Efficient approaches are presented for the carry-save, implementation of a saturation control. The concepts are extended and refined for the high-throughput implementation of decisiondirected algorithms such as division, modulo multiplication and CORDIC which have yet been avoided because of a lack of efficient concepts for implementation.It is shown, that the carry-save technique can be extended to a comprehensive method to implement high-speed DSP algorithms. Successfully fabricated commercial VLSI circuits emphasize the potential of this method.