Fehlerkorrekturcodes und Hamming-Distanz

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Welche der folgenden Aussagen beschreibt Forward Error Correction?

Fehler werden vor der Übertragung vollständig ausgeschlossen.

Fehler werden während der Übertragung erkannt und korrigiert. (correct)

Fehler werden nach der Übertragung korrigiert.

Die Übertragung erfolgt ohne jegliche Fehlererkennung.

Was ist die Hamming-Distanz?

Die Rate, mit der Fehler während einer Übertragung erkannt werden.

Die maximale Anzahl von Fehlern, die in einem Codeblock auftreten können.

Die Anzahl der Differenzen zwischen zwei binären Codes. (correct)

Die Länge des kürzesten Codes zur Fehlerkorrektur.

Welcher Faktor beeinflusst den Durchsatz eines binären symmetrischen Kanals?

Der Grad der Redundanz im Signal.

Die Anzahl der Übertragungsarten.

Die Länge des verwendeten Codes.

Die Frame-Länge des übertragenden Signals. (correct)

Innert welchem Konzept wird die Kanalkapazität eines BSC bestimmt?

Durch die Entropie des Informationssignals. Signup and view all the answers

Wie wird die Coderate R eines binären Block-Codes definiert?

Als Verhältnis der Anzahl der Nutzdatenbits zur Gesamtanzahl der Bits. Signup and view all the answers

Was definiert einen perfekten Code?

Jedes empfangene Wort hat genau ein Codewort mit minimaler Hamming-Distanz. Signup and view all the answers

Wie wird das Hamming-Gewicht eines Codeworts bestimmt?

Durch die Anzahl der Einsen im Codewort. Signup and view all the answers

Wie berechnet man die Hamming-Distanz zwischen zwei Codewörtern?

Durch bitweise XOR-Operation der beiden Codewörter und anschließendem Bestimmen des Hamming-Gewichts des Ergebnisses. Signup and view all the answers

Wie ist die Anzahl der erkennbaren Fehler e in Bezug auf die Hamming-Distanz dmin definiert?

e = dmin - 1. Signup and view all the answers

Was beschreibt ein (N,K)-Blockcode in der Codierung?

Das Verhältnis der Informationen zu den Codeworten. Signup and view all the answers

Was ist die maximale Entropie einer Binary Memoryless Source (BMS)?

1.0 Signup and view all the answers

Welcher Ausdruck beschreibt die Kapazität eines fehlerfreien Binary Symmetric Channel (BSC)?

$C_{BSC} = 1 - H(p)$ Signup and view all the answers

Wie ist die Ausgangswahrscheinlichkeit $P_y$ im BSC definiert?

$P_y = P_x(1 - ε) + P_x(ε)$ Signup and view all the answers

Was passiert mit der Kanalkapazität des fehlerfreien BSC, wenn $p$ gleich 0.5 ist?

Die Kapazität erreicht ihr Maximum von 1 Signup and view all the answers

Was ist der Hauptfaktor für die Entropie einer Störquelle im Kontext eines BSC?

Die Wahrscheinlichkeit der Fehler Signup and view all the answers

Was ist ein Nachteil der Backward Error Correction?

Ein Rückkanal ist erforderlich. Signup and view all the answers

Welche Methode gehört zur Forward Error Correction?

Minimum-Distance-Decoding Signup and view all the answers

In welchem Fall ist Backward Error Correction nicht anwendbar?

Einmalige Ereignisse Signup and view all the answers

Welche Technik nutzt Forward Error Correction zur Fehlerkorrektur?

Blockcodes Signup and view all the answers

Was beschreibt das Kanalcodierungstheorem?

Die Möglichkeit, die Fehlerwahrscheinlichkeit beliebig zu reduzieren. Signup and view all the answers

Was ist eine typische Methode der Backward Error Correction?

Blockcodes Signup and view all the answers

Was ist der Wert von $P(y_0)$ im gegebenen Beispiel?

0.0590 Signup and view all the answers

Was ist ein Charakteristikum der Forward Error Correction?

Sie nutzt von der Kanalcodierung hinzugefügte Redundanz. Signup and view all the answers

Was passiert, wenn bei der Backward Error Correction ein Fehler auftritt?

