Tristan Guillaume
email: tristan.guillaume@u-cergy.fr

ANALYTICAL VALUATION OF OPTIONS ON JOINT MINIMA AND MAXIMA

Keywords: option, barrier, step barrier, pricing, dimension

In this paper, we show how to obtain explicit formulae for a variety of popular pathdependent contracts with complex payoffs involving joint distributions of several extrema. More specifically, we give formulae for standard step-up and step-down barrier options, as well as partial and outside step-up and step-down barrier options, involving multiple integrals of dimensions ranging between three and five. Our method can be extended to other exotic pathdependent payoffs as well as to higher dimensions. Numerical results show that the quasi random integration of these formulae involving multivariate distributions of correlated Gaussian random variables provides option values more quickly and more accurately than Monte Carlo simulation.

Introduction

Barrier options are one of the oldest types of options. They are also one of the most popular, due to their low cost and their strong leverage effect, as well as to the precision and the flexibility with which they can adapt to investors' needs or views about the market. As a result, barrier options are now heavily traded, particularly in the foreign exchange markets. They are also embedded in a lot of popular structured derivatives in equity and interest rate markets.

There has been quite extensive research dealing with the analytical pricing of barrier options. A closed form formula for a down-and-out European call option was published by Merton as early as 1973 [START_REF] Levy | Processus Stochastiques et Mouvement Brownien[END_REF]. An exhaustive list of formulae for standard barrier options was published by [START_REF] Rich | The mathematical foundations of barrier option-pricing theory[END_REF]. In the mid-90's, contributions started to focus on more exotic types of barrier options, such as partial barrier options [START_REF] Heynen | Partial barrier options[END_REF][START_REF] Carr | Two extensions to barrier option valuation[END_REF], outside barrier options [START_REF] Bermin | Time and path dependent options : the case of time dependent inside and outside barrier options[END_REF], double barrier options [START_REF] Kunitomo | Pricing options with curved boundaries[END_REF]Bhagavatula and Carr, 1995 ;[START_REF] Geman | Pricing and hedging double barrier option : a probabilistic approach[END_REF]. [START_REF] Heynen | Partial barrier options[END_REF] derive formulae for partial barrier options in a partial-differential-equation framework. [START_REF] Carr | Two extensions to barrier option valuation[END_REF] includes American-type rebates. [START_REF] Bermin | Time and path dependent options : the case of time dependent inside and outside barrier options[END_REF] develops a decorrelation approach to reduce the dimension of the partial outside barrier option pricing problem. [START_REF] Kunitomo | Pricing options with curved boundaries[END_REF] draw on Levy's seminal works (1948) to provide a formula for a double barrier option with curved boundaries. Bhagavatula and Carr (1995) deal with double barrier options by means of Fourier series, whereas [START_REF] Geman | Pricing and hedging double barrier option : a probabilistic approach[END_REF] apply Laplace transformation.

So far, there are no available formulae for a special type of barrier option that attracts strong interest among practitioners : step barrier options. These contracts feature sequences of constant one-sided barriers. They are called step barrier options, because barriers are step functions of time. When barriers are monotonically decreasing or increasing, we have a standard step barrier option. There can be gaps during which there is no barrier monitoring. In this case, the step barrier option is said to be partial. When the asset involved in the payoff is not the same as the one involved in barrier monitoring, we have an outside step barrier option. The main difficulty associated with an analytical valuation of such contracts, in a risk-neutral framework, is that they involve joint distributions of extrema over various time intervals that are currently not explicitly known. Furthermore, the dimension of the pricing problem quickly increases.

Consequently, it is assumed that these contracts have to be numerically priced. When the dimension of the problem is greater than three, Monte Carlo simulation is thought to be the only tractable method, as its convergence rate is independent of dimension, contrary to a grid-based approach.

The purpose of this paper is to show that this valuation problem can be analytically solved, by providing explicit formulae for all kinds of step barrier options, whether they are standard, nonstandard, partial or outside contracts, in dimensions that range between three and five, knowing that the method we use can be applied to higher dimensions (sections 1, 2, 3). Then, by using simple low discrepancy sequences to perform quasi random integration, this paper aims at showing that the numerical implementation of these exact formulae is both more efficient and more accurate than alternative advanced or plain Monte Carlo simulation methods (section 4).

Analytical framework

It is assumed that the underlying asset follows a geometric brownian motion :

t t t t dS S dt S dW m s   (1)
The parameters m and s are constant, and s is positive. The option life starts at time 0 and that its expiry is T. t

W is Brownian motion defined on a probability space   , ,

t F P  , where   , t s F W s t s   is the natural filtration of t W .
According to the risk-neutral valuation approach, at the contract inception 0 t  , the noarbitrage value of a European call option with path-dependent conditions 1 2 , ,..

., m A A

A is given by the discounted expectation of its payoff under the equivalent martingale measure, conditional on the information available at time 0 t  : ,,,,, ,...,

      1 1 0 ,...,
m rT Q m T A A e C S T K r A A E S K S 1 s d           (2)
where K is the strike price, r is the riskless rate, d is a dividend rate, Q E is the expectation operator under the equivalent martingale measure, Q , and   . 1 is the indicator function taking value 1 if the conditions inside the brackets are met and value zero otherwise.

Equivalently, we have : ,,,,, ,...,

      1 1 0 ,..., ,
m rT Q m T A A K e C S T K r A A E S K S T S 1 s d               2 1 1 2 0 ,..., , ,..., , T m m r T W Q Q A A K A A K E S e KE T T S S 1 1 s d s                                                2 1 1 2 ,..., , ,..., , T m m T W Q Q A A K A A K FE e KE T T S S 1 1 s s                         (3)
where

  0 r T F S e d  
is the risk-neutral forward price.

Let us define a new measure Q  such that :

2 2 T T T W F dQ e dQ s s     (4)
Then, according to Girsanov theorem, we have :

      1 1 1
, , , , , ,..., . ,..., , . ,..., ,

rT m m T m T e C S T K r A A F Q A A X k K Q A A X k s d      (5) with :     0 0 ln / , ln / T T X S S k K S  
Similarly, we have the following expression for a path-dependent put option :

      1 1 1
, , , , ,..., . ,..., , . ,..., ,

rT m m T m T e P S T K r A A K Q A A X k F Q A A X k s d        Hence, it suffices to calculate probabilities under the Q  measure : a simple change of drift from 2 / 2 r m d s    to 2 / 2 r m d s     will provide the corresponding probabilities under the Q   measure.
In general, the greater the number of path dependent conditions, the higher the dimension of the solution will be.

Low-dimensional problems can be solved in terms of univariate or bivariate standard Gaussian distribution functions,   N a and  

, ;

N a b r respectively. This is the case for standard barrier and lookback options, as well as for partial or outside barrier options. If we want to find closed form formulae for more complex path-dependent options, we need to use higher-dimensional Gaussian distributions.

In general, if

  1 ,..., n X X X 
is a vector of n joint standardized Gaussian random variables with a symmetric, positive-definite  

n n  matrix of variances and covariances  , then the density of X is given by :

      1 2 1 / 2 ,..., 2 T X X n n e f x x Det p      (6)
where T X is the transpose of X ,

 

Det  is the determinant of  and 1   is the inverse of  .

For example, if we denote by 12 23 ,   and 13 r the correlation coefficients between three standardized Gaussian random variables 1 2 , X X and 3 X , it is easily shown, by applying formula (6), that the joint density of 1 2 , X X and 3 X is given by :

      2 2 2 1 2 3 4 5
l l l l l l r p           (7)
with :

        2 2 2 23 13 13 23 12 12 1 2 3 4 1 1 1 Det Det Det Det r r r r l l l l                     13 12 23 12 23 13 5 6 Det Det r r l l             (8) and   Det   2 2 2 12 23 13 12 23 13 1 2 r r r        (9)
However, using these general multinormal expressions becomes analytically cumbersome and computationally inefficient as the dimension of the integral rises. Actually, simplified expressions can be used when dealing with the finite-dimensional distributions of geometric T be three different dates during the option life   0 3 , T T , such that :

0 1 2 3 T T T T    .
By using the Markov property of Brownian motion, as well as the independence of Brownian increments, one can write :

  1 2 3 , , T T T Q X a X b X c    =                                                                                             (10)
where 12

1 2 / T T   and   . N is the univariate standard Gaussian distribution.
Manipulating this triple integral and standardizing it yields :

  1 2 3 , , T T T Q X a X b X c                  e dzdydx m m m s s s r r p r r                  (11)
which can be written in a more compact form as : .

3 1 2 3 12 23 1 2 3                                         2 2 2 2 12 23 34 3 1 2 4 2 2 2 3 1 2 4 12 23 34 - 2 2 1 2 1 2 1 2 2 2 2 12 23 34 2 1 1 1 x w y x z y c T w a T b T d T T T T T e dzdydxdw m m m m s s s s r r r p r r r                          (
              1 2 2 2 2 2 2 1,2 1 1,2 1 2 2 , 1 1 , 1 2 1 2 1 1 arccos 2 arccos 2 2 , 1 , ,..., exp 2 arcsin exp d d k k k k k k T T T d x x x x x x k k P X dx X dx X dx r r r r p r                                                                                                      1 2 d k        (
Alternatively, the finite-dimensional distribution of order d of arithmetic Brownian motion with drift m and volatility s , is given by :

  1 2 1 2 , ,..., d T T T d Q X x X x X x    1 1 2 2 12 23 1, 1 2 , ,..., , ,..., d d d d d d x T x T x T N T T T m m m r s s s                             2 2 1 1 , 1 1 1 1 2 2 2 1 1 2 , 1 2 2 1 1 1 /2 2 2 2 12 23 1, ... ... 2 1 1 ... 1 d k k k k d d k d k k y y x T y x T x T T T T d d d d d
e dy dy dy

   m m m s s s r p r r r                          (15)
We will now show, in sections 2 and 3 of this paper, how to use these finite-dimensional distributions to value step barrier options.

Standard step-up and step-down barrier options

The Let us focus on an up-and-out put option with four different barriers over four intervals of the

option life :         0 1 1 2 2 3 3 4
, , , , , , ,

T T T T T T T T

, where 0 T is the beginning of the option life and 4 T is the expiry. We name our four barriers : H and that the value of the underlying asset at expiry 4 S will be lower than the strike price K . That is, we need to know the value of :

  1 2 3 4 0 1 1 2 2 3 3 4 4 , , , , Q M h M h M h M h X k      (16)
where

    0 0 ln / , ln / , T T X S S k K S     0 ln / i i h H S  and     , sup a b b a t t T T M X  
Graph 1, in appendix 1, gives an illustration of this problem.

The formula for :  

1 1 0 1 , T Q M h X k  
is a classical result that is assumed to be known (see,e.g., [START_REF] Karatzas | Brownian motion and stochastic calculus[END_REF]).

Using the Markov property of brownian motion and the independence of brownian increments, the second maximum can be dealt with in the following way :

  2 1 2 0 1 1 2 , , T Q M h M h X k    =         1 1 2 1 1 0 1 1 2 1 2 , , T T h Q Q T X h M h X k M h E E X u u du 1 1                          (17)
where :

          2 2 1 1 1 1 1 1 2 2 2 1 1 2 2 2 2 1 1 2 2 1 2 2 1 2 1 2 1 2 2 2 u T u h T T T h h u e e u e T T k u T T k h u T T u N e N T T T T m m m s s s m s s p s p m m s s                                                                        (18)
Using identities (A.1), (A.2) and (B.1) in appendix 3, the following solution can be obtained :

  2 2 1 2 1 2 2 2 1 1 2 1 1 2 2 2 12 2 12 1 2 1 2 2 2 1 1 1 2 1 1 2 1 2 2 12 2 12 1 2 1 2 2 , , 2 2 2 , , h h h h h T k T h T k h T N e N T T T T h T k h T h T k h h T e N e N T T T T m s m m s s m m m m s s s s m m m m s s s s                                                               (19)
where 12

1 2 / T T  
as in section 2. The next step is to find :

  3 1 2 3 0 1 1 2 2 3 , , , T Q M h M h M h X k   
 . This probability can be formulated as the following conditional expectation :

    1 2 3 2 0 1 1 2 2 3 2 3 2 , , , T T Q Q X h M h M h X k M h E E X 1 1                      (20)
Building on our acquired knowledge of  

2 1 2 0 1 1 2 , , T Q M h M h X k  
 , the following integral form of the problem can be written down :

    1 2 3 2 0 1 1 2 2 3 2 3 2 , , , T T Q Q X h M h M h X k M h E E X 1 1                                         1 2 1 2 2 2 1 2 1 2 1 2 1 2 2 2 1 2 2 2 3 4
; ;

; + h h h h h h h h h

h h h u v v dvdu e u v v dvdu e u v v dvdu e u v v dvdu         m s m m s s                               (21)
where :

        3 2 2 3 2 3 3 2 3 2 3 2 2 h v k v T T k h v T T v N e N T T T T m s m m s s                                  (22)         2 2 2 2 2 1 2 2 1 1 1 1 2 1 1 2 1 2 1 1 2 2 1 2 2 2 1 2 1 2 ( ) v u T T v u h T T u T u T T T T T T T e e u v u v T T T m m m m s s s s s p s                                                                                                                                1 2 1 2 ( ) T T T p  (23)         2 2 2 2 1 2 1 2 1 2 1 1 1 1 2 1 1 2 1 2 2 2 1 1 2 2 3 4 2 1 2 1 2 ( ) v u h T T v u h h T T u T u T T T T T T T e e u v u v T T T m m m m s s s s s p                                                                                                                            2 1 2 1 2 ( ) T T T s p       
Using identities (A.3) and (B.3) in appendix 3, one can obtain the following explicit expression composed of eight terms involving a special form of the trivariate gaussian cumulative distribution :

  3 1 2 3 0 1 1 2 2 3 , , , T Q M h M h M h X k      2 2 2 3 2 3 1 1 2 2 1 1 2 2 3 12 23 3 12 23 1 2 3 1 2 3 2 , , , , , , h k T k h T h T h T h T h T N e N T T T T T T m s m m m m m m s s s s s s                                  (24) 1 2 2 1 3 1 1 2 1 2 3 12 23 1 2 3 2 2 , , , h k h T h T h h T e N T T T m s m m m s s s                      2 1 2 2 2 1 3 1 1 1 2 2 3 12 23 1 2 3 2 2 2 , , , h h k h h T h T h h T e N T T T m s m m m s s s                      3 2 2 3 3 1 1 2 2 3 12 23 1 2 3 2 , , , h k h T h T h T e N T T T m s m m m s s s                    3 2 2 2 3 2 3 1 1 2 2 3 12 23 1 2 3 2 2 , , , h h k h h T h T h T e N T T T m s m m m s s s                       3 1 2 2 3 1 3 1 1 2 1 2 3 12 23 1 2 3 2 2 2 , , , h h k h h T h T h h T e N T T T m s m m m s s s                        3 1 2 2 2 3 2 1 3 1 1 2 1 2 3 12 23 1 2 3 2 2 2 2 , , , h h h k h h h T h T h h T e N T T T m s m m m s s s                        
where it is recalled that :

               2 2 2 12 23 2 2 12 23 - 2 2 1 2 1 3 12 23 3/2 2 2 12 23 , , , 2 1 1 y x z y x a b c e N a b c dzdydx r r p r r                  (25)
as was shown in section 1. Knowing this probability would be enough to value a threedimensional standard step up-and-out put option. But, to value a four-dimensional standard step up-and-out put option, we need to add the condition that : 4 3 4

M h

 , as well as the condition that :

4 T X k
 . This is done by solving :

    1 2 3 4 3 3 0 1 1 2 2 3 3 4 3 4 , , , , T T Q Q T X h M h M h M h X k M h E E X 1 1                       =         3 3 1 2 1 2 2 2 2 1 2 h h h h h h h u v w w dwdvdu e u v w w dwdvdu       m s                       (26)           3 3 1 2 1 1 1 2 1 2 1 2 2 2 2 2 2 3 4 + h h h h h h h h h h h e u v w w dwdvdu e u v w w dwdvdu       m m s s                                     3 3 1 2 1 2 3 3 2 2 2 2 2 5 6 + h h h h h h h h h e u v w w dwdvdu e u v w w dwdvdu       m m s s                                    3 3 1 2 1 1 1 2 3 1 3 1 2 2 2 2 2 2 2 7 8 - h h h h h h h h h h h h h e u v w w dwdvdu e u v w w dwdvdu       m m s s                             with :         4 2 2 4 3 4 4 3 4 3 4 3 2 h w k w T T k h w T T w N e N T T T T m s m m s s                                  (27)
and :

        2 2 2 2 1 3 2 1 1 2 1 3 2 1 2 1 3 / 2 3 1 2 1 3 2 2 ( )( ) v u T T w v T T u T T T T T T e u v w T T T T T m m m s s s s p                                                                                      (28)         2 2 2 2 1 2 3 2 1 1 2 1 3 2 2 1 2 2 3 / 2 3 1 2 1 3 2 2 ( )( ) v u T T w v h T T u T T T T T T e u v w T T T T T m m m s s s s p                                                                                               2 2 2 2 1 1 3 2 1 1 2 1 3 2 2 1 2 3 3 / 2 3 1 2 1 3 2 2 ( )( ) v u T T w v h T T u T T T T T T e u v w T T T T T m m m s s s s p                                                                                               2 2 2 2 1 2 1 3 2 1 1 2 1 3 2 2 2 1 2 4 3 / 2 3 1 2 1 3 2 2 ( )( ) v u T T w v h h T T u T T T T T T e u v w T T T T T m m m s s s s p                                                                                                2 2 2 2 1 3 3 2 1 1 2 1 3 2 2 1 2 5 3 / 2 3 1 2 1 3 2 2 ( )( ) v u T T w v h T T u T T T T T T e u v w T T T T T m m m s s s s p                                                                                               2 2 2 2 1 3 2 3 2 1 1 2 1 3 2 2 2 1 2 6 3 / 2 3 1 2 1 3 2 2 ( )( ) v u T T w v h h T T u T T T T T T e u v w T T T T T m m m s s s s p                                                                                                2 2 2 2 1 3 1 3 2 1 1 2 1 3 2 2 2 1 2 7 3 / 2 3 1 2 1 3 2 2 ( )( ) v u T T w v h h T T u T T T T T T e u v w T T T T T m m m s s s s p                                                                                                2 2 2 2 1 3 2 1 3 2 1 1 2 1 3 2 2 2 2 1 2 8 3 / 2 3 1 2 1 3 2 2 ( )( ) v u T T w v h h h T T u T T T T T T e u v w T T T T T m m m s s s s p                                                                                        
Using identities (A.4) and (B.5) in appendix 3, we obtain an explicit expression composed of sixteen terms involving the quadrivariate standard gaussian distribution :

  4 1 2 3 4 0 1 1 2 2 3 3 4 , , , , T Q M h M h M h M h X k      with 1 2 3 4 h h h h    = 3 3 1 1 2 2 4 4 12 23 34 1 2 3 4 , , , , , h T h T h T k T N T T T T m m m m s s s s                  (29) 2 2 2 3 2 3 1 1 2 2 2 4 4 12 23 34 1 2 3 4 2 2 , , , , , h h h T h T h T k h T e N T T T T m s m m m m s s s s                      1 2 2 3 1 3 1 1 2 1 2 1 4 4 12 23 34 1 2 3 4 2 2 2 , , , , , h h h T h T h h T k h T e N T T T T m s m m m m s s s s                         2 1 2 2 3 2 1 3 1 1 1 2 2 2 1 4 4 12 23 34 1 2 3 4 2 2 2 2 2 , , , , , h h h h h T h T h h T k h h T e N T T T T m s m m m m s s s s                          3 2 2 3 3 3 4 1 1 2 2 4 12 23 34 1 2 3 4 2 , , , , , h h T k h T h T h T e N T T T T m s m m m m s s s s                       3 2 2 2 3 2 3 3 2 4 1 1 2 2 4 12 23 34 1 2 3 4 2 2 2 , , , , , h h h h T k h h T h T h T e N T T T T m s m m m m s s s s                           3 1 2 2 3 1 3 3 1 4 1 1 2 1 2 4 12 23 34 1 2 3 4 2 2 2 2 , , , , , h h h h T k h h T h T h h T e N T T T T m s m m m m s s s s                            3 1 2 2 2 3 2 1 3 3 2 1 4 1 1 2 1 2 4 12 23 34 1 2 3 4 2 2 2 2 2 2 , , , , , h h h h h h T k h h h T h T h h T e N T T T T m s m m m m s s s s                              4 2 2 3 3 1 1 2 2 4 4 4 12 23 34 1 2 3 4 2 , , , , , h h T h T h T k h T e N T T T T m s m m m m s s s s                      4 2 2 2 3 2 3 1 1 2 2 4 2 4 4 12 23 34 1 2 3 4 2 2 2 , , , , , h h h h T h T h T k h h T e N T T T T m s m m m m s s s s                          4 1 2 2 3 1 3 1 1 2 1 2 4 1 4 4 12 23 34 1 2 3 4 2 2 2 2 , , , , , h h h h T h T h h T k h h T e N T T T T m s m m m m s s s s                           4 1 2 2 2 3 2 1 3 1 1 1 2 2 4 2 1 4 4 12 23 34 1 2 3 4 2 2 2 2 2 2 , , , , , h h h h h h T h T h h T k h h h T e N T T T T m s m m m m s s s s                              4 3 2 2 3 3 4 3 4 1 1 2 2 4 12 23 34 1 2 3 4 2 2 , , , , , h h h T k h h T h T h T e N T T T T m s m m m m s s s s                         4 3 2 2 2 3 2 3 4 3 2 4 1 1 2 2 4 12 23 34 1 2 3 4 2 2 2 2 , , , , , h h h h h T k h h h T h T h T e N T T T T m s m m m m s s s s                             4 3 1 2 2 3 1 3 4 3 1 4 1 1 2 1 2 4 12 23 34 1 2 3 4 2 2 2 2 2 , , , , , h h h h h T k h h h T h T h h T e N T T T T m s m m m m s s s s                              4 3 2 1 2 3 2 1 3 4 3 2 1 4 1 1 2 1 2 2 1 2 3 4 4 12 23 34 2 2 2 2 2 2 2 , , ,
, ,

h h h h h h h T k h h h h T h T h h T T T T T e N m s m m m m s s s s                                    
where we recall that : ,,,,,2 1 1 1

                    2
x w y x z y w a b c d e N a b c d dzdydxdw r r r p r r r                          (30)
The same method can be applied to value all other standard step-up or step-down barrier options. As a second example, we provide in appendix 2 the formula for a down-and-out call option with four decreasing down-barriers during the option life.

Partial and outside step barrier options

As mentioned earlier, the sequence of monitored barriers needs not be monotonically increasing or decreasing. Besides, monitoring needs not start at the beginning of the option life nor does it have to end at expiry. For example, we may want to value a forward-start earlyending down-and-out call option with monitoring of three different barriers 1 2 3

, ,

H

T T T T T T

     , where 5 T is the option expiry. This time we choose : 1

2 2 3 3 1 , , H H H H H H  
 , instead of having :

1 2 3 H H H  
, as illustrated by graph 3 in appendix 1.

To value this option, we need to calculate :

  5 2 3 4 1 1 2 2 3 3 m , m , m , T Q h h h X k     with 1 2 2 3 3 1 , , h h h h h h   
which is equal to :

  3 4 5 2 3 4 1 1 2 2 3 3 3 3 m , m , m , , T T T Q h h X h h X h X k       (31)
Note that we must impose the condition that :

3 3 T X h
 , in this case.

To find this probability, we first solve :

    2 1 1 1 1 1 2 m , T T Q Q T X h h X k E E X 1 1                    , then : (32)     2 3 2 1 1 1 2 1 2 3 ,m m , T T Q Q T X h h h X k E E X 1 1                     ,then : (33)     2 3 4 3 3 1 1 2 2 3 3 3 4 ,m ,m m , T T Q Q T X h h h h X k E E X 1 1                     
, and eventually : (34)

    2 3 4 4 3 1 1 2 2 3 3 3 5 4 3 ,m ,m , ,m T T T Q Q T X k X h h h X h h E E X 1 1                       (35)
The result is a sum of eight terms involving the quintivariate standard gaussian distribution :

  3 4 5 2 3 4 1 1 2 2 3 3 3 3 m , m , m , , T T T Q h h X h h X h X k        3 3 3 4 5 1 1 1 2 5 12 23 34 45 1 2 3 4 5 , , , , , , , h T h T k T h T h T N T T T T T m m m m m s s s s s                         (36) 1 2 2 3 1 3 3 1 4 1 5 1 1 1 2 5 12 23 34 45 1 2 3 4 5 2 2 2 , , , , , , , h h h T h h T k h T h T h T e N T T T T T m s m m m m m s s s s s                            2 2 2 3 2 3 3 2 4 2 5 1 1 1 2 5 12 23 34 45 1 2 3 4 5 2 2 2 , , , , , , , h h h T h h T k h T h T h T e N T T T T T m s m m m m m s s s s s                               2 1 2 3 2 1 3 3 2 1 4 2 1 5 1 1 1 2 2 1 2 3 4 5 5 12 23 34 45 2 2 2 2 2 2 , , , , , , , h h
h h h T h h h T k h h T h T h T T T T T T e N m s m m m m m s s s s s                                     3 2 2 3 3 3 4 3 5 1 1 1 2 5 12 23 34 45 1 2 3 4 5 2 , , , , , , , h h T h T k h T h T h T e N T T T T T m s m m m m m s s s s s                            3 1 2 2 3 1 3 3 1 4 3 1 5 1 1 1 2 5 12 23 34 45 1 2 3 4 5 2 2 2 2 , , , , , , , h h h h T h h T k h h T h T h T e N T T T T T m s m m m m m s s s s s                               3 2 2 2 3 2 3 3 2 4 3 2 5 1 1 1 2 5 12 23 34 45 1 2 3 4 5 2 2 2 2 , , , , , , , h h h h T h h T k h h T h T h T e N T T T T T m s m m m m m s s s s s                                3 2 1 2 3 2 1 3 3 2 1 4 3 2 1 5 1 1 1 2 2 1 2 3 4 5 5 12 23 34 45 2 2 2 2 2 2 2 , , , , , , , h h h
h h h T h h h T k h h h T h T h T T T T T T e N m s m m m m m s s s s s                                     
where : , , , , , , ,

                         2 2
2 1 1 1 1 v u w v x w y x u u u u u u e N u u u u u dydxdwdvdu r r r r p r r r r                                 (37)
We may also require that the monitored barriers be outside barriers. This can be easily done in our analytical framework. Let us take the example of an up-and-out put option written on an asset S with strike K , expiry 3 T and three outside barriers 1 2 3

, ,

H H H (with 1 2 3 H H H  
) monitored with respect to another asset V . Both S and V follow geometric brownian motion with risk-neutral drift s m and v m respectively, and volatility s s and v s respectively. S and V have correlation coefficient q .

To value this option, we need to find :

      3 1 2 3 0 1 1 2 2 3 , , , V V V T Q M h M h M h X k               (38)
with :

        0 , sup ln / a b V b a t t T T M V V   ,   0 ln / i i h H V  ,   0 ln / k K S  and   3 3 0 ln / T T X S S  (39)
In terms of conditional expectation, this probability can be expressed as :

        3 1 2 3 3 0 1 1 2 2 3 3 3 , , , V V V T T Q Q T X k M h M h M h Y h E E Y 1 1                                        (40)
with :

  3 3 0 ln / T T Y V V  We know how to calculate       1 2 3 0 1 1 2 2 3 3 3 , , , V V V T Q M h M h M h Y h E 1                               (41) Now,   3 3 T Q T X k E Y 1         
is the expectation, under the equivalent martingale measure, of the logarithm of a geometric Brownian motion

      2 2 3 3 3 3 2 3 3 3 3 3 3 1 2 2 1 , 2 3 , 2 1 V V S S V V S S T T a T a T b T b T T T T T X Y s v e f a b T m m m m q s s s s q ps s q                                                                                           (42)
Hence, the density of

3 T X conditional on 3 T Y is :           2 3 3 2 2 3 3 3 2 1 2 3 2 1 S S V V S T T b T a T T X Y S e f b a T s m q m s q s s p q                     (43) i.e.,     3 3 3 2 2 3 3 3 1 S T T S T V S V X Y T Y T T s m q m s q s                    (44)
where  refers to the univariate Gaussian distribution with mean

  3 3 3 S S V V T Y T s m q m s   and variance   2 2 3 1 S T s q 
. Then, performing the necessary calculations, one can obtain :

        3 1 2 3 3 0 1 1 2 2 3 3 3 , , , V V V T T Q Q T X k M h M h M h Y h E E Y 1 1                                        1 1 2 2 3 3 3 4 12 23 1 2 3 3 , , , , , V V V S V V V S h T h T h T k T N T T T T m m m m q s s s s                  (45) 2 2 2 2 3 1 1 2 2 3 2 3 4 12 23 1 2 3 3 2 2 , , , , , V V S S h V V V V V V V S k h T h T h T h h T e N T T T T m s s q m m m m s q s s s s                           1 2 2 1 3 1 1 2 1 2 3 1 3 4 12 23 1 2 3 3 2 2 2 , , , , , V V S S h V V V V V V V S k h T h T h h T h h T e N T T T T m s s q m m m m s q s s s s                                2 1 2 2 1 2 3 1 1 1 2 2 3 2 1 3 4 12 23 1 2 3 3 2 2 2 2 , , , , , V V S S h h V V V V V V V S k h h T h T h h T h h h T e N T T T T m s s q m m m m s q s s s s                               3 2 2 3 3 1 1 2 2 3 3 4 12 23 1 2 3 3 2 , , , , , V V S S h V V V V V V V S k h T h T h T h T e N T T T T m s s q m m m m s q s s s s                              3 2 2 2 2 3 3 1 1 2 2 3 2 3 4 12 23 1 2 3 3 2 2 , , , , , V V S S h h V V V V V V V S k h h T h T h T h h T e N T T T T m s s q m m m m s q s s s s                                  3 1 2 2 1 3 3 1 1 2 1 2 3 1 3 4 12 23 1 2 3 3 2 2 2 , , , , , V V S S h h V V V V V V V S k h h T h T h h T h h T e N T T T T m s s q m m m m s q s s s s                                  3 1 2 2 2 2 3 1 3 1 1 2 1 2 3 2 1 3 4 1 2 3 3 12 23 2 2 2 2 , , , , , V V S S h h h V V V V V V V S k h h h T h T h h T h h h T e N T T T T m s s q m m m m s s s s s q                                    
In the case of outside barriers, we have to resort to a new convolution of normal distribution functions, slightly different from the one given in section 1. This is because we are now faced with two different kinds of correlation coefficients : the first one   12 23 ,   , which is the one we have dealt with so far, is purely path-dependent ; the second one   q measures a correlation of returns between two assets. As a result, we obtain the following minor modification :

                    2 2 2 2 3 12 23 2 2 2 12 23 2 2 1 2 1 2 1 4 12 23 2 2 2 2 12 23 , , , , , 2 1 1 1 z T y x w y x w a b c d e N a b c d dzdydxdw q r r q q p r r q                         (46)
Note too that the final option valuation formula implies a new change of measure. As shown in section 1, the option value is :

            3 3 3 3 1 2 3 0 1 1 2 3 2 1 2 3 0 0 1 1 2 3 2 . , , , , , , S V V V rT T V V V T T e K Q M h M h M h X k S e Q M h M h M h X k d                                     (47)
As before, we have :

2 S S S m m s   
. However, application of Girsanov theorem shows that :

V V S V m m qs s    .

Numerical results

The formulae given in the previous sections would be of little use if their implementation did not provide fast and accurate option values. This raises the question of how to perform the numerical integration implied by the computation of the special forms of multivariate Gaussian distributions involved. As the dimension of the integrals is quite moderate, one can turn to low discrepancy sequences.

The fundamentals of quasi random integration are very well covered, for instance, in [START_REF] Niederreiter | Random Number Generation and Quasi Monte Carlo Methods[END_REF]. It has been shown by [START_REF] Paskov | New methodologies for valuing derivatives[END_REF] that the Sobol algorithm [START_REF] Sobol | On the distribution of points in a cube and the approximate evaluation of integrals[END_REF] performs particularly well when applied to financial problems. Faure sequences have also been proved to be a judicious choice [START_REF] Faure | Discrépance de suites associées associées à un système de numération (en dimension s)[END_REF][START_REF] Boyle | Quasi Monte Carlo Methods in Numerical Finance[END_REF]. There is evidence that Halton sequences [START_REF] Halton | On the efficiency of certain quasi random sequences of points in evaluating multi-dimensional integrals[END_REF] are slightly less reliable than Sobol or Faure sequences in high dimensions. However, they have the attraction of simplicity, and since we are dealing here with five-dimensional integrals at most, they can be used without significant loss of precision, as will be verified in a moment.

To put our analytical approach to the test, we are indeed going to compare the Halton quasi random integration of our formulae with Monte Carlo simulation results. We choose to implement conditional Monte Carlo because, in our experience, it consistently outperforms alternative Monte Carlo variance reduction techniques, such as matching moments, stratification or importance sampling. Good references on conditional Monte Carlo are El Babsiri and Noël (1998) or [START_REF] Andersen | Monte Carlo simulation of options on joint minima and maxima[END_REF]. In particular, El Babsiri and Noël (1998) show how generating extrema over a certain period by their own law, conditional on the simulated terminal value of the underlying asset over the given period, substantially increases the speed and the accuracy of Monte Carlo simulation, and their method will be followed here.

To further reduce variance, we combine conditional Monte Carlo with antithetic variates, and we call this « advanced Monte Carlo », as opposed to « plain Monte Carlo » in which the asset price path is dicretized in time without applying any variance reduction technique and the extrema are monitored four times per business day (which is inefficient and biased high).

We start with the implementation of the formula for a four-dimensional step down-and-out call option given in appendix 2. The dimension, here, is quite moderate, but the fact that we have 32 terms to compute (16 terms under the Q  measure and 16 terms under the Q   measure) makes the issue of efficiency not so trivial. Our Monte Carlo estimator, after n simulations, will be given by :

          1 2 3 4 4 1 2 3 4 0 1 1 2 2 3 3 4 , , , Q T T T T T m H m H m H m H E S K S S S S + 1 1 1 1                                    2 1 1 1 4 4 1 2 3 4 1 2 3 4 4 2ln / ln / ln / / , , , 1 1 1 1 i i i i j j j T T T T j j j j i i i i T T T T n H S S S H S T i rT T S H S H S H S H j i e S K e n 1 s                                                                                             (48)
where   i t S denotes the value of t S randomly drawn at simulation n°i

The results are provided in Table 1. One can observe the quality of convergence of quasi random integration of analytical formulae, using only a small sample of Halton points, which makes it extremely fast to compute, even on an ordinary personal computer. In contrast, convergence is much slower with Monte Carlo simulation.

Due to its intrinsic uncertainty, the accuracy of Monte Carlo simulation should obviously be gauged with respect to analytical values, provided that the process of quasi random integration does not alter the exact theoretical solutions. One way to estimate the possible distorsion created by quasi random integration is to use it to compute option values that can be computed otherwise with great precision, so that we have a benchmark at our disposal.

This the case for one-dimensional options, as we can rightfully trust our numerical estimates of the univariate gaussian distribution. However, our test of quasi random integration will be biased if we simply perform one-dimensional quasi-random integration, because then we shall not feel entitled to extrapolate our findings to the behaviour of quasi random integration in dimension four. A possible solution is to compute four-dimensional formulae which exactly converge to one-dimensional formulae. For example, a step down-and-out call option with H1=90, H2=90, H3=90 and H4=90, should have exactly the same value as that of a standard down-and-out call option with H=90. Table 2 shows the results of this simple test. They confirm the robustness of quasi random integration. Almost instantaneously, we obtain a price whose divergence from the calibrating exact price is less than 0.003%. In contrast, using advanced Monte Carlo, the immediate price we obtain exhibits an awful divergence of 11.9% from the calibrating exact price. After performing two million simulations, that divergence has shrunk to 0.008%, but the procedure is extremely time-consuming and cannot be applied in real trading time.

In Table 3, we turn to the implementation of the formula for a four-dimensional step up-and-out put option given in section 2. Again, we test the precision of quasi random integration by using it compute the value of the same step up-and-out put option with all four barriers fixed at 120, which should be strictly equal to a standard up-and-out put option with a knock-out barrier at 120. This time, the quasi instantaneous analytical price we obtain diverges from the exact calibrating price from 0.002% (Table 4).

In Table 5, we implement the formula for a forward-start early-ending three-step downand-out call option given in section 3. As one more dimension is involved, we increase the size of our samples of Halton quasi random points. As a result, computational time is slightly longer, but it remains extremely efficient compared with Monte Carlo simulation.

Of course, computational time could be cut simply by using more hardware resources.

Eventually, in Table 6, we implement the formula for an outside three-step up-and-out put option given in section 3. Inputs : S = 100 ; K = 100 ; r = 0.06 ;  = 0.02 ; T1 = 0.6 ; T2 = 1.2 ; T3 = 1.8 ; T4 = 2.4 H1 = 90 ; H2 = 90 ; H3 = 90 ; H4 = 90 ; volatility = 32% Inputs : S = 100 ; K = 100 ; r = 0.06 ;  = 0.02 ; T1 = 0.6 ; T2 = 1.2 ; T3 = 1.8 ; T4 = 2.4 H1 = 120 ; H2 = 122 ; H3 = 125 ; H4 = 128 Inputs : S = 100 ; K = 100 ; r = 0.06 ;  = 0.02 ; T1 = 0.6 ; T2 = 1.2 ; T3 = 1.8 ; T4 = 2.4 H1 = 120 ; H2 = 120 ; H3 = 120 ; H4 = 120 ; volatility = 32% Inputs : S = 100 ; K = 100 ; r = 0.06 ;  = 0.02 ; T1 = 0.3 ; T2 = 0.6 ; T3 = 0.9 ; T4 = 1.2 T5 = 2 ; H1 = 92 ; H2 = 85 ; H3 = 88 More sophisticated stochastic processes may be required to model the motion of the underlying asset, making it impossible to find explicit solutions when joint extrema are involved. Still, analytical formulae remain valuable as accurate benchmarks to test more general numerical schemes.

In the cases that have been covered, only one barrier, whether down-and-out or up-and-out, or no barrier at all, is monitored at any one time. One may need to value partial double barrier options with periods when two barriers, one down-and-out and the other up-and-out, are simultaneously monitored. Classical examples are the so-called « hot dog » or « corridor » options with double barriers that change as step functions of time. Exact values can be found for these contingent claims too. However we would not recommend the use of analytical pricing in this case. Indeed, such formulae involve products of infinite series, so that the number of terms increases very quickly, which makes it cumbersome to calculate analytically and inefficient to compute numerically.

APPENDIX 1 : GRAPHS Graph 1 : four-dimensional standard step up-and-out option

T 0 T 1 T 2 T 3 T 4
Graph 2 : four-dimensional standard step down-and-out option

T 0 T 1 T 2 T 3 T 4
Graph 3 : forward-start early-ending three-step down-and-out option

  4 1 2 3 4 0 1 1 2 2 3 3 4 m , m , m , m , T Q h h h h X k      (49)
where:

      0 , inf ln / a b b a t t T T m S S     0 ln / i i h H S    0 ln / k K S    4 4 0 ln / T T X S S  By successively solving :     1 2 1 1 0 1 1 2 1 2 , , T T Q Q T X h m h X k m h E E X 1 1                     (50)     1 2 3 2 2 0 1 1 2 2 3 2 3 , , , T T Q Q T X h m h m h X k m h E E X 1 1                      (51)     1 2 3 4 3 3 0 1 1 2 2 3 3 4 3 4 , , , , T T Q Q T X h m h m h m h X k m h E E X 1 1                       (52)
by means of the method explained in section 2 of this paper, using identities (A.

  4 1 2 3 4 0 1 1 2 2 3 3 4 m , m , m , m , T Q H H H H X K                                4 3 2 2 2 3 2 3 4 3 2 4 1 1 2 2 4 12 23 34 1 2 3 4 2 2 2 2 , , , , , h h h h h T k h h h T h T h T e N T T T T m s m m m m s s s s                                                      3 1 2 2 3 1 3 3 1 4 1 1 2 1 2 4 12 23 34 1 2 3 4 2 2 2 2 , , , , , h h h h T k h h T h T h h T e N T T T T m s m m m m s s s s                            4 3 1 2 2 3 1 3 4 3 1 4 1 1 2 1 2 4 12 23 34 1 2 3 4 2 2 2 2 2 , , , , , h h h h h T k h h h T h T h h T e N T T T T m s m m m m s s s s                                                         4 2 1 2 2 3 2 1 3 1 1 2 1 2 4 2 1 4 4 12 23 34 1 2 3 4 2 2 2 2 2 2 h h h h h h T h T h h T k h h h T e N T T T T m s m m m m s s s s                                  3 2 1 2 2 3 2 1 3 3 2 1 4 1 1 2 1 2 4 12 23 34 1 2 3 4 2 2 2 2 2 2 , , , , , h h h h h h T k h h h T h T h h T e N T T T T m s m m m m s s s s                                                          
where the function   , , ,     are any real numbers. There is a one-to-one correspondence between each operator  or  appearing on the left-hand side of every identity and each symmetrical operator appearing on the right-hand side of the same identity (symmetrical meaning here in the same order of appearance). To make sure that these notations are clear, proposition A.3) is expanded at the end of this list into the two identities it is equivalent to.

These straightforward identities, which can easily be verified, are helpful to simplify multiple integrals that are frequently encountered in multidimensional barrier option pricing. They are readily extended to higher dimensions.

2 2 1 2 1 1 1 .1) 2 2 2 1 1 u T u T A u T T m m m s s s                                             2 2 2 2 1 2 1 2 1 1 .2) 2 2 2 2 1 1 u h T u h T A h h u h h T T m m m m a a l a l a s s s s                                                     2 2 2 2 1 2 2 1 1 .3) 2 2 1 2 1 2 2 2 1 2 1 1 2 1 2 1 v u h h T T u T A h h h v T T T v u h h T T u T T T T m m m b a l b a s s s m m b a s s                                                                                                                         2 2 2 h h h m l b a s                                                                                                                                                                 m m m a b g l b a g s s s                                                                                                                                                                                                        2 2 2 h h h m l b a s                                     2 2 2 2 2 2 1 2 3 2 2 1 1 .8) 2 2 1 2 1 3 2 2 1 1 2 1 w v h h h T

