Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Lattice discrete Fourier transforms

  1. May 12, 2010 #1
    1. The problem statement, all variables and given/known data
    Hi

    Say I have a 5x5 lattice, where each entry (or we can call it site) contains the number 1. Now, on the lattice we have a function g(R), which is equal to the number on the site. In this case g(R)=1 for all sites (here R is a vector from the point (3,3), which denotes the site we are talking about).

    Now I wish to Fourier transform the function g, and I use the lattice discrete FT

    [tex]
    f(\mathbf{k}) = \sum_{\mathbf{R} } e^{i \mathbf{k} \cdot \mathbf{R} } g(\mathbf{R})
    [/tex]

    where k is a vector. Now, since each site contains the number 1, the system is homogeneous, and from the inverse Fourier transform,

    [tex]
    g(\mathbf R) = \sum_{\mathbf k} e^{-i\mathbf k\mathbf R} f(\mathbf k),
    [/tex]

    we see that only the k=0-term can survive, since g(R) is constant. But by performing the sum

    [tex]
    f(\mathbf{k}) = \sum_{\mathbf{R} } e^{i \mathbf{k} \cdot \mathbf{R} } g(\mathbf{R}),
    [/tex]

    it is quite obvious that all terms are there, i.e. it is not only the k=0 term that survives. That is a paradox I cannot explain. Can you guys shed some light on this?

    Best,
    Niles.
     
    Last edited: May 12, 2010
  2. jcsd
  3. May 12, 2010 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your exponents are missing some factors. Instead of

    [tex]e^{-ik\cdot R}[/tex]

    it should be

    [tex]e^{-2\pi i k \cdot R / N}[/tex]

    where in your case [itex]N = 5[/itex].

    Then for [itex]k \neq 0[/itex] you will be summing evenly spaced samples around the unit circle, so the result will be zero.
     
    Last edited: May 12, 2010
  4. May 12, 2010 #3

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    P.S. Since your function is constant, the 2d DFT is equivalent to two iterated 1d DFT's. If I write [itex]k = (k_1, k_2)[/itex] and [itex]R = (R_1, R_2)[/itex], then

    [tex]f(k) = \sum_R e^{2\pi i (k_1 R_1 + k_2 R_2) / N} = \sum_{R_1} e^{2\pi i k_1 R_1 / N} \sum_{R_2} e^{2\pi i k_2 R_2 / N}[/tex]
     
  5. May 12, 2010 #4
    Thanks for helping. I just tried doing it again (with the correct factor in the exponential) for a 3x3 system, but still other terms show up (I tried writing it up manually).
     
  6. May 13, 2010 #5
    I'm sorry to bump the thread, but it is extremely important that this issue gets solved (I potentially have to redo 6 months of course work), and I am all out of good ideas.
     
    Last edited: May 13, 2010
  7. May 13, 2010 #6

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I'm not sure what is going wrong for you. Maybe I am misinterpreting what you want to do. I wrote the following segment of Matlab code (actually Octave, but it should work for Matlab as well) to calculate your sum:

    Code (Text):

    fid = fopen('out.txt','w');

    for a = -2:2
        for b = -2:2
            k = [a b];
            f_k = 0;
            for m = -2:2
                for n = -2:2
                    r = [m n];
                    f_k = f_k + exp(i*2*pi * (k * r') / 5);
                end
            end
            fprintf(fid, 'f([%d %d]) = %f + i*%f\n', a, b, real(f_k), imag(f_k));
        end
    end

    fclose(fid);
     
    Here is the result I got:

    f([-2 -2]) = 0.000000 + i*0.000000
    f([-2 -1]) = -0.000000 + i*0.000000
    f([-2 0]) = -0.000000 + i*0.000000
    f([-2 1]) = -0.000000 + i*-0.000000
    f([-2 2]) = 0.000000 + i*0.000000
    f([-1 -2]) = -0.000000 + i*0.000000
    f([-1 -1]) = -0.000000 + i*0.000000
    f([-1 0]) = 0.000000 + i*-0.000000
    f([-1 1]) = -0.000000 + i*-0.000000
    f([-1 2]) = 0.000000 + i*0.000000
    f([0 -2]) = -0.000000 + i*0.000000
    f([0 -1]) = 0.000000 + i*0.000000
    f([0 0]) = 25.000000 + i*0.000000
    f([0 1]) = 0.000000 + i*0.000000
    f([0 2]) = -0.000000 + i*0.000000
    f([1 -2]) = 0.000000 + i*0.000000
    f([1 -1]) = -0.000000 + i*0.000000
    f([1 0]) = 0.000000 + i*0.000000
    f([1 1]) = -0.000000 + i*-0.000000
    f([1 2]) = -0.000000 + i*0.000000
    f([2 -2]) = 0.000000 + i*0.000000
    f([2 -1]) = -0.000000 + i*0.000000
    f([2 0]) = -0.000000 + i*0.000000
    f([2 1]) = -0.000000 + i*0.000000
    f([2 2]) = 0.000000 + i*0.000000
     
  8. May 13, 2010 #7
    No no, you got it. What I want to do is to find f(k). But you change the value of the k-vector? Why is it that you do that, instead of leaving it just as (kx,ky)?
     
  9. May 13, 2010 #8
    Wait, ignore my post #7. I will try out your example, and return when I get a result.
     
  10. May 13, 2010 #9
    Ok, now I get the same table as you. But the problem comes when we choose e.g. k=(0, 1.5)T - there f(k) blows up (I get f(k)=6.18 in that case).
     
  11. May 13, 2010 #10

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, if you look at points that do not have integer coordinates, you will not get zero. In fact, if you evaluate f at all points (instead of just integers), you will obtain a 2-dimensional "sinc" function.

    The reason for this is that you only use finitely many terms in the sum. You are in effect calculating the Fourier transform of a 2-dimensional "rectangle" function.

    If you use more terms, you will more closely approximate an "impulse."

    See here for a visualization:

    http://cnyack.homestead.com/files/artran/ft2dxy1.htm
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook