การคำนวณเชิงสุ่ม (Stochastic computing)คือชุดของเทคนิคที่ใช้กระแสของบิตสุ่มแทนค่าต่อเนื่อง การคำนวณที่ซับซ้อนสามารถทำได้โดยการดำเนินการแบบบิตต่อบิตอย่างง่ายบนกระแสเหล่านั้น การคำนวณเชิงสุ่มแตกต่างจากการศึกษาเกี่ยวกับอัลกอริทึมแบบสุ่ม

สมมติว่ากำหนดค่า มาให้แล้ว และเราต้องการคำนวณค่าการคำนวณเชิงสุ่มจะดำเนินการนี้โดยใช้ความน่าจะเป็นแทนการคำนวณทางคณิตศาสตร์ ${\displaystyle p,q\in [0,1]}$${\displaystyle p\times q}$

โดยเฉพาะอย่างยิ่ง สมมติว่ามีกระแสบิตสุ่มอิสระสองกระแสที่เรียกว่าจำนวนสุ่ม s (เช่นกระบวนการเบอร์นูลลี ) โดยที่ความน่าจะเป็นของเลข 1 ในกระแสแรกคือและความน่าจะเป็นในกระแสที่สองคือเราสามารถนำการดำเนินการ AND ทางตรรกะ มาใช้ กับกระแสทั้งสองได้ ${\displaystyle p}$${\displaystyle q}$

${\displaystyle a_{i}}$	1	0	1	1	0	1	...
${\displaystyle b_{i}}$	1	1	0	1	1	0	...
${\displaystyle a_{i}\land b_{i}}$	1	0	0	1	0	0	...

ความน่าจะเป็นที่จะได้เลข 1 ในกระแสข้อมูลขาออกคือ. โดยการสังเกตบิตข้อมูลขาออกจำนวนมากพอและวัดความถี่ของเลข 1 จะสามารถประมาณค่าได้ด้วยความแม่นยำในระดับที่ต้องการ ${\displaystyle pq}$${\displaystyle pq}$

การดำเนินการข้างต้นแปลงการคำนวณที่ค่อนข้างซับซ้อน (การคูณของและ) ให้เป็นชุดของการดำเนินการที่ง่ายมาก (การประเมินค่า) บนบิตสุ่ม เพื่อให้เห็นภาพชัดเจนขึ้น สมมติว่าเรามีตารางความจริงของเกต AND การตีความแบบดั้งเดิมคือเอาต์พุตจะเป็นจริงก็ต่อเมื่ออินพุต A และ B เป็นจริงเท่านั้น อย่างไรก็ตาม หากตีความตารางในแนวตั้ง (0011) AND (0101) จะเป็น (0001) นั่นคือ 1/2 x 1/2 = 1/4 ซึ่งเป็นการคูณทางคณิตศาสตร์อย่างแท้จริง เนื่องจากข้อมูลถูกนำเสนอในรูปแบบการแจกแจงความน่าจะเป็นการคูณความน่าจะเป็นจึงเป็นการดำเนินการ AND อย่างแท้จริง ${\displaystyle p}$${\displaystyle q}$${\displaystyle a_{i}\land b_{i}}$

โดยทั่วไปแล้ว การคำนวณเชิงสุ่มจะแสดงตัวเลขในรูปของกระแสบิตสุ่ม และสร้างตัวเลขขึ้นใหม่โดยการคำนวณความถี่ การคำนวณจะดำเนินการกับกระแสบิตเหล่านั้น และแปลงการดำเนินการที่ซับซ้อนบนและให้เป็นการดำเนินการที่เรียบง่ายบนการแสดงกระแสบิต (เนื่องจากวิธีการสร้างใหม่ อุปกรณ์ที่ทำการดำเนินการเหล่านี้บางครั้งเรียกว่าโปรเซสเซอร์เฉลี่ยเชิงสุ่ม) ในแง่สมัยใหม่ การคำนวณเชิงสุ่มสามารถมองได้ว่าเป็นการตีความการคำนวณในแง่ของความน่าจะเป็น ซึ่งจะถูกประเมินด้วยตัวสุ่มแบบกิบส์ นอกจาก นี้ยังสามารถตีความได้ว่าเป็นคอมพิวเตอร์ แบบผสมผสานระหว่าง อนาล็อกและดิจิทัล${\displaystyle p}$${\displaystyle q}$

