LDPC coding with differentiated protection

Abstract

A new unequal-error-protection method that is based on using a particular parity-check-matrix structure for LDPC codes.

Claims

1. A method for encoding a binary message (M) composed of a first sub-message having a first priority level and of a second sub-message having a second priority level, using an LDPC code defined by a parity-check matrix H having a first dimension corresponding to the bits of the coded binary message (M.sub.c) and a second dimension, the parity-check matrix H consisting of four sub-sets (ES.sub.1,ES.sub.2,ES.sub.3,ES.sub.4) of two sub-matrices that are concatenated in the second dimension, the four sub-sets (ES.sub.1,ES.sub.2,ES.sub.3,ES.sub.4) being concatenated in the first dimension, the first sub-matrix (J.sub.1) of the first sub-set (ES.sub.1) taking the form ##STR00004## where x is equal to the size of half of the first sub-message, y is equal to the size of half of the second sub-message, I is an identity matrix of dimensions (x,x) and G.sub.1 is a nonzero matrix of dimensions (x,y), the second sub-matrix (H.sub.1) of the first sub-set (ES.sub.1) being a nonzero matrix, the first sub-matrix of the second sub-set (ES.sub.2) being a zero matrix, the second sub-matrix (H.sub.2) of the second sub-set (ES.sub.1) being a nonzero matrix, the first sub-matrix (H.sub.3) of the third sub-set (ES.sub.3) being a nonzero matrix, the second sub-matrix (J.sub.2) of the third sub-set (ES3) taking the form ##STR00005## where G.sub.2 is a nonzero matrix of (x,y) dimensions, the first sub-matrix (H.sub.4) of the fourth sub-set (ES.sub.4) being a nonzero matrix, and the second sub-matrix of the fourth sub-set (ES.sub.4) being a zero matrix, the sub-matrices (H.sub.1, H.sub.2, H.sub.3, H.sub.4, J.sub.1, J.sub.2) of the four sub-sets been square and of dimensions (x+y,x+y), the encoding method comprising a step of encoding the binary message (M) using the parity-check matrix H to produce the coded binary message (M.sub.c).

2. The method for encoding a binary message according to claim 1, wherein the coded binary message (M.sub.c) is composed of two independent coded sub-messages each comprising data bits corresponding to one half of the first sub-message and to one half of the second sub-message and parity bits.

3. The method for encoding a binary message according to claim 1, wherein the first sub-set (ES.sub.1) is associated with a first data-bit set consisting of a first half of the first sub-message and of a first half of the second sub-message, the second sub-set (ES.sub.2) is associated with the parity bits corresponding to the first data-bit set, the third sub-set (ES.sub.3) is associated with a second data-bit set consisting of a second half of the first sub-message and of a second half of the second sub-message and the fourth sub-set (ES.sub.4) is associated with the parity bits corresponding to the second data-bit set.

4. The method for encoding a binary message according to claim 1, wherein the second sub-matrix (H.sub.2) of the second sub-set (ES.sub.2) and the first sub-matrix (H.sub.4) of the fourth sub-set (ES.sub.4) are of maximum rank.

5. The encoding method according to claim 1, wherein: the second sub-matrix (H.sub.1) of the first sub-set (ES.sub.1) and the first sub-matrix (H.sub.3) of the third sub-set (ES.sub.3) have the same density of “1” values, the second sub-matrix (H.sub.2) of the second sub-set (ES.sub.2) and the first sub-matrix (H.sub.4) of the fourth sub-set (ES.sub.4) have the same density of “1” values, the sub-matrices G.sub.1 and G.sub.2 have the same density of “1” values.

6. An encoding device comprising a coder configured to execute the method for encoding a binary message according to claim 1.

7. A transmitter comprising an encoding device according to claim 6 for encoding a binary message composed of the first sub-message having a first priority level and of the second sub-message having a second priority level, in order to produce a coded binary message composed of two independent coded sub-messages each comprising data bits corresponding to half of the first sub-message and half of the second sub-message and parity bits, the transmitter comprising a transmitting means configured to transmit each of the two coded sub-messages independently.

8. A computer program containing instructions for executing the encoding method according to claim 1, when the program is executed by a processor.

9. A processor-readable storage medium on which is stored a program containing instructions for executing the encoding method according to claim 1, when the program is executed by a processor.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Other features and advantages of the present invention will become more clearly apparent on reading the following description with reference to the following appended drawings.

