# Patent

## Title
Method of transmitting a digital signal for a non-orthogonal MS-MARC system, and a corresponding program product and relay device

## Abstract

A method for non-orthogonal transmission of a signal intended for a system with N sources, M relays and a single receiver, in which simultaneous transmission over a single spectral resource by the relays is simultaneous with a transmission over a single spectral resource by the sources. The method includes, for each relay: joint iterative detection/decoding of messages transmitted respectively by the sources during first transmission intervals to obtain decoded messages; detecting errors on the decoded messages; interleaving the detected error-free messages, followed by algebraic network coding including a linear combination, in a finite field of an order higher than two, of the interleaved messages to obtain a coded message, the linear combinations being independent, in pairs, between the relays; and channel coding to generate a signal representative of the network coded message and to transmit this signal during the subsequent transmission intervals simultaneously with a transmission by the sources.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This Application is a Section 371 National Stage Application of International Application No. PCT/FR2012/053027, filed Dec. 20, 2012, which is incorporated by reference in its entirety and published as WO 2013/093361 on Jun. 27, 2013, not in English.
FIELD OF THE INVENTION
The present invention relates to the field of telecommunications. Within this field, the invention relates more particularly to transmitting coded data in a multi-source-multi-relay (MS-MR) network. An MS-MR network is a telecommunications system that, for a given destination, comprises at least four nodes: at least two sources and at least two relays. The invention relates to network coding. It relates to improving the quality of data transmission, and in particular to improving the performance of error-correcting decoding at the destination.
The invention applies particularly, but not exclusively, to transmitting data via mobile networks, e.g. for real time applications.
PRIOR ART
Networks, and in particular mobile networks, seek to find significant improvements in terms of capacity, reliability, consumption, etc. The transmission channel of a mobile network has the reputation of being difficult and it leads to transmission reliability that is relatively mediocre. Considerable progress has been made over the last few years in terms of coding and modulation, in particular for considerations of consumption and capacity. In a mobile network in which a plurality of sources and destinations are sharing the same resources (time, frequency, and space), it is necessary to keep transmission power as low as possible.
Low power goes against coverage and thus against the capacity of the system and more generally against its performance.
In order to increase coverage, to make communications more reliable, and more generally to improve performance, one approach consists in relying on relays for increasing spectrum efficiency and thus for improving the efficiency of transmission and the reliability of systems.
The basic topology of an MS-MR system is shown in FIG. 1 and is such that the sources, nodes S1 and S2, broadcast their code information sequences for the attention of relays R1 and R2 and of the destination D; the sources are typically user terminals seeking to reach the same base station with the help of relays. Each relay decodes the signals it receives coming from the sources S1 to S2 and jointly re-encodes the sequences obtained by the decoding, while also adding their own redundancy, thereby creating a network code. At the destination D, the spatially-distributed code sequences, comprising the received code sequences coming directly from the sources S1 and S2 and the code sequences coming from the relays R1 and R2 are decoded by means of channel decoding algorithms and network decoding algorithms.
Network coding is a form of co-operation in which the nodes of the network share not only their own resources (power, bandwidth, etc.) but also their calculation capacity in order to create a distributed code of ever increasing power as the information propagates through the nodes. This leads to substantial gains in terms of diversity and of coding, and thus in terms of transmission reliability.
A major difficulty lies in the links from the sources to the relays not always enabling all of the relays to detect the messages from the sources without error on the basis of the signals they receive. This difficulty may be encountered for example in a transmission channel from sources to relays that suffers from Rayleigh fading and in the absence of knowledge about the channel at the sources. Under such circumstances, there exists a non-zero probability of outage, with the relays decoding the messages from the sources imperfectly. Such imperfection can lead to errors propagating towards the destination.
In addition, achieving maximum diversity means that it must be possible to recover all of the messages from the sources even in the event of outages on a number of links equal to the number of relays.
Article [1] mentions a network code for a simple MS-MR system as shown in FIG. 1. That MS-MR system corresponds to the basic topology. The system is limited to two sources and two relays. The MS-MR system under consideration is such that all of the source-to-destination and relay-to-destination links are orthogonal and use different spectrum resources (i.e. the radio resources used between the sources and the relays are separate in time or in frequency). This separation leads to a loss of spectrum efficiency since the radio resource is subdivided among a plurality of users.
The two sources S1 and S2 broadcast the coded information to the relays R1, R1 and to the destination D. The relays R1 and R2 take the streams that are assumed to be perfectly decoded from the two users, and combine them in linear manner using a linear network coding scheme defined in a finite field of order 4. That network code enables the maximum diversity to be achieved, which is three (M+1), since any pair of two codes taken from the four codes I1, I2, I+I2, and I1+2I2 suffices to reconstitute the messages I1 and I2 coming from the sources, in the event of outage in two links.
In that system, decoding errors can be reduced solely in the absence of interference, since the MS-MR system under consideration is purely theoretical and is assumed to suffer from no interference because the links are completely orthogonal. In addition, the constraints that consist in imposing links that are completely orthogonal lead to non-optimum use of the spectrum resource, and thus to a limit on the capacity of the network.
The relays of MS-MR systems may equally well be fixed relays or mobile relays. Given the density of communications to be transmitted in densely populated areas, the number of relays may be large and much greater than two. In order to cover such zones, it may be preferable to use fixed relays rather than base stations since base stations can be considerably more expensive. In alternative manner, it is possible to use mobile relays. Such mobile relays are typically mobile terminals. Such an MS-MR system becomes very complex and a transmission method in accordance with [1] consumes a large amount of resources, thereby making the system relatively unattractive.
MAIN CHARACTERISTICS OF THE INVENTION
The invention provides a method of non-orthogonal transmission of a signal, for use in a system having N sources, M relays, and a single receiver, wherein simultaneous transmission over a common spectrum resource by the relays takes place simultaneously with simultaneous transmission over the same spectrum resource by the sources, the method comprising for each relay:

    
    
        a step of iterative joint detection and decoding of messages transmitted respectively by the sources during αN first transmission intervals to obtain decoded messages;
        a step of detecting errors in the decoded messages;
        a step of interleaving only the messages that are detected without error, followed by a step of algebraic network coding consisting in a linear combination in a finite field of order strictly greater than two of the interleaved messages to obtain a coded message, the linear combinations being independent in pairs between the relays of the system; and
        a step of shaping comprising channel coding to generate a signal representative of the network coded message and to transmit this signal during the following (1−α)N transmission intervals simultaneously with transmission from the sources, where α∈]0,1[.
    
    


Such transmission of the invention is adapted to a system having at least two relays that relay messages coming from at least two sources to a single destination. The system is said to be multi-user and multi-relay. The transmission protocol is said to be non-orthogonal since it takes place in two stages. During the first stage, the sources transmit simultaneously while occupying a common spectrum resource. The relays and the destination listen, detect, and decode. The signals that are transmitted interfere both at the relays and at the destination. During the second stage, the sources transmit simultaneously, occupying the same spectrum resource, and the relays transmit simultaneously the signals they received and processed during the first stage, while also occupying the same spectrum resource. The transmitted signals interfere at the destination. The source-to-relay links, the relay-to-destination links, and the source-to-destination links are non-orthogonal. The use of the term non-orthogonal comes from the two stages of transmission that take place with links that are non-orthogonal: during the first stage the links are non-orthogonal between the sources and the relays and between the sources and the destination, and during the second stage the links are non-orthogonal between the sources and the relays, between the sources and the destination, and between the relays and the destination. Thus, during the first stage there is interference at the relays and interference at the destination between signals coming solely from the sources. During the second stage, there is interference at the destination between signals coming from the sources and signals coming from the relays.
The network coding advantageously makes it possible to reach the maximum order of diversity, which is M+1 for a system having M relays; the maximum order is given by the number of different paths that can be followed by the signals transmitted by one of the sources towards the destination (the direct path and the M paths via each of the M relays). The independence in pairs of the linear combinations defined in a finite field of order greater than two as used by the relays makes it possible to reach an order of diversity equal to M+1, since eliminating the M links from among the M+1 links enables the destination always to find the source signals, given the irreversible nature of the constructed linear system.
In a prior art system having two relays, the use of an XOR function (⊕) at each of the relays for performing the combination does not enable maximum diversity to be achieved. When the two source-to-destination links suffer an outage, it is not possible at the destination to reconstitute the messages I1 and I2 coming from the two sources on the basis of the messages I1⊕I2 coming from the relays. The information I1⊕I2 received at the destination coming from the relays does not enable either I1 or I2 to be reconstituted in the absence of information I1 or I2 received directly from the sources. Unlike the techniques known from the prior art, the invention is adapted to any number of relays greater than or equal to two.
The invention makes it possible to maximize spectrum efficiency by allowing signals to collide at the relays and at the destination, given simultaneous transmission by the sources over a common spectrum resource and simultaneous transmission by the relays over a common spectrum resource. Thus, the invention takes account not only of the non-orthogonal source-to-relay and source-to-destination links, but also of the non-orthogonal relay-to-destination links. Spectrum efficiency is optimized when the sources and the relays occupy the same resources during their respective transmissions, which corresponds to a particular implementation of the invention.
The invention also makes it possible to perform iterative joint channel and network decoding at the destination, given the interleaving performed by the relays before network coding. Interleaving each message that is received without error reduces the correlation between the channel coding performed at the sources on the same messages when non-interleaved and the channel and network coding performed at the relays on the same messages. Consequently, this ensures that joint channel and network decoding at the destination making use firstly of the signals coming directly from the sources and secondly of the signals coming from the relays is of higher performance than channel decoding performed independently of network decoding.
Relaying in accordance with the invention serves to increase the reliability of transmissions between the sources and the destination, while minimizing the propagation of errors from the relays to the destination, given the adaptive nature of the network coding. Such a method is thus particularly suited to a system deployed in an urban environment in which the transmission channel generally presents a profile with so-called Rayleigh fading. Such fading disturbs the transmitted signal and gives rise to a non-zero probability of erroneous detection (known as the “outage” probability). An adaptive (or selective) relaying method of the invention advantageously makes it possible for a relay not to transmit information if all of the messages it receives are erroneous while also enabling the relay to transmit information representative of a source even if only the message coming from that source is detected without error. The method thus accommodates noisy source-to-relay links.
The invention is particularly adapted to half-duplex relays, but it is equally capable of being applied to full-duplex relays. Co-operative systems making use of half-duplex relays are very attractive because their communications schemes are simpler than for full-duplex relays, because they are easy to implement, and because they are of smaller cost.
The invention also provides a relay for a non-orthogonal MS-MR system.
Thus, a relay of the invention for implementing a transmission method of the invention comprises:

    
    
        means for iterative joint detection and decoding to separate the streams coming from the sources and to determine for each stream a message representative of a code word transmitted by a source during αN first transmission intervals;
        means for detecting errors;
        interleaving means for interleaving only those messages that are detected without error;
        means for algebraic network coding of vector aj=[a1,j a2,j . . . aN,j]T consisting in a linear combination of the interleaved messages in a finite field of order strictly greater than two, the linear combinations being independent in pairs between the relays of the system; and
        means for shaping, comprising channel coding of the messages from the network coding to generate a signal representative of the network coded messages and to transmit this signal during the following (1−α)N transmission intervals simultaneously with transmission by the sources, with α∈]0,1[.
    
    


A relay of the invention is advantageously of the half-duplex (HD) type.
In a particular implementation, a transmission method further comprises a step of shaping a control signal specifying the messages detected without error represented in the representative signal for the signal receiver.
Such a message makes it possible to simplify considerably the processing on reception.
In a particular implementation, a transmission method is such that the channel coding is of the systematic type.
Coding of this type makes it possible very easily to punch the systematic portion of the code and to use the relay to transmit only the parity portion, thereby optimizing spectrum efficiency of the transmission by the relay to the destination.
In a particular implementation, the channel coding is binary and the transmission method further comprises:

    
    
        a step of binary-to-symbol conversion between the interleaving step and the algebraic coding step; and
        a step of symbol-to-binary conversion after the algebraic network coding step.
    
    


This implementation is particularly adapted to binary source channel coding.
In a particular implementation, a transmission method is such that the finite field of order strictly greater than two is the Galois field of order four.
The order four for the field corresponds to an optimum selection for a number M of relays up to three.
In a particular implementation, the transmission method is such that the step of detecting errors is performed by means of using redundancy information of the cyclic type associated with a message transmitted by a source.
This implementation has the advantage of being particularly simple to perform. It is adapted to systematic type encoding at the source.
In a particular implementation, a transmission method is such that the step of iterative joint detection and decoding jointly performs multi-user detection and soft input and soft output decoding.
This implementation has the advantage of providing better performance than multi-user detection followed by decoding without exchanging a priori information between the detection and the decoding.
In a particular implementation, a transmission method is such that the iterative joint detection and decoding steps implement space-time decoding.
This implementation is particularly adapted to a system in which the sources have a plurality of transmit antennas and perform space-time coding. When the relays are fitted with a plurality of receive antennas, the system is said to be a multiple-input or multiple-output (MIMO) system, otherwise it is said to be a multiple-input or single-output (MISO) system.
In a particular implementation, a transmission method is such that the step of shaping comprises modulating messages before transmission, and interleaving between the channel coding and the modulation.
This implementation provides great flexibility in constructing the modulation and coding scheme, by enabling the modulation and the coding to be selected independently. In addition, the channel interleaver makes it possible to use an iterative method between detection and decoding at the destination and at the relay.
In a particular implementation, a transmission method is such that the N sources transmit the messages simultaneously over a common spectrum resource, each of which messages comprises a systematic portion and a first redundancy portion during the αN first transmission intervals, and they transmit second redundancy portions simultaneously over the same spectrum resource during the following (1−α)N transmission intervals while the relays are simultaneously transmitting third redundancy portions.
In a particular implementation, a transmission method performs distributed turbo coding between the sources and the relays. The coding step in the sources also makes use of a convolutional coder.
For example, the distributed turbo code is constituted at a source by a recursive systematic convolutional code (RSCC) of coding rate 1⁄3, and at the relays an RSCC of coding rate 2⁄3 preceded by an interleaver for each stream from the decoder. Selecting a distributed turbo code with parallel concatenation enables spatially distributed network coding to be implemented very simply for a non-orthogonal MS-MR system with a half-duplex relay by having by construction a code made up of a concatenation of a systematic portion and two redundancy portions (a first redundancy portion determined and transmitted by a source and a second redundancy portion determined and transmitted by the relays). This concatenation makes it possible for a source to transmit the systematic portion and the first redundancy portion during the two transmission intervals, and for the relays to transmit the second redundancy portion during the second transmission interval. This concatenation thus makes it simple to ensure that the relays provide new redundancy information to the information bits corresponding to the systematic portion independently of the first redundancy portion transmitted during the two transmission intervals from the sources to the destination. The destination thus has a plurality of redundancies, thereby enabling very powerful decoding to be performed and thus improving reliability.
The invention also provides a reception method for a receiver of a non-orthogonal MS-MR system for implementing a transmission method of the invention. The reception method comprises in iterative manner:

    
    
        a first multi-user detection step of detecting coded messages transmitted simultaneously by the respective sources to obtain soft information about the respective messages coded by the sources;
        a second multi-user detection step of detecting coded messages transmitted simultaneously respectively by the sources and by the relays to obtain soft information about the messages coded by the sources and the relays;
        a first step of soft channel decoding in parallel of the N messages coded respectively by the N sources; and
        a second step of algorithmic soft network decoding in cascade of the M messages coded respectively by the M relays under the control of information about the messages detected without error by the relays;
    
    


the first step of soft channel decoding N messages uses as a priori information the soft information coming from the first detection step and the soft information relating to the source messages coming from the second detection step in order to provide the soft information about the M messages decoded in the second step of algebraic soft network decoding;
the second step of soft network decoding M messages uses as a priori information the soft information coming from the first and second detection steps to respond by supplying soft information about the decoded messages to the second detection step;
the first step of soft channel decoding N messages and the second step of soft network decoding M messages supplying each other mutually with extrinsic information, this mutual supply being under the control of information coming from the relays identifying which messages were detected without error by the relays.
The invention also provides a receiver for a non-orthogonal MS-MR system for implementing a transmission method of the invention. The receiver comprises:

    
    
        first detection means for multi-user joint detection to separate the simultaneous streams of coded messages coming respectively from the N sources during a first stage of transmission and to generate soft information about the coded messages;
        second detection means for multi-user joint detection to separate the simultaneous streams of coded messages coming respectively from the N sources and from the M relays during a second stage of transmission and to generate soft information about the coded messages coming respectively from the sources and from the relays;
        as many soft decoders in parallel as there are sources for soft decoding of the messages coded respectively by the sources while using as a priori information the soft information coming from the first detection means and the soft information about the source messages coming from the second detection means and to generate soft information about the decoded messages;
        as many soft algebraic decoders operating in cascade as there are relays for soft decoding of the messages coded respectively by the relays while using as a priori information the soft information coming from the first and second detection means and to respond by supplying soft information about the decoded messages to the second detection means;
    
    


the N soft channel decoders and the M soft algebraic decoders supplying each other mutually with extrinsic information, this mutual supply being under the control of information coming from the relays identifying which messages were detected without error by the relays;

    
    
        decision-taking means for the channel decoders to obtain an estimate of the messages coming respectively from the sources.
    
    


This reception method and this receiver have the advantage of being adapted to a non-orthogonal MS-MR system implementing a transmission method of the invention.
Each of the above-described implementations may optionally be combined with one or more of the other implementations in order to define yet more implementations.
The invention also provides an optionally MIMO non-orthogonal MS-MR system adapted to implement the method of the invention.
Thus a non-orthogonal MS-MR system of the invention includes at least two relays of the invention.
In a preferred implementation, the steps of the transmission method and/or of the reception method are determined by instructions of a transmission and/or a reception program incorporated in one or more electronic circuits such as chips, themselves suitable for being arranged in electronic devices of the non-orthogonal MS-MR system. The transmission and/or reception method of the invention may also be performed when the program is loaded into a calculation member such as a processor or the equivalent with its operation then being controlled by executing the program.
Consequently, the invention also applies to a computer program, in particular a computer program on or in a data medium, and suitable for performing the invention. The program may use any programming language, and being in the form of source code, object code, or code intermediate between source code and object code, such as in a partially compiled form, or in any other desirable form for implementing a method of the invention.
The data medium may be any entity or device capable of storing the program. By way of example, the medium may comprise storage means such as a read-only memory (ROM), e.g. a compact disk (CD) ROM, or a microelectronic circuit ROM, or indeed magnetic recording means, e.g. a hard disk or a universal serial bus (USB) key.
Alternatively, the data medium may be an integrated circuit in which the program is incorporated, the circuit being adapted to execute or to be used in the execution of the method in question.
Furthermore, the program may be converted into a transmissible form such as an electrical or optical signal, which may be conveyed via an electrical or optical cable, by radio, or by other means. The program of the invention may in particular be downloaded from an Internet type network.



LIST OF FIGURES
Other characteristics and advantages of the invention appear more clearly on reading the following description of preferred methods given merely as illustrative and non-limiting examples, and with reference to the accompanying drawings, in which:
FIG. 1 shows an example of a prior art MS-MR system with orthogonal links between the various nodes;
FIG. 2 is a diagram showing the topology of MS-MR systems having N sources S1, . . . , SN and M relays R1, . . . , RN, for a receiver D;
FIG. 3a is a diagram of a non-orthogonal MS-MR system of the invention such that the links are non-orthogonal between the sources and the relays, between the sources and the destination, and between the relays and the destination, the figure showing the first stage of transmission;
FIG. 3b is a diagram of a non-orthogonal MS-MR system of the invention such that the links are non-orthogonal between the sources and the relays, between the sources and the destination, and between the relays and the destination, the figure showing the second stage of transmission;
FIG. 4 is a simplified flow chart of the transmission method of the invention as implemented by a non-orthogonal MS-MR system shown in FIGS. 3a and 3b; 
FIG. 5 is a diagram of a first embodiment of an MS-MR system of the invention in which the space-time modulation and coding schemes at the sources and at the relays are defined in the binary field;
FIG. 6 is a diagram of an iterative joint detector and decoder JDDj that jointly detects and decodes messages transmitted simultaneously by the sources and received by the relay;
FIG. 7 is a diagram of a joint detector MAPD-E;
FIG. 8 is a diagram of a decoder DecSi;
FIG. 9 is a diagram of a second embodiment of an MS-MR system of the invention in which the space-time modulation and coding schemes at the sources and at the relays are defined in the field defined by the algebraic network code;
FIG. 10a is a diagram of a destination receiver of the invention;
FIG. 10b is a diagram of an embodiment of the detector MAPD-EII of the FIG. 10a receiver;
FIG. 11 is a diagram of an embodiment of the SISO decoder Algj when all of the transmissions are performed in the field F4, i.e. in the second embodiment shown in FIG. 9 in which the channel coding is of the algebraic type;
FIG. 12 is a diagram of an embodiment of the SISO decoder Alg for binary channel code, i.e. as in the first embodiment shown in FIG. 5; and
FIGS. 13 to 15 are diagrams showing the adaptive structure of the receiver as a function of the in-band information transmitted by the relays.



DESCRIPTION OF PARTICULAR IMPLEMENTATIONS
The following notation is used in this application.
All vectors use bold characters. A vector v has its kth element written [v]k, or vk.
Fq is the q-element Galois field,  is the field of real numbers and  is the field of complex numbers.
Matrices/tensors use capital letters in bold. If X is a matrix of dimensions N×M belonging to the field E, i.e. X∈EN×M, then Xk denotes its kth column (k=1, . . . , M).
Functions use non-italic capital letters. A multi-dimensional function F is applied to input in the form of a matrix A of dimensions m×q, where each element ai,j (for all i=1, . . . , m and j=1, . . . , q) belongs to the set E, and it outputs a matrix B of dimensions n×p in which each element bi,j (for all i=1, . . . , n and j=1, . . . , p) belonging to the set G, such that F(A)=B written: F:Em×q→Gn×p.
The probability density of a complex random variable x with circularly symmetrical Gaussian distribution of mean μx and covariance σx2 is written: CN(μx,σx2).
A transmission of the invention is implemented in MS-MR systems having the topology shown in FIG. 2. This topology is such that the sources, nodes Si, i∈{1, . . . N} broadcast their coded information sequences for the attention of relays Rj, j∈{1, . . . , M} and of the destination D; the sources are typically user terminals seeking to reach the same base station with the help of relays. Each relay decodes the signals received from the sources S1 to SN and re-encodes the decoded sequences jointly while adding its own redundancy so as to create a network code. At the destination D, the spatially-distributed code sequences comprising the code sequences received directly from the N sources and the code sequences from the M relays are decoded by channel decoding algorithms and by network decoding algorithms.
The invention uses relays with a new non-orthogonal transmission protocol as shown in FIGS. 3a and 3b to improve the spectrum efficiency of transmission while making simple and effective decoding possible at the destination. FIG. 3a shows the first stage of transmission during which only the sources transmit simultaneously to the relays and to the destination. During this stage, the relays are silent. FIG. 3b shows the second stage of transmission during which the sources transmit simultaneously to the relays and to the destination. During this second stage, the relays transmit simultaneously during the same number of transmission intervals to the destination.
Thus, a method 1 of the invention is as shown in FIG. 4.
There is no constraint on the transmission channel; it may suffer from fast fading, with the coefficients of the matrices representing the transmission channel changing on each occasion the channel is used, or it may have slow B-block fading in which the coefficients remain constant over N/B consecutive uses (block) of the channel but change from one block to another, and the channel may be frequency selected, and it may be a MIMO channel. The notations adopted in the description below correspond to a slow 1-block fading channel, i.e. a channel that is quasi-static.
In the description below, the nodes (sources, relays, and destination) are assumed to be perfectly synchronized and the sources are independent (there is no correlation between them).
The non-orthogonal transmission protocol is such that the transmission of information to the destination takes place over Nuse uses of the channel arranged in two stages: in a first stage, the sources transmit during αNuse=Chuse uses of the channel, and in a second stage the sources and the relays transmit simultaneously during (1−α)Nuse=ChuseR uses of the channel.
In a first aspect of the invention, the non-orthogonal transmission method 1 of transmitting a signal is performed by the relays Rj of the system.
A source data block ui∈FqKi∈{1, . . . , N} is a message vector of length K in which the components taken their values in a finite field Fq of integer order q.
The statistically independent sources Si perform channel coding of the information data ui while adding a cyclic redundancy check (CRC) to a systematic portion for the purpose of verifying message integrity. The sources Si having Tsi transmit antennas use a space-time modulation and coding scheme Θi defined on Fq (e.g. the binary field F2 or the four-element finite field F4) that associates every block ui with coded and modulated symbols




  
    X
    i
  
  ∈
  
    χ
    i
    
      
        T
        
          S
          i
        
      
      ×
      
        N
        use
      
    
  




belonging to the complex constellations χi of cardinalities |χi|=2wi, wi∈. A symbol of Fq has a binary representation containing ln2(q) bits. If the ratio





  
    s
    i
  
  =
  
    
      w
      i
    
    
      
        ln
        2
      
      ⁡
      
        (
        q
        )
      
    
  




is an integer, it represents the number of symbols of Fq carried by the modulation. The function Θi may be described in the following generic manner:





  
    Θ
    i
  
  :
  
    
      F
      q
      K
    
    →
    
      
        X
        i
        
          
            T
            
              S
              i
            
          
          ×
          
            N
            use
          
        
      
      .
    
  




The channel coding and the space-time coding are performed by the coders ENCi.

During the first stage of transmission, the N sources respectively transmit the N symbols




  
    X
    i
    
      (
      1
      )
    
  
  ∈
  
    
      χ
      i
      
        
          T
          
            S
            i
          
        
        ×
        
          Ch
          use
        
      
    
    .
  




During the second stage of transmission, the N sources transmit respectively the N symbols





  
    X
    i
    
      (
      2
      )
    
  
  ∈
  
    
      χ
      i
      
        
          T
          
            S
            i
          
        
        ×
        
          Ch
          useR
        
      
    
    .
  




Each relay Rj has NRj receive antennas and TRj transmit antennas. During the first stage of transmission, each relay receives the disturbed versions of the N source signals transmitted over the source-relay channels. The channel between the sources Si and a relay Rj is designated by the set of coefficients of the MIMO channel:




  
    {
    
      
        H
        
          
            
              S
              i
            
            ⁢
            
              R
              j
            
          
          ,
          k
          ,
          m
        
      
      ∈
      
        C
        
          
            N
            
              R
              j
            
          
          ×
          
            T
            
              S
              i
            
          
        
      
    
    }
  
  .




The signal received at the instant k by the relay Rj is expressed in the following form:




  
    
      y
      
        
          R
          j
        
        ,
        k
      
    
    =
    
      
        
          ∑
          
            i
            =
            1
          
          N
        
        ⁢
        
          
            ∑
            
              m
              =
              0
            
            
              L
              m
            
          
          ⁢
          
            
              H
              
                
                  
                    S
                    i
                  
                  ⁢
                  
                    R
                    j
                  
                
                ,
                k
                ,
                m
              
            
            ⁢
            
              X
              
                i
                ,
                
                  k
                  -
                  m
                
              
              
                (
                1
                )
              
            
          
        
      
      +
      
        n
        
          
            R
            j
          
          ,
          k
        
      
    
  




  
    
      k
      ∈
      
        {
        
          1
          ,
          ...
          ⁢
          
            
          
          ,
          
            C
            ⁢
            
              
            
            ⁢
            
              h
              use
            
          
        
        }
      
    
    ,
    
      

    
    ⁢
    
      j
      ∈
      
        {
        
          1
          ,
          ...
          ⁢
          
            
          
          ,
          M
        
        }
      
    
  



where





  
    n
    
      
        R
        j
      
      ,
      k
    
  
  ∈
  
    C
    
      N
      
        R
        j
      
    
  




designates the additive noise vector at the relay Rj at the instant k and Lm designates the memory of the channel. The memory effect of the channel is associated with the propagation delay spread. This delay causes transmitted signals to be superposed, thereby giving rise to inter-symbol interference.

The destination has ND receive antennas. During the first stage of transmission, the destination then receives the disturbed versions of the N source signals transmitted by the source-to-destination channels. Let




  
    H
    
      
        S
        i
      
      ⁢
      D
    
  
  ∈
  
    C
    
      
        N
        D
      
      ×
      
        T
        
          S
          i
        
      
    
  




be the matrices of fading coefficients associated with the N source-to-destination channels. The signal received by the destination during the first stage of transmission is written:





  
    
      y
      
        
          1
          ⁢
          D
        
        ,
        k
      
    
    =
    
      
        
          ∑
          
            i
            =
            1
          
          N
        
        ⁢
        
          
            ∑
            
              m
              =
              0
            
            
              L
              m
            
          
          ⁢
          
            
              H
              
                
                  
                    S
                    i
                  
                  ⁢
                  D
                
                ,
                k
                ,
                m
              
            
            ⁢
            
              X
              
                i
                ,
                
                  k
                  -
                  m
                
              
              
                (
                1
                )
              
            
          
        
      
      +
      
        n
        
          
            1
            ⁢
            D
          
          ,
          k
        
      
    
  
  ,
  
    

  
  ⁢
  
    k
    ∈
    
      {
      
        1
        ,
        ...
        ⁢
        
          
        
        ,
        
          C
          ⁢
          
            
          
          ⁢
          
            h
            use
          
        
      
      }
    
  




where n1D,k∈ND designates the additive noise vector during the first stage of transmission at the destination at instant k.

Each relay Rj has a multi-user iterative joint detector and decoder for performing turbo multi-user detection or “turbo-MUD” that performs joint detection and decoding 2 in iterative manner on the signals received during the first stage in order to obtain the estimated signal vectors from each source ûi∈FqK. This joint processing relies on observing the received signal representative of all of the source messages as distorted by the channel and on soft input and output decoding of the channel code from each source. An estimate of the message transmitted by each source is available after a certain number of iterations, which number can be set.
The relay Rj then uses CRC detectors in parallel to detect 3 from the redundant portion of the messages any errors that might have occurred in the previously estimated messages. Let Jj⊂{1, . . . , N} be the set of message indices detected without error by the relay Rj of cardinality ∫.
In parallel, the relay Rj interleaves 4 only the J non-erroneous messages ûi,i∈Jj with a first type of interleaver πj of size K.
The relay applies 5 a function ΘRj to the interleaved messages by means of a network coder in order to obtain a network coded message:

uRj=ΘRj({ûi,i∈Jj})∈FqK 

The function ΘRj linearly combines the interleaved messages in a finite field of dimension strictly greater than two. This linear operation is referred to as network coding. A network code is a linear combination of N source messages received by a relay that can be represented by a vector of dimension N in which each component is non-zero. The network coding associated with the relay Rj is defined by the vector aj=[a1,j a2,j . . . aN,j]T of dimension N. Assuming that this relay detects only J messages without error of indices contained in the set Jj⊂{1, . . . , N}, the result of the network coding uRj is the linear combination uRj=Σi∈Jjai,jûi. This amounts to zeroing the coefficients {ai,j}i∉Jj of the vector aj having indices that are not included in the set Jj. It is thus possible to define effective network coding for each relay that depends on the source messages that it was not possible to detect without error. In this definition, non-transmission of a relay is an effective network code consisting in a zero vector of dimension N.
In a system having M relays, the order of maximum diversity is M+1. A system having N sources and M relays is said to have maximum diversity if, in the event of outage of any M links from among the NM S-R links and the N+M S-D and R-D links, it is still possible to recover the N messages from the sources (the messages associated with the remaining links are assumed to be detected without error). Let T=[ING] be the systematic generator matrix where IN is the identity matrix of dimension N, and G represents the M vectors of the effective network code of the relays. The vectors aj=[a1,j a2,j . . . aN,j]T of the network code can be determined by randomly drawing in independent manner the components of the vectors after selecting the order of the field to be strictly greater than two. After the draw, it is necessary to verify that maximum diversity has been reached. This makes it necessary to consider all configurations of Q outages among the MN S-R links, Q∈{0, 1, . . . , M} and to make sure that the systematic generator matrix T=[ING] satisfies the following conditions: after eliminating M−Q columns from the matrix T, the remaining N+Q columns have the property of having a rank of not less than N. It should be observed that it suffices to test the case Q=0 (no outages in the MN source destination channels), with the validity of the other conditions being mathematically deduced therefrom.
The channel coded messages from the sources and the corresponding messages interleaved by the relays and then subjected to channel coding by the function ΘRj forms a distributed turbo code. The interleaving enables the destination to perform iterative joint channel/network decoding based on the signals received from the sources and the relays. When J=1, the linear operation amounts to identity.
The message resulting from the network coding is shaped 6, 7 by the relay in order to obtain the signal:




  
    X
    
      R
      j
    
  
  ∈
  
    
      C
      
        
          T
          
            R
            j
          
        
        ×
        
          Ch
          useR
        
      
    
    .
  




Shaping typically comprises an operation of space-time modulation and coding. The shaper signal XRj is transmitted from the antennas of the relay. The relay Rj informs the destination D of the J messages involved in the network coding by means of an in-band control signal, e.g. consisting in control bits. Alternatively, the relay may indicate which messages were detected with error.

During the second stage of the non-orthogonal protocol, the sources and the relays transmit simultaneously for the same number of uses ChuseR of the channel over the same radio resource. The signals transmitted simultaneously by the sources and by the relays interfere at the destination. Let




  
    H
    
      
        R
        j
      
      ⁢
      D
    
  
  ∈
  
    C
    
      
        N
        D
      
      ×
      
        T
        
          R
          j
        
      
    
  




be the matrices of the coefficients of the M relay-to-destination channels. The signal received at the destination during the second stage is written as follows:

y2D,k=Σj=1MΣm=0LmHRjD,k,mXRj,k-m+Σi=1NΣm=0LmHSiD,k,mXi,k-m(2)+n2D,kk∈{1, . . . , ChuseR}

where n2D,k∈ND is the additive noise during the second stage of transmission at the destination at instant k.

The destination observes a superposition of the symbols transmitted by the sources during the first stage of transmission followed by the symbols transmitted by the sources and by the relays during the second stage. At the end of the second stage of transmission, the destination has signals available to it that come directly from the sources and signals that come simultaneously from the sources and from the relays. The destination can then proceed with joint channel network decoding in order to recover the source messages: u1 . . . uN from the received signals.
The space-time modulation and coding schemes at the sources and at the relays are defined either in the binary field or in the field defined by the network coding, i.e. decoding them provides probabilistic information about the representation of the messages from the sources either in the binary field or in the field associated with the network coding.
The description of the invention is given in detail on the basis of particular embodiments of non-orthogonal MS-MR systems having two sources and two relays. Each source has a transmit antenna, each relay has a receive antenna and a transmit antenna, and the destination has a receive antenna.
In a first embodiment of the invention, the modulation and channel coding at the sources and at the relays are defined in the binary field. An embodiment is shown in FIG. 5. The modulation and coding schemes at the sources and at the relays are based on a scheme of the bit interleaved coded modulation (BICM) type that corresponds to concatenating binary channel coding (defined in the binary field) with binary interleaving and with bit-to-symbol Gray coding (modulation). The channel coding is preferably of the systematic type, e.g. the encoders are based on recursive systematic convolutional (RSC) codes, possibly associated with puncturing.
Each source Si, i=1 or 2, has an encoder ENCci for performing the channel coding on the messages for transmission. A message ui∈F2K is coded as a vector ci∈F2ni where




  
    n
    i
  
  K




is the coding rate of the encoder associated with the source Si. The code words ci are shared between two words ci(1)∈F2αNusesi and ci(2)∈F2(1-α)Nusesi. They are then interleaved with a binary interleaver πchi. The interleaver is necessary for ensuring independence between the coded values by reducing the correlation between the successive code values. The output from the interleaver corresponds to the sequences Vi(1)∈F2αNuse×si and Vi(2)∈F2(1-α)Nuse×si.

The interleaved words are modulated by a modulator MODi into sequences xi(1)∈αNuse and xi(2)∈(1-α)Nuse with 2si being the order of the modulation; the labeling is performed by the following bijective function: φi:F2si→Xi. Let vi,k,l=φi,l−1(xi,k) be the lth bit corresponding to the modulated symbol xi,k (corresponding to the bits of the source i {vi,k,l: l=1, . . . , si}).
Each relay Rj, j=1 or 2, comprises an iterative joint detector and decoder (or Turbo MUD) JDDj with as many outputs as there are sources Si, an error detector CRCji on each output of the joint detector and decoder, an interleaver πji after each error detector CRCji, an algebraic network coder CRj connected to the outputs of the interleavers πij, and a shaper module MCSj at the output from the algebraic network coder. In this embodiment, each relay also has as many binary-to-algebraic converters CBAji at the input to the network coding as there are sources together with an algebraic-to-binary converter CABj at the output from the network coding.
Each iterative joint detector and decoder JDDj jointly detects and decodes messages transmitted simultaneously by the sources. It is shown in FIG. 6. It comprises a joint detector MAPD-E, two decoders DecS1, DecS2 corresponding to each of the sources, two interleavers πch1, πch2 between the output to the decoders and the inputs of the detector, and two deinterleavers πch1−1, πch2−1 between the outputs from the detector and the inputs of the decoders. The interleavers are of the same type as those used in the sources. The deinterleavers are the inverses of the interleavers. The relay Rj receives a signal yRj,k resulting from interference between the signals from the two sources Si:

yRj,k=h1,Rjx1,k(1)+h2,Rjx2,k(1)+nRj,k, k∈{1, . . . , αNuse}

where nRj,k is additive noise with the distribution CN(0,σn2), and hi,Rj is the coefficient of the channel between the source Si and the relay Rj. The joint detector MAPD-E (or multi-user detector (MUD)) based on the maximum a posteriori criterion receives the signal yRj,k and exchanges information with the decoders DecS1, DecS2 to extract the information û1, û2 from each source. The exchange is applied to the detected bits and to the decoded bits. On each iteration, the decoders receive as input the intrinsic logarithmic likelihood ratios (LLRs) of the coded bits {L(ci1)} and they deliver the extrinsic LLRs {E(ci1)} on the coded bits ci1. After reinterleaving, the extrinsic LLRs {E(Vi1)} are used as a priori LLRs at the inputs of the detector. Iterations are stopped when the messages are perfectly decoded or after a certain number of iterations, which number can be set.

The joint detector MAPD-E is shown in FIG. 7. The multi-user detector implements the following equations:




  
    
      
        
          Λ
          ⁡
          
            (
            
              v
              
                i
                ,
                k
                ,
                l
              
              1
            
            )
          
        
        =
        
        ⁢
        
          log
          ⁡
          
            (
            
              
                P
                ⁡
                
                  (
                  
                    
                      v
                      
                        i
                        ,
                        k
                        ,
                        l
                      
                      1
                    
                    =
                    
                      1
                      |
                      
                        y
                        
                          R
                          j
                        
                      
                    
                  
                  )
                
              
              
                P
                ⁡
                
                  (
                  
                    
                      v
                      
                        i
                        ,
                        k
                        ,
                        l
                      
                      1
                    
                    =
                    
                      0
                      |
                      
                        y
                        
                          R
                          j
                        
                      
                    
                  
                  )
                
              
            
            )
          
        
      
    
  
  
    
      
        ≈
        
        ⁢
        
          log
          ⁢
          
            
              
                ∑
                
                  
                    
                      a
                      ∈
                      
                        
                          χ
                          i
                        
                        :
                        
                          
                            φ
                            
                              i
                              ,
                              l
                            
                            
                              -
                              1
                            
                          
                          ⁡
                          
                            (
                            a
                            )
                          
                        
                      
                    
                    =
                    1
                  
                  ,
                  
                    b
                    ∈
                    
                      χ
                      j
                    
                  
                
              
              ⁢
              
                
                  P
                  ⁡
                  
                    (
                    
                      
                        
                          
                            Y
                            
                              R
                              j
                            
                          
                          |
                          
                            x
                            
                              i
                              ,
                              k
                            
                            1
                          
                        
                        =
                        a
                      
                      ,
                      
                        
                          x
                          
                            j
                            ,
                            k
                          
                          1
                        
                        =
                        b
                      
                    
                    )
                  
                
                ⁢
                
                  e
                  
                    
                      ξ
                      ⁡
                      
                        (
                        a
                        )
                      
                    
                    +
                    
                      ξ
                      ⁡
                      
                        (
                        b
                        )
                      
                    
                  
                
              
            
            
              
                ∑
                
                  
                    
                      a
                      ∈
                      
                        
                          χ
                          i
                        
                        :
                        
                          
                            φ
                            
                              i
                              ,
                              l
                            
                            
                              -
                              1
                            
                          
                          ⁡
                          
                            (
                            a
                            )
                          
                        
                      
                    
                    =
                    0
                  
                  ,
                  
                    b
                    ∈
                    
                      χ
                      j
                    
                  
                
              
              ⁢
              
                
                  P
                  ⁡
                  
                    (
                    
                      
                        
                          
                            Y
                            
                              R
                              j
                            
                          
                          |
                          
                            x
                            
                              i
                              ,
                              k
                            
                            1
                          
                        
                        =
                        a
                      
                      ,
                      
                        
                          x
                          
                            j
                            ,
                            k
                          
                          1
                        
                        =
                        b
                      
                    
                    )
                  
                
                ⁢
                
                  e
                  
                    
                      ξ
                      ⁡
                      
                        (
                        a
                        )
                      
                    
                    +
                    
                      ξ
                      ⁡
                      
                        (
                        b
                        )
                      
                    
                  
                
              
            
          
        
      
    
  




where (i,j)∈{1,2}2 such that i≠j and:





   
  
    {
    
      
        
          
            
              ξ
              ⁡
              
                (
                a
                )
              
            
            =
            
              
                ∑
                
                  
                    l
                    ′
                  
                  =
                  1
                
                
                  
                    log
                    2
                  
                  ⁡
                  
                    (
                    
                      
                      
                        χ
                        i
                      
                      
                    
                    )
                  
                
              
              ⁢
              
                
                  
                    φ
                    
                      i
                      ,
                      l
                    
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    a
                    )
                  
                
                ⁢
                
                  E
                  ⁡
                  
                    (
                    
                      v
                      
                        i
                        ,
                        k
                        ,
                        
                          l
                          ′
                        
                      
                      1
                    
                    )
                  
                
              
            
          
        
      
      
        
          
            
              ξ
              ⁡
              
                (
                b
                )
              
            
            =
            
              
                ∑
                
                  
                    l
                    ′
                  
                  =
                  1
                
                
                  
                    log
                    2
                  
                  ⁡
                  
                    (
                    
                      
                      
                        χ
                        j
                      
                      
                    
                    )
                  
                
              
              ⁢
              
                
                  
                    φ
                    
                      j
                      ,
                      
                        l
                        ′
                      
                    
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    b
                    )
                  
                
                ⁢
                
                  E
                  ⁡
                  
                    (
                    
                      v
                      
                        j
                        ,
                        k
                        ,
                        
                          l
                          ′
                        
                      
                      1
                    
                    )
                  
                
              
            
          
        
      
    
  




and where E(vi,k,l′1) is the extrinsic information of the bit vi,k,l′1 supplied by the decoder corresponding to the source Si, the l′th bit in the labeling corresponding to the symbol xi,k1.

The outputs from the joint detector are then described by: L(V11)=Λ(V11)−E(V11) where Λ(V11) is the log a posteriori probability ratio (LAPPR) on the interleaved bits in V11 and E(V11) is the extrinsic information from the decoder associated with the source Si of these bits.
The decoder DecSi is shown in FIG. 8. It is a decoder with soft inputs and soft outputs, e.g. of the BCJR type [2]. The equations that characterize soft information exchange at the decoder are given by:

E(ci1)=Λ(ci1)−L(ci1)

where Λ(ci1) is the LLR corresponding to the coded bits of the code word ci1, L(ci1) is the a priori information about the bits, and E(ci1), which is supplied to the detector, is the extrinsic information about these coded bits.

The error detector CRCji detects the errors so as to select only those messages that have been decoded without error. When there is systematic coding at the sources, the contents of the selected error-free messages correspond to the systematic bits of the code words detected without error.
The interleavers πji are defined in the binary field, they are identical for a given relay given that the method implements joint network-channel coding. The interleavers πji interleave the messages that have been detected without error from the source Si corresponding to the systematic bits of their respective code words, thus making it possible to create a distributed turbo code.
The binary-to-algebraic converters CBAji associate a number n=ln2(q) of bits (where q is a power of 2 equal to the cardinality of the field, ln2 is the base 2 logarithm) with an element of the field defined by the network coding. Thus, in the example of a four-element Galois field F4, the converters rely on the following bijective function:

