\documentclass[a4paper,11pt]{report}
\usepackage{latexsym}
\usepackage[activeacute,spanish]{babel}
\usepackage[dvips]{graphicx}
\usepackage{makeidx}

\addtolength{\textwidth}{1.5cm} \addtolength{\textheight}{0.5cm}

\author{Alberto~Molina~Mart\'inez \\ Jos\'e \'Angel de Pascual Viciana}
\title{CODEC Hamming}
\frenchspacing \linespread{1.1}

\begin{document}
\newenvironment{ejemplo}{\paragraph{Ejemplo:}}{}
\hyphenation{pa-la-bras pa-la-bra} \maketitle \tableofcontents

\chapter{El proyecto}
\section{Justificaci'on de proyecto}
En cualquier comunicaci'on electr'onica (por ejemplo, en una red
de computadores) es conveniente saber si se han producido errores
en la transmisi'on. Por desgracia hoy d'ia es muy frecuente que la
informaci'on enviada por un emisor se altere en el medio de
transmisi'on, por efectos del ruido, con lo cual el receptor
recibir'ia ``algo'' diferente a lo que se envi'o.

Esencialmente, hay tres m'etodos de correcci'on de errores:

\begin{description}
  \item[Sustituci'on de s'imbolos.] La \emph{sustituci'on de
  s'imbolos} se dise\~n'o para usarse en un ambiente humano: en donde
  hay un ser humano, en la terminal de recepci'on, para analizar
  los datos recibidos y tomar decisiones sobre su integridad. Con
  la sustituci'on de s'imbolos, si un car'acter se recibe en error,
  en vez de revertirse a un nivel superior de correcci'on de
  errores o mostrar el car'acter incorrecto, un car'acter 'unico que
  es indefinido por el c'odigo de caracteres, tal que como un signo
  de interrogaci'on invertido, se sustituye por el car'acter malo.
  Si el car'acter err'oneo no puede distinguirse por el operador, la
  retransmisi'on es para llamada (o sea, la sustituci'on de s'imbolos
  es una forma de retransmisi'on selectiva). Por ejemplo, si el
  mensaje ``nombre'' ten'ia un error en el primer car'acter, se
  mostrar'ia como ``?ombre'', un operador puede discernir el
  mensaje correcto por inspecci'on, y la retransmisi'on no es
  necesaria. Sin embargo, si el mensaje ``\$?,000.00'' se
  recibiera, un operador no podr'ia determinar el car'acter correcto
  y la retransmisi'on ser'ia requerida.

  \item[Retransmisi'on.] La \emph{retransmisi'on}, como el nombre lo
  implica, es volver a enviar un mensaje, cuando es recibido un
  error, y la terminal de recepci'on autom'aticamente pide la
  retransmisi'on de todo el mensaje. La retransmisi'on
  frecuentemente se llama ARQ, el cual es un t'ermino antiguo de la
  comunicaci'on de radio, que significa \emph{petici'on autom'atica
  para la retransmisi'on}. ARQ es probablemente el m'etodo m'as
  confiable de correcci'on de errores, aunque no siempre es el m'as
  eficiente. Las dificultades en el medio de transmisi'on ocurren
  en r'afagas. Si se usan mensajes cortos, la probabilidad de que
  una dificultad ocurra, durante la transmisi'on, es peque\~na. Sin
  embargo, los mensajes cortos requieren de m'as reconocimientos y
  regresos de l'inea que los mensajes largos. Los reconocimientos y
  regresos de l'inea para el control de error son formas de
  \emph{encabezamientos} (caracteres diferentes a los datos que se
  deben transmitir). Con los mensajes largos, menos tiempo de
  regreso es necesario, aunque la probabilidad de que un error de
  transmisi'on ocurra es mayor que para los mensajes cortos. Se
  puede mostrar, de manera estad'istica, que los bloques de
  mensajes entre 256 y 512 caracteres son de tama\~no 'optimo, cuando
  se utiliza ARQ para correcci'on de errores.

  \item[Seguimiento de correcci'on de error.] El \emph{seguimiento de correcci'on de
  error} (FEC), es el 'unico esquema de correcci'on de error que
  detecta y corrige los errores de transmisi'on, del lado receptor,
  sin pedir retransmisi'on.

  Con FEC, se agregan bits al mensaje antes de la transmisi'on. Un
  c'odigo de correcci'on de errores popular, es el \emph{c'odigo de
  Hamming}, desarrollado por R. W. Hamming, en los laboratorios
  Bell. Este ser'a el procedimiento que el proyecto va
  estudiar, e incluso llegando a hacer un dise\~no l'ogico que nos
  permita simularlo. El desarrollo te'orico del c'odigo Hamming se
  encuentra en el \textbf{ap'endice \ref{A}}.

  El c'odigo de Hamming que tratamos, detectar'a s'olo errores de un
  s'olo bit, no se puede usar para identificar errores de bit
  m'ultiples.
\end{description}

El c'odigo de Hamming, como todos los c'odigos FEC, requiere de la
adici'on de los bits a los datos, alargando consecuentemente el
mensaje transmitido. El prop'osito de los c'odigos FEC es reducir
o eliminar el tiempo gastado en retransmisiones. Sin embargo, la
suma de los bits FEC a cada mensaje gasta el tiempo de
transmisi'on. Obviamente, se negocia entre ARQ y FEC, y los
requerimientos del sistema determinan qu'e m'etodo es mejor para
un sistema en particular. El FEC frecuentemente se usa para
transmisiones sencillas a muchos receptores, cuando los
reconocimientos no son pr'acticos.

Existen muchos tipos de c'odigos Hamming en funci'on del n'umero
de bits redundantes que se quieran a\~nadir. Este n'umero nos
determinar'a la longitud de la palabra c'odigo completa, as'i como
el n'umero de bits de informaci'on del mensaje. En la secci'on
te'orica se habla con m'as detalle acerca de este concepto. En
nuestro caso hemos escogido 3 bits redundantes, por lo que tenemos
una palabra c'odigo de 7 bits (longitud 7), de los cuales, 4 son
de informaci'on. A partir de ahora, denominaremos nuestro c'odigo
como un c'odigo Hamming (7,4).

En las siguientes secciones se describir'a, paso a paso, c'omo ha
sido el proceso de dise\~no de este sistema de correcci'on de
errores.


\section{Un planteamiento general}
Antes de proceder al dise\~no de componentes es preciso alzar la
vista y ver d'onde se sit'ua el sistema en el contexto de una
comunicaci'on electr'onica--digital.

Hagamos una descomposici'on funcional del sistema y de c'omo 'este
interacciona con las entidades externas.

\begin{figure}[!h]
\begin{center}
\includegraphics[width=15cm,height=7.5cm]{Figura1.bmp}
\caption{Diagrama de contexto de nuestro sistema} \label{figura1}
\end{center}
\end{figure}

Como elementos externos o ajenos al sistema tenemos los
siguientes:
\begin{itemize}
  \item \textbf{Emisor:} Es la parte que env'ia informaci'on al
  receptor.
  \item \textbf{Receptor:} Es quien recibe la informaci'on enviada
  anteriormente.
  \item \textbf{Canal de transmisi'on}: Es el medio f'isico por el
  cual se transmiten los datos enviados por el emisor. Este canal,
  por lo general, suele alterar ocasionalmente los datos
  transmitidos.
\end{itemize}

El sistema que nosotros proponemos estar'ia compuesto por los
siguientes m'odulos:
\begin{itemize}
  \item \textbf{Codificador:} Es el subsistema encargado de
  codificar el mensaje enviado por el emisor a una palabra del
  c'odigo Hamming (7,4).

  \item \textbf{Protocolo de env'io:} Este elemento recibe una
  palabra c'odigo de 7 bits en paralelo, y la env'ia al canal de
  transmisi'on en serie. En definitiva, lo que tenemos es un
  conversor paralelo--serie.

  \item \textbf{Protocolo de recepci'on:} Recibe los datos del
  canal de transmisi'on transform'andolos de serie a paralelo.
  Adem'as se encarga de la sincronizaci'on de relojes para que se
  lean los bits en el momento adecuado. Devuelve una palabra de 7
  bits en paralelo al decodificador.

  \item \textbf{Decodificador:} Se encarga de decodificar una
  palabra c'odigo en un mensaje, corrigiendo cualquier error que se
  hubiera cometido.

  \item \textbf{Relojes:} Se trata de dos relojes con la misma
  frecuencia pero desfasados un tiempo $t$, igual al tiempo de
  transmisi'on por el canal.
\end{itemize}

\section{M'odulo codificador}
El codificador recibe una palabra en serie de cuatro bits
procedente del emisor. A continuaci'on esta palabra se multiplica
por la matriz generadora ($G$), resultando as'i una palabra de
siete bits ya codificada. Este proceso se explica con m'as detalle
en la secci'on de teor'ia del ap'endice. Resumiendo, se realiza la
siguiente operaci'on:

\begin{displaymath}
(x_{3}x_{2}x_{1}x_{0}) \times \left( \begin{array}{cccc|ccc}
1 & 0 & 0 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
\end{array} \right)=(y_{6}y_{5}y_{4}y_{3}y_{2}y_{1}y_{0})
\end{displaymath}

El orden de llegada de los bits al m'odulo codificador debe ser
del m'as significativo al menos significativo, es decir, primero
llega $x_{3}$, luego llegar'ia $x_{2}$, $X_{1}$ y por 'ultimo
$x_{0}$.

Como es de suponer, la velocidad de transmisi'on de la palabra
debe ajustarse a un reloj con una frecuencia preestablecida. Dicho
de otro modo, por cada pulso de reloj se leer'a la informaci'on
contenida en el canal y ser'a interpretada como un bit.

Entrando ya en el funcionamiento interno del propio m'odulo
codificador, los bits de entrada van llegando, uno a uno, a un
registro de desplazamiento de longitud 4. Por tanto, cada 4 ciclos
de reloj el registro contendr'a un mensaje v'alido apto para ser
codificado.

En teor'ia, la codificaci'on se hace mediante una multiplicaci'on
de matrices, esto puede simplificarse en un circuito combinacional
ya que esta matriz generadora es siempre la misma para nuestro
c'odigo Hamming. Si observamos esta matriz generadora vemos que
las cuatro primeras columnas forman una matriz identidad $4 \times
4$, en consecuencia, los 4 primeros bits de la palabra codificada
deber'an coincidir con el mensaje del emisor. Las tres 'ultimas
columnas de $G$ ser'an las que aporten los bits de redundancia que
posibilitar'an la futura correcci'on de errores.

Aprovechamos el hecho de que la multiplicaci'on en base 2 se
corresponde con una operaci'on l'ogica AND, y la suma con la XOR.
Entonces la multiplicaci'on de una palabra por una matriz se
resume:

\begin{displaymath}
(x_{3}x_{2}x_{1}x_{0}) \times \left( \begin{array}{ccc}
d_{1,1} & d_{1,2} & d_{1,3} \\
d_{2,1} & d_{2,2} & d_{2,3} \\
d_{3,1} & d_{3,2} & d_{3,3} \\
d_{4,1} & d_{4,2} & d_{4,3} \\
\end{array} \right) = \begin{array}{c}
((x_{3} \otimes d_{1,1}) \oplus (x_{2} \otimes d_{2,1}) \oplus
(x_{1} \otimes d_{3,1}) \oplus (x_{0} \otimes d_{4,1}), \\ (x_{3}
\otimes d_{1,2}) \oplus (x_{2} \otimes d_{2,2}) \oplus (x_{1}
\otimes d_{3,2}) \oplus (x_{0} \otimes d_{4,2}), \\ (x_{3} \otimes
d_{1,3}) \oplus (x_{2} \otimes d_{2,3}) \oplus (x_{1} \otimes
d_{3,3}) \oplus (x_{0} \otimes d_{4,3})) \end{array}
\end{displaymath}

Esto, aplicado a nuestro caso ser'ia:
\begin{displaymath}
(x_{3}x_{2}x_{1}x_{0}) \times \left( \begin{array}{ccc}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \\
1 & 1 & 1 \\
\end{array} \right) = \begin{array}{c}
((x_{3} \otimes 0) \oplus (x_{2} \otimes 1) \oplus (x_{1} \otimes
1) \oplus (x_{0} \otimes 1),\\ (x_{3} \otimes 1) \oplus (x_{2}
\otimes 0) \oplus (x_{1} \otimes 1) \oplus (x_{0} \otimes 1),\\
(x_{3} \otimes 1) \oplus (x_{2} \otimes 1) \oplus (x_{1} \otimes
0) \oplus (x_{0} \otimes 1)) \end{array}
\end{displaymath}

La codificaci'on que hemos visto se realiza constantemente incluso
para estados intermedios del registro de desplazamiento. Hay que
admitir s'olo aquellos resultados correctos, para esto lo que se
hace es a\~nadir siete flip--flops~D que s'olo admiten el
resultado al final del cuarto ciclo. Se consigue de este modo que
la palabra c'odigo que haya en la salida del codificador siempre
sea correcta, y adem'as, persista durante todo el tiempo que va
llegando la siguiente palabra. Esto 'ultimo es muy importante
porque si no no habr'ia que enviar toda la palabra c'odigo de 7
bits en un ciclo y no en 4 como est'a pensado.

Estos son los puntos claves de este m'odulo, adem'as hay detalles
que no se han mencionado ya que solamente sirven para llevar el
control de todo lo anterior.

En la l'amina~1 se muestra el circuito correspondiente a este
m'odulo.

\section{M'odulo decodificador}
Este m'odulo es muy similar al codificador. En este caso se
reciben 7 bits en serie correspondientes a la palabra c'odigo a
decodificar. Una vez m'as, en la secci'on de teor'ia se explica
c'omo decodificar una palabra c'odigo usando la matriz de paridad
($H$) y s'indromes\footnote{Este t'ermino se usa en el proceso de
decodificaci'on y es explicado en la parte de teor'ia.}.

En este m'odulo tambi'en existe un registro de desplazamiento para
gestionar la recepci'on de la serie de bits. Adem'as est'a la
l'ogica encargada de la multiplicaci'on de dicha palabra por $H$
para el c'alculo del s'indrome (l'ogica similar a la empleada en
el m'odulo codificador).

Cuando el s'indrome calculado es $(001)$, $(010)$, $(011)$ 'o
$(100)$ se debe de sumar un 1 a la posici'on indicada por el
s'indrome (esta posici'on es el valor decimal del s'indrome). De
esta forma queda corregido un posible error (uno y s'olo uno). Si
el s'indrome es cualquier otro valor la palabra decodificada
ser'an los primeros 4 bits sin ning'un cambio.

En la l'amina~3 est'a el esquema l'ogico correspondiente al
m'odulo decodificador.

\section{Relojes secundarios}
A lo largo del transcurso de codificaci'on y decodificaci'on
existen situaciones en las que es preciso, por ejemplo, leer
cuatro bits a la vez que se env'ian 7. Es decir, deben existir dos
relojes que, en el mismo tiempo, uno haga cuatro pulsos y el otro
siete, todo esto sin ninguna posibilidad de desfase.

En principio no parece f'acil ya que 7 no es m'ultiplo de 4. En
una simulaci'on por computador ser'ia posible crear dos relojes
independientes de forma que uno sea 1,75 veces m'as r'apido que el
otro, pero en la realidad esto es inviable. Sin embargo, lo que
s'i se puede hacer es tener un reloj principal y los dos relojes
mencionados dependiendo de 'este. El m'inimo com'un m'ultiplo de 7
y 4 es 28, por tanto, cada 28 ciclos del reloj principal los
relojes secundarios deben coincidir. Adem'as, en estos 28 ciclos
uno de los relojes debe hacer 4 pulsos y el otro 7, o lo que es lo
mismo, cada 4 pulsos del reloj principal habr'a un pulso para el
reloj de 7 y cada 7 pulsos habr'a un ciclo para el reloj de 4.

A partir de ahora, llamaremos \emph{reloj7} al reloj secundario
r'apido y \emph{reloj4} al lento.

Necesitamos un contador asociado al reloj principal que cuente
desde 0 hasta 27, dise\~nado en el ap'endice \ref{c27}.

Esta ser'ia la tabla de verdad para el reloj7 en funci'on de los
valores del contador anterior:

\begin{center}
\begin{tabular}{|ccccc|c|}\hline
  $Q_{4}$ & $Q_{3}$ & $Q_{2}$ & $Q_{1}$ & $Q_{0}$ & $reloj7$\\ \hline \hline
  0 & 0 & 0 & 0 & 0 & 1 \\ \hline
  0 & 0 & 0 & 0 & 1 & 0 \\ \hline
  0 & 0 & 0 & 1 & 0 & 0 \\ \hline
  0 & 0 & 0 & 1 & 1 & 0 \\ \hline
  0 & 0 & 1 & 0 & 0 & 1 \\ \hline
  0 & 0 & 1 & 0 & 1 & 0 \\ \hline
  0 & 0 & 1 & 1 & 0 & 0 \\ \hline
  0 & 0 & 1 & 1 & 1 & 0 \\ \hline
  0 & 1 & 0 & 0 & 0 & 1 \\ \hline
  0 & 1 & 0 & 0 & 1 & 0 \\ \hline
  0 & 1 & 0 & 1 & 0 & 0 \\ \hline
  0 & 1 & 0 & 1 & 1 & 0 \\ \hline
  0 & 1 & 1 & 0 & 0 & 1 \\ \hline
  0 & 1 & 1 & 0 & 1 & 0 \\ \hline
  0 & 1 & 1 & 1 & 0 & 0 \\ \hline
  0 & 1 & 1 & 1 & 1 & 0 \\ \hline
  1 & 0 & 0 & 0 & 0 & 1 \\ \hline
  1 & 0 & 0 & 0 & 1 & 0 \\ \hline
  1 & 0 & 0 & 1 & 0 & 0 \\ \hline
  1 & 0 & 0 & 1 & 1 & 0 \\ \hline
  1 & 0 & 1 & 0 & 0 & 1 \\ \hline
  1 & 0 & 1 & 0 & 1 & 0 \\ \hline
  1 & 0 & 1 & 1 & 0 & 0 \\ \hline
  1 & 0 & 1 & 1 & 1 & 0 \\ \hline
  1 & 1 & 0 & 0 & 0 & 1 \\ \hline
  1 & 1 & 0 & 0 & 1 & 0 \\ \hline
  1 & 1 & 0 & 1 & 0 & 0 \\ \hline
  1 & 1 & 0 & 1 & 1 & 0 \\ \hline
  1 & 1 & 1 & 0 & 0 & 0 \\ \hline
  1 & 1 & 1 & 0 & 1 & 0 \\ \hline
  1 & 1 & 1 & 1 & 0 & 0 \\ \hline
  1 & 1 & 1 & 1 & 1 & 0 \\ \hline
\end{tabular}
\end{center}

La funci'on l'ogica del reloj7 ser'ia:
\begin{displaymath}
reloj7=\overline{Q_{4}} \cdot \overline{Q_{1}} \cdot
\overline{Q_{0}} + \overline{Q_{3}} \cdot \overline{Q_{1}} \cdot
\overline{Q_{0}} + \overline{Q_{2}} \cdot \overline{Q_{1}} \cdot
\overline{Q_{0}}
\end{displaymath}


Esta ser'ia la tabla de verdad para el reloj4:
\begin{center}
\begin{tabular}{|ccccc|c|}\hline
  $Q_{4}$ & $Q_{3}$ & $Q_{2}$ & $Q_{1}$ & $Q_{0}$ & $reloj4$\\ \hline \hline
  0 & 0 & 0 & 0 & 0 & 1 \\ \hline
  0 & 0 & 0 & 0 & 1 & 0 \\ \hline
  0 & 0 & 0 & 1 & 0 & 0 \\ \hline
  0 & 0 & 0 & 1 & 1 & 0 \\ \hline
  0 & 0 & 1 & 0 & 0 & 0 \\ \hline
  0 & 0 & 1 & 0 & 1 & 0 \\ \hline
  0 & 0 & 1 & 1 & 0 & 0 \\ \hline
  0 & 0 & 1 & 1 & 1 & 1 \\ \hline
  0 & 1 & 0 & 0 & 0 & 0 \\ \hline
  0 & 1 & 0 & 0 & 1 & 0 \\ \hline
  0 & 1 & 0 & 1 & 0 & 0 \\ \hline
  0 & 1 & 0 & 1 & 1 & 0 \\ \hline
  0 & 1 & 1 & 0 & 0 & 0 \\ \hline
  0 & 1 & 1 & 0 & 1 & 0 \\ \hline
  0 & 1 & 1 & 1 & 0 & 1 \\ \hline
  0 & 1 & 1 & 1 & 1 & 0 \\ \hline
  1 & 0 & 0 & 0 & 0 & 0 \\ \hline
  1 & 0 & 0 & 0 & 1 & 0 \\ \hline
  1 & 0 & 0 & 1 & 0 & 0 \\ \hline
  1 & 0 & 0 & 1 & 1 & 0 \\ \hline
  1 & 0 & 1 & 0 & 0 & 0 \\ \hline
  1 & 0 & 1 & 0 & 1 & 1 \\ \hline
  1 & 0 & 1 & 1 & 0 & 0 \\ \hline
  1 & 0 & 1 & 1 & 1 & 0 \\ \hline
  1 & 1 & 0 & 0 & 0 & 0 \\ \hline
  1 & 1 & 0 & 0 & 1 & 0 \\ \hline
  1 & 1 & 0 & 1 & 0 & 0 \\ \hline
  1 & 1 & 0 & 1 & 1 & 0 \\ \hline
  1 & 1 & 1 & 0 & 0 & 0 \\ \hline
  1 & 1 & 1 & 0 & 1 & 0 \\ \hline
  1 & 1 & 1 & 1 & 0 & 0 \\ \hline
  1 & 1 & 1 & 1 & 1 & 0 \\ \hline
\end{tabular}
\end{center}

La funci'on l'ogica del reloj4 ser'ia:
\begin{displaymath}
reloj4=\overline{Q_{4}} \cdot \overline{Q_{3}} \cdot
\overline{Q_{2}} \cdot \overline{Q_{1}} \cdot \overline{Q_{0}} +
\overline{Q_{4}} \cdot \overline{Q_{3}} \cdot Q_{2} \cdot Q_{1}
\cdot Q_{0} + \overline{Q_{4}} \cdot Q_{3} \cdot Q_{2} \cdot Q_{1}
\cdot \overline{Q_{0}} + Q_{4} \cdot \overline{Q_{3}} \cdot Q_{2}
\cdot \overline{Q_{1}} \cdot Q_{0}
\end{displaymath}

\section{Protocolos de transmisi'on}
El m'odulo codificador devuelve la palabra c'odigo como una serie
de bits en paralelo, sin embargo, nuestro canal es simplex y la
informaci'on se transmite en serie. Adem'as, debe haber un
sincronismo entre los relojes de los sistemas emisor y receptor.

El emisor env'ia una palabra de sincronizaci'on al inicio de la
trama que desea transmitir. Esta palabra de sincronizaci'on ser'a
1111 (codificada en Hamming ser'ia 1111111). El receptor se
sincroniza con cualquier palabra que comience en 1. Si se produce
un error en el primer bit enviado (m'as significativo de la
palabra Hamming 1111111) el receptor no se sincroniza, siendo
imposible la interpretaci'on correcta de los datos.

Conseguimos realizar una correcta comunicaci'on, con los m'odulos:
protocolo de env'io y protocolo de recepci'on.

\subsection{Protocolo de env'io}
Este m'odulo s'olo realiza la conversi'on de los datos en paralelo
que recibe del m'odulo codificador a serie, enviando 'estos al
canal de transmisi'on.

Puede verse en la implementaci'on f'isica de este m'odulo en la
l'amina 7.


\subsection{Protocolo de recepci'on}
Mientras se reciban 0's (el canal est'a a un nivel bajo de
voltaje), la entrada de habilitaci'on del flip--flop (flip--flop D
con entrada de habilitaci'on) estar'a activa. Al recibir el primer
1, la se\~nal de inicializaci'on se activa, e inmediatamente la
entrada de habilitaci'on del flip--flop queda desactivada para
siempre. Quedando almacenado en el flip--flop un uno, que
deshabilita la se\~nal de inicializaci'on.

En resumen, al recibir el primer uno, la se\~nal de
inicializaci'on adquiere un nivel alto durante un tiempo muy
peque\~no, que reinicia el contador asociado al reloj principal.

\section{C'odigo fuente de la implementaci'on}
\subsection{Contador de 0 hasta 6}
\subsubsection{h\_contador\_06.h}
\begin{verbatim}
/* CONTADOR DESDE 0 HASTA 6 */ /* L'amina 4 */


class CONTADOR_06{
  NEG_JK_FF_PC f[3];
  WIRE Q0n,Q1n,Q2n;
  WIRE t[3];
  AND a[1];
  OR o[2];
public:
  void run(WIRE &reset, WIRE &ck, WIRE &Q0, WIRE &Q1, WIRE &Q2,
  WIRE &voltaje, WIRE &tierra);
};
\end{verbatim}

\subsubsection{h\_contador\_06.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_06.h"


void CONTADOR_06::run(WIRE &reset, WIRE &ck, WIRE &Q0, WIRE
&Q1,WIRE &Q2, WIRE &voltaje, WIRE &tierra) {
  f[0].run(t[0],voltaje,ck,voltaje,reset,Q0,Q0n);
  f[1].run(Q0,t[1],ck,voltaje,reset,Q1,Q1n);
  f[2].run(t[2],Q1,ck,voltaje,reset,Q2,Q2n);

  o[0].run(t[0],Q2n,Q1n);
  o[1].run(t[1],Q0,Q2);
  a[0].run(t[2],Q0,Q1);
}
\end{verbatim}

\subsubsection{test\_h\_contador\_06.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_06.h"
#include "clock.h"
#include <stdio.h>

WIRE voltaje=VCC; WIRE tierra=GND;

void main() {
  int iter=500;
  WIRE c=tierra,Q0=tierra,Q1=tierra,Q2=tierra;
  CONTADOR_06 co;
  CLOCK clock(20);
  co.run(tierra,c,Q0,Q1,Q2,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,voltaje,tierra);
  while(iter--) {
    clock.run(iter,c);
    co.run(voltaje,c,Q0,Q1,Q2,voltaje,tierra);
    printf("%3d %3d %3d %3d\n",c,Q0,Q1,Q2);
  }
}
\end{verbatim}

\newpage
\subsection{Contador de 0 hasta 27}
\subsubsection{h\_contador\_027.h}
\begin{verbatim}
// CONTADOR DE 0 HASTA 27
// L'amina 6


class CONTADOR_027{
  NEG_JK_FF_PC f[5];
  WIRE Q0n,Q1n,Q2n,Q3n,Q4n;
  AND a[14];
  OR o[7];
  WIRE j[5];
  WIRE k[5];
  WIRE t[12];

public:
  void run(WIRE &clr, WIRE &ck, WIRE &Q0, WIRE &Q1, WIRE &Q2,
  WIRE &Q3, WIRE &Q4, WIRE &voltaje, WIRE &tierra);
};
\end{verbatim}

\subsubsection{h\_contador\_027.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_027.h"


void CONTADOR_027::run(WIRE &clr, WIRE &ck, WIRE &Q0, WIRE &Q1,
WIRE &Q2, WIRE &Q3, WIRE &Q4, WIRE &voltaje, WIRE &tierra){
  // L'ogica del flip-flop 0
  o[0].run(j[0],3,Q4n,Q3n,Q2n);
  f[0].run(j[0],voltaje,ck,voltaje,clr,Q0,Q0n);

  // L'ogica del flip-flop 1
  a[0].run(t[0],Q2n,Q0);
  a[1].run(t[1],Q3n,Q0);
  a[2].run(t[2],Q4n,Q0);
  o[1].run(j[1],3,t[0],t[1],t[2]);
  a[3].run(t[3],3,Q4,Q3,Q2);
  o[2].run(k[1],t[3],Q0);
  f[1].run(j[1],k[1],ck,voltaje,clr,Q1,Q1n);

  // L'ogica del flip-flop 2
  a[4].run(t[4],3,Q3n,Q1,Q0);
  a[5].run(t[5],3,Q4n,Q1,Q0);
  o[3].run(j[2],t[4],t[5]);
  a[6].run(t[6],Q1,Q0);
  a[7].run(t[7],Q4,Q3);
  o[4].run(k[2],t[6],t[7]);
  f[2].run(j[2],k[2],ck,voltaje,clr,Q2,Q2n);

  // L'ogica del flip-flop 3
  a[10].run(j[3],3,Q2,Q1,Q0);
  a[8].run(t[8],Q4,Q2);
  a[9].run(t[9],3,Q4,Q1,Q0);
  o[5].run(k[3],3,j[3],t[8],t[9]);
  f[3].run(j[3],k[3],ck,voltaje,clr,Q3,Q3n);

  // L'ogica del flip-flop 4
  a[12].run(t[10],3,Q3,Q1,Q0);
  a[13].run(j[4],t[10],Q2);
  a[11].run(t[11],Q3,Q2);
  o[6].run(k[4],t[10],t[11]);
  f[4].run(j[4],k[4],ck,voltaje,clr,Q4,Q4n);
}
\end{verbatim}

\subsubsection{test\_h\_contador\_027.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_027.h"
#include "clock.h"
#include <stdio.h>

WIRE voltaje=VCC; WIRE tierra=GND;

void main() {
  int iter=1000;
  WIRE c=0,Q0=0,Q1=0,Q2=0,Q3=0,Q4=0;
  CONTADOR_027 co;
  CLOCK clock(20);
  co.run(tierra,c,Q0,Q1,Q2,Q3,Q4,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,Q3,Q4,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,Q3,Q4,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,Q3,Q4,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,Q3,Q4,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,Q3,Q4,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,Q2,Q3,Q4,voltaje,tierra);
  while(iter--) {
    clock.run(iter,c);
    co.run(voltaje,c,Q0,Q1,Q2,Q3,Q4,voltaje,tierra);
    printf("%3d %3d %3d %3d %3d %3d\n",c,Q0,Q1,Q2,Q3,Q4);
  }
}
\end{verbatim}

\newpage
\subsection{Contador de 2 bits}
\subsubsection{h\_contador\_2bits.h}
\begin{verbatim}
// CONTADOR DE 2 BITS
// L'amina 9


class CONTADOR_2BITS{
  NEG_JK_FF_PC f[2];
  WIRE Q0n,Q1n;
public:
  void run(WIRE &reset, WIRE &ck, WIRE &Q0, WIRE &Q1,
  WIRE &voltaje, WIRE &tierra);
};
\end{verbatim}

\subsubsection{h\_contador\_2bits.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_2bits.h"


/* Contador de 2 bits */
void CONTADOR_2BITS::run(WIRE &reset,
WIRE &ck, WIRE &Q0, WIRE &Q1, WIRE &voltaje, WIRE &tierra) {
  f[0].run(voltaje,voltaje,ck,voltaje,reset,Q0,Q0n);
  f[1].run(Q0,Q0,ck,voltaje,reset,Q1,Q1n);
}
\end{verbatim}

\subsubsection{test\_h\_contador\_2bits.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_2bits.h"
#include "clock.h"
#include<stdio.h>

WIRE voltaje = VCC; WIRE tierra = GND;

void main() {
  int iter=5000;
  WIRE c=0,Q0=0,Q1=0;
  CONTADOR_2BITS co;
  CLOCK clock(50);

  co.run(tierra,c,Q0,Q1,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,voltaje,tierra);
  co.run(tierra,c,Q0,Q1,voltaje,tierra);

  while(iter--) {
    clock.run(iter,c);
    co.run(voltaje,c,Q0,Q1,voltaje,tierra);
    printf("%3d %3d %3d\n",c,Q0,Q1);
  }
}
\end{verbatim}

\newpage
\subsection{Reloj m'ultiple}
\subsubsection{h\_reloj.h}
\begin{verbatim}
// RELOJ MULTIPLE
// Lamina 5

class RELOJ{
  CONTADOR_027 contador;
  WIRE s[5];
  NOT n[5];
  AND a[7];
  OR o[2];
  WIRE t[11];
  WIRE ns[5];
  D_LATCH latch[2];

public:
  void run(WIRE &ck, WIRE &reset, WIRE &reloj4, WIRE &reloj7,
  WIRE &voltaje, WIRE &tierra);
};
\end{verbatim}

\subsubsection{h\_reloj.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_p_recibe.h"

void P_RECIBE::inicializa(WIRE &voltaje, WIRE &tierra){
  t[0] = tierra;
  t[1] = tierra;
  t[2] = tierra;
  t[3] = tierra;
  t[4] = tierra;
  t[5] = voltaje;
  t[6] = tierra;
  t[7] = voltaje;
}

void P_RECIBE::run(WIRE &entrada, WIRE &salida, WIRE
&inicializacion, WIRE &voltaje, WIRE &tierra) {
  latch[0].run(entrada,t[4],t[5]);
  latch[1].run(t[4],t[6],t[7]);

  n.run(t[2],t[1]);
  a.run(inicializacion,t[2],t[6]);
  f.run(entrada,t[0],t[1],Qn);
  na.run(t[0],t[6],t[2]);
  salida = t[6];
}
\end{verbatim}

\subsubsection{test\_h\_reloj.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_027.h"
#include "h_reloj.h"
#include"clock.h"
#include <stdio.h>


WIRE voltaje=VCC; WIRE tierra=GND;

void main() {
  int iter=5000;
  WIRE c=tierra,reloj7,reloj4;
  RELOJ reloj;
  CLOCK clock(20);
  reloj.run(tierra,tierra,reloj4,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,reloj4,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,reloj4,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,reloj4,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,reloj4,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,reloj4,reloj7,voltaje,tierra);
  while(iter--) {
    clock.run(iter,c);
    reloj.run(c,voltaje,reloj4,reloj7,voltaje,tierra);
    printf("%3d %3d %3d\n",c,reloj4,reloj7);
  }
}
\end{verbatim}

\newpage
\subsection{Retardo}
\subsubsection{h\_retardo.h}
\begin{verbatim}
// RETARDO DE PROPAGACI'ON DE 6 NIVELES
class RETARDO{
  NOT n[6];
  WIRE t[5];

public:
  void run(WIRE &salida, WIRE &entrada, WIRE &voltaje, WIRE &tierra);
};
\end{verbatim}

\subsubsection{h\_retardo.c}
\begin{verbatim}
#include "gates.h"
#include "h_retardo.h"

void RETARDO::run(WIRE &salida, WIRE &entrada, WIRE &voltaje, WIRE
&tierra) {
  n[0].run(t[0],entrada);
  n[1].run(t[1],t[0]);
  n[2].run(t[2],t[1]);
  n[3].run(t[3],t[2]);
  n[4].run(t[4],t[3]);
  n[5].run(salida,t[4]);
}
\end{verbatim}

\subsubsection{test\_h\_retardo.c}
\begin{verbatim}
#include "gates.h"
#include "clock.h"
#include "h_retardo.h"
#include <stdio.h>

WIRE voltaje=VCC; WIRE tierra=GND;

void main() {
  int iter=1000;
  WIRE  entrada=tierra,salida=tierra;
  CLOCK c(20);
  RETARDO ret;

  while(iter--) {
    c.run(iter,entrada);
    ret.run(salida,entrada,voltaje,tierra);
    printf("%3d %3d\n",entrada, salida);
  }
}
\end{verbatim}

\newpage
\subsection{Codificador Hamming}
\subsubsection{h\_codificador.h}
\begin{verbatim}
// CODIFICADOR HAMMING
// L'amina 1


class CODIFICADOR{
  CONTADOR_2BITS contador;
  NEG_D_FF f[11];
  AND a[12];
  XOR xo[3];
  AND na[1];
  WIRE Qn[11];
  WIRE t[25];
  RETARDO ret;
  D_LATCH latch;

public:
  void inicializa(WIRE &voltaje, WIRE &tierra);
  void run(WIRE &reset, WIRE &ck, WIRE &dato,
  WIRE &s0, WIRE &s1, WIRE &s2, WIRE &s3,
  WIRE &s4, WIRE &s5, WIRE &s6,
  WIRE &voltaje, WIRE &tierra);
};
\end{verbatim}

\subsubsection{h\_codificador.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_2bits.h"
#include "h_retardo.h"
#include"h_codificador.h"
#include <stdio.h>


void CODIFICADOR::inicializa(WIRE &voltaje, WIRE &tierra){
  for (int i=0;i<11;i++)
    Qn[i]=voltaje;

  for (int i=0;i<25;i++)
    t[i]=tierra;

}

void CODIFICADOR::run(WIRE &reset, WIRE &ck, WIRE &dato,
                      WIRE &s0, WIRE &s1, WIRE &s2, WIRE &s3, WIRE &s4, WIRE &s5, WIRE &s6,
                      WIRE &voltaje, WIRE &tierra){

  contador.run(reset,ck,t[20],t[21],voltaje,tierra);

  // registros de desplazamiento
  f[0].run(dato,ck,t[0],Qn[0]);
  f[1].run(t[0],ck,t[1],Qn[1]);
  f[2].run(t[1],ck,t[2],Qn[2]);
  f[3].run(t[2],ck,t[3],Qn[3]);

  // logica de codificaci'on
  xo[0].run(t[16],4,t[4],t[5],t[6],t[7]);
  a[0].run(t[4],t[3],tierra);
  a[1].run(t[5],t[2],voltaje);
  a[2].run(t[6],t[1],voltaje);
  a[3].run(t[7],t[0],voltaje);

  xo[1].run(t[17],4,t[8],t[9],t[10],t[11]);
  a[4].run(t[8],t[3],voltaje);
  a[5].run(t[9],t[2],tierra);
  a[6].run(t[10],t[1],voltaje);
  a[7].run(t[11],t[0],voltaje);

  xo[2].run(t[18],4,t[12],t[13],t[14],t[15]);
  a[8].run(t[12],t[3],voltaje);
  a[9].run(t[13],t[2],voltaje);
  a[10].run(t[14],t[1],tierra);
  a[11].run(t[15],t[0],voltaje);

  // control de la salida
  na[0].run(t[19],t[20],t[21]);
  latch.run(t[19],t[22],t[23]);

  ret.run(t[24],t[22],voltaje,tierra);

  f[4].run(t[3],t[24],s6,Qn[4]);
  f[5].run(t[2],t[24],s5,Qn[5]);
  f[6].run(t[1],t[24],s4,Qn[6]);
  f[7].run(t[0],t[24],s3,Qn[7]);
  f[8].run(t[16],t[24],s2,Qn[8]);
  f[9].run(t[17],t[24],s1,Qn[9]);
  f[10].run(t[18],t[24],s0,Qn[10]);

}
\end{verbatim}

\subsubsection{test\_h\_codificador.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_2bits.h"
#include "clock.h"
#include"h_retardo.h"
#include "h_codificador.h"
#include<stdio.h>

WIRE voltaje = VCC; WIRE tierra = GND;

void main (void){
  WIRE c = tierra;
  WIRE s0=tierra,s1=tierra,s2=tierra,s3=tierra,s4=tierra,
  s5=tierra,s6=tierra;
  int i,iter;

  CODIFICADOR codificador;
  CLOCK clock(30);

  WIRE entrada[600];

    for (i=0;i<60;i++)
    {
      entrada[i]=tierra;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+60]=tierra;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+120]=tierra;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+180]=voltaje;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+240]=tierra;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+300]=tierra;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+360]=voltaje;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+420]=voltaje;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+480]=voltaje;
    }

    for (i=0;i<60;i++)
    {
      entrada[i+540]=tierra;
    }

  codificador.inicializa(voltaje,tierra);
  codificador.run(tierra,c,entrada[0],s0,s1,s2,s3,s4,s5,s6,voltaje,tierra);
  codificador.run(tierra,c,entrada[0],s0,s1,s2,s3,s4,s5,s6,voltaje,tierra);
  codificador.run(tierra,c,entrada[0],s0,s1,s2,s3,s4,s5,s6,voltaje,tierra);
  codificador.run(tierra,c,entrada[0],s0,s1,s2,s3,s4,s5,s6,voltaje,tierra);
  codificador.run(tierra,c,entrada[0],s0,s1,s2,s3,s4,s5,s6,voltaje,tierra);
  codificador.run(tierra,c,entrada[0],s0,s1,s2,s3,s4,s5,s6,voltaje,tierra);

  for (iter = 0; iter < 600; iter++) {
    clock.run(iter,c);
    codificador.run(voltaje,c,entrada[iter],s0,s1,s2,s3,s4,s5,s6,
      voltaje,tierra);
    printf("%3d %3d   %3d %3d %3d %3d %3d %3d %3d\n",c,
      entrada[iter],s0,s1,s2,s3,s4,s5,s6);
  }
}
\end{verbatim}

\newpage
\subsection{Decodificador Hamming}
\subsubsection{h\_decodificador.h}
\begin{verbatim}
// DECODIFICADOR HAMMING
// L'amina 3


class DECODIFICADOR{
  CONTADOR_06 contador;
  NEG_D_FF f[11];
  AND a[25];
  XOR xo[7];
  AND na[1];
  WIRE Qn[11];
  NOT n[4];
  WIRE t[50];
  RETARDO ret;
  D_LATCH latch;

public:
  void inicializa(WIRE &voltaje, WIRE &tierra);
  void run(WIRE &reset, WIRE &ck, WIRE &dato,WIRE &s0, WIRE &s1,
  WIRE &s2, WIRE &s3,WIRE &voltaje, WIRE &tierra);
};
\end{verbatim}


\subsubsection{h\_decodificador.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_06.h"
#include "h_retardo.h"
#include"h_decodificador.h"


void DECODIFICADOR::inicializa(WIRE &voltaje, WIRE &tierra){
  for (int i=0;i<11;i++)
    Qn[i]=voltaje;

  for (int i=0;i<50;i++)
    t[i]=tierra;

  contador.run(tierra,tierra,t[42],t[43],t[44],voltaje,tierra);
  contador.run(tierra,tierra,t[42],t[43],t[44],voltaje,tierra);
  contador.run(tierra,tierra,t[42],t[43],t[44],voltaje,tierra);
  contador.run(tierra,tierra,t[42],t[43],t[44],voltaje,tierra);
  contador.run(tierra,tierra,t[42],t[43],t[44],voltaje,tierra);
  contador.run(tierra,tierra,t[42],t[43],t[44],voltaje,tierra);
}

void DECODIFICADOR::run(WIRE &reset, WIRE &ck, WIRE &dato,WIRE
&s0, WIRE &s1, WIRE &s2, WIRE &s3,WIRE &voltaje, WIRE &tierra){


  contador.run(reset,ck,t[42],t[43],t[44],voltaje,tierra);
  // registros de desplazamiento
  f[0].run(dato,ck,t[0],Qn[0]);
  f[1].run(t[0],ck,t[1],Qn[1]);
  f[2].run(t[1],ck,t[2],Qn[2]);
  f[3].run(t[2],ck,t[3],Qn[3]);
  f[4].run(t[3],ck,t[4],Qn[4]);
  f[5].run(t[4],ck,t[5],Qn[5]);
  f[6].run(t[5],ck,t[6],Qn[6]);

  // C'alculo del s'indrome
  xo[0].run(t[28],7,t[7],t[8],t[9],t[10],t[11],t[12],t[13]);
  a[0].run(t[7],t[6],tierra);
  a[1].run(t[8],t[5],tierra);
  a[2].run(t[9],t[4],tierra);
  a[3].run(t[10],t[3],voltaje);
  a[4].run(t[11],t[2],voltaje);
  a[5].run(t[12],t[1],voltaje);
  a[6].run(t[13],t[0],voltaje);

  xo[1].run(t[29],7,t[14],t[15],t[16],t[17],t[18],t[19],t[20]);
  a[7].run(t[14],t[6],tierra);
  a[8].run(t[15],t[5],voltaje);
  a[9].run(t[16],t[4],voltaje);
  a[10].run(t[17],t[3],tierra);
  a[11].run(t[18],t[2],tierra);
  a[12].run(t[19],t[1],voltaje);
  a[13].run(t[20],t[0],voltaje);

  xo[2].run(t[30],7,t[21],t[22],t[23],t[24],t[25],t[26],t[27]);
  a[14].run(t[21],t[6],voltaje);
  a[15].run(t[22],t[5],tierra);
  a[16].run(t[23],t[4],voltaje);
  a[17].run(t[24],t[3],tierra);
  a[18].run(t[25],t[2],voltaje);
  a[19].run(t[26],t[1],tierra);
  a[20].run(t[27],t[0],voltaje);

  // L'ogica de decodificaci'on
  n[0].run(t[31],t[28]);
  n[1].run(t[32],t[29]);
  n[2].run(t[33],t[30]);

  a[21].run(t[34],3,t[31],t[32],t[30]);
  a[22].run(t[35],3,t[31],t[29],t[33]);
  a[23].run(t[36],3,t[31],t[29],t[30]);
  a[24].run(t[37],3,t[28],t[32],t[33]);

  xo[3].run(t[38],t[34],t[6]);
  xo[4].run(t[39],t[35],t[5]);
  xo[5].run(t[40],t[36],t[4]);
  xo[6].run(t[41],t[37],t[3]);

  // control de la salida
  n[3].run(t[45],t[42]);
  na[0].run(t[46],3,t[43],t[44],t[45]);
  latch.run(t[46],t[47],t[48]);

  ret.run(t[49],t[47],voltaje,tierra);

  f[7].run(t[38],t[49],s3,Qn[7]);
  f[8].run(t[39],t[49],s2,Qn[8]);
  f[9].run(t[40],t[49],s1,Qn[9]);
  f[10].run(t[41],t[49],s0,Qn[10]);

}
\end{verbatim}

\subsubsection{test\_h\_decodificador.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_contador_06.h"
#include "clock.h"
#include"h_retardo.h"
#include "h_decodificador.h"
#include<stdio.h>

WIRE voltaje = VCC; WIRE tierra = GND;

void main (void){

WIRE c = tierra; WIRE s0=tierra,s1=tierra,s2=tierra,s3=tierra; int
i,iter;

DECODIFICADOR decodificador; CLOCK clock(10);

WIRE entrada[200];

  for (i=0;i<20;i++)
  {
        entrada[i]=voltaje;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+20]=tierra;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+40]=tierra;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+60]=voltaje;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+80]=voltaje;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+100]=tierra;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+120]=voltaje;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+140]=voltaje;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+160]=voltaje;

  }
  for (i=0;i<20;i++)
  {
        entrada[i+180]=voltaje;

  }

  decodificador.inicializa(voltaje,tierra);
  for (iter = 0; iter < 200; iter++) {
    clock.run(iter,c);
    decodificador.run(voltaje,c,entrada[iter],s0,s1,s2,s3,voltaje,tierra);
    printf("%3d %3d   %3d %3d %3d %3d\n",c,entrada[iter],s0,s1,s2,s3);
  }
}
\end{verbatim}

\newpage
\subsection{Protocolo de env'io}
\subsubsection{h\_p\_envio.h}
\begin{verbatim}
// PROTOCOLO DE ENV'IO
// L'amina 7

class P_ENVIO{
  CONTADOR_06 contador;
  WIRE t[3];
  MUX multiplexor;

public:
  void inicializa(WIRE &voltaje,WIRE &tierra);
  void run(WIRE &reset,WIRE datos[], WIRE &ck, WIRE &salida,
  WIRE &voltaje,WIRE &tierra);

};
\end{verbatim}

\subsubsection{h\_p\_envio.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "decods.h"
#include "muxs.h"
#include "h_contador_06.h"
#include "h_p_envio.h"


void P_ENVIO::inicializa(WIRE &voltaje, WIRE &tierra){
  multiplexor.create(3);
  t[0]=tierra;
  t[1]=tierra;
  t[2]=tierra;
}

void P_ENVIO::run(WIRE &reset, WIRE datos[], WIRE &ck, WIRE
&salida,WIRE &voltaje,WIRE &tierra){
  contador.run(reset,ck,t[0],t[1],t[2],voltaje,tierra);
  multiplexor.run(datos,t,salida);
}
\end{verbatim}


\subsubsection{test\_h\_p\_envio.c}
\begin{verbatim}
#include "gates.h"
#include "clock.h"
#include "latches.h"
#include "decods.h"
#include "flip-flops.h"
#include "muxs.h"
#include "h_contador_06.h"
#include "h_p_envio.h"
#include<stdio.h>

WIRE voltaje=VCC; WIRE tierra=GND;

void main() {
  int iter=420;
  WIRE s=tierra;
  WIRE c=tierra;
  WIRE v[8];
   v[0]=voltaje;
   v[1]=tierra;
   v[2]=voltaje;
   v[3]=tierra;
   v[4]=voltaje;
   v[5]=tierra;
   v[6]=voltaje;
   v[7]=tierra;

  P_ENVIO p;
  CLOCK clock(30);

  p.inicializa(voltaje,tierra);

  p.run(tierra,v,c,s,voltaje,tierra);
  p.run(tierra,v,c,s,voltaje,tierra);
  p.run(tierra,v,c,s,voltaje,tierra);
  p.run(tierra,v,c,s,voltaje,tierra);
  p.run(tierra,v,c,s,voltaje,tierra);
  p.run(tierra,v,c,s,voltaje,tierra);

  while(iter--) {
    clock.run(iter,c);
    p.run(voltaje,v,c,s,voltaje,tierra);
    printf("%3d %3d\n",c,s);
  }
}
\end{verbatim}

\newpage
\subsection{Protocolo de recepci'on}
\subsubsection{h\_p\_recibe.h}
\begin{verbatim}
// PROTOCOLO DE RECEPCI'ON
// L'amina 8

class P_RECIBE{
  NEG_D_FF f;
  NAND a;
  NAND na;
  NOT n;
  WIRE t[8];
  WIRE Qn;
  D_LATCH latch[2];

public:
  void inicializa(WIRE &voltaje, WIRE &tierra);
  void run(WIRE &entrada, WIRE &salida, WIRE &inicializacion,
  WIRE &voltaje, WIRE &tierra);
};
\end{verbatim}


\subsubsection{h\_p\_recibe.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_p_recibe.h"

void P_RECIBE::inicializa(WIRE &voltaje, WIRE &tierra){
  t[0] = tierra;
  t[1] = tierra;
  t[2] = tierra;
  t[3] = tierra;
  t[4] = tierra;
  t[5] = voltaje;
  t[6] = tierra;
  t[7] = voltaje;
}

void P_RECIBE::run(WIRE &entrada, WIRE &salida, WIRE
&inicializacion, WIRE &voltaje, WIRE &tierra) {
  latch[0].run(entrada,t[4],t[5]);
  latch[1].run(t[4],t[6],t[7]);

  n.run(t[2],t[1]);
  a.run(inicializacion,t[2],t[6]);
  f.run(entrada,t[0],t[1],Qn);
  na.run(t[0],t[6],t[2]);
  salida = t[6];
}
\end{verbatim}

\subsubsection{test\_h\_p\_recibe.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_retardo.h"
#include "h_p_recibe.h"
#include <stdio.h>


WIRE tierra = GND; WIRE voltaje = VCC;

void main() {
  int i;
  int iter;
  WIRE salida = tierra;
  WIRE ini = tierra;
  P_RECIBE pr;
  WIRE entrada[200];

  for (i=0;i<=19;i++)
  {
        entrada[i]=tierra;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+20]=tierra;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+40]=tierra;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+60]=voltaje;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+80]=tierra;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+100]=tierra;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+120]=voltaje;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+140]=voltaje;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+160]=voltaje;

  }
  for (i=0;i<=19;i++)
  {
        entrada[i+180]=tierra;

  }

  pr.inicializa(voltaje,tierra);
  for (iter = 0; iter < 200;iter++) {

    pr.run(entrada[iter],salida,ini,voltaje,tierra);

    printf("%3d %3d %3d\n",entrada[iter],salida,ini);
  }
}
\end{verbatim}

\newpage
\subsection{M'odulo emisor}
\subsubsection{h\_emisor.h}
\begin{verbatim}
// M'ODULO EMISOR
//

class EMISOR{
  WIRE t[7];
  WIRE reloj7;
  CODIFICADOR codificador;
  P_ENVIO p_envio;
  RELOJ reloj;

public:
  EMISOR(WIRE &voltaje, WIRE &tierra);
  void run(WIRE &reset, WIRE &ck, WIRE &entrada, WIRE &salida,
  WIRE &reloj4, WIRE &voltaje, WIRE &tierra);

};
\end{verbatim}

\subsubsection{h\_emisor.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "decods.h"
#include "muxs.h"
#include "h_retardo.h"
#include "h_contador_06.h"
#include "h_contador_2bits.h"
#include"h_contador_027.h"
#include "h_reloj.h"
#include"h_codificador.h"
#include "h_p_envio.h"
#include"h_emisor.h"




EMISOR::EMISOR(WIRE &voltaje, WIRE &tierra){
  WIRE s=tierra;

  for (int i = 0; i < 7; i++){
        t[i] = tierra;
  }

  codificador.inicializa(voltaje,tierra);
  codificador.run(tierra,tierra,tierra,t[0],t[1],t[2],t[3],t[4],t[5],
    t[6],voltaje,tierra);
  codificador.run(tierra,tierra,tierra,t[0],t[1],t[2],t[3],t[4],t[5],
    t[6],voltaje,tierra);
  codificador.run(tierra,tierra,tierra,t[0],t[1],t[2],t[3],t[4],t[5],
    t[6],voltaje,tierra);
  codificador.run(tierra,tierra,tierra,t[0],t[1],t[2],t[3],t[4],t[5],
    t[6],voltaje,tierra);
  codificador.run(tierra,tierra,tierra,t[0],t[1],t[2],t[3],t[4],t[5],
    t[6],voltaje,tierra);
  codificador.run(tierra,tierra,tierra,t[0],t[1],t[2],t[3],t[4],t[5],
    t[6],voltaje,tierra);

  p_envio.inicializa(voltaje,tierra);
  p_envio.run(tierra,t,tierra,s,voltaje,tierra);
  p_envio.run(tierra,t,tierra,s,voltaje,tierra);
  p_envio.run(tierra,t,tierra,s,voltaje,tierra);
  p_envio.run(tierra,t,tierra,s,voltaje,tierra);
  p_envio.run(tierra,t,tierra,s,voltaje,tierra);
  p_envio.run(tierra,t,tierra,s,voltaje,tierra);

  reloj.run(tierra,tierra,s,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,s,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,s,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,s,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,s,reloj7,voltaje,tierra);
  reloj.run(tierra,tierra,s,reloj7,voltaje,tierra);

  reloj7 = tierra;
}


void EMISOR::run(WIRE &reset, WIRE &ck, WIRE &entrada, WIRE
&salida, WIRE &reloj4, WIRE &voltaje, WIRE &tierra){
  reloj.run(ck,reset,reloj4,reloj7,voltaje,tierra);
  codificador.run(reset,reloj4,entrada,t[0],t[1],t[2],t[3],t[4],t[5],t[6],voltaje,tierra);
  p_envio.run(reset,t,reloj7,salida,voltaje,tierra);
}
\end{verbatim}

\subsubsection{test\_h\_emisor.c}
\begin{verbatim}
#include "gates.h"
#include "clock.h"
#include"latches.h"
#include"flip-flops.h"
#include "decods.h"
#include"muxs.h"
#include "h_retardo.h"
#include "h_contador_06.h"
#include"h_contador_2bits.h"
#include "h_contador_027.h"
#include"h_reloj.h"
#include "h_codificador.h"
#include"h_p_envio.h"
#include "h_emisor.h"
#include <stdio.h>


WIRE voltaje = VCC; WIRE tierra = GND;


void main (void){

  CLOCK clock(20);
  WIRE salida = tierra;
  WIRE reloj4 = tierra;
  WIRE c = tierra;

  EMISOR emisor(voltaje,tierra);

  int iter = 0;
  int k,n;

  WIRE dato[40];
    dato[0]=voltaje;
    dato[1]=tierra;
    dato[2]=voltaje;
    dato[3]=tierra;
    dato[4]=voltaje;
    dato[5]=tierra;
    dato[6]=voltaje;
    dato[7]=tierra;
    dato[8]=voltaje;
    dato[9]=tierra;
    dato[10]=voltaje;
    dato[11]=tierra;
    dato[12]=voltaje;
    dato[13]=tierra;
    dato[14]=voltaje;
    dato[15]=tierra;
    dato[16]=voltaje;
    dato[17]=tierra;
    dato[18]=voltaje;
    dato[19]=tierra;
    dato[20]=voltaje;
    dato[21]=tierra;
    dato[22]=voltaje;
    dato[23]=tierra;
    dato[24]=voltaje;
    dato[25]=tierra;
    dato[26]=voltaje;
    dato[27]=tierra;
    dato[28]=voltaje;
    dato[29]=tierra;
    dato[30]=voltaje;
    dato[31]=tierra;
    dato[32]=voltaje;
    dato[33]=tierra;
    dato[34]=voltaje;
    dato[35]=tierra;
    dato[36]=voltaje;
    dato[37]=tierra;
    dato[38]=voltaje;
    dato[39]=tierra;

  WIRE entrada[1600];
  for (k=0;k<40;k++)
    for (n=0;n<40;n++)
      entrada[n+(k*40)]=dato[k];

  emisor.run(tierra,tierra,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,tierra,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,tierra,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,tierra,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,tierra,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,tierra,entrada[0],salida,reloj4,voltaje,tierra);


  for (iter = 0; iter < 1600; iter++)
  {
     clock.run(iter,c);
     emisor.run(voltaje,c,entrada[iter],salida,reloj4,voltaje,tierra);
     //printf("%3d  %3d  %3d         %3d\n",c,entrada[iter],salida,reloj4);
  }
}
\end{verbatim}

\newpage
\subsection{M'odulo de recepci'on}
\subsubsection{h\_receptor.h}
\begin{verbatim}
// M'ODULO RECEPTOR
//

class RECEPTOR{
  WIRE t[2];
  WIRE reloj7;
  DECODIFICADOR decodificador;
  P_RECIBE p_recibe;
  RELOJ reloj;

public:
  RECEPTOR(WIRE &voltaje, WIRE &tierra);
  void run(WIRE &ck, WIRE &entrada, WIRE &s0, WIRE &s1, WIRE &s2,
  WIRE &s3, WIRE &voltaje, WIRE &tierra);

};
\end{verbatim}

\subsubsection{h\_receptor.c}
\begin{verbatim}
#include "gates.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_p_recibe.h"

void P_RECIBE::inicializa(WIRE &voltaje, WIRE &tierra){
  t[0] = tierra;
  t[1] = tierra;
  t[2] = tierra;
  t[3] = tierra;
  t[4] = tierra;
  t[5] = voltaje;
  t[6] = tierra;
  t[7] = voltaje;
}

void P_RECIBE::run(WIRE &entrada, WIRE &salida, WIRE
&inicializacion, WIRE &voltaje, WIRE &tierra) {
  latch[0].run(entrada,t[4],t[5]);
  latch[1].run(t[4],t[6],t[7]);

  n.run(t[2],t[1]);
  a.run(inicializacion,t[2],t[6]);
  f.run(entrada,t[0],t[1],Qn);
  na.run(t[0],t[6],t[2]);
  salida = t[6];
}
\end{verbatim}


\subsubsection{test\_h\_receptor.c}
\begin{verbatim}
#include "gates.h"
#include "clock.h"
#include "latches.h"
#include "flip-flops.h"
#include "h_retardo.h"
#include"h_contador_06.h"
#include "h_contador_027.h"
#include"h_reloj.h"
#include "h_decodificador.h"
#include"h_p_recibe.h"
#include "h_receptor.h"
#include <stdio.h>


WIRE voltaje = VCC; WIRE tierra = GND;


void main (void){

  CLOCK clock(30);
  WIRE c = tierra;
  WIRE s0=tierra, s1=tierra, s2=tierra, s3=tierra;

  RECEPTOR receptor(voltaje,tierra);

  int iter = 0;
  int k,n;

  WIRE dato[60];
    dato[0]=tierra;
    dato[1]=tierra;
    dato[2]=tierra;
    dato[3]=tierra;
    dato[4]=voltaje;
    dato[5]=voltaje;
    dato[6]=voltaje;
    dato[7]=voltaje;
    dato[8]=voltaje;
    dato[9]=voltaje;
    dato[10]=voltaje;
    dato[11]=voltaje;
    dato[12]=voltaje;
    dato[13]=voltaje;
    dato[14]=voltaje;
    dato[15]=voltaje;
    dato[16]=voltaje;
    dato[17]=voltaje;
    dato[18]=voltaje;
    dato[19]=voltaje;
    dato[20]=voltaje;
    dato[21]=voltaje;
    dato[22]=voltaje;
    dato[23]=voltaje;
    dato[24]=voltaje;
    dato[25]=voltaje;
    dato[26]=voltaje;
    dato[27]=voltaje;
    dato[28]=voltaje;
    dato[29]=voltaje;
    dato[30]=voltaje;
    dato[31]=voltaje;
    dato[32]=voltaje;
    dato[33]=voltaje;
    dato[34]=voltaje;
    dato[35]=voltaje;
    dato[36]=voltaje;
    dato[37]=voltaje;
    dato[38]=voltaje;
    dato[39]=voltaje;
    dato[40]=voltaje;
    dato[41]=voltaje;
    dato[42]=voltaje;
    dato[43]=voltaje;
    dato[44]=voltaje;
    dato[45]=voltaje;
    dato[46]=voltaje;
    dato[47]=voltaje;
    dato[48]=voltaje;
    dato[49]=voltaje;
    dato[50]=voltaje;
    dato[51]=voltaje;
    dato[52]=voltaje;
    dato[53]=voltaje;
    dato[54]=voltaje;
    dato[55]=voltaje;
    dato[56]=voltaje;
    dato[57]=voltaje;
    dato[58]=voltaje;
    dato[59]=voltaje;

  WIRE entrada[2400];
  for (k=0;k<60;k++)
    for (n=0;n<40;n++)
      entrada[n+(k*40)]=dato[k];

  for (iter = 0; iter < 2400; iter++)
  {
     clock.run(iter,c);
     receptor.run(c,entrada[iter],s0,s1,s2,s3,voltaje,tierra);
     printf("%3d  %3d       %3d  %3d  %3d %3d\n",c,entrada[iter],s0,s1,s2,s3);
  }
}
\end{verbatim}

\subsection{Entrenador general}
\begin{verbatim}
#include "gates.h"
#include "clock.h"
#include "latches.h"
#include "flip-flops.h"
#include "decods.h"
#include "muxs.h"
#include "h_retardo.h"
#include "h_contador_06.h"
#include"h_contador_2bits.h"
#include "h_contador_027.h"
#include"h_reloj.h"
#include "h_p_recibe.h"
#include"h_codificador.h"
#include "h_p_envio.h"
#include"h_decodificador.h"
#include "h_emisor.h"
#include"h_receptor.h"
#include <stdio.h>

WIRE voltaje = VCC; WIRE tierra = GND;


void main (void) {
  int iter = 0;
  int n=0;
  int k=0;

  WIRE s0 = tierra;
  WIRE s1 = tierra;
  WIRE s2 = tierra;
  WIRE s3 = tierra;

  EMISOR emisor(voltaje,tierra);
  RECEPTOR receptor(voltaje,tierra);


  WIRE c=tierra;
  WIRE salida=tierra;
  WIRE reloj4=tierra;

  CLOCK clock(30);

  WIRE dato[80];


  dato[0]=voltaje;
  dato[1]=voltaje;
  dato[2]=voltaje;
  dato[3]=voltaje;
  dato[4]=voltaje;
  dato[5]=voltaje;
  dato[6]=voltaje;
  dato[7]=voltaje;
  dato[8]=voltaje;
  dato[9]=voltaje;
  dato[10]=tierra;
  dato[11]=tierra;
  dato[12]=tierra;
  dato[13]=tierra;
  dato[14]=tierra;
  dato[15]=tierra;
  dato[16]=tierra;
  dato[17]=tierra;
  dato[18]=voltaje;
  dato[19]=voltaje;
  dato[20]=voltaje;
  dato[21]=voltaje;
  dato[22]=voltaje;
  dato[23]=voltaje;
  dato[24]=voltaje;
  dato[25]=voltaje;
  dato[26]=voltaje;
  dato[27]=voltaje;
  dato[28]=voltaje;
  dato[29]=voltaje;
  dato[30]=voltaje;
  dato[31]=voltaje;
  dato[32]=voltaje;
  dato[33]=voltaje;
  dato[34]=voltaje;
  dato[35]=voltaje;
  dato[36]=voltaje;
  dato[37]=voltaje;
  dato[38]=voltaje;
  dato[39]=voltaje;
  dato[40]=voltaje;
  dato[41]=voltaje;
  dato[42]=voltaje;
  dato[43]=voltaje;
  dato[44]=voltaje;
  dato[45]=voltaje;
  dato[46]=voltaje;
  dato[47]=voltaje;
  dato[48]=voltaje;
  dato[49]=voltaje;
  dato[50]=voltaje;
  dato[51]=voltaje;
  dato[52]=voltaje;
  dato[53]=voltaje;
  dato[54]=voltaje;
  dato[55]=voltaje;
  dato[56]=voltaje;
  dato[57]=voltaje;
  dato[58]=voltaje;
  dato[59]=voltaje;
  dato[60]=voltaje;
  dato[61]=voltaje;
  dato[62]=voltaje;
  dato[63]=voltaje;
  dato[64]=voltaje;
  dato[65]=voltaje;
  dato[66]=voltaje;
  dato[67]=voltaje;
  dato[68]=voltaje;
  dato[69]=voltaje;
  dato[70]=voltaje;
  dato[71]=voltaje;
  dato[72]=voltaje;
  dato[73]=voltaje;
  dato[74]=voltaje;
  dato[75]=voltaje;
  dato[76]=voltaje;
  dato[77]=voltaje;
  dato[78]=voltaje;
  dato[79]=voltaje;

  WIRE entrada[4800];
  for (k=0;k<80;k++)
    for (n=0;n<60;n++)
      entrada[n+(k*60)]=dato[k];

  emisor.run(tierra,c,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,c,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,c,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,c,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,c,entrada[0],salida,reloj4,voltaje,tierra);
  emisor.run(tierra,c,entrada[0],salida,reloj4,voltaje,tierra);


  for (iter = 0; iter < 4800; iter++)
  {
    clock.run(iter,c);
    emisor.run(voltaje,c,entrada[iter],salida,reloj4,voltaje,tierra);
    receptor.run(c,salida,s0,s1,s2,s3,voltaje,tierra);
    printf("%3d %3d %3d          %3d %3d %3d %3d\n",c, entrada[iter],
      salida,s0,s1,s2,s3);
  }

}
\end{verbatim}







\appendix
\chapter{Teor'ia de c'odigos lineales} \label{A}
\section{Conceptos algebraicos fundamentales}
\subsection{Definiciones}
En esta secci'on se har'a una introducci'on al 'algebra binaria,
que es la que define las estructuras y operaciones sobre las que
m'as tarde basaremos la construcci'on de los c'odigos lineales.

Primeramente, definiremos los conceptos de \emph{grupo} y
\emph{cuerpo} para describir los \textbf{cuerpos de Galois}, y
m'as tarde enumeraremos sus principales propiedades.

Sea $G$ un conjunto gen'erico de elementos:

Diremos que\ldots
\begin{itemize}
  \item $G$ es un \textbf{grupo} $\Leftrightarrow$
  \begin{enumerate}
     \item Tiene definida la operaci'on binaria: $\ast$.
     \item La operaci'on $\ast$ es asociativa: $\forall a,b,c \in G,
     a \ast (b+c)=a \ast b+a \ast c$.
     \item Existe elemento neutro: $\exists e \in G \textrm{ tal que } \forall a \in G,a \ast e=e \ast a$.
     \item Existe elemento inverso: $\forall a \in G, \exists
     a' \in G \textrm{ tal que } a \ast a'=e$.
  \end{enumerate}

  \item $G$ es un \textbf{grupo conmutativo} $\Leftrightarrow$
  \begin{enumerate}
     \item $\forall a,b \in G,a \ast b=b \ast a$.
     \item $(G, \ast )$ es un grupo.
  \end{enumerate}
\end{itemize}

Sea ahora $F$ otro conjunto de elementos, con dos operaciones: $+$
y $\cdot$.

Diremos que\ldots
\begin{itemize}
  \item $F$ es un \textbf{cuerpo} $\Leftrightarrow$
  \begin{enumerate}
     \item $F$ es un \textbf{grupo conmutativo} bajo la operaci'on
     $+$.
     \item $\forall a \in F,a \neq 0 \Rightarrow aF$ es un grupo
     conmutativo para la operaci'on $\cdot$.
     \item La operaci'on $\cdot$ es distributiva con respecto a
     $+$: $\forall a,b \in G,a \cdot (b+c)=a \cdot b+a \cdot c$.
  \end{enumerate}

  \item $F$ es un \textbf{cuerpo de Galois} $\Leftrightarrow$
  \begin{enumerate}
     \item $F$ es un cuerpo.
     \item El alfabeto de $F$ es finito.
  \end{enumerate}
\end{itemize}

Concretemos ahora las definiciones generales anteriores para el
caso que nos interesa, el 'algebra binaria:
\begin{itemize}
  \item El alfabeto fuente de nuestros conjuntos es ahora
  $A=(0,1)$.
  \item Las operaciones $+$ (XOR) y $\cdot$ (AND) quedan definidas
  de la siguiente forma:

  \begin{center}
  \begin{tabular}{|c|c|c|} \hline
    $\mathbf{+}$ & \textbf{0} & \textbf{1} \\ \hline
    \textbf{0} & 0 & 1 \\ \hline
    \textbf{1} & 1 & 0 \\ \hline
  \end{tabular}
  \begin{tabular}{|c|c|c|} \hline
    $\mathbf{\cdot}$ & \textbf{0} & \textbf{1} \\ \hline
    \textbf{0} & 0 & 0 \\ \hline
    \textbf{1} & 0 & 1 \\ \hline
  \end{tabular}
  \end{center}
\end{itemize}

Se puede demostrar, por lo tanto, que el conjunto $A=(0,1)$ junto
con las operaciones anteriores cumplen las condiciones necesarios
para construir un \emph{cuerpo de Galois} $GF(2)$.

\subsection{Propiedades de GF(2)}
\begin{enumerate}
  \item Sea $\mathbf{V_{n}}$ un conjunto de n--tuplas en la forma
  $\vec{v}=(v_{1},\ldots,v_{n})$ y donde $v_{i} \in
  GF(2)$. Las operaciones $+$ y $\cdot$ quedan as'i definidas:
  \begin{itemize}
     \item $\vec{v}+
     \vec{u}=\vec{w}$, donde
     $w_{i}=v_{i}+u_{i}$.
     \item $a \cdot \vec{v}=\vec{w}$, donde
     $w_{i}=a \cdot v_{i}$.
  \end{itemize}

  El conjunto $\mathbf{V_{n}}$ es un \emph{espacio vectorial} sobre $GF(2)$
  con $2^{n}$ elementos y de dimensi'on $n$.

  \item Sea $S\subseteq \mathbf{V_{n}}$. Diremos que es un subespacio
  vectorial suyo $\Leftrightarrow$
  \begin{itemize}
     \item $\emptyset \in S$.
     \item $\forall \vec{u},\vec{v} \in S,(\vec{u} +
     \vec{v}) \in S$. Esta propiedad va a resultar
     especialmente importante para nuestros c'odigos.
     \item $(a \cdot \vec{u}) \in S, \forall a \in
     GF(2) \textrm{ y } \forall \vec{u} \in S$.
  \end{itemize}

  \item Diremos que los vectores $\vec{v_{1}},\ldots,\vec{v_{n}}$
  son linealmente independientes $\Leftrightarrow \textrm{no } \exists c_{1},\ldots,c_{n} \in GF(2) \textrm{ tal que } c_{1} \cdot \vec{v_{1}}+ \ldots + c_{n} \cdot \vec{v_{n}}=\emptyset \textrm{ y } (c_{1},\ldots,c_{n})\neq
  \emptyset$.

  \item El conjunto de vectores $\{ \vec{g_{1}},\ldots,\vec{g_{n}}
  \}$ genera el espacio vectorial $\mathbf{V_{n}}\Leftrightarrow\forall
  \vec{v} \in \mathbf{V_{n}}, \vec{v}=\sum_{i=1}^n(c_{i} \cdot
  \vec{g_{i}})$.

  \item $\forall \mathbf{V_{n}}, \exists \{\vec{g_{1}},\ldots,\vec{g_{n}}
  \} \in \mathbf{V_{n}}$ y linealmente independientes que generan es
  espacio $\mathbf{V_{n}}$.

  \item Si $k>m$ y $\{ \vec{v_{1}},\ldots,\vec{v_{n}} \} \in
  \mathbf{V_{n}}$ son linealmente independientes, entonces el
  conjunto definido como $\mathbf{S}=\{ \vec{u} \textrm{ tal que}
  \vec{v}=\sum_{i=1}^{n}(c_{i} \cdot \vec{v_{i}}) \} \in
  \mathbf{V_{n}}$ es un subespacio vectorial de $\mathbf{V_{n}}$.

  \item Se define la operaci'on \emph{producto interior} de dos
  vectores de la siguiente forma: $\vec{a} \cdot
  \vec{b}=\sum_{i=1}^{n}(a_{i} \cdot b_{i})$. Seg'un esta operaci'on
  diremos que:
  \begin{itemize}
     \item $\vec{u}$ y $\vec{v}$ son ortogonales $\Leftrightarrow
     \vec{u} \cdot \vec{v}=0$.
     \item El \textbf{espacio vectorial dual} de $\mathbf{S}$
     (subespacio vectorial de dimensi'on $k$ de $V_{n}$) es el
     conjunto $\mathbf{S_{d}}$ cuyos elementos son todos los
     vectores ortogonales a los vectores $\vec{v} \in S$. Se dice
     que es un espacio dual de orden $(n-k)$.
  \end{itemize}
\end{enumerate}

%-----------------------------------------------------
\section{Introducci'on a los c'odigos bloque lineales}
Asumimos que la salida de una fuente de informaci'on es una
secuencia de d'igitos binarios ``0'' 'o ``1''. En la
\emph{codificaci'on de bloque}, esta secuencia de informaci'on
binaria es segmentada en bloques de mensajes de una longitud fija;
cada bloque de mensaje, llamado $u$, est'a formado por $k$
d'igitos de informaci'on. Hay un total de $2^k$ mensajes
distintos.

El codificador, de acuerdo con ciertas reglas, transforma cada
mensaje entrante $u$ en una n--tupla binaria $v$ con $n>k$. Esta
n--tupla binaria $v$ es lo que llamamos \emph{palabra c'odigo} (o
vector c'odigo) del mensaje $u$. Por lo tanto, para los $2^k$
posibles mensajes, hay $2^k$ palabras c'odigo. A este conjunto de
$2^k$ palabras c'odigo se le llama \textbf{c'odigo bloque}. Para
que un c'odigo bloque sea 'util, las $2^k$ palabras c'odigo deben
ser distintas. En consecuencia, tiene que haber una
correspondencia uno a uno entre un mensaje $u$ y su palabra
c'odigo $v$.

Para un c'odigo con $2^k$ palabras c'odigo de longitud $n$, a
menos que tenga una estructura especial, el aparato de
codificaci'on ser'a prohibitivamente complejo si $k$ y $n$ son
grandes, ya que tiene que almacenar las $2^k$ palabras c'odigo de
longitud $n$ en un diccionario. Por lo tanto, debemos restringir
nuestra atenci'on a c'odigos de bloque que pueden ser mecanizados
de una manera pr'actica. Una estructura que se desea que tenga un
c'odigo bloque es la \textbf{linealidad}. Con esta estructura, la
complejidad de la codificaci'on se reduce enormemente, como
veremos m'as adelante.

\subsection{Definici'on de c'odigo bloque lineal}
A un c'odigo bloque de longitud $n$ y $2^k$ palabras c'odigo se le
llama �\emph{c'odigo lineal $(n,k)$} si y s'olo si sus $2^k$
palabras c'odigo forman un subespacio k--dimensional del espacio
vectorial de las n--tuplas sobre el campo GF(2).

De hecho, un c'odigo binario es lineal si y s'olo si la suma
m'odulo 2 de dos palabras c'odigo es tambi'en una palabra c'odigo.
El bloque c'odigo dado en la siguiente tabla es un c'odigo lineal
(7,4). Se puede comprobar f'acilmente que la suma de dos palabras
c'odigo es tambi'en otra palabra c'odigo.
\begin{table}[!h] \label{tabla1}
\begin{center}
\begin{tabular}{|c|c|} \hline
  \textbf{Mensajes} & \textbf{Palabras c'odigo} \\ \hline \hline
  (0 0 0 0) & (0 0 0 0 0 0 0) \\ \hline
  (1 0 0 0) & (1 1 0 1 0 0 0) \\ \hline
  (0 1 0 0) & (0 1 1 0 1 0 0) \\ \hline
  (1 1 0 0) & (1 0 1 1 1 0 0) \\ \hline
  (0 0 1 0) & (1 1 1 0 0 1 0) \\ \hline
  (0 1 1 0) & (0 0 1 1 0 1 0) \\ \hline
  (1 1 1 0) & (1 0 0 0 1 1 0) \\ \hline
  (0 0 0 1) & (0 1 0 1 1 1 0) \\ \hline
  (1 0 0 1) & (1 0 1 0 0 0 1) \\ \hline
  (0 1 0 1) & (0 1 1 1 0 0 1) \\ \hline
  (1 1 0 1) & (1 1 0 0 1 0 1) \\ \hline
  (0 0 1 1) & (0 1 0 0 0 1 1) \\ \hline
  (1 0 1 1) & (1 0 0 1 0 1 1) \\ \hline
  (0 1 1 1) & (0 0 1 0 1 1 1) \\ \hline
  (1 1 1 1) & (1 1 1 1 1 1 1) \\ \hline
\end{tabular}
\end{center}
\caption{Ejemplo de c'odigo lineal (7,4)}
\end{table}

Dado que un c'odigo lineal $(n,k)$ $C$ es un subespacio
k--dimensional del espacio de vectores $V_{n}$ de las n--tuplas
binarias, es posible encontrar $k$ palabras c'odigo linealmente
independientes ($g_{0},g_{1},\ldots,g_{k-1}$) en $C$, de tal forma
que cada palabra c'odigo $v$ en $C$ es una combinaci'on lineal de
esas $k$ palabras c'odigo. Por tanto, $v=u_{0}g_{0}+u_{1}g_{1}+
\ldots +u_{k-1}g_{k-1}$, donde $u_{i}=0 \vee 1$ para $0 \leq i
\leq k$.

Ahora vamos a colocar estas $k$ palabras c'odigo linealmente
independientes como las filas de una matriz $k \times n$:
\begin{displaymath}
G=\left( \begin{array}{c}
g_{0} \\
g_{1} \\
\vdots \\
g_{k-1}
\end{array} \right)
= \left( \begin{array}{cccc}
g_{0,0} & g_{0,1} & \ldots & g_{0,n-1} \\
g_{1,0} & g_{1,1} & \ldots & g_{1,n-1} \\
\vdots & \vdots & \ddots & \vdots \\
g_{k-1,0} & g_{k-1,1} & \ldots & g_{k-1,n-1} \\
\end{array} \right)
\end{displaymath}

Si $u=(u_{0},u_{1},\ldots,u_{k-1})$ es el mensaje que va a ser
codificado, la palabra c'odigo correspondiente puede ser dada de
la siguiente manera:
\begin{displaymath}
v=u \cdot G=u \cdot \left( \begin{array}{c}
g_{0} \\
g_{1} \\
\vdots \\
g_{k-1}
\end{array} \right)
= u_{0}g_{0}+u_{1}g_{1}+\ldots+u_{k-1}g_{k-1}
\end{displaymath}

Evidentemente las filas de $G$ generan el c'odigo lineal $(n,k)$
$C$. Por esta raz'on a la matriz $\mathbf{G}$ se le llama
\textbf{matriz generadora} de $C$. N'otese que cualquier conjunto
de $k$ palabras c'odigo linealmente independientes pueden ser
usadas para formar una matriz generadora del c'odigo. Por lo
tanto, un c'odigo lineal $(n,k)$ est'a completamente definido por
las $k$ filas de la matriz generadora $G$. Como consecuencia de
esto, el codificador s'olo tiene que almacenar las $k$ filas de
$G$ y formar una combinaci'on lineal de estas $k$ filas basada en
el mensaje de entrada $u$.

\begin{ejemplo} \label{ejemplo1}
El c'odigo lineal $(7,4)$ dado en la tabla \ref{tabla1} tiene la
siguiente matriz generadora:
\begin{displaymath}
G=\left( \begin{array}{c}
g_{0} \\
g_{1} \\
g_{2} \\
g_{3}
\end{array} \right)
= \left( \begin{array}{ccccccc}
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 1 \\
\end{array} \right)
\end{displaymath}

Sea $u=(1 1 0 1)$ el mensaje que hay que codificar, su palabra
c'odigo correspondiente ser'a: $v=1 \cdot g_{0} + 1 \cdot g_{1} +
0 \cdot g_{2} + 1 \cdot g_{3}= (1 1 0 1 0 0 0) + (0 1 1 0 1 0 0) +
(1 0 1 0 0 0 1) = (0 0 0 1 1 0 1)$
\end{ejemplo}

\subsection{Forma sistem'atica}
Una propiedad deseable en un c'odigo lineal es una estructura
sistem'atica donde una palabra c'odigo se divide en dos partes: la
parte del \emph{mensaje} y la parte de \emph{redundancia}. La
parte del mensaje consiste en $k$ bits de informaci'on inalterada
(o mensaje); y la parte de redundancia consiste de $(n-k)$ bits de
comprobaci'on de paridad, los cuales son una suma lineal de los
bits de informaci'on. A un c'odigo lineal de bloque con esta
estructura se le llama \textbf{c'odigo lineal sistem'atico de
bloque}. El c'odigo $(7,4)$ dado en la tabla \ref{tabla1} es un
c'odigo sistem'atico, los cuatro bits que est'an m'as a la derecha
de cada palabra�c'odigo son id'enticos a los bits correspondientes
de informaci'on.

\begin{center}
\begin{tabular}{|c|c|} \hline
  \textbf{REDUNDANCIA} & \textbf{MENSAJE} \\ \hline \hline
  $n-k$ d'igitos & $k$ d'igitos \\ \hline
\end{tabular}
\end{center}

Un c'odigo lineal $(n,k)$ sistem'atico queda completamente
definido por una matriz $G$ $k \times n$ de la siguiente forma:
\begin{displaymath}
\label{matrizG}
G=\left( \begin{array}{c}
g_{0} \\
g_{1} \\
\vdots \\
g_{k-1}
\end{array} \right)
= \left( \begin{array}{cccc|ccccc}
p_{0,0} & p_{0,1} & \ldots & p_{0,n-k-1} & 1 & 0 & 0 & \ldots & 0\\
p_{1,0} & p_{1,1} & \ldots & p_{1,n-k-1} & 0 & 1 & 0 & \ldots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\
p_{k-1,0} & p_{k-1,1} & \ldots & p_{k-1,n-k-1} & 0 & 0 & 0 & \ldots & 1\\
\end{array} \right)
\end{displaymath}

Si llamamos $I_{k}$ a la matriz identidad de dimensi'on $k$
observamos que $G=[PI_{k}]$. Como $u=(u_{0},u_{1},\ldots,u_{k-1})$
es el mensaje que hay que codificar, entonces la palabra c'odigo
correspondiente es
$v=(v_{0},v_{1},\ldots,v_{n-1})=(u_{0},u_{1},\ldots,u_{k-1})G$.

Por tanto, podemos decir que las componentes de $v$ son:
\begin{itemize}
  \item $v_{n-k+i}=u_{i}$ con $0 \leq i<k$.
  \item $v_{j}=u_{0}p_{0,j}+u_{1}p_{1j}+ \ldots +u_{k-1}p_{k-1,j}$
  con $0 \leq j<(n-k)$.
\end{itemize}

Esto nos demuestra que los $k$ primeros d'igitos por la derecha de
una palabra c'odigo $v$ son id'enticos a los d'igitos informaci'on
$u_{0},u_{1}, \ldots ,u_{k-1}$ que hay que codificar, y que los
$n-k$ d'igitos de redundancia que est'an a la izquierda son sumas
lineales de los de informaci'on.

\begin{ejemplo} \label{ejemplo2}
La matriz $G$ dada en el ejemplo anterior de la p'agina
\pageref{ejemplo1} est'a en forma sistem'atica. Si
$u=(u_{0},u_{1},u_{2},u_{3})$ es el mensaje que hay que codificar,
y $v=(v_{0},v_{1},v_{2},v_{3},v_{4},v_{5},v_{6})$ es la
correspondiente palabra c'odigo, entonces:
\begin{displaymath}
v=u \cdot \left(
\begin{array}{ccccccc}
1 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 1 \\
\end{array} \right)
\end{displaymath}

Multiplicando las matrices obtenemos los d'igitos de la palabra
c'odigo $v$:
\begin{displaymath}
\begin{array}{l}
v_{6}=u_{3} \\
v_{5}=u_{2} \\
v_{4}=u_{1} \\
v_{3}=u_{0} \\
v_{2}=u_{1}+u_{2}+u_{3} \\
v_{1}=u_{0}+u_{1}+u_{2} \\
v_{0}=u_{0}+u_{2}+u_{3} \\
\end{array}
\end{displaymath}

Por lo tanto, la palabra c'odigo correspondiente a $(1 0 1 1)$ es
$(1 0 0 1 0 1 1)$.
\end{ejemplo}

\subsection{Matriz de comprobaci'on de paridad}
Existe otra matriz 'util asociada con cada c'odigo lineal de
bloque. Para cada matriz $\mathbf{G}$ de dimensiones $k \times n$
con $k$ filas linealmente independientes, existe una matriz
$\mathbf{H}$ de dimensiones $(n-k) \times n$ con $n-k$ filas
linealmente independientes de tal manera que cada vector en el
espacio de las filas de $\mathbf{G}$ es ortogonal a las filas de
$\mathbf{H}$. Adem'as, cada vector que es ortogonal a las filas de
$\mathbf{H}$ est'a en el espacio de las filas de $\mathbf{G}$.
Como consecuencia de esto podemos describir el c'odigo lineal
$(n,k)$ generado por $\mathbf{G}$ de otra forma alternativa que a
continuaci'on se detalla.

Una n--tupla $v$ es una palabra c'odigo en el c'odigo generado por
$G$ si y s'olo si $v\mathbf{H}^T=0$. Esta matriz $\mathbf{H}$ es
la \textbf{matriz de comprobaci'on de paridad} del c'odigo. Las
$2^{n-k}$ combinaciones lineales de las filas de la matriz
$\mathbf{H}$ forman un c'odigo lineal $C_{d}$ $(n,n-k)$. Este
c'odigo es el espacio nulo del c'odigo lineal $C$ $(n,k)$ generado
por la matriz $\mathbf{G}$, esto significa que para cualquier
$\forall v \in C \wedge \forall w \in C_{d}, vw=0$. $C_{d}$ es el
\textbf{c'odigo dual} de $C$. Por lo tanto, una matriz de
comprobaci'on de paridad de un c'odigo lineal $C$ es la matriz
generadora de su c'odigo dual.

Si la matriz generadora de un c'odigo lineal $(n,k)$ est'a en la
forma sistem'atica, la matriz de comprobaci'on de paridad tiene la
siguiente forma:
\begin{displaymath}
\label{matrizH}
H=[I_{n-k}P^T]= \left( \begin{array}{ccccccccc}
1 & 0 & 0 & \ldots & 0 & p_{0,0} & p_{0,1} & \ldots & p_{0,n-k-1} \\
0 & 1 & 0 & \ldots & 0 & p_{1,0} & p_{1,1} & \ldots & p_{1,n-k-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \ldots & 1 & p_{k-1,0} & p_{k-1,1} & \ldots & p_{k-1,n-k-1} \\
\end{array} \right)
\end{displaymath}

Donde $P^T$ es la traspuesta de la matriz $P$. Sea $h_{j}$ la
j--'esima fila de $H$. Podemos comprobar que el producto de la
i--'esima fila de $G$ definida en la p'agina \pageref{matrizG} y
la j--'esima fila de $H$ anterior es $g_{i}h_{j}=p_{ij}+p_{ij}=0$
con $0 \leq j<(n-k)$.

Esto implica que $\mathbf{GH^T=0}$. Adem'as, las $n-k$ filas de
$\mathbf{H}$ son linealmente independientes. Por lo tanto, la
matriz $\mathbf{H}$ es una matriz de comprobaci'on de paridad del
c'odigo lineal generado por $\mathbf{G}$.

\section{S'indrome y detecci'on de errores}
Consideramos un c'odigo lineal $(n,k)$ con su matriz generadora
$G$ y su matriz de comprobaci'on de paridad $H$. Sea $v$ una
palabra c'odigo que se transmite en un canal ruidoso\footnote{Un
canal es ruidoso cuando la informaci'on de entrada puede sufrir
alguna modificaci'on resultando una salida distinta a la
esperada}, y $\mathbf{r}$ es el vector recibido a la salida del
canal. Debido a que el canal es ruidoso, $\mathbf{r}$ puede ser
distinto de $\mathbf{v}$.

\begin{figure}[!h]
\begin{center}
$v \longrightarrow$
\begin{tabular}{|c|} \hline
  CANAL \\ \hline
\end{tabular}
$\longrightarrow r$

$\uparrow$

$e$
\end{center}
\end{figure}

El vector suma de $\mathbf{r}$ y $\mathbf{v}$ es $\mathbf{e}$;
$\mathbf{e}$ es una n--tupla tal que $e_{i}=1$ si $r_{i} \neq
v_{i}$, y $e_{i}=0$ si $r_{i}=v_{i}$. A esta n--tupla se le llama
\textbf{vector de error}. Los 1's que aparecen en $\mathbf{e}$ son
errores de transmisi'on producidos porque el canal es ruidoso.

El receptor recibe $\mathbf{r}$, que es la suma de la palabra
c'odigo transmitida y el vector error. Cuando recibe $\mathbf{r}$,
el decodificador debe determinar si contiene errores de
transmisi'on. Si se detectan errores, el decodificador intentar'a
corregirlos (FEC) o pedir'a una retransmisi'on (ARQ).

Cuando se recibe $\mathbf{r}$, el decodificador calcula la
siguiente (n--k)--tupla:
$\mathbf{s}=rH^T=(s_{0},s_{1},\ldots,s_{n-k-1})$, esta
(n--k)--tupla es el \textbf{s'indrome} de $\mathbf{r}$.

Podemos afirmar que $\mathbf{s}=0$ si y s'olo si $r$ es una
palabra c'odigo (el receptor acepta $r$ como la palabra c'odigo
transmitida), y $\mathbf{s} \neq 0$ si y s'olo si $r$ no es una
palabra c'odigo (el receptor detecta la presencia de al menos un
error). Pero es posible que los errores no sean detectables, es
decir, que $r$ contenga errores pero $\mathbf{s}=0$. Esto sucede
cuando el vector de error es id'entico a una palabra c'odigo no
nula. En este caso, $r$ es la suma de dos palabras c'odigo y por
lo tanto el s'indrome es igual a cero. Estos errores son
\textbf{errores indetectables}. Como hay $2^{k}-1$ palabras
c'odigo no nulas, hay $2^{k}-1$ errores indetectables.

\begin{ejemplo} \label{ejemplo3}
Vamos a calcular el s'indrome del c'odigo cuya matriz de
comprobaci'on de paridad es la siguiente:
\begin{displaymath}
\mathbf{H}=\left( \begin{array}{ccccccc}
1 & 0 & 0 & 1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 & 1 & 1 & 1 \\
\end{array} \right)
\end{displaymath}

Si $\mathbf{r}=(r_{0},r_{1},r_{2},r_{3},r_{4},r_{5},r_{6})$ es el
vector recibido, el s'indrome se calcula de la siguiente manera:
\begin{displaymath}
\mathbf{s}=r \cdot \left( \begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 0 \\
0 & 1 & 1 \\
1 & 1 & 1 \\
1 & 0 & 1 \\
\end{array} \right)
\end{displaymath}

Con lo cual los d'igitos que componen el s'indrome son:
\begin{displaymath}
\begin{array}{c}
s_{0}=r_{0}+r_{3}+r_{5}+r_{6} \\
s_{1}=r_{1}+r_{3}+r_{5}+r_{6} \\
s_{2}=r_{2}+r_{4}+r_{5}+r_{6} \\
\end{array}
\end{displaymath}
\end{ejemplo}

Como se ha visto, el s'indrome depende s'olo del vector de error,
y no de la palabra c'odigo transmitida:
$s=rH^T=(v+e)H^T=vH^T+eH^T$, como $vH^T=0$ obtenemos la siguiente
expresi'on:
\begin{displaymath}
\mathbf{s=eH^T}
\end{displaymath}

Llegado a este punto, uno puede pensar que cualquier esquema de
correcci'on de errores consiste en resolver las $n-k$ ecuaciones
lineales dadas por la expresi'on anterior. Una vez que se
encuentra el error, se considera que el vector
$\mathbf{r}+\mathbf{e}$ es la palabra c'odigo transmitida.
Desgraciadamente, determinar cu'al es el verdadero vector de error
no es una cuesti'on sencilla. Esto es debido a que las $n-k$
ecuaciones lineales no tienen una soluci'on 'unica, sino que
tienen $2^k$ soluciones. En otras palabras, hay $2^k$ patrones de
error que dan el mismo s'indrome, y el verdadero error que se ha
producido es 'unicamente uno de ellos.

Para minimizar la probabilidad de error, se elige como vector de
error al patr'on de error m'as probable. Si el canal es
BSC\footnote{ BSC (binary simmetric channel): Es un canal ruidoso
en el que la probabilidad de que un 1 se transforme en 0 es igual
a la probabilidad de que un 0 se transforme en 1. Adem'as, si la
probabilidad de que ocurra un error es $p$, la posibilidad de que
se produzcan dos errores es $p^2$.}, el vector m'as probable es el
que tiene el mayor n'umero de ceros.

\begin{ejemplo} \label{ejemplo4}
Consideramos el c'odigo $(7,4)$ dado en el ejemplo anterior de la
p'agina \pageref{ejemplo3}. Si $v=(1 0 0 1 0 1 1)$ es la palabra
c'odigo transmitida y $r=(1 0 0 1 0 0 1)$ es el vector recibido.
El receptor calcula el s'indrome: $s=rH^T=(1 1 1)$.

Una vez hecho esto, el receptor intenta determinar el verdadero
vector de error $\mathbf{e}$. Los d'igitos de error est'an
relacionados con los del s'indrome por las siguientes ecuaciones
lineales:
\begin{displaymath}
\begin{array}{l}
1=e_{0}+e_{3}+e_{5}+e_{6} \\
1=e_{1}+e_{3}+e_{4}+e_{5} \\
1=e_{2}+e_{4}+e_{5}+e_{6} \\
\end{array}
\end{displaymath}

Hay $2^4=16$ patrones de error que satisfacen las ecuaciones de
arriba. Son:
\begin{displaymath}
\begin{array}{cc}
  (0 0 0 0 0 1 0) & (1 0 1 0 0 1 1) \\
  (1 1 0 1 0 1 0) & (0 1 1 1 0 1 1) \\
  (0 1 1 0 1 1 0) & (1 1 0 0 1 1 1) \\
  (1 0 1 1 1 1 0) & (0 0 0 1 1 1 1) \\
  (1 1 1 0 0 0 0) & (0 1 0 0 0 0 1) \\
  (0 0 1 1 0 0 0) & (1 0 0 1 0 0 1) \\
  (1 0 0 0 1 0 0) & (0 0 1 0 1 0 1) \\
  (0 1 0 1 1 0 0) & (1 1 1 1 1 0 1) \\
\end{array}
\end{displaymath}

El vector de error $e=(0 0 0 0 0 1 0)$ es el que tiene el menor
n'umero de componentes distintas de cero. Si el canal es BSC,
$e=(0 0 0 0 0 1 0)$ es el vector de error m'as probable de los que
satisfacen las ecuaciones anteriores. Si tomamos $e=(0 0 0 0 0 1
0)$ como el verdadero vector de error, el receptor decodifica el
vector $\mathbf{r}$ en la siguiente palabra c'odigo:
$v^{\ast}=r+e=(1 0 0 1 0 0 1)+(0 0 0 0 0 1 0)=(1 0 0 1 0 1 1)$.
Como se puede apreciar, $v^{\ast}$ es la palabra c'odigo
transmitida. Por lo tanto, el receptor ha hecho una
decodificaci'on correcta.
\end{ejemplo}

\section{Distancia m'inima de un c'odigo}
Tomamos una n--tupla $v=(v_{0},v_{1},\ldots,v_{n-1})$. El
\textbf{peso Hamming} (o simplemente peso) de $v$, que se denota
como $w(v)$, se define como el n'umero de componentes distintas de
cero de $v$. Por ejemplo, el peso de $v=(1 0 0 1 0 1 1)$ es 4.

Sean $v$ y $w$ dos n--tuplas, las \textbf{distancia Hamming} (o
simplemente distancia) entre $v$ y $w$, que se denota como
$d(v,w)$, se define como el n'umero de d'igitos en el mismo sitio
que tienen diferentes. Por ejemplo, la distancia Hamming entre
$v=(1 0 0 1 0 1 1)$ y $w=(0 1 0 0 0 1 1)$ es 3, tienen diferentes
las posiciones cero, uno y tres.

La distancia Hamming es una funci'on m'etrica que satisface la
\emph{desigualdad triangular}. Es decir, sean $v$, $w$ y $x$ tres
n--tuplas, entonces $d(u,w)+d(w,x) \geq d(v,x)$.

De todo esto se deduce que la distancia Hamming entre dos
n--tuplas, $v$ y $w$, es igual al peso Hamming de la suma de $v$ y
$w$, esto es, $d(v,w)=w(v+w)$. Por ejemplo, la distancia Hamming
entre $v=(1 0 0 0 1 0 1 1)$ y $w=(1 1 1 0 0 1 0)$ es 4, y el peso
de $v+w=(0 1 1 1 0 0 1)$ es tambi'en 4.

Dado un c'odigo bloque $C$, se puede calcular la distancia Hamming
entre cualquiera dos palabras c'odigo distintas. La
\textbf{distancia m'inima} de $C(d_{min})$ se define como
$d_{min}=min\{d(v,w):v,w \in C, v \neq w \}$.

Sea $C$ un c'odigo lineal, la suma de dos vectores es tambi'en un
vector c'odigo. Por lo tanto, la distancia Hamming entre dos
vectores c'odigo en $C$ es igual al peso Hamming de un tercer
vector c'odigo en $C$. De esto obtenemos que:
\begin{displaymath}
d_{min}=min\{d(v,w):v,w \in C, v \neq w\}=min\{w(x):x \in C, x
\neq 0\}=w_{min}
\end{displaymath}

$w_{min}$ es el \textbf{peso m'inimo} del c'odigo lineal $C$. De
lo cual obtenemos el siguiente teorema:

\newtheorem{teorema}{Teorema}
\begin{teorema} \label{t1}
La distancia m'inima de un c'odigo lineal bloque es igual al
m'inimo peso de sus palabras distintas de cero.
\end{teorema}

\begin{teorema} \label{t2}
Sea $C$ un c'odigo lineal $(n,k)$ con su matriz de comprobaci'on
de paridad $\mathbf{H}$. Para cada vector c'odigo de peso Hamming
1, existen 1 columnas de $\mathbf{H}$ tales que el vector suma de
esas columnas es igual al vector cero. Rec'iprocamente, si existen
1 columnas de $\mathbf{H}$ cuyo vector suma es el vector cero,
existe un vector c'odigo con peso Hamming 1 en $C$.
\end{teorema}

\newtheorem{corolario}{Corolario}
\begin{corolario} \label{c1}
Sea $C$ un c'odigo bloque lineal cuya matriz de comprobaci'on de
paridad es $\mathbf{H}$. Si $d-1$ o menos columnas de H suman 0,
el c'odigo tiene un peso m'inimo de por lo menos $d$.
\end{corolario}

\newtheorem{c2}{Corolario}
\begin{c2} \label{c2}
Sea $C$ un c'odigo bloque lineal cuya matriz de comprobaci'on de
paridad es $\mathbf{H}$. El peso m'inimo (o la m'inima distancia)
de $C$ es igual al menor n'umero de columnas de $\mathbf{H}$ que
suman 0.
\end{c2}

\begin{ejemplo} \label{ejemplo5}
Vamos a considerar el c'odigo lineal dado en la tabla de la
p'agina \pageref{tabla1}. Su matriz de comprobaci'on de paridad es
la siguiente:
\begin{displaymath}
\mathbf{H}= \left( \begin{array}{ccccccc}
1 & 0 & 0 & 1 & 0 & 1 & 1\\
0 & 1 & 0 & 1 & 1 & 1 & 0\\
0 & 0 & 1 & 0 & 1 & 1 & 1\\
\end{array} \right)
\end{displaymath}

Se ve que todas las columnas de $\mathbf{H}$ son distintas de cero
y que ninguna de ellas es igual a otra. Por consiguiente, no hay
dos columnas que sumen 0. Entonces, el peso m'inimo de este
c'odigo es por lo menos 3. Por otro lado, las columnas cero, dos y
seis suman 0. Por lo tanto, el peso m'inimo del c'odigo es 3. Y,
aplicando el teorema \ref{t1}, concluimos que la distancia m'inima
es 3.
\end{ejemplo}

Los corolarios \ref{c1} y \ref{c2} se utilizan generalmente para
determinar la distancia m'inima o establecer un l'imite inferior
en la distancia m'inima de un c'odigo lineal de bloque.

\section{Propiedades de detecci'on y correcci'on de errores de un
c'odigo bloque}
\subsection{Propiedades detectoras}
Cuando se transmite un vector c'odigo $\mathbf{v}$ por un canal
ruidiso, un vector de error con 1 errores provoca que el vector
recibido $\mathbf{r}$ sea diferente del vector $\mathbf{v}$ en 1
posiciones ($d(v,r)=1$). Si la distancia m'inima del c'odigo $C$
es $d_{min}$, cada pareja de dos vectores de $C$ tienen al menos
$d_{min}$ posiciones distintas. Por lo tanto, cualquier vector de
error con $d_{min}-1$ o menos errores da un vector $\mathbf{r}$
que no es una palabra c'odigo de $C$. Cuando el receptor detecta
que el vector recibido no es una palabra c'odigo de $C$, el error
ha sido detectado.

Por lo tanto, un c'odigo bloque con distancia m'inima $d_{min}$ es
capaz de detectar todos los patrones de error de $d_{min}-1$ o
menos errores.

Un c'odigo bloque detecta todos los patrones de error de
$d_{min}-1$ o menos errores, pero tambi'en detecta una gran
fracci'on de los patrones de error con $d_{min}$ o m'as errores.
En realidad, un c'odigo lineal $(n,k)$ es capaz de detectar
$2^n-2^k$ patrones de error de longitud $n$.

De entre los $2^n-1$ patrones de error distintos de cero, hay
$2^k-1$ patrones de error que son id'enticos a las $2^k-1$
palabras c'odigo. Si sucede cualquiera de esos $2^k-1$ patrones de
error, la palabra c'odigo transmitida $\mathbf{v}$ se transforma
en otra palabra c'odigo $\mathbf{w}$. Por lo tanto, se recibe
$\mathbf{w}$ y su s'indrome es cero. En este caso, el
decodificador acepta $\mathbf{w}$ como la palabra transmitida y
realiza una decodificaci'on incorrecta. De todo esto concluimos
que hay $2^k-1$ \textbf{patrones de error que son indetectables}.

Hay $2^n-2^k$ patrones de error detectables. Para $n$
suficientemente grande, $2^k-1$ es en general mucho m'as peque\~no
que $2^n$. Por lo tanto, \textbf{s'olo una peque\~na fracci'on de
errores pasa por el decodificador sin ser detectados}.

\paragraph{Probabilidad de no detectar un error}
Sea $C$ un c'odigo lineal $(n,k)$. Sea $A_{i}$ el n'umero de
vectores del c'odigo de peso $i$. A los n'umeros
$A_{0},A_{1},\ldots,A_{n}$ se les llama distribuci'on del peso de
$C$. Si $C$ se usa s'olo para detecci'on de errores en un BSC, la
probabilidad de que el decodificador falle al detectar errores se
puede calcular como la distribuci'on del peso de $C$.

Sea $p$ la probabilidad de error de bit del canal, si denotamos la
probabilidad de no detectar un error como $P_{U}(E)$, entonces:
\begin{displaymath}
P_{U}(E)=\sum_{i=0}^{n}A_{i}p^{i}(1-p)^{n-i}
\end{displaymath}

Adem'as, si la distancia m'inima de $C$ es $d_{min}$ entonces
desde $A_{1}$ hasta $A_{d_{min}-1}$ son cero.

\begin{ejemplo} \label{ejemplo6}
Vamos a considerar el c'odigo dado en la tabla de la p'agina
\pageref{tabla1}. La distribuci'on del peso de este c'odigo es
$A_{0}=1,A_{1}=2,A_{2}=0,A_{3}=A_{4}=7,A_{5}=A_{6}=0,A_{7}=1$. La
probabilidad de que no se detecte un error es:
\begin{displaymath}
P_{U}(E)=7p^3(1-p)^4+7p^4(1-p)^3+p^7
\end{displaymath}

Si $p=10^{-2}$, esta probabilidad es aproximadamente $7 \times
10^{-6}$. En otras palabras, si un mill'on de palabras se
transmiten por un canal BSC con $p=10^{-2}$, por t'ermino medio
siete palabras c'odigo err'oneas pasar'an por el decodificador sin
ser detectados.
\end{ejemplo}

\subsection{Propiedades correctoras}
Si un c'odigo bloque $C$ con distancia m'inima $d_{min}$ se usa
para corregir errores aleatorios, es conveniente saber cu'antos
errores es capaz de corregir dicho c'odigo.

La distancia m'inima es par o impar. Por lo tanto, podemos elegir
un entero $t$ tal que: $2t+1 \leq d_{min} \leq 2t+2$.

Ahora vamos a probar que el c'odigo $C$ es capaz de corregir todos
los patrones de error de $t$ o menos errores. Sean $\mathbf{v}$ y
$\mathbf{r}$ el vector transmitido y recibido respectivamente. Sea
$\mathbf{w}$ cualquier otro vector c'odigo de $C$. La distancia
Hamming entre $\mathbf{v}$, $\mathbf{r}$ y $\mathbf{w}$ satisface
la desigualdad triangular: $d(v,r)+d(w,r) \geq d(v,w)$.

Supongamos que un patr'on de error de $t'$ sucede durante la
transmisi'on de $\mathbf{v}$. Entonces, el vector recibido tiene
$t'$ posiciones distintas de $\mathbf{v}$ y $d(v,r)=t'$. Puesto
que $\mathbf{v}$ y $\mathbf{w}$ son vectores c'odigo de $C$,
tenemos que $d(v,w) \geq d_{min} \geq 2t+1$.

Obtenemos la siguiente desigualdad: $d(w,r) \geq 2t+1-t'$. Si $t'
\leq t$, entonces $d(w,r)>1$.

La desigualdad anterior dice que si un patr'on de $t$ o menos
errores tiene lugar, el vector recibido $\mathbf{r}$ est'a m'as
cerca del vector transmitido $\mathbf{v}$ que a cualquier otro
vector $\mathbf{w}$ en $C$. Bas'andose en el \emph{esquema de
decodificaci'on de m'axima similitud}, $\mathbf{r}$ es
decodificado en $\mathbf{v}$, que es el vector que se transmiti'o.
Se ha realizado una decodificaci'on correcta y por lo tanto una
correcci'on de errores.

Por otra parte, el c'odigo no es capaz de corregir todos los
patrones de error de 1 errores con $1>t$. Esto sucede porque por
lo menor hay un caso en el cual un patr'on de 1 errores da lugar
en recepci'on un vector $\mathbf{r}$ que est'a m'as cerca de un
vector c'odigo incorrecto que al vector transmitido. Veamos esto
con dos vectores c'odigo $\mathbf{v}$ y $\mathbf{w}$:

$d(v,w)=d_{min}$.

Sean $e_{1}$ y $e_{2}$ dos patrones de error que satisfacen las
siguientes condiciones:
\begin{enumerate}
  \item $e_{1} + e_{2} = v+w$.
  \item $e_{1}$ y $e_{2}$ no tienen componentes distintas de cero
  en las mismas posiciones.
\end{enumerate}

Obviamente, tenemos que $w(e_{1})+w(e_{2})=w(v+w)=d(v,w)=d_{min}$.

Ahora suponemos que $\mathbf{v}$ se transmite y es corrompida por
$e_{1}$. El vector recibido es $r=v+e_{1}$.

La distancia Hamming entre $\mathbf{v}$ y $\mathbf{w}$ es
$d(v,r)=w(v+r)=w(e_{1})$.

La distancia Hamming entre $\mathbf{w}$ y $\mathbf{r}$ es
$d(w,r)=w(v+r)=w(w+v+e_{1})=w(e_{2})$.

Ahora suponemos que el patr'on de error $e_{1}$ contiene m'as de
$t$ errores ($w(e_{1})>t$). Puesto que $2t+1 \leq d_{min} \leq
2t+2$, obtenemos que $w(e_{2}) \leq t+1$.

Combinando las tres 'ultimas expresiones y usando el hecho de que
$w(e_{1})<t$, obtenemos la siguiente desigualdad: $d(v,r) \geq
d(w,r)$.

Esta desigualdad dice que existe un patr'on de error de 1 ($1>t$)
errores que da lugar a un vector recibido que est'a m'as cerca de
un vector incorrecto que del vector transmitido. Bas'andose en el
esquema de decodificaci'on de m'axima similitud se puede producir
una decodificaci'on incorrecta.

Para resumir, un c'odigo bloque con distancia m'inima $d_{min}$
garantiza  que \textbf{corrige todos los patrones de error de
$t=[(d_{min}-1)/2]$ o menos errores}.

La distancia m'inima del c'odigo dado en la tabla de la p'agina
\pageref{tabla1} es 3, con lo que $t=1$. Por lo tanto, es capaz de
corregir cualquier patr'on de error con un s'olo error.

Un c'odigo bloque con capacidad de corregir $t$ errores aleatorios
generalmente es capaz de corregir bastantes patrones de error
$t+1$ errores o m'as. Un c'odigo lineal (n,k) con capacidad de
corregir $t$ errores, es capaz de corregir un total de
$2^{n}-2^{k}$ patrones de error.

\paragraph{Probabilidad de decodificar de forma incorrecta}
Si usamos un c'odigo bloque, que es capaz de corregir $t$ errores,
'unicamente para corregir en un canal BSC con probabilidad de
error $p$, la probabilidad de que el decodificador realice una
decodificaci'on incorrecta es:

\begin{displaymath}
P(E) \leq \sum_{i=t+1}^{n} \left( \begin{array}{c} n \\ i
\end{array} \right) p^{i}(1-p)^{n-i}
\end{displaymath}

\section{Matriz t'ipica y decodificaci'on de s'indrome}
\subsection{Partici'on como m'etodo de decodificaci'on}
Sea $C(n,k)$ un c'odigo lineal y $v_{1}$, $v_{2}$, \ldots, $v_{k}$
los vectores c'odigo que componen $C$. Si enviamos un vector
c'odigo cualquiera a trav'es de un canal ruidoso, el vector
s'imbolo recibido estar'a dentro de las n--tuplas
$(U_{1},\ldots,U_{n})$.

Todo sistema de decodificaci'on divide el total de vectores en
$2^{k}$ subconjuntos disjuntos $D_{1},D_{2},\ldots,D_{k}$. En el
m'etodo que veremos, cada palabra c'odigo $v_{j}$ se encuentra en
un y s'olo un subconjunto $D_{j}$. Si el vector recibido $r_{j}$
se encuentra en ese subconjunto $D_{j}$, se decodificar'a como
$v_{j}$.

\subsection{Construcci'on de la matriz t'ipica}
Empezamos colocando en la primera fila los $2^{k}$ vectores del
c'odigo con el vector nulo $v_{1}=(0,0,\ldots,0)$ como primer
elemento. De las $2^n-2^k$ n--tuplas restantes se toma $e_{2}$
como vector de error y se sit'ua debajo del $v_{1}$, obteniendo el
resto de elementos de la fila como suma de $e_{2}$ con los
vectores c'odigo de la fila primera poniendo $e_{2}+v_{j}$ bajo el
vector $v_{j}$. Para la tercera fila se coge otro que no se
encuentre en las dos primeras y se le llama $e_{3}$. El resto de
la fila lo forman las palabras $e_{3}+v_{j}$ que se sit'ua bajo
$v_{j}$. As'i continuaremos el proceso hasta que todas las
n--tuplas sean usadas quedando la matriz:

\begin{displaymath}
\begin{array}{cccccc}
v_{1}=0 & v_{2} & \ldots & v_{i} & \ldots  & v_{2}k\\
e_{2} & e_{2}+v_{2} & \ldots & e_{2}+v_{i} & \ldots & e_{2}+v_{2}k \\
e_{3} & e_{3}+v_{2} & \ldots & e_{3}+v_{i} & \ldots & e_{3}+v_{2}k \\
\vdots &  &  &  &  & \vdots \\
e_{j} & e_{j}+v_{2} & \ldots & e_{j}+v_{i} & \ldots & e_{j}+v_{2}k \\
\vdots &  &  &  &  & \vdots \\
e_{2n-k} & e_{2n-k}+v_{2} & \ldots & e_{2n-k}+v_{i} & \ldots & e_{2n-k}+v_{2}k \\
\end{array}
\end{displaymath}

\begin{teorema} \label{t3}
En una fila de una matriz t'ipica no existen dos n--tuplas
iguales. Cada n--tupla aparece en una y s'olo una fila.
\end{teorema}

\textbf{Demostraci'on}

\textsl{La primera parte del teorema se deduce del hecho de que
todos los vectores c'odigo de $C$ son distintos. Si suponemos que
dos n--tuplas de la fila k--'esima son iguales, es decir,
$e_{k}+v_{i}=e_{k}+v_{j}$ con $i$ distinto de $j$, entonces
tendr'iamos $v_{i}=v_{j}$, lo cual es imposible. Por tanto dos
n--tuplas de una misma fila no pueden ser iguales.}

\textsl{De la regla de construcci'on de la matriz t'ipica se sigue
que toda n--tupla aparece al menos una vez. Supongamos ahora que
una n--tupla apareciera en las filas $t$ y $m$ con $t<m$. Entonces
esta n--tupla ser'ia igual a $e_{1}+v_{s}$ para alg�un $s$ y
tambi'en $e_{m}+v_{j}$ para alg'un $j$. Pero entonces
$e_{t}+v_{s}=e_{m}+v_{j}$ y, despejando,
$e_{m}=e_{t}+(v_{s}+j)=e_{t}+v_{k}$ (pues la suma de dos palabras
c'odigo es otra palabra c'odigo). Esta ecuaci'on significa que el
vector $e_{m}$ estaba tambi'en en la fila $t$, lo que contradice
la regla de construcci'on de la matriz t'ipica, pues el l'ider de
un coconjunto ha de ser un vector que no aparezca todav'ia en la
matriz. Esto demuestra la segunda parte del teorema.}

Se deduce pues que hay $e^{n-k}$ filas distintas, cada una con
$2^{k}$ elementos distintos. Estas filas son denominadas
coconjuntos del c'odigo $C$ y la primera n--tupla de cada
coconjunto se denomina l'ider del coconjunto. Cualquier elemento
del coconjunto ha de ser l'ider del mismo, permut'andose los
elementos, pero sin cambiar el coconjunto.

Una matriz t'ipica de un c'odigo lineal C(n,k) consta de $2^{k}$
columnas disjuntas, cada una con $2^{n-k}$ n--tuplas siendo la
m'as alta un vector c'odigo de $C$. Si denominamos $D_{j}$ a la
columna j--'esima de la matriz t'ipica, entonces:

$D_{j}=\{v_{j},e_{2}+v_{j},e_{3}+v_{j},\ldots
,e_{2^{n-k}}+v_{j}\}$, donde $v_{j}$ es un vector c'odigo de $C$ y
$e_{2},\ldots ,e_{2^{n-k}}$ son los l'ideres de los coconjuntos.
Las $2^{k}$ columnas disjuntas $D_{1},D_{2},\ldots ,D_{2^{k}}$
pueden ser usadas para decodificar $C$.

\begin{teorema} \label{t4}
Todo c'odigo lineal de bloque es capaz de corregir $2^{n-k}$
patrones de error.
\end{teorema}

\textbf{Demostraci'on}

\textsl{Enviamos un vector c'odigo $v_{j}$ a trav'es de un canal
ruidoso y recibimos un vector $r$. Este vector ser'a correctamente
decodificado si se encuentra en el coconjunto $D_{j}$, y para ello
el vector ruido del canal ha se ser l'ider del coconjunto. Si no
lo es, aparecer'a en la matriz bajo la columna $t$ cuya palabra
c'odigo asociada es el vector $v_{t}$ de tal forma que si llamamos
$x$ al ruido del canal ser'a $x=e_{1}+v_{t}$. Por tanto, al enviar
$v_{j}$ tendremos que $r=v_{j}+x=v_{j}+v_{t}+e_{1}=v_{n}+e_{1}$,
siendo $v_{n}$ vector c'odigo por ser suma de palabras c'odigo. Al
decodificar obtendremos err'oneamente $v_{n}$ en vez de $v_{j}$.}

\textsl{Por tanto, la decodificaci'on es correcta si el vector del
canal es l'ider del coconjunto. Por ello, a estos $2^{n-k}$
vectores l'ideres de los coconjuntos se les denomina
\textbf{patrones de error} y son los 'unicos que pueden ser
corregidos correctamente en el c'odigo C(n,k).}

Para minimizar la probabilidad de error hemos de coger como
l'ideres de los coconjuntos los patrones de error m'as probables,
que en un BSC son los de menos peso. Por consiguiente, al formar
la matriz t'ipica, deben elegirse los l'ideres de lo coconuuntos
como un vector del menor peso entre los que a'un no han sido
incluidos. As'i, el l'ider tiene m'inimo peso en su coconjunto,
siendo la decodificaci'on basada en la matriz t'ipica una
\textbf{decodificaci'on de m'inima distancia}.

\textbf{Demostraci'on}

\textsl{Esta es la demostraci'on del m'inimo peso del l'ider del
coconjunto:}

\textsl{Sea $\mathbf{r}$ el vector recibido. Supongamos que $r$ se
encuentra en la columna i'esima $D_{1}$ y el coconjunto l--'esimo
de la matriz t'ipica. Entonces $r$ se deocodifica como el vector
$v_{1}$. Como $r=e_{1}+v_{i}$, la distancia entre $r$ y $v_{i}$ es
$d(r,v_{i})=w(r+v_{i})=w(e_{1}+v_{i}+v_{i})=e(e_{1})$.}

\textsl{Consideremos ahora la distancia entre $r$ y otro vector
c'odigo $v_{j}$: $d(r,v_{j})=w(r+v_{j})=w(e_{1}+v_{i}+v_{j})$.
Como $v_{i}$ y $v_{j}$ son dos vectores diferentes, $v_{i}+v_{j}$
es un vector c'odigo no nulo $v_{s}$. As'i
$d(r,v_{s})=w(e_{1}+v_{s})$ y como $e_{1}$ y $e_{1}+v_{s}$ est'an
en el mismo coconjunto cumpli'endose $w(e_{1}) \leq
w(e_{1}+v_{s})$, se sigue: $\mathbf{d(r,v_{i}) \leq d(r,v_{j})}$.}

Un c'odigo lineal (n,k) es capaz de detectar $2^{n}-2^{k}$
patrones de error y de corregir $2^(n-k)$. Para $n$ muy grande el
error de decodificaci'on es mucho mayor que la probabilidad de
error sin detectar.


\begin{teorema} \label{t5}
Para un c'odigo lineal C(n,k) con distancia m'inima $d_{min}$,
todas las n--tuplas de peso $t=[(d_{min}-1)/2]$ o menor pueden ser
usadas como l'ideres de coconjuntos de una matriz t'ipica de $C$.
Si todas las n--tuplas de peso $t$ o menor son usadas, hay al
menos una n--tupla de peso $t+1$ que no puede ser usada como
l'ider de coconjunto.
\end{teorema}

Este teorema nos confirma que un c'odigo lineal C(n,k) con
distancia m'inima $d_{min}$, es capaz de corregir todos los
patrones de error de $[(d_{min}-1)/2]$ o menos errores, pero no es
capaz de corregir todos los patrones de error de peso $t+1$.

\begin{teorema} \label{t6}
Todas las $2^{k}$ n--tuplas de un coconjunto tienen el mismo
s'indrome. Los s'indromes para diferentes coconjuntos son
distintos.
\end{teorema}

Sabemos que el s'indrome de una n--tupla es una (n-k)--tupla y hay
$2^(n-k)$ (n-k)--tuplas. Usando la correspondencia uno a uno que
existe entre un l'ider de coconjunto y un s'indrome podemos formar
una tabla de decodificaci'on, que es un m'etodo mucho m'as simple
para usar la matriz t'ipica. La tabla contiene los $2^(n-k)$
l'ideres de coconjuntos y sus correspondientes s'indromes. La
decodificaci'on consta de tres pasos:
\begin{enumerate}
  \item Calcular el s'indrome del vector recibido $r$,
  multiplic'andolo por la matriz $H$ traspuesta.
  \item Localizar el l'ider del coconjunto cuyo s'indrome es igual
  al hallado. Entonces dicho l'ider ($e_{i}$) se considera el
  patr'on de error causado por el canal.
  \item Decodificar el vector recibido $r$ en el vector c'odigo $v=r+e_{i}$.
\end{enumerate}

A este esquema de decodificaci'on se le denomina
\textbf{decodificaci'on de s'indrome}. El resultado de aplicar
este m'etodo a un c'odigo lineal C(n,k) es un retraso en
decodificaci'on m'inimo y una probabilidad de error m'inima. No
obstante para $n-k$ grandes, el esquema se vuelve poco pr'actico.

\begin{ejemplo} \label{ejemplo7}
Consideremos el c'odigo lineal C(7,4). La matriz de comprobaci'on
de paridad es:
\begin{displaymath}
H= \left( \begin{array}{ccccccc}
1 & 0 & 0 & 1 & 0 & 1 & 1\\
0 & 1 & 0 & 1 & 1 & 1 & 0\\
0 & 0 & 1 & 0 & 1 & 1 & 1\\
\end{array} \right)
\end{displaymath}

El c'odigo tiene $2^{3}=8$ coconjuntos y, as'i hay ocho patrones
de correcci'on de errores (incluyendo el vector nulo). Como la
distancia m'inima del c'odigo es 3, es capaz de corregir todos los
patrones de error de peso 1 'o 0. Aqu'i pueden ser usadas como
l'ideres de coconjuntos todas las 7--tuplas de peso 1 'o 0. Hay 8
vectores que cumplen esto. En este ejemplo, para el c'odigo lineal
(7,4), el n'umero de patrones de error que se pueden corregir
garantizado por la distancia m'inima es igual al total de patrones
de error corregibles. Los patrones de error corregibles y sus
correspondientes s'indromes vienen dados en la siguiente tabla:

\begin{center}
\begin{tabular}{|c|c|}\hline
  S'indrome & L'ideres de coconjuntos \\ \hline \hline
  $(1 0 0)$ & $(1 0 0 0 0 0 0)$ \\
  $(0 1 0)$ & $(0 1 0 0 0 0 0)$ \\
  $(0 0 1)$ & $(0 0 1 0 0 0 0)$ \\
  $(1 1 0)$ & $(0 0 0 1 0 0 0)$ \\
  $(0 1 1)$ & $(0 0 0 0 1 0 0)$ \\
  $(1 1 1)$ & $(0 0 0 0 0 1 0)$ \\
  $(1 0 1)$ & $(0 0 0 0 0 0 1)$ \\\hline
\end{tabular}
\end{center}

Supongamos que se transmite el vector c'odigo $v=(1 0 0 1 0 1 1)$
y se recibe $r=(1 0 0 1 1 1 1)$. Para decodificar $r$ calculamos
su s'indrome:
\begin{displaymath}
s=(1 0 0 1 1 1 1) \left( \begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 1 & 0 \\
0 & 1 & 1 \\
1 & 1 & 1 \\
1 & 0 & 1 \\
\end{array} \right) =(0 1 1)
\end{displaymath}

Si observamos la tabla averiguamos que $(0 1 1)$ es el s'indrome
del l'ider de coconjunto $e=(0 0 0 0 1 0 0)$. As'i, se asume que
el patr'on de error causado por el canal es $(0 0 0 0 1 0 0)$, y
$r$ se decodifica en $v^{*}=r+e=(1 0 0 1 1 1 1)+(0 0 0 0 1 0 0)=(1
0 0 1 0 1 1)$ que coincide con el vector transmitido. La
decodificaci'on ser'a correcta si el patr'on de error causado por
el canal es un �l'ider de cconjunto.

Ahora supongamos que se transmite $v=(0 0 0 0 0 0 0)$ y se recibe
$r=(1 0 0 0 1 0 0)$. Vemos que se han producido dos errores
durante la transmisi'on de $v$. El patr'on de rror no se puede
corregir y causar'a un error de decodificaci'on. Cuando se recibe
$r$, el receptor calcula el s'indrome $s=rH^{T}=(1 1 1)$.

De la tabla de decodificaci'on encontramos que el l'ider del
coconjunto $e=(0 0 0 0 0 1 0)$ corresponde al s'indrome $s=(1 1
1)$. Como resultado, $r$ se decodifica en el vector c'odigo en
$v^{*}=r+e=(1 0 0 0 1 0 0)+(0 0 0 0 0 1 0)=(1 0 0 0 1 1 0)$.

Como $v^{*}$ no es el vector c'odigo transmitido, se comoete un
error de decodificaci'on. Usando pues la tabla anterior se pueden
corregir errores simples sobre un bloque de 7 d'igitos. Cuando
ocurren dos o m'as errores se comete un error de decodificaci'on.
\end{ejemplo}

\section{C'odigos Hamming}
Los c'odigos Hamming fueron la primera clase de c'odigos ideados
para correcci'on de errores. Estos c'odigos y sus variaciones han
sido 'ampliamente usados para control de errores en comunicaci'on
digital y en sistemas de almacenaje de informaci'on.

Para cualquier entero positivo $m \geq 3$ existe un c'odigo
Hamming con los siguientes par'ametros:

\begin{center}
\begin{tabular}{cc}
  Longitud del c'odigo & $n=2^{m}-1$ \\
  N'umero de s'imbolos de informaci'on & $k=2^{m}-m-1$ \\
  N'umero de s'imbolos de comprobaci'on de paridad & $n-k=m$ \\
  Capacidad de correcci'on de errores & $t=1$($d_{min}=3$) \\
\end{tabular}
\end{center}

La matriz de comprobaci'on de paridad $H$ de este c'odigo consta
de todas las m--tuplas no nulas como columnas. En forma
sistem'atica, las columnas de $H$ est'an ordenadas de la siguiente
forma: $H=[I_{m}Q]$, donde $I_{m}$ es una matriz identidad $m
\times m$ y la submatriz $Q$ consta de $2^{m}-m-1$ columnas, las
cuales son las m--tuplas de peso 2 o m'as. Estas columnas pueden
ser colocadas en cualquier orden sin afectar a la propiedad de
distancia y distribuci'on de peso del c'odigo. En forma
sistem'atica, la matriz generadora del c'odigo es
$G=[Q^{T}I_{2^{m}-m-1}]$, donde $Q^{T}$ es la traspuesta de $Q$ y
$I_{2^{m}-m-1}$ es una matriz identidad de orden $2^{m}-m-1$.

Como las columnas de $H$ son no nulas y distintas, dos columnas no
pueden sumar cero. Se sigue que la m'inima distancia de un c'odigo
Hamming es, al menos, 3. Como $H$ consta de todas las m--tuplas no
nulas como columnas, el vector suma de dos columnas cualesquiera,
$h_{i}$ y $h_{j}$, debe ser tambi'en una columna de $H$, $h_{1}$.
As'i $h_{i}+h_{j}+h_{1}=0$.

De aqu'i se sigue que la m'inima distancia de un c'odigo Hamming
es exactamente 3. As'i, el c'odigo es capaz de corregir todos los
patrones de error con un error simple o de detectar todos los
patrones de error de dos errores o menos.

Si formamos una matriz t'ipica para el c'odigo Hamming de longitud
$2^{m}-1$, se pueden usar todas las ($2^{m}-1$)--tuplas de peso 1
como l'ideres de coconjunto. El n'umero de ($2^{m}-1$)--tuplas de
peso 1 es $2^{m}-1$. Como $n-k=m$, el c'odigo tiene $2^{m}$
coconjuntos. As'i, el vector 0 y las ($2^{m}-1$)--tuplas de peso 1
forman todos los l'ideres de los coconjuntos de la matriz t'ipica.
Esto nos dice que un c'odigo Hamming corrige solamente los
patrones de error simple y ning'un otro. Esta es una construcci'on
muy interesante. Un c'odigo corrector de errores de peso $t$ se
llama \textbf{c'odigo perfecto} si su matriz t'ipica tiene todos
los patrones de error de peso $t$ o menor y ninguno otro como
l'ideres de coconjunto. As'i, los c'odigos Hamming forman una
clase de c'odigos perfectos de correcci'on de errores simples.

Podemos borrar cualesquiera $l$ columnas de la matriz de
comprobaci'on de paridad $H$ de un c'odigo Hamming. Esto da como
resultado una matriz $H'$ de orden $m \times (2^{m}-l-1)$. Usando
$H'$ como matriz de comprobaci'on de paridad, obtenemos un c'odigo
Hamming recortado por los siguientes par'ametros:

\begin{center}
\begin{tabular}{cc}
  Longitud del c'odigo & $n=2^{m}-l-1$ \\
  N'umero de s'imbolos de informaci'on & $k=2^{m}-m-l-1$ \\
  N'umero de s'imbolos de comprobaci'on de paridad & $n-k=m$ \\
  Capacidad de correcci'on de errores & $d_{min}=3$ \\
\end{tabular}
\end{center}

Si borramos las columnas apropiadas de $H$, obtenemos un c'odigo
Hamming recortado de distancia m'inima 4. El c'odigo Hamming
recortado de distancia 4 puede ser usado para corregir los
patrones de error simple y simult'aneamente detectar los patrones
de error doble. Cuando un error simple ocurre durante la
transmisi��on de un vector c��odigo, el s'indrome resultante es
distinto de cero y contiene un n'umero par de unos. No obstante,
cuando ocurre un error doble el s'indrome es tambi'en distinto de
cero, pero consta de un n'umero impar de unos. Bas'andonos en
estos hechos, la decodificaci'on puede ser realizada de la
siguiente manera:
\begin{enumerate}
  \item Si el s'indrome $s$ es cero, asumimos que el error no existi'o.
  \item Si $s$ es distinto de cero y consta de un n'umero par de
  unos, asumimos que el error ocurrido fue un error simple. El
  patr'on del error simple que corresponde a $s$ se suma al vector
  recibido para la correcci'on de errores.
  \item Si $s$ es distinto de cero y contiene un n'umero impar de
  unos se ha detectado un patr'on de error no corregible.
\end{enumerate}


\chapter{Dise\~no de subcircuitos}
\section{Contador binario de 0 a 6}
Nos va a hacer falta un contador que cuente 7 veces, o lo que es
lo mismo, que cuente de 0 a 6. Para ello vamos a seguir una
metodolog'ia de dise\~no de circuitos secuenciales. A
continuaci'on se muestra la ``tabla del estado futuro'' en la que
se basar'a el contador.
\begin{center}
\begin{tabular}{|ccc|ccc|cc|cc|cc|} \hline
  $Q_{2}$ & $Q_{1}$ & $Q_{0}$ & $Q_{2}'$ & $Q_{1}'$ & $Q_{0}'$ & $J_{2}$ & $K_{2}$ & $J_{1}$ & $K_{1}$ & $J_{0}$ & $k_{0}$
  \\ \hline \hline
  0 & 0 & 0 & 0 & 0 & 1 & 0 & x & 0 & x & 1 & x \\ \hline
  0 & 0 & 1 & 0 & 1 & 0 & 0 & x & 1 & x & x & 1 \\ \hline
  0 & 1 & 0 & 0 & 1 & 1 & 0 & x & x & 0 & 1 & x \\ \hline
  0 & 1 & 1 & 1 & 0 & 0 & 1 & x & x & 1 & x & 1 \\ \hline
  1 & 0 & 0 & 1 & 0 & 1 & x & 0 & 0 & x & 1 & x \\ \hline
  1 & 0 & 1 & 1 & 1 & 0 & x & 0 & 1 & x & x & 1 \\ \hline
  1 & 1 & 0 & 0 & 0 & 0 & x & 1 & x & 1 & 0 & x \\ \hline
  1 & 1 & 1 & 0 & 0 & 0 & x & 1 & x & 1 & x & 1 \\ \hline
\end{tabular}
\end{center}

Se debe simplificar cada $J$ y cada $K$ en funci'on de las
entradas $Q_{2}$, $Q_{1}$ y $Q_{0}$. El resultado de esta
simplificaci'on es el siguiente:

$J_{2}=Q_{1} Q_{0}$

$K_{2}=Q_{1}$

$J_{1}=Q_{0}$

$K_{1}=Q_{2} + Q_{0}$

$J_{0}=\overline{Q_{2}} + \overline{Q_{0}}$

$K_{0}=1$

\section{Contador hasta 27}\label{c27}
Ahora dise\~naremos un contador que cuente de 0 hasta 27 (28
veces). Esta es su tabla de estado futuro:

\begin{center}
{\scriptsize

\begin{tabular}{|ccccc|ccccc|cc|cc|cc|cc|cc|}\hline
  $Q_{4}$ & $Q_{3}$ & $Q_{2}$ & $Q_{1}$ & $Q_{0}$ & $Q_{4}'$ & $Q_{3}'$ & $Q_{2}'$ & $Q_{1}'$ & $Q_{0}'$ & $J_{4}$ & $K_{4}$ & $J_{3}$ & $K_{3}$ & $J_{2}$ & $K_{2}$ & $J_{1}$ & $K_{1}$ & $J_{0}$ & $K_{0}$
  \\ \hline \hline
  0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & x & 0 & x & 0 & x &
  0 & x & 1 & x \\ \hline
  0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & x & 0 & x & 0 & x &
  1 & x & x & 1 \\ \hline
  0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & x & 0 & x & 0 & x &
  x & 0 & 1 & x \\ \hline
  0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & x & 0 & x & 1 & x &
  x & 1 & x & 1 \\ \hline
  0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & x & 0 & x & x & 0 &
  0 & x & 1 & x \\ \hline
  0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & x & 0 & x & x & 0 &
  1 & x & x & 1 \\ \hline
  0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & x & 0 & x & x & 0 &
  x & 0 & 1 & x \\ \hline
  0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & x & 1 & x & x & 1 &
  x & 1 & x & 1 \\ \hline
  0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & x & x & 0 & 0 & x &
  0 & x & 1 & x \\ \hline
  0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & x & x & 0 & 0 & x &
  1 & x & x & 1 \\ \hline
  0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & x & x & 0 & 0 & x &
  x & 0 & 1 & x \\ \hline
  0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & x & x & 0 & 1 & x &
  x & 1 & x & 1 \\ \hline
  0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & x & x & 0 & x & 0 &
  0 & x & 1 & x \\ \hline
  0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & x & x & 0 & x & 0 &
  1 & x & x & 1 \\ \hline
  0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & x & x & 0 & x & 0 &
  x & 0 & 1 & x \\ \hline
  0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & x & x & 1 & x & 1 &
  x & 1 & x & 1 \\ \hline
  1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & x & 0 & 0 & x & 0 & x &
  0 & x & 1 & x \\ \hline
  1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & x & 0 & 0 & x & 0 & x &
  1 & x & x & 1 \\ \hline
  1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & x & 0 & 0 & x & 0 & x &
  x & 0 & 1 & x \\ \hline
  1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & x & 0 & 0 & x & 1 & x &
  x & 1 & x & 1 \\ \hline
  1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & x & 0 & 0 & x & x & 0 &
  0 & x & 1 & x \\ \hline
  1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & x & 0 & 0 & x & x & 0 &
  1 & x & x & 1 \\ \hline
  1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & x & 0 & 0 & x & x & 0 &
  x & 0 & 1 & x \\ \hline
  1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & x & 0 & 1 & x & x & 1 &
  x & 1 & x & 1 \\ \hline
  1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & x & 0 & x & 0 & 0 & x &
  0 & x & 1 & x \\ \hline
  1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & x & 0 & x & 0 & 0 & x &
  1 & x & x & 1 \\ \hline
  1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & x & 0 & x & 0 & 0 & x &
  x & 0 & 1 & x \\ \hline
  1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & x & 1 & x & 1 & 0 & x &
  x & 1 & x & 1 \\ \hline
  1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & x & 1 & x & 1 & x & 1 &
  0 & x & 0 & x \\ \hline
  1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & x & 1 & x & 1 & x & 1 &
  0 & x & x & 1 \\ \hline
  1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & x & 1 & x & 1 & x & 1 &
  x & 1 & 0 & x \\ \hline
  1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & x & 1 & x & 1 & x & 1 &
  x & 1 & x & 1 \\ \hline
\end{tabular}
}
\end{center}

Estas ser'ian las funciones l'ogicas:

$J_{4}=Q_{3}Q_{2}Q_{1}Q_{0}$

$K_{4}=Q_{3}Q_{1}Q_{0}+Q_{3}Q_{2}$

$J_{3}=Q_{2}Q_{1}Q_{0}$

$K_{3}=Q_{2}Q_{1}Q_{0}+Q_{4}Q_{1}Q_{0}+Q_{4}Q_{2}$

$J_{2}=\overline{Q_{4}}Q_{1}Q_{0}+\overline{Q_{3}}Q_{1}Q_{0}$

$K_{2}=Q_{4}Q_{3}+Q_{1}Q_{0}$

$J_{1}=\overline{Q_{4}}Q_{0}+\overline{Q_{3}}Q_{0}+\overline{Q_{2}}Q_{0}$

$K_{1}=Q_{4}Q_{3}+Q_{0}$

$J_{0}=\overline{Q_{4}}+\overline{Q_{3}}+\overline{Q_{2}}$

$K_{0}=1$


\end{document}
