Signal space diversity: a power- and bandwidth-efficient diversitytechnique for the Rayleigh fading channel

The increasing need for high data-rate transmissions over time- or frequency-selective fading channels has drawn attention to modulation schemes with high spectral efficiency such as QAM. With the aim of increasing the “diversity order” of the signal set we consider multidimensional rotated QAM constellations. Very high diversity orders can be achieved and this results in an almost Gaussian performance over the fading channel, This multidimensional modulation scheme is essentially uncoded and enables one to trade diversity for system complexity, at no power or bandwidth expense     

Optimal Volterra kernel estimation algorithms for a nonlinearcommunication system for PSK and QAM inputs

A fifth-order Volterra kernel estimation algorithm, which is optimal in the least mean square error sense, for a bandpass nonlinear system is derived. The algorithm is based on some characteristics of i.i.d. circularly symmetric zero-mean complex-valued Gaussian random variables. The proposed algorithm can be used to identify a nonlinear system under uniformly i.i.d. rectangular M-QAM input and under uniformly i.i.d. M-PSK input (M⩾4) with modest modification. The same approach has been used to derive an optimal Volterra kernel estimation algorithm up to the third order. However, in some cases, a third-order model is not of “high enough order” to capture the nonlinear system characteristics. A simulation example is given to show the necessity of deriving a fifth-order Volterra kernel estimation algorithm and to test for the correctness of the algorithm     

Instrumental variable subspace tracking using projectionapproximation

Subspace estimation plays an important role in, for example, sensor array signal processing. Recursive methods for subspace tracking with application to nonstationary environments have also drawn considerable interest. In this paper, instrumental variable (IV) extensions of the projection approximation subspace tracking (PAST) algorithm are presented. The IV approach is motivated by the fact that PAST gives biased estimates when the noise is not spatially white. The proposed algorithms are based on a projection like unconstrained criterion, with a resulting computational complexity, of 3ml+O(mn), where m is the dimension of the measurement vector; l is the dimension of the IV vector; and n is the subspace dimension. In addition, an extension to a “second order” IV algorithm is proposed, which in certain scenarios is demonstrated to have better tracking properties than the basic IV-PAST algorithms. The performance of the algorithms is demonstrated with a simulation study of a time-varying array processing scenario     

A modified block FTF adaptive algorithm with applications tounderwater target detection

In this paper, the problem of weighted block recursive least squares (RLS) adaptive filtering is formulated in the context of a block fast transversal filter (FTF) algorithm. This “modified block FTF algorithm” is derived by modifying the constrained block-LS cost function to guarantee global optimality. This new soft-constrained algorithm provides an efficient way of transferring weight information between blocks of data. The tracking ability of the algorithm can be controlled by varying the block length and/or a soft constrained parameter. This algorithm is computationally more efficient compared with other LS-based schemes. The effectiveness of this algorithm is tested on a real-life problem dealing with underwater target identification from acoustic backscatter. The process involves the identification of the presence of resonance in the acoustic backscatter from a target of unknown shape submerged in water     

Image-based virtual world generation

The methodologies introduced here generate photographically realistic 3D worlds from 2D photographic images instead of from 3D geometrical models. If we call conventional methods “algorithm intensive”, these methods are “data intensive”. Several prototype systems, including the Virtual Dome and Camera with GPS, serve as examples. Of course, both types have their advantages, so trade-offs and combinations of the two are also discussed briefly     

The generalized distributive law

We discuss a general message passing algorithm, which we call the generalized distributive law (GDL). The GDL is a synthesis of the work of many authors in information theory, digital communications, signal processing, statistics, and artificial intelligence. It includes as special cases the Baum-Welch algorithm, the fast Fourier transform (FFT) on any finite Abelian group, the Gallager-Tanner-Wiberg decoding algorithm, Viterbi's algorithm, the BCJR algorithm, Pearl's “belief propagation” algorithm, the Shafer-Shenoy probability propagation algorithm, and the turbo decoding algorithm. Although this algorithm is guaranteed to give exact answers only in certain cases (the “junction tree” condition), unfortunately not including the cases of GTW with cycles or turbo decoding, there is much experimental evidence, and a few theorems, suggesting that it often works approximately even when it is not supposed to     

A new, cellular automaton-based, nearest neighbor patternclassifier and its VLSI implementation

A new, parallel, nearest-neighbor (NN) pattern classifier, based on a 2D Cellular Automaton (CA) architecture, is presented in this paper. The proposed classifier is both time and space efficient, when compared with already existing NN classifiers, since it does not require complex distance calculations and ordering of distances, and storage requirements are kept minimal since each cell stores information only about its nearest neighborhood. The proposed classifier produces piece-wise linear discriminant curves between clusters of points of complex shape (nonlinearly separable) using the computational geometry concept known as the Voronoi diagram, which is established through CA evolution. These curves are established during an “off-line” operation and, thus, the subsequent classification of unknown patterns is achieved very fast. The VLSI design and implementation of a nearest neighborhood processor of the proposed 2D CA architecture is also presented in this paper     

