We consider a set of transmitter-receiver pairs, or links, that share a wireless medium and address the problem of emptying backlogged queues with given initial size at the transmitters in minimum time. The problem amounts to determining activation subsets of links, and their time durations, to form a minimum-time schedule. Scheduling in wireless networks has been studied under various formulations before. In this paper, we present fundamental insights and solution characterizations that include: 1) showing that the complexity of the problem remains high for any continuous and increasing rate function; 2) formulating and proving sufficient and necessary optimality conditions of two baseline scheduling strategies that correspond to emptying the queues using one-at-a-time or all-at-once strategies; and 3) presenting and proving the tractability of the special case in which the transmission rates are functions only of the cardinality of the link activation sets. These results are independent of physical-layer system specifications and are valid for any form of rate function. We then develop an algorithmic framework for the solution to this problem. The framework encompasses exact as well as sub-optimal, but fast, scheduling algorithms, all under a unified principle design. Through computational experiments, we finally investigate the performance of several specific algorithms from this framework.
The use of large-scale antenna arrays can bring substantial improvements in energy and/or spectral efficiency to wireless systems due to the greatly improved spatial resolution and array gain. Recent works in the field of massive multiple-input multiple-output (MIMO) show that the user channels decorrelate when the number of antennas at the base stations (BSs) increases, thus strong signal gains are achievable with little interuser interference. Since these results rely on asymptotics, it is important to investigate whether the conventional system models are reasonable in this asymptotic regime. This paper considers a new system model that incorporates general transceiver hardwareimpairments at both the BSs (equipped with large antenna arrays) and the single-antenna user equipments (UEs). As opposed to the conventional case of ideal hardware, we show that hardwareimpairments create finite ceilings on the channel estimation accuracy and on the downlink/uplink capacity of each UE. Surprisingly, the capacity is mainly limited by the hardware at the UE, while the impact of impairments in the large-scale arrays vanishes asymptotically and interuser interference (in particular, pilot contamination) becomes negligible. Furthermore, we prove that the huge degrees of freedom offered by massive MIMO can be used to reduce the transmit power and/or to tolerate larger hardware impairments, which allows for the use of inexpensive and energy-efficient antenna elements.
The equivocation of the key for a simple substitution cipher is upper and lower hounded, when the message source is memoryless. The hounds are shown to be exponentially tight. The results are compared with random ciphering. It is observed that the exponential behavior of the equivocation of the key is not determined by the redundancy in the message source, but by the symbol probabilities which are closest in a certain sense.
Unconditionally secure message authentication is an important part of Quantum Cryptography (QC). We analyze security effects of using a key obtained from QC for authentication purposes in later rounds of QC. In particular, the eavesdropper gains partial knowledge on the key in QC that may have an effect on the security of the authentication in the later round. Our initial analysis indicates that this partial knowledge has little effect on the authentication part of the system, in agreement with previous results on the issue. However, when taking the full QC protocol into account, the picture is different. By accessing the quantum channel used in QC, the attacker can change the message to be authenticated. This together with partial knowledge of the key does incur a security weakness of the authentication. The underlying reason for this is that the authentication used, which is insensitive to such message changes when the key is unknown, becomes sensitive when used with a partially known key. We suggest a simple solution to this problem, and stress usage of this or an equivalent extra security measure in QC.
A sequence of q-ary cyclic codes is analyzed. For each finite field GF (q), q=4, there is a code with parameters [n, k, d, q] = [q(q-1)+1, q(q-1)-6, 6,q]. All these codes are n-, k-, and d-optimal, with only one exception. The dual codes are considered. Their true minimum distances are calculated in the range 4=q=32.
Information age is a recently introduced metric to represent the freshness of information in communication systems. We investigate age minimization in a wireless network and propose a novel approach of optimizing the scheduling strategy to deliver all messages as fresh as possible. Specifically, we consider a set of links that share a common channel. The transmitter at each link contains a given number of packets with time stamps from an information source that generated them. We address the link transmission scheduling problem with the objective of minimizing the overall age. This minimum age scheduling problem (MASP) is different from minimizing the time or the delay for delivering the packets in question. We model the MASP mathematically and prove it is NP-hard in general. We also identify tractable cases as well as optimality conditions. An integer linear programming formulation is provided for performance benchmarking. Moreover, a steepest age descent algorithm with better scalability is developed. Numerical study shows that, by employing the optimal schedule, the overall age is significantly reduced in comparison to other scheduling strategies.
A new implementation is presented for the optimum likelihood ratio detector for stationary Gaussian signals in white Gaussian noise that uses only two causal time-invariant filters. This solution also has the advantage that fast algorithms based on the Levinson and Chandrasekhar equations can he used for the determination of these time-invariant filters. By using a notion of "closeness to stationarity,' there is a natural extension of the above results for nonstationary signal processes.
This paper investigates linear precoding over nonsingular linear channels with additive white Gaussian noise, with lattice-type inputs. The aim is to maximize the minimum distance of the received lattice points, where the precoder is subject to an energy constraint. It is shown that the optimal precoder only produces a finite number of different lattices, namely perfect lattices, at the receiver. The well-known densest lattice packings are instances of perfect lattices, but are not always the solution. This is a counter-intuitive result as previous work in the area showed a tight connection between densest lattices and minimum distance. Since there are only finite many different perfect lattices, they can theoretically be enumerated offline. A new upper bound on the optimal minimum distance is derived, which significantly improves upon a previously reported bound, and is useful when actually constructing the precoders.
Traceability codes are identifiable parent property (IPP) codes with the additional requirement that Hamming distance can be used to trace a parent of a word. Traceability codes can be used for constructing digital fingerprints in order to deter users from illegally copying digital data. We construct a class of traceability codes and determine the exact parameters of some of the codes in this class.
Parameter estimation problems that can be formulated as linear regressions are quite common in many applications. Recursive (on-line, sequential) estimation of such parameters can be performed using the recursive least squares (RLS) algorithm or a stochastic gradient version of this algorithm. In this paper the convergence properties of the gradient algorithm are analyzed under the assumption that the gain tends to zero. The technique is the same as the so-called ordinary differential equation approach, but the treatment here is self-contained and includes a proof of the boundedness of the estimates. A main result is that the convergence conditions for the gradient algorithm are the same as those for the recursive least squares algorithm.
A state-space model of a second-order random process is a representation as a linear combination of a set of state-variables which obey first-order linear differential equations driven by an input process that is both white and uncorrelated with the initial values of the state-variables. Such a representation is often called a Markovian representation. There are applications in which it is useful to consider time running backwards and to obtain corresponding backwards Markovian representations. Except in one very special circumstance, these backwards representations cannot be obtained simply by just reversing the direction of time in a forwards Markovian representation. We show how this problem can be solved, give some examples, and also illustrate how the backwards model can be used to clarify certain least squares smoothing formulas.
n/a
We consider a slow fading n_{t} x n_{r} multiple-input multiple-output (MIMO) system with channel state information (CSI) at both the transmitter and receiver. Since communication in such scenarios is subject to block fading, reception reliability, quantified in terms of the achievable diversity gain, is of importance. A simple and well known precoding scheme is based upon the singular value decomposition (SVD) of the channel matrix, which transforms the MIMO channel into parallel subchannels. Despite having low maximum likelihood decoding (MLD) complexity, this SVD based precoding scheme provides a diversity gain which is limited by the diversity gain of the weakest subchannel. We therefore propose X- and YCodes, which improve the diversity gain of the SVD precoding scheme, by jointly coding information across a pair of subchannels (i.e., pairing subchannels). In particular, subchannels with high diversity gain are paired with those having low diversitygain. A pair of subchannels is jointly encoded using a 2 x 2 real matrix, which is fixed a priori and does not change with each channel realization. For X-Codes, these matrices are 2-dimensional rotation matrices parameterized by a single angle, while for Y-Codes, these matrices are 2-dimensional upper left triangular matrices. Also, since joint coding is performed only across a pair of subchannels, the joint MLD complexity remains low. In particular, the MLD complexity of Y-Codes is even lower than that of X-Codes, and is equivalent to symbol by symbol detection. Moreover, we propose X-, Y-Precoders with the same structure as X-, Y-Codes, but with encoding matrices adapted to each channel realization. With respect to the error probability performance, the optimal encoding matrices for X-, YCodes/ Precoders are derived analytically and numerically. Whencompared to other precoding schemes reported in the literature, it is observed that X-Codes/Precoders perform better in wellconditioned channels, while Y-Codes/Precoders perform better in ill-conditioned channels.
We consider Gaussian multiple-input multiple-output (MIMO) channels with discrete input alphabets. We propose a non-diagonal precoder based on the X-Codes in \cite{Xcodes_paper} to increase the mutual information. The MIMO channel is transformed into a set of parallel subchannels using Singular Value Decomposition (SVD) and X-Codes are then used to pair the subchannels. X-Codes are fully characterized by the pairings and a $2\times 2$ real rotation matrix for each pair (parameterized with a single angle). This precoding structure enables us to express the total mutual information as a sum of the mutual information of all the pairs. The problem of finding the optimal precoder with the above structure, which maximizes the total mutual information, is solved by {\em i}) optimizing the rotation angle and the power allocation within each pair and {\em ii}) finding the optimal pairing and power allocation among the pairs. It is shown that the mutual information achieved with the proposed pairing scheme is very close to that achieved with the optimal precoder by Cruz {\em et al.}, and is significantly better than Mercury/waterfilling strategy by Lozano {\em et al.}. Our approach greatly simplifies both the precoder optimization and the detection complexity, making it suitable for practical applications.
This correspondence concerns the estimation algorithm for hinging hyperplane (HH) models, a piecewise-linear model for approximating functions of several variables, suggested in Breiman (1993). The estimation algorithm is analyzed and it is shown that it is a special case of a Newton algorithm applied to a sum of squared error criterion. This insight is then used to suggest possible improvements of the algorithm so that convergence to a local minimum can be guaranteed. In addition, the way of updating the parameters in the HH model is discussed. In Breiman, a stepwise updating procedure is proposed where only a subset of the parameters are changed in each step. This connects closely to some previously suggested greedy algorithms and these greedy algorithms are discussed and compared to a simultaneous updating of all parameters.
We consider the problem of determining the maximum size of a ternary code with constant composition and Hamming weight three. We give several constructions of codes having maximum size and we also present an improvement of the Johnson bound. The results presented here solve the problem for all lengths when d = 3, as well as for lengths 7, 11, and all even lengths when d = 4.
The problem of determining the maximum size of a ternary code is considered, under the restriction that each symbol should appear a given number of times in each codeword. Upper and lower bounds on the size of such codes under Hamming metric are discussed, where the lower bounds follow from constructions of good codes. Some of the results are obtained by explicitly finding codes by computer search. A table of exact values and best known bounds on the maximum size for codes of length at most 10 is presented.