کد همینگ (۷،۴): چگونه منطق XOR خطاهای حافظه را پیش از پردازنده اصلاح می‌کند

تولیدکنندگان سخت‌افزار مصرفی اغلب ادعا می‌کنند که حافظه‌های دارای قابلیت تصحیح خطا برای کاربران عادی هزینه‌ای اضافی است و رم‌های امروزی ذاتاً پایدارند. اما فیزیکِ کوچک‌سازی سیلیکون این را نقض می‌کند.

با کاهش اندازه سلول‌های حافظه به زیر ۱۰ نانومتر، آسیب‌پذیری آن‌ها در برابر تشعشعات پس‌زمینه و نوسانات ولتاژ بیشتر می‌شود؛ تا جایی که تغییر بیت‌ها (Bit flips) به جای یک اتفاق نادر، به یک قطعیت ریاضی تبدیل می‌شود. راهکار این ناپایداری یک وصله نرم‌افزاری جدید نیست، بلکه چارچوب ریاضیاتی است که در سال ۱۹۵۰ توسط ریچارد همینگ در آزمایشگاه‌های بل (Bell Labs) منتشر شد.[2]

مقاله بنیادین همینگ با عنوان «کدهای تشخیص و تصحیح خطا»، سیستمی را معرفی کرد که نه‌تنها داده‌های خراب را علامت‌گذاری می‌کند، بلکه پیش از آنکه پردازنده حتی متوجه خطا شود، آن را فعالانه ترمیم می‌کند. همینگ در مجله فنی سیستم بل نوشت: «هدف این مقاله ساخت کدهای سیستماتیکی است که نه‌تنها خطاها را تشخیص می‌دهند، بلکه آن‌ها را اصلاح نیز می‌کنند.»

مشهورترین پیاده‌سازی کار او، کد همینگ (۷،۴) است. اعداد، ساختار را دیکته می‌کنند: به ازای هر چهار بیت داده واقعی، سیستم سه بیت توازن (Parity bits) اضافه می‌کند و یک بلوک هفت‌بیتی می‌سازد. این یعنی یک سربار ذخیره‌سازی عظیم ۷۵ درصدی. اگر این نسبت دقیق را روی یک درایو ۱ ترابایتی اعمال کنید، ۴۲۸ گیگابایت را فقط برای تصحیح خطا از دست خواهید داد.[3]

به دلیل این سربار شدید، ساختار (۷،۴) به‌ندرت برای ذخیره‌سازی انبوه استفاده می‌شود. در عوض، ارزش آن در سادگی محاسباتی‌اش نهفته است. همان‌طور که دپارتمان مهندسی دانشگاه نیوبرانزویک شرح داده است، فرآیندهای رمزگذاری و رمزگشایی کاملاً بر پایه گیت‌های منطقی یای انحصاری (XOR) استوارند.[1]

گیت XOR یکی از پایه‌ای‌ترین اجزا در الکترونیک دیجیتال است. این گیت تنها در صورتی خروجی «۱» می‌دهد که دو ورودی آن متفاوت باشند. کنترلر حافظه با عبور دادن چهار بیت داده از ترکیب‌های خاصی از این گیت‌ها، سه بیت توازن را در کسری از نانوثانیه تولید می‌کند.[4]

هنگامی که داده‌ها بعداً از حافظه خوانده می‌شوند، کنترلر بلوک هفت‌بیتی را از همان منطق XOR عبور می‌دهد. اگر یک پرتو کیهانی یا نوسان برق یک صفر را به یک تبدیل کرده باشد، خروجی این گیت‌ها—که کلمه سندرم (Syndrome word) نامیده می‌شود—صفر نخواهد بود.[5]

نبوغ کد همینگ (۷،۴) در همین کلمه سندرم نهفته است. این یک عدد باینری سه‌بیتی است که دقیقاً به مکان خطا اشاره می‌کند. اگر سندرم در حالت باینری «۱۱۰» (معادل عدد ۶ در مبنای ده) باشد، کنترلر فوراً می‌فهمد که بیت ششم در بلوک خراب شده است.[3]

