Comparison of ILP formulations for the RWA problem

We present a review of the integer linear programming (ILP) formulations that have been proposed for the routing and wavelength assignment problem in WDM optical networks assuming asymmetrical traffic. We show that all formulations proposed under asymmetrical traffic assumptions, both link and path formulations, are equivalent in terms of the upper bound value provided by the optimal solution of their linear programming relaxation, although their number of variables and constraints widely differ. We propose improvements for some of the formulations that result in further reductions in the number of variables and constraints.Under the objective of minimizing the blocking rate, we propose an experimental comparison of the best lower and upper bounds that are available. We then discuss the easiness of exact ILP solution depending on the formulations. We observe that LP relaxation bounds often provide solutions with a value very close to the optimal ILP one. We solve exactly for the first time several RWA (Routing and Wavelength Assignment) realistic instances, including those proposed by Krishnaswamy and Sivarajan [R. Krishnaswamy, K. Sivarajan, Algorithms for routing and wavelength assignment based on solutions of LP-relaxation, IEEE Communications Letters 5 (10) (2001) 435–437], with a proof of the optimality.     

Lagrangian-based methods for finding MAP solutions for MRF models

Finding maximum a posteriori (MAP) solutions from noisy images based on a prior Markov random field (MRF) model is a huge computational task. In this paper, we transform the computational problem into an integer linear programming (ILP) problem. We explore the use of Lagrange relaxation (LR) methods for solving the MAP problem. In particular, three different algorithms based on LR are presented. All the methods are competitive alternatives to the commonly used simulation-based algorithms based on Markov Chain Monte Carlo techniques. In all the examples (including both simulated and real images) that have been tested, the best method essentially finds a MAP solution in a small number of iterations. In addition, LR methods provide lower and upper bounds for the posterior, which makes it possible to evaluate the quality of solutions and to construct a stopping criterion for the algorithm. Although additive Gaussian noise models have been applied, any additive noise model fits into the framework.     

Bounds on maximum likelihood ratio-part I: application to antenna array detection-estimation with perfect wavefront coherence

The multiple hypothesis testing problem of the detection-estimation of an unknown number of independent Gaussian point sources is adequately addressed by likelihood ratio (LR) maximization over the set of admissible covariance matrix models. We introduce nonasymptotic lower and upper bounds for the maximum LR. Since LR optimization is generally a nonconvex multiextremal problem, any practical solution could now be tested against these bounds, enabling a high probability of recognizing nonoptimal solutions. We demonstrate that in many applications, the lower bound is quite tight, with approximate maximum likelihood (ML) techniques often unable to approach this bound. The introduced lower bound analysis is shown to be very efficient in determining whether or not performance breakdown has occurred for subspace-based direction-of-arrival (DOA) estimation techniques. We also demonstrate that by proper LR maximization, we can extend the range of signal-to-noise ratio (SNR) values and/or number of data samples wherein accurate parameter estimates are produced. Yet, when the SNR and/or sample size falls below a certain limit for a given scenario, we show that ML estimation suffers from a discontinuity in the parameter estimates: a phenomenon that cannot be eliminated within the ML paradigm.     

Maximum power estimation for CMOS circuits using deterministic andstatistical approaches

Excessive instantaneous power consumption may reduce the reliability and performance of VLSI chips. Hence, to synthesize circuits with high reliability, it is imperative to efficiently obtain a precise estimation of the maximum power dissipation. However, due to the inherent input-pattern dependence of the problem, it is impractical to conduct an exhaustive search for circuits with a large number of primary inputs. Hence, the practical approach is to generate a tight lower bound and an upper bound for maximum power dissipation within a reasonable amount of central processing unit (CPU) time. In this paper, instead of using the traditional simulation-based techniques, we propose a novel approach to obtain a lower bound of the maximum power consumption using automatic test generation (ATG) technique, Experiments with MCNC and ISCAS-85 benchmark circuits show that our approach generates the lower bound with the quality which cannot be achieved using simulation-based techniques. In addition, a Monte Carlo-based technique to estimate maximum power dissipation is described. It not only serves as a comparison version for our ATG approach, but also generates a metric to measure the quality of a lower bound from a statistical point of view     