(2) FIG. 1 shows the structure of a parity-check matrix of a correction code according to one embodiment of the invention,

(3) FIG. 2 shows the parity-check matrix of FIG. 1 in a systematic form,

(4) FIG. 3 shows the parity-check matrix of FIG. 2 with detail elements,

(5) FIG. 4 shows an example of a structure of a message coded using a coding method according to the invention,

(6) FIG. 5 shows a flowchart of a coding method according to the invention,

(7) FIG. 6 shows an example of performance results obtained via the coding method according to the invention,

(8) FIG. 7 shows a diagram of a differentiated-protection coder according to the invention,

(9) FIG. 8 shows a diagram of a transmitter comprising a differentiated-protection coder according to the invention.

DETAILED DESCRIPTION

(10) The invention proposes a new structure for the parity-check matrix H of an LDPC correction code. This new structure is shown in FIG. 1. It allows two different protection levels to be applied to the data to be transmitted.

(11) The structure of the matrix H is illustrated in FIG. 1. It is composed of four sets ES.sub.1,ES.sub.2,ES.sub.3,ES.sub.4 each composed of two sub-matrices that are concatenated in the vertical dimension. In total, the matrix H consists of eight square sub-matrices of dimensions (x+y; x+y). x and y are integer values that define the proportion of high-priority bits and of low-priority bits in the message to be coded. If the binary message to be coded is denoted M, this message is composed of 2x high-priority bits and 2y low-priority bits.

(12) The first set ES.sub.1 is composed of two sub-matrices J.sub.1 and H.sub.1. The second set ES.sub.2 is composed of a zero matrix and of a sub-matrix H.sub.2. The third set ES.sub.3 is composed of two sub-matrices H.sub.3 and J.sub.2. The fourth set ES.sub.4 is composed of a sub-matrix H.sub.4 and of a zero matrix.

(13) The sub-matrices J.sub.1 et J.sub.2 are of the form

(14) ##STR00003##
with I an identity matrix of dimensions (x,x) and G.sub.1, G.sub.2 a sub-matrix of dimensions (x,y). The other coefficients of the sub-matrices J.sub.1 and J.sub.2 are zero.

(15) The sub-matrices H.sub.1, H.sub.2, H.sub.3, H.sub.4, G.sub.1, G.sub.2 are low-density matrices that are generated using optimization techniques, for example a density-evolution or EXIT-chart method as described in reference [7].

(16) FIG. 2 shows the parity-check matrix H in another form in which sets ES.sub.2 and ES.sub.3 have been permuted. Generally, the four sets of matrices may be permuted in any way without modifying the principle of the coding. The parity-check matrix H is shown in FIG. 2 in its systematic form. In other words, sub-matrix A (composed of the sets ES.sub.1 and ES.sub.3) corresponds to the data bits whereas sub-matrix B (composed of the sets ES.sub.2 and ES.sub.4) corresponds to the parity bits.

(17) If the binary message to be coded is denoted M, the vector of the parity bits P is obtained using the following relationships:
AM.sup.T=BP.sup.T=0  [Math. 1]
P.sup.T=AB.sup.−1M.sup.T  [Math. 2]

(18) The sub-matrix B must be invertible and of maximum rank.

(19) FIG. 3 shows yet another illustration of the parity-check matrix H. Each sub-matrix H.sub.1, H.sub.2, H.sub.3, H.sub.4 is composed of two square matrices of respective dimensions (x,x) and (y,y) and of two matrices of respective dimensions (x,y) and (y,x).

(20) The parity-check matrix H comprises 4(x+y) columns and 2(x+y) rows.

(21) FIG. 4 schematically shows the structure of the coded message M.sub.c obtained after coding of the message M using the matrix H. The coded message M.sub.c is composed of two separate frames or two separate blocks 1B and 2B that may be transmitted and decoded separately and independently.

(22) Each block is composed: of a first portion 1i.sub.1, 2i.sub.1 containing a respective half of the high-priority bits of the message M, of a second portion 1i.sub.2, 2i.sub.2 containing a respective half of the low-priority bits of the message M, of a third portion 1p.sub.1, 2p.sub.1 containing the parity bits associated with the first portion, of a fourth portion 1p.sub.2, 2p.sub.2 containing the parity bits associated with the second portion.

(23) In FIG. 3, the notations of FIG. 4 have been reused in order to indicate, for each set, the corresponding bits of the coded message.

(24) The coding ratio applied to the high-priority bits is higher than the coding ratio applied to the low-priority bits.

