Low-density parity-check (LDPC) codes can be used to improve the storage reliability of multi-level cell (MLC) flash memories because of their strong error-correcting capability. In order to improve the weighted bit-flipping (WBF) decoding of LDPC codes in MLC flash memories with cell-to-cell interference (CCI), we propose two strategies of normalizing weights and adjusting log-likelihood ratio (LLR) values. Simulation results show that the WBF decoding under the proposed strategies is much advantageous in both error and convergence performances over existing WBF decoding algorithms. Based on complexity analysis, the strategies provide the WBF decoding with a good tradeoff between performance and complexity.

In this letter, we investigate the separating redundancy of binary linear codes. Using analytical techniques, we provide a general lower bound on the first separating redundancy of binary linear codes and show the bound is tight for a particular family of binary linear codes, i.e., cycle codes. In other words, the first separating redundancy of cycle codes can be determined. We also derive a deterministic and constructive upper bound on the second separating redundancy of cycle codes, which is shown to be better than the general deterministic and constructive upper bounds for the codes.

Using linear programming (LP) decoding based on alternating direction method of multipliers (ADMM) for low-density parity-check (LDPC) codes shows lower complexity than the original LP decoding. However, the development of the ADMM-LP decoding algorithm could still be limited by the computational complexity of Euclidean projections onto parity check polytope. In this paper, we proposed a bisection method iterative algorithm (BMIA) for projection onto parity check polytope avoiding sorting operation and the complexity is linear. In addition, the convergence of the proposed algorithm is more than three times as fast as the existing algorithm, which can even be 10 times in the case of high input dimension.

In this paper, we consider a wide family of λ-quasi-twisted (λ-QT) codes of index 2 and provide a bound on the minimum Hamming distance. Moreover, we give a sufficient condition for dual containing with respect to Hermitian inner product of these involved codes. As an application, some good stabilizer quantum codes over small finite fields F2 or F3 are obtained from the class of λ-QT codes.

The Gabidulin-based locally repairable code (LRC) construction by Silberstein et al. is an important example of distance optimal (r,δ)-LRCs. Its distance optimality has been further shown to cover the case of multiple (r,δ)-locality, where the (r,δ)-locality constraints are different among different symbols. However, the optimality only holds under the ordered (r,δ) condition, where the parameters of the multiple (r,δ)-locality satisfy a specific ordering condition. In this letter, we show that Gabidulin-based LRCs are still distance optimal even without the ordered (r,δ) condition.

The symbol flipping decoding algorithms based on prediction (SFDP) for non-binary LDPC codes perform well in terms of error performances but converge slowly when compared to other symbol flipping decoding algorithms. In order to improve the convergence rate, we design new flipping rules with two phases for the SFDP algorithms. In the first phase, two or more symbols are flipped at each iteration to allow a quick increase of the objective function. While in the second phase, only one symbol is flipped to avoid the oscillation of the decoder when the objective function is close to its maximum. Simulation results show that the SFDP algorithms with the proposed flipping rules can reduce the average number of iterations significantly, whereas having similar performances when compared to the original SFDP algorithms.

A high-rate coding scheme that polar codes are concatenated with low density generator matrix (LDGM) codes is proposed in this paper. The scheme, referred to as polar-LDGM (PLG) codes, can boost the convergence speed of polar codes and eliminate the error floor behavior of LDGM codes significantly, while retaining the low encoding and decoding complexity. With a sensibly designed Gaussian approximation (GA), we can accurately predict the theoretical performance of PLG codes. The numerical results show that PLG codes have the potential to approach the capacity limit and avoid error floors effectively. Moreover, the encoding complexity is lower than the existing LDPC coded system. This motives the application of powerful PLG codes to satellite communications in which message transmission must be extremely reliable. Therefore, an adaptive relaying protocol (ARP) based on PLG codes for the relay satellite system is proposed. In ARP, the relay transmission is selectively switched to match the channel conditions, which are determined by an error detector. If no errors are detected, the relay satellite in cooperation with the source satellite only needs to forward a portion of the decoded message to the destination satellite. It is proved that the proposed scheme can remarkably improve the error probability performance. Simulation results illustrate the advantages of the proposed scheme

The central limit theorem (CLT) claims that the standardized sum of a random sequence converges in distribution to a normal random variable as the length tends to infinity. We prove the existence of a family of counterexamples to the CLT for d-tuplewise independent sequences of length n for all d=2,...,n-1. The proof is based on [n, k, d+1] binary linear codes. Our result implies that d-tuplewise independence is too weak to justify the CLT, even if the size d grows linearly in length n.

Quasi cyclic LDPC (QC-LDPC) codes consisting of circulant permutation matrices (CPM-QC-LDPC) are one of the most attractive types of LDPC codes due to their many advantages. In this paper, we mainly do some research on CPM-QC-LDPC codes. We first propose a two-stage decoding scheme mainly based on parity check matrix transform (MT), which can efficiently improve the bit error rate performance. To optimize the tradeoff between hardware implementation complexity and decoding performance, an improved method that combines our proposed MT scheme with the existing CPM-RID decoding scheme is presented. An experiment shows that both schemes can improve the bit error rate (BER) performance. Finally, we show that the MT decoding mechanism can be applied to other types of LDPC codes. We apply the MT scheme to random LDPC codes and show that it can efficiently lower the error floor.

We propose a recursive algorithm to reduce the computational complexity of the r-order nonlinearity of n-variable Boolean functions. Applying the algorithm and using the sufficient and necessary condition put forward by [1] to cut the vast majority of useless search branches, we show that the covering radius of the Reed-Muller Code R(3, 7) in R(5, 7) is 20.

