基于分阶段LFF策略的大规模模块布局方法

提出了一种用于求解大规模VLSI模块布局问题的确定性方法.该方法在"最小自由度优先"原则的基础上,模拟人工布局过程提出了"分阶段布局"的思想.分阶段布局就是将布局过程按照布局完成的比例划分成若干个阶段,再将各种启发式策略适当地应用到各个阶段中,从而改善算法的整体性能.理论上,算法的时间复杂为(N1+N2)O(n2)+N3O(n4lgn),其中N1,N2,N3为各个阶段的模块数目,N1+N2+N3=n,且N3＜＜n,比原有的最小自由度优先算法复杂度O(n5lgn)小很多.实验结果也表明该方法很有潜力.     

A distortion optimal rate allocation algorithm for transmission of embedded bitstreams over noisy channels

We propose a distortion optimal rate allocation algorithm for robust transmission of embedded bitstreams over noisy channels. The algorithm is based on the backward application of a Viterbi-like algorithm to a search trellis, and can be applied to both scenarios of fixed and variable channel packet length problems, referred to as FPP and VPP, respectively. For the VPP, the complexity of the algorithm is comparable to the well-known dynamic programming approach of Chande and Farvardin. For the FPP, where no low-complexity algorithm is known, the complexity of the proposed algorithm is O(N/sup 2/), where N is the number of transmitted packets.     

An efficient rate-distortion optimal shape coding approach utilizing a skeleton-based decomposition

In this paper, we present a new shape-coding approach, which decouples the shape information into two independent signal data sets; the skeleton and the boundary distance from the skeleton. The major benefit of this approach is that it allows for a more flexible tradeoff between approximation error and bit budget. Curves of arbitrary order can be utilized for approximating both the skeleton and distance signals. For a given bit budget for a video frame, we solve the problem of choosing the number and location of the control points for all skeleton and distance signals of all boundaries within a frame, so that the overall distortion is minimized. An operational rate-distortion (ORD) optimal approach using Lagrangian relaxation and a four-dimensional direct acyclic graph (DAG) shortest path algorithm is developed for solving the problem. To reduce the computational complexity from O(N/sup 5/) to O(N/sup 3/), where N is the number of admissible control points for a skeleton, a suboptimal greedy-trellis search algorithm is proposed and compared with the optimal algorithm. In addition, an even more efficient algorithm with computational complexity O(N/sup 2/) that finds an ORD optimal solution using a relaxed distortion criterion is also proposed and compared with the optimal solution. Experimental results demonstrate that our proposed approaches outperform existing ORD optimal approaches, which do not follow the same decomposition of the source data.     

DCT-based motion estimation

We propose novel discrete cosine transform (DCT) pseudophase techniques to estimate shift/delay between two one-dimensional(1-D) signals directly from their DCT coefficients by computing the pseudophase shift hidden in DCT and then employing the sinusoidal orthogonal principles, applicable to signal delay estimation remote sensing. Under the two-dimensional (2-D) translational motion model, we further extend the pseudophase techniques to the DCT-based motion estimation (DXT-ME) algorithm for 2-D signals/images. The DXT-ME algorithm has certain advantages over the commonly used full search block-matching approach (BKM-ME) for application to video coding despite certain limitations. In addition to its robustness in a noisy environment and low computational complexity, O(M(2)) for an MxM search range in comparison to the O(N(2).M(2)) complexity of BKM-ME for an NxN block, its ability to estimate motion completely in DCT domain makes possible the fully DCT-based motion-compensated video coder structure, which has only one major component in the feedback loop instead of three as in the conventional hybrid video coder design, and thus results in a higher system throughput. Furthermore, combination of the DCT and motion estimation units can provide space for further optimization of the overall coder. In addition, the DXT-ME algorithm has solely highly parallel local operations and this property makes feasible parallel implementation suitable for very large scale integration (VLSI) design. Simulation on a number of video sequences is presented with comparison to BKM-ME and other fast block search algorithms for video coding applications even though DXT-ME is completely different from any block search algorithms.     

Greedy Algorithm Applied to Relay Selection for Cooperative Communication Systems in Amplify-and-Forward Mode

