Search

Many emerging multimedia streaming applications involve multiple users communicating under strict latency constraints. In this paper we study streaming codes for a network involving two source nodes, one relay node and a destination node. In this paper’s setting, each source node transmits a stream of messages, through the relay, to a destination, who is required to decode the messages under a strict delay constraint. For the case of a single source node, a class of streaming codes has been proposed by Fong et al., using the concept of delay-spectrum. The current paper presents a novel framework, which constructs streaming codes for a relayed multi-user setting by sequentially constructing the codes for each link. This requires a characterization of the set of all achievable delay spectra for a given rate, blocklength and number of erasures, beyond the specific choice considered by Fong et al. This characterization is presented in the paper for systematic codes. Using this novel framework, the first proposed scheme involves greedily selecting the rate on the link from relay to destination and using properties of the delay-spectrum to find feasible streaming codes that satisfy the required delay constraints. A closed form expression for the achievable rate region is provided, and conditions for when the proposed scheme is optimal are established by a natural outer bound. The second proposed scheme builds upon this approach, but uses a numerical optimization-based approach to improve the achievable rate region over the first scheme. Experimental results show that the proposed schemes achieve significant improvements over baseline schemes based on single-user codes.

In this paper, a security evaluation framework for AND-RX ciphers against rotational-XOR differential cryptanalysis is proposed. This framework first models the structure of all the possible rotational-XOR differential (abbreviated to “RXD”) trails and introduces a method to calculate this structure round by round. Based on this approach, an automatic method is proposed for searching RXD trails. In this method, four strategies are proposed to derive better result and improve the efficiency. Unlike previous automations, the time complexity for this framework can be pre-computed, which is bounded by ${\mathcal{ O}}\left ({{c\cdot n\cdot R^{2}\cdot C_{n}^{n_{1}}} }\right)$ (where $n$ is the block size, $n_{1}$ is the number of active bits for the starting point of automatic method, $R$ is the length of the targeted rounds and $c$ is a fixed constant). Under the given strategies and searching subspaces, the derived RXD trails are guaranteed to be optimal. To prove the correctness and efficiency, this framework is applied to all the ten variants for SIMON and three variants for Simeck. When compared with previous RXD trails, the best improvement is up to three rounds. To validate the correctness of the derived rotational-XOR differential trails, a concrete experiment on Simeck32 is conducted and the experimental result complies with the theoretical analysis. As far as we know, for all the variants of Simeck, current longest distinguishers over all the cryptanalytic methods are obtained in this paper.

Insertion and deletion (insdel for short) codes have recently attracted a lot of attention due to their applications in many interesting fields such as DNA storage, DNA analysis, race-track memory error correction and language processing. The present paper mainly studies limits and constructions of insdel codes. The paper can be divided into two parts. The first part focuses on various bounds, while the second part concentrates on constructions of insdel codes. Although the insdel-metric Singleton bound has been derived before, it is still unknown if there are any nontrivial codes achieving this bound. Our first result shows that any nontrivial insdel codes do not achieve the insdel-metric Singleton bound. The second bound shows that every $[n,k]$ Reed-Solomon code has insdel distance upper bounded by $2n-4k+4$ and it is known in literature that an $[n,k]$ Reed-Solomon code can have insdel distance $2n-4k+4$ as long as the field size is sufficiently large. The third bound shows a trade-off between insdel distance and code alphabet size for codes achieving the Hamming-metric Singleton bound. In the second part of the paper, we first provide a non-explicit construction of nonlinear codes that can approach the insdel-metric Singleton bound arbitrarily when the code alphabet size is sufficiently large. The second construction gives two-dimensional Reed-Solomon codes of length $n$ and insdel distance $2n-4$ with field size $q=O(n^{5})$ . The non-explicit construction of insdel codes is based on constant-weight $L^{1}$ -codes that are introduced in this paper. We first establish a relation between constant-weight $L^{1}$ -codes and insdel codes. Based on this relation, we construct constant-weight $L^{1}$ -codes with reasonable parameters and subsequently give insdel codes approaching the insdel-metric Singleton bound. Via automorphism group of rational function field, we provide a necessary and sufficient condition under which a two-dimensional Reed-Solomon code of length $n$ has insdel distance $2n-4$ . Based on this criterion, we present a construction of $q$ -ary two-dimensional Reed-Solomon codes of length $n$ and insdel distance $2n-4$ with $q=O(n^{5})$ . Though this is worse than the current best field size, we provide a new angle to look into the problem.

