Subversion Repositories yahamm

\documentclass[twoside,a4paper]{refart}
\usepackage{ae} % CM-Zeichens"atze mit T1 encoding
\usepackage{makeidx}
\usepackage{ifthen}
 
%% \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\\
  ---\\
  Specification
}
\author{Nicola De Simone (ndesimone@opencores.org)\\
Version 0.1}
\date{}
\emergencystretch1em  %
 
\pagestyle{myfootings}
\markboth{YAHAMM Specification}%
         {YAHAMM Specification}
 
\makeindex 
 
\setcounter{tocdepth}{2}
\settextfraction{0.7}
 
 
\begin{document}
 
\maketitle
 
\tableofcontents
 
\newpage
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
\begin{abstract}
YAHAMM is a VHDL implementation of an Hamming encoder, as entity yahamm\_enc, and and Hamming decoder, as entity yahamm\_dec, of message length defined trough generic.  All the math needed to compute the code is internally implemented in VHDL and it is transparent to the user.  Single Error Correction and Double Error Detection is also provided (see next for details).  Encoder has latency 1 clock cycle, decoder latency 2, independently from their configuration.
\end{abstract}
 
 
\section{Project files}
The projects includes the file:
 
\begin{enumerate}
\item rtl/vhdl/yahamm\_enc.vhd: encoder entity
\item rtl/vhdl/yahamm\_dec.vhd: decoder entity
\item rtl/vhdl/matrix\_pkg.vhd: help functions for matrix manipulation
\item rtl/vhdl/yahamm\_pkg.vhd: core math functions
\item bench/vhdl/yahamm\_tb[0-3].vhd: test benches
\item sim/rtl\_sim/bin/Makefile: a set of rules for the analysis and simulation with GHDL.
\end{enumerate}
 
\section{Makefile}
 
The Makefile targets call ghdl for analyzing the VHDL and running simulations.
 
\subsection{Analyze the VHDL}
\begin{enumerate}
\item \verb|cd sim/rtl_sim/bin|
\item \verb|make <vhdl file>|
\end{enumerate}
 
\subsection{Run the simulation}
\begin{enumerate}
\item \verb|cd sim/rtl_sim/bin|
\end{enumerate}
To simulate a single test-bench:
\begin{enumerate}
\item[2] \verb|make simulate_tb[0..3]|
\end{enumerate}
or, to simulate all test-benches:
\begin{enumerate}
\item[2] \verb|make simulate|
\end{enumerate}
 
Each test-bench will output ``OK'' if successful.
 
The simulation will create waveform as VCD compressed file in \verb|cd sim/rtl_sim/out|.  They can be view, for example, with gtkwave by running:
 
\begin{enumerate}
\item[3] \verb|make view_[0..3]|
\end{enumerate}
 
\subsection{Cleanup}
\begin{enumerate}
\item \verb|cd sim/rtl_sim/bin|
\item \verb|make clean|
\end{enumerate}
 
 
\section{Encoder}
\label{sec:encoder}
 
\begin{verbatim}
entity yahamm_enc is
  generic (
    MESSAGE_LENGTH       : natural := 5;
    EXTRA_PARITY_BIT : natural range 0 to 1 := 1;
    ONE_PARITY_BIT : boolean := false
    );
  port(
    clk_i, rst_i : in  std_logic;
    en_i       : in  std_logic := '1';          -- Synchronous output enable .
    data_i        : in  std_logic_vector(MESSAGE_LENGTH - 1 downto 0);  -- Input data.
    data_o        : out std_logic_vector(MESSAGE_LENGTH - 1 downto 0);  -- Out data.
    data_valid_o : out std_logic;        -- High when data_o is valid.
    parity_o   : out std_logic_vector(calc_nparity_bits(MESSAGE_LENGTH, ONE_PARITY_BIT) + EXTRA_PARITY_BIT - 1 downto 0)    -- Parity bits.
    );
 
end yahamm_enc;
\end{verbatim}
 
Generics:
 
