Showing 1–33 of 33 results for author: Kasai, K

Spatially-Coupled MacKay-Neal Codes Universally Achieve the Symmetric Information Rate of Arbitrary Generalized Erasure Channels with Memory

Authors: Masaru Fukushima, Takuya Okazaki, Kenta Kasai

Abstract: This paper investigates the belief propagation decoding of spatially-coupled MacKay-Neal (SC-MN) codes over erasure channels with memory. We show that SC-MN codes with bounded degree universally achieve the symmetric information rate (SIR) of arbitrary erasure channels with memory. We mean by universality the following sense: the sender does not need to know the whole channel statistics but needs… ▽ More This paper investigates the belief propagation decoding of spatially-coupled MacKay-Neal (SC-MN) codes over erasure channels with memory. We show that SC-MN codes with bounded degree universally achieve the symmetric information rate (SIR) of arbitrary erasure channels with memory. We mean by universality the following sense: the sender does not need to know the whole channel statistics but needs to know only the SIR, while the receiver estimates the transmitted codewords from channel statistics and received words. The proof is based on potential function. △ Less

Submitted 27 January, 2015; originally announced January 2015.

Non-Binary LDPC Codes with Large Alphabet Size

Authors: Koji Tazoe, Kenta Kasai, Kohichi Sakaniwa

Abstract: We study LDPC codes for the channel with input ${x}\in \mathbb{F}_q^m$ and output ${y}={x}+{z}\in \mathbb{F}_q^m$. The aim of this paper is to evaluate decoding performance of $q^m$-ary non-binary LDPC codes for large $m$. We give density evolution and decoding performance evaluation for regular non-binary LDPC codes and spatially-coupled (SC) codes. We show the regular codes do not achieve the ca… ▽ More We study LDPC codes for the channel with input ${x}\in \mathbb{F}_q^m$ and output ${y}={x}+{z}\in \mathbb{F}_q^m$. The aim of this paper is to evaluate decoding performance of $q^m$-ary non-binary LDPC codes for large $m$. We give density evolution and decoding performance evaluation for regular non-binary LDPC codes and spatially-coupled (SC) codes. We show the regular codes do not achieve the capacity of the channel while SC codes do. △ Less

Submitted 28 January, 2014; originally announced January 2014.

Spatially-Coupled MacKay-Neal Codes with No Bit Nodes of Degree Two Achieve the Capacity of BEC

Authors: Takuya Okazaki, Kenta Kasai

Abstract: Obata et al. proved that spatially-coupled (SC) MacKay-Neal (MN) codes achieve the capacity of BEC. However, the SC-MN codes codes have many variable nodes of degree two and have higher error floors. In this paper, we prove that SC-MN codes with no variable nodes of degree two achieve the capacity of BEC. Obata et al. proved that spatially-coupled (SC) MacKay-Neal (MN) codes achieve the capacity of BEC. However, the SC-MN codes codes have many variable nodes of degree two and have higher error floors. In this paper, we prove that SC-MN codes with no variable nodes of degree two achieve the capacity of BEC. △ Less

Submitted 28 January, 2014; originally announced January 2014.

Spatially-Coupled Precoded Rateless Codes with Bounded Degree Achieve the Capacity of BEC under BP decoding

Authors: Kosuke Sakata, Kenta Kasai, Kohichi Sakaniwa

Abstract: Raptor codes are known as precoded rateless codes that achieve the capacity of BEC. However the maximum degree of Raptor codes needs to be unbounded to achieve the capacity. In this paper, we prove that spatially-coupled precoded rateless codes achieve the capacity with bounded degree under BP decoding. Raptor codes are known as precoded rateless codes that achieve the capacity of BEC. However the maximum degree of Raptor codes needs to be unbounded to achieve the capacity. In this paper, we prove that spatially-coupled precoded rateless codes achieve the capacity with bounded degree under BP decoding. △ Less

Submitted 28 January, 2014; originally announced January 2014.

Iterative pre-distortion of the non-linear satellite channel

Authors: Thibault Deleu, Mathieu Dervin, Kenta Kasai, François Horlin

Abstract: Digital Video Broadcasting - Satellite - Second Generation (DVB-S2) is the current European standard for satellite broadcast and broadband communications. It relies on high order modulations up to 32-amplitude/phase-shift-keying (APSK) in order to increase the system spectral efficiency. Unfortunately, as the modulation order increases, the receiver becomes more sensitive to physical layer impairm… ▽ More Digital Video Broadcasting - Satellite - Second Generation (DVB-S2) is the current European standard for satellite broadcast and broadband communications. It relies on high order modulations up to 32-amplitude/phase-shift-keying (APSK) in order to increase the system spectral efficiency. Unfortunately, as the modulation order increases, the receiver becomes more sensitive to physical layer impairments, and notably to the distortions induced by the power amplifier and the channelizing filters aboard the satellite. Pre-distortion of the non-linear satellite channel has been studied for many years. However, the performance of existing pre-distortion algorithms generally becomes poor when high-order modulations are used on a non-linear channel with a long memory. In this paper, we investigate a new iterative method that pre-distorts blocks of transmitted symbols so as to minimize the Euclidian distance between the transmitted and received symbols. We also propose approximations to relax the pre-distorter complexity while keeping its performance acceptable. △ Less

