Simon Malinowski

Hervé Jégou

Christine Guillemot

Synchronization recovery and state model reduction for soft decoding of variable length codes

published or not. The documents may come

Synchronization recovery and state model reduction for soft decoding of variable length codes

I. INTRODUCTION

VLCs are widely used in compression systems due to their high compression efficiency. One drawback of VLCs is their high sensitivity to errors. A single bit error may lead to the de-synchronization of the decoder. Nevertheless, many VLCs exhibit self-synchronization properties. The authors in [START_REF] Ferguson | Self-synchronizing huffman codes[END_REF] show such properties for some binary Huffman codes. The error recovery properties of VLCs have also been studied in [START_REF] Maxted | Error recovery for variables length codes[END_REF], where a method to compute the so-called expected error span E s (i.e. the expected number of source symbols on which a single bit error propagates), has been proposed. The same quantity has been called mean error propagation length (MEPL) in [START_REF] Zhou | Synchronization recovery of variable length codes[END_REF]. The authors in [START_REF] Monaco | Corrections and additions to "error recovery for variable length codes[END_REF] consider the variance of the error propagation length (VEPL) to assess the resilience of a code with hard decoding techniques. In [START_REF] Swaszek | More on the error recovery for variable length codes[END_REF], the method of [START_REF] Maxted | Error recovery for variables length codes[END_REF] is extended to compute the so-called synchronization gain/loss, i.e. the probability that the number of symbols in the transmitted and decoded sequences differ by a given amount ∆S when a single bit error occurs during the transmission. Note that various VLC constructions have also been proposed to improve the self-synchronization properties of the codes [START_REF] Montgomery | Synchronization of binary source codes[END_REF], [START_REF] Titchener | Generalized t-codes: extended constructions algorithm for self-synchronising codes[END_REF], [START_REF] Freiling | Selfsynchronization of huffman codes[END_REF]. The author in [START_REF] Titchener | Generalized t-codes: extended constructions algorithm for self-synchronising codes[END_REF] introduces a method to construct prefix-free self-synchronizing VLCs called T-codes. The synchronization property of these codes is analyzed in [START_REF] Titchener | The synchronisation of variable length codes[END_REF] in terms of the expected synchronization delay.

VLC soft decoding techniques based on MAP (or MMSE) estimators have also been considered to minimize the error rates (or distortion) observed on the decoded sequences. The approaches essentially differ in the optimization metrics as well as in the assumptions made on the source model and on the information available at the decoder. These assumptions lead to different trellis structures on which the estimation or soft-decoding algorithms are run. Two main types of trellises are considered to estimate the sequence of emitted symbols from the received noisy bitstream: the bit-level trellis proposed in [START_REF] Balakirsky | Joint source-channel coding with variable length codes[END_REF] and the bit/symbol trellis. The bit-level trellis leads to low decoding complexity. However, it does not allow the exploitation of extra information, such as the number of emitted symbols. It hence suffers from some suboptimality. If the knowledge of the number of emitted symbols is available at the decoder, the problem is referred to as soft decoding with length constraint and is addressed, e.g., in [START_REF] Murad | Robust transmission of variable-length encoded sources[END_REF] [START_REF] Park | Decoding entropy-coded symbols over noisy channels using discrete hmms[END_REF][13] [START_REF] Kliewer | Iterative joint source-channel decoding of variable-length codes using residual source redundancy[END_REF]. This problem has led to the introduction of the bit/symbol trellis in [START_REF] Bauer | Iterative source-channel decoding based on a trellis representation for variable length codes[END_REF]. This trellis can optimally exploit such constraints, leading to optimal performance in terms of error resilience. Nevertheless, the number of states of the bit/symbol trellis is a quadratic function of the sequence length. The corresponding complexity is actually not tractable for typical sequence lengths. In order to overcome this complexity hurdle, most authors apply suboptimal estimation methods on this optimal state model such as sequential decoding [START_REF] Kliewer | Iterative joint source-channel decoding of variable-length codes using residual source redundancy[END_REF] [16][17].

This paper presents a method to assess the error resilience of VLCs when trellis decoding with length constraint is used at the decoder side. The approach is based on the concept of gain polynomials defined on error state diagrams introduced in [START_REF] Maxted | Error recovery for variables length codes[END_REF] and [START_REF] Swaszek | More on the error recovery for variable length codes[END_REF]. The method introduced in [START_REF] Swaszek | More on the error recovery for variable length codes[END_REF] to compute the synchronization gain/loss is first recalled. This method is then extended to the case of a symbol sequence of length L(S) being sent over a binary symmetrical channel (BSC) of a given crossover probability. The derivation is inspired from the matricial method described in [START_REF] Zhou | Synchronization recovery of variable length codes[END_REF]. It has been shown in [START_REF] Weidmann | Reduced-complexity soft-in-soft-out decoding of variable length codes[END_REF] [START_REF] Thobaben | Robust decoding of variable length encoded markov sources using a three-dimensional trellis[END_REF] that the Markovian property of a source can be easily integrated in the source model by expanding the state model by a constant factor. We thus restrict the analysis to memoryless sources. It is shown that for VLCs, the probability mass function (p.m.f.) of the synchronization gain/loss is a key indicator of the error resilience of such codes when soft decoding with length constraint is applied at the decoder side. The p.m.f. of the gain/loss allows the computation of the probability that the symbol length of the decoded sequence is equal to L(S), i.e. the probability that the decoder resynchronizes in the strictsense (no gain nor loss of symbols during the transmission). This quantity is given by P(∆S = 0). The length constraint is used to discard all decoded sequences which do not satisfy the constraint ∆S = 0. If P (∆S = 0) is high, the number of "de-synchronized" sequences which will be discarded will be high. This results in increasing the likelihood of the correct sequence, hence in decreasing the decoding error rate. The entropy of the p.m.f. of the gain/loss represents the amount of information that the length constraint brings to the decoder. These two quantities (P(∆S = 0) and H(∆S)) are shown to better predict the relative decoding performance of VLCs when soft decoding with a length constraint is used,than the MEPL and VEPL measures (these measures are appropriate when hard decoding is used). Note that, in the following, the term MEPL will be used to refer to the expectation of the error propagation length.

