A Diallo

Member, IEEE C Weidmann

Senior Member, IEEE M Kieffer

Efficient computation and optimization of the free distance of variable-length finite-state joint source-channel codes

Keywords: Variable length codes, finite state machines, source coding, channel coding, arithmetic codes

This paper considers the optimization of a class of joint source-channel codes described by finitestate encoders (FSEs) generating variable-length codes. It focuses on FSEs associated to joint-source channel integer arithmetic codes, which are uniquely decodable codes by design. An efficient method for computing the free distance of such codes using Dijkstra's algorithm is proposed. To facilitate the search for codes with good distance properties, FSEs are organized within a tree structure which allows the use of efficient branch-and-prune techniques avoiding a search of the whole tree.

I. INTRODUCTION

Today, most communication systems are based on Shannon's separation principle [START_REF] Shannon | A mathematical theory of communication[END_REF], which states that source and channel coding may be optimized separately, without loss of optimality compared to a joint design. However, this result has been obtained under the hypothesis of a stationary channel, which is seldom the case in wireless communication systems. As a consequence, channel codes are usually difficult to adapt to time-varying channel conditions. Moreover, source codes are suboptimal due to complexity constraints. These issues have prompted 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 error-correction performance may be predicted with an union bound 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 variable-length codes (JSC-VLC) was introduced in [START_REF] Bernard | Some combinatorial results on variable-length error-correcting codes[END_REF], while design techniques aiming at optimizing distance properties of such codes were reported in [START_REF] Buttigieg | On variable-length error-correcting codes[END_REF] and later for a small subclass of JSC integer arithmetic codes (JSC-IAC) in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF].

This paper focuses on the optimization of codes generated by finite-state encoders (FSEs), which can be used to describe many JSC codes, including JSC-VLC and JSC-IAC. More precisely, our aim is to efficiently explore the (already very large) subclass of finite-state codes (FSCs) corresponding to JSC-IAC. One prerequisite for such optimization is the availability of efficient tools to evaluate distance properties of FSCs, which constitutes the first contribution of this paper, see Section III.

The first tools for evaluating distance properties considered linear FSCs, such as convolutional codes (CCs) [START_REF] Elias | Coding for noisy channels[END_REF]. In [START_REF] Viterbi | Convolutional codes and their performance in communication systems[END_REF], Viterbi computed transfer functions on the state diagram of CCs to obtain their distance spectra and deduced their free distance. In [START_REF] Astola | Convolutional code for phase-modulated channels[END_REF], a variant of Dijkstra's shortest path algorithm is applied on the CC state diagram to compute the free distance without generating the spectrum. Later, [START_REF] Cedervall | A fast algorithm for computing distance spectrum of convolutional codes[END_REF] proposed a fast tree search algorithm for computing the CC distance spectrum. All these techniques have a complexity that is linear in the number of encoder states, due to the linearity of CCs.

For nonlinear FSCs, all pairs of codewords have to be compared to compute the free distance.

For Euclidean-distance codes generated by trellis-coded modulation (TCM) [START_REF] Ungerboeck | Channel coding with multilevel/phase signals[END_REF], [START_REF] Biglieri | High-level modulation and coding for nonlinear satellite channels[END_REF] used the product graph derived from the graph associated to the FSE. This allows to compute the distance spectrum of TCM in the code (signal) domain and to infer the free distance. For a FSC with 2 ν states, a product trellis with (2 ν ) 2 states is required for these evaluations [START_REF] Biglieri | High-level modulation and coding for nonlinear satellite channels[END_REF]. For the class of geometrically uniform FSCs [START_REF] Forney | Geometrically uniform codes[END_REF], which includes certain TCM codes, a modified generating function on a state diagram with only 2 ν states is sufficient to compute the spectrum [START_REF] Zehavi | On the performance evaluation of tellis codes[END_REF]. All the above-described techniques are for fixed-rate codes, more precisely for FSEs defined by graphs where all transitions have input labels of the same length k, as well as output labels of the same length n, as is the case, e.g., for rate k/n CCs. Distance properties for JSC-VLCs were first evaluated in [START_REF] Buttigieg | On variable-length error-correcting codes[END_REF], [START_REF] Buttigieg | Variable-length error correcting codes[END_REF], where a lower bound for their free distance and exhaustive (exponential complexity) algorithms for their distance spectrum were proposed. Graphs that are similar to those used for distance properties of fixed-rate trellis codes have also been used in the context of JSC-VLCs, but to evaluate other figures of merit. For example, [START_REF] Even | Test for synchronizability of finite automata and variable length codes[END_REF] defined a testing graph, consisting of the product graph that represents only pairs of paths at null Hamming distance to define a test for synchronizability of VLCs. The error-state diagram introduced by [START_REF] Maxted | Error recovery for variable length code[END_REF] for VLCs is the product graph that represents the pairs of paths at Hamming distance one to study the resynchronization properties of the decoder after a single bit error in the encoded sequence. In [START_REF] Malinowski | Error recovery properties and soft decoding of quasi-arithmetic codes[END_REF], these results were extended to JSC-IACs.

Evaluating the distance properties of nonlinear FSCs corresponding to JSC-IACs is slightly more complex than for JSC-VLCs. This is due to the fact that the FSE of a JSC-VLC has only one state in which paths can diverge and converge, while there may be many such states for a JSC-IAC. First analytical tools for JSC-IACs were proposed in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF], where the free distance is evaluated with polynomial complexity, whereas approximated distance spectra are obtained with exponential complexity as in [START_REF] Buttigieg | Variable-length error correcting codes[END_REF]. More recently, [START_REF] Weidmann | Evaluation of the distance spectrum of variable-length finite-state codes[END_REF] explicitly defined variable-length finite-state codes (VL-FSCs) generated by variable-length finite state encoders (VL-FSEs) and proposed a matrix method with polynomial complexity to compute the exact distance spectrum in the code domain or some upper bound on it. The definitions of VL-FSEs and VL-FSCs will be recalled in Section II.

In Section III, we first generalize the methods proposed in [START_REF] Biglieri | High-level modulation and coding for nonlinear satellite channels[END_REF] and [START_REF] Astola | Convolutional code for phase-modulated channels[END_REF] to all FSCs, in order to be able to evaluate distance properties. A product graph inspired by that in [START_REF] Biglieri | High-level modulation and coding for nonlinear satellite channels[END_REF] is proposed for general FSEs and is simplified to get two graphs: the modified product graph (MPG), which allows to compute the code domain distance spectrum using a transfer function approach, and the pairwise distance graph (PDG). The PDG allows to compute the free distance of the FSC by applying Dijkstra's algorithm as in [START_REF] Astola | Convolutional code for phase-modulated channels[END_REF], without computing the entire distance spectrum. This approach is much less complex than the technique for computing the free distance of a JSC-IAC proposed in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF].

Our aim is then to apply these free distance evaluation tools to the efficient optimization of JSC-IACs.