Submitted 13 May, 2014; v1 submitted 20 January, 2014; originally announced January 2014.

Weight Distribution for Non-binary Cluster LDPC Code Ensemble

Authors: Takayuki Nozaki, Masaki Maehara, Kenta Kasai, Kohichi Sakaniwa

Abstract: 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,d_c)$-regular non-binary cluster LDPC code ensembles whose normalized typical minimum distances are strictly pos… ▽ More 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,d_c)$-regular non-binary cluster LDPC code ensembles whose normalized typical minimum distances are strictly positive. △ Less

Submitted 16 May, 2013; v1 submitted 11 May, 2013; originally announced May 2013.

Comments: 12pages, 6 figures, To be presented in ISIT2013, Submitted to IEICE Trans. Fundamentals

Efficient Termination of Spatially-Coupled Codes

Authors: Koji Tazoe, Kenta Kasai, Kohichi Sakaniwa

Abstract: Spatially-coupled low-density parity-check codes attract much attention due to their capacity-achieving performance and a memory-efficient sliding-window decoding algorithm. On the other hand, the encoder needs to solve large linear equations to terminate the encoding process. In this paper, we propose modified spatially-coupled codes. The modified $(\dl,\dr,L)$ codes have less rate-loss, i.e., hi… ▽ More Spatially-coupled low-density parity-check codes attract much attention due to their capacity-achieving performance and a memory-efficient sliding-window decoding algorithm. On the other hand, the encoder needs to solve large linear equations to terminate the encoding process. In this paper, we propose modified spatially-coupled codes. The modified $(\dl,\dr,L)$ codes have less rate-loss, i.e., higher coding rate, and have the same threshold as $(\dl,\dr,L)$ codes and are efficiently terminable by using an accumulator. △ Less

Submitted 6 February, 2013; originally announced February 2013.

Spatially-Coupled Precoded Rateless Codes

Authors: Kosuke Sakata, Kenta Kasai, Kohichi Sakaniwa

Abstract: Raptor codes are rateless codes that achieve the capacity on the binary erasure channels. However the maximum degree of optimal output degree distribution is unbounded. This leads to a computational complexity problem both at encoders and decoders. Aref and Urbanke investigated the potential advantage of universal achieving-capacity property of proposed spatially-coupled (SC) low-density generator… ▽ More Raptor codes are rateless codes that achieve the capacity on the binary erasure channels. However the maximum degree of optimal output degree distribution is unbounded. This leads to a computational complexity problem both at encoders and decoders. Aref and Urbanke investigated the potential advantage of universal achieving-capacity property of proposed spatially-coupled (SC) low-density generator matrix (LDGM) codes. However the decoding error probability of SC-LDGM codes is bounded away from 0. In this paper, we investigate SC-LDGM codes concatenated with SC low-density parity-check codes. The proposed codes can be regarded as SC Hsu-Anastasopoulos rateless codes. We derive a lower bound of the asymptotic overhead from stability analysis for successful decoding by density evolution. The numerical calculation reveals that the lower bound is tight. We observe that with a sufficiently large number of information bits, the asymptotic overhead and the decoding error rate approach 0 with bounded maximum degree. △ Less

Submitted 6 February, 2013; originally announced February 2013.

Multi-Dimensional Spatially-Coupled Codes

Authors: Ryunosuke Ohashi, Kenta Kasai, Keigo Takeuchi

Abstract: Spatially-coupled (SC) codes are constructed by coupling many regular low-density parity-check codes in a chain. The decoding chain of SC codes stops when facing burst erasures. This problem can not be overcome by increasing coupling number. In this paper, we introduce multi-dimensional (MD) SC codes. Numerical results show that 2D-SC codes are more robust to the burst erasures than 1D-SC codes. F… ▽ More Spatially-coupled (SC) codes are constructed by coupling many regular low-density parity-check codes in a chain. The decoding chain of SC codes stops when facing burst erasures. This problem can not be overcome by increasing coupling number. In this paper, we introduce multi-dimensional (MD) SC codes. Numerical results show that 2D-SC codes are more robust to the burst erasures than 1D-SC codes. Furthermore, we consider designing MD-SC codes with smaller rateloss. △ Less

Submitted 6 February, 2013; originally announced February 2013.

A Potential Theory of General Spatially-Coupled Systems via a Continuum Approximation

Authors: Keigo Takeuchi, Toshiyuki Tanaka, Kenta Kasai

