澁谷 智治

In this paper, we propose a group theoretic representation suitable for the rank-modulation (RM) scheme over the multi-cell ranking presented by En Gad et al. By introducing an action of the group of all permutation matrices on the set of all permutations, the scheme is clearly reformulated. Moreover, weintroduce the concept ofr-dominating sets over the multi-cell ranking, which is a generalization of conventional dominating sets, inthe design of rank-modulation rewriting codes. The concept together with the proposed group theoretic representation yields an explicit formula of an upper bound on the size of the set of messages that can be stored in the memory by using RM rewriting codes over multi-cell ranking. This bound enables us to consider the trade-off between the size of the storable message set and the rewriting cost more closely. We also provide a concrete example of RM rewriting code that is not available by conventional approaches and whose size of the storable message set can not be achieved by conventional codes.

In this paper, we study rank-modulation (RM) rewriting codes based on dominating sets. By introducing a special class of dominating sets in a construction of RM rewriting codes and employing the notion of a group action in an analysis of those codes, we succeeded to construct. RM rewriting codes based on the dominating sets that maximize the amount of stored data under the limit of rewriting cost for flash memories with 4 and 5 cells.

The amplitude damping (AD) quantum channel is one of the models describing evolution of quantum states. The construction of quantum error correcting codes for the AD channel based on classical codes has been presented, and Shor et al. proposed a class of classical codes over F-3 which are efficiently applicable to this construction. In this study, we expand Shor's construction to that over F-7, and succeeded to construct an AD code that has better parameters than AD codes constructed by Shor et al.

In this paper, we propose a new encoding method applicable to any linear codes over arbitrary finite field whose computational complexity is O(δ*n) where δ* and n denote the maximum column weight of a parity check matrix of a code and the code length, respectively. This means that if a code has a parity check matrix with the constant maximum column weight, such as LDPC codes, it can be encoded with O(n) computation. We also clarify the relation between the proposed method and conventional methods, and compare the computational complexity of those methods. Then we show that the proposed encoding method is much more efficient than the conventional ones. © 2014 The Institute of Electronics, Information and Communication Engineers.

The amplitude damping (AD) quantum channel is one of the models describing evolution of quantum states. Several constructions of quantum error correcting codes for the AD channel based on classical codes has been presented, and Shor et al. proposed a class of classical codes over F-3 which are efficiently applicable to this construction. Recently, we succeeded to expand Shor's construction to that based on classical codes over F-7. In this study, we further expand our construction method to that based on classical codes over F-p where p is arbitrary odd prime.

Entanglement-assisted quantum error-correcting (EAQEC) codes, a wider class of stabilizer codes, allow us to construct quantum error-correcting codes from arbitrary classical codes with the help of ebits, i.e. maximally entangled quantum states. However, in the construction of EAQEC codes, it is desirable to use as small number of ebits as possible because of the high cost in the preparation of those entangled states. In addition, it is also desired that the error-correcting capability of classical codes from which EAQEC codes are constructed is as high as possible. In order to solve those problems, we consider in this paper a class of EAQEC codes that are based on classical LDPC codes whose parity check matrices are designed by the circulant permutation matrix. Then we give some sufficient conditions on those parity check matrices so that the obtained EAQEC codes need only one ebits. Moreover, we also clarify the condition on which parity check matrices satisfying above sufficient conditions have no 4-cycle, which is one of the important characteristics for the sum-product decoding to exhibit high error-correcting capability.

Spatially coupled (SC) low-density parity-check (LDPC) codes are defined 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.© 2013 The Institute of Electronics, Information and Communication Engineers.

In this paper, we propose a new encoding algorithm applicable to any linear codes over arbitrary finite field whose computational complexity is O(w(H)) where w(H) denotes the number of non-zero elements in a parity check matrix H of a code. The proposed algorithm is essentially equivalent to the linear time encoding algorithm presented by Lu et al. when the maximum column weight delta* of H is less than or equal to 3, and is regarded as a natural generalization of the algorithm when delta* > 3. Moreover, the proposed algorithm can encode any linear codes defined by sparse parity check matrices, such as LDPC codes, with O(n) complexity where n denotes the code length.

線形符号の反復符号化に適した検査行列の環論的構成に関する研究

In this paper, we propose a new encoding algorithm for linear codes whose computational complexity is O(w( H)) where w(H) denotes the number of non-zero elements in a parity check matrix H of a code. The proposed algorithm is based on the block-triangularization - an efficient technique to solve a system of linear equations - of a parity part of a parity check matrix, combining additional row and column permutations. As a result, the proposed algorithm can encode any linear codes defined by sparse parity check matrices, such as LDPC codes, with O(n) complexity where n denotes the code length.

