Amadou Diallo
email: amadou.diallo@lss.supelec.frkieffer@lss.supelec.fr

Claudio Weidmann
email: claudio.weidmann@ieee.org

Michel Kieffer

Optimizing the Free Distance of Error-Correcting Variable-Length Codes

This paper considers the optimization of Error-Correcting Variable-Length Codes (EC-VLC), which are a class of joint-source channel codes. The aim is to find a prefix-free codebook with the largest possible free distance for a given set of codeword lengths, ℓ = (ℓ1, ℓ2, . . . , ℓM ). The proposed approach consists in ordering all possible codebooks associated to ℓ on a tree, and then to apply an efficient branch-and-prune algorithm to find a codebook with maximal free distance. Three methods for building the tree of codebooks are presented and their efficiency is compared.

I. INTRODUCTION

The transmission of multimedia contents over an error-prone channel with scarce bandwidth usually requires lossless or lossy compression of the content to remove redundancy. The introduction of structured redundancy via a channel code is also required to improve the robustness of the compressed stream to transmission errors, which are unavoidable when considering transmission over a wireless channel. This scheme is well known as separated (tandem) scheme and is motivated by Shannon's separation principle [START_REF] Shannon | A mathematical theory of communication[END_REF], [START_REF] Cover | Elements of Information Theory[END_REF], which states that source and channel coding may be optimized separately, without loss in optimality compared to a joint design. Nevertheless, this result has been obtained under the hypothesis of a stationary channel, with well-known characteristics at the transmitter and receiver, which is seldom the case in wireless communication systems.

These limitations have motivated the development of joint source-channel (JSC) coding techniques, which aim at designing low-complexity codes simultaneously providing data compression and error correction capabilities. The hope is to get joint codes outperforming separate codes when the length of the codes is constrained, see [START_REF] Zhong | On the joint source-channel coding error exponent for discrete memoryless systems[END_REF].

Compression efficiency is measured by the ratio of the average code length to the source entropy [START_REF] Cover | Elements of Information Theory[END_REF], while the errorcorrection performance may be predicted with an union bound MMSP '10, October 4-6, 2010, Saint-Malo, France. 978-1-4244-8112-5/10/$26.00 c 2010 IEEE using the distance properties of the code, i.e., its free distance and distance spectrum, see [START_REF] Viterbi | Principles of Digital Communication and Coding[END_REF].

JSC coding using error-correcting arithmetic coding (EC-AC) was introduced in [START_REF] Boyd | Integrating error detection into arithmetic coding[END_REF]. First techniques for optimizing the free distance of EC-AC are presented in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF], whereas a global optimization of the free distance using a tree data structure and an efficient branch-and-prune algorithm is reported in [START_REF] Diallo | Optimizing the search of finite-state joint source-channel codes based on arithmetic coding[END_REF]. The present work aims to apply the ideas of [START_REF] Diallo | Optimizing the search of finite-state joint source-channel codes based on arithmetic coding[END_REF] to the optimization of error-correcting variable-length codes (EC-VLC).

Early work on JSC coding using EC-VLCs includes [START_REF] Bernard | Some combinatorial results on variablelength error-correcting codes[END_REF]. In [START_REF] Buttigieg | Variable-length error correcting codes[END_REF], two methods of constructing EC-VLCs with a desired free distance are proposed, namely the "code anti-code" construction and a heuristic construction algorithm. The main problem of these methods is that the obtained codeword lengths are not matched to the source statistics. In addition, if the smallest codeword length is less than the desired free distance, then no EC-VLC is found.

In this paper, we propose an alternative approach for building EC-VLCs with large free distance. For a given set of codeword lengths, ℓ = (ℓ 1 , ℓ 2 , . . . , ℓ M ), which satisfies Kraft's inequality M i=1 2 -ℓ1 ≤ 1, and where we assume w.l.o.g. ℓ i ≤ ℓ i+1 , the proposed algorithms aim to design a prefixfree codebook with maximal free distance.

Our approach consists in ordering all possible codebooks associated to ℓ in a tree such that leaves correspond to EC-VLC codebooks, and (internal) parent nodes correspond to partially defined codebooks, from which child nodes may be obtained by specific rules. By construction, the free distance of a parent node will be an upper bound on the free distances of its child nodes, so that we may apply an efficient branchand-prune algorithm to explore only a part of the tree, thus reducing the time needed to find the best EC-VLC [START_REF] Diallo | Optimizing the search of finite-state joint source-channel codes based on arithmetic coding[END_REF]. Three methods to structure the search tree are proposed. The first method, construction by codewords, adds one codeword at time to a parent node to obtain a child node. It is described in Section III-B. The second method, construction by bit planes, is described in Section III-C. It successively determines bitplanes, i.e., chooses the first bits of all codewords, then the second bits, and so on. The third method separates the structure of a prefix-free code tree from the actual labeling with 0 and 1, by first enumerating canonical trees representing tree isomorphism classes, see Section III-D.

Before detailing these construction methods, Section II details some properties of EC-VLCs and recalls the basis of the tools used to compute the free distance. Experimental results are provided in Section IV, before drawing some conclusions.

II. COMPUTING THE FREE DISTANCE OF AN EC-VLC

In this section, we briefly recall EC-VLCs and show how their free distance can be computed. Consider a memoryless source X with alphabet X = {a 1 , a 2 , . . . , a M } and associated probabilities p = (p 1 , p 2 , . . . , p M ). To each symbol a i in X , one associates a codeword c i in a set of codewords

C = {c 1 , c 2 , . . . , c M }. The length in bits of c i is ℓ i , i = 1, . . . , M . The codebook C is prefix-free iff the codeword lengths ℓ = (ℓ 1 , ℓ 2 , . . . , ℓ M ) satisfy Kraft's inequality M i=1 2 -ℓ1 ≤ 1, (1)
see [START_REF] Cover | Elements of Information Theory[END_REF]. Henceforth we assume (1) is satisfied and call ℓ a Kraft vector.

The performance of an EC-VLC is determined by its redundancy and its error correcting capability. The redundancy R c is the difference between the average codeword length ℓ av = M i=1 p i ℓ i and the source entropy

H c = - M i=1 p i log 2 p i . Thus R c = ℓ av -H c = M i=1 p i ℓ i + M i=1 p i log 2 p i . (2)
The error correcting capability is primarily characterized by the free distance d free (a finer characterization is possible through the distance spectrum). To evaluate the distance properties of an EC-VLC, a graphical representation of the code is better suited than a list of codewords. The code C can be represented as a directed graph Γ(S, T ), where S is a set of states (vertices) and T is a set of transitions (directed edges). Each transition is labeled with an input symbol in X and a sequence of output bits. Γ is also called a finite-state encoder (FSE). In the simple case of an EC-VLC, S contains a single state s 0 , from/to which all transitions leave/lead, so T has M transitions associated to the elements of X . Each transition u i has an input label I(u i ) = a i , an output label O(u i ) = c i and an associated probability P (u i ) = p i . Hence

T = {u i = a i /c i : 1 i M } . (3)
Fig. 1(a) shows the FSE associated to a source X with alphabet

X 3 = {a 1 = a, a 2 = b, a 3 = c} encoded using the codebook C 3 = {c 1 = 0, c 2 = 10, c 3 = 111}.
A better-suited representation of C for distance evaluation is the bit-clock FSE (B-FSE) in which each transition is labeled with exactly one output bit and may have an empty input label. Details on how B-FSE can be obtained from the FSE are presented in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF]. Let σ(u) be the originating state of some transition u ∈ T and τ (u) its target state.

A path u = (u 1 • u 2 • • • • • u k ) ∈ T k on the graph is a concatenation of transitions that satisfy σ(u i+1 ) = τ (u i ) for 1
i < k (this corresponds to a walk of length k on the encoder graph). By extension, we define σ(u) = σ(u 1 ) and τ (u) = τ (u k ), as well as I(u) and O(u), which are the concatenations of the input, respectively output, labels of u. The probability of a path is

P (u) = k i=1 P (u i ).
Finally, ℓ(x) is the length (in symbols or bits) of the sequence x.

The Hamming distance d H between two equal-length sequences x, y is equal to the Hamming weight w H , i.e., the number of non-zero entries, of their elementwise difference,

d H (x, y) = w H (x -y). If two paths (u 1 , u 2 ) ∈ T k1 × T k2 are such that ℓ(O(u 1 )) = ℓ(O(u 2 )), then we will write d H (u 1 , u 2 ) = d H (O(u 1 ), O(u 2 )).
Definition 1: Let P be the set of all pairs of paths in T k1 × T k2 1 k1,k2<∞ diverging from s 0 and converging for the first time in s 0 with the same length of output labels. Then d free is the minimum Hamming distance in P,

d free = min (u1,u2)∈P d H (u 1 , u 2 ) . ( 4
)
Definition 2: The distance spectrum [START_REF] Viterbi | Convolutional codes and their performance in communication systems[END_REF] in the code domain can be represented with a generating function

G (D) = ∞ d=dfree A d D d , (5)
where A d is the average number of pairs of paths in P with Hamming distance d. In [START_REF] Buttigieg | Variable-length error correcting codes[END_REF], A d is defined as :