Abstract: This paper analyzes general spatially-coupled (SC) systems with multi-dimensional coupling. A continuum approximation is used to derive potential functions that characterize the performance of the SC systems. For any dimension of coupling, it is shown that, if the boundary of the SC systems is fixed to the unique stable solution that minimizes the potential over all stationary solutions, the syste… ▽ More This paper analyzes general spatially-coupled (SC) systems with multi-dimensional coupling. A continuum approximation is used to derive potential functions that characterize the performance of the SC systems. For any dimension of coupling, it is shown that, if the boundary of the SC systems is fixed to the unique stable solution that minimizes the potential over all stationary solutions, the systems can approach the optimal performance as the number of coupled systems tends to infinity. △ Less

Submitted 18 April, 2013; v1 submitted 24 January, 2013; originally announced January 2013.

Comments: submitted to IEEE ITW2013

Approaching the Capacity of Large-Scale MIMO Systems via Non-Binary LDPC Codes

Authors: Puripong Suthisopapan, Kenta Kasai, Anupap Meesomboon, Virasit Imtawil

Abstract: In this paper, the application of non-binary low-density parity-check (NBLDPC) codes to MIMO systems which employ hundreds of antennas at both the transmitter and the receiver has been proposed. Together with the well-known low-complexity MMSE detection, the moderate length NBLDPC codes can operate closer to the MIMO capacity, e.g., capacity-gap about 3.5 dB (the best known gap is more than 7 dB).… ▽ More In this paper, the application of non-binary low-density parity-check (NBLDPC) codes to MIMO systems which employ hundreds of antennas at both the transmitter and the receiver has been proposed. Together with the well-known low-complexity MMSE detection, the moderate length NBLDPC codes can operate closer to the MIMO capacity, e.g., capacity-gap about 3.5 dB (the best known gap is more than 7 dB). To further reduce the complexity of MMSE detection, a novel soft output detection that can provide an excellent coded performance in low SNR region with 99% complexity reduction is also proposed. The asymptotic performance is analysed by using the Monte Carlo density evolution. It is found that the NBLDPC codes can operate within 1.6 dB from the MIMO capacity. Furthermore, the merit of using the NBLDPC codes in large MIMO systems with the presence of imperfect channel estimation and spatial fading correlation which are both the realistic scenarios for large MIMO systems is also pointed out. △ Less

Submitted 21 November, 2012; originally announced November 2012.

Comments: 29 pages. arXiv admin note: substantial text overlap with arXiv:1203.0960, arXiv:1204.4151

Ultra Low Complexity Soft Output Detector for Non-Binary LDPC Coded Large MIMO Systems

Authors: Puripong Suthisopapan, Anupap Meesomboon, Kenta Kasai, Virasit Imtawil

Abstract: The theoretic results of MIMO capacity tell us that the higher the number of antennas are employed, the higher the transmission rate is. This makes MIMO systems with hundreds of antennas very attractive but one of the major problems that obstructs such large dimensional MIMO systems from the practical realization is a high complexity of the MIMO detector. We present in this paper the new soft outp… ▽ More The theoretic results of MIMO capacity tell us that the higher the number of antennas are employed, the higher the transmission rate is. This makes MIMO systems with hundreds of antennas very attractive but one of the major problems that obstructs such large dimensional MIMO systems from the practical realization is a high complexity of the MIMO detector. We present in this paper the new soft output MIMO detector based on matched filtering that can be applied to the large MIMO systems which are coded by the powerful non-binary LDPC codes. The per-bit complexity of the proposed detector is just 0.28% to that of low complexity soft output MMSE detector and scales only linearly with a number of antennas. Furthermore, the coded performances with small information length 800 bits are within 4.2 dB from the associated MIMO capacity. △ Less

Submitted 18 April, 2012; originally announced April 2012.

Near Capacity Approaching for Large MIMO Systems by Non-Binary LDPC Codes with MMSE Detection

Authors: Puripong Suthisopapan, Kenta Kasai, Anupap Meesomboon, Virasit Imtawil

Abstract: In this paper, we have investigated the application of non-binary LDPC codes to spatial multiplexing MIMO systems with a large number of low power antennas. We demonstrate that such large MIMO systems incorporating with low-complexity MMSE detector and non-binary LDPC codes can achieve low probability of bit error at near MIMO capacity. The new proposed non-binary LDPC coded system also performs b… ▽ More In this paper, we have investigated the application of non-binary LDPC codes to spatial multiplexing MIMO systems with a large number of low power antennas. We demonstrate that such large MIMO systems incorporating with low-complexity MMSE detector and non-binary LDPC codes can achieve low probability of bit error at near MIMO capacity. The new proposed non-binary LDPC coded system also performs better than other coded large MIMO systems known in the present literature. For instance, non-binary LDPC coded BPSK-MIMO system with 600 transmit/receive antennas performs within 3.4 dB from the capacity while the best known turbo coded system operates about 9.4 dB away from the capacity. Based on the simulation results provided in this paper, the proposed non-binary LDPC coded large MIMO system is capable of supporting ultra high spectral efficiency at low bit error rate. △ Less

