Shibuya Tomoharu

Rank Modulation code is a recoding code expressing information by using the mutual relation between the level of electric charge of each cell constituting a flash memory. Compressed encoding is one of the rank modulation encodings that employ the push up operation to realize a state transition of memory. In this study, we investigate a code constructions based on the dominating set of a transition graph, which is known as one of techniques to inclease the capacity of memory and decrease frequency of the occurrence of the block erasure in the compressed encoding. As a result, we propose a new algorithm to construct a dominating set. Moreover, we show a sufficient condition for the proposed algorithm to generate a minimal dominating set. In addition, we give a concretely an example of minimal dominating set for a memory constituting 5 cells.

Spatially coupled (SC) low-density parity-check (LDPC) codes are denned by bipartite graphs that are obtained by assembling prototype graphs. The combination and connection of prototype graphs are designated by specifying some parameters, and Kudekar et al. showed that BP threshold of the ensemble of SC LDPC codes agrees with MAP threshold of the ensemble of regular LDPC codes when those parameters are grown up so that the code length tends to infinity. When we design SC LDPC codes with practical code length, however, it is not clear how to set those parameters to enhance the performance of SC LDPC codes. In this paper, we provide the result of numerical experiments that suggest the dependence of error performance of SC LDPC codes over BEC on their design parameters.

It is well known that LDPC codes can exhibit excellent performance by iterative decoding with O(n) computational complexity. As for their encoding, however, no algorithm has been developed that can be executed with computation less than O(n^2). Therefore, it has been one of the most important research subject to reduce computational complexity of encoding of LDPC codes. In this paper, we will survey the conventional approaches to reduce computational complexity of encoding of LDPC codes. Then the encoding method of LDPC codes that can be executed with O(n) computation will be introduced.

Efficient algorithms to solve a system of linear equations have been extensively and deeply investigated in a large number of researches. Among them, the block-triangularization is one of the well-know approaches effective for linear systems defined by matrices with particular characteristics, especially by sparse matrices. In this paper, we propose an encoding algorithm that can be applied to arbitrary linear codes over any finite field and executed with complexity O (w(H)) where w(H) denotes the number of non-zero elements of the parity check matrix H under consideration. By giving our attention to the fact that encoding of a linear code is equivalent to solving a system of linear equations, we propose an encoding algorithm based on the block-triangularization of the part of parity check matrices combining rearrangement of subblocks of them. As the result, any linear codes defined by sparse parity check matrices, such as LDPC codes, can be encoded by the proposed algorithm with complexity O(n) where n denotes the code length.

Recently, Haley and Grant introduced the concept of reversible codes - a class of linear codes encodable by the iterative message-passing algorithm based on the Jacobi method over F_2. They also developed a concrete procedure to construct parity check matrices of reversible codes by utilizing some properties of circulant matrices which is described in terms of polynomials over F_2. In this paper, we investigate the size of circulant matrices considered in the Haley's procedure and clarify the necessary and sufficient condition on the size for which reversible codes based on circulant matrices exist. This condition tells us that no reversible codes based on circulant matrices exist other than those constructed by the Haley's procedure.

Recently, Haley and Grant introduced the concept of reversible codes - a class of linear codes encodable by the iterative message-passing algorithm based on the Jacobi method over F_2. They also developed a concrete procedure to construct parity check matrices of reversible codes by utilizing some properties of circulant matrices which is described in terms of polynomials over F_2. In this paper, we investigate the size of circulant matrices considered in the Haley's procedure and clarify the necessary and sufficient condition on the size for which reversible codes based on circulant matrices exist. This condition tells us that no reversible codes based on circulant matrices exist other than those constructed by the Haley's procedure.

Recently, Mooij et al. proposed sufficient conditions for convergence of the sum-product algorithm, which was stated as the upper bound for the spectral radius of a matrix defined by a probability distribution under consideration. In this paper, we adapt Mooij's sufficient conditions to the decoding problem, and derive a sufficient condition for convergence of the sum-product decoding.

