Theorema Magnum MCMIL: das WKS–Abtasttheorem

Von Thilo / 22. Oktober 2020 / 7 Kommentare / Seite 2 von 2 / Auf einer Seite lesen

Shannons Arbeit legte die theoretischen Grundlagen der Kodierungstheorie, in der es darum geht, durch möglichst effizientes Einfügen von Redundanzen eine Absicherung gegen auftretende Fehler zu erreichen.
Für handhabbare Algorithmen verwendet man Codes, die algebraische Strukturen verwenden wie zum Beispiel Vektorräume über endlichen Körpern. Ebenfalls noch 1949 wurden die ersten solchen Codes gefunden: die Golay-Codes und die Hamming-Codes.

Bild: https://informatik.rostfrank.de/info/lex06/shannon.html

« Vorherige Seite

Seite 1 / 2

Kommentare (7)

#1 hwied
28. Oktober 2020

Wenn ich das richtig verstehe, dann ist das Abtasttheorem für analog-digital-Wandler nützlich.
#2 Frank Wappler
30. Oktober 2020

Thilo schrieb (22. Oktober 2020):
> […] wollte Shannon eine von den Wahrscheinlichkeiten $p_i$ der einzelnen Ereignisse abhängende „Entropie“ $H[ \, p_1, \ldots, p_n \, ]$ definieren, die drei Bedingungen genügen sollte. Sie soll stetig von den $p_i$ abhängen. Für Gleichverteilungen $p_i = 1/n$ soll sie eine monoton wachsende Funktion in $n$ sein. Und sie soll eine Additivitätsbedingung erfüllen: wenn eine Möglichkeit mit Wahrscheinlichkeit $p_i$ in zwei Möglichkeiten zerlegt werden kann, dann soll das ursprüngliche $H$ die gewichtete Summe der beiden einzelnen $H$ sein.

Gemeint ist womöglich die Additivitätsbedingung:

$H[ \, p_1, \ldots, p_k, \ldots, p_n \, ] =$
$H[ \, \sum[ \, p_1, \ldots, p_k \, ], \sum[ \, p_{(k + 1)}, \ldots, p_n \, ] \, ] +$
$(\sum[ \, p_1, \ldots, p_k \, ]) \, H[ \, (p_1 / \sum[ \, p_1, \ldots, p_k \, ]), \ldots, (p_k / \sum[ \, p_1, \ldots, p_k \, ]) \, ] +$
$(\sum[ \, p_{k + 1}, \ldots, p_n \, ]) \, H[ \, (p_{k + 1} / \sum[ \, p_{k + 1}, \ldots, p_k \, ]), \ldots, (p_n / \sum[ \, p_{k + 1}, \ldots, p_n \, ]) \, ],$

wobei der erste Term der Summe offenbar nicht zur “gewichteten Summe der beiden einzelnen $H$ “ gehört.

> Im Beispiel

… entsprechend dem im obigen ScienceBlog-Artikel gezeigte und verlinkte Bild https://i2.wp.com/scienceblogs.de/mathlog/files/2020/08/12931861-232D-4BDC-9B81-A126E12CF15B.png?ssl=1 …

> soll $H[ \, 1/2, 1/3, 1/6 \, ] = H[ \, 1/2, 1/2 \, ] + (1/2) \, H[ \, 1/3, 2/3 \, ]$ sein, wobei der Faktor $(1/2)$ der Wahrscheinlichkeit des zweiten Prozesses entspricht.

In Anwendung der oben vorgeschlagenen Additivitätsbedingung auf dieses Beispiel, d.h. mit Identifikation der Einzelwahrscheinlichkeiten $p_1, p_2, p_3$ “von unten nach oben” mit $k = 2$ ist tatsächlich

$H[ \, 1/6, 1/3, 1/2 \, ] =$

$H[ \, (1/6 + 1/3), 1/2 \, ] +$
$(1/6 + 1/3) \, H[ \, ((1/6) / (1/6 + 1/3)), ((1/3) / (1/6 + 1/3)) \, ] +$
$(1/2) \, H[ \, ((1/2) / (1/2)) \, ] =$

$H[ \, 1/2, 1/2 \, ] + (1/2) H[ \, ((1/6) / (1/2)), ((1/3) / (1/2)) \, ] + (1/2) \, H[ \, 1 \, ] =$

$H[ \, 1/2, 1/2 \, ] + (1/2) H[ \, 1/3, 2/3 \, ] + 0.$

> Shannon bewies in seiner Arbeit, dass die (bis auf Multiplikation mit einem konstanten Faktor) einzige Funktion mit diesen Eigenschaften
> $H[ \, p_1, \ldots, p_n \, ] = -\Sigma_{i=1}^n[ \, p_i \text{Log}[ \, p_i \, ] \, ]$ ist, […]

Reichen die drei oben angegebenen Bedingungen aus, um zu garantieren, dass die gesuchte „Entropie“-Funktion $H$ symmetrisch in all ihren Argumenten ist (sofern das mehr als nur ein einziges Argument ist),
d.h. dass $H[ \, \ldots, p_j, \ldots, p_q, \ldots \, ] = H[ \, \ldots, p_q, \ldots, p_j, \ldots \, ]$ für alle Indexpaare $(j, q)$ ?
Oder wäre das eine ausdrücklich zusätzliche, vierte Bedingung an $H$ ?
#3 Frank Wappler
30. Oktober 2020

p.s. — ScienceBlogs-Kommentar-HTML-Test:

“Wahrscheinlichkeiten p<sub>i</sub>” wird dargestellt als “Wahnscheinlichkeiten pi”.
#4 Thilo
30. Oktober 2020

Ich denke, dass die Symmetrie nicht vorausgesetzte werden muss. Einen Beweis der Eindeutigkeit findet man z.B. in https://en.wikipedia.org/wiki/Entropy_(information_theory)#Characterization
#5 Frank Wappler
30. Oktober 2020

Thilo schrieb (30. Oktober 2020):
> Einen Beweis der Eindeutigkeit findet man z.B. in https://en.wikipedia.org/wiki/Entropy_(information_theory)#Characterization

Die dort gezeigte Additivitätsbedingung (ausgedrückt unter Verwendung der obigen Symbolik), $H[ \, p_1, p_2 \, ] = H[ \, p_1 \, ] \, + \, H[ \, p_2 \, ]$ , ist allerdings offenbar keine gewichtete Summe, die im obigen ScienceBlog erwähnt wurde.

> Ich denke, dass die Symmetrie nicht vorausgesetzte werden muss.

Mit der Wikipedia-Additivitätsbedingung, oder zumindest ihrer Verallgemeinerung zu

$H[ \, p_1, p_2, \ldots, p_n \, ] = H[ \, p_1 \, ] \, + \, H[ \, p_2 \, ] \ldots + H[ \, p_n \, ]$ ,

wäre allerdings die Symmetrie von $H$ direkt durch die Symmetrie des “ $+$ “-Operators (für reelle Zahlen) gegeben, die ihrerseits zweifellos vorausgesetzt werden kann und muss.
#6 Thilo
24. Dezember 2020

https://www.quantamagazine.org/how-claude-shannons-information-theory-invented-the-future-20201222/
#7 Theorema Magnum – Mathlog
19. Februar 2022

[…] Die Leray-Spektralsequenz Konditionierung linearer Gleichungssysteme Das Simplex-Verfahren Das WKS-Abtasttheorem Adelische Poisson-Summation Der Vergleichssatz von Rauch Die Berechnung des Kobordismusrings Die […]