This analysis is then used in Section III to assess the performance of MAP decoding on the aggregated state models proposed in [START_REF] Jegou | Trellis state aggregation for soft decoding of variable length codes[END_REF], for jointly typical source/channel realizations. The aggregated state model is defined by both the internal state of the VLC decoder (i.e., the internal node of the VLC codetree) and the remainder of the Euclidean division of the symbol clock values by a fixed parameter called T . This model aggregates states of the bit/symbol trellis which differs by multiple of T symbol clock instants. The parameter T controls the trade-off between estimation accuracy and decoding complexity. The choice of this parameter has indeed an impact on the quantity of information brought by the length constraint on the corresponding trellis. It is shown that the probability that the VLC decoder does not re-synchronize in a strict sense, as well as the entropy of the constraint, are not significantly altered by aggregating states, provided that the aggregation parameter T is greater than or equal to a threshold. An upper bound of this threshold is derived according to the analysis of Section II. This proves that the performance obtained by running a length-constrained Viterbi decoder on the aggregated trellis closely approaches the performance obtained on the bit/symbol trellis, with a significantly reduced complexity. Finally, it is shown in Section IV that the decoding complexity can be further reduced by considering separate estimations on trellises of smaller dimensions, whose parameters T 1 and T 2 are relatively prime. If the two sequence estimates are not equal, the decoding on a trellis of parameter T 1 × T 2 is then computed. The equivalence in terms of decoding performance between this approach, referred to as combined trellis decoding, and the decoding on a trellis of parameter T 1 × T 2 is proved for the MAP criterion, i.e. for the Viterbi algorithm [START_REF] Viterbi | Error bounds for convolution codes and an asymptotically optimum decoding algorithm[END_REF].

II. LINK BETWEEN VLC SYNCHRONIZATION RECOVERY PROPERTIES AND SOFT DECODING PERFORMANCE WITH A LENGTH CONSTRAINT

Let S = S 1 , ...S t , ...S L(S) be a sequence of L(S) symbols. This sequence is encoded with a VLC C, producing a bitstream X = X 1 , ...X k , ...X L(X) of length L(X). This bitstream is modulated using a binary phase shift keying (BPSK) modulation and is transmitted over an additive white Gaussian noise (AWGN) channel, without any channel protection. The channel is characterized by its signal to noise ratio, denoted E b /N 0 and expressed in decibels (dB). Note that we reserve block capital letters to represent random variables and small letters to represent their corresponding realizations. In this paper, the term polynomial refers to expressions of the form i∈Z a i x i , where x denotes the variable and a i are polynomial coefficients. Hence, we include in this terminology either polynomial series (with an infinite number of non null coefficients) or finite length polynomials (such as ∃N ∈ N | ∀n > N, a -i = a i = 0), both with negative powers.

A. The gain/loss behavior of a variable length code

A method to compute the so-called expected error span E s following a single bit error has been introduced in [START_REF] Maxted | Error recovery for variables length codes[END_REF]. This method relies on an error state diagram which represents the states of the decoder when the encoder is in the root node. Hence, the error state diagram includes the internal states of the decoder, i.e. the internal nodes of the VLC, plus two states which represent the loss of synchronization state n l and the return to synchronization state n s respectively. Therefore, the set of states of the diagram is {n l , n α1 , n α2 , ..., n s }, where the set {α 1 , α 2 , ...} represents the set of prefixes of the VLC. The state n s of the error state diagram corresponds to a return of both encoder and decoder automata to the root node of the code tree. However, this state may not correspond to a strict sense synchronization. In other words, the number of decoded symbols may be different from the number of emitted ones. The branches of the error state diagram represent the transitions between two states of the decoder when a single source symbol has been emitted by the encoder. They are labeled by an indeterminate variable z which corresponds to the encoding of one source symbol. Hence, the gain along each edge is the probability of the transition associated with that edge multiplied by z. In that case, the gain on the diagram from n l to n s (i.e. the transfer function between n l and n s ) is a polynomial of the variable z such that the coefficient of z i is the probability that the considered VLC resynchronizes after exactly i source symbols following the bit error. Evaluating the derivative of the gain polynomial at 1 provides the expected error span E s .

The branch labeling of the error state diagram has been extended in [START_REF] Swaszek | More on the error recovery for variable length codes[END_REF] so that the gain polynomial informs about the difference, caused by a single bit error, between the number of emitted and decoded symbols, after hard decoding of the received bitstream. This quantity, denoted ∆S, is referred to as the gain/loss. In order to evaluate the p.m.f. of the random variable ∆S, a new variable y j is introduced in the branch labeling of the error state diagram. The exponent j represents the number of extra output symbols for each input symbol. Hence, the corresponding gain polynomial G(y, z) is function of both variables y and z. Evaluating this polynomial at z = 1 gives a polynomial in y only. For sake of clarity, we simply denote this polynomial as

G(y) = G(y, z)| z=1 . (1)
The coefficient of y i in the polynomial G(y) gives the probability P(∆S = i) following one bit error. Note that i can be negative if the decoded sequence is longer than the encoded one. In this section, we focus on the behavior of the polynomial G(y). Since the variable z is not necessary, we compute directly the state diagram for z = 1. Let H be the transition matrix corresponding to the error state diagram.

H =      P(n l |n l ) P(n α1 |n l ) • • • P(n s |n l ) P(n l |n α1 ) P(n α1 |n α1 ) • • • P(n s |n α1 ) . . . . . . . . . . . . P(n l |n s ) P(n α1 |n s ) • • • P(n s |n s )      (2)
where P(n αi |n αj ) represents the probability to go to state n αi from state n αj . Let us call h k i,j (y) the element at row i and column j of the matrix H k . Note that h k i,j (1) is the probability to go from state n αi to state n αj in k stages, i.e. after the encoding of k source symbols. The top right elements of the matrices H and H k are respectively denoted h(y) = P(n s |n l )

