Edge memory architecture for LDPC decoder

Systems, devices, and methods are disclosed for a novel edge memory architecture. An architecture is described wherein the extrinsic information typically stored inside the edge memory is reformatted. Instead of storing the extrinsic information for every edge, the novel edge memory stores a set of possible extrinsic information values for a check node in a “value memory.” The edge memory also stores an index for each edge in a second, “index memory,” identifying which value stored in the value memory applies to each respective edge.

BACKGROUND

Embodiments of the invention described herein generally relate to forward error correction (FEC) and, more specifically, to low-density parity-check (LDPC) encoding and decoding for satellite communications.

Forward error correction (FEC) is a method of transmitting redundant information with transmitted data to allow a receiver to reconstruct the data if there is an error in the transmission. At a transmitter, a structured redundancy may be added in the form of some parity bits by encoding the data. This structured redundancy may be exploited at the receiver by decoding to correct any errors introduced during transmission.

Some FEC coding schemes incorporate iterative decoding by a decoder. Turbo codes and LDPC codes are examples of coding schemes that may be iteratively decoded. However, because of the complexity of these coding schemes, there may be very significant memory and processing resources required in some implementations of the decoder. LDPC edge memory, in particular, can have a very substantial footprint in many traditional LDPC decoder designs. There is, thus, a need in the art to reduce the size of the edge memory while maintaining performance.

SUMMARY

Systems, devices, and methods are disclosed related to a novel edge memory architecture. Edge memory is typically used to store the extrinsic information generated during each iteration of the decoding process for all the edges (i.e., the connections between the bit nodes and the check nodes). An architecture is described wherein the extrinsic information typically stored inside the edge memory is reformatted. Instead of storing the extrinsic information for every edge, the novel edge memory stores a set of possible extrinsic information values for a check node (in “value” memory). The edge memory also stores an index for each edge (in “index” memory) identifying which value stored in the value memory applies to each respective edge. This separation of the edge memory into two novel parts (value memory and index memory) may reduce the size of edge memory.

An example of a communication terminal according to the disclosure includes: a decoding circuit configured to decode encoded data that has been encoded according to a coding scheme defining a parity check matrix, wherein the parity check matrix defines parity equations and edges between bit nodes and check nodes, the decoding circuit including: an input buffer configured to store channel soft information; a BNP accumulation module configured to read the channel soft information, to access extrinsic information for edges, and to generate accumulated values for edges by summing the channel soft information and the extrinsic information for edges; a controller module configured to reformat the accumulated values for edges as multiple candidate values and multiple indexes, each index identifying one of the candidate values as applying to a respective edge; edge memory configured to store the reformatted accumulated values for edges as the multiple candidate values and the multiple indexes; a BNP calculation module configured to access extrinsic information for edges of a previous CNP iteration and to generate extrinsic information inputs for edges for a new CNP iteration by subtracting the extrinsic information for edges of the previous CNP iteration from the reformatted accumulated values for edges; a CNP processor module configured to generate output extrinsic information for edges using the extrinsic information inputs for edges generated by the BNP calculation module; and an output buffer configured to store output data from the BNP accumulation module when a determination is made that all parity equations defined by the parity check matrix are satisfied.

Embodiments of such a communication terminal may include one or more of the following features. Reformatting the accumulated values for edges as the multiple candidate values and the multiple indexes includes a selection process defined by a selection criterion and a selection value. The CNP processor module generates the output extrinsic information for edges with an accumulation operation using as operands the extrinsic information inputs for edges generated by the BNP calculation module; and the selection process identifies the operands which have a higher probability of dominating results of the accumulation operation of the CNP processor module. The selection criterion is least reliability, the selection value is three, and the selection process identifies the three operands which have a least reliability of the extrinsic information inputs for edges. The edge memory includes a value memory portion configured to store the multiple candidate values and an index memory portion configured to store the multiple indexes, each index including a reference to a respective candidate value and a sign of the respective candidate value. The coding scheme includes an LDPC code. The communication terminal is a satellite modem.

