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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
4 بیتی LFSR فیبوناچی با نمودار حالت آن است. گیت XOR فراهم می‌کند بازخورد به ثبت نام که شیفت بیت از چپ به راست است. دنباله حداکثر متشکل از هر دولت ممکن است به جز "۰۰۰۰" دولت

در محاسبه ثبات تغییر باز خورد خطی (به انگلیسی: linear feedback shift register) بیت ورودی، عملکرد خطی مرحله پیشین می‌باشد.

متداول ترین عملکرد خطی بکار رفته در بیت‌های منفرد، XOR است. از اینرو، LRFS غالباً ثبات تغییر است که بیت ورودی در آن از طریق XORهای انحصاری یا برخی بیت‌های دارای مقدار کلی ثبات تغییر بدست می‌آید.

مقدار اولیه LFSR، ریشه، نامیده می‌شود و به دلیل قطعی بودن عملیات ثبات، زنجیره مقادیر بدست آمده از این ثبات بطور کامل بوسیله مرحله فعلی (یا پیشین) تعیین می‌گردد. همچنین، به این دلیل که ثبات تعداد مشخصی از حالات ممکن را دارا می‌باشد، در نهایت باید دوره تکراری را وارد نمود. در صورت، LFSR با عملکرد باز خورد انتخابی می‌تواند، دامنه‌ای از بیت‌ها را بوجود آورد که بطور تصادفی ظاهر می‌شود و دارای دوره بسیار طولانی هستند.

عملیات‌های LFSR عبارتند از تولید اعداد شبه تصادفی - توالی شبه صوتی، شمارنده‌های سریع عددی و توالی سفید سازی انجام عمیات سخت‌افزار و نرم‌افزار در LFSRها متداول است.

علم ریاضی بررسی مکرر دوره‌ای، برای بررسی سریع خطاهای انتقال مورد استفاده قرار می‌گیرد که دقیقاً به LFSR مربوط می‌باشد.

فیبوناچی LFSRs[ویرایش]

یک LFSR شانزده بیتی فیبوناچی، تعداد بیت‌های باز خورد در محل سفید رنگ با چند جمله‌ای اولیه در این جدول متناظر است، بنابراین دوره‌های ثبات از طریق ماکزیمم عدد ۶۵۵۳۵ وضعیت نمام صفرها را منحصربه‌فرد می‌نماید. حالت نشان داده شده، 0XACE1 (ششصت تایی) در نتیجه 0X5670 بدست می‌آید.

موقعیت‌های بیتی که حالت بعدی را تحت تاثیر قرار می‌دهد، تپ نامیده می‌شوند. در این نمودار این تپ‌ها [۱۶٬۱۴٬۱۳٬۱۱] هستند. راست ترین بیت در LFSR، بیت خروجی نامیده می‌شود. این تپ‌ها بطور متوالی با بایت خروجی XOR شده و سپس در چپ ترین بیت بازخورد می‌دهند. زنجیره بیتها در موقعیت راست ترین زنجیره خروجی نامیده می‌شوند.

  • بیت‌های حالت LFSR که بر ورودی تاثیر می‌گذارند، تپ نامیده می‌شوند (محل سفید رنگ نمودار).
  • ماکزیمم طول LFSR، توالی m را بوجود می‌آورد (یعنی، از طرق تمام حالتهای 2n-1 ممکن در فهرست تغییر به استثناء حالتی که تمام بیتی‌ها صفر هستند، تکراری می‌شود)، مگر اینکه شامل تمام صفرهایی باشد که در آن هیچگونه تغییری ایجاد نشود.
  • بعنوان راه حل بازخورد متنی بر XOR در LFSR، فرد می‌تواند از XNOR استفاده نماید. این عملکرد طرح مشابه بوده و بطور محدود طرح خطی نمی‌باشد، اما از یک شمارنده چند جمله‌ای معادل ناشی می‌شود که در آن حالت شمارنده، اغجرای وضعیت LFSR می‌باشد. یک شمارنده چند جمله‌ای معادل ناشی می‌شود که در آن حالت شمارنده، اجرای وضعیت LFSR می‌باشد. یک وضعیت با تمام یک‌ها، در زمان استفاده از بازخورد XNOR غیر قانونی بوده و به روش مشابه در زمان استفاده از XOR، صفرهای آن غیر قانونی است. این حالت غیر قانونی در نظر گرفته می‌شود، زیرا شمارنده، در این وضعیت "مسدود" باقی خواهد ماند.