This paper considers the problem of estimating the structure of structurally similar graphical models in high dimensions. This problem is pertinent in multi-modal or multi-domain datasets that consist of multiple information domains, each modeled by one probabilistic graphical model (PGM), e.g., in brain network modeling using different neuroimaging modalities. Induced by an underlying shared causal source, the domains, and subsequently their associated PGMs, can have structural similarities. This paper focuses on Gaussian and Ising models and characterizes the information-theoretic sample complexity of estimating the structures of a pair of PGMs in the degree-bounded and edge-bounded subclasses. The PGMs are assumed to have $p$ nodes with distinct and unknown structures. Their similarity is accounted for by assuming that a pre-specified set of $q$ nodes form identical subgraphs in both PGMs. Necessary and sufficient conditions on the sample complexity for a bounded probability of error are characterized. The necessary conditions are information-theoretic (algorithm-independent), delineating the statistical difficulty of the problem. The sufficient conditions are based on deploying maximum likelihood decoders. While the specifics of the results vary across different subclasses and parameter regimes, one key observation is that in specific subclasses and regimes, the sample complexity varies with $p$ and $q$ according to $\Theta (\log (p-q))$ . For Ising models, a low complexity, online structure estimation (learning) algorithm based on multiplicative weights is also proposed. Numerical evaluations are also included to illustrate the interplay among different parameters on the sample complexity when the structurally similar graphs are recovered by a maximum likelihood-based graph decoder and the proposed online estimation algorithm.

The purpose of this paper is to solve the two conjectures on the largest minimum distance $d_{so}(n,5)$ of a binary self-orthogonal $[n, 5]$ code proposed by Kim and Choi (2022). The determination of $d_{so}(n,k)$ has been a fundamental and difficult problem in coding theory because there are too many binary self-orthogonal codes as the dimension $k$ increases. Recently, Kim et al. (2021) considered the shortest self-orthogonal embedding of a binary linear code, and many binary optimal self-orthogonal $[n,k]$ codes were constructed for $k=4,5$ . Kim and Choi (2022) improved some results of Kim et al. (2021) and made two conjectures on $d_{so}(n,5)$ . In this paper, we develop a general method to determine the exact value of $d_{so}(n,k)$ for $k=5,6$ and show that the two conjectures made by Kim and Choi (2022) are true.

This paper investigates adaptive streaming codes over a three-node relayed network. In this setting, a source node transmits a sequence of message packets to a destination with help of a relay. The source-to-relay and relay-to-destination links are unreliable and introduce at most $N_{1}$ and $N_{2}$ packet erasures, respectively. The destination node must recover each message packet within a strict delay constraint $T$ . The paper presents a new construction of streaming codes for all feasible parameters $\{N_{1}, N_{2}, T\}$ . Our work improves upon the construction in Fong et al. by adapting the relaying strategy based on the erasure patterns from source to relay. Specifically, the code employs the notion of symbol estimates, which allows the relay to forward information about symbols before it can decode that symbol, and variable-rate encoding, which decreases the rate used to encode a packet as more erasures affect that packet. The codes proposed in this paper achieve rates higher than the ones proposed by Fong et al. whenever $N_{2} > N_{1}$ , and achieve the same rate when $N_{2} \leq N_{1}$ , in which case the rate is optimal. The paper also presents an upper bound on the achievable rate that takes into account erasures in both links in order to bound the rate in the second link. The upper bound is shown to be tighter than a trivial bound that considers only the erasures in the second link.