T v u T T u T A h h h h w

                                                                                                                                                                                                           2 2 1 2 1 2 1 1 2 1 2 12 2 2 1 2 1 2 1 .1) , 2 ( ) u v u T T T e B dvdu N T T T T T s s s s s p                                                                                  2 2 1 2 1 2 1 1 2 1 2 12 2 2 1 2 1 2 1 .2) , 2 ( ) u v u T T T e B dvdu N T T T T T s s s s s p                                                                                                                                                                                                         
                                                                                                                                                                                                                                     
                    
For example, proposition A.3) is expanded into :

      a s s                                                                                                                               2 2 h h h m l b a s                                2 2 2 2 1 2 2 1 1 2 2 1 2 1 2 2 2 2 1 2 1 1 2 1 2 1 ii v u h h T T u T h h h v T T T v u h h T T u T T T T m m m b a l b a s s s m m b a s s                                                                                                                              2 2 h h h m l b a s                        

    .  refers to the first-order derivative of  

  analytical valuation of a d  dimensional standard step-up barrier option involves the calculation of the distribution of d increasing maxima and terminal value of a geometric Brownian motion. Likewise, valuing a d  dimensional standard step-down barrier option involves the calculation of the distribution of d decreasing minima and terminal value of a geometric Brownian motion.

  Inputs : S = 100 ; K = 100 ; r = 0.06 ;  = 0.02 ; T1 = 0.6 ; T2 = 1.2 ; T3 = 1.8 ; T4 = 2.4 H1 = 90 ; H2 = 84 ; H3 = 80 ; H4 = 76 ; QRA = Quasi Random Analytical(Halton) ; AMC = Advanced Monte Carlo simulation ; PMC = Plain Monte Carlo simulation

  Inputs : S = 15 ; K = 18 ; V = 100 ; H1 = 125 ; H2 = 130 ; H3 = 135 r = 0.06 ;  S = 0.27 ;  S = 0.01 ;  V = 0.32 ;  V = 0.02 ; T1 = 0.5 ; T2 = 0.8 ; T3 = 1.5ConclusionThis paper has shown ways to obtain explicit formulae for a variety of barrier options with complex payoffs involving joint distributions of several extrema. Combined with quasi random integration, analytical formulae provide extremely fast and accurate option values, compared with Monte Carlo simulation. They can also provide exact hedge ratios by mere differentiation. Probably most important of all, analytical solutions tell us how the various parameters affect the solution and bring out the interrelationships among them.

     has been defined in Section 1APPENDIX 3 : USEFUL IDENTITIESIn the following, , , , u v w x are variables of integration, , , , l a b g are arbitrary integers indexing barrier level, and 1 2 3 4

