Übung zur Vorlesung Informationstheorie und Codierung

ÜbungzurVorlesung
InformationstheorieundCodierung
Prof.Dr.LiliaLajmi
Juni2015
Ostfalia Hochschule für angewandte Wissenschaften
Hochschule Braunschweig/Wolfenbüttel
Postanschrift: Salzdahlumer Str. 46/48 • 38302 Wolfenbüttel
Besucheranschrift: Salzdahlumer Str. 46/48 • 38302 Wolfenbüttel
ÜbungInformationstheorieundCodierung2015
1
Aufgaben
AlphabetundWörter
Aufgabe1
1. EsseidasAlphabet
0, 1, 2 und
3gegeben.
a. BestimmenSie: , , , und ∗ b. Wiegroßist| |?
2. EinAlphabetA,bestehendaus26Buchstaben,3UmlautensowiedemLeerzeichen
unddenneunSatzzeichen.,;:?!„“und–sollBinärundhexadezimaldargestellt
werden.
Wievielebinärebzw.hexadezimaleStellensindfürdieDarstellungeinesSymbols
mindestenserforderlich?
CodierungundDecodierung
Aufgabe2
EinSenderkannvierCodierteNachrichtenaussenden(Eshandeltsichhierumeinerbi‐
närenBlockcodierungderLänge2):
00DieBörseistsehrfest.
11Sollenwirverkaufen?
01DieKursefallen.
10Helftunsgegensteuern!
EinesTageswirddieSymbolfolge…00110011001…empfangen.Dabeihatmandaserste
Symbolverpasstunderstdaszweiteempfangen.
Zusätzlichweißmannicht,wodieMitteilungaufhört,daderSenderimmerweitersendet.
RekonstruierenSiediegesendeteBotschaftunterderAnnahme,dassderSenderetwas
Sinnvollesübertragenhat.
Aufgabe3:PräfixfreierCode
GegebenseidasAlphabet
IstdieMenge
0, 1 .
1, 011, 01110, 1110,10011 einsinnvollerCodefürfünfNachrichten?
Aufgabe4:
BestimmenSiefürjedenderfolgendenCodes,obdiesereindeutigdecodierbaristundob
essichumeinenpräfixfreienCodehandelt.
IstderCodenichteindeutigdecodierbar,danngebenSieeineCodesequenzan,fürwelche
zweiunterschiedlicheInterpretationenalsSequenzausCodewörternexistieren.Sonstre‐
präsentierenSiedenCodemiteinemCodebaum.
5.Juni2015
Seite1von56
ÜbungInformationstheorieundCodierung2015
1.
00, 10, 01, 11 2.
0, 10, 11 3.
0, 01, 11 4.
1, 101 5.
0, 1, 01 Bemerkung: ExistierteineindeutigdecodierbarerCode,dannexistiertaucheinpräfix‐
freierCodemitdenselbenCodewortlängen.Deshalbwerdenfüreindeutig
decodierbareCodesüblicherweisePräfixfreieCodesVerwendet.
Aufgabe5:UngleichungvonKraft
EinbinärerBaumhabe
7Endknoten,derenAbstände vonderWurzelsind:
2;
3; 4
1. ExistiertdieserBaum?
2. Wennja,stellenSiediesenBaumdar.
Aufgabe6:UngleichungvonKraft
1. ExistiertfürfolgendeCodewortlängeneinbinärerPräfixfreierCode?Wennja,dann
konstruierenSieeinenentsprechendenCode
a.
1, 2, 3, 4, 5, 5 b.
1, 2, 3, 4, 4, 5 c.
2, 2, 2, 3, 4 2. ExistiertfürfolgendeCodewortlängeneinternärerPräfixfreierCode?Wennja,dann
konstruierenSieeinenentsprechendenCode
a.
1,2,3,1,2,3,2 b.
1,2,3,4,1,2,3,4 c.
3,3,3,3,3,3,2,1,1 Aufgabe7:ASCII‐Codierung
1. WielautetderASCII‐CodevomSymbol„A“(Hexadezimalzahl=41)
2. VervollständigenSiediefolgendeTabellezurUmrechnungvonDezimal‐,Hexadezi‐
mal‐undBinärzahl
5.Juni2015
Seite2von56
ÜbungInformationstheorieundCodierung2015
Dezimalzahl
Hexadezimalzahl
Binärzahl
715
19
B3
125
1010101
Quellencodierung
Aufgabe8
GegebenseieineQuelleQmit4Symbolen(A,B,CundD).
DieAuftrittswahrscheinlichkeitenderSymboleseien:
0,8
0,1
0,08
0,02
1. WiegroßistdieInformationeineseinzelnenSymbols?
2. WiegroßistdieEntropiederQuelle?
3. WiegroßwäredieEntropiebeigleicherAuftrittswahrscheinlichkeitder4Symbole?
Aufgabe9
EineQuelleenthält4Symbole:Q
A B C D
1. BerechnenSie:
a. DenEntscheidungsgehaltH .
b. DieEntropieH Q c. DieRedundanzderQuelleR .
2. DieQuellewirdmiteineroptimalenCodewortlängecodiert(angepasstandenInfor‐
mationsgehaltdereinzelnenSymbole).
a. BerechnenSiediemittlereCodewortlängeproSymbolL x b. WielautendieCodewörterdereinzelnenSymbole?
c. BerechnenSiediemittlereCodewortlängeL
d. BerechnenSiedieRedundanzdesCodesR Aufgabe10:FanoCodierung
QuelleQistgegebendurchAlphabetundabsoluteHäufigkeiten:
15
7
6
6
5
1. CodierenSiedieQuellenachFano(CodierungstabelleundCode‐Baum)
2. WiegroßistdiemittlereCodewortlänge?
5.Juni2015
Seite3von56
ÜbungInformationstheorieundCodierung2015
Aufgabe11:FanoCodierung
ErstellenSiejeweilsdenCodebaumundCode‐Tabelle.GebenSiefürjedesZeichendieCo‐
dierunganundberechnenSiediemittlereCodewortlänge
1.
2.
ZeigenSie,dasseshiernachdemFanodreiunterschiedlichemöglicheCodierungengibt
unddassdieFano‐Codierungnichtimmeroptimalist
Aufgabe12:
GegebenistdieQuelle 0,4 0,1
0,2 0,3
1. WiegroßistdieEntropiederQuelle?
2. Fano‐Codierung
a. CodierenSiedieQuellemitdemFano‐Algorithmus
b. BerechnenSiediemittlereCodewortlängeunddieRedundanzdesCodes
3. Shannon‐Codierung
a. CodierenSiedieQuellemitdemShannon‐Algorithmus
b. BerechnenSiediemittlereCodewortlängeunddieRedundanzdesCodes
4. Huffman‐Codierung
a. CodierenSiedieQuellemitdemHuffmann‐Algorithmus
b. BerechnenSiediemittlereCodewortlängeunddieRedundanzdesCodes
5. VergleichenSiedieErgebnissederdreiAlgorithmen.
Aufgabe13:Shannon‐Codierung
EineQuelleenthälteinZeichenvorratvon4Zeichen(A,B,C,D).DieAuftrittswahrschein‐
lichkeitendereinzelnenZeichenseien:
PA=0,8;
PB=0,1;
PC=0,08;
PD=0,02.
1. WiegroßsinddieInformationsgehaltedereinzelnenZeichen?
2. WiegroßistdieEntropiederQuelle?WiegroßwäredieEntropiederQuellebeiglei‐
cherAuftrittswahrscheinlichkeitdervierZeichen?
3. Für die Übertragung soll ein Binärcode nach Shannon entwickelt werden. Welche
mittlereCodewortlängeergibtsichausdemerstelltenCode.
Aufgabe14:HuffmanCodierung
GegebenseidiefolgendeNachricht:
RZROZPZZ
1. GebenSiediezugehörigeHuffman‐Codierungan.
2. ErmittelnSiedurchRechnung,obessichdabeiumeinenoptimalenCodehandeltund
begründenSiedasErgebnis.WelcheRegeltriffthierzu?
5.Juni2015
Seite4von56
ÜbungInformationstheorieundCodierung2015
Aufgabe15:HuffmanCodierung
FüreinenZeichenvorratsindfolgendeAuftrittswahrscheinlichkeitengegeben:
Zeichen
R
E
Häufigkeit
0,09 0,01
H
K
P
A
S
0,4
0,05
0,12
0,13
0,2
1. LeitenSiediezugehörigeHuffman‐Codierungher
2. BerechnenSiedieRedundanzdesCodes
3. CodierenSiedieZeichenfolgen
a. KEKSE
b. HARKE
4. IstderCodeoptimal?WannliefertderHuffman‐AlgorithmuseinenoptimalenCode?
Aufgabe16:
GegebenseidieQuelle
0,7 0,2 0,1
1. CodierenSiedieSymbolevon undberechnenSiediemittlereCodewortlänge
2. CodierenSieSymbolpaarevon undbestimmenSiediemittlereCodewortlängepro
Symbol.VergleichenSiebeideErgebnissemitderEntropiederQuelle
Aufgabe17:
GegebenistfolgendeBinärsequenz:
0001 0000 1010 0000 1000 0011 0010 0010 1. BerechnenSiefürdieobigeNachricht:
a. DenEntscheidungsgehalt
b. DieEntropie
c. DieRedundanzproSymbolunddiegesamteRedundanzderNachricht.
2. Es sind jeweils zwei benachbarte Bits zu einem Symbol zusammenzufassen. Beant‐
wortenSiefürdiesichdarausergebendeSymbolfolgealleFragengemäß1a‐c.
3. CodierenSiedieSymbolfolgemitShannon.WelcheRedundanzergibtsich?
4. CodierenSiedieSymbolfolgemitHuffman.WelcheRedundanzergibtsichjetzt?
Aufgabe18:
GegebenistfolgendeNachricht:
AACDABCAAADBACAC
1. Wiegroßsind
a. derEntscheidungsgehaltderNachrichtenquelle,
b. derInformationsgehaltdereinzelnenZeichen,
c. dieEntropieundRedundanzderNachricht.
2. DieZeichensollenbinärcodiertunddannübertragenwerden.DerCodelautet:
A=00
B=01
C=10
D=11
5.Juni2015
Seite5von56
ÜbungInformationstheorieundCodierung2015
a. GebenSiedenInformationsgehaltderbinärenZeichen0und1an
b. WelcheRedundanzergibtsichjetzt?
c. MachenSieeinenVorschlag,wiedieRedundanzdurcheineoptimierteCodierung
verringertwerdenkann.
Aufgabe19:
EinefarbigeGrafikbestehtaus1MillionBildpunkten,dieROT,GRÜN,BLAU,WEISSund
SCHWARZ aussehen können. Das gesamte Bild wird in 1 Sekunde übertragen. Alle ge‐
nanntenFarben/HelligkeitentreteninderGrafikgleichhäufigauf.
1. BerechnenSiedenEntscheidungsgehaltderQuelle„farbigeGrafik“undgebenSieden
InformationsgehaltfürjedesdermöglichenZeichen(Farbenbzw.Helligkeitswerte)
an.
2. Die Zustände der Bildpunkte sollen binär codiert werden (gleiche Codewortlänge).
WelcherDatenflussergibtsichhierbei?WelcheRedundanzliegtjetztvor?
3. StellenSiedieZeichenmitdemHuffman‐Codedar.WelchemittlereCodewortlänge
ergibtsich?WelcheRedundanzresultiert?
DiskreteQuellemitGedächtnis
Aufgabe20:
GegebenSeieineQuelle
, , mitGedächtnis.FürdieQuellensymbolegeltendie
folgendenbedingtenWahrscheinlichkeiten:
| 1
3
1
3
1
3
1
4
1
2
1
4
1
4
1
4
1
2
1. StellenSiedieQuelleanschaulichmitHilfeeinesMarkov‐Diagramms1.Ordnung
dar.
2. BestimmenSiedieSymbolwahrscheinlichkeiten
,
und
3. BerechnenSiedieVerbundwahrscheinlichkeiten
, 4. Berechnen Sie die Entropie der Quelle, die bedingte Entropie und die Verbun‐
dentropie
Aufgabe21:Markov‐Quelle
EinediskreteQuelle
Abbildung.
5.Juni2015
,
mitGedächtnishabedenZustandsgrafausderfolgenden
Seite6von56
ÜbungInformationstheorieundCodierung2015
3/4
?
B
A
?
1. GebenSiedieÜbergangswahrscheinlichkeitenan.
2. BerechnenSiedieAuftrittswahrscheinlichkeitendereinzelnenZustände.
3. GebenSiedieEntropiederQuelleanunterBerücksichtigungderÜbergangswahr‐
scheinlichkeiten.
4. Fassen Sie jeweils drei Zeichen zu einem Symbol zusammen. Berechnen Sie die
WahrscheinlichkeitendermöglichenSymbole.
5. FührenSieeineHuffman‐CodierungdurchundgebenSiediemittlereCodewort‐
längedesCodes.
Kanalcodierung
Aufgabe22:(A32Dr.Jäger)
GegebenseieinsymmetrischerbinärerKanal(BSC),dessenEingangszeichen und 0,4 und
0,6 haben und dessen Bit‐
die Auftrittswahrscheinlichkeiten
fehlerwahrscheinlichkeit
0,05beträgt.
1. BestimmenSiedieEntropiederKanalausgabe
2. dieEntropiederIrrelevanz
| ,
3. dieTransinformation
, .
,
Aufgabe23:(A31 Dr. Jäger) GegebenseiderskizzierteKanal
WiegroßistdieKanalkapazität ,wenndieEingangs‐undAusgangszeichengleichverteilt
sind?
5.Juni2015
Seite7von56
ÜbungInformationstheorieundCodierung2015
Aufgabe24:(A30 Dr. Jäger) GegebenseieinBSC‐KanalmiteinerÜbertragungsrate
wahrscheinlichkeitvon
0,1
1
/ undeinerBitfehler‐
DieDaten,dieüberdiesenKanalübertragenwerdensollen,stammenvoneinerbinären
Quelle( und )mitdenAuftrittswahrscheinlichkeiten
und
.DieSymbole
derQuellewerdenstatistischunabhängigvoneinanderausgewählt.
1. WiegroßistdieKanalkapazität ?
2. WiegroßistdieEntropiederQuellemit
0,3und
0,7?
3. WelchemaximaleSymbolrate
kannimPrinzipfehlerfreiübertragenwerden?
Aufgabe25:(A34 Dr. Jäger) Es sei ein fehlererkennender und fehlerkorrigierender Code über dem Alphabet 0, 1 miteinerCodewortlänge 20gegeben.
1. WievieleNachrichtenstellenkönnenmitdiesemCodeübertragenwerden,wennbis
zu3Fehlerkorrigiertwerdensollen?
2. WievieleverschiedeneNachrichtenkönnendannmaximalcodiertwerden?
3. WiegroßistdieMinimaldistanzdesCodes?
4. WievieleFehlerkönnen(ggf.ohneKorrekturmöglichkeit)erkanntwerden?
Aufgabe26
EinHamming‐CodederLänge
Bestätigungeingesetztwerden.
sollzurreinenFehlererkennungmitanschließender
DieBitfehlerwahrscheinlichkeiteinessymmetrischenBinärkanalsbeträgt
5 ∙ 10 1. WiegroßistdieWahrscheinlichkeit,dasseinCodewortfehlerhaftempfangenwird?
2. WiegroßistdieWahrscheinlichkeit,dasseinfehlerbehaftetesEmpfangswortnichter‐
kanntwird?
Aufgabe27:(A33Dr.Jäger)
Gegeben sei ein linearer Blockcode über dem Alphabet matrix 0
1
1
1
0
1
0
1
0
1
0
0
1
1
0, 1 mit der Generator‐
0
1
0
0 1
1
1
1. StellenSiedenvollständigenCodeauf(ListederNachrichtenwörtermitdenzuge‐
hörigenCodewörtern).
2. BerechnenSie
, und desCodes.
3. Geben Sie alle möglichen Vektoren an, die in der Korrigierkugel um
0111010 liegen.
5.Juni2015
Seite8von56
ÜbungInformationstheorieundCodierung2015
4. WielautetdieGeneratormatrix ´ deszugehörigenseparierbarenCodes?
5. StellenSiedieKontrollmatrix fürdenseparierbarenCodeauf.
6. GebenSiedieGleichungenzurErmittlungderKontrollstellenan(Ablesenausder
Kontrollmatrix).
7. WielautendanndiezugehörigenPrüfgleichungen?
8. ErstellenSieausderKontrollmatrix dievollständigeSyndromtabelle(fürEin‐
zelfehler).KönnenalleEinzelfehlerkorrigiertwerden?
9. ZeigenSiedann(durchBerechnungdermöglichenSyndrome),dasssichauchalle
BündelfehlerderLänge2korrigierenlassen.
10. Wielautendiezudenfolgenden(verfälschten)Empfangsvektoren gehörenden
(korrigierten)Codewörter 0001101 ;
0010100 ;
1111110 Aufgabe28:
(A37Dr.Jäger)
GegebenseieinzyklischerCodeCüber 0,1 mitdemGeneratorpolynom
1,derCodewörterderLänge 7erzeugt. 1. WievieleKontroll‐undNachrichtenstellenhatderCode?
2. GebenSiediezugehörigeGeneratormatrix desCodesan.
111 und
101 invektorieller
3. CodierenSiedieNachrichtenvektoren
undinpolynomialerDarstellung.
4. KonstruierenSiedieCodewortpolynomedeszugehörigenseparierbarenCodeszuden
Nachrichtenwörtern
1und
.
5. ErstellenSieeineSyndromtabellefüralleEinzelfehler.
6. EswerdendasWort
1001001 unddasWort
0100111 empfan‐
gen.PrüfenSie,obessichumgültigeCodewörterhandeltundkorrigierenSiegegebe‐
nenfallsdieEmpfangswörter.
Faltungscodierung
Aufgabe29:
GegebenisteinCodiererfüreinenFaltungscodederrate
länge2.
mitderSchieberegister‐
1. ZeichnenSiedasTrellis‐unddasZustandsdiagramm.
2. DecodierenSiedieEmpfangssequenz100101.Handeltessichumeinerfehlerfreien
oderfehlerbehaftetenÜbertragung?
3. DecodierenSiedieEmpfangssequenz110101.Handeltessichumeinerfehlerfreien
oderfehlerbehaftetenÜbertragung?
5.Juni2015
Seite9von56
ÜbungInformationstheorieundCodierung2015
Aufgabe30:
GegebenistderfolgendeFaltungscodierer:
+
Ausgabebits
c2c1c0
c2
q1i-1 q0i-1
q1i
q0i
Eingabebits
c1
c0
+
+
1. WelcheCoderatehatdieserCodierer?
2. GebenSiedieAusgangsbitsequenzamAusgangdesCodierers,wennamEingangdie
Sequenz011010vorliegt.
3. VervollständigenSiedasfolgendeTrellisdiagramm.
t
--
--
--
--
Zustände
4. DecodierenSiedieEmpfangsfolge111011.Handeltessichumeinerfehlerfreienoder
FehlerbehaftetenÜbertragung?WievieleFehlerwurdenerkanntbzw.korrigiert?
5.Juni2015
Seite10von56
ÜbungInformationstheorieundCodierung2015
2
Lösungen
AlphabetundWörter
Aufgabe1
1. EsseidasAlphabet
a. BestimmenSie: ,
, , und
, , und
∗
gegeben.
:MengeallerWörterderLänge über .
∗
:MengeallerWörtermiteinermaximalenLänge über .
∅
0, 1, 2 00, 01, 02, 10, 11, 12, 20, 21, 22 000, 001, 002
010, 011, 012
020, 021, 022
100, 101, 102
100, 111, 112
120, 121, 121
200, 201, 202
210, 211, 212
220, 221, 222
b. Wiegroßist
?
| | | |
3
27
| ∗ | 0 3 9 27 39
2. EinAlphabet ,bestehendaus26Buchstaben,3UmlautensowiedemLeerzei‐
chenunddenneunSatzzeichen.,;:?!„“und–sollBinärundhexadezimaldar‐
gestelltwerden.
Wievielebinärebzw.hexadezimaleStellensindfürdieDarstellungeinesSym‐
bolsmindestenserforderlich?
Alphabet hatinsgesamt:| |
Binär:2
26
32zuwenig;2
3
1
9
39Symbole
64OK
Binär:Essind6Stellenerforderlich.
Hexadezimal: 1.Stelle16 15Zeichenzuwenig
2.Stelle16 16 bismax.
15 ∙ 16
15
255OK
Hexadezimal:Essind2Stellenerforderlich.
5.Juni2015
Seite11von56
ÜbungInformationstheorieundCodierung2015
CodierungundDecodierung
Aufgabe2
EinSenderkannvierCodierteNachrichtenaussenden(Eshandeltsichhierumeinerbi‐
närenBlockcodierungderLänge2):
00DieBörseistsehrfest.
11Sollenwirverkaufen?
01DieKursefallen.
10Helftunsgegensteuern!
EinesTageswirddieSymbolfolge…00110011001…empfangen.Dabeihatmandaserste
Symbolverpasstunderstdaszweiteempfangen.
Zusätzlichweißmannicht,wodieMitteilungaufhört,daderSenderimmerweitersendet.
RekonstruierenSiediegesendeteBotschaftunterderAnnahme,dassderSenderetwas
Sinnvollesübertragenhat.
Lösung:
Möglichkeit1:DasersteSymbolist0dieNachrichtlautet:DieBörseistsehrfest.Die
Kursefallen.Helftunsgegensteuern!
Möglichkeit2:DasersteSymbolist1dieNachrichtlautet:Helftunsgegensteuern!Die
Kursefallen.
DasersteZeichenwar„1“.
Aufgabe3:PräfixfreierCode
GegebenseidasAlphabet
IstdieMenge
0, 1 .
1, 011, 01110, 1110,10011 einsinnvollerCodefürfünfNachrichten?
Lösung:
Codewort2(011)istauchinCodewort3(01110)enthaltenkeinPräfixfreierCode
Codeungünstig
Aufgabe4:
BestimmenSiefürjedenderfolgendenCodes,obdiesereindeutigdecodierbaristundob
essichumeinenpräfixfreienCodehandelt.
IstderCodenichteindeutigdecodierbar,danngebenSieeineCodesequenzan,fürwelche
zweiunterschiedlicheInterpretationenalsSequenzausCodewörternexistieren.Sonstre‐
präsentierenSiedenCodemiteinemCodebaum.
1. 00, 10, 01, 11 5.Juni2015
Seite12von56
ÜbungInformationstheorieundCodierung2015
2.
0, 10, 11 3.
0, 01, 11 4.
1, 101 5.
0, 1, 01 Bemerkung: ExistierteineindeutigdecodierbarerCode,dannexistiertaucheinpräfix‐
freierCodemitdenselbenCodewortlängen.Deshalbwerdenfüreindeutig
decodierbareCodesüblicherweisePräfixfreieCodesVerwendet.
Lösung:
1.
,
,
,
IsteinBlockcodeundPräfixfreiwiealle
Blockcodes.
DaalleCodewortediegleicheLängeha‐
ben,kanneinCodenurdannPräfixeines
anderen Codewortes sein, wenn diese
identischsind.
00
0
0
1
1
0
01
10
1
11
2.
,
,
Ist präfixfrei  alle Codeworte sind
BlättereinesBaums
0
1
0
0
1
10
11
3.
,
,
Istnichtpräfixfrei,denn0istPräfixvon01.DennochistdieserCodeeindeutigdeco‐
dierbar,dennkeinCodewortSuffixeinesanderesist.EinsuffixfreierCodekannim‐
mervomEndeeinerSequenzbeginnendeindeutigdecodiertwerden.
4.
,
Istnichtpräfixfrei,denn1istPräfixvon101.Trotzdemeindeutigdecodierbar,daim‐
mereine0inderSequenzeindeutigerkanntwerdenkann.
5.Juni2015
Seite13von56
ÜbungInformationstheorieundCodierung2015
5.
, ,
KeinPräfixfreierCodeundnichteindeutigdecodierbar.
Beispiel:01und0,1sindzweiInterpretationenderselbenSequenz.
Aufgabe5:UngleichungvonKraft
EinbinärerBaumhabe
7Endknoten,derenAbstände vonderWurzelsind:
2;
3; 4
1. ExistiertdieserBaum?
2. Wennja,stellenSiediesenBaumdar.
Lösung:
1. UngleichungvonKraft:
2
2
4∙2
2∙2
0,875
1
Baumexistiert
2. Baum
l=2
l=3
l=3
l=3
l=3
l=4
l=4
Aufgabe6:UngleichungvonKraft
2. ExistiertfürfolgendeCodewortlängeneinbinärerPräfixfreierCode?Wennja,dann
konstruierenSieeinenentsprechendenCode
a.
, , , , ,
UngleichungvonKraft:
2
2
2
2
2
2
2
1
Codeexistiert
5.Juni2015
Seite14von56
ÜbungInformationstheorieundCodierung2015
l=1
l=2
l=3
l=4
l=5
b.
, , , , ,
UngleichungvonKraft:
2
2
2
2
2
2
33
32
2
1
Baum(undsomitCode)existiertnicht
c.
, , , ,
2
2
2
2
2
15
16
2
1
Codeexistiert
l=2
l=2
l=2
l=3
l=4
3. ExistiertfürfolgendeCodewortlängeneinternärerPräfixfreierCode?Wennja,dann
konstruierenSieeinenentsprechendenCode
a.
, , , , , ,
2∙3
3∙3
3
5.Juni2015
2∙3
29
27
1
Seite15von56
ÜbungInformationstheorieundCodierung2015
Codeexistiertnicht
b.
, , , , , , ,
3
2∙3
3∙3
2∙3
80
81
2∙3
1
l=1
l=1
l=2 l=2
Codeexistiert
l=3 l=3
l=4l=4
c.
3,3,3,3,3,3,2,1,1 3
2∙3
6∙3
3
1
l=1
l=1
l=2
Codeexistiert
l=3
l=3
Aufgabe7:ASCII‐Codierung
1. WielautetderASCII‐CodevomSymbol„A“(Hexadezimalzahl=41)
41
4
∙
∙
∙
1
∙
∙
1000001
∙
∙
ASCII‐CodemitParitätsbit:01000001
2. VervollständigenSiediefolgendeTabellezurUmrechnungvonDezimal‐,Hexadezi‐
mal‐undBinärzahl
Dezimalzahl
Hexadezimalzahl
Binärzahl
715
2CB
1011001011
19
13
10111
179
B3
10110011
5.Juni2015
Seite16von56
ÜbungInformationstheorieundCodierung2015
293
125
85
55
1010101
Lösung:
DezimalHexadezimal
715|
2 ∙ 256
715|
2
|
12 ∙ 16
11
2 ∙ 16
12 ∙ 16
11 ∙ 16 DezimalBinär
715|
1∙2
715|
512
0
128
0∙2
64
1∙2
8
1∙2
1011001011|
ä
2
1
0∙2
0∙2
1∙2
0∙2
1∙2
1∙2 Aufgabe8
GegebenseieineQuelleQmit4Symbolen(A,B,CundD).
DieAuftrittswahrscheinlichkeitenderSymboleseien:
0,8
0,1
0,08
0,02
1. WiegroßistdieInformationeineseinzelnenSymbols?
1
0,8
0,322
0,1
0,08
0,02
3,322
3,643
5,643
2. WiegroßistdieEntropiederQuelle?
∙
∙
0,8 ∙ 0,322
0,9941
0,1 ∙ 3,322
/
∙
0,08 ∙ 3,643
∙
∙
0,02 ∙ 5,643
3. Wie groß wäre die Entropie beigleicher Auftrittswahrscheinlichkeitder 4
Symbole?
4
5.Juni2015
2
/
Seite17von56
ÜbungInformationstheorieundCodierung2015
Aufgabe9
A B C D
EineQuelleenthält4Symbole:Q
1. BerechnenSie:
a. DenEntscheidungsgehalt
.
DerEntscheidungsgehalt=NachrichtenmengeproSymbol
H 0  m  ld N   ld 4   2
H0  2
Bit
Symbol
Bit
Symbol
b. DieEntropie
=mittlererInformationsgehalt
Entropie  H   p(xi )  I(xi )  ‐ p(xi )  ldp(xi )
H   pA  ld pA   pB  ld pB   pC  ld pC   pD  ld pD 
1
1
1
1
 ld 2    ld 4    ld 8    ld 8 
