SUPER-RESOLUTION TECHNIQUES FOR GPS, RADAR ANDWIRELESS COMMUNICATIONS

(1)

SUPER-RESOLUTION TECHNIQUES FOR GPS, RADAR AND WIRELESS COMMUNICATIONS

梁, 同信

https://doi.org/10.15017/2534458

出版情報：九州大学, 2019, 博士（工学）, 課程博士バージョン：

権利関係：

(2)

COMMUNICATIONS

Author:

Dongshin YANG

Supervisor:

Dr. Yutaka JITSUMATSU

A doctoral dissertation submitted in fulfillment of the requirements for the degree of Doctor of Philosophy in Engineering

in the

Circuits, Systems, and Communication Networks Laboratory Department of Informatics

2019

(3)

Declaration of Authorship

I, Dongshin YANG, declare that this doctoral dissertation titled, “SUPER-RESOLUTION TECHNIQUES FOR GPS, RADAR AND WIRELESS COMMUNICATIONS” and the work presented in it are my own. I confirm that:

• This work was done wholly or mainly while in candidature for a research degree at this University.

• Where any part of this doctoral dissertation has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated.

• Where I have consulted the published work of others, this is always clearly attributed.

• Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this doctoral dissertation is entirely my own work.

• I have acknowledged all main sources of help.

• Where the doctoral dissertation is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself.

Signed:

Date:

(4)

“SUPER-RESOLUTION TECHNIQUES FOR GPS, RADAR AND WIRELESS COM- MUNICATIONS”a dissertation prepared by Mr. DONGSHIN YANG in partial fulfillment of the requirements for the degree, Doctor of Philosophy in Engineering, has been approved and accepted by the following:

—————————————————————————————————————

Associate Prof. Yutaka Jitsumatsu, Chairman of the Examining Committee

—————————————————————————————————————

Prof. Jun’ichi Takeuchi

—————————————————————————————————————

Associate Prof. Osamu Muta

—————————————

Date

Committee in Charge:

Associate Prof. Yutaka Jitsumatsu Prof. Jun’ichi Takeuchi

Associate Prof. Osamu Muta

(5)

KYUSHU UNIVERSITY

Abstract

Graduate School and Faculty of Information Science and Electrical Engineering Department of Informatics

Doctor of Philosophy in Engineering

SUPER-RESOLUTION TECHNIQUES FOR GPS, RADAR AND WIRELESS COMMUNICATIONS

by Dongshin YANG

The fourth industrial revolution built on the digital revolution is marked by emerg- ing technology breakthroughs in a number of fields, including robotics, Artificial Intelligence (AI), fifth generation (5G) wireless technologies, the Internet of Things (IoT), and autonomous vehicles. Location information and reliability of wireless communication are important factors to realize these technologies.

A purpose of channel estimation processes for wireless communications, radar, and GPS is to improve location information accuracy and reliability of wireless communication. To improve channel estimation accuracy, we especially discuss finer quantities than the accuracy of one unit time/one unit frequency when continuous parameters are discretized.

Several channel estimation methods are discussed in this doctoral dissertation such as Least Square (LS), Compressed Sensing (CS), line spectral estimation (Prony’s method and annihilating filter), and Atomic Norm Minimization (ANM).

We provide an overview of related technologies such as radar, Orthogonal Fre- quency Division Multiplexing (OFDM), Spread Spectrum (SS) communications. In addition, Multiple Input and Multiple Output (MIMO) is explained for future works.

Conventional LS-based methods have been applied to channel estimation. How- ever, some researchers presented that CS-based channel estimation was better than LS-based channel estimation. We focus on application of CS. CS is largely accepted for sparse channel estimation and its variants. We present the fundamental concept of CS and give an overview of its application to pilot-aided channel estimation.

However, conventional CS uses finite size dictionaries. Therefore, conventional CS- based channel estimation methods have the grid problem. In this paper, we take two approaches to solve the grid problem, realizing better resolution than the conventional CS-based methods.

In the first part of this study, we improve the accuracy of channel estimation by an upsampling CS-based channel estimation method. Dividing grids by using the upsampling technique can improve accuracy for channel estimation. The performance of channel estimation method depends on the SS codes. To investigate the effect of SS codes, we compare the channel estimation performance of Markov codes with independent and identically distributed (i.i.d.) codes. We show that Markov codes can improve accuracy of channel estimation. The simulation results show that accuracy of our proposed method is better than nonupsampling CS-based channel estimation. However, calculation time increases as the upsampling rate increases, whereas the performance improvement becomes slight if very large upsampling rate is employed.

(6)

signals can be extended to GPS that uses Gold codes.

In summary, this paper contributes the channel estimation in wireless communication, radar, and GPS. We solve the grid problem for systems using SS signals by upsampling and ANM methods and realize super-resolution channel estimation.

We expect that our proposed methods can be extended to other communication systems such as MIMO and Synthetic Aperture Radar (SAR) systems.

(7)

Publicaion List

Conference papers

D. Yang, T. Higuchi and Y. Jitsumatsu, Optimal Reference Block Partitions for Mul- tipath Fading Channels with Doppler Shift, The Third International Japan-Egypt Conference on Electronics, Communications and Computers, 2015.3. Pages 120-121.

S. Ito, D. Yang and Y. Jitsumatsu, Estimation of Multi-path Channels by Using the Annihilating Filter Method, The 2015 IEEE 82nd Vehicular Technology Conference, 2015.9. Pages 1-5.

D. Yang and Y. Jitsumatsu, Parameter Discritization Problem in Channel Estimation Method Based on Compressed Sensing, IEICE, General Conference 2016, 2016.3.

Pages A-8-20.

D. Yang and Y. Jitsumatsu, Discretization in Channel Estimation Using Compressed Sensing and Its Performance Improvement, The 13th IEEE Vehicular Technology Society Asia Pacific Wireless Communications Symposium, 2016.8. Pages 474-478.

D. Yang and Y. Jitsumatsu, Compressive Sensing of Up-Sampled Model and Atomic Norm for Super-Resolution Radar, International Radar Symposium 2017, 2017.6.

Pages 1-9.

D. Yang and Y. Jitsumatsu, Channel Estimation by Using Spread Spectrum Signal and Atomic Norm Minimization, The 40th Symposium on Information Theory and its Applications, 2017.11. Pages 576-581.