An example of a method for decoding encoded data that has been encoded according to a coding scheme defining a parity check matrix, the parity check matrix defining parity equations and edges between bit nodes and check nodes includes: receiving channel soft information; accessing extrinsic information for edges; generating accumulated values for edges by summing the channel soft information and the extrinsic information for edges; reformatting the accumulated values for edges as multiple candidate values and multiple indexes, each index identifying one of the candidate values as applying to a respective edge; storing the reformatted accumulated values for edges as the multiple candidate values and the multiple indexes; accessing extrinsic information for edges of a previous CNP iteration; generating extrinsic information inputs for edges for a new CNP iteration by subtracting the extrinsic information for edges of the previous CNP iteration from the reformatted accumulated values for edges; generating extrinsic information output for edges using the extrinsic information inputs for edges; updating the bit nodes by summing the extrinsic information output for edges associated with the respective bit nodes; determining that all parity equations defined by the parity check matrix are satisfied; and storing output bit node data.

Embodiments of such a method may include one or more of the following features. Reformatting the accumulated values for edges as the multiple candidate values and the multiple indexes includes selecting based on a selection criterion and a selection value. Generating the extrinsic information output for edges includes generating output extrinsic information for edges with an accumulation operation using as operands the extrinsic information inputs for edges; and selecting includes identifying the operands which have a higher probability of dominating results of the accumulation operation. The selection criterion is least reliability, the selection value is three, and selecting includes identifying the three operands which have a least reliability of the extrinsic information inputs for edges. Storing the reformatted accumulated values for edges includes storing the multiple candidate values in a value memory portion of edge memory and storing the multiple indexes in an index memory portion of the edge memory, each index including a reference to a respective candidate value and a sign of the respective candidate value. The coding scheme includes an LDPC code.

An example of a communication terminal includes: a decoding circuit configured to decode encoded data that has been encoded according to a coding scheme defining a parity check matrix, wherein the parity check matrix defines parity equations and edges between bit nodes and check nodes, the decoding circuit including: a CNP processor module configured to calculate extrinsic information for all bit nodes connected by edges to respective check nodes during decoding iterations; one or more BNP processor modules configured to combine extrinsic information for check nodes connected by edges to respective bit nodes to provide updated extrinsic information inputs to the CNP processor module during decoding iterations; and edge memory configured to store multiple candidate extrinsic information values for check nodes and to store multiple indexes, each index identifying one of the candidate extrinsic information values as applying to a respective edge.

Embodiments of such a communication terminal may include one or more of the following features. The one or more BNP processor modules include a BNP accumulation module and a BNP extrinsic information calculation module. The decoding circuit further includes a controller configured to reformat accumulated values for edges generated by the one or more BNP processor modules as the multiple candidate extrinsic information values and the multiple indexes. The CNP processor module is configured to calculate the extrinsic information with an accumulation operation using as operands the updated extrinsic information inputs generated by the one or more BNP processor modules; and the controller is configured to reformat the accumulated values for edges by identifying the operands which have a higher probability of dominating results of the accumulation operation of the CNP processor module. The operands identified have the least reliability of the updated extrinsic information inputs. The operands identified have the smallest of the updated extrinsic information inputs. The coding scheme includes an LDPC code.

DETAILED DESCRIPTION

It should also be appreciated that the following systems, methods, and software may individually or collectively be components of a larger system, wherein other procedures may take precedence over or otherwise modify their application. Also, a number of steps may be required before, after, or concurrently with the following embodiments.

Systems, devices, methods, and software are described related to a novel edge memory design for an LDPC decoder. Instead of storing the extrinsic information for each edge, the edge memory stores a set of possible extrinsic information values for a check node (value memory), and then stores an index for each edge (index memory) that identifies the value that applies to each edge. This separation of the edge memory into two parts (value memory and index memory) may reduce the size of edge memory. Example embodiments of device and system architectures are described herein with respect to LDPC codes, LDPC decoding, and a novel indexing architecture. However, these may be adapted for other FEC coding schemes.

LDPC and turbo codes are often used in satellite communications. Referring first toFIG. 1, a block diagram illustrates an example satellite communications system100configured according to various embodiments of the invention. While a satellite communications system is used to illustrate various aspects of the invention, it is worth noting that certain principles set forth herein are applicable to a number of other wireless systems, as well. The satellite communications system100includes a network120, such as the Internet, interfaced with a gateway115that is configured to communicate with one or more user terminals130, via a satellite105.

The network120may be any type of network and can include, for example, the Internet, an IP network, an intranet, a wide-area network (WAN), a local-area network (LAN), a virtual private network (VPN), the Public Switched Telephone Network (PSTN), or any other type of network supporting data communication between any devices described herein. A network120may include both wired and wireless connections, including optical links. Many other examples are possible and apparent to those skilled in the art in light of this disclosure. The network120may connect the gateway115with other gateways (not pictured), which are also in communication with the satellite105, and which may share information on link conditions and other network metrics.

The gateway115provides an interface between the network120and the user terminal130. The gateway115may be configured to receive data and information directed to one or more user terminals130, and format the data and signaling information for delivery downstream to the respective user terminals130via the satellite105. In some embodiments, the gateway115may encode data to be transmitted downstream using LDPC codes.

The gateway115may also be configured to receive upstream signals from the satellite105(e.g., from one or more user terminals130) directed to a destination in the network120, and can format the received signals for transmission through the network120. The novel LDPC decoding techniques and edge memory architectures described herein are, in many instances, described with reference to encoding and transmission at the gateway115, and reception and decoding at the user terminal130. However, in other embodiments, the LDPC decoding techniques and edge memory architectures may be applied to encoding and transmission at the user terminal130, and reception and decoding at the gateway115(star) or user terminal130(mesh).

A device (not shown) connected to the network120may communicate with one or more user terminals130through the gateway115. Data packets may be sent from a device in the network120to the gateway115. The gateway115may format a series of frames in accordance with a physical layer definition for transmission to the satellite105via a downstream link135. A variety of physical layer transmission modulation and coding techniques may be used with certain embodiments of the invention, including those defined with the DVB-S2 and WiMAX standards. In a number of embodiments, the gateway115utilizes adaptive coding and modulation (ACM) in conjunction with one or more of the LDPC coding techniques described herein (e.g., according to the DVB-S2 specification) to direct traffic to the individual terminals. The gateway115may use a broadcast signal, with a modulation and coding (the term “modcode” may be used interchangeably herein in exchange with “modulation and coding”) format adapted for each packet to the link conditions of the user terminal130or set of user terminals130to which the packet is directed (e.g., to account for the variable service link150conditions from the satellite105to each respective user terminal130).

The gateway115may use an antenna110to transmit the signal to the satellite105. In one embodiment, the antenna110is a parabolic reflector with high directivity in the direction of the satellite and low directivity in other directions. The downstream signals135,150may include, for example, one (or more) single carrier signals. Each single carrier signal may be divided in time (e.g., using Time-Division Multiple Access (TDMA) or other time-division multiplexing techniques) into a number of sub-channels. The sub-channels may be the same size, or different sizes, and a range of options will be addressed below. In some embodiments, other channelization schemes may be integrated with or used in place of time-divided sub-channels, such as Frequency-Division Multiple Access (FDMA), Orthogonal Frequency-Division Multiple Access (OFDMA), Code-Division Multiple Access (CDMA), or any number of hybrid or other schemes known in the art.

In one embodiment, a geostationary satellite105is configured to receive the signals from the location of antenna110and within the frequency band and specific polarization transmitted. The satellite105may, for example, use a reflector antenna, lens antenna, array antenna, active antenna, or other mechanism known in the art for reception and/or transmission of signals. The satellite105may process the signals received from the gateway115and transmit the signal from the gateway115to one or more user terminals130. In one embodiment, the satellite105operates in a multi-beam mode, transmitting a number of narrow beams, each directed at a different region of the earth, allowing for frequency re-use. With such a multi-beam satellite105, there may be any number of different signal switching configurations on the satellite105, allowing signals from a single gateway115to be switched between different spot beams. In one embodiment, the satellite105may be configured as a “bent pipe” satellite, wherein the satellite105may frequency-convert the received carrier signals before retransmitting these signals to their destination, but otherwise perform little or no other processing on the contents of the signals. A variety of physical layer transmission modulation and coding techniques may be used by the satellite105in accordance with certain embodiments of the invention, including those defined with the DVB-S2 and WiMAX standards. For other embodiments, a number of configurations are possible (e.g., using LEO satellites, or using a mesh network instead of a star network), as evident to those skilled in the art.

The signals transmitted from the satellite105may be received by one or more user terminals130, via the respective user antenna125. In one embodiment, the antenna125and user terminal130together make up a very small aperture terminal (VSAT). In other embodiments, a variety of other types of antennas125may be used at the user terminal130to receive the signal from the satellite105. The user terminals130may each include an implementation (or aspects of the implementation) of the novel decoder architecture disclosed herein to decode the LDPC encoded data. Each of the user terminals130may be a single user terminal130or, alternatively, be a hub or router (not pictured) that is coupled with multiple user terminals130. Each user terminal130may be connected to consumer premises equipment (CPE)160(e.g., computers, local area networks, Internet appliances, wireless networks, etc.).

In one embodiment, a Multi-Frequency Time-Division Multiple Access (MF-TDMA) scheme is used for upstream links140,145, allowing efficient streaming of traffic while maintaining flexibility in allocating capacity among each of the user terminals130. In this embodiment, a number of frequency channels are allocated which may be fixed, or which may be allocated in a more dynamic fashion. A TDMA scheme is then employed in each frequency channel. In this scheme, each frequency channel may be divided into several timeslots that can be assigned to a connection (i.e., a user terminal130). In other embodiments, one or more of the upstream links140,145may be configured with other schemes, such as TDMA, FDMA, OFDMA, CDMA, or any number of hybrid or other schemes known in the art.

A user terminal130may transmit information related to signal quality to the gateway115via the satellite105. The signal quality may be a measured signal-to-noise ratio, an estimated signal-to-noise ratio, a bit error rate, a received power level, or any other communication link quality indicator. The user terminal130itself may measure or estimate the signal quality, or it may pass information measured or estimated by other devices. The user terminal130may specify a modcode to be used for transmission by the gateway115to the user terminal130, or to the set of user terminals130near the user terminal130. A user terminal130may also transmit data and information to a network120destination via the satellite105and gateway115. The user terminal130transmits the signals via the upstream uplink145to the satellite105using the antenna125. A user terminal130may transmit the signals according to a variety of physical layer transmission modulation and coding techniques, including those defined with the DVB-S2 and WiMAX standards. In various embodiments, the physical layer techniques may be the same for each of the links135,140,145,150, or may be different. The gateway115may, in some embodiments, use this signal quality information to implement ACM, adjusting the modcode formats to each user terminal130or set of user terminals130based on their link conditions. Thus, the gateway115may adapt the code rate of the LDPC codes for data to be transmitted downstream to user terminals130.

Turning now to the use of LDPC codes in the described satellite network100, the concept of LDPC codes may be generalized to all the linear block codes that can be represented by a sparse parity check matrix. These codes may be decoded using iterative soft-input soft-output (SISO) decoding, using one or more aspects of the novel decoder and edge memory architectures described herein. An iteration involves two processing stages—check node processing (CNP) and bit node processing (BNP). During the CNP stage, extrinsic information and parity bits involved in a parity check equation are gathered and new extrinsic information is calculated for all the related bits. During the BNP stage, the extrinsic information corresponding to the several parity check equations for any bit is combined to provide updated output information for the next iteration. In general, the information and parity bits may be referred to as bit nodes, and the parity check equations may be referred to as check nodes. The parity check matrix can be considered as an interconnection network between bit nodes and check nodes, and every connection is defined as an edge. It may be desirable to reduce the size of the edge memory, as the edge memory may occupy a large footprint in many conventional decoder designs. Aspects of the present invention relate to the storage of information in edge memory, and a novel indexing scheme to leverage certain redundancies inherent in some edge memory architectures to reduce the size of edge memory.

FIG. 2is an example200parity check matrix A and an associated bipartite graph. In the bipartite graph, each bit node b0-b7represents a corresponding column in the parity check matrix A, and each check node c0-c5represents a corresponding row in the parity check matrix A. The example parity check matrix A is not an actual LDPC parity check matrix, and is provided for illustrative purposes only. Each “1” represents a bit involved in a parity check. Thus, for each code word a=[a0, a1, . . . a7] received, the parity checks are based on:
a0+a3+a6+a7,
a1+a2+a4+a6, . . .
etc. The received code word may be represented by soft information, the values of which may be used to initialize a matrix according to the parity check matrix A for iterative decoding. For example, if the soft information generated from a received code word is [0.22, 0.17, 0.78, 0.80, 0.87, 0.10, 0.25, 0.33], then an initialized matrix X according to the parity check matrix ofFIG. 2would be:

Each connection between a bit node and a check node is an edge, and corresponds to a “1” in the parity check matrix A. Because the parity check matrix A has a column weight of 3 and a row weight of 4, each bit node is connected to three edges and each check node is connected to four edges. During the iterative decoding process, each check node provides a bit node estimate to a bit node based on information from other related bit nodes. Each bit node, in return, provides an estimate of its own value based on information from other related check nodes. The process continues until all parity check equations are satisfied, indicating a valid decode, or until a maximum number of iterations is reached without satisfying all parity check equations, indicating a decoding failure.

During decoding, a value may be assigned to each edge of a bipartite graph that is representative of a channel value associated with a bit node to which the edge is connected. Check nodes are then updated by accumulating the edge values according to a log-likelihood operation G:

Bit nodes may thereafter be updated with the update edge values by summing the edge values associated with the bit node. Thereafter, the system determines if all parity equations are satisfied or if a maximum number of iterations has been reached if all parity equations are not satisfied.

The interconnection between the bit nodes and check nodes in an LDPC code is typically pseudo-random. To facilitate high-speed decoding with reasonable complexity, a structure is often imparted in the code design so that the connections to the check nodes for a group of bit nodes are a linear translation of each other, i.e., some or all of the parity equations may be a linear translation of one particular parity equation. For example, a parity check matrix may define the following sets of linearly shifted parity check equations (1) and (2):
a0+a8+a16+a32=0,
a1+a9+a17+a33=0,
a2+a10+a18+a34=0 . . .  (1)
a0+a10+a20+a30=0,
a1+a11+a21+a31=0,
a2+a12+a22+a32=0 . . .  (2)
etc. Thus, in the linearly shifted parity check equation (1), operands a0, a1, and a2correspond to the first operand ap, operands a8, a9, and a10correspond to the second operand ap+8, and so on. Such a code structure facilitates parallelizing the decoding process.

Memory size and access can present unique implementation challenges. Multiple bits of soft-extrinsic information for all the edges between bit nodes and check nodes are stored. The memory for storing such information is often referred to as edge memory. Additionally, during the iterative decoding process, the bit node processors may require the original soft-input from the channel. The size of the various memories depends on the block size, the resolution of soft-information, and also the average number of edges per bit, and may be relatively large for large block code sizes. Additionally, a highly-parallel decoder will read from and write to memory stores in a highly-parallel fashion. Thus, for a degree of parallelism “p” the decoder may read and write p blocks of information at a time from these memories. For example, the sets of linearly shifted parity check equations (1) and (2) above define a first degree of parallelism p and a second degree of parallelism p. The values of p may differ for each degree of parallelism, e.g., the first degree of parallelism p may be 8, and the second degree of parallelism may be 16. The values of p may also be the same for some or all degrees of parallelism. Thus, edge memory can often encompass a large portion of the real estate in a decoder.

As illustrated above, powerful LDPC codes are based on complex interconnection of the bit nodes and check nodes, so gathering and storing the data to perform highly parallel check node processing and bit node processing operations is a design challenge for efficient decoder implementation. However, the information in the edge memory for many LDPC decoder designs may be simplified to create certain redundancies in the edge information. A novel indexing scheme is described herein to leverage these redundancies.

Referring toFIG. 3, a block diagram is shown illustrating an example configuration300for certain devices of the satellite communications system100ofFIG. 1. While the example configuration illustrates communication between a gateway115-aand a user terminal130-a, those skilled in the art will recognize that similar components may be used between other links for the same or other types of terminals, or between a satellite and a terminal.

In one embodiment, an initiating terminal (not shown) transmits data via a network (e.g. network120) to the gateway115-afor transmission downstream. The data is received by the gateway115-a. The received data may, for example, be a series of IP packets. The gateway115-aincludes an ACM/frame processing module310, an LDPC encoder module315, a channel interleaver module320, and a modulator module325.

After some intermediate processing by other components (not shown) of the gateway115-a, the data may be received by the ACM/frame processing module310. The ACM/frame processing module310may identify, for each of the packets of the stream, a modcode format from a number of different modcode formats. The identified modcode format may be based on the link condition associated with a destination for each respective packet.

ACM/frame processing module310may also define a series of frames. These may be frames defined according to the DVB-S2 framing format. Thus, the frames may each include a physical layer header to be transmitted at a very robust code rate. The physical layer header may include a unique word and signaling information. The payload for each frame may be encoded using LDPC codes at the adapted code rate (based on, for example, the link condition for the destination terminal or the type of programming).

Therefore, the ACM/frame processing module310may set the payload size and code rate for each frame, and thus determine the amount of information that is to be forwarded to the LDPC encoder module315for encoding for each frame. Turning briefly toFIG. 4, a block diagram illustrates an example LDPC block400for a frame. As noted, once the payload size and code rate are known for a frame, a block size for the information bits405is known. ACM/frame processing module310may forward the information bits405to the LDPC encoder module315. The LDPC encoder module315may then generate a set of parity bits410(e.g., according to the code rate and the DVB-S2 specification). Together, information bits405and parity bits410may make up the LDPC block400for a given frame.

Turning back toFIG. 3, the LDPC encoder315may forward the LDPC block400(which may be rearranged before transmission from the gateway115-ato facilitate parallel processing at the decoder) for a given frame to a channel interleaver module320for interleaving. The channel interleaver module320may perform intra-block interleaving and/or inter-block interleaving, based on channel characteristics. This channel interleaving may be based on any one of a number of traditional interleaving schemes known in the art. The channel interleaver module320may then forward the frame with the payload to be processed by the modulator module325for modulation (according to the assigned modulation format and DVB-S2 specification) and transmission via a wireless signal through the satellite105to the user terminal130-a.

At the user terminal130-a, the transmitted signal is received. The user terminal130-ain this embodiment is made up of a demodulator module355, channel de-interleaver module360, and LDPC decoder module365. These components (355-365) may be implemented, in whole or in part, in hardware. Thus, they may be made up of one, or more, Application Specific Integrated Circuits (ASICs) adapted to perform a subset of the applicable functions in hardware. Alternatively, the functions may be performed by one or more other processing units (or cores), on one or more integrated circuits. In other embodiments, other types of integrated circuits may be used (e.g., Structured/Platform ASICs, Field Programmable Gate Arrays (FPGAs), and other Semi-Custom ICs), which may be programmed in any manner known in the art. Each may also be implemented, in whole or in part, with instructions embodied in a computer-readable medium, formatted to be executed by one or more general or application specific processors. Thus, the device130-amay include different types and configurations of memory (not shown), which may be integrated into the hardware or may be one or more separate components.

The demodulator module355may downconvert, amplify, and demodulate the signal, thereby producing a soft-information version of the interleaved LDPC block (i.e., the block that was forwarded by the channel interleaver module320to the modulator module325). This is then forwarded to the channel de-interleaver module360, wherein the block (or blocks) are de-interleaved, thereby producing a soft-information version of the LDPC block400(i.e., the block that was forwarded by the LDPC encoder315to the channel interleaver module320). The channel de-interleaver module360may forward the soft-information version of the LDPC block400to the LDPC decoder365for decoding.

Turning next toFIG. 5, a block diagram illustrates a more specific example of an LDPC decoder500, which may be the LDPC decoder365ofFIG. 3. The LDPC decoder500includes input buffer505, a BNP accumulator510, an edge memory515, a BNP extrinsic information calculator520, CNP processors525, output buffer530, and controller535. The edge memory515may be located at the center of the decoder500, surrounded by CNP525and BNP510,520processing modules with their own memories. Thus, the BNP may be split into two parts: the BNP accumulator510and the BNP extrinsic information calculator520. When the CNP processors525are completed with processing and the edge information is ready to be written back to the edge memory515, the BNP accumulator510may collect the channel information and the extrinsic information for the edges associated with a particular bit.

The controller535may reformat the extrinsic information for storage in the edge memory515, which includes a value memory and an index memory. The edge memory515stores a set of possible values (in value memory), which may be relatively small. The edge memory515also stores an index for each edge (in index memory) identifying which value stored in the value memory applies to each respective edge. The determinations and calculations related to the value memory and index memory will be discussed in more detail below. At the other side of the of edge memory515, the BNP extrinsic information calculator520may ascertain the extrinsic information from the previous CNP iteration and subtract this extrinsic information from the aggregated BNP values to create the new extrinsic information inputs for the new iteration of CNP.

As noted, the edge memory515may store the reformatted extrinsic information for the edges for the LDPC code. For an LDPC code block (e.g., block400ofFIG. 4) of 64 Kb, there may be an average of three to four edges per bit. Moreover, to provide sufficient resolution for good performance, the extrinsic information for every edge in conventional designs may need to be a 6 bit or higher resolution number. In highly parallel designs, the edge memory may need to allow massively parallel read and write ports to support BNP and CNP parallel processing. The edge memory515may thus need to be large and two-port, while also being very wide and not so deep. The size and complexity of edge memory515can be significant. Thus, reducing the footprint of edge memory515using the described indexing architecture may provide cost and power saving advantages.

Turning to a more specific example discussion ofFIG. 5, the input buffer505is configured to store channel soft input (received, for example, from the channel de-interleaver module360ofFIG. 3). A BNP accumulator510may include a parallel BNP processor array. BNP accumulator510receives channel soft information. BNP accumulator510also receives the edge values coming from the CNP processors525, and sums these edge values with the original soft channel information X0for storage in edge memory515. As noted, the edge memory515may include a value memory and an index memory. The controller535may reformat the data from the BNP accumulator510to generate: 1) a set of possible values (for storage in the value memory portion of edge memory515), and 2) a set of data identifying which value stored in the value memory applies to each respective edge (for storage in the index memory portion of edge memory515).

BNP extrinsic information calculator520accesses the edge memory515, and generates extrinsic information for a particular edge by subtracting the original extrinsic information from the newly summed edge value of that edge. Thus, BNP extrinsic information calculator520subtracts extrinsic information of a previous CNP iteration from the accumulated BNP values to create the new extrinsic information inputs for the new iteration of CNP processing by the CNP processors525.

At any check node processor, the data for the different edges can be provided serially for a pipelined implementation or in batches for a parallel implementation. The BNP accumulator510thereafter updates the bit nodes with the updated edge values by summing the edge values associated with the bit node. When a determination is made that all parity equations are satisfied, output data may be stored in an output buffer530.

It is worth noting that the edge memory design described herein (e.g., including a value memory portion and an index memory portion) may be used in any number of LDPC decoder designs, and should not be limited to the specific design described above. For example, referring to the decoder design and the edge memory28described with reference to FIG. 2 of commonly assigned U.S. Pat. No. 7,760,880 entitled “Decoder Architecture System and Method” issued to Dave et al., the entirety of which is herein incorporated by reference for all purposes, a similar index memory/value memory design may be used.

A more specific example of the division of edge memory will now be set forth to further illustrate certain embodiments of the invention. This architecture may, for example, be used for storage of information in the edge memory515ofFIG. 5, but may be used in other edge memory architectures, as well.

First, it is worth providing an example of how extrinsic information may be generated in the CNP processing. One way to create the indexing scheme is to use a simplified G operation described with reference to FIGS. 3-7 of U.S. Pat. No. 7,760,880. Accumulations via the G operation yield a result that is dominated by smaller input values. A decoding algorithm may be based on log likelihood ratios that are, in turn, based on logarithms of probability calculations. Thus, the multiplication or division of probabilities involves simple additions or subtractions of the log likelihood ratios. Addition or subtraction of the log likelihood ratio values, however, may require special accumulation functions in the logarithmic domain. Depending upon the exact nature of the calculations, these accumulation functions have the tendency of being dominated by a small group of operands. The G operation is one such operation that has the tendency to produce an output dominated by a small subset of operands. In particular, the G operation has the tendency of producing an output that is dominated by the smaller of the input values.

The tendency of the G operation to produce an output dominated by the smaller input values may be exploited by using the indexing techniques and architecture described herein. In this decoding method, a forward pass through the input values is reduced to a selection process. The selection process may identify the operands among the incoming data that are likely to dominate the results of the operation (these may then be used for the set of possible values to be stored in value memory). The selection process may include a selection criterion that defines how the selections are made, and a selection value that defines how many selections are made. This may be the selection process described with reference to FIG. 6 of U.S. Pat. No. 7,760,880.

The selection criterion may be a property or metric that depends on the particular operation being simplified. For example, in some cases, the magnitude of the operands may be of primary interest, and thus the selection is made based on only the few smallest or largest values. Likewise, in some cases polarity may be the primary interest. The CNP selection criterion in one embodiment may be based on the smallest magnitudes of the input values, as the output of the G operation is dominated by these smaller input values.

The selection value reflects a trade-off between implementation complexity and accuracy. The actual trade-off depends upon the operation, but in general increasing the number of selections results in increased accuracy and better performance while also leading to increased computational complexity. For the G operation, a selection value of three will be used for purposes of example, although other selection values may also be used.

In one embodiment, a first step may be to find the least reliability edges for any CNP, and then perform the G operation on two out of these three values to generate the extrinsic information for all the edges. The extrinsic information has a sign dependent upon the XOR of the other edges, and the reliability is one out of three values (to be stored in a value memory portion of edge memory). Therefore, in the index memory portion of edge memory, if the sign is stored along with a reference to a reliability value (out of 3), only a three-bit storage would be needed per edge (in the index memory portion).

It is worth noting that three 5-bit extrinsic information values would not be stored for every set of edges for a check node. Instead, for a 64 Kb block size code of code rate 9/10, the storage requirement may be 64 Kb* 1/10*3*5=96 Kb for the value portion of edge memory. Thus, the memory requirement for this example may, in one embodiment, be reduced to approximately 850 Kb. Compare this to a conventional approach for an LDPC code of block size 64 Kb, where there is an average of 3-4 edges per bit, and to provide sufficient resolution for good performance, the extrinsic information for every edge needs to be a six bits or higher resolution number. This translates into a memory requirement for the conventional approach of approximately 1.5 Mb. Thus, in one example the memory requirement reduction may be approximately 45%.