Evaluation of the reliable data rates supported by multiple-antennacoded wireless links for QAM transmissions

We present some novel results about the reliable information-rate supported by point-to-point multiple-antenna Rayleigh-faded wireless links for coded transmissions that employ two-dimensional (QAM or PSK) data constellations. After deriving the symmetric capacity of these links, we present fast-computable analytical upper and lower bounds that are asymptotically exact both for high and low SNRs, and give rise to a reliable evaluation of the link capacity when perfect channel state information (CSI) is available at the receiver. Furthermore, asymptotically exact simple upper bounds are also presented for a tight evaluation of the outage probability     

Performance of Alamouti Scheme with Transmit Antenna Selection for M-ray Signals

In this letter, we present a comprehensive performance analysis of orthogonal space-time block codes (STBCs) with transmit antenna selection under uncorrelated Rayleigh fading channels. Two best transmit antennas that maximize the instantaneous received signal-to-noise (SNR) are selected. Using the well-known moment generating function-based analysis approach, we derive the exact average symbol error rate (SER) for M-ary signals. Furthermore, we provide tight upper bounds on the SER for any number of transmit antennas and receive antennas. The tightness is verified by simulation results. It is shown that the diversity order, with antenna selection, is maintained as that of the full complexity systems     

Calculating mean system-failure frequency with prescribed accuracy

To calculate mean system-failure frequency (MSFF) for good engineering designs, an approximation with prescribed accuracy is possible, starting from mincuts, viz, from a sum-of-products form of the fault-tree Boolean-function. Bonferroni-type inequalities, for which a new proof is included, are used. There is a far-reaching similarity between certain kinds of bounds for MSFF (of coherent systems) and for system unavailability. However, this similarity Is not complete. For most real systems, omitting the less-important mincuts yields lower bounds not only for unavailability but also for MSFF. Because an equivalent of the first Bonferroni inequality also holds with MSFF, it is possible to determine an upper bound of the contribution of the deleted mincuts or, the other way around: given a maximum error, determine a set of less-important mincuts, which can be deleted prior to a standard (exact) analysis of the rest. Since 1977 there is a valuable insight that Bonferroni-type inequalities hold also for MSFF (and since 1995 for mean electronic-system life). However, if the difference between the first upper and lower bounds is not small enough, then the investigation of further bounds might be rather cumbersome. However, there is a straight-forward mincut-based approximation to MSFF. As for approximate values of system mean time to failure (MTTF) and mean time to repair (MTTR), upper and lower bounds can be readily found via MSFF=unavailability/MTTR=availability/MTTF using upper and lower bounds for unavailability and MSFF in an obvious way. Of course, these bounds might not be sufficiently tight initially     

Signal propagation and noisy circuits

The information carried by a signal decays when the signal is corrupted by random noise. This occurs when a message is transmitted over a noisy channel, as well as when a noisy component performs computation. We first study this signal decay in the context of communication and obtain a tight bound on the rate at which information decreases as a signal crosses a noisy channel. We then use this information theoretic result to obtain depth lower bounds in the noisy circuit model of computation defined by von Neumann. In this model, each component fails (produces 1 instead of 0 or vice-versa) independently with a fixed probability, and yet the output of the circuit is required to be correct with high probability. Von Neumann showed how to construct circuits in this model that reliably compute a function and are no more than a constant factor deeper than noiseless circuits for the function. We provide a lower bound on the multiplicative increase in circuit depth necessary for reliable computation, and an upper bound on the maximum level of noise at which reliable computation is possible     

Moment space upper and lower error bounds for digital systems with intersymbol interference

A method for the evaluation of upper and lower bounds to the error probability of a linear pulse-amplitude modulation (PAM) system with bounded intersymbol interference and additive Gaussian noise is obtained via an isomorphism theorem from the theory of moment spaces. These upper and lower bounds are seen to be equivalent to upper and lower envelopes of some compact convex body generated from a set of kernel functions. Depending on the selection of these kernels and their corresponding moments, different classes of bounds are obtained. In this paper, upper and lower bounds that depend on the absolute moment of the intersymbol interference random variable, the second moment, the fourth moment, and an "exponential moment" are found by analytical, graphical, or iterative approaches. We study in detail the exponential moment case and obtain a family of new upper and a family of new lower bounds. Within each family, expressions for these bounds are given explicitly as a function of an arbitrary real-valued parameter. For two channels of interest, upper and lower bounds are evaluated and compared. Results indicate these bounds to be tight and useful.     

