Marc-Aurèle Lagache
email: marc-aurele-lagache@etud-univ-tln.fr

Ulysse Serres
email: ulysse.serres@univ-lyon1.fr

Vincent Andrieu
email: vandrieu@lagep.univ-lyon1.fr

Minimal time synthesis for a kinematic drone model

Keywords: 2010 Mathematics Subject Classification. 93D15, 49J15, 34H05, 49K15, 93C15, 93C10, 34D23 Nonlinear control systems, optimal control, optimal synthesis, Pontryagin Maximum Principle, feedback stabilization

  L'archive ouverte pluridisciplinaire

(Communicated by the associate editor name) 1. Introduction. The purpose of this study is to determine the fastest way (in time) to steer a kinematic UAV (or drone) flying at a constant altitude from any starting point to a fixed horizontal circle of minimum turning radius.

The problem is only described from a kinematic point of view. In particular, we do not take into account the inertia of the drone . We consider that the drone velocities are controlled parameters. In consequence, they are allowed to vary arbitrarily fast.

From the kinematic point of view, a rough drone that flies at a constant altitude is governed by the standard Dubins equations (see e.g. [START_REF] Balluchi | Stability and robustness of optimal synthesis for route tracking by Dubins' Vehicules[END_REF], [START_REF] Dubins | On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[END_REF]):

     ẋ = v cos θ ẏ = v sin θ θ = u, (1.1)
with (x, y, θ) ∈ R 2 × S 1 being the state (where (x, y) ∈ R 2 is the UAV's coordinates in the constant altitude plane, and θ the yaw angle), and u ∈ [-u max , u max ], v ∈ [v min , v max ] being the control variables. Note that the yaw angle θ is the angle between the aircraft direction and the x-axis.

In this paper, only system (1.1) is studied. Despite the fact that our motivation is UAVs, one could apply our results to other control problems modelled by system (1.1).

These equations express that the drone moves on a perfect plane (perfect constant altitude) in the direction of its velocity vector, and is able to turn right and left.

We assume that the controls on the drone kinematics are its angular velocity u and its linear velocity v.

Moreover, we make the assumptions that the linear velocity v has a positive lower bound v min and a positive upper bound v max and that the time derivative u of the drone yaw angle is constrained by an upper positive bound u max .

The above assumptions imply in particular that no stationary or quasi-stationary flights are allowed and that the drone is kinematically restricted by its minimum turning radius r min = v min /u max > 0.

A similar problem with a constant linear velocity has already been addressed in [START_REF] Maillot | Lyapunov and Minimum-Time Path Planning for Drones[END_REF]. The purpose of this paper is to study the influence of a non-constant linear velocity. A preliminary version of this work as been published in [START_REF] Lagache | Time minimum synthesis for a kinematic drone model[END_REF].

Minimum time problem under consideration.

2.1. Optimal control problem. We aim to steer a UAV driven by system (1.1) in minimum time from any given initial position point to the target manifold C which is defined to be the counterclockwise-oriented circular trajectory of minimum turning radius centered at the origin. In the (x, y, θ)-coordinates, C is given by C = {(x, y, θ) | x = r min sin θ, y = -r min cos θ} .

More precisely, we consider the following optimal control problem: (P 0 ) For every (x 0 , y 0 , θ 0 ) ∈ R 2 ×S 1 find a pair trajectory-control joining (x 0 , y 0 , θ 0 ) to C, which is time-optimal for the control system (1.1).

Existence of solutions.

The following two propositions are well-known and stated without proof (see, e.g. [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF]).

Proposition 2.1 (Controllability). System (1.1) is controllable provided that u ∈ [-u max , u max ] and v ∈ [v min , v max ] for any choice of 0 < u max +∞ and 0 < v min v max +∞. Also, Filippov's theorem gives. Proposition 2.2 (Existence of minimizers). For any point (x 0 , y 0 , θ 0 ) ∈ R 2 × S 1 , there exists a time-optimal trajectory joining (x 0 , y 0 , θ 0 ) to C.

Dimension reduction of the system.

To solve problem (P 0 ) it is convenient to work with a reduced system in dimension two. Indeed, in dimension two, a complete theory to build time-optimal syntheses exists and will be described in Section 3.

Let the control set be defined by U = [-u max , u max ] × [v min , v max ] ⊂ R 2 . Also, we introduce the UAV-based coordinates (x, ỹ, θ) with x and ỹ defined by the transformation (in SO [START_REF] Balluchi | Stability and robustness of optimal synthesis for route tracking by Dubins' Vehicules[END_REF]):

x ỹ = cos θ sin θ -sin θ cos θ x y .
The main advantage of this UAV-based coordinate system is that it decouples the variable θ and projects the final manifold C to the point X0 = (0, -r min ). Therefore, the original time-optimal control problem can be equivalently reformulated in the reduced state space (x, ỹ) as the following minimum-time problem:

(P 1 ) For every (x 0 , ỹ0 ) ∈ R 2 find a pair trajectory-control joining (x 0 , ỹ0 ) to X0 = (0, -r min ), which is time-optimal for the control system

ẋ = v + uỹ ẏ = -ux , (u, v) ∈ U. (2.1)
Remark 2.3. One can read, in equation (2.1) that (0, -r min ) is an equilibrium point corresponding to the control values u = u max and v = v min .

The family of all solutions to problem (P 1 ) for (x 0 , ỹ0 ) ∈ R 2 is called the timeoptimal synthesis.

Following a standard approach (see [START_REF] Boscain | Optimal syntheses for control systems on 2-D manifolds[END_REF]) for time-optimal control syntheses, it is convenient to rephrase problem (P 1 ) as an equivalent problem backward in time. Hence, changing the sign of the dynamics, the following equivalent time-optimal problem is considered: (P 2 ) For every (x f , ỹf ) ∈ R 2 find a pair trajectory-control joining X0 = (0, -r min ) to (x f , ỹf ), which is time-optimal for the control system

ẋ = -v -uỹ ẏ = ux , (u, v) ∈ U. (2.2)
Once problem (P 2 ) is solved, then the time-optimal synthesis (corresponding to problem (P 1 )) is obtained straightforwardly following the travelled trajectories backward.

Remark 2.4. Note that up to a dilation in the (x, y)-plane and a dilation of time (a time-reparametrization with constant derivative), we may assume that

[-u max , u max ] × [v min , v max ] = [-1, 1] × [1, η] (η = v max /v min ).
This normalization is used to simplify the treatment in Sections 4 and 5.

3. Time-optimal synthesis on R 2 . In this section, following the same ideas as those developed by Boscain, Bressan, Piccoli and Sussmann in [START_REF] Boscain | Extremal synthesis for generic planar systems[END_REF][START_REF] Boscain | Optimal syntheses for control systems on 2-D manifolds[END_REF][START_REF] Bressan | A generic classification of time-optimal planar stabilizing feedbacks[END_REF][START_REF] Piccoli | Classification of generic singularities for the planar time-optimal synthesis[END_REF][START_REF] Sussmann | Regular synthesis for time-optimal control of single-input real analytic systems in the plane[END_REF] for optimal syntheses on two-dimensional manifolds for single input control systems, we introduce important definitions and develop basic facts about optimal syntheses on R 2 for control-affine systems with two bounded controls (which are different from those studied in [START_REF] Boscain | Nonisotropic 3-level quantum systems: complete solutions for minimum time and minimum energy[END_REF] and [START_REF] Boscain | Minimal time trajectories for two-level quantum systems with two bounded controls[END_REF]). This part is widely inspired by the book [START_REF] Boscain | Optimal syntheses for control systems on 2-D manifolds[END_REF] and extends some of its results.

The definitions and results given in Subsections 3.1, 3.2 and 3.3 are valid in R n for any n. However, starting from Subsection 3.4 results are valid and make sense only for n = 2.

3.1. Pontryagin Maximum Principle. Let F and G be two smooth and complete vector fields on R n . Define the control variable U = (u, v) and the control set

U = [-u max , u max ] × [v min , v max ] ⊂ R 2
, where u max , v min , v max are assumed to be positive. Consider the following general control-affine time-optimal problem. (R) For every X 0 and X f in R n find the pair trajectory-control joining X 0 to X f , which is time-optimal for the control system Thanks to the compactness of the set of controls, the convexity of the set of velocities, and the completeness of the vector fields, Filippov's theorem (see, for instance, [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF]) yields: Proposition 3.2. For any pair of points in R n , there exists a time-optimal trajectory joining them.

Ẋ = vF (X) + uG(X), X ∈ R n , (u, v) ∈ U. ( 3
The main tool to compute time-optimal trajectories is the Pontryagin Maximum Principle (PMP). A general version of PMP can be found in [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF]. The following theorem is a version of PMP for control systems of the form (3.1) that we state in our own context only.

Theorem 3.3 (PMP)

. Consider the control system (3.1). For every (P, X, U ) ∈ R n × R n × U, define the Hamiltonian function

H(P, X, U ) = v P, F (X) + u P, G(X) . (3.2)
Let U (•) be an admissible time-optimal control defined on [t 0 , t 1 ] and let X(•) be the corresponding trajectory. Then there exist a never vanishing Lipschitz covector (or adjoint vector)

P (•) : t ∈ [t 0 , t 1 ] → P (t) ∈ R n and a non negative constant λ such that for almost all t ∈ [t 0 , t 1 ]: i. Ẋ(t) = ∂H ∂P (P (t), X(t), U (t)), ii. Ṗ (t) = - ∂H ∂X (P (t), X(t), U (t)),
iii.

H(P (t), X(t), U (t)) = max W ∈ U H(P (t), X(t), W ), iv. H(P (t), X(t), U (t)) = λ 0.
A pair trajectory-control (X(•), U (•)) (resp. a triplet (P (•), X(•), U (•))) satisfying the conditions given by the PMP is said to be an extremal trajectory (resp. an extremal). An extremal corresponding to λ = 0 is said to be abnormal, otherwise we call it normal.

Remark 3.4. Notice that, up to change U (•) on a set of measure zero, an extremal control can always be chosen so that the function t → H(P (t), X(t), U (t)) is continuous. Consequently, we may always assume (without loss of generality) that condition iv of PMP is valid everywhere.

Basic definitions.

Definition 3.5 (Switching functions). Let X(•) be an extremal trajectory. The corresponding u-and v-switching functions are (the differentiable functions) defined respectively as φ u (t) = P (t), G (X(t)) and φ v (t) = P (t), F (X(t)) .

Switching functions are very important since their analysis determine when the corresponding control may change. Unlike in the single input case, the switching functions are differentiable but not necessarily C 1 .

In the following three definitions (Definitions 3.6-3.8), X(•) is an extremal trajectory defined on the time interval [t 0 , t 1 ] and U (•) : [t 0 , t 1 ] → U is the corresponding control.

Definition 3.6 (Bang). U (•) is said to be a u-bang (resp. v-bang) control if, for a.e. t ∈ [t 0 , t 1 ], u(t) = -u max (or u(t) = u max ) (resp. v(t) = v min (or v(t) = v max )). U (•) is a bang control if, for a.e. t in [t 0 , t 1 ]
, it is u-bang and v-bang. A finite concatenation of bang controls is called a bang-bang control. Definition 3.7 (Singular). We say that U (•) is a u-singular control (resp. vsingular) if the corresponding switching function φ u (resp. φ v ) vanishes identically on [t 0 , t 1 ]. If φ u and φ v both vanish identically on [t 0 , t 1 ], we say that U (•) is totally singular. Definition 3.8 (Switching times). A u-switching time of U (•) is a time τ ∈ (t 0 , t 1 ) such that, for a sufficiently small ε > 0, u(t) = u max for a.e. t ∈ (τ -, τ ] and u(t) = -u max for a.e. t ∈ (τ, τ + ] or vice-versa. A v-switching time is defined similarly. A (u, v)-switching time is a time that is both a u-and a v-switching time. If τ is a switching time, the corresponding point X(τ ) on the trajectory X(•) is called a switching point.

Abnormal trajectories.

The following lemma gives some information on the nature of abnormal extremals of system (3.1). Lemma 3.9. Let γ(•) = (P (•), X(•), U (•)) be an abnormal extremal defined on

[t 0 , t 1 ]. Assume that γ(•) is never totally singular in restriction to any subinterval of [t 0 , t 1 ]. Then γ(•) is bang with v(•) = v min on an open dense subset of [t 0 , t 1 ].
Proof. Since the considered extremal is abnormal, we have, for all t ∈ [t 0 , t 1 ],

H (P (t), X(t), U (t)) = v(t)φ v (t) + u max |φ u (t)| = 0. ( 3
∆ A (X) = det (F (X), G(X)) , ∆ Bu (X) = det (G(X), [F, G](X)) , ∆ Bv (X) = det (F (X), [F, G](X)) ,
whose zero sets are fundamental loci (see [START_REF] Boscain | Optimal syntheses for control systems on 2-D manifolds[END_REF]) in the construction of the optimal synthesis.

Remark 3.11. Notice that, although the functions ∆ A , ∆ Bu and ∆ Bv depend on coordinates in R 2 , the sets ∆ -1 A (0), ∆ -1 Bu (0) and ∆ -1 Bv (0) do not; indeed, they are intrinsic objects related with the control system (3.1).

The following lemma which is a direct generalization of [6, Theorem 12 page 47] is stated without proof. Lemma 3.12. u-singular (resp. v-singular) trajectories are contained in the set

∆ -1 Bu (0) (resp. ∆ -1 Bv (0)). Lemma 3.13 ((u, v)-singular trajectories). (u, v)-singular trajectories are contained in the set ∆ -1 A (0) ∆ -1 Bu (0) ∆ -1 Bv (0). Proof. Let (P (t), X(t), U (t)) be a (u, v)-singular extremal defined on [t 0 , t 1 ]. Then for a.e. t ∈ [t 0 , t 1 ], φ v (t) = P (t), F (X(t)) = 0, φ u (t) = P (t), G (X(t)) = 0,
which implies that P (t) is orthogonal to both F (X(t)) and G(X(t)). But, according to PMP, P (t) cannot vanish, hence, F and G must be parallel along X(•). We thus get X(•) ⊂ ∆ -1 A (0). Moreover, according to Lemma 3.12, we also have ∆ -1 Bu (0) ∆ -1 Bv (0). Remark 3.14. Although it is not addressed here, it can be proved that the intersection ∆ -1 A (0) ∆ -1 Bu (0) ∆ -1 Bv (0) is generically empty. In other words, generically, on R 2 , there is no totally singular trajectories.

The next lemma describes the kind of switches that may occur along singular arcs.

Lemma 3.15. Along a u-singular trajectory which is not totally singular, v is a.e. equal to v max . Along a v-singular trajectory which is not totally singular, a u-switching cannot occur.

Proof. Let (X(•), U (•)) be a u-singular extremal trajectory on [t 0 , t 1 ] which is not totally singular. According to the PMP and since the trajectory is not v-singular, we have

H (P (t), X(t), U (t)) = v(t)φ v (t) = λ > 0 for a.e. t ∈ [t 0 , t 1 ]. Hence, φ v (•) is positive on [t 0 , t 1 ] and consequently v(t) = v max for a.e. t ∈ [t 0 , t 1 ].
The proof for a v-singular trajectory is similar but the PMP yields not the value of the control u along it.

3.5. Switchings. 1 If F 1 and F 2 are two vector fields, [F 1 , F 2 ] denotes their Lie bracket.

if v = v max .
Proof. Let X(•) be a normal trajectory on [t 0 , t 1 ] and let U (•) be the corresponding control. Let τ ∈ (t 0 , t 1 ) be a u-switching time, i.e. φ u (τ ) = 0. From the PMP, we have

H (P (τ ), X(τ ), U (τ )) = v(τ )φ v (τ ) > 0, with v(τ ) > 0. Hence, φ v (τ ) > 0 and thus for sufficiently small, v(t) = v max for a.e. t ∈ [τ -, τ + ].
Remark 3.17. The previous lemma implies in particular that, along a normal trajectory, a v-switching from v max to v min is necessarily followed by another vswitching from v min to v max before a u-switching occurs.

(u, v)-switchings.

Lemma 3.18 ((u, v)-switchings). A (u, v)-switching cannot occur along an extremal trajectory.

Proof. Let (P (•), X(•), U (•)) be an extremal and let τ be a (u, v)-switching time. Since the Hamiltonian is constant along trajectories with

H (P (τ ), X(τ ), U (τ )) = v(τ )φ v (τ ) + u max |φ u (τ )| = 0,
the extremal is abnormal. But, according to Lemma 3.9, an abnormal extremal admits only (u(•), v(•)) = (±u max , v min ) as bang controls and thus cannot have a (u, v)-switching.

Special domains. Using the sets ∆ -1

A (0), ∆ -1 Bu (0) and ∆ -1 Bv (0) defined in Section 3.4, we can define domains in which a control can switch at most once. Consider a point X / ∈ ∆ -1 A (0). Then F (X) and G(X) are linearly independent and form a basis. An easy computation shows that

[F, G] (X) = f (X)F (X) + g(X)G(X), ( 3.4)
with

f (X) = - ∆ Bu (X) ∆ A (X) and g(X) = ∆ Bv (X) ∆ A (X) .
Lemma 3.19. A normal and non-singular trajectory along which f > 0 (resp. f < 0) admits at most one u-switching and necessarily from -u max to u max (resp. from u max to -u max ). Similarly, a normal and non-singular trajectory along which g > 0 (resp. g < 0) admits at most one v-switching and necessarily from v max to v min (resp. from v min to v max ).

Proof. Let (P (•), X(•), U (•)) be a normal, non-singular extremal defined on [t 0 , t 1 ] along which f > 0. At any τ ∈ [t 0 , t 1 ] such that φ u (τ ) = 0, we have

H (P (τ ), X(τ ), U (τ )) = v(τ )φ v (τ ) = λ > 0, which, with equation (3.4), implies φu (τ ) = v(τ ) P (τ ), [F, G](X(τ )) = v(τ )f (X(τ ))φ v (τ ) + v(τ )g(X(τ ))φ u (τ ) = v(τ )φ v (τ )f (X(τ )) > 0. (3.5)
Since, φ u is continuous, we conclude that φ u can vanish at most once in [t 0 , t 1 ]. Moreover, according to inequality (3.5), φu (τ ) and f (X(τ )) have same sign. Consequently, if φ u (τ ) = 0, then φu (τ ) > 0 and u(•) switches at τ from -u max to u max .

Reasoning similarly with φ u replaced by φ v gives the second part of the lemma.

4. Construction of time-optimal synthesis for the reduced system. In this section, we apply the results obtained in the previous sections to solve problem (P 2 ). Although the problem is similar to the one studied in [START_REF] Maillot | Lyapunov and Minimum-Time Path Planning for Drones[END_REF], the resolution is much more complicated due to the presence of a second control.

In this section, for the sake of clarity and without loss of generality, we assume, according to Remark 2.4, that U = [-1, 1] × [1, η]. Note moreover that, in this case, r min = 1.

Application of the Pontryagin Maximum Principle.

First of all, notice that system (2.2) is of the form (3.1) with

X = x ỹ , F ( X) = -1 0 and G( X) = -ỹ x .
We apply PMP to (P 2 ). The control-dependent Hamiltonian function of PMP is

H X, P, U = -vp + u (qx -pỹ) ,
with P = (p, q) ∈ R 2 being the covector. The adjoint system is thus given by ṗ(t) = -u(t)q(t)

q(t) = u(t)p(t) . (4.1)
and the switching functions are

φ u (t) = q(t)x(t) -p(t)ỹ(t), (4.2) φ v (t) = -p(t). (4.3)
The maximality condition of the PMP reads

H X(t), P (t), U (t) = max (u,v)∈ U uφ v (t) + vφ u (t) = λ,
and yields the controls

u(t) = -1 if φ u (t) < 0 1 if φ u (t) > 0 , v(t) = 1 if φ v (t) < 0 η if φ v (t) > 0 . (4.4) Remark 4.1.
The cases where the switching functions vanish identically is addressed in the next subsection.

Singular trajectories. Let us compute the quantities

∆ A (x, ỹ) = -x, ∆ Bu (x, ỹ) = ỹ ∆ Bv (x, ỹ) = 1, f (x, ỹ) = ỹ x , g(x, ỹ) = - 1
x . Lemmas 3.12, 3.13 and 3.15 imply that • there exists no v-singular trajectory (and consequently no totally singular trajectory) since ∆ -1 Bv (0) = ∅;

• u-singular trajectories are contained in the set2

∆ -1 Bu (0) = (x, ỹ) ∈ R 2 | ỹ = 0 .
To compute the corresponding control, we differentiate w.r.t. t the function φ u (which is identically zero). A straightforward calculation yields φu (t

) = η P (t), [F, G] (X(t)) = -ηq(t) = 0, φu (t) = ηu(t) P (t), [G, [F, G]] (X(t)) = ηu(t)p(t) = 0,
which, taking into account that (p(t), q(t)) never vanishes, implies that, along u-singular trajectories, u(•) vanishes identically. Note that this is quite intuitive since u = 0 is the only control that allows the trajectory to stay on the x-axis.

Notation.

The following table defines a naming convention for the five possible optimal controls in order to simplify the description of the trajectories. The 1. Notation of the five possible optimal controls letter stands for u equals to plus (p, P ) or minus (m, M ) one or to the singular control. The lower case and upper case correspond to 1 and η respectively. We define γ i as the trajectory starting from X0 with the control i ∈ {m, M, p, P, s}. Similarly, γ ij denotes the trajectory switching from γ i at time T ij with the control j ∈ {m, M, p, P, s}\{i}, and ζ ij φu (resp. ζ ij φv ) denotes a zero of the switching function on u (resp. v) corresponding to the trajectory γ ij . 4.4. Optimal synthesis algorithm. Since X0 is an equilibrium point of system (1.1) for the control (1, 1) and since X0 / ∈ ∆ -1 Bu (0), there are, a priori, three possible optimal starting trajectories candidates: γ M , γ m and γ P corresponding to the bang controls (-1, η), (-1, 1) and (1, η) respectively (see Fig. 1). The time-optimal synthesis is constructed following the three steps described below.

Control Notation (-1, 1) m (1, 1) p (-1, η) M (1, η) P u-singular s Table
Step 1 For each bang trajectory starting from X0 , compute the last time at which the trajectory is extremal (or has lost its optimality by intersecting itself) and study which kind of extremal trajectories can bifurcate from it.

Step 2 For each bang or singular trajectory bifurcating from one of the starting trajectories, compute the last time at which it is extremal. If there are intersections among trajectories, we cancel those parts that are not optimal (among trajectories already computed up to this step).

Step 3 For each trajectory computed at the previous step that did not loose its optimality, prolong it with the next bang or singular trajectory up to the last time at which it is extremal. If there are intersections among trajectories, cancel those parts that are not optimal (among trajectories already computed up to this step).

(-1, 1) , γ m (-1, η) , γ M (1, η) , γ P x ỹ X0
p(t) = cos (α + t) q(t) = u 0 sin (α + t) , u 0 ∈ {-1, 1}, (4.5)
where α is defined by P (0) = (cos α, u 0 sin α). The condition iv of PMP written at the initial point implies that

(-v 0 + u 0 ) p(0) 0. Since (u 0 , v 0 ) = (1, 1) , (-v 0 + u 0 ) is non-positive. Hence, p(0) = cos α 0 and α ∈ [ π 2 , 3π 2 ]
. The following study consists in analyzing the behaviour of the extremal trajectories depending on the value of (α,

u 0 , v 0 ) ∈ [ π 2 , 3π 2 ]×{(-1, 1), (-1, η), (1, η)}.

4.6.

Step 1: Analysis of the trajectories starting from X0 . This section details the first step (and only this one) of the algorithm described in Section 4.4.

Trajectories corresponding to control (-1, η).

The trajectory γ M starting from X0 with the control (-1, η) has coordinates

x(t) = -(η + 1) sin t ỹ(t) = η -(η + 1) cos t,
and from (4.5), the coordinates of the adjoint vector are

p(t) = cos (t + α) q(t) = -sin (t + α) , with α ∈ [ π 2 , 3π 2 ]
. It follows that the switching functions are

φ u (t) = (η + 1) cos α -η cos (t + α) , φ v (t) = -p(t) = -cos (t + α) .
Recall that the sign of each of these functions determines the value of the corresponding control. It is thus fundamental to study when does a switching function change its sign. Depending on the initial value of the covector parameterized by α the following cases have to be distinguished.

• For α = π/2, φ u starts with value zero and then takes positive values: from (4.4), it cannot correspond to a trajectory starting with control (-1, η). • For α sing = arccos (-η/(η + 1)), φ u starts with negative values and has a zero of order two at t sing = π -α sing . φ v starts with positive values and vanishes after φ u does. The trajectory reaches the x-axis at time t sing . In this case, at time t = t sing , either the trajectory becomes u-singular, switches to (1, η) or does not switch. In the latter case, there is a v-switching at time T M m (α) = -α + 3π/2. • For every α ∈ (π/2, α sing ), φ u starts with negative values and φ v with positive values. The function that vanishes first is φ u . At time T M P (α) = -α + arccos (cos α(η + 1)/η), φ u changes its sign and a u-switching occurs. • For every α ∈ (α sing , 3π/2), φ u is always negative. φ v starts with positive values and changes sign at time T M m (α) = -α + 3π/2. There is a v-switching at this time. • For α = 3π/2, φ v starts with value zero and then takes negative values: from (4.4), it cannot correspond to a trajectory starting with control (-1, η). From this analysis, we define the following families of trajectories issued from γ M : Family 1: trajectories γ M s corresponding to α = α sing = arccos (-η/(η + 1)). and from (4.5), the coordinates of the corresponding adjoint vector are

p(t) = cos (t + α) q(t) = sin (t + α) ,
with α ∈ π 2 , 3π 2 . It follows that the switching functions are

φ u (t) = -(η -1) cos α + η cos (t + α) , φ v (t) = -cos (t + α) .
Similarly to Section 4.6.1, depending on the value of α the following analysis may be performed.

• For α ∈ [ π 2 , 3π 2
), φ u starts with a nonpositive value and then takes negative values: from (4.4), it cannot correspond to a trajectory starting with control (1, η).

• For α = 3π 2 , φ v starts with value zero and then takes negative values: from (4.4), it cannot correspond to a trajectory starting with control (1, η).

We conclude that there is no optimal trajectory starting from X0 with the controls (1, η). 4.6.3. Trajectories corresponding to control (-1, 1). The trajectory γ m starting from X0 with the control (-1, 1) has coordinates

x(t) = -2 sin t ỹ(t) = 1 -2 cos t,
and from (4.5), the coordinates of the adjoint vector are

p(t) = cos (t + α) q(t) = -sin (t + α) .
It follows that the switching functions are

φ u (t) = 2 cos (α) -cos (t + α) , φ v (t) = -cos (t + α) .
The maximization condition iv of PMP implies

φ u (0) = cos (α) 0, φ v (0) = -cos (α) 0, i.e. α ∈ { π 2 , 3π 2
} (in particular, the trajectory is abnormal). Note that φ u and φ v must be negative on a (small) open interval of the form (0, ) since the starting control is the bang control (-1, 1). Moreover, since φ u (0) = φ v (0) = 0 and φu (0) = sin α, φv (0) = sin α, φ u and φ v will be both negative on (0, ) if and only if α = 3π/2. Consequently, there is only one extremal (corresponding to α = 3π/2) starting from X0 with control (-1, 1). The two switching functions along this extremal (φ u (t) = φ v (t) = -sin t) change their sign at t = π and since a (u, v)-switching cannot occur (see Lemma 3.18) the trajectory γ m loses its optimality no later than time π.

4.7.

Step 2: Analysis of the trajectories bifurcating from γ M . At this step we study separately all the bifurcating candidate extremals found at the previous step. 4.7.1. Family 1: singular trajectory. This family corresponds to a trajectory entering the turnpike at the time t sing = π -α sing . From Lemma 3.15, the control (0, η) remains unchanged and the trajectory exits the turnpike with the control v = η. The trajectory is obtained from (2.1) and lies on the turnpike, that is

x(t) = -ηt -(2η + 1) + ηt sing ỹ(t) = 0 , ∀ t > t sing .
It follows from (4.1) that the covector is constant along a u-singular trajectory. Evaluating (4.5) at time t = t sing with α = α sing gives

P (t) = (p(t), q(t)) = (-1, 0), ∀ t > t sing .
The u-singular trajectory is then extremal for any time t > t sing . 4.7.2. Family 2: first switching on u. This family corresponds to the set of trajectories switching from γ M with a u-switching. Recall that the trajectories of this family correspond to controls (1, η) and the u-switching time is T M P (α) = -α + arccos (cos α(η + 1)/η) , with α ∈ π 2 , α sing . The trajectory, obtained from (2.1), is

x(t) = (η + 1) sin(t -2T M P (α)) -2η sin(t -T M P (α)) ỹ(t) = -η -(η + 1) cos(t -2T M P (α)) + 2η cos(t -T M P (α)),
for all t > T M P (α). The covector satisfies (4.1), which leads to the coordinates of the adjoint vector: p(t) = cos(t -α -2T M P (α))

q(t) = sin(t -α -2T M P (α)),
Given the coordinates of the trajectory and the covector, the switching functions are:

φ u (t) = q(t)x(t) -p(t)ỹ(t) = η cos(t -α -2T M P (α)) + (η + 1) cos α -2η cos(α + T M P (α)) = -(η + 1) cos α + η cos(t -α -2T M P (α)) φ v (t) = -p(t) = -cos(t -α -2T M P (α))
As in the previous section, we study the sign of the switching functions. Let ζ M P φu (α) and ζ M P φv (α), both greater than T M P (α), be the first zeros of φ u and φ v respectively. We thus have

φ u (ζ M P φu (α)) = -(η + 1) cos α + η cos(ζ M P φu (α) -α -2T M P (α)) = 0.
Since we seek the first zero of φ u , it follows that

ζ M P φu (α) = α + arccos η + 1 η cos α + 2T M P (α), = -α + 3 arccos η + 1 η cos α .
In the same way, we determine the first zero of φ v , we have

φ v (ζ M P φv (α)) = -cos(ζ M P φv (α) -α -2T M P (α)) = 0.
which gives the v-switching time

ζ M P φv (α) = - π 2 + α + 2T M P (α), = - π 2 -α + 2 arccos η + 1 η cos α .
Evaluating the difference between the two switching times, one can determine which switching function changes sign first. Since α sing < π, the difference

ζ M P φu (α) -ζ M P φv (α) = arccos η + 1 η cos α + π 2
is positive for all α ∈ π 2 , α sing . The next switching is then a v-switching which occurs at a time T M P p (α) = ζ M P φv (α) for this family of trajectories.

The curve made of v-switching points is called v-switching curve. This curve, parametrized by α, is given by

       xMP sw (α) = x(T M P p (α)) = (η + 1) cos α ỹMP sw (α) = ỹ(T M P p (α)) = -η -(η + 1) sin α + 2η 1 - η + 1 η cos α 2 ,
with α ∈ π 2 , α sing . On Fig. 2, this curve is shown in gray.

Family 3: first switching on v.

This family corresponds to the set of trajectories switching from γ M with a v-switching. Recall that the trajectories of this family correspond to a control (-1, 1) and a v-switching time T M m (α) = -α+3π/2, with α ∈ [α sing , 3π 2 ). For all t > T M m (α), the trajectory is

x(t) = (η -1) cos(α + t) -(η + 1) sin t ỹ(t) = 1 -(η + 1) cos t -(η -1) sin(α + t)
and the covector is given by

p(t) = sin(t -T M m (α)) = cos(t + α) q(t) = cos(t -T M m (α)) = -sin(t + α).
Since the Family 3 of extremals results from a switching on v, according to Remark 3.17, the next switching is a v-switching. Moreover, since φ v (t) = -p(t) the next switching occurs at time T M mM (α) = π + T M m (α) = -α + 5π/2. As for the Family 2, we get the corresponding parametric equation of the switching curve:

xMm sw (α) = -(η + 1) cos α ỹMm sw (α) = (2 -η) -(η + 1) sin α , α ∈ α sing , 3π 2 .
All results of Subsections 4. During the construction of the optimal synthesis some special curves appears, namely

• switching curves, i.e. curves made of switching points;

• cut loci, i.e. sets of points where the extremal curves of problem (P 2 ) lose global optimality. In practice, switching curves and cut loci can be very difficult to compute. In the following, some of them were computed numerically. Following the algorithm described in Section 4.4, the time-optimal synthesis corresponding to the problem (P 1 ) has been solved. The corresponding (discontinuous) state-feedback is given in Fig. 3 and Table 2 as a partition of the reduced state space. Remark 5.1. Note that the first version of the synthesis (Fig. 3) presented without detail in the conference paper [START_REF] Lagache | Time minimum synthesis for a kinematic drone model[END_REF] is mistaken. Indeed, in [START_REF] Lagache | Time minimum synthesis for a kinematic drone model[END_REF], the synthesis is incomplete since the last arc γ M P pP M m of Family 2 is missing. Remark 5.2. Notice that the minimum time function (as a function of x and ỹ) is not continuous along the abnormal trajectory. As a consequence, the optimality of the synthesis cannot be confirmed a posteriori using the verification theorem ([13, Theorem 2.13]) based on the notion of regular synthesis as it was done in [START_REF] Souères | Optimal feedback control for route tracking with a bounded-curvature vehicle[END_REF] for the case of the Dubins' system for tracking a rectilinear route in minimum time. Indeed, it is easy to see that the minimum time function is not weakly upper semicontinuous (w.u.s.c. for short) and thus does not match the hypothesis of [START_REF] Piccoli | Regular synthesis and sufficiency conditions for optimality[END_REF]Theorem 2.13].

To see this let Xn → X0 as n → ∞ where Xn = (x n , ỹn ), with xn > 0, belongs to the v-switching curve passing through X0 . Denote by V (X) the minimum time to ỹ x X0 Figure 3. Time-optimal synthesis for the problem (P 1 ) reach X0 from X. We have V ( X0 ) = 0. The v-switching occurring on the considered switching curve is a switching from η to 1. Then, according to Remark 3.17 and since

φ v (t) = -cos (α + t), V ( Xn ) > π. Consequently, lim n→∞ V ( Xn ) π > 0 = V ( X0 )
which shows that V is not w.u.s.c. at X0 . 5.2. Verification of the synthesis. Using Lemma 3.19 for the problem (P 1 ), one can check the given synthesis. We have the functions:

f ( X) = - ∆ Bu ( X) ∆ A ( X) = - ỹ x and g( X) = ∆ Bv ( X) ∆ A ( X) = 1 x .
We define four domains according to the values of f and g (see Figure 4). We conclude that there is at most one switching on u in each domains and at most one switching on v in the union of domains 1 and 4 and in the union of 2 and 3. Moreover,

• in orthants 1 and 3: only a u-switching from 1 to - • in orthants 2 and 4: only a u-switching from -1 to 1 is allowed, • in the union of orthants 1 and 4: only a v-switching from η to 1 is allowed, • in the union of orthants 2 and 3: only a v-switching from 1 to η is allowed. One can easily check that the synthesis given in Figure 3 respects Lemma 3.19.

f > 0 g < 0 f < 0 g < 0 f < 0 g > 0 f > 0 g > 0 x ỹ 2 3 1 4 Figure 4.
Domains on which at most one switching is possible 5.3. Correspondence with problem (P 0 ). The solutions of problem (P 0 ) can be deduced from the solutions of problem (P 1 ). In this section, we display pairs of figures (Fig. 5 and6) showing two solutions of problem (P 1 ) (that start from the same point in the cut locus) and the corresponding lifted solutions of problem (P 0 ). Notice that the singular trajectory go straight to the center of the target. 5.4. Stability of the optimal feedback control. We have shown that the discontinuous feedback control law is a time-optimal feedback for system (2.1). However, the optimality of the feedback does not imply Lyapunov stability (see e.g. the beautiful and simple example in [START_REF] Boscain | Encyclopedia of Systems and Control, chapter Synthesis Theory in Optimal Control[END_REF]. In our case we have the following proposition.

Proposition 5.3. The time-optimal feedback law renders system (2.1) globally asymptotically stable.

Proof. The convergence to the equilibrium X0 follows from the optimality of the synthesis (actually, the equilibrium is even reached in finite time). We prove the stability by a direct application of Lyapunov's definition (in the reduced space). A Consequently, for every > 0, choosing either δ = 1 if (2(η -1) + 1) or δ = ((η -1) 2 + 2 ) -(η -1) otherwise we obtain

∀ > 0 ∃ δ > 0 | X(t; Z) -X0 , ∀ t 0, ∀ Z ∈ B( X0 , δ).

Conclusion.

In this paper we have solved a time-minimal control problem for a kinematic model describing a UAV flying at constant altitude with controls on the steering angle and on the linear velocity. Thanks to a change of coordinates applied to the three-dimensional Dubins' system, we could simplify the problem and use (and extend) the existing theory of time-optimal syntheses for two-dimensional single input affine control systems to two-dimensional affine control systems with two inputs. We gave the time-optimal synthesis as a state-feedback law such that the target is reached optimally in finite time. Note however that our kinematic model does not actually correspond to a realistic dynamic, as the velocities may not be continuous. A more challenging problem would be to consider a model with controls on accelerations.

Appendix: construction details of the synthesis.

A.1. 3rd arc.

A.1.1. Family 1. In this subsection, we study the trajectories bifurcating from the singular trajectory γ M s . A trajectory exiting the turnpike has either the control (-1, η) or the control (1, η).

From each point

x(τ ) = -ητ -(2η + 1) + ηt sing ỹ(τ ) = 0 , ∀ τ > t sing ,
two trajectories bifurcate. This family of trajectories is then parametrized by τ instead of α. For u ∈ {-1, 1} and for all t > τ the corresponding trajectory is

     x(t) = -(2η + 1) -ητ + ηt sing cos(t -τ ) -η sin(t -τ ) ỹ(t) = u -η + -(2η + 1) -ητ + ηt sing sin(t -τ ) + η cos(t -τ ) ,
the covector is

p(t) = -u cos(t -τ ) q(t) = -sin(t -τ ),
the switching functions, defined by (4.2) and (4.3), are

φ u (t) = η -η cos(t -τ ), φ v (t) = u cos(t -τ ).
Since in each case φ u > 0, the next switching occurs on the control v at time

T M sP p (τ ) = T M sM m (τ ) = τ + π/2.
The parametric equations of the corresponding switching curve is

xMsi sw (τ ) = -η ỹMsi sw (τ ) = u(-η -(2η + 1) -ητ + ηt sing ),
with i = P (resp. M ) for u = 1 (resp. -1).

A.1.2. Family 2. In this subsection, we study the trajectories γ M P p switching from γ M P at a time T M P p (α) with a control (1, 1) and α ∈ π 2 , α sing . These trajectories start from the parametrized curve

       xMP sw (α) = (η + 1) cos α ỹMP sw (α) = -η -(η + 1) sin α + 2η 1 - η + 1 η cos α 2 , (A.1)
and, for all t T M P p (α), have coordinates

x(t) = xMP sw (α) cos(t -T M P p (α)) -(1 + ỹMP sw (α)) sin(t -T M P p (α)) ỹ(t) = (1 + ỹMP sw (α)) cos(t -T M P p (α)) + xMP sw (α) sin(t -T M P p (α)) -1 (A.2) with T M P p (α) = -π/2 -α + 2 arccos η+1 η cos α = -π 2 + α + 2T M P (α) , i.e.                                              x(t) = (η -1) cos t + α -2 arccos η + 1 η cos α -2η sin t + α -arccos η + 1 η cos α + (η + 1) sin t + 2α -2 arccos η + 1 η cos α ỹ(t) = -1 -(η -1) sin t + α -2 arccos η + 1 η cos α + 2η cos t + α -arccos η + 1 η cos α -(η + 1) cos t + 2α -2 arccos η + 1 η cos α .
By continuity of the covector, we have P (T M P p (α)) = (0, 1), the covector is then given by p(t) = -sin(t -T M P p (α))

q(t) = cos(t -T M P p (α)) , ∀ t T M P p (α) .
Since the previous switching was a v-switching from η to 1, the next switching will be a v-switching (see Remark 3.17) and will occur after a duration π since (φ u (t) = p(t) is a sinusoidal function). We then have T M P pP (α) = T M P p (α) + π = π/2 -α + 2 arccos η+1 η cos α . The switching curve is then given by xMP p sw (α) = x(T M P pP (α)) = x(T M P p (α) + π) ỹMP p sw (α) = ỹ(T M P pP (α)) = ỹ(T M P p (α) + π).

which, using (A.2), becomes

xMP p sw (α) = -x M P sw (α) ỹMP p sw (α) = -2 -ỹMP sw (α), (A.3)
where xMP sw and ỹMP sw are given by (A.1). A.1.3. Family 3. In this subsection, we study the trajectories γ M mM switching from γ M m at a time

T M mM (α) = π + T M m (α) = -α + 5π/2 with a control (-1, η) and α ∈ α sing , 3π
2 . These trajectories starts from the parametrized curve xMm sw (α) = -(η + 1) cos α ỹMm sw (α) = (2 -η) -(η + 1) sin α. For all t T M mM (α), the trajectories are

x(t) = xMm sw (α) cos(-t + T M mM (α)) + (η -ỹMm sw (α)) sin(-t + T M mM (α)) ỹ(t) = η -(η -ỹMm sw (α)) cos(-t + T M mM (α)) + xMm sw (α) sin(-t + T M mM (α)
), which, after simplifications, yields

x(t) = -(η + 1) sin t + 2(η -1) cos(t + α) ỹ(t) = η -2(η -1) sin(t + α) -(η + 1) cos t.
By continuity, P (T M mM (α)) = (0, 1) and for all t T M mM (α) the covector is

p(t) = sin(t -T M mM (α)) = sin(t + α -5π/2) = cos(t + α) q(t) = cos(t -T M mM (α)) = cos(t + α -5π/2) = -sin(t + α).
The switching functions, defined by (4.2) and (4.3), are then

φ u (t) = (η + 1) cos α -η cos(t + α), φ v (t) = -cos(t + α).
The analysis of these switching functions shows that

• for α ∈ [α sing , 2π -arccos(-η/(η + 1))] φ u is always negative. φ v starts with positive values and changes sign at time T M mM m (α) = T M mM (α) + π, at which a v-switching occurs. • for α ∈ [2π -arccos(-η/(η + 1)), 3π/2] φ u starts with negative values and φ v with positive values. The function that has a zero first is φ u and there is a u-switching at time T M mM P (α) = T M mM (α) -arcsin((η + 1)/η cos α)

For α ∈ [2π -arccos(-η/(η + 1)), 3π/2], the switching curve is given by

                 xMmM sw (α) = -(η + 1) cos -α -arcsin η + 1 η cos α + 2 (η 2 -1) η cos α ỹMmM sw (α) = η -2(η -1) cos arcsin η + 1 η cos α + (η + 1) sin -α -arcsin η + 1 η cos α .
We will see later that the switching curve for the other interval of α is not needed (see Remark A.1, page 25).

A.1.4. Reduction of γ M P p , γ M m and γ M mM . The plot of the trajectories computed previously (see left part of Fig. 8) shows that γ M P p intersects with γ M m and γ M mM . We then have to compute when the optimality of each trajectory is lost. This computation has been made numerically for η = 2 and indicates that • for α ∈ [α M P p , α sing ], with α M P p 2.19947, the trajectories γ M P p loose their optimality. γ M P pP is then defined for α ∈ (π/2, α M P p ). • for α ∈ [α sing , α M mM ], with α M mM 3.84506, the trajectories γ M m or γ M mM loose their optimality. γ M mM P is then defined for α ∈ (α M mM , 3π/2).

The times at which trajectories loose optimality, although not detailed here, allow to plot the corresponding cut locus (in green on the right part of Fig. 8). The rest of the synthesis will be restricted to the above-mentioned intervals.

A.2. 4th arc.

A.

           x(t) = -η sin(t -τ )+ (1 -η -(2η + 1) -ητ + ηt sing ) cos(t -τ ) ỹ(t) = -1 + η cos(t -τ )+ (1 -η -(2η + 1) -ητ + ηt sing ) sin(t -τ ).
By continuity of the covector P (T M sP p (τ )) = (0, -1) and the covector is

p(t) = sin(t -T M sP p (τ )) = -cos(t -τ ) q(t) = -cos(t -T M sP p (τ )) = -sin(t -τ ) , ∀ t T M sP p (τ ).
Since the last switching was a v-switching from η to 1, the next switching will be a v-switching. Taking into account the form of φ v , the switching will occur after a duration π. We conclude that T M sP pP (τ ) = T M sP p (τ ) + π = τ + 3π/2. The plot of the trajectories shows that trajectories γ M sM m and γ M sP p will necessarily intersect before reaching their next switching curve, which, therefore does not need to be computed. Moreover, since for a same τ , γ M sM m (t) and γ M sP p (t) are symmetric with respect to the x axis, they will reach the x axis at the same time. We obtain that the set

(x, ỹ) | x > η 2 -1 + 1 -η -(2η +
                                             x(t) = 2(η -1) cos t + α -2 arccos η + 1 η cos α -2η sin t + α -arccos η + 1 η cos α + (η + 1) sin t + 2α -2 arccos η + 1 η cos α ỹ(t) = -η + 2(η -1) sin t + α -2 arccos η + 1 η cos α + 2η cos t + α -arccos η + 1 η cos α -(η + 1) cos t + 2α -2 arccos η + 1 η cos α .
The covector is then p(t) = -sin(t -T M P pP (α))

q(t) = cos(t -T M P pP (α)), which leads to        p(t) = cos t + α -2 arccos η + 1 η cos α q(t) = sin t + α -2 arccos η + 1 η cos α ,
The switching functions, defined by (4.2) and (4.3), are then

φ u (t) = -(η + 1) cos α -η cos t + α -2 arccos η + 1 η cos α , φ v (t) = cos t + α -2 arccos η + 1 η cos α .
The analysis of these switching functions for α ∈ (π/2, α M P p ) shows that the next switching will be a u-switching that will occur at time

T M P pP M (α) = T M P pP (α) -arcsin η + 1 η cos α = -α + 3 arccos η + 1 η cos α .
The switching curve is then

                         xMP pP sw (α) = η + 1 η cos α -3η cos arcsin η + 1 η cos α + 2(η -1) sin α + (η + 1) sin α ỹMP pP sw (α) = -3η + (η + 1) cos arcsin η + 1 η cos α sin α + 3η η + 1 η cos α 2 + 2(η -1) cos arcsin η + 1 η cos α .
A.2.3. Reduction of γ M P pP and γ M mM . The simulation shows that γ M P pP and γ M mM intersect themselves. The corresponding cut locus is computed numerically and it yields:

• for α ∈ [α M P pP , α sing ], with α M P pP 2.18628, the trajectories γ M P pP loose their optimality. γ M P pP M is then defined for α ∈ (π/2, α M P pP ).

• for α ∈ [α sing , α M mM ], with α M mM 4.09691, the trajectories γ M mM loose their optimality. γ M mM P is then defined for α ∈ (α M mM , 3π/2).

The remaining part of the synthesis will be restricted to the above-mentioned intervals.

Remark A.1. Recall that the trajectories γ M mM m are defined for α ∈ [α sing , 2πarccos(-η/(η + 1))]. Since η = 2, α M mM > 2π -arccos(-η/(η + 1)), these arcs do not appear because γ M mM looses its optimality before switching to γ M mM m . A.2.4. Family 3. In this subsection, we study the trajectories γ M mM P switching from γ M mM at a time T M mM P (α) = -α + 5π/2 -arcsin((η + 1)/η cos α) with a control (1, η) and α ∈ (α M mM , 3π/2). The starting points are on the parametrized curve

                 xMmM sw (α) = -(η + 1) cos -α -arcsin η + 1 η cos α + 2 (η 2 -1) η cos α ỹMmM sw (α) = η -2(η -1) cos arcsin η + 1 η cos α + (η + 1) sin -α -arcsin η + 1 η cos α .
For all t T M mM P (α), the trajectory is

     x(t) = xMmM sw (α) cos(t -T M mM P (α)) -(η + ỹMmM sw (α)) sin(t -T M mM P (α)) ỹ(t) = -η + (η + ỹMmM sw (α)) cos(t -T M mM P (α)) + xMmM sw (α) sin(t -T M mM P (α)).
By continuity of the covector we have

       p(T M mM P (α)) = - η + 1 η cos α q(T M mM P (α)) = cos arcsin η + 1 η cos α .
The covector is then given by

       p(t) = cos t + α -2 arccos η + 1 η cos α q(t) = sin t + α -2 arccos η + 1 η cos α .
The switching functions, defined by (4.2) and (4.3), are then

φ u (t) = cos arcsin η + 1 η cos α xMmM sw (α) + η + 1 η cos α (η + ỹMmM sw (α)) -η cos t + α -2 arccos η + 1 η cos α , φ v (t) = -cos t + α -2 arccos η + 1 η cos α .
The analysis of these switching functions shows that the next switching will be a v-switching that will occur at time

T M mM P p (α) = -α + 5π/2 -2 arcsin η + 1 η cos α = T M mM P (α) -arcsin η + 1 η cos α .
This switching time leads to the switching curve:

                          xMmMP sw (α) = xMmM sw (α) cos arcsin η + 1 η cos α -(η + ỹMmM sw (α)) η + 1 η cos α ỹMmMP sw (α) = -η + (η + ỹMmM sw (α)) cos arcsin η + 1 η cos α + xMmM sw (α) η + 1 η cos α .
A.2.5. Family 2. In this subsection we study the trajectories γ M P pP M switching from γ M P pP at time T M P pP M = -α + 3 arccos η+1 η cos α with control (-1, η) and α ∈ (π/2, α M P pP ). We recall The analysis of these switching functions shows that the next switching will be a v-switching and will occur at time

                         xMP pP sw (α) = η + 1 η cos α -3η cos arcsin η + 1 η cos α + 2(η -
T M P pP M m (α) = T M P pP M (α) -arcsin η + 1 η cos α = -α - π 2 + 4 arccos η + 1 η cos α .
The switching curve is then A.2.6. Reduction of γ M P pP and γ M P pP M . The simulation shows that γ M P pP and γ M P pP M intersect themselves. Notice that this is a particular case because these trajectories belong to the same family (see e.g. Fig. 9). The corresponding cut locus is computed numerically and it yields that for α ∈ [α M P pP M , α M P pP ), with α M P pP M = 2.13033, the trajectories γ M P pP loose their optimality. γ M P pP M m is then defined for α ∈ (π/2, α M P pP M ).

                    
The rest of the synthesis will be restricted to the above-mentioned intervals.

A.3. 5th arc:

A.3.1. Family 3. In this subsection we study the trajectories γ M mM P p switching from γ M mM P at time T M mM P p = -α + 5π/2 -2 arcsin η+1 η cos α with control (1, 1) and α ∈ (α M mM , 3π/2). We recall that these trajectories start from Since the previous switching occurred on v, the next switching will also be on v and will occur after a time π (following the same reasoning as previously). At this step of the construction of the synthesis, we immediately see that the next switching will not occur. Indeed, these trajectories will necessarily intersect with trajectories found earlier in the construction of the synthesis before reaching their switching curve. A.3.2. Family 2. In this subsection we study the trajectories γ M P pP M m switching from γ M P pP M at time T M P pP M m = -α -π 2 + 4 arccos η+1 η cos α with control (-1, 1) and α ∈ (π/2, α M P pP M ).

                        
The trajectories are Since the previous switching occurred on v, the next switching will also be on v and will occur after a time π (following the same reasoning as previously). At this step of the construction of the synthesis, we immediately see that the next switching will not occur. Indeed, these trajectories will necessarily intersect with trajectories found earlier in the construction of the synthesis before reaching their switching curve. A.3.3. Reduction of γ M mM P , γ M mM P p , γ M P pP M and γ M P pP M m . The simulation shows that γ M P pP M m intersects with γ M mM P , γ M mM P p and γ M P pP M (see Fig. 9). The corresponding cut locus is computed numerically.

           x(t) =
It also appears that γ M mM P p intersects with the abnormal trajectory γ m . Clearly, γ M mM P p looses its optimality at this intersection. A part of the abnormal trajectory is then a cut locus (in cyan on Fig. 3). Since no new trajectories can be generated, the construction of the synthesis stops.

3. 5 . 1 .

 51 u-switchings. Lemma 3.16. Along a normal extremal trajectory, a u-switching can occur if and only

Figure 1 .Remark 4 . 2 .

 142 Figure 1. Candidate extremal trajectories of problem (P 2 ) issued from X0

Family 2 : 4 . 6 . 2 .

 2462 trajectories γ M P corresponding to α ∈ (π/2, α sing ]. Family 3: trajectories γ M m corresponding to α ∈ [α sing , 3π/2). Trajectories corresponding to control (1, η). The trajectory γ P starting from X0 with the control (1, η) has coordinates x(t) = -(η -1) sin t ỹ(t) = -η + (η -1) cos t

5 .Figure 2 . 5 . 1 .

 5251 Figure 2. Extremal trajectories starting from X0 and having one switching

Figure 5 .x ỹX 0 CFigure 6 .Figure 7 .

 5067 Figure 5. Bang-bang-singular-bang optimal trajectories. Two optimal trajectories solutions of problem (P 1 ) starting from the same point in the cut locus (left) and the corresponding optimal trajectories solutions of problem (P 0 ) (right) y x x ỹX 0 C

2 . 1 .Figure 8 .

 218 Figure 8. Intersection of γ M P p with γ M m and γ M mM (left) and the corresponding cut locus (right)

1 )+ 1 η cos α sin α + 3η η + 1 η cos α 2 + 2 -

 122 sin α + (η + 1) sin αỹMP pP sw (α) = -3η + (η + 1) cos arcsin η (η -1) cos arcsin η + 1 η cos α . cos(t -T M P pP M (α)) -(η -ỹMP pP sw (α)) sin(t -T M P pP M (α)) ỹ(t) = η -(η -ỹMP pP sw (α)) cos(t -T M P pP M (α)) -xMP pP sw (α) sin(t -T M P pP M (α)). ) = cos t + α -4 arccos η + 1 η cos α q(t) = -sin t + α -4 arccos η + 1 η cos α .We have then the switching functions, defined by (4.2) and (4.3), φ u (t) = xMP pP sw η cos t + α -4 arccos η + 1 η cos α , φ v (t) = -cos t + α -4 arccos η + 1 η cos α .

  For all t T M mM P p (α), the trajectories are cos(t -T M mM P p (α))-(1 + ỹMmMP sw (α)) sin(t -T M mM P p (α)) ỹ(t) = -1 + (η + ỹMmMP sw (α)) cos(t -T M mM P p (α)) + xMmMP sw (α) sin(t -T M mM P p (α)),

  xMP pP M sw (α) cos(t -T M P pP M m (α)) -(1 -ỹMP pP M sw (α)) sin(t -T M P pP M m (α)) ỹ(t) = 1 -(1 -ỹMP pP M sw (α)) cos(t -T M P pP M m (α)) -xMP pP M sw (α) sin(t -T M P pP M m (α)).

Figure 9 .

 9 Figure 9. Intersection of γ M P pP M m with γ M mM P , γ M mM P p and γ M P pP M

Table 2 .

 2 Color convention of the optimal synthesis

	1 is allowed,

  [START_REF] Agrachev | Control theory from the geometric viewpoint[END_REF]

	forms a cut locus.
	A.2.2. Family 2. Trajectories of Family 2 bifurcate from γ M P p at time T M P pP (α) =
	π/2 -α + 2 arccos η+1 η cos α , with control (1, η). Notice that after reduction of
	this family, we have α ∈ (π/2, α M P p ). γ M P p starts from the switching curve
	      	xMP p sw (α) = -(η + 1) cos α ỹMP p sw (α) = (η -2) + (η + 1) sin α -2η 1 -	η + 1 η	cos α	2	,
	and has, for all t T M P pP (α), coordinates
	x(t) = xMP p sw (α) cos(t -T M P pP (α)) -(η + ỹMP p sw	(α)) sin(t -T M P pP (α))
	ỹ(t) = -η + (η + ỹMP p sw	(α)) cos(t -T M P pP (α)) + xMP p sw (α) sin(t -T M P pP (α)).
	which is equivalent to
				2
					and ỹ = 0

According to[START_REF] Boscain | Optimal syntheses for control systems on 2-D manifolds[END_REF], the set {(x, ỹ) ∈ R 2 | ỹ = 0} is a turnpike.

The authors were partially supported by the Grant ANR-12-BS03-0005 LIMICOS of the ANR..


Ayse Unsal
email: ayse.unsal@insa-lyon.fr

Jean-Marie Gorce
email: jean-marie.gorce@insa-lyon.fr

κβ Bounds for Gaussian Broadcast Channels with Finite Blocklength

Dans cet article, nous étudions les performances atteignables d'une transmission par superposition de codes dans un canal Gaussien à diffusion avec deux récepteurs et en régime à longueur de codes finie. Dans ce but, nous adaptons la borne atteignable introduite par Polyanskiy et al. en 2010 pour un canal point à point au canal à diffusion. De plus, une nouvelle borne supérieure (converse) est proposée et caractérise les débits conjoints non atteignables en fonction de la longueur des codes et pour une probabilité d'erreur donnée.

Introduction

The strongest results from classical information theory hold for vanishing error probability and asymptotically large blocklengths or equivalently signal dimensionality in analyzing the performance limits of communication systems. In the finitedimensional case imposed by small payload transmission, many of the classical error-probability bounds stemming from information theoretic results are no longer applicable, especially for multiuser channels due to delay and complexity limitations. In the asymptotic regime, the channel coding rate approaches the mutual information which is the expectation of the information density or the mutual information random variable based on the joint probability density function of the input and output. The mutual information random variable is a theoretic notion, some measure, of the channel depending on the input signal and the channel noise to be defined later. It is shown by Strassen in 1962 that the variance of the mutual information random variable, namely the channel dispersion term denoted V , plays a crucial role for a discrete memoryless channel (DMC) in the finite blocklength regime and that the logarithm of the maximal code size M * (n, ) is given as a function of the error probability and the blocklength n as follows

log M * (n, ) = nC -Q -1 ( ) √ nV + O(log n) (1)
where C denotes the channel capacity. In [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF], Polyanskiy et al.

analyzed the performance of coding with finite blocklength for various types of point-to-point (P2P) channels.

In [START_REF] Tan | On the dispersions of three network information theory problems[END_REF], the results of [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF] is adapted to the Slepian-Wolf problem, multiple-access channel (MAC) and asymmetric broadcast channel (ABC). In [START_REF] Molavianjazi | A second-order achievable rate region for Gaussian multi-access channels via a central limit theorem for functions[END_REF], maximum achievable rate regions are presented for the DM-MAC and the Gaussian MAC.

In this paper, we consider a two-receiver degraded Gaussian broadcast channel (BC) using superposition coding with finite blocklength and adapt the so-called κβ bound to the two-user broadcast setting. κβ achievability bounds, which are based on a binary hypothesis test to choose between two possible output distributions, are derived on the maximal code sizes for each user as functions of the error probability and the blocklength. In addition, we adapt the converse bound on the maximal code size of the P2P AWGN channel by Polyanskiy et al. to the two-receiver Gaussian BC.

The next section describes the considered model for the addressed problem.Section 3 provides a short reminder of the original κβ bound for the AWGN P2P channel which is followed by its generalization to the degraded Gaussian BC in the setting of superposition coding. New converse bounds on the code sizes of each user and on their product are presented in Section 4 in addition to the numerical comparison results of the obtained bounds.

System Model

We consider the real-valued channel model

Y j,i = X i + Z j,i , (2)
for j = 1, 2 and i = 1, • • • , n where X i corresponds to the encoded messages

m 1 ∈ [1, 2, • • • , M 1 ] and m 2 ∈ [1, 2, • • • , M 2 ],
respectively with the channel noise terms Z 1,i ∼ N (0, N 1 ) and Z 2,i ∼ N (0, N 2 ) for N 2 > N 1 and the following channel transition probability density

P Y n j |X n (y n j |x n ) = (2πN j ) -n/2 e - y n j -x n 2 2N j . (3)
User j decodes message mj from observation Y n j . We assume that the channel of user 2, the weaker user, has the larger of the two noise variances. For the achievable scheme considered here, the stronger user decodes the message m2 prior to decoding its own message. We have the overall average error probability defined as

= 1 + 2 (4)
where j = Pr [ mj = m j ]. For the achievability scheme based on successive decoding using m2 we have for 1

1 = Pr { m2 = m 2 } Pr { m1 = m 1 }|{ m2 = m 2 } + Pr { m2 = m 2 } Pr { m1 = m 1 }|{ m2 = m 2 } ≤ 11 + 21 (5)
where

11 = Pr { m1 = m 1 }|{ m2 = m 2 } and 21 = Pr { m2 = m 2 }
. The decoding rule is set for the threshold decoding as i(

x n ; y n ) > log η ( 6
)
where η is some threshold and the information density or the mutual information random variable denoted i(.; .) is defined as

i(x n ; y n ) :== log dP Y n |X n (y n |x n ) dP Y n (y n ) (7)
Here P (., .), P (.|.) and P (.) respectively denote joint, conditional and marginal distributions.

For the broadcast adaptation of the κβ bound [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF], we also assume codebooks constructed as X n = X n 1 + X n 2 and we define the power constraint on the channel input

x n (m 1 , m 2 ) 2 = n i=1 |x 1,i (m 1 , m 2 ) + x 2,i (m 2 )| 2 ≤ nP, (8
) ∀m 1 , m 2 where we consider the equal power per codeword for the cloud center X 2,i (m 2 )

for i = 1, • • • , n, m 2 = 1, • • • , M 2 and m 1 = 1, • • • , M 1 s.t. n i=1 |x 2,i (m 2 )| 2 = nP 2 , ∀m 2 . ( 9
)
For X 1,i (m 1 , m 2 ) we have

x n (m 1 , m 2 ) 2 = x 1 (m 1 , m 2 ) 2 + x 2 (m 2 ) 2 + 2 x 1 (m 1 , m 2 ), x 2 (m 2 ) (a) = nP 1 (m 1 , m 2 ) + nP 2 + 2nρ(m 1 , m 2 ) P 1 (m 1 , m 2 )P 2 ≤ nP (10) for ρ(m 1 , m 2 ) confined in [-1, 1] through defining n i=1 x 2 1,i (m 1 , m 2 ) = nP 1 (m 1 , m 2 ), ∀m 1 , m 2 . (11) If we choose X n 1 (m 1 , m 2 ) in the null space of X n 2 (m 2 )
for each m 2 then we can assign a constant power P 1 (m 1 , m 2 ) = P -P 2 . Note that this is not orthogonal multiplexing but the effective dimensionality of the codebook X n 1 (m 1 , m 2 ) is n -1 for each m 2 . This model is considered for the κβ bound given in Section 3.The feasible set of permissible inputs F n is defined as

F n := {x n : x n 2 ≤ nP } ⊂ R n (12)
3 κβ bound-Achievability

The idea behind the κβ bound introduced in [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF] both for discrete and Gaussian channels is the optimality of the binary hypothesis testing problem and the Neyman-Pearson lemma.

Imagine the binary hypothesis test between the two possible distributions, for instance P and Q, a random variable W ∈ W can take on. A randomized test, denoted β a (P, Q) is set through the transformation P Z|W : W → {0, 1} where the test chooses the distribution Q and P for 0 and 1, respectively. As for the case of codewords with cost constraints where all of the codewords belong to the feasible set F ⊂ A, A being the input set, the corresponding measure of performance denoted

κ τ (F, Q Y ) for the hypothesis test is to choose between Q Y and {P Y |X=x } x∈F for 0 < τ < . As stated in [1, Theorem 25],
for a discrete P2P channel, there exists an (M, ) code with codewords chosen from the feasible set F that satisfies for any ∈ (0, 1)

M ≥ sup 0<τ < sup Q Y κ τ (F, Q Y ) sup x∈F β 1-+τ (x, Q Y ) ( 13
)
This bound is particularized to the Gaussian channel yielding

M * (n, , P ) ≥ κ n τ /β n 1-+τ (14)
where M * denotes the maximal code size and ∀x ∈ F,

β n 1-+τ (x, Q Y ) = β n 1-+τ .

Two -User Degraded Gaussian BC

In this part, we adapt the κβ bound given above by (14) to a two receiver degraded Gaussian BC. The degraded channel can be observed as two AWGN P2P channels since the channel between the transmitter and the weak receiver is the cascade of the channel from the transmitter to the strong receiver and the one from the strong receiver to the weak receiver. Note that this bounding technique does not constrain the distribution of the channel input to any particular distribution. The next theorem reminds the reader of the classical result from [START_REF] Cover | Broadcast channels[END_REF][START_REF] Bergmans | A simple converse for broadcast channels with additive white gaussian noise[END_REF] for the capacity region of the two-user Gaussian BC in the asymptotic regime.

Theorem 1 [START_REF] Cover | Broadcast channels[END_REF][START_REF] Bergmans | A simple converse for broadcast channels with additive white gaussian noise[END_REF]). The capacity region of the Gaussian BC is given as

R 1 ≤ C αP N 1 , R 2 ≤ C ᾱP αP + N 2 ( 15
)
where α is a constant confined in [0, 1] and ᾱ = 1 -α. The Shannon capacity C(.) is defined for SNR P as

C(P ) = 1 2 log(1 + P ) (16)
Using Theorem 1, we define the information densities of the Gaussian BC i(X n 2 ; Y n 2 ) and i(X n ; Y n 1 |X n 2 ) using [START_REF] Sato | An outer bound to the capacity region of broadcast channels[END_REF]. Expectation of these information densities bring out the two mutual information functions that compose the capacity region of the Gaussian BC given in Theorem 1. Note that unlike the asymptotic case, the error event that corresponds to decoding the cloud center using the observation of the strong user cannot be ignored as shown in ( 4)-( 5) with the corresponding error probability 21 . Therefore we also take i(X n 2 ; Y n 1 ) into account in our derivation.

Let us set P Y n j = N (0, σ 2 Yj I n ) with σ 2 Yj = P + N j for j = 1, 2. The mutual information random variable i(X n 2 ; Y n 2 ) under P Y n 2 is given as

G n2 = n 2 log σ 2 Y2 - nP 2 P 1 + N 2 log e 2 + 1 2 log e n i=1 (1 -σ 2 Y2 )S 2 i + 2 P 2 /(P 1 + N 2 )σ Y2 S i (17) where S i ∼ N (0, 1) for i = 1, • • • , n. Under the conditional distribution P Y n 2 |X n 2 the same function yields H n2 = n 2 log(σ 2 Y2 ) + nP 2 P 1 + N 2 log e 2σ 2 Y2 + log e 2σ 2 Y2 n i=1 1 -σ 2 Y2 S 2 i + 2 P 2 /(P 1 + N 2 )S i (18)
In a similar manner, the mutual information random variable

i(X n ; Y n 1 |X n 2 ) under P Y n 1 where Y n 1 = Y n 1 -X n 2 yields G n1 = n 2 log σ 2 Y 1 - nP 1 N 1 log e 2 + 1 2 log e n i=1 (1 -σ 2 Y 1 )S 2 i + 2 P 1 /N 1 σ Y 1 S i (19)
for σ 2 Y 1

= P 1 + N 1 since P 2 is subtracted off the sum power P . As for the conditional distribution P Y n 1 |X n 1 we get the information density as

H n1 = n 2 log(σ 2 Y 1 ) + P 1 N 1 log e 2σ 2 Y 1 + log e 2σ 2 Y 1 n i=1 1 -σ 2 Y 1 S 2 i + 2 P 1 /N 1 S i (20)
Lastly, we denote i(X n 2 ; Y n 1 ) by G n3 and H n3 under the distributions of P Y n 1 and P Y n 1 |X n 2 , respectively. We adapt [1, Theorem 40] to the setting of superposition coding for the degraded Gaussian BC and define β functions as follows 4) and with any positive γ k and k = 1, 2, 3. Theorem 2. For any k , n ≥ 1, τ k ∈ [0, 1], k = 1, 2, 3, and the chosen P Yj for j = 1, 2 with F n as defined by ( 12), the maximal code sizes denoted M * j of the j th user in a two receiver Gaussian degraded BC are bounded by

β a,k = Pr[G n k ≥ γ k ] (21) where Pr[H n k ≥ γ k ] = a k for a k = 1 -k as defined by (
M * 1 ≥ κ τ1,1 (F n , P Y n 1 ) β 1-1+τ1,1 (x, P Y n 1 ) (22)
M * 2 ≥ max κ τ2,2 (F n , P Y n 2 ) β 1-2+τ2 ,2 (x, P Y n 2 ) , κ τ3,3 (F n , P Y n 2 ) β 1-3+τ3,3 (x, P Y n 2 ) (23)
where

κ τ k ,k (F n , P Y n j ) = P 0,k p 1,k (r) p 0,k (r) ≥ ψ k with ψ k satis- fying P 1,k p 1,k (r) p 0,k (r) ≥ ψ k = τ k .
The probability distributions p 0,k (r) and p 1,k (r) are defined as

p 0,k (r) = 1 Γ(n/2)ω n/2 k r n/2-1 e r/ω k p 1,k (r) = 1 2 e (r+υ k )/2 ( r υ k ) n/4-1/2 I n/2-1 ( √ υ k r)
with the modified Bessel function of the first kind

I b (y) = (y/2) b ∞ j=0 (y 2 /4) l
l!Γ(b+l+1) and the following parameters for k = 1 ω 1 = 2(N 1 + P 1 ) and

υ 1 = nP1 N1 , for k = 2 ω 2 = 2(N 2 + P ) and υ 2 = nP2 P1+N2 whereas for k = 3 ω 3 = 2(N 1 + P ) with υ 3 = nP2
P1+N1 . Proof. Detailed proofs of the general case for a P2P-AWGN channel can be found in the original paper [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF]Theorems 25,40 and 42]. 21) is derived using the functions (17)-(20). As for evaluating κ τ k ,k 's the following definitions on P 0,k and P 1,k are set using superposition coding

β 1-k +τ k ,k (x, P Y n j ) for a = 1 -k + τ k given by (
P Y n 1 = P0,1 ∼ n i=1 (P1 + N1)S 2 i P Y n 2 = P0,2 ∼ n i=1 (P + N2)S 2 i P Y n 1 = P0,3 ∼ n i=1 (P + N1)S 2 i P Y n 1 |X n 1 = P1,1 ∼ n i=1 √ P1 + √ N1Si 2 P Y n 2 |X n 2 = P1,2 ∼ n i=1 √ P2 + (P1 + N2)Si 2 P Y n 1 |X n 2 = P1,3 ∼ n i=1 √ P2 + (P1 + N1)Si 2
for S i ∼ N (0, 1).

A Converse Bound

In [6, Theorem 2], it was shown using the classical results of Sato [START_REF] Sato | An outer bound to the capacity region of broadcast channels[END_REF] that in a physically degraded two-user BC the error probability of the system is upper bounded by the maximum of the two individual error probabilities per user and lower bounded by the error probability of the cooperative BC, which is equivalent to a P2P channel. Here, we have

2 max{ 1 , 2 } ≥ ≥ c ( 24
)
where 1 and 2 and c represent the first and second terms in (4) and the error probability of the cooperative BC, respectively.

[1, Theorem 41] presented a converse bound on the maximal code size of the P2P-AWGN channel. This bound is derived as a function of two random variables derived based on i(X n ; Y n c ) which is denoted by H n and G n under P (Y n c ) and P (Y n c |X n ), respectively. The corresponding functions for the cooperative channel are defined as

H n = n 2 log 2 (1 + P c ) + 1 2 P c log e 1 + P c n i=1 1 -S 2 i + 2S i √ P c , (25)
G n = n 2 log 2 (1 + P c )- P c log e 2 n i=1 1 + S 2 i -2 1 + S i P c (
(Pr[G n ≥ γ n ]) -1 given that Pr[H n ≥ γ n ] = 1 -is satisfied [1, Theorem 41].
We also define the functions H nc,j and G nc,j , respectively through (25) and ( 26) where P c is replaced by P/N j for j = 1, 2.

Theorem 3. For a Gaussian broadcast channel with two receivers with a power constraint as given by ( 8), the following inequalities on the maximal code sizes of user 1 and 2 denoted M * 1 and M * 2 , respectively hold for any n

M * 1 ≤ 1 Pr[G nc,1 ≥ γ c,1 ] (27)
M * 2 ≤ 1 Pr[G nc,2 ≥ γ c,2 ] (28)
M * 1 M * 2 ≤ 1 Pr[G n ≥ γ c ] (29)
where the positive thresholds in each inequality γ c,1 , γ c,2 and

γ c satisfy Pr[H nc,1 ≥ γ c,1 ] = 1 -1 , Pr[H nc,2 ≥ γ c,2 ] = 1 -2 , Pr[H n ≥ γ c ] = 1 -c respectively for 2 max{ 1 , 2 } ≥ c .
Proof. First two inequalities ( 27) and (28) corresponding respectively to user 1 and 2 are a direct application of the AWGN bound of [1, Theorem 41] using (25) and (26). For the third inequality (29) in order to apply the AWGN bound, we use the channel where the two receivers are allowed to cooperate with an error probability that cannot exceed the one of the broadcast channel as shown in [START_REF] Sato | An outer bound to the capacity region of broadcast channels[END_REF][START_REF] Weng | Error exponent regions for Gaussian broadcast and multiple-access channels[END_REF]. This last inequality corresponds to the cooperative channel with the product code sizes of the two users and the corresponding condition on γ c depends on the error probability satisfying (24).

Figure 1 shows the numerical comparison of the converse bound from Theorem 3 labeled as the outer bound with the asymptotic capacity region given by Theorem 1 and the superposition coding applied to the κβ bound where κ is derived through [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF]Lemma 43]. Sato's bounding technique yields a very loose bound since the converse is partially outside of the infinite blocklength capacity. The dotted line represents the time-sharing between two single-user achievable rates R j = 1 n log M j where M j is given by (14) as functions of P 1 and P 2 , respectively for user 1 and 2. A more fair comparison can be made by limiting time-sharing to within 1000 dimensions where n 1 +n 2 = 1000 and R j is (14) as a function of n j . In the case of an asymmetric channel, the advantage of superposition coding over orthogonal multiplexing with short blocklength is significant as in the asymptotic regime. 5 Acknowledgement

  26)with S i ∼ N (0, 1) and P c = P/N c where N c = min{N 1 , N 2 }. The maximal code size of the AWGN channel for any n and the average error probability is upper bounded by

Figure 1 :

 1 Figure 1: Numerical comparison of the obtained bounds for P = 100, = 10 -3 , N 1 = 1 and N 2 = 100.

This work has been partly supported by the INSA Lyon -SPIE ICS chair on the Internet of Things, by Orange Labs under Grant no F05151 and by the French National Research Agency project ARBURST.


Ayşe Ünsal
email: ayse.unsal@insa-lyon.fr

Jean-Marie Gorce
email: jean-marie.gorce@insa-lyon.fr

The Dispersion of Superposition Coding for Gaussian Broadcast Channels

In this paper, we analyze the performance of superposition coding for Gaussian broadcast channels with finite blocklength. To this end, we adapt two different achievability bounds, the dependence testing and the κβ bounds introduced by Polyanskiy et al. in 2010 to the broadcast setting. The distinction between these bounds lies in fixing either the input or the output distributions of the channel. For the first case of the dependence testing bound, an upper bound on the average error probability of the system is derived whereas for the latter, lower bounds on the maximal code sizes of each user are presented. 1

I. INTRODUCTION

It is well known that, superposition coding is optimum for degraded Gaussian broadcast channels (BC) in the asymptotic regime which is guaranteed by the vanishing error probability as the blocklength is allowed to grow boundlessly [START_REF] Bergmans | Random coding theorem for broadcast channels with degraded components[END_REF], [START_REF] Gallager | Capacity and coding for degraded broadcast channels[END_REF]. In general, classical information theory studies and analyzes fundamental limits of communication systems subject to interference and channel noise using coding schemes that require asymptotically large blocklengths. In this case, the channel coding rate is obtained through the expectation of the mutual information random variable or the information density (to be defined later) based on the input distribution. The information density is a theoretic notion, some measure, of the channel depending on the input signal and the channel noise.

There is a practical requirement for coding with finite blocklength to which the classical information theory results are no longer applicable. The loss in the channel capacity due to coding with finite blocklength is explained with a second order statistic of the information density, namely the channel dispersion term denoted V for a single user channel. In [START_REF] Strassen | Asymptotische Abschaetzungen in Shannon's Informationstheorie[END_REF], the author has shown that, the following equality holds for the single-user discrete-memoryless channels log M * (n, ) = nC -Q -1 ( )

√ nV + O(log n) (1)
where n, , M and C denote the blocklength, the error probability, the maximum code size and the channel capacity, respectively. In [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF], the above result is generalized to various point-to-point channel models including the AWGN channel where the channel dispersion term is defined as a function of the signal-to-noise ratio.

In [START_REF] Tan | On the dispersions of three network information theory problems[END_REF], the authors extended the use of the channel dispersion term to multi-user channels and studied three network information problems as the Slepian-Wolf problem, the multipleaccess (MAC) and asymmetric broadcast (ABC) for discrete channels only. In the multiuser settings of [START_REF] Tan | On the dispersions of three network information theory problems[END_REF] the scalar dispersion term V , is shown to be a positive semi-definite matrix and inner bounds for the (n, )-capacity regions of the discrete memoryless MAC and ABC are presented. In [START_REF] Molavianjazi | A second-order achievable rate region for Gaussian multi-access channels via a central limit theorem for functions[END_REF], maximum achievable rate regions are presented for the Gaussian MAC. The result of [START_REF] Molavianjazi | A second-order achievable rate region for Gaussian multi-access channels via a central limit theorem for functions[END_REF] depends only on the first and second order statistic of the relevant mutual information random variables represented by a scalar distribution where the authors firstly present the multi-access adaptation of the dependence testing bound by Polyanskiy et al. which constitutes the inspiration of the results presented in the first part of this paper.

In this paper, we consider a two-receiver degraded Gaussian broadcast channel (BC) in the setting of superposition coding with finite blocklength and we adapt the so-called dependence testing (DT) bound to the broadcast setting through random coding and threshold decoding to provide an upper bound on the average error probability of the system. To this end, we derive the channel dispersion terms for each error event that is defined through the information density functions based on the asymptotic capacity region. The overall bound consists of three different error events as the mis-detection, confusion and the input signals being confined to a pre-defined set. We derive the probability distributions of the channel dispersion terms for the mis-detection and confusion errors along with the corresponding parameters in order to derive the error probabilities. In addition, κβ achievability bounds based on a binary hypothesis test to choose between two possible output distributions are derived on the maximal code sizes of both users. Section II describes the channel model for the addressed problem that is followed by the broadcast adaptation of the DT bound in section III. Lastly, in Section IV we give a short reminder of the original κβ bound in an AWGN P2P channel which is followed by its generalization to a degraded Gaussian BC in the setting of superposition coding.

II. SYSTEM MODEL

We consider the following real-valued channel model

Y j,i = X i + Z j,i , (2)
for j = 1, 2 and i = 1, • • • , n where X i corresponds to the encoded messages that are m 1 ∈ [1, 2, • • • , M 1 ] and m 2 ∈ [1, 2, • • • , M 2 ]
, respectively subject to the channel noise terms Z 1,i ∼ N (0, N 1 ) and Z 2,i ∼ N (0, N 2 ) and the following channel transition probability density

P Y n j |X n (y n j |x n ) = (2πN j ) -n/2 e - y n j -x n 2 2N j . (3)
User j decodes message m j using the observation Y n j . We assume that the channel of user 2, the weaker user, has the larger of the two noise variances, i.e. N 2 > N 1 . For the achievable schemes considered here, the stronger user decodes the message m 2 prior to decoding its own message. We define the average error probability based on either user to be in error

= Pr [ m1 = m 1 ∪ m2 = m 2 ] (4)
which is further bounded by the union bound as follows

≤ 1 + 2 (5)
where j = Pr [ mj = m j ] with mj being the estimated m j on the corresponding user. The error probability in decoding message 1 is expanded as

1 = Pr { m2 = m 2 } Pr { m1 = m 1 }|{ m2 = m 2 } + Pr { m2 = m 2 } Pr { m1 = m 1 }|{ m2 = m 2 } (a)
≤ 11 + 21 [START_REF] Molavianjazi | A second-order achievable rate region for Gaussian multi-access channels via a central limit theorem for functions[END_REF] where m2 denotes the estimate of message 2 on user 1. In step (a),we denote 11 = Pr { m1 = m 1 }|{ m2 = m 2 } and 21 = Pr { m2 = m 2 } . This expansion is based on successive decoding.

We consider two different cases for this channel model depending on the bounding technique either fixing the input distribution as in the case of DT bound or with fixed output distribution as the κβ bound. These two cases are studied in the following subsections starting with the DT bound.

A. Random codebooks

This subsection presents the detailed model considered for the broadcast adaptation of the DT bound on the error probability. Here we have an input and two outputs with the n-letter channel model given as in [START_REF] Gallager | Capacity and coding for degraded broadcast channels[END_REF] where

X n = X n 1 + X n 2 (7)
with X n j ∼ N (0, P j I n ) for P 1 = αP and P 2 = ᾱP for α ∈ (0, 1) and ᾱ = 1 -α.

The decoding rule is set for the threshold decoding as

i(x n ; y n ) > γ (8)
where γ is some threshold and the information density or the mutual information random variable denoted i(.; .) is defined as

i(x n ; y n ) = log dP n |X n (y n |x n ) dP Y n (y n ) (9)
Here P (.|.) and P (.) respectively denote conditional and marginal distributions.

Definition II.1. An (n, M 1 , M 2 , , P ) code is composed of the messages m 1 ∈ [1, 2, • • • , M 1 ] and m 2 ∈ [1, 2, • • • , M 2 ]
encoded into n i.i.d. sequences X 1 and X 2 that are chosen randomly according to N (0, αP ) and N (0, ᾱP ), respectively with the following average power constraints

1 M 1 M1 i=1 E x 1,i 2 ≤ nαP, 1 M 2 M1 i=1 E x 2,i 2 ≤ nᾱP (10)
and the average probability of error defined by (4).

B. Peak power

For the broadcast adaptation of the κβ bound [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF], we assume codebooks constructed as in [START_REF] Cover | Broadcast channels[END_REF] subject to the power constraint defined as

x n (m 1 , m 2 ) 2 = n i=1 |x 1,i (m 1 , m 2 ) + x 2,i (m 2 )| 2 ≤ nP, (11
) ∀m 1 , m 2 where we assume equal power per codeword for the cloud center

X 2,i (m 2 ) for i = 1, • • • , n, m 2 = 1, • • • , M 2 and m 1 = 1, • • • , M 1 s.t. n i=1 |x 2,i (m 2 )| 2 = nP 2 , ∀m 2 . ( 12
)
For X 1,i (m 1 , m 2 ), we have

x n (m 1 , m 2 ) 2 = x 1 (m 1 , m 2 ) 2 + x 2 (m 2 ) 2 + 2 x 1 (m 1 , m 2 ), x 2 (m 2 ) (a) = nP 1 (m 1 , m 2 ) + nP 2 + 2nρ(m 1 , m 2 ) P 1 (m 1 , m 2 )P 2 ≤ nP (13) with ρ(m 1 , m 2 ) ∈ [-1, 1] through the following definition n i=1 x 2 1,i (m 1 , m 2 ) = nP 1 (m 1 , m 2 ), ∀m 1 , m 2 . ( 14
)
If we choose X n 1 (m 1 , m 2 ) in the null space of X n 2 (m 2 ) for each m 2 then we can assign a constant power P 1 (m 1 , m 2 ) = P -P 2 . Note that this is not orthogonal multiplexing but the effective dimensionality of the codebook

X n 1 (m 1 , m 2 ) is n - 1 for each m 2 .
This model is considered for the κβ bound covered in Section IV. The feasible set of permissible inputs F n is defined as

F n := {x n : x n 2 ≤ nP } ⊂ R n (15)

III. DEPENDENCE TESTING BOUND -SUPERPOSITION CODING AND THRESHOLD DECODING

The dependence testing bound on the error probability of a P2P channel presented in [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF]Theorem 20] is adapted to the model defined in Section II-A for a two-receiver Gaussian BC. The next theorem reminds the reader of the classical result by [START_REF] Bergmans | Random coding theorem for broadcast channels with degraded components[END_REF], [START_REF] Gallager | Capacity and coding for degraded broadcast channels[END_REF], [START_REF] Cover | Broadcast channels[END_REF] for this channel in the asymptotic regime.

Theorem III.1. The capacity region of the Gaussian BC is given as

R 1 ≤ C αP N 1 , R 2 ≤ C ᾱP αP + N 2 ( 16
)
where α is a constant confined in [0, 1] and ᾱ = 1 -α. The Shannon capacity C(.) is defined for a signal-to-noise ratio of P as C(P ) = 1 2 log(1 + P ). The aim of this part is to provide a finite blocklength adaptation of this result and to introduce an achievability bound on the system error probability. We state our first result with the following theorem which provides the broadcast adaptation of [4, Theorem 20] using the mutual information functions in (16) achieving the capacity region of Theorem III.1. The average error probability defined in (4) with ( 6) is upper bounded based on the decoding rule (8).

Theorem III.2. An (n, M 1 , M 2 , , P ) code exists for the channel as described in Definition II.1 with the average error probability satisfying

≤ Pr [i(X n 2 ; Y n 2 ) < γ 2 ] + η 2 Pr i(X n 2 ; Ȳ n 2 ) > γ 2 (17) + Pr [i(X n ; Y n 1 |X n 2 ) < γ 1 ] + η 1 Pr i(X n ; Ȳ n 1 |X n 2 ) > γ 1 (18) + Pr [i(X n 2 ; Y n 1 ) < γ 2 ] + η 2 Pr i(X n 2 ; Ȳ n 1 ) > γ 2 (19) + Pr[X n / ∈ F ] ( 20
)
where Ȳ n j follows the same distribution as the output signal Y n j but is independent of the input X n , the thresholds are set as γ j = log η j and η j = (M j -1)/2 for j = 1, 2 and F denotes the set of permissible inputs.

Proof. The capacity region of the two-receiver Gaussian BC given by Theorem III.1 is achieved through the information densities

i(X n ; Y n 1 |X n 2 ) and i(X n 2 ; Y n 2 )
for user 1 and 2, respectively. i(X n ; Y n 1 |X n 2 ) and i(X n 2 ; Y n 2 ) are defined using (9). Expectation of these information densities bring out the mutual information functions that compose the asymptotic capacity region in Theorem III.1. Unlike the asymptotic case, the error event for decoding message 2 using the observation of the strong user Y n 1 cannot be ignored with the corresponding error probability 21 as shown by [START_REF] Molavianjazi | A second-order achievable rate region for Gaussian multi-access channels via a central limit theorem for functions[END_REF]. Applying the threshold decoding rule defined by (8) to these three functions, we obtain

i(X n 2 ; Y n 2 ) > γ 2 , (21) i(X n ; Y n 1 |X n 2 ) > γ 1 , (22) i(X n 2 ; Y n 1 ) > γ 2 . ( 23
)
Combining the dependence testing bound proposed in [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF]Theorem 20] with (21), ( 22) and ( 23) yields ( 17), ( 18) and ( 19), respectively. The proposed bound consists of three types of errors. The first case of mis-detection, which is shown by the first terms in ( 17)-( 19), corresponds to the information density of a correct pair of input-output to remain below the threshold. In the second case, the confusion error, shown by the second terms in ( 17)-( 19), occurs when a pair exceeds the threshold where the output does not depend on the input signal that was transmitted. The probabilities (17), ( 18) and ( 19) are

2 = Pr [ mj = m j ], 11 = Pr { m1 = m 1 }|{ m2 = m 2 } and 21 = Pr { m2 = m 2 }
, respectively. Lastly, due to the input signal defined by ( 7), we have Pr[X n / ∈ F ] given by (20) as the last error event of the proposed bound that represents the probability of the channel input X n not being chosen from the feasible set denoted F .

Hereafter, starting with decoding message 2 on the weaker user, we evaluate the probabilities of each error event considered in the proposed bound in detail.

1) Decoding m 2 : This scheme uses successive decoding where initially message 2 is decoded using the observation of Y n 2 . This event is represented by the information density i(X n 2 ; Y n 2 ). The terms in the first line of Theorem III.2 are evaluated in the following starting with the mis-detection error event i(X n 2 ; Y n 2 ) < γ 2 . We derive i(X n 2 ; Y n 2 ) as

