一个基于分治法的快速多精度乘法

多精度运算中,乘法的设计与实现非常复杂,传统的多精度乘法的时间复杂度为O(n2),基于分治法介绍了一种改进的快速乘法,通过理论分析,改进算法的时间复杂度为O(nlog23).     

二元周期序列的5错线性复杂度

线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标。该文通过研究周期为2n的二元序列的线性复杂度,将k错线性复杂度的计算转化为求Hamming重量的最小的错误序列,基于Games．Chan算法,分析了线性复杂度为2n,周期为2n的二元序列的5错线性复杂度的分布情况,给出了5错线性复杂度为2n-3,2n-3＋1和2n-2-2n-4的二元序列的计数公式,并通过计算机编程进行了验证。     

最值吸收算法解决矩阵连乘次序问题

通过分析矩阵序列乘法的特点,找到了一种新的算法一最小维数边界吸收算法,并将此算法分别与穷举搜索算法、动态规划算法的时间复杂度及空间复杂度进行分析比较．可以看出,动态规划算法的时间复杂度为O（n^3）,空间复杂度为O（n^2）,而本算法的时间复杂度和空间复杂度均为O（n）,并且不需要额外的空间开销．     

基于Karatsuba和Vedic算法的快速单精度浮点乘法器

针对现有的单精度浮点乘法器存在运算速度慢的问题,该文设计了一种融合Karatsuba算法和Vedic算法两者优点的快速单精度浮点乘法器。该文利用Karatsuba算法减少单精度浮点乘法器的乘法运算次数,将24 bit尾数的乘法运算分解为少位数乘法运算,获得基于3 bit和4 bit的尾数乘法架构;进一步地,利用Vedic算法对单精度浮点乘法器的尾数乘法架构进行优化,利用复杂度低、速度快的加法器实现了Karatsuba算法分解后的3 bit和4 bit的两个基本乘法运算,提高了运算速度。仿真及FPGA验证结果表明,该文设计的单精度浮点乘法器相对于基于传统的Karatsuba算法的单精度浮点乘法器、基于Vedic算法的单精度浮点乘法器,其最大运行时钟频率分别提高了约5倍和2倍。     

量子图像乘法运算及其仿真实现

为了解决图像处理领域中经典图像乘法运算复杂度较高的问题，提出了一种量子图像乘法运算的实现方式.首先对基于NEQR表示模型的图像制备方式进行改进，采用按行制备的方式以降低时间复杂度；然后根据二进制数的乘法步骤，使用Toffoli门和量子全加器结合移位操作设计量子乘法器；之后将制备好的量子图像使用量子乘法器进行相乘，最终实现量子图像的乘法运算.使用经典计算机与IBM平台提供的可编程量子模拟器进行量子图像乘法运算的仿真，所得的概率直方图表明该算法实现了图像的相乘.对比实验表明，该文研究的量子图像乘法运算与经典图像乘法运算相比在时间复杂度上有指数级提升.     

一种余数系统基扩展算法及VLSI实现

基扩展是余数系统(RNS)在数字信号处理(DSP)系统中应用的关键问题之一。该文提出了一种新型基扩展算法,实现基为{2n-1,2n,2n+1}的余数系统到基为{22n-1,22n,22n+1}的余数系统的动态范围扩展。给出其VLSI实现结构,并基于{2n-1,2n,2n+1}的特性对该结构进行了优化,使该实现结构仅由普通二进制加法器和模加法器构成。基于单位门模型和ASIC的性能对比分析结果表明,在实现相同动态范围扩展时,该算法具有良好的VLSI实现性能。     

二维非递归的低成本FIR滤波器设计方法