توالی اعداد موجود آمده بوسیله LFSR یا نظیر XNOR آن می‌تواند همانند کد خاکستری یا کد صفر و یک داخلی معتبر، سیستم عددی صفر و یک مدّ نظر قرار می‌گیرد.

تنظیم تپها در بازخورد LFSR می‌تواند بعنوان طرح چند جمله‌ای در علم حساب زمینه مشخص بیان گردد. یعنی اینکه ضرایب چند جمله‌ای باید0's یا 1's باشد. این مطلب چند جمله‌ای بازخورد یا دارای خصوصیت دو سویه نامیده می‌شود. بعنوان مثال، اگر تپ‌ها در بیت‌های ۱۱٬۱۳٬۱۴٬۱۶ اُم باشند (همانطور که نشان داده شد)، چند جمله‌ای بازخورد بصورت زیر است:

'یک' در چند جمله‌ای با تپ متناظر نمی‌باشد- بلکه با ورودی بیت نخست (یعنی، x0 با ۱ معادل است) مشابه است. توان‌های این عبارات، بیت‌های تپ داررا نشان می‌دهد، که از چپ شمرده می‌شود. بیت‌های اول و آخر همیشه بعنوان، به ترتیب تپ ورودی و خروجی به هم متصل می‌شوند. جداول را نشان می‌دهد، که از چپ شمرده می‌شود. بیت‌های اول و آخر همیشه بعنوان، به ترتیب تپ ورودی و خروجی به هم متصل می‌شوند.

جداول چند جمله‌ای اولیه که در آن LFSRهای دارای طول ماکزیمم تولید می‌شوند، در قسمت زیر و در منابع ارائه شده است.

  • تنها اگر تعداد تپ‌ها یکسان باشد، LFSR می‌تواند دارای طول ماکزیمم باشد.
  • مجموعه تپ ها-که با هم در نظر گرفته می‌شوند، نه روستایی (یعنی، بعنوان عوامل جفتی) – بایستی پریم نسبی باشد. به عبارتی دیگر، در اینجا نباید برای تمام تپ‌ها مقسوم علیه مشترک وجود داشته باشد.
  • در اینجا می‌تواند بیش از یک توالی تپ دارای طول ماکزیمم برای طول ارائه شده LFSR وجود داشته باشد.
  • زمانیکه توالی تپ دارای طول ماکزیمم وجود داشته باشد، سایرین بطور خودکار از آن پیروی می‌کنند. اگر توالی تپ در بیت n ام LFSR، [n,A،BG,C،0] که در آن صفر متناظر با عبارت x0=1 باشد، سپس توالی 'بازتابگر' متناظر [n,n-C,n-B,n-A,0] است. بنابراین توالی تپ، [۳۲٬۷٬۳٬۲٬۰] همانند نظیر خود [۳۲٫۳۰٫۲۹٫۲۵٫۰] می‌باشد. هر دو یک توالی با طول ماکزیمم را ارائه می‌دهند.

برخی مثالهای کد C بصورت زیر است:

# include <stdint.h>
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 <<15);
  ++period;
} while(lfsr!= 0xACE1u);

در کد فوق تصور می‌شود، مهمترین بیت LFSR، یک و کم اهمیت ترین بیت ۱۶ باشد. این قالب LFSR و همچنین فیبوناچی تحت عنوان استاندارد، زیاد به یک یا درگاه‌های خارجی XOR نامیده می‌شوند. LFSR دارای چارچوب دیگری نیز است.

