̬̬̬̈̬̬̬̬̈̬̬̬̬̬̪쬪̬̬̬̪쬪 >? @DD@D@DD@D@@D@D@@@@D@@@@@@DDD 0333303333033333033030330333303033 33333033 0303333333033 330303303030333333 3333033 33033033333 0333333 33033 03303033 033 333030303303303033 33303333033333 0303303303333303033033033333303330330333333303 ffff f`f`ff`fff`f`ff ff``f```f``f fff`f```f`f f`f`f`f`fff``f ``f`fffffffffffff`f`f f `ff `ff `ff f `f ff  ff`f`fff `ff fffff `ff `ff `ff `ff ff ff`ff `ff `ff `f`ff `f`f`ff`f`ff f ff`ff `fffff ffff fff ff`ff ff `f `ff`ff f`f`fff `ff`ff `ff ffff `fff `ff fffff`ff `ff fff`f `fff f `ff`f `ff `ff `ff `fff f y -- title: dft example -- author: cid -- desc: an example of discrete Fourier transform for the cyclic group of n elements (the usual dft) -- license: Unlicense -- version: 0.1 -- script: lua t=0 n= 20; flag_new = false function gen_data(n) -- generate random data data = {} for i=1,n do data[i] = math.random(-7,7)+math.random() end return data end function test_data_const(n) -- example data : costant function data = {} for i=1,n do data[i] = 3 end return data end function test_data_sin(n) -- example data: sine data = {} for i=1,n do data[i] = 2+4*math.sin(i) end return data end function plot_data(data,y,n,c) -- plot original data delta = math.floor(240/(n+1)) for i=1,n do line(delta*i,y,delta*i,y- data[i],13) circ(delta*i,y- data[i],2,c) end line(0,y,240,y,12) end function plot_datac(fdata,y,n,c,d) -- plot real and im. part of Fourier transform of data delta = math.floor(240/(n+1)) for i=1,n do line(delta*i,y,delta*i,y- fdata[1][i],13) line(delta*i,y,delta*i,y- fdata[2][i],13) circ(delta*i,y- fdata[1][i],2,c) circ(delta*i,y- fdata[2][i],2,d) end line(0,y,240,y,12) end function char_gen(n) -- generates the characters of the cyclic group of n elements -- i.e. exp(-2 pi * i * j / n) -- separated by real and imaginary part re = {} im = {} exp = math.exp for i = 1,n do re[i]= {} im[i]= {} for j = 1,n do re[i][j] = math.cos(-(2*(j-1)*(i-1)*math.pi)/n) im[i][j] = math.sin(-(2*(j-1)*(i-1)*math.pi)/n) end end return {re,im} end -- save characters (need to be cmputed only once) chars = char_gen(n) function dft(data,n) fre = {} fim = {} for i=1,n do fre[i] = 0 fim[i] = 0 for j=1,n do fre[i] = fre[i] + data[j]*chars[1][i][j] fim[i] = fim[i] + data[j]*chars[2][i][j] end end return {fre,fim} end function TIC() cls(0) print("Example of discrete Fourier transform" ,1,0,12) print("n = " .. n ,1,10,4) print("press 'z' for new data",120,10,14) print("Original data",1,19,12) if not flag_new then data = gen_data(n) -- data = test_data_const(n) -- data = test_data_sin(n) fdata = dft(data,n) flag_new = true end plot_data(data,40,n,3) print("Fourier transform",1,60,12) print("Real part",120,60,6) print("Im. part",190,60,9) plot_datac(fdata,110,n,6,9) if btnp(4) then flag_new=false end end