Submitted 5 March, 2012; originally announced March 2012.

Spatially-Coupled Binary MacKay-Neal Codes for Channels with Non-Binary Inputs and Affine Subspace Outputs

Authors: Kenta Kasai, Takayuki Nozaki, Kohichi Sakaniwa

Abstract: We study LDPC codes for the channel with $2^m$-ary input $\underline{x}\in \mathbb{F}_2^m$ and output $\underline{y}=\underline{x}+\underline{z}\in \mathbb{F}_2^m$. The receiver knows a subspace $V\subset \mathbb{F}_2^m$ from which $\underline{z}=\underline{y}-\underline{x}$ is uniformly chosen. Or equivalently, the receiver receives an affine subspace $\underline{y}-V$ where $\underline{x}$ lies.… ▽ More We study LDPC codes for the channel with $2^m$-ary input $\underline{x}\in \mathbb{F}_2^m$ and output $\underline{y}=\underline{x}+\underline{z}\in \mathbb{F}_2^m$. The receiver knows a subspace $V\subset \mathbb{F}_2^m$ from which $\underline{z}=\underline{y}-\underline{x}$ is uniformly chosen. Or equivalently, the receiver receives an affine subspace $\underline{y}-V$ where $\underline{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., $2^m$-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. △ Less

Submitted 20 May, 2012; v1 submitted 5 February, 2012; originally announced February 2012.

Simple Low-Rate Non-Binary LDPC Coding for Relay Channels

Authors: Puripong Suthisopapan, Kenta Kasai, Anupap Meesomboon, Virasit Imtawil, Kohichi Sakaniwa

Abstract: Binary LDPC coded relay systems have been well studied previously with the assumption of infinite codeword length. In this paper, we deal with non-binary LDPC codes which can outperform their binary counterpart especially for practical codeword length. We utilize non-binary LDPC codes and recently invented non-binary coding techniques known as multiplicative repetition to design the low-rate codin… ▽ More Binary LDPC coded relay systems have been well studied previously with the assumption of infinite codeword length. In this paper, we deal with non-binary LDPC codes which can outperform their binary counterpart especially for practical codeword length. We utilize non-binary LDPC codes and recently invented non-binary coding techniques known as multiplicative repetition to design the low-rate coding strategy for the decode-and-forward half-duplex relay channel. We claim that the proposed strategy is simple since the destination and the relay can decode with almost the same computational complexity by sharing the same structure of decoder. Numerical experiments are carried out to show that the performances obtained by non-binary LDPC coded relay systems surpass the capacity of direct transmission and also approach within less than 1.5 dB from the achievable rate of the relay channels. △ Less

Submitted 16 August, 2011; originally announced August 2011.

Comments: submitted to IEEE JSAC

Threshold Improvement of Low-Density Lattice Codes via Spatial Coupling

Authors: Hironori Uchikawa, Brian M. Kurkoski, Kenta Kasai, Kohichi Sakaniwa

Abstract: Spatially-coupled low-density lattice codes (LDLC) are constructed using protographs. Using Monte Carlo density evolution using single-Gaussian messages, we observe that the threshold of the spatially-coupled LDLC is within 0.22 dB of capacity of the unconstrained power channel. This is in contrast with a 0.5 dB noise threshold for the conventional LDLC lattice construction. Spatially-coupled low-density lattice codes (LDLC) are constructed using protographs. Using Monte Carlo density evolution using single-Gaussian messages, we observe that the threshold of the spatially-coupled LDLC is within 0.22 dB of capacity of the unconstrained power channel. This is in contrast with a 0.5 dB noise threshold for the conventional LDLC lattice construction. △ Less

Submitted 25 July, 2011; originally announced July 2011.

Comments: 5 pages, 4 figures, submitted to ICNC2012

Analysis of Error Floors of Non-Binary LDPC Codes over MBIOS Channel

Authors: Takayuki Nozaki, Kenta Kasai, Kohichi Sakaniwa

Abstract: 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 provide a necessary and sufficient condition for successful decoding of zigzag cycle codes over the MBIOS channel by the belief propagation decoder. We consider an expurgated ensemble of non-binary LDPC codes by using… ▽ More 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 provide a necessary and sufficient condition for successful decoding of zigzag cycle codes over the MBIOS channel by the belief propagation decoder. We consider an expurgated ensemble of non-binary LDPC codes by using the above necessary and sufficient condition, and hence exhibit lower error floors. Finally, we show lower bounds of the error floors for the expurgated LDPC code ensembles over the MBIOS channel. △ Less

Submitted 10 June, 2011; originally announced June 2011.

Comments: 15 pages, 9 figures, The material in this paper was presented in part at IEEE International Conference on Communications, submitted in IEICE transaction fundamentals

Spatially Coupled LDPC Codes for Decode-and-Forward in Erasure Relay Channel

Authors: Hironori Uchikawa, Kenta Kasai, Kohichi Sakaniwa

Abstract: We consider spatially-coupled protograph-based LDPC codes for the three terminal erasure relay channel. It is observed that BP threshold value, the maximal erasure probability of the channel for which decoding error probability converges to zero, of spatially-coupled codes, in particular spatially-coupled MacKay-Neal code, is close to the theoretical limit for the relay channel. Empirical results… ▽ More We consider spatially-coupled protograph-based LDPC codes for the three terminal erasure relay channel. It is observed that BP threshold value, the maximal erasure probability of the channel for which decoding error probability converges to zero, of spatially-coupled codes, in particular spatially-coupled MacKay-Neal code, is close to the theoretical limit for the relay channel. Empirical results suggest that spatially-coupled protograph-based LDPC codes have great potential to achieve theoretical limit of a general relay channel. △ Less

Submitted 19 June, 2011; v1 submitted 24 February, 2011; originally announced February 2011.

Comments: 7 pages, extended version of ISIT2011

Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes

Authors: Kenta Kasai, Kohichi Sakaniwa

Abstract: Kudekar et al. recently proved that for transmission over the binary erasure channel (BEC), spatial coupling of LDPC codes increases the BP threshold of the coupled ensemble to the MAP threshold of the underlying LDPC codes. One major drawback of the capacity-achieving spatially-coupled LDPC codes is that one needs to increase the column and row weight of parity-check matrices of the underlying LD… ▽ More Kudekar et al. recently proved that for transmission over the binary erasure channel (BEC), spatial coupling of LDPC codes increases the BP threshold of the coupled ensemble to the MAP threshold of the underlying LDPC codes. One major drawback of the capacity-achieving spatially-coupled LDPC codes is that one needs to increase the column and row weight of parity-check matrices of the underlying LDPC codes. It is proved, that Hsu-Anastasopoulos (HA) codes and MacKay-Neal (MN) codes achieve the capacity of memoryless binary-input symmetric-output channels under MAP decoding with bounded column and row weight of the parity-check matrices. The HA codes and the MN codes are dual codes each other. The aim of this paper is to present an empirical evidence that spatially-coupled MN (resp. HA) codes with bounded column and row weight achieve the capacity of the BEC. To this end, we introduce a spatial coupling scheme of MN (resp. HA) codes. By density evolution analysis, we will show that the resulting spatially-coupled MN (resp. HA) codes have the BP threshold close to the Shannon limit. △ Less

Submitted 25 January, 2013; v1 submitted 22 February, 2011; originally announced February 2011.

Comments: Corrected typos in degree distributions νand μof MN and HA codes

Spatially Coupled Quasi-Cyclic Quantum LDPC Codes

Authors: Manabu Hagiwara, Kenta Kasai, Hideki Imai, Kohichi Sakaniwa

Abstract: We face the following dilemma for designing low-density parity-check codes (LDPC) for quantum error correction. 1) The row weights of parity-check should be large: The minimum distances are bounded above by the minimum row weights of parity-check matrices of constituent classical codes. Small minimum distance tends to result in poor decoding performance at the error-floor region. 2) The row weight… ▽ More We face the following dilemma for designing low-density parity-check codes (LDPC) for quantum error correction. 1) The row weights of parity-check should be large: The minimum distances are bounded above by the minimum row weights of parity-check matrices of constituent classical codes. Small minimum distance tends to result in poor decoding performance at the error-floor region. 2) The row weights of parity-check matrices should not be large: The sum-product decoding performance at the water-fall region is degraded as the row weight increases. Recently, Kudekar et al. showed spatially-coupled (SC) LDPC codes exhibit capacity-achieving performance for classical channels. SC LDPC codes have both large row weight and capacity-achieving error-floor and water-fall performance. In this paper, we design SC LDPC-CSS (Calderbank, Shor and Steane) codes for quantum error correction over the depolarizing channels. △ Less

