Informationsmenge berechnen - Frage zu "Bitfehlern"

[jk86]

Moin,

in der Berufsschule machen wir gerade die Berechnung von Informationsmengen. Als Beispiel dazu mussten wir die Informationsmenge eines sechsseitigen Würfels berechnen.

Die Wahrscheinlichkeit für den Wurf einer bestimmten Zahl ist 1/6. Also ist die Informationsmenge = log (6) / log (2) = 2,585. So weit, so klar.

Dass man das Ereignis "Zahl n gewürfelt" mit 3 Bit codiert, weil 3! = 6 mögliche Ergebnisse sind die gewürfelt werden können, ist auch klar. Dass Redundanz entsteht, auch (2³ Bits minus 3! Bits = 2 Bits Redundanz).

Allerdings ist mir nicht klar, welche Bits redundant sind.

Die Augenzahlen des Würfels codieren wir mit Augenzahl = (dezimal) 1 = (binär) 001 und (dezimal) 6 = (binär) 110. Da die binären und dezimalen Zahlen übereinstimmen, macht das ja auch Sinn, obwohl es an sich ja egal sein müsste, wie die Würfelergebnisse codiert werden (die Menge der Möglichkeiten bleibt ja gleich).

Und nun das Rätsel: Der Lehrer meinte, die Bits 000 und 111 müssten redundant sein, weil diese Zahlenfolgen am ehesten beim Datentransport zu Fehlern neigen und dann falsch interpretiert würden. Das kapiere ich nun überhaupt nicht - die Gefahr besteht doch bei jedem Bit?

Was hat es damit auf sich? Kann es mir jemand erklären?

[Klotzkopp]

Vermutlich will er darauf hinaus, dass 000 und 111 keine Flankenwechsel enthalten.

[Crash2001]

Wieso die redundant sein müssen, verstehe ich allerdings auch nicht - vor allem, da sie ja nicht einmal genutzt werden, da die 1 (dez) der 001 (bin) entspricht und die 6 (dez) der 110 (bin).

@Klotzkopp:
Hängt das nicht von der Übertragungsart ab, ob Flankenwechsel stattfinden? Es kann ja durchaus auch nach jedem Bit ein "Rücksetzbit" übertragen werden, so dass z.B. die 1 einem Pegel von xV entspricht und die 0 einem negativen Pegel von xV, aber nach jedem übertragenen Bit der Pegel wieder auf 0 zurückgesetzt wird.
Ist was doof zu erklären, aber ich hoffe, du verstehst, was ich meine.
 

[Klotzkopp]

vor 31 Minuten schrieb Crash2001:

Hängt das nicht von der Übertragungsart ab, ob Flankenwechsel stattfinden?

Natürlich. Jedes real existierende Datenübertragungssystem wird auf der physikalischen Schicht eine Codierung vornehmen, die Flankenwechsel auch dann erzeugt, wenn die Nutzdaten nur aus Dauer-0 (oder Dauer-1) bestehen.

Aber wenn die hier beschriebene Codierung schon der Leitungscode sein soll, wenn man die so codierten Daten irgendwie "direkt" auf einen Draht geben würde, wäre das eine mögliche Überlegung des Lehrers. Wie gesagt, nur eine Vermutung meinerseits.

 

[mqr]

Hallo Community,

jetzt wird das aber sehr theoretisch. Unabhängig vom Übertragungsverfahren, was ja hier nicht gegeben ist, ist das mit den theoretischen Fehlinterpretationen ja dieses was den "Schnitt" für eine Bitkombination nach unten zieht. Man darf bei Übertragungen jedoch nicht den Taktgeber vergessen, der ja vorgibt wann das Signal einen neuen Zustand erreicht hat. Sonst wären die Fehler riesig, abhängig von Länge, Impedanz, Kapazität und ähnlichem. Außerdem müsste man eine Folge von "100" und "001" genauso wie "011" und "110" erst recht vermeiden. Früher war so etwas, ich denke das nennt man Latenzzeit (Begriff aus dem Arbeitsspeicher), noch eher wichtig . Ein Transistor brauchte länger zum sperren, je länger er durchgeschaltet war. Solche Feinheiten das ein Steuerkondensator nach theoretischen 5tau geladen war aber eben erst zu, was weis ich, 98%. Wenn also der Einschaltvorgang noch einmal 5tau dauerte, hat der Kondensator schon eine Ladung von, was weis ich, 99,8% erreicht. Dementsprechend war die Dauer bis zum erreichen des Sperrzustand länger. Dann kam es auf die Justierung des Taktsignals an. Eine Weile geht es gut aber hin und wieder wird ein Soll-"low" noch als "high" interpretiert und das nur bei z.B. >50 Grad Celsius Schaltschranktemperatur. Äquivalent die anderen Fehler.

Übertragungungsverfahren mit Flankenwechsel oder gar mit erzwungener Polaritäsänderung sind halt langsamer.

vor 22 Stunden schrieb jk86:

...weil 3! = 6 mögliche Ergebnisse

das verstehe ich aber nicht. Hängt das von den zwei möglichen Richtungen der drei Würfelachsen ab? Wie wäre das bei einem 20 seitigem Würfel? 10 Achslagen mit jeweils zwei Richtungen ---> 10*2*1=20 Ergebnisse?

Grüße

Micha

[jk86]

vor 2 Stunden schrieb mqr:

das verstehe ich aber nicht. Hängt das von den zwei möglichen Richtungen der drei Würfelachsen ab? Wie wäre das bei einem 20 seitigem Würfel? 10 Achslagen mit jeweils zwei Richtungen ---> 10*2*1=20 Ergebnisse?

Für 20 verschiedene Zahlen würden ja 2^5 =32 Bit ausreichen, oder mit weniger Redundanz: 4! = 24 Bit.

Ich meine, die Fakultät würde mit der Anzahl der möglichen Permutationen zusammenhängen. Darauf kommt es ja an, wenn man die einzelnen Bytes aus Nullen und Einsen zusammenbastelt zur Codierung der Würfelergebnisse. Der Matheunterricht ist bei mir aber schon 10 Jahre her... kann sein, dass da ein Denkfehler meinerseits drinsteckt. Ne Leuchte drin war ich auch nicht gerade...

20-seitiger Würfel -> Bist du Rollenspieler?

[mqr]

Hallo jk86,

vor einer Stunde schrieb jk86:

20-seitiger Würfel -> Bist du Rollenspieler?

ist bestimmt zwanzig Jahre oder länger her, da war es das "schwarze Auge" (zwanzig seitiger Würfel) und im Studium "Rolle, Rollentheorie, Psychodrama", hat aber nichts mit dem Würfel zu tun. Meine Mathematik aus dem Elektrotechnikstudium auch.

Es ging mir in erster Line um die Begründung für die 3!, das ist dann die Anzahl der Möglichkeiten, die eine dreistellige Binärzahl unterscheiden kann. Ich dachte zunächst, das es sechs Würfelergebnisse sind, weil 3!=6 ist (siehe Zitatausschnitt). Da habe ich das wohl nicht richtig gelesen .

Was der Lehrer da sagte, ist ja, dass dann zwei Kombinationen nicht gebraucht (notwendig) sind und am ehesten entscheidet man sich dann für Kombinationen, die vielleicht Probleme machen. Wenn man in einem anderen Zusammenhang (der zu Missverständnissen führen könnte), den Code 101 als Zwangsabschaltung definiert, bei Spagetticode oder sonstwas, könnte man den hier ausschließen. Irgendwelche zwei Zahlen müssen raus und irgendwie muss eine Begründung her.

Die Fakultät ist in erster Linie eine Rechenoperation, wie das Summatra(∑). Hier werden ganzzahlig alle Zahlen bis eins hinunter multipliziert. Bsp. 5!=5*4*3*2*1 und ∑5=5+4+3+2+1

Für Zwanzig komme ich auf 5 bit, dass entspräche 32 Kombinationen.

31₁₀=>1 1111₂    20₁₀=>1 0100₂

Grüße

Micha

 

Bearbeitet 9. Dezember 2016 von mqr
Binärrechnung???

[jk86]

vor 5 Stunden schrieb mqr:

Für Zwanzig komme ich auf 5 bit, dass entspräche 32 Kombinationen.

31₁₀=>1 1111₂    20₁₀=>1 0100₂

Jo sehe ich auch so:

Wahrscheinlichkeit W für eine bestimmte Zahl beim 20-seitigen Würfel: 1/20

I = log (Kehrwert von W) / log (2) = log (20) / log (2) = 4,322 -> aufgerundet 5 Bit

Mit der Fakultät scheint ein Denkfehler zu sein. Zur Darstellung einer Zahl größer als 15 braucht man 5 Binärstellen. Macht Sinn.

