وبلاگ

 

 

 

 

اثبات: برای  که قضیه به طور بدیهی صحیح می‌باشد بنابراین فرض می‌کنیم  است. اگر  و  ضرایب دوLFSR مطرح شده باشند و برخلاف رابطه (۳) فرض کنیم که  باشد با توجه به فرضیات قبلی خواهیم داشت:

 

 

‏۲‑۴

 

 

 

 

 

و

 

 

‏۲‑۵

 

 

 

 

 

بنابراین می‌توان نوشت:

 

 

‏۲‑۶

 

 

 

 

 

اینکه از رابطه‌ی ‏۲‑۵ در سمت چپ رابطه‌ی ‏۲‑۶ استفاده کرده‌ایم به این دلیل است که مجموعه  زیر مجموعه‌ای از مجموعه  می‌باشد. با جا به جا کردن مرتبه‌ی جمع ها و استفاده از روابط ‏۲‑۴ و ‏۲‑۵ خواهیم داشت:

 

 

‏۲‑۷

 

 

 

 

 

استفاده از رابطه ‏۲‑۴ این را نشان می‌دهد که مجموعه  زیر مجموعه‌ای از مجموعه  می‌باشد. اما رابطه‏۲‑۷، رابطه ‏۲‑۴ را رد می‌کند و ثابت می‌کند که فرضیه  غیرقابل قبول است. بنابراین همان‌طور که در قضیه‏۲‑۱ مطرح شد نتیجه می‌گیریم که  می‌باشد.
اگر دنباله‌ی  را یک دنباله‌ی نامتناهی در نظر بگیریم که N بیت اول این دنباله به صورت  باشد، چند جمله ای  را چند جمله‌ای با کمترین درجه تعریف می‌کنیم که در میان تمام LFSR ها بتواند دنباله‌ی  را تولید کند. با توجه به گفته‌های قبلی  می‌باشد. علاوه بر این با افزایش N ، درجه‌ی چندجمله‌ای باید به طور یکنواختی غیرکاهشی باشد. به تعبیر ساده‌تر می‌توان گفت که تمام دنباله‌های تمام صفر توسط LFSR ای با طول  تولید می‌شوند، بنابراین  است اگر و فقط اگر دنباله‌ی  تماماً صفر باشد.
لم۱:
اگر LFSR ای با طول  دنباله‌ی  را تولید کند اما نتواند دنباله‌ی  تولید کند، خواهیم داشت:

اثبات: از غیر نزولی بودن  داریم  . قضیه ۱ نیز تاکید می‌کند که  پس با توجه با این دو رابطه، لم همیشه برقرار است.
در قسمت بعدی از لم۱ برای نشان دادن اینکه LFSR ای که توسط این الگوریتم یافته و مشخص می‌شود دارای کمینه طول^[۶] است، استفاده می شود. با توجه به نتایج به دست آمده از محاسبات نیز می‌توان ثابت کرد که نامساوی در لم۱ را می‌توان با تساوی جایگزین کرد.
سنتز الگوریتم LFSR
در این قسمت به بررسی یک الگوریتم بازگشتی مربوط به محاسبه طول LFSR ، با نماد  می‌پردازیم که منجر به تولید دنباله‌ی  به ازای  می‌شود. چند جمله ای  را به عنوان چندجمله‌ای اتصال^[۷] برای LFSR در شکل ‏۲‑۱به صورت زیر تعریف می‌کنیم: