Ist das Konzept von "Bit" in der Computerprogrammierung dem Konzept von "Bit" in der Informationstheorie ähnlich?

Bis heute wusste ich, dass ein Bit eine Variable oder ein Speicherplatz ist, der den Wert Eins (hoch) oder Null (niedrig) enthalten kann. Dies ist das Konzept, das ich durch das Studium von Computerprogrammierung, Mikroprozessor oder DATA-Bus usw. gelernt habe.

Aber nachdem ich den Kurs über Informationstheorie begonnen hatte, fand ich heraus, dass Bit als Informationsgehalt eines Symbols in einer Nachricht ausgedrückt wird. Dies wird unter Verwendung des Logarithmus (Basis 2) der Umkehrung der Wahrscheinlichkeit des Auftretens des Symbols berechnet.

Sind diese beiden Konzepte gleich? Ein Bit ist einerseits eine Variable, die entweder Null oder Eins speichern kann. Andererseits ist ein Bit die Unsicherheit, die mit einem von zwei Symbolen mit einer Eintrittswahrscheinlichkeit von 0,5 verbunden ist. Bedeutet 1 Bit in der Computerprogrammierung oder im ASCII-Code 1 Bit im Informationsgehalt der Quelle oder der Informationstheorie?

Eine kleine Änderung: Hier ist eine Sache, bei der ich Probleme habe, dieses Thema zu verstehen. Wenn wir bei der Datenübertragung von englischen Alphabeten ASCII-Code verwenden, stellen wir grundsätzlich jedes Symbol mit 8 Bits dar. Angenommen, das ist 00000000 für a, 00000001 für b usw. Wir weisen also im Wesentlichen 8 Quantisierungsstufen für jedes Symbol zu.

Wenn jedoch die Informationstheorie ins Spiel kommt, berücksichtigen wir die Wahrscheinlichkeit jedes Symbols. 'E' hat die höchste Frequenz, wobei 'Z' die niedrigste hat. Der durchschnittliche Informationsgehalt beträgt also 3 oder 4 Bit, oder?

In meinem Buch heißt es: "Entropie oder durchschnittlicher Informationsgehalt ist die minimale durchschnittliche Anzahl von Bits, die erforderlich sind, um jede Probe ohne Verzerrung darzustellen." Erstellen wir in diesem Fall für eine effiziente Datenübertragung maximal vier Quantisierungsstufen für jedes Symbol? Weil sie im Durchschnitt Informationen im Wert von 4 Bit enthalten. Wenn dem so ist, ist das Bit in der Informationstheorie nicht dasselbe wie das in der Computerprogrammierung, Datenübertragung oder im ASCII-Code usw.?

Sie bekommen wahrscheinlich, dass ich hier eindeutig ein Noob bin: p

information-theory Benjamin
quelle

Eine Sache, die zu MBaz 'Antwort hinzugefügt werden muss, ist, dass die Skalierung des "Bits" in der Informationstheorie so ist, dass es mit "Bits" im Computerspeicher identisch ist. Es gibt andere Informationseinheiten in Shannon IT. was auch immer multipliziert die Funktion. Wenn es , das die Protokollfunktion skaliert, dann ist in Bits.

I (m) = - C \log (P (m))

$I(m) = -C\log(P(m))$

C = \frac{1}{\log (2)}

$C= \frac{1}{\log(2)}$

I (m)

$I(m)$

Robert Bristow-Johnson

@ Robertbristow-Johnson, das ist ein guter Punkt.

MBaz

Die Huffman-Codierung versucht, die informationstheoretische Grenze zu erreichen, indem häufigen Symbolen weniger Bits zugewiesen werden. Dies ist ein ungefährer Prozess, da die wahren Frequenzen unbekannt sind und die Anzahl der Bits eine ganze Zahl bleiben muss. Die arithmetische Codierung ist besser und schafft es, unter Verwendung einer gebrochenen Anzahl von Bits pro Symbol zu packen.

Yves Daoust

Die Häufigkeit (z. B. von Zeichen, wenn es sich um eine Textdatei handelt) kann durch Zählen ermittelt werden. Auch verschiedene Symbole (mit einer gebrochenen Anzahl von Bits) können zu einer einzigen zusammengesetzten Nachricht zusammengefasst werden, die nahe an einer ganzzahligen Anzahl von Bits liegt. aber es wird immer weniger effizient sein als die theoretische Grenze.

Robert Bristow-Johnson

Antworten:

Sie sind nicht gleich, aber sie sind verwandt. Wenn Sie sich insbesondere einen Computerspeicher ansehen, der "Computer" -Bits enthält, wobei jedes Bit als zufällig und unabhängig von allen anderen Bits betrachtet werden kann und ungefähr 50% der Nullen vorhanden sind, enthält der Speicher auch ungefähr "Informationstheorie "Bits. $M$ $M$

Natürlich ist dies oft nicht der Fall: Computerbits sind normalerweise korreliert und nicht einheitlich zufällig. Deshalb können sie komprimiert werden. Kompressorprogramme wie LZW ("Quellcodierer" in der informationstheoretischen Sprache) arbeiten gewissermaßen so, dass jedes Computerbit ein Informationsbit enthält.

Bearbeitet, um hinzuzufügen: Dieses Beispiel kann die Unterscheidung klarer machen. Betrachten Sie eine speicherlose Quelle mit zwei Ausgängen, und , mit einer Wahrscheinlichkeit von jeweils 0,5. Es ist klar, dass die Informationen in jeder Nachricht ein (Informations-) Bit sind, aber ihre Länge beträgt drei (Computer-) Bits. Ein Quellcodierer wie der Huffman-Algorithmus codiert die Nachrichten leicht auf und , wodurch die komprimiert wird. Sie können dieses Beispiel leicht auf eine Quelle extrapolieren, die ASCII-codierten Text erzeugt. $m_1=000$ $m_2=001$ $c_1=0$ $c_2=1$

Beachten Sie, dass bei Schriftsprachen im Allgemeinen und Englisch im Besonderen niemand die tatsächliche Quellenentropie kennt, da es kein Modell dafür gibt. Aus diesem Grund gibt es Wettbewerbe für die beste Komprimierung großer Textkörper. Niemand ist sich wirklich sicher, was der optimale Komprimierungsalgorithmus für Englisch ist.

MBaz
quelle

Danke MBaz. Aber hier ist eine Sache, bei der ich Probleme habe, dieses Thema zu verstehen. Wenn wir bei der Datenübertragung von englischen Alphabeten ASCII-Code verwenden, stellen wir grundsätzlich jedes Symbol mit 8 Bits dar. Angenommen, das ist 00000000 für a, 00000001 für b usw. Wir weisen also im Wesentlichen 8 Quantisierungsstufen für jedes Symbol zu. Wenn jedoch die Informationstheorie ins Spiel kommt, berücksichtigen wir die Wahrscheinlichkeit jedes Symbols. 'E' hat die höchste Frequenz, wobei 'Z' die niedrigste hat. Der durchschnittliche Informationsgehalt beträgt also 3 oder 4 Bit, oder?

Benjamin

@benjamin, das ist richtig, und das ist der Grund, warum Text so stark komprimiert werden kann. Es enthält viel weniger Informationen als die Anzahl der (Computer-) Bits, die zur Darstellung verwendet werden.

MBaz

Hallo, ich habe den Kommentar im Antwortbereich ausführlich gepostet, da er zu lang wurde. Muss vergessen haben, es zu löschen. Übrigens bedeutet das im Grunde, dass Textsymbole Informationen im Wert von 3 bis 4 Bit enthalten, während wir 8 Bit verwenden, um sie zu übertragen, oder? Sie enthalten also nutzlose Bits oder Redundanz. Für eine effiziente Datenübertragung können wir sie also mit weniger Bits codieren und somit komprimieren. Das heißt, wir können kleinere Quantisierungsstufen erstellen, um sie zu codieren. Früher haben wir 8 Quantisierungsstufen erstellt, jetzt reichen 4 Quantisierungsstufen aus.

