\documentclass[12pt, a4paper] {ncc}
\usepackage[utf8] {inputenc}
\usepackage[T2A]{fontenc}
\usepackage[english, russian] {babel}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{listings,a4wide,longtable,amsmath,amsfonts,graphicx,tikz}

\begin{document}
\pagestyle{empty}

% ============================ ТИТУЛЬНЫЙ ЛИСТ ================================
\begin{center}
	Университет ИТМО\\
\end{center}
\vspace{\stretch{2}}
\begin{center}
		{\bfОтчёт по лабораторной работе №2 по дисциплине}\\
			"Теория информации"\\
\end{center}
\vspace{\stretch{3}}
\begin{flushright}
				Выполнила:\\
				Куклина М.Д., P3201\\
				Преподаватель: \\
				Тропченко А.А.\\
\end{flushright}
\vspace{\stretch{4}}
\begin{center}
				Санкт-Петербург, 2016
\end{center}
\newpage
% ======================== КОНЕЦ ТИТУЛЬНОГО ЛИСТА ============================

% ================================ ОТЧЁТ =====================================

\section{Цель}
Овладение навыками статического кодирования по методам Шеннона-Фано и Хаффмана.

\section{Постановка задачи}
Сообщение X с символами x1, x2, x3, x4, x5 передается по дискретному двоичному каналу. Полоса пропускания канала обеспечивает возможность передачи двоичных символов длительность $\tau $ . Требуется выбрать наилучший способ кодирования.\\
Вариант 4 \\
\begin{tabular}{|c|c|c|c|c|c|}
  \hline
  $p(x_1)$ & $p(x_2)$ & $p(x_3)$ & $p(x_4)$ & $p(x_5)$ & $\tau,\;c$ \\
  \hline
  $0.2$ & $0.1$ & $0.3$ & $0.2$ & $0.2$ & $10^{-4}$ \\
  \hline
\end{tabular}

