Christine Guillemot

A Roumy

Toward constructive Slepian-Wolf coding schemes

come

Toward constructive Slepian-Wolf coding schemes

Introduction

This chapter deals with practical solutions for the Slepian Wolf (SW) coding problem, which refers to the problem of lossless compression of correlated sources with coders which do not communicate. Here, we will consider the case of two binary correlated sources X and Y , characterized by their joint distribution. If the two coders communicate, it is well known from Shannon's theory that the minimum lossless rate for X and Y is given by the joint entropy H(X, Y ). Slepian and Wolf established in 1973 [START_REF] Slepian | Noiseless Coding of Correlated Information Sources[END_REF] that this lossless compression rate bound can be approached with a vanishing error probability for infinitely long sequences, even if the two sources are coded separately, provided that they are decoded jointly and that their correlation is known to both the encoder and the decoder. Hence, the challenge is to construct a set of encoders which do not communicate and a joint decoder which can achieve the theoretical limit.

This chapter gives an overview of constructive solutions both for the asymmetric and the non asymmetric SW coding problems. Asymmetric SW coding refers to the case where one source, for example Y , is transmitted at its entropy rate and used as side information to decode the second source X. Non asymmetric SW coding refers to the case where both sources are compressed at a rate lower than their respective entropy rates. Sections 2 and 3 recall the principles and then describe practical schemes for asymmetric and symmetric coding respectively. Practical solutions for which the compression rate is a priori fixed according to the correlation between the two sources are first described. In this case, the correlation between the two sources needs to be known -or estimated -at the transmitter. Rate-adaptive schemes in which the SW code is incremental are then presented. This chapter ends with Section 4 covering various advanced SW coding topics such as the design of schemes based on source codes and the generalization to the case of non-binary sources, and to the case of M sources.

1

H(X) H(X, Y ) R X H(Y |X) H(Y ) H(X, Y ) R Y B A H(X, Y ) 2 C H(X, Y ) 2
H(X|Y ) (b)
Figure 1: Distributed source coding of statistically dependent i.i.d. discrete random sequences X and Y . Set-up (left); achievable rate region (right).

Principle of asymmetric SW coding 2.1.1 The syndrome approach

Because of the random code generation in the SW theorem, the SW proof is non-constructive. However, some details in the proof do give insights on how to construct SW bound achieving codes. More precisely, the proof relies on binning -that is a partition of the space of the source sequences into subsets (or bins) such that the vectors in the bins are as far apart (or as much "jointly non-typical") as possible (see Figure 2). In 1974 [START_REF] Wyner | Recent results in the Shannon theory[END_REF], Wyner suggested to construct the bins as cosets of a binary linear code and showed the optimality of this construction. More precisely, if the linear block code achieves the capacity of the binary symmetric channel (BSC) that models the correlation between the two sources, then this capacity achieving channel code can be turned into a SW achieving source code. The partition of the sequences x into four subsets (called bins) such that the sequences in each bin are as far apart as possible. The set of sequences x jointly typical with a given y are as "different" as possible: here they are elements of different bins.

In order to present Wyner's algebraic binning scheme, we first review some notations on binary linear codes. A binary (n, k) code C is defined by an (n -k) × n parity-check matrix H, and contains all the n-length vectors1 x s. t. xH T = 0:

C = x : xH T = 0 .
Notice that the code C is equivalently defined by a k × n generator matrix G such that C = {x : x = uG}, where u is a k-bit vector.

If H has full row rank, then the rate of the channel code is k/n. Moreover, for a good code, all the vectors of the code (called words or codewords) have maximum Hamming distance. The code partitions the space containing 2 n sequences into 2 n-k cosets of 2 k words with maximum Hamming distance. Each coset is indexed by an (n -k)-length syndrome, defined as s = xH T . In other words, all sequences in a coset share the same syndrome: C s = x : xH T = s . Moreover, as a consequence of the linearity of the code, a coset results from the translation of the code by any representative of the coset:

∀v ∈ C s , C s = C ⊕ v. (1)
A geometric approach to binary coding visualizes binary sequences of length n as vertices of an n-dimensional cube. In Figure 3, the code C (the set of codewords or the set of vectors of syndrome 0 that is represented with •) is a subspace of {0, 1} 3 , whereas the coset with syndrome 1, denoted C 1 and represented with •, is an affine subspace parallel to C. Notice that properties of a subspace and the linearity property (1) are satisfied (to verify this, all operations have to be performed over the finite field of order 2). If a codeword x is sent over a BSC with cross-over probability p and error sequence z, the received sequence is y = x + z. Maximum likelihood (ML) decoding over the BSC, searches for the closest codeword to y with respect to the Hamming distance d H (., .):

x = arg min x:x∈C d H (x, y).
This can be implemented with syndrome decoding. This decoding relies on a function f : {0, 1} n-k → {0, 1} n , that computes for each syndrome a representative called the coset leader that has minimum Hamming weight. Thus, a syndrome decoder first computes the syndrome of the received sequence: s = yH T , then the coset leader f (s). This coset leader is the ML estimate of the error pattern z. Finally, the ML estimate of x is given by x = y ⊕ f (yH T ).

In order to use such a code for the asymmetric SW problem, [START_REF] Wyner | Recent results in the Shannon theory[END_REF] suggests to construct bins as cosets of a capacity-achieving parity-check code. Let x and y be two correlated binary sequences of length n. These sequences are the realizations of the sources X and Y . The encoder computes and transmits the syndrome of x: s = xH T . The sequence x of n input bits is thus mapped into its corresponding (n -k) syndrome bits, leading to a compression ratio of n : (n -k). The decoder, given the correlation between the sources X and Y and the received coset index s, searches for the sequence in the coset that is closest to y. In other words, ML decoding is performed in order to retrieve the original sequence x:

x = arg min

x:x∈Cs d H (x, y). (2)
Note that the maximization is performed in a set of vectors with syndrome that may not be 0. Therefore, the classical ML channel decoder has to be adapted in order to be able to enumerate all vectors in a given coset C s . This adaptation is straightforward if syndrome decoding is performed. In this case, the decoder can first retrieve the error pattern (since for each syndrome, the corresponding coset leader is stored) and add it to the SI y. Syndrome decoding is used here as a mental representation rather than an efficient decoding algorithm, since it has complexity O(n2 n-k ). There exists codes with linear decoding complexity and we will detail these constructions in Section 2.2. In this section, we have presented a structured binning scheme for the lossless source coding problem with SI at the decoder. However, the principle is quite general and can be applied to a large variety of problems as shown in [START_REF] Zamir | Nested linear/lattice codes for structured multiterminal binning[END_REF].

x p x Decoder Encoder

y x G arg min (x xp):(x xp)∈C ′ d H ((x x p ), (y x p )) x (b)
Figure 4: Asymmetric SW coding. The syndrome approach (left); the parity approach (right).

The parity approach

The above detailed syndrome approach is optimal [START_REF] Wyner | Recent results in the Shannon theory[END_REF], however it may be difficult to construct rate-adaptive codes by puncturing the syndrome. Therefore, another approach called parity approach has been proposed [START_REF] Garcia-Frias | Compression of correlated binary sources using turbo codes[END_REF] 2 , [START_REF] Aaron | Compression with side information using turbo codes[END_REF].

Let C ′ be an (n, 2n -k) systematic binary linear code, defined by its (2n -k) × n generator matrix G = (I P ):

C ′ = {xG = (x x p ) : x ∈ {0, 1} n }.
The compression of the source X is achieved by transmitting only the parity bits x p of the source sequence x (see Figure 4). The systematic bits x are not transmitted. This leads to a compression ratio n : (n -k). Here again, the correlation between the source X and the SI Y is modeled as a "virtual" channel, where the pair (y x p ) is regarded as a noisy version of (x x p ). The channel is therefore a parallel combination of a BSC and a perfect channel. The decoder corrects the "virtual" channel noise, and thus estimates x given the parity bits x p and the SI y regarded as a noisy version of the original sequence x. Therefore, the usual ML decoder must be adapted to take into account that some bits of the received sequence (x p ) are perfectly known. We will detail this in Section 2.2.

