Search

This paper considers a state dependent broadcast channel with one transmitter, Alice, and two receivers, Bob and Eve. The problem is to effectively convey (“amplify”) the channel state sequence to Bob while “masking” it from Eve. The extent to which the state sequence cannot be masked from Eve is referred to as leakage. This can be viewed as a secrecy problem, where we desire that the channel state itself be minimally leaked to Eve while being communicated to Bob. This paper is aimed at characterizing the tradeoff region between amplification and leakage rates for such a system. An achievable coding scheme is presented, wherein the transmitter transmits a partial state information over the channel to facilitate the amplification process. For the case when Bob observes a stronger signal than Eve, the achievable coding scheme is enhanced with secure refinement. Outer bounds on the tradeoff region are also derived, and used in characterizing some special case results. In particular, the optimal amplification-leakage rate difference, called as differential amplification capacity, is characterized for the reversely degraded discrete memoryless channel, the degraded binary, and the degraded Gaussian channels. In addition, for the degraded Gaussian model, the extremal corner points of the tradeoff region are characterized, and the gap between the outer bound and achievable rate-regions is shown to be less than half a bit for a wide set of channel parameters. [ABSTRACT FROM PUBLISHER]

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of $\ell $ nodes. An $(n,k,d,\ell)$ secure exact-repair regenerating code is an $(n,k,d)$ exact-repair regenerating code that is secure under this eavesdropping model. It has been shown that for some parameters $(n,k,d,\ell)$ , the associated optimal storage-bandwidth tradeoff curve, which has one corner point, can be determined. The focus of this paper is on characterizing such parameters. We establish a lower bound $\hat {\ell }$ on the number of wiretap nodes, and show that this bound is tight for the case $k = d = n-1$. [ABSTRACT FROM AUTHOR]

Index coding studies multiterminal source-coding problems where a set of receivers are required to decode multiple (possibly different) messages from a common broadcast, and they each know some messages a priori. In this paper, at the receiver end, we consider a special setting where each receiver knows only one message a priori, and each message is known to only one receiver. At the broadcasting end, we consider a generalized setting where there could be multiple senders, and each sender knows a subset of the messages. The senders collaborate to transmit an index code. This paper looks at minimizing the number of total coded bits the senders are required to transmit. When there is only one sender, we propose a pruning algorithm to find a lower bound on the optimal (i.e., the shortest) index codelength, and show that it is achievable by linear index codes. When there are two or more senders, we propose an appending technique to be used in conjunction with the pruning technique to give a lower bound on the optimal index codelength; we also derive an upper bound based on cyclic codes. While the two bounds do not match in general, for the special case where no two distinct senders know any message in common, the bounds match, giving the optimal index codelength. The results are expressed in terms of strongly connected components in directed graphs that represent the index-coding problems. [ABSTRACT FROM AUTHOR]

In this paper, we study the wireline two-unicast-Z communication network over directed acyclic graphs. The two-unicast- $Z$ network is a two-unicast network where the destination intending to decode the second message has a priori side information of the first message. We make three contributions in this paper. First, we describe a new linear network coding algorithm for two-unicast-Z networks over the directed acyclic graphs. Our approach includes the idea of interference alignment as one of its key ingredients. For the graphs of a bounded degree, our algorithm has linear complexity in terms of the number of vertices, and the polynomial complexity in terms of the number of edges. Second, we prove that our algorithm achieves the rate pair (1, 1) whenever it is feasible in the network. Our proof serves as an alternative, albeit restricted to two-unicast-Z networks over the directed acyclic graphs, to an earlier result of Wang et al., which studied the necessary and sufficient conditions for the feasibility of the rate pair (1, 1) in two-unicast networks. Third, we provide a new proof of the classical max-flow min-cut theorem for the directed acyclic graphs. [ABSTRACT FROM AUTHOR]

In this paper, we study a new model of defect memory cells, called partially stuck-at memory cells, which is motivated by the behavior of multi-level cells in non-volatile memories, such as flash memories and phase change memories. If a cell can store the q levels 0, 1, {\dots }, q-1 , we say that it is partially stuck-at level s$ , where $1 \leq s \leq q-1$ , if it can only store values, which are at least $s$ . We follow the common setup where the encoder knows the positions and levels of the partially stuck-at cells whereas the decoder does not. Our main contribution in this paper is the study of codes for masking $u$ partially stuck-at cells. We first derive lower and upper bounds on the redundancy of such codes. The upper bounds are based on two trivial constructions. We then present three code constructions over an alphabet of size $q$ , by first considering the case where the cells are partially stuck-at level $s=1$ . The first construction works for $u

The compute-and-forward (C&F) protocol in quasi-static channels normally employs lattice codes based on the rational integers $\mathbb {Z}$ , the Gaussian integers $\mathbb {Z} [i]$ , or the Eisenstein integers $\mathbb {Z} [\omega ]$ , while its extension to more general channels often assumes channel state information at transmitters (CSIT). In this paper, we propose a novel scheme for C&F in block-fading channels without CSIT, which is referred to as ring C&F because the fading coefficients are quantized to the canonical embedding of a ring of algebraic integers. Owing to the multiplicative closure of the algebraic lattices employed, a relay is able to decode an algebraic–integer linear combination of lattice codewords. We analyze its achievable computation rates and show it outperforms conventional C&F based on the $\mathbb {Z}$ -lattices. By investigating the effect of the Diophantine approximation by algebraic conjugates, we prove that the degrees of freedom (DoFs) of the optimized computation rate are ${n}/{L}$ , where $n$ is the number of blocks and $L$ is the number of users. [ABSTRACT FROM AUTHOR]

