1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229
|
/*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__ */
|