Method and apparatus for parallel processing in a gigabit LDPC decoder

A receiver for use in a wireless communications network capable of decoding encoded transmissions. The receiver comprises receive path circuitry for receiving and downconverting an incoming radio frequency (RF) signal to produce an encoded received signal; and a low-density parity check (LDPC) decoder associated with the receive path circuitry for decoding the encoded received signal. The LDPC decoder further comprises a memory for storing a parity check H matrix comprising R rows and C columns, where each element of the parity check H matrix comprises one of a shift value or a −1 value; and a plurality of processing elements for performing LDPC layered decoding, wherein at least one processing element is operable to process in the same cycle a first row and a second row of the parity check H matrix.

The present application is also related to U.S. patent application Ser. No. 12/876,903, filed Sep. 7, 2010, entitled “System and Method For Structured LDPC Code Family” and U.S. patent application Ser. No. 12/855,442, filed Aug. 12, 2010, entitled “System and Method For Structured LDPC Code Family With Fixed Code Length And No Puncturing”. U.S. patent application Ser. Nos. 12/876,903 and 12/855,442 are assigned to the assignee of the present application and are hereby incorporated by reference into the present application as if fully set forth herein.

TECHNICAL FIELD OF THE INVENTION

The present application relates generally to wireless communications devices and, more specifically, to encoding and decoding data transmitted between wireless communication devices.

BACKGROUND OF THE INVENTION

In information theory, a low-density parity-check (LDPC) code is an error correcting code for transmitting a message over a noisy transmission channel. LDPC codes are a class of linear block codes. While LDPC and other error correcting codes cannot guarantee perfect transmission, the probability of lost information may be made as small as desired. LDPC was the first code to allow data transmission rates close to the theoretical maximum known as the Shannon Limit. LDPC codes can perform with 0.0045 dB of the Shannon Limit. LDPC was impractical to implement when developed in 1963. Turbo codes, discovered in 1993, became the coding scheme of choice in the late 1990s. Turbo codes are used for applications such as deep-space satellite communications. LDPC requires complex processing but is the most efficient scheme discovered as of 2007. LDPC codes can yield a large minimum distance (hereinafter “dmin”) and reduce decoding complexity.

SUMMARY OF THE INVENTION

A receiver, for use in a wireless communications network, capable of decoding encoded transmissions is provided. The receiver comprises receive path circuitry for receiving and downconverting an incoming radio frequency (RF) signal to produce an encoded received signal; and a low-density parity check (LDPC) decoder associated with the receive path circuitry for decoding the encoded received signal. The LDPC decoder further comprises a memory for storing a parity check H matrix comprising R rows and C columns, where each element of the parity check H matrix comprises one of a shift value or a −1 value; and a plurality of processing elements for performing LDPC layered decoding, wherein at least one processing element is operable to process in the same cycle a first row and a second row of the parity check H matrix.

A method for decoding transmissions in a wireless communications network is provided. The method includes the steps, in a receiving device, receiving and down-converting an incoming radio frequency (RF) signal to produce an encoded received signal; and decoding the encoded received signal in a low-density parity check (LDPC) decoder. The LDPC decoder comprises a memory for storing a parity check H matrix comprising R rows and C columns, where each element of the parity check H matrix comprises one of a shift value or a −1 value. The method further comprises, in a processing element of the decoder operable to perform LDPC layered decoding, processing in the same cycle a first row and a second row of the parity check H matrix.

DETAILED DESCRIPTION OF THE INVENTION

The present disclosure describes an apparatus and method to increase design efficiency for a >1 Gbps LDPC decoder. The proposed architecture supports LDPC H matrix codes for Z=42, as proposed in U.S. patent application Ser. No. 12/876,903, which was previously incorporated by reference above. The proposed architecture also supports LDPC H Matrix codes for z=24, as proposed in U.S. patent application Ser. No. 12/855,442, which was previously incorporated by reference above.

Basically, LDPC decoding methods may be divided into two main categories. A first category, called flooding or parallel decoding ignores row contentions to increase parallelism. A second category, called layered or serial decoding uses the information accumulated between row processing. Layered decoding may require more cycles to process per iteration due to contentions. However, layered decoding requires significantly less iterations (33%-50% less iterations) to converge to the same BLER performance as the flooding decoding.

Prior art solutions for gigabit LDPC decoding mainly considered the flooding decoding method to increase LDPC processing parallelism to meet throughput requirements and ignored any possible contentions between the check nodes. This reduced the processing efficiency and increased the number of required iterations to reach the target FER/BER, which resulted in increased power consumption.

