Feiloppdagelse og korreksjon - Error detection and correction

For å rydde opp i overføringsfeil som ble introdusert av jordens atmosfære (til venstre), brukte Goddard -forskere Reed - Solomon feilkorreksjon (til høyre), som vanligvis brukes på CDer og DVDer. Typiske feil inkluderer manglende piksler (hvit) og falske signaler (svart). Den hvite stripen indikerer en kort periode da overføringen ble stoppet.

I informasjonsteori og kodeteori med applikasjoner innen datavitenskap og telekommunikasjon , er feildeteksjon og korreksjon eller feilkontroll teknikker som muliggjør pålitelig levering av digitale data over upålitelige kommunikasjonskanaler . Mange kommunikasjonskanaler er utsatt for kanalstøy , og dermed kan det innføres feil under overføring fra kilden til en mottaker. Feildeteksjonsteknikker gjør det mulig å oppdage slike feil, mens feilretting muliggjør rekonstruksjon av originaldata i mange tilfeller.

Definisjoner

Feildeteksjon er deteksjon av feil forårsaket av støy eller andre svekkelser under overføring fra senderen til mottakeren.

Feilretting er påvisning av feil og rekonstruksjon av de opprinnelige, feilfrie dataene.

Historie

I den klassiske antikken ble kopister av den hebraiske bibelen betalt for arbeidet sitt i henhold til antall stikk (verslinjer). Siden prosabøkene i Bibelen nesten aldri ble skrevet med sting, måtte kopistene telle bokstavene for å estimere mengden arbeid. Dette bidro også til å sikre nøyaktighet i overføringen av teksten med produksjon av påfølgende kopier. Mellom det 7. og 10. århundre e.Kr. formaliserte og utvidet en gruppe jødiske skriftlærde dette for å lage den numeriske masoren for å sikre nøyaktig gjengivelse av den hellige teksten. Den inkluderte tellinger av antall ord i en linje, seksjon, bok og grupper av bøker, og noterte den midterste stikken i en bok, statistikk for bruk av ord og kommentarer. Standarder ble slik at et avvik i enda en bokstav i en Torah -bok ble ansett som uakseptabelt. Effektiviteten av deres feilkorrigeringsmetode ble bekreftet av nøyaktigheten av kopiering gjennom århundrene demonstrert ved oppdagelsen av Dødehavsrullene i 1947-1956, fra ca.150 f.Kr.-75 e.Kr.

Den moderne utviklingen av feilkorrigeringskoder er kreditert til Richard Hamming i 1947. En beskrivelse av Hamming kode dukket opp i Claude Shannon er en matematisk teori for kommunikasjon og ble raskt generalisert av Marcel JE Golay .

Introduksjon

Alle feiloppdagelses- og korreksjonsordninger legger til en viss redundans (dvs. noen ekstra data) i en melding, som mottakere kan bruke til å kontrollere konsistensen til den leverte meldingen, og for å gjenopprette data som er bestemt for å være ødelagt. Feiloppdagings- og korreksjonsordninger kan være enten systematiske eller ikke-systematiske. I et systematisk skjema sender senderen de originale dataene og legger ved et fast antall kontrollbiter (eller paritetsdata ), som er avledet fra databitsene av en deterministisk algoritme . Hvis bare feildeteksjon er nødvendig, kan en mottaker ganske enkelt anvende den samme algoritmen på de mottatte databitsene og sammenligne utgangen med de mottatte sjekkbitene; hvis verdiene ikke stemmer overens, har det oppstått en feil på et tidspunkt under overføringen. I et system som bruker en ikke-systematisk kode, blir den opprinnelige meldingen transformert til en kodet melding som bærer samme informasjon, og som har minst like mange biter som den opprinnelige meldingen.

