Gérard Henry

Edmond Duchamp

Hadj Hatem

Eric Kacem

Laugerotte

Gérard H E Duchamp
email: gerard.duchamp@lipn.univ-paris13.fr

Hatem Hadj Kacem
email: hatem.hadj-kacem@univ-rouen.fr

Éric Laugerotte
email: eric.laugerotte@univ-rouen.fr

Algebraic Elimination of epsilon-transitions

Keywords: Automata with multiplicities, ε-transitions, behaviour, star of matrices

Introduction

Automata with multiplicities (or weighted automata) are a versatile class of transition systems which can modelize as well classical (boolean), stochastic, transducer automata and be applied to various purposes such as image compression, speech recognition, formal linguistic (and automatic treatment of natural languages too) and probabilistic modelling. For generalities over automata with multiplicities see [START_REF] Berstel | Rational Series and Their Languages[END_REF] and [START_REF] Kuich | Semirings, Automata, Languages[END_REF], problems over identities and decidability results on these objects can be found in [START_REF] Krob | The equality problem for rational series with multiplicities in the tropical semiring is undecidable[END_REF], [START_REF] Krob | Some automata-theoretic aspects of Min-Max-Plus semirings[END_REF] and [START_REF] Krob | Algorithms, automata, complexity and games[END_REF].

A particular type of these automata are the automata with ε-transitions denoted by k-ε-automata which are the result, for example, of the application of Thompson method to transform a weighted regular expression into a weighted automaton [START_REF] Laugerotte | Weighted recognition[END_REF].

The aim of this paper is to study the equivalence between k-ε-automata and k-automata. Indeed, we will present here an algebraic method in order to compute, for a weighted automaton with ε-transitions (choosen in a suited class) an equivalent weighted automaton without ε-transitions which has the same behaviour. Here, the closure of ε-transitions implies the existence of the star of transition matrix for ε. Its running time complexity is deduced from that of the matrix multiplication in k n×n . In the case of wellknown semirings (like boolean and tropical), the closure is computed in O(n 3 ) [START_REF] Mohri | Generic ε-Removal Algorithm for Weighted Automata[END_REF]. We fit the running time complexity to the case when k is a ring.

The structure of the paper is the following. We first recall (in Section 2) the notions of a semiring and the computation of the star of matrices.

After introducing (in Section 3 ) the notions of a k-automaton and k-ε-automaton, we present (in Section 4 and 5 ) our principal result which is a method of elimination of ε-transitions and show particular cases of series on which our result can be applied. In Section 6 , we give the equivalence between the two types of automata and discuss its validity. A conclusion section ends the paper.

In the following, a semiring (k, ⊕, ⊗, 0 k , 1 k ) is a set together with two laws and their neutrals. More precisely (k, ⊕, 0 k ) is a commutative monoid with 0 k as neutral and (k, ⊗, 1 k ) is a monoid with 1 k as neutral. The product is distributive with respect to the addition and zero is an annihilator (0 k ⊗ x =

x ⊗ 0 k = 0 k ) [START_REF] Hebisch | Semirings -Algebraic Theory and Applications in computer Science[END_REF]. For example all rings are semirings, whereas (N, +, ×, 0, 1), the boolean semiring B = ({0, 1}, ∨, ∧, 0, 1) and the tropical semiring T = (R + ∪ {∞}, min, +, ∞, 0) are well-known examples of semirings that are not rings. The star of a scalar is introduced by the following definition:

Definition 1 Let x ∈ k, the scalar y is a right (resp. left) star of x if and only if (x ⊗ y) ⊕ 1 k = y (resp. (y ⊗ x) ⊕ 1 k = y).
If y ∈ k is a left and right star of x ∈ k, we say that y is a star for x and we write y = x .

Remark 1 Left or right stars need not exist and need not coincide (see examples below).

Example(s) 1

(1) For k = C, any complex number x = 1 has a unique star which is y = (1x) -1 . In the case |x| < 1, we observe easily that y = 1

+ x + x 2 + • • •.
(2) Let k be the ring of all linear operators (R[x] → R[x]). Let X and Y α defined by X(x 0 ) = 1,

X(x n ) = x n -nx n-1 with n > 0 and Y α (x n ) = (n+1) -1 x n+1 +α with α ∈ R. Then XY α +1 = Y α
and an infinite number of solutions exist for the right star (which is not a left star if α = 0).

(3) For k = T (tropical semiring), any number x > 0 has a unique star y = 1.

We can observe that if the opposite -x of x exists then right (resp. left) stars of x are right (resp. left) inverses of (1 ⊕ (-x)) and conversely. Thus, if they exist, any right star x r equals any left star x l as

x l = x l ⊗ ((1 ⊕ (-x)) ⊗ x r ) = (x l ⊗ (1 ⊕ (-x))) ⊗ x r = x r .
In this case, the star is unique.

