و در حالت خاص با بهره گرفتن از رابطه ۲‑۱۲ خواهیم داشت:
۲‑۱۳
و دراین حالت ادعا می‌کنیم که چندجمله‌ای اتصال زیر انتخاب معتبری برای خواهد بود.
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
۲‑۱۴
با توجه به رابطه ۲‑۱۴ حداکثر درجه برابر است با:
که سمت راست تساوی از جای‌گذاری رابطه ۲‑۱۳ به دست آمده است. بنابراین یک چندجمله ای اتصال قابل قبول برای LFSR با طول L خواهد بود به طوری که :
۲‑۱۵
علاوه بر این با بهره گرفتن از رابطه (۱۴) داریم:
که تساوی آخر از رابطه ۲‑۱۰ و ۲‑۱۲ نتیجه می‌شود. بنابراین از رابطه ۲‑۲ داریم که LFSR با طول L و چندجمله ای اتصال ، n+1 بیت دنباله‌ی تولید خواهد کرد. در نتیجه L در رابطه ۲‑۱۵ شرایط لم۱ را در حالت تساوی برقرار می‌کند و خواهیم داشت ، بنابراین این تساوی در لم۱ همیشه برقرار است. بدین صورت قضیه ۲‑۲ را نیز اثبات کرده ایم.
قضیه ۲‑۲ :
اگر LFSR با طول دنباله ی و همچنین دنباله‌ی را تولید کند، آنگاه . بالعکس اگر LFSR ای با طول دنباله‌ی را تولید کند اما قادر به تولید دنباله‌ی نباشد، آنگاه .
اثبات ما برای قضیه ۲‑۲ یک اثبات سازنده برای گسترش اعتبار الگوریتم زیر به منظور پیدا کردن کوتاهترین LFSR برای تولید دنباله ی به شمار می‌رود.
سنتز الگوریتم LFSR (الگوریتم تکرار شونده برلکمپ[۱۰]) :
به ازای هرN زمانی که N = n شود و مرحله‌ی۲ به اتمام رسد پس از آن مقدار به دست آمده توسط الگوریتم به صورت روابط زیر با مقادیر گفته شده در قضیه ۲‑۲ :در ارتباط است:
اساس و پایه‌ی الگوریتم برلکمپ [۱] از قضیه ۲‑۲ :نتیجه شده است. مرحله ۵ در آن دقیقاً زمانی اتفاق می افتد که به تغییر طول احتیاج داشته باشیم. در این مورد برای مرحله بعدی تکرار، آخرین چندجمله ای اتصال قبل از آخرین تغییر طول خواهد بود بنابراین جدید برابر با خواهد بود. بعد از آن فرض کنید اولین غیر صفر در مرحله ۲ با رخ دهد. این اتفاق به این معنی است که اما می‌باشد. در این لحظه است و طول دنباله قبل از آخرین تغییر طول تعریف نشده‌است زیرا هیچ LFSR ای نمی‌تواند طول کمتر از صفر داشته باشد. بنابراین رابطه ۲‑۱۴ برای محاسبه چند جمله‌ای اتصال بعدی قابل اجرا نیست. با این حال، در این مورد مقداردهی اولیه در مرحله۱ دارای اثری است که در مرحله۵ به کار گرفته می‌شود و پس از آن و نتیجه می‌شود که البته قبلاً ذکر شده بود که هر LFSR ای با طول K+1 پاسخ قابل قبولی برای این مورد می‌باشد.
شکل ۲‑۲٫ مثال به کار بردن الگوریتم سنتز LFSR روی دنباله باینری [۲]
شکل ۲‑۲ .مدار منطقی مربوط به پیاده‌سازی الگوریتم سنتز LFSR [2]
در شکل ۲-۲ نتایج به کار گیری الگوریتم برروی یک دنباله باینری در میدان نشان داده شده است. توجه داشته باشید که LFSR نتیجه شده منحصر بفرد است و در آن آخرین مرحله‌اش دارای تپ نمی باشد.
شکل۲-۳ مدار منطقی برای پیاده سازی این الگوریتم را نشان می‌دهد و بیانگر این است که به اندازه واحد حافظه احتیاج دارد که در آن هر سلول می‌تواند یک رقم در میدان را در خود ذخیره کند و حداکثر طول LFSR است که می‌تواند توسط این مدار تولید شود.
تا اینجا ما تنها به بررسی راهی برای یافتن رجیستر کمینه طول به منظور تولید یک دنباله‌ی موردنظر بوده ایم. اما مجموعه‌ای از همه‌ی LFSR های کمینه طول را که می‌توانند دنباله ی موردنظر تولید کنند را می‌توان با بهره گرفتن از الگوریتم سنتز LFSR به آسانی یافت. با توجه به قضیه ۲‑۲ :مشاهده می کنیم، زمانی که اگر LFSRی که دنباله‌ی را تولید می‌کند نتواند دنباله تولید کند به یک تغییر طول احتیاج دارد که اگر و فقط اگر باشد. به این دلیل که زمانی یک LFSR کمینه طول، منحصربفرد است که اگر و فقط اگر باشد. بنابراین اگر الگوریتم در حالت متوقف شود LFSR کمینه طول نتیجه شده منحصربفرد نخواهد بود. تنها زمانی این LFSR نتیجه شده پاسخی منحصربفرد خواهد بود که بقیه بیت های دنباله شامل با بیت های دنباله ی خروجی LFSR یکی باشند. علاوه بر این برای هر بیت باقی مانده از دنباله فقط از مراحل ۳ و ۴ الگوریتم برای یافتن چندجمله‌ای اتصال جدید استفاده می‌شود چرا که از الگوی اختلاف مجاور برای تعیین مضرب چندجمله ای تغییرناپذیر به کار می رود و در آخر به نهایی اضافه می شود. تمامی این اظهارات در قضیه زیر به صورت خلاصه بیان شده است.
قضیه ۲‑۳ :
فرض کنید الگوریتم سنتز LFSR روی دنباله اجرا شده است و متغیرهای و دارای مقادیر خود پس ازپایان اجرای الگوریتم می باشند. اگر باشد آنگاه چندجمله‌ای اتصال منحصربفرد LFSR با کمینه طول می‌باشد که می‌تواند دنباله موردنظر را تولید کند. اگر باشد مجموعه همان مجموعه چندجمله‌ای‌های اتصال موردنظر برای LFSR با کمینه طول می‌باشد که قادر به تولید دنباله مورد نظر هستند.
فرم در حال بارگذاری ...
