Search

This paper focuses on the design and evaluation of pragmatic schemes for delay-sensitive communication. Specifically, this contribution studies the operation of data links that employ incremental redundancy as a means to shield information bits from the degradation associated with unreliable channels. While this inquiry puts forth a general methodology, exposition centers around erasure channels because they are well suited for analysis. Nevertheless, the goal is to identify both structural properties and design guidelines that are broadly applicable. Conceptually, this paper leverages a methodology, termed sequential differential optimization, aimed at identifying near-optimal block sizes for hybrid ARQ. This technique is applied to erasure channels and it is extended to scenarios where throughput is maximized subject to a constraint on the feedback rate. The analysis shows that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when maximizing throughput. Ultimately, block size selection is informed by approximate distributions on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid automatic repeat request and coding, offers a computationally efficient framework to select code rates and blocklengths for incremental redundancy. These findings are supported through numerical results. [ABSTRACT FROM AUTHOR]

This paper studies the distributed linearly separable computation problem, which is a generalization of many existing distributed computing problems such as distributed gradient coding and distributed linear transform. A master asks ${\mathsf {N}}$ distributed workers to compute a linearly separable function of ${\mathsf {K}}$ datasets, which is a set of ${\mathsf {K}}_{\mathrm{ c}}$ linear combinations of ${\mathsf {K}}$ equal-length messages (each message is a function of one dataset). We assign some datasets to each worker in an uncoded manner, who then computes the corresponding messages and returns some function of these messages, such that from the answers of any ${\mathsf {N}}_{\mathrm{ r}}$ out of ${\mathsf {N}}$ workers the master can recover the task function with high probability. In the literature, the specific case where ${\mathsf {K}}_{\mathrm{ c}}=1$ or where the computation cost is minimum has been considered. In this paper, we focus on the general case (i.e., general ${\mathsf {K}}_{\mathrm{ c}} $ and general computation cost) and aim to find the minimum communication cost. We first propose a novel converse bound on the communication cost under the constraint of the popular cyclic assignment (widely considered in the literature), which assigns the datasets to the workers in a cyclic way. Motivated by the observation that existing strategies for distributed computing fall short of achieving the converse bound, we propose a novel distributed computing scheme for some system parameters. The proposed computing scheme is optimal for any assignment when ${\mathsf {K}}_{\mathrm{ c}}$ is large and is optimal under the cyclic assignment when the numbers of workers and datasets are equal or ${\mathsf {K}}_{\mathrm{ c}}$ is small. In addition, it is order optimal within a factor of 2 under the cyclic assignment for the remaining cases. [ABSTRACT FROM AUTHOR]

The growing number of Internet of Thing (IoT) and Ultra-Reliable Low Latency Communications (URLCC) use cases in next generation communication networks calls for the development of efficient Forward Error Correction (FEC) mechanisms. These use cases usually imply using short to mid-sized information blocks and requires low-complexity and/or fast decoding procedures. This paper investigates the joint learning of short to mid block-length coding schemes and associated Belief-Propagation (BP) like decoders using Machine Learning (ML) techniques. An interpretable auto-encoder (AE) architecture is proposed, ensuring scalability to block sizes currently challenging for ML-based linear block code design approaches. By optimizing a coding scheme w.r.t. the targeted decoder, the proposed system offers a good complexity/performance trade-off compared to various codes from literature with length up to 128 bits. [ABSTRACT FROM AUTHOR]

The design of zero-delay Joint Source-Channel Coding (JSCC) schemes for the transmission of correlated information over fading Multiple Access Channels (MACs) is an interesting problem for many communication scenarios like Wireless Sensor Networks (WSNs). Among the different JSCC schemes so far proposed for this scenario, Distributed Quantizer Linear Coding (DQLC) represents an appealing solution since it is able to outperform uncoded transmissions for any correlation level at high Signal-to-Noise Ratios (SNRs) with a low computational cost. In this paper, we extend the design of DQLC-based schemes for fading MACs considering sphere decoding to make the optimal Minimum Mean Squared Error (MMSE) estimation computationally affordable for an arbitrary number of transmit users. The use of sphere decoding also allows to formulate a practical algorithm for the optimization of DQLC-based systems. Finally, non-linear Kalman Filtering for the DQLC is considered to jointly exploit the temporal and spatial correlation of the source symbols. The results of computer experiments show that the proposed DQLC scheme with the Kalman Filter decoding approach clearly outperforms uncoded transmissions for medium and high SNRs. [ABSTRACT FROM AUTHOR]

In this paper, two new decoding algorithms to decode Reed–Solomon codes during transmission over burst Rayleigh fading channels with additive white Gaussian noise (AWGN) are proposed. They only conduct error correction for coded symbols located in the pure AWGN region and conduct error and erasure correction for those symbols located in the burst fading region by treating those coded symbols that are very likely erroneous as erasures. The first algorithm does not need to know the fading locations in advance, while the second algorithm assumes that the fading locations are known. In addition, the performance of such two algorithms is studied when a pre-computed threshold is used to determine the erasures of the code. Simulation results show that our proposed algorithms not only significantly perform better than the classic Berlekamp–Messay algorithm with a comparable computational complexity but also achieve a better tradeoff between the performance and the computational complexity when compared with other existing algorithms. In particular, our algorithms exhibit excellent robustness for tested various code parameters and fading configurations. Furthermore, a more detailed mathematical analysis is also developed in this paper in order to estimate the performance of the new algorithms in the burst Rayleigh fading channels. We observe that the performance of the first algorithm can only be estimated relatively accurately when encountering burst deep-fading, whereas the performance prediction for the second algorithm is always in agreement with the simulation results for various fading cases. [ABSTRACT FROM AUTHOR]