การคำนวณแบบสุ่มได้รับการแนะนำครั้งแรกในบทความบุกเบิกโดยJohn von Neumannในปี 1953 ^{[ 1 ]}อย่างไรก็ตาม ทฤษฎีนี้ไม่สามารถพัฒนาได้อย่างสมบูรณ์จนกระทั่งความก้าวหน้าในการคำนวณในช่วงทศวรรษ 1960 ^{[ 2 ] [ 3 ]} ส่วนใหญ่ผ่านความพยายามพร้อมกันและแบบขนานในสหรัฐอเมริกา^{[ 4 ]} และสหราชอาณาจักร^{[ 5 ]} ในช่วงปลายทศวรรษ 1960 ความสนใจได้หันไปที่การออกแบบฮาร์ดแวร์เฉพาะทางเพื่อทำการคำนวณแบบสุ่ม เครื่องเหล่านี้จำนวนมาก^{[ 6 ]} ถูกสร้างขึ้นระหว่างปี 1969 ถึง 1974; RASCEL ^{[ 7 ]} ปรากฏอยู่ในบทความนี้

แม้ว่าจะมีความสนใจอย่างมากในช่วงทศวรรษ 1960 และ 1970 แต่การคำนวณแบบสุ่มก็ไม่สามารถแข่งขันกับตรรกะดิจิทัลแบบดั้งเดิมได้ในที่สุด ด้วยเหตุผลที่กล่าวไว้ด้านล่าง การประชุมวิชาการนานาชาติเกี่ยวกับการคำนวณแบบสุ่มครั้งแรก (และครั้งสุดท้าย) ^{[ 8 ]} จัดขึ้นในปี 1978 การวิจัยที่กระตือรือร้นในด้านนี้ลดลงในช่วงไม่กี่ปีถัดมา

แม้ว่าการคำนวณแบบสุ่มจะลดลงในฐานะวิธีการคำนวณทั่วไป แต่ก็แสดงให้เห็นถึงศักยภาพในแอปพลิเคชันหลายอย่าง การวิจัยแบบดั้งเดิมมุ่งเน้นไปที่งานบางอย่างในการเรียนรู้ของเครื่องและการควบคุม^{[ 9 ] [ 10 ]} เมื่อไม่นานมานี้ ความสนใจได้หันไปสู่การถอดรหัสแบบสุ่ม ซึ่งใช้การคำนวณแบบสุ่มในการถอดรหัสรหัสแก้ไขข้อผิดพลาด^{[ 11 ]}เมื่อไม่นานมานี้ วงจรแบบสุ่มได้ถูกนำมาใช้ประสบความสำเร็จใน งาน ประมวลผลภาพเช่นการตรวจจับขอบ^{[ 12 ]}และการกำหนดเกณฑ์ภาพ^{[ 13 ]} ความก้าวหน้าล่าสุดในวงจรแบบสุ่มยังแสดงให้เห็นถึงข้อได้เปรียบด้านความเร็วและประสิทธิภาพการใช้พลังงานที่น่าสนใจใน การเร่งความเร็วฮาร์ดแวร์ปัญญาประดิษฐ์ (AI) บนการประมวลผลแบบเอดจ์

แม้ว่าการคำนวณแบบสุ่ม (stochastic computing) จะล้มเหลวในเชิงประวัติศาสตร์ แต่ก็อาจยังคงมีความเกี่ยวข้องสำหรับการแก้ปัญหาบางอย่าง เพื่อให้เข้าใจว่าเมื่อใดที่การคำนวณแบบสุ่มยังคงมีความเกี่ยวข้อง การเปรียบเทียบการคำนวณแบบสุ่มกับวิธีการคำนวณดิจิทัลแบบดั้งเดิมจึงเป็นสิ่งที่มีประโยชน์

