Student Member, IEEE Jérôme Gauthier
email: jerome.gauthier@univ-paris-est.fr.

Member, IEEE Laurent Duval
email: laurent.duval@ifp.fr.

Senior Member, IEEE Jean-Christophe Pesquet
email: jean-christophe.pesquet@univ-paris-est.fr.

J.-C Pesquet

Optimization of Synthesis Oversampled Complex Filter Banks

Keywords: Oversampled filter banks, inversion, filter design, optimization, time localization, frequency localization, lapped transforms, modulated filter banks. I

An important issue with oversampled FIR analysis filter banks (FBs) is to determine inverse synthesis FBs, when they exist. Given any complex oversampled FIR analysis FB, we first provide an algorithm to determine whether there exists an inverse FIR synthesis system. We also provide a method to ensure the Hermitian symmetry property on the synthesis side, which is serviceable to processing real-valued signals. As an invertible analysis scheme corresponds to a redundant decomposition, there is no unique inverse FB. Given a particular solution, we parameterize the whole family of inverses through a null space projection. The resulting reduced parameter set simplifies design procedures, since the perfect reconstruction constrained optimization problem is recast as an unconstrained optimization problem. The design of optimized synthesis FBs based on time or frequency localization criteria is then investigated, using a simple yet efficient gradient algorithm.

oversampled FBs (OFBs) constitute an extensively studied instance with remaining open questions. Their development came along under a variety of different appellations, to name a few: general Analysis-Synthesis Systems [START_REF] Kellermann | Analysis and design of multirate systems for cancellation of acoustical echoes[END_REF], DFT (discrete Fourier transform) with stack-shift capability, Overlap-Add or Generalized DFT, underdecimated systems, oversampled harmonic modulated filter banks [START_REF] Bölcskei | Oversampled cosine modulated filter banks with perfect reconstruction[END_REF], [START_REF] Labeau | Oversampled filter banks as error correcting codes: Theory and impulse noise correction[END_REF], complex lapped transforms [START_REF] Young | Frequency-domain motion estimation using a complex lapped transform[END_REF], generalized lapped pseudo-biorthogonal transform, etc.

In a more generic form, OFBs have received a considerable attention both theoretically and in many applications, in the past ten years, following their association with specific types of frames [START_REF] Bölcskei | Oversampled cosine modulated filter banks with perfect reconstruction[END_REF], [START_REF] Bölcskei | Frame-theoretic analysis of oversampled filter banks[END_REF], [START_REF] Cvetković | Overampled filter banks[END_REF].

Their design flexibility, improved frequency selectivity and increased robustness to noise and aliasing distortions have made them useful for subband adaptive filtering in audio processing [START_REF] Malvar | A modulated complex lapped transform and its applications to audio processing[END_REF], noise shaping [START_REF] Bölcskei | Oversampled filter banks: Optimal noise shaping, design freedom, and noise analysis[END_REF], denoising [START_REF] Labeau | Oversampled filter banks as error correcting codes: Theory and impulse noise correction[END_REF], multiple description coding [START_REF] Goyal | Quantized frame expansions with erasures[END_REF], echo cancellation [START_REF] Dumitrescu | Simplified design of low-delay oversampled NPR GDFT filterbanks[END_REF], multiple antenna code design [START_REF] Hassibi | Representation theory for high-rate multiple-antenna code design[END_REF], channel equalization [START_REF] Pun | Design of oversampled filter bank based widely linear OQPSK equalizer[END_REF], [START_REF] Ihalainen | Channel equalization in filter bank based multicarrier modulation for wireless communications[END_REF], [START_REF] Johansson | Flexible frequency-band reallocation networks using variable oversampled complexmodulated filter banks[END_REF] or channel coding [START_REF] Weiß | Paraunitary oversampled filter bank design for channel coding[END_REF]. Two major problems arise when resorting to OFBs: (i) the existence of an inverse for the analysis OFB achieving perfect reconstruction (PR) and (ii) the determination of an "optimal" synthesis FB. Since the additional degrees of freedom gained through redundancy may increase the design complexity, several works have focused on FBs modulated with a single [START_REF] Cvetković | Tight Weyl-Heisenberg frames in 2 (R)[END_REF], [START_REF] Yui | Multicriteria design of oversampled uniform DFT filter banks[END_REF] or multiple windows [START_REF] Ueng | Frames and orthonormal bases for variable windowed Fourier transforms[END_REF]. More general formulations are based on factorizations of OFB polyphase representations with additional constraints (restricted oversampling ratios, symmetry, realness or filter length) into a lattice [START_REF] Borries | On filter banks with rational oversampling[END_REF], [START_REF] Borries | Linear phase oversampled filter banks[END_REF], [START_REF] Gan | Oversampled linear-phase perfect reconstruction filterbanks: Theory, lattice structure and parameterization[END_REF], [START_REF] Tanaka | A direct design of oversampled perfect reconstruction FIR filter banks of 50%-overlapping filters[END_REF] or a lifting structure [START_REF] Riel | Lifting-based design and implementation of oversampled paraunitary modulated filter banks[END_REF]. Constructions with near perfect reconstruction (relaxing the PR property) have also been proposed [START_REF] Harteneck | Design of near perfect reconstruction oversampled filter banks for subband adaptive filters[END_REF], [START_REF] Wilbur | Efficient design of oversampled NPR GDFT filter banks[END_REF], [START_REF] Dumitrescu | Simplified design of low-delay oversampled NPR GDFT filterbanks[END_REF], [START_REF] Hermann | Window based prototype filter design for highly oversampled filter banks in audio applications[END_REF]. In [START_REF] Kalker | Groebner basis techniques in multidimensional multirate systems[END_REF], [START_REF] Park | Gröbner bases and multidimensional FIR multirate systems[END_REF], [START_REF] Zhou | Multidimensional oversampled filter banks[END_REF], more involved algebraic tools (such as Gröbner bases) have also been employed. Recently, Chai et al. have proposed a design based on FB state-space representations [START_REF] Chai | Frame-theory-based analysis and design of oversampled filter banks: Direct computational method[END_REF]. The design may use different kinds of optimization criteria based on filter regularity or more traditional cost functions based on filter shape (subband attenuation [START_REF] Gan | Oversampled linear-phase perfect reconstruction filterbanks: Theory, lattice structure and parameterization[END_REF], [START_REF] Dumitrescu | Simplified design of low-delay oversampled NPR GDFT filterbanks[END_REF], coding gain [START_REF] Labeau | Synthesis filters design for coding gain in oversampled filter banks[END_REF]).

Most of those synthesis FB designs rely on minimum-norm solutions. An interesting approach combining the latters with a null space method was successfully pursued by Mansour [START_REF] Mansour | On the optimization of oversampled DFT filter banks[END_REF] for synthesis window shape optimization in a modulated DFT FB.

Within the compass of the proposed work is a relatively generic construction and optimization of oversampled synthesis filter banks with Finite Impulse Response (FIR) properties at both the analysis and synthesis sides. We can additionally impose a practically useful Hermitian symmetry on the synthesis side. This work extends the results given in two previous conference papers [START_REF] Gauthier | Low redundancy oversampled lapped transforms and application to 3D seismic data filtering[END_REF], [START_REF]Oversampled inverse complex lapped transform optimization[END_REF]. A special case has been judiciously devised in [START_REF] Tanaka | A direct design of oversampled perfect reconstruction FIR filter banks of 50%-overlapping filters[END_REF], for specific filter length and redundancy factor allowing closed form expressions for two design criteria. In Section II we recall the polyphase notation used throughout this paper. Given arbitrary FIR complex oversampled analysis FB, we first describe in Section III-A July 20, 2009 DRAFT a simple algorithm to test whether it is FIR invertible or not, based on known results on polynomial matrices [START_REF] Fornasini | nD polynomial matrices with applications to multidimensional signal analysis[END_REF], [START_REF] Park | Symbolic computation and signal processing[END_REF]. The standard Moore-Penrose pseudo-inverse (PI) solution [START_REF] Ben-Israel | Generalized Inverses: Theory and Applications[END_REF] is studied in Section III-B. In Section III-C, a method is supplied to enforce an Hermitian symmetric FB, which is useful for real data analysis, processing and synthesis. In Section IV, the problem of the optimal design of the synthesis FB is addressed. Although optimization can be studied both on the analysis and synthesis sides [START_REF] Tanaka | The generalized lapped pseudo-biorthogonal transform: Oversampled linear-phase perfect reconstruction filter banks with lattice structures[END_REF], [START_REF] Komeiji | A direct design of oversampled perfect reconstruction bandpass fir filterbanks with real coefficients[END_REF], we consider here a given analysis FB and work on the synthesis side. We derive in Section IV-A an efficient parameter set size reduction for this purpose. Using time or frequency localization criteria, we then reformulate in Section IV-B the constrained optimization problem as an unconstrained one for both the general and Hermitian symmetric cases. After describing the optimization process, we illustrate, in Section V, the different methods proposed for the inversion and optimization on three classical oversampled real and complex FB types.

II. PROBLEM STATEMENT

A. Notations Lapped transforms [START_REF] Malvar | Signal processing with Lapped Transforms[END_REF] were introduced in [START_REF] Cassereau | Encoding of images based on lapped orthogonal transform[END_REF] to avoid blocking artifacts in audio processing.

Similarly for images, they reduce tiling effects produced by classical block transforms (as can be seen in the JPEG image compression format). Lapped transforms belong to the class of FBs, such as the one represented in Figure 1, with a decimation factor N smaller than the length of each filter. The filters, whose impulse responses are denoted by (h i ) 0≤i<M , are supposed of finite length kN with k an integer greater than or equal to 2. We therefore consider k overlapping blocks of size N .

A signal (x(n)) n∈Z is decomposed by M filters; since the decimation factor is N , the overall redundancy of the transform is M/N = k . In this paper, we investigate the oversampled case, i.e. k > 1.

The M outputs of the analysis FB are denoted by (y i (n)) 0≤i<M . With these notations, the outputs of July 20, 2009 DRAFT the analysis FB are expressed, for all i ∈ {0, . . . , M -1} and n ∈ Z, as

y i (n) = p h i (p)x(N n -p) = N -1 j=0 h i (N + j)x(N (n -) -j). (1)

B. Polyphase formulation

