چگونه اعداد تصادفی واقعا تصادفی بسازیم!؟

ساخت اعداد تصادفی

شاید برای شما هم پیش آمده باشد که برای ساخت یک بازی یا الگوریتم رمزگذاری یا هر منظور دیگری نیاز به ساخت اعداد تصادفی داشته باشید!

ممکن است فکر کنید که ساخت یک عدد تصادفی کار زیاد پیچیده‌ای نیست و با صدازدن یک تابع Rand یا تابعی مشابه آن، کار تمام می‌شود. اما عدد تولیدشده با این روش چقدر تصادفی است؟ آیا نتیجه قابل تکرار نیست؟ در این مقاله قصد داریم این موضوع را مورد کنکاش قرار دهیم.

چرا نمی توان اعداد تصادفی را واقعا تصادفی نامید؟

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

int main(void)
{
int i = 0;
srand ( time(NULL) );
for(i=0;i<10;i++)
printf("%i\t",rand());
return 0;
}

در برنامه فوق ما قصد داشتیم که ۱۰ عدد تصادفی ایجاد کنیم و نتیجه را نمایش دهیم. برای این کار از یک حلقه استفاده می‌کنیم که ۱۰ بار تابع rand را فراخوانی کند و نتیجه را نمایش دهد. به نظر توالی اعداد تولیدشده اتفاقی هستند. البته در نظر داشته باشید این توالی تا وقتی اتفاقی است که ما از الگوریتم تولید آنها اطلاع نداشته باشیم. وقتی الگوریتم را مطالعه کنیم و روش عملکرد آن را دربیابیم با داشتن یکی از اعداد می‌توانیم عدد بعدی و حتی قبلی را حدس بزنیم! در این مرحله این مسئله را نادیده می‌گیریم.

24464 26962 29358 11478 15724 19169 26500 6334 18467 41

انتظار داریم که با هر بار اجرای برنامه ده عدد کاملاً اتفاقی داشته باشیم؛ اما هر بار که برنامه را اجرا می‌کنیم، همین ده عدد نمایش داده می‌شوند. (ممکن است برای شما ده عدد دیگر باشد ولی نتیجه تکرارپذیر است.) یعنی اعداد واقعاً تصادفی نیستند و توسط الگوریتمی ایجاده شده‌اند که هیچ پارامتر متغیری نداشته است. برای رفع این نقص، تابعی وجود دارد به نام srand که با دریافت یک عدد، اعداد تصادفی را از آن نقطه شروع خواهد کرد. به این معنی که اگر در هر بار اجرای برنامه، ما یک عدد تصادفی (که خود ساخت این عدد نیز مسئله‌ساز است.) به این تابع بدهیم، خروجی نیز اعداد تصادفی است! ازآنجایی‌که در شروع برنامه اعداد تصادفی‌ای در کار نیست، ما برای این‌که هر بار اجرای برنامه نتیجه‌ای متفاوت در بر داشته باشد، زمان را به‌عنوان ورودی این تابع در نظر می‌گیریم. این کار به نظر منطقی می‌رسد. هر بار که برنامه را اجرا می‌کنیم، با توجه به زمان اجرای برنامه، نتیجه‌ای متفاوت خواهیم داشت.

int main(void)
{
int i = 0;
srand ( time(NULL) );
for(i=0;i<10;i++)
printf("%i\t",rand());
return 0;
}

چرا در سیستم‌های میکروکنترلری وضع حاد‌تر است؟

معمولاً در سیستم‌های مبتنی بر میکروکنترلر، زمان واقعی (RTC) وجود ندارد و زمان سیستم معمولاً از زمان روشن شدن دستگاه سنجیده می‌شود. خود این مسئله باعث می‌شود که عملاً تابع srand بی‌استفاده شود؛ چراکه مثلاً همیشه در زمان خاصی از اجرای برنامه فراخوانی می‌شود و همیشه یک مقدار خاص به آن داده می‌شود. برای روشن شدن مسئله، برنامه بالا را برای سخت‌افزار آردوینو بازنویسی می‌کنیم.

void setup() {
// put your setup code here, to run once:
Serial.begin(9600);
srand(millis());

for(int i=0;i<10;i++)
Serial.println(rand());
}

void loop() {
// put your main code here, to run repeatedly:

}

همان‌طور که مشاهده می‌کنید با هر بار اجرای برنامه (ریست کردن یا خاموش و روشن کردن) برنامه خروجی یکسانی را نمایش می‌دهد. البته لازم به ذکر است که اگر در سیستم از RTC استفاده شود، مقداری وضع بهبود پیدا می‌کند و حدس زدن خروجی سخت‌تر خواهد شد. اما باز به معنی واقعیِ کلمه، اعداد تولیدشده تصادفی نخواهند بود.

برای تصادفی بودن یک دنباله از اعداد، باید دو شرط وجود داشته باشد؛

• دنباله تکرارپذیر نباشد.
• اعداد تولیدشده قابل حدس زدن نباشند.

راه‌حل تولید اعداد تصادفی واقعی چیست؟

اما راه‌حل اساسی برای تولید اعداد واقعاً تصادفی چیست؟ همان‌طور که گفته شد اعداد تصادفی وقتی به مفهوم واقعی خود نزدیک‌تر می‌شوند که غیرقابل‌پیش‌بینی و تکرارناپذیر باشند. اگر پایه تولید اعداد تصادفی را میزان تجمع نوع خاصی از باکتری بر روی یک سطح انتخاب کنیم، اعداد تولیدشده با این روش به‌راحتی قابل پیش‌بینی نیستند؛ چراکه عوامل متغیر زیادی در میزان رشد آن نوع خاص از باکتری وجود خواهد داشت. به‌عنوان‌مثال: دمای هوا، میزان نور، میزان رطوبت، میزان وجود نوع دیگری از باکتری و… . به همین دلیل حدس این‌که در یک زمان خاص چه مقدار باکتری بر روی سطح موردنظر ما تجمع کرده است عملاً امری غیرممکن خواهد بود و می‌توان تا حدود زیادی گفت که عدد به‌دست‌آمده عددی است تصادفی! نمونه فوق فقط یک مثال برای نشان دادن این مسئله بود که با زیاد کردن پارامترهای دخیل در تولید یک عدد تصادفی، می‌توان به همان نسبت حدس زدن عدد تولیدشده را دشوارتر کرد.

روش‌های متفاوتی برای تولید اعداد تصادفی با استفاده از اصول ذکرشده وجود دارد. اما روش‌هایی که چندان پیچیده نباشند و بتوان به‌راحتی آن‌ها را پیاده‌سازی کرد محدود هستند. ما در این مقاله قصد داریم تا برای تولید اعداد تصادفی از نویز سفید (White Noise) استفاده کنیم. از نظر فیزیکدانان نویز سفید سیگنالی تصادفی است که تراکم طیفی ثابتی دارد. اگر بخواهیم به شکل ساده‌تر مسئله را بیان کنیم باید بگوییم که مثلاً گوش ما انسان‌ها، معمولاً محدوده‌ی فرکانس ۲۰ هرتز تا ۲۰ هزار هرتز را می‌شنود. اگر یک دستگاه صوتی بخواهد نویز سفید برای گوش ما تولید کند، باید توان امواجی که از آن در محدوده فرکانسی ۲۰ تا ۴۰ هرتز ساطع می‌شود، با توان امواجی که مثلاً در محدوده فرکانسی ۱۰۰۰۰ و ۱۰۰۲۰ ساطع می‌شود، برابر باشد. صدای اقیانوس نیز نویز سفید است.

چگونه نویز سفید بسازیم؟

یکی از ساده‌ترین روش‌های تولید نویز سفید، استفاده از دیود به‌صورت بایاس معکوس هست. همان‌طور که می‌دانید دیود از پیوند N و P تشکیل شده است. وقتی‌که دیود را به‌صورت معکوس در مدار قرار می‌دهیم، پیوند PN گسترش می‌یابد و میزان جریان کمی برقرار می‌شود که به این جریان، جریان نشتی می‌گویند. این جریان با توجه به ماهیت دیود و پیوند PN دارای نویز سفید است. بر همین اساس برای تولید نویز سفید می‌توان از مدار زیر استفاده کرد:

اگر خروجی مدار فوق را به یک تقویت‌کننده صوتی وصل کنیم، صدای نویز سفید را خواهیم شنید. برای تقویت دامنه و تصحیح امپدانس مدار می‌توان خروجی مدار را به یک تقویت‌کننده عملیاتی (Opamp) وصل کرد. مدار نهایی به شکل زیر خواهد بود:

چگونه می‌توانم از ژنراتور نویز سفید استفاده کنم؟

می‌توان خروجی مدار فوق را به ورودی آنالوگ میکروکنترلر و یا حتی به کارت صوتی کامپیوتر وصل کرد! نمونه‌های به‌دست‌آمده از این روش کاملاً تصادفی هستند و به‌هیچ‌وجه نمی‌توان نتیجه اعداد تولیدشده را تکرار کرد. در برنامه زیر برای ایجاد یک عدد تصادفی از نویز سفید و ADC به کمک توابع Rand و Srand استفاده شده است.

int adc_pin = 0;

void setup(){

Serial.begin(9600); 
}

void loop()
{

int adc_value = analogRead(adc_pin);
srand(adc_value);
Serial.println(rand());
delay(1000);
}

بررسی نتایج

خروجیِ دیجیتال مدار رندم ژنراتور را برای مدت ۱۵ ساعت با نرخ نمونه‌برداری ۵۰۰ میکروثانیه ذخیره و موردبررسی قراردادیم که نتایج زیر به‌دست آمد:

اگر هر بیت را یک پیکسل فرض کنیم و داده‌های ذخیره‌شده را به‌صورت یک عکس آشکار کنیم، تصویر زیر به‌دست خواهد آمد که شباهت زیادی به تصویر برفکی تلویزیون‌ها دارد.

نمودار پراکندگی داده‌های موجود:

منبع: سیسوگ