# US 10,372,530 B1 · Generic encoder for low-density parity-check (LDPC) codes > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,530 B1 - Document ID: US10372530B1 - Status: Granted - Kind: B1 - Application number: 15/606,720 - Filed: 2017-05-26 - Granted: 2019-08-06 - Earliest claimed: 2007-08-17 - Assignees: Marvell International Ltd. - Applicants: Marvell International Ltd. - Inventors: Kiran Gunnam; Nedeljko Varnica - Web page: https://patentgrep.com/patent/US10372530B1 ## CPC - G06F 11/1032: {Simple parity} - H03M 13/1102: {Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes} - H03M 13/1148: {Structural properties of the code parity-check or generator matrix} - H03M 13/116: {Quasi-cyclic LDPC [QC-LDPC] codes, i.e. the parity-check matrix being composed of permutation or circulant sub-matrices} - H03M 13/118: {Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure (H03M13/1165 takes precedence)} - H03M 13/1188: {wherein in the part with the double-diagonal at least one column has an odd column weight equal or greater than three} - H03M 13/3776: {using a re-encoding step during the decoding process} - H03M 13/458: {by updating bit probabilities or hard decisions in an iterative fashion for convergence to a final decoding result} - H03M 13/616: {Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations} - H03M 13/6527: {IEEE 802.11 [WLAN]} - H03M 13/6544: {IEEE 802.16 (WIMAX and broadband wireless access)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract Systems and methods are provided for encoding data based on an LDPC code using various inversion mechanisms to obtain parity bits. In some embodiments, an LDPC encoder may compute parity bits using a speculative recursion and correction mechanism. In these embodiments, the LDPC encoder may initiate a recursion using at least one speculative value in place of the actual value for a parity component. The speculative values may then be corrected using a correction factor. In other embodiments, an LDPC encoder is provided that can perform a blockwise inversion mechanism. This mechanism may be used on LDPC codes with parity check matrices having a parity portion composed partially of a large triangular matrix. In still other embodiments, a generic LDPC encoder is provided. The generic LDPC encoder can implement a variety of different encoding techniques, such as different inversion mechanisms, and may be processor-based or finite state machine-based. ## Claims ### Claim 1 A method for generating parity symbols for a low density parity check (LDPC) code having a parity check matrix comprising a data portion and a parity portion, the method comprising: obtaining an intermediate vector, using control circuitry, based at least in part on a vector of data symbols with the data portion of the parity check matrix; determining an initial parity symbol based on the parity portion of the parity check matrix and a symbol from the intermediate vector; and determining one or more additional parity symbols based, at least in part, on the initial parity symbol and the intermediate vector. ### Claim 2 (depends on 1) The method of claim 1 wherein the determining an initial parity symbol based on the parity portion of the parity check matrix and a symbol from the intermediate vector comprises: determining the initial parity symbol based on the parity portion of the parity check matrix and a symbol at substantially one end of the intermediate vector. ### Claim 3 (depends on 2) The method of claim 2, wherein the determining one or more additional parity symbols comprises: initiating a recursion to obtain the one or more additional parity symbols. ### Claim 4 (depends on 3) The method of claim 3, further comprising: terminating the recursion in response to determining that a portion of the parity symbols up to a second end of the intermediate vector have been obtained, wherein the second end is substantially opposite to the one end. ### Claim 5 (depends on 3) The method of claim 3, comprising: initiating a first recursion to obtain the one or more additional parity symbols; and initiating a second recursion from a second end of the intermediate vector to obtain the one or more additional parity symbols, wherein the second end is substantially opposite to the one end. ### Claim 6 (depends on 1) The method of claim 1, further comprising configuring the parity portion of the parity check matrix as a dual-diagonal matrix. ### Claim 7 (depends on 1) The method of claim 1, comprising: determining a first initial parity symbol based on the parity portion of the parity check matrix and a symbol from the intermediate vector; generating a speculative value for a second initial parity symbol; and processing the first initial parity symbol, the speculative value for the second initial parity symbol, and the intermediate vector to obtain speculative values for the one or more additional parity symbols. ### Claim 8 (depends on 7) The method of claim 7, further comprising: determining a correction factor based on a correct value of a parity symbol corresponding to a second end of the intermediate vector, wherein the second end is substantially opposite to the one end; and correcting the speculative values for the one or more additional parity symbols based on the correction factor to obtain correct values of the one or more additional parity symbols. ### Claim 9 (depends on 7) The method of claim 7, further comprising configuring the parity portion of the parity check matrix as a tri-diagonal matrix. ### Claim 10 (depends on 7) The method of claim 7, comprising: generating a speculative value for a second initial parity symbol, wherein the speculative value of the second initial parity symbol is a predetermined value. ### Claim 11 A system comprising: initialization circuitry configured to process a vector of data symbols with the data portion of the parity check matrix to obtain an intermediate vector; and decoding circuitry configured to: determine an initial parity symbol based on the parity portion of the parity check matrix and a symbol from the intermediate vector; and determine one or more additional parity symbols based, at least in part, on the initial parity symbol and the intermediate vector. ### Claim 12 (depends on 11) The method of claim 11 wherein the decoding circuitry is configured to determine the initial parity symbol based on the parity portion of the parity check matrix and the symbol at substantially one end of the intermediate vector. ### Claim 13 (depends on 12) The system of claim 12, wherein the decoding circuitry determines one or more additional parity symbols by being configured to: initiate a recursion to obtain the one or more additional parity symbols. ### Claim 14 (depends on 13) The system of claim 13, wherein the decoding circuitry is further configured to: terminate the recursion in response to determining that a portion of the parity symbols up to a second end of the intermediate vector have been obtained, wherein the second end is substantially opposite to the one end. ### Claim 15 (depends on 13) The system of claim 13, wherein the decoding circuitry is further configured to: initial a first recursion to obtain the one or more additional parity symbols; and initiate a second recursion from a second end of the intermediate vector to obtain the one or more additional parity symbols, wherein the second end is substantially opposite to the one end. ### Claim 16 (depends on 11) The system of claim 11, wherein the decoding circuitry is further configured to configure the parity portion of the parity check matrix as a dual-diagonal matrix. ### Claim 17 (depends on 16) The system of claim 16, wherein the decoding circuitry is configured to configure the parity portion of the parity check matrix as a tri-diagonal matrix. ### Claim 18 (depends on 16) The system of claim 16, wherein the decoding circuitry is configured to generate a speculative value for a second initial parity symbol wherein the speculative value of the second initial parity symbol is a predetermined value. ### Claim 19 (depends on 11) The system of claim 11 wherein the decoding circuitry is further configured to: determine a first initial parity symbol based on the parity portion of the parity check matrix and a symbol from the intermediate vector; generate a speculative value for a second initial parity symbol; and process the first initial parity symbol, the speculative value for the second initial parity symbol, and the intermediate vector to obtain speculative values for the one or more additional parity symbols. ### Claim 20 (depends on 19) The system of claim 19, wherein the decoding circuitry is further configured to: determine a correction factor based on a correct value of a parity symbol corresponding to a second end of the intermediate vector, wherein the second end is substantially opposite to the one end; and correct the speculative values for the one or more additional parity symbols based on the correction factor to obtain correct values of the one or more additional parity symbols.