An Efficient Nearest Neighbor Search Method

A simple, but efficient, nearest neighbor search algorithm is proposed and simulation results demonstrating its effectiveness in the case of vector quantization for a given source are presented. The simulation results indicate that use of this approach reduces the number of multiplications and additions to as low as 9 percent of those required for the conventional full search method. The reduction in the number of subtractions is also considerable. The increase in the number of comparisons is moderate, and therefore, the total number of operations can be as low as 28 percent of those required by the full search method. An additional advantage of the described algorithm is the fact that it requires no precomputations and/or extra memory.     

完全搜索块匹配运动补偿算法光电混合系统

基于声光相关器提出了种能实时实现视频图象压缩中完全搜索块匹配运动补偿算法的光电混合系统，与全数字电路相比，该系统具有足够的带宽，能并行处理大量数据，并且电路较简单，可降低功耗、成本及结构复杂性，还讨论了该系统的适用范围。     

一种矢量量化编码的加速算法

本文提出了一种基于最小均方误差测度的快速矢量量化编码算法。在进行均方测度计算之前，通过一组距离测度的不等式判据和预排序的码书，排了作大部分候选码字。     

基于增强位平面的自适应运动估计算法

提出了一种基于增强位平面的自适应运动估计算法(ABPS)。算法采用位平面的思想,将图像分解为8个增强位平面,在图像的位平面中完成运动矢量的搜索,匹配准则使用简单的布尔函数就可以实现;根据运动矢量场自适应选择搜索起始点和不同的搜索策略进行搜索,同时设定阈值对静止块直接中止搜索。实验结果表明：该算法的搜索点数比全搜索算法提高了95％以上,搜索速度优于绝大多数现有的运动估计算法;且PSNR值比全搜索算法仅相差0．05dB左右,具有较高的搜索精度。     

Incremental backprojection algorithm: modification of the searching flow scheme and utilization of the relationship among projection views

A two-dimensional (2-D) search flow scheme is proposed for the incremental backprojection algorithm. In this scheme, the searching direction in a beam is determined only by the distance from the current pixel to the corresponding ray; no pixels outside the beam are involved in the procedure. In addition, the geometrical relationships between the image grids and the projection rays in different views are fully exploited to further reduce the search operations. It is found that backprojection of four views can be performed at the same time, and the search operation is only required for one of them if the number of views is even. Thus, backprojection is accomplished on a quartet-by-quartet of views basis as well as on beam-by-beam basis. These approaches not only minimize the number of search operations but also possess a simple algorithm structure. Implementation results obtained with an AST-386 computer for the incremental backprojection algorithm using this search flow scheme and the relationship among projection views show that the processing time can be reduced by a factor of about 2.     

Fast search techniques for use in vector quantisation and related pattern matching applications

Two techniques for the design and fast search of a vector quantiser codebook are proposed. These classify speech data vectors according to (i) the sign and (ii) the slope between successive samples. With both techniques the performance obtained is superior to that obtained from a conventional gain/shape vector quantiser and comparable to that of a full search vector quantiser. A major attraction of both approaches is that they significantly reduce the number of computations required for the codebook search.     

A Fiber Routing Problem in Designing Optical Transport Networks with Wavelength Division Multiplexed Systems

In this paper, we consider a fiber routing problem arising from the design of optical transport networks. The problem is to find an optimal routing of multiple rings and an optimal location of wavelength division multiplexed (WDM) systems for carrying demand traffic. This problem can be conceptualized as a Steiner (multiple) ring problem with link capacity constraints. We formulate the problem as a mixed-integer programming model and develop a new branch-and-cut procedure along with preprocessing routines and valid inequalities for optimally solving the problem. Exploiting the inherent special structures of the formulation, we focus on developing strong valid inequalities and devising an effective Tabu search heuristic for solving large-scale problems. Computational results indicate that preprocessing rules and valid inequalities provide a tight lower bound, and in turn reduce the effort required to solve the problem within the framework of the branch-and-cut procedure. Moreover, the proposed Tabu search heuristic works quite well for solving large-scale problems. Motivated by promising computational results, we provide insights into implementing the proposed branch-and-cut procedure for deploying fiber optic networks in practice.     

一种矢量量化码书搜索的快速算法

本文提出了一种采用均方误差(MSE)测度的矢量量化码书搜索的快速算法.该算法在码书设计的每次迭代前预先计算各码字的和值(一个矢量各分量的和)并保存在码书中.在迭代过程中,利用输入矢量的和值、各码字的和值以及均方误差三者之间的各种特性排除大部分候选码字而免去许多均方误差计算.测试结果表明,相对于穷尽搜索方法,计算量得到明显的降低,计算时间减少约90%,同时只需要很少的预先计算量和额外存储量.     

