تحويل الجيب المنفصل

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 10 صور
الموسوعة الحرة

في الرياضيات ، يُعدّ تحويل الجيب المنفصل (DST) تحويلاً مرتبطاً بتحويل فورييه، وهو مشابه لتحويل فورييه المنفصل (DFT)، ولكنه يستخدم مصفوفة حقيقية بحتة . وهو يُكافئ الأجزاء التخيلية لتحويل فورييه المنفصل بطول يُقارب ضعف طول تحويل الجيب المنفصل، ويعمل على بيانات حقيقية ذات تناظر فردي (لأن تحويل فورييه لدالة حقيقية وفردية هو تخيلي وفردي)، حيث يتم في بعض المتغيرات إزاحة بيانات الإدخال و/أو الإخراج بمقدار نصف عينة.

يرتبط تحويل ديريشليه المنفصل (DST) بتحويل جيب التمام المنفصل (DCT)، وهو مكافئ لتحويل فورييه المنفصل (DFT) للدوال الحقيقية والزوجية . راجع مقالة DCT لمناقشة عامة حول كيفية ارتباط الشروط الحدية بأنواع DCT وDST المختلفة. عمومًا، يُشتق DST من DCT باستبدال شرط نيومان عند x = 0 بشرط ديريشليه . [ 1 ] وصف كل من DCT وDST ناصر أحمد ، وت. ناتاراجان، وك. ر. راو في عام 1974. [ 2 ] [ 3 ] وصف أنيل ك. جاين النوع الأول من DST (DST-I) لاحقًا في عام 1976، ثم وصف هـ. ب. كيكرا وج. ك. سولانكا النوع الثاني من DST (DST-II) في عام 1978. [ 4 ]

من منظور معالجة الإشارات الجبرية ، ينشأ كل من تحويل جيب التمام المنفصل (DST) وتحويل جيب التمام المنفصل (DCT) كتحويلات طيفية مرتبطة بالمجموعة ثنائية السطوح ، ويختلفان فقط في اختيار الشروط الحدية: يتوافق تحويل جيب التمام المنفصل مع الحدود المتناظرة (الزوجية، نيومان)، بينما يتوافق تحويل جيب التمام المنفصل مع الحدود غير المتناظرة (الفردية، ديريشليه). يشكلان معًا عائلة كاملة من التحويلات الطيفية للمجموعة ثنائية السطوح، تمامًا كما أن تحويل فورييه المنفصل (DFT) هو التحويل الطيفي للمجموعة الدورية ذات الشروط الحدية الدورية. [ 5 ]

التطبيقات

تُستخدم تحويلات DST على نطاق واسع في حل المعادلات التفاضلية الجزئية بواسطة الطرق الطيفية ، حيث تتوافق المتغيرات المختلفة لتحويل DST مع شروط حدودية فردية/زوجية مختلفة قليلاً عند طرفي المصفوفة.

نظرة عامة غير رسمية

توضيح للامتدادات الزوجية/الفردية الضمنية لبيانات إدخال التوقيت الصيفي، لـ N = 9 نقاط بيانات (نقاط حمراء)، لأكثر أربعة أنواع شيوعًا من التوقيت الصيفي (الأنواع من الأول إلى الرابع).

كأي تحويل مرتبط بتحويل فورييه، تُعبّر تحويلات الجيب المنفصلة (DSTs) عن دالة أو إشارة بدلالة مجموع موجات جيبية بترددات وسعات مختلفة . وكما هو الحال في تحويل فورييه المنفصل (DFT)، يُطبّق تحويل الجيب المنفصل على دالة عند عدد محدود من نقاط البيانات المنفصلة. ويكمن الفرق الواضح بين تحويل الجيب المنفصل وتحويل فورييه المنفصل في أن الأول يستخدم دوال الجيب فقط، بينما يستخدم الثاني دوال الجيب وجيب التمام (في صورة دوال أسية مركبة ). مع ذلك، فإن هذا الاختلاف الظاهر ليس إلا نتيجة لاختلاف أعمق: إذ يتطلب تحويل الجيب المنفصل شروطًا حدودية مختلفة عن تلك التي يتطلبها تحويل فورييه المنفصل أو غيره من التحويلات ذات الصلة.

