At a flash memory, each stored data frame is protected by error correction codes (ECC) such as Bose-Chaudhuri-Hocquenghem (BCH) codes from random errors. Exclusive-OR (XOR) based erasure codes like RAID-5 have also been employed at the flash memory to protect from memory block defects. Conventionally, the ECC and erasure codes are used separately since their target errors are different. Due to recent aggressive technology scaling, additional error correction capability for random errors is required without adding redundancy. We propose an algorithm to improve error correction capability by using XOR parity with a simple counter that counts the number of unreliable bits in the XOR stripe. We also propose to apply Chase decoding to the proposed algorithm. The counter makes it possible to reduce the false correction and execute the efficient Chase decoding. We show that combining the proposed algorithm with Chase decoding can significantly improve the decoding performance.

This paper considers error-correction for information in array design, i.e., two-dimensional design such as QR-codes. The error model is multi deletion/substitution/erasure errors. Code construction for the errors and an application of the code are provided. The decoding technique uses an error-locator for deletion codes.

It is known that quasi-cyclic (QC) codes over the finite field Fq correspond to certain Fq[x]-modules. A QC code C is specified by a generator polynomial matrix G whose rows generate C as an Fq[x]-module. The reversed code of C, denoted by R, is the code obtained by reversing all codewords of C while the dual code of C is denoted by C⊥. We call C reversible, self-orthogonal, and self-dual if R = C, C⊥ ⊇ C, and C⊥ = C, respectively. In this study, for a given C, we find an explicit formula for a generator polynomial matrix of R. A necessary and sufficient condition for C to be reversible is derived from this formula. In addition, we reveal the relations among C, R, and C⊥. Specifically, we give conditions on G corresponding to C⊥ ⊇ R, C⊥ ⊆ R, and C = R = C⊥. As an application, we employ these theoretical results to the construction of QC codes with best parameters. Computer search is used to show that there exist various binary reversible self-orthogonal QC codes that achieve the upper bounds on the minimum distance of linear codes.

A construction method of self-orthogonal and self-dual quasi-cyclic codes is shown which relies on factorization of modulus polynomials for cyclicity in this study. The smaller-size generator polynomial matrices are used instead of the generator matrices as linear codes. An algorithm based on Chinese remainder theorem finds the generator polynomial matrix on the original modulus from the ones constructed on each factor. This method enables us to efficiently construct and search these codes when factoring modulus polynomials into reciprocal polynomials.

This paper presents new encoding and decoding methods for Berlekamp-Preparata convolutional codes (BPCCs) based on tail-biting technique. The proposed scheme can correct a single block of n bit errors relative to a guard space of m error-free blocks while no fractional rate loss is incurred. The proposed tail-biting BPCCs (TBBPCCs) can attain optimal complete burst error correction bound. Therefore, they have the optimal phased-burst-error-correcting capability for convolutional codes. Compared with the previous scheme, the proposed scheme can also improve error correcting capability.

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.

Non-volatile memories are a promising alternative to memory design but data stored in them still may be destructed due to crosstalk and radiation. The data stored in them can be restored by using error-correcting codes but they require extra bits to correct bit errors. One of the largest problems in non-volatile memories is that they consume ten to hundred times more energy than normal memories in bit-writing. It is quite necessary to reduce writing bits. Recently, a REC code (bit-write-reducing and error-correcting code) is proposed for non-volatile memories which can reduce writing bits and has a capability of error correction. The REC code is generated from a linear systematic error-correcting code but it must include the codeword of all 1's, i.e., 11…1. The codeword bit length must be longer in order to satisfy this condition. In this letter, we propose a method to generate a relaxed REC code which is generated from a relaxed error-correcting code, which does not necessarily include the codeword of all 1's and thus its codeword bit length can be shorter. We prove that the maximum flipping bits of the relaxed REC code is still limited theoretically. Experimental results show that the relaxed REC code efficiently reduce the number of writing bits.

