waashk/dblp huggingface dataset:
data synchronization with timing: the variable-rate case. this paper extends the theory of data synchronization with timing for fixed-rate codes, previously developed by the authors, to the variable-rate case. given a source code, a class of synctiming codes called variable-rate cascaded (vrc) codes is considered that "wrap around" the source code in such a way as to enable the decoder to not only resynchronize rapidly when the encoded bits are corrupted by insertion, deletion, or substitution errors, but also produce estimates of the time indices of the data symbols encoded by the source code. the estimates of the time indices are modulo-t reductions of the actual time indices, for some integer t called the timing span of the code. these sync-timing codes are analyzed on the basis of the maximum timing span achievable for a given coding rate r and permissible resynchronization delay d. it is shown that the timing span of vrc codes is upper-bounded by 2d(1-r)+o(d), and that this upper bound is achievable asymptotically in d. this exponential rate of growth of timing span with delay is the same as that found previously for certain fixed-rate sync-timing codes, e.g., (fixed-rate) cascaded codes.
asymptotic-information-lossless designs and the diversity-multiplexing tradeoff. it is known that neither the alamouti nor the v-blast scheme achieves the zheng-tse diversity-multiplexing tradeoff (dmt) of the multiple-input multiple-output (mimo) channel. with respect to the dmt curve, the alamouti scheme achieves the point corresponding to maximum diversity gain only, whereas v-blast meets only the point corresponding to maximum multiplexing gain. it is also known that d-blast achieves the optimal dmt for n transmit and n receive antennas, but only under the assumption that the leading and trailing zeros are ignored. when these zeros are taken into account, d-blast achieves the point corresponding to zero multiplexing gain, but not the point corresponding to zero diversity gain. the first scheme to achieve the dmt is the coding scheme of yao and wornell for the case of two transmit and two receive antennas. in this paper, we introduce the notion of an asymptotic-information-lossless (aill) design and obtain a necessary and sufficient condition under which a design is aill. analogous to the result that full-rank designs achieve the point corresponding to the zero multiplexing gain of the optimal dmt curve, we show aill to be a necessary and sufficient condition for a design to achieve the point on the dmt curve corresponding to zero diversity gain. we also derive a lower bound on the tradeoff achieved by designs from field extensions and show that the tradeoff is very close to the optimal tradeoff in the case of a single receive antenna. a lower bound to the tradeoff achieved by designs from division algebras is presented which indicates that these designs achieve both extreme points (corresponding to zero diversity and zero multiplexing gain) of the optimal dmt curve. finally, we present simulations results for n transmit and n receive antennas, for n = 2,3,4, which suggest that designs from division algebras are likely to have the property of being dmt achieving.
the capacity of channels with feedback. in this paper, we introduce a general framework for treating channels with memory and feedback. first, we prove a general feedback channel coding theorem based on massey's concept of directed information. second, we present coding results for markov channels. this requires determining appropriate sufficient statistics at the encoder and decoder. we give a recursive characterization of these sufficient statistics. third, a dynamic programming framework for computing the capacity of markov channels is presented. fourth, it is shown that the average cost optimality equation (acoe) can be viewed as an implicit single-letter characterization of the capacity. fifth, scenarios with simple sufficient statistics are described. sixth, error exponents for channels with feedback are presented.
on the expected codeword length per symbol of optimal prefix codes for extended sources. given a discrete memoryless source x, it is well known that the expected codeword length per symbol ln(x) of an optimal prefix code for the extended source xn converges to the source entropy as n approaches infinity. however, the sequence ln(x) need not be monotonic in n, which implies that the coding efficiency cannot be increased by simply encoding a larger block of source symbols (unless the block length is appropriately chosen). as the encoding and decoding complexity increases exponentially with the block length, from a practical perspective it is useful to know when an increase in the block length guarantees a decrease in the expected codeword length per symbol. while this paper does not provide a complete answer to that question, we give some properties of ln(x) and obtain for each n ≥ 1 and nondyadic p1n (p1 is the probability of the most likely source symbol) an integer k* for which lkn(x) < ln(x) for all k ≥ k*, implying that the coding efficiency of encoding blocks of length kn is higher than that of encoding blocks of length n for all k ≥ k*. this question is simpler in part because lkn(x) ≤ ln(x) is guaranteed for all n ≥ 1 and k ≥ 1, but our results distinguish scenarios where increasing the multiplicative factor guarantees strict improvement. these results extend and generalize those by montgomery and kumar.
information theoretic bounds for compound mimo gaussian channels. in this paper, achievable rates for compound gaussian multiple-input-multiple-output (mimo) channels are derived. two types of channels, modeled in the frequency domain, are considered when: 1) the channel frequency response matrix h belongs to a subset of h∞ normed linear space, and 2) the power spectral density (psd) matrix of the gaussian noise belongs to a subset of l1 space. the achievable rates of these two compound channels are related to the maximin of the mutual information rate. the minimum is with respect to the set of all possible h matrices or all possible psd matrices of the noise. the maximum is with respect to all possible psd matrices of the transmitted signal with bounded power. for the compound channel modeled by the set of h matrices, it is shown, under certain conditions, that the code for the worst case channel can be used for the whole class of channels. for the same model, the water-filling argument implies that the larger the set of matrices h, the smaller the bandwidth of the transmitted signal will be. for the second compound channel, the explicit relation between the maximizing psd matrix of the transmitted signal and the minimizing psd matrix of the noise is found. two psd matrices are related through a riccati equation, which is always present in kalman filtering and liner-quadratic gaussian control problems.
error event characterization on 2-d isi channels. in this paper, we analyze the distance properties of two-dimensional (2-d) intersymbol interference (isi) channels, in particular the 2-d partial response class-1 (pr1) channel which is an extension of the one-dimensional (1-d) pr1 channel. the minimum squared-euclidean distance of this channel is proved to be 4 and a complete characterization of the squared-euclidean distance 4 error events is provided. as for 1-d channels, we can construct error-state diagrams for 2-d channels to help characterize error events. we propose an efficient error event search algorithm operating on the error-state diagram that is applicable to any 2-d channel.
spectrum management for interference-limited multiuser communication systems. consider a multiuser communication system in a frequency selective environment whereby users share a common spectrum and can interfere with each other. assuming gaussian signaling and no interference cancelation, we study optimal spectrum sharing strategies for the maximization of sum-rate under separate power constraints for individual users. since the sum-rate function is nonconcave in terms of the users' power allocations, there can be multiple local maxima for the sum-rate maximization problem in general. in this paper, we show that, if the normalized crosstalk coefficients are larger than a given threshold (roughly equal to 1/2), then the optimal spectrum sharing strategy is frequency division multiple access (fdma). in case of arbitrary positive crosstalk coefficients, if each user's power budget exceeds a given threshold, then fdma is again sum-rate optimal, at least in a local sense. in addition, we show that the problem of finding the optimal fdma spectrum allocation is np-hard, implying that the general problem of maximizing sum-rate is also np-hard, even in the case of two users. we also propose several simple distributed spectrum allocation algorithms that can approximately maximize sum-rates. numerical results indicate that these algorithms are efficient and can achieve substantially larger sum-rates than the existing iterative waterfilling solutions, either in an interference-rich environment or when the users' power budgets are sufficiently high.
doubly-generalized ldpc codes: stability bound over the bec. the iterative decoding threshold of low-density parity-check (ldpc) codes over the binary erasure channel (bec) fulfills an upper bound depending only on the variable and check nodes with minimum distance 2. this bound is a consequence of the stability condition, and is here referred to as stability bound. in this paper, a stability bound over the bec is developed for doubly-generalized ldpc codes, where variable and check nodes can be generic linear block codes, assuming maximum a posteriori erasure correction at each node. it is proved that also in this generalized context the bound depends only on the variable and check component codes with minimum distance 2. a condition is also developed, namely, the derivative matching condition, under which the bound is achieved with equality. the stability bound leads to consider single parity-check codes used as variable nodes as an appealing option to overcome common problems created by generalized check nodes.
low-snr capacity of noncoherent fading channels. discrete-time rayleigh-fading single-input single-output (siso) and multiple-input multiple-output (mimo) channels are considered, with no channel state information at the transmitter or the receiver. the fading is assumed to be stationary and correlated in time, but independent from antenna to antenna. peak-power and average-power constraints are imposed on the transmit antennas. for mimo channels, these constraints are either imposed on the sum over antennas, or on each individual antenna. for siso channels and mimo channels with sum power constraints, the asymptotic capacity as the peak signal-to-noise ratio (snr) goes to zero is identified; for mimo channels with individual power constraints, this asymptotic capacity is obtained for a class of channels called transmit separable channels. the results for mimo channels with individual power constraints are carried over to siso channels with delay spread (i.e., frequency-selective fading).
nonlinear estimation for a class of systems. this paper considers nonlinear estimation problems for classes of models, and employs relative entropy to describe the uncertainty classes. two optimization problems are formulated on general banach spaces, and their solutions are sought: 1) when the transition probability between the signal to be estimated x and the measurement y or stochastic kernel is unknown, and 2) when the joint probability induced by the random variables (rvs) x,y is unknown. for both problems, the uncertainty is described by a relative entropy constraint between the unknown distribution and a fixed nominal distribution. the results include existence of the optimal measures using weak convergence techniques, and properties associated with the estimate of the true distribution. classical examples are chosen to illustrate the applicability of the results.
on fast-decodable space-time block codes. we focus on full-rate, fast-decodable space-time block codes (stbcs) for 2×2 and 4×2 multiple-input multiple-output (mimo) transmission. we first derive conditions and design criteria for reduced-complexity maximum-likelihood (ml) decodable 2×2 stbcs, and we apply them to two families of codes that were recently discovered. next, we derive a novel reduced-complexity 4×2 stbc, and show that it outperforms all previously known codes with certain constellations.
interference alignment on the deterministic channel and application to fully connected gaussian interference networks. an interference alignment example is constructed for the deterministic channel model of the k-user interference channel. the deterministic channel example is then translated into the gaussian setting, creating the first known example of a fully connected gaussian k-user interference network with single antenna nodes, real, nonzero and constant channel coefficients, and no propagation delays where the degrees of freedom outerbound is achieved. an analogy is drawn between the propagation delay based interference alignment examples and the deterministic channel model which also allows similar constructions for the two-user x channel as well.
orthogonal space-time block codes with sphere packing. orthogonal designs have received considerable attention in the development of efficient modulation and coding methods for future multi-antenna wireless communication systems due to their special properties. in this paper, we propose a class of space-time block codes constructed by combining orthogonal designs with sphere packing for an arbitrary number of transmit antennas. the structure of the orthogonal designs is exploited to guarantee full diversity, and sphere packing is used to improve the coding advantage. space-time block code construction from block-orthogonal designs is also considered: the full-diversity property is ensured by rotating the sphere packing underlying the code, and the optimal rotation angle is determined for a class of sphere packing. code design examples are provided for two and four transmit antennas and various transmission rates. the simulation results show that by jointly designing the symbols in the orthogonal designs, the performance of the block codes can be significantly increased.
achieving the empirical capacity using feedback: memoryless additive models. we address the problem of universal communications over an unknown channel with an instantaneous noiseless feedback, and show how rates corresponding to the empirical behavior of the channel can be attained, although no rate can be guaranteed in advance. first, we consider a discrete modulo-additive channel with alphabet x, where the noise sequence zn is arbitrary and unknown and may causally depend on the transmitted and received sequences and on the encoder's message, possibly in an adversarial fashion. although the classical capacity of this channel is zero, we show that rates approaching the empirical capacity |x| - hemp (zn) can be universally attained, where hemp (zn) is the empirical entropy of zn. for the more general setting, where the channel can map its input to an output in an arbitrary unknown fashion subject only to causality, we model the empirical channel actions as the modulo-addition of a realized noise sequence, and show that the same result applies if common randomness is available. the results are proved constructively, by providing a simple sequential transmission scheme approaching the empirical capacity.
on certain large random hermitian jacobi matrices with applications to wireless communications. in this paper we study the spectrum of certain large random hermitian jacobi matrices. these matrices are known to describe certain communication setups. in particular, we are interested in an uplink cellular channel which models mobile users experiencing a soft-handoff situation under joint multicell decoding. considering rather general fading statistics we provide a closed-form expression for the per-cell sum-rate of this channel in high signal-to-noise ratio (snr), when an intra-cell time-division multiple-access (tdma) protocol is employed. since the matrices of interest are tridiagonal, their eigenvectors can be considered as sequences with second-order linear recurrence. therefore, the problem is reduced to the study of the exponential growth of products of two-by-two matrices. for the case where k users are simultaneously active in each cell, we obtain a series of lower and upper bound on the high-snr power offset of the per-cell sum-rate, which are considerably tighter than previously known bounds.
distributed opportunistic scheduling for ad hoc networks with random access: an optimal stopping approach. in this paper, we study distributed opportunistic scheduling (dos) in an ad hoc network, where many links contend for the same channel using random access. in such a network, dos involves a process of joint channel probing and distributed scheduling. due to channel fading, the link condition corresponding to a successful channel probing could be either good or poor. in the latter case, further channel probing, although at the cost of additional delay, may lead to better channel conditions and hence yield higher throughput. the desired tradeoff boils down to judiciously choosing the optimal stopping rule for channel probing and distributed scheduling. in this paper, we pursue a rigorous characterization of the optimal strategies from two perspectives, namely, a network-centric perspective and a user-centric perspective. we first consider dos from a network-centric point of view, where links cooperate to maximize the overall network throughput. using optimal stopping theory, we show that the optimal scheme for dos turns out to be a pure threshold policy, where the rate threshold can be obtained by solving a fixed-point equation. we further devise iterative algorithms for computing the threshold. we also generalize the studies to take into account fairness requirements. next, we explore dos from a user-centric perspective, where each link seeks to maximize its own throughput. we treat the problem of threshold selection across different links as a noncooperative game. we explore the existence and uniqueness of the nash equilibrium, and show that the nash equilibrium can be approached by the best response strategy. since the best response strategy requires message passing from neighboring nodes, we then develop an online stochastic iterative algorithm based on local observations only, and establish its convergence to the nash equilibrium. because there is an efficiency loss at the nash equilibrium, we then study pricing-based mechanisms to mitigate the loss. our results reveal that rich physical layer/mac layer (phy/mac) diversities are available for exploitation in ad hoc networks.we believe that these initial steps open a new avenue for channel-aware distributed scheduling.
new m -ary sequence families with low correlation and large size. in this paper, we construct four m-ary sequence families from a power residue sequence of odd prime period p and its constant multiple sequences using the shift-and-add method, when m is a divisor of p - 1. we show that the maximum correlation values of the proposed sequence families are upper-bounded by 2√p+5 or 3√p+4. in addition, we prove that the linear complexity of each sequence in the proposed families is either p-1 or p-p-1/m-1. we also construct an m-ary sequence family from sidel'nikov sequences of period pm - 1. by applying the same method, when m is a divisor of pm - 1. the proposed sequence family fs has larger size than the known m-ary sidel'nikov sequence families, whereas they all have the same upper bound on the maximum correlation.
low-density graph codes that are optimal for binning and coding with side information. in this paper, we describe and analyze the source and channel coding properties of a class of sparse graphical codes based on compounding a low-density generator matrix (ldgm) code with a low-density parity-check (ldpc) code. our first pair of theorems establishes that there exist codes from this ensemble, with all degrees remaining bounded independently of block length, that are simultaneously optimal for both channel coding and source coding with binary data when encoding and decoding are performed optimally. more precisely, in the context of lossy compression, we prove that finite-degree constructions can achieve any pair (r, d) on the rate-distortion curve of the binary symmetric source. in the context of channel coding, we prove that the same finite-degree codes can achieve any pair (c, p) on the capacity-noise curve of the binary symmetric channel (bsc). next, we show that our compound construction has a nested structure that can be exploited to achieve the wyner-ziv bound for source coding with side information (scsi), as well as the gelfand-pinsker bound for channel coding with side information (ccsi). although the results described here are based on optimal encoding and decoding, the proposed graphical codes have sparse structure and high girth that renders them well suited to message passing and other efficient decoding procedures.
diversity gains of power control with noisy csit in mimo channels. a multiantenna channel with partial channel state information at the transmitter (csit) is studied. the partial csit takes the form of the channel matrix corrupted by additive white gaussian noise (awgn) with a variance that is assumed to decay as a power of the signal-to-noise ratio (snr). it is shown that under a long-term power constraint and in the regime of asymptotically high snr, a large diversity gain over the channel can be achieved by using rarely a high power at the transmitter that compensates for bad channel realizations. examples relating the diversity gain of the systems with the channel doppler bandwidth are discussed.
a constant bound on throughput improvement of multicast network coding in undirected networks. recent research in network coding shows that, joint consideration of both coding and routing strategies may lead to higher information transmission rates than routing only. a fundamental question in the field of network coding is: how large can the throughput improvement due to network coding be? in this paper, we prove that in undirected networks, the ratio of achievable multicast throughput with network coding to that without network coding is bounded by a constant ratio of 2, i.e., network coding can at most double the throughput. this result holds for any undirected network topology, any link capacity configuration, any multicast group size, and any source information rate. this constant bound 2 represents the tightest bound that has been proved so far in general undirected settings, and is to be contrasted with the unbounded potential of network coding in improving multicast throughput in directed networks.
noise enhanced nonparametric detection. this paper investigates potential improvement of nonparametric detection performance via addition of noise and evaluates the performance of noise modified nonparametric detectors. detection performance comparisons are made between the original detectors and noise modified detectors. conditions for improvability as well as the optimum additive noise distributions of the widely used sign detector, the wilcoxon detector, and the dead-zone limiter detector are derived. finally, a simple and fast learning algorithm to find the optimal noise distribution solely based on received data is presented. a near-optimal solution can be found quickly based on a relatively small dataset.