Arithmetic coding (AC) [START_REF] Witten | Arithmetic coding for data compression[END_REF] is an efficient source coding method whose variants have been used in recent still image and video coders [START_REF] Christopoulos | The JPEG-2000 still image coding system: An overview[END_REF], [START_REF] Richardson | H.264 and MPEG-4 video compression: Video coding for next generation multimedia[END_REF]. Nevertheless, AC is particularly vulnerable to transmission errors. To overcome this, the most common form of JSC-AC introduces some redundancy in the compressed bitstream by means of a forbidden symbol (FS), to which a non-zero probability is given during the partition of the code interval [START_REF] Boyd | Integrating error detection into arithmetic coding[END_REF]. The larger the FS probability, the higher the redundancy and the robustness against errors. This idea is extended in [START_REF] Sayir | Arithmetic coding for noisy channels[END_REF], which proposes the introduction of multiple FSs (MFS). All these FS techniques can be applied to IAC [START_REF] Howard | Practical implementations of arithmetic coding[END_REF] leading to JSC-IAC. Optimization of JSC-IAC has been considered in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF], assuming that the total probability allotted to the (M)FS and the probability of each individual FS are independent of the states of the FSE representing the JSC-IAC. However, the class of JSC-IAC with state-independent probability allocation for the FSs is significantly smaller than that with state-dependent allocation. For a fixed amount of redundancy, more robust JSC-IACs than those obtained by [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF] may be obtained.

The second contribution of this paper, described in Section IV, consists in presenting some algorithms to globally optimize the free distance of some FSE by adjusting the introduction of MFS with in binary input JSC-IAC.

A JSC-IAC (and its corresponding FSE) may be described by its characteristic parameters (source probabilities, arithmetic precision, design rate) and by the way MFS are introduced.

The set of all JSC-IACs for fixed parameter values and with state-dependent MFS is generally huge, but Section IV-B shows that it may be structured with a tree, where all JSC-IAC codes correspond to leaves of the tree. An efficient branch-and-prune algorithm is then used to explore this tree and discard large parts of it as soon as it can be shown that all JSC-IACs stemming from a given node of the tree cannot have good performances in terms of free distance. An extension to non-binary input JSC-IACs is then presented in Section IV-C. Experimental results for both binary input and non-binary input JSC-IACs are then provided in Section V.

II. JOINT SOURCE-CHANNEL FINITE-STATE ENCODERS

We briefly recall and extend some definitions from [START_REF] Weidmann | Evaluation of the distance spectrum of variable-length finite-state codes[END_REF]. A binary-output FSE may be represented with a directed graph Γ(S, T ), where S is the set of states (vertices) and T is the set of transitions (directed edges). Each transition is labeled with a sequence of input symbols and a sequence of output bits. Let σ(t) be the originating state of a transition t ∈ T and τ (t) its target state, while I(t) denotes its input label and O(t) its output label. Let P (t), t ∈ T , be the probability that I(t) is emitted by the source, which for simplicity we assume to be memoryless.

A path t = (t 1 • t 2 • • • • • t k ) ∈ T k on
the graph is a concatenation of transitions that satisfy σ(t i+1 ) = τ (t i ) for 1 ≤ i < k (this corresponds to a walk of length k on the encoder graph).

By extension, we define σ(t) = σ(t 1 ) and τ (t) = τ (t k ), as well as I(t) and O(t), which are the concatenations of the input, respectively output, labels of t. The probability of a path is

P (t) = k i=1 P (t i ).
Finally, ℓ(x) is the length (in symbols or bits) of the sequence x. We assume that the FSE graph is irreducible, i.e., that any state can be reached from any other in a finite number of transitions, and that it is aperiodic, i.e., that the state recurrence times, measured in output bits, are not multiples of an integer period m > 1. These assumptions imply that the FSE together with the source being encoded forms an ergodic Markov chain, which has a unique stationary state distribution. Let P * (s), s ∈ S, be the stationary probability of the state s, which is computed taking into account the output label lengths as outlined in [START_REF] Weidmann | Evaluation of the distance spectrum of variable-length finite-state codes[END_REF].

For a FSE to be a proper source encoder, for every state, the input labels of the outgoing transitions have to form a complete prefix set, which implies that their transition probabilities sum to one [START_REF] Weidmann | Evaluation of the distance spectrum of variable-length finite-state codes[END_REF].

Given an initial state s 0 , the succession of states of the FSE for all possible (semi-)infinite input sequences can be displayed with a trellis, which can be viewed as a description of the temporal evolution of the FSE. The output labels of all paths through the trellis form a FSC, whose performance is determined by its coding rate and its error correcting capability. The error correcting capability is primarily characterized by the free distance d free (a finer characterization is possible through the distance spectrum). Under the assumption that the FSE is an irreducible graph, the free distance will be the same for every possible initial states.

Definition 1:

The coding rate R c , in bits per symbol, is the ratio between the average length of the output labels and the average length of the input labels of the transitions in T , R c = t∈T P * (σ(t))P (t)ℓ(O(t))

t∈T P * (σ(t))P (t)ℓ(I(t))

.

(1)

Definition 2: Let P k s 0 be the set of all paths with k transitions starting in s 0 . The FSC C (Γ, s 0 ) is the set of all infinite-length output sequences generated by the FSE from s 0 , C (Γ, s 0 ) = {O(t) : t ∈ P ∞ s 0 }. 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 (t 1 , t 2 ) ∈ T k 1 × T k 2 are such that ℓ(O(t 1 )) = ℓ(O(t 2 )), then we will write d H (t 1 , t 2 ) = d H (O(t 1 ), O(t 2 )).
Definition 3: The free distance, d free , of the FSC C (Γ, s 0 ) is the minimum Hamming distance between any pair of distinct code sequences. Let P be the set of all pairs of paths in

T k 1 × T k 2 1≤k 1 ,k 2 <∞
diverging in some state and converging for the first time in the same or another state and with the same length of output labels. Consequently, d free is also the minimum Hamming distance in P

d free = min (t 1 ,t 2 )∈P d H (t 1 , t 2 ) .
(

) 2
Definition 4: 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=d free A d D d , (3)
where A d is the average number of paths at Hamming distance d from a given path. In the most general case, A d can be defined as [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF], [START_REF] Weidmann | Evaluation of the distance spectrum of variable-length finite-state codes[END_REF],

A d = (t 1 ,t 2 )∈P d H (t 1 ,t 2 )=d P * (σ(t 1 ))P (t 1 ) (4)
By the above definitions we see that the code C (Γ, s 0 ) and its free distance are independent of the source (provided all source letters have nonzero probability), while the joint source-channel nature shows that the rate and the spectrum coefficients A d depend on the source statistics.

Finally, we introduce two notions which may help searching codes with a computer. A complete automaton (CA) is an FSE that can encode any source sequence. An incomplete automaton (IA)