D. Yang and Y. Jitsumatsu, Super Resolution Channel Estimation with Spread Spec- trum Signal and Atomic Norm Minimization, 2018 International Symposium on Information Theory and its Applications, 2018.10. Pages 144-148.

Journal papers

D. Yang and Y. Jitsumatsu, Dividing the grids of compressed sensing for channel estimation and investigating Markov codes, Nonlinear Theory and Its Applica- tions, IEICE, Special issue on The second step of the FIRST, 2018.4. Volume 9, Issue 2, Pages 259-267.

D. Yang and Y. Jitsumatsu, Super Resolution Channel Estimation by Using Spread Spectrum Signal and Atomic Norm Minimization, Special Section on Information Theory and Its Applications, 2018.12. Volume E101.A, Issue 12, Pages 2141-2148.

(8)

formatics, for his guidance and boundless support during my research and study in Kyushu University. His enthusiasm and perpetual energy in research had motivated all his advises, including me.

I am deeply indebted toProf. Dr. Jun’ichi Takeuchi, in the Graduate School and Faculty of Information Science and Electrical Engineering, Kyushu University, for his continuous advices and guidance in everything during my study.

I express my deep thanks toAssociate Prof. Dr. Osamu Mutain the Department of Electrical Engineering and Computer Science, School of Engineering, Kyushu University, for his kind support and advice.

Special thanks are further extend toProf. Dr. Kazushi Mimura,from Faculty of Information Sciences, Hiroshima City University, I appreciate his valuable discus- sions and advices.

I would like to express the deepest appreciation toDr. Masanori Kawakitawho was assistant professor until March 2018, for his kind support and advice.

I record my thanks to all of my laboratory members and all of my colleagues in Kyushu University for their kind cooperation and warm relationship.

Finally, I take this opportunity to express my profound gratitude to my beloved family for their patience and support during my study in Kyushu University.

(9)

List of Figures

1.1 Channel of wireless communication . . . 2

1.2 Multipath propagation . . . 3

1.3 Radar multipath echoes from an actual target cause ghosts to appear . 3 1.4 Location error in GPS . . . 4

1.5 Image of channel . . . 5

1.6 Narrowband versus wideband channel frequency response . . . 6

1.7 The grid problem . . . 7

2.1 Depiction of a Fourier transform . . . 10

2.2 band-limited baseband signal of spectrum as a function of frequency . 11 2.3 FiniteNsamples with truncation error . . . 14

2.4 The relation betweenx⁽^T⁾(nTs)andX⁽^N^T⁾(_T^k) . . . 15

2.5 Geometrical concept ofl₁-minimization . . . 19

3.1 Block diagram of a simple radar system . . . 21

3.2 Spectrum difference of FDM and OFDM on frequency domain . . . 22

3.3 Subcarriers spacing for OFDM . . . 23

3.4 Markov chains of two-state transition . . . 24

3.5 Antenna configuration of MIMO and SISO . . . 25

3.6 MIMO system with multipath channel . . . 27

4.1 Application of multiple access interference concept . . . 29

4.2 Simplified communication system model . . . 29

4.3 The channel impulse response estimated by DS . . . 31

4.4 A simple two-state(+1,−1)Markov chains state transition diagram . . 32

4.5 The delays span between the grids were estimated by DS . . . 34

4.6 Comparing calculation time with up-sampling factor . . . 34

4.7 Comparing MSE of Markov chain code with MSE of i.i.d. code (N₀=32) 35 4.8 MSE versus SNR between Markov chain code and i.i.d. code . . . 36

4.9 Different results byaandN₀ . . . 36

4.10 The effect ofN₀between Markov chain code and i.i.d. code(λ=−0.4) . 37 5.1 The continuous-time representation of SS system . . . 40

5.2 Comparison between estimation of CIR by the LS and the DS . . . 47

5.3 Grid problem with DS . . . 47

5.4 Compare the the ANM with the DS . . . 48

5.5 MSE versus SNR . . . 49

5.6 Gold code (code length is 31) . . . 49

5.7 Gold code (code length is 63) . . . 50

5.8 MSE of Gold code and i.i.d code . . . 50

5.9 Calculation times at one execution . . . 51

5.10 Results of channel estimation by DS, DSUP, and ANM . . . 51

5.11 MSEs of DS, DSUP, and ANM . . . 52

(12)

(13)

List of Tables

4.1 Simulation parameters . . . 33 5.1 Simulation parameters . . . 46

(14)

5G 5thGeneration AF AnnihilatingFilter AI ArtificialIntelligence AoA AngleofArrival AoD AngleofDeparture

ANM AtomicNormMinimization AWGN AdditiveWhiteGaussianNoise BER BitErrorRate

BP BasisPursuit

BPDN BasisPursuitDeNoising CDMA CodeDivisionMultipleAccess CS CompressedSensing

CIR ChannelImpluseResponse CSI ChannelStateInformation DFT DiscretFourierTransfromation DS DantzigSelector

ESPRIT Estimation ofSignalParameters viaRotationalInvarianceTechniques FDM Frequency-DivisionMulitiplexing

GPS GlobalPositioningSystem

IDFT InverseDiscretFourierTransfromation i.i.d. independentidenticallydistributed IoT InternetofThings

ISI InterSymbolInterference LFSR LinearFeedbackShiftRegister LMMSE LinearMinimumMeanSquareError LOS LineOfSight

LS LeastSquare

MAI MultipleAccessInterference

MIMO MultipleInput andMultipleOutput MP MatchingPursuits

MSE MeanSquareError

MUSIC MUltipleSIgnalClassification

OFDM OrthogonalFrequency-DivisionMultiplexing OMP OrthogonalMatchingPursuit

PLL PhaseLockLoop PN PseudoNoise RoI RateofInnovation RRC RootRaisedCcosine SAR SyntheticApertureRadar SDP SemidefiniteProgramming SISO SingleInputSingleOutput

(15)

SNR Signal-to-NoiseRatio SS SpreadSpectrum

SSMA SpreadSpectrumMultipleAccess SVD SingularValueDecomposition

(16)

