\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}
\usepackage{indentfirst,verbatim,pdfpages}

\usetikzlibrary{shapes,arrows}

\begin{document}
\setcounter{figure}{0}
\frenchspacing
\pagestyle{empty}
% ============================ ТИТУЛЬНЫЙ ЛИСТ ================================
\begin{center}
     Национальный исследовательский университет информационных технологий,
                              механики и оптики.\\
                       Кафедра вычислительной техники.\\
                      Методы цифровой обработки сигналов.
\end{center}
\vspace{\stretch{2}}
\begin{center}
                         {\bf Курсовая работы}\\
    Исследование влияния конечной разрядности АЛУ спецпроцессора на точность
           результатов при выполнении линейной фильтрации сигналов\\
                                {\sl 11 вариант}
\end{center}
\vspace{\stretch{3}}
\begin{flushright}
                                          Работу выполнил студент группы P3415\\
                                                         {\it Халанский Дмитрий}
\end{flushright}
\vspace{\stretch{4}}
\begin{center}
                                      2016
\end{center}
\newpage
% ======================== КОНЕЦ ТИТУЛЬНОГО ЛИСТА ============================

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

\section{Задание}

Имеется специализированный процессор для линейной фильтрации сигналов. На вход
ему поступают дискретные сигналы в формате целых чисел разрядности $n_1$. При
фильтрации применяются весовые коэффициенты, имеющие разрядность $n_2$. Все
промежуточные и конечные результаты имеют разрядность $n_3$.

Требуется:

\begin{enumerate}
        \item Написать программу на любом языке программирования, которая
                реализует алгоритм линейной фильтрации, используя внутри числа
                с плавающей точкой;
        \item Написать программу, которая реализует тот же алгоритм, но
                использует целые числа разрядностей $n_i$;
        \item Определить зависимости:
                \begin{enumerate}
                        \item Среднеквадратической погрешности от длины
                                обрабатываемого вектора данных и/или длины ядра
                                преобразования;
                        \item Точности от способа формирования малоразрядного
                                результата: с отсечением младших разрядов, с
                                отсечением и увеличением младшего разряда на
                                единицу, с округлением;
                        \item Среднеквадратического отклонения от длины
                                обрабатываемого вектора для всех трёх способов;
                        \item Среднеквадратического отклонения от длины
                                обрабатываемого вектора при округлении
                                результата с изменением:
                                \begin{itemize}
                                        \item $n_1$ на 2 и 4 бита;
                                        \item $n_2$ на 2 и 4 бита.
                                \end{itemize}
                \end{enumerate}
\end{enumerate}

\subsection{Вариант}

Вычисление апериодической свёртки при $M = 5, N = [10; 40], n_1 = 8, n_2
= 4, n_3 = 12$.

\section{Математические соотношения}

Свёртка~--- алгоритм, при котором на вход поступают две последовательности~---
$a(n)$, $b(m)$, где $n \in [0; N), m \in [0; M)$~--- и на выходе имеется новая
последовательность, представляющая собой произведение элементов $a$ и $b$
такое, что элементы $a$ берутся по возрастающему индексу, а $b$~--- по
убывающему.

Апериодическая свёртка~--- частный случай свёртки, при котором входные
последовательности не зацикливаются, а дополняются нулями.

Определим $A(n), n \in \mathbb{Z}$ как функцию, которая на $n \in [0; N)$ имеет
те же значения, что и $a(n)$, а на остальной области определения~--- $0$.
Аналогично определим $B(m)$ как расширение $b(m)$.

Тогда элемент выходной последовательности высчитывается следующим образом:

$$c(k) = \sum\limits_{i = 0}^k A(i) \cdot B(k-i), k \in [0; N + M - 2]$$

