Search

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arıkan style constructions. This paper, which is presented in two parts, solves this problem by providing a necessary and sufficient condition for a binary operation to be polarizing. This (first) part of this paper introduces the mathematical framework that we will use in the second part to characterize the polarizing operations. We define uniformity preserving, irreducible, ergodic, and strongly ergodic operations, and we study their properties. The concepts of a stable partition and the residue of a stable partition are introduced. We show that an ergodic operation is strongly ergodic if and only if all its stable partitions are their own residues. We also study the products of binary operations and the structure of their stable partitions. We show that the product of a sequence of binary operations is strongly ergodic if and only if all the operations in the sequence are strongly ergodic. In the second part of this paper, we provide a foundation of polarization theory based on the ergodic theory of binary operations that we develop in this part. [ABSTRACT FROM PUBLISHER]

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]

Motivated by the work of Dahrouj and Yu in applying the Han-Kobayashi transmission strategy for mitigating the intercell interference in a multi-cell multi-user multiple-input single-output interference network (MISO IN), this paper considers splitting messages into private and common parts in a multi-cell multi-user MIMO IN. Specifically, the covariances of the private messages and common messages are designed to optimize either the sum rate or the minimal rate. The common messages and private messages are decoded in sequence using successive decoding. This paper shows how these difficult optimization problems can be adequately solved by means of d.c. (difference of concave functions) optimization over a simple convex set. Numerical and simulation results also reveal the great advantage of our proposed solutions for various types of INs. In particular, the proposed solutions are shown to outperform the algorithm developed by Dahrouj and Yu for the simpler case of the MISO IN. [ABSTRACT FROM PUBLISHER]

In this article, we present a new construction of evaluation codes in the Hamming metric, which we call twisted Reed–Solomon codes. Whereas Reed–Solomon (RS) codes are MDS codes, this need not be the case for twisted RS codes. Nonetheless, we show that our construction yields several families of MDS codes. Further, for a large subclass of (MDS) twisted RS codes, we show that the new codes are not generalized RS codes. To achieve this, we use properties of Schur squares of codes as well as an explicit description of the dual of a large subclass of our codes. We conclude the paper with a description of a decoder, that performs very well in practice as shown by extensive simulation results. [ABSTRACT FROM AUTHOR]

This paper considers “ $\delta $ -almost Reed–Muller codes”, i.e., linear codes spanned by evaluations of all but a $\delta $ fraction of monomials of degree at most $d$. It is shown that for any $\delta > 0$ and any $\varepsilon >0$ , there exists a family of $\delta $ -almost Reed–Muller codes of constant rate that correct $1/2- \varepsilon $ fraction of random errors with high probability. For exact Reed–Muller codes, the analogous result is not known and represents a weaker version of the longstanding conjecture that Reed–Muller codes achieve capacity for random errors (Abbe-Shpilka-Wigderson STOC ’15). Our proof is based on the recent polarization result for Reed–Muller codes, combined with a combinatorial approach to establishing inequalities between the Reed–Muller code entropies. [ABSTRACT FROM AUTHOR]

We study a class of real robust phase retrieval problems under a Gaussian assumption on the coding matrix when the received signal is sparsely corrupted by noise. The goal is to establish conditions on the sparsity under which the input vector can be exactly recovered. The recovery problem is formulated as residual minimization in the $\ell _{1}$ -norm. The main contribution is a robust phase retrieval counterpart to the seminal paper by Candes and Tao on compressed sensing ($\ell _{1}$ regression) [Decoding by linear programming. IEEE Transactions on Information Theory, 51(12):4203–4215, 2005]. The analysis depends on a key new property of the coding matrix called the Absolute Range Property (ARP) which is the analogue to the Null Space Property (NSP) in compressed sensing. When the residuals are computed using squared magnitudes, we show that ARP follows from a standard Restricted Isometry Property (RIP). However, when the residuals are computed using absolute magnitudes, a different kind of RIP or growth property is required. We conclude by showing that the robust phase retrieval objectives are sharp with respect to their minimizers with high probability. [ABSTRACT FROM AUTHOR]

Interference alignment (IA) is a promising technique for interference management in wireless networks. However, most of the existing IA works are based on symmetric multiuser networks. To meet the requirements of practical applications, we consider asymmetric networks where the location of each user is randomly distributed. When the path loss is large, interference may become sufficiently weak, and aligning the interference via IA becomes unnecessary. In this paper, a spectrum-efficient topology management (TM) scheme is proposed for asymmetric interference networks. In this scheme, for a user far away from others, solely adopting spatial multiplexing (SM) as a point-to-point multiple-input and multiple-output subnetwork is more spectrum efficient. On the other hand, for the users close to each other, jointly comprising an IA subnetwork can be the better choice. Thus, we first present the decision criterion, which is used for reinterpreting the network as a graph. Then, the TM scheme is elaborated with the graph theory. In addition, we present the designs of the precoding and decoding matrices for the IA and SM subnetworks. Simulation results show that the proposed TM scheme is much more spectrum efficient than the conventional IA scheme in asymmetric interference networks. [ABSTRACT FROM AUTHOR]