The fourth industrial revolution built on the digital revolution is marked by emerg- ing technology breakthroughs in a number of fields, including robotics, Artificial Intelligence (AI), fifth generation (5G) wireless technologies, the Internet of Things (IoT), and autonomous vehicles. Significance of location information and reliability of wireless communication is one of factors to realize robotics, IoT, autonomous vehicles, and 5G wireless technologies. Channel estimation processes for wireless communications, radar, and GPS are to improve location information accuracy and reliability of wireless communication. In this chapter, we present concept of channel estimation and related multi path propagation for radar, GPS, and wireless communications. Besides, we describe our motivation and our contribution for this doctoral dissertation.

1.1 Channel estimation overview

In wireless communication, the transmitted signals are distorted by the channel and various noise are added to the signals. Fig.1.1 shows channel of wireless communication. There are some differences between transmitted signals and received signals, because of noise, attenuation, and phase-shift throughout channel.

To properly decode the received signal with as small number of errors as possible, we need to remove the distortion and noise applied by the channel from the received signal. Hence, it is necessary to mitigate the channel distortion in an effi- cient way.

The first step is to figure out the characteristics of the channel that the signal has gone through. The technique to characterize the channel is called channel estimation. The performance and capacity of wireless communication system are directly influenced by the speed and precision of channel estimation. There are many different ways for channel estimation [Bajwa et al., 2010]. In training-based channel estimation methods, the transmitter multiplexes signals (training signal) that are known to the receiver with data-carrying signals in time, frequency, and/or code domain, and channel state information (CSI) is obtained at the receiver from knowledge of the training and received signals. On the other hand, in blind channel estimation methods, CSI is acquired at the receiver by making use of the statistics of data-carrying signals only.

(17)

FIGURE1.1: Channel of wireless communication

1.2 Multipath propagation

1.2.1 Multipath on wireless communication

Multipath propagation affects most forms of wireless communications links in one form or another. Causes of multipath include atmospheric ducting, ionospheric refection and refraction, and refection from water bodies and terrestrial objects such as mountains and buildings [Goldsmith, 2005]. The effects of multipath include constructive and destructive interference, and phase shifting of the signal. Multipath can cause errors and affect the quality of communications. A simple receiver cannot distinguish between the different multipath signals. Quite likely, this causes many of the same signals to arrive at the receiver at different times. It just adds them up, so that they interfere with each other. The interference between them can be destructive or constructive, depending on the phases of the multipath signals. As shown in Fig.1.2, the phases, in turn, depend mostly on the runlength of the multipath signals, and thus on the position of the transmitted antenna and the received antenna. For this reason, the interference, and thus the amplitude of the total signal, changes with time if either the transmitted antenna or the received antenna are moving.

(18)

FIGURE1.2: Multipath propagation

1.2.2 Multipath on radar

In radar processing, multipath causes ghost targets to appear, deceiving the radar receiver [Leigsnering, 2018]. These ghosts are particularly bothersome since they move and behave like the normal objects (which they echo), and so the receiver has difficulty in isolating the correct object echo. Fig.1.3 shows a situation where radar signals echo from the same position through multiple paths. If the radar signal echoes from its destination to the sensor via the shortest path, there will be no problem getting information about the target, but in real situations, each path expe- riencing different delay and some arriving out of "phase". This "multipath" behavior generally reduces quality and introduces distortion to the signal. This is cause of the ghost targets.

FIGURE 1.3: Radar multipath echoes from an actual target cause ghosts to appear

(19)

1.2.3 Multipath on GPS

Global Positioning System (GPS) receivers receive signals from the satellites (at least 4 are needed) and use these signals to determine their location. Multipath propagation is the corruption of a direct GPS signal by one or more signals reflected from surfaces near the receiver [Van Sickle, 2008].

Fig.1.4 shows location error in GPS. The signal of GPS may bounce off various local obstructions before it gets to a receiver. Therefore, location error occurs because of multipath. It is well known that location error increases in urban areas due to multipath caused by buildings.

FIGURE1.4: Location error in GPS

1.2.4 Mathematical model of the multipath

The mathematical model of the multipath can be presented using the method of the channel impulse response used for studying linear systems. When a user or reflectors is moving, the user’s velocity causes a shift in the frequency of the signal transmitted along each signal path. This phenomenon is known as the Doppler shift. In this paper, we focus on channel estimation for delay. Ideal Dirac pulse of electromagnetic power at time 0, is given by

x(t)=δ(t) (1.1)

At the receiver, due to the presence of the multiple electromagnetic paths, more than one pulse will be received and each one of them will arrive at different times. In fact, since the electromagnetic signals are transmitted at the speed of light, and since every path has a geometrical length possibly different from that of the other ones, there are different transmitted times. Thus, the received signal will be expressed by mathematical model of the multipath can be presented using the method of the channel impulse response used for studying linear systems.

(20)

FIGURE1.5: Image of channel

Fig.1.5 shows the channel impulse response. The received signal will be expressed by

y(t)= h(t)=

∑K k=1

ckδ(t−tk), (1.2)

wherey(t)also represents the impulse response functionh(t)of the equivalent multipath model,K is the number of paths, ck is complex amplitude, andtk is the time delay of the generick^th.

Rapid phase changes in each multipath parts gives rise to constructive and destructive addition of the multipath parts comprising the received signal, which in turn causes rapid variation in the received signal strength. This phenomenon is also called fading.

Channel delay spread is dependent on the propagation environment. If the signal propagates along a straight line between the transmitter and receiver, the channel model associated with this transmission is called a line-of-sight (LOS) channel, and the corresponding received signal is called the LOS signal.

The impact of multipath on the received signal depends on whether the spread of time delays associated with the LOS and different multipath parts is large or small relative to the inverse signal bandwidth. If this channel delay spread is small then the LOS and all multipath components are typically non-resolvable, leading to the narrowband fading model. The narrowband means the delay spreadT_mof a channel is small relative to the inverse signal bandwidth B of the transmitted signal. The narrowband assumption isT_m<< _B¹.

When the signal is not narrowband we get another form of distortion due to the multipath delay spread. In this case a short transmitted pulse of durationT will result in a received signal that is of durationT+T_m, whereT_mis the multipath delay spread.