In this paper, we show how the presence of locality within a binary cyclic code can be exploited to improve decoding performance and to reduce decoding complexity. We pursue two approaches. Under the first approach, we show how the ordered statistics decoding (OSD) method can be modified by inserting a simple single round belief-propagation step at the start that involves only the local codes. The resultant locality-aware OSD algorithm yields an appreciable signal-to-noise ratio (SNR) gain for a given level of reliability and essentially the same level of decoder complexity. Under the second, trellis decoding approach, we show that the careful introduction of locality results in the creation of a cyclic subcode that possesses lower maximum state complexity. In addition, we present a simple means of deriving an upper bound to the state complexity profile of any cyclic code that is based only on the zeros of the code. Furthermore, we show how the decoding speed of either locality-aware OSD or trellis decoding can be significantly increased in the presence of locality, in the moderate-to-high SNR regime, by making the use of a quick-look decoder that often returns the maximum likelihood code word. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) are introduced in distributed storage systems due to their low repair overhead. An LRC is called optimal if its minimum distance attains the Singleton-like upper bound. Chen et al. (2018) recently studied the constructions of optimal $(r, \delta)$ -LRCs with length $n \mid (q+1)$ and $(r+\delta -1) \mid n$ , where many classes of optimal cyclic constructions were obtained. In this paper, by employing constacyclic MDS codes, we construct seven classes of optimal $(r, \delta)$ -LRCs with new parameters. After adding these new optimal LRCs via constacyclic codes, we have completely obtained all optimal $(r, \delta)$ -LRCs with length $n \mid (q+1)$ and $(r+\delta -1) \mid n$ for all possible parameters for the completeness in the coding theory. It is worth noting that the optimal constacyclic LRCs with new parameters provide more alternatives to cyclic LRCs in the practical demands of distributed storage systems, where specific values of $n$ , $k$ , $r$ , and $\delta $ are required. Moreover, constacyclic LRCs also possess the encoding and decoding efficiency as cyclic LRCs. [ABSTRACT FROM AUTHOR]

In this paper, the upper bound and asymptotical approximation for the bit error rate (BER) as well as for the frame error rate of linear block codes under maximum-likelihood decoding operating over exponentially correlated (EC) generalized-fading channels are proposed. Particularly, our analysis takes the convolutional codes as an example and three different fading scenarios are considered, namely Rice, Nakagami- $m$ , and Weibull fading. Such scenarios have a common property that is spherically invariant random process (SIRP). Our analysis relies on the derivation of new lower bounds per each eigenvalue since the BER as well as the FER expressions are written in terms of the pairwise error probability, which by its turn depends on the eigenvalues of the channel covariance matrix. Based on that, the upper bounds and asymptotic expressions of the considered metrics subject to the three above fading models are derived, which show to be tighter than the previous results published elsewhere in the literature, especially for the high signal-to-noise ratio regions. [ABSTRACT FROM AUTHOR]

Circular-shift linear network coding (LNC) is a class of vector LNC with low encoding and decoding complexities, and with local encoding kernels chosen from cyclic permutation matrices. When $L$ is a prime with primitive root 2, it was recently shown that a scalar linear solution over GF($2^{L-1}$) induces an $L$ -dimensional circular-shift linear solution at rate $(L-1)/L$. In this paper, we prove that for arbitrary odd $L$ , every scalar linear solution over GF($2^{m_{L}}$), where $m_{L}$ refers to the multiplicative order of 2 modulo $L$ , can induce an $L$ -dimensional circular-shift linear solution at a certain rate. Based on the generalized connection, we further prove that for such $L$ with $m_{L}$ beyond a threshold, every multicast network has an $L$ -dimensional circular-shift linear solution at rate $\phi (L)/L$ , where $\phi (L)$ is the Euler’s totient function of $L$. An efficient algorithm for constructing such a solution is designed. Finally, we prove that every multicast network is asymptotically circular-shift linearly solvable. [ABSTRACT FROM AUTHOR]

The principal mission of multi-source multicast (MSM) is to disseminate all messages from all sources in a network to all destinations. MSM is utilized in numerous applications. In many of them, securing the messages disseminated is critical. A common secure model is to consider a network where there is an eavesdropper which is able to observe a subset of the network links, and seeks a code which keeps the eavesdropper ignorant regarding all the messages. While this is solved when all messages are located at a single source, secure MSM (SMSM) is an open problem, and the rates required are hard to characterize in general. In this paper, we consider individual security, which promises that the eavesdropper has zero mutual information with each message individually, or, more generally, with sub sets of messages. We completely characterize the rate region for SMSM under individual security, and show that such a security level is achievable at the full capacity of the network, that is, the cut-set bound is the matching converse, similar to non-secure MSM. Moreover, we show that the field size is similar to non-secure MSM and does not have to be larger due to the security constraint. [ABSTRACT FROM AUTHOR]

In this paper, we present the block Markov superposition transmission of BCH (BMST-BCH) codes, which can be constructed to obtain a very low error floor. To reduce the implementation complexity, we design a low complexity iterative sliding-window decoding algorithm, in which only binary and/or erasure messages are processed and exchanged between processing units. The error floor can be predicted by the proposed genie-aided lower bounds, while the waterfall performance can be analyzed by the density evolution method. To evaluate the error floor of the constructed BMST-BCH codes at a very low bit error rate (BER) region, we propose a fast simulation approach. Numerical results show that, at a target BER of $10^{-15}$ , the proposed BMST-BCH code with hard-decision can achieve a net coding gain (NCG) of 10.55 dB with 25% overhead, while a soft-decision design can yield an NCG of 10.74 dB. The construction of BMST-BCH codes is flexible to trade off latency against performance at all overheads of interest and may find applications in optical transport networks as an attractive candidate. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA in the initial iterations using a quadratic approximation, and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate the non-linear behavior of SPA at around the operating point of zero in all iterations. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model. We also make connections to the semi-analytical code-dependent technique proposed by Richardson for the error floor estimation of LDPC codes, and demonstrate that the proposed state-space model not only is a fully-analytical code-independent counterpart to that method, but also has less complexity and, in some cases, more accuracy. [ABSTRACT FROM AUTHOR]