This paper investigates interplay among storage overhead, bandwidth requirement, and security constraint in distributed storage. In the model used in our analysis, storage nodes are dispersed in multiple clusters. When a node fails, necessary content gets restored by downloading data from different nodes that may possibly be in other clusters. The bandwidth required for transferring data for node repair is assumed more scarce for cluster-to-cluster links than the links connecting intra-cluster nodes. Eavesdropping takes place on links across clusters only, and a fraction of the total number of clusters is assumed compromised. When a cluster is compromised, any repair traffic going in and out of it is eavesdropped. For this clustered model with eavesdroppers, we analyze the security of distributed storage systems (DSSs) and provide guidelines on designing system solutions for securing the data. First, under the setting of functional repair, we derive a general upper bound on the secrecy capacity, the maximum data size that can be stored in DSSs with perfect secrecy. In the practically important bandwidth-limited regime where the node storage size is equal to the repair bandwidth, the upper bound is shown to be achievable through proposed code constructions. Moreover, we obtain a closed-form expression for the required system resources-node storage size and repair bandwidth-to store a given amount of data with perfect secrecy. Second, we investigate the behavior of secrecy capacity as the number of compromised clusters increases. According to our mathematical analysis, the secrecy capacity decreases as a quadratic function until the number of compromised clusters reaches a certain threshold. Finally, based on the fundamental relationship between the system resources and the secrecy capacity, we provide a guideline on balancing intra- and cross-cluster repair bandwidths depending on the given system security level. [ABSTRACT FROM AUTHOR]

This paper establishes the exact exponents for the soft-covering phenomenon of a memoryless channel under the total variation metric when random (i.i.d. and constant-composition) channel codes are used. The exponents, established herein, are strict improvements in both directions on bounds found in the literature. This complements the recent literature establishing the exact exponents under the relative entropy metric; however, the proof techniques have significant differences, and thus, neither result trivially implies the other. The found exponents imply new and improved bounds for various problems that use soft-covering as their achievability argument, including new lower bounds for the resolvability exponent and the secrecy exponent in the wiretap channel. [ABSTRACT FROM AUTHOR]

A central question in the era of big data is what to do with the enormous amount of information. One possibility is to characterize it through statistics, e.g., averages, or classify it using machine learning, in order to understand the general structure of the overall data. The perspective in this paper is the opposite, namely that most of the value in the information in some applications is in the parts that deviate from the average, that are unusual, atypical. We define what we mean by atypical in an axiomatic way as data that can be encoded with fewer bits in itself rather than using the code for the typical data. We show that this definition has good theoretical properties. We then develop an implementation based on universal source coding, and apply this to a number of real world data sets. [ABSTRACT FROM AUTHOR]

This paper presents and analyzes a novel concatenated coding scheme for enabling error resilience in two distributed storage settings: one being storage using existing regenerating codes and the second being storage using locally repairable codes. The concatenated coding scheme brings together a maximum rank distance code as an outer code and either a globally regenerating or a locally repairable code as an inner code. In addition, error resilience for combination of locally repairable codes with regenerating codes is considered. This concatenated coding system is designed to handle two different types of adversarial errors: the first type includes an adversary that can replace the content of an affected node only once; while the second type studies an adversary that is capable of polluting data an unbounded number of times. The paper establishes an upper bound on the resilience capacity for a locally repairable code. This paper also proves that the proposed concatenated coding approach attains the upper bound on the resilience capacity in the presence of the first type of adversary for both minimum storage regenerating codes and locally repairable codes. Further, this paper presents mechanisms that combine the presented concatenated coding scheme with subspace signatures to achieve error resilience for the second type of errors. [ABSTRACT FROM PUBLISHER]

Consider the problem of a multiple-input multiple-output multiple-access channel at the limit of large number of users. Clearly, in practical scenarios, only a small subset of the users can be scheduled to utilize the channel simultaneously. Thus, a problem of user selection arises. However, since solutions which collect channel state information from all users and decide on the best subset to transmit in each slot do not scale when the number of users is large, distributed algorithms for user selection are advantageous. In this paper, we analyze a distributed user selection algorithm, which selects a group of users to transmit without coordinating between users and without all users sending CSI to the base station. This threshold-based algorithm is analyzed for both zero-forcing and minimum mean square error receivers, and its expected sum rate in the limit of large number of users is investigated. It is shown that for large number of users, it achieves the same scaling laws as the optimal centralized scheme. [ABSTRACT FROM AUTHOR]

Recent works by Ahmad et al. and by Hollmann studied the concept of “locally repairable regenerating codes (LRRCs)” that successfully combines the functional repair and partial information exchange of regenerating codes (RCs) with the much-desired local repairability feature of locally repairable codes (LRCs). One important issue that needs to be addressed by any local repair schemes (including both LRCs and LRRCs) is that sometimes designated helper nodes may be temporarily unavailable, the result of various reasons that include multiple failures, degraded reads, or power-saving strategies to name a few. Under the setting of LRRCs with temporary node unavailability, this paper studies the impact of different helper selection methods. It proves that with node unavailability, all existing methods of helper selection, including those used in RCs and LRCs, can be insufficient in terms of achieving the optimal repair-bandwidth. For some scenarios, it is necessary to combine LRRCs with a new class of helper selection methods, termed dynamic helper selection, to achieve optimal repair-bandwidth. This paper also compares the performance of different classes of helper selection methods and answers the following fundamental question: is one method of helper selection intrinsically better than the other? for various scenarios. [ABSTRACT FROM PUBLISHER]

Linear programming approaches have been applied to derive upper bounds on the size of classical and quantum codes. In this paper, we derive similar results for general quantum codes with entanglement assistance by considering a type of split weight enumerator. After deriving the MacWilliams identities for these enumerators, we are able to prove algebraic linear programming bounds, such as the Singleton bound, the Hamming bound, and the first linear programming bound. Our Singleton bound and Hamming bound are more general than the previous bounds for entanglement-assisted quantum stabilizer codes. In addition, we show that the first linear programming bound improves the Hamming bound when the relative distance is sufficiently large. On the other hand, we obtain additional constraints on the size of Pauli subgroups for quantum codes, which allow us to improve the linear programming bounds on the minimum distance of quantum codes of small length. In particular, we show that there is no $[[27, 15, 5]]$ or $[[28, 14, 6]]$ stabilizer code. We also discuss the existence of some entanglement-assisted quantum stabilizer codes with maximal entanglement. As a result, the upper and lower bounds on the minimum distance of maximal-entanglement quantum stabilizer codes with length up to 20 are significantly improved. [ABSTRACT FROM PUBLISHER]