Interestingly, both approaches (syndrome or parity) are equivalent if the generator matrix (in the parity approach) is the concatenation of the identity matrix and the parity check matrix used in the syndrome approach: G = (I H). However, the two codes C and C ′ (defined by H and G respectively) are not the same. They are not even defined in the same space (C is a subspace of {0, 1} n , whereas C ′ is a subspace of {0, 1} 2n-k ). Figure 4 compares the implementation of the syndrome and parity approaches. Practical solutions based on the syndrome approach first appeared in a scheme called discus [START_REF] Pradhan | Distributed source coding using syndromes (DISCUS): Design and construction[END_REF]. For block codes [START_REF] Pradhan | Distributed source coding using syndromes (DISCUS): Design and construction[END_REF], syndrome decoding is performed. For convolutional codes, the authors in [START_REF] Pradhan | Distributed source coding using syndromes (DISCUS): Design and construction[END_REF] propose to apply the Viterbi decoding on a modified trellis. In order to solve the problem (2), the decoder is modified such that it can enumerate all the codewords in a given coset. The method uses the linearity property [START_REF] Aaron | Compression with side information using turbo codes[END_REF]. For systematic convolutional codes, a representative of the coset is the concatenation of the k-length zero vector and the n -k-length syndrome s. This representative is then added to all the codewords labeling the edges of the trellis (see Figure 5). Note that the states of the trellis depend on the information bits, and thus on the systematic bits, only. Thus, there exists one trellis section per syndrome value. The decoder, knowing the syndrome s, searches for the sequence with that particular syndrome that is closest to y. First it builds the complete trellis. Each section of the trellis is determined by the syndrome. Once the whole trellis is built, the Viterbi algorithm chooses the closest sequence to the received y. A variation of the above method is proposed in [START_REF] Tu | An efficient SF-ISF approach for the Slepian-Wolf source coding problem[END_REF], where the translation by a coset representative is performed outside the decoder (see Figure 6). First the representative (0 s) is computed (this step is called "inverse syndrome former") and added to y. Then the decoding is performed (in the coset of syndrome 0), and finally the representative is retrieved from the output of the decoder. The advantage of this method is to use a conventional Viterbi decoder without a need to modify it. This method can also be applied to turbo codes [START_REF] Tu | An efficient SF-ISF approach for the Slepian-Wolf source coding problem[END_REF]. In this case, two syndromes (s 1 , s 2 ) are computed, one for each constituent code. A representative of the coset is (0 s 1 s 2 ). The authors in [START_REF] Roumy | Rate-adaptive turbo-syndrome scheme for Slepian-Wolf coding[END_REF] propose a SW scheme based on convolutional codes and turbo codes that can be used for any code (not only systematic convolutional code). Rather than considering the usual trellis based on the generator matrix of the code, the decoder is based on a syndrome trellis. This trellis has first been proposed for binary linear block codes [START_REF] Wolf | Efficient Maximum Likelihood decoding of linear block codes using a trellis[END_REF], and was then generalized to convolutional codes [START_REF] Sidorenko | Decoding of convolutional codes using a syndrome trellis[END_REF]. Such a trellis can enumerate a set of sequences in any coset. More precisely, a section corresponds to the reception of n bits of x and n -k syndrome bits (see Figure 7). Thus, there exists 2 n-k possible trellis sections, one for each syndrome value. The decoder, knowing the syndrome s, searches for the sequence with that particular syndrome which is closest to y. First it builds the complete trellis. Each section of the trellis is determined by the syndrome. Once the whole trellis is built, the Viterbi algorithm is performed and chooses the closest sequence to the received y.

For LDPC codes, the belief propagation decoder can be adapted to take into account the syndrome [START_REF] Liveris | Compression of binary sources with side information at the decoder using LDPC codes[END_REF]. More precisely, the syndrome bits are added to the graph such that each syndrome bit is connected to the parity check equation it is related to. The update rule at a check node is modified in order to take into account the value of the syndrome bit (known perfectly at the decoder).

The parity approach

The parity approach presented in Section 2.1.2 has been implemented using various channel codes, for instance turbo-codes [START_REF] Aaron | Compression with side information using turbo codes[END_REF][START_REF] Bajcsy | Coding for the Slepian-Wolf problem with turbo codes[END_REF]. Consider a turbo encoder formed by the parallel concatenation of two recursive systematic convolutional (RSC) encoders of rate (n -1)/n separated by an interleaver (see Figure 8). For each sequence x (of length n) to be compressed, two sequences of parity bits x p = (x 1 p x 2 p ) are computed and transmitted without any error to the decoder. The turbo code is composed of two symbol Maximum A Posteriori (MAP) decoders. Each decoder receives the (unaltered) parity bits together with the SI y, seen as a noisy version of the sequence x. The concatenation (y x p ) can be seen as a noisy version of the coded sequence (x x p ), where the channel is a parallel combination of a BSC and of a perfect channel. Therefore, the usual turbo decoder must be matched to this combined channel. More precisely, the channel transitions in the symbol MAP algorithm which do not correspond to the parity bits are eliminated. Such a scheme achieves an n : 2 compression rate.

x (D) D D 2 σ 1 σ (D) (D) s(D) 1 2 x (D) (a)

Rate adaptation

Note that in all methods presented so far, in order to select the proper code and code rate, the correlation between the sources needs to be known or estimated at the transmitter before the compression starts. However, for many practical scenarios, this correlation may vary, and rate adaptive schemes have to be designed. When the correlation decreases, the rate bound moves away from the origin (see Figure 9). The rate of the code can then be controlled via a feedback channel. The decoder estimates the Bit Error Rate (BER) at the output of the decoder with the help of the log-likelihood ratios computed by the channel decoder. If the Bit Error Rate (BER) at the output of the decoder exceeds a given value, more bits are requested from the encoder. In this context of feedback controlled schemes, the code should be incremental such that the encoder does not need to re-encode the data. The first bits are kept, and additional bits are only sent upon request. In the following, we present various rate-adaptive methods and specify whether they are incremental or not.

B for a given correlation

H(X) R X H(Y ) R Y A Slepian Wolf bound
Figure 9: Evolution of the SW region, when the correlation between the sources varies.

The parity approach

The parity approach has been originally proposed in order to easily construct rate adaptive schemes (see Section 2.2). At the encoder, the parity bits are punctured (some parity bits are not transmitted) and the decoder compensates for this puncturing, using standard techniques coming from channel coding. The source sequence x is compressed through some punctured parity bits xp , and the decoder retrieves the original sequence aided by the SI y. The sequence (y xp ) can be seen as the output of a channel which is a combination of a perfect channel (unpunctured parity bits), an erasure channel (punctured parity bits) and a BSC channel (correlation between the sources x and y). The method is by construction incremental.

The syndrome approach.

Due to the optimality of the syndrome approach [START_REF] Wyner | Recent results in the Shannon theory[END_REF], a natural design of a rate-adaptive scheme consists of puncturing the syndrome. However, using puncturing mechanisms leads to performance degradation as reported in [START_REF] Tan | Enhancing the robustness of distributed compression using ideas from channel coding[END_REF][START_REF] Li | An optimal distributed and adaptive source coding strategy using rate-compatible punctured convolutional codes[END_REF][START_REF] Varodayan | Rate-adaptive codes for distributed source coding[END_REF]. More precisely, it is shown in [START_REF] Tan | Enhancing the robustness of distributed compression using ideas from channel coding[END_REF] that the syndrome approach is very sensitive to errors or erasures, which indicates that the puncturing of syndromes will lead to performance degradation. Therefore, the first contributions avoid or compensate for this performance degradation.

A first method proposed in [START_REF] Li | An optimal distributed and adaptive source coding strategy using rate-compatible punctured convolutional codes[END_REF] punctures the parity bits rather than the syndrome bits. Each puncturing pattern defines a new code for which a parity check matrix can be computed. Then, one can construct a syndrome former and inverse syndrome former for the new punctured code (presented in Section 2.1.2). This method can be implemented using any code, in particular convolutional and turbo codes. However, the resulting code is not incremental.