The problem of computing the Hamming weight distribution of linear codes is considered in this paper. A novel method to enumerate all codewords up to a certain Hamming weight for binary linear block codes in general and in particular for the punctured, shortened, precoded polar codes is introduced. The proposed approach performs a recursive decomposition of the codes using construction X4 that is typically used to combine codes of different lengths. This allows to enumerate the low-weight codewords of the overall code as combinations of the low-weight codewords of the component codes. Numerical results show that the proposed approach can efficiently compute the exact partial weight distribution of the 5G New Radio punctured/shortened polar codes with CRC11 and pure polar codes. In the former and latter cases, the low-weight codeword number is up to 106 and 108, respectively. Besides, randomly punctured and shortened polar codes and randomly precoded polar codes are also considered. To the best of the authors’ knowledge, this is the first method able to solve these problems. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the maximum likelihood decoding performance of Raptor codes with a systematic low-density generator-matrix code as the pre-code. By investigating the rank of the product of two random coefficient matrices, we derive upper and lower bounds on the decoding failure probability. The accuracy of our analysis is validated through simulations. Results of extensive Monte Carlo simulations demonstrate that for Raptor codes with different degree distributions and pre-codes, the bounds obtained in this paper are of high accuracy. The derived bounds can be used to design near-optimum Raptor codes with short and moderate lengths. [ABSTRACT FROM AUTHOR]

In this paper, the problem of designing a forward link linear precoder for massive multiple-input multiple-output (MIMO) systems in conjunction with quadrature amplitude modulation (QAM) is addressed. A challenge in such system design is to consider finite alphabet inputs, especially with larger constellation sizes, such as $M\geq 16$ . First, we employ a novel and efficient methodology that allows for an orthogonal, sparse representation of multiple users and groups in a fashion similar to joint spatial division and multiplexing (JSDM), thus offering an extension of JSDM to finite alphabet data symbols. We term the new approach JSDM for finite alphabets (JSDM-FA). JSDM-FA employs virtual channel model beams in order to explore the orthogonality between different groups. Then, we present a natural generalization of JSDM-FA to the frequency-selective case with orthogonal frequency-division multiplexing (OFDM) and also enhance OFDM with combined frequency and spatial division and multiplexing. This configuration offers high flexibility in Massive MIMO systems, as it is capable of offering separate decoding of each user data within a group or increase the spectral efficiency of spatially overlapping groups without sacrificing the overall cell spectral efficiency. The proposed methodology is next applied jointly with the complexity-reducing Per-Group Processing within groups technique, on a per user group basis, in conjunction with QAM modulation and in simulations, for constellation size up to $M=64$ . We show by numerical results that the precoders developed offer significantly better performance than the configuration with no precoder or the plain beamformer and with $M\geq 16$ . [ABSTRACT FROM PUBLISHER]

Most multi-dimensional (more than two dimensions) lattice partitions only form additive quotient groups and lack multiplication operations. This prevents us from constructing lattice codes based on multi-dimensional lattice partitions directly from non-binary linear codes over finite fields. In this paper, we design lattice codes from Construction A lattices where the underlying linear codes are non-binary irregular repeat-accumulate (IRA) codes. Most importantly, our codes are based on multi-dimensional lattice partitions with finite constellations. We propose a novel encoding structure that adds randomly generated lattice sequences to the encoder’s messages, instead of multiplying lattice sequences to the encoder’s messages. We prove that our approach can ensure that the decoder’s messages exhibit permutation-invariance and symmetry properties. With these two properties, the densities of the messages in the iterative decoder can be modeled by Gaussian distributions described by a single parameter. With Gaussian approximation, extrinsic information transfer charts for our multi-dimensional IRA lattice codes are developed and used for analyzing the convergence behavior and optimizing the decoding thresholds. Simulation results show that our codes can approach the unrestricted Shannon limit within 0.46 dB and outperform the previously designed lattice codes with 2-D lattice partitions and existing lattice coding schemes for large codeword length. [ABSTRACT FROM PUBLISHER]

In this paper, we analyze Luby transform (LT) and Raptor codes under inactivation decoding. A first-order analysis is introduced, which provides the expected number of inactivations for an LT code, as a function of the output distribution, the number of input symbols, and the decoding overhead. The analysis is then extended to the calculation of the distribution of the number of inactivations. In both cases, random inactivation is assumed. The developed analytical tools are then exploited to design LT and Raptor codes, enabling a tight control on the decoding complexity versus failure probability tradeoff. The accuracy of the approach is confirmed by numerical simulations. [ABSTRACT FROM AUTHOR]