Let H( ) = [h i (N + j)] 0≤i<M,0≤j<N , ∈ {0, . . . , k -1} be the k polyphase matrices obtained from the impulse responses of the analysis filters. We also define the polyphase vector from the input signal

x(n): ∀n ∈ Z, x(n) = (x(N n -j)) 0≤j<N
, leading to concisely rewriting (1) into a convolutive form:

y(n) = (y 0 (n), . . . , y M -1 (n)) = k-1 =0 H( )x(n -) = (H * x) (n), (2)
where is the transpose operator. Thus, (2) can be reexpressed as:

y[z] = H[z]x[z],
where

H[z] = k-1 =0 H( )z -is the M × N polyphase transfer matrix of the analysis FB and x[z] (resp. y[z]) is the z-transform of (x(n)) n∈Z (resp. (y(n)) n∈Z ).

C. Synthesis FB

The polyphase transfer matrix of the synthesis FB:

H[z] = H( )z -, satisfies: x[z] = H[z]y[z], (3)
where the polyphase vector of the ouput signal of the synthesis FB ( x(n)) n∈Z is defined similarly to (x(n)) n∈Z . We deduce from (3) that:

∀n ∈ Z, ∀i ∈ {0, ..., N -1} , x(nN -i) = M -1 j=0 ∞ =-∞ H i,j (n -)y j ( ), (4)
where

H( ) = H i,j ( ) 0≤i<N,0≤j<M
. Expressing (4) with impulse responses, we can write: for every i ∈ {0, ..., N -1} and n ∈ Z,

x(nN -i) = M -1 j=0 ∞ =-∞ h j (N (n -) -i)y j ( ) (5)
which, by identifying ( 4) and ( 5), allows us to deduce that

H( ) = h j (N -i) 0≤i<N,0≤j<M , ∈ Z. (6)
These expressions hold for any oversampled FIR FB.

July 20, 2009 DRAFT

III. INVERSION

A. Invertibility of an analysis FB

This work being focused on the construction of FIR synthesis filters, a preliminary point is the verification of the given analysis FB FIR invertibility. The polyphase representation of FBs offers the advantage of relating the perfect reconstruction property to the invertibility of the polyphase transfer matrix [START_REF] Vaidyanathan | Multirate systems and filter banks[END_REF]. The latter matrix belongs to the ring C[z, z -1 ] M ×N of Laurent polynomial matrices of dimensions M × N . We emphasize that we do not look for any inverse MIMO filter, but for an inverse

polynomial matrix in C[z, z -1 ] N ×M instead.
In other words, we aim at obtaining a (non-necessarily causal) FIR synthesis FB.

A first answer to this FIR invertibility problem can be conveyed through the study of the Smith

McMillan form of a polynomial matrix [START_REF] Kailath | Linear Systems[END_REF], [START_REF] Vaidyanathan | Multirate systems and filter banks[END_REF], but unfortunately this decomposition is quite costly.

Park, Kalker and Vetterli also devised a method using Gröbner bases [START_REF] Park | Gröbner bases and multidimensional FIR multirate systems[END_REF] to study the invertibility of polynomial matrices which is applicable to the general multidimensional case. We describe here an alternative cost-effective method in the one-dimensional case. The following result gives a necessary and sufficient condition for a matrix to be left invertible, and thus, for the existence of such an inverse system:

let

H[z] ∈ C[z, z -1 ]
M ×N be a polynomial matrix with M > N . The following conditions are equivalent:

1) H[z] is "coprime", which means that the determinants of the maximum minors (sub-matrices of size N × N ) are mutually relatively prime.

2) H[z] is left invertible in the sense that there exists

H[z] ∈ C[z, z -1 ] N ×M such that H[z]H[z] = I N .
A proof of this result can be found in [START_REF] Fornasini | nD polynomial matrices with applications to multidimensional signal analysis[END_REF] for instance.

The first condition is directly applicable in practice to resolve the left invertibility of the polyphase transfer matrix. Using the following procedure, we can check numerically whether this condition is satisfied:

x Extract a maximal sub-matrix

H e [z] of H[z]. y Compute det(H e [z]
), and determine its set of roots S e .

z Consider another maximal sub-matrix. Remove from S e the elements which are not roots of the determinant of this sub-matrix.

{ Repeat step z until S e = ∅ or all maximal sub-matrices have been extracted.

| If S e = ∅ then the polyphase transfer matrix is left-invertible; otherwise, it is not.

The corresponding algorithm is easily implemented, leading to extract the roots of a single polynomial and check the roots of at most invertible, the number of considered polynomials in practice is usually much smaller than M N -1, this bound being reached only when the matrix is not invertible. Note that in the case of causal filters (i.e.

M N -1 = M ! N !(M -N )! -

both H[z] and H[z]

are polynomial matrices in C[z -1 ] N ×M ), simpler invertibility conditions exist by invoking the so-called column-reduced property [START_REF] Forney | Minimal bases of rational vector spaces, with applications to multivariable linear systems[END_REF], [START_REF] Inouye | A system-theoretic foundation for blind equalization of an FIR MIMO channel system[END_REF]. Also notice that, one of the advantages of this algorithm over other methods is that it can be fully numerically implemented.

B. Computation of an inverse FB

The method proposed in Section III-A only guarantees the existence of a left-inverse, corresponding to an FIR synthesis FB. Since it does not provide a constructive expression, we now perform the actual computation of an inverse polyphase transfer matrix. We assume hereafter that H[z] was proven to be FIR left invertible.

Since the goal is to achieve PR, we search for a matrix

H[z] in C[z, z -1 ] N ×M such that H[z] H[z] = I N
and there exists (p 1 , p 2 ) ∈ N 2 such that the polyphase transfer function of the synthesis FB reads:

H[z] = p2 =-p1 H( )z -.
The resulting overlapping factor of the synthesis filters is p = p 1 + p 2 + 1. When working with Laurent polynomial matrices, these integers p 1 and p 2 are a priori unknown, whereas with polynomial matrices a bound exists [START_REF] Forney | Minimal bases of rational vector spaces, with applications to multivariable linear systems[END_REF]. By rewriting the PR property in block convolutional form, we get the following linear system:

H H = U (7)
where

U = 0 N,p1N , I N , 0 N,(p2+k-1)N ∈ R N ×(k+p-1)N , H = H(-p 1 ), • • • , H(p 2 ) ∈ C N ×pM , (8)
and

H =       H(0) • • • H(k -1) 0 . . . . . . 0 H(0) • • • H(k -1)       ∈ C pM ×(k+p-1)N . (9)
As already mentioned, p 1 and p 2 are unknown, but since the system [START_REF] Malvar | A modulated complex lapped transform and its applications to audio processing[END_REF] The HS property in the synthesis filters is satisfied provided that, considering any symmetric subband indices j f ∈ {0, ..., M -1} and M -1j f , for any coefficients

(y i (n)) 0≤i<M such that y i (n) = 0 if (i, n) = (j f , n f ) or (i, n) = (M -1 -j f , n f ) with n f ∈ Z and, such that y jf (n f ) = y M -1-jf (n f ), a
real-valued signal is reconstructed. The reconstructed signal reads:

x(m) = M -1 j=0 ∞ =-∞ h j (m -N )y j ( ) = h jf (m -n f N )y jf (n f ) + h M -1-jf (m -n f N )y jf (n f ).
A necessary and sufficient condition for

x(m) ∈ R for all y jf (n f ) ∈ C, is that h jf (m -n f N ) = h M -1-jf (m -n f N )
. This condition must be verified for any couple of integers (j f , n f ). The condition on the synthesis filter is then: ∀j ∈ {0, ..., M -1} and ∀n ∈ Z, h j (n) = h M -1-j (n). Using (6), we rewrite the condition as

∀ ∈ {-p 1 , ..., p 2 } , H( ) = H( )J M . ( 10
)
where J M is the M × M counter-identity matrix:

J M =       0 1 . . . 1 0      
.

We have supposed here that the transformed coefficients of a real signal exhibit the HS property. In other words, for any real signal (x(n)) n∈Z , and for any couple (j f , n f ) ∈ {0, ..., M -1} × Z, the output of the analysis FB verifies:

y jf (n f ) = y M -jf -1 (n f )
. This condition can be rewritten:

m h jf (m)x(N n f -m) = m h M -jf -1 (m)x(N n f -m).
Considering a zero input signal x except for one sample, we deduce that

h jf (n) = h M -jf -1 (n), which is equivalent to H( ) = J M H( ). (11)
Hence, if the analysis FB verifies Condition [START_REF] Hassibi | Representation theory for high-rate multiple-antenna code design[END_REF], then the coefficients after decomposition satisfy the HS property.

Remark 1: Consider an invertible HS analysis FB. By inserting [START_REF] Hassibi | Representation theory for high-rate multiple-antenna code design[END_REF] in the PR condition we get:

δ I N = min(p2, ) s=max( -k+1,-p1) H(s)J M H( -s). It implies that if H = H(-p 1 ), • • • , H(p 2 )
is a solution of the linear system (7) then, under the HS hypothesis on the analysis FB,

H 2 = H(-p 1 )J M , • • • , H(p 2 )J M
is also a solution of the linear system. Finally, it follows that the sum:

H 0 = 1 2 ( H + H 2 )
is also a solution. Moreover, this solution verifies Condition (10) by construction.

In other words, we have proved that an invertible HS analysis FB admits at least one HS synthesis FB.

2) Construction method:

We suppose here that the analysis FB was proven invertible and that the matrices H( ) satisfy Condition [START_REF] Hassibi | Representation theory for high-rate multiple-antenna code design[END_REF]. Our objective is to build a synthesis FB possessing both the PR and HS properties. a) First case: M is even: First, we rewrite Conditions ( 10) and ( 11):

(10) ⇔ ∀ ∈ {-p 1 , ..., p 2 } ,      H( ) = H 1 ( ), H 2 ( ) , H 1 ∈ C N ×M and H 2 ∈ C N ×M , H 1 ( ) = H 2 ( )J M (11) ⇔ ∀ ∈ {0, ..., k -1} ,            H( ) =    H 1 ( ) H 2 ( )    , H 1 ∈ C M ×N and H 2 ∈ C M ×N , H 1 ( ) = J M H 2 ( )
with M = M/2. Combining these conditions and the PR property, we get:

δ I N = min(p2, ) s=max( -k+1,-p1) H 1 (s)H 1 ( -s) + min(p2, ) s=max( -k+1,-p1) H 1 (s)J 2 M H 1 ( -s). (12)
Since J 2 M = I M , the previous equation can be seen as the sum of a complex matrix with its conjugate, leading to a real matrix. We deduce that

1 2 δ I N = min(p2, ) s=max( -k+1,-p1) H R 1 (s), -H I 1 (s)    H R 1 ( -s) H I 1 ( -s)    ,
where A R is the matrix of the real part of a matrix A and A I is its imaginary part. We will then define the following matrices:

H s = H R 1 (-p 1 ), -H I 1 (-p 1 ), • • • , H R 1 (p 2 ), -H I 1 (p 2 ) ∈ R N ×pM , (13)
July 20, 2009 DRAFT and

H s =              H R 1 (0) • • • H R 1 (k -1) 0 H I 1 (0) • • • H I 1 (k -1) 0 . . . . . . 0 H R 1 (0) • • • H R 1 (k -1) 0 H I 1 (0) • • • H I 1 (k -1)              ∈ R pM ×(k+p1+p2)N .
b) Second case: M is odd : Similarly to the first case, Conditions ( 10) and ( 11) can be rewritten:

(10) ⇔ ∀ ∈ {-p 1 , ..., p 2 } ,      H( ) = H 1 ( ), c 1 ( ), H 2 ( ) , H 1 ∈ C N ×M and H 2 ∈ C N ×M , H 1 ( ) = H 2 ( )J M and c 1 ( ) ∈ R N (11) ⇔ ∀ ∈ {0, ..., k -1} ,                  H( ) =       H 1 ( ) c 2 ( ) H 2 ( )       , H 1 ∈ C M ×N and H 2 ∈ C M ×N , H 1 ( ) = J M H 2 ( ) and c 2 ( ) ∈ R N with M = (M -1)/2.
Combining these conditions with the PR equation and following the same reasoning as in the previous section, we deduce that

1 2 δ I N = min(p2, ) s=max( -k+1,-p1) H R 1 (s), c 1 (s) √ 2 , -H I 1 (s)       H R 1 ( -s) c2( -s) √ 2 H I 1 ( -s)      
.

Subsequently, we introduce in this case the following matrices:

H s = H R 1 (-p 1 ), c 1 (-p 1 ) √ 2 , -H I 1 (-p 1 ), • • • , H R 1 (p 2 ), c 1 (p 2 ) √ 2 , -H I 1 (p 2 ) ∈ R N ×pM , (14)
and

H s =                    H R 1 (0) • • • H R 1 (k -1) 0 c2(0) √ 2 • • • c2(k-1) √ 2 0 H I 1 (0) • • • H I 1 (k -1) 0 . . . . . . 0 H R 1 (0) • • • H R 1 (k -1) 0 c2(0) √ 2 • • • c2(k-1) √ 2 0 H I 1 (0) • • • H I 1 (k -1)                    ∈ R pM ×(k+p1+p2)N .
July 20, 2009 DRAFT c) Conclusion : In both even and odd options, we solve a linear system of the same size as the one of Section III-B, but with real coefficients in this case. More precisely, with the introduced notations, we have:

H s H s = U s = 1 2 0 N,p1N , I N , 0 N,(p2+k-1)N .
The system is then solved, in the same way as in Section III-B. For increasing values of p (starting with p = 1), for each couple (p 1 , p 2 ) ∈ N 2 such that p = p 1 + p 2 + 1 we try to invert the generated system through a Moore-Penrose pseudo-inversion.

IV. OPTIMIZATION

A. Dimension reduction 1) General case: Before addressing the issue of optimization in itself, let us rewrite the linear system expressing the PR property. The analysis FB is still supposed invertible. Let r be the rank of the matrix H ∈ C (k+p1+p2)N ×pM . We assumed that r < M p (with p = p 1 + p 2 + 1). Performing a Singular Value Decomposition [START_REF] Strang | Introduction to Linear Algebra[END_REF] (SVD) on this matrix yields

H = U 0 Σ 0 V * 0 , where Σ 0 ∈ C r×r is an invertible diagonal matrix, U 0 ∈ C N (k+p-1)×r and V 0 ∈ C M p×r are semi-unitary matrices (i.e. U * 0 U 0 = I r and V * 0 V 0 = I r ). Therefore, there exists U 1 ∈ C N (k+p-1)×(N (k+p-1)-r) and V 1 ∈ C M p×(M p-r) such that [U 0 , U 1 ] and [V 0 , V 1 ]
are unitary matrices. When an inverse polyphase transfer matrix exists, a particular solution to [START_REF] Malvar | A modulated complex lapped transform and its applications to audio processing[END_REF] is

H 0 = H U , where H = V 0 Σ -1 0 U * 0 is the pseudo-inverse matrix of H. Equation (7) is then equivalent to U 0 Σ 0 V * 0 ( H -H 0 ) = 0 N (k+p-1)×N . Since U * 0 U 0 = I r and Σ 0 is invertible, we get: V * 0 ( H -H 0 ) = 0 r×N .
In other words, the columns of H -H 0 belong to Ker(V * 0 ), the null space of V * 0 . Moreover, it can be easily seen that Ker(V * 0 ) is equal to Im(V 1 ). We then obtain the following affine form for H:

H = V 1 C + H 0 , (15)
where

C ∈ C (M p-r)×N .
The construction of a synthesis FB thus amounts to the choice of C. If C = 0 (M p-r)×N , then the obtained synthesis FB is the PI FB. This expression can be further rewritten into a more convenient form for optimization purposes. First, we define the matrices (V j ) j∈{0,...,M -1} by: for all ∈ {-p 1 , . . . , p 2 } and [START_REF] Weiß | Paraunitary oversampled filter bank design for channel coding[END_REF] and ( 8), we can write for all ∈ {-p 1 , ..., p 2 }, i ∈ {0, ..., N -1} and j ∈ {0, ..., M -1}:

n ∈ {0, . . . , M p-r-1}, (V j ) +p1,n = V 1 ( +p 1 )M +j, n , with V 1 = [V 1 (s, n)] 0≤s<M p,0≤n<M p-r . Ac- cording to
H i,j ( ) = M p-r-1 n=0 (V j ) +p1,n C(n, i) + H 0 i,j ( ),
where H i,j ( ) -p1≤ ≤p2 represent the impulse responses of the synthesis FB, H 0 i,j ( ) -p1≤ ≤p2 correspond to the PI solution and C = [C(n, i)] 0≤n<M p-r,0≤i<N . For all j ∈ {0, ..., M -1}, we introduce the matrices H 0 j defined by: H 0 j +p1,i = H 0 i,j ( ) for all ∈ {-p 1 , ..., p 2 } and i ∈ {0, ..., N -1}. We thus obtain

H i,j ( ) = V j C + H 0 j +p1,i . ( 16
)
This equation is used in Section IV-B1 to simplify the optimization problem raised by the design of the synthesis FB.

The above expressions are given in the complex case, but they naturally remain valid in the real case.

This will be illustrated by the first example of Section V-B3a.

2) Symmetric case: In this section, we adapt the results of the previous section to the HS FB case.

The notations used here are similar to those introduced in Section III-C2. It is worth noticing that we can calculate the matrix H directly from H s , as defined in Section III-C2 when M is either even or odd, in the following way:

H = P rc H s (17)
where the matrix P rc ∈ C pM ×pM is the block diagonal matrix built with the block:

   I M -ıI M J M ıJ M   
if M = 2M (even case, as seen in Section III-C2a) and:

      I M 0 -ıI M 0 √ 2 0 J M 0 ıJ M      
if M = 2M + 1 (odd case, as seen in Section III-C2b). By applying once again an SVD on H s , and by following the same steps as in Section IV-A1, we end up with an equation similar to [START_REF] Weiß | Paraunitary oversampled filter bank design for channel coding[END_REF]:

H s = V 1 C + H s 0 . ( 18
)
Note that, according to the properties of the SVD, the matrix C is now real-valued. By noticing that H 0 = P rc H s 0 and setting W 1 = P rc V 1 , we finally obtain:

H = W 1 C + H 0 . ( 19
)
We next define the matrices (W j ) 0≤j≤M -1 : for all ∈ {-p 1 , . . . , p 2 } and n ∈ {0, . . . , M pr -1}:

(W j ) +p1,n = W 1 ( + p 1 )M + j, n . Using [START_REF] Borries | On filter banks with rational oversampling[END_REF] as in Section IV-A1, we get: Our goal is to optimize the filter shape given by the coefficients h of the synthesis FB, subject to the perfect reconstruction property. According to the results in Section IV-A, it is possible to represent the coefficients in the general case by using [START_REF] Cvetković | Tight Weyl-Heisenberg frames in 2 (R)[END_REF]. The optimization favorably takes place in the reduced dimension space the matrix C belongs to (compared with the dimension of the space of the coefficients of h), thus allowing us to reformulate the optimization under a perfect reconstruction constraint as an unconstrained problem. In this context, the generic cost function form we consider is:

H i,j ( ) = W j C + H 0 j +p1,i . (20)
J( h) = J(C) = M -1 j=0 V j C + H 0 j 2 Kj V j C + H 0 j 2 Λ .
Hereabove, the following notation has been employed:

∀A ∈ C N ×p , A 2 K = (i,i , , ) A i, A i , K(i, i , , ),
where K and Λ are (N ×N ×p×p) kernels. Moreover, we assume here that A K represents a semi-norm over C N ×p and it is thus real non-negative. Let K be the matrice defined by K i+ N,i + N = K(i, i , , )

for all ( , ) ∈ {0, ..., p -1} 2 and (i, i ) ∈ {0, ..., N -1} 2 . Without loss of generality, this matrix can be taken positive semi-definite, which implies that K i+ N,i + N = K i + N,i+ N and, thus, K(i, i , , ) = K(i , i, , ). We deduce the following expression:

A 2 K = (i,i , , ) A i, A i , K(i, i , , ) = (i,i , , ) A i, A i , K(i , i, , ).
This relation will be used to simplify some equations in Section IV-C and Appendix C. We finally notice that K is a positive definite Hermitian matrix if and only if . K is a norm.

2) Impulse responses optimization:

A first objective is to obtain impulse responses ( h j ) 0≤j<M for the synthesis filters well-localized, around some time-indices (m j ) 0≤j<M . We now explain the link between the cost function form introduced in the previous section and the previously described dimension reduction to further simplify the problem.

The considered cost function is the following:

J t ( h) = M -1 j=0 ω t,j m |m -m j | α h j (m) 2 m h j (m) 2 ,
July 20, 2009 DRAFT with α ∈ R * + and weights (ω t,j ) 0≤j<M ∈ (R + ) M such that M -1 j=1 ω t,j = 1.

If α = 2 and m j = m m hj (m) 2 m hj(m)
2 , then J t ( h) represents a weighted sum of the standard temporal dispersions measuring the time localization of a filter h j [START_REF] Flandrin | Time-frequency and time-scale analysis[END_REF]. Combined with (6), we get:

J t ( h) = M -1 j=0 ω t,j p2 =-p1 N -1 i=0 | N -i -m j | α h j ( N -i) 2 p2 =-p1 N -1 i=0 h j ( N -i) 2 = M -1 j=0 ω t,j p2 =-p1 N -1 i=0 | N -i -m j | α H i,j ( ) 2 p2 =-p1 N -1 i=0 H i,j ( ) 2
.

We now introduce the kernels K t j and Λ defined by

K t j (i, i , + p 1 , + p 1 ) = ω t,j | N -i -m j | α δ i-i δ -, (21)
Λ(i, i , + p 1 , + p 1 ) = δ i-i δ -,
for all j ∈ {0, . . . , M -1}, ( , ) ∈ {-p 1 , . . . , p 2 } 2 and (i, i ) ∈ {0, . . . , N -1} 2 . Using ( 16) we write:

p2 =-p1 N -1 i=0 H i,j ( ) 2 = V j C + H 0 j 2 Λ and ω t,j p2 =-p1 N -1 i=0 ( N -i -m j ) 2 H i,j ( ) 2 = V j C + H 0 j 2 K t j .
Hereabove, . Λ reduces to the Frobenius norm. Finally, we deduce that

J t ( h) = M -1 j=0 V j C + H 0 j 2 K t j V j C + H 0 j 2 Λ = J t (C).
The constrained minimization of J t is then reexpressed as the unconstrained minimization of J t .

3) Frequency response optimization: We proceed similarly to the previous section, for a different cost function J f ( h). Our goal, dual to that in the previous section, is now to regularize the frequency responses of the synthesis FB by concentrating the frequency response of each filter h j around some frequency f j . This is achieved by minimizing

J f ( h) = M -1 j=0 ω f,j 1/2+fj -1/2+fj |ν -f j | α h j [ν] 2 dν 1/2+fj -1/2+fj h j [ν] 2 dν ( 22
)
where

α ∈ R * + , (ω f,j ) 0≤j<M ∈ (R * + ) M with M -1 j=0 ω f,j = 1 and, h j [.]
is the frequency response of the j th synthesis filter, defined as

∀ν ∈ [-1/2, 1/2[, h j [ν] = p2 =-p1 N -1 i=0 H i,j ( )e -2ıπ(N -i)ν . July 20, 2009 DRAFT When f j = 1/2 -1/2 ν h j [ν] 2 dν 1/2 -1/2 h j [ν] 2 dν
, the cost function J f ( h) represents a classical weighted frequency dispersion measure for the synthesis filters. We then define the kernel

K f j (i, i , + p 1 , + p 1 ) = ω f,j 1/2+fj -1/2+fj |ν -f j | α e -2ıπ(N ( -)-(i-i ))ν dν = ω f,j 1/2 -1/2 |ν| α e -2ıπ(N ( -)-(i-i ))(ν+fj) dν, (23)
with

(i, i , , ) ∈ {0, ..., N -1} 2 × {-p 1 , ..., p 2 } 2 .

Remark 2:

The examples provided in Section V-B3 are obtained with α = 2. In this case, the explicit expression of the kernel becomes:

K f j (i, i , + p 1 , + p 1 ) =        ω f,j 12 if i = i and = ω f,j (-1) N ( -)-(i-i ) e -2ıπ(N ( -)-(i-i ))fj 2π 2 (N ( -) -(i -i )) 2 otherwise with (i, i , , ) ∈ {0, ..., N -1} 2 × {-p 1 , ..., p 2 } 2 .
Combining these notations and ( 16), we have

ω f,j 1/2+fj -1/2+fj |ν -f j | α h j [ν] 2 dν = V j C + H 0 j 2 K f j .
Invoking Plancherel's theorem and the kernel Λ defined in Section IV-B2, we obtain:

1/2+fj -1/2+fj h j [ν] 2 dν = p2 =-p1 N -1 i=0 H i,j ( ) 2 = V j C + H 0 j 2 Λ .
Finally, substituting these expressions in [START_REF] Tanaka | A direct design of oversampled perfect reconstruction FIR filter banks of 50%-overlapping filters[END_REF] yields

J f ( h) = M -1 j=0 V j C + H 0 j 2 K f j V j C + H 0 j 2 Λ = J f (C).
Once again, the constrained optimization problem has been reformulated as an unconstrained one.

C. Gradient optimization

The constrained optimization problem being turned into an unconstrained minimization, we now provide more details about the minimization algorithm we employ. In this work we have used a simple gradient algorithm with an adaptive step µ n . The algorithm can be summarized as follows:

x Initialization: C 0 = 0, n = 0.

y µ n = 1 z Computation of D n = ∇ J(C n ). July 20, 2009 DRAFT { While J(C n -µ n D n ) ≥ J(C n ), set µ n ← 1 1 µn +1 . | C n+1 = C n -µ n D n .
} If C n+1 -C n > then increment n and go to step y.

The step-size µ n used here remains large as long as the algorithm is getting closer to a local minimum (in other words, as long as J(C n+1 ) < J(C n )). It is only adapted (reduced) to prevent the criterion from increasing. The initialization with C 0 = 0 entails that we consider the pseudo-inverse synthesis FB as the starting point for the algorithm. In practice, was set to 10 -13 .

Other step selection strategies exist: constant or optimal steps, steps satisfying Wolfe or Armijo conditions [START_REF] Nocedal | Numerical optimization[END_REF], [50]. The method used in this work is easy to implement and is well-suited to the different cost functions we have considered, while keeping a reasonable complexity.

As the cost functions considered in this work are not convex, there is no theoretical guarantee that the algorithm converges to a global minimum. Yet, as is shown in Section V, initializing this method with the PI synthesis FB provides quite good results and extensive simulations have confirmed this good behaviour.

The expression of the gradient for the general cost function is given in Appendix A and is next applied to J t and J f in Appendix B.

D. Optimal solution in the symmetric case 1) Cost functions:

Using the same notations as in Section IV-B, in the HS case, the following form of the cost function is found:

J s ( h) = J s (C) = M -1 j=0 W j C + H 0 j 2 Kj W j C + H 0 j 2 Λ .
As in the general case, [START_REF] Borries | Linear phase oversampled filter banks[END_REF] has been used to transform the constrained optimization problem on h into an unconstrained minimization problem on C. 20) is very similar to [START_REF] Cvetković | Tight Weyl-Heisenberg frames in 2 (R)[END_REF]. We consequently define the cost functions in the HS case following the same approach as in Sections IV-B2 and IV-B3. Thus, the following functions are considered:

2) Examples of cost functions: Equation (

J ts (C) = M -1 j=0 W j C + H 0 j 2 K t j W j C + H 0 j 2 Λ , July 20, 2009 DRAFT
to concentrate the time localization of impulse responses, and:

J fs (C) = M -1 j=0 W j C + H 0 j 2 K f j W j C + H 0 j 2 Λ ,
to enhance the frequency selectivity of the filters. Their gradients are provided in Appendix C.

V. EXAMPLES

As emphasized in the introduction, a wide variety of filter banks and design choices can be made. In this section, we have chosen to work with three different examples exhibiting interesting properties and allowing us to show the benefits incurred in the proposed inversion and optimization methods.

A. Considered filter banks 1) Real Lapped Transforms:

The study, developed for the general complex case, remains fully applicable to the design of real filter banks. As an illustration, we first consider real lapped transforms introduced in the middle of the 90s under the name of GenLOT (generalized linear-phase lapped orthogonal transform) [START_REF] De Queiroz | The GenLOT: generalized linear-phase lapped orthogonal transform[END_REF]. Those transforms generalize the DCT (Discrete Cosine Transform) and the LOT (lapped orthogonal transform).

To illustrate the inversion method, we have chosen a GenLOT with M = 16 filters of 32 coefficients.

This FB is invertible, in a non standard oversampled use, with parameters N = 8, k = 4 and k = 2. Its impulse and frequency responses are represented in Figure 2. This FB is real and does not satisfy the HS condition. By using the method described in Section III-B, we find p 1 = 3 and p 2 = 0 (hence p = 4).

The frequency and impulse responses of the synthesis FB computed with the pseudo-inverse are shown on Figures 3(a) and 4(a).

2) Modulated complex lapped transform:

We now consider another analysis FB based on a windowed generalized Fourier transform, corresponding to a modulated complex lapped transform (MCLT). This family of FB has been used by Kingsbury [START_REF] Young | Frequency-domain motion estimation using a complex lapped transform[END_REF] or Malvar [START_REF] Malvar | A modulated complex lapped transform and its applications to audio processing[END_REF] for applications in video as well as audio processing. The analysis impulse responses are:

h i (n) = E(i, n)h a (n),
where

