نتیجه:
اگر باشد الگوریتم سنتز LFSR پاسخ کمینه طول منحصربفرد و را مشخص خواهد کرد. اما زمانی که باشد تنها فقط بیت دنباله توسط الگوریتم پردازش شده است.
به عنوان مثال، اگر دنباله یک چرخه غیرصفر با طول از LFSR ای با حداکثر طول ۱۰۰ سلول باشد این الگوریتم الزاماً پس از آنکه بیت اول دنباله را پردازش کند می تواند LFSR مولد منحصربفرد را پیدا کند.
الگوریتم سنتز LFSR ارائه شده در این بخش عملاً شبیه به الگوریتم تکرار شونده‌ی برلکمپ برای کدگشایی کدهای BCH [3] می باشد. لازم به ذکراست زمانی که و باشد مجاز به تغییر مرحله ۴ از الگوریتم می‌باشیم به طوری که میتوان به جای از همان قدیمی (مرحله قبل) استفاده کرد. دلیل این کار این است که میتوان نشان داد که به جای انتخاب به عنوان چندجمله‌ای اتصال قبل از آخرین تغییر طول، کافی است را به عنوان چندجمله‌ای‌های اتصال برای هر یک از حالت‌های که در آن و به حداکثر رسیده است انتخاب کرد. همچنین زمانی که و باشد، خواهیم داشت . بنابراین جایگزین قابل قبولی برای خواهد بود. الگوریتم برلکمپ شامل یک آزمون اضافی برای تصمیم‌گیری جایگزینی در این حالت میباشد اما به نظر می‌رسد که این آزمون هیچ مزیتی ندارد و ما آن را از الگوریتم سنتز LFSR حذف کرده‌ایم.
نمایش کلاسیک دنباله های LFSR
در این بخش ما به بررسی ویژگیهای دنباله‌های تولید شده توسط LFSR ها با نگاهی به سمت به کارگیری کدهای BCH در این دنباله ها می‌پردازیم.
خواهیم دید که نمایش دنباله با بهره گرفتن از تبدیل-D هافمن[۱۱] بسیار ساده تر خواهد بود.
| ۲‑۱۶ |
با توجه به رابطه ۲‑۸ و۲‑۱۶ می بینیم که رابطه ۲‑۲ به سادگی مشخص می کند که در حاصلضرب اندیس j در دنباله برای به صفر می رسند. بنابراین می توان رابطه را به صورت زیر بازنویسی کرد.
| ۲‑۱۷ |
که در آن
| ۲‑۱۸ |
یک چندجمله ای با درجه ی کمتر از L می باشد. علاوه برآن با بهره گرفتن از رابطه ۲‑۱۷ و ۲‑۱۸ می توان معادله ماتریسی زیر را که رابطه ضرایب را با چند جمله ای LFSR و مقدار اولیه آن را بیان می کند، نوشت.
| ۲‑۱۹ |
از آنجایی که ماتریس رابطه۲‑۱۹ معکوس پذیر می باشد، پس به ازای هر ، مقدار اولیه منحصربفرد متناظر وجود خواهد داشت. این موضوع به طور خلاصه در قضیه۴ بیان شده است.
قضیه ۲‑۴ :
دنباله خروجی تولید شده توسط LFSR L-مرحله ای با چند جمله ای اتصال همان مجموعه متناظر با مجموعه تبدیل زیر می باشد:
قضیه ۲‑۴ :نشان میدهد که دنباله s دنباله خروجی یک LFSR است اگر و فقط اگر تبدیل آن یک تابع گویا باشد. به عنوان مثال، به صورت نسبت دوچندجمله ای باشد به طوری که . علاوه بر این اگر دو چند جمله ای و نسبت به هم اول باشند (یعنی هیچ عامل مشترک از درجه یک یا بیشتر نداشته باشند.) به تبعیت از قضیه ۲‑۴ الزاماً دارای یک ضریب ثابت است به طوری که می باشد و همان چند جمله‌ای اتصال کوتاهترین LFSR ای است که دنباله S را تولید می کند. طول این LFSR حداکثر از درجه یا درجه به علاوه یک است. این مطلب را به زبان دیگر میتوان در نتیجه زیر بیان کرد.
نتیجه :
اگر چندجمله ای به صورت باشد به طوری که و نسبت به هم اول باشند و باشد آنگاه چندجمله ای اتصال کوتاهترین LFSR ای است که دنباله s را با تبدیل تولید می کند و:
|
[جمعه 1400-07-30] [ 06:28:00 ب.ظ ]
|
