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

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

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

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

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

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

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

# تخرج بتة جديدة من أحد طرفي السجل
# تنزاح جميع البتات خانة واحدة في اتجاه اليمين (الإزاحة)
# تدخل بتة الجديدة إلى السجل و تقوم بالتفاعل مع قيم المسجل (التغذية الخلفية)

## الخصائص
تصغير|350x350بك|سجّل إزاحة ذو تغذية خلفية خطية من نوع بطول 16 بت. بعد كل خطوة يتم تغذية السجل بناتج عملية أو القاصرة (xor) على البتات 11 و 13 و 14 و 16.
وبما أن عمل السجّل حتمي، فإن تسلسل القيم الناتج عنه يتحدد بالكامل بحالته الأولية. ولأن للسجّل عددًا محدودًا من الحالات الممكنة، فإنه سيدخل في نهاية المطاف في دورة تكرارية. ومع ذلك، إذا اختيرت دالة التغذية الراجعة بعناية، يمكن إنتاج تسلسل بتات يبدو عشوائيًا وله دورة طويلة جدًا.
يُسمّى هذا النوع من سجلات LFSR سجلّ إزاحة ذو تغذية راجعة خطية بصيغة غالوا (Galois-form LFSR). يُعرَّف سجل غالوا عادةً بواسطة أربع مواصفات أساسية:

# طول السجل n: وهو عدد البتّات المخزّنة في السجل.
# كثير حدود التغذية الخلفية: (Feedback polynomial): وهو الذي يحدّد “نقاط” أو “مواضع” التغذية الراجعة (Feedback Taps). وغالبًا يُختار كثير حدود أولي/بدائي (Primitive) إذا كان الهدف الحصول على دورة قصوى، أي المرور بأكبر عدد ممكن من الحالات مثل p(x) = x^4 + x + 1.
# اتجاه الإزاحة (Shift direction): هل يتم الإزاحة يمينًا أم يسارًا، وأي طرف يُعتبر بتّ الخرج. هذا مهم لأن ترقيم البتّات وتحديد المواضع يعتمد عليه.
# بذرة غير صفرية (Non-zero seed): تُسمّى القيمة الابتدائية للمسجّل البذرة (Seed)، وهي الحالة الابتدائية للسجل. ويُشترط أن لا تكون صفرا بالكامل، لأن حالة الصفر الكامل في LFSR (بشكله القياسي) تؤدي إلى “انحباس” السجل في الصفر وعدم توليد تسلسلا مفيدا.

اعتمادًا على هذه المواصفات يمكن بناء سجل غالوا، ثم تشغيله خطوةً بعد خطوة لتوليد سلسلة شبه عشوائية (Pseudo-random sequence) من البتّات.

**الحصول على دورة قصوى:** يتحقق طول دورة أعظمي عندما يُختار كثير حدود تغذية خلفية بدائي (Primitive polynomial) من حقل غالوا GF(2) مع بذرة غير صفرية، عندها يكون طول الدورة 2^n - 1 لسجل بطول n بتا.

## مراجع

تصنيف:حسابيات ثنائية
تصنيف:سجلات رقمية
تصنيف:خوارزميات تعمية
تصنيف:مولدات أعداد عشوائية