موضوع مقاله: محاسبات تصادفی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # محاسبات تصادفی | مقدمه: محاسبات تصادفی مجموعه ای از تکنیک هاست که مقادیر پیوسته را توسط جریان بیت های تصادفی نشان می دهد. | ## بخش 1: محاسبات تصادفی | البته باید توجه داشت که محاسبات تصادفی از مطالعه الگوریتم های تصادفی متمایز است. به طور خاص، فرض کنید که دو جریان بیت تصادفی و مستقل به نام اعداد تصادفی (یعنی فرآیندهای برنولی) وجود دارد، که در آن احتمال در جریان اول برابر است با و احتمال در جریان دوم است. با مشاهده تعداد کافی بیت خروجی و اندازه گیری فراوانی عدد 1، می توان را با دقت دلخواه تخمین زد. عملیات فوق یک محاسبه نسبتاً پیچیده را به یک سری عملیات بسیار ساده (ارزیابی ) بر روی بیت های تصادفی تبدیل می کند. از دیدگاه دیگر، با فرض جدول درستی یک دروازه AND، تفسیر متداول این است که خروجی تنها در صورتی درست است که ورودی های A و B درست باشند. با این حال، اگر جدول را به صورت عمودی تفسیر کنیم، (0011) AND (0101) برابر با (0001) است، یعنی 1/2 × 1/2 = 1/4، که دقیقاً یک ضرب حسابی است. از آنجایی که اطلاعات به صورت توزیع احتمال ارائه می شود، ضرب احتمال به معنای واقعی کلمه یک عمل AND است. +OUTBA000010001111 تاریخچه محاسبات تصادفی برای اولین بار در سال 1953 توسط جان فون نویمان در یک مقاله پیشگامانه معرفی شد. با این حال، این نظریه تا پیشرفت‌های محاسباتی دهه 1960 نتوانست به طور کامل توسعه یابد، که عمدتاً از طریق مجموعه‌ای از تلاش‌های همزمان و موازی در ایالات متحده و بریتانیا انجام شد. تا اواخر دهه 1960، توجه به طراحی سخت‌افزارهای ویژه برای انجام محاسبات تصادفی معطوف شد. بسیاری از این ماشین‌ها بین سال‌های 1969 و 1974 ساخته شدند؛ RASCEL در این مقاله به تصویر کشیده شده است. علیرغم علاقه شدید در دهه‌های 1960 و 1970، محاسبات تصادفی در نهایت نتوانست با منطق دیجیتال سنتی رقابت کند، به دلایلی که در زیر توضیح داده شده است. اولین (و آخرین) سمپوزیوم بین‌المللی محاسبات تصادفی در سال 1978 برگزار شد؛ تحقیقات فعال در این زمینه در چند سال آینده کاهش یافت. اگرچه محاسبات تصادفی به عنوان یک روش کلی محاسبات کاهش یافت، اما در چندین کاربرد نویدبخش بوده است. اخیراً، علاقه به رمزگشایی تصادفی معطوف شده است که محاسبات تصادفی را برای رمزگشایی کدهای تصحیح خطا اعمال می‌کند. اخیراً، مدارهای تصادفی با موفقیت در وظایف پردازش تصویر مانند تشخیص لبه و آستانه‌گذاری تصویر استفاده شده‌اند. پیشرفت اخیر در مدارهای تصادفی همچنین مزایای سرعت و کارایی انرژی امیدوارکننده‌ای را در شتاب‌دهنده‌های سخت‌افزاری هوش مصنوعی (AI) در محاسبات لبه نشان می‌دهد. نقاط قوت و ضعف اگرچه محاسبات تصادفی در گذشته شکست خورده است، اما ممکن است همچنان برای حل برخی مشکلات مرتبط باشد. برای درک اینکه چه زمانی مرتبط است، مقایسه محاسبات تصادفی با روش‌های سنتی‌تر محاسبات دیجیتال مفید است. | ## بخش 2: محاسبات تصادفی | با محاسبات تصادفی، می‌توانیم هر تعداد بیت را با هم AND کنیم و مقدار مورد انتظار همیشه صحیح خواهد بود. علاوه بر این، عملیات‌های زیربنایی در یک ضرب‌کننده دیجیتال جمع‌کننده‌های کامل هستند، در حالی که یک کامپیوتر تصادفی فقط به یک دروازه AND نیاز دارد. علاوه بر این، یک ضرب‌کننده دیجیتال به طور ساده به 2n سیم ورودی نیاز دارد، در حالی که یک ضرب‌کننده تصادفی فقط به دو سیم ورودی نیاز دارد. (اگر ضرب‌کننده دیجیتال خروجی خود را سریال کند، در این صورت نیز فقط به دو سیم ورودی نیاز دارد.) علاوه بر این، محاسبات تصادفی در برابر نویز مقاوم است؛ اگر چند بیت در یک جریان تغییر کنند، این خطاها تأثیر قابل توجهی بر راه حل نخواهند داشت. علاوه بر این، عناصر محاسبات تصادفی می‌توانند تاخیر در زمان ورود ورودی‌ها را تحمل کنند. در نتیجه، سیستم‌های تصادفی می‌توانند برای کار با ساعت‌های محلی ارزان‌قیمت تولید شده به جای استفاده از یک ساعت جهانی و یک شبکه توزیع ساعت گران‌قیمت طراحی شوند. در نهایت، محاسبات تصادفی برآوردی از راه‌حل ارائه می‌دهد که با افزایش جریان بیت دقیق‌تر می‌شود. این ویژگی معمولاً به عنوان دقت تدریجی شناخته می‌شود، که نشان می‌دهد دقت اعداد تصادفی (جریان‌های بیت) با پیشرفت محاسبات افزایش می‌یابد. این مانند این است که مهم‌ترین بیت‌های عدد قبل از کم‌اهمیت‌ترین بیت‌های آن می‌رسند؛ برخلاف مدارهای حسابی متداول که مهم‌ترین بیت‌ها معمولاً آخرین بار می‌رسند. در برخی از سیستم‌های تکراری، راه‌حل‌های جزئی به دست آمده از طریق دقت تدریجی می‌توانند بازخورد سریع‌تری نسبت به روش‌های محاسبات سنتی ارائه دهند و منجر به همگرایی سریع‌تر شوند. وقتی یک جریان بیت تصادفی را بررسی می‌کنیم و سعی می‌کنیم مقدار زیربنایی را بازسازی کنیم، دقت موثر را می‌توان با واریانس نمونه اندازه‌گیری کرد. در مثال بالا، ضرب‌کننده دیجیتال عددی را با دقت بیت محاسبه می‌کند، بنابراین دقت است. اگر از یک جریان بیت تصادفی برای تخمین یک عدد استفاده می‌کنیم و می‌خواهیم انحراف استاندارد تخمین ما از راه‌حل حداقل باشد، به نمونه نیاز خواهیم داشت. با این حال، در برخی از کاربردها، می‌توان از ویژگی دقت تدریجی محاسبات تصادفی برای جبران این کاهش نمایی استفاده کرد. نقطه ضعف دوم این است که ، محاسبات تصادفی به روشی برای تولید جریان‌های بیت تصادفی بایاس نیاز دارد. متأسفانه، تولید بیت‌های (شبه-)تصادفی نسبتاً پرهزینه است (در مقایسه با هزینه، مثلاً یک جمع‌کننده کامل). سوم: تحلیل محاسبات تصادفی فرض می‌کند که جریان‌های بیت مستقل (بدون همبستگی) هستند. برای مثال، اگر سعی کنیم را با ضرب یک جریان بیت برای در خودش محاسبه کنیم، این فرآیند شکست می‌خورد: از آنجایی که، محاسبات تصادفی را به دست می‌دهد که به طور کلی درست نیست (مگر اینکه =0 یا 1 باشد). سیستم‌های پردازنده‌های تصادفی مستعد قفل شدن هستند، جایی که بازخورد بین اجزای مختلف می‌تواند به حالت قفل شده دست یابد. | ## بخش 3: محاسبات تصادفی | برای تلاش برای اصلاح قفل شدن، باید تلاش زیادی برای از همبستگی خارج کردن سیستم صرف شود. چهارم: اگرچه برخی از توابع دیجیتال دارای همتایان تصادفی بسیار ساده‌ای هستند (مانند ترجمه بین ضرب و دروازه AND)، بسیاری از آنها اینطور نیستند. تلاش برای بیان این توابع به صورت تصادفی می‌تواند باعث ایجاد آسیب‌شناسی‌های مختلف شود. هیچ عمل بیت واحدی وجود ندارد که بتواند این تابع را محاسبه کند؛ راه حل معمول شامل تولید بیت‌های خروجی همبسته است که همانطور که در بالا دیدیم، می‌تواند باعث ایجاد مشکلات زیادی شود. در توابع دیگر (مانند عملگر میانگین‌گیری که نیاز به کاهش یا افزایش نمونه‌برداری جریان دارند. رمزگشایی تصادفی اگرچه محاسبات تصادفی به عنوان یک روش محاسبات عمومی دارای برخی محدودیت‌ها است، اما در برخی کاربردها نقاط قوت خود را نشان می‌دهد. در توسعه‌های مرتبط با محاسبات تصادفی، روش‌های بسیار کارآمدی برای رمزگشایی کدهای LDPC با استفاده از الگوریتم انتشار باور توسعه یافتند. انتشار باور در این زمینه شامل تخمین مجدد تکراری برخی پارامترها با استفاده از دو عملیات اساسی است (در اصل، یک عملیات XOR احتمالی و یک عملیات میانگین‌گیری). در سال 2003، محققان متوجه شدند که این دو عملیات را می‌توان به سادگی با محاسبات تصادفی مدل‌سازی کرد. علاوه بر این، از آنجایی که الگوریتم انتشار باور تکراری است، محاسبات تصادفی راه‌حل‌های جزئی ارائه می‌دهد که می‌تواند به همگرایی سریع‌تر منجر شود. طرفداران این روش‌ها استدلال می‌کنند که عملکرد رمزگشایی تصادفی با جایگزین‌های دیجیتال رقابت می‌کند. روش‌های قطعی برای محاسبات تصادفی روش‌های قطعی SC برای انجام محاسبات کاملاً دقیق با مدارهای SC توسعه یافته‌اند. اصل اساسی این روش‌ها این است که هر بیت از یک جریان بیت دقیقاً یک بار با هر بیت از جریان بیت‌های دیگر تعامل می‌کند. برای تولید نتیجه کاملاً دقیق با این روش‌ها، عملیات باید برای حاصلضرب طول جریان‌های بیت ورودی اجرا شود. روش‌های قطعی بر اساس جریان‌های بیت یکتایی، جریان‌های بیت شبه‌تصادفی و جریان‌های بیت کم‌اختلاف توسعه یافته‌اند. در محاسبات تصادفی معمولی، به دلیل واریانس تخمین، می‌توانیم دقت تقریباً مقدار مختلف را نشان دهیم. با این حال، پردازش بسته‌ای همان پایداری خطای پردازش تصادفی معمولی را حفظ می‌کند. پردازش ارگودیک شامل ارسال جریانی از بسته‌ها است که مزایای پردازش تصادفی و بسته‌ای معمولی را به همراه دارد. به عنوان مثال، عدد 4.3 را با ده رقم اعشار به صورت زیر کدگذاری می‌کنیم: 4444444555 زیرا میانگین مقدار جریان قبلی 4.3 است. | ## جمع‌بندی | این نمایش مزایای مختلفی دارد: هیچ تصادفی‌سازی وجود ندارد زیرا اعداد به ترتیب صعودی ظاهر می‌شوند، بنابراین مسائل PRNG از بین می‌روند، اما بسیاری از مزایای محاسبات تصادفی حفظ می‌شوند (مانند تخمین‌های جزئی از راه‌حل).