Design and Complexity Optimization of a New Digital IF for Software Radio Receivers With Prescribed Output Accuracy

This paper studies the design, signal round-off noise, and complexity optimization of a new digital intermediate frequency (IF) architecture for a software radio receiver (SRR). The IF under study consists of digital filters with fixed coefficients, except for a limited number of multipliers required in the Farrow-based sampling rate converter (SRC). The fixed-coefficient filters can be implemented efficiently using sum-of-power-of-two (SOPOT) coefficients and the multiplier-block technique, which gives minimum adder realization. Apart from the multipliers required in the SRC, the digital IF can be implemented without any multiplications. While most multiplier- less filter design and realization methods address only the coefficient round-off problem by minimizing the number of SOPOT terms used, the proposed design methodology aims to minimize more realistic hardware complexity measure, such as adder cells and registers, of the digital IF subject to a given spectral and accuracy specifications. The motivation is that the complexity is closely related to the target output accuracy, which is specified statistically by its total output noise power generated by rounding the intermediate data. Two novel algorithms for optimizing the internal wordlengths of linear time-invariant systems are proposed. The first one relaxes the solution to real valued and formulates the design problem as a constrained optimization. A closed-form solution can be determined by the Lagrange multiplier method. The second one is based on a discrete optimization method called the Marginal Analysis method, and it yields the desired wordlengths in integer values. Both approaches are found to be effective and suitable to large scale systems. A design example and the field programmable gate array (FPGA) realization of a multi-standard receiver are given to demonstrate the proposed method     

Design of nonuniformly spaced linear-phase FIR filters using mixedinteger linear programming

An optimization problem for designing a nonuniformly spaced linear-phase FIR filter with minimal complexity is formulated and solved by mixed integer linear programming (MILP). Examples illustrate that the proposed method is useful for designing a wide range of filter types and can outperform subset selection-based design methods     

An Improved Lattice Filter Structure with Minimum Roundoff Noise Gain

In this paper, a new filter structure is derived by combining the lattice structure and error feedback technique, which contains a free parameter used for structure optimization. The roundoff noise of the proposed structure is analyzed, and the corresponding mathematical expression is deduced. The problem of how to optimize the free parameter is investigated in terms of minimizing the roundoff noise gain. When the free parameter is expressed as an integer power-of-two, for an Nth-order digital filter, the proposed structure requires \(5N+1\) multipliers, which yields the same implementation complexity as the normalized lattice structure. A numerical example is given to show the finite wordlength performance of the proposed structure.     

A new method for designing multiplierless two-channel filterbank using shifted-Chebyshev polynomials

This paper presents an efficient design method for a digital multiplierless two-channel filterbank using the shifted-Chebyshev polynomials and common sub-expression elimination (CSE) algorithm for reducing hardware requirements such as adders and multipliers. For designing a two-channel filterbank, the design problem is constructed as minimization of integral mean square error between the desired and designed response of a prototype filter in the passband and stopband. For controlling the performance in passband and stopband, two parameters (K_P, and K_S) are used, whose optimum values are determined by swam optimization techniques such as differential evolution algorithm, artificial bee colony optimization, particle swarm optimizations, cuckoo search algorithm and hybrid method using a fitness function, constructed by perfect reconstruction condition of a filterbank. The number of polynomials used for approximation depends upon the order of a prototype filter. A new hybrid CSE is proposed for further reduction of hardware requirement. A comparative study of various CSE techniques such as horizontal, vertical and proposed hybrid CSE is also made. Numerical examples illustrate the effectiveness of the proposed algorithm in the reduction of adders with comparisons accomplished using existing methods. It has been found that almost 43% adder gain can be achieved when a filter is designed with N = 32 and wordlength (WL) as 12 using proposed methodology.     

Applying SMT-based verification to hardware/software partitioning in embedded systems

When performing hardware/software co-design for embedded systems, the problem of which functions of the system should be implemented in hardware (HW) or in software (SW) emerges. This problem is known as HW/SW partitioning. Over the last 10 years, a significant research effort has been carried out in this area. In this paper, we present two new approaches to solve the HW/SW partitioning problem by using verification techniques based on satisfiability modulo theories (SMT). We compare the results using the traditional technique of integer linear programming, specifically binary integer programming and a modern method of optimization by genetic algorithm. The experimental results show that SMT-based verification techniques can be effective in particular cases to solve the HW/SW partition problem optimally using a state-of-the-art model checker based on SMT solvers, when compared against traditional techniques.     