\begin{figure}[h]
        \centering
        \tikzstyle{decision} = [draw, diamond, aspect=2]
        \tikzstyle{block} = [draw, rectangle]
        \begin{tikzpicture}[node distance=4em, auto]
                \node[draw, ellipse] (begin) {Begin};
                \node[block, below of=begin] (init0) {$i \leftarrow 0$};
                \node[decision, below of=init0, node distance=6em] (loop0)
                        {$i < N + M - 1$};
                \node[block, above of=loop0, xshift=12em] (inc0)
                        {$i \leftarrow i + 1$};
                \node[block, below of=loop0, xshift=6em]
                        (init11) {$j \leftarrow 0$};
                \node[block, below of=init11] (init12)
                        {$c_i \leftarrow 0$};
                \node[decision, below of=init12] (loop1)
                        {$j \le i$};
                \node[decision, below of=loop1, node distance=6em] (doadd)
                        {$i < N \land k - i < M$};
                \node[block, below of=doadd, xshift=8em] (add)
                        {$c_i \leftarrow c_i + a_i + b_{k-i}$};
                \node[block, above of=loop1, node distance=2.5em,
                        xshift=-10em] (inc1) {$j \leftarrow j + 1$};
                \node[draw, ellipse, below of=loop0, xshift=-6em]
                        (end) {End};

                \draw[->] (begin) -- (init0);
                \draw[->] (init0) -- (loop0);
                \draw[->] (loop0) -| node{yes} (init11);
                \draw[->] (init11) -- (init12);
                \draw[->] (init12) -- (loop1);
                \draw[->] (loop1) -- node{yes} (doadd);
                \draw[->] (doadd) -| node{yes} (add);
                \draw[->] (doadd) -| node[near start]{no} (inc1);
                \draw[->] (add) -| (inc1);
                \draw[->] (loop1) -| node[near start]{no} (inc0);
                \draw[->] (inc0) -| (loop0);
                \draw[->] (inc1) -| (loop1);
                \draw[->] (loop0) -| node[above left, near start]{no} (end);
        \end{tikzpicture}
        \caption{Блок-схема алгоритма}
\end{figure}

\section{Ход работы}

\subsection{Числа с плавающей точкой}

\lstinputlisting[basicstyle=\scriptsize]{src/fold_f32.rs}

\subsection{Числа с ограниченной разрядностью}

\lstinputlisting[basicstyle=\scriptsize]{src/fold.rs}

\subsection{Зависимости}

\subsubsection{Зависимости СКО от длины вектора}

\begin{figure}[h!]
        \centering
        \includegraphics[page=1]{stdev_u.pdf}
        \caption{Зависимость СКО от длины входного вектора для разных видов
        фильтрации с ядром [-1, -1, 4, -1, -1]}
\end{figure}

Для заданного ядра оказалось, что при любой длине вектора заданной точности
оказывается достаточно. Действительно, положительная и отрицательная компоненты
суммы имеют максимальную разрядность $8 + 3 = 11$ битов. Соответственно, сумма
компонент не может превышать $11$ битов ни в нижнюю, ни в верхнюю сторону, и
один бит отводится на знак.

Погрешность наблюдается лишь при ограничении разрядности входных данных
(максимальное СКО~--- 2) и при ограничении разрядности ядра до двух битов, что
приводит к преобразованию ядра в [0, 0, 4, 0, 0] и, соответственно, к
существенным отклонениям (СКО порядка сотен).

\begin{figure}[h!]
        \centering
        \includegraphics[page=1]{stdev_f.pdf}
        \caption{Зависимость СКО от длины входного вектора для разных видов
        фильтрации с ядром [8, 8, 8, 8, 8]}
\end{figure}

С другой стороны, для ядра [8, 8, 8, 8, 8] картина совсем иная. Действительно,
перемножая числа с разрядностями 8 и 4 бита, имеем число разрядностью 12 битов.
Складывая пять таких чисел, получаем число разрядностью в 16 битов.

Для этого ядра также обнаружено, что округление и обрезание нижних битов не
приводят к потере точности, в отличие от обрезания и увеличения верхних битов
на единицу.

Также по графикам можно установить, что имеется зависимость не от размера
входного вектора, но от отношения длины строба ко всей длине вектора. Это
отношение в рамках опыта менялось периодически.

\section{Выводы}

В результате проделанной работы мы выяснили, что длина входного вектора не
оказывает существенного влияния на погрешность апериодической свёртки,
ограниченной по разрядности. С другой стороны, разрядность ядра крайне важна.

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

\end{document}
