; TeX output 1998.07.27:1731n7o]{o]1СN cmbx12KLEINEٚEINF4UHRUNGINDIEKODIERUNGSTHEORIE}^K`y cmr10VORLESUNGUUVONB.P*AREIGISIMSS19986qsX"- cmcsc10Inhal32tsverzeichnis XQ cmr12Einleitung;1 1. DerSatzvronShannon81 2. DieHamming-Metrik=04 3. LineareCoSdesb^6 4. KonrtrollmatrizenundHamming-Metrik߹9 5. SystematiscrheCoSdes:.12 6. StandardtafelnundDekroSdierung@13 7. Hamming-CoSdesP16 8. ProlynomringeundendlicheKyorpSerp18 9. ZykliscrheCoSdesS~21 10. BeispieleinesBCH-CoSdes221f"XEinleitung Im]Sommersemester1998habSeicrhinderReihederFVortbildungsveranstaltungendesMa-thematiscrhen.InstitutsderLudwig-Maxililians-UniversityatMSyuncheneine1-stSyundigeVVorle-sung>6yubSerKodierungstheoriefyurLehreranGymnasieninBaryernangeboten. EsAwrardasZieldieserVVorlesung,BMeinenBegri yubSerdieMyoglichkeitunddieGrenzenvronCvielenheuteverwendetenKoSdierungsmyoglichkeitenzurFVehlerkorrekturzuvermitteln.NicrhtdievielenProblemederVVerscrhlSyusselungvonDaten,umZugri evonUnbSefugtenzukvrermeiden,ksonderndieTVechnikenzurVVermeidungoSderKorrekturvonFVehlernbSeiderwvpxUbSertragung0vronDatenstandenimMittelpunktderVVorlesung.REinfacheCoSdeslassensichscrhonNmitHilfsmittelnderlinearenAlgebraerstellen.DieDarstellungdieserMethoSdenundderMethoSdenderFVehlerkrorrekturstandenimMittelpunktderVorlesung.+DiemoSderneKoSdierungstheorie!vrerwendetzurErstellungleistungsfyahigererCoSdesHilfsmittelderZah-lenrtheorieundderalgebraischenundarithmetischenGeometrie.DaraufkonnteichwegenderKSyurzederZeitnicrhteingehen. MSyuncrhen,imJuli1998B.Pareigis2ˍ1.ˢDerSa32tzvonShannonBemerkung1.1.c5Informationen6yubSertragenwird. EinensolcrhenKanalnenntmaneinendiskrffeten,binyaren,symmetrischenKanalohneSpffeicher꨹(BSC).'Beispiele1.3.SfSyurKoSdierungen: 1)ִPrarityats-PrSyufsumme(ParityCheck):BeieinemComputerspSeicherverwendetmanzurSpSeicrherunghtvon1Byte(=8Bits)Bv=+p(b|{Ycmr81:::b8)einweiteresKontrollbitb9,halso9Bits,wrobSei7'das9.7KontrollbitwiefolgtbSestimmtwird:7bwennndieAnzahlderBitseinesBytesist,dieauf1gesetztsind,soistdas* wKonrtrollbit=URz"u cmex10( 1;jfalls5n꨹ungerade,ɍ 0;jfalls5n꨹gerade. [ZurbpxUbSerpryufungtestetman,obfyurdieSummealler>6yubertragenen9Bitsgiltj9jX ㇍k2cmmi8i=14bi,UR0 moSd&6(2): qɍWVennJdieseBedingungvrerletztist,^dannistsicherbSeiderpxUbertragungeinFVehleraufgetre-ten.6WVenn4eineinzigesBitfalscrhyubSertragenwird,5,dannwirddieseKontrollbSedingungschonvrerletzt.ZEineosolcheKoSdierungkXannalsoeinenFVehler(proyubertragenesByte)erkrennen.DiesesVVerfahrenwirdbSeivielenPCsvrerwendet.JWirdeinFehlererkXannrt,Msokanndiesernicrhtautomatischkorrigiertwerden,derComputerbleibtalsosicherheitshalbSerstehen. n7o]ʍkeKLEINE!EINF'ҟ UHR9UNGINDIEKODIERUNGSTHEORIEgXg3[o] 2)DasMorsealphabSet,6dasmitdenZeicrhen:(dit)und(dah)aufgebautwird.Genauerwrerdenpdie*"  Strings-l\pausdenBuchstabSenf:(dit),(dah),뀉zꨎ%(kurzePrause),뀉z G(langePrause)gBLgebildet.CMMitdiesenZeichenkyonnendieBuchstabSendesAlphabetsgebildetwrerden(z.B.a=.-;b=-...).De nition1.4.YWorterbuch derKo`dierung:EinCoffdeisteineMengeC`5(vronZeichen,diegeeignetist,InformationenzuspSeicrhernundzu>6yubermitteln). EineHChi rffeoSdereineVerschl'yusselung(KodierungoSderChi rierung)isteineAbbildungfQ:URC1V!C2einesCoSdesineinenanderen. Eine%Deffchi rierungeinerChi refQ:URC1V!C2)ist%eineAbbildunggË:URC2!C1)mit%gn9fQ=id . DieQuelleeinerChi ref2ù:C1 !C2 ߹heitKlartext,einElemenrtdesKlartextesheitNachrichtenwort. EinElemenrtdesBildeseinerChi reheitCoffdewort. EineKoSdierungheitlineffarerKodierung,:wrennC1undC2VVektorryaumesindundfQ:URC1V!C2einelineareAbbildungist. EinBloffckcodeisteinCoSde,dessenWyorterausBucrhstabeneinesAlphabets(trypischerweiseaus=denBits0und1)zusammengesetztsindundallegleicrheLyangehabSen,@d.h.ausgleichvielenBucrhstabSenbestehen. WirL bSetracrhtenhauptsyachlichKoSdierungenfG,L#dieinjektivsind.LFVallsdiesnichtderFVallist,!istdieobSenangegebeneBedingungfyureineDekrodierungnicrhterfyullbar.rEsgibtjedocrhBeispiele,indeneneineKoSdierungmiteinernicrhtinjektivenAbbildungsinnvollist,z.B.dieGraphik-Kompressions-ProtokrolleJPEG,GIFundandere.Beispiele1.5.SfSyurCoSdesundKodierungen: 1)SpracrhensindbSeliebigeMengen(unddamitCodes)vron*" ustrings-l\oderWyorternayubereinembSeliebigenAlphabetA. 2)#DasZahlensystem,$d.h.diemitdenZi ern0;:::ʚ;9unddenZeicrhen:unddarge-stelltenZahlen,isteinCoSde. 3)WRDieqn9-unddiez-GruppSeninderMorsespracrhe,WxdassindGruppenvrondreiBuchstabSendes(BucrhstabSen-)Alphabets,diemitq_%bzw.zyϹbeginnen,z.B.qth=Standort,bildeneinenCoSde. 4)DieBarcoSdeszurBezeicrhnungvonWVarenimSupSermarktsindCodes. 5)'DerISBN-CoSde(InrternationalStandardBookNumrber),iwiez.B.3-519-02211-7,isteinCoSde,wrobeidieeinzelnenGruppenfolgendesbedeuten: 1.#3=Erscrheinungsland 2.#519=VVerlag 3.#02211=fortlaufendeBucrhnummer 4.#7=PrSyufnrummer(inf0;1;2;3;4;5;6;7;8;9;Xg).Cx$DieOPrSyufungaufeinekrorrekte]şpxUbSertragung(FVehlererkennung)geschiehtimBeispieledurcrhpx UbSerpryufungvron10!3+95+81+79+60+52+42+31+21+17UR0moSd":11.DieRestklassenrbSerechnungmoSdulo11kXanndurchBildungderalternierendenQuersummevrorgenommenwerden.(http://infoshare1.princeton.edu/kXatmandu/marc/aut020.html)$6)pBeliebigerTVextderUmgangsspracrhekXannineinenlinearenCoSdeKܞ2n u^fyurK=GFƹ(qn9)Ty.ubSersetztwrerden,uindemmanzunyachstdenTVextjeweilsinGruppSenvonlDBuch-stabSenZundAbstyande(undevtl.tsonstigeZeicrhen)zusammenfat.BeiderVVerwrendungvona;:::ʚ;z;A;:::;Z5;Zwischenrffaumђsindalso532lZvrerschiedeneђsolcheTVextgruppSenmyoglich.DiesenqBwreistmanineinerbSeliebigfestzulegendenWVeiseebensovielevrerschiedeneqBElemente inKܞ2n ozu.DamitbSestimmrtsichl.7aus532lwURqn92n 1alslnG`ln ((qI{)۟z1ܟꍍln\(53)B.n7o]&e4V9ORLESUNG!VONB.P:AREIGISIMSS1998[o]Bemerkung1.6.c5WirwrerdenimfolgendenimmerBloSckcodesverwenden,@d.h.dieEle-menrte$derbSeidenCodeseinerKodierunghabenallegleicrheLyange,+z.B.gleicheAnzahlvonBits.2EinBloScrkcodederLyangek.hatalsoqn92k YWyorter,wrennq6dieAnzahlderZeichendesvrerwendetenAlphabSetsist,alsofyurf0;1gistqË=UR2.e WirvvrerwendenzurMpxUbSertragungeinenbinyaren,|symmetrischenKanal(BSC).WVenneineKoSdierungmitBlocrkcodesfo:'C1 !C2 gegebenist,wrobeiC1 WyorterderLyangekcundC2^Wyorter4ZderLyangenbSesitztunddasvrerwendete4ZAlphabetf0;1gist,4msowrerdenbeiderwvpxUbSertragung1vronnBits,kalsoinnZeiteinheitenlediglichkoNInformationsbits[yubSermittelt. DieDurffchsatzratederKoSdierungistdannkg=n.*WVeiteristdieBit-Fehler-WahrscheinlichkeitdieWVahrscrheinlichkeit,Uda.einBiteinesKlartextrwortes.trotzerfolgterFehlerkrorrekturfalschankrommt. WirformrulierenjetztdenSatzvonShannon,ohneihnallerdingszubSeweisen.ErdientzumOVVerstyandnisderMyoglicrhkeitenOderKoSdierungstheorieundauerdemalsMotivXationdafSyur,myoglicrhstvieleverschiedeneKoSdierungenzu ndenundzustudieren.Theorem1.7.TDerSatzvonShannonM(ClaudeShannon:UAmathematicaltheoryofcommrunicationn-1948.)ASeieinbinyarffersymmetrischerKanalmiteinerBit-Fehler-Wahr-scheinlichkeit Q0pй0, dieKanalkXapazityat,soda:eszujeffdem">0:undzujederDurchsatzrate0mʟcfd1Lcfd1UПpfd aUПҬfd aUПfd aUП&fd aUПcfd a큃I0.1־^I0.29I0.38I0.4tI0.5zEI0R.„ afej„ afeRʟ„ afe>:„ afeb`1b̞.2b3b>m4bU0PwByZÄfdfewnP Afdfewofdfew֟ffdfewfdfex |ġfdfexMsӄfdfex{;#"fdfex қfdfex8fdfey}1fdfey4ބfdfeycfdfey:Bfdfeyefdfey|ڄfdfez!ySsfdfezQ͟fdfezifdfezMffdfezy+fdfe{؟wfdfe{Gyfdfe{y+{fdfe{3fdfe{tfdfe|5Afdfe|DWfdfe|w_fdfe|sWʄfdfe|m Yfdfe} fdfe}Hofdfe}|"ބfdfe}fdfe}d@fdfe~<fdfe~Rٟ fdfe~񣻄fdfe~Wfdfe~Y fdfe-@𿝄fdfedsۄfdfe6(=fdfeÄfdfe LmfdfeDF;fdfe}SfdfeYfdfe履eLfdfe)=fdfeb*fdfe τfdfez;fdfe/fdfeM,짖fdfe9]˄fdfeşfdfegfdfe;fdfex7˄fdfefdfe{꥿fdfe.\fdfel9Cfdfe˻fdfe՟Wfdfe&/:Ԅfdfedџfdfe誾fdfebfdfe" 8fdfeaӫfdfeBfdfe;Dfdfe"ԟ܄fdfeci߄fdfeofdfe)fdfe'qfdfeifdfeUfdfe?fdfe1ɑfdfet5䃳fdfe=fdfecfdfe>㲚fdfe)mKfdfeǯ( fdfe }fdfeQ86fdfeYwfdfe:܄fdfe"'efdfeh\fdfeyGfdfe=wfdfefdfe̵e„fdfe,ퟻ9fdfeͣpTfdfeIӄfdfeΓjvfdfe ӟ=fdfeτa(fdfei67fdfeu Ufdfe1߫fdfei%fdfeÄfdfe\``fdfe6kfdfeQ ufdfe-⣄fdfeHfdfeUkfdfe?cdfdfeջ;fdfe8Wfdfeֵ=鉄fdfe1Hfdfe׮fdfe,zopfdfeتGfdfe(̟fdfe٦9fdfe%sfdfeڤ9fdfe#}߄fdfeۣYVKfdfe"(.ۄfdfeܢkfdfe"gfdfeݣɟcfdfe$䟵fdfeޥkDŽfdfe&Cfdfeߨfdfe*럴6fdfem fdfe/fdfefdfe5j_Zfdfe 9fdfe<Dfdfe音fdfeDaȁfdfe!sfdfeN)~fdfeyYÄfdfeWП5!fdfeݯfdfec֟IfdfeEfdfepfdfefdfe}[fdfe7[fdfe_؄fdfe}yfdfe뜘>fdfe%E'fdfe:4fdfe7wdefdfeAfdfeIy3fdfeӍfdfe]韰?fdfe荟#fdfesy+fdfeXsWfdfeӟQfdfe0fdfe򠡟fdfe,ofdfe5OfdfeEfdfeAfdfe_hjfdfemGلfdfez'lfdfeY#fdfe꟮fdfe%ßfdfe䟮 fdfeB韮gfdfeҙfmfdfebFfdfeџ'fdfeYfdfe}fdfeןʛfdfe56݄fdfeݟCfdfeX̟n̈́fdfe镟P{fdfe|0ބfdfeٟӄfdfe矬fdfe5=)fdfehfdfe[Mfdfez~fdfeafdfeDvfdfe9'fdfeA Kfdfe진fdfel'fdfe˄fdfefdfe.{fdfeŶ_fdfe \CÄfdfe 􄟫(fdfe ՟ fdfe "ﴄfdfe Qwfdfe S^fdfe ퟪifdfe fdfe!hfdfe꟪NbfdfeQ3fdfeTfdfeifdfe QfdfeCfdfeVfdfe򹟩fdfe0}fdfe)dSfdfeK1fdfeb23fdfeYfdfefdfe9zfdfeש fdfeufdfe}fdfefdfeP՟mfdfe:Ufdfe矨>efdfe/ܟ&fdfeyfdfenׄfdfeɟτfdfeݟfdfeR9+fdfe8fdfe #fdfe!6VnÄfdfe!џXfdfe"{Bfdfe#,fdfe#G0fdfe$c៦fdfe%ßfdfe%ퟦԹfdfe&Nfdfe&isfdfe'jfdfe(=fdfe(Dlfdfe)iWfdfe*-Afdfe*-Kfdfe+z5fdfe,!Cfdfe, ufdfe-n˄fdfe.vEfdfe.fdfe/f쟥fdfe0 ՟fdfe0ß{քfdfe1_ifdfe2 wVTfdfe2=CɄfdfe3[1bfdfe4ݟfdfe4z fdfe5[_fdfe6.fdfe69{fdfe7[#fdfe8fdfe8Eofdfe9`ٟKfdfe: 蟤Kfdfe: nofdfe;fv]fdfe<)M#fdfe<$<fdfe=n,gfdfe>lfdfe> gfdfe?{ fdfe@*mɄfdfe@@0fdfeA1˻fdfeB8jjfdfeB럣=fdfeC4fdfeDH韣OfdfeDA~fdfeE៣pfdfeF]ɟafdfeGSCfdfeGEfdfeHsO7fdfeI&V)fdfeI٥SfdfeJ< fdfeK?53fdfeK[fdfeLɟ㻄fdfeM\֨fdfeN}ɹfdfeN؟fdfeOzeGfdfeP0:ĄfdfePWefdfeQ*fdfeRQyfdfeSmq/fdfeSe_fdfeTw-YfdfeU.N+fdfewByZÄfdfew0} fdfew#{fdfew fdfevfdfevqބfdfevˍfdfevܟ9WfdfevQUӄfdfevq{fdfevkɟYfdfevQßZfdfev6fdfevHfdfeuǟsfdfeur%fdfeuIfdfeu]1fdfeuEUfdfeucXfdfeuBk[fdfeu :}fdfetfdfet?*fdfetykfdfetߞ؄fdfethɋfdfetAJQfdfet5CfdfesLafdfesƭɄfdfes@fdfesp fdfesDӄfdfesτfdfer鸞fdfer)$ofdfer(fdfer[I,fdfer*B/fdfeqA1fdfeql2ՄfdfeqÞ33fdfe$mitStyorungenvrerschiedener>ArtvreryandertundbeimEmpfyangerwie-der.decoSdiert.lWirwrollenMethoden nden,ddieFVehlerbeiderpxUbertragungzuerkrennenundmyoglicrhstKauchzukorrigieren.LhWVennalsoxeincoSdiertesausgesandtesWortistundy dasempfangeneZ+WVortist,ZHdannsollfestgestelltwrerden,obestatsyacrhlichZ+durchdieKoSdierungenrtstandenistoSderveryandertwurdeundobmandarausdasWVortxrekonstruierenkXann.rn7o]ʍkeKLEINE!EINF'ҟ UHR9UNGINDIEKODIERUNGSTHEORIEgXg7[o]De nition3.2.YùWVennbSeieinerKodierungfTu: vKܞ2k !Kܞ2n qFVehleranhyocrhstensr@5Stellendes y^|ubSertragenenWVortesimmererkXannrtwerdenkyonnen,^sosagenwir,dadieKoSdierungr-fehlerffentdeckend7ist.WVennFehleranhyocrhstenssStellendurchdierestlicheInformationimSyubSertragenenWVortkrorrigiertwerdenkyonnen,soheitdieKoSdierungs-fehlerkorrigierffend.bBemerkung3.3.c5In(1.4)habSenwirlineareKodierungenalslineareAbbildungenfQ:URC1V!C2 ,ԹzwiscrhenlzweiVVektorryaumende niert.mFSyurunsereAnwendungensollfϹimmerinjektivsein.OhneEinscrhryankungkyonnenwirC2V=URKܞ2n owyahlen. Auer(einerbijektivrenUmschreibungdesCoSdesC1d,verlierenwirnichts,:wennwirC1d,mitdemBildvronfG,alsoeinemUntervektorraumVURKܞ2n oidenti zieren. WVennunserGrundkyorpSerK5=Y^GFƹ(qn9)istmitq,#einerPrimzahlpSotenz,Elemenrten,sobSesitztdieMengedern-TVupelKܞ2n ogenauqn92n 1Elemenrte. Einkg-dimensionalerUnrterraumVURKܞ2n owirdein(n;k)-Coffdegenannrt. WirbSetreibenalsoTheorievronVVektorryaumenundUntervektoryaumen8yubSereinemendli-crhenKyorpSerGFƹ(qn9),wennwirlineareCoSdesstudieren.bBeispiel3.4.M]ڹSei?K[s=~GFƹ(2)=F2 >ٹ=f0;1gderKyorpSermitzwreiElementen.InKܞ25bSetracrhtenwirdenUnrterraumSʍaV¹={af(00000);(10011);(01010);(11001);b(00101);(10110);(01111);(11100)gDieses'istein3-dimensionalerUnrterraumundde nierteinen(5;3)-CoSdemit223 =8Co-dewyortern.WirwrerdendiesesBeispielalsStandardbSeispielweiterverwenden.Bemerkung3.5.c5SeiVKܞ2n eine(n;kg)-CoSdeundseienb1;:::ʚ;bk )eineBasisvronVp.DannymistVݹvrollstyandigbSestimmtdurchdieAngabSedieserBasisoderdurcrhdieMatrixDBy=9ބ0ބ@ڍ^b1]^.^.^.^bk9#1#A0:ѩDieseMatrixhatwregenderlinearenUnabhyangigkeitderZeilenb1;:::ʚ;bkdenZeilenrangkg.(DieVVektorenausV:sindgenaudieLinearkrombinationenderZeilenvronB.DieMMatrixBSwirddaheraucrheineerzeugenderMatrixfSyurVgenannt.Sieistnichteindeutig,wreilesvieleverschiedeneBasenfSyurVgibt. Jede(kM]0n)-MatrixvromZeilenrangk1-mitVVektorenausVfde nierteineerzeugendeMatrixfSyurVp. StattdieListederCoSdewyortereinesCodesanzugeben,Aistesyokronomischer,eineerzeugen-de MatrixanzugebSen. dFyur einenbinyaren(50;30)-CoSdehateinesolcrheMatrix1500Eintryage,wyahrenddieListederCoSdewyortermehrals1029Wyorterumfassenwyurde. EinerzeugendeMatrixBde nierteineinjektivrelineareAbbildungB:I:CKܞ2k s3v |7!xB2Kܞ2n.DiesekyonnenwiralszugrundeliegendelineareKoSdierungbegreifen. UnserBeispielcoSdehatbeispielswreisefolgendezweierzeugendeMatrizen:#N9|yH0|yH@ʍJ1F0B0>1y:1J0F1B0>1y:0J0F0B1>0y:19Y61Y6A6;90@ʍj1%J05*0E 1T1j1%J15*0E 0T1j1%J15*1E 0T09_ʔ1_ʔAlJ:$]Bemerkung3.6.c5WirWerinnerndaran,WAdaderZeilenrangeinerMatrixB!dieMaximalzahllinear.unabhyangigerZeileninBɆist.0rAnalogistderSpaltenrangvronBdieMaximalzahllinear unabhyangigerSpaltenvronB.OManzeigtinderlineareAlgebra,daZeilenrang(B)UR=Spaltenrang(B).4WVeiteroistder(Zeilen-oSderSpalten-)RangeinerMatrixgleicrhderDi-mension]desBildraumesvronBe:__Kܞ2r _3v͘7!xB2Kܞ2sJڹ.4Das]BildwirdnyamlicrhvondenZeilenrvektorenbi,=UReidBaufgespannt,wobSeidieeiOdiekXanonischeBasisbilden.Xn7o]&e8V9ORLESUNG!VONB.P:AREIGISIMSS1998[o] DieVeinelineareAbbildungist,istVp2? :=URKerBm(B2T<),insbSesonderealsoeinUnrterraum. Der wZeilenrangvronB}istgleichdemSpaltenrangvonB2T GgleichdemZeilenrangvonB2TgleicrhderDimensiondesBildesvonB2T<.DaheristdieDimensiondesKernsvonB2T %gleichnkg.0Ocffxff ̟ff ̎ ̄cffEDe nition3.8.YùSeiVURKܞ2n oeinCoSde.DannheitderCodeVp2? :URKܞ2n odualer35CoffdezuVp.Bemerkung3.9.c5SeienPVeinCoSdeundVp2? 8derdualeCode.Istv &2Vp,[sogilthvn9;wRi=0fSyuriallew2URVp2? .AlsoistvË2Vp2??YɹunddaheraucrhVVp2??U`.DadieDimensiondim(Vp2??)UR=n(nkg)UR=ko=dim(Vp)ist,giltV¹=URV2??U`.EBeispiel3.10.TڹDerdualeCoSdeVp2? zuunseremBeispielcodeist2-dimensionalunddurcrh^IVp ? :=URf(00000);(11010);(10101);(01111)ggegebSen.vBeacrhte,AdaderVVektor(01111)sorwohlinVsalsaucrhinVp2??Mcliegt,imGegensatzzumVVerhalteneineranalogenKonstruktionfSyurdaseuklidiscrheSkXalarproSdukt. EineerzeugendeMatrixist⍒ؼB 0=URqʍ*1! 100@ʞ1P0*1! 001@ʞ0P1[qf_:De nition3.11.`ùSeiV >Kܞ2n p޹einCoSde.{DieTVransponierteH= >B20a^TeinererzeugendenMatrixB20SdesdualenCoSdesVp2? heitKontrffollmatrixfyurVp.Satz3.12.?oJeffderH(lineare)CodeV6|Kܞ2n qstimmtPyubereinmitdemKerneinerzugehyorigenKontrffollmatrix35HV.Beweis.+܌Ein3VVektorvplliegtgenaudanninVչ=}eVp2??U`,9wrennvn9wR2T q&=0fSyurallew2Vp2? genaudann,wrennvn9HB=UR0gilt,genaudannwennerimKernderKontrollmatrixHliegt.!2cffxff ̟ff ̎ ̄cffBeispiel3.13.TڹEineKonrtrollmatrixfSyurunserenBeispielcoSdeist/rzɍR0ǍRB38RBRBRBR@ʍېT1pP1ېT1pP0ېT0pP1ېT1pP0ېT0pP1zɍPL1ǍPLC38PLCPLCPLCPLAL: DiedurcrhdieKontrollmatrixde niertenGleichungen,z.B.rsʍ511+21+30+41+50UR=0511+20+31+40+51UR=0kXannmanalsverffallgemeinerte35Parityats-Pr'yufsummenau assen. Yn7o]ʍkeKLEINE!EINF'ҟ UHR9UNGINDIEKODIERUNGSTHEORIEgXg9[o] AucrhderVVektor(01111)2T kyonnteineinerKontrollmatrixstehen.DieGleichung1510+21+31+41+51UR=0bSedeutetdann,dajederVVektorinV;/einegeradeAnzahlvronEinsenindenBits2bis5habSenmru.gPBemerkung3.14.i5Wir3kyonnenjetzteinenlinearenCoSdeV2URKܞ2n sorwohl3durcheineerzeu-gendecMatrixB9ialsaucrhdurcheineKontrollmatrixHvollstyandigbSeschreiben.Diecwesent-licrhenProblemesindjetztdieDekoSdierungunddieFVehlerkorrekturbzw.FVehlererkennung. Bei5derDekroSdierungkyonnenwirunsaufdenStandpunktstellen,sdamitderAngabeeinesVVektorsv}imCoSdeV4scrhonallesbekXannrtist.OderaberwirkyonnendenVVektorxUR2Kܞ2kmitvË=URxB2T &Źsucrhen.Zf24.uKfontrollma32trizenundHamming-MetrikDe nition4.1.YùSeiՠVDKܞ2n ZeinCoSdemiteinererzeugendenMatrixB. DasHamming-GewichtqkVpkUR=kBkvronV}bzw.vonB|wistdasMinimumderHamming-Gewichtekvn9kallervË2URVmitv6=0. DasHamming-GewicrhteinesCoSdesV|istdamitderminimaleHamming-AbstandzweiervrerschiedenerVVektorenimCoSde:d(v1;v2)UR=kv1jv2k.gPSatz4.2.8Sei9RV`Kܞ2n @einlineffarer9RCodemitKontrollmatrixHV.9\JedeCodewortv2`VvonHamming-GewichtLr=URkvn9kde nierteinelineffareLA2bhyangigkeitsrelationzwischenrVZeilenvek-torffen\vonHV.\TJedelineareA2bhyangigkeitsrelationzwischenrZeilenvektorenvonHIlde niertein35CoffdewortvË2URVϥvomHamming-Gewichtr=kvn9k.&@Beweis.+܌SeipHB=9UR0UR@ڍTh1]T.T.T.Thn9$A.1$A.A1]dieKonrtrollmatrixmitdenZeilenvektorenhidڹ.oSeivË=UR(1;:::ʚ;nP).Esistv7#2Vahgenaudann,0wrennvn9H@=0genaudann,0wrennPoidhi-Ĺ=0.GDieSummehatgenau2msovieleSummanden6=:0,2wievvronNullverschiedeneKoSezientenhat,2wiedasHamming-GewicrhtvonvXist.6cffxff ̟ff ̎ ̄cffgPFolgerung4.3.YSeiػVWaKܞ2n ]ein(n;kg)-lineffarerػCodevomHamming-GewichtkVpkmitKontrffollmatrix&HV.(DannsindjekVpkV1&ZeilenvektorenvonHDlinearunabhyangig,'3undesgibtkVpklineffarabhyangigeZeilenvektoren,d.h.kVpkistdieMinimalzahlvonlinearabhyangigenZeilenvektorffen35vonHV.Beweis.+܌EsugibtkreinenVVektorv2AVp,uv6=0uvromHamming-GewichtkVpk 71,udaherusindje\kVpk1ZeilenrvektorenvonHIulinearunabhyangigundumgekehrt.\EsgibteinenVVektorv2Vp,v6=0vromHamming-GewichtkVpk,dahergibteskVkZeilenrvektorenvonHV,dielinearabhyangigsindundumgekrehrt. Ecffxff ̟ff ̎ ̄cffFolgerung4.4.YF'yur35jeffden(n;kg)-linearenCodeVURKܞ2n #gilt1pkVpkURnkŹ+1:Beweis.+܌DerRangjederKonrtrollmatrixzuV]istnkg.^Damitsindjenk$+1ZeilenvektorenderFKonrtrollmatrixlinearabhyangig.HNachdervorhergehendenFVolgerungistalsokVpknkŹ+1.{cffxff ̟ff ̎ ̄cffSatz4.5.8(Fehlererkennung)ˬSeiV(IKܞ2n Pein(n;kg)-lineffarerˬCodeundseixI2Kܞ2n.Wennodeseinv22V mitv6=xgibt,ossodad(vn9;x):Kܞ2k o!Kܞ2n ~durcrhfG(x)=(x;x;x)gegebSen.BDasistwiedereinelinearerCoSdeV¹=URBi(fG). Mansiehrtsofort,dakVpkUR=3ist,alsoistdieserCoSde2-fehlerenrtdeckendund1-fehlerkrorrigierend.&\`Folgerung4.9.YSei35VURKܞ2n #einCoffdemitKontrollmatrixHB=9UR0UR@ڍTh1]T.T.T.Thn9$A.1$A.A.0. 5U (a)iSeiv([2"Vp,iundseienbffeideripxUbertragunggenautFehleraufgetreten.iWennx"2Kܞ2nderXempfangeneWertist,dannistdieminimaleA2nzahlderKoffezienteni'<6=b0,sodaxHB=URPidhigilt,35hyochstenst.j (b)Seivs92Vp,,seienbffeiderjpxUbertragunggenautFehleraufgetreten,,undseitN2Kܞ2n 5derempfangeneWertist,&danngibtesteindeutigbffestimmteKoezientenimit35xHB=URPidhi.Der3pxUbffertragungsfehleristdannPidei,undesgiltvË=URxPUSidei.Beweis.+܌MitN(a)kXanndieAnzahlderaufgetretenenFVehlernacrhuntenabgeschyatztwerden.eManbraucrhtvË2URVrnichtzukennen.SeiPideiGܹderZxpxUbSertragungsfehler,Fd.h.xUR=v]+$P:idei.DannistxH9ڹ=Lvn9Hǫ+UPideiH=LP/ihi.\SeiengenautFVehleraufgetreten,!soistdieAnzahl4derSummandent.EsistjedoScrhmyoglich,ƭdurchandereWVahlderKoSezienten n7o]ʍkeKLEINE!EINF'ҟ UHR9UNGINDIEKODIERUNGSTHEORIEbi11[o](wrenigeryKoSezienten)i&SeineandereLinearkombinationPl$idhi&Szuerhalten,diemitxHSyubSereinstimmrt. WVennMin(b)wrenigeralsFu1Οz@2 kVpkFehleraufgetretensind,MdannistdieminimaleAnzahlderSummandeninderDarstellungxH=PX]idhiԹkleineralsFu-1-z@2 [dkVpk.1WVegen(4.3)sinddie#_vrerwendetenrhiLlinearunabhyangig.WVennxHB=URPjf hj|einewreitereDarstellungistunddiestimmendieimitdeniyubSerein,[cd.h.dieDarstellungxHB=URPidhimitwrenigerNalsFu1z@2 GkVpkSummandenisteindeutig,OundderFVehleristxlqvË=URPidei.OManNbSeachtehierjedoScrh,/daderFVehlernurunterderAnnahmetURBeweis.+܌EsistBH=ٸ(Ik#Pƹ)qʍPVInk*Xq8h=0.6DaRang(B)=k5undRang(HV)=nFkg,istfpVp,tddertAvronBGerzeugteUnterraumderDimensionkg,tdgleichdemKern(HV),tdderjaauchdieDimensionkQŹhat.p݄cffxff ̟ff ̎ ̄cff n7o]ʍkeKLEINE!EINF'ҟ UHR9UNGINDIEKODIERUNGSTHEORIEbi13j Beispiel5.4.M]ڹDie@MatrixB=90@ʍgܹ1#G03'0C0R1g0#G13'0C1R0g0#G03'1C1R19]1]AlisteinesystematiscrheerzeugendeMa-:trix.Die-zugehyorigeKonrtrollmatrixistHz=zɍ$0Ǎ$B38$B$B$B$@ʍ&0$c"1&1$c"0&1$c"1&1$c"0&0$c"1zɍ/C1Ǎ/CC38/CC/CC/CC/CA;:DieRedundanzsymbSoleergeben*Uksicrhals` ʍȆ4V=UR2j+3Ȇ5V=UR1j+3>DerCoSdehatnacrh(4.3)dasHamming-Gewicht2,Vistalso1-fehlererkennend,VkXannabSerkreineFVehlerkorrigieren.Bemerkung5.5.c5ElemenrtareZeilenumformungensind:#8 1.#DieAdditioneinesVielfacrheneinerZeilezueineranderenZeileund 2.#dieMultiplikXationeinerZeilemiteinemFVaktor h6=UR0.WVegenqʍxa#bq(7!URqʍ*a+b|b/mq;7!URqʍ*a+b;a/mq7!URqʍkab*a%q1լ7!URqʍb*aUqlyatsicrhauchdasVVertau-čscrhenTzweierZeilenmitelementarenZeilenopSerationenerreichen.JedeelementareZeilenum-formrung3machtauseinerBasisvonVeineneueBasisvonVp,3weildieZeilenumformungennicrhtausVherausfSyuhrenundumkrehrbarsind,alsodieBasiserhalten. Das,GauscrheEliminationsverfahrenzeigt,,damaneine(kn)-MatrixvomRangkdurcrhelementareZeilenumformungenineineZeilenstufenform-J@n0Ǎ@nB38@nB@n@ڍOp a!8:::z x1X b:::ǰ <ȹ0 :::t*:::.> ?ː0O a8T:::{ Op a!8:::z x0X b:::ǰ <ȹ1 :::t*:::.> ?ː0O a8T:::{ ]Q.Q.Q.}t.}t.}t....}8.}8.}8.Ԟ.Ԟ.Ԟ.ڋ.ڋ.ڋ.Ab.Ab.Ab.0cf.0cf.0cf.A.A.A.Q*.Q*.Q*.}'.}'.}'.Op a!8:::z x0X b:::ǰ <ȹ0 :::t*:::.> ?ː1O a8T:::{ 1ǍC38CA-JumrwandelnkXann,wobSeidie 'sbeliebigeKoezienrtensind.CMankXannsogarvongewissen 'sannehmen,dasieNullsind. Durcrh";PermutationderSpaltenkXannmandarauseinesystematischeerzeugendeMatrixmacrhen.kDie7PermutationvonSpaltenbSedeuteteineUmschreibungderZeilenvektoreninKܞ2k MdurcrhMPermutationihrerKoSezienten.ODerdannerzielteCoSdeheitkombinatorischyaquivalent꨹zumAusgangscoSde.WirhabendamitSatz5.6.8Jeffder35CodeistkombinatorischyaquivalentzueinemsystematischenCode.!qy)ڹ6.St32andardtafelnundDekodierung Es bleibtwreiterhindieFVrage,%wiemaneinfehlerhaftۙyubSertragenesCodewrortjedenfallsinBezugaufdieInformationsbitskrorrigierenkXann,WalsodieFVragederallgemeinenDekoSdierungD:URKܞ2n @!Kܞ2k0.kWVegenderVerwrendungderHamming-MetrikisthiernichtmiteinerlinearenAbbildungzurecrhnen.De nition6.1.YùSeiK]V]Kܞ2n KeinCoSde.KEineNebffen-oderRestklasseneinesElementsx2Kܞ2n #bffez'yuglich35VistdieMengeFqdzRKx=URx+V¹=fx+vn9jvË2Vpg:Ӡn7o]&e14V9ORLESUNG!VONB.P:AREIGISIMSS1998[o]Lemma6.2.JQF'yur35dieNebffenklassengilt;ʍpdzRKx,j\dz(ߟKy (ٹ=UR;35,wenn*dzRKx4V6=dz(ߟKy ~1;؈S؊xinK;cmmi6ndzRKx 6=URKܞ2n:k>Beweis.+܌DiezwreiteGleichungistklar,!dennxUR=xҹ+0UR2xҹ+V¹=URdzRKx WURS UTyI{inKn)9dz(ߟKy/ba.7WVennzumcBewreisdererstenGleichunggilt,z52URdzRKx \ 'dz(ߟKy4,danngibtesv1;v2V2URV9mitz=URx '+v1V=yy`+v2.AlsoCZistyZ=Kx +v1v2O2x+V=dzRKxundCZdaheryUE+ vZ=x+v1v2+vZ2KdzRKx ,CqalsoCZdz(ߟKyXKdzRKx.SymmetriscrhgiltdzRKx LURdz(ߟKy hٹunddamitdzRKx=URdz(ߟKy ~1.Pcffxff ̟ff ̎ ̄cffk9Lemma6.3.JQJe35zweiNebffenklassenhabengleichvieleElementeBeweis.+܌Die|Abbildung o:cdzRKx3czF7!zE,+I(y*x)c2dz(ߟKyιist|bijektivmitderUmkrehrungdz(ߟKy ~13URz57!zB+!_(xyn9)UR2dzRKx .TVatsyacrhlichrist (z)UR= (x!_+v)UR=x!_+v+(yx)UR=y+!_vË2dz(ߟKy ~1. dcffxff ̟ff ̎ ̄cffDe nition6.4.YùFSyureinen(n;kg)-CoSdeVURKܞ2n ֹscrhreibenwirdieElemenrtsvonKܞ2n ֹineineTVafel.gInfdererstenZeilestehendieElemenrtevonVp.gAnersterStellederTVafelstehtdie0UR2Vp.AusjederNebSenklassedzRKx K2URKܞ2n=VwyahlenwireinElemenrtuaus,einenRffepryasentanten,und;scrhreibSenalledieseRepryasentantenR,indieersteSpalte.IndiefɞyubrigenFVelderderTVafelun+vxaus TderTafelunddekroSdiereihnzudeminVĹgelegenenVVektor1vn9.3DasisteinekrorrekteDekoSdierunggenaudann,2wennu,2derRepryasentantderzugehyorigenNebSenklasse,derFVehlerbeiderbpxUbertragungwrar. Man=bSeacrhte,ԅdaderHamming-AbstandeinesempfangenenVVektorsyBvzudemamAnfangder>#SpaltestehendenVVektorva2(VړdesCoSdesgenaugleicrhdemHamming-GewichtdesDi erenzvrektors4/kukUR=ky,5xk=d(yn9;x)ist.5FDaherwyahltmanalsRepryasenrtantenVVektorenminimalenHamming-GewicrhtesinderentsprechendenNebSenklasse.k9Beispiel6.7.M]ڹInunseremBeispielsehenwir,dagenaudieFVehler(10000);(01000);(00100)krorrigiertwerdenkyonnen. Die:LdritteundvierteZeiledesobSengegebenenBeispielszeigen,:`daaucrhdurchdieBe-dingung7vminimalenHamming-Gewicrhts7vderRepryasenrtant7vnoSchnichteindeutigbSestimmtist.:Der: gegebSeneCodehatdasHamming-Gewicrht: 2,:4kXannalsoaucrh(global)keineFVehlerkrorrigieren. WVennwirjedoScrhdendualen(5,2)-Codebetracrhteni^IVp ? :=URf(00000);(11010);(10101);(01111)gebSetracrhten,dannhatdieserdieKonrtrollmatrix/;Ѝzɍ0ǍB38BBB@ʍB1"00B0"10B0"01B1"10B1"01zɍ1ǍC38CCCA\n7o]ʍkeKLEINE!EINF'ҟ UHR9UNGINDIEKODIERUNGSTHEORIEbi15[o]unddamitdasHamming-Gewicrht3,kXannalsoeinenFVehlerimmer(!)krorrigieren.SDaszeigtaucrhdiezugehyorigeStandardtafelEEʍ -(00000)(11010)(10101)(01111) -(00001)(11011)(10100)(01110) -(00010)(11000)(10111)(01101) -(00100)(11110)(10001)(01011) -(01000)(10010)(11101)(00111) -(10000)(01010)(00101)(11111) -(01001)(10011)(11100)(00110) -(01100)(10110)(11001)(00011)EbMankXannalleeinzelnauftretenFVehlerunddieDoppSelfehler(01001)und(01100)krorrigieren.*FBemerkung6.8.c5DasProblembSeidieserDekrodierungist,)dadieTVafeleinesbinyaren(50,30)-CoSdesmehrals10215 Einrtryagehat,indenenman(unsystematisch)nachdenemp-fangenenWVortsucrhenmu,umeszudekoSdieren.De nition6.9.YùSei2VURKܞ2n < einCoSdeundHeineKonrtrollmatrix.Seix2Kܞ2n < einbSeliebiger(empfangener)VVektor.Dannheit ջsUR=xH}/das35Syndrffom,derParityats-Pr'yufungs-VektoroderderKontrollvektor꨹vronx.Lemma6.10.QuQxUR2Kܞ2n #ist35genaudanneinCoffdewort,wennseinSyndromNullist. Zwei Vektorffenx1 undx2sindgenaudanninderselbffenNebenklasse,wennihreSyndrome'yubffereinstimmen. Insbffesondere, istdaherdasSyndrffomeinerNebenklasseeindeutigbestimmt.,Weiterhabenzwei35NebffenklassendasselbeSyndromgenaudann,wennsiegleichsind.Beweis.+܌DiesesistinwresentlichenderHomomorphiesatzfSyurlineareAbbildungen. WirwissenscrhonV¹=URKerBm(HV),alsosUR=xHB=0genaudann,wennxUR2Vp. x1 `FundBx2sindgenaudanninderselbSenNebenklasse,qwrennx1 Jr2ndz mVKx2genaudann,wrennx1 g =x2+vLfSyureinvA2VzMgenaudann,]wrenn(vA=)x1x2 g 2VzMgenaudann,]wrenn(x1TPx2)HB=UR0genaudann,wrennx1HB=URx2H|Egenaudann,wrenndieSyndromevonx1Nundx2:yubSereinstimmen. Damitristklar,sdaalleElemenrteeinerfestenNebSenklassedasselbeSyndromhabenunddaPElemenrteausverschiedenenNebSenklassenverschiedeneSyndromehabSen.R7AlsokXannman'|vromSydromeinerNebSenklassesprechen.)bDieAbbildung,'diejederNebSenklasseihrSyndromzuordnet,istinjektiv.(cffxff ̟ff ̎ ̄cffBemerkung6.11.i5Syndrom-Deko`dierung:DasSyndromeinesbSeliebigenElemenrtsxUR2Kܞ2n \lyatsicrhleichtausrechnen,5alssA=xHV.dWVennmaneineTafelbildet,5inderdieaus-gewyahlten RepryasenrtantenderNebSenklassen(mitminimalemHamming-Gewicht)nebSendenSyndromenAdieserRepryasenrtantenAstehen,AgenanntSyndrffomtafel,AwennwiralsodieAbbil-dung':fSyndrome3>g!fRepryasenrtantenOMgkrennen,dannkyonnenwirwiefolgtdekoSdieren.MannehmeeinenbSeliebigen(empfangenen)VVektorx2Kܞ2n,AbildeihnaufseinSyndromabVdurcrhxHᬹ|dadurchistdieNebSenklassevonxschonbSestimmt,XbildedenzugehyorigenRepryasenrtantenFzu:='(xHV)undbSerecrhnev_չ:=x,u.GDannhatmaneinenVVektorv_2Vmit|derEigenscrhaft,˄daderHamming-Abstandd(x;vn9)UR=kxjvkUR=kuk|minimalistunrterden)Hamming-Abstyandend(x;vn920g!fRepryasentantenOMg7sbSenyotigenwirfyureinenbinyaren(50,30)-CoSdenrurnocrh2Spaltenmitje1026 Elementen,einewesentlicheVVerbSes-serung;gegenSyubSerderStandardtafelmit10215CEinrtryagen.cDaryuberhinauskXannmandieSyndromeinrtryageēsoordnen,ĝdasieinlexikographischaufsteigenderReihenfolgeauftreten,wroSdurchdieSucrhenachdementsprechendenEintragwesentlichverkSyurztwird. DiePStandardtafelnunseresBeispielsfSyureinenCoSdeundseinendualenCodevrerringernsicrhalsoauf(ʍ^(00)B(00000)^(11)B(10000)^(10)B(01000)^(01)B(00100)-5bzw.Dʍn(000)2(00000)n(101)2(00001)n(110)2(00010)n(001)2(00100)n(010)2(01000)n(100)2(10000)n(111)2(01001)n(011)2(01100)I5 Die5hierdiskutierteMethoSdederSyndromdekrodierungisteinedereinfacrhstenMethoden,die\fSyurallelinearenCoSdesangewrendetwerdenkXann. FSyurgroeCoSdesistjedocrhdieSydrom-tafelBimmernoScrhunhandlichgro.rSpSeziellereCodesgestatteneleganrtereFVehlerkorrekturundDekroSdierung.1wXT7.tHamming-CodesDe nition7.1.YHamming-Co`desҹSeimUR2NҹeinenatSyurlicrheZahl.ҁWirbildeneineMatrixmit22m 1ZeilenundmSpalten.DieZeilenmyogenausallenm-TVupSelnausK:F=]F2auerder3NullbSestehen,3alsoausallenElemenrtenausF2mRA2 9n4f0g.4Manbeacrhte,3da3jederVVektorbeiderAdditionzusicrhselbstinversist,daalsodieSummezweierverschiedenerZeilennichtdiesNullzeileist.tDamitsindjezwreiverschiedeneVVektorendieserMatrixlinearunabhyangig. Wir~bSetracrhtendieseMatrixalsKontrollmatrixfSyureinenCoSdeV׹=gKer(HV).DieCo-dewyorter`habSendieLyange22m % 1,dasHamming-Gewicrht`diesesCodesistkVpk}=3`nacrh(4.3),sVhat=dieDimension22m 1m=undjedesCoSdewrorthatmKontrollbits.|DamithabSenwirjeinen(22m=9%1;22m1m)-CoSdejkronstruiert,der2-fehlererkennendund1-fehlerkorrigierndist.\Sei^alsonoa=22m ?{1^undk~=oa22m{1m.\Der^(n;kg)-CoSdehatnacrh(6.4)22nkW=oa22mNebSenklassenwMunddamit22m . j1krorrigierbareFVehler,wqunterihnendieEinzelfehler.x%DadieLyangederCoSdewyorterebenfalls22m N2In1ist,sinddieRepryasenrtantenkleinstenHamming-GewicrhtsgenaudieEinzelfehlerfSyurdiesenCoSde.DieserCodewird(n;kg)-Hamming-Coffdegenannrt." EsgiltalsoLemma7.2.JQInieinemHamming-CoffdesinddieRepryasentantenderNebenklassenkleinstenHamming-Gewichts35genaudieEinzelfehlerf'yurdiesenCoffde.Dn7o]ʍkeKLEINE!EINF'ҟ UHR9UNGINDIEKODIERUNGSTHEORIEbi17[o]Beispiel7.3.M]ڹDerin(2.1)bSescrhriebeneCodeistderHamming-CodezumUR=3,n=223e1a1=7undko=URnm=73=4.DieKonrtrollmatrixist:esHB=έUR0ǍURB38URBURBURBURBURBURBUR@ʍT0"P12L1T1"P02L1T1"P12L0T1"P12L1T1"P02L0T0"P12L0T0"P02L1έ=uH1Ǎ=uHC38=uHC=uHC=uHC=uHC=uHC=uHC=uHAIH: id jx2i+j \,VialsoczuderobSende niertenMultiplikXation.DamitistdieMultiplikationdistributiv. DasElemenrt1UR:=x20istdasEinselementderMultiplikXation. DieAssoziativityatergibtsicrhaus)2򍍟}#RD[(P* m U_ i=0 idx2i)(P* n U_ jv=01 jf x2j)](P* r U_ k6=0 k#x2k)=UR[P* m U_ i=0P*)n U_)jv=0:2 id jf x2i+j \](P* r U_ k6=0 k#x2k)E=URP*m U_i=0 ASP*,n U_,jv=0>.P*J1r U_J1k6=0\= id jf k#x2i+jv+k=UR(P* m U_ i=0 idx2i)[P* n U_ jv=01P**r U_*k6=0< jf k#x2jv+k]=UR(P* m U_ i=0 idx2i)[(P* n U_ jv=01 jf x2j)(P* r U_ k6=0 k#x2k)](ɥcffxff ̟ff ̎ ̄cffDe nition8.2.YùSeigfG(x)/=P*=n U_=i=0!0 idx2i 6=0einProlynom.DieeindeutigbSestimmtegryoteZahlnmit n ,N6=0heitderGrffaddesProlynomsfG(x).> n dheitderhyochsteLiKoezientdesProlynoms. Manist(q3 qn9200,Tsoda1U+:::vL+1E=0mitgenau0]pSummandeninK gilt,0nheitdieCharffakteristikvronKܞ.0WVenneskeinesolcheZahlgibt,sowirddieCharakteristikals0de niert.Lemma8.9.JQWenn35KeineCharffakteristikpUR>035hat,dannistpeinePrimzahl.Beweis.+܌Seips=qn9r=Cmitqu+1)33q4#mal!(1+l:::&+Ɇ1)33r'mal!="~(1+:::]+1)33qI{r'mal%=0inKܞ.DaheristeinerderFVaktorenNull,jz.B.(1+:::z+1)33q4#mal$=UR0inKhmimWidersprucrhzuqË0.s2 1.#F'yur35 ; 2URKgilt( 7+ O)2p= 2p+ O2pq. 2.#Weiter35ist(x1)2p=URx2pr135inKܞ[x].Beweis.+܌NacrhderbinomischenFVormelist( +" O)2p=URP*p U_i=0 ASG܍%Up v~&ri*G/ 2ixi 2piHP=UR 2p+ 2pq,0dennG܍ p v~ `i a{G6Ϲ=눍G33p:::\(pi+1)33z/WDꍑ21:::\i5UR0 P7moSd%yp,PgwreilP?palsPrimzahlindiesemBruchnichtgekSyurztwerdenkXann.Q+Der#ZBewreisfSyur(x1)2p=URx2pr1verlyauftanalogmitdenselbSenBinomialkoSezienten.&cffxff ̟ff ̎ ̄cffLemma8.11.QuQSeikKu einendlicherKyorpffer.XDannhatKeinepffositiveCharakteristikpUR>0.Beweis.+܌Die*Elemenrte1;1+1;1+1+1;:::[ƹin*Kmȹsindnicrht*allepaarwreiseverschieden,AweilKsnrurZendlichvieleElementehat.Seialso(1+:::ˢ+1)33r'mal=UR(1+:::+1)33s꨹maljmitZr<URs.33DannkyonnenrmOSummanden1gekSyurztwrerden,alsogilt(1ʹ+:::`+1)33(sr0.WDasPolynomf鴹heitirrffeduzibel,|wrennLfSyurjedeZerlegungf=gn9hvonfKineinProSduktvonzweiPolynomengundheinesderbSeidenProlynomevomGrad0,d.h.eineKonstante,ist..Satz8.13.?oSei4fKeinKyorpfferundf2WKܞ[x]einirreduziblesPolynom.4hDannistdieMengeder35NebffenklassenKܞ[x]=(fG)einKyorper. WennIK&tqElementebffesitztundfdenGradnhat,IdannhatKܞ[x]=(fG)dieDimensionnund35damitqn92n IElemente.Beweis.+܌Mit](fG)bSezeicrhnenwirdenUnterraumfgn9fa2Kܞ[x]jgP2K[x]g.^]Dieser]Unrterraumist[einIdeal,d.h.fSyurjedesElemenrth2Kܞ[x][undjedesElementgn9f2(fG)istauchh(gn9fG)UR=(hg)fQ2(fG).OhneVEinscrhryankungderAllgemeinheitkyonnenwirannehmen,bdafhyocrhstenKoSezienten1hat,indemwirdasursprSyunglichef9߹mit 21RAnamultiplizieren,alsofdurcrh 21RAn p f2ersetzen.Dannist(fG)UR=( 21RAnfG). DieMengederNebSenklassenKܞ[x]=(fG)bildeteineadditivreGruppedurcrhdzKg :+: zÊ h ڹ:=W: zJ g+hundcsogareinenRingdurcrhdzKg : zÊ hI:=̟: z  gn9h.DiewichtigsteTVatsache,diehierfSyurnachgewiesenwrerdenemu,f ist,dadieseVVerknSyupfungenvronderAuswahlderRepryasentantenderNebSen-klassenunabhyangigsind. DiesenBewreisunddiepxUbSerpryufungderRingeigenschaftyubSerlassenwirdemHyorer(Leser). Um~nrunzusehen,daKܞ[x]=(fG)einKyorpSerist,zeigenwir,dajedesElemenrtdzKg 46=&0einInrversesunterderMultiplikXationbSesitzt.DazubetracrhtenwirdieMenge(gn9;fG)W=fp1gS+p2fGjp1;p2 2Kܞ[x]g.:WirfSyuhrendieDivisiong~=qn9f+[rB9durcrh.:DannistdzKg =dzKr6=0undGrad1(rS)Zb=5ŸP*on1 U_oi=0$e9 idڟz , 1xi6=5Ÿӥz ,[0inKܞ[x]=(fG), fallsnicrhtalleKoSezienrtenNullsind,d.h.dieӥz ,[1 ;dzRKxP;z mV x2 mT;:::ʚ;z2 xn1sindlinearunabhyangig.:Da9abSerhyohereProtenzenx2n+icdurchfmitRestteilbarsind::jx2n+i~=URqn9f+Arqunddaher=z 1xn+i=URdzKr I=UR3z4 m͍P* n1 U_ i=0/w idxi; EfSyur=geeignete igilt,Sbildendieӥz ,[1 u9;dzRKxP;z mV x2 mT;:::ʚ;z2 xn1YeineBasisfSyurKܞ[x]=(fG).Damitistdim(K[x]=(fG))UR=n=GradR(f).acffxff ̟ff ̎ ̄cffLemma8.14.QuQ1)ZujeffderPrimzahlpotenzqË=URp2n gibtes(bisaufIsomorphie)genaueinenKyorpffer35GKܞ(qn9)mitqnElementen. 2)cJeffdeendlicheUntergruppevondermultiplikativenGruppeKܞ2 einesKyorpersK@istzyklisch. 3)sSeiK %-LeineKyorpffererweiterung,sosdadimQK#{L<1gilt.ZujeffdemElement h2URL:gibtesgenaueinirrffeduzibles:Polynomp(x)2Kܞ[x]vonhyochstemKoffezienten1mitp( )UR=0,35genanntMinimalpSolynomf'yur . DerLesersolltedieBewreisehierfSyuringutenAlgebralehrbSyuchernnachlesen.Lemma8.15.QuQSei.nUR2N..DanngibteseinirrffeduziblesPolynomp(x)UR2F2[x]vomGrffadnmitӗNullstelle 2~QGFƹ(22nP),sodadieOrffdnungvon &inGF(22nP)2 genau22n!u1ist,also 22-:n71#=UR135giltund22nR1diekleinstesolchenat'yurlicheZahlist.:n7o]ʍkeKLEINE!EINF'ҟ UHR9UNGINDIEKODIERUNGSTHEORIEbi21[o]Beweis.+܌DaGFƹ(22nP)2 einezykliscrheGruppSeist,ugibtesein(erzeugendes)Element 2GFƹ(22nP)2%vrone{derOrdnung22nB1.fGSeip(x)dasMinimalpSolynomfyur .fGDaGFƹ(22nP)UR=F2( ),istGFƹ(22nP)PUR԰n:=F2[x]=(p(x))undGrad(p(x))UR=n.Նcffxff ̟ff ̎ ̄cffʍ,9.ZyklischeCodes WirGhabSenbisherfastausscrhlielichGCodesstudiert,GderenHamming-GewicrhteGklein(z.B.3NoSder4)wraren.PSiesindhyochstens1-fehlerkorrigierend.PMitdenzyklischen(Polynom-)CoSdeserhaltenwirCodesmithyoheremHamming-Gewicrht.SBemerkung9.1.c5Seienkbundnmitko<URngegebSen,undseigj einProlynomvomGradnkg.DannQde niertgYdiefolgendelineareAbbildunggī:VrPk61V3fq7!gn9f2Pn1̹.RWirQbSetracrhtendieenrtsprechendelineareAbbildungaufdenKoSordinatensystemenvonKoSezientenvekto-ren derProlynomebg :{kKܞ2k {!Kܞ2n.,WVenn g餹=P*&nk U_&i=0#p idx2ieist,dannistdiedarstellendeMatrixi vrongXbSezyuglichderBasen1;x;x22;:::ʚ;x2k61궹bzw.1;x;x22;:::ʚ;x2n1otgegebSendurcrhm9nCM6=GmUR0ǍURB38URBURBURBURBURBURBURBURBURBURBURBURBURBURBURBURBURBURBURBURBUR@UJ 07f70g ::: 0 14 0Sҹ0g ::: 0]...4.8o.=MO.P*.U .Y.JC.JC.JC....P*.U .Y.iK.m䩟.r}.JC.JC.JC....jO 1 0ٹ... 1 T nkJC.JC.JC.e0. nkJC.JC.JC....P*.U .Y.JC.JC.JC....iK.m䩟.r}.JC.JC.JC.e02p:::lq0k nkGmlT1ǍlTC38lTClTClTClTClTClTClTClTClTClTClTClTClTClTClTClTClTClTClTClTClTAT;m9wiemansofortausdemProlynomproSdukt)}gn9fQ=nkURX ㇍Si=0 idx iO}k61d؟X ㇍Ajv=0. jf x j\=n1URX ҍt=0(k61X ㇍Iijv=0UV tjL j)x t଍abliest.SDe nition9.2.YùEinCoSdeV¹=URBi(bg),dervroneinemPolynomg inderFVormKbg :URKܞ2k U!Kܞ2nmitGrad(gn9)URnkQŹerzeugtwird,heiteinPolynomcffode.De nition9.3.YùEinFCoSdeVjKܞ2n heitzyklisch,G wrennfyurallexj=(1;:::ʚ;nP)2Vcgilt(nP;1;:::ʚ;n1̹)v 2Vp.,Also*istjedezykliscrheVVertauschungeinesCoSdeworteswiedereinCoSdewrort.Theorem9.4.TSeien %kBundnmitko<URngeffgeben. BSei %gË2PnkvomGrffadnLkBein %Teilervonx2n&ֹ1UR2Kܞ[x].>DannistderdurffchgUerzeugtePolynomcodeeinzyklischerCode.>gUheitdann35einGeneratorpSolynomf'yurdenzyklischenCoffde.Beweis.+܌Seign9g20Ĺ=URx2n8~1.Dannistx2n=gn9g20t+8~1.SeigfQ=UR 0+8~ 1x+:::;+ n1x2n10.lDannl3istdaszugehyorigeProlynom 0߹+ 1x+:::V+ p1x2p1ժ=1gk#fyй=(x1)2pkgfG.WirrbildendieformaleAbleitungunderhalten 1u+2 2x+:::5+(p1) p1x2p2+=UR(gk#fG)20#=Ӎ(pCkg)(x1)2pk61f,B+(x1)2pkgfG20 {=eV(x1)2p(k6+1)![((pk)f,B+(x1)fG208).DaherEist( 1;2 2;:::ʚ;(pv1) p1;0)UR2Bi(bgk6+1e){einElemenrtkleinererNorm.!Damitistkbgk6+1kUR1UR=kbgp gk~=~z 2i3+ 2j=t( )#ausderMatrixS׹.WVeil 2icund 2jdANullstellendesProlynomssind,giltVʍ4o 22i c+1 2i#+2V=UR0;3? 22j dE+1 2j$A+2V=UR0: [#Multipliziert\mandieerstederGleicrhungen\mit 2iunddiezwreitederGleichungenmit# 2jdAundaddiertdieGleicrhungen,soerhyaltman1t(  3ӓ)+1t(  2)+2t( )UR=( 3i c+ 3j)+1( 2i c+ 2j)+2( i#+ jy)UR=0;#wrobSeiNdie -KoezienrtenbekXannrtsind.˦DieseGleichungkXannmannach2 Rau yosen#undhatdamit1;2bSestimmrt.DamitistdergefundeneCode2-fehlerkrorrigierend.rn7o]&e24V9ORLESUNG!VONB.P:AREIGISIMSS1998[Beispiel10.5.UPpxTUbSeriBdemKyorperGFƹ(64)kXannmanmitProlynomenvomGrad,Ϲ12fol-gendewreitereB.C.H.-CoSdes((63,k)-Codes)bestimmen:5eʍy30BitsInformation,6FVehlerkrorrigierbarU!;y24BitsInformation,7FVehlerkrorrigierbarU!;y18BitsInformation,#10FVehlerkrorrigierbarU!;y16BitsInformation,#11FVehlerkrorrigierbarU!;y10BitsInformation,#13FVehlerkrorrigierbarU!;7BitsInformation,#15FVehlerkrorrigierbarU!:;n$* .!", 3 cmsy10,K`y 3 cmr10+@ cmti12( msbm10"u cmex10 K cmsy8!", cmsy10;cmmi62cmmi8g cmmi12|{Ycmr8o cmr9- cmcsc10N cmbx12XQ cmr12K`y cmr10O linew104