If Q is a finite set, the space k Q×Q of square matrices with indices in Q and coefficients in k has a natural semiring structure with the usual operations (sum and product where

a 11 ∈ k Q1×Q1 , a 12 ∈ k Q1×Q2 , a 21 ∈ k Q2×Q1 and a 22 ∈ k Q2×Q2 such that Q 1 + Q 2 = Q. Let N ∈ k Q×Q given by N = A 11 A 12 A 21 A 22 with A 11 = (a 11 + a 12 a 22 * a 21 ) * (1)
A 12 = a 11 * a 12 A 22 (2)
A 21 = a 22 * a 21 A 11 (3)
A 22 = (a 22 + a 21 a 11 * a 12 ) * (4)

Theorem 1 If the right hand sides of formulas ( 1), ( 2), ( 3) and ( 4) are defined, the matrix M admits N as a right star.

Proof. Suppose, without loss of generality, that (i) In [START_REF] Heyting | Die Theorie der Linearen Gleichungen in einer Zahlenspezies mit nichtkommutativer Multiplikation[END_REF] and [START_REF] Richardson | Simultaneous Linear equations over a division ring[END_REF], similar formulas are expressed for the computation of the inverse of matrices when k is a division ring (this can be extended to the case of rings).

Q = [1, n] N ; n = p + q; Q 1 = [1, p] N ; Q 2 = [p + 1, p + q] N .
It must be emphasized that the converse of Theorem [START_REF] Berstel | Rational Series and Their Languages[END_REF], of course, does not hold as shows the example below (the coefficients are taken in a ring and here the star is unique). (iii) When all their terms are defined, formulas above (as well as ( 1), ( 2), ( 3) and ( 4) where n ∈ 2N + 1. The dynamic peeling [START_REF] Huss-Lederman | Implementation of Strassen's Algorithm for Matrix Multiplication[END_REF] consists of cutting out the matrix in the following way:

M = 1 -1 1 -1 M * = 2 -1 1 0 (5
)
a 11 is a (n -1) × (n -1) matrix, a 12 is a (n -1) × 1 matrix, a 21 is a 1 × (n -1)
matrix and a 22 is a scalar.

If desired, formulation of Theorem (1) can be seen as recursive in essence. In this respect, it implies that stars of submatrices could be already computed by the same scheme. This type of computation will be formalized by the notion of admissible tree of computation which we describe below. Let Q be a finite set and A[Q] be the set of binary trees with leaves in Q. It can be defined by the grammar

A[Q] = Q + (A[Q], A[Q]) (6)
or, if one prefers a graded version

A 1 [Q] = Q A n [Q] = i+j=n (A i [Q], A j [Q]) if n ≥ 2. Now, the list of leaves of a tree T ∈ A n [Q] is a word lv(T ) ∈ Q n defined by lv(T ) = T if T ∈ A 1 [Q] lv(T ) = lv(T 1 )lv(T 2 ) (concatenation) if T = (T 1 , T 2 ).
The set of leaves of T is then alph(lv(T )), where alph(w) is classically the alphabet of the word w. We will say that T ∈ A[Q] is an admissible tree of computation for M ∈ k Q×Q if 1. the word lv(T ) is standard (with no repetition) and contains all the indices (i.e. |lv(T )| = |Q| and

alph(lv(T )) = Q) 2. if |Q| = 1 (thus M ∈ k Q×Q k is a scalar), M admits a star in k Q×Q 3. • if |Q| ≥ 2, set T = (T 1 , T 2 ) and Q i = lv(T i ) (i = 1, 2)
then T 1 is admissible for the submatrix M Q1×Q1 and T 2 is admissible for the submatrix M Q2×Q2 .

• formulas above (1), ( 2), ( 3) and ( 4) are defined for the partitionning

Q = Q 1 + Q 2 .
The conditions above assures that the recursive computation of Theorem ( 1) is defined at each step and, in this case, we will say that the star of M is computed along the (admissible) tree of computation T .

Theorem 2 Let k be a semiring, M ∈ k Q×Q a square matrix and T a tree of computation admissble for M . Then, the right star of a matrix of size n ∈ N can be computed in O(n ω ) operations with:

• ω ≤ 3 if k is not a ring, • ω ≤ 2.808 if k is a ring, • ω ≤ 2.376 if k is a field. Proof. For n = 2 m ∈ N, let T + m , T × m and T *
m denote the number of operations ⊕, ⊗ and in k that the addition, the multiplication and the star of matrix respectively perform with an input of size n. Then

T * 0 = 1 T * m = 2T + m-1 + 8T × m-1 + 4T * m-1 (7)
by Theorem 1. For arbitrary semiring, one has T + m-1 = 2 2(m-1) . If k is a ring, using Strassen's algorithm for the matrix multiplication [START_REF] Strassen | Gaussian Elimination is not optimal[END_REF], it is known that at most n log 2 (7) operations are necessary. If k is a field, using Coppersmith and Winograd's algorithm [START_REF] Coppersmith | Matrix Multiplication via arithmetic progressions[END_REF], it is known that at most n 2.376 operations are necessary. Suppose that T × m-1 = 2 (m-1)ω . The solution of the recurrence relation ( 7) is

4 m + 1 2 (m + 1)4 m - (6 + 2 ω-1 ) 2 ω -4 + 8 • 2 mω 2 ω -4
where the leading term is 2 mω .

Remark 3

In some situations, any tree T with |Q| leaves and standard lv(T ) is admissible. This is the case, for example, of matrices of series without constant term (matrices of proper series [START_REF] Berstel | Rational Series and Their Languages[END_REF]).

The running time complexity for the computation of the right (resp. left) star of a matrix depends on T , T and T , but it depends also on the representation of coefficients in machine. In the case k = Z for example, the multiplication of two integers is computed in O(m log(m) log(log(m))), using FFT if m bits are necessary [START_REF] Schönhage | Schnelle Multiplikation grosser Zahlen[END_REF].

Theorem 3 With the same hypotheses as in (2) (M ∈ k Q×Q a square matrix and T a tree of computation admissible for M ), the space complexity of the right star of a matrix of size n ∈ N is O(n 2 log(n)).

Proof. For n = 2 m ∈ N and k a semiring, let E * m denote the space complexity of operation * that the star of matrix perform with an input of size n. Then

E * 0 = 1 E * m = 12 • 2 2m-1 + 4E * m-1 (8)
The solution of the recurrence relation ( 8) is

-5 • 4 m + (6m + 6)4 m
where the leading term is m • 4 m .

The running of the algorithm needs the reservation of memory spaces for the resulting matrix (the star of the input matrix) and for intermediate results stored in temporary locations.

Let k Σ be the set of noncommutative formal series with Σ as alphabet (i.e. functions on the free monoid Σ * with values in k). It is a semiring equipped with + the sum and • the Cauchy product.

We denote by α(?) and (?)α the left and right external product respectively. The star (?) * of a formal series is well-defined if and only if the star of the constant term exists [START_REF] Kuich | Semirings, Automata, Languages[END_REF][START_REF] Berstel | Rational Series and Their Languages[END_REF].

When Σ is finite, the set RAT k (Σ) is the closure of the alphabet Σ by sums, external and Cauchy products and the star.

Automata with multiplicities

Let Σ be a finite alphabet and k be a semiring. A weighted automaton (or linear representation) of dimension n on Σ with multiplicities in k is a triplet (λ, µ, γ) where:

• λ ∈ k 1×n (the input vector),

• µ : Σ → k n×n (the transition function),

• γ ∈ k n×1 (the output vector).

Such an automaton is usually drawn as a directed valued graph (see Figure 1). A transition (i, a, j) ∈ {1, . . . , n} × Σ × {1, . . . , n} connects the state i with the state j. Its weight is µ(a) ij . The weight of the initial (final) state i is λ i (respectively γ i ). The mapping µ induces a morphism of monoids from Let u = aba. Then, its weight in A is:

Σ * to 1 2 a | 1 a | 3 b | 1 a | 1 b | 4 3 1
λµ(u)γ = λµ(a)µ(b)µ(a)γ = 3 0 3 1 0 1 1 0 0 4 3 1 0 1 0 1 = 21.
The set REC k (Σ) is known to be equal to the set of series which are the behaviour of a k-automaton. We recall the well-known result of Schützenberger [START_REF] Schützenberger | On the definition of a family of automata[END_REF]:

REC k (Σ) = RAT k (Σ).
A k-ε-automaton A ε is a k-automaton over the alphabet Σ ε = Σ ∪ ε (see Figure 2). We must keep the reader aware that ε is considered here as a new letter and that there exists an empty word for Σ * ε = (Σ∪ ε) * denoted here by ε. The transition matrix of ε is denoted µ ε.

Example(s) 3

In Figure 2, the behaviour of the automaton

A ε is behaviour(A ε ) = 18ε i∈N 2 i (aε) i ε = 18ε(2aε) * ε. 1 2 3 ε | 3 3 1 ε | 2 a | 1

Algebraic elimination

Let Φ be the morphism from Σ * ε to Σ * induced by

Φ(x) = x if x ∈ Σ, Φ(ε) = ε.
It is classical that the morphism Φ can be uniquely extended to the polynomials of k Σ ε as a morphism of algebras k Σ ε → k Σ by, for P a polynomial,

Φ(P ) = Φ( u∈Σ * P |u u) = u∈Σ * ( Φ(v)=u P |v )u (9)
as, in this case, the sum

Φ(v)=u P |v (10)
is finite-supported and then well defined. But, we remark that the set of preimages of

u = a 1 a 2 . . . a n by Φ is {v | Φ(v) = u} = ε * a 1 ε * a 2 • • • ε * a n ε * (11)
This shows that, in this case, all preimages are infinite and we will discuss on the convergence of the sum Φ(v)=u P |v . ßIn the sequel, we will extend formula (9) in two ways:

1. To the series for which the sum (10) remains with finite support (this set is larger than the polynomials and includes also the behaviours of ε-automata with an acyclic -transition matrix). We will call them Φ-finite series (FF series).

2. Having supposed the semiring endowed with a topology (or, at least, an "infinite sums" function) we define the set of series for which the sums ( 10) converge (this definition covers the behaviour of classical boolean ε-automata). We will call them Φ-convergent series (FC series).

After these extensions, we will prove that the behaviour of the automaton obtained by algebraic elimination is the image by Φ (the erasure of ε) of the behaviour (in k Σ ε ) of the initial automaton.

5 FF and FC series

FF (Φ-finite) series

Let S ∈ k Σ ε be a formal series, we recall that the support of S is given by: supp(S) = {v ∈ Σ * ε : S, v = 0}. We will call (FF) the following condition:

(FF) For any u ∈ Σ * , the set supp(S) ∩ (Φ -1 (u)) is finite.

If the formal series S satisfies (FF), we say that it is Φ-finite. The set of Φ-finite series in k Σ ε is denoted (k Σ ε ) Φ-finite .

Theorem 4

The set (k Σ ε ) Φ-finite is closed under +, •, α(?) and (?)α.

Proof. As supp(S 1 + S 2 ) ⊆ supp(S 1 ) ∪ supp(S 2 ), supp(αS 1 ) ⊆ supp(S 1 ) and supp(S 1 α) ⊆ supp(S 1 ) for S 1 , S 2 ∈ k Σ ε and α ∈ k, the stability is shown for +, α(?) and (?)α. Now, for the Cauchy product, one can check that :

supp(S 1 S 2 ) ∩ Φ -1 (u) ⊆ u=u1u2 (supp(S 1 ) ∩ Φ -1 (u 1 ))(supp(S 2 ) ∩ Φ -1 (u 2 )) (12) which is a finite set if S 1 , S 2 ∈ (k Σ ε ) Φ-finite .

Remark 4

• Every polynomial is Φ-finite.

• The star S * need not be Φ-finite even if S is Φ-finite. The simplest example is provided by S = ε.

Next, we show that Φ : k Σ ε → k Σ can be extended to k Σ ε Φ-finite as a polymorphism.

Theorem 5 For any S, T ∈ (k Σ ε ) Φ-finite ,

Φ(S + T ) = Φ(S) + Φ(T ) , Φ(ST ) = Φ(S)Φ(T ) Φ(αS) = αΦ(S) , Φ(Sα) = Φ(S)α If S * is Φ-finite, Φ(S *
) is a star of Φ(S). In particular, if Φ(S) has no constant term, one has

Φ(S * ) = (Φ(S)) *
Proof. For sum and Cauchy product, we obtain the result by the following relations:

v∈Φ -1 (u) S + T, v = v∈Φ -1 (u) S, v ⊕ v∈Φ -1 (u) T, v v∈Φ -1 (u) ST, v = u=u1u2 ( v∈Φ -1 (u1) S, v ⊗ v∈Φ -1 (u2) T, v )
Then Φ(S * ) is a solution of the equation Y = ε + Φ(S)Y as S * = ε + SS * , and then Φ(S * ) = Φ(S) * .

A Φ-finite series may be not rational.

Example(s) 4

The series in

N Σ S = |u|a=|u|ε u.
is not rational and however Φ-finite.

We recall that a matrix M ∈ k n×n is nilpotent if there exists a positive integer N such that M N = 0.

Proposition 1 Let S be a rational series in k Σ ε with (λ, µ, γ) a linear representation of S.

i) If µ is nilpotent then S is Φ-finite. ii) Conversely, if S is Φ-finite, k a field and (λ, µ, γ) is of minimal dimension then µ is nilpotent.
Proof. i) With the notations of the theorem, suppose that there is an integer N such that µ(ε

) N = 0 n×n . Then, for u = a 1 a 2 • • • a k one has Φ(v)=u S|v = n0, n1, •••n k ∈N S|ε n0 a 1 εn1 a 2 εn2 • • • a k εn k = n0, n1, •••n k ∈N λµ(ε) n0 µ(a 1 )µ(ε) n1 µ(a 2 )µ(ε) n2 • • • µ(a k )µ(ε) n k γ = n0, n1, •••n k <N λµ(ε) n0 µ(a 1 )µ(ε) n1 µ(a 2 )µ(ε) n2 • • • µ(a k )µ(ε) n k γ
which is obviously finite. ii) If (λ, µ, γ) is of minimal dimension n, then there exists words

(u i ) 1≤i≤n , (v j ) 1≤j≤n in Σ ε such that the n × n matrices L =      λµ(u 1 ) λµ(u 2 ) . . . λµ(u n )      and G = µ(v 1 )γ µ(v 2 )γ • • • µ(v n )γ (13)
are regular (L is a block matrix of n lines of size 1 × n and G is a block matrix of n columns of size n × 1; indeed, L and G are n × n square matrices.) [START_REF] Berstel | Rational Series and Their Languages[END_REF]. Now, for 1 ≤ i, j ≤ n the family

( S|u i εn v j ) n≥0 = (λµ(u i )µ(ε n )µ(v j )γ) n≥0 (14)
as a subfamily of ( S|v ) Φ(v)=Φ(ui vj ) must be with finite support. This implies that (Lµ(ε n )G) n≥0 is with finite support. As L and G are invertible, µ(ε) must be nilpotent.

FC (Φ-convergent) series

If we want to go further in the extension of Φ (and so doing to cover the -boolean -classical case), we must extend the domain of computability of the sums [START_REF] Kuich | Semirings, Automata, Languages[END_REF] to (some) countable families. Many approaches exist in the literature [START_REF] Kuich | Semirings, Automata, Languages[END_REF], mainly by topology, ordered structure or "sum" function.

Here, we adopt the last option with a minimal axiomatization adapted to our goal.

The semiring k will be supposed endowed with a sum function sum taking some (at most) countable families (a i ) i∈I (called summable) and computing an element of k denoted sum i∈I a i . This function is subjected to the following axioms: ßCS1. -If (a i ) i∈I is finite, then it is summable and

sum i∈I a i = i∈I a i (15)
CS2.

-If (a i ) i∈I and (b i ) i∈I are summable, so is (a i + b i ) i∈I and

