Low density parity check (LDPC) code

What is this patent about?

’980 is related to the field of forward error correction, specifically focusing on the design and implementation of Low Density Parity Check (LDPC) codes. In modern communication systems, these codes are essential for maintaining data integrity over noisy channels by adding redundant parity bits to an information stream. The technical challenge addressed here is the trade-off between high coding gain and the computational complexity required for encoding and decoding, particularly when trying to support multiple data rates and block sizes without overhaul of the underlying hardware circuitry.

The underlying idea behind ’980 is the use of a structured parity check matrix that is built by expanding a smaller base matrix using specific permutation rules. Instead of using a completely random or dense matrix, the invention replaces each non-zero entry in a base matrix with a circularly shifted identity matrix of a specific size. This approach allows the system to scale to different block lengths by simply adjusting the expansion factor and shift amounts, significantly reducing the physical wiring and memory requirements in the hardware while maintaining a structure that supports efficient, recursive encoding.

The claims of ’980 focus on a specific expanded parity check matrix defined by a precise grid of shift values, where the integer -1 represents an all-zero matrix and other integers represent circularly right-shifted identity matrices. The independent claims cover both the methods and the physical apparatus—such as encoders, decoders, and transceivers—that apply this specific matrix configuration to process data. The matrix is characterized by an expansion factor of 81, resulting in sub-matrices of 81x81, which are used to either generate parity bits during encoding or recover original information during decoding.

In practice, the invention works by partitioning the parity check matrix into a data portion and a parity portion. The parity portion is designed with a dual diagonal or lower triangular structure, which is the key mechanism that enables simple recursive processing. By solving for parity bits one by one or in small groups, the encoder avoids the heavy computational burden of full matrix inversion. This specific matrix geometry ensures that the row and column weights are optimized to provide robust error correction performance while keeping the hardware implementation semi-parallel and power-efficient.

This approach differs from prior solutions by providing a highly irregular data part combined with a structured parity part to maximize coding gain without sacrificing speed. While traditional LDPC codes often struggled with high encoding complexity or rigid block sizes, the ’980 patent utilizes a shift-based expansion technique that allows a single hardware architecture to handle various code rates. By carefully selecting the shift values and the matrix weight distribution, the invention achieves a balance where the inverse of the parity portion remains sparse, ensuring that the final communication device is both flexible and high-performing.