In this paper, we assume an error such that a single insertion occurs and then a single deletion occurs. Under such an error model, this paper provides a decoding algorithm for non-binary quantum codes constructed by Matsumoto and Hagiwara.

Research on quantum insertion or deletion error correcting codes has become active in recent years. In 2023, Hagiwara constructed a binary quantum code that corrects multiple deletion errors and has a more flexible code rate than conventional ones. The contribution of this study is to provide an insertion correcting algorithm for the code constructed by Hagiwara.

Streaming codes provide reliable low-latency communication over the packet erasure channels. In the sliding window channel model, the maximum number of erasures and the maximum length of the burst erasure are given for an arbitrary sliding window of a fixed length. This paper presents an explicit construction of a rate-optimal streaming code over small finite fields for the sliding window channels.

The number-theoretic code is a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts’ codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo$r$.

The number-theoretic codes are a class of codes defined by single or multiple congruences and are mainly used for correcting insertion and deletion errors. Since the number-theoretic codes are generally non-linear, the analysis method for such codes is not established enough. The distance enumerator of a code is a unary polynomial whose$i$th coefficient gives the number of the pairs of codewords with distance$i$. The distance enumerator gives the maximum likelihood decoding error probability of the code. This paper presents an identity of the distance enumerators for the number-theoretic codes. Moreover, as an example, we derive the Hamming distance enumerator for the Varshamov-Tenengolts (VT) codes.

This paper investigates the extended weight enumerators for the number-theoretic insertion/deletion correcting codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the Tenengolts’ non-binary codes, which are non-binary codes correcting single insertion/deletion.

A code is bounded single insertion/deletion correcting if a decoder corrects a single insertion or single deletion with side information about a range of positions occurring an inserted symbol or deleted symbol. This paper constructs two bounded single insertion/deletion correcting codes and gives decoding algorithms for these. Moreover, we evaluate the number of codewords of these codes. As a result, the constructed codes have larger cardinalities than the existing ones.

A random access scheme is a fundamental scenario in which users transmit through a shared channel and cannot coordinate with each other. In recent years, successive interference cancellation (SIC) is introduced into the random access scheme. It is possible to decode transmitted packets using collided packets by the SIC. The coded slotted ALOHA (CSA) is a random access scheme using the SIC. The CSA encodes each packet using a local code prior to transmission. It is known that the CSA achieves excellent throughput. On the other hand, it is reported that shift operation improves the decoding performance for packet-oriented erasure correcting coding system. In this paper, we propose a random access scheme which applies the shift operation to the CSA. Numerical examples show that our proposed random access scheme achieves better throughput and packet loss rate than the CSA.

This paper proposes an erasure correcting code and its systematic form for the distributed storage system. The proposed codes are encoded by exclusive OR and bit-level shift operation. By the shift operation, the encoded packets are slightly longer than the source packets. This paper evaluates the extra length of encoded packets, called overhead, and shows that the proposed codes have smaller overheads than the zigzag decodable code, which is an existing code using exclusive OR and bit-level shift operation.

Fountain codes are erasure correcting codes realizing reliable communication systems for the multicast on the Internet. The zigzag decodable fountain (ZDF) code is one of generalization of the Raptor code, i.e, applying shift operation to generate the output packets. The ZDF code is decoded by a two-stage iterative decoding algorithm, which combines the packet-wise peeling algorithm and the bit-wise peeling algorithm. By the bit-wise peeling algorithm and shift operation, ZDF codes outperform Raptor codes under iterative decoding in terms of decoding erasure rates and overheads. However, the bit-wise peeling algorithm spends long decoding time. This paper proposes a fast bit-wise decoding algorithm for the ZDF codes. Simulation results show that the proposed algorithm drastically reduces the decoding time compared with the existing algorithm.

This paper constructs a non-binary code correcting a single b-burst of insertions or deletions with a large cardinality. This paper also proposes a decoding algorithm of this code and evaluates a lower bound of the cardinality of this code. Moreover, we evaluate an asymptotic upper bound on the cardinality of codes which correct a single burst of insertions or deletions.

In the present paper, we derive an upper bound on the average network breakdown probability of packet networks with unreliable relay nodes. We here assume that relay nodes get independently broken with a given node breakdown probability. A survivor graph is the induced subgraph obtained by removing the broken relay nodes and their connecting edges from the original graph. If the survivor network is disconnected, we consider a network breakdown happens. The primal contribution of the paper is to derive an upper bound on the average network breakdown probability, where the expectation is taken over a regular graph ensemble. The proof of the bound is based on a natural one-to-one correspondence between a regular graph and a regular bipartite graph, and also on enumeration of bipartite graphs satisfying certain conditions. This proof argument is inspired by the analysis of weight distribution for low-density parity-check codes. Compared with estimates of the average network breakdown probability obtained by computer experiments, it is observed that the upper bound provides the values which are not only upper bounds but also precise estimates of the network breakdown probability when the node breakdown probability is small.