1 n i(X n 2 ; Y n 2 ) = 1 n log P Y n 2 |X n 2 (Y n 2 |X n 2 ) P Y n 2 (Y n 2 ) = 1 n log (2π) -n/2 (αP + N 2 ) -n/2 e - Y n 2 -X n 2 2 2(αP +N 2 ) (2π) -n/2 (P + N 2 ) -n/2 e - Y n 2 2 2(P +N 2 ) = 1 n log P + N 2 αP + N 2 n/2 e Y n 2 2
2(P +N 2 ) - Y n 2 -X n 2 2 2(αP +N 2 ) = C ᾱP αP + N 2 + 1 n log e Y n 2 2 2(P + N 2 ) - Y n 2 -X n 2 2 2(αP + N 2 ) (24)
Let us denote the additional term to the Shannon capacity C ᾱP αP +N2 by v 22 . (24) is rewritten as

1 n i(X n 2 ; Y n 2 ) = C ( ᾱP/(αP + N 2 )) + v 22 (25)
As for v 22 , we get

v 22 (a) = 1 n log e f 1 X n 1 + X n 2 + Z n 2 2 + f 2 X n 1 + Z n 2 2 (b) = 1 n log e f 1 X n 2 + Zn 2 2 + f 2 Zn 2 2 = 1 n log e f 1 X n 2 2 + (f 1 + f 2 ) Zn 2 2 + 2f 1 X n 2 , Zn 2 = 1 n log e n i=1 X 2,i Z2,i A X 2,i Z2,i T (c) = 1 n log e n i=1 [µ 1,i µ 2,i ] P 2 AP 2 [µ 1,i µ 2,i ] T (26)
In step (a) we substituted

