HK1072840B - Method and apparatus for transmitting and receiving low density parity check codes - Google Patents

Description

Method and apparatus for transmitting and receiving low density parity check code

Technical Field

The present invention relates to communication systems, and more particularly to coding systems.

Background

Communication systems use coding to ensure reliable communication over noisy communication channels. These communication channels exhibit a fixed capacity, which can be expressed in terms of bits per symbol at a certain signal-to-noise ratio (SNR), thereby defining a theoretical upper limit, known as the Shannon (Shannon) limit. As a result, the goal of code design is to achieve rates approaching this shannon limit. One class of coding that approaches the shannon limit is Low Density Parity Check (LDPC) codes.

Conventional LDPC codes have not been widely used due to a number of disadvantages. One drawback is that LDPC coding techniques are very complex. Encoding an LDPC code using its generator matrix requires the storage of a very large non-sparse matrix. In addition, LDPC codes require large blocks to be efficient; therefore, even if the parity check matrices of the LDPC code are sparse, it is difficult to store the matrices.

From an implementation point of view, many challenges are faced. For example, storage is an important reason why LDPC codes have not been widely implemented. Also, a key challenge in LDPC code implementation is how to implement a connection network between several processing engines (nodes) in the decoder. Furthermore, the computational load during decoding, especially check node operation, faces difficulties.

For example, in broadcast applications, any cost impact on the receiver hardware including the LDPC decoder is far-reaching due to the amount of spread tuning with the receiver.

On the other hand, in some applications, such as satellite broadcast applications, the number of required transmitters is relatively small. This results in a transmitter that is much more costly than a receiver.

Therefore, it is desirable to configure a standard receiver to perform the encoding operation. In this way, the transmitter can enjoy the economy of the receiver.

Disclosure of Invention

These and other needs are addressed by the present invention, which provides a method for performing Low Density Parity Check (LDPC) encoding using LDPC decoder components. In one embodiment, the n-K bits are initialized according to a maximum value of likelihood ratios of the channel bits associated with a logical 0 value. The above method advantageously provides coding capabilities by sharing existing LDPC decoder hardware, thereby enhancing the functionality of the receiver at minimal cost. Because of the multiplicity of parallel processing engines that an LDPC decoder can use, the LDPC decoder can exploit these resources to provide fast and efficient encoding. Also, the above-described scheme advantageously eliminates the need to construct dedicated hardware for the encoder in the receiver. This can provide significant cost savings in satellite broadcast applications involving deployment of millions of receivers.

According to an aspect of an embodiment of the present invention, a method for supporting broadcast transmission of a Low Density Parity Check (LDPC) encoded signal to a plurality of receivers is disclosed. The method includes receiving an input signal by one of the receivers including an LDPC decoder. The method also includes encoding an input signal by the LDPC decoder to output an encoded signal.

According to another aspect of an embodiment of the present invention, an apparatus for receiving a broadcast transmission of a low density parity check encoded signal is disclosed. The apparatus comprises means for receiving an input signal via one of the receivers comprising an LDPC decoder. The apparatus also includes an LDPC decoder configured to encode an input signal to output an encoded signal.

According to yet another aspect of embodiments of the present invention, an LDPC decoder for generating a low density parity check code is disclosed. The LDPC decoder includes a processor configured to decode a received LDPC encoded signal. The processor is further configured to decode the encoded signal for interference cancellation of the received LDPC encoded signal.

According to an aspect of the present invention, there is provided a method for supporting broadcast transmission of a low density parity check, LDPC, encoded signal to a plurality of receivers, the method comprising:

receiving an input LDPC encoded signal with one of said receivers, said one of said receivers comprising an LDPC decoder; and

encoding the input LDPC encoded signal with the LDPC decoder to output an encoded LDPC signal.

According to another aspect of the present invention, there is provided a receiver apparatus for receiving broadcast transmission of a low density parity check, LDPC, encoded signal, the apparatus comprising:

means for receiving an input LDPC encoded signal by one of the receivers, the one of the receivers comprising an LDPC decoder; and

an LDPC decoder configured to encode the input LDPC coded signal to output a coded LDPC signal.

According to still another aspect of the present invention, there is provided an LDPC decoder for generating a low density parity check LDPC code, the LDPC decoder comprising:

a processor configured to decode the received LDPC encoded signal; and

wherein the processor is further configured to encode the decoded LDPC signal to perform interference cancellation on the received LDPC coded signal.

