(۲-۴)
برای مثال، با توجه به روابط فوق برای عبارت ۱۰۱۰ ، مقدار کد شده عبارت است از ۱۰۱۱۰۱۰ . برای چک کردن عبارت کد شده، می­توان از روی بیتهای اطلاعات، مقدار چک بیتها را دوباره محاسبه کرد و پس از مقایسه با مقدار موجود چک بیتها در عبارت کد شده، به وجود و مکان خطا پی برد.

روش دیگر برای دیکد کردن کد همینگ، استفاده از ماتریس توازن (ماتریس 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) تعداد یک­های موجود در آن سطر است.
(۲-۱۰)
(۲-۱۱)
۲-۲-۶ استراتژی جایابی بیت انتخابی^[۴۳]
همانطور که در بخش قبل نیز بیان شد، تعداد بیتهای اطلاعات استفاده شده در حافظه­ها معمولا توانهایی از عدد ۲ است. در نتیجه با اعمال کد همینگ در آنها طبق رابطه ۲-۷، پارامترهای به دست آمده، پارامترهای استانداردی نیست. در مرجع]۲۹[ روشی به نام جایابی بیت ارائه شده است که با اعمال آن در کدهای همینگ کوتاه شده برای تعداد بیتهای اطلاعات ۸، ۱۶ و ۳۲، موجب بهبود تشخیص خطاهای مجاور دوتائی و سه تائی شده است.