FIG. 8-11give an example for LDPC decoding of four different rates supported by four different H Matrices, as defined in WiGig/802.11ad, Spec 1.0, with a 672-bit block size. As discussed below in greater detail,FIGS. 8-11describe how the two decoding methods (layered and flooding) may process the given rate and H Matrix and indicated how many LDPC machines (processing elements) and cycles are required to process the H Matrix. A comparison for processing the related rate is given between the two decoding methods.

In general, the advantages of a flooding decoding architecture for WiGig are: i) high-speed processing (1 iteration/cycle); and ii) low latency (single block processing). The disadvantages of a flooding decoding architecture for WiGig are: i) high power per gate count per throughput; slower convergence (33-50% slower); iii) less efficient (i.e., rate 13/16 case—3 rows and 4 machines); and iv) higher critical path.

In general, the advantages of a layered decoding architecture for WiGig are: i) smaller gate count per throughput (3 machines vs. 4 machines); scalability (ease of synthesis—single machine synthesis); iii) lower critical path (reduced logic, no need to add min values before write back); and iv) allows inter-row early stopping. The disadvantages of a layered decoding architecture for WiGig are: i) 1.5× max latency due to multiple blocks; and ii) bigger buffers to support multiple blocks.

FIG. 1illustrates an exemplary wireless network100, which performs LDPC encodings and decoding according to the principles of the present disclosure. In the illustrated embodiment, wireless network100includes base station (BS)101, base station (BS)102, base station (BS)103, and other similar base stations (not shown). Base station101is in communication with base station102and base station103. Base station101is also in communication with Internet130or a similar IP-based network (not shown).

Base station102provides wireless broadband access (via base station101) to Internet130to a first plurality of mobile stations within coverage area120of base station102. The first plurality of mobile stations includes mobile station111, which may be located in a small business (SB), mobile station112, which may be located in an enterprise (E), mobile station113, which may be located in a WiFi hotspot (HS), mobile station114, which may be located in a first residence (R), mobile station115, which may be located in a second residence (R), and mobile station116, which may be a mobile device (M), such as a cell phone, a wireless laptop, a wireless PDA, or the like.

Base station103provides wireless broadband access (via base station101) to Internet130to a second plurality of mobile stations within coverage area125of base station103. The second plurality of mobile stations includes mobile station115and mobile station116. In an exemplary embodiment, base stations101-103may communicate with each other and with mobile stations111-116using OFDM or OFDMA techniques.

Base station101may be in communication with either a greater number or a lesser number of base stations. Furthermore, while only six mobile stations are depicted inFIG. 1, it is understood that wireless network100may provide wireless broadband access to additional mobile stations. It is noted that mobile station115and mobile station116are located on the edges of both coverage area120and coverage area125. Mobile station115and mobile station116each communicate with both base station102and base station103and may be said to be operating in handoff mode, as known to those of skill in the art.

Mobile stations111-116may access voice, data, video, video conferencing, and/or other broadband services via Internet130. In an exemplary embodiment, one or more of mobile stations111-116may be associated with an access point (AP) of a WiFi WLAN. Mobile station116may be any of a number of mobile devices, including a wireless-enabled laptop computer, personal data assistant, notebook, handheld device, or other wireless-enabled device. Mobile stations114and115may be, for example, a wireless-enabled personal computer (PC), a laptop computer, a gateway, or another device.

FIG. 2Ais a high-level diagram of an orthogonal frequency division multiple access (OFDMA) transmit path.FIG. 2Bis a high-level diagram of an orthogonal frequency division multiple access (OFDMA) receive path. InFIGS. 2A and 2B, the OFDMA transmit path is implemented in base station (BS)102and the OFDMA receive path is implemented in mobile station (MS)116for the purposes of illustration and explanation only. However, it will be understood by those skilled in the art that the OFDMA receive path may also be implemented in BS102and the OFDMA transmit path may be implemented in MS116.

In BS102, channel coding and modulation block205receives a set of information bits, applies LDPC coding and modulates (e.g., QPSK, QAM) the input bits to produce a sequence of frequency-domain modulation symbols. Serial-to-parallel block210converts (i.e., de-multiplexes) the serial modulated symbols to parallel data to produce N parallel symbol streams where N is the IFFT/FFT size used in BS102and MS116. Size N IFFT block215then performs an IFFT operation on the N parallel symbol streams to produce time-domain output signals. Parallel-to-serial block220converts (i.e., multiplexes) the parallel time-domain output symbols from Size N IFFT block215to produce a serial time-domain signal. Add cyclic prefix block225then inserts a cyclic prefix to the time-domain signal. Finally, up-converter230modulates (i.e., up-converts) the output of add cyclic prefix block225to RF frequency for transmission via a wireless channel. The signal may also be filtered at baseband before conversion to RF frequency.

