Wie funktioniert das Internet? Teil 2

In dieser Lektion/diesem Beitrag sprechen wir über Netzwerke.

Einführung in Bits, Signale und Pakete

Die Fähigkeit, Informationen über die Kommunikationsnetzwerke der Welt bereitzustellen und auszutauschen, hat die Art und Weise, wie Menschen arbeiten, spielen und leben, revolutioniert. Um die Jahrhundertwende listete die US-amerikanische National Academy of Engineering 20 Technologien mit den größten gesellschaftlichen Auswirkungen im 20. Jahrhundert auf. Diese Liste umfasste lebensverändernde Innovationen wie die Elektrifizierung, das Automobil und das Flugzeug. Dazu gehörten auch vier Kommunikationstechnologien – Radio und Fernsehen, Telefon, Internet und Computer –, deren technologische Grundlagen im Mittelpunkt dieses Buches stehen.

Überraschenderweise landete das Internet nur auf Platz 13, da es Ende des Jahrhunderts entwickelt wurde und das Komitee glaubte, dass seine größten Auswirkungen im 21. Jahrhundert eintreten würden. Diese Vorhersage scheint zutreffend: Die Verbreitung drahtloser Netzwerke und mobiler Geräte, der Aufstieg sozialer Netzwerke und die Kommunikation jederzeit und überall haben den Handel und die sozialen Verbindungen verändert und sogar gesellschaftliche und politische Veränderungen vorangetrieben.

Kommunikation ist für das moderne Leben von grundlegender Bedeutung. Ein Leben ohne das Internet, seine Anwendungen oder vernetzten Mobilgeräte ist kaum vorstellbar. Bis Anfang 2011 waren weltweit über 5 Milliarden Mobiltelefone aktiv, über eine Milliarde mit „Breitband“-Konnektivität – mehr als die Zahl der Menschen mit Strom, Schuhen, Zahnbürsten oder Toiletten im Jahr 2011!

Ziele

Dieser Beitrag/diese Lektion (wie auch immer Sie es nennen) soll erklären, wie Kommunikationsnetzwerke funktionieren. Es lohnt sich, dies aus zwei Gründen zu studieren:

• die Entwurfsprinzipien und Analysetechniken zu verstehen, die in diesen Systemen verwendet werden;
• weil die technischen Ideen für andere Bereiche der Informatik (CS) und Elektrotechnik (EE) relevant sind. Das macht das Studium von Kommunikationssystemen zu einer großartigen Möglichkeit, allgemein anwendbare Konzepte zu erlernen.

Am MIT (Massachusetts Institute of Technology) absolvieren Studenten im zweiten Studienjahr einen solchen Kurs mit etwas Erfahrung in Wahrscheinlichkeitstheorie und Fourier-Reihen.

Traditionell galt „Low-Level-Kommunikation“ (wie sich Informationen über eine einzelne Verbindung bewegen) als EE-Thema, während „Networking“ (Aufbau von Netzwerken aus mehreren Verbindungen) ein CS-Thema war. Herkömmliche digitale Kommunikationskurse befassen sich selten mit dem Aufbau von Netzwerken, und Computernetzwerkkurse behandeln die Kommunikation über physische Verbindungen als Blackbox. Dieses Buch soll diese Lücke schließen und ein umfassendes Verständnis beider Aspekte vermitteln.

Wir werden Kommunikationssysteme durchgängig abdecken: von der Quelle mit den zu übertragenden Informationen über Pakete (für die Übertragung aufgeschlüsselte Nachrichten) bis hin zu Bits („0“ oder „1“) und Signalen (analoge Wellenformen). über Verbindungen wie Kabel, Glasfaser, Funk oder akustische Wellen gesendet werden). Wir untersuchen verschiedene Netzwerke: einfache Punkt-zu-Punkt-Verbindungen, gemeinsam genutzte Medien mit mehreren Knoten und größere Multi-Hop-Netzwerke, die zu noch größeren Netzwerken verbunden sind.

Themen

Drei Herausforderungen sind für die digitale Kommunikation von zentraler Bedeutung: Zuverlässigkeit, Austausch und Skalierbarkeit. Dieser Einführungsabschnitt konzentriert sich auf die ersten beiden.

Zuverlässigkeit

Viele Faktoren machen die Kommunikation unzuverlässig. Wir werden Techniken zur Verbesserung der Zuverlässigkeit untersuchen, die alle Redundanz nutzen, um Zuverlässigkeit mit unzuverlässigen Komponenten zu erreichen, und sich dabei auf unabhängige Komponentenausfälle verlassen.

Die größte Herausforderung besteht darin, Rauschen, Interferenzen, Bitfehler und Paketverluste (durch nicht korrigierbare Fehler, Warteschlangenüberläufe oder Verbindungs-/Softwarefehler) zu überwinden, die alle die Kommunikationsqualität beeinträchtigen.

Neben Zuverlässigkeit ist auch Geschwindigkeit wichtig. Zuverlässigkeitstechniken nutzen häufig Redundanz, wodurch die Geschwindigkeit verringert wird. Viele Kommunikationssysteme vereinen Zuverlässigkeit und Geschwindigkeit.

Die Kommunikationsgeschwindigkeit ist dramatisch gestiegen, von Kilobit pro Sekunde in den frühen 1980er Jahren auf 100 Megabit pro Sekunde drahtlos und 1–10 Gigabit pro Sekunde über kabelgebundene Verbindungen heute.

Wir werden untersuchen, warum die Kommunikation unzuverlässig ist und wie man dagegen vorgehen kann, indem wir fehlerkorrigierende Codes verwenden, mit Intersymbolinterferenzen, Neuübertragungsprotokollen und fehlertolerantem Routing umgehen.

Effizientes Teilen

Dedizierte Links für jedes Knotenpaar sind unerschwinglich teuer. Teilen ist wichtig. Wir untersuchen das Teilen von Punkt-zu-Punkt-Links, geteilten Medien und Multi-Hop-Netzwerken.

Wir behandeln die gemeinsame Nutzung eines Mediums (relevant für Ethernet, WLAN, Mobilfunknetze und Satellitennetze), Modulation/Demodulation (Übertragung über verschiedene Frequenzen) und MAC-Protokolle (Medium Access Control) (Regeln für das Verhalten von Netzwerkknoten). . Wir werden Time-Sharing (jeder Knoten sendet für eine bestimmte Zeit) und Frequency-Sharing (Bandbreite aufteilen) untersuchen. Dann gehen wir zu Multi-Hop-Netzwerken über, in denen viele Kommunikationen Links teilen, die durch Switches orchestriert werden.

Zu den wichtigsten Fragen gehört, wie mehrere Kommunikationen das Netzwerk gemeinsam nutzen, wie Nachrichten das Netzwerk durchlaufen und wie eine zuverlässige Kommunikation über ein Multi-Hop-Netzwerk sichergestellt werden kann.

Sharing-Techniken und Zuverlässigkeitsmechanismen bestimmen die Netzwerkeffizienz. Effizienz kann als Minimierung der Kosten für bestimmte Anforderungen oder als Maximierung der „nützlichen Arbeit“ (Gesamtdurchsatz, Durchsatzschwankung und durchschnittliche Verzögerung/Latenz) für ein bestimmtes Netzwerk definiert werden. Dieser Beitrag konzentriert sich auf Durchsatz und Latenz.

Skalierbarkeit

Skalierbarkeit (Entwerfen von Netzwerken, die große Größen bewältigen) ist wichtig. Dieser Beitrag geht kurz darauf ein und überlässt eine ausführliche Diskussion den späteren Lektionen.

Gliederung und Plan

Die Lektion ist in vier Teile unterteilt: die Quelle und die Abstraktionen von Bits, Signalen und Paketen, die in dieser Reihenfolge untersucht werden.

1. Die Quelle: Wir beginnen mit den Grundlagen von Information, Entropie, Quellkodierung (Datenkomprimierung), Huffman-Codes und dem Lempel-Ziv-Welch-Algorithmus.
2. Bits: Wir gehen die Überwindung von Bitfehlern mit fehlerkorrigierenden Codes an: lineare Blockcodes und Faltungscodes.
3. Signale: Wir behandeln Modulation/Demodulation, Modellierung von Signalverzerrungen mit linearen zeitinvarianten (LTI) Kanälen, Zeit-/Frequenzbereichsdarstellungen und Frequenzgang von Kanälen/Filtern.
4. Pakete: Wir untersuchen die gemeinsame Nutzung von Medien mit MAC-Protokollen, Routing in Multi-Hop-Netzwerken und zuverlässige Datentransportprotokolle.

Information, Entropie und die Motivation für Quellcodes

Claude Shannons Informationstheorie (entwickelt Ende der 1940er Jahre) ist eine bahnbrechende Idee, die viele technologische Bereiche, insbesondere Kommunikationssysteme und Netzwerke, verändert hat. Dieses Kapitel stellt die Intuition hinter Informationen vor, definiert sie mathematisch und verknüpft sie mit der Entropie, einer Eigenschaft von Datenquellen.

Diese Konzepte ermöglichen eine effiziente Datenkomprimierung vor der Kommunikation oder Speicherung und ermöglichen so eine Wiederherstellung der Originaldaten ohne Verzerrung. Eine Kernidee ist die Quellcodierung, die jedes Symbol aus einer Datenquelle einem Codewort mit gewünschten Eigenschaften zuordnet. Eine Nachricht ist eine Folge von Symbolen. Unser Fokus liegt auf der verlustfreien Quellcodierung, bei der die ursprüngliche Nachricht aus einer unbeschädigten Übertragung perfekt wiederhergestellt werden kann.

Information und Entropie

Shannon erkannte, aufbauend auf Hartleys Arbeit, dass Informationen allgemein definiert werden können, unabhängig von der Anwendungs- oder Nachrichtensemantik. Bei der Kommunikation wählt ein Sender (S) eine von mehreren möglichen Nachrichten aus und sendet sie an einen Empfänger (R). Beispielsweise könnte S die britische Ankunftsroute angeben:

• „1“, wenn auf dem Landweg
• „2“ wenn auf dem Seeweg

Wenn jede Auswahl gleich wahrscheinlich ist (kein Vorwissen), beträgt die übermittelte Information 1 Bit. Dieses Bit kann die Auswahl kodieren. 1000 solcher unabhängigen Ereignisse können mit 1000 Bits kodiert werden.

Wenn Vorkenntnisse eine höhere Wahrscheinlichkeit für eine Wahl nahelegen (z. B. Land aufgrund eines Sturms), dann übermittelt die weniger wahrscheinliche Nachricht (Meer) mehr Informationen. Ebenso ist eine Temperatur von 75 °F in Boston im Januar aussagekräftiger als 32 °F.

Informationen über ein Ereignis hängen von seiner Wahrscheinlichkeit (p) ab. Eine geringere Wahrscheinlichkeit (weniger wahrscheinliches Ereignis) impliziert höhere Informationen.

Definition von Informationen

Hartley definierte Information (I) als:

I = log(1/p) = -log(p) (2.1)

Der Logarithmus zur Basis 2 wird verwendet und die Informationseinheit ist ein Bit. Die logarithmische Funktion sorgt für Additivität: Informationen aus zwei unabhängigen Ereignissen A und B (Wahrscheinlichkeiten pA und pB) addieren sich:

IA IB = log(1/pA) log(1/pB) = log(1/(pA*pB)) = log(1/P(A und B))

Beispiele

Entropie

Entropie (H) quantifiziert die erwarteten Informationen aus einer Reihe sich gegenseitig ausschließender Ereignisse. Wenn das Ereignis i die Wahrscheinlichkeit pi:

hat

H(p1, p2, ... pN) = Σ pi * log(1/pi) (2.2)

Entropie wird in Bits gemessen und stellt die durchschnittliche Unsicherheit dar. Für zwei sich gegenseitig ausschließende Ereignisse mit Wahrscheinlichkeiten p und 1-p:

H(p, 1-p) = -p*log(p) - (1-p)*log(1-p) (2.3)

H(p) ist symmetrisch um p = 1/2, mit einem Maximum von 1 Bit bei p = 1/2. H(0) = H(1) = 0. Entropie ist immer nicht negativ und H(p1, p2, ... pN) ≤ log N.

Quellcodes

Quellkodierung kodiert Nachrichten effizient. Viele Nachrichten verfügen über Standardkodierungen (ASCII, Bildpixel, Audiobeispiele). Dabei handelt es sich um Codierungen mit fester Länge, die leicht manipuliert werden können.

