(۲-۴)
برای مثال، با توجه به روابط فوق برای عبارت ۱۰۱۰ ، مقدار کد شده عبارت است از ۱۰۱۱۰۱۰ . برای چک کردن عبارت کد شده، میتوان از روی بیتهای اطلاعات، مقدار چک بیتها را دوباره محاسبه کرد و پس از مقایسه با مقدار موجود چک بیتها در عبارت کد شده، به وجود و مکان خطا پی برد.
روش دیگر برای دیکد کردن کد همینگ، استفاده از ماتریس توازن (ماتریس H) است. با ضرب این ماتریس در عبارت کد شده، برداری به نام بردار سندرم[۳۳] به دست می آید. اگر بردار سندرم یک عبارت نول[۳۴] باشد (۰۰۰۰)، خطایی در کد وجود ندارد، در بقیه موارد در کد خطا وجود دارد. ماتریس توازن مربوط به کد همینگ (۷،۴) در رابطه ۲-۵ نشان داده شده است (ماتریس توازن، ماتریس باینری قرار گرفته در سمت چپ تساوی است).
(۲-۵)
در عبارت کد شده با کد همینگ اگر خطای تک بیتی در کد مورد نظر رخ دهد، سندرم به دست آمده برابر است با ستون باینری متناظر با مکان خطا در ماتریس H. اگر یک خطای چندبیتی در کد رخ دهد، سندرم به دست آمده برابر است با XOR بین ستون هایی از ماتریس H، که خطا در آنها رخ داده است. به عنوان مثال، رابطه ۲-۵ را در نظر بگیرید، اگر خطا در مکان c1 رخ دهد بردار سندرم برابر است با ۰۰۱ که این مقدار برابر با ستون مربوط به آن در ماتریس توازن است. حال فرض کنید خطا در c1 و c2 رخ دهد، بردار سندرم به دست آمده برابر است با ۰۱۱ که به خطا در مکان c3 اشاره دارد. در نتیجه در خطاهای دوتایی این کد دچار یک تصحیح اشتباه می شود. برای تشخیص خطاهای دوتایی یک چک بیت سراسری به عبارت کد شده اضافه می شود. در نتیجه زمانی که، بردار سندرم غیر صفر باشد و بیت توازن سراسری بدون خطا باشد، خطای رخ داده شده دوبیتی است. اگر در این حالت بیت توازن سراسری خطا داشته باشد، خطای رخ داده شده تک بیتی است. به این کد کد همینگ توسعه یافته[۳۵] میگویند، که قابلیت تشخیص خطاهای دو بیتی و تصحیح خطاهای تک بیتی را دارد (SEC-DED)[36]. در رابطه ۲-۶ ماتریس توازن مربوط به کد همینگ توسعه یافته (۸،۴) را ملاحظه میکنید. (ماتریس توازن، ماتریس باینری قرار گرفته در سمت چپ تساوی است). همانطور که ملاحظه میکنید یک ستون “۰” و یک سطر “۱” به دلیل اضافه کردن بیت توازن سراسری به این ماتریس نسبت به ماتریس توازن کد (۷،۴) اضافه شده است.
(۲-۶)
۲-۲-۲ استفاده از کد همینگ در بیتهای پیکره بندی (LUT)
در مرجع ]۲۷[ برای مقابله با SEU کد همینگ توسعه یافته (در بخش قبل توضیح داده شد) در بیتهای پیکره بندیFPGA اعمال شده است. این روش در سه سطح FPGA Level و CLB Level و LUT Level اجرا می شود که قدرت تصحیح در هرکدام متفاوت است (در بخش ۱-۲ ساختار FPGA توضیح داده شده است).
در سطح FPGA ، با توجه به رابطه ۲-۳، ابتدا یک ردیف از CLB ها برای ذخیره کردن بیتهای اطلاعات انتخاب میشوند و تعداد دیگری از CLB ها نیز برای ذخیره کردن بیتهای توازن در نظر گرفته میشوند. سپس در زمان کد کردن، چک بیتهای موجود در CLB های مربوط به چک بیتها، از روی بیتهای اطلاعات متناظر در CLB های مربوط به بیتهای اطلاعات محاسبه میشوند. در شکل ۲-۶ یک شمای کلی از این سطح مقاوم سازی نشان داده شده است. در این شکل CLB های خاکستری برای ذخیره کردن چک بیتها در نظر گرفته شده اند. این روش قابلیت تصحیح کامل یک CLB را دارد، اما اگر در دو CLB در یک آدرس یکسان خطا رخ دهد نمیتواند آن را تصحیح کند.
شکل ۲-۶: اعمال کد همینگ توسعه یافته در سطح FPGA ]27[.
در سطح CLB ، با توجه به رابطه ۲-۳، ابتدا یک ردیف از LUT ها برای ذخیره کردن بیتهای اطلاعات انتخاب میشوند و تعداد دیگری از LUT ها نیز برای ذخیره کردن بیتهای توازن در نظر گرفته میشوند. سپس در زمان کد کردن، چک بیتهای موجود در LUT های مربوط به چک بیتها، از روی بیتهای اطلاعات متناظر در LUT های مربوط به بیتهای اطلاعات محاسبه میشوند. در شکل ۲-۷ یک شمای کلی از این سطح مقاوم سازی نشان داده شده است. در این شکل LUT های خاکستری برای ذخیره کردن چک بیتها در نظر گرفته شده اند. در این سطح، تصحیح کامل یک LUT امکان پذیر است اما اگر دو LUT از یک CLB در یک بیت یکسان دچار خطا شوند قابل تصحیح نیست.
شکل ۲-۷: اعمال کد همینگ توسعه یافته در سطح CLB ]27[.
در سطح LUT ، کد همینگ در هر LUT به طور جدا گانه اعمال می شود. در نتیجه، اگر در یک LUT دوبیت دارای خطا باشد، نمی توان آنها را تصحیح کرد، اما خطا در چند LUT قابل تصحیح است. این سطح از نظر سخت افزاری نیاز به سخت افزار بیشتری برای پیاده سازی نسبت به دو سطح دیگر دارد. در شکل ۲-۸ نحوه اعمال این سطح از مقاوم سازی نشان داده شده است.
شکل ۲-۸: اعمال کد همینگ توسعه یافته در سطح LUT ]27[.
برای پیاده سازی این روشها، برای افزایش سرعت میتوان عملیات دیکد کردن را برای تمام سطر ها به طور هم زمان انجام داد[۳۷] که نیاز به سخت افزار بیشتری دارد یا میتوان برای تک تک سطرها انجام دادکه موجب کاهش سرعت می شود، اما حجم سخت افزار نیز کاهش مییابد. در مرجع ]۲۷[ مقاوم سازی در سطح CLB به عنوان سطح بهینه از نظر حجم سخت افزار و قدرت تصحیح معرفی شده است. در نتیجه این سطح از مقاوم سازی در جدول ۲-۷ با روشهای دیگر مقایسه شده است. جدول زیر از سنتز طرح در نرم افزار synopys با تکنولوژی ۱۸/۰ میکرون به دست آمده است.
جدول ۲-۷: مقایسه روش ارائه شده در مرجع ]۲۷[ با روش های دیگر]۲۷[.
۲-۲-۳ اعمال کد همینگ در ماژول سویچ
همانطور که در بخش ۱-۲ نیز بیان شد، دو نوع حافظه پیکره بندی در FPGA ها وجود دارد، یکی برای بلوکهای منطقی و دیگری برای ماژولهای سویچ. بیتهای پیکره بندی بلوکهای منطقی برای ذخیره کردن جدولهای صحت مربوط به توابع مدار استفاده میشوند و بیتهای پیکره بندی مربوط به ماژولهای سویچ، برای تعیین چگونگی اتصالات بین توابع و پایه های خروجی مورد استفاده قرار میگیرند. هر ماژول سویچ شامل چهار جعبه سویچ است و هر جعبه سویچ ۶ بیت پیکره بندی دارد (ساختار ماژول سویچ در بخش ۱-۲ توضیح داده شده است). در نتیجه هر ماژول سویچ نیز شامل ۲۴ بیت پیکره بندی است، که SEU در این بیتها موجب تغییر اتصالات بین بلوکهای منطقی در FPGA ودر نهایت تغییر تابع اجرایی مدار می شود. در همین راستا دو سطح از مقاوم سازی برای ماژول سویچ در مرجع ]۲۸ [ مورد توجه قرار گرفته است. ۱- مقاوم سازی در سطح جعبه سویچ . ۲- مقاوم سازی در سطح ماژول سویچ. در ادامه به بیان دقیق تر این سطوح مقاوم سازی می پردازیم.
در کد همینگ برای محافظت از N بیت باید تعداد K بیت، به بیتهای اطلاعات اضافه شود. برای داشتن قابلیت تصحیح یک بیت، N و K باید شرط مو جود در رابطه ۲-۷ را بر آورده کنند.
N+K+1≤ ۲K (۲-۷)
هر جعبه سویچ دارای ۶ بیت برای پیکره بندی است، در نتیجه در رابطه ۲-۷ مقدار N=6 است. برای محافظت از ۶ بیت بر اساس رابطه ۲-۷ باید ۴ بیت دیگر اضافه شود. شکل۲-۹ ساختار کد مورد نظر را نشان میدهد.
شکل۲-۹: ساختار کد همینگ استفاده شده برای هر جعبه ی سویچ.
ترکیب حالتهای ۴ بیت می تواند برای کد همینگ استاندارد (۱۱،۱۵) استفاده شود، اما در این کاربرد تنها ۶ بیت در هر جعبه سویچ وجود دارد و کد همینگ استفاده شده (۶،۱۰) است. این نوع کد، کد همینگ کوتاه شده[۳۸] نامیده شده است]۲۹.[ ماتریس H مربوط به کد همینگ (۶،۱۰) در رابطه ۲-۸ نشان داده شده است (ماتریس شامل اعداد صفر و یک در سمت چپ تساوی، ماتریس H است).
(۲-۸)
و اما برای مقاوم سازی در سطح ماژول سویچ، در این سطح از مقاوم سازی نیز کد همینگ برای محافظت از هر ماژول سویچ اعمال می شود. در هر ماژول سویچ ۲۴ بیت کنترلی وجود دارد (N=24) در نتیجه طبق رابطه ۲-۷ تعداد ۵ بیت به عنوان چک بیت باید اضافه شود تا کد قابلیت تصحیح خطاهای تک بیتی را داشته باشد. تعداد ترکیبهای مختلف حاصل از ۵ بیت می تواند برای کد همینگ استاندارد (۲۶،۳۱ ) استفاده شود، اما در این کاربرد تعداد بیتهای اطلاعات ۲۴ عدد است. در نتیجه کد استفاده شده، کد همینگ (۲۴، ۲۹) است که این کد نیز یک کد همینگ کوتاه شده است. ساختار این طرح در شکل ۲-۱۰ نشان داده شده است. ماتریس H مربوط به این کد نیز در رابطه ۲-۹ نشان داده شده است.
(۲-۹)
شکل ۲-۱۰: ساختار کد همینگ استفاده شده برای هر ماژول سویچ]۲۸[.
برای ارزیابی این دو سطح از مقاوم سازی، بر روی ۱۰ مدار از مدارات ITC’۹۹ این طرحها پیاده سازی شده و توسط نرم افزار synopsys سنتز شده اند. نتایج به دست آمده در جدول ۲-۸ نشان داده شده است. در این جدول، HSM نشان دهنده مقاوم سازی در سطح ماژول سویچ است و HSB نشان دهنده مقاوم سازی در سطح جعبه سویچ است. عبارت parity نیز نشان دهنده اضافه کردن یک بیت توازن به بیتهای پیکره بندی است که فقط قابلیت تشخیص خطا را دارد. در این جدول ۱st حالتی را نشان میدهد که برای هر ماژول یک مدار تست و تصحیح خطا در نظر گرفته شده است که در نتیجه این زمان مقدار ثابتی خواهد بود. اما در حالت ۲nd یک مدار تست و تصحیح برای کل ماژولها قرار داده شده است که این زمان را متغیر (وابسته به تعداد ماژولها در هر مدار) و طولانی می کند، اما حجم سخت افزار کاهش مییابد.
جدول ۲-۸: مقایسه نتایج به دست آمده برای اعمال کد همینگ در ماژول سویچ]۲۸[.
۲-۲-۴ میان گذاری[۳۹]
همانطور که در بخش ۱-۴-۳ بحث شد، با پیشرفت تکنولوژی نیمه هادی و کوچکتر شدن طول کانال، احتمال خطاهای مجاور چندتایی در حافظهها افزایش یافته است. در این راستا در مرجع ]۱۹[ با ارائه روشی به نام میان گذاری به مقابله با خطا های مجاور دوتایی پرداخته است.
ابتدا یک کد همینگ با قابلیت تصحیح تک بیتی را در نظر بگیرید، حال به شکل ۲-۱۱ توجه کنید. در این شکل در حالت Type1 کد همینگ مورد نظر در هر سطر اعمال شده است، در نتیجه در هر سطر فقط قابلیت تصحیح یک خطای تک بیتی وجود دارد. حال در همین شکل به Type2 توجه کنید، همانطور که مشاهده میکنید تعداد سلولها با Type1 متفاوت نیست، اما تعداد سطرها دو برابر شده است و در هر دو سطر، سلولهای آنها در میان یکدیگر قرار گرفتهاند. این دفعه با اعمال کد همینگ مورد نظر در هر سطر، قابلیت تصحیح خطای دو بیت مجاور به دست می آید. در این ساختار اگر خطا در دو سلول رخ دهد که یک سلول بدون خطا در وسط آنها باشد، خطا قابل تشخیص نیست.
شکل ۲-۱۱: چگونگی اعمال میانگذاری در سلولهای حافظه]۱۹[.
برای ارزیابی این طرح توسط دستگاه تشعشعات، نوترونهایی با انرژی MeV 800 به یک DRAM با ظرفیت Mb 16 تابیده شده است و نتایج آن در شکل ۲-۱۲ نشان داده شده است. همانطور که در این شکل مشخص است، قابلیت تصحیح دو بیت مجاور در سلولهای حافظه، کمک زیادی در کاهش نرخ خطا کرده است.
شکل۲-۱۲: مقایسه نتایج به دست آمده از میان گذاری]۱۹[.
۲-۳-۵ بهبود قابلیت تصحیح خطاهای مجاور
در بخش قبل برای مقابله با خطاهای مجاور، روشی به نام میان گذاری توضیح داده شده است. این روش در حافظههای کوچک کاربرد ندارد و اثرات نامطلوبی در floor-planning ، زمان دسترسی و توان مصرفی دارد]۳۰[. از این رو برای مقابله با MBU [۴۰] به بهبود در کدهای تصحیح خطا به جای استفاده از میان گذاری پرداخته شده است. در مرجع ]۳۰[ به بهبود کد همینگ (این کد در بخش ۲-۲-۱ توضیح داده شده است) برای مقابله با خطاهای مجاور دوتایی پرداخته شده است، که در ادامه به ارائه جزئیات این مقاله میپردازیم.
همانطور که میدانید تعداد بیتهای اطلاعات ذخیره شده در حافظهها، توانهای عدد ۲ مانند ۱۶ ، ۳۲ و ۶۴ هستند. در نتیجه برای اعمال کد همینگ با قابلیت تصحیح خطای تک بیتی در این بیتهای اطلاعات، با توجه به رابطه ۲-۷ به ترتیب باید تعداد چک بیتهای ۵، ۶ و ۷ به این بیتها اضافه شود و کدهای همینگ به دست آمده عبارتند از (۱۶،۲۱)، (۳۲،۳۸) و (۶۴،۷۱). طبق جدول ۲-۵ پارامترهای کدهای همینگ مورد نظر، پارامترهای استانداردی نیست.
در مرجع ]۳۰[ علاوه بر تعداد چک بیتهای مورد نیاز برای تصحیح خطای تک بیتی در بیتهای اطلاعات مورد نظر، یک چک بیت دیگر نیز اضافه شده است، یعنی پارامترهای کدهای مورد نظر عبارتند از (۲۲،۱۶)، (۳۹،۳۲) و (۷۲،۶۴)، اما این کار با هدف بهبود قابلیت تصحیح خطاهای مجاور دوتایی در کدهای مورد نظر انجام شده است.
برای بهبود قابلیت تشخیص خطا در کدهای مورد نظر، باید ماتریس توازن تشکیل شده شرایط زیر را ارضاء کند]۳۰[:
۱- هیچ ستون صفری در این ماتریس وجود نداشته باشد. این شرط موجب می شود که خطای تک بیتی با حالت بدون خطا اشتباه گرفته نشود.
۲- تمام ستونها از یکدیگر متمایز باشند. این شرط تضمین می کند که تمام خطاهای تک بیتی قابل تصحیح است.
۳- وابستگی خطی میان هیچ سه ستونی از ماتریس وجود نداشته باشد (XOR بین آنها صفر نشود). این شرط تضمین می کند که سندرمهای به دست آمده برای خطاهای دو بیتی از خطاهای تک بیتی متمایز است. در نتیجه خطاهای دو بیتی قابل تشخیص می شود.
۴- زمانی که وابستگی خطی بین چهار ستون در ماتریس وجود داشت، نباید بیشتر از دو تا از این ستونها در مجاورت یکدیگر قرار گیرند. این شرط موجب می شود که سندرم به دست آمده برای دو بیت مجاور با دو بیت مجاور دیگر یکسان نباشد و به عبارتی با رعایت این شرط، کد قابلیت تصحیح خطاهای مجاور دوتایی را دارا است. در صورتی که این شرط بر قرار نباشد به این حالت [۴۱]۴FC میگویند.
۵- تا جایی که ممکن است از وابستگی خطی میان چهار ستون جلوگیری شود. این امر موجب کاهش تداخل تصحیح خطاهای دو بیتی مجاور و تشخیص خطاهای دو بیتی غیر مجاور می شود و از احتمال اشتباه عمل کردن کد میکاهد. در صورتی که وابستگی خطی میان ۴ ستون در ماتریس وجود داشته باشد وآن ۴FC نباشد به آن [۴۲]۴BC میگویند.
الگوریتم یافتن ماتریس H بر مبنای یک جستجوی شبه عمومی است، که پنج شرط بیان شده در فوق را ارضاء می کند. در شکل ۲-۱۳ یک ماتریس H به دست آمده با توجه به شرایط فوق برای کد (۲۲،۱۶) نشان داده شده است. به عنوان نمونه بین ستونهای ۳ و ۴ و ۶ و ۲۲ این ماتریس یک ۴BC وجود دارد.
شکل۲-۱۳: ماتریس H به دست آمده برای کد (۲۲،۱۶)]۳۰[.
همانطور که ملاحظه میکنید در ماتریس فوق هیچ ستونی با وزن ۲ (به این معنی است که ۲ عدد ۱ در این ستون وجود دارد) وجود ندارد، زیرا زمانی که خطای دوتایی در بیتهای مربوط با ستونهایی به وزن ۱ رخ دهد، موجب تداخل بین خطای تک بیتی و دو بیتی می شود. در نتیجه زمانی که الگوریتم در حال جستجو است از قرار دادن ستونهایی با وزن ۲ در ماتریس فوق، پرهیز می کند. این مثال برای مفهوم جستجوی شبه عمومی در الگوریتم بیان شد. در شکلهای ۲-۱۴ و ۲-۱۵ ماتریسهای توازن به دست آمده برای کدهای (۳۹،۳۲) و (۷۲،۶۴) نیز نشان داده شده است.
شکل ۲-۱۴: ماتریس H به دست آمده برای کد (۳۲،۳۹)]۳۰[.
شکل ۲-۱۵: ماتریس H به دست آمده برای کد (۶۴،۷۲)]۳۰[.
در جدول ۲-۹ نتایج به دست آمده از این کدها با کدهای تصحیح خطای دیگر مقایسه شده است.
جدول ۲-۹: مقایسه کدهای ارائه شده در مرجع ]۳۰[ با کدهای دیگر.
در جدول فوق برای محاسبه تعداد گیتهای XOR دو ورودی مورد نیاز برای کد کردن و دیکد کردن و همچنین ماکزیمم عمق Logic آنها از روی ماتریس توازن از روابط ۲-۱۰ و ۲-۱۱ استفاده شده است. در رابطه ۲-۱۰منظور از وزن هر سطر (row weight) تعداد یکهای موجود در آن سطر است.
(۲-۱۰)
(۲-۱۱)
۲-۲-۶ استراتژی جایابی بیت انتخابی[۴۳]
همانطور که در بخش قبل نیز بیان شد، تعداد بیتهای اطلاعات استفاده شده در حافظهها معمولا توانهایی از عدد ۲ است. در نتیجه با اعمال کد همینگ در آنها طبق رابطه ۲-۷، پارامترهای به دست آمده، پارامترهای استانداردی نیست. در مرجع]۲۹[ روشی به نام جایابی بیت ارائه شده است که با اعمال آن در کدهای همینگ کوتاه شده برای تعداد بیتهای اطلاعات ۸، ۱۶ و ۳۲، موجب بهبود تشخیص خطاهای مجاور دوتائی و سه تائی شده است.
[جمعه 1400-07-23] [ 02:32:00 ق.ظ ]
|