The separating redundancy is an important property in the analysis of the error-and-erasure decoding of a linear block code. In this work, we investigate the separating redundancy of the duals of first-order generalized Reed-Muller (GRM) codes, a class of nonbinary linear block codes that have nice algebraic properties. The dual of a first-order GRM code can be specified by two positive integers m and q and denoted by R(m,q), where q is the power of a prime number and q≠2. We determine the first separating redundancy value of R(m,q) for any m and q. We also determine the second separating redundancy values of R(m,q) for any q and m=1 and 2. For m≥3, we set up a binary integer linear programming problem, the optimum of which gives a lower bound on the second separating redundancy of R(m,q).

Maximal designed distances for nonbinary narrow-sense quantum Bose-Chaudhuri-Hocquenghem (BCH) codes of length $n=rac{q^4-1}{r}$ and new constructions for them are given, where q is an odd prime power. These constructions are capable of designing quantum BCH codes with new parameters. Furthermore, some codes obtained here have better parameters than those constructed by other known constructions.

Performance of network coded cooperation over the Gaussian channel in which multiple communication nodes send each one's message to a common destination is analyzed. The nodes first broadcast the message, and subsequently relay the XOR of subset of decoded messages to the destination. The received vector at the destination can be equivalently regarded as the output of a point-to-point channel, except that the underlying codes are drawn probabilistically and symbol errors may occur before transmission of a codeword. We analyze the error performance of this system from coding theoretic viewpoint.

Locally repairable codes, which can repair erased symbols from other symbols, have attracted a good deal of attention in recent years because its local repair property is effective on distributed storage systems. (ru, δu)u∈[s]-locally repairable codes with multiple localities, which are an extension of ordinary locally repairable codes, can repair δu-1 erased symbols simultaneously from a set consisting of at most ru symbols. An upper bound on the minimum distance of these codes and a construction method of optimal codes, attaining this bound with equality, were given by Chen, Hao, and Xia. In this paper, we discuss the parameter restrictions of the existing construction, and we propose explicit constructions of optimal codes with multiple localities with relaxed restrictions based on the encoding polynomial introduced by Tamo and Barg. The proposed construction can design a code whose minimum distance is unrealizable by the existing construction.

In this paper, we investigate how to obtain binary locally repairable codes (LRCs) with good locality and availability from binary Simplex codes. We first propose a Combination code having the generator matrix with all the columns of positive weights less than or equal to a given value. Such a code can be also obtained by puncturing all the columns of weights larger than a given value from a binary Simplex Code. We call by block-puncturing such puncturing method. Furthermore, we suggest a heuristic puncturing method, called subblock-puncturing, that punctures a few more columns of the largest weight from the Combination code. We determine the minimum distance, locality, availability, joint information locality, joint information availability of Combination codes in closed-form. We also demonstrate the optimality of the proposed codes with certain choices of parameters in terms of some well-known bounds.

Several types of capacitive crosstalk avoidance codes have been devised in order to prevent capacitive crosstalk in on-chip buses. These codes are designed to prohibit transition patterns prone to capacitive crosstalk from any two consecutive words transmitted to on-chip buses. The present paper provides a rigorous analysis of the asymptotic rate for (p,q)-transition free word sequences under the assumption that coding is based on a stateful encoder and a stateless decoder. Here, p and q represent k-bit transition patterns that should not appear in any two consecutive words at the same adjacent k-bit positions. The maximum rate for the sequences is proven to be equal to the subgraph domatic number of the (p,q)-transition free graph. Based on the theoretical results for the subgraph domatic partition problem, lower and upper bounds on the asymptotic rate are derived. We also show that the asymptotic rate 0.8325 is achievable for p=01 and q=10 transition free word sequences.

Spatially “Mt. Fuji” coupled (SFC) low density parity check (LDPC) codes are constructed as a chain of block LDPC codes. A difference between the SFC-LDPC codes and the original spatially coupled (SC) LDPC codes is code lengths of the underlying block LDPC codes. The code length of the block LDPC code at the middle of the chain is larger than that at the end of the chain. It is experimentally confirmed that the bit error probability in the error floor region of the SFC-LDPC code is lower than that of the SC-LDPC code whose code length and design rate are the same as those of the SFC-LDPC code. In this letter, we calculate the weight distribution of the SFC-LDPC code and try to explain causes of the low bit error rates of the SFC-LDPC code.

Integer codes are defined by error-correcting codes over integers modulo a fixed positive integer. In this paper, we show that the construction of integer codes can be reduced into the cases of prime-power moduli. We can efficiently search integer codes with small prime-power moduli and can construct target integer codes with a large composite-number modulus. Moreover, we also show that this prime-factorization reduction is useful for the construction of self-orthogonal and self-dual integer codes, i.e., these properties in the prime-power moduli are preserved in the composite-number modulus. Numerical examples of integer codes and generator matrices demonstrate these facts and processes.

Recently, IoT compatible products have been popular, and various kinds of things are IoT compliant products. In these devices, cryptosystems and authentication are not treated properly, and security measures for IoT devices are not sufficient. Requirements of authentication for IoT devices are power saving and one-to-many communication. In this paper, we propose a zero-knowledge identification scheme using LDPC codes. In the proposed scheme, the zero-knowledge identification scheme that relies on the binary syndrome decoding problem is improved and the computational cost of identification is reduced by using the sparse parity-check matrix of the LDPC codes. In addition, the security level, computational cost and safety of the proposed scheme are discussed in detail.

In this paper, we study self-dual cyclic codes of length n over the ring R=Z4[u]/, where n is an odd positive integer. We define a new Gray map φ from R to Z42. It is a bijective map and maintains the self-duality. Furthermore, we give the structures of the generators of cyclic codes and self-dual cyclic codes of odd length n over the ring R. As an application, some self-dual codes of length 2n over Z4 are obtained.