Consider a pair of random vectors $( {\mathbf{X}}, {\mathbf{Y}}) $ and the conditional expectation operator $ \mathbb {E}[ {\mathbf{X}}| {\mathbf{Y}}={\mathbf{y}}]$ . This work studies analytical properties of the conditional expectation by characterizing various derivative identities. The paper consists of two parts. In the first part of the paper, a general derivative identity for the conditional expectation is derived. Specifically, for the Markov chain $ {\mathbf{U}}\leftrightarrow {\mathbf{X}}\leftrightarrow {\mathbf{Y}}$ , a compact expression for the Jacobian matrix of $ \mathbb {E}[ \psi ( {\mathbf{Y}}, {\mathbf{U}})| {\mathbf{Y}}= {\mathbf{y}}]$ for a smooth function $\psi $ is derived. In the second part of the paper, the main identity is specialized to the exponential family and two main applications are shown. First, it is demonstrated that, via various choices of the random vector $ {\mathbf{U}}$ and function $\psi $ , one can recover and generalize several known identities (e.g., Tweedie’s formula) and derive some new ones. For example, a new relationship between conditional expectations and conditional cumulants is established. Second, it is demonstrated how the derivative identities can be used to establish new lower bounds on the estimation error. More specifically, using one of the derivative identities in conjunction with a Poincaré inequality, a new lower bound on the minimum mean squared error, which holds for all prior distributions on the input signal, is derived. The new lower bound is shown to be tight in the high-noise regime for the additive Gaussian noise setting.

Interplay between coding theory and combinatorial $t$ -designs has been a hot topic for many years for combinatorialists and coding theorists. Some infinite families of cyclic codes supporting infinite families of 3-designs have been constructed in the past 50 years. However, no infinite family of negacyclic codes supporting an infinite family of 3-designs has been reported in the literature. This is the main motivation of this paper. Let $q=p^{m}$ , where $p$ is an odd prime and $m \geq 2$ is an integer. The objective of this paper is to present an infinite family of cyclic codes over ${\mathrm {GF}}(q)$ supporting an infinite family of 3-designs and two infinite families of negacyclic codes over ${\mathrm {GF}}(q^{2})$ supporting two infinite families of 3-designs. The parameters and the weight distributions of these codes are determined. The subfield subcodes of these negacyclic codes over ${\mathrm {GF}}(q)$ are studied. Three infinite families of almost MDS codes are also presented. A constacyclic code over ${\mathrm {GF}}(4)$ supporting a 4-design and seven open problems are also presented in this paper.

Gradient-related first-order methods have become the workhorse of large-scale numerical optimization problems. Many of these problems involve nonconvex objective functions with multiple saddle points, which necessitates an understanding of the behavior of discrete trajectories of first-order methods within the geometrical landscape of these functions. This paper concerns convergence of first-order discrete methods to a local minimum of nonconvex optimization problems that comprise strict-saddle points within the geometrical landscape. To this end, it focuses on analysis of discrete gradient trajectories around saddle neighborhoods, derives sufficient conditions under which these trajectories can escape strict-saddle neighborhoods in linear time, explores the contractive and expansive dynamics of these trajectories in neighborhoods of strict-saddle points that are characterized by gradients of moderate magnitude, characterizes the non-curving nature of these trajectories, and highlights the inability of these trajectories to re-enter the neighborhoods around strict-saddle points after exiting them. Based on these insights and analyses, the paper then proposes a simple variant of the vanilla gradient descent algorithm, termed Curvature Conditioned Regularized Gradient Descent (CCRGD) algorithm, which utilizes a check for an initial boundary condition to ensure its trajectories can escape strict-saddle neighborhoods in linear time. Convergence analysis of the CCRGD algorithm, which includes its rate of convergence to a local minimum, is also presented in the paper. Numerical experiments are then provided on a test function as well as a low-rank matrix factorization problem to evaluate the efficacy of the proposed algorithm.