为降低有限冲激响应(Finite impulse response, FIR)数字滤波器的成本,提升可综合性,提出了一种基于系数矩阵的二维非递归优化算法,并进行了仿真.首先,对现有的数字滤波器优化算法进行了调研,比较了各优化算法的优势和不足;然后,对现有的一维非递归算法进行优化,提取一维非递归算法优化后的冗余项,得到了二维非递归优化算法,并分析了算法的复杂度;最后,生成多组滤波器分别对本算法与一维非递归算法,以及本算法和现有递归算法进行仿真和对比.仿真结果表明:提出的二维非递归FIR滤波器设计方法充分利用了系数矩阵的冗余信息,保留了现有算法的最小逻辑深度特性,同时可以进一步节省中间加法器个数;相比于现有的一维非递归算法,本算法可节省10.05%(12 bit量化)和7.21%(16 bit量化)的加法器个数;在低阶滤波器的设计中,加法器使用量降低到了传统CSD表示法的30%左右,从逻辑深度和加法器个数两方面都超越了已发表的递归和非递归滤波器设计方法.     

2n-周期二元序列的6-错线性复杂度

线性复杂度和k-错线性复杂度是度量密钥流序列的密码强度的重要指标.该文通过研究周期为2n的二元序列线性复杂度,基于Games-Chan算法,讨论了线性复杂度为2n-1的2n-周期二元序列的6-错线性复杂度分布情况.在大多数情况下,给出了对应6-错线性复杂度序列的计数公式,并且指出了参考文献中的一个重要错误.     

基于三步旋转坐标旋转数字计算机算法的直接数字频率综合器实现

提出基于三步旋转机制的高精度低时延坐标旋转数字计算机 (CORDIC)算法. 该算法通过对输入角度进行二极化重编码来免除剩余旋转角度的运算,利用三步旋转机制对迭代次数进行压缩,结合合并迭代技术进一步减少迭代次数,降低输出时延. 以16位输出位宽为例,对三步旋转CORDIC算法和流水线迭代式算法进行实现,仿真结果表明：三步旋转CORDIC算法与流水线迭代式算法相比,改善了输出精度,输入到输出的时延降低了75%,硬件开销下降了29.2%. 基于三步旋转CORDIC算法,实现了相位累加器位宽为24的直接数字频率综合器 (DDFS);使用加法树结构对多输入加法器进行优化,以提高电路工作频率. 仿真结果表明,该算法的最大幅度误差为8.24 × 10^?6,输出时延为38.5 ns.     

一个反对称矩阵乘法的快速算法

矩阵乘法是数值计算中的常见问题,其运算阶的降低一直是人们关注的基本问题,而多项式求值、多项式插值及多项式求导问题迄今已出现了许多有效且稳定的快速算法。讨论了一个n阶反对称矩阵与n维列向量的乘法问题,证明了该问题与多项式求值问题的等价性,提出了一个运算阶为O（n(log2n)2）的快速算法,并讨论了一个反对称矩阵乘法的例子,其O(n2)的运算阶在反对称矩阵乘法情形至少可降低到O（n(log2n)2）。     

2n周期平衡二元序列的6-错线性复杂度

该文针对线性复杂度和k-错线性复杂度是度量密钥流序列的密码强度的重要指标.周期序列的k-错线性复杂度就是在其一个周期改变至多k比特后所得到的线性复杂度最小值.基于Games-Chan算法,讨论了线性复杂度小于2n的2n-周期二元序列的6-错线性复杂度分布情况,给出了对应6-错线性复杂度为2n-2,2n-3和2n-3+1...     

基于现场可编程门阵列的高斯滤波算法优化实现

针对传统高斯滤波算法硬件设计方法中关键路径较长、逻辑延时较大的问题,提出加数压缩的硬件优化实现方法.在高斯滤波算法优化实现过程中,采用移位操作来实现乘法与除法计算,避免使用乘法器与除法器.并引入保留进位加法器(CSA)、基于多路选择器(MUX)的4-2压缩器、加数压缩的树型结构,对9个加数进行3个层次的压缩.经过优化后,只需1个全加器便可得求和结果.结果表明,经过加数压缩设计可以达到缩短关键路径、减少逻辑延时的目标,使逻辑延时缩小32.48%,同时还极大节省所需加法器宏单元数,为后续图像处理模块提供更大的设计自由度.     

