A Fast Algorithm for Sorting and Counting Third-Order Intermodulation Products

This paper presents a fast algorithm that performs a selective counting of the third-order intermodulation products generated when several carriers of various types are transmitted through a common nonlinear device. In deriving the algorithm, the carrier configuration and the frequency distribution of intermodulation products are both described by polynomials which are related to each other. The frequency distributions of third-order intermodulation products of the various kinds are then obtained with the aid of an FFT algorithm and a numerical method for solving a set of linear equations. When compared to a direct counting procedure, the proposed algorithm has presented a drastic reduction on the required Computational effort. This advantage is particularly important when the number of carriers sharing the nonlinearity is large. In an example with 1366 carriers of three different types sharing the nonlinearity, the CPU time was reduced from 7 h 46 min. down to 52 s.     

Simple method for intermodulation products counting in multicarrier systems

This paper presents a novel algorithm for intermodulation products counting in multicarrier systems. Intermodulation products are caused by the nonlinearity of the amplifiers’ transfer characteristic. Along the transmission network, broadband amplifiers are needed to boost up the signal level and compensate the signal attenuation. When the number of carriers increases, the number of intermodulation products also increases extremely fast. In our approach, selective counting procedure by grouping intermodulation products was introduced. The presented solution shows considerable reduction in computational effort in counting the number of intermodulation products in the individual channel, especially if the number of products is very large.     

基于数据结构的选择排序算法剖析与改进

排序在数据处理中起着非常重要的作用。选择排序算法是数据结构中的一种基本的排序算法,运用极其广泛。这里对基本选择排序的算法进行剖析,继而提出一种改进的思路,形成改进型的选择排序。其特点是在比较的过程中将被交换数据的下标进行保存,在选择下一个目标时只需在最后一次交换的位置与待排纪录之间进行,从而大大地减少了比较的次数。从时间复杂度、空间复杂度与稳定性进行比较,体现出其优越性能。     

Adaptive Resource Reuse Scheduling for Multihop Relay Wireless Network Based on Multicoloring

In this paper, an adaptive resource reuse scheduling (ARRS) algorithm is presented with the goal of enhancing the system capacity for relay networks, which supports arbitrary topology and relay stations (RSs) mobility. Since one key step in ARRS is modeled as graph multicoloring, a fast [%p-]- approximation algorithm named dual sorting greedy (DSG) is provided for the problem. Simulation results show that ARRS achieves high system capacity and hence satisfies the multimedia service QoS requirements of relay networks efficiently.     

An Efficient VLSI Architecture for Nonbinary LDPC Decoders

Low-density parity-check (LDPC) codes constructed over the Galois field $ hbox{GF}(q)$, which are also called nonbinary LDPC codes, are an extension of binary LDPC codes with significantly better performance. Although various kinds of low-complexity quasi-optimal iterative decoding algorithms have been proposed, the VLSI implementation of nonbinary LDPC decoders has rarely been discussed due to their hardware unfriendly properties. In this brief, an efficient selective computation algorithm, which totally avoids the sorting process, is proposed for Min–Max decoding. In addition, an efficient VLSI architecture for a nonbinary Min–Max decoder is presented. The synthesis results are given to demonstrate the efficiency of the proposed techniques.      

激光分拣系统的设计和改进

相机分拣机常用于食品和非食品分拣,如炸薯条、虾、蔬菜、小吃、棉花、塑料等。但有些看不见的异物(如玻璃)或与产品颜色相同的异物是无法由相机检测到的。而激光扫描系统则可用于检测与产品颜色相同的异物。设计和改进了基于选择性吸收原理的激光分选系统,并对系统进行了高速信号采样实验以及成像实验。在信号采样实验中,系统可以通过选择性吸收分选技术有效识别产品和异物。在成像实验中,选择报纸的标题作为成像样图,调整扫描光斑直径接近0.35 mm,扫描后的数据经由计算机程序转码并成像。实验成像的分辨率为18043 pixel。成像结果表明,系统可以有效地识别1.5 mm 的异物。最后对光学扫描系统进行了分析,发现部分的光信号损失于扫描光的非垂直入射,于是提出了曲线扫描分拣结构用以改进传统分拣系统。     

基于内存优化的小波零块嵌入图像编码算法

