شیفت رِجیستر فیدبک دار خطی ( به انگلیسی: Linear feedback shift register ) یا LFSR، شیفت رجیستری n - بیتی است که ترکیب خطی برخی از بیت های آن، به عنوان ورودی، به آن بازخورد ( فیدبک ) می شود ( شکل روبرو را ببینید ) .
کار LFSR با یک مقدار اولیۀ n - بیتی غیرصفر آغاز می شود. این مقدار اولیه، دانه ( Seed ) یا حالت اولیه ( Initial state ) نام دارد. رشته بیت های تولیدشدۀ LFSR، به حالت ( State ) کنونی و ورودی شیفت رجیستر بستگی دارد. چون تعداد حالات ممکن شیفت رجیستر، محدود است، رشته بیت خروجی آن تکرار می شود.
با انتخاب سرهای ( بیت های ) مناسب که ترکیب خطی آن ها به ورودی شیفت رجیستر بازخورد ( فیدبک ) می شود، می توان رشته ای از بیت ها را تولید کرد که شبه تصادفی ( Pseudorandom ) و دارای دوره تکرار طولانی هستند. اینکه کدام بیت های شیفت رجیستر برای فیدبک انتخاب شوند را چندجمله ای متناظر LFSR تعیین می کند. هر LFSR، یک چندجمله ای متناظر دارد.
در یک LFSR با شیفت رجیستر n - بیتی، حداکثر دورۀ تناوب رشته بیت تولیدشده، برابر 2 n − 1 است. این مقدار به شرطی به دست می آید که چندجمله ای متناظر LFSR، اول ( primitive ) باشد. چندجمله ای اول، کاهش ناپذیر ( irreducible ) است، یعنی نمی توان آن را به عوامل اول تجزیه کرد. در این حالت، رشته بیت تولیدشده را «رشتۀ با طول بیشینه» ( maximum - length sequence ) یا به اختصار m - رشته ( m - sequence ) می گویند. m - رشته ها، خواص جالبی دارند؛ مثلاً اینکه تابع خودهمبستگی آن ها، شباهت زیادی به تابع خودهمبستگی نویز سفید دارد، و نیز اینکه، تعداد صفر و یک ها در آن ها، تقریباً برابر است. به این دو دلیل، آن ها شبه تصادفی هستند.
اصول عملکرد LFSRها، در مبحث میدان های متناهی مطرح می شود. میدان های متناهی را با F q n نشان می دهند، که q ، عددی اول و n عددی طبیعی است ( در اینجا، طول شیفت رجیستر ) . اعضای F q n ، چندجمله ای هایی هستند که درجۀ آن ها، حداکثر برابر n است، و ضرائب آن ها از مجموعۀ F q = { 0 , 1 , 2 , … , q − 1 } گرفته می شوند. چندجمله ای متناظر LFSR، در این میدان تعریف می شود. اگر q = 2 باشد، خروجی LFSR، یک رشته بیت ( باینری ) است.
نام دیگر میدان های متناهی، میدان های گالوا ( Galois fields ) است؛ به افتخار ریاضی دان فرانسوی، اِواریست گالوا ( Evariste Galois ) .
کاربردی از LFSR در تولید اعداد شبه تصادفی ( تولید نویز سفید ) است. در مهندسی برق ( به ویژه مخابرات ) و کامپیوتر از LFSRها استفاده می شود.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفکار LFSR با یک مقدار اولیۀ n - بیتی غیرصفر آغاز می شود. این مقدار اولیه، دانه ( Seed ) یا حالت اولیه ( Initial state ) نام دارد. رشته بیت های تولیدشدۀ LFSR، به حالت ( State ) کنونی و ورودی شیفت رجیستر بستگی دارد. چون تعداد حالات ممکن شیفت رجیستر، محدود است، رشته بیت خروجی آن تکرار می شود.
با انتخاب سرهای ( بیت های ) مناسب که ترکیب خطی آن ها به ورودی شیفت رجیستر بازخورد ( فیدبک ) می شود، می توان رشته ای از بیت ها را تولید کرد که شبه تصادفی ( Pseudorandom ) و دارای دوره تکرار طولانی هستند. اینکه کدام بیت های شیفت رجیستر برای فیدبک انتخاب شوند را چندجمله ای متناظر LFSR تعیین می کند. هر LFSR، یک چندجمله ای متناظر دارد.
در یک LFSR با شیفت رجیستر n - بیتی، حداکثر دورۀ تناوب رشته بیت تولیدشده، برابر 2 n − 1 است. این مقدار به شرطی به دست می آید که چندجمله ای متناظر LFSR، اول ( primitive ) باشد. چندجمله ای اول، کاهش ناپذیر ( irreducible ) است، یعنی نمی توان آن را به عوامل اول تجزیه کرد. در این حالت، رشته بیت تولیدشده را «رشتۀ با طول بیشینه» ( maximum - length sequence ) یا به اختصار m - رشته ( m - sequence ) می گویند. m - رشته ها، خواص جالبی دارند؛ مثلاً اینکه تابع خودهمبستگی آن ها، شباهت زیادی به تابع خودهمبستگی نویز سفید دارد، و نیز اینکه، تعداد صفر و یک ها در آن ها، تقریباً برابر است. به این دو دلیل، آن ها شبه تصادفی هستند.
اصول عملکرد LFSRها، در مبحث میدان های متناهی مطرح می شود. میدان های متناهی را با F q n نشان می دهند، که q ، عددی اول و n عددی طبیعی است ( در اینجا، طول شیفت رجیستر ) . اعضای F q n ، چندجمله ای هایی هستند که درجۀ آن ها، حداکثر برابر n است، و ضرائب آن ها از مجموعۀ F q = { 0 , 1 , 2 , … , q − 1 } گرفته می شوند. چندجمله ای متناظر LFSR، در این میدان تعریف می شود. اگر q = 2 باشد، خروجی LFSR، یک رشته بیت ( باینری ) است.
نام دیگر میدان های متناهی، میدان های گالوا ( Galois fields ) است؛ به افتخار ریاضی دان فرانسوی، اِواریست گالوا ( Evariste Galois ) .
کاربردی از LFSR در تولید اعداد شبه تصادفی ( تولید نویز سفید ) است. در مهندسی برق ( به ویژه مخابرات ) و کامپیوتر از LFSRها استفاده می شود.
wiki: ثبات تغییر بازخورد خطی