We consider a network of K interfering transmitter-receiver pairs, where each node has N antennas and at most one beam is transmitted per user. We investigate the asymptotic performance of different beamforming strategies, as characterized by the slope and y-axis intercept (or offset) of the high signal-to-noise-ratio (SNR) sum rate asymptote. It is known that a slope (or multiplexing gain) of 2N-1 is achievable with interference alignment. On the other hand, a strategy achieving a slope of only N might allow for a significantly higher offset. Assuming that the number of fully aligned beamformer sets that achieve a slope of 2N-1 is finite for a given channel realization, we approximate the average offset when the best out of a large number L of these sets is selected. We also derive a simple large system approximation for the sum rate of a successive beam allocation scheme when K=N. We show that both approximations accurately predict simulated results for moderate system dimensions and characterize the large-system asymptotes for different relationships between L and N.

We study distributed algorithms for updating transmit preceding matrices for a two-user Multi-Input/Multi-Output (MIMO) interference channel. Our objective is to maximize the sum rate with linear Minimum Mean Squared Error (MMSE) receivers, treating the interference as additive Gaussian noise. An iterative approach is considered in which given a set of preceding matrices and powers, each receiver announces an interference price (marginal decrease in rate due to an increase in interference) for each received beam, corresponding to a column of the precoding matrix. Given the interference prices from the neighboring receiver, and also knowledge of the appropriate cross-channel matrices, the transmitter can then update the beams and powers to maximize the rate minus the interference cost. Variations on this approach are presented in which beams are added sequentially (and then fixed), and in which all beams and associated powers are adjusted at each iteration. Numerical results are presented, which compare these algorithms with iterative water-filling (which requires no information exchange), and a centralized optimization algorithm, which finds locally optimal solutions. Our results show that the distributed algorithms perform close to the centralized algorithm, and by adapting the rank of the precoder matrices, achieve the optimal high-SNR slope.

Non-linear precoding for point-to-point (P2P) multiple-input multiple-output (MIMO) systems is considered. First, the minimum mean square error (MMSE) optimal vector precoding (VP) is presented for different receiver structures, viz., weighted identity matrix, diagonal matrix, weighted unitary matrix, and matrix without particular structure. Whereas the former two structures can also be applied to the vector broadcast channel, the latter two are only realizable for cooperative receivers. Second, VP is derived that minimizes the MSE but is restricted to maximize the mutual information of the MIMO channel. Third, the corresponding Tomlinson-Harashima precoding (THP) is found by applying the nearest-plane approximation to the computation of the perturbation signal. The resulting maximum mutual information THP clearly outperforms the state-of-the-art P2P-MIMO THP based on the generalized triangular decomposition (GTD) with respect to MSE and BER.

For the single-group multicast scenario, where K users are served with the same data by a base station equipped with N antennas, we present two beamforming algorithms which outperform state-of-the-art multicast filters and feature a drastically reduced complexity at the same time. For the power minimization problem, where QoS constraints need to be satisfied, we introduce a successive beamforming filter computation approach aiming at satisfying at least one additional SNR constraint per orthogonal filter update. As long as the number of users K is smaller than the number N of transmit antennas, this procedure delivers excellent results. Our second approach is an iterative update algorithm for the max-min problem subject to a limitation of the transmit power. Given a low-complexity initialization beamformer, we search within the local vicinity of this filter vector for a filter-update preserving the transmit power and achieving a larger minimum SNR. To this end, we improve the weakest user's SNR during each iteration and keep on applying this procedure as long as the updates increase the smallest SNR. Otherwise, we adapt the step-size and continue investigating the local vicinity. It turns out that this novel approach is superior to existing state-of-the-art multicast beamformers for an arbitrary number of users.

In this paper, we present a novel algorithm for determining the sum-rate optimal transmit covariance matrices for the MIMO broadcast channel. Instead of optimizing the covariances directly, our algorithm operates on the preceding matrices, i.e., the square roots of the covariances. As a result, no eigenvalue decompositions are required in the iterations, and the complexity per iteration is significantly lower. A look at the convergence over the required number of computations shows a visible advantage over the state-of-the-art sum power iterative waterfilling algorithm. Also, our algorithm allows us to find the optimal sum-rate for an arbitrarily limited number of data streams per user. Finally, with a simple modification, our algorithm can also be used for sum-MSE minimization.

