This manuscript presents a construction method for quantum codes capable of correcting multiple deletion errors. By introducing two new algorithms, the alternating sandwich mapping and the block error locator, the proposed method reduces deletion error correction to erasure error correction. Unlike previous quantum deletion error correcting codes, our approach enables flexible code rates and eliminates the requirement of knowing the number of deletions.

This paper discusses harnessing of pure states in the study of quantum deletion. Quantum deletion is one of the recently prominent aspects in the error model of quantum error correction codes, and pure states represent a class of quantum states widely used in the study of other error models. This study reveals that, under specific encoding and decoding operations, the possibility of deletion error-correction for pure states extends to deletion error-correction for mixed states. Through this paper, it is hoped that the understanding of quantum deletion errors deepens, contributing to the advancement of research in quantum deletion error-correction codes.

A single deletion error correcting code (SDECC) over binary alphabet is a set of fixed-length sequences consisting of two types of symbols, 0 and 1, such that the original sequence can be recovered for at most one deletion error. There is a conjecture “the upper bound for the size of SDECC is equal to the size of Varshamov- Tenengolts (VT) code.” This conjecture had been shown to be true when the code length is ten or less. In this paper, we discuss a method for calculating this upper bound by providing an integer linear programming solver with several linear constraints. As a new result, we obtained that the tight upper bound for the size of a single deletion error correcting code of length 11 is 172. In other words, we could prove that the conjecture is true for the case where the length is 11.

This article contributes to an unsolved quantum information problem: the equivalence between insertion error-correctability and deletion error-correctability. The solution in Shibayama and Ouyang’s sense is provided in the single-error under the assumption of the purity of quantum codeword states On the other hand, a class of codes that can correct both single deletion and single insertion is provided.

Two dimensional (2D) error correcting codes have been investigated for a long time owing to their numerous applications. Recently, 2D codes correcting row-deletions and column-deletions, also known as criss-cross deletion correcting codes, have been studied as a generalisation of one dimensional deletion correcting codes. In this work, we show that 2D deletion correcting codes are useful to correct errors in racetrack memories. With motivation from both theoretical and practical point of view, we study these 2D codes and aim to improve the previous known results. Our first main result is a construction of an optimal (1,1)-criss-cross deletion correcting code with the redundancy is at most$2n+2\log n+o(\log n)$bits. Then, we also present a construction of an asymptotic optimal$(t_{r},\ t_{c})$-criss-cross deletion correcting code with less redundancy than the best known results. Furthermore, since a 2D binary code correcting multiple row-deletions is equivalent to a I1D q-ary code correcting multiple deletions with large$q$, we also improve some previous known results on 1D q-ary code correcting multiple deletions.

This paper presents conditions for constructing permutation-invariant quantum codes for deletion errors and provides a method for constructing them. Our codes include examples of quantum codes that can correct two or more deletion errors, which have not been studied before. We also give examples of quantum codes that can correct both multiple-qubit errors and multiple-deletion errors. We discuss a generalization of the construction of our codes at the end.

This article studies the cardinality of perfect multi deletion binary codes. The lower bound for any perfect deletion code with fixed code length and number of deletions, and the asymptotic achievability of Levenshtein's upper bound are shown.

This paper provides a new instance of quantum deletion error-correcting codes. This code can correct any single quantum deletion error, while our code is only of length 4. This paper also provides an example of an encoding quantum circuit and decoding quantum circuits. It is also proven that the length of any single deletion error-correcting codes is greater than or equal to 4. In other words, our code is optimal for the code length.

This paper introduces descent moment distributions for analysis of single and multi permutation codes defined via Levenshtein (VT) codes. Originally this work is motivated by computer experiments of deletion spheres for contant weight codes and the authors proved properties in a theoretical manner.