s:{0,1}×{0,1}→F4 

which associates with two bits (b1,b2) the symbol q=s(b1,b2) of F4.

This function and its inverse gives the binary representation of an element of F4. The following notation is used below: b1=s1−1(q) and b2=s2−1(q) for q=s(b1,b2).
The network coder CRj represented in FIG. 5 by a square with a cross performs the linear combination in the field F4 of the messages from two sources as detected without error, interleaved, and converted into algebraic form. The network coding vectors of the relays R1 and R2 are respectively [1,1]T and [1,2]T. The network coding [n,m]T defined by the vectors [1,1]T and [1,2]T performs the operation n·u1+m·u2. The system formed by the independent equations u2+u1 and u1+2·u2 is invertible in F4 and thus makes it possible to retrieve the messages u1 and u2 in the event of outages on the links S1 to D and S2 to D.
The algebraic-to-binary converters transform an element of the finite field into its binary representation, they implement the function that is the inverse of s.
The shaper module MCSj performs a modulation and coding scheme, which may for example be of the bit interleaving coding and modulation (BICM) type, that corresponds to concatenating binary channel coding (defined in the binary field), a binary interleaver, and bit-to-symbol Gray coding (modulator). The binary channel coding at the relays is based for example on recursive systematic codes (RSC). The vector of the coded bits is written:




  
    c
    
      R
      j
    
  
  ∈
  
    
      F
      2
      
        n
        
          R
          j
        
      
    
    .
  