A heuristic method for self‐healing ring design in a single‐homing cluster

In this paper, we consider a SONET (Synchronous Optical NETwork) USHR (Uni‐directional Self‐Healing Ring) design problem for a single‐homing cluster, i.e., a cluster with a single designated hub. The problem is formulated as a nonlinear integer programming problem and a branch and bound heuristic method based on the Lagrangian relaxation and subgradient optimization technique is proposed to handle the problem. In solving any ring design problem, we should deal with two different aspects of the ring design, namely, the ring routing aspect and the ring loading aspect. Both of these two aspects are well integrated and represented in our model. Such an integrated formulation has not been proposed in the existing literature mainly due to its computationally intractable complexity. In order to cope with such complexity, a preprocessing technique for reducing the complexity and several branch and bound strategies are proposed. The efficiency of the proposed method is tested through computational experiments. For the computational experiments, test problems are generated using the data obtained from the actual topologies in Seoul, Korea. The computational experiments show that the proposed method yields near‐optimum designs within reasonable computation time. This revised version was published online in August 2006 with corrections to the Cover Date.     

H.264中DCT算法在FPGA上的高层次综合实现

针对传统硬件设计方法在大规模算法应用实现中的高复杂度,提出了一种高层次综合方法,从而实现高效快速地硬件设计。以H.264编码中常用的DCT算法的硬件实现为目的,对算法的C语言实现进行优化,并使用高层次综合工具将优化后的C语言算法描述转换为专用硬件加速器;通过高层次综合工具提供的接口设定、流水线插入、块并行等操作,对生成的硬件作进一步优化;与人为DCT算法的RTL设计和采用高层次综合方法的DCT硬件设计相比,具有更大的设计空间和更高的代码可裁剪性。FPGA实现结果表明,H.264中基于高层次综合方法的DCT算法在节省大量设计开发时间的前提下,可达到每秒处理516兆个整型数的计算性能。     

设计有限字长FIR数字滤波器的Tabu优化算法

该文提出了设计有限字长FIR数字滤波器的Tabu优化算法,这是一种模拟人的记忆过程的并行优化算法。首先,详细描述了Tabu算法并给出了计算步骤;然后将Tabu算法应用于有限字长FIR数字滤波器的优化设计;最后给出了模拟计算结果。     

k-out-of-m system availability with minimum-costallocation spares

An optimization method for determining the number of spare units that should be allocated to a k-out-of-m system to minimize the system-spares cost yet attain the specified system availability is presented. The objective function for optimization is a nonlinear integer type. The optimization method is a variation of the simplex search technique used for continuous functions. The optimization problem is cast in a form that minimizes the system-spares cost, with the required system availability as an inequality constraint. Results obtained by using the proposed optimization technique, as well as the computation time required for optimization, are compared to those for methods developed specifically for dealing with nonlinear integer problems. The method is simple, easy to implement, and yet very effective in dealing with the spare allocation problem for k-out-of-m:F systems     

Design of Linear Phase FIR Filters in Subexpression Space Using Mixed Integer Linear Programming

In this paper, a novel optimization technique is proposed to optimize filter coefficients of linear phase finite-impulse response (FIR) filter to share common subexpressions within and among coefficients. Existing approaches of common subexpression elimination optimize digital filters in two stages: first, an FIR filter is designed in a discrete space such as finite wordlength space or signed power-of-two (SPT) space to meet a given specification; in the second stage, an optimization algorithm is applied on the discrete coefficients to find and eliminate the common subexpressions. Such a two-stage optimization technique suffers from the problem that the search space in the second stage is limited by the finite wordlength or SPT coefficients obtained in the first stage optimization. The new proposed algorithm overcomes this problem by optimizing the filter coefficients directly in subexpression space for a given specification. Numerical examples of benchmark filters show that the required number of adders obtained using the proposed algorithm is much less than those obtained using two-stage optimization approaches.     

Topological Design and Lightpath Routing in WDM Mesh Networks: A Combined Approach

