A generalized recursive construction for de Bruijn sequences

This paper is concerned with the construction of de Bruijn sequences of spann--binary sequences of period2^{n}in which every binaryn-tuple appears as somenconsecutive terms in one period of the sequence. Constructions in the literature are based on maximum length linear sequences, algorithms which start from scratch, and recursive methods which start with a single de Bruijn sequence of spannand produce one of spann+1. We give a more general recursive construction which takes two de Brnijn sequences of spannand produces a de Bruijn sequence of spann+1. In addition, for a special case of the construction, the complexity (shortest linear recursion that generates the sequence) of the resulting sequence is determined in terms of the complexities of the ingredient sequences. In particular, de Bruijn sequences of spann+1with maximum complexity2^{(n+1)}-1are obtained from maximum complexity sequences of spann. Reverse-complementary de Bruijn sequences are also considered.     

Equivalence of propagation characteristics for thetransmission-line matrix and finite-difference time-domain methods intwo dimensions

The equivalence of propagation characteristics for the transmission line matrix (TLM) and finite-difference-time-domain (FD-TD) methods in two dimensions is discussed. A propagation analysis of a TLM shunt node complete with permittivity and loss stubs and a dispersion analysis of the two-dimensional FD-TD method in an arbitrary medium are performed and yield dispersion relations. The relations are identical when the FD-TD method is operated at the upper limit of its stability range     

A recursive variance-reduction algorithm for estimatingcommunication-network reliability

In evaluating the capacity of a communication network architecture to resist possible faults of some of its components, several reliability metrics are used. This paper considers the 𝒦-terminal unreliability measure. The exact evaluation of this parameter is, in general, very costly since it is in the NP-hard family. An alternative to exact evaluation is to estimate it using Monte Carlo simulation. For highly reliable networks, the crude Monte Carlo technique is prohibitively expensive; thus variance reduction techniques must be used. We propose a recursive variance-reduction Monte-Carlo scheme (RVR-MC) specifically designed for this problem, RVR-MC is recursive, changing the original problem into the unreliability evaluation problem for smaller networks. When all resulting systems are either up or down independently of components state, the process terminates. Simulation results are given for a well-known test topology. The speedups obtained by RVR-MC with respect to crude Monte Carlo are calculated for various values of component unreliability. These results are compared to previously published results for five other methods (bounds, sequential construction, dagger sampling, failure sets, and merge process) showing the value of RVR-MC     

A sequential regression algorithm for recursive filters

A sequential regression (s.e.r.) algorithm is derived for recursive or infinite impulse response (i.i.r.) adaptive filters. Results pertaining to using the algorithm in a system-identification experiment are also included.     

A recursive link adaptation algorithm for MIMO systems

An algorithm to adjust the coding/modulation (CM) scheme in a multiple-input multiple-output (MIMO) wireless communication system is proposed and analysed. The CM scheme selected for each transmitter is determined by a recursive procedure at the receiver, taking into account estimated signal-to-noise ratio and the properties of available CM schemes. The algorithm performance was tested with different detection algorithms: pseudo-inverse (PINV), V-BLAST and maximum likelihood (ML).     

A recursive algorithm for computing Cramer-Rao-type bounds onestimator covariance

We give a recursive algorithm to calculate submatrices of the Cramer-Rao (CR) matrix bound on the covariance of any unbiased estimator of a vector parameter &thetas;_. Our algorithm computes a sequence of lower bounds that converges monotonically to the CR bound with exponential speed of convergence. The recursive algorithm uses an invertible “splitting matrix” to successively approximate the inverse Fisher information matrix. We present a statistical approach to selecting the splitting matrix based on a “complete-data-incomplete-data” formulation similar to that of the well-known EM parameter estimation algorithm. As a concrete illustration we consider image reconstruction from projections for emission computed tomography     

A robust recursive least squares algorithm

