Class GaliosFieldTableOps

java.lang.Object
boofcv.alg.fiducial.qrcode.GaliosFieldTableOps

public class GaliosFieldTableOps
extends Object
Precomputed look up table for performing operations on GF polynomials of the specified degree.

Code and code comments based on the tutorial at [1].

[1] Reed-Solomon Codes for Coders Viewed on September 28, 2017

  • Constructor Details

    • GaliosFieldTableOps

      public GaliosFieldTableOps​(int numBits, int primitive)
      Specifies the GF polynomial
      Parameters:
      numBits - Number of bits needed to describe the polynomial. GF(2**8) = 8 bits
      primitive - The primitive polynomial
  • Method Details

    • multiply

      public int multiply​(int x, int y)
      Computes the following (x*y) mod primitive. This is done by
    • divide

      public int divide​(int x, int y)
      Computes the following the value of output such that:

      divide(multiply(x,y),y)==x for any x and any nonzero y.

    • power

      public int power​(int x, int power)
      Computes the following x**power mod primitive
    • power_n

      public int power_n​(int x, int power)
    • inverse

      public int inverse​(int x)
      Computes the following 2**(max-x) mod primitive
    • polyScale

      public void polyScale​(DogArray_I8 input, int scale, DogArray_I8 output)
      Scales the polynomial.

      Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

      Parameters:
      input - Input polynomial.
      scale - scale
      output - Output polynomial.
    • polyAdd

      public void polyAdd​(DogArray_I8 polyA, DogArray_I8 polyB, DogArray_I8 output)
      Adds two polynomials together. output = polyA + polyB

      Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

      Parameters:
      polyA - (Input) First polynomial
      polyB - (Input) Second polynomial
      output - (Output) Results of addition
    • polyAdd_S

      public void polyAdd_S​(DogArray_I8 polyA, DogArray_I8 polyB, DogArray_I8 output)
      Adds two polynomials together.

      Coefficients for smallest powers are first, e.g. 2*x**3 + 8*x**2+1 = [1,0,2,8]

      Parameters:
      polyA - (Input) First polynomial
      polyB - (Input) Second polynomial
      output - (Output) Results of addition
    • polyAddScaleB

      public void polyAddScaleB​(DogArray_I8 polyA, DogArray_I8 polyB, int scaleB, DogArray_I8 output)
      Adds two polynomials together while scaling the second.

      Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

      Parameters:
      polyA - (Input) First polynomial
      polyB - (Input) Second polynomial
      scaleB - (Input) Scale factor applied to polyB
      output - (Output) Results of addition
    • polyMult

      public void polyMult​(DogArray_I8 polyA, DogArray_I8 polyB, DogArray_I8 output)

      Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

    • polyMult_flipA

      public void polyMult_flipA​(DogArray_I8 polyA, DogArray_I8 polyB, DogArray_I8 output)
    • polyMult_S

      public void polyMult_S​(DogArray_I8 polyA, DogArray_I8 polyB, DogArray_I8 output)
      Identical to polyMult(DogArray_I8, DogArray_I8, DogArray_I8)

      Coefficients for smallest powers are first, e.g. 2*x**3 + 8*x**2+1 = [1,0,2,8]

    • polyEval

      public int polyEval​(DogArray_I8 input, int x)
      Evaluate the polynomial using Horner's method. Avoids explicit calculating the powers of x.

      01x**4 + 0fx**3 + 36x**2 + 78x + 40 = (((01 x + 0f) x + 36) x + 78) x + 40

      Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

      Parameters:
      input - Polynomial being evaluated
      x - Value of x
      Returns:
      Output of function
    • polyEval_S

      public int polyEval_S​(DogArray_I8 input, int x)
      Evaluate the polynomial using Horner's method. Avoids explicit calculating the powers of x.

      01x**4 + 0fx**3 + 36x**2 + 78x + 40 = (((01 x + 0f) x + 36) x + 78) x + 40

      Coefficients for smallest powers are first, e.g. 2*x**3 + 8*x**2+1 = [1,0,2,8]

      Parameters:
      input - Polynomial being evaluated
      x - Value of x
      Returns:
      Output of function
    • polyEvalContinue

      public int polyEvalContinue​(int previousOutput, DogArray_I8 part, int x)
      Continue evaluating a polynomial which has been broken up into multiple arrays.
      Parameters:
      previousOutput - Output from the evaluation of the prior part of the polynomial
      part - Additional segment of the polynomial
      x - Point it's being evaluated at
      Returns:
      results
    • polyDivide

      public void polyDivide​(DogArray_I8 dividend, DogArray_I8 divisor, DogArray_I8 quotient, DogArray_I8 remainder)
      Performs polynomial division using a synthetic division algorithm.

      Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

      Parameters:
      dividend - (Input) Polynomial dividend
      divisor - (Input) Polynomial divisor
      quotient - (Output) Division's quotient
      remainder - (Output) Divisions's remainder
    • polyDivide_S

      public void polyDivide_S​(DogArray_I8 dividend, DogArray_I8 divisor, DogArray_I8 quotient, DogArray_I8 remainder)
      Performs polynomial division using a synthetic division algorithm.

      Coefficients for smallest powers are first, e.g. 2*x**3 + 8*x**2+1 = [1,0,2,8]

      Parameters:
      dividend - (Input) Polynomial dividend
      divisor - (Input) Polynomial divisor
      quotient - (Output) Division's quotient
      remainder - (Output) Divisions's remainder