Current approaches to the practical implementation of network coding are batch-based, and often do not use feedback, except possibly to signal completion of a file download. In this paper, the various benefits of using feedback in a network coded system are studied. It is shown that network coding can be performed in a completely online manner, without the need for batches or generations, and that such online operation does not affect the throughput. Although these ideas are presented in a single-hop packet erasure broadcast setting, they naturally extend to more general lossy networks, which employ network coding in the presence of feedback. The impact of feedback on sender-side queue size and receiver-side decoding delay is studied in an asymptotic sense as the traffic load approaches capacity. Different notions of decoding delay are considered, including an order-sensitive notion, which assumes that packets are useful only when delivered in order. Strategies for adaptive coding based on feedback are presented. Our scheme achieves throughput optimality and asymptotically optimal sender queue size and is conjectured to achieve asymptotically optimal in-order delivery delay for any number of receivers. This paper may be viewed as a natural extension of Automatic Repeat reQuest to coded networks. [ABSTRACT FROM PUBLISHER]

Caching is an efficient way to reduce network traffic congestion during peak hours by storing some content at the users’ local caches. For the shared-link network with end-user-caches, Maddah-Ali and Niesen proposed a two-phase coded caching strategy. In practice, users may communicate with the server through intermediate relays. This paper studies the tradeoff between the memory size ${\mathsf M}$ and the network load ${\mathsf R}$ for the networks where a server with ${\mathsf N}$ files is connected to ${\mathsf H}$ relays (without caches), which in turn are connected to ${\mathsf K}$ users equipped with caches of ${\mathsf M}$ files. When each user is connected to a different subset of ${\mathsf r}$ relays, i.e., ${\mathsf K}= \binom {\mathsf H}{\mathsf r}$ , the system is referred to as a combination network with end-user-caches. In this work, converse bounds are derived for the practically motivated case of uncoded cache contents, that is, bits of the various files are directly pushed into the user caches without any coding. In this case, once the cache contents and the users’ demands are known, the problem reduces to a general index coding problem. This paper shows that relying on a well-known “acyclic index coding converse bound” results in converse bounds that are not tight for combination networks with end-user-caches. A novel converse bound that leverages the network topology is proposed, which is the tightest converse bound known to date. As a result of independent interest, an inequality that generalizes the well-known sub-modularity of entropy is derived. Several novel caching schemes are proposed, based on the Maddah-Ali and Niesen cache placement. These schemes leverage the structure of the combination network or/and perform interference elimination at the end-users. The proposed schemes are proved: (i) to be (order) optimal for some $({\mathsf N}, {\mathsf M}, {\mathsf H}, {\mathsf r})$ parameters regimes under the constraint of uncoded cache placement, and (ii) to outperform the state-of-the-art schemes in numerical evaluations. [ABSTRACT FROM AUTHOR]

In this paper, we formulate the problem to cope with the transmission of extra bits over an existing coded transmission link (referred to as coded payload link) without any cost of extra transmission energy or extra bandwidth. This is possible since a gap to the channel capacity typically exists for a practical code. A new concept, termed as accessible capacity, is introduced to specify the maximum rate at which the superposition transmission of extra bits is reliable and has a negligible effect on the performance of the coded payload link. For a binary-input output-symmetric (BIOS) memoryless channel, the accessible capacity can be characterized as the difference between the channel capacity and the mutual information rate of the coded payload link, which can be numerically evaluated for very short payload codes. For a general payload code, we present a simple lower bound on the accessible capacity, given by the channel capacity minus the coding rate of the payload code. We then focus on the scenarios where low-density parity-check (LDPC) codes are implemented for the payload link. We propose to transmit extra bits by random superposition for encoding, and exhaustive search (with the aid of statistical learning) for decoding. We further propose, by establishing an auxiliary channel (called syndrome channel) induced from “zero-forcing” over the binary field, to transmit extra bits with structured codes such as repetition codes and first-order Reed-Muller (RM) codes. Numerical results show that up to 60 extra bits can be reliably transmitted along with a rate-1/2 LDPC code of length 8064. [ABSTRACT FROM AUTHOR]

Erasure coding has been recognized as a powerful method to mitigate delays due to slow or straggling nodes in distributed systems. This work shows that erasure coding of data objects can flexibly handle skews in the request rates. Coding can help boost the service rate region, that is, increase the overall volume of data access requests that the system can handle. This paper aims to postulate the service rate region as an important consideration in the design of erasure-coded distributed systems. We highlight several open problems that can be grouped into two broad threads: 1) characterizing the service rate region of a given code and finding the optimal request allocation, and 2) designing the underlying erasure code for a given service rate region. As contributions along the first thread, we find the rate regions of maximum-distance-separable, locally repairable, and simplex codes. We show the effectiveness of hybrid codes that combine replication and erasure coding in terms of code design. We also discover fundamental connections between multi-set batch codes and the problem of maximizing the service rate region. [ABSTRACT FROM AUTHOR]