A first incremental SW coding scheme based on Serially Concatenated Accumulate (SCA) codes is proposed in [START_REF] Chen | Distributed source coding using serially-concatenated-accumulate codes[END_REF]. An inner encoder concatenates the first source bit with the modulo-2 sum of consecutive pairs of source bits. The output of the accumulator is interleaved and fed into a so-called base code, which is either an extended Hamming code or a product of single parity check codes, which then computes the syndrome bits. The accumulator code is of rate 1, so that the compression rate is controlled by the base code. The base code is first decoded using a MAP decoder for extended hamming codes or a belief propagation algorithm for product parity check codes. The accumulator code is decoded with a symbol MAP algorithm decoder. A turbo-like algorithm iterates between both decoders.

The authors in [START_REF] Varodayan | Rate-adaptive codes for distributed source coding[END_REF] investigate the puncturing of LDPC (Low density parity check code) encoded syndromes. To avoid degrading the performance of the LDPC code, the syndrome bits are first protected with an accumulator code before being punctured. Here also, the accumulator code is of rate 1, so that the compression rate is not modified. The combined effect of the puncturing and of the accumulator code is equivalent to merging some rows of the parity check matrix by adding them. This defines a set of parity check matrices, one for each rate. Then, for each parity check matrix, decoding is performed according to the modified sum-product algorithm [START_REF] Liveris | Compression of binary sources with side information at the decoder using LDPC codes[END_REF] presented in Section 2.1.1. An interesting feature of this method is that it is incremental. If the merging of rows satisfies a regularity rule (one can only add two rows that have no "1" at the same column position), then the accumulated syndrome value of the new (smallest compression rate) matrix can be computed by adding the previous syndrome value (corresponding to the highest compression rate matrix) to the current one. The performance of the method is shown in Figure 10 (a). Another method is proposed in [START_REF] Jiang | Rateless Slepian-Wolf coding based on rate adaptive Low-Density-Parity-Check codes[END_REF]. Instead of protecting the syndrome bits, the authors combine the syndrome and the parity approaches. Given an input vector x of length n, the encoder transmits m syndrome bits plus l parity bits, defining an (n + l, n -m) linear error correcting code. Rate adaptation is then performed by puncturing the parity bits.

In [START_REF] Roumy | Rate-adaptive turbo-syndrome scheme for Slepian-Wolf coding[END_REF], the optimal decoder for convolutional codes under syndrome puncturing is designed. It is shown that performance degradation due to syndrome puncturing can be avoided without a need to encode (or protect) the syndromes. When syndrome bits are punctured, the optimal decoder should in principle search for the closest sequence in a union of cosets. This union corresponds to all possible syndromes that equal the received syndrome in the unpunctured positions. Therefore, the number of cosets grows exponentially with the number of punctured bits. A brute force decoder consists in performing a ML algorithm in each coset, but then the decoding complexity of such a method would grow exponentially with the number of punctured bits. On the other hand, if the decoder is not modified, it leads to systematic errors, since the search may be performed in the wrong coset. The method proposed in [START_REF] Roumy | Rate-adaptive turbo-syndrome scheme for Slepian-Wolf coding[END_REF] is based on the syndrome trellis presented in Section 2.1.1. Whenever some syndrome bits are punctured, a new trellis section is constructed as the union of the trellis sections compatible with the received punctured syndrome. This enumerates the sequences in the union of cosets. The resulting trellis is called the super trellis (see Figure 11) and the Viterbi algorithm is performed on this new trellis. The complexity of the proposed algorithm grows only linearly with the code blocklength and with the number of punctured positions. The authors in [START_REF] Roumy | Rate-adaptive turbo-syndrome scheme for Slepian-Wolf coding[END_REF] also show that this decoder can be applied to turbo-codes. The performance of the method is shown in Figure 10.

Non-asymmetric SW coding

For the sake of simplicity, we focus again on the two-user setting and we now consider the case where both sources are compressed in order to reach any point of the segment between A and B in Figure 1 (b). For some applications, it may be desirable to vary the rates of each encoder while keeping the total sum-rate constant. This set-up is referred to as non asymmetric. It will be said to be symmetric when both sources are compressed ]. This trellis is the union of the two trellis sections of Figure 7.