Diese Kodierungen können jedoch ineffizient sein. Im englischen Text kommt „e“ häufiger vor als „x“. Die Kodierung von „e“ mit weniger Bits und „x“ mit mehr Bits kann die durchschnittliche Nachrichtenlänge verkürzen. Dies steht im Einklang mit dem Informationskonzept: Häufige Symbole (höherer Pi) vermitteln weniger Informationen und benötigen weniger Bits.

Ein Code ordnet Informationen Bitsequenzen zu. Ein Codewort ist eine Bitfolge im Code. Quellcodes zielen darauf ab, Daten zu komprimieren, indem sie die Länge der codierten Nachricht an den Informationsinhalt (Entropie) anpassen.

Beispiel: Kodierung von 1000 Noten (A, B, C, D) mit Wahrscheinlichkeiten:

Kodierung fester Länge: 2 Bit/Grad (insgesamt 2000 Bit). Die Dekodierung ist einfach, aber ineffizient.

Codierung mit variabler Länge (Beispiel): A=10, B=0, C=110, D=111. Die Länge hängt von der Nachricht ab. Die Dekodierung erfordert eine sequentielle Verarbeitung. Dieser Beispielcode ist nicht optimal.

Wie viel Komprimierung ist möglich?

Idealerweise verwendet die Komprimierung nur die notwendigen Bits, um die Informationen darzustellen. Die Entropie (Gleichung 2.2) liefert die Untergrenze für die durchschnittliche Anzahl der Bits, die zur Vermeidung von Mehrdeutigkeiten erforderlich sind. Das Senden weniger Bits führt zu ungelösten Entscheidungen beim Empfänger.

Im Notenbeispiel beträgt die erwartete Information pro Note 1,626 Bit. Die Kodierung von 1000 Noten erfordert durchschnittlich 1626 Bit. Der Beispielcode mit variabler Länge verwendet 1667 Bit und ist daher nicht optimal. Die Kodierung von Notenfolgen kann die Komprimierung verbessern.

Gute Codes zu finden ist eine Herausforderung. Manchmal können kontextspezifische Codes sehr effizient sein (z. B. die Codierung von Shakespeare-Sonetten mit nur 8 Bit, wenn sowohl Sender als auch Empfänger alle Sonette kennen).

Warum Komprimierung?

Komprimierung bietet mehrere Vorteile:

• Schnellere Übertragung: Kürzere Nachrichten reduzieren die Übertragungszeit und geben Netzwerkkapazität frei.
• Effiziente Ressourcennutzung: Kleinere Nachrichten schonen Netzwerkressourcen (Bandbreite, Puffer) und ermöglichen mehr Kommunikation.
• Verbesserter Durchsatz über fehleranfällige Links: Die Komprimierung vor der Fehlerkorrekturcodierung ermöglicht eine optimierte Redundanz für Fehlerresistenz.

Komprimierung ist typischerweise eine End-to-End-Funktion (Anwendungsschicht), kann aber auch auf der Verbindungsschicht angewendet werden, wenn die Daten komprimierbar sind und Redundanz enthalten. Das nächste Kapitel befasst sich mit Huffman-Codes und der Lempel-Ziv-Welch (LZW)-Komprimierung.

Kompressionsalgorithmen: Huffman und Lempel-Ziv-Welch (LZW)

In diesem Kapitel werden zwei Quellcodierungsalgorithmen für die Nachrichtenkomprimierung erläutert (wobei eine Nachricht eine Folge von Symbolen ist): Huffman-Codierung und Lempel-Ziv-Welch (LZW). Die Huffman-Codierung ist effizient, wenn die Symbolwahrscheinlichkeiten bekannt und unabhängig sind. LZW ist adaptiv und erfordert keine Vorkenntnisse über Wahrscheinlichkeiten. Beide sind weit verbreitet (GIF, JPEG, MPEG, MP3 usw.).

Eigenschaften guter Quellcodes

Ein Code ordnet Symbole aus einem Alphabet (Text, Pixelintensitäten oder abstrakte Symbole) Codewörtern zu. Binäre Codewörter sind für viele Kommunikationskanäle praktisch.

Beispiel: Kodierung der Noten in 6.02: A=1, B=01, C=000, D=001. Eine Folge von Noten könnte als 0010001110100001 übertragen und als „DCAAABCB“ dekodiert werden.

Momentane Codes: Ein Symbol wird dekodiert, sobald sein Codewort empfangen wird. Die obige Notenkodierung erfolgt sofort. Nicht-augenblickliche Codes erfordern einen Blick nach vorne oder eine Dekodierung vom Ende aus, wodurch sie schwieriger zu dekodieren sind.

Codebäume und präfixfreie Codes: Ein Codebaum visualisiert Codes. In einem binären Codebaum werden Kanten mit 0 oder 1 gekennzeichnet. Der Pfad von der Wurzel zu einem Symbol gibt seine Kodierung an. Präfixfreie Codes haben Symbole nur an Blattknoten, um sicherzustellen, dass kein Codewort ein Präfix eines anderen ist. Präfixfreie Codes sind sofort verfügbar.

Erwartete Codelänge (L): Für N Symbole mit Wahrscheinlichkeiten pi und Codewortlängen li: L = Σ pi * li. Für die Komprimierung sind Codes mit kleinem L wünschenswert. Ein optimaler Code hat ein Minimum an L. Shannon zeigte, dass L ≥ H (Entropie) und es Codes gibt, die Entropie asymptotisch erreichen.

Huffman-Codes

Huffman-Codes bieten eine effiziente Kodierung gegebener Symbolwahrscheinlichkeiten. Wahrscheinlichere Symbole erhalten kürzere Codes.

Huffmans Algorithmus erstellt den Codebaum von unten nach oben, beginnend mit den am wenigsten wahrscheinlichen Symbolen:

1. Eingabe: Menge S von (Wahrscheinlichkeits-, Symbol-)Tupeln.
2. Kombinieren Sie die beiden am wenigsten wahrscheinlichen Symbole zu einem neuen Tupel (kombiniertes Symbol, Summe der Wahrscheinlichkeiten). Fügen Sie das neue Tupel zu S hinzu.
3. Wiederholen Sie Schritt 2, bis S nur noch ein Tupel (die Wurzel) hat.

Der resultierende Codebaum definiert den Code variabler Länge.

Eigenschaften von Huffman-Codes

• Nicht-Eindeutigkeit:Aufgrund willkürlicher Gleichstandsunterbrechungen während der Baumkonstruktion können mehrere optimale Codes (und Bäume) vorhanden sein.
• Optimalität: Huffman-Codes haben die minimale erwartete Länge unter den momentanen Codes für unabhängige Symbole, die aus einer festen, bekannten Wahrscheinlichkeitsverteilung gezogen werden.

LZW: Ein adaptiver Quellcode variabler Länge

Einfache Huffman-Codierung basierend auf Buchstabenwahrscheinlichkeiten weist Einschränkungen auf. Eine adaptive Kodierung, die sich an den Nachrichteninhalt anpasst, kann eine bessere Leistung erbringen. LZW ist ein beliebter adaptiver Algorithmus.

LZW erstellt eine String-Tabelle, die Symbolsequenzen auf/von N-Bit-Indizes abbildet. Die Tabelle (2^N Einträge) wird mit Einzelbyte-Sequenzen (0-255) initialisiert. Kodierung:

1. Akkumulieren Sie Bytes, während sich die Sequenz (S) in der Tabelle befindet.
2. Wenn S nächstes Byte (b) nicht in der Tabelle ist:
   • Übertragen Sie den Code für S.
   • S b zur Tabelle hinzufügen.
   • S auf b zurücksetzen.
3. Wiederholen, bis alle Bytes verarbeitet sind; Übertragen Sie dann den Code für das letzte S.

Der Decoder baut die Tabelle neu auf, wenn er Codes empfängt, sodass er die ursprüngliche Nachricht wiederherstellen kann.

LZW-Beobachtungen:

• Gierig: Findet die längsten Übereinstimmungen.
• Adaptiv: Tabelleneinträge spiegeln tatsächliche Nachrichtensequenzen wider.
• Suboptimal: Kann ungenutzte Einträge enthalten.
• Variable Komprimierung: Die Komprimierung nimmt zu, wenn die Tabelle gefüllt ist.
• Neuinitialisierung der Tabelle: Die Tabelle wird zurückgesetzt, wenn sie voll ist, und passt sich so an sich ändernde Wahrscheinlichkeiten an. Einige Varianten verwenden einen CLEAR-Code für explizite Zurücksetzungen.

Warum digital? Kommunikationsabstraktionen und digitale Signalisierung