Table 1 : four-dimensional standard step down-and-out call option

 1

	Number of	Volatility	Volatility	Volatility	Computational	Standard error
	simulations /	= 18%	= 25%	= 32%	Time	(for simulation)
	Halton points				(PIII 1 GHz)
	QRA	11.42	11.42	11.26	00 : 18'
	50,000
	QRA	11.37	11.42	11.29	00 : 04'
	10,000
	AMC	11.41	11.40	11.26	03 : 07'	0.0067
	2,000,000
	AMC	11.19	11.56	11.06	00 : 16'	0.0604
	200,000
	PMC	11.76	12.01	11.92	18 : 23'	0.1242
	100,000

Table 2 : four-dimensional step down-and-out call option theoretically equal to a standard down-and-out call option

 2

		Exact value QRA	QRA	AMC	AMC	AMC
			10,000	50,000	10,000	50,000	2,000,000
	4-D step	10.46	10.49	10.44	9.35	9.40	10.38
	DOC

Table 3 : four-dimensional standard step up-and-out put option

 3

	Number of	Volatility	Volatility	Volatility	Computational	Standard error
	simulations /	= 18%	= 25%	= 32%	Time	(for simulation)
	Halton points				(PIII 1 GHz)
	QRA	5.60	7.70	9.14	00 : 18'
	50,000
	QRA	5.59	7.71	9.17	00 : 04'
	10,000
	AMC	5.64	7.74	9.14	03 : 09'	0.0044
	2,000,000
	AMC	5.82	7.58	9.26	00 : 16'	0.0592
	200,000
	PMC	6.02	7.08	9.52	18 : 28'	0.1308
	100,000