Distributed Arithmetic Coding (DAC) is a practical realization of Slepian-Wolf coding that partitions source space into cosets. Coset Cardinality Spectrum (CCS) is an important property of DAC that was defined in our previous work. In this paper, we give two applications of CCS. First, we find that DAC bitstream is not compact. The rate loss of DAC bitstream is caused by two factors: unequal coset partitioning and bit indivisibility. It is proved that as code length goes to infinity, the expected value of bit-indivisibility rate loss will tend to 0.5 for any irrational Rate Change Step (RCS), where the RCS refers to the rate change when one source bit is flipped. With the help of CCS, the bit-indivisibility rate loss can be compensated to some extend. Especially, for any irrational RCS, as code length goes to infinity, the expected value of the remaining bit-indivisibility rate loss after compensation will tend to about 0.47. The second application of CCS is DAC decoder design. We derive the formula of path metric and find that in the original paper on DAC, the intuitive formula of path metric is not correct. The backward-replacing algorithm is proposed to make full use of memory. Experimental results confirm the correctness of theoretical analyses. [ABSTRACT FROM AUTHOR]

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting only two deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct ${d}$ deletions in a codeword of length ${n}$ , successive-cancellation decoding is run separately for each of the $\binom {n}{d}$ possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is ${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in ${m} = \log _{2} {n}$ decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most $\binom {d+2}{2}$ scenarios at each node, and the overall decoding complexity is only ${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ , which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions ${d}$ is small, i.e. ${d}={o}({n})$. We also conjecture the strong polarization for when ${d}={O}(1)$ and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions. [ABSTRACT FROM AUTHOR]

This paper investigates the theory of sum-rank-metric codes for which the individual matrix blocks may have different sizes. Various bounds on the cardinality of a code are derived, along with their asymptotic extensions. The duality theory of sum-rank-metric codes is also explored, showing that MSRD codes (the sum-rank analogue of MDS codes) dualize to MSRD codes only if all matrix blocks have the same number of columns. In the latter case, duality considerations lead to an upper bound on the number of blocks for MSRD codes. The paper also contains various constructions of sum-rank-metric codes for variable block sizes, illustrating the possible behaviours of these objects with respect to bounds, existence, and duality properties. [ABSTRACT FROM AUTHOR]

Normalized maximum likelihood (NML) distribution of probabilistic model gives the optimal code length function in the sense of minimax regret. Despite its optimal property, the calculation of NML distribution is not easy, and existing efficient methods have been focusing on its asymptotic behavior, or on specific models. This paper gives an efficient way to calculate NML by integral on parameter domain, not on data domain, showing that NML distribution is a Bayesian predictive distribution with a complex prior, based on our novel Fourier expansion approach. Our results provide an integrated way to calculate NML for exponential family and also include a non-asymptotic version of previous work on asymptotic behavior for general cases. The applications of our methodology are not limited to but also include normal distribution, Gamma distribution, Weibull distribution, and von Mises distribution. [ABSTRACT FROM AUTHOR]

Existing fixed-length feedback communication schemes are either specialized to particular channels (Schalkwijk–Kailath, Horstein), or apply to general channels but either have high coding complexity (block feedback schemes) or are difficult to analyze (posterior matching). This paper introduces a new fixed-length feedback coding scheme which achieves the capacity for all discrete memoryless channels, has an error exponent that approaches the sphere packing bound as the rate approaches the capacity, and has $O(n\log n)$ coding complexity. These benefits are achieved by judiciously combining features from previous schemes with new randomization technique and encoding/decoding rule. These new features make the analysis of the error probability for the new scheme easier than for posterior matching. [ABSTRACT FROM AUTHOR]

We consider the problem of information embedding where the encoder modifies a white Gaussian host signal in a power-constrained manner to encode a message, and the decoder recovers both the embedded message and the modified host signal. This partially extends the recent work of Sumszyk and Steinberg to the continuous-alphabet Gaussian setting. Through a control-theoretic lens, we observe that the problem is a minimalist example of what is called the triple role of control actions. We show that a dirty-paper-coding strategy achieves the optimal rate for perfect recovery of the modified host and the message for any message rate. For imperfect recovery of the modified host, by deriving bounds on the minimum mean-square error (MMSE) in recovering the modified host signal, we show that Dirty-Paper Coding-based strategies are guaranteed to attain within a uniform constant factor of 16 of the optimal weighted sum of power required in host signal modification and the MMSE in the modified host signal reconstruction for all weights and all message rates. When specialized to the zero-rate case, our results provide the tightest known lower bounds on the asymptotic costs for the vector version of a famous open problem in decentralized control: the Witsenhausen counterexample. Numerically, this tighter bound helps us characterize the asymptotically optimal costs for the vector Witsenhausen problem to within a factor of 1.3 for all problem parameters, improving on the earlier best known bound of 2. [ABSTRACT FROM AUTHOR]

In this paper, a compress-and-forward scheme with backward decoding is presented for the unicast wireless relay network. The encoding at the source and relay is a generalization of the noisy network coding (NNC) scheme. While it achieves the same reliable data rate as NNC scheme, the backward decoding allows for a better decoding complexity as compared with the joint decoding of the NNC scheme. Characterizing the layered decoding scheme is shown to be equivalent to characterizing an information flow for the wireless network. A node-flow for a graph with bisubmodular capacity constraints is presented and a max-flow min-cut theorem is presented. This generalizes many well-known results of flows over capacity constrained graphs studied in computer science literature. The results for the unicast relay network are generalized to the network with multiple sources with independent messages intended for a single destination. [ABSTRACT FROM AUTHOR]

This paper considers the problem of minimum cost communication of correlated sources over a network with multiple sinks, which consists of distributed source coding followed by routing. We introduce a new routing paradigm called dispersive information routing (DIR), wherein the intermediate nodes are allowed to split a packet and forward subsets of the received bits on each of the forward paths. This paradigm opens up a rich class of research problems, which focus on the interplay between encoding and routing in a network. Unlike conventional routing methods such as in [1], DIR ensures that each sink receives just the information needed to reconstruct the sources it is required to reproduce. We demonstrate using simple examples that the proposed approach offers better asymptotic performance than conventional routing techniques. We show that, under certain assumptions on the cost function, the problem of finding the minimum cost under DIR essentially reduces to characterizing an achievable rate region for a new multiterminal information theoretic setup. While it is possible to derive an achievable region for this setup using prior results from general multiterminal source coding [3], these techniques do not exploit the underlying problem structure and thereby lead to suboptimal regions. In this paper, we propose a new coding scheme, using principles from multiple descriptions encoding [2], and show that it strictly improves upon a corresponding variant of coding scheme in [3]. We further show that the new coding scheme achieves the complete rate region for certain special cases of the general setup and thereby achieves the minimum communication cost under this routing paradigm. [ABSTRACT FROM PUBLISHER]

The Ising channel, which was introduced in 1990, is a channel with memory that models intersymbol interference. In this paper, we consider the Ising channel with feedback and find the capacity of the channel together with a capacity-achieving coding scheme. To calculate the channel capacity, an equivalent dynamic programming (DP) problem is formulated and solved. Using the DP solution, we establish that the feedback capacity is the expression \(C=({2H_{b}(a)}/{3+a})\approx 0.575522\) , where \(a\) is a particular root of a fourth-degree polynomial and \(H_{b}(x)\) denotes the binary entropy function. Simultaneously, \(a=\arg \max _{0\leq x \leq 1} ({2H_{b}(x)}/{3+x})\) . Finally, an error-free, capacity-achieving coding scheme is provided together with the outlining of a strong connection between the DP results and the coding scheme. [ABSTRACT FROM AUTHOR]

This paper addresses the question of achieving capacity with lattice codes in multi-antenna block fading channels when the number of fading blocks tends to infinity. A design criterion based on the normalized minimum determinant is proposed for division algebra multi-block space-time codes over fading channels; this plays a similar role to the Hermite invariant for Gaussian channels. Under maximum likelihood decoding, it is shown that this criterion is sufficient to guarantee transmission rates within a constant gap from capacity both for deterministic channels and ergodic fading channels. Moreover, if the number of receive antennas is greater than or equal to the number of transmit antennas, the same constant gap is achieved under naive lattice decoding as well. In the case of independent identically distributed Rayleigh fading, the error probability vanishes exponentially fast. In contrast to the standard approach in the literature, which employs random lattice ensembles, the existence results in this paper are derived from the number theory. First, the gap to capacity is shown to depend on the discriminant of the chosen division algebra; then, class field theory is applied to build families of algebras with small discriminants. The key element in the construction is the choice of a sequence of division algebras whose centers are number fields with small root discriminants. [ABSTRACT FROM AUTHOR]

Any sequence of uniformly bounded N\times N Hermitian Toeplitz matrices \{H_{N}\} is asymptotically equivalent to a certain sequence of N\times N circulant matrices \CN\ derived from the Toeplitz matrices in the sense that \left \|{HN- CN }\right \|F = o(\sqrt {N}) as $N\rightarrow \infty $ . This implies that certain collective behaviors of the eigenvalues of each Toeplitz matrix are reflected in those of the corresponding circulant matrix and supports the utilization of the computationally efficient fast Fourier transform (instead of the Karhunen-Loève transform) in applications like coding and filtering. In this paper, we study the asymptotic performance of the individual eigenvalue estimates. We show that the asymptotic equivalence of the circulant and Toeplitz matrices implies the individual asymptotic convergence of the eigenvalues for certain types of Toeplitz matrices. We also show that these estimates asymptotically approximate the largest and smallest eigenvalues for more general classes of Toeplitz matrices. [ABSTRACT FROM AUTHOR]

Consider a multi-user channel, where each user has a large but non-replenishable bit pool to transmit. Completion time refers to the number of channel uses spent by each user to complete its transmission. In this paper, an information-theoretic formulation of completion time is based on the concept of constrained rates, which are defined over possibly different number of channel uses. Analogous to the capacity region, the completion time region characterizes all possible trade-offs among users’ completion times. For a two-user multi-access channel, it is shown that the completion time region is achieved by operating the channel in two independent phases: a multi-access phase when both users are transmitting, and a point-to-point phase when one user has finished and the other is still transmitting. Using a similar two-phase approach, the completion time regions (or inner and outer bounds) are established for a two-user Gaussian broadcast channel and a two-user Gaussian interference channel. It is observed that although consisting of two convex subregions, the completion time region may not be convex in general. Finally, optimization problems of minimizing the weighted sum completion time for a Gaussian multi-access channel and a Gaussian broadcast channel are solved, demonstrating the utility of the completion time approach. [ABSTRACT FROM PUBLISHER]

This paper considers network communications under a hard timeliness constraint, where a source node streams perishable information to a destination node over a directed acyclic graph subject to a hard delay constraint. Transmission along any edge incurs unit delay, and it is required that every information bit generated at the source at the beginning of time t to be received and recovered by the destination at the end of time t+ {\mathrm {D}}-1 , where {\mathrm {D}}>0$ is the maximum allowed end-to-end delay. We study the corresponding delay-constrained unicast capacity problem. This paper presents the first example showing that network coding (NC) can achieve strictly higher delay-constrained throughput than routing even for the single unicast setting and the NC gain can be arbitrarily close to 2 in some instances. This is in sharp contrast to the delay-unconstrained ( {\mathrm {D}}=\infty ) single-unicast case where the classic min-cut/max-flow theorem implies that coding cannot improve throughput over routing. Motivated by the above findings, a series of investigation on the delay-constrained capacity problem is also made, including: 1) an equivalent multiple-unicast representation based on a time-expanded graph approach; 2) a new delay-constrained capacity upper bound and its connections to the existing routing-based results [Ying et al. 2011]; 3) an example showing that the penalty of using random linear NC can be unbounded; and 4) a counter example of the tree-packing Edmonds’ theorem in the new delay-constrained setting. Built upon the time-expanded graph approach, we also discuss how our results can be readily extended to cyclic networks. Overall, our results suggest that delay-constrained communication is fundamentally different from the well-understood delay-unconstrained one and call for investigation participation. [ABSTRACT FROM PUBLISHER]