A matrix is termed superregular if all of its possible submatrices are non-singular. Superregular lower triangular Toeplitz matrices are useful for MDS convolutional codes and (sequential) network codes. In this paper, we present the explicit matrix constructions for superregular lower triangular Toeplitz matrices in \mathrm GF(2^p)^k \times k, k \leq 5 . For $k > 5$ we provide a greedy algorithm, which (over sufficiently large fields) is guaranteed to find a superregular lower triangular Toeplitz matrix. We introduce (product preserving) joint superregularity, and extend our explicit matrix constructions to these cases. We provide methods for deriving the exact symbol loss probability and delay for any deterministic block code. We derive the exact symbol loss probability and delay for codes using a superregular lower triangular matrix and for codes using two (product preserving) jointly superregular lower triangular matrices. We then compare these results with those obtained from both simulations and our practical implementation, and for each case we also compare with random-based codes. Furthermore, our experiments show a gain in coding throughput above 40% for superregular lower triangular Toeplitz matrices over random matrices. [ABSTRACT FROM AUTHOR]

In this paper, a class of $p$ -ary 3-weight linear codes and a class of binary 2-weight linear codes are proposed respectively by virtue of the properties of the perfect nonlinear functions over $\mathbb {F}_{p^{m}}$ and $(m,s)$ -bent functions from $\mathbb {F}_{2^{m}}$ to $\mathbb {F}_{2^{s}}$ , where $p$ is an odd prime and $m, s$ are positive integers. The weight distributions are completely determined by the sign of the Walsh transform of weakly regular bent functions and the size of the preimage of the employed $(m,s)$ -bent functions at the zero point, respectively. As a special case, a class of optimal linear codes meeting Griesmer bound is obtained from our construction. [ABSTRACT FROM AUTHOR]

In this paper, linear index codes with multiple senders are studied, where every receiver receives encoded messages from all senders. A new fitting matrix for the multiple senders is proposed and it is proved that the minimum rank of the proposed fitting matrices is the optimal codelength of linear index codes for the multiple senders. In addition, a new type of a side information graph related with the optimal codelength is proposed and whether given side information is critical or not is studied. Furthermore, linear index codes for the cellular network scenario are studied, where each receiver can receive a subset of sub-codewords. Since some receivers cannot receive the entire codeword in the cellular network scenario, the encoding method based on the fitting matrix has to be modified. In the cellular network scenario, we propose another fitting matrix and prove that an optimal generator matrix can be found based on these fitting matrices. In addition, some properties on the optimal codelength of linear index codes for the cellular network case are studied. [ABSTRACT FROM AUTHOR]

A class of network codes have been proposed in the literature where the symbols transmitted on network edges are binary vectors and the coding operation performed in network nodes consists of the application of (possibly several) permutations on each incoming vector and XOR-ing the results to obtain the outgoing vector. These network codes, which we will refer to as permute-and-add network codes, involve simpler operations and are known to provide lower complexity solutions than scalar linear network codes. The complexity of these codes is determined by their degree which is the number of permutations applied on each incoming vector to compute an outgoing vector. Constructions of permute-and-add network codes for multicast networks are known. In this paper, we provide a new framework based on group algebras to design permute-and-add network codes for arbitrary (not necessarily multicast) networks. Our framework allows the use of any finite group of permutations (including circular shifts, proposed in prior works) and admits a trade-off between coding rate and the degree of the code. Further, our technique permits elegant recovery and generalizations of the key results on permute-and-add network codes known in the literature. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) are important for distributed storage systems due to their efficient repairing ability of the failed storage nodes. A $q$ -ary optimal $(n,k,r)$ -LRC is an $[n,k,d]$ linear code over $\mathbb {F}_{q}$ such that every code symbol has locality $r$ , and the minimum distance attains the well-known Singleton-like bound. In this paper, we study the maximal code length, code constructions and weight distributions of $q$ -ary optimal LRCs with locality 2 and distance 5, which are of both practical and theoretical interest. Firstly, it is proved that when the code dimension is even or odd, corresponding maximal code lengths of such $q$ -ary optimal LRCs are $3 \cdot \lfloor \frac {q+1}{3} \rfloor $ and $3 \cdot \left \lfloor{ \frac {q-1}{3} }\right \rfloor +5$ , respectively. Up to the equivalence of linear codes, we propose constructions of all the possible $q$ -ary optimal LRCs with locality 2, distance 5 and maximal code length. Then, by characterizing the weight type hierarchy of codewords, we show that the weight distribution of any $q$ -ary optimal LRC with locality 2, distance 5 and even code dimension can be uniquely determined and explicit expression of the weight distribution is given. Moreover, it is shown that all $q$ -ary optimal LRCs with locality 2, distance 5 and even code dimension are maximally recoverable. [ABSTRACT FROM AUTHOR]