Benjamin

Ein Quantisierungspegel ist 1 binäres Ziffernbit. Jetzt können wir also geringere Quantisierungspegel oder weniger binäre Ziffernbits verwenden. Betrachten wir binäre Ziffernbits und Quantisierungsbits nicht als im Grunde dasselbe? Damals haben wir 8 Bits verwendet, um ein einzelnes Symbol zu übertragen. Aber jetzt wissen wir, dass die Symbole im Durchschnitt nur 4 Informationsbits wert sind. Wir senden sie also mit 4 Quantisierungspegeln oder 4 Binärziffernbits, da sie 4 Informationsbits enthalten. Tatsächlich habe ich versucht, selbst ein wenig über Hoffman-Codierung zu lernen, aber hier bin ich wirklich festgefahren.

Benjamin

@benjamin, ich denke du bist hier auf dem richtigen Weg. Stellen Sie sich das so vor: Wenn der Text (oder eine beliebige Computerdatei oder ein beliebiges Datum) perfekt komprimiert ist, enthält jedes darin enthaltene Computerbit ein Informationsbit.

MBaz

Bit ist eine Maßeinheit und mehrere Größen werden in Bits gemessen. Es ist nicht so, dass Programmierung und Informationstheorie unterschiedliche Bedeutungen haben. Es ist so, dass Speicher und Informationsgehalt konzeptionell unterschiedliche Größen darstellen.

Zum Beispiel können wir das Passwort '' 123456 '' nehmen. Wenn es in UTF-8 codiert ist, benötigt es 6 * 8 = 48 Bit Speicher. Für Zwecke der realen Welt beträgt der Informationsgehalt etwa 10 Bit. Bit bedeutet in beiden Fällen gleich, die gemessene Größe ist unterschiedlich. Wenn Sie das Kennwort komprimieren, verringert sich der Speicherbedarf, der Informationsgehalt ändert sich jedoch nicht.

Eine Analogie: Physikalische Größen wie Schwerkraft und elektromagnetische Kraft werden beide in Newton gemessen, repräsentieren jedoch unterschiedliche Arten von Wechselwirkungen. Sie können empirisch sehen, dass die Einheit Newton in beiden Fällen dieselbe Idee darstellt - Schwerkraft und elektromagnetische Kraft können sich gegenseitig ausgleichen (Magnetschwebebahn).

Ich hoffe das hilft :)

Martinkunev
quelle

Auf dem Datenbus können wir theoretisch besser abschneiden als es die Informationstheorie sagt. Ich weiß, wie man eine Schaltung baut, mit der ich 8 Bits parallel über 6 Drähte senden kann. Dies beinhaltet einen Trick mit Dioden und Pull-Up / Down-Widerständen, mit dem alle drei nicht brennenden Zustände eines digitalen Kabels zur Informationsübertragung verwendet werden können. Mit 3 Zuständen von 6 Leitungen erhalte ich 729 mögliche Zustände, wodurch ich EOF, INT, CLK übertragen und im Hauptkanal getrennt werden kann und immer noch viel Platz habe (dies verwendet nur 518 der 729 Zustände).

Joshua
quelle

Das definiert den Kanal nur neu und fügt Speicher hinzu;)

Bright-Star

Was Trevor gesagt hat. Sie gehen implizit davon aus, dass der "Informationstheoretiker" den Kanal nur einmal pro Symboldauer verwendet, um 1 Information von H oder L zu senden. Wenn Sie jedoch Zustände hinzufügen, tun Sie etwas, das nicht dasselbe ist :)

Marcus Müller