Mahdi Saleh
email: mahdi.saleh@u-bordeaux.fr

Samir-Mohamad Omar

Eric Grivel
email: eric.grivel@ims-bordeaux.fr

Oussama Bazzi
email: obazzi@ul.edu.lb

A Modified Stepped Frequency Phase Coding Radar Waveform Designed for the Frequency Domain Algorithm

Keywords: Stepped frequency waveforms, phase coding, intra-pulse modulation, peak sidelobe ratio, FD algorithm

A great deal of interest has been paid to enhance the radar range resolution for the last decades. One of the techniques is to construct a waveform combining inter-pulse and intra-pulse modulations. In this paper, stepped frequency (SF) waveform is used to represent the former, whereas phase coding (PC) is considered for the latter. To obtain the highresolution range profile (HRRP) of a target induced by an SF waveform at the receiver, one of the approaches is the frequency domain (FD) algorithm. It has been successfully applied with SF linear frequency modulation waveforms. However, based on our investigations, processing the SFPC waveform with the FD algorithm does not lead to the performance, in terms of peak sidelobe ratio (PSLR) and integrated sidelobe ratio (ISLR), of the single-carrier phase coding (SCPC) waveform processed with a matched filter (MF). To overcome these drawbacks, we propose to split the spectrum of a phase coded pulse into a predetermined number of portions, and then to successively transmit the time-domain transformed versions of these various portions. The received echoes are then processed with a modified version of the FD algorithm. Our analysis and simulations show that the proposed waveform can be characterized by a PSLR and an ISLR close to those of the SCPC processed with MF in some scenarios.

Introduction

During the last decades, a great deal of interest has been paid to high range resolution (HRR) in various radar applications, from synthetic aperture radar (SAR) and ground penetrating radar (GPR) to radar target recognition. The key way to obtain HRR is to select a wide bandwidth waveform. For this purpose, two families can be considered. On the one hand, waveforms with high instantaneous bandwidths can be used. One of them consists of a train of nonmodulated pulses whose durations are of the order of the nanoseconds. Another waveform consists of a train of modulated pulses. In the latter, each pulse is internally modulated in phase or in frequency. This modulation is known as the intra-pulse modulation, and one of its representatives is the linear frequency modulation (LFM). However, the aforementioned waveforms lead to a high sampling rate at the receiver. An expensive analog-to-digital converter (ADC) is hence required. On the other hand, a waveform that consists of a train of externally modulated pulses can be considered. This modulation is known as the inter-pulse modulation. The most attractive one is the stepped frequency (SF) waveform [START_REF] Lord | Aspects of stepped-frequency processing for lowfrequency SAR systems[END_REF] [2] [START_REF] Melvin | Principles of modern radar[END_REF]. In this waveform, a large bandwidth can be obtained by sequentially changing the carrier frequency equidistantly from one pulse to another in one burst. This makes it possible to reduce the instantaneous bandwidth and hence an ADC with a small sampling rate can be exploited. In various radar applications, the above two families can be combined. This has the advantage of reducing the number of pulses within the coherent processing interval (CPI) 1 . Toward this goal, SF-LFM is considered as one of the most popular waveforms [START_REF] Zhai | Application of super-SVA to stepped-chirp radar imaging with frequency band gaps between subchirps[END_REF] [START_REF] Yuan | Study on I SAR imaging of steppedfrequency chirp signal[END_REF] [6] [START_REF] Liu | Imaging approach for airborne steppedfrequency synthetic aperture radar in the squinted mode[END_REF] [8] [START_REF] Luo | Micro-Doppler effect analysis and feature extraction in ISAR imaging with stepped-frequency chirp signals[END_REF]. Nonetheless, two other waveforms, known as stepped-frequency phase coding (SFPC) and SF nonlinear frequency modulation (SF-NLFM), have recently started to attract the attentions of the researchers [START_REF] Li | RFI suppression based on phase-coded stepped-frequency waveform in through-wall radars[END_REF]. In [START_REF] Fukushima | A study on stepped frequency radar by using intra-pulse phase coded modulation[END_REF], the SFPC waveform was investigated. The range estimation in the presence of moving targets is more precise than that of the SF waveform. Moreover, it was suggested to be used with the through the wall radar (TWR) in order to enhance the anti-radio frequency interference performance [START_REF] Li | RFI suppression based on phase-coded stepped-frequency waveform in through-wall radars[END_REF]. As for the SF-NLFM waveform, Gladkova [START_REF] Gladkova | Grating lobes suppression in stepped-frequency pulse train[END_REF] illustrated its advantage over the SF-LFM waveform in terms of reductions of the grating-lobe levels. In most radar systems, the traditional approach to process the received echoes at the receiver consists in applying a matched filter (MF) in one shot to the whole train of the received echoes. The processing of SF waveforms with MF requires a high computational cost. In addition, grating lobes may appear in the high-resolution range profile (HRRP) 2 [START_REF] Gladkova | Grating lobes suppression in stepped-frequency pulse train[END_REF]. One alternative can be seen as a kind of stretch processing. It includes three different algorithms, namely the IFFT, the time domain (TD), and the frequency domain (FD) algorithms [START_REF] Lord | Aspects of stepped-frequency processing for lowfrequency SAR systems[END_REF]. Concerning the latter, the MF is considered at the level of each received echo separately so that the discrete Fourier transform (DFT) of each received echo is multiplied by the conjugate of the DFT of a reference pulse. Then, an inverse discrete Fourier transform (IDFT) is applied to a concatenated version of the previous results, instead of separately applying it to each individual one. The FD and the IFFT algorithms have computational costs smaller than that of the MFbased approach. However, they have some limitations. The IFFT algorithm produces ghost targets in the HRRP of the extended targets due to the spill-over effect of energy into consecutive coarse range bins [START_REF] Lord | Aspects of stepped-frequency processing for lowfrequency SAR systems[END_REF]. The TD algorithm [START_REF] Lord | High resolution SAR processing using stepped frequencies[END_REF] does not produce ghost targets but suffers from the up-sampling requirement of the narrow-bandwidth pulses prior to the frequency shift. Finally, the FD algorithm can cope with the drawbacks of the TD and the IFFT algorithms, but a DFT must be computed on a relatively large number of samples. Nevertheless, with the recent advances in designing and fabricating powerful processors (FPGAs, DSPs etc.), this no longer constitutes an obstacle for implementing this algorithm in real applications. Whatever the type of algorithm that is considered to detect a single-point target, the range profile usually exhibits one mainlobe and several sidelobes. The levels of the sidelobes with respect to the mainlobe one have a great influence on the probability of detection (PD) and the probability of false alarm (PFA). This can be quantified using two ratios: the peak sidelobe ratio (PSLR) and the integrated sidelobe ratio (ISLR). Various schemes have been proposed to enhance these ratios. In [START_REF] Key | A method of side-lobe suppression in phase-coded pulse compression systems, Technical report[END_REF], a tapped delay technique is used to suppress the range sidelobes of phase reversal codes. The authors in [START_REF] Ackroyd | Optimum mismatched filters for sidelobe suppression[END_REF] designed an optimum mismatched filter that can be applied to any phase code. The latter filter reduces the sidelobes at the expense of a slight loss in SNR compared to that obtained from an MF. In a noiseless environment, the PSLR and ISLR that characterize the HRRP obtained by processing a single-carrier phase coding (SCPC) waveform with an MF at the receiver has the same shape as the autocorrelation function of the phase code that is used. However, directly processing an 2 HRRP is representative of the reflectivity of the target to an HRR radar waveform projected onto the radar line-of-sight. This 1-D signature characterized by range bins makes it possible to estimate the target size and the positions of some scattering points of the target structure.

SFPC waveform with the FD or the IFFT algorithm leads to a PSLR and an ISLR that are worse than those obtained with an SCPC waveform. The PSLR is limited to -13.2 dB and the ISLR to -9.6 dB. To overcome these limitations, we propose a modified SFPC waveform derived from the SCPC waveform. Firstly the spectrum of a phase coded pulse is split into a predetermined number of non-overlapping portions. Then, the corresponding time-domain signals are successively transmitted. The latter signals represent the modified SFPC waveform. As this methodology leads to some constraints on selecting the number of portions, two alternative solutions are proposed. The first one consists in splitting the spectrum into non-overlapping portions of different sizes. As for the second, the spectrum is split into overlapping portions of equal size. At the receiver, the processing chain is necessarily modified. The purpose of our analysis is then twofold: firstly, we aim at studying the relevance of the modified waveform compared with the single-carrier phase coding (SCPC) waveform in terms of PSLR, ISLR, and sampling frequency. In addition, the influence of the selected number of portions on the PSLR and the ISLR is investigated. Secondly, we suggest comparing the modified SFPC waveform with the SFPC waveforms processed by either the IFFT or the FD algorithm in terms of PSLR, ISLR, and computational cost. The remainder of the paper is organized as follows: in section 2, we briefly recall the analytic expressions of the SCPC waveform and various SF waveforms at both the transmitter and the receiver parts. We also present the steps of the FD algorithm to reconstruct the HRRP when an SF-LFM waveform is considered. In addition, some details about the PSLR, the minimum range, and the range resolution are provided. In section 3, the modified SFPC waveform is first presented by focusing on the case of nonoverlapping portions and then by dealing with the variants either based on non-overlapping portions or overlapping portions of unequal sizes. Then in section 4, the results of the simulations of the modified SFPC waveform in different scenarios are shown. Finally, conclusions and perspectives are drawn in section 5. In what follows, note that * denotes the conjugate, . * stands for a multiplication of vectors element by element, and rect(t) stands for a rectangular pulse equal to 1 for -1 2 ≤ t ≤ 1 2 and zero elsewhere.

Waveforms Modeling and FD algorithm

In this section, the SCPC, SF, and SFPC waveforms are presented. Then, the steps of the FD algorithm are briefly recalled. Finally, the definitions of some special radar metrics that are used in the simulation part are given.

2.1. Waveform modeling at the transmitter and the receiver Let us start with the modeling of the SCPC waveform.

SCPC waveform model

When dealing with phase coding intra-pulse modulation, a pulse with width T p is modulated by a code sequence of length M . This is done by dividing the pulse into M concatenated sub-pulses of duration T c , where T c = Tp M . Each element of the code sequence is represented by a code phase value φ m (m ∈ 0, M -1 ). Hence, the SCPC waveform is given for 0 ≤ t ≤ T p by:

s tx (t) = M -1 m=0 A.rect t -m.T c -T c /2 T c .exp(jφ m ) (1)
.

exp[j2πf c t]

where A is the amplitude of the pulse, f c is the carrier frequency, and φ m is the sequence of the phase code used.

SF waveform model

The SF radar transmits a burst of N p > 1 pulses, whose carrier frequency monotonically increases from pulse to pulse by a fixed frequency step size denoted as ∆f . For the (i + 1) th pulse (i ∈ 0, N p -1 ), the transmitted waveform is described as follows:

s tx,i (t) = v i (t).exp[j2πf i t] (2)
with

v i (t) = A.rect t -i.T r -T p /2 T p (3)
In [START_REF] Wehner | High resolution radar[END_REF], the carrier frequency of the (i + 1) th transmitted pulse is given by:

f i = f c + 1 -N p 2 + i ∆f (4)
where f c is the central carrier frequency of the complete train of pulses. In addition, in (3), T r denotes the pulse repetition interval.

SFPC waveform model

The SFPC waveform consists of a burst of N p phase coded pulses whose carrier frequencies vary as in the case of the SF waveform. Therefore, it can be represented by [START_REF] Wehner | High resolution radar[END_REF] where v i (t) is given for i.T r + m.T c ≤ t < i.T r + (m + 1).T c and i ∈ 0, N p -1 by:

v i (t) = M -1 m=0 A.rect t -m.T c -i.T r -T c /2 T c .exp(jφ m )
(5) In the FD algorithm, which is illustrated in the sequel, the discrete-time version of ( 5) is required where T (T x) s denotes the sampling time at the transmitter. Hence, (5) becomes:

v i (n) = M -1 m=0 A.rect nT (T x) s -m.T c -i.T r -T c /2 T c (6)
.exp(jφ m )

In [START_REF] Chua | Phase coded stepped frequency linear frequency modulated waveform synthesis technique for low altitude ultra wideband synthetic aperture radar[END_REF], n ∈ 0, N -1 where N = Tp T (T x) s denotes the number of samples associated with each transmitted pulse. In accordance with this arrangement, each sub-pulse is represented by N/M samples.