Determining a single-letter secrecy-capacity formula for the arbitrarily varying wiretap channel (AVWTC) is an open problem largely because of two main challenges. Not only does it capture the difficulty of the compound wiretap channel (another open problem), it also requires that secrecy is ensured with respect to exponentially many possible channel state sequences. By extending the strong soft-covering lemma, recently derived by the authors, to the heterogeneous scenario, this paper accounts for the exponential number of secrecy constraints while only imposing single-letter constraints on the communication rate. Through this approach, we derive a single-letter characterization of the correlated-random (CR)-assisted semantic-security (SS) capacity of an AVWTC with a type constraint on the allowed state sequences. The allowed state sequences are the ones in a typical set around a single constraining type. The stringent SS requirement is established by showing that the mutual information between the message and the eavesdropper’s observations is negligible even when maximized over all message distributions, choices of state sequences, and realizations of the CR-code. Both the achievability and the converse proofs of the type-constrained coding theorem rely on stronger claims than actually required. The direct part establishes a novel single-letter lower bound on the CR-assisted SS-capacity of an AVWTC with state sequences constrained by any convex and closed set of state probability mass functions. This bound achieves the best known single-letter secrecy rates for a corresponding compound wiretap channel over the same constraint set. In contrast to other single-letter results in the AVWTC literature, this paper does not assume the existence of a best channel to the eavesdropper. Instead, SS follows by leveraging the heterogeneous version of the strong soft-covering lemma and a CR-code reduction argument. Optimality is a consequence of a max-inf upper bound on the CR-assisted SS-capacity of an AVWTC with state sequences constrained to any collection of type-classes. When adjusted to the aforementioned compound WTC, the upper bound simplifies to a max–min structure, thus strengthening the previously best known single-letter upper bound by Liang et al. that has a min–max form. The proof of the upper bound uses a novel distribution coupling argument. The capacity formula shows that the legitimate users effectively see an averaged main channel, while security must be ensured versus an eavesdropper with perfect channel state information. An example visualizes our single-letter results, and their relation to the past multi-letter secrecy-capacity characterization of the AVWTC is highlighted. [ABSTRACT FROM PUBLISHER]

