A polynomial time algorithm for subpattern matching

An O(N³K) time algorithm for searching matches of a template of size K in an image of size N is given. It uses bounding regions and the Soviet Ellipsoid Algorithm [1]. It will work under moderately heavy shift noise.     

Efficient generation technique for polynomial codesets

The letter introduces a new technique for the generation of a set of polynomial codewords. Each word is generated with a single modulo-2 addition, rather than by using the conventional polynomial multiplication technique. The method is simple to apply and can form the basis for set generation by a minicomputer or microprocessor.     

A partitioned polynomial integration algorithm for failure probability evaluation

Devices and components are subjected to stresses of certain types which the device must withstand to maintain proper operation. The applied stress and the withstand capability of a device are typically random quantities with associated probability distributions which can have arbitrary shapes. Previous workers approximated these distributions by standard shapes, for example, normal or Weibull, to calculate the failure probability analytically. This letter avoids the approximation of distributions and presents an efficient algorithm which can handle any distribution shape with complete control of the computation accuracy.     

A new algorithm for arbitrary transformation of polynomial andrational functions

A new algorithm for performing the arbitrary polynomial transformation for single and multiple variables is presented. It is based on the polynomial interpolation of the numerator and the denominator polynomials of the rational functions at the roots of unity using the discrete Fourier transform (DFT). By proper modification of the algorithm, it is possible to compute the Q-matrix of the transformation. Generalization of the algorithm to higher dimensions is also presented     

多项式快速乘法探讨

多项式乘法具有很强的规律性,介绍了几种常见的多项式乘法算法.并根据运算规律,给出一种图解的方法,该方法具有直观易用尤其适合手算的特点.最后对该图解算法编程实现进行了探讨,实验结果表明该方法比直接使用矩阵法高效.     

A column generation algorithm for bandwidth packing

We describe a column generation branch and bound procedure for optimally solving the bandwidth packing problem. The objective of this problem is to allocate bandwidth in a telecommunications network to maximize total revenue. The problem is formulated as an integer programming problem and the linear programming relaxation solved using column generation and the simplex algorithm. A branch and bound procedure which branches upon a particular path being used for a bandwidth routing is used to solve the IP. We present computational results.This research was partially supported by a grant from the Colorado Advanced Software Institute and by Air Force Office of Scientific Research and Office of Naval Research Contract Nos. F49620-90-C-0033 and F49620-92-J-0248-DEF.     

New polynomial transform algorithm for multidimensional DCT

A new algorithm for the type-II multidimensional discrete cosine transform (MD-DCT) is proposed. Based on the polynomial transform, the rD-DCT with size N₁×N₂×···×N _r, where N_i is a power of 2, can be converted into a series of one dimensional (1-D) discrete cosine transforms (DCTs). The algorithm achieves considerable savings on the number of operations compared with the row-column method. For example, the number of multiplications for computing an r-dimensional DCT is only 1/r times that needed by the row-column method, and the number of additions is also reduced. Compared with other known polynomial transform algorithms for MD-DCT and the most recently presented algorithm for MD-DCT, the proposed one uses about the same number of operations. However, advantages such as better computational structure and flexibility in the choice of dimensional sizes can be achieved     

A new algorithm for the generation ofk-AryM sequences

A new algorithm for generatingk-aryM sequences is given. In the algorithm a new method is used that the main cycle is extended by joining to it a subset of cycles instead of the classical one in which the main cycle is extended by joining to it one cycle. The algorithm reduces the times of choosing bridging states and accelerates the speed of joining cycles.     

A method for nonlinearity compensation of OFDR based on polynomial regression algorithm

A method based on polynomial regression algorithm(PRA) is proposed in this paper to compensate the nonlinear phase noise in optical frequency domain reflection(OFDR) systems. In this method, the nonlinear phase of OFDR systems is represented by the polynomial phase function, and then the coefficients of the polynomial phase function are estimated by PRA. Finally, the nonlinearity is compensated by match Fourier transform(MFT). Simulation results demonstrate that the proposed algorithm has good performance in compensating both weak and strong nonlinear phase noises of OFDR systems.     

Improved fast polynomial transform algorithm for cyclic convolutions

An improved version of the Fast Polynomial Transform for the computation of two-dimensional cyclic convolutions is proposed in this paper. This new version of the Fast Polynomial Transform comes from the concept of splitting product-fields and gives more than a 20% to 50% reduction in the numbers of multiplications. An average of 20% improvement on overall computation time compared with the previous approach is also achievable.     