Received SF signal model

At the receiver, a demodulation process takes place to down-convert the signal to baseband. In the absence of noise3 , the received SF signal for a stationary point target at range R can be written as follows:

s rx,i (t) = v i t -t d .exp j2πf i .(t -t d ) (7) = v i t - 2R c .exp j2πf i .(t - 2R c )
where t d = 2R c and c is the speed of light. The reference signal used for the demodulation is defined by:

s ref,i (t) = exp[j2πf i t] (8)
The demodulated signal at the baseband is therefore given by:

s d,i (t) = s rx,i (t).s * ref,i (t) (9)
= v i t - 2R c .exp -j2πf i . 2R c
As the baseband signal terms in (9) are associated with the range of the target, different algorithms can be exploited to produce the HRRP of the SF waveforms. Among them, the FD algorithm is presented in the following.

Processing chain based on the standard FD algorithm

The FD algorithm aims at reconstructing a large target reflectivity spectrum by coherently combining the individual spectra of the received narrow-band LFM pulses in the frequency domain [START_REF] Wilkinson | Stepped-frequency processing by reconstruction of target reflectivity spectrum[END_REF]. In the following, the steps of the FD algorithm4 are briefly recalled: 1. S d,i (k), the DFT of the received samples associated with each pulse in (9) padded with N -1 zeros is computed, where k ∈ 0, 2N -2 . The sampling frequency at the receiver satisfies in this case:

F (Rx) s = 2B inst = F (T x) s N p = B N p (10)
In [START_REF] Li | RFI suppression based on phase-coded stepped-frequency waveform in through-wall radars[END_REF],

F (T x) s
denotes the sampling frequency at the transmitter and B denotes the total bandwidth of the waveform.

with v i (n) = A.rect n.T (T x) s -i.
(k) = 1 |V pad i (k)| 2 . This leads to: Z r,i (k) = exp -j2π(f i + kF (Rx) s 2N -1 ) 2R c (11)
The magnitude of the synthesized spectrum obtained in (11) has a rectangular shape, i.e. |Z r,i (k)| = 1. 4. The sub-spectra in [START_REF] Fukushima | A study on stepped frequency radar by using intra-pulse phase coded modulation[END_REF] are contiguously arranged to synthesize the whole spectrum.

Z r,i = [Z r,i (0) Z r,i (1) . . . Z r,i (2N -2)] (12)
The total concatenated spectrum can be represented as a row vector of size (2N -1).N p as follows:

Z r,total = Z r,0 Z r,1 . . . Z r,Np-1 (13)
5. Z r,total is of interest to deduce the HRRP. As recalled in Appendix A, providing that F (Rx) s = ∆f , the IDFT of the elements of the vector Z r,total leads to:

|z r (n)| = 1 (2N -1).N p sin N p π(F (Rx) s 2R c -n Np ) sin π 2N -1 F (Rx) s 2R c -n Np ( 14
)
where n ∈ 0, (2N -1).N p -1 and |z r (n)| has its maximum equal to 1 when n =

2RF (Rx ) s Np c = t d F (Rx) s N p .
Due to [START_REF] Key | A method of side-lobe suppression in phase-coded pulse compression systems, Technical report[END_REF], amplitude weighting can be applied to reduce the range sidelobes. It consists in multiplying (13) by another row vector W of the same length containing the spectrum of a shaping window, such as Hanning.

G r,total = Z r,total . * W ( 15
)
An IDFT is finally applied to the synthesized spectrum in [START_REF] Ackroyd | Optimum mismatched filters for sidelobe suppression[END_REF] to create the HRRP.

Performance measures

Four performance measures are considered.

1. The peak sidelobe ratio (PSLR) is given by:

P SLR = 20log max(sidelobe peak) mainlobe peak (16)
The best performance in terms of PSLR mitigates the masking effect of nearby targets and increases the useful dynamic range.

2. The integrated sidelobe ratio (ISLR) is given by: ISLR = 10log total energy in sidelobes energy in mainlobe (17) The sidelobes which are less than T p far away from the center of the mainlobe, on both sides of the mainlobe, are taken into consideration. 3. The minimum range (R min ) represents the minimum range through which the targets can be detected by the radar. It is directly proportional to the pulse width:

R min = cT p 2 (18)
4. The range resolution (R res ) is the separation between the peak and the first null of the range profile. R res is inversely proportional to B ef f .

R res = c 2B ef f (19)
It reflects the capability of the radar to separate two closely spaced targets. The level of significance given for each performance measure, especially the PSLR and the ISLR, depends on the surrounding environment. Whenever the received signal is disturbed by a distributed clutter environment, the ISLR is of high importance and should be maintained as low as possible to enable the detection of weak targets. For instance, it contributes to the multiplicative noise in SAR image [START_REF] Carrara | Spotlight synthetic aperture radar: signal processing algorithms[END_REF]. However, if the received signal is disturbed by a strong discrete clutter, the PSLR is more critical to be kept low. Otherwise, sidelobes may be interpreted falsely as real targets [START_REF] Lellouch | Design of OFDM radar pulses using genetic algorithm based techniques[END_REF]. In the following the modified SFPC waveform is presented.

The modified SFPC waveform

Let us first elaborate the background upon which the proposed waveform has been built. The way by which we construct the modified SFPC (M.SFPC) waveform has a great similarity and analogy with that of the SF-LFM waveform. To the best of our knowledge, researchers like Hamada [START_REF] Fukushima | A study on stepped frequency radar by using intra-pulse phase coded modulation[END_REF] modulate the transmitted pulses of the SFPC waveform with the same phase code. However, this arrangement is not useful whenever the FD algorithm is exploited since it leads to bad PSLR and ISLR. Accordingly, to solve this problem, we propose the M.SFPC waveform that follows the same methodology of the aforementioned SF-LFM waveform, and consequently improves both the PSLR and the ISLR. This section deals with the steps done both at the transmitter and the receiver. They are presented for a nonoverlapping scenario where B inst = B 2Np . A block diagram that illustrates the whole processing chain of the M.SFPC waveform is given in Fig. 1.

Generation of the modified SFPC waveform at the transmitter 3.1.1. Description of the different steps to be done

Without loss of generality, let us consider any single pulse from (6). For instance, for i = 0, it is given for n ∈ 0, N -1 by:

v(n) = M -1 m=0 A.rect nT (T x) s -mT c -T c /2 T c .exp(jφ m ) (20) where:
1

T (T x) s = F (T x) s = B (21)
At this level, the following steps are carried out:

1. Apply a DFT to [START_REF] Galati | Chirp signals and noisy waveforms for solid-state surveillance radars[END_REF] to get V (k). 2. Split V (k) into N p equal portions denoted as P l (k), where l is an integer that satisfies l ∈ 0, N p -1 and k ∈ 0, N -1 . If N p = 1, this would correspond to a single phase coded pulse similar to the one given in [START_REF] Galati | Chirp signals and noisy waveforms for solid-state surveillance radars[END_REF]. In the following, N p > 1 and N is necessarily an integer multiple of N p .

P l (k) = V (k) lN Np ≤ k ≤ (l + 1) N Np -1 0 elsewhere (22)
The frequency band occupied by P l (k) is

F (T x) s
Np .

Apply an IDFT to each separated portion P l (k).

This leads to N p sequences, p 0 (n), . . . , p Np-1 (n), each of size N . 4. Scale the amplitudes of {p l (n)} l=0,1,...,Np-1 as follows:

p s,l (n) = 1 1 N N -1 n=0 |p l (n)| 2 p l (n) = 1 α l p l (n) (23)
The train of pulses {p s,l (n)} l=0,...,Np-1 represents the M.SFPC waveform. This step is necessary to guarantee that the powers of all transmitted pulses are equal. 5. Convert the discrete sequences {p s,l (n)} l=0,1,...,Np-1

to the continuous-time domain by using a digital-toanalog converter (DAC).

6. Multiply the latter continuous-time domain pulses by exp[j2πf c t] to frequency translate each portion by f c . The resulting continuous-time signal transmitted through the antenna is hence given by:

s tx,l (t) = 1 α l p l (t)exp j2πf c t (24)
Furthermore, one has to prepare a version of the non-zero components of the spectra P 0 (k), . . . , P Np-1 (k) centered at the zero frequency. These versions are not intended to be transmitted at all. They are saved in the memory of the radar to be used later on in the receiver part 5 . Thus, for l ∈ 0, N p -1 , the reference signals are given by:

p ref,l (n) =p l (n)exp -j2π (2l + 1)B 2N p n F (T x) s = (29) p l (n)exp -jπ 2l + 1 N p n (25)
Then, the resulting sequence associated with each portion is down-sampled by a factor N p so that it is composed of N Np samples. For n ∈ 0, N Np -1 , it is given by:

p down ref,l (n) = p ref,l (n.N p ) = p l (n.N p )exp -jπ(2l + 1)n (26)
Finally, the output of the down-sampler is padded by

About the relation between

P dopad ref ,l (k) and V(k) Let us now find a relation between P dopad ref,l (k) and V (k). Given an N -length signal x(n), it is known that the DFT of exp -j2π mn N .x(n) is equal to X(k + m).
Therefore, by combining ( 21) and (25), P ref,l (k) can be written as follows:

P ref,l (k) = P l k + 2l + 1 2 N N p (27)
Given Appendix C, one has: where the psinc function is defined as follows:

P dopad ref,l (k) = N Np -1 k1=0 P down ref,l (k 1 ) .exp -jπ( k 2N -N p - k 1 N )(N -N p ) .psinc N Np 2πN p k 2N -N p - k 1 N (28)
psinc N Np (θ) = N p N sin( N Np θ 2 ) sin( θ 2 ) (29)
Combining ( 22), (B.3), ( 27) and (28) leads to:

P dopad ref,l (k) = 1 Np N 2Np -1 k 1 =0 V k1 + 2l + 1 2 N Np (30) .exp -jπ( k 2N -Np - k1 N )(N -Np) .psinc N Np 2πNp k 2N -Np - k1 N + 1 Np N Np -1 k 1 = N 2Np V k1 + 2Np + 2l -1 2 N Np .exp -jπ( k 2N -Np - k1 N )(N -Np) .psinc N Np 2πNp k 2N -Np - k1 N
where k ∈ 0, 2N Np -2 and k 1 ∈ 0, N Np -1 . These types of expressions are useful for the simulation of the receiving steps. It also shows the influences of the downsampling and the padding through the psinc function.

Processing of the modified SFPC waveform at the receiver 3.2.1. Description of the different steps to be done

Due to the round trip path, the received signal corresponds to a version of the transmitted signal delayed by the time t d . In addition, the received signal is usually disturbed by additive disturbances containing the measurement white noise and the clutter. In the following and as done in subsection 2.2, they are not taken into account in order to focus the reader attention on the signal part. However, for completeness, the issues related to the noise will be addressed at the end of subsection 3.2. Using [START_REF] Omar | A novel barker code algorithm for resolving range ambiguity in high PRF radars[END_REF], the "ideal" received signal is given by:

s rx,l (t) = s tx,l (t -t d ) = 1 α l p l (t -t d )exp j2πf c (t -t d )
(31) The first step is to down-convert the received signal to the baseband. It is done by multiplying the l th received pulse with exp -j2π(f c + (1+2l)B 2Np )t . The resulting signal is:

s bb,l (t) = 1 α l p l (t -t d )exp -j2π( (1 + 2l)B 2Np )t (32) × exp -j2πfct d
Then, it is sampled at the sampling frequency F (Rx) s defined in [START_REF] Li | RFI suppression based on phase-coded stepped-frequency waveform in through-wall radars[END_REF].

In this case, the number of samples that represent each received pulse is equal to N Np . For the sake of simplicity, let us address the toy example where the delay is strictly a multiple of the sampling period at the receiver 6 , one has:

t d = d F (Rx) s = d.T (Rx) s ( 33
)
6 Otherwise some approximations would appear in the algorithm.

At this level, taking into account [START_REF] Li | RFI suppression based on phase-coded stepped-frequency waveform in through-wall radars[END_REF], (32), and (33), the l th baseband received signal can be represented for n ∈ 0, N Np -1 by:

s bb,l (n) = 1 α l p l ((n -d)N p )exp -jπ(1 + 2l)n (34) exp -j2πf c .d.T (Rx)
s Given (26), this leads to:

s bb,l (n) (35) = 1 α l .p down ref,l (n -d)exp -jπ(1 + 2l)d exp -j2πfc.d.T (Rx) s
Then, the following steps are carried out:

1. Apply an inverse scale to the result given in (35) by multiplying each received pulse by α l . Hence, for n ∈ 0, N Np -1 , (35) becomes:

p down ref,l (n-d)exp -j2πf c .d.T (Rx) s exp -jπ(1+2l)d (36) 2.
Pad each sequence obtained in (36) by N Np -1 zeros. This yields a vector of length Q = 2N

Np -1 on which a Q-size DFT is applied. The result is given by:

P dopad ref,l (k)exp -j2π k Q d exp -j2πf c .d.T (Rx) s .exp -jπ(1 + 2l)d (37)
where k ∈ 0, 2N Np -2 . 3. Apply an MF by multiplying each component of (37) by the complex conjugate of P dopad ref,l (k). The output is given by:

Z l (k) = |P dopad ref,l (k)| 2 exp -j2π k Q d (38) .exp -j2πf c .d.T (Rx) s exp -jπ(1 + 2l)d
where from (30) one has:

|P dopad ref,l (k)| 2 = 1 N 2 p N 2Np -1 k 1 =0 V (k1 + 2l + 1 2 N Np ) 2 .psinc 2 N Np 2πNp k 2N -Np - k1 N + 1 N 2 p N Np -1 k 1 = N 2Np V k1 + 2Np + 2l -1 2 N Np 2 (39)
.psinc 2

N Np 2πNp k 2N -Np - k1 N
The values in (38) are then stored in a vector of length Q = 2N Np -1:

Z l = [Z l (0) Z l (1) . . . Z l (Q -1)] (40)
4. Construct the whole spectrum by arranging the N p sub-spectra contiguously. The total concatenated spectrum is represented by a row vector of size N p Q = 2N -N p as follows:

Z total = Z 0 Z 1 . . . Z Np-1 (41)
Alternatively, this frequency shift can be achieved by multiplying the time domain version of (38) with a linear phase ramp. However, using a cut and paste method in the frequency domain, as it is done here, results in a much more efficient algorithm [START_REF] Lord | Aspects of stepped-frequency processing for lowfrequency SAR systems[END_REF]. 5. To produce the HRRP, apply an IDFT to (41) yields:

z(n) = 1 NpQ Np-1 l=0 Q-1 k=0 Z total (lQ + k)exp j 2π(lQ + k)n NpQ ( 42
)
where Z total (lQ + k) is the (lQ + k) th element of Z total . A zero padding may be done in the frequency domain to force power of 2-size IFFT, or to interpolate further the HRRP to get a better view. It should be noted that plotting the HRRP by directly using (39) and (42) constitutes a milestone to validate the results of the simulation section.

Remark about the impact of the compression filter in the presence of noise

Let us now assume that a white Gaussian noise is added to the received signals. Hence, (40) becomes:

s rx,l (t) = s tx,l (t -t d ) + u l (t) (43) = 1 α l p l (t -t d )exp j2πf c (t -t d ) + u l (t) (44)
where u l (t) represents the Gaussian noise in the l th pulse. Following the same mathematical developments done after (40), the expressions given in (37) and (38) become respectively:

P dopad ref,l (k)exp -j2π k Q d exp -j2πf c .d.T (Rx) s .exp -jπ(1 + 2l)d + Ũl (k) ( 45
)
where Ũl (k) is the DFT of the baseband noise at the output of the processing chain, and

