From 9f618c793a76e4199d69eca5ef802fdb7492ffdf Mon Sep 17 00:00:00 2001 From: Philipp Le Date: Fri, 10 Jun 2022 22:34:03 +0200 Subject: Add Exercise 08 --- exercise08/exercise08.tex | 423 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 423 insertions(+) create mode 100644 exercise08/exercise08.tex (limited to 'exercise08') diff --git a/exercise08/exercise08.tex b/exercise08/exercise08.tex new file mode 100644 index 0000000..b8259b2 --- /dev/null +++ b/exercise08/exercise08.tex @@ -0,0 +1,423 @@ +% SPDX-License-Identifier: CC-BY-SA-4.0 +% +% Copyright (c) 2022 Philipp Le +% +% Except where otherwise noted, this work is licensed under a +% Creative Commons Attribution-ShareAlike 4.0 License. +% +% Please find the full copy of the licence at: +% https://creativecommons.org/licenses/by-sa/4.0/legalcode + +\phantomsection +\addcontentsline{toc}{section}{Exercise 8} +\section*{Exercise 8} + + +% Information Content +% Shannon Entropy +% Source Efficiency + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{question}[subtitle={Information}] + A discrete memoryless source has the source alphabet with the probabilities of the symbols: + \begin{table}[H] + \centering + \begin{tabular}{|l|l|l|l|l|} + \hline + Symbol & $s_1$ & $s_2$ & $s_3$ & $s_4$ \\ + \hline + Probability & $0.5$ & $0.25$ & $0.125$ & $0.125$ \\ + \hline + \end{tabular} + \end{table} + + \begin{tasks} + \task + Determine the information content of each symbol! + + \task + Determine the Shannon entropy of the source! + + \task + How much is the source efficiency? + \end{tasks} +\end{question} + +\begin{solution} + \begin{tasks} + \task + The information content is in general: + \begin{equation*} + \mathrm{I}(s_i) = \log_2 \left(\frac{1}{p_i}\right) + \end{equation*} + + For the given symbols, their information content is: + \begin{table}[H] + \centering + \begin{tabular}{|l|l|l|l|l|} + \hline + Symbol & $s_1$ & $s_2$ & $s_3$ & $s_4$ \\ + \hline + Probability & $0.5$ & $0.25$ & $0.125$ & $0.125$ \\ + \hline + Information Content & $1$ & $2$ & $3$ & $3$ \\ + \hline + \end{tabular} + \end{table} + + Note: The information content is a property of the symbol! + + \task + The Shannon entropy is in general: + \begin{equation*} + \begin{split} + \mathrm{H}(X) &= - \sum\limits_{i=1}^{M} p_i \log_2 \left(p_i\right) \\ + &= \sum\limits_{i=1}^{M} p_i \cdot \mathrm{I}(s_i) + \end{split} + \end{equation*} + + For this task: + \begin{equation*} + \begin{split} + \mathrm{H}(X) &= \left(0.5 \cdot 1\right) + \left(0.25 \cdot 2\right) + \left(0.125 \cdot 3\right) + \left(0.125 \cdot 3\right) \\ + &= 0.5 + 0.5 + 0.375 + 0.375 \\ + &= 1.75 + \end{split} + \end{equation*} + + Note: The Shannon entropy is a property of the source! + + \task + We need the decision quantity: + \begin{equation*} + \mathrm{D}(X) = \log_2 \left(M\right) = 2 + \end{equation*} + with $M = 4$ which is the number of symbols in the alphabet. + + The source efficiency is: + \begin{equation*} + \eta_X = \frac{\mathrm{H}(X)}{\mathrm{D}(X)} = \frac{1.75}{2} = 0.875 + \end{equation*} + \end{tasks} +\end{solution} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{question}[subtitle={Source Coding}] + A input source alphabet has the symbols $s_1 = (000)_2$, $s_2 = (001)_2$, $s_3 = (010)_2$, $s_4 = (011)_2$, $s_5 = (100)_2$, $s_6 = (101)_2$, $s_7 = (110)_2$ and $s_8 = (111)_2$ with the following probabilities: + \begin{table}[H] + \centering + \begin{tabular}{|l|l|l|l|l|l|l|l|l|} + \hline + Symbol & $s_1$ & $s_2$ & $s_3$ & $s_4$ & $s_5$ & $s_6$ & $s_7$ & $s_8$ \\ + \hline + Sequence & $(000)_2$ & $(001)_2$ & $(010)_2$ & $(011)_2$ & $(100)_2$ & $(101)_2$ & $(110)_2$ & $(111)_2$ \\ + \hline + Probability & $0.4$ & $0.1$ & $0.05$ & $0.05$ & $0.15$ & $0.025$ & $0.135$ & $0.09$ \\ + \hline + \end{tabular} + \end{table} + + \begin{tasks} + \task + Define a source coding using the Shannon-Fano algorithm. + + \task + Encode the message $\left(000001101110\right)_2$! + + \task + Decode the message $\left(01100010100\right)_2$! + \end{tasks} +\end{question} + +\begin{solution} + \begin{tasks} + \task + We subsequently divide the symbols into portions of equal probability until each portion only has one symbol: + \begin{enumerate} + \item + Division of all symbols into: $S_{0} = \left\{s_1, s_2\right\}$ and $S_{1} = \left\{s_3, s_4, s_5, s_6, s_7, s_8\right\}$ with $P\left(S_{0}\right) = 0.5$ and $P\left(S_{1}\right) = 0.5$ + \item + Division of $S_{0}$ into: $S_{00} = \left\{s_1\right\}$ and $S_{01} = \left\{s_2\right\}$ with $P\left(S_{00}\right) = 0.4$ and $P\left(S_{01}\right) = 0.1$ (no better balancing possible; all portions contain only one element) + \item + Division of $S_{1}$ into: $S_{10} = \left\{s_3, s_4, s_5\right\}$ and $S_{11} = \left\{s_6, s_7, s_8\right\}$ with $P\left(S_{10}\right) = 0.25$ and $P\left(S_{11}\right) = 0.25$ + \item + Division of $S_{10}$ into: $S_{100} = \left\{s_3, s_4\right\}$ and $S_{101} = \left\{s_5\right\}$ with $P\left(S_{100}\right) = 0.1$ and $P\left(S_{101}\right) = 0.15$ + \item + Division of $S_{11}$ into: $S_{110} = \left\{s_6, s_8\right\}$ and $S_{111} = \left\{s_7\right\}$ with $P\left(S_{110}\right) = 0.115$ and $P\left(S_{111}\right) = 0.135$ + \item + Division of $S_{100}$ into: $S_{1000} = \left\{s_3\right\}$ and $S_{1001} = \left\{s_4\right\}$ with $P\left(S_{1000}\right) = 0.05$ and $P\left(S_{1001}\right) = 0.05$ (all portions contain only one element) + \item + Division of $S_{110}$ into: $S_{1100} = \left\{s_6\right\}$ and $S_{1101} = \left\{s_8\right\}$ with $P\left(S_{1100}\right) = 0.025$ and $P\left(S_{1101}\right) = 0.9$ (no better balancing possible; all portions contain only one element) + \end{enumerate} + + The encoding is now: + \begin{table}[H] + \centering + \begin{tabular}{|l|l|l|l|} + \hline + Symbol & Probability & Portion & Codeword \\ + \hline + \hline + $s_1 = (000)_2$ & $0.4$ & $S_{00}$ & $(00)_2$ \\ + \hline + $s_2 = (001)_2$ & $0.1$ & $S_{01}$ & $(01)_2$ \\ + \hline + $s_3 = (010)_2$ & $0.05$ & $S_{1000}$ & $(1000)_2$ \\ + \hline + $s_4 = (011)_2$ & $0.05$ & $S_{1001}$ & $(1001)_2$ \\ + \hline + $s_5 = (100)_2$ & $0.15$ & $S_{101}$ & $(101)_2$ \\ + \hline + $s_6 = (101)_2$ & $0.025$ & $S_{1100}$ & $(1100)_2$ \\ + \hline + $s_7 = (110)_2$ & $0.135$ & $S_{111}$ & $(111)_2$ \\ + \hline + $s_8 = (111)_2$ & $0.09$ & $S_{1101}$ & $(1101)_2$ \\ + \hline + \end{tabular} + \end{table} + Here, you see that a more probable symbol is encoded with less bits than a less probable symbol. We are close to an optimal encoding of the symbols. + + \task + Separate the message into symbols: + \begin{equation*} + \left(000001101110\right)_2 = \left[\left(000\right)_2, \left(001\right)_2, \left(101\right)_2, \left(110\right)_2\right] + \end{equation*} + + Encode the symbols using the table: + \begin{equation*} + \left[\left(00\right)_2, \left(01\right)_2, \left(1100\right)_2, \left(111\right)_2\right] = \left(00011100111\right)_2 + \end{equation*} + + We have reduced the number of bits from 12 to 11. + + Even if this seems to be less. But this scales with the message length. For example, reducing a file size from \SI{12}{GiB} to \SI{11}{GiB} is quite a lot. + + \task + Split the message $\left(011000101\right)_2$ into the codewords: + \begin{equation*} + \left(01100010100\right)_2 = \left[\left(01\right)_2, \left(1000\right)_2, \left(101\right)_2, \left(00\right)_2\right] + \end{equation*} + + Do a reverse lookup in out encoding table: + \begin{equation*} + \left[\left(001\right)_2, \left(010\right)_2, \left(100\right)_2, \left(000\right)_2\right] = \left(001010100000\right)_2 + \end{equation*} + \end{tasks} +\end{solution} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{question}[subtitle={Bit Errors}] + We consider the transmission of binary symbols. The transmitter transmits symbols from the alphabet $X = \left\{0, 1\right\}$. The receiver decodes the received signal to the symbol alphabet $Y = \left\{0, 1\right\}$. + + If there is no noise ($\mathrm{SNR} = \infty$), there are no bit errors. The joint probability matrix for the received symbols is: + \begin{equation*} + \mat{P}_{Y/X,\SI{0}{\percent}} = \left[\begin{matrix} + 1 & 0 \\ + 0 & 1 + \end{matrix}\right] + \end{equation*} + + Under a noisy transmission, there is a probability of bit errors. The bit error rate (BER) is $\SI{10}{\percent}$. The joint probability matrix for the received symbols is: + \begin{equation*} + \mat{P}_{Y/X,\SI{10}{\percent}} = \left[\begin{matrix} + 0.9 & 0.1 \\ + 0.1 & 0.9 + \end{matrix}\right] + \end{equation*} + + \begin{tasks} + \task + The symbols sequence $\left[1, 0, 1, 0\right]$ is transmitted through the \textbf{noise-free} channel. How will the received symbol sequence look like? + + \task + The receiver receives the symbol sequence $\left[1, 0, 1, 0, 1, 1, 1, 0, 0, 1\right]$ from the \textbf{noisy} channel. In average, how many bits of this sequence are correct? What countermeasures can be taken? + \end{tasks} +\end{question} + +\begin{solution} + \begin{tasks} + \task + There are no bit errors. So the receiver will always decode $\left[1, 0, 1, 0\right]$. + + Note that, this will never be observed in reality where noise is always present. This is just a theoretical consideration. + + \task + We have a bit error rate of $\SI{10}{\percent}$, meaning every tenth received bit is wrong. For the received sequence of 10 symbols, only \textbf{9 symbols} are correct in average. + + However, we cannot definitively say which bits are correct and which are wrong. We can only determine the probabilities. So we need error detection and error correction methods (channel coding). + + Every transmission channel is noisy. So there will always be a non-zero probability of observing bit errors. Generally, the better the signal to noise ratio (SNR), the lower the bit error rate (BER). + \end{tasks} +\end{solution} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{question}[subtitle={Hamming Distance}] + Determine the Hamming distance of the following codeword pairs! + + \begin{tasks} + \task + $\vec{v}_1 = \left[1, 0, 1\right]$ and $\vec{v}_2 = \left[1, 1, 1\right]$ + + \task + $\vec{v}_1 = \left[1, 1\right]$ and $\vec{v}_2 = \left[1, 1\right]$ + + \task + $\vec{v}_1 = \left[1, 0, 0, 0, 0\right]$ and $\vec{v}_2 = \left[0, 1, 1, 0, 0\right]$ + + \task + $\vec{v}_1 = \left[1, 0\right]$ and $\vec{v}_2 = \left[0, 0, 0, 1\right]$ + \end{tasks} +\end{question} + +\begin{solution} + \begin{tasks} + \task + $\mathrm{d}\left(\vec{v}_1, \vec{v}_2\right) = 1$ + + \task + $\mathrm{d}\left(\vec{v}_1, \vec{v}_2\right) = 0$ + + The codewords are equal. + + \task + $\mathrm{d}\left(\vec{v}_1, \vec{v}_2\right) = 3$ + + \task + No Hamming distance. The codewords are of different length and not comparable. + \end{tasks} +\end{solution} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{question}[subtitle={Channel Coding}] + A linear block code with the generator matrix $\mat{G}$ is given. + \begin{equation*} + \mat{G} = \left[\begin{matrix} + 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ + 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ + 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ + 0 & 0 & 0 & 1 & 1 & 1 & 1 + \end{matrix}\right] + \end{equation*} + + \begin{tasks} + \task + How many bits are in one information block? \textit{(Hint: Information, not codeword length)} + \task + How many bit errors can be detected and how many can be corrected in one message block? + \task + Encode the message $\vec{m} = \left[1, 0, 0, 1\right]$! + \task + Is the code systematic? Explain briefly the characteristic of systematic codes! + \task + Construct the parity check matrix! + \task + Is the word $\vec{x} = \left[1, 0, 1, 0, 1, 0, 1\right]$ a valid codeword? What is the message $\vec{m}$? + \end{tasks} +\end{question} + +\begin{solution} + \begin{tasks} + \task + It is a $(7,4)$ code. One information block has $k = 4$ bits. + + \task + \begin{itemize} + \item It is a $(7,4)$ code. $n = 7$, $k = 4$. + \item Minimum hamming distance is $d_{min} = n - k + 1 = 4$ + \item Detectable errors: $d_{min} - 1 = 3$ + \item Correctable errors: $\frac{d_{min}}{2} - 1 = 1$ + \end{itemize} + + \task + \begin{equation*} + \vec{x} = \left[1, 0, 0, 1\right] \cdot \left[\begin{matrix} + 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ + 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ + 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ + 0 & 0 & 0 & 1 & 1 & 1 & 1 + \end{matrix}\right] = \left[1, 0, 0, 1, 1, 0, 0\right] + \end{equation*} + + \task + \begin{itemize} + \item Systematic codes resemble the original message unchanged. Only parity bits are added. + \item So a receiver can read the data without the need for decoding, provided that no bit errors are present. + \item This code is systematic. + \end{itemize} + + \task + The parity matrix is + \begin{equation*} + \mat{P} = \left[\begin{matrix} + 0 & 1 & 1 \\ + 1 & 0 & 1 \\ + 1 & 1 & 0 \\ + 1 & 1 & 1 + \end{matrix}\right] + \end{equation*} + Its transpose is + \begin{equation*} + \mat{P}^{\mathrm{T}} = \left[\begin{matrix} + 0 & 1 & 1 & 1 \\ + 1 & 0 & 1 & 1 \\ + 1 & 1 & 0 & 1 + \end{matrix}\right] + \end{equation*} + + The identity matrix is + \begin{equation*} + \mat{I} = \left[\begin{matrix} + 1 & 0 & 0 \\ + 0 & 1 & 0 \\ + 0 & 0 & 1 + \end{matrix}\right] + \end{equation*} + The identity matrix is now $3 \times 3$. Otherwise, it cannot be concatenated to the transposed parity matrix. + + The parity check matrix is + \begin{equation*} + \mat{H} = \left[-\mat{P}^{\mathrm{T}}, \mat{\mathrm{I}}\right] = \left[\begin{matrix} + 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ + 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ + 1 & 1 & 0 & 1 & 0 & 0 & 1 + \end{matrix}\right] + \end{equation*} + Every operation is modulo 2. That is, $(1) \mod 2 \equiv (-1) \mod 2$. So $-1$ (from the negation $-\mat{P}^{\mathrm{T}}$) is equivalent to $1$. + + \task + Calculate the syndrome vector: + \begin{equation*} + \vec{s} = \mat{H} \cdot \vec{x} = \left[\begin{matrix} + 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ + 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ + 1 & 1 & 0 & 1 & 0 & 0 & 1 + \end{matrix}\right] \left[1, 0, 1, 0, 1, 0, 1\right]^{\mathrm{T}} = \left[0, 0, 0\right] = \mat{\mathrm{0}} + \end{equation*} + The codeword is valid because the syndrome vector is zero. + + The message can directly be read from the codeword because: + \begin{itemize} + \item The codeword is valid. No error correction is required. + \item The code is systematic. The message is encoded in the first four bits. + \end{itemize} + The message is $\vec{s} = \left[1, 0, 1, 0\right]$. + \end{tasks} +\end{solution} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{question}[subtitle={DS-CDMA}] +%\begin{tasks} +% \task +% +%\end{tasks} +%\end{question} +% +%\begin{solution} +%\begin{tasks} +% \task +% +%\end{tasks} +%\end{solution} + -- cgit v1.1