Non-volatile memories are paid attention to as a promising alternative to memory design. Data stored in them still may be destructed due to crosstalk and radiation. We can restore the data by using error-correcting codes which require extra bits to correct bit errors. Further, non-volatile memories consume ten to hundred times more energy than normal memories in bit-writing. When we configure them using error-correcting codes, it is quite necessary to reduce writing bits. In this paper, we propose a method to generate a bit-write-reducing code with error-correcting ability. We first pick up an error-correcting code which can correct t-bit errors. We cluster its codeswords and generate a cluster graph satisfying the S-bit flip conditions. We assign a data to be written to each cluster. In other words, we generate one-to-many mapping from each data to the codewords in the cluster. We prove that, if the cluster graph is a complete graph, every data in a memory cell can be re-written into another data by flipping at most S bits keeping error-correcting ability to t bits. We further propose an efficient method to cluster error-correcting codewords. Experimental results show that the bit-write-reducing and error-correcting codes generated by our proposed method efficiently reduce energy consumption. This paper proposes the world-first theoretically near-optimal bit-write-reducing code with error-correcting ability based on the efficient coding theories.

A projective Reed-Muller (PRM) code, obtained by modifying a Reed-Muller code with respect to a projective space, is a doubly extended Reed-Solomon code when the dimension of the related projective space is equal to 1. The minimum distance and the dual code of a PRM code are known, and some decoding examples have been presented for low-dimensional projective spaces. In this study, we construct a decoding algorithm for all PRM codes by dividing a projective space into a union of affine spaces. In addition, we determine the computational complexity and the number of correctable errors of our algorithm. Finally, we compare the codeword error rate of our algorithm with that of the minimum distance decoding.

Data stored in non-volatile memories may be destructed due to crosstalk and radiation but we can restore their data by using error-correcting codes. However, non-volatile memories consume a large amount of energy in writing. How to reduce maximum writing bits even using error-correcting codes is one of the challenges in non-volatile memory design. In this paper, we first propose Doughnut code which is based on state encoding limiting maximum and minimum Hamming distances. After that, we propose a code expansion method, which improves maximum and minimum Hamming distances. When we apply our code expansion method to Doughnut code, we can obtain a code which reduces maximum-flipped bits and has error-correcting ability equal to Hamming code. Experimental results show that the proposed code efficiently reduces the number of maximum-writing bits.

Entangled states play crucial roles in quantum information theory and its applied technologies. In various protocols such as quantum teleportation and quantum key distribution, a good entangled state shared by a pair of distant players is indispensable. In this paper, we numerically examine entanglement sharing protocols using quantum LDPC CSS codes. The sum-product decoding method enables us to detect uncorrectable errors, and thus, two protocols, Detection and Resending (DR) protocol and Non-Detection (ND) protocol are considered. In DR protocol, the players abort the protocol and repeat it if they detect the uncorrectable errors, whereas in ND protocol they do not abort the protocol. We show that DR protocol yields smaller error rate than ND protocol. In addition, it is shown that rather high reliability can be achieved by DR protocol with quantum LDPC CSS codes.

Orthogonal Arrays (OAs) have been playing important roles in the field of experimental design. It has been known that OAs are closely related to error-correcting codes. Therefore, many OAs can be constructed from error-correcting codes. But these OAs are suitable for only cases that equal interaction effects can be assumed, for example, all two-factor interaction effects. Since these cases are rare in experimental design, we cannot say that OAs from error-correcting codes are practical. In this paper, we define OAs with unequal strength. In terms of our terminology, OAs from error-correcting codes are OAs with equal strength. We show that OAs with unequal strength are closer to practical OAs than OAs with equal strength. And we clarify the relation between OAs with unequal strength and unequal error-correcting codes. Finally, we propose some construction methods of OAs with unequal strength from unequal error-correcting codes.

In this paper, an efficient architecture for an adaptive Reed-Solomon decoder is presented, where the block length n and the message length k can be varied from their minimum allowable values up to their selected values. This eliminates the need of inserting zeros before decoding shortened RS codes. And the error-correcting capability t can be changed adaptively to channel state at every codeword block. The decoder allows efficient decoding in both burst mode and continuous mode, and it permits 3-step pipelined processing based on the modified Euclid's algorithm. Each step in decoding is designed to be clocked by a separate clock. Thus, each step can be efficiently pipelined with no help of multiplexing. Also, it makes it possible to employ no additional buffer even when the decoder input and output clocks are different. The adaptive RS decoder over GF(28) having the error-correcting capability of upto 10 has been designed in VHDL, and successfully synthesized in an FPGA chip. It can be used in a wide range of applications because of its versatility.

Near-optimality of subcodes of the cyclic Hamming codes is demonstrated on the binary additive channel whose noise process is the two-state homogeneous Markov chain, which is a model of bursty communication channels.

