تصحیح خطای رید-سالامون
در نظریّهٔ کدگذاری، کدهای 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 معروف است.
محتویات |
See also [ویرایش]
- Forward error correction
- BCH code
- Low-density parity-check code
- Chien search
- ماتریس داده
- Tornado codes
- Finite ring
Notes [ویرایش]
- ↑ A popular construction is a concatenation of an outer RS code with an inner convolutional code, since the latter delivers errors primarily in bursts.
References [ویرایش]
- Cipra, Barry A. (1993), "The Ubiquitous Reed-Solomon Codes", SIAM News 26 (1), http://www.eccpage.com/reed_solomon_codes.html
- 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 0894120638
- 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, Stanford University, http://www.stanford.edu/class/ee387/handouts/notes7.pdf, retrieved April 21, 2010
- Hong, Jonathan; Vetterli, Martin (August 1995), "Simple Algorithms for BCH Decoding", IEEE Transactions on Communications 43 (8): 2324–2333
- Koetter, Ralf (2005), Reed-Solomon Codes, MIT Lecture Notes 6.451 (Video), http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-451Spring-2005/LectureNotes/detail/embed10.htm
- 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", IEEE Transactions on Information Theory IT-15 (1): 122–127, http://crypto.stanford.edu/~mironov/cs359/massey.pdf
- 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, Lecture Notes, http://csi.usc.edu/PDF/RSoriginal.pdf
External links [ویرایش]
- Schifra Open Source C++ Reed–Solomon Codec
- Henry Minsky's RSCode library، Reed–Solomon encoder/decoder
- A Tutorial on Reed–Solomon Coding for Fault-Tolerance in RAID-like Systems
- Algebraic soft-decoding of Reed–Solomon codes
- Matlab implementation of errors and-erasures Reed-Solomon decoding
- BBC R&D White Paper WHP۰۳۱