A fast search algorithm for vector quantization usingL2-norm pyramid of codewords

Vector quantization for image compression requires expensive encoding time to find the closest codeword to the input vector. This paper presents a fast algorithm to speed up the closest codeword search process in vector quantization encoding. By using an appropriate topological structure of the codebook, we first derive a condition to eliminate unnecessary matching operations from the search procedure. Then, based on this elimination condition, a fast search algorithm is suggested. Simulation results show that with little preprocessing and memory cost, the proposed search algorithm significantly reduces the encoding complexity while maintaining the same encoding quality as that of the full search algorithm. It is also found that the proposed algorithm outperforms the existing search algorithms.     

A 14-Gops programmable motion estimator for H.26X video coding

A 14 Giga operations per second (Gops) programmable motion estimator chip is developed to support multiple algorithms and video coding standards. The chip performs multisurvivor motion estimation in the subsampled scan and the cluster search mode. The chip uses a dual-addressing single-port memory and a pel-rotating processing element array to implement synchronous self-aligned block difference computation. The chip is implemented in 0.5-μm CMOS achieving 86.4 Million operations per second (Mops)/KXtr and 21 mW/Gop. The chip delivers full search quality for H.26X coding at CIF 30 f/s, near full search quality at NTSC level, and a wide range of other video quality and resolution tradeoffs     

An Efficient Scalable RNS Architecture for Large Dynamic Ranges

This paper proposes an efficient scalable Residue Number System (RNS) architecture supporting moduli sets with an arbitrary number of channels, allowing to achieve larger dynamic range and a higher level of parallelism. The proposed architecture allows the forward and reverse RNS conversion, by reusing the arithmetic channel units. The arithmetic operations supported at the channel level include addition, subtraction, and multiplication with accumulation capability. For the reverse conversion two algorithms are considered, one based on the Chinese Remainder Theorem and the other one on Mixed-Radix-Conversion, leading to implementations optimized for delay and required circuit area. With the proposed architecture a complete and compact RNS platform is achieved . Experimental results suggest gains of 17 % in the delay in the arithmetic operations, with an area reduction of 23 % regarding the RNS state of the art. When compared with a binary system the proposed architecture allows to perform the same computation 20 times faster alongside with only 10 % of the circuit area resources.     

基于量子搜索算法的非对称量子加密协议(英文)

Quantum cryptography and quantum search algorithm are considered as two important research topics in quantum information science.An asymmetrical quantum encryption protocol based on the properties of quantum one-way function and quantum search algorithm is proposed.Depending on the no-cloning theorem and trapdoor one-way functions of the publickey,the eavesdropper cannot extract any private-information from the public-keys and the ciphertext.Introducing key-generation randomized logarithm to improve security of our proposed protocol,i.e.,one privatekey corresponds to an exponential number of public-keys.Using unitary operations and the single photon measurement,secret messages can be directly sent from the sender to the receiver.The security of the proposed protocol is proved that it is informationtheoretically secure.Furthermore,compared the symmetrical Quantum key distribution,the proposed protocol is not only efficient to reduce additional communication,but also easier to carry out in practice,because no entangled photons and complex operations are required.     

Low complexity hybrid layered tabu-likelihood ascent search for large MIMO detection with perfect and estimated channel state information

In this work, we proposed a low-complexity hybrid layered tabu-likelihood ascent search (LTLAS) algorithm for large multiple-input multiple-output (MIMO) system. The conventional layered tabu search (LTS) approach involves many partial reactive tabu searches (RTSs), and each RTS requires an initialization and searching phase. In the proposed algorithm, we restricted the upper limit of the number of RTS operations. Once RTS operations exceed the limit, RTS will be replaced by low-complexity likelihood ascent search (LAS) operations. The block-based detection approach is considered to maintain a higher signal-to-noise ratio (SNR) detection performance. An efficient precomputation technique is derived, which can suppress redundant computations. The simulation results show that the bit error rate (BER) performance of the proposed detection method is close to the conventional LTS method. The complexity analysis shows that the proposed method has significantly lower computational complexity than conventional methods. Also, the proposed method can reduce almost 50% of real operations to achieve a BER of 10⁻³.     

Incremental-search fast vector quantiser using triangularinequalities for multiple anchors

A new fast vector quantiser (VQ) is proposed which reduces computational complexity by searching the intersection of search regions defined by triangular inequalities for multiple anchors. A greedy algorithm which selects an anchor set is also proposed. The proposed VQ reduces the number of multiply operations by 24.4% compared to Li's VQ [1995] while preserving the same encoding quality as the full-search VQ     

Two-Step Sparse Representation Based 2D DOA Estimation with Single Moving Acoustic Vector Sensor