f 1 = [2(P + N 2 )] -1 , f 2 = -[2(αP + N 2 )] -1 , in step (b) we defined Zn 2 = X n 1 + Z n
2 and in step (c), the standard Gaussian random variables µ 1,i , µ 2,i are introduced where A and P 2 are 2 × 2 matrices given by

A = f 1 f 1 f 1 f 1 + f 2 , ( 27
)
and

P 2 = diag √ ᾱP , √ αP + √ N 2 .
The eigenvalues of the matrix product

A = P 2 AP 2 yield λ 1 = √ ᾱP 2 √ (P +N2) , λ 2 = -λ 1 .
Rewriting A through its eigen decomposition UΛU T where Λ is a diagonal matrix with the eigenvalues on the diagonal elements and U is the corresponding eigenvector, we define [μ 21,i , μ2 2,i ] T which is the product U T [µ 1,i , µ 2,i ] T . Using λ 1 and λ 2 , the dispersion term v 22 yields

v 22 = 1 n log e × λ 1 n i=1 (μ 2 1,i -μ2 2,i ). (28)
The weighted difference of chi-squares with n degrees of freedom follows the variance-gamma distribution 2 with the location parameter m and asymmetry parameter denoted by b are both 0 and δ = θ = P +N2 ᾱP . Substituting v 22 into (25), the probability of mis-detection error in decoding m 2 on user 2 yields

