Package io.odilon.rs

Class Galois

  • public final class Galois
extends Object
    8-bit Galois Field This class implements multiplication, division, addition, subtraction, and exponentiation. The multiplication operation is in the inner loop of erasure coding, so it's been optimized. Having the class be "final" helps a little, and having the EXP_TABLE repeat the data, so there's no need to bound the sum of two logarithms to 255 helps a lot.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static int FIELD_SIZE
      The number of elements in the field.
      static int GENERATING_POLYNOMIAL
      The polynomial used to generate the logarithm table.
      static short[] LOG_TABLE
      Mapping from members of the Galois Field to their integer logarithms.

    • Constructor Summary

      Constructors 
      Constructor Description
      Galois()  

    • Field Detail

      • FIELD_SIZE

        public static final int FIELD_SIZE
        The number of elements in the field.
        See Also:
        Constant Field Values

      • GENERATING_POLYNOMIAL

        public static final int GENERATING_POLYNOMIAL
        The polynomial used to generate the logarithm table. There are a number of polynomials that work to generate a Galois field of 256 elements. The choice is arbitrary, and we just use the first one. The possibilities are: 29, 43, 45, 77, 95, 99, 101, 105, 113, 135, 141, 169, 195, 207, 231, and 245.
        See Also:
        Constant Field Values

      • LOG_TABLE

        public static final short[] LOG_TABLE
        Mapping from members of the Galois Field to their integer logarithms. The entry for 0 is meaningless because there is no log of 0. This array is shorts, not bytes, so that they can be used directly to index arrays without casting. The values (except the non-value at index 0) are all really bytes, so they range from 0 to 255. This table was generated by java_tables.py, and the unit tests check it against the Java implementation.

    • Constructor Detail

      • Galois

        public Galois()

    • Method Detail

      • add

        public static byte add​(byte a,
                       byte b)
        Adds two elements of the field. If you're in an inner loop, you should inline this function: it's just XOR.

      • subtract

        public static byte subtract​(byte a,
                            byte b)
        Inverse of addition. If you're in an inner loop, you should inline this function: it's just XOR.

      • multiply

        public static byte multiply​(byte a,
                            byte b)
        Multiplies to elements of the field.

      • divide

        public static byte divide​(byte a,
                          byte b)
        Inverse of multiplication.

      • exp

        public static byte exp​(byte a,
                       int n)
        Computes a**n. The result will be the same as multiplying a times itself n times.
        Parameters:
        a - A member of the field.
        n - A plain-old integer.
        Returns:
        The result of multiplying a by itself n times.

      • generateLogTable

        public static short[] generateLogTable​(int polynomial)
        Generates a logarithm table given a starting polynomial.

      • generateExpTable

        public static byte[] generateExpTable​(short[] logTable)
        Generates the inverse log table.

      • allPossiblePolynomials

        public static Integer[] allPossiblePolynomials()
        Returns a list of all polynomials that can be used to generate the field. This is never used in the code; it's just here for completeness.