and h k (y). The gain polynomial G(y) can then be written as

G(y) = k∈N * h k (y). (3)
Hence, the gain polynomial G(y) is obtained as the top right element of the matrix (I -H) -1 , where I denotes the identity matrix of the same dimensions as H. Note that this property holds if (I -H) -1 exists. Let us consider the 5-symbol source and the 16 VLCs used in [START_REF] Zhou | Synchronization recovery of variable length codes[END_REF] to illustrate these concepts. The probability of this source as well as the different codes are reproduced in Table I. These codes have the same mean description length of 2.2 bits per symbols.

Example 1: Let us consider the code C 5 . Its state diagram is depicted in Fig. 1. The transition matrix derived from the previous guidelines, i.e. by setting the variable z to 1 in the extended diagram of [START_REF] Swaszek | More on the error recovery for variable length codes[END_REF], is given by This leads to G(y) = 0.0625y -1 + 0.8352 + 0.1023y, which also means that

H C5 =        0 1
   P(∆S = -1) = 0.1023 P(∆S = 0) = 0.8352 P(∆S = 1) = 0.0625. (4)

B. Extension to the BSC

Let us recall that ∆S corresponds to the gain/loss engendered by a single bit error. We propose here to estimate P(∆S = i) for a sequence of L(S) symbols that has been sent through a BSC of crossover probability p (equals to the bit error rate). Since in this section the VLC decoder is assumed to be a classical hard decoder, the analysis is also valid on an AWGN channel characterized by its signal to noise ratio E b /N 0 by taking p = 1 2 erfc

E b
N0 . For a sequence of L(S) symbols, the bitstream length L(X) lies in the interval of integers I = {L(S) × l m , . . . , L(S) × l M }, where l m and l M respectively denote the lengths of the shortest and longest codewords. Let E denote the random variable corresponding to the number of errors after the hard decoding of the received bitstream Y. For i ∈ Z, the probability P(∆S = i) is given by

P(∆S = i) = e∈N P(∆S = i | E = e)P(E = e). (5)
For e ∈ N, the probability P(E = e) can be expressed as

P(E = e) = k∈I P(E = e|L(X) = k)P(L(X) = k) (6) if e ≤ L(S) × l M (7)
otherwise

P(E = e) = 0, (8)
where the quantities P(E = e|L(X) = k) only depend on the signal to noise ratio and are equal to

P(E = e|L(X) = k) = k e p e (1 -p) i-e if e ≤ k P(E = e|L(X) = k) = 0 if e > k. (9)
For every k ∈ I, the probability P(L(X) = k) is calculated from the source statistics and the code C structure.

To calculate P(∆S = i) according to Eqn. 5, we now need to compute the quantities P(∆S = i | E = e). For that purpose, let us now assume that the decoder has already recovered from previous errors when another error occurs. This assumption requires that the probability that an error occurs when the decoder has not returned to the synchronization state n s is very low. The lower the error span is and the higher E b /N 0 is, the more accurate this approximation is. Under this assumption, the quantity ∆S is independently impacted by multiple errors.

Let us define

G e (y) = (G ⋆ ... ⋆ G e times )(y) = i∈Z a i,e y i , (10)
where ⋆ denotes the convolution product. Note that the polynomial G 1 = G corresponds to the gain polynomial of Eqn. 3. Under the previous assumption, the quantity a i,e equals P(∆S = i|E = e). With Eqn. 8, the resulting gain polynomial for this crossover probability can be expressed as

G(y) = e∈N G e (y) P(E = e), (11)
Let η > 0 be a criterion of negligibility. For a given η, the pseudo-degree d η of the polynomial G is defined as

d η = ∆ min N * d i∈Z-{-d,...,d} gi < η. (15)
The pseudo-degree d η of a polynomial is the degree beyond which the sum of the coefficients of this polynomial are below a given threshold η. = 0.0004578 P(∆S = 3) = 0.0000041 P(∆S ≥ 4) = 0.0000001 [START_REF] Bystrom | Soft source decoding with applications[END_REF] and also lead to

d η = 3.
The simulated values of P(∆S = i) are close to the estimated ones for a large set of E b /N 0 values, which validates the approximation. The pseudo-degrees for η = 10 -6 of the codes introduced in Table I have been computed and are given in Table II.

C. Code selection criteria

Let us consider a MAP estimation run on the bit/symbol trellis, with an additional constraint on the length of the decoded sequence. This length constraint is used to discard all decoded sequences having a number of symbols which differs from the number of transmitted symbols, that is, which does not satisfy the constraint ∆S = 0. On the bit/symbol trellis, the decoder has two kinds of information to help the estimation: the excess rate of the code and the information brougth by the length constraint. The excess rate of a VLC (residual redundancy in the encoded bitstream) is given by the difference between the mean description length (mdl) of the code and the entropy of the source. The information brougth by the length constraint on the bit/symbol trellis is given by the entropy of the p.m.f. of the gain/loss measure (∆S). For the considered set of codes, the excess rate is equal to 0.0781 bits of information and is the same for all codes of Table I.

From the p.m.f. of ∆S the following two quantities can be computed:

• the probability P(∆S = 0) to have a strict sense resynchronization • the entropy H(∆S). If the probability P(∆S = 0) is small, the number of "desynchronized" sequences which will be discarded will be high, then the probability of detecting and correcting errors increases. This results in increasing the likelihood of the correct sequence, hence in decreasing the decoding error rate. As explained below, the entropy H(∆S) measures the amount of information brought by the length constraint on the bit/symbol trellis. To design performance criteria for VLCs, we consider codes having the same mdl so that their performance can be fairly compared. Hence, the values P(∆S = 0) and H(∆S), computed from the p.m.f. of the gain/loss measure, are indicators of the performance of a VLC when soft decoding with length constraint is applied at the decoder side. Table II shows the values of these two quantities for the codes of Table I, together with the MEPL and the VEPL of [START_REF] Zhou | Synchronization recovery of variable length codes[END_REF]. The corresponding decoding performance in terms of the normalized Levenshtein distance (NLD) [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions and reversals[END_REF], BER and frame error rate (FER) obtained with the bit/symbol trellis, for E b /N 0 = 6dB and L(S) = 100, are also given. It can be observed that the code C 10 gives the largest MEPL and VEPL. Hence, one could expect this code to lead to the worst decoding performance. However, this conclusion is valid only when hard decoding is used. When soft decoding with a length constraint is being used, it can be observed that the entropy H(∆S) better predicts the decoding performance, the code C 10 giving the best performance in this case in terms of FER, BER and NLD. Similarly, the code C 5 leads to the worst performance in terms of BER and FER. The same observations can be made for longer sequences (see Table III for L(S) = 500 and L(S) = 1000). The MEPL and VEPL criteria are well-suited for hard decoding. However, the two quantities P(∆S = 0) and H(∆S) are better suited in the case of soft decoding with length contraints.

Simulations have also been performed with a larger source alphabet. The English alphabet together with three Huffman codes considered for this source in [START_REF] Maxted | Error recovery for variables length codes[END_REF] and [START_REF] Swaszek | More on the error recovery for variable length codes[END_REF] has been used. This source and the corresponding codes are given in Table IV. These three codes have the same mean description length (4.1557 bits). Table V gives the MEPL and VEPL values, as well as the quantities P(∆S = 0) and H(∆S), for these codes. It also gives the FER and BER MAP decoding performance of these codes on the bit/symbol trellis. The code C 17 is the worst code in terms of MEPL and VEPL, but the best according to our criteria (P(∆S = 0) and H(∆S)). This is confirmed by the actual FER and BER performance of this code when running the MAP decoder with the length constraint.

III. STATE AGGREGATION

The above analysis is used to assess the conditions for optimality of MAP decoding with length constraint on the aggregated state model described in [START_REF] Jegou | Trellis state aggregation for soft decoding of variable length codes[END_REF]. This model keeps track of the symbol clock values modulo a parameter T instead of the symbol clock values as on the classical bit/symbol trellis. The state aggregation leads to a significantly reduced decoding complexity, as detailled in Section III-B. In this section, it is shown that, from d η (the pseudo-degree of the polynomial representation of ∆S), one can derive the minimal value of T required to have nearly optimum decoding performance (i.e. which closely approaches the performance obtained with the bit/symbol trellis). For these values of T , we show that the amount of information conveyed by the length constraint is not significantly altered by state aggregation.

A. Optimal state model

The sequence of transmitted bits can be modeled as a hidden markov model with states defined as X k , where k represents the bit clock instants, 1 ≤ k ≤ L(X). Let N k denote the random variable corresponding to the internal state of the VLC (i.e. the internal node of the VLC codetree) at the bit clock instant k. For instance, the possible values of N k for the code C 0 = {0, 10, 11} are n ε and n 1 , where n ε represents the root node of the VLC codetree. In the bit-level trellis [START_REF] Balakirsky | Joint source-channel coding with variable length codes[END_REF], the decoder state model is defined by the random variable N k only. The internal states of the automaton associated with a given VLC are defined by the internal nodes of the codetree, as depicted in Fig. 2-a for the code C 0 . The corresponding decoding trellis is given in Fig. 3-a. Let us assume that the number of transmitted symbols is perfectly known on the decoder side. To use this information as a termination constraint in the decoding process, the state model must keep track of the symbol clock (that is of the number of decoded symbols). The optimal state model is defined by the pair of random variables (N k , T k ) [START_REF] Guyader | Joint sourcechannel turbo decoding of entropy coded sources[END_REF] [START_REF] Bauer | Iterative source-channel decoding based on a trellis representation for variable length codes[END_REF], where T k denotes the symbol clock instant corresponding to the bit clock instant k. Since the trellis corresponding to this model is indexed by both the bit and the symbol instants, it is often called the bit/symbol trellis. This trellis is depicted in Fig. 3-b for the code C 0 . The number of states of this model is a quadratic function of the sequence length (equivalently the bitstream length). The resulting computational cost is thus not tractable for typical values of the sequence length L(S).

B. Aggregated State model: a brief description

The aggregated state model proposed in [START_REF] Jegou | Trellis state aggregation for soft decoding of variable length codes[END_REF] is defined by the pair of random variables (N k , M k ), where M k = T k mod T is the remainder of the Euclidean division of T k by T . The corresponding realization of M k is denoted m k . Note that T = 1 and T = L(S) amounts to considering respectively the bit-level trellis and the bit/symbol trellis. The automaton and decoding trellis of parameter T = 2 corresponding to this state model are depicted for the code C 0 in Figs. 2-b and3-c respectively. The transitions which terminate in the state n ε , that is corresponding to the encoding/decoding of a symbol, modify M k as M k = M k-1 +1 mod T . Hence, the transition probabilities on this automaton are given by where the probabilities

P(N k = n k , M k = m k |N k-1 = n k-1 , M k-1 = m k-1 ) =            P(N k = n k |N k-1 = n k-1 ) if n k = n ε and m k = m k-1 P(N k = n k |N k-1 = n k-1 ) if n k = n ε and m k = m k-1 + 1 mod T 0 otherwise ( 18
P(N k = n k |N k-1 = n k-1
) are deduced from the source statistics. Note that the transition probabilities P(N k |N k-1 ) are the ones used in the bit-level trellis.

The proposed state model keeps track of the symbol clock values modulo T during the decoding process. In order to exploit this information, the decoder has to know the value m L(X) = L(S) mod T . This information can be used as a termination constraint, as depicted in Fig. 3. If this value is not given by the syntax elements of the source coding system, it has to be transmitted. The transmission cost of m L(X) is greater than or equal to log 2 (T ) bits. Note that the knowledge of this value has a lower cost than the one of transmitting the exact number of emitted symbols in the bit/symbol trellis. In the following, the quantity m L(X) is assumed to be known by the decoder. The estimation is performed using the Viterbi algorithm [START_REF] Viterbi | Error bounds for convolution codes and an asymptotically optimum decoding algorithm[END_REF], hence minimizing the FER. In the sequel, the error resilience will be measured according to this criterion. For the estimation, the paths which do not satisfy the appropriate boundary constraints, i.e. the paths that do not terminate in states of the form (n ε , m L(X) ), are discarded. The number of states of the trellis of parameter

T satisfies ν T ≤ T × L(X) × Γ, (19)
where Γ represents the number of internal nodes of the code. The inequality in Eqn. 19 results from the fact that some pairs (n k , t k ) are not reachable according to the code structure. Such states are mostly located at the first and last bit clock instants of the trellis. However, for some particular codes, some states are not reachable all along the trellis. For example, for the set of codewords {0, 100, 101, 110, 111}, the states (n ǫ , 2q), q ∈ N are not reachable for any bit clock instants. To approximate the complexity on a trellis of parameter T , the worst case in terms of the number of states is considered, i.e. we assume that

ν T ≈ T × L(X) × Γ, (20)
Hence, as the number of states of the bit-level trellis is equal to L(X) × Γ, the computational cost D T corresponding to the trellis of parameter T can be approximated as

D T ≈ T × D bal , (21)
where D bal denotes the computational cost of the bit-level trellis. This computational cost is approximatively linear in the sequence length and in T .

C. Aggregated state model: analysis

According to the definition of the pseudo-degree (Eqn. 15) of the polynomial G(y), the probability that ∆S belongs to the interval {-d η , . . . , d η } is greater than or equal to 1 -η. This leads to the following property. Property 1: A value of T such that T = d η , and all the more such that T > d η , ensures that the Viterbi algorithm run on the aggregated trellis selects, with at least probability 1 -η, a sequence with the correct number of symbols.

However, this property does not mean that the algorithm will offer similar results as the ones on the bit/symbol trellis. To analyze the respective performance of both models, the amount of information conveyed by the termination constraint in both cases must be quantified. These quantities are respectively given by the entropies of the random variables ∆S mod T and ∆S. They depend on the sequence length and E b /N 0 , which are assumed to be fixed. Here, we show that by setting the aggregation parameter T to T = 2d η + 1, the information brought by the length constraint on the aggregated trellis (H(∆S mod T ) tends towards the one available on the bit/symbol trellis (H(∆S)).

For a trellis of parameter T and following the analysis of Section II-B, the quantity

gT i = ∆ P(∆S mod T = i) (22)
can be computed from the quantities gi as

gT i = j∈Z gjT +i . (23)
The entropy of the termination constraint on a trellis of parameter T is then given by

H(∆S mod T ) = - i∈{0,...,T -1} gT i log 2 gT i (24)
≥ H(∆S)

+ i / ∈{0,...,T -1} gi log 2 gi . ( 25
)
When T = 2d η + 1, (25) can be re-written as

H(∆S mod 2d η + 1) ≥ H(∆S) + i / ∈{-dη,...,dη}
gi log 2 gi .

(26) Let us now assume that η < 1 e . Then the function x → x log(x) decreases on the interval [0, η] and since ∀i / ∈ {-d η , . . . , d η }, gi ≤ η, we have

i / ∈{-dη,...,dη} gi log 2 gi ≥ |{i / ∈ {-d η , . . . , d η }], gi > 0}| η log 2 η, (27)
where the cardinal |{i, gi > 0}| of the set of possible nonzero values of gi is bounded by the bitstream length L(X). Together with L(X) ≥ T , this leads to Hence, for a given η, we have the following lower and upper bounds:

|{i / ∈ {-d η , . . . , d η }, gi > 0}| ≤ L(X) -2 d η -1. (28)
H(∆S)+(L(X)-2 d η -1) η log 2 η ≤ H(∆S mod 2 d η +1) ≤ H(∆S).
(29) These bounds mean that for η small enough, hence for T = 2 d η + 1 sufficiently high, the quantity of information brought by the length constraint on the aggregated trellis of parameter T tends toward the one available on the bit/symbol trellis. The convergence of H(∆S mod T ) is depicted in Fig. 4 for codes of Table I. In this figure, the arrows represent the values of H(∆S) for the considered codes. Note that for C 10 , H(∆S mod T ) has not converged towards H(∆S) yet for T = 10. For the other codes, the limit is reached for T ≤ 10. According to Section II-C, the best codes are those with the highest values of H(∆S). Such codes require a higher value of T to approach the value H(∆S) of the entropy of the termination constraint on the bit/symbol trellis, since the pseudo-degree of these codes is higher. Nevertheless, for the considered set of codes, the values of T leading to the same performance as on the bit/symbol trellis are always lower than L(X). Note that for the code C 13 , H(∆S mod 2) = 0 = H(∆S mod 1). This means that the decoding performance of code C 13 on a trellis of parameter T = 2 is the same as the one on the bit/level trellis (T = 1).

The previous analysis has been validated by simulation, for sequences of L(S) = 100 symbols. For each parameter set (VLC, E b /N 0 and T ), the FER is measured over 10 5 channel realizations. The performance at different values of the parameter T and for the codes C 5 , C 7 , C 10 and C 13 is given These values correspond to the performance obtained on the bit/symbol trellis. Note that these values are obtained for a value of T which is considerably lower than L(S). As predicted, the trellis of parameter T = 2 does not bring any improvement in terms of error resilience for the code C 13 compared to the bit-level trellis. These results validate the criteria described in Section II-C to select good codes in terms of error resilience. Indeed, according to these criteria and the simulation results, the best code among the ones proposed in Table I is the code C 10 and the worst is the code C 5 .

IV. COMBINED TRELLIS DECODING

A. Motivation

In this section, we propose an approach allowing further reduction of the decoding complexity without inducing any suboptimality in terms of decoding performance. The optimality of this approach is proved for the FER criterion. This approach is motivated by the following equivalence

L(S) mod (T 1 × T 2 ) = m ⇔ L(S) mod T 1 = m mod T 1 L(S) mod T 2 = m mod T 2 , (31)
satisfied if T 1 and T 2 are relatively prime. Note that, if T 1 and T 2 are not relatively prime, the converse is not satisfied.

Property 2: Let us assume that T 1 and T 2 are relatively prime and that T 3 = ∆ T 1 × T 2 . Let us denote by Ŝ1 , Ŝ2 and Ŝ3 the estimates of S provided by the Viterbi algorithm run on the trellises of parameters T 1 , T 2 and T 3 respectively. Then, we have

Ŝ1 = Ŝ2 ⇒ Ŝ3 = Ŝ1 = Ŝ2 . ( 32
)
Proof: Let us first emphasize that the probability of a sequence, computed by the Viterbi algorithm on a trellis of parameter T does not depend on T . Let us assume that if two sequences have the same probability, then a subsidiary rule is applied to select one sequence amongst the two. For instance, the lexicographical order can be chosen as a comparison rule. Such a rule ensures that the Viterbi algorithm behavior is deterministic. Let

S T = ∆ {s ′ /L(s ′ ) mod T = L(s) mod T } (33)
be the set of sequences satisfying the termination constraint for the trellis of parameter T . From Eqn. 31, we deduce that if T 3 = T 1 × T 2 with T 1 and T 2 relatively prime, then

S T3 = S T1 ∩ S T2 , (34) hence
, S T3 ⊆ S T1 . (35)
Moreover, since we have assumed that Ŝ1 = Ŝ2 , we get

Ŝ1 ∈ S T3 . (36)
The estimate Ŝ1 provided by the Viterbi algorithm applied on the trellis of parameter T 1 is then such that

Ŝ1 = arg max s ′ ∈ST 1 P(s ′ |X) (37) = arg max s ′ ∈ST 3 P(s ′ |X) (38) = Ŝ3 , (39)
where the subsidiary rule may be used in the selection of the maximum. This concludes the proof. This property means that if a sequence is selected by the trellises of parameters T 1 and T 2 , then this sequence is also selected by the trellis of parameter T 3 .

B. The decoding algorithm

The purpose of the algorithm described in this section is to exploit Property 2. The corresponding approach is referred to as combined trellis decoding. The rationale behind this approach is to use two trellises of parameters T 1 and T 2 instead of the trellis of parameter T = T 1 × T 2 in order to reduce the overall decoding complexity. We will also assume that the greatest common divisor (gcd) of T 1 and T 2 is 1, i.e. that T 1 and T 2 are relatively prime. The decoding of a sequence proceeds as follows:

1) The Viterbi algorithm is applied to both trellises T 1 and T 2 . They respectively provide the estimated sequences Ŝ1 and Ŝ2 .

2) If Ŝ1 = Ŝ2 , the decoded sequence is used as the estimate of the emitted sequence. 3) Else, the Viterbi algorithm is applied to the trellis of parameter T 1 × T 2 . According to Property 2, if the same sequence is selected by both trellises T 1 and T 2 , this sequence is also selected by the trellis of parameter T 1 × T 2 . Hence, the performance of the above 3-step decoding algorithm of parameters T 1 and T 2 is equivalent to the one obtained with a Viterbi decoder operating on the trellis of parameter T 1 × T 2 .

