18.2. Fast Fourier Transform🔗

The core of the erasure coding is an additive FFT over GF(2^16), following the Cantor basis construction. The FFT transforms data symbols into evaluation points; the IFFT inverts the transform for recovery.

def

Jar.Erasure.fftInPlace (data : Array UInt16)
  (pos size truncatedSize skewDelta : Nat) : Array UInt16
Jar.Erasure.fftInPlace
  (data : Array UInt16)
  (pos size truncatedSize skewDelta :
    Nat) :
  Array UInt16

In-place decimation-in-time FFT (fast Fourier transform) on GF(2^16) elements. Operates on data[pos .. pos + size] where size is a power of 2.

def

Jar.Erasure.ifftInPlace (data : Array UInt16)
  (pos size truncatedSize skewDelta : Nat) : Array UInt16
Jar.Erasure.ifftInPlace
  (data : Array UInt16)
  (pos size truncatedSize skewDelta :
    Nat) :
  Array UInt16

In-place decimation-in-time IFFT (inverse fast Fourier transform). Operates on data[pos .. pos + size] where size is a power of 2.