Table 4 : four-dimensional step up-and-out put option theoretically equal to a standard up-and-out put option

 4

		Exact value QRA	QRA	AMC	AMC	AMC
			10,000	50,000	10,000	50,000	2,000,000
	4-D step	8.92	8.94	8.89	9.27	8.98	8.94
	UOP

Table 5 : forward-start early-ending three-step down-and-out call option

 5

	Number of	Volatility	Volatility	Volatility	Computational	Standard error
	simulations /	= 18%	= 25%	= 32%	Time	(for simulation)
	Halton points				(PIII 1 GHz)
	QRA	10.45	11.67	12.95	01 : 06'
	200,000
	PMC	10.50	11.78	13.09	58 : 33'	0.014
	1,000,000
	QRA	10.40	11.62	12.91	00 : 42'
	100,000

Table 6 : outside three-step up-and-out put option

 6

	Number of	Correlation	Correlation	Correlation	Computational	Standard error
	simulations /	= -0.5	= 0	= 0.5	Time	(for simulation)
	Halton points				(PIII 1 GHz)
	QRA	1.01	1.52	1.91	00 : 03'
	10,000
	QRA	1.01	1.51	1.91	00 : 30'
	100,000
	AMC	1.06	1.51	1.93	01 : 54'	0.002
	2,000,000
	AMC	1.07	1.54	1.95	00 : 16'	0.008
	200,000

