کدهای تصحیحکننده خطا
کدهای تصحیحکننده خطا افزونگی ساختاریافتهای را به دادهها اضافه میکنند تا خطاهای ایجاد شده در طول انتقال یا ذخیرهسازی قابل شناسایی و تصحیح باشند.
Definition
کد مجموعهای از کلمات کد است که معمولاً رشتههایی بر روی یک الفبای متناهی هستند و به گونهای انتخاب میشوند که هر دو کلمه کد در موقعیتهای کافی با یکدیگر تفاوت داشته باشند تا خطاهایی که چند نماد را تغییر میدهند، با رمزگشایی به نزدیکترین کلمه کد، قابل شناسایی یا تصحیح باشند.
Scope
این موضوع پارامترهای اساسی کدهای بلوکی – طول، بعد، و حداقل فاصله – متریک همینگ، کدهای خطی و ماتریسهای مولد و بررسی توازن آنها، و خانوادههای کلیدی مانند کدهای همینگ، رید-سولومون، BCH و رید-مولر را پوشش میدهد. همچنین کرانهای بنیادی بر پارامترهای کد، شامل کرانهای سینگلتون، همینگ و گیلبرت-وارشاموف را معرفی میکند.
Core questions
- با توجه به حداقل فاصله یک کد، چند خطا را میتواند شناسایی و تصحیح کند؟
- کدهای خوب چگونه بر روی میدانهای متناهی ساخته میشوند؟
- مبادلات اساسی بین طول، نرخ و فاصله چیست؟
- کدها چگونه میتوانند به طور کارآمد رمزگشایی شوند؟
Key concepts
- فاصله و وزن همینگ
- حداقل فاصله
- کدهای خطی
- ماتریسهای مولد و بررسی توازن
- کدهای همینگ و رید-سولومون
- کرانهای سینگلتون و همینگ
Key theories
- حداقل فاصله و تصحیح خطا
- یک کد با حداقل فاصله همینگ d میتواند تا d-1 خطا را شناسایی کند و تا کف (d-1)/2 خطا را تصحیح کند، که اصل مرکزی ارتباط جدایی هندسی کلمات کد با قابلیت مدیریت خطا است.
- کران سینگلتون و کدهای MDS
- حداقل فاصله یک کد با طول n و بعد k نمیتواند از n-k+1 تجاوز کند؛ کدهایی که این کران را با برابری برآورده میکنند، مانند کدهای رید-سولومون، کدهای با حداکثر فاصله جداپذیر (MDS) هستند و بهینه کارآمد میباشند.
Clinical relevance
کدهای تصحیحکننده خطا در ارتباطات و ذخیرهسازی دیجیتال ضروری هستند: آنها از دادهها در دیسکهای فشرده و هارد دیسکها، در کدهای QR، لینکهای سلولی و ماهوارهای، و انتقال در فضای عمیق محافظت میکنند، و به طرحهای ترکیبیاتی و هندسه متناهی مرتبط میشوند.
History
قضیه کدگذاری کانال شانون در سال ۱۹۴۸ ثابت کرد که ارتباط قابل اعتماد در زیر ظرفیت امکانپذیر است، و کدهای همینگ در سال ۱۹۵۰ اولین ساختار عملی را ارائه دادند و نظریه کدگذاری را به عنوان یک رشته علمی پایهگذاری کردند.
Key figures
- Claude Shannon
- Richard Hamming
- Irving Reed
Related topics
Seminal works
- macwilliams1977
- vanlintcoding1999
Frequently asked questions
- یک کد چگونه بدون دانستن محل خطا، آن را تصحیح میکند؟
- از آنجا که کلمات کد معتبر با فاصله زیادی از هم قرار دارند، یک کلمه دریافتی با خطاهای کم به دقیقاً یک کلمه کد نزدیکتر است، و رمزگشایی به نزدیکترین کلمه کد، کلمه اصلی را بازیابی میکند.
- تفاوت بین شناسایی و تصحیح چیست؟
- شناسایی فقط نشان میدهد که خطایی رخ داده است و ممکن است درخواست ارسال مجدد کند، در حالی که تصحیح مستقیماً دادههای مورد نظر را بازیابی میکند؛ تصحیح به حداقل فاصله بزرگتری نیاز دارد.