Fig.1.6 shows narrowband versus wideband channel frequency response. The narrowband or wideband depends on the relation between channel properties and system bandwidth. It is not an absolute measure. A narrow-band system (band- widthB₁) will not experience any significant frequency selectivity or delay dispersion. A wide-band system (bandwidthB₂) will however experience both frequency selectivity and delay dispersion. Narrowband and wideband communications channels make use of available bandwidth in different ways.

(21)

FIGURE 1.6: Narrowband versus wideband channel frequency response

1.3 Motivation

The channel state information (CSI) makes it possible to adapt transmissions to cur- rent channel conditions, which is important for achieving reliable communication with high data rates in wireless communication systems.

Bajwaet al [Bajwa et al., 2010] proposed channel estimation methods based on Compressed Sensing (CS) to estimate CSI. CS is a sensing modality, which com- presses the signals being acquired at the time of sensing [Donoho, 2006]. The signals can have compressible representation or sparse either in original domain or in some transform domain. Relying on the sparsity of the signals, CS allows us to sample the signal at a rate much below the Nyquist sampling rate. In addition, the varied reconstruction algorithms of CS can faithfully reconstruct the original signal back from fewer compressive measurements. Channel estimation accuracy of CS is markedly superior to that of the conventional methods based on Estimation of Signal Parame- ters via Rotational Invariance Techniques (ESPRIT) algorithms and MUltiple SIgnal Classification (MUSIC) [Harry and Trees, 2002]. However, there is a problem in the method that delays may not be resolved if they span between the grids. This problem is called the grid problem. This problem leads to inaccurate channel estimation. Fig.1.7 shows the grid problem. The horizontal-axis shows time delay (t), and the vertical-axis shows Channel Impulse Response (CIR). There are three true delays. Only two delays(c1,c₂)on grid could be accurately estimated. There is one mismatched estimation for the actual delay between the grids. This is because Ba- jwa’s method adopted a discretization procedure to reduce the continuous parameter space to a finite set of grid points. Our research purpose is to overcome this grid problem.

1.4 Major contributions

In order to support our doctoral dissertation, we have developed new theory and methods in the dissertation for some of the fundamental problems.

Firstly, upsampling is a common technique for mitigating the grid problem. The advantage of upsampling is the simplicity of the system configuration, while computational cost is increased as the upsampling ratio is increased [Yang and Jitsumatsu, 2018a]. We investigated CS by using upsampled model. The result shows that accuracy of upsampled model is better than nonupsampled model.

(22)

FIGURE1.7: The grid problem

Secondly, the Atomic Norm Minimization (ANM) provides a way for estimat- ing unknown continuous signals with few sensors by solving convex optimization problems. The concept of the ANM is introduced in [Chandrasekaran et al., 2012].

Bhaskaret alpresented a method of line spectral estimation using ANM method [Bhaskar, Tang, and Recht, 2013]. ANM method can estimate continuous parameter. In addition, the line spectral estimation is applicable to the communication and radar field because of similarity with the estimation. Pejoski presented an OFDM system with pilot-aided channel estimation by using ANM [Pejoski and Kafedziski, 2015]. Reso- lution of ANM method is very high since ANM is based on infinite dictionary. Fur- thermore, GPS and radar detection methods are resemble to channel estimation for wireless communications, therefore, the ANM can be applied for the two systems.

Thirdly, we develop new ANM for Spread Spectrum (SS) signals. The SS-based multiple access, such as CDMA, has been chosen for 3rd Generation (3G) wireless communications. Other applications of SS techniques are in wireless LAN (IEEE 802.11a, IEEE 802.11b, IEEE 802.11g), Bluetooth, radar, and Global Positioning Sys- tem (GPS) [Rappaport et al., 2002][Ström, Ottosson, and Svensson, 2002].

SS signal is transmitted on a bandwidth considerably larger than the frequency content of the original information. SS signal is used for the establishment of se- cure communications, increasing resistance to interference, noise and jamming, to prevent detection. SS signals are intentionally made to be a much wider band than the information they are carrying to make them more noise-like. The use of special pseudo noise (PN) codes in SS communications makes signals appear wide band and noise-like.

Finally, we investigate Markov codes, independent and identically distributed (i.i.d.) codes, and Gold codes. The performance of channel estimation may differ depending on the codes. Therefore, we compared (i.i.d.) codes, Markov chain codes, and Gold codes. Accuracies of Markov codes are more accurate than i.i.d. codes.

Gold codes are used GPS. We show our new ANM for SS signal systems can apply GPS systems.

1.5 Notational convention

We present some general notations that we use coherently throughout this dissertation. Any exceptions to this notational convention, while rare, are explicitly men- tioned in the body of the dissertation. We use bold-faced, upper-case letters, such as Ato denote matrices. Similarly, we use bold-faced, lower-case letters, such asxand

(23)

y, to denote vectors. Furthermore, unless explicitly stated, we take all the vectors to be column vectors. We use the superscripts(·)^T and(·)^H to denote the operations of transposition, conjugate transposition (Hermitian conjugate).

1.6 Organization of this doctoral dissertation

The rest of this dissertation is organized as follows. In Chapter 2, we briefly review the key mathematical fundamentals that are the most relevant to our discussion. We review Fourier transform, band-limited signals, baseband equivalent and passband signals, Nyquist-Shannon sampling theorem, discrete Fourier transformation, line spectral estimation (Prony’s method, annihilating filter), and Compressed Sensing (CS).

In Chapter 3, we present overview of related technologies. More specifically, radar, OFDM, SS communications, GPS, MIMO, several PN codes are also described.

In Chapter 4, we describe drawbacks of discretization of CS. In addition, we propose CS-based channel estimation using upsampling signals and investigating i.i.d codes and Markov codes. We conducted numerical simulation such as calculation time, Mean Square Error (MSE), Signal-to-Noise Ratio (SNR), and effect of code length.

In Chapter 5, we describe concept of infinite dictionary. Atomic Norm Minimiza- tion (ANM) is presented as a sparse signal recovery method using an infinite dictionary. We develop and analyze ANM with an SS signal. We compare conventional methods such as Least Square (LS) and CS with ANM. In addition, we investigate Gold codes for GPS. We conducted numerical simulation such as MSE, SNR, and calculation time.

Finally, in Chapter 6, our conclusion and future works are described.

(24)

