بخشی از مقاله
چکیده
تشخیص خطا، برای بالا بردن بهره تولید و کاهش زمان خطایابی محصول اهمیت دارد. در این مقاله، ما یک روش جدید برای آنالیز خطای چندگانه در مدارات، ارائه می کنیم . اساس این روش تزریق خطای چندگانه است. این در حالی است که بیشتر روش های تشخیص خطای رایج، یک خطا را از بین کاندیدهای خطا در یک زمان انتخاب می کنند و آن را شبیه سازی می کنند و براساس الگوهای موجود، خطا را مشخص می کند. این در حالی است که یک تزریق خطای تکی نمی تواند اثر خطاهای چندگانه که در مدار خطادار واقعی وجود دارد را آشکار کند. ما در این جا خطاهای چندگانه را با هم به مدار تزریق می کنیم و از طریق یک آنالیز effect-cause ، لیستی از خطاهای ممکن را پیدا می کنیم..
واژه های کلیدی: تشخیص خطا، تزریق خطای چندگانه، الگوریتم های ابتکاری
مقدمه
تشخیص خطا یک عملیات مهم برای تولید آزمون مدارهای مجتمع1 سالم است و نقش مهمی در بالا بردن بهره وری دارد. نقص ها در سطح منطقی می توانند با استفاده از خطاهایی که روی موقعیت های تکی یا چندگانه در مدار اثر می گذارند، شبیه سازی شوند و پاسخ های غلط را برای یک یا تعداد بیشتری از بردار های تست ورودی مدار تولید می کنند. می توانیم از پاسخ های غلط و مدار تحت تشخیص، برای تشخیص خطا و اینکه کدام محل ها به طور بالقوه خطادار هستند، استفاده کنیم. دو نوع الگوریتم کلاسیک به نام های Cause-effect و Effect-cause، داریم که تشخیص منطقی مدار را مورد تحقیق قرار داده اند [1]و.[2]
الگوریتم Cause-effect بر پایه شبیه سازی خطا است. اساس کار این الگوریتم این است که یک دیکشنری خطا درست می کند که شامل پاسخ های یک گروه تست در حضور یک گروه خطای داده شده می باشد[3]و.[4] تشخیص منطقی این الگوریتم به وسیله مقایسه ی پاسخ های مدار واقعی با پاسخ های ذخیره شده در دیکشنری می باشد. اشکال مهم این الگوریتم اندازه دیکشنری است. زیرا نیاز به ذخیره مقدار زیادی از اطلاعات که به وسیله شبیه سازی خطا تولید می شوند، را دارد. این مشکل در مدارات بزرگ بیشتر دیده می شود.
الگوریتم دوم Effect-cause ، از یک فرآیند برگشتی2 خطا مانند ردیابی مسیر بحرانی استفاده می کند.[5] ردیابی مسیر این گونه است که حرکت از خروجی اصلی3 خطا به سمت ورودی اولیه4 مدار تحت تست تعریف می گردد . یعنی هر خط مدار تحت تست، توسط این فرآیند برگشتی بازدید می شود و آن را به عنوان منبع احتمالی کاندید خطا، در نظر می گیرد. الگوریتم Cause-effect حافظه کارآمد بیشتری نسبت به الگوریتم Effect-cause دارد. در مقاله[12] پیشنهاد تولید الگوهای تستی که رزولوشن تشخیص خطای چندگانه را بهبود بدهد را دادند. اما در عمل، برای تشخیص خطا یک مصرف کننده ممکن است ، بیاید از الگوهای تست یکسانی که به وسیله ابزار تولید الگوهای تست اتوماتیک 5 برای تست خطاهای ایستا 6 تولید می شوند، استفاده کند.
در مقالات[7]، [8]، [9] و [14] از یک تکنیک تحت عنوان الگوی ارزیابی و تزریق استفاده شده است. آنها ابتدا از یک الگوریتم ردیابی مسیر7 ، استفاده کرده اند و محل های کاندید خطای ممکن را پیدا کردند. سپس این خطاها را به ترتیب در محل های دلخواه تزریق کردند پس از شبیه سازی این کاندیدها به وسیله پتانسیل بالقوه ای که دارند، رتبهبندی میشوند. از الگوهای 8SLAT به کمک خطاهای چندگانه برای تشخیص پاسخ های خطادار ایجاد شده، استفاده می کنند .[6] الگوهای SLAT هر پاسخ خطا را را برای یک خطای تکی نسبت می دهند. الگوریتم تلاش می کند، با استفاده از الگوهای SLAT، همه ی موقعیت های خطای تکی را پیدا کند. هر کاندید می تواند تعدادی از الگوهای خطا را توضیح بدهد. الگوریتم وقتی این کاندیدها را پیدا می کند، برای مرتب کردن آن ها داخل گروه های کاردینالیتی که همه الگو های شکست را توضیح می دهند، شروع به جست و جو می کند. نتایج نشان می دهد اگر چه خطاهای چندگانه در مدار وجود دارند اما بسیاری از الگوهای خطا ، در واقع الگوهای SLAT هستند .[6] اما در واقعیت، وقتی خطاهای چندگانه در مدار وجود داشته باشند، هر خطایی نمی تواند یک تست SLAT داشته باشد.
همه ی روش هایی که در بالا گفته شد، وقتی کار می کنند که یک الگو تست فقط یک خطا را فعال کند. اگرچه در مداری که تحت تست قرار گرفته است، خطای چندگانه وجود داشته باشد.. اما در واقعیت، وقتی چگالی خطا افزایش می یابد، یک الگو می تواند خطاهای چندگانه را فعال کند و رفتارهای خطا چند گانه را به وجود آورد. یک روش جدید به اسم روش افزایشی، توسعه یافت[13] و .[15] این روش بر اساس شبیه سازی خطاهای چندگانه، ابتدا یک گروه از خطاهای بالقوه را به وسیله الگوریتم برگشتی تعیین می کند آن خطاها را آزمایش می کند و خطایی که به طور موفقیت آمیز بیشترین تعداد الگوهای خطادار را توضیح دهد، انتخاب می کند. حال این خطای انتخاب شده را به مدار تزریق می کنند و مدار را براساس آن خطا اصلاح می کنند.
این فرآیند تا زمانی که همه الگوهای خطادار شرح داده شوند، ادامه می یابد. مشکل اساسی این روش این است که اگر خطایی اشتباهی در هر مرحله ای انتخاب شود، می تواند موجب راه حل خطا دار شود. با وجود اینکه تشخیص افزایشی خطا در اکثر موارد خوب کار می کند. اما بعضی اوقات شکست می خورد. به دلیل این که الگوریتم ذاتا برپایه شبیه سازی خطای تکی می باشد. اما تزریق تکی خطا هرگز نمی تواند اثر خطاهای چند گانه که در مدارات وجود دارد را آشکار کند.
بنابراین برای تشخیص خطاهای چندگانه، در نظر گرفتن تزریق شبیه سازی خطاهای چندگانه ضروری می باشد. یک الگوریتم دیگر نیز ارائه شده که شامل شبیه سازی هر دو خطای تکی و چندگانه می باشد. همه خطاهایی که می توانند به وسیله الگوهای خطادار آشکار شوند، کاندیدهای اولیه می شدند. الگوریتم می آید الگوهای خطادار را شبیه سازی می کند و کاندیدهای غیرممکن را حذف می کند. حال به وسیله انتخاب تصادفی، گروهی از خطا های دوبل و سه گانه و چهارگانه از خطاهای کاندید ذاتی ایجاد می شوند را انتخاب می کند. این گروه های خطا سپس شبیه سازی می شوند
براساس تعداد الگوهای خطادار که هرگروه می تواند توضیح دهد، رتبهبندی می شوند. اما یک انتخاب تصادفی هرگز نمی تواند تضمینی برای راه حل پیدا شده باشد. در این جا ، از آنجایی که تعداد محل های خطا مشخص نیست. ما یک الگوریتم تشخیص خطا براساس شبیهسازی خطای چندگانه ارائه می کنیم.. اکثر الگوریتم های تشخیص خطای موجود، می تواند تنها یک گروه تست با کاردینالیتی مینیمم تولید کنند که به طور موفقیت آمیز کل گروه الگو خطا را توضیح دهند. الگوریتم های شبیهسازی خطاهای چندگانه، ذاتا در زمان نمایی هستند بنابراین برای پوشش این فضای جستجوی نمایی، از الگوریتم های ابتکاری استفاده می کنیم.[16] در ابتدا ما به وسیله روش ردیابی مسیر از هر خروجی اصلی خطادار یک لیست از کاندیدهای احتمالی خطا و اجتماعی از آنها می گیریم.
حالا ما بصورت تصادفی از محل های که امکان خطا در آنها وجود دارد ذرات اولیه الگوریتم های ابتکاری را انتخاب می کنیم. تعداد خطاها در هر ذره مختلف است. پس هر ذره، گروهی از خطا ها با کاردینالیتی مختلف دارد. این ذرات سپس به وسیله الگوهای - خطادار یا سالم - که شرح می دهند، ارزیابی می شوند. الگوریتم پیشنهادی ما می تواند به طور موفقیت آمیزی، شمار زیادی از خطاهای موجود در مدار را تشخیص دهد. نتایج، خطاهای بالای 10 تا را نشان می دهد و همچنین این الگوریتم قابلیت تشخیص و رزولوشن و نرخ موفقیت بالایی را نشان می دهد. مزیت راه حل ما تولید گروه های بسیار با کاردینالیتی متفاوت می باشد که همه ی آنها می توانند طور موفقیت آمیزی مجموعه الگوخطا و همچنین الگوهای سالم را نشان دهند.
تشخیص خطا
تشخیص خطای مدارهای منطقی یک مرحله بسیار مهم در خطوط تولید چیپ های مدار منطقی است. پایه گیت های مورد استفاده ممکن است دچار خطای تحویل سیگنال ثابت صفر یا یک شوند که این می تواند در عملکرد کل سیستم الکترونیکی اختلال ایجاد کند. بدین منظور روش های برای شناسایی محل اینگونه خطاها ارائه شده است، که با ارسال پترن های شناخته شده و با فرض درست بودن مدار، به بررسی خروجی گیت ها پرداخته و از نتایج غلط بدست آمده برای تعیین مکان محل خطا استفاده می کنند.
یکی از روش های شناخته شده روش مسیر بازگشتی است که از طریق مکان های حساس به تغییر بیت درون مدار به بررسی مسیرهای بحرانی کل مدار در حضور یک پترن بیت ارسالی به ورودی می پردازد. به عبارت دیگر با یافتن مسیرهای بحرانی به طور بازگشتی می توان کاندیدهای محل خطا در کل مدار را پیدا کرد. در این جا از این روش برای یافتن راه حل اولیه برای مکان های خطا استفاده می شود. روش نهایی مورد استفاده برای تعیین محل خطا، روش الگوریتم های ابتکاری است که با فرض چندین راه حل اولیه برای مساله به حرکت تمامی ذره ها در ساختار مساله پرداخته و با مکانیزم خاصی سعی دارد که از طریق یک تابع هزینه بهترین راه حل را از میان تمامی ذره ها بعد از چند تکرار انتخاب و معرفی کند. در این جا ما مدارهای بدون پهنای خروجی - فاقد پایه مشترک - را بررسی می کنیم .
شبیه سازی های خطا چندگانه
الگوریتم تشخیصی خطا، که براساس خطاهای تکی کار می کنند. از رفتار شبیه سازی خطای تکی برای تطبیق پاسخ های خطادار مشاهده شده با الگوهای تست داده شده استفاده می کند. در واقعیت وقتی چگالی خطا افزایش پیدا می کند، یک الگو ممکن است خطا های چندگانه را فعال کند و رفتارهای خطای چندگانه ایجاد نماید. محدودیت های الگوریتم های تشخیصی بر پایه خطای تکی با این مثال که در شکل1 آورده شده، نشان داده می شود. فرض کنید برای مدار شکل1، می توان از 3 الگو برای تشخیص استفاده نمود. با بکاربردن الگوهای P2 و P3، تعدادی خروجی های اولیه شکست مشاهده می شود. الگوریتم تشخیص خطای تکی، روی الگو شکست P3 به کار برده می شود که کاندید خطا ممکن B:S-a-0 را نتیجه می دهد. - خطا A:S-a-0 به وسیله P3 فعال نمی شود. -
این مثال توضیح می دهد که الگوریتم های فرضی خطای تکی گاهی اوقات کار می کنند، اگرچه خطاهای چندگانه در مدار وجود داشته باشند. با این وجود، الگو معیوب P2 نمی تواند به وسیله خطا تکی در مدار توضیح داده شود. همه فرضیات خطا تکی در این مورد شکست خواهند خورد. تنها یک الگوریتم با استفاده از مکانیسم تطبیق دادن جزیی1 می تواند A:S-a-0 را به عنوان کاندید محتمل دیگر گزارش دهد [10] و .[17] بنابراین، برای توضیح همه الگوها، دو خطا - A:S-a-0 , B:S-a-0 - باید با هم شبیه سازی شوند.
الگوریتم تشخیص خطا
ابتدا با یک خروجی اولیه خطا - برای یک الگو خطادار خاص - شروع می کنیم و با روش ردیابی مسیر به سمت ورودی های اولیه بر می گردیم. این فرآیند برای همه ی خروجی های اولیه خطا و همه الگوهای خطادار انجام می دهیم.[5] به دلیل این که خطاها چندگانه در نظر گرفته شده اند، اجتماع همه ظریفت ورودی مخروط ها2 گرفته می شود. همه خطاهای به دست آمده از این روش به عنوان خطاهای کاندید قلمداد می شوند و به عنوان یک ورودی به الگوریتم های ابتکاری داده می شوند.
الگوریتم های ابتکاری ما همچنین گروهی از الگوهای خطادار با پاسخ های غلط - از تست تر - و همچنین الگوهای سالم به عنوان ورودی های دیگر می گیرند. الگوریتم، گروه های چندگانه خطا که تابع شایستگی3 مشابه دارند را به عنوان بهترین ذره تولید می کند. نتایج نهایی تولید شده به وسیله این روش، لیستی از خطاهای ممکن به ما میدهند. الگوریتم های ابتکاری همچنین بهترین راه حل فراهم شده را به ما می دهند.
الگوریتم های ابتکاری برای شبیه سازی خطا چندگانه
الگوریتم های شبیه سازی خطا چندگانه، ذاتا به زمان نمایی می-باشند. زیرا حقیقت این است که تعداد محل های خطادار برای ما ناشناخته میباشند. از الگوریتم های ابتکاری برای پوشاندن این فضا جستجو نمایی و پیدا کردن راهحل مناسب استفاده می کنیم.[16] خطاهای کاندید احتمالی ابتدا از روش مسیر ردیابی مدار پیدا می شوند و به عنوان یک ورودی به الگوریتم های ابتکاری ما داده می شوند. در این مسئله، ساختار ذره یک آرایه n بیتی می باشد. N تعداد کل کاندیدهای احتمالی خطا میباشد. بنابراین 1 در موقعیت i ام نشان می دهد که خطای i ام در لیست کاندید حاضر است و در غیر این حالت 0 گذاشته می شود.
نمونه شکل2 را در نظر بگیرید: کاندید های خطا بعد از روش مسیر ردیابی به صورت زیر می باشد:
چون 8 خطا ممکن وجود دارد، ساختار ذره در شکل 3 آورده شده است. ذره بالا شامل سه خطا می باشد: .PO1/1,PO2/1,B/0 معمولا در الگوریتم های ابتکاری از ذرات با موقعیت های تصادفی استفاده می شود. در اینجا مشابه همین کار انجام شده اما برای استفاده از فضای جستوجو به صورت بهتر، کل فضای جستوجو به بخش های مختلفی تقسیم می کنیم. این کار با توجه به این که اگرچه از نظر تئوری هر تعداد خطا می تواند در مدار حضور داشته باشد، اما در عمل تنها تعداد کمی می تواند باشد، انجام شده است[11] و .[15] یک متغیر MAX_POSS_FAULT تعریف می شود. این متغیر تعداد ماکسیمم خطاهای ممکنی که می تواند در مدار اتفاق بیفتد را نشان می دهد و بیش از 10تا نیست. مهم است که گفته شود جستوجو فقط برای 10 خطا محدود نمی شود.
مدارهای بدون پهنای خروجی - فاقد پایه مشترک - ابتدا ما ردیابی مسیرهای بحرانی را در یک مدار بدون پهنای خروجی با استفاده از مثال شکل 4 بیان می کنیم. برای چنین مداری - که همیشه ساختار درختی دارد - ، ردیابی مسیر بحرانی یک روش حرکت درختی ساده است که هر ورودی حساس با خروجی بحرانی را بعنوان بحرانی مشخص می کند. این براساس این واقعیت است که اگر یک خروجی بحرانی باشد، پس ورودی حساس آن در هر صورت بحرانی است. برای استفاده از الگوریتم پیشنهادی در این جا ، از یک مدار که در شکل 4 آورده شده است استفاده کردیم
