METHODS AND DEVICES FOR TRANSMITTING AND RECEIVING NON-BINARY ERROR CORRECTING CODE WORDS

Abstract

The invention relates to the transmission and reception of non-binary error correcting code words. The transmission method includes a first modulation (56) which implements a set of q sequences comprising q-1 sequences of q-1 chips, each sequence being obtained by circular shifting of a basic pseudo-random sequence, and a partially invariant sequence, invariant to a predetermined subset of circular shifts. The first modulation (56) further implements an association between each code word symbol and a sequence of the set of sequences wherein said finite field GF.sub.q has a non-zero primitive element, the symbol zero being associated with said partially invariant sequence and a symbol equal to a power j of the primitive element, j being an integer comprised between 0 and q-2, being associated with a pseudo-random sequence determined by j circular shifts of the basic pseudo-random sequence.

Claims

1. A method for transmitting non-binary error correcting code word symbols through a transmission channel, each code word symbol comprising p bits and being part of a finite field GF.sub.q with q=2.sup.p elements, the method including: a first spread spectrum modulation associating a sequence of chips with each p-bit code word symbol, a second modulation for modulating at least one carrier with the sequences associated with the code words, by phase or amplitude modulation, making it possible to obtain at least one modulated carrier, a transmission of said at least one modulated carrier forming a signal through said transmission channel, wherein the first modulation implements a set of q sequences comprising q-1 sequences of q-1 chips, each sequence being obtained by circular shifting of a basic pseudo-random sequence, and a partially invariant sequence, consisting of q-1 chips and invariant to a predetermined subset of circular shifts, and wherein the first modulation further implements an association between each code word symbol and a sequence of the set of sequences wherein, said finite field GF.sub.q has a non-zero primitive element, the symbol zero being associated with said partially invariant sequence and a symbol equal to a power j of the primitive element, j being an integer comprised between 0 and q-2, being associated with a pseudo-random sequence determined by j circular shifts of the basic pseudo-random sequence.

2. The method according to claim 1, wherein said partially invariant sequence is a constant sequence consisting of q-1 chips of the same value.

3. The method according to claim 1, further including, prior to the application of a non-binary error correcting code, the formation of a message of K symbols of GF.sub.q, to which the non-binary error correcting coding is applied so as to generate a code word, the message being formed in such a way that a symbol called an anchoring symbol, with a value belonging to a predetermined subset of GF.sub.q, is placed at a predetermined position in the message or in said code word.

4. The method according to claim 3, wherein said predetermined subset comprises a single predetermined non-zero value, and said anchoring symbol takes said predetermined non-zero value.

5. The method according to claim 4, wherein during the step of forming the message, said anchoring symbol is placed at said predetermined position in the message.

6. The method according to claim 4, wherein the formation of the message comprises a determination of a symbol of said message as a function of K-1 other symbols of the message, the code word obtained after encoding comprising said anchoring symbol at said predetermined position.

7. Transmission method according to claim 1, wherein the first modulation comprises the generation of the basic pseudo-random sequence by a linear feedback shift register of maximum length.

8. The transmission method according to claim 1, wherein the second modulation is a phase or an amplitude modulation of the carrier.

9. The transmission method according to claim 1, wherein the second modulation used for the partially invariant sequence is different from the second modulation used by the sequences obtained by circular shifting of the basic pseudo-random sequence.

10. The transmission method according to claim 9, wherein the second modulation includes an absence of carrier wave for the partially invariant sequence and a phase modulation for the sequences obtained by circular shifting of the basic pseudo-random sequence.

11. A method for receiving a received signal, said received signal coming from a signal transmitted by a transmission method according to claim 1, said transmitted signal including transmitted error correcting code word symbols, the reception method comprising steps of: demodulating the received signal, which can be used for obtaining an estimation of the coded symbols transmitted from the received signal, a joint decoding and synchronization, comprising: a decoding for determining a decoded word and/or a corresponding decoded message from the estimations of the coded symbols, as provided by the demodulation step, said decoded word providing an estimation of the transmitted code word multiplied by the primitive element of the finite field GF.sub.q raised to a power equal to a synchronization shift, an estimation of said synchronization shift starting from an anchoring symbol at a predetermined position in the decoded word or in the corresponding decoded message.

12. The reception method according to claim 11, further comprising an estimation of the transmitted code word by dividing the symbols of the decoded word and/or of the decoded message by the primitive element of the finite field raised to the power equal to the estimated synchronization shift.

13. The reception method according to claim 12, further comprising, when the estimation of the transmitted code word does cannot be used for obtaining a code word, a synchronization by applying the estimated synchronization shift and an iteration of the decoding steps, of estimation of the synchronization shift until a stop criterion is satisfied.

14. The reception method according to claim 11, wherein the steps of demodulation and of joint decoding and synchronization are periodically repeated, shifting the received signal by a predetermined number of chips.