Submitted 15 February, 2011; originally announced February 2011.

Spatially Coupled Codes over the Multiple Access Channel

Authors: Shrinivas Kudekar, Kenta Kasai

Abstract: We consider spatially coupled code ensembles over a multiple access channel. Convolutional LDPC ensembles are one instance of spatially coupled codes. It was shown recently that, for transmission over the binary erasure channel, this coupling of individual code ensembles has the effect of increasing the belief propagation threshold of the coupled ensembles to the maximum a-posteriori threshold of… ▽ More We consider spatially coupled code ensembles over a multiple access channel. Convolutional LDPC ensembles are one instance of spatially coupled codes. It was shown recently that, for transmission over the binary erasure channel, this coupling of individual code ensembles has the effect of increasing the belief propagation threshold of the coupled ensembles to the maximum a-posteriori threshold of the underlying ensemble. In this sense, spatially coupled codes were shown to be capacity achieving. It was observed, empirically, that these codes are universal in the sense that they achieve performance close to the Shannon threshold for any general binary-input memoryless symmetric channels. In this work we provide further evidence of the threshold saturation phenomena when transmitting over a class of multiple access channel. We show, by density evolution analysis and EXIT curves, that the belief propagation threshold of the coupled ensembles is very close to the ultimate Shannon limit. △ Less

