FFT: الخوارزمية البالغة من العمر 60 عامًا الكامنة وراء تكنولوجيا اليوم

لن يكون المسح المقطعي ، وتدفق مقاطع الفيديو ، وإرسال الصور عبر الإنترنت ممكنًا بدون تحويل فورييه السريع. تُعرف خوارزمية الكمبيوتر التي تُعرف باسم FFT ، والتي صممها الباحثون في جامعة برينستون و IBM في كل جهاز إلكتروني تقريبًا ، وفقًا لدخول في ويكي تاريخ الهندسة والتكنولوجيا.

أظهره Fellows John Tukey و James W. Cooley للمرة الأولى في عام 1964 من قبل IEEE John Tukey و James W. Cooley ، وهي سلسلة من القيم مع مرور الوقت – وتحولها إلى ترددات. كان FFT أسرع 100 مرة من تحويل فورييه المنفصل الحالي. يتطلب DFT أيضًا ذاكرة أكثر من FFT لأنه يحفظ النتائج الوسيطة أثناء المعالجة.

أصبحت FFT أداة مهمة لمعالجة الإشارات وتحليلها في العديد من المجالات بما في ذلك معالجة الصوت ، والاتصالات ، والبث الرقمي ، وتحليل الصور. يساعد في تصفية الإشارات وضغطها والقضاء عليها من الإشارات وتعديلها.

يحتوي رمز الكمبيوتر في كل مكان البالغ من العمر 60 عامًا أيضًا على تطبيقات في التقنيات المتطورة اليوم مثل الذكاء الاصطناعي والحوسبة الكمومية والسيارات ذاتية القيادة وأنظمة الاتصالات 5G.

تم الاحتفال بـ FFT مع معلم IEEE خلال حفل أقيم في مايو في جامعة برينستون.

وقال رئيس IEEE 2024 توم كوغلين في الحفل “خوارزمية Cooley-Tukey تسارعت بشكل كبير إلى حساب DFTS”. “تتطلب الأساليب السابقة المزيد من الحسابات بشكل ملحوظ ، مما يجعل FFT بمثابة اختراق ثوري. من خلال الاستفادة من الخصائص والدوريات الجبرية ، خفضت FFT عدد العمليات ، مما يجعلها بشكل خاص وعمليًا للمهام اليومية ، واستبدال الأساليب التناظرية الأقل كفاءة.”

أداة رياضية جديدة

في عام 1963 ، شارك توكي ، أستاذ الرياضيات والإحصاءات في برينستون ، في اجتماع للجنة الاستشارية للعلوم للرئيس الأمريكي جون ف. كينيدي لمناقشة طرق اكتشاف الاختبارات النووية تحت الأرض ، وفقًا لدخول ETHW.

كان ريتشارد جاروين ، وهو عالم ومهندس في IBM ، الذي كان يحضر هذا الاجتماع ، دورًا رئيسيًا في تصميم أول قنبلة هيدروجين. توفي في مايو. اقرأ عن حياته الرائعة في هذا الشهر في Memoriam.

أخبر Tukey Garwin أنه كان يعمل على تسريع حساب طريقة موجودة – تحويل فورييه – قد يساعد في التفكير في الكشف. قام خوارزميةه بتحويل إشارة من مجالها الأصلي ، مثل الوقت أو الفضاء ، إلى مجال التردد.

أدركت Garwin إمكاناته وطلب من IBM اختيار محلل رياضي للتعاون مع Tukey. كان هذا الشخص هو كولي ، وهو موظف أبحاث يعمل على مشاريع التحليل العددي والحساب.

وقال جاروين إنه إذا كان من الممكن إجراء تحويل فورييه بشكل أسرع ، فيمكن زرع مقاييس الزلازل في الأرض في البلدان المحيطة بالاتحاد السوفيتي للكشف عن الانفجارات النووية من اختبارات القنابل الذرية ، لأن السوفييت لن يسمحوا باختبارات في الموقع ، وفقًا لتاريخ كولي الشفوي في WIKINARENGERING و TECHNOALSERANT. مقياس زلازل يقيس الاهتزازات الأرضية ، والتي يتم تحويلها إلى إشارات كهربائية وتسجيلها كـ Seismograms.

وقال كولي في تاريخه عن طريق الفم: “لتصميم أجهزة استشعار للاختبارات النووية تحت الأرض ،” يجب عليك معالجة جميع الإشارات الزلزالية ، ويمكن إجراء جزء كبير من المعالجة من خلال تحويلات فورييه “. لكن “قوة الحوسبة في ذلك الوقت لم تكن كافية لمعالجة جميع الإشارات التي تحتاجها للقيام بذلك.”

قال هارولد س. ستون زميله في IEEE في حدث Milestone ، إن FFT يمكن أن يحسب تردد المستشعر الزلزالي وإنتاج صور. وهو باحث في معالجة الصور وزميله الفخري في مختبرات NEC America ، في برينستون ، وباحث سابق في IBM.

قاد Tukey و Cooley الفريق الذي كتب رمز الكمبيوتر الذي أظهر قوة FFT.

وقال ستون: “أظهرت مظاهرة خوارزمية Coley-Tukey أنها أسرع 100 مرة”. “لقد كان بسرعة كبيرة بحيث يمكنه مواكبة البيانات الزلزالية.”

