Administrace komentářů

complex = {__mt={} }

function complex.new(r, i)
  local new={real=r, imaginary=i or 0}
  setmetatable(new,complex.__mt)
  return new
end

function complex.__mt.__add(c1, c2)
  return complex.new(c1.real + c2.real, c1.imaginary + c2.imaginary)
end

function complex.__mt.__sub(c1, c2)
  return complex.new(c1.real - c2.real, c1.imaginary - c2.imaginary)
end

function complex.__mt.__mul(c1, c2)
  return complex.new(c1.real * c2.real - c1.imaginary * c2.imaginary,
					 c1.real * c2.imaginary + c1.imaginary * c2.real)
end

function complex.expi(i)
  return complex.new(math.cos(i),math.sin(i))
end

function complex.__mt.__tostring(c)
  return "("..c.real..","..c.imaginary..")"
end


--[[---------------------------------------------------------------------
Cooley–Tukey Fast Fourier Transformation                                -
Zdroj: https://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm         -
]]-----------------------------------------------------------------------

function FFT(vect)
  local n=#vect
  if n<=1 then return vect end

  local odd,even={},{}
  for i=1,n,2 do
    odd[#odd+1]=vect[i]
    even[#even+1]=vect[i+1]
  end

  FFT(even)
  FFT(odd)

  for k=1,n/2 do
    local t=even[k] * complex.expi(-2*math.pi*(k-1)/n)
    vect[k] = odd[k] + t
    vect[k+n/2] = odd[k] - t
  end
  return vect
end

--[[-----------------------------------------------------------------------
Inverse Fast Fourier Transformation                                       -
]]-------------------------------------------------------------------------

function IFFT(amplitudes)

	local N = #amplitudes
	local input = 1 / N

	local i=nil
	for i=1, N do
		amplitudes[i].imaginary = -amplitudes[i].imaginary
	end

	FFT(amplitudes)

	for i=1, N do
		amplitudes[i].imaginary = -amplitudes[i].imaginary
		amplitudes[i].real = amplitudes[i].real * input
		amplitudes[i].imaginary = amplitudes[i].imaginary * input
	end

	return amplitudes
end

function toComplex(vector)
  vect={}
  for r,i in ipairs(vector) do
    vect[r]=complex.new(i)
  end
  return vect
end

-- test
data = toComplex{1, 1, 1, 1, 0, 0, 0, 0}

print("orig:", unpack(data))
print("fft :", unpack(FFT(data)))
print("ifft:", unpack(IFFT(data)))