\section{Кодирование}
\begin{description}
  \item[Пропускная способность]~\\
    $c = \dfrac{1}{\tau} = 10^4 \left(c^{-1}\right)$
  \item[Кодирование равномерным двоичным кодом]~\\ \\
    \begin{tabular}{|c|c|c|c|c|}
      \hline
      $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ \\
      \hline
      000 & 001 & 010 & 011 & 100 \\
      \hline
    \end{tabular}

    $\tau* = 3\tau = 3 \cdot 10^{-4} \left(c\right)$

    $V = \dfrac{1}{\tau*} = \dfrac{1}{3 \cdot 10^{-4}} \approx 3.3 \cdot 10^3 \left(\dfrac{\text{элем}}{{c}}\right)$

    $H = - \sum\limits_{i = 1}^5 p(x_i) \text{lb} p(x_i) \approx 2.246 \left(\dfrac{\text{бит}}{\text{элем}}\right)$
  
	\item[Кодирование методом Шеннона-Фано без укрупнения]~\\ \\
    \begin{tabular}{|c|c|l|c|c|}
      \hline
      $x_i$ & $p(x_i)$ & \bf комбинации & $\tau_i,\;c$ \\
      \hline
      $x_3$ & 0.3 & 00 & $2\tau$ \\  \hline
      $x_1$ & 0.2 & 01 & $2\tau$ \\  \hline
      $x_4$ & 0.2 & 10 & $2\tau$ \\  \hline
      $x_5$ & 0.2 & 110 & $3\tau$ \\  \hline
      $x_2$ & 0.1 & 111 & $3\tau$ \\ 
      \hline
    \end{tabular}

    $\tau* = \sum\limits_{i = 1}^5 p(x_i) \tau_i = 0.3 \cdot 2 \tau + 0.2 \cdot 2 \tau + 0.2 \cdot 2 \tau + 0.2 \cdot 3 \tau + 0.1 \cdot 3 \tau = 2.3 \tau$

    $V = \dfrac{1}{\tau*} = \dfrac{1}{2.3 \cdot 10^{-4}} \approx 4.35 \cdot 10^3 \left(\dfrac{\text{элем}}{{c}}\right)$

    $R = V \cdot H = 4.35 \cdot 10^3 \cdot 2.246 \approx 0.98 \cdot 10^4 \left(\dfrac{\text{бит}}{\text{элем}}\right)$

  \item[Кодирование методом Шеннона-Фано с укрупнениями]~\\ \\
    \begin{tabular}{|c|c|l|c|c|}
      \hline
      $x_i x_j$ & $p(x_i) \cdot p(x_j)$ & \bf комбинации & $\tau_i,\;c$ \\
      \hline
      $x_3 x_3$ & $0.09$ & 0000    & $4 \tau$ \\ \hline
      $x_1 x_3$ & $0.06$ & 0001    & $4 \tau$ \\ \hline
      $x_3 x_1$ & $0.06$ & 0010    & $4 \tau$ \\ \hline
      $x_4 x_3$ & $0.06$ & 0011    & $4 \tau$ \\ \hline
      $x_3 x_4$ & $0.06$ & 0100    & $4 \tau$ \\ \hline
      $x_5 x_3$ & $0.06$ & 0101    & $4 \tau$ \\ \hline
      $x_3 x_5$ & $0.06$ & 0110    & $4 \tau$ \\ \hline
			$x_1 x_1$ & $0.04$ & 0111    & $4 \tau$ \\ \hline
      $x_1 x_4$ & $0.04$ & 1000    & $4 \tau$ \\ \hline
      $x_4 x_1$ & $0.04$ & 10010   & $5 \tau$ \\ \hline
      $x_1 x_5$ & $0.04$ & 10011   & $5 \tau$ \\ \hline
      $x_5 x_1$ & $0.04$ & 1010    & $4 \tau$ \\ \hline
      $x_4 x_4$ & $0.04$ & 10110   & $5 \tau$ \\ \hline
      $x_5 x_4$ & $0.04$ & 10111   & $5 \tau$ \\ \hline
      $x_4 x_5$ & $0.04$ & 11000   & $5 \tau$ \\ \hline
      $x_5 x_5$ & $0.04$ & 11001   & $5 \tau$ \\ \hline
			$x_3 x_2$ & $0.03$ & 11010   & $5 \tau$ \\ \hline
      $x_2 x_3$ & $0.03$ & 11011   & $5 \tau$ \\ \hline
			$x_1 x_2$ & $0.02$ & 11100   & $5 \tau$ \\ \hline
      $x_2 x_1$ & $0.02$ & 111010  & $6 \tau$ \\ \hline
      $x_4 x_3$ & $0.02$ & 111011  & $6 \tau$ \\ \hline
      $x_2 x_4$ & $0.02$ & 111100  & $6 \tau$ \\ \hline
      $x_5 x_2$ & $0.02$ & 111101  & $6 \tau$ \\ \hline
      $x_2 x_5$ & $0.02$ & 111110  & $6 \tau$ \\ \hline
      $x_2 x_2$ & $0.01$ & 111111  & $6 \tau$ \\ 
      \hline
    \end{tabular}

    $\tau* = \frac{1}{2} \sum\limits_{i = 1}^n p(x_i) \tau_i = 2.27 \tau \left(c\right)$

    $V = \dfrac{1}{\tau*} = \dfrac{1}{2.27 \cdot 10^{-4}} \approx 4.4 \cdot 10^3 \left(\dfrac{\text{элем}}{{c}}\right)$

    $R = V \cdot H = 4.4 \cdot 10^3 \cdot 2.246 \approx 0.989 \cdot 10^4 \left(\dfrac{\text{бит}}{\text{элем}}\right)$

  \item[Метод Хаффмана без укрупнений]~\\ \\
    \begin{tabular}{|c|c|c|c|c|c|l|c|}
      \hline
      $x_i$ & $p(x_i)$ & 1 & 2 & 3 & 4 & \bf код & $\tau_i,\;c$ \\
      \hline
      $x_2$         & 0.1 &     &     &     &   & 000 & $3 \tau$ \\ \hline
      $x_4$         & 0.2 &     &     &     &   & 001 & $3 \tau$ \\ \hline
      $x_4 x_4$     &     & 0.3 &     &     &   & & \\ \hline
      $x_5$         & 0.2 &     &     &     &   & 10 & $2 \tau$ \\ \hline
      $x_1$         & 0.2 &     &     &     &   & 11 & $2 \tau$ \\ \hline
      $x_1 x_5$     &     &     & 0.4 &     &   & & \\ \hline
      $x_3$         & 0.3 &     &     &     &   & 01 & $2 \tau$ \\ \hline
      $x_3 x_4 x_2$ &     &     &     & 0.6 &   & & \\ \hline
      $X$           &     &     &     &     & 1 & & \\ 
      \hline
    \end{tabular}

    $\tau* = \sum\limits_{i = 1}^5 p(x_i) \tau_i = 2.3 \tau \left(c\right)$

    $V = \dfrac{1}{\tau*} = \dfrac{1}{2.3 \cdot 10^{-4}} \approx 4.35 \cdot 10^3 \left(\dfrac{\text{элем}}{{c}}\right)$

    $R = V \cdot H = 4.35 \cdot 10^3 \cdot 2.246 \approx 0.98 \cdot 10^4 \left(\dfrac{\text{бит}}{\text{элем}}\right)$

  \item[Метод Хаффмана с укрупнениями]~\\
    \begin{longtable}{|c|c|l|c|}
      \hline
      $x_i x_j$ & $p(x_i) \cdot p(x_j)$ & \bf комбинации & $\tau_i,\;c$ \\ \\
      \hline
      $x_2 x_2$ & $0.01$ & 111001 & $6 \tau$ \\ \hline
      $x_5 x_2$ & $0.02$ & 11101  & $5 \tau$ \\ \hline
      $x_4 x_2$ & $0.02$ & 010001 & $6 \tau$ \\ \hline
      $x_1 x_2$ & $0.02$ & 111000 & $6 \tau$ \\ \hline
      $x_2 x_5$ & $0.02$ & 000111 & $6 \tau$ \\ \hline
      $x_2 x_1$ & $0.02$ & 000110 & $6 \tau$ \\ \hline
      $x_2 x_4$ & $0.02$ & 010000 & $6 \tau$ \\ \hline
      $x_2 x_3$ & $0.03$ & 10110  & $5 \tau$ \\ \hline
      $x_3 x_2$ & $0.03$ & 10111  & $5 \tau$ \\ \hline
      $x_4 x_1$ & $0.04$ & 00000  & $5 \tau$ \\ \hline
      $x_4 x_5$ & $0.04$ & 01001  & $5 \tau$ \\ \hline
      $x_1 x_1$ & $0.04$ & 00111  & $5 \tau$ \\ \hline
      $x_4 x_4$ & $0.04$ & 00001  & $5 \tau$ \\ \hline
      $x_1 x_5$ & $0.04$ & 00010  & $5 \tau$ \\ \hline
      $x_5 x_1$ & $0.04$ & 00100  & $5 \tau$ \\ \hline
      $x_1 x_4$ & $0.04$ & 00110  & $5 \tau$ \\ \hline
      $x_5 x_4$ & $0.04$ & 00101  & $5 \tau$ \\ \hline
      $x_5 x_5$ & $0.04$ & 1111   & $4 \tau$ \\ \hline
      $x_3 x_1$ & $0.06$ & 0110   & $4 \tau$ \\ \hline
      $x_5 x_3$ & $0.06$ & 1001   & $4 \tau$ \\ \hline
      $x_4 x_3$ & $0.06$ & 0101   & $4 \tau$ \\ \hline
      $x_1 x_3$ & $0.06$ & 1010   & $4 \tau$ \\ \hline
      $x_3 x_5$ & $0.06$ & 0111   & $4 \tau$ \\ \hline
      $x_3 x_4$ & $0.06$ & 1000   & $4 \tau$ \\ \hline
      $x_3 x_3$ & $0.09$ & 110    & $3 \tau$ \\
      \hline
    \end{longtable}

    $\tau*  = 2.265 \left(c\right)$

    $V = \dfrac{1}{\tau*}  \approx 44.15 \cdot 10^3 \left(\dfrac{\text{элем}}{{c}}\right)$

    $R = V \cdot H  \approx 0.992 \cdot 10^4 \left(\dfrac{\text{бит}}{\text{элем}}\right)$