Der Sender wartet auf eine Quittung. Signup and view all the answers

Wie wird $P(y_#)$ berechnet?

$P(x#) imes (1 - ext{𝜖}) + P(x_0) imes ext{𝜖}$ Signup and view all the answers

Was ist die Entropie, wenn $P(x_0) = 0.05$ und $P(y_3) = 0.5$?

0.75 Signup and view all the answers

Welcher der folgenden Werte entspricht $P(x#)$, wenn $P(x_0) = 0.05$?

0.95 Signup and view all the answers

Welche Aussage über die Summierung der Wahrscheinlichkeiten ist korrekt?

Die Summe der Wahrscheinlichkeiten muss 1 ergeben. Signup and view all the answers

Study Notes

Perfekter Code

Ein Code heisst ein "perfekter Code", wenn jedes empfangene Wort genau ein Codewort hat, zu dem es eine geringste Hamming-Distanz hat und dem es eindeutig zugeordnet werden kann.

Hamming-Gewicht

Das Hamming-Gewicht gibt an, wieviele Einsen das Codewort enthält.
Beispiel: 𝑤𝐻(000) = 0 und 𝑤𝐻(110) = 𝑤𝐻(011) = 𝑤𝐻(101) = 2
Das Hamming-Gewicht darf nicht mit der Hamming-Distanz verwechselt werden.

Hamming-Distanz

Die Hamming-Distanz zweier Codewörter wird mit einer bitweisen XOR-Operation berechnet, die die Differenz der beiden Codewörter bestimmt.
Das Hamming-Gewicht der Differenz der Codewörter entspricht der Hamming-Distanz.
Beispiel: 𝑑6 000, 110 = 𝑤6 000 ⨁ 110 = 𝑤6 110 = 2

Anzahl der Erkennbaren Fehler

Die Anzahl der erkennbaren Fehler e bei einer gegebenen Hamming-Distanz 𝒅𝒎𝒊𝒏 ist e = (dmin – 1).

Forward- und Backward Error Correction

Forward Error Correction (FEC) erlaubt es, Fehler am Empfänger zu korrigieren.
Backward Error Correction (BEC) erlaubt es, Fehler zu erkennen und eine Neuübertragung der Daten anzufordern.
Beispiele für FEC: Blockcodes, Minimum-Distance-Decoding und Faltungscodes.
Beispiele für BEC: Blockcodes und CRC.

Kanalmodell und Bitfehlerwahrscheinlichkeit

Das Kanalmodell beschreibt die Bedingungen, unter denen Daten übertragen werden.
Die Bitfehlerwahrscheinlichkeit (BER) gibt die Wahrscheinlichkeit an, dass ein Bit fehlerhaft übertragen wird.

Entropie und Kanalkapazität

Die Entropie einer Quelle gibt die durchschnittliche Informationsmenge pro Symbol an.
Die Kanalkapazität gibt die maximale Datenrate an, die über einen Kanal fehlerfrei übertragen werden kann.

Hamming-Distanz und Fehlererkennung

Die Hamming-Distanz eines Codes bestimmt die Anzahl der erkennbaren Fehler.
Je höher die Hamming-Distanz, desto mehr Fehler können erkannt werden.

Binäre Blockcodes

Blockcodes sind eine Art von Codes, die Daten in Blöcken übertragen.
Die Coderate R eines Blockcodes gibt das Verhältnis von Nutzdatenbits zu Codebits an.
Die Systematik eines Blockcodes beschreibt die Anordnung der Daten und der Redundanzbits.

Linearität und Zyklizität

Lineare Codes erfüllen die Eigenschaften der Vektoraddition und -multiplikation.
Zyklische Codes haben die Eigenschaft, dass eine zyklische Verschiebung des Codeworts erneut ein gültiges Codewort erzeugt.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Testen Sie Ihr Wissen über perfekt Codes, Hamming-Gewicht und Hamming-Distanz. Erfahren Sie, wie diese Konzepte in der Fehlerkorrektur zusammenwirken und welche Rolle sie bei der Erkennung von Fehlern spielen. Dieses Quiz ist ideal für Studierende der Informatik und Mathematik.