Subversion Repositories yahamm

\documentclass[twoside,a4paper]{refart}

\usepackage{ae}

\usepackage{makeidx}

\usepackage{ifthen}

\usepackage{url}

\usepackage[outputdir=..]{minted}

\usepackage{graphicx}

\usepackage{svg}

\usepackage{makecell}

\usepackage{multirow}

\usepackage{pbox}

%% \def\bs{\char'134 } % backslash in \tt font.

%% \newcommand{\ie}{i.\,e.,}

%% \newcommand{\eg}{e.\,g..}

%% \DeclareRobustCommand\cs[1]{\texttt{\char`\\#1}}

\title{YAHAMM\\

  Yet Another Hamming Encoder and Decoder\\

  ---\\

  Design

}

\author{Nicola De Simone (ndesimone@opencores.org)\\

Version 0.1}

\date{}

\emergencystretch1em  %

\pagestyle{myfootings}

\markboth{YAHAMM Design}%

         {YAHAMM Design}

\makeindex

\setcounter{tocdepth}{2}

% \settextfraction{0.7}

\begin{document}

\maketitle

\tableofcontents

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The present document assumes that the reader is familiar with the Specification Document and with the references \textit{Hamming code} \cite{ham} and \textit{Hamming(7,4)} \cite{ham74} and with the terminology used therein.  No additional knowledge is needed, apart from basic matrix algebra.  Information already included in those documents are not be duplicated.

\section{General structure}

The user connects the encoder entity in \verb|yahamm_enc| to the decoder entity \verb|yahamm_dec|, as described by the specification document.  No other logic is needed.  The amount of code in those two entities is kept to the minimal by choice.  In the encoder the core functionality is in the synchronous logic:

\begin{verbatim}

        code_sys <= to_slv(xor_multiply_vec(G, data_i_padded));

\end{verbatim}

corresponding to the math operation:

\begin{displaymath}

\mathbf{code\_sys} = \mathbf{G} \; \mathbf{data\_i\_padded}

\end{displaymath}

where \verb|G| is the code generator matrix in systematic form, \verb|data_i_padded| the input data and \verb|code_sys| the code word in systematic form.

Similarly, in the decoder the core functionality is in the synchronous logic:

\begin{verbatim}

      syndrome <= xor_multiply_vec(H, code_nonsys);

\end{verbatim}

corresponding to the math operation:

\begin{displaymath}

\mathbf{syndrome} = \mathbf{H} \; \mathbf{code\_nonsys}

\end{displaymath}

where \verb|H| is the parity-check matrix in non-systematic form, \verb|code_non_sys| the input data in non-systematic form and \verb|syndrome| the error syndrome vector that identifies the patterns of errors.

There is some more logic in the decoder entity \verb|yahamm_dec| to implement the counters of errors corrected or detected and the position of the error.

The higher complexity is hidden inside the package \verb|yahamm_pkg| where there are the functions to create the code generator matrix and the parity-check-matrix, to calculate the number of parity bits, block length, to swap between systematic and non-systematic form, to multiply two matrices or matrix and vector.  \verb|matrix_pkg| contains some help functions for \verb|yahamm_pkg|.

\paragraph{One parity bit}

If the encoder and the decoder are configured with the generic \verb|ONE_PARITY_BIT| set to true, their behavior change to a simple one parity bit encoder and decoder.  This is still described and handled with same matrix formalism of the Hamming code, so all math functions accept a parameter \verb|ONE_PARITY_BIT| and behave differently in this case.

\paragraph{Additional parity bit (SECDED)}

Hamming codes can be extended by an extra parity bit. This way, it is possible to increase the minimum distance of the Hamming code to 4, which allows the decoder to distinguish between single bit errors and two-bit errors. Thus the decoder can detect and correct a single error and at the same time detect (but not correct) a double error. If the decoder does not attempt to correct errors, it can detect up to three errors \cite{ham}.

\verb|EXTRA_PARITY_BIT| adds an extra row and extra column to the parity-check matrix and it's handled as a special case in the construction of the code generator matrix.

\paragraph{Bus padding}

Incoming data bus \verb|data_i| are zero-padded on the most significant bit to length $2^r - r - 1$, where $r$ is the number of parity bits \verb|NPARITY_BITS| specified by generic.  This allow the user to use a data bus of any width, ideally the smallest necessary in order to economize routing resources, while the logic for the Hamming code can operate with the standard block length for any given number of parity bits.

\section{matrix\_pkg}

File matrix\_pkg.vhd.

\section{Encoder}

See Fig.~\ref{fig:encoder}.  Entity \verb|yahamm_enc|, file yahamm\_enc.vhd.  Latency 1.

\begin{figure}[!ht]

  \centering

  \includesvg[width=1.1\textwidth]{yahamm_enc}

  \caption{Encoder structure.}

  \label{fig:encoder}

\end{figure}

Input data \verb|data_i| are zero-padded, then multiplied by the code generator matrix $\mathbf{G}$ in systematic form (see Sec.~\ref{sec:codegen}) to compute the code word in systematic form.  Note that the only synthesized logic up to this point are the xor operations used to perform the product with the code generator matrix.

The code word in systematic form had the data in lower significant bits, routed on the output port \verb|data_o|, and the parity bits in the highest significant bits, route on the output port \verb|parity_o|.  \verb|data_valid_o| is the synchronous clear signal \verb|en_i| delayed.

\section{Decoder}

See Fig.~\ref{fig:decoder}.  Entity \verb|yahamm_dec|, file yahamm\_dec.vhd.  Latency 2.

\begin{figure}[!ht]

  \centering

  \includesvg[scale=.30,angle=90]{yahamm_dec}

  \caption{Decoder structure.}

  \label{fig:decoder}

\end{figure}

Input parity bits \verb|parity_i| together with zero-padded input data \verb|data_i| form the systematic code word.  This is swapped to non-systematic form multiplying for the swapping matrix $\mathbf{S}$ (see Sec.~\ref{sec:swap}).   The non-systematic code word is multiplied by the parity-check matrix $\mathbf{H}$ in non-systematic form (see Sec.~\ref{sec:paritycheck}) to compute the syndrome.  Note that the only synthesized logic up to this point are the xor operations used to perform the product with the parity-check matrix.

A non zero syndrome means indicates an error.  There are different possibilities, depending on the user choice of the value of the generics \verb|CORRECT| and \verb|EXTRA_PARITY_BIT|, as show by Table~\ref{tab:secded}.  A combinatorial logic (see \emph{Correction Assessment} in Fig.~\ref{fig:decoder}) determines if the correction has to be done (\verb|correction_en| signal|) and the position of the wrong bit (\verb|wrong_bit| signal).  In the SECDED configuration (\verb|CORRECT| true and \verb|EXTRA_PARITY_BIT| 1), a double error can be detected observing that the syndrome is odd with only the extra parity bit '1', and no correction is done.

In the Single Event Detected case (SEC), and with \verb|CORRECT| generic set to \verb|true|, the wrong bit is then corrected in the non-systematic form of the code word.  This is then swapped to systematic form and \verb|data_o| data output is the least signal part of this code word.

Single Error and Double Error are counted (\verb|cnt_proc| process) and the counters connected to the output ports \verb|cnt_errors_corrected_o| and \verb|cnt_errors_detected_o|.  \verb|cnt_errors_corrected_o| increments only in the SEC case (see Table~\ref{tab:secded}).   In all other cases errors, if any, are not corrected and are counted by \verb|cnt_errors_detected_o|.  Counters can be synchronously cleared with the input \verb|cnt_clr_i|.

In the SEC case (see Table~\ref{tab:secded}) the position of the wrong bit in case of Single Error is used to flip the corresponding bit in the internal \verb|log_wrong_bit_pos_data_o_nonsys| that, after form swapping and slicing, is mapped to the output ports \verb|log_wrong_bit_pos_data_o| and \verb|log_wrong_bit_pos_parity_o|.  They can be synchronously cleared with the input \verb|cnt_clr_i|.

\begin{table}

\hspace{-6cm}

\begin{tabular}{cc|c|c|}

  \cline{3-4}

  \multicolumn{1}{c}{} & & \multicolumn{2}{c|}{\texttt{CORRECT}}\\\cline{3-4}

  \multicolumn{1}{c}{} &  & false & true\\\hline

  \multicolumn{1}{ |c }{\multirow{2}{*}{\texttt{EXTRA\_PARITY\_BIT}}} &

                                                                        \multicolumn{1}{ |c| }{0} & \multicolumn{1}{c|}{\multirow{2}{*}{\makecell{Correction disabled }}} & \makecell{\emph{(SEC)}\\\begin{tabular}{c|c|c|}\hline\multicolumn{1}{|c|}{\multirow{2}{*}{\texttt{syndrome}}} & 0 & no error\\\cline{2-3}\multicolumn{1}{|c|}{} & $\neq 0$ & \texttt{wrong\_bit <= syndrome}\\\hline\end{tabular}\\\\}\\\cline{2-2}\cline{4-4}

  \multicolumn{1}{ |c }{} &

                            \multicolumn{1}{ |c| }{1} & &

  \makecell{\emph{(SECDED)}\\\begin{tabular}{cc|c|c|}

    \cline{3-4}

    \multicolumn{1}{c}{} & & \multicolumn{2}{c|}{\texttt{syndrome's MSB}}\\\cline{3-4}

    \multicolumn{1}{c}{} &  & '0' & '1' \\\hline

    \multicolumn{1}{ |c }{\multirow{2}{*}{\texttt{syndrome's LSBs}}} &

                                                                          \multicolumn{1}{ |c| }{0} & no error & \makecell{SEC\\\texttt{wrong\_bit <= extra\_bit}} \\\cline{2-2}\cline{3-4}

    \multicolumn{1}{ |c }{} &

                               \multicolumn{1}{ |c| }{$\neq 0$} & \makecell{DED\\no correction} & \makecell{SEC\\\texttt{wrong\_bit <= syndrome LSBs}}\\\hline\end{tabular}\\\\}

  % % %   \makecell{syndrome's MSB\\(extra bit)} & \multicolumn{2}{c|}{syndrome's LSBs}\\

  % % %   % && \multicolumn{2}{c|}{syndrome's LSBs}\\

  % % %   % \cline{2-3}

  % % %   % '0' & \makecell{Double error\\\makecell{\texttt{correction\_en <= false} \\ \texttt{wrong\_bit <= 0}}}&\\\hline '1' &\makecell{Single error\\\makecell{\texttt{correction\_en <= true} \\\\ \pbox{5cm}{The wrong bit is the syndrom MSB itself if the remaining part of the syndrome is zero, otherwise it is the one corresponding to the remaining part of the syndrome.}}}&\\\hline

  % \end{tabular}}

  \\\hline

\end{tabular}

\caption{}

  \label{tab:secded}

\end{table}

% The codeword in systematic form had the data in lower significant bits, routed on the output port \verb|data_o|, and the parity bits in the highest significant bits, route on the output port \verb|parity_o|.  \verb|data_valid_o| is the synchronous clear signal \verb|en_i| delayed.

\section{yahamm\_pkg}

File yahamm\_pkg.vhd.

\paragraph{function calc\_nparity\_bits}

\begin{minted}{vhdl}

  function calc_nparity_bits (

    k : natural;

    ONE_PARITY_BIT : boolean := false)

    return natural;

\end{minted}

$r$ parity bits can cover up to $2^r - 1$ bits, including data and parity bits.  That is $2^r - r - 1$ data bits.  The function returns the smallest $r$ such that $2^r - r - 1 \geq k$, where $k$ is the message length (number of data bits).  It returns 1 if \verb|ONE_PARITY_BIT| is true, by definition.

\paragraph{function calc\_block\_length}

\begin{minted}{vhdl}

  function calc_block_length (

    k : natural;

    ONE_PARITY_BIT : boolean := false)

    return natural;

\end{minted}

Length of message bits plus parity bits.   $r$ parity bits can cover up to $2^r - 1$ bits, including data and parity bits.  The function returns $2^r - 1$ where \verb|r := calc_nparity_bits(k)|.  It returns $k+1$ if \verb|ONE_PARITY_BIT| is true.

\paragraph{function calc\_block\_length}

\begin{minted}{vhdl}

  function calc_block_length (

    k : natural;

    ONE_PARITY_BIT : boolean := false)

    return natural;

  \end{minted}

Length of message bits plus parity bits.   $r$ parity bits can cover up to $2^r - 1$ bits, including data and parity bits.  The function returns $2^r - 1$ where \verb|r := calc_nparity_bits(k)|.  It returns $k+1$ if \verb|ONE_PARITY_BIT| is true.  Note that block length does not depend from \verb|EXTRA_PARITY_BIT|; this is an arbitrary choice to simplify the code.

\paragraph{function check\_parameters}

Sanity check on the generic settings for \verb|yahamm_enc| and \verb|yahamm_dec| entities.  It works in both synthesis and simulation.

\paragraph{function get\_parity\_check\_matrix}

\label{sec:paritycheck})

\begin{minted}{vhdl}

  function get_parity_check_matrix (

    MESSAGE_LENGTH : natural;

    EXTRA_PARITY : natural range 0 to 1  := 1;

    ONE_PARITY_BIT : boolean := false)

    return matrix_t;

  \end{minted}

  It returns the non-systematic form of parity check matrix, built following the general algorithm described in \cite{ham}.

  E.g. we want to get the parity-check matrix for the code Hamming(7,4) that encodes four bits of data into seven bits by adding three parity bits.  The matrix has dimension 3x7 if no extra parity bit is added.  The following snippet of test-bench:

  \begin{minted}{vhdl}

entity test is

end entity test;

architecture std of test is

  constant MESSAGE_LENGTH   : natural              := 4;

  constant EXTRA_PARITY_BIT : natural range 0 to 1 := 0;

  constant ONE_PARITY_BIT   : boolean              := false;

  constant NPARITY_BITS : natural := calc_nparity_bits(MESSAGE_LENGTH, ONE_PARITY_BIT);

  constant BLOCK_LENGTH : natural := calc_block_length(MESSAGE_LENGTH, ONE_PARITY_BIT);

  constant H : matrix_t(0 to NPARITY_BITS + EXTRA_PARITY_BIT - 1,

    get_parity_check_matrix(MESSAGE_LENGTH, EXTRA_PARITY_BIT, ONE_PARITY_BIT);

begin

  process is

  begin

    pretty_print_matrix(H);

    stop(0);

  end process;

end architecture std;

\end{minted}

outputs the parity-check matrix $\textbf{H}$: in non-systematic form:

\begin{verbatim}

1 0 1 0 1 0 1

\end{verbatim}

If in the above code, \verb|EXTRA_PARITY_BIT| is 1, the output is:

\begin{verbatim}

1 0 1 0 1 0 1 0

1 1 1 1 1 1 1 1

\end{verbatim}

A right-most column and a bottom row has been added to the previous parity-check matrix.  The addition of '1' in the bottom row means that the forth parity bit encodes the parity for the entire code word.  No change on the existing parity bits ('0' in the last column for those parity bits).

If in the above code, \verb|ONE_PARITY_BIT| is true, the output is:

\begin{verbatim}

1 1 1 1 1

\end{verbatim}

That means that the only parity bit encodes the parity of the entire code word.

\paragraph{function get\_form\_swap\_matrix}

\label{sec:swap})

\begin{minted}{vhdl}

  function get_form_swap_matrix (

    MESSAGE_LENGTH : natural;

    EXTRA_PARITY : natural;

    ONE_PARITY_BIT : boolean := false)

    return matrix_t;

\end{minted}

Returns a $n \times n$ matrix $\textbf{S}$ to convert a $n$-row matrix or vector from non-systematic form $\mathbf{M}_{ns}$ to systematic form $\mathbf{M}_b{s}$ and vice-versa:

\begin{displaymath}

  \mathbf{M}_{s} = \mathbf{M}_{ns} \; \mathbf{S}

\end{displaymath}

The construction of the matrix can be understood by noticing that the systematic form of the parity-check matrix $\textbf{H}$ for the $Hamming(n,k)$ code is:

\begin{equation}

  \label{eq:h}

  \mathbf{H} := ( \mathbf{A} | \mathbf{I}_{n-k} )

\end{equation}

where $\mathbf{I_{n-k}}$ is the $(n-k) \times (n-k)$ identify matrix .  This can be obtained by swapping the columns $2^r - 1$-th of the identify matrix $\mathbf{I}_n$ corresponding to the position, in the non-systematic form, of the parity bits $r$ with the column $n-k+r$.  Note that since $\textbf{S} = \textbf{S}^T = \textbf{S}^{-1}$, the matrix can be used to transform from systematic to non-systematic form and vice-versa.

Example:

\begin{minted}{vhdl}

entity test is

end entity test;

architecture std of test is

  constant MESSAGE_LENGTH   : natural              := 4;

  constant EXTRA_PARITY_BIT : natural range 0 to 1 := 0;

  constant ONE_PARITY_BIT   : boolean              := false;

  constant NPARITY_BITS : natural := calc_nparity_bits(MESSAGE_LENGTH, ONE_PARITY_BIT);

  constant BLOCK_LENGTH : natural := calc_block_length(MESSAGE_LENGTH, ONE_PARITY_BIT);

  constant H : matrix_t(0 to NPARITY_BITS + EXTRA_PARITY_BIT - 1,

    get_parity_check_matrix(MESSAGE_LENGTH, EXTRA_PARITY_BIT, ONE_PARITY_BIT);

  constant swap_matrix : matrix_t(0 to BLOCK_LENGTH + EXTRA_PARITY_BIT - 1,

    get_form_swap_matrix(MESSAGE_LENGTH, EXTRA_PARITY_BIT, ONE_PARITY_BIT);

begin

  process is

  begin

    pretty_print_matrix(H);

    pretty_print_matrix(swap_matrix);

    pretty_print_matrix(xor_multiply(H, swap_matrix));

    pretty_print_matrix(xor_multiply(xor_multiply(H, swap_matrix), swap_matrix));

    stop(0);

  end process;

end architecture std;

\end{minted}

Outputs:

\begin{verbatim}

-- parity-check matrix, non-systematic form

1 0 1 0 1 0 1

-- form-swap matrix

1 0 0 0 0 0 0

-- parity-check matrix, systematic form

1 0 1 1 1 0 0

1 1 0 1 0 0 1

-- parity-check matrix, non-systematic form

1 0 1 0 1 0 1

\end{verbatim}

The first three matrices are: the parity-check matrix for Hamming(7,4) in non-systematic form, the form swapping matrix, the parity-check matrix in systematic form.  Note the identity matrix in the right-most columns in the systematic form of the parity-check matrix.  The forth matrix is the parity-check matrix obtained by multiplying its systematic form for the form-swap matrix.

If \verb|EXTRA_PARITY_BIT| is 1, the matrix has an additional column and row.  Last column is the same as in the identity matrix (no swapping).

\paragraph{function get\_code\_generator\_matrix}

\label{sec:codegen}

\begin{minted}{vhdl}

  function get_code_generator_matrix (

    MESSAGE_LENGTH : natural;

    EXTRA_PARITY : natural range 0 to 1 := 1;

    ONE_PARITY_BIT : boolean := false)

    return matrix_t;

\end{minted}

Returns the code generator matrix in systematic form.  The construction algorithm, as suggested in \cite{ham}, Sec. \emph{Construction of G and H}, is based on the comparison of G in systematic form:

\begin{equation}

  \label{eq:g}

  \mathbf{G} := ( \mathbf{I}_{k} | \mathbf{A}^T )

\end{equation}

with the expression of the parity-check matrix in systematic form in Eq.~\ref{eq:h}.  So the left hand side of $\mathbf{H}$ in systematic form can be transposed and combined with the $\mathbf{I}_{k}$ identity matrix.

E.g. we want to get the code generator matrix for the code Hamming(7,4) that encodes four bits of data into seven bits by adding three parity bits.  The matrix has dimension 7x4 if no extra parity bit is added.  The following snippet of test-bench:

  \begin{minted}{vhdl}

architecture std of test is

  constant MESSAGE_LENGTH   : natural              := 4;

  constant EXTRA_PARITY_BIT : natural range 0 to 1 := 0;

  constant ONE_PARITY_BIT   : boolean              := false;

  constant NPARITY_BITS : natural := calc_nparity_bits(MESSAGE_LENGTH, ONE_PARITY_BIT);

  constant BLOCK_LENGTH : natural := calc_block_length(MESSAGE_LENGTH, ONE_PARITY_BIT);

  constant G : matrix_t(0 to BLOCK_LENGTH + EXTRA_PARITY_BIT - 1,

    get_code_generator_matrix(MESSAGE_LENGTH, EXTRA_PARITY_BIT, ONE_PARITY_BIT);

begin

  process is

  begin

    pretty_print_matrix(G);

    stop(0);

  end process;

end architecture std;

\end{minted}

Outputs:

\begin{verbatim}

1 0 0 0

1 0 1 1

1 1 0 1

\end{verbatim}

If in the above code, \verb|EXTRA_PARITY_BIT| is 1, the output is:

\begin{verbatim}

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0

\end{verbatim}

A bottom row has been added to the previous code generator matrix, based on the parity of the rows of the parity-check matrix.

If in the above code, \verb|ONE_PARITY_BIT| is true, the output is:

\begin{verbatim}

1 0 0 0

1 1 1 1

\end{verbatim}

Where the result is a row of '1' at the bottom of an identity matrix.  That means that the code word is the message plus its parity bit.

\printindex

\bibliographystyle{abbrv}

\bibliography{design}

\end{document}