مهندسان معمای پنجاه ساله در پردازش سیگنال را حل کردند!

همین الان الگوریتم تبدیل فوریه سریع(FFT) در گوشی همراه شما در حال اجرا است. FFT همانطور که همه می‌دانند یک الگوریتم پردازش سیگنال است که بیش از آن چه فکر کنید از آن استفاده می‌کنید. بر اساس عنوان یک مقاله، الگوریتمی است که تمام اعضا خانواده می‌توانند استفاده کنند.

نویسنده: پریسا ایلون

Alexander Stoytchev، دانشیار مهندسی الکترونیک و کامپیوتر در دانشگاه Iowa State که در مرکز نرم افزارهای واقعیت مجازی نیز مشغول به کار است، می‌گوید الگوریتم FFT و عکس آن قلب پردازش سیگنال هستند.آن‌ها الگوریتم‌هایی هستند که انقلاب دیجیتال را امکان‌پذیر کردند. آن‌ها در موسیقی در حال اجرا، تلفن در حال زنگ زدن، بالا پایین کردن صفحات اینترنت و گرفتن یک سلفی وجود دارند.

الگوریتم FFT در سال 1965 منتشر شد. چهار سال بعد، دانشمندان یک فرم کاربردی‌تر و عمومی‌تر از آن به نام chirp z-transform (CZT) را معرفی کردند. اما یک عمومی‌سازی از عکس تبدیل فوریه برای پنجاه سال مجهول مانده بود.

 تا وقتی که Stoytchev و Vladimir Sukhoy دانشجوی دکترا با همکاری یکدیگر الگوریتم مورد نظر را یافتند و آن را ICZT یا chirp z-transform معکوس نامیدند.

همانند سایر الگوریتم‌ها، این الگوریتم هم با یک رویه پله به پله مساله را حل می‌کند.

toytchev :

در این جا الگوریتم، خروجی  یک CZT را مرحله به مرحله به ورودی اولیه تبدیل می‌کند. این دو الگویتم تا حدی شبیه یک سری منشور هستند- که اولی موج نور را به طیف رنگی می‌شکند و دومی عکس آن را انجام می‌دهد یعنی تمام طیف را به نور سفید تبدیل می‌کند.

Stoytchev و Vladimir Sukhoy الگوریتم جدید خود را در مقاله توضیح دادند و مقاله آن‌ها نشان می‌دهد که الگوریتم با پیچیدگی محاسباتی یا سرعت الگوریتم مقابل خود جور می‌شود، به این معنی که می‌تواند با فرکانس بالا رونده یا پایین رونده‌ی نمایی استفاده شود. آن‌ها الگوریتم خود را برای دقت عددی نیز آزمایش کردند.

Stoytchev گفت او در مورد ایده ایجاد فرمول الگوریتم مجهول مردد بود در حالی که همواره در جستجوی آنالوگ‌هایی بود تا به دانشجویان خود کمک کند بهتر تبدیل فوریه را درک کنند. او در مورد پردازش سیگنال بسیار مطالعه کرد و نتوانست اطلاعاتی در مورد معکوس chirp z-transform بیابد.

کنجکاو شدم. آیا به این دلیل است که کسی نتوانسته آن را توضیح دهد یا وجود ندارد؟ او نتیجه گرفت اصلا وجود ندارد.

و به همین دلیل تصمیم گرفت تا یک الگوریتم تبدیل فوریه سریع معکوس را بیابد.

Stoytchev گفت در مقایسه با خود الگوریتم که رو به جلو است، الگوریتم معکوس مساله پیچیده‌تری است و بنابراین ما دقت بیشتر و کامپیوترهای قوی‌تری احتیاج داشتیم تا بتوانیم آن را پیدا کنیم. او همچنین گفت کلید معما، مشاهده الگوریتم در یک قالب ریاضیاتی ماتریسی بود.

حتی این زمان، بررسی‌های کامپیوتری بسیاری در حال انجام بود” تا نشان دهد همه چیز درست کار می‌کند- باید خودمان را متقاعد می‌کردیم که درست عمل می‌کند.”

James Oliver  ، مدیر مرکز خلاقیت دانشگاه و مدیر سابق مرکز نرم افزارهای واقعیت مجازی می‌گوید” ادامه دادن به بررسی شجاعت می‌طلبید. Stoytchev و Sukhoy در مقاله خود از Oliver برای محیا کردن محیط پژوهشی که بتوانند در آن طی سه سال کار خود را ادامه دهند قدردانی کردند.

Oliver گفت:

الکس همیشه مرا تحت تاثیر علاقه و تعهد خود برای انجام یک پروژه پژوهشی چالش برانگیز قرار داده است. همیشه در کار پژوهشی ریسک وجود دارد و شجاعت لازم است تا انسان سال ها کار بی وقفه خود را صرف یک مساله بنیادین بکند. الکس محقق بسیار با استعداد و شجاعی است.

منبع