ফুরিয়ে ট্রান্সফর্ম
ফুরিয়ে ট্রান্সফর্ম পদার্থবিজ্ঞান ও গণিতে প্রায়ই দেখা যায়, আর তাই এর দৈনন্দিন ব্যবহারও অনেক।
সংক্ষেপে, ফুরিয়ে ট্রান্সফর্ম একটি ইনপুট সিগন্যাল নেয়, যা প্রায়ই টাইম বা স্পেস ডোমেইনে থাকে, এবং সেটিকে ফ্রিকোয়েন্সি ডোমেইনে রূপান্তর করে।
আরও স্পষ্ট করে বললে, ইনপুট সিগন্যালটি যদি বিভিন্ন ফ্রিকোয়েন্সির মিশ্রণ (অর্থাৎ সুপারপজিশন) দিয়ে তৈরি হয়, তবে এই রূপান্তরটি আলাদা আলাদা ফ্রিকোয়েন্সি ছেঁকে বের করে তাদের আপেক্ষিক শক্তি দেখায়।
এ কারণেই এই রূপান্তরটি সিগন্যাল প্রসেসিং (যেমন ফিল্টারিং, কম্প্রেশন ইত্যাদি) এবং ডেটা সায়েন্সের অনেক প্রয়োগে একটি প্রধান হাতিয়ার।
তাই এটি প্রথমে যতটা ভাবা যায় তার চেয়ে অনেক বেশি ব্যবহৃত হয়, আর এ কারণেই কাল্পনিক সংখ্যা কোথায় অপরিহার্য হয়ে ওঠে তার একটি উৎকৃষ্ট উদাহরণ এটি, কারণ ফুরিয়ে ট্রান্সফর্মের আউটপুট সাধারণত একটি জটিল সংখ্যা।
ফুরিয়ে ট্রান্সফর্মের একটি ইন্টিগ্রাল রূপ থাকলেও আমরা ডিজিটাল, তাই আমাদের আগ্রহ ডিসক্রিট সংস্করণে।
এই রূপান্তরের ডেরিভেশন এই অনুশীলনীর পরিধির বাইরে, তবে ফরওয়ার্ড ডিসক্রিট ট্রান্সফর্ম (ফ্রিকোয়েন্সি ডোমেইনে) দেখতে এমন হয়:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
এখানে যোগফলটি n-এর ওপর চলে, আর N হলো স্যাম্পলের সংখ্যা, k হলো ফ্রিকোয়েন্সি, i হলো কাল্পনিক একক এবং xₙ হলো একটি আলাদা স্যাম্পল।
ফাস্ট ফুরিয়ে ট্রান্সফর্ম
ফুরিয়ে ট্রান্সফর্ম অত্যন্ত উপযোগী হলেও, সরলভাবে প্রয়োগ করা হলে এটি কিছুটা ধীর (O(n²))।
ফাস্ট ফুরিয়ে ট্রান্সফর্ম (FFT) এমন একটি অ্যালগরিদম যা এটিকে নাটকীয়ভাবে দ্রুত করে তোলে।
এটি সাধারণত ডিভাইড-অ্যান্ড-কনকার কৌশলের মাধ্যমে করা হয়, যা ফর্মুলেশনটির কিছু সিমেট্রি কাজে লাগায় এবং ফলস্বরূপ অ্যাসিম্পটটিকভাবে O(Nlog(N)) কমপ্লেক্সিটি দেয়।
এই গতি বৃদ্ধি এই রূপান্তরের ব্যবহারিক উপযোগিতা ও প্রয়োগের পরিধি অনেক বাড়িয়ে দেয়।