A network of three nodes mutually communicating with each other is studied. This multi-way network is a suitable model for three-user device-to-device communications. The main goal of this paper is to characterize the capacity region of the underlying Gaussian three-way channel (3WC) within a constant gap. To this end, a capacity outer bound is derived using cut-set bounds and genie-aided bounds. For achievability, the 3WC is first transformed into an equivalent star channel. This latter is then decomposed into a set of “successive” sub-channels, leading to a sub-channel allocation problem. Using backward decoding, interference neutralization, and known results on the capacity of the star-channel relying of physical-layer network coding, an achievable rate region for the 3WC is obtained. It is then shown that the achievable rate region is within a constant gap of the developed outer bound, leading to the desired capacity approximation. Interestingly, in contrast to the Gaussian two-way channel (TWC), adaptation is necessary in the 3WC. Furthermore, message splitting is another ingredient of the developed scheme for the 3WC, which is not required in the TWC. The two setups are, however, similar in terms of their sum-capacity pre-log, which is equal to 2. Finally, some interesting networks and their approximate capacities are recovered as special cases of the 3WC, such as the cooperative broadcast channel and multiple access channel. [ABSTRACT FROM PUBLISHER]

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters $(q,d,k)$ , namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes. [ABSTRACT FROM AUTHOR]

Symbol-pair codes introduced by Cassuto and Blaum (2010) are designed to protect against pair errors in symbol-pair read channels. The higher the minimum pair distance, the more pair errors the code can correct. Maximum distance separable (MDS) symbol-pair codes are optimal in the sense that pair distance cannot be improved for given length and code size. The contribution of this paper is twofold. First, we present three lower bounds for the minimum pair distance of constacyclic codes, the first two of which generalize the previously known results due to Cassuto and Blaum (2011) and Kai et al. (2015). The third one exhibits a lower bound for the minimum pair distance of repeated-root cyclic codes. Second, we obtain new MDS symbol-pair codes with minimum pair distance seven and eight through repeated-root cyclic codes. [ABSTRACT FROM AUTHOR]

This paper attempts to highlight the decoding capabilities of MDP convolutional codes over the erasure channel by defining them as discrete linear dynamical systems, with which the controllability property and the observability characteristics of linear system theory can be applied, in particular those of output observability, easily described using matrix language. Those are viewed against the decoding capabilities of MDS block codes over the same channel. Not only is the time complexity better but the decoding capabilities are also increased with this approach because convolutional codes are more flexible in handling variable-length data streams than block codes, where they are fixed-length and less adaptable to varying data lengths without padding or other adjustments.

In general, the problem of building optimal convolutional codes under a certain criteria is hard, especially when size field restrictions are applied. In this paper, we confront the challenge of constructing an optimal 2D convolutional code when communicating over an erasure channel. We propose a general construction method for these codes. Specifically, we provide an optimal construction where the decoding method presented in the bibliography is considered.

Let p be a prime, and \lambda be a nonzero element of the finite field \mathbb Fp^{m} . The \lambda -constacyclic codes of length p^s over \mathbb Fp^{m} are linearly ordered under set-theoretic inclusion, i.e., they are the ideals \langle (x-\lambda 0)^{i} \rangle , 0 \leq i \leq p^s of the chain ring [(\mathbb Fp^{m[x]})/({\langle x^{p^{s}}-\lambda \rangle })] . This structure is used to establish the symbol-pair distances of all such $\lambda$ -constacyclic codes. Among others, all maximum distance separable symbol-pair constacyclic codes of length p^s are obtained. [ABSTRACT FROM AUTHOR]