God feilkontrollytelse krever at ordningen velges ut fra egenskapene til kommunikasjonskanalen. Vanlige kanalmodeller inkluderer minneløse modeller der feil oppstår tilfeldig og med en viss sannsynlighet, og dynamiske modeller der feil oppstår hovedsakelig i burst . Følgelig kan feiloppdagende og korrigerende koder generelt skilles mellom tilfeldige feiloppdagende/korrigerende og burst-feiloppdagende/korrigerende . Noen koder kan også være egnet for en blanding av tilfeldige feil og burst -feil.

Hvis kanalkarakteristikkene ikke kan bestemmes, eller er svært varierende, kan et feildeteksjonsskjema kombineres med et system for gjenoverføring av feilaktige data. Dette er kjent som automatisk gjentagelsesforespørsel (ARQ), og brukes mest på Internett. En alternativ tilnærming for feilkontroll er hybrid automatisk gjentagelsesforespørsel (HARQ), som er en kombinasjon av ARQ og feilkorrigeringskoding.

Typer feilretting

Det er tre hovedtyper av feilretting.

Automatisk gjentagelsesforespørsel (ARQ)

Automatic Repeat reQuest (ARQ) er en feilkontrollmetode for dataoverføring som bruker feildeteksjonskoder, bekreftelse og/eller negative bekreftelsesmeldinger og timeout for å oppnå pålitelig dataoverføring. En bekreftelse er en melding sendt av mottakeren for å indikere at den har mottatt en dataramme på riktig måte .

Vanligvis, når senderen ikke mottar bekreftelsen før tidsavbruddet inntreffer (dvs. innen rimelig tid etter at datarammen er sendt), sender den rammen på nytt til den enten er riktig mottatt eller feilen vedvarer utover et forhåndsbestemt antall gjenoverføringer .

Tre typer ARQ-protokoller er Stop-and-wait ARQ , Go-Back-N ARQ og Selective Repeat ARQ .

ARQ er passende hvis kommunikasjonskanalen har varierende eller ukjent kapasitet , slik som er tilfellet på Internett. Imidlertid krever ARQ tilgjengeligheten av en bakre kanal , fører muligens øket latenstid på grunn av gjentatte overføringer, og krever opprettholdelse av buffere og timere for gjentatte overføringer, noe som i tilfelle av nettverkstrafikken kan sette en belastning på serveren og generelle nettverkskapasitet.

For eksempel brukes ARQ på kortbølgede radiodatakoblinger i form av ARQ-E , eller kombinert med multipleksing som ARQ-M .

Videresend feilretting

Forward error correction (FEC) er en prosess for å legge til redundante data, for eksempel en feilkorrigerende kode (ECC) i en melding, slik at den kan gjenopprettes av en mottaker selv om det er et antall feil (opp til kodens evne ble brukt) ble introdusert, enten under overføringsprosessen eller under lagring. Siden mottakeren ikke trenger å be avsenderen om å overføre dataene på nytt, er det ikke nødvendig med en tilbakekanal for feilkorrigering fremover, og den er derfor egnet for enkel kommunikasjon som kringkasting . Feilkorrigerende koder brukes ofte i kommunikasjon med lavere lag , samt for pålitelig lagring i medier som CDer , DVDer , harddisker og RAM .

Feilrettende koder skilles vanligvis mellom konvolusjonskoder og blokkoder :

Shannons teorem er et viktig teorem for feilkorrigering fremover, og beskriver maksimal informasjonshastighet der pålitelig kommunikasjon er mulig over en kanal som har en viss feil sannsynlighet eller signal-til-støy-forhold (SNR). Denne strenge øvre grensen uttrykkes i form av kanalkapasitet . Nærmere bestemt sier teoremet at det finnes koder slik at med økende kodelengde kan sannsynligheten for feil på en diskret minneløs kanal gjøres vilkårlig liten, forutsatt at koderaten er mindre enn kanalkapasiteten. Koderaten er definert som brøkdelen k/n av k kildesymboler og n kodede symboler.

Den faktiske maksimale tillatte koderaten avhenger av den feilkorrigerende koden som brukes, og kan være lavere. Dette er fordi Shannons bevis bare var av eksistensiell karakter, og ikke viste hvordan man konstruerer koder som er både optimale og har effektive kodings- og dekodingsalgoritmer.

