轻量级迭代MDS矩阵的构造

随着具有最大分支数的扩散层在分组密码和hash函数中的应用,轻量级MDS矩阵的构造受到广泛关注.基于迭代构造是实现低成本MDS矩阵的一种有效方法.将低成本的矩阵通过迭代一定次数后成为MDS矩阵,通过实现该低成本的矩阵来实现MDS性质.但是这种方法需要以增加迭代次数个时钟周期等待时间为代价.本文通过减少矩阵迭代次数,从而降低矩阵实现的延迟,来构造更加轻量的迭代MDS矩阵.在迭代次数小于等于阶数时,本文给出了有限域F_{2^m}上4阶矩阵在不同迭代次数下,能够成为迭代MDS矩阵所含非零元个数的下界;进一步地,通过矩阵置换相似分类及MDS条件,不断减小可行空间,实现了非零元个数达到下界的迭代MDS矩阵的穷搜,从而找到在该迭代次数下异或数达到下界的4阶迭代MDS矩阵.     

基于循环谱的多循环频率加权合作频谱检测

在接入主用户授权频段之前,认知用户需要检测该频段是否处于空闲状态,以免干扰主用户通信.利用主用户信号和噪声的不同谱相关特性,研究了基于循环谱的频谱检测方法.将主用户非零循环频率上的接收信号循环谱幅度作为检测统计量,给出了判决准则和检测方法.利用主用户信号在不同循环频率下不同程度的循环平稳特征,多个循环频率之间通过加权迭代合作来提高检测结果的可信度;并通过蒙特卡罗仿真方法验证该方法的可行性.仿真结果表明:加权迭代合作可有效实现频谱检测,且检测性能优于等权合作检测;通过合理选择信号采样点数、循环频率个数、迭代次数进行合作检测既可有效提高检测概率,又能保证检测灵敏度.     

隐式B样条曲线拟合的加权PIA算法

为了使拟合数据点的曲线生成速度更快、误差更小,提出一种隐式B样条曲线拟合数据点的加权PIA算法.首先,用待拟合数据点以及给定法向量生成偏移点集.然后,通过偏移点集构造差分向量,从而得到需要调整的误差控制系数,为了使迭代效率更高,在迭代过程中对误差控制系数做加权处理.最后,用最新的控制系数矩阵得到拟合数据点的曲线.文中5个数值算例采用均匀节点序列,实验结果表明,在相同迭代次数下,相对于I-PIA算法,该算法得到的拟合曲线误差值更小,曲线能更好保特征.     

大规模RC网络的优化消去模型降阶算法

针对电路后仿中大规模、多端口RC矩阵在降阶时非零元会显著增加,导致降阶系统处理时间大幅上升的问题,提出了寻找最优剩余节点数,使降阶后的网络求解速度达到最优的算法.首先采用统计建模的方法得到RC网络求解时间与节点数、非零元数的近似关系;然后在对实际电路进行模型降阶时用节点消去法快速得到剩余节点数与非零元的关系,从中选出最优的剩余网络节点数并根据它实施模型降阶,实验结果表明,采用该策略得到的降阶网络不造成精度损失,且使电路求解速度比已有方法快2～5倍.     

基于分而治之的多维标度算法

作为一种典型的多元统计分析方法,多维标度法(MDS)广泛应用于降维和可视化研究中.MDS从n个样本间的距离距阵出发,求取它们在低维欧氏空间的坐标.经典MDS算法(CMDS)的时间复杂度为Θ(n3),影响MDS的速度.文中基于分而治之的思想提出一种新的MDS算法.首先将距离矩阵沿对角线分成若干子矩阵,然后对每个子矩阵求解,最后通过正交变换和平移变换整合各子矩阵的解,从而得到原距离矩阵的全局解.该算法的结果与CMDS完全一致.当样本维数远小于样本个数时,其时间复杂度仅为Θ(nlgn).与CMDS算法相比,该算法的速度大大提高,从而使MDS可应用于更大规模数据集.     

基于相乘法的图像置乱算法

简单幻方变换的图像置乱算法只是简单的元素迭代,使得图像置乱在较少迭代次数情况下难以达到满意的置乱效果。针对以上问题,分析了相乘法构造幻方应用于图像置乱的合理性,提出了一种新的基于幻方变换的双重迭代图像置乱算法。该算法采用小幻方通过相乘法来生成大幻方,应用幻方分块来实现双重迭代。实验结果表明,与简单幻方变换的图像置乱算法相比,该算法只需要在较少迭代次数下就能达到令人满意的置乱效果,而且在准周期问题方面也进行了改进。     

MDS矩阵和对合MDS矩阵的新构造方法

首先对Lacan等人给出的由Vandermonde矩阵构造MDS码的方法进行了研究, 指出了其中存在的问题, 给出了由两个Vandermonde矩阵构造MDS矩阵的充要条件; 然后利用矩阵乘的方法, 给出了由标量乘Vandermonde矩阵构造MDS矩阵的充要条件; 最后在Sajadieh等人给出的由两个Vandermonde矩阵构造对合MDS矩阵方法的基础之上, 给出了标量乘Vandermonde矩阵构造对合MDS矩阵的方法。对标量乘矩阵来讲, 可以通过调控标量中分量的大小来调整标量乘矩阵元素大小和元素重量大小来满足其软、硬件实现性能, 因此该构造MDS矩阵及对合MDS矩阵的方法具有实用价值。     

多维Plateaued函数的构造

布尔函数在编码、组合设计和序列设计等中扮演重要的角色。利用Maiorana-McFarland构造法构造出一类Plateaued函数,在此基础上,结合m-序列的状态转移矩阵,构造出n元(n+1)/2维的n-1阶Plateaued函数。所构造的多维Plateaued函数可以满足多个密码指标,即高非线性度、没有非零线性结构、平衡、代数次数达到最高等。     

基于PageRank和谱方法的个性化推荐算法

传统的PageRank推荐算法的可扩展性较差。针对这一问题,提出融合PageRank和谱方法的个性化推荐算法。通过在PageRank算法迭代过程中加入候选集节点数来控制迭代的次数,同时利用阈值来修剪参与迭代的节点个数,从而得到候选节点集;采用谱聚类对候选集进行排序,归一化候选节点邻接矩阵,使用矩阵的特征值与特征向量来评估图中节点与目标节点之间的距离,从而产生最终的推荐列表。实验结果表明,所提推荐算法在保证推荐质量的前提下,提高了处理效率。     

一类具有最大分支数的16阶0-1矩阵构造

具有最大分支数的0—1可逆矩阵被广泛应用于分组密码的扩散结构设计中。为构造16阶该类矩阵,将16阶0—1矩阵划分为以4阶0-1矩阵为单元的4阶块矩阵,根据特征和域上重量均为2的4维0-1向量相加后所得向量的重量分布特点,在行置换同构意义下构造满足某种特殊结构的4阶0．1矩阵单元组,以此为基础,根据Hadamard矩阵的结构特点,利用矩阵的分块构造思想,给出一类分支数达到最大值8的16阶0-1可逆矩阵和对合矩阵构造方法,并在行置换同构意义下给出对合矩阵的计数。     

Parallel solution of linear systems with striped sparse matrices

The multiplication of a vector by a matrix and the solution of triangular linear systems are the most demanding operations in the majority of iterative techniques for the solution of linear systems. Data-driven VLSI networks which perform these two operations, efficiently, for certain sparse matrices are introduced. In order to avoid computations that involve zero operands, the non-zero elements in a sparse matrix are organized in the form of non-overlapping stripes, and only the elements within the stripe structure of the matrix are manipulated. Detailed analysis of the networks proves that both operations may be completed in n global cycles with minimal communication overhead, where n is the order of the linear system. The number of cells in each network as well as the communication overhead, are determined by the stripe structure of the matrix. Different stripe structures for the class of sparse matrices generated in Finite Element Analysis are examined in a separate paper.     

Sparse systems solving on GPUs with GMRES

Scientific applications very often rely on solving one or more linear systems. When matrices are sparse, iterative methods are preferred to direct ones. Nevertheless, the value of nonzero elements and their distribution (i.e., the sketch of the matrix) greatly influence the efficiency of those methods (in terms of computation time, number of iterations, result precision) or simply prevent the convergence.     

