高速32位伪随机数发生器电路设计

文章提出了一种实现32位伪随机发生器电路设计方案。该方案的关键是对产生伪随机数所需要的乘法器和模2n－1加法器的设计。针对所采用的伪随机数迭代函数的特殊性,提出了特定的32位×16位乘法器以及模231－1加法器实现方案,使电路的速度得以提高,规模得以减小。整个电路设计采用VHDL语言描述,并通过了逻辑仿真验证。文章同时介绍了一般乘法器以及并行前缀模2n－1加法器的设计原理。     

关于M序列:有限域中本原元的升幂序列与M序列的关系

本文提出了M序列的一个新定义,即利用有限域中本原元的升幂序列来定义M序列。用这种方法,很容易推导出M序列的性质。本文还给出一个用模2加法器合成M序列一个平移等价类中的全部M序列(即不同相位的M序列)的计算方法。它在设计不同相位的M序列时是有用的。本文还推导出用于M序列设计的一些关系式,并指出最多只要(n-2)个模2加法器便可得到任一相位的M序列。     

二维离散哈特莱变换的乘法复杂性

本文研究了长度为2~n×2~n(n为正整数)二维离散哈特莱(Hartley)变换的乘法复杂性。虽然DHT(2~n;2)的变换核cas[2π(kp+lq)/2~n]不象DFT(2~n,2)的变换核exp[—2πj(kp+lq)/2~n]那样可以分离成一维DHT变换核的乘积,但是DHT(2~n;2)可以利用线性同余组和环结构转换成1个DHT(2~(n-1);2)和(3/2)2~n个一维奇DHT.一维奇DHT可以简化为一维DHT的核CHT的直和,在有理数域Q上计算长度为2~n的二维离散DHT(2~n;2)所需的最少实乘次数为2~(2n+1)—6(n—1)2~n—8。所以二维DHT(2~n;2)和相应的实DFT(2~n;2)具有相同的乘法复杂性。     

一种新的余数系统下快速计算素域椭圆曲线点乘的方法

椭圆曲线密码运算主要是椭圆曲线点乘,后者由一系列的模乘构成。利用余数系统下的蒙哥马利模乘算法,素域中对阶取模余的模乘可以转化为对余数系统基底取模余。提出一种新的余数系统下的方法以加速计算椭圆曲线点乘。（1）与传统上取两个几乎对称的余数系统不同,该方法取了两个非对称的余数系统。其中,余数系统Γ包括两个模数{2L, 2 L-1}; 余数系统Ω包括八个模数,它们都具有如2L－2Ki+1的形式。这种选择使其模算术变得简单。（2）在上述非对称的余数系统中,大部分原来需要对椭圆曲线域特征值取模的模乘运算可以在余数系统中直接用乘法代替。此外,计算椭圆曲线点乘时用到了仅计算x坐标的蒙哥马利梯子。在每次并行的倍点和点加结束时,需要四次余数系统下的蒙哥马利模乘,以压缩中间结果的值域。因此,计算一个N位的椭圆曲线点乘,需要的时间约为55.5N·I, 其中,I是一个L/2位的乘法、一次保留进位加法、一个L/2位的加法的总延时。     

一种进位链TDC的实现及其抽头方式研究

采用Xilinx公司的Kintex-7内部的进位链,实现了时间数字转换器(Time to Digital Converter,TDC)。采用码密度校准方法 对TDC进行逐位校准,标定了TDC的码宽。码密度校准过程中发现,不同的进位链抽头位置会导致TDC的码宽不同、非线性不同,研究了2抽头、 4抽头方式下的TDC的码宽和非线性,在“0tap+3tap”的2抽头方式下,TDC可以获得较好的线性,时间分辨率为25 ps(对应最低有效位(Least Significant Bit,LSB)),微分非线性范围为-0.84～3.1 LSB,积分非线性范围为-5.2～2.2 LSB。     

可重构模运算单元的研究

分析了多种对称密码算法,总结了几种常用的模运算,设计并实现了高效、灵活的可重构模运算单元,该单元支持模28加、模28减、模28乘、模216加、模216减、模216乘、模(216+1)乘、模232加、模232减、模232乘及模(232-1)乘运算,也支持模28加、模28减、模28乘、模216加、模216减、模216乘及模(216+1)乘中任意2种运算的并行操作,给出了通用的操作指令。实验证明了该运算单元的有效性。     