An efficient algorithm for cyclic convolution based on fast-polynomial and fast-W transforms

This paper first presents a fastW-transform (FWT) algorithm for computing one-dimensional cyclic and skew-cyclic convolutions. By using this FWT in conjunction with the fast polynomial transform (FPT), an efficient algorithm is then proposed for calculating the two-dimensional cyclic convolution (2D CC). Compared to the conventional row-column 2D discrete Fourier transform algorithm or the FPT Fast Fourier transform algorithm for 2D CC, the proposed algorithm achieves 65% or 40% savings in the number of multiplications, respectively. The number of additions required is also reduced considerably.     

基于平均方差和邻域信息的改进型二维Otsu算法

针对传统二维Otsu算法忽略边界信息对图像分割结果有一定影响、计算时间长的问题,研究提出了一种基于平均方差和邻域信息的改进型算法。新算法先利用中值滤波来重新构建一个二维直方图,再用平均方差定义一个新的二维阈值选取函数,最后对图像进行二值化处理。实验结果表明,与传统二维Otsu法及其快速递推算法相比,新算法有效提高了分割精度,减少了算法的运行时间,其运行时间仅为传统二维Otsu算法的1.55%,大约是快速递推算法的40.69%。     

Automatic generation of fast discrete signal transforms

This paper presents an algorithm that derives fast versions for a broad class of discrete signal transforms symbolically. The class includes but is not limited to the discrete Fourier and the discrete trigonometric transforms. This is achieved by finding fast sparse matrix factorizations for the matrix representations of these transforms. Unlike previous methods, the algorithm is entirely automatic and uses the defining matrix as its sole input. The sparse matrix factorization algorithm consists of two steps: first, the “symmetry” of the matrix is computed in the form of a pair of group representations; second, the representations are stepwise decomposed, giving rise to a sparse factorization of the original transform matrix. We have successfully demonstrated the method by computing automatically efficient transforms in several important cases: for the DFT, we obtain the Cooley-Tukey (1965) FFT; for a class of transforms including the DCT, type II, the number of arithmetic operations for our fast transforms is the same as for the best-known algorithms. Our approach provides new insights and interpretations for the structure of these signal transforms and the question of why fast algorithms exist. The sparse matrix factorization algorithm is implemented within the software package AREP     

快速置乱耦合3D混沌映射的图像加密算法研究

针对当前3D混沌映射加密算法的安全性不高,且其置乱过程的计算量大,置乱性不稳定,以及置乱方法不具有通用性等缺陷,设计了一种快速通用置乱方法,并将混淆与扩散机制同时引入进来,提出了一种新的3D混沌映射图像加密算法。首先利用快速置乱方法置乱初始图像,以改变像素位置;利用三维Chen系统结合像素值变换函数所生成初始外部密钥迭代3D混沌映射,得到一个序列,该序列根据混淆机制对置乱图像像素值进行混淆;改变外部密钥,再迭代计算3D混沌映射,得到三元一维伪随机数组,并借助密钥流机制量化该数组,得到新序列,利用该新序列根据扩散机制对混淆后的像素进行扩散处理。借助MATLAB仿真软件对该算法及其他3D算法进行对比仿真。结果显示:与其他3D算法相比,该算法安全性更高,置乱速度更快,计算效率更高,且其密钥空间巨大。     

Factor graphs and the sum-product algorithm

Algorithms that must deal with complicated global functions of many variables often exploit the manner in which the given functions factor as a product of “local” functions, each of which depends on a subset of the variables. Such a factorization can be visualized with a bipartite graph that we call a factor graph, In this tutorial paper, we present a generic message-passing algorithm, the sum-product algorithm, that operates in a factor graph. Following a single, simple computational rule, the sum-product algorithm computes-either exactly or approximately-various marginal functions derived from the global function. A wide variety of algorithms developed in artificial intelligence, signal processing, and digital communications can be derived as specific instances of the sum-product algorithm, including the forward/backward algorithm, the Viterbi algorithm, the iterative “turbo” decoding algorithm, Pearl's (1988) belief propagation algorithm for Bayesian networks, the Kalman filter, and certain fast Fourier transform (FFT) algorithms     

Fast sequential implementation of “neural-gas” networkfor vector quantization

Although the “neural-gas” network proposed by Martinetz et al. in 1993 has been proven for its optimality in vector quantizer design and has been demonstrated to have good performance in time-series prediction, its high computational complexity (NlogN) makes it a slow sequential algorithm. We suggest two ideas to speedup its sequential realization: (1) using a truncated exponential function as its neighborhood function and (2) applying a new extension of the partial distance elimination method (PDE). This fast realization is compared with the original version of the neural-gas network for codebook design in image vector quantization. The comparison indicates that a speedup of five times is possible, while the quality of the resulting codebook is almost the same as that of the straightforward realization     