This paper investigates the two dimensional direction of arrival (2D DOA) estimation problem of multiple sources with one single moving acoustic vector sensor (AVS). We first use one single moving AVS to construct a synthetic nested AVS array, which is later shown that is equivalent to the physical nested AVS array. Then the vectorization and row extraction operations are performed to obtain the observation vector that behaves like signals received by a virtual uniform AVS array. Finally, the 2D DOA estimation is obtained via a two-step sparse representation (SR) method, which transforms the 2D grid search to a computationally efficient 1D grid search. The Cramer-Rao bound comparison between the synthetic and physical nested AVS arrays shows that these two arrays are equivalent for DOA estimation. Based on the property of the nested arrays and the full utilization of the array aperture via SR, the proposed method can achieve better estimation performance than spatial smoothing methods with nested AVS arrays and methods with uniform AVS arrays. Simulations validate the effectiveness of the proposed synthetic array method.

     

Phase equalization of one and two-dimensional recursive filers

An effective optimization algorithm is proposed to design multidimensional recursive phase equalizers. The optimization algorithm uses the modified version of the Rosenbrock (1960) pattern search method to minimize the maximum group delay ripple. This numerical method eliminates the increased complexity that derivative methods show when multiple variables are to be found. The criteria used to guarantee the stability of the equalizer are based on the DeCarlo-Strintzis theorem. By applying this theorem, the stability test procedure in m dimensions is reduced to m one-dimensional stability test routines. Using this stabilization technique and the Rosenbrock pattern search method for optimization, the intensity of computations is considerably reduced in higher dimensions     

An efficient encoding algorithm for vector quantization based on subvector technique

In this paper, a new and fast encoding algorithm for vector quantization is presented. This algorithm makes full use of two characteristics of a vector: the sum and the variance. A vector is separated into two subvectors: one is composed of the first half of vector components and the other consists of the remaining vector components. Three inequalities based on the sums and variances of a vector and its two subvectors components are introduced to reject those codewords that are impossible to be the nearest codeword, thereby saving a great deal of computational time, while introducing no extra distortion compared to the conventional full search algorithm. The simulation results show that the proposed algorithm is faster than the equal-average nearest neighbor search (ENNS), the improved ENNS, the equal-average equal-variance nearest neighbor search (EENNS) and the improved EENNS algorithms. Comparing with the improved EENNS algorithm, the proposed algorithm reduces the computational time and the number of distortion calculations by 2.4% to 6% and 20.5% to 26.8%, respectively. The average improvements of the computational time and the number of distortion calculations are 4% and 24.6% for the codebook sizes of 128 to 1024, respectively.     

Efficient bounded-distance decoding of the hexacode and associateddecoders for the Leech lattice and the Golay code

Two soft-decision decoding algorithms for the (6, 3, 4) quaternary code hexacode are presented. Both algorithms realize half the minimum Euclidean distance of the code. The proposed algorithms are most practical. In using them, bounded-distance decoding of the Golay code and the Leech lattice are performed with at most 187 and 519 real-number operations respectively. Compare this to 651, respectively 3595, operations required by the best known maximum likelihood decoders (Vardy and Be'ery, 1991, 1993), and 431, respectively 1007, operations required by the bounded-distance decoders (Amrani et al., 1994). We present some simulation results for the proposed Leech lattice decoders revealing near-optimal performance. A comparison to known trellis codes is also provided     

FPGA architecture of the LDPS Motion Estimation for H.264/AVC Video Coding

Motion estimation is a highly computational demanding operation during video compression process and significantly affects the output quality of an encoded sequence. Special hardware architectures are required to achieve real-time compression performance. Many fast search block matching motion estimation (BMME) algorithms have been developed in order to minimize search positions and speed up computation but they do not take into account how they can be effectively implemented by hardware. In this paper, we propose three new hardware architectures of fast search block matching motion estimation algorithm using Line Diamond Parallel Search (LDPS) for H.264/AVC video coding system. These architectures use pipeline and parallel processing techniques and present minimum latency, maximum throughput and full utilization of hardware resources. The VHDL code has been tested and can work at high frequency in a Xilinx Virtex-5 FPGA circuit for the three proposed architectures.     

基于边框定界的WSN分布式全搜索定位算法

提出一种基于边框定界的WSN分布式全搜索定位算法。该算法通过节点测距得到邻居节点的坐标和距离信息,然后通过边框定界方法确定节点存在的位置区域,最后将位置区域网格化,并用全搜索方法在该区域搜索最佳估计点,最佳估计点的坐标即为节点的定位坐标。该算法应用到网络时需运行多轮,通过逐步求精得到节点的定位坐标。仿真实验表明该算法达到当前其他复杂定位算法的性能。