利用剩余数制简化DNA算术运算

在DNA算术运算的理论模型中,普遍应用固定基数制,比如二进制、三进制。但是由于受到进位的影响,难以实现并行运算。基于Adleman-Lipton模型,分析了剩余数制的基本原理,改进了整数的DNA链表示,并将其应用于DNA算术运算,给出了剩余数制下进行DNA算术运算的算法模型。由于在剩余数制中,算术运算（加、减、乘）在剩余位之间无须进行进位计算,故可以降低运算过程的复杂度,而且有利于进行各个剩余位上的并行计算。     

基于DNA自动机的串行二进制进位加法的实现

提出了一种基于DNA自动机的串行二进制进位加法的实现方法。对于一位二进制的进位加法，通过预先设计的DNA自动机模型在一个试管中以自动机的方式完成。对于”位二进制的进位加法，通过将n个类似的试管按照从低位到高位的顺序组成串行网络；将低位加法操作产生的进位转移到高位试管，组成高位自动机的输入符号串，完成高位的加法操作。这种运算方式类似于电子计算机中加法运算系统，为DNA计算机实现算术运算提供了一种新颖的方法。     

DNA计算机算术运算的自装配模型（I）—加法

DNA计算是基于DNA分子生化反应,能够在DNA计算机上实现的算法。它具有高度并行性、容量大、速度快等特点。同传统电子计算机一样,它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在Labean加法的基础上,设计了通用的N进制的并行加法DNA自装配模型,算法的时间复杂度为O（1）,空间复杂度为O（n）。在此基础上又设计了一位数连加的DNA自装配模型,为今后的并行乘法奠定了基础。算法的主要优点在于编码简单、效率高,且具有通用性。     

实现快速运算的剩余系统

一、概述 二进制与十进制具有许多优点,它们已广泛地用于数字计算机的算术运算。但是,由于它们是一种固定基的加权数制,所以对于任何算术运算,其结果的每一位数字不仅依赖于操作数的对应位,而且依赖于比该位低的数位上的所有数字。由于运算时需要考虑进位传送,不可能实现所有数位的并行运算,从而使得算术运算的速度受到限制。随着电子计算机运算速度的迅速提高,在执行算术运算时为了处理     

DNA计算机算术运算的自装配模型(Ⅲ)—减法

DNA计算是基于DNA分子生化反应,能够在DNA计算机上实现的算法。它具有高度并行性、容量大、速度快等特点。同传统电子计算机一样,它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在DNA自装配加法的基础上,设计了一般的DNA自装配并行减法模型,算法的时间复杂度为O(1),空间复杂度为O(n),并通过实例验证了算法的有效性。算法的主要优点在于编码简单、效率高,且具有通用性。     

TTL中规模集成电路及其应用

<正> 三、算术逻辑运算单元算术逻辑运算单元是功能较强的中规模集成电路。除了能进行快速加法运算外还能进行其它算术运算(如减法……)及逻辑运算(如逻辑乘、求反……)。集成化运算单元的结构设计主要考虑两个问题: (一)提高运算速度,普遍在片内采用超前进位技术;运算单元要能扩展,能和专门的快速进位扩展器配合,组成多片快速运算单元。     

LSMPP并行C语言设计

LSMPP并行C语言是针对LSMPP嵌入式并行计算机而设计的并行语言,在选取特定的C语言子集的基础上进行并行扩充得到,并增加了图像处理函数库及算术运算函数库,形成的面向图像处理的并行语言。     

基于互补电阻开关的忆阻乘法器设计