Pr [i(X n 2 ; Y n 2 ) < γ 2 ] = Pr   v 22 < γ 2 -nC ᾱP αP +N2 log e   (29)
The confusion error event represents the case where the information density exceeds the threshold according to the decoding rule (8) where the channel output does not depend on the input signal that is transmitted over the channel. More precisely, for a codeword C n k from a given codebook

(C n 0 , C n 1 , • • • , C n Mj -1
) for user j, the confusion error event represents the information density of interest to exceed the threshold with C n l given that the input is C n k for all l < k. In decoding m 2 , we have for the confusion error event

1 n i(X n 2 ; Ȳ n 2 ) = 1 n log P Y n 2 |X n 2 =C n k (Y n 2 |X n 2 = C n k ) P Y n 2 (Y n 2 ) = 1 n log (2π) -n/2 (2(αP + N 2 )) -n/2 e - Y n 2 -C n l 2 2(αP +N 2 ) (2π) -n/2 (2(P + N 2 )) -n/2 e - Y n 2 2 2(P +N 2 ) = C ᾱP (αP + N 2 ) + v c,2 . ( 30
)
The additional term v c,2 is further derived as

v c,2 = 1 n log e g 1 C n k + Zn 2 2 + g 2 C n k -C n l + Zn 2 2 = 1 n log e n i=1 [C k,i C l,i Z2,i ]A c [C k,i C l,i Z2,i ] T = 1 n log e n i=1 [µ 1,i µ 2,i µ 3,i ]P c2 A c P c2 [µ 1,i µ 2,i µ 3,i ] T
where