In this paper, we reinterpret the $(k+2,k)$ zigzag code in coding matrix and then propose an optimal exact repair strategy for its parity nodes, whose repair disk I/O approaches a lower bound derived in this paper. [ABSTRACT FROM PUBLISHER]

Barcoding photons, atoms, and any quantum states can provide a host of functionalities that could benefit future quantum communication systems and networks beyond today’s imagination. As a significant application of barcoding photons, we introduce code division multiple-access (CDMA) communication systems for various applications. In this context, we introduce and discuss the fundamental principles of a novel quantum CDMA (QCDMA) technique based on spectrally encoding and decoding of continuous-mode quantum light pulses. In particular, we present the mathematical models of various QCDMA modules that are fundamental in describing an ideal and typical QCDMA system, such as quantum signal sources, quantum spectral encoding phase operators, M × M quantum broadcasting star-coupler, quantum spectral phase decoding operators, and the quantum receivers. Following the above discussions, we then elaborate on a QCDMA system with M users. In describing a QCDMA system, this paper considers a unified approach where the input continuous-mode quantum light pulses can take on any form of pure states such as quantum coherent (Glauber) states and quantum number (Fock) states. The mathematical presentation is independent of the form of the input pure quantum states. We show that the spectrally encoded quantum states of the light at the quantum star-coupler output are not, in general, factorized states, except for input Glauber states. For input number states, one can observe features like entanglement and quantum interference. Moreover and interestingly, as a consequence of Heisenberg’s uncertainty principle, the quantum signals sent by photon number states obtain complete phase uncertainty at the time of measurement. Therefore, at the receiver output, the multiaccess inter-signal interference vanishes. Due to Heisenberg’s uncertainty principle, the received signal intensity at the photodetector’s output, right at the time of measurement, changes from coherent detection scheme for input Glauber states to incoherent detection scheme for input number states. We also would like to highlight that the mathematical models and tools developed in this paper, in the context of QCDMA, become very useful for developing and analyzing other quantum multiple-access techniques based on wavelength, space and time domain. Furthermore, our mathematical model is valuable in signal design and data modulations of point-to-point quantum communications, quantum pulse shaping, and quantum radar signals and systems where the inputs are continuous mode quantum signals. QCDMA may open up novel possibilities for various quantum technologies such as data privacy, distributed quantum computation, quantum internet, and anti-jamming quantum communication systems. [ABSTRACT FROM AUTHOR]

Both linear complementary dual (LCD) codes and maximum distance separable (MDS) codes have good algebraic structures, and they have interesting practical applications such as communication systems, data storage, quantum codes, and so on. So far, most of LCD MDS codes have been constructed by employing generalized Reed-Solomon codes. In this paper we construct some classes of new Euclidean LCD MDS codes and Hermitian LCD MDS codes which are not monomially equivalent to Reed-Solomon codes, called LCD MDS codes of non-Reed-Solomon type. Our method is based on the constructions of Beelen et al. (2017) and Roth and Lempel (1989). To the best of our knowledge, this is the first paper on the construction of LCD MDS codes of non-Reed-Solomon type; any LCD MDS code of non-Reed-Solomon type constructed by our method is not monomially equivalent to any LCD code constructed by the method of Carlet et al. (2018). [ABSTRACT FROM AUTHOR]

This paper studies a large random matrix system (LRMS) model involving an arbitrary signal distribution and forward error control (FEC) coding. We establish an area property based on the approximate message passing (AMP) algorithm. Under the assumption that the state evolution for AMP is correct for the coded system, the achievable rate of AMP is analyzed. We prove that AMP achieves the constrained capacity of the LRMS with an arbitrary signal distribution provided that a matching condition is satisfied. As a byproduct, we provide an alternative derivation for the constraint capacity of an LRMS using a proved property of AMP. We discuss realization techniques for the matching principle of binary signaling using irregular low-density parity-check (LDPC) codes and provide related numerical results. We show that the optimized codes demonstrate significantly better performance over un-matched ones under AMP. For quadrature phase shift keying (QPSK) modulation, bit error rate (BER) performance within 1 dB from the constrained capacity limit is observed. [ABSTRACT FROM AUTHOR]

This paper studies a generalization of sparse superposition codes (SPARCs) for communication over the complex additive white Gaussian noise (AWGN) channel. In a SPARC, the codebook is defined in terms of a design matrix, and each codeword is a generated by multiplying the design matrix with a sparse message vector. In the standard SPARC construction, information is encoded in the locations of the non-zero entries of the message vector. In this paper we generalize the construction and consider modulated SPARCs, where information is encoded in both the locations and the values of the non-zero entries of the message vector. We focus on the case where the non-zero entries take values from a phase-shift keying (PSK) constellation. We propose a computationally efficient approximate message passing (AMP) decoder, and obtain analytical bounds on the state evolution parameters which predict the error performance of the decoder. Using these bounds we show that PSK-modulated SPARCs are asymptotically capacity achieving for the complex AWGN channel, with either spatial coupling or power allocation. We also provide numerical simulation results to demonstrate the error performance at finite code lengths. These results show that introducing modulation to the SPARC design can significantly reduce decoding complexity without sacrificing error performance. [ABSTRACT FROM AUTHOR]

A new method to construct q-ary complementary sequence sets (CSSs) and complete complementary codes (CCCs) of size N is proposed by using desired para-unitary (PU) matrices. The concept of seed PU matrices is introduced and a systematic approach on how to compute the explicit forms of the functions in constructed CSSs and CCCs from the seed PU matrices is given. A general form of these functions only depends on a basis of the functions from ZN to Zq and representatives in the equivalent class of Butson-type Hadamard (BH) matrices. Especially, the realization of Golay pairs from our general form exactly coincides with the standard Golay pairs. The realization of ternary complementary sequences of size 3 is first reported here. For the realization of the quaternary complementary sequences of size 4, almost all the sequences derived here are never reported before. Generalized seed PU matrices and the recursive constructions of the desired PU matrices are also studied, and a large number of new constructions of CSSs and CCCs are given accordingly. From the perspective of this paper, all the known results of CSSs and CCCs with explicit GBF form in the literature (except non-standard Golay pairs) are constructed from the WHT matrices. This suggests that the proposed method with other BH matrices will yield a large number of new CSSs and CCCs with the significantly increasing number of the sequences of low peak-to-mean envelope power ratio. [ABSTRACT FROM AUTHOR]

Pattern recognition based on a high-dimensional predictor is considered. A classifier is defined which is based on a Transformer encoder. The rate of convergence of the misclassification probability of the classifier towards the optimal misclassification probability is analyzed. It is shown that this classifier is able to circumvent the curse of dimensionality provided the a posteriori probability satisfies a suitable hierarchical composition model. Furthermore, the difference between the Transformer classifiers theoretically analyzed in this paper and the ones used in practice today is illustrated by means of classification problems in natural language processing. [ABSTRACT FROM AUTHOR]

This paper contains two main contributions concerning the expurgation of hierarchical ensembles for the asymmetric broadcast channel. The first is an analysis of the optimal maximum likelihood (ML) decoders for the weak and strong user. Two different methods of code expurgation will be used, that will provide two competing error exponents. The second is the derivation of expurgated exponents under the generalized stochastic likelihood decoder (GLD). We prove that the expurgated exponents achieved for the hierarchical ensemble under GLD decoding are at least as good as the maximum between the random coding error exponents derived in an earlier work by Averbuch and Merhav (2018) and one of our ML–based expurgated exponents. [ABSTRACT FROM AUTHOR]

The rate-distortion saddle-point problem considered by Lapidoth (1997) consists in finding the minimum rate to compress an arbitrary ergodic source when one is constrained to use a random Gaussian codebook and minimum (Euclidean) distance encoding is employed. We extend Lapidoth’s analysis in several directions in this paper. First, we consider refined asymptotics. In particular, when the source is stationary and memoryless, we establish the second-order, moderate, and large deviation asymptotics of the problem. Second, by random Gaussian codebook, Lapidoth referred to a collection of random codewords, each of which is drawn independently and uniformly from the surface of an $n$ -dimensional sphere. To be more precise, we term this as a spherical codebook. We also consider i.i.d. Gaussian codebooks in which each random codeword is drawn independently from a product Gaussian distribution. We derive the second-order, moderate, and large deviation asymptotics when i.i.d. Gaussian codebooks are employed. In contrast to the recent work on the channel coding counterpart by Scarlett, Tan, and Durisi (2017), the dispersions for spherical and i.i.d. Gaussian codebooks are identical. The ensemble excess-distortion exponents for both spherical and i.i.d. Gaussian codebooks are established for all rates. Furthermore, we show that the i.i.d. Gaussian codebook has a strictly larger excess-distortion exponent than its spherical counterpart for any rate greater than the ensemble rate-distortion function derived by Lapidoth. [ABSTRACT FROM AUTHOR]

Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction $\text{D}'$ whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction $\text{D}'$ is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel. [ABSTRACT FROM AUTHOR]

In this paper, we develop a technique to extend any bound for the minimum distance of cyclic codes constructed from its defining sets (ds-bounds) to Abelian (or multivariate) codes through the notion of ${\mathbb B}$ -apparent distance. We also study conditions for an Abelian code to verify that its ${\mathbb B}$ -apparent distance reaches its (true) minimum distance. Then, we construct some codes as an application. [ABSTRACT FROM AUTHOR]