现有的忆阻算术逻辑多采用单个忆阻器作为存储单元,在忆阻交叉阵列中易受到漏电流以及设计逻辑电路时逻辑综合复杂度高的影响,导致当前乘法器设计中串行化加法操作的延时和面积开销增加。互补电阻开关具有可重构逻辑电路的运算速度和抑制忆阻交叉阵列中漏电流的性能,是实现忆阻算术逻辑的关键器件。提出一种弱进位依赖的忆阻乘法器。为提升忆阻器的逻辑性能,基于互补电阻开关电路结构,设计两种加法器的优化方案,简化操作步骤。在此基础上,通过改进传统的乘法实现方式,并对进位数据进行拆解,降低运算过程中进位数据之间的依赖性,实现并行化的加法运算。将设计的乘法器映射到混合CMOS/crossbar结构中,乘法计算性能得到大幅提高。在Spice仿真环境下验证所提乘法器的可行性。仿真实验结果表明,与现有的乘法器相比,所提乘法器的延时开销从O(n²)降低为线性级别,同时面积开销降低约70%。     

基于三值光计算机的并行无进位加法

在三值光计算机(其核心是一块体积为38.0×65.5×2.2 mm~3、能耗为0.3mw的单色液晶显示器及其两侧的偏振片)上以全并行方式实现了两向量无进位光学加法。为利用光的并行性,在MSD(Modified Signed-Digit)数字系统上通过定义4个变换,分3步实现了全并行无进位加法。加法所需时间与操作数的位数无关。通过实验证明了三值光计算机并行无进位加法运算的可行性和正确性。该系统能以全并行的方式完成两个680位的MSD数加法运算。     

子字并行加法器的研究与实现

子字并行加法器能够有效提高多媒体应用程序的处理性能。基于门延迟模型对加法器原理及性能进行了分析,设计了进位截断和进位消除两种子字并行控制机制。在这两种机制的指导下,实现了多种子字并行加法器,并对它们的性能进行了比较和分析。结果表明进位消除机制相对于进位截断机制需要较短的延时,较少的逻辑门数以及较低的功耗。在各种子字并行加法器中,Kogge-Stone加法器具有最少的延迟时间,RCA加法器具有最少的逻辑门数和最低的功耗。研究结果可以用于指导子字并行加法器的设计与选择。     

Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem

The residue number system (RNS) is an unconventional number system which can lead to parallel and fault-tolerant arithmetic operations. However, the complexity of residue-to-binary conversion for large number of moduli reduces the overall RNS performance, and makes it inefficient for nowadays high-performance computation systems. In this paper, we present an improved approximate Chinese remainder theorem (CRT) with the aim of performing efficient residue-to-binary conversion for general RNS moduli sets. To achieve this aim, the required number of fraction bits for accurate residue-to-binary conversion is derived. Besides, a method is proposed to substitute fractional calculations by similar computations based on integer numbers to have a hardware amenable algorithm. The proposed approach results in high-speed and low-area residue-to-binary converters for general RNS moduli sets. Therefore, with this conversion method, high dynamic range residue number systems suitable for cryptography and digital signal processing can be designed.     

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

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

An efficient RNS parity checker for moduli set{2~n-1,2~n 1,2~(2n) 1}and its applications

Residue number system (RNS) has received considerable attention since decades before,because it has inherent carry-free and parallel properties in addition,sub-traction,and multiplication operations. For an odd moduli set,the fundamental problems in RNS,such as number comparison,sign determination,and overflow detection,can be solved based on parity checking. The paper proposes a parity checking algorithm along with related propositions and the certification based on the celebrated Chinese remainder theory (CRT) and mixed radix conversion (MRC) for the moduli set {2n-1,2n 1,22n 1}. The parity checker consists of two modular adders and a carry-look-ahead chain. The hardware implementation requires less area and path delay. Besides,the implementations of number comparison,sign determination,and overflow detection,which are based on this parity checker,are also performed in this paper. And this kind of parity checker can be used as a basic element to design ALUs and DSP module in RNS.     

Parallel computational algorithms for generalized Chinese remainder theorem