g 1 = [2(P + N 2 )] -1 and g 2 = -[2(αP + N 2 )] -1 with P c2 = diag( √ ᾱP , √ ᾱP , √ αP + √ N 2 ) A c =   (g 1 + g 2 ) -g 2 (g 1 + g 2 ) -g 2 g 2 -g 2 (g 1 + g 2 ) -g 2 (g 1 + g 2 )   ( 31
)
and µ j,i ∼ N (0, 1) for j = 1, • • • , 4. We remind the reader that Zn

2 = X n 1 + Z n 2 .
The non-zero eigenvalues of the matrix product

P c2 A c P c2 are λ c1 = -ᾱP + √ ᾱP (P +N2) 2(αP +N2)
and

λ c2 = -ᾱP + √ ᾱP (P +N2) 2(αP +N2)
. The dispersion term v c,2 is obtained in the following form which constitutes a weighted sum of chisquared variables with n degrees of freedom, a special case of the gamma distribution.

v c,2 = 1 n log e n i=1 [λ c1 µ 2 1,i + λ c2 µ 2 2,i ] (32)
The confusion error probability for decoding m 2 on user 2 is

Pr i(X n 2 ; Ȳ n 2 ) > γ 2 = Pr   v c,2 > γ 2 -nC ᾱP αP +N2 log e   (33)
Let us denote the threshold functions in the right hand sides (r.h.s.) of ( 29) and (33) by ζ 2 . Combining (29) and (33), we obtain the total error probability in decoding message 2 given by (17), which in fact is