A new algorithm is developed, which guarantees the normalized bias in the weight vector due to persistent and bounded data perturbations to be bounded. Robustness analysis for this algorithm has been presented. An approximate recursive implementation is also proposed. It is termed as the robust recursive least squares (RRLS) algorithm since it resembles the RLS algorithm in its structure and is robust with respect to persistent bounded data perturbation. Simulation results are presented to illustrate the efficacy of the RRLS algorithm     

A recursive maximum likelihood algorithm for ARMA spectral estimation

A spectral estimation technique is presented for autoregressive moving-average (ARMA) processes. The technique is based on a parameter estimation technique known as the rec ursive maximum likelihood (RML) method. The recursive spectral estimation algorithm is presented and its asymptotic properties are discussed. Simulation results are presented to illustrate the performance of the estimator for various types of data.     

A generalized algorithm for evaluating distributed-programreliability

A one-step algorithm, GEAR (generalized evaluation algorithm for reliability), is introduced that computes the reliability of a distributed computing system (DCS), which usually consists of processing element, memory unit, input/output devices, data-files, and programs as its shared resources. The probability that a task or an application can be computed successfully by sharing the required resources on the DCS is termed the system reliability. Some of the important reliabilities defined using the above concept are discussed, including terminal-pair, computer-network, distributed-program, and distributed-system. GEAR is general enough to compute all four of these parameters, and does not require any prior knowledge about multiterminal connections for computing reliability expression. Many examples are included to illustrate the usefulness of GEAR for computing reliability measures of a DCS     

A recursive linear detection algorithm for asynchronous CDMAcommunication system

A recursive linear detection algorithm is proposed for the detection of signals from an asynchronous direct-sequence code-division multiple-access (DS-CDMA) communication system. This algorithm works for short as well as long codes. Under some reasonable conditions, this algorithm is proved to be stable and converges to the ideal decorrelating detector (IDD) with a sufficiently large memory length. The performance of the algorithm is analyzed in some detail. Upper and lower bounds for the bit-error probabilities are developed. It is demonstrated that the two bounds converge to the bit-error probabilities of the IDD as the large memory length increases. Simulation results show that the recursive detector proposed outperforms the truncated decorrelating detector with less memory and less computational complexity     

A gradient algorithm for center-frequency adaptive recursive bandpass filters

Mean-square output of a center-frequency variable bandpass filter is employed as the performance criterion to make the filter self-adjusting to the center frequency of the input signal. A gradient ascending algorithm is proposed to update the center-frequency-dependent coefficients of the filter to maximize the performance function.     

A 2-D recursive inverse adaptive algorithm

In this paper, a 2-D form of the recently proposed recursive inverse (RI) adaptive algorithm is introduced. The filter coefficients can be updated along both the horizontal and vertical directions on a 2-D plane. The proposed approach uses a variable step size and avoids the use of the inverse autocorrelation matrix in the coefficient update equation, which leads to an improved and more stable performance. Performance of the 2-D RI algorithm is compared to that of the 2-D RLS algorithm in an image deconvolution and an adaptive line enhancer problem settings. The simulation results show that the proposed 2-D RI algorithm leads to an improved performance compared to that of the 2-D RLS algorithm.     

一种快速递归全局最小二乘算法

针对FIR系统输入和输出信号均被噪声干扰的情况,提出一种快速递归全局最小二乘(XS-RTLS)算法用于迭代计算全局最小二乘解,算法沿着输入数据的符号方向并采用著名的快速增益矢量,搜索约束瑞利商(c-RQ)的最小值得到系统参数估计。算法关于方向更新矢量的内积运算可通过加减运算实现,有效降低了计算复杂度;另外XS-RTLS算法没有进行相关矩阵求逆递归运算,因而具有长期稳定性,算法的全局收敛性通过Laslle不变性原理得到证明。最后通过仿真比较了XS-RTLS算法和递归最小二乘(RLS)算法在非时变系统和时变系统中的性能,验证了XS-RTLS算法的长期稳定性。     

