کد تصحیح خطا

در محاسبات (به انگلیسی: computing)، مخابرات (به انگلیسی: telecommunication)، نظریه اطلاعات (به انگلیسی: information theory) و نظریه کدگذاری (به انگلیسی: coding theory)، تصحیح خطای پیشرو (FEC) یا کدگذاری کانال (به انگلیسی: channel coding) ، تکنیکی برای کنترل خطاها در ارسال داده ها از طریق کانال های مخابراتی غیر قابل اعتماد و یا پر نویز می باشد.

ایده اصلی این است که فرستنده پیام را به صورت افزونه‌ای (به انگلیسی: redundant)،  اغلب با استفاده از کد تصحیح کننده خطا (به انگلیسی: error-correcting code) یا کد تصحیح خطا (به انگلیسی: error-correction code) (ECR)کدگذاری می‌کند . این افزونگی (به انگلیسی: redundancy) به گیرنده این امکان را می‌دهد که نه تنها خطاهایی را که ممکن است در هر نقطه‌ای از پیام رخ دهد تشخیص دهد،  بلکه اغلب تعداد محدودی از خطاها را نیز تصحیح کند. بنابراین ممکن است به کانال معکوس (به انگلیسی: reverse channel)، برای ارسال مجدد نیازی نباشد. هزینه این روش افزایش و ثبات پهنای باند پیشرو (به انگلیسی: forward channel bandwidth) می باشد.

ریاضیدان آمریکایی ریچارد همینگ (به انگلیسی: Richard Hamming) این حوزه را در دهه 1940 پایه گذاری کرد و اولین کد تصحیح خطا  (به انگلیسی: error-correcting code) را در سال 1950 به وجود آورد:کد همینگ(7، 4).

تحصیح خطای پیش رو (FEC)، می تواند در موقعیت هایی که ارسال مجدد هزینه بر یا ناممکن است، همانند لینک های ارتباطی یک طرفه و یا درحین ارسال پیام به چند گیرنده به صورت چند بخشی (به انگلیسی: multicast)، به کار گرفته شود. اتصالات با تاخیر طولانی نیز می توانند از این روش بهره ببرند؛ در مورد یک ماهواره که بدور مدار اورانوس در چرخش است، ارسال مجدد (به انگلیسی: retransmission) به دلیل خطا، می تواند تاخیری به مدت 5 ساعت ایجاد کند. FEC بطور گسترده در مودم ها و شبکه های سلولی نیز استفاده می شود.

پردازش FEC در یک گیرنده ممکن است به یک جریان بیت دیجیتالی (به انگلیسی: digital bit stream) و یا دمدوله سازی (به انگلیسی: demodulation) یک حامل دیجیتالی (به انگلیسی: digital carrier) مدوله شده (به انگلیسی: modulated) اعمال شود. در مورد بخش دوم، FEC یک بخش جدایی ناپذیر از مبدل آنالوگ به دیجیتال (به انگلیسی: analog-to-digital conversion) اولیه در گیرنده ها می باشد. رمزگشای ویتربی (به انگلیسی: Viterbi decoder) یک الگوریتم انتخابی نرم (به انگلیسی: soft decision algorithm) را برای دمدوله سازی (به انگلیسی: demodulate) داده های دیجیتال از یک سیگنال آنالوگ آلوده به نویز (به انگلیسی: noise) پیاده سازی می کند. بسیاری از رمزگشاهای (به انگلیسی: decoder) FEC  قادرند یک سیگنال نرخ خطای بیت (به انگلیسی: bit-error-rate) را تولید کند که می تواند به عنوان یک بازخورد برای تنظیم الکترونیک دریافت آنالوگ استفاده شود.

اطلاعات FEC به دستگاه های ذخیره ساری انبوه (به انگلیسی: mass storage) (مغناطیسی، نوری، حالت جامد/ فلش ) اضافه میشود تا امکان بازیابی داده های آلوده (به انگلیسی: corrupted) را فراهم کند، و همچنین به عنوان حافظه کامپیوتری ECC در سیستم هایی که به شرایط ویژه ای برای اعتبار و اطمینان نیاز دارند استفاده می شوند.

حداکثر مقدار خطا ها یا بیت های گمشده ای که می تواند تصحیح شود بر اساس طراحی ECC تعیین می شود، بنابراین کد های FEC مختلف برای شرایط متفاوتی مناسب می باشند. به طور کلی ، یک کد قوی تر افزونگی (به انگلیسی: redundancy) بیشتر را ایجاد می کند که نیاز دارد توسط پهنای موجود منتقل شود و این کار نرخ بیت (به انگلیسی: bit-rate) موثر را کاهش و در عین حال نسبت سیگنال به نویز (به انگلیسی: signal-to-noise) موثر دریافت شده را افزایش می دهد. نظریه کدگذاری کانال پر نویز کلاد شانون (به انگلیسی: The noisy-channel coding theorem of Claude Shannon) در محاسبه حداکثر مقدار پهنای باند ارتباطی قابل دستیابی برای یک خطای احتمالی قابل قبول حداکثری استفاده می شود. این قضیه یک محدودیت بر حداکثر نرخ انتقال اطلاعات تئوری یک کانال همراه با سطحی از نویز پایه ی مشخص را بوجود می آورد. هرچند، اثبات آن مفید نیست و به این دلیل هیچ بینشی در مورد چگونگی ساخت یک کد درحال دستیابی به ظرفیت (به انگلیسی: capacity achieving code) ارائه نمی دهد. بعد از سال ها تحقیق و پژوهش، برخی از سیستم های FEC پیشرفته همانند کد قطبی (به انگلیسی: polar code) به حداکثر نظری ای که در ظرفیت کانال شانون تحت عنوان قاب با طول بینهایت (به انگلیسی: infinite length frame) مطرح شده، نزدیک شده اند.

جستارهای وابسته

• Burst error-correcting code
• Code rate
• Erasure codes
• تشخیص و تصحیح خطا
• Error-correcting codes with feedback
• کد خطی
• تصحیح خطای کوانتومی
• Soft-decision decoder

منابع

• "Hamming codes for NAND flash memory devices" Archived 21 August 2016 at the Wayback Machine. EE Times-Asia. Apparently based on "Micron Technical Note TN-29-08: Hamming Codes for NAND Flash Memory Devices" Archived 29 August 2017 at the Wayback Machine. 2005. Both say: "The Hamming algorithm is an industry-accepted method for error detection and correction in many SLC NAND flash-based applications."
• Tse, David; Viswanath, Pramod (2005), Fundamentals of Wireless Communication, Cambridge University Press, UK
• Charles Wang; Dean Sklar; Diana Johnson (Winter 2001–2002). "Forward Error-Correction Coding". Crosslink. 3 (1). The Aerospace Corporation. Archived from the original on 14 March 2012. Retrieved 5 March 2006.
• Charles Wang; Dean Sklar; Diana Johnson (Winter 2001–2002). "Forward Error-Correction Coding". Crosslink. 3 (1). The Aerospace Corporation. Archived from the original on 14 March 2012. Retrieved 5 March 2006. How Forward Error-Correcting Codes Work]
• Maunder, Robert (2016). "Overview of Channel Coding"
• Glover, Neal; Dudley, Trent (1990). Practical Error Correction Design For Engineers (Revision 1.1, 2nd ed.). CO, USA: Cirrus Logic. ISBN 0-927239-00-0.
• Hamming, Richard Wesley (April 1950). "Error Detecting and Error Correcting Codes". Bell System Technical Journal. 29 (2). USA: AT&T: 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. S2CID 61141773.