2 = Pr [ m2 = m 2 ]. 2 = Pr [v 22 < ζ 2 ] + η 2 Pr [v c,2 > ζ 2 ] (34)
2) Decoding m 1 : In order to reconstruct m 1 , in the setting of superposition coding, the strong user that is subject to a channel with a smaller noise variance, firstly decodes m 2 with i(X n 2 ; Y n 1 ). Note that in the asymptotic case, the error probability for this event is insignificant. In a similar fashion to i(X n 2 ; Y n 2 ), we have for i(X n 2 ;

Y n 1 ) 1 n i(X n 2 ; Y n 1 ) = C ᾱP αP + N 1 + v 21 (35)
where v 21 follows a variance-gamma distribution with n degrees of freedom, m = b = 0 and δ = θ = P +N1 αP . Substituting v 21 into (35), the probability of mis-detection error in decoding m 2 on user 1 yields

Pr [i(X n 2 ; Y n 1 ) < γ 2 ] = Pr [v 21 < ζ 21 ] (36)
with

ζ 21 = γ2-nC ᾱP αP +N 1 log e
. As for the confusion error probability of decoding message 2 on the stronger user, we have Pr i(X n

2 ; Ȳ n 1 ) > γ 2 = Pr [v c,21 > ζ 21 ] (37)
where