is an FSE having one or more terminal states without outgoing transitions, in which encoding stops, see Figure 1. Such terminal states are called stopping states or unexplored states. An IA Γ 0 generates finite-length prefixes of code sequences and possibly some infinite-length code sequences. Let the incomplete code C 0 = C(Γ 0 , s 0 ) contains these (finite and infinite) sequences.

Definition 5:

The free distance associated to an incomplete FSE is the minimum Hamming distance between any pair of distinct output sequences, which are either infinite, or of equal length and associated to paths ending in the same state (all paths begin in s 0 ). If there is no pair of (finite-length) paths ending in the same state or (infinite-length) path converging at some time instant in the same state, the free distance is infinite.

An IA or CA Γ 1 is derived from an IA Γ 0 if it has been obtained by exploring (adding the successor states of) one or more terminal states of Γ 0 (hence the graph Γ 0 is a subgraph of Γ 1 ) [START_REF] Gondran | Graphs and algorithms[END_REF]. Let C 0 and C 1 be two codes generated by Γ 0 and Γ 1 , respectively, with free distance d (0) free and d In [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF], three types of FSE describing the coding operations were considered: a symbol-clock FSE (S-FSE) suited for encoding, where each transition is labeled with exactly one input symbol; a reduced FSE (R-FSE), with variable-length non-empty input and output labels, leading to a compact trellis better suited for decoding, and a bit-clock FSE (B-FSE) suited for the evaluation of distance spectra, where each transition is labeled with exactly one output bit, see Figure 1.

Details on how these FSEs are obtained can be found in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF]. In the sequel, S r and T r are the set of states and transitions in R-FSE and S b and T b the set of states and transitions in B-FSE.

M r and M b are the number of states in a R-FSE and a B-FSE, respectively.

III. CHARACTERIZATION OF THE ERROR CORRECTING PERFORMANCE

From here on, we consider B-FSE. To evaluate the free distance and the distance spectrum of some JSC-IAC described by a B-FSE Γ b (S b , T b ), techniques inspired from [START_REF] Biglieri | High-level modulation and coding for nonlinear satellite channels[END_REF] are applied to track the distances between pairs of paths in the B-FSE. The product graph Γ 2 b = Γ b × Γ b labeled with Hamming distances (which would yield the product trellis considered in [START_REF] Biglieri | High-level modulation and coding for nonlinear satellite channels[END_REF]) is considered for that purpose. The main difference with [START_REF] Biglieri | High-level modulation and coding for nonlinear satellite channels[END_REF] is that for VL-FSE, states may have a different number of outgoing transitions. Then we show how this product graph may be simplified.

A. Efficient free distance computation

This section describes the generation of the product graph associated to a B-FSE and its simplification to efficiently compute the free distance of the FSC generated by the B-FSE.

(S b , T b ) is the directed graph Γ 2 b (S b × S b , T b × T b ) with M 2 b states s i,j defined as s i,j = (s i , s j ), 0 i, j < M b .
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) . The weight of the edge e, w H (e) is defined as the Hamming distance between the output of the two transitions, u and v, i.e., w H (e) = d H (u, v).

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 defined as

w H (e) = N µ=1 w H (e µ ). (5)
Since Γ b is output bit clock, one has w H (e) N .

Thus, the weight of a directed path in Γ 2 b from a state s i,j to a state s m,n , is the Hamming distance between the output bits of two paths (t

1 , t 2 ) ∈ T k b × T k b .
S div = s i,i ∈ S 2 b : ∃ (u, v) ∈ T 2 b , u = v, such that σ(u) = σ (v) = s i , (6)
S conv = s i,i ∈ S 2 b : ∃ (u, v) ∈ T 2 b , u = v, such that τ (u) = τ (v) = s i . ( 7
)
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 . We merge the states in S div into a single state s in with only outgoing edges. 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 . We merge the states in S conv into a single state s out with only incoming edges. In Figure 2, S div = {s 0,0 , s 2,2 } and S conv = {s 0,0 , s 2,2 }. In Γ 2 b , the set of edges {e = (u, u) : u ∈ T b } corresponds to pairs of paths which have not diverged, therefore, according to Definition 3, this set will be not useful to find

d free . If we replace in Γ 2
b the sets S div and S conv by respectively s in and s out , and we remove the set {e = (u, u) : u ∈ T b }, we obtain a modified product graph (MPG), in which s in is the initial state and s out is the final state, and which still contains all paths needed for the evaluation of d free . The MPG derived from the product graph in Figure 2 is represented in Figure 3. When we explore the MPG from the initial state to the final state the weights of the paths give the Hamming distances in P. Thus finding d free amounts to determining the directed path(s) from s in to s out with smallest weight.

It can be seen that in the MPG, if e 1 is a directed path from s in to s i,j , i = j, then, there is also a directed path e 2 from s in to s j,i such that ℓ(e 1 ) = ℓ(e 2 ) and w H (e 1 ) = w H (e 2 ).

(

) 8
This is so since d H is symmetric in its arguments. Here, we say that the paths e 1 and e 2 in the MPG are equivalent. Thus the complexity can be further reduced by defining a pairwise distance graph (PDG) that contains a single path for each pair of equivalent paths in the MPG. For this end, the two states s i,j and s j,i in the MPG are merged and replaced with a single state s ν,γ Finding d free with this PDG is again the same as finding the directed path(s) from s in to s out with the smallest 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.

(ν = min(i, j), γ = max(i, j)) in
The number of states in PDG, M PDG , is

M PDG = M b × (M b -1) 2 + 2. ( 9
)
M PDG is the maximum number of states explored when Dijkstra's algorithm is applied on PDG to compute d free .

An alternative method to compute the free distance of a JSC-IAC was presented in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF]. It uses a three-dimensional array defined as △ n = (a k,i,j ) 0≤k,i,j<M b , where a k,i,j is the minimum

Hamming distance between all pairs of paths of length n (in code domain) starting from the state s k and ending respectively in the states s i and s j and not having converged. This method is an iterative method over the path length n. The algorithm needs to compare the paths up to n free , which is the path length for which no unmerged pairs of paths with distance less than d free exist. In practical implementations, some upper bound n max for n has to be given to perform the algorithm in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF] in finite time. If n max is too small, no guarantee may be provided that the actual value of d free has been found. This may occur for some codes like catastrophic codes, since such codes contain pairs of codewords with a finite Hamming distance that correspond to neverconverging paths. The computational complexity of this method is

O (n max × |T b | 2 × M r ),

B. Distance spectra in the code domain

This section briefly describes the way an MPG could be labeled such that the distance spectrum in code domain is obtained from a generating function, which may be computed by evaluating a symbolic transfer function, e.g., using Mason's gain formula [START_REF] Mason | Feedback theory : Further properties of signal flow graphs[END_REF]. For this end, we assign to every edge e = (u, v) a gain g(e) defined as

