Reed-Solomon-kode

Reed-Solomon-koder er en gruppe af fejlkorrigerende koder, som blev introduceret af Irving S. Reed og Gustave Solomon i 1960. Reed-Solomon-koder har mange anvendelser, de mest prominente af disse omfatter forbrugerteknologier såsom CD'er, DVD'er, Blu-ray Discs, QR-koder, datatransmissionsteknologier såsom DSL og WiMAX, broadcast-systemer såsom DVB and ATSC, og datalagringssystemer såsom RAID 6. Reed-Solomon-koder anvendes også i satellitkommunikation.

Eksempler

En Reed-Solomon-kode specificeres som RS(n,k) med s paritetssymboler. Fuldt kodeord = n = 2^s - 1. Meddelelsesstørrelsen i det fulde kodeord er k.

Reed-Solomon-koder er i stand til at detektere og korrigere flere symbolfejl i en fuldt kodeord. Ved at tilføje $2*t$ tjeksumsymboler til dataene, kan en Reed-Solomon-kode detektere enhver kombination af op til $2*t$ fejlsymboler - eller korrigere op til $t$ fejlsymboler hvorsomhelst i det fulde kodeord.

RS(255,223)

Fx RS(n=255,k=223) med 8-bit (= 1 byte) symboler.

n = 255 bytes, k = 223 bytes, s = log2(n+1) = log2(255+1) = 8 bytes

Så er 2t = n-k = 255-223 = 32 max antal detekterbare symbolfejl, t = 16 max antal korrigerbare symbolfejl

Referencer

↑ Reed & Solomon (1960)
↑ Hagenauer, J.; Offer, E.; Papke, L. (1994). "11. Matching Viterbi Decoders and Reed-Solomon Decoders in a Concatenated System". Reed Solomon Codes and Their Applications. IEEE Press. s. 433. ISBN 9780470546345. OCLC 557445046.
1 2 3 Posted on Jun 13 2021, berthub.eu: Practical Reed-Solomon for Programmers, backup Citat: "...A symbol can be 8 bits long and equal a byte, but this does not have to be the case...."
1 2 3 4 cs.cmu.edu: Reed-Solomon Codes. An introduction to Reed-Solomon codes: principles, architecture and implementation, backup

Yderligere læsning

Gill, John (n.d.), EE387 Notes #7, Handout #28 (PDF), Stanford University, arkiveret fra originalen (PDF) 30. juni 2014, hentet 21. april 2010
Hong, Jonathan; Vetterli, Martin (august 1995), "Simple Algorithms for BCH Decoding" (PDF), IEEE Transactions on Communications, 43 (8): 2324-2333, doi:10.1109/26.403765
Lin, Shu; Costello, Jr., Daniel J. (1983), Error Control Coding: Fundamentals and Applications, New Jersey, NJ: Prentice-Hall, ISBN 0-13-283796-X
Massey, J. L. (1969), "Shift-register synthesis and BCH decoding" (PDF), IEEE Transactions on Information Theory, IT-15 (1): 122-127, doi:10.1109/tit.1969.1054260
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.; 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, arkiveret fra originalen (PDF) 2. juli 2010, hentet 9. september 2018

Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy
Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory (Revised udgave), Laguna Hills, CA: Aegean Park Press, ISBN 0-89412-063-8
Cipra, Barry A. (1993), "The Ubiquitous Reed–Solomon Codes", SIAM News, 26 (1)
Forney, Jr., G. (oktober 1965), "On Decoding BCH Codes", IEEE Transactions on Information Theory, 11 (4): 549-557, doi:10.1109/TIT.1965.1053825
Koetter, Ralf (2005), Reed–Solomon Codes, MIT Lecture Notes 6.451 (Video), arkiveret fra originalen 2013-03-13
MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company
Reed, Irving S.; Chen, Xuemin (1999), Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers

Eksterne henvisninger

[1] Reed & Solomon (1960)

[Hagenauer-2] Hagenauer, J.; Offer, E.; Papke, L. (1994). "11. Matching Viterbi Decoders and Reed-Solomon Decoders in a Concatenated System". Reed Solomon Codes and Their Applications. IEEE Press. s. 433. ISBN 9780470546345. OCLC 557445046.

[berthub2021-3] 1 2 3 Posted on Jun 13 2021, berthub.eu: Practical Reed-Solomon for Programmers, backup Citat: "...A symbol can be 8 bits long and equal a byte, but this does not have to be the case...."

[Richardson-4] 1 2 3 4 cs.cmu.edu: Reed-Solomon Codes. An introduction to Reed-Solomon codes: principles, architecture and implementation, backup