Minimum interference routing of bandwidth guaranteed tunnels withMPLS traffic engineering applications

This paper presents new algorithms for dynamic routing of bandwidth guaranteed tunnels, where tunnel routing requests arrive one by one and there is no a priori knowledge regarding future requests. This problem is motivated by the service provider needs for fast deployment of bandwidth guaranteed services. Offline routing algorithms cannot be used since they require a priori knowledge of all tunnel requests that are to be rooted. Instead, on-line algorithms that handle requests arriving one by one and that satisfy as many potential future demands as possible are needed. The newly developed algorithms are on-line algorithms and are based on the idea that a newly routed tunnel must follow a route that does not “interfere too much” with a route that may he critical to satisfy a future demand. We show that this problem is NP-hard. We then develop path selection heuristics which are based on the idea of deferred loading of certain “critical” links. These critical links are identified by the algorithm as links that, if heavily loaded, would make it impossible to satisfy future demands between certain ingress-egress pairs. Like min-hop routing, the presented algorithm uses link-state information and some auxiliary capacity information for path selection. Unlike previous algorithms, the proposed algorithm exploits any available knowledge of the network ingress-egress points of potential future demands, even though the demands themselves are unknown. If all nodes are ingress-egress nodes, the algorithm can still be used, particularly to reduce the rejection rate of requests between a specified subset of important ingress-egress pairs. The algorithm performs well in comparison to previously proposed algorithms on several metrics like the number of rejected demands and successful rerouting of demands upon link failure     

基于子集划分的素长度二维DCT快速算法

该文针对素长度类型的2维离散余弦变换(DCT)变换,提出一种子集划分准则,并根据该准则将2维DCT变换输出的频域数据集合划分为若干个互不相交子集;将对频域的计算转换为对2(N－1)个N点1维素数尺寸DCT的奇系数或偶系数的计算;最后给出了该算法的乘法复杂度和加法运算复杂度。相对于行列分解法,该算法节省了约一半的乘法次数,省略了数据的转置存储过程,而加法的运算复杂度基本维持不变。     

A new key generation method for frequency-domain speech scramblers

This paper describes a method which uses “derangement” permutations as scrambling keys in a frequency-domain speech scrambling system. Subjective tests based on the number test confirm that such keys produce scrambled speech with virtually no residual intelligibility. A new derangement generation algorithm is introduced for key generation. This algorithm maps each integer g, in the range of 0⩽g<(n-1)!, to a distinct derangement of 2 elements,     

基于多维指派算法的被动多目标跟踪方案

该文针对无源测向交叉定位系统提出了基于多维指派算法的被动多目标跟踪方案。该方案是将三维空间的基准线最小代价算法与动态2D指派算法相结合。该方案的特点是：三维空间的基准线最小代价算法是一种快速数据关联算法,它能够快速削减候选关联集合并简化关联代价的计算,完成航迹起始任务;动态2D指派算法则能够简单而准确地实现观测与航迹的关联。仿真结果证明该方案可以有效地完成无源测向交叉定位系统中的多目标跟踪任务。     

The sliding-window Lempel-Ziv algorithm is asymptotically optimal

The sliding-window version of the Lempel-Ziv data-compression algorithm (sometimes called LZ '77) has been thrust into prominence recently. A version of this algorithm is used in the highly successful “Stacker” program for personal computers. If is also incorporated into Microsoft's new MS-DOS-6. Although other versions of the Lempel-Ziv algorithm are known to he optimal in the sense that they compress a data source to its entropy, optimality in this sense has never been demonstrated for this version. In this self-contained paper, we will describe the algorithm, and show that as the “window size,“ a quantity which is related to the memory and complexity of the procedure, goes to infinity, the compression rate approaches the source entropy. The proof is surprisingly general, applying to all finite-alphabet stationary ergodic sources     

Image restoration using a conjugate gradient-based adaptive filtering algorithm

A new two-dimensional (2D) sample-based conjugate gradient (SCG) algorithm is developed for adaptive filtering. This algorithm is based on the conjugate gradient method of optimization and therefore has a fast convergence characteristic. The SCG is computationally simpler than the recursive least squares (RLS) algorithm. The SCG algorithm with the equation-error and output-error methods is investigated for application in image restoration. Simulation results show that the new algorithm significantly outperforms existing algorithms in the restoration of noisy images.This work was supported in part by a grant from the Colorado Advanced Software Institute.     

Differential trellis decoding of convolutional codes

This paper investigates the principle of metric differences for trellis decoding of convolutional codes. Based on this differential method, a new algorithm, referred to as differential trellis decoding (DTD), is proposed. DTD offers an alternative to the conventional “add-compare-select” (ACS) method for implementing the Viterbi algorithm