g(e) =      P * (σ(u))P (u)D w H (e) : σ(u) = σ(v), P (u)D w H (e) : σ(u) = σ(v), (10)
where D is a symbolic variable used to track the path weight. Then, applying Mason's gain formula between s in and s out in the MPG allows to obtain a transfer function G(D), which represents the distance spectrum according to (4). In [START_REF] Weidmann | Evaluation of the distance spectrum of variable-length finite-state codes[END_REF] a method to compute the distance spectrum (in code domain) directly using matrices instead of generating functions is proposed.

In this method, the coefficients A d (for 0 ≤ d < ∞) of G(D) are computed one by one. The index of the first non null coefficient gives the value of the free distance. The method in [START_REF] Weidmann | Evaluation of the distance spectrum of variable-length finite-state codes[END_REF] uses a matrix inversion with matrices of size M 2 b × M 2 b to compute the coefficients. This is more complex than using Dijkstra's algorithm. The method described above cannot be applied in the information (source) domain for general variable-length FSCs, since the distances between information sequences need to be expressed using the Levenshtein distance [START_REF] Levenshtein | Binary codes with correction of deletions, insertions and substitution of symbols[END_REF], which is not additive.

IV. OPTIMIZING FINITE-STATE JSC CODES BASED ON ARITHMETIC CODING

This section describes a method to search for error-correcting codes with large free distance.

Our approach is to explore a subset of the set F of all FSEs. F contains the set F u of FSEs which generates uniquely decodable FSCs, which in turn contains the set F JSC-IAC of all FSEs corresponding to JSC-IAC. The latter contains the set F T JSC-IAC of all FSEs representing an IAC followed by an error-correcting code (i.e. classical separate tandem encoding). It also contains the set F M JSC-IAC of all memoryless JSC-IAC, i.e., JSC-IAC whose encoding behavior depends only on the current arithmetic encoder state. For such codes, the encoder behavior can depend on the previously encoded symbols or on the previously generated output bits only indirectly through the state. Some IAC followed by block codes belong to the set F M JSC-IAC , but more general tandem schemes consisting of an IAC followed by a CC do not belong to F M JSC-IAC . For the sake of simplicity, we restrict our exploration to the set F M JSC-IAC . As the set F M JSC-IAC still remains large, it will be interesting to structure it in a way that allows to promptly explore it for the largest d free . This may be done with a tree in which the leaves correspond to complete JSC-IACs (CAs) and internal nodes correspond to incomplete JSC-IACs (IAs). From the root which is the initial IA determined by the values of the characteristic parameters, the tree is generated by successively extending all intermediate IAs as described in Sections IV-B and IV-C. Using Lemma 1 in a branch-and-prune algorithm substantially reduces the time needed to find the best JSC-IAC. The idea of the branch-and-prune algorithm is to successively eliminate large parts of the tree which cannot lead to the optimum d free . This is done by iteratively updating a lower bound d free , of the largest free distance which may be obtained for given values of the characteristic parameters. When exploring the tree, if an IA is reached, its d free is compared to d free . If it is larger, the IA is extended, in the other case, the IA is no more explored, since according to Lemma 1 all IAs and CAs derived from it will have a d free smaller or equal to d free . If a CA is reached and its d free is larger than d free , then d free is updated. Three ways for exploring the tree are considered: depth first exploration, breadth first exploration, and a sort method which extends the IA with the largest d free . Their respective efficiency is compared in Section V. Section IV-A recalls some bases of AC which may be helpful for understanding the tree construction methods. Sections IV-B and IV-C describe the tree construction method for binary input and non-binary input JSC-IAC respectively.

A. Finite-state integer arithmetic coding

The basic idea of binary AC is to assign to every sequence of source symbols a unique subinterval of the unit interval [0, 1). A subinterval of width w is represented by a binary fraction of length at least ⌈log 2 w⌉ bits. The source entropy can be approached by iteratively partitioning the code interval [0, 1) according to the probabilities of the source symbols. Let K be the size of the source alphabet {a 1 , a 2 , . . . , a K }. At the end of some iteration, assume that the code interval is [l, h). At the next iteration, [l, h) is partitioned into K non-overlapping subintervals {I 1 , I 2 , . . . , I K }, the width of I i being proportional to the probability of the symbol a i . The subinterval corresponding to the symbol to encode is then selected as the new code interval. Partitions and selections continue until the last symbol has been processed. The encoder chooses a value in the current code interval, and its binary representation is associated to the sequence of encoded symbols. For sources with skewed probabilities or for long source sequences, subintervals may however get too small to be accurately handled by a finite-precision computer. This problem is solved by IAC.

Binary IAC, also called quasi-arithmetic coding (QAC) [START_REF] Pasco | Source coding algorithms for fast data compression[END_REF], [START_REF] Howard | Practical implementations of arithmetic coding[END_REF] works as the scheme presented above, but the initial interval is replaced by the integer interval [0, T ), where T = 2 P and P is the binary precision (register size) of the encoding device. All interval boundaries are rounded to integers. During the encoding process, the bounds of the interval [l, h) are renormalized as follows

• If h T /2, l and h are doubled.

• If T /2 l, l and h are doubled after subtracting T /2.

• If T /4 l and h 3T /4, l and h are doubled after subtracting T /4.

If the current interval before renormalization overlaps the midpoint of [0, T ), no bit is output.

The number of consecutive times this occurs is stored in a variable f (for follow). If the current interval before renormalization lies in the upper or lower half of [0, T ), the encoder emits the leading bit of l (0 or 1) and f opposite bits (1 or 0). This is called follow-on [START_REF] Witten | Arithmetic coding for data compression[END_REF].

Since the IAC encoding process can be characterized by [l, h) and f (and the source probabilities), the state of the automaton representing the encoder may be defined as (l, h, f ). If the value of f is bounded, it is possible to precompute all the reachable states and the transitions between them, thus yielding a FSE. In general, f may grow without bounds, but it can be easily limited to f f max , as in [START_REF] Bi | State machine interpretation of arithmetic codes for joint source and channel coding[END_REF]. The present work takes the approach of [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF]: whenever f = f max and the current source interval is such that f could be further incremented, the symbol probabilities are temporarily modified to force a follow-on after encoding the current symbol.

B. A tree of binary input JSC-IAC automata

Consider a source X with alphabet A = {a 0 , a 1 } and pr(X = a 0 ) = p 0 and pr(X = a 1 ) = p 1 .

Let (l, h, f ) be the current state of the encoder and w = h -l be the width of the current code interval. During encoding, [l i , h i ) is the subinterval of width w i = h i -l i assigned to a i , i = 0, 1.

As mentioned in Section I, a JSC-IAC may be derived from an IAC by considering FSs. In the case of a single FS, let p be the "probability" of the FS and w ε be the width of the subinterval assigned to it. Given p ε and p 0 , the widths of the subintervals of the code interval [l, h) are computed as follows