پس از شناسایی مکان، رفع آن به هیچ الگوریتم پیچیده‌ای نیاز ندارد. کنترلر به‌سادگی با استفاده از یک گیت NOT نهایی، بیت ششم را به حالت اولیه خود برمی‌گرداند. پردازنده چهار بیت داده اصلاح‌شده را دریافت می‌کند بدون اینکه هرگز بداند خطایی رخ داده است، و کل این فرآیند با سرعت حرکت الکتریسیته در سیلیکون انجام می‌شود.[1][4]

مطالعه‌ای در سال ۲۰۱۲ که در مجله بین‌المللی تحقیقات و فناوری مهندسی منتشر شد، این موضوع را با پیاده‌سازی یک رمزگذار و رمزگشای (۷،۴) روی یک دستگاه منطقی برنامه‌پذیر پیچیده (CPLD) نشان داد. محققان تایید کردند که عمق منطق سخت‌افزاری آن‌قدر کم است که تاخیر ایجادشده توسط فرآیند تصحیح در عملیات استاندارد حافظه عملاً غیرقابل تشخیص است.[4]

با این حال، کد (۷،۴) یک محدودیت ریاضی سخت‌گیرانه دارد: در هر بلوک تنها می‌تواند یک خطای تک‌بیتی را تصحیح کند. اگر دو بیت در یک بلوک هفت‌بیتی به‌طور همزمان تغییر کنند، کلمه سندرم به مکان اشتباهی اشاره می‌کند و باعث می‌شود کنترلر یک بیت سالم را «تصحیح» کرده و در واقع خطای سومی را وارد کند.[5]

برای کاهش این مشکل، مهندسان اغلب یک بیت هشتم—یک بیت توازن کلی—اضافه می‌کنند و کد همینگ توسعه‌یافته (۸،۴) را می‌سازند. این تغییر به سیستم اجازه می‌دهد خطاهای تک‌بیتی را تصحیح کرده و خطاهای دوبل را به‌دقت تشخیص دهد (اما تصحیح نکند)، و از خرابی خاموش داده‌ها جلوگیری کند.[3]

سرورهای سازمانی و ایستگاه‌های کاری مدرن از نسخه مقیاس‌یافته این ریاضیات استفاده می‌کنند. رم‌های استاندارد با کد تصحیح خطا (ECC) به جای (۷،۴) از ساختار (۷۲،۶۴) بهره می‌برند. این ساختار از ۶۴ بیت داده با ۸ بیت توازن محافظت می‌کند و سربار ذخیره‌سازی را از ۷۵٪ به تنها ۱۲.۵٪ کاهش می‌دهد، در حالی که توانایی رفع خطاهای تک‌بیتی در لحظه را حفظ می‌کند.[5]

با وجود کارایی پیاده‌سازی (۷۲،۶۴)، پردازنده‌های دسکتاپ مصرفی و مادربردها از نظر تاریخی پشتیبانی از ECC را برای بخش‌بندی بازار و کاهش هزینه‌ها غیرفعال کرده‌اند. این امر کاربران عادی را در معرض خرابی خاموش داده‌ها قرار می‌دهد، جایی که تغییر یک بیت در یک عکس خانوادگی یا فایل سیستمی دائمی می‌شود.[6]

میراث اختراع سال ۱۹۵۰ ریچارد همینگ بسیار فراتر از حافظه کامپیوتر است. اصول بنیادین بررسی توازن و رمزگشایی سندرم، پایه و اساس کدهای پیچیده‌تر Reed-Solomon و LDPC را تشکیل می‌دهند که امروزه در شبکه‌های 5G، ارتباطات ماهواره‌ای و درایوهای حالت جامد (SSD) استفاده می‌شوند.[2][5]