In diesem Kapitel wird die analoge und digitale Kommunikation erläutert, wobei der Schwerpunkt auf den Problemen der analogen Kommunikation und den Gründen für die digitale Kommunikation liegt. Es stellt Methoden zum Senden und Empfangen digitaler Daten über analoge Kommunikationsverbindungen vor (notwendig, da physische Verbindungen auf der untersten Ebene grundsätzlich analog sind). Außerdem wird ein mehrschichtiges Kommunikationsmodell eingeführt: Nachrichten → Pakete → Bits → Signale, das die Grundlage für den Rest des Buches bildet.

Datenquellen

Kommunikationstechnologien ermöglichen Benutzern (Menschen oder Anwendungen) den Austausch von Nachrichten. Datenquellen können von Natur aus digital (z. B. computergenerierte Daten) oder analog (z. B. Video, Audio, Sensordaten) sein. Moderne Systeme digitalisieren häufig alle Daten, unabhängig von der Quelle.

Warum digital?

Digitale Kommunikation zeichnet sich aus zwei Gründen aus:

1. Modularität: Die digitale Abstraktion ermöglicht den Aufbau großer Systeme durch die Zusammenstellung von Modulen.
2. Ausgeklügelte Verarbeitung:Ermöglicht die Verwendung von Algorithmen zur Verbesserung der Datenqualität und Systemleistung.

Physische Verbindungen sind jedoch analog und erfordern Digital-Analog- und Analog-Digital-Konvertierungen.

Warum Analog in vielen Anwendungen selbstverständlich ist

Analoge Darstellungen lassen sich gut auf physische Linkeigenschaften übertragen. Beispiele:

• Schwarz-Weiß-Fernseher: Die Bildhelligkeit (Grauton) wird durch Spannungspegel dargestellt (0 V = Schwarz, 1 V = Weiß).

• Analoges Telefon:Schallwellen werden in elektrische Signale umgewandelt.

Analogsignale können mit unterschiedlichen Spannungs-/Intensitäts-/Wellenlängenpegeln gesendet werden, die vom Empfänger einfach gemessen werden können.

Warum also nicht analog?

Keine Kommunikationsverbindung ist fehlerfrei. Rauschen und Verzerrungen stören Signale und diese Fehler akkumulieren sich über mehrere Übertragungsstufen (Kaskadeneffekt). Dies erschwert den zuverlässigen Aufbau analoger Systeme, insbesondere komplexer Systeme. Die digitale Signalisierung löst dieses Problem.

Digitale Signalisierung: Zuordnung von Bits zu Signalen

Digitale Signalisierung verwendet diskrete Werte zur Darstellung von Bits und ermöglicht so eine robuste Unterscheidung vom Rauschen. Binäre Signalisierung verwendet zwei Spannungen: V0 für „0“ und V1 für „1“. V0 und V1 müssen ausreichend voneinander getrennt sein, um Rauschen verarbeiten zu können.

Der Empfänger verwendet eine Schwellenspannung (Vth = (V0 V1) / 2), um empfangene Spannungen auf Bits abzubilden (Spannung < Vth → „0“, Spannung ≥ Vth → „1“). Eine genaue Messung in der Nähe von Vth ist schwierig, aber nicht entscheidend, wenn V0 und V1 weit voneinander entfernt sind.

Signale in dieser Lektion

Übertragungssignale sind Wellenformen fester Spannung, die für eine bestimmte Zeit gehalten werden. Kontinuierliche Signale werden durch zeitdiskrete Abtastwerte dargestellt. Die Abtastrate (Samples pro Sekunde) wird zwischen Sender und Empfänger vereinbart. Probeintervall ist die Zeit zwischen den Proben.

Taktübertragungen

Sender und Empfänger müssen sich auf eine Taktrate einigen. Bits werden bei Taktübergängen gesendet. Samples_per_bit ist die Anzahl der Samples pro Bit. Der Empfänger leitet Taktflanken aus Übergängen in empfangenen Abtastwerten ab.

Herausforderungen:

1. Uhrsynchronisation:Die Uhren von Sender und Empfänger können unterschiedlich sein. Lösung: Adaptives Timing beim Empfänger basierend auf erkannten Übergängen.
2. Sicherstellung häufiger Übergänge: Wird für die Taktwiederherstellung benötigt. Lösung: Zeilenkodierung (z. B. 8b/10b).