15. A device for transmitting non-binary error correcting code word symbols through a transmission channel, each code word symbol comprising p bits and being part of a finite field GF.sub.q with q=2.sup.p elements, the transmission device being configured for implementing: a first spread spectrum modulation module associating a sequence of chips with each p-bit code word symbol, a second modulation module configured for modulating of at least one carrier with the sequences associated with the code words, by phase or amplitude modulation, which can be used for obtaining at least one modulated carrier, a module for transmitting said at least one modulated carrier forming a signal, through said transmission channel, wherein the first modulation module is configured for implementing a set of q sequences comprising q-1 sequences of q-1 chips, each sequence being obtained by circular shifting of a basic pseudo-random sequence, and a partially invariant sequence, consisting of q-1 chips and invariant to a predetermined subset of circular shifts, and wherein the first modulation module is further configured for implementing an association between each code word symbol and a sequence of the set of sequences wherein, said finite field GF.sub.q having a non-zero primitive element, the symbol zero being associated with the partially invariant sequence and a symbol equal to a power j of the primitive element, j being an integer comprised between 0 and q-2, is associated with a pseudo-random sequence determined by j circular shifts of the basic pseudo-random sequence.

16. A device for receiving a received signal, said received signal being derived from a signal transmitted by a transmission device according to claim 15, said transmitted signal including transmitted error correcting code word symbols, the reception device being configured for implementing: a module for demodulating the received signal, which can be used for obtaining an estimation of the coded symbols transmitted from the received signal, a module for joint decoding and synchronization, comprising: a decoding module for determining a decoded word and/or a corresponding decoded message from the estimations of the coded symbols, as provided by the demodulation step, said decoded word providing an estimation of the transmitted code word multiplied by the primitive element of the finite field GF.sub.q raised to a power equal to a synchronization shift, a module for estimating said synchronization shift from an anchoring symbol at a predetermined position in the decoded word or in the corresponding decoded message.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0047] Other features and advantages of the invention will be clear from the description thereof which is given below as a non-limiting example, with reference to the enclosed figures, among which:

[0048] FIG. 1 schematically represents an asynchronous communication system according to one embodiment;

[0049] FIG. 2 schematically represents a transmission device according to one embodiment;

[0050] FIG. 3 schematically represents a reception device according to one embodiment;

[0051] FIG. 4 is a flowchart of the main steps of a transmission method according to one embodiment;

[0052] FIG. 5 is a flowchart of the main steps of reception method according to one embodiment;

[0053] FIG. 6 is a graph with curves illustrating the error rate per reception frame for a plurality of examples of implementation.

DETAILED DESCRIPTION OF EMBODIMENTS

[0054] FIG. 1 illustrates an asynchronous communication system 2 suitable for implementing the invention, hereinafter called more simply a communication system.

[0055] The communication system 2 includes a transmission device 4 and a reception device 6. A message M is processed and transmitted to the reception device 6, in the form of a signal modulated by carriers and referenced by X, by the transmission device 4, via a transmission channel 8 represented schematically in FIG. 1. The reception device 6 receives and processes a received signal Y, in order to obtain a decoded message M̂.

[0056] The message M contains exploitable data density to be transmitted, in the form of a set of bits called source bits.

[0057] The transmission channel 8 adds an unknown delay, hereinafter called synchronization delay, and channel noise.

[0058] In the example shown in FIG. 1, the transmission device 4 includes a non-binary encoding module 10, which applies a non-binary linear error correcting coding to the message to be transmitted.

[0059] The invention applies to any non-binary and linear error correcting code, e.g. one of the following correcting codes: Low Density Parity Check (LDPC), Reed-Solomon, Turbo-code or polar code.

[0060] Such correcting codes are built on a non-binary Galois field with q elements (or with cardinality q), denoted by GF.sub.q, q being a power of a prime number, and preferentially a power of 2, e.g. q.sub.=2.sup.pso as to represent symbols with p bits.

[0061] In a known manner, such a Galois field comprises the zero element 0 and q-1 successive powers of a primitive element α.

[0062] In other words, the elements of the field GF.sub.q are defined by:

[00001]$G{F}_q=\left\{0,{\alpha }^0,{\alpha }^1,.Math.,{\alpha }^{q-2}\right\}$

[0063] A set of (K-1)×p source bits, corresponding to K-1 source symbols of p bits each, is first supplemented by p known bits, corresponding to a non-zero symbol of GF.sub.q, with a known value, also called anchoring symbol, so as to generate a source message of exactly K symbols. The extended message is denoted by:

[00002]$M=\left(m_1,m_2,.Math.,m_K\right)\in G{F}_q^K$

e.g., if the anchoring symbol takes the value α.sup.0 = 1 and is placed in the first position of the message M, one obtains:

[00003]$M=\left({\alpha }^0,m_2,.Math.,m_K\right)\in G{F}_q^K$

[0064] Of course, any other predetermined non-zero value α.sup.i ≠ 0, and any other predetermined position with j, 1 ≤ j ≤ K index, can be chosen:

[00004]$M=\left(m_1,.Math.,m_{j-1},{\alpha }^i,m_{j+1},.Math.,m_K\right)\in G{F}_q^K$

[0065] For simplicity and without loss of generality, it can thus be assumed that m.sub.1 ≠ 0 is the anchoring symbol, known both to the transmitter and to the receiver.

[0066] In such case, the anchoring symbol takes the value thereof in a predetermined subset of GF.sub.q, the subset being reduced to a single predetermined non-zero value.

[0067] The extended message with a size of K symbols is then transformed by the error correcting coding into a code word C of N symbols (i.e. N×p coded bits), the number N being greater than the number K.

[00005]$C=\left(c_1,.Math.,c_N\right)\in G{F}_q^N$

[0068] If the encoding operation is systematic, i.e. set of K symbols of the message M is integrally found in the code word C at known positions, then the anchoring symbol of predetermined value m.sub.1 will be found at a known position of C.

[0069] In such case, for simplicity and without loss of generality, it will be assumed that m.sub.1 is in the first position in C, i.e. c.sub.1 = m.sub.1, which makes it a symbol known both to the transmitter and to the receiver.

[0070] It should be noted that if the encoding operation is not systematic, the code word C does not necessarily contain an anchoring symbol of predetermined value.

[0071] Nevertheless, in an alternative embodiment, instead of assigning a predetermined value to a symbol of the message M (anchoring symbol in the message), it is possible to assign a predetermined value to a symbol of the code word C.

[0072] To this end, it is sufficient to consider the fact that any symbol of the code word C can be expressed as a linear combination of the symbols of the message M. Considering e.g. the first symbol of C:

[00006]$c_1=h_1{m}_1+h_2{m}_2+.Math.+h_K{m}_K$

where the coefficients h.sub.1, h.sub.2, ..., h.sub.K ∈ GF.sub.q, with at least one non-zero coefficient, and the multiplication and addition operations in the above formula, are performed in GF.sub.q. Thus, assuming without loss of generality that h.sub.1 ≠ 0, it is possible to assign a predetermined value to the symbol c.sub.1, e.g. c.sub.1 = α.sup.0, simply by determining the value of the symbol m.sub.1 from the values of the symbols m.sub.2, ..., m.sub.K by the formula:

[00007]$m_1=h_1^{-1}\left({\alpha }^0-h_2{m}_2.Math.-h_K{m}_K\right)$

[0073] Thus c.sub.1 = α.sup.0 is obtained, which makes same an anchoring symbol of predetermined value, known both to the transmitter and to the receiver.

[0074] The present invention applies to the two embodiments hereinabove: both for the first embodiment when the anchoring symbol is a symbol of the message M, and for the second embodiment when the anchoring symbol is a symbol of the code word C. It should be noted, that the two embodiments are obtained by a specific formation of the message M.

[0075] The transmission device further includes a first modulation module 14 configured for applying a first modulation and a second modulation module 16 configured for applying a second modulation.

[0076] The first modulation applied by the module 14 is spread spectrum modulation. More particularly, the first modulation module 14 implements a modified variant of the CCSK cyclic code-shift keying modulation.

[0077] Conventional CCSK modulation consists of associating a sequence of q chips with each symbol of a set of q symbols, numbered from 0 to q-1. The chip sequence space consists of sequences Po to P.sub.q-1, where Po is a pseudo-random sequence consisting of q bits, and each sequence P.sub.j is obtained by circular shifting of j positions, in a predetermined direction, of the sequence P.sub.0.

[0078] As a numerical example, for q=8 and p=3, table 1 below illustrates the association or mapping between each symbol and each sequence, obtained by circular shifting to the left of a sequence P.sub.0=(1,1,1,0,1,0,0,0):

TABLE-US-00001 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 2 1 0 1 0 0 0 1 1 3 0 1 0 0 0 1 1 1 4 1 0 0 0 1 1 1 0 5 0 0 0 1 1 1 0 1 6 0 0 1 1 1 0 1 0 7 0 1 1 1 0 1 0 0

[0079] The direction of the circular shifting is chosen by convention.

[0080] The first modulation according to the invention implements a set of q sequences {Z,R.sub.0,..., R.sub.q-2} comprising q-1 sequences of q-1 chips, each sequence being obtained by circular shifting of a basic pseudo-random sequence R.sub.0, and a partially invariant sequence Z, which is, in the present embodiment, a constant sequence (i.e. invariant to any circular shifting in the present case) consisting of q-1 chips of the same value.

[0081] Preferentially, the basic pseudo-random sequence R.sub.0 is generated by a linear-feedback shift register of maximum length or by a sequence called constant amplitude zero autocorrelation waveform (CAZAC).

[0082] Using a mathematical formulation, the basic pseudo-random sequence R.sub.0 is written:

[00008]$R_0=\left(R_0\left(0\right),R_0\left(1\right),.Math.,R_0\left(q-2\right)\right)$

