Preview

Journal of «Almaz – Antey» Air and Space Defence Corporation

Advanced search

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

https://doi.org/10.38013/2542-0542-2021-2-90-95

Abstract

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. The paper also gives an estimation of the LDPC coding efficiency with account for additional a priory information known for the signalcode sequence in use.

For citations:


Egorov I.V., Gaivoronskiy D.V. Improving the efficiency of LDPC decoding when using additional a priory information. Journal of «Almaz – Antey» Air and Space Defence Corporation. 2021;(2):90-95. https://doi.org/10.38013/2542-0542-2021-2-90-95

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 Eb/N0 (the ratio of bit energy to spectral density of noise power) during LDPC decoding: Eb/N0 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 Eb/N0 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 Eb/N0 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 * zT = 0H * zT = 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.

 

Fig. 1. 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 (ПСП0) with value 1 – ПСП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 Ic(t) and Qc(t) at its output.

Signals Ic(t) and Qc(t) are sent to four parallel correlators: correlator ПСП0 for Ic(t) with output Ic0(t), ПСП0 for Qc(t) with output Qc0(t), ПСП1 for Ic(t) with output Ic1(t) and ПСП1 for Qc(t) with output Qc1(t).

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

MAG0 (t) = I2c0(t) + Q2c0(t), (9)

MAG1 (t) = I2c1(t) + Q2c1(t), (10)

SYNC(t) = MAG0 (t) + MAG1 (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 ПСП0 or ПСП1), 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 MAG0 (t) and MAG1 (t) once signal SYNC(t) reaches its maximum.

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

LLRs(t) = log(MAG0 (t)) – log(MAG1 (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 Eb/N0, Fig. 3 – the dependence of the required number of iterations for complete recovery (if possible) on Eb/N0 (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 Eb/N0.

 

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 Eb/N0 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).

 

References

1. Shannon C. A mathematical theory of communication. The Bell System Technical Journal. Vol. 27. Issue 3. July 1948, P. 379 –423.

2. Gallager R. Low-density parity-check codes. IRE Transactions on information theory. 1962. № 8(1). P. 21–28.

3. Tanner R. A recursive approach to low complexity codes. IEEE transactions on information theory. 1981. № 27(5). P. 533–547.

4. Kou Y., Lin S., Fossorier M.P. Low-density parity-check codes based on finite geometries: a rediscovery and new results. IEEE Transactions on Information theory. 2001. № 47(7). P. 2711–2736.

5. Mohammad R.I., Dewan S.S., MuhammadM.A.F., Imran R. Optimized Min-Sum Decoding Algorithm for Low Density Parity Check Codes Dept. International Journal of Advanced Computer Science and Applications. 2011. Vol. 2. № 12. P. 172–174.

6. Amir H., Djahanshahi A.H. Optimizing and Decoding LDPC codes with Graph-Based Techniques. A dissertation submitted in partial satisfaction of the requirements for the degree. 2010. P. 16–80.

7. Johnson S. Introducing Low-Density ParityCheck Codes. University of Newcastle. May 2010, P. 8–9.

8. Short Blocklength LDPC Codes For Tc Synchronization And Channel Coding, CCSDS 231.0-O-x.x, 2012. P. 15–16.


About the Authors

I. V. Egorov
Saint Petersburg Electrotechnical University “LETI”
Russian Federation

Egorov Ivan Viktokrovich – Assistant Lecturer, Department of Radio Engineering Systems.
Science research interests: ultra-wideband radar and communication.

St. Petersburg



D. V. Gaivoronskiy
Saint Petersburg Electrotechnical University “LETI”
Russian Federation

Gaivoronskiy Dmitriy Vyacheslavovich – Candidate of Engineering Sciences, Associate Professor, Deputy Dean for Research, Faculty of Radio Engineering and Telecommunications, Associate Professor, Department of Radio Engineering Systems.
Science research interests: ultra-wideband radar and communication. 

St. Petersburg



Review

For citations:


Egorov I.V., Gaivoronskiy D.V. Improving the efficiency of LDPC decoding when using additional a priory information. Journal of «Almaz – Antey» Air and Space Defence Corporation. 2021;(2):90-95. https://doi.org/10.38013/2542-0542-2021-2-90-95

Views: 242


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.


ISSN 2542-0542 (Print)