Other aspects, features and advantages of the present invention will become more apparent from the following detailed description, simply by illustrating a number of specific embodiments and implementations, including the best mode contemplated for carrying out the present invention. The invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the spirit and scope of the present invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive.

Drawings

The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which:

FIG. 1 is a schematic diagram of an LDPC decoder capable of performing LDPC encoding according to an embodiment of the present invention;

FIG. 2 is a diagram of a sparse parity check matrix according to an embodiment of the present invention;

FIG. 3 is a bipartite graph (bipartite graph) of the LDPC code of the matrix shown in FIG. 2;

FIG. 4 is a submatrix diagram of a sparse parity check matrix according to an embodiment of the present invention, wherein the submatrix contains parity values defined in a low triangular region;

FIG. 5 is a flowchart of the operation of the LDPC decoder shown in FIG. 1 for encoding data according to an embodiment of the present invention;

FIG. 6 is a flowchart of a modified operation of the LDPC decoder shown in FIG. 1 for encoding data according to an embodiment of the present invention; and

FIG. 7 is a diagram of a computer system that can perform the process of encoding and decoding LDPC codes according to an embodiment of the present invention.

Detailed Description

Systems, methods, and software are described for efficiently encoding Low Density Parity Check (LDPC) codes. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It is apparent, however, to one skilled in the art that the present invention may be practiced without these specific details or with an equivalent arrangement. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

Fig. 1 is a schematic diagram of a Low Density Parity Check (LDPC) decoder capable of performing LDPC encoding according to an embodiment of the present invention. Generally, an LDPC encoding process involves receiving an input from an information source at a receiver and outputting a stream of highly redundant encoded data suitable for error correction processing. For example, the information source generates k signals from a discrete alphabet X. The LDPC code is specified by a parity check matrix. Encoding LDPC codes, on the other hand, typically requires specifying a generator matrix. Even though it is possible to obtain a generator matrix from a parity check matrix by using Gaussian (Gaussian) elimination, the resulting matrix is no longer sparse and it is complicated to store a large generator matrix.

The LDPC encoding process generates a signal from the letter Y to the modulator using a simple encoding technique that uses only the parity check matrix by adding a structure to the parity check matrix. Specifically, the constraint is placed on the parity-check matrix by constraining some portion of the matrix to be triangular. The construction of such a parity check matrix is fully described in fig. 4. This limitation results in negligible performance loss and therefore constitutes an attractive compromise.

As shown, the functional components that support the LDPC encoding process by LDPC decoder 101 include a received vector construction module 103, an LDPC decoder initialization module 105, and a check node processing module 107. The check node processing module 107 outputs to an adder 111 which calculates the sum of the previous outputs stored in the register 109. These modules 103, 105, 107 operate cooperatively to encode new information or re-encode the received data stream (as in interference cancellation applications). This process will be described in more detail with reference to fig. 5 and 6.

In order to understand the advantages offered by the present invention, it is suggested to carefully observe how the LDPC code described below is generated.

FIG. 2 is a diagram of a sparse parity check matrix according to an embodiment of the present invention. The LDPC code is a code having a sparse parity check matrix H_(n-k)xnLong, linear block codes. Typically, the length n of the block ranges from thousands of bits to tens of thousands of bits. For example, a parity check matrix of an LDPC code having a length n of 8 and a ratio of 1/2 is depicted in fig. 2. The same code is represented equally by the even graph in each figure 3.

FIG. 3 is an even graph of the LDPC code of the matrix shown in FIG. 2. The parity check equation shows that for each check node, the sum of all neighboring bit nodes (over GF (galois field) (2)) is equal to 0. As shown in the figure, the bit nodes occupy the left side of the graph and are associated with one according to a predetermined relationshipOne or more check nodes are iteratively associated. For example, corresponding check node m₁The following expressions for bit nodes exist: n is₁+n₄+n₅+n₈＝0

Returning to the example of fig. 1, LDPC decoder 101 is considered a message passing decoder, where the purpose of LDPC decoder 101 is to find the values of the bit nodes. To accomplish this task, the bit nodes and check nodes repeatedly communicate with each other. The nature of this communication is described below.

From check node to bit node, each check node provides an estimate ("belief") of the value of that bit node to the adjacent bit node based on information from other adjacent bit nodes. For example, in the example above, if for m₁，n₄，n₅And n₈The sum of (a) is "seemingly" 0, then m₁Indication n₁，n₁Must be 0 (because n₁+n₄+n₅+n₈0); otherwise m₁Indication n₁，n₁The value of (d) must be 1. Furthermore, for soft decision decoding, the reliability measure can be increased.