A d = (u1,u2)∈P d H (u 1 ,u 2 )=d P (u 1 ) (6)
In recent work [START_REF] Diallo | Efficient computation and optimization of the free distance of variable-length finite-state joint source-channel codes[END_REF], we introduced a Pairwise Distance Graph (PDG), which is a modified and reduced product graph of the B-FSE and tracks the Hamming distances in P. This PDG is defined such that the free distance can be found by applying Dijkstra's algorithm [START_REF] Gondran | Graphs and algorithms[END_REF].

The PDG is obtained as follows. Let S b = {s i : 0 i < M b } be the set of states of the B-FSE. The product graph associated to

Γ b (S b , T b ) is the directed graph Γ 2 b (S b × S b , T b × T b ) with states s i,j defined as s i,j = (s i , s j ) : 0 i j < M b . (7)
For any pair of transitions (u, v) in the original graph, Γ 2 b contains a directed edge e with e = (u, v),

(e) = s σ(u),σ(v) and τ (e) = s τ (u),τ (v) . (8) σ
The weight of the edge e, w H (e) is defined as the Hamming distance between the outputs of the two transitions u and v,

w H (e) = d H (u, v) . (10)
A directed path e in Γ 2 b from the state s i,j to the state s m,n , is a sequence of edges e = (e

1 • e 2 • • • • • e N ) such that σ(e µ+1 ) = τ (e µ ) for 1 µ < N . The weight of this directed path, w H (e) is w H (e) = N µ=1 w H (e µ ). (11)
Form two sets of states, S div and S conv , in the product graph. S div is the set of states of Γ 2 b in which the outgoing edges consist of pairs of diverging transitions in T 2 b having the same originating state in S b and S conv is the set of states of Γ 2 b in which the incoming edges consist of pairs of distinct transitions in T 2 b converging in the same target state in S b . By merging the states in S div into a single state s in and S conv into a single state s out we obtain the PDG. Finding d free with this PDG is equivalent to finding a directed path from s in to s out with minimal weight. This is known as the shortest weighted path problem in graph theory and can be solved efficiently using Dijkstra's algorithm [START_REF] Gondran | Graphs and algorithms[END_REF], since all weights are non-negative. The PDG derived from the B-FSE in Fig. 1(b) is represented in Fig. 2.

S div = s i,i : ∃ u = v ∈ T 2 b and σ(u) = σ (v) = s i , (12) S conv = s i,i : ∃ u = v ∈ T 2 b and τ (u) = τ (v) = s i . (13)
The code optimization using the search tree relies on bounds on the free distance of partially defined codebooks.

Definition 3: An EC-VLC is an incomplete codebook (IC) if some codewords or parts of codewords are not determined. For X 3 , two examples are C 1 = {0, 10, xxx} and C 1 = {0, 1x, 1xx}, where x stands for an undetermined bit. A complete codebook (CC) is an EC-VLC in which all codewords are determined. {0, 10, 110} is an example for X 3 .

Definition 4: An incomplete (complete) codebook C 1 is derived from an IC C 0 (denoted C 0 ⊂ C 1 ) if it is obtained by specifying some (all) undetermined bits in C 0 .

If two (incomplete) codebooks C 0 and C 1 satisfy C 0 ⊂ C 1 , then upper and lower bounds on the free distance of C 1 can be obtained directly from C 0 . For this end, the PDG of C 0 is constructed. To get an upper or a lower bound, the weights of the transitions which contain an undetermined bit (x) are replaced by 1 or 0, respectively, and then applying Dijkstra's algorithm.

III. STRUCTURING THE SEARCH SPACE

A. Trees of EC-VLCs

The approach in this work is to arrange all EC-VLCs for a given Kraft vector ℓ = (ℓ 1 , ℓ 2 , . . . , ℓ M ) in a tree data structure, such that every leaf corresponds to a specific EC-VLC codebook, and (internal) parent nodes correspond to partially defined codebooks, from which children nodes (codebooks) may be obtained by specific rules (to be described). This tree data structure should not be mistaken with the tree representing a prefix-free VLC. Then we explore this tree using an efficient branch-and-prune algorithm to find one of the EC-VLCs with the largest free distance. The key to efficient pruning is the availability of an upper bound on the free distance of partial codebooks that is monotonically nonincreasing when traversing the tree from the root towards the leaves. At each step of the algorithm, a list of nodes to be explored is sorted according to the free distance bound and the node with the largest upper bound is explored first. Thus partial codebooks leading to potentially large free distance are examined first. The pruning efficiency can be further improved by using a lower bound on the free distance as a secondary sorting criterion, i.e., for equal upper bound, the partial codebook with the largest lower bound will be extended first (the sorting criteria should not be inverted, since upper bounds turned out to be much more discriminating for partial codebooks). The same approach has been successfully used for the optimization of error-correcting arithmetic coding [START_REF] Diallo | Optimizing the search of finite-state joint source-channel codes based on arithmetic coding[END_REF].

For a given Kraft vector, there is a total of 2 M i=1 ℓi codebooks, including such that are not uniquely decodable.

Here, we will only consider prefix-free codebooks and additionally use symmetry properties to discard some codebooks known to have that same free distance than codebooks already considered. Next we outline three methods for structuring trees of EC-VLCs, i.e., for creating hierarchies of partial codebooks.

B. Construction by codewords

A straightforward method to structure the tree of EC-VLCs is to add one codeword at a time, starting from an empty codebook at the tree root, such that child nodes inherit the partial codebook from their parent node and augment it by one codeword. Thus the tree will have M levels.

Let us first introduce some notations. For any x ∈ N and ℓ ∈ N such that ℓ ≥ ⌈log 2 (x + 1)⌉, B ℓ (x) is the binary representation of x using ℓ bits. For instance, B 3 (1) = 001. Consider some x, ℓ ≥ ⌈log 2 (x + 1)⌉ as just defined, and A, a prefix-free codebook. We define by pref(A, x, ℓ) the function which is zero if A ∪ {B ℓ (x)} is a prefix-free codebook, and one otherwise. For example, A = {1, 01}. If x = 1 and ℓ = 3, A ∪ {B ℓ (x)} = {1, 01, 001}, then pref(A, 1, 3) = 0. If x = 3 and ℓ = 3, then A ∪ {B ℓ (x)} = {1, 01, 011} is not prefix, thus pref(A, 3, 3) = 1. For any ℓ ∈ N, the set V A,ℓ contains all integers x ∈ N which satisfy pref(A, x, ℓ) = 0:

V A,ℓ = {x ∈ N 0 : pref(A, x, ℓ) = 0} (14)
Finally, v j A,ℓ is the jth element of V A,ℓ .

ℓ1 ℓ2 A1 A2 Aν+1 A1,1 A1,2 A 1,λ 0 1 ν v 1 A 1 ,ℓ 2 v 2 A 1 ,ℓ 2 v λ A 1 ,ℓ 2 B ℓ 1 (0) B ℓ 1 (0) B ℓ 1 (1)
B ℓ 1 (1)

B ℓ 1 (ν) B ℓ 1 (ν) B ℓ 2 (v 1 A 1 ,ℓ 2 ) B ℓ 2 (v 2 A 1 ,ℓ 2 ) B ℓ 2 (v λ A 1 ,ℓ 2 )
Fig. 3. Tree of EC-VLCs for the Kraft vector (ℓ 1 , ℓ 2 , . . . , ℓ M ) Fig. 3 shows how all possible EC-VLCs corresponding to a Kraft vector can be ordered in a tree data structure. Since ℓ 1 is the smallest length, the tree is initialized with 2 ℓ1 codebooks which consist of a single codeword B ℓ1 (x) of length ℓ 1 bits. These binary representations are shown in Fig. 3 by B ℓ1 (0) to B ℓ1 (ν), where ν = 2 ℓ1 -1. The obtained codebooks are named A 1 to A ν+1 . Then, each codebook A k , 1 k ν + 1, is extended with different possible binary sequences B ℓ2 (v j A k ,ℓ2 ). In Fig. 3, for example, we suppose that V A1,ℓ2 has λ elements. Then, there are λ possibilities to extend the codebook A 1 , leading to λ new different codebooks denoted by A 1,1 to A 1,λ . Then the obtained new codebooks are extended with codewords with length ℓ 2 and so on, until the codewords of length ℓ M are added. Hence, all EC-VLCs corresponding to the Kraft vector ℓ are obtained as the leaves of the final tree. Fig. 4 gives an example of a tree of EC-VLCs corresponding to the Kraft vector ℓ = (1, 2, 3).

Inverting all bits of a EC-VLC does not change its distance properties. This symmetry property helps reducing the complexity of the branch-and-prune search and divide by two the time needed to find the best EC-VLC. To use this property, one can initialize the tree of EC-VLCs with B ℓ1 (0) to B ℓ1 ( ν+1 2 -1). In Fig. 4, only one part of the tree stemming from A 1 = {0} or A 2 = {1} is needed to find the best free distance.

