\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}
				Работу выполнил студент группы 2125\\
				\emph{Халанский Дмитрий Владимирович}
\end{flushright}
\vspace{\stretch{4}}
\begin{center}
				2015
\end{center}
\newpage
% ======================== КОНЕЦ ТИТУЛЬНОГО ЛИСТА ============================

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

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

\section{Условие}
\begin{center}
16 вариант
\end{center}
\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.2$ & $0.1$ & $0.2$ & $0.3$ & $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) = - (0.2 \text{lb} 0.2 + 0.2 \text{lb} 0.2 + 0.1 \text{lb} 0.1 + 0.2 \text{lb} 0.2 + 0.3 \text{lb} 0.3) \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_5$ & 0.3 & 00 & $2\tau$ \\
      $x_1$ & 0.2 & 01 & $2\tau$ \\
      $x_2$ & 0.2 & 10 & $2\tau$ \\
      $x_4$ & 0.2 & 110 & $3\tau$ \\
      $x_3$ & 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_5 x_5$ & $0.09$ & 0000    & $4 \tau$ \\
      $x_1 x_5$ & $0.06$ & 0001    & $4 \tau$ \\
      $x_5 x_1$ & $0.06$ & 0010    & $4 \tau$ \\
      $x_2 x_5$ & $0.06$ & 0011    & $4 \tau$ \\
      $x_5 x_2$ & $0.06$ & 0100    & $4 \tau$ \\
      $x_4 x_5$ & $0.06$ & 0101    & $4 \tau$ \\
      $x_5 x_4$ & $0.06$ & 0110    & $4 \tau$ \\
      $x_1 x_1$ & $0.04$ & 0111    & $4 \tau$ \\
      $x_1 x_2$ & $0.04$ & 1000    & $4 \tau$ \\
      $x_2 x_1$ & $0.04$ & 10010   & $5 \tau$ \\
      $x_1 x_4$ & $0.04$ & 10011   & $5 \tau$ \\
      $x_4 x_1$ & $0.04$ & 1010    & $4 \tau$ \\
      $x_2 x_2$ & $0.04$ & 10110   & $5 \tau$ \\
      $x_4 x_2$ & $0.04$ & 10111   & $5 \tau$ \\
      $x_2 x_4$ & $0.04$ & 11000   & $5 \tau$ \\
      $x_4 x_4$ & $0.04$ & 11001   & $5 \tau$ \\
      $x_5 x_3$ & $0.03$ & 11010   & $5 \tau$ \\
      $x_3 x_5$ & $0.03$ & 11011   & $5 \tau$ \\
      $x_1 x_3$ & $0.02$ & 11100   & $5 \tau$ \\
      $x_3 x_1$ & $0.02$ & 111010  & $6 \tau$ \\
      $x_2 x_3$ & $0.02$ & 111011  & $6 \tau$ \\
      $x_3 x_2$ & $0.02$ & 111100  & $6 \tau$ \\
      $x_4 x_3$ & $0.02$ & 111101  & $6 \tau$ \\
      $x_3 x_4$ & $0.02$ & 111110  & $6 \tau$ \\
      $x_3 x_3$ & $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_3$         & 0.1 &     &     &     &   & 000 & $3 \tau$ \\
      $x_2$         & 0.2 &     &     &     &   & 001 & $3 \tau$ \\
      $x_2 x_3$     &     & 0.3 &     &     &   & & \\
      $x_4$         & 0.2 &     &     &     &   & 10 & $2 \tau$ \\
      $x_1$         & 0.2 &     &     &     &   & 11 & $2 \tau$ \\
      $x_1 x_4$     &     &     & 0.4 &     &   & & \\
      $x_5$         & 0.3 &     &     &     &   & 01 & $2 \tau$ \\
      $x_5 x_2 x_3$ &     &     &     & 0.6 &   & & \\
      $X$           &     &     &     &     & 1 & & \\
      \hline
    \end{tabular}

    $\tau* = \sum\limits_{i = 1}^5 p(x_i) \tau_i = 0.1 \cdot 3 \tau + 0.2 \cdot 3 \tau + 0.2 \cdot 2 \tau + 0.2 \cdot 2 \tau + 0.3 \cdot 2 \tau = 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_3 x_3$ & $0.01$ & 111001 & $6 \tau$ \\
      $x_4 x_3$ & $0.02$ & 11101  & $5 \tau$ \\
      $x_2 x_3$ & $0.02$ & 010001 & $6 \tau$ \\
      $x_1 x_3$ & $0.02$ & 111000 & $6 \tau$ \\
      $x_3 x_4$ & $0.02$ & 000111 & $6 \tau$ \\
      $x_3 x_1$ & $0.02$ & 000110 & $6 \tau$ \\
      $x_3 x_2$ & $0.02$ & 010000 & $6 \tau$ \\
      $x_3 x_5$ & $0.03$ & 10110  & $5 \tau$ \\
      $x_5 x_3$ & $0.03$ & 10111  & $5 \tau$ \\
      $x_2 x_1$ & $0.04$ & 00000  & $5 \tau$ \\
      $x_2 x_4$ & $0.04$ & 01001  & $5 \tau$ \\
      $x_1 x_1$ & $0.04$ & 00111  & $5 \tau$ \\
      $x_2 x_2$ & $0.04$ & 00001  & $5 \tau$ \\
      $x_1 x_4$ & $0.04$ & 00010  & $5 \tau$ \\
      $x_4 x_1$ & $0.04$ & 00100  & $5 \tau$ \\
      $x_1 x_2$ & $0.04$ & 00110  & $5 \tau$ \\
      $x_4 x_2$ & $0.04$ & 00101  & $5 \tau$ \\
      $x_4 x_4$ & $0.04$ & 1111   & $4 \tau$ \\
      $x_5 x_1$ & $0.06$ & 0110   & $4 \tau$ \\
      $x_4 x_5$ & $0.06$ & 1001   & $4 \tau$ \\
      $x_2 x_5$ & $0.06$ & 0101   & $4 \tau$ \\
      $x_1 x_5$ & $0.06$ & 1010   & $4 \tau$ \\
      $x_5 x_4$ & $0.06$ & 0111   & $4 \tau$ \\
      $x_5 x_2$ & $0.06$ & 1000   & $4 \tau$ \\
      $x_5 x_5$ & $0.09$ & 110    & $3 \tau$ \\
      \hline
    \end{longtable}

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

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

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

% ============================ КОНЕЦ ОТЧЁТА ==================================

\end{document}