Some nonlinear codes, such as Kerdock and Preparata codes, can be represented as binary images under the Gray map of linear codes over rings. This paper introduces MAP decoding of Kerdock and Preparata codes by working with their quaternary representation (linear codes over $\mathbb {Z}_{4}$) with the complexity of $\mathcal {O}(N^{2}\log _{2} N)$ , where N is the code length in $\mathbb {Z}_{4}$. A sub-optimal bitwise APP decoder with good error-correcting performance and complexity of $\mathcal {O}(N\log _{2} N)$ that is constructed using the decoder lifting technique is also introduced. This APP decoder extends upon the original lifting decoder by working with likelihoods instead of hard decisions and is not limited to Kerdock and Preparata code families. Simulations show that our novel decoders significantly outperform several popular decoders in terms of error rate. [ABSTRACT FROM AUTHOR]

Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L -dimensional vector of data symbols over a base field GF( q ). Vector LNC enriches the choices of coding operations at intermediate nodes, and there is a popular conjecture on the benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist (single-source) multicast networks that are vector linearly solvable of dimension L over GF( q . This paper introduces a systematic way to construct such multicast networks, and subsequently establish explicit instances to affirm the positive answer of this conjecture for infinitely many alphabet sizes p^{L} with respect to an arbitrary prime p$ . On the other hand, this paper also presents explicit instances with the special property that they do not have a vector linear solution of dimension L$ over GF(2) but have scalar linear solutions over GF( q'$ ) for some , where $q'$ can be odd or even. This discovery also unveils that over a given base field, a multicast network that has a vector linear solution of dimension $L$ does not necessarily have a vector linear solution of dimension $L' > L$ . [ABSTRACT FROM AUTHOR]

The $T$ -Private Information Retrieval ($T$ -PIR) problem is that a user wishes to retrieve a single record from $N$ servers, without revealing the identity of the desired record even if the number of colluding servers up to $T$. Here every server stores all $M$ records and each record can be viewed as a vector over the $q$ -ary finite field $\mathbb {F}_{q}$. To reduce the field size, a capacity-achieving $T$ -PIR scheme based on some MDS array codes for all possible $N>T,M\geq 2$ was constructed by Xu and Zhang in 2019. A key idea in that scheme is to construct some MDS array codes in query phase, whose generator matrices satisfy the recovery property (see (C1) in , page 6), i.e., there exist some specific columns in each generator matrix such that the number of them is equal to the rank of such matrix. We call the set of each column index of those columns in each generator matrix as the column index set. However, that scheme didn’t give an explicit selection of the column index set satisfying the recovery property. In this paper, let $N=d(2t-1)$ , $N>T=dt>1, M\geq 3$ and $d\geq 1$ , under the constraint of $2^{t-1}\geq N$ , we present a novel method to construct capacity-achieving $T$ -PIR schemes over the binary field with an explicit selection of the column index set. Moreover, our scheme has sub-packetization $N(2t-1)^{M-2}$ , which is optimal for all linear capacity-achieving $T$ -PIR schemes determined by Zhang and Xu in 2019. The key to our method is that all locators and column multipliers are precisely selected such that a Generalized Reed-Solomon (GRS) code defined by them has a zero-dimensional subfield sub-code. Compared with all the known capacity-achieving $T$ -PIR schemes for the same non-trivial parameters, ours is the first explicit capacity-achieving $T$ -PIR scheme over the binary field. [ABSTRACT FROM AUTHOR]

The two-sender unicast index coding problem consists of two senders, each having a different set of messages. Some messages may be common to both the senders. Each receiver demands a unique message and has a subset of messages known as its side-information. The senders transmit coded messages by availing the knowledge of the side-information of all the receivers, such that all the receivers are able to decode their demands. The aim is to find the optimal aggregate number of coded transmissions per message length (also called the optimal broadcast rate with finite length messages), and its limiting value as the message length tends to infinity (also called the optimal broadcast rate). In this paper, only linear coding schemes are considered. Optimal linear broadcast rate for any finite message length and optimal linear broadcast rate for a basic class of the two-sender unicast index coding problem are established. Optimal code-constructions are also provided. These results are given in terms of the corresponding results of three independent single-sender sub-problems of the two-sender unicast index coding problem. Proof techniques used to obtain the results for the two-sender problem are shown to be useful in obtaining the results for some classes of the multi-sender unicast index coding problem. [ABSTRACT FROM AUTHOR]

Evaluating the block error rate of a digital communication system is usually done using the Monte Carlo (MC) simulation method. The main drawback of the Monte Carlo method is the need of a huge sample size for estimating low error rates. Other methods commonly used are the importance sampling technique and the quasi-analytical method. This paper introduces the metric star domain decoder model and shows that many practical decoders fall into this category. The main result is the introduction of a novel SNR-invariant quasi-analytical technique for estimating the block error rate of a communication link over the geodesic channel model (a generalization of a vast number of commonly used channels, including binary symmetric channel, BEC, and AWGN channel) with a metric star domain decoder used at the receiver. This technique outperforms the Monte Carlo and importance sampling methods in both accuracy and speed. It is shown that our quasi-analytical method is at least $10^{3}$ times faster than MC and 10 times faster than IS for the same accuracy. [ABSTRACT FROM AUTHOR]

The interest in polar codes has been increasing significantly since their adoption for use in the 5th generation wireless systems standard. Successive cancellation (SC) decoding algorithm has low implementation complexity, but yields mediocre error-correction performance at the code lengths of interest. SC-Flip algorithm improves the error-correction performance of SC by identifying possibly erroneous decisions made by SC and re-iterates after flipping one bit. It was recently shown that only a portion of bit-channels are most likely to be in error. In this paper, we investigate the average log-likelihood ratio (LLR) values and their distribution related to the erroneous bit-channels, and develop the Thresholded SC-Flip (TSCF) decoding algorithm. We also replace the LLR selection and sorting of SC-Flip with a comparator to reduce the implementation complexity. Simulation results demonstrate that for practical code lengths and a wide range of rates, TSCF shows negligible loss compared with the error-correction performance obtained when all single-errors are corrected. At matching maximum iterations, TSCF has an error-correction performance gain of up to 0.45 dB compared with SC-Flip decoding. At matching error-correction performance, the computational complexity of TSCF is reduced by up to 40% on average and requires up to $5\times $ lower maximum number of iterations. [ABSTRACT FROM AUTHOR]

Locally repairable codes are desirable for distributed storage systems to improve the repair efficiency. In this paper, a connection between locally repairable codes with multiple disjoint repair sets and packings is derived under the condition that each repair set contains exactly one check symbol. Particularly, conditions under which an optimal locally repairable code corresponds to a packing are also characterized. As an application of this connection, some optimal locally repairable codes can be obtained by packings. Specifically, two constructions of locally repairable codes are proposed which not only generalize some known explicit constructions but also give optimal locally repairable codes with flexible new parameters. [ABSTRACT FROM AUTHOR]

This paper proposes a novel lower bound on the Bhattacharyya parameter of synthesized channels in polar codes. The proposed bound is a result of a newly defined merge operation that reduces the cardinality of output alphabets of a symmetric binary-input discrete memoryless channel. By repeated applications of the proposed merge operation, we establish a universal bound on the Bhattacharyya parameters of synthesized channels that holds for any symmetric binary-input discrete memoryless transmission channel. We then discuss some applications of the new bound. For example, using the derived universal lower bound along with the existing upper bound, we find a partial order among the Bhattacharyya parameters of those synthesized channels that cannot be ordered through existing results. This ordering can help efficient design of polar codes. In addition, some extremal behaviors of the binary-symmetric channel are also proved. [ABSTRACT FROM AUTHOR]

We consider the problem of cache-aided Multiuser Private Information Retrieval (MuPIR) which is an extension of the single-user cache-aided PIR problem to the case of multiple users. In cache-aided MuPIR, each of the $K_{\mathrm{ u}}$ cache-equipped users wishes to privately retrieve a message out of $K$ messages from $N$ databases each having access to the entire message library. Demand privacy requires that any individual database learns nothing about the demands of all users. The users are connected to each database via an error-free shared-link. In this paper, we aim to characterize the optimal trade-off between user cache memory and communication load for such systems. First, we propose a novel approach of cache-aided interference alignment (CIA), for the MuPIR problem with $K=2$ messages, $K_{\mathrm{ u}}=2$ users and $N\ge 2$ databases. The CIA approach is optimal when the cache placement is uncoded. For general cache placement, the CIA approach is optimal when $N=2$ and 3 verified by the computer-aided converse approach. Second, for the general case, we propose a product design (PD) which incorporates the PIR code into the linear caching code. The product design is shown to be order optimal within a multiplicative factor of 8 and is exactly optimal in the high memory regime. [ABSTRACT FROM AUTHOR]

Locally recoverable codes play a crucial role in distributed storage systems. Many studies have only focused on the constructions of optimal locally recoverable codes with regard to the Singleton bound. The aim of this paper is to construct optimal binary locally recoverable codes meeting the alphabet-dependent bound. Using a general framework for linear codes associated to a set, we provide a new approach to constructing binary locally recoverable codes with locality 2. We turn the problem of designing optimal binary locally recoverable codes into constructing a suitable set. Several constructions of optimal binary locally recoverable codes are proposed by this new method. Finally, we propose constructions of optimal binary locally recoverable codes with locality 2 and locality parameters $(\text {r},\delta)$ by Griesmer codes. [ABSTRACT FROM AUTHOR]

In this paper, we present a new construction of asymmetric quantum codes (AQCs) by combining classical concatenated codes (CCs) with tensor product codes (TPCs), called asymmetric quantum concatenated and tensor product codes (AQCTPCs) which have the following three advantages. First, only the outer codes in AQCTPCs need to satisfy the orthogonal constraint in quantum codes, and any classical linear code can be used for the inner, which makes AQCTPCs very easy to construct. Second, most AQCTPCs are highly degenerate, which means they can correct many more errors than their classical TPC counterparts. Consequently, we construct several families of AQCs with better parameters than known results in the literature. Third, AQCTPCs can be efficiently decoded although they are degenerate, provided that the inner and outer codes are efficiently decodable. In particular, we significantly reduce the inner decoding complexity of TPCs from Ω (n2an1)(a > 1) to O(n2) by considering error degeneracy, where n1 and n2 are the block length of the inner code and the outer code, respectively. Furthermore, we generalize our concatenation scheme by using the generalized CCs and TPCs correspondingly. [ABSTRACT FROM AUTHOR]

By introducing several levels of recoverability for locally recoverable codes (LRCs), LRCs with hierarchical locality (H-LRCs) are defined for correcting different numbers of erasures. There are two major ingredients in this paper. The first is to investigate some properties and existence conditions of optimal H-LRCs with respect to a generalized Singleton-like bound for H-LRCs. The second ingredient is to propose several constructions of optimal H-LRCs by employing cyclic codes. Notably, the parameters of these optimal H-LRCs are flexible. [ABSTRACT FROM AUTHOR]

In this paper, we investigate an artificial-intelligence (AI) driven approach to design error correction codes (ECC). Classic error-correction code design based upon coding-theoretic principles typically strives to optimize some performance-related code property such as minimum Hamming distance, decoding threshold, or subchannel reliability ordering. In contrast, AI-driven approaches, such as reinforcement learning (RL) and genetic algorithms, rely primarily on optimization methods to learn the parameters of an optimal code within a certain code family. We employ a constructor-evaluator framework, in which the code constructor can be realized by various AI algorithms and the code evaluator provides code performance metric measurements. The code constructor keeps improving the code construction to maximize code performance that is evaluated by the code evaluator. As examples, we focus on RL and genetic algorithms to construct linear block codes and polar codes. The results show that comparable code performance can be achieved with respect to the existing codes. It is noteworthy that our method can provide superior performances to classic constructions in certain cases (e.g., list decoding for polar codes). [ABSTRACT FROM AUTHOR]

Protograph low-density-parity-check (LDPC) codes are considered to design near-capacity low-rate codes over the binary erasure channel and the binary additive white Gaussian noise channel. For protographs with degree-one variable nodes and doubly-generalized LDPC (DGLDPC) codes, conditions are derived to ensure the equality of bit-error threshold and block-error threshold. Using this condition, low-rate codes with block-error threshold close to capacity are designed and shown to have better error rate performance than other existing codes. [ABSTRACT FROM AUTHOR]

For high-rate linear systematic maximum distance separable (MDS) codes, most early constructions could initially optimally repair all the systematic nodes but not all the parity nodes. Fortunately, this issue was first solved by Li et al. in (IEEE Trans. Inform. Theory, 64(9), 6257-6267, 2018), where a transformation that can convert any nonbinary MDS array code into another one with desired properties was proposed. However, the transformation does not work for binary MDS array codes. In this paper, we address this issue by proposing another generic transformation that can convert any $[n, k]$ binary MDS array code into a new one, which endows any $r=n-k\ge 2$ chosen nodes with optimal repair bandwidth and optimal rebuilding access properties, and at the same time, preserves the normalized repair bandwidth/rebuilding access for the remaining $k$ nodes under some conditions. As two immediate applications, we show that 1) by applying the transformation multiple times, any binary MDS array code can be converted into one with optimal rebuilding access for all nodes, 2) any binary MDS array code with optimal repair bandwidth or optimal rebuilding access for the systematic nodes can be converted into one with the corresponding optimality property for all nodes. [ABSTRACT FROM AUTHOR]