C. Expected computational cost of the proposed algorithm

First, let us recall that if T = 1, the resulting trellis is equivalent to the bit-level trellis. If T is greater than or equal to L(S) -L(X) lM + 1 (hence greater than or equal to L(S)), the trellis is equivalent to the bit/symbol trellis. The intermediate values of T amount to considering trellises whose complexity is lower than the one of the bit/symbol trellis (see Section III-B). The expectation D mtd (T 1 , T 2 ) of the computational cost of the proposed decoding scheme is then given by

D mtd (T 1 , T 2 ) = T 1 D bal + T 2 D bal + ρT 1 T 2 D bal ( 40
)
where ρ = P( Ŝ1 = Ŝ2 ). In the following, D mtd (T 1 , T 2 ) will be denoted D mtd . The proposed method is worthwhile in terms of computational cost if

D mtd < T 1 × T 2 × D bal , i.e. if ρ < ρ * = 1 - T 1 + T 2 T 1 × T 2 . (41)
Therefore, the benefit of the proposed algorithm depends on the probability ρ that the two estimators return the same sequence estimate. The probability ρ decreases when the channel noise and/or the sequence length increases. Fig. 5 illustrates the complexity reduction brought by the combined trellis decoding algorithm for the same decoding performance.

For the considered settings, a lower computational cost is obtained with this approach as long as E b /N 0 is greater than 0.65 dB.