sum i∈I a i + b i = (sum i∈I a i ) + (sum i∈I b i ) (16)
CS3.

-If (a i ) i∈I and (b j ) j∈J are summable, so is (a i b j ) (i,j)∈I×J and

sum (i,j)∈I×J a i b j = (sum i∈I a i )(sum j∈J b j ) (17)
CS4.

-If (a i ) i∈I is summable and I = λ∈Λ J λ is partitionned in finite subsets. Then ( j∈J λ a j ) λ∈Λ is summable and

sum i∈I a i = sum λ∈Λ ( j∈J λ a j ) (18)
CS5.

-If I = λ∈Λ J λ with Λ finite and each (a j ) j∈J λ is summable. Then so is (a i ) i∈I and

sum i∈I a i = λ∈Λ sum j∈J λ a j (19)
CS6.

-If (a i ) i∈I is summable and φ : J → I is one-to-one then (a φ(j) ) j∈J is summable and

sum i∈I a i = sum j∈J a φ(j) (20)
Definition 2 A semiring with sum function (as above) which fulfills CS1..6 will be called a CS-semiring.

If k is a CS-semiring, the semiring of square matrices k n×n will be equipped with the following sum function: A family (M (i) ) i∈I of square matrices will be said summable iff it is so componentwise i.e. the n 2 families (M

(i)
r,s ) i∈I (for 1 ≤ r, s ≤ n) are summable. In this case, the sum of the family is the matrix L such that, for 1 ≤ r, s ≤ n, L rs = sum i∈I M (i) rs (i.e. the sum is computed componentwise). It can be easily checked that, with this sum function, k n×n is a CS-semiring.

Remark 5 Let k be a topological semiring (i.e. k is endowed with some Hausdorff topology T such that the two binary operations -sum and product -are continuous mappings k × k → k). We recall that a family (a i ) i∈I is said summable with sum s iff it satisfies the following property, where B(s) is a basis of neighbourhoods of s.

∀V ∈ B(s) ∃F ⊂ f inite I ∀F F ⊂ F ⊂ f inite I =⇒ i∈F a i ∈ V . ( 21
)
In this case the axioms CS12456 are automatically satisfied for the preceding (usual) notion of summability.

Example(s) 5

Below some examples of CS-semirings which are metric semirings (i.e. the notion of summability and the sum function are given as in Remark ( 5)).

1. The fields Q, R, C with their usual metric.

2. Any semiring with the discrete topology, given by the metric d(x, y) = 1 if x = y and d(x, x) = 0. (FC) For any u ∈ Σ * , the (countable) family ( S|v ) v∈Φ -1 (u) is summable.

If the formal series S satisfies (FC), we say that it is Φ-convergent. The set of Φ-convergent series in

k Σ ε is denoted k Σ ε Φ-conv .
It is straightforward that a Φ-finite series is Φ-convergent. We have now a theorem similar to Theorem (4) for k Σ ε Φ-conv .

Theorem 6

The set k Σ ε Φ-conv is closed under +, •, α(?) and (?)α.

Proof. Stability by +, α(?) and (?)α is straightforward using the axioms CS123. Let us give the details of the proof for the Cauchy product. We have to prove that, for every S, T ∈ k Σ ε Φ-conv and u ∈ Σ * , the (countable) family

( ST |v ) v∈Φ -1 (u) = ( ST |v ) Φ(v)=u (22)
is summable.

From the definition of the Cauchy product we have the finite sums

ST |v = v1v2=v S|v 1 T |v 2
and, from CS4, the summability would be a consequence of that of the family

( S|v 1 T |v 2 ) Φ(v)=u v=v 1 v 2 = ( S|v 1 T |v 2 ) Φ(v1v2=u)
(with the same sum). This family can be partitionned in a finite sum of families (with the same sum)

u1u2=u ( S|v 1 T |v 2 ) v 1 ∈Φ -1 (u 1 ) v 2 ∈Φ -1 (u 2 ) (23)
each of which, by CS3, is summable. Thus, by CS5, the family ( 23) is summable and hence summability of (22) (with the same sum) follows.

Next, we show that Φ :

(k Σ ε ) Φ-conv → k Σ is a polymorphism. Theorem 7 For any S, T ∈ (k Σ ε ) Φ-conv , Φ(S + T ) = Φ(S) + Φ(T ) , Φ(ST ) = Φ(S)Φ(T ) Φ(αS) = αΦ(S) , Φ(Sα) = Φ(S)α If S * is Φ-conv, Φ(S *
) is a star of Φ(S). In particular, if Φ(S) has no constant term, one has

Φ(S * ) = (Φ(S)) *
Proof. The proof is similar to that of Theorem (5), using the axioms of CS-semirings.

In the sequel, as in the classical case, the summability of (µ(ε) n ) n∈N will play a central rôle. We will then call closable a square matrix M ∈ k n×n such that the family (M n ) n∈N is summable. Note that, in this case, the sum sum n∈N M n is a two-sided (we could say "topological") star of M . For example, with the boolean semiring endowed with the discrete topology, every M ∈ B n×n is closable (i.e. the sequence S N = N k=0 M k is stationnary). We have the following theorem, very similar to (1).

Proposition 2 Let S be a rational series in k Σ ε (k a CS semiring) with (λ, µ, γ) a linear representation of S.

(i) If µ(ε) is closable then S is Φ-convergent. (ii) Conversely, if S is Φ-convergent, k = R, C and (λ, µ, γ) minimal then µ(ε) is closable.
. Proof. The proof (i) is similar to that of Theorem [START_REF] Berstel | Rational Series and Their Languages[END_REF]. The first computation of (ii) is similar, but, to conclude, we use the property (which holds in R and C) that a family is summable iff it is absolutely summable (because of CS6) and then subfamilies of summable families are summable. In the following, we have an example of a boolean automaton with ε-transitions.

Example(s) 6

The linear representation of Figure 3 is:

λ = 1 0 0 0 , µ ε =     0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0     , µ(a) =     1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1     , µ(b) =     0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 1     and γ =     0 0 1 1     .
By computation:

µ * ε =     1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1     , λ = 1 0 0 0 , µ (a) = µ * ε µ(a) =     1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1     , µ (b) = µ * ε µ(b) =     0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1     and γ = µ * ε γ =     1 1 1 1     ,
The resulting boolean automaton is presented in Figure 4 and its linear representation is (λ , µ , γ ). In the next example, our algebraic method is applied on a Q-ε-automaton.

Example(s) 7

The linear representation of Figure 5 is: The resulting automaton is presented in Figure 6 and its linear representation is (λ , µ , γ ).

Conclusion

Algebraic elimination for ε-automata has been presented. The problem of removing the ε-transitions is originated from generic ε-removal algorithm for weighted automata [START_REF] Mohri | Generic ε-Removal Algorithm for Weighted Automata[END_REF] using Floyd-Warshall and generic single-source shortest distance algorithms. Here, we have the same objective but the methods and algorithms are different. In [START_REF] Mohri | Generic ε-Removal Algorithm for Weighted Automata[END_REF], the principal characteristics of semirings used by the algorithm as well as the complexity of different algorithms used for each step of the elimination are detailed. The case of acyclic and non acyclic automata are analysed differently. Our algorithm here works with any semiring (supposing only that µ(ε) is closable and with unique star) and the complexity is unique for the case of acyclic or non acyclic automata. This algorithm is even more efficient when the considered semiring is a ring.

Figure 1 :

 1 Figure 1: A N-automaton k n×n . The behaviour of the weighted automaton A belongs to k Σ . It is defined by: behaviour(A) =

Figure 2 :

 2 Figure 2: A N-ε-automaton

3 .

 3 The extended integers (N ∪ {+∞}, +, ×) with the Frechet topology given by the metric d(n, m) = | 1 n -1 m | and d(+∞, n) = 1 n . 4. The (min, plus) closed half-ray ([0, +∞]R, min, +) with the metric transported by the rational homomorphism x → x x+1 from [0, +∞]R to [0, 1] R i.e. with d(x, y) = | x x+1 -y y+1 | and with x x+1 | x=+∞ = 1. Let S ∈ k Σ ε be a formal series, we will call (FC) the following condition:

Figure 3 :Remark 6

 36 Figure 3: A B-ε-automaton Remark 6 One could also with the same result set λ = λµ * ε , µ (a) = µ(a)µ * ε for each letter a ∈ Σ and γ = γ.

Figure 4 :Figure 6 :

 46 Figure 4: A B-automaton

  We have to show that N is a solution of the equation M y + 1 n×n = y. 11 + a 12 A 21 + 1 p×p a 11 A 12 + a 12 A 22 a 21 A 11 + a 22 A 21 a 21 A 12 + a 22 A 22 + 1 q×qwhere 0 p×q is the zero matrix in k p×q . We verify the relations (1), (2), (3) and (4) by:a 11 A11 + a 12 A 21 + 1 p×p = a 11 A 11 + a 12 a * 22 a 21 A 11 + 1 p×p = A 11 (a 11 + a 12 a 22 * a 21 ) + 1 p×p = A 11 a 11 A 12 + a 12 A 22 = a 11 a 11 * a 12 A 22 + a 12 A 22 = (a 11 a 11 * + 1)a 12 A 22 = a 11 * a 12 A 22 = A 12 a 21 A 11 + a 22 A 21 = a 21 A 11 + a 22 a 22 * a 21 A 11 = (1 + a 22 a 22 * )a 21 A 11 = a 22 * a 21 A 11 = A 21 a 21 A 12 + a 22 A 22 + 1 q×q = a 21 a 11 * a 12 A 22 + a 22 A 22 + 1 q×q = (a 22 a 21 a 11 * a12)A 22 + 1 q×q = A 22

	one has a 11 A Remark 2 M N + 1 = a 11 a 12 a 21 a 22 =	A 11 A 12 A 21 A 22	+	1 p×p 0 p×q 0 q×p 1 q×q	By computation,

  )

	However, if the formulas are defined at each step of the computation (see below for a formalization of this), it provides a recursive way to compute a star of a matrix.
	(ii) Similar formulas can be stated in the case of a left star. The matrix N is the left star of M with
	A 11 = (a 11 + a 12 a 22	* a 21 ) *
	A 12 = A 11 a 12 a 22	*
	A 21 = A 22 a 21 a 11	*
	A 22 = (a 22 + a 21 a 11	* a 12 ) *

Acknowledgements

We thank the anonymous referees for careful reading and fruitful remarks.

Semirings