Some simple bounds on the symmetric capacity and outage probabilityfor QAM wireless channels with Rice and Nakagami fadings

In this article, quickly computable upper and lower bounds are presented on the symmetric capacity of flat-faded Rice and Nakagami channels with side information (SI) for data-transmissions via finite-size quadrature amplitude modulation (QAM) constellations. The proposed bounds exhibit the appealing feature to be tight and asymptotically exact both for high and low signal-to-noise ratios (SNRs). Furthermore, exponentially tight Chernoff-like formulas are also presented for an analytical evaluation of the resulting system outage probabilities when interleaved packet transmissions are carried out     

Channel assignment algorithms satisfying cochannel and adjacent channel reuse constraints in cellular mobile networks

Improved channel assignment algorithms for cellular networks were designed by modeling the interference constraints in terms of a hypergraph. However, these algorithms only considered cochannel reuse constraints. Receiver filter responses impose restrictions on simultaneous adjacent channel usage in the same cell or in neighboring cells. We first present some heuristics for designing fixed channel assignment algorithms with a minimum number of channels satisfying both cochannel and adjacent channel reuse constraints. An asymptotically tight upper bound for the traffic carried by the system in the presence of arbitrary cochannel and adjacent channel use constraints was developed by Deora (1995). However, this bound is computationally intractable even for small systems like a regular hexagonal cellular system of 19 cells. We have obtained approximations to this bound using the optimal solutions for cochannel reuse constraints only and a further graph theoretic approach. Our approximations are computationally much more efficient and have turned out to track very closely the exact performance bounds in most cases of interest.     

Error bounds for the nonlinear filtering of signals with smalldiffusion coefficients

New upper and lower bounds for the nonlinear filtering problem are presented. The lower bounds are especially useful in the region of small diffusion coefficients where previously known bounds are inefficient. The upper and lower bounds are shown to be tight. An example demonstrating the tightness of the bounds is presented     

MAP estimation via agreement on trees: message-passing and linear programming

We develop and analyze methods for computing provably optimal maximum a posteriori probability (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is tight if and only if all the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: a) a tree-relaxed linear program (LP), which is derived from the Lagrangian dual of the upper bounds; and b) a tree-reweighted max-product message-passing algorithm that is related to but distinct from the max-product algorithm. In this way, we establish a connection between a certain LP relaxation of the mode-finding problem and a reweighted form of the max-product (min-sum) message-passing algorithm.     

Bounds on the Sum Capacity of Synchronous Binary CDMA Channels

In this paper, we obtain a family of lower bounds for the sum capacity of code-division multiple-access (CDMA) channels assuming binary inputs and binary signature codes in the presence of additive noise with an arbitrary distribution. The envelope of this family gives a relatively tight lower bound in terms of the number of users, spreading gain, and the noise distribution. The derivation methods for the noiseless and the noisy channels are different but when the noise variance goes to zero, the noisy channel bound approaches the noiseless case. The behavior of the lower bound shows that for small noise power, the number of users can be much more than the spreading gain without any significant loss of information (overloaded CDMA). A conjectured upper bound is also derived under the usual assumption that the users send out equally likely binary bits in the presence of additive noise with an arbitrary distribution. As the noise level increases, and/or, the ratio of the number of users and the spreading gain increases, the conjectured upper bound approaches the lower bound. We have also derived asymptotic limits of our bounds that can be compared to a formula that Tanaka obtained using techniques from statistical physics; his bound is close to that of our conjectured upper bound for large scale systems.     

On the capacity of frequency-flat and frequency-selective Rician MIMO channels with single-ended correlation

This paper considers the ergodic capacity of spatially-correlated Rician MIMO channels. We address the case where the Rician component has a single dominant path and where the correlation occurs at one end of the MIMO link. We derive upper bounds which are tight for all signal to noise ratios (SNR), and lower bounds which converge to the exact capacity at high SNR. For frequency-flat channels we investigate the capacity variation with Rician K-factor and correlation. For frequency-selective channels we also examine the effect of the total angle spread.     