In this chapter, we discuss resolution enhancement of wireless communication and radar signal processing. We discuss finer quantities than the accuracy of one unit time/one unit frequency when continuous parameters are discretized. Therefore, it is important to accurately describe the difference between the Fourier transform of a continuous time signal and the discrete Fourier transformation (DFT) obtained by discretizing the continuous time signal without neglecting the difference. This chapter gives definitions of continuous and discrete time signal Fourier transforms [Schoen- stadt, 2006]. We also discuss sampling theorem and describe aliasing of the spectrum when the signal is not band-limited.

2.1 Fourier transform

Definition 1 Let x(t) be a continuous-time, complex-valued signal with finite energy, i.e.

∫_∞

−∞|x(t)|²dt< ∞. The Fourier transform ofx(t)is defined by X(f)= F [x(t)]=

∫ _∞

−∞ x(t)e⁻^j2π^{f t}dt. (2.1) The inverse Fourier transforms ofX(f)is defined by

x(t)=F⁻¹[X(f)]=

∫ _∞

−∞X(f)e^j2π^{f t}df. (2.2) Although the notationX(ω)is often used with the angular frequencyω=2πf, it is represented asX(f)in this paper.

Letx^(T⁾(t)be a periodic function with a period ofT. x^(T⁾(t)can be expanded as a Fourier series:

x⁽^T⁾(t)= ∑^∞

n=−∞

C_ne^j^2π^T^nt, (2.3)

where Fourier coefficientCnis given by Cn= 1

T

∫ _T

0

x⁽^T⁾(t)e⁻^j^2π^T ^ntdt. (2.4) Dirac’s delta function is normally symbolized byδ(t)and represents an “instantaneous” force, such as occurs in the inelastic collision between billiard balls. the simplest instantaneous force to consider would seem to one acting att=0 and with unit area - this, of course, becomes what we callδ(t), or the unit impulse. Most texts usually generateδ(t)as the limit of a set of even rectangular pulses of unit area and continually smaller duration (and hence proportionally growing amplitudes). As

(25)

their limit,δ(t)will thus have infinite amplitude att=0 and be 0 elsewhere [Schoen- stadt, 2006].

Dirac’s delta function is defined by the following property δ(t)=

{ 0,t,0

∞,t=0 (2.5)

The important property of the delta function is the following relation:

∫ _∞

−∞ f(t)δ(t)dt = f(0) (2.6) for any continuous function f(t). Delta functionδ(t)satisfies

F⁻¹[δ(f− f₀)] =

∫ _∞

−∞δ(f − f₀)e^j2π^{f t}df

= e^j2π^f⁰^t. (2.7)

Therefore the Fourier transform of Eq.(2.3) is given by F [x⁽^T⁾]=∑^∞

−∞

Cnδ(f− n

T). (2.8)

This shows thatx⁽^T⁾has a discrete spectrum.

Furthermore, assume thatx⁽^T⁾(t)is constructed fromx(t)by x⁽^T⁾(t)= ∑^∞

k=−∞

x(t−kT). (2.9)

Then, from Eq.(2.4), we have C_n = 1

T

∫ _T

0

∑∞ k=−∞

x(t−kT)e^−j^2π^T^ntdt

= 1 TX(n

T) (2.10)

Fig.2.1 shows depiction of Fourier transforms ofx(t)andx⁽^T⁾(t).

FIGURE2.1: Depiction of a Fourier transform

(26)

X(f)=0 for |f|>W. (2.11) Fig.2.2 shows example of a band-limited baseband signal spectrum as a function of frequency.

FIGURE2.2: band-limited baseband signal of spectrum as a function of frequency

2.3 Baseband equivalent and passband signals

Let the baseband signal bex_B(t). LetWbe the bandwidth of x(t). Then,

XB(f)=F [xB(t)]=0 for |f| >W. (2.12) The passband signal isxB(t)multiplied by sinusoidal wave, given by

x_P(t)=x_B(t) ×cos(2πf_ct+ϕ0), (2.13) where f_c is a carrier frequency and ϕ0 is an initial phase. The sinusoidal wave is generated by an oscillator circuit. Usually,ϕ0can not be controlled and is considered to be uniformly distributed in[0, 2π]. On the receiver’s side, xP(t)is multiplied by the sinusoidal wave with the same f_c andϕ0as the transmitter. x_B(t)is restored by cutting double frequency components. In other words,

ˆ

x_B(t) = 2LPF[x_P(t) ·cos(2πf_ct+ϕ0)]

= 2LPF[xB(t) ·cos²(2πfct+ϕ0)]

= 2LPF[xB(t) ·1+cos(4πfct+ϕ0)

2 ] (2.14)

≑ x_B(t). (2.15)

(27)

The receiver needs to use the same fcandϕ0used by the transmitter. The estimation and tracking of f_candϕ0are performed by a Phase Lock Loop (PLL) circuit.

ThexP(t)is transmitted by

x_P(t) = x_I(t)cos(2πf_ct+ϕ0) −x_Q(t)sin(2πf_ct+ϕ0) (2.16) wherex_I(t)andx_Q(t)are a real number function of baseband.

In receiver side, Thex_I(t)and the x_Q(t)are reconstructed by ˆ

x_I(t) = 2LPF[x_P(t)cos(2πf_ct+ϕ0)]

ˆ

xQ(t) = 2LPF[xP(t)sin(2πfct+ϕ0)]. (2.17) Therefore, Eq.(2.16) can represent as

xP(t)=ℜ[xI(t)+j xQ(t)e^j⁽²^π^f^c^t^+ϕ⁰⁾], (2.18) wherex_I(t)+ j x_Q(t)are called complex passband signal. Furthermore,x_I(t)is called in-phase, andxQ(t)is called Q-phase (quadri-phase) componets ofxP(t).

2.4 Nyquist-Shannon sampling theorem

Nyquist-Shannon sampling theorem is quantitatively indicates how often sampling should be done when converting an analog signal to a digital signal. This theorem is one of the very important theorems in the field of information theory. According to this theorem, sampling at a frequency exceeding twice the maximum frequency of the waveform completely reconstructs the original waveform. Mathematically ideal way to interpolate signals involves the use of sinc function.

Theorem 1 Ifx(t)contains no frequencies higher thanW[Hz], it is completely determined by sampled valuex(nTs)at spaced _2W¹ sampling apart. x(t)is reconstructed fromx(nTs)by specificity

x(t) = ∑

n

x(xT_s)sinc( t

Ts −n), (2.19)

where

sinc(t) = sinπt

πt . (2.20)

2.5 Discrete fourier transformation

Instead of regarding as sampled values of a continuous signal and sampled value of its Fourier transform, we may think of the Discrete Fourier Transform (DFT) as an operation that accepts as input-output a list ofN numbers. For a given finite energy signalx(t), let us consider a periodic signal x⁽^T⁾(t)defined by

x⁽^T⁾(t)= ∑^∞

k=−∞

x(t−kT). (2.21)

In this case, samplesx⁽^T⁾(n·Ts)ofx⁽^T⁾(t)is represented as

(28)

Then,we have

X⁽^N^T⁾(k

T)=Ts·∑

k=0

x⁽^t⁾(nTs)e⁻^j^2π^N^nk. (2.24) Definition 3 The DFT and Inverse DFT of vectorsx=(x₀,x₁· · · ,xn−1)^T of length N are represented as

X = Fx, x = F⁻¹X= 1

NF^HX, (2.25)

whereFisN-dimensional DFT-matrix, i.e.

(F)kn=e⁻^j^2π^N^kn. (2.26) If x(t) is not time limited to [0,T], truncation error occurs, and the sample x(nTs) is different fromx⁽^T⁾(nT_s). On the other hand, ifx(t)is not band-limited, the DFT coefficient of (xTc)(n=0,· · · ,N−1)isX⁽^N^T⁾(f)=∑

pX(f −p^N_T)evaluated at f = _T^k, and aliasing error occurs.

Fig.2.3 give an explanation of truncation error. Fig.2.3 (a) shows root raised cosine (RRC) pulse. In order to avoid inter symbol interference (ISI), the signal is low- pass filtered. The raised-cosine filter satisfies the Nyquist criterion of suppressing the spectral distortion at integral multiples of the sampling rate. The filter is usually split into two parts, the RRC filter, one at the sender side and the other at the receiver side [Joost, 2010]. The RRC pulse is defined by

RRC(t)= 



√1

Tc(1−β+4^β_π),t=0

√β

2Tc[(1+ _π²sin(₄^π_β)+(1− ²_π)cos(₄^π_β)],t =±^T₄^c_β

√1 Tc

sin[π_Tc^t (1−β)]+4β_Tc^t cos[π_Tc^t (1+β)]

π_Tc^t [1−(4β_Tc^t )²] , otherwise,

(2.27)

whereT_cis chip-time, andβis a roll-off factor.

Fig.2.3 (b) shows the Fourier transform of RRC pulse. Fig.2.3 (c) showsNsamples atTs sampling interval. There are truncation errors, since sampling the RRC pulse in Fig.2.3 (d).

To avoid truncation error, we should usex^T(nTs)instead of x(nTs). Fig.2.4 shows the relation betweenx⁽^T⁾(nT_s)andX⁽^N^T⁾(_T^k)is described by DFT. Ifx(t)is band-limited to _2T¹

s [Hz],X(f)andX(f−_T¹_s)are not overlapped. Therefore,

(29)

X(f)= X⁽^N^T⁾(f) for − 1

2Ts ≤t ≤ 1 2Ts

. (2.28)

Otherwise (i.e.x(t)is not band-limited),

X(f), X⁽^N^T⁾(f). (2.29)

This is the aliasing.

FIGURE2.3: FiniteNsamples with truncation error

(30)

FIGURE2.4: The relation betweenx^(T)(nT_s)andX⁽^N^T⁾(_T^k)

2.6 Line spectral estimation

Line spectral estimation is a classical signal processing problem that finds numer- ous applications in speech analysis and array signal processing, including the direction of arrival estimation in sensor array signal processing, imaging systems spec- troscopy, molecular dynamics, power electronics, and radar.

This estimation aims to infer the distinct frequency components of a signal from a finite number of observations. Prony’s methods is famous to solve line spectral estimation processing problem [Tang et al., 2014]. In this section, we will give overview about Prony’s method and the annihilating filter method, which is extended version of Prony’s method.

2.6.1 Prony’s method

The Prony’s method was developed by Gaspard de Prony in 1795 [Singh, 2003]. The method has been shown to be a viable technique to model a linear sum of complex exponentials to signals that are uniformly sampled [Feilat, 2006]. The method ex- tracts valuable information from a uniformly sampled signal. The method allows for the estimation of amplitude, frequency, and phase of signals. Prony’s method is essentially a decomposition of a signal withk complex exponentials via the following process [Hauer, Demeure, and Scharf, 1990]: The original approach is related to

(31)

the noiseless measurements. The signal is modeled as a weighted mixture ofkcom- plex exponentials with complex amplitudes and frequencies [Marvasti et al., 2012]:

xr =

∑k i=1

biz^r_i, (2.30)

where xr is the noiseless discrete sparse signal consisting of k exponentials with parameters.

bi = aie^j^θⁱ

zi = e^j2π^fⁱ^T^s, (2.31)

whereai, θi, fi mean amplitude, phase, and frequency, respectively. Ts is the sampling interval (usually assumed as unity). Let us define the polynomialH(z) such that its roots represent the complex exponential functions related to the sparse tones.

H(z)=

∏k i=1

(z−z_i)=

∑k i=0

h_iz^k−i, (2.32)

whereh_i represents coefficients. By shifting the index of Eq.(2.30) and multiplying by the parameterhjand summing over jwe get:

∑k j=0

h_jx_r₋_j =

∑k i=1

b_iz^r−k_i

∑k j=0

h_jz^k_i⁻^j=0, (2.33) wherer is indexed in the range k+1 ≤ r ≤ 2k. This means a recursive equation to solve forhis, the roots of Eq.(2.32) yield the frequency components. Therefore, the amplitudes of the exponentials can be calculated from a set of linear equations given in Eq.(2.30). This method includes following steps 1) −3): 1) Solve the recursive equation in Eq.(2.33) to evaluatehis. 2) Find the roots of the polynomial represented in Eq.(2.32); these roots are the complex exponentials defined as z_i in Eq.(2.30). 3) Solve Eq.(2.30) to obtain the amplitudes of the exponentials (bis).