Equivalence

We now deal with an algebraic method to eliminate the ε-transitions from a weighted ε-automaton A ε . The result is a weighted automaton with behaviour Φ(behaviour(A ε )).

Theorem 8 Let k be a CS semiring and A ε = (λ, µ, γ) be a weighted ε-automaton with weights in k. We suppose that µ(ε) is closable. Then i) the series behaviour(A ε ) is Φ-convergent.

ii) there exists a (algorithmically constructible) weighted automaton A = (λ , µ , γ ) such that behaviour(A) = Φ(behaviour(A ε )).

Proof. The point i) is a reformulation of Proposition [START_REF] Champarnaud | Brzozowski's derivatives extended to multiplicities[END_REF]. Remark that, if (µ(ε) n ) n∈N is summable its sum is a (two sided) star of µ(ε) that, for convenience, we will denote µ(ε) * . Let B be the behaviour of A ε one has

Let k be a semiring and A ε = (λ, µ, γ) a k-ε-automaton with S ∈ k Σ ε ) Φ -conv as behaviour. Theorem [START_REF] Champarnaud | Brzozowski's derivatives extended to multiplicities[END_REF] gives the lower bounds if the set of coefficients is the semiring k (resp. ring, field).

Proposition 3

We suppose that, in k n×n , stars are unique. Let (λ, µ, γ) a k-ε-automaton such that µ(ε) admits a tree of computation and is closable, then the complexity of the elimination of ε-transitions which produces the weighted automaton A = (λ , µ , γ ), is O(n ω ).

Proof. The unique matrix µ * ε given by the algorithm of Theorem (1) satisfies the relation:

As (µ m ) m∈N is summable, one has µ * = µ m . Next set λ = λ, γ = µ * ε γ and µ (a) = µ * ε µ(a) for each letter a ∈ Σ.


Abdullah Haskou
email: abdullah.haskou@univ-rennes1.fr

Ala Sharaiha
email: ala.sharaiha@univ-rennes1.fr

Sylvain Collardey
email: sylvain.collardey@univ-rennes1.fr

Mélusine Pigeon

Kouroch Mahdjoubi

A Design Methodology for Electrically Small Superdirective Antenna Arrays

Keywords: Superdirectivity, end-fire, excitation coefficients

This paper presents a design methodology for electrically small superdirective antenna arrays. To calculate the required current excitation coefficients the radiated electrical fields obtained from an electromagnetic simulator are integrated in Uzkov equations. The obtained parameters are, then, optimized and used for calculating the power excitation coefficients. The proposed method is deployed for designing a two-element array for an inter-element separating distance varying from 0.05λ to 0.5λ. Simulation results show that the proposed method accurately estimates the required excitation coefficients and the method is validated.

I. INTRODUCTION

The limits on a single antenna-and an antenna array-directivity has undergone a lot of research. R.F. Harrington showed that the directivity of a single antenna can attain N 2 + 2N , N being the highest mode order permitted by this antenna [START_REF] Harrington | On the Gain and Beamwidth of Directional Antennas[END_REF]. I. Uzkov demonstrated that the end-fire directivity of N closely placed isotropic radiators can attain N 2 [START_REF] Uzkov | An Approach to the Problem of Optimum Directive Antennae Design[END_REF]. Ever since, a lot of study has been done on the design of superdirective antenna arrays [START_REF] Altshuler | A Monopole Superdirective Array[END_REF][START_REF] O'donnell | Electrically Small Superdirective Arrays Using Parasitic Elements[END_REF][START_REF] O'donnell | Frequency Optimization of Parasitic Superdirective Two Element Arrays[END_REF][START_REF] Sentucq | Superdirective Compact Parasitic Array of Metamaterial-Inspired Electrically Small Antenna[END_REF]. E.E. Altshuler et al. studied a threeelement monopole-based superdirective array [START_REF] Altshuler | A Monopole Superdirective Array[END_REF]. O'Donnell and Yaghjian showed that approximately the same directivity obtained with two driven elements can be achieved with exciting one element and shorting the other one [START_REF] O'donnell | Electrically Small Superdirective Arrays Using Parasitic Elements[END_REF]. O'Donnell et al. also studied the effect of the frequency optimization on a parasitic two elements array [START_REF] O'donnell | Frequency Optimization of Parasitic Superdirective Two Element Arrays[END_REF]. The authors showed that using the parasitic element as a director can approximately achieve the same results as driving both elements. Sentucq et al. presented a two-element parasitic array [START_REF] Sentucq | Superdirective Compact Parasitic Array of Metamaterial-Inspired Electrically Small Antenna[END_REF]. The array is mounted on relatively big ground plane and achieves a maximum directivity of 7.76dBi. This paper presents a method for designing electrically small superdirective antenna arrays. The proposed method is validated via the design of a miniaturized two-element superdirective antenna array with a separating distance changing form 0.05λ to 0.5λ. 1

II. THE PROPOSED DESIGN METHODOLOGY

The proposed design methodology is as follows:

• First, the antenna array is simulated via an electromagnetic simulator, ANSYS HFSS in our case [7], to obtain the radiated electrical field for each element and the array impedance matrix.

• In order to calculate the required current excitation coefficients, the radiated electrical fields are integrated in Uzkov equations that were later re-presented by Altshuler et al in [START_REF] Altshuler | A Monopole Superdirective Array[END_REF]. The current excitation coefficients that maximizes the directivity in the direction (θ 0 , ϕ 0 ) are given by:

a 0n = [H * mn ] -1 e -jk r0rm f * m (θ 0 , ϕ 0 )f n (θ 0 , ϕ 0 ) (1)
where r0 is the unit vector in the far field direction (θ 0 , ϕ 0 ), k = w c is the wave number, and H mn is given by:

H mn = 1 4π ∫ 2π 0 ∫ π 0 f m (θ, ϕ)f * n (θ, ϕ)
e jkr(rm-rn) sin(θ) dθ dϕ [START_REF] Uzkov | An Approach to the Problem of Optimum Directive Antennae Design[END_REF] where r is the unit vector in the far field direction (θ, ϕ).

• However, in our case, and since the far field patterns' equations are not known, HFSS results are used instead and the following approximation for H mn is used:

H mn = 1 4π 2π ∑ θ=0 π ∑ ϕ=0 f m (θ, ϕ)f * n (θ, ϕ)
e jkr(rm-rn) sin(θ)∆(θ)∆(ϕ) [START_REF] Altshuler | A Monopole Superdirective Array[END_REF] where ∆(θ) = 2π N θ and ∆(ϕ) = π N ϕ are the far field sampling step in spherical angles (θ, ϕ), N θ and N ϕ being the number of samples.

• It is well known that Equation 2 is the limit of Equation 3 when ∆(θ) and ∆(ϕ) tend to zero (N θ and N ϕ tend to infinity) [START_REF] Riemann | Ueber die Darstellbarkeit einer Function durch eine trigonometrische Reihe[END_REF]. Hence, the obtained parameters need to be slightly modified to maximize the directivity of the array.

• Finally, the current excitation coefficients and the array impedance matrix can be used to calculate the required power excitation coefficients.

III. SIMULATION AND RESULTS

A. Single Element Description

The single element used in this study is a miniaturized spiral antenna. This antenna is printed on a 0.835mm-thick FR4 substrate. The antenna total dimensions are approximately

B. Two-Element Array Design

The proposed method was used to design a two-element spiral antenna array. The separating distance is varied between 0.05λ and 0.5λ. 2 distance increases, the obtained directivity approaches the optimal one. The explanation of all the results can be as follows: since the coupling between the two elements increases as the distance decreases, the number of samples for accurately describing the radiated fields increases. Hence, for obtaining the same estimation accuracy, the number of the samples should increase as the separating distance decreases. Figure 3(a), shows the radiation pattern in the horizontal plane for all the cases. The figure shows that for very small distances, the mutual coupling highly affects the radiation patterns and hence a high directivity cannot be obtained. However, starting from 0.1λ a good directivity and Front to Back Ratio (FBR) can be attained, where for 0.1λ we have a maximum directivity of 6.89dBi and a FBR of 8.4dB. As the distance increases, the backward radiation also increases and for 0.5λ the directivity for both end-fire directions is approximately the same. Furthermore, a Maximum to Minimum Ratio (MMR) of about 30dB can be noticed for all distances starting from 0.1λ. Where for 0.1λ, for example, the side lobe level is -20.3dBi which means an MMR of 27.2dB (referenced to the maximum of 6.89dBi). Figure 3(b) shows the results obtained by applying the calculated power excitation coefficients. The figure shows a very good accordance with the results obtained in the case of exciting the antennas with current signals.

The applied power excitations and the maximum achieved directivities are given in Table I. Figure 4 shows the simulated 3D radiation patterns for a separating distance of d = 0.1λ when exciting the array with current and power signals. Finally, for a distance of d = 0.05λ, exciting the first antenna and loading the second one with a capacitor C = 7.19pF , a maximum directivity of 5.67dBi can be achieved. Figure 5 shows the simulated 3D radiation patterns for 918.75M Hz and the directivity in the direction (θ = 90, ϕ = 180) as a function of the frequency. The 3D radiation pattern shows a very good accordance with the results obtained when exciting the two antennas with current or power signals. As expected, Figure 5(b) shows that the directivity is maximal at the design frequency and rapidly decreases as we deviate from this frequency.

d[λ] P1[W ] ϕ1[ • ] P2[W ] ϕ2[ • ] Dmax[dBi] 0.

IV. MEASUREMENTS AND RESULTS VALIDATION

A prototype of the parasitic array was fabricated and measured for the input reflection coefficient and the radiation pattern. Figure 6, shows a photograph of the fabricated prototype. Figure 7, shows the simulated and measured insertion loss and input impedance when taking into account the cable and SMA connector effect. The figure shows a good match between the simulated and measured results. Figure 8, shows the simulated and measured radiation patterns. The figure shows that the superdirectivity effect cannot be monitored because of the cable radiation effect. The figure also shows a considerable difference between the simulated and measured results. This difference can be attributed to the limited length of the cable considered in simulation (5cm), while in the measurement set up the cable length which is out of the Teflon is considerably bigger.

V. CONCLUSION

In this paper, a method for designing electrically small superdirective antenna arrays is presented. The proposed method is used for designing a two-element array for different separating distances. Simulation results show that the proposed method accurately estimates the required excitation coefficients, and hence, the method is validated. Measurement results for the array input parameters are in a good match with simulated ones.