Using a relaying system to provide spatial diversity and improve the system performance is a tendency in the wireless cooperative communications. Amplify-and-forward (AF) mode with a low complexity is easy to be implemented. Under the consideration of cooperative communication systems, the scenario includes one information source, M relay stations and N destinations. This work proposes a relay selection algorithm in the Raleigh fading channel. Based on the exhaustive search method, easily to realize, the optimal selection scheme can be found with a highly complicated calculation. In order to reduce the computational complexity, an approximate optimal solution with a greedy algorithm applied for the relay station selection is proposed. With different situations of the communication systems, the performance evaluation obtained by both the proposed algorithm and the exhaustive search algorithm are given for comparison. It shows the proposed algorithm could provide a solution approach to the optimal one.     

基于链码的肿瘤CT图象层间轮廓线最佳点匹配技术的研究

本文利用链码理论对已获取的肿瘤层间轮廓线进行编码,将二维轮廓线转化为包含轮廓形状信息的一维链码;采用一种基于链码的匹配技术来完成相邻层轮廓线点匹配,从而建立起其间的对应关系并用于后期的三维重建.本文首先对模式识别中链码的串匹配算法作了一个简要的介绍,并详细分析了应用链码技术获取相邻轮廓间点对应关系的关键难点,使其能够适用于本文的工作.该方法的计算复杂度近似于M*N(M和N分别为相邻轮廓线顶点的数目).并用实际的肿瘤图象进行实验,结果表明了该方法的有效性.     

基于前缀区间集合的IPv6路由查找算法

对IPv6相关的通用型与特定型路由算法进行了分析,重点研究了以BSR为基础的IPv6路由算法在查找和更新时的不平衡问题,提出了基于前缀区间集合的IPv6路由算法。通过对路由前缀（N）进行范围（K）、集合（M）划分以及更新节点自修复提高查询速度、降低不平衡性的影响,具有O(log2N/K)和O(log2N/K+2M)的查询与更新时间复杂度,空间复杂度为O(K+2N)。实验表明,该算法具有良好的查询性能,降低了更新不平衡性的影响。     

基于Key的XML连续查询算法

普遍认为，XML将会取代Html成为数据表示和数据交换的主流标准，由于在线信息变化频繁，XML文档变化检测成为Internet查询系统、搜索引擎以及连续查询系统的关键技术．先前的研究多着眼于有序模式的XML文档，而无需模式的通用比较已经被证明是NP问题，目前针对无需模式的最好算法复杂度为多项式时间．本文提出了基于Key的变化检测算法，能够高效地检测无序模式XML文档的变化，算法复杂度为O(nlogn)，n为文档结点数．     

Real-valued maximum likelihood decoder for quasi-orthogonal space-time block codes

In this letter, we propose a low complexity Maximum Likelihood (ML) decoding algorithm for quasi-orthogonal space-time block codes (QOSTBCs) based on the real-valued lattice representation and QR decomposition. We show that for a system with rate r = n_s/T, where n_s is the number of transmitted symbols per T time slots; the proposed algorithm decomposes the original complex-valued system into a parallel system with n_s 2 × 2 real-valued components, thus allowing for a simple joint decoding of two real symbols. For a square QAM constellation with L points (L-QAM), this algorithm achieves full diversity by properly incorporating two-dimensional rotation using the optimal rotation angle and the same rotating matrix for any number of transmit antennas (N ⩾4). We show that the complexity gain becomes greater when N or L becomes larger. The complexity of the proposed algorithm is shown to be linear with the number of transmitted symbols n_s.     

Low-complexity centralized joint power and admission control in cognitive radio networks

This letter introduces a centralized joint power and admission control algorithm for cognitive radio networks. Its novelty lies in the proposed admission metric. Unlike those in existing algorithms, our metric predetermines the admission order of N secondary users which intend to access the network. This allows us to search a group of admitted secondary users with the bisection method. The proposed algorithm is shown by simulation to achieve a comparable performance to existing algorithms, and the computational complexity is reduced from O(N³) to O(N² log₂ N).     

高质量的4 kb/s散布脉冲CELP语音编码算法

本文提出了一种散布脉冲CELP(DP-CELP)语音编码算法,激励矢量由特殊结构的代数码书与固定形式的散布脉冲的卷积获得,这种激励源有效地改善了重建语音质量,但未增加代数码书搜索的复杂度.非正式的主观听力测试表明,这种4 kb/s DP-CELP语音编码算法的合成语音质量非常接近G.723.1中6.3 kb/s语音编码器.     

A low-complexity max-log-MAP detector

A low-complexity soft-output Max-log-MAP (maximum a posteriori probability) detector for N2-QAM is exemplified for a 64-QAM 2×M multiple-input-multiple-output (MIMO) system, exhibiting the following novel features: (1) hierarchical formulation of the exhaustive metric calculation to reduce the number of candidate tests by a factor of N per received symbol, and (2) multiplier-free implementation of the exhaustive search with 8-fold parallelization. The computational complexity is reduced by a factor of about 250, resulting in a chip area of 0.031 mm2 using 65nm CMOS.     