where R.sub.0(i) ∈ {0,1}, ∀i = 0,1, ..., q – 2

[0083] The set of sequences R.sub.1 to R.sub.q-2 is defined by circular shifting the sequence R.sub.0 in a predetermined direction. Thus, any sequence R.sub.u, ∀u = 0, ..., q – 2 is written:

[00009]$R_u\left(i\right)=R_0\left(i+umod\left(q-1\right)\right),\forall i=0,.Math.,q-1,$

[0084] The constant sequence Z has q-1 chips of the same values, and is denoted by: Z = (z, z,.., z).

[0085] z=0 or z=1 e.g. can be considered. However, z can be also considered as a symbolic value (rather than a numerical value), so as to distinguish same from the chips 0 and 1 which form the sequences R.sub.0,..., R.sub.q-2. In this way it is possible to distinguish, in the second modulation module 16, between the modulation used for the sequence Z and the modulation used for the sequences R.sub.0,..., R.sub.q-2.

[0086] Advantageously, the constant sequence Z is invariant for any circular shift.

[0087] The association of a symbol GF.sub.q with a sequence of the sequence set {z, R.sub.0,R.sub.1, ...,R.sub.q-21 is defined by a mapping function .Math.() defined as follows:

[00010]$\begin{array}{c}\mu \left(0\right)=Z\\ \mu \left({\alpha }^u\right)=R_u,\forall k=0,.Math.,q-2\end{array}$

[0088] Thus, all the symbols c.sub.u of the code word are associated with a sequence of q-1 chips of the set of sequences defined hereinabove.

[0089] The .Math.() function defines a mapping scheme.

[0090] As a numerical example, for q=8 and p=3, table 2 below illustrates the association according to the mapping scheme defined hereinabove, with the base sequence R.sub.0=(1,1,1,0,1,0,0):

TABLE-US-00002 0 z z z z z z z α.sup.0 1 1 1 0 1 0 0 α.sup.1 1 1 0 1 0 0 1 α.sup.2 1 0 1 0 0 1 1 α.sup.3 0 1 0 0 1 1 1 α.sup.4 1 0 0 1 1 1 0 α.sup.5 0 0 1 1 1 0 1 α.sup.6 0 1 1 1 0 1 0

[0091] Such association is called GF.sub.q-covariant association.

[0092] The following property, called the covariance property, is verified for the modified CCSK modulation: when a symbol c of GF.sub.q is associated with the mapping scheme defined by .Math.(), i.e. .Math.(c) = S, the sequence S′ obtained by a circular shifting of k positions, denoted by S′ = k ↺S, is the sequence of chips associated with α.sup.k c. In other words:

[00011]$\mu \left({\alpha }^{k}c\right)=k\circlearrowleft S$

[0093] In an equivalent way, by denoting by .Math..sup.-1() the inverse association, used for associating a sequence of chips with a symbol, the following relation is verified:

[00012]${\mu }^{-1}\left(k\circlearrowleft S\right)={\alpha }^{k}c$

[0094] The second modulation, implemented by the second modulation module 16, is a phase modulation or an amplitude modulation, e.g. a BPSK (Binary Phase Shift Keying) modulation or an OOK (On Off Keying) modulation.

[0095] In one embodiment, the sequences R.sub.u obtained by a circular shifting of the sequence R.sub.0 are modulated using phase modulation, preferentially BPSK phase modulation, and the constant sequence Z is modulated according to a different modulation.

[0096] According to a particular embodiment, the second modulation comprises an absence of carrier wave for the constant sequence and a 2-state phase modulation or BPSK (Binary Phase Shift Keying) modulation for the sequences obtained by circular shifting of the basic pseudo-random sequence.

[0097] The modulated carriers form an X signal transmitted via the transmission channel.

[0098] The reception device 6 includes a demodulation module 20 and a joint decoding and synchronization module 22, the decoding being a non-binary corrector decoding.

[0099] Advantageously, in particular by virtue of the application of the first modulation as described above, the receiver device is suitable for jointly performing the error correcting decoding and the synchronization, as will be described in greater detail hereinabove.

[0100] FIG. 2 schematically represents a transmission device 4 according to one embodiment. The transmission device 4 is a programmable electronic device, typically a computer, and comprises a central computing unit (CPU) 30, an electronic memory 32, a communication interface 34 and a human-machine interface 36. The elements 30, 32, 34, 36 are suitable for communicating via a communication bus.

[0101] The central computing unit 30 comprises one or a plurality of processors apt to execute computer program instructions stored by the electronic memory 32 when the device 4 is powered on.

[0102] The electronic memory unit is configured for storing a module 10 for forming a message of K non-binary symbols, a module 12 for non-binary coding, a module 14 for a first modulation and a module 16 for a second modulation.

[0103] In one embodiment, the modules 10, 12, 14, 16 are embodied in the form of software code, and form a computer program, including software instructions which, when implemented by the programmable electronic device, implement a method for transmitting non-binary error correcting code symbols according to the invention.

[0104] In a variant (not shown), the modules 10, 12, 14, 16 are each embodied in the form of a programmable logic component, such as an FPGA (Field Programmable Gate Array) or a GPGPU (General-purpose processing on graphics processing), or further in the form of a dedicated integrated circuit, such as an ASIC (Application Specific Integrated Circuit).

[0105] The computer program implementing the method for transmitting non-binary error correcting code symbols is further apt to be recorded on a computer-readable medium (not shown). The computer-readable medium is e.g. a medium apt to store the electronic instructions and to be coupled to a bus of a computer system. As an example, the readable medium is an optical disk, a magneto-optical disk, a ROM memory, a RAM memory, any type of non-volatile memory (e.g. EPROM, EEPROM, FLASH, NVRAM), a magnetic card or an optical card.

[0106] FIG. 3 schematically represents a reception device 6 according to one embodiment. The reception device 6 is a programmable electronic device, typically a computer, and comprises a central computing unit (CPU) 40, an electronic memory 42, a communication interface 44 and a human-machine interface 66. The elements 40, 42, 44, 46 are suitable for communicating via a communication bus.

[0107] The central computing unit 40 comprises one or a plurality of processors apt to execute computer program instructions stored by the electronic memory 42 when the device 6 is powered on.

[0108] The electronic memory unit is configured for storing a demodulation module 20 and a module 22 for joint decoding and synchronization. The module 22 comprises a module 24 for decoding a non-binary error correcting code, a module 26 for estimating a synchronization shift and a module 28 for calculating the transmitted code word and the corresponding message by applying the estimated synchronization shift.

[0109] In one embodiment, the modules 20, 24, 26, 28 are produced in the form of software code, and form a computer program, including software instructions which, when implemented by a programmable electronic device, implement a reception method according to the invention.

[0110] In a variant (not shown), the modules 20, 24, 26, 28 are each embodied in the form of a programmable logic component, such as an FPGA (Field Programmable Gate Array) or a GPGPU (General-purpose processing on graphics processing), or further in the form of a dedicated integrated circuit, such as an ASIC (Application Specific Integrated Circuit).

[0111] The computer program implementing the reception method is further apt to be recorded on a computer-readable medium (not shown). The computer-readable medium is e.g. a medium apt to store the electronic instructions and to be coupled to a bus of a computer system. As an example, the readable medium is an optical disk, a magneto-optical disk, a ROM memory, a RAM memory, any type of non-volatile memory (e.g. EPROM, EEPROM, FLASH, NVRAM), a magnetic card or an optical card.

[0112] FIG. 4 is an flowchart of the main steps of the transmission method according to one embodiment.

[0113] The method includes a step 50 of obtaining non-binary error code word symbols to be transmitted.

[0114] In one embodiment, the step 50 includes sub-steps 51 of formation of the message M to be processed and transmitted according to the description given hereinabove, and a sub-step 52 of encoding by a chosen non-binary error correcting code which can be used for obtaining p-bit coded symbols, p being an integer.

[0115] Two distinct embodiments of the sub-step 51 of formation of the message M are envisaged.

[0116] In a first embodiment, the message M comprises K-1 exploitable data symbols to be transmitted, as well as an anchoring symbol of predetermined non-zero value, placed at a predetermined position in the message (e.g. m.sub.1 = α.sup.0).

[0117] In a second embodiment, the message M comprises K-1 exploitable data symbols to be transmitted and a symbol, the value of which is determined as a function of the K-1 symbols of exploitable data, so that an anchoring symbol placed at a predetermined position in the code word, takes a predetermined non-zero value (e.g. m.sub.1 = h.sub.1.sup.-1(α.sup.0 h.sub.2m.sub.2 .Math..Math..Math.-h.sub.Km.sub.K), so that after the encoding step 52, c.sub.1 = α.sup.0 is obtained)

[0118] The non-binary error correcting code applied in the sub-step 52 is e.g. a non-binary low density parity code NB-LDPC.

[0119] The symbols obtained are part of a Galois field GF.sub.q with q=2.sup.p elements.

[0120] At the end of the step 50, a correcting code word is obtained: C = {c.sub.1, ..., c.sub.N} (referenced by 54).

[0121] The method further comprises a step 56 of applying a first modulation, which is a modified CCSK modulation as described hereinabove, which can be used for associating each symbol with a sequence of q-1 chips among the set of sequences {Z, R.sub.0, R.sub.1, ..., R.sub.q-2} including the constant sequence Z and sequences of chips R.sub.u, each sequence R.sub.u being obtained by circular shifting of a pseudo-random basic sequence R.sub.0 of q-1 chips.

[0122] Optionally, the first modulation step 56 comprises sub-steps 58 to 62 as described hereinafter.

[0123] The step 56 then comprises a sub-step 58 for obtaining the basic pseudo-random sequence R.sub.0.

[0124] Preferentially, such basic pseudo-random sequence is generated by a generator and stored. The sequence is e.g. generated by a linear feedback shift register of maximum length.

[0125] The step 56 further comprises a sub-step 60 for generating and storing sequences R.sub.1 to R.sub.q-2.

[0126] Step 56 also comprises a sub-step 62 of storing the mapping function .Math.() as defined by the formula [MATH 10].

[0127] In a variant, the generation of the set of sequences R.sub.0 to R.sub.q-2 and the storage of the mapping are performed prior to the implementation of the method.

[0128] Finally, the step 58 comprises a step 64 of associating a sequence of chips with each code word symbol, wherein, for each symbol c.sub.j of the code word C, the associated sequence of chips Sj is determined by applying the mapping function:

[00013]$S_j=\mu \left(c_j\right)$

[0129] The method further comprises a step 66 of applying a second modulation, e.g. a phase modulation or an amplitude modulation.

[0130] In one embodiment, for each sequence S.sub.j=R.sub.i, in other words if the sequence S.sub.j is one of the sequences of chips obtained from the basic pseudo-random sequence R.sub.0, then the BPSK modulation is applied, as well as for the constant sequence Z.

[0131] According to a variant, different from the modulation applied to the sequences of chips obtained by circular shifting of the basic pseudo-random sequence, the constant sequence is modulated to “0”. In other words, there is no transmission (e.g. absence of carrier wave) during the duration of the constant sequence Z. Advantageously, the transmission power is reduced.

[0132] The second modulation 66 is followed by a step of transmission 68 of the successive carriers forming a signal X.

[0133] Advantageously, due to the covariance property defined hereinabove, in an “ideal” case, if the transmission channel 8 introduces a circular desynchronization, i.e. if the sequences of chips (S.sub.1,..., S.sub.N) associated with the symbols (c.sub.1,..., c.sub.N) of a code word C, are received at the decoder in the form (k ↺ S.sub.1, ..., k ↺ S.sub.N), the implementation of the inverse association .Math..sup.-1() can be used for directly obtaining the code word C′ = (a.sup.kc.sub.1, ..., a.sup.kc.sub.N).

[0134] The ideal case described hereinabove is purely theoretical.

[0135] In practice, the transmission channel 8 introduces a desynchronization which results in a “quasi-circular” desynchronization of the sequences (S.sub.1,..., S.sub.N). Indeed, in the event of desynchronization of k chips, only q-1-k chips of a received sequence correspond to a circular shift of the transmitted sequence of chips, the k remaining chips being in fact chips belonging to a contiguous sequence of chips. In this way it is possible to consider the received sequence as a noisy version of the sequence (k ↺ S.sub.1, ..., k ↺ S.sub.N).

[0136] Thus, by decoding the received sequence, an estimation of the code word C′ = (a.sup.kc.sub.1, ... , a.sup.kc.sub.N), and thus of the corresponding message M′ = (a.sup.km.sub.1, ..., a.sup.km.sub.K), is obtained.

[0137] The knowledge of an anchoring symbol of predetermined value, whether same is a symbol of the transmitted code word C or of the corresponding message M, can then be further used for determining the synchronization shift k undergone by the transmitted signal, as will be explained thereafter.

[0138] It should also be noted that, in addition to correction of the synchronization shift, the decoding operation can be further used for correcting the transmission errors due to the noise present on the transmission channel.

[0139] Thus, the proposed invention makes it possible to jointly perform the synchronization and the error-correcting decoding.

[0140] FIG. 5 is a flowchart of the main steps of the reception method according to one embodiment.

[0141] The reception method includes a step 70 of receiving a signal Y, which corresponds to the signal X transmitted by the transmission method, affected by an unknown synchronization shift and corrupted by a noise, e.g. which can be modeled by Gaussian white noise.

[0142] The reception method comprises a demodulation step 72 which can be used for obtaining an estimation of the transmitted coded symbols, from the received signal Y, without any estimation of the synchronization shift.

[0143] According to various possible embodiments, the estimation can take either the form of a hard decision, i.e. determining for each code word symbol, the most likely value in GF.sub.q based on the received signal, or the form of a soft decision, i.e. determining for each symbol of the code word, a probability distribution over GF.sub.q, or in an equivalent way, logarithmic likelihood values for each element of GF.sub.q, depending on the signal received.

[0144] In one embodiment, the demodulation 72 applies a so-called log likelihood ratio (LLR) method of order q (q-ary LLR), known to a person skilled in the art.

[0145] In one embodiment, the calculation is performed using discrete and inverse Fourier transform operations, implemented e.g. by Fast Fourier Transforms (FFT) and Inverse Fast Fourier Transforms (IFFT).

[0146] The method then includes a joint decoding and synchronization step 74, jointly performing the decoding of the transmitted code words and the estimation of the synchronization shift k.

[0147] The step 74 includes a sub-step 76 of decoding by applying the non-binary error correcting decoding corresponding to the non-binary error correcting coding applied in the transmission method.

[0148] At the end of the step 76 a decoded word is obtained, denoted by:

[00014]${\widehat{C}}^{\prime }=\left({{\widehat{c}}^{\prime }}_1.Math.,{{\widehat{c}}^{\prime }}_N\right)$

and a corresponding message, denoted by:

[00015]${\widehat{M}}^{\prime }=\left({{\widehat{m}}^{\prime }}_1,.Math.,{{\widehat{m}}^{\prime }}_K\right)$

[0149] The decoded word is an estimation of the transmitted code word multiplied by the primitive element α of the field GF.sub.q to the power of k, k being the synchronization shift undergone by the transmitted signal:

[00016]${\widehat{C}}^{\prime }\simeq \left({\alpha }^k{c}_1,.Math.,{\alpha }^k{c}_N\right)$

[0150] In the same way, the decoded message is an estimation of the message M multiplied by the primitive element α of the field GF.sub.q to the power of k

[00017]${\widehat{M}}^{\prime }\simeq \left({\alpha }^k{m}_1,.Math.,{\alpha }^k{m}_K\right)$

[0151] The method then comprises a step 78 of estimating the synchronization shift k from the decoded word or message, the estimated value of the synchronization shift being denoted by k̂.

[0152] In one embodiment, the estimation is performed knowing the predetermined position and the predetermined non-zero value of the message anchoring symbol M, introduced during the step 51 of formation of the message M .

[0153] The position symbol in first position e.g. is concerned, and the predetermined non-zero value is equal to 1, i.e., m.sub.1 = 1 from which is deduced:

[00018]${{\widehat{m}}^{\prime }}_1={\alpha }^k$

[0154] Therefore, the estimation of the synchronization shift is calculated by the formula:

[00019]$\widehat{k}={\log }_{\alpha }{{\widehat{m}}^{\prime }}_1$

where the logarithmic function hereinabove denotes the discrete logarithm defined in the multiplicative group of the field GF.sub.q.

[0155] In another embodiment, the estimation is performed knowing the predetermined position and the predetermined non-zero value of the anchoring symbol of the code word C, introduced during the step 51 of formation of the message M.

[0156] The position symbol in the first position e.g. is concerned, and the predetermined non-zero value is equal to 1, i.e., c.sub.1 = 1 from which is deduced:

[00020]${{\widehat{c}}^{\prime }}_1={\alpha }^k$

[0157] Therefore, the estimation of the synchronization shift is calculated by the formula:

[00021]$\widehat{k}={\log }_{\alpha }{{\widehat{c}}^{\prime }}_1$

[0158] The method then includes estimating 80 the transmitted code word C and/or the corresponding message M by applying the estimated synchronization shift k̂.

[0159] The step 80 implements a calculation consisting of dividing each symbol of the decoded word Ĉ′ and/or of the message M̂′ by the primitive element α of the field GF.sub.q to the power of k̂.

[0160] Thus, by denoting by Ĉ = (ĉ.sub.1, ... , ĉ.sub.N) the estimation of the transmitted code word C, and by M̂ = (m̂.sub.1, ... , m̂.sub.k)the estimation of the corresponding message M, during the step 80 we determine:

[00022]$\begin{array}{cc}{\widehat{c}}_i={\alpha }^{-\widehat{k}}{{\widehat{c}}^{\prime }}_i,& \forall i=1,.Math.,N\\ {\widehat{m}}_i={\alpha }^{-\widehat{k}}{{\widehat{m}}^{\prime }}_i,& \forall i=1,.Math.,K\end{array}$

[0161] Optionally, if the word decoded Ĉ during the step 80 is not a code word, i.e. same is not part of the set of code words of the error correcting code implemented, the method further comprises a step 82 of synchronizing the received signal by applying the estimated synchronization shift k̂, and the steps 72 to 80 are iterated until a stop criterion is satisfied.

[0162] The stop criterion consists e.g. of checking that the word decoded during the step 80 is a code word, or that a predetermined number of iterations has been performed.

[0163] Moreover, according to a variant, the steps 70 to 82 are applied periodically, with a period equal to a predetermined number of chips k.

[0164] FIG. 6 illustrates the decoding performance in a practical example wherein p=6, q=64. The non-binary error correcting code used is the NB-LDPC code on GF.sub.64, with variable nodes of degree 2 and parity nodes of degree 3, and a yield R=⅓.

[0165] The message to be transmitted comprises 20 source symbols of GF.sub.64 (corresponding to K×p =120 source bits), including the anchoring symbol. The code word generated by the non-binary LDPC coding contains N=60 symbols of GF.sub.64.

[0166] The code word symbols are modulated according to the first modified CCSK modulation, so as to obtain 60 sequences of q-1=63 chips, i.e. a frame of 3780 chips. The constant sequence Z is an “all set to zero” sequence.

[0167] The BPSK modulation is applied to chip sequences, including the sequence Z, according to the modulation scheme: 0->1 and 1->-1.

[0168] The signal obtained is made noisy with a Gaussian white noise of variance σ.sup.2 for simulating the transmission channel.

[0169] The result curves are plotted in the plane of the received frame error rate (FER) as a function of the signal-to-noise ratio SNR.

[0170] The curve F.sub.0 corresponds to the case without any synchronization shift (k=0).

[0171] The curves F.sub.1, F′.sub.1 correspond to a synchronization shift less than or equal to 4, the decoding being repeated periodically every k = 8 chips. The solid line curve F.sub.1 corresponds to the result after the first application of the joint decoding with the synchronization shift estimation, and the dotted line curve F.sub.1′ corresponds to the result after the application of the joint decoding with the synchronization shift estimation with an additional iteration.

[0172] The curves F.sub.2, F′.sub.2 correspond to a synchronization shift less than or equal to 10, the decoding being repeated periodically every k = 20 chips, the solid line curve F.sub.2 , respectively, corresponds to the result after the first application of the decoding together with the synchronization shift estimation, and the dotted line curve F.sub.2′ corresponds to the result after the application of the joint decoding with the synchronization shift estimation with an additional iteration.

[0173] The curves F.sub.3, F′.sub.3 correspond to a synchronization shift less than or equal to 15, the decoding being repeated periodically every k = 30 chips, the solid line curve F.sub.3 corresponds to the result after the first application of the decoding together with the synchronization shift estimation, and the curve F.sub.3′ dotted line corresponds to the result after the application of the joint decoding with the synchronization shift estimation with an additional iteration.

[0174] According to a variant of embodiment, the formation of the message M is done so as to “partially” determine the value of an anchoring symbol placed at a predetermined position either in the message M or in the code word C, the value belonging to a predetermined subset of GF.sub.q, with a cardinal greater than 1.

[0175] It should be further noted that if the anchoring symbol takes a value in a predetermined subset of 2.sup.α elements of GF.sub.q, with a < p, the message M then includes (K -1)p + a data bits.

[0176] In such case, a plurality of estimations of the synchronization shift can be determined during the step 78. Specifically, an estimation of the synchronization shift can be obtained for each possible value of the anchoring symbol. It is then possible to choose one of the estimations of the synchronization shift, using e.g. a likelihood criterion, or an a priori knowledge of the interval of the synchronization shift.

[0177] When the steps 70 to 82 e.g. are applied periodically, with a period equal to a predetermined number k̅ of chips, the synchronization shift is then deduced therefrom as a priori information k ∈

[00023]$\left[-\frac{\overline{k}}{2},+\frac{\overline{k}}{2}\right].$

If only one of the estimations obtained falls within said interval, it will then be possible to determine accurately the value of the synchronization shift.

[0178] In all the embodiments described hereinabove, the sequence of chips Z, associated with the symbol 0 of GF.sub.q, is a constant sequence formed by q-1 chips of the same value, and thus invariant to any circular shift (or circular permutation).

[0179] According to a variant of embodiment, the sequence of chips Z is invariant only to a predetermined subset of permutations corresponding to circular shifts.

[0180] In such variant, the sequence of chips Z is said to be partially invariant.

[0181] If the sequence of chips Z e.g. is invariant to permutations corresponding to circular shifts by an even number of positions, then Z will have the form:

[00024]$Z=\left(z,z^{\prime },z,z^{\prime },.Math.\right)$

[0182] If the chip sequence Z is invariant to the permutations corresponding to the circular shifts by a number [of] multiple of 3 positions, then Z will have the form:

[00025]$Z=\left(z,z^{\prime },z^{″},z,z^{\prime },z^{″},.Math.\right)$

[0183] In this way it is possible to apply all the steps of the invention, as described hereinabove, in particular the steps 70 to 82, considering a plurality of hypotheses on the synchronization shift, until the difference between the hypothesis considered and the true synchronization shift introduced by the channel corresponds to a permutation of the predetermined subset.

[0184] If the sequence of chips Z e.g. is invariant to the permutations corresponding to the circular shifts by an even number of positions, two hypotheses can be considered, a first hypothesis considering that the synchronization shift is even, and a second hypothesis considering that the synchronization shift is odd.

[0185] If the sequence of chips Z is invariant to the permutations corresponding to the circular shifts by a number [of] multiple of 3 positions, three hypotheses can be considered, considering that the synchronization shift is a multiple of three, a multiple of three plus one, or a multiple of three plus two, respectively.

[0186] Advantageously, the proposed method can be used for detecting the presence of a message. Advantageously, when the message is formed so that an anchoring symbol is placed at a predetermined position, the method can be further used for determining the synchronization shift, and consequently for jointly performing the synchronization and the error-correcting decoding after reception.

[0187] The detection of the presence of a message is of interest as such for certain applications.

[0188] Moreover, in the case of a transmitted message protected by a CRC (Cyclic Redundancy Check) correcting code, determining the synchronization shift can be envisaged by testing all the possible values.