Uhr- und Datenwiederherstellung

Die Uhr des Empfängers kann etwas schneller oder langsamer sein als die des Senders. Der Empfänger passt seinen Sampling-Index basierend auf Übergängen dynamisch an:

• Wenn die halbe Abtastung zwischen aktuellem und vorherigem Punkt gleich wie die aktuelle Abtastung ist (Abtastung zu spät): Erhöhen Sie den Index um Samples_per_Bit - 1.
• Wenn die Halbwertsprobe anders ist (Abtastung zu früh): Inkrementieren Sie um „Samples_per_bit 1“.
• Wenn kein Übergang: Erhöhen Sie um Samples_per_bit.

Die anfängliche Korrektur wird durch eine Trainingssequenz aus abwechselnden Nullen und Einsen zu Beginn der Übertragung unterstützt.

Leitungskodierung mit 8b/10b

8b/10b befasst sich mit Gleichstromgleichgewicht und häufigen Übergängen. Es ordnet 8-Bit-Symbole 10-Bit-Übertragungssymbolen zu und gewährleistet so Folgendes:

• Die maximale Anzahl von Nullen oder Einsen beträgt 5 Bit.
• Der maximale Unterschied zwischen der Einsen- und der Nullenanzahl bei jeder Stichprobe beträgt 6.
• Spezielle 7-Bit-Sequenzen ermöglichen die Erkennung von Paketgrenzen.

Kodierungsprozess:

1. Paketdaten werden in Bytes unterteilt.
2. Jedes Byte wird einem 10-Bit-Symbol zugeordnet.
3. Pakete werden mit einer Trainingssequenz und einem SYNC-Muster zur Synchronisierung umrahmt.

Kommunikationsabstraktionen

Ein Kommunikationssystem umfasst mehrere Module: Mapper (Bits zu Signalen), Demapper (Signale zu Bits), Kanalcodierung (Fehlerkorrektur), Kanaldecodierung. Nachrichten werden in Pakete aufgeteilt und über mehrere Verbindungen übertragen. Die drei wichtigsten Abstraktionen sind Pakete, Bits und Signale. Das Buch konzentriert sich auf diese und ihre Wechselwirkungen innerhalb des Kommunikationsnetzwerks.

Umgang mit Bitfehlern mithilfe von Fehlerkorrekturcodes

In diesem Kapitel werden Techniken für eine zuverlässige digitale Kommunikation erörtert, wobei der Schwerpunkt auf der Hinzufügung von Redundanz liegt, um unvermeidliche Bitfehler in Kommunikationskanälen und Speichermedien zu bekämpfen. Das Kernkonzept ist Kanalkodierung: Kodierung beim Sender und Dekodierung beim Empfänger, um Fehler zu korrigieren oder nicht korrigierbare Fehler zu erkennen. Das Kapitel konzentriert sich auf Fehler-Korrekturcodes, insbesondere lineare Blockcodes und (spätere) Faltungscodes.

Bitfehler und BSC

Das Binary Symmetric Channel (BSC)-Modell charakterisiert Bitfehler mit einem einzigen Parameter, ε (Bit-Flip-Wahrscheinlichkeit), wobei ein übertragenes Bit mit der Wahrscheinlichkeit ε umkippt, unabhängig von anderen Bits. ε kann empirisch geschätzt werden. Paketfehlerwahrscheinlichkeit (PER) für ein Paket der Größe S Bits:

PER = 1 - (1 - ε)^S (5.1)

Wenn ε << 1: PER ≈ Sε (5.2)

Reale Kanäle können Burst-Fehler aufweisen, wobei die Fehlerwahrscheinlichkeit vom Verlauf abhängt (höher, wenn auch die letzten Bits fehlerhaft waren).

Der einfachste Code: Wiederholung

Ein Wiederholungscode kodiert Bit b als n Kopien von b. Die Coderate beträgt 1/n. Maximum-Likelihood-Dekodierung wählt anhand des empfangenen Codeworts die wahrscheinlichste Nachricht aus. Für einen BSC bedeutet dies, das Codewort auszuwählen, das die meisten Bits mit dem empfangenen gemeinsam hat.