The construction of polar codes with code length $n=2^{m}$ involves $m$ layers of polar transforms. In this paper, we observe that after each layer of polar transforms, one can swap certain pairs of adjacent bits to accelerate the polarization process. More precisely, if the previous bit is more reliable than its next bit under the successive decoder, then switching the decoding order of these two adjacent bits will make the reliable bit even more reliable and the noisy bit even noisier. Based on this observation, we propose a new family of codes called the Adjacent-Bits-Swapped (ABS) polar codes. We add a permutation layer after each polar transform layer in the construction of the ABS polar codes. In order to choose which pairs of adjacent bits to swap in the permutation layers, we rely on a new polar transform that combines two independent channels with 4-ary inputs. This new polar transform allows us to track the evolution of every pair of adjacent bits through different layers of polar transforms, and it also plays an essential role in the successive cancellation list (SCL) decoder for the ABS polar codes. Extensive simulation results show that ABS polar codes consistently outperform standard polar codes by $0.15 \mathop {\mathrm {dB}}\nolimits $ — $0.3 \mathop {\mathrm {dB}}\nolimits $ when we use CRC-aided SCL decoder with list size 32 for both codes. The implementations of all the algorithms in this paper are available at https://github.com/PlumJelly/ABS-Polar

Maximally recoverable local repairable codes (MR LRCs for short) have received great attention in the last few years. Various constructions have been proposed in literature. The main focus of this topic is to construct MR LRCs over small fields. An interesting parameter regime for an $(N=nr,r,h, \delta)$ -MR LRC is the constant global parities $h=O(1)$ . In this parameter setting, all previous constructions require the field size $\ell =\Omega _{h} (N^{h-1-o(1)})$ . It remains challenging to improve this bound. In this paper, via subspace direct sum systems, we present a construction of MR LRC with the field size $\ell = O\left({N^{h-2+\frac {1}{h-1}-o(1)}}\right)$ . In particular, for the interesting cases where $h=2,3$ , we improve previous constructions by either reducing field size or removing constraints. In addition, we also offer some constructions of MR LRCs for larger global parity $h$ . The main techniques used in this paper is through subspace direct sum systems that we introduce.

Recently, much progress has been made to construct minimal linear codes due to their preference in secret sharing schemes and secure two-party computation. In this paper, we put forward a new method to construct minimal linear codes by using vectorial Boolean functions. Firstly, we give a necessary and sufficient condition for a generic class of linear codes from vectorial Boolean functions to be minimal. Based on that, we derive some new three-weight minimal linear codes and determine their weight distributions. Secondly, by studying deeply the construction of linear codes in this paper, we find a necessary and sufficient condition of the linear codes to be minimal and to be violated the AB condition. As a result, we get three infinite families of minimal linear codes violating the AB condition. To the best of our knowledge, this is the first time that minimal liner codes are constructed from vectorial Boolean functions. Compared the parameters with other known ones, in general the minimal liner codes obtained in this paper have higher dimensions.

Laplacian distribution is widely used to model the differences between correlated continuous or nonbinary signals, e.g., the predictive residues of videos. Usually, distributed coding of correlated nonbinary sources, e.g., distributed video coding, is implemented by binary or nonbinary Low-Density Parity-Check (LDPC) codes. In this paper, as an alternative, we attempt using nonbinary Distributed Arithmetic Coding (DAC) to implement distributed coding of uniform nonbinary sources with Laplace-distributed correlation. To analyze $Q$ -ary DAC for uniform $Q$ -ary sources, following the methodology developed in our prior work for binary DAC, we define and deduce Coset Cardinality Spectrum (CCS) from both fixed-length and variable-length perspectives, whose physical meanings are explained in detail; while for binary DAC, our prior work totally ignored the subtle difference between these two perspectives. Compared with binary DAC, an important advantage of nonbinary DAC is that, the mapping from source symbols to coding intervals is so flexible that there are many parameters that can be tuned to achieve better performance; while for binary DAC, there are very few tunable parameters, making it very hard to achieve better performance. This paper proposes a simple method to map source symbols onto coding intervals, which results in a very lightweight codec, while possessing a good Manhattan distance distribution. Then this paper deduces the formula of path metrics for decoder design by making use of CCS. All theoretical analyses are perfectly verified by simulation results. Most important, experimental results show that $Q$ -ary DAC achieves significantly better performance than LDPC codes for distributed coding of uniform $Q$ -ary sources with Laplace-distributed correlation.