In a particular implementation, channel coding is followed by a puncturing operation Ω, which consists in the recursive systematic coder retaining only bits of determined parity. Under such circumstances, the overall efficiency is equal to




  
    
      n
      
        R
        j
      
    
    K
  
  .




The coded and interleaved sequences are written:




  
    V
    
      R
      j
    
  
  ∈
  
    
      F
      2
      
        
          Ch
          
            use
            R
          
        
        ×
        
          S
          
            R
            j
          
        
      
    
    .
  




The bit-to-symbol coding is described by





  
    
      φ
      j
      R
    
    :
    
      
        F
        2
        
          S
          
            R
            j
          
        
      
      →
      
        X
        j
        R
      
    
  
  ,




where XjR designates the constellation of symbols obtained with the order of the modulation being





  
    2
    
      S
      
        R
        j
      
    
  
  .




The signal (code word) transmitted by the relay Rj is written:




  
    x
    
      R
      j
    
  
  ∈
  
    
      C
      
        Ch
        
          use
          R
        
      
    
    .
  




When the relays have a plurality of transmit antennas, shaping may for example be of the space-time bit interleaving coding and modulation (ST-BICM) type.
In a second implementation of the invention, the space-time modulation and coding schemes at the sources and at the relays are defined in the field defined by the network coding. A particular implementation is shown in FIG. 9. In this second implementation, the modulation and coding schemes implemented at the sources and at the relays are defined directly by the field defined by the network coding, i.e. on a representation of the messages from the sources in the field. The example shown in FIG. 9 is identical to that of FIG. 5 except that the relays do not have a binary-to-algebraic converter, nor do they have an algebraic-to-binary converter, and except in that the shaper module MCSj shown corresponds to a particular implementation involving puncturing Ωj.
The modulation and coding schemes are based on a scheme of the symbol interleaved coded modulation (SICM) type and corresponds to concatenating channel coding ECcj defined in the field F4, a symbol interleaver πchRj (not binary) defined on F4, and a modulator Modj performing Gray bit-to-symbol coding operating on the binary representations of the symbols of F4. The example is described for the situation when




  
    s
    i
  
  =
  
    
      w
      i
    
    
      
        ln
        2
      
      ⁡
      
        (
        q
        )
      
    
  




is an integer. Thus, a modulated symbol from the source i carries si symbols of the field under consideration, i.e. the modulators may be considered as being bijective functions φi:F4Si→Xi.

The detection and the decoding performed by the relay take place in a manner similar to that described above for the example corresponding to the binary implementation shown in FIGS. 5 to 8. The difference comes from the fact that the information exchanged between the detector and the decoders is now in the form of vectors. The linearity of the detection and decoding operations means that it is equivalent to applying on each component of these vectors the same operations as those described for the binary implementation.
The multi-user detector implements the following equations:




  
    
      
        
          
            Λ
            q
          
          ⁡
          
            (
            
              v
              
                i
                ,
                k
                ,
                l
              
              1
            
            )
          
        
        =
        
        ⁢
        
          log
          ⁡
          
            (
            
              
                P
                ⁡
                
                  (
                  
                    
                      v
                      
                        i
                        ,
                        k
                        ,
                        l
                      
                      1
                    
                    =
                    
                      q
                      |
                      
                        y
                        
                          R
                          j
                        
                      
                    
                  
                  )
                
              
              
                P
                ⁡
                
                  (
                  
                    
                      v
                      
                        i
                        ,
                        k
                        ,
                        l
                      
                      1
                    
                    =
                    
                      0
                      |
                      
                        y
                        
                          R
                          j
                        
                      
                    
                  
                  )
                
              
            
            )
          
        
      
    
  
  
    
      
        ≈
        
        ⁢
        
          log
          ⁢
          
            
              
                ∑
                
                  
                    
                      a
                      ∈
                      
                        
                          χ
                          i
                        
                        :
                        
                          
                            φ
                            
                              i
                              ,
                              l
                            
                            
                              -
                              1
                            
                          
                          ⁡
                          
                            (
                            a
                            )
                          
                        
                      
                    
                    =
                    q
                  
                  ,
                  
                    b
                    ∈
                    
                      χ
                      j
                    
                  
                
              
              ⁢
              
                
                  P
                  ⁡
                  
                    (
                    
                      
                        
                          
                            Y
                            
                              R
                              j
                            
                          
                          |
                          
                            x
                            
                              i
                              ,
                              k
                            
                            1
                          
                        
                        =
                        a
                      
                      ,
                      
                        
                          x
                          
                            j
                            ,
                            k
                          
                          1
                        
                        =
                        b
                      
                    
                    )
                  
                
                ⁢
                
                  e
                  
                    
                      ξ
                      ⁡
                      
                        (
                        a
                        )
                      
                    
                    +
                    
                      ξ
                      ⁡
                      
                        (
                        b
                        )
                      
                    
                  
                
              
            
            
              
                ∑
                
                  
                    
                      a
                      ∈
                      
                        
                          χ
                          i
                        
                        :
                        
                          
                            φ
                            
                              i
                              ,
                              l
                            
                            
                              -
                              1
                            
                          
                          ⁡
                          
                            (
                            a
                            )
                          
                        
                      
                    
                    =
                    0
                  
                  ,
                  
                    b
                    ∈
                    
                      χ
                      j
                    
                  
                
              
              ⁢
              
                
                  P
                  ⁡
                  
                    (
                    
                      
                        
                          
                            Y
                            
                              R
                              j
                            
                          
                          |
                          
                            x
                            
                              i
                              ,
                              k
                            
                            1
                          
                        
                        =
                        a
                      
                      ,
                      
                        
                          x
                          
                            j
                            ,
                            k
                          
                          1
                        
                        =
                        b
                      
                    
                    )
                  
                
                ⁢
                
                  e
                  
                    
                      ξ
                      ⁡
                      
                        (
                        a
                        )
                      
                    
                    +
                    
                      ξ
                      ⁡
                      
                        (
                        b
                        )
                      
                    
                  
                
              
            
          
        
      
    
  




where (i,j)∈{1,2}2 such that i≠j and:





   
  
    {
    
      
        
          
            
              ξ
              ⁡
              
                (
                a
                )
              
            
            =
            
              
                ∑
                
                  
                    l
                    ′
                  
                  =
                  1
                
                
                  
                    log
                    4
                  
                  ⁡
                  
                    (
                    
                      
                      
                        χ
                        i
                      
                      
                    
                    )
                  
                
              
              ⁢
              
                
                  
                    φ
                    
                      i
                      ,
                      
                        l
                        ′
                      
                    
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    a
                    )
                  
                
                ⁢
                
                  E
                  ⁡
                  
                    (
                    
                      v
                      
                        i
                        ,
                        k
                        ,
                        
                          l
                          ′
                        
                      
                      1
                    
                    )
                  
                
              
            
          
        
      
      
        
          
            
              ξ
              ⁡
              
                (
                b
                )
              
            
            =
            
              
                ∑
                
                  
                    l
                    ′
                  
                  =
                  1
                
                
                  
                    log
                    4
                  
                  ⁡
                  
                    (
                    
                      
                      
                        χ
                        j
                      
                      
                    
                    )
                  
                
              
              ⁢
              
                
                  
                    φ
                    
                      j
                      ,
                      
                        l
                        ′
                      
                    
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    b
                    )
                  
                
                ⁢
                
                  E
                  ⁡
                  
                    (
                    
                      v
                      
                        j
                        ,
                        k
                        ,
                        
                          l
                          ′
                        
                      
                      1
                    
                    )
                  
                
              
            
          
        
      
    
  




E(vi,k,l′1) is the extrinsic information supplied by the decoder corresponding to the source Si, concerning the bit vi,k,l′1 relative to the value Φi,l′−1(b) which is the l′th bit in the labeling corresponding to the symbol xi,k1. The output from the detector is then written by: L(Vi1)=Λ(Vi1)−E(Vi1) where Λ(Vi1) is the LAPPR of the word Vi1 and E(Vi1) is the extrinsic information of this word from the decoder associated with the source Si. The decoding takes place in a manner similar to that described with reference to FIG. 8.
FIG. 10a shows a destination receiver of the invention. It essentially comprises two stages: a detection stage followed by a decoding stage. The description of the receiver is based on a particular implementation of the transmission method in which the sources transmit their systematic bits and their initial parity bits during the first stage of transmission and additional parity bits during the second stage.
The detection stage performs multi-user iterative detection to detect messages coming directly from the sources during the first stage of the protocol and messages coming from the sources and from the relays during the second stage of the protocol respectively by means of two detectors MAPD-EI and MAPD-EII. The two detectors provide soft information about the detected messages coming respectively from the sources and from the relays. The operation of the detector MAPD-EI is identical to the operation of the detector described with reference to FIG. 7.
During the second stage of the protocol, the destination receives the signals from the sources and also the signals from the relays:

yD,k(2)=h1,Dx1,k(2)+h2,Dx2,k(2)+hR1,DxR1,k+hR2,DxR2,k+nD,k(2)k∈{1, . . . , (1−α)Nuse}

where nD(2) designates additive noise with the distribution CN(0,σn2), where hi,D and hRj,D respectively designate the fading coefficients between the source i and the destination D and between the relay R and the destination D. The multi-user detector MAPD-EII shown in FIG. 10b combines as inputs:

    
    
        the extrinsic information E(cRj) on the parity bits of the relays coming from the decoders corresponding to the network coding operations at the relays; and
        the extrinsic information E(ci2) on the parity bits of the second stage of transmission from the sources coming from the channel decoders corresponding to the two sources: SISO1 and SISO2.
    
    


