NS3
 [[ns3]]
정보통신기술용어 해설 정리
 정보통신기술용어
Theory
Chapter 2. Probability & Fourier Transform
Introduction
 Several factors influence the performance of wireless systems:
 Density of mobile users
 Cell size
 Moving direction and speed of users (Mobile models)
 Call rate, call duration
 Interference, etc.
 Probability, statistics theory and traffic patterns, help make these factors tractable.
Probability Theory and Statistics Theory
 Random Variables(RVs):
 Let S be sample associated with experiment E
 X is a function that associates a real number to each $$s \in S$
 RVs can be of two types: Discrete or Continuous
 Discrete random variable => probability mass function (pmf)
 Continuous random variable => probability density function (pdf)
Discrete Random Variables
 The probability mass function (pmf) pk) of X is defined as:
 \[p(k) = p(X = k), for k=0,1,2, ...\]
 where
 Probability of each state occuring \(0 \le p(k) \le 1\) for every k;
 Sum of all states \(\sum p(k) = 1\) for all k.
Continuous Random Varaibles
 Mathmatically, X is a continuous random variable if there is a function f, called probability density function (pdf) of X that satisfies the following criteria:
 \(f(x) \ge 0\) for all x;
 \[\int f(x) dx = 1\]
Cumulative Distribution Function
 Applies to all random variables
 A cumulative distribution function (cdf) is defined as:
 For discreate random variables:
 \[P(k) = P(X \le k) = \sum_{all \le k} P(X = k)\]
 For continous random variables:
 \[F(x) = P(X \le x) = \int_{ \infty}^X f(x) dx\]
 For discreate random variables:
Probability Density Function
 The pdf f(x) of a continous random variable X is the derivative of the cdf F(x),
 \[f(x) = \frac{F_X(x)}{dx}\]
Expected Value, nth Moment, nth Central Moment, and Variance
 Discreate Random Variable:
 Expected value represented by E or average of random variable
 \[E[X] = \sum_{all \le k} k P(X=k)\]
 nth moment:
 \[E[X^n] = \sum_{all \le k} k^n P(X=k)\]
 nth central moment
 \[E[(XE[X])^n] = \sum_{all \le k} (kE[X])^n P(X=k)\]
 Variance or the second central moment
 \[\sigma^2 = Var(X) = E[(X  E[X])^2] = E[X^2]  (E[X])^2\]
 Expected value represented by E or average of random variable
 Continous Random Variable:
 Expected value or mean value:
 \[E[X] = \int_{\infty}^{\infty} xf(x) dx\]
 nth moment
 \[E[X^n] = \int_{\infty}^{\infty} x^n f(x) dx\]
 nth central moment
 \[E[(X  E[X])^n] = \int_{\infty}^{\infty} (x  E[X])^n f(x) dx\]
 Variance or the second central moment
 \[\sigma^2 = Var(X) = E[(XE[X])^2] = E[X^2]  E([X])^2\]
 Expected value or mean value:
Some Important Discrete Random Distributions
Poisson
 \[P(X=k)=\frac{\lambda ^k e ^{\lambda}}{k!}, k=0,1,2,...,and \lambda > 0\]
 \[E[X] = \lambda, and Var(X) = \lambda\]
Geometric
 \[P(X) = p(1p)^k, k =0,1,2,...\]
 where p is success probability
 \[E[X] = 1 / (1p) and Var(X) = p/(1p)^2\]
Binomial
 Out of n dice, exactly k dice have the same value, and (n  k) dice have different values: \((1p)^{nk}\)
 \[P(X=k)=\binom{n}{k} p^{k}(1p)^{nk}\]
 where k = 0, 1, 2, …, n; n = 0, 1, 2, …; p is the success probability
Normal
 \[f_X(x)=\frac{1}{\sqrt{2 \pi} \sigma} e^{\frac{(x  \mu)^2}{2 \sigma ^2}}, for \infty < x < \infty\]
 and the cumulative distribution function can be obtained by
 \[F_X(x) = \frac{1}{\sqrt{2 \pi} \sigma} \int_{ \infty}^{x} e ^ {\frac{ (y  \mu)^2}{2 \sigma^2}} dy\]
 \[E[X] = \mu, and Var(X) = \sigma^2\]
Uniform
 \[f_x(x) = \begin{cases} \frac{1}{ba}, & \text{for $a \le x \le b$} \\ 0, & \text{otherwise} \end{cases}\]
 \[F_X(x) = \begin{cases} 0, & \text{for $x < a$} \\ \frac{xa}{ba}, & \text{ for $a \le x \le b$} \\ 1, & \text{for $x > b$} \end{cases}\]
 \[E[X] = \frac{a+b}{2}, \text{ and } Var(X) = \frac{(ba)^2}{12}\]
Exponential
 \[f_X(x) = \begin{cases} 0, & $x<0$ \\ \lambda e^{\lambda x}, & \text{for $0 \le x < \infty$} \end{cases}\]
 \[F_X(x) = \begin{cases} 0, & $x<0$ \\ 1  e^{ \lambda x}, & \text{for $0 \le x < \infty$} \end{cases}\]
 \[E[X] = \frac{1}{\lambda}\]
 \[Var(X) = \frac{1}{\lambda ^ 2}\]
Multiple Random Variables
 There are cases whter the result of one experiment determines the values of several random variables
 The joint probabilities of these variables are:
 Discreate variables:
 \[p(x_1, ..., x_n) = P(X_1 = x_1, ..., X_n = x_n)\]
 Continuous variables:
 cdf : \(F_{x_1, x_2, ..., x_n}(x_1, ..., x_n) = P(X_1 \le x_1, ..., X_n \le x_n)\)
 pdf : \(f_{X_1, X_2, ..., X_n}(x_1, ..., x_n) = \frac{\partial^n F_{X_1, ..., X_n}(x_1, ..., x_n)}{\partial x_1 \partial x_2 ... \partial x_n}\)
 Discreate variables:
Indpendence and Conditional Probability
 Independence : The random variables are said to be independent of each other when the occurrence of one does not affect the other. The pmf for discrete random variables in such a case is given by:
 \[p(x_1, x_2, ..., x_n) = P(X_1 = x_1)P(X_2=x_2) \cdots P(X_n = x_n)\]
 and for continous random variables as:
 \[F_{X_1, X_2, ..., X_n} = F_{X_1}(x_1)F_{X_2}(x_2) \cdots P(X_n = x_n)\]
 Conditional probability : is the probability that \(X_1 = x_1\) given that \(X_2 = x_2\). Then for discrete random variables the probability becomes:
 \[P(X_1 = x_1  X_2 = x_2, ... , X_n = x_n) = \frac{P(X_1 = x_1, X_2 = x_2, ..., X_n = x_n)}{P(X_2 = x_2, ..., X_n = x_n)}\]
 and for continous random variables it is:
 \[P(X_1 \le x_1  X_2 \le x_2 , ... , X_n \le x_n) = \frac{X_1 \le x_1, X_2 \le x_2, ..., X_n \le x_n}{P(X_2 \le x_2, ... , X_n \le x_n)}\]
Bayes Theorem

A theorem concerning conditional probabilities of the form $$P(X Y)$$ (read: the proability of X, given Y) is:  \[P(XY) = \frac{P(YX)P(X)}{P(Y)}\]
 where P(X) and P(Y) are the unconditional probabilities of X and Y respectively.