يمكن اعتبار التحويلات المتعلقة بفورييه والتي تعمل على دالة ضمن نطاق محدود ، مثل تحويل فورييه المنفصل (DFT) أو تحويل فورييه المنفصل المتسلسل (DST) أو متسلسلة فورييه ، بمثابة تعريف ضمني لامتداد تلك الدالة خارج النطاق. أي، بمجرد كتابة دالةو(x){\displaystyle f(x)}باعتبارها مجموعًا من الدوال الجيبية، يمكنك حساب هذا المجموع عند أيx{\displaystyle x}، حتى بالنسبةx{\displaystyle x}حيث الأصلو(x){\displaystyle f(x)}لم يتم تحديد ذلك. يشير تحويل فورييه المنفصل (DFT)، مثل متسلسلة فورييه، إلى امتداد دوري للدالة الأصلية. بينما يشير تحويل فورييه المنفصل الموجه (DST)، مثل تحويل الجيب ، إلى امتداد فردي للدالة الأصلية.

مع ذلك، ولأن تحويلات الجيب المنفصلة تعمل على متتابعات منفصلة محدودة ، تظهر مشكلتان لا تنطبقان على تحويل الجيب المستمر. أولًا، يجب تحديد ما إذا كانت الدالة زوجية أم فردية عند كل من الحدين الأيسر والأيمن للمجال (أي الحدين الأدنى- n والحدين الأقصى- n في التعريفات أدناه، على التوالي). ثانيًا، يجب تحديد النقطة التي تكون عندها الدالة زوجية أو فردية. على وجه الخصوص، لنفترض متتابعة ( a , b , c ) من ثلاث نقاط بيانات متساوية التباعد ، ولنفترض أننا حددنا حدًا أيسر فرديًا . هناك احتمالان منطقيان: إما أن تكون البيانات فردية حول النقطة السابقة لـ a ، وفي هذه الحالة يكون الامتداد الفردي هو ( -c , -b , -a , 0, a , b , c )، أو أن تكون البيانات فردية حول النقطة الواقعة في منتصف المسافة بين a والنقطة السابقة، وفي هذه الحالة يكون الامتداد الفردي هو ( -c , -b , -a , a , b , c ) .

تؤدي هذه الخيارات إلى جميع التباينات القياسية لتحويلات جيب التمام المنفصلة (DSTs) وكذلك تحويلات جيب التمام المنفصلة (DCTs). يمكن أن يكون كل حد إما زوجيًا أو فرديًا (خياران لكل حد) ويمكن أن يكون متناظرًا حول نقطة بيانات أو النقطة الواقعة في منتصف المسافة بين نقطتي بيانات (خياران لكل حد)، ليصبح المجموع2×2×2×2=16{\displaystyle 2\times 2\times 2\times 2=16}الاحتمالات. نصف هذه الاحتمالات، تلك التي يكون فيها الحد الأيسر فرديًا، تتوافق مع الأنواع الثمانية من تحويلات DST؛ أما النصف الآخر فهو الأنواع الثمانية من تحويلات DCT.

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

تعريف

بصورة رسمية، يُعدّ تحويل الجيب المنفصل دالة خطية قابلة للعكس F : R → N ( حيث R هي مجموعة الأعداد الحقيقية )، أو مكافئًا لها مصفوفة مربعة N × N. توجد عدة صيغ لتحويل الجيب المنفصل بتعريفات معدلة قليلاً. يتم تحويل الأعداد الحقيقية N، x₀ ، ... ، xₙ₋₁ ، إلى الأعداد الحقيقية N ، X₀ ، ...، Xₙ₋₁، وفقًا لإحدى الصيغ التالية: 