In this paper, we propose an efficient parallel encoding algorithm for the low-density parity-check (LDPC) codes. The main idea of the proposed encoding algorithm is the block-diagonalization of the parity part of a given parity check matrix by row and column permutation. The numerical examples in this paper show that the proposed encoding algorithm efficiently works in the multi-processor systems.

In this paper, we propose a decoding algorithm which lowers decoding erasure rates in the error floor regions for non-binary low-density parity-check codes transmitted over the binary erasure channels. This decoding algorithm is a combination with belief propagation (BP) decoding and maximum a posteriori (MAP) decoding on zigzag cycles, which cause decoding erasures in the error floor region. We show that MAP decoding on the zigzag cycles is realized by means of a message passing algorithm. A simulation result shows that the decoding erasure rates in the error floor regions by the proposed decoding algorithm are lower than those by the BP decoder.

In this paper, we derive the average weight distributions for the irregular non-binary cluster low-density parity-check (LDPC) code ensembles. Moreover, we give the exponential growth rate of the average weight distribution in the limit of large code length. We show that there exist (2, dc)-regular non-binary cluster LDPC code ensembles whose normalized typical minimum distances are strictly positive.

We study LDPC codes for the channel with 2m-ary input x ϵ F2mand output y = x + z ϵ F2m. The receiver knows a subspace V ⊂ F2mfrom which z = y - x is uniformly chosen. Or equivalently, the receiver receives an affine subspace y-V where x lies. We consider a joint iterative decoder involving the channel detector and the LDPC decoder. The decoding system considered in this paper can be viewed as a simplified model of the joint iterative decoder over non-binary modulated signal inputs e.g., 2m-QAM. We evaluate the performance of binary spatially-coupled MacKay-Neal codes by density evolution. The iterative decoding threshold is seriously degraded by increasing m. EXIT-like function curve calculations reveal that this degradation is caused by wiggles and can be mitigated by increasing the randomized window size. The resultant iterative decoding threshold values are very close to the Shannon limit.

In this paper, we compare the decoding error rates in the error floors for non-binary low-density parity-check (LDPC) codes over the general linear group with those for non-binary LDPC codes over finite field transmitted over the q-ary memoryless symmetric channel under belief propagation decoding. To analyze non-binary LDPC codes defined over both general linear group GL(m, F2) and finite field F2m, we investigate non-binary LDPC codes defined over GL(m3, F2m4). We propose a method to lower the error floors for non-binary LDPC codes. In this analysis, we see that the optimized non-binary LDPC codes defined over general linear group have the same decoding performance in the error floors as those defined over finite field. The non-binary LDPC codes defined over general linear group have more choices of the labels in the edges which satisfy the condition for the optimization.

The scaling law developed by Amraoui et al. is a powerful technique to estimate the block erasure probabilities of finite- length low-density parity-check (LDPC) codes. Solving a system of differential equations called covariance evolution, one can obtain the scaling parameter. However, the covariance evolution has not been analytically solved. In this paper, we present the analytical solution of the covariance evolution for irregular LDPC code ensembles.

In this paper, we investigate the error floors of non-binary low-density parity-check (LDPC) codes transmitted over the memoryless binary-input output-symmetric (MBIOS) channels. We clarify a necessary and sufficient condition for successful decoding of zigzag cycle codes over the MBIOS channel by the BP decoder. We expurgate non-binary LDPC code ensemble to analyze and to lower the error floor by using the above condition. Finally, we show upper and lower bounds of the error floors of the expurgated LDPC code ensemble over the MBIOS channel.

The fixed points of the belief propagation decoder for non-binary low-density parity-check (LDPC) codes are referred to as stopping constellations. In this paper, we give the stopping constellation distributions for the irregular non-binary LDPC code ensembles defined over the general linear group. Moreover, we derive the exponential growth rate of the average number of the stopping constellation distributions in the limit of large code length.

In this paper, we analyze (2, k)-regular non-binary low-density parity-check codes over the binary erasure channels. We propose a method to improve the error floors by optimizing labels in zigzag cycles in the Tanner graph. We analyze the error floors for codes designed by the proposed optimization method and show that the error floors are decreasing in the size of Galois field.

The covariance evolution is a system of differential equations with respect to the covariance of the number of edges connecting to the nodes of each residual degree. Solving the covariance evolution, we can derive distributions of the number of check nodes of residual degree 1, which helps us to estimate the block error probability for finite-length LDPC code. Amraoui et al. resorted to numerical computations to solve the covariance evolution. In this paper, we give the analytical solution of the covariance evolution.

Luby et al. derived evolution of degree distributions in residual graphs for irregular LDPC code ensembles. Evolution of degree distributions in residual graphs is an important characteristic which is used for finite-length analysis of the expected block and bit error probabilities over the binary erasure channel. In this paper, we derive detailed evolution of degree distributions in residual graphs for irregular LDPC code ensembles with joint degree distributions.