Signalverarbeitung – Prof. Vallentin – SS 2016

Signalverarbeitung–Prof.Vallentin–SS2016
Codierungstheorie
1.Grundlagen
1.1Aufgeht’s
•
•
•
•
•
•
Definitionen:Blockcode,Hamming-Distanz,Hamming-Gewicht,Minimaldistanz,
Minimalgewicht,(n,M,d)-Code,Informationsrate,Hamming-Kugel,perfekterCode
Lemma1.1:DieHamming-DistanzisteineMetrik Lemma1.2: Satz1.3(Hamming-Schranke):
VerwendungvonCodes,KommunikationskanalnachShannon,ML-Decoding
Theorem1.4:SeiCein(n,M,d)-Code,dannkannChöchstens(d-1)/2Fehler korrigieren
Beweis
Beweis
Beweis
Beweis
1.2LineareCodes
•
•
•
•
•
•
Definitionen:linearer-Codebzw.[n,k]-Code,[n,k,d]-Code,dualerCode,Erzeugermatrix,
Kontrollmatrix,äquivalenteCodes,Syndrom
Lemma1.5:FürClineargiltw(C)=d(C)
Beweis
Lemma1.6:GErzeugermatrixvonC↔GKontrollmatrixvonC-dual
Beweis
Satz1.7:JederlineareCodelässtsichinStandardformbringen Beweis
AllgemeineCodierung&DecodierungfürlineareCodes
Theorem1.8:DieBerechnungeinessolchene’sistNP-vollständig
1.3GewichtszählerunddieMacWilliams-Identität
•
•
•
•
•
Definitionen:Gewichtszähler
Theorem1.9(MacWilliams-Identität):
Lemma1.10:
Satz1.11: Lemma1.12:FürCbinär,linear,ngerade,CselbstdualundgeradegiltA_i=A_n-i
Beweis
Beweis
Beweis
Beweis
2.Konstruktionen
2.1Golay-Code
•
•
•
Definitionen:G_24,erweiterterCode,G_23
Theorem2.1:G_24istein[24,12]-Code,selbstdual,doppeltgerade,mitd=8und
invariantundeinerPermutation
Lemma2.2:FürCbinärmitd(C)ungeradeistC-quereinCodemitd(C-quer)=d(C)+1
Beweis
Beweis
2.2Reed-Solomon-Code
•
•
•
Definitionen:A_q(n,d),MDS-Code,RS-Code
Satz2.3(Singleton-Schranke):A_q(n,d)≤q^{n-d+1}
Satz2.4:RS_{q,n,k}isteinMDS-Code
Beweis
Beweis
Definitionen:Nearest-Codeword-Problem,Graph-Code
Lemma2.5:
Theorem2.6:NCPistNP-vollständigfürallgemeineCodes
Welch-Berlekamp-Algorithmus
Lemma2.7:Q/E=Q’/E’,d.h.dieWahlvonQ,Eistbeliebig Beweis
Beweis
Beweis
2.3EffizienteCodierungvonRS-Codes
•
•
•
•
•
2.4ZyklischeCodes
•
•
Definitionen:zyklischerCode,R_{q,n},Kontrollpolynom,BCH-Code
Satz2.8:CisteinzyklischerCode↔CisteinIdealinR_{q,n}
•
•
•
•
•
Satz2.9:EigenschaftenzyklischerCodes Satz2.10:Czyklisch,dannistauchC-dualzyklischmitErzeugerpolynomx^n*h(x^-1)
Satz2.11:d(BCH(q,n,delta,l))≥delta
Satz2.12:dim(BCH(q,n,delta,l))≥n-m(delta-1)
Satz2.13:RS_{q,q-1,q-delta}=BCH(q,q-1,delta,1) Beweis
Beweis
Beweis
Beweis
Beweis
3.SchrankenfürCodes
3.1ElementareSchranken
•
•
Satz3.1(Gilbert-Vershamov-Schranke/Greedy-Konstruktion): Satz3.2(Plotkin-Schranke):Seitheta=1-1/q.Fürd>theta*ngilt
A_q(n,d)≤d/(d-theta*n)
Beweis
Beweis
Beweis
Beweis
Beweis
Beweis
Beweis
3.2DiskreteFouriertransformation(DFT)
•
Definitionen:C^G,Faltung,Charakter,DFT
3.3SchnelleFouriertransformation(FFT)
•
Definitionen 3.4ZweiAnwendungenderFFT
•
Definitionen 3.5DieLineareProgrammierungsschrankevonDelsarte
•
Definitionen MaschinellesLernen
4.Dimensionsreduktion
4.1Hauptkomponentenanalyse(PCA)
•
Definitionen 4.2DünneHauptkomponentenanalyse(sparsePCA)
•
Definitionen 4.3DasJohnson-LindenstraussLemma
•
•
•
•
•
Lemma4.9(Johnson-Lindenstaum,1984): Satz4.10: Lemma4.11(Markov-Ungleichung:
Lemma4.12:
Sublemma4.13:
Fragen
•
blablabla
Beweisideen
•
Satz1.1:blablabla
Übungsblätter
Blatt7
• Aufgabe1:
o a)ssss

Download Report