w ε = p ε × w , (11)
w 0 = p 0 × (h -l -w ε ) , (12)
w 1 = h -l -w 0 -w ε , (13)
where • means rounding towards the nearest integer. In a more general case, the probability of the FS may be split among up to three FSs {ε 0 , ε 1 , ε 2 }, with corresponding probabilities

{p ε 0 , p ε 1 , p ε 2 } such that p ε 0 + p ε 1 + p ε 2 = p ε . 6
shows how the code interval may be partitioned during the coding process in the case of a JSC-IAC with 3 FSs. The way p ε is distributed among {ε 0 , ε 1 , ε 2 } may be state-independent, i.e., independent of the values of l, h, and f , or it may be state-dependent, in which case, the order of the subintervals assigned to source symbols may also change. Considering a state-dependent FS probability assignment provides a large design freedom allowing to build automata potentially leading to better codes than those obtained with a state-independent design, already considered in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF]. However, to the best of our knowledge, no analytical method is known to find the optimal state-dependent probability assignment.

The set of all encoders can be obtained by iteratively exploring the successors of all states, starting from the IA with state (l = 0, h = T, f = 0), for every admissible configuration of the subintervals [l 0 , h 0 ) (associated to a 0 ) and [l 1 , h 1 ) (associated to a 1 ) of [l, h). This may be done by letting both l 0 and l 1 vary from l to h -1 in steps of one. Then one may check whether one of the following conditions is satisfied.

l l 0 < (h 0 = l 0 + w 0 ) l 1 < (h 1 = l 1 + w 1 ) h, (14)
l l 1 < (h 1 = l 1 + w 1 ) l 0 < (h 0 = l 0 + w 0 ) h. (15)
Each time [START_REF] Forney | Geometrically uniform codes[END_REF] or [START_REF] Zehavi | On the performance evaluation of tellis codes[END_REF] are satisfied, a new IA or CA is derived from the previous IA by supplementing it with two states (obtained from [l 0 , h 0 ) and [l 1 , h 1 ) after appropriate renormalizations) if they do not already exist. The resulting IAs are then explored in turn. From the initial IA with state (l = 0, h = T, f = 0), the expansion of IAs gives a tree of automata in which all internal nodes corresponds to IAs and leaves correspond to CAs and each edge corresponds to the exploration of an unexplored state.

Figure 7 shows how all possible automata for a given value of the characteristic parameters and with a state-dependent FS probability assignment may be described by a tree. The initial IA consists of the unexplored state (0, T, 0) shared by all automata. It forms the root of the tree.

Each node in the first layer of internal nodes represents an IA for which a given configuration of the subintervals of the initial code interval have been considered. Figure 8 shows an example of a tree of automata for the characteristic parameters T = 8,

f max = 1, p 0 = 1 4
, and p ε = 1 2 . The circles labeled s 0 , s 1 , . . . represent the states of the IA or CA. They are shaded for unexplored states. The initial incomplete automaton IA 0 consists of the initial state s 0 = (0, 8, 0). One possible manner to extend the initial state is to assign to a 0 the interval [0, 1) and to a 1 the interval [START_REF] Shannon | A mathematical theory of communication[END_REF][START_REF] Viterbi | Principles of Digital Communication and Coding[END_REF] leading to the second incomplete automaton IA 1 . The last possible extension of the initial state assigns to a 0 the interval [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF][START_REF] Elias | Coding for noisy channels[END_REF] and to a 1 the interval [4, 7) yielding the incomplete automaton IA N . Iterating this approach, one may get CAs such as the one shown shaded on the bottom left side of the tree.

C. Extension to non-binary input JSC-IAC

For sources with K > 2 symbols, extending the interval subdivision presented in Section IV-B would require to consider at most K + 1 FSs. Allowing state-dependent assignment of the probabilities of the FSs may lead to a very high number of automata for given values of the characteristic parameters. Nevertheless, in practice most (if not all) source coding standards involving arithmetic codes introduce a binarization step of the non-binary symbols to encode before binary input arithmetic coding [START_REF] Richardson | 264 and MPEG-4 Video Compression: Video Coding for Next-Generation[END_REF]. This allows the use IAC with reduced precision, compared to non-binary input ACs. Instead of a single source probability model, several (adaptive) probability models are considered and chosen depending on some context, corresponding here to the index of the bit to encode in a binarized symbol. The methods described in Section IV-B are thus extended for binarized sources with K > 2 symbols, accounting for some simple context, with non-adaptive probability model.

Let X be a memoryless source with alphabet A K = {a 1 , . . . , a K } and corresponding set of symbol probabilities P a = {p a 1 , . . . , p a K }. Without loss of generality, assume that p a i ≥ p a i+1 , i = 1, . . . , K.

A binarization of A K may be done as follows. Consider first some x ∈ N and L ∈ N * such that L ≥ ⌈log 2 (x)⌉. Let B L (x) be the binary representation of the integer x on L digits. For I shows the probability of occurrence [START_REF] Buttigieg | Variable-length error correcting codes[END_REF] and the bit assignment for each symbol in A 26 . The entropy of a memoryless source X generating symbols according to the probabilities given in Table I is H(X) = 4.175 bits/symbol. Now denote a j i , i = 1, . . . , K and j = 1, . . . , L K be the j-th bit in the binary representation of a i . To avoid confusion with the output bits of the AC, a j i is called a symbol. Let p j b for b ∈ {0, 1} and j = 1, . . . , L K be the probability that a j i = b. One has p j b = K i=1 p a i δ(a j i -b), where δ(x) is the indicator function (δ(x) = 1 if x = 0 and δ(x) = 0 else). One has of course p j 0 + p j 1 = 1. The entropy of a memoryless binary source X j 2 generating the j-th bit of a binarized symbol with probability model p j 0 , p j 1 may easily be evaluated. The entropy of the source after binarization is then

instance B 3 (1) = 001. Now consider L K ∈ N * such that L K ≥ ⌈log 2 (K)⌉. For each symbol a i ∈ A K , B L K (i -1) is a possible binary representation.
L(K) 1 H(X j
2 ). Example 2: For A 26 , p 1 0 = 0.0963; p 2 0 = 0.269; p 3 0 = 0.379; p 4 0 = 0.432; p 5 0 = 0.455 and 5 1 H(X j 2 ) = 4.237 bits/non-binarized symbol, which is greater than H(X). Using an AC involving five independent probability models for memoryless binary sources leads thus to some loss in efficiency compared to an AC directly handling a K-valued source.

With a context corresponding to the index of the bit to encode in the binarized source symbol, the symbol a j i will be arithmetic coded with the probability model p j 0 , p j 1 . In the FSE, this requires keeping track of the context by supplementing the state {l, h, f } with the value of the context to get the new state {l, h, f, j}, with j = 1, . . . , L K . As a consequence, the number of states of the FSE is multiplied by L K when considering such context. When designing an JSC-IAC, one usually tries to reach some target source-channel coding rate R c . For that purpose, a "probability"