Local rank modulation (LRM) scheme was suggested for representing the information in flash memories in order to overcome the drawbacks of rank modulation. For $0 < s\leq t\leq n$ with $s$ dividing $n$ , an $(s,t,n)$ -LRM scheme is a LRM scheme where the $n$ cells are locally viewed cyclically through a sliding window of size $t$ resulting in a sequence of small permutations, which requires less comparisons and less distinct values. The gap between two such windows equals to $s$. In this paper, encoding, decoding, and asymptotic enumeration of the $(1,t,n)$ -LRM scheme are studied. [ABSTRACT FROM AUTHOR]

We consider the problem of single-round private information retrieval (PIR) from $N$ replicated databases. We consider the case when $B$ databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of $M$ messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the $T$ -privacy constraint in this paper, where any $T$ databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of correct symbols that can be retrieved privately (under the $T$ -privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be $C=(N-2B)/N \cdot (1-T/(N-2B))/(1-(T/(N-2B))^{M})$ , if $2B+T < N$. This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing $2B$ databases from the system, with a penalty factor of $(N-2B)/N$ , which signifies that even though the number of databases needed for PIR is effectively $N-2B$ , the user still needs to access the entire $N$ databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the errors introduced by the Byzantine databases as opposed to erasures in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes. [ABSTRACT FROM AUTHOR]

Compute-and-forward (CF) harnesses interference in wireless communications by exploiting structured coding. The key idea of CF is to compute integer combinations of code words from multiple source nodes, rather than to decode individual code words by treating others as noise. Compute-compress-and-forward (CCF) can further enhance the network performance by introducing compression operations at receivers. In this paper, we develop a more general compression framework, termed generalized CCF (GCCF), where the compression function involves the selection of message segments over finite fields. We show that GCCF achieves a broader compression rate region than CCF. We also compare our compression rate region with the fundamental Slepian–Wolf (SW) region. We show that GCCF is optimal in the sense of achieving the minimum total compression rate. We also establish the criteria under which GCCF achieves the SW region. In addition, we consider a two-hop relay network employing the GCCF scheme. We formulate a sum-rate maximization problem and develop an approximate algorithm to solve the problem. Numerical results are presented to demonstrate the performance superiority of GCCF over CCF and other schemes. [ABSTRACT FROM AUTHOR]

In this paper, we consider a channel model that is often used to describe mobile wireless scenarios: multiple-antenna additive white Gaussian noise channels subject to random (fading) gains with full channel state information at the receiver. The dynamics of the fading process are approximated by a piecewise-constant process (frequency non-selective isotropic block fading). This paper addresses the finite blocklength fundamental limits of this channel model. Specifically, we give a formula for the channel dispersion—a quantity governing the delay required to achieve capacity. The multiplicative nature of the fading disturbance leads to a number of interesting technical difficulties that required us to enhance traditional methods for finding the channel dispersion. Alas, one difficulty remains: the converse (impossibility) part of our result holds under an extra constraint on the growth of the peak-power with blocklength. Our results demonstrate, for example, that while the capacities of $n_{t}\times n_{r}$ and $n_{r} \times n_{t}$ antenna configurations coincide (under fixed received power), the coding delay can be sensitive to this switch. For example, at the received SNR of 20 dB, the $16\times 100$ system achieves capacity with codes of length (delay) which is only 60% of the length required for the $100\times 16$ system. Another interesting implication is that for the MISO channel, the dispersion-optimal coding schemes require employing orthogonal designs such as Alamouti’s scheme—a surprising observation considering the fact that Alamouti’s scheme was designed for reducing demodulation errors, not improving coding rate. Finding these dispersion-optimal coding schemes naturally gives a criteria for producing orthogonal design-like inputs in dimensions where orthogonal designs do not exist. [ABSTRACT FROM AUTHOR]

We consider the problem of constructing codes that can correct $\delta $ deletions occurring in an arbitrary binary string of length $n$ bits. Varshamov–Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion $(\delta =1)$ correcting codes and have an asymptotically optimal redundancy. Finding similar codes for $\delta \geq 2$ deletions remains an open problem. In this paper, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the $\delta $ deletions (or insertions) are independent of the code word. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of $\delta $ deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization. [ABSTRACT FROM AUTHOR]

This paper asks how much we can gain in terms of bandwidth and user satisfaction, if recommendation systems became bandwidth aware and took into account not only the user preferences, but also the fact that they may need to serve these users under bandwidth constraints, as is the case over wireless networks. We formulate this as a new problem in the context of index coding: we relax the index coding requirements to capture scenarios where each client has preferences associated with messages. The client is satisfied to receive any message she does not already have, with a satisfaction proportional to her preference for that message. We consistently find, over a number of scenarios we sample, that although the optimization problems are in general NP-hard, significant bandwidth savings are possible even when restricted to polynomial time algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we extend Construction A of lattices to the ring of algebraic integers of a general imaginary quadratic field that may not form a principal ideal domain (PID). We show that such a construction can produce good lattices for coding in the sense of Poltyrev and for MSE quantization. As an application, we then apply the proposed lattices to the compute-and-forward paradigm with limited feedback. Without feedback, compute-and-forward is typically realized with lattice codes over the ring of integers, the ring of Gaussian integers, or the ring of Eisenstein integers, which are all PIDs. A novel scheme called adaptive compute-and-forward is proposed to exploit the limited feedback about the channel state by working with the best ring of imaginary quadratic integers. Simulation results show that by adaptively choosing the best ring among the considered ones according to the limited feedback, the proposed adaptive compute-and-forward provides a better performance than that provided by the conventional compute-and-forward scheme which works over Gaussian or Eisenstein integers solely. [ABSTRACT FROM AUTHOR]