Another useful symmetry property is that if the lengths ℓ i and ℓ i+1 are equal, exchanging the codewords i and i+1 does not change the average distance properties of the corresponding EC-VLC. Hence we can impose a lexicographic order in the construction of the codebooks. This may substantially reduce the time needed to find the best EC-VLCs. Instead of successively adding codewords, one may build a codebook and thus obtain a tree of EC-VLCs by successively determining bitplanes, i.e., by choosing the first bit for all codewords, then choosing the second bit (where present), and so on. In doing this, one must make sure that the suffixes of the codewords with a common prefix satisfy Kraft's inequality for the overall code to remain prefix-free. If the codewords for i ∈ I have a common prefix of length ℓ, then the condition is i∈I 2 ℓ-ℓi 1. Fig. 5 shows an example of generating a tree of EC-VLCs by bitplanes. In this figure, the codewords of each EC-VLC are ordered vertically. The tree is initialized with all possible combinations of the first bit of each codeword (by taking care that the EC-VLC remains prefix-free). The symbol x represents the indeterminate bits of each codeword at a given time. Then the tree is explored by adding all possible combinations of the next bits. At each step, we check if the suffixes of codewords having the same prefix satisfy Kraft's inequality.

2 3 0 1 A 1 A 2 A 1, 1 A 1, 2 A 2, 1 A 2, 2 A 1, 1, 1 A 1, 1, 2 A 1, 2, 1 A 1, 2, 2 A 2, 1, 1 A 2, 1, 2 A 2, 2, 1 A 2, 2, 2

C. Construction by bitplanes

A 1 A 2 A 1, 1 A 1, 2 A 2, 1 A 2, 2 A 1, 1, 1 A 1, 1, 2 A 1, 2, 1 A 1, 2, 2 A 2, 1, 1 A 2, 1, 2 A 2, 2, 1 A 2, 2

D. Construction using canonical code trees

Any prefix-free EC-VLC can be represented by a labeled binary code tree with leaves mapped to the M source letters, such that the codeword for a letter can be read off as the concatenation of the (binary) labels from the root to the corresponding leaf. Clearly, if two codewords have a common prefix this will affect the distance between sequences starting with those words, regardless of the labels on this prefix. It can be seen that the structure of the unlabeled code tree already gives some information about the code, which can be used to derive upper and lower bounds on the free distance. To exploit this fact, we group the code trees into isomorphism (equivalence) classes, which can be arranged on a search tree (not to be confused with a code tree). Each isomorphism class can then be explored in turn using variants of the two methods outlined above.

Definition 5: Two binary trees are isomorphic if they can be transformed into each other by transposing (flipping) the children of internal nodes, including the root (i.e. all nodes stay at the same level, only their horizontal position changes, assuming the tree is drawn top-down from the root).

Fig. 6 shows an example of two isomorphic trees, while Fig. 7 shows an example of two non-isomorphic trees. An isomorphism class can be represented by an appropriately defined canonical tree, so the main problem becomes that of enumerating all canonical trees having a given Kraft vector ℓ. Such enumerations are classic problems in graph isomorphism; however, to the best of our knowledge, no algorithm is directly (and efficiently) applicable to the case when a Kraft vector is given. Thus we outline one below.

Let T a binary tree, left(T ) its left subtree, right(T ) its right subtree (for compactness of notation, we identify the tree with its root; left and right outgoing edges may be thought as labeled 0 and 1, respectively). The function ℓ * (T ) yields the Kraft vector in non-increasing order. For example, say T has ℓ(T ) = [START_REF] Shannon | A mathematical theory of communication[END_REF][START_REF] Zhong | On the joint source-channel coding error exponent for discrete memoryless systems[END_REF][START_REF] Zhong | On the joint source-channel coding error exponent for discrete memoryless systems[END_REF][START_REF] Cover | Elements of Information Theory[END_REF]. Then ℓ * (T ) = (3, 3, 2, 1). Kraft(ℓ * (T )) = Kraft(ℓ(T )) = M i=1 2 -ℓi is the Kraft sum. For example Kraft((2, 1)) = 0.75, Kraft((0)) = 1, where (0) stands for a single leaf node.

Define the order ≺ as follows:

T 1 ≺ T 2 iff ℓ * (T 1 ) ≺ lex ℓ * (T 2), (15)
where ≺ lex is the lexicographic order on integer vectors. E.g.

(1) ≺ lex (1), (3) ≺ lex (3, 2, 2), (0) ≺ lex [START_REF] Shannon | A mathematical theory of communication[END_REF], where (0) stands for a single-node tree, and (∅) ≺ lex (0), where (∅) stands for no tree, i.e. empty branch, which is "smaller" than anything. Definition 6: A binary tree is canonical if it satisfies left(T i ) ≺ right(T i ) at all its internal nodes T i (i.e. recursively from the root down). canonical tree may be represented by traversing it in any well-defined order that visits each internal node T i once (preorder, inorder, postorder) and listing (ℓ * (left(T i )), ℓ * (right(T i ))).

To obtain a list of all canonical trees, start with the ordered Kraft vector ℓ * and split ℓ * -1 (componentwise subtraction as in Matlab, since we go one level down, we have to subtract one from the lengths) into two parts ℓ * 1 , ℓ * 2 (which are again ordered) such that ℓ * 1 ≺ lex ℓ * 2 and Kraft(ℓ * i ) 1 (i = 1, 2) with one hitch: ℓ * 1 may be empty (no leaf), so we define Kraft((∅)) = 1. Repeat recursively for ℓ * 1 (the left subtree) and ℓ * 2 (right subtree). For example, consider the Kraft vector ℓ = (3, 2, 4). Fig. 8 shows how canonical trees may be obtained from ℓ. We have ℓ * -1 = (3, 2, 1). At the first level, represented by the node R, we have four possible choices for (ℓ

[{1},{3,2}] [{},{3,2,1}] [{2},{3,1}] [{2,1},{3}] [ ] [ ],[ ] {}{0} {}{2,1} [ ] [ ] [ ] {}{0} {1}{2} , [ ] [ ] [ ] {} {0}{1} , R [ ] [ ] [ ] {} {}{0} , [ ] [ ] [ ] {} {} ,
* 1 , ℓ * 2 ): (ℓ * 1 = (∅), ℓ * 2 = (3, 2, 1)), (ℓ * 1 = (1), ℓ * 2 = (3, 2)), (ℓ * 1 = (2), ℓ * 2 = (3, 1)) and (ℓ * 1 = (2, 1), ℓ * 2 = (3)).
Each choice leads to one or more possible canonical trees. At the second level, we have several ways to split ℓ * 1 -1 and ℓ * 2 -1 for the pair (ℓ * 1 = (1), ℓ * 2 = (3, 2)). We repeat this process for all internal nodes. This leads to the first branch on the left of Fig. 8 which is the first obtained canonical tree, represented by Fig. 6 (a).

As mentioned above, the structure of the (canonical) code tree allows to already compute bounds on the free distance. For example, the tree in Fig. 7 (a) contains two codewords of length three, having two common prefix bits. Hence the free distance of any code derived from this tree will be the upper bounded by one. Algorithmically, this can be accomplished by labeling the canonical tree with special labels. Start by numbering the internal nodes. Then, label the left branch leaving node i with "L i " and the right branch with "R i ." Now, when constructing the PDG for bounding d free , we may exploit the knowledge that d H (L i , R j ) = 1 if i = j, while for all other distances, we insert either 0 or 1, depending on the type of bound (lower, upper) we want to compute.

For a given Kraft vector ℓ, we first list all canonical trees and compute an upper bound on the free distance for each tree (this may also be done for partially known trees). The trees with the largest upper bound will then be explored first, using variations of the methods defined in Sections III-B and III-C.

IV. EXPERIMENTAL RESULTS

Experiments were run to display the time savings over an exhaustive search gained by applying the branch-and-prune algorithm on a search tree. The results shown in Table I are for the Kraft vector ℓ = [START_REF] Zhong | On the joint source-channel coding error exponent for discrete memoryless systems[END_REF][START_REF] Viterbi | Principles of Digital Communication and Coding[END_REF][START_REF] Boyd | Integrating error detection into arithmetic coding[END_REF][START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF], for which the maximal free distance is d free = 4. The three methods for constructing this tree of EC-VLCs described in Sections III-B (by codeword), III-C (by bitplane) and III-D (using canonical trees) are compared. The row "# VLCs" shows the number of intermediate EC-VLCs that were examined by the algorithm. Clearly, the branch-and-prune algorithm is a promising method to find a code with maximal d free for a given Kraft vector.

The main benchmark is the number of intermediate EC-VLCs that need to be examined, while the execution times are only partially comparable, due to implementation differences. Indeed the complexity of computing (a bound on) d free is the number of states in the pairwise distance graph (PDG). In our implementation, when bounding d free of intermediate EC-VLCs using bitplanes or canonical trees, the PDG is static and has maximal number of states, whereas in the approach by codewords, this number of states is dynamic and can be as small as two. The rather disappointing performance of the canonical trees method has two origins: on one hand, for simplicity we chose to label the trees one bit at a time (i.e. neither by codewords, nor by bitplanes), which likely increases the number of trees that need to be examined. On the other, listing all canonical trees on the first level of the (branch-andprune) optimization tree is suboptimal, because it does not allow to prune incomplete canonical trees. Other experiments showed that the bitplane and canonical tree methods are more efficient for codes having many codewords of the same length.

V. CONCLUSION In this paper, we propose three methods to build a tree ordering all prefix-free EC-VLCs with a given Kraft vector ℓ. First results show that using a branch-and-prune algorithm on a tree built with one these methods yields fast algorithms to optimize the free distance, when compared to an exhaustive search algorithm. Qualitatively, we observed that the method by codewords works better for Kraft vectors with distinct lengths, while the bitplane and canonical tree approaches are more efficient when many codeword lengths are equal.

  Fig.1(a)shows the FSE associated to a source X with alphabetX 3 = {a 1 = a, a 2 = b, a 3 = c} encoded using the codebook C 3 = {c 1 = 0, c 2 = 10, c 3 = 111}.A better-suited representation of C for distance evaluation is the bit-clock FSE (B-FSE) in which each transition is labeled with exactly one output bit and may have an empty input label. Details on how B-FSE can be obtained from the FSE are presented in[START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF]. Fig. 1(b) shows the B-FSE derived from the FSE of Fig. 1(a).

Fig. 1 .

 1 Fig. 1. (a) Example of FSE associated to X 3 and C 3 and (b) its corresponding bit-clock representation

Fig. 2 .

 2 Fig. 2. Pairwise distance graph derived from the B-FSE in Fig. 1(b)

Fig. 4 .

 4 Fig. 4. Example of a tree of EC-VLCs for Kraft vector ℓ = (1, 2, 3)

Fig. 5 .

 5 Fig. 5. Example of a tree of EC-VLCs obtained by bit plane construction for Kraft vector ℓ = (1, 2, 3)

Fig. 6 .Fig. 7 .

 67 Fig. 6. Two isomorphic trees

Fig. 8 .

 8 Fig.8. Generating all canonical trees for ℓ =[START_REF] Cover | Elements of Information Theory[END_REF][START_REF] Zhong | On the joint source-channel coding error exponent for discrete memoryless systems[END_REF][START_REF] Viterbi | Principles of Digital Communication and Coding[END_REF]

ACKNOWLEDGMENTS

The authors would like to thank Pierre Duhamel for helpful discussions and suggestions.

This work was partly supported by the European Commission in the framework of the FP7 Network of Excellence in Wireless COMmunications NEWCOM++ (contract n. 216715).


Nesrine Changuel
email: nesrine.changuel@alcatel-lucent.com

Nicholas Mastronarde

Mihaela Van Derschaar
email: mihaelaucla@gmail.com

Bessem Sayadi
email: bessem.sayadi@alcatel-lucent.com

Michel Kieffer
email: kieffer@lss.supelec.fr

End-to-end Stochastic Scheduling of Scalable Video Over Time-Varying Channels

Keywords: Buffer control, Markov Decision Process, Scalable video coding, Video scheduling Categories and Subject Descriptors C.2 [Computer communication network]: Network Architecture and Design-Wireless communication, Network management, Client/server Algorithms, Experimentation

This paper addresses the problem of video on demand delivery over a time-varying wireless channel. Packet scheduling and buffer management are jointly considered for scalable video transmission to adapt to the changing channel conditions. A proxy-based filtering algorithm among scalable layers is considered to maximize the decoded video quality at the receiver side while keeping a minimum playback margin. This problem is cast in the context of Markov Decision Processes which allows the design of foresighted policies maximizing some long-term reward. Experimental results illustrate the benefit of this approach compared to a shortterm policy in term of average PSNR improvement.

INTRODUCTION

The rapid growth in wireless networks allows a higher diversity of services provided to users. Thus, broadcasting, mobile television, or video-on-demand are expected to develop widely in the near future. Even if wireless resources expected to grow significantly for large-display mobile receivers, one major concern is to maximize the received video quality. This paper focuses on Quality of Service (QoS) optimization in the context of video streaming applications to mobile users while considering channel and buffering constraints. The time-varying characteristics of the source and of the channel make the end-to-end optimization of such streaming chain quite difficult.

Several components in the streaming system may be optimized, for example, the media server, intermediate buffers, the channel resource scheduler, receiver buffers, etc. [START_REF] Pahalawatta | Review of content-aware resource allocation schemes for video streaming over wireless networks[END_REF].

A first class of techniques used to solve this problem considers a deterministic optimization framework. The work in [START_REF] Chi-Yuan | Rate control for robust video transmission over burst-error wireless channels[END_REF] focuses on delivery delay satisfaction of real-time non scalable video contents. To solve this problem accurate models of the rate-distortion (R-D) characteristics of the source are required. In [START_REF] Hassan | Video transport over wireless channels: a cycle-based approach for rate control[END_REF], a scheme is proposed to avoid underflow state of the playback buffer while smoothing out the variations of the encoding rate. An adaptive media playout method is proposed in [START_REF] Kalman | Adaptive media playout for low-delay video streaming over error-prone channels[END_REF] to limit the data buffering at the client and to reduce the display delay in time-varying channel conditions. In [START_REF] Liebl | Radio link buffer management and scheduling for wireless video streaming[END_REF], the problem is extended to a multi-users scenario.

