%% ------------------------------------------------------------------------- %%
%!TEX root = diss.tex


\chapter{Fundamentos da Teoria de Códigos}
\label{cap:codfundamentos}

A Teoria de Códigos é responsável por encontrar meios eficientes de transmitir
mensagens, de uma fonte a um receptor, através de um canal, possivelmente ruidoso.
Quando um canal de transmissão não é ruidoso, a meta é codificar uma mensagem
de modo que a mensagem transmitida tenha o mínimo possível de
símbolos, e a mensagem original possa ser decodificada da transmitida.
Por sua vez, numa transmissão feita por um canal ruidoso, a meta é codificar
a mensagem de modo que a mensagem original possa ser recuperada, mesmo que
alguns símbolos sejam alterados por conta de ruídos intrínsecos ao canal.

A Figura~\ref{fig:codific_canal} exemplifica a transmissão de uma mensagem $m$
por um canal ruidoso. Idealmente, $m = \hat{m}$ ao final da transmissão.
Porém, se o erro $e$ fizer $c'$ ser muito diferente de $c$, pode ser que o
algoritmo $D$ não seja capaz de recuperar a mensagem $m$ corretamente.
%
% \cite{shannon1948mathematical}
% \cite{roman1992coding}
% \cite{van2012introduction}

\usetikzlibrary{calc,trees,positioning,arrows,chains,shapes.geometric,%
decorations.pathreplacing,decorations.pathmorphing,shapes,%
matrix,shapes.symbols}

