คำนิยาม

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

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

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

ปัจจัยหลักที่ควรพิจารณาในการสร้างแบบทดสอบ ได้แก่:

1. เวลาที่ใช้ในการสร้างชุดทดสอบขั้นต่ำ;
2. ขนาดของอุปกรณ์ต้นแบบ หรือระบบฮาร์ดแวร์/ซอฟต์แวร์ที่จำเป็นในการจำลองอุปกรณ์ที่กำลังทดสอบอย่างเหมาะสม
3. ขอบเขตของกระบวนการตรวจสอบนั้นเอง;
4. เวลาที่ใช้ในการโหลดตัวอย่างทดสอบ และ
5. อุปกรณ์ภายนอกที่จำเป็น (ถ้ามี)

ตัวอย่างของวิธีการอัลกอริทึม ATPG ที่ใช้กันอย่างแพร่หลายในปัจจุบัน ได้แก่D-Algorithm, PODEM และ FANการสร้างรูปแบบโดยใช้อัลกอริทึมเหล่านี้จำเป็นต้องมีสิ่งที่เรียกว่า 'การทำให้ไวต่อเส้นทาง' การทำให้ไวต่อเส้นทางหมายถึงการค้นหาเส้นทางในวงจรที่อนุญาตให้ข้อผิดพลาดปรากฏที่เอาต์พุตที่สังเกตได้ของอุปกรณ์หากเส้นทางนั้นล้มเหลว ตัวอย่างเช่น ในเกต AND สองอินพุต การทำให้ไวต่อเส้นทางของอินพุตหนึ่งต้องการให้อินพุตอีกตัวหนึ่งถูกตั้งค่าเป็น '1'

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

กระบวนการสร้างต้นแบบอัลกอริทึมโดยพื้นฐานแล้วประกอบด้วยขั้นตอนดังต่อไปนี้:

1. เลือกข้อผิดพลาด หรือเลือกข้อผิดพลาดที่ต้องการตรวจจับ;
2. การกำหนดค่าเริ่มต้น หรือการค้นหารูปแบบอินพุต จะกำหนดค่า D หรือ D' ที่เอาต์พุตของพอร์ตที่ผิดพลาด
3. ขับเคลื่อนไปข้างหน้า หรือขับเคลื่อน D หรือ D' ไปสู่เอาต์พุตที่สังเกตได้โดยใช้เส้นทางที่สั้นที่สุดเท่าที่จะเป็นไปได้
4. ปรับค่า หรือกำหนดค่าให้กับอินพุตที่ยังไม่ได้กำหนดค่าอื่นๆ เพื่อปรับค่าที่กำหนดไว้ในระหว่างการปรับค่าล่วงหน้า

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

อัลกอริทึม D ถูกพัฒนาโดย Roth ที่ IBM ในปี 1966 และเป็นอัลกอริทึมตรวจสอบข้อผิดพลาดแบบจำลอง "สมบูรณ์" ตัวแรกที่ออกแบบมาให้สามารถตั้งโปรแกรมบนคอมพิวเตอร์ได้ อัลกอริทึมตรวจสอบข้อผิดพลาดจะถือว่า "สมบูรณ์" หากสามารถส่งต่อข้อผิดพลาดไปยังเอาต์พุตที่สังเกตได้หากข้อผิดพลาดนั้นมีอยู่จริง ดังที่ได้กล่าวไว้ก่อนหน้านี้ อัลกอริทึม D จำเป็นต้องค้นหาชุดอินพุตที่เป็นไปได้ทั้งหมดสำหรับวงจรที่อาจทำให้เกิดข้อผิดพลาดในวงจร "บล็อกข้อผิดพลาด D ดั้งเดิม" หรือ PDCF คือชุดอินพุตที่ทำให้เส้นทางไวต่อข้อผิดพลาดเฉพาะในวงจร "บล็อก D ที่ส่งต่อ" หรือ PDC คือชุดอินพุตที่ส่งต่อ D จากอินพุตไปยังเอาต์พุต

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

วิธีการตัดสินใจแบบมุ่งเน้นเส้นทาง (Path-Oriented Decision Making: PODEM) ถูกพัฒนาขึ้นโดย Goel ในปี 1981 เพื่อแก้ปัญหาที่อัลกอริทึม D พบเจอเกี่ยวกับเกต XOR PODEM เป็นการปรับปรุงครั้งสำคัญครั้งแรกที่เหนือกว่าอัลกอริทึม D ในแง่ของประสิทธิภาพ อัลกอริทึม D มีความซับซ้อนเพิ่มขึ้นแบบทวีคูณตามจำนวนโหนดภายในวงจร ในขณะที่ความซับซ้อนของ PODEM เปลี่ยนแปลงแบบทวีคูณตามจำนวนอินพุตของวงจร PODEM มีประสิทธิภาพมากกว่าอัลกอริทึม D เนื่องจากจำนวนอินพุตมักจะน้อยกว่าจำนวนโหนดภายในวงจรมาก

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

อัลกอริทึม Fan-out Oriented (FAN)เป็นการพัฒนาต่อยอดจาก PODEM โดยมีคุณสมบัติเพิ่มเติมหลายประการ ตัวอย่างเช่น มันใช้ข้อมูลเกี่ยวกับโครงสร้างวงจรเพื่อเพิ่มประสิทธิภาพในการค้นหา FAN แตกต่างจาก PODEM ในหลายด้าน ได้แก่: มันหยุดการย้อนกลับที่เส้นทางภายในบางเส้นทาง; มันทำการย้อนกลับหลายครั้ง; มันอนุญาตให้มีการอนุมานทั้งไปข้างหน้าและย้อนกลับ; และมันกำหนดสัญญาณที่ระบุได้อย่างเฉพาะเจาะจงทันที

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

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

วิธีการเชิงอัลกอริทึมสำหรับการสร้างชุดทดสอบเป็นตัวอย่างของ ATPG แบบ 'กำหนดได้' (deterministic) เนื่องจากชุดทดสอบได้รับการพัฒนาอย่างเป็นระบบโดยให้ผลลัพธ์ที่แน่นอนสำหรับข้อผิดพลาดเป้าหมาย การสร้างชุดทดสอบแบบสุ่มเทียม (pseudo-random) เป็นตัวอย่างของ ATPG แบบ 'ความน่าจะเป็น' (probabilistic) เนื่องจากเวกเตอร์ทดสอบถูกสร้างขึ้น 'แบบสุ่ม' และต้องการเพียงการตรวจสอบประสิทธิภาพผ่านการจำลองข้อผิดพลาด การผสมผสานการสร้างชุดทดสอบแบบสุ่มเทียมกับการสร้างชุดทดสอบเชิงอัลกอริทึมเป็นตัวอย่างของ ATPG แบบ 'ไฮบริด' (hybrid) ATPG แบบไฮบริดเป็นแนวทางที่ดีเพราะสามารถใช้ประโยชน์จากข้อดีของทั้ง ATPG แบบกำหนดได้และแบบความน่าจะเป็นได้