The equations that generate the operation of the MAPD-E are given below. The calculation of the LLRs of the lth bit vRj,k,l of the symbol received at the instant k and transmitted by the relay Rj is given by:




  
    
      
        
          
            Λ
            q
          
          ⁡
          
            (
            
              v
              
                
                  R
                  j
                
                ,
                k
                ,
                l
              
            
            )
          
        
        =
        
        ⁢
        
          log
          ⁡
          
            (
            
              
                P
                ⁡
                
                  (
                  
                    
                      v
                      
                        
                          R
                          j
                        
                        ,
                        k
                        ,
                        l
                      
                    
                    =
                    
                      1
                      |
                      
                        y
                        
                          D
                          ,
                          k
                        
                        2
                      
                    
                  
                  )
                
              
              
                P
                ⁡
                
                  (
                  
                    
                      v
                      
                        
                          R
                          j
                        
                        ,
                        k
                        ,
                        l
                      
                    
                    =
                    
                      0
                      |
                      
                        y
                        
                          D
                          k
                        
                        2
                      
                    
                  
                  )
                
              
            
            )
          
        
      
    
  
  
    
      
        ≈
        
        ⁢
        
          log
          ⁡
          
            (
            
              
                
                  ∑
                  
                    
                      c
                      ∈
                      
                        
                          χ
                          
                            R
                            j
                          
                        
                        :
                        
                          
                            φ
                            
                              R
                              j
                            
                            
                              -
                              1
                            
                          
                          ⁡
                          
                            (
                            c
                            )
                          
                        
                      
                    
                    =
                    1
                  
                
                ⁢
                
                  
                    ∑
                    
                      
                        a
                        ∈
                        
                          χ
                          1
                        
                      
                      ,
                      
                        b
                        ∈
                        
                          χ
                          2
                        
                      
                      ,
                      
                        d
                        ∈
                        
                          χ
                          
                            
                              R
                              j
                            
                            _
                          
                        
                      
                    
                  
                  ⁢
                  
                    
                      P
                      ⁡
                      
                        (
                        
                          
                            
                              
                                Y
                                
                                  D
                                  ,
                                  k
                                
                                2
                              
                              |
                              
                                x
                                
                                  1
                                  ,
                                  k
                                
                                2
                              
                            
                            =
                            a
                          
                          ,
                          
                            
                              x
                              
                                2
                                ,
                                k
                              
                              2
                            
                            =
                            b
                          
                          ,
                          
                            
                              x
                              
                                
                                  R
                                  j
                                
                                ,
                                k
                              
                            
                            =
                            c
                          
                          ,
                          
                            
                              x
                              
                                
                                  
                                    R
                                    j
                                  
                                  _
                                
                                ,
                                k
                              
                            
                            =
                            d
                          
                        
                        )
                      
                    
                    ⁢
                    
                      e
                      
                        
                          ξ
                          ⁡
                          
                            (
                            a
                            )
                          
                        
                        +
                        
                          ξ
                          ⁡
                          
                            (
                            b
                            )
                          
                        
                        +
                        
                          ξ
                          ⁡
                          
                            (
                            c
                            )
                          
                        
                        +
                        
                          ξ
                          ⁡
                          
                            (
                            d
                            )
                          
                        
                      
                    
                  
                
              
              
                
                  ∑
                  
                    
                      c
                      ∈
                      
                        
                          χ
                          
                            R
                            j
                          
                        
                        :
                        
                          
                            φ
                            
                              R
                              j
                            
                            
                              -
                              1
                            
                          
                          ⁡
                          
                            (
                            c
                            )
                          
                        
                      
                    
                    =
                    0
                  
                
                ⁢
                
                  
                    ∑
                    
                      
                        a
                        ∈
                        
                          χ
                          1
                        
                      
                      ,
                      
                        b
                        ∈
                        
                          χ
                          2
                        
                      
                      ,
                      
                        d
                        ∈
                        
                          χ
                          
                            
                              R
                              j
                            
                            _
                          
                        
                      
                    
                  
                  ⁢
                  
                    
                      P
                      ⁡
                      
                        (
                        
                          
                            
                              
                                Y
                                
                                  D
                                  ,
                                  k
                                
                                2
                              
                              |
                              
                                x
                                
                                  1
                                  ,
                                  k
                                
                                2
                              
                            
                            =
                            a
                          
                          ,
                          
                            
                              x
                              
                                2
                                ,
                                k
                              
                              2
                            
                            =
                            b
                          
                          ,
                          
                            
                              x
                              
                                
                                  R
                                  j
                                
                                ,
                                k
                              
                            
                            =
                            c
                          
                          ,
                          
                            
                              x
                              
                                
                                  
                                    R
                                    j
                                  
                                  _
                                
                                ,
                                k
                              
                            
                            =
                            d
                          
                        
                        )
                      
                    
                    ⁢
                    
                      e
                      
                        
                          ξ
                          ⁡
                          
                            (
                            a
                            )
                          
                        
                        +
                        
                          ξ
                          ⁡
                          
                            (
                            b
                            )
                          
                        
                        +
                        
                          ξ
                          ⁡
                          
                            (
                            c
                            )
                          
                        
                        +
                        
                          ξ
                          ⁡
                          
                            (
                            d
                            )
                          
                        
                      
                    
                  
                
              
            
            )
          
        
      
    
  




where j∈{1,2}, where Rj designates the relay other than Rj, where:





   
  
    {
    
      
        
          
            
              ξ
              ⁡
              
                (
                a
                )
              
            
            =
            
              
                ∑
                
                  
                    l
                    ′
                  
                  =
                  1
                
                
                  
                    log
                    2
                  
                  ⁡
                  
                    (
                    
                      
                      
                        χ
                        1
                      
                      
                    
                    )
                  
                
              
              ⁢
              
                
                  
                    φ
                    
                      1
                      ,
                      
                        l
                        ′
                      
                    
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    a
                    )
                  
                
                ⁢
                
                  E
                  ⁡
                  
                    (
                    
                      v
                      
                        i
                        ,
                        k
                        ,
                        
                          l
                          ′
                        
                      
                      2
                    
                    )
                  
                
              
            
          
        
      
      
        
          
            
              ξ
              ⁡
              
                (
                b
                )
              
            
            =
            
              
                ∑
                
                  
                    l
                    ′
                  
                  =
                  1
                
                
                  
                    log
                    2
                  
                  ⁡
                  
                    (
                    
                      
                      
                        χ
                        2
                      
                      
                    
                    )
                  
                
              
              ⁢
              
                
                  
                    φ
                    
                      2
                      ,
                      
                        l
                        ′
                      
                    
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    b
                    )
                  
                
                ⁢
                
                  E
                  ⁡
                  
                    (
                    
                      v
                      
                        2
                        ,
                        k
                        ,
                        
                          l
                          ′
                        
                      
                      2
                    
                    )
                  
                
              
            
          
        
      
      
        
          
            
              ξ
              ⁡
              
                (
                d
                )
              
            
            =
            
              
                ∑
                
                  
                    l
                    ′
                  
                  =
                  1
                
                
                  
                    log
                    2
                  
                  (
                  
                    
                    
                      χ
                      
                        
                          R
                          j
                        
                        _
                      
                    
                    
                  
                  )
                
              
              ⁢
              
                
                  
                    φ
                    
                      
                        
                          R
                          j
                        
                        _
                      
                      ⁢
                      
                        l
                        ′
                      
                    
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    d
                    )
                  
                
                ⁢
                
                  E
                  (
                  
                    v
                    
                      
                        
                          R
                          j
                        
                        _
                      
                      ,
                      k
                      ,
                      
                        l
                        ′
                      
                    
                  
                  )
                
              
            
          
        
      
    
  




and where E(vRj,k,l′) is the extrinsic information supplied by the decoder corresponding to the relaying function of the relay Rj of the bit vRj,k,l′, the l′th bit in the labeling corresponding to the symbol xRj,k. These equations are valid only in the presence of the channel interleavers πchUi where Ui is a source or a relay.

The LLRs corresponding to the second stage of transmission from the sources are given in a manner that is symmetrical relative to the LLRs from the relays. At the output from the detector MAPD, the method calculates the extrinsic information on the parity bits of the second stage of transmission from the sources and also on the parity bits from the relays using the following relationships:

L(Vi2)=Λ(Vi2)−E(Vi2) and L(VRj)=Λ(VRj)−E(VRj) where i=1,2

designates the sources and where j=1,2 designates the relays.

The decoding stage serves to decode messages respectively from the sources and from the relays on the basis of soft information taken a priori and coming from the detection stage. The decoding is performed by means of as many soft decoders SISO (soft input soft output) as there are sources and as many algebraic decoders SISO algj as there are algebraic network coders, and thus as there are relays. The decoders SISO1, SISO2, and the decoders SISO Alg1, SISO Alg2 are based on the codes implemented respectively in the sources and in the relays.
The soft decoders associated with the sources operate in totally identical manner with one another. Their operation is similar to that of the decoder described with reference to FIG. 8. FIG. 10 shows a demultiplexer between the output of the detector MAPD-EI and each of the soft decoders SISO1, SISO2, and it enables the systematic portion to be distinguished from the parity portion of the code, whereas in FIG. 8 the single input of the decoder implicitly includes both portions. Compared with the decoder of FIG. 8, a difference comes from taking account of the parity information supplied by the algebraic decoders associated with the relays. Furthermore, each decoder SISOi receives the a priori information on the systematic bits and the initial parity bits of the detector MAPD-EI, whereas it receives the a priori information on the second series of parity bits from the second detector MAPD-EII.
The decoders provide soft information about the decoded symbols to the detectors. An iterative exchange of soft information takes place between the decoders associated with the sources and the algebraic decoders associated with the relays, thereby giving rise to iterative joint network channel decoding.
The LLRs of the systematic bits and of the parity bits corresponding to the sequence transmitted by the source i during the first stage are written LSi and Lpi1. The LLRs of the parity bits corresponding to the sequence transmitted by the source i during the second stage are written Lpi2. Let LSiRj be the LLRs supplied by the relay Rj for the systematic bits from the source Si. The extrinsic information corresponding to the preceding LLRs is written ESi, Epi1, Epi2, ESiRj.
The decoder SISO Algj is a decoder having soft inputs and outputs that incorporate a logic (algebraic) operation corresponding to the linear transform of the network coding of the relay Rj under consideration.
FIG. 11 is a diagram of an embodiment of the SISO decoder Algj when all of the transmissions are performed in the field F4, i.e. in the second implementation shown in FIG. 9 where the channel coding is of the algebraic type. In the example shown, the network coding corresponds to the relay Rj=R2 which performs the linear combination uR=u1+2·u2. The messages from the sources u1 and u2 represented in F4 are detected without error at the relays, and thus uR=u1+2·u2 is included in the parity bits transmitted by the relay R2. The decoder with soft inputs and outputs SISO Alg2 corresponding to the relay under consideration receives as input a priori information about the parity symbols (because of the puncturing, only the parity bits are transmitted by the relays) from the relay LpR together with a priori information about the symbols from the two sources u1 and u2 (included in the systematic portions of the code words from the sources) which are E′S1=ΠES1+ΠLS1 and E′S2=ΠES2+ΠLS2. This a priori information E′S1 and E′S2 about the symbols from the two sources is used to calculate a priori information about the systematic symbols at the input of the channel coding of the relay by using the relationship modeled by the operator 1,2Σ in FIG. 11:

E′SR,k=Σ1,2,k(E′s1,E′S2) where k∈F4={0,1,2,3}

