End-to-End Blocking for Circuit-Switched Networks: Polynomial Algorithms for Some Special Cases

Recursive algorithms for the computation of the end-to-end blocking in circuit-switched networks operating under very general routing schemes have recently been proposed and implemented, but with exponential upper bounds for their running time. For certain important classes of routings, however, we show that algorithms requiring a single pass in all the route trees are sufficient and, thus, have a polynomial bound. Furthermore, we show that the computation of the appropriate link blocking probabilities is best done by a fixed point method, rather than a Newton-type algorithm. Computational experience is also presented, indicating that these algorithms are fast enough to be considered for the evaluation step of a routing optimization procedure.     

哈默斯坦非线性时变系统的加权学习辨识方法

针对有限区间哈默斯坦(Hammerstein)非线性时变系统,该文提出一种加权迭代学习算法用以估计系统时变参数。首先将Hammerstein系统输入非线性部分进行多项式展开,采用迭代学习最小二乘算法辨识系统的时变参数。为了防止数据饱和,采用带遗忘因子的迭代学习最小二乘算法,进而引入权矩阵,采用加权迭代学习最小二乘算法改进系统跟踪误差,以提高辨识精度。该文分别给出3种算法的推导过程并进行仿真验证。结果表明,与迭代学习最小二乘算法和带遗忘因子迭代学习最小二乘算法相比,加权迭代学习最小二乘算法具有辨识精度高、跟踪误差小以及迭代次数少等优点。     

Quadratic phase integration using a Chebyshev expansion

An integration algorithm is described which is particularly effective in the numerical treatment of integrands having rapidly varying phase and slowly varying amplitude. The algorithm involves approximating the phase function by a quadratic polynomial and rewriting the integrand without approximation as a slowly varying function multiplied by this quadratic phase exponential. The slowly varying function is then approximated by Chebyshev expansion and the desired integral is thus expressed as a sum of constituent integrals with integrands containing a Chebyshev polynomial multiplied by the quadratic phase factor. These constituent integrals are computed by means of LU decomposition applied to a system of linear equations with a banded coefficients matrix. Example results are presented indicating that a substantial reduction in computation time may be realized by means of this approach.     

Complex polynomial phase integration

A previously published integration algorithm applicable to the numerical computation of integrals with rapidly oscillating integrands is generalized. The previous algorithm involved quadratic approximation of the phase function which was assumed to be real. The present generalization concerns approximation of a complex phase function by a polynomial of arbitrary degree. As before, the integrand is then written without approximation as a slowly varying function multiplied by the polynomial phase exponential and the slowly varying factor is approximated by a finite sum of Chebyshev polynomials. The integral is thus expressed as a sum of constituent integrals which are computed recursively via LU decomposition applied to a system of linear equations with a banded coefficients matrix. Examples are presented comparing various degree phase approximants.     

Efficient VLSI Architecture for Soft-Decision Decoding of Reed–Solomon Codes

Reed–Solomon (RS) codes have very broad applications in digital communication and storage systems. The recently developed algebraic soft-decision decoding (ASD) algorithms of RS codes can achieve substantial coding gain with polynomial complexity. Among the ASD algorithms with practical multiplicity assignment schemes, the bit-level generalized minimum distance (BGMD) decoding algorithm can achieve similar or higher coding gain with lower complexity. ASD algorithms consist of two major steps: the interpolation and the factorization. In this paper, novel architectures for both steps are proposed for the BGMD decoder. The interpolation architecture is based on the newly proposed Lee-O'Sullivan (LO) algorithm. By exploiting the characteristics of the LO algorithm and the multiplicity assignment scheme in the BGMD decoder, the proposed interpolation architecture for a (255, 239) RS code can achieve 25% higher efficiency in terms of speed/area ratio than prior efforts. Root computation over finite fields and polynomial updating are the two main steps of the factorization. A low-latency and prediction-free scheme is introduced in this paper for the root computation in the BGMD decoder. In addition, novel coefficient storage schemes and parallel processing architectures are developed to reduce the latency of the polynomial updating. The proposed factorization architecture is 126% more efficient than the previous direct root computation factorization architecture.      