Riemannian Gaussian distributions were initially introduced as basic building blocks for learning models which aim to capture the intrinsic structure of statistical populations of positive-definite matrices (here called covariance matrices). While the potential applications of such models have attracted significant attention, a major obstacle still stands in the way of these applications: there seems to exist no practical method of computing the normalising factors associated with Riemannian Gaussian distributions on spaces of high-dimensional covariance matrices. The present paper shows that this missing method comes from an unexpected new connection with random matrix theory. Its main contribution is to prove that Riemannian Gaussian distributions of real, complex, or quaternion covariance matrices are equivalent to orthogonal, unitary, or symplectic log-normal matrix ensembles. This equivalence yields a highly efficient approximation of the normalising factors, in terms of a rather simple analytic expression. The error due to this approximation decreases like the inverse square of dimension. Numerical experiments are conducted which demonstrate how this new approximation can unlock the difficulties which have impeded applications to real-world datasets of high-dimensional covariance matrices. The paper then turns to Riemannian Gaussian distributions of block-Toeplitz covariance matrices. These are equivalent to yet another kind of random matrix ensembles, here called “acosh-normal” ensembles. Orthogonal and unitary “acosh-normal” ensembles correspond to the cases of block-Toeplitz with Toeplitz blocks, and block-Toeplitz (with general blocks) covariance matrices, respectively.

Compute–forward is a coding technique that enables receiver(s) in a network to directly decode one or more linear combinations of the transmitted codewords. Initial efforts focused on Gaussian channels and derived achievable rate regions via nested lattice codes and single-user (lattice) decoding as well as sequential (lattice) decoding. Recently, these results have been generalized to discrete memoryless channels via nested linear codes and joint typicality coding, culminating in a simultaneous-decoding rate region for recovering one or more linear combinations from $K$ users. Using a discretization approach, this paper translates this result into a simultaneous-decoding rate region for a wide class of continuous memoryless channels, including the important special case of Gaussian channels. Additionally, this paper derives a single, unified expression for both discrete and continuous rate regions via an algebraic generalization of Rényi’s information dimension.

This paper is concerned with the problem of frequency estimation from multiple-snapshot data. It is well-known that ESPRIT (and spatial-smoothing ESPRIT in presence of coherent sources or given limited snapshots) can locate the true frequencies if either the number of snapshots or the signal-to-noise ratio (SNR) approaches infinity. In this paper, we analyze the nonasymptotic performance of ESPRIT and spatial-smoothing ESPRIT with finitely many snapshots and finite SNR. We show that the absolute frequency estimation error of ESPRIT (or spatial-smoothing ESPRIT) is bounded from above by $C\frac {\max \left \{{\sigma, \sigma ^{2}}\right \}}{\sqrt {L}}$ with overwhelming probability, where $\sigma ^{2}$ denotes the Gaussian noise variance, $L$ is the number of snapshots and $C$ is a coefficient independent of $L$ and $\sigma ^{2}$ , if and only if the true frequencies can be localized by ESPRIT (or spatial-smoothing ESPRIT) without noise or with infinitely many snapshots. Our results are obtained by deriving new matrix perturbation bounds and generalizing the classical Schur product theorem, which may be of independent interest. Extensions to MUSIC and spatial-smoothing MUSIC are also made. Numerical results are provided corroborating our analysis.