A second class of techniques consider Markov models of the source, the contents of the buffers, or the channel to perform a stochastic control of the streaming system. In [START_REF] Cabrera | Stochastic rate-control of video coders for wireless channels[END_REF], the quantization parameters are optimized based on source and buffers Markov models for non scalable video. The problem is cast into the framework of Markov Decision Processes (MDP) [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. Scalable video coders are considered in [START_REF] De Cuetos | Optimal streaming of layered video: joint scheduling and error concealment[END_REF], where the impact of error-concealment which may be performed at receiver side is explicitly taken into account when searching for some optimal long-term control policy. Later, [START_REF] Mastronarde | Designing autonomous layered video coders[END_REF] proposes a framework for the design of autonomous layered video coders by optimizing each layer accounting for In this paper, we consider the problem of joint packet scheduling for SNR scalable video coders. Encoder and receiver buffers management is also considered with a stochastic control technique over time-varying channels. A proxybased filtering algorithm among scalable layers is proposed to maximize packet transmission while considering priority level among layers, see Section 2. Buffers at encoder and receiver side are considered for each layer to ensure minimum playback margin and maintain satisfying video quality. This problem is cast in the context of Markov Decision Processes (MDP) in Section 3. This formalism allows to derive a foresighted control policy maximizing some long-term discounted sum of rewards. Experimental results, detailed in Section 4 illustrate the benefits of this approach compared to a short-term (myopic) policy. The impact of information concerning the level of the receiver buffers on the global scheduling performance is mentioned.

STREAMING SYSTEM

The considered streaming system is illustrated Figure 1. The core network consists of a streaming server, hosting a scalable video coder, a proxy, and a base station, which is the front-end of the wireless part of the system. Packets are transmitted through a wireless channel and received by a mobile client. Information on the level of the receiver buffers may be sent back to the proxy.

System description

In the streaming server, the video sequence is segmented into frames and encoded into a base layer and a set of L -1 enhancement layers. The base layer and its corresponding enhancement layers form an access unit (AU). An AU is generated with a constant period of time ∆t and is identified by its temporal index t.

Scalable Video Coding (SVC) [START_REF] Schwarz | Overview of the scalable video coding extension of the H.264/AVC standard[END_REF] supports usually three types of scalability: temporal, spatial, and quality (SNR) scalability. SNR scalability is classified into Coarse, Medium, and Fine-Grain quality Scalable coding (CGS, MGS, FGS). Here, only MGS scalability is considered, since it is wellsuited in an unicast scenario. The encoding parameters (quantization steps, frame rate, etc.) are controlled by the streaming server, independently of the remainder of the chain.

In order to minimize the drift due to lost layers, a base layer only control scheme [START_REF] Schwarz | Overview of the scalable video coding extension of the H.264/AVC standard[END_REF] for the encoder is considered. Each SNR layer of each encoded frame is packetized into a single Network Abstraction Layer (NAL) unit, which itself is encapsulated into a Real-time Transport Protocol (RTP) packet. These packets are fed via the an over-provisioned core network (assumed lossless), to the L post-encoder buffers of the proxy. Considering one buffer per layer facilitates differentiation of the actions applied to each layer.

For each layer, the proxy has to decide to send packets, to wait, or to drop packets (layer filtering process). Constraints on the available bandwidth have to be satisfied. For that purpose, the proxy may exploit some feedback from the mobile client to estimate the channel conditions. In order to limit the delay between transmission and feedback information, the proxy is placed at the boundary of the wireless network, close to the base station. Here, delays resulting from buffering at MAC layer and transmission are neglected.

The receiver hosts the video decoder and one buffer per scalability layer. The levels of the receiver buffers and the state of the channel are fed back (with no delay nor error) to the proxy with a period ∆t. For both post-encoder and receiver buffers, when buffers reach fullness, packets in the queue have to be dropped in a Head-Of-Line (HOL) order, i.e., packet which resides longest in the buffer are dropped first. At each time t, the decoder builds AUs from the packets available in the receiver buffers, which are then decoded. Outdated packets are dropped, without being decoded.

System constraints

This paper focuses on the design of an efficient layer filtering process done by the proxy in such a way that the quality of the decoded video is maximized while satisfying the following constraints: (i) the transmission rate has to be below and as close as possible to the rate allowed by the channel;

(ii) the level of the post-encoder buffers should avoid under and overflow; (iii) the receiver buffers should provide some playback margin to be robust against temporary unavailability of the channel.

SYSTEM MODEL

In this section, the problem of designing an optimal scheduling policy of L SNR scalable layers over a wireless channel is translated in the framework of discrete-time MDP [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF].

An MDP is a 4-tuple (S, A, T, R), where S is the set of states of the system, A is the set of actions, T (s, s , a) determines the transition probability from s ∈ S at time t -1 to s ∈ S at time t, when the action a ∈ A is applied to the system. Finally R (s, s , a) indicates the immediate reward received after transition from s to s with transition when a is applied on the system.

Designing an optimal scheduler for the proxy consists thus in determining an optimal policy π (s) , s ∈ S. Such policy may be obtained using, e.g., classical value iteration technique, see [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. This requires all components of the tuple to be identified for the system considered in Section 2.

States

The considered states of the system are the states of the channel ht ∈ H = 0, 1, the levels of the post-encoding buffers hosted by the proxy s e l , l = 1 . . . L, and the levels of the receiver buffers s r l , l = 1 . . . L. More states could be considered (type of picture) to get a more accurate control process at the price of an increased complexity.

Channel model

The behavior of the channel is described by a two-state Markov model, to simulate the bursty nature of an errorprone wireless channel. The channel state ht represents the channel conditions, assumed constant, between time t -1 and t. In the good state (ht = 1), at most Rc bits/s may be transmitted. In the bad state (ht = 0), the channel is unable to transmit any bit. The channel state transition probabilities are described by

pij = p(ht = i | ht-1 = j), with i, j ∈ {0, 1} . (1)
These probabilities are assumed time-invariant and may be estimated using learning techniques [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. here, they are assumed known a priori.

Buffers

The states of the l-th post-encoder and receiver buffer, with l ∈ {1 . . . }, are denoted by s e l ∈ S e l and s r l ∈ S r l . They represent the level of the corresponding buffer. The vectors of states of all post-encoder and receiver buffers are respectively denoted by s e t = (s e 1,t , . . . , s e L,t ) and s r t = (s r 1,t , . . . , s r L,t ). Various granularity levels may be considered to represent the content of a buffer [START_REF] Mastronarde | Designing autonomous layered video coders[END_REF][START_REF] Mastronarde | Online reinforcement learning for dynamic multimedia systems[END_REF]. To minimize complexity, a coarse representation of the levels of the buffers is considered. Since buffer under and overflow have to be avoided, the values taken by the levels are quantized to get S x l = {1, 2, 3} with x ∈ {e, r}, where 1 represents underflow, 3 overflow, and 2 satisfying level.

Actions

The proxy has to determine the number of packets from each layer to send. When the channel conditions are bad and to avoid post-encoder buffer overflow, packets may also be dropped. The action a l,t taken for the l-th layer at time t represents then the number of transmitted packets from the post-encoder buffer, when its value is positive, or the number of dropped packets when it is negative. If a l,t = 0, packets are neither transmitted nor dropped. The vector gathering all actions is denoted by a = (a1, . . . , aL) ∈ A.

Transition matrix and reward function

Once all states and actions have been identified, one has to determine the 3D transition probability matrix

T (st, st+1, at) = Pr (st+1 | st, at) , (2)
with st = (s e t , s r t , ht). At time t, the proxy has to apply an action that maximizes the received video quality while satisfying the constraints described in Section 2.2. For that purpose, the following reward function is introduced. ].

Rt(st, at) = L l=1 γ l a l,
(3)

The positive parameters γ l , λ l , µ l , with l = 1 . . . L, and β help to trade off the importance of the various constraints. The reward function (3) involves several parts, the first linked to the received video quality, the others to the constraints mentioned in Section 2.2.

Assuming that increasing the amount of transmitted packets increases the received quality, the transmission reward should help to maximize the amount of transmitted packets. The parameters γ l allow to give a higher priority to packets belonging to the base layer compared to those of the enhancement layers.

For encoder and receiver buffer constraints, ρ(.) provides a positive reward for buffer State 2 and a negative reward for States 1 and 3.

RT,t (at, ht) is the total transmission rate at time t when the action is at and the channel state is ht. The function ν(x) = -abs(x)-ν0sgn(x) introduces a strong penalty when RT,t(at, ht) -Rc,t > 0, corresponding to a required rate larger than the actual channel transmission rate. When RT,t(at, ht) -Rc,t ≤ 0, a positive reward is provided, maximum when the difference vanishes.

Myopic and foresighted policies

Unlike traditional myopic rate control optimization techniwues, which focuses on the maximization of some immediate reward, the goal in the proposed rate control framework is to find an optimal policy for each SNR layer that maximizes the expected discounted sum of future rewards

∞ t=0 α t Rt(st, at|s0). (4)
where the parameter 0 < α < 1 is the discount factor, which defines the relative importance of present and future rewards, and s0 is the initial state. The foresighted policy, which maximizes the above sum when α > 0, takes into account the impact of the current actions on the future rewards. When α = 0, only the immediate reward is maximized and the corresponding policy is called myopic.

Both policies are obtained by value iteration as detailed, e.g., in [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF].

EXPERIMENTAL RESULTS

The performance of the proposed layer filtering process has been evaluated on various video sequences (Foreman, Mother & daughter,. . . ). Here the results for Foreman in QCIF format at fr = 30 fps are reported. Similar results are observed for the other sequences. Experiments are performed using the H.264/SVC encoder.

The Foreman sequence is encoded using three MGS scalability layers per frame (L = 3) corresponding to cumu-lated average rates (PSNR for luminance) of 34.7 kbits/s (28.67 dB) for Layer 1, 107.0 kbits/s (31.5 dB) for Layer 1 and 2, and 327.0 kbits/s (35.82 dB) for all layers. The channel rate in its good state is Rc = 300 kbit/s. The channel state transition probabilities are p11 = 0.9 and p00 = 0.8, resulting in an average channel rate of 200 kbits/s. Four possible actions per layer are considered at each time instant A = {-1, 0, 1, 2}.

The post-encoder and the receiver buffers are assumed to have a maximum size (in term of number of packets) S e = 20 and S r = 30. The levels at which they are considered in over and underflow are S e max = 19 and S e min = 6 for the postencode buffers. The underflow limit for the receiver buffers is S r min = 13. The values of the parameters in the reward function (3) reflect the importance of the various constraints. Some training provides γ1 = 300, γ2 = 150, γ3 = 60, λ1 = 200, λ2 = 100, λ3 = 40, µ1 = 300, µ2 = 150, and µ3 = 60. The parameters β and ν0 of the bandwidth constraint are respectively set to 0.1 and 5000 to give more weight to the bandwidth constraint compared to other constraints. AAA Mihaela, do you have any good way to perform the tuning apart from doing it by hand as was done by Nesrine ? ZZZ Performances obtained with a myopic policy are compared to those obtained with a foresighted policy with α = 0.9.

The evolution of the PSNR for the luminance of the decoded video streams for both strategies are represented in Figure 2. In average, a gain of about 1.36 dB is obtained with the foresighted policy compared to the myopic one. This gain is mainly due to more packets of the first enhancement layer reaching the receiver. With the foresighted policy, 20.3% of the actions for the second enhancement layer are drop actions compared to 20.9% in the case of a myopic policy. For what concerns the first enhancement layer, no drop actions are obtained by using the foresighted policy compared to 20.3% for the myopic one.

An analysis of the level of the receiver buffers shows that they are more often at a satisfying level with the foresighted policy than with the myopic policy AAA Nesrine, give per-centage of the time in both cases)ZZZ. This allows a better playback margin to be obtained with the foresighted policy.

The impact of controlling the level of the receiver buffers is easily evaluated by setting µ l = 0, l = 1 . . . 3. AAA Nesrine, provide a plot, or provide numbers, An increase of the video quality when receiver buffer information is exploited.ZZZ

CONCLUSIONS AND PERSPECTIVES

This paper presents a scalable video streaming system over a time-varying wireless channel to a mobile user cast in the framework of MDP. Experimental results illustrate an improvement in the average PSNR with the foresighted policy compared to myopic policy. Considering receiver buffers contributes in some video quality improvements.

The proposed filtering process performs for video-on-demand services. For real-time video transmission, the parameters of the off-line control can be adapted to the variation of the video characteristics using reinforcement learning designed for on-line learning MDP policies [START_REF] Sutton | Reinforcement Learning: An Introduction[END_REF]. Additional test benchmark, such as that in [START_REF] Liebl | Radio link buffer management and scheduling for wireless video streaming[END_REF], will be considered.

Figure 1 :

 1 Figure 1: End-to-end video streaming scheme

  Without filtering process) Decoded PSNR (Foresighted control) Decoded PSNR (Myopic control)