FORMULA FOR THE PRICE OF A FOUR-DIMENSIONAL STANDARD STEP DOWN-AND-OUT CALL OPTION

	APPENDIX 2 : At expiry 4 T , a four-dimensional European standard step down-and-out call option pays
	off : 	4 T S		K	 	, provided that the barrier 1 H is not crossed before 1 T and that the barrier 2 H is
	not crossed between 1 T and 2 T and that the barrier 3 H is not crossed between 2 T and 3 T and
	that the barrier	H	4	is not crossed between 3 T and the option expiry 4 T , with :
	1 H		0 S H ,	2		0 S H ,	3		0 S H ,	4	0  , and : 1 S H		H	2		H	3		H	4
				T 0							T 1						T 2				T 3	T 4	T 5

.

As shown in section 1, finding a formula for the price of a four-dimensional European standard step down-and-out call option involves computing the following joint cumulative distribution :

  A.8) and(B.6) in Appendix 3 at stage (iii), one can obtain a closed form expression made up of sixteen terms involving the quadrivariate standard gaussian distribution :

5), (A.6) and (B.2) in Appendix 3 at stage (i), identities (A.7) and (B.4) in Appendix 3 at stage (ii), identities (

  

	N	4	s	1 T 1	,	s	2 T 2	,	s	3 T 3	,	s	4 T 4	12	,	23	,	34


Mohamed Amellal
email: mohamed.amellal@eseo.fr

Mohamed Ramdani
email: mohamed.ramdani@eseo.fr

Richard Perdriau
email: richard.perdriau@eseo.fr

Mathieu Medina
email: m.medina@serma.com

Mhamed Drissi
email: mhamed.drissi@insa-rennes.fr

Ali Ahaitouf
email: aliahitouf@yahoo.fr

The Conducted Immunity of SPI EEPROM Memories

This paper focus on the conducted immunity measurement of non-volatile memories up to 1 GHz. A specific measurement flow is introduced, which makes possible to compare the EMC performances in different test cases. Trough measurements and simulation, this study gives a real view on the immunity difference of this integrated circuits (IC).

I. INTRODUCTION

Currently, the memory market reaches almost half of the production of integrated circuits. This evolution is mainly due to the improvement of the manufacturing and the design process of memories. Therefore, the significant growth experienced by industrial applications requiring permanent storage of information, helped to focus on the study and improvement of the performance of non-volatile memories. Based on the fact that electromagnetic disturbances can trigger modifications in memory zones, the impact on systems incorporating these circuits can be enough to make them unusable.

In addition, modern ICs suffer from high susceptibility to radio frequency interference up to 5 GHz [START_REF] Barber | Conducted susceptibility measurements on integrated circuits[END_REF] [START_REF] Sketoe | Integrated circuit electromagnetic immunity handbook[END_REF]. Consequently, the study of the conducted susceptibility of various memories is becoming compulsory as far as each supplier has its own technologies. Many efforts have been done in the development of tools, methodology [START_REF] Chen | Interconnect and circuit modeling techniques for full-chip power supply noise analysis[END_REF] [4] [START_REF] Steinecke | Highaccuracy emission simulation models for vlsi chips including package and printed circuit board[END_REF] and models [START_REF]Models of integrated circuits for EMI behavioural simulation[END_REF] for the prediction of parasitic emission of ICs. However susceptibility modeling has not followed the same evolution and few dedicated simulation methodologies or models [START_REF] Levant | Emc assessment at chip and pcb level: Use of the icem model for jitter analysis in an integrated pll[END_REF] have been proposed yet, particularly for memories. This paper describes measurement technique based on direct power injection (DPI) test [START_REF]Integrated Circuits Measurement of Electromagnetic Immunity 150 kHz to 1 GHz Part 4: Direct RF Power Injection Method[END_REF] specially dedicated to Serial Peripheral Interface (SPI) memories, which proposes three different test modes and set a digital immunity criterion. The main objective of this study is to compare the conducted immunity of two SPI EEPROM memories.

The paper is organized as follows. Sect. II describes the structure and validity conditions of the test. Then, Sect. III provides the obtained results and discuses the validation of this technique and also a simulation model is presented and explained, before giving some statement about new perspectives.

II. STRUCTURE AND TEST SET-UP OF THE SPI MEMORIES

A. Description of the tested memories

The choice of tested memories was based on the principle of obsolescence, in other words, the selected memories size may be different, with different technologies and produced by different manufactures, however, they must share three characteristics :

• SPI communication interface.

• SOIC8 package.

• 3.3Vpower supply voltage. Based on these parameters, and in order to assess the impact of manufacturing and design process, we chose to conduct our study on two memories whose characteristics are presented in Table I.

B. Test set-up for SPI memories

The suggested test is dedicated to the prediction of the immunity behavior for continuous wave (CW) disturbances, in the 1MHz-1GHz frequency range, and up to 30 dBm incident power in the DPI test. As shown in the Figure 1, the measurement system consists of two different board:

• Test PCB: it is a generic SOIC DPI measurement board [START_REF] Frédéric | Développement de techniques et de méthodologies pour la prise en compte des contraintes CEM dans la conception d'équipements du domaine automobile. Etude de l'immunité, du composant l'équipement[END_REF]. Thanks to it, both S-parameter and DPI measurements can be performed on the same PCB. • SPI interface:This board is specifically developed for the study of SPI memories with a module FTDI2232H that plays the role of the SPI communication interface.

In fact, this component will allow the implementation of our susceptibility criteria for the different test mode.

It should be noted that in addition to being mounted on two separate boards, the FTDI module and the DUT have also two different power supplies. The purpose of this is to reduce as much as possible coupling of RF aggression to the SPI power supply board and, consequently,the disturbance of the FTDI module.

C. Definition of an immunity criterion

The definition of immunity criteria for integrated circuits is still a prominent issue, due to the very wide range of IC functionalities. For memories, the accuracy of its returned data is the essential information, therefore our criterion is based on this assertion. The circuit is considered perturbed if:

• Criterion 1: The value of the status register has changed after the RF perturbation. • Criterion 2: The percentage of wrong read data is higher than the error rate threshold (10%).

Based on the fact that in an industrial application, electromagnetic disturbances can occur at random instants, the SPImemory test includes three kinds of investigation, a flowchart of one of them is shown in Figure 2 :

• Test mode 1: Disturbed write, undisturbed read.

• Test mode 2: Undisturbed write, disturbed read.

• Test mode 3: Undisturbed write, 2-second disturbance, undisturbed read.

In all tests, two different data are written in two the different addresses and then, read 100 times each to ensure the measurement reproducibility.

III. RESULTS AND DISCUSSION

A. DPI measurements

For validation purposes, different experiments were performed for each memory using the same immunity criterion. As we can see in Figure 3, even if the memories are functionally equivalent and therefore interchangeable, their susceptibility is far from being the same. The difference between the two memories immunity can be more than 10 dB at some frequencies for the same test mode. This result is fundamental for the suggested methodology since, at first glance, the AT25512 and the 25LC512 are a priori two equivalent EEPROMs, this proves that manufacturing and design process have a big impact on the electromagnetic character of ICs.

B. simulation model

In order to confirm the measurements results, a simulation model based on the ICIM-CI standard [START_REF]Proposal) Integrated Circuit EMC modeling Part 4: ICIM-CI (Integrated Circuit Immunity Model, Conducted Immunity)[END_REF] was performed on the two memories. The main objective is, the immunity prediction and validation of DPI measurements.