Submitted 14 February, 2011; originally announced February 2011.

Report number: ISIT 2011

Threshold Saturation on Channels with Memory via Spatial Coupling

Authors: Shrinivas Kudekar, Kenta Kasai

Abstract: We consider spatially coupled code ensembles. A particular instance are convolutional LDPC ensembles. It was recently shown that, for transmission over the memoryless binary erasure channel, this coupling increases the belief propagation threshold of the ensemble to the maximum a-posteriori threshold of the underlying component ensemble. This paved the way for a new class of capacity achieving low… ▽ More We consider spatially coupled code ensembles. A particular instance are convolutional LDPC ensembles. It was recently shown that, for transmission over the memoryless binary erasure channel, this coupling increases the belief propagation threshold of the ensemble to the maximum a-posteriori threshold of the underlying component ensemble. This paved the way for a new class of capacity achieving low-density parity check codes. It was also shown empirically that the same threshold saturation occurs when we consider transmission over general binary input memoryless channels. In this work, we report on empirical evidence which suggests that the same phenomenon also occurs when transmission takes place over a class of channels with memory. This is confirmed both by simulations as well as by computing EXIT curves. △ Less

Submitted 2 February, 2011; originally announced February 2011.

Comments: Submitted to ISIT 2011

Analytical Solution of Covariance Evolution for Irregular LDPC Codes

Authors: Takayuki Nozaki, Kenta Kasai, Kohichi Sakaniwa

Abstract: A scaling law developed by Amraoui et al. is a powerful technique to estimate the block error probability of finite length low-density parity-check (LDPC) codes. Solving a system of differential equations called covariance evolution is a method to obtain the scaling parameter. However, the covariance evolution has not been analytically solved. In this paper, we present the analytical solution of t… ▽ More A scaling law developed by Amraoui et al. is a powerful technique to estimate the block error probability of finite length low-density parity-check (LDPC) codes. Solving a system of differential equations called covariance evolution is a method to 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. △ Less

Submitted 10 June, 2011; v1 submitted 7 November, 2010; originally announced November 2010.

Comments: 13pages, submitted to IEEE trans. on information theory, January 2010

Journal ref: IEEE Transactions on Information Theory (Volume:58, Issue: 7, pp.4770 - 4780, July 2012)

Effects of Single-Cycle Structure on Iterative Decoding for Low-Density Parity-Check Codes

Authors: Ryuhei Mori, Toshiyuki Tanaka, Kenta Kasai, Kohichi Sakaniwa

Abstract: We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as blocklength tends to infinity, and the limit is obtained via density evolution. On the other hand, the difference between the bit error probability of codes with blocklen… ▽ More We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding. For fixed numbers of BP iterations, the bit error probability approaches a limit as blocklength tends to infinity, and the limit is obtained via density evolution. On the other hand, the difference between the bit error probability of codes with blocklength $n$ and that in the large blocklength limit is asymptotically $α(ε,t)/n + Θ(n^{-2})$ where $α(ε,t)$ denotes a specific constant determined by the code ensemble considered, the number $t$ of iterations, and the erasure probability $ε$ of the BEC. In this paper, we derive a set of recursive formulas which allows evaluation of the constant $α(ε,t)$ for standard irregular ensembles. The dominant difference $α(ε,t)/n$ can be considered as effects of cycle-free and single-cycle structures of local graphs. Furthermore, it is confirmed via numerical simulations that estimation of the bit error probability using $α(ε,t)$ is accurate even for small blocklengths. △ Less

Submitted 2 October, 2010; originally announced October 2010.

Comments: 16 pages, 7 figures, submitted to IEEE Transactions on Information Theory

Design and Performance of Rate-compatible Non-Binary LDPC Convolutional Codes

Authors: Hironori Uchikawa, Kenta Kasai, Kohichi Sakaniwa

