The subblock energy-constrained codes (SECCs) have recently attracted attention due to various applications in communication systems such as simultaneous energy and information transfer. In a SECC, each codeword is divided into smaller subblocks, and every subblock is constrained to carry sufficient energy. In this work, we study SECCs under more general constraints, namely bounded SECCs and sliding-window constrained codes (SWCCs), and propose two methods to construct such codes with low redundancy and linear-time complexity, based on Knuth’s balancing technique and sequence replacement technique. For certain codes parameters, our methods incur only one redundant bit.
The recursive projection-aggregation (RPA) decoding algorithm for Reed-Muller (RM) codes was recently introduced by Ye and Abbe. We show that the RPA algorithm is closely related to (weighted) belief-propagation (BP) decoding by interpreting it as a message-passing algorithm on a factor graph with redundant code constraints. We use this observation to introduce a novel decoder tailored to high-rate RM codes. The new algorithm relies on puncturing rather than projections and is called recursive puncturing–aggregation (RXA). We also investigate collapsed (i.e., non-recursive) versions of RPA and RXA and show some examples where they achieve similar performance with lower decoding complexity.
Complex codebooks with small inner-product correlation have many applications such as in code-division multiple access communications and compressed sensing. It is desirable but difficult to construct optimal codebooks achieving the well-known Welch bound. In this paper, complex codebooks are investigated from a graph theoretic perspective. A connection between codebooks and Cayley sum graphs is established. Based on this, many infinite families of complex codebooks are explicitly constructed, which are asymptotically optimal with respect to the Welch bound. These constructions not only include some known constructions as special cases but also provide flexible new parameters.
We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders.
Gabidulin codes over fields of characteristic zero were recently constructed by Augot et al., whenever the Galois group of the underlying field extension is cyclic. In parallel, the interest in sparse generator matrices of Reed-Solomon and Gabidulin codes has increased lately, due to applications in distributed computations. In particular, a certain condition pertaining to the intersection of zero entries at different rows, was shown to be necessary and sufficient for the existence of the sparsest possible generator matrix of Gabidulin codes over finite fields. In this paper we complete the picture by showing that the same condition is also necessary and sufficient for Gabidulin codes over fields of characteristic zero. Our proof builds upon and extends tools from the finite-field case, combines them with a variant of the Schwartz-Zippel lemma over automorphisms, and provides a simple randomized construction algorithm whose probability of success can be arbitrarily close to one. In addition, potential applications for low-rank matrix recovery are discussed.
Service rate is an important, recently introduced, performance metric associated with distributed coded storage systems. Among other interpretations, it measures the number of users that can be simultaneously served by the system. We introduce a geometric approach to address this problem. One of the most significant advantages of this approach over the existing ones is that it allows one to derive bounds on the service rate of a code without explicitly knowing the list of all possible recovery sets. To illustrate the power of our geometric approach, we derive upper bounds on the service rates of the first order Reed-Muller codes and the simplex codes. Then, we show how these upper bounds can be achieved. Furthermore, utilizing the proposed geometric technique, we show that given the service rate region of a code, a lower bound on the minimum distance of the code can be obtained.