Multicommodity flow models are commonly used to formulate the logical topology design (LTD) problem and the lightpath routing (LR) problem as mixed integer linear programming (MILP) problems. In general, MILP formulations are intractable even for relatively small networks due to the combinatorial complexity of the problem. In this paper we propose improvements to these models and a method to solve the LTD and the LR problems in a combined manner. The interest is two fold: firstly, by tackling the two problems with separate models, problem instances of realistic size (up to 14 nodes in this paper) can be dealt with. Furthermore, different combinations of optimization models and objective functions can be investigated in a modular manner. Secondly, the mechanisms proposed to combine the problems allow to keep track of the global design problem when solving each individual step.     

An enhanced integer simplicial optimization method for minimum costspares for k-out-of-n systems

The authors report two enhancements to an integer simplicial optimization method developed for a spares allocation problem where it is necessary to minimize the spares cost of a k-out-of-n system configuration subject to an availability constraint. The first is an automated, simple, general method for generating an initial feasible good starting vector for optimization. This vector increases the likelihood of convergence to a global optimal solution and does not require homogenization of a suboptimum solution vector prior to restarting the optimization process of the penalty function for the lower values of the multipliers. The second is treatment of cases where the simplex strays into the feasible region. Results of testing the integer simplicial optimization procedure with the enhancements are compared to those obtained from methods developed specifically for dealing with this type of nonlinear integer problem. The tests were conducted for systems with various numbers of subsystems     

非连续正交频分复用系统次优导频设计

在非连续正交频分复用系统中,为了改善信道估计的性能并尽可能地降低计算复杂度,基于最小化最小二乘信道估计均方误差(Mean Square Error,MSE)的准则提出了一种次优导频设计方法.该方法利用凸映射解决了导频位置优化设计的非凸问题,求得符合三次函数关系的非均匀分布次优导频位置,并推导导频位置已知条件下的最优导频功率分布.仿真结果表明：所提次优导频设计方法与现存导频设计方法相比,能够获得较好的信道估计MSE性能,且具有计算简单的优势.     

Link optimization for energy‐constrained wireless networks with packet retransmissions

With the objective to minimize the energy consumption for packet based communications in energy‐constrained wireless networks, this paper establishes a theoretical model for the joint optimization of the parameters at the physical layer and data link layer. Multilevel quadrature amplitude modulation (MQAM) and automatic repeat request (ARQ) techniques are considered in the system model. The optimization problem is formulated into a three dimensional nonlinear integer programming (NIP) problem with the modulation order, packet size, and retransmission limit as variables. For the retransmission limit, a simple search method is applied to degenerate the three dimensional problem into a two dimensional NIP problem, for which two optimization algorithms are proposed. One is the successive quadratic programming (SQP) algorithm, combining with the continuous relaxation based branch‐and‐bound method, which can obtain the global optimal solution since the continuous relaxation problem is proved to be hidden convex. The other is a low‐complexity sub‐optimal iterative algorithm, combining with the nearest‐neighboring method, which can be implemented with a polynomial complexity. Numerical examples are given to illustrate the optimization solution, which suggests that the joint optimization of the physical/data link layer parameters contributes noticeably to the energy saving in energy‐constrained wireless networks. Copyright © 2010 John Wiley & Sons, Ltd.     

Security enhancement with joint transmit antenna selection and transmit beamforming under energy harvesting constraints

This paper considers a multiuser multiple‐input single‐output (MISO) broadcasting system with simultaneous wireless information and power transfer (SWIPT), which consists of one information receiver (IR) and several energy harvesting receivers (ERs) which are capable of eavesdropping the legitimate signals. For reducing cost and hardware complexity, transmit antenna selection (TAS) is applied in the transmitter. We aim to maximize the achievable secrecy rate under the individual energy harvesting constraint at the ERs and the transmit power constraint at the transmitter by jointly optimizing TAS, transmit beamforming, and artificial noise (AN). The joint optimization problem is a non‐convex mixed integer programming problem. We apply variable replacements to decouple the variable couplings and relax and approach the binary constraint by the difference of two convex constraints. Afterwards, penalty method and constrained concave convex procedure (CCCP) are applied to transform the relaxed problem into a sequence of semi‐definiteness programming (SDP) problems. Simulation results shows that our proposed joint optimization scheme is superior over existing non‐joint optimization schemes. This paper studies the joint transmit antenna selection (TAS), transmit beamforming, and artificial noise (AN) optimization in a multiple‐input multiple‐output (MISO) wiretap system with simultaneous wireless information and power transfer (SWIPT). The joint optimization problem is nonconvex and we propose a penalty method based scheme to solve it. The simulation results show that our joint optimization scheme is superior to other non‐joint optimization schemes.     