8
2
4
8
1 1 3 3
bit
     1,75
2 2 8 8
Symbol

H  1,75
Bit
Symbol
c. DieRedundanzderQuelle
R  H 0  H  2  1,75  0 ,25
R  0 ,25
.
Bit
Symbol
Bit
Symbol
2. DieQuellewirdmiteineroptimalenCodewortlängecodiert(angepasstanden
InformationsgehaltdereinzelnenSymbole).
a. BerechnenSiediemittlereCodewortlängeproSymbol
b. WielautendieCodewörterdereinzelnenSymbole?
5.Juni2015
Seite18von56
ÜbungInformationstheorieundCodierung2015
Code
A
1
2
1
1
0
B
1
4
2
2
10
C
1
8
3
3
110
D
1
8
3
3
111
c. BerechnenSiediemittlereCodewortlänge L   pi  mi  pA  mA  pB  mB  pC  mC  pD  mD
1
1
1
1
bit
 1   2  3  3  1,75
2
4
8
8
Symbol
1,75
d. BerechnenSiedieRedundanzdesCodes
R  H c  H  1,75
R0
Bit
Bit
 1,75
Symbol
Symbol
Bit
Symbol
Aufgabe10:FanoCodierung
QuelleQistgegebendurchAlphabetundabsoluteHäufigkeiten:
15
7
6
6
5
1. CodierenSiedieQuellenachFano(CodierungstabelleundCode‐Baum)
5.Juni2015
Seite19von56
ÜbungInformationstheorieundCodierung2015
Symbol A
15
B
7
C
6
D
6
E
5
0
1
0
A00
1
B01
0
C10
1
0
D110
1
E111
ZugehörigerBaum:
2. WiegroßistdiemittlereCodewortlänge?
2 ∙ 15
2,28
7
/
6
39
3∙ 6
5
/
Aufgabe11:FanoCodierung
ErstellenSiejeweilsdenCodebaumundCode‐Tabelle.GebenSiefürjedesZeichendieCo‐
dierunganundberechnenSiediemittlereCodewortlänge
1.
2.
ZeigenSie,dasseshiernachdemFanodreiunterschiedlichemöglicheCodierungengibt
unddassdieFano‐Codierungnichtimmeroptimalist
Lösung
1.
5.Juni2015
Seite20von56
ÜbungInformationstheorieundCodierung2015
Symbol C
0,33
A
0,25
B
0,25
D
0,16
0
1
0
C00
1
A01
0
B10
1
D11
AlternativeLösungAundBvertauschen
2
/
2.
Möglichkeit1:
Symbol A
0,4
B
0,2
C
0,2
D
0,2
A0
0
2
0
1
1
B10
0
C110
1
D111
/
5.Juni2015
Seite21von56
ÜbungInformationstheorieundCodierung2015
Möglichkeit2:
Symbol A
0,4
B
0,2
C
0,2
D
0,2
0
1
0
A00
1
B01
0
C10
1
D11
2
/
Möglichkeit3:
Symbol A
0,4
B
0,2
C
0,2
D
0,2
1 ∙ 0,4
2
Entropie:
A0
0
0
1
0
B100
1
C101
1
3 ∙ 0,2
/
3 ∙ 0,2
D11
2 ∙ 0,2
0,4 ∙
0,4
3 ∙ 0,2 ∙
0,2
1,92
/
DieFano‐Codierungistleidernichtoptimal.
Aufgabe12:
GegebenistdieQuelle 0,4 0,1
0,2 0,3
1. WiegroßistdieEntropiederQuelle?
∙
0,4 ∙
,
0,4
0,1 ∙
0,1
0,2 ∙
0,2
0,3 ∙
0,3
2. Fano‐Codierung
a. CodierenSiedieQuellemitdemFano‐Algorithmus
5.Juni2015
Seite22von56
ÜbungInformationstheorieundCodierung2015
A
D
0,4
0,3
C
0,2
B
0,1
0 0A
0 10D
1
1
0
110C
1
111B
b. BerechnenSiediemittlereCodewortlängeunddieRedundanzdesCodes
1 ∙ 0,4
1,9
3 ∙ 0,1
/
3 ∙ 0,2
2 ∙ 0,3
3. Shannon‐Codierung
a. CodierenSiedieQuellemitdemShannon‐Algorithmus
Symbol Binär
Code
A
0,4
1,32
2
0
0,000
00
D
0,3
1,73
2
0,4
0,011..
01
C
0,2
2,32
3
0,7
0,1011
101
B
0,1
3,32
4
0,9
0,1110
1110
b. BerechnenSiediemittlereCodewortlängeunddieRedundanzdesCodes
2 ∙ 0,4
2,4
2 ∙ 0,3
/
3 ∙ 0,2
4 ∙ 0,1
2,4
1,8463
0,5537Bit/Symbol
4. Huffman‐Codierung
a. CodierenSiedieQuellemitdemHuffmann‐Algorithmus
Sortierung:A>D>C>B
5.Juni2015
Seite23von56
ÜbungInformationstheorieundCodierung2015
W
0
0
1
1
0,6
A
A1
0,4
B011
D
C010
0
0,3
1
0,3
D00
C
B
0,2
0,1
b. BerechnenSiediemittlereCodewortlängeunddieRedundanzdesCodes
1 ∙ 0,4
1,9
3 ∙ 0,1
/
3 ∙ 0,2
2 ∙ 0,3
5. VergleichenSiedieErgebnissederdreiAlgorithmen.
Esgilt
und
, DieShannonCodierungistalsonichtoptimal
Aufgabe13:Shannon‐Codierung
EineQuelleenthälteinZeichenvorratvon4Zeichen(A,B,C,D).DieAuftrittswahrschein‐
lichkeitendereinzelnenZeichenseien:
, ;
, ;
,
;
,
.
1. WiegroßsinddieInformationsgehaltedereinzelnenZeichen?
 1 
  ld ( px 
Def:Informationsgehalt: I ( x)  ld 
 p ( x) 
Symbol Wahrscheinlichkeit
Informationsgehalt
A
0,8
0,8
0,32
B
0,1
0,1
3,321
C
0,08
0,08
3,64
D
0,02
0,02
5,64
5.Juni2015
Seite24von56
ÜbungInformationstheorieundCodierung2015
2. WiegroßistdieEntropiederQuelle?
EntropiederQuelle?
H   p( xi )  I ( xi )   p( x)  ld  p( xi )
H  p( A) I( x A )  p(B) I( xB )  p(C ) I( xC )  p(D) I( xD )
H  0,8  ld(0,8)  0,1  ld(0,1)  0,08  ld(0 ,08 )  0,02  ld(0,02)
H  0,994 Bit / Symbol
WiegroßwäredieEntropiederQuellebeigleicherAuftrittswahrscheinlichkeit
dervierZeichen?
p( A)  p(B)  p(C )  p(D)  H  H0  ld(4)
H  Ho  2Bit/Symbol
3. FürdieÜbertragungsolleinBinärcodenachShannonentwickeltwerden.
Symbol
Binär
Code
0,00
0
A
0,8
0,321
1
0
B
0,1
3,321
4
0,8
0,11001…
1100
C
0,08
3,64
4
0,9
0,11100…
1110
D
0,02
5,64
6
0,98
0,111110… 111110
WelchemittlereCodewortlängeergibtsichausdemerstelltenCode.
1 ∙ 0,8
1,64
4 ∙ 0,1
/
4 ∙ 0,08
6 ∙ 0,02
Aufgabe14:HuffmanCodierung
GegebenseidiefolgendeNachricht:
RZROZPZZ
1. GebenSiediezugehörigeHuffman‐Codierungan.
2. Symbol
R
Z
1
4
5.Juni2015
1
2
O
P
1
8
1
8
Seite25von56
ÜbungInformationstheorieundCodierung2015
01
Huffman-Code
1
1
S
1
Z
000
0
1
1
4
001
R
1
4
0
1
2
1
O
1
4
0
P
1
8
1
8
3. ErmittelnSiedurchRechnung,obessichdabeiumeinenoptimalenCodehan‐
deltundbegründenSiedasErgebnis.WelcheRegeltriffthierzu?
1 14
1
1
1
L  2   1  3   3    1,75
4 
2 
8 
8 8

R
Z
O
P
L  1,75 Bit / Symbol
H:Entropie; H 
1
1
1
1
 ld (4)   ld (2)   ld (8)   ld (8)  1,75 bit / Symbol
4
2
8
8
H  1,75 Bit / Symbol
0optimalerCode
Aufgabe15:HuffmanCodierung
FüreinenZeichenvorratsindfolgendeAuftrittswahrscheinlichkeitengegeben:
Zeichen
R
Häufigkeit
0,09 0,01
5.Juni2015
E
H
K
P
A
S
0,4
0,05
0,12
0,13
0,2
Seite26von56
ÜbungInformationstheorieundCodierung2015
1. LeitenSiediezugehörigeHuffman‐Codierungher
Code:
1
0
H0
1
1
0,6
1
0,35
1
P100
0,4
A101
S111
0
1
S
0,2
H
0
0
0,25
R1101
A
P
K11001
0,12
E11000
0,15
0
0,13
1
0,06
0
R
0,09
K
E
0,05
0,01
2. BerechnenSiedieRedundanzdesCodes
R  LH
 1 
 H   p( xi )  ld
 p( xi ) 
L   p( xi )  mi
L  0,09  4  0,01  5  0,04  1  0,05  5  0,12  3  0,13  3  0,2  3
L  2,05 Bit / Symbol
 0,09  ld 0,09  0,01  ld 0,01  0,04  ld 0,04  0,05  ld 0,05  0,12  ld 0,12

H  

  0,13  ld 0,13  0,2  ld(0,2)
H  1,995 Bit / Symbol
R  L  H  2,05  1,995 Bit / Symbol  0,055 Bit / Symbol 3. CodierenSiedieZeichenfolgen
a. KEKSE
K
E
K
11001
5.Juni2015
11000
11001
S
E
111
11000
Seite27von56
ÜbungInformationstheorieundCodierung2015
b. HARKE
H
A
R
0
101
1101 K
11001
E
11000
4. IstderCodeoptimal?WannliefertderHuffman‐Algorithmuseinenoptimalen
Code?
Nein,daR0
WenndieWahrscheinlichkeit=1/(2i)ist
Aufgabe16:
GegebenseidieQuelle
,
,
,
1. Codieren Sie dieSymbolevon mit Huffman und berechnen Sie die mittlere
Codewortlänge
1 ∙ 0,7
2 ∙ 0,2 2 ∙ 0,1
1,3 /
2. CodierenSieSymbolpaarevon mitHuffmanundbestimmenSiediemittlere
CodewortlängeproSymbol.VergleichenSiebeideErgebnissemitderEntropie
derQuelle
Symbol Codierung
∙
AA
0,49
0
1
0,49
AB
0,14
110
3
0,42
AC
0,07
1011
4
0,26
BA
0,14
111
3
0,42
BB
0,04
1000
4
0,16
BC
0,02
10010
5
0,1
CA
0,07
1010
4
0,28
CB
0,02
100111
6
0,12
5.Juni2015
Seite28von56
ÜbungInformationstheorieundCodierung2015
CC
0,01
100110
6
0,06
2,33
1,165
1,3
Aufgabe17:
GegebenistfolgendeBinärsequenz:
0001 0000 1010 0000 1000 0011 0010 0010 1. BerechnenSiefürdieobigeNachricht:
a. DenEntscheidungsgehalt
Symbole0und12Symbole:
2 1
b. DieEntropie
Insgesamt32ZeichenmitdenSymbol‐Wahrscheinlichkeiten:
5.Juni2015
Seite29von56
ÜbungInformationstheorieundCodierung2015
Symbol
Wahrscheinlichkeit
0
24
32
3
4
1
8
32
1
4
 1 
H   p(x i )  I(x i )  p(x i )  ld 

 p(x i ) 
3 4 1
 ld   ld 4
4 3 4
 0 ,81 Bit
H  0,81bit / Symbol
c. DieRedundanzproSymbolunddiegesamteRedundanzderNachricht.
RedundanzproSymbol
–
1
0,81
0,19
/
R  0,19 Bit / Symbol
Gesamt‐Redundanz
32
R ges  6 ,08 Bit
2. EssindjeweilszweibenachbarteBitszueinemSymbolzusammenzufassen.Be‐
antwortenSiefürdiesichdarausergebendeSymbolfolgealleFragengemäß1a‐
c.
ZweibenachbarteBitszueinemSymbolzusammenfassenEsentstehen4neueSym‐
bolemitfolgendenWahrscheinlichkeiten:
Symbol
Wahrscheinlichkeit
A=00
9
16
B=01
1
16
C=10
5
16
D=11
1
16
5.Juni2015
Seite30von56
ÜbungInformationstheorieundCodierung2015
a. DerEntscheidungsgehalt
4
2
b. DieEntropie
 1 
H   p(x i )  I(x i )  p(x i )  ld 

 p(x i ) 
9  16  1
5  16  1
 ld    ld 16  ld    ld 16
16  9  16
16  5  16
 1,49 Bit / Symbol
H  1,49 Bit / Symbol
c. DieRedundanzproSymbolunddiegesamteRedundanzderNachricht.
RedundanzproSymbolR=H–H0=2–1,49=0,51Bit/Symbol
R  0,51 Bit / Symbol
Gesamt‐Redundanz
16 ∙
16
∙ 0,51
8,16
Rges  8,16 Bit
3. CodierenSiedieSymbolfolgemitShannon.
Symbol
Binär
Code
A
0,83
9
 0,5625 16
1
0
0,00
0
C
1,678
5
 0,3125 16
2
0,5625
0,1001
10
B
4
1
 0,0625 16
4
0,875
0,1110
1110
D
4
1
 0,0625 16
4
0,9375
0,1111
1111
WelcheRedundanzergibtsich?
1∙
9
16
5.Juni2015
4∙
1
16
2∙
5
16
4∙
1
16
27
16
1,6875
Seite31von56
ÜbungInformationstheorieundCodierung2015
1,6875
L
H
0,1975
4. CodierenSiedieSymbolfolgemitHuffman.WelcheRedundanzergibtsichjetzt?
Code:
1
A1
0
1
B000
A
9/16
C01
7/16
1
0
D001
C
5/16
1
2/16
0
D
B
1/16
1/16
RedundanzdesCodes:
1∙
9
16
1,5625
L
H
3∙
1
16
2∙
5
16
3∙
1
16
1,5625
0,0725
Aufgabe18:
GegebenistfolgendeNachricht:
AACDABCAAADBACAC
1. Wiegroßsind
a. derEntscheidungsgehaltderNachrichtenquelle,
Insgesamt16Zeichen
5.Juni2015
Seite32von56
ÜbungInformationstheorieundCodierung2015
8 1

16 2
4 1
p(C )  
16 4
2 1

16 8 2 1
p(D)  
16 8
p( A) 
Wahrscheinlichkeiten
p(B ) 
H0  ld4  2 Bit
b. derInformationsgehaltdereinzelnenSymbole,
Symbol
 1 
 I x i   ld
 px i  
A
ld2  1 Bit B
ld8  3 Bit C
ld4  2 Bit D
ld8  3 Bit c. dieEntropieundRedundanzderNachricht.
 1 
 Entropie: H   pxi  ld


p
x
i


H
2
28
8
2
4
1 3   2  3 
 1,75
16
16
16
16
16
H  1,75 Bit / Symbol Redundanz:
2
1,75
R  0,25 Bit / Symbol
2. DieSymbolesollenbinärcodiertunddannübertragenwerden.DerCodelautet:
A=00
B=01
C=10
D=11
a. GebenSiedenInformationsgehaltderbinärenZeichen0und1an
A,B,C,DersetzendurchBinärzeichenundneudurchzählen:22x LOW und 10x
HIGH
Informationsgehalt:
22
32
5.Juni2015
11
⟹
16
16
11
0,54
Seite33von56
ÜbungInformationstheorieundCodierung2015
10
32
5
⟹
16
16
5
1,68
b. WelcheRedundanzergibtsichjetzt?
Entropie: H  p0  I0  p1  I1  0,896 Bit H  0,896 Bit Redundanz: R H0  H  1  0,896 0,104Bit R  0,104 Bit c. MachenSieeinenVorschlag,wiedieRedundanzdurcheineoptimierteCo‐
dierungverringertwerdenkann.
RedundanzreduktiondurchangepassteCodewortlängederZeichen.HäufigeZei‐
chen mit kurzer Codewortlänge, seltene Zeichen mit längerer Codewortlänge
(Code erstellen über Huffman‐Code). Mittlere Codewortlänge wird minimiert.
Redundanz:R=L‐H
Aufgabe19:
EinefarbigeGrafikbestehtaus1MillionBildpunkten,dieROT,GRÜN,BLAU,WEISSund
SCHWARZ aussehen können. Das gesamte Bild wird in 1 Sekunde übertragen. Alle ge‐
nanntenFarben/HelligkeitentreteninderGrafikgleichhäufigauf.
1. BerechnenSiedenEntscheidungsgehaltderQuelle„farbigeGrafik“undgeben
SiedenInformationsgehaltfürjedesdermöglichenZeichen(Farbenbzw.Hel‐
ligkeitswerte)an.
Entscheidungsgehalt
N=5Zeichen
5
Informationsgehalt
2,32
 1 
 I( xi )  ld
 p( xi ) 
1
Alle5Zeichentretengleichwahrscheinlichauf  pxi   5
 1 
  ld(5)  2,32Bit / Symbol I( xi )  ld
 p( xi ) 
I(xi )  2,32 bit/Symbol Entropie   p(xi )  I(xi ) BeigleicherWahrscheinlichkeit H  H0  2,32 bit/Symbol
5.Juni2015
Seite34von56
ÜbungInformationstheorieundCodierung2015

H  bit
Symbol

Nachrichtenfluss H '  

  sec
Symbol 

106Bildpunkte/sec
 =ZeitindereinQuellzeichenausgewähltundübertragenwird=
H'
2,32 Bit / Zeichen
106 sec/ Zeichen

1sec
 10  6 sec 106 pkt
H' 2,32MBit/sec Redundanz
R  H0  H  0 daGleichverteilung 2. Die Zustände der Bildpunkte sollen binär codiert werden (gleiche Codewort‐
länge). Welcher Datenfluss ergibt sich hierbei? Welche Redundanz liegt jetzt
vor?
BinäreCodierungderBildpunkte.GleicheCodewortlängebenutzen.
5Zeichen=> H0  2,32 bit/Symbol
FürdieCodierungwerden3Bit/Zeichenverwendet.
z.B.:
Rot
=>
000
Grün =>
001
Blau =>
010
Weiß =>
011
Schwarz
=>
100
Datenfluss=?Bit/sec
106 Bildpunkte/sec übertragen
Eswerden 
pro
Bildpunkt
:
3
Bit/Bildpu
nkte

H'  3 MBit/sec Redundanz
3
5.Juni2015
2,32
Seite35von56
ÜbungInformationstheorieundCodierung2015
0,68
3. StellenSiedieZeichenmitdemHuffman‐Codedar.WelchemittlereCodewort‐
längeergibtsich?WelcheRedundanzresultiert?
1
1
0
3/5
1
0
2/5
2/5
1
1
0
0
1/5
1/5
1/5
1/5
1/5
Schwarz
Weiss
Blau
Grün
Rot
Rot
=>
10
Grün =>
110
Blau =>
111
Weiß =>
00
Schwarz
=>
01
L
1
2  3  3  2  2  2,4 bit 5
Symbol
R  L  H  2,4
0,08
5.Juni2015
bit
bit
 2,32
Symbol
Symbol
Seite36von56
ÜbungInformationstheorieundCodierung2015
DiskreteQuellemitGedächtnis
Aufgabe20:
GegebenSeieineQuelle
, , mitGedächtnis.FürdieQuellensymbolegeltendie
folgendenbedingtenWahrscheinlichkeiten:
| 1
3
1
3
1
3
1
4
1
2
1
4
1
4
1
4
1
2
1. StellenSiedieQuelleanschaulichmitHilfeeinesMarkov‐Diagramms1.Ordnung
dar.
2. BestimmenSiedieSymbolwahrscheinlichkeiten
∙
∙
/
1
3
3
∙
8
∙
1
4
3
∙
8
∙
∙
2
∙
3
1
3
∙
/
∙
/
∙
/
1
∙ 4
∙
∙
/
/
und
1 /
1
∙
2
∙
5.Juni2015
∙
,
1
2
/
1
∙ 4
2 ∙
/
Seite37von56
ÜbungInformationstheorieundCodierung2015
2
∙
3
1
∙
2
3 AusdenGleichungen(2)und(3)folgt
EingesetztinGleichung(1)
3
∙
8
⟹
3
∙
8
6
∙
8
3
∙
4
Esgiltdennoch:
4
∙
3
1⟹
4
∙
3
3
11
11
∙
3
4
11
4
11
3. BerechnenSiedieVerbundwahrscheinlichkeiten
Esgilt:
,
∙
,
z.B.
/
1
,
1
11
1
11
1
11
1
11
2
11
1
11
1
11
1
11
2
11
,
∙
/
∙
4. Berechnen Sie dieEntropie der Quelle,diebedingte Entropie unddie Verbun‐
dentropie
EntropiederQuelleX:
3
∙
11
3
11
1,0412
BedingteEntropie:
5.Juni2015
4
∙
11
∑
∙
4
11
4
∙
11
4
11
1,0412
/
∑
∑
,
∙
/
Seite38von56
ÜbungInformationstheorieundCodierung2015
/
,
∙
/
,
∙
/
,
∙
/
,
∙
/
,
∙
/
,
∙
/
,
/
∙
,
1,0412
,
2,564
,
,
∙
/
,
∙
/
1,5228
Verbundentropie:
1
2
/
,
/
1,5228
2,564
1,282
Aufgabe21:Markov‐Quelle
EinediskreteQuelle
Abbildung.
,
mitGedächtnishabedenZustandsgrafausderfolgenden
3/4
B
A
?
?
1. GebenSiedieÜbergangswahrscheinlichkeitenan.
/
1
,
4
/
1
/
3
,
4
/
0
2. BerechnenSiedieAuftrittswahrscheinlichkeitendereinzelnenZustände.
∙
∙
4
,
7
5.Juni2015
/
1
4
1
∙
/
∙ 1
1
3
∙
4
3
7
Seite39von56
ÜbungInformationstheorieundCodierung2015
3. GebenSiedieEntropiederQuelleanunterBerücksichtigungderÜbergangs‐
wahrscheinlichkeiten.
BedingteEntropie:
,
/
∙
/
/
/
/
/
/
/
/
/
∙
/
∙
/
/
∙
/
/
0
∙
∙
1∙
/
∙
/
0,81
/
∙
1
0
0∙
4
∙ 0,81
7
∙
0,4629
0,4629
4. FassenSiejeweilsdreiZeichenzueinemSymbolzusammen.BerechnenSie
dieWahrscheinlichkeitendermöglichenSymbole.
Symbol
Wahrscheinlichkeit
∙
/
∙
/
4 1 1
∙ ∙
7 4 4
1
28
∙
/
∙
/
4 1 3
∙ ∙
7 4 4
3
28
∙
/
∙
/
4 3
∙ ∙1
7 4
12
28
∙
/
∙
/
0
∙
/
∙
/
3
1
∙1∙
7
4
3
28
∙
/
∙
/
3
3
∙1∙
7
4
9
28
BBA
∙
/
∙
/
0
BBB
∙
/
∙
/
0
AAA
AAB
ABA
ABB
BAA
BAB
5.Juni2015
Seite40von56
ÜbungInformationstheorieundCodierung2015
5. FührenSieeineHuffman‐CodierungdurchundgebenSiediemittlereCode‐
wortlängedesCodes.
Codierung:
AAA1010
AAB100
ABA0
BAA1011
BAB11
MittlereCodewortlänge :
4∙
1
28
3∙
3
28
1∙
4∙
3
28
2∙
9
28
55
28
1,964
0,654
3
12
28
Kanalcodierung
Aufgabe22:(A32Dr.Jäger)
GegebenseieinsymmetrischerbinärerKanal(BSC),dessenEingangszeichen und die Auftrittswahrscheinlichkeiten
0,4 und
0,6 haben und dessen Bit‐
fehlerwahrscheinlichkeit
0,05beträgt.
1. BestimmenSiedieEntropiederKanalausgabe
∙
∙
∙
5.Juni2015
,
∙
/
∙
/
Seite41von56
ÜbungInformationstheorieundCodierung2015
0,4 ∙ 1
0,05
0,41
0,6 ∙ 0,05
0,41 ∙
∙
0,4 ∙ 0,05
1
0,59
0,6 ∙ 0,95
0,59 Oder
1
0,41 ∙
0,41
0,59 ∙
0,59
0,976
0,976
2. dieEntropiederIrrelevanz
/
|
/
∙
,
/
∙
/
∙
/
∙
/
∙
/
∙
/
∙
/
∙
/
∙
/
∙
/
∙ 1
∙
1
∙
∙
∙ 1
∙
1
∙
∙
/
/
1
0,95 ∙
/
∙
1
0,95
0,05 ∙
3. dieTransinformation
/
,
0,976
,
0,69
5.Juni2015
0,29
0,05 0,29
,
:Shannon‐Gleichung
∙
,
.
0,69
Seite42von56
ÜbungInformationstheorieundCodierung2015
Aufgabe23: (A31 Dr. Jäger) GegebenseiderskizzierteKanal
WiegroßistdieKanalkapazität ,wenndieEingangs‐undAusgangszeichengleich‐
verteiltsind?
∙
1
∙
1
Beweis:
,
/
GleichverteilteSymboleamKanalausgang
/
,
,
∙
∙
1
∙
3
/
,
,
/
1
∙
3
/
1
3
1
∙
3
/
0
1
∙
3
/
/
,
∙
/
∙
,
∙
1
∙ 1
3
∙
5.Juni2015
/
3 3
3
3
,
,
∙
1
1
∙
3
∙
3
1
3
∙
∙
/
/
,
,
0
,
∙
0
1
/
,
,
∙
1
∙ ∙
3
1
∙ 1
3
,
,
/
∙
∙
,
,
1
∙ 1
3
∙
1
∙
1
1
∙
3
Seite43von56
ÜbungInformationstheorieundCodierung2015

/
3
Aufgabe24:(A30 Dr. Jäger) GegebenseieinBSC‐KanalmiteinerÜbertragungsrate
wahrscheinlichkeitvon
0,1.
/ undeinerBitfehler‐
1
DieDaten,dieüberdiesenKanalübertragenwerdensollen,stammenvoneinerbinären
Quelle( und )mitdenAuftrittswahrscheinlichkeiten
und
.DieSymbole
derQuellewerdenstatistischunabhängigvoneinanderausgewählt.
1. WiegroßistdieKanalkapazität ?
1
∙ max
∙ max
,
∙ 1
1
∙ 1
∙ 1
533
0,1 ∙
0,1
,
∙
1
1
0,1 ∙
1
∙
1
0,1 /
2. WiegroßistdieEntropiederQuellemit
0,3 ⟹
0,881
, und
∙
0,3 ∙
0,3
, ?
0,7 ∙
0,7 /
3. WelchemaximaleSymbolrate
den?
kannimPrinzipfehlerfreiübertragenwer‐
SatzderKanalkapazität:
/
/
Symbolrate
Bitrate
/
1
604
533 /
0,881 /
/
604
/
Aufgabe25:
Es sei ein fehlererkennender und fehlerkorrigierender Code über dem Alphabet 0, 1 miteinerCodewortlänge 20gegeben.
5.Juni2015
Seite44von56
ÜbungInformationstheorieundCodierung2015
1. Wie viele Nachrichtenstellen können mit diesem Code übertragen werden,
wennbiszu3Fehlerkorrigiertwerdensollen?
3und
20.Esgilt:
0
1
3
2
1
1
5
9
11
2
2!
!
2 !
3!
3 !
11
10,4 ⟹ 20
!
1 !
1
6
2
1351
!
1
9
2. WievieleverschiedeneNachrichtenkönnendannmaximalcodiertwerden?
Eskönnenmaximal2
512Nachrichtencodiertwerden
2
3. WiegroßistdieMinimaldistanzdesCodes?
2
2
2
1
Hiergilt:
2
1
2∙3
1
7
7
4. WievieleFehler
können(ggf.ohneKorrekturmöglichkeit)erkanntwerden?
1
1
6
6
Aufgabe26:
EinHamming‐CodederLänge
Bestätigungeingesetztwerden.
sollzurreinenFehlererkennungmitanschließender
DieBitfehlerwahrscheinlichkeiteinessymmetrischenBinärkanalsbeträgt
5 ∙ 10 1. WiegroßistdieWahrscheinlichkeit,dasseinCodewortfehlerhaftempfangen
wird?
1
1
1
1
1
0,0345
0,0345 5.Juni2015
Seite45von56
ÜbungInformationstheorieundCodierung2015
2. Wie groß ist die Wahrscheinlichkeit, dass ein fehlerbehaftetes Empfangswort
nichterkanntwird?
Essollen3oder6Fehlersein.
7
3
7
6
1
4,288 ∙ 10 1
4,288 ∙ 10
Aufgabe27:
Gegeben sei ein linearer Blockcode über dem Alphabet matrix 0
1
1
1
0
1
0
1
0
1
0
0
1
1
0, 1 mit der Generator‐
0
1
0
0 1
1
1
1. StellenSiedenvollständigenCodeauf(ListederNachrichtenwörtermitdenzu‐
gehörigenCodewörtern).
0
1
1
1
0
1
0
1
0
1
0
0
1
1
0
1
0
0
1
1
1
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
0
0
0
0
0
0
0
0
1
0
0
1
1
1
1
0
1
0
0
1
1
1
1
1
0
1
0
0
0
1
1
1
0
1
0
0
0
1
1
1
0
1
1
1
0
1
0
0
1
1
0
0
1
1
1
0
0 4 4 4 4 4 4 4
2. BerechnenSie
,
und
desCodes.
4
3
1⟹
2
2
4;
5.Juni2015
1
3;
1
Seite46von56
ÜbungInformationstheorieundCodierung2015
3. GebenSieallemöglichenVektoren an,dieinderKorrigierkugel
liegen.
um
VektoreninderKugelhabeneinenBitunterschiedzumgültigenCodewortc,da
ist.
0111010 ;
111010 ;
4. WielautetdieGeneratormatrix
→
→ →
0
1
1
1
0
1
0
1
0
1
0
0
1
1
0
1
0
0
1
1
1

0 11010
⋯
´ deszugehörigenseparierbarenCodes?
′
⨁
′

′
⨁
5. StellenSiedieKontrollmatrix
1
0
0
1 ;
1
1
0
⨁
′
1
0
0
1
1
1
0
1
1
1
0
1
1
1
0
0
1
1
1
′
0
1
0
0 ;
1
1
1
′
0
0
1
1 1
0
1
0
0
0
1 1
0
1
fürdenseparierbarenCodeauf.
0
1
1
1
1
1
0
1
|
|
|
|
0
0
0
0
0
0
0
0
0
0
0
0
6. GebenSiedieGleichungenzurErmittlungderKontrollstellenan(Ablesenaus
derKontrollmatrix).
⨁ ⨁ ⨁ ⨁ ⨁ 7. WielautendanndiezugehörigenPrüfgleichungen?
⨁ ⨁ ⨁ ⨁ ⨁ ⨁ ⨁ 5.Juni2015
Seite47von56
ÜbungInformationstheorieundCodierung2015
⨁ ⨁ 8. Erstellen Sie aus der Kontrollmatrix
die vollständige Syndromtabelle (für
Einzelfehler).KönnenalleEinzelfehlerkorrigiertwerden?
∙
∙ da
∙
∙
0(Orthogonal)
∙ :IsteinFehlervektormit1Bitfehler
1
0
;
0
⋮
0
1
;
0
⋮
0
0
1
⋮
∙ ,wobei eineEinheitsmatrixist.
DieVollständigeSyndromtabelle:
⋯ SyndromTabelle:
Ja Es können Einzelfehler korrigiert werden (Durch Vergleich mit den Spalten der
Kontrollmatrix .).
Z.B.FehleranBit3Ergebnis =dritteSpaltevon .
9. ZeigenSiedann(durchBerechnungdermöglichenSyndrome),dasssichauch
alleBündelfehlerderLänge2korrigierenlassen.
1
1
1
0
Prüfmatrix:
Fehlermatrix
∙
5.Juni2015
1
1
0
0
0
0
0
0
1
1
1
1
1
0
1
0
1
1
0
0
0
0
|
|
|
|
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
:Syndromtabelle
Seite48von56
ÜbungInformationstheorieundCodierung2015
1
1
1
0
0
1
1
1
1
1
0
1
|
|
|
|
0
0
0
0
0
0
0
0
0
1
0 1
0 0
∙ 0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
0
1
0
0
1
0
1
1
1
0
0
0
1
1
0
0
0
1
1
AlleSpaltenvektorenderSyndromtabellesindverschiedenMankannalsoBündelfeh‐
lererkennenundkorrigieren.
10. Wielautendiezudenfolgenden(verfälschten)Empfangsvektoren gehören‐
den(korrigierten)Codewörter ;
;
1
1
1
0
∙
0
1
1
1
1
1
0
1
FehlerinBit3.
1
1
1
0
∙
|
|
|
|
0
0
0
0
0
0
0
0
0
0011101 0
1
1
1
1
1
0
1
|
|
|
|
0
0
0
0
0
0
0
0
0
0
0
0
0
0
∙ 1
0
1
0
1
1
1
 dritte Spalte aus
0
1
0
0
0
1
0
∙ 0
0
1
0
0
1
0
0
1

ErsteSpalteausderSyndromtabellefürBündelfehlerFehlerinBit1undinBit2.

1110100 1
1
1
0
∙
0
1
1
1
1
1
0
1
|
|
|
|
0
0
0
0
0
0
0
0
0
1
1
0
1
0
∙ 1
0
1
1
0
1
0
1
0
ZweiteSpalteausderSyndromtabellefürBündelfehlerFehlerinBit2undinBit3.

1001110 Aufgabe28:
GegebenseieinzyklischerCodeCüber 5.Juni2015
0,1 mitdemGeneratorpolynom
1,derCodewörterderLänge 7erzeugt. Seite49von56
ÜbungInformationstheorieundCodierung2015
1. WievieleKontroll‐undNachrichtenstellenhatderCode?
1
4:HöchsteOrdnungimGeneratorpolynom.
Kontrollstellen:
Nachrichtenstellen:
7 4 3
2. GebenSiediezugehörigeGeneratormatrix
1
desCodesan.
1
1
1
0
1
0
0
00 
3. CodierenSiedieNachrichtenvektoren
riellerundinpolynomialerDarstellung.
0
1
1
1
0
1
0
und
0
0
1
1
1
0
1
invekto‐
Vektoriell:
∙
1010011 ∙
1101001 Polynomial:
∙
z
1⊕1 1⊕1⊕1 1
z
1 ∙
1⊕1 1 z
1
1⊕1 z
1
1010011 ∙
1⊕1 1
1 ∙
1 1
1⊕1 1
1101001 4. KonstruierenSiedieCodewortpolynomedeszugehörigenseparierbarenCodes
zudenNachrichtenwörtern
und
.
Schritt1:
∙
∙
∙
5.Juni2015
1 ∙
∙
Seite50von56
ÜbungInformationstheorieundCodierung2015
Schritt2:DivisiondesPolynoms
∙
:
∙
durch
1 :
1
∙
:
:
1
1
:
1
Schritt3:
1
:
1
1
∙
1
∙
1
∙
1010011 0100111 5. ErstellenSieeineSyndromtabellefüralleEinzelfehler.
istohneRestdurch
teilbar.
⟹
⟹PolynomdivisiondurchführenundRestalsSyndromverwenden.

:

1
; :

1
1
1; :
5.Juni2015
1
1 ⟹ Seite51von56
ÜbungInformationstheorieundCodierung2015

:
1 ⟹ 
:
1 ⟹ 
:
1 ⟹ 
1:
1 ⟹ 1
6. Es werden das Wort
und das Wort
empfangen.PrüfenSie,obessichumgültigeCodewörterhandeltundkorrigie‐
renSiegegebenenfallsdieEmpfangswörter.
berechnenunddannmitSyndromvergleichen
1001001
1
⟹
:
1
1 ∶
1 ∶
1
LautSyndromtabellegilt:
1
;
FehlerinBit2
istkeingültigesEmpfangswort. wirdkorrigiertzu
0100111
1
⟹
:
1 01001 1 ∶
1
0
1;
isteingültigesEmpfangswort.Esgiltalso
0100111 Faltungscodierung
Aufgabe29:
GegebenisteinCodiererfüreinenFaltungscodederrate
länge2.
mitderSchieberegister‐
5.Juni2015
Seite52von56
ÜbungInformationstheorieundCodierung2015
1. ZeichnenSiedasTrellis‐unddasZustandsdiagramm.
p  1 Eingabebits

p(k 1)
 2 Zustände(Zust.0,Zust.1)
  Es existieren2
k  2 Zellengruppen
Zustandsdiagramm
Ausgang=C1C0
Trellisdiagramm
2. DecodierenSiedieEmpfangssequenz100101. Handeltessichumeinerfehlerfreien
oderfehlerbehaftetenÜbertragung?
0
01
01
1
1
1
1
0
10
1
0
01
1
0
11
0
00
0
11
10
0
01
1
0
111istdiegesendeteFolge.fehlerfreiÜbertragung
3. DecodierenSiedieEmpfangssequenz110101. Handeltessichumeinerfehlerfreien
oderfehlerbehaftetenÜbertragung?
111istdiegesendeteFolge.FehlerbehafteteÜbertragung
5.Juni2015
Seite53von56
ÜbungInformationstheorieundCodierung2015
Aufgabe30:
GegebenistderfolgendeFaltungscodierer:
WelcheCoderatehatdieserCodierer?
2
3
5. GebenSiedieAusgangsbitsequenzamAusgangdesCodierers,wennamEingangdie
Sequenz011010vorliegt.
⨁
⨁
⨁
⨁
⨁
0
1
0
0
0
0
1
1
0
0
1
1
0
0
1
0
1
0
0
0
1
Ausgabebitsequenz:001100001
5.Juni2015
Seite54von56
ÜbungInformationstheorieundCodierung2015
6. VervollständigenSiedasfolgendeTrellisdiagramm.
t
000
00
00
000
00
01
010
01
10
011
10
11
011
11
Zustände
7. DecodierenSiedieEmpfangsfolge111011.Handeltessichumeinerfehlerfreienoder
FehlerbehaftetenÜbertragung?WievieleFehlerwurdenerkanntbzw.korrigiert?
111
0
011
3
2
2
2
0
10
1
0
1
5.Juni2015
Seite55von56
ÜbungInformationstheorieundCodierung2015


FehlerfreieÜbertragung0Fehler
DecodierteSequenz1010
5.Juni2015
Seite56von56

Download Report