ডিসক্রিট ফুরিয়ার ট্রান্সফর্ম (DFT)

১ · DTFT থেকে DFT — কেন এই পরিবর্তন দরকার

L২০-এ দেখেছি DTFT $X(e^{j\omega})$ একটি কন্টিনিউয়াস ফাংশন — $\omega$ যেকোনো বাস্তব মান নিতে পারে। কম্পিউটারে এটি সরাসরি সংরক্ষণ করা অসম্ভব (অসীম সংখ্যক মান)। সমাধান: $\omega$-কে ঠিক $N$টি সমান-ব্যবধানের মানে স্যাম্পল করা, $\omega_k = \frac{2\pi k}{N}$, যেখানে $k = 0, 1, \ldots, N-1$। এই স্যাম্পল-করা DTFT-ই DFTDiscrete Fourier Transformএকটি সসীম-দৈর্ঘ্যের সিগন্যালকে ঠিক N-টি সমান-ব্যবধানের ফ্রিকোয়েন্সি-বিনে রূপান্তরকারী সসীম সামেশন সূত্র — সম্পূর্ণভাবে কম্পিউটারে গণনাযোগ্য।:

প্রতিটি $k$-কে একটি ফ্রিকোয়েন্সি বিন বলা হয়, যা প্রকৃত ফ্রিকোয়েন্সি $f_k = \dfrac{k \cdot f_s}{N}$ Hz-এর সাথে সংশ্লিষ্ট (যেখানে $f_s$ হলো স্যাম্পল রেট, M২-তে সংজ্ঞায়িত)। বিন-থেকে-বিনের ব্যবধান, অর্থাৎ ফ্রিকোয়েন্সি রেজোলিউশন, হলো $f_s/N$ Hz — এটি L২৫-এ গুরুত্বপূর্ণ হয়ে উঠবে।

২ · হাতে-লেখা DFT বাস্তবায়ন

নিচে সরাসরি সূত্র অনুযায়ী একটি DFT ফাংশন লেখা হয়েছে — শুধু cmath.exp ও নেস্টেড লুপ, কোনো NumPy/SciPy নেই। এটি এই কোর্সের বাকি অংশে বারবার পুনরায় ব্যবহৃত হবে, তাই এখানে সঠিকভাবে যাচাই করা গুরুত্বপূর্ণ।

import cmath, math

def dft(x):
    """সরাসরি O(N^2) সামেশন সূত্র দিয়ে DFT -- এই কোর্সে বারবার পুনর্ব্যবহৃত হবে।"""
    N = len(x)
    X = []
    for k in range(N):
        s = sum(x[n] * cmath.exp(-2j * math.pi * k * n / N) for n in range(N))
        X.append(s)
    return X

fs = 64.0   # স্যাম্পল রেট (Hz)
N = 32      # স্যাম্পল সংখ্যা
f1, f2 = 8.0, 20.0   # প্রকৃত (জানা) ফ্রিকোয়েন্সি, Hz
a1, a2 = 1.0, 0.5    # অ্যামপ্লিটিউড

x = [a1 * math.sin(2 * math.pi * f1 * n / fs) + a2 * math.sin(2 * math.pi * f2 * n / fs)
     for n in range(N)]

X = dft(x)
mags = [abs(v) for v in X]

print(f"fs={fs} Hz, N={N}, বিন রেজোলিউশন fs/N = {fs/N} Hz")
print(f"{'k':>3} | {'freq (Hz)':>9} | {'|X[k]|':>8}")
for k in range(N // 2 + 1):
    print(f"{k:3d} | {k*fs/N:9.2f} | {mags[k]:8.3f}")

৩ · পিক-বিন খুঁজে ফ্রিকোয়েন্সি পুনরুদ্ধার

বাস্তব ব্যবহারে আমরা কোন বিনে পিক আছে তা "চোখে দেখে" নয়, বরং সর্বোচ্চ ম্যাগনিটিউডের বিন প্রোগ্রামগতভাবে খুঁজে বের করি। নিচের কোডে (উপরের x, X, mags ব্যবহার করে) সেই অনুসন্ধান দেখানো হলো।

# উপরের কোষের x, X, mags, fs, N ব্যবহার করে --
# k=0 (DC) বাদ দিয়ে, k=1..N/2 রেঞ্জে সর্বোচ্চ দুটো ম্যাগনিটিউডের বিন খোঁজা
sorted_bins = sorted(range(1, N // 2 + 1), key=lambda k: -mags[k])
top2 = sorted_bins[:2]

print("সর্বোচ্চ ম্যাগনিটিউডের বিন (k=1..N/2):", top2)
for k in top2:
    f_recovered = k * fs / N
    print(f"  k={k} -> পুনরুদ্ধারকৃত ফ্রিকোয়েন্সি = {f_recovered} Hz, |X[k]| = {mags[k]:.4f}")

print()
print(f"প্রকৃত ফ্রিকোয়েন্সি ছিল: {f1} Hz ও {f2} Hz")