Formalization deals with expressing definitions or theorems and proofs at the level of fundamental logic, which allows for automatic verification by computer programs. We report on work done formalizing definitions and theorems in coding theory using the Lean theorem prover, released by Microsoft Research and Carnegie Mellon University in 2015. We formalize fundamental concepts regarding error-correcting codes capable of correcting insertions, deletions, or combinations of insertions and deletions. In particular, we formalize definitions and theorems about subsequences and supersequences, the Levenshtein distance, insertion/deletion spheres, and insertion/deletion codes.

This paper presents a formula for the cardinality of a class of BAD correcting codes proposed at ISIT2017. Furthermore, we show that the cardinality is approximately optimal. In other words, the ratio of the cardinality of the code and that of maximal cardinality BAD correcting code converges to 1 for sufficiently large length.

Two classes of perfect codes for single balanced adjacent deletions (BADs) are provided. These classes are inspired by Levenshtein's work on binary perfect codes for single standard deletions. One of the classes is defined via inversion numbers and the other is defined via Levenshtein codes. The first half of this paper is devoted to the proof of perfectness and the second half is devoted to discussion on the other properties of the provided codes.

Permutation codes, in the form of rank modulation, have shown promise for applications such as flash memory. One of the metrics recently suggested as appropriate for rank modulation is the Ulam metric. Multipermutation codes have also been proposed as a generalization of permutation codes that would improve code size. In this paper we analyze the Ulam metric in the context of multipermutations, noting similarities and differences with the Ulam metric in the context of permutations. We then consider sphere sizes for multipermutations under the Ulam metric and resulting bounds on code size.

Classes of multi insertion/deletion error-correcting codes based on order theory and axiomatic algebra are proposed by an abstraction of Helberg's construction.

Linear constraints for a matrix polytope with no fractional vertex are investigated as intersecting research among permutation codes, rank modulations, and linear programming methods. By focusing the discussion to the block structures of matrices, new classes of such polytopes are obtained from known small polytopes and give ML decodable codes by an LP method. This concept “consolidation” is applied to find a new compact graph which is known as an approach for the graph isomorphism problem. The minimum distances associated with Kendall tau and Euclidean distances of a code obtained by changing the basis of a permutation code may be larger than the original one.

Recent interest on permutation rank modulation shows the Kendall-tau metric as an important distance metric. This note documents our first efforts to obtain upper bounds on optimal code sizes (for said metric) ala Delsarte's approach. For the Hamming metric, Delsarte's seminal work on powerful linear programming (LP) bounds have been extended to permutation codes, via association scheme theory. For the Kendall-tau metric, the same extension needs the more general theory of coherent configurations, whereby the optimal code size problem can be formulated as an extremely huge semidefinite programming (SDP) problem. Inspired by recent algebraic techniques for solving SDP's, we consider the dual problem, and propose an LP to search over a subset of dual feasible solutions. We obtain modest improvement over a recent Singleton bound due to Barg and Mazumdar. We regard this work as a starting point, towards fully exploiting the power of Delsarte's method, which are known to give some of the best bounds in the context of binary codes.

We introduce in this paper the concept of a correctable error set and a fixed initialization decoding, by noticing that the sum-product decoder with a given iteration number only depends on the initialized probability of error, for a BSC. Although this value has been conventionally selected as the BSC crossover probability, we show that other selections can provide better performance or faster convergence. We also prove that for any fixed initialization (i.e., any given correctable error set), the word-error-rate can be represented as a polynomial of the BSC crossover probability. This suggests that the word-error-rate can be analytically derived from the knowledge of the correctable error set.

In this paper, we consider quantum error correction over depolarizing channels with nonbinary low-density parity-check codes defined over Galois field of size 2p. The proposed quantum error correcting codes are based on the binary quasi-cyclic Calderbank, Shor, and Steane (CSS) codes. The resulting quantum codes outperform the best known quantum codes and surpass the performance limit of the bounded distance decoder. By increasing the size of the underlying Galois field, i.e., 2p, the error floors are considerably improved.

