LDPC Codes for 2D Arrays | EPFL Graph Search

Binary codes over 2D arrays are very useful in data storage, where each array column represents a storage device or unit that may suffer failure. In this paper, we propose a new framework for probabilistic construction of codes on 2D arrays. Instead of a pure combinatorial erasure model used in traditional array codes, we propose a mixed combinatorial-probabilistic model of limiting the number of column failures, and assuming a binary erasure channel in each failing column. For this model, we give code constructions and detailed analysis that allow sustaining a large number of column failures with graceful degradation in the fraction of erasures correctable in failing columns. Another advantage of the new framework is that it uses low-complexity iterative decoding. The key component in the analysis of the new codes is to analyze the decoding graphs induced by the failed columns, and infer the decoding performance as a function of the code design parameters, as well as the array size and failure parameters. A particularly interesting class of codes, called probabilistically maximum distance separable (MDS) array codes, gives fault-tolerance that is equivalent to traditional MDS array codes. The results also include a proof that the 2D codes outperform standard 1D low-density parity-check codes.

Array-Code Ensembles -or- Two-Dimensional LDPC Codes

Yuval Cassuto, Mohammad Amin Shokrollahi

Probabilistic construction of codes on two-dimensional arrays is proposed and analyzed. Instead of a pure combinatorial erasure model used in traditional array codes, we propose a mixed combinatorial-probabilistic model of limiting the number of column failures, with assuming a binary erasure channel in each failing column. In addition, motivated by practical applications, we maintain an array with a fixed number of columns, while allowing the column size to grow to infinity. As a result, we obtain a framework that allows developing powerful constructions and analysis techniques previously only applicable in the theory of iteratively decoded one-dimensional low-density parity-check codes. The new array-code ensembles are shown to approach the performance of traditional MDS codes, with a simple decoder that offers better scalability in the number of column failures.

IEEE Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

Asymptotic and finite-length analysis of low-density parity-check codes

Changyan Di

This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.

EPFL2004

Prediction of Survival and Risk Assessment Using Joint Analysis of Microarray Gene Expression Data

Haleh Yasrebi

Gene expression profiles have been widely used in molecular classification, diagnosis and prediction, particularly in the area of oncology where accurate and early diagnosis is needed for appropriate treatment. Avoiding under-/over-treatment when it is not necessary can extend a patient's survival and prevent disease recurrence. These high-throughput assay technologies have generated terabytes of data exploited extensively to provide insights on cancer biology and the underlying mechanism of disease progression. The ultimate goal is to identify possibly tailored treatment and therapy for personalized medicine. Analysis of microarray data is constrained by the following characteristics: (i) noisy due to missing or erroneous values; (ii) high dimensional due to a large number of genes versus a few number of samples in which their expression levels are measured; (iii) costly due to expensive microarray experiments. Abundant microarray gene expression data should be processed by appropriate computational and statistical learning methodologies such as machine learning techniques. These methods are robust to noisy data and have a great capacity to analyze high dimensional data. Their computational power is nevertheless limited to sample size based on which these methods are built. These algorithms have been widely applied to microarray gene expression data to identify a set of genes known as a gene signature whose expressions are highly correlated to a target value or outcome such as disease status, tumor subtype, a patient's survival time, risk of mortality or cancer relapse. Prediction of survival time and a patient's risk which is unknown at diagnosis presents a more challenging task for machine learning methods than tumor subtype or disease classification, which is already established by oncologists. The properties of microarray data cited above, the limitation of the number of samples in cancer patients and dependency of the machine learning methods' performance on sample size justify joint analysis of microarray data to increase the number of samples. We applied joint analysis methods to breast and lung cancer data sets to improve survival prediction and risk assessment. In overall, no significant improvement or deterioration of the performance accuracy was obtained with joint analysis. However, increasing sample size helped to identify robust or stable gene signatures predictive of survival time and risk assessment. Our achievements and learned-lessons from joint analysis of microarray gene expression data can be used as a guideline for future research studies in classification and prediction.