Shannon < Netzwerke < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 14:13 Mo 08.12.2008 | | Autor: | DAB268 |
| Aufgabe | Eine Informationsquelle sende sechs Zeichen A, B, C, D, E und F mit folgender Auftrittswahrscheinlichkeit aus: A 10%, B 5%, C 40%, D 20%, E 5%, F 20%. Dabei sei jedes Sendeereignis vom vorherigen unabhängig.
(a) Berechnen Sie Entropie, relative Entropie und Redundanz dieser Informationsquelle (nutzen Sie dabei die Werte log2(10)=3,32 und log2(6)=2,58).
(b) Kodieren Sie die Symbole nach der Methode von Fano (es gibt dabei mehrere Möglichkeiten, die gleichwertig sind). Berechnen Sie die zugehörige durchschnittliche Bitlänge pro Symbol.
(c) Wieso bleibt die durchschnittliche Bitlänge aus (b) etwas über dem Idealwert der Entropie aus (a)? |
Hallo.
Hier meine Lösungen. Bitte schaut mal ob diese korrekt sind:
(a)
H = [mm] -\bruch{1}{10} \cdot log_2 \bruch{1}{10} [/mm] - [mm] \bruch{1}{20} \cdot log_2 \bruch{1}{20} [/mm] - [mm] \bruch{2}{5} \cdot log_2 \bruch{2}{5} [/mm] - [mm] \bruch{2}{5} \cdot log_2 \bruch{2}{5} [/mm] - [mm] \bruch{1}{20} \cdot log_2 \bruch{1}{20} [/mm] - [mm] \bruch{2}{5} \cdot log_2 \bruch{2}{5}
[/mm]
H = [mm] \bruch{log_2 10}{10} [/mm] + [mm] \bruch{2 \cdot log_2 20}{20} [/mm] + [mm] \bruch{2 \cdot log_2 5}{5} [/mm] - [mm] \bruch{2}{5} [/mm] + [mm] \bruch{2 \cdot log_2 5}{5}
[/mm]
H = [mm] \bruch{10 \cdot log_2 10 + 10 \cdot log_2 20 + 80 \cdot log_2 5 - 40}{100}
[/mm]
H = [mm] \bruch{10 \cdot 3,32 +10 \cdot 4,32 + 80 \cdot 2,32 - 40}{100}
[/mm]
H= [mm] \bruch{33,2 + 43,2 + 185,6 -40}{100}
[/mm]
H= [mm] \bruch{222}{100} [/mm] = 2,22
[mm] H_{max} [/mm] = - 6 [mm] \cdot (\bruch{1}{6} \cdot log_2 \bruch{1}{6} [/mm] = - [mm] log_2 \bruch{1}{6} [/mm] = [mm] log_2 [/mm] 6 = 2,58
[mm] H_{rel} [/mm] = [mm] \bruch{H}{H_{max}} [/mm] = [mm] \bruch{2,22}{2,58} [/mm] = 0,86
[mm] {Redundanz}=1-H_{rel} [/mm] = 1 - 0,86 = 0,14
(b)
C 0
D 10
F 110
A 1110
B 11110
E 11111
[mm] DurchschnittlicheBitlaenge=\bruch{\bruch{2}{5}+2 \cdot\bruch{1}{5} + 3 \cdot \bruch{1}{5} + 4 \cdot \bruch{1}{10} + 5 \cdot \bruch{1}{20} +5 \cdot \bruch{1}{20}}{6} [/mm] = [mm] \bruch{\bruch{7}{5} + \bruch{4}{10} + \bruch{10}{20}}{6}= \bruch{\bruch{23}{10}}{6} [/mm] = [mm] \bruch{23}{60} [/mm] = 0,38
c) Leider keine Lösung, aber ich hab mir schonmal gedacht, dass es evtl. daran liegt, dass man mit [mm] 2^3 [/mm] Bits nicht nr 6 sondern 8 Zeichen kodieren kann.
MfG
DAB268
|
|
| |
|
Hallo DAB268,
> Eine Informationsquelle sende sechs Zeichen A, B, C, D, E
> und F mit folgender Auftrittswahrscheinlichkeit aus: A 10%,
> B 5%, C 40%, D 20%, E 5%, F 20%. Dabei sei jedes
> Sendeereignis vom vorherigen unabhängig.
> (a) Berechnen Sie Entropie, relative Entropie und
> Redundanz dieser Informationsquelle (nutzen Sie dabei die
> Werte log2(10)=3,32 und log2(6)=2,58).
> (b) Kodieren Sie die Symbole nach der Methode von Fano (es
> gibt dabei mehrere Möglichkeiten, die gleichwertig sind).
> Berechnen Sie die zugehörige durchschnittliche Bitlänge pro
> Symbol.
> (c) Wieso bleibt die durchschnittliche Bitlänge aus (b)
> etwas über dem Idealwert der Entropie aus (a)?
> Hallo.
>
> Hier meine Lösungen. Bitte schaut mal ob diese korrekt
> sind:
>
> (a)
> H = [mm]-\bruch{1}{10} \cdot log_2 \bruch{1}{10}[/mm] -
> [mm]\bruch{1}{20} \cdot log_2 \bruch{1}{20}[/mm] - [mm]\bruch{2}{5} \cdot log_2 \bruch{2}{5}[/mm]
> - [mm]\bruch{2}{5} \cdot log_2 \bruch{2}{5}[/mm] - [mm]\bruch{1}{20} \cdot log_2 \bruch{1}{20}[/mm]
> - [mm]\bruch{2}{5} \cdot log_2 \bruch{2}{5}[/mm]
Es muss doch so lauten:
H = [mm]-\bruch{1}{10} \cdot log_2 \bruch{1}{10} -
\bruch{1}{20} \cdot log_2 \bruch{1}{20}- \bruch{2}{5} \cdot log_2 \bruch{2}{5} - \bruch{\red{1}}{5} \cdot log_2 \bruch{\red{1}}{5} - \bruch{1}{20} \cdot log_2 \bruch{1}{20} -
\bruch{\red{1}}{5} \cdot log_2 \bruch{\red{1}}{5}[/mm]
> H = [mm]\bruch{log_2 10}{10}[/mm]
> + [mm]\bruch{2 \cdot log_2 20}{20}[/mm] + [mm]\bruch{2 \cdot log_2 5}{5}[/mm]
> - [mm]\bruch{2}{5}[/mm] + [mm]\bruch{2 \cdot log_2 5}{5}[/mm]
> H = [mm]\bruch{10 \cdot log_2 10 + 10 \cdot log_2 20 + 80 \cdot log_2 5 - 40}{100}[/mm]
>
> H = [mm]\bruch{10 \cdot 3,32 +10 \cdot 4,32 + 80 \cdot 2,32 - 40}{100}[/mm]
>
> H= [mm]\bruch{33,2 + 43,2 + 185,6 -40}{100}[/mm]
> H=
> [mm]\bruch{222}{100}[/mm] = 2,22
Das Ergebnis stimmt. ![[ok]](/images/smileys/ok.gif "[ok]")
>
> [mm]H_{max}[/mm] = - 6 [mm]\cdot (\bruch{1}{6} \cdot log_2 \bruch{1}{6}[/mm]
> = - [mm]log_2 \bruch{1}{6}[/mm] = [mm]log_2[/mm] 6 = 2,58
>
> [mm]H_{rel}[/mm] = [mm]\bruch{H}{H_{max}}[/mm] = [mm]\bruch{2,22}{2,58}[/mm] = 0,86
>
> [mm]{Redundanz}=1-H_{rel}[/mm] = 1 - 0,86 = 0,14
Das ist doch die relative Redundanz.
Meines Wissens berechnet man die Redundanz einer Quelle als maximale Entropie vermindert um die Entropie der Nachrichtenquelle.
Siehe ![[]](/images/popup.gif) Redundanz - Informationstheorie
>
> (b)
> C 0
> D 10
> F 110
> A 1110
> B 11110
> E 11111
>
> [mm]DurchschnittlicheBitlaenge=\bruch{\bruch{2}{5}+2 \cdot\bruch{1}{5} + 3 \cdot \bruch{1}{5} + 4 \cdot \bruch{1}{10} + 5 \cdot \bruch{1}{20} +5 \cdot \bruch{1}{20}}{6}[/mm]
> = [mm]\bruch{\bruch{7}{5} + \bruch{4}{10} + \bruch{10}{20}}{6}= \bruch{\bruch{23}{10}}{6}[/mm]
> = [mm]\bruch{23}{60}[/mm] = 0,38
Das kommt mir etwas sonderbar vor, richtig muß es heißen:
[mm]\bruch{2}{5}+2 \cdot\bruch{1}{5} + 3 \cdot \bruch{1}{5} + 4 \cdot \bruch{1}{10} + 5 \cdot \bruch{1}{20} +5 \cdot \bruch{1}{20}=\bruch{23}{10}=2,3[/mm]
>
> c) Leider keine Lösung, aber ich hab mir schonmal gedacht,
> dass es evtl. daran liegt, dass man mit [mm]2^3[/mm] Bits nicht nr 6
> sondern 8 Zeichen kodieren kann.
>
> MfG
> DAB268
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Do 08.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