λ

  13 * λ 23 . The antenna has a -10dB bandwidth of approximately 7.3M Hz at a central frequency of 927M Hz, and a directivity of 2.67dBi. Figure1(a), shows the antenna geometry and corresponding dimensions.

Figure 1 (

 1 b), shows the antenna simulated input reflection coefficient and Figure1(c), shows the antenna simulated radiation pattern.

Fig. 1 .

 1 Fig. 1. Miniaturized spiral antenna. (a) Antenna geometry and dimensions, (b) simulated input reflection coefficient and (c) simulated 3D radiation pattern.

  Figure 2(a), shows the input reflection coefficient of the two basic elements as a function of the separating distance. Based on this results, the array is designed for a frequency of of 918.75M Hz for all the distances. Figure 2(b), shows the initial-and optimized-current magnitudes. The figure shows a significantly good accordance between the initial and optimized magnitudes starting from 0.1λ.

Figure 2 (

 2 c) shows the initial-and optimized-current phases. The figure shows that as the separating distance increases the estimated phases get closer to the optimal ones. Finally, Figure2(d)shows the initial-and optimized-end-fire directivity of the antenna array. The figure also shows that as the separating2 The distance is calculated based on a frequency of 900MHz.

Fig. 2 .

 2 Fig. 2. Two spirals-based array. (a) The input reflection coefficient of the two elements as a function of the separating distance, (b) current excitation magnitudes, (c) current excitation phases and (d) simulated end-fire directivity.

Fig. 3 .

 3 Fig. 3. Simulated horizontal radiation patterns of a two spirals-based array. (a) With current excitations and (b) with power excitation.

Fig. 4 .

 4 Fig. 4. Two spirals-based array simulated 3D radiation pattern. (a) With current excitation and (b) with power excitation.

Fig. 5 .

 5 Fig. 5. Parasitic two spirals-based array. (a) 3D radiation pattern and (b) maximum directivity vs. frequency.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Two spiral-based array, a photo of the fabricated prototype.

Fig. 8 .

 8 Fig. 8. Two spiral-based array radiation pattern measurement results. (a) Vertical-plane and (b) horizontal-plane.

TABLE I .

 I TWO SPIRALS-BASED ARRAY: THE APPLIED POWER EXCITATIONS AND THE ACHIEVED DIRECTIVITY.

 [START_REF] Harrington | On the Gain and Beamwidth of Directional Antennas[END_REF]This work was supported and funded by the French National Research Agency as part of the project "SOCRATE".


Mathieu Vallérian

Florin Hutu

Guillaume Villemaud

Benoît Miscopein

Tanguy Risset

A study of companding approaches to alleviate the ADC constraints when demodulating multiple signals

Keywords: RF front end, analog processing, multiplicative companding, additive companding, multiple signals digitization, dynamic range reduction

In urban sensor networks, the diversity of propagation conditions can lead to the simultaneous reception of signals having very different power levels. Given the diversity of wireless technologies used in this area, implementing gateways using a Software-Defined Radio (SDR) approach seems to be a very practical solution. Overcoming the high dynamic range may however require an Analog-to-Digital Converter (ADC) with a resolution fine enough to digitize the weakest signal with a satisfying precision. In order to relax these specifications, an analog processing, such as companding, should be performed before digitization. The companding technique is usually employed on one signal (and not on multiple signals that are only separated on the frequency domain). This report studies three companding laws to test their efficiency in relaxing the digitization constraints with multiple signals. A µ-law, a Piecewise-Linear (PL) law and a Piecewise-Linear, Constant Gain with Offsets (PLCGO) law are tested. It is described how to use a PLCGO approach to reduce ADC's complexity, and two implementations of the compressing law are proposed.

Une étude de lois de compression-extension pour relâcher les contraintes sur le CAN dans le cas d'une démodulation de signaux multiples Résumé : Dans les réseaux de capteurs urbains, la diversité des conditions de propagation des signaux peut mener à une réception de signaux multiples, avec des niveaux de puissance très différents. De nombreuses technologies de communication sont utilisées dans ce domaine. Sachant cela, la solution la plus adaptée pour implémenter la passerelle collectant les données des noeuds semble être d'utiliser une radio logicielle. Pour pouvoir absorber la grande plage dynamique des signaux, le Convertisseur Analogique-Numérique (CAN) requiert une résolution suffisamment fine pour numériser le signal le plus faible avec une précision satisfaisante. Afin de relâcher cette contrainte, un traitement analogique, comme la compression-extension, doit être appliqué sur les signaux avant numérisation. Habituellement la technique de compression-extension est utilisée sur un seul signal, et pas sur des signaux multiples (qui ne sont séparés que dans le domaine fréquentiel). Ce rapport étudie donc trois lois de compression-extension afin de tester leur capacité à abaisser les contraintes de numérisation de signaux multiples. Une loi en µ, une loi linéaire par morceaux, et une loi linéaire par morceaux, avec gain constant et niveaux de tension continue sont testées. Il est décrit dans ce rapport comment une approche avec cette dernière loi permet de réduire la complexité du CAN. Deux implémentations de la loi de compression sont proposées.

Mots-clés : systèmes RF, traitement analogique, compression-extension multiplicative, compressionextension additive, numérisation de signaux multiples, réduction de plage dynamique

Introduction

A urban sensor networks is generally built on sensor nodes that collect data from various applications, such as parking management, water and gas metering, pollution monitoring, public lighting, etc. A sink node (also called gateway) collects the data received from the sensors. The sensors are Short Range Devices (SRD) in many actual deployments. Such devices generally emit in the 868 MHz band with a 8 MHz frequency band [START_REF] Etsi | Electromagnetic compatibility and Radio spectrum Matters (ERM); System Reference document (SRdoc): Spectrum Requirements for Short Range Device, Metropolitan Mesh Machine Networks (M3N) and Smart Metering (SM) applications[END_REF]. Each application having its own constraints, several communication protocols are used to handle them. These communication protocols are still evolving today, and new ones are susceptible to emerge in a near future. To embed these protocols in the gateway, the existing solution consists in a stack-up of radio receivers, each one dedicated to one communication protocol. This method has a major drawback: if a new technology has to be added to the network, the gateway must be replaced. This problem can be avoided by using a reconfigurable gateway: then the gateway could be able to embed a new technology with a simple software update. As done in Software-Defined Radio (SDR), the transmission frequency band should be digitized at once [START_REF] Dardaillon | Cognitive radio programming: Existing solutions and open issues[END_REF].

Nevertheless another problem appears from this choice. From the diversity of constraints, propagation conditions and signals' features that originate from the diversity of applications, received signals with high dynamic ranges can be encountered. It has been shown in [START_REF] Vallerian | SDR for SRD: ADC specifications for reconfigurable gateways in urban sensor networks[END_REF] that the dynamic range between two received signals can be up to 100 dB. This high dynamic range is an important constraint from the Analogto-Digital Converter (ADC) perspective. Indeed the greater the dynamic range is, the higher should be the ADC resolution to properly digitize every signals. The expression of the required ADC resolution to demodulate all the signals in the band with such a dynamic range has been expressed [START_REF] Vallerian | SDR for SRD: ADC specifications for reconfigurable gateways in urban sensor networks[END_REF], and is plotted in Figure 1. With a 100 dB dynamic range, the required resolution (highlighted with dashed lines on Figure 1) is 21 bits. Reminding that a band of 8 MHz must be digitized, a 21 bits resolution appears to be unfeasible with today's ADCs [START_REF] Jonsson | A survey of A/D-Converter performance evolution[END_REF]. This presents the ADCs performance evolution to 2010. On figure 2, the evolution of ENOB is given. The ADCs with a sampling frequency of the order of 10 MS/s (grey line) had an ENOB of about 14 bits in 2010. Extrapolating the grey line, an ADC with an ENOB of 16 bits can't be expected in a near future. Then another solution has to be found to digitize the signals. Digitizing subbands in parallel would be problematic if signals straddle two sub-bands. Moreover, some communication Figure 2: ADC performance evolution, from [START_REF] Jonsson | A survey of A/D-Converter performance evolution[END_REF]. The sampling rates are 10 kS/s, 100kS/s, 1MS/s, 10MS/s, 100MS/s, and 1 GS/s. The grey line represents the 10 MS/s ADCs. By extrapolation, no ENOB higher than 16 bits can be expected in a near future. protocols use spread spectrum techniques, so the signal could be digitized in several sub-bands: then it would be disrupted after reconstitution. Another way to reduce the required resolution is to apply on the signals an analog processing, such as companding, in order to reduce their dynamic range.

The goal of this work is to explore how companding laws are able to improve or not the required resolution to properly digitize the multiple signals present on the band. Three companding laws are studied: the µ-law [START_REF] Van Ess | Algorithm -Logarithmic Signal Companding -Not just a good idea -it is µ-Law[END_REF], a Piecewise-Linear (PL) law [START_REF] Maheshwari | Companding Baseband Switched Capacitor Filters and ADCs for WLAN Applications[END_REF] and a Piecewise-Linear, Constant Gain law with Offsets (PLCGO) [START_REF] Bes | An additive instantaneously companding readout system for cochlear implants[END_REF]. It is shown that whereas the µ-law brings no improvement with multiple signals with a high dynamic range, the PL law shows promising results. The PLCGO law is similar to the PL law although offsets are added to the signal to reduce its dynamic range instead of changing the compressing gain. This feature allows to reach a far better digitization performance than the PL law.

The section 2 introduces the companding technique and gives common examples of companding laws. Three companding laws are also introduced, and are studied latter in the report. The µ-law is described and studied in section 3. The Bit Error Rate (BER) of a weak signal in presence of a stronger signal and the quantization noise are used to quantify the digitization quality, which is compared with and without companding. The section 4 is dedicated to the study of PL law, which is described there. The digitization performance is still quantified by the BER of a weak signal and by the quantization noise. The section 5 introduces the PLCGO law. Its efficiency to reduce the required resolution with multiple signals is studied, and its performance in terms of BER and of quantization noise is compared with the PL law and µ-law. The relevance of the PLCGO law in our case being proved, the section 6 proposes two implementations for this law, and discusses their performance. The section 7 gives the conclusions of this work and gives some directions for future work.

The companding technique

