شیفت رِجیستر فیدبک دار خطی (به انگلیسی: Linear feedback shift register) یا LFSR، شیفت رجیستری n {\displaystyle n} -بیتی است که ترکیب خطی برخی از بیت های آن، به عنوان ورودی، به آن بازخورد (فیدبک) می شود (شکل روبرو را ببینید).
International Telecommunications Union Recommendation O.151 (August 1992)
Maximal Length LFSR table with length from 2 to 67. (Error detected: period are (2^n)-1 not 2^n)
Pseudo-Random Number Generation Routine
http://www.quadibloc.com/crypto/co040801.htm
Feedback terms
General LFSR Theory
An implementation of LFSR in VHDL.
کار LFSR با یک مقدار اولیۀ n {\displaystyle n} -بیتی غیرصفر آغاز می شود. این مقدار اولیه، دانه (Seed) یا حالت اولیه (Initial state) نام دارد. رشته بیت های تولیدشدۀ LFSR، به حالت (State) کنونی و ورودی شیفت رجیستر بستگی دارد. چون تعداد حالات ممکن شیفت رجیستر، محدود است، رشته بیت خروجی آن تکرار می شود.
با انتخاب سرهای (بیت های) مناسب که ترکیب خطی آن ها به ورودی شیفت رجیستر بازخورد (فیدبک) می شود، می توان رشته ای از بیت ها را تولید کرد که شبه تصادفی (Pseudorandom) و دارای دوره تکرار طولانی هستند. اینکه کدام بیت های شیفت رجیستر برای فیدبک انتخاب شوند را چندجمله ای متناظر LFSR تعیین می کند. هر LFSR، یک چندجمله ای متناظر دارد.
در یک LFSR با شیفت رجیستر n {\displaystyle n} -بیتی، حداکثر دورۀ تناوب رشته بیت تولیدشده، برابر 2 n − 1 {\displaystyle 2^{n}-1\,} است. این مقدار به شرطی به دست می آید که چندجمله ای متناظر LFSR، اول (primitive) باشد. چندجمله ای اول، یک چندجمله ای است که کاهش ناپذیر (irreducible) است، یعنی نمی توان آن را به عوامل اول تجزیه کرد. در این حالت، رشته بیت تولیدشده را «رشتۀ با طول بیشینه» (maximum-length sequence) یا به اختصار m-رشته (m-sequence) می گویند. m-رشته ها، خواص ویژه و جالبی دارند؛ مثلاً اینکه تابع خودهمبستگی آن ها، شباهت زیادی به تابع خودهمبستگی نویز سفید دارد، و نیز اینکه، تعداد صفر و یک ها در آن ها، تقریباً برابر است. به این دو دلیل، آن ها شبه تصادفی هستند.
International Telecommunications Union Recommendation O.151 (August 1992)
Maximal Length LFSR table with length from 2 to 67. (Error detected: period are (2^n)-1 not 2^n)
Pseudo-Random Number Generation Routine
http://www.quadibloc.com/crypto/co040801.htm
Feedback terms
General LFSR Theory
An implementation of LFSR in VHDL.
کار LFSR با یک مقدار اولیۀ n {\displaystyle n} -بیتی غیرصفر آغاز می شود. این مقدار اولیه، دانه (Seed) یا حالت اولیه (Initial state) نام دارد. رشته بیت های تولیدشدۀ LFSR، به حالت (State) کنونی و ورودی شیفت رجیستر بستگی دارد. چون تعداد حالات ممکن شیفت رجیستر، محدود است، رشته بیت خروجی آن تکرار می شود.
با انتخاب سرهای (بیت های) مناسب که ترکیب خطی آن ها به ورودی شیفت رجیستر بازخورد (فیدبک) می شود، می توان رشته ای از بیت ها را تولید کرد که شبه تصادفی (Pseudorandom) و دارای دوره تکرار طولانی هستند. اینکه کدام بیت های شیفت رجیستر برای فیدبک انتخاب شوند را چندجمله ای متناظر LFSR تعیین می کند. هر LFSR، یک چندجمله ای متناظر دارد.
در یک LFSR با شیفت رجیستر n {\displaystyle n} -بیتی، حداکثر دورۀ تناوب رشته بیت تولیدشده، برابر 2 n − 1 {\displaystyle 2^{n}-1\,} است. این مقدار به شرطی به دست می آید که چندجمله ای متناظر LFSR، اول (primitive) باشد. چندجمله ای اول، یک چندجمله ای است که کاهش ناپذیر (irreducible) است، یعنی نمی توان آن را به عوامل اول تجزیه کرد. در این حالت، رشته بیت تولیدشده را «رشتۀ با طول بیشینه» (maximum-length sequence) یا به اختصار m-رشته (m-sequence) می گویند. m-رشته ها، خواص ویژه و جالبی دارند؛ مثلاً اینکه تابع خودهمبستگی آن ها، شباهت زیادی به تابع خودهمبستگی نویز سفید دارد، و نیز اینکه، تعداد صفر و یک ها در آن ها، تقریباً برابر است. به این دو دلیل، آن ها شبه تصادفی هستند.
wiki: ثبات تغییر بازخورد خطی