\end{description}
\section{Декодирование}
Пусть передается сообщение: $x_2 x_1 x_3 x_4 x_5 x_1$. Выполним проверочные операции кодировки декодировки  для вышеперечисленных кодов.
\begin{enumerate}
	\item Кодом Шеннона-Фано\\
		Сообщение: 111010010111001 ->  $x_2 x_1 x_3 x_4 x_5 x_1$
	\item Кодом Шеннона-Фано с укрупнением\\
	Сообщение: 1110001001010 ->  $x_2 x_1 x_3 x_4 x_5 x_1$
	\item Кодом Хаффмана\\
	Сообщение: 000011010011011 ->  $x_2 x_1 x_3 x_4 x_5 x_1$
	\item Кодом Хаффмана с укрупнением\\
	Сообщение: 000110100000100 ->  $x_2 x_1 x_3 x_4 x_5 x_1$
\end{enumerate}
\section{Вывод}
Все исследованные коды обладают свойством однозначности.
Максимальная скорость передачи достигается при кодировании кодом Хаффмана с укрупнением.
Код Шеннона-Фано без укрупнения и код Хаффмана без укрупнения  показали схожий результат.
Как и следовало ожидать самым «медленным» оказался равномерный двоичный, когда кодировании кодом Хаффмана с укрупнением дало самый оптимальный результат.
\end{document}