p j ǫ = 1 -2 -(Rc-H(X j 2 )) (16)
is assigned to each context j. The characteristic parameters of a JSC-IAC are then T , f max , P a , and R c . As in Section IV-B, the set of all encoders which may be obtained by a state-dependent assignment of the FS probabilities may be obtained by iteratively exploring the successors of all states of IAs, starting with the IA having the single state (l = 0, h = T, f = 0, j = 1), for every admissible configurations of the subintervals of a unexplored state.

D. Complexity issues

It would useful for the branch-and-prune algorithm to find a relation between the characteristic parameters and the computational time for finding the best automaton. However, this is very difficult, since the number of automata generated depends on these parameters in intricate ways. One may compute an upper bound on the number of states per automaton and thus on the number of distinct automata, but this upper bound will likely be too loose to be useful. An additional difficulty resides in estimating the time required by the algorithm for computing the free distance of an automaton. Again, this is extremely difficult to estimate from the parameters without building the actual FSE.

V. EXPERIMENTAL RESULTS

Two sets of experiments are conducted. First, simple binary sources are considered, allowing an easy evaluation of the efficiency of the branch-and-prune algorithm compared to an exhaustive search for the best FSE. Dijkstra's algorithm-based free distance evaluation is compared to the method proposed in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF]. Various tree traversal algorithms are then compared. Second, a JSC-IAC for the binarized English alphabet is provided.

A. JSC-IAC for binary sources

A first binary-input JSC-IAC with characteristic parameters T = 8, f max = 1, p 0 = 0.1, and a design R c = 0.62 bits/symbol (p ε = 0.1) is considered first. The time needed to generate all possible automata with a state-dependent assignment of the FS probabilities, to compute their free distance and select the best one is 6300 s. Using the branch-and-prune algorithm with breadth-first exploration, the time needed to find the largest d free is only 25 s, resulting in a time saving of 99.6%. In both cases, free distances are evaluated with the technique of [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF]. This first experiment has been done on an Intel Core 2 Duo at 2.66 Ghz with 1 Gb memory.

A second binary-input JSC-IAC with characteristic parameters T = 16, f max = 1, p 0 = 0.1, and a design R c = 0.91 bits/symbol (p ε = 0.27) is now considered. An exhaustive exploration for such JSC-IAC would be unreasonably time-consuming. Table II shows the time (in seconds)

needed with a depth-first exploration, a breadth-first exploration, and the sort method described in Section IV to find the best automaton. The free distance evaluation method of [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF] is compared to that presented in Section III. |S r | and |T r | denote the number of states and the number of transitions of the corresponding R-FSE. These numbers depend on the exploration method, since several FSCs may have the same d free , without necessarily having the same number of states or transitions. The coding rate is expressed in bits/symbol. The sort method is the best in terms of computing time. This is mainly due to the fact that this method explores first the IA with the highest potential to have a large d free , so that d free may rapidly increase. Having a large value of d free at the beginning of the algorithm facilitates pruning large parts of the tree without exploring them. It can also be seen that using Dijkstra's algorithm to compute d free is much more efficient than using the method in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF].

Compared to an equivalent tandem scheme (IAC followed by a Convolutional Code (CC))

with the same coding rate, the free distance of the obtained JSC-IAC remains suboptimal. For the example of Table II, consider a R c = 91 bits/symbol equivalent tandem scheme with an IAC with T = 16, p 0 = 0.1, p ε = 0, followed by a rate 1/2 CC. The free distance of the tandem scheme depends on the constraint length of the CC. For constraint length 2 (respectively 3), the best d free of a rate 1/2 CC is 4 (respectively 5) [START_REF] Proakis | Digital Communications[END_REF]Chapter 8]. The weakness of the JSC-IAC is mainly due to its small effective memory (which is related to the set of states), that is more geared towards good compression than towards large d free . The minimum number of states for the best obtained FSE in the JSC-IAC case is 2 (Table II), while in the tandem scheme, the total number of states is the product of the number of states of the IAC and the number of states of the CC(at least 2). Hence, the joint scheme will be less complex than the tandem scheme.

In Table II one notes a slight variation of the effective coding rate, which are due to rounding

It also shows that the proposed branch-and-prune algorithm (using the Sort Method) is a fast way to find the JSC-IAC with largest d free for binary sources. Using an appropriate binarization process prior to AC and using several probability models, this method may be extended to the design of JSC-IAC for non-binary sources.

Nevertheless, at fixed code rate, the codes obtained for the time being remain less efficient than equivalent tandem schemes. Future work will consider the extension of JSC-IAC with an m-bit memory which may improve d free by separating paths that would lead to small distances.

The memory holds an integer 0 ≤ ≤ 2 m -1, so that the FSE state can be represented as (l, h, f, λ). The set of FSEs of JSC-IAC with memory m contains the set of tandem schemes with CC with constraint length m + 1. Therefore one may expect to find at least FSEs with performance (compression, d free ) equivalent to the tandem schemes, but hopefully less complex (regarding the number of states and transitions). Initial unexplored state ((l 1 0 , h 1 0 ), (l 1 1 , h 1 1 )) ((l N 0 , h N 0 ), (l N 1 , h N 1 ))

IA 1 IA 2 IA 3 IA N IA 1,1 IA 1,ν IA 2,1 IA 2,γ

A

  . Diallo is with the L2S -CNRS -SUPELEC -Univ Paris-Sud, France. C. Weidmann is with INTHFT, Vienna University of Technology, Vienna, Austria. M. Kieffer is with Telecom ParisTech, Paris, France, on leave from L2S. This work was supported by the European Commission in the framework of the FP7 Network of Excellence in Wireless COMmunications NEWCOM++ (contract n. 216715). Parts of this paper have been presented at EUSIPCO 2009.

( 1 ) 1 :

 11 free , respectively. We define the relation C 0 C 1 , meaning that all elements in C 0 are prefixes of elements in C 1 . If C 0 C 1 , an important property following directly from Definitions 3 Let C 0 and C 1 be two (incomplete) codes such that C 0 C 1 . Then d free (C 0 ) d free (C 1 ).

  Consider the set of states S b = {s i : 0 i < M b } and the set of transitions T b of the directed graph Γ b (S b , T b ) representing some B-FSE. The product graph associated to Γ b

  Figure 1 (b). The edges in Figure 2 are labeled with their weight. Since, for the evaluation of d free one is only concerned with paths in Γ 2 b belonging to P, we can derive from Γ 2 b a modified product graph (MPG) that represents only these paths. Consider the two sets of states S div ⊂ S 2 b and S conv ⊂ S 2 b such that

  the PDG, and the two directed edges (u, v) and (v, u) (with u ∈ T b and v ∈ T b ) in MPG are replaced by a single edge in the PDG. The PDG derived from the MPG in Figure 3 is represented in Figure 4.

  while the worse complexity of applying Dijkstra's algorithm on a PDG is O(M 2 PDG ). With a better implementation of Dijkstra's algorithm using Fibonacci heaps, the complexity may be reducedto O(|T PDG | + M PDG × log(M PDG )), where T PDG is the set of edges in PDG. The existence of catastrophic pairs of paths implies a zero-weight (directed) loop in the PDG and vice-versa. For instance in Figure5(a) the codewords obtained by (s 0 , s1 , s 3 , • • • , s 3 ) and (s 0 , s 2 , s 4 , • • • , s 4 )have Hamming distance one. Dijkstras algorithm has no problems with such codes, since during the process, each edge of the PDG is explored at most once.