Companding is a signal processing technique aiming at reducing the dynamic range of the input signal [START_REF] Van Ess | Algorithm -Logarithmic Signal Companding -Not just a good idea -it is µ-Law[END_REF]. It has been patented in 1928 for the transmission of analog pictures [START_REF] Clark | Electrical Picture-Transmitting System[END_REF] and the technique had been Inria widely used in analog telephony. Another application is the transmission of speech messages in digital wireless systems like cellular telephony. The technique is widely described in [START_REF] Tsividis | Externally linear, time-invariant systems and their application to companding signal processors[END_REF], where Tsividis studies externally-linear, time-invariant systems and demonstrates their interest in companding implementation by improving the dynamic range and power dissipation. In the case of digitization, the signal is first compressed to reduce its dynamic range, the compressed signal is then digitized and eventually expanded to recover the original signal. The expansion is performed by means of the expanding function, which is the compression reciprocal function.

Companding can be instantaneous or syllabic. With instantaneous companding, the compressing gain varies with the instantaneous amplitude value of the input signal [START_REF] Mallinckrodt | Instantaneous Compandors[END_REF]. With syllabic companding, the input signal is divided in small time segments called syllables [START_REF] Tsividis | Externally linear, time-invariant systems and their application to companding signal processors[END_REF]. The measurement of a mean (e.g. Root Mean Square: RMS) amplitude value on the syllable is used to set up the compressing gain. In both cases the compressing gain depends on the input signal amplitude, so the compressing and expanding functions are always non-linear.

The companding law can follow various functions. Some commonly used functions are the logarithmic function (log), the hyperbolic tangent (tanh) function, the hyperbolic sinus function (sinh) or the square root function ( √ ). They are usually implemented through log, tanh, sinh or √ -domain filters. Examples of implementations of these laws through this way can be found in [START_REF] Katsiamis | A Practical CMOS Companding Sinh Lossy Integrator[END_REF] (proposing a new implementation of the sinh law and making simpler to analyze the circuit imperfections), in [START_REF] Chatchawaree | A 3rd-order elliptic syllabic-companding tanh filter[END_REF] (proposing a tanh implementation for syllabic companding in order to reduce power dissipation) or in [START_REF] De | Limit cycle behavior in a class-AB second-order square root domain filter[END_REF] (whose primary goal is to demonstrate that an external non-linear behaviour of logarthmic laws can be extended to √ laws). These implementations are usually dedicated to syllabic companding, but [START_REF] Mulder | An instantaneous and syllabic companding translinear filter[END_REF] showed that instantaneous companding can be implemented through a translinear filter, using the analog floating point technique. The logarithmic function is the most commonly used, and is for example used in the well-known µ-law [START_REF] Van Ess | Algorithm -Logarithmic Signal Companding -Not just a good idea -it is µ-Law[END_REF]. The compression functions of these laws are similarly shaped, and have the same behavior when compressing a signal. Thus, in this report, only the logarithmic law is considered and results are extrapolated to other similarly shaped laws. Another class of companding laws exists. The described above laws are all bijective functions. But the compressing law can be only surjective (not injective), i.e. the original signal can't be directly recovered from the compressed signal. Then one compressed signal level corresponds to several input signal levels. This input signal level is eventually recovered thanks to the state variable. An example of a surjective law where a state variable is used can be found in [START_REF] Maheshwari | Companding Baseband Switched Capacitor Filters and ADCs for WLAN Applications[END_REF].

In this report, only instantaneous companding is considered and three compression laws are described, one being bijective and the other two being only surjective. The first one relies on a logarithmic function whereas the second one is built on a PL function. The third one is defined by a PLCGO function. It is important to note that companding is usually used to compress signals that are separated in the time domain. Given this report explores how to digitize two signals which occur simultaneously but separated in the frequency domain, the following sections show how these three techniques can meet this requirement or not.

Logarithmic compressing function 3.1 Introduction to the logarithmic compressing law

Applying a logarithmic gain on the received signal is a common means to get a logarithmic compression. This can be implemented with a logarithmic amplifier for example [START_REF] Van Ess | Algorithm -Logarithmic Signal Companding -Not just a good idea -it is µ-Law[END_REF]. This kind of function was widely used in analog telephony, when the audio signal dynamic range is bigger than the one supported by the transmission protocol [START_REF] Van Ess | Algorithm -Logarithmic Signal Companding -Not just a good idea -it is µ-Law[END_REF]. Another application is the transmission of speech messages in digital wireless systems like cellular telephony. In practice, the most widely used functions were the µ-law in North Input signal amplitude (V) Output signal amplitude (V)

µ-law (compression) µ-law (expansion) A-law (compression) A-law (expansion)
Figure 4: Gains of the µ-law and of the A-law with a compression factor of 100 America and the A-law in Europe. The Figure 3 presents the block diagram of companding using a logarithmic law.

Denoting the input signal, the compressed signal and the expanded signal by respectively x(t), w(t) and y(t), and µ and A being the respective compression factors of the µ and A-laws, their compressing and expanding laws are defined respectively in (1) for the µ-law and in (2) for the A-law.

w(t) = sgn(x(t)) • ln(1 + µ|x(t)|) ln(1 + µ) (Compression) y(t) = sgn(w(t)) ((1 + µ) |w(t)| -1) µ (Expansion) (1)
w(t) =        sgn(x(t)) • A|x(t)| 1 + ln(A) if |x(t)| < 1 A sgn(x(t)) • 1 + ln(A|x(t)|) 1 + ln(A) if 1 A ≤ |x(t)| ≤ 1 (Compression) y(t) =          sgn(w(t)) • |w(t)|(1 + ln(A)) A if |w(t)| < 1 1 + ln(A) sgn(w(t)) • exp(|w(t)|(1 + ln(A)) -1) A if 1 1 + ln(A) ≤ |w(t)| ≤ 1 (Expansion) (2)
Both laws have the same behavior, as one can see on Figure 4. There the µ-law and the A-law have been plotted with the same compression factor of 100. As the compressing and expanding functions are similarly shaped, only the µ-law has been studied.

Inria

In [START_REF] Vallerian | SDR for SRD: ADC specifications for reconfigurable gateways in urban sensor networks[END_REF], the required resolution to demodulate two simultaneous signals has been found with respect to their power ratio. This required resolution is shown on Figure 1. One can see that the required resolution to demodulate the signals with a 100 dB dynamic range is 21 bits. The goal of this section is to assess how this ADC requirement is impacted when a logarithmic compression law is used.

Simulation of the µ-law's performance

Using the Agilent ADS software, a strong and a weak Binary Phase Shift Keying (BPSK)-modulated signals (whose amplitudes are respectively denoted S s and S w ) are generated together with an Additive White Gaussian Noise (AWGN), both with a bitrate of 200 kbps. The resulting signal is compressed, digitized and then expanded using the µ-law with a compression factor of 100. The digitization is performed with a sampling frequency of 16 MHz. After demodulation, a BER test is performed through the Monte-Carlo method (the simulation ends when the desired relative variance is met) to evaluate the companding impact and the digitization quality . Simulations are done by varying the ADC resolution and the power ratio between the strong and weak signals (S s /S w ), respectively from 1 to 25 bits and from 0 to 100 dB. The noise level is defined by the energy per bit to noise power spectral density ratio (E b /N 0 ) of the weakest signal. The lowest required resolution to demodulate the weakest signal only depends on S s /S w [START_REF] Vallerian | SDR for SRD: ADC specifications for reconfigurable gateways in urban sensor networks[END_REF]. Since it does not depend on the weakest signal's E b /N 0 , this latter value has been arbitrarily set to 7 dB in all the simulations. As the S s /S w ratio can be up to 100 dB the BER test is performed only on the weak signal since it would take too much simulation time if done on the strongest one. Moreover, the Signal-to-Noise Ratio (SNR) of the strong signal (which is basically the sum of the weakest signal's SNR and S s /S w ) is high enough too guarantee a demodulation with a significantly low BER.

The Figure 5 shows the results of these simulations with a relative variance of 0.01. For a given value of S s /S w , the minimum required resolution is determined when the BER comes close to the 10 -3 floor, corresponding to the expected BER for a BPSK modulation when using an AWGN channel with E b /N 0 = 7 dB. The variation range of S s /S w has been chosen to be similar to the case of [START_REF] Vallerian | SDR for SRD: ADC specifications for reconfigurable gateways in urban sensor networks[END_REF] (i.e. up to 100 dB).

When S s /S w is 0 dB, a positive effect on the BER is observed since it is lightly lessened. If S s /S w is a little higher, but remains low (here 20 dB) the BER is the same with and without companding. When the S s /S w ratio is getting higher, companding with a µ-law leads to a BER degradation. The simulation results on Figure 5 are presented with a compressing factor µ = 100, but other values have been tested, giving similar results.

The effect of the logarithmic companding on BER can be explained by considering the time-based representation of quantization noise. The quantization noise can be measured by performing the compression, digitization and expansion steps on a sine input signal. If the compression and expansion functions' implementations are the exact mathematical functions, the difference between the expanded and original signals is the quantization noise. This representation is given in Figure 6 and has been obtained through Matlab simulations. It shows the quantization noise of a 20-bit ADC obtained on a sinusoidal input signal (Figure 6a), using a µ-law compression (Figure 6b) and a Direct Digitization (DD) (Figure 6c). When using a µ-law compression, the quantization noise level depends on the input signal level: the higher the input signal, the higher the quantization noise. This effect is not observed with a DD.

When two signals are combined in time, the quantization noise with the µ-law is driven by the strongest signal's amplitude. This issue is shown on Figure 7, where the equivalent quantization step is highlighted when using a DD and a µ-law on two signals represented by sinusoids with different amplitudes and frequencies. The quantization step is higher when the input signal level is high, leading to a higher quantization noise. It means that when the input signal level is high the weakest signal's SNR may be severely affected, leading to a BER degradation. This effect is amplified as S s /S w is getting higher. When S s /S w = 0 dB, the signals' amplitudes are equal: then the total signal amplitude is driven by both signals. The SNR then depends on the amplitude of both signals, leading to a BER improvement. All this The simulation results reported on Figure 6b show that companding using a logarithmic (or similarly shaped) law is not appropriate to reduce the dynamic range between two simultaneous signals, due to the aforementioned impact of the quantization noise. In the next section the PL compressing law is studied, as it may provide a different behavior depending on the compressing function shape.

PL compressing function 4.1 Introduction to the PL compressing function