1) S parameters and PDN model: Lumped elements modeling of the input impedance of each component will identify the influence of PDN (Passive Distribution Network) on the immunity difference. The extraction of the S-parameters, by considering each pin as a port referenced to the ground pin of the IC (port 1 is the V dd pin), was done with the same PCB as in DPI measurements, and a direct calibration is performed in the reference plane of the IC thanks to a custom calibration kit.

As showed in Figure 4 the MICROCHIP memory has the lowest S 11 , it means that, if both devices have the same manufacturing and design process, more RF power is needed to disturb the ATMEL memory. To prove that same active parameters can affect the memories susceptibility, we try to evaluate the MOS capacitance of each device by measuring the input impedance. In fact, this capacitance can be extracted from the difference between the input impedance with and without power supply.

As we can see in the result showed in figure 5(a) and 6(a), the MOS capacitance C3 is higher on the MICROCHIP memory (about 17 times).This result indicates that, the manufacturing and design process of both devices are actually To estimate the power transmitted to the IC, a simulation based on the modeling of a complete DPI set-up was used [START_REF] Lafon | Immunity Modeling of Integrated Circuits: an Industrial Case[END_REF], the only difference is that, in this paper, we use an ADS simulation witch allows use of measured S-parameters. Figure 7 display the model corresponds to the SPI memories test on the V dd pin in predict configuration. In the fact, the 100 pFdecoupling capacitor is added to the simulation model to predict the device immunity in other configuration and then validate the model. A significant correlation between simulation and measurement can be noticed (Figure 8), seeing that, the DPI measurements artifacts. Based on this, we can assert that DPI measurement are correct.

