پرش به محتوا

تصحیح خطای رید-سالامون

از ویکی‌پدیا، دانشنامهٔ آزاد
نظریه گذاری

در نظریّهٔ کدگذاری، کدهای Reed–Solomon یا به اختصار (RS) در واقع کدهای غیردودویی هستند که نشانه ورودی از نوع مجموعه ای بزرگتر از ۲ هستند. کدهای تصحیح خطا دایره ای توسط ایروینگ اس رید و گوستاو سولومون اختراع شد. آن‌ها یک روش سیستماتیک برای ساختن کدهایی که می‌توانند چندین خطای نشانه تصادفی توصیف کردند. با اضافه کردن t نشانه بررسی به داده، یک کد RS می‌تواند هر ترکیب از t نشانه خطادار را تشخیص دهد، و تا ⌊t/۲⌋ نشانه را تصحیح کند. به عنوان یک کد قابل حذف شدن، می‌تواند تا t نشانه قابل پاک شدن را تصحیح کنkد، یا به نوعی می‌توان گفت که می‌تواند ترکیبی از خطاها و کدهای قابل پاک شدن را تشخیص و تصحیح کند.

به علاوه، از آنجا که توالی b+۱ خطای بیتی می‌تواند حداکثر دو نشانه با اندازه b را تحت تأثیر قرار دهد، کدهای RS برای استفاده به صورت تصحیح خطای بیتی مسلسل‌وار مناسب است.[۱] انتخاب t بستگی به طراح کد دارد، و می‌تواند در محدوده عریضی انتخاب شود.

در کدکردن رید-سالامون، نشانه‌های منبع به صورت ضرایب یک چندجمله‌ای p(x) بر روی یک طول محدود تعریف می‌شود. ایده اصلی تولید n نشانه کد از k نشانه منبع با استفاده از فرانمونه‌برداری (p(x در n > k نقطه متفاوت، فرستادن نقطه‌های نمونه‌برداری شده، و استفاده از تکنیک میانیابی در گیرنده برای بازسازی پیام اصلی است. امروزه کدهای RS بدین روش مورد استفاده قرار نمی‌گیرند. در عوض، کدهای RS به صورت کد BCH دوره‌ای، که نشانه‌های رمزکننده از روی ضرایب یک چندجمله‌ای که با استفاده از جاصلضرب p(x) و یک چندجمله‌ای مولد دوره‌ای ساخته می‌شود بدست می‌آید.

این کار به یک الگوریتم رمزگشایی مؤثر منجر می‌شود، که توسط Elwyn Berlekamp و James Massey کشف شد، و به الگوریتم رمزگشایی Berlekamp-Massey معروف است.

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

[ویرایش]

پانویس

[ویرایش]
  1. A popular construction is a concatenation of an outer RS code with an inner convolutional code, since the latter delivers errors primarily in bursts.

منابع

[ویرایش]
  • Cipra, Barry A. (1993), "The Ubiquitous Reed-Solomon Codes", SIAM News, 26 (1)
  • Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy
  • Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory, Laguna Hills, CA: Aegean Park Press, ISBN 0-89412-063-8 {{citation}}: Unknown parameter |ed= ignored (help)
  • Forney, Jr., G. (1965), "On Decoding BCH Codes", IEEE Transactions on Information Theory, IT-11: 549–557
  • Gill, John (unknown), EE387 Notes #7, Handout #28 (PDF), Stanford University, archived from the original (PDF) on 30 June 2014, retrieved April 21, 2010 {{citation}}: Check date values in: |year= (help)
  • Hong, Jonathan; Vetterli, Martin (August 1995), "Simple Algorithms for BCH Decoding", IEEE Transactions on Communications, 43 (8): 2324–2333{{citation}}: نگهداری یادکرد:تاریخ و سال (link)
  • Koetter, Ralf (2005), Reed-Solomon Codes, MIT Lecture Notes 6.451 (Video)
  • Lin, Shu; Costello, Jr., Daniel J. (1983), Error Control Coding: Fundamentals and Applications, New Jersey, NJ: Prentice-Hall, ISBN 0-13-283796-X
  • MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company
  • Massey, J. L. (1969), "Shift-register synthesis and BCH decoding" (PDF), IEEE Transactions on Information Theory, IT-15 (1): 122–127
  • Peterson, Wesley W. (1960), "Encoding and Error Correction Procedures for the Bose-Chaudhuri Codes", IRE Transactions on Information Theory, Institute of Radio Engineers, IT-6: 459–470
  • Reed, Irving S.; Chen, Xuemin (1999), Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers
  • Reed, Irving S.; Solomon, Gustave (1960), "Polynomial Codes over Certain Finite Fields", Journal of the Society for Industrial and Applied Mathematics (SIAM), 8 (2): 300–304, doi:10.1137/0108018
  • Welch, L. R. (1997), The Original View of Reed-Solomon Codes (PDF), Lecture Notes, archived from the original (PDF) on 2 July 2010, retrieved 28 April 2010

پیوند به بیرون

[ویرایش]