Stochastic P-type/D-type iterative learning control algorithms

This paper presents stochastic algorithms that compute optimal and sub-optimal learning gains for a P-type iterative learning control algorithm (ILC) for a class of discrete-time-varying linear systems. The optimal algorithm is based on minimizing the trace of the input error covariance matrix. The state disturbance, reinitialization errors and measurement errors are considered to be zero-mean white processes. It is shown that if the product of the input-output coupling matrices C ( t + 1 ) B ( t ) is full column rank, then the input error covariance matrix converges to zero in presence of uncorrelated disturbances. Another sub-optimal P-type algorithm, which does not require the knowledge of the state matrix, is also presented. It is shown that the convergence of the input error covariance matrices corresponding to the optimal and sub-optimal P-type and D-type algorithms are equivalent, and all converge to zero at a rate inversely proportional to the number of learning iterations. A transient-response performance comparison, in the domain of learning iterations, for the optimal and sub-optimal P- and D-type algorithms is investigated. A numerical example is added to illustrate the results.     

基于随机间距稀疏 Toeplitz 测量矩阵的压缩传感

选择合适的测量矩阵是压缩传感理论实用化的关键之一. 本文在Toeplitz矩阵独立元素中随机地引入零元,形成随机间距稀疏Toeplitz矩阵, 使得随机独立变元个数可以减少到原Toeplitz矩阵的1/2～1/16,甚至更少, 非零元个数同样大大减少,有利于数据传输和存储.模拟实验表明随机间距稀疏 Toeplitz矩阵在重建效果优于Gauss矩阵和原Toeplitz矩阵的同时,重建时间只有Gauss矩阵和一般Toeplitz矩阵重建时间的约15%～40%.     

多视三角化的迭代算法

多视三角化是在给定测量点对应和摄像机投影矩阵的情况下,求解相应的空间点的过程.由于测量点存在测量误差,所以只能求解在某种准则下的最优空间点.文中提出一种新的优化准则:在空间平面矩阵最小奇异值为0的约束下最小化估计点到测量点的L2-范数距离.在此基础上,采用该准则约束的Sampson近似得到一种简单的迭代求解方法;通过空间平面矩阵最小奇异值单调递减的条件和共轭梯度方法得到另一种收敛性更好的迭代算法.实验结果表明,这2种迭代算法不仅迭代次数及运算时间明显少于黄金标准算法,而且能得到基本相同的计算精度.     

Basic Lul Factorization And Improved Iterative Method With Orderings

Consider the 'basic LUL factorization' of the matrices as the generalization of the LU factorization and the UL factorization, and using this LUL factorization of the matrices, we propose an "improved iterative method" such that the spectral radius of this iterative matrix is equal to zero, and this method converges at most n iterations. Our main concern is the necessary and sufficient conditions that the improved iterative matrix is equal to the iterative matrix of the improved SOR method with orderings. Concerning the tridiagonal matrices and the upper Hessenberg matrices, this method becomes the improved SOR method with orderings, and we give n selections of the multiple relaxation parameters such that the spectral radii of the corresponding improved SOR matrices are 0. We extend these results to a class of $n \times n$ matrices. We also consider the basic LUL factorization and improved iterated method 'corresponding to permutation matrices'.     

Turbo码的按位迭代译码仿真与优化

Turbo码的迭代译码次数越多,译码延时和功耗也越大,通过图像传输的Turbo译码仿真分析,提出按不同比特位迭代次数不同的译码方法,并对各比特位的迭代次数进行优化,结果能使总迭代译码次数减少50%,且能保证译码后的图像效果。     

Finite time stability conditions for non-autonomous continuous systems

Lower and upper bounds for the quadratic cost functional of linear regulators are derived. These bounds are explicitly expressed in terms of some system parameters, arc independent of the initial conditions and are rather easy to compute. The results are based on a previous work by the authors concerning the lower bound. In this paper, the upper bound established is used to improve the lower bound, both being calculated by an iterative procedure to any degree of accuracy which is dependent on the number of iterations only.