A recursive algorithm for the error probability evaluation of M-QAM

A general recursive algorithm for the efficient and accurate computation of the bit error rate (BER) of square-shaped M-QAM constellations over additive white Gaussian noise (AWGN) channels is derived. We take advantage of the relationship amongst different square-shaped M-QAM constellations using Gray coded bit mapping     

A unified fast recursive algorithm for data shuffling in variousorders

Data shuffling in a particular order is frequently required in signal processing applications. The authors present fast recursive algorithms, of order O(N), for shuffling a data sequence in various orders, e.g. bit reversed, Gray code, and other related orders, under a unified framework. These algorithms are computationally efficient in that every permutation index is essentially computed by a single logical or arithmetic operation between a previous index and a proper offset. The proposed algorithms can be used for the fast Fourier transform, fast Hartley transform, and mutual conversion among three typical forms of the Walsh transform     

A generalized Euclidean algorithm for multisequence shift-registersynthesis

The problem of finding a linear-feedback shift register of shortest length capable of generating prescribed multiple sequences is considered. A generalized Euclidean algorithm, which is based on a generalized polynomial division algorithm, is presented. A necessary and sufficient condition for the uniqueness of the solution is given. When the solution is not unique, the set of all possible solutions is also derived. It is shown that the algorithm can be applied to the decoding of many cyclic codes for which multiple syndrome sequences are available. When it is applied to the case of a single sequence, the algorithm reduces to that introduced by Y. Sugiyama et al. (Inf. Control, vol.27, p.87-9, Feb. 1975) in the decoding of BCH codes     

A spectral recursive transformation method for electromagneticwaves in generalized anisotropic layered media

A transition-matrix method is commonly used to deal with the problems of plane wave scattering from and the Green's function for multilayered generalized anisotropic media. The boundary conditions at the source interfaces are matched numerically. This method, although rigorous analytically, causes numerical singularities in the matrix inversion when the spectral fields are highly attenuating. A recursive variable transformation method is developed to deal with the exponentially growing or decaying terms associated with the spectral matrix method. The proposed scheme is suitable for numerical analysis of generalized anisotropic layers including uniaxial and biaxial materials, biased ferrites, magnetoplasmas, chiral and bi-anisotropic materials without increasing computer time. Applications of the recursive method are highlighted through examples of radiation and scattering from a three-layer ferrite structure and a conductor-backed magnetoplasma layer     

One-multiplier adaptive lattice algorithm for recursive filters

The formulation of one-multiplier lattice structures of the Gray-Markel type forinfinite impulse response filters is reviewed. Several special cases of this formulation — including the well-known Gray-Markel normalized lattice—are presented as scaled polynomial versions of the two-multiplier lattice. A new adaptive algorithm is presented for updating the parameters of one-multiplier lattice structured recursive filters. The LMS-based algorithm requires fewer computations than earlier reported algorithms [1]–[4].The research reported here was conducted with funds administered by the Naval Postgraduate School research council.     

The recursive suppression algorithm for adaptive superresolution

The recursive suppression algorithm is an adaptive algorithm that is one of the simplest superresolution algorithms to implement but, nevertheless, converges approximately as rapidly as the computationally intensive MUSIC algorithm. Simulation results verify the effectiveness of this algorithm in resolving closely spaced signals. Necessary and sufficient conditions for the convergence of the mean weight vector in the recursive suppression algorithm are derived     

A square root covariance algorithm for constrained recursive least squares estimation

In this contribution, a covariance counterpart is described of the information matrix approach to constrained recursive least squares estimation. Unlike information-type algorithms, covariance algorithms are amenable to parallel implementation, e.g., on processor arrays, and this is also demonstrated. As compared to previously described combined covariance-information algorithms/arrays, the present implementation avoids a doubling of the hardware requirement, and therefore constitutes a significant improvement over these combined implementations as well.