representing the relationship uR=u1+2·u2. Let E′SR be the set {E′SR,k:k=0, 1, 2, 3, 4}. From the (four component) vector E′SR and LpR the decoder outputs the extrinsic information for the parity symbols EpR2 from the relay R2 under consideration and for the systematic symbols from both sources: ESiR2 which are associated by the following relationships modeled by the operators 1,2Σ and 3,3Σ in FIG. 11:

ES1R2=(Σ1,2,k(ESR,E′S2))k={0,1,2,3} representing u1=uR+2·u2 and

ES2R2=(Σ3,3,k(ESR,E′S1))k={0,1,2,3} representing u2=3·uR+3·u1.

FIG. 12 is a diagram of an embodiment of the SISO decoder Algj for binary channel coding, i.e. as in the first embodiment shown in FIG. 5. Operation is on the same principle as that of the SISO decoder Algj shown in FIG. 11 corresponding to algebraic transmission and described above. The difference comes from adding binary-to-algebraic converters CBAs (bit to symbol) at the input of the operators Σ and algebraic-to-binary converters CABs (symbol to bit) at the output from the operators 1,2Σ, 2,1Σ, and 3,3Σ. The binary-to-algebraic converters act on the extrinsic information from the sources in order to retain channel decoding at binary level. The LLRs and the extrinsic information are in the binary domain. Let u=s(u1, u2) be an element of F4, let q∈F4, and let




  
    
      Λ
      q
    
    ⁡
    
      (
      u
      )
    
  
  =
  
    log
    ⁡
    
      (
      
        
          P
          ⁡
          
            (
            
              u
              =
              q
            
            )
          
        
        
          P
          ⁡
          
            (
            
              u
              =
              0
            
            )
          
        
      
      )
    
  




be the LLR of u corresponding to the value q. The bit-to-symbol converters CBAs perform the operation that consists in determining the LLR of the symbol u knowing the LLRs of the bits (u1)i∈{1,2}:

∀q∈F4, Λq(u)=Σi∈{1,2}si−1(q)Λ(ui) where





  
    Λ
    ⁡
    
      (
      
        u
        i
      
      )
    
  
  =
  
    log
    ⁡
    
      (
      
        
          P
          ⁡
          
            (
            
              
                u
                i
              
              =
              1
            
            )
          
        
        
          P
          ⁡
          
            (
            
              
                u
                i
              
              =
              0
            
            )
          
        
      
      )
    
  




At the output from the operators 1,2Σ, 2,1Σ, and 3,3Σ, the symbol-to-bit converters CABs perform the operation that consists in determining the two LLRs associated with each of the bits of the symbol u:




  
    
      Λ
      ⁡
      
        (
        
          u
          i
        
        )
      
    
    =
    
      log
      (
      
        
          
            ∑
            
              
                q
                ∈
                
                  F
                  4
                
              
              ,
              
                
                  
                    s
                    i
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    q
                    )
                  
                
                =
                1
              
            
          
          ⁢
          
            e
            
              (
              
                
                  Λ
                  q
                
                ⁡
                
                  (
                  u
                  )
                
              
              )
            
          
        
        
          
            ∑
            
              
                q
                ∈
                
                  F
                  4
                
              
              ,
              
                
                  
                    s
                    i
                    
                      -
                      1
                    
                  
                  ⁡
                  
                    (
                    q
                    )
                  
                
                =
                0
              
            
          
          ⁢
          
            e
            
              (
              
                
                  Λ
                  q
                
                ⁡
                
                  (
                  u
                  )
                
              
              )
            
          
        
      
      )
    
  
  ,
  
    i
    ∈
    
      {
      
        1
        ,
        2
      
      }
    
  




The SISO decoder Algj shown corresponds to a relay that transmits only the parity bits and that punctures the systematic bits.
The BCJR decoder of FIG. 12, like that of FIG. 11, operates on the two-element finite field like the associated channel coding. Only the binary-to-algebraic and algebraic-to-binary converters and the operators Σ operate in the field F4.
The basic arrangement of a receiver of the invention is described below for the special case corresponding to an embodiment of relays in which the systematic bits are punctured at the relays.
1/ The detector MAPD-EI receives as input the multiplexed extrinsic information of the systematic and parity bits respectively from the two sources. Thus, it receives E1=[ES1+Π1−1ES1R1+Π2−1ES1R2, Ep11] and E2[ES2+Π1−1ES2R1+Π2−1ES2R2, Ep21]. As output it supplies the LLRs of each of the bit sequences received from the two sources [Ls1,Lp11] and [Ls2,Lp21].
2/ The detector MAPD-EII receives as input the extrinsic information on the parity bits from the two relays EpR1 and EpR2 together with the extrinsic information on the parity bits for the second stage of transmission from the two sources Ep12 and Ep22. It outputs the LLRs of these sequences LpR1, LpR2, Lp12 and Lp22.
3/ The decoders SISO1 and SISO2 receive as input the LLRs of the parity bits relating to the first stage and to the second stage of transmission from the two sources coming respectively from the detector MAPD-EI and from the detector MAPD-EII, together with the LLRs of the systematic bits from the detector MAPD-EI and the extrinsic information about the respective systematic bits from the algebraic decoders SISO Alg1 and SISO Alg2. This extrinsic information constitutes a priori information about the systematic bits from the two sources. Thus, SISO1 receives Lp11 and Ls1 from the detector MAPD-EI and Lp12 from the detector MAPD-EII and as a priori information about the systematic bits it receives: Π1−1ES1R1+Π2−1ES1R2 from the algebraic decoders. It calculates the LLRs: ΛS1 and Λp1, and from them together with Ls1, Lp11, and Lp12 it deduces the extrinsic information Es1, Ep11, and Ep12 that it delivers as output. SISO2 is symmetrical with SISO1.
4/ The SISO Alg1 is then activated. As input it receives the extrinsic information about the systematic bits from the sources S1 and S2 supplied by the two channel decoders SISO1 and SISO2 together with the extrinsic information calculated at the preceding iteration by the decoder SISO Alg2: Π1(ES1+ΠΠ2−1·Es1R2) and Π1(ES2+Π2−1·Es2R2). It also receives as input the a priori information about the systematic bits generated by the multi-user detector MAPD-EI: Π1·LS1 and Π1·LS2. It also receives as input the LLRs LpR1 of the parity bits coming from the first relay R1 supplied by the detector MAPD-EII. The decoder outputs the extrinsic information EpR1 about the parity bits from the relay R1 together with the extrinsic information about the systematic bits from the sources S1 and S2:Es1R1 and Es2R1. The decoders SISO Alg2 and SISO Alg1 are symmetrical in their operation, but each of them contains a decoder that is specific to their respective algebraic operations. The provision of the extrinsic information EpR2 about the parity bits of the relay R2 and also the extrinsic information Es1R2 and Es2R2 about the systematic bits from the sources S1 and S2 by the decoder SISO Alg2 terminates the first iteration.
The return to detection step 1/ marks the beginning of the following iteration.
At the end of the iterative process, the method takes from the outputs of the decoders and of the detectors, firstly Ls1+Es1+Π1−1ES1R1+Π2−1ES1R20 in order to proceed with taking a decision about û1, and secondly Ls2+Es2+Π1−1ES2R1+Π2−1ES2R20 in order to proceed with taking a decision about û2. The sign  means that if the output is positive then the decision is that û1 or û2 is one, and if the output is negative then the decision is that û1 or û2 is zero.
The following examples serve to illustrate how the destination receiver uses the information transmitted in-band by the relays. This information specifies which messages have been detected without error by the relays. On the basis of this information, the receiver disconnects or does not disconnect an algebraic decoder of a SISO decoder associated with a source, or it deactivates an algebraic decoder.
In the first example shown in FIG. 13: one of the two relays, the relay R2 sends only of the source signals, the signal u2. Under such circumstances, the algebraic SISO decoder SISO alg2 corresponding to the relay R2 is disconnected from the SISO decoder SISO1 of the non-coded source S1.
A second situation is shown in FIG. 14: each relay R1, R2 sends only one source signal. The SISOi is then disconnected from the decoder SISO Algj where i is the index of the source Si that is not coded by the relay Rj.
A third situation is shown in FIG. 15: one of the two relays, the relay R1, does not send any source signal. Under such circumstances, the algebraic SISO decoder SISO alg1 corresponding to the relay R1 is deactivated.
APPENDIX A
A.1 Field F4 
The primitive polynomial at the origin of the elements of this field is X2+X+1. Let α and α2 be the two roots of this polynomial, and use the notations 0 and 1 respectively for the neutral elements respectively of addition and multiplication for this field. Decimal notation is used for these elements: {0, 1, 2, 3} where 2 and 3 represent α and α2, respectively.
















TABLE 1





(+)
0
1
2
3
(×)
0
1
2
3







0
0
1
2
3
0
0
0
0
0


1
1
0
3
2
1
0
1
2
3


2
2
3
0
1
2
0
2
3
1


3
3
2
1
0
3
0
3
1
2









a) Addition table for F4 b) Multiplication table for F4 