(25) Blocks 1B and 2B may be decoded independently. The decoding may be carried out using a decoding algorithm suitable for decoding LDPC correction code, for example a belief-propagation algorithm such as described in reference [7], or any other equivalent algorithm.

(26) The invention has a number of advantages because of the particular structure of the parity-check matrix proposed.

(27) In the case of a transmission of the blocks 1B and 2B over a channel without error, it is possible to recover all the high-priority bits of the message M by decoding a single of the two blocks. This property makes it possible to ensure a more reliable and rapider transmission of the high-priority bits.

(28) In the case of a transmission over a channel with errors (a radio channel for example), the decoding of a single of the two blocks 1B and 2B allows the high-priority bits to be recovered with an error probability lower than that obtained for a code defined with a parity-check matrix designed for a single priority level. Such a matrix is defined by the structure of FIG. 1 with y=0. It corresponds to a so-called root-LDPC code, such as described in reference [6].

(29) The error-correction capacity associated with the high-priority bits is related to the ratio x/y.

(30) In one variant embodiment of the invention, to obtain a robust system, the error-correction capacity is equivalent whatever the decoded block 1B or 2B. To obtain this result, the sub-matrices H.sub.1 and H.sub.3 have the same “1” density. Likewise, the sub-matrices H.sub.2 and H.sub.4 have the same “1” density. The sub-matrices G.sub.1 and G.sub.2 also have the same “1” density.

(31) For example, the sub-matrices H.sub.1, H.sub.2, H.sub.3, H.sub.4 are quasi-cyclic parity-check matrices such as defined in [7].

(32) FIG. 5 schematically shows a flowchart of an example of a coding method according to the invention. A binary message M is received then a step 501 of separating the bits of the message depending on their priority levels is applied. Next, a coding step 502 is applied to the bits organized depending on their priority levels to generate the coded message M.sub.c, which is composed of the two blocks 1B and 2B. The coding step 502 is carried out using the parity-check matrix H according to the invention.

(33) FIG. 6 shows, in a graph, examples of results obtained using the coding method according to invention. In this particular example, the sub-matrices H.sub.1, H.sub.2, H.sub.3, H.sub.4 are quasi-cyclic parity-check sub-matrices having a density equal to 3. The sub-matrices G.sub.1 and G.sub.2 have a density equal to 2.

(34) The curves shown in FIG. 6 are curves of binary error rate as a function of the ratio of the power of the carrier to the spectral density of the noise t C/N.sub.0.

(35) Curve 501 is a curve of the probability of errors in all the decoded data bits corresponding to the LDPC code used in the data component of the GPS navigation signal L1C such as explained in reference [8].

(36) Curves 502, 503, 504 and 505 are curves of the probability of errors in all the data bits decoded when both the blocks 1B and 2B are received and decoded.

(37) The curve 502 corresponds to the case y=0, i.e. to coding with a single priority level. Curves 503, 504 and 505 correspond to values of x equal to 200, 100 and 50, respectively, for a value of x+y=250 in every case. The basic correction code has an efficiency of ½.

(38) Curves 510, 520, 530 and 540 correspond to the probability of error in high-priority bits when only one of the two blocks 1B or 2B is received and decoded. The dashed curves correspond to the first block 1B and the curves with symbols correspond to the second block 2B. The curves superpose.

(39) The curves 540 correspond to the case y=0. The curves 510, 520 and 530 correspond to values of x equal to 200, 100 and 50, respectively, for a value of x+y=250 in every case.

(40) The proportion of high-priority bits has an influence on the probability of error in high-priority bits; the higher this proportion, the lower the probability of error.

(41) FIG. 7 schematically shows a diagram of a differentiated-protection coder according to the invention, able to implement the coding method described with reference to FIG. 5.

(42) The coder 700 according to the invention receives as input a binary message M to be coded and produces as output a coded binary message M.sub.c composed of two blocks 1B and 2B. The coder 700 comprises a first module 701 for assigning a priority level to the bits of the message M, and a second module 702 for grouping bits of same priority level together and organizing the message before coding with the expected structure. The coder 700 furthermore comprises a coding third module 703 for coding the binary message using the parity-check matrix H.