Example 1 :

 1 Consider the 26 letters of the English alphabet A 26 . Then K = 26 and L K = 5 bits. Table

Fig. 1 . 2 s 3 , 3 Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 . 2 Fig. 6 .

 1233234526 Fig. 1. Example of an incomplete automaton (a) and a complete automaton (b) derived from the automaton (a)

CA 0 :Fig. 7 .Fig. 8 . 4 ,

 0784 Fig. 7. All automata for given values of characteristic parameters on a tree

TABLE I PROBABILITY

 I OF OCCURENCE OF EACH LETTER IN ENGLISH ALPHABET TAKEN FROM[START_REF] Buttigieg | Variable-length error correcting codes[END_REF] AND EXAMPLE OF

		BINARIZATION
	Methods	depth-first	breadth-first	sort method
	|Sr|	8	2	3
	|Tr|	28	9	12
	d free	3	3	3
	Rc	0.93	0.92	0.92
	Time with [7]	451266 s	31338 s	12431 s
	Time with PDG	734 s	219 s	45 s

TABLE II COMPARISON

 II BETWEEN THE THREE METHODS TO EXPLORE THE TREE FOR T = 16, P0 = 0.1, Pε = 0.26

effects in finite-precision IAC. This second experiment and the followings have been done on an Intel Xeon E5420 at 2.50GHz with 64 Gb memory.

B. JSC-IAC for non-binary sources

Now, our aim is to optimize a JSC-IAC for the binarized English alphabet A 26 given in Table I. To reduce the number of IAs and CAs to build in the tree of automata, only two values of the context are considered. The first corresponds to the first bit index and the second to the remaining bit indexes. Two probability models are then considered, namely {p 1 0 , p 1 1 } and

The probability p 2:5 ε assigned to the context 2 : 5 can be obtained with [START_REF] Buttigieg | Variable-length error correcting codes[END_REF]. To further simplify the search for a good code, the FS probability assignment is state-dependent, but is not allowed to vary for a given value of the context. This significantly reduces the amount of different automaton which may be built for a given value of the characteristic parameters taken now as

, and a design R c = 14 bits/symbols. Dijkstra's algorithm is used to compute d free and the sort method is used in the branch-andprune algorithm. The best code has d free = 6 and R c = 13.9 bits/symbols. The time needed to find this code is 1425 s. JSC-IAC code design is thus possible even for large alphabet sizes, provided that a binarization process is considered. However, the reduced number of contexts and the constraints imposed on the FSs lead to a JSC-IAC which is less efficient than that proposed in [START_REF] Buttigieg | Variable-length error correcting codes[END_REF], where a JSC-VLC for A 26 with d free = 5 and R c = 10.41 bits/symbols is obtained.

Improvements may be obtained by considering more contexts and by allowing more variations of the state-dependent assignments of the FS probabilities. However, the price to be paid is a higher computational complexity. The considered branch-and-prune algorithm may be strongly parallelized, which may help addressing this issue.

VI. CONCLUSION

This paper has shown how established graph transfer function methods for fixed-rate channel codes can be generalized to compute the free distance and the distance spectrum of VL-FSC.

The resulting method for computing the free distance is much more efficient than the method for JSC-IAC presented in [START_REF] Ben-Jamaa | Analytical tools for optimizing the error correction performance of arithmetic codes[END_REF] and does not have problems dealing with catastrophic codes.


François Buret

Monique Dauge

Patrick Dular

Laurent Krähenbühl

Victor Péron

Ronan Perrussel

Clair Poignard
email: clair.poignard@inria.fr

Damien Voyer

à la diffusion de documents scientifiques de niveau

recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

The aim of this work is to introduce a method to tackle a magneto-harmonic problem in a bidimensional setting where the conducting medium is non-magnetic and has a corner singularity. More precisely, denote by Ω -the bounded domain corresponding to the conducting non-magnetic material, and by Ω + the surrounding dielectric material (see Fig. 1(a)). The domain Ω is then defined by Ω = Ω -∪ Ω + ∪ Σ, where Σ is the boundary of Ω -. The boundary of Ω is denoted by Γ. For the sake of simplicity, we assume that: (H1) Σ has only one geometric singularity, and we denote by C this corner. The angle of the corner (from the conducting material, see Fig. 1(a)) is denoted by ω. (H2) the current source term J is located in Ω + and it vanishes in a neighborhood of C.

Γ Ω + Σ C Ω - ω C Corner detail ρ θ = 0 θ = ω θ (a)
Model domain for the heuristics. Throughout the paper ρ denotes the distance to the corner and θ is the angular variable (see Fig. 1). Moreover the notations [u] Σ = u + |Σ -u - |Σ and ∂ n = n • ∇ are used, n being the normal to Σ inwardly directed from Ω + to Ω -. The skin depth δ = 1/(πf σµ 0 ) is supposed to be small compared to the characteristic length of the domain. In the expression of δ, f is the frequency of the source term, σ is the conductivity, and µ 0 is the vacuum magnetic permeability. The magnetic

θ = 0 σ = 1 πf µ 0 δ 2 θ ρ C ∂ n A δ = 0 A δ = 1
vector potential A δ (reduced to one scalar component in 2D) satisfies              -∆A + δ = µ 0 J in Ω + , -∆A - δ + 2i δ 2 A - δ = 0 in Ω -, [A δ ] Σ = 0 on Σ, [∂ n A δ ] Σ = 0 on Σ, A + δ = 0 on Γ. (1)
Denote by A 0 the potential in the perfectly conducting case:

   -∆A + 0 = µ 0 J in Ω + , A + 0 = 0 on Σ, A + 0 = 0 on Γ, A - 0 = 0 in Ω -. (2)