Z l (k) = |P dopad ref,l (k)| 2 exp -j2π k Q d exp -j2πf c .d.T (Rx) s ( 46
)
.exp -jπ(

Z l (k) = exp -j2π k Q d exp -j2πf c .d.T (Rx) s (47)
.exp -jπ(1 + 2l)d + Ũl (k)

P dopad ref,l (k)
Phase coded pulses may exhibit small values in their spectrum at certain frequencies (see, for instance, Fig. 3). At the bins that represent these frequencies,

Ũl (k) P dopad ref,l (
k) have large values. As a consequence, high peaks appear in the reconstructed spectrum. As they produce artifacts in the HRRP, the PSLR and ISLR deteriorate. Therefore, processing the SFPC waveform with the FD algorithm leads to undesirable performance in terms of PLSR and ISLR. As an alternative, a modified FD algorithm can be used where the compression filter is avoided.

Removing the constraints to choose F (T x) s

and N p Splitting the original spectrum into N p equal portions cannot be done when F (T x) s /N p is not an integer. To address this problem, there are two possibilities:

1. Decomposing the spectrum into N p portions of unequal size: In this case, each portion has a different bandwidth. Following this methodology, the spectrum can be split into any number of portions without worrying about the ratio F (T x) s /N p . However, at the receiver, the pulses would have different bandwidths. The sampling frequency would be either confined to the largest bandwidth of the portions or modified for each received echo.

Resorting to an overlapping methodology:

The spectrum is still split into N p equal portions, but the bandwidth of each portion is augmented and overlaps with its neighbor. The percentage of the overlap is the same between every two successive portions. By doing so, N p is maintained within the CPI whereas F (Rx) s increases. The larger the overlapping, the higher the F (Rx) s

. Following this methodology, as the second equality in [START_REF] Li | RFI suppression based on phase-coded stepped-frequency waveform in through-wall radars[END_REF] no longer holds, some simplifications done for the equations at the receiver part are no longer valid. In this case, (36), (37), and (38) become respectively:

± p down ref,l (n -d)exp -j2πfc.d.T (Rx) s ( 48
)
.exp -jπ

(1 + 2l)B.d.T (Rx) s Np ± P dopad ref,l (k)exp -j2π k Q d exp(-j2πfc.d.T (Rx) s ) (49)
.exp -jπ

(1 + 2l)B.d.T (Rx) s Np ± |P dopad ref,l (k)| 2 exp -j2π k Q d exp(-j2πfc.d.T (Rx) s ) (50)
.exp -jπ

(1 + 2l)B.d.T (Rx) s

Np

As a consequence, a trade-off has to be found in the selection of the methodology that would be followed for splitting the original spectrum. Selection relies on the specified application and the limitation one would have in terms of F (Rx) s .

Comments

1. About the envelope of the M.SFPC: In the traditional radar waveforms, the transmitted pulses have a constant envelope even though they may have a phase or frequency modulation in the context of an intra-pulse modulation. However, in our M.SFPC waveform, the resulting samples of each transmitted pulse have not only arbitrary phases but also arbitrary amplitudes, as shown in Fig. 2. Having a nonconstant envelope is a common feature of some proposed waveforms, e.g. the orthogonal frequency division multiplexing (OFDM), and the hybrid NLFM.

[19] [START_REF] Galati | Chirp signals and noisy waveforms for solid-state surveillance radars[END_REF] [21]. 2. About a trade-off between R min and B inst :

Radar engineers are always interested in using the minimal possible pulse width. In order to obtain high PSLRs with phase coded pulses, it is better to use polyphase codes of large length M . They lead to a trade-off between R min and B inst . On the one hand, exploiting these long codes with a fixed pulse width leads to a dramatic augmentation of B inst because the latter is proportional to M (see Table 1).

On the other hand, if we augment the pulse width to grasp this long code, R min increases according to [START_REF] Lellouch | Design of OFDM radar pulses using genetic algorithm based techniques[END_REF]. As a consequence, a trade-off has also to be found between the minimum range and the instantaneous bandwidth. This is the case of the SFPC waveform.

With the M.SFPC waveform and thanks to the methodology followed at the transmitting and receiving sides, the polyphase codes with large length M can be exploited while each pulse of the M.SFPC waveform still has the same width as the original pulse from which it is derived. Hence, for a certain value of B inst , the minimum range of the waveform is smaller than that of the SFPC waveform.

3. About the computational cost of M.SFPC vs. SFPC: For a fair comparison, N p and B inst are set at the same values for both M.SFPC and SFPC. As a consequence, each pulse of the SFPC waveforms consists of N samples whereas each pulse of the M.SFPC waveform consists of N Np samples. Table. 2 summarizes the computational cost of each step for both

M.SFPC 1 / O(N 2 ) O(Np.N 2 ) O(N ) 2 / / O(Np(2N -1)) O( (2N -Np) 2 Np ) 3 / O((N.Np) 2 ) O(Np(2N -1)) O(2N -Np) 4 / O(N Np) / / 5 / / O(Np(2N -1)) O((2N -Np) 2 ) 6 / / O(N 2 p (2N -1) 2 ) /
the M.SFPC and the SFPC at the transmitter and receiver sides. On the one hand, at the transmitter side, generating the transmitted signal for the SFPC waveform is straightforward and avoids all the procedure done for the M.SFPC waveform. However, all the steps at the transmitter should be executed only once. When the waveform is generated for the first time, the resulting samples are saved in the memory of the radar to be utilized later on for other transmissions. As a consequence, the computational burden at the transmitter is almost negligible compared with that of the receiver. Normally, radar engineers are interested in the latter rather than the former. This is due to the fact that all the steps at the receiver should be repeated every time an echo arrives at its front end. On the other hand, at the receiver side, given Table. 2, the addition of the computational power of the whole steps of each waveform reveals that the M.SFPC waveform requires less computational power than the SFPC waveform. Finally, in our M.SFPC waveform, the generated pulses are multiplied by the same carrier signal which eases the operation of the oscillator whereas in the SFPC waveform the frequency of the carrier signal varies in a fixed step from pulse to pulse.

About the relation between N p and CPI:

It is important that all the N p pulses that carry the different portions of the split spectrum are transmitted within the CPI. This highly depends on the velocity of the target. If the target is fixed or moving slowly, the number N p of split portions of the spectrum can be large, and consequently, a better performance is achieved. However, if the target is moving fast, then N p should be relatively small in order to guarantee that all the transmitted pulses lie within the CPI. Otherwise, the radar will not be able to receive all the echoes within the CPI. One of the possible solutions for this issue is to resort to compressed sensing techniques that have been proposed to deal with such scenarios where sparsity in the collected data exists [START_REF] He | High-resolution imaging and 3-D reconstruction of precession targets by exploiting sparse apertures[END_REF] [23].

Simulations and results

In this section, some features such as the magnitude spectrum and the range resolution of the M.SFPC waveform are investigated first. Then, comparisons of the M.SFPC waveform with SCPC and SFPC waveforms are presented.

The magnitude spectrum of M.SFPC waveform

At the receiver, as mentioned in subsection 3.2, each pulse is padded by zeros followed by an MF in the frequency domain. Let us analyze the influence of the zeropadding process on the reconstructed spectrum. For this purpose, suppose that there is a single pulse phase coded with P4 of length M = 100. Fig. 3 represents its magnitude spectrum obtained by two approaches: one by the DFT without padding and the other by the DFT with padding. It reveals that the discrete spectra are quasisymmetric. Let us now apply our methodology, illustrated in subsection 3.1, by splitting the discrete magnitude spectrum presented in red in Fig. 3 into N p = 4, 10, 20, 50 portions. In Fig. 4, for each value of N p , the reconstructed spectrum is presented. It is obvious that after reconstructing the spectrum, the quasi-symmetric feature is lost. When N p increases, the reconstructed spectrum differs more and more from the original one. This is due to the fact that applying the MF to the single received echo of the SCPC that is zero padded yields a different result from zero padding the corresponding received-echoes of the M.SFPC while applying the split MF.

M.SFPC waveform vs. SCPC waveform 4.2.1. R res of the M.SFPC waveform

Let us now investigate the capability of our M.SFPC waveform to obtain the range resolution of the SCPC waveform. Again, a polyphase P4 code with length M = 100 is used. In Fig. 5, we present the HRRP of a stationary point target located at range R = 240 m when N p = 4, 10, 20, and 40. For N p = 10, 20 and 40, R res = 1.5 m which is equal to the range resolution of the SCPC waveform. When N p = 4, R res for the M.SFPC waveform is slightly larger than the range resolution of the SCPC waveform.

Introduction including simulation protocol

Our purpose is to study the performance of the M.SFPC waveform with stationary targets. An additive white Gaussian noise (AWGN) is considered at the receiver, leading to a specific SNR. Some of the common parameters used in the whole subsection are given in Table 3, while the others are introduced gradually. In all the simulations, two cases (non-overlap and overlap) are addressed. At the receiver, the SCPC waveform is processed by MF is proportional to the bandwidth of the received signal, the sampling frequency at the receiver for the M.SFPC waveform is N p times smaller than that of the SCPC. Even if this comparison could be unfair due to this difference, we propose to analyze how much the PSLR and the ISLR vary. In the first illustration, the spectrum is split into non-overlapping portions, whereas in the second one, it is split into overlapping portions. Simulation protocol: The SNR varies from -5 dB to 30 dB with a step equal to 1 dB. For each SNR, 7000 independent realizations of the noise are generated. The SNR is defined as the ratio between the power of the SCPC pulse, denoted as P SCPC , and the variance of the noise, σ 2 n .

SN R = 10log 10 (

P SCP C σ 2 n ) ( 51
)
For the non-overlapping case and for a fair comparison, the sum of the powers of the N p pulses of the M.SFPC waveform is equal to P SCP C . Hence, even when N p changes, the sum of the power of all pulses is kept fixed. As for the phase codes used in this illustration, both P4 with length M = 100 (B = 200 MHz) and polyphase Barker with length M = 54 (B = 108 MHz) are considered.

For the overlapping case, the percentage of the overlap is set at 50%. The total number of samples of the M.SFPC waveform in this case is larger than that of the SCPC pulse by a factor of 1.5. Thus, for a fair comparison between both waveforms, the sum of the energy of N p pulses of the M.SFPC waveform is equal to the energy of the SCPC pulse. Furthermore, only P4 with length M = 100 (B = 200 MHz) and T p = 1 µs are considered for all the simulations in this illustration. Hence, both R min and R res are fixed.

Results and comments

The M.SFPC waveform with non-overlapping portions versus SCPC Let us now study the evolutions of the PSLR and the ISLR with respect to the SNR. According to Fig. 6, the mean value of the PSLR for both waveforms gets worse as the SNR decreases. At very low SNR, the mean of the PSLR of the M.SFPC waveform is 1.5 dB worse than that of the SCPC for N p = 2. However, at high SNR the mean of the PSLR of the M.SFPC waveform is highly dependent on N p . This difference appears since an MF is applied separately to each received pulse. Furthermore, the ability of the M.SFPC waveform with N p = 4 to outperform the SCPC waveform comes at the expense of an increase of the range resolution, as shown in Fig. 5-a. The good performance is mainly due to the interaction between two phenomena: First, the MF is applied to each pulse separately instead of jointly applying it to all the received echoes. Second, the cyclic-autocorrelation of the P4 code has zero sidelobes. The last feature has been exploited recently to separate overlapping echoes in weather radar [START_REF] Omar | A novel barker code algorithm for resolving range ambiguity in high PRF radars[END_REF]. In Fig. 8, the evolution of the PSLR of the M.SFPC using polyphase Barker code is presented. The latter code does not exhibit the zero-sidelobes feature. It reveals that the M.SFPC waveform is no longer capable of outperforming the SCPC waveform. This result confirms our aforementioned interpretation. In the same context, Fig. 7 provides the mean value of the ISLR at different SNR for both waveforms using P4 code. At very low SNR, the value of the ISLR of the M.SFPC waveform is 2 dB worse than that of the SCPC waveform for N p = 2. However, at high SNR, this amount varies with N p . The M.SFPC waveform with overlapping portions vs. SCPC waveform

Let us now investigate the performance of our M.SFPC waveform when an overlap between different portions exists. For this purpose, a set of Monte-Carlo simulations is carried out in which a P4 code is used as an intrapulse modulation. In Fig. 9 and Fig. 10, the mean values of the PSLR and the ISLR of the M.SFPC waveform are respectively presented as functions of the SNR. The PSLR ranges between -29 dB for N p = 39 and -21 dB for N p = 99. Using the overlapping between the transmitted portions offers the possibility to enhance the performance compared to the non overlapping scenario. For instance, at SNR = 30 dB, when N p = 50 for the non-overlapping scenario and N p = 49 for the overlapping one, the gain in terms of PSLR is around 6.8 dB. Although the number of transmitted pulses is almost the same in both scenarios, B inst for each transmitted portion in the non-overlapping scenario is equal to 4 MHz, whereas it is set at 8 MHz in the overlapping one. Therefore, this improvement comes at the expense of increasing the sampling frequency at the receiver. Moreover, as with non-overlapping portions, the PSLR of the M.SFPC waveform is larger than that of the SCPC waveform due to the same reasons. It is obvious that at low SNR, both the PSLR and ISLR of the M.SFPC waveform for the different number of portions N p converge to the same value. In order to shed light more on the powerfulness of the overlapping scenario in attaining PSLR and ISLR values better than those obtained with the non-overlapping one, we present a summary of different simulations we have conducted in Table. [START_REF] Zhai | Application of super-SVA to stepped-chirp radar imaging with frequency band gaps between subchirps[END_REF]. In every row of this table, the value of N p for the overlapping and the corresponding non-overlapping cases are carefully chosen. For N p = 9 in the overlapping case which requires F (Rx) s = 40 MHz, we choose two corresponding values of N p for the nonoverlapping case: N p = 5 which is almost twice smaller but used with the same sampling frequency at the receiver and N p = 10 which requires almost the same number of portions but used with the sampling frequency which is twice smaller. Similar comments can be drawn for the other three cases presented in the table. Given the results presented in table 4, the overlapping scenario outperforms the non-overlapping one, in terms of PSLR and ISLR. The tax to be paid is either a higher F (Rx) s or a larger N p . In this section, the performance of the M.SFPC waveform as defined in the previous subsection is compared with that of the SFPC waveform. Both the IFFT and the FD algorithms are used, because the first one is usually considered whereas the second has not yet been applied in the literature with the SFPC waveform. Simulation protocol: The SNR in both illustrations is defined by: SN R = 10log10(

P SF P C l σ 2 n ) = 10log10( P M.SF P C l σ 2 n ) (52)
where P SF P C l and P M.SF P C l respectively denote the power of the l th pulse of SFPC and M.SFPC waveforms. For a fair comparison in both illustrations, the following equality holds true:

Np-1 l=0 P SF P C l = Np-1 l=0 P M.SF P C l ∀ N p (53)
Furthermore, the power of each transmitted pulse in both waveforms is kept fixed even when N p changes. This is different from what has been implemented in subsection 4.2.

Concerning the parameters and the phase codes used, there are some variations depending on the algorithm used at the receiver:

1. The case of the FD algorithm: Polyphase Barker code with length M = 60 is used instead of P4 as an intra-pulse modulation. The reason for this selection is due to the fact that in the FD algorithm, the output of the MF is multiplied by the inverse of the magnitude spectrum (See section 2.2, step 3). This arrangement cannot work properly with polyphase codes, such as P4, because they exhibit small values in their magnitude spectra, as illustrated previously in 3.2.2. The polyphase Barker code is one of the codes that does not exhibit small values in its spectrum. The parameters of each waveform are given in Table . 5. For a fair comparison, B inst for both waveforms should be the same. Moreover, this table shows that B ef f is also the same. This has been achieved by making 50% overlapping between the spectra of the different pulses of the SFPC waveform at the transmitter. At the receiver, the spectrum of each received echo of the SFPC waveform is multiplied by a rectangular window of width B/(2N p ). Hence, at the receiver, only half of the transmitted spectrum of each received echo of the SFPC waveform is exploited. This methodology is used for two reasons: To guarantee a fair comparison between both waveforms by maintaining the same B ef f , and to reduce the ISLR of the SFPC waveform as much as possible.

2. The case of the IFFT algorithm: The parameters used in this simulation are given in Table . 6. Again, the parameters are selected so that B inst is the same for both waveforms. Moreover, the polyphase P4 code with length M = 100 is used.

Results and comments

Modified SFPC versus SFPC using FD algorithm First, in Fig. 11, the HRRP of the SFPC waveform in the absence of noise when N p = 10 is presented. Then, in Fig. 12a, the PSLR versus SNR for both waveforms are depicted for different numbers of transmitted pulses. The PSLR of the SFPC waveform cannot exceed -13.5 dB, in the best case with the absence of noise. This is because its spectrum is transformed into a rectangular form, after applying the compression filter. Therefore, its PSLR is significantly worse than that of the M.SFPC at the whole SNR range, no matter what N p is. In Fig. 12b the ISLR of both waveforms is shown. It is obvious that the M.SFPC substantially outperforms the SFPC at low to moderate SNR, whereas the performance is equivalent at high SNR and large N p . Furthermore, Table . 5 reveals that the pulse width in M.SFPC does not vary with N p . It exhibits a smaller minimum range compared with the SFPC. This is because the pulse width of the latter waveform grows with N p . The minimum range must be as small as possible for radars that search for targets at a close range. It turns out that the exploitation of the FD algorithm with the SFPC is not favorable due to the non-rectangular shape of any phase coded pulse. As a consequence, the M.SFPC waveform is considered as an alternative to the SFPC waveform when the FD algorithm is used. Modified SFPC vs. SFPC using IFFT algorithm In Fig. 13a and Fig. 13b, the evolutions of the mean value of the PSLR and ISLR of both waveforms for various N p are presented respectively. Fig. 13a shows clearly the enhancement of the PSLR of the M.SFPC waveform compared to that of the SFPC waveform. As for the ISLR, the results are highly dependent on N p . Hence, the M.SFPC waveform outperforms the SFPC for certain values of N p , and the converse occurs for other values. Looking at both waveforms from another viewpoint, the range resolution for the SFPC waveform is twice better than that of the M.SFPC. However, the minimum range of the M.SFPC waveform is kept constant for any value of N p whereas that of the SFPC waveform varies with the selected N p . The larger N p is, the longer R min is. See Table . 6. is much smaller in M.SFPC waveform, which is a great advantage. Furthermore, the latter approximately achieves the same PSLR, and even better than that of the SCPC in some situations depending on N p . From the other side, the comparison between the M.SFPC and the SFPC waveforms processed with the FD algorithm, reveals that both waveforms attain the same range resolution and require the same sampling frequency at the receiver for the same number of transmitted pulses. However, the former leads to better PSLR and ISLR. Moreover, R min is much shorter. If the SFPC is processed with the IFFT algorithm instead, R res is enhanced by a factor of two, and also the ISLR becomes much better. Nonetheless, compared with the M.SFPC waveform, it still achieves higher PSLR and R min . In the same context, one may wonder why we do not exploit the amplitude windowing with the SFPC as an alternative approach to the M.SFPC, knowing that both are processed with the FD algorithm. It is true that amplitude windowing reduces the range sidelobes of the HRRP. However this reduction comes at an increase in the range resolution. To cope with this shortcoming, the M.SFPC is designed to permit a reconstruction of a spectrum at the receiver that is close as much as possible to that of the phase code initially used at the transmitter. In this case, there is no need to apply windowing to the reconstructed spectrum.

Studying the performance of the M.SFPC waveform in a real radar scenario

In this subsection, our purpose is to study the performance of the M.SFPC waveform in a realistic scenario. Its performance is compared with that of the SFPC waveform processed with the IFFT algorithm. Suppose it is required to detect and identify a certian target from some of its scatterers. In this case, let us consider four point scatterers with reflection coefficients [A 1 A 2 A 3 A 4 ]=[0.5 0.7 0.2 1]. The ranges between the scatterers and the radar are

[R 1 R 2 R 3 R 4 ] =[30006m 30009m 30015m 30018m].
A Monte-Carlo simulation is carried out for each of the M.SFPC and the SFPC waveforms where a polyphase P4 with M = 100 is used. The parameters of the two waveforms are given in Table . 8. In addition, the SNR is equal to 5 dB. It is defined as the ratio between the power of the received pulse that corresponds to the scatterer that has the smallest reflection coefficient and the power of the noise. For a fair comparison, we resort to a scenario where both waveforms have the same instantaneous bandwidth, hence they require the same value of F (Rx) s . Moreover, the total occupied bandwidth B of both waveforms is the same. In addition, ∆F.Tp M = 0.5 has been taken into consideration for the SFPC waveform. The latter is a necessary condition for the IFFT algorithm to prevent ambiguous returns from folding in a certain region [START_REF] Melvin | Principles of modern radar[END_REF]. In Fig. 14 and Fig. 15, the HRRP of the SFPC waveform and the M.SFPC waveform are respectively presented. It turns out that with the SFPC waveform, the third scatterer cannot be discerned from the sidelobes of the other scatterers, as shown in Fig. 14. Moreover, the straddle loss associated with the IFFT algorithm [START_REF] Melvin | Principles of modern radar[END_REF] reduces the apparent amplitude of the second scatterer as shown in Fig. 14. In contrast, with the M.SFPC waveform, the same scatterer can easily be identified, as shown in Fig. 15. This result clearly reveals the advantage of the better PSLR of the M.SFPC waveform. Furthermore, the SFPC waveform requires longer CPI for the burst of pulses (N p = 13) to be transmitted, and the value of its minimum range (R min =600 m) is four times larger than that of the M.SFPC waveform. Nevertheless, it attains a range resolution R res = 0.75m which is twice better than that of the M.SFPC waveform.

Conclusions and perspectives

In this paper, the relevance of the simple yet efficient FD algorithm to treat the echoes of the SFPC waveform is studied. Our investigations have revealed that treating the latter waveform with either the FD algorithm or the IFFT algorithm could not exploit the PSLR and the ISLR that result from the autocorrelation function of the phase code used. Hence, to overcome this shortcoming, we have proposed a modified SFPC radar waveform. Contrasting this waveform with the SCPC waveform reveals that the M.SFPC waveform makes it possible to attain and even exceed the PSLR and the ISLR of such phase codes in the overlapping scenarios. This is achieved while still making use of the existing FD algorithm with some minor modifications to treat the received echoes. Moreover, contrasting the M.SFPC waveform with the SFPC waveform reveals that the former outperforms the latter in terms of PSLR, ISLR, and R min . To sum up, the M.SFPC waveform is suitable for applications that seek a high range resolution, small minimum range and a low computational cost. We believe that our proposed approach is not restricted to the SFPC scheme, but could rather be used with other SF schemes like SF-NLFM. Finally, in the future, we are going to investigate these schemes, following the same methodology that has been applied with the SFPC waveform in this paper.

Acknowledgements

This project has been funded with support from the National Council for Scientific Research in Lebanon.

Appendices

Appendix A Applying an IDFT to [START_REF] Lord | High resolution SAR processing using stepped frequencies[END_REF], yields: The latter is equal to 1 if θ = 0 and to 0 if θ is a multiple of 2π L . Otherwise, intermediate values are obtained. The DFT of the padded signal x M (n) is given by evaluating X L (θ) at the normalized angular frequency θ = k 2π M where k ∈ 0, M -1 . Hence, X M (k) is given by:

X M (k) = L-1 k1=0 X L (k 1 )exp -jπ( k M - k 1 L )(L -1) .psinc L 2π( k M - k 1 L ) (C.5)
No simplification or approximation can be really done at this stage. All the values of the DFT of the non-padded signal contribute to get the values of the DFT of the padded signal. They are weighted by psinc L 2π( k M -k1 L ) . It should be noted that for a given k, the values of k 1 that lie in the main lobe of the psinc function satisfies:

k L M -1 < k 1 < k L M + 1. When M = 2L -1, k L 2L-1 -1 < k 1 < k L 2L-1 + 1.

NNp - 1

 1 zeros to get the sequence p dopad ref,l (n). Then, a DFT is applied to the latter sequence to obtain P dopad ref,l (k), as shown in Fig.1.

Figure 1 :

 1 Figure 1: A block diagram showing the whole processing chain of the M.SFPC waveform at both transmitter and receiver sides

Figure 2 :

 2 Figure 2: Real and imaginary parts of the M.SFPC waveform where the spectrum is split into four portions

Figure 3 :

 3 Figure 3: The power spectrum of polyphase P4 whose length is M = 100, with or without zero-padding

Figure 4 :

 4 Figure 4: Reconstructed power spectrum which corresponds to the concatenation of |P dopad ref,l (k)| 2 (a) Np = 4, (b) Np = 10, (c) Np = 20, and (d) Np = 50.

Figure 5 :

 5 Figure 5: HRRP of the M.SFPC waveform when (a) Np = 40, (b) Np = 20, (c) Np = 10, and (d) Np = 4.

Figure 6 :Figure 7 :

 67 Figure 6: Mean value of PSLR versus SNR using Np portions of polyphase P4 (M = 100)

Figure 8 :

 8 Figure 8: Mean value of the PSLR versus SNR using Np portions of polyphase Barker (M = 54)

Figure 9 :Figure 10 :

 910 Figure 9: Mean value of the PSLR versus SNR using Np overlapping portions of polyphase P4 (M = 100)

Figure 11 :

 11 Figure 11: HRRP of SFPC waveform treated using the FD algorithm. The phase code used is polyphase Barker with M = 60.

Figure 12 :

 12 Figure 12: Mean values of the PSLR and ISLR versus SNR for the SFPC, treated with FD algorithm, and M.SFPC waveforms using polyphase Barker (M = 60).

Figure 13 :

 13 Figure 13: Mean values of the PSLR and ISLR versus SNR for the SFPC, treated with IFFT, and M.SFPC, treated with FD, using polyphase P4 (M = 100).

Figure 14 :

 14 Figure 14: The HRRP of the SFPC waveform processed with the IFFT algorithm.

Figure 15 :

 15 Figure 15: The HRRP of the M.SFPC waveform.

Z|sin 1 ) 1 NpF (T x) s 2Np [ 1 NpF 1 Np 1 1 1 (B. 3 ) 2 )

 11111132 r,total (l 1 + 1)exp j2πl 1 n (2N -1)N p where Z r,total (l) is the l th element of Z r,total . Using (4), the above equation can be expressed as follows:z r (n) = exp -j2π(f c + Npπ(∆f 2R c -n Np ) | |sin π(∆f 2R c -n Np ) | = N p and |z r (n)| = 1 Appendix BThe relation between the discrete-time Fourier Transform (DTFT) of the sequence p ref,l (n) and that of its downsampled version p down ref,l (n) is given by: This amounts to reproducing N p times P ref (f ), or equivalently a portion of the Fourier transform V (f ), with a shift of frequency equal to kF (T x) s Np with k = 1, ..., N p -1.Since the latter is band-limited on a frequency band equal toF (T x) sNp , the different terms of the sum in (B.1) do not overlap. Hence, by taking advantage of the periodicity of the DTFT, (B.1) in the frequency band [0,F (T x) s P ref,l (f ) if f ∈ [0, P ref,l (f + (N p -1) .2), a relation can be deduced between the DFT of {p ref,l (n)} n=0,...,N -1 and that of {p down ref,l (n)} n=0,...,N/Np-1 computed at the sampling frequency F can be written for the k th frequency bin as follows:P ref,l (k) if k ∈ 0, N 2Np -Np P ref,l (k + (N p -1) N Np ) if k ∈ N 2Np , N Np -Appendix CIn the following, x L (n) denotes the original signal with length L and x M (n) is the original signal padded with zeros whose length is M . Given X L (k) the DFT of x L (n), θ the normalized angular frequency with respect to the sampling frequency, and k the frequency bin, let us recall the DTFT and the IDFT of X L (k):By substituting (C.2) in (C.1), the latter becomes:X L (θ) =

Table 1 :

 1 Table. 1 summarizes the relationship between B inst , B and B ef f for various waveforms. Relation between the bandwidths of different waveforms

	Waveform	Binst	B	B ef f
	SCP C	M/Tp	2M/Tp	B/2
	SF	1/Tp	(Np -1)∆F + 2Binst	B/2
	SF P C	M/Tp	(Np -1)∆F + 2Binst	B/2

Table 2 :

 2 The computational cost of the M.SFPC and SFPC waveforms at the transmitter and receiver sides. / is used when no computational cost is required

	Steps	Transmitter SFPC M.SFPC	SFPC	Receiver

Table 3 :

 3 General Parameters used in the simulation section

	Parameter	Value
	Pulse repetition	250 Hz
	frequency (P RF )
	Carrier frequency (f c )	3 GHz
	Pulse width (T p )	1 µs

since it consists of a single carrier whereas the steps given in subsection 3.2 are done for the M.SFPC waveform. Therefore, as F (Rx) s

Table 4 :

 4 PSLR and ISLR of the M.SFPC waveform for overlap-

	ping vs. corresponding non-overlapping cases, using polyphase P4
	(M=100) in a noiseless scenario
	N p	F	(Rx) s	PSLR	ISLR	50% Over-
		(MHz)	(dB)	(dB)	lap
	5		40	-26.46	-12.1	No
	9		40	-27.04	-15.5	Yes
	10		20	-24.15	-12.8	No
	10		20	-24.15	-12.8	No
	19		20	-27.52	-15.76	Yes
	20		10	-23.7	-7.9	No
	20		10	-23.7	-7.9	No
	39		10	-29.63	-13.54	Yes
	40		5	-22.62	-8.65	No
	50		4	-20.5	-7.8	No
	99		4	-20.96	-11.86	Yes
	100		2	-12	-5.94	No

Table 5 :

 5 Parameters for contrasting M.SFPC and SFPC waveforms using the FD algorithm.

			Polyphase Barker (M = 60) is used as an
	intra-pulse modulation
	Parameter	M.SFPC ∀ Np	Np = 10	SFPC Np = 20	Np = 30
	Tp (µs)	1	10	20	30
	B inst (MHz)	B 2Np	6	3	2
	F s (Rx)	(MHz)	B Np	12	6	4
	∆f (MHz)	B Np	6	3	2
	B (MHz)	120	120	120	120
	B ef f (MHz)	60	60	60	60
	Rres (m)	2.5	2.5	2.5	2.5
	R min (m)	150	1500	3000	4500

Table 6 :

 6 Parameters for contrasting M.SFPC and SFPC waveforms using IFFT algorithm. Polyphase P4 is used as an intra-pulse modulation

	Parameter	M.SFPC ∀ Np	Np = 10	SFPC Np = 20	Np = 40
	Tp (µs)	1	10	20	40
	B inst (MHz)	B 2Np	10	5	2.5
	F s (Rx)	(MHz)	B Np

Table 7 :

 7 Summary of the performance of various waveformsThe various waveforms that have been examined in this section are listed in Table.7. The values of the PSLR and the ISLR are measured for a P4 code in a noiseless environment. This table illustrates how the M.SFPC waveform processed with the FD algorithm outperforms both the SCPC and the SFPC waveforms. From one side, both the SCPC and the M.SFPC waveforms exhibit same range resolution and minimum range. Nevertheless, F

	W avef orm	SCP C SF P C	SF P C	M.SF P C
	Algorithm	M F	F D	IF F T	F D
	F	(Rx) s	(M Hz)	B	B/Np	B/Np	B/Np
		Rres	c/B	c/B	c/2B	c/B
	No. of pulses	1	Np	Np	Np
		Rmin	cTp/2 cTpNp/2 cTpNp/2	cTp/2
	P SLR(dB)	-26.32 -13.2	-12	[-21; -29.3]
	ISLR(dB)	-13.88 -6.67	-10.4	[-7.8; -13.7]
		Artif acts	N o	N o	Y es	N o
	4.4. Summary about M.SFPC vs. both SCPC and SFPC
							(Rx)
							s

Table 8 :

 8 Parameters for comparing the M.SFPC and the SFPC waveforms using the IFFT algorithm. Polyphase P4 is used as an intrapulse modulation

	Parameter	M.SFPC SFPC
	N p (µs)	4	13
	f c (GHz)	9.2	9.2
	P RF (Hz)	2300	2300
	T p (µs)	1	4
	B inst (MHz)	25	25
	F s (Rx)	(MHz)	50	50
	∆f (MHz)	50	12.5
	B (MHz)	200	200
	B ef f (MHz)	100	200

  If the above approach is applied to the sequence p down ref (n) with L = N Np and M = 2N Np -1 = 2L-1, this leads to:

	N Np -1
	P dopad ref,l (k) =	P down ref,l (k1)
	k 1 =0
	.exp -jπ(	k 2N -Np	-	k1 N	)(N -Np)
	.psinc N Np	2πNp	k 2N -Np	-	k1 N	(C.6)

CPI is the amount of time a given target is within the antenna beam on a single scan.

For the sake of simplicity the noise is omitted, although in practical cases it exists. Its effect will be treated later on in the paper.

[START_REF] Zhai | Application of super-SVA to stepped-chirp radar imaging with frequency band gaps between subchirps[END_REF] The latter was based on the general waveform defined in (2),

Normally, the received echoes are processed at the baseband to save the computational cost.


Denis Cornaz
email: denis.cornaz@dauphine.fr

Roland Grappe
email: grappe@lipn.univ-paris13.fr

Mathieu Lacroix
email: lacroix@lipn.univ-paris13.fr

Trader multiflow and box-TDI systems in series-parallel graphs

Keywords: box-TDI system, series-parallel graph, multiflow 90C27, 90C57, 05C70, 05C85

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

Introduction

Throughout the paper, all the entries will be rational. A linear system Ax ≥ b, x ≥ 0 is totally dual integral (TDI for short) if the maximum in the LP-duality equation min{c x : Ax ≥ b, x ≥ 0} = max{b y : A y ≤ c, y ≥ 0} has an integer optimal solution for all integer vectors c for which the optimum is finite. This property is much sought-after since such systems describe integer polyhedra when b is integer and yield min-max relations [START_REF] Edmonds | A Min-Max Relation for Submodular Functions on Graphs[END_REF]. An even stronger property than TDIness is box-TDIness, where a box-TDI system is a TDI system Ax ≥ b, x ≥ 0 which remains TDI when adding box-constraints ≤ x ≤ u, for all rational1 vectors , u. In other words, it is box-TDI if max{b y + z 1 -u z 2 : A y + z 1 -z 2 ≤ c, y ≥ 0, z 1 , z 2 ≥ 0} has an integer solution for all integer vectors c and all rational vectors , u for which the optimum is finite. General properties of such systems can be found in Cook [START_REF] Cook | On box totally dual integral polyhedra[END_REF] and Chapter 22.4 of Schrijver [START_REF] Schrijver | Theory of linear and integer programming[END_REF]. Note that, although every rational polyhedron {x : Ax ≥ b, x ≥ 0} is described by a TDI system

1 k Ax ≥ 1
k b, x ≥ 0, for some integer k, not every polyhedron is described by a box-TDI system.

The book by Schrijver [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF] contains numerous min-max relations of combinatorial optimization derived from TDI systems. When such systems are box-TDI, most of the time, the matrix A is totally unimodular. The past few years, this topic has received a renewed interest [START_REF] Ding | The complexity of recognizing linear systems with certain integrality properties[END_REF][START_REF] Pap | Recognizing conic TDI systems is hard[END_REF], and other box-TDI systems have been studied [START_REF] Chen | A Unified Approach to Box-Mengerian Hypergraphs[END_REF][START_REF] Chen | A Characterization of Box-Mengerian Matroid Ports[END_REF][START_REF] Chen | The box-TDI system associated with 2-edge connected spanning subgraphs[END_REF], with matrices that are not totally unimodular. A 0-1 matrix A so that the linear system Ax ≥ 1, x ≥ 0 is (box-) TDI is called (box-) Mengerian. In 1977, Seymour [START_REF] Seymour | The matroids with the max-flow min-cut property[END_REF] proved that a 0-1 matrix associated with a binary clutter is Mengerian if and only if it does not contain Q 6 as a minor. In 2008, Chen, Ding and Zang [START_REF] Chen | A Characterization of Box-Mengerian Matroid Ports[END_REF] proved that such matrices are box-Mengerian if and only if they contain neither Q 6 nor Q 7 as a minor. Recently, Ding, Tan and Zang [START_REF] Ding | When is the matching polytope box-totally dual integral?[END_REF] announced a characterization of the graphs for which a box-TDI system describes the matching polytope.

In 2009, Chen, Ding and Zang [START_REF] Chen | The box-TDI system associated with 2-edge connected spanning subgraphs[END_REF] proved that a graph is series-parallel if and only if the system 1 2 Ax ≥ 1, x ≥ 0 describing the 2-edge-connected spanning subgraph polytope is box-TDI, where A is the cut-edge incidence matrix of the graph. Another set of characterizations of series-parallel graphs given by Schrijver asserts that they are precisely the graphs for which the standard linear systems describing the cut cone, the cycle cone [START_REF] Seymour | Sums of circuits[END_REF], the cut polytope [START_REF] Barahona | On the cut polytope[END_REF], the T -join polytope [START_REF] Seymour | Matroids and Multicommodity Flows[END_REF] and the T -join dominant [START_REF] Edmonds | Matching, Euler tours and the Chinese postman[END_REF] are TDI -see Corollary 29.9c of [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF]. Moreover, it is proved in [START_REF] Cornaz | Max-multiflow/min-multicut for G+H series-parallel[END_REF] that a graph is series-parallel if and only if the standard linear system describing its multicut polytope is TDI. rial optimization and have been considerably studied, see for instance [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF]. We focus on integer multiflows in the present paper. Multiflow problems involve two simple undirected graphs, a supply graph G = (V, E) and a demand graph H = (V, R), and two vectors, a capacity vector c ∈ Z E + and a demand vector

d ∈ Z R + .
An edge e ∈ E is a link of capacity c e whereas an edge r ∈ R is a net of demand d r . From now on, (G, H, c, d) will refer to such a quadruplet. For a net r = st, let P(r) be the set of all st-paths in G, and let P be the union of P(r) for all nets r. A multiflow of (G, H, c, d) is an integer vector y ∈ Z P satisfying the following system of linear inequalities:

(mflow)        P ∈P(r) y P ≥ d r
for each net r ∈ R, P ∈P: e∈P y P ≤ c e for each link e ∈ E, y ≥ 0.

Two famous NP-hard problems are related to multiflows. Given G, H and c, the maximum multiflow problem asks for a demand vector d such that there exists a multiflow for (G, H, c, d) and r∈R d r is maximum. Given (G, H, c, d) and some cost vector w ∈ Z E + on the links, the min-cost multiflow problem asks for a multiflow minimizing the sum of w e y e over all links e ∈ E, where y e := P ∈P: e∈P y P is the amount of flow through link e.

A necessary condition for the existence of a multiflow in (G, H, c, d) is the cut condition which requires that d(D ∩ R) ≤ c(D ∩ E) for all cuts D of G + H, the latter being G + H = (V, E ∪ R) where E and R are considered as disjoint, that is, G + H may contain parallel edges. Seymour [START_REF] Seymour | Matroids and Multicommodity Flows[END_REF] proved that a graph (V, F ) is series-parallel if and only if for all partitions F into E and R, and for all c ∈ Z E + and d ∈ Z R + , the cut condition implies the existence of a multiflow.

Contribution.

In this paper, we investigate some box-TDI systems related to multiflows. Our main result is to strengthen the TDI characterizations of series-parallel graphs mentioned earlier by proving that the standard linear systems describing the cut cone, the cycle cone, the T -join polytope, the cut polytope, the multicut polytope, and the T -join dominant are actually box-TDI systems for series-parallel graphs -see Theorem 1.

From the box-TDIness of the cut cone, we derive a min-max relation for series-parallel graphs that involves a new multiflow problem generalizing both the maximum multiflow and min-cost multiflow problems. Given (G, H, c, d), a profit ∈ Z R + and a cost u ∈ Z E + , the trader multiflow problem asks to maximize z 1 -u z 2 over all (y, z 1 , z 2 ) ∈ Z P + × Z R + × Z E + such that y is a multiflow of (G, H, c, d) with c = c + z 2 and d = d + z 1 . Therefore, in this new multiflow problem, we gain r for each additional unit of demand on net r ∈ R that we are able to satisfy, we pay u e to add a unit of capacity on link e ∈ E, and the goal is to maximize the total benefit. The min-max relation we derive connects the trader multiflow problem and box-multicuts, where box-multicuts are a generalization of multicuts. We also show that the trader multiflow problem is polynomial time solvable in series-parallel graphs.

Outline. In Section 2, we establish our characterization of series-parallel graphs in terms of box-TDI systems. Section 3 is devoted to the trader multiflow problem. We first show how it generalizes both the maximum multiflow and min-cost multiflow problems. Then, we provide our min-max relation for the trader multiflow problem in series-parallel graphs and explain why this problem is polynomial in these graphs. For the sake of clarity, the most technical part of the proof of Theorem 1 is postponed to the Appendix. The rest of this section is devoted to definitions.

Definitions. Throughout, G = (V, E) will denote an undirected graph and T ⊆ V a set of vertices of even cardinality. A graph is series-parallel if it is obtained from a forest by repeating the operations of replacing one edge by two edges in parallel, or by two edges in series. Equivalently, these are the graphs without K 4 minor [START_REF] Duffin | Topology of series-parallel networks[END_REF]. Then, a series-parallel graph is planar and its planar dual is also series-parallel. Following [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF], a cycle is a subset C ⊆ E so that every vertex of (V, C) has an even degree. A minimal nonempty cycle is a circuit. The cut defined by a subset of vertices U , denoted by δ(U ), is the set of edges having one extremity in U and the other one in V \ U . A minimal nonempty cut is a bond. Note that cycles (resp. cuts) are disjoint unions of circuits (resp. bonds). A multicut is the set of all the edges between different classes of some partition of the vertex set. A T -join is a subset of edges F such that the odd degree vertices of (V, F ) are the ones in T . Note that a cycle is an

∅-join. A T -cut is a cut δ(U ) with |U ∩ T | odd. For x ∈ R E and F ⊆ E,
we use the notation x(F ) = e∈F x e . We will make no difference between combinatorial objects and their characteristic vectors, that is, for instance, we will speak of nonnegative combinations of cycles instead of nonnegative combinations of characteristic vectors of cycles.

Box-TDI systems of series-parallel graphs

In this section, we first provide the systems involved in our main theorem. Then, we state and prove Theorem 1, which establishes that the standard linear systems describing the cut cone, the cycle cone, the T -join polytope, the cut polytope, the multicut polytope and the T -join dominant are box-TDI if and only if the graph is series-parallel. These systems were already known to be TDI [START_REF] Cornaz | Max-multiflow/min-multicut for G+H series-parallel[END_REF][START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF].

TDI systems of series-parallel graphs...

Let us write now the systems involved in Theorem 1. Let G = (V, E) be an undirected graph and T ⊆ V a set of vertices of even cardinality.

Seymour [START_REF] Seymour | Sums of circuits[END_REF] proved that the cycle cone of G, that is, the set of nonnegative combinations of cycles of G, is described by the following set of inequalities.

(Cycle cone)

x(δ(U ) \ {e}) -x e ≥ 0 for each U ⊆ V and each e ∈ δ(U ),

x ≥ 0.

The T -join polytope of G is the convex hull of its T -joins. Seymour [START_REF] Seymour | Matroids and Multicommodity Flows[END_REF] proved that it is described by the following set of inequalities.

(T -join)

   x(F ) -x(δ(U ) \ F ) ≤ |F | -1 for each U ⊆ V , F ⊆ δ(U ) with |U ∩ T | + |F | odd, 0 ≤ x ≤ 1.
The T -join dominant of G is the set of vectors greater than or equal to some T -join of G. This dominant is described by the following set of inequalities, see Corollary 29.2b in [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF].

(T -join dominant) x(C) ≥ 1 for each T -cut C, x ≥ 0.
Sebő [START_REF] Sebő | The Schrijver system of odd join polyhedra[END_REF] provided a minimal TDI system describing the T -join dominant of G.

Let us assume that G is planar and let G * denote its dual graph. Recall that the cycles of G are the cuts of G * . Hence, (Cut cone)

x(C \ {e}) -x e ≥ 0 for each circuit C and each edge e ∈ C,

x ≥ 0, describes the cut cone of G, that is, the set of nonnegative combinations of cuts of G. Moreover, by taking T = ∅ in system (T -join), and then writing the planar dual, we have the following description of the cut polytope of G, that is, the convex hull of its cuts.

(Cut)

   x(F ) -x(C \ F ) ≤ |F | -1 for each circuit C and F ⊆ C with |F | odd, 0 ≤ x ≤ 1.
Actually, the systems (Cut cone) and (Cut) describe the cut cone and the cut polytope for a larger class than planar graphs, namely graphs with no K 5 -minor -see [START_REF] Seymour | Matroids and Multicommodity Flows[END_REF] and [START_REF] Barahona | On the cut polytope[END_REF], respectively. Schrijver showed that the systems (Cycle cone), (T -join) and (T -join dominant) are TDI if and only if the graph is series-parallel -see Corollary 29.9c of [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF]. A graph is series-parallel if and only if its dual is; this result, combined with the fact that cycles are ∅-joins, implies that (Cut cone) and (Cut) are TDI if and only if the graph is series-parallel.

Multicuts can be equivalently defined as arbitrary unions of cuts, or as sets of edges D ⊆ E such that |D ∩ C| = 1 for all cycles C. The multicut polytope of a graph is the convex hull of its multicuts, and is therefore contained in the polyhedron defined by the inequalities of (Cut cone) and x ≤ 1. Chopra [START_REF] Chopra | The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs[END_REF] showed that the following system, called (Multicut), describes the multicut polytope of a graph if and only if the graph is series-parallel.

(Multicut)

x(C \ {e}) -x e ≥ 0 for each circuit C and each edge e ∈ C,

0 ≤ x ≤ 1.
Corollary 4.1 of [START_REF] Cornaz | Max-multiflow/min-multicut for G+H series-parallel[END_REF] strengthens the result of Chopra [START_REF] Chopra | The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs[END_REF] by stating that system (Multicut) is TDI if and only if the graph is series-parallel.

... are actually box-TDI

We now strengthen the aforementioned TDIness results. More precisely, we show that each system mentioned in Section 2.1 which is TDI for seriesparallel graphs is actually box-TDI for these graphs. Our theorem implies Corollary 4.1 of [START_REF] Cornaz | Max-multiflow/min-multicut for G+H series-parallel[END_REF] and Corollary 29.9c of [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF].

Theorem 1. Let G = (V, E) be a graph. The following statements are equivalent. (i) G is series-parallel. (ii) System (Cut cone) is box-TDI. (iii) System (Cycle cone) is box-TDI. (iv) System ( T -join) is box-TDI, for all T ⊆ V of even cardinality. (v) System (Cut) is box-TDI. (vi) System (Multicut) is box-TDI. (vii) System ( T -join dominant) is box-TDI, for all T ⊆ V of even cardinal- ity.
Proof. Proof. Series-parallelness is already necessary for the systems of (ii)-(vii) to be TDI -see [START_REF] Cornaz | Max-multiflow/min-multicut for G+H series-parallel[END_REF] for (vi) and Corollary 29.9c of [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF] for the others.

A box-TDI system being TDI, the necessity of (i) follows. For the other directions, we will show that (i) ⇒ (ii) ⇒ (iii) ⇒ (iv) ⇒ (v) and (ii) ⇒ (vi) and (iv) ⇒ (vii).

(i) ⇒ (ii): Let G = (V, E) be series-parallel, c ∈ Z E and , u ∈ Q E with ≤ u.
The primal problem is to optimize over the system (Cut cone) intersected with the box {x : ≤ x ≤ u}. Since we have x ≥ 0, we may suppose that ≥ 0 and we get:

(P )        min c x
x(C \ {e}) -x e ≥ 0 for each circuit C of G and each edge e ∈ C,

0 ≤ ≤ x ≤ u.
To prove box-TDIness, one has to show that if the dual given below has an optimal solution, then it also has an integer one.

(D)

         max z 1 -u z 2 circuit C e f ∈C\{e} y C,f -y C,e ≤ c e -z 1 e + z 2 e
for each e ∈ E, y ≥ 0, z 1 , z 2 ≥ 0.

The feasible set for (D) has the form Q = {z 1 , z 2 ≥ 0, y ≥ 0 : z 1z 2 + Ay ≤ c}, and its projection onto the space of z = (z

1 , z 2 ) ∈ R E×E is proj z (Q) = {z 1 , z 2 ≥ 0 : v z 1 -v z 2 ≤ v c, for each v ∈ K} where K is the projection cone K = {v ∈ R E : v A ≥ 0 , v ≥ 0}. Observe that K is the set of v ∈ R E satisfying the inequalities of the system (Cut cone). Since G is series-parallel, K is the cut cone of G [14]. Therefore proj z (Q) = {(z 1 , z 2 ) ∈ R E×E + : z 1 (D) -z 2 (D) ≤ c(D), for each cut D of G}.
The following claim states that proj z (Q) is an integer polyhedron. It is a direct corollary of a technical result whose statement and proof are postponed to the Appendix. Claim 2. proj z (Q) is integer whenever c is integer. Suppose (D) has an optimal solution. By Claim 2, there exists an integer optimal solution (z 1 , z2 ) of max z 1 -u z 2 over proj z (Q). We now build an optimal solution (ȳ, z1 , z2 ) of (D) as follows.

Let G ,H,c ,d). Hence, G + H = G being series-parallel, Theorem 8.1 of [START_REF] Seymour | Matroids and Multicommodity Flows[END_REF] implies that there exists a multiflow ŷ of (G , H, c , d). Define ȳ as follows:

ȳC,e := ŷP if b e ≤ 0 and P = C \ {e}, 0 otherwise.

By construction, (ȳ, z1 , z2 ) is an integer optimal solution of (D), and we are done.

(ii) ⇒ (iii): The system (Cycle cone) of a series-parallel graph is the system (Cut cone) of its planar dual which is also a series-parallel graph. As the latter system is box-TDI precisely for such graphs, we get the desired implication.

(iii) ⇒ (iv): In the following, Ax ≤ b is a system whose underlying polyhedron P = {x : Ax ≤ b} is pointed. The vertex system associated with a vertex z of {x : Ax ≤ b} is the system A z x ≤ b z composed of the inequalities of Ax ≤ b satisfied with equality by z. Suppose that all the vertex systems of P are box-TDI. Let F be a proper face of P and z be a vertex of F . Then, the active rows in A z x ≤ b z for the minimal face of {x : A z x ≤ b z } containing F are exactly the same as those in Ax ≤ b for F . Hence, by [2, Proposition 2.2], the set of active rows for F forms a box Hilbert basis. Since this holds for every face of P , [2, Proposition 2.2] implies that Ax ≤ b is box-TDI. The converse can be proved in a similar way.

Let T ⊆ V . Recall that vertices of the polytope defined by the system (T -join) correspond to T -joins of G, and conversely. Let J be any T -join of G. By Claim 3, it suffices to show that the vertex system of (T -join) associated with vertex J is box-TDI. Let φ J : R E → R E be defined by

[φ J (x)] e := 1 -x e if e ∈ J, x e if e ∈ E \ J.
The next two claims exhibit properties of φ J .

Claim 4. The system obtained from (Cycle cone) by replacing x by φ J (x) is the vertex system of ( T -join) associated with J.

Proof. Schrijver proves that replacing x by φ J (x) in the vertex system of (Tjoin) associated with J gives the system (Cycle cone) -see (29.61) to (29.63) page 506 in [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF] for the details. As φ J (φ J (x)) = x, the assertion follows.

Claim 5. Replacing x by φ J (x) preserves box-TDIness.

Proof. From the definition of box-TDI systems, it follows that replacing some coordinates by their opposite preserves box-TDIness. So does translation, see Theorem 5.34 in [START_REF] Schrijver | Combinatorial Optimization Polyhedra and Efficiency[END_REF].

The (Cycle cone) being box-TDI by (iii), Claims 4 and 5 imply the box-TDIness of the vertex system of (T -join) associated with J. Since this holds for any T -join J of G, Claim 3 gives the box-TDIness of (T -join).

(iv) ⇒ (v): We have already shown that (T -join) is box-TDI if and only if the graph is series-parallel. Recall that the cuts of a planar graph are the cycles of its planar dual, and that cycles are ∅-joins. Therefore, (Cut) is nothing but the system (∅-join) for the planar dual of the graph, and since planar duality preserves series-parallelness, we get that (iv) implies (v).

(ii) ⇒ (vi): This is immediate because (Multicut) is nothing but the box-TDI system (Cut cone) together with the box-constraints x ≤ 1.

(iv) ⇒ (vii): The system describing the T -join polytope being box-TDI, the TDI system (T -join dominant) describing its dominant is also box-TDIby Theorem 22.11 of [START_REF] Schrijver | Theory of linear and integer programming[END_REF].

Box-TDI systems have the remarkable property that any TDI system describing the same polyhedron is also box-TDI [START_REF] Cook | On box totally dual integral polyhedra[END_REF]. This gives the following consequence of Theorem 1. The minimal TDI system describing the T -join dominant given by Sebő [START_REF] Sebő | The Schrijver system of odd join polyhedra[END_REF] becomes box-TDI when the graph is seriesparallel.

Trader multiflow vs box-multicut

In this section, we first explain how the trader multiflow problem generalizes both the min-cost multiflow and maximum multiflow problems. We then provide a min-max relation involving the trader multiflow problem and the so-called box-multicuts. Finally, we briefly explain why the trader multiflow problem is polynomial in series-parallel graphs.

Related multiflow problems

Recall that an instance (G, H, c, d, , u) of the trader multiflow problem is composed of two simple undirected graphs G = (V, E) and

H = (V, R), a capacity c ∈ Z E + , a demand d ∈ Z R + , a profit ∈ Z R + and a cost u ∈ Z E + .
The trader multiflow problem aims at maximizing z 1 -u z 2 over all (y, z 1 , z 2 ) ∈

Z P + × Z R + × Z E + such that y is a multiflow of (G, H, c, d) with c = c + z 2 and d = d + z 1 .
This problem contains the maximum multiflow problem as a special case. Let (G,H,c,d,,u) be an instance of the trader multiflow problem with d = 0, = 1 and u = +∞. In any optimal solution (ȳ, z1 , z2 ), since u = +∞, we have z2 = 0, that is, capacities remain unchanged. Since d = 0 and = 1, the problem reduces to find z1 such that r∈R z1 r is maximum and there exists a multiflow in (G, H, c, z1 ). This is nothing but the maximum multiflow problem associated with (G, H, c).

The trader multiflow problem also contains the min-cost multiflow problem as a special case. Let (G, H, c, d, w) be an instance of the min-cost multiflow problem. It is transformed into an instance (G , H , c , d , , u ) of the trader multiflow problem as follows. Let G = (V , E ) be the graph obtained from G by subviding every link e ∈ E into two links e 1 , e 2 in series. Then, the amount of flow passing by e 1 equals the amount of flow passing by e 2 . Let c e 1 = c e and u e 1 = +∞. The capacity of e 1 is chosen in order to limit the value of the flow passing by e 1 , e 2 to c e . Let c e 2 = 0 and u e 2 = w e . The role of e 2 is to charge a fee w e for each unit of flow passing by e 1 , e 2 . Let H = (V , R), d = d and = 0. In an optimal solution (ȳ, z1 , z2 ) of the trader multiflow problem, we may suppose without loss of generality that z1 = 0 since = 0. Since u e 1 = +∞, the amount of flow passing by e 1 , e 2 is no more than c e 1 = c e . Since c e 2 = 0, for each unit of flow passing by e 1 , e 2 , one has to increase the capacity of e 2 by one at cost u e 2 = w e . Hence, ȳ defines a multiflow in (G, H, c, d) minimizing the total cost of the flow.

Min-max theorem

Given a graph and integer vectors and u indexed on its edges, the integer vectors x satisfying system (Cut cone) and ≤ x ≤ u are called box-multicuts within [ , u]. If we are also given a cost vector c defined on the edges, the minimum box-multicut problem seeks a box-multicut x within [ , u] of minimum cost c x.

Box-multicuts are a generalization of multicuts, these latter being boxmulticuts within [0, 1]. Box-multicuts also generalize separating multicuts, where, given a supply graph G and a demand graph H = (V, R), a separating multicut is a multicut of G + H containing R. Indeed, separating multicuts are box-multicuts of G + H within [ , 1] where equals 1 for every net of R and 0 otherwise.

The min-max relation between the trader multiflow and minimum boxmulticut problems given in the following Corollary 6 is a consequence of Theorem 1. Its statement uses the following notation: given a supply graph G = (V, E) and a demand graph H = (V, R) and two vectors v 1 ∈ Z E + and v 2 ∈ Z R + , the vector associated with the edges of G + H defined by v 1 and v 2 is denoted by (v 1 , v 2 ). Corollary 6. The maximum trader multiflow of (G, H, c, d, , u) equals the minimum box-multicut of G + H within [(0, ), (u, +∞)] with respect to costs (c, -d), if G + H is series-parallel. Proof. First, set ĉ = (c, -d), ˆ = (0, ) and û = (u, +∞). Consider the linear program (P ) of the proof of Theorem 1 where G, c, and u are replaced by G + H, ĉ, ˆ and û, respectively. Since ˆ e = 0, we may suppose, without loss of generality, that z1 e = 0 for all links e ∈ E in an optimal solution (ȳ, z1 , z2 ) of the dual (D). Moreover, as u r = +∞, z2 r = 0 for all nets r ∈ R. The dual can then be written as:

(D )                    max r∈R r z 1 r -e∈E u e z 2 e circuit C r y C,r - f ∈C\{r} y C,f ≥ d r + z 1 r for each r ∈ R, circuit C e f ∈C\{e} y C,f -y C,e ≤ c e + z 2 e
for each e ∈ E, y ≥ 0, z 1 , z 2 ≥ 0.

By strong duality, the optimal values of (P ) and (D ) are equal, when finite. In this case, we will show that there exists an integer optimal solution for both problems.

We may suppose that ȳC,f = 0 if f ∈ E. Otherwise, one may decrease ȳC,f by some > 0. If the solution becomes infeasible, then there exists a circuit C f and link f ∈ C \ {f } with ȳC ,f ≥ since c ≥ 0. Decreasing ȳC ,f by and increasing ȳC ,f by where C is the circuit of C∆C containing f restores its feasibility. Similarly, we may suppose that ȳC,f = 0 if C \ f intersects R. Thus, for every ȳC,f > 0, f ∈ R and C \ f ∈ P(r). Since G + H is series-parallel, system (Cut cone) is box-TDI and (ȳ, z1 , z2 ) may be assumed integer. The latter then corresponds to an optimal solution to the trader multiflow problem. Finally, since ˆ and û are integer, the box-TDIness of system (Cut cone) implies that the optimal solution of (P ) is integer, that is, a box-multicut of G + H within [ ˆ , û].

Min-max relations involving min-cost multiflow and maximum multiflow stem from Corollary 6 since the transformations described in Section 3.1 preserve series-parallelness. In particular, Corollary 6 implies that the two following min-max relations of [START_REF] Cornaz | Max-multiflow/min-multicut for G+H series-parallel[END_REF] that hold if G + H is series-parallel:

• the maximum multiflow equals the minimum separating multicut,

• the minimum multiflow loss equals the maximum multicut, where the minimum multiflow loss problem asks to remove a minimum number of demands of H to ensure the existence of a multiflow in G + H.

Applying the arguments used in the proof of (i) ⇒ (ii) of Theorem 1, it can be shown that optimizing over (D ) amounts to optimize over an integer polyhedron similar to proj z (Q). For series-parallel graphs, optimizing over such a polyhedron is polynomial-time solvable [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF][START_REF] Shih | Unifying Maximum Cut and Minimum Cut of a Planar Graph[END_REF]. It yields an increase of capacities and demands which maximizes the objective function and ensures that the cut condition is satisfied. Then, applying Theorem 8.1 of [START_REF] Seymour | Matroids and Multicommodity Flows[END_REF] provides an optimal solution to the trader multiflow problem. To sum up, we have the following complexity result. (G,H,c,d,,u) is polynomial-time solvable for all vectors and u and for all integer vectors c and d.

As seen in Corollary 7, our approach yields a polynomial algorithm, however it relies on the ellipsoid method. We conclude with the question: is there a combinatorial algorithm that solves the trader multiflow problem in series-parallel graphs? contradicting the extremality of p. Thus, for all e, either xe = 0 or ȳe = 0.

(A.5)

We can choose c so as to minimize the norm of p (e.g. Euclidean). Consequently, nonzero coordinates of p are fractional. Indeed, we have By (A.4) and by construction of series-parallel graphs, there are two edges ē and f in series. We may assume w.l.o.g. that bē ≤ b f . Since D = {ē, f } is a cut, we have b f ≥ -bē . Denote by p = (x, ŷ) ∈ R E\{ f }×E\{ f } the restriction of p to E \{ f }×E \{ f }, and let Ĝ be the graph obtained from G by contracting f , and ĉ the restriction of c to E \ { f }. Clearly, p belongs to P ( Ĝ, ĉ), and the latter is full-dimensional since neither loops nor bridges appeared in Ĝ.

0 ≤ p < 1, (
Moreover, since c is integer and p fractional, (A.3) and (A.5) imply that at least two edges have a fractional x or ȳ coordinate. Therefore p is fractional, and hence, by minimality of |E|, p is not an extreme point of P ( Ĝ, ĉ).

Remark that in fact we have:

b f = | bē | (A.7)
If it is not true, then p does not saturate the constraint associated to D, and moreover b f > bē . Hence, except maybe for x f = 0 or ȳ f = 0, the edge f appears in no equation among (A.1)-(A.3). Then p is an extreme point, a contradiction.

By the integrality of c, a direct consequence of (A.5)-(A.7) is that:

Exactly one of xē , ȳē is fractional ⇐⇒ exactly one of x f , ȳ f is fractional. (A.8) Since p is not extreme, there is a (nonzero) direction d = ( dx , dy ) ∈ R E\{ f }×E\{ f } and an ε > 0 such that Therefore, b+ ē = b+ f . By (A.9), choosing a small enough ε ensures the nonnegativity of p+ . Since p+ does not belong to P (G, c), we get that p+ violates x( D) -y( D) ≤ c( D), that is, b+ ē + b+ f = bē + b f + 2ε( dy ē -dx ē ) < 0, ∀ε > 0 (A.10)

Notice that exactly one of xē and ȳē is fractional, as otherwise (A.9) would imply dx ē = dy ē = 0, and then (A.10) would give the contradiction b( D) < 0. Consequently, we have bē + b f > 0, a contradiction to the fact that (A.10) holds for all > 0. This settles Case 1. In particular, p+ satisfies the constraint of the cut D, and since nonnegativity is ensured, then p+ violates the constraint of a cut D containing f but not ē, that is

  b := c -z1 + z2 . Then b is integer and satisfies b(D) ≥ 0 for each cut D of G. Define R as the set of all e ∈ E with b e ≤ 0 and E = E \ R. Let G = (V, E ) and H = (V, R). Let c ∈ Z E + and d ∈ Z R + be defined by c e = b e for all e ∈ E and d r = -b r for all r ∈ R. Then d(D ∩ R) ≤ c (D ∩ E ) for each cut D of G + H. In other words, the cut condition is satisfied in (

Corollary 7 .

 7 If G + H is series-parallel, then the maximum trader multiflow problem on

A. 6 )

 6 as otherwise, if xe ≥ 1 (resp. ȳe ≥ 1) for some edge e, then (A.1)-(A.3) would still be satisfied after resetting xe := xe -1 and c e := c e -1 (resp. ȳe := ȳe -1 and c e := c e + 1).

  ε • d) where both p + ε • d and p -ε • d belong to P ( Ĝ, ĉ). Extend the direction d = ( dx , dy ) ∈ R E\{ f }×E\{ f } to a direction d = ( dx , dy ) ∈ R E×E by arbitrarily defining the two missing components dx f and dy f ε • d) ∀ε > 0 where the points p+ = p + ε • d and p-= p -ε • d are different. Since p is extreme, we can assume that p+ = (x + , ȳ+ ) / ∈ P (G, c). Clearly, we have xē = 0 (resp. ȳē = 0) implies dx ē = 0 (resp. dy ē = 0). (A.9) Define b+ := c -x+ + ȳ+ . By (A.7), there are two cases. Case 1: bē = b f ≥ 0d, and by (A.8)-(A.9), we have b+ē -bē = (ȳ + ē -ȳē ) -(x + ē -xē ) = ε( dy ē -dx ē ) = (ȳ + f -ȳ f ) -(x + f -x f ) = b+ f -b f .

Case 2 :

 2 bē = -b f < 0d, and by (A.8)-(A.9), we have b+ē -bē = ε( dy ē -dx ē ) = (x + f -x f ) -(ȳ + f -ȳ f ) = b f -b+ f . Therefore, b+ f = -b+ ē .

  b+ (D) = b(D) + ε( dy (D) -dx (D)) < 0 (∀ε > 0) (A.11) Since D = D ∪ {ē} \ { f } is a cut, we have b(D ) ≥ 0, thus b(D) = b(D )bē + b f > 0. This contradiction to (A.11) finishes the proof.

  Claim 3. The system Ax ≤ b is box-TDI if and only if the vertex system associated with each vertex of P = {x : Ax ≤ b} is box-TDI.Proof. Cook proves that a system is box-TDI if and only if, for each face F of the associated polyhedron, the set of active rows for F forms a box Hilbert basis [2, Proposition 2.2].

allowed to take infinite values

Acknowledgment

The very careful reading of the paper by an anonymous referee has allowed an improvement of several technical proofs readability, we would like to thank her or him very much.

Appendix A.

The proof of Theorem 1 is based on Claim 2 which is a direct consequence of the following result. Proof. Necessity. First, note that P ( Ĝ, ĉ) has a fractional extreme point if Ĝ is the complete graph K 4 with cost ĉe = -1 on the three edges of a triangle and ĉe = +1 on the remaining star. Indeed, the point p = (x, ŷ) defined by ŷe = 1/2 for the edges of the triangle and zero elsewhere is the unique optimal solution of maximizing ˆ x -û y over P ( Ĝ, ĉ), where ˆ is zero and û is the all-one vector. Now, let Ḡ be a graph which is not series-parallel, then, by [START_REF] Duffin | Topology of series-parallel networks[END_REF], it has a K 4 -minor, that is we can remove and contract some edges of Ḡ to obtain K 4 . Let us extend (ĉ, ˆ , û) to (c, ¯ , ū) by defining ¯ e = -∞ and ūe = +∞ for the new edges e, with ce = +∞ if e must be contracted, and ce = 0 if it must be deleted. Clearly, the point p obtained by extending p with zero components is the unique optimal solution of maximizing ¯ x-ū y over P ( Ḡ, c). Sufficiency. By contradiction, let (G, c) be a counter-example with a minimum number of edges. Throughout, p = (x, ȳ) will denote some fractional extreme point of P (G, c) and b := c -x + ȳ.

Note that b(D) ≥ 0, for each cut D.

First, note that G has no loops or bridges. Indeed, a loop belongs to no cut, and a bridge e appears exactly in three nonredundant constraints, namely x e ≥ 0, y e ≥ 0 and y e -x e ≥ c e , two of which are satisfied with equality by any extreme point.

Moreover, P (G, c) is full-dimensional. To see this, observe that the point p = (x, y) ∈ R E×E defined by x e = 1 and y e = +∞ for all e ∈ E belongs to P (G, c). Moreover, for each edge e ∈ E, the point p x e (resp. p y e ) obtained from p by resetting x e to zero (resp. y e to zero) also belongs to P (G, c) since each cut has size at least two. The 2|E| + 1 points p, p x e , p y e , for e ∈ E, are affinely independent, hence the dimension of P (G, c) is 2|E|.

In consequence, the point p is the solution of a system of 2|E| equations of the following type, where the left-hand-side forms a full-rank matrix. xe = 0 for some edges e, (A.1) ȳe = 0 for some edges e, (A.2) x(D) -ȳ(D) = c(D) for some bonds D = ∅.

(A.3) Suppose G has two parallel edges ē and f . Then, replacing (x ē, ȳē ) by (x ē, ȳē ) + (x f , ȳ f ) and (x f , ȳ f ) by (0, 0) yields a feasible point (x, ỹ) because ē and f belong to the same cuts. This point (x, ỹ) satisfies all the equations (A.1)-(A.3) except possibly the equations (A.1) and (A.2) associated with ē. But these two equations are not satisfied only if x f > 0 or ȳ f > 0 respectively. This implies that (x, ỹ) satisfies 2|E| equations among (A.1)-(A.3), x f = 0, and ȳ f = 0. Hence, it is also an extreme point of P (G, c). Therefore resetting c ē := c ē + c f and removing f gives a counter-example with a smaller number of edges, a contradiction. We have just proved the following.

G has no parallel edges.

(A.4)

Note that, if both xe > 0 and ȳe > 0 for some edge e, then one could reset xe := xe -ε and ȳe := ȳe -ε (for some ε > 0) and still satisfy (A.1)-(A.3),