Recently, the residue number system (RNS) has been intensively studied. The Chinese remainder theorem (CRT) is a solution to the conversion problem of a number to RNS with a general moduli set. This paper introduces the generalized CRT (GCRT) with parallel algorithms used for the conversion. The GCRT differs from the CRT because it has the advantage of having more applications than does the CRT. The GCRT, however, has a disadvantage in computational performance. To remedy this shortcoming, this paper proposes algorithms that calculate concurrently for some non-related program fragments of GCRT computation. These proposed algorithms also allow the GCRT to compute more efficiently.     

PRNS—有权剩余数系统

本文提出的ＰＲＮＳ是一种有权和无权两种记数制相嵌套而构成的层次结构记数制，根据ＰＲＮＳ蚵以构造比传统二进制系统快许多倍的算术处理机，本文阐述了ＰＲＮＳ的基本概念，原理和加法算法，并提出了一种Ｓ进制ＰＲＮＳ数母全加器。     

An efficient RNS parity checker for moduli set {2^n-1, 2^n＋1, 2^2n＋1} and its applications

Residue number system （RNS） has received considerable attention since decades before, because it has inherent carry-free and parallel properties in addition, sub- traction, and multiplication operations. For an odd moduli set, the fundamental problems in RNS, such as number comparison, sign determination, and overflow detection, can be solved based on parity checking. The paper proposes a parity checking algorithm along with related propositions and the certification based on the celebrated Chinese remainder theory （CRT） and mixed radix conversion （MRC） for the moduli set {2^n-1, 2^n＋1, 2^2n＋1}. The parity checker consists of two modular adders and a carry-look-ahead chain. The hardware implementation requires less area and path delay. Besides, the implementations of number comparison, sign determination, and overflow detection, which are based on this parity checker, are also performed in this paper. And this kind of parity checker can be used as a basic element to design ALUs and DSP module in RNS.     

Fast fourier transform processors using Gaussian residue arithmetic

Residue arithmetic using moduli which are Gaussian primes is suggested as a method for computing the fast Fourier transform (FFT). For complex operations, a substantial savings in hardware and time over residue arithmetic using real moduli can be obtained using complex moduli. Gaussian residue arithmetic is discussed and methods for conversion into and out of the complex residue representation are developed. This representation lends itself to table-driven computation, allowing very low latency designs to be developed. A 64-point Cooley-Tukey style processor and a 60-point Rader-Winograd style processor using this technique are described and compared. Hardware savings are realized by approximating the rotations necessary to perform the FFT by small complex integers and by scaling the results of the computation at an intermediate point. It is shown that further hardware reductions can be made by developing custom integrated circuits at the expense of latency.     

Four-moduli set (2, 2−1, 2+2−1, 2+2−1) simplies the residue to binary converters based on CRT II

A multiplier-free residue to binary converter architecture based on the Chinese remainder theorem II (CRT II) [1] is presented. The paper also includes a binary to residue converter. This is achieved by introducing a new moduli set (2, 2ⁿ − 1, 2ⁿ + 2ⁿ⁻¹ − 1, 2ⁿ⁺¹ + 2ⁿ − 1) for RNS application. The complexity of conversion has been greatly reduced using CRT II with the new moduli set. The proposed hardware architecture replaces the necessary multiplication by shift-left operations. A similar hardware architecture is presented for the binary to residue conversion.     

On the computation of invariant sets for constrained nonlinear systems: An interval arithmetic approach

This paper deals with the computation of control invariant sets for constrained nonlinear systems. The proposed approach is based on the computation of an inner approximation of the one step set, that is, the set of states that can be steered to a given target set by an admissible control action. Based on this procedure, control invariant sets can be computed by recursion.We present a method for the computation of the one-step set using interval arithmetic. The proposed specialized branch and bound algorithm provides an inner approximation with a given bound of the error; this makes it possible to achieve a trade off between accuracy of the computed set and computational burden. Furthermore an algorithm to approximate the one step set by an inner bounded polyhedron is also presented; this allows us to relax the complexity of the obtained set, and to make easier the recursion and storage of the sets.