Figure 2 :

 2 Figure 2: PSNR of the decoded sequence

  t transmission + βν (RT,t(at, ht) -Rc,t)

			bandwidth constraint
	L		L
	+E[	λ l ρ(s e l,t , a l,t )	+	µ l ρ(s r l,t , a l,t )
	l=1		l=1
	encoder buffer	receiver buffer


Usman Ali

Michel Kieffer

Pierre Duhamel

Frame Synchronization based on Robust Header Recovery and Bayesian Testing

Video transmission on wireless links usually requires some frame aggregation, so that the overhead due to the headers is not a too large percentage of the bit-stream. In such a situation, header error detection is essential, because any error in the header may cause a loss of several consecutive frames. The contributions of this paper are (i) an improved reception of the length field of the header and (ii) an improved Frame Synchronization (FS) algorithm for aggregated frames. The FS algorithm has the following characteristics: (i) it makes use of the implicit redundancies which are present in the headers, thus resulting in an efficient synchronization of the variable-length frames; (ii) Bayesian hypothesis testing is used to estimate the correct synchronization; (iii) the proposed algorithm performs estimation on-the-fly and does not require reading the whole bit-stream. A comparative performance evaluation with respect to previously proposed algorithms is provided in the context of WiMAX MAC.

I. INTRODUCTION

In several communication systems, at a given layer of the protocol stack, small packets or frames are aggregated into larger frames or bursts in order to reduce the overhead due to headers, see e.g., 802.11/802.16 standards [START_REF]Wireless LAN Medium Access Control (MAC) and physical layer (PHY) specifications: Enhancements for higher throughput[END_REF], [START_REF]IEEE standard for local and metropolitan area networks, air interface for fixed broadband wireless access systems[END_REF] for Wireless Local Area Networks (WLANs). These aggregated frames are then forwarded by the transmitter to lower protocol layers. As an example, frame aggregation techniques at intermediate protocol layers have been studied recently [START_REF] Sidelnikov | Fragmentation/aggregation scheme for throughput enhancement of IEEE 802.11n WLAN[END_REF] in the context of 802.11 standard. This aggregation has two effects: on one side, it increases the useful throughput in quite a large amount, but, on another side, any error upon reception of the burst header results in the loss of the complete burst, corresponding to many individual frames. When the burst header has been correctly received, efficient Frame Synchronization (FS) becomes very important, since if some frames are not correctly delineated, a large amount of bits has to be retransmitted. When the delay is constrained (situations where one cannot afford retransmission of large aggregated frames) or when retransmitting bursts in error is not possible (broadcasting), header recovery and FS remain the only options.

Initially, FS techniques, as proposed in [START_REF] Barker | Group synchronization of binary digital systems in Communication Theory[END_REF], [START_REF] Massey | Optimum frame synchronization[END_REF], [START_REF] Scholtz | Frame synchronization techniques[END_REF] were using regularly spaced fixed patterns or Sync Words (SW) to delimit fixed-length frames. This is the situation, e.g., at the PHY layer of DVB-H [START_REF]ETSI. Digital video broadcasting (DVB); framing structure, channel coding and modulation for digital terrestrial television[END_REF] for MPEG2-TS frames. In [START_REF] Barker | Group synchronization of binary digital systems in Communication Theory[END_REF], synchronization is performed by maximizing the correlation between the SW and the received data. This has been improved in [START_REF] Massey | Optimum frame synchronization[END_REF], where the optimal statistic for FS has been proposed for the AWGN case, taking into account the presence of data around the SW. This was further extended in [START_REF] Lui | Frame synchronization for gaussian channels[END_REF] for more sophisticated transmission schemes. Similarly, in the presence of SW, in [START_REF] Chiani | On sequential frame synchronization in AWGN channels[END_REF], [START_REF] Martini | Optimum metric for frame synchronization with gaussian noise and unequally distributed data symbols[END_REF], several hypothesis testing techniques have been presented to perform FS, for variable-length frames. In the absence of SW, the Header Error Control (HEC) field of the header has been employed in [START_REF] Ueda | Reducing misframe frequency for HEC-based variable length frame suitable for IP services[END_REF] to perform FS of variable length IP frames with a three-state automaton adapted from [START_REF]B -ISDN user-network interface -physical layer specification: General characteristics[END_REF], performing bit-by-bit search for FS. A length field, assumed present in the frame header, facilitates the FS when the noise is moderate. In several situations, e.g., when the HEC field is erroneous itself or when its length is too short compared to the header size, false alarms can hamper an effective FS.

The above-mentioned FS techniques work on-the-fly, i.e., only a small portion of the aggregated frame is processed at each time to perform FS. This has the advantage of allowing early decisions, therefore introducing almost no latency.

It can be observed that none of these methods make full use of intra and inter-layer redundancies introduced by the structure of the header, redundancies which can be very useful. This usefulness was evidenced in the trellis-based approach [START_REF] Ali | Joint protocol-channel decoding for robust aggregated packet recovery at WiMAX MAC layer[END_REF] for the segmentation of MAC frames aggregated in large WiMAX PHY bursts. However, in this hold-and-sync(hronize) technique, the receiver must wait for whole or at least for a large part of an aggregated frame, which is sometimes undesirable in certain situations (such as framing of IP frames over ATM network), thus an unavoidable trade off between performance and delay is required.

In some sense, this paper proposes an on-the-fly technique which tries to take the best of these previously proposed methods: It combines robust header recovery techniques inspired from [START_REF] Marin | Robust header recovery based enhanced protocol layer mechanism[END_REF] with Bayesian hypothesis testing inspired from [START_REF] Chiani | Optimum synchronization of frames with unknown, variable lengths on Gaussian channels[END_REF], [START_REF] Chiani | Practical frame synchronization for data with unknown distribution on AWGN channels[END_REF], [START_REF] Chiani | On sequential frame synchronization in AWGN channels[END_REF], [START_REF] Martini | Optimum metric for frame synchronization with gaussian noise and unequally distributed data symbols[END_REF] to localize frame boundaries via a sample-bysample search. We use the three-state automaton, derived from that of [START_REF] Ueda | Reducing misframe frequency for HEC-based variable length frame suitable for IP services[END_REF], but instead of hard CRC correction, a soft header recovery technique [START_REF] Marin | Robust header recovery based enhanced protocol layer mechanism[END_REF] for correcting the damaged headers (exploiting all known intra and interlayer redundancies) is exploited to estimate the length field of the header. Moreover, the Bayesian hypothesis testing used to search for the correct location of FS is improved based on soft channel information (the output of the channel or channel decoder) combined with a priori information due to the redundancy present at the header of frame (known fields, presence of CRC or checksums, etc).

To be fully efficient, FS techniques require soft information from the channel decoders at PHY layer to reach upper layers, as proposed by [START_REF] Panza | Supporting network transparency in 4G networks[END_REF], [START_REF] Woo | Beyond the bits: cooperative packet recovery using physical layer information[END_REF]. Combined with joint sourceprotocol-channel (JSPC) decoders (see [START_REF] Duhamel | Joint source-channel decoding: A crosslayer perspective with applications in video broadcasting[END_REF] and the references therein), robust FS techniques allow to significantly reduce the amount of frames that need to be retransmitted. Moreover, the combination of transparent layer mechanisms [START_REF] Panza | Supporting network transparency in 4G networks[END_REF] with a robust header estimation technique [START_REF] Marin | Robust header recovery based enhanced protocol layer mechanism[END_REF] allows erroneous frames, which would be otherwise dropped, to reach the APL layer where they may be correctly understood by JSPC decoders.

The paper is organized as follows: Structure of frames and their aggregation is presented in Section II. The proposed three-state automaton is presented in Section III. Finally, we present the results obtained for the WiMAX MAC layer over AWGN and Rayleigh channels in Section IV before drawing some conclusions.

II. FRAME AGGREGATION

Aggregation algorithms entail the process of assembling frames with similar destination called aggregation target. Upon arrival at the target, the original small frames are recovered from the aggregate frame. This recovery process is known as fragmentation or de-aggregation, which can be performed in a robust manner using FS techniques.

A. Structure of a frame

Consider the n-th variable-length frame at a given protocol layer. This frame is assumed to contain λ n = h + p,n bits, where the leading h bits represent the frame header, of fixed length, and the remaining p,n bits are the variable-length payload. In the header, c bits are some Header Error Control (HEC) bits, CRC or checksum.

In this paper, we assumed that the header h n of the n-th frame may be partitioned into four fields. The constant field k, contains all bits which do not change from frame to frame. It includes the sync word indicating the beginning of the frame, but also other bits which are constant [START_REF] Marin | Robust header recovery based enhanced protocol layer mechanism[END_REF]. The header is assumed to contain a length field u n , indicating the size of the frame in bits λ n , including the header. The other field o n , gathers all bits of the header which are not fully determined and are not used to perform FS. Finally, the HEC field c n is assumed to cover only the header (i.e., hc bits) without covering the payload. Thus:

c n = f (k, u n , o) , ( 1
)
where f is some (CRC or checksum) encoding function. The payload of the n-th frame is denoted by p n , assumed to be generated by a binary symmetric source.

The length λ n of the n-th frame is assumed to be a realization of a stationary memoryless process Λ characterized by

π λ = Pr (Λ = λ) = 0 for min λ max , (2)
where min and max are the minimum and maximum length in bits of a frame. In what follows, the length in bits of a vector z is denoted by (z) and its observation (soft information) at the output of a channel, a channel decoder, or a lower protocol layer is denoted by y z . Moreover, z b a represents the sub-vector of z between indexes a (bits) and b (bits).

B. Aggregated frames within a burst

Consider a burst of L bits consisting of N aggregated frames. This burst contains either N -1 data frames and an additional padding frame containing only padding bits, see Figure 1, or N data frames and no padding bits. Assume that each of these frames, except the padding frame, contains a header and a payload and follows the same syntax, as described in Section II-A.

Assuming that L is fixed before frame aggregation and that N is not determined a priori, the accumulated length in bits of the n first aggregated frames may be described by a Markov process, which state is denoted by S n . If < L, then

P (S n = | S n-1 = ) = π - if min - max 0 else, (3)
and if = L, then

P (S n = L | S n-1 = ) =        0, if L -> max 1, if 0 < L -< min max k=L- π k , else. (4)
In ( 4), if 0 < L -< min , there is not enough space in the burst to put a data frame and the n-th frame is thus necessarily the (last) padding frame. If L -> max , there is enough space to put a data frame of any allowed length, thus, the n-th frame cannot end the burst. In the other cases, only data and padding frames of Lbits are allowed to finish the burst. This is possible when the n-th data frame is of Lbits or if the n-th data frame generated by the source has a length strictly larger than Lbits.

With this representation, the successive values taken by S n , n = 0, . . . , N max can be described by a trellis, first proposed in [START_REF] Ali | Joint protocol-channel decoding for robust aggregated packet recovery at WiMAX MAC layer[END_REF], as shown in Figure 2. This trellis is inspired from the one proposed in [START_REF] Bauer | Symbol-by-symbol MAP decoding of variable length codes[END_REF] for the robust decoding of variable-length encoded data. In this trellis, dashed transitions correspond to padding frames and plain transitions correspond to data frames. For the last frame (when S n = L), dashed and plain transitions may be parallel.

III. THREE-STATE FS AUTOMATON

This section proposes an adaptation of the three-state (3S) automaton proposed in [START_REF]B -ISDN user-network interface -physical layer specification: General characteristics[END_REF] for the synchronization of fixedlength ATM cells and adapted by Ueda et al. in [START_REF] Ueda | Reducing misframe frequency for HEC-based variable length frame suitable for IP services[END_REF] to deal with variable-length aggregated frames. When the frames are of variable length, a single random bit error in the header may falsely signal synchronization error. Therefore, some error correction has to be used. In [START_REF] Ueda | Reducing misframe frequency for HEC-based variable length frame suitable for IP services[END_REF], frame headers are assumed to contain an HEC and a length field. The HEC is assumed to be a CRC, which is used as an error-correcting code for the part of the header protected by the HEC. Correction is performed before hunting for synchronization, if required. Rather long HECs are required to be able to correct errors, as error correction is less efficient when the number of HEC bits protecting the header is small compared to the size of the header. More precisely, the automaton presented in [START_REF] Ueda | Reducing misframe frequency for HEC-based variable length frame suitable for IP services[END_REF] consists of three states: SYNCH, HUNT, and PRESYNCH. Assume that the automaton is in the SYNCH state. It remains in this state as long as no synchronization error is detected using HEC. If HEC detects a synchronization error, one first tries to correct errors in the header. In case of failure, the automaton switches to the HUNT state. In HUNT state, the automaton hunts for the correct synchronization by searching bit-by-bit for the correct HEC and for the assumed header fields. Once an agreement is found, the automaton switches to the PRESYNCH state, an intermediate state. In this state, a frame-by-frame checking is performed. In the PRESYNCH state, one makes sure that the synchronization retrieved in the HUNT state is indeed the correct synchronization by verifying that HEC is correct for δ > 0 consecutive frames. Once δ consecutive correct HECs have been obtained, the automaton returns to the SYNCH state and in case of failure it again switches to HUNT state. This method is denoted in what follows as the Ueda's method.

k u 2 o 2 c 2 k u 3 o 3 p N-1 1 L bytes S 2 bytes S bytes N-1 k u 1 o 1 c 1 p 1 S 1 bytes p 2
This section proposes several improvements to Ueda's method, see Figure 3. First, instead of performing error correction in the SYNCH state, the robust header estimation presented in [START_REF] Marin | Robust header recovery based enhanced protocol layer mechanism[END_REF] and briefly recalled in Section III-A is employed to estimate the length field of the frame. In case of failure to verify HEC of header with estimated length field (HEC verification is performed after replacing the re- Note that alternatively, an automation with a single HUNT State (HUNT State Alone, HSA) may be considered to perform FS. This may be useful when the frame length is not included in the header.

A. SYNCH State: Header Recovery

In [START_REF] Marin | Robust header recovery based enhanced protocol layer mechanism[END_REF], a maximum a posteriori estimator is proposed to determine some fields in the headers of the aggregated frames. In case of FS with frames of variable lengths, one is mainly interested in the length field denoted by u n for the n-th frame. With the notations of Section II-A, one obtains

ûn = arg max un∈Ωu P (y u |u n ) o P (y o |o) P (o) P (y c |c = f (k, u n , o)) , (5)
where Ω u = { min , ..., max } is the set of lengths which may be taken by the length field. The evaluation of (5) may be done optimally with a complexity O( (o) 2 (c) ), or suboptimally with a reduced-complexity algorithm, see [START_REF] Marin | Robust header recovery based enhanced protocol layer mechanism[END_REF] for more details.

B. HUNT State: Bayesian hypotheses test

In [START_REF] Chiani | Optimum synchronization of frames with unknown, variable lengths on Gaussian channels[END_REF], [START_REF] Chiani | Practical frame synchronization for data with unknown distribution on AWGN channels[END_REF], [START_REF] Chiani | On sequential frame synchronization in AWGN channels[END_REF], [START_REF] Martini | Optimum metric for frame synchronization with gaussian noise and unequally distributed data symbols[END_REF], several hypotheses tests based on a Neyman-Pearson (NP) criterion are introduced to determine whether a frame starts at a given bit index. Only the presence of a SW is assumed. Evaluations have been performed for balanced data symbols in [START_REF] Chiani | On sequential frame synchronization in AWGN channels[END_REF] and for unbalanced ones in [START_REF] Martini | Optimum metric for frame synchronization with gaussian noise and unequally distributed data symbols[END_REF]. This technique is efficient when the SW is long, but suffers limitations when it is short.

This section is devoted to the construction of Bayesian hypotheses tests exploiting all information present in the header as proposed in [START_REF] Ali | Joint protocol-channel decoding for robust aggregated packet recovery at WiMAX MAC layer[END_REF], [START_REF] Marin | Robust header recovery based enhanced protocol layer mechanism[END_REF]. This allows to build more efficient tests, especially when the SW is short.

Consider a given bit index of the burst. Under the hypothesis H h that a frame header h = [k, u, o, c] starts at , one may interpret the corresponding channel output as y = [y k , y u , y o , y c ] and

P (y|H h ) = h P (y|h, H h ) P (h|H h ) . (6)
With the same hypotheses as in [START_REF] Ali | Joint protocol-channel decoding for robust aggregated packet recovery at WiMAX MAC layer[END_REF], only the h starting1 with k have to be considered since this field is fully determined. Moreover, assuming that the channel is memoryless, taking into account the fact that k, u, o, and c do not depend on p, and the fact that the HEC c is fully determined by k, u, and o, (6) becomes

P (y|H h ) = P (y k |k) u∈Ωu (P (y u |u) P (u) o P (y o |o) P (o) P (y c |c = f (k, u, o))) . (7)
Under the hypothesis H d that does not correspond to the beginning of a frame, y is the channel output when data bits d are transmitted. Thus, assuming balanced data symbols, one gets

P (y|H d ) = d P (y|d, H d ) P (d|H d ) = d P (y|d, H d ) 2 -(d) . (8)
Bayesian hypotheses test can now be represented as

Λ(y) = P (y|H d ) P (y|H h ) D h ≶ D d P a ( , H h ) P a ( , H d ) , (9)
where D h or D d correspond to deciding H h or H d respectively. P a ( , H h ) and P a ( , H d ) are the a priori probabilities of the hypotheses at the bit index . When L -< max , may also represent the start of a padding frame. Thus, an additional hypothesis H p , corresponding to the presence of a padding frame, has to be considered. The Bayesian hypotheses test for deciding between H p and H d is given by

Λ(y) = P (y|H d ) P (y|H p ) D p ≶ D d P a ( , H p ) P a ( , H d ) . ( 10
)
Under H p , we have P (y|H p ) = P (y|1), where 1 is a vector of ones of the same size as of y. P (y|H d ) is given by [START_REF] Chiani | On sequential frame synchronization in AWGN channels[END_REF].

First ( 9) is applied to choose between header and data. Then, if data has been decided, [START_REF] Duhamel | Joint source-channel decoding: A crosslayer perspective with applications in video broadcasting[END_REF] is considered to see whether the data corresponds to a padding frame or not.

1) A priori probabilities: To determine the a priori probability P ( ) that a frame (data or padding) starts at a bit index of a burst of L bits, consider again the trellis representation as shown in Figure 2. One may write