From bit node to check node, each bit node passes on to its other neighboring check nodes an estimate of its own value based on feedback from its neighboring check nodes. In the above example, n₁With only two adjacent check nodes m₁And m₃. If from m₃To n₁Is displayed by feedback n₁Is approximately 0, then n₁Will inform m₁，n₁The own estimate is 0. For the case where a bit node has more than 2 neighboring check nodes, the bit node performs a majority vote (soft decision) based on feedback from other neighboring check nodes before reporting that check node that decides to communicate to it. The above process is repeated until all bit nodes are considered correct (i.e., all parity equations are satisfied), or until a predetermined maximum number of iterations is reached, thereby declaring a parity check that is correctDecoding the failure.

Fig. 4 is a submatrix diagram of a sparse parity check matrix according to an embodiment of the present invention, wherein the submatrix includes parity values defined in a low triangular region. As described above, the LDPC encoding process can use a simple encoding technique by defining the values of the low triangular region of the parity check matrix. According to an embodiment of the present invention, the definition imposed on the parity check matrix is of the form:

H_(n-k)xn＝[A_(n-k)xkB_(n-k)x(n-k)]where B is a low triangle.

Any information block i ═ i (i)₀，i₁，...，i_k-1) By using Hc^T0 and recursively solves for parity bits to encode a codeword c ═ (i)₀，i₁，...，i_k-1，p₀，p₁，...，p_n-k-1) (ii) a For example

And also for p₂，p₃，...，p_n-k-1.

Since the LDPC decoder 101 can be implemented as a highly parallel system, a properly designed encoder using hardware for decoding is very efficient in terms of processing time. Thus, the encoding process can "steal" clock cycles without affecting normal decoding operations. In terms of hardware cost, little or no additional cost is added to the LDPC decoder 101 by advantageously adjusting the encoding of the decoder hardware.

For purposes of explanation, the focus of attention is on a particular family of LDPC codes (depicted in fig. 4), although the methods of the present invention may be applied to other LDPC codes. The code set is continued according to the form of matrix operation, the computation of the parity bits is expressed as follows:

the encoding is done by performing the above matrix multiplication. This encoding process is suitable for the LDPC decoder 101. For purposes of explanation, it is assumed that LDPC codes are decoded by trusted propagation.

Two cases can be considered: the first case includes using the hardware of the LDPC decoder 101 to encode generally any information (fig. 5 and 6); and the second case involves re-encoding data decoded by the same hardware. In principle, the second case is a special case of the first case, and therefore its processing is exactly the same as the first case. Optionally, some of the advantages of dealing with the second case are noted differently than the specific case where this case is only treated as a previous method.

FIG. 5 is a flowchart illustrating operation of the LDPC decoder of FIG. 1 for encoding data according to an embodiment of the present invention. It should be appreciated that any hardware implementation must use limited precision. Thus, the definition is as follows: let POSINF and neglnf, which are the maximum values of the likelihood ratios of a particular channel bit, respectively, take 1 or-1 (logical 0 or 1, respectively). The encoding algorithm for the first case is as follows.

In step 501, the LDPC decoder 101, per module 103, constructs a "receive vector" from the k information bits to be encoded such that the first k received values are mapped from the k information bits, logic 0 to POSINF and logic 1 to neglnf. The last n-k received values are also wave initialized to POSINF. Next, by performing normal initialization of the LDPC decoder 101, the LDPC decoder 101 is initialized with the construction vector (values of all edges) by the module 105 as by step 503.

In step 505, for the ith check node, check node processing engine 107 calculates the following:

wherein v is_iIs the number of edges connected to the ith check node. Without loss of generality, assumeIs an edge connected to a bit node corresponding to one non-information bit (parity bit).

Next, as in step 507, the LDPC decoder 101 performs a hard decisionTo a binary bit directionFinal parity checkThe following is calculated (step 509):

from the above process, it is observed that the encoding process can also be performed by LDPC decoder 101 with the computation time of one iteration of LDPC decoder 101. Given the fact that LDPC decoder 101 typically requires at least tens of iterations to decode most of the codes, the time to perform encoding is a relatively small fraction of the time used to decode a typical LDPC frame.