Recently, Mooij et al. proposed sufficient conditions for convergence of the sum-product algorithm, which was stated as the upper bound for the spectral radius of a matrix defined by a probability distribution under consideration. In this paper, we adapt Mooij's sufficient conditions to the decoding problem, and derive a sufficient condition for convergence of the sum-product decoding.

Montanari constructed lower bounds on the conditional entropy of the transmitted message using Multi-Poisson ensemble. In case of BEC, this bounds are identical to the conditional entropy of the transmitted message by the analysis of EXIT function by Measson. We will consider the extention of this method to LDPC codes over GF (4).

Multi-edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles have better performance than other known ensembles. Orlitsky et al. derived the condition for irregular LDPC code ensembles with minimum distance linearly increasing in code length. Nakasendo et al. derived the condition that code ensembles have exponentially decreasing small linear weight codewords for two-edge type LDPC code ensembles which is simple example of multi-edge type LDPC code ensembles. In this letter, we derive the condition for multi-edge type LDPC code ensembles with exponentially decreasing small linear weight codewords.

The support weight distribution of a code is the number of unique subspaces of the code with specified dimension and support weight. The extrinsic information transfer (EXIT) function on erasure channels is exactly described by the support weight distribution. In this paper, we formulate the average second support weight distribution of regular LDPC code ensembles.

Jin et al. introduce irregular repeat-accumulate (IRA) codes. IRA codes have a linear-time encoding algorithm. The authors have introduced detailedly represented irregular low-density parity-check code ensembles specified with joint degree distributions between variable nodes and check nodes. In this paper, by using density evolution method [6], we design IRA codes specified with joint degree distributions. Resulting codes have higher thresholds and lower error floors than standard IRA codes.

Since the joint distribution considered in the CCCP decoding presented in the previous work is different from the a posteriori probability considered in the usual sum-product decoding, there is the possibility that the direct comparison of error performance of those decoding algorithms might be unfair. In this paper, we clear up this suspicion by showing that an objective function that is equivalent to the one minimized in the conventional CCCP decoding can be derived from the a posteriori probability distribution treated in the sum-product algorithm. Moreover, we present more efficient implementation of the CCCP decoding.

Belief Propagation(BP) decoding is equivalent to Maximum a Posteriori(MAP) decoding when the Tanner graph of the code is free of cycles. Performance of BP decoding with Tanner graph with cycle is often not good if the Tanner graph has cycles of length four. Adding redundant parity-checks and puncturing bits, Yedidia et al. transformed high-density parity-check matrices to low-density ones. In this report, we investigate the transformation of parity-check matrices (or equivalently of Tanner graphs) removing cycles of length four in Tanner graphs, which is the special case of Yedidia's transformation. We prove that, when transmission over erasure channels, under the transformation, BP-recoverable erasures are preserved. We show transforming Tanner graph of (7,4,3) Hamming code makes some new BP-recoverable erasures.

Richardson et al. showed concentration of the performance of the BP decoder around its average performance in the regular and irregular LDPC code ensemble and that its average performance converges to the performance obtained by density evolution. Furthermore, Kasai et al. presented detailedly represented ensemble and its density evolution in order to look for ensembles which have better threshold than standard irregular ensembles. In this paper, we show concentration of the performance of the BP decoder around its average performance in the detailedly represented ensemble and that its average performance converges to the performance obtained by density evolution.

Burshtein and Miller provided an asymptotic estimation of the exponent of the average weight distribution for conventional irregular LDPC ensembles defined by Richardson et al., which are based on bipartite graphs. This estimation is derived by the asymptotic estimation of the exponent of a coefficient in multinomials with non-negative coefficients. In this paper, we employ Burshtein's method to provide an asymptotic estimation of the exponent of the average weight distribution for detailedly represented irregular LDPC ensembles. Moreover, we present numerical examples which show the relation between the exponent of the average weight distribution for conventional and detailedly represented ensemble, and provide an example of code ensemble which has larger typical minimum distance than given conventional ensemble has.