Minimal linear codes have important applications in secure communications, including in the framework of secret sharing schemes and secure multi-party computation. A lot of research have been carried out to derive codes with few weights (but more importantly, being minimal) using algebraic or geometric approaches. One of the main power and fructify algebraic methods is based on the design of those codes by employing functions over finite fields. Li et al. (2021) have recently identified some binary linear codes with few weights from two classes of two-to-one functions. In this paper, our ultimate objective is to expand the class of codes derived from the paper of Li et al. by proposing larger classes of binary linear codes with few weights via generic constructions involving other known families of two-to-one functions over the finite field $\mathbb {F}_{2^{n}}$ of order $2^{n}$ . We succeed in constructing such codes, and we also completely determine their weight distributions. The linear codes presented in this paper differ in parameters from those known in the literature. Besides, some of them are optimal concerning the well-known Griesmer bound. Notably, we prove that our codes are either optimal or almost optimal with respect to the online Database of Grassl. We next observe that the derived binary linear codes also have the minimality property for most cases. We then describe the access structures of the secret-sharing schemes based on their dual codes. Finally, we solve two problems left open in the paper by Li et al. (more specifically, a complete solution to Problem 2 and a partial solution to Problem 1).

Consider a channel $\mathbf {Y}= \mathbf {X}+ \mathbf {N}$ where $\mathbf {X}$ is an $n$ -dimensional random vector, and $\mathbf {N}$ is a multivariate Gaussian vector with a full-rank covariance matrix $\boldsymbol {\mathsf {K}}_{ \mathbf {N}}$ . The object under consideration in this paper is the conditional mean of $\mathbf {X}$ given $\mathbf {Y}={\mathbf{y}}$ , that is ${\mathbf{y}} \mapsto \mathbb {E} [\mathbf {X}| \mathbf {Y}={\mathbf{y}}]$ . Several identities in the literature connect $\mathbb {E}[\mathbf {X}| \mathbf {Y}={\mathbf{y}}]$ to other quantities such as the conditional variance, score functions, and higher-order conditional moments. The objective of this paper is to provide a unifying view of these identities. In the first part of the paper, a general derivative identity for the conditional mean estimator is derived. Specifically, for the Markov chain $\mathbf {U}\leftrightarrow \mathbf {X}\leftrightarrow \mathbf {Y}$ , it is shown that the Jacobian matrix of $\mathbb {E}[\mathbf {U}| \mathbf {Y}={\mathbf{y}}]$ is given by $\boldsymbol {\mathsf {K}}_{ \mathbf {N}}^{-1} \boldsymbol {\mathsf {Cov}} (\mathbf {X}, \mathbf {U}| \mathbf {Y}={\mathbf{y}})$ where $\boldsymbol {\mathsf {Cov}} (\mathbf {X}, \mathbf {U}| \mathbf {Y}={\mathbf{y}})$ is the conditional covariance. In the second part of the paper, via various choices of the random vector $\mathbf {U}$ , the new identity is used to recover and generalize many of the known identities and derive some new identities. First, a simple proof of the Hatsel and Nolte identity for the conditional variance is shown. Second, a simple proof of the recursive identity due to Jaffer is provided. The Jaffer identity is then further explored, and several equivalent statements are derived, such as an identity for the higher-order conditional expectation (i.e., $\mathbb {E}[\mathbf {X}^{k}| \mathbf {Y}]$ ) in terms of the derivatives of the conditional expectation. Third, a new fundamental connection between the conditional cumulants and the conditional expectation is demonstrated. In particular, in the univariate case, it is shown that the $k$ -th derivative of the conditional expectation is proportional to the $(k+1)$ -th conditional cumulant. A similar expression is derived in the multivariate case.