E(i, n) = 1 √ k N e -ı(i-k N 2 + 1 2 )(n-kN 2 + 1 2 ) 2π k N ,
and (h a (n)) 1≤n≤kN is an analysis window. In this paper, we consider two analysis windows. is a standard sine window, employed for example in [START_REF] Malvar | A modulated complex lapped transform and its applications to audio processing[END_REF], [START_REF] Young | Frequency-domain motion estimation using a complex lapped transform[END_REF]. The second (h a2 (n)) 1≤n≤kN , corresponds to a zero-phase low-pass filter with cutoff frequency 2π/(kN ), built from a Kaiser window. This window, with better tapering than h a1 , was used for instance in [START_REF] Mansour | On the optimization of oversampled DFT filter banks[END_REF]. It is interesting to note that this analysis FB family, with both analysis windows, satisfies Condition [START_REF] Hassibi | Representation theory for high-rate multiple-antenna code design[END_REF]. In other words, it can be used to illustrate our approach in the HS case. The method from Section III-A was employed to verify the invertibility on this FB, with both analysis windows and parameters N = 8, k = 3 and k = 7/4. We then compute a first synthesis FB with the PI method of Section III-B. For the analysis FB with h a1 window, the minimal parameters p 1 = 2 and p 2 = 0 were obtained. The frequency response of this synthesis FB is represented in Figure 5(a). In the h a2 case, the minimal parameters p 1 = 2 and p 2 = 0 were, once again, found when applying the method of Section III-B. An HS synthesis FB is then derived from this filter bank using the method of Section III-C2 to directly build an HS synthesis FB. The frequency and impulse responses of the resulting synthesis FBs, in the h a2 case, are shown in Figures 6 and7, respectively. Figure 6(a) shows that synthesis filters present a symmetric behavior for their coefficients (in other words, they have a linear phase) while the synthesis FB in itself is not HS. We also notice that the frequency selectivity or time-frequency localization of the filters obtained through the pseudo-inverse methods is not satisfactory.

B. Optimization examples 1) Kernel parameters:

a) Temporal kernel K t j : It is defined by [START_REF] Gan | Oversampled linear-phase perfect reconstruction filterbanks: Theory, lattice structure and parameterization[END_REF]. The parameters m j define the (temporal) positions around which the impulse responses of the j th filter should be concentrated. To obtain well tapered filters, we need to concentrate the impulse responses around the middle of the filter support. Therefore, the same parameter was used for all filters. The support of the filters being

{-p 1 N -N + 1, ..., p 2 N },
we have chosen m j as

∀0 ≤ j < M, m j = m = p 2 N + 1 -p 1 N -N 2 .
In our design example, α has been set to 2.

b) Frequency kernel K f j : It is defined by [START_REF] Riel | Lifting-based design and implementation of oversampled paraunitary modulated filter banks[END_REF]. The parameters f j represent the reduced frequencies around which we want to concentrate the frequency responses of the synthesis filters. More precisely, we chose f j such that it is centered inside the bandwidth of the analysis filter h j . The exponent α has been set to 2. c) Weight parameters: In the proposed cost functions, the parameters ω t,j and ω f,j control the relative importance of the different filters in the optimization process. For the following examples we have chosen equal weights:

∀j ∈ {0, ..., M -1} , ω t,j = ω f,j = 1 M .
In other words, we aim at obtaining synthesis filters with similar behavior.

2) Computation time:

In Section IV-A, we have seen how to parameterize the system and thus how to reduce the dimension of the optimization problem. To evaluate the gain resulting from this parameterization, Matlab programs were written to compare the solutions of the constrained problem, using function fmincon, with the solutions of the unconstrained problem, using function fminunc and using the gradient method explained in Section IV-C. The two functions fmincon and fminunc were chosen as examples of optimization implementation, while the gradient procedure can be easily applied in different languages without requiring Matlab. These programs were tested with the analysis July 20, 2009 DRAFT FB introduced in Section V-A2 with the h a1 window and the following parameters: overlap factor k = 3, redundancy k = 7/4 and downsampling N ∈ {4, 8, 16}. The cost function used was J t (as defined in Section IV-B2). Table I shows the computation time for the different methods on a computer with 2.16GHz Intel Core2 T7400 CPU and 2Gb of RAM. identical synthesis FBs. The computation times are however very different: more than two hours (with N = 16) for the constrained optimization against a few seconds for the unconstrained optimizations. We can also that the gradient algorithm is as fast as the fminunc Matlab function. This shows that the optimization method can be easily implemented, through a gradient algorithm, with no performance loss and without having to resort to the fminunc Matlab function 1 . In other words, this last result indicates that in some applicative contexts in which Matlab is not available the optimization method can still be easily and efficiently implemented. We observe that the frequency responses after optimization exhibit more regularity and an improved selectivity. The proposed cost functions take into account all synthesis filters at once. It therefore interesting to look more closely at each filter independently and determine whether the optimization leads to better results. In Table II, the frequency dispersion of each filter is reported before and after optimization with cost function J f . In this case, the overall frequency dispersion of the optimized filters has been noticeably improved and spread variability has been drastically reduced. b) Results in the symmetric case: The optimization procedure was next applied in the HS case to the FB of Section V-A2 (with analysis window h a2 ). In this case, the cost functions J ts and J fs were employed. Once again, the following parameters were used: N = 8, k = 3 and k = 7/4. Figures 8 and9 show the optimization results. We observe that the optimizations with these two cost functions lead to FBs with different characteristics: as expected, with J ts the impulse responses are better concentrated than with J fs and, conversely, with J fs the frequency selectivity is better than with J ts .

4) Comparison:

To conclude this example section, we propose a comparison with an existing filter bank design. We have chosen to compare our design methodology with the filter banks used in [START_REF] Malvar | A modulated complex lapped transform and its applications to audio processing[END_REF], [START_REF] Young | Frequency-domain motion estimation using a complex lapped transform[END_REF].

In these works, the considered FBs correspond to a modulated complex lapped transform with overlap factor k = 2 and redundancy k = 2. For this application, our choice of N = 8 results in the filters shown in [START_REF] Young | Frequency-domain motion estimation using a complex lapped transform[END_REF]. The synthesis filter bank is then built with a method equivalent to the weighted overlap-add technique. We have applied the methods proposed in this work to compute an optimized synthesis filter bank using the cost function J ts . In Table III, the time dispersion of each synthesis filter computed as explained in [START_REF] Young | Frequency-domain motion estimation using a complex lapped transform[END_REF] h j j∈{0,...,15} and after optimization h opt j j∈{0,...,15}

are reported as well as the value of the cost function J ts . The time dispersion was clearly reduced with the proposed method.

VI. CONCLUSION

In this paper, we have proposed a method to test that a given oversampled FIR analysis FB is FIR invertible and a method to compute an optimized inverse FB. The optimization was performed for a class of cost functions allowing either to emphasize the time localization or the frequency selectivity of the filters. By rewriting the system defining the synthesis FB, we were able to parameterize the synthesis filters for a given filter length. This parameterization was then used to convert the constrained optimal synthesis problem into an unconstrained one, which can be solved with a simple gradient algorithm.

The FB considered here are one-dimensional; it would be interesting to study how the proposed methods could be extended to the multidimensional case. Another perspective could be to study the case of FBs admitting an IIR left inverse that can be approximated using a FIR FB with very long support. (V j ) i,m δ -n (V j C + H 0 j ) i , + (V j ) i ,m δ -n (V j C + H 0 j ) i, K j (i, i , , ) + ı ı(V j ) i,m δ -n (V j C + H 0 j ) i , -ı(V j ) i ,m δ -n (V j C + H 0 j ) i, K j (i, i , , ) = 2 i,i , (V j ) i ,m (V j C + H 0 j ) i, K j (i, i , , n).

From this result, we deduce that

∇ J(C) m,n = 2 M -1 j=0 i,i , (V j ) i ,m (V j C + H 0 j ) i, (β j K j (i, i , , n) -α j Λ(i, i , , n)) β 2 j , (24)
with α j = V j C + H

EXAMPLES OF GRADIENTS

A first example is the calculation of the gradient of the cost function J t . Applying [START_REF] Harteneck | Design of near perfect reconstruction oversampled filter banks for subband adaptive filters[END_REF] to the kernels (K t j ) 0≤j<M , we get: ∂f ∂C m,n = 2ω t,j i (V j ) i,m (V j C + H 0 j ) i,n (Γ j ) i,n

= 2ω t,j V * j (Γ j (V j C + H 0 j )) m,n
, where (Γ j ) i, +p1 = | N -i -m j | α for all 0 ≤ i < N and -p 1 < ≤ p 2 . The symbol represents the Hadamard product (or pointwise matrix product). Finally we obtain:

∇ J t (C) = 2 M -1 j=0 V * j ((ω t,j β j Γ j -α j 1) (V j C + H 0 j )) β 2 j ,
where 1 i, = 1 for all 0 ≤ i < N and 0 ≤ < p.

The same study can be carried out for the cost function J f , with kernels (K f j ) 0≤j<M . Rewriting the result under a matrix form does not simplify the final expression in this case. Hence, the gradient reads: (W j ) i,m δ -n (W j C + H 0 j ) i , + (W j ) i ,m δ -n (W j C + H 0 j ) i, K j (i, i , , ).

∇ J f (C) m,n = 2 M -1 j=0 i,i , (V j ) i ,m (V j C + H 0 j ) i, (β j K f j (i, i , , n) -α j δ i-i δ -n ) β 2
By using this expression and the relation K j (i, i , , ) = K j (i , i, , ), we deduce the gradient of the cost function J s :

∇ J s (C) m,n = 2Re   M -1 j=0
i,i , (W j ) i,m (W j C + H 0 j ) i , (β j K j (i, i , n, )α j Λ(i, i , n, ))

β 2 j   , (25)
with α j = W j C + H i,i , (W j ) i,m (W j C + H 0 j ) i , (β j K f j (i, i , n, )α j δ i-i δ n-) β 2 j    .

Fig. 1 .

 1 Fig. 1. Oversampled M -channel filter bank.

1 )

 1 General form for the cost functions: Depending on the desired properties for the synthesis FB, several cost functions can be employed. We first propose a generic cost function formulation and then provide practical examples based on the filter time or frequency spread, respectively.

1 ,Fig. 2 .

 12 Fig. 2. (a) Impulse and (b) frequency responses of a GenLOT analysis FB.

Fig. 3 .

 3 Fig. 3. First example (with the GenLOT FB of Section V-A1): frequency response of the synthesis FB obtained (a) through the pseudo-inverse method and (b) after optimization with cost function Jt.

Fig. 4 .

 4 Fig. 4. First example: impulse response of the synthesis FB obtained (a) through the pseudo-inverse method and (b) after optimization with cost function Jt.

Fig. 5 .

 5 Fig. 5. Second example (in the MCLT case with window ha 1 ): frequency responses of synthesis filters (a) before and (b) after optimization with the cost function J f .