小波嵌入零块编码算法(Set Partitioned Embedded bloCK,SPECK)是一种高效的具有渐进传输特性的图像编码算法,但其在编解码过程中的巨大内存占用致使编解码速度慢且不利于硬件实现.本文提出了一种基于内存优化的小波零块嵌入图像编码算法,采用标志状态图和块深度优先搜索策略完成嵌入编码中的排序和细化过程.两张标志状态图分别标识编解码过程中的重要系数和不重要集合,同时结合块深度优先搜索策略检索块结构中的不重要集合,代替排序和细化过程中的重要系数链表和不重要集合链表,较大地节省了内存占用.实验结果表明,与SPECK算法相比,在保持相当信噪比的情况下,内存占用仅为原来的1/12,与另一种低内存零树编码算法LZC(Listless Zerotree Coding)相比,在内存略有增加的情况下,信噪比至少提高1.1dB,为硬件实现小波零块编码算法探讨了一条有效途径.     

An ASIC design and formal analysis of a novel pipelined and parallel sorting accelerator

Sorting, which is widely used in different areas such as database systems, IP routing, bio informatics, and cognitive-processing-based applications, imposes considerable overhead on computing resources. Therefore, an efficient on-chip sorting accelerator may significantly enhance real-time decision-making in such applications. In this paper we introduce a novel pipelined and parallel sorting algorithm with streaming I/O, with the time, logic, and memory complexity of O(n), , and O(n), respectively. We present a formal analysis to prove the correctness of this algorithm. We then model, verify, and synthesize this unconditional algorithm (in the TSMC 0.13 micron technology) for 4k-word clusters as an ASIC accelerating engine. More specifically, our implementation with 3969-word multiple-bank memory, 63 word-size comparators, 64 word-size multiplexers, and 63 word-size registers only requires some 8k clock cycles to sort an arbitrary 3969-word long array of random data, which arrive at the sorter and also depart it one item at a time.     

Cellular Automata Algorithms for String Sorting and Integer Multiplication According to the Atrubin Scheme

Being unavailable in the literature for the past few recent decades, the cellular automata formulations of some algorithms for sorting character and string arrays are considered here. A cellular automaton multiplying two integers written in a numeral system with an arbitrary basis is proposed for the first time. The algorithm is based on the Atrubin parallel multiplication scheme for a systolic array of processors and requires four components (registers) instead of five.     

Tanner graphs for group block codes and lattices: construction andcomplexity

We develop a Tanner graph (TG) construction for an Abelian group block code L with arbitrary alphabets at different coordinates, an important application of which is the representation of the label code of a lattice. The construction is based on the modular linear constraints imposed on the code symbols by a set of generators for the dual code L*. As a necessary step toward the construction of a TG for L we devise an efficient algorithm for finding a generating set for L*. In the process, we develop a construction for lattices based on an arbitrary Abelian group block code, called generalized Construction A (GCA), and explore relationships among a group code, its GCA lattice, and their duals. We also study the problem of finding low-complexity TGs for Abelian group block codes and lattices; and derive tight lower bounds on the label-code complexity of lattices. It is shown that for many important lattices, the minimal label codes which achieve the lower bounds cannot be supported by cycle-free Tanner graphs     

High-performance VLSI architecture for the Viterbi algorithm

The Viterbi (1967) algorithm (VA) is known to be an efficient method for the realization of maximum-likelihood (ML) decoding of convolutional codes. The VA is characterized by a graph, called a trellis, which defines the transitions between states. To define an area efficient architecture for the VA is equivalent to obtaining an efficient mapping of the trellis. We present a methodology that permits the efficient hardware mapping of the VA onto a processor network of arbitrary size. This formal model is employed for the partitioning of the computations among an arbitrary number of processors in such a way that the data are recirculated, optimizing the use of the PEs and the communications. Therefore, the algorithm is mapped onto a column of processing elements and an optimal design solution is obtained for a particular set of area and/or speed constraints. Furthermore, the management of the surviving path memory for its mapping and distribution among the processors was studied. As a result, we obtain a regular and modular design appropriate for its VLSI implementation in which the only necessary communications between processors are the data recirculations between stages     

一种中值滤波的快速算法

在信号处理中,大多数中值滤波的快速算法都是基于排序理论的.本文突破了这种约束,一方面从序列中快速寻找中值人手,对传统的快速排序求中值的算法进行了改进,它无须对数据进行排序,减少了运算量;另一方面充分利用数据相关性,考虑移入值和移出值与中值的位置关系,达到数据的快速插入与删除.实验表明,该算法应用于信号滤波处理时,能有效地降低中值滤波算法的时间复杂度,计算效率和运算速度比传统快速滤波算法更高.     

An efficient code-timing estimator for receiver diversity DS-CDMAsystems

