یک الگوریتم جستجو توپولوژیک برای ATPG

تولید آزمایش برای مدارهای دیجیتال ترکیبی می‌تواند به عنوان یک مساله جستجو مشخص شود. یک تست برای یک خطا را می توان با امتحان کردن الگوهای مختلف یافت تا زمانی که مشخص شود که مدار خوب را از مدار معیوب متمایز می‌کند. پیدا کردن راهی موثر برای امتحان این الگوهای مختلف مشکل را به سمت تکنیک‌های جستجوی [ Kirkland در ارجاع ۸۷۱] تبدیل می‌کند. فضای جستجو می‌تواند کاملا بزرگ باشد، با این حال، ممکن است یک راه‌حل وجود نداشته باشد. برخی از روش‌ها باید برای سازماندهی روند جستجو برای اطمینان از اینکه هر الگوی ممکن می‌تواند امتحان شود و هیچ الگویی دو بار امتحان نشده است، استفاده شود. با این حال، لازم نیست که به طور واضح کل فضا را جستجو کنیم؛ ممکن است در برخی موارد امکان پذیر باشد تا مشخص شود که هیچ راه‌حل تنها با یک جستجوی نسبی وجود ندارد Gael در ارجاع [۸۱۱] به طور مشابه، اگر یک روش برای جستجوی فضای کوچکتری برای راه‌حل پیدا کرد، اندازه مشکل جستجو کاهش می‌یابد و مساله تولید آزمایش بیشتر انعطاف‌پذیر می‌شود. در طول جستجو برای تست، مقادیر به نودهای موجود در فضای جستجو اختصاص داده می‌شوند. گره‌ها به دو دسته ت

The automatic generation of tests for combinational digital circuits is examined from the standpoint of a guided search through a search space. The limitations of this process, namely the size of the search space and the overall strategy, are identified and methods are presented to reduce the size of the search space as well as produce a more optimal ordering of node assignments. A new algorithm is proposed that uses the smaller search space and the improved ordering for node assignments based on a topological analysis of the circuit. Results are presented indicating that this new algorithm, termed TOPological Search (TOPS), is faster than existing algorithms and also rapidly identifies many redundant faults without search.