FIG. 6 is a flow diagram of the improved operation of the LDPC decoder shown in FIG. 1 for encoding data according to an embodiment of the present invention. The modified process is similar to that of fig. 5; however, in step 601, the last n-k received values are initialized to "DON' T CARE" (or null) instead of POSNF. Step 603-.

FIG. 7 illustrates a computer system upon which an embodiment of the invention may be implemented. Computer system 700 includes a bus 701 or other communication mechanism for communicating information, and a processor 703 coupled to bus 701 for processing information. The computer system 700 also includes main memory 705, such as a Random Access Memory (RAM) or other dynamic storage device, coupled to the bus 701 for storing information and instructions to be executed by the processor 703. Main memory 705 can also be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 703. The computer system 700 further includes a Read Only Memory (ROM)707 or other static storage device coupled to the bus 701 for storing static information and instructions for the processor 703. A storage device 709, such as a magnetic disk or optical disk, is additionally coupled to the bus 701 for storing information and instructions.

Computer system 700 is coupled via bus 701 to a display 711, such as: cathode Ray Tubes (CRTs), liquid crystal displays, active matrix displays, or plasma displays are used to display information to a computer user. An input device 713, such as a keyboard including alphanumeric and other keys, is coupled to the bus 701 for communicating information and command selections to the processor 703. Another type of user input device is cursor control 715, such as: a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 703 and for controlling cursor movement on display 711.

According to one embodiment of the invention, the computer system 700 provides for the generation of LDPC codes in response to processor 703 executing an arrangement of instructions contained in main memory 705. Such instructions may be read into main memory 705 from another computer-readable medium, such as the storage device 709. Execution of the arrangement of instructions contained in main memory 705 causes the processor 703 to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the instructions contained in main memory 705. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the embodiment of the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

Computer system 700 also includes a communication interface 717 coupled to bus 701. The communication interface 717 provides a two-way data communication coupling to a network link 719, the network link 719 connecting to a local network 721. For example, the communication interface 717 may be a Digital Subscriber Line (DSL) card or modem, an Integrated Services Digital Network (ISDN) card, a cable modem, or a telephone modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 717 may be a Local Area Network (LAN) card (e.g., Ethernet)^TMOr an Asynchronous Transfer Mode (ATM) network) to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 717 sends and receives electrical, electromagnetic, or optical signals that carry digital data streams representing various types of information. In addition, the communication interface 717 may include peripheral interface devices such as: a Universal Serial Bus (USB) interface, a PCMCIA (personal computer memory card international association) interface, etc.

The network link 719 typically provides data communication through one or more networks to other data devices. For example, the network link 719 may provide a connection to a host 723 over a local area network 721 having a connectivity to a network 725 (such as a Wide Area Network (WAN) or the global packet data communication network now commonly referred to as the "Internet") or to data devices operated by a service provider. Local network 721 and network 725 both use electrical, electromagnetic or optical signals to convey information and instructions. The signals through the various networks and the signals on the network link 719 and through the communication interface 717, which exchange digital data with the computer system 700, are exemplary forms of carrier waves carrying information and instructions.

Computer system 700 can send and receive messages and data, including program code, through the network(s), network link 719 and communication interface 717. In the Internet example, a server (not shown) might transmit requested code belonging to an application program for executing an embodiment of the present invention through the network 725, the local network 721 and the communication interface 717. The processor 703 may execute the transmitted code as it is received, and/or store the code in the storage device 709, or other non-volatile storage for later execution. In this manner, computer system 700 may obtain application code in the form of a carrier wave.

The term "computer-readable medium" as used herein refers to any medium that participates in providing instructions to processor 703 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, and transmission media. Non-volatile media include: such as an optical or magnetic disk, for example, storage device 709. Volatile media includes dynamic memory, such as main memory 705. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus 701. Transmission media can also take the form of acoustic, light, or electromagnetic waves, such as those generated during Radio Frequency (RF) and Infrared (IR) data communications. Computer readable media generally comprises in form: for example: a floppy disk, a flexible disk, hard disk, magnetic tape, any other magnetic medium, a CD-ROM, CDRW, DVD, any other optical medium, punch cards, paper tape, optical mark sheets, any other physical medium with patterns of holes or other optically recognizable indicia, a RAM, a PROM, an EPROM, a FLASH-EPROM, any other memory chip or cartridge, a carrier wave, or any medium from which a computer can read.