线性划分问题的一个改进算法

给定一个由n个非负数构成的序列X={x1, x2, …, xn}及正整数k≤n, 线性划分问题要求将该序列划分为不大于k段子序列,使得最小化各段子序列元素之和为最大值。目前已知该问题的最好算法是时间复杂度为O(kn2)和空间复杂度为O(kn)的动态规划算法。利用非负数序列的性质,给出一个快速改进算法,其时间复杂度为O(knlogn),空间复杂度为O(n)。     

基于缩边递推法的图色多项式求解算法设计与分析

给出了缩边递推法求解图的色多项式的有效算法,并用Java语言在计算机上实现：输入图的顶点数n及每一条边,即能在屏幕上输出该图图形及其色多项式;最后对算法实现的效率进行了分析,其时间复杂度为O（n2）。     

广义自缩生成器的猜测决定攻击

利用猜测决定攻击分析了广义自缩生成器的安全性。结果表明,n级线性移位寄存器构成的广义自缩生成器的猜测决定攻击的时间复杂度为O（n3·1/（2（1＋α）n））,存储复杂度为O（n2）,数据复杂度为O（（1-β）/（2（1＋α）N））。猜测决定攻击可以以一定概率实现在不同条件下对广义自缩生成器的攻击,因此不失为一种良好的攻击方法。     

MIMO空间复用系统中的一种新的低复杂度球形检测算法

针对采用高阶正交幅度调制(MQAM)的多输入多输出(MIMO)复用系统,提出一种新的基于分层调制的M IMO球形检测算法.新算法利用高阶正交幅度调制的分层特性,对高阶正交幅度调制的星座点进行区域划分,根据权重系数大的调制子层数据确定候选区域,在候选区域中采用最小距离准则进行星座点优选,再采用球形检测算法对各层优选后的星座点进行搜索,确定发送数据矢量.计算机仿真结果表明,与多状态球形检测(MSD)算法相比,新算法的误码率(BER)性能有所改善,且其复杂度大约仅是MSD的20%.     

求GF(pm)上周期为kn的序列线性复杂度的快速算法

提出和证明了求GF(p^m)上周期为kn的序列线性复杂度和极小多项式的一个快速算法, 其中p是素数, gcd(n, p^m-1)=1且p^m-1=kt, n,k与t均为正整数．该算法推广了陈豪提出的求GF(p^m)上周期为3n的序列线性复杂度的一个快速算法, 其中p是素数, gcd(n, p^m-1)=1且p-1=3t, n与t均为正整数．结合一些已知的快速算法, 可以快速计算GF(p^m)上周期为kn的序列线性复杂度, 最后给出一个具体例子．     

介绍一种计算相关和卷积的新算法

本文介绍一种计算相关和卷积的新算法。以卷积Z=sum from k=0 to -1 y_Ax(n=0,1,…2N-2)为例,考虑到计算机的乘法运算速度比加法运算要慢得多,当数据点少于128时,本算法比FFT法更有效,并且几乎只需直接计算的运算工作量的一半。     

一种改进的多元LDPC译码算法

为解决多进制LDPC码基于FFT-BP译码算法不利于硬件实现的问题,提出了一种改进算法:利用对数运算,将乘法运算变换成对数域上的加法运算,从而降低复杂度,便于硬件实现。对该算法在高斯白噪声信道,基于GF(4)有限域、码率0.5的规则LDPC码(486,972)进行了仿真分析。结果显示:改进的FFT-BP译码算法相对传统的FFT-BP译码算法,在误码性能上损失极小(当误码率10-4时,信噪比损失大约0.07dB)情况下,能够使译码算法硬件复杂度得到较大的改善。     

Cauchy矩阵Moore-Penrose逆的快速算法

给出了求以秩为n的m×n阶Cauchy矩阵Moore-Penrose逆的快速算法,该算法的计算复杂度为O(mn)+O(n2)。而用C+=(CTC)-1CT求解C+时所需的运算量为O(mn2)+O(n3)