LFSRs گالویس[ویرایش]

یک LFSR گالویس ۱۶ بیتی. تعداد فهرست محل سفید رنگ متناظر با چند جمله‌ای اولیه مشابه، است همانند مثال فیبوناچی، اما در مسیر انتقال بطور معکوس شمرده می‌شود. بعلاوه، این فهرست از طریق تعداد ماکزیمم حالات ۶۵۵۳۵ منحصر به تمام صفرها، تکرار می‌شود. حالت شش‌گانه ACE1 نشان داده شده، در نتیجه E270 شش‌گانه بدست خواهد آمد.

LFSR با قالب گالویس، نام ریاضیدان فرانسوی او اریسته گالویس را یدک می‌کشد که به قدر مطلقی، XORهای داخلی و همچنین LFSR بک به زیاد شناخته شده است و ساختاری دیگر است که می‌تواند زنجیره خروجی مشابهی را بعنوان LFSR متداول بوجود آورد (اما به موقع متوازن) در ساختار گالویس، زمانیکه این سیستم مسدود می‌شود، بیتهایی که تپ نیستند، یک وضعیت را به سمت راست بدون تغییر رها می‌کنند. این تپها، به عبارت دیگر، بیش از ذخیره‌سازی در وضعیت بعدی، بایت خروجی XOR می‌شوند. بیت خروجی جدید، بیت ورودی بعدی است. نتیجه این است زمانیکه بیت خروجی صفر است، تمام بیت‌های فهرست بدون تغییر به سمت راست انتقال می‌یابند، و بیت ورودی صفر می‌شود هنگامیکه بیت خروجی یک می‌شود، و سپس فهرست کامل به سمت راست انتقال یافته و بیت ورودی به یک، تبدیل می‌شود.

برای ایجاد دامنه خروجی مشابه، مرتبه تپ‌ها، متناظر مرتبه LFSR قدر مطلقی می‌باشد، در غیر اینصورت، این زنجیره معکوس خواهد شد. توجه کنید که ضرورتاً، حالت داخلی LFSR، یکسان است. فهرست گالویس ارائه شده، دارای دامنه خروجی مشابه به همانندفهرست فیبوناچی در بخش نخست می‌باشد. زمان متوازن میان این دامنه‌ها بوجود می‌آید، سپس برای دستیابی به خروجی یکسان هر دوره به نقطه شروع متفاوتی نیازمند هستیم.

  • LFSRهای گالویس برای تولید ورودی جدید (با XOR سازی در LFSR و بدون درگاههای – XOR اجرا شده در سریال، سپس، زمان تکثیر به جای کل زنجیره به یک XOR، کاهش می یایبد)، هر تپ را هم زنجیره نمی‌نماید، بنابراین برای هر تپ، محاسبه مشابه، افزایش سرعت اجرا، امکان پذیر است.
  • در اجرای نرم‌افزار LFSR، شکل گالویس، همانند عملیات XOR که در لحظه، یک واژه را اجرا می‌سازد، کار آمدتر است: فقط بیت خروجی بایستی بطور انحصاری بررسی گردد.

در قسمت زیر نمونه کد دارای دوره ماکزیمم ۳۲ بیتی در LFSR گالویس وجود دارد که با C معتبر است:

# include <stdint.h>
uint32_t lfsr = ۱;
unsigned period = ۰;
 
do {
  /* taps: 32 31 29 1; feedback polynomial: x^32 + x^31 + x^29 + x + 1 */
  lfsr = (lfsr>> 1) ^ (-(lfsr & 1u) & 0xD0000001u);
  ++period;
} while(lfsr!= 1u);

و در اینجا برای نمونه ۱۶ بیتی در شکل، کدی وجود دارد.

# include <stdint.h>
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 <stdint.h>
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 با تپ‌های بازتابگر از طریق توالی خروجی با مرتبه معکوس تکرار خواهد شد.

منابع[ویرایش]

* http://en.wikipedia.org/wiki/LFSR

پیوند به بیرون[ویرایش]