We propose an efficient algorithm for estimating the code timing of direct-sequence code-division multiple-access (DS-CDMA) systems that consist of an arbitrary antenna array at the receiver and work in a flat-fading and near-far environment. The algorithm is an asymptotic (for large number of data samples) maximum-likelihood (ML) estimator that is derived by modeling the known training sequence as the desired signal and all other signals including the interfering signals and the additive noise as unknown colored Gaussian noise. The algorithm does not require the search over a parameter space and the code timing is obtained by rooting a second-order polynomial, which is computationally very efficient. Simulation results show that the algorithm is quite robust against the near-far problem and channel fading. It requires a shorter training sequence than the single-antenna-based estimators     

Efficient hundreds-baseline stereo by counting interest points for moving omni-directional multi-camera system

In this article, we propose an efficient method for estimating a depth map from long-baseline image sequences captured by a calibrated moving multi-camera system. Our concept for estimating a depth map is very simple; we integrate the counting of the total number of interest points (TNIP) in images with the original framework of multiple baseline stereo. Even by using a simple algorithm, the depth can be determined without computing similarity measures such as SSD (sum of squared differences) and NCC (normalized cross correlation) that have been used for conventional stereo matching. The proposed stereo algorithm is computationally efficient and robust for distortions and occlusions and has high affinity with omni-directional and multi-camera imaging. Although expected trade-off between accuracy and efficiency is confirmed for a naive TNIP-based method, a hybrid approach that uses both TNIP and SSD improve this with realizing high accurate and efficient depth estimation. We have experimentally verified the validity and feasibility of the TNIP-based stereo algorithm for both synthetic and real outdoor scenes.     

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     

一种基于三阶累积量的准则及自适应滤波算法

该文提出了一个基于三阶累积量的优度准则。基于此准则,利用最速下降法,得到一种新的基于三阶累积的梯度型自适应滤波算法,该算法用于平稳和非平稳的MA(Moving Average)模型系统辨识的计算机模拟仿真结果表明:该算法有良好的收敛性能及对时变系统的跟踪能力。     

基于亚像素精度分割的晶粒图像识别方法

机器视觉在工业产品质量控制中的应用越来越广,针对LED晶粒的质量检测问题,提出了一种基于亚像素精度阈值分割的方法进行LED晶粒图像的识别。首先通过图像增强及预处理,然后通过基于亚像素精度的阈值分割方法进行晶粒图像的预处理,再通过K值聚类算法进行感兴趣的区域提取,最后通过NCC归一化的方法进行晶粒位置的识别及定位。实验结果表明,提出的亚像素精度阈值分割和NCC归一化定位算法相结合的方法应用在LED分拣机中,能准确地识别出LED晶粒图像。     

Image inpainting using directional wavelet packets originating from polynomial splines

The paper presents a new algorithm for the image inpainting problem. The algorithm uses a recently designed versatile library of quasi-analytic complex-valued wavelet packets (qWPs) which originate from polynomial splines of arbitrary orders. Tensor products of 1D qWPs provide a diversity of 2D qWPs oriented in multiple directions. For example, a set of the fourth-level qWPs comprises 62 different directions. The properties of these qWPs such as refined frequency resolution, directionality of waveforms with unlimited number of orientations, (anti-)symmetry of waveforms and windowed oscillating structure of waveforms with a variety of frequencies, make them efficient in image processing applications, in particular, in dealing with the inpainting problem addressed in the paper. The obtained results for this problem are quite competitive with the best state-of-the-art algorithms. The inpainting is implemented by an iterative scheme, which expands the Split Bregman Iteration (SBI) procedure by supplying it with an adaptive variable soft thresholding based on the Bivariate Shrinkage algorithm. In the inpainting experiments, performance comparison between the qWP-based methods and the state-of-the-art algorithms is presented.     

Information routing and reliability issues in distributed sensornetworks

Communication issues and problems in information routing in distributed sensor networks (DSNs) are considered. Two important communication constraints, viz., the delay constraint and the reliability constraint, are identified, and their impact on information routing is discussed. It is shown that the maximum end-to-end delay in a network depends on the diameter of the network, and efficient distributed algorithms are presented to determine the diameter of asynchronous networks. A distributed algorithm that determines the diameter of an asynchronous tree network when an arbitrary node in the network initiates the algorithm is introduced. An efficient algorithm for determining the diameter when multiple nodes initiate the algorithm is presented. An algorithm to determine the diameter of arbitrary networks is presented, and its message complexity is shown. Effects of link/node failures on network delay are studied, and important network structure design criterion are discussed. The distributed, dynamic routing algorithms are reviewed, and their adaptation to DSN environments is discussed     

A new algorithm for order statistic and sorting

An algorithm for rank filtering and stack filtering is presented. This algorithm is simple and results in fast and easy implementations. Various implementations of the algorithm are described, and the H-tree design is shown to be most area efficient. Also introduced is a modification of the filtering algorithm that results in better implement sorting