Further Exploring the Strength of Prediction in the Factorization of Soft-Decision Reed–Solomon Decoding

Reed-Solomon (RS) codes are among the most widely utilized error-correcting codes in digital communication and storage systems. Among the decoding algorithms of RS codes, the recently developed Koetter-Vardy (KV) soft-decision decoding algorithm can achieve substantial coding gain, while has a polynomial complexity. One of the major steps of the KV algorithm is the factorization. Each iteration of the factorization mainly consists of root computations over finite fields and polynomial updating. To speed up the factorization step, a fast factorization architecture has been proposed to circumvent the exhaustive-search-based root computation from the second iteration level by using a root-order prediction scheme. Based on this scheme, a partial parallel factorization architecture was proposed to combine the polynomial updating in adjacent iteration levels. However, in both of these architectures, the root computation in the first iteration level is still carried out by exhaustive search, which accounts for a significant part of the overall factorization latency. In this paper, a novel iterative prediction scheme is proposed for the root computation in the first iteration level. The proposed scheme can substantially reduce the latency of the factorization, while only incurs negligible area overhead. Applying this scheme to a (255, 239) RS code, speedups of 36% and 46% can be achieved over the fast factorization and partial parallel factorization architectures, respectively.     

基于广义切比雪夫多项式的身份基加密体制安全性分析

Chebyshev polynomials are used as a reservoir for generating intricate classes of symmetrical and chaotic patterns, and have been used in a vast amount of applications. Using extended Chebyshev polynomial over finite field Zp , Algehawi and Samsudin presented recently an Identity Based Encryption (IBE) scheme. In this paper, we showed their proposal is not as secure as they claimed. More specifically, we presented a concrete attack on the scheme of Algehawi and Samsudin, which indicated the scheme cannot be consolidated as a real alternative of IBE schemes since one can exploit the semi group property (bilinearity) of extended Chebyshev polynomials over Zp to implement the attack without any difficulty.     

Solving sparse linear equations over finite fields

A "coordinate recurrence" method for solving sparse systems of linear equations over finite fields is described. The algorithms discussed all requireO(n_{1}(omega + n_{1})log^{k}n_{1})field operations, wheren_{1}is the maximum dimension of the coefficient matrix,omegais approximately the number of field operations required to apply the matrix to a test vector, and the value ofkdepends on the algorithm. A probabilistic algorithm is shown to exist for finding the determinant of a square matrix. Also, probabilistic algorithms are shown to exist for finding the minimum polynomial and rank with some arbitrarily small possibility of error.     

Almost Equiripple Low-Pass FIR Filters

An approximation of the linear phase almost equiripple low-pass finite impulse response filter is introduced. The frequency response of an almost equiripple low-pass finite impulse response filter closely approaches the frequency response of an optimal equiripple low-pass finite impulse response filter in the Chebyshev sense. The presented approximation is based on the generating polynomial. Despite that the generating polynomial has no iso-extremal behavior, it is related to the class of iso-extremal polynomials. The zero phase transfer function of an almost equiripple low-pass finite impulse response filter follows from the generating polynomial. The closed form solution for the direct algebraic computation of the impulse response of the filter has been developed on the basis of generalization of the differential equation suitable for the half-band specifications. No numerical procedures are involved. The practical design procedure based on the developed approximation is presented. For illustration of the design procedure one example of the design is included here.     

On decoding of both errors and erasures of a Reed-Solomon codeusing an inverse-free Berlekamp-Massey algorithm