Let x1, x2, and y be three elements of F4 such that: x1+2·x2=y. The transformations that enable x1 and x2 to be determined are given by:




   
  
    {
    
      
        
          
            
              x
              1
            
            =
            
              y
              +
              
                2
                ·
                
                  x
                  2
                
              
            
          
        
      
      
        
          
            
              x
              2
            
            =
            
              
                3
                ·
                y
              
              +
              
                3
                ·
                
                  x
                  1
                
              
            
          
        
      
    
  




The notation Sn,m,i is used for the set of pairs (k,l) of F4 that are solutions to the equation given by n·k+m·l=i. Thus:

Sn,m,i={(k,l)∈(F4)2, n·k+m·l=i}

The notation Σn,m,i is used for the function defined by:




  
    
      
                4
      
      ×
      
                4
      
    
    →
      




  
    
      (
      
        x
        ,
        y
      
      )
    
    →
    
      Log
      (
      
        
          
            ∑
            
              
                (
                
                  k
                  ,
                  l
                
                )
              
              ∈
              
                S
                
                  n
                  ,
                  m
                  ,
                  i
                
              
            
          
          ⁢
          
            Exp
            ⁡
            
              (
              
                
                  x
                  k
                
                +
                
                  y
                  l
                
              
              )
            
          
        
        
          
            ∑
            
              
                (
                
                  k
                  ,
                  l
                
                )
              
              ∈
              
                S
                
                  n
                  ,
                  m
                  ,
                  o
                
              
            
          
          ⁢
          
            Exp
            ⁡
            
              (
              
                
                  x
                  k
                
                +
                
                  y
                  l
                
              
              )
            
          
        
      
      )
    
  



A.2 Algebraic Magnitudes

A.2.1. LLR

LLR is the logarithm of the likelihood ratio or probability ratio relating to two symbols.
In the binary version, a bit u may be 1 or 0. Such a ratio is given by a scalar:




  LLR
  =
  
    log
    ⁡
    
      (
      
        
          P
          ⁡
          
            (
            
              u
              =
              1
            
            )
          
        
        
          P
          ⁡
          
            (
            
              u
              =
              0
            
            )
          
        
      
      )
    
  




and its sign defines in unique manner the hard decision about the bit u.

In the algebraic version, e.g. in F4, a symbol u may have four different values. A scalar LLR cannot designate the symbol u in unique manner. We therefore introduce a vector LLR of size four defined as follows:




  
    ∀
    
      q
      ∈
      
        F
        4
      
    
  
  ,
  
    
      
        LLR
        q
      
      ⁡
      
        (
        u
        )
      
    
    =
    
      log
      ⁡
      
        (
        
          
            P
            ⁡
            
              (
              
                u
                =
                q
              
              )
            
          
          
            P
            ⁡
            
              (
              
                u
                =
                0
              
              )
            
          
        
        )
      
    
  




The first component is zero since u=0 is considered to be the reference event relative to which the likelihoods of the other events are calculated.
A.2.2. LAPPR
The log a posteriori probability ratio (LAPPR) is a form of LLR that is “conditional” on “side information” that is typically provided by a received sequence.
In the binary version, LAPPR is defined by:




  LAPPR
  =
  
    log
    ⁡
    
      (
      
        
          P
          ⁡
          
            (
            
              u
              =
              
                1
                |
                y
              
            
            )
          
        
        
          P
          ⁡
          
            (
            
              u
              =
              
                0
                |
                y
              
            
            )
          
        
      
      )
    
  




in the algebraic version, e.g. in F4, use is made of a vector LAPPR of size four defined as follows:




  
    ∀
    
      q
      ∈
      
        F
        4
      
    
  
  ,
  
    
      
        LAPPR
        q
      
      ⁡
      
        (
        u
        )
      
    
    =
    
      log
      ⁡
      
        (
        
          
            P
            ⁡
            
              (
              
                u
                =
                
                  q
                  |
                  y
                
              
              )
            
          
          
            P
            ⁡
            
              (
              
                u
                =
                
                  0
                  |
                  y
                
              
              )
            
          
        
        )
      
    
  




    [1] M. Xiao, M. Skoglund, “Design of Network Codes for Multiple Users Multiple Relays Wireless Networks”, IEEE International Symposium on Information Theory, 2009.
    [2] L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal Decoding of Linear Codes for minimizing symbol error rate”, IEEE Transactions on Information Theory, vol. IT 20(2), pp. 284-287, March 1974

## Claims

1. A method of non-orthogonal transmission of a signal, for use in a system having N sources, M relays, and a single receiver, wherein non-coordinated simultaneous transmission over a common spectrum resource by each of the M relays takes place simultaneously with simultaneous transmission over the same spectrum resource by the sources, N≧2, M≧2, the method comprising for each of the M relays Rj, 1≦j≦M:
iterative joint multi-user detection and decoding of coded source messages transmitted respectively by the sources during αN first transmission intervals to obtain decoded source messages;
detecting errors in the decoded source messages;
interleaving only the decoded source messages that are detected without error, followed by algebraic network coding including a linear combination in a finite field of order strictly greater than two of the interleaved decoded source messages to obtain a relay message, the linear combinations being independent in pairs between the relays of the system; and
shaping comprising channel coding the relay message to obtain the signal representative of the relay message and to transmit this signal during the following (1−α)N transmission intervals simultaneously with transmission from the sources, where α∈]0,1[.

2. A method according to claim 1, further including shaping a control signal identifying the decoded source messages involved in the algebraic network coding of the relay message.

3. A method according to claim 1, wherein the channel coding is systematic.

4. A method according to claim 1, wherein the channel coding is binary, and further comprising:
binary-to-symbol conversion between the interleaving step and the algebraic coding step; and
symbol-to-binary conversion after the algebraic network coding step.

5. A method according to claim 1, wherein the finite field of order strictly greater than two is a Galois field of order four.

6. A method according to claim 1, wherein detecting errors is performed using redundancy information of a cyclic type associated with the coded messages transmitted by the sources.

7. A method according to claim 1, wherein the iterative joint detection and decoding jointly performs multi-user detection and soft input and soft output decoding.

8. A method according to claim 1, wherein the iterative joint detection and decoding implement space-time decoding.

9. A method according to claim 1, wherein the shaping further comprises interleaving and modulation, interleaving being between channel coding and modulation, to obtain the signal representative of the relay message.

10. A method according to claim 1, wherein the algebraic network coding by the M relays is represented by a systematic generator matrix T=[ING] with IN being an identity matrix of dimension N and with G being a matrix of M network coding vectors aj=[a1,j a2,j . . . aN,j]T, wherein the components of the network coding vectors are determined by independent random drawing in such a manner that maximum diversity of the system is reached.

11. A method of non-orthogonal transmission of a signal, for use in a system having N sources, M relays, and a single receiver, wherein non-coordinated simultaneous transmission over a common spectrum resource by each of the M relays takes place simultaneously with simultaneous transmission over the same spectrum resource by the sources, N≧2, M≧2, the method comprising for each of the M relays Rj, 1≦j≦M:
iterative joint multi-user detection and decoding of coded source messages transmitted respectively by the sources during αN first transmission intervals to obtain decoded source messages;
detecting errors in the decoded source messages;
interleaving only the decoded source messages that are detected without error, followed by algebraic network coding including a linear combination in a finite field of order strictly greater than two of the interleaved decoded source messages to obtain a relay message, the linear combinations being independent in pairs between the relays of the system; and
shaping comprising channel coding the relay message to obtain the signal representative of the relay message and to transmit this signal during the following (1−α)N transmission intervals simultaneously with transmission from the sources, where α∈]0,1[,
wherein the N sources transmit the coded source messages simultaneously over a common spectrum resource, each of which coded source messages comprises a systematic portion and a first redundancy portion during the αN first transmission intervals, and the N sources transmit second redundancy portions simultaneously over the same spectrum resource during the following (1−α)N transmission intervals while the relays are simultaneously transmitting third redundancy portions.

12. A non-transitory data medium including program instructions stored thereon and adapted to implement a method of non-orthogonal transmission of a signal, when said program is loaded in and executed by a relay for a system having N sources, M relays, and a single receiver, wherein non-coordinated simultaneous transmission over a common spectrum resource by each of the M relays takes place simultaneously with simultaneous transmission over the same spectrum resource by the sources, the method comprising for each of the M relays Rj, 1≦j≦M, N≧2, M≧2:
iterative joint multi-user detection and decoding of coded source messages transmitted respectively by the sources during αN first transmission intervals to obtain decoded source messages;
detecting errors in the decoded source messages;
interleaving only the decoded source messages that are detected without error, followed by algebraic network coding including a linear combination in a finite field of order strictly greater than two of the interleaved decoded source messages to obtain a relay message, the linear combinations being independent in pairs between the relays of the system; and
shaping comprising channel coding the relay message to obtain the signal representative of the relay message and to transmit this signal during the following (1−α)N transmission intervals simultaneously with transmission from the sources, where α∈]0,1[.

13. A relay Rj, j∈{1, . . . , M} for a non-orthogonal system having N sources, M relays Rj, 1≦j≦M, N≧2, M≧2, and a single receiver for implementing a method of non-orthogonal transmission of a signal, wherein non-coordinated simultaneous transmission over a common spectrum resource by each of the M relays takes place simultaneously with simultaneous transmission over the same spectrum resource by the sources, the relay Rj comprising:
means for iterative joint multi-user detection and decoding coded source messages transmitted respectively by the sources during αN first transmission intervals to obtain decoded source messages;
means for detecting errors in the decoded source messages;
interleaving means for interleaving only those decoded source messages that are detected without error;
means for algebraic network coding including a linear combination of the interleaved decoded source messages in a finite field of order strictly greater than two to obtain a relay message, the linear combinations being independent between the relay and each one of the other relays of the system; and
means for shaping, comprising channel coding means for channel coding the relay message to obtain the signal representative of the relay message and to transmit this signal during the following (1−α)N transmission intervals simultaneously with transmission by the sources, with α∈]0,1[.

14. A system having the N sources, the M relays, and the single non-orthogonal receiver, wherein the relays are relays according to claim 13.

15. A reception method for a receiver of a non-orthogonal system having N sources and M relays, N≧2, M≧2, the system being for implementing a method of non-orthogonal transmission of a signal, wherein non-coordinated simultaneous transmission over a common spectrum resource by the M relays takes place simultaneously with simultaneous transmission over the same spectrum resource by the N sources, the reception method comprising in iterative manner a joint channel and network decoding:
a first multi-user detection for detecting N coded source messages transmitted simultaneously by the respective N sources to obtain intrinsic soft information about the respective N coded source messages;
a second multi-user detection for detecting N source coded messages and M relay messages transmitted simultaneously respectively by the N sources and by the M relays to obtain intrinsic soft information about the respective N coded source messages and about the respective M relays messages which were obtained at the relays by algebraic network coding decoded source messages detected without error by the relays;
N soft channel decoding, in parallel, the N coded source messages; and
M soft algebraic network decoding in cascade the M relay messages under the control of information received from the relays identifying the decoded source messages involved in the algebraic network coding at the relays;
wherein the N soft channel decoding the N coded source messages uses as first a priori information the intrinsic soft information coming from the first multi-user detection and the intrinsic soft information relating to the coded source messages coming from the second multi-user detection in order to provide extrinsic soft information about the decoded source messages involved in the M relay messages decoded in the M soft algebraic network decoding;
wherein the M soft algebraic network decoding the M relay messages uses as second a priori information the intrinsic soft information coming from the first and second multi-user detection and provides extrinsic soft information about the decoded relay messages to the second multi-user detection;
wherein the N soft channel decoding the N coded source messages and the M soft algebraic network decoding the M relay messages supplying each other mutually with the extrinsic soft information they provide, this mutual supply being under the control of information coming from the M relays identifying the decoded source messages involved in the algebraic network coding at the relays.

16. A receiver for a non-orthogonal system having N sources and M relays, N≧2, M≧2, the system being for implementing a method of non-orthogonal transmission of a signal, wherein non-coordinated simultaneous transmission over a common spectrum resource by the M relays takes place simultaneously with simultaneous transmission over the same spectrum resource by the N sources, and the receiver comprising:
first multi-user detection means for multi-user joint detection for detecting N coded source messages coming respectively from the N sources during a first stage of transmission and to generate intrinsic soft information about the N coded source messages;
second multi-user detection means for multi-user joint detection for detecting N coded source messages coming respectively from the N sources and M relays messages coming respectively from the M relays during a second stage of transmission and to obtain intrinsic soft information about the respective N coded source messages and about the respective M relays messages which were obtained at the relays by algebraic network coding decoded source messages detected without error by the relays;
N soft decoders in parallel for soft decoding the N coded source messages coming respectively from the N sources while using as first a priori information the intrinsic soft information coming from the first multi-user detection means and the intrinsic soft information about the N coded source messages coming from the second multi-user detection means and to provide extrinsic soft information about the decoded source messages involved in M decoded relays messages decoded by M soft algebraic network decoders in cascade;
the M soft algebraic network decoders operating in cascade for soft decoding the M relay messages while using as second a priori information the intrinsic soft information coming from the first and second multi-user detection means and provide extrinsic soft information about the decoded relay messages to the second multi-user detection means;
wherein the N soft channel decoders and the M soft algebraic network decoders supplying each other mutually with the extrinsic soft information they provide, this mutual supply being under the control of information coming from the M relays identifying the decoded source messages involved in the algebraic network coding at the relays; and
decision-taking means for the N soft channel decoders to obtain after some iterations of the mutual supply with the M soft algebraic network decoders an estimate of the source messages.