Random linear coding (RLC) can improve the performance of multicast transmissions in terms of throughput and energy efficiency. However, RLC and linear codes in general cannot necessarily attain the optimal performance in arbitrary networks. In this regard, partial packet recovery can be considered as a nonlinear strategy to complement such approaches for more general networks. In this paper, we propose a partial packet recovery scheme that benefits from the sparsity of bit errors in partially corrupted RLC packets. As opposed to many previous schemes, it performs without introducing preliminary checksums or preambles, demanding physical layer soft information, or requesting post-redundancy from the transmitter. It relies only on algebraic coding and data processing techniques, the existing knowledge at the receiver, and the conventional acknowledgment messages in RLC. By reconstructing and utilizing the partially corrupted packets that are usually discarded, it can reduce the average number of transmitted RLC packets required for successful decoding by typically 50%, which improves throughput and energy efficiency at the transmitter. We formulate our partial packet recovery in the form of a sparse recovery problem, present its different solutions using compressive sensing theory, discuss their complexity, and present and evaluate a Markov chain model for its performance. [ABSTRACT FROM AUTHOR]

The uplink of a cloud radio access network architecture is studied in which decoding at the cloud takes place via network function virtualization on commercial off-the-shelf servers. In order to mitigate the impact of straggling decoders in this platform, a novel coding strategy is proposed, whereby the cloud re-encodes the received frames via a linear code before distributing them to the decoding processors. Transmission of a single frame is considered first, and upper bounds on the resulting frame unavailability probability as a function of the decoding latency are derived by assuming a binary symmetric channel for uplink communications. Then, the analysis is extended to account for random frame arrival times. In this case, the tradeoff between an average decoding latency and the frame error rate is studied for two different queuing policies, whereby the servers carry out per-frame decoding or continuous decoding, respectively. Numerical examples demonstrate that the bounds are useful tools for code design and that coding is instrumental in obtaining a desirable compromise between decoding latency and reliability. [ABSTRACT FROM AUTHOR]