In a previous article by Truong et al. (see ibid., vol.46, p.973-76, 1998), it was shown that an inverse-free Berlekamp-Massey (1968, 1969) algorithm can be generalized to find the error locator polynomial in a Reed-Solomon (RS) decoder for correcting errors as well as erasures. The basic idea of this procedure is the replacement of the initial condition of an inverse-free BM algorithm by the Forney (1965) syndromes. It is shown that the errata locator polynomial can be obtained directly by initializing an inverse-free BM algorithm with the erasure locator polynomial and the syndromes. An important ingredient of this new algorithm is a modified BM algorithm for computing the errata locator polynomial. As a consequence, the separate computation of the erasure locator polynomial and the Forney syndrome, needed in the decoder developed by Truong et al., are completely avoided in this modification of the BM algorithm. This modified algorithm requires fewer finite field addition and multiplication operations than the previous algorithm. Finally, the new decoding method was implemented on a computer using C++ language. It is shown in a simulation that the speed of this new decoder is faster than the decoder developed by Truong et al. An example using this program is given for an (255, 239) RS code for correcting errors and erasures with 2ν+s⩽10     

On the computation of the inverse of a two-variable polynomial matrix by interpolation

Two interpolation algorithms are presented for the computation of the inverse of a two variable polynomial matrix. The first interpolation algorithm, is based on the Lagrange interpolation method that matches pre-assigned data of the determinant and the adjoint of a two-variable polynomial matrix, on a set of points on several circles centered at the origin. The second interpolation algorithm is using discrete fourier transforms (DFT) techniques or better fast fourier transforms which are very efficient algorithms available both in software and hardware and that they are greatly benefitted by the existence of a parallel environment (through symmetric multiprocessing or other techniques). The complexity of both algorithms is discussed and illustrated examples are given. The DFT-algorithm is implemented in the Mathematica programming language and tested in comparison to the respective built-in function of Mathematica.     

Synthèse des filtres numériques non récursifs à phase linéaire et coefficients de longueur finie

This paper presents some different methods for the design of finite impulse response linear phase digital filters with finite wordlength coefficients. An approximation problem with discrete variables is stated for which we search a solution in a Chebyshev sense. The optimal algorithm proposed associates the Remez algorithm and a branch and bound technique (BaB). The use of this kind of algorithm may sometimes lead to relatively important computer time, so two local search algorithms are also considered. The application of these algorithms with or without constraints is illustrated by examples.     

Faster Algorithms for Construction of Recovery Trees Enhancing QoP and QoS

Medard et al. proposed an elegant recovery scheme (known as the MFBG scheme) using red/blue recovery trees for multicast path protection against single link or node failures. Xue et al. extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric for multifailure recovery capabilities of single failure recovery schemes. They also presented polynomial time algorithms to construct recovery trees with good QoP and quality of service (QoS). In this paper, we present faster algorithms for constructing recovery trees with good QoP and QoS performance. For QoP enhancement, our O(n + m) time algorithm has comparable performance with the previously best O(n²(n + m)) time algorithm, where n and m denote the number of nodes and the number of links in the network, respectively. For cost reduction, our O(n + m) time algorithms have comparable performance with the previously best O(n²(n + m)) time algorithms. For bottleneck bandwidth maximization, our O(m log n) time algorithms improve the previously best O(nm) time algorithms. Simulation results show that our algorithms significantly outperform previously known algorithms in terms of running time, with comparable QoP or QoS performance.     

不确定型模糊Kripke结构的计算树逻辑模型检测

本文研究了不确定型模糊Kripke结构的计算树逻辑的模型检测问题,并说明了该问题可以在对数多形式时间内解决.首先给出了不确定型模糊Kripke结构的定义,引入了模糊计算树逻辑的语法和语义.为了刻画存在量词∃和任意量词∀在不确定型模糊Kripke结构中的两种语义解释,在模糊计算树逻辑语法中引入了路径量词∃_sup,∃_inf和∀_sup,∀_inf,分别用于替换存在量词∃和任意量词∀.其次讨论了基于不确定型模糊Kripke结构的计算树逻辑模型检测算法,特别地对于模糊计算树逻辑公式∃_suppUq,∀_suppUq,∃_infpUq和∀_infpUq分别给出时间复杂度为对数多项式时间的改进算法.     

A new structured design method for convolutions over finite fields, Part I