v c,21 = 1 n log e n i=1 [λ c5 µ 2 1,i + λ c6 µ 2 2,i ] for µ 2 1,i and µ 2
2,i being chi-squared variables with n degrees of freedom,

λ c5 = -ᾱP + √ ᾱP (P +N1) 2(αP +N1)
and

λ c6 = -ᾱP + √ ᾱP (P +N1) 2(αP +N1)
. The total error probability in decoding m 2 on the first user given by ( 19) becomes

21 = Pr [v 21 < ζ 21 ] + η 2 Pr [v c,21 > ζ 21 ] (38)
which is equivalent to 21 = Pr m2 = m 2 . The derivation follows the same way as in (30). Therefore it is omitted due to space limitations. For the stronger user to decode its intended message m 1 using the observation of Y n 1 given the information of X n 2 , we derive the relevant information density to evaluate the probability of mis-detecting m 1 as

1 n i(X n ; Y n 1 |X n 2 ) = 1 n log P Y n 1 |X n 1 ,X n 2 (Y n 1 |X n 1 , X n 2 ) P Y n 1 |X n 2 (Y n 1 |X n 2 ) = C (αP/N 1 ) + v 11 (39)
The additional term v 11 yields

v 11 = 1 n log e f 3 X n 1 + Z n 1 2 + f 4 Z n 1 2 = 1 n log e n i=1 [X 1,i Z 1,i ] B [X 1,i Z 1,i ] T (d) = 1 n log e n i=1 [µ 1,i µ 4,i ] P 1 BP 1 [µ 1,i µ 4,i ] T (40)
for f 3 = 1 2(αP +N1) and f 4 = -1 2N1 and in step (d) we define the standard Gaussian random variables µ 1,i , µ 4,i with 2 × 2 matrices B and P 1 given by

