Shortened Array Codes of Large Girth

Abstract

One approach to designing structured low-density parity-check (LDPC) codes with large girth is to shorten codes with small girth in such a manner that the deleted columns of the parity-check matrix contain all the variables involved in short cycles. This approach is especially effective if the parity-check matrix of a code is a matrix composed of blocks of circulant permutation matrices, as is the case for the class of codes known as array codes. We show how to shorten array codes by deleting certain columns of their parity-check matrices so as to increase their girth. The shortening approach is based on the observation that for array codes, and in fact for a slightly more general class of LDPC codes, the cycles in the corresponding Tanner graph are governed by certain homogeneous linear equations with integer coefficients. Consequently, we can selectively eliminate cycles from an array code by only retaining those columns from the parity-check matrix of the original code that are indexed by integer sequences that do not contain solutions to the equations governing those cycles. We provide Ramsey-theoretic estimates for the maximum number of columns that can be retained from the original parity-check matrix with the property that the sequence of their indices avoid solutions to various types of cycle-governing equations. This translates to estimates of the rate penalty incurred in shortening a code to eliminate cycles. Simulation results show that for the codes considered, shortening them to increase the girth can lead to significant gains in signal-to-noise ratio in the case of communication over an additive white Gaussian noise channel.

16 pages; 8 figures; to appear in IEEE Transactions on Information Theory, Aug 2006

Cited by in corpus (12)

• Searching for Voltage Graph-Based LDPC Tailbiting Codes with Large Girth
• Scalable constructions of fractional repetition codes in distributed storage systems
• The Trapping Redundancy of Linear Block Codes
• Design of Multiple-Edge Protographs for QC LDPC Codes Avoiding Short Inevitable Cycles
• Array Convolutional Low-Density Parity-Check Codes
• Decomposition Methods for Large Scale LP Decoding
• Quasi-cyclic LDPC codes with high girth
• Structured LDPC Codes from Permutation Matrices Free of Small Trapping Sets
• LDPC Codes from Latin Squares Free of Small Trapping Sets
• Absorbing Set Spectrum Approach for Practical Code Design
• The Cycle Consistency Matrix Approach to Absorbing Sets in Separable Circulant-Based LDPC Codes
• Joint Shortening and Puncturing Optimization for Structured LDPC Codes