GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.
Spring 2016: Principles of Digital Communications
[TOC]
- index
- notations
- OSI model
- modem : transmitter/receiver pair (result of contracting terms modulator and demodulator)
- pulse train :
$w(t)=\sum_{i=0}^\infty s_i p(t-iT_0)$ -
Nyquist result : can fit
$n=2BT$ non-interfering pulses in $T$s with $B$Hz bandwidth - engineering contraints
- symbols cannot take arbitrarily large value
$[A,-A]$ - receiver cannot estimate symbol with infinite precision
$\pm\delta$
- symbols cannot take arbitrarily large value
- alphabet size : at most
$m=1+A/\delta$ - sequence :
$m^n$ distinct$n$ -length sequences ($2^k$ bits sequences) - highest possible rate (without noise) : $\frac{k}{T}\le 2B\log_2(1+\frac{A}{\delta})$bps
- thermal noise : emmitted by every conductor, error-free communication impossible, but error can be as small as wanted
-
channel capacity : $\frac{k}{T}\le 2B\log_2(1+\frac{P}{N_0B})$bps with
$P$ signal power and$N_0/2$ power spectral density of white gaussian noise - communication system over bandlimited gaussian channel
- entropy :
$-\sum_{i=1}^m p_i\log_2p_i$
- random variable : mapping from the sample space to the reals
- AWGN : discrete-time additive white gaussian noise
-
communication system
- source : random variable
$H={0,\ldots (m-1)}$ with$P_H(i)$ - transmitter : mapping from to signal set
$C={c_o,\ldots,c_{m-1}}$ (signal constellation) - channel :
$P_{Y_1,\ldots,Y_n\mid X_1,\ldots, X_n}(y_1,\ldots,y_n\mid x_1,\ldots,x_n)=\Pi_{i=1}^n P_{Y_i\mid X_i}(y_i\mid x_i)$ - receiver : random variable
$\hat H\in H$ with receiver decision$î$ 
- source : random variable
-
hypothesis testing
- maximize correct probability :
$P_c=Pr{\hat H=H}=E[P_{H|Y}(\hat H(Y)\mid Y)]=\int_y P_{H\mid Y}(\hat H(y)\mid y)f_Y(y)dy$ - minimize error probability :
$P_e=1-P_c=\sum_{i}P_e(i)P_H(i)$ - prior probability :
$P_H(h)$ - channel :
$f_{Y\mid H}(y\mid h)$ - a posteriori probability :
$P_{H\mid Y}(i\mid y)=\frac{P_H(i)f_{Y\mid H}(y\mid i)}{f_Y(y)}$
- maximize correct probability :
-
maximum a posteriori (MAP) :
$\hat H_{MAP}(y)=\arg\max_{i\in H}P_{H\mid Y}(i\mid y)=\arg\max_{i\in H}P_H(i)f_{Y\mid H}(y\mid i)$ - minimize the error
- maximize correctness :
$Pc=E[P_{H\mid Y}(\hat H(Y)\mid Y)]=\int_y P_{H\mid Y}(\hat H(y)\mid y)f_Y(y)dy$ - optimum
-
maximum likelihood (ML) :
$\hat H_{ML}(y)=\arg\max_{i\in H} f_{Y\mid H}(y\mid i)$ - in case of uncertainty
- unknown prior
- not optimum
- ML = MAP if prior uniform
-
binary hypothesis testing
-
binary MAP test : inverse comparison if negative division
- likelihood ratio :
$\Lambda(y)$ - threshold :
$\eta$ - log likelihood ratio :
$\ln(\Lambda(y))$ 
- likelihood ratio :
-
decision function :
$\hat H:Y\to H$ (decoding function)- decision regions :
$R_i={y\in Y : \hat H(y)=i}$ - region error probability :
$P_e(i)=Pr{Y\in R_1\mid H=i}=Pr{\Lambda(Y)\ge\eta\mid H=i}=\int_{R_1}f_{Y\mid H}(y\mid i)dy$
- decision regions :
-
law of total expection :
$E[Z]=\sum_w E[Z\mid W=w]P_W(w)$ -
$m$ -ary hypothesis testing : as binary -
Q-function :
$Pr{Z\ge x}=Q(x)=\frac{1}{\sqrt{2\pi}}\int_x^\infty e^{-\zeta^2/2}d\zeta$ with$Z\sim N(0,1)$ - with
$Z\sim N(m,\sigma^2)$ ,$Pr{Z\ge x}=Q(\frac{x-m}{\sigma})$ -
$Q(0)=1/2$ ,$Q(1)\sim 0.158$ ,$Q(100)\sim 0$ ,$Q(-1)=1-Q(1)$ - alternative expression :
$Q(x)=\frac{1}{\pi}\int^{\pi/2}_0 e^{-\frac{x^2}{2\sin^2\theta}}d\theta$ 
- with
-
discrete-time AWGN channel
- binary decision for scalar observation
-
$H=0:Y\sim N(c_0,\sigma^2)$ and$H=1:Y\sim N(c_1,\sigma^2)$ - threshold
$\theta$ : middle point between$c_0$ and$c_1$ - error :
$P_e=P_H(0)Q(\frac{\theta-c_0}{\sigma})+P_H(1)Q(\frac{c_1-\theta}{\sigma})=Q(\frac{d}{2\sigma})$ if equiprobable and$d$ distance
-
- binary decision for
$n$ -tuple-
$H=0:Y=c_0+Z\sim N(c_0,\sigma^2 I_n)$ and$H=1:Y=c_1+Z\sim N(c_1,\sigma^2 I_n)$ $N(c_i,\sigma^2 I_n)=\frac{1}{(2\pi\sigma^2)^{n/2}}\exp(-\frac{||y-c_i||^2}{2\sigma^2})$ - error :
$P_e=P_H(0)Q(\frac{d}{2\sigma}+\frac{\sigma\ln\eta}{d})+P_H(1)Q(\frac{d}{2\sigma}-\frac{\sigma\ln\eta}{d})=Q(\frac{d}{2\sigma})$ if equiprobable and$d$ distance
-
-
$m$ -ary decision for$n$ -tuple $\hat H_{ML}(y)=\arg\max_{i\in H}f_{Y\mid H}(y\mid i)=\arg\min_i||y-c_i||$ - PAM of
$m$ points (pulse amplitude modulation) :$P_e(2-\frac{2}{m})Q(\frac{d}{2\sigma})$ 
- QAM of
$m$ points (quadrature amplitude modulation) :$P_e=2Q(\frac{d}{2\sigma})-Q^2(\frac{d}{2\sigma})$ defined for all$m=(2i)^2$ ,$i$ integer
- PSK of
$m$ points (phase shift keying) :$P_e=2Q(\frac{\sqrt{\epsilon_s}}{\sigma}\sin\frac{\pi}{m})$ 
- binary decision for scalar observation
-
inner product :
$<u,v>=b^Ha$ with$h$ hermitian -
norm :
$||u||=\sqrt{<u,v>}$ with$||a\pm b||^2=||a||^2+||b||^2\pm \re(<a,b>)$ -
markov chain
$U\to V\to W$ :$P_{W\mid V,U}(w\mid v,u)=P_{W\mid V}(w\mid v)$ , reversible,$P_{U,W\mid V}(u,w\mid v)=P_{U\mid V}(u\mid v)P_{W\mid V}(w\mid v)$ -
sufficient statistic
$T$ :$H\to T(Y)\to Y$ , error probability of MAP decoder do not different from$Y$ - irrelevant : part not include in
$T(y)$ - Fisher-Neyman :
$f_{Y\mid H}(y\mid i)=g_i(T(y))h(y)\iff T(y)$ is a sufficient statistique for each$i\in H$ , often use indicator function
- irrelevant : part not include in
-
union bound :
$P(\cup_{i=1}^m A_i)\le\sum_{i=1}^m P(A_i)$ -
bounded region :
$B_{i,j}={y: P_H(j)f_{Y\mid H}(y\mid j)\ge P_H(i)f_{Y\mid H}(y\mid i)}$ with$R_i^c\subseteq\cup_{j\not=i}B_{i,j}$ , contains $y$s for which a MAP decision would choose$j$ over$i$ - upper bound error probability :
$P_e(i)=\sum_{j\not=i}\int_{B_{i,j}}f_{Y\mid H}(y\mid i)dy$ - ML with AWGN :
$P_e(i)\le\sum_{j\not=i} Q(\frac{||c_j-c_i||}{2\sigma})$
- upper bound error probability :
-
union bhattacharyya bound : if not AWGN, rewrite
$B_{i,j}={y:\frac{P_H(j)f_{Y\mid H}(y\mid j)}{P_H(i)f_{Y\mid H}(y\mid i)}\ge 1}$ - bound :
$Pr{Y\in B_{i,j}\mid H=i}\le\sqrt{\frac{P_H(j)}{P_H(i)}}\int_{y\in\R^n}\sqrt{f_{Y\mid H}(y\mid i)f_{Y\mid H}(y\mid j)}dy$ - total error :
$P_e\le\sum_i\sum_{j\not=i}\sqrt{P_H(i)P_H(j)}\int_{y\in\R^n}\sqrt{f_{Y\mid H}(y\mid i)f_{Y\mid H}(y\mid j)}dy$
- bound :
-
Gram-Schmidt :
$\alpha_i=\beta_i-\sum_{j=1}^{i-1}<\beta_i,\psi_j>\psi_j$ and$\psi_i=\frac{\alpha_i}{||\alpha_i||}$
-
continuous-time AWGN channel
-
signal energy :
$||x||^2$ -
waveform channel abstraction
-
inner product :
$<a,b>=\int a(t)b^*(t)dt$ - covariance :
$cov(Z_i,Z_j)=E[Z_iZ_j^*]$ -
white gaussian noise : power spectral density
$\frac{N_0}{2}$ if$Z_i=\int N(\alpha)g_i(\alpha)d\alpha$ has$cov(Z_i,Z_j)=\frac{N_0}{2}<g_i,g_j>$ -
$g_i(t)$ orthonormal :$Z_i$ are zero-mean Gaussian iid with variance$\sigma^2=\frac{N_0}{2}$
-
-
sufficient statistic :
$Y_i=\int R(\alpha)\psi_i^*(\alpha)d\alpha$ for hypothesis$H$ with orthonormal basis${\psi_1(t),\ldots,\psi_n(t)}$ -
$H=i$ :$Y_j=\int R(\alpha)\psi_j^*(\alpha)=c_{i,j}+Z_{|V,j}$ - projected noise :
$Z_{|V,j}\sim N(0,\frac{N_0}{2}I_n)$ on$j$ element of orthonormal basis
-
-
decomposed transmitter and receiver
-
rectanguler pulse position modulation : low decay of side lobes, electrical circuit
-
frequency-shift keying : wireless communication
-
sinc pulse position modulation : finite support in frequency domain
-
spread spectrum :
$s_{i,1},\ldots,s_{i,n}\in{\pm 1}^n$ , robust against interfering (non-white, non-gaussian)
-
signal error probability : same as discrete
$P_e=Q(\frac{||c_1-c_0||}{2\sigma})=Q(\sqrt{\frac{\epsilon}{N_0}})$ for codewords$(\sqrt{\epsilon},0)^T$ and$(0,\sqrt{\epsilon})^T$ -
single shot PAM :
$w_i(t)=c_i\varphi(t)$ unit-energy with$c_i\in{\pm a,\pm 3a,\ldots,\pm (m-1)a}$ -
single shot PSK :
$w_i(t)=\sqrt{\frac{2\epsilon}{T}}\cos(2\pi f_ct+\frac{2\pi}{m}i)1_{{t\in[0,T]}}$ with$i$ integer -
single shot QAM
-
equivalent MAP tests
-
correlator
-
matched filter : output sampled at time
$T$ with impulse response$h(t)=b^*(T-t)$ ($T$ enforce causality)$y(t)=\int r(\alpha)h(t-\alpha)d\alpha=\int r(\alpha)b^*(T+\alpha-t)d\alpha$ - at
$t=T$ ,$y(T)=\int r(\alpha)b^*(\alpha)d\alpha$ 
-
map receiver for AWGN :
$n$ dimensions for$m$ signal, alternative former requires$m$ matched filters
-
continous-time channel
- attenuation and amplification : compensated by a cascade of amplifiers, noise also scaled
- low-noise amplifier : filter at first amplification
- automatic gain control (AGC) : bring signal in desired range
- propagation delay and clock misalignment : receiver role to adapt itself
- filtering : refractions modelised as channel impulse response, can be measured and inversed (if bursty, confirmation of impulse response needed or water-filling)
- colored gaussian noise : filtered white noise, whitening filter in the range of interest
- attenuation and amplification : compensated by a cascade of amplifiers, noise also scaled
-
error probability : entirely determined by the codebook
$C={c_0,\ldots,c_{m-1}}$ -
isometry
$a$ :$\alpha,\beta\in V$ keep the distance between$\alpha$ and$\beta$ the same as$a(\alpha)$ and$a(\beta)$ - composition : reflection, rotation, translation
- minimize energy : average energy
$\epsilon=E[||Y||^2]$ - decreased by translation iff mean
$m=E[Y]=\sum_i P_H(i)c_i$ non-zero - best energy in codebook :
$\tilde c_i=c_i-m$ achieve$\tilde\epsilon =\epsilon-||m||^2$ - best set of waveform energy :
$\tilde w_i(t)=w_i(t)-m(t)$ where$m(t)=\sum_i P_H(i)w_i(t)$
- decreased by translation iff mean
-
average energy per bit :
$\epsilon_b$ -
signal space dimension :
$n$ -
number of signal :
$m=|H|$ , typically a power of$2$ -
number of bit :
$k=\log_2 m$ -
transmission rate :
$R_b=\frac{k}{T}=\frac{\log_2(m)}{T}$ bits/second -
message error probability :
$P_e$ , block error -
but error rate :
$P_b$ with$\frac{P_e}{k}\le P_b\le P_e$ -
scalability :
$n$ vs$k$ when$m\to\infty$ using$\epsilon=k\epsilon_b$ and$n=2^k$ -
$n=1$ fixed as$k$ grows : PAM- error :
$P_e=(2-\frac{2}{m})Q(\frac{a}{\sigma})$ - energy :
$\epsilon=\frac{a^2(m^2-1)}{3}$ -
$a=\sqrt{\frac{3\epsilon_b\log_2 m}{(m^2-1)}}\to 0$ hence$P_e\to 1$
- error :
-
$n=2$ fixed as$k$ grows : single-shot PSK- error :
$P_e\ge 2Q(\sqrt{\frac{\epsilon}{\sigma^2}}\sin\frac{\pi}{m})\frac{m-1}{m}\to 1$ - circumference : grows as
$\sqrt{k}$ , number of points grows as$2^k$
- error :
-
$n$ linearly with$k$ : bit by bit- codewords :
$c_{i,j}=b_{i,j}\sqrt{\epsilon_b}$ (+1/-1 bits) - shifts :
$\omega_i(t)=\sum_{j=1}^k c_{i,j}\varphi(t-jT_s)$ - correctness :
$P_c(i)=[1-Q(\frac{\sqrt{\epsilon-b}}{\sigma})]^k\to 0$ - incorrect decoding : does not depends on
$k$ - symbol by symbol : same as bit by bit but with PAM for each dimension
- codewords :
- growing
$n$ exponentially with$k$ : block-orthogonal- waveform :
$\omega_i(t)=\sqrt{\epsilon}\varphi_i(t)$ with$\varphi_1(t)$ orthonormal and$n=m=2^k$ - pulse position modulation :
$\varphi_i(t)=\varphi(t-iT)$ -
$m$ -ary frequency-shift keying :$\omega_i(t)=\sqrt{\frac{2\epsilon}{T}}\cos(2\pi f_i t)1_{t\in[0,T]}$ with$2f_i T=k_i$ - correctness :
$P_c=\int_{-\infty}^\infty \frac{1}{\sqrt{\pi N_0}}\exp{-\frac{(\alpha-\sqrt{\epsilon})^2}{N_0}}[1-Q(\frac{\alpha}{\sqrt{N_0/2}})]^{m-1}$ - error :
$P_e\le\exp[-k(\frac{\epsilon/k}{2N_0}-\ln 2)]\to 0$ with$\sigma^2=\frac{N_0}{2}$ ,$d^2=||c_i-c_j||^2=2\epsilon$ ,$m-1< 2^k$ ,$Q(x)\le\exp[-\frac{x^2}{2}]$ - nonzero component : as large as
$\sqrt{k\epsilon_b}$ where noise same for all
- waveform :
-
-
indistinguishable signal : at level
$\eta$ , difference norm less than$\eta$ -
time-limited signal : indistinguisabhle at level
$\eta$ from$s(t)1_{{t\in(a,b)}}}$ - duration
$T$ : length of interval
- duration
-
frequency-limited signal :
$s_F(f)$ and$s_F(f)1_{{f\in (c,d)}}$ indistinguishable at level$\eta$ - bandwith
$W$ : length of interval
- bandwith
- finite-energy signal : finite duration, finite bandwidth
-
approximate dimension
$n$ : at level$\varepsilon$ during interval$(-\frac{T}{2},\frac{T}{2})$ , fixed collection of$n=n(T,\varepsilon)$ signals${\varphi_1(t),\ldots,\varphi_n(t)}$ st. every signal over the interval indistinguishable at level$\varepsilon$ from$\sum_{i=1}^na_i\varphi_i(t)$ -
slepian theorem
- set
$G_n$ : all signals frequency-limited to$(-\frac{W}{2},\frac{W}{2})$ and time-limited to$(-\frac{T}{2},\frac{T}{2})$ at level$\eta$ - approximate dimension
$n(W,T,\eta,\varepsilon)$ of$G_n$ : at level$\varepsilon$ during interval$(-\frac{T}{2},\frac{T}{2})$ - for every
$\varepsilon>\eta$ :$\lim_{T\to\infty}\frac{n(W,T,\eta,\varepsilon)}{T}=W$ ,$\lim_{W\to\infty}=\frac{n(W,T,\eta,\varepsilon)}{W}=T$ - in short : set of finite-energy signal spanned by
$TW=n$ orthonormal functions - singled-sided bandwidth :
$B$ ,$(-B,B)$ - double-sided bandwith :
$W$ ,$(-W/2,W/2)$
- set
-
bit-by-bit vs block-orthogonal
- error :
$P_e(i)\approx N_d Q(\frac{d_m}{2\sigma})$ - number of dominant terms :
$N_d$ , number of nearest neighbors to$c_i$ - minimum distance :
$d_m$ , distance to a neareat neighbors
- number of dominant terms :
- bit-by-bit
- nearest neighbors :
$N_d=k$ - distance :
$d_m=2\sqrt{\epsilon_b}$ -
$k$ increase :$N_d$ increase,$Q(\frac{d_m}{2\sigma})$ constant
- nearest neighbors :
- block-orthogonal
- nearest neighbors :
$N_d=2^k-1=\exp(k\ln 2)-1$ - distance :
$d_m=\sqrt{2\epsilon}=\sqrt{2k\epsilon_b}$ -
$k$ increase :$\exp(k\ln 2)$ increase,$Q(\frac{d_m}{2\sigma})\le \exp(-\frac{k\epsilon_b}{4\sigma^2})$ decrease
- nearest neighbors :
- error :
-
trade time for bandwidth :
$\phi_i(t)=\sqrt{b}\varphi_i(bt)$ ,$\phi_F(t)=\frac{1}{|b|}\varphi_F(\frac{f}{b})$ -
ultimate rate :
$C=\frac{W}{2}\log_2(1+\frac{2P}{N_0W})=B\log_2(1+\frac{P}{N_0B})$ bps with power$P$ and power spectral density$N_0/2$ watts/Hz
-
symbol by symbol :
$\omega(t)=\sum_{j=1}^ns_j\varphi(t-jT)$ instead of$\omega_i(t)=\sum_{j=1}^nc_{i,j}\varphi(t-jT)$ - $j$th enxcoder output :
$s_j=\varphi(jT)\sqrt{T}$ - waveform former :
$\varphi(t)=\frac{1}{\sqrt{T}}sinc(\frac{t}{T})$ 
- $j$th enxcoder output :
-
sampling theorem
-
$\omega(t)$ : continuous$L_2$ possibily complex -
$\omega_F(f)$ : vanish for$f\not\in[-B,B]$ -
$\omega(t)$ : can be reconstructed from$\omega(nT)$ provided that$T\le\frac{1}{2B}$ - reconstruction :
$w(t)=\sum_{n=-\infty}^\infty\omega(nT)sinc(\frac{4}{t}{T}-n)$
-
-
power spectral density : PSD, spectrum,
$S_X(f)=\frac{|\zeta-F(f)|^2}{T}\sum_k K_X[k]\exp(-j2\pi kfT)$ - model :
$X(t)=\sum_{i=-\infty}^\infty X_i\zeta(t-iT-\Phi)$ -
${X_j}_{j=-\infty}^\infty$ : zero mean wide-sense stationary (WSS) discrete time process -
$\zeta(t)$ : arbitrary$L_2$ function -
$\Phi$ : independent random dither (delay) - self-similarity function :
$R_\zeta(\tau)=\int_{-\infty}^\infty\zeta(\alpha+\tau)\zeta^*(\alpha)d\alpha$ - autocovariance :
$K_X[i]=E[(X_{j+i}-E[X_{j+i}])(X_j-E[X_j])^*]$ - with mean
$0$ :$K_X(\tau)=\sum_k K_X[k]\frac{1}{T}R_\zeta(\tau-kT)$
- with mean
- uncorrelated :
$K_X[k]=\epsilon 1_{{k=0}}$ with$\epsilon=E[|X_i|^2]$ - autocovariance :
$K_X(\tau)=\epsilon\frac{R_\zeta(\tau)}{T}$ - PSD :
$S_X(f)=\epsilon\frac{|\zeta_F(f)|^2}{T}$
- autocovariance :
- model :
-
frequency-domain condition :
$\int_{-\infty}^\infty\varphi(t-nT)\varphi^*(t)dt=1_{{n=0}}$ -
nyquist's criterion : ${\varphi(t-jT)}{j=-\infty}^\infty$ with $\varphi(t)\in L_2$ consists of ortthonormal functions iff $l.i.m.\sum{k=-\infty}^\infty |\varphi_F(f-\frac{k}{T})|^2=T$ (left side of equality has
$1/T$ period) -
nyquist example
$|\varphi_F(f)|^2=T1_{{-\frac{1}{2T}<f<\frac{1}{2T}}}(f)$ $|\varphi_F(f)|^2=Tcos^2(\frac{\pi}{2}fT)1_{{-\frac{1}{T}<f<\frac{1}{T}}}(f)$ $|\varphi_F(f)|^2=T(1-T|f|)1_{{-\frac{1}{T}<f<\frac{1}{T}}}(f)$
-
nyquist comments
- constant but not
$T$ : orthogonal to$T$ -space time translate even when equal to other constant than$T$ ($||\varphi(t)||^2\not=1$ ) - minimum bandwidth :
$\frac{1}{2T}$ - test for bandwiths between
$\frac{1}{2T}$ and$\frac{1}{T}$ : if$|\varphi_F(f)|^2$ vanishes outside$[-1/T,1/T]$ , nyquist satisfied iff$|\varphi_F(\frac{1}{2T}-\varepsilon)|^2+|\varphi_F(-\frac{1}{2T}-\varepsilon)|^2=T$ 
- test for arbitrary finite bandwidths :
$|\varphi_F(f)|^2$ wider than$1/T$ , nysquist satisfied iff$g(\varepsilon)=\sum_{i\in I}|\varphi_F(f_i+\varepsilon)|^2$ for$\varepsilon\in[-\frac{1}{2T},\frac{1}{2T}]$ 
- constant but not
-
root-raised-cosine family
- when
$\beta=0$ :$\varphi(t)=\sqrt{1/T}sinc(\frac{1}{T})$
- when
-
eye diagrams
- noiseless output :
$y(jT)=\sum_i s_iR_\varphi((j-i)T)=s_j$ - truncated pulse : too short, could be not orthogonal
- inter-symbol interference : ISI,
$y(jT)=\sum_is_il_{j-i}$ with$l_i=R_\varphi(iT)$ - when
$R_\varphi(\tau)$ nonzero for more than one sample - when matched filter output not sampled at correc times :
$l_i=R_\varphi(iT+\Delta)$
- when
- should have single value at
$t=0$ - more space in middle : more tolerant to small sampling variation (jitter), larger
$\beta$ 
- noiseless output :
-
sinc-rect relation :
$b=cd$ ,$d=2ab$ 
-
binary source symbols :
${\pm 1}$ rather than${0,1}$ , factoring out$\sqrt{\epsilon_s}$ 
-
convolutional encoder : for
$b_j$ produce$x_{2j-1}$ and$x_{2j}$ with$b_{-1}=b_0=1$ - length :
$n=2k$ - usage : only
$2^k/2^n=2^{-k}$ used by codewords
- specification
- source symbols entering : number
$k_0$ - symbols produced : number
$n_0>k_0$ - constraint length :
$m_0$ , number of input$k_0$ -tuples used to determine an output$n_0$ -tuple - encoding function :
$k_0\times m_0$ matrix
- source symbols entering : number
- length :
-
decoder
- ML : maximizes
$<c,y>-\frac{||c||^2}{2}$ or$<c,y>$ with$y$ channel output and$c=\sqrt{\epsilon_s}x$ codeword - bruteforce :
$2^k$ sequence
- ML : maximizes
-
viterbi algorithm : VA
- linear
- trellis : for
$y=(1,3),(-2,1),(4,-1),(5,5),(-3,-3),(1,-6),(2,-4)$ - depth
$j=0$ : leftmost initial state - depth
$j=k+2$ : rightmost final state - edge value :
$y_{2j-1}x_{2j-1}+y_{2j}x_{2j}$ for depth$j-1$ to$j$ with output$x_{2j-1},x_{2j}$ - survivor : largest subpath to this depth
- depth
- reference path : by convenience, all-one path
-
detour
- start at depth
$j$ :$\omega_j$ number of bit errors of that detour (number of positions in which they differ) - no start at depth
$j$ :$\omega_j=0$ - incorrect bits :
$\sum_{j=0}^{k-1}\omega_j$ - incorrect fraction :
$\frac{1}{kk_0}\sum_{j=0}^{k-1}\omega_j$ - output distance
$d$ : compare two segments of encoder output, count number position that differ - input distance
$i$ : compare the segments of encoder input sequences, count number position that differ - counting : number of detour
$a(i,d)$ , does not depend on$j$ (time-invariant) nor on reference path (linear encoded) - flow graph : remove self-loop of start state, split it in start and end, label
$I^iD^d$ 
- generating function :
$T(I,D)=\sum_{i,d}I^iD^d a(i,d)$ - detour flow path :
$a_l(i,d)$ from state$s$ and end state$l$ ,$T_l(I,D)=\sum_{i,d}I^iD^da_l(i,d)$ , no detour means$T_l=1$
- detour flow path :
- start at depth
-
bit-error probability :
$P_b$ upperbound- waveform :
$\omega(t)=\sqrt{\epsilon}\sum_{j=1}^nx_j\varphi_j(t)$ with$\varphi_i(t)$ orthonormal - received signal :
$y=(y_1,\ldots,y_n)$ with$y_i=\int r(t)\varphi_i^*(t)dt$ - stochastic model :
$P_b=\frac{1}{kk_0}\sum_{j=0}^{k-1}E[\Theta_j]$ - expectation : $E[\Theta_j]=\sum_h i(h)\pi(h)\le\sum_{i=1}^\infty\sum_{d=1}^\infty i Q(\sqrt{\frac{\epsilon_s d}{\sigma^2}})a(i,d)\le\sum_{i=1}^\infty\sum_{d=1}^\infty i z^da(i,d)=\\ \frac{\partial}{\partial I}\sum_{i=1}^\infty\sum_{d=1}^\infty I^i D^da(i,d)|{I=1,D=z}=\frac{\partial}{\partial I}T(I,D)|{I=1,D=z}$ over all detours with
$z=e^{-\frac{\epsilon_s}{2\sigma^2}}$ - detour probability :
$\pi(h)$ - input distance between detour
$h$ and reference path :$i(h)$ - noise :
$Z\sim N(0,\frac{N_0}{2}I_{2m})$ - upperbound :
$\pi(h)\le Q(\frac{d_E(h)}{2\sigma})=Q(\sqrt{\frac{\epsilon_s d(h)}{\sigma^2}})$ 
- detour probability :
- relation :
$\sum_{i=1}^\infty i f(i)=\frac{\partial}{\partial I}\sum_{i=1}^\infty I^if(i)|_{I=1}$ for any function$f$ - finally :
$P_b=\frac{1}{kk_0}\sum_{j=0}^{k-1}E[\Theta_j]\le\frac{1}{k_0}\frac{\partial}{\partial I}T(I,D)|_{I=1,D=z}$ , need no convergence issue ($0\le z\le 1/2$ )- encoder :
$\frac{T(I,D)}{k_0}$ - channel :
$z^d$ upperbound to ML receiver with Hamming distance$d$ - Bhattacharyya bound :
$z=\sum_y\sqrt{P(y\mid a)P(y\mid b)}$ , guarantee$0\le z\le 1$ (tigher bound can improve to$1/2$ )
- encoder :
- waveform :
- baseband vs passband
-
carrier frequency :
$f_c$ - reflection : if wavelength much smaller than obstacle size
-
diffraction : if wavelength much larger than obstacle size
- sky wave : ionoshpere trapping signal to transmit elsewhere ($300$kHz to $30$Mhz)
- absorption : under sea, very limited bandwith ELF-VLF (
$2$ -$3$dB per $1000$km attentuation on Earth) -
passband signal :
$x(t)=\sqrt{2}\re{\hat x(t)}=\sqrt{2}\re{x_E(t)e^{j2\pi f_ct}}$ -
baseband-equivalent :
$x_E(t)=\hat x(t)e^{-j2\pi f_ct}$ , complex valued -
analytic-equivalent :
$\hat x(t)=\sqrt{2}(x*h_>)(t)$ 
- real-valued : conjugate symmetric
$x_F^*(f)=x_F(-f)$ - purely imaginary : conjugate anti-symmetric
$x_F^*(f)=-x_F(-f)$ -
passband inner product :
$<x,y>=\re{<\hat x,\hat y>}=\re{<x_E,y_E>}$ , orthogonal iff purely imaginary -
norm :
$||x||^2=||\hat x||^2=||x_E||^2$ -
double-sideband modulation with suppressed carrier : DSB-SC
$x(t)=\sqrt{2}b(t)\cos(2\pi f_ct)=\sqrt{2}\re{b(t)e^{j2\pi f_ct}}$ , bandwidth efficiency by removing extra frequencies
-
AM modulation :
$x(t)=(1+mb(t))\sqrt{2}\cos(2\pi f_ct)$ , energy consumed by frequency carrier (allow simpler receiver) -
single-sideband modulation : SSB, amateur radio (efficient use of limited spectrum)
- USB : upper side-band
- LSB : lower side-band
-
quadrature amplitude modulation : QAM, two real valued baseband information signaés
$b(t)=b_R(t)+jb_I(t)$ , bandwidth efficiency by doubling content, two streams doing symbol by symbol
- parts :
$x=\re(z)=\frac{z+\bar z}{2}$ ,$y=\im(z)=\frac{z-\bar z}{2i}$ for$z=x+iy$ -
baseband constellation :
- baseband :
$\omega_{E,i}(t)=\sum_{l=1}^n c_{i,l}\varphi_l(t)$ - passband :
$\omega_i(t)=\sqrt{2}\re{\omega_{E,i}(t)e^{j2\pi f_ct}}=\sum_{l=1}^n\re{c_{i,l}}\varphi_{1,l}(t)+\sum_{l=1}^n\im{c_{i,l}}\varphi_{2,l}(t)$ $\varphi_{1,l}(t)=\sqrt{2}\re{\varphi_l(t)e^{j2\pi f_ct}}$ $\varphi_{2,l}(t)=-\sqrt{2}\im{\varphi_l(t)e^{j2\pi f_ct}}$
- orthonormal :
${\varphi_{1,l}(t),\varphi_{2,l}(t) : l=1,\ldots,n}$ iff$\varphi_l$ frequency-limited to$[-B,B]$ - baseband dimension :
$n$ - passband dimension :
$2n$ -
$2n$ -tuple former :$Y=Y_1+jY_2$ with$Y_l=Y_{1,l}+jY_{2,l}=<\sqrt{2}e^{-j2\pi f_ct}R(t), \varphi_l(t)>$ $Y_{1,l}=<R(t),\varphi_{1,l}(t)>=\re{<\sqrt{2}e^{-j2\pi f_ct}R(t),\varphi_l(t)>}$ -
$Y_{2,l}=<R(t),\varphi_{2,l}(t)>=\im{<\sqrt{2}e^{-j2\pi f_ct}R(t),\varphi_l(t)>}$ 
- baseband :
-
PSK complex : 4-ary,
$w(t)=\sqrt{2\epsilon}\sum_l\cos(2\pi f_ct+\phi_l)\varphi(t-lT)$ for symbol$s_l=\sqrt{\epsilon}e^{j\phi_l}$ , real and imaginary not independent -
QAM complex :
$w(t)=\sqrt{2}\sum_l a_l\cos(2\pi f_ct+\phi_l)\varphi(t-lT)$ for symbol$s_l=a_le^{j\phi_l}$ , twice efficiency of PAM - sub-layer
-
ML rule complex :
$\hat H_{ML}(y)=\arg\min_i||y-c_i||=\arg\max_i \re{<y,c_i>}-\frac{||c_i||^2}{2}$ -
baseband equivalent channel : $U_l=<[\omega_i(t)h(t)]\sqrt{2}e^{-j2\pi f_c t},g_t(t)>=<(\omega_{E,i}(t)+\omega_{E,i}^(t)e^{-j4\pi f_ct})*h_0(t),g_l(t)>=<\omega_{E,i}(t)h_0(t),g_l(t)>$ with $h_0(t)=h(t)e^{-j2\pi f_ct}$, $\omega_i(t)=\frac{1}{2}[\omega_{E,i}(t)e^{j2\pi f_ct}+\omega_{E,i}^(t)e^{-j2\pi f_ct}]$
-
$\omega_{E,i}^*(t)e^{j4\pi f_ct}*h_0(t)$ nothing in common with$g_l(t)$ (frequency) -
$h_0(t)$ : fourrier$h_F(f+f_c)$ 
-
-
independent white gaussian noise
-
$N_R(t)$ ,$N_I(t)$ independent : require any functions$h_1(t)$ ,$h_2(t)$ to give$\int N_R(t)h_1(t)dt$ ,$\int N_I(t)h_2(t)dt$ independent - noise output of down converter :
$\tilde N_E(t)=\tilde N_R(t)+j\tilde N_I(t)$ -
$\tilde N_R(t)=N(t)\sqrt{2}\cos(2\pi f_ct)$ , not independent -
$\tilde N_I(t)=-N(t)\sqrt{2}\sin(2\pi f_ct)$ , not independent
-
-
$Z_i=\int \tilde N_R(t)h_i(t)dt\sim N(0,\frac{N_0}{2}||\sqrt{2}\cos(2\pi f_ct)h_i(t)||^2$ ,$cov(Z_1,Z_2)=\frac{N_0}{2}<\sqrt{2}\cos(2\pi f_ct)h_1(t),\sqrt{2}\cos(2\pi f_ct)h_2(t)>=\frac{N_0}{2}<h_1(t),h_2(t)>$ ,$cov(Z_2,Z_3)=\frac{N_0}{2}<\sqrt{2}\cos(2\pi f_ct)h_2(t),\sqrt{2}\sin(2\pi f_ct)h_3(t)>=0$ - bandlimited to
$[-B,B]$ $B<f_c$ : can model noise$N_E(t)=N_R(t)+jN_I(t)$ independent of spectral density$\frac{N_0}{2}$
-
$\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots+\frac{1}{2^n}=1-\frac{1}{2^n}$ -
$\sqrt{1+x}=1+\frac{x}{2}$ when$x << 1$ $e^x=\lim_{n\to\infty}(1+\frac{x}{n})^n$ - geometric series : converge to
$\sum_{n=1}^\infty ar^{n-1}=\frac{a}{1-r}$ if$|r|<1$ - Riemann series :
$\sum_{n=1}^\infty \frac{1}{p^\alpha}$ converges if$\alpha >1$ $(x+y)^n=\sum_{k=0}^n {n \choose k} x^{n-k}y^k$ $erf(x)=\frac{2}{\sqrt{\pi}}\int_0^xe^{-t^2}dt$ $n!\approx n^ne^{-n}\sqrt{2\pi n}$
$2\sin^2 t = 1-\cos 2t$ $2\cos^2 x = 1+\cos 2x$ $\sin 2x = 2\sin x \cos x$ $\sin(a+b)=\sin a\cos b+\cos a\sin b$ $\cos(a+b)=\cos a\cos b-\sin a\sin b$ $\tan^2 x +1=\frac{1}{\cos^2 x}$ $\cot^2 x +1=\frac{1}{\sin^2 x}$ $\sin 0 = \frac{1}{2}\sqrt{0} = \cos \pi/2 = 0$ -
$\sin \pi/6 = \frac{1}{2}\sqrt{1} = \cos \pi/3 = \frac{1}{2}$ $\sin \pi/4 =\frac{1}{2}\sqrt{2} = \cos \pi/4 =\frac{\sqrt{2}}{2}$
$\sin \pi/3 = \frac{1}{2}\sqrt{3} = \cos \pi/6=\frac{\sqrt{3}}{2}$ $\sin \pi/2 = \frac{1}{2}\sqrt{4} = \cos 0 = 1$ $\cosh z =\frac{e^z+e^{-z}}{2}$ $\sinh z =\frac{e^z-e^{-z}}{2}$ $\cos z =\frac{e^{iz}+e^{-iz}}{2}=\cosh iz$ $\sin z =\frac{e^{iz}-e^{-iz}}{2i}=\frac{\sinh iz}{i}$ $e^z=\cosh z +\sinh z=\cos z+i\sin z$ $e^{-z}=\cosh z -\sinh z$ $\cosh^2 z -\sinh^2 z = 1$ $\sin mx\cos nx=\frac{1}{2}[\sin (m+n)x + \sin (m-n)x]$ $\cos mx\cos nx=\frac{1}{2}[\cos (m+n)x + \cos (m-n)x]$ $\sin mx\sin nx=\frac{1}{2}[-\cos (m+n)x + \cos (m-n)x]$
$\tan'x=\sec^2x$ $\csc'x = -\csc x\cot x$ $\sec'x = \sec x\tan x$ $\cot'x = -\csc^2x$ $\sin'^{-1}x = \frac{1}{\sqrt{1-x^2}}$ $\cos'^{-1}x = -\frac{1}{\sqrt{1-x^2}}$ $\tan'^{-1}x = \frac{1}{1+x^2}$ $\csc'^{-1}x = -\frac{1}{x\sqrt{x^2-1}}$ $\sec'^{-1}x = \frac{1}{x\sqrt{x^2-1}}$ $\cot'^{-1}x = -\frac{1}{1+x^2}$
$\int \ln x dx = x \ln x - x$ $\int x \ln xdx= \frac{1}{4}x^2(2\ln x -1)$ $\int \frac{1}{x\log x}dx=\log (\log x)$ $\int \frac{1}{x\log^2 x}dx=-\frac{1}{\log x}$ $\int \frac{1}{x}dx = \ln |x|$ $\int a^x dx = \frac{1}{\ln a} a^x$ $\int \tan x dx = \ln |\sec x| $ $\int \frac{a}{a^2+x^2}dx = \tan^{-1}\frac{x}{a}$ $\int \frac{a}{a^2-x^2}dx = \frac{1}{2}\ln\left|\frac{x+a}{x-a}\right|$ $\int \frac{1}{\sqrt{a^2-x^2}} dx = \sin^{-1} \frac{x}{a}$ $\int \frac{1}{\sqrt{x^2-a^2}} dx = \cosh^{-1} \frac{x}{a}$ $\int \frac{1}{\sqrt{x^2+a^2}} dx = \sinh^{-1} \frac{x}{a}$ $\int \sin^{-1} x dx=\sqrt{1-x^2}+x\sin^{-1} x$ $\int \cos^{-1} x dx=-\sqrt{1-x^2}+x\cos^{-1} x$ $\int \tan^{-1} x dx=-\frac{1}{2}\ln(x^2+1)+x\tan^{-1} x$ $\int \sin x \cos xdx = -\frac{1}{2}\cos^2 x$ $\displaystyle\int^\pi_{-\pi} 1\cdot \cos (nx),dx=\left.\frac{1}{n}\sin (nx)\right|^{\pi}_{-\pi}=0.$ $\quad\displaystyle\int^\pi_{-\pi} 1\cdot \sin (nx),dx=\left.-\frac{1}{n}\cos (nx)\right|^{\pi}_{-\pi}=0.$ $\displaystyle\int^\pi_{-\pi} \sin (nx)\cos (nx),dx=\left.\frac{\sin^2 (nx)}{2n}\right|^{\pi}_{-\pi}=0.$ $\displaystyle\int^\pi_{-\pi} \sin (mx)\sin(nx),dx=0$ $\displaystyle\int^\pi_{-\pi} \cos (mx)\cos(nx),dx=0$ $\displaystyle\int^\pi_{-\pi} \sin (mx)\cos(nx),dx=0$ - $\int_{{0}}^{{\frac{\pi}{2}}} \sin^n x , dx = \int_{{0}}^{{\frac{\pi}{2}}} \cos^n x , dx = \begin{cases}\frac{n-1}{n} \cdot \frac{n-3}{n-2} \cdots \frac{3}{4} \cdot \frac{1}{2} \cdot \frac{\pi}{2}, & \text{if }n\text{ is even}\\frac{n-1}{n} \cdot \frac{n-3}{n-2} \cdots \frac{4}{5} \cdot \frac{2}{3} & \text{if }n\text{ is odd andmore than 1}\end{cases}$
$\int_{{-c}}^{{c}}\sin {x};\mathrm{d}x = 0 !$ $\int_{{-c}}^{{c}}\cos {x};\mathrm{d}x = 2\int_{{0}}^{{c}}\cos {x};\mathrm{d}x = 2\int_{{-c}}^{{0}}\cos {x};\mathrm{d}x = 2\sin {c} !$ $\int_{{-c}}^{{c}}\tan {x};\mathrm{d}x = 0 !$ $\int_{-\frac{a}{2}}^{\frac{a}{2}} x^2\cos^2 {\frac{n\pi x}{a}};\mathrm{d}x = \frac{a^3(n^2\pi^2-6)}{24n^2\pi^2} \qquad\mbox{(for }n=1,3,5...\mbox{)},!$ $\int_{\frac{-a}{2}}^{\frac{a}{2}} x^2\sin^2 {\frac{n\pi x}{a}};\mathrm{d}x = \frac{a^3(n^2\pi^2-6(-1)^n)}{24n^2\pi^2} = \frac{a^3}{24} (1-6\frac{(-1)^n}{n^2\pi^2}) \qquad\mbox{(for }n=1,2,3,...\mbox{)},!$ $\int_{{0}}^{{2 \pi}}\sin^{2m+1}{x}\cos^{2n+1}{x};\mathrm{d}x = 0 ! \qquad {n,m} \in \mathbb{Z}$ $\int_0^{2\pi} \sin x \cos^2 x d x=0$ $\int_0^{2\pi} \sin^2 x \cos x d x=0$ $\int_0^{2\pi} \sin^2 x d x=\pi$ $\int_0^{2\pi} \cos^2 x d x=\pi$ $\int_0^{2\pi} \sin^4 x d x=\frac{3\pi}{4}$ $\int_0^{2\pi} \cos^4 x d x=\frac{3\pi}{4}$ $\int_0^{2\pi} \sin^2 x \cos^2 x d x=\frac{\pi}{4}$ $\int x\sin xd x=\frac{\sin(n x)-n x \cos(n x)}{n^2}$ $\int x\cos xd x=\frac{nx\sin(n x)+ \cos(n x)}{n^2}$ $\frac{2}{T}\int_0^T\cos(\frac{2\pi n}{T}x)\cos(\frac{2\pi m}{T}x)d x=\frac{2}{T}\int_0^T\sin(\frac{2\pi n}{T}x)\sin(\frac{2\pi m}{T}x)d x\cases{0 &\text{si }n\not=m\\ 1 &\text{si }n=m}$ $\int_0^T\sin(\frac{2\pi n}{T}x)\cos(\frac{2\pi m}{T}x)d x=0$
$\frac{1}{1-ax}=\sum_{n=0}^\infty (ax)^n=1+ax+ax^2+ax^3+\cdots$ $\frac{1}{1+x}=\sum_{n=0}^\infty (-x)^n=1-x+x^2-x^3+\cdots$ $\frac{1}{(1-x)^2}=\sum_{n=0}^\infty (n+1)x^n=1+2x+3x^2+4x^3+\cdots$ $\sin x=\sum_{n=0}^\infty (-1)^n \frac{x^{2n+1}}{(2n+1)!}=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\cdots$ $\cos x=\sum_{n=0}^\infty (-1)^n \frac{x^{2n}}{(2n)!}=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\cdots$ $\tan^{-1} x=\sum_{n=0}^\infty (-1)^n \frac{x^{2n+1}}{2n+1}=x-\frac{x^3}{3}+\frac{x^5}{5}-\cdots$ $ln(1+x)=\sum_{n=1}^\infty (-1)^n \frac{x^n}{n}=x-\frac{x^2}{2}+\frac{x^3}{3}-\cdots$
- Jacobian : $J=|\frac{\partial(x,y)}{\partial(u,v)}|=\begin{vmatrix} \frac{dx}{du}&\frac{dx}{dv} \\ \frac{dy}{du}&\frac{dy}{dv}\end{vmatrix}$
-
substitution :
$\int_{\mathbb D}f(\vec x) d\vec x = \int_S f(T(\vec u)) J d\vec u$ - polar coordinates :
$x = r \cos \theta\quad y = r\sin\theta\quad J=r$ and$\int_{\mathbb D}f(\vec x)d\vec x = \int_a^b \int_{g(\theta)}^{f(\theta)} f(r,\theta)r dr d\theta$ - cylindrial coordinates :
$x = r \cos \theta\quad y = r\sin\theta\quad z=z \quad J=r$ - spherical coordinates :
$x = \rho \sin \phi \cos \theta\quad y = \rho \sin\phi\sin\theta\quad z=\rho\cos\phi \quad J=\rho^2\sin \phi$ where$0 \le \theta \le 2\pi$ and$0\le \phi\le\pi$ (starting on the positive y-axis side) - affine transformations : barycentric coordinates
$\vec x = \vec v_1 \beta_1 + \vec v_2 \beta_2 \quad 0 \le \beta_i \le 1 \quad \beta_1+\beta_2=1$ - rotation matrix : $A=\begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}$
-
gaussienne multivariée :
$f_X(x)=\frac{1}{\sqrt{(2\pi)^ndet\Sigma}}e^{-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)}$ - matrice de covariance :
$\Sigma$ symmetrique et semi-définie postivie - entièrement caractérisisé par les moments d'ordre 1 et 2
- changement de variables linéaire :
$Y=AX+b$ alors$S=A\Sigma A^T$ et$m=A\mu+b$ remplacent$A$ et$\mu$ - décorrelation possible par diagonalisation
- matrice de covariance :