Low density parity check (LDPC) code

What is this patent about?

’829 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 digital communication, these codes are essential for maintaining data integrity across noisy channels by adding redundant parity bits. The technical challenge addressed here is the need for a flexible coding scheme that supports various block sizes and high data rates without requiring complex hardware re-wiring or computationally expensive encoding processes.

The underlying idea behind ’829 is the creation of a structured parity check matrix that balances high coding gain with hardware efficiency. By partitioning the matrix into a data portion and a parity portion, the invention utilizes a specific arrangement of sub-matrices—specifically shifted identity matrices—to allow for a recursive encoding algorithm. This approach avoids the heavy computational burden of full matrix inversion, instead enabling parity bits to be calculated through simple shift-and-sum operations that are easily mapped to parallel hardware architectures.

The claims of ’829 focus on a specific expanded parity check matrix designed for a code length of 1944 bits, utilizing an expansion factor of 81. The independent claims define the precise spatial arrangement of non-zero elements within an 8x24 base matrix structure, where each integer represents a circularly right-shifted identity matrix and each -1 represents an all-zero matrix. This specific configuration is optimized to ensure a minimum column weight of 3 in the data portion while maintaining a sparse, lower-triangular-like structure in the parity portion.

In practice, the invention works by taking a block of input data and applying the expanded matrix to generate a systematic codeword. The architecture is particularly effective because it supports multiple code rates, such as R=2/3, by scaling a base matrix through an expansion factor (L). For a code length of 1944, the system uses 81x81 sub-matrices, allowing the encoder to process large blocks of data while maintaining the low-density characteristics that make LDPC decoding efficient at the receiver.

This approach differentiates itself from prior LDPC implementations by optimizing the row weight distribution and ensuring the parity portion of the matrix is inherently structured for simple recursion. Unlike traditional random LDPC codes that require massive look-up tables or complex interconnects, the ’829 design uses a dual-diagonal-like parity structure that simplifies the hardware logic. This allows for high-throughput communication systems that can adapt to different block lengths without sacrificing the error-correction performance required for high-speed data transmission.