With a PL compressing function, the gain is still dependent on the input signal amplitude; nevertheless it remains constant in predefined amplitude ranges. These amplitude ranges, or functioning states, are delimited by voltage thresholds. Thus within one state the compression law is linear irrespective to the input signal level, but overall the law is still non-linear (i.e. the compressing gain varies with time). The block diagram is given in Figure 8. With x(t), w(t), g(t) and y(t) the input signal, the compressed signal, the compressing gain and the expanded signal, the compressing law can be expressed as:

w(t) = g(t) • x(t) (Compressing) y(t) = w(t) g(t) (Expanding) (3)
To expand the signal the inverse gains are applied to the compressed signal. For that, the state must be transmitted from compression to expansion through a dedicated state variable. An example of such a law can be seen on Figure 9, where three states (0, 1 and 2) are defined with the related thresholds V th1 9a and the compression step is represented on Figure 9b with a sinusoidal input for illustration. The law example comes from [START_REF] Maheshwari | Companding Baseband Switched Capacitor Filters and ADCs for WLAN Applications[END_REF], where an implementation using switched capacitor filters is presented. The aim of this work is to propose an implementation that can coexist with digital blocks on die, allowing to reduce the ADC power consumption. One can note that the dynamic range is effectively compressed; however the compressed signal amplitude range is not uniform from one state to another, due to the different gains applied on the input signal. The goal of the following is to demonstrate how the ADC resolution requirements are affected when a PL compressing law is used.

Simulations of the law's performance

As in section 3, the BER of a weak signal is simulated in presence of a stronger signal using the Agilent ADS software. The only differences with the simulation schematic described at the beginning of the subsection 3.2 are the compressing and the expanding laws, which are cosimulated using the MatLab software. The laws were simulated using three states and as previously, the BER of the weak signal is simulated regarding the ADC resolution and S s /S w . E b /N 0 is still 7 dB, leading to the same BER floor of 10 -3 .

The simulation results are shown on Figure 10, still with a relative variance of 0.01. Contrary to the µ-law, the PL law has always a positive effect on the BER by lessening it regardless of the S s /S w value. The benefit in terms of quantization bits is still dependent on S s /S w for the same reason as previously: the total signal amplitude being driven by the strong signal amplitude, the quantization noise do likewise.

This effect can be seen on Figure 11 where the quantization noise is given assuming a sinusoidal signal as an input signal (Figure 11a) for a µ-law compression (Figure 11b), a PL law compression (Figure 11c) and a DD (Figure 11d). The same ADC features as in section 3 were used. The PL law's performance The analysis of Figure 11 indicates that PL compression seems a better way to reduce the required ADC resolution to digitize both low and strong levels signals than logarithmic compression. Indeed it can be easily shown that the quantization noise with a PL law is at worst equivalent to the one obtained with DD: when the signal is in the higher state (in the state 2 in our example) the compressing gain is 1 and then the compressed signal is equal to the input signal. In the other states the gain is higher and the input signal is amplified. The quantization noise is then drastically reduced in comparison with the µ-law case: it is at its maximum close to the one obtained with a DD, whereas with the µ-law it was higher at its maximum than the one with a DD.

The Figure 12 shows the equivalent quantization step when using a PL compressing law. More quantization states are used with the PL law than with DD, thanks to the use of a state variable. When the input signal is low, more quantization states are used, leading to a lower quantization noise. When the input signal is high, the same number of quantization states as with DD are used. When comparing with the µ-law's performance, less quantization states are used when the signal is low, but more quantization states are used when the signal is high. As the quantization noise was mainly present when the signal was high with the µ-law, the quantization noise is globally reduced.

The fact that the quantization noise with the PL law is globally lower than the one with a DD proves that the PL law improves the digitization quality with regard to the DD. However, it can be seen on Figure 9b that most of time only a part of the ADC's dynamic range is occupied by the compressed signal. Especially in the states 1 and 2 the signal occupies a small part of the total ADC's dynamic range. The next section presents the PLCGO law, that maximizes the signal's dynamic range occupancy.

Compression law using offsets 5.1 Motivation

The general idea of the additive companding law is to maximize the dynamic range occupied by the signal after compression (i.e. before digitization) as an improvement of the PL law. A way to get this improvement is to add offsets on the input signal to center it around the zero level and to set the compressing gain in order to maximize the signal occupancy of the ADC's dynamic range. To do this, voltage thresholds are The principle of the law is shown on Figure 14, with a sinusoidal input signal for illustration, and the block diagram is shown on Figure 13. With x(t), w(t), off (t) and y(t) the input signal, the compressed signal, the compressing offset and the expanded signal, the compressing law can be expressed as:

w(t) = x(t) + off (t) (Compressing) y(t) = w(t) -off (t) (Expanding) (4)
An example of the law is given in Figure 14. The gain of the law is shown in Figure 14a whereas the compression step is represented in Figure 14b, with a sinusoidal input signal for illustration. One can see that the dynamic range is reduced by the use of this compressing law.

The most similar approach is the PL law [START_REF] Maheshwari | Companding Baseband Switched Capacitor Filters and ADCs for WLAN Applications[END_REF]. Indeed this law uses functioning states too, but the compressing gain is modified instead of adding an offset regarding the state value. The PL law is thus the most relevant law to compare the additive companding law's performance with. In this report the additive companding law is referred to as a PLCGO to keep the same notation convention as with the PL law.

The PLCGO law has already been implemented in [START_REF] Bes | An additive instantaneously companding readout system for cochlear implants[END_REF] for a different application (i.e. cochlear implants). However, their implementation has the drawback of requiring to save the path that have led to the current state variable value (i.e. the list of the states the signal crossed before arriving in the current state), and not the state variable itself. This can lead to memory issues, especially if a lot of states are used with fast-varying signals. Another implementation is proposed latter in this report.

The Figure 15 outlines the benefit of the PLCGO law (Figure 15c) with regard to the PL law (Fig 15b) with a sinusoidal input (Figure 15a): the quantization noise was dependent on the input signal amplitude with the PL law, leading to a fall of performance because of the presence of the strong signal. This effect has disappeared with the PLCGO law. By comparison with the quantization noise with DD (Figure 15d), one can see that the quantization noise is lessened with the PLCGO law. Moreover, the quantization noise level is independent of the S s /S w value, as with a DD. On Figure 16, the equivalent quantization step of the PLCGO and PL companding laws have been plotted. With the PL law, the quantization step was lower when the input signal was high, but this effect has disappeared with the PLCGO law: the quantization step is uniform whatever the input signal level is. Then the weak signal is properly quantized regardless of the total signal amplitude.

Analytical impact of PLCGO companding

Assuming the input uncompressed signal varies between -V M and V M , the i th threshold will take the value:

V th,i = -V M + 2 •V M N th + 1 • i (5)
with N th being the total number of thresholds. In a given state, the gain G that should be applied to the signal depends on the ADC's dynamic range V ADC and on the number of states N th + 1. As the thresholds are equidistributed, the gain does not depend on i. It can be expressed as the ratio of the ADC full-scale range and the difference of two voltage thresholds:

G = V ADC V th,i+1 -V th,i = (N th + 1) • V ADC 2V M (6)
The impact of this law can be evaluated through the quantization noise. On Figure 14b, it can be seen that after compressing, the total signal's dynamic range is reduced by a factor equal to the number of states. The quantization step ∆ is reduced by the same factor (assuming the signal is scaled to the ADC Figure 16: Equivalent quantization states when using a PLCGO law compression input), since it is the ratio between the dynamic range and the number of quantization states. So, ∆ PLCGO and ∆ DD denoting the equivalent quantization step with the PLCGO compressing law and the quantization step with a DD:

∆ PLCGO = ∆ DD N th + 1 (7)
N Q,PLCGO , N Q,DD are respectively the quantization noise with the PLCGO law and with a DD. The quantization noise being ∆/ √ 12 [START_REF] Gupta | ADC Guide, Part 1 -The Ideal ADC[END_REF], the benefit of the law in terms of quantization noise can be expressed from [START_REF] Bes | An additive instantaneously companding readout system for cochlear implants[END_REF] as:

N Q,PLCGO N Q,DD = ∆ PLCGO ∆ DD = 1 N th + 1 (8)
The quantization step is the ADC full scale voltage divided by the number of quantization states 2 n of the ADC (n being the ADC resolution). n PLCGO and n DD being respectively the equivalent resolution when using the PLCGO compressing law and the real resolution of the ADC, the gain in terms of number of bits of resolution can be expressed from (8) as:

∆ PLCGO ∆ DD = 2 n DD 2 n PLCGO = 1 N th + 1 ⇒ n PLCGO = n DD + log 2 (N th + 1) (9)
The great interest of this approach is highlighted in [START_REF] Tsividis | Externally linear, time-invariant systems and their application to companding signal processors[END_REF], since PLCGO companding allows to save a number of bits equal to the binary logarithm of the number of states. We remind here that 21 bits of resolution are required to digitize the set of received signals in the 8 MHz band. Implementing PLCGO companding with 32 states would require an ADC resolution of 16 bits. Such a resolution is still unaffordable today, but recent work performance [START_REF] Hurrell | An 18 b 12.5 MS/s ADC With 93 dB SNR[END_REF] allows to expect such ADCs will be available in a foreseeable future.

Theoretical performance of the law

The PLCGO law has been first cosimulated to assess the relevance of the approach in a multiple signals case. As previously, a strong and a weak signals are simulated using the Agilent ADS software with a BPSK modulation, a bitrate of 200 kbps and a AWGN. The simulation schematic remains nearly the same as in sections 3 and 4: the only difference is the companding law. The compressing and expanding functions are cosimulated through the MatLab software. The BER on the weak signal is simulated with E b /N 0 = 7 dB while S s /S w and the ADC resolution are varying. The sampling frequency is still of 16 MHz, and the PLCGO companding is performed using 8 states. During the simulations, The ADC resolution and S s /S w are varying from 1 to 25 bits and from 0 to 100 dB. The results are shown on Figure 17. When comparing with the µ-law (Figure 5) and PL law (Figure 10) performance, one can see that the BER does not depend anymore on S s /S w . Moreover, the BER is significantly improved with the PLCGO law, whereas it was only lightly improved with the PL law and degraded with the µ-law.

Other simulations has been done to evaluate the required resolution gain regarding the number of states used in the PLCGO law compression. E b /N 0 still being 7 dB, S s /S w is arbitrary fixed to 50 dB. This value is not of prime importance since the ADC resolution improvement only depends on the number of states. The simulations are done by varying the ADC resolution and the number of states. Assumption is made that there is no delay between the time the signal cross a threshold and the time the appropriate offset is added to the signal.