สมมติว่าเราต้องการคูณตัวเลขสองตัวที่มีความแม่นยำระดับบิต โดยใช้ วิธี การคูณแบบยาว ทั่วไป เราจำเป็นต้องดำเนิน การหลายอย่าง แต่ด้วยการคำนวณแบบสุ่ม เราสามารถใช้การดำเนินการ AND กับบิตจำนวนเท่าใดก็ได้ และค่าที่คาดหวังจะถูกต้องเสมอ (อย่างไรก็ตาม หากจำนวนตัวอย่างน้อย ความแปรปรวนจะทำให้ผลลัพธ์ที่แท้จริงไม่แม่นยำอย่างมาก) ${\displaystyle n}$${\displaystyle n^{2}}$

ยิ่งไปกว่านั้น การทำงานพื้นฐานในตัวคูณดิจิทัลคือ วงจรบวกเต็ม (full adder) ในขณะที่คอมพิวเตอร์เชิงสุ่ม (stochastic computer) ต้องการเพียงแค่เกต AND เท่านั้น นอกจากนี้ ตัวคูณดิจิทัลจะต้องการสายอินพุตจำนวนมาก ในขณะที่ตัวคูณเชิงสุ่มต้องการเพียงสายอินพุตสองเส้น (อย่างไรก็ตาม หากตัวคูณดิจิทัลแปลงเอาต์พุตเป็นอนุกรม ก็จะต้องการสายอินพุตเพียงสองเส้นเช่นกัน) ${\displaystyle 2n}$

นอกจากนี้ การคำนวณแบบสุ่มยังมีความทนทานต่อสัญญาณรบกวน หากบิตเพียงไม่กี่บิตในสตรีมเกิดการเปลี่ยนแปลง ข้อผิดพลาดเหล่านั้นจะไม่มีผลกระทบอย่างมีนัยสำคัญต่อผลลัพธ์

นอกจากนี้ องค์ประกอบการคำนวณแบบสุ่มยังสามารถทนต่อความคลาดเคลื่อนของเวลาการมาถึงของอินพุตได้ วงจรทำงานได้อย่างถูกต้องแม้ว่าอินพุตจะไม่ตรงกันตามเวลา ส่งผลให้ระบบแบบสุ่มสามารถออกแบบให้ทำงานโดยใช้สัญญาณนาฬิกาที่สร้างขึ้นในพื้นที่ราคาไม่แพง แทนที่จะใช้สัญญาณนาฬิกาทั่วโลกและเครือข่ายกระจายสัญญาณนาฬิกาที่มีราคาแพง^{[ 14 ]}

ในที่สุด การคำนวณแบบสุ่มจะให้ค่าประมาณของคำตอบที่แม่นยำมากขึ้นเมื่อเราขยายกระแสบิต โดยเฉพาะอย่างยิ่ง จะให้ค่าประมาณคร่าวๆ อย่างรวดเร็ว คุณสมบัตินี้มักเรียกว่าความแม่นยำแบบก้าวหน้าซึ่งบ่งชี้ว่าความแม่นยำของตัวเลขแบบสุ่ม (กระแสบิต) เพิ่มขึ้นเมื่อการคำนวณดำเนินไป ^{[ 15 ]} ราวกับว่าบิตที่มีนัยสำคัญที่สุดของตัวเลขมาถึงก่อนบิตที่มีนัยสำคัญน้อยที่สุดซึ่งแตกต่างจากวงจรเลขคณิต แบบดั้งเดิม ที่บิตที่มีนัยสำคัญที่สุดมักจะมาถึงเป็นลำดับสุดท้าย ในระบบวนซ้ำบางระบบ คำตอบบางส่วนที่ได้จากความแม่นยำแบบก้าวหน้าสามารถให้ผลตอบรับที่เร็วกว่าวิธีการคำนวณแบบดั้งเดิม ซึ่งนำไปสู่การบรรจบกันที่เร็วขึ้น

