CS 536 ParkFundamentals of information transmissionand coding (a.k.a. communication theory)Signals and functionsElementary operation of communication: send signal onmedium from A to B.• media—copper wire, optical fiber, air/space, ...• signals—voltage and currents, light pulses, radio waves,microwaves, ...→ electromagnetic wave (let there be light!)Signal can be viewed as a time-varying function s(t).CS 536 ParkIf s(t) is “sufficiently nice” (Dirichlet conditions) then s(t)can be represented as a linear combination of complexsinusoids:...+++||CS 536 ParkSimple example:-3-2-101230 2 4 6 8 10 12 14s(t)tsin(t) + sin(2*t) + sin(3*t)-3-2-101230 2 4 6 8 10 12 14s(t)tsin(t)-3-2-101230 2 4 6 8 10 12 14s(t)tsin(2*t)-3-2-101230 2 4 6 8 10 12 14s(t)tsin(3*t)−→ sinusoids form basis for other signalsCS 536 ParkAnalogous to basis in linear algebra:other elements can be expressed as linear combi-nations of “elementary” elements in the basis set−→ like atomsEx.: in 3-D, {(1, 0, 0), (0, 1, 0), (0, 0, 1)} form a basis.−→ (7, 2, 4)=7· (1, 0, 0)+2· (0, 1, 0)+4· (0, 0, 1)−→ coefficients: 7, 2, 4−→ spectrumHow many elements are there in a basis?CS 536 ParkVector spaces:• finite dimensional• infinite dimensional: signals→ infinite number of bases→ subject of functional analysisGiven an arbitrary element in the vector space, how tofind the coefficient of basis elements?−→ e.g., given (7, 2, 4), coefficient of (0, 1, 0)?CS 536 ParkIn linear algebra, matrix inversion:Ax = y ⇔ x = A−1ywhere A is (n × n) matrix, x and y are (n × 1) vectors.−→ solution techniques: e.g., Gaussian eliminationNote: the arbitrary vector y (our “signal”) is representedas a linear combinationy = Ax = x1A1+ x2A2+ ···+ xnAnwhere x =(x1,x2,...,xn) and Aiis the ith columnvector of A.−→ the Ai’s are the bases!−→ correct viewpoint of the world (for us)For continuous (i.e., infinite dimensional) signals ...CS 536 ParkFourier expansion and transform:s(t)=12πZ∞−∞S(ω)eiωtdω,S(ω)=Z∞−∞s(t)e−iωtdt.−→ recall: eiωt= cos ωt + i sin ωt−→ signal s(t) is a linear combination of the eiωt’s−→ S(ω): coefficient of basis elements−→ time domain vs. frequency domainFrequency ω: cycles per second (Hz)−→ ω =1/TT : period of sinusoidCS 536 ParkExample: square wavetω00CS 536 ParkExample: audio (e.g., speech) signalSource: Dept. of Linguistics and Phonetics, Lund UniversityCS 536 ParkRandom function (i.e., white noise) has “flat-looking”spectrum.−→ unbounded bandwidthWhy bother with frequency domain representation?−→ contains same information (invertible) ...−→ convenience−→ brings out “relevant” informationCS 536 ParkLuckily, most “interesting” functions arising in practiceare “special”:−→ bandlimited−→ i.e., S(ω) = 0 for |ω| sufficiently large−→ when S(ω) ≈ 0, can treat as S(ω)=0−→ let’s approximate!−→ e.g., square wavetω00CS 536 ParkEx.: human auditory system−→ 20 Hz–20 kHz−→ speech is intelligible at 300 Hz–3300 Hz−→ broadcast quality audio; CD quality audioTelephone systems: engineered to exploit this property−→ bandwidth 3000 Hz−→ copper medium: various grades−→ no problem transmitting 3000 Hz signalsCS 536 ParkFor communication:Both absolute frequency and bandwidth are relevant.−→ baseband vs. broadband−→ high-speed ⇔ broadbandManipulate shape of different frequency sinusoids to si-multaneously carry information (i.e., bits).−→ multi-lane highway analogy−→ different lane ⇔ different frequencyManipulation of different frequencies can create compli-cated looking s(t).−→ side effect of encoding−→ decoding: use Fourier