D. Constrained optimization of trellis parameters T 1 and T 2

Let T c be a targeted decoding performance. According to the combined trellis decoding scheme described above, this level of performance can be reached using two trellises of parameters T 1 and T 2 such that T 1 ×T 2 = T c , T 1 and T 2 being relatively prime. Without loss of generality, let us assume that T 2 = T 1 +∆T , and T c = T 1 ×(T 1 +∆T ). Note that parsing the set N * ×N * with the pairs (T 1 , ∆T ) ensures to parse the set of attainable constraints. The probability ρ is a function of T 1 and T 2 , hence a function of T 1 and ∆T . The computational cost D mtd of the combined trellis decoding algorithm of parameters T 1 and T 1 + ∆T is given by D mtd (T 1 , ∆T ) = ρ(T 1 , ∆T )D Tc + D bal (2 T 1 + ∆T ) (42)

The quantity ρ(T 1 , ∆T ) represents the probability that the trellises of parameter T 1 and T 1 +∆T do not provide the same estimate. This quantity can hence be assumed to increase with ∆T . This assumption may not be satisfied for codes having specific synchronisation recovery properties. For example, according to section III, even values of T are not appropriate for the code C 13 . Indeed, for this code, a trellis of parameter T = 2q -1, q ∈ N provides better decoding performance than a trellis of parameter T = 2q, q ∈ N. The previous assumption is not always satisfied for this specific code. Under the assumption that ρ(T 1 , ∆T ) increases with ∆T , we deduce the following property from Eqn. 42.