2.6.2 Annihilating filter

Annihilating Filter (AF) method is an approach to solve a certain type of a 2K-th order nonlinear simultaneous equation by transforming it into aK-th order linear equation whose coefficients are given by roots of a certainK-th order characteristic polynomial [Ito, Yang, and Jitsumatsu, 2015]. In this subsection, the AF method is briefly reviewed. Denote the bandwidth of the transmitted signal byW. Then, the received signal is usually sampled at a sampling interval∆T < 1/2W. Therefore, the number of the required samples increases asWincreases irrespective of the number of the paths. On the other hand, “Rate of Innovation (RoI)” [Vetterli, Marziliano, and Blu, 2002] is a different concept of sampling and restoring signal. RoI is a value that indicates the average degree of freedom per unit time of the original signal. Accord- ing to RoI concept, the number of samples required for reconstructing the signal is at least twice the degrees of freedom of the original signal. In [Vetterli, Marziliano, and Blu, 2002], several signals including trains of the Dirac were demonstrated to

(32)

τ τ _k=0 ^k

whereuk = e⁻^j⁽²^π^t^k^/τ). Let x(t)be passed through an ideal low-pass filter (sinc function filter) with bandwidthB.

Such a filter is defined by h_B(t) =sin(πBt)/(πt), which is used to limit the bandwidth ofx(t).