While many communications media, such as wireless and certain classes of wireline channels, typically lead to bursty errors, most decoders are designed assuming memoryless channels. Consequently, communication systems generally rely on interleaving over tens of thousands of bits to match decoder assumptions. Even for short high rate codes, awaiting sufficient data in interleaving and de-interleaving is a significant source of unwanted latency. We construct an extension to the recently proposed Guessing Random Additive Noise Decoding (GRAND) algorithm, which we call GRAND-MO for GRAND Markov Order. By foregoing interleaving and instead making use of the bursty nature of noise, low-latency communication is possible with block error rates outperforming their interleaved counterparts by a substantial margin. We establish that certain well-known binary codes with structured code-word patterns are ill-suited for use in bursty channels, but Random Linear Codes (RLCs) prove robust to correlated noise. We further demonstrate that by operating directly on modulated symbols rather than de-mapped bits, GRAND-MO achieves further performance and complexity gains by exploiting information that is lost in demodulation. As a result, GRAND-MO provides one potential solution for applications that require ultra-reliable low latency communication. [ABSTRACT FROM AUTHOR]

Designs and methods for nested lattice codes using Construction D’ lattices for coding and convolutional code lattices for shaping are described. Two encoding methods and a decoding algorithm for Construction D’ coding lattices that can be used with shaping lattices for power-constrained channels are given. We construct nested lattice codes with good coding properties, high shaping gain, and low-complexity encoding and decoding. Convolutional code generator polynomials for Construction A lattices with the greatest shaping gain are given, as a result of an extensive search. It is shown that rate 1/3 convolutional codes provide a more favorable performance-complexity trade-off than rate 1/2 convolutional codes. Tail-biting convolutional codes have higher shaping gain than that of zero-tailed convolutional codes. A design for quasi-cyclic low-density parity-check (QC-LDPC) codes to form Construction D’ lattices which have efficient encoding and indexing is presented. The resulting QC-LDPC Construction D’ lattices are evaluated using four shaping lattices: the $E_{8}$ lattice, the $BW_{16}$ lattice, the Leech lattice and our best-found convolutional code lattice, showing a shaping gain of approximately 0.65 dB, 0.86 dB, 1.03 dB and 1.25 dB at dimension 2304. [ABSTRACT FROM AUTHOR]

