5-dammMethod.tex

\chapter{Damm's method}

Damm's method is check digit algorithm based on 
\emph{quasigroup}.
It can detect all single-digit errors and all adjacent transposition errors.

\section{Quasigroup}

\emph{Quasigroup} $(Q,*)$ is a set $Q$ with a binary operation ``$*$''
such that  \emph{ Latin square property} holds:
for every $a,b \in Q$, there exists unique $x$ and $y$ satisfy the following.
\begin{align*}
 a*x = b\\
 y*a = b
\end{align*}

Let us consider a \emph{Cayley table} of the operation ``$*$''.
Latin square property can be characterize by whether 
the table is \emph{Latin square}:
each element occurs exactly once in each row and exactly once in each column.
For example, the operation expressed by the following table
satisfies Latin square property.
\begin{center}
\begin{tabular}{| l || l | l | l |}
\hline
$*$& 0 & 1 & 2\\
\hline\hline
0   & 0 & 1 & 2\\
\hline
1   & 1 & 2 & 0 \\
\hline
1   & 2 & 0 & 1 \\
\hline
\end{tabular}
 \end{center}

The following lemma is derived immediately,
which is significant for error detection  of 
damm's method.
\begin{lemma}
 Suppose $(Q,*)$ is quasigroup.
 For arbitrary $x,x'$ and $a$ in $Q$, the following hold.
\begin{align}
 x \neq x'\; \Rightarrow a*x \neq a*x' \label{eq:lem1}\\
 x \neq x'\; \Rightarrow x*a \neq x'*a \label{eq:lem2}
 \end{align}
\end{lemma}



\section{Damm's method}

This algorithm is based on quasigroup $(Q,*)$
of 10-order with a special property:
for all $c,x,y \in Q$ the followings hold.
\begin{align}
 &(c*x)*y = (c*y)*x \;\Rightarrow x = y \label{eq:antiSym1}\\
&x*x = 0 \label{eq:res}
\end{align}
The example of such a quasigroup is shown below.

\begin{figure}[htb]
 \begin{center}
\begin{tabular}{| l || l | l | l | l | l | l | l | l | l | l |}
 \hline
* & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline\hline
0 & 0 & 3 & 1 & 7 & 5 & 9 & 8 & 6 & 4 & 2\\
\hline
1 & 7 & 0 & 9 & 2 & 1 & 5 & 4 & 8 & 6 & 3\\
\hline
2 & 4 & 2 & 0 & 6 & 8 & 7 & 1 & 3 & 5 & 9\\
\hline
3 & 1 & 7 & 5 & 0 & 9 & 8 & 3 & 4 & 2 & 6\\
\hline
4 & 6 & 1 & 2 & 3 & 0 & 4 & 5 & 9 & 7 & 8\\
\hline
5 & 3 & 6 & 7 & 4 & 2 & 0 & 9 & 5 & 8 & 1\\
\hline
6 & 5 & 8 & 6 & 9 & 7 & 2 & 0 & 1 & 3 & 4\\
\hline
7 & 8 & 9 & 4 & 5 & 3 & 6 & 2 & 0 & 1 & 7\\
\hline
8 & 9 & 4 & 3 & 8 & 6 & 1 & 7 & 2 & 0 & 5\\
\hline
9 & 2 & 5 & 8 & 1 & 4 & 3 & 6 & 7 & 9 & 0\\
\hline
\end{tabular}
 \end{center}
\caption{Example:Quasigroup for damm's method}
\label{fig:10digitsQuasi}
\end{figure}
{\bf The validity of a digit sequence $m_1 m_2 ... m_n$ is judged by whether
$(...((0*m_1)*m_2)*...*m_n) = 0 $ holds.}
Given a digit sequence $m_1 m_2...m_{n-1}$,
a valid sequence can be generated by
adding $m_n = (...((0*m_1)*m_2)*...*m_{n-1})$ to the tail:
$(...((0*m_1)*m_2)*...*m_n) = 0 $ holds from the equation~\ref{eq:res}.

This method can detect all single-digit
 errors and all adjacent transposition errors.
The proof is as follow.
We denote $k_i^{m}$ as $(...(0*m_1)*...*m_i)$.
\begin{itemize}
 \item \underline{single-digit errors }

       Suppose digit sequences $m$ and $m'$ are same except for i'th element:
       $m_i \neq m'_i$.
       \begin{align*}
	k_i^{m} &= k_{i-1}^{m} * m_i \\
	k_i^{m'} &= k_{i-1}^{m} * m'_i 
       \end{align*}
       From the implication~\ref{eq:lem1},
       $$k_i^{m} \neq k_i^{m'}$$ 
       is derived.
       \begin{align*}
	k_{i+1}^{m} &= k_i^{m} * m_i \\
	k_{i+1}^{m'} &= k_i^{m} * m'_i 
       \end{align*}
       From the implication~\ref{eq:lem2},
       $$k_{i+1}^{m} \neq k_{i+1}^{m'}$$
       Therefore, inductively,
       $$k_{n}^{m'} \neq k_{n}^{m} = 0$$

 \item \underline{ adjacent transposition errors}

       Suppose a digit sequence $m'$ is a result of
       swapping $m_i$ and $m_{i+1}$ in a sequence $m$.
       Here, we assume $m_i \neq m_{i+1}$.
       \begin{align*}
	k_{i+1}^{m} &= (k_{i-1}^{m}* m_i) * m_{i+1} \\
	k_{i+1}^{m'} &= (k_{i-1}^{m}* m_{i+1}) * m_i
       \end{align*}
       From (\ref{eq:antiSym1}),
       $$k_{i+1}^{m} \neq k_{i+1}^{m'}$$ 
       is derived.
       Hence, same as the  case \underline{single-digit errors },
       $$k_{n}^{m'} \neq k_{n}^{m} = 0$$
\end{itemize}

\section{Sufficient condition}
We modified the original validation method such that the additional property is as weak as possible.

Given a digit sequence $m_1 m_2 \ldots m_{n-1}$, since  \emph{ Latin square property} of Quasigroup, there exists unique $m_n$ such that $(((0*m_1)*m_2)*\ldots *m_{n-1}) * m_n = 0$. Valid sequence can be generated by adding this $m_n$ value to the tail.

\underline{single-digit errors } proof requires implication~\ref{eq:lem1} and~\ref{eq:lem2}, that can be implied from \emph{ Latin square property} of Quasigroup. And, \underline{ adjacent transposition errors} proof requires only~\ref{eq:antiSym1}. We wrote a program to find all such Quasigroups that they satisify~\ref{eq:antiSym1} but not~\ref{eq:res}. The result is shown in Figure~\ref{fig:10digitsQuasiNotdamm1},~\ref{fig:10digitsQuasiNotdamm2},~\ref{fig:10digitsQuasiNotdamm3}.

C++ code is as following

\begin{minted}{cpp}
#include <iostream>
using namespace std;

#define SIZE 10
//number of tables to find
#define NFIND 3
int cnt = NFIND;

void tprint(int a[][SIZE]){
  cout << "Result " << (NFIND - cnt + 1) << endl;
  for(int row = 0; row < SIZE; row++){
    for(int col = 0; col < SIZE; col ++)
    cout << a[row][col] << " ";
    cout << endl;
    //print for latex
    //cout << row;
    //for(int col = 0; col < SIZE; col ++)
      //cout << " & " << a[row][col];
    //cout << "\\\\\n\\hline\n";
  }
  cout << endl;
}
bool f(int a[][SIZE], int row, int col, int val){
  if (!cnt) return false;
  a[row][col] = val;
  int nrow, ncol;
  if (col < SIZE - 1){
    ncol = col + 1;
    nrow = row;
  } else if (row < SIZE - 1){
      ncol = 0;
      nrow = row + 1;
    } else {
      bool found = false;
      for(int i = 0; i < SIZE; i++)
        if (a[i][i] != i){
          found = true;
          break;
        }
      if (!found) return false;
      tprint(a);
      cnt--;
      return !cnt;
    }
  bool checked[SIZE];
  fill(checked, checked + SIZE * sizeof(bool), false);
  for(int i = 0; i < ncol; i++)
    checked[a[nrow][i]] = true;
  for(int i = 0; i < nrow; i++)
    checked[a[i][ncol]] = true;
  for(int v = 0; v < SIZE; v++)
    if (!checked[v] && f(a, nrow, ncol, v))
      return true;
  return false;
}

int main(){
  int a[SIZE][SIZE];
  for(int i = 0; i < SIZE; i++)
    f(a, 0, 0, i);
  if (cnt == NFIND)
    cout << "not found" << endl;
  return 0;
}
\end{minted}

\begin{figure}[htb]
 \begin{center}
\begin{tabular}{| l || l | l | l | l | l | l | l | l | l | l |}
 \hline
* & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline\hline
0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
1 & 1 & 0 & 3 & 2 & 5 & 4 & 7 & 6 & 9 & 8\\
\hline
2 & 2 & 3 & 0 & 1 & 6 & 7 & 8 & 9 & 4 & 5\\
\hline
3 & 3 & 2 & 1 & 0 & 7 & 6 & 9 & 8 & 5 & 4\\
\hline
4 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3\\
\hline
5 & 5 & 4 & 7 & 6 & 9 & 8 & 1 & 0 & 3 & 2\\
\hline
6 & 6 & 7 & 8 & 9 & 2 & 3 & 4 & 5 & 0 & 1\\
\hline
7 & 7 & 6 & 9 & 8 & 3 & 2 & 5 & 4 & 1 & 0\\
\hline
8 & 8 & 9 & 4 & 5 & 0 & 1 & 2 & 3 & 6 & 7\\
\hline
9 & 9 & 8 & 5 & 4 & 1 & 0 & 3 & 2 & 7 & 6\\
\hline
\end{tabular}
 \end{center}
\caption{Example1: Non anti-symmetric Quasigroup for damm's method}
\label{fig:10digitsQuasiNotdamm1}
\end{figure}

\begin{figure}[htb]
 \begin{center}
\begin{tabular}{| l || l | l | l | l | l | l | l | l | l | l |}
 \hline
* & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline\hline
0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
1 & 1 & 0 & 3 & 2 & 5 & 4 & 7 & 6 & 9 & 8\\
\hline
2 & 2 & 3 & 0 & 1 & 6 & 7 & 8 & 9 & 4 & 5\\
\hline
3 & 3 & 2 & 1 & 0 & 7 & 6 & 9 & 8 & 5 & 4\\
\hline
4 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3\\
\hline
5 & 5 & 4 & 7 & 6 & 9 & 8 & 1 & 0 & 3 & 2\\
\hline
6 & 6 & 7 & 8 & 9 & 2 & 3 & 4 & 5 & 0 & 1\\
\hline
7 & 7 & 6 & 9 & 8 & 3 & 2 & 5 & 4 & 1 & 0\\
\hline
8 & 8 & 9 & 4 & 5 & 0 & 1 & 2 & 3 & 7 & 6\\
\hline
9 & 9 & 8 & 5 & 4 & 1 & 0 & 3 & 2 & 6 & 7\\
\hline
\end{tabular}
 \end{center}
\caption{Example2: Non anti-symmetric Quasigroup for damm's method}
\label{fig:10digitsQuasiNotdamm2}
\end{figure}

\begin{figure}[htb]
 \begin{center}
\begin{tabular}{| l || l | l | l | l | l | l | l | l | l | l |}
 \hline
* & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline\hline
0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
\hline
1 & 1 & 0 & 3 & 2 & 5 & 4 & 7 & 6 & 9 & 8\\
\hline
2 & 2 & 3 & 0 & 1 & 6 & 7 & 8 & 9 & 4 & 5\\
\hline
3 & 3 & 2 & 1 & 0 & 7 & 6 & 9 & 8 & 5 & 4\\
\hline
4 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & 1 & 2 & 3\\
\hline
5 & 5 & 4 & 7 & 6 & 9 & 8 & 1 & 0 & 3 & 2\\
\hline
6 & 6 & 7 & 8 & 9 & 2 & 3 & 4 & 5 & 0 & 1\\
\hline
7 & 7 & 6 & 9 & 8 & 3 & 2 & 5 & 4 & 1 & 0\\
\hline
8 & 8 & 9 & 4 & 5 & 0 & 1 & 3 & 2 & 6 & 7\\
\hline
9 & 9 & 8 & 5 & 4 & 1 & 0 & 2 & 3 & 7 & 6\\
\hline
\end{tabular}
 \end{center}
\caption{Example3: Non anti-symmetric Quasigroup for damm's method}
\label{fig:10digitsQuasiNotdamm3}
\end{figure}