Solving Math Word Problems (MWPs) automatically is a challenging task for AI-tutoring in online education. Most of the existing State-Of-The-Art (SOTA) neural models for solving MWPs use Goal-driven Tree-structured Solver (GTS) as their decoders. However, owing to the defects of the tree-structured recurrent neural networks, GTS can not obtain the information of all generated nodes in each decoding time step. Therefore, the performance for long math expressions is not satisfactory enough. To address such limitations, we propose a Goal Selection and Feedback (GSF) decoding module. In each time step of GSF, we firstly feed the latest result back to all goal vectors through goal feedback operation, and then the goal selection operation based on attention mechanism is designed for generate the new goal vector. Not only can the decoder collect the historical information from all generated nodes through goal selection operation, but also these generated nodes are always updated timely by goal feedback operation. In addition, a Multilayer Fusion Network (MFN) is proposed to provide a better representation of each hidden state during decoding. Combining the ELECTRA language model with our novel decoder, experiments on the Math23k, Ape-clean, and MAWPS datasets show that our model outperforms the SOTA baselines, especially on the MWPs of complex samples with long math expressions. The ablation study and case study further verify that our model can better solve the samples with long expressions, and the proposed components are indeed able to help enhance the performance of the model. [ABSTRACT FROM AUTHOR]

List-decodability of Reed–Solomon codes has received a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form $r=1-\varepsilon $ for $\varepsilon $ tending to zero. Our main result states that there exist Reed–Solomon codes with rate $\Omega (\varepsilon)$ which are $(1-\varepsilon, O(1/\varepsilon))$ -list-decodable, meaning that any Hamming ball of radius $1-\varepsilon $ contains at most $O(1/\varepsilon)$ codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance. [ABSTRACT FROM AUTHOR]

With the development of various information and communication technologies, the amount of big data has increased, and distributed file systems have emerged to store them stably. The replication technique divides the original data into blocks and writes them on multiple servers for redundancy and fault tolerance. However, there is a symmetrical space efficiency problem that arises from the need to store blocks larger than the original data. When storing data, the Erasure Coding (EC) technique generates parity blocks through encoding calculations and writes them separately on each server for fault tolerance and data recovery purposes. Even if a specific server fails, original data can still be recovered through decoding calculations using the parity blocks stored on the remaining servers. However, matrices generated during encoding and decoding are redundantly generated during data writing and recovery, which leads to unnecessary overhead in distributed file systems. This paper proposes a cache-based matrix technique that uploads the matrices generated during encoding and decoding to cache memory and reuses them, rather than generating new matrices each time encoding or decoding occurs. The design of the cache memory applies the Weighting Size and Cost Replacement Policy (WSCRP) algorithm to efficiently upload and reuse matrices to cache memory using parameters known as weights and costs. Furthermore, the cache memory table can be managed efficiently because the weight–cost model sorts and updates matrices using specific parameters, which reduces replacement cost. The experiment utilized the Hadoop Distributed File System (HDFS) as the distributed file system, and the EC volume was composed of Reed–Solomon code with parameters (6, 3). As a result of the experiment, it was possible to reduce the write, read, and recovery times associated with encoding and decoding. In particular, for up to three node failures, systems using WSCRP were able to reduce recovery time by about 30 s compared to regular HDFS systems.

Low-density parity-check (LDPC) codes based on affine permutation matrices, APM-LDPC codes, have been attracted recently, because of some advantages rather than QC-LDPC codes in minimum-distance, cycle distribution and error-rate performance. In this letter, circulant and anti-circulant permutation matrices are used to define a class of LDPC codes, called AQC-LDPC codes, which can be considered as an special case of APM-LDPC codes. In fact, each AQC-LDPC code can be verified by a sign matrix and a slope matrix which are helpful to show each cycle in the Tanner graph by a modular linear equation. For the normal sign matrix $A$ , if −1 $\in A$ , it is shown that the corresponding AQC-LDPC code has maximum-girth 8. Finally, two explicit constructions for AQC-LDPC codes with girths 6, 8 are presented which have some benefits rather than the explicitly constructed QC and APM LDPC codes in minimum-distance, cycle distributions and bit-error-rate performances. [ABSTRACT FROM AUTHOR]

We study the use of Low-Density Parity-Check (LDPC) codes for two-phase, network-coded bidirectional relaying with higher-order modulation. In the multiple-access phase, the sum of transmitted symbols scaled by the channel gains is the received relay constellation, which is network-mapped (clustered) to a transmit constellation for the ensuing broadcast phase. This operation at the relay is termed Clustered-Scaled-Sum (CSS) decoding. We propose a CSS coding scheme for bidirectional relaying using a single LDPC code over a ring with higher-order PAM or QAM alphabets. We design a message-passing decoder for CSS decoding with trade-offs possible between complexity and performance. We suggest a method for completing a Constrained Partially-filled Latin Square (CPLS) to a latin square, which is used in the construction of network maps at the relay for any channel fading state. The performance of the CSS coding scheme with LDPC codes over rings is shown to be very close to information-theoretic outer bounds. [ABSTRACT FROM PUBLISHER]