فهم حقيقة سجل إزاحة ذو تغذية خلفية خطية

في مجال الحوسبة، يُعدّ سجل الإزاحة ذو التغذية الخلفية الخطية (LFSR) سجل إزاحة تكون بتّاته المدخلة دالة خطية لحالته السابقة.

الدالة الخطية الأكثر شيوعًا للبتات المفردة هي عملية XOR (الجمع الحصري أو). لذا، غالبًا ما يكون سجل الإزاحة ذو التغذية الراجعة الخطية سجل إزاحة تُغذّى بتّاته المدخلة بعملية XOR لبعض بتات قيمة مسجل الإزاحة الكلية.

تُسمى القيمة الابتدائية لسجل الإزاحة ذو التغذية الراجعة الخطية بالبذرة، ولأنّ عمل السجل حتمي، فإنّ سلسلة القيم التي ينتجها السجل تتحدد كليًا بحالته الحالية (أو السابقة). وبالمثل، ولأنّ للسجل عددًا محدودًا من الحالات الممكنة، فلا بدّ أن يدخل في دورة متكررة. مع ذلك، يمكن لسجل الإزاحة ذو التغذية الراجعة الخطية، مع دالة تغذية راجعة مُختارة بعناية، أن ينتج سلسلة من البتات تبدو عشوائية ولها دورة طويلة جدًا.

تشمل تطبيقات سجلات الإزاحة ذات التغذية الراجعة الخطية توليد أرقام شبه عشوائية، وسلاسل ضوضاء شبه عشوائية، وعدادات رقمية سريعة، وسلاسل تبييض. وتُعدّ تطبيقات سجلات الإزاحة ذات التغذية الراجعة الخطية شائعة في كلٍّ من الأجهزة والبرامج.

تتشابه الرياضيات المستخدمة في فحص التكرار الدوري، والذي يُستخدم للتحقق السريع من أخطاء الإرسال، تشابهًا وثيقًا مع رياضيات مسجل الإزاحة ذي التغذية الخطية الخطية (LFSR). وبشكل عام، فإن العمليات الحسابية الكامنة وراء سجلات الإزاحة ذات التغذية الخطية الخطية تجعلها سهلة الدراسة والتطبيق. إذ يُمكن إنشاء دوائر منطقية معقدة نسبيًا باستخدام وحدات بناء بسيطة. مع ذلك، ينبغي أيضًا النظر في طرق أخرى أقل أناقة ولكنها ذات أداء أفضل.

بشكل مبسط، يمكن تخيّل سجل الإزاحة على أنه صفّ من البتات. عند كل خطوة زمنية:



تخرج بتة جديدة من أحد طرفي السجل

تنزاح جميع البتات خانة واحدة في اتجاه اليمين (الإزاحة)

تدخل بتة الجديدة إلى السجل و تقوم بالتفاعل مع قيم المسجل (التغذية الخلفية)