It is intuitive that A + 0 approximates A δ in the dielectric medium. Moreover, it can be proved for a regular interface Σ that the "power norm" [START_REF] Schmidt | Estimating the Eddy-Current modeling error[END_REF] of the error A δ -A 0 is of order δ [START_REF] Caloz | Uniform estimates for transmission problems with high contrast in heat conduction and electromagnetism[END_REF]. This accuracy is no more valid for a corner singularity. Our aim is to propose a rigorous method to recover the order δ by adding an appropriate correction in the neighborhood of the corner. Note that Yuferev et al. in [START_REF] Yuferev | Surface impedance boundary conditions near corner and edges: Rigorous consideration[END_REF] have considered a similar problem using a formal approach of transmitted singularities. Their work aimed at "correcting" the method proposed by Deeley [START_REF] Deeley | Surface impedance near edges and corners in threedimensional media[END_REF]. However we are confident that the heuristics of [START_REF] Yuferev | Surface impedance boundary conditions near corner and edges: Rigorous consideration[END_REF] lead to non relevant results. This is detailed in Section III.

In the following, we present the heuristics of the treatment of the singularity, that lead to the accurate approximation of A δ as δ goes to zero, and we conclude by numerical experiments.

II. HEURISTICS OF THE EXPANSION

Let first note the two following remarks:

• similarly to the regular case, A 0 defined by ( 2) is the solution of the limit problem of (1) as δ goes to zero. Hence the first term of the expansion should start by A 0 . • since the respective behaviors of A δ and A 0 are different in the corner for any non zero δ, it seems natural to truncate A 0 in the corner by a function ϕ which is zero close to the corner and 1 far from this corner. Suppose that we introduce such a smooth radial cut-off function:

ϕ(ρ) = 1, if ρ ≥ d 1 0, if ρ ≤ d 0 , with d 0 < d 1 , (3)
d 0 , d 1 being fixed corner distances. If ϕA 0 is taken as the first term for approximating A δ , it will obviously not converge to A 0 as δ goes to zero. However if ϕ(•/δ)A 0 is considered instead, the correct limit is obtained. According to these remarks, consider the problem satisfied by r δ 0 = A δ -ϕ(./δ)A 0 :

-

∆r δ 0 = [∆; ϕ (./δ)] A + 0 , in Ω + , r δ 0 | Γ = 0, on Γ, (4a) -∆r δ 0 + 2i δ 2 r δ 0 = 0, in Ω -, (4b)
r δ 0 Σ = 0, ∂ n r δ 0 Σ = -∂ n ϕ(./δ)A + 0 , on Σ, (4c)
where for any couple (ν, u), [∆; ν]u = ∆(νu) -ν∆u. Note that assumption (H2) is necessary to obtain (4a). If we were not to use the cut-off function ϕ in the corner, therefore the jump ∂ n r δ 0 Σ would be equal to -∂ n A + 0 | Σ , which blows up in the corner. Since [∂ n A δ ] Σ identically vanishes in the corner on Σ we would have to compensate this blowing term, which would lead to numerical difficulties. The use of ϕ(./δ) in (4c) ensures that ∂ n r δ 0 Σ vanishes in the corner. Solving exactly (4) provides no benefits, but since

A + 0 ≃ ρ→0 a 1 ρ α sin(αθ) = a 1 s α where α = π/(2π -ω), ( 5
)
we guess a correction in the corner region such that the expansion becomes

A δ = ϕ(•/δ)A 0 + (1 -ϕ)a 1 δ α V α (•/δ) + r δ α . (6)
In ( 6), the "profile" term V α is the solution of a problem in R 2 that is independent of A 0 and δ while r δ α lives in the domain Ω. To determine the problem solved by V α , from ( 5) we first replace A + 0 by s α in ( 4). Then we use the fact that ϕ depends only on ρ and that ∂ n = ±(1/ρ)∂ θ near the corner, and we perform the rescaling X = x/δ (R = ρ/δ). Taking the limit when δ goes to zero (Γ is thus "sent" to the infinite) leads to the "profile" problem satisfied by V α in R 2 , which is divided into two infinite sectors S + and S -(remember that X = (R cos(θ), R sin(θ)) with R > 0):

-∆ X V α = [∆ X ; ϕ] s α , in S + = {X : θ ∈ (ω, 2π)}, (7a) -∆ X V α + 2iV α = 0, in S -= {X : θ ∈ (0, ω)}, (7b) V α → |X|→+∞ 0, (7c)
with the transmission conditions on G = {X : θ = 0, ω} :

[V α ] G = 0, [∂ n V α ] G = αϕR α-1 . ( 7d
)
Capturing the singularity of the domain in a profile term is quite natural and has to be linked up similarly to [START_REF] Ciuperca | Influence of a Rough Thin Layer on the Steady-state Potential[END_REF], [START_REF] Krähenbühl | Numerical treatment of rounded and sharp corners in the modeling of 2D electrostatic fields[END_REF]. The theoretical proof that r δ α is of order δ needs more than two pages, and will be presented in a forthcoming paper.

III. NUMERICAL RESULTS

The domain presented in Fig. 1(b) is considered for numerical purpose. The errors |r δ 0 | and |r δ α | are plotted respectively on Fig. 2(a) and 2(b). The terms A δ , a 1 , A 0 and V α are computed by using the finite element method as in [START_REF] Krähenbühl | Numerical treatment of rounded and sharp corners in the modeling of 2D electrostatic fields[END_REF] where an electrostatic problem on a geometry with a rounded corner is considered. On both figures, the same color scale is used except the white area around the corner on Fig. 2(a) where the error is higher (between 0.04 and 0.14). Fig. 2(b) shows the profile correction (7): the highest error lies now in the regular part of the interface Σ, for which correction is known [START_REF] Caloz | Uniform estimates for transmission problems with high contrast in heat conduction and electromagnetism[END_REF].

Suppose that a 1 = 0, which is the worst corner influence, and denote by Z s = (1 + i)/(σδ) the regular surface impedance. According to the expansion, the surface impedance Z δ can be approximated close to the corner by:

Z δ = Z s 1 + i δ A δ ∂ n A δ ≃ ρ→0 Z s (1 + i) V α (•/δ) (∂ n V α )(•/δ) , (8)
therefore for any σ and f such that δ is small enough, the function Z δ (δ•)/|Z s | behaves close to zero as √ 2iV α /(∂ n V α ). These similar behaviors are shown on Fig. 3 where the "impedance" from the profile function is compared to the real impedance for two values of δ, where f and σ are different. According to [START_REF] Yuferev | Surface impedance boundary conditions near corner and edges: Rigorous consideration[END_REF], the surface impedance should blow up like ρ -1 for any non zero δ, which is shown to be false here.

1 1 . 5 (

 15 b) L-shape dielectric domain and boundary conditions for the example.

Fig. 1 .

 1 Fig. 1. Geometry of the problems considered.

  (a) |r δ 0 |. (b) |r δ α |. Fig. 2. Modulus of the errors between the solution and the two first orders of (6) for δ = 0.025. The distances of (3) are d 0 = 1 and d 1 = 1.2.

Fig. 3 .

 3 Fig. 3. Behavior of Z δ /|Zs| vs ρ/δ. The domain characteristic length L is here 0.1m, then δ/L is between 2 and 4.6% for the situations considered.