سجل إزاحة ذو تغذية خلفية خطية
بدايةً، في مجال الحوسبة، يُعدّ سجل الإزاحة ذو التغذية الخلفية الخطية (LFSR) سجل إزاحة تكون بتّاته المدخلة دالة خطية لحالته السابقة. وفيما يلي تفاصيل أوسع عن ذلك.
علاوةً على ذلك، الدالة الخطية الأكثر شيوعًا للبتات المفردة هي عملية XOR (الجمع الحصري أو). لذا، غالبًا ما يكون سجل الإزاحة ذو التغذية الراجعة الخطية سجل إزاحة تُغذّى بتّاته المدخلة بعملية XOR لبعض بتات قيمة مسجل الإزاحة الكلية.
من جانب آخر، بشكل مبسط، يمكن تخيّل سجل الإزاحة على أنه صفّ من البتات. عند كل خطوة زمنية:
ومن جهة أخرى، تُسمى القيمة الابتدائية لسجل الإزاحة ذو التغذية الراجعة الخطية بالبذرة، ولأنّ عمل السجل حتمي، فإنّ سلسلة القيم التي ينتجها السجل تتحدد كليًا بحالته الحالية (أو السابقة). وبالمثل، ولأنّ للسجل عددًا محدودًا من الحالات الممكنة، فلا بدّ أن يدخل في دورة متكررة. مع ذلك، يمكن لسجل الإزاحة ذو التغذية الراجعة الخطية، مع دالة تغذية راجعة مُختارة بعناية، أن ينتج سلسلة من البتات تبدو عشوائية ولها دورة طويلة جدًا.
من جانب آخر، تتشابه الرياضيات المستعملة في فحص التكرار الدوري، والذي يُستعمل للتحقق السريع من أخطاء الإرسال، تشابهًا وثيقًا مع رياضيات مسجل الإزاحة ذي التغذية الخطية الخطية (LFSR). وبشكل عام، فإن العمليات الحسابية الكامنة وراء سجلات الإزاحة ذات التغذية الخطية الخطية تجعلها سهلة الدراسة والتطبيق. إذ يُمكن إنشاء دوائر منطقية معقدة نسبيًا باستخدام وحدات بناء بسيطة. مع ذلك، ينبغي كذلك النظر في طرق أخرى أقل أناقة ولكنها ذات أداء أفضل.
في هذا الإطار، تشمل تطبيقات سجلات الإزاحة ذات التغذية الراجعة الخطية توليد أرقام شبه عشوائية، وسلاسل ضوضاء شبه عشوائية، وعدادات رقمية سريعة، وسلاسل تبييض. وتُعدّ تطبيقات سجلات الإزاحة ذات التغذية الراجعة الخطية شائعة في كلٍّ من الأجهزة والبرامج.
تخرج بتة جديدة من أحد طرفي السجل
تنزاح جميع البتات خانة واحدة في اتجاه اليمين (الإزاحة)
كذلك، تدخل بتة الجديدة إلى السجل و تقوم بالتفاعل مع قيم المسجل (التغذية الخلفية)
الخصائص
كذلك، بذرة غير صفرية (Non-zero seed): تُسمّى القيمة الابتدائية للمسجّل البذرة (Seed)، وهي الحالة الابتدائية للسجل. ويُشترط أن لا تكون صفرا بالكامل، لأن حالة الصفر الكامل في LFSR (بشكله القياسي) تؤدي إلى “انحباس” السجل في الصفر وعدم توليد تسلسلا مفيدا.
من جانب آخر، كثير حدود التغذية الخلفية: (Feedback polynomial): وهو الذي يحدّد “نقاط” أو “مواضع” التغذية الراجعة (Feedback Taps). وغالبًا يُختار كثير حدود أولي/بدائي (Primitive) إذا كان الهدف الحصول على دورة قصوى، أي المرور بأكبر عدد ممكن من الحالات مثل .
وعلى صعيد آخر، الحصول على دورة قصوى: يتحقق طول دورة أعظمي عندما يُختار كثير حدود تغذية خلفية بدائي (Primitive polynomial) من حقل غالوا GF(2) مع بذرة غير صفرية، عندها يكون طول الدورة لسجل بطول بتا.
كذلك، يُسمّى هذا النوع من سجلات LFSR سجلّ إزاحة ذو تغذية راجعة خطية بصيغة غالوا (Galois-form LFSR). يُعرَّف سجل غالوا عادةً بواسطة أربع مواصفات أساسية:
ومن جهة أخرى، اعتمادًا على هذه المواصفات يمكن بناء سجل غالوا، ثم تشغيله خطوةً بعد خطوة لتوليد سلسلة شبه عشوائية (Pseudo-random sequence) من البتّات.
من جانب آخر، اتجاه الإزاحة (Shift direction): هل يتم الإزاحة يمينًا أم يسارًا، وأي طرف يُعتبر بتّ الخرج. هذا مهم لأن ترقيم البتّات وتحديد المواضع يعتمد عليه.
إضافةً إلى ذلك، وبما أن عمل السجّل حتمي، فإن تسلسل القيم الناتج عنه يتحدد بالكامل بحالته الأولية. ولأن للسجّل عددًا محدودًا من الحالات الممكنة، فإنه سيدخل في نهاية المطاف في دورة تكرارية. ومع ذلك، إذا اختيرت دالة التغذية الراجعة بعناية، يمكن إنتاج تسلسل بتات يبدو عشوائيًا وله دورة طويلة جدًا.
طول السجل n: وهو عدد البتّات المخزّنة في السجل.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