Fig. 6 .

 6 Fig. 6. Modulus of the impulse responses of the synthesis FBs (in the MCLT case with ha 2 window): (a) pseudo-inverse and (b) symmetric version with the method of Section III-C2.

Fig. 7 .

 7 Fig. 7. Frequency responses of the synthesis FBs (in the MCLT case with ha 2 window): (a) pseudo-inverse and (b) symmetric version with the method of Section III-C2.

3 )

 3 Examples of optimized FBs: In this section, we present optimization results 2 obtained with the different FBs introduced in Section V-A and using the different proposed cost functions. a) General case: We have applied the optimization method on the real FB introduced in Section V-A1 with parameters: N = 8, k = 4 and k = 2. The employed cost function is J t . The result is shown in Figure 4(b), the coefficients before optimization (obtained with the pseudo-inverse method) are also displayed. It is clear that the impulse responses of optimized filters are better concentrated around the middle of the support. Figure 3 illustrates that the gain in time localization does not entail a too severe loss in frequency selectivity of the optimized filters. A second optimization example is given using an MCLT FB with analysis window h a1 and parameters N = 8, k = 3 and k = 7/4. The resulting frequency responses after optimization with cost function J f are represented in Figure 5(b).

Fig. 8 .

 8 Fig. 8. Third example (in the MCLT case with window ha 2 ): modulus of the impulse responses of synthesis filters (a) before and after optimization (b) with the cost function Jts and (c) with J fs .

Fig. 9 .

 9 Fig. 9. Third example (in the MCLT case with window ha 2 ): frequency responses of synthesis filters (a) before and after optimization (b) with the cost function Jts and (c) with J fs .

j 2 Kj.

 2 appendix, we study the gradient of J (as defined in Section IV-B1) with respect to C. We first need to calculate the gradient of f (C) = V j C + H 0 The matrix C being complex, we have ∂f ∂C

0 j 2

 2 Kjand β j = V j C + H

j 2 Kj

 2 THE HS CASE Similarly to Appendix A, we first compute the gradient of f (C) = W j C + H 0 with respect to the matrix C, the only difference being that the matrix C is now real: ∂f ∂C m,n = i,i , ,

0 j 2 Kj and β j = W j C + H 0 j 2 Λ

 22 , for all 0 ≤ j < M . Using[START_REF] Wilbur | Efficient design of oversampled NPR GDFT filter banks[END_REF], the calculation of the gradient of J ts yields∇ J ts (C) = 2Re   M -1 j=0 W * j ((ω t,j β j Γ jα j 1) (W j C + Hwhere Γ j is defined as in Appendix B. For the second cost function we find ∇ J fs (C)

  1 polynomials. If the polyphase matrix is left

	July 20, 2009	DRAFT

  is supposed invertible, at least a couple of integers (p 1 , p 2 ) solving the system exists. The values of p 1 and p 2 are actually obtained

	C. Hermitian symmetric case
	1) Symmetry conditions: It is well known that the Fourier transform of a real signal is Hermitian
	Symmetric (HS): its frequency decomposition is symmetric for the real part and anti-symmetric for the
	imaginary part. Conversely, if the coefficients are HS in the frequency domain, then the reconstructed
	signal is real. This property is very useful for real data filtering, which often consists of removing or
	thresholding coefficients in the frequency domain before reconstructing. Securing the reconstruction of
	real-valued signals from the transformed coefficients is thus a desirable property. In this section, we study
	the HS case and its effects on the methods proposed in the previous sections.
	by increasing the value of p and looking for every couple satisfying p = p 1 + p 2 + 1, starting with
	p = 1. Hence, for a given p, we consider all (p 1 , p 2 ) in {(p -1, 0), (p -2, 1), ..., (0, p -1)}. The first
	p allowing a Moore-Penrose pseudo-inverse [46] solution to (7) provides an inverse polyphase transfer
	matrix of minimum order.
	July 20, 2009	DRAFT

TABLE I COMPUTATION

 I TIME TO OPTIMIZE A SYNTHESIS FB WITH DIFFERENT METHODS USING MATLAB.

		N = 4 N = 8 N = 16
	optimization (with fmincon)	1.2s	120s	8800s
	Unconstrained optimization (with fminunc)	0.04s	0.7s	8s
	optimization (gradient algorithm)	0.06s	0.6s	7s
	A first interesting result is that all three methods, starting from the same FB, converge to almost
	July 20, 2009			DRAFT

TABLE II FREQUENCY

 II DISPERSION OF THE SYNTHESIS FILTERS OPTIMIZED WITH COST FUNCTION J f .

	Filter Freq. disp.	Filter Freq. disp.
	h0	0.0290	h opt 0	0.0111
	h1	0.0851	h opt 1	0.0110
	h2	0.0569	h opt 2	0.0109
	h3	0.0606	h opt 3	0.0112
	h4	0.0658	h opt 4	0.0110
	h5	0.0596	h opt 5	0.0109
	h6	0.0363	h opt 6	0.0111
	h7	0.0156	h opt 7	0.0111
	h8	0.0411	h opt 8	0.0109
	h9	0.0231	h opt 9	0.0110
	h10	0.0508	h opt 10	0.0112
	h11	0.0499	h opt 11	0.0110
	h12	0.0574	h opt 12	0.0109
	h13	0.0521	h opt 13	0.0111
	Sum	0.6833		0.1544
	July 20, 2009			DRAFT

TABLE III TIME

 III DISPERSION OF THE SYNTHESIS FILTERS OPTIMIZED WITH COST FUNCTION Jts.

	Filter	Time disp.	Filter	Time disp.
	h0, h15	21.25	h opt 0 , h opt 15	2.4152
	h1, h14	21.25	h opt 1 , h opt 14	2.1064
	h2, h13	21.25	h opt 2 , h opt 13	2.3424
	h3, h12	21.25	h opt 3 , h opt 12	2.5516
	h4, h11	21.25	h opt 4 , h opt 11	2.5516
	h5, h10	21.25	h opt 5 , h opt 10	2.3424
	h6, h9	21.25	h opt 6 , h opt 9	2.1064
	h7, h8	21.25	h opt 7 , h opt 8	2.4152
	Jts	340		37.6626

July 20, 2009 DRAFT

This fairly sophisticated function uses an interior-reflective Newton method[START_REF] Coleman | On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds[END_REF].

A matlab toolbox for FB optimization is available here: http://www.laurent-duval.eu/misc-research-codes.htmlJuly 20, 2009 DRAFT


Théo Rogliano

Guillermo Polito
email: guillermo.polito@univ-lille.fr

Pablo Tesone

Virtualization for porting programs or tools to solve a puzzle

Keywords: Migration, modularity, virtualization

Migrating programs between language versions is an endeavour task. A developer writes a program in a particular version of a language and cannot foresee future language changes. In this article, we explore a solution to gradual program migration based on virtualization in the programming language level. Our language virtualization approach adds a backwards-compatibility layer on top of a recent language version, allowing developers to load and run old programs on the more recent infrastructure. Developers are then able to migrate the program to the new language version or are able to run it as it is. Our virtualization technique is based on a dynamic module implementation and code intercession techniques. Migrated and non-migrated parts co-exist in the meantime allowing an incremental migration procedure. We validate it by migrating legacy Pharo programs, MuTalk and Fuel.

Introduction

Migrating programs is a complex task. A developer writes her programs targeting a version of a programming language. As languages, libraries and frameworks evolve, programs using them become obsolete. She tries to keep her programs as much compatible as possible but it is not always possible or straightforward [START_REF] Robbes | How Do Developers React to API Deprecation?: The Case of a Smalltalk Ecosystem[END_REF][START_REF] Wu | Aura: a hybrid approach to identify framework evolution[END_REF]. Changes in the language may break her programs. For example, in Pharo 2 there was a trait named TBehavior whereas now it does not exist anymore. Programs using that trait are now broken. Moreover, this problem is not exclusive to program forward-porting (Pharo2 -> Pharo7) but also to back-porting (Pharo7 -> Pharo2) and to porting between language dialects (Squeak -> Pharo).

When a language evolves enough, the differences are so important that it becomes impossible to execute pieces of code written in an old version of the language. We identified the following evolutions provoking incompatible code (Section 2): Syntax changes. Changes in the syntax make programs that were valid for one version, invalid in another.

IWST '19, July, 2019, Cologne, Germany 2019.

Standard Library changes. Changes in the classes of the standard library invalidate the code that uses it e.g., methods or classes removed, or methods with modified semantics. Meta model changes. Reflective languages expose their meta model to the programs [START_REF] Rivard | Smalltalk: a Reflective Language[END_REF]. If the meta model changes from one version to another, programs using it are not able to execute correctly anymore.

We explore the problems of program migration using a virtualization approach. Virtualization is well-known in Operating System (OS) and the problem it solves is similar to ours. For example, Games running in Windows XP do not run natively on Windows 10 due to different kernel infrastructure, file system and so on. Windows uses virtualization in the form of a compatibility layer to solve this issue. The technique consists in interposing a layer between a program and the OS, called hypervisor. The role of the hypervisor is to be an adapter: if the behavior is present it transmits calls to the OS else it adapts them to make them compatible with the new API.

We want to achieve the same results with a programming language instead of an OS. Meaning interposing a virtualization layer between a program and a language in order to run old programs in a newer version of the language.

In this goal, we present a set of techniques required to be able to load and run programs intended for older versions of the host language (Section 3). We implemented the virtualization layer through the use of dynamic modules and metalinks for code rewriting. Once the program is loaded, developers are able to update the program to the new language version or are able to run it as it is using the virtualization layer. We validate the chosen infrastructure with different migrating scenarios of Pharo programs (Section 5).

Contribution. The contribution of this paper is:

1. the design of a dynamic module system that allows us to load partially broken code; 2. the identification of a set of migration problems and a corresponding set of intercession techniques to make them compatible to recent systems transparently; 3. an experience report on migrating two real-world libraries written from 7-9 years. Successfully loaded and running. This is the state we want the program to be. Successfully loaded but not running. The program was loaded but some unexpected bugs appear. They make the program unusable. Since the program is loaded the developer is able to debug it. She changes the source code of the program thus making it incompatible again with the version it was conceived for. Unloadable. The program cannot be loaded. In order to correctly load the program, the developer should debug the loading process. Once the incompatibilities are discovered, the program source code is modified to comply with the newer language version. Finally, the program is loaded and it arrives to one of the previous state. The 2 last cases are the problematic ones and are due to language changes. We identified these changes through examples:

Syntax changes

Syntax changes break the loading of a program. For example, in old Pharo versions, the parser accepted two different syntaxes for assignments, with an underscore a _ 2 or with a colon followed by an equal a := 2. The former gradually disappeared and now is not supported anymore. A program using underscore as assignment is then not understood anymore by the compiler therefore not compiling.

Standard library changes.

Standard library changes break both loading and execution.

We can split them in three categories: Renaming of methods or classes. For example, the method String » includesSubString: changed into String »includesSubstring:. Both the loader (to get the source code) and the program relied on the first one resulting in a doesNotUnderstand during the loading process then during the execution. Removal of methods or classes. The class PackageInfo does not exist anymore breaking program relying on it. Behavioral modifications. A method classNamed:

which was returning nil if the class is absent, now return an Exception. The code expecting a nil in this case is not valid anymore and must catch the exception instead.

Meta-model changes.

Changes in the meta model also occur and break the loading process. As an example, the Trait class has its own hierarchy similar to the one of Class in Pharo 2. Both inherit from Behavior and ClassDescription and use a trait TPureBehavior.

In newer versions of Pharo, this hierarchy has been updated and Trait is now a subclass of Class. The meta side of traits has been reworked making their creation different and any code relying on reflection on traits is obsolete.

Modules for Virtualization

To illustrate with an image we will reuse, an object oriented program can be viewed as a patchwork or a puzzle composed by different entities, namely packages, classes, methods and objects (Figure 1). They are linked by mainly three relationships: subclassing, reference and message-send. Changes are equivalent to loosing some pieces of the puzzles or the way they are linked (Figure 2). Our goal is to make new pieces looking alike the old ones and manage to link them. This is the role of the hypervisor. We propose the introduction of language hypervisor i.e., a compatibility layer at the level of the programming language. This component intercepts all the interactions of the loaded code and the language environment (Figure 3). In this section, we will detail the prerequisites for creating a hypervisor as we intend. The following features are mandatory.

Encapsulating changes

An unwanted side effect of loading an old application is the corruption of the host language environment. For example, the program depends on a different version of the class String. required by the program, replacing its own String. The host environment end up with this version of String which is not compatible with other current components. This is the worst scenario as it breaks all the new libraries and cannot be debugged. We require that the loading process does not affect the host environment. We propose to solve this problem using encapsulation techniques, here in the form of a module system (Figure 4) .

The loading process manages to install version of String

The module system in a nutshell

Our modules are composed by sets of name bindings: Defined. A set containing the entities defined inside the module. Import. A set containing a binding to the entities we used that come from the outside. Undefined. A set containing existing reference in the module to entities not defined nor imported. A module has the same API than the host environment API so tools in the host environment are able to interact with the modules transparently. Also the modules introduce the API needed for its own management such as class creation for itself, import, undefined references and so on. A same name is allowed to appear in different modules, as each of these bindings are independent. Now, with the earlier example, the loading process loads the program in a module. The class String expected by the program will be loaded in the module and will be different than the one of the host environment. Doing so, the incompatibility is isolated into the loaded module. It only affects its execution. Moreover, the developer is able to debug this incompatibility and fix it without affecting the stability of the host environment.

In our proposed solution, we have 3 modules: the hypervisor, the incompatible program under test and the host language environment.

Late class creation

Now that we have the possibility to safely load the program to virtualize, we can take a look on the loading difficulties. The first cause of loading failure are missing classes that prevents us from loading all the hierarchy below them (Figure 5). New classes in Pharo are created by sending the message #subclass: to the superclass as shown in Listing 1.

Point subclass: #ColorPoint instanceVariableNames: 'color' classVariableNames: '' category:''

Listing 1. Example of class creation. The superclass is then in charge of class creation by configuring a class builder with the arguments of the message. In case of a missing superclass, a common scenario, we cannot create all the subclasses, the compiler will not manage to resolve the receiver of the message subclass:. In Listing 1, if we miss the class Point we cannot send the subclass message to it, hence we cannot create the class ColorPoint. A similar problem appears with missing traits, the users of the missing trait will not be configured properly and will certainly be broken. From now on, we will use the term behavior to refer to classes and traits.

To handle this problem, instead of executing a class definition directly; we transform the class definition message-send into an Abstract Syntax Tree. It allows us to detect missing references and to react to them. The class builder has been enhanced to be configurable with such ASTs. For example, a possible solution is to change the superclass of ColorPoint to another class (e.g., Object) in the model and ask the builder to make the class.

This solution works when there is a direct replacement of the missing class. For example, if the class Point has just been renamed. However, if there is no direct replacement we change the intended original definition and it will continue to break the program. So, we require to have a better abstraction for missing entities.

Representation of missing entities

We need to have a representation of missing behaviors for two reasons. As stated above, for resolving, at least in a temporary way, the missing references to those behaviors. The second reason is we want to keep track of the dependencies of the loaded program. We want to load the program under test without modifying it. In term of pieces of a puzzle, we want to keep the expected shape of the pieces (Figure 6). Figure 6. We know a piece is missing. We know it was expecting a yellow part on the top. We create a stub piece (dashed lines) with a yellow part on top and link it, waiting for a better replacement For that purpose, we used stubs classes or traits that will contain the information obtained through static dependency analysis. We call those stubs undefined classes for classes and undefined traits for traits.

We encounter three scenarios: Undefined classes. We create an undefined class by subclassing the class UndefinedClass. We followed the proposal solution of Polito et al [START_REF] Polito | First-Class Undefined Classes for Pharo[END_REF]. This last one redefine basicNew and doesNotUnderstand to prevent instantiation. Undefined traits. UndefinedTrait is a subclass of Trait.

Only the method isDefined is redefined to return false. The creation of undefined trait is the same as for regular trait. A trait composition with an undefined trait becomes undefined. An undefined trait is created when a behavior refer to a missing trait. Undefined traited classes. An undefined traited class is a class that uses an undefined trait. As for undefined classes we prevent the instantiation, here by applying UndefinedTraitedClass on the class side of the target class which redefines basicNew. In a first, we load our program with stub classes (Figure 7). Once we found the corresponding classes, we are able to throw away those stubs easily and replace them.

Dependency management

In some cases, the missing entities are still present in the host environment and are compatible, so we want to use them. In the last example Point is missing in the module containing the program but is present in the host environment. We would like to create a stub for Point and make it inherit from the Point from the host environment. We need then to import the point from the host. This creates a name conflict, we have two times "Point" inside the same module. Point from the host which will stay in the host but is imported and the subclass Point we want to create. For doing so, we suggest aliasing as a solution for this problem. We import Point by giving it another name, an alias. With this mechanism, you can solve the problem in different ways. As show in Figure 8), you can use alias in the program's module or in the hypervisor.