\begin{enumerate}
\item MESSAGE\_LENGTH: the data payload length, excluding parity bits.
\item EXTRA\_PARITY\_BIT: if 1 the Hamming codes are extended by an extra parity bit. This way the minimum Hamming distance is increased 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 (SECDED). If the decoder does not attempt to correct errors, it can detect up to three errors.  \seealso{Sec \ref{sec:decoder}}.  Default is 1.
\item ONE\_PARITY\_BIT: if true the encoder does not perform Hamming encoding but just adds a single parity bit to the message.  Default is false.
\end{enumerate}
 
The generics MESSAGE\_LENGTH, EXTRA\_PARITY\_BIT and ONE\_PARITY\_BIT must have the same values on both the encoder and the decoder instances.
 
Ports:
 
\begin{enumerate}
\item clk\_i: input reset, active high.
\item rst\_i: input reset, active high.
\item en\_i: input enable.  When asserted input data are encoded.  If de-asserted, data and parity outputs are zero.  Default is high.
\item data\_i: input data.  Length equal to MESSAGE\_LENGTH.
\item data\_o: output data. Length equal to MESSAGE\_LENGTH.
\item data\_valid\_o: output valid signal for data\_o.  This is just en\_i delayed by the core latency.
\item parity\_o: output parity bits.  The length of this vectors corresponds to the number of parity bits needed by the hamming code and it's computed by the VHDL function calc\_nparity\_bits().  One extra parity bit is needed if the generic EXTRA\_PARITY\_BIT is true.  The user instantiating the entity and mapping that port can determine the length in three ways:
  \begin{enumerate}
  \item Calculate the number of parity bits $r$ needed for the specified message length $k$, looking for the smallest $r$ such that $k \geq 2^r - r - 1$ for $r \ge 2$.
  \item Use the script \verb|sw/calc_nparity_bits.sh|.
  \item Connect a bus or arbitrary random length.  Run any VHDL analysis tool and use the syntax error you get to see which is the right length.
  \end{enumerate}
\end{enumerate}
 
\section{Decoder}
\label{sec:decoder}
 
\begin{verbatim}
entity yahamm_dec is
  generic (
    MESSAGE_LENGTH       : natural := 5;
    CORRECT : boolean := true;
    EXTRA_PARITY_BIT : natural range 0 to 1 := 1;
    ONE_PARITY_BIT : boolean := false;
    ERROR_LEN : natural := 16
    );
  port(
    clk_i, rst_i : in  std_logic;
    cnt_clr_i : in std_logic := '0';             -- Clear monitor counters.
    en_i       : in  std_logic := '1';          -- Input enable.
    data_i        : in  std_logic_vector(MESSAGE_LENGTH - 1 downto 0);  -- Input data.
    parity_i   : in std_logic_vector(calc_nparity_bits(MESSAGE_LENGTH, ONE_PARITY_BIT) + EXTRA_PARITY_BIT - 1 downto 0);    -- Parity bits.
    data_o        : out std_logic_vector(MESSAGE_LENGTH - 1 downto 0);  -- Out data.
    dout_valid_o : out std_logic;                                          -- data_o valid.
    cnt_errors_corrected_o, cnt_errors_detected_o : out std_logic_vector(ERROR_LEN - 1 downto 0);
    log_wrong_bit_pos_data_o : out std_logic_vector(MESSAGE_LENGTH - 1 downto 0);
    log_wrong_bit_pos_parity_o : out std_logic_vector(calc_nparity_bits(MESSAGE_LENGTH, ONE_PARITY_BIT) + EXTRA_PARITY_BIT - 1 downto 0)  
    );
 
end yahamm_dec;
\end{verbatim}
 
Generics:
 
\begin{enumerate}
\item \verb|CORRECT|: if true, the core corrects detected errors.  Default is true.
\item \verb|ERROR_LEN|: bit length of the error counters provided on ports \verb|cnt_errors_corrected_o| and \verb|cnt_errors_detected_o|.
\item \verb|MESSAGE_LENGTH|: see Sec. \ref{sec:encoder}.
\item \verb|EXTRA_PARITY_BIT|: see Sec. \ref{sec:encoder}.
\item \verb|ONE_PARITY_BIT|: see Sec. \ref{sec:encoder}.
\end{enumerate}
 
The generics MESSAGE\_LENGTH, EXTRA\_PARITY\_BIT and ONE\_PARITY\_BIT must have the same values on both the encoder and the decoder instances.
 