Application of boundary-tracking gradient-method for optimizingspares cost for k-out-of-n:G systems

This paper presents an application of a classical method of steepest-descent optimization coupled with a boundary-tracking technique to solve the integer spare allocation problem for k-out-of-n:G systems. The objective function for the optimization is linear and subject to a nonlinear availability constraint. The constrained problem is solved in an unconstrained manner using a multiple-gradient technique. The search along the function gradient (unit cost) aims to locate the desired optimum on the constraint boundary. A recovery move to the feasible region is carried out if the search strays into the unfeasible region. Upon re-entry into the feasible region, a new base point for the new search direction is found along the vector sum of the gradient of the objective function and the violated constraint at the recovery point. Results for this boundary tracking multi-dimensional gradient optimization method are compared with enhanced simplical optimization and other methods developed specifically for solving integer problems. The authors' tests are carried out on systems of various numbers of subsystems. The results show appreciable improvement in execution time when compared to their earlier integer simplical optimization methods and to the Sasaki method. The improvement in CPU times is presented for comparison     

Carrier Frequency Offset Estimation for OFDM Systems with Null Subcarriers

An accurate estimation of carrier frequency offset (CFO) is a crucial task for orthogonal frequency-division multiplexing (OFDM) systems but should be performed with affordable computational complexity for practicality. In this paper, the authors derive two new estimation algorithms (one for the integer part and the other for the fractional part of CFO), each of which utilizes only one OFDM block with null subcarriers but offers improved accuracy and reduced complexity. The proposed estimator for fractional CFOs operates iteratively and is insensitive to the initial CFO. The other proposed estimator for integer CFOs employs a pseudonoise binary random sequence to assist in subcarrier arrangement and accurate estimation of the integer CFO. To demonstrate the efficiency of the proposed methods, numerical results are provided from computer simulation and analysis, and comparisons are made with other existing methods in the literature.     

OFDM系统信道估计方法研究

分析了现有实用OFDM系统的信道估计方法及其硬件结构,并根据信道的统计特征给出了一种改进的门限滤波方法与其对应的硬件结构.在提高性能的同时,这种方法复杂度并不高,且不需要任何已知的信道统计特性.通过实验验证,这种新方法(尤其是二维的方法)明显优于传统的基于FFT的方法和最小二乘方法.     

二进制猫群算法在大规模MIMO天线选择中的应用

在多输入多输出(MIMO)系统中,天线选择技术平衡了系统的性能和硬件开销,但大规模MI-MO系统收发端天线选择复杂度问题一直没有得到很好的解决.基于信道容量最大化的准则,采用两个二进制编码字符串分别表示发射端和接收端天线被选择的状态,提出将二进制猫群算法(BCSO)应用于多天线选择中,以MIMO系统信道容量公式作为猫群的适应度函数,将收发端天线选择问题转化为猫群的位置寻优过程.建立了基于BCSO的天线选择模型,给出了算法的实现步骤.仿真结果表明所提算法较之于基于矩阵简化的方法、粒子优化算法具有更好的收敛性和较低的计算复杂度,选择后的系统信道容量接近于最优算法,非常适用于联合收发端天线选择的大规模MIMO系统中.     

Linear quadratic Gaussian control of 2-dimensional systems

The linear quadratic Gaussian (LQG) control for one-dimensional (1D) systems has been known to be one of the fundamental and significant methods in linear system theory. However, the LQG control problem for two-dimensional (2D) systems has not been satisfactorily solved due to their structural and dynamical complexity. In this paper, sufficient conditions for evaluation of the quadratic performance indices of 2D systems in terms of the system state and control variables are proposed. Using these conditions, systematic design methods for finite horizon and infinite horizon LQG controls of 2D systems are developed using a convex optimization method.