Recently, Vatan, Roychowdhury and Anantram have presented two types of revised versions of the Calderbank-Shor-Steane code construction, and have also provided an exhaustive procedure for determining bases of quantum error-correcting codes. In this paper, we investigate the revised versions given by Vatan et al., and point out that there is no essential difference between them. In addition, we propose an efficient algorithm for searching for bases of quantum error-correcting codes. The proposed algorithm is based on some fundamental properties of classical linear codes, and has much lower complexity than Vatan et al.'s procedure.

In this paper we propose a class of byte-error-correcting codes derived from algebraic curves which is a generalization on the Reed-Solomon codes, and present their fast parallel decoding algorithm. Our algorithm can correct up to (m + b -θ)/2b byte-errors for the byte length b, where m + b -θ + 1dG for the Goppa designed distance dG. This decoding algorithm can be parallelized. In this algorithm, for our code over the finite field GF (q), the total complexity for finding byte-error locations is O (bt(t + q - 1)) with time complexity O (t(t + q - 1)) and space complexity O(b), and the total complexity for finding error values is O (bt(b + q - 1)) with time complexity O (b(b + q - 1)) and space complexity O (t), where t(m + b -θ)/2b. Our byte-error-correcting algorithm is superior to the conventional fast decoding algorithm for randomerrors in regard to the number of correcting byte-errors in several cases.

The aliasing probability was analyzed for MISRs when the error probability for each input was different. A closed form expression was derived by applying the complete weight distributions of linear codes over a Galois field and its dual codes. The aliasing probability for MISRs characterized by non-primitive polynomials was also analyzed. The inner product for binary representation of symbols was used instead of multiplication over a Galois field. The results show the perfect expression for analyzing the aliasing probability of MISRs.

A soft-decision decoding algorithm for binary linear block codes is proposed. This algorithm seeks to minimize the block error probability. With careful examinations of the first hard-decision decoded results, the candidate codewords are efficiently searched for. Thus, we can reduce the decoding complexity (the number of hard-decision decodings) and lower the block error probability. Computer simulation results are presented for the (23, 12) Golay code. They show that the decoding complexity is considerably reduced and the block error probability is close to that of the maximum likelihood decoder.

As RAMs become dense, their reliability reduces because of complex interactions between memory cells and soft errors due to alpha particle radiations. In order to rectify this problem, RAM manufacturers have started incorporating on-chip (built-in) ECC. In order to minimize the area overhead of on-chip ECC, the same technology is used for implementing the check bits and the information bits. Thus the check bits are exposed to the same failure modes as the information bits. Furthermore, faults in the check bits will manifest as uncorrectable multiple errors when a soft error occurs. Therefore it is important to test the check bits for all failure modes expected of other cells. In this paper, we formulate the problem of testing RAMs with on-chip ECC capability. We than derive necessary and sufficient conditions for testing the check bits for arbitrary and adjacent neighborhood pattern sensitive faults. We also provide an efficient solution to test a memory array of N bits (including check bits) for 5-cell neighborhood pattern sensitive faults in O (N) reads and writes, with the check bits also tested for the same fault classes as the information bits.

Although individual segments of a natural language such as words have different importance on human interpretation of the meaning, every segment has been uniformly protected by an error-correcting code. If the importance of individual segments is defined by considering their meaning in the sentence, we can adaptively control the level of error-protection for each segment according to its importance in order to reduce errors on human interpretation of the meaning. In this paper, we propose an error-control scheme based on the varying importance of each word. We first introduce a method which determines the importance of each word and then propose an error-control scheme in which several error-correcting codes are alternately used to protect each word according to its importance. Probablity of semantic errors, that is, errors on human interpretation of the meaning, is defined and used as a criterion in mapping error-correcting codes to words possessing different importance. We theoretically formalize the problem of obtaining an optimum mapping which minimizes the probability of semantic errors under some constraint. Given a certain probability distribution of the importance of words and set of error-correcting codes, we can derive the optimum mapping. The proposed error-controlling scheme is theoretically evaluated by comparing its probability of semantic errors with that of a conventional scheme in which every word is uniformly protected by a single error-correcting code. Results show that the proposed scheme can considerably raduce the probability of semantic errors while retaining the same average transmission rate or redundancy.