It is well known that a decoding algorithm based on sum-product algorithm requires a little computation to give extremely good decoding performance. A conventional CCCP-based decoding algorithm is expected to outperform sum-product decoding algorithm. However, it has huge computational complexity as opposed to sum-product algorithm. In our report, we propose a new CCCP-based decoding algorithm whose computational complexity is comparable to that of sum-product algorithm. We also show by numerical simulations that the decoding performance of the proposed algorithm is better than that of sum-product algorithm for an LDPC code with relatively short length.

We have proposed a low-density parity-check code ensemble C_1(η,π) and developed its density evolution. The density evolution for C_1(η,π) required a conjecture which was supported empirically. In this report we simplify the conjecture to derive the density evolution for C_1(η,π). Further, we propose a subensemble C_2(η,π) ⊂ C_1(η,π) whose density evolution does not require any conjecture.

In this paper, we investigate the tightness of Tanner's lower bound for the minimum distance of regular low-density parity-check (LDPC) codes. More precisely, we introduce two classes of regular LDPC codes based on a combinatorial design known as Steiner system and we formulate Tanner's lower bound for these codes. Moreover, we point out that one of these two classes of codes contains EG-LDPC codes and show that Tanner's lower bound agrees with BCH bound for EG-LDPC codes.

The notion of generalized Hamming weights was first introduced by Wei. Since then, lots of authors have investigated generalized Hamming weights and have derived some estimates or true weights for several codes. As for q-ary Reed-Muller(RM)codes, the calculation method of its generalized Hamming weight was developed by Wei for binary(q=2)case and by Heijnen and Pellikaan for any q. Recently, we proposed a lower bound for the generalized Hamming weight which can be applied to arbitrary [n, k]linear code C. Moreover, we defined a parameter, denote by g(C), which can be easily calculated for given code C and we showed that the t-th generalized Hamming weight of code C, denote by d_t(C), is equal to n-k+t for g(C)+1≤t≤k. C is said to be t-th rank MDS(Maximum Distance Separable)if d_t(C)=n-k+t. For a q-ary RM code of order u and m variables, we have derived an explicit formula of g(C)in term of u, m and q. In this paper, we show that for binary RM codes C, g(C)gives a necessary and sufficient condition on t for C to be t-th rank MDS, that is d_t(C)=n-k+t if and only if g(C)+1≤t≤k.

It has been reported that Turbo-Codes attain the performance close to the Shannon limits. Since then, Turbo-Codes are much attractive to many researchers. But, the decoding delay due to the iterative decoding can not be disregarded. In this study, we propose a new algorithm emulating BCJR algorithm which is employed in the conventional decoder of Turbo-Codes. Since the proposed algorithm is processed in parallel, the decoding delay can be reduced. We also examine by computer simulation the performance of Turbo-Code with the proposed algorithm. Then we show that the proposed algorithm attains the performance almost same as that of the conventional one.

In this paper, the tightness of lower bounds for generalized Hamming weights proposed in is investigated in the case of some algebraic geometric codes. It is shown that g^*&le;g where g^* denotes the parameter which was introduced in to give the lower bound of generalized Hamming weights and g denotes the genus of the curve C_<ab>. This implies that the range for which our lower bound agrees with the true weight is not narrower than the conventional one.

As a generalization of conventional algebraic geometric codes, codes constructed on affine algebraic varieties were proposed by S.Miura. He has shown that by introducing a monomial order and a Grobner basis in the code construction, the Feng-Rao designed distance gives a non-trivial lower bound for the minimum distance of the code. In this paper, we give a lower bound for the generalized Hamming weights of linear codes on affine algebraic varieties constructed by Miura's method. We first investigate a kind of linearly dependent relation on the sequence of parity check matrices by using the monomial order and the Grobner basis employed. Then we provide a lower bound for the generalized Hamming weights of the code. Next, by introducing a number g^* which is determined by a given affine algebraic variety, we show that when the order π of generalized Hamming weights is greater than g^*, the proposed lower bound agrees with the true generalized Hamming weights. Finally, we improve the proposed bound for μ>g^* by using the notion of well-behaving pair which was introduced by Feng and Rao.