Erasure Coding is a fundamental part of many algorithms and have a variety of use cases like securing data availability in blockchains and STARKs. And one of the key building blocks of Erasure Coding is Fast Fourier Transforms. Life is a full circle, right? I ran away from the course teaching Fourier Transforms as far as possible and here I am, trying to learn it again. But this time it’s different as curiosity has appeared wildly.

But you’re a dirty little liar with a message of obsession to come

You got your head in the clouds

And your world’s upside down

Get away from the life you’re living

Song time baby!! This time it’s Dirty Little Thing by Velvet Revolver. Oooooh, it’s a wild song. I couldn’t get the tune out of my head when I first listened to it.


Process to convert sequence of complex numbers to another sequence of complex numbers .1




Vandermode matrix:

Working With Polynomials

An -degree polynomial is represented in coefficient form:

Lagrange coefficients:

Algorithms and Time Complexity:

  1. Addition/Subtraction: in coefficient and point-value
  2. Multiplication: in coefficient and in point-value and converting between the two can be done in

Let the polynomial be defined with coefficients , with results for .

Above equation is the DFT equation, represented as .



Lemma’s that help in understanding FFT:

  1. Cancellation Lemma:
  2. Halving Lemma: squares of nth complex root of unity are n/2 complex n/2th root of unity.
  3. Summation Lemma:

Uses the following relation: .


Domain should be power of 2, and complex roots of unity, .

Why does it need to be power of 2?

It actually depends upon the algorithm used, the most optimised Cooley-Tukey algorithm runs in time, and uses roots of unity as the domain. And Cooley-Tuckey uses properties to divide into length , mostly 2. This is the radix property of the algorithm, thus it requires domain to order of length .

Let’s understand radix-2 Cooley-Tukey FFT algorithm

Cooley-Tukey Algorithm



  1. Discrete Fourier Transform