For a given number of states, the minimum resolution is obtained when the BER value is close to the expected value of 10 -3 (which is the theoretical BER when using a BPSK modulation with E b /N 0 = 7 dB). It can be seen on Figure 18 that rising the number of states allows to reach the expected BER floor with a smaller resolution. The use of 40 states reduces the required resolution by 5 bits, showing the interest of the method.

The relevance of the PLCGO compressing law to reduce the required ADC resolution to digitize multiple signals being proved, the next section's purpose is to propose an implementation of this law.

Inria

Indeed with the implementation proposed in [START_REF] Bes | An additive instantaneously companding readout system for cochlear implants[END_REF], the complete list of states crossed by the signal are saved instead of only saving the state variable itself. In the case of urban sensor networks the signals are fast varying, and thus this approach is not suitable.

6 PLCGO law architecture proposals and implementation 6.1 Impact of the delay of updating of the state variable With the PLCGO law as well as with the PL law, the state variable must be updated when the signal reaches a threshold level to apply respectively the proper offset and gain. The threshold crossing can be detected both in analog or digital domains.

It has been previously assumed that the state variable update was instantaneous, but this assumption does not stand if the threshold crossing detection is performed after digitization. In that case, the delay would be at least one sampling period T s . The existence of this delay of updating is a problem, as during this delay a wrong offset is added to the signal. This can lead to an ADC clipping and thus to the loss of the signal's information during this time interval. This problem cannot be addressed by using a scaling factor between the compression and digitization steps, since the number of thresholds that the signal can cross during the delay of updating cannot be predicted on a real signal.

The impact on a single signal's BER of the state variable delay of updating has been evaluated by performing the compression with a delay set to T s . If ideal companding (i.e. without delay) would allow to properly digitize the signal, the BER remains equal to 0.5 when a delay of T s is added, regardless of the ADC resolution: the delay is so big that the expanding law is almost never applied using the proper state variable. Thus the law must be implemented analogically, to guarantee the delay of updating to be negligible compared to T s .

Implementation proposal

A simple implementation would be to use a Sample and Hold (S&H) device to generate the offsets. But this solution would then rely on time-based discretization, although PLCGO is based on a amplitudebased discretization. The biggest issue of this option is the required digitization of the S&H output signal, which has the same dynamic range as the original signal. It turns out that the digitization of the S&H output implies the same resolution as without companding, meaning 21 bits. Another solution must be found to implement this law.

One can use comparators to generate the offsets. A parallelized and a cascaded implementations are proposed, whose diagrams are shown on Figure 19. In the parallelized implementation (Figure 19a), the comparators compare the signal with pre-defined thresholds that can be generated through bandgap voltage references. Their outputs are summed, giving a proportional value to the offset that must be added to the signal. This value is scaled to generate the real offset and is subtracted from the signal. The resulting signal is then scaled to the ADC input. On Figure 19a, a differential amplifier performs all these operations. Another digitization (not shown on Figure 19a) is still required to get the offset in a digital form. To do this, the comparators outputs are summed, giving the state variable and digitized with a resolution equal to the binary logarithm of the number of thresholds. As it was found through (9) that 32 thresholds should be enough to properly digitize the signal with a 16 bits resolution (with S s /S w = 100 dB), the offsets can be digitized with a 5 bits ADC. So this solution could allow in theory (i.e. without considering the implementation imperfections) to replace one ADC with a 21 bits resolution with two ADCs with resolutions of 16 and 5 bits.

With the cascaded implementation (Figure 19b), the offset value is found iteratively. The first comparator gives the most significant bit of the offset value and this value (V thi ) is scaled to the input signal and subtracted from it through a differential amplifier. The resulting signal is the input signal compressed ADC Simulated BER resolution parallelized cascaded without architecture architecture companding 5 1.7

• 10 -2 1.4 • 10 -2 3.7 • 10 -1 8 1.2 • 10 -3 1.3 • 10 -3 8.6 • 10 -3 25 (11 → ∞) 1.3 • 10 -3 1.1 • 10 -3 1.2 • 10 -3
Table 1: Simulated BER depending on the PLCGO compressing architecture

Discussion on the parallelized and cascaded implementations

From the BER performance perspective, one cannot prefer the cascaded or the parallel implementation.

But both of them has some pros and cons: on one hand the parallelized architecture ensures that an error on one offset does not propagate to the other offsets, contrary to the cascaded architecture. On the other hand, a problem exists on the state transition: when the signal crosses a threshold, the comparators output does not switch from the low to the high state immediately, as the comparator amplifier's gain is not high enough. During this transition time, the offset takes a voltage value ranging between two predefined values. If this happened at an ADC sampling time (assuming the clocks of the offset's ADC and of the compressed signal's ADC are aligned), the signal would be compressed and expanded with a different offset value. The probability of this to happen is smaller with the cascaded architecture, as the amplifiers' gains cumulate from one stage to the other. The selection of a given architecture can also be led from an implementation complexity perspective. The parallelized architecture uses more amplifier stages: a k states compression requires k amplifier stages if they are in parallel, whereas 2 • log 2 (k) amplifier stages are enough if cascaded. To digitize the state variable, the parallelized implementation is more advantageous as it sums the comparators outputs. So it can be digitized using a summing amplifier. In the cascaded implementation case, each comparator output is one bit of the final offset value. The all comparators outputs should be digitized separately, with a one-bit ADC.

Conclusion

In the special case of urban sensor networks, the high dynamic range of received signals makes the digitization of the full band impossible with today's ADCs. A way to tackle this problem is to use the companding technique. Three existing companding laws have been studied: the µ-law, the PL law and the PLCGO law. Only two signals have been considered, one with a low power level (weak signal) and the other one with a high power level (strong signal). The µ-law is considered to be representative of other similarly-shaped companding functions, such as the sinh, tanh or √ functions. The µ-law represents bijective companding functions, whereas the PL law represents the non-bijective functions, which require the use of a state variable. The PLCGO law (which is also non-bijective) is an additive companding technique, and therefore behaves differently than the µ-law and the PL law, which are multiplicative companding techniques. For both the PL and the µ-laws, the performance in terms of BER when demodulating the weak signal and of quantization noise has been studied. The µ-law presents a disappointing performance: the BER is degraded in most of cases, and the quantization noise is globally amplified. The PL law performance is better since it lightly decrease the quantization noise: the BER is then improved. The BER performance and the quantization noise brought by the use of the PLCGO law have also been studied, highlighting the great interest of this approach with multiple signals. The PLCGO law performance is far better than the PL law's one: the quantization noise is drastically reduced by the use of this law. It has been shown that the required resolution to digitize multiple signals can be reduced in theory by five bits by the use of 32 states with this law.

The implementation of the PLCGO law proposed in [START_REF] Bes | An additive instantaneously companding readout system for cochlear implants[END_REF] may not be relevant with the signals considered in urban sensor networks, which are fast-varying signals. For that two implementations of the PLCGO law are proposed, that facilitate the digitization of the state variable. These implementations are based on cascaded or on parallelized amplifiers stages. Both architectures have been simulated using the Agilent ADS software and confirm their expected theoretical performances. The main advantage of the cascaded architecture is its low complexity, whereas the parallelized architecture allows more precision when offsets are generated since an error on one comparator does not propagate to the other ones. However, the cascaded architecture cumulative gain is an advantage, as the comparators saturation is faster, leading to a smaller probability of error when digitizing the state variable.

Both architectures have limits, since the offset must be generated with the same precision than the target equivalent resolution, and its AC component must be less than one LSB. Future work will focus on a physical implementation of these architectures and tests on real systems in order to evaluate this method's feasibility in practice.

Figure 1 :

 1 Figure 1: Required resolution regarding the power ratio between the strong and the weak signal

Figure 3 :

 3 Figure 3: Block diagram of the µ-law

  µ-law, µ=100 S s /S w = 0 dB S s /S w = 20 dB S s /S w = 50 dB S s /S w = 80 dB S s /S w = 100 dB

Figure 5 :Figure 6 :Figure 7 :Figure 8 :

 5678 Figure 5: Simulated BER as a function of S s /S w and of the ADC resolution, with and without companding using a µ-law

Figure 9 :

 9 Figure 9: Example of a PL companding technique

Inria

Figure 10 :

 10 Figure 10: Simulated BER as a function of S s /S w and of the ADC resolution, with and without companding using a PL law

Figure 11 :Figure 12 :Figure 13 :Figure 14 :

 11121314 Figure 11: Quantization noise with a µ-law, PL law and without companding

Figure 15 :

 15 Figure 15: Quantization noise with a PL law, PLCGO law and a DD

Figure 18 :

 18 Figure17: Simulated BER as a function of S s /S w and of the ADC resolution, with and without companding using a PLCGO law

RR n°8683

Vallerian & Hutu & Villemaud & Miscopein & Risset

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Figure 19: Proposed implementations of the PLCGO law with one threshold. Then the second comparator gives the next bit of the offset value, and the corresponding value is subtracted from the signal. This operation is repeated until the total offset has been subtracted from the signal.

Given that the application of this digitization method targets sensors network gateways the main constraint to design a suitable implementation of the companding technique is the demodulation performance. The power consumption is not a key point, as it is assumed that the gateway is powered by the mains supply. These architectures are compared through simulations with a S s /S w ratio of 50 dB. E b /N 0 is still 7 dB in all the simulations, and only the BER considering the weak signal is simulated. With both architectures, 8 states are used in order to compress the signal, allowing in theory (from ( 9)) to save 3 bits. Simulations have been made using ADC resolutions set to 25, 8 and 5 bits. It should be noted that a minimum resolution of 11 bits is required to digitize the signal without companding (see Figure 18), meaning that any resolution higher than 11 bits will provide the same BER performance. A 25-bit resolution therefore represents the expected satisfying level of performance that solutions implementing companding should be compared with. 1 are given with a relative variance of 0.01. They show that both architectures provide good results: the expected gain of 3 bits provided by the PLCGO law is confirmed. Indeed both architectures with 8-bit resolution provide the same BER value as the one provided by the minimum required 11-bit resolution (represented by the 25-bit resolution row). Along the same line, the BER levels obtained with companding with a 5-bit resolution are comparable (even if slightly above) to the BER value of a 8-bit resolution without companding. Inria Inovallée 655 avenue de l'Europe Montbonnot

Results reported in Table