Abstract: In this paper, we present a construction method of non-binary low-density parity-check (LDPC) convolutional codes. Our construction method is an extension of Felstroem and Zigangirov construction for non-binary LDPC convolutional codes. The rate-compatibility of the non-binary convolutional code is also discussed. The proposed rate-compatible code is designed from one single mother (2,4)-regular n… ▽ More In this paper, we present a construction method of non-binary low-density parity-check (LDPC) convolutional codes. Our construction method is an extension of Felstroem and Zigangirov construction for non-binary LDPC convolutional codes. The rate-compatibility of the non-binary convolutional code is also discussed. The proposed rate-compatible code is designed from one single mother (2,4)-regular non-binary LDPC convolutional code of rate 1/2. Higher-rate codes are produced by puncturing the mother code and lower-rate codes are produced by multiplicatively repeating the mother code. Simulation results show that non-binary LDPC convolutional codes of rate 1/2 outperform state-of-the-art binary LDPC convolutional codes with comparable constraint bit length. Also the derived low-rate and high-rate non-binary LDPC convolutional codes exhibit good decoding performance without loss of large gap to the Shannon limits. △ Less

Submitted 19 June, 2011; v1 submitted 1 October, 2010; originally announced October 2010.

Comments: 8 pages, submitted to IEICE transaction

Weight Distributions of Multi-Edge type LDPC Codes

Authors: Kenta KASAI, Tomoharu AWANO, David DECLERCQ, Charly POULLIAT, Kohichi SAKANIWA

Abstract: The multi-edge type LDPC codes, introduced by Richardson and Urbanke, present the general class of structured LDPC codes. In this paper, we derive the average weight distributions of the multi-edge type LDPC code ensembles. Furthermore, we investigate the asymptotic exponential growth rate of the average weight distributions and investigate the connection to the stability condition of the density… ▽ More The multi-edge type LDPC codes, introduced by Richardson and Urbanke, present the general class of structured LDPC codes. In this paper, we derive the average weight distributions of the multi-edge type LDPC code ensembles. Furthermore, we investigate the asymptotic exponential growth rate of the average weight distributions and investigate the connection to the stability condition of the density evolution. △ Less

Submitted 6 September, 2010; originally announced September 2010.

Comments: To appear in IEICE Trans. Fundamentals, vol.E93-A, no.11 November 2010

Fourier Domain Decoding Algorithm of Non-Binary LDPC codes for Parallel Implementation

Authors: Kenta Kasai, Kohichi Sakaniwa

Abstract: For decoding non-binary low-density parity check (LDPC) codes, logarithm-domain sum-product (Log-SP) algorithms were proposed for reducing quantization effects of SP algorithm in conjunction with FFT. Since FFT is not applicable in the logarithm domain, the computations required at check nodes in the Log-SP algorithms are computationally intensive. What is worth, check nodes usually have higher de… ▽ More For decoding non-binary low-density parity check (LDPC) codes, logarithm-domain sum-product (Log-SP) algorithms were proposed for reducing quantization effects of SP algorithm in conjunction with FFT. Since FFT is not applicable in the logarithm domain, the computations required at check nodes in the Log-SP algorithms are computationally intensive. What is worth, check nodes usually have higher degree than variable nodes. As a result, most of the time for decoding is used for check node computations, which leads to a bottleneck effect. In this paper, we propose a Log-SP algorithm in the Fourier domain. With this algorithm, the role of variable nodes and check nodes are switched. The intensive computations are spread over lower-degree variable nodes, which can be efficiently calculated in parallel. Furthermore, we develop a fast calculation method for the estimated bits and syndromes in the Fourier domain. △ Less

Submitted 25 August, 2010; originally announced August 2010.

Comments: To appear in IEICE Trans. Fundamentals, vol.E93-A, no.11 November 2010

Quantum Error Correction beyond the Bounded Distance Decoding Limit

Authors: Kenta Kasai, Manabu Hagiwara, Hideki Imai, Kohichi Sakaniwa

Abstract: In this paper, we consider quantum error correction over depolarizing channels with non-binary low-density parity-check codes defined over Galois field of size $2^p$ . The proposed quantum error correcting codes are based on the binary quasi-cyclic CSS (Calderbank, Shor and Steane) codes. The resulting quantum codes outperform the best known quantum codes and surpass the performance limit of the b… ▽ More In this paper, we consider quantum error correction over depolarizing channels with non-binary low-density parity-check codes defined over Galois field of size $2^p$ . The proposed quantum error correcting codes are based on the binary quasi-cyclic CSS (Calderbank, Shor and Steane) codes. The resulting quantum codes outperform the best known quantum codes and surpass the performance limit of the bounded distance decoder. By increasing the size of the underlying Galois field, i.e., $2^p$, the error floors are considerably improved. △ Less

Submitted 13 July, 2011; v1 submitted 11 July, 2010; originally announced July 2010.

Comments: To appear in IEEE Transactions on Information Theory

Fountain Codes with Multiplicatively Repeated Non-Binary LDPC Codes

Authors: Kenta Kasai, Kohichi Sakaniwa

