تسلسل ذو طول أقصى

الموسوعة الحرة

التسلسل ذو الطول الأقصى ( MLS ) هو نوع من التسلسل الثنائي شبه العشوائي .

هي عبارة عن متواليات ثنائية مُولَّدة باستخدام مسجلات إزاحة ذات تغذية راجعة خطية قصوى ، وتُسمى كذلك لأنها دورية وتُعيد إنتاج كل متوالية ثنائية (باستثناء متجه الصفر) التي يُمكن تمثيلها بواسطة مسجلات الإزاحة (أي، بالنسبة لمسجلات طولها m، فإنها تُنتج متوالية طولها 2m - 1 ). تُسمى متوالية التغذية الراجعة الخطية القصوى أحيانًا متوالية n أو متوالية m . تتميز متواليات التغذية الراجعة الخطية القصوى بسطح طيفي مُسطَّح ، باستثناء حد تيار مستمر قريب من الصفر.  

يمكن تمثيل هذه المتتاليات كمعاملات لكثيرات الحدود الأولية . [ 1 ] في حلقة كثيرات الحدود على Z/2Z .

تشمل التطبيقات العملية لتقنية قياس الطيف متعدد القنوات (MLS) قياس استجابات النبضات (مثل صدى الغرفة أو أوقات وصول الموجات من مصادر مسحوبة في المحيط [ 2 ] ). كما تُستخدم كأساس لاستخلاص متواليات شبه عشوائية في أنظمة الاتصالات الرقمية التي تستخدم أنظمة نقل الطيف المنتشر بالتسلسل المباشر وأنظمة نقل الطيف المنتشر بالقفز الترددي ، وفي التصميم الفعال لبعض تجارب التصوير بالرنين المغناطيسي الوظيفي (fMRI ) . [ 3 ]

جيل

الشكل 1: يتم تحديد القيمة التالية للمسجل a 3 في مسجل إزاحة التغذية الراجعة بطول 4 عن طريق مجموع modulo-2 لـ a 0 و a 1 .

يتم توليد إشارات MLS باستخدام مسجلات الإزاحة ذات التغذية الراجعة الخطية القصوى . يوضح الشكل 1 نظام توليد إشارات MLS باستخدام مسجل إزاحة بطول 4. ويمكن التعبير عنه باستخدام العلاقة التكرارية التالية:

{أ3[ن+1]=أ0[ن]+أ1[ن]أ2[ن+1]=أ3[ن]أ1[ن+1]=أ2[ن]أ0[ن+1]=أ1[ن]{\displaystyle {\begin{cases}a_{3}[n+1]=a_{0}[n]+a_{1}[n]\\a_{2}[n+1]=a_{3}[n]\\a_{1}[n+1]=a_{2}[n]\\a_{0}[n+1]=a_{1}[n]\\\end{cases}}}

حيث n هو مؤشر الوقت و+{\displaystyle +}يمثل هذا الجمع بتردد 2. بالنسبة لقيم البتات 0 = خطأ أو 1 = صحيح، فإن هذا يعادل عملية XOR.

بما أن سجلات MLS دورية وتدور سجلات الإزاحة عبر كل قيمة ثنائية ممكنة (باستثناء متجه الصفر)، يمكن تهيئة السجلات إلى أي حالة، باستثناء متجه الصفر.

تفسير متعدد الحدود

يمكن ربط متعددة حدود على حقل غالوا GF(2) بمسجل الإزاحة ذي التغذية الراجعة الخطية. درجتها تساوي طول مسجل الإزاحة، ومعاملاتها إما 0 أو 1، وتتوافق مع نقاط التغذية في المسجل التي تغذي بوابة XOR . على سبيل المثال، متعددة الحدود الموضحة في الشكل 1 هيx4+x+1{\displaystyle x^{4}+x+1}.

الشرط الضروري والكافي لكي يكون التسلسل الناتج عن LFSR ذو طول أقصى هو أن تكون متعددة الحدود المقابلة له بدائية .

تطبيق

تعتبر MLS غير مكلفة للتنفيذ في الأجهزة أو البرامج، ويمكن لمسجلات الإزاحة ذات التغذية الراجعة منخفضة الترتيب نسبيًا توليد تسلسلات طويلة؛ التسلسل الذي تم إنشاؤه باستخدام مسجل إزاحة بطول 20 هو 2 20 − 1 عينة (1,048,575 عينة).  

خصائص المتتاليات ذات الطول الأقصى

تتمتع MLS بالخصائص التالية، كما صاغها سولومون غولومب . [ 4 ]

عقار متوازن

ينبغي أن يكون تكرار الرقمين 0 و1 في المتتالية متقاربًا. وبشكل أدق، في متتالية ذات طول أقصى يبلغ طولها2ن-1{\displaystyle 2^{n}-1}هناك2ن-1{\displaystyle 2^{n-1}}واحد و2ن-1-1{\displaystyle 2^{n-1}-1}الأصفار. عدد الآحاد يساوي عدد الأصفار زائد واحد، لأن الحالة التي تحتوي على أصفار فقط لا يمكن أن تحدث.

تشغيل العقار

التسلسل هو سلسلة فرعية من الأرقام "1" أو "0" المتتالية ضمن نظام MLS المعني. عدد التسلسلات هو عدد هذه السلاسل الفرعية.

من بين جميع "السلاسل" (المكونة من "1" أو "0") في التسلسل  :

  • نصف المسارات طولها 1.
  • ربع الجريات طولها 2.
  • يبلغ طول ثُمن عدد الجولات 3.
  • ... إلخ. ...

خاصية الارتباط

تُعدّ دالة الارتباط الذاتي الدائري لشبكة MLS دالة دلتا كرونكر [ 5 ] [ 6 ] (مع إزاحة التيار المستمر وتأخير زمني، حسب التطبيق). بالنسبة لاتفاقية ±1، أي يتم تعيين قيمة البت 1s=+1{\displaystyle s=+1}وقيمة البت 0s=-1{\displaystyle s=-1}، حيث يتم تعيين XOR إلى معكوس الناتج:

R(ن)=1شمال∑م=1شمالs[م]s*[م+ن]شمال={1لو ن=0،-1شماللو 0<ن<شمال.{\displaystyle R(n)={\frac {1}{N}}\sum _{m=1}^{N}s[m]\,s^{*}[m+n]_{N}={\begin{cases}1&{\text{إذا كان }}n=0,\\-{\frac {1}{N}}&{\text{إذا كان }}0<n<N.\end{cases}}}

أينs*{\displaystyle s^{*}}يمثل المرافق المعقد و[م+ن]شمال{\displaystyle [m+n]_{N}}يمثل تحولاً دائرياً .

يُقارب الارتباط الذاتي الخطي لنموذج المربعات الصغرى المتعددة دالة دلتا كرونكر.

استخلاص استجابات النبض

إذا أردنا قياس استجابة نبضية لنظام خطي ثابت مع الزمن (LTI) باستخدام طريقة المربعات الصغرى متعددة المستويات (MLS)، فيمكن استخلاص هذه الاستجابة من خرج النظام المقاس y [ n ] عن طريق حساب الارتباط الدائري المتبادل بينه وبين طريقة المربعات الصغرى متعددة المستويات. وذلك لأن الارتباط الذاتي لطريقة المربعات الصغرى متعددة المستويات يساوي 1 عند التأخير الصفري، ويقترب من الصفر ( -1 / N حيث N هو طول التسلسل) عند جميع التأخيرات الأخرى؛ بعبارة أخرى، يمكن القول إن الارتباط الذاتي لطريقة المربعات الصغرى متعددة المستويات يقترب من دالة نبضية تساوي واحدًا مع ازدياد طول التسلسل.

إذا كانت استجابة النبضة لنظام ما هي h [ n ] وكان MLS هو s [ n ]، فإن

y[ن]=(ح*s)[ن].{\displaystyle y[n]=(h*s)[n].\,}

بأخذ الارتباط المتبادل بالنسبة إلى s [ n ] لكلا الجانبين،

ϕsy=ح[ن]*ϕss{\displaystyle {\phi }_{sy}=h[n]*{\phi }_{ss}\,}

وبافتراض أن φ ss عبارة عن نبضة (صالحة للتسلسلات الطويلة)

ح[ن]=ϕsy.{\displaystyle h[n]={\phi }_{sy}.\,}

يمكن استخدام أي إشارة ذات ارتباط ذاتي نبضي لهذا الغرض، لكن الإشارات ذات معامل الذروة العالي ، مثل النبضة نفسها، تُنتج استجابات نبضية بنسبة إشارة إلى ضوضاء ضعيفة . يُفترض عادةً أن إشارة MLS هي الإشارة المثالية، لأنها تتكون من قيم كاملة النطاق فقط، ومعامل ذروتها الرقمي هو الأدنى، أي 0  ديسيبل. [ 7 ] [ 8 ] مع ذلك، بعد إعادة البناء التناظري ، تُنتج الانقطاعات الحادة في الإشارة قممًا قوية بين العينات، مما يُقلل معامل الذروة بمقدار 4-8  ديسيبل أو أكثر، ويزداد مع طول الإشارة، مما يجعلها أسوأ من مسح جيبي. [ 9 ] صُممت إشارات أخرى بمعامل ذروة أدنى، لكن من غير المعروف ما إذا كان من الممكن تحسينه إلى ما يزيد عن 3  ديسيبل. [ 10 ]

العلاقة بتحويل هادامارد

أظهر كوهن وليمبل [ 11 ] العلاقة بين طريقة المربعات الصغرى المتعددة (MLS) وتحويل هادامارد . تسمح هذه العلاقة بحساب ارتباط طريقة المربعات الصغرى المتعددة (MLS) باستخدام خوارزمية سريعة مشابهة لتحويل فورييه السريع (FFT) .

انظر أيضاً

مراجع

  1. ↑ "مسجلات الإزاحة ذات التغذية الراجعة الخطية - التنفيذ، خصائص التسلسل M، جداول التغذية الراجعة"، شركة نيو ويف إنسترومنتس (NW)، تم الاطلاع عليه بتاريخ 2013.12.03.
  2. ↑ جيمبا، كاي إل.؛ فازكيز، هيريبيرتو جيه.؛ فيالكوفسكي، جوزيف؛ إيدلمان، جيفري إف.؛ دزيتش، ماثيو إيه.؛ هودجكيس، ويليام إس. (أكتوبر 2021). "مقارنة أداء بين متواليات m والمسح الخطي المُعدَّل التردد لتقدير زمن انتقال الصوت من مصدر متحرك" . مجلة الجمعية الصوتية الأمريكية . 150 (4): 2613-2623 . Bibcode : 2021ASAJ..150.2613G . doi : 10.1121/10.0006656 . PMID: 34717519. S2CID : 240355915 .  
  3. ↑ بوراكاس جي تي، بوينتون جي إم (يوليو 2002). " التصميم الفعال لتجارب التصوير بالرنين المغناطيسي الوظيفي المرتبطة بالأحداث باستخدام تسلسلات M". مجلة NeuroImage . 16 (3 الجزء 1): 801-813 . doi : 10.1006/nimg.2002.1116 . PMID 12169264. S2CID 7433120 .  
  4. ↑ غولومب، سولومون و. (1967). تسلسلات مسجل الإزاحة . هولدن-داي. ISBN 0-89412-048-4.
  5. ↑ جاكوبسن، فين؛ جول، بيتر مولر (2013-06-04). أساسيات الصوتيات الخطية العامة . جون وايلي وأولاده. ISBN 978-1118636176. التسلسل ذو الطول الأقصى هو تسلسل ثنائي يكون ارتباطه الذاتي الدائري (باستثناء خطأ التيار المستمر الصغير) دالة دلتا.
  6. ↑ ساروات، د. ف.؛ بورسلي، م. ب. (1980-05-01). "خصائص الارتباط المتبادل للتسلسلات شبه العشوائية والمتتابعات ذات الصلة". وقائع معهد مهندسي الكهرباء والإلكترونيات . 68 (5): 593-619 . doi : 10.1109/PROC.1980.11697 . ISSN 0018-9219 . S2CID 6179951 .  
  7. ↑ "دليل مبسط لتسلسل الطول الأقصى (MLS) | dspGuru.com" . dspguru.com . تم الاطلاع عليه بتاريخ 19-05-2016 . قيمتا الجذر التربيعي المتوسط ​​(RMS) والذروة تساويان X، مما يجعل عامل الذروة (الذروة/RMS) يساوي 1، وهو أدنى قيمة ممكنة.
  8. ↑ "تقنيات قياس كهروصوتية أخرى" . www.clear.rice.edu . تاريخ الاسترجاع: 19-05-2016 . معامل الذروة لتقنية MLS قريب جدًا من 1، لذا من المنطقي استخدام هذا النوع من إشارة الإدخال عندما نحتاج إلى نسبة إشارة إلى ضوضاء عالية للقياس.
  9. ↑ تشان، إيان هـ. "نبضات جيبية متغيرة التردد لقياس استجابة النبضة" (ملف PDF) . thinksrs.com . تاريخ الاسترجاع: 19 مايو 2016. يُعدّ تسلسل الطول الأقصى (MLS) مناسبًا نظريًا نظرًا لامتلاكه عامل ذروة رياضيًا قدره 0 ديسيبل، وهو أدنى عامل ذروة ممكن. مع ذلك، عمليًا، تؤدي الانتقالات الحادة وإعادة إنتاج الإشارة المحدودة بعرض النطاق الترددي إلى عامل ذروة يبلغ حوالي 8 ديسيبل.
  10. ↑ فريز، م. (1997-10-01). "إشارات متعددة النغمات ذات عامل ذروة منخفض" (ملف PDF) . معاملات IEEE في الاتصالات . 45 (10): 1338-1344 . doi : 10.1109/26.634697 . ISSN 0090-6778 . 
  11. ↑ كوهن، م.؛ ليمبل، أ. (يناير 1977). "حول تحويلات متسلسلة M السريعة". معاملات IEEE لنظرية المعلومات . 23 (1): 135-137 . doi : 10.1109/TIT.1977.1055666 .