The structure of bilinear cyclic convolution algorithms is explored over finite fields. The algorithms derived are valid for any length not divisible by the field characteristic and are based upon the small length polynomial multiplication algorithms. The multiplicative complexity of these algorithms is small and depends on the field of constants. The linear transformation matricesA, B(premultiplication), andC(postmultiplication) defining the algorithm have block structures which are related to one another. The rows ofAandBand the columns ofCare maximal length recurrent sequences. Because of the highly regular structure ofA, B, andC, the algorithms can be very easily designed even for large lengths. The application of these algorithms to the decoding of Reed-Solomon codes is also examined.     

A fast finite difference method for propagation predictions overirregular, inhomogeneous terrain

Propagation of electromagnetic waves over irregular, inhomogeneous terrain is solved by a finite difference scheme. The method is fast and requires considerably less memory than the integral equation methods. The method requires a storage space of order O(N) and an execution time of order O(N²). Fields generated by a TE₂ line source are represented in an integral form in terms of the field over a flat, constant impedance plane (the incident field), and the field scattered by the terrain irregularities and inhomogeneities. Accurate expressions are provided for the incident field and the Green's function, whose evaluation is otherwise accomplished by the rather time-consuming Sommerfeld's integrals. Measured equation of invariance is used to terminate the computational domain. The sparse matrix generated by the method is inverted by the Ricatti transform. Numerical results are presented for the ground wave as well as for the sky wave. Comparison is made for known geometries to establish the validity and limitations of the method     

An enhanced Gauss-Newton inversion algorithm using a dual-optimal grid approach

We developed two algorithms for solving the nonlinear electromagnetic inversion problem in the Earth. To achieve a balance between efficiency and robustness, both algorithms employ the Gauss-Newton inversion method. Moreover, to speed up the inversion's computational time, the so-called optimal grid technique is utilized. The first algorithm uses a forward solver with a very coarse optimal grid to calculate the Jacobian matrix. Hence, in this scheme we employ two different sets of optimal grids. One set is used to compute the data mismatch to be minimized and the other set is used to construct the Jacobian matrix. In the second approach we use a fixed-point iteration process where the inverse kernel is approximated on a coarse optimal grid that does not significantly compromise accuracy. The advantage of these optimal grids is that they considerably reduce the computation time without compromising accuracy. Numerical examples for two-dimensional axially symmetric and three-dimensional anisotropic configurations are used to demonstrate the advantage of using both algorithms over the standard Gauss-Newton inversion method.     

基于免疫克隆选择的最优ECOC编码输出

纠错输出编码（Error Correcting Output Codes,ECOC）是解决模式识别领域多类分类问题的有效工具。在寻找最优编码输出的问题上,现有方法忽略了样本类别之间的相关性,导致学习效率和分类效果低下。为构造数据感知的编码矩阵,提出基于免疫克隆选择（Immune Clonal Selection Algorithm,ICSA）的最优纠错输出编码方法,将矩阵构造的多约束NP（Non-deterministic Polynomial,NP）难问题转换为优化搜索问题.首先基于分类精度和编码长度定义亲合度函数,然后结合样本知识改进变异交叉算子,根据约束性条件对矩阵进行搜索,从而快速有效地构建最优ECOC编码.实验表明该方法能够在提升多类分类精度的同时加快算法效率,而且输出的编码矩阵更加紧凑.     

Approximate distributed Bellman-Ford algorithms

Routing algorithms based on the distributed Bellman-Ford algorithm (DBF) suffer from exponential message complexity in some scenarios. We propose two modifications to the algorithm which result in a polynomial message complexity without adversely affecting the response time of the algorithm. However, the new algorithms may not compute the shortest path. Instead, the paths computed can be worse than the shortest path by at most a constant factor (<3). We call these algorithms approximate DBF algorithms. The modifications proposed to the original algorithm are very simple and easy to implement. The message complexity of the first algorithm, called the multiplicative approximate DBF, is O(nmlog(nΔ)) where Δ is the maximum length over all edges of an n-nodes m-edges network. The message complexity of the second algorithm, called the additive approximate DBF, is O(δ/Δ nm) where δ is the minimum length over all edges in the network