Figure 8. We cannot ask for the first subclass message in the hypervisor. The compiler will resolve it as the same and we will build a circular hierarchy. Instead we rename the Point from the host environment in the import.

With late class creation, undefined entities , modules and aliases we are able to handle all the hindrance for creating a hypervisor.

Virtualizer

The hypervisor is a module containing all that it is necessary for the program to work and be compatible with the newer version of the language. It contains all the modifications and adaptations required to run the program in the host environment without modifying the program nor the language environment.

For example, it contains the undefined entities of the program's module, the program's module import them from the hypervisor. Having the undefined entities in a module allows us to resolve them without modifying the host environment nor the loaded program 9.

Intercession techniques for virtualization

We have 3 strategies for resolving incompatibilities:

Kernel indirection. We still have an entity with the same name in the host environment. We assume some methods are similar and we want to reuse them. We then discard the undefined behavior and declare a new one subclassing the one from the host environment. This way the methods are found with a regular look up. If a method is still missing we create it in the newly created behavior in the virtualization layer. Catching messages. This strategy is for missing classes without similiraties with the ones of the host environment. Our only information is their names, we lost their methods or their layout. In some cases, we still have the opportunity to consult old versions of the language to retrieve the original classes. In the other cases, we have to implement them from start. We define those by subclassing Object. We then run the tests and catch the doesNotUnderstand messages which contains the names of the expected methods. We then implement them by assuming the behavior by testing (similar to Test Driven Developpement [START_REF] Beck | Test Driven Development: By Example[END_REF]). Metalinks. In less common cases, a method still exists but has been renamed. The lookup raises a doesNotUnderstand since the method was not found. We solved the problem with metalinks [START_REF] Röthlisberger | Unanticipated Partial Behavioral Reflection: Adapting Applications at Runtime[END_REF]. Metalinks are used to annotate AST nodes. An annotated AST is expanded, compiled and executed on the fly thanks to the Reflec-tiveMethod/CompiledMethod twin. In our case, using metalinks allows us to replace the execution of the original method with the new one. Even more, we are able to translate different message sends (e.g., the parameters have different orders between the versions).

The source code stays untouched while we still execute the expected method.

Using the virtualizer: an example

In order to use our virtualization solution the developer should perform the following steps.

1. She installs the program that works in a different version of our language inside a module. During the loading of the program, the module system detects missing dependencies and generates undefined entities for them. 2. The virtualizer component transfers the undefined entities to another module that is going to become the hypervisor. We decomposed this in 2 stages, creating the missing dependencies in the hypervisor and then importing them. 3. She runs the program's tests to find out potential problems to solve.

She analyzes and determines the best course of options

(if there is one) to simulate the missing behaviors or the semantic mismatchs applying one of the stated strategies. 5. When all the tests are running and passing, it means for her that the program is operational.

Validation

In order to validate our infrastructure, we port 2 old Pharo programs to a newer version of Pharo.

Methodology. We consider a migration is successful if all the tests are passing. If all the tests are passing, we assume the program is working. Moreover we assume that the tests are passing in the original version of Pharo. We only choose programs with tests for this purpose.

For each of the programs to run we executed the steps stated in Section 4.

Selected Scenarios. We chose 3 scenarios. The first one is an exchange of libraries and serve the purpose of testing the module system. The 2 others are program migrations bringing each different challenges. The migration of MuTalk was chosen for compiler challenges and the migration of Fuel for file and objects creation challenges.

System/container collection

This scenario is our calibration test for modules. We use the system tests (the tests of the current implementation of the language) with an alternate implementations of some collections and, the opposite, use another tests implementation on the system collections. It allows us to assert that we can run tests on independent implementations.

We chose the Stack and LinkedList collections. In the system, the implementation of Stack is based on LinkedList whereas we introduce another implementation, called CT-Stack, using an array (Figure 10). In the modules containing the tests, we decide which implementation to use by redefining the Stack import. Both implementation pass the tests of the other one. For LinkedList the general principle is the same, except two redefinitions of import are done, LinkedList and Link. We noticed that it's possible to mix the system-LinkedList with the CT-Link and vice versa. As for the results, all tests pass with a greenlight. This scenario showed us that the module system produces isolated modules that are freely linkable between each other.

MuTalk

In this scenario, we produce a hypervisor for MuTalk 1 . Mu-Talk a mutation testing framework which last commit dates from 2013. We know the framework was working in old versions of the language (i.e., all tests were green). We chose it because mutation testing implies modification of methods at runtime bringing interesting challenges since there is need to interface with the compiler.

Indeed thanks to this experiment we found a problem when the program is modifying CompiledMethod objects (object representing methods). In order to generate mutants the program asks methods for their source code with the getSource message and modify it. In this scenario the getter for source code has changed to sourceCode and we are stuck with a doesNotUnderstand message (Figure 12). The hypervisor is not involved in the process since the compiler use the CompiledMethod from the system. This problem is a 1 https://github.com/pavel-krivanek/mutalk metamodel problem and allowed us to develop our metalinks strategy.

Figure 12. Scenario with a doesNotUnderstand

In this validation scenario, we identified 45 references to missing entities in the framework. Out of the 45, 30 are classes with the same name that a classes in the system. We used the kernel indirection strategy in those cases. For the others classes we used catching messages strategy. We retrieved methods from Pharo 2 and implemented them in only 3 classes. With our different strategies and thanks to the use of metalinks, we managed to pass 355 out of 362. The 4 failures and 3 errors remaining means some behaviors are still missing or that we did not manage to retrieve the correct semantic for some methods.

Note: We only talked about fixing 33 references out of 45. In the 12 remaining, 4 are global objects referenced with the same name that we still have in the system. We applied something similar to the kernel indirection strategy. The missing 8 references could be the cause of the failing tests or just are present in the program but not used at all (dead code).

Fuel

This scenario is about the virtualization of Fuel2 version 1.6, last comitted in 2012. Fuel is a serialization/materialization program still maintened to this day. Serialization implies I/O management, file management and assumptions on objects. This scenario presents an extra challenge. A newer version of Fuel exists in Pharo and conflicts with our.

This time, we identified 79 missing references. 66 have been resolved using the kernel indirection strategy. We quickly got result in applying the catching message strategy since the first bring us to our first hindrance.

This version of Fuel uses the class FileDirectory which does not exist anymore. We retrieved an implementation of FileDirectory from Pharo 1. In addition, a problem raise up because Fuel relies on an old implementation of streams. To get around this matter we added in the hypervisor a stream compatibility for files using the new implementation of streams and FileReference. Thanks to this workaround we manage to use an erzatz of FileDirectory and so achieve to get back the file management. Fuel uses extension methods on system classes but we do not have any support for them yet. The question is how to handle extension methods without breaking the properties of our modules. For example, an extension method foo expects to be installed in the class String. We do not want it to be installed in the class String of the host environment. Conflicts arise in case of another method foo has been implemented in the meantime. Moreover, by doing so we break our property to keep the host environment intact. Creating a String class in the hypervisor specifically and installing the method does not work. Moreover, similarly to the Compiled-Method problem in MuTalk, the compiler use the String of the host environment for creating strings. Those strings will then not understand the method foo. We plan on handling extension methods in the future.

Finally, Fuel assumes that it works in a single environment, the Smalltalk global environment. It serializes and materializes objects in this environment. Since we installed it in an isolated environment, it does not have free access to the host environment (nowadays Smalltalk) creating incompatibilities. For example, asking Fuel to materialize a LargeInteger fails. Fuel asks the class using reflection to create the object. The class LargeInteger was not an import of Fuel and is not in its environment because it accesses it dynamically. It cannot asks LargeInteger to create the large integer requested. Moreover, Fuel also uses Smalltalk for reflective operations on itself and does not find itself in it provoking incompatibilities too. Reflective libraries require more work in case of their introduction into a module system, for example an installing environment for objects. We also plan on overcoming this problem in future works.

Since the solution is incomplete a lot of tests still fail (19 passes/239 tests) but this scenario learned us a lot on unforeseen difficulties and on a new kind of incompatibilities.

6 Related Work

OS virtualization

A similar solution is used for porting applications in different versions of operating systems. Windows's application compatibility layers (Application Compatibility Toolkit 3 ) attempts to run poorly written applications or those written for earlier versions of the platform. It exposes a layer that emulates the old versions of the API.

FreeBSD includes a Linux compatibility layer (https://www. freebsd.org/doc/handbook/linuxemu.html) that enables binaries built specifically for Linux to run on FreeBSD. FreeBSD also provides other Unix-like system emulations, including 3 https://docs.microsoft.com/en-us/windows/desktop/ win7appqual/application-compatibility-toolkit--act-NDIS, NetBSD, PECoff, SVR4, and different CPU versions of FreeBSD. NetBSD includes similar Unix-like system emulation.

All these virtualization layers are provided by the platform without any support to modify them. Moreover, it is impossible to create extensions to support applications that expect old versions of third party libraries (i.e., libraries that are not part of the operating system).

Application migration

In the literature, solutions exist to help developers in migrating applications. For example, they analyse and extract the required refactorings from one version of the host environment to another [START_REF] Brito | APIDiff: Detecting API breaking changes[END_REF][START_REF] Chow | Semi-automatic update of applications in response to library changes[END_REF][START_REF] Henkel | CatchUp!: capturing and replaying refactorings to support API evolution[END_REF][START_REF] Wu | Aura: a hybrid approach to identify framework evolution[END_REF]. These solutions provide different level of automatic generation of refactorings. For example, Wu et al [START_REF] Wu | Aura: a hybrid approach to identify framework evolution[END_REF] proposes a solution to automatically extract the required refactorings from one version to another of a library comparing the source code and the call graph. Henkel et al [START_REF] Henkel | CatchUp!: capturing and replaying refactorings to support API evolution[END_REF] propose to generate the set of refactorings from capturing the changes performed by the developer. However, they all modify the original program making it incompatible with the older version of the language.

Encapsulation techniques

Solutions exist to encapsulate changes. Allan Wills propose Capsules. Capsules in Fresco [START_REF] Wills | Capsules and Types in Fresco[END_REF] chose to modify the class definition in order to have several times the same name. In their solution, a class owns meta-data such as the author name, the date of creation and the prerequisites of the classes. The idea is to encapsulate a class like data in a network. Modular Smalltalk [START_REF] Wirfs | An Overview of Modular Smalltalk[END_REF], The Java Module System [START_REF] Strniša | The java module system: core design and semantic definition[END_REF] Newspeak [START_REF] Bracha | Modules as Objects in Newspeak[END_REF] and Matriona [START_REF] Springer | Hierarchical Layer-Based Class Extensions in Squeak/Smalltalk[END_REF] offer encpsulation solutions based on name scoping. Some solutions based , this time, on methods scoping [START_REF] Bergel | Classboxes: A Minimal Module Model Supporting Local Rebinding[END_REF] also exist. Bergel et al. analyse module diversity and explain many of them [START_REF] Bergel | Analyzing Module Diversity[END_REF][START_REF] Schärli | Composable Encapsulation Policies[END_REF]. Finally some solutions [START_REF] Denker | Encapsulating and Exploiting Change with Changeboxes[END_REF][START_REF] Lincke | Scoping changes in selfsupporting development environments using context-oriented programming[END_REF] allow the developer to modify the program under migration without affecting the host environment. However, these solutions do not provide a way of performing the changes without affecting the original source code.

Conclusion

In this article, we presented a set of language changes causing problems in loading or running programs. We proposed a solution based on virtualization to migrate programs despite those problems. We designed an infrastructure based on dynamic modules and metalinks in this goal and chose to validate it with real migration scenarios. Although our solution does not yet cover the entire selected scenarios, we always manage to load the programs and have promising results in running almost flawlessly the covered scenarios. The infrastructure needs to take into account extension methods and have a better environment handling. As a future work, we plan to extend our solution to include the missing features. Moreover, we plan to continue using this solution to migrate old application to newer versions of Pharo. Other possible path of evolution is the automatic hypervisor generation using refactoring detection techniques [START_REF] Henkel | CatchUp!: capturing and replaying refactorings to support API evolution[END_REF][START_REF] Wu | Aura: a hybrid approach to identify framework evolution[END_REF].

1 2

 1 Motivation: Incompatible programsWhen you try to execute programs developed in an older version into a newer version of the language mainly 3 situations occur:

Figure 1 .

 1 Figure 1. A program seen as many related entities forming a puzzle.

Figure 2 .

 2 Figure 2. Missing parts as time goes. For example removed classes from standard library

Figure 3 .

 3 Figure 3. All the calls to missing parts from the program are intercepted by the hypervisor and redirect to an equivalent in the host environment.

Figure 4 .

 4 Figure 4. Encapsulated entities in different modules. They are only aware of what is inside the module (oval).

Figure 5 .

 5 Figure 5. Behaviors are missing and we cannot load the fractured pieces.

Figure 7 .

 7 Figure 7. A program loaded with two undefined pieces. The undefined pieces will be replace later with real pieces.

Figure 9 .

 9 Figure 9. The undefined entities of the program are in a module called hypervisor. They are isolated and modifying them impact only the hypervisor.

Figure 10 .

 10 Figure 10. Exchanging tests between implementation.

Figure 11 .

 11 Figure 11. Feature diagram of linked list tests

IWST' 19 ,

 19 July, 2019, Cologne, Germany Théo Rogliano, Guillermo Polito, and Pablo Tesone

https://rmod.inria.fr/web/software/Fuel

Acknowledgments

This work was supported by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council, CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020. The work is supported by I-Site ERC-Generator Multi project 2018-2022. We gratefully acknowledge the financial support of the Métropole Européenne de Lille.