Ports:
 
\begin{enumerate}
\item \verb|cnt_clr_i|: input synchronous clear of the error counters.
\item \verb|en_i|: optional input enable.  Can be connected to \verb|dout_valid_o| of the encoder to propagate a valid signal to the output port \verb|data_valid_o|:  Default is high (\verb|data_valid_o| will be always asserted in this case).
\item \verb|data_i|: input data.  It must be connected to the \verb|data_o| of the decoder.  Length equal to MESSAGE\_LENGTH.
\item \verb|parity_i|: input parity bits.  It must be connected to the \verb|parity_o| of the decoder.
\item \verb|data_o|: output data.  Length equal to MESSAGE\_LENGTH.
\item data\_valid\_o: output valid signal for data\_o.  This is just en\_i delayed by the core latency.
\item \verb|cnt_errors_corrected_o|: counter of single errors corrected.  It is always zero if the generic \verb|CORRECT| is false.
\item \verb|cnt_errors_detected_o|: counter of errors detected.  It includes single, double and triple errors (not there's no way to distinguish between a single and a triple error), if the generic \verb|CORRECT| is false, otherwise it only counts double errors.
\item \verb|log_wrong_bit_pos_data_o|: position of the single errors in \verb|data_o|.  A bit is asserted high when there is an error in the same position in \verb|data_o|.  They are only de-asserted by a synchrnous clear \verb|cnt_clr_i| or by a reset.  It is not used if generic \verb|CORRECT| is false or if it's not a single error.
\item \verb|log_wrong_bit_pos_parity_o|: position of the single error in \verb|parity_o|.  A bit is asserted high when there is an error in the same position in \verb|parity_o|.  They are only de-asserted by a synchrnous clear \verb|cnt_clr_i| or by a reset.  It is not used if generic \verb|CORRECT| is false or if it's not a single error.
\end{enumerate}
 
 
\section{SEC-DED and other possibilities}
 
In order to have SEC-DED (Single Error Corrected - Double Error Detected) capability, user should use the default values for the generics \verb|EXTRA_PARITY_BITS| 1, and \verb|CORRECT| true.
 
Other choices can be made as described by the following table.
 
\begin{table}
  \begin{tabular}{||c|cc||}
    \hline
    \hline        
    & \multicolumn{2}{|c||}{\texttt{CORRECT}} \\    
    \hline
    \verb|EXTRA_PARITY_BIT| & false & true\\
    \hline
    false & SED-DED & SEC\\
    true & SED-DED-TED & SEC-DED\\
    \hline        
    \hline    
  \end{tabular}
  \caption{SEC = single bit error corrected,
    SED = single bit error detected,
    DED = double bit error detected,
    TED = triple bit error detected
  }
\end{table}
 
The generic \verb|EXTRA_PARITY_BITS| set to true (default) adds a parity bit so that the Hamming distance is $4$ between two code words (number of bits to flip in a code word to obtain another code word).  With \verb|EXTRA_PARITY_BITS| set to false the Hamming distance will be $3$.
 
The generic \verb|CORRECT| set to true (default) corrects for single bit errors.  It can be set to false if only error detection is needed.  This allows triple error detection with \verb|EXTRA_PARITY_BIT| set to true.  Indeed, a triple error is indistinguishable from a single error with an Hamming distance 4 and the correction would be wrong in this case.  Similarly, with \verb|EXTRA_PARITY_BIT| set to false, hence with Hamming distance 3, a double error is indistinguishable from a single error and the correction would be wrong.
 
If \verb|CORRECT| is false, the port \verb|cnt_errors_detected_o| provides the value of a counter that sums up any kind of error detected (single, double and triple).  If the configuration is SEC-DED, \verb|cnt_errors_detected_o| provides the counter for DED, \verb|cnt_errors_corrected_o| provides the counter for SEC.
 
For most applications, SEC-DED configuration (the default) is the preferred choice.  A communication channel can be considered reliable if the probability of double error is negligible.   A noisy channel showing double errors detected is not to be trusted because event a corrected single error may be a triple error and the correction would be wrong.
 
 
\printindex
 
\end{document}