According to that property, the set of pairs (T 1 , T 2 ) such that T 2 = T 1 + 1 is optimum.

V. CONCLUSION

This paper makes the link between re-synchronisation properties of VLCs and length-constrained MAP estimation techniques of these codes. This analysis is also used to assess conditions for optimality of state aggregation on the bit/symbol trellis widely used for soft decoding of VLC encoded sources. Nearly optimal decoding performance can be achieved with a reduced decoding complexity with respect to the classical bit/symbol trellis. A combined trellis decoding algorithm, further reducing the decoding complexity without inducing suboptimality, is then proposed. The aggregated trellises can easily be coupled with a convolutional code or a turbo-code in an iterative structure, as done in [START_REF] Guyader | Joint sourcechannel turbo decoding of entropy coded sources[END_REF], and [START_REF] Bauer | Symbol by symbol map decoding of variable length codes[END_REF].

Fig. 1 .

 1 Fig. 1. Error state diagram of [5] for the code C 5 . The transition probabilities are denoted next to the branches.

  where only the quantity P(E = e) depends on E b /N 0 . The coefficients gi of G verify gi = e∈N a i,e P(E = e) (12) = e∈N P(∆S = i|E = e)P(E = e)(13)= P(∆S = i).

Example 2 :

 2 Let us determine the pseudo-degree such that η = 10 -6 for the code C 5 , E b /N 0 = 6 dB, and L(S) = 100. The estimates of gi obtained from Eqn. 14 lead to                  P(∆S ≤ -4) = 0.0000002 P(∆S = -3) = 0.0000235 P(∆S = -2) = 0.0013201 P(∆S = -1) = 0.0493389 P(∆S = 0) = 0.9186664 P(∆S = 1) = 0.0301524 P(∆S = 2) = 0.0004930 P(∆S = 3) = 0.0000053 P(∆S ≥ 4) = 0.0000001.

( 16 )

 16 Hence, according to the definition of the pseudo-degree in Eqn.[START_REF] Bauer | Iterative source-channel decoding based on a trellis representation for variable length codes[END_REF], d η = 3. The values of P(∆S = i) obtained by simulation and averaged over 10 7 channel realizations are                    P(∆S ≤ -4) = 0.0000002 P(∆S = -3) = 0.0000207 P(∆S = -2) = 0.0012587 P(∆S = -1) = 0.0500770 P(∆S = 0) = 0.9185508 P(∆S = 1) = 0.0296306 P(∆S = 2)

Fig. 3 .U n c o r r e c t e d 2 Fig. 2 .

 322 Fig. 3. Trellises for the code C 0 : a) bit-level trellis (T = 1), b) bit/symbol trellis and c) trellis of parameter T = 2. The termination constraints are also depicted by circles(here L(S) is assumed to be odd).

U n c o r r e c t eFig. 4 .

 4 Fig. 4. Entropy of ∆S mod T versus T for the codes C 5 , C 7 , C 9 , C 10 and C 13 .

Example 3 :

 3 Let us consider the same parameters as in Example 2 (i.e. code C 5 , d η = 3). From Eqn. 29 we deduce that H(∆S) -H(∆S mod 2 d η + 1) ≤ -(100 l M -5)η log 2 (η) ≤ 0.04900 bits (30)

Fig. 5 .

 5 Fig.5. Computational cost of the combined trellis decoding approach versus E b /N 0 against the computational cost of a single trellis decoding approach for parameters (T 1 = 3, T 2 = 4, T 3 = 12). The corresponding cut-off value of E b /N 0 is also depicted and is obtained for ρ * = 0.417.

Property 3 :

 3 Let T c ∈ N * and R p ⊆ N * × N * be the subset of positive integers which are relatively prime. Then arg min T1,T2∈Rp / T1T2=Tc D mtd = arg min T1,T2∈Rp / T1T2=Tc |T 2 -T 1 |.

TABLE II PSEUDO

 II -DEGREES dη FOR η = 10 -6 , PROPOSED CRITERIA, CRITERIA OF[START_REF] Zhou | Synchronization recovery of variable length codes[END_REF], AND ERROR RESILIENCE PERFORMANCE FOR E b /N 0 = 6 DB, AND L(S) = 100.

	Code dη	P(∆S = 0) H(∆S) MEPL[3] VEPL[3]	NLD	BER	FER
	C1	3	0.9185	0.499	3.89256	34.721 0.00877 0.00193 0.34053
	C2	4	0.9005	0.578	2.02273	2.003 0.00632 0.00191 0.33641
	C3	4	0.8971	0.595	2.06061	2.107 0.00626 0.00192 0.33636
	C4	4	0.8913	0.608	4.07692	27.800 0.00759 0.00177 0.31548
	C5	3	0.9187	0.497	1.71023	1.200 0.00586 0.00194 0.34296
	C6	4	0.8996	0.578	3.54546	18.854 0.00758 0.00182 0.32368
	C7	5	0.7088	1.287	1.55556	0.370 0.00619 0.00154 0.21849
	C8	10	0.7006	1.553	2.34861	2.045 0.00646 0.00134 0.19543
	C9	9	0.6703	1.632	1.95707	1.025 0.00571 0.00123 0.16739
	C10	36	0.6401	2.267	6.18182	36.231 0.00483 0.00074 0.10354
	C11	8	0.8797	0.655	1.85227	2.233 0.00614 0.00183 0.32219
	C12	8	0.8882	0.620	1.71678	1.506 0.00617 0.00187 0.32951
	C13	8	0.8860	0.634	1.79798	1.914 0.00615 0.00182 0.32142
	C14	8	0.8957	0.599	2.03104	2.952 0.00666 0.00186 0.32698
	C15	8	0.8941	0.610	2.20321	4.144 0.00685 0.00189 0.33244
	C16	6	0.9044	0.564	1.98086	2.615 0.00672 0.00193 0.33829