P ( ) = 1 n / min P (S n = ), (11)
where P (S n = ) is the a priori probability that the n-th frame ends at bit index -1 (or that the n + 1-th frame starts at bit index ). P (S n = ) satisfies

P (S n = ) = P (S n = |S n-1 = )P (S n-1 = ), (12)
which may be evaluated iteratively with the help of ( 3) and ( 4), starting from n = 1 till n = / min , with initial condition P (S 0 = 0) = 1 and P (S 0 = 0) = 0.

A priori probability P ( ) = P a ( , H d ) corresponding to an absence of the start of frame at bit index is calculated by P ( ) = 1 -P ( ). P ( ) represents the a priori probability of a frame start, be it a data and/or a padding frame. Thus, P ( ) = P a ( , H h ) + P a ( , H p ) = P ( )P (H h | ) + P ( )P (H p | ) , where

P (H h | ) =        0, if 0 < L -< min 1, if L -> max L- λ= min π λ , else, (13)
and P (H p | ) = 1 -P (H h | ) are the conditional a priori probabilities of H h (header hypothesis) and H p (padding hypothesis), respectively.

IV. SIMULATION RESULTS

Simulation results for WiMAX MAC layer are provided in this section. In the WiMAX standard [START_REF]IEEE standard for local and metropolitan area networks, air interface for fixed broadband wireless access systems[END_REF], downlink (DL) subframes begin with a frame control section that contains the down-link map (DL-MAP) for the current down-link frame as well as the up-link map (UL-MAP) for a frame in future. The DL sub-frame is divided into bursts, each containing multiple concatenated fixed-length or variable-length MAC frames received from the higher layers. Each burst is modulated and coded at the PHY layer before transmission in the PHY DL sub-frame. Lengths of burst are assigned by the scheduler and are communicated to users in the DL-MAP. In what follows, we consider only the DL scenario and thus only the DL subframe.