Turning toFIG. 6, an example edge memory600design is disclosed. This edge memory600may be the edge memory515described with reference toFIG. 5, or may be implemented in any number of other decoders. The edge memory600architecture includes value memory605and index memory610. The value memory605stores a set of possible extrinsic information values for a check node. In the illustrated embodiment, there are three illustrated reliability values (C01, C02, C03), while in other embodiments there may be different numbers of values stored (see, e.g., the discussion on selection value above).

The index memory610, in this embodiment, stores an index value for each edge identifying which value stored in the value memory605applies to each respective edge. In one embodiment, there are three bits of information stored for each edge in the index memory610(one bit for sign, two bits to identify one of the three corresponding values in the value memory605).

The features of the various embodiments of FIGS.3and5-6may be implemented in a number of ways according to the specification. Further, the components and functionalities in those figures may be used to perform a number of different methods according to the specification.FIG. 7provides a flow diagram illustrating an example method for decoding encoded data that has been encoded according to a coding scheme defining a parity check matrix. The parity check matrix defines parity equations and edges between bit nodes and check nodes.

The method700may begin at block705by receiving channel soft information. Extrinsic information for edges may be accessed at block710(e.g., by the BNP accumulator510ofFIG. 5). Accumulated values for edges may be generated by summing the channel soft information and the extrinsic information for edges (e.g., by the BNP accumulator510) at block715.

At block720, the accumulated values for edges may be reformatted as multiple candidate values and multiple indexes, where each index identifies one of the candidate values as applying to a respective edge (e.g., by the controller535).

At block725, the reformatted accumulated values for edges may be stored as the multiple candidate values and the multiple indexes (e.g., by the edge memory515). In some implementations, the multiple candidate values are stored in a value memory portion of edge memory, and the multiple indexes are stored in an index memory portion of the edge memory. In some implementations, each index includes a reference to a respective candidate value and the sign of the respective candidate value.

Extrinsic information for edges of a previous CNP iteration may be accessed at block730, e.g., by the BNP extrinsic information calculator520. At block735, extrinsic information inputs for edges may be generated for a new CNP iteration by subtracting the extrinsic information for edges of the previous CNP iteration from the reformatted accumulated values for edges (e.g., by the BNP extrinsic information calculator520).

Extrinsic information output for edges may be generated using the extrinsic information inputs for edges at block740, e.g., by the CNP processors525. At block745, the bit nodes may be updated by summing the extrinsic information output for edges associated with the respective bit nodes. For example, the BNP accumulator510can update the bit nodes.

At block750, a determination may be made that all parity equations defined by the parity check matrix are satisfied. If it is determined that all parity equations are satisfied, output bit node data may be stored (e.g., by the output buffer530) at block755. If it is determined that not all parity equations are satisfied, another decoding iteration with the BNP and CNP stages can be performed. In some implementations, decoding terminates if a maximum number of decoding iterations are reached before all parity equations are satisfied.

In some implementations, reformatting the accumulated values for edges includes selecting based on a selection criterion and a selection value. For example, generating the extrinsic information output for edges may include generating output extrinsic information for edges with an accumulation operation using as operands the extrinsic information inputs for edges. Selecting can then include identifying the operands which have a higher probability of dominating results of the accumulation operation. In some implementations, the selection criterion is least reliability, the selection value is three, and selecting includes identifying the three operands which have the least reliability of the extrinsic information inputs for edges. In some implementations, the coding scheme includes an LDPC code.

Moreover, as disclosed herein, the term “memory” or “memory unit” may represent one or more devices for storing data, including read-only memory (ROM), random access memory (RAM), magnetic RAM, core memory, magnetic disk storage mediums, optical storage mediums, flash memory devices, or other computer-readable mediums for storing information. The term “computer-readable medium” includes, but is not limited to, portable or fixed storage devices, optical storage devices, wireless channels, a sim card, other smart cards, and various other mediums capable of storing, containing, or carrying instructions or data.

Furthermore, embodiments may be implemented by hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. When implemented in software, firmware, middleware, or microcode, the program code or code segments to perform the necessary tasks may be stored in a computer-readable medium such as a storage medium. Processors may perform the necessary tasks.