The output of the filter is denoted by y(t), which is sampled uniformly with an intervalT = 1/B. Let us consider to reconstruct the delays{t_k}and the attenuation factors{ck}from the samplesyn= y(nT)forn=0, 1, 2,. . .,N−1.

The sample value is

yn =

∫

hB(t)x(nT−t)dt

= ∑

m∈Z

fm

∫

hB(t)e^j^2π^τ ^m⁽^nT⁻^t⁾dt

= ∑

m∈Z

fmHB

(2πm τ

)

e^j^2π^τ^T^mn

=

∑M m=−M

f_me^j^2πT^τ ^mn (2.36)

whereM is an integer satisfying ^M_τ < ^B₂ < ^M_τ⁺¹. We observe from Eq.(2.36) that f_m, m=−M,−M+1,. . .,Mcan be obtained from the sample valueyn,n=0, 1,. . .,N−1, if N ≥ 2M+1. Then, we can determine the {t_k}and the {c_k} by solving Eq.(2.35), which is a nonlinear simultaneous equation. The AF method [Vetterli, Marziliano, and Blu, 2002] is a solution to solve such a nonlinear simultaneous equation. We consider aK-th order polynomial having{u_k}as its roots, i.e.,

A(z)= ^K−1∏

k=0

(1−ukz⁻¹) (2.37)

We regard A(z)as a polynomial with respect toz⁻¹. Rewrite Eq.(2.37) as

A(z)=

∑K m=0

amz⁻^m (2.38)

It follows from Eq.(2.35) that the coefficients{am}satisfy

(33)

∑K k=0

f_m₋_ka_k =0, m∈Z. (2.39)

Assumea₀ = 1. Then, for given{f_m}, Eq.(2.39) can be viewed as a Yule-Walker equation with respect toa_kfork =1, 2,. . .K.

It is also possible to obtain{ak}by performing a singular value decomposition (SVD) for a Toeplitz matrix{f_m−k}. Here, the M must be greater thanK to obtain a unique solution.

After the coefficients{ak}is obtained, we calculate the roots of A(z)to obtainuk. The{t_k}is determined byt_k = −₂^τ_π arg(u_k), where arg(u_k)denotes the argument (or phase) ofu_k. Finally,{c_k}are obtained by solving Eq.(2.35). Eq.(2.35) is expressed in matrix-vector form as the following Vandermonde system:





 f₀ f₁ ... fK−1







= 1 τ·







1 1 . . . 1

u₀ u₁ . . . uK−1

... ... . . . ... u₀^K⁻¹ u₁^K⁻¹ . . . u^K_K₋₁⁻¹











 c₀ c₁ ... cK−1







The above procedure is called the AF method. Note that the number of samplesN, the bandwidth limitationMand the number of DiracsKmust satisfy

N ≥ 2M+1 ≥2K+1. (2.40)

2.7 Compressed sensing

In this section, we briefly review Compressed Sensing (CS). Traditional information /communication systems have been developed mainly on digital systems designed based on sampling theorem by Shannon and Nyquist. The theory called CS was presented by Donoho (professor of Stanford statistics), Candès (professor of Cal- tech mathematics), and Tao (professor of mathematics at UCLA, 2006 Fields Medal- ist) [Donoho, 2006][Candes, Romberg, and Tao, 2006]. The most interesting point of this CS theory is that it deals with the case where a signal can be completely reproduced even if it is not sampled above the Nyquist rate. According to CS theory, many signals are mostly so-called "sparse" signals with most values zero when transformed into a particular signal space. This sparse signal is almost completely reconstructed by a very small number of linear measurements. CS theory deals with incomplete linear equation systems of the type:

y=Ax, (2.41)

where theN-dimensional vectorycollects observations obtained by a linear sensor, Ais an N × M matrix characterizing how the coefficient vector is mapped to the observations, and theM-dimensional coefficient vectorxrepresents unknown sparse signals. CS assumes that N<M. A vector x is called K-sparse if at most K of its coefficients are nonzero. The goal of CS is to reliably recoverxfrom the knowledge ofyandA.

(34)

The contact point corresponds to the solution of thel₁reconstruction. Basis pursuit is a principle for decomposing a signal into an optimal superposition of dictionary elements, where optimal means having the smallestl₁norm of coefficients among all such decompositions [Chen, Donoho, and Saunders, 2001]. In noisy case, we have y = Ax+n, where n means noise. A well-known estimation method is the Basis Pursuit Denoising (BPDN). BPDN refers to a mathematical optimization problem of the form:

minx

1

2||y−Ax||₂²+λ||x||1, (2.43)

whereλis a parameter that controls the trade-off between reconstruction fidelity and sparsity. Solvers such as interior point methods can solve BPDN, because BPDN is a convex quadratic problem. There is a variety of CS algorithms. For example, Matching Pursuits (MP), Orthogonal Matching Pursuit (OMP), and Dantzig Selector (DS). We will explain DS next chapter. As the dimension of wireless communication systems increases, design time and computational complexity increase significantly.

