Improving the efficiency of LDPC decoding when using additional a priory information

Introduction

In 1948, C. Shannon [1] proved that reception errors caused by the channel noise could be minimised by using a sufficiently lengthy code word (by implementing sufficient redundancy into data to be transmitted).

LDPC codes (low-density parity-check codes) are a code family with error checking. The theory of LDPC was developed by R. Gallager [2] in the 1960s, but codes were not widely used for about two decades. In the 1980s, once computers with sufficient performance appeared, the approaches proposed by R. Gallager were further developed [3].

LPDC code is a code with a low-density parity-check matrix [4], i.e. the number of ones in the matrix is smaller than the number of zeros.

Nowadays, there are many methods intended to reduce the bit error rate (BER) at fixed ratio E_b/N₀ (the ratio of bit energy to spectral density of noise power) during LDPC decoding: E_b/N₀ estimation [5], additional correcting estimation at decoding steps [6] and other methods.

The paper describes LDPC decoding with account for packet synchronisation information, which, based on the principle of data generation, is more reliable than the information to be transmitted and interpreted as a priori known information.

LDPC coding and decoding

LDPC coding and decoding implies the selection of sizes of the initial data block (K), code rate (K/N, where N is the coded data block size) and generator matrix H of size [M × N], where M = N – K.

We are not going to analyse specific features of generating matrices, their classification, properties and generation methods, but we should note that the coding procedure requires matrix G of size [K × N], which can be acquired through appropriate transformations from matrix H [7]. Communication channel standards or noiseless coding standards usually specify both matrices.

Matrix G is a system of two matrices: identity matrix I of size [K × K] and matrix W of size [M × K].

Coding
The coding matrix can be represented as follows: the source data vector is transposed and multiplied by matrix G, then values in each column of the generated matrix are added as per the required field modulus. The resultant array of size N is a coded data block.

Assume that in is the initial data array, and out is a code message. In this case, the LDPC coding algorithm will be as follows (1):

out(i) = Σ_{j = 1:M} in(j) * G(j, i), (1)
where i = 1:N.

Decoding
For different conditions of data corruption and its detection, different types of decoding, optimised in terms of computational resources and correction effect, were developed: decoding with erasure, bit-flipping decoding, sum-of-products algorithm, minimum sum algorithm, modified minimum sum algorithms, etc.

The first two types are used if additional information is not available (estimation of E_b/N₀ ratio, character probability characteristics, etc.; errors in any accepted character are assumed to be equally probable). They are the least intensive in terms of computational resources. These types are used for channels with a relatively high E_b/N₀ ratio [7].

The last three types imply (but do not require) that additional information about the data is available.

Decoding algorithms of the last three types
Assume that r is an input data array represented in the format of logarithmic likelihood ratios (LLR), A(i) are indices of non-zero cells of matrix H of column i, B(j) – indices of non-zero cells of matrix H of row j.

The sum-of-products algorithm is represented as follows:
1. Preparation step (generation of matrix M): M(j, i) = r(i), (2)
where i ∈ B(j), j ∈ A(i).

2. Horizontal step (computation of matrix E):

 (3)
where i ∈ B(j), j ∈ A(i).

3. Vertical step (computation of vector L and vector z):

L(n) = r(n) + Σ _{i ∈ B( j), j ∈ A(i)} E( j, i), (4)

 (5)
where n = 1:N.

4. Decoding completion check:
if
H * z^T = 0H * z^T = 0, (6)
then decoding is completed.

5. Transition to the next iteration (generation of matrix M):

M( j, i) = r(n) + Σ _{j'∈ A(i), j'≠ j} E( j', i), (7)
where n = 1:N, i ∈ B( j), j ∈ A(i).

Steps 2–5 are called the decoding iteration and repeated as many times as necessary. The number of iterations is expected to increase the probability of correct data decoding. If array z is used as an output array, there will be a hard-output decoder; if L – a soft-output decoder.

We should note that the completion check step (6) may be used not at every iteration or may not be used at all, i.e. a decoder can operate in the mode with a fixed number of iterations.

The minimum sum algorithm duplicates the algorithm described above, except for the horizontal step (expression (8) shall be used instead of expression (3)):

 (8)
where i ∈ B( j), j ∈ A(i).

The distinctive feature of modified minimum sum algorithms is the presence of correction factors at different steps, which depend on Eb/N0 estimation, signal power estimation, etc.

Data packet generation and processing

To explain the proposed method, we shall take a quick look at the applicable signal-code sequence. Fig. 1 shows the transceiver block diagram.

The receiver’s initial data is an array of 224 bits in size. Packet synchronisation bits are added to an array as follows: a bit with the relevant index belonging to the 31-element pseudo-random M-sequence is placed between every 7 data bits (ПСП_с).

[Data [0..6]] [ПСП_с [0]] [Data[7:13]] [ПСП_с [1]]...

As a result, we have a data array of 255 bits in size, which has one additional reserved bit.

The resulting data array is sent to the LDPC coder block with code rate of 1/2. In an output packet of 512 bits in size, check bits are arranged in the first half of the packet, and data bits – in the second half.

The packet is sent to the pseudo-random sequence spread spectrum block, which, according to the value of the relevant bit equal to 0, generates a 31-element pseudo-random m-sequence (ПСП₀) with value 1 – ПСП₁.

The next link is the ФМ-2 modulator, then the signal is emitted into space.

The receiving side has a quadrature modulator installed after the antenna and feeder device, with signals I_c(t) and Q_c(t) at its output.

Signals I_c(t) and Q_c(t) are sent to four parallel correlators: correlator ПСП₀ for I_c(t) with output I_c0(t), ПСП₀ for Q_c(t) with output Q_c0(t), ПСП₁ for I_c(t) with output I_c1(t) and ПСП₁ for Q_c(t) with output Q_c1(t).

Magnitudes of pseudo-channel 0 (MAG₀ (t)) (9) and pseudo-channel 1 (MAG₁ (t)) (10), as well as sync signal (SYNC(t)) as their sum (11) are calculated at the next step:

MAG₀ (t) = I²_c0(t) + Q²_c0(t), (9)

MAG₁ (t) = I²_c1(t) + Q²_c1(t), (10)

SYNC(t) = MAG₀ (t) + MAG₁ (t). (11)

The next data processing block is a pre-synchroniser, which, using signal SYNC(t) and possessing the information about the data recurrence rate, searches an approximate interval as per the criteria of the maximum of signal SYNC(t) in the known interval (duration ПСП₀ or ПСП₁), as well as per the criterion of recurrence regularity for these maxima. Irrespective of the synchronization quality at the current time, the synchroniser displays a validity signal for signals MAG₀ (t) and MAG₁ (t) once signal SYNC(t) reaches its maximum.

In response to signals MAG₀ (t) and MAG₁ (t), signal LLRs(t) (12) is calculated to be sent to the packet synchronisation block.

LLRs(t) = log(MAG₀ (t)) – log(MAG₁ (t)). (12)

The packet synchronisation block has a memory with the depth of 521 cells for input LLR storage. Each time a new report on signal LLRs(t) is received, data are written to the end of memory, while any data stored in memory are shifted by one cell, with a report removed from the low core. The current memory state is checked for compliance with the moment of packet reception completion time using correlator ПСП_c (relevant bits of the expected packet are analysed). Once the ПСП_c correlation peak exceeds the threshold to be calculated as per the previous peaks, this is viewed as the criterion of packet detection.

If a packet is successfully detected, maximum LLR values corresponding to ПСП_c bits are placed in packet synchronisation bit positions. Therefore, ПСП_c known to the receiver is used as a priori information.

A received packet is sent for processing to the LDPC decoder operating as per the minimum sum algorithm with the completion check step described above. Matrices from experimental standard CCSDS 231.0-O-x.x for satellite communication system [8] are used as matrices H and relevant matrix G for the coding/decoding procedure.

LDPC decoding efficiency evaluation

LDPC decoding efficiency was evaluated by using a simulation method in the Matlab environment.

Fig. 2 shows the dependence of BER on E_b/N₀, Fig. 3 – the dependence of the required number of iterations for complete recovery (if possible) on E_b/N₀ (maximum number of iterations is 50). A channel with additive white Gaussian noise is used as the channel. Random data sampling size is 10e5 bits for each value of E_b/N₀.

In the first case (a blue dot line in Figs. 2 and 3), the LLR values in packet synchronisation bit positions remained unchanged; in the second case (a red line in Figs. 2 and 3), they changed as per the algorithm described above.

According to simulation results, the packet synchronisation bit LLR correction, with account for prior knowledge of their values (ПСП_c), allows to reduce the number of iterations (by 1.5 times) during decoding, and BER (by 7 times) for the E_b/N₀ range of –2.6 to 0 dB.

Conclusion

The proposed method of bit LLR correction, based on prior knowledge of bit packet synchronisation for the represented signal-code sequence, allows to improve the LDPC decoding performance (to reduce the number of iterations by 1.5 times until the similar BER is reached; to reduce BER by 7 times for the same number of iterations).