%        File: tcodici.tex
%
% (c) Copyright 2009 Andrea Lo Pumo aka AlpT <alpt@freaknet.org>
%
% This source code is free software; you can redistribute it and/or
% modify it under the terms of the GNU General Public License as published 
% by the Free Software Foundation; either version 2 of the License,
% or (at your option) any later version.
%
% This source code is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
% Please refer to the GNU Public License for more details.
%
% You should have received a copy of the GNU Public License along with
% this source code; if not, write to:
% Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
%

\documentclass[a4paper]{article}
%%% 	 Orientamento	      %%%
%\usepackage[landscape]{geometry}
%%%			      %%%

\usepackage{xr-hyper}
\usepackage{amath}

\externaldocument[AI-]{algebraI}[../../algebra/1/algebraI.pdf]
\externaldocument[AL-]{alineare}[../../algebra/lineare/alineare.pdf]
\externaldocument[GII-]{geometriaII}[../../geometria/2/geometriaII.pdf]
\externaldocument[AC-]{complementi}[../../algebra/complementi/complementi.pdf]
\ifpdf
\newcommand{\AI}[1]{\T{[AI,\ref{AI-#1},pg.\pageref{AI-#1}]}}
\newcommand{\AL}[1]{\T{[AL,\ref{AL-#1},pg.\pageref{AL-#1}]}}
\newcommand{\GII}[1]{\T{[GII,\ref{GII-#1},pg.\pageref{GII-#1}]}}
\newcommand{\AC}[1]{\T{[AC,\ref{AC-#1},pg.\pageref{AC-#1}]}}
\else
\newcommand{\AI}[1]{\T{[AI,x.y.z,pg.xx]}}
\newcommand{\AL}[1]{\T{[AL,x.y.z,pg.xx]}}
\newcommand{\GII}[1]{\T{[GII,x.y.z,pg.xx]}}
\newcommand{\AC}[1]{\T{[AC,x.y.z,pg.xx]}}

% add label debugging if we are not compiling pdf.
\let\oldlabel\label
\renewcommand{\label}[1]{ [#1] \oldlabel{#1}}
\fi


\begin{document}
\title{Teoria dei Codici}
\author{AlpT (@freaknet.org)\\
\small{\url{http://freaknet.org/alpt}}
}


\pagenumbering{roman}
\maketitle{}

\begin{abstract}
Questo testo e' una rielaborazione personale degli appunti presi durante
il corso di Teoria dei Codici, tenuto dal Prof. Re Riccardo presso il dipartimento di
Matematica, Catania, A.A. 2008/2009.\\
Saro' ben lieto di correggere ogni eventuale errore che mi comunicherai.

Buon lettura.
\begin{center}
	\verb|^_^|
\end{center}
\end{abstract}

\input{gpl}

\clearpage
\tableofcontents
\clearpage
\pagenumbering{arabic}

\let\oldsection\section
\renewcommand{\section}[1]{\oldsection{#1}\ilabel{#1}}
\let\oldsubsection\subsection
\renewcommand{\subsection}[1]{\oldsubsection{#1}\ilabel{#1}}
\let\oldsubsubsection\subsubsection
\renewcommand{\subsubsection}[1]{\oldsubsubsection{#1}\ilabel{#1}}


\def\RE#1#2{\T{[RE,#1,pg.#2]}}   %% Appunti di Re modificati a penna
\def\QUA#1#2{\T{[QUA,#1,pg.#2]}} %% Appunti sul quaderno
%% Quando trascrivi le proposizioni qui, come \ilabel usa \ilabel{QUA#1#2}
%% e sostituisci QUA con \def\QUA#1#2{\see{QUA#1#2}} 

\section{Introduzione}
Questi appunti digitali fanno riferimento a i relativi appunti cartacei che
sono stati acquisiti e inclusi nell'appendice.\\
Notazione:
\begin{enumerate}
	\item \QUA{OssX.Y.Z}{123} e' un riferimento alla proposizione OssX.Y.Z
		che trovate nell'appendice B, a pagina 123.
	\item \RE{OssX.Y.Z}{123} e' un riferimento all'appendice A.
	\item \AC{formuleviete} e' un riferimento agli appunti di Complementi
		di Algebra (vedi gli altri appunti su
		\href{http://freaknet.org/alpt}{} ).
	\item \AL{proprangodiAMeqrandoMAeqrangoA} e' un riferimento agli
		appunti di Algebra Lineare.
\end{enumerate}

%Legenda: 
%\begin{verbatim}
%\def\RE#1#2{\T{[RE,#1,pg.#2]}}   %% Appunti di Re modificati a penna
%\def\QUA#1#2{\T{[QUA,#1,pg.#2]}} %% Appunti sul quaderno
%\externaldocument[AC-]{complementi}[../../algebra/complementi/complementi.pdf]
%\end{verbatim}

\def\.{\cdot}
\def\Z{{\mathbb{Z}}}
\newcommand{\pmin}[2]{P_{\T{min}}\pton{#1,#2}}
\def\orto#1{{#1}^{\perp }}

\section{Varie}
\def\b{{\beta}}
\begin{lem}\ilabel{SommaDiUnita}	Sia $\b\in U_n$, con $U_n$ gruppo delle radici $n$-esime
	dell'unita',	allora	\eal{&\b \neq 1 \> \b^0+\b^1+\dots+\b^{n-1} = 0	}\end{lem}
	\begin{proof}
		\eal{&x^n-1=(x-1)(1+x+x^2+\dots+x^{n-1})\;\;(1)\NN
		\b \in U_n \= \b^n-1=0  \ubrace{\=}{(1),\;\b \neq 1} 
		1+\b+\dots+\b^{n-1}=0
		}
	\end{proof}
\begin{prop}
	\ilabel{TrovaHdaG}
	Sia $G\in k\*n$ la matrice generatrice del codice lineare $C\(K^n$, $\dim
	C=k$. Sia $H\in n-k \*n$, con $\rho(H)=n-k$, 
	\eal{&H\T{ e' una matrice di controllo per }C \= H\.G\TR =0 }
	Inoltre, se i vettori colonna $h_1,\dots,h_s$ sono una base dello spazio vettoriale
	$\pgra{x\in K^n\;|\;Gx= 0 }$,  allora 
	\eal{&H=\begin{pmatrix}
		h_1\TR\\
		h_2\TR\\
		\vdots\\
		h_s\TR
	\end{pmatrix}
	}
	e' una matrice di controllo di $C$ (nota\footnote{e si ha $s=n-k$}).

	Nota: questa proposizione e' utile per calcolare $H$ a partire da $G$.
\end{prop}
\begin{proof}
	\eal{&G=\begin{pmatrix}
		g_1\\
		\vdots\\
		g_k
	\end{pmatrix}\T{ generatrice di } C
	\> \pgra{g_1,\dots,g_k}\T{ base di }C\;\;(1)}
	\step{p0}{
	\eal{&H\T{ e' una matrice di controllo per }C \= H\.G\TR =0 }
	}
	\begin{prova}
		infatti,
		\eal{&\rho(H)=n-k \> \T{ le righe di H, }
		H_1,\dots,H_{n-k}, \T{ sono l.i.} \;\;(2)\NN
		H\T{ di controllo per C }
		\ubrace{\=}{\QUA{prop3.3.1}{4}} H\T{ generatrice per }\orto
		C \ubrace{\=}{(1)}  \pgra{H_1,\dots,H_{n-k}}\T{ indipendenti, },\;H_i g_j =0
		\;\;\forall i,j  \=\NN
		\ubrace{\=}{(2)}  
		H_i g_j =0
                \;\;\forall i,j \= H G\TR =0
		}
	\end{prova}
	\step{}{Dim $2.$}
	\begin{prova}
\eal{&x\in \orto C \= 
x\.g_i=0\forall i \= G x =0 \= x\in \pgra{x\in K^n\;|\;Gx= 0 }\NN
\qq \> \orto C = \pgra{x\in K^n\;|\;Gx= 0}\;\;(2)
}
Siano le colonne $h_1,\dots,h_s$  una base di $\orto C$ e sia 
	\eal{&H=\begin{pmatrix}
		h_1\TR\\\vdots\\h_s\TR
	\end{pmatrix}
	}
	allora
	\eal{&(2) \> h_i\TR \. g_j =0 \;\;\forall i,j \= HG\TR =0\NN
	\dim \orto C = n-\dim C = n-k \> s=n-k\NN
	\pgra{h_1,\dots,h_{n-k}}\T{ base } \>  \pgra{h_1,\dots,h_{n-k}}\T{
	l.i. }\NN
	\qq  \ubrace{\>}{\sref{p0}} H\T{ e' di controllo per }C
	}
\end{prova}
\end{proof}

\section{MDS}
\begin{prop}\ilabel{CostruzioneMDS}
\def\g{{\gamma}}
	Costruzione di codici MDS.\\
	Sia $S=\pqua{\g_1,\dots,\g_n}\(  F_q,\;|S|=n$, e sia $k\le n$,  allora il codice
	lineare
\eal{&
	C = \pgra{(f(\g_1),\dots,f(\g_n))\;|\;f\in F_q[x]_{k-1}}
}
e' un codice $MDS$ con $\dim C=k$.
\end{prop}
\begin{proof}
\def\g{{\gamma}}
Sia $\ove f = (f(\g_1),\dots,f(\g_n))$. 
Si ha:
\eal{&f\in   F_q[x]_{k-1} \> \deg f \le  k-1  \|  f\equiv 0 \;\;(1)\NN
f \neq 0  \ubrace{\>}{(1)} f\T{ puo' avere al piu' } k-1\T{ radici }
\;\;(1.1)
}
\step{}{$C$ e' lineare e $\dim C=k$}
\begin{prova}
	\def\f{{\varphi}}
Consideriamo l'applicazione:
\eal{&\f: F_q[x]_{k-1} \longrightarrow  C\NN
f\mapsto \ove f
}
$\f$ e' lineare perche' la valutazione di polinomi e' un omomorfismo di anelli. 
E' surriettiva per definizione di $C$.
\eal{&\Im \f = C,\;\f\T{ lineare }  \> C\T{ spazio vett. } }
E' iniettiva:
\eal{&\ker \f = \pgra{f\;|\;f(\g_i)=0\;\;\forall i=1,\dots,n}
\ubrace{=}{(1.1)} =\pgra{0}\> \f\T{ iniettiva } 
}
\eal{&\f\T{ isomorfismo } \> \dim F_q[x]_{k-1} = \dim \Im f =
\dim C \= \dim C = k
}
\end{prova}
\eal{&(1.1)\> \T{ al piu' si annullano } k-1 \T{ coordinate di } 
\ove f \> n-w(\ove f ) \le  k-1 \= w(\ove f) \ge  n-k+1\;\;(2)\NN
(2) \> d(C) \ubrace{=}{\QUA{Oss3.1}{1}} \min w(C^*) \ge  n-k+1\;\;(3)\NN
d(C) \ubrace{\le}{\QUA{Prop3.3}{1}} n-\dim C +1 =  n -k +1 \NN
\qq \> d(C) = n -k +1 \= C\T{ e' MDS }
}
\end{proof}
\begin{prop}\ilabel{TroncatMDSestMDS}
	Sia $C\( F_q^{n}$ un codice lineare e sia 
	\eal{& \pi:C\longrightarrow C'=\pi(C)\NN
		(c_1,\dots,c_n) \mapsto (c_1,\dots,c_m)
	}
	la proiezione che tronca le ultime $n-m$ componenti. \\
	Se $n-m <  d(C)$, allora,
	\eal{&0.\;\;\pi\T{ e' un isomorfismo vettoriale}\NN
	1.\;\;C'\( F_q^m\T{ e' un codice con } \dim C=\dim C'\NN
	2.\;\;d(C') \ge  d(C) - (n-m)\NN
	3.\;\;C\T{ MDS } \>  C' \T{ MDS }
	}
	Nota: la $2.$ vale per un codice $C$ qualsiasi
\end{prop}
\begin{proof}
	\step{}{}
	\begin{prova}
	$\pi$ e' surriettiva (per definizione), ma e' anche iniettiva, basta
	infatti applicare la dimostrazione di \QUA{prop3.3}{1}, sostituendo
	$d-1$ con $n-m$.\\
	$\pi$ e' chiaramente lineare.
	\eal{&\pi \T{ lineare, biettiva } 
	\> \pi\T{ isomorfismo vettoriale } 
	\> \dim C'=\dim C
	}
	\end{prova}
	\step{}{}
	\begin{prova}
	Sia $c\in C$,
	\eal{&d(C)  \ubrace{=}{\QUA{oss3.1}{1}
	}  \min w(C^*) = w(\ove x)\;\;(1)\NN
d(C') = \min w(C'^*) = w(\pi(y))\;\;(2)\NN
%%w(\pi(c)) = w(c_1,\dots,c_m)= |\pgra{i\;|\;c_i \neq 0,\;i=1,\dots, m}| \le   |\pgra{i\;|\;c_i \neq 0,\;i=1,\dots, n}|=w(c)\;\;(*)\NN
w(\pi(c))  = w(c) - |\pgra{i\;|\;c_i \neq 0,\;\;i=m+1,\dots,n
}| \ubrace{\ge}{(1)}  d(C) - 
 |\pgra{i\;|\;c_i \neq 0,\;\;i=m+1,\dots,n
}| \ge  d(C) -(n-m)\>\NN
\ubrace{\>}{(2)}  d(C') \ge   d(C) -(n-m)\;\;(3)
}
	\end{prova}
	\step{}{}
	\begin{prova}
		\eal{&C\T{ MDS } \> d(C) = n- \dim C +1  \ubrace{=}{1.}
		n-\dim C' +1 \;\;(4)\NN
		d(C') \ubrace{\ge}{(3)}  d(C) -(n-m)  \ubrace{=}{(4)} 
		n-\dim C' +1  - n +m = 
		m - \dim C' +1 \NN
	d(C') \ubrace{\le}{\QUA{prop3.3}{1}} 
	m - \dim C' +1 \NN
	\qq \> d(C')  = m - \dim C' +1 \> C'\T{ MDS}
		}	
	\end{prova}
\end{proof}
\begin{defn}\ilabel{DefShortening}
	Sia $C\(F_q^n$ codice lineare, $m\le n$, e sia
	\eal{&\ove C = \pgra{c\in C\;|\;c_{m+1}=c_{m+2}=\dots=c_n=0}
	}
	sia data la proiezione
	\eal{&\pi:\ove C\longrightarrow \pi(\ove C)\NN
		(c_1,\dots,c_n) \mapsto (c_1,\dots,c_m)
		}
	allora, la funzione
	\eal{&\ove \pi: \mathcal{P}(F_q^n) \longrightarrow 
	 \mathcal{P}(F_q^m) \NN
	 C \mapsto \pi(\ove C)
	}
	viene chiamata \iemph{operazione di shortening}.
	$\pi(\ove C)$ viene chiamato $m$-shortening di $C$.
\end{defn}
\begin{prop}\ilabel{ShortMDSestMDS}
Sia $C\(F_q^n$ codice lineare e sia 
$C'=\pi(\ove C)$ lo $m$-shortening di $C$.\\
Se $n-m\le  k$, allora
\eal{&1.\;\;H=(h_1,\dots,h_n)\T{ matrice di controlo di C  } 
\> H'=(h_1,\dots,h_m)\T{ di controllo di $C'$, ($h_i$  colonna)}\NN
2.\;\;C \T{ MDS di tipo } [n,k] \> C' \T{ MDS di tipo } [m,k-(n-m)]
}
\end{prop}
\begin{proof}
	E' chiaro che $\pi$ e' un isomorfismo vettoriale, quindi
	\eal{&\pi\T{
	isomorfismo } \>  \dim C' = \dim \ove C\;\;(0)
	}
Sia $H=(h_1,\dots, h_n)$ una matrice di controllo di $C$, con $h_i$ colonna. 
\step{p0}{$H'=(h_1,\dots,h_n)$ e' di controllo per $C'$}
\begin{prova}
	\eal{&(x_1,\dots,x_m)\in C'  \ubrace{\=}{\T{def di }\pi}  (x_1,\dots,x_m,0,0,\dots,0)\in \ove C
	\=
	H\cdot  (x_1,\dot
s,x_m,0,0,\dots,0)\TR 
=0 \=\NN
x_1 h_1+\dots+x_mh_m=0 \= 
 H'\.  (x_1,\dots,x_m)=0
	}
\end{prova}
\eal{&C\T{ MDS } 
\> d(C) = n-k+1 ,\;\;k=\dim C 
\ubrace{\>}{\QUA{prop3.2}{1}} 
s= n-k,\;\T{ ogni insieme di $\le  s$ colonne di $H$ e' l.i. }\;\;(1)
\>\NN
\ubrace{\>}{H'=(h_1,\dots,h_m)} \T{ ogni insieme di $\le  s=n-k$ colonne di $H'$
e' l.i. }\;\;(2)\NN
(2)  \ubrace{\>}{m\ge n-k\T{ per Hp}} 
n-k\T{ colonne di $H'$ sono } l.i. \;\;(2.1)\NN
H\T{ di controllo } \> H\in n-k\* n\> H'\in n-k\* m\;\;(3)\NN
(2),(3) \> \rho(H') = n-k
\> \dim C' = m-(n-k) =k-(n-m)\;\;(4)\NN
d(C')=s'+1  \ubrace{=}{(2)} n-k+1 \ubrace{=}{(4)} n-(\dim C'+(n-m))+1
= m-\dim C' +1 
\> C'\T{ MDS}
}
\end{proof}

\begin{prop}
	TODO/Domanda: conoscendo $H$ matrice di controllo di $C$, qual'e' la
	matrice di controllo di $C'$ ottenuto tramite puncturing?
	(Hint: usare $H$ in forma standard).
\end{prop}

\section{BCH e Reed Solomon}
\def\d{{\delta}}
\def\a{{\alpha}}
\textbf{NOTA:} in questa sezione supponiamo sempre $(n,p)=1$.

\begin{defn}\ilabel{DefBCH}
	\eal{&
	C\T{ e' un codice BCH  } \definizione{\=} C=\pgra{c(x)\in
	F_{q}[x]_{n-1}\;|\;c(\a^b)=c(\a^{b+1})= \dots = c(\a^{b+\d-2})=0 }
	}
	dove $U_n=\gen{\a}=\pgra{1,\a,\a^2,\dots,\a^n}, \;b,\d>0,\;\d \le n$.
\end{defn}
\begin{lem}\ilabel{AlphaNDistinte}
Sia $C$ un BCH, allora
\eal{&\a^b,\;\a^{b+1},\; \dots ,\; \a^{b+\d-2}}
sono tutte distinte fra loro
\end{lem}
\begin{proof}
	Sia $0\le i<j\le \d -2$
	\eal{&0\le i<j\le \d -2 < \d \le n \> i<j< n \> j-i < j < n\;\;(1)\NN
	\a^{b+j}= \a^{b+i}  \ubrace{\=}{n=|U_n| = o(\a)}  b+j=b+i\;\;\Z_n\=
	i=j\;\;\Z_n \= n\div j-i  \ubrace{\=}{j-i<n}j-i=0\= j=i}
\end{proof}
\begin{prop}\ilabel{BCH-DistanzaDelta}
	Sia $C$ un codice BCH, allora 
	\eal{&1.\;\;C\T{ e' ciclico}\NN
	2.\;\;d(C) \ge  \d }
\end{prop}
\begin{proof}
	\step{}{Dim $1.$}
	\begin{prova}
		Basta applicare la \RE{Prop4.6}{24} alla definizione,
		considerando che 
		\eal{&\a\in U_n \> \a^i \in U_n}
	\end{prova}
	\step{}{Dim $2.$}
	\begin{prova}
	Supponiamo per assurdo che $d(C) < \d$,
	\eal{&d(C) < \d  \ubrace{\=}{\QUA{Oss3.1}{1}} 
	\exists c(x)\in C\-\pgra{0}:\;\; w(c(x)) < \d \;\;(1)}
Si ha
\eal{&c(x)=c_0+c_1x +\dots+ c_{n-1}x^{n-1}\in C  \ubrace{\=}{\T{def.}} 
c(\a^{i})=0 \;\;\forall i=b,b+1,\dots,b+\d-2\=\NN
\= 
\begin{bmatrix}
	1 & \a^b  & \a^{2b } & \dots &  \a^{(n-1)b } \\
	1 & \a^{(b+1)}  & \a^{2(b+1) } & \dots &  \a^{(n-1)(b+1) } \\
	\vdots \\
	1 & \a^{(b+\d-2)}  & \a^{2(b+\d-2) } & \dots &  \a^{(n-1)(b+\d-2) }
\end{bmatrix}
\begin{bmatrix}
	c_0\\
	c_1\\
	\vdots \\
	c_{n-1}
\end{bmatrix} = 0\;\;(2)\NN
w(c(x)) < \d \= \T{ esistono al piu' $\d-1$  componenti non nulle,
$c_{i_1},\dots,c_{i_{d-1}}$ di $c(x)$ }\;\;(3)\NN
(2)   \ubrace{\=}{H_i\T{ colonna}}  c_0H_1 +c_1 H_2 + \dots + c_{n-1}H_n =0
\ubrace{\=}{(3)} 
c_{i_1}H_{i_1+1} +c_{i_2} H_{i_2+1} + \dots + c_{i_{\d-1}}H_{i_{\d-1}+1} =0
\=  \NN
\=
\begin{bmatrix}
	\a^{i_1b} & \a^{i_2b}  & \a^{i_3b } & \ldots &  \a^{i_{\d-1}b } \\
	\a^{i_1(b+1)} & \a^{i_2(b+1)}  & \a^{i_3(b+1) } & \ldots & \a^{i_{\d-1}(b+1) } \\
	\vdots \\
 \a^{i_1(b+\d-2))} & \a^{i_2(b+\d-2)}  & \a^{i_3(b+\d-2) } & \ldots &  \a^{i_{\d-1}(b+\d-2) }
\end{bmatrix}
\begin{bmatrix}
	c_{i_1}\\
	c_{i_2}\\
	\vdots \\
	c_{i_{\d-1}}
\end{bmatrix} = 0\;\;(4)\NN
\T{Sia $A$ l'ultima matrice, si ha: }\NN
\qq \det A  \ubrace{=}{\T{mettendo in evidenza dalle colonne}}  \a^{i_1b}
\a^{i_2b} \dots  \a^{i_{\d-1}b}
\det \begin{bmatrix}
	1 & 1 & 1 & \ldots & 1 \\
	\a^{i_1} & \a^{i_2}  & \a^{i_3 } & \ldots & \a^{i_{\d-1} } \\
	\a^{2i_1} & \a^{2i_2}  & \a^{2i_3 } & \ldots & \a^{2i_{\d-1} } \\
	\vdots \\
 \a^{(\d-2)i_1} & \a^{(\d-2)i_2}  & \a^{(\d-2)i_3 } & \ldots &  \a^{(\d-2)i_{\d-1}}
\end{bmatrix}=\NN
\qq 
\ubrace{=}{\T{Vandermonde}} 
\a^{i_1b}
\a^{i_2b} \dots  \a^{i_{\d-1}b}\prod_{1\le j<h\le \d -1
}^{}(\a^{i_j}-\a^{i_h})\;\;(5)\NN
\det A  \neq 0  \ubrace{\=}{(5)}  \a^{i_j} \neq \a^{i_h}\;\;\forall j \neq
h\T{ questo e' vero per la }\see{AlphaNDistinte} \NN
\qq \> A\T{ e' invertibile }  \ubrace{\>}{(4)}  c_{i_1}=\dots=c_{i_{\d-1}}= 0
\ubrace{\=}{(3)}  c(x) =0
}
ma questo e' assurdo contro $c(x)\in C\-\pgra{0}$
	\end{prova}
\end{proof}
\begin{defn}
	$C$ \T{ e' RS (Reed-Solomon) } $\=$ $C$ e' BCH e inoltre $n\div q-1 $
\end{defn}
\begin{prop}\ilabel{RS-OssVarie}
	\label{RSOssVarie}
	Sia $C$ di Reed-Solomon, allora
	\eal{&1.\;\;U_n=\gen \a  \( F_q \NN
	2.\;\;\pmin{\a^i}{F_q} = x- \a^i\NN
	3.\;\;C\T{ e' generato da } g(x) = \prod_{i=b}^{b+\d-2}x-\a^{i}\in
	F_q[x],\T{
	ovvero: }\NN
	\qq \qq C=\pgra{q(x)g(x) \;|\; q(x)\in F_q[x],\;\; \deg q(x) + \deg
	g(x)  \le  n-1\T{ oppure } q(x)= 0}\NN
	4.\;\;d(C)=\d,\;\;\dim C = n - \d +1 ,\;\;\deg g(x) = \d -1\NN
	\T{ ovvero } C\T{ e' MDS di tipo } [ n, n-\d +1, \d]
	}
\end{prop}
\begin{proof}
	\step{}{Dim $1.$}
	\begin{prova}
		\eal{&C\T{ RS } \> 
		n\div q- 1  \ubrace{\>}{\QUA{Oss4.4.1}{18}} 
		U_n \( F_q
		}
	\end{prova}
	\step{}{Dim $2.$}
	\begin{prova}
		\eal{&\a^i\in U_n \( F_q \> 
		\pmin{\a^i}{F_q} = x- \a^i
		}
	\end{prova}
	\step{}{Dim $3.$}
	\begin{prova}
		Per la \RE{Prop4.6}{24} si ha
		\eal{&g(x)= \mcm\pton{\pmin{\a^i}{F_q}\;|\;
		i=b, b+1,\dots,b+\d-2
		}  \ubrace{=}{2.} 
		\mcm\pton{x-\a^i\;|\;
                i=b, b+1,\dots,b+\d-2
		}  \;\;(1)\NN
		\pgra{\a^i}\T{ distinte per la }
		\see{AlphaNDistinte},\;\;\deg x-\a^i =1 
		\> \pgra{x-\a^i}\T{ coprimi fra loro }
		\> \mcm \T{ e' il prodotto }
		}
	\end{prova}
	\step{}{Dim. $4.$}
	\begin{prova}
	Si ha
	\eal{&\deg g(x)  \ubrace{=}{3.,\;\;\see{AlphaNDistinte}}  \d -1 
	\ubrace{\>}{\RE{Prop4.3}{21}} \dim C = n-\deg g(x) = n-\d+1\;\;(1)}
	Inoltre,
	\eal{&n-\d +1  \ubrace{=}{(1)} \dim C \ubrace{\le } { \QUA{Prop3.3}{1}} 
	n-d(C) +1 \ubrace{\le  }{\see{BCH-DistanzaDelta}} 
	n- \d + 1  
	\> \sist{\dim C = n- \d + 1 \\
	\d=d(c)
	}
	}
	\end{prova}
\end{proof}
\begin{prop}\ilabel{RS-Coeffg(x)}
	\label{RSCoeffgx}
	Sotto le ipotesi di \see{RS-OssVarie}, sia $g(x)= g_0+g_1x+\dots+g_{\d-1}x^{\d-1}$ il generatore di
	$C$, allora
	\eal{&1.\;\; \pgra{ \lambda x^i g(x) \;|\; i\ge 0,\;\;\lambda \in F_q^*}
	\( \pgra{ c(x)\in C\;|\;w(c(x))=d(C)}\NN
	\qq 
	\T{Cioe', gli elementi di $\lambda x^i g(x)$ hanno peso minimo.
	Domanda: vale $\)$ ?}\NN
		2.\;\;g_{\d-1}= 1,\;\;g_h = (-1)^{\d-1-h}
		\sum_{i_1<i_2<\dots <i_{\d-1-h}} \a_{i_1}\a_{i_2}\dots
		\a_{i_{\delta-1-h}}\;\;\forall h=0,\dots,\d-2\NN
\qq 
\T{ dove:  } 
\pgra{\a_1,\dots,\a_{\d-1}}= \pgra{\a^i\;|\;
                i=b, b+1,\dots,b+\d-2
		}\NN
	3.\;\; g_i \neq 0\;\;\forall i\NN
	}
\end{prop}
\begin{proof}
	\step{}{Dim. $1.,3.$}
	\begin{prova}
	\step{}{$w(g(x))=d(C)$}
	\begin{prova}
		\eal{&\deg g(x)  \ubrace{=}{\see{RS-OssVarie}} 
		\d -1 \> g(x)=g_0+g_1x+\dots+g_{\d-1}x^{\d-1} \;\;(1)\NN
		w(g(x) ) =| \pgra{i\;|\; g_i \neq 0}| \ubrace{\le }{(1)} \d\NN
		d(C)  \ubrace{=}{\see{RS-OssVarie}}  \d,\;\;g(x)\in C \>
		w(g(x)) \ge  d(C) =\d\NN
		\qq \> w(g(x)) = \d = d(C)\;\;(2)
		}
	\end{prova}
	Inoltre, $x^ig(x)$ e' $g(x)$ ``spostato'', ovvero,
	\eal{&g(x) \simeq  (g_0,g_1,\dots, g_{\d-1},0,0,\dots,0) \> x^ig(x) \simeq (g_i,
	g_{i+1},\dots)
	} e poiche' $C$ e' ciclico,
	$x^ig(x)\in C$.\\
	Infine, 
	\eal{&(2) \> g_i \neq 0\;\;\forall i \;\;(3)\NN
	\lambda g_i =0  \ubrace{\=}{g_i \neq 0}  \lambda =0
	}
	\end{prova}
	\step{}{Dim. $2.$}
	\begin{prova}
		\eal{&g(x)\T{ monico } \> g_{\d-1}=1}
Gli altri coefficienti si ricavano applicando le formule di
Viete' (vedi \AC{formuleviete}) alla \see{RS-OssVarie}
	\end{prova}
\end{proof}
\begin{prop}\ilabel{RS-Proiezione}
	\label{RSProiezione}
Sia $\pi$ la proiezione che tronca le ultime $n-m$ componenti:
\eal{&\pi:{F_q}^n \longrightarrow  {F_q}^m,\;\;m<n\NN
(a_1,\dots,a_n)  \mapsto (a_1,\dots,a_m) 
}
Se $C$ e' RS, si ha
\eal{&\pi(C) \T{ e' un codice MDS di tipo $[m,n-\d+1,\d-(n-m)]$, ovvero: }\NN
\qq 
\dim \pi(C)   = \dim C = n-\d+1,\;\;d(\pi(C)) = \d-(n-m)
}
Questa proposizione permette di costruire codici MDS a partire dai codici MDS
 di Reed-Solomon.
\end{prop}
\begin{proof}
	Nota: questa proposizione e' una diretta conseguenza di
	\see{TroncatMDSestMDS}. Diamo qui di seguito una dim. alternativa.\\
	Sia $C'=\pi(C)$
	\step{}{$\pi$ e' surriettiva e lineare}
	\begin{prova}
	\end{prova}
	\step{}{Dim. che $d(C')=\d-(n-m)$}
	\begin{prova}
		Per la \see{TroncatMDSestMDS} si ha
		\eal{&d(C') \ge  d(C)-(n-m)}
		Sia $g(x)\simeq (g_0,g_1,\dots, g_{\d-1},0,0,\dots,0)$ il generatore di $C$ (\vedi{RSOssVarie}),
		\eal{&g(x)\in C  \ubrace{\>}{C\T{ ciclico}} 
		x^{n-d}g(x) \in C\NN
		x^{n-d}g(x)=(0,0,\dots,0,g_0,g_1,\dots,g_{\d-1})=\T{
		$g(x)$ spostato negli ultimi posti }\NN
		\pi(x^{n-d}g(x))
		=(0,0,\dots,0,g_0,g_1,\dots,g_{\d-1-(n-m)})\;\;(1)\NN
		g_i \neq 0\;\;\forall i \T{ \vedi{RSCoeffgx} } \;\;(2)\NN
		(1), (2) \> w(      \pi(x^{n-d}g(x))    ) 
		= (\d-1-(n-m) )+1
		\> d(C') = \min w(C'^*) \le  \d-(n-m)\>\NN
		\ubrace{\>}{\sref{p0}} d(C') = \d-(n-m)
\;\;(3)
		}
	\end{prova}
	\step{}{$\dim C'=\dim C$}
	\begin{prova}
	Per la \see{RSOssVarie}, $\dim C= n-\d+1$.\\
Per la \RE{prop4.3}{21}, una matrice generatrice per $C$ e' 
\eal{&G=\begin{bmatrix}
	g_0 & g_1 & \dots & g_{\d-1} & 0  & 0 & \ldots & 0\\
	0 & g_0 & g_1 & \dots & g_{\d-1} & 0   & \ldots & 0\\
	0 & 0 & g_0 & g_1 & \dots & g_{\d-1} & 0 & \ldots & 0\\
	\vdots \\ 
	0 & 0 & \ldots & 0 & g_0 & g_1 & \dots & g_{\d-1}
\end{bmatrix}
\in n-\d+1\* n \NN
G\T{ generatrice per C }  \ubrace{\>}{\QUA{prop3.3.1}{4}}  G\T{ di controllo
per }C^{\perp }\NN
C\T{ RS }  \ubrace{\>}{\see{RSOssVarie}} C\T{ MDS } d(C) = \d 
\ubrace{\>}{\QUA{prop3.4}{2}} \orto C\T{ MDS } d(\orto C) = n-d(C)+2= 
n-\d+2\;\;(4)\NN
d(\orto C)  \ubrace{=}{\QUA{prop3.2}{1}} s+1  \ubrace{\>}{(4)}  s=n-\d+1
\> \T{ qualsiasi insieme di } s \T{ colonne di } G\T{ e' l.i. } \> \NN
\>\T{
qualsiasi minore di ordine } n-\d+1 \T{ e' invertibile }\;\;(5)\NN
G=\begin{bmatrix}
	G_1\\
	G_2\\
	\vdots\\
	G_{n-\d+1}
\end{bmatrix},\;\T{ $G_i$ riga } \NN
G'= \pi(G) = \begin{bmatrix}
	\pi(G_1)\\
	\vdots\\
	\pi(        G_{n-\d+1}
)
\end{bmatrix} \in n-\d+1 \* m\;\;(6)\NN
\sist{(5)\\
(6)\\
n-\d+1 \le  m } \> \T{ le righe di G' } sono l.i.  \ubrace{\>}{\pi(G_i)\in C'}
 \dim C' \ge  \dim C\NN
 \pi\T{ lineare e surriettiva } \>  \dim C' \le \dim C\NN
  \qq \> \dim C' =\dim C
}
	\end{prova}
\end{proof}
\begin{exemp}
	Vogliamo costruire un codice con $n=8$ (parole di $8$ caratteri),
	$e=2$ (correzione di due errori), MDS.
	\eal{&\frac{d-1}{2} \ubrace{=}{\RE{prop2.1}{10}} e=2  \> d=5\NN
	MDS \> k=n-d+1 = 8-5+1=4
	}
	Quindi cerchiamo un codice di tipo $[8,4,5]$.\\
	Come campo scegliamo $F_9$. Costruiamo un RS con $b=1$\\
	\eal{&RS \> d=\d=\deg g(x) +1\NN
	F_9=F_{3^2}\simeq\frac{F_3[x]}{(x^2+1)} \simeq
	F_3[i]=\pgra{
	a+ib\;|\;a,b\in F_3} \NN
	F_9^* \T{ ciclico },\;\;|F_9^*|=8  \ubrace{\>}{\T{biezione tra i
	divisori di $|G|$ e i sottogruppi}} 
	\exists ! \T{ sottogruppo di ordine } 4 \T{ ed e' }\gen
	i=\pgra{1,i,-1,-i}\NN
	\T{ L'unico sottogruppo di ordine 2} e' \pgra{1,-1}\( \gen i\NN
	1+i\notin \gen i,\;\;1+i \neq 1 \> o(1+i ) = 8  \> F_9^* =\gen 1+i\NN
	\T{Sia } \a = 1+i\NN
	o(\a)=8 \> U_8=\gen \a \NN
	\deg g(x)  \ubrace{=}{\see{RSOssVarie}} \d -1 = 5-1=4
	\ubrace{\>}{\see{RSOssVarie}} g(x)  =
	(x-\a)(x-\a^2)(x-\a^3)(x-\a^4)=\NN
	=(x-i-1)(x-2i)(x-1-2i)(x+1)\NN
	C(x) = \pgra{q(x)g(x)\;|\;q(x)\in F_9[x],\;\deg q(x) \le 3 \T{ oppure }q(x)=0}
	}
\end{exemp}
\subsubsection{Trasformata di Fourier}
\def\b{{\beta}}
\def\F{{\mathfrak{F}}}
\begin{defn}\ilabel{Fourier}
	Trasformata di Fourier finita.\\
	Sia $U_n=\gen \b$, supponiamo sempre $(n,p)=1$,
	, con $p=\oname{char} F_q$,
	e inoltre che $U_n\(F_q\= n\div q-1$.
\\
	La trasformata di Fourier finita, relativa a $\b$,  e' la seguente applicazione:
	\eal{&\F_\b:F_q[x]_{n-1} \longrightarrow  F_q[x]_{n-1}\NN
	v(x)=v_0+v_1x+\dots+v_{n-1}x^{n-1}
	\mapsto v^*(x)=v(\b^0)+v(\b^1)x+\dots+ v(\b^{n-1})x^{n-1}
}
Nota\footnote{Se il campo in cui operiamo e' $\mathbb{C}$, allora
\eal{&\b = e^{i\frac{2\pi}{n}}= \cos \frac{2\pi}{n}+ i\sin \frac{2\pi}{n}}
per questo motivo l'applicazione sopra definita si chiama Trasformata di
Fourier Finita}
In termini vettoriali:
\eal{&\F_\b:F_q^{n}\longrightarrow F_q^n\NN
v=(v_0,\dots,v_{n-1}) \mapsto v^*=(v(\b^0), \dots, v(\b^{n-1}))\NN
\T{ dove } v(\b^j)=v\.
%\ubrace{\.}{\T{prod. scalare}}
(
(\b^j)^0,
(\b^j)^1,
(\b^j)^2,\dots,
(\b^j)^{n-1})
= v\. (\b^0, \b^j,\b^{2j}, \dots, \b^{(n-1)j)}
}
Notazione:
\eal{&v^*\definizione{=}\F(v)\NN
v_*\definizione{=}\inv \F (v)}
\end{defn}
\begin{prop}\ilabel{PropFourier}\qq\\
	\begin{enumerate}
		\item Fourier e' un isomorfismo vettoriale.
		\item La matrice associata e' la matrice di Vandermonde
			\eal{&A_{ij}=\b^{ij}\;\;\forall i,j=0,\dots,n-1\NN
			A\in n\*n
			}
			(in questo caso numeriamo gli elementi di $A$ a
			partire da $0$.
			\eal{&v^* = Av,\;\;\T{ dove }v^*,v\T{ si intendono
			come colonne}}
		\item L'inversa di $\F$ e':
			\eal{&1.\;\;\inv { (\F_\b)} = \frac{1}{n}\F_{\b^{-1}}\NN
			2.\;\;w_*\definizione{=}\F_{\b^{-1}}(w)=
		(w(\b^0), w(\b^{-1}),w(\b^{-2}), \dots, w(\b^{-(n-1)}))
		=
		(w(\b^{n-n}), w(\b^{n-1}),w(\b^{n-2}), \dots, w(\b^{1}))\NN
		3.\;\;
		(\inv  A)_{ij}=\frac{1}{n}\b^{-ij}
		}
		Nota\footnote{la $3.$ da' esplicitamente l'inversa della
		matrice di Vandermonde $A$}.
	\end{enumerate}
\end{prop}
\def\a{\alpha}
\begin{proof}
	\step{}{Dimostriamo che $\F$ e' lineare ed invertibile}
	\begin{prova}
Calcolare un polinomio $v(x)$ in un elemento $v(\a)$ equivale a effettuare un
prodotto scalare. Per questo motivo possiamo esprimere $\F$ direttamente con
una matrice:
	\eal{&
	v^* \ubrace{=}{\T{def. di $\F$} }
	\begin{pmatrix}
	v(\b^0)\\
	v(\b^1)\\
	v(\b^2)\\
	\vdots\\
	v(\b^{n-1})
	\end{pmatrix}
	= \NN
	\qq =\begin{pmatrix}
 (\b^0, \b^0,\b^{0}, \dots, \b^{0})\.v\\
 (\b^0, \b^1,\b^{2}, \dots, \b^{(n-1)})\.v\\
 (\b^0, {(\b^1)}^2,\pton{\b^{2}}^2, \dots, \pton{\b^{(n-1)}}^2)\.v\\
\vdots\\
 (\b^0, \b^j,\b^{2j}, \dots, \b^{(n-1)j})\.v\\
 \vdots\\
 (\b^1, \b^{n-1},\b^{2(n-1)}, \dots, \b^{(n-1)(n-1)})\.v
	\end{pmatrix}
	= \begin{pmatrix}
		\b^0& \b^0&\b^{0}& \dots& \b^{0}\\
 \b^0& \b^1&\b^{2}& \dots& \b^{(n-1)}\\
\vdots\\
\b^0& \b^j&\b^{2j}& \dots& \b^{(n-1)j}\\
 \vdots\\
\b^1& \b^{n-1}&\b^{2(n-1)}& \dots& \b^{(n-1)(n-1)}
	\end{pmatrix} v
	}
	Sia $A$  l'ultima matrice. $A$ e' una matrice di Vandermonde formata
	sulle radici $\pgra{\b^0,\b^1,\dots,\b^{n-1}}=U_n$. Quindi e'
	invertibile.
	\end{prova}
	\step{}{Calcoliamo $\inv \F$}
	\begin{prova}
		\step{}{Dim. che 
 $\inv { (\F_\b)} = \frac{1}{n}\F_{\b^{-1}}$	
		}
		\begin{prova}
\eal{&v^*=\F_\b(v) = (v(\b^0), \dots, v(\b^{n-1})) \;\;(1)\NN
\F_{\b^{-1}}(v^*)=( v^*(\b^0),\;v^*(\b^{-1}),\;\dots,\; v^*(\b^{-(n-1)}))\;\;(2)\NN
\T{Poniamo } \ove \a \definizione{=} (\a^0,\a,\dots,\a^{n-1})\NN
v^*(\b^{-i})= v^*\.\ove \b ^{-i}
\ubrace{=}{(1)}  \sum_{j=0}^{n-1} v(\b^{j}) \b^{-ij}
= 
\sum_{j=0}^{n-1} (v\. \ove \b^{j})\b^{-ij}
=
\sum_{j=0}^{n-1} \sum_{k=0}^{n-1}v_k \b^{jk}\b^{-ij}
=
\sum_{k=0}^{n-1} v_k\sum_{j=0}^{n-1} \b^{j(k-i)}\;\;(3)\NN
\sum_{j=0}^{n-1} \b^{j(k-i)} = 
\sum_{j=0}^{n-1} \pton{\b^{(k-i)}}^j = \NN
\qq \b^{k-i} =1 \= 
k=i\;\;(\Z_n) 
\ubrace{\=}{0\le i,k\le n-1}  k=i\;\;(*)\NN
\ubrace{=}{\see{SommaDiUnita},\;(*)} 
\sist{n& k=i \= \b^{(k-i)}=1\\
0 & k \neq i
} = n\delta_{ik}\;\;(4)\NN
(3),(4) \> v^*(\b^{-i})= \sum_{k=0}^{n-1} v_k n\delta_{ik} = nv_i\;\;(5)\NN
\F_{\b^{-1}}(v^*) \ubrace{=}{(2),(5)} n(v_0,v_1,\dots,v_{n-1})
\> \frac{1}{n}\F_{\b^{-1}}(v^*)  = v\;\;(6)\NN
\T{Abbiamo cosi' dimostrato che: }\NN
\pton{\frac{1}{n}\F_{\b^{-1}}}\circ \F_{\b}(v)=v
\> 
\pton{\frac{1}{n}\F_{\b^{-1}} }\F_{\b}=\id 
\ubrace{\>}{\F_\b\T{ invertibile } } 
\pton{\frac{1}{n}\F_{\b^{-1}}}\F_{\b}\inv{(\F_{\b})}=
\inv{(\F_{\b})}
\= \frac{1}{n}\F_{\b^{-1}}  = \inv{(\F_{\b})}
}
		\end{prova}
	\end{prova}
\end{proof}
\def\d{{\delta}}
\def\s{{\sigma}}
\begin{prop}\ilabel{CostruzioneDiRSconFourier}
	I codici di Reed-Solomon, con $b=1$, si ottengono dalla costruzione
	\see{CostruzioneMDS} scegliendo $S=U_n$ e $k-1=n-\d$.
	(nota\footnote{quindi questa proposizione e' una dimostrazione
	alternativa del fatto che i codice RS sono MDS})
\end{prop}
\begin{rem}
	La costruzione \see{CostruzioneMDS} fornisce un metodo per costruire
	codici MDS. Tuttavia, conviene usare i codici di Reed-Solomon, perche'
esistono algoritmi di decodifica molto efficienti.
\end{rem}
\begin{proof}
	Sia $U_n=\gen \b$.
	\step{}{Dimostriamo che  il codice 
	\eal{&D = \pgra{(f(\b^0),\dots,f(\b^{n-1}))\;|\;f\in F_q[x]_{n-\d}}
	}
	e' isomorfo al codice di RS definito da $\b$, scegliendo $b=1$. 
	}
	\begin{prova}
	\eal{&C\T{ e' MDS definito da $\b$, con $b=1$ } \=
\NN
	\ubrace{\=}{def.} 
(n,p)=1,\;n\div q-1 ,\;\	C=\pgra{c(x)\in
F_q[x]_{n-1}\;|\;c(\b^i)=0\;\;\forall i=1,\dots,\delta-1}\;\;(1)\NN
\T{ dove } U_n =\gen \b
}
Poiche' $(n,p)=1,\;n\div q-1$, possiamo considerare  le trasformate di Fourier
dei $c(x)$, secondo $\inv \b$:
\eal{&\F_{\inv \b}\pton{ c(x)} =  c^*(x) =
c(1)+c(\inv \b)x+c(\b^{-2})x^2+\dots+c(\b^{-(n-1)})x^{n-1}=\NN
=
c(1)+c(\b^{n-1})x+c(\b^{n-2})x^2+\dots+c(\b^{1})x^{n-1} \ubrace{=}{(1)} 
c(1)+c(\b^{n-1})x+c(\b^{n-2})x^2+\dots+c(\b^{\delta}) x^{n-\delta}
\;\;(2)\NN
\T{Sia } C'  = \F_{\inv \b}\pton{C} \NN
(2) \> C' \(  F_q[x]_{n-\delta}\;\;(3)\NN
\F_{\inv \b}\T{ isomorfismo (\vedi{PropFourier})}
\> \dim C' = \dim C  \ubrace{=}{\see{RSOssVarie}}  n-\delta+1 = \dim  F_q[x]_{n-\delta}\;\;(3.1)\NN
(3),(3.1) \>  C'=F_q[x]_{n-\delta}\;\;(4)
}
$C$ si ottiene con l'inversa di $\F_{\inv \b}$:
\eal{&\inv{(\F_{\inv \b})}  \ubrace{=}{\see{PropFourier} } 
\frac{1}{n}\F_\b \> 
C=\frac{1}{n}\F_\b(C') \NN
  c(x)\in C \= c(x) = \frac{1}{n}\sum_{i=0}^{n-1}c^*(\b^{i})x^i
\leftrightarrow
\pton{c^*(\b^{0}),\dots, c^*(\b^{n-1})}\ubrace{\in}{(3)} D\NN
\qq \> C \simeq D
}
	\end{prova}
\end{proof}
\subsubsection{Decodifica}
\begin{defn}\ilabel{DefRSDecodifica}
	Sia $C\(F_q^n$ un codice RS, su $U_n=\gen{\b}$,  con $b=1$, $\dim C =k,\;d(C) =\delta$.\\
	Sia $c(x)$ la parola trasmessa e
	$d(x)=c(x)+e(x)$ la parola ricevuta, con $e(x)$ errore.\\
	Supponiamo che l'errore si possa correggere, ovvero (vedi
	\RE{Prop2.1}{10}) \eal{&w=w(e(x)) \le t=\floor{\frac{\delta-1}{2}}}
	Definiamo i seguenti oggetti:
	\eal{&\ove b=(b_1,\dots,b_w)=(e_{i_1},\dots,e_{i_w})\T{ vettore dei
	coefficienti non nulli di $e(x)$, con } 0\le i_1<\dots<i_w\le n-1\NN
\ove a=	(a_1,\dots,a_w)=(\b^{i_1},\dots,\b^{i_w})
	\T{ vettore di posizione dei coefficienti $\ove b$}
	}
	nota\footnote{esiste una corrispondenza biunivoca tra
	$\pgra{\b^{i_j}\;|\;j=1,\dots,w}$ e $\pgra{i_{j}\;|\;j=1,\dots,w}$.
	Per questo motivo conoscere $\ove a$ equivale a conoscere
	$(i_1,\dots,i_w)$}\\
	L'\iemph{error locator polynomial} e':
	\eal{&\sigma(x)= \prod_{i=1}^{w}x-a_i
	}
	Le \iemph{sindromi generalizzate} sono:
	\eal{&s_j=d(\beta^j) \;\;\forall j=1,\dots,\delta-1
	}
\end{defn}
\begin{prop}
	\ilabel{PropRSDecodifica}	
	Sotto le ipotesi di \see{DefRSDecodifica}, si ha
	\eal{&1.\;\; e_j \neq  0 \> \sigma ( \b^j) =0\;\;\forall j=1,\dots,n-1\NN
	2.\;\;s_j=d(\beta^j)=e(\beta^j)\;\;\forall j=1,\dots,\delta-1\NN
	3.\;\;s_j\sigma_0+s_{j+1}\sigma_1+\dots+s_{j+w}\sigma_w =0\;\;\forall
	j=1,\dots,w\NN
	4.\;\;\ove b \T{ e' soluzione del sistema } 
		A\begin{pmatrix}
				b_1\\\vdots\\b_w
			\end{pmatrix}=\begin{pmatrix}
				s_1\\\vdots\\s_w
			\end{pmatrix},\;\T{ dove 
		dove $A$ e' la matrice $A=(a_j^i)_{i=1,\dots,w;\;j=1,\dots,w}$
		}\NN\NN
		\qq \T{la soluzione esiste ed e' unica}\NN
		5.\;\; (\s_0,\dots,\s_{w-1})\T{ e' soluzione di }
	M_w\begin{pmatrix}
				\s_0\\
				\s_1\\
				\vdots\\
				\s_{w-1}
			\end{pmatrix}=
			-\begin{pmatrix}
				s_{w+1}\\
				s_{w+2}\\
				\vdots\\
				s_{2w}
			\end{pmatrix},\;\;\T{ dove
			$M_h=(s_{i+j-1})_{i=1,\dots,h;\; j=1,\dots, h}$}\NN
		\qq \T{la soluzione esiste ed e' unica}\NN
	6.\;\;w=\rho(M_t)
	}
\end{prop}
\begin{proof}
	\step{}{}
	\begin{prova}
		\eal{&e_j \neq 0 \> e_j\T{ e' un coefficiente di } e(x) \T{
		non nullo } \> \exists k:\;j=i_k  \ubrace{\=}{\T{ def di
		$		\sigma(x) $}} \b^{i_k}\T{ radice di }\sigma(x)
		\= \sigma(\b^j)=0}
	\end{prova}
	\step{}{}
	\begin{prova}
		\eal{&
		1\le j\le\delta-1,\; c(x)\in C\T{ ReedSolomon}  \>
		c(\b^j)=0\;\;(1)\NN
		s_j \ubrace{=}{\T{def}} d(\b^j) = c(\b^j)+e(\b^j)  \ubrace{=}{(1) } =e(\b^j) \;\;\forall j
		=1,\dots,\delta-1
		}
	\end{prova}
	\step{}{}
	\begin{prova}
		\step{}{Dimostrazione $1$}
		\begin{prova}
Per definizione di $\ove b$:
\eal{&e(x) = b_1x^{i_1}+\dots+b_wx^{i_w}\NN
e(\b^j) =  b_1\b^{ji_1}+\dots+b_w\b^{ji_w} 
\ubrace{=}{\T{def di }\ove a} b_1a_1^j+\dots+b_wa_w^j\;\;(1.1)\NN
s_j \ubrace{=}{2.}  e(\b^j) \ubrace{=}{(1.1)}
 b_1a_1^j+\dots+b_wa_w^j \;\;\forall j=1,\dots,\delta-1\;\;(1.2)}
	Poniamo $b_i=a_i=0\;\;\forall w<i\le t$.
	\eal{&a_j=\beta^{i_j} \neq 0 \> e_{i_j} \neq 0  \ubrace{\>}{1.} 
	\sigma(a_j)=0\NN
a_i=0 \=  i>w\NN
\qq \> b_ia_i^j \sigma(a_i) =0\;\;\forall i=1,\dots,t\;\;(1.3)\NN
(1.3) \> \sum_{i=1}^t b_ia_i^j \sigma(a_i) =0\;\;(1.4)\NN
\sum_{i=1}^t b_ia_i^j \sigma(a_i)
= \sum_{i=1}^t b_ia_i^j 
\pton{\s_0+\s_1a_i + \dots + \s_{w}a_i^w }
= \s_0\pton{\sum_{i=1}^t b_ia_i^j }+ \s_1 \pton{\sum_{i=1}^t b_ia_i^{j+1}}
+ \dots + \s_w \pton{\sum_{i=1}^t b_ia_i^{j+w}}= \NN
\qq \sum_{i=1}^t b_ia_i^{j+h}  \ubrace{=}{(1.2),\;a_i=0\;\forall i>w}
s_{j+h}\;\;\forall j=1,\dots,\delta-1-h(*)\NN
\ubrace{=}{(*)} \s_0s_j+\s_1s_{j+1}+\dots+\s_w s_{j+w}\;\;(1.5)\NN
(1.4),\;(1.5) \> \s_0s_j+\s_1s_{j+1}+\dots+\s_w s_{j+w} =0\;\;\forall
j= \delta-1-w\;\;(**)
}
In particolare, poiche' $2w \le 2t \le \delta-1\> w\le \delta-1-w$, la $(**)$
vale per $j=1,\dots,w$.
		\end{prova}
		\step{}{Dimostrazione alternativa $2$}
		\begin{prova}
	Diamo solo una bozza di dimostrazione.

		\eal{&\F_{\inv \b}(e(x)) =e^*(x) =
		\sum_{i=0}^{n-1}e(\b^{n-i})x^i\;\;(1)\NN
		e(x) = \inv {\pton{\F_{\inv \b}}} (e^*(x)) 
		= \frac{1}{n}\F_{\b}(e^*(x)) = \frac{1}{n}\sum_{i=1}^{n-1}
		e^*(\b^{i})x^i\;\;(2)
		\NN
		e_k \> e_k\sigma(\b^k) =0;\;\;e_k \neq 0 \ubrace{\>}{1.} 
		e_k\sigma(\b^k)=0\NN
		\qq \> 
		e_k\sigma(\b^k)  \ubrace{=}{1.} 0 \;\;\forall k=1,\dots,n-1
\;\;(3)\NN
(3) \ubrace{\=}{(2)} 
e^*(\b^{k})\sigma(\b^k)=0\;\;\forall k=1,\dots,n-1
\= \forall \b^k\in U_n \T{ e' una radice di }
e^*(x)\sigma(x) \= x^n-1 \div e^*(x)\sigma(x) \;\;(4)\NN
\deg e^*(x) \le  n-1, \;\deg \sigma(x) = w \> \deg e^*(x)\sigma(x)  \le
n+w-1\;\;(5)\>\NN
\ubrace{\>}{(4),(5)} e^*(x)\sigma(x) = (x^n-1) (h_0+h_1x+\dots+h_{w-1}x^{w-1})
\;\;(6) \>\NN
\>\T{ in }  e^*(x)\sigma(x) \T{ non sono presenti i termini di grado
$r:\; w\le  r\le  n-1$ } \> 
\T{ i loro coefficienti sono nulli }\;\;(7)\NN
\T{calcoliamo i coefficienti sviluppando il prodotto e usando la  (1): } \NN
(7) \= \sum_{i=0}^{r}\sigma_{r-i}e(\b^{n-i})=0\;\;\forall r=w,w+1,\dots,n-1
}
%%%TODO%%%
%%%TODO%%%
%%%TODO%%%
Utilizzando la $2.$, con un'opportuno cambio di variabili e un'opportuna
scelta di $\b$ si ottiene la
tesi.
%\textbf{TODO: esplicitare il cambio di variabili}
%%%TODO%%%
%%%TODO%%%
%%%TODO%%%
\end{prova}
\end{prova}
\step{}{}
	\begin{prova}
\eal{&(1.2) \ubrace{\>}{w\le t=\floor{\delta-1/2} < \delta-1}  s_j= b_1a_1^j+\dots+b_wa_w^j
\;\;\forall j=1,\dots,w\=\NN
\= \begin{pmatrix}
a_1 & \ldots & a_w\\
a_1^2 & \ldots & a_w^2\\
\vdots\\
a_1^w & \ldots & a_w^w\\
\end{pmatrix}\ove b = \begin{pmatrix}
	s_1\\
	\vdots\\
	s_w
\end{pmatrix}\NN
\T{mettendo in evidenza nelle colonne di $A$: }
\det A = a_1\cdots a_w \begin{vmatrix}
	1& \ldots & 1\\
	a_1& \ldots & a_w\\
	\vdots\\
	a_1^{w-1}& \ldots & a_w^{w-1}
\end{vmatrix}
\ubrace{=}{\T{Vandermonde }} 
  a_1\cdots a_w \prod_{i<j}^{}(a_i-a_j)}
Poiche' 
\eal{&
a_i \neq a_j\;\;\forall i \neq j,\;\;  a_i \neq 0\;\;\forall i
\> 
\det A \neq 0\;\;(9.2)
}
il sistema ammette un'unica soluzione.
	\end{prova}
	\step{}{}
	\begin{prova}
\eal{&\sigma(x)\T{ e' monico } \> \sigma_w = 1
\ubrace{\>}{3.} -s_{j+w} = 
s_j\sigma_0+s_{j+1}\sigma_1+\dots+s_{j+w-1}\sigma_{w-1} =0\;\;\forall
j=1,\dots,w
\= \NN
\=\begin{pmatrix}
	s_1 & s_2 & \ldots & s_{1+w-1}\\
	s_2 & s_3 & \ldots & s_{2+w-1}\\
	\vdots\\
	s_{j} & s_{j+1} & \ldots & s_{j+w-1}\\
	\vdots\\
	s_{w} & s_{w+1} & \ldots & s_{2w-1}\\
\end{pmatrix} \begin{pmatrix}
	\sigma_0\\
	\vdots\\
	\sigma_{w-1}
\end{pmatrix}
= -\begin{pmatrix}
	\s_{w+1}\\
	\vdots\\
	\s_{2w}
\end{pmatrix}
\= M_w  \begin{pmatrix}
        \sigma_0\\
        \vdots\\
        \sigma_{w-1}
\end{pmatrix}
= -\begin{pmatrix}
        \s_{w+1}\\
        \vdots\\
        \s_{2w}
\end{pmatrix}
}
Resta da dimostrare che la soluzione esiste ed e' unica.\\
Per la $(1.2)$, la matrice $M_w$ si puo' cosi' decomporre:
\eal{&M_w=A_w'\diag (b_1a_1,\dots,b_{w}a_w) {(A_w')}^{\TR}\;\;\;(10)\NN
\T{ dove } A_w' = 
\begin{pmatrix}
	1& \ldots & 1	 \\
	a_1& \ldots & a_w \\
	\vdots		   \\
	a_1^{w-1}& \ldots & a_w^{w-1}
\end{pmatrix}
}
infatti:
\eal{&\diag (b_1a_1,\dots,b_wa_w) {(A_w')}^{\TR} =
\begin{pmatrix}
	b_1a_1 (1,a_1,\dots,a_1^{w-1})\\
	b_2a_2 (1,a_2,\dots,a_2^{w-1})\\
	\vdots\\
	b_wa_w (1,a_w,\dots,a_w^{w-1})
\end{pmatrix}\NN
\pton{A_w'\diag (b_1a_1,\dots,b_{w}a_w) {(A_w')^{\TR}}}_{ij}
= (A_{w'})_i
(\diag (b_1a_1,\dots,b_wa_w) {(A_w')}^{\TR})^{j}
= 
\begin{pmatrix}
a_1^{i-1}& \ldots & a_w^{i-1}
\end{pmatrix} 
\begin{pmatrix}
	b_1a_1  a_{1}^{j-1}\\
	b_2a_2  a_{2}^{j-1}\\
	\vdots\\
	b_wa_w  a_{w}^{j-1}\\
\end{pmatrix}
= \NN
=
b_1a_1 a_{1}^{j-1} a_{1}^{i-1}
+ \dots + b_wa_w a_{w}^{j-1} a_{w}^{i-1} 
= 
b_1a_{1}^{i+j-1} 
+ \dots + b_w a_{w}^{i+j-1} 
\ubrace{=}{(1.2)} s_{i+j-1}  \ubrace{=}{\T{def. di $M_w$}}
(M_w)_{ij}\;\;\;(10.1)
}
Quindi,
\eal{&\det M_w = (\det A_w)^2 \det\pton{ \diag(b_1a_1,\dots,b_wa_w)}
=b_1a_1\cdots b_wa_w  (\det A_w)^2  \ubrace{ \neq }{b_i \neq 0\T{ per def di
$\ove b$,\;(9.2)}} 0
}
\end{prova}
\step{}{}
\begin{prova}
Estendiamo il vettore $\ove b$ ponendo $b_i=0\;\;\forall i>w$ e scegliamo
$a_{w+1},\dots,a_{t}$ in modo che $\pgra{a_1,\dots,a_t}$ siano tutti distinti
fra loro\footnote{$\pgra{a_1,\dots,a_{w}}$ sono gia' distinti fra loro}. Si ha:
	\eal{&M_h=
M_h=A_h'\diag (b_1a_1,\dots,b_{h}a_h) {(A_h')}^{\TR}\;\;
\forall w\le h\le t
\;\;\;
(11)
	}
	infatti, basta rileggere la $(10.1)$ considerando che
	$b_i=0\;\;\forall i>w$.
	\eal{&\pgra{a_1,\dots,a_t}\T{ distinti fra loro } \ubrace{\>}{A_h\T{
	matrice di Vandermonde }} A_h'\T{ invertibile } \forall w\le h\le t
	\;\;(11.1)
}
$h=t$ e' il massimo indice che possiamo prendere perche':
\eal{&(M_t)_{t,t}=s_{2t-1}\NN
\T{gli $s_j$ sono $s_1,\dots,s_{\delta-1}$ }\NN
2t-1 \ubrace{\le }{t=\floor{\delta-1/2}} \delta-1
}
Quindi, 
\eal{&
(11),\;(11.1)  \ubrace{\>}{\AL{proprangodiAMeqrandoMAeqrangoA}} 
\rho(M_t) = \rho(\diag(b_ia_i\;|\;1\le i\le t)) = \NN
=t-|\pgra{1\le i\le t\;|\;a_i=0}|
= t-|\pgra{1\le i\le t\;|\;b_i=0}| = w
}
\end{prova}
\end{proof}
\begin{prop}
	Algoritmo di decodifica.\\
	Sotto le ipotesi di \see{DefRSDecodifica}, si puo' utilizzare il
	seguente algoritmo per calcolare $c(x)$ a partire dalla parola
	ricevuta $w(x)$.
	\begin{enumerate}
		\item Sia $t=\floor{\delta-1/2}$
		\item Calcola $s_j=w(\b^j)\;\;\forall j=1,\dots,\delta -1$
		\item Calcola il rango $w=\rho(M_t)$, dove $M_t$ e' la
			matrice $M_t=(s_{i+j-1})_{i=1,\dots,t;\; j=1,\dots,t}$
		\item Risolvi il sistema:
			\eal{&M_w\begin{pmatrix}
				\s_0\\
				\s_1\\
				\vdots\\
				\s_{w-1}
			\end{pmatrix}=
			-\begin{pmatrix}
				s_{w+1}\\
				s_{w+2}\\
				\vdots\\
				s_{2w}
			\end{pmatrix}
			}
		\item Trova le radici $\ove a=(a_1,\dots,a_w)$ di 
			\eal{&
			\s(x)= \sum_{i}\s_ix^i}
			L'unico metodo generale noto per trovarle e' procedere
			per forza bruta sostituendo tutti i possibili elementi
			di $F_q$.
		\item Da $\ove a$ ricava il vettore $(i_1,\dots,i_w)$ tale che
			$\b^{i_j}=a_j$.
		\item Risolvi il sistema
			\eal{&
			A\begin{pmatrix}
				b_1\\\vdots\\b_w
			\end{pmatrix}=\begin{pmatrix}
				s_1\\\vdots\\s_w
			\end{pmatrix}
		}
		dove $A$ e' la matrice $A=(a_j^i)_{i=1,\dots,w;\;j=1,\dots,w}$
	\item $e(x)$ e' il polinomio
		\eal{&e(x)=b_1x^{i_1}+\dots+b_wx^{i_w}
		}
	\item Correggi la parola $w(x)$:
		\eal{&c(x)=w(x)-e(x)}
		$c(x)$ e' la parola corretta 
	\end{enumerate}
Nota: un altro algoritmo di decodifica, piu' efficiente di questo, e' il  ``Berlekamp-Massey Algorithm''.
\end{prop}
\begin{proof}
	La correttezza di questo algoritmo deriva dalla \see{PropRSDecodifica}	
\end{proof}


%%%%%%%

\section{Appendice A}
Qui di seguito vengono inclusi gli appunti cartacei appunti forniti dal
professore Re Riccardo. Sono stati modificati con l'aggiunta di alcune
annotazioni.\\
\dots
TODO: da scannerizzare
%\ifpdf
%	\includepdf
%\fi

\section{Appendice B}
Qui di seguito vengono inclusi i miei appunti cartacei.\\
\dots
TODO: da scannerizzare
%\ifpdf
%	\includepdf
%\fi


\printindex
\end{document}