In the past decade, there has been tremendous amount of research on the analysis and design of the Low-Density Parity-Check (LDPC) codes with belief propagation decoding over different types of Binary-Input Output-Symmetric Memoryless (BIOSM) channels. However, with the exception of the Binary Erasure Channel (BEC), analytical results on LDPC codes over such channels are limited and most results are based on numerical methods and optimization. In particular, systematic design of provably capacity achieving sequences of LDPC code ensembles over general class of BIOSM channels has remained a fundamental open problem. Such sequences have been designed only for the binary erasure channel (BEC). In this paper, we first prove some novel analytical properties of the LDPC code ensembles over BIOSM channels. In particular, we prove a result that generalizes the previously known stability condition over symmetric channels. This suggests that a modified version of the flatness condition, a property which has been shown to be critical for capacity achieving sequences over the BEC, can be used to devise capacity achieving sequences for general class of BIOSM channels. Based on this assumption, we propose a method which could result in the systematic design of such sequences over BIOSM channels. Numerical evidence is promising and provides a consistent convergence behavior to capacity over the considered BIOSM channels as the average check node degree increases.In the past decade, there has been tremendous amount of research on the analysis and design of the Low-Density Parity-Check (LDPC) codes with belief propagation decoding over different types of Binary-Input Output-Symmetric Memoryless (BIOSM) channels. However, with the exception of the Binary Erasure Channel (BEC), analytical results on LDPC codes over such channels are limited and most results are based on numerical methods and optimization. In particular, systematic design of provably capacity achieving sequences of LDPC code ensembles over general class of BIOSM channels has remained a fundamental open problem. Such sequences have been designed only for the binary erasure channel (BEC). In this paper, we first prove some novel analytical properties of the LDPC code ensembles over BIOSM channels. In particular, we prove a result that generalizes the previously known stability condition over symmetric channels. This suggests that a modified version of the flatness condition, a property which has been shown to be critical for capacity achieving sequences over the BEC, can be used to devise capacity achieving sequences for general class of BIOSM channels. Based on this assumption, we propose a method which could result in the systematic design of such sequences over BIOSM channels. Numerical evidence is promising and provides a consistent convergence behavior to capacity over the considered BIOSM channels as the average check node degree increases.

IEEE Information Theory Workshop (ITW)Jun 1, 20090 citations

Error detecting codes for the q-ary symmetric channel

Series on coding theory and cryptologyApr 1, 20070 citations

The decoding of binary quasi-cyclic codes

P. Heijnen, Henk C. A. van Tilborg

Jan 1, 19984 citations

Using concatenated algebraic geometry codes in channel polarization

Abdulla Eid, Iwan Duursma

Polar codes were introduced by Arikan in 2008 and are the first family of error-correcting codes achieving the symmetric capacity of an arbitrary binary-input discrete memoryless channel under low complexity encoding and using an efficient successive cancellation decoding strategy. Recently, non-binary polar codes have been studied, in which one can use different algebraic geometry codes to achieve better error decoding probability. In this paper, we study the performance of binary polar codes that are obtained from non-binary algebraic geometry codes using concatenation. For binary polar codes (i.e. binary kernels) of a given length $n$ , we compare numerically the use of short algebraic geometry codes over large fields versus long algebraic geometry codes over small fields. We find that for each $n$ there is an optimal choice. For binary kernels of size up to $n \leq 1,800$ a concatenated Reed-Solomon code outperforms other choices. For larger kernel sizes concatenated Hermitian codes or Suzuki codes will do better.Polar codes were introduced by Arikan in 2008 and are the first family of error-correcting codes achieving the symmetric capacity of an arbitrary binary-input discrete memoryless channel under low complexity encoding and using an efficient successive cancellation decoding strategy. Recently, non-binary polar codes have been studied, in which one can use different algebraic geometry codes to achieve better error decoding probability. In this paper, we study the performance of binary polar codes that are obtained from non-binary algebraic geometry codes using concatenation. For binary polar codes (i.e. binary kernels) of a given length $n$, we compare numerically the use of short algebraic geometry codes over large fields versus long algebraic geometry codes over small fields. We find that for each $n$ there is an optimal choice. For binary kernels of size up to $n \leq 1,800$ a concatenated Reed-Solomon code outperforms other choices. For larger kernel sizes concatenated Hermitian codes or Suzuki codes will do better.

arXiv:1310.7159Oct 27, 20133 citations

Hierarchical Polar Coding for Achieving Secrecy Over State-Dependent Wiretap Channels Without Any Instantaneous CSI

Hongbo Si, O. Ozan Koyluoglu, Sriram Vishwanath

This paper presents a polar coding scheme to achieve secrecy in block fading binary symmetric wiretap channels without the knowledge of instantaneous channel state information (CSI) at the transmitter. For this model, a coding scheme that hierarchically utilizes polar codes is presented. In particular, on the polarization of different binary symmetric channels over different fading blocks, each channel use is modeled as an appropriate binary erasure channel over fading blocks. Polar codes are constructed for both coding over channel uses for each fading block and coding over fading blocks for certain channel uses. In order to guarantee security, random bits are introduced at appropriate places to exhaust the observations of the eavesdropper. It is shown that this coding scheme, without instantaneous CSI at the transmitter, is secrecy capacity achieving for the simultaneous fading scenario. For the independent fading case, the capacity is achieved when the fading realizations for the eavesdropper channel are always degraded with respect to the receiver. For the remaining cases, the gap between lower and upper bounds is analyzed. Remarkably, for the scenarios where the secrecy capacity is achieved, the results imply that the instantaneous CSI does not increase the secrecy capacity.This paper presents a polar coding scheme to achieve secrecy in block fading binary symmetric wiretap channels without the knowledge of instantaneous channel state information (CSI) at the transmitter. For this model, a coding scheme that hierarchically utilizes polar codes is presented. In particular, on the polarization of different binary symmetric channels over different fading blocks, each channel use is modeled as an appropriate binary erasure channel over fading blocks. Polar codes are constructed for both coding over channel uses for each fading block and coding over fading blocks for certain channel uses. In order to guarantee security, random bits are introduced at appropriate places to exhaust the observations of the eavesdropper. It is shown that this coding scheme, without instantaneous CSI at the transmitter, is secrecy capacity achieving for the simultaneous fading scenario. For the independent fading case, the capacity is achieved when the fading realizations for the eavesdropper channel are always degraded with respect to the receiver. For the remaining cases, the gap between lower and upper bounds is analyzed. Remarkably, for the scenarios where the secrecy capacity is achieved, the results imply that the instantaneous CSI does not increase the secrecy capacity.

IEEE Transactions on CommunicationsJul 18, 201610 citations

Optimal binary codes and binary construction of quantum codes

Weiliang, Wang, Yangyu +3 more

Frontiers of Computer ScienceJan 1, 20141 citation

n

, we compare numerically the use of short algebraic geometry codes over large fields versus long algebraic geometry codes over small fields. We find that for each

n

there is an optimal choice. For binary kernels of size up to

n \leq 1,800

a concatenated Reed-Solomon code outperforms other choices. For larger kernel sizes concatenated Hermitian codes or Suzuki codes will do better.