MAC PDU begins with a fixed-length header of h = 48 bits, followed by a variable-length payload and an optional CRC [START_REF]IEEE standard for local and metropolitan area networks, air interface for fixed broadband wireless access systems[END_REF]. The header can be of two types, one is the generic header containing either MAC Management messages or Convergence Sublayer (CS) data and the other is the bandwidth request header used to request additional bandwidth. For DL with already established connections MAC PDUs always have a generic header as shown in Figure 4. The LEN field represents the length in bytes of the MAC PDU including the MAC header and Header Check Sequence (HCS). The HCS is a function of the content of all header fields, and is stored in an 8-bit field. Some assumptions are made for the sake of simplicity. CRC, ARQ, packing, fragmentation, and encryption are not used. Furthermore, no extended subheader is present. Some fields are already fixed in a MAC header, but with the considered assumptions, fields such as Header Type (HT), Encryption Control (EC), sub-headers, and special payload types (Type), Reserved (Rsv), CRC Indicator (CI), and Encryption Key Sequence (EKS) remain constant. All these fields are merged together in a constant field k of 13 bits, which can be used as a SW. A simulator consisting of a burst generator, a channel, and a receiver has been implemented. Simulations are carried over both Additive White Gaussian Noise (AWGN) and Rayleigh fading channel. In the case of Rayleigh fading channel, the modulated signal is subject to zero mean and unit variance fast (bit) Rayleigh fading plus zero-mean AWGN noise. In these simulations, we assume that all frames are byte aligned and that byte alignment has been already performed. Then in the HUNT state, the search is done byte-by-byte. This assumption is reasonable when FS is considered at intermediate layers of the protocol stack. Moreover, the burst size L is received without any error as it is transmitted in DL-MAP, which is protected with a more robust modulation and coding scheme. We have chosen L = 1800 bytes, as by ignoring the header overhead, 1800 bytes in every frame of 20 ms can provide a raw data rate of 703.125 kbps, which, if fully dedicated, is enough for a real-time video service. Random sized data frames with min = 50 bytes and max = 200 bytes are concatenated in a burst. If the generated frame is not insertable in the remaining space of a burst, a padding frame is inserted to fill the burst, which is then BPSK modulated before being sent over the channel.

For performance analysis, Erroneous Frame Location Rate (EFLR) is evaluated as a function of the channel Signal-to-Noise Ratio (SNR). A frame is deemed correctly synchronized when both of its ends have been correctly determined.

The proposed on-the-fly 3S FS method is compared with several other FS techniques. First, on-the-fly methods such as Ueda's method [START_REF] Ueda | Reducing misframe frequency for HEC-based variable length frame suitable for IP services[END_REF] 2 and the method presented in [START_REF] Chiani | On sequential frame synchronization in AWGN channels[END_REF], denoted as NP FS in what follows, serve as reference. Second, the hold-and-sync trellis-based technique presented in [START_REF] Ali | Joint protocol-channel decoding for robust aggregated packet recovery at WiMAX MAC layer[END_REF] is also considered, mostly as a lower bound for the EFLR, since the corresponding complexity and delay are not of the same order of magnitude. Since the MAC header uses an HEC of 8 bits only, a modified version 3 of Ueda's method, denoted MU, is applied.

Simulation results for transmission over an AWGN channel are provided in Figure 5. For the NP FS method, two curves The NP FS method with such a short SW of 13 bits has some FS error floor at high SNR, as expected, due to unavoidable and persistent high false alarm (emulation), as the payload data can simulate the SW more often due to the short size of the SW. The HSA method, since it uses more redundancy from the header, gives a much lower floor. 2 In case of two-bit error syndromes, the frame length is verified by evaluating the HEC over the next header, at the position indicated by the corresponding candidate. If no candidate is correct, i.e., corresponds to correct HEC at the potential location of the next header, then the candidate that gives one bit error syndrome at the next header is selected. In case of failure, the automaton switches to the HUNT state.

3 Modified UEDA's (MU) method: UEDA's Method [START_REF] Ueda | Reducing misframe frequency for HEC-based variable length frame suitable for IP services[END_REF] is well adapted for rather long HEC like CRC-16, because in this case there are no more than two candidates for two-bit error syndromes. For low order HEC, e.g., CRC-8, many more candidates can be found for syndromes with two bits in error, thus UEDA's method needs some modification. We propose to search for the best candidate by shifting the bit stream by the potential frame length and then calculating HEC over the next header sequence at the position indicated by corresponding candidate. If no candidate is correct (i.e., corresponds to correct HEC) at the potential location of the next header sequence, then the candidate that gives one-bit error syndrome at the next header sequence is selected as the best candidate. In case of failure, the FS automaton switches to HUNT state. Unfortunately, in case of low order HEC, meeting a configuration in which random bits emulate the header are more likely, making the method of hunting using HECs unreliable at low SNR. The proposed 3S FS method performs better than MU method, due to the use of soft hunt operation and to the robust header recovery technique. The MU method performs poorly, specifically at low SNR, due to the fact that it uses hard HEC detection/correction and the size of HCS (8 bits) is small compared to the size of the header (48 bits), thus more than 10 candidates for two bit error syndrome have to be considered. The 3S FS automaton performs better at low SNR due to the effectiveness of Bayesian hypothesis testing in the HUNT state, which can retrieve synchronization quickly. The difference between 3S FS and MU decreases at high SNR, since even though header recovery performs well, erroneous FS by Bayesian hypothesis testing degrades the performance because even in a good channel condition one can wrongly assume misalignment due to the simulation of header by random data. Trellis-based technique provide the best performance as expected, but at the cost of a delay equivalent to the length of an aggregated frame. The proposed 3S FS technique clearly provides improved FS compared to other on-the-fly algorithms thus providing reasonable compromise between performance and latency.

Simulation results for transmission over a Rayleigh channel are shown in Figure 6. MU method performance is highly impacted by Rayleigh channel, while the results for the 3S automaton clearly show its effectiveness in this context.

V. CONCLUSION

Header Error Control detection used as an indicator of correct frame synchronization does not perform efficiently at low SNR for variable-length frames. This paper proposes a FS technique exploiting structural properties of the frame headers to perform efficient segmentation. This technique makes use of header recovery and Bayesian hypothesis testing, while exploiting soft information provided at the output of the channel (or channel decoder) in conjunction with a priori information due to the redundancy present at the frame header. Simulations clearly demonstrate an improvement in terms of erroneous frame localization rate compared to methods performing computations on-the-fly. Practically, this improvement will result in reducing the amount of frames that need to be retransmitted.

Figure 1 .Figure 2 .

 12 Figure 1. Aggregated frames in a WiMAX burst

Figure 3 .

 3 Figure 3. Three-state FS automaton

Figure 4 .

 4 Figure 4. Generic MAC Header

Figure 5 .

 5 Figure 5. FS methods over an AWGN channel, with min = 50 bytes, max = 200 bytes, and L = 1800 bytes with two probability of False Alarm (FA) have been provided.The NP FS method with such a short SW of 13 bits has some FS error floor at high SNR, as expected, due to unavoidable and persistent high false alarm (emulation), as the payload data can simulate the SW more often due to the short size of the SW. The HSA method, since it uses more redundancy from the header, gives a much lower floor.

Figure 6 .

 6 Figure 6. FS methods over a Rayleigh channel, with min = 50 bytes, max = 200 bytes, and L = 1800 bytes

Here, to facilitate presentation, we have assumed that the bits of the known field k are at the beginning of the header. Any other organization of the header may be considered.

ACKNOWLEDGMENT This work was partly supported by Microsoft Research through its PhD European Scholarship program and by the NoE NEWCOM++.