B = f 3 f 3 f 3 f 3 + f 4 , (41)
and αP . In the evaluation of the achievability bound proposed in Theorem III.2 in order to derive the confusion error probability in detecting m 1 , we have

P 1 = diag √ αP , √ N 1 .
1 n i(X n ; Ȳ n 1 |X n 2 ) = C (αP/N 1 ) + v c,1 (43)
The dispersion term v c,1 is obtained in the form of

1 n log e n i=1 [λ c3 μ2 1,i + λ c4 μ2 2,i ] with λ c3 = - αP + √ αP (αP +N1) 2N1
and

λ c4 = -αP + √ αP (αP +N1) 2N1
. Finally, summing up the probabilities of mis-detection and confusion for user 1 to detect its intended message m 1 , we obtain

11 = Pr [v 11 < ζ 11 ] + η 1 Pr [v c,1 > ζ 11 ] . (44)
for

ζ 11 = γ1-nC αP N 1 log e
. Given the power constraint (10), the probability of the input being confined to the set F n yields Pr{X n / ∈ F n } = 0. In summary, combining 2 , 21 and 11 respectively given by (34), ( 38) and ( 44), the derivation of the achievability bound of Theorem III.2 is complete.

IV. κβ BOUND-ACHIEVABILITY

The idea behind the κβ bound is the optimality of the binary hypothesis testing problem and the Neyman-Pearson lemma. In this part, we adapt the κβ bound proposed in [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF]Theorem 41] to the Gaussian BC. The degraded channel can be considered as two AWGN P2P channels since the channel between the transmitter and the weak receiver is the cascade of the channel from the transmitter to the strong receiver and the one from the strong receiver to the weak receiver. The input distribution is no longer limited to the Gaussian distribution. To apply superposition coding and obtain the two-user equivalent of the κβ bound, we consider the mutual information functions from Section III.

Let P Y n j denote N (0, σ 2 Yj I n ) with σ 2 Yj = P + N j for j = 1, 2. Using the definition of (9), i(X n 2 ; Y n 2 ) under P Y n 2 is given as

G n2 = n 2 log σ 2 Y2 - nP 2 P 1 + N 2 log e 2 + 1 2 log e n i=1 (1 -σ 2 Y2 )S 2 i + 2 P 2 /(P 1 + N 2 )σ Y2 S i (45)
where S i ∼ N (0, 1)

for i = 1, • • • , n. Under the conditional distribution P Y n 2 |X n
2 the same function yields

H n2 = n 2 log(σ 2 Y2 ) + nP 2 P 1 + N 2 log e 2σ 2 Y2 + log e 2σ 2 Y2 n i=1 1 -σ 2 Y2 S 2 i + 2 P 2 /(P 1 + N 2 )S i (46)
In a similar manner, the mutual information random variable

i(X n ; Y n 1 |X n 2 ) under P Y n 1 becomes G n1 = n 2 log σ 2 Y 1 - nP 1 N 1 log e 2 + 1 2 log e n i=1 (1 -σ 2 Y 1 )S 2 i + 2 P 1 /N 1 σ Y 1 S i (47)
where we define

Y n 1 = Y n 1 -X n 2 with σ 2 Y 1 = P 1 + N 1 since P 2 is
subtracted off the sum power P . Under the conditional distribution P Y n 1 |X n 1 we obtain the information density as

H n1 = n 2 log(σ 2 Y 1 ) + P 1 N 1 log e 2σ 2 Y 1 + log e 2σ 2 Y 1 n i=1 1 -σ 2 Y 1 S 2 i + 2 P 1 /N 1 S i (48)
Lastly, i(X n 2 ; Y n 1 ) is respectively denoted by G n3 and H n3 under P Y n 1 and P Y n 1 |X n 2 , which will not be given here explicitly. Using Theorem 40 of [START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF] for the degraded Gaussian BC, we define β functions as follows

β a,k = Pr[G n k ≥ γ k ] (49)
where Pr[H n k ≥ γ k ] = a k for a k = 1k as defined by (4) and with any positive γ k and k = 1, 2, 3. The resulting achievability bound for the Gaussian BC is stated in the next theorem.

Theorem IV. V. DISCUSSION We introduced the dependence testing and the κ -β bounds for the two-receiver Gaussian BC. Both types of bounds can be easily extended to scenarios with k-users for k ≥ 2. It is clear that unlike the well-known optimality of superposition coding for Gaussian BC, k user adaptation of the proposed bounds in Theorems III.2 and IV.1 would perform poorly due to the additional error event using the successive cancellation.

P 1 BP 1 are λ 4 = 1 2 αP αP +N1 and λ 5 = -1 2 λ 4 =

 1224 The eigenvalues of B = αP αP +N1 . Finally we obtain the channel dispersion term v 11 in the following form -λ 5 and μl,i 's for l = 1, 4 are obtained through substitution of the eigen decomposition of B . v 11 follows the variance gamma distribution with n degrees of freedom, m = b = 0 and δ = θ = αP +N1

p(P 1 +P 1 + N 1 S i 2 PP 2 + (P 1 + N 2 )S i 2 PP 2 + (P 1 +

 112212221 0,k (r) ≥ ψ k = τ k . The probability distributions p 0,k (r) and p 1,k (r) are defined as p 0,k (r2-1 e r/ω k andp 1,k (r) = 1 2 e (r+υ k )/2 ( r υ k ) n/4-1/2 I n/2-1 ( √ υ k r)with the modified Bessel function of the first kindI b (y) = (y/2) b ∞ j=0 (y 2 /4) ll!Γ(b+l+1) and the following parametersfor k = 1, ω 1 = 2(N 1 + P 1 ) and υ 1 = nP1 N1 , for k = 2, ω 2 = 2(N 2 + P ) and υ 2 = nP2P1+N2 whereas for k = 3, ω 3 = 2(N 1 + P ) with υ 3 = nP2 P1+N1 . Proof. Detailed proofs of the general case for a P2P-AWGN channel can be found in the original paper[START_REF] Polyanskiy | Channel coding rate in the finite blocklength regime[END_REF] Theorems 25, 40 and 42].β 1-k +τ k ,k (x, P Y n j ) for a = 1k + τ kgiven by (49) is derived using the functions (45)-(48). As for evaluating κ τ k ,k 's the following definitions on the distribution of the output signals P 0,k and the distribution of the output given the input P 1,k are set using superposition coding as followsP 0,1 ∼ n i=1 N 1 )S 2 i , P 1,1 ∼ n i=1 N 1 )S i2

  (F n , P Y n 1 ) β 1-1+τ1,1 (x, P Y n 1 ) (F n , P Y n 2 ) β 1-2+τ2,2 (x, P Y n 2 ) , κ τ3,3 (F n , P Y n 2 ) β 1-3+τ3,3 (x, P Y n

	M * 1 ≥	κ τ1,1 (50)
	M * 2 ≥ max	κ τ2,2 2 )
						(51)
	where	κ τ k ,k (F n , P Y n j ) = P 0,k	p 1,k (r) p 0,k (r)	≥ ψ k	(52)
	with ψ k satisfying P 1,k	p 1,k (r)

1. For any k , n ≥ 1, τ k ∈ [0, 1], k = 1, 2, 3,

and the chosen P Yj for j = 1, 2 with F n as defined by (15), the maximal code sizes denoted M * j of the j th user in a two receiver Gaussian degraded BC are bounded by

This work was supported by Orange Labs under Grant no:F05151 and by the French National Research Agency project ARBURST.

The variance-gamma distribution with λ > 0 degrees of freedom, the real-valued location parameter m and the asymmetry parameter b, is defined asf (t) = θ 2λ |t -m| λ-1/2 K λ-1/2 (δ|t -m|) √ πΓ(λ)(2δ) λ-1/2 e b(t-m) , -∞ < t < ∞where K λ and Γ denote the modified Bessel function of the second kind and the gamma function, respectively for real δ, θ = √ δ 2 -b 2 > 0.