Recently Mooij et al proposed new sufficient conditions for convergence of the sum product algorithm and it was also shown that if the factor graph is a tree Mooijs sufficient condition for convergence is always activated. In this letter we show that the converse of the above statement is also true under some assumption and that the assumption holds for the sum product decoding. These newly obtained fact implies that Mooijs sufficient condition for convergence of the sum product decoding is activated if and only if the factor graph of the a posteriori probability of the transmitted codeword is a tree

Luby et al. derived evolution of degree distributions in residual graphs for irregular LDPC code ensembles. Evolution of degree distributions in residual graphs is important characteristic which is used for finite-length analysis of the expected block and bit error probability 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.

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 small linear weight codewords exponentially decreasing in code length. Nakasendo et al. derived the condition in which code ensembles have exponentially decreasing small linear weight codewords for two-edge type LDPC code ensembles which is simple example of mufti-edge type LDPC code ensembles. Our conclusion is the same as that of Nakasendo et al., and although Nakasendo's method is difficult to apply to more than three edge-types, there is a possibility that our method using Hayman approximation as Di et al. do derives the condition for mufti-edge type LDPC codes ensembles.

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 paper, we derive the condition for three-edge type LDPC code ensembles whose edge-types does not share any variable node and does share all of the check nodes with exponentially decreasing small linear weight codewords. The condition is necessary for the existence of the average relative minimum distance of ensembles. Our method is expected to derive the condition for multi-edge type LDPC codes.

Multi-Edge type LDPC codes are introduced by Richardson and Urbanke, and they show examples of their ensembles has 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. We derive the condition corresponding to Orlitsky's condition for two-edge type LDPC code ensembles which is simple example of Multi-Edge type LDPC code ensembles.

In this paper, we consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes. We consider MAP decoding not using a whole Wanner graph but only a neighborhood graph of fixed depth preferred to as local-MAP decoding for deriving lower bounds of the error probability under message-passing decoding and bit-flipping decoding. The main result of this paper is to derive an asymptotic performance for regular ensembles under local-MAP decoding and to derive an asymptotic gap of the bit error probability between belief propagation (BP) and local-MAP decoding for irregular ensembles. Finally, we show the limit of the scaling parameter of these decodings when number of iterations tends to infinity.

Weight distributions of binary low-density parity-check (LDPC) codes are well studied in [1],[5],[4],[2]. We investigate the average distributions of symbol and binary weight for non-binary LDPC code ensemble. We derive the asymptotic growth rate and its linear approximation for small weight. Moreover, we show the typical minimum distance does not monotonically increase with the size of the field where the codes are defined.

We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. Furthermore, a gap between the bit error probability after finite number of iterations for finite block length n and that for infinite block length is asymptotically alpha/n, where alpha denotes a specific constant determined by a degree distribution, a number of iterations and erasure probability. Our main result is to derive an efficient algorithm for calculating alpha for regular ensembles.

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.

The average bit erasure probability of a binary linear code ensemble under maximum a-posteriori probability (MAP). decoding over binary erasure channel (BEC) can be calculated with the average support weight distribution of the ensemble via the EXIT function and the shortened information function. In this paper, we formulate the relationship between the average bit erasure probability under MAP decoding over BEC and the average support weight distribution for a binary linear code ensemble. Then, we formulate the average support weight distribution and the average bit erasure probability under MAP decoding over BEC for regular LDPC code ensembles.

In this paper, we derive an upper bound for the average block error probability of a standard irregular low-density parity-check (LDPC) code ensemble under the maximum-likelihood (ML) decoding. Moreover, we show that the upper bound asymptotically decreases polynomially with the code length. Furthermore, when we consider several regular LDPC code ensembles as special cases of standard irregular ones over an additive white Gaussian noise channel, we numerically show that the signal-to-noise ratio (SNR) thresholds at which the proposed bound converges to zero as the code length tends to infinity are smaller than those for a bound provided by Miller et al.. We also give an example of a standard irregular LDPC code ensemble which has a lower SNR threshold than a given regular LDPC code ensemble.

Irregular Repeat-Accumulate (IRA) codes, introduced by Jin et al., have a linear-time encoding algorithm and their decoding performance is comparable to that of irregular low-density parity-check (LDPC) codes. Meanwhile the authors have introduced detailedly represented irregular LDPC code ensembles specified with joint degree distributions between variable nodes and check nodes. In this paper, by using density evolution method [7], [8], we optimize IRA codes specified with joint degree distributions. Resulting codes have higher thresholds than Jin's IRA codes.

