188 lines
7.4 KiB
TeX
188 lines
7.4 KiB
TeX
\section{Theoretical Background}%
|
||
\label{sec:Theoretical Background}
|
||
|
||
|
||
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
||
%\subsection{Motivation}%
|
||
%\label{sub:Motivation}
|
||
|
||
\begin{frame}[t]
|
||
\frametitle{Motivation}
|
||
\begin{itemize}
|
||
\item General ML decoding problem NP-complete \citereference{BMT78}
|
||
\item Iterative message–passing algorithms popular in practice do not guarantee
|
||
optimality when the graph contains cycles \citereference{KTP19}
|
||
\item Standard message-passing algorithms difficult to analyze \citereference{FEL03}
|
||
\end{itemize}
|
||
|
||
\vspace{3.5cm}
|
||
|
||
\addreferences
|
||
{BMT78}{E. Berlekamp; R. McEliece; H. van Tilborg: \emph{On the inherent intractability
|
||
of certain coding problems (Corresp.)}.
|
||
IEEE Transactions on Information Theory 24.3 (May 1978), pp. 384–386.}
|
||
{KTP19}{Banu Kabakulak; Z. Caner Taşkın; Ali Emre Pusane: \emph{Optimization–based
|
||
decoding algorithms for LDPC convolutional codes in communication systems}.
|
||
IISE Transactions 51.10 (2019), pp. 1061–1074.}
|
||
{FEL03}{Jon Feldman: \emph{Decoding error-correcting codes via linear programming}.
|
||
PhD thesis. MIT, 2003.}
|
||
\stopreferences
|
||
\end{frame}
|
||
|
||
|
||
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
||
%\subsection{Presumptions}%
|
||
%\label{sub:Presumptions}
|
||
|
||
\begin{frame}[t]
|
||
\frametitle{Presumptions: Channel \& Modulation}
|
||
|
||
\tikzstyle{mapper} = [rectangle, minimum width=1.5cm, minimum height=0.7cm,
|
||
rounded corners=0.1cm, text centered, draw=black, fill=KITgreen!80]
|
||
\begin{figure}[htpb]
|
||
\centering
|
||
|
||
\begin{tikzpicture}[scale=1, transform shape]
|
||
\node (in) {$\boldsymbol{c}$};
|
||
\node[mapper, right=0.5cm of in] (bpskmap) {Mapper};
|
||
\node[right=1.5cm of bpskmap,
|
||
draw, circle, inner sep=0pt, minimum size=0.5cm] (add) {$+$};
|
||
\node[below=0.5cm of add] (noise) {$\boldsymbol{n}$};
|
||
\node[mapper, right=1.5cm of add] (decoder) {Decoder};
|
||
\node[mapper, right=1.5cm of decoder] (demapper) {Demapper};
|
||
\node[right=0.5cm of demapper] (out) {$\boldsymbol{\hat{c}}$};
|
||
|
||
\node at ($(bpskmap.east)!0.5!(add.west) + (0,0.3cm)$) {$\boldsymbol{x}$};
|
||
\node at ($(add.east)!0.5!(decoder.west) + (0,0.3cm)$) {$\boldsymbol{y}$};
|
||
\node at ($(decoder.east)!0.5!(demapper.west) + (0,0.3cm)$) {$\boldsymbol{\hat{x}}$};
|
||
|
||
\draw[->] (in) -- (bpskmap);
|
||
\draw[->] (bpskmap) -- (add);
|
||
\draw[->] (add) -- (decoder);
|
||
\draw[->] (noise) -- (add);
|
||
\draw[->] (decoder) -- (demapper);
|
||
\draw[->] (demapper) -- (out);
|
||
\end{tikzpicture}
|
||
\end{figure}
|
||
|
||
\begin{itemize}
|
||
\item All simulations are performed with BPSK:
|
||
\begin{align*}
|
||
\boldsymbol{x} = \left( -1 \right)^{\boldsymbol{c}},
|
||
\hspace{5mm} \boldsymbol{c} \in \mathbb{F}_2^n,
|
||
\hspace{2mm} \boldsymbol{x} \in \left\{ -1, 1 \right\}^n
|
||
\end{align*}
|
||
\item The channel model is AWGN:
|
||
\begin{align*}
|
||
\boldsymbol{y} = \boldsymbol{x} + \boldsymbol{n},
|
||
\hspace{5mm}\boldsymbol{n}\sim \mathcal{N}
|
||
\left(0,\frac{1}{2}\left(\frac{k}{n}\frac{E_b}{N_0}\right)^{-1}\right),
|
||
\hspace{2mm} \boldsymbol{y}, \boldsymbol{n} \in \mathbb{R}^n
|
||
\end{align*}
|
||
\item All-zeros assumption:
|
||
\begin{align*}
|
||
\boldsymbol{c} = \boldsymbol{0}
|
||
\end{align*}
|
||
\end{itemize}
|
||
\end{frame}
|
||
|
||
|
||
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
||
%\subsection{Optimization as a Decoding Method}%
|
||
%\label{sub:Optimization as a Decoding Method}
|
||
|
||
\begin{frame}[t]
|
||
\frametitle{Optimization as a Decoding Method}
|
||
|
||
\begin{minipage}[c]{0.6\linewidth}
|
||
\begin{itemize}
|
||
\item Reformulate decoding problem as optimization problem
|
||
\begin{itemize}
|
||
\item Establish objective function
|
||
\item Establish constraints
|
||
\end{itemize}
|
||
\item Use optimization method to solve the new problem
|
||
\end{itemize}
|
||
|
||
\vspace{5mm}
|
||
|
||
\begin{itemize}
|
||
\item Usage of ''$\sim$`` to denote change in domain, e.g.:
|
||
\end{itemize}
|
||
|
||
\vspace*{-2mm}
|
||
\hspace*{-10mm}
|
||
\begin{minipage}[c]{\textwidth}
|
||
\centering
|
||
\begin{align*}
|
||
\boldsymbol{c} \in \left\{ 0, 1 \right\}^n &\rightarrow
|
||
\tilde{\boldsymbol{c}} \in \left[ 0,1 \right]^n \\
|
||
\boldsymbol{x} \in \left\{ -1, 1 \right\}^n &\rightarrow
|
||
\tilde{\boldsymbol{x}} \in \mathbb{R}^n
|
||
\end{align*}
|
||
\end{minipage}
|
||
\end{minipage}%
|
||
\hfill%
|
||
\begin{minipage}[c]{0.4\linewidth}
|
||
\begin{figure}[H]
|
||
\centering
|
||
|
||
\tikzstyle{codeword} = [color=KITblue, fill=KITblue,
|
||
draw, circle, inner sep=0pt, minimum size=4pt]
|
||
|
||
\tdplotsetmaincoords{60}{245}
|
||
|
||
\begin{tikzpicture}[scale=1, transform shape, tdplot_main_coords]
|
||
\tikzstyle{every node}=[font=\normalsize]
|
||
|
||
% Cube
|
||
|
||
\draw[dashed] (0, 0, 0) -- (2, 0, 0);
|
||
\draw[dashed] (2, 0, 0) -- (2, 0, 2);
|
||
\draw[] (2, 0, 2) -- (0, 0, 2);
|
||
\draw[] (0, 0, 2) -- (0, 0, 0);
|
||
|
||
\draw[] (0, 2, 0) -- (2, 2, 0);
|
||
\draw[] (2, 2, 0) -- (2, 2, 2);
|
||
\draw[] (2, 2, 2) -- (0, 2, 2);
|
||
\draw[] (0, 2, 2) -- (0, 2, 0);
|
||
|
||
\draw[] (0, 0, 0) -- (0, 2, 0);
|
||
\draw[dashed] (2, 0, 0) -- (2, 2, 0);
|
||
\draw[] (2, 0, 2) -- (2, 2, 2);
|
||
\draw[] (0, 0, 2) -- (0, 2, 2);
|
||
|
||
% Codeword Polytope
|
||
|
||
% \draw[line width=1pt, color=KITblue] (0, 0, 0) -- (2, 0, 2);
|
||
% \draw[line width=1pt, color=KITblue] (0, 0, 0) -- (2, 2, 0);
|
||
% \draw[line width=1pt, color=KITblue] (0, 0, 0) -- (0, 2, 2);
|
||
|
||
% \draw[line width=1pt, color=KITblue] (2, 0, 2) -- (2, 2, 0);
|
||
% \draw[line width=1pt, color=KITblue] (2, 0, 2) -- (0, 2, 2);
|
||
|
||
% \draw[line width=1pt, color=KITblue] (0, 2, 2) -- (2, 2, 0);
|
||
|
||
% Polytope Annotations
|
||
|
||
\node[codeword] (c000) at (0, 0, 0) {};% {$\left( 0, 0, 0 \right) $};
|
||
\node[codeword] (c101) at (2, 0, 2) {};% {$\left( 1, 0, 1 \right) $};
|
||
\node[codeword] (c110) at (2, 2, 0) {};% {$\left( 1, 1, 0 \right) $};
|
||
\node[codeword] (c011) at (0, 2, 2) {};% {$\left( 0, 1, 1 \right) $};
|
||
|
||
\node[color=KITblue, right=0cm of c000] {$\left( 0, 0, 0 \right) $};
|
||
\node[color=KITblue, above=0cm of c101] {$\left( 1, 0, 1 \right) $};
|
||
\node[color=KITblue, left=0cm of c110] {$\left( 1, 1, 0 \right) $};
|
||
\node[color=KITblue, left=0cm of c011] {$\left( 0, 1, 1 \right) $};
|
||
|
||
% f
|
||
|
||
\node[color=KITgreen, fill=KITgreen,
|
||
draw, circle, inner sep=0pt, minimum size=4pt] (f) at (0.7, 0.7, 1) {};
|
||
\node[color=KITgreen, right=0cm of f] {$\tilde{\boldsymbol{c}}$};
|
||
\end{tikzpicture}
|
||
\end{figure}
|
||
\end{minipage}
|
||
\end{frame}
|
||
|