waashk/dblp huggingface dataset:
ergodic channel capacities for the amplify-and-forward half-duplex cooperative systems. in this paper, the ergodic channel capacities are established for the amplify-and-forward (af) half-duplex cooperative systems, which consist of a source node, a destination, and multiple-relay nodes. the relay nodes assist the transmission from the source node to the destination. since the channel matrices for the cooperative systems involve product of gaussian random variables, which are no longer gaussian, the approach in obtaining the ergodic channel capacity for conventional multiple-input-multiple-output (mimo) gaussian channels (telatar, 1999) is not applicable. by using a novel approach, we have arrived at the following conclusions about the ergodic channel capacities for the af cooperative systems. for the single antenna af relay systems in which all nodes are equipped with one antenna, the optimal covariance matrix of the input signals to achieve the ergodic channel capacity is diagonal, and the diagonal elements are obtained by solving optimization problems of multidimensional integrals. these diagonal entries are not all equal even if all the channel gains in the cooperative systems are independent and identically distributed (i.i.d.) gaussian with unit variance. therefore, a white input signal for the af cooperative system may not achieve the ergodic channel capacity of the system. this is in direct contrast to the case of conventional multiple-input-single-output (miso) systems having i.i.d. gaussian channel gains of unit variance, in which case, the ergodic capacity is achieved if the input covariance matrix is a scaled identity matrix. for the mimo relay system in which the nodes have multiple antennas, the input covariance matrix to achieve the ergodic capacity is block diagonal and each block diagonalizes the autocorrelation of channel matrix from the source to the destination. this is different from the case of conventional mimo systems, where the input covariance matrix to achieve the ergodic channel capacity diagonalizes the channel autocorrelation matrix of the mimo system (tulina, lozano, and verdú, 2006). if the channel gains in conventional mimo systems are correlated gaussian random variables, the input covariance matrix is a full matrix, not block diagonal; and if the channel gains are i.i.d. gaussians, the optimal input covariance matrix is a scaled identity. the observations obtained in this paper reveal useful insights of how the af cooperative systems "mimic" the conventional miso and mimo systems from the ergodic channel capacity perspective.
on the entropy rate of hidden markov processes observed through arbitrary memoryless channels. this paper studies the entropy rate of hidden markov processes (hmps) which are generated by observing a discrete-time binary homogeneous markov chain through an arbitrary memoryless channel. a fixed-point functional equation is derived for the stationary distribution of an input symbol conditioned on all past observations. while the existence of a solution to the fixed-point functional equation is guaranteed by martingale theory, its uniqueness follows from the fact that the solution is the fixed point of a contraction mapping. the entropy or differential entropy rate of the hmp can then be obtained through computing the average entropy of each input symbol conditioned on past observations. in absence of an analytical solution to the fixed-point functional equation, a numerical method is proposed in which the fixed-point functional equation is first converted to a discrete linear system using uniform quantization and then solved efficiently. the accuracy of the computed entropy rate is shown to be proportional to the quantization interval. unlike many other numerical methods, this numerical solution is not based on averaging over a sample path of the hmp.
universal simulation with fidelity criteria. we consider the problem of universal simulation of a memoryless source (with some partial extensions to markov sources), based on a training sequence emitted from the source. the objective is to maximize the conditional entropy of the simulated sequence given the training sequence, subject to a certain distance constraint between the probability distribution of the output sequence and the probability distribution of the input, training sequence. we derive, for several distance criteria, single-letter expressions for the maximum attainable conditional entropy as well as corresponding universal simulation schemes that asymptotically attain these maxima.
on the capacity of the discrete-time poisson channel. the large-inputs asymptotic capacity of a peak-power and average-power limited discrete-time poisson channel is derived using a new firm (nonasymptotic) lower bound and an asymptotic upper bound. the upper bound is based on the dual expression for channel capacity and the notion of capacity-achieving input distributions that escape to infinity. the lower bound is based on a lower bound on the entropy of a conditionally poisson random variable in terms of the differential entropy of its conditional mean.
the generalized random energy model and its application to the statistical physics of ensembles of hierarchical codes. in an earlier work, the statistical physics associated with finite-temperature decoding of code ensembles, along with the relation to their random coding error exponents, were explored in a framework that is analogous to derrida's random energy model (rem) of spin glasses, according to which the energy levels of the various spin configurations are independent random variables. the generalized rem (grem) extends the rem in that it introduces correlations between energy levels in an hierarchical structure. in this paper, we explore some analogies between the behavior of the grem and that of code ensembles which have parallel hierarchical structures. in particular, in analogy to the fact that the grem may have different types of phase transition effects, depending on the parameters of the model, then the above-mentioned hierarchical code ensembles behave substantially differently in the various domains of the design parameters of these codes.we make an attempt to explore the insights that can be imported from the statistical mechanics of the grem and be harnessed to serve for code design considerations and guidelines.
optimal monotone encodings. moran, naor, and segev have asked what is the minimal r = r(n, k) for which there exists an (n, k)-monotone encoding of length r, i.e., a monotone injective function from subsets of size up to k of {1, 2,..., n} to r bits. monotone encodings are relevant to the study of tamper-proof data structures and arise also in the design of broadcast schemes in certain communication networks. to answer this question, we develop a relaxation of k-superimposed families, which we call α-fraction k-multiuser tracing (k, α)-fut (fraction user-tracing) families). we show that r(n, k) = θ(klog(n/k)) by proving tight asymptotic lower and upper bounds on the size of (k, α)-fut families and by constructing an (n, k)-monotone encoding of length o(k log (n/k)). we also present an explicit construction of an (n, 2)-monotone encoding of length 2logn + o(1), which is optimal up to an additive constant.
better binary list decodable codes via multilevel concatenation. a polynomial time construction of binary codes with the currently best known tradeoff between rate and error-correction radius is given. specifically, linear codes over fixed alphabets are constructed that can be list decoded in polynomial time up to the so-called blokh-zyablov bound. the work builds upon earlier work by the authors where codes list decodable up to the zyablov bound (the standard product bound on distance of concatenated codes) were constructed. the new codes are constructed via a (known) generalization of code concatenation called multilevel code concatenation. a probabilistic argument, which is also derandomized via conditional expectations, is used to show the existence of inner codes with a certain nested list decodability property that is appropriate for use in multilevel concatenated codes. a "level-by-level" decoding algorithm, which crucially uses the list recovery algorithm for the outer folded reed-solomon codes, enables list decoding up to the designed distance bound, aka the blokh-zyablov bound, for multilevel concatenated codes.
two batch search with lie cost. we consider the problem of searching for an unknown number in the search space u = {0,..., m -1}. qary questions can be asked and some of the answers may be wrong. an arbitrary integer weighted bipartite graph γ is given, stipulating the cost γ(i,j) of each answer j ≠ i when the correct answer is i, i.e., the cost of a wrong answer. correct answers are supposed to be cost-less. it is assumed that a maximum cost e for the sum of the cost of all wrong answers can be afforded by the responder during the whole search. we provide tight upper and lower bounds for the largest size m = m (q, e, γ, n) for which it is possible to find an unknown number x* ∈ u with n q-ary questions and maximum lie cost e. our results improve the bounds of cicalese et al. (2004) and ahlswede et al. (2008). the questions in our strategies can be asked in two batches of nonadaptive questions. finally, we remark that our results can be further generalized to a wider class of error models including also unidirectional errors.
network coding: a computational perspective. in this work, we study the computational perspective of network coding, focusing on two issues. first, we address the computational complexity of finding a network code for acyclic multicast networks. second, we address the issue of reducing the amount of computation performed by network nodes. in particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e., nodes that generate new packets by performing algebraic operations on packets received over incoming links. we present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph g(v,e) in time o(|e|kh + |v|k2h2 + h4k3(k+h)), where k is the number of destinations and h is the number of packets. our algorithm improves the best known running time for network code construction. in addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is upper-bounded by o(h3k2). next, we address the problem of finding integral and fractional network codes with the minimum number of encoding nodes. we prove that in the majority of settings this problem is np-hard. however, we show that if h = o(1),k = o(1), and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time.
on the throughput of secure hybrid-arq protocols for gaussian block-fading channels. the focus of this paper is an information-theoretic study of retransmission protocols for reliable packet communication under a secrecy constraint. the hybrid automatic retransmission request (harq) protocol is revisited for a block-fading wiretap channel. here, two legitimate users communicate over a block-fading channel in the presence of a passive eavesdropper who intercepts the transmissions through an independent block-fading channel. in this model, the transmitter obtains a 1-bit ack/nack feedback from the legitimate receiver via an error-free public channel. both reliability and confidentiality of secure harq protocols are studied through the joint consideration of channel coding, secrecy coding, and retransmission protocols. in particular, the error and secrecy performance of repetition time diversity (rtd) and incremental redundancy (inr) protocols are investigated based on wyner code sequences. these protocols ensure that the confidential message is decoded successfully by the legitimate receiver and is kept completely secret from the eavesdropper for a set of channel realizations. this paper illustrates that there exists a rate-compatible wyner code family which ensures a secure inr protocol. further, it defines the connection outage and secrecy outage probabilities to characterize the tradeoff between the reliability of the legitimate communication link and the confidentiality with respect to the eavesdropper's link. for a given connection/secrecy outage probability pair, an achievable throughput of secure harq protocols is derived for block-fading channels. finally, both asymptotic analysis and numerical calculations demonstrate the benefits of harq protocols to throughput and secrecy.
performance analysis and design criteria of bicm-id with signal space diversity for keyhole nakagami-m fading channels. this paper generalizes the application bit-interleaved coded modulation with iterative decoding (bicm-id) using signal space diversity (ssd) over keyhole nakagami-m fading channels. the tight union bound on the asymptotic error performance is first analytically derived. the near-optimal rotation matrix with respect to both the asymptotic performance and the convergence behavior is then determined. in particular, it is demonstrated that the suitable rotation matrix is the one that has 1) all entries equal in magnitude, 2) a high diversity order, and 3) a large minimum product of the ratios between squared distances to the power m and log-squared distances to the power m of the rotated constellation scaled by factors of signal-to-noise ratio (snr) and the parameter m. various analytical and simulation results show that by employing ssd with a sufficiently large dimension, the error performance can closely approach that over an additive white gaussian noise (awgn) channel, even in the worst case of keyhole fading.
on the relay channel with receiver-transmitter feedback. an achievable rate for the discrete memoryless relay channel with receiver-transmitter feedback is proposed based on block-markov superposition encoding. the achievable rate can also be extended to gaussian channels. a second achievable rate for the gaussian relay channel based on a schalkwijk-kailath type scheme is presented. for some channels both achievable rates strictly improve upon all previously known achievable rates. for the discrete memoryless relay channel also a converse result is provided.
cyclic lowest density mds array codes. three new families of lowest density maximum-distance separable (mds) array codes are constructed, which are cyclic or quasi-cyclic. in addition to their optimal redundancy (mds) and optimal update complexity (lowest density), the symmetry offered by the new codes can be utilized for simplified implementation in storage applications. the proof of the code properties has an indirect structure: first mds codes that are not cyclic are constructed, and then transformed to cyclic codes by a minimum-distance preserving transformation.
finite state channels with time-invariant deterministic feedback. we consider capacity of discrete-time channels with feedback for the general case where the feedback is a time-invariant deterministic function of the output samples. under the assumption that the channel states take values in a finite alphabet, we find a sequence of achievable rates and a sequence of upper bounds on the capacity. the achievable rates and the upper bounds are computable for any n, and the limits of the sequences exist. we show that when the probability of the initial state is positive for all the channel states, then the capacity is the limit of the achievable-rate sequence. we further show that when the channel is stationary, indecomposable, and has no intersymbol interference (isi), its capacity is given by the limit of the maximum of the (normalized) directed information between the input xn and the output yn, i.e., c = limn → ∞ 1/n max i(xn → yn) where the maximization is taken over the causal conditioning probability q(xn∥zn-1) defined in this paper. the main idea for obtaining the results is to add causality into gallager's results on finite state channels. the capacity results are used to show that the source-channel separation theorem holds for time-invariant determinist feedback, and if the state of the channel is known both at the encoder and the decoder, then feedback does not increase capacity.
coding on countably infinite alphabets. this paper describes universal lossless coding strategies for compressing sources on countably infinite alphabets. classes of memoryless sources defined by an envelope condition on the marginal distribution provide benchmarks for coding techniques originating from the theory of universal coding over finite alphabets. we prove general upper bounds on minimax regret and lower bounds on minimax redundancy for such source classes. the general upper bounds emphasize the role of the normalized maximum likelihood (nml) codes with respect to minimax regret in the infinite alphabet context. lower bounds are derived by tailoring sharp bounds on the redundancy of krichevsky-trofimov coders for sources over finite alphabets. up to logarithmic (resp., constant) factors the bounds are matching for source classes defined by algebraically declining (resp., exponentially vanishing) envelopes. effective and (almost) adaptive coding techniques are described for the collection of source classes defined by algebraically vanishing envelopes. those results extend our knowledge concerning universal coding to contexts where the key tools from parametric inference are known to fail.
provably good codes for hash function design. a new technique to lower-bound the minimum distance of certain types of quasi-cyclic codes with large dimension by reducing the problem to lower-bounding the minimum distance of a few significantly smaller codes has been developed. these codes have the property that they have extremely efficient software encoders. using this technique, it is proved that a code which is similar to the sha-1 (secure hash algorithm, to be explained shortly) message expansion code has minimum distance 82, and that too in just the last 64 of the 80 expanded words. in fact, the proposed code has much greater distance than that of sha-1 code, which makes our proposed hashing scheme robust against cryptographic attacks. the technique is further used to find the minimum weight of the sha-1 code itself (25 in last 60 words), which was an open problem. estimating minimum distance of a code given by its parity-check matrix is well known to be a hard problem. our technique is expected to be helpful in estimating minimum distance of similar codes as well as in designing future practical cryptographic hash functions.
channel simulation with quantum side information. we study and solve the problem of classical channel simulation with quantum side information at the receiver. this is a generalization of both the classical reverse shannon theorem, and the classical-quantum slepian-wolf problem. the optimal noiseless communication rate is found to be reduced from the mutual information between the channel input and output by the holevo information between the channel output and the quantum side information. our main theorem has two important corollaries. the first is a quantum generalization of thewyner-ziv problem: ratedistortion theory with quantum side information. the second is an alternative proof of the tradeoff between classical communication and common randomness distilled from a quantum state. the fully quantum generalization of the problem considered is quantum state redistribution. here the sender and receiver share a mixed quantum state and the sender wants to transfer part of her state to the receiver using entanglement and quantum communication. we present outer and inner bounds on the achievable rate pairs.
constrained capacities for faster-than-nyquist signaling. this paper deals with capacity computations of fasterthan-nyquist (ftn) signaling. it shows that the capacity of ftn higher than the orthogonal pulse linear modulation capacity for all pulse shapes except the sinc. ftn signals can in fact achieve the ultimate capacity for the signal power spectral density (psd). the paper lower- and upper-bounds the ftn capacity under the constraint of finite input alphabet. it is often higher than the capacity for comparable orthogonal pulse systems; sometimes it is superior to all forms of orthogonal signaling with the same psd.
robust hypothesis testing with a relative entropy tolerance. this paper considers the design of a minimax test for two hypotheses where the actual probability densities of the observations are located in neighborhoods obtained by placing a bound on the relative entropy between actual and nominal densities. the minimax problem admits a saddle point which is characterized. the robust test applies a nonlinear transformation which flattens the nominal likelihood ratio in the vicinity of one. results are illustrated by considering the transmission of binary data in the presence of additive noise.
local base station cooperation via finite-capacity links for the uplink of linear cellular networks. cooperative decoding at the base stations (or access points) of an infrastructure wireless network is currently well recognized as a promising approach for intercell interference mitigation, thus enabling high frequency reuse. deployment of cooperative multicell decoding depends critically on the tolopology and quality of the available backhaul links connecting the base stations. this work studies a scenario where base stations are connected only if in adjacent cells, and via finite-capacity links. relying on a linear wyner-type cellular model with no fading, achievable rates are derived for the two scenarios where base stations are endowed only with the codebooks of local (in-cell) mobile stations, or also with the codebooks used in adjacent cells. moreover, both uni- and bidirectional backhaul links are considered. the analysis sheds light on the impact of codebook information, decoding delay, and network planning (frequency reuse) on the performance of multicell decoding as enabled by local and finite-capacity backhaul links. analysis in the high-signal-to-noise ratio (snr) regime and numerical results validate the main conclusions.
capacity of a class of modulo-sum relay channels. this paper characterizes the capacity of a class of modular additive noise relay channels, in which the relay observes a corrupted version of the noise and has a separate channel to the destination. the capacity is shown to be strictly below the cut-set bound in general and adhievable using a quantize-and-forward strategy at the relay. this result confirms a previous conjecture on the capacity of channels with rate-limited side information at the receiver for this particular class of modulo-sum channels. this paper also considers a more general setting in which the relay is capable of conveying noncausal rate-limited side information about the noise to both the transmitter and the receiver. the capacity is characterized for the case where the channel is binary symmetric with a crossover probability 1/2. in this case, the rates available for conveying side information to the transmitter and to the receiver can be traded with each other arbitrarily--the capacity is a function of the sum of the two rates.
quantifying the loss of compress-forward relaying without wyner-ziv coding. the compress-and-forward (cf) strategy achieves the optimal diversity-multiplexing tradeoff (dmt) of a three-node half-duplex relay network in slow fading, under the assumption that the relay has perfect knowledge of all three channel coefficients and that the relay makes use of wyner-ziv (wz) source coding with side information. this paper studies the achievable dmt of the same network when the relay is constrained to make use of standard (non-wz) source coding. under a short-term power constraint at the relay, using source coding without side information results in a significant loss in terms of the dmt. for multiplexing gains r ≤ 2/3, this loss can be fully compensated for by using power control at the relay. on the contrary, for r ∈ (2/3,1), the loss with respect to wz coding remains significant.