Multi-Edge type Low-Density Parity-Check codes (MET-LDPC codes) introduced by Richardson and Urbanke are generalized LDPC codes which can be seen as LDPC codes obtained by concatenating several standard (ir)regular LDPC codes. We prove in this paper that MET-LDPC code ensembles possess a certain symmetry with respect to their Average Coset Weight Distributions (ACWD). Using this symmetry, we drive ACWD of MET-LDPC code ensembles from ACWD of their constituent ensembles.

Multi-Edge type Low-Density Parity-Check codes (MET-LDPC codes) introduced by Richardson and Urbanke are generalized LDPC codes which can be seen as LDPC codes obtained by concatenating several standard (ir)regular LDPC codes. We prove in this paper that MET-LDPC code ensembles possess a certain symmetry with respect to their Average Coset Weight Distributions (ACWD). Using this symmetry, we drive ACWD of MET-LDPC code ensembles from ACWD of their constituent ensembles. Copyright © 2006 The Institute of Electronics, Information and Communication Engineers.

In this paper, we explicitly formulate the average weight and the stopping set distributions and their asymptotic exponents of two-edge type LDPC code ensembles. We also show some characteristics such as the symmetry and the conditions for zero of the weight distributions of two code ensembles. Further we investigate the relation between two code ensembles from the perspectives of the weight and stopping set distributions.

New decoding algorithms for binary linear codes based on the concave-convex procedure are presented. Numerical experiments show that the proposed decoding algorithms surpass Belief Propagation (BP) decoding in error performance. Average computational complexity of one of the proposed decoding algorithms is only a few times greater than that of the BP decoding.

We have been developing an interactive and realtime multimedia distance education system among multiple sites using IP (Internet protocol) -based satellite networks. Video, audio, telepointers, and other data must be efficiently shared among many sites through such a network. We have therefore designed basic multicast-capable networks for efficient communication through satellite communication. We have developed a set of tools, called FocusShare, which include a sender application, a receiver application, a multipoint viewer, and other tools. Using two satellite communication networks and the developed tools, we have conducted experiments in cooperation with groups in other countries to demonstrate the appropriateness of our satellite IP network, and have shown that our tool suite is useful for point-to-point and multipoint conferencing.

We have developed a prototype system for 3D video distance education using satellite communications and IP multicasting. Our system is based on personal computers and software codecs. The system is inexpensive and flexible for various configurations because it utilizes software modules. Our system can be easily installed outdoors since it does not use special hardware to encode, decode, or transmit multimedia data. Testing of our system implemented between a horticulture farm and an indoor studio, approximately 140 km apart, showed that it effectively supports distance education between indoor and outdoor environments and that it provides an enhanced 3D educational environment. © 2005 IEEE.

In this paper, we provide explicit representations of average weight and stopping set distributions and asymptotic expressions of their exponent for detailedly represented irregular LDPC code ensembles. Further we present numerical examples which compare a detailedly represented irregular LDPC code ensemble with a conventional one with respect to both of weight and stopping set distributions. key words: weight distribution, stopping set distribution, detailedly represented irregular LDPC code ensemble with a conventional one with respect to both of weight and stopping set distributions.

In this paper, we provide explicit representations of average weight and stopping set distributions and asymptotic expressions of their exponent for detailedly represented irregular LDPC code ensembles. Further we present numerical examples which compare a detailedly represented irregular LDPC code ensemble with a conventional one with respect to both of weight and stopping set distributions.

In this paper, we investigate Tanner's lower bound for the minimum distance of regular LDPC codes based on combinatorial designs. We first determine Tanner's lower bound for LDPC codes which are defined by modifying bipartite graphs obtained from combinatorial designs known as Steiner systems. Then we show that Tanner's lower bound agrees with or exceeds conventional lower bounds including the BCH bound, and gives the true minimum distance for some EG-LDPC codes.

In this letter, we show the effectiveness of a double-loop algorithm based on the concave-convex procedure (CCCP) in decoding linear codes. For this purpose, we numerically compare the error performance of CCCP-based decoding algorithm with that of a conventional iterative decoding algorithm based on belief propagation (BP). We also investigate computational complexity and its relation to the error performance.

Richardson and Urbanke developed a powerful method density evolution which determines, for various channels; the capacity of irregular low-density parity-check code ensembles. We develop generalized density evolution for minutely represented ensembles and show it includes conventional representation as a special case. Furthermore, we present an example of code ensembles used over binary erasure channel and binary input. additive white Gaussian noise channel which have better thresholds than highly optimized ensembles with conventional representation.

In this paper, we investigate Tanner's lower bound for the minimum distance of regular LDPC codes based on combinatorial designs We first determine Tanner's lower bound for LDPC codes which are defined by modifying bipartite graphs obtained from combinatorial designs known as Steiner systems Then we show that Tanner's lower bound agrees with or exceeds conventional lower bounds including the BCH bound, and gives the true minimum distance for some EG-LDPC codes.