galois.h

/*C
  (c) 2005 bl0rg.net
**/

#ifndef GALOIS_H__
#define GALOIS_H__

/*H
  \subsection{Galois field implementation}

  To avoid roundings using calculations of FEC coefficients, we
  need to compute in a finite field.

  \subsubsection{Mathematical background}

  % Group
  \begin{definition}
  A \emph{group} is a set $G$ with a binary operation $\cdot$
  satisfying the following axioms:
  \begin{enumerate}
  \item \emph{Closure}: $\forall a, b \in G$: $a \cdot b \in G$
  \item \emph{Associativity}: $\forall a, b, c \in G$: $\left(a \cdot
  b\right) \cdot c = a \cdot \left(b \cdot c\right)$
  \item \emph{Identity}: $\forall a \in G$: $\exists e \in G$: $e \cdot a =
  a \cdot e = a$
  \item \emph{Inverse}: $\forall a \in G$: $\exists a^{-1} \in G$: $a 
  \cdot a^{-1} = a^{-1} \cdot a = e$
  \end{enumerate}
  \end{definition}

  % abelian group
  \begin{definition}
  A group $G$ is \emph{commutative} or \emph{abelian} if
  \[\forall a, b \in G: a \cdot b = b \cdot a.\]
  \end{definition}

  % subgroup
  \begin{definition}
  A \emph{subgroup} of a group $G$ is a subset $H$ of $G$ that is
  itself a group under the operation of $G$.
  \end{definition}

  % ring
  \begin{definition}
  A \emph{ring} is a set $R$ with two binary operations, addition $+$
  and multiplication $\cdot$, satisfying the following axioms:
  \begin{enumerate}
  \item $\left(R, +\right)$ is an abelian group
  \item \emph{Associativity for multiplication}: $\forall a, b, c \in R$:
  $\left(a \cdot b\right) \cdot c = a \cdot \left(b \cdot c\right)$
  \item \emph{Distributivity}: $\forall a, b, c \in R$: $a \cdot \left(b +
  c\right) = \left(a \cdot b\right) + \left(a \cdot c\right)$ and
  $\left(b + c\right) \cdot a = \left(b \cdot a\right) + \left(c
  \cdot a\right)$
  \end{enumerate}
  \end{definition}

  % field
  \begin{definition}
  A \emph{field} is a set $F$ with two binary operations, addition
  $+$ and multiplication $\cdot$, satisfying the following axioms:
  \begin{enumerate}
  \item $\left(F, +\right)$ is an abelian group
  \item $\left(F - \left\{0\right\}, \cdot\right)$ is an abelian group
  \item \emph{Distributivity}: $\forall a, b, c \in F$: $a \cdot
  \left(b + c\right) = \left(a \cdot b\right) + \left(a \cdot c\right)$
  \end{enumerate}
  \end{definition}

  % subfield
  \begin{definition}
  A \emph{subfield} of a field $F$ is a subset $G$ of $F$ that is
  itself a field under the operations of $F$.
  \end{definition}

  % characteristic
  \begin{definition}
  The additive subgroup generated by $1$ (that is, $0, 1, 1+1, 1+1+1,
  \dots$) has finite order, and its elements are called the
  \emph{field integers}. This order is called the
  \emph{characteristic} of a finite field.
  \end{definition}

  % characteristic is a prime number
  \begin{theorem}
  The characteristic of a finite field is a prime number.
  \end{theorem}
  
  % finite fields have p^m elements
  \begin{theorem}
  A finite field has $p^m$ elements, where $p$ is the characteristic
  of the field.
  \end{theorem}

  % multiplicative groups of finite fields are cyclic
  \begin{theorem}
  \label{theorem:finite-cyclic}
  The multiplicative group of the finite field \gf{q} is cyclic of
  order $q - 1$.
  \end{theorem}

  % definition GF(p)
  \begin{theorem}
  The integers ($0, 1, \dots, p-1$) with modulo $p$ arithmetic form a
  commutative ring, in which every nonzero element has a
  multiplicative inverse, thus forming a field.
  \end{theorem}

  \begin{definition}
  The field of the integers with modulo $p$ arithmetic is called \gf{p}.
  \end{definition}

  % definition GF(Q)

  % definition prime polynomial
  \begin{definition}
  A \emph{monic} polynomial is a polynomial with leading coefficient $1$.
  \end{definition}
  \begin{definition}
  An \emph{irreducible} polynomial has no proper divisors (divisors
  of smaller degree).
  \end{definition}
  \begin{definition}
  A \emph{prime} polynomial is a monic irreducible polynomial.
  \end{definition}

  \begin{theorem}
  The polynomials over a finite field \gf{q} modulo a
  prime polynomial of degree $m$ form a field with $q^m$ elements.
  \end{theorem}

  \begin{definition}
  The field of the polynomials over a finite field \gf{q} modulo a
  prime polynomial of degree $m$ form a field called \gf{q^m}.
  \end{definition}

  % definition vector space
  \begin{definition}
  A \emph{vector space} is a set $V$ of \emph{vectors} over a field
  $F$ of \emph{scalars} with a binary operator on $V$ and a
  scalar-vector product $\cdot$ satisfying the following axioms:
  \begin{enumerate}
  \item $\left(V, +\right)$ is a commutative group
  \item $\forall v \in V$: $1 \cdot v = v$
  \item \emph{Distributivity}: $\forall a \in F, v_1, v_2 \in V$:
  $a \cdot \left(v_1 + v_2\right) a \cdot v_1 + a \cdot v_2$ and
  $\forall a_1, a_2 \in F, v \in V$:
  $\left(a_1 + a_2\right) \cdot v = a_1 \cdot \left(a_2 \cdot v\right)$
  \end{enumerate}
  \end{definition}

  \subsubsection{Representation of \gf{p} elements as polynomials}
  
  In a finite field $F$ of characteristic $p$, any sum of multiple $p$
  ones is $0$, so the arithmetic with field integers is the same as
  the integers modulo $p$. The field integers are closed under
  division, and are a subfield of $F$. Furthermore, they are the
  smallest subfield of $F$, because every field must contain $1$ and
  all of its sums and products. Thus, $F$ can be considered a vector
  space over the subfield \gf{p}. However, $F$ has many bases over
  \gf{p}

  Efficient multiplication and division can be achieved when choosing
  a good basis for F over \gf{p}: the powers of an element
  $\alpha \in F$. If $\left\{1, \alpha, \dots, \alpha^{m-1}\right\}$
  is linearly independent, then every element of $F$ is a linear
  combination of powers of $\alpha$, i.e. a polynomial in $\alpha$ of
  degree less than $m$. The sum operation is the sum between
  coefficients, modulo $p$, the product is the product between
  polynomials, modulo a prime polynomial of degree $m$, and with
  coefficients reduced modulo $p$.

  When $p = 2$, operations on \gf{2^m} are
  extremely simple: an element of \gf{2^m} requires $m$ bits to be
  represented. Sum and substraction become the same operation, which
  is simply implemented with an exclusive \verb|OR|.

  There exists $\alpha \in F$ such that $F$ can be represented as
  $\left\{0, 1, \alpha, \alpha^2, \dots, \alpha^{p^m-2}\right\}$ (see
  \ref{theorem:finite-cyclic}). Thus, we can express any non-zero
  field element as $\alpha^k$, with $k$ being the ``logarithm'', and
  multiplication and division can be computed using logarithms.

  \subsection{Code}

  We restrict ourselves to the implementation of
  \gf{2^8}. Multiplications are done using lookup, division can be
  done using logarithm table, substraction and addition is \verb|XOR|.

**/

/*M
  \emph{Galois field element type.}

  We use polynomials over \gf{8}, so we need 8 bits.
**/
typedef unsigned char gf;

/*M
  \emph{Polynomial representation of field elements.}
**/
extern gf gf_polys[256];

/*M
  \emph{Logarithmic representation of field elements.}
**/
extern gf gf_logs[256];

/*M
  \emph{Precomputed multiplication table.}
**/
extern gf gf_mul[256][256];

/*M
  \emph{Precomputed inverse table.}
**/
extern gf gf_inv[256];

void gf_init(void);
void gf_add_mul(gf *a, gf *b, gf c, int k);

#define GF_MUL(x, y) (gf_mul[(x)][(y)])
#define GF_ADD(x, y) ((x) ^ (y))
#define GF_INV(x) (gf_inv[(x)])

/*C
**/

#endif /* GALOIS_H__ */