We consider transmission over a wiretap channel where both the main channel and the wiretapper's channel are binary erasure channels (BEC). A code construction method is proposed using two edge-type low-density parity-check (LDPC) codes based on the coset encoding scheme. Using a single edge-type LDPC ensemble with a given threshold over the BEC, we give a construction for a two edge-type LDPC ensemble with the same threshold. If the given single edge-type LDPC ensemble has degree two variable nodes, our construction gives rise to degree one variable nodes in the code used over the main channel. This results in zero threshold over the main channel. In order to circumvent this problem, the degree distribution of the two edge-type LDPC ensemble is numerically optimized. We find that the resulting ensembles are able to perform close to the boundary of the rate-equivocation region of the wiretap channel. Further, a method to compute the ensemble average equivocation of two edge-type LDPC ensembles is provided by generalizing a recently published approach to measure the equivocation of single edge-type ensembles for transmission over the BEC in the point-to-point setting. From this analysis, we find that relatively simple constructions give very good secrecy performance.

We consider the symmetric discrete memoryless relay channel with orthogonal receiver components and show that polar codes are suitable for decode-and-forward and compress-and-forward relaying. In the first case we prove that polar codes are capacity achieving for the physically degraded relay channel; for stochastically degraded relay channels our construction provides an achievable rate. In the second case we construct sequences of polar codes that achieve the compress-and-forward rate by nesting polar codes for source compression into polar codes for channel coding. In both cases our constructions inherit most of the properties of polar codes. In particular, the encoding and decoding algorithms and the bound on the block error probability O(2-Nβ) which holds for any 0<;β<;1/2.

We consider transmission over a wiretap channel where both the main channel and the wiretapper's channel are Binary Erasure Channels (BEC). We use regular convolutional LDPC ensembles, introduced by Felström and Zigangirov, together with Wyner's coset encoding scheme. We show that such a construction achieves the whole rate-equivocation region of the BEC wiretap channel. This result is based on the recent observation by Kudekar, Richardson, and Urbanke who proved that convolutional LDPC ensembles exhibit a “threshold saturation” phenomenon which converts the MAP threshold into the BP threshold for transmission over the BEC. Although our present result is less general (since we only consider the BEC) than the elegant code constructions based on polar codes which were recently introduced by several research groups, we see two potential advantages which we believe makes our construction worth considering. First, the proposed codes have a significantly better performance already for moderate lengths. Second, and perhaps more importantly, the proposed construction has the potential of being universal. More precisely, the phenomenon of spatial coupling has been observed empirically to hold for general binary memoryless symmetric channels as well. Hence, we conjecture that our construction is a universal rate-equivocation achieving construction when the main channel and wiretapper's channel are binary memoryless symmetric channels, and the wiretapper's channel is degraded with respect to the main channel.

In this paper, the transmission over the binary erasure channel (BEC) using non-binary LDPC (NBLDPC) codes is considered. The concept of peeling decoder and stopping sets is generalized to NBLDPC codes. Using these generalizations, a combinatorial characterization of decoding failures of NBLDPC codes is given, under assumption that the Belief Propagation (BP) decoder is used. Then, the residual ensemble of codes resulted by the BP decoder is defined and the design rate and the expectation of total number of codewords of the residual ensemble are computed. The decoding failure criterion combined with the density evolution analysis helps us to compute the asymptotic residual degree distribution for NBLDPC codes. Our approach to compute the residual degree distribution on the check node side is not efficient as it is based on enumeration of all the possible connections on the check node side which satisfy the decoding failure criterion. So, the computation of the asymptotic check node side residual degree distribution and further part of our analysis is performed for NBLDPC codes over GF2mwithm= 2 . In order to show that asymptotically almost every code in such LDPC ensemble has a rate equal to the design rate, we generalize the argument of the Maxwell construction to NBLDPC codes, defined over GF22. It is also observed that, like in the binary setting, the Maxwell construction, relating the performance of MAP and BP decoding holds in this setting.

We consider lower bounds on the rate-distortion performance for the binary erasure source(BES) introduced by Martinian and Yedidia, using sparse graph codes for compression. Our approach follows that of Kudekar and Urbanke, where lower bounds on the rate distortion performance of low-density generator matrix (LDGM) codes for the binary symmetric source(BSS) are derived. They introduced two methods for deriving lower bounds, namely the counting method and the test channel method. Based on numerical results they observed that the two methods lead to the same bound. We generalize these two methods for the BES and prove that indeed both methods lead to identical rate-distortion bounds for the BES and hence, also forthe BSS.

We consider the Binary Erasure Source (BES) introduced by Martinian and Yedidia. Based on the technique introduced by Martinian and Wainwright, we upper bound the rate-distortion performance of the check regular Poisson LDGM ensemble and the compound LDGM-LDPC ensemble for the BES. We also show that there exist compound LDGM-LDPC codes, with degrees independent of the block-length, which can achieve any given point on the Shannon rate-distortion curve of the BES.

This paper is the first part of an investigation if the capacity of a binary-input memoryless symmetric channel under ML decoding can be achieved asymptotically by using non-binary LDPC codes. We consider (l, r)-regular LDPC codes both over finite fields and over the general linear group and compute their asymptotic binary weight distributions in the limit of large blocklength and of large alphabet size. A surprising fact, the average binary weight distributions that we obtain do not tend to the binomial one for values of normalized binary weights ¿ smaller than 1-2-l/r. However, it does not mean that non-binary codes do not achieve the capacity asymptotically, but rather that there exists some exponentially small fraction of codes in the ensemble, which contains an exponentially large number of codewords of poor weight. The justification of this fact is beyond the scope of this paper and will be given in.

We consider transmission over the binary erasure channel (BEC) using non-binary LDPC codes. We generalize the concept of stopping sets to non-binary LDPC codes. We give a combinatorial characterization of decoding failures for non-binary LDPC codes decoded via Belief Propagation (BP). Using the density evolution analysis, we compute the asymptotic residual degree distribution for non-binary LDPC codes. In order to show that asymptotically almost every code in the non-binary LDPC ensemble has a rate equal to the design rate, we generalize the arguments of Measson, Montanari, and Urbanke to the non-binary setting. This generalization enables us to compute the conditional entropy of non-binary LDPC codes. We observe that the Maxwell construction of Measson, Montanari, and Urbanke relating the performance of MAP and BP decoding, holds in the setting of non-binary LDPC codes.

The extended BP (EBP) generalized EXIT (GEXIT) function introduced in C. Measson et al. (2005) plays a fundamental role in the asymptotic analysis of sparse graph codes. For transmission over the binary erasure channel (BEC) the analytic properties of the EBP GEXIT function are relatively simple and well understood. The general case is much harder and even the existence of the curve is not known in general. We introduce some tools from non-linear analysis which can be useful to prove the existence of EXIT like curves in some cases. The main tool is the Krasnoselskii-Rabinowitz (KR) bifurcation theorem.

We estimate the variance of weight distribution of regular LDPC ensembles. Using this estimate and the second moment method we obtain bounds on the probability that a randomly chosen code from regular LDPC ensemble has its weight distribution close to the ensemble average. We are able to show that a large fraction of total number of codes have their weight distribution close to the average