Each of base stations101-103may implement a transmit path that is analogous to transmitting in the downlink to mobile stations111-116and may implement a receive path that is analogous to receiving in the uplink from mobile stations111-116. Similarly, each one of mobile stations111-116may implement a transmit path corresponding to the architecture for transmitting in the uplink to base stations101-103and may implement a receive path corresponding to the architecture for receiving in the downlink from base stations101-103.

The channel decoding and demodulation block280decodes the received data. The channel decoding and demodulation block280includes a decoder configured to perform a low density parity check decoding operation. In some embodiments, the channel decoding and demodulation block280comprises one or more context-based operation reconfigurable instruction set processors (CRISPs), such as the CRISP processor(s) described in one or more of Application Ser. No. 11/123,313, filed May 6, 2005 and entitled “Context-Based Operation Reconfigurable Instruction Set Processor And Method Of Operation”; U.S. Pat. No. 7,769,912, filed Jun. 1, 2005 and entitled “MultiStandard SDR Architecture Using Context-Based Operation Reconfigurable Instruction Set Processors”; U.S. Pat. No. 7,483,933, issued Jan. 27, 2009 and entitled “Correlation Architecture For Use In Software-Defined Radio Systems”; application Ser. No. 11/225,479, filed Sep. 13, 2005 and entitled “Turbo Code Decoder Architecture For Use In Software-Defined Radio Systems”; and application Ser. No. 11/501,577, filed Aug. 9, 2006 and entitled “Multi-Code Correlation Architecture For Use In Software-Defined Radio Systems”, all of which are hereby incorporated by reference into the present application as if fully set forth herein.

FIG. 3illustrates a top-level architecture of LDPC CRISP300according to embodiments of the present disclosure. The embodiment of LDPC CRISP300shown inFIG. 3is for illustration only. Other embodiments of top-level architectures for LDPC CRISP300could be used without departing from the scope of this disclosure. LDPC CRISP300may be implemented in channel decoding and demodulation block280inFIG. 2.

LDPC CRISP300includes instruction decoder & address generator block305. In some embodiments, instruction decoder & address generator block305may be a programmable finite state machine. In some embodiments, instruction decoder & address generator block305operates as a controller for LDPC CRISP300and its components. LDPC CRISP300also includes input buffer block310, read switch block315, processor array320, write switch block325and extrinsic buffer block330. In some embodiments (not specifically illustrated), input buffer block310includes extrinsic buffer block330(e.g., input buffer block310and extrinsic buffer330may be the same block).

Instruction decoder & address generator block305includes a plurality of instructions to control operations of LDPC CRISP300. In some embodiments, a portion (e.g., some or all) of the plurality of instructions is reconfigurable to vary the operation of LDPC CRISP300. The plurality of instructions may be reconfigured to have LDPC CRISP300perform Serial V decoding or Serial-C decoding. Additionally, the plurality of instructions may be reconfigured to have LDPC CRISP300perform decoding by a flooding technique, layered technique, sum products technique, or min-sum technique. The plurality of instructions also may be reconfigured to vary a number of iterations performed such that LDPC CRISP300only performs a number of iterations or continues to perform iterations until a specified event occurs or a specified amount of time lapses.

Further, the plurality of instructions may be reconfigured to have LDPC CRISP300perform decoding for any one or more of IEEE 802.16e (hereafter, “WiMax”), Digital Video Broadcasting-Satellite-Second Generation (hereafter, “DVB-S2”), and international Mobile Telecommunications-Advanced (hereafter, “IMT-Advanced” or “4G”). LDPC CRISP300may be applied to any system that incorporates an LDPC decoding algorithm including, but not limited to, CDMA, OFDMA, WiMax, third generation (3G) and 4G systems. Additionally, the plurality of instructions may be reconfigured to have LDPC CRISP300vary the number of LDPC CRISP decoder units for use in the decoding operation. Instruction decoder & address generator block305also is configured to store an H-matrix (discussed below with respect toFIGS. 5A and 5B).