Abstract: We study fountain codes transmitted over the binary-input symmetric-output channel. For channels with small capacity, receivers needs to collects many channel outputs to recover information bits. Since a collected channel output yields a check node in the decoding Tanner graph, the channel with small capacity leads to large decoding complexity. In this paper, we introduce a novel fountain coding s… ▽ More We study fountain codes transmitted over the binary-input symmetric-output channel. For channels with small capacity, receivers needs to collects many channel outputs to recover information bits. Since a collected channel output yields a check node in the decoding Tanner graph, the channel with small capacity leads to large decoding complexity. In this paper, we introduce a novel fountain coding scheme with non-binary LDPC codes. The decoding complexity of the proposed fountain code does not depend on the channel. Numerical experiments show that the proposed codes exhibit better performance than conventional fountain codes, especially for small number of information bits. △ Less

Submitted 11 July, 2010; v1 submitted 5 July, 2010; originally announced July 2010.

Comments: To appear in Proc. 6th International Symposium on Turbo Codes and Iterative Information Processing

Multiplicatively Repeated Non-Binary LDPC Codes

Authors: Kenta Kasai, David Declercq, Charly Poulliat, Kohichi Sakaniwa

Abstract: We propose non-binary LDPC codes concatenated with multiplicative repetition codes. By multiplicatively repeating the (2,3)-regular non-binary LDPC mother code of rate 1/3, we construct rate-compatible codes of lower rates 1/6, 1/9, 1/12,... Surprisingly, such simple low-rate non-binary LDPC codes outperform the best low-rate binary LDPC codes so far. Moreover, we propose the decoding algorithm fo… ▽ More We propose non-binary LDPC codes concatenated with multiplicative repetition codes. By multiplicatively repeating the (2,3)-regular non-binary LDPC mother code of rate 1/3, we construct rate-compatible codes of lower rates 1/6, 1/9, 1/12,... Surprisingly, such simple low-rate non-binary LDPC codes outperform the best low-rate binary LDPC codes so far. Moreover, we propose the decoding algorithm for the proposed codes, which can be decoded with almost the same computational complexity as that of the mother code. △ Less

Submitted 13 July, 2011; v1 submitted 29 April, 2010; originally announced April 2010.

Comments: To appear in IEEE Transactions on Information Theory

Analytical Solution of Covariance Evolution for Regular LDPC Codes

Authors: Takayuki Nozaki, Kenta Kasai, Kohichi Sakaniwa

Abstract: 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 numeric… ▽ More 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. △ Less

Submitted 19 January, 2009; originally announced January 2009.

Comments: 5 pages, 3 figures, submitted to ISIT2009

Finite-Length Analysis of Irregular Expurgated LDPC Codes under Finite Number of Iterations

Authors: Ryuhei Mori, Toshiyuki Tanaka, Kenta Kasai, Kohichi Sakaniwa

Abstract: Communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding is considered. The average bit error probability of an irregular LDPC code ensemble after a fixed number of iterations converges to a limit, which is calculated via density evolution, as the blocklength $n$ tends to infinity. The difference between the bit error pr… ▽ More Communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) codes and belief propagation (BP) decoding is considered. The average bit error probability of an irregular LDPC code ensemble after a fixed number of iterations converges to a limit, which is calculated via density evolution, as the blocklength $n$ tends to infinity. The difference between the bit error probability with blocklength $n$ and the large-blocklength limit behaves asymptotically like $α/n$, where the coefficient $α$ depends on the ensemble, the number of iterations and the erasure probability of the BEC\null. In [1], $α$ is calculated for regular ensembles. In this paper, $α$ for irregular expurgated ensembles is derived. It is demonstrated that convergence of numerical estimates of $α$ to the analytic result is significantly fast for irregular unexpurgated ensembles. △ Less

Submitted 23 May, 2009; v1 submitted 15 January, 2009; originally announced January 2009.

Comments: 5 pages, 3 figures, submitted to ISIT2009; revised

The Asymptotic Bit Error Probability of LDPC Codes for the Binary Erasure Channel with Finite Iteration Number

Authors: Ryuhei Mori, Kenta Kasai, Tomoharu Shibuya, Kohichi Sakaniwa

Abstract: We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. The bit error probability for infinite block length is known by density evolution and it is well known that a difference between the bit error probability at finite iteration number for finite block length $n$ and for infinite block length is asymptotic… ▽ More We consider communication over the binary erasure channel (BEC) using low-density parity-check (LDPC) code and belief propagation (BP) decoding. The bit error probability for infinite block length is known by density evolution and it is well known that a difference between the bit error probability at finite iteration number for finite block length $n$ and for infinite block length is asymptotically $α/n$, where $α$ is a specific constant depending on the degree distribution, the iteration number and the erasure probability. Our main result is to derive an efficient algorithm for calculating $α$ for regular ensembles. The approximation using $α$ is accurate for $(2,r)$-regular ensembles even in small block length. △ Less

Submitted 23 January, 2008; v1 submitted 7 January, 2008; originally announced January 2008.

Comments: 5 pages, 6 figures, correcting errors in Theorem 1 and poor English