We study complementary dual Fq-linear codes defined over an extension field Fqm, which we refer to as additive complementary dual (ACD) codes. We first consider duality of this class of codes with ...respect to a general inner product on Fqmn, which covers the commonly studied cases such as the trace-Euclidean and Hermitian inner products. In general this inner product is not necessarily symmetric, hence we define the notions of left/right hulls and left/right duals of an additive code. This leads to one-sided ACD codes, for which we prove a characterization result in terms of the generator matrix, extending the analogous characterization of Massey for linear complementary dual (LCD) codes. Then we focus on constructions and parameters of ACD codes with respect to trace-Euclidean, Hermitian and Galois inner products. We prove how LCD codes yield ACD codes relative to inner products considered in this work, make some observations on MDS subclass of ACD codes and present a construction of an ACD code by expanding another ACD code. We provide extensive computational results and tables on ACD codes over F4,F8 and F9. Our computations yield many MDS ACD codes and also examples of ACD codes, which have more codewords than the comparable LCD codes with the same length and minimum distance.
Racetrack memory (RM), a highly dense and high-speed spintronic non-volatile memory (NVM) technology, has the potential to revolutionize data storage. However, its reliability is often compromised by ...shift errors that occur during data transfer. To mitigate these errors, system architects often employ error-correcting codes (ECCs) such as single-error correction and double-error detection (SECDED) codes. However, these codes have very limited capabilities when it comes to dealing with double errors, leaving room for improvement in error correction capabilities. In this article, we introduce an enhanced positional SECDED (EP-SECDED) that significantly improves the double-error correction capabilities. Our simulation results demonstrate a two-deletion correction percentage of 19.1% for a 26-bit message, which is a <inline-formula> <tex-math notation="LaTeX">3.3\times </tex-math></inline-formula> improvement over the current state-of-the-art SECDED code. Importantly, our scheme does not incur any additional hardware complexity or cost in terms of redundancy. EP-SECDED offers a low-cost solution for improving the reliability of RM.
In this paper, we are interested in monomial codes with associated vector $a=(a_0, a_1,\ldots, a_{n-1}),$ introduced in \cite{Maria2017}, and more generally in linear codes invariant under a monomial ...matrix $M=\diag(a_0, a_1,\ldots, a_{n-1}) P_{\sigma}$ where $\sigma$ is a permutation and $P_{\sigma}$ its associated permutation matrix.We discuss some connections between monomial codes and codes invariant under an arbitrary monomial matrix $M$. Next, we identify monomial codes with associated vector $a=(a_0,a_2,\ldots, a_{n-1})$ by the ideals of the polynomial ring $ R_{_{q,n}}:= \quot{{\Fqx}}{{\langle x^{n}-\prod_{i=0}^{n-1}a_i \rangle}},$ via a special isomorphism $\varphi_{_{\overline{a}}}$ which preserves the Hamming weight and differs from the classical isomorphism used in the case of cyclic codes and their generalizations. This correspondence leads to some basic characterizations of monomial codes such as generator polynomials, parity check polynomials, and others. Next, we focus on the structure of $\ell-$quasi-monomial ( $\ell-$QM) codes of length $n=m\ell,$ where on the one hand, we characterize them by the $ R_{_{q,m}}-$submodules of $ R_{_{q,m}}^{\ell}.$ On the other hand, $\ell-$QM codes are seen as additive monomial codes over the extension $\mathbb{F}_{q^{\ell}}/\Fq.$ So, as in the case of quasi-cyclic codes \cite{Guneri2018}, we characterize those codes that have $\mathbb{F}_{q^{\ell}}-$linear images with respect to a basis of the extension $ \mathbb{F}_{q^{\ell}}/\Fq,$ based on the CRT decomposition. Finally, we show that $\ell-$QM codes and additive monomial codes are asymptotically good.
We study application of convolutional codes to the randomized encoding scheme introduced by Wyner as a way of confusing the eavesdropper over a wiretap channel. We describe optimal and practical ...sub-optimal decoders for the main and the eavesdropper's channels, and estimate the security gap, which is used as the main metric. The sub-optimal decoder works based on the trellis of the code generated by a convolutional code and its dual, where one encodes the data bits and the other encodes the random bits. By developing a code design metric, we describe how these two generators should be selected for optimal performance over a Gaussian wiretap channel. We also propose application of serially concatenated convolutional codes to this setup so as to reduce the resulting security gaps. Furthermore, we provide an analytical characterization of the system performance by extending existing lower and upper bounds for coded systems to the current randomized convolutional coding scenario. We illustrate our findings via extensive simulations and numerical examples, which show that the newly proposed coding scheme can outperform the other existing methods in the literature in terms of security gap.
We propose a decoding algorithm for a class of convolutional codes called skew Reed-Solomon convolutional codes. These are convolutional codes of designed Hamming distance endowed with a cyclic ...structure yielding a left ideal of a non-commutative ring (a quotient of a skew polynomial ring). In this setting, right and left division algorithms exist, so our algorithm follows the guidelines of the Sugiyama's procedure for finding the error locator and error evaluator polynomials for Goppa block codes.
Coding theory package for Macaulay2 Ball, Taylor; Camps, Eduardo; Chimal-Dzul, Henry ...
The journal of software for algebra and geometry,
12/2021, Volume:
11, Issue:
1
Journal Article
Recent work by Divsalar has shown that properly designed protograph-based low-density parity-check codes typically have minimum (Hamming) distance linearly increasing with block length. This fact ...rests on ensemble arguments over all possible expansions of the base protograph. However, when implementation complexity is considered, the expansions are frequently selected from a smaller class of structured expansions. For example, protograph expansion by cyclically shifting connections generates a quasi-cyclic (QC) code. Other recent work by Smarandache and Vontobel has provided upper bounds on the minimum distance of QC codes. In this paper, we generalize these bounds to punctured QC codes and then show how to tighten these for certain classes of codes. We then evaluate these upper bounds for the family of protograph codes known as AR4JA codes that have been recommended for use in deep space communications in a standard established by the Consultative Committee for Space Data Systems. At block lengths larger than 4400 bits, these upper bounds fall well below the ensemble lower bounds.
We introduce the spanning tree matching (STM) decoder for surface codes, which guarantees the error correction capability up to the code's designed distance by first employing an instance of the ...minimum spanning tree on a subset of ancilla qubits within the lattice. Then, a perfect matching graph is simply obtained, by selecting the edges more likely to be faulty. A comparative analysis reveals that the STM decoder, at the cost of a slight performance degradation, provides a substantial advantage in decoding time compared to the minimum weight perfect matching (MWPM) decoder. Finally, we propose an even more simplified and faster algorithm, the Rapid-Fire (RFire) decoder, designed for scenarios where decoding speed is a critical requirement.
This article studies skew generalized quasi-cyclic codes (SGQC-codes) over finite fields for any length n. We derive generator polynomials and cardinality of SGQC codes. Moreover, we show that the ...dual of any length SGQC-code is also an SGQC-code. Our search results lead to the construction of fifteen new 2-generator SGQC codes over the finite field F4 with minimum distances exceeding the minimum distances of the previously best known F4-linear codes with comparable parameters.
We analyze a class of high performance, low decoding-data-flow error-correcting codes suitable for high bit-rate optical-fiber communication systems. A spatially coupled split-component ensemble is ...defined, generalizing from the most important codes of this class, staircase codes and braided block codes, and preserving a deterministic partitioning of component-code bits over code blocks. Our analysis focuses on low-complexity iterative algebraic decoding, which, for the binary erasure channel, is equivalent to a generalization of the peeling decoder. Using the differential equation method, we derive a vector recursion that tracks the expected residual graph evolution throughout the decoding process. The threshold of the recursion, for asymptotically long component codes, is found using potential function analysis. We generalize the analysis to mixture ensembles consisting of more than one type of component code. We give an example of a mixture ensemble consisting of two component codes, which has better performance than spatially-coupled split-component ensembles consisting of only one component code. The analysis extends to the binary symmetric channel by assuming miscorrection-free component-code decoding. Simple upper bounds on the number of errors correctable by the ensemble are derived. Finally, we analyze the threshold of spatially coupled split-component ensembles under beyond bounded-distance component decoding.
PDF