分布查找及其复杂性分析

本文提出了一个分布查找算法,并进行了算法的复杂性分析.该算法利用数学公式查找,在N个元素序列中查找N个元素的期望时间为O(N).     

Parallel routing algorithms in Benes-Clos networks

A new parallel algorithm for route assignments in Benes-Clos (1962, 1953) networks is studied. Most known sequential route assignment algorithms, such as the looping algorithm, are designed for circuit switching systems where the switching configuration can be rearranged at relatively low speed. In packet switching systems, switch fabrics must be able to provide internally conflict-free paths simultaneously, and accommodate packets requesting connections in real time as they arrive at the inputs. In this paper, we develop a parallel routing algorithm for Benes networks by solving a set of Boolean equations which are derived from the connection requests and the symmetric structure of the networks. Our approach can handle partial permutations easily. The time complexity of our algorithm is O(log/sup 2/ N), where N is the network size. We also extend the algorithm and show that it can be applied to the Clos networks if the number of central modules is M=2/sup m/, where m is a positive integer. The time complexity is O(log N/spl times/log M) in this case.     

A fast recursive algorithm for the maximum likelihood estimation ofthe parameters of a periodic signal

Describes a new recursive algorithm for the estimation of the parameters of a periodic signal in additive Gaussian white noise. These parameters are the period, and the complex amplitudes of the harmonics present. The proposed algorithm is based on recursive maximum likelihood (ML) algorithms for incomplete data as described by Titterington (1985) and others. These algorithms are of complexity O(NM), where N is the number of harmonics, and M is the signal length. The performance of the method is compared to that of the extended Kalman filter with the aid of simulations     

Improved mode decision algorithm based on residues and early zero block detection in H.264/AVC

Video compression standard H.264/AVC outperforms previous standards in terms of coding efficiency but at the cost of higher computational complexity. In H.264/AVC, the variable block size full motion estimation is the most time-consuming operation. This paper presents a method to reduce the complexity of motion estimation in two stages. The first stage exploits the similarities between frames for early SKIP mode decision for a macroblock (MB) based upon a criteria formulated on the basis of the statistics of the frame difference residues. MBs that fail to qualify for the SKIP mode in the first stage spills over to the second stage where mode decision depends upon the number of zero blocks (ZB) in the MB. The study of the full search motion estimation on different sequences show that there is a strong dependence between the number of ZBs in a MB and the likelihood of a particular mode being selected. The proposed algorithm utilizes this relationship for early mode decision for a MB. The algorithm is evaluated using a wide range of test sequences from different classes. Experimental results show that the proposed algorithm gives considerable saving in encoding time and search points in the range of 36–87%. Furthermore, despite the reduction in computational complexity, the coding efficiency (picture quality and bitrate) in the proposed method is comparable to the H.264/AVC standard software Joint Model (JM12.4).     

具有低复杂度和QoS敏感的LTE调度算法

基于线性松弛原理和贪心法,设计并实现了一种适用于LTE网络、具有全QoS保证能力的低复杂度QPF调度算法。该算法分为时域和频域2个部分,对GBR业务和Non-GBR业务可一次性实现全部资源的分配,将算法复杂度从O(MN)下降到O(M lb N)。仿真表明,该调度算法各项性能较为均衡,在高负荷时部分性能较参考算法有10%的提升,较好地解决了调度的性能和复杂度之间的矛盾。     

Low complexity detection algorithm based on optimized Neumann series for massive MIMO system

An optimized Neumann series ( NS ) approximation isdescribed based on Frobenius matrix decomposition, this method aims to reduce the high complexity, which caused by the large matrix inversion of detection algorithm in the massive multiple input multiple output (MIMO) system. The large matrix in the inversion is decomposed into the sum of the hollow matrix and a Frobenius matrix, and the Frobenius matrix has the diagonal elements and the first column of the large matrix. In order to ensure the detection performance approach to minimum mean square error (MMSE) algorithm, the first three terms of the series approximation are needed, which results in high complexity as O(K³), where K is the number of users. This paper further optimize the third term of the series approximation to reduce the computational complexity from O(K³) to O(K²). The computational complexity analysis and simulation results show that the performance of proposed algorithm can approach to MMSE algorithm with low complexity O(K²).