A set of linearly constrained permutation matrices are proposed for constructing a class of permutation codes. The main feature of this class of permutation codes, called linear programming (LP)-decodable permutation codes, is this LP decodability. It is demonstrated that the LP decoding performance of the proposed class of permutation codes is characterized by the vertices of the code polytope of the code. Two types of linear constraints are discussed: one is structured constraints and the other is random constraints. The structured constraints allow an efficient encoding algorithm. On the other hand, the random constraints enable us to use probabilistic methods for analyzing several code properties such as the average cardinality and the average weight distribution.

For designing low-density parity-check (LDPC) codes for quantum error-correction, we desire to satisfy the conflicting requirements below simultaneously. 1) The row weights of parity-check “should be large”: The minimum distances are bounded above by the minimum row weights of parity-check matrices of constituent classical codes. Small minimum distance tends to result in poor decoding performance at the error-floor region. 2) The row weights of parity-check matrices “should not be large”: The performance of the sum-product decoding algorithm at the water-fall region is degraded as the row weight increases. Recently, Kudekar et al. showed spatially-coupled (SC) LDPC codes exhibit capacity-achieving performance for classical channels. SC LDPC codes have both large row weight and capacity-achieving error-floor and water-fall performance. In this paper, we propose a new class of quantum LDPC codes based on spatially coupled quasi-cyclic LDPC codes. The performance outperforms that of quantum “non-coupled” quasi-cyclic LDPC codes.

In this paper, we propose a construction method for two-level quantum error-correcting codes via non-binary LDPC codes over an extended field of order 2p, p an integer p >; 1. The proposed quantum error-correcting codes are based on binary quasi-cyclic LDPC codes which have almost achieved a “Bounded Distance Decoding (BDD)” limit but have not surpassed the limit yet. Quantum codes constructed from the proposed method surpass the BDD limit. Furthermore the codes outperform the efficiently-decodable state-of-the-art quantum codes.

A set of linearly constrained permutation matrices are proposed for constructing a class of permutation codes. Making use of linear constraints imposed on the permutation matrices, we can formulate a minimum Euclidian distance decoding problem for the proposed class of permutation codes as a linear programming (LP) problem. The main feature of this novel class of permutation codes, called LP decodable permutation codes, is this LP decodability. It is demonstrated that the LP decoding performance of the proposed class of permutation codes is characterized by the vertices of the code polytope of the code. In addition, based on a probabilistic method, several theoretical results for randomly constrained permutation codes are derived.

In this paper, we introduce the concept of correctable error set for the BSC, which allows to generalize sum-product decoding for this channel. As a result, better error performance or faster convergence can be achieved. Furthermore, the correctable error set allows to evaluate the error performance of generalized sum-product decoding with a given iteration number for the BSC.

While preparing [H. Hagiwara et al., 2006], we realized that the proof of [M. Fossorier, 2004, Theorem 2.3] was leading to confusion as written. More precisely, only e1= o2directly follows from o1+ e1and o2+ e2= e. The other equality o1= e2follows from e1= e2and the fact that the sum of the (distinct) Delta's between the two rows considered has to be zero. Actually, a much concise proof can be obtained by directly observing that for J = p = 2m, {Delta1,2(I) mod p, 0I=0L-1Delta1,2(I) = m mod p ne 0. Since Ruwei Chen recently pointed out this issue, we decided to clarify this point.

We give a tracing algorithm for 2-secure probabilis- tic fingerprinting codes with the property that it never accuses innocent users when there are up to 2 attackers. Moreover, by using our code and tracing algorithm, innocent users are also unlikely to be accused even if either the number of attackers or attackers' abilities exceed our assumption. Our code is the first example of collusion-secure fingerprinting codes with both of these two properties. Furthermore, our code has shorter length among the preceding 2-secure codes, and possesses further properties desirable in a practical use.

In this paper, a construction of a pair of quasi-cyclic LDPC codes to construct a quantum error-correcting code is proposed. Our construction method is based on algebraic combinatorics and have lots of variations for length, code rate.