Various forms of computer readable media may be involved in carrying out the instructions to a processor for execution. For example, the instructions for carrying out at least part of the present invention may initially be borne on a magnetic disk of a remote computer. In this scenario, the remote computer loads the instructions into main memory and sends the instructions over a telephone line using a modem. A modem of a local computer system receives the data on the telephone line and uses an infrared transmitter to convert the data to an infrared signal and transmit the infrared signal to the portable computing device, such as: personal Digital Assistants (PDAs) and laptop computers. An infrared detector on the portable computing device receives the information and instructions carried by the infrared signal and places the data on a bus. The bus transfers data to main memory, from which the processor retrieves instructions and executes the instructions. The instructions received by main memory are optionally stored on storage device either before or after execution by processor.

Accordingly, various embodiments of the present invention provide a method for supporting broadcast transmission of a Low Density Parity Check (LDPC) encoded signal to a plurality of receivers. The receiver includes an LDPC decoder that decodes the LDPC signal to output a decoded signal and encodes the input signal. The input signal may be a decoded signal, whereby the re-encoded signal is used for interference cancellation. The above approach advantageously avoids the need to configure a separate, dedicated encoder in the receiver.

While the invention has been described in connection with a number of examples and embodiments, the invention is not so limited, but includes various obvious modifications and equivalents within the scope of the appended claims.

Claims (19)

1. A method for supporting broadcast transmission of a low density parity check, LDPC, encoded signal to a plurality of receivers, the method comprising:

receiving an input LDPC encoded signal with one of said receivers, said one of said receivers comprising an LDPC decoder; and

encoding the input LDPC encoded signal with the LDPC decoder to output an encoded LDPC signal.

2. The method of claim 1, further comprising: the LDPC decoder (101) decodes the LDPC signal to output a decoded LDPC signal.

3. The method of claim 2, wherein the input LDPC encoded signal is the decoded LDPC signal and the encoded LDPC signal is used for interference cancellation of the received LDPC signal.

4. The method of claim 2, wherein the decoding and encoding steps are performed simultaneously.

5. The method of claim 4, further comprising:

constructing a reception vector based on the first k information bits of the decoded signal; and

initializing the LDPC decoder using the received vector.

6. The method of claim 5, wherein the received vector is n in length and n-k bits are initialized according to a maximum of likelihood ratios of channel bits associated with logical zero values.

7. The method of claim 5, wherein the length of the received vector is n, and n-k bits are initialized according to a maximum value of likelihood ratios of channel bits associated with a null value.

8. The method of claim 1, wherein the LDPC signal is received over a satellite link.

9. The method of claim 1, wherein the LDPC encoded signal is modulated according to a signal constellation comprising: one of 8-PSK, 16-QAM, 16-APSK, 32-APSK and QPSK.

10. A receiver apparatus for receiving a broadcast transmission of a low density parity check, LDPC, encoded signal, the apparatus comprising:

means for receiving an input LDPC encoded signal by one of the receivers, the one of the receivers comprising an LDPC decoder; and

an LDPC decoder configured to encode the input LDPC coded signal to output a coded LDPC signal.

11. The apparatus of claim 10, further comprising: the LDPC decoder decodes the LDPC signal to output a decoded LDPC signal.

12. The apparatus of claim 11, wherein the input LDPC encoded signal is the decoded LDPC signal and the encoded LDPC signal is used for interference cancellation of the received LDPC signal.

13. The apparatus of claim 11, wherein the LDPC decoder performs the decoding and encoding simultaneously.

14. The apparatus of claim 11, wherein the LDPC decoder is further configured to construct a receive vector based on the first k information bits of the decoded signal and initialize the LDPC decoder with the receive vector.

15. The apparatus of claim 14, wherein the received vector length is n and the n-k bits are initialized based on a maximum value of likelihood ratios of channel bits associated with logical zero values.

16. The apparatus of claim 14, wherein the receive vector length is n, and n-k bits are initialized according to a maximum value of likelihood ratios of channel bits associated with a null value.

17. The apparatus of claim 10, wherein the LDPC signal is received over a satellite link.

18. The apparatus of claim 10, wherein the LDPC encoded signal is modulated according to a signal constellation comprising: one of 8-PSK, 16-QAM, 16-APSK, 32-APSK and QPSK.

19. A decoder for generating a low density parity check, LDPC, code, the decoder comprising:

a processor configured to decode the received LDPC encoded signal; and

wherein the processor is further configured to encode the decoded LDPC signal to perform interference cancellation on the received LDPC encoded signal.