Importatnt Properties of Random Variables
 Sum property of the expected value:
 Expected value of the sum of random variables:
 \[E[\sum_{i=1}^n a_i X_i] = \sum_{i=1}^n a_iE[X_i]\]
 Expected value of the sum of random variables:
 Product property of the expected value:
 Expected value of product of stochastically independent random variables:
 \[E[\prod_{i=1}^n X_i] = \prod_{i=1}^n E[X_i]\]
 Expected value of product of stochastically independent random variables:
 Sum property of the variance:
 Variance of the sum of random variables is:
 \[Var[\sum_{i=1}^n a_iX_i] = \sum{i=1}^n a_i^2 Var(X_i) + 2 \sum_{i=1}^{n1} \sum_{j=i+1}^n a_i a_j cov[X_i, X_j]\]
 where \(cov[X_i, X_j]\) is the covariance of random variables \(X_i\) and \(X_j\) and
 \[cov[X_i, X_j] = E[(X_iE[X_i])(E_j  E[X_j) \\ = E[X_i X_j]  E[X_i]E[X_j]\]
 Variance of the sum of random variables is:
 If random variables are independent of each other, i.e., \(cov[X_i, X_j] = 0\), then
 \[Var(\sum_{i=1}^n a_i X_i) = \sum_{i=1}^n a_i^2 Var(X_i)\]
Central Limit Theorem
 The Central Limit Theorem states that whenever a random sample (\(X_1, X_2, ..., X_n\)) of size n is taken from any distribution with expected value \(E[X_i] = \mu\) and variance \(Var(X_i) = \sigma^2\), where i=1, 2, …, n, then their arithmetic mean is defined by:
 \[S_n = \frac{1}{n} \sum_{i=1}^{n} X_i\]
 The sample mean is approximated to a normal distribution with:
 \(E[S_n] = \mu\) and \(Var(S_n) = \sigma^2 /n\)
 The larger the value of the sample size n, the better the approximation to the normal.
 This is very useful when inference between signals needs to be considered.
Queueing Theory
Poisson Arrival Model
 A Possion process is a sequence of events randomly spaced in time.
 For example, customers arriving at a bank and Geiger counter clicks are similar to packets arriving at a buffer.
 The rate \(\lambda\) of a Possion process is the average number of events per unit time(over a long time).
Properties of a Poisson Process
 Properties of a Poisson process
 For a time interval [0, t), the probability of n arrivals in t units of time is:
 \[P_n(t) = \frac{(\lambda t)^n}{n!}e^{\lambda t}\]
 For two disjoint (non overlapping) intervals (t1, t2) and (t3, t4), the number of arrivals in (t1, t2) is independent of arrivals in (t3, t4).
 For a time interval [0, t), the probability of n arrivals in t units of time is:
Interarrival Times of Poisson Process
 Interarrival times of a Possion process
 We pick an arbitrary starting point \(t_0\) in time. Let \(T_1\) be the time until the next arrival. We have
 \[P(T_1 > t) = P_0 (t) = e^{\lambda t}\]
 Thus the distribution function of \(T_1\) is given by
 \[F_{T_1} (t) = P(T_1 \le t) = 1  e ^ { \lambda t}\]
 We pick an arbitrary starting point \(t_0\) in time. Let \(T_1\) be the time until the next arrival. We have
 The pdf of \(T_1\) is given by:
 \[f_{T_1} (t) = \lambda e^{ \lambda t}\]
 Therefore, \(T_1\) has an exponential distribution with mean rate \(\lambda\).
Memoryless and Merging Properties
 Memoryless property:
 A random variable X has the property that “the future is independent of the past”. i.e., the fact taht it hasn’t happened yet, tells us nothing about how much longer it will take before it does happen.
 \[P(X > \delta +t  X > \delta) = P(X > t)\]
 A random variable X has the property that “the future is independent of the past”. i.e., the fact taht it hasn’t happened yet, tells us nothing about how much longer it will take before it does happen.
 Merging property:
 If we merge n Possion processes with distributions for the inter arrival times
 \(1  e^{ \lambda i t}\),
 where i = 1, 2, …, n
 If we merge n Possion processes with distributions for the inter arrival times
 into one single process, then the result is a Possion process for which the inter arriavl times have the distribution \(1  e^{\lambda t}\) with mean
 \[\lambda = \lambda_1 + \lambda_2 + ... + \lambda_n\]
Basic Queuing Systems
 What is queuing theory?:
 Queuing theory is the study of queues(sometimes called waiting lines).
 Can be used to describe real world queues, or more abstract queues, found in many branches of computer science, such as operating systems and networks.
 Basic queuing theory
 Queuing theory is divided into 3 main sections:
 Traffic flow
 Scheduling
 Facility design and employee allocation
 Queuing theory is divided into 3 main sections:
Kendall’s Notation
 D.G. Kendall in 1951 propsed a standard notation for classifying queuing systems into different types.
 Accordingly the systems were described by the notation A/B/C/D/E where:
 A : Distribution of inter arrival times of customers
 B : Distribution of service times
 C : Number of servers
 D : Maximum number of customers in the system
 E : Calling population size
 A and B can take any of the following distributions types:
 M : Exponential distribution (Markovian)
 D : Degenerate (or deterministic) distribution
 \(E_k\) : Erlang distribution (k = shape parameter)
 \(H_k\) : Hyper expoential with parameter k
Little’s Law
 Assuming a queuing environment to be operating in a stable steady state where all initial transients have vanished, the key parameters characterizing the system are:
 \(\lambda\)  the mean steady state consumer arrival
 \(N\)  the average no. of customers in the system
 \(T\)  the mean time spent by each customer in the system which gives:
 \[N = \lambda T\]
Markov Process
 A Markov process is one in which the next state of the process depends only on the present state, irrespective of any previous states taken by the process.
 The knowledge of the current state and the transition probabilties from this state allows us to predict the next state.
BirthDeath Process
 Special type of Markov process
 Often used to model a population (or, no.of jobs in a queue).
 If, at some time, the population has n entities (n jobs in a queue), then birth of another entity (arrival of another job) causes the state to change to n + 1.
 On the other hand, a death(a job removed from the queue for service) would cause the state to change to n1.
 Any state transitions can be made only to one of the two neighboring states.
State Transition Diagram
 The state transition diagram of the continuous birthdeath process.
M/M/1/inf or M/M/1 Queuing System
 When a customer arrives in this system it will be served if the server is free. Otherwise the customer is queued.
 In this system customers arrive according to a Poisson distribution and compete for the service in a FIFO (first in first out) manner.
 Service tiems are independent identically distributed (IID) random variables, the common distribution being exponential.
Queuing Model and State Transition Diagram
 The M/M/1/inf queuing model
 The state transition diagram of the M/M/1/inf queuing system
Equilibrium State Equations
 If mean arrival rate is \(\lambda\) and mean service rate is \(\mu\), i = 0, 1, 2, .. be the number of customers in the system and P(i) be the state probability of the system having i customers.
 From the state transition diagram, the equilibrium state equations are given by:
 \[\lambda P(0) = \mu P(1), i=0\]
 \[(\lambda + \mu) P(i) = \lambda P(i1) + \mu P(i + 1), i \ge 1\]
Traffic Intensity
 We know that the P(0) is the probability of server being free. Since P(0) > 0, the necessary condition for a system being in steady state is,:
 \[\rho = \frac{\lambda}{\mu} < 1\]
 This means taht the arrival rate cannot be more than the service rate, otherwise an infinite queue will form and jobs will experience infinite service time.
Queuing System Metrics
 \(\rho = 1  P(0)\), is the probability of the server being busy. Therefore, we have
 \[P(i) = \rho^i (1  \rho)\]
 The average number of customers in the system is
 \[L_s = \frac{\lambda}{\mu  \lambda}\]
 The average dwell time of customers is
 \[W_s = \frac{1}{\mu  \lambda}\]
Queuing System Metrics
 The average queuing length is
 \[L_q = \sum_{i=1}^{\infty} (i1) P(i) = \frac{\rho^2}{1  \rho} = \frac{\lambda ^ 2}{\mu(\mu\lambda)}\]
 The average waiting time of customers is
 \[W_q = \frac{L_q}{\lambda} = \frac{\rho ^ 2}{\lambda(1  \rho)} = \frac{\lambda}{\mu(\mu  \lambda)}\]
 The average number of customers in the system is
 \[L_s = \sum_{i=0}^{\infty} i P(i) = \alpha + \frac{\rho \alpha ^ S P(0)}{S! (1  \rho)^2}\]
 The average number dwell time of a customer in the system is given by
 \[W_S = \frac{L_S}{\lambda} = \frac{1}{\mu} + \frac{\alpha^S P(0)}{S_{\mu} S! (1  \rho)^2}\]
M/G/1/inf Queuing Model
 We consider a single server queuing system whose arrival process is Poisson with mean arrival rate \(\lambda\).
 Service times are independent and identically distributed with distribution function \(F_B\) and pdf \(f_b\).
 Jobs are scheduled for service as FIFO.
Basic Queuing Model
 Let N(t) denote the number of jobs in the system (those in queue plus in service) at time t.
 Let \(t_n\) (n = 1, 2, …) be the time of departure of the nth job and \(X_n\) be the number of jobs in the system at time \(t_n\) so that:
 \[X_n = N(t_n), \text{for n = 1, 2, ...}\]
 The stochastic process can be modeled as a discrete Markov chain known as imbedded Markov chain, which helps convert a nonMarkovian problem into a Markovian one.
Queuing System Metrics
 The average number of jobs in the system, in the steady state is:
 \[E[N] = \rho + \frac{\lambda^2 E[B^2]}{2(1\rho)}\]
 The average dwell time of customers in the system is:
 \[W_s = \frac{E[N]}{\lambda} = \frac{1}{\mu} + \frac{\lambda E[B^2]}{2(1\rho)}\]
 The average waiting time of customers in the queue is:
 \[E[N] = \lambda W_q + \rho\]
 Average wiating time of customers in the queue is:
 \[W_q = \frac{\lambda E[B^2]}{2(1\rho)}\]
 The average queue length is:
 \[L_q = \frac{\lambda^2E[B^2]}{2(1\rho)}\]
Fourier Transform
Dirac Delta Function
 The dirac delta function can be loosely thought of as a function on the real line which is zero everywhere except at the origin, where it is infinite:
 \[\delta(x) = \begin{cases} \infty, & x = 0 \\ 0, & x \not = 0 \end{cases}\]
 and which is also constrained to satisfy the identity:
 \[\int_{\infty}^{\infty} \delta (x) dx = 1\]
 An important property:
 \[\int_{\infty}^{\infty} f(x) \delta(x) dx = f(0)\]
 where f is a suita ble test function.
Unit Step Function
 Unit Step funciton is defined by:
 \[u(t) = \begin{cases} 1, & t > 0 \\ 1/2, & t = 0 \\ 0, & t < 0 \end{cases}\]
Sinc Function
 Sinc Function is defined by:
 \[sinc(x) = \frac{sin(\pi x)}{\pi x}\]
 For all x except x = 0. For x = 0, sinc(0) = 1
Rectangular Function
 Rectangular funciton is defined by
 \[rect(t) = \sqcap(t) = \begin{cases} 0 & if t > \frac{1}{2} \\ \frac{1}{2} & if t = \frac{1}{2} \\ 1 & if t < \frac{1}{2} \end{cases}\]
Triangular Function
 Triangular Function is defined by
 \[tri(t) = \wedge (t) = \begin{cases} 1  t; & t < 1 \\ 0 & otherwise \end{cases}\]
LTI System
 LTI (Linear Time Invariant) system is the system satisfies the following two:
 Linearity:
 If the input to the system is the sum of two component signals:
 \[x(t) = x_1(t) + x_2(t)\]
 then the output of the system will be \(y(t) = y_1(t) + y_2(t)\) where \(y_n(t)\) is the output resulting from the sole input \(x_n(t)\)
 Formally, a linear system is a system which exhibits the following property:
 if the input of the system is \(x(t) = \sum_{n} c_n x_n(t)\)
 then the output of the system will be \(y(t) = \sum_{n} c_n y_n(t)\) for any constants \(c_n\) and where each \(y_n(t)\) is the output resulting from the sole input \(x_n(t)\)
 If the input to the system is the sum of two component signals:
 TimeInvariance:
 means that whether we apply an input to the system now of T seconds from now, the output will be identical except for a time delay of the T seconds.
 If the output due to input x(t) is y(t), then the output due to input x(t  T) is y(t  T). More specifically, an input affected by a time delay should effect a corresponding time delay in the output, hence timeinvariant.
 Impulse Response h(t):
 Is the response of the system to a unit impulse input \(\delta (t)\)
 \[h(t) = LTI[\delta(t)]\]
 Very Important Result:
 \[y(t) = LTI[x(t)] \\ = LTI[x(t) * \delta(t)] \\ = LTI[\int_{\infty}^{\infty} x(\tau)\delta(t  \tau) d \tau] \\ = \int_{\infty}^{\infty} x(\tau) LTI[\delta(t  \tau)] d \tau \\ = \int_{\infty}^{\infty} x(\tau)h(t  \tau) d \tau \\ = x(t)*h(t)\]
 여기서 적분을 LTI 밖으로 꺼낼 수 있는 것은 Linearity, \(LTI[\delta(t\tau)]\) 를 계산할수 있는 것은 Timeinvariant 때문이다.
 Linearity:
Taylor Series
 Definition:
 The Taylor series of a function f that is differentiable in a neighborhood of a, is the power series:
 \[f(a) + \frac{f'(a)}{1!} (x  a) + \frac{f''(a)}{2!} (x  a)^2 + \frac{f^{(3)}(a)}{3!} (x  a)^3 + \cdots\]
 Thus, we can say:
 \[e^x = \sum_{n = 0}^{\infty} \frac{x^n}{n!} \text{for all x}\]
 \[cos x = \sum_{n = 0}^{\infty} \frac{(1)^n}{(2n)!} x^{2n} = 1  \frac{x^2}{2!} + \frac{x^4}{4!}  \cdots \text{for all x}\]
 \[sin x = \sum_{n = 0}^{\infty} \frac{(1)^n}{(2n + 1)!} x^{2n + 1} = x  \frac{x^3}{3!} + \frac{x^5}{5!}  \cdots \text{for all x}\]
 The Taylor series of a function f that is differentiable in a neighborhood of a, is the power series:
 Euler’s Formula:
 \[e^{ix} = cos(x) + i sin(x)\]
 since:
 \[e^{iz} = 1 + iz + \frac{(iz)^2}{2!} + \frac{(iz)^3}{3!} + \cdots \\ = 1 + iz  \frac{z^2}{2!}  \frac{iz^3}{3!} + \cdots \\ = (1  \frac{z^2}{2!} + \frac{z^4}{4!}  \cdots) + i (z  \frac{z^3}{3!} + \frac{z^5}{5!}  \cdots ) \\ = cos(z) + i sin(z)\]
 The Fourier transform of a funciton x is defined by \(X(f) = \int_{ \infty}^{\infty} x(t) e ^{i 2 \pi f t} dt, \text{ for } f\).
 When the idependent variable t represents time (with unit of seconds), the transform variable f represents frequecy (in hertz).
 If x is a continuous function, then it can be reconstructed from x by the inverse transform:
 \[x(t) = \int_{\infty}{\infty} X(f) e^{i 2 \pi f t} df, \text{ for } t\]
 Note that a symbol of a Fourier transform is capitalized.
Fouerier Transform Properties
 \(\mathcal{F}(a g(t) + b h(t)) = a G(f) + b H(f)\) : Linearity
 \(\mathcal{F}(g(t  a)) = e^{ i 2 \pi a f}G(f)\) : Shift in time
 \(\mathcal{F}(e^{iat} g(t)) = G(f  \frac{a}{2 \pi})\) : Shift in frequency

$$\mathcal{F}(g(at)) = \frac{1}{ a } G(\frac{f}{a})$$ : Widening in time makes narrowing in frequency, or vice versa  \(\mathcal{F}(G(t)) = g(f)\) : Duality property
 \[\mathcal{F}(\frac{d^n g(t)}{d t^n}) = (i 2 \pi f)^n G(f)\]
 \[\mathcal{F}(t^n g(t) = (\frac{i}{2 \pi}) ^n \frac{d^n G(f)}{df^n}\]
 \[\mathcal{F}((g * h)(t)) = G(f)H(f)\]
 \[\mathcal{F}(g(t)h(t)) = (G*H)(f)\]
 Fourier Transform of \(f(t) e^{i 2 \pi f_0 t}\):
 \(F(f + f_0)\) 이므로 \(e^{i 2 \pi f_0 t}\) 를 원함수에 곱한다는 것은 주파수 영역에서 \(f_0\)만큼 평행이동한다는 것을 의미한다.
 이때 \(e^{i 2 \pi f_0 t} = cos(2 \pi f_0 t)\) 이기 때문에, 아래 식 또한 같은 의미를 가진다.
 \[f(t) cos(2 \pi f_0 t)\]
Fourier Transform of Various Function
 \[\mathcal{F}(rect(at)) = \frac{1}{a} sinc(\frac{f}{a})\]
 \[\mathcal{F}(sinc(at)) = \frac{1}{a} rect(\frac{f}{a})\]
 \[\mathcal{F}(sinc^2(at)) = \frac{1}{a} tri(\frac{f}{a})\]
 \[\mathcal{F}(tri(at)) = \frac{1}{a} sinc^2 (\frac{f}{a})\]
 \[\mathcal{F}(e^{ \alpha t^2}) = \sqrt{\frac{\pi}{\alpha}} e^{\frac{(\pi f)^2}{\alpha}}\]
 \[\mathcal{F}(e^{i \alpha t^2}) = \sqrt{\frac{\pi}{\alpha}} e^{i \frac{\pi ^2 f ^2}{\alpha}  \frac{\pi}{4}}\]
 \[\mathcal{F}(cos(at^2)) = \sqrt{\frac{\pi^2 f^2}{a} cos(\frac{\pi^2 f^2}{a}  \frac{\pi}{4})}\]
 \[\mathcal{F}(sin(at^2)) = \sqrt{\frac{\pi^2 f^2}{a} sin(\frac{\pi^2 f^2}{a}  \frac{\pi}{4})}\]
 \[\mathcal{F}(e^{a t}) = \frac{2 a}{a^2 + 4 \pi^2 f ^2}\]
 \[\mathcal{F}(\frac{1}{\sqrt{t}}) = \frac{1}{\sqrt{f}}\]
 \[\mathcal{F}(1) = \delta (f)\]
 \[\mathcal{F}(\delta (t)) = 1\]
 \[\mathcal{F}(e^{iat}) = \delta (f  \frac{a}{2 \pi })\]
 \[\mathcal{F}(cos(at)) = \frac{\delta (f  \frac{a}{2 \pi}) + \delta (f + \frac{a}{2 \pi})}{2}\]
 \[\mathcal{F}(sin(at)) = i \frac{\delta (f + \frac{a}{2 \pi}) + \delta (f  \frac{a}{2 \pi})}{2}\]
 \[\mathcal{F}(t^n) = (\frac{i}{2 \pi})^n \delta^{(n)} (f)\]
 \[\mathcal{F}(\frac{1}{t^n}) = i \pi \frac{(i 2 \pi f)^{n  1}}{(n1)!} sgn(f)\]
 \[\mathcal{F}(sgn(t)) = \frac{1}{i \pi f}\]
 \[\mathcal{F}(u (t)) = \frac{1}{2} (\frac{1}{i \pi f} + \delta (f))\]
 \[\mathcal{F}(e^{ at} u(t)) = \frac{1}{a + i 2 \pi f}\]
 \[\mathcal{F}(\sum_{n =  \infty}^{\infty} \delta (t  n T)) = \frac{1}{T} \sum_{k =  \infty}^{\infty} \delta(f  \frac{k}{T})\]
Chapter 3. Radio Propagation, Sampling & Quantization
Information, Signals, and Communications
 Goal of communication is to deliver (send, transmit) information from a source to a destination
 AWGN(Additive whit Gaussian noise) : is a baisc noise model used in information theory to mimic the effect of many raondom processes that occur in nature.:
 Additive becuase it is added to any noise that might be intrinsic to the information system.
 White refers to the idea that it has uniform power across the frequency band for the information system. It is an analogy to the color white which has uniform emissions at all frequencies in the visible spectrum.
 Gaussian because it has a normal distribution in the time domain with an average time domain value of zero.
Radio Frequency Bands
 Classification Band  Initials  Frequency Range  Characteristics   ——————  ——–  —————  —————   Extremely low  ELF  < 300 Hz  Ground wave   Infra low  ILF  300 Hz ~ 3 kHz  Ground wave   Very low  VLF  3kHz ~ 30 kHz  Ground wave   Low  LF  30 kHz ~ 300 kHz  Ground wave   Medium  MF  300 kHz ~ 3 MHz  Ground/Sky   High  HF  3 MHz ~ 30 MHz  Sky wave   Very high  VHF  30 MHz ~ 300 MHz  Space wave   Ultra high  UHF  300 MHz ~ 3 GHz  Space wave   Super high  SHF  3 GHz ~ 30 GHz  Space wave   Extremely high  EHF  30 GHz ~ 300 GHz  Space wave   Tremendously high  THF  300 GHz ~ 3000 GHz  Space wave 
Propagation Mechanisms
 Reflection:
 Propagtation wave impinges on an object which is large as compared to wavelength
 Diffraction:
 Radio path between transmitter and receiver obstructed by surface with sharp irregular edges.
 Scattering:
 Objects smaller than the wavelength of the propagtion wave
Freespace Propagation
 The recieved signal power at distance d:
 \[P_r = \frac{A_e G_t P_t}{4 \pi d^2}\]
 where \(P_t\) is transmitting power, \(A_e\) is effective area, and \(G_t\) is the transmitting antenna gain. Assuming that the radiated power is uniformly distributed over the surface of the sphere.
Antenna Gain
 For a circular reflector antenna:
 \[G = \eta ( \pi D / \lambda)^2\]
 where \(\eta\) is net efficiency (depends on the electric field distribution over the antenna aperture, losses, ohmic heating, typically 0.55) and \(D\) is diameter
 thus \(G = \eta (\pi D f / c)^2, c = \lambda f\)
Land Propagation
 The received signal power:
 \[P_r = \frac{G_t G_r P_t}{L}\]
 where \(G_r\) is the receiver antenna gain, \(L\) is the propagation loss in the channel
 \[L = L_p L_S L_F\]
 where \(L_p\) is path loss, \(L_S\) is Slow fading, and \(L_F\) is Fast fading
Path Loss (Freespace)
 Definition of path Loss \(L_p\):
 \[L_P = \frac{P_t}{P_r}\]
 Path Loss in Freespace:
 \[L_{PF}(dB) = 32.45 + 20 log_{10} f_c(MHz) + 20 log_{10} d (km)\]
 where \(f_c\) is teh carrier frequency. This shows greater than \(f_c\), more is the loss.
Path Loss (Land Propagation)
 Simplest Formula:
 \[L_p = Ad^{\alpha}\]
 where \(A\) and \(\alpha\) : propgation constants
 \(d\) : distance between transmitter and receiver
 \(\alpha\) : value of 3 ~ 4 in typical urban area
Path Loss
 Path loss in decreasing order:
 Urban area > Urban area(medium and small city) > Suburban area > Open area
Slow Fading
 The longterm variation in the mean level is known as slow fading (shadowing or longnormal fading)_. This fading caused by shadowing.
 Lognormal distribution :
 The pdf of the received signal level is given in decibels by:
 \[p(M) = \frac{1}{\sqrt{2 \pi} \sigma} e^{ \frac{(M  \bar M)^2 }{2 \sigma^2}}\]
 where M is the treue received signal level m in decibels,
 \(\bar M\) is the area average signal level
 \(\sigma\) the standard deviation in decibels
 The pdf of the received signal level is given in decibels by:
Fast Fading
 The signal from the transmitter may be reflected from objects such as hills, buildings, or vehicles.
 When LOS does not exist, the envelope distribution of received signal is Rayleigh distribution.
 The pdf is:
 \[p(r) = \frac{r}{\sigma^2} e ^{ \frac{r^2}{2 \sigma^2}}, r > 0\]
 where \(\sigma\) is the standard deviation.
 Middle value \(r_m\) of evelope signal within sampe range to be satisfied by \(P(r \le r_m) = 0.5\)
 We have \(r_m = 1.777 \sigma\)

It called Reyleigh Distribution
 When LOS exists, the envelope distribution of received signal is Rician distribution. The pdf is:
 \[p(r) = \frac{r}{\sigma^2} e ^{ \frac{r^2 + \alpha ^ 2}{2 \sigma^2}} I_0 (\frac{r \alpha}{\sigma}), r \ge 0\]
 where \(\sigma\) is the standard deviation,
 \(I_0(x)\) is the zeroorder Bessel function of the first kind.
 When \(\alpha = 0\), Rician Distribution are equal to Rayleigh Distribution
Characteristics of Instantaneous Amplitude
 Level Crossing Rate:
 Average number of times per second that the signal envelope crosses the level in positive going direction
 Fading Rate:
 Number of times signal evelope crosses middle value in positive going direction per unit time.
 Fading Duration:
 Time for which signal is below given threshold.
Doppler Shift
 Doppler Effect : When a wave source and a receiver are moving towards each other, the frequency of the received signal will not be the same as the source.:
 When they are moving toward each other, the frequency of the received signal is higher than the source.
 When they are opposing each other, the frequency decreases.
 Thus the frequency of the received signal is:
 \[f_R = f_C  f_D\]
 where \(f_C\) is the frequency of source carrier,
 \(f_D\) is the Doppler frequency.
 \[f_D = \frac{v}{\lambda} cos \theta\]
 where \(v\) is the moving speed, \(\lambda\) is the wavelength of carrier.
Delay Spread
 When a signal propagates from a transmitter to a receiver, signal suffers one or more reflections.
 This forces signal to follow different paths.
 Each path has different path length, so the time of arrival for each path is different.
 This effect which spreads out the signal is called “Delay Spread”.
Intersymbol Interference (ISI)
 Caused by time delayed multipath signals
 Has impact on burst error rate of channel
 Second multipath is delayed and is received during next symbol
 Second multipath is delayed and is received during next symbol
 For low biterrorrate (BER):
 \[R < \frac{1}{2 \tau_d}\]
 R(digital transmission rate) limited by delay spread.
Digital Communications
General Structure of a Communication Systems
 Source (info) > Transmitter (Transmitted signal) > Channel (Recieved signal) > Receiver  (Received info) > Destination
Digital versus Analog
 Regnerator receiver
 Diffrent kinds of digital signal are treated identically.
Advantages of Digital Communications over Analog
 Digital signals are more easily regenerated.
 Extremely low error rates producing high signal fidelity are possible through error detection & correction.
 Easy availability of digital circuits & uprocessors.
 Multiplexing & switching is easier
 Much data (e.g., computers) is inherently digital.
Formatting and Transmission of Signal
 Analog Info > Sample > Quantize > Encode > Pulse Moduolated > Transmitted.
 Textual Info > Encode > Pulse Modulate > Transmitted.
 Digital Info > Pulse Modulate > Transmitted.
 Received Data > Demodulate/Detect > Decode > Lowpass filter > Analog Info
 Received Data > Demodulate/Detect > Decode > Textual info
 Received Data > Demodulate/Detect > Digital info.
Sampling
Sampling of Analog Signal
 Time domain 에서는 연속적인 데이터를 잘라서 샘플링 한다.
 이는 Frequency Domain 에서는 하나의 함수를 중복해서 반복시키는 것 (frequency 영역에서 주기를 가지는 delta 함수와 convolution) 과 동일한 의미이다.
 다시말해서 주파수 영역에서 반복되는 함수를 찾아서 시간 영역으로 옮기면 원 함수를 추출할수 있다고 할 수 있다.
 이때 하나의 고유값이 나오게 된다.(Nyquist rate) 바로 아래에서 추가 설명한다.
Aliasing effect & Nyquist Rate
 도메인 영역에서 반복되는 함수를 추출하기 위해서 필터를 씌우는데 이를 LP filter 라고 한다.
 원함수의 정의역의 최솟값(\(f_m\))과 최댓값(\(f_m\))이라고 할때 LP filter의 최소 크기를 Nyquist rate 라고 하며 \(f_s = 2f_m\) 이다.
 이보다 작게 된다면 aliasing 이 일어나게 된다.
Sampling Theorem
 Sampling theorm: A bandlimited signal with no spectral components beyond \(f_m\), can be uniquely determined by values sampled at uniform intervals of \(T_s \le \frac{1}{2 f_m}\)
 The samplign rate:
 \[f_s = \frac{1}{T_S} = 2 f_m\]
 is called Nyquist rate.
Quantization
 Amplitutde quantizing : Mpaaing samples of a continuous amplitude waveform to a finite set of amplitudes.
 Average quantization noise power:
 \[\sigma^2 = \frac{q^2}{12}\]
 Signal peak power:
 \[V_p^2 = \frac{L^2 q^2}{4}\]
 Signal power to average quantization noise power:
 \[(\frac{S}{N})_q = \frac{V_p^2}{\sigma^2} = 3 L^2\]
PCM
 A uniform linear quantizer is called Pualse Code Modulation (PCM) from the Pulse Modulated (PAM) Signal.
 Pulse code modulation (PCM) : Encoding the quantized signals into a digital word(PCM word or codeword)
 \[k = log_2 L\]
Quantization error
 Quantizing error : The difference between the input and output of a qunatizer
Nonuniform quantization
 It is done by uniformly quantizing the “compressed” signal.
 At the receiver, an inverse compression characteristic, called “expansion” is employed to avoid signal distortion.
 compression + expansion > companding
Baseband transmission
 To transmit information thru physical channels, PCM sequences (codewords) are transformed to pulses (waveforms).:
 Each waveform carries a symbol from a set of size M.
 Each transmit symbol represents \(m=log_2M\) bits of the PCM words.
 PCM waveforms (line codes) are used for binary symbols (M=2).
 Here, consider PCM and PAM are interchangeable.
 Mary pulse modulation are used for nonbinary symbols(M > 2):
 For a given rate, Mary PAM (M>2) requires less bandwidth than binary PCM.
 For a given average pulse power, binary PCM is easier to detect than Mary PAM(M > 2).
 Assuming real time Tx and euqal energy per tx data bit for binaryPAM and 4ary PAM:
 4ary: T=2T_b and Binary : T= T_b
 Energy per symbol in binaryPAM: A^2 = 10 B^2
Chapter 4, 7
Source and Channel Coding
Source  Info > Transmitter (Formatter > Source encoder > Channel encoder > modulator > Multiplexer)  Transmitted signal > Channel (With noise)  Received Signal > Receiver(Demultiplexer > Demodulator > Channel decoder > Source decoder > Formmater)  Received Info > Destination
Source Coding vs. Channel Coding
 Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, errorcorrection and more recently also for network coding.
 This typically involves the removal of redundancy or the correction (or detection) of errors in the transmitted data.
 There are essentially two aspects to coding theory:
 Data compression (or, source coding)
 Error correction (or channel coding)
 Source encoding attempts to compress the data from a source in order to ransmit it more efficiently. This practice is found every day on the Internet where the common Zip data compression is used to reduce the network load and make files smaller.
 Channel encoding, adds extra data bits to make the transmission of data more robust to disturbances present on the transmission channel. A typical music CD uses the ReedSolomon code to correct for scratches and dust. Cell phones also use coding techniques to correct for the fading and noise of high frequency radio transmission. Data modems, telephone transmissions, and NASA all employ channel coding techniques to get the bits through, for example the turbo code and LDPC codes.
Source Coding
Introduction
 Source symbols encoded in binary
 The average codelength must be reduced
 Remove redundancy > reduces bitrate
 Consider a discrete memoryless source on the alphabet
 \[S = \{s_0, s_1, ... s_k\}\]
 Let the corresponding probabilities be \(\{p_0, p_1, ... , p_k\}\)
 and codelengths be \(\{ l_0, l_1, ..., l_k \}\)
 Then, the average codelength (average number of bits per symbol) of the source is defined as
 \[L = \sum_{k=0}^{K1} p_k l_k\]
 If \(L_{min}\) is the minimum possible value of \(\bar L\), then the coding efficiency of the source is given by \(\eta\)
 \[\eta = \frac{L_{min}}{\bar L}\]
 Data Compaction:
 Removal of redundant information prior to transmission.
 Loseless data compaction  no information is lost.
 A source code which represents the output of a discrete memoryless source should be uniquely decodable.
Source Coding Schemes for Data Compaction
 Prefix Coding:
 The Prefix Code is variable length source coding scheme where no code is the prefix of any other code.
 The prefix code is a niquely decodable code.
 But, the converse is not true
 Any symbol \(s_k\) is emitted with probability \(p_k=2^{l_k}\)
 \[sum_{k=0}^{K1} 2^{l_k} = \sum_{k=0}^{K 1} p_k = 1\]
 Therefore, the average codeword length is given by
 \[\bar L = \sum_{k=0}^{K1} \frac{l_k}{2^{l_k}}\]
Huffman Coding
 Step 1: arrange the symbol probabilities in a decreasing order and consider them as leaf nodes of a tree.
 Step 2: while there are more than one node:
 Find the two nodes with the smallest probability and assign the one with the lowest probability a “0”, and the other one a “1”(or the other way, but be consistent)
 Merge the two nodes to form a new node whose proability is the sum of the two merged nodes.
 Go back to Step 1

Step 3: For each symbol, determine its codeword by tracing the assigned bits from the corresponding leaf node to the top of the tree. The bit at the leaf node is the last bit of the codeword
 Huffman code is a prefix code
 The length of codeword for each symbol is roughly equal to the amount of information conveyed.
 If the probability distribution is known and accurate. In this sight, Huffman coding is very good.
 Variance is a measure of the variablitiy in codeword lengths of a source code and is defined as follows:
 \[\sigma^2 = \sum_{k=0}^{K1} p_k (l_k  \bar L)^2\]
 It is reasonable to choose the Huffman tree which gives greater variance (Provide diversity or disimilarity to avoid errors).
Channel Coding
Forward Error Correction(FEC)
 The key idea of FEC is to transmit enough redundant data to allow receiver to recover from erros all by itself. No sender retransmission required.
 The major categories of FEC codes are:
 Block codes, Cyclic codes, ReedSolomon codes, Convolutional codes, and Turbo codes
Block Codes
 Information is divided into blocks of length k
 r parity bits or check bits are added to each block (total length n = k + r)
 Code rate R = k/n
 Decoder looks for codeword cloest to received vector (code vector + error vector)
 Tradeoffs between:
 Efficiency
 Reliability
 Encoding/Decoding complexity
Block Codes: Linear Block Codes
 C of the Linear Block Code is \(C= mG\)
 where m is the uncoded message vector \(m = (m_1, m_2, ..., m_k)\)

and \(G\) is the generator matrix, $$G=[I P]  where \(p_i\) = Remainder of [\(x^{nk+i1} / g(x)\)] for i = 1, 2,… k, and I is unit matrix.

g(x) = generator polynomial
 The parity check matrix:
 \[H = [p^T  I]\]
 where \(p^T\) is the transpose of the matrix p.
 Operations of the generator matrix and the parity check matrix
 The parity check matrix H is used to detect erros in the received code by using the fact that \(c*H^T = 0\) (null vector)
 Let \(x \bigoplus e\) be the received message where c is the correct code and e is the rror
 Compute \(S = x * H^T = (c \bigoplus e) * H^T = c H^T \bigoplus e H^T = e H^T\)
 If S is 0 then message is correct else there are erros in it, from common known error patterns the correct message can be decoded.
Convolutional Codes
 Encoding of information stream rather than information blocks
 Value of certain information symbol also affects the encoding of next M information symbols.
 Easy implementation using shift register
 Assuming k inputs and n outputs
 Decoding is mostly performed by the Viterbi Algorithm
Interleaving
 인풋 데이터를 순서대로 하는 것이 아닌 2차원 형태로 바꾼 다음 열의 순서로 보내는 방식
 Error spreading > Can be correct.
Information Capacity Theorem (Shannon Limit)
 The information capacity (or channel capacity) C of a continuous channel with bandwidth B hertz can be perturbed by additive Gaussian white noise of power spectral density N_0/2 provided bandwidth B satisfies
 \(C = B log_2 (1 + \frac{P}{N_0 B})\) bits/ second
 where P is the average transmitted power \(P = E_b R_b\) (for an ideal system, \(R_b = C\)).
 \(E_b\) is the transmitted energy per bit,
 \(R_b\) is transmission rate.
Turbo Codes
 A brief historic of turbo codes:
 The turbo code concept was first introduced by C. Berrou in 1993. Today, Turbo Codes are considered as the most efficient coding schmes for FEC.
 Scheme with known components (simple convolutional or block codes, interleaver, softdecision decoder, etc.)
 Performance close to the Shannon Limit at modest complexity!
 Turbo codes have been proposed for lowpower applications such as deepspace and stellite communications, as well as for interference limited applications such as third generation cellular, personal communication services, ad hoc and sensor networks.
Modulation
Signal transmission through linear systems
 Input x(t) > y(t) Output
 Y(f) = X(f)H(f)
Bandwidth of signal
 Baseband versus bandpass:
 x(t) (Baseband signal)  convolution \(cos (2\pi f_ct)\) (local socillator) > x_c(t) (Bandpass signal)
 기저 대역(baseband)에 있는 메시지를 통과대역(passband)로 변환하는 과정
 수신자는 송신자와 같은 대역으로 대역으로 발진해야하지만, 실제로는 도플러효과나 오실레이터의 노화에 따라서 대역이 변화하게 된다. 따라서 이를 동기화(Synchronization)을 해줘야지만 이를 수신할 수 있게 된다.
 물론 이를 동기화 하지 않고 수신하는 기법(DPSK)도 있지만 성능이 떨어진다.
Bandwidth of signal
 신호에 절대값을 씌웠을 때,
 Halfpower bandwidth : 3dB 가 되는 지역, 즉 Power 가 최대의 절반이 되는 지점까지
 Noise equivalent bandwidth : 노이즈와 파워가 동등해지는 대역
 Nulltonull bandwidth : 최대값을 기준으로 처음으로 0이되는 양쪽 지점 사이 대역폭
 Fractional power containment bandwidth
 Bounded power spectral density
Modulation
 Encoding information in a manner suitable for transmission.:
 Translate baseband source signal to bandpass signal
 Basdpass signal: “modulated signal”
 Why need modulation?:
 Small antenna size
Modulation and Demodulation
 Major sources of erros:
 Thermal noise (AWGN):
 distrubs the signal in an additive fashion (Additive)
 has flat spectral density for all frequencies of interest (White)
 is modeled by Gaussian random process (Gaussian Noise)
 InterSymbol Interference (ISI):
 Due to the filtering effect of transmitter, channel and receiver, symbols are “smeared”.
 Thermal noise (AWGN):
Basic Modulation Techniques
 Amplitude Modulation (AM)
 Frequency Modulation (FM)
 Frequency Shift Keying (FSK)
 Phase Shift Keying (PSK)
 Quadrature Phase Shift Keying (QPSK)
 Quadrature Amplitude Modulation (QAM)
Amplitude Modulation (AM)
 Amplitude of arrier signal is varied as the message signal to be transmitted.
 Frequency of carrier signal is kept constant.
Frequency Modulation (FM)
 FM integrates message signal with carrier signal by varying the instantaneous frequency.
 Amplitude of carrier signal is kept constant.
Frequency Shift Keying (FSK)
 1/0 represented by two different frequencies slightly offset from carrier frequency
Phase Shift Keying (PSK)
 Use alternative sine wave phase to encode bits
Receiver job for Demoulation
 Demodulation and sampling:
 Waveform recovery and preparing the received signal for detection:
 Improving the signal power to the noise power (SNR) using matched filter (project to signal space)
 Reducing ISI using equalizer (remove channel distortion)
 Samplign the recovered waveform
 Waveform recovery and preparing the received signal for detection:
 Detection:
 Estimate the transmitted symbol based on the received sample
Receiver structure
 Step 1  waveform to sample transofrmation: (demodulate & sample)
 Frequency downconversion : For bandpass signals
 Receiving filter
 Equalizing filter : Compensation for channel induced ISI
 Step 2 decision making:(detect)
 Threshold comparison
Signal Space Concept
 What is a signal space?:
 Vector representations of signals in an Ndimensional orthogonal space
 Why do we need a signal space?:
 It is a menas to convert signals to vectors and vice versa.
 It is a means to calculate signals energy and Euclidean distances between signals.
 Why are we interested in Euclidean distances between signals?:
 For detection purposes: The received signal is transformed to a received vectors.
 The signal which has the miniumum distance to the received signal is estimated as the transmitted signal.
Signal space
 To form a signal space, first we need to know the inner product between two signals:
 Inner (scalar) product:
 \[<x(t),y(t)> = \int_{\infty}^{\infty} x(t) y^{*}(t) dt\]
 = crosscorrelation between x(t) and y(t)
 Properties of inner product:
 <ax(t), y(t)> = a <x(t), y(t)>
 <x(t), ay(t)> = a* <x(t), y(t)>
 <x(t) + y(t), z(t) > = <x(t), z(t)> + <y(t), z(t)>
 Inner (scalar) product:
 The distance in singal space is measure by calculating the norm.
 What is norm?:
 Norm of a signal:
 \[x(t) = \sqrt{<x(t), x(t)>} = \sqrt{\int_{\infty}^{\infty} x(t)^2 dt} = \sqrt{E_x}\]
 \[ax(t) = a x(t)\]
 Norm between two signals:
 \[d_{x,y} =  x(t)  y(t) \]
 Norm of a signal:
 We refer to the norm between two signals as the Euclidean distance between two signals.
Orthogonal signal space
 Ndimensional orthogonal signal space is chracterized by N linearly independent functions \(\{\psi_j(t) \}_{j=1} ^N\) called basis functions. The basis functions must satisfy the orthogonality condition
 \(<\psi_i(t), \psi_j(t)> = \int_0^T \psi_i(t) \psi_j^*(t)dt = K_i \delta_{ji}\), \(0 \le t \le T\), \(j,i = 1,...,N\)
 where \(\delta_{ij} = \begin{case} 1 > i = j \\\ 0 > i \not = j \end{case}\)
 If all \(K_i=1\), the signal space is orthonormal.
 Constructing Orthonormal basis from nonorthnormal set of vectors:
 GramSchmidt precedure
 Example : BPSK
Signal space
 Any arbitrary finite set of waveforms \(\{s_i(t)\}_{i=1}^M\) where each member of the set is of duration T, can be expressed as a linear combination of N orthogonal waveforms \(\{\psi_j (t)\}_{j=1}^N\) where \(N \le M\)
 \[s_i(t) = sum_{j=1}^N a_{ij} \psi_j(t)\]
 where \(a_{ij} = \frac{1}{K_j}<s_i(t), \psi_j(t)> = \frac{1}{K_j} \int_{0}^T s_i(t) \psi_j(t) dt\), \(j=1,...N\), \(i=1,...,M\), \(0 \le t \le T\)
 \(s_i = (a_{i1}, a_{i2}, ..., a_{iN})\) : vector representation of waveform

$$E_i = \sum_{j=1}^N K_j a_{ij} ^2$$ : Waveform energy
Quadrature Amplitude Modulation (QAM)
 Combination of AM and PSK
 Two carriers out of phase by 90 deg are amplitude modulated
Chapter 6.
Network Software
 Layered Architecture:
 To reduce their design complexity, most networks are organized as a stack of layers or levels.
 The purpose of each layer is to offer certain services to the higher layers, shielding those layers from the details of how the offered services are actually implemented
 Protocol: An agreement between communicating parties on how communication is to proceed.
Terminologies
 The entities comprising the corresponding layers on different machines are called peers.
 Interface: defines which primitive operations and services the lower layer makes available to upper one.
 A set of layers and protocols is called a network architecture.
 A list of protocols used by a certain system, once protocols per layer, is called a protocol stack
Service Primitives
 Tells the service to perform some action or report an action taken by a peer entity
 Sequence chart in a simple clientserver interaction on a connectionoriented network
Reference Models
 Network Protocol Suites that are heavily referenceed:
 OSI refernce Model
 TCP/IP
Data Link Layer
 Provides for reliable transfer of information across the physical link
 Sends blocks (frames) with the necessary synchronization, error control and flow control
 Usually subdivided by Medium Access Control(MAC) and Logical Link Control (LLC)
Multiple Radio Access
 Multiple access networks:
 Each node is attached to a transmitter/receiver which communicates via a medium shared by other nodes
 Transmission from any node is received by other nodes
Multiple Access
 Multiple access issues:
 If more than one node transmit at a time on the broadcast channel, a collision occurs
 How to determin which node can transmit?
 Multiple access protocols:
 Solving multiple access issues
 Contentionfree vs Contentionbased(Conflictbaased)
Contentionfree protocols
FDMA (Frequency Division Multiple Access)
 Single channel per carrier
 All fist generation systems use FDMA
TDMA (Time Division Multiple Access)
 Multiple channels per carrier
 Most of second generation systems use TDMA
Combining TDMA and FDMA
 Each channel gets a certain frequency band for a certain amount of time. Example :GSM
 Advantages:
 More robust against frequencyselective interference
 Much greater capacity with time compression
 Inherent tapping protection
 Disadvantages:
 Frequency changes must be coordinated
CDMA (Code Division Multiple Access)
 User share bandwidth by using code sequences that are orthogonal to each other
 Some second generation systems use CDMA
 Most of third generation systems use CDMA
Types of Channels
 Control channel:
 Forward (Downlink) control channel
 Reverse (uplink) control channel
 Traffic channel:
 Forward traffic (information) channel
 Reverse traffic (information) channel
Duplexing Methods for Radio Links
Frequency Division Duplex(FDD)
 Forward link frequency and reverse link frequency is different.
 In each link, signals are continuously transmitted in parallel.
Time Division Duplex (TDD)
 Forward link frequency and reverse link frequency is the same.
 In each link, signals take turns just like a pingpong game.
Frequency Hopping Spread Spectrum (FHSS)
Direct Sequnce Spread Spectrum (DSSS)
 This sequnce can be mapped into bipolar notations
 \[S * T = \frac{1}{m} \sum_{i=1}^m S_i T_i = 0\]
 \[S * S = \frac{1}{m} \sum_{i=1}^m S_i S_i = \frac{1}{m} \sum_{i=1}^m S_i^2= \frac{1}{m} \sum_{i=1}^{m} (\pm 1)^2 = 1\]
 \[S * \bar S = 1\]
 During each bit time,:
 a station can transmit a 1 by sending its chip sequence,
 it can transmit a 0 by sending the negative of its chip sequence,
 Or it can be silent and transmit nothing
 At the receiving station, the transmitted bit is recovered by computing the inner producet of received signal and its chip sequence
 For example, if the received signal \(S = A + \bar B + C\), the receiver computes
 \[S * C = (A + \bar B + C) * C = A*C + \bar B * C + C *C = 0 + 0 + 1 = 1\]
 and determines that bit 1 has been transmitted independent of what is the signal for A, B, and D is.
ContentionBased Protocols
 ALOHA:
 Developed in the 1970s for a packet radio network by Hawaii University.
 Whenever a station has a data, it transmits. Sender finds out whether transmission was successful or experienced a collision by listening to the broadcase from the destination station. Sender retransmits after some random time if there is a collision.
 Slotted ALOhA:
 Improvement: Time is slotted and a packet can only be transmitted at the beginning of one slot. Thus, it can reduce the collision duration.
 CSMA(Carrier Sense Multiple Access):
 Improvement: Start transmission only if no transmission is ongoing
 CSMA/CD (CSMA with Collision Detection):
 Improvement: Stop ongoing transmission if a collision is detected
 CSMA/CA (CSMA with Collision Avoidance):
 Improvement: Wait a random time and try agian when carrier is quite. If is still quit, then transmit
 CSMA/CA with ACK
 CSMA/CA with RTS/CTS
ALOHA analysis
 In poission process:
 \[P(k,t)= \frac{(\lambda t)^k e^{ \labmda t}}{k!}, k=0,1,2...\]
 E[Number of attempts in t seconds] = \(\lambda t\)
 Assumptions:
 Assume backlogged frames randomized sufficently, so that retransmissions can be recirculated and counted as new arrivals:
 New overall Poisson arrival rate G > \(\lambda\)
 G is therefore defined as the rate of attempted transmissions(including retransmissions and new arrivals)
 In reality, G is time varying, but assume constant for our analysis
 The probability that a transmitted frame is successful is defined as \(P_0\)
 The throughput S is defined as the departure rate of the system.
 Therefor, \(S = G P_0\) in this notation.
 Assume backlogged frames randomized sufficently, so that retransmissions can be recirculated and counted as new arrivals:
 Unslotted analysis:
 \[P_0 = e^{2G}\]
 \[S=GP_0=Ge^{2G}\]
 To maximize throughput, maximize departure rate
 G=0.5 > 18% maximum efficiency
 if G > 0.5, too many collisions
 if G < 0.5, too many idle slots
 Slotted analysis assumptions:
 Frames all have same length
 Time is slotted, and users synchronized
 Nodes listen to results (1s later) to determine what happend
 All frames either collide or perfectly received
 Now, vulnerable period is cut in half
 G=1, 36% maximum efficiency
 Tradeoff between ALOHA and roundrobin(Time Division Multiplexing):
 TDM : avoid collisions, but longer average delays
 Aloha : small delay (immediately transmit), but collisions possible
Summary of Aloha
 Some problems:
 Inefficient(good for infrequent transactions in a large user population)
 Not good for backtoback data transmissions
 Some stabilization techniques have achieved throughputs on order of 50%
 Still, a good technique for many users
CMSA (Carrier Sense Multiple Access)
 CSMA gives imporved throughput compared to Aloha protocols.
 Listens to the channel befor transmitting a packet
Nonpersistent / xpersistent CSMA Protocols
 Nonpersistent CSMA Protocol:
 Step 1 : If the medium is idel, transmit immediately
 Step 2 : If the medium is busy, wait a random amount of time and repeat Step1
 Random backoff reduces probability of collisions
 Waste idel time if the backoff time is too long
 1persisten CSMA Protocol:
 Step 1 : If the medium is idel, transmit immediately
 Step 2 : If the medium is busy, continue to listen until medium becomes idel, and then transmit immediately
 There will always be a collision if two nodes want to retransmit
 ppersistent CSMA Protocol:
 Step 1 : If the medium is idel, transmit with probability p, and delay for one propagation delay with probability (1p)
 Step 2 : If the medium is busy, continue to listen until medium becomes idle, then go to Step 1
 Step 3 : If transmission is delayed by one time slot, continue with Step 1
 A good tradeoff between nonpersistent and 1persistent CSMA
How to select probability p?
 Assume that N nodes have a packet to send and the medium is busy
 Np is the expected number of nodes that will attempt to transmit once the medium becomes idle
 If Np > 1, then a collision is expected to occur. Therefore, network must make sure that Np < 1, where N is the maximum number of nodes taht can be activate a time
CSMA/CD (CSMA with Collision Detection)
 In CSMA, if 2 terminals begin sending packet at the same time, each will transmit its complete packet(although collision is takign place).
 Wasting medium for an entire packet time.
 CSMA/CD:
 Step 1: If the medium is idel, transmit
 Step 2: If the medium is busy, continue to listen until the channel is idel then transmit
 Step 3: If a collision is detected during transmission, cease transmitting
 Step 4: Wait a random amount of time and repeats the same algorithm
CSMA/CA (CSMA with collision Avoidance)
 All terminals listen to the medium same as CSMA/CD.
 Terminal ready to transmit senses the medium.
 If medium is busy it waits until the end of current transmission.
 It again waits for an additional predetermined time period DIFS (Distributed inter frame Space)
 Then picks up a random number of slots (the initial value of backoff counter) within a contention window to wait before transmitting its frame.
 if there are transmissions by other terminals during this time period (backoff time), the terminal freezes its counter.
 It resumes count down after other terminals finish transmission + DIFS. The terminal can start its transmission when the counter reaches to zero.
CSMA/CA with ACK
 Immediate Acknowlegements from receiver upon reception of data frame.
 ACK frame transmitted after time interval SIFS (Short InterFrame Space) (SIFS < DIFS)
 Receiver transmits ACK without sensing the medium.
 If ACK is lost, retransmission done.
Hidden node problem
 CSMA will be ineffective here
CSMA/CA with RTS/CTS
 Transmitter sends a RTS (request to send) after medium has been idle for time interval more than DIFS.
 Receiver responsds with CTS (clear to send) after medium has been idle for SIFS.
 Then data is exchnaged.
 RTS/CTS is used for reserving channel for data transmission so that the collision can only occur in control message.
Exponential Backoff
 When transmitting a packet, choose a backoff interval in the range[0, cw]:
 cw is contention window
 Count down the backoff interval when medium is idle:
 Countdown is suspended if medium becomes busy
 When backoff interval reaches 0, transmit RTS
Backoff Interval
 Choosing a large cw leads to large backoff intervals and can result in larger overhead
 Choosing a small cw leads to a larger number of collisions (when two nodes count down to 0 simultaneously)
 Since the number of nodes attempting to transmit simultaneously may change with time, some mechanism to manage contentions is needed.
 IEEE 802.11 DCF : contention window cw is chosen dynamically depending on collision occurrence.
Chapter 13, 5, 10
Network Layer Protocols
Why Wireless?
 Objective:
 anything, anytime, anywhere
 Advantages:
 Spatial flexibility in radio reception range
 Ad hoc networks without former planning
 No problems with wiring
 Robust against disasters like earthquake, fire
 Disadvantages:
 Generally very low transmission rates for higher numberfs of users
 Many national regulations, global regulations are evolving slowly
 Restricted frequency range, interferences of frequencies
Wireless vs. Mobile
 Two aspects of mobility:
 user mobility. user communicate (wireless), anytime, anywhere with anyone.
 device portability: devices can be connected any time, anywhere to the network
Wireless Routing
 So, the routing(network) still relies upon the existing wireline routing protocols with apperas in Chapter 9.
 Instead, we will discuss true wireless multihop networks called MANET (Mobile Ad hoc Network) which is an autonomous system of nodes(MSs) connected by wireless links.
 A MANET does not necessarily need support from any existing network infrastructure like an Internet gateway or other fixed stations.
Chracteristics of Ad Hoc Networks
 Dynamic topologies: Network topology may change dynamiccaly as the nodes are free to move or battery is off.
 No oracle for configuration : Distributed and Selforganizing.
 Bandwidthconstrained, variable capacity links: Realized throughput of wireless communication is less than the radio’s maximum transmission rate. Collision occurs frequently (Low BW relative to wired).
 Energyconstrained operation: Some nodes in the ad hoc network may rely on batteries or other exhaustible means for their energy.
 Limited physical security: More prone to physical security threats than fixed cable networks.
Routing in MANETS  Goals
 Provide the maximum possible reliability  use alternative routes if an intermediate node fails.
 Choose a route with the least cost metric (memory, bandwidth, power, etc).
 Give the nodes the best possible response time and throughput.
 Route computation must be distributed. Centralized routing in a dynamic network is usually very expensive.
 Routing computation should not involve the maintenance of global state.
 Every node must have quick access to routes on demand.
 Each node must be only concerned about the routes to its destination.
 Broadcast should be avoided(highly unreliable)
 It is desirable to have a backup route when the primary route has become stale.
Routing Classification
 The existing routing protocols can be classified as:
 Proactive: when a packet neetds to be forwarded, the route is already known.
 Reactive: Determine a route only when there is data to send.
 Routing protocols may also be categorized as:
 Table Driven protocols
 Source Initiated (on demand) protocols
Table Driven Routing Protocols
 Each node maintains routing information independently of need for communication
 Update messages send throughout the network periodically or when network topology changes.
 Low latency, suitable for realtime traffic
 Bandwidth might get wasted due to periodic updates
 They maintain O(N) state per node, N = #nodes
 Examples are:
 Destination Sequenced Distance Vector routing (DSDV)
 Clusterhead Gateway Switch routing (CGSR)
 Wireless Routing Protocol (WRP)
Destination Sequenced Distance Vector Routing (DSDV)
 Based on the BellmanFord algorithm.
 Each mobile node maintains a routing table in terms of number of hops to each destination, i.e., every node knows “where” everybody else is.
 Routing table updates are periodically transmitted.
 Each entry in the table is marked by a sequence number which helps to distinguish stale routes from new ones, and thereby avoiding loops.
 To minimize the routing updates, variable sized update packets are used depending on the number of topological changes. (incremental dump of changes)
Clusterhead Gateway Switch Routing (CGSR)
 CGSR is a clustered multihop mobile wireless network with several heuristic routing schemes.
 A distributed clusterhead (CH) selection algorithm is used to select a node as the cluster head.
 It modified DSDV by using a hierarchical CH to route traffic.
 Gateway nodes serve as bridge nodes between two or more clusters.
 A packet sent by a node is first routed to its CH and then the packet is routed from the CH to a gateway of another cluster and then to the CH and so on, until the destination cluster head is reached.
 Frequent changes in the CH may affect the performance of the routing protocol.
SourceInitiated OnDemand Routing (Reactive)
 Each source discovers route(s) to its destination only when the source needs it.
 Save energy and bandwidth during inactivity
 Can be busrty > congestion during high activity
 Significant delay might occur as a result of route discovery
 Good for light load, collapse in large loads
 Examples are:
 Dynamic Source Routing (DSR)
 Ad hoc OnDemand Distance Vector (AODV).
Dynamic Source Routing (DSR)
 Each packet header contains a route, which is represented as a complete sequence of nodes between a sourcedestination pair
 Protocol consists of two phases:
 route discovery
 route maintenance
 Optimizations for efficiency:
 Route cache
 Piggybacking
 Error handling
 The protocol consists of two major phases: Route Discovery, Route Maintenance.
 When a mobile node has a packet to send to some destination, it first consults its route cache to check whether it has a route to that destination.
 If it is an unexpired route, it will use this route.
 If the node doest not have a route, it initiates route discovery by broadcasting a Route Request packet.
 This Route Request contains the address of the destination, along with the source address.
 Each node receiving the packet checks to see whether it has a route to the destintaiton. If it does not, it adds its own address to the route record of the packet and forwards it.
 A route reply is generated when the request reaches either the destination itself or an intermediate node that contains in its route cache an unexpired route to that destination.
 If the node generating the route reply is the destination, it places the route record contained in the route request into the route reply.
### Adhoc On Demand Distance Vector (AODV)
 On demand protocol that uses sequence numbers to build loop free routes
 Key difference from DSR si that source route is no longer required
 Path discovery:
 Reverse path setup
 Forward path setup
 Table management and path maintenance
 Local connectivity management
 AODV is an improvement over DSDV, which minimizes the number of required broadcasts by creating routes on demand.
 Nodes that are not in a selected path do not maintain routing information or participate in routing table exchanges.
 A source node initiates a path discvoery process to loacate the other intermediate nodes(and the destination), by boradcasting a Route Request (RREQ) packet to its neighbors.
The Cellular Concept
 Cell shape : Ideal(Circle), Actual(Not circle), 실제로는 빈틈 없이 모델링을 하기 위해서 육각형을 많이 사용한다.
 Signal Strength
 Handoff Region:
 By looking at the variation of signal strength from either base station it is possible to decide on the optimum area where handoff can take place.
 한 기지국에서 이동하면서 더 좋은 기지국으로 접속해야한다. 이때 넘겨지는 영역을 Handoff Region이라고 한다. (Handover Region)
Cell Capacity
 Average number of MSs requesting service (Average arrival rate): \(\lambda\)
 Average length of time MS requires service (Average holding time): T
 Offered load: \(a = \labmda T\)
 e.g., in a cell with 100 MSs, on an average 30 requests are gnerated during an hour, with average holding time T = 360 secs.
 Then, arrivatl rate \(\lambda = 30 / 3600\) requests/sec.
 A channel kept busy for one hour is defined as on Erlang
 e.g., \(a = 30/3600 \text{calls/sec} * 360 \text{sec / call} = 3 \text { Erlangs }\)
 Average arrival rate during a short interval t is given by \(\lambda t\)
 Assuming Poisson distribution of service requests, the probability P(n, t) for n calls to arrive in an interval of length t is given by:
 \[P(n, t) = \frac{(\lambda t)^n}{n!} e^{\lambda t}\]
 Assumming \(\mu\) to be the service rate, probability of each call to terminate during interval t is given by \(\mu t\)
 Thus, probability of a given call requires service for time t or less is given by:
 \[S(t) = 1  e^{\mu t}\]
Erlang B and Erlang C
 Probability of an arriving call being blocked is:
 \(B(C, a) = \frac{a^C}{C!} \frac{1}{\sum_{i=1}^C \frac{a^i}{i!}}\) : Erlang B formula
 Probabilty of an arriving call beign delayed is:
 \(C(C, a) = \frac{\frac{a^C}{(C1)! (Ca)}}{\frac{a^C}{(C1)!(Ca)} + \sum_{i=0}^{C1} \frac{a^i}{i!}}\) : Erlang C formula
 where C(C,a) is the probability of an arriving call being delayed with a load and C Channels.
Efficiency (Utilization)
 Efficiency = Traffic non blocked / Capacity = Erlangs * portions of nonrouted traffic / Number of trucks(channels)
Cell Structure
 육각형으로 모델링을 하는데, 인접한 Cell끼리는 서로 다른 주파수 영역을 써서, 간섭(interference)과 동시전송(cross talk)을 방지하고자 한다.
Frequency Reuse
 인접한 영역끼리 같은 주파수를 못쓴다. 반대로 말하면, 인접하지 않으면 같은 주파수를 쓸수 있다는 뜻이다. 따라서 주파수를 다시 재활용 해야한다.
 인접하지 않은(간섭을 주지 않는) 영역끼리는 같은 주파수를 사용할 수 있게 한다.
Reuse Distance
 For hexagonal cells, the reuse distance is given by:
 \[D = \sqrt(3N) R\]
 where R is cell radius and N is the reuse pattern (the cluster size of the number of cells per cluster).
 Reuse factor is:
 \[\frac{D}{R} = \sqrt{3N}\]
 The cluster size of the number of cells per cluster is given by:
 \[N = i^2 + ij + j^2\]
 where i and j are integers.
 N = 1,3,4, 7, 9 …
 The popular value of N begin 4 and 7.
Cochannel Interference
 Cochannel interference ratio is given by:
 \(\frac{C}{I} = \frac{\text{Carrier}}{\text{Interference}} = \frac{C}{\sum_{k=1}^M I_k + N}\) : SINR
 where I is cochannel interference and M is the maximum number of cochannel interfering cells.
Cell Splitting
 Large cell(low density)
 Small cell(high density) : low power consumption and powerful signal but frequent handover
 Depending on traffic patterns the smaller calls may be activated/deactivated in order to efficiently use cell resources.
 femto cell : 아파트 한 층
 picocell : 아파트 건물 하나
 microcell : 도시(urban)
 macrocell : 대도시(suburban)
Cell Sectoring by Antenna Design
Cellular SYstem
 MS : Mobile Station
 BTS: Base Transceiver System
 BSC: BS Controller
 MSC: Mobile Switching Center
 VLR: Visitor Location Register
 HLR: Home Location Register
 AUC: AUthentication Center
 EIR: Equipment Identify Register
Registration
 Wireless system needs to know whether MS is currently located in its home area or some other area (routing of incoming calls).
 This is done by periodically exchagning signals between BS and MS known as beacons.
 BS perioidically boradcasts beacon signal (e.g., 1 signal per second) to determine and test the MSs around.
 Each MS listens to the beacon, if it has not heard it previously then it adds it to the active beacon kernel table.
 This information is used by the MS to locate the nearest BS.
 Information carried by beacon signal: cellular network identifier, timestamp, gateway address ID of the paging area, etc.
Steps for Registration
 MS listens to a new beacon, if it’s a new one, MS adds it to the active beacon kernel table.
 If MS decides that it has to communicate through a new BS, kernel modulation initiates handoff process.
 MS locates the nearest BS via user level processing.
 The visiting BS performs user level processing and decides:
 Who the user is?
 What are it access permissions?
 Keeping track of billing.
 Home site sends appropriate authentication response to the current serving BS.
 The BS approves/disapproves the user access.
Handoff
 Change of radio resoruces from one cell to adjacent one.
 Handoff depends on cell size, signal strength, fading, reflection, etc.
 Handoff can be initiated by MS or BS and could be due to:
 Radio link
 Network management
 Service issues
 Radio link handoff is due to mobility of MS.
 It depends on:
 Number of MSs in the cell
 Number of MSs that have left the cell
 Number of calls generated in the cell
 Number of calls transferred from the neighboring cells
 Number of calls terminated in the cell
 Number of calls that were handoff to neighboring cells
 Number of active calls in the cell
 Cell population
 Total time spent in the cell by a call
 Arrival time of a call in the cell
 etc.
 Network management may cause handoff if there is drastic imbalance of traffic in adjacent cells and optimal balance of resources is required.
 Serivce related handoff is due to the dagradation of Qos(Quality of service)
Time for Handoff
 Factors deciding right time for handoff:
 Signal strength
 Signal phase
 Combination of above two
 Bit error rate(BER)
 Distance
 Need for Handoff is determined by:
 Signal strength
 SINR(Signal to Interference and Noise Ratio)
Handoff initiation
 One option is to do handoff where the two signal strengths are equal.
 If MS moves back and forth around this point, it will result in too frequent handoffs(pingpong effect).
 Therefore, MS is allowed to continue with the existing BS till the signal strength decreased by a threshold value E.
 Different cellular systems follow different handoff procedures.
Types of Handoff
 Hard Handoff (break before make):
 Releasing current resources from the prior BS before acquiring resources from the next BS.
 FDMA & TDMA follow this type of handoff.
 Soft Handoff (make before break):
 In CDMA, since the same channel is used, we have to change the code of the handoff, if the code is not orghogonal to the codes in the next BS.
 Therefore, it is possible for the MS to communicate simultaneously with the prior BS as well as the new BS.
Roaming
 To move from a cell controlled by one MSC area to a cell connected to another MSC.
 Beacon signals and the use of HLRVLR allow the MS to roam anywhere provided we have the same service provider, using that particular frequency band.