TABLE III PSEUDO

 III

	Code dη	P(∆S = 0)	H(∆S)	BER	F ER
				L(S) = 500
	C5	5	0.67565	1.39229	0.002210 0.90012
	C7	9	0.30597	2.49437	0.002200 0.84090
	C10	40	0.13111	4.38846	0.001687 0.64636
				L(S) = 1000
	C5	7	0.49590	1.91479	0.002290 0.99062
	C7	14	0.19019	3.00963	0.002275 0.98422
	C10	40	0.03215	4.97712	0.001899 0.92838

-DEGREES, PROPOSED CRITERIA AND ERROR RESILIENCE PERFORMANCE FOR E b /N 0 = 6 DB, AND FOR L(S) = 500 AND L(S) = 1000.

TABLE IV SOURCE

 IV AND CODES FOR THE ENGLISH ALPHABET USED IN THIS PAPER.

	ASCII Code Symbol probability	C17[2]	C18[2]	C19[5]
	A	0.08833733	0000	0100	0100
	B	0.01267680	011111	111101	000101
	C	0.02081665	11111	11100	01100
	D	0.04376834	00010	10110	01101
	E	0.14878569	001	000	100
	F	0.02455297	11100	11010	00011
	G	0.01521216	011101	111011	001100
	H	0.05831331	1000	1000	1100
	I	0.05644515	1001	1001	1111
	J	0.00080064	111010101	111111110	001110100
	K	0.00867360	1110100	1111110	0011100
	L	0.04123298	00011	10111	00100
	M	0.02361889	11110	11011	01110
	N	0.06498532	0110	0111	0101
	O	0.07245796	0100	0101	1101
	P	0.02575393	10111	11001	01111
	Q	0.00080064	1110101000 1111111110	0011101010
	R	0.06872164	0101	0110	0000
	S	0.05537763	1010	1010	1110
	T	0.09354149	110	001	101
	U	0.02762209	10110	11000	00101
	V	0.01160928	111011	111110	001111
	W	0.01868161	011100	111010	001101
	X	0.00146784	11101011	11111110	00111011
	Y	0.01521216	011110	111100	000100
	Z	0.00053376	1110101001 1111111111	0011101011

TABLE V PROPOSED CRITERIA

 VCRITERIA

	Code	P(∆S = 0) H(∆S) MEPL[3] VEPL[3]	BER	FER
	C17	0.7312	1.376	5.456	5.868 0.002082 0.53768
	C18	0.8338	0.861	3.863	3.906 0.002094 0.56607
	C19	0.8433	0.844	1.915	1.192 0.002105 0.56900

, CRITERIA OF

[START_REF] Zhou | Synchronization recovery of variable length codes[END_REF]

AND DECODING PERFORMANCE OF THE ENGLISH ALPHABET CODES ON THE BIT/SYMBOL TRELLIS FOR E b /N 0 = 6 DB, AND L(S) = 100.

TABLE VI FER

 VI FOR SOFT DECODING (VITERBI) WITH DIFFERENT VALUES OF THE AGGREGATION PARAMETER T .

	E b /N0	3	4	5	6	7
				Code C5
	T = 1	0.99120 0.92330	0.70464	0.38774 0.14558
	T = 2	0.98805 0.90368	0.66193	0.34633 0.12452
	T = 3	0.98698 0.89901	0.65527	0.34313 0.12388
	T = 4	0.98665 0.89795	0.65457	0.34298	0.12386
	T = 5	0.98652 0.89782	0.65449	0.34296
	T = 10	0.98651	0.89780	0.65448
	bit/symb.(T = 100) 0.98651 0.89780	0.65448	0.34296 0.12386
				Code C7
	T = 1	0.99182 0.92604	0.71405	0.39372 0.14885
	T = 2	0.98634 0.88506	0.59864	0.25742 0.06997
	T = 3	0.98247 0.86379	0.55406	0.22571 0.06152
	T = 4	0.98005 0.85387	0.53964	0.21947 0.06059
	T = 5	0.97893 0.84960	0.53581	0.21866	0.06057
	T = 10	0.97773	0.84731	0.53468	0.21849
	T = 20	0.97772
	bit/symb.(T = 100) 0.97772 0.84731	0.53468	0.21849 0.06057
				Code C10
	T = 1	0.97993 0.87316	0.61783	0.31353 0.11390
	T = 2	0.96917 0.82122	0.51758	0.22232 0.06832
	T = 3	0.96092 0.78516	0.46126	0.18023 0.05207
	T = 4	0.95331 0.75512	0.41127	0.14437 0.03718
	T = 5	0.94755 0.73502	0.38403	0.12851 0.03226
	T = 10	0.93238 0.68744	0.33174	0.10496 0.02631
	T = 20	0.92801 0.67825	0.32560	0.10354	0.02610
	T = 30	0.92791	0.67811	0.32558
	bit/symb.(T = 100) 0.92791 0.67811	0.32558	0.10354 0.02610
				Code C13
	T = 1	0.98973 0.91752	0.69351	0.38031 0.14431
	T = 2	0.98973 0.91752	0.69351	0.38031 0.14431
	T = 3	0.98369 0.88547	0.62816	0.32182 0.11644
	T = 4	0.98552 0.89259	0.63858	0.32711 0.11762
	T = 5	0.98286 0.88356	0.62642	0.32142	0.11638
	T = 10	0.98286 0.88356	0.62642
	T = 20	0.98277	0.88348	0.62638
	bit/symb.(T = 100) 0.98277 0.88348	0.62638	0.32142 0.11638
	in

Table VI .

 VI In this table, the best decoding performance for each code, at different values of E b /N 0 is written in italics.