(43) FIG. 8 shows a diagram of a transmitter 800 comprising a coder 802 according to the invention. The transmitter 800 may furthermore comprise an application module 801 for generating bit frames M and a radio module 803 for modulating, filtering, forming and analoguely converting a coded bit frame M.sub.c before its transmission to an antenna 804 for emission over a radio channel. The transmitter 800 may, for example, be a transmitter compatible with a satellite radio-navigation system. In this respect, the transmitter 800 may be integrated into the payload of a satellite.

(44) The modules of the coder and of the decoder according to the invention may be implemented using hardware and/or software components. In this respect, the invention may especially be implemented in the form of a computer program containing instructions for its execution. The computer program may be stored on a processor-readable storage medium. The medium may be electronic, magnetic, optical or electromagnetic.

(45) In particular, the invention in its entirety or each module of the coder or of the decoder according to the invention may be implemented by a device comprising a processor and a memory. The processor may be a generic processor, a specific processor, an application-specific integrated circuit (ASIC) or a field-programmable gate array (FPGA).

(46) The device may use one or more dedicated electronic circuits or a general-use circuit. The technique of the invention may be carried out by a reprogrammable computing machine (a processor or a microcontroller for example) executing a program comprising a sequence of instructions, or by a dedicated computing machine (for example a set of logic gates such as an FPGA or an ASIC, or any other hardware module).

(47) According to one embodiment, the device comprises at least one computer-readable storage medium (a RAM, ROM, EEPROM, flash memory or a memory in another technology, a CD-ROM, DVD or another optical disc medium, a magnetic cassette, a magnetic strip, a magnetic storage disk, or another storage device or another computer-readable nonvolatile storage medium) coded with a computer program (i.e. a plurality of executable instructions) that, when it is executed by a processor or more than one processor, performs the functions of the embodiments of the invention described above.

(48) By way of example of a hardware architecture suitable for implementing the invention, a device according to the invention may include a communication bus to which are connected: a central processing unit or microprocessor (CPU); a read-only memory (ROM) able to store the programs required to implement the invention; a random-access or cache memory (RAM) containing registers suitable for recording variables and parameters created and modified during the execution of the aforementioned programs; and a communication or input/output (I/O) interface suitable for transmitting and receiving data.

(49) The reference to a computer program that, when it is executed, performs any one of the functions described above, should not be understood as being limited to an application program executed by a single host computer. On the contrary, the terms computer program and software are used here in a general sense to refer to any type of computer code (for example a piece of application software, a piece of firmware, a microcode, or any other form of computer instructions) that may be used to program one or more processors to implement aspects of the techniques described here. The computational resources or means may especially be distributed (cloud computing), optionally with peer-to-peer technologies. The software code may be executed by any suitable processor (a microprocessor for example) or processor core or a set of processors, whether they be provided in a single computing device or distributed between a plurality of computing devices (for example such as possibly accessible in the environment of the device). The executable code of each program, allowing the programmable device to implement the processes according to the invention, may be stored, for example, on a hard disk or read-only memory. Generally, the one or more programs will possibly be loaded into one of the storage means of the device before being executed. The central unit may control and direct the execution of the software code sections or instructions of the one or more programs according to the invention, which instructions are stored in the hard disk or in the read-only memory or indeed in another of the aforementioned storage components.

REFERENCES

(50) [1] C. Poulliat, D. Declercq and I. Fijalkow, “Enhancement of Unequal Error Protection Properties of LDPC Codes”, EURASIP Journal on Wireless Communications and Networking, vol. 2007, Article ID 92659, 9 pages, 2007. [2] P. Pulini et al, “Unequal Diversity LDPC Codes for Relay Channels”, IEEE Trans. On Wireless Communications, Vol 12, No. 11, November 2013. [3] C. Lamy-Bergot & B. Gadat, “Embedding protection inside H.264/AVC and SVC streams”, EURASIP Journal on Wireless Communications and Networking, 2010. [4] C. Poulliat, “Contribution à l'étude et à l'optimisation de systèmes à composantes itératives”, HdR 2011. [5] FR3035286 [6] J. J. Boutros, A. Guillen i Fabregas, E. Biglieri and G. Zemor, “Low-Density Parity-Check Codes for Nonergodic Block-Fading Channels,” in IEEE Transactions on Information Theory, vol. 56, no. 9, pp. 4286-4300, September 2010. [7] Ryan, W., Lin, S. (2009). Channel Codes: Classical and Modern. Cambridge: Cambridge University Press. [8] Marion Roudier. Analysis and Improvement of GNSS Navigation Message Demodulation Performance in Urban Environments. Theses, INP Toulouse, January 2015.