\tikzstyle{rec}=[draw, minimum size=2em]
\begin{figure}[h]
  \centering
  \begin{tikzpicture}[auto,>=latex']
    \node [rec] (fonte) {Fonte};
    \node [rec] (codif) [right of=fonte, node distance=3.3cm] {Codificador};
    \node [rec] (canal) [right of=codif, node distance=3.6cm] {Canal};
    \node [rec] (decod) [right of=canal, node distance=3.8cm] {Decodificador};
    \node [rec] (recep) [right of=decod, node distance=4cm] {Receptor};

    \path[->] (fonte) edge node {$m \in \mathcal{M}$} (codif);
    \path[->] (codif) edge node {$c = E(m)$} (canal);
    \path[->] (canal) edge node {$c' = c \oplus e$} (decod);
    \path[->] (decod) edge node {$\hat{m} = D(c')$} (recep);

      % \node (b) [left of=a,node distance=2cm, coordinate] {a};
      % \node [int, pin={[init]above:$p_0$}] (c) [right of=a] {$\frac{1}{s}$};
      % \node [coordinate] (end) [right of=c, node distance=2cm]{};
      % \path[->] (b) edge node {$a$} (a);
      % \path[->] (a) edge node {$v$} (c);
      % \draw[->] (c) edge node {$p$} (end) ;
  \end{tikzpicture}
  \caption{Transmissão de uma palavra $m$ através de um canal que produziu o
  erro $e$, usando algoritmos $E$ e $D$, de codificação e decodificação, respectivamente.}
\label{fig:codific_canal}
\end{figure}

Quando o canal de transmissão não é ruidoso, e a meta da codificação é a compressão
de mensagens, dizemos que há codificação da fonte. E quando o canal é ruidoso, e
a codificação adiciona redundâncias à mensagem, dizemos que há codificação de canal.
Para os algoritmos criptográficos que analisamos nesta dissertação, é útil apenas a
teoria de codificação de canal.

Chama-se \emph{alfabeto da fonte} o conjunto de símbolos que a fonte usa para
formar mensagens. O conjunto de todas as possíveis mensagens é chamado
\emph{espaço de mensagens}, e denotado por $\mathcal{M}$. Usa-se um algoritmo
PPT $E$ para codificar uma mensagem m, transformando-a numa \emph{palavra de código}.
O conjunto de todas as palavras de código chama-se \emph{código}, e é denotado por
$\mathcal{C}$.


\section{Códigos Lineares}


\section{Algumas Famílias de Códigos Notáveis}
\label{cap:codigos}


\subsection{Códigos de Repetição}

Esses são provavelmente os códigos mais simples que se pode imaginar. A ideia é
codificar um bit como a repetição de uma mensagem de k A ideia é, na
transmissão de

\begin{definition}
  Um \emph{código de repetição} é um código [$n$, 1]-linear definido pela seguinte
  matriz geradora de dimensão $1 \times n$
  \[
    G = [1\ 1 \ldots 1].
  \]
\end{definition}


\subsection{Códigos de Verificação Única de Paridade}

\subsection{Códigos Quase Cíclicos}

\subsection{Códigos de Goppa}
Principais referências:~\cite{engelbert2007summary},~\cite{van1993coding},~\cite{berlekamp1973goppa},
~\cite{patterson1975algebraic},~\cite{bernstein2008attacking}


\subsubsection{Definições}

\begin{definition}
Sejam $L = (\gamma_0, \ldots, \gamma_{n-1})$ um vetor com $n$ elementos distintos de $GF(2^m)^n$, e $g(x)$
um polinômio irredutível de grau $t$ de $GF(2^m)[x]$.
Um \textbf{código de Goppa binário e irredutível} $\mathcal{G}$ é o conjunto de vetores
$c = (c_0, \ldots, c_{n-1})$ de $GF(2)^n$ para que vale a identidade
$$
\sum_{i=0}^{n - 1} \frac{c_i}{x - \gamma_i} \equiv 0 \mod g(x).
$$

Para explicitar a relação entre $\mathcal{G}$ e o par $(L, g)$, dizemos que $\mathcal{G} = \Gamma(L, g)$.
\end{definition}

\begin{definition}
Dados um código de Goppa binário e irredutível $\mathcal{G} = \Gamma(L, g)$ e um vetor $c$ de $GF(2)^n$. A \textbf{síndrome}
de um vetor $c$, denotada por $S_c(x)$, é o polinômio
$$
S_c(x) = \sum_{i=0}^{n-1} \frac{c_i}{x - \gamma_i} \mod g(x).
$$

Então é claro que os $\mathcal{G}$ é o conjunto de vetores com síndrome nula.
\end{definition}

\begin{theorem}
Todo código de Goppa binário e irredutível $\Gamma(L, g)$ tem distância mínima de maior ou igual $2t + 1$, onde
$t$ é o grau de $g$.
\end{theorem}

\begin{proof} \label{proof:gop_min_dist}
Seja $\goppa = \goppair$ \cgbi , com $g$ de grau $t$, e $L = (\gamma_0, \ldots, \gamma_{n-1})$. Tome
$c$ uma palavra qualquer do código $\goppa$, e seja $\mathcal{T}_c$ o seu suporte
$\mathcal{T}_c = \{i : c_i = 1\}$. Queremos provar que o $\wt(c) \geq 2t + 1$.

Considere o seguinte polinômio $\sigma_c$, de grau $\wt(c)$, dado por
$$
\sigma_c(x) = \prod_{i \in \supp{c}} (x - \gamma_i).
$$

Se $c$ for a palavra nula, convencionamos $\sigma_c(x) = 1$.
Fazendo o produto de $\sigma_c$ pela síndrome de $c$, temos

\begin{align*}
\sigma_c(x) S_c(x)
  &\equiv \prod_{i \in \supp{c}} (x - \gamma_i) \sum_{i=0}^{n-1} \frac{c_i}{x - \gamma_i}     \\
  &\equiv \prod_{i \in \supp{c}} (x - \gamma_i) \sum_{i \in \supp{c}} \frac{1}{x - \gamma_i}  \\
  &\equiv \sum_{i \in \supp{c}} \prod_{j \neq i \in \supp{c}} (x - \gamma_i) \\
  &\equiv \sigma_c'(x) \mod g(x).
\end{align*}

Como $g$ é irredutível, $\sigma$ admite inversa módulo $g$. Então
$$
\frac{\sigma_c'(x)}{\sigma_c(x)} \equiv  S_c(x) \mod g(x).
$$

Podemos, assim, definir o código $\goppa$ como o conjunto de todos os vetores $c$ para que
$\sigma_c'(x) \equiv 0 \mod g(x)$.

Pela definição de derivada formal, e por $GF(2^m)$ ter característica $2$, temos que
\begin{align} \label{sigma_der}
\sigma_c'(x) = \sum_{i=1}^n i \sigma_i x^{i - 1} = \sum_{i=0}^{n/2} \sigma_{2i+1} x^{2i}.
\end{align}
Ou seja, $\sigma_c'(x)$ é soma de potências pares de $x$ e, portanto, um quadrado de outro elemento de
$GF(2^m)[x]$. Como $g$ é irredutível, devemos ter que $g$ divide $\sqrt{\sigma_c'}$, o que implica que
$g^2$ divide $\sigma_c'$. Portanto, para toda palavra não nula $c$ de $\goppa$, vale que
\begin{align*}
\wt(c) = \deg \sigma_c \geq 1 + \deg \sigma_c' \geq 1 + 2 \deg g = 2t + 1.
\end{align*}

\end{proof}

\subsubsection{Codificação}


\subsubsection{Decodificação}

Seja $\goppa = \goppair$, com $L = (\gamma_0, \ldots, \gamma_{n-1})$ e $g$ de grau $t$.
Considere palavra $m$ de $\goppa$ foi somada a um erro $e$ tal que $\wt(e) \leq t$,
obtendo $c = m \oplus e$.
Demonstramos o funcionamento do algoritmo de Patterson para correção dos $\wt(e)$ erros de $c$.

Como $m \in \goppa$, temos que
$$
S_c(x) \equiv S_m(x) + S_e(x) \equiv S_e(x) \mod g(x).
$$

Seja $\supp{e}$ o suporte de $e$, definimos o polinômio localizador de erros $\sigma_e$
$$
\sigma_e(x) = \prod_{i \in \supp{e}} (x - \gamma_i).
$$
Como vemos no meio da demonstração do Teorema~\ref{proof:gop_min_dist}, esse polinômio
é tal que
\begin{align} \label{sigsind_eq_sigder}
\sigma_c(x) S_c(x) \equiv \sigma_c'(x) \mod g(x).
\end{align}

Como $GF(2^m)$ tem característica $2$, $ b \longmapsto b^2$ é automorfismo de Frobenius, e então
todos os seus elementos são quadrados perfeitos. Então podemos calcular facilmente a
raiz quadrada de qualquer polinômio, formado apenas por potências pares, da seguinte
forma
$$
\sqrt{\prod_{i=0}^l a_i x^{2i}} = \prod_{i=0}^l \sqrt{a_i} x^{i}.
$$

Assim, podemos separar $\sigma_e$ em quadrados e não quadrados, para algum par de
polinômios $\sigma_0$ e $\sigma_1$, como
$$
\sigma_e(x) = \sigma_0^2(x) + x \sigma_1^2(x).
$$

Pela equação \ref{sigma_der} $\sigma_e'(x) = \sigma_1^2(x)$, e então
podemos reescrever a equação \ref{sigsind_eq_sigder} como
\begin{align}
(\sigma_0^2(x) + x \sigma_1^2(x))S_e(x) &\equiv \sigma_1^2(x) \mod g(x) \\
\implies \sigma_1^2(x)(xS_e(x) + 1) &\equiv \sigma_0^2(x)S_e(x) \mod g(x).
\end{align}

Multiplicando os dois lados por $T(x) = S_e^{-1}(x)$
$$
\sigma_1^2(x)(x + T(x)) \equiv \sigma_0^2(x) \mod g(x).
$$

E seja $\tau(x)$ a raiz quadrada de $1 + T(x)$
$$
\sigma_1(x) \tau(x) \equiv \sigma_0 \mod g(x).
$$

Como $\sigma_0(x)$ e $\sigma_1(x)$ podem ser determinados numa variação do algoritmo
extendido de euclides aplicado à entrada $(\tau(x), g(x))$, é possível obter o
polinômio corretor de erros.


\subsection{Códigos LDPC}
%Seguimos a exposição de \cite{baldi2014ldpc_crypto}

Uma outra família que admite decodificadores eficientes é a dos códigos com matriz verificação
de paridade de baixa densidade. Para nos referir a eles, usamos a abreviação comumente usada \emph{LDPC}, do
inglês \emph{low-density parity-check codes}. Estes códigos foram descobertos por Gallager \cite{gallager1962low}
na década de 60, e redescobertos por McKay.

Gallager notou que códigos com matrizes de paridade esparsas podem ser decodificados eficientemente
usando algoritmos iterativos.

\begin{definition}
  Um código binário e linear com matriz de verificação de paridade $H$ é dito um código
  \textbf{LDPC} se o número de elementos não nulos de $H$ é $\mathcal{O}(n)$.
\end{definition}

\begin{definition}
  Um código LDPC com matriz de verificação de paridade $H$ é dito \emph{regular} se todas
  as colunas de $H$ têm mesmo peso $g$, e todas as suas linha têm mesmo peso $r$. Assim,
  é claro que $mr = ng$, e, pela esparsidade de $H$, deve-se ter que $g \ll m$, ou
  equivalentemente que $r \ll n$.
\end{definition}

\begin{definition}
  O \textbf{grafo de Tanner} associado a uma matriz de verificação de paridade $H^{(n-k) \times n}$
  é um grafo $T_H$ bipartido entre os conjuntos $C$, dos
  \textbf{nós de verificação}, e $V$, dos \textbf{nós de variáveis}, tais que:
  \begin{enumerate}
    \item $C = \{ c_1, \ldots, c_{n-k} \}$, e cada $c_i$ representa a linha $i$ de $H$;
    \item $V = \{ v_1, \ldots,  v_n \}$, e cada $v_j$ representa a coluna $j$ de $H$;
    \item A aresta $\{ c_i, v_j \}$ pertence a $T_H$ se e somente se $H_{i, j} = 1$.
  \end{enumerate}
\end{definition}

\begin{example}[Grafo de Tanner]
\label{ex:exemplo_tanner}
  A Figura~\ref{fig:exemplo_tanner} mostra o grafo de Tanner da matriz
  \[
    H =
    \begin{bmatrix}
      1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
      1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
      0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 \\
      0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
      0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1
    \end{bmatrix}.
  \]

  \begin{figure}[h]
    \begin{tikzpicture}[thick,
      every node/.style={draw,circle,minimum size=4mm,inner sep=0pt,outer sep=0pt},
      fsnode/.style={fill=white},
      ssnode/.style={fill=gray},
      every fit/.style={ellipse,draw,inner sep=-2pt,text width=2cm},
      -,shorten >= 2pt,shorten <= 3pt,very thin
    ]
       %% the check_nodes
       \begin{scope}[xshift=28.5mm,start chain=going right,node distance=7mm]
       \foreach \i in {1,...,5}
         \node[ssnode,on chain] (c\i) [label=above: $c_{\i}$] {};
       \end{scope}

       %% the var_nodes
       \begin{scope}[yshift=-4cm, start chain=going right,node distance=7mm]
       \foreach \i in {1,...,10}
         \node[fsnode,on chain] (v\i) [label=below: $v_{\i}$] {};
       \end{scope}

       \draw (c1) -- (v1);
       \draw (c1) -- (v2);
       \draw (c1) -- (v3);
       \draw (c1) -- (v4);
       \draw (c2) -- (v1);
       \draw (c2) -- (v5);
       \draw (c2) -- (v6);
       \draw (c2) -- (v7);
       \draw (c3) -- (v2);
       \draw (c3) -- (v5);
       \draw (c3) -- (v8);
       \draw (c3) -- (v9);
       \draw (c4) -- (v3);
       \draw (c4) -- (v6);
       \draw (c4) -- (v8);
       \draw (c4) -- (v10);
       \draw (c5) -- (v4);
       \draw (c5) -- (v7);
       \draw (c5) -- (v9);
       \draw (c5) -- (v10);
     \end{tikzpicture}
     \caption{Grafo de Tanner da matriz $H$.}
  \label{fig:exemplo_tanner}
  \end{figure}
\end{example}

\subsubsection{Codificação}

Como são códigos lineares, códigos LDPC podem ser codificados usando uma matriz
geradora derivada da matriz de verificação de paridade. Por exemplo, para o
código mostrado no Exemplo~\ref{ex:exemplo_tanner}, temos como uma possível matriz
geradora
\[
G =
  \begin{bmatrix}
    1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
    0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\
    0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
    0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
    0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\
    0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1
  \end{bmatrix}.
\]

Porém, este não é o meio mais eficiente para codificar mensagens com códigos LDPC.
Isso pois a matriz geradora nem sempre é esparsa, e assim
os melhores métodos de codificação são aqueles que usam esparsidade da própria
matriz de paridade. Estes algoritmos estão fora do nosso escopo, pois ao tratar
de criptografia assimétrica, veremos que é fundamental que a chave pública não
exponha a representação esparsa do código.

Um caso importante é quando o código LDPC é quase cíclico e \textbf{eu tenho que falar
como é feita a geração!}

\subsubsection{Decodificação}

A decodificação de códigos LDPC é feita por meio de algoritmos iterativos de aproximação.
Há duas classes de decodificadores LDPC: os de decisão dura, e os de decisão suave.
Ambos os tipos de decodificadores funcionam por meio da passagem de mensagem através das arestas
de um grafo de Tanner. E a distinção entre decisão dura ou suave se dá pelo conjunto a
que pertence a mensagem, sendo discreto para os de decisão dura, e contínuo para os de
decisão suave.

Com algoritmos de decisão dura, a decodificação de uma mensagem transmitida é feita através de
sucessivas inversões de seus bits, até possivelmente chegar na mensagem original.
Por sua vez, os de decisão suave usam algoritmos de propagação de crença
sobre a probabilidade de determinado bit da
mensagem transmitida ser 1 ou não.

Para adquirir certa intuição sobre as duas classes de decodificadores, considere as
Figuras~\ref{fig:decod_dura} e~\ref{fig:decod_suave}. Elas mostram a decodificação
de uma palavra $c' = c \oplus e$ para a palavra $c$. A primeira mostra a decodificação
usando o algoritmo de \emph{bit-flipping}, e a segunda mostra a mesma decodificação usando o algoritmo de
propagação de crença. Os dois exemplos são decodificações para um código LDPC real que gerei
aleatoriamente. Este código tem tamanho $n = 50$, dimensão $k = 25$, e tem colunas de mesmo
peso $w_c = 4$. Não é feito nenhum controle sobre o peso das linhas, nem sobre a
maximização da cintura. E os algoritmos que implementei são os mesmos de Gallager.

\begin{figure}[htpb]
  \includegraphics[scale = 1] {figuras/teocod/hard_decision_dec.png}
  \caption{Decodificação por decisão dura.}
\label{fig:decod_dura}
\end{figure}

\begin{figure}[htpb]
  \includegraphics[scale = 1]{figuras/teocod/soft_decision_dec.png}
  \caption{Decodificação por decisão suave.}
\label{fig:decod_suave}
\end{figure}


\paragraph{Decodificação Dura}


\paragraph{Algoritmo B de Gallager} \  \\

\begin{algorithm}[H]
  \Entrada{$H$ matriz de paridade de um código LDPC.\\
  \myinput{$y$ uma palavra transmitida a ser decodificada.}
  \myinput{\texttt{max\_it} o número máximo de iterações.}
  }
  \Saida{Uma decodificação estimada de $y$, ou $\perp$ se o número máximo de
         iterações for excedido.}
  \Inicio{
    $T = (C \cup V, E) \gets $ Grafo de Tanner de $H$ \\
    \Para{cada $j \in 1, \ldots, |V| $}{
      $M_j \gets y_j$
    }
    \Para{cada $(i, j) \in E$}{
      $M_{j \rightarrow i} \gets M_j$
    }
    \texttt{it} $\gets$ 0 \\
    $ \hat{y} = y $ \\
    \Enqto{$\hat{y} H^T \neq 0 $ e \emph{\texttt{it}} < \emph{\texttt{max\_it}}}{
      \Para{cada $(i, j) \in E$}{
        $
        M_{i \rightarrow j} \bigoplus_{v_{j'} \in N(c_i) - \{ v_j \}} M_{j' \rightarrow i}
        $
      }
      \Para{cada $(i, j) \in E$}{
        $d \gets \left| \left\{ c_{i'} \in N(v_j) - \{ c_i \} : M_{i' \rightarrow j} = \bar{M_j} \right\} \right|$

        \Se{$d \leq b$} {
          $M_{j \rightarrow i} = \bar{M_j}$
        }
        \Senao{
          $M_{j \rightarrow i} = M_j$
        }
      }
      \Para{cada $j \in 1, \ldots, |V| $}{
        \Se{$ N(j) $ é ímpar}{
          $\hat{y}_j \gets $ moda do conjunto de mensagens $\left\{ M_{i \rightarrow j} \ \forall i \right\}$
        }
        \Senao{
          $\hat{y}_j \gets $ moda do conjunto $\left\{ M_j \right\} \cup \left\{ M_{i \rightarrow j} \ \forall i  \right\}$
        }
      }
      \texttt{it} $\gets$ \texttt{it} + 1
    }

    \Se{$\hat{y} H^T = 0 $}{
      \Retorna{$\hat{y}$}
    }
    \Senao{
      \Retorna{$\perp$}
    }
  }
  \caption{Algoritmo B de Gallager}
\end{algorithm}
\label{alg:bit_flipping}

\paragraph{Decodificação Suave} \ \\

\begin{algorithm}[H]
  \Entrada{$H$ matriz de paridade de um código LDPC.\\
  \myinput{$y$ uma palavra transmitida a ser decodificada.}
  \myinput{\texttt{max\_it} o número máximo de iterações.}
  }
  \Saida{Uma decodificação estimada de $y$, ou $\perp$ se o número máximo de
         iterações for excedido.}
  \Inicio{
    $T = (C \cup V, E) \gets $ Grafo de Tanner de $H$ \\
    \Para{cada $j \in 1, \ldots, |V| $}{
      $L_j \gets L(v_j | y_j)$
    }
    \Para{cada $(i, j) \in E$}{
      $L_{j \rightarrow i} \gets L_j$
    }
    \texttt{it} $\gets$ 0 \\
    $ \hat{y} = y $ \\
    \Enqto{$\hat{y} H^T \neq 0 $ e \emph{\texttt{it}} < \emph{\texttt{max\_it}}}{
      \Para{cada $(i, j) \in E$}{
        $
        L_{i \rightarrow j} \gets 2 \tanh^{-1} \left( \prod_{j' \in N(c_i) - \{v_j\}} \tanh \left(  \frac12 L_{j' \rightarrow i} \right) \right)
        $
      }
      \Para{cada $(i, j) \in E$}{
        $
        L_{j \rightarrow i} \gets L_j + \sum_{i' \in N(v_j) - \{ c_i \}} L_{i' \rightarrow j}
        $
      }
      \Para{cada $j \in 1, \ldots, |V| $}{
        $L_j^{\text{total}} \gets L_j + \sum_{i \in N(v_j)} L_{i \rightarrow j}$
      }
      \Para{cada $j \in 1, \ldots, |V| $}{
        \Se{$L_j^{\text{total}} < 0$}{
          $\hat{y}_j \gets 1$
        }
        \Senao{
          $\hat{y}_j \gets 0$
        }
      }
      \texttt{it} $\gets$ \texttt{it} + 1
    }
    \Se{$\hat{y} H^T = 0 $}{
      \Retorna{$\hat{y}$}
    }
    \Senao{
      \Retorna{$\perp$}
    }
  }
  \caption{Propagação de Crença}
\end{algorithm}
\label{alg:propagacao_crenca}


Algoritmos de propagação um código LDPC pode de crença são algoritmos de processamento distribuído
entre os nós de um grafo