Dekodierfehlerwahrscheinlichkeit für Wiederholungscode (siehe Gleichung 5.3 im Originaltext). Die Wahrscheinlichkeit nimmt exponentiell mit der Coderate ab, ist aber aufgrund des hohen Overheads ineffizient.

Einbettungen und Hamming-Distanz

Hamming-Distanz (HD) zwischen zwei n-Bit-Wörtern ist die Anzahl der unterschiedlichen Bitpositionen. Für die Einzelfehlerkorrektur (SEC) muss HD zwischen zwei beliebigen gültigen Codewörtern mindestens 3 betragen. Ein Code mit der minimalen Hamming-Distanz D kann D-1-Fehler erkennen und Floor(D/2 -1) Fehler.

Lineare Blockcodes und Paritätsberechnungen

Lineare Blockcodes (n, k) ordnen k-Bit-Nachrichten n-Bit-Codewörtern zu, indem lineare Funktionen (gewichtete Summen) über Nachrichtenbits verwendet werden. Algebraische Blockcodes führen solche Operationen innerhalb des Blocks aus. (n,k,d)-Codes bezeichnen Blockcodes mit einem minimalen Hamming-Abstand „d“. Coderate = k/n.

Lineare Codes erfordern, dass die Summe zweier beliebiger Codewörter ebenfalls ein Codewort ist. Das aus Nullen bestehende Codewort existiert in jedem linearen Code. Der minimale Hamming-Abstand eines linearen Blockcodes entspricht dem Gewicht des kleinsten Codeworts ungleich Null (Anzahl der Einsen). Binäre lineare Codes verwenden Modulo-2-Arithmetik (Galois-Feld F2).

SEC-Code mit rechteckiger Parität

Parität ist die Modulo-2-Summe der Bits. Gerader Paritätscode fügt jeder Nachricht ein Paritätsbit hinzu, wodurch das Codewort eine gerade Parität aufweist. Dadurch werden einzelne Fehler erkannt (HD=2).

Der rechteckige Paritätscode ordnet k Bits in einem r x c-Array an und fügt Zeilen- und Spaltenparitäten hinzu. Codewort: Nachrichtenzeilenparitäten, Spaltenparitäten. Länge: n = rc r c. Dieser Code ist ein SEC-Code (HD=3). Beim Dekodieren werden die Zeilen- und Spaltenparitäten überprüft und das entsprechende Bit korrigiert, wenn beide Paritäten einen Fehler anzeigen.

Wie viele Paritätsbits werden in einem SEC-Code benötigt?

Jeder lineare Code kann in einen systematischen Code (Nachrichtenbits gefolgt von Paritätsbits) umgewandelt werden. Für SEC muss die Anzahl der Paritätskombinationen (2^(n-k)) größer oder gleich der Anzahl korrigierbarer Situationen (n 1) sein:

n 1 ≤ 2^(n-k) (5.6)

Die Anzahl der Paritätsbits wächst mindestens logarithmisch mit den Nachrichtenbits.

Hamming-Codes

Hamming-Codes sind effiziente SEC-Codes mit logarithmischem Paritätsbitwachstum. Jedes Paritätsbit schützt mehrere Datenbits und einzelne Fehler erzeugen einzigartige Paritätsfehlerkombinationen.

Syndrombits (Ei) werden beim Empfänger durch Überprüfen der Paritäten berechnet. Die Kombination der Syndrombits gibt das fehlerhafte Bit an (falls vorhanden).

Gibt es eine Logik in der Konstruktion des Hamming-Codes?

Hamming-Code-Konstruktion:

1. Paritätsbits Indizes zuweisen, die Potenzen von 2 sind (1, 2, 4, 8,...).
2. Datenbits den verbleibenden Indizes zuweisen.
3. Datenbit di wird genau dann in die Paritätsberechnung für pj einbezogen, wenn index(pj) zu index(di) in binärer Darstellung (bitweises UND ist ungleich Null).

Die als Binärzahl behandelten Syndrombits (E3E2E1 im (7,4)-Beispiel) geben den Index des zu korrigierenden Bits an.

Hinweis: Dies sind nur die Informationen, die man für die Webentwicklung benötigt. Für Sysops sind die Netzwerke und ihre Grundlagen ein zweisemestriger Kurs.

Das obige ist der detaillierte Inhalt vonWie funktioniert das Internet? Teil 2. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!