HK1118991A - An interleaving scheme for an ldpc coded qpsk/8psk system - Google Patents

Description

Interleaving scheme for QPSK/8PSK system with low density parity check coding

Technical Field

The present invention relates to interleaving low density parity check ("LDPC") coded bits in a quadrature phase shift keying ("QPSK")/8 PSK modulation system. Specifically, by allocating bits that determine modulation symbols based on different bitdegrees (bit degrees), it is possible to effectively find a desirable compromise between the error performance and the error floor (error floor) provided by the LDPC code used.

Background

The authors investigated the performance of Modulation systems using 8PSK LDPC coding, published in "Bit-Reliability Mapping in LDPC-Codes Modulation systems" (Bit-Reliability Mapping in LDPC code Modulation systems) by Yan Li and William Ryan, IEEE Communications Letters, vol.9, no.1, january 2005. With the proposed bit reliability mapping strategy, a performance improvement of about 0.15dB over the non-interleaving scheme is achieved. The authors also explain the reason for this improvement using an analysis tool called an EXIT chart. In the interleaving scheme, an interleaving method is considered, and the result shows that the method provides better performance than a non-interleaving system, that is, in the bit reliability mapping scheme, LDPC code bits with low reliability are mapped to modulation bits with low order, and bits with higher reliability are mapped to bits with high order.

Forward Error Control (FEC) coding is important for communication systems to ensure reliable transmission of data over noisy channels. Based on Shannon's theory, these channels have a certain capacity in bits per symbol at a certain signal-to-noise ratio (SNR), which is defined as Shannon limit (Shannon limit). One of the most important research areas in communication and coding theory is to design coding schemes that provide performance approaching the shannon limit with reasonable complexity. LDPC codes using Belief Propagation (BP) decoding have been shown to have controllable encoding and decoding complexity and can provide performance approaching the shannon limit.

LDPC codes were originally described by Gallager in 1960. The performance of LDPC codes is very close to the shannon limit. An (N, K) binary LDPC code having a code length N and a dimension K is defined by a parity check matrix H of (N-K) rows and N columns. Most elements of the matrix H are 0 and only a small portion of the elements are 1, so the matrix H is sparse. Each row of the matrix H represents a checksum and each column represents a variable, e.g., a bit or a symbol. The LDPC code described by Gallager is regular, that is, the parity check matrix H has a constant row weight and column weight.

Regular LDPC codes can be extended to irregular LDPC codes, which vary in row and column weight. The irregular LDPC code is specified by degree distribution polynomials (x) and c (x) that define degree distributions of variable nodes and check nodes, respectively. More specifically, let

And

wherein the variable d _vmax And d _cmax Respectively, a maximum variable node degree and a check node degree, and v _j (c _j ) Represents the fraction (fraction) of an edge (edge) emanating from a variable (check) node of degree j.

While irregular LDPC codes are more complex to represent and/or implement, it has been shown theoretically and empirically that irregular LDPC codes with appropriately chosen degree profiles are superior to regular LDPC codes. Fig. 1 illustrates a parity check matrix diagram of an irregular LDPC code having a codeword length of 6.

LDPC codes may also be represented by bipartite graphs, or Tanner graphs. In the Tanner graph, one set of nodes, referred to as variable nodes (or bit nodes), corresponds to the bits of the codeword, while another set of nodes, referred to as constraint nodes (or check nodes), corresponds to a set of parity check constraints that define the LDPC code. The bit nodes and the check nodes have connecting edges. Bit nodes and check nodes are considered to be adjacent or neighboring if they have connecting edges. In general, it is assumed that a pair of nodes is connected by no more than one edge.

FIG. 2 illustrates a bipartite graph representation of an irregular LDPC code as shown in FIG. 1. The codeword length of the LDPC code represented by fig. 1 is 6 and has 4 parities. As shown in fig. 1, there are a total of 9 1's in the parity check matrix representation of the LDPC code. Thus, in the Tanner graph representation as in fig. 2, 6 bit nodes 201 are connected by 9 edges 203 to 4 check nodes 202.