Hybridordninger

Hybrid ARQ er en kombinasjon av ARQ og feilkorrigering fremover. Det er to grunnleggende tilnærminger:

  • Meldinger overføres alltid med FEC-paritetsdata (og redundans for feiloppdagelse). En mottaker dekoder en melding ved hjelp av paritetsinformasjonen, og ber om gjenoverføring med ARQ bare hvis paritetsdataene ikke var tilstrekkelige for vellykket dekoding (identifisert gjennom en mislykket integritetskontroll).
  • Meldinger overføres uten paritetsdata (bare med informasjon om feiloppdagelse). Hvis en mottaker oppdager en feil, ber den om FEC -informasjon fra senderen ved hjelp av ARQ, og bruker den til å rekonstruere den opprinnelige meldingen.

Sistnevnte tilnærming er spesielt attraktiv på en slettingskanal når du bruker en rateløs slettingskode .


Feiloppdagelsesordninger

Feildeteksjon realiseres vanligvis ved bruk av en passende hashfunksjon (eller spesifikt en kontrollsum , syklisk redundanssjekk eller annen algoritme). En hashfunksjon legger til en tag med fast lengde i en melding, som gjør det mulig for mottakere å bekrefte den leverte meldingen ved å beregne taggen på nytt og sammenligne den med den som er gitt.

Det finnes et stort utvalg av forskjellige hashfunksjonsdesigner. Noen er imidlertid spesielt utbredt på grunn av enten deres enkelhet eller egnethet til å oppdage visse typer feil (f.eks. Den sykliske redundanssjekkens ytelse ved å oppdage burstfeil ).

Minimum avstandskoding

En tilfeldig feilkorrigeringskode basert på minimumsavstandskoding kan gi en streng garanti for antall påviselige feil, men den beskytter kanskje ikke mot et angrep på forhånd .

Gjentagelseskoder

En repetisjonskode er et kodingsskjema som gjentar bitene over en kanal for å oppnå feilfri kommunikasjon. Gitt en datastrøm som skal overføres, er dataene delt inn i blokker med biter. Hver blokk sendes et forhåndsbestemt antall ganger. For eksempel, for å sende bitmønsteret "1011", kan firebitsblokken gjentas tre ganger og dermed produsere "1011 1011 1011". Hvis dette tolv-biters mønsteret ble mottatt som "1010 1011 1011"-der den første blokken er ulik de to andre-har det oppstått en feil.

En repetisjonskode er svært ineffektiv, og kan være utsatt for problemer hvis feilen oppstår på nøyaktig samme sted for hver gruppe (f.eks. "1010 1010 1010" i forrige eksempel vil bli oppdaget som riktig). Fordelen med repetisjonskoder er at de er ekstremt enkle, og faktisk brukes i noen overføringer av tallstasjoner .

Paritetsbit

En paritetsbit er en bit som legges til en gruppe kildebiter for å sikre at antall settbiter (dvs. biter med verdi 1) i resultatet er like eller oddetall. Det er et veldig enkelt opplegg som kan brukes til å oppdage enkelt eller annet oddetall (dvs. tre, fem, etc.) av feil i utdata. Et jevnt antall vendte biter vil få paritetsbiten til å virke korrekt, selv om dataene er feil.

Paritetsbiter som legges til hvert "ord" som sendes kalles tverrgående redundanskontroller , mens de som legges til på slutten av en strøm av "ord" kalles langsgående redundanskontroller . For eksempel, hvis hver av en serie m-bit "ord" har en paritetsbit lagt til, som viser om det var et oddetall eller partall i det ordet, vil et hvilket som helst ord med en enkelt feil i det bli oppdaget. Det vil imidlertid ikke være kjent hvor feilen er i ordet. Hvis det i tillegg etter hver strøm av n ord sendes en paritetssum, som hver bit viser om det var et oddetall eller partall på den bitposisjonen som ble sendt i den siste gruppen, vil den nøyaktige plasseringen av feilen kan bestemmes og feilen rettes. Denne metoden er imidlertid garantert effektiv, hvis det ikke er mer enn 1 feil i hver gruppe med n ord. Med flere feilkorrigeringsbiter kan flere feil oppdages og i noen tilfeller korrigeres.

