Computer Networking and IT Security (CNS) Slides PDF

Chair of Distributed Systems and Security School of Computation, Information and Technology Technical University of Munich Computer Networking and IT Security (CNS) INHN0012 – WiSe...

Chair of Distributed Systems and Security School of Computation, Information and Technology Technical University of Munich Computer Networking and IT Security (CNS) INHN0012 – WiSe 2024/25 Prof. Dr.-Ing. Stephan Günther Chair of Distributed Systems and Security School of Computation, Information and Technology Technical University of Munich Friday 1st November, 2024 08:03 Chapter 1: Physical layer Signals, information, and their meaning A mathematical representation of signals Sampling, reconstruction, and quantization Transmission channel Message transmission Transmission media Literature and references Chapter 1: Physical layer 1-1 Chapter 1: Physical layer Signals, information, and their meaning Information and entropy Signals and their meaning A mathematical representation of signals Sampling, reconstruction, and quantization Transmission channel Message transmission Transmission media Literature and references Chapter 1: Physical layer 1-2 Signals, information, and their meaning Definition – Signals and symbols Signals are time-dependent and measurable physical quantities. Defined measurable signal changes can be assigned a symbol. These symbols are the physical representation of information. Examples for signals light, e. g. transmission of Morse code in navigation voltage, e. g. telegraphy sound, e. g. language and music 0.6 Signal amplitude s(t) 0.4 0.2 0.0 -0.2 -0.4 -0.6 0 1 2 3 time t [s] Figure 1: The first 3 s of „Sunrise Avenue – Hollywood Hills“ Chapter 1: Physical layer — Signals, information, and their meaning 1-3 Information and entropy Definition – Information content The information content of a symbol (sign or character) expresses how much information is transmitted by the sign. The information content has the following properties: The less frequently a character occurs, the higher its information content. The information content of a string is the sum of the information content of the individual characters provided that characters occur independently from each other. The information content of predictable characters is 0 The logarithm is the simplest function to define the information content with these properties. Chapter 1: Physical layer — Signals, information, and their meaning 1-4 Information and entropy Claude Elwood Shannon ∗ April 30, 1916 † February 24, 2001 AT&T Bell Labs: 1941–1958, then professor at the MIT A Mathematical Theory of Communication Communication Theory of Secrecy Systems by Claude E. Shannon by Claude E. Shannon In: The Bell System Technical Journal, In: The Bell System Technical Journal, Vol. 27, No 3, 1948, pp. 379–423 and Vol. 28, No. 4, 1949, pp. 656–715 Vol. 27, No 4, 1948, pp. 623–656 http://netlab.cs.ucla.edu/wiki/files/ https://dl.acm.org/doi/pdf/10.1145/584091.584093 shannon1949.pdf Communication in the Presence of Noise Prediction and Entropy of Printed English by Claude E. Shannon by Claude E. Shannon Proc. Inst. Radio Eng. (IRE) Vol. 37, 1949, pp.10-21 In: The Bell System Technical Journal, Online retyped copy of the paper: Vol. 30, No. 1, 1951, pp. 50–64, https://www.noisebridge.net/images/e/e5/Shannon_ https://archive.org/details/bstj30-1-50 noise.pdf Chapter 1: Physical layer — Signals, information, and their meaning 1-5 Information and entropy Definition – Information Information consists in the uncertainty of being able to predict changes in a signal. The information content of a character x ∈ X from an alphabet X depends on the probability p(x) that the information-carrying signal takes on the value or range of values assigned to this character at the time of observation. The information content I of the character x with probability of occurrence p(x) is defined as I(x) = − log2 p(x) mit [ I ] = bit. 1 Will be covered in Theory of Computation and Information Theory (INHN0013). Chapter 1: Physical layer — Signals, information, and their meaning 1-6 Information and entropy Definition – Information Information consists in the uncertainty of being able to predict changes in a signal. The information content of a character x ∈ X from an alphabet X depends on the probability p(x) that the information-carrying signal takes on the value or range of values assigned to this character at the time of observation. The information content I of the character x with probability of occurrence p(x) is defined as I(x) = − log2 p(x) mit [ I ] = bit. Definition – Entropy The average information content of a source is called entropy X X H(X ) = p(x)I(x) = − p(x) log2 (p(x)). x ∈X x ∈X 1 Will be covered in Theory of Computation and Information Theory (INHN0013). Chapter 1: Physical layer — Signals, information, and their meaning 1-6 Information and entropy Definition – Information Information consists in the uncertainty of being able to predict changes in a signal. The information content of a character x ∈ X from an alphabet X depends on the probability p(x) that the information-carrying signal takes on the value or range of values assigned to this character at the time of observation. The information content I of the character x with probability of occurrence p(x) is defined as I(x) = − log2 p(x) mit [ I ] = bit. Definition – Entropy The average information content of a source is called entropy X X H(X ) = p(x)I(x) = − p(x) log2 (p(x)). x ∈X x ∈X Note: We sometimes use the notations p(x) or px as a short form of Pr[X = x] (read as “the probability that the random variable X takes the value x ”)1. 1 Will be covered in Theory of Computation and Information Theory (INHN0013). Chapter 1: Physical layer — Signals, information, and their meaning 1-6 Information and entropy Examples: 1. Deterministic, discrete source that always emits the character ’A’: X AAAAA... I(A) = − log2 (Pr[X = A]) = − log2 (1) = 0 bit Chapter 1: Physical layer — Signals, information, and their meaning 1-7 Information and entropy Examples: 1. Deterministic, discrete source that always emits the character ’A’: X AAAAA... I(A) = − log2 (Pr[X = A]) = − log2 (1) = 0 bit 2. Binary, discrete source which emits the characters ’0’ or ’1’ in a completely unpredictable way: X 01101... I(0) = − log2 (Pr[X = 0]) = − log2 (0.5) = 1 bit I(1) = − log2 (Pr[X = 1]) = − log2 (0.5) = 1 bit The entropy H(X ) = pi I(xi ) of thus source is P i H(X ) = −(p0 log2 (p0 ) + p1 log2 (p1 )) = −(−0.5 − 0.5) = 1 bit/symbol. Chapter 1: Physical layer — Signals, information, and their meaning 1-7 Information and entropy Examples: 1. Deterministic, discrete source that always emits the character ’A’: X AAAAA... I(A) = − log2 (Pr[X = A]) = − log2 (1) = 0 bit 2. Binary, discrete source which emits the characters ’0’ or ’1’ in a completely unpredictable way: X 01101... I(0) = − log2 (Pr[X = 0]) = − log2 (0.5) = 1 bit I(1) = − log2 (Pr[X = 1]) = − log2 (0.5) = 1 bit The entropy H(X ) = pi I(xi ) of thus source is P i H(X ) = −(p0 log2 (p0 ) + p1 log2 (p1 )) = −(−0.5 − 0.5) = 1 bit/symbol. 3. Unordered characters of a long German text, i. e., X ∈ {A , B , C ,... , Z}: X EWTILEMHCAB... I(E) = − log2 (Pr[X = E]) = − log2 (0.1740) ≈ 2.52 bit The entropy H(X ) of this source is N X H(X ) = − pi log2 (pi ) ≈ 4.0629 bit/symbol, i=1 i. e., German text can be encoded with slightly more than 4 bit per character on average. Note: This applies only to memoryless sources or sufficiently long texts, respectively. Otherwise, conditional probabilities must be considered. Chapter 1: Physical layer — Signals, information, and their meaning 1-7 Signals and their meaning What is the meaning of specific signal? A signal transports information. Only by an interpretation rule this information gets a meaning, i. e., there must be a mapping between symbols (physical signal values or value ranges) and data. Example: Given a binary alphabet with the characters X ∈ {0,1 }. The interpretation rule is 0 s(t) ≤ 0, x = 1 otherwise. What is the meaning of the signal shown below? 1 s(t) 0.5 0 −0.5 0 1 2 3 4 Time t [s] Chapter 1: Physical layer — Signals, information, and their meaning 1-8 Signals and their meaning Open questions 1 s(t) 0.5 0 −0.5 0 1 2 3 4 Time t [s] At what time intervals are samples taken? (Time discretization) Does more frequent sampling also automatically mean more information? (Sampling theorem) How to round continuous signal values? (Quantization) What is the interpretation rule of sampled data? (Line coding) Which interfering factors play a role? (noise, attenuation, distortion,... ) (Channel coding) And how is such a signal generated in the first place? (Impulse shaping, modulation) Chapter 1: Physical layer — Signals, information, and their meaning 1-9 Chapter 1: Physical layer Signals, information, and their meaning A mathematical representation of signals Fourier Series Signal properties Fourier Transform Sampling, reconstruction, and quantization Transmission channel Message transmission Transmission media Literature and references Chapter 1: Physical layer 1-10 Fourier Series Periodic time signals can be understood as a superposition of sine and cosine oscillations of different frequencies: 1.5 1 Signalamplitude s(t) Fourierkoeffizient bk 1.0 0 0.5 −1 0 0 1 2 3 4 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 time t [s] k -harmonics (a) time signal s(t) (b) spectrum S(f ) Fourier Series: (with ω = 2π/T , period T = 2 s) a0 s(t) ≈ 2 Chapter 1: Physical layer — A mathematical representation of signals 1-11 Fourier Series Periodic time signals can be understood as a superposition of sine and cosine oscillations of different frequencies: 1.5 1 Signalamplitude s(t) Fourierkoeffizient bk 1.0 0 0.5 −1 0 0 1 2 3 4 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 time t [s] k -harmonics (a) time signal s(t) (b) spectrum S(f ) Fourier Series: (with ω = 2π/T , period T = 2 s) a0 s(t) ≈ + a1 cos(ω t) + b1 sin(ω t) 2 Chapter 1: Physical layer — A mathematical representation of signals 1-11 Fourier Series Periodic time signals can be understood as a superposition of sine and cosine oscillations of different frequencies: 1.5 1 Signalamplitude s(t) Fourierkoeffizient bk 1.0 0 0.5 −1 0 0 1 2 3 4 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 time t [s] k -harmonics (a) time signal s(t) (b) spectrum S(f ) Fourier Series: (with ω = 2π/T , period T = 2 s) 4 a0 X s(t) ≈ + (ak cos(k ω t) + bk sin(k ω t)) 2 k =1 Chapter 1: Physical layer — A mathematical representation of signals 1-11 Fourier Series Periodic time signals can be understood as a superposition of sine and cosine oscillations of different frequencies: 1.5 1 Signalamplitude s(t) Fourierkoeffizient bk 1.0 0 0.5 −1 0 0 1 2 3 4 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 time t [s] k -harmonics (a) time signal s(t) (b) spectrum S(f ) Fourier Series: (with ω = 2π/T , period T = 2 s) 10 a0 X s(t) ≈ + (ak cos(k ω t) + bk sin(k ω t)) 2 k =1 Chapter 1: Physical layer — A mathematical representation of signals 1-11 Fourier Series Periodic time signals can be understood as a superposition of sine and cosine oscillations of different frequencies: 1.5 1 Signalamplitude s(t) Fourierkoeffizient bk 1.0 0 0.5 −1 0 0 1 2 3 4 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 time t [s] k -harmonics (a) time signal s(t) (b) spectrum S(f ) Fourier Series: (with ω = 2π/T , period T = 2 s) 40 a0 X s(t) ≈ + (ak cos(k ω t) + bk sin(k ω t)) 2 k =1 Chapter 1: Physical layer — A mathematical representation of signals 1-11 Fourier Series Periodic time signals can be understood as a superposition of sine and cosine oscillations of different frequencies: 1.5 1 Signalamplitude s(t) Fourierkoeffizient bk 1.0 0 0.5 −1 0 0 1 2 3 4 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 time t [s] k -harmonics (a) time signal s(t) (b) spectrum S(f ) Fourier Series: (with ω = 2π/T , period T = 2 s) For the limit N → ∞ holds: ∞ a0 X s(t) = + (ak cos(k ω t) + bk sin(k ω t)) 2 k =1 Chapter 1: Physical layer — A mathematical representation of signals 1-11 Fourier Series Fourier series A periodic signal s(t) can be reconstructed as the sum of weighted sinus and cosinus functions. The resulting series s(t) is called Fourier series: ∞ a0 X s(t) = + (ak cos(k ω t) + bk sin(k ω t)). 2 k =1 The sum component with index k is called the k -harmonic. The constant component a0 /2 represents a shift of the signals amplitude regarding the y-axis and therefore is a constant factor of the function. The angular frequency ω = 2π/T defines the periodicity T of the signal The weights ak und bk can be calculated as follows: Z T Z T 2 2 ak = s(t) cos(k ω t) dt and bk = s(t) sin(k ω t) dt. T T 0 0 Chapter 1: Physical layer — A mathematical representation of signals 1-12 Signal properties Calculating the coefficients ak and bk can be done through simple calculations Some signal properties can be seen directly: 1 Z T /2 Signalamplitude s(t) s(t) dt 0 0 Z T s(t) dt T /2 −1 0 1 2 3 4 Zeit t [s] Z
2 T Point symmetry regarding T/2,0 ⇒ a0 = s(t) dt = 0 T 0 No constant component Question: What holds for the signal s ′ (t) = s(t) + c with c > 0? Chapter 1: Physical layer — A mathematical representation of signals 1-13 Signal properties Calculating the coefficients ak and bk can be done through simple calculations Some signal properties can be seen directly: 1 Signalamplitude s(t) 0 −1 0 1 2 3 4 Zeit t [s] All weights of the cosinus components are zero, that is ak = 0 ∀k ∈ N Reason: s(t) is in-phase with the sinus Question: What happens if we shift s(t) by 90°? Chapter 1: Physical layer — A mathematical representation of signals 1-13 Fourier Transform So far, we have only looked at periodic signals. So what happens if we introduce non-periodic signals to the equation? We cannot use the fourier series anymore We result with a continuous spectrum, rather than a discrete one Fourier Transformation The fourier transform of a steady rising, integrable function s(t) is defined as Z ∞ Z ∞ s(t) b r S(ω ) = s(t)e −j ω t dt = s(t) (cos(ω t) − j sin(ω t)) dt , −∞ −∞ where j denotes the imaginary unit and ω = 2π f the angular frequency. The equivalency e jx = cos(x) + j sin(x) is known as Euler’s formula. Chapter 1: Physical layer — A mathematical representation of signals 1-14 Fourier Transform So far, we have only looked at periodic signals. So what happens if we introduce non-periodic signals to the equation? We cannot use the fourier series anymore We result with a continuous spectrum, rather than a discrete one Fourier Transformation The fourier transform of a steady rising, integrable function s(t) is defined as Z ∞ Z ∞ s(t) b r S(ω ) = s(t)e −j ω t dt = s(t) (cos(ω t) − j sin(ω t)) dt , −∞ −∞ where j denotes the imaginary unit and ω = 2π f the angular frequency. The equivalency e jx = cos(x) + j sin(x) is known as Euler’s formula. Example: Square impulse and associated spectrum 0.8 1 0.7 Basic impulse g(t) Spectrum |G(f )| 0.6 0.5 0.5 0.4 0.3 0 0.2 -2 -1 0 1 2 -5 -4 -3 -2 -1 0 1 2 3 4 5 Time t in multiples of period T Frequency f Chapter 1: Physical layer — A mathematical representation of signals 1-14 Chapter 1: Physical layer Signals, information, and their meaning A mathematical representation of signals Sampling, reconstruction, and quantization Sampling Reconstruction Quantization Signal types (overview) Transmission channel Message transmission Transmission media Literature and references Chapter 1: Physical layer 1-15 Sampling, reconstruction, and quantization Naturally occurring signals are continuous in time and continuous in value, i.e., they take on arbitrary real values at infinitely many points in time. Problem for computers: limited memory limited precision Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-16 Sampling, reconstruction, and quantization Naturally occurring signals are continuous in time and continuous in value, i.e., they take on arbitrary real values at infinitely many points in time. Problem for computers: limited memory limited precision Solution approach: Discretization of signals in the time domain (sampling) and value domain (quantization). A discrete-time and discrete-value signal is digital and is stored in fixed-length words. A Q 0001 0010 0011 Comparison: Usage of fixed or floating point numbers instead of real numbers corresponds to rounding (quantization) to a finite number of discrete steps. Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-16 Sampling The signal s(t) is sampled using the unit pulse (Dirac pulse) δ [t] at equidistant intervals Ta (sampling interval) for n ∈ Z: ∞  X 1 t = nTa , ŝ(t) = s(t) δ [t − nTa ], with δ [t − nTa ] = 0 otherwise. n=−∞ Since ŝ(t) is nonzero only at times nTa for integer n, we agree on the notation ŝ[n] for discrete-time but continuous-value signals. 1 s(t) 0.5 0 −0.5 0 1 2 3 4 Time t [s] Figure 2: Time continuous signal s(t) Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-17 Sampling The signal s(t) is sampled using the unit pulse (Dirac pulse) δ [t] at equidistant intervals Ta (sampling interval) for n ∈ Z: ∞  X 1 t = nTa , ŝ(t) = s(t) δ [t − nTa ], with δ [t − nTa ] = 0 otherwise. n=−∞ Since ŝ(t) is nonzero only at times nTa for integer n, we agree on the notation ŝ[n] for discrete-time but continuous-value signals. 1 s(t) ŝ[n] 0.5 0 −0.5 0 1 2 3 4 Time t [s] Figure 2: Time continuous signal s(t) and corresponding discrete samples ŝ[n] Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-17 Reconstruction By means of the samples ŝ[n] it is possible to approximate or even reconstruct the original signal s(t): ∞   X t − nTa s(t) ≈ ŝ[n] · sinc. Ta n=−∞ Samples are support points and serve as weights for a suitable approximate function (trigonometric interpolation, cf. polynomial interpolation). 1 s(t) ŝ[n] 0.5 0 −0.5 0 1 2 3 4 Time t [s] Figure 3: Samples ŝ[n] Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-18 Reconstruction By means of the samples ŝ[n] it is possible to approximate or even reconstruct the original signal s(t): ∞   X t − nTa s(t) ≈ ŝ[n] · sinc. Ta n=−∞ Samples are support points and serve as weights for a suitable approximate function (trigonometric interpolation, cf. polynomial interpolation). 1 s(t) ŝ[n] ŝ · sinc(t/3 − 6) 0.5 0 −0.5 0 1 2 3 4 Time t [s] Figure 3: Each sample ŝ[n] serves as a weight for the reconstruction function. Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-18 Reconstruction By means of the samples ŝ[n] it is possible to approximate or even reconstruct the original signal s(t): ∞   X t − nTa s(t) ≈ ŝ[n] · sinc. Ta n=−∞ Samples are support points and serve as weights for a suitable approximate function (trigonometric interpolation, cf. polynomial interpolation). 1 s(t) ŝ[n] 0.5 0 −0.5 0 1 2 3 4 Time t [s] Figure 3: Each sample ŝ[n] serves as a weight for the reconstruction function. Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-18 Reconstruction By means of the samples ŝ[n] it is possible to approximate or even reconstruct the original signal s(t): ∞   X t − nTa s(t) ≈ ŝ[n] · sinc. Ta n=−∞ Samples are support points and serve as weights for a suitable approximate function (trigonometric interpolation, cf. polynomial interpolation). 1 s(t) ŝ[n] 13 support points 0.5 0 −0.5 0 1 2 3 4 Time t [s] Figure 3: The sum of the weighted functions approaches the original signal depending on the number of summing elements. Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-18 Reconstruction By means of the samples ŝ[n] it is possible to approximate or even reconstruct the original signal s(t): ∞   X t − nTa s(t) ≈ ŝ[n] · sinc. Ta n=−∞ Samples are support points and serve as weights for a suitable approximate function (trigonometric interpolation, cf. polynomial interpolation). 1 s(t) 13 support points 17 support points 0.5 0 −0.5 0 1 2 3 4 Time t [s] Figure 3: The sum of the weighted functions approaches the original signal depending on the number of summing elements. Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-18 Reconstruction Under which conditions is a lossless reconstruction possible? Multiplication in the time domain corresponds to convolution in the frequency domain: s(t) · δ [t − nT ] b r 1 S(f ) ∗ δ [f − n/T ]. T This convolution with unit pulses corresponds to a shift of S(f ) along the abscissa. Consequently, the sampling of the signal s(t) at intervals Ta corresponds to the periodic repetition of its spectrum S(f ) at intervals fa = 1/Ta. Example: Sampling of a signal s(t) band limited on some maximum frequency B with sampling frequency fa = 4B : 1 1 Frequency components S(f ) 0.8 Signal amplitude s(t) 0.5 0.6 0 0.4 0.2 −0.5 0 0 1 2 3 4 -10 -8 -6 -4 -2 0 2 4 6 8 10 Time t [s] Frequency f [Hz] (schematic) Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-19 Reconstruction Under which conditions is a lossless reconstruction possible? Multiplication in the time domain corresponds to convolution in the frequency domain: s(t) · δ [t − nT ] b r 1 S(f ) ∗ δ [f − n/T ]. T This convolution with unit pulses corresponds to a shift of S(f ) along the abscissa. Consequently, the sampling of the signal s(t) at intervals Ta corresponds to the periodic repetition of its spectrum S(f ) at intervals fa = 1/Ta. Example: Sampling of a signal s(t) band limited on some maximum frequency B with sampling frequency fa = 4B : 1 1 Frequency components S(f ) 0.8 Signal amplitude s(t) 0.5 0.6 0 0.4 0.2 −0.5 0 0 1 2 3 4 -10 -8 -6 -4 -2 0 2 4 6 8 10 Time t [s] Frequency f [Hz] (schematic) Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-19 Reconstruction Shannon and Nyquist sampling theorem A signal s(t) band-limited to |f | ≤ B is fully described by equidistant samples ŝ[n], provided they are no farther apart than Ta ≤ 1/2B. The sampling frequency, which allows a complete signal reconstruction, is consequently bounded below by fa ≥ 2B. 1 1 Frequency components S(f ) 0.8 2B Signal amplitude s(t) 0.5 0.6 0 0.4 Ta 0.2 −0.5 0 0 1 2 3 4 -10 -8 -6 -4 -2 0 2 4 6 8 10 Time t [s] Frequency f [Hz] (schematic) Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-20 Reconstruction Shannon and Nyquist sampling theorem A signal s(t) band-limited to |f | ≤ B is fully described by equidistant samples ŝ[n], provided they are no farther apart than Ta ≤ 1/2B. The sampling frequency, which allows a complete signal reconstruction, is consequently bounded below by fa ≥ 2B. 1 1 Frequency components S(f ) 0.8 Aliasing if fa < 2B Signal amplitude s(t) 0.5 Ta 0.6 0 0.4 2B 0.2 −0.5 0 0 1 2 3 4 -10 -8 -6 -4 -2 0 2 4 6 8 10 Time t [s] Frequency f [Hz] (schematic) If one chooses fa < 2B , the periodic repetitions of the spectrum overlap This effect is known as aliasing In that case, a lossless reconstruction is no longer possible. Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-20 Quantization The samples ŝ[n] ∈ R are still continuous in the range of values and cannot be stored exactly. Solution: Quantization In order to differentiate between M = 2N signal stage, we need code words of N bit A specific code word is assigned to each signal stage in the process The signal stages are distributed in the quantization interval in a sensible way What is “sensible”? Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-21 Quantization The samples ŝ[n] ∈ R are still continuous in the range of values and cannot be stored exactly. Solution: Quantization b=4 In order to differentiate between M = 2N signal stage, we need code words of N bit 111 A specific code word is assigned to each signal stage in the process 3 The signal stages are distributed in the quantization interval in a sensible way 110 What is “sensible”? 2 101 Example: Linear quantization with mathematical rounding 1 100 This scheme is optimal if all values within IQ occur with equal probability 0 ∆ b−a 011 Step width ∆ = M −1 Within IQ the maximum quantization error is qmax = ∆/2 010 Signal values outside IQ are mapped to the largest or smallest signal stage, respectively ⇒ the quanti- −2 zation error is unbounded outside of IQ 001 −3 000 a = −4 Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-21 Quantization The samples ŝ[n] ∈ R are still continuous in the range of values and cannot be stored exactly. Solution: Quantization b=4 In order to differentiate between M = 2N signal stage, we need code words of N bit 111 A specific code word is assigned to each signal stage in the process 3 The signal stages are distributed in the quantization interval in a sensible way 110 What is “sensible”? 2 101 Example: Linear quantization with mathematical rounding 1 100 This scheme is optimal if all values within IQ occur with equal probability 0 ∆ b−a 011 Step width ∆ = M −1 Within IQ the maximum quantization error is qmax = ∆/2 010 Signal values outside IQ are mapped to the largest or smallest signal stage, respectively ⇒ the quanti- −2 zation error is unbounded outside of IQ 001 −3 What if the signal values are not uniformly distributed? 000 a = −4 Linear quantization is typically suboptimal Non-linear quantization is used, for example, in the digitization of speech or music Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-21 Quantization Example: Linear quantization within the interval I = [−0.5; 0.5] mit N = 3 bit: 1 1 s(t) qe (t) ≤ qmax s(t) qe (t) > qmax 0.5 0.5 0 0 −0.5 −0.5 0 1 2 3 4 0 1 2 3 4 Time t – quantized signal s(t) (blue) Time t – quantization error qe (t) = s(t) − s(t) Code word 000 001 010 011 100 101 110 111 Signal stage −7/16 −5/16 −3/16 −1/16 1/16 3/16 5/16 7/16 Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-22 Quantization Example: Linear quantization within the interval I = [−0.5; 0.5] mit N = 3 bit: 1 1 s(t) qe (t) ≤ qmax s(t) qe (t) > qmax 0.5 0.5 0 0 −0.5 −0.5 0 1 2 3 4 0 1 2 3 4 Time t – quantized signal s(t) (blue) Time t – quantization error qe (t) = s(t) − s(t) Code word 000 001 010 011 100 101 110 111 Signal stage −7/16 −5/16 −3/16 −1/16 1/16 3/16 5/16 7/16 Question: Why is the highest signal stage at 7/16 and not at 1/2 ? Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-22 Quantization Example: Linear quantization within the interval I = [−0.5; 0.5] mit N = 3 bit: 1 1 s(t) qe (t) ≤ qmax s(t) qe (t) > qmax 0.5 0.5 0 0 −0.5 −0.5 0 1 2 3 4 0 1 2 3 4 Time t – quantized signal s(t) (blue) Time t – quantization error qe (t) = s(t) − s(t) Code word 000 001 010 011 100 101 110 111 Signal stage −7/16 −5/16 −3/16 −1/16 1/16 3/16 5/16 7/16 Question: Why is the highest signal stage at 7/16 and not at 1/2 ? Remarks: The assignment of code words to signal levels is in principle arbitrary However, one often chooses a code which reduces the effect of single bit errors (e. g. Gray code: Adjacent codewords differ only in one binary digit each, i. e., the Hamming distance is 1). Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-22 Signal types (overview) 1 1 0.5 0.5 0 0 −0.5 −0.5 0 1 2 3 4 0 1 2 3 4 (a) Analog s(t) (b) Discrete time and continuous value ŝ[n] 1 1 0.5 0.5 0 0 −0.5 −0.5 0 1 2 3 4 0 1 2 3 4 (c) Time continuous and discrete value s(t) (d) Digital s[n] Chapter 1: Physical layer — Sampling, reconstruction, and quantization 1-23 Chapter 1: Physical layer Signals, information, and their meaning A mathematical representation of signals Sampling, reconstruction, and quantization Transmission channel Channel effects Channel capacity Message transmission Transmission media Literature and references Chapter 1: Physical layer 1-24 Transmission channel From the last subchapter we should know: What are the differences between analog, discrete-time, discrete-value and digital signals? How must a signal be sampled so that no information is lost? Under what conditions can a naturally occurring signal be reconstructed from sampled and quantized values without loss? How should the samples be quantized if within the quantization interval each signal level is equally likely? In this subchapter we clarify the following questions: What influence does the transmission channel have on a signal? What is the theoretically maximum achievable transmission rate? Chapter 1: Physical layer — Transmission channel 1-25 Channel effects Model of a (linear, time-invariant) channel with one input and one output: X Channel Y Our model considers: η Attenuation (Signal amplitude of the useful signal at the output is lower than at the input) Low pass filter (higher frequencies are attenuated more than low ones) Delay (the transfer takes some time) Noise in shape of additive white Gaussian noise (AWGN)1 Among others, we do not consider the following effects: Interference by other transmissions Reflections of our own signal Distortions due to non linear filtering effects, among others in dependency of the signal amplitude Time variant effects, e. g. objects or people may have an influence on wireless transmissions 1 AWGN is a simplifying model conception of noise processes. In reality, there is no AWGN. Chapter 1: Physical layer — Transmission channel 1-26 Channel effects Example: 1 Signal amplitude s(t) 0 −1 0 1 2 3 4 5 6 7 8 9 10 Time t Figure 4: Idealized transmitted signal Chapter 1: Physical layer — Transmission channel 1-27 Channel effects Example: 1 Signal amplitude s(t) 0 −1 0 1 2 3 4 5 6 7 8 9 10 Time t Figure 4: Transmit signal after attenuation and low-pass influences by the channel Chapter 1: Physical layer — Transmission channel 1-27 Channel effects Example: 1 Signal amplitude s(t) 0 −1 0 1 2 3 4 5 6 7 8 9 10 Time t Figure 4: Transmit signal after attenuation and low-pass influences through the channel as well as with AWGN Chapter 1: Physical layer — Transmission channel 1-27 Channel capacity We have already seen that a channel has similar effects like a low pass filter and additional noise distorts the transmission. Because of the low-pass characteristic of channels, one can speak of a channel bandwidth B : Low frequencies pass unhindered (low pass) High frequencies are attenuated Above a certain frequency, the attenuation is so strong that the relevant signal components can be neglected Simplified we assume a sharp upper bound for B : Frequencies |f | < B pass Frequencies |f | ≥ B are filtered What is the achievable data rate on a channel with bandwidth B ? For this we need a connection between the channel bandwidth B , the number M of distinguishable signal stages, and the relation between the power of the useful signal and the noise. Chapter 1: Physical layer — Transmission channel 1-28 Channel capacity Noise-free, binary channel We remember the sampling theorem: A signal bandlimited to B must be sampled at least at the frequency 2B in order to reconstruct the signal without loss, i.e. so that no information is lost. Viewed the other way around: We obtain up to 2B distinguishable2 symbols from a signal limited to bandwidth B. If you scan more frequently, you do not gain any new information. This leads to a new interpretation of the frequency f = 2B , which is also called Nyquist rate. Definition: Nyquist rate Let B be the cutoff frequency of a bandlimited channel. Then the Nyquist rate fN = 2B is a lower bound for the sampling frequency that allows a complete reconstruction of the signal and an upper bound for the number of symbols per time interval that are distinguishable after transmission. 2 Sufficiently sensitive measuring systems provided Chapter 1: Physical layer — Transmission channel 1-29 Channel capacity Noise-free, M -ary channel Assuming that not only two but M = 2N distinguishable symbols can be transferred. How does the achievable data rate change? We remember quantization and entropy: With a word width of N bit, M = 2N discrete signal stages can be represented. If a source emits all characters (symbols) with the same probability, the entropy (and thus the average information) of the source is maximal. Consequently, for the transmission rate over a channel of bandwidth B , we obtain the maximum rate 2B log2 (M) bit. Hartleys theoreom On a channel of bandwidth B with M distinguishable signal stages, the channel capacity bounded above by CH = 2B log2 (M) bit. Interesting: If we could distinguish any number of signal stages from each other, the achievable data rate would be unlimited! Where is the problem? Chapter 1: Physical layer — Transmission channel 1-30 Channel capacity Noise Noise makes it hard to tell signal levels apart The finer the signal levels are selected, the more difficult this becomes 1 Signal amplitude s(t) 0 −1 0 1 2 3 4 5 6 7 8 9 10 Time t Measure of the strength of the noise Signal power PS SNR = = Noise power PN The Signal to Noise Ratio (SNR) is given as dB: SNR dB = 10 · log10 (SNR) Chapter 1: Physical layer — Transmission channel 1-31 Channel capacity Noise Noise makes it hard to tell signal levels apart The finer the signal levels are selected, the more difficult this becomes 1 Signal amplitude s(t) 0 −1 0 1 2 3 4 5 6 7 8 9 10 Time t Measure of the strength of the noise Example: PS = 1 mW, PN = 0,5 mW   Signal power PS 1 SNR = = SNR = 10 · log10 dB ≈ 3,0 dB Noise power PN 0,5 The Signal to Noise Ratio (SNR) is given as dB: SNR dB = 10 · log10 (SNR) Chapter 1: Physical layer — Transmission channel 1-31 Channel capacity Theorem of Shannon and Hartley On a channel of bandwidth B with additive white noise with noise power PN and signal power PS , the upper bound for the achievable data rate is   PS CS = B log2 1+ bit. PN Derivation of the theorem: see Shannon’s 1949 publication Communication in the Presence of Noise. Chapter 1: Physical layer — Transmission channel 1-32 Channel capacity Theorem of Shannon and Hartley On a channel of bandwidth B with additive white noise with noise power PN and signal power PS , the upper bound for the achievable data rate is   PS CS = B log2 1+ bit. PN Derivation of the theorem: see Shannon’s 1949 publication Communication in the Presence of Noise. Comparison with Hartley’s law:   b−a CH = 2B log2 (M) = 2B log2 bit. ∆ Chapter 1: Physical layer — Transmission channel 1-32 Channel capacity Theorem of Shannon and Hartley On a channel of bandwidth B with additive white noise with noise power PN and signal power PS , the upper bound for the achievable data rate is   PS CS = B log2 1+ bit. PN Derivation of the theorem: see Shannon’s 1949 publication Communication in the Presence of Noise. Comparison with Hartley’s law:   b−a CH = 2B log2 (M) = 2B log2 bit. ∆ The interval limits a,b here refer to the unquantized signal With α = a + ∆/2 and β = b − ∆/2 as minimum and maximum quantized signal amplitude, respectively, we obtain    2    β−α+∆ β−α (β − α)2 β−α CH = 2B log2 = B log2 1+ = B log2 1+ +2. (1) ∆ ∆ ∆2 ∆ Chapter 1: Physical layer — Transmission channel 1-32 Channel capacity Theorem of Shannon and Hartley On a channel of bandwidth B with additive white noise with noise power PN and signal power PS , the upper bound for the achievable data rate is   PS CS = B log2 1+ bit. PN Derivation of the theorem: see Shannon’s 1949 publication Communication in the Presence of Noise. Comparison with Hartley’s law:   b−a CH = 2B log2 (M) = 2B log2 bit. ∆ The interval limits a,b here refer to the unquantized signal With α = a + ∆/2 and β = b − ∆/2 as minimum and maximum quantized signal amplitude, respectively, we obtain    2    β−α+∆ β−α (β − α)2 β−α CH = 2B log2 = B log2 1+ = B log2 1+ +2. (1) ∆ ∆ ∆2 ∆ Just as with CS , we get a logarithm of 1 + SNR, where this time the SNR is a quantization noise: CS considers only additive noise of the channel but no quantization erros. CH considers only signal stages and thus noise due to quantization but no channel effects. The missing mixed term in (1) compared to CS is related to the assumption of independence between signal and noise (E[x η ] = E[x]E[η ]). The quantization error is of course not independent of the input signal – for this reason (1) cannot be put into the same form as CS without approximation. Chapter 1: Physical layer — Transmission channel 1-32 Channel capacity Summary The channel capacity C is limited by two factors: The number M of distinguishable symbols Even a noise-free channel is of no use if we can only use two symbols. Signal-to-Noise Ratio (SNR) If the signal-to-noise ratio SNR is too low, the distance ∆ between the signal stages may have to be increased and thus the number of distinguishable symbols reduced to ensure reliable discrimination. The channel capacity C is thus limited by the following upper bound: C < min{CH ,CS } = min {2B log2 (M), B log2 (1 + SNR)} bit. Remarks: This is just a model – with highly simplifying assumptions. How to construct a channel code with just the right amount of redundancy so that C is maximized is an open problem in information theory. (← challenge!) We are talking here about data rates in the information-theoretical sense, i. e., the data to be transmitted is available without redundancy. This is never guaranteed in real systems Payloads are not necessarily (and never optimally) compressed before transmission In addition to the payloads, control information (headers) is required (→ more on that later). ⇒ The net data rate that can actually be achieved is below the information-theoretic barrier. Chapter 1: Physical layer — Transmission channel 1-33 Chapter 1: Physical layer Signals, information, and their meaning A mathematical representation of signals Sampling, reconstruction, and quantization Transmission channel Message transmission Source coding Channel coding Line coding Modulation Transmission media Literature and references Chapter 1: Physical layer 1-34 Message transmission Digital data Codewords Channel words Baseband impulses Source Channel Line Modulation coding coding coding Channel Source Channel Detection Demodulation decoding decoding Layer 6/1 Layer 1 Chapter 1: Physical layer — Message transmission 1-35 Source coding Digital data Codewords Channel words Baseband impulses Source Channel Line Modulation coding coding coding Channel Source Channel Detection Demodulation decoding decoding Layer 6/1 Layer 1 Chapter 1: Physical layer — Message transmission 1-36 Source coding Source coding The goal of source coding is to remove (unstructured) redundancy from the data to be transmitted by mapping bit sequences to code words. This corresponds to lossless data compression. Source encoding can occur in different layers of the ISO/OSI model: Data compression can take place on the presentation layer (layer 6) Data may already be in compressed form (lossless compressed file formats, e. g. ZIP, PNG). In mobile communications (digital voice transmission), the source coding may happen even at layer 1. In local area networks such as Ethernet and WLAN there is commonly no explicit source coding Examples: Huffman code Lempel-Ziv / Lempel-Ziv-Welch (LZW) Run-Length Enconding (RLE) → In Chapter 5 we will go into the Huffman code, which is also covered by the lecture Theory of Computation and Information Theory. Chapter 1: Physical layer — Message transmission 1-37 Channel coding Digital data Codewords Channel words Baseband impulses Source Channel Line Modulation coding coding coding Channel Source Channel Detection Demodulation decoding decoding Layer 6/1 Layer 1 Chapter 1: Physical layer — Message transmission 1-38 Channel coding No feasible transmission channel is perfect. One measure of this is the bit error probability pe : Characteristic for Ethernet over copper cable: pe ≈ 10−8 Characteristic for WLAN: pe ≈ 10−6 or more Characteristic for unsecured long range radio transmission: pe ≈ 10−4 or more Mind game: Assume an unsecured radio transmission with bit error probability pe = 10−4 , and let bit errors be independently and uniformly distributed Assume a packet length of L = 1500 B = 12 000 bit Pr [„no bit error in the packet“] = (1 − 10−4 )12000 ≈ 30 % ⇒ 70 % of the transmitted packets would contain at least one bit error. 3 Note that error detection and error correction are different goals. Not every error that is detected can also be corrected. Chapter 1: Physical layer — Message transmission 1-39 Channel coding No feasible transmission channel is perfect. One measure of this is the bit error probability pe : Characteristic for Ethernet over copper cable: pe ≈ 10−8 Characteristic for WLAN: pe ≈ 10−6 or more Characteristic for unsecured long range radio transmission: pe ≈ 10−4 or more Mind game: Assume an unsecured radio transmission with bit error probability pe = 10−4 , and let bit errors be independently and uniformly distributed Assume a packet length of L = 1500 B = 12 000 bit Pr [„no bit error in the packet“] = (1 − 10−4 )12000 ≈ 30 % ⇒ 70 % of the transmitted packets would contain at least one bit error. Channel coding The aim of channel coding is to add structured redundancy to the data to be transmitted so that the largest possible number of bit errors can be detected and corrected.3 3 Note that error detection and error correction are different goals. Not every error that is detected can also be corrected. Chapter 1: Physical layer — Message transmission 1-39 Channel codin