anon.mixminion.fec
Class FECMath

java.lang.Object
  anon.mixminion.fec.FECMath

public class FECMath
extends java.lang.Object

This class provides the majority of the logic for the pure Java implementation of the vandermonde FEC codes. This code is heavily derived from Luigi Rizzo's original C implementation. Copyright information can be found in the 'LICENSE' file that comes with this distribution. (c) Copyright 2001 Onion Networks (c) Copyright 2000 OpenCola

Author:

Justin F. Chapweske (justin@chapweske.com), JAP-Team -- made some changes

Field Summary

char[]	gf_exp To speed up computations, we have tables for logarithm, exponent and inverse of a number.
int[]	gf_log
char[][]	gf_mul_table gf_mul(x,y) multiplies two numbers.
int	gfBits The following parameter defines how many bits are used for field elements.
int	gfSize
char[]	inverse
static java.lang.String[]	prim_polys Primitive polynomials - see Lin & Costello, Appendix A, and Lee & Messerschmitt, p.

Constructor Summary

FECMath()

FECMath(int gfBits)

Method Summary

void	addMul(byte[] dst, int dstPos, byte[] src, int srcPos, byte c, int len)
void	addMul(char[] dst, int dstPos, char[] src, int srcPos, char c, int len)
protected char[]	createDecodeMatrix(char[] encMatrix, int[] index, int k, int n) createDecodeMatrix constructs the encoding matrix given the indexes.
char[]	createEncodeMatrix(int k, int n)
static char[]	createGFMatrix(int rows, int cols) Generate GF(2**m) from the irreducible polynomial p(X) in p[0]..p[m] Lookup tables: index->polynomial form gf_exp[] contains j= \alpha^i; polynomial form -> index form gf_log[ j = \alpha^i ] = i \alpha=x is the primitive element of GF(2^m) For efficiency, gf_exp[] has size 2*gfSize, so that a simple multiplication of two numbers can be resolved without calling modnn
void	generateGF()
void	initMulTable()
void	invertMatrix(char[] src, int k)
void	invertVandermonde(char[] src, int k)
static boolean	isIdentity(char[] m, int k)
void	matMul(char[] a, char[] b, char[] c, int n, int k, int m)
void	matMul(char[] a, int aStart, char[] b, int bStart, char[] c, int cStart, int n, int k, int m)
char	modnn(int x) modnn(x) computes x % gfSize, where gfSize is 2**gfBits - 1, without a slow divide.
char	mul(char x, char y)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

gfBits

public int gfBits

The following parameter defines how many bits are used for field elements. This probably only supports 8 and 16 bit codes at this time because Java lacks a typedef construct. This code should perhaps be redone with some sort of template language/ precompiler for Java.

gfSize

public int gfSize

prim_polys

public static final java.lang.String[] prim_polys

Primitive polynomials - see Lin & Costello, Appendix A, and Lee & Messerschmitt, p. 453.

gf_exp

public char[] gf_exp

To speed up computations, we have tables for logarithm, exponent and inverse of a number. If gfBits <= 8, we use a table for multiplication as well (it takes 64K, no big deal even on a PDA, especially because it can be pre-initialized an put into a ROM!), otherwhise we use a table of logarithms.

gf_log

public int[] gf_log

inverse

public char[] inverse

gf_mul_table

public char[][] gf_mul_table

gf_mul(x,y) multiplies two numbers. If gfBits<=8, it is much faster to use a multiplication table. USE_GF_MULC, GF_MULC0(c) and GF_ADDMULC(x) can be used when multiplying many numbers by the same constant. In this case the first call sets the constant, and others perform the multiplications. A value related to the multiplication is held in a local variable declared with USE_GF_MULC . See usage in addMul1().

Constructor Detail

FECMath

public FECMath()

FECMath

public FECMath(int gfBits)

Method Detail

generateGF

public final void generateGF()

initMulTable

public final void initMulTable()

modnn

public final char modnn(int x)

modnn(x) computes x % gfSize, where gfSize is 2**gfBits - 1, without a slow divide.

mul

public final char mul(char x,
                      char y)

createGFMatrix

public static final char[] createGFMatrix(int rows,
                                          int cols)

Generate GF(2**m) from the irreducible polynomial p(X) in p[0]..p[m] Lookup tables: index->polynomial form gf_exp[] contains j= \alpha^i; polynomial form -> index form gf_log[ j = \alpha^i ] = i \alpha=x is the primitive element of GF(2^m) For efficiency, gf_exp[] has size 2*gfSize, so that a simple multiplication of two numbers can be resolved without calling modnn

addMul

public final void addMul(char[] dst,
                         int dstPos,
                         char[] src,
                         int srcPos,
                         char c,
                         int len)

addMul

public final void addMul(byte[] dst,
                         int dstPos,
                         byte[] src,
                         int srcPos,
                         byte c,
                         int len)

matMul

public final void matMul(char[] a,
                         char[] b,
                         char[] c,
                         int n,
                         int k,
                         int m)

matMul

public final void matMul(char[] a,
                         int aStart,
                         char[] b,
                         int bStart,
                         char[] c,
                         int cStart,
                         int n,
                         int k,
                         int m)

isIdentity

public static final boolean isIdentity(char[] m,
                                       int k)

invertMatrix

public final void invertMatrix(char[] src,
                               int k)
                        throws java.lang.IllegalArgumentException

Throws:

java.lang.IllegalArgumentException

invertVandermonde

public final void invertVandermonde(char[] src,
                                    int k)

createEncodeMatrix

public final char[] createEncodeMatrix(int k,
                                       int n)

createDecodeMatrix

protected final char[] createDecodeMatrix(char[] encMatrix,
                                          int[] index,
                                          int k,
                                          int n)

createDecodeMatrix constructs the encoding matrix given the indexes.