Modified algorithm for two-dimensional convolutions by polynomial transforms

Recently two new methods for computing two-dimensional convolutions by using fast polynomial transforms have been published, by Pei and Wu (1981) and Martens (1982). Analysis shows, however, that it is impossible to obtain the expected higher efficiency with the new methods as compared to the FPT-FFT-CRT algorithm presented by Truong et al. (1981). A modified method is proposed in the letter, with which a gain in efficiency of 2?5% can be achieved.     

A synthesis-based test generation and compaction algorithm for multifaults

Because of its inherent complexity, the problem of automatic test pattern generation for multiple stuck-at faults (multifaults) has been largely ignored. Recently, the observation that multifault testability is retained by algebraic factorization demonstrated that single fault (and therefore multifault) vector sets for two-level circuits could give complete multifault coverage for multilevel circuits constructed by algebraic factorization. Unfortunately, in using this method the vector set size can be much larger than what is really required to achieve multifault coverage, and the approach has some limitations in its applicability.In this article we first present a multifault test generation and compaction strategy for algebraically factored multilevel circuits, synthesized from two-level representations. We give a basic sufficiency condition for multifault testability of such networks.We next focus on the relationship between hazard-free robust path-delay-fault testability and multifault testability. We show that the former implies the latter for arbitrary multilevel circuits. This allows the use of previously developed composition rules that maintain path-delay-fault testability for the synthesis of multifault testable circuits.We identify a class of multiplexor-based networks and prove an interesting property of such networks—if the networks are fully single stuck-at fault testable, or made fully single stuck-at fault testable, they are completely multifault testable. We give a multifault test generation and compaction algorithm for such networks.We provide experimental results which indicate that a compacted multifault test set derived using the above strategies can be significantly smaller than the test set derived using previously proposed procedures. These results also indicate the substantially wider applicability of our procedures, as compared to previous techniques.     

Performance of a recursive algorithm for polynomial predistorter design

In this article, based on least square estimation, a recursive algorithm for indirect learning structure predistorter is introduced. Simulation results show that of all polynomial predistorter nonlinear terms, higher-order （higher than 7th-order） nonlinear terms are so minor that they can be omitted in practical predistorter design. So, it is unnecessary to construct predistorter with higher-order polynomials, and the algorithm will always be stable. Further results show that even when 15th-order polynomial model is used, the algorithm is convergent after 10 iterations, and it can improve out-band spectrum of 20 MHz bandwidth signal by 64 dB, with a 1.2×10^11 matrix condition number.     

A fast algorithm for the generation ofk-ary De Bruijn sequences

De Bruijn sequences are highly important nonlinear shift register sequences. This paper presents a new algorithm for the generation ofk-ary de Bruijn sequences by juxtaposing the periodic reductions of the cycles. Its each step produces a string of elements instead of one element. Hence the algorithm reduces the time of operation, and accelerates the speed of generation.     

Interval algorithm for random number generation

The problem of generating a random number with an arbitrary probability distribution by using a general biased M-coin is studied. An efficient and very simple algorithm based on the successive refinement of partitions of the unit interval (0, 1), which we call the interval algorithm, is proposed. A fairly tight evaluation on the efficiency is given. Generalizations of the interval algorithm to the following cases are investigated: (1) output sequence is independent and identically distributed (i.i.d.); (2) output sequence is Markov; (3) input sequence is Markov; (4) input sequence and output sequence are both subject to arbitrary stochastic processes     

An estimation algorithm for 2-D polynomial phase signals.

We consider nonhomogeneous 2-D signals that can be represented by a constant modulus polynomial-phase model. A novel 2-D phase differencing operator is introduced and used to develop a computationally efficient estimation algorithm for the parameters of this model. The operation of the algorithm is illustrated using an example.     

Combined polynomial transform and radix-q algorithm for MD discreteW transform

The type-II r-dimensional discrete W transform (rD-DWT-II) with size q^l1×q^l2 ×···×^lr q where q is an odd prime number, is converted into a series of one-dimensional (1-D) reduced DWT-IIs by using the multidimensional polynomial transform and an index permutation. Then, a radix-q algorithm and a cyclic convolution algorithm are presented for the computation of the 1-D reduced DWT-IIs. The new fast algorithm substantially reduces the overall computational complexity compared with the row-column method. Especially, the number of multiplications required by the proposed algorithm for computing an rD-DWT-II is only 1/r times that needed by the commonly used row-column method     

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

本文针对低阶多项的多项式累加和问题∑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时,大大提高了低阶多项的多项式累加求和的效率.