We address the problem of jointly optimizing the pre coder and the receivers in a multi-user broadcast system for a linear and nonlinear transmitter under sum mean square error (MSE) minimization. By means of alternating optimization (AO), we find an iterative algorithm which always converges to the global optimum. In addition to an elegant initialization of the receivers' weights, we come up with expressions for the speed of convergence. Our algorithm is applicable to both single-antenna and multi-antenna receivers and can be combined with nonlinear Tomlinson-Harashima precoding (THP). For THP, the precoding order can easily be included in the AO. Moreover, we show that for sum MSE minimization the user-wise channels are not necessarily diagonalized and give some ideas how this fact can be exploited

We derive the minimum mean square error (MMSE) solution to vector precoding for frequency flat multiuser scenarios with a centralized multi-antenna transmitter. The receivers employ a modulo operation, giving the transmitter the additional degree of freedom to choose a perturbation vector. Similar to existing vector precoding techniques, the optimum perturbation vector is found with a closest point search in a lattice. The proposed MMSE vector precoder does not, however, search for the perturbation vector resulting in the lowest transmit energy, as proposed in all previous contributions on vector precoding, but finds an optimum compromise between noise enhancement and residual interference. We present simulation results showing that the proposed technique outperforms existing vector precoders, as well as the MMSE Tomlinson-Harashima precoder.

A reactive system can be specified by a labelled transition system, which indicates static structure, along with temporal-logic formulas, which assert dynamic behaviour. But refining the former while preserving the latter can be difficult, because: (i) Labelled transition systems are ‘total’ – characterised up to bisimulation – meaning that no new transition structure can appear in a refinement. (ii) Alternatively, a refinement criterion not based on bisimulation might generate a refined transition system that violates the temporal properties. In response, Larsen and Thomson proposed modal transition systems, which are ‘partial’, and defined a refinement criterion that preserved formulas in Hennessy–Milner logic. We show that modal transition systems are, up to a saturation condition, exactly the mixed transition systems of Dams that meet a mix condition, and we extend such systems to non-flat state sets. We then solve a domain equation over the mixed powerdomain whose solution is a bifinite domain that is universal for all saturated modal transition systems and is itself fully abstract when considered as a modal transition system. We demonstrate that many frameworks of partial systems can be translated into the domain: partial Kripke structures, partial bisimulation structures, Kripke modal transition systems, and pointer-shape-analysis graphs.

Widely used in object-oriented programming, the Unified Modelling Language (UML) is largely ignored by the declarative programming community. this paper attempts to introduce the UML and provide reasons for its adoption by declarative programmers as both a design methodology and as a novel application area.

This expository paper simplifies and clarifies Steffen's depiction of data flow analysis (d.f.a.) as model checking: By employing abstract interpretation (a.i.) to generate program traces and by utilizing Kozen's modal mu-calculus to express trace properties, we express in simplest possible terms that a d.f.a. is a model check of a program's a.i. trace. In particular, the classic flow equations for bit-vector-based d.f.a.s reformat trivially into modal mu-Calculus formulas. A surprising consequence is that two of the classical d.f.a.s are exposed as unsound; this problem is analyzed and simply repaired. In the process of making the above discoveries, we clarify the relationship between a.i. and d.f.a. in terms of the often-misunderstood notion of collecting semantics and we highlight how the research areas of flow analysis, abstract interpretation, and model checking have grown together.

Sufficient criteria are given for replacing all occurrences of the store argument in a Scott-Strachey denotational definition of a programming language by a single global variable. The criteria and transformation are useful for transforming denotational definitions into compilers and interpreters for imperative machines, for optimizing applicative programs, and for judging the suitability of semantic notations for describing imperative languages. An example transformation of a semantics of a repeat-loop language to one which uses a global store variable is given to illustrate the technique.