We studied power splitting-based simultaneous wireless information and power transfer (PS-SWIPT) in multiple access channels (MACs), considering the decoding cost and non-linear energy harvesting (EH) constraints at the receiving nodes to study practical limitations of an EH communication system. Under these restrictions, we formulated and analyzed the achievable rate and maximum departure regions in two well-studied scenarios, i.e., a classical PS-SWIPT MAC and a PS-SWIPT MAC with user cooperation. In the classical PS-SWIPT MAC setting, closed-form expressions for the optimal values of the PS factors are derived for two fundamental decoding schemes: simultaneous decoding and successive interference cancellation. In the PS-SWIPT MAC with user cooperation, the joint optimal power allocation for users as well as the optimal PS factor are derived. This reveals that one decoding scheme outperforms the other in the classical PS-SWIPT MAC, depending on the function type of the decoding cost. Finally, it is shown that the cooperation between users can potentially boost the performance of a PS-SWIPT MAC under decoding cost and non-linear EH constraints. Moreover, effects of the decoding cost functions, non-linear EH model and channel quality between the users are studied, and performance characteristics of the system are discussed. [ABSTRACT FROM AUTHOR]

A novel method to recursively construct a set of precoded polar codes of various rates and short-to-moderate lengths is presented. The proposed code design method minimizes the successive cancellation (SC) decoding error probability estimate under three constraints. The first constraint is the minimum distance requirement to improve the maximum-likelihood (ML) performance of the resulting code and therefore the performance under the SC list (SCL) decoding. The other two constraints introduce preselected supercode and subcode, where the supercode ensures fast computation of the minimum distance and the subcode ensures reduction of the search space size. The supercode is given by the Plotkin sum of shorter codes, which are nested to simplify computation of low-weight codewords. These low-weight codewords are needed to satisfy the minimum distance constraint. The simulation results indicate that the proposed precoded polar codes of lengths 128 and 256 provide a better frame error rate (FER) than polar codes with CRC and e-BCH polar subcodes under the SCL decoding algorithm with the list size $8-128$. [ABSTRACT FROM AUTHOR]

We propose a new probabilistic amplitude shaping (PAS) scheme based on short linear block codes. In the proposed system, the capacity-approaching signal distribution is generated in the process of decoding linear block codes for a given information bit sequence. We associate the design problem of shaping codes with the classical covering problem, suggesting the use of good covering codes for shaping. From simulation results, it is demonstrated that by selecting perfect binary codes as our shaping codes, the proposed scheme offers a shaping gain of around 0.3–1.0 dB. By comparing with the enumerative sphere shaping (ESS) of the same block length, we verify that the proposed scheme achieves significantly lower storage complexity and computational complexity at the receiver even with comparable block error rate performance. [ABSTRACT FROM AUTHOR]

We study the cooperative data exchange problem for fully connected networks. In this problem, nodes make broadcast transmissions to recover a file consisting of $K$ independent packets. Each node initially only possesses a subset of the packets. We propose $(d,K)$ -Basis Searching, a deterministic polynomial-time minimization approach, to calculate the minimum rate for this problem. $(d,K)$ -Basis Searching has strictly reduced complexity compared with the state-of-the-art algorithms, which are based on submodular function minimization. We extend our algorithm to a generalized problem: the so-called successive local omniscience problem. [ABSTRACT FROM AUTHOR]

In his pioneering work on LDPC codes, Gallager dismissed codes with parity-check matrices of weight two after proving that their minimum Hamming distances grow at most logarithmically with their code lengths. In spite of their poor minimum Hamming distances, it is shown that quasi-cyclic LDPC codes with parity-check matrices of column weight two have good capability to correct phased bursts of erasures which may not be surpassed by using quasi-cyclic LDPC codes with parity-check matrices of column weight three or more. By modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. Quasi-cyclic LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel are also considered. Examples of such codes based on Reed-Solomon and Gabidulin codes are presented. [ABSTRACT FROM AUTHOR]

Wireless random access protocols are attracting a revived research interest as a simple yet effective solution for machine-type communications. In the quest to improve reliability and spectral efficiency of such schemes, the use of multiple receivers has recently emerged as a promising option. We study the potential of this approach considering a population of users that transmit data packets following a simple slotted ALOHA policy to a set of uncoordinated relays (phase-1). These, in turn, independently forward – part of – what decoded towards a collecting sink (phase-2). For an on-off fading channel model, we provide exact expressions for phase-1 throughput and packet loss rate for an arbitrary number of relays, characterising the benefits of multi-receiver schemes. Moreover, a lower bound on the minimum amount of phase-2 resources needed to deliver all information collected at the relays is provided. The bound is proven to be achievable via random linear coding when no constraints in terms of latency are set, with an overhead that approaches zero with the inverse of the packet length. We complement our study discussing a family of simple forwarding policies that require no packet-level coding, and optimising their performance based on the amount of available phase-2 resources. The behaviour of both random linear coding and simplified policies is also characterised when receivers are equipped with finite buffers, revealing non-trivial tradeoffs. [ABSTRACT FROM AUTHOR]

High quality data is essential in deep learning to train a robust model. While in other fields data is sparse and costly to collect, in error decoding it is free to query and label thus allowing potential data exploitation. Utilizing this fact and inspired by active learning, two novel methods are introduced to improve Weighted Belief Propagation (WBP) decoding. These methods incorporate machine-learning concepts with error decoding measures. For BCH(63,36), (63,45) and (127,64) codes, with cycle-reduced parity-check matrices, improvement of up to 0.4dB at the waterfall region, and of up to 1.5dB at the error-floor region in FER, over the original WBP, is demonstrated by smartly sampling the data, without increasing inference (decoding) complexity. The proposed methods constitutes an example guidelines for model enhancement by incorporation of domain knowledge from error-correcting field into a deep learning model. These guidelines can be adapted to any other deep learning based communication block. [ABSTRACT FROM AUTHOR]