Input buffer block310is configured to receive data (e.g., codewords or symbols). Input buffer block310includes a number of memory blocks for storing the received data. In some embodiments, input buffer block310may includes twenty-four (24) memory blocks for storing the received data.

Read switch reads the H-matrix from instruction decoder & address generator block305. Read switch315also reads the received data from input buffer block310. Read switch315uses the H-matrix to determine from where to read the data from input buffer310. Read switch315is configured to apply a Z-factor right shift multiplexer (MUX) operation to the received data read from input buffer block310. The Z-factor right shift multiplexor (MUX) operation is based on the shift data computed from the H-matrix or the shift vector (discussed below with respect toFIGS. 5A and 5B).

Processor array320includes a number of processor elements. Each processor element (PE) includes a plurality of processors configured to perform a flooding technique, layered technique, sum products technique, or min-sum technique. For example, processor array320may be configured to find minimum values using a min-sum technique. Further, processor array320is configured to perform decoding for any one or more of WiMax, DVB-S2 and 4G. In some embodiments, processor array320includes four (4) processor elements, each processor element including twenty-four (24) processors. In such embodiments, LDPC CRISP300may be referenced as a 2/4-unit LDPC decoder CRISP.

Write switch block325is configured to receive Min/Next Min selection and sums from processor array320. Write switch block325further is configured to apply a Z-factor left shift MUX operation to the Min/Next Min selection and sums received from processor array320to generate a set of output extrinsic data. Further, write switch block325is configured to write the output extrinsic data of write switch block325to extrinsic buffer block330. For example, write switch block325is configured to use the H-matrix to reverse the operation performed by read switch315.

Extrinsic buffer block330is configured to store the output extrinsic data in a number of memory units. In some embodiments, extrinsic buffer block330includes twenty-four (24) memory units. Extrinsic buffer block330also is coupled to read switch315such that read switch315may read the output extrinsic data (hereinafter also “extrinsic output”).

Thus, LDPC CRISP300is able to perform a number of iterations of the received data. LDPC CRISP300is operable to read the input data and apply a decoding process to the input data to output an extrinsic data. Thereafter, LDPC CRISP300performs one or more iterations of the decoding process using extrinsic data from the previous decoding process as the input for the next decoding process. As such, the input data is used only once and, thereafter, LDPC CRISP300generates the extrinsic data for use in the subsequent iterations.

LDPC CRISP300may be configured to perform iterations until a cessation event occurs. For example, LDPC CRISP300may be configured to perform a specified number of iterations. Additionally, LDPC CRISP300may be configured to perform iterations until the extrinsic data reaches a specified value (e.g., a convergence point). Further, LDPC CRISP300may be configured to perform iterations until a most significant bit (MSB) output is unchanged for several consecutive iterations.

LDPC codes are linear codes that may be characterized by sparse parity check matrices (H). The H matrix has a low density of binary 1 bits. The sparseness of H yields a large dminand reduces decoding complexity. An exemplary H-matrix is represented by Equation 1:

An LDPC code is regular if every row has the same weight, (Wr) and every column has the same weight (Wc). The regular LDPC code is denoted by (Wc, Wr)-regular. Otherwise, the LDPC code is irregular. Regular codes are easier to implement and analyze. Furthermore, regular codes have lower error floors. However, irregular codes may get closer to capacity than regular codes.

FIG. 4illustrates Tanner graph400, which corresponds to a parity check matrix according to embodiments of the present disclosure. The embodiment of Tanner graph400shown inFIG. 4is for illustration only. Other embodiments of Tanner graph400may be used without departing from the scope of this disclosure.

Tanner graph400is a bipartite graph. In bipartite graphs, nodes are separated into two distinctive sets and edges only connect nodes of two different types. The two types of nodes in Tanner graph400are referred to as variable nodes (hereafter, “v-nodes”) and check nodes (hereafter, “c-nodes”).

V-nodes correspond to bits of the codeword or, equivalently, to columns of the parity check H-matrix. There are n v-nodes. V-nodes are also referenced as “bit nodes”. C-nodes correspond to parity check equations or, equivalently, to rows of the parity check H-matrix. There are at least m=n−k c-nodes.

Tanner graph400corresponds to the parity check H-matrix illustrated by Equation 1. Tanner graph400includes five (5) c-nodes (the number of parity bits) and ten (10) v-nodes (the number of bits in a codeword). C-node fiis connected to v-node cjif the element hijof H-matrix is a binary 1. For example, c-node f0is connected c0, c1, c2, c3, c5, c7and c9. The connection between f0and c0corresponds to h00; the connection between f0and c2corresponds to h01; and so on. Therefore, the connections to f0correspond to the first row in the H-matrix, further illustrated in Equation 2:
H0=[1 1 1 1 0 1 0 1 0 1].  [Eqn. 2]

