Search

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

This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of $n \times n$ arrays affected by ${t}$ -criss-cross deletions defined as any combination of ${t_{\mathrm {r}}}$ row and ${t_{\mathrm {c}}}$ column deletions such that ${t_{\mathrm {r}}}+ {t_{\mathrm {c}}}= {t}$ for a given $t$. We show an equivalence between correcting ${t}$ -criss-cross deletions and ${t}$ -criss-cross insertions and show that a code correcting ${t}$ -criss-cross insertions/deletions has redundancy at least ${t} n + {t}\log n - \log ({t}!)$. Then, we present an existential construction of a ${t}$ -criss-cross insertion/deletion correcting code with redundancy bounded from above by ${t} n + \mathcal {O}({t}^{2} \log ^{2} n)$. The main ingredients of the presented code construction are systematic binary ${t}$ -deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient. [ABSTRACT FROM AUTHOR]

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]

In this paper, we analyze the high-SNR regime of the $M\times K$ Network MISO channel in which each transmitter has access to a different channel estimate, possibly with different precision. It has been recently shown that, for some regimes, this setting attains the same Degrees-of-Freedom as the ideal centralized setting with perfect Channel State Information (CSI) sharing, in which all the transmitters are endowed with the best estimate available at any transmitter. This result is restricted by the limitations of the Degrees-of-Freedom metric, as it only provides information about the slope of growth of the capacity as a function of the SNR, without any insight about the possible performance at a given SNR. In order to overcome this limitation, we analyze the affine approximation of the rate on the high-SNR regime for this decentralized Network MISO setting for the antenna configurations in which it achieves the Degrees-of-Freedom of the centralized setting. We show that, for a regime of antenna configurations, it is possible to asymptotically attain the same achievable rate as in the ideal centralized scenario. Consequently, it is possible to achieve the beamforming gain of the ideal perfect-CSI-sharing setting even if only a subset of transmitters is endowed with precise CSI, which can be exploited in scenarios such as distributed massive MIMO where the number of transmit antennas is much bigger than the number of served users. This outcome is a consequence of the synergistic compromise between CSI precision at the transmitters and consistency between the locally-computed precoders, which is an inherent trade-off of decentralized settings that does not exist in the centralized CSI configuration. We propose a precoding scheme achieving the previous result, which is built on an uneven structure in which some transmitters reduce the precision of their own precoding vector for the sake of using transmission parameters that can be more easily predicted by the other transmitters. [ABSTRACT FROM AUTHOR]

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may either fail to return a codeword or miscorrect to an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of error matrices decodable by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known. [ABSTRACT FROM AUTHOR]

Already in the 1960s, Levenshtein and others studied error-correcting codes that protect against synchronization errors, such as symbol insertions and deletions. However, despite significant efforts, progress on designing such codes has been lagging until recently, particularly compared to the detailed understanding of error-correcting codes for symbol substitution or erasure errors. This paper surveys the recent progress in designing efficient error-correcting codes over finite alphabets that can correct a constant fraction of worst-case insertions and deletions. Most state-of-the-art results for such codes rely on synchronization strings, simple yet powerful pseudo-random objects that have proven to be very effective solutions for coping with synchronization errors in various settings. This survey also includes an overview of what is known about synchronization strings and discusses communication settings related to error-correcting codes in which synchronization strings have been applied. [ABSTRACT FROM AUTHOR]

Whereas the design and properties of bent and plateaued functions have been frequently addressed during the past few decades, there are only a few design methods of the so-called five-valued spectra Boolean functions whose Walsh spectra take the values in $\{0, \pm 2^{\lambda _{1}}, \pm 2^{\lambda _{2}}\}$. Moreover, these design methods mainly regard the specification of these functions in their algebraic normal form (ANF) domain. In this paper, we give a precise characterization of this class of functions in their spectral domain using the concept of a dual of plateaued functions. Both necessary and sufficient conditions on the Walsh support of these functions are given, which then connects their design (in the spectral domain) to a family of the so-called totally (non-overlap) disjoint spectra plateaued functions. We identify some suitable families of plateaued functions having this property, thus providing some generic methods in the spectral domain. Furthermore, we also provide an extensive analysis of their constructions in the ANF domain and provide several generic design methods. The importance of this class of functions is manifolded, where apart from being suitable for some cryptographic applications, we emphasize their property of being constituent functions in the so-called four-bent decomposition. [ABSTRACT FROM AUTHOR]

In 1959, Rényi proposed the information dimension and the $d$ -dimensional entropy to measure the information content of general random variables. This paper proposes a generalization of information dimension to stochastic processes by defining the information dimension rate as the entropy rate of the uniformly quantized stochastic process divided by minus the logarithm of the quantizer step size $1/m$ in the limit as $m\to \infty $. It is demonstrated that the information dimension rate coincides with the rate-distortion dimension, defined as twice the rate-distortion function $R(D)$ of the stochastic process divided by $-\log (D)$ in the limit as $D\downarrow 0$. It is further shown that among all multivariate stationary processes with a given (matrix-valued) spectral distribution function (SDF), the Gaussian process has the largest information dimension rate and the information dimension rate of multivariate stationary Gaussian processes is given by the average rank of the derivative of the SDF. The presented results reveal that the fundamental limits of almost zero-distortion recovery via compressible signal pursuit and almost lossless analog compression are different in general. [ABSTRACT FROM AUTHOR]