at the same rate (point C in Figure 1 (b)). Note that both sources can be compressed at the same rate if and only if max(H(X|Y ),

H(Y |X)) ≤ H(X, Y ) 2 ≤ min((H(X), H(Y ))
. Several methods can be used to reach any point of the SW rate bound. The first approach called time sharing uses two asymmetric coder/decoder pairs alternatively. Other methods code each input sequence x and y with linear channel codes. For each source, part of the information bits plus syndrome or parity bits are transmitted. The decoder then needs to estimate the n-length sequences x and y knowing the partial information bits, the syndrome or parity bits and the correlation between x and y.

Time-sharing

Let x and y again denote two random binary correlated sequences of source symbols of length n. It is assumed that the correlation is defined by a BSC of cross-over probability p. All points of the segment between A and B of the SW rate bound are achievable by time sharing. More precisely, a fraction α of samples (α.n samples, where n is the sequence length) is coded at the vertex point A, that is, at rates (H(Y ), H(X|Y )), with the methods described in Section 2, and a fraction (1 -α) of samples is then coded at rates (H(X), H(Y |X)) corresponding to the corner point B of the SW rate region. This leads to the rates R

X = αH(X) + (1 -α)H(X|Y ) and R Y = (1 -α)H(Y ) + αH(Y |X).

The parity approach

The sequences x and y of length n are fed into two linear channel coders (turbo coders [START_REF] Cabarcas | Approaching the Slepian-Wolf boundary using practical channel codes[END_REF] or LDPC coders [START_REF] Sartipi | Distributed source coding in wireless sensor networks using LDPC coding: The entire Slepian-Wolf rate region[END_REF]) which produce two subsequences x h = (x 1 . . . x l ) and y h = (y l+1 . . . y n ) of information bits and two sequences x p 1 . . . x p a and y p 1 . . . y p b of parity bits, where a ≥ (n -l)H(X|Y ) and b ≥ lH(Y |X). The achievable rates for each source are then

R X ≥ l n H(X) + a n ≥ l n H(X) + n-l n H(X|Y ) and R Y ≥ n-l n H(Y ) + b n ≥ n-l n H(Y ) + l n H(Y |X).
The SW boundary can be approached by varying the ratio l n between 0 and 1. Unlike the time-sharing approach, the parity bits are computed on the entire input sequences of length n. The sequence (x h x p ) is regarded as a noisy version of the sequence (y p y h ). As in the asymmetric set-up, the channel is a parallel combination of a BSC and of a perfect channel. The decoder then needs to estimate x and y given (x h x p ) and (y p y h ).

A first practical implementation of the parity approach is proposed in [START_REF] Garcia-Frias | Compression of correlated binary sources using turbo codes[END_REF] with turbo codes, and considers the particular case of symmetric SW coding. The solution is then extended to reach any point of the SW boundary in [START_REF] Cabarcas | Approaching the Slepian-Wolf boundary using practical channel codes[END_REF], [START_REF] Garcia-Frias | Approaching the Slepian-Wolf boundary using practical channel codes[END_REF]. In [START_REF] Garcia-Frias | Approaching the Slepian-Wolf boundary using practical channel codes[END_REF], the two information sequences of length n are encoded with a systematic punctured turbo code. The information bits of the second source are interleaved before being fed to the encoder. All the systematic bits plus a subset of the parity bits are punctured in order to leave only a bits for the sequence x and b bits for the sequence y. Each turbo decoder proceeds in the standard way, with the difference that part of the bits are received via an ideal channel. After each iteration, the measures obtained as a result of a turbo decoding on each input bit of one sequence, e.g. x, are passed as additional extrinsic information to the turbo decoder used to estimate the sequence y, via the binary symmetric correlation channel (i.e. P(y k = 0) = (1 -p)P(x k = 0) + pP(x k = 1)).

Another implementation of the parity approach is described in [START_REF] Sartipi | Distributed source coding in wireless sensor networks using LDPC coding: The entire Slepian-Wolf rate region[END_REF] with LDPC codes, and later studied in [START_REF] Sartipi | Distributed Source Coding Using Short to Moderate Length Rate-Compatible LDPC Codes: The Entire Slepian-Wolf Rate Region[END_REF] for short to moderate length codes. The decoder needs to determine an n-length sequence from the part of information bits and parity bits received for the sequence x and from the correlated sequence y. For this, a message-passing algorithm is used by setting the LLR (Log likelihood ratio) of the bits received via the ideal channel to infinity. The LLR of the bits received via the correlation channel are set to ± log( 1-p p ). The LLR for the punctured bits are set to zero. Two sets of degree distributions for the variables nodes are used to account for the fact that information bits are received via the correlation channel whereas the parity bits are received via an ideal channel.

The syndrome approach

Let us consider an (n, k) linear channel code C defined by its generator matrix G k×n and its parity-check matrix H (n-k)×n . A syndrome approach was first proposed in [START_REF] Pradhan | Distributed source coding: symmetric rates and applications to sensor networks[END_REF], based on the construction of two independent linear binary codes C 1 and C 2 with G 1 and G 2 as generator matrices, obtained from the main code C. More precisely, the generator matrices G 1 and G 2 of the two subcodes are formed by extracting m 1 and m 2 lines respectively, where m 1 +m 2 = k, from the matrix G of the code C. The parity check matrices H 1 and H 2 are then of size (n-m 1 )×n and (n-m 2 )×n respectively. A geometric interpretation of the code splitting is shown in Figure 12. Each coder sends a syndrome, defined as s x = xH T 1 and s y = yH T 2 respectively, to index the cosets of C 1 and C 2 containing x and y. The total rate for encoding the input sequences of length n is then n -m 1 + n -m 2 = 2n -k bits. The cosets containing x and y are translated versions of the codes C 1 and C 2 (i.e., the cosets having null syndromes) by vectors t x and t y . This translation is illustrated in Figure 12, where the addition by the translation vector is performed over the finite field {0, 1}. The codes C 1 and C 2 must be chosen such that all pairs (x, y) can be determined uniquely given the two coset indexes. We now explain how to determine a pair (x, y) from a usual ML decoder. Let u x G 1 and u y G 2 define codewords in C 1 and C 2 . By definition these vectors have a null syndrome. All possible codewords in a coset of syndrome s can be enumerated by translating a codeword belonging to the coset of null syndrome by a vector t belonging to the coset of syndrome s (see equation ( 1)). If the code is systematic, a candidate for the translating vector is t = (0 s), as explained in Section 2.2. Thus, x and y can be seen as translated versions of codewords belonging to the cosets of null syndrome of the codes C 1 and C 2 respectively. The vectors x and y can thus be expressed as x = u x G 1 ⊕ (0 s x ), y = u y G 2 ⊕ (0 s y ), where t x = (0 s x ) and t y = (0 s y ) are the representatives of the cosets of C 1 and C 2 with syndromes s x and s y . The decoder must search for a pair of codewords, one from each translated coset of C 1 and C 2 . When receiving the syndromes s x and s y , it first finds a codeword c of the main code C (which is actually the error pattern between x and y) that is closest to the vector t = t x ⊕ t y = (0 s x ) ⊕ (0 s y ). The error pattern x ⊕ y is the minimum weight codeword having the same syndrome as the vector t. If the code is systematic, the sequences x and y are reconstructed as x = ûx G 1 ⊕ t x and ŷ = ûy G 2 ⊕ t y , where ûx and ûy are the systematic bits of the codeword c. This method achieves the optimal SW compression sum-rate if the global code C achieves the capacity of the equivalent correlation channel (between x and y). The number of lines assigned to G 1 (and therefore to G 2 ) allows to choose any rate on the dominant face of the SW region (between points A and B in Figure 1 (b)). The above ideas are further developed in [START_REF] Stankovic | Design of Slepian-Wolf codes by channel code partitioning[END_REF], [START_REF] Stankovic | On code design for the Slepian-Wolf problem and lossless multiterminal networks[END_REF], for non-systematic linear codes. The code construction has been extended in [START_REF] Schonberg | Distributed code constructions for the entire Slepian-Wolf rate region for arbitrarily correlated sources[END_REF] to the case where the sources X and Y are binary but non uniformly distributed.

C 2 01 = {•} C 2 10 = { } C 2 11 = { } C 2 = {•} C 1 01 = {•} C 1 10 = { } C 1 11 = { } C 1 = {•}
In a second approach proposed in [START_REF] Gehrig | Symmetric and asymmetric slepian-wolf codes with systematic and non-systematic linear codes[END_REF], the vectors x and y belong to the same coset of a unique code C, which is the translated version of the coset of null syndrome by a vector t. Each source vector is identified by a syndrome computed with the parity check matrix H of the code C plus part of the source information bits [START_REF] Gehrig | Symmetric and asymmetric slepian-wolf codes with systematic and non-systematic linear codes[END_REF]. The syndromes s T x = Hx T and s T y = Hy T , of length (n -k), are thus computed for both sequences and transmitted to the decoder. In addition, the k ′ first bits of x (denoted x k ′ 1 ) and the k -k ′ next bits for the source y (denoted y k k ′ +1 ), are transmitted as systematic bits, where k ′ is an integer so that k ′ ∈ [0, k]. The total rate for the sequences x and y of length n is respectively n -k + k ′ and n -k ′ bits. The structure of the coders is depicted in Figure 13. Note that k ′ = k and k ′ = 0 correspond to the two asymmetric set-ups with rates given by the corner points A and B of the SW region.

y k k ′ +1 H x n 1 n Encoder X k ′ n -k s x x k ′ 1 H y n 1 n Encoder Y k -k ′ n -k s y
Figure 13: The non asymmetric coders in the syndrome approach [START_REF] Gehrig | Symmetric and asymmetric slepian-wolf codes with systematic and non-systematic linear codes[END_REF]. A single code C (determined by the parity check matrix H) is used for each sequence to be compressed.

As in the asymmetric case, the representative of the coset is thus the concatenation of the transmitted information bits (k ′ bits for the sequence x) and of the (n -k)-length syndrome vector. As in the first approach, when receiving the syndromes s x and s y , the decoder must find a codeword c of the code C that is closest to the translating vector t = t x ⊕ t y = (0 s x ) ⊕ (0 s y ). For this, it first computes s z = s x ⊕ s y , which is the syndrome of the error pattern z between x and y (z = x ⊕ y). In [START_REF] Gehrig | Symmetric and asymmetric slepian-wolf codes with systematic and non-systematic linear codes[END_REF], a modified LDPC decoder estimates ẑ = x ⊕ y from the syndrome s z and the all-zero word of size n (see Figure 14) [START_REF] Liveris | Compression of binary sources with side information at the decoder using LDPC codes[END_REF]. The error pattern z is the smallest weight codeword with syndrome s z . When convolutional and turbo codes are used, the estimation of the error pattern can be performed with a conventional Viterbi decoder and an inverse syndrome former (ISF) [START_REF] Tan | A practical and optimal symmetric Slepian-Wolf compression strategy using syndrome formers and inverse syndrome formers[END_REF] or with a syndrome decoder [START_REF] Roumy | Rate-adaptive turbo-syndrome scheme for Slepian-Wolf coding[END_REF] (see Section 2.2 for further details).

Once the error pattern is found, the subsequences of information bits x k k ′ +1 and y k ′ 1 can be retrieved from the error pattern z = x ⊕ y as (see Figure 14-right)

xk k ′ +1 = y k k ′ +1 ⊕ ẑk k ′ +1 and ŷk ′ 1 = x k ′ 1 ⊕ ẑk ′ 1 . (3)
Subsequences of n -k bits, i.e. x n k+1 and y n k+1 , to be computed for both sequences. Let us assume that H = (A B), where B is an invertible square matrix of dimension (n -k) × (n -k). Note that for a rate k/n channel code, the parity check matrix H has rank n -k. Therefore, one can always find a permutation to be applied on the columns of H so that the resulting parity check matrix has the right form. Thus, sequence x (and similarly for the sequence y) can be computed as

s x = Hx = (A B)x = A x k 1 ⊕ B x n k+1 ,
xn k+1 = B -1 (s x ⊕ A xk 1 ), (4)
where B -1 denotes the inverse of the matrix B [START_REF] Gehrig | Symmetric and asymmetric slepian-wolf codes with systematic and non-systematic linear codes[END_REF]. The authors in [START_REF] Gehrig | Symmetric and asymmetric slepian-wolf codes with systematic and non-systematic linear codes[END_REF] have used LDPC codes.

If the error pattern is not perfectly estimated, the estimation of the remaining symbols x n k+1 in equation ( 4) may yield error propagation. Note that the unknown positions in the vector x are design parameters. These positions (or equivalently the columns of the matrix H to be extracted in order to build the matrix B) can be chosen such that the inverse B -1 is as sparse as possible. Figure 15 shows the BER of the error pattern z (continuous line) and its effect on the estimation of the source sequence x. Performance is shown for a convolutional code. The dotted curve represents the BER, when equation ( 4) is performed with an arbitrary invertible matrix B. This BER can be lowered to the dashed curve, if a matrix B with sparse inverse is chosen. This limits the error propagation. Finally, the error propagation can be further reduced, if one applies a modified decoder to solve equation ( 4). This decoder (Viterbi for a convolutional code) is matched to a channel which combines a perfect channel (for x k ′ 1 ), a BSC (for xk k ′ +1 with crossover probability, the BER of z) and an erasure channel (for x n k+1 ). Interestingly, with this decoder the BER of x remains almost the same as that of z.

Source splitting

Source splitting [START_REF] Rimoldi | Asynchronous Slepian-Wolf Coding via Source-Splitting[END_REF] is another approach to vary the rates between the two encoders. The approach is asymptotic and involves splitting the source into sub-sources having a lower entropy. More precisely, it transforms the two source problem into a three source problem where one source, e.g. X is split into two i.i.d discrete sources U and V as U = XT and V = Y (1-T ). T is an i.i.d. binary source (which can be seen as a time-sharing sequence). 15 12 17 and is punctured over a period of four trellis sections in order to get a 2 : 1 compression rate for the source.

By varying P(T = 1), one can vary H(Y |U ) between H(Y ) and H(Y |X). The sum-rate

becomes

R X + R Y = R U + R V + R Y = H(U |T ) + H(Y |U ) + H(V |U, Y ).
A random coding argument is used to show that the rate triple is achievable [START_REF] Rimoldi | Asynchronous Slepian-Wolf Coding via Source-Splitting[END_REF], however no constructive codes are proposed.

Rate adaptation

In practical applications, the correlation between the two sources may not be known at the time of code design. It may thus be necessary, as in the asymmetric set-up, to have solutions allowing for flexible rate adaptation to any correlation between the two sources. Non-asymmetric rate-adaptive SW coding/decoding schemes are direct extensions of their asymmetric counterparts. Rate adaptation is performed by simply puncturing information, parity or syndrome bits in the schemes described above.

In the parity approach, we have seen that for two correlated sequences of length n, the rate allocation between the two sequences is controlled by the number l of information bits transmitted for each. The change in the rate allocation between the two sources is thus performed by puncturing more or less information bits. For a given rate share between the two sources, rate adaptation to varying correlation is achieved by simply puncturing the parity bits. Standard decoding of punctured channel codes can then be applied.

For the syndrome approaches, as explained in Section 2.3, the application of the puncturing is less straightforward. Puncturing the syndrome bits may degrade the performance of the code. The approach considered in [START_REF] Toto-Zarasoa | Rate-adaptive codes for the entire Slepian-Wolf region and arbitrarily correlated sources[END_REF], similarly to [START_REF] Varodayan | Rate-adaptive codes for distributed source coding[END_REF] for the asymmetric setup, consists of first protecting the syndromes with an accumulator code. The effect of the accumulator code followed by the puncturing is equivalent to merging some rows of the parity check matrix H by adding them, thus constructing a matrix H i of dimension (n -k i ) × n, of rank n -k i . In the matrix H i , with appropriate permutation, one may exhibit a submatrix B i of dimension (n -k i ) × (n -k i ) which is invertible (see equation ( 4)). The positions of the k ′ (k ′ ∈ [0, k i ]) and k i -k ′ information bits transmitted for the sequences x and y respectively must then be chosen so that they correspond to the positions of the remaining non-free k i columns of H i . If the correlation is not known to the encoder, the rate may be controlled via a feedback channel. In this case, once the error pattern ẑ has been estimated, the decoder verifies if the condition ẑH T = s z is satisfied. If this condition is not satisfied, it then requests for more syndrome bits. Note that, if the error pattern is not perfectly estimated, the last step of the decoding algorithm represented by equation (4) may yield error propagation. The coding and decoding structures are depicted in Figure 16. Figure 17 illustrates the rate points achieved with a non-symmetric SW coding/decoding scheme based on LDPC codes.

Punct Punct y n 1 n Encoder Y k i -k ′ n -k i H H x n 1 n Encoder X k ′ n -k i

Advanced topics 4.1 Practical code design based on source codes

Code design based on source alphabet partitioning: The use of source codes for SW coding has first been explored in [START_REF] Al Jabri | Zero-error codes for correlated information sources[END_REF] considering Huffman codes. The approach relies on partitioning the source alphabet into groups of symbols. One source Y is coded with a Huffman code designed according to its stationary probability P(Y ). The alphabet of the second source X is partitioned so that two symbols x i and x j are not grouped together if there exists a symbol y such that P(x i , y) > 0 and P(x j , y) > 0. The joint p.m.f of (X, Y ) may need to be slightly modified, e.g. by thresholding the smallest values and then renormalizing, so that this condition is verified. In addition, the entropy of the group index must be minimum, and approach at best H(X|Y ). Knowing the SI symbol y, and the group index, the decoder can find the transmitted symbol x. The above code design based on alphabet partitioning has been formalized and generalized in [START_REF] Zhao | Optimal code design for lossless and near lossless source Coding in multiple access network[END_REF] for arbitrary p.m.f. P(X, Y ), assuming memoryless sources. The partition can be coded with a Huffman or an arithmetic code.

Punctured and overlapped arithmetic codes: Different solutions based on overlapped arithmetic [START_REF] Grangetto | Distributed arithmetic coding[END_REF] and quasi-arithmetic (QA) [START_REF] Artigas | Overlapped quasi-arithmetic codes for distributed video coding[END_REF] codes, as well as punctured (quasi)arithmetic codes [START_REF] Malinowski | Distributed source coding uspunctured quasi-arithmetic codes for memory and memoryless sources[END_REF] have appeared recently for the case of binary sources. Arithmetic coding recursively divides the interval [0, 1) according to the source probabilities. Let us consider a binary memoryless source with probabilities denoted P 0 and P 1 . At each symbol clock instant n, the current interval [L n , H n ) is divided into two subintervals whose widths are proportional to P 0 and P 1 = 1 -P 0 respectively. One of these subintervals is selected according to the value of the next symbol and becomes the current interval. Once the last symbol is encoded, the encoder produces a sequence of bits identifying the final sub-interval. Practical implementations of arithmetic coding have been first introduced in [START_REF] Rissanen | Generalized Kraft inequality and arithmetic coding[END_REF] and [START_REF] Pasco | Source coding algorithms for fast data compression[END_REF], and further developed in [START_REF]Arithmetic codings as number representations[END_REF], [START_REF] Witten | Arithmetic coding for data compression[END_REF].

The encoding and decoding processes can be modeled as state machines. But, with optimal arithmetic coding, the number of states can grow exponentially with the sequence length. Controlled approximations can reduce the number of possible states without significantly degrading compression performances [START_REF] Howard | Image and Text Compression[END_REF]. This fast, but reduced precision, implementation of arithmetic coding is called quasi-arithmetic coding [START_REF] Howard | Image and Text Compression[END_REF]. Instead of using the real interval [0, 1[, quasi-arithmetic coding is performed on an integer interval [0, T [. The value of T controls the trade-off between complexity, the number of states, and compression efficiency.

The average code length achieved per input source symbol is very close to the source entropy. To further reduce the rate down to the conditional entropy of two correlated sources, two strategies can be considered: puncturing the sequence of encoded bits [START_REF] Malinowski | Distributed source coding uspunctured quasi-arithmetic codes for memory and memoryless sources[END_REF] or overlapping the symbol probability intervals of the arithmetic [START_REF] Grangetto | Distributed arithmetic coding[END_REF] or quasi-arithmetic coder [START_REF] Artigas | Overlapped quasi-arithmetic codes for distributed video coding[END_REF]. For the overlapped (quasi)-arithmetic codes, at a given instant n, the probability interval [L n , H n ) is partitioned into two sub-intervals [L n , P 0 (H n -L n ) + ρT /2) associated to the symbol 0 and [P 0 (H n -L n ) -ρT /2, H n ) associated to the symbol 1. The parameter ρ controls the overlap between the sub-intervals. The larger the overlap, the lower the bit rate but the higher the uncertainty on the decoded sequence. In both cases, overlapped and punctured codes, the resulting code is not uniquely decodable anymore. The ambiguity on the encoded sequence of symbols can be removed with the help of the SI (correlated source) and of a symbol MAP decoder.

To explain the decoding algorithm, let us first consider the punctured solution. Let x and y be two correlated sequences of length L(x). The sequence x is coded with a QA code producing a sequence of bits u of length L(u) which is then punctured. Given the received QA coded bitstream u L(u) 1 and the correlated sequence y L(x) 1 (SI), the symbol posterior marginals P(

X n = x n | u L(u) 1 , y L(x) 1
) are computed by running a BCJR algorithm [START_REF] Bahl | Optimal decoding of linear codes for minimizing symbol error rate[END_REF] on the state model of the QA automaton. To cope with the fact that the QA automaton contains transitions corresponding to a varying number of symbols and a varying number of bits, the state model used in the decoding must keep track of the number of symbols being coded at a particular bit clock instant k. It is hence defined by the pairs of random variables V k = (N k , M k ), where N k denotes the state of the QA automaton, and M k represents the symbol clock value at the bit clock instant k [START_REF] Guionnet | Soft and joint source-channel decoding of quasiarithmetic codes[END_REF]. Since the variable M k corresponds to the symbol clock, it accounts for the correlation between the encoded sequence and the SI. The transition probabilities on the state model V k = (N k , M k ) are equal to the transition probabilities between states N k of the QA automaton, if the numbers of bits and symbols associated to this transition match the one defined by the automaton. The transition probabilities are equal to zero otherwise. The probabilities of transition between states N k of the QA automaton depend on the source statistics, and can account for source memory. Thus, for each state ν = (n, m), the BCJR algorithm computes the probabilities α k (ν) = P(V k = ν; U k 1 ) and β k (ν) = P(U

L(U) k+1 | V k = ν).
The branch metric γ k (ν ′ |ν) used for the transition τ between two states ν = (n, m) and ν ′ = (n ′ , m ′ ) is given by γ k (ν ′ |ν) = P(ν ′ |ν) × P(b τ ) × P(x τ |y τ ), where b τ and x τ denote the subsequences of bits and symbols associated to the given transition τ on the QA automaton. The probability P(b τ ) is computed considering a probability of 0.5 for the punctured positions. The term P(x τ |y τ ) represents the correlation channel between X and Y .

The decoding for the overlapped quasi-arithmetic codes proceeds in the same manner as for the punctured solution. The only difference is in the automaton which, in the case of overlapped codes, does not only depend of the distribution of the source X but also of the overlap factor ρ (for details see [START_REF] Malinowski | Distributed source coding uspunctured quasi-arithmetic codes for memory and memoryless sources[END_REF] and [START_REF] Artigas | Overlapped quasi-arithmetic codes for distributed video coding[END_REF]). A second difference is in the branch metric γ k (ν ′ |ν) in which the term P(b τ ) disappears, since, in this case, all the coded bits are known to the decoder (and not punctured as in the previous method).

Generalization to non-binary sources

In the chapter so far, only binary correlated sources have been considered. Practical applications often involve non-binary, e.g. q-ary, sources. In practice, before being encoded, the q-ary sources are first binarized. Each resulting sequence of bits is then fed to the SW coder. This is, for example, the case in [START_REF] Zhao | Data compression of correlated non-binary sources using punctured turbo codes[END_REF] where the authors describe the principle using turbo codes to compress both sources X and Y . For each source, the sequences of bits at the output of the "symbol-to-bit" converter are interleaved and input to a punctured turbo coder. The turbo decoders act at a bit level in a standard fashion, but information exchange is performed between the two turbo decoders at the symbol level. The a posteriori probabilities computed by a turbo decoder for each input bit is converted into a measure on the corresponding q-ary symbol. The resulting symbol probabilities are then multiplied by the conditional probabilities characterizing the correlation channel and fed into the second turbo decoder as extrinsic information.

Generalization to M sources

The asymmetric and non-asymmetric coding schemes presented above can be extended to more than 2 sources. The practical code design approach proposed in [START_REF] Pradhan | Distributed source coding: symmetric rates and applications to sensor networks[END_REF] has been extended in [START_REF] Stankovic | Design of Slepian-Wolf codes by channel code partitioning[END_REF] and [START_REF] Stankovic | On code design for the Slepian-Wolf problem and lossless multiterminal networks[END_REF] for M sources (see Section 3.3). Each sub-code is constructed by selecting a subset of rows from the generator matrix G of the starting code C. Examples of design are given for IRA codes. However, the method is shown to be suboptimal when the number of sources is greater (or equal) than three. The parity approach described in [START_REF] Sartipi | Distributed source coding in wireless sensor networks using LDPC coding: The entire Slepian-Wolf rate region[END_REF] has also been extended to M sources in [START_REF] Sartipi | Distributed Source Coding Using Short to Moderate Length Rate-Compatible LDPC Codes: The Entire Slepian-Wolf Rate Region[END_REF]. The sequences x i , i = 1, . . . M , of length n are fed into M LDPC coders which produce subsequences of a i × k information bits and of (1 -a i ) × k parity bits. Joint decoding of the M sources is then performed.

Conclusions

This chapter has explained how near-capacity achieving channel codes can be used to approach the SW rate bound. Although the problem is posed as a communication problem, classical channel decoders need to be modified. This chapter has outlined the different manners to adapt channel decoding algorithms to the Slepian-Wolf decoding problem. In the approaches presented, it is assumed that syndrome or parity bits are transmitted over a perfect channel. As explained above, the equivalent communication channel is thus the parallel combination of a BSC and a perfect channel. In some applications, this may not be the case: syndrome or parity bits may have to be transmitted on an erroneous communication channel. Distributed joint source-channel coding schemes, in which the SW code acts as a single code for both source coding and channel error correction, can be found in the literature to address this particular scenario. This last problem however remains a field of research. Finally, the use of SW codes is currently being explored for a number of applications such as low-power sensor networks, compression of hyperspectral images, mono-view and multi-view video compression, error-resilient video transmission,

For a given y, set of xFigure 2 :

 2 Figure2: The partition of the sequences x into four subsets (called bins) such that the sequences in each bin are as far apart as possible. The set of sequences x jointly typical with a given y are as "different" as possible: here they are elements of different bins.

Figure 3 :

 3 Figure 3: Construction of a binning scheme with a linear block code in {0, 1} 3 . The cube and the basis vector in {0, 1} 3 (left); a code defined by the parity check matrix H = (111) or equivalently the generator matrix G = 110 101 (right).

2. 2

 2 Practical code design based on channel codes 2.2.1 The syndrome approach.

= 1 Figure 5 :

 15 Figure 5: Block diagram (a) and trellises (b,c) for the systematic convolutional code H = [1 5 7 ]. The diagram (a) defines the states σ 1 (D) σ 2 (D) of the trellis, where D is a dummy variable representing a time offset. The trellis section in (b) corresponds to the syndrome value s = 0 and is called the principal trellis. The complementary trellis corresponds to s = 1 and is obtained by adding (0 s) to all the codewords labeling the edges of the principal trellis.

Figure 6 :

 6 Figure6: Implementation of the syndrome approach with a usual channel decoder. ISF stands for inverse syndrome former and computes a representative of the coset with syndrome s.

x 1 x 2 σ 1 1 Figure 7 :

 117 Figure 7: Block diagram (a) and syndrome trellises (b-c) for the rate 1/2 convolutional code H = [5 7]. The states σ 1 (D) σ 2 (D) are defined in the block diagram (a). Two trellis sections are obtained: one for the syndrome value s = 0 (b) and one for s = 1 (c).

Figure 8 :

 8 Figure 8: DSC system for two binary correlated sources using punctured turbo codes.

Figure 10 :

 10 Figure10: Syndrome puncturing of an LDPC code[START_REF] Varodayan | Rate-adaptive codes for distributed source coding[END_REF] and of a turbo code[START_REF] Roumy | Rate-adaptive turbo-syndrome scheme for Slepian-Wolf coding[END_REF]: two rate adaptive schemes. Performance versus the entropy rate H(X|Y ) and comparison with the SW bounds. The 1/2-rate constituent code of the turbo code is defined by its parity check matrix H = (23/33, 35/33). The overall compression rate for both schemes is 1 : 1, and puncturing leads to various compression rates. (a) Comparison of the syndrome punctured LDPC and turbo code for a blocklength of 2046. (b) Performance of the turbo code for an interleaver of size 10 5 .

Figure 11 :

 11 Figure11: Super trellis for the rate 1/2 convolutional code defined by its polynomial parity check matrix H(D) =[5 7]. This trellis is the union of the two trellis sections of Figure7.

Figure 12 :

 12 Figure 12: Splitting the code of Figure 3 into two subcodes: code C 1 defined by G 1 = (110) or H 1 = 110 001 (left); code C 2 defined by G 2 = (101) or H 2 = 010 101 (right).

Figure 14 :

 14 Figure 14: Non-asymmetric decoder: estimation of the error pattern z = x ⊕ y (left); reconstruction of the source sequence x (right).

Figure 15 :

 15 Figure15: Error propagation in the estimation of the source X. The convolutional code is defined by its parity check matrix H =11 15 06 1512 17 and is punctured over a period of four trellis sections in order to get a 2 : 1 compression rate for the source.

Figure 16 :

 16 Figure 16: Rate-adaptive coding/decoding scheme.

  bits /source symbol) R Y (bits/source symbol) p = 0.01, gap = 0.0562 bits p = 0.01, theoretical bound p = 0.05, gap = 0.0907 bits p = 0.05, theoretical bound p = 0.13, gap = 0.0687 bits p = 0.13, theoretical bound

Figure 17 :

 17 Figure 17: Rate points achieved for different parameters p of the binary symmetric correlation channel.

All vectors are line vectors, and T denotes transposition. Moreover, ⊕ denotes the addition over the finite field of order

and + the addition over the real field.

Note that this paper introduces the principle of the parity approach in the general case of nonasymmetric coding.

and secure fingerprint biometrics. These applications are presented in other chapters of this book.


LLACAN Stéphane Robert
email: stephane.robert@cnrs.fr

Sept suffixes causatifs pour

Introduction

Wolof : Niger-Congo, Atlantic, mainly spoken in Senegal (10M speakers, all included) -Rich system of suffixes for verbal derivation (up to 40) -Fine grained distinctions inside categories: 2 applicatives, 3 reciprocals and… 7 causative suffixes in addition to 3 verbs used for periphrastic causatives: -S (causer) is a mere controller, the causee realizes the action: indirect causation -Specificity: the causee can not be explicitly mentioned: omitted causee -Syntactically: no valence increasing since the causee is not mentioned Why to code an omitted causee ?

The causee might be discursively not important or pragmatically not known, e.g. in requests (Nouguier 2000: 188-9):

 indirect causation with omitted causee (possible extension to sociative meaning)

(-loo) CAUS5

Does not apply to stative verbs, only with dynamic verbs (actions) Indirect causation but with an explicit causee (discursive proeminence): constrast ( 6) with ( 5

2. The 'pure' causative suffixes of Wolof 2.1. (-e) CAUS1 and (-al) CAUS2  Difficult to find semantic or syntactic differences but -al fully productive and -e : ± lexicalized cf -Restricted to a handful of verbs ('to go down

							4
					'I had a dress sewed'	(Creissels & Voisin 2008)
							initiates/controls	realizes/undergoes the process
					Syntax: Valence increasing with readjustment of the semantic and syntactic roles
							enfants / the mother had the kids eat
					A continuum with an intermediate type, the sociative causation (Shibatani & Pardeshi 2002):
						direct sociative  indirect causation
			CAUS 1 CAUS 2	-al  -ale -e	Causer's 'agentivity': (physical intervention)	+	±	-
			CAUS 3	-le
			CAUS 4	-lu
			CAUS 5	-loo
			CAUS 6	-antal
			CAUS 7	(stem alternation)+-ali
							', 'to be named', 'to be forbidden'…)
					-In complementary distribution with (-al):
					e.g. génn 'go out': genn-e, *génn-al ; toog 'to sit': toog-al, *toog-e
					 Both express direct causation, with intransitive verbs (stative quality, movement verbs…)
					becoming transitive:
	2.3. (-lu) CAUS4				weex 'to be white', weex-al 'to whiten something' i.e. to make something become white
	Applies only to transitive dynamic verbs, e.g. ñaw 'to sew':	fees 'to be full', fees-al 'to fill in something'  S + agent, O +patient (cf 1b)
	(5) a. Ñaw sew 'I sewed a dress' naa PFT.1SG dress roob	(1)	a. Génn na ci diggu kër go_out PFT.3SG LOC.PROX middle-GEN.SG house 'He/she went out in the yard' (INTR)
	b. Ñaw-lu	naa	roob
	sew-CAUS4 PFT.1SG dress

tax 'to cause', def 'to do', bàyyi 'to leave, abandon' (= only indirect causatives ± intentionality, cf Nougier Voisin 2002) 5 causative suffixes, well studied by Nouguier Voisin (2002) 2 additional suffixes added by S. Robert for the CORTYPO project (cortypo.huma-num.fr)  Obviously related (-l-'morphem', except for CAUS2) but not segmentable in synchrony (fused forms, portmanteau) (for diachronic hypothesis, see Nouguier Voisin 2002) -Typology: Distinction between different semantic types of causatives well known (e.g. Shibatani 1975, Comrie 1976…, see Song 1996 for a review, Dixon 2002) But usually distributed across a few constructions or polyvalent morphemes cf. Chimwi:ni (Bantu G): 5 types of causation but a single suffix (Abasheikh 1978): causative semantics depends on the type of predicate Wolof: 7 causative suffixes (+ 3 periphrastic constructions): Why is Wolof so ?  what kind of distinctions or subcategorizations in Wolof ?  typologically rare types of causatives ? 1. A few definitions  The causative construction e.g. The child fell  I made the child fall  a caused event, addition of a causer (fr. causateur), a causee (fr. causataire) Wolof: causative derivation  Causer in Subject position, Causee in Object position (SVO)  Types of causation -direct causation: le soleil a blanchi (= fait devenir blanc) le coussin -indirect causation: the speaker made the audience laugh -sociative causative: la mère a fait manger les b. Génn-e na guro yu sànkar yépp go_out-CAUS2 PFT.3SG cola_nut LINK be_with_worms CLSy-all 'He/she took out all the cola nuts that had worms' (TRANS) (from Creissels & Voisin 2008)  Extension to joint action or assistive causation (= sociative causation) with animate Objects (2) Toog-al na gan yi sit-CAUS2 PFT.3SG guest DEFy.PROX 'He had the guest seated' = to sit an invitation for the others to seat (joint action) or to provide seats for the guest to sit (assistive causative) CAUS1/2  direct causation, can be extended to joint action 2.2. (-le) CAUS3 May apply to transitive or intransitive verbs but apparently not to stative quality verbs (≠ CAUS1/2) Specific causative meaning, cf (3b) (3) a. Bul wat saaku bi ! wat 'to lift' (TRANS) PROH.1SG lift bag DEFb.PROX 'Ne traîne pas le sac parterre !' b. ... moo koy wat-le gaal gi wat-le (DITRANS) FOC.S.3SG O.3SG-IPFV lift-CAUS3 dugout DEFg.PROX '...c'est elle qui l'aidait-à-tirer la pirogue' (Nouguier 2002: 186) Addition of a new argument (causer) in S position, helping O (causee) to realize the action = (3b) = Joint action: both Causee and Causer participate physically in the caused action (4) = Assisting action: the causer assists/helps the causee but does not perform the action (4) Lekk-le na xale bi eat-CAUS3 PFT.3SG child DEFb.PROX 'Il fait manger l'enfant / il aide l'enfant à manger' (Nouguier 2002: 185) NB. transitive derived verbs  ditransitive, but sometimes no valence increasing: one object (causee or recipient) may be omitted while semantically present, cf (4) no recipient CAUS3  sociative causation only (typologically rare ?), i.e. joint action or assistive ± 2 agents: O cause agentive, causer ± agentive, more than in direct causation

  fenantal ´to digress´  ? fen 'to lie') or in deverbal nouns (e.g mujj-antal B 'finition'/´finishing stage or touch´ from mujj ´to be the last one´) applies mostly to stative intransitive verbs: e.g. set 'to be clean', sett-antal 'to purge s.t. from', suufe 'to be low', suufeental  suufe-antal 'to put down somebody' / 'rabaisser' Problem : -*ant does not exist in synchrony, however visible in other verbal suffixes (reconstruction): -ante (RECP3): prototypical reciprocal; -anti (with stem altern): un peu de foi' < gëm 'croire'....  the causative suffix (-al) alternates with the middle suffix (-u) in -ant-al vs. -ant-u reew 'être impoli', reew-antu 'faire semblant d'être impoli/ faire l'enfant gâté), reew-al 'rendre impoli', reew-antal 'un peu gâter un enfant' Applies mostly to stative quality verbs but sometimes also dynamic verbs (e.g. àgg 'to arrive', àggali 'to lead something to completion' / 'faire arriver à terme, donner le coup de grâce')Close to (-al) for its causative component but express a direct causation for completing/finalizing a process.With (dynamic) transitive verbs, this construction adds a beneficiary for the completed process in a ditransitive construction: e.g. jot 'to get something' / 'atteindre, recevoir' jott-ali 'to fully transmit or report s.t to s.o'/ 'transmettre, passer qq ch à qqn, rendre compte' i.e. 'to cause someone to fully get something'A compound suffixe ? No obvious segmentation: CAUS2 -al (cf causative meaning) or APPLICATIVE -al (cf beneficiary) ?+ directionnel -i (cf teminative value) but problem with stem alternation ?? or reversive (stem altern + -i) but with which meaning ??A remarkable distribution of various types of causatives and causations across different suffixes A remarkable combination of causation with (un)completeness of the process -A dedicated construction for (strictly) assistive sociative construction (-le)  typological rarity ? -A dedicated construction for (indirect) causative with omitted causee (-lu) -A dedicated construction for strictly indirect causative (-loo)

	3. The "complex" causative suffixes of Wolof
		CAUS6 (-antal) and CAUS7 (stem alternation+-ali) are paired forms combining causative
		meaning with an indication about the state of the process
		 'uncompleted' vs. 'completing' causation / causation 'incomplete' vs. 'parachevante'			"correctif" (Diouf 2003) cf. jubanti "redresser qqch qui est courbé" < jub "être droit" (an
							additional causative); -antu : « simulatif » (Diouf 2003), « limitatif » (Church 1981).
							Church (1981: 167) : « limitatif, indiquant un engagement à partiel dans l'action,
	3.1. CAUS 6 (-antal) : the uncompleted causative				l'absence de sérieux » ; Sa valeur est dans certains cas assez proche celle du diminutif -
							adi » :
		-a rare causative suffix (not really productive in derivation) but well attested in lexicalized			beyantu 'faire semblant de / s'amuser à cultiver la terre' < bey 'cultiver la terre'
	verbal forms (e.g -direct causative (as -al) but indicating an uncompleted process : compare (7)b and c a. Xale bii, dafa reew Conclusion (7) causation  direct joint action assistive supervision indirect	(6) gëmantu 'avoir 3.2. CAUS7 (stem final alternation + -ali) : a completing causative Ñaw-loo naa ko roob sew-CAUS5 PFT.1SG O.3SG dress doxantu 'flâner' < dox 'marcher' laalantu 'toucher sans but précis' < laal 'toucher'	)
		kid this, FOC.V.3SG be_impolite CAUS -e	(O animate)			'I had him/her sew a dress' (Creissels & Voisin 2008)
		'this child is is disrespectful/impolite' CAUS -al (O animate)
			CAUS -le			-S (causer) is a mere controller
			omitted causee	CAUS -lu		-O (causee) is the real agent, so generally animate (≠ CAUS2)
		achievement 		CAUS -loo		-Valence increasing
		+ uncompleted CAUS -antal + completing CAUS -ali			-al/-ali :	 a strict indirect causative (no extension)
			(adapted from Nouguier Voisin 2002: 197)	2.6. A first summary fees 'to be full', fees-al 'to fill in s.t.', feccali 'to complete filling s.t.' mat 'être mature, complet', mat-al 'compléter", mottali 'achever ce qui était inachevé'
							saf 'to be tasty', sàp-pali 'to restore the flavour of/to something'
							Agentivity
							Prototypically :
		-baaxantal : a remarkable meaning				O	S
	(8)	Dañuy baax-antal cosaan-u maam yi FOC.V.3PL:IPFV ?-CAUS6 custom ancestor-GEN.SG DEFy:PROX 'ils commémorent la coutume des anciens' / 'they commemorate the ancient custom'	(9)	CAUS 1 -al  -ale CAUS 2 -e (lexicalized) Dogg-ali ko !	direct causative ( joint action if O anim.)	S agentive causer O patient/undergoer causee
		baax 'être bon' ; cf. baax-al 'rendre qqn bon/positif'			CAUS 3 -le die-CAUS7 O.3SG Ferme-lui les yeux !	assistive causative (or joint action)	S ± agentive causer O agentive causee	_	_
		 baax G 'tradition' baax-antal : 'to commemorate something' i.e. 'to make something become a celebrated tradition (baax) to repeat'	(10)	CAUS 4 -lu jekk 'to be all right / 'être convenable bien fait', jekk-ali 'to finish off something'/'achever' = indirect causative (or assistive) with omitted causee S beneficiary/ordering causer to lead something correctly to completion, cf (10) Agentive causee omitted [O recipient] a. Lem na ko ba mu jekk
						CAUS 5 -loo fold PFT.3SG O.3SG until NARR.3SG be_correct indirect causative	S controller causer
							O agentive causee

b. dafa reew-al doom ji FOC.V.3SG be_impolite-CAUS2 child DEFj.PROX 'il a rendu son enfant impoli ' / 'he spoiled his child' lit. 'he made his child impolite' c. dafa reew-antal doom ji FOC.V.3SG be_impolite-CAUS6 child DEFj.PROX 'il a un peu gâté son enfant' i.e. 'l'a rendu un peu mal élevé (mais pas complètement') / 'he spoiled a little bit his child'  indicates an incomplete transformation, slightly affecting the Objet  CAUS6 indicates that the caused event is not a completed process, be it in time (frequentative meaning) or in quality (incomplete transformation), jéem 'to try' jéem-antal 'to train somebody' ('exercer, entraîner qqn') = 'to make s.o. try a little bit' 6 -A compound suffixe ? -antal  ant-+ CAUS2 -al ?

 CAUS7 indicates that a human causer/controller (S) is acting on a causee/patient (O) in order to complete a process or to lead it towards its qualitative endpoint: 'completing' causative, cf: dog 'to die'( 'to cut off'), dogg-ali 'to close the eye of the dead': 'Il l'a plié correctement.'

[START_REF] Diouf | Dictionnaire wolof-français et français-wolof[END_REF]

b. Xaaral ba jekk-ali sa liggéey wait:IMP.SG until be_correct-CAUS7 POSS.2SG work 'Attends d'avoir terminé ton travail'

[START_REF] Diouf | Dictionnaire wolof-français et français-wolof[END_REF]