For the successful development of CS-based wireless communication systems, low- complexity and fast implementation is of importance [Choi et al., 2017].

FIGURE2.5: Geometrical concept ofl₁-minimization

(35)

Chapter 3

Overview of related technologies

In this chapter, we present related technologies with our research. radar, GPS, OFDM, Spread Spectrum (SS) are described to apply our research.

3.1 Radar

Radar is an electromagnetic sensor for the detection and location of reflecting objects [Skolnik, 1970]. Radar is an acronym for RAdio Detection And Ranging. A common waveform radiated by a radar is a series of relatively narrow, rectangular- like pulses. As an example as an illustration, a pulse radar emits short and power- ful pulses and in the silent period receives the echo signals. The pulse radar uses a pulsed wave signal to determine target range. The round-trip delay time of the pulsed wave signal is used to determine the target range. For better resolution shorter pulses are used and for better signal-to-noise ratio longer pulses are desired.

Fig.3.1 shows elementary basic block diagram of a simple radar system. The transmitter generates the high-frequency radar signal. The radar signal passes through a special type of connector, called a switch to the antenna, where the signal radiates outward in a beam whose shape is defined by the geometry of the antenna. The radio waves reflected off targets make their way back to the antenna, where they are picked up and converted into an electrical signal. The switch is a device which allows signals to be sent in only one direction. It prevents the received signal from entering back into the transmitter. The receiver stores the received signal in the data recorder, the processor calculates the desired information from differences between the transmitted and received signals, and displays the information in a preferred format.

Radar can be used to detect aircraft, ships, spacecraft, motor vehicles, weather formations, and terrain. The channel estimation method is applied to the detection of radar.

(36)

FIGURE3.1: Block diagram of a simple radar system

A Synthetic Aperture Radar (SAR) is a coherent mostly airborne side-looking radar system which utilizes the flight path of the platform to simulate an extremely large antenna or aperture electronically, and that generates high-resolution remote sensing imagery. Microwaves have a longer wavelength than visible light and so can be observed without being affected by clouds. However, the resolution of lenses and antennas of observation instruments using electromagnetic waves are propor- tional to the wavelength. Hence, radars using microwaves have very low resolution about 100, 000 times smaller than optical lenses of the same diameter. In order to improve resolution, it is necessary to make the diameter of the antenna extremely large, which is physically difficult, and SAR have been developed to overcome this problem. The concept of SAR is an array of virtual antennas arranged in orbit. Trans- mission and reception are repeated while moving the orbit, and the received radio waves are combined in consideration of the Doppler shift to improve the resolution.

Compressed Sensing (CS) and Atomic Norm Minimization (ANM) has researched as channel estimation for applying SAR [Dong and Zhang, 2014][Zhu et al., 2016].

3.2 Orthogonal frequency division multiplexing

In wireless communications, Orthogonal Frequency Division Multiplexing (OFDM) is a method of encoding digital data on multiple carrier frequencies [Goldsmith, 2005]. OFDM technology has a relatively high frequency utilization ratio because adjacent carriers are orthogonal to each other, unlike conventional multi-carrier technology. Furthermore, modulation and demodulation of OFDM in a transmitter receiver can be realized by simple signal processing by using IFFT and FFT.

Chang of Bell Labs contribute fundamental developing OFDM in 1966. Chang developed general conditions for the shapes of pulses, defined as the combination of transmitter filter and channel characteristic, with bandlimited [Chang, 1966]. How- ever, in 1960s, the realization of OFDM was not realistic at the hardware technology level. [Weinstein, 2009]. After 1970s, modulation and demodulation methods using discrete Fourier transform were proposed, and became feasible with advances in technologies such as LSI and DSP [Weinstein and Ebert, 1971].

OFDM has developed into a popular scheme for wideband digital communication, used in applications such as wireless networks, digital television, and 4th Gen- eration (4G) mobile communications. Conceptually, OFDM is a specialized frequency- division multiplexing (FDM) method, with the additional constraint that all subcarrier signals within a communication channel are orthogonal to one another. Fig.3.2

(37)

shows spectrum difference of FDM and OFDM signal on frequency domain. In OFDM, the sub-carrier frequencies are chosen so that the sub-carriers are orthogonal to each other, meaning that cross-talk between the sub-channels is eliminated and inter-carrier guard bands are not required. Fig.3.3 shows subcarrier spacing for OFDM. OFDM use dividing a given channel into many narrower subcarriers. The subcarrier spacing is determined by a condition of orthogonality between the subcarriers, which allows to decode each one without interference form its neighbors.

Spectral efficiency is increased by choosing a specific interval∆f = f_i₊₁− f_i, wherei is number of subcarrier.

Time and frequency synchronization is an issue in OFDM systems with a large Doppler shift [Jitsumatsu, Hashiguchi, and Higuchi, 2014][Schmidl and Cox, 1997].

OFDM requires very accurate frequency synchronization between the receiver and the transmitter; with frequency deviation the sub-carriers will no longer be orthogonal, causing inter-carrier interference. Frequency offsets are typically caused by mismatched transmitter and receiver oscillators, or by Doppler shift due to movement.

While Doppler shift alone may be compensated for by the receiver, the situation is worsened when combined with multipath, as reflections will appear at various frequency offsets, which is much harder to correct. This effect typically worsens as speed of vehicles increases, and is an important factor limiting the use of OFDM in high-speed vehicles.

The pilot-symbol-aided estimator is highly robust to Doppler frequency for dis- persive fading channels with noise impairment even though it has some performance degradation for systems with lower Doppler frequencies [Li, 1999].

Since channel estimation is an integral part of OFDM systems, it is critical to understand the basis of channel estimation techniques for OFDM systems so that the most appropriate method can be applied. Although the existing proposed techniques differ in terms of computational complexity and their mean squared error (MSE) performance, it has been observed that many channel estimation techniques are indeed a subset of Linear Minimum Mean Square Error (LMMSE) channel estimation technique [Ozdemir and Arslan, 2007].

FIGURE3.2: Spectrum difference of FDM and OFDM on frequency domain

SUPER-RESOLUTION TECHNIQUES FOR GPS, RADAR ANDWIRELESS COMMUNICATIONS