A degree of a node is the number of edges (e.g., connections) connected to the node. A cycle is the total length, in Tanner graph400, of a path of distinct edges that closes upon itself. A path from c1→f2→c7→f0→c1is an example of a short cycle. Short cycles should be avoided since short cycles adversely affect decoding performance. Short cycles manifest themselves in the H-matrix by columns with an overlap of two.

In some embodiments, LDPC CRISP300uses a sum-product process to decode the LDPC codes. In some such embodiments, a hard-decision decoding is performed. In other such embodiments, a soft-decision decoding is performed. In additional and alternative embodiments, LDPC CRISP300uses a min-sum process.

LDPC CRISP300is configured as a universal decoder for use with multiple transmission standards including, but not limited to, WiMax, DVB-S2 and 4G. The LDPC is configured to use a number of rate codes including, but not limited to: 1/2 rate code, 5/8 rate code, 3/4 rate code, and 13/16 rate code.

FIG. 5Aillustrates rate 1/2 code500according to one embodiment of a conventional LDPC decoder. The embodiment of rate 1/2 code500shown inFIG. 5Ais for illustration only. Other embodiments of rate 1/2 code500could be used without departing from the scope of this disclosure.

In some embodiments, the parity check H-matrix stored in a receive path, (e.g., stored in channel decoder and demodulator280) may be configured according to rate 1/2 code500. Rate 1/2 code500is a 576×288 matrix that represents a transmission of five hundred seventy-six (576) bits per frame (bpf). In rate 1/2 code500, the first twelve (12) columns505represent systematic (or data) bits while the second twelve (12) columns510represent parity (or redundancy) bits. Each bit is a location bit that represents a 24×24 matrix. The Z-factor defines the number of bits per matrix. For example, the Z-Factor may be twenty-four (24). As such, in rate 1/2 code500, each frame in the transmission includes two-hundred eighty-eight (288) systematic bits and two-hundred eighty-eight (288) parity bits. A −1 value represents a zero (0) matrix. Accordingly, a “−1” value indicates that the location is not used in the calculation. The remaining values (i.e., other than −1) are location values that represent a matrix. For example, the matrix represented by the location value 94, found in h01515, is divided by four (4) and rounded-down to yield a twenty-three (23). Thereafter, the unity matrix is shifted twenty-three times.

FIG. 5Billustrates rate 5/6 code550, according to one embodiment of a conventional LDPC decoder. The embodiment of rate 5/6 code550shown inFIG. 5Bis for illustration only. Other embodiments of rate 5/6 code550could be used without departing from the scope of this disclosure.

In some embodiments, the parity check H-matrix may be configured according to rate 5/6 code550. Rate 5/6 code550is a 576×288 matrix that represents a transmission of five hundred seventy-six (576) bpf. In rate 5/6 code550, the first twenty (20) columns555represent systematic (data) bits, while the last four (4) columns560represent parity (redundancy) bits. As such, using rate 5/6 code550, each frame in the transmission includes four-hundred eighty (480) bits of systematic bits and ninety-six (96) parity bits. A −1 value represents a zero (0) 24×24 matrix. Accordingly, a −1 value indicates that the bit is not used. The remaining values (other than −1) are location values that represent a matrix. For example, the matrix represented by the location value 25 found in h01565is divided by four (4) to and rounded down to yield a six (6). Thereafter, the unity matrix is shifted six times.

In some embodiments, a 4G H-matrix may comprise two vectors. In such embodiments, the first vector includes only the location values while the second vector includes a shift value. For example, the location vector for the first row of the H-Matrix500is illustrated by Equation 3:
H0=[1 2 8 9 12 13].  [Eqn. 3]

Each value in the vector H0illustrated in Equation 3 represents a non-zero (e.g., not “−1”) column position for row 0. Additionally, the second vector (referenced herein as Hs0), containing the shift values for the H-Matrix500, is illustrated by Equation 4:

FIG. 6illustrates a detailed block diagram of an exemplary LDPC decoder CRISP600that performs decoding according to a flooding method. The embodiment of the serial-v LDPC CRISP600shown inFIG. 6is for illustration only. Other embodiments of LDPC CRISP600could be used without departing from the scope of this disclosure. InFIG. 6, it shall be assumed that decoding operations are performed on N=672 total bits. Thus, for a Rate 1/2 decoding, there would be 336 systematic bits and 336 parity bits. For Z=42, the 336 systematic bits are segmented into 8 blocks of 42 data bits each and the 336 parity bits are segmented into 8 blocks of 42 parity bits each.

LDPC CRISP600includes an input buffer comprising a plurality of individual memory units605. The individual memory units605are a plurality of separate and distinct memory devices that are each capable of receiving data to independent data write operations occurring the remaining individual memory units605. In an exemplary embodiment, LDPC CRISP600includes sixteen (16) memory units605a-605p. It will be understood that the illustration of 16 memory units merely is exemplary and the plurality of memory units605can include any number of memory units. The memory units605a-pare configured to store data received via the receive path. As such, LDPC CRISP600is configured to read16data simultaneously (as opposed to only one data at a time if using only one memory unit).

For example, each memory unit605can receive data samples (e.g., 8 soft bits) from the receive path inFIG. 2E. In such example, when memory unit605areceives data, memory unit605ais receiving systematic data samples0-41at a time t0. Similarly, memory unit605bwould receive data samples42-83at the time t0, and so forth. Finally, memory unit605pwould receive data samples629-671at the time t0. Therefore, memory units605a-605preceive (336) samples of data (systematic or parity) simultaneously.

LDPC CRISP600also includes extrinsic/row subtractor block610. The extrinsic/row subtractor block610is configured to remove at least a portion of extrinsic data stored in the memory banks by write switch640. Extrinsic/row subtractor block610has 16 input channels, one for each of memory units605a-605p, and16output channels.

LDPC CRISP600also includes a 1-to-1 read switch615. Read switch615selects and aligns N variable inputs from the 16 input/extrinsic data per row. N corresponds to the number of processors elements (e.g., processors) operating in a processor array625.

LDPC CRISP600includes Z-factor right shift MUX block620. Z-factor right shift MUX block620is configured to apply a Z-factor right shift MUX operation to the received data read from the memory banks605(via blocks610and615). After selecting the N inputs/extrinsic outputs, Z-factor right shift MUX block620aligns (i.e., Z-shifts) the N inputs/extrinsic outputs based on the H-matrix.

For example, the Z-factor shift is applied to the data in each memory unit605according to the H-matrix500. In such example, since each location value corresponds to a 42×42 matrix (e.g., 42 samples of data), all 42 samples of data in each memory unit605are processed based on the location value found in the H-matrix. Therefore, all the data in memory units605a-605pare shifted based on the H-matrix.

Minimum detection block625includes a number of processors configured to perform a flooding technique, sum products technique or min-sum technique. Minimum detection block625may include structures and functions similar to processor array320inFIG. 3. For example, minimum detection block625may be configured to find minimum values using a min-sum technique. Further, minimum detection block625is configured to perform decoding for any one or more of WiMax, DVB-S2 and 4G. Each of the processors in minimum detection block625is configured to apply a different equation as represented by the H-matrix. In some embodiments, the processor array comprises 16 processors. In some additional and alternative embodiments, minimum detection block625includes a single unit with 42 processors.

Each of the processor elements in minimum detection block625is configured to read from each of memory units605a-605psuch that all the data stored in one of memory units605a-605pis processed using a different equation simultaneously.

Minimum detection block625is dependent upon the number of Z-factor columns processed per cycle. In some embodiments, minimum detection block625is configured to output a minimum (Min) value and a next minimum (Next Min) value corresponding to the smallest bit value and second smallest bit value respectively. Minimum detection block625stores the Min and Next Min values in one or more registers. The one or more registers are included in minimum detection block625.

LDPC CRISP600includes a number of selection and sum blocks630. In some embodiments, LDPC CRISP600includes a first selection and sum block630aand a second selection and sum block630b. Each of selection and sum blocks630is configured to perform a Min/Next Min selection and sum operation. In some embodiments, the first selection and sum block630ais configured to perform the Min/Next Min selection and sum operation on a first check node while the second selection and sum block630bis configured to perform the Min/Next Min selection and sum operation on a second check node.

LDPC CRISP600further includes a number of Z-factor left shift MUX blocks635. In some embodiments, LDPC CRISP600includes a first Z-factor left shift MUX block635aand a second Z-factor left shift MUX block635b. Each of the number of Z-factor left shift MUX blocks635a,bis configured to receive Min/Next Min selection and sums and apply a Z-factor left shift MUX operation to the received Min/Next Min selection and sums.

