Obviousness

An obviousness analysis under 35 U.S.C. § 103 for US Patent 7,627,805 requires identifying combinations of prior art that would have made the claimed invention obvious to a person having ordinary skill in the art (PHOSITA) at the time of the invention (priority date of June 8, 2005). The analysis will focus on the independent claims (Claims 1, 11, and 17) and utilize the prior art references cited in the patent itself, inferring their technical teachings from their titles and general knowledge in the field.

The problem addressed by US7627805 is the need for efficient LDPC code implementations in communication systems to support high data rates without increasing hardware complexity. The patent's solution involves a structured LDPC code using a "mother code parity check matrix" built from "m-by-m square matrices with cyclic structure," and a "macro matrix" that represents the non-zero sub-matrices.

Relevant Prior Art References and Inferred Teachings:

The following references are highlighted from the "Prior Art" section of US7627805B2:

1. Richardson et al., "Efficient encoding of low density parity check codes," Feb. 2001, IEEE Trans. on Info. theory, vol. 47, No. 2, p. 638-656.

   • Inferred Teaching: Given its title, this seminal work would describe methods for constructing and encoding LDPC codes efficiently. A PHOSITA would understand that this typically includes structured LDPC codes, such as Quasi-Cyclic (QC-LDPC) codes, which employ parity-check matrices composed of circulant permutation matrices (a form of cyclic square sub-matrices). The overall structure of such a matrix is usually defined by a smaller "base matrix" or "macro matrix" indicating the positions of these circulants. The paper would also likely address techniques to improve code performance, such as avoiding short cycles (e.g., length-4 cycles).

2. US7162684B2 (Texas Instruments Incorporated), "Efficient encoder for low-density-parity-check codes," issued 2007-01-09 (priority 2003-01-27).

   • Inferred Teaching: The title directly suggests this patent teaches specific apparatus and methods for efficiently encoding LDPC codes. For a major semiconductor company like Texas Instruments, efficiency implies hardware-friendly designs, which would likely involve structured matrices and optimized encoding algorithms.

3. US7139959B2 (Texas Instruments Incorporated), "Layered low density parity check decoding for digital communications," issued 2006-11-21 (priority 2003-03-24).

   • Inferred Teaching: This patent, while focused on decoding, would inherently discuss LDPC code structures that are conducive to efficient (e.g., layered) decoding. Often, the same structured matrices beneficial for efficient encoding are also advantageous for efficient decoding.

Obviousness Combination and Rationale:

Combination: Richardson et al. (2001) in view of US7162684B2 and US7139959B2, combined with the general knowledge of a PHOSITA.

Motivation for Combination:
A PHOSITA, aiming to design a hardware-efficient LDPC encoder for high-data-rate communication (as noted in the background of US7627805), would be motivated to combine the teachings of these references. Richardson et al. directly addresses "efficient encoding" methods, which are known to involve structured code constructions like QC-LDPC codes. US7162684B2 further reinforces the need and provides techniques for "efficient encoders," likely including hardware-optimized structures. US7139959B2 provides insights into structures that also enable efficient decoding, making a complete communication system practical. The overarching motivation is to develop robust, high-performance, and hardware-implementable LDPC coding solutions for modern communication standards.

Analysis of Independent Claims:

• Claim 1 (Method of Coding Data): This claim describes generating a codeword from a mother code parity check matrix and a macro matrix, where the mother code matrix is a (j*m)-by-(k*m) matrix with m-by-m cyclic sub-matrices, and the macro matrix is j-by-k and represents the non-zero sub-matrices.

  • Obviousness: Richardson et al. (2001), with its focus on "efficient encoding," would have motivated a PHOSITA to use structured LDPC codes, such as QC-LDPC codes. QC-LDPC codes are fundamentally defined by a parity-check matrix (the "mother code parity check matrix") constructed from an arrangement of circulant permutation matrices (which are "m-by-m square matrices with cyclic structure"). The arrangement of these circulants is precisely specified by a smaller "base matrix" or "macro matrix" (a "j-by-k matrix" whose elements "represent nonzero sub-matrices"). Therefore, the core structural elements and the method of generating a codeword using them would have been well-known and obvious to a PHOSITA.

• Claim 11 (LDPC Encoder Apparatus): This claim describes an LDPC encoder comprising "means for generating" a codeword using the structured matrices of Claim 1.

  • Obviousness: Given the teachings of Richardson et al. (2001) and US7162684B2 on "efficient encoders" for LDPC codes, implementing such an encoder in hardware using the known QC-LDPC structure would be an obvious engineering task for a PHOSITA. The use of cyclic sub-matrices is specifically known to simplify hardware implementation through shift-registers. The "means for generating" elements are functional recitations of components that a PHOSITA would readily design based on the established coding methods.

• Claim 17 (Communications System): This claim combines the LDPC encoder of Claim 11 with an "LDPC iterative decoder."

  • Obviousness: It is a fundamental principle of communication systems to pair an encoder with a corresponding decoder. The motivation to integrate an efficient LDPC encoder (as taught by Richardson et al. and US7162684B2) with an efficient LDPC decoder is inherent in designing a functional and high-performance communication link. US7139959B2 explicitly teaches "layered low density parity check decoding," providing a known efficient decoding component to complete the system. Thus, a PHOSITA would find it obvious to combine these known efficient components into a communication system.

Consideration of Dependent Claims:

Many dependent claims of US7627805 describe further optimizations and design choices that would have been obvious to a PHOSITA applying the principles of the cited prior art:

• Rate compatibility (Claim 6): Techniques for achieving rate compatibility (e.g., through puncturing, extension, or row/column operations on the parity-check matrix) were known in LDPC code design. A PHOSITA would be motivated to adapt such methods to structured matrices to offer flexible data rates.
• Avoiding bi-diagonal sub-matrices (Claim 7) and length-four cycles (Claim 9): These are well-established criteria for designing high-performance LDPC codes. Richardson et al. (2001) and other literature commonly discuss avoiding short cycles to reduce error floors. The avoidance of specific matrix patterns like bi-diagonal sub-matrices for hardware benefits (e.g., simplified routing and parallelization) is a known engineering design consideration for a PHOSITA.
• Column grouping (Claim 8): Grouping columns based on their degree distribution is a technique used to optimize hardware resources (e.g., memory, routing) in LDPC decoders and encoders. This would be an obvious design choice for a PHOSITA aiming for "efficient" hardware.
• Application to IEEE 802.11n MIMO (Claim 10): Applying known efficient coding schemes, such as structured LDPC codes, to emerging communication standards like IEEE 802.11n MIMO for performance enhancement would be a routine engineering endeavor.

In conclusion, the combination of the teachings related to "efficient encoding" of LDPC codes from Richardson et al. (2001) and US7162684B2, coupled with general PHOSITA knowledge of structured LDPC codes (e.g., QC-LDPC codes with cyclic sub-matrices and macro matrices) and efficient decoding techniques from US7139959B2, would render the independent claims of US7627805 obvious. The motivation for combining these elements stems from the well-understood goal of achieving high-performance, hardware-efficient LDPC coding solutions for modern communication systems.