Wobei es ja nur 5 Zahlen sind, die 5 Binärstellen zur Codierung brauchen. Da frage ich mich: kann man nicht auch 4 Bit nehmen und für jede fünfte Zahl (oder die Zahlen 16-19, wenn wir 20 als 0 (bin) codieren) 5 Bit? Macht zusammen 60 Bit (vierstellig) + 20 Bit (fünfstellig) = 80 Bit insgesamt (statt 100 Bit, wenn alle Zahlen fünfstellig codiert sind). Wobei sich das sicher noch weiter reduzieren ließe, wenn 0 (dez) nicht 0000 (bin), sondern 0 (bin), 2 (dez) nicht 0010 (bin), sondern 10 (bin), usw.

Das macht bei einem 20-seitigen Würfel vielleicht keinen Sinn, weil man zur Unterscheidung der Zahlencodes Stopp-Bits einbauen müsste, die die Wortlänge künstlich aufblähen. Aber wenn wir einen sehr breiten Zahlenbereich haben, z.B. 2^0 bis 2^64,  macht das ja schon was aus?

Oder muss die, äh - keine Ahnung wie das heißt, ich übertrage es mal aus der Programmierung: Wortlänge - immer gleich lang sein, damit der Computer auch weiß, wo welcher Zahlencode anfängt?

Bsp. 1111 (bin) = 01111 (bin) = 15 (dez), 10000 (bin) = 16, aber 111110000 (bin) = 496 (dez)

-> wenn der Computer nicht weiß, ob er nun nach dem vierten oder dem fünften Bit trennen soll und deshalb einfach weiterliest, könnte der Code verfälscht werden, und weil eine Codierung mit gleicher Wortlänge redundanz- und fehlerfreier ist als eine komprimierte Variante mit Stopp-Bits,  (zumindest in niedrigeren Zahlenbereichen), macht man's eben so?

 

Sorry für die dummen Fragen... ich hoffe ihr könnt mir noch irgendwie folgen

[mqr]

Hallo jk86,

vor 19 Stunden schrieb jk86:

Oder muss die, (...) Wortlänge - immer gleich lang sein, damit der Computer auch weiß, wo welcher Zahlencode anfängt?

Das nicht unbedingt, es hängt natürlich alles vom Übertragungsprotokoll ab. Eigentlich beantwortest Du Dir ja Deine Frage selbst in dem Beispiel. Ich weis jetzt auch nicht wie Du Dir das mit einem Stoppbit vorstellst, da ein Bit nun einmal nur "0" oder "1" ist. Dann könntest Du nur aufeinanderfolgende Nullen oder Einsen "zählen". Es würde erst bei relativ langen Daten zur Zeiteispararung führen. Rein theoretisch, mir fällt kein Grund ein so ein Protokoll zu Entwickeln, könntest Du Dir Deinen Standart selbst definieren. Für Inhouse, bei Superechnern, zum Passwort knacken und das dann Protokoll "abc v X.Y" nennen.

Aber rein theoretisch, es müßte dann ein Stoppcode definiert sein, der die möglichen Übertragungen nicht zu sehr einschränkt. Als Folgebeispiel zu Deinem Ansatz:

vor 19 Stunden schrieb jk86:

Bsp. 1111 (bin) = 01111 (bin) = 15 (dez), 10000 (bin) = 16, aber 111110000 (bin) = 496 (dez)

Man definiert "01" als Stoppcode, dann könnte man schon beliebig viel Kombinationen aus Einsen gefolgt von Nullen übertragen:

"10", "110", "100", "11110000" jedoch nicht "101111", "011111", "1111001000", da zwischen drin ja das definierte Datenende enthalten ist. Es macht also nur Sinn, wenn der Stoppcode einige Zeichen lang ist damit nicht zu viele Brauchdaten ausgeschlossen werden müssen. Somit nur bei sehr, sehr vielstelligen Daten.

Man könnte hier jetzt jedoch ausrechnen ab wann das ganze Zeiteinsparungen oder Einsparungen in der übertragenen Datenmenge bringt. Nur im öffendlichen Netz kann man nicht an den Protokollen basteln, obwohl dort auch nur Deine Daten in ein "zusätzliches" Protokoll gepackt werden, dass es egal wird ob ein Paket von Dir 60 Minuten oder 60,5 Minuten braucht. Allerdings ist es ein guter Ansatz zur persönlichen Verschlüsselung.

Zwei weitere Ansätze wären, Zugriff auf das Übertragungssystem vorausgesetzt: Den Taktgeber ein Bit aussetzen zu lassen, eine weitere Ader zur Datentrennung, jedoch würde man schnell von serieller zur paralleler Datenübertragung greifen oder die Polarität ändern (Wobei das wiederum auch schon an drei mögliche Zustände grenzt und somit andere Wege besser geeignet wären).

Wie gesagt nur theoretisch, es macht halt nur in Sonderfällen Sinn.

Grüße

Micha