زرعت أجهزة الاستشعار التي تستخدم الخوارزمية ، واكتشفوا الانفجارات النووية داخل دائرة نصف قطرها 15 كيلومترًا من حيث تم تفجيرها ، وفقًا لإدخال ETHW.

“من خلال الاستفادة من الخصائص الجبرية والدوريات ، قلل FFT من عدد العمليات ، مما يجعلها مجدية بشكل خاص وعمليًا للمهام اليومية ، واستبدال الأساليب التناظرية الأقل كفاءة.” -2024 رئيس IEEE توم كوغلين

في عام 1965 ، نشرت كولي وتوكي “خوارزمية لحساب الماكينة لسلسلة فورييه المعقدة” ، واصفا عملية FFT. حفزت الورقة المنوية على تطوير تقنيات معالجة الإشارات الرقمية.

من أجل عمله ، حصل Tukey على ميدالية علمية وطنية أمريكية في عام 1973. كما حصل على ميدالية شرف IEEE لعام 1982 لـ “مساهمات التحليل الطيفي للعمليات العشوائية وخوارزمية تحويل فورييه السريعة”.

كان Cooley ، الذي حصل على ميدالية معالجة الإشارات IEEE Kilby لعام 2002 لريادة FFT ، شخصية رائدة في مجال معالجة الإشارات الرقمية. من خلال مشاركته في لجنة معالجة الإشارات الرقمية IEEE (المعروفة اليوم باسم جمعية معالجة الإشارات IEEE) ، ساعد في إنشاء مصطلحات واقتراح اتجاهات البحث.

على الرغم من أنه ليس أحد المخترعين ، إلا أن Garwin يُنسب إلى إدراك أن الخوارزمية لديها تطبيقات أوسع ، خاصة في المجالات العلمية والهندسية.

وقال ستون: “في لغة اليوم ، ساعد Garwin FFT” Go Viral “من خلال جمع Cooley و Tukey”.

وأضاف فرانك أنسكومب ، ابن أخ توكي ، “سعى جاروين وتوكي إلى الحصول على معلومات أفضل لإثارة الحروب ومنع الحروب”. “لقد تقدمت Cooley-Tukey FFT بشكل سريع هذا السبب من خلال إعطاء حل عملي وتبسيط للبيانات المتموجة. بفضل FFT ، بدأ عبور روبيكون التكنولوجي: الآلات التناظرية إلى الرقمية.”

روح التعاون بين الأوساط الأكاديمية والصناعة

مثل العديد من الابتكارات ، خرجت FFT من التعاون بين الصناعة والأوساط الأكاديمية ، ويجب الاعتراف بها ، حسبما قال زميل IEEE أندريا جولدسميث في الحفل. وأوضحت أنها تعمل بانتظام مع FFT في مشاريعها البحثية. في وقت الحدث ، كانت عميد برينستون للعلوم والعلوم التطبيقية. بدأت هذا الشهر منصبه الجديد كرئيس لجامعة ستوني بروك ، في نيويورك.

وقالت: “إن أخذ الأفكار التي لدينا من الأبحاث الأساسية في مختبرات الجامعة الخاصة بنا ، والتحدث إلى الأشخاص في الصناعة ، وفهم كيف يمكن لمشاكل البحث التي نعمل عليها أن تستفيد من الصناعة إما غدًا أو في غضون خمس سنوات أو 20 عامًا من الآن ، أمر مهم للغاية”. “يفكر بعض الناس في الهندسة على أنها مملة وجافة وشيء يفعله المهووسين فقط ، ولكن هناك مثل هذا الجمال والإبداع في الكثير من الابتكارات التي طورناها ، وأعتقد أن FFT مثال مثالي على ذلك.”

ينضم FFT إلى أكثر من 270 معالم أخرى IEEE. إنهم أكثر من مجرد علامة للإنجاز ، كما قال عضو في IEEE Life Bala S. Prasanna ، مدير منطقة IEEE 1.

وقال براسانا: “إنهم شهادة على الإبداع البشري والمثابرة وروح التعاون”. “كانت هذه المعالم أكثر من مجرد اختراقات ؛ لقد أصبحت محفزات للابتكار ، مما يتيح التقدم بطرق فكرت مرة واحدة. كل واحد يضمن الحفاظ على القصة وراء هذه الابتكارات ، ليس فقط كإلهام للأجيال القادمة.”

أقيم حفل آخر في 11 يونيو في مركز IBM Watson للأبحاث.

تعرض لويحات Milestone التي تدرك FFT في بهو كلية برينستون للهندسة والعلوم التطبيقية وفي الردهة الرئيسية عند مدخل مركز أبحاث IBM.

قرأوا:

“في عام 1964 ، تم توضيح برنامج الكمبيوتر الذي يقوم بتنفيذ خوارزمية تحليل فورييه عالية الكفاءة في IBM Research. تم تطويرها بشكل مشترك من قبل جامعة برينستون ومتعاونين مع IBM ، وهي تقنية Cooley-Tukey المحسوبة فورييه المنفصلة التي تم تحويلها إلى عدادات ، وتسريع التصرفات ، أو التداخلات المتدنية ، أو التداخلات المتصاعدة ، أو التداخلات المتنوعة ، أو التداخلات المتدنية ، أو التداخلات المتشددة. البث “.

يديره برنامج IEEE للتاريخ وبدعم من المانحين ، يعترف برنامج Milestone بالتطورات التقنية المتميزة في جميع أنحاء العالم. قام قسم IEEE Princeton Central Jersey برعاية الترشيح.