LDPC CRISP600is configured to generate a set of output data (e.g., extrinsic outputs). Each of a number of write switch blocks640is configured to write the output data of the Z-factor left shift MUX blocks635to at least one of a plurality of extrinsic memory units645and the plurality of memory banks605. In some embodiments, a first write switch block640ais configured to write the output data to the plurality of extrinsic memory units645while a second write switch block640bis configured to write the output data to the plurality of memory units605.

FIG. 7illustrates a detailed block diagram of exemplary LDPC decoder CRISP700, which performs layered decoding according to the principles of the present disclosure. Conventional layered decoding methods operate on one row of the H Matrix at a time. Decoded information from one row is used in the decoding of subsequent rows. However, the improved layered decoding method differs from conventional layered decoding methods in that two rows may be decoded simultaneously provided that column elements in the two selected rows of the matrix are mutually exclusive or non-overlapping (i.e., the elements from the same column are not used at the same time).

FIG. 8may be used to illustrate this concept.FIG. 8depicts an H Matrix for a rate 1/2 code. The first row of the H Matrix and the third row of the H Matrix are mutually exclusive or non-overlapping. It is recalled that a −1 entry in the H matrix indicates that the corresponding entry in the H matrix is not used in decoding the systematic and parity bits. For each column element in the first row of the H Matrix that is not −1, the corresponding column element in the third row of the H Matrix is −1 (not used). Similarly, for each column element in the third row of the H Matrix that is not −1, the corresponding column element in the first row of the H Matrix is −1 (not used).

More specifically, the first (=40), third (=38), fifth (=13), seventh (=5), and ninth (=18) column values of the first row all correspond to −1 values in the first, third, fifth, seventh, and ninth columns of the third row. Also, the second (=36), fourth (=31), sixth (=7), eighth (=34), tenth (=10), and eleventh (=41) column values of the third row all correspond to −1 values in the second, fourth, sixth, eighth, tenth, and eleventh columns of the first row.

It is this mutually exclusive (or non-overlapping) characteristic of the first and third rows to be decoded simultaneously, even in a layered decoding method. Similarly, the second and fourth rows of the H Matrix inFIG. 8are mutually exclusive and may be decoded at the same time.

InFIG. 7, many of the component blocks of LDPC CRISP700are similar to LDPC CRISP600inFIG. 6. In particular, LDPC CRISP700includes an input buffer comprising a plurality of individual memory units605a-605p, as in LDPC CRISP600. LDPC CRISP700also includes extrinsic/row subtractor block610, as in LDPC CRISP600.

However, 1-to-1 read switch615is replaced inFIG. 7by a 1×16-to-2×8 read switch715. Read switch715receives the 16 input channels from subtractor block610, but splits the outputs into two distinct 8 channel outputs—one for each of the mutually exclusive rows that are being processed at the same time.

Thereafter, the two distinct channels are processed in parallel. Z-factor right shift MUX block720aperforms a right shift on a first group of eight outputs (corresponding to one mutually exclusive matrix row) from subtractor block715. Z-factor right shift MUX block720bperforms a right shift on a second group of eight outputs (corresponding to a second mutually exclusive matrix row) from subtractor block715.

Minimum detection block725includes a number of processors configured to perform a layered decoding operation on one group of 8 output channels from MUX block720asimultaneously with another group of 8 output channels from MUX block720b. Unlike minimum detection block625(which generates a Min value and a Next Min value), minimum detection block725generates a pair of such values—namely, a Min value and a Next Min value for the outputs of MUX block720aand a Min value and a Next Min value for the outputs of MUX block720b. Based on the current H-Matrix rows processed, the Minimum detection block725can output either the two Min values (and two corresponding Next Min values) of the two sets of 8 inputs (for two mutually exclusive rows), or a single Min value (and the corresponding Next Min value) of the all 16 inputs (for a single row).

Selection and sum blocks730a,730b,730cand730dperform operations that are analogous to the operations performed by selection and sum blocks630aand730b. However, each of selection and sum blocks730a-730doperates on 8 input channels and generates 8 output channels, whereas each of selection and sum blocks630aand630boperates on 16 input channels and generates 16 output channels.

Similarly, Z-factor left shift MUX blocks735a,735b,735cand750dperform operations that are analogous to the operations performed by Z-factor left shift MUX blocks635aand635b. However, each of MUX blocks735a-750doperates on 8 input channels and generates 8 output channels, whereas MUX blocks635aand635beach operate on 16 input channels and generate 16 output channels.

Finally, LDPC CRISP700comprises write switch blocks740aand740b, which are 2×8-to-1×16 devices that reverse the operation of 1×16-to-2×8 read switch715. Write switch block740awrites output data to extrinsic memory units645a-645p. Write switch block740bwrites the output data to memory units605a-605p.

FIGS. 8-11illustrate the comparative advantages of layered decoding according to the principles of the present disclosure.

FIG. 8depicts an H Matrix for a rate 1/2 code. In an exemplary embodiment, LDPC decoder CRISP700comprises 16 processing elements, where each processing element processes42data or parity bits per cycle. For the rate 1/2 code inFIG. 8, there are 4 pairs of independent rows (i.e., mutually exclusive or non-overlapping) that can be processed independently (i.e., parallel machines for flooding). For a maximum for Wr=8 inputs per row, each machine can process 2 rows (8+8 processing elements) per cycle.

In layered operation, machine no. P0 processes the first and third rows in a first cycle (T=0). Machine no. P0 processes the second and fourth rows in a second cycle (T=1). Machine no. P0 processes the fifth and seventh rows in a third cycle (T=2). Finally, machine no. P0 processes the sixth and eighth rows in a fourth cycle (T=3).

In flooding operation, all in the same cycle, machine no. P0 processes the first and third rows, machine no. P1 processes the second and fourth rows, machine no. P2 processes the fifth and seventh rows, and machine no. P3 processes the sixth and eighth rows.

Thus, flooding is four times faster than layered, but requires four times as many processing elements. However, flooding decoding is 33-50% slower to converge than layered decoding. As a result, flooding decoding is about 33% less efficient than layered decoding.

FIG. 9depicts an H Matrix for a rate 5/8 code. For the rate 5/8 code, there are 2 pairs of independent rows that can be processed independently and 2 dependent rows (i.e., 4 parallel machines for flooding). For the 2 pairs with maximum of Wr<=8 inputs per row, each machine can process 2 rows (8+8 processing elements) per cycle.

In layered operation, machine no. P0 processes the first in a first cycle (T=0). Machine no. P0 processes the second row in a second cycle (T=1). Machine no. P0 processes the third and fifth rows in a third cycle (T=2). Finally, machine no. P0 processes the fourth and sixth rows in a fourth cycle (T=3).

In flooding operation, all in the same cycle, machine no. P0 processes the first row, machine no. P1 processes the second row, machine no. P2 processes the third and fifth rows, and machine no. P3 processes the fourth and sixth rows. Thus, flooding is four times faster than layered, but requires four times as many processing elements.

Again, flooding is four times faster than layered, but requires four times as many processing elements. However, flooding decoding is 33-50% slower to converge than layered decoding. As a result, flooding decoding is about 33% less efficient than layered decoding.

FIG. 10depicts an H Matrix for a rate 3/4 code. For the rate 3/4 code, there are 0 pairs of independent rows that can be processed independently and 4 dependent rows (i.e., 4 parallel machines for flooding).

In layered operation, machine no. P0 processes the first in a first cycle (T=0). Machine no. P0 processes the second row in a second cycle (T=1). Machine no. P0 processes the third row in a third cycle (T=2). Finally, machine no. P0 processes the fourth row in a fourth cycle (T=3).

In flooding operation, all in the same cycle, machine no. P0 processes the first row, machine no. P1 processes the second row, machine no. P2 processes the third row, and machine no. P3 processes the fourth row.

Thus, flooding is four times faster than layered, but requires four times as many processing elements. However, flooding decoding is 33-50% slower to converge than layered decoding. As a result, flooding decoding is about 33% less efficient than layered decoding.

FIG. 11depicts an H Matrix for a rate 13/16 code. For the rate 13/16 code, there are 0 pairs of independent rows that can be processed independently and 3 dependent rows (i.e., minimum of 4 parallel machines for flooding to support the other rates above).

In layered operation, machine no. P0 processes the first in a first cycle (T=0). Machine no. P0 processes the second row in a second cycle (T=1). Machine no. P0 processes the third row in a third cycle (T=2).

In flooding operation, all in the same cycle, machine no. P0 processes the first row, machine no. P1 processes the second row, and machine no. P2 processes the third row.

Thus, flooding is three times faster than layered, but requires four times as many processing elements. However, flooding decoding is 33-50% slower to converge than layered decoding. As a result, flooding decoding is about 50% less efficient than layered decoding.