It can be noted that 30 dBm corresponds to the maximum incident power fixed during the tests.

IV. CONCLUSION

In this paper, we described a measurement methodology of conducted immunity for SPI memories. Throughout our analysis, we made the susceptibility comparison of two EEPROM memories from different suppliers.

The measurement results showed firstly that, although the selected memories are in the same technology and also func-tionally equivalent, is no proof that their conducted immunity should be the same. Secondly, the S-parameters are not the best way, in this case, to find and explain the source of the immunity difference. However, modeling the input impedance was useful to prove the impact of manufacturing and design process on the conducted immunity of EEPROM SPI Memories.

Moreover, a detailed technological analysis confirmed that, manufacturing and design process of the two device is very different.

These observations must be confirmed with other technologies of non-volatile memories but, nevertheless, provide interesting perspectives for obsolescence management in EMC study.

Fig. 1 .

 1 Fig. 1. General diagram of DPI measurement system for SPI memories

Fig. 2 .

 2 Fig. 2. Test mode 1 : Disturbed write, undisturbed read flowchart

Fig. 3 .

 3 Fig. 3. Immunity difference between both memories

  Fig. 5. Measurement of the ATMEL MOS capacitance

Fig. 6 . 2 )

 62 Fig. 6. Measurement of the MICROCHIP MOS capacitance

Fig. 8 .

 8 Fig. 8. Immunity prediction compared with DPI measurement results on the AT25512.