-تبدیل فوریه :
بدست آوردن طیف فرکانسی موج صوتی در گوش بصورت مکانیکی صورت می گیرد.
در ریاضیات با استفاده از تبدیلهای فوریه و در کامپیوتر با استفاده از FFT ( Fast Fourier Transform) این امر صورت میگیرد.
ساختار صوت :
صوت ارتعاشی است که در هوا منتشر می شود.
( یا در محیط های فیزیکی دیگر به جز خلا ) اغلب صداها در طبیعت طیف فرکانسی مشخصی ندارند و اطلاعات مفید کمی را شامل می شوند .
صداهای با طیف فرکانسی مشخص محتوی اطلاعات بیشتری هستند .
برای شناخت اهمیت فرکانس در صدا باید در مورد نحوه تولید ودریافت صوت بررسی صورت گیرد.
بسیاری از اشیا در زمان نوسان ، امواج صوتی تولید
می کنند .
وقتی صحبت می کنیم یا آواز می خوانیم تارهای صوتی به ارتعاش در می آیند و صدا در گلو دهان و بینی نوسان می کند.
آنچه مهم است این است که تکرار حرکت یک شکل موج باعث تشخیص صوت از نویز می شود .
هر صوت فرازو فرودی دارد .
بوسیله فرکانس مشخص می شود که شکل موج به چه صورت تکرار می شود .
روشی که گوش فرکانسهای مختلف را تفکیک می کند جالب توجه است .
مبنای آن بر اصل تشدید ( رزونانس ) استوار است .
ضربه یک جسم با فرکانس خاص را به ارتفاش وا می دارد.
همچنین آن جسم با موج صوتی با فرکانس مشابه شروع به نوسان می کند .
به عنوان مثال اگر به یک لیوان شیشه ای ضربه وارد کنیم صدایی از آن متصاعد می شود .
اگر سعی کنیم همان صدا را تولید کنیم و لیوان را در معرض آن قرار دهیم لیوان شروع به ارتعاش می کند .
مولکولهای هوا که توسط ارتعاشات صوتی مرتعش شده اند سطح لیوان را دچار فشار و کشش می کنند .
هنگامی که این کشش وفشارهای کوچک منطبق با فرکانس طبیعی لیوان باشند می توانند لیوان را تحریک به نوسان کنند.
در گوش تشدید در داخلی ترین بخش گوش که حلزون گوش نامیده می شود اتفاق میافتد .
قسمتهای مختلف این بخش حلزونی شکل با فرکانسهای مختلف نوسان می کنند.
وقتی یک قسمت خاص از حلزون گوش شروع به تشدید می کند گیرنده های عصبی که در آنجا قرار دارند سیگنال را دریافت می کنند و آنرا به مغز می فرستند .
اغلب صداها به یکباره در مناطق مختلف حلزون گوش تشدید ایجاد میکنند که این صداها بصورت مختلط شنیده می شود.
1-2 -نمونه گیری صدا :
امروزه اغلب صدا بصورت دیجیتالی ذخیره میشود .
ابتدا میکروفن صوت را به جریانهای الکتریکی تبدیل می کند.
نوسان متوالی فشار هوا به نوسان متوالی ولتاژ در یک مدار الکتریکی تبدیل می شود .
این تغییرات سریع ولتاژ در یک مبدل آنالوگ به دیجیتال به یک سری از اعداد تبدیل می شود.
عملکرد مبدل ADC شبیه یک ولتمتر دیجیتال است که تعداد زیادی اندازه گیری در ثانیه انجام میدهد .
هر یک از نتایج اندازه گیری بصورت یک عدد ذخیره میشود .
این اعداد نمونه یا سمپل نامیده می شوند .
تبدیل کامل یک صدا به یک سری از اعداد ، نمونه گیری (Sampling) نامیده می شود .
کارت صدا در کامپیوتر در واقع یک مبدل دیجیتال کننده است که جریانی از سمپل ها را تولید می کند که بوسیله نرم افزار سیستم می تواند مورد استفاده قرار گیرد .
مثال :
به عنوان نمونه وضعیت ضبط موسیقی در یک CD را مورد بررسی قرار میدهیم .
موسیقی بصورت 44100 سمپل در ثانیه ضبط می شود که هر نمونه بصورت 16 بیت ذخیره می شوند .
در ضبط استریو این میزان دو برابر می شود.
به بیان دیگر برای ضبط موسیقی بصورت استریو برای یک ساعت به635,000,000 بایت فضا نیاز است .
1-3 -بردارها و موج ضربه ای :
صدا در کامپیوتر در بافرهای حاوی سمپل ذخیره می شود .
یک سری از اعداد صحیح که هر یک متناظر با دامنه صدا در یک لحظه مجزا است .
یک بردار را می توان بصورت آرایه ای از اعداد نمایش داد .
1-3-1 -آنالیز بردار ضربه : یک بافر را که حاوی سمپل های یک صوت است در نظر بگیرید .
اگر بافرشامل n نمونه باشد می توان آنرا بصورت یک بردار n بعدی نمایش داد.
هر نمونه معرف یک مختصات در فضای n بعدی است .
در صورتیکه تنها بافرهای با سه سمپل را در نظر بگیریم سمپل ها ، مختصات X ،Y و Z یک بردار سه بعدی می شوند .
به طور معمول صدها سمپل در یک بافر داریم .
همچنین تصور یک فضای n بعدی که یک بردار را تشکیل داده اند مشکل است .
از نظر ریاضی با محاسبه مجدد مختصات بردار سمپل ها که از بردارهای مبنا مخنلف در فضای n – بعدی استفاده میکنند تبدیل موج ضربه ای بدست می آید که نتیجه بصورت n شماره خواهد بود .
1-3-2- تبدیل موج ضربه ای 8 – نقطه ای : در صورتیکه یک بافر با 8 سمپل در نظر گرفته شود که سمپل ها پی در پی در آن قرار دارند برای رسم بافر بصورت یک بردار n – بعدی سمپل ها بصورت 8 بخش عمودی یکی پس از دیگری نشان داده می شوند.
n بردار مبنا که معرف سمپل ها هستند می توانند در روش مشابهی نشان داده شوند .
روشی که اغلب در آنالیز موج ضربه ای بکار می رود مبنای Haar است .
این مبناهای خاص عمود بر محور هستند .
ضرب داخلی هر جفت از آنها صفر و ضرب داخلی هر یک در خودش مساوی یک است .
برای مثال آخرین بردار مبنا در تصویر فوق مشخصات زیر را دارا می باشد : i8 = (0, 0, 0, 0, 0, 0, a, -a), a = 1/√2 (i8*i8) = 02 + 02 + 02 + 02 + 02 + 02 + a2 + a2 = 2 * a2 = 1 از ضرب داخلی بردار اختیاری V به مختصاتv = (v1, v2, v3, v4, v5, v6, v7, v8)با n امین بردار مبنا ، ضریب موج ضربه ای هشتم موج V را حساب می کنیم : w8 = (v * i8) = (v7 - v8)/√2 این ضرب تفاوت بین هفتمین و هشتمین ضریب بردار که معرف تفاوت سمپل ها در بافر محتوی سمپل ها هستند را نشان می دهد .
اگر تغییرات سیگنال آهسته باشد این اختلاف خیلی کوچک خواهد بود .
با توجه به تصاویر بردارهای مبنا می توان ضرایب موج ضربه ای اول را بدست آورد .
( ضرب داخلی V با in ) ضریب اول میانگین دامنه سیگنال و ضریب دوم اختلاف بین نیمه نخست سیگنال و نیمه دوم آن را بیان می کند .
به این ترتیب تصویر کلی سیگنال بدست می آید .
یک سری از ضرایب موج ضربه ایw1, w2, ...
w8 تبدیل موج ضربه ای سیگنال V نامیده می شود.
چون بافرهای با 8 سمپل مد نظر است آنرا تبدیل موج ضربه ای 8 نقطه ای می نامیم .
برای بدست آوردن سیگنالی که ضرایب موج ضربه ای آن داده شده است بردارهای مبنا را در ضرایب آنها ضرب کرده و با هم جمع میشود.
v = w1 i1 + w2 i2 + ...
+ w8 i8 فصل دوم تحلیل فوریه 2-1- تحلیل فوریه : تبدیل فوریه مورد خاص تبدیل موج با بردارهای مبنا با توابع مثلثاتی Sin و Cos است .
با دقت در اسیلاتور هارمونیک مشاهده می شود وقتی اجسام نوسان می کنند حرکت آنها تابع توابع مثلثاتی است .
2-1-1 - تشدید : هنگامی که یک موج صوتی به یک اسیلاتور اثر می کند ممکن است نوسانگر را تحریک کند .
وقتی موج صوتی نوسانگر را تحریک کرد اسیلاتور شروع به نوسان با مشخصه فرکانسی خودش می کند .
نوسان اسیلاتور مبین این مطلب است که موج صوتی محتوی مولفه فرکانسی نوسانگر است .
موج صوتی می تواند یک موج پیچیده باشد که شباهتی به موج سینوسی ندارد ولی در هر صورت در خودش یک مولفه فرکانسی مشخص دارد .
چون موج صوتی اسیلاتور را به نوسان وا می دارد باید به طور پیوسته انرژی خود را به اسیلاتور منتقل نماید .موج صوتی اسیلاتور را دچار آونگ می کند .
می توان مشخص کرد صوت مشخصه فرکانسی لازم برای نوسان اسیلاتور را دارد یا نه .
تنها بایستی نمونه های متوالی صوت را در وزن های مخصوص ضرب نموده و آنها را با هم تلفیق کنیم .
وقتی نوسانگر در نیمه نخست پریود قرار دارد این وزن ها مثبت در نظر گرفته می شود و در نیمه دوم پریود این وزنها را منفی در نظر می گیریم .
از آنجایی که بهترین زمان انتقال انرژی وقتی است که نوسانگر در نیمه نوسان است بلندترین وزن در این نقطه در نظر گرفته می شود .
همه این موارد در نظر گرفته می شود تا بهترین تابع وزن بدست آید .
این تابع را بصورت سینوسی در نظر می گیریم .
وقتی صوت شامل فرکانس مشخصی نباشد این جمع نزدیک صفر می شود .
نمونه های مثبت بطور متوسط نمونه های منفی را خنثی می کنند .
اگر یک همبستگی بین صوت و توابع وزنها باشد این همبستگی تلفیق می شود و نتیجه ممکن است یک عدد بزرگ باشد .
در صورتیکه یک صوت را از نظر فیزیکی آنالیز کنیم بایستی یک سری نوسانگر که هر یک اندکی در فرکانس با هم تفاوت دارند در نظر گرفته شود .
در صورتیکه صوت آنها را به نوسان وا دارد هر فرکانسی که در موج صوتی وجود دارد نوسانگر نظیر آن را به حرکت در می آورد .
به جای استفاده از اسیلاتورها که با فرکانسهای اندکی متفاوت وفق داده شده اند میتوان موج صوتی را با استفاده از ریاضیات تحلیل کرد تا بدست آید کدام اسیلاتورها باید تحریک شوند .
هر اسیلاتور نظیر یک تابع وزن سینوسی با فرکانس مشخص است .
اگر صوت بصورت دیجیتال باشد میتوان نمونه های آنرا در اوزان نظیر آن ضرب کرد وبا هم تلفیق نمود .
بدون دیجیتال سازی باید موج صوتی را در تابع سینوسی ضرب کرد و سپس انتگرالگیری نمود .
اعداد حاصله نشان میدهد چه مقدار از فرکانسهای معین در یک موج صوتی خاص وجود دارد .
یک سری از چنین اعدادی با فرکانسهای مختلف نظیر آن تبدیل فوریه ( به عبارت بهتر تبدیل فوریه دیجیتال DFT ) یا طیف فرکانسی صوت نامیده می شود .
توابع سینوسی به تنهایی کافی نیستند برای تکمیل باید توابع کسینوسی را اضافه نماییم اگر چه نظیر فرکانس نمودارهای سینوسی باشد .
توابع کسینوسی همفاز نبودن نوسان اسیلاتورها را نشان می دهند .
2-2- ترکیب فوریه : موج ضربه ای فوریه یک دستگاه متعامد را نشان می دهد .
در صورتیکه ضرب اسکالر به کار رود ضرب عددی دو بردار صفر می شود .
همچنین با نرمالیزاسیون مناسب میتوان مربعات این بردارها را مساوی یک بدست آورد .
هر بافر با n نمونه می تواند به n بردار که n عدد می دهد تبدیل شود .
این اعداد ضرایب فوریه هستند .
این اعداد تبدیل فوریه دیجیتال بافر را شکل میدهد .
به طور معکوس با داشتن این اعداد میتوان بافر را بازسازی نمود .
کافی است هر بردار پایه در ضریب فوریه نظیر آن ضرب شود و همه را با هم تلفیق کرد تا یک بردار n بعدی بدست آید که دقیقا معادل بافر اصلی است .
عملیات بازسازی موج صوتی از ضرایب فوریه آن ترکیب فوریه نامیده می شود .
هر بردار مبنا یک موج نمونه سینوسی با فرکانس معین است .
با اضافه کردن این امواج بهم با ضرایب مناسب میتوان هر موج صوتی را دوباره بازسازی کرد .
فصل سوم تبدیل فوریه دیجیتال 3-1- تبدیل فوریه دیجیتال : مبانی فوریه بر نمونه های توابع سینوسی و کسینوسی مبتنی است .
با استفاده از اعداد مختلط این دو می توانند با هم ترکیب شوند و به صورت یک تابع نمایی نشان داده شوند .
برای نمونه یک تبدیل فوریه چهار نقطه ای در نظر گرفته می شود .
به چهار بردار مبنای ek, k = 0...3 نیاز است که نمونه های نمایی فرکانسهای صعودی هستند .
ek = (e-2πi(0*k)/4, e-2πi(1*k)/4, e-2πi(2*k)/4, e-2πi(3*k)/4) اینها چهار مثال از تابع نمایی e-2πitk/4 هستند که در آن t = 0, 1, 2, 3 .
در اینصورت خواهیم داشت : e0 = (1, 1, 1, 1) e1 = (1, e-2πi/4, e-2πi2/4, e-2πi3/4) e2 = (1, e-2πi2/4, e-2πi4/4, e-2πi6/4) e3 = (1, e-2πi3/4, e-2πi6/4, e-2πi9/4) جزء حقیقی و موهومی توابع فوق به شکل زیر ساده می شود : در حقیقت 4 بردار مبنای مستقل در فضای 4 بعدی وجود دارد .
در زیر قسمت حقیقی بردارهای مبنا دیده می شود که با توابع مثلثاتی مناسب تطبیق دارند .
این مطلب که این بردارها بسیار منظم هستند اساس الگوریتم FFT را شکل می دهد .
پیش از پرداختن به الگوریتم لازم است چند نماد مناسب معرفی شوند .
تمام بردارهای مبنا در فضای N – بعدی می توانند بر حسب توانهای متفاوتی از یک عدد بیان شوند .
WN ، WN = e-2πi/N به عنوان مثال به ازای N=4 داریم : ek = (W4k*0, W4k*1, W4k*2, W4k*3) e-2πik*2/4=(e-2πi/4)k*2 =W4k*2 بنابراین شکل نهایی مبنای فوریه N – نقطه ای بصورت زیر است : ek[n] = WNkn, n = 0, 1, ...
N-1 K – امین مولفه DFT بردار بافرv[n] حاصل ضرب نرده ای K – امین بردار مبنا در بردار نمونه می باشد .
V[k] = Σn=0...N-1 Wkn v[n] 3-2- خصوصیات تبدیل فوریه دیجیتال : تبدیل فوریه را میتوان بصورت هندسی نمایش داد .
فرکانسهای بالا و پایین را از هم جدا کرد وفرکانس خاصی را از سیگنال حذف کرد.
( فیلتر کردن ) مولفه های DFT اعداد مختلط هستند که دارای ضریب و فاز می باشند .
ضریب V[k] ، جذر (V[k]*V*[k]) است که شدت یک فرکانس مجزا که با K نشان داده می شود را توصیف می کند .
فاز جز داده شده نشان دهنده زاویه ای است که آن جز شروع می شود .
3-3- تبدیل فوریه سریع : پیاده سازی تبدیل دیجیتال N – نقطه ای فوریه شامل محاسبه ضرب اسکالر بافر نمونه ( محاسبه شده به صورت یک بردار N- بعدی ) با N بردار مبنای مجزا می باشد .
از آنجایی که هر ضرب اسکالر شامل N ضرب است و N عمل جمع هم باید انجام شود پیچیدگی زمانی این الگوریتم از مرتبه O(N2) می باشد .
در هر صورت به نظر میرسد با چیدن دوباره عملیات میتوان پیچیدگی زمانی را به O(N log(N)) بهینه کرد که به ازای N های بزرگ تفاوت بزرگی حاصل می شود .
الگوریتم بهینه شده DFT ، FFT نامیده می شود .
تصور کنید یک تبدیل فوریه واقعی برای یک کانال با کیفیت صدای CD انجام شود .
کیفیت CD ، 44K نمونه در هر ثانیه است و فرض بر این است که یک بافر 1K داریم که در هر ثانیه 44 بار با داده ها پر می شود.
برای تولید یک تبدیل 1000 نقطه ای فوریه ، باید 2 میلیون عمل اعشاری انجام شود.
( 1 میلیون ضرب و 1 میلیون جمع ) برای اینکه از پس بافرهای وارد شونده بر آییم حداقل به 88M عمل با ممیز شناور در هر ثانیه نیاز است .
با استفاده از FFT حدود 2*1000*log2(1000) عمل در هر بافر انجام می شود که صد مرتبه سریع تر از قبل است .
استراژی استاندارد برای سرعت دادن به یک الگوریتم تقسیم می باشد .
بایستی راهی برای دسته بندی عبارات در معادله یافت .
V[k] = Σn=0..N-1 WNkn v[n] در صورتیکه نانوثانیه های فرد را از نانوثانیه های زوج جدا کنیم خواهیم داشت : ( فرض کنید N زوج است ) V[k] = Σn even WNkn v[n] + Σn odd WNkn v[n] = Σr=0..N/2-1 WNk(2r) v[2r] + Σr=0..N/2-1 WNk(2r+1) v[2r+1] = Σr=0..N/2-1 WNk(2r) v[2r] + Σr=0..N/2-1 WNk(2r) WNk v[2r+1] = Σr=0..N/2-1 WNk(2r) v[2r] + WNk Σr=0..N/2-1 WNk(2r) v[2r+1] = (Σr=0..N/2-1 WN/2kr v[2r]) + WNk (Σr=0..N/2-1 WN/2kr v[2r+1]) همچنین داریم : WNk(2r) = e-2πi*2kr/N = e-2πi*kr/(N/2) = WN/2kr حاصلجمع فوق در واقع تبدیل N/2- نقطه ای زیر مجموعه فرد و زیر مجموعه زوج است .
در صورتیکه K بزرگتر یا مساوی N/2 باشد داریم : WN/2m+N/2 = WN/2mWN/2N/2 = WN/2m اگر N توانی از 2 باشد میتوان آن را به 2 تقسیم کرد تا زمانی که به تبدیل 2 – نقطه ای برسیم .
V[k] = W20*k v[0] + W21*k v[1], k=0,1 و V[0] = W20 v[0] + W20 v[1] = v[0] + W20 v[1] V[1] = W20 v[0] + W21 v[1] = v[0] + W21 v[1] این دو معادله مولفه های تبدیل فوریه را میتوان بصورت زیر نمایش داد که به آن نمایش پروانه ای گویند .
علاوه بر این با استفاده از تقسیم مجدد و اتخاذ استراتژی مناسب یک تبدیل 4 - نقطه ای را میتوان به دو تبدیل 2 – نقطه ای برای عوامل زوج و فرد تبدیل کرد.
عامل فرد در W4k ضرب می شود که میتوان با دو سطح پروانه ای بصورت هندسی نمایش داد .
با استفاده از عبارت WN/2n = WN2n میتوان همواره همه ضرایب را بصورت توانی از WN نمایش داد .
دیاگرام محاسبه تبدیل فوریه 4 – نقطه ای با توجه به موارد فوق فرم کلی دیاگرام پروانه ای بصورت زیر بدست می آید : که با استفاده از عبارات زیر ساده می شود .
WNs+N/2 = WNs WNN/2 = -WNs WNN/2 = e-2πi(N/2)/N = e-πi = cos(-π) + isin(-π) = -1 فرم ساده شده دیاگرام به شکل زیر خواهد بود : از این نتایج برای ساده سازی دیاگرام 4 – نقطه ای استفاده می کنیم : الگوریتم FFT بر اساس این دیاگرام شکل می گیرد .
نکته اصلی این است که هر مولفه ای از تبدیل فوریه، جداگانه محاسبه نمی شود .
در گیر شدن در محاسبات تکراری یک سری از اعداد غیر ضروری خواهد بود .
در عوض محاسبات در مراحل مختلف انجام می شود .
در هر مرحله با اعداد مختلط N و استفاده از دیاگرام پروانه ای به یک سری جدید از اعداد مختلط N می رسیم .
این اعداد یکی پس از دیگری بعنوان ورودی مرحله بعد بکارمی روند .
محاسبه تبدیل فوریه سریع 4 – نقطه ای شامل دو مرحله است .
ورودی مرحله اول 4 نمونه کلی دارد .
خروجی مرحله دوم 4 مولفه تبدیل فوریه را در بر می گیرد .
هر مرحله در بر گیرنده N/2 ضرب مختلط است .
به تعداد N/2 قرینه می شوند ( ضرب در 1- ) و N مورد هم اضافه می شوند .
هر مرحله می تواند در زمان O(N) اتفاق بیفتد .
تعداد مراحل log2N خواهد بود .
در صورتی که N توانی از 2 باشد به صورت N = 2m در نظر می گیریم .
در مجموع FFT به تعداد O(N logN) محاسبه نیاز دارد .
علاوه بر این ، محاسبات می توانند درمورد یک بافر با N عدد مختلط بکار روند .
شیوه مورد استفاده این است که این بافر با سمپل های مناسب بار گذاری شود .
برای N=4 ، سمپل ها بصورت v[0] ، v[1] ،v[2] و v[3] خواهند بود .
به طور کلی ابتدا این سمپل ها به دو گروه زوج و فرد تقسیم می شوند .
با استفاده از تقسیم برگشتی ، این گروه ها را به دو گروه تقسیم می کنیم .
برای مثال گروه (0, 2, 4, 6, 8, 10, ...
2N-2)به دو گروه (0, 4, 8, ...) و (2, 6, 10, ...) تقسیم می شود .
اگر این اعداد در نماد باینری نوشته شوند ، اولین بخش ( زوج یا فرد ) با کم رتبه ترین بیت شروع می شود و دومین بخش با دومین بیت پایین رتبه شروع می شود .
به ترتیب 8 عدد باینری بصورت زیر خواهند بود : 000, 001, 010, 011, 100, 101, 110, 111 با تقسیم بندی زوج و فرد به دست می آید : [زوج] (000, 010, 100, 110), [فرد] (001, 011, 101, 111) و اگر این گروه ها را تقسیم کنیم : ((000, 100), (010, 110)), (001, 101), (011, 111)) نتیجه به صورت زیر خواهد شد : 000, 100, 010, 110, 001, 101, 011, 111 عبارت فوق مرتب سازی اعداد به صورت معکوس است .
در زیر چگونگی عملکرد الگوریتم FFT بیان شده است .
برای محاسبه تبدیل فوریه سریع N – نقطه ای ، N را به صورت توانی از 2 در نظر می گیریم .
سمپل ها را در بافری به طول N ذخیره می کنیم .
این سمپل ها را به صورت بیت معکوس در بافر N – نقطه ای مختلط قرار می دهیم .
مرحله اول دیاگرام پروانه ای را برای هر جفت عدد مجاور در بافر به کار می بریم .
مرحله دوم دیاگرام پروانه ای را برای جفتهایی که 2 تایی جدا شده اند بکار می بریم .
استفاده از دیاگرام پروانه ای را ادامه می دهیم تا به صورت N/2 تفکیک شوند .
در این حالت بافر حاوی تبدیل فوریه مورد نظر خواهد بود .
Re (e0) = (1, 1, 1, 1)Im (e0) = (0, 0, 0, 0)Re (e1) = (1, 0, -1, 0)Im (e1) = (0, 1, 0, -1)Re (e2) = (1, -1, 1, -1)Im (e2) = (0, 0, 0, 0)Re (e3) = (1, 0, -1, 0)Im (e3) = (0, -1, 0, 1)