Det er også andre bitgrupperingsteknikker.

Sjekksum

En kontrollsum av en melding er en modulær aritmetisk sum av meldingskodeord med en fast ordlengde (f.eks. Byteverdier). Summen kan negeres ved hjelp av en en -komplement- operasjon før overføring for å oppdage utilsiktede alle-null-meldinger.

Sjekksum -ordninger inkluderer paritetsbiter, kontrollsifre og langsgående redundansjekk . Noen kontrollsum -ordninger, for eksempel Damm -algoritmen , Luhn -algoritmen og Verhoeff -algoritmen , er spesielt designet for å oppdage feil som mennesker vanligvis introduserer ved å skrive ned eller huske identifikasjonsnummer.

Syklisk redundanssjekk

En syklisk redundansjekk (CRC) er en usikker hashfunksjon designet for å oppdage utilsiktede endringer i digitale data i datanettverk. Det er ikke egnet for å oppdage skadelig innførte feil. Det er preget av spesifikasjon av et generatorpolynom , som brukes som divisor i en polynomdivisjon over et begrenset felt , og tar inndataene som utbytte . Den resterende blir resultatet.

En CRC har egenskaper som gjør den godt egnet til å oppdage burst -feil . CRC er spesielt enkle å implementere i maskinvare og brukes derfor ofte i datanettverk og lagringsenheter som harddiskstasjoner .

Paritetsbiten kan sees på som en spesiell 1-bits CRC.

Kryptografisk hashfunksjon

Utdataene fra en kryptografisk hashfunksjon , også kjent som en meldingsfordeling , kan gi sterke forsikringer om dataintegritet , enten endringer i dataene er tilfeldige (f.eks. På grunn av overføringsfeil) eller skadelig innført. Enhver endring av dataene vil sannsynligvis bli oppdaget gjennom en hash -verdi som ikke samsvarer. Gitt noen hash -verdi, er det vanligvis umulig å finne noen inndata (andre enn den som er gitt) som vil gi den samme hash -verdien. Hvis en angriper ikke bare kan endre meldingen, men også hashverdien, kan en nøkkelbasert hash- eller meldingsautentiseringskode (MAC) brukes for ytterligere sikkerhet. Uten å kjenne nøkkelen, er det ikke mulig for angriperen å enkelt eller praktisk beregne den riktige nøkkelverdien for en modifisert melding.

Feilkorrigeringskode

En hvilken som helst feilrettende kode kan brukes til feildeteksjon. En kode med minimum Hamming -avstand , d , kan oppdage opptil d - 1 feil i et kodeord. Å bruke minimumsavstandsbaserte feilkorrigerende koder for feildeteksjon kan være passende hvis man ønsker en streng grense for det minste antallet feil som skal oppdages.

Koder med minimum Hamming-avstand d = 2 er degenererte tilfeller av feilrettende koder, og kan brukes til å oppdage enkeltfeil. Paritetsbiten er et eksempel på en enkeltfeiloppdagende kode.

applikasjoner

Applikasjoner som krever lav ventetid (for eksempel telefonsamtaler) kan ikke bruke automatisk gjentagelsesforespørsel (ARQ); de må bruke fremover feilkorreksjon (FEC). Når et ARQ-system oppdager en feil og sender det på nytt, kommer de sendte dataene for sent til å være brukbare.

Programmer der senderen umiddelbart glemmer informasjonen så snart den sendes (for eksempel de fleste TV -kameraer) kan ikke bruke ARQ; de må bruke FEC fordi de originale dataene ikke lenger er tilgjengelige når det oppstår en feil.