DST-I

تحويل الجيب المنفصل ( https://www.desmos.com/calculator/k5jlr0ykzw ).
Xك=∑ن=0شمال-1xنالخطيئة⁡[πشمال+1(ن+1)(ك+1)]ك=0،...،شمال-1Xك-1=∑ن=1شمالxن-1الخطيئة⁡[πنكشمال+1]ك=1،...،شمال{\displaystyle {\begin{aligned}X_{k}&=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N+1}}(n+1)(k+1)\right]&k&=0,\dots ,N-1\\X_{k-1}&=\sum _{n=1}^{N}x_{n-1}\sin \left[{\frac {\pi nk}{N+1}}\right]&k&=1,\dots ,N\end{aligned}}}

مصفوفة DST-I متعامدة (حتى عامل قياس).

يُكافئ تحويل فورييه المنفصل من النوع الأول (DST-I) تمامًا تحويل فورييه المنفصل (DFT) لمتتالية حقيقية ذات تناظر فردي حول النقطة الصفرية والنقطة الوسطى، مُقسَّمة على 1/2. على سبيل المثال، يُكافئ تحويل فورييه المنفصل من النوع الأول (DST-I) لـ N = 3 أعداد حقيقية ( a , b , c ) تمامًا تحويل فورييه المنفصل لثمانية أعداد حقيقية (0 , a , b , c , 0, −c , −b , −a ) (تناظر فردي)، مُقسَّمة على 1/2 . (في المقابل، تتضمن أنواع تحويل فورييه المنفصل من النوع الثاني إلى الرابع (DST - II-IV) إزاحة نصف عينة في تحويل فورييه المنفصل المكافئ). هذا هو سبب وجود N + 1 في مقام دالة الجيب: يحتوي تحويل فورييه المنفصل المكافئ على 2( N + 1) نقطة، وتردده الجيبي يساوي 2π/2( N + 1)، لذا فإن تردد تحويل فورييه المنفصل من النوع الأول (DST-I) يساوي π/( N + 1).  

وبالتالي، فإن DST-I يتوافق مع الشروط الحدية: x n فردي حول n  =  −1 وفردي حول n = N ؛ وبالمثل بالنسبة لـ X k .

DST-II

Xك=∑ن=0شمال-1xنالخطيئة⁡[πشمال(ن+12)(ك+1)]ك=0،...،شمال-1{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)(k+1)\right]\quad \quad k=0,\dots ,N-1}

يقوم بعض المؤلفين بضرب الحد X N − 1 في 1/ √ 2 (انظر أدناه للتغيير المقابل في DST-III). هذا يجعل مصفوفة DST-II متعامدة (حتى عامل قياس)، ولكنه يكسر التوافق المباشر مع تحويل فورييه المنفصل الحقيقي الفردي للإدخال المُزاح نصف إزاحة.

يشير DST-II إلى الشروط الحدية التالية: x n فردي حول n  =  −1/2 وفردي حول n  = N − 1/2؛ X k فردي حول k = −1 وزوجي حول k = N − 1.         

DST-III

Xك=(-1)ك2xشمال-1+∑ن=0شمال-2xنالخطيئة⁡[πشمال(ن+1)(ك+12)]ك=0،...،شمال-1{\displaystyle X_{k}={\frac {(-1)^{k}}{2}}x_{N-1}+\sum _{n=0}^{N-2}x_{n}\sin \left[{\frac {\pi }{N}}(n+1)\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\dots ,N-1}

يقوم بعض المؤلفين بضرب الحد x N − 1 في √ 2 (انظر أعلاه للتغيير المقابل في DST-II). هذا يجعل مصفوفة DST-III متعامدة (حتى عامل قياس)، ولكنه يكسر التوافق المباشر مع تحويل فورييه المنفصل الحقيقي الفردي للمخرجات نصف المزاحة.

يشير DST-III إلى الشروط الحدية التالية: x n فردي حول n  =  −1 وزوجي حول n  = N − 1؛ X k فردي حول k = −1/2 وفردي حول k = N − 1/2.         

DST-IV

Xك=∑ن=0شمال-1xنالخطيئة⁡[πشمال(ن+12)(ك+12)]ك=0،...،شمال-1{\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\sin \left[{\frac {\pi }{N}}\left(n+{\frac {1}{2}}\right)\left(k+{\frac {1}{2}}\right)\right]\quad \quad k=0,\dots ,N-1}

مصفوفة DST-IV متعامدة (حتى عامل قياس).

يشير DST-IV إلى الشروط الحدية التالية: x n فردي حول n  =  −1/2 وزوجي حول n  = N − 1/2؛ وبالمثل بالنسبة لـ X k .   

التوقيت الصيفي الخامس - الثامن

تُكافئ أنواع تحويلات الجيب المنفصلة من النوع الأول إلى الرابع تحويلات فورييه المنفصلة الحقيقية ذات الرتبة الزوجية. من حيث المبدأ، توجد أربعة أنواع إضافية من تحويلات الجيب المنفصلة (مارتوتشي، 1994)، تُقابل تحويلات فورييه المنفصلة الحقيقية ذات الرتبة الفردية منطقيًا، والتي تحتوي على عوامل N + 1/2 في مقامات وسائط الجيب. مع ذلك، يبدو أن هذه الأنواع نادرة الاستخدام عمليًا.

التحويلات العكسية

معكوس DST-I هو DST-I مضروبًا في 2/( N  +  1). معكوس DST-IV هو DST-IV مضروبًا في 2/ N . معكوس DST-II هو DST-III مضروبًا في 2/ N (والعكس صحيح).

أما بالنسبة لتحويل فورييه المنفصل (DFT) ، فإن عامل التطبيع الذي يسبق تعريفات هذا التحويل هو مجرد اصطلاح ويختلف بين المعالجات. على سبيل المثال، يقوم بعض المؤلفين بضرب التحويلات بـ2/شمال{\textstyle {\sqrt {2/N}}}بحيث لا يتطلب المعكوس أي عامل ضرب إضافي.

حساب

على الرغم من أن التطبيق المباشر لهذه الصيغ يتطلب O( N² ) عملية حسابية، فإنه من الممكن حساب الشيء نفسه بتعقيد O( N log N ) فقط عن طريق تحليل الحساب بطريقة مشابهة لتحويل فورييه السريع (FFT). (يمكن أيضًا حساب تحويلات الدرجات المنفصلة (DSTs) باستخدام تحويلات فورييه السريعة مع O( N ) من خطوات المعالجة المسبقة واللاحقة).

يمكن حساب تحويل جيب التمام المنفصل من النوع الثالث (DST-III) أو الرابع (DST-IV) من تحويل جيب التمام المنفصل من النوع الثالث (DCT-III) أو الرابع (DCT-IV) (انظر تحويل جيب التمام المنفصل )، وذلك بعكس ترتيب المدخلات وقلب إشارة كل مخرج آخر، والعكس صحيح بالنسبة لتحويل جيب التمام المنفصل من النوع الثاني (DST-II) من تحويل جيب التمام المنفصل من النوع الثاني (DCT-II). وبالتالي، تتطلب الأنواع من الثاني إلى الرابع من تحويل جيب التمام المنفصل نفس عدد العمليات الحسابية (الجمع والضرب) التي تتطلبها أنواع تحويل جيب التمام المنفصل المقابلة.

التعميمات

توجد عائلة من التحويلات تتكون من دوال الجيب ودوال الجيب الزائدي ؛ وتستند هذه التحويلات إلى الاهتزاز الطبيعي للصفائح المربعة الرقيقة ذات الشروط الحدية المختلفة . [ 6 ]

مراجع

  1. ↑ بريتاناك، فلاديمير؛ يب، باتريك سي؛ راو، كيه آر (2010). تحويلات الجيب وجيب التمام المنفصلة: خصائص عامة، خوارزميات سريعة، وتقريبات عددية صحيحة . إلسيفير . ص 35-36 . ISBN  9780080464640.
  2. ↑ أحمد، ناصر ؛ ناتاراجان، ت.؛ راو، ك. ر. (يناير 1974)، "تحويل جيب التمام المنفصل" (ملف PDF) ، معاملات IEEE في الحوسبة ، C-23 (1): 90-93 ، doi : 10.1109/TC.1974.223784 ، S2CID 149806273 
  3. ↑ أحمد، ناصر (يناير 1991). "كيف توصلتُ إلى تحويل جيب التمام المنفصل" . معالجة الإشارات الرقمية . 1 (1): 4-5 . Bibcode : 1991DSP.....1....4A . doi : 10.1016/1051-2004(91)90086-Z .
  4. ↑ دهاميجيا، سواتي؛ جاين، بريانكا (سبتمبر 2011). "تحليل مقارن لتحويل الجيب المنفصل كطريقة مناسبة لتقدير الضوضاء" . المجلة الدولية لعلوم الحاسوب . 8 (5): 162-164 . تم الاطلاع عليه بتاريخ 4 نوفمبر 2019 - عبر ResearchGate.
  5. ↑ بوشيل، ماركوس؛ مورا، خوسيه إم إف (2008). "نظرية معالجة الإشارات الجبرية: الفضاء أحادي البعد". معاملات IEEE في معالجة الإشارات . 56 (8): 3586-3599 . doi : 10.1109/TSP.2008.925259 .
  6. ↑ عابدي، م.؛ صن، ب.؛ تشنغ، ز. (يوليو 2019). "عائلة من التحويلات الجيبية-الزائدية ذات تطبيقات محتملة في الاستشعار المضغوط". معاملات IEEE في معالجة الصور . 28 (7): 3571-3583 . Bibcode : 2019ITIP...28.3571A . doi : 10.1109/TIP.2019.2912355 . PMID: 31071031. S2CID : 174820107 .  

فهرس

  • SA Martucci, "Symmetric convolution and the discrete sine and cosine transforms," ​​IEEE Trans. Signal Process. SP-42 , 1038–1051 (1994).
  • ماتيو فريجو وستيفن ج. جونسون : FFTW ، الصفحة الرئيسية لـ FFTW . مكتبة C مجانية ( مرخصة بموجب رخصة GPL ) لحساب تحويلات DST السريعة (من النوع الأول إلى الرابع) في بُعد واحد أو أكثر، وبحجم عشوائي. انظر أيضًا: م. فريجو وستيفن ج. جونسون، " تصميم وتنفيذ FFTW3 "، وقائع IEEE 93 (2)، 216-231 (2005).
  • تاكويا أورا: حزمة FFT للأغراض العامة، حزمة FFT أحادية البعد / ثنائية البعد . مكتبات C و FORTRAN مجانية لحساب تحويلات DST السريعة في بُعد واحد أو بُعدين أو ثلاثة أبعاد، بأحجام من مضاعفات 2.
  • بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007)، "القسم 12.4.1. تحويل الجيب" ، وصفات عددية: فن الحوسبة العلمية (  الطبعة الثالثة)، نيويورك: مطبعة جامعة كامبريدج، رقم ISBN 978-0-521-88068-8تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 11 أغسطس 2011 ، وتمت معاينته بتاريخ 13 أغسطس 2011..
  • R. Chivukula and Y. Reznik, “ Fast Computing of Discrete Cosine and Sine Transforms of Types VI and VII ,” Proc. SPIE Vol. 8135, 2011.