การคำนวณแบบสุ่มนั้น โดยธรรมชาติแล้วเป็นการสุ่ม เมื่อเราตรวจสอบกระแสบิตแบบสุ่มและพยายามสร้างค่าพื้นฐานขึ้นมาใหม่ ความแม่นยำที่แท้จริงสามารถวัดได้จากความแปรปรวนของตัวอย่างของเรา ในตัวอย่างข้างต้น ตัวคูณดิจิทัลคำนวณตัวเลขด้วยความแม่นยำระดับบิต ดังนั้นความแม่นยำจึงเป็นถ้าเราใช้กระแสบิตแบบสุ่มเพื่อประมาณค่าตัวเลขและต้องการให้ค่าเบี่ยงเบนมาตรฐานของการประมาณค่าคำตอบของเรามีอย่างน้อยเราจะต้องใช้ตัวอย่างจำนวนมาก ซึ่งแสดงถึงการเพิ่มขึ้นของงานแบบทวีคูณ อย่างไรก็ตาม ในบางแอปพลิเคชัน คุณสมบัติความแม่นยำที่เพิ่มขึ้นของการคำนวณแบบสุ่มสามารถนำมาใช้เพื่อชดเชยการสูญเสียแบบทวีคูณนี้ได้ ${\displaystyle 2n}$${\displaystyle 2^{-2n}}$${\displaystyle 2^{-2n}}$${\displaystyle O(2^{4n})}$

ประการที่สอง การคำนวณแบบสุ่ม (stochastic computing) จำเป็นต้องมีวิธีการสร้างกระแสบิตแบบสุ่มที่มีอคติ ในทางปฏิบัติ กระแสเหล่านี้ถูกสร้างขึ้นโดยใช้ ตัวสร้างตัวเลขสุ่ม เทียม (pseudo-random number generators ) น่าเสียดายที่การสร้างบิต (แบบสุ่ม) นั้นมีต้นทุนค่อนข้างสูง (เมื่อเทียบกับค่าใช้จ่ายของวงจรบวกเต็ม (full adder)) ดังนั้น ข้อได้เปรียบในระดับเกตของการคำนวณแบบสุ่มจึงมักจะหายไป

ประการที่สาม การวิเคราะห์การคำนวณแบบสุ่มถือว่ากระแสบิตเป็นอิสระต่อกัน (ไม่สัมพันธ์กัน) หากสมมติฐานนี้ไม่เป็นจริง การคำนวณแบบสุ่มอาจล้มเหลวอย่างมาก ตัวอย่างเช่น หากเราพยายามคำนวณโดยการคูณกระแสบิตด้วย ตัวมันเอง กระบวนการจะล้มเหลว เนื่องจากการคำนวณแบบสุ่มจะให้ผลลัพธ์เป็นซึ่งโดยทั่วไปแล้วจะไม่เป็นจริง (เว้นแต่จะเป็น0 หรือ 1) ในระบบที่มีการป้อนกลับ ปัญหาของการลดความสัมพันธ์อาจแสดงออกมาในรูปแบบที่ซับซ้อนมากขึ้น ระบบของโปรเซสเซอร์แบบสุ่มมีแนวโน้มที่จะเกิด การล็อกซึ่งการป้อนกลับระหว่างส่วนประกอบต่างๆ สามารถทำให้เกิดสถานะติดตายได้^{[ 16 ]} ต้องใช้ความพยายามอย่างมากในการลดความสัมพันธ์ของระบบเพื่อพยายามแก้ไขปัญหาการล็อก ${\displaystyle p^{2}}$${\displaystyle p}$${\displaystyle a_{i}\land a_{i}=a_{i}}$${\displaystyle p\times p=p}$${\displaystyle p=}$