模2n 加和模2加混合运算的异或分支数

研究了扩散结构为二元域上非线性变换的异或分支数.给出了扩散结构为二元域上非线性变换的异或分支数的定义及其与分组密码抗差分攻击和线性分析能力的关系,证明了以模2n加和模2加的混合运算为扩散结构的异或分支数等于将模2n加换成模2加且将各变元系数模2后所得的二元域上线性变换的异或分支数,从而简化了此类非线性扩散结构异或分支数的计算问题.     

基于Montgomery模乘的RSA加密处理器

提出一种基4的Montgomery模乘算法及优化的硬件结构,将传统基2模乘运算迭代次数减少近一半。在该模乘模块基础上设计高速RSA加密处理器,采用进位保留形式的全并行模幂运算流程,避免长进位链和中间结果转换的问题。结果表明,该设计同时适应FPGA和ASIC实现,完成一次标准1 024位RSA加密运算仅需9 836个周期,加密速率提高50%以上。     

环F2+uF2+u2F2上线性码的深度分布

记R=F₂+uF₂+u²F₂,定义了环R上码字的深度以及R上线性码的深度分布,研究了环R上码字深度的性质,给出了计算环[R]上码字深度的递归算法。利用环R上的线性码C及其生成矩阵,得到了域F2上的线性码C1,Cu,Cu2及相应的生成矩阵。通过域F2上的线性码C1,Cu,Cu2之间的关系,讨论了环R上的线性码的深度谱和深度分布,进而得到R上一类线性码的深度分布。     

MPEG-1/2到MPEG-4码流转换的研究与实现

该文研究并实现了MPEG-1/2码流到MPEG-4码流的转换,包括MPEG-1/2码流的解码及其优化,MPEG-4视音频码流的编码及其优化,及编码后生成的MPEG-4视音频码流的合成。     

An efficient architecture for designing reverse converters based on a general three-moduli set

In this paper, a high-speed, low-cost and efficient design of reverse converter for the general three-moduli set {2^α, 2^β − 1, 2^β + 1} where α < β is presented. The simple proposed architecture consists of a carry save adder (CSA) and a modulo adder. As a result it can be efficiently implemented in VLSI circuits. The values of α and β are set in order to provide the desired dynamic range and also to obtain a balanced moduli set. Based on the above, two new moduli sets {2^n+k, 2²ⁿ − 1, 2²ⁿ + 1} and {2²ⁿ⁻¹, 2²ⁿ⁺¹ − 1, 2²ⁿ⁺¹ + 1}, which are the special cases of the moduli set {2^α, 2^β − 1, 2^β + 1} are proposed. The reverse converters for these new moduli sets are derived from the proposed general architecture with better performance compared to the other reverse converters for moduli sets with similar dynamic range.     

On Complexity of Computation of Partial Derivatives of Boolean Functions Realized by Zhegalkin Polynomials

The combinational complexity of a system of partial derivatives in the basis of linear functions is established for a Boolean function of n variables that is realized by a Zhegalkin polynomial. An algorithm whose complexity equals 3ⁿ – 2ⁿ modulo 2 additions is proposed for computation of all partial derivatives of such a function from the coefficients of its Zhegalkin polynomial.     

Area and delay efficient GDI based accuracy configurable adder design

Adders are one of the basic fundamental critical arithmetic circuits in a system and their performances affect the overall performance of the system. Traditional n-bit adders provide precise results, whereas the lower bound of their critical path delay of n bit adder is Ὠ(log n). To achieve a minimum critical path delay lower than Ὠ(log n), many inaccurate adders have been proposed. These inaccurate adders decrease the overall critical path delay and improve the speed of computation by sacrificing the accuracy or predicting the computation results. In this work, a fast reconfigurable approximate ripple carry adder has been proposed using GDI (Gate Diffusion Logic) passing cell. Here, GDI cell acts as a reconfigurable cell to be either connected with the previous carry value or approximated value in an adder chain. This adder has greater advantage and it can be configured as an accurate or inaccurate adder by selecting working mode in GDI cell. The implementation results show that, in the approximate working mode, the proposed 64-bit adder provides up to 23%, 34% and 95% reductions in area, power and delay, respectively compared to those of the existing adder.     

Computing Frobenius maps and factoring polynomials

A new probabilistic algorithm for factoring univariate polynomials over finite fields is presented. To factor a polynomial of degreen overF _q , the number of arithmetic operations inF _q isO((n ²+nlogq). (logn)² loglogn). The main technical innovation is a new way to compute Frobenius and trace maps in the ring of polynomials modulo the polynomial to be factored.     

Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2

Summary Polynomial multiplication of degree N can be accomplished in time O (N · log N) provided the scalar field contains suitable roots of unity. Otherwise at least O (N · log N · log log N) is obtained by a modified version of the Schönhage-Strassen multiplication which employs computations modulo 1 + xⁿ (where N = 2ⁿ), if the field contains 2^–1, or modulo 1 + xⁿ + x^2N, if 3^–1 exists. The latter method covering all fields of characteristic 2 is presented here in detail.     

The Complexity of Boolean Functions in Different Characteristics

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}ⁿ → {0, 1} which depend on all n variables, and distinct primes p, q:

The prism machine: An alternative to the pyramid

The prism machine is a stack of n cellular arrays, each of size 2ⁿ × 2ⁿ. Cell (i, j) on level k is connected to cells (i, j), (i + 2^k, j), and (i, j + 2^k) on level k + 1, 1 ≤ k < n, where the sums are modulo 2ⁿ. Such a machine can perform various operations (e.g., “Gaussian” convolutions or least-squares polynomial fits) on image neighborhoods of power-of-2 sizes in every position in O(n) time, unlike a pyramid machine which can do this only in sampled positions. It can also compute the discrete Fourier transform in O(n) time. It consists of n · 4ⁿ cells, while a pyramid consists of fewer than 4ⁿ⁺¹/3 cells; but in practice n would be at most 10, so that a prism would be at most about seven times as large as a pyramid.     

AN EXTENSION OF HILL CIPHER USING GENERALISED INVERSES AND mth RESIDUE MODULO n

Hill Cipher is a symmetric polyalphabetic block cipher that enciphers a string of letters into another string of the same length using the linear transformation y=xK. In deciphering, the determinant value must be less than 26 and relatively prime to 26 so that the matrix K of the linear transformation is invertible in modulo 26. The Affine Hill cipher extends the concept of Hill cipher by using the non-linear transformation y=xK+b. In this paper, we extend this concept to encrypt a plaintext of blocksize m to a ciphertext of blocksize n≥m using (a) affine transformation and (b) polynomial transformation to make this cipher more secure. Here the matrix K of the transformation need not be a square matrix. To enable decryption, we state the conditions to be satisfied by K which are as follows. Case (a): (i) For affine transformation, the generalised inverse K ⁺ of the matrix K corresponding to the transformation should satisfy the equation KK ⁺=I in modulo p where p is a chosen prime p>26. For m=n, K ⁺ is the usual inverse of the matrix K. Case(b): (i) For polynomial transformation, the generalised inverse K ⁺ should satisfy the above condition, (ii) If r is the degree of the polynomial, then choose those values of s≤r such that the sth root of modulo p exists for all elements in Z _p . In other words, choose those values of s that are relatively prime to Φ(p).     

A low energy dual-mode adder

VLSI designs are typically data-independent and as such, they must produce the correct result even for the worst-case inputs. Adders in particular assume that addition must be completed within prescribed number of clock cycles, independently of the operands. While the longest carry propagation of an n-bit adder is n bits, its expected length is only O(log₂ n) bits. We present a novel dual-mode adder architecture that reduces the average energy consumption in up to 50%. In normal mode the adder targets the O(log₂ n)-bit average worst-case carry propagation chains, while in extended mode it accommodates the less frequent O(n)-bit chain. We prove that minimum energy is achieved when the adder is designed for O(log₂ n) carry propagation, and present a circuit implementation. Dual-mode adders enable voltage scaling of the entire system, potentially supporting further overall energy reduction. The energy-time tradeoff obtained when incorporating such adders in ordinary microprocessor’s pipeline and other architectures is discussed.