The cross-correlation between two maximum length sequences ( $m$ -sequences) of the same period has been studied since the end of 1960s. One open conjecture by Helleseth states that the cross-correlation between any two $p$ -ary $m$ -sequences takes on the value −1 for at least one shift provided that the decimation $d$ obeys $d\equiv 1\,({\mathrm{ mod}}\, p-1)$ . This was known as the −1 conjecture. Up to now, the −1 conjecture was confirmed for the following decimations: (1) Niho-type decimations, i.e., $d=s(p^{n/{2}}-1)+1$ , where $s$ is an integer; (2) all the complete permutation polynomial (CPP) exponents $d$ satisfying $d\equiv 1\, ({\mathrm{ mod}}\, p-1) $ ; and (3) the additional families of decimations tabulated in this paper. In this paper, we first discuss the connection between the −1 conjecture on cross-correlation of $m$ -sequences and CPP exponents, then we confirm the −1 conjecture for a new type of decimations by giving a new class of CPP exponents. The decimations are of the type $d=1+l{(p^{rtm}-1)}/{(r+1)}$ over ${\mathbb F}_{p^{rtm}}$ , where $p$ is a prime, $r+1$ is an odd prime satisfying $p^{r/{2}} \equiv -1\,({\mathrm{ mod}}\, r+1)$ , $t$ is an odd integer ( $t>2$ if $p=2$ ) with $\gcd (t,r)=1$ , and $m$ is a positive integer. We transform the problem of determining whether $d$ is a CPP exponent into that of investigating the existence of irreducible polynomials over $\mathbb {F}_{p}$ with degree $t$ satisfying a congruence equation. By a theorem given by Rosen that considered the number of irreducible polynomials with a special congruence relation, we prove that $d$ is a CPP exponent over ${\mathbb F}_{p^{rtm}}$ for sufficiently large $t$ . When $m$ is odd, our new CPP exponents are of Niho type; thus, we give a new class of CPP exponents of Niho type. When $m$ is even, we obtain a new class of CPP exponents which are not of Niho type. As a consequence, we show that the −1 conjecture is true for $d=1+l{(p^{rtm}-1)}/{(r+1)}$ when $t$ is a sufficiently large integer.

One pervasive challenge in providing a high quality-of-service for live communication is to recover lost packets in real-time. Streaming codes are a class of erasure codes that are designed for such strict, low-latency streaming communication settings. Motivated by applications that transmit messages whose sizes vary over time, such as live video streaming, this paper considers the setting of streaming codes under variable-size messages. In practice, streaming codes operate in an “online” setting where the sizes of the future messages are unknown. “Offline” codes, in contrast, have access to the sizes of all messages, including future ones. This paper introduces the first online rate-optimal streaming codes for communicating over a burst-only packet loss channel for two broad parameter regimes. These two online codes match the rates of optimal offline codes for the two settings despite the apparent advantage of the offline setting. This paper further establishes that online codes cannot attain the optimal rate for offline codes for all remaining parameter settings.

This paper introduces the partial-inverse problem for linearized polynomials and develops its application to decoding Gabidulin codes and lifted Gabidulin codes in linear random network coding. The proposed approach is a natural generalization of its counterpart for ordinary polynomials, thus providing a unified perspective on Reed–Solomon codes for the Hamming metric and for the rank metric. The basic algorithm for solving the partial-inverse problem is a common parent algorithm of a Berlekamp–Massey algorithm, a Euclidean algorithm, and yet another algorithm, all of which are obtained as easy variations of the basic algorithm. Decoding Gabidulin codes can be reduced to the partial-inverse problem via a key equation with a new converse. This paper also develops new algorithms for interpolating crisscross erasures and for joint decoding of errors, erasures, and deviations in random network coding.

In this paper, we propose an analysis of the automorphism group of polar codes, with the aim of designing codes tailored for automorphism ensemble (AE) decoding. Using a novel description of polar codes as monomial codes through negative monomials, we prove the equivalence between the notion of decreasing monomial codes and the universal partial order (UPO) framework for polar codes; this property is widely believed to hold true but a formal proof was missing. We further provide a rigorous mathematical connection between code word permutations and affine transformations, an important link to understand the considered automorphisms. Based on this mathematical formalisms, we analyze the algebraic properties of the affine automorphisms group of polar codes, providing a novel description of its structure. We classify automorphisms such that all automorphisms in the same class lead to the same result under permutation decoding, which gives rise to the concept of redundant automorphisms. Mathematically this is achieved by introducing equivalence classes of affine automorphisms under AE-based decoding. For practical application, we provide an algorithm to compute representatives for the equivalence classes, such that one automorphism from each equivalence class can be selected for use in AE decoding. A numerical analysis of the error correction performance of AE decoding of polar codes, based on equivalence classes, concludes the paper.