Applikasjoner som bruker ARQ må ha en returkanal ; applikasjoner som ikke har noen returkanal, kan ikke bruke ARQ.

Applikasjoner som krever ekstremt lave feilrater (for eksempel digitale pengeoverføringer) må bruke ARQ på grunn av muligheten for feil som ikke kan korrigeres med FEC.

Pålitelighet og inspeksjonsteknikk bruker også teorien om feilrettende koder.

Internett

I en typisk TCP/IP -stabel utføres feilkontroll på flere nivåer:

  • Hver Ethernet-ramme bruker CRC-32 feildeteksjon. Rammer med oppdagede feil kastes av mottakerens maskinvare.
  • Den IPv4 Hodet inneholder en kontrollsum som beskytter innholdet i spissen. Pakker med feil kontrollsum slippes i nettverket eller på mottakeren.
  • Kontrollsummen ble utelatt fra IPv6 -overskriften for å minimere behandlingskostnadene i nettverksruting og fordi gjeldende koblingslagteknologi antas å gi tilstrekkelig feildeteksjon (se også RFC 3819).
  • UDP har en valgfri kontrollsum som dekker nyttelast og adresseringsinformasjon i UDP- og IP -overskriftene. Pakker med feil kontrollsum blir kastet av nettverksstakken . Kontrollsummen er valgfri under IPv4, og kreves under IPv6. Når den utelates, antas det at datalinkingslaget gir ønsket nivå av feilbeskyttelse.
  • TCP gir en kontrollsum for å beskytte nyttelasten og adressere informasjonen i TCP- og IP -overskriftene. Pakker med feil kontrollsum blir kastet av nettverksstakken, og blir til slutt sendt på nytt ved hjelp av ARQ, enten eksplisitt (for eksempel gjennom treveis håndtrykk ) eller implisitt på grunn av en timeout .

Deep-space telekommunikasjon

Utviklingen av feilkorrigeringskoder var tett forbundet med historien til dybdeoppdrag på grunn av ekstrem fortynning av signaleffekt over interplanetære avstander, og den begrensede strømtilgjengeligheten ombord på romprober. Mens tidlige oppdrag sendte dataene sine ukodede, fra 1968, ble digital feilkorrigering implementert i form av (sub-optimalt dekodede) konvolusjonskoder og Reed-Muller-koder . Reed - Muller -koden var godt egnet for støyen som romfartøyet ble utsatt for (tilnærmet matchende en klokkekurve ), og ble implementert for Mariner -romfartøyet og brukt på oppdrag mellom 1969 og 1977.

De Voyager 1 og Voyager 2 oppdrag, som startet i 1977, ble utviklet for å gi farge bildebehandling og vitenskapelig informasjon fra Jupiter og Saturn . Dette resulterte i økte kodingskrav, og romfartøyet ble dermed støttet av (optimalt Viterbi-avkodet ) konvolusjonelle koder som kunne kobles sammen med en ytre Golay (24,12,8) kode . Voyager 2 -båten støttet i tillegg en implementering av en Reed - Solomon -kode . Den sammenkoblede Reed - Solomon - Viterbi (RSV) -koden tillot svært kraftig feilretting, og muliggjorde romfartøyets forlengede reise til Uranus og Neptun . Etter oppgradering av ECC -systemet i 1989 brukte begge håndverkene V2 RSV -koding.

Den rådgivende komité for romdatasystemer anbefaler for øyeblikket bruk av feilkorrigeringskoder med ytelse som ligner på Voyager 2 RSV -koden som et minimum. Sammenkoblede koder faller i økende grad i unåde med romoppdrag, og erstattes av kraftigere koder som Turbo -koder eller LDPC -koder .

De forskjellige typene dype rom og orbitale oppdrag som utføres antyder at det å prøve å finne et feilrettingssystem som passer for alle vil være et pågående problem. For oppdrag nær Jorden, naturen av støy i kommunikasjonskanalen er forskjellig fra det som et romskip på en interplanetarisk oppdrag opplevelser. I tillegg, ettersom et romfartøy øker avstanden fra jorden, blir problemet med å korrigere for støy vanskeligere.

