ثبات تغییر بازخورد خطی

4 بیتی LFSR فیبوناچی با نمودار حالت آن است. گیت XOR فراهم می‌کند بازخورد به ثبت نام که شیفت بیت از چپ به راست است. دنباله حداکثر متشکل از هر دولت ممکن است به جز "۰۰۰۰" دولت
در علم محاسبه ثبات تغییر باز خورد خطی بیت ورودی، عملکرد خطی مرحله پیشین می‌باشد.
متداول‌ترین عملکرد خطی بکار رفته در بیت‌های منفرد، XOR است. از اینرو، LRFS غالبا ثبات تغییر است که بیت ورودی در آن از طریق XORهای انحصاری یا برخی بیت‌های دارای مقدار کلی ثبات تغییر بدست می‌آید.
مقدار اولیه LFSR، ریشه، نامیده می‌شود و به دلیل قطعی بودن عملیات ثبات، زنجیره مقادیر بدست آمده از این ثبات بطور کامل بوسیله مرحله فعلی (یا پیشین) تعیین می‌گردد. همچنین، به این دلیل که ثبات تعداد مشخصی از حالات ممکن را دارا می‌باشد، در نهایت باید وارد حلقه‌ای تکراری شود. اگر چه، LFSR با تابع باز خورد انتخابی خوبی، می‌تواند دامنه‌ای از بیت‌ها را بوجود آورد که بطور تصادفی ظاهر می‌شود و دارای دوره تکرار بسیار طولانی هستند.
کاربردهای LFSR عبارتند از تولید اعداد شبه تصادفی - توالی شبه صوتی، شمارنده‌های سریع عددی و توالی سفیدسازی انجام عمیات سخت‌افزار و نرم‌افزار در LFSRها متداول است.
علم ریاضی کد افزونگی چرخشی، برای بررسی سریع خطاهای انتقال داده مورد استفاده قرار می‌گیرد که دقیقا به LFSR مربوط می‌باشد.
فیبوناچی LFSRs
یک LFSR شانزده بیتی فیبوناچی، تعداد بیت‌های باز خورد در محل سفید رنگ با چندجمله‌ای اولیه در این جدول متناظر است، بنابراین دوره‌های ثبات از طریق ماکزیمم عدد ۶۵۵۳۵ وضعیت نمام صفرها را منحصربه‌فرد می‌نماید. حالت نشان داده شده، 0XACE1 (ششصت تایی) در نتیجه 0X5670 بدست می‌آید.
موقعیت‌های بیتی که حالت بعدی را تحت تاثیر قرار می‌دهد، تپ نامیده می‌شوند. در این نمودار این تپ‌ها ۱۶،۱۴،۱۳،۱۱ هستند. راست‌ترین بیت در LFSR، بیت خروجی نامیده می‌شود. این تپ‌ها بطور متوالی با بیت خروجی XOR شده و سپس در چپ‌ترین بیت بازخورد می‌دهند. زنجیره بیتها در موقعیت راست‌ترین زنجیره خروجی نامیده می‌شوند.
بیت‌های حالت LFSR که بر ورودی تاثیر می‌گذارند، تپ نامیده می‌شوند (محل سفید رنگ نمودار).
ماکزیمم طول LFSR، توالی m را بوجود می‌آورد (یعنی، تمام حالتهای 2n-1 ممکن در شیفت رجیستر به استثناء حالتی که تمام بیت‌ها صفر هستند، تکراری می‌شود)، مگر اینکه شامل تمام صفرهایی باشد که در آن هیچگونه تغییری ایجاد نشود.
به عنوان راه حل بازخورد متنی بر XOR در LFSR، فرد می‌تواند از XNOR استفاده نماید. این عملکرد طرح مشابه بوده و بطور محدود طرح خطی نمی‌باشد، اما از یک شمارنده چندجمله‌ای معادل ناشی می‌شود که در آن حالت شمارنده، مکمل وضعیت LFSR می‌باشد. یک وضعیت با تمام یک‌ها، در زمان استفاده از بازخورد XNOR غیرقانونی بوده و به روش مشابه در زمان استفاده از XOR، صفرهای آن غیرقانونی است. این حالت غیرقانونی در نظر گرفته می‌شود، زیرا شمارنده، در این وضعیت "مسدود" باقی خواهد ماند.
توالی اعداد به وجود آمده بوسیله LFSR یا نظیر XNOR آن، همانند کد گری یا دستگاه اعداد دودویی یا سیستم عددی صفر و یک می‌تواند معتبر مد نظر قرار گیرد.
تنظیم تپها در بازخورد LFSR می‌تواند به عنوان طرح چندجمله‌ای در علم حساب زمینه مشخص بیان گردد. یعنی اینکه ضرایب چندجمله‌ای باید0s یا 1s باشد. این مطلب چندجمله‌ای بازخورد یا دارای خصوصیت دو سویه نامیده می‌شود. به عنوان مثال، اگر تپ‌ها در بیت‌های ۱۱،۱۳،۱۴،۱۶ ام باشند (همانطور که نشان داده شد)، چندجمله‌ای بازخورد به صورت زیر است:
یک در چندجمله‌ای با تپ متناظر نمی‌باشد- بلکه با ورودی بیت نخست (یعنی، x0 با ۱ معادل است) مشابه است. توان‌های این عبارات، بیت‌های تپ داررا نشان می‌دهد، که از چپ شمرده می‌شود. بیت‌های اول و آخر همیشه بعنوان، به ترتیب تپ ورودی و خروجی به هم متصل می‌شوند. جداول را نشان می‌دهد، که از چپ شمرده می‌شود. بیت‌های اول و آخر همیشه بعنوان، به ترتیب تپ ورودی و خروجی به هم متصل می‌شوند.
جداول چندجمله‌ای اولیه که در آن LFSRهای دارای طول ماکزیمم تولید می‌شوند، در قسمت زیر و در منابع ارائه شده‌است.
تنها اگر تعداد تپ‌ها یکسان باشد، LFSR می‌تواند دارای طول ماکزیمم باشد.
مجموعه تپ‌ها-که با هم در نظر گرفته می‌شوند، نه روستایی (یعنی، به عنوان عوامل جفتی) – بایستی پریم نسبی باشد. به عبارتی دیگر، در اینجا نباید برای تمام تپ‌ها مقسوم علیه مشترک وجود داشته باشد.
در اینجا می‌تواند بیش از یک توالی تپ دارای طول ماکزیمم برای طول ارائه شده LFSR وجود داشته باشد.
زمانی‌که توالی تپ دارای طول ماکزیمم وجود داشته باشد، سایرین بطور خودکار از آن پیروی می‌کنند. اگر توالی تپ در بیت n ام LFSR، n,A،BG,C،0 که در آن صفر متناظر با عبارت x0=1 باشد، سپس توالی بازتابگر متناظر n,n-C,n-B,n-A,0 است. بنابراین توالی تپ، ۳۲،۷،۳،۲،۰ همانند نظیر خود ۳۲٫۳۰٫۲۹٫۲۵٫۰ می‌باشد. هر دو یک توالی با طول ماکزیمم را ارائه می‌دهند.
برخی مثالهای کد C به صورت زیر است:
include
uint16_t lfsr = 0xACE1u;
unsigned bit;
unsigned period = ۰;
do {
/* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
bit = ((lfsr>> 0) ^ (lfsr>> 2) ^ (lfsr>> 3) ^ (lfsr>> ۵)) - ۱;
lfsr = (lfsr>> ۱) | (bit
> 1) ^ (-(lfsr - 1u) - 0xD0000001u);
++period;
while(lfsr!= 1u);
و در اینجا برای نمونه ۱۶ بیتی در شکل، کدی وجود دارد.
include
uint16_t lfsr = 0xACE1u;
unsigned period = ۰;
do {
/* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
lfsr = (lfsr>> 1) ^ (-(lfsr - 1u) - 0xB400u);
++period;
while(lfsr!= 0xACE1u);
این نمونه کدها، با استفاده از عملگر XOR، برای بکارگیری مقدار متغیر، پوشش کشویی (اهرمی) را بوجود می‌آورند. این پوشش با حذف نخستین تمام بیت‌ها به غیر از بیتها ی دارای اهمیت پایین با مقدار کنونی (بیت خروجی) بدست می‌آید. بنابراین، ای مقدار، در صورتی‌که بیت خروجی، به ترتیب صفر یا یک باشد، (انکار دو تعریف) ایجاد تمام مقادیر 0s یا 1s را نفی می‌کند. به وسیله AND‌سازی نتیجه با مقدار یک، (مثلا: 0XB400 در مثال دوم)، پیش از بکارگیری پوشش اهرمی، بطور کارآمد به عنوان شرطی در استفاده یا عدم استفاده از پوشش اهرمی مبتنی بر بیت خروجی اعمال می‌شود. نمونه‌ای از کد مشخص و دارای اهمیت پایین در قسمت زیر ارائه شده‌است.
include
uint16_t lfsr = 0xACE1u;
unsigned period = ۰;
do {
unsigned lsb = lfsr - 1; /* Get lsb (i.e.، the output bit). */
lfsr>>= 1; /* Shift register */
if (lsb == 1) /* Only apply toggle mask if output bit is 1. */
lfsr ^= 0xB400u; /* Apply toggle mask, value has 1 at bits corresponding
* to taps, 0 elsewhere. */
++period;
while(lfsr!= 0xACE1u);
غیر دودویی گالویس LFSR
LFSRهای صفر و یک گالویس همانند آنهایی که در قسمت فوق ارائه شده، با هر حرف {0,1،…,q-1 q-ary (مثلا در سیستم صفر و یک، ض معادل دو و حرف الفبا، صرفا {۰،۱ است) موجود می‌آید. در این صورت، مقدار ویژه یا جزء تشکیل دهنده با واحد دیگر -q (توجه کنید که XOR، واحد دیگر ۲ است) و بیت بازخورد (بیت خروجی) تولید می‌شود که (واحد - q) بر مقدار q-ary تقسیم می‌شود. که این مقدار در هر نقطه خاص تپ ثابت است. ملاحظه نمائید که همچنین صفر و یکی تولید می‌شود. که در آن بازخورد بر هر یک از صفر (بدون بازخورد، یعنی بدون تپ) یا یک (باز خورد وجود دارد) تقسیم می‌شود. با ارائه قالب مناسبی برای تپ، چنین LFSRها می‌توانند ور تولید زمینه‌های گالویس مقادیر اولیه و اختیاری q، مورد استفاده قرار گیرد.
برخی چندجمله‌ای‌ها با ماکزیمم LFSRها
جدول ذیل فهرستی از چندجمله‌ای‌های دارای طول ماکزیمم را با طول‌های فهرست تغییر بیش از ۱۹ تهیه نموده‌است. توجه کنید که بیش از یک چندجمله‌ای می‌تواند برای هر طول ارائه شده در فهرست تغییر وجود داشته باشد. فهرستی از چندجمله‌ای‌های دیگر با طول ۳۲-۴ (بیش از آنچه که برای ذخیره یا انتقال آن‌ها غیرممکن است) را می‌توان در این قسمت یافت:
ویژگی‌های زنجیره خروجی
صفر و یک‌ها در ‘اجرا’ بوجود می‌آیند. زنجیره خروجی ۰۱۱۰۱۰۰ به عنوان مثال، شامل پنجم اجرا با طول به ترتیب ۱،۲،۱،۱،۲ است. در یک دوره از LFSR ماکزیمم، اجرای 2n-1 انجام می‌شود، (برای مثال، ۶ بیت LFSR، 32 اجرای خواهند داشت). دقیقا نیمی از این اجراها، یک بیت طول، ۴/۱ دو بیت طول، بیشتر، اجرای صفرهای واحد، n-1 بیت طول و اجرای واحد یک‌ها، n بیت طول خواهد داشت. این فرا وانی تقریبا با مقدار آماری مورد انتظار و توالی دقیقا تصادفی معادل است. در هر صورت، احتمال یافتن دقیق این فراوانی در یک نمونه از توالی تصادفی نسبتا پایین است.
زنجیره‌های خروجی LFSR، قطعی هستند. اگر از وضعیت فعلی اطلاع داشته باشید. می‌توانید، وضعیت بعدی را بیش بینی کنید. این موضوع با رویدادهای دقیقا تصادفی امکانپذیر نیست.
زنجیره خروجی معکوس می‌باشد، LFSR با تپ‌های بازتابگر از طریق توالی خروجی با مرتبه معکوس تکرار خواهد شد.