‏۳‑۵

به وضوح در رابطه بالا مشخص است که با افزایش وزن در چندجمله ای (که در واقع همان تعداد جملات چند جمله ای است.) تعداد بیت های مورد نیاز برای اجرای الگوریتم نیز افزایش می یابد. به همین دلیل ما فقط به جستجو برای پیدا کردن مضرب های تکین[۲۰] از چند جمله ای فیدبک می پردازیم. الگوریتم بازیابی چند جمله ای فیدبک ، عبارت است از اینکه برای همه‌ی چند جمله‌ای‌های با وزن و حداکثر از درجه تعیین کنیم که آیا مضربی از چندجمله ای فیدبک می باشند یا خیر. (مقادیر معمول برای وزن ۳ ، ۴ و ۵ می باشد.) این الگوریتم در جدول ۳-۱ شرح داده شده است.

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

جدول ‏۳‑۱ الگوریتم شناسایی چندجمله‌ای فیدبک اسکرمبلرهای سنکرون [۶]

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

یک چندجمله ای با درجه توسط این الگوریتم زمانی شناسایی می‌شود که بعد از انجام آزمایش برای ، شود.
زمانی این الگوریتم موفقیت آمیز خواهد بود که مقدار احتمال هشدار کاذب بسیار کم در نظر گرفته شود به عنوان مثال . برای مقادیر بزرگتر برخی از چندجمله‌ای‌های یافته شده مضربی از چند جمله ای نبودند. پس ما برای افزایش میزان موفقیت آمیز بودن به جای محاسبه بزرگترین مقسوم علیه مشترک بین اولین دو چندجمله ای شناسایی شده، به محاسبه ی بزرگترین مقسوم علیه مشترک بین اولین سه چندجمله ای شناسایی شده می‌پردازیم. اگرچه شبیه سازی ها نشان داده است که این اصلاحیه در الگوریتم باعث افزایش زمان اجرای آن شده است. بنابراین کارآمدترین مقدار برای موفقیت آمیز بودن الگوریتم می باشد که در درصد موارد موفقیت آمیز است. مقادیر بزرگتری از نتایج بهتری را فراهم نمی کند و زمان اجرای برنامه را نیز افزایش می‌دهد.
اگر یک چندجمله ای بنیادین انتخاب شده تصادفی باشد، حداقل تعداد بیت هایی از دنباله خروجی که برای بازیابی مورد نیاز است برابر است با:

‏۳‑۶

و تعداد عملیات انجام شده توسط الگوریتم برابر است با:

‏۳‑۷

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

بنابراین حمله[۲۱] ما برای یافتن چند جمله ای فیدبک به بیت های خروجی کمتر نیاز خواهد داشت و در مقایسه با شمارش همه‌ی چند جمله ای ها با درجه کمتر از کارآمدتر خواهد بود مخصوصاً اگر چندجمله ای فیدبک تکین[۲۲] نباشد. جدول ۳-۲ و ۳-۳ زمان موردنیاز برای اجرای برنامه به منظور بازیابی چند جمله‌ای‌هایی متفاوت از اسکرمبلرهای سنکرون را ارائه می‌دهد. می‌توان این جدول‌ها را با جدول‌های آخر همین فصل که مربوط به شبیه‌سازی‌های الگوریتم کلوزیو توسط بنده می‌باشد مقایسه نمود.
قابل ذکر است که این الگوریتم برای حالتی که چندجمله‌ای فیدبک اسکرمبلر یک سه‌جمله‌ای باشد بسیار کاربردی است که در اغلب سیستم های مخابراتی عملی چند‌جمله‌ای‌ها به این شکل می باشند به عنوان مثال در SONET/SDH اسکرمبلر سنکرون فریم چندجمله‌ای فیدبک آن به صورت می‌باشد.
جدول ‏۳‑۲ عملکرد الگوریتم کلوزیو با بایاس [۶]

چندجمله‌ای فیدبک

چندجمله‌ای شناسایی شده

زمان

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...