Fejlkorrigerende kode
Inden for datalogi, telekommunikation, informationsteori og kodningsteori er fejlkorrigerende kode (engelsk forward error correction (FEC)[2] en teknik, der anvendes for afprøvning og fejlkorrigering af datafejl i datatransmission over upålidelige kommunikationskanaler eller kommunikationskanaler med støj.
Den centrale idé er, at afsenderen koder databeskeden på en redundant måde, oftest ved hjælp af en FEC.[3][4] Redundansen giver modtageren ikke kun mulighed for at opdage datafejl, der kan opstå hvor som helst i beskeden, men ofte også for at rette et begrænset antal datafejl. Derfor er en returkanal til at anmode om retransmission muligvis ikke nødvendig. Omkostningerne er en fast, større kanalbåndbredde.
Den amerikanske matematiker Richard Hamming var pioner på dette område i 1940'erne og opfandt den første fejlkorrigerende kode i 1950: Hamming (7,4)-koden.[4]
FEC kan anvendes i situationer, hvor retransmissioner er dyre eller umulige, såsom envejskommunikationsforbindelser eller ved transmission til flere modtagere via multicast.
Forbindelser med stor tidsforsinkelse drager også fordel af dette; I tilfælde af satellitter i kredsløb om fjerne planeter, ville retransmission på grund af fejl skabe en forsinkelse på flere timer. FEC bruges også i vid udstrækning i modemer og i mobilnetværk.
FEC-behandling i en modtager kan anvendes på en datastrøm eller i demodulationen af en digitalt moduleret bærebølge. For sidstnævnte er FEC en integreret del af den indledende analog-til-digital-konvertering i modtageren. Viterbi-dekoderen implementerer en soft-decision-algoritme til at demodulere digitale data fra et analogt signal med tilføjet støj. Mange FEC-dekodere kan også generere et bit-fejlrate (engelsk bit-error rate, BER) signal, som kan bruges som feedback til at finjustere den analoge modtageelektronik.
FEC-information tilføjes til baggrundslagre (magnetiske, optiske og solid state/flash-baserede) for at muliggøre gendannelse af ødelagte data og bruges som ECC-computerhukommelse på systemer, der kræver særlige bestemmelser for dataintegritet.
Den maksimale andel af fejl eller manglende bits, der kan korrigeres for, bestemmes af FEC'ens design, så forskellige fejlkorrigerende koder er egnede til forskellige forhold. Generelt inducerer en stærkere kode mere redundans, der skal transmitteres ved hjælp af den tilgængelige båndbredde, hvilket reducerer den effektive bitrate, samtidig med at det modtagne effektive signal-støj-forhold forbedres. Claude Shannons kanalkodningssætning (en) kan bruges til at beregne den maksimalt opnåelige kommunikationsbåndbredde for en given maksimal acceptabel fejlsandsynlighed. Dette sætter grænser for den teoretiske maksimale informationsoverførselshastighed for en kanal med et givet basisstøjniveau. Beviset er dog ikke konstruktivt og giver derfor ingen indsigt i, hvordan man opbygger en kapacitetsopnående kode. Efter års forskning kommer nogle avancerede FEC-systemer som polarkode (en)[5] meget tæt på det teoretiske maksimum givet af Shannon-kanalens kapacitet under hypotesen om en uendelig længde af rammen.
Referencer
[redigér | rediger kildetekst]- ↑ 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.
- ↑ Charles Wang; Dean Sklar; Diana Johnson (Winter 2001-2002). "Forward Error-Correction Coding". Crosslink. The Aerospace Corporation. 3 (1). Arkiveret fra originalen 14 marts 2012. Hentet 5 marts 2006.
{{cite journal}}: CS1-vedligeholdelse: Dato automatisk oversat (link) CS1-vedligeholdelse: Dato-format (link) - ↑ Glover, Neal; Dudley, Trent (1990). Practical Error Correction Design For Engineers (Revision 1.1, 2nd udgave). CO, USA: Cirrus Logic. ISBN 0-927239-00-0.
- 1 2 Hamming, Richard Wesley (april 1950). "Error Detecting and Error Correcting Codes". Bell System Technical Journal. USA: AT&T. 29 (2): 147-160. Bibcode:1950BSTJ...29..147H. doi:10.1002/j.1538-7305.1950.tb00463.x. hdl:10945/46756. S2CID 61141773.
{{cite journal}}: CS1-vedligeholdelse: Dato automatisk oversat (link) - ↑ Maunder, Robert (2016). "Overview of Channel Coding".
Yderligere læsning
[redigér | rediger kildetekst]- MacWilliams, Florence Jessiem; Sloane, Neil James Alexander (2007) [1977]. Skrevet i AT&T Shannon Labs, Florham Park, New Jersey, USA. The Theory of Error-Correcting Codes. North-Holland Mathematical Library. Vol. 16 (digital print of 12th impression, 1st udgave). Amsterdam / London / New York / Tokyo: North-Holland / Elsevier BV. ISBN 978-0-444-85193-2. LCCN 76-41296. (xxii+762+6 pages)
- Clark, Jr., George C.; Cain, J. Bibb (1981). Error-Correction Coding for Digital Communications. New York, USA: Plenum Press. ISBN 0-306-40615-2.
- Arazi, Benjamin (1987). Swetman, Herb (red.). A Commonsense Approach to the Theory of Error Correcting Codes. MIT Press Series in Computer Systems. Vol. 10 (1 udgave). Cambridge, Massachusetts, USA / London, UK: Massachusetts Institute of Technology. ISBN 0-262-01098-4. LCCN 87-21889. (x+2+208+4 pages)
- Wicker, Stephen B. (1995). Error Control Systems for Digital Communication and Storage. Englewood Cliffs, New Jersey, USA: Prentice-Hall. ISBN 0-13-200809-2.
- Wilson, Stephen G. (1996). Digital Modulation and Coding. Englewood Cliffs, New Jersey, USA: Prentice-Hall. ISBN 0-13-210071-1.
- "Error Correction Code in Single Level Cell NAND Flash memories" 2007-02-16
- "Error Correction Code in NAND Flash memories" 2004-11-29
- Observations on Errors, Corrections, & Trust of Dependent Systems, by James Hamilton, 2012-02-26
- Sphere Packings, Lattices and Groups, by J. H. Conway, Neil James Alexander Sloane, Springer Science & Business Media, 2013-03-09 – Mathematics – 682 pages.
Eksterne henvisninger
[redigér | rediger kildetekst]- Youtube: Forelæsning om "Fejlkorrigerende koder", Aalborg Universitet, AAU Play (dansk)
- Morelos-Zaragoza, Robert (2004). "The Correcting Codes (ECC) Page". Hentet 2006-03-05.
- error correction zoo. Database of error correcting codes.
- lpdec: library for LP decoding and related things (Python)