مرجع
آخر الزيارات

مولد أعداد شبه عشوائية

441 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: مولد أعداد شبه عشوائية هو خوارزمية تولد متتالية من الأعداد تقترب من خصائص الأعداد العشوائية. تتناول المقالة قسمين هما «سجل إزاحة ذو تغذية خلفية خطية» و«تخرج بتة جديدة من أحد طرفي السجل».
المحتويات
  1. سجل إزاحة ذو تغذية خلفية خطية
  2. تخرج بتة جديدة من أحد طرفي السجل

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

أمثلة عن مولدات شبه عشوائية

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

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

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

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

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

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

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

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

طول السجل n: وهو عدد البتّات المخزّنة في السجل.

ومن جهة أخرى، بذرة غير صفرية (Non-zero seed): وهي الحالة الابتدائية للسجل. ويُشترط أن لا تكون صفرا بالكامل، لأن حالة الصفر الكامل في LFSR (بشكله القياسي) تؤدي إلى “انحباس” السجل في الصفر وعدم توليد تسلسلا مفيدا.

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

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

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

  • انظر كذلك
  • توليد الأعداد العشوائية
  • عشاوة

ومن جهة أخرى، يُسمّى هذا النوع من سجلات LFSR سجلّ إزاحة ذو تغذية راجعة خطية بصيغة غالوا (Galois-form LFSR). يُعرَّف سجل غالوا عادةً بواسطة أربع مواصفات أساسية:

من جهة ثانية، كثير حدود التغذية الخلفية: (Feedback polynomial): وهو الذي يحدّد “نقاط” أو “مواضع” التغذية الراجعة (Feedback Taps). وغالبًا يُختار كثير حدود أولي/بدائي (Primitive) إذا كان الهدف الحصول على دورة قصوى، أي المرور بأكبر عدد ممكن من الحالات مثل .

من جهة ثانية، اتجاه الإزاحة (Shift direction): هل يتم الإزاحة يمينًا أم يسارًا، وأي طرف يُعتبر بتّ الخرج. هذا مهم لأن ترقيم البتّات وتحديد المواضع يعتمد عليه.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.