Satellittkringkasting

Etterspørselen etter satellitt transponder båndbredde fortsetter å vokse, drevet av ønsket om å levere TV (inkludert nye kanaler og HD-TV ) og IP-data. Transponder tilgjengelighet og båndbredde begrensninger har begrenset denne veksten. Transponderkapasitet bestemmes av det valgte moduleringsopplegget og andelen kapasitet som forbrukes av FEC.

Datalagring

Feildeteksjon og korreksjonskoder brukes ofte for å forbedre påliteligheten til datalagringsmedier. Et paritetsspor som var i stand til å oppdage enkeltbitfeil, var tilstede på det første magnetbåndets datalagring i 1951. Den optimale rektangulære koden som brukes i gruppekodede opptakstape oppdager ikke bare, men korrigerer også enkeltbitfeil. Noen filformater , spesielt arkivformater , inkluderer en kontrollsum (oftest CRC32 ) for å oppdage korrupsjon og avkorting og kan bruke redundans- eller paritetsfiler for å gjenopprette deler av ødelagte data. Reed-Solomon-koder brukes på CD-plater for å rette opp feil forårsaket av riper.

Moderne harddisker bruker Reed - Solomon -koder for å oppdage riktige mindre feil i sektorresninger, og for å gjenopprette ødelagte data fra sviktende sektorer og lagre dataene i reservedelsektorene. RAID -systemer bruker en rekke feilkorrigeringsteknikker for å gjenopprette data når en harddisk mislykkes helt. Filsystemer som ZFS eller Btrfs , samt noen RAID -implementeringer, støtter dataskrubbing og resilvering, noe som gjør at dårlige blokker kan oppdages og (forhåpentligvis) gjenopprettes før de brukes. De gjenopprettede dataene kan skrives om til nøyaktig samme fysiske plassering, for å spare blokker andre steder på den samme maskinvaren, eller dataene kan skrives om til erstatningsmaskinvare.

Feilretting minne

Dynamisk tilfeldig tilgangsminne (DRAM) kan gi sterkere beskyttelse mot myke feil ved å stole på feilkorrigerende koder. Slikt feilkorrigerende minne, kjent som ECC- eller EDAC-beskyttet minne, er spesielt ønskelig for misjonskritiske applikasjoner, for eksempel vitenskapelig databehandling, finansiell, medisinsk, etc. så vel som utenomjordiske applikasjoner på grunn av økt stråling i rommet.

Feilrettende minnekontrollere bruker tradisjonelt Hamming-koder , selv om noen bruker trippel modulær redundans . Interleaving tillater distribusjon av effekten av en enkelt kosmisk stråle som potensielt kan forstyrre flere fysisk nabobiter over flere ord ved å knytte nabobiter til forskjellige ord. Så lenge en enkelt hendelsesforstyrrelse (SEU) ikke overskrider feilgrensen (f.eks. En enkelt feil) i et bestemt ord mellom tilgangene, kan den korrigeres (f.eks. Med en enkeltbit feilkorrigerende kode), og illusjonen om et feilfritt minnesystem kan opprettholdes.

I tillegg til at maskinvare gir funksjoner som kreves for at ECC -minne skal fungere, inneholder operativsystemer vanligvis relaterte rapporteringsfasiliteter som brukes til å gi varsler når myke feil blir gjennomsiktig gjenopprettet. Et eksempel er den Linux-kjerne 's EDAC system (tidligere kjent som Bluesmoke ), som samler data fra feilsjekkings-aktiverte komponenter inne i et datasystem; i tillegg til å samle inn og rapportere hendelser relatert til ECC -minne, støtter den også andre sjekksummerfeil, inkludert de som er oppdaget på PCI -bussen . Noen få systemer støtter også skrubbing av minne for å fange opp og rette feil tidlig før det blir uopprettelig.

Se også

Referanser

Videre lesning

Eksterne linker