Attenuation by a lightning protection system of induced voltagesdue to direct strikes to a building

This paper deals with induced transient voltages on electric circuits inside a protected building due to direct lightning strikes. The prediction of these overvoltages is a mandatory requirement for every EMC design of the installations inside the stricken building. The maximum level of expected transients and the efficiency of their attenuation by different configurations of a lightning protection system (LPS) are evaluated by a new simplified approach. The results are compared with those obtained by a complete circuit prediction model. A loop transfer impedance is defined as the ratio between the open end voltage induced in metal loops and the injected lightning current. This impedance is used to set the upper and lower bounds of the frequency spectra of the voltages induced in the loops internal to the building. The results are helpful in locating critical positions of circuits and devices within the volume protected by a LPS     

Exponential-type bounds on the generalized Marcum Q-function withapplication to error probability analysis over fading channels

Strict upper and lower bounds of exponential-type are derived for the generalized (mth order) Marcum Q-function which enable simple evaluation of a tight upper bound on the average bit-error probability performance of a wide class of noncoherent and differentially coherent communication systems operating over generalized fading channels. For the case of frequency selective fading with arbitrary statistics per independent fading path, the resulting upper hound on performance is expressed in the form of a product of moment generating functions of the instantaneous power random variables that characterize these paths     

Bounds for Queue Lengths in a Contention Packet Broadcast System

A finite number of users communicating through a broadcast channel is considered. Each user has a buffer of infinite capacity, and a user randomly accesses the channel (ALOHA-type protocol). Moreover, only one packet per user might be sent in an access time. Both symmetric and asymmetric models are considered; that is, we assume either indistinguishable or distinguishable users. An exact analysis of the queue lengths in that type of system is not now available, and therefore, based on some algebraic studies, we shall present some lower and some upper bounds for the average queue lengths. These bounds are quite tight for a small number of users and acceptable for a wide range of input parameters in the symmetric case. In the asymmetric case the bounds are acceptable only for light input traffic and a small number of users.     

Analysis of power losses for instantaneous compensation of three-phase four-wire systems

This paper deals with the effect that the instantaneous compensation in three-phase four-wire systems, including or not the compensation of the neutral current, has on the supply line power losses. Thus, for three-phase circuits, the instantaneous compensation criterion has been established based on the instantaneous power theory. According to the instantaneous value concept the noninstantaneous power current is reduced, without altering the instantaneous active power. Two approaches are marked in this paper for instantaneous compensation: the first one is for eliminating the total noninstantaneous power current but the neutral current can still flow. The second one for eliminating the modified noninstantaneous power current, thus the neutral current component is compensated. It demonstrates that, in common situations of medium and low relative-values of the zero-sequence voltage, the total losses (line and neutral losses) obtained with the second approach are lower than those obtained with the first approach. The same results are obtained when a criterion based on the average value concept is used. Simulated and experimental results are obtained to confirm the theoretical properties and to show the compensator performance.     

Using SAT-based techniques in power estimation

Recent algorithmic advances in Boolean satisfiability (SAT), along with highly efficient solver implementations, have enabled the successful deployment of SAT technology in a wide range of applications domains, and particularly in electronic design automation (EDA). SAT is increasingly being used as the underlying model for a number of applications in EDA. This paper describes how to formulate two problems in power estimation of CMOS combinational circuits as SAT problems or 0–1 integer linear programming (ILP). In these circuits, it was proven that maximizing dissipation is equivalent to maximizing gate output activity, appropriately weighted to account for differing load capacitances. The first problem in this work deals with identifying an input vector pair that maximizes the weighted circuit activity. In the second application we attempt to find an estimate for the maximum power-up current in circuits where power cut-off or gating techniques are used to reduce leakage current. Both problems were successfully formulated as SAT problems. SAT-Based and generic Integer Linear Programming (ILP) solvers are then used to find a solution. The experimental results obtained on a large number of benchmark circuits provide promising evidence that the proposed complete approach is both viable and useful and outperforms the random approach.