LDPC codes can be decoded in a variety of ways, such as most logical decoding and iterative decoding. LDPC codes are mostly logically decodable because of the structure of their parity check matrices. While most logical decoding requires minimal complexity and exhibits reasonably good decoding performance for some types of LDPC codes (e.g., euclidean geometry LDPC codes and projective geometry LDPC codes) that have relatively high column weights in the parity check matrix, iterative decoding methods have gained more attention because they can achieve a better tradeoff between complexity and performance. Unlike most logical decoding, iterative decoding improves the reliability of each symbol by backtracking the received symbol based on constraints that define the pattern. In the first iteration, the iterative decoder uses only the channel output as input, producing a reliability output for each symbol. The reliability metric output for the decoded symbol at the end of each decoding iteration is then used as input for the next iteration. The decoding process ends until certain stopping conditions are met. A final decision is then made based on the reliability metric for the decoded symbol output for the last iteration. Iterative decoding algorithms can be further divided into hard decision, soft decision and hybrid decision algorithms, depending on the different characteristics of the reliability metric used at each iteration. The corresponding common algorithms are iterative Bit Flipping (BF), belief Propagation (BP), and Weighted Bit Flipping (WBF) decoding algorithms, respectively. It has been demonstrated that the BP algorithm is capable of maximum likelihood decoding when the corresponding Tanner graph is acyclic, and thus the algorithm becomes the most popular decoding method. Only BP decoding of LDPC codes will be discussed in the present invention described below.

BP of LDPC codes is a type of information-passing decoding. The information sent along the edges of the graph is the log-likelihood ratios associated with the variable nodes corresponding to the codeword bitsIn this expression, p ₀ And p ₁ Representing the probability of the relevant bit taking values 0 and 1, respectively. BP decoding comprises two steps: a horizontal step and a vertical step. In the horizontal step, each check node c _m Will be based on dividing from bit b _n All but c entering into the check _m The 'check-to-bit' information calculated from the 'bit-to-check' information is transmitted to the adjacent node b _n . In the vertical step, each bit node b _n Will be based on the division from check node c _m All but the incoming bit b _n Is sent to the adjacent check node c _m . These two steps are repeated until a usable codeword is found or the maximum number of iterations is reached.

Because of the significant performance of BP decoding, irregular LDPC codes are one of the best choices for many applications. Many communication and storage standards, such as DVB-S2/DAB, wireline ADSL, IEEE802.11n and IEEE802.16, etc., have adopted or are under consideration for the adoption of irregular LDPC codes. When considering the application of irregular LDPC codes in video broadcast systems, one often encounters problems due to error floor.

The error floor performance region of an LDPC decoder can be described by the error performance curve of the system. LDPC decoder systems generally exhibit a rapid decrease in the probability of error as the quality of the input signal increases. The resulting fault performance curve is generally referred to as a waterfall curve, and the corresponding region is referred to as a waterfall region. However, when a certain point is reached, the rate of decrease in the error probability corresponding to the improvement in the quality of the input signal becomes slow, and the resulting flat error performance curve is called an error floor. Fig. 3 exemplarily illustrates FER performance curves of an irregular LDPC code including a waterfall region 301 and an error floor region 302.

Disclosure of Invention

An interleaving method is disclosed in which, for LDPC code bits having an arbitrary level of reliability, a portion of low order modulation bits and a portion of high order modulation bits are mapped. For a particular LDPC code structure and modulation method, the optimal division of low order and high order modulation bits can be determined by a theoretical algorithm called density evolution.

In one embodiment of the present invention, there is provided a digital communication system for interleaving bits in a QPSK modulation system using an FEC code, the system including: a transmitter capable of generating a signal waveform to a receiver via a communication channel, the transmitter having an information source that generates a set of discrete bits with corresponding signal waveforms; and an LDPC encoder for generating a signal according to the character table and sending the signal to the signal mapper, wherein the interleaving is a non-continuous mapping capable of generating a minimum threshold value of the corresponding LDPC code predicted by density evolution.

By carefully selecting the check sum bit node degree distribution and the Tannner graph structure, the LDPC code has good threshold characteristics and can reduce the transmission power under the requirement of specific FER performance.

The threshold of the LDPC code is defined as a minimum SNR value at which the bit error probability can be made arbitrarily small when the codeword length tends to be infinite.

Different applications have different requirements on the threshold and error floor of LDPC codes. Therefore, there is a need to devise a decision method by which the determined mapping scheme in QPSK/8PSK system can provide the required threshold while keeping the error floor below a certain standard.

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 parity check matrix representation of an exemplary irregular LDPC code of codeword length six;

FIG. 2 illustrates a bipartite graph representation of an irregular LDPC code as shown in FIG. 1;

FIG. 3 illustrates an exemplary FER performance curve including waterfalls and error floor regions of irregular LDPC codes;

FIG. 4 is an exemplary communication system employing LDPC codes and an interleaver according to an embodiment of the present invention;

FIG. 5 illustrates an example of the transmitter of FIG. 4;

FIG. 6 illustrates an example of the receiver of FIG. 4;

fig. 7 illustrates a bit mapping function in QPSK modulation;

fig. 8 illustrates bit mapping of QPSK symbols;

fig. 9 illustrates a bit mapping function in 8PSK modulation;

fig. 10 illustrates bit mapping of 8PSK symbols.

Detailed Description

Although the present invention is described in terms of LDPC codes, it should be appreciated that bit labeling approach (bit labeling approach) may be used in other codes as well. In addition, this method can be implemented in a non-coded system.

Fig. 4 is a diagram of a communication system with an interleaver employing LDPC codes, according to an embodiment of the present invention. The communication system includes a transmitter 401 that generates a signal waveform that is transmitted over a communication channel 402 to a receiver 403. The transmitter 401 includes an information source that generates a discrete set of possible information. Each of these pieces of information corresponds to a certain signal waveform. The waveform enters the channel 402 and is degraded by noise. LDPC codes are employed to reduce interference introduced by channel 402. For a particular LDPC code and the level of error floor required, interleavers and deinterleavers are used in the transmitter 401 and receiver 403, respectively, based on some interleaving rule that yields a good threshold.

Fig. 5 depicts an exemplary transmitter in the communication system of fig. 4, in which an LDPC code and interleaver are employed. LDPC encoder 502 encodes information bits from source 501 into LDPC codewords. The mapping from each information block to each LDPC codeword is specified by the parity check matrix (or equivalent generator matrix) of the LDPC code. The LDPC codeword is interleaved and modulated into a signal waveform by an interleaver/modulator 503. These signal waveforms are sent to the transmit antenna 504 and propagated to the receiver as shown in fig. 6.

Fig. 6 depicts the exemplary receiver of fig. 4, in which an LDPC code and deinterleaver are employed. The signal waveform is received by a receiving antenna 601 and distributed to a demodulator/deinterleaver 602. The signal waveform is demodulated by a demodulator and deinterleaved by a deinterleaver, and then distributed to an LDPC decoder 603 that iteratively decodes the received message, and outputs an estimate of the transmitted codeword. The de-interleaving rules employed by the demodulator/de-interleaver 602 should match the interleaving rules employed by the interleaver/modulator 503. That is, the deinterleaving scheme should satisfy an anti-rule (anti-rule) of the interleaving scheme.

For a specific LDPC code and modulation scheme (QPSK or 8 PSK), we define the optimal interleaving as a non-continuous mapping means, which can generate the optimal threshold of the corresponding LDPC code predicted by density evolution.

QPSK

As shown in fig. 7, the QPSK bit-to-symbol mapping circuit acquires a pair of bits (b 2I, b2I + 1) at a time and maps them to an I value and a Q value, where I =0,1, 2. The mapping logic is shown in fig. 8, where the theoretical constellation points are defined as:

for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1, and imod2=0}, letIs the 2 bits that determine the ith symbol. Given the requirements of LDPC codes and error floor levels, an optimal interleaving scheme can be obtained through density evolution analysis. For efficiencies in "AfamiyofLDPCcodes for video cassette ligands" filed # # # # # " ¹ / ₄ 、2/5、 ¹ / ₂ 、3/5、2/3、 ³ / ₄ 4/5, 5/6, 13/15, and 9/10 LDPC codes for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1 and imod2=0}, the best interleaving rule predicted by the density evolution of QPSK is

Where _ x _ is a floor function (floor function) that returns the largest integer less than or equal to x.

8PSK

As shown in FIG. 9, the 8PSK bit-to-symbol mapping circuit obtains a triplet of bits (b) at a time _3i ，b _3i+1 ，b _3i+2 ) And mapping it to I and Q values, where I =0,1, 2. The mapping logic is shown in FIG. 10, where theoretical constellation points are mappedIs defined as follows:

in 8PSK, for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1, and imod3=0}, letIs 3 bits that determine the ith symbol. We specify N _offset To define the number of bit maps for each code efficiency. Given the requirements of LDPC codes and error floor levels, an optimal interleaving scheme can be obtained through density evolution analysis. For the "AfamiyofLDPCcodes for video decoding of proteins" filed ###, the efficiency is 3/5, 2/3, ³ / ₄ 4/5, 5/6, 13/15, and 9/10 LDPC codes for i ∈ i |0 ≦ i ≦ N _{ldpc_bits} -1 and imod3=0}, the interleaving rule for 8PSK is:

the bit offset numbers are listed in table 1.

Table 1: offset value for interleaving in 8PSK

Efficiency of	N Offset
		3/5	40
2/3	40
		3/4	80
5/6	88
		13/15	104
9/10	160

Claims (6)

1. A digital communication transmitter for interleaving LDPC coded bits in a QPSK modulation system based on the following rules:

for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1, and imod2=0}, where _ x _ is a rounding function that returns a maximum integer less than or equal to x, N _{ldpc_bits} =15360 is the codeword length of the LDPC code used.

2. A digital communication receiver employing an LDPC decoder which decodes interleaved LDPC coded bits in a QPSK modulation mode based on the following rules:

for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1, and imod2=0}, where _ x _ is a rounding function returning a largest integer less than or equal to x, N _{ldpc_bits} =15360 is the codeword length of the LDPC code used.

3. A computer-readable medium having stored thereon a computer program for executing a method capable of implementing an LDPC coded bit scheme interleaved based on the following rules in a QPSK modulation system:

for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1, and imod2=0}, where _ x _ is a rounding function returning a largest integer less than or equal to x, N _{ldpc_bits} =15360 is the codeword length of the LDPC code used.

4. A digital communication transmitter for interleaving LDPC coded bits in an 8PSK modulation system based on the following rules:

for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1, and imod3=0}, where _ x _ is a rounding function that returns the largest integer less than or equal to x, N _{ldpc_bits} =15360 codeword length of LDPC code used, and offset value N for different code rates _Offset Is defined as:

efficiency of N _Offset 3/5 40 2/3 40 3/4 80 5/6 88 13/15 104 9/10 160

。

5. A digital communication receiver employing an LDPC decoder that decodes interleaved LDPC coded bits in an 8PSK modulation system based on the following rules:

for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1, and imod3=0}, where _ x _ is the fetch that returns the largest integer less than or equal to xInteger function, N _{ldpc_bits} =15360 code of LDPC code usedWord length and offset value N for different code rates _Offset Is defined as:

efficiency of N _Offset 3/5 40 2/3 40 3/4 80 5/6 88 13/15 104 9/10 160

。

6. A computer-readable medium storing a computer program for executing a method capable of implementing an LDPC coded bit scheme interleaved based on the following rules in an 8PSK modulation system:

for i e { i |0 ≦ i ≦ N _{ldpc_bits} -1, and imod3=0}, where _ x _ is a rounding function that returns a maximum integer less than or equal to x, N _{ldpc_bits} =15360 codeword length of LDPC code used, and offset value N for different code rates _Offset Is defined as:

efficiency of N _Offset 3/5 40 2/3 40 3/4 80 5/6 88 13/15 104 9/10 160

。