ประการที่สี่ แม้ว่าฟังก์ชันดิจิทัลบางฟังก์ชันจะมีฟังก์ชันสุ่มที่เทียบเคียงได้ง่ายมาก (เช่น การแปลงระหว่างการคูณและเกต AND) แต่หลายฟังก์ชันก็ไม่มี การพยายามแสดงฟังก์ชันเหล่านี้ในรูปแบบสุ่มอาจทำให้เกิดปัญหาต่างๆ มากมาย ตัวอย่างเช่น การถอดรหัสแบบสุ่มต้องคำนวณฟังก์ชันซึ่งไม่มีการดำเนินการบิตเดียวที่สามารถคำนวณฟังก์ชันนี้ได้ วิธีแก้ปัญหาทั่วไปคือการสร้างบิตเอาต์พุตที่สัมพันธ์กัน ซึ่งดังที่เราได้เห็นข้างต้นแล้ว อาจก่อให้เกิดปัญหามากมาย ${\displaystyle f(p,q)\rightarrow pq/(pq+(1-p)(1-q))}$

ฟังก์ชันอื่นๆ (เช่น ตัวดำเนินการหาค่าเฉลี่ย) จำเป็นต้องมีการลดหรือเพิ่มจำนวนข้อมูลในสตรีม การแลกเปลี่ยนระหว่างความแม่นยำและหน่วยความจำอาจเป็นเรื่องท้าทาย ${\displaystyle f(p,q)\rightarrow (p+q)/2}$

แม้ว่าการคำนวณแบบสุ่มจะมีข้อบกพร่องอยู่หลายประการเมื่อพิจารณาว่าเป็นวิธีการคำนวณทั่วไป แต่ก็มีแอปพลิเคชันบางอย่างที่แสดงให้เห็นถึงจุดแข็งของมัน ตัวอย่างที่โดดเด่นอย่างหนึ่งคือการถอดรหัสแก้ไขข้อผิดพลาดบางประเภท

ในการพัฒนาที่ไม่เกี่ยวข้องกับการคำนวณเชิงสุ่ม ได้มีการพัฒนาวิธีการที่มีประสิทธิภาพสูงในการถอดรหัสLDPCโดยใช้ อัลกอริธึม การแพร่กระจายความเชื่อการแพร่กระจายความเชื่อในบริบทนี้เกี่ยวข้องกับการประเมินค่าพารามิเตอร์บางอย่างซ้ำๆ โดยใช้การดำเนินการพื้นฐานสองอย่าง (โดยพื้นฐานแล้วคือการดำเนินการ XOR เชิงความน่าจะเป็นและการดำเนินการหาค่าเฉลี่ย)

ในปี พ.ศ. 2546 นักวิจัยตระหนักว่าการดำเนินการทั้งสองนี้สามารถจำลองได้อย่างง่ายดายด้วยการคำนวณแบบสุ่ม^{[ 17 ]} ยิ่งไปกว่านั้น เนื่องจากอัลกอริธึมการแพร่กระจายความเชื่อเป็นแบบวนซ้ำ การคำนวณแบบสุ่มจึงให้โซลูชันบางส่วนที่อาจนำไปสู่การบรรจบกันที่เร็วขึ้น การใช้งานฮาร์ดแวร์ของตัวถอดรหัสแบบสุ่มได้รับการสร้างขึ้นบนFPGA [ ^{18 ] ผู้} สนับสนุนวิธีการเหล่านี้โต้แย้งว่าประสิทธิภาพของการถอดรหัสแบบสุ่มนั้นสามารถแข่งขันได้กับทางเลือกแบบดิจิทัล

วิธีการเชิงกำหนดของ SC ได้รับการพัฒนาขึ้นเพื่อทำการคำนวณที่แม่นยำอย่างสมบูรณ์ด้วยวงจร SC ^{[ 19 ]}หลักการสำคัญของวิธีการเหล่านี้คือ บิตทุกบิตของบิตสตรีมหนึ่งจะโต้ตอบกับบิตทุกบิตของบิตสตรีมอื่นเพียงครั้งเดียวเท่านั้น เพื่อให้ได้ผลลัพธ์ที่แม่นยำอย่างสมบูรณ์ด้วยวิธีการเหล่านี้ การดำเนินการจะต้องทำงานเป็นเวลาเท่ากับผลคูณของความยาวของบิตสตรีมอินพุต วิธีการเชิงกำหนดได้รับการพัฒนาขึ้นโดยอิงจากบิตสตรีมเอกภาค^{[ 20 ] [ 21 ]}บิตสตรีมแบบสุ่มเทียม^{[ 22 ]}และบิตสตรีมที่มีความคลาดเคลื่อนต่ำ^{[ 23 ]}

มีรูปแบบต่างๆ มากมายของแบบจำลองการคำนวณเชิงสุ่มพื้นฐาน สามารถหาข้อมูลเพิ่มเติมได้ในหนังสืออ้างอิงของ Mars และ Poppelbaum

การประมวลผลแบบกลุ่ม (Bundle Processing)เกี่ยวข้องกับการส่งบิตจำนวนคงที่แทนที่จะส่งเป็นกระแส ข้อดีอย่างหนึ่งของวิธีการนี้คือความแม่นยำที่ดีขึ้น เพื่อให้เข้าใจเหตุผล ลองสมมติว่าเราส่ง บิตจำนวนหนึ่ง ในการคำนวณแบบสุ่มทั่วไป เราสามารถแสดงความแม่นยำได้ค่าที่แตกต่างกันเล็กน้อย เนื่องจากความแปรปรวนของการประมาณค่า ในการประมวลผลแบบกลุ่ม เราสามารถแสดงความแม่นยำได้ค่าหนึ่งอย่างไรก็ตาม การประมวลผลแบบกลุ่มยังคงรักษาความทนทานต่อข้อผิดพลาดเช่นเดียวกับการประมวลผลแบบสุ่มทั่วไป ${\displaystyle s}$${\displaystyle O(1/{\sqrt {s}})}$${\displaystyle 1/s}$

การประมวลผลแบบเออร์โกดิก (Ergodic Processing)เกี่ยวข้องกับการส่งกระแสของชุดข้อมูล ซึ่งเป็นการรวมข้อดีของการประมวลผลแบบสุ่มทั่วไปและการประมวลผลแบบชุดข้อมูลเข้าด้วยกัน

การประมวลผลแบบ Burst Processingจะเข้ารหัสตัวเลขโดยใช้ลำดับฐานที่เพิ่มขึ้นเรื่อยๆ ตัวอย่างเช่น เราจะเข้ารหัส 4.3 ด้วยตัวเลขทศนิยมสิบหลักดังนี้

4444444555

เนื่องจากค่าเฉลี่ยของกระแสข้อมูลก่อนหน้าคือ 4.3 การนำเสนอแบบนี้มีข้อดีหลายประการ: ไม่มีการสุ่มเนื่องจากตัวเลขปรากฏในลำดับที่เพิ่มขึ้น ดังนั้นจึงหลีกเลี่ยงปัญหาของ PRNG ได้ แต่ยังคงรักษาข้อดีหลายประการของการคำนวณแบบสุ่ม (เช่น การประมาณค่าบางส่วนของคำตอบ) นอกจากนี้ ยังคงรักษาความแม่นยำเชิงเส้นของการประมวลผลแบบกลุ่มและแบบเออร์โกดิกไว้ได้

• การคำนวณแบบไม่ธรรมดา

• Gaines, Brian R. (1967). "เทคนิคการระบุตัวตนด้วยคอมพิวเตอร์เชิงสุ่ม" (PDF) . รายงานการประชุมสัมมนา IFAC เรื่อง "ปัญหาของการระบุตัวตนในระบบควบคุมอัตโนมัติ" ส่วนที่ 6 เครื่องมือระบุตัวตนพิเศษ กรุงปราก 12-19 มิถุนายน 1967 . สืบค้นเมื่อ 11 พฤศจิกายน 2013 .
• Alaghi, Armin; Hayes, John P. (2013). "การสำรวจการคำนวณเชิงสุ่ม" (PDF) . ACM Transactions on Embedded Computing Systems . 12 (2s): 1– 19. CiteSeerX  10.1.1.296.4448 . doi : 10.1145/2465787.2465794 . S2CID  4689958 . สืบค้นเมื่อ2013-11-11 .