互聯網如何運作？第2部分

在本課/貼文中，我們將討論網路。

位元、訊號和封包簡介

透過全球通訊網路傳遞和交換資訊的能力徹底改變了人們的工作、娛樂和生活方式。世紀之交，美國國家工程院列出了20世紀最具社會影響力的20項技術。該清單包括改變生活的創新，如電氣化、汽車和飛機。它還包括四種通訊技術——廣播和電視、電話、網路和電腦——其技術基礎是本書的重點。

令人驚訝的是，網路僅排名第 13，因為它是在本世紀末發展的，委員會認為其最重大的影響將出現在 21 世紀。這項預測似乎很準確：無線網路和行動裝置的普及、社交網路的興起以及隨時隨地的通訊已經改變了商業、社會聯繫，甚至推動了社會和政治變革。

溝通是現代生活的基礎。很難想像沒有網路、網路應用程式或連網行動裝置的生活。到 2011 年初，全球活躍手機數量超過 50 億部，其中超過 10 億部擁有「寬頻」連線——超過 2011 年擁有電力、鞋子、牙刷或廁所的人數！

目標

這篇文章/課程（無論你怎麼稱呼它）旨在解釋通訊網路是如何運作的。這值得研究，原因有二：

• 了解這些系統中所使用的設計原理和分析技術；
• 因為技術思想與電腦科學（CS）和電機工程（EE）的其他領域相關。這使得學習通訊系統成為學習廣泛適用概念的好方法。

在麻省理工學院（麻省理工學院），二年級學生會學習這樣的課程，接觸一些機率和傅立葉級數。

傳統上，「低階通訊」（資訊如何在單一連結上移動）被認為是 EE 主題，而「網路」（建立多個連結的網路）一直是 CS 主題。傳統的數位通訊課程很少涉及網路建設，而電腦網路課程將實體鏈路上的通訊視為黑盒子。本書旨在彌合這一差距，提供對這兩方面的全面理解。

我們將端到端地介紹通訊系統：從要傳輸的資訊來源，到資料包（分解傳輸的訊息），到位（「0」或「1」），到訊號（模擬波形）透過電線、光纖、無線電或聲波等連結發送）。我們將研究不同的網路：簡單的點對點連結、具有多個節點的共享媒體以及連接形成更大網路的更大的多跳網路。

主題

數位通訊面臨三個核心挑戰：可靠性、共享和可擴展性。本介紹部分重點介紹前兩個。

可靠性

許多因素導致溝通不可靠。我們將研究提高可靠性的技術，所有這些技術都採用冗餘來實現不可靠組件的可靠性，並依賴獨立組件故障。

主要挑戰是克服雜訊、幹擾、位元錯誤、資料包遺失（來自不可糾正的錯誤、佇列溢位或連結/軟體故障），所有這些都會降低通訊品質。

除了可靠性之外，速度也很重要。可靠性技術經常使用冗餘，從而降低速度。許多通訊系統平衡可靠性和速度。

通訊速度顯著提高，從 20 世紀 80 年代初的每秒千位元到如今的無線每秒 100 兆位元和有線鏈路每秒 1-10 千兆位元。

我們將探討為什麼通訊不可靠以及如何解決它，使用糾錯碼、處理符號間幹擾、重傳協定和容錯路由。

高效共享

每個節點對的專用連結都非常昂貴。分享是必不可少的。我們將研究共享點對點連結、共享媒體和多跳網路。

我們將介紹共享介質（與乙太網路、WiFi、蜂窩網路和衛星網路相關）、調變/解調（透過不同頻率傳輸）和介質存取控制 (MAC) 協定（管理網路節點行為的規則） 。我們將探討時間共享（每個節點在專用時間內進行傳輸）和頻率共享（分割頻寬）。然後我們將轉向多跳網絡，其中許多通信共享鏈接，由交換機協調。

關鍵問題包括多個通訊如何共享網路、訊息如何穿越網路以及如何確保跨多跳網路的可靠通訊。

共享技術和可靠性機制決定網路效率。效率可以定義為最小化給定要求的成本或最大化給定網路的「有用工作」（聚合吞吐量、吞吐量變化和平均延遲/等待時間）。這篇文章重點討論吞吐量和延遲。

可擴展性

可擴充性（設計處理大尺寸的網路）很重要。這篇文章簡要介紹了它，為後面的課程留下詳細討論。

摘要與計劃

本課程分為四個部分：原始碼以及位元、訊號和資料包的抽象，依序學習。

1. 來源：我們從資訊、熵、來源編碼（資料壓縮）、霍夫曼編碼和 Lempel-Ziv-Welch 演算法的基礎知識開始。
2. 位元：我們透過糾錯碼來克服位元錯誤：線性分組碼和卷積碼。
3. 訊號：我們涵蓋調變/解調、使用線性時不變 (LTI) 通道建模訊號失真、時域/頻域表示以及通道/濾波器的頻率響應。
4. 封包：我們研究 MAC 協定的媒體共享、多跳網路中的路由以及可靠的資料傳輸協定。

資訊、熵和原始碼的動機

克勞德·香農 (Claude Shannon) 的資訊理論（發展於 20 世紀 40 年代末）是一個開創性的思想，它改變了許多技術領域，特別是通訊系統和網路。本章介紹訊息背後的直覺，以數學方式定義訊息，並將其與熵（資料來源的屬性）連結起來。

這些概念可以在通訊或儲存之前實現高效的資料壓縮，從而可以在不失真的情況下恢復原始資料。 核心思想是來源編碼，它將資料來源中的每個符號對應到具有所需屬性的代碼字。訊息是符號序列。我們的重點是無損源編碼，可以從未損壞的傳輸中完美恢復原始訊息。

資訊與熵

香農在哈特利工作的基礎上，意識到訊息可以被普遍定義，獨立於應用程式或訊息語義。通訊涉及發送者 (S) 選擇幾種可能的訊息之一並將其發送給接收者 (R)。例如，S可以表示英國到達路線：

• 若陸路則為「1」
• 如果是海運則為「2」

如果每個選擇的可能性相同（沒有先驗知識），則傳達的訊息為 1 位元。該位可以對選擇進行編碼。 1000 個這樣的獨立事件可以用 1000 位元進行編碼。

如果先驗知識顯示一種選擇的機率較高（例如，由於風暴而選擇陸地），那麼可能性較小的訊息（海洋）會傳達更多訊息。 同樣，波士頓 1 月 75°F 的氣溫比 32°F 的氣溫更能提供資訊。

有關事件的資訊取決於其機率 (p)。較低的機率（不太可能發生的事件）意味著較高的資訊。

資訊的定義

Hartley 將資訊 (I) 定義為：

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

採用以2為底的對數，訊息單位為位元。 對數函數確保可加性：來自兩個獨立事件A和B（機率pA和pB）的資訊相加：

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

範例

熵

熵 (H) 量化一組互斥事件的預期資訊。如果事件 i 的機率為 pi:

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

熵以位元為單位測量，代表平均不確定性。對於機率為 p 和 1-p 的兩個互斥事件：

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

H(p) 在 p = 1/2 附近對稱，在 p = 1/2 時最多 1 位。 H(0) = H(1) = 0。熵總是非負且 H(p1, p2, ... pN) ≤ log N。

原始碼

來源編碼有效地對訊息進行編碼。 許多訊息都有標準編碼（ASCII、圖像像素、音訊樣本）。這些是固定長度的編碼，易於操作。

但是，這些編碼可能效率低。 在英文文本中，「e」出現比「x」更頻繁。用更少的比特對“e”進行編碼，用更多的比特對“x”進行編碼可以縮短平均訊息長度。 這與資訊概念一致：頻繁的符號（pi 較高）傳達的訊息較少，所需的位數也較少。

代碼將資訊映射到位序列。 碼字是程式碼中的一個位元序列。 原始碼旨在透過將編碼訊息長度與資訊內容（熵）相匹配來壓縮資料。

範例：用機率編碼 1000 個等級（A、B、C、D）：

定長編碼：2位/級（共2000位）。 解碼簡單，但效率低。

可變長度編碼（範例）：A=10、B=0、C=110、D=111。 長度取決於訊息。 解碼需要順序處理。 此範例程式碼不是最佳的。

可以壓縮多少？

理想情況下，壓縮僅使用必要的位元來表示資訊。熵（公式 2.2）提供了避免歧義所需的平均位數的下限。發送較少的位元會導致接收器無法解決選擇。

在成績範例中，每個成績的預期資訊為 1.626 位元。 編碼 1000 個等級平均需要 1626 位元。範例可變長度程式碼使用 1667 位，因此它不是最佳的。 對等級序列進行編碼可以提高壓縮率。

尋找好的程式碼是具有挑戰性的。有時，特定於上下文的代碼可能非常有效率（例如，如果發送者和接收者都知道所有十四行詩，則僅使用 8 位元對莎士比亞十四行詩進行編碼）。

為什麼要壓縮？

壓縮有幾個優點：

• 更快的傳輸：較短的訊息可以減少傳輸時間並釋放網路容量。
• 高效率的資源利用：較小的訊息可以節省網路資源（頻寬、緩衝區），容納更多的通訊。
• 提高了易錯連結的吞吐量：糾錯編碼之前的壓縮可以實現錯誤復原的最佳化冗餘。

壓縮通常是端對端功能（應用層），但如果資料可壓縮且包含冗餘，也可以應用於連結層。 下一章將介紹霍夫曼程式碼和 Lempel-Ziv-Welch (LZW) 壓縮。

壓縮演算法：Huffman 和 Lempel-Ziv-Welch (LZW)

本章討論兩種用於訊息壓縮的來源編碼演算法（其中訊息是符號序列）：Huffman 編碼和 Lempel-Ziv-Welch (LZW)。當符號機率已知且獨立時，霍夫曼編碼是有效的。 LZW 是自適應的，不需要先驗機率知識。 兩者都被廣泛使用（GIF、JPEG、MPEG、MP3 等）。

良好原始碼的屬性

代碼將字母表中的符號（文字、像素強度或抽象符號）對應代碼字。 二進位碼字對於許多通訊管道來說都很方便。

範例：6.02 中的編碼等級：A=1、B=01、C=000、D=001。一系列等級可以傳輸為 0010001110100001，解碼為“DCAAABCB”。

瞬時代碼：一旦收到符號的代碼字，就會對其進行解碼。 上面的等級編碼是瞬時的。非瞬時代碼需要向前查看或從末尾解碼，這使得它們更難解碼。

程式碼樹與無前綴碼：程式碼樹視覺化程式碼。 在二元碼樹中，邊用 0 或 1 標記。從根到符號的路徑給出了它的編碼。 無前綴代碼僅在葉節點處有符號，確保沒有代碼字是另一個代碼字的前綴。無前綴代碼是即時的。

預期碼長度(L): 對於具有機率pi 的N 符號與碼字長度li：L = Σ pi *李。 L 較小的程式碼適合壓縮。 最優程式碼具有最小L。香農證明L ≥ H（熵），漸近實現熵的代碼存在。

霍夫曼碼

霍夫曼編碼在給定符號機率的情況下提供高效率的編碼。 更有可能的符號會得到更短的代碼。

霍夫曼演算法自下而上建構程式碼樹，從最不可能的符號開始：

1. 輸入：設定（機率，符號）元組的 S。
2. 將兩個機率最小的符號組合成一個新的元組（組合符號，機率總和）。將新元組加入 S.
3. 重複步驟 2，直到 S 只有一個元組（根）。

產生的程式碼樹定義了可變長度程式碼。

霍夫曼代碼的性質

• 非唯一性：由於樹建造過程中的任意平局，可能存在多個最佳程式碼（和樹）。
• 最優性：對於從固定的已知機率分佈中提取的獨立符號，霍夫曼代碼在瞬時代碼中具有最小的預期長度。

LZW：自適應可變長度原始碼

基於字母機率的簡單霍夫曼編碼有其限制。 根據訊息內容進行調整的自適應編碼可以表現得更好。 LZW 是一種流行的自適應演算法。

LZW 建立一個字串表，將符號序列對應到 N 位元索引或從

N

位元索引映射符號序列。此表（2^N 個條目）使用單字節序列 (0-255) 進行初始化。 編碼：
2. 當序列（S）在表中時累積位元組。
   • 當S下一個位元組(b)不在表中：
   • 傳送 S 代碼。
   • 將 S b 加入表中。
   將 S 重設為 b。

重複直到處理完所有位元組；然後傳送最後一個 S 的程式碼。

解碼器在接收程式碼時重建表，使其能夠恢復原始訊息。

LZW 觀察結果：
貪婪：
• 找出最長的匹配。
自適應：
• 表格條目反映實際的訊息序列。
次優：
• 可能包含未使用的條目。
可變壓縮：
• 壓縮隨著表格填充而增加。
表格重新初始化：

表滿後會重置，以適應不斷變化的機率。 某些變體使用 CLEAR 代碼進行明確重置。

為什麼選擇數位化？通訊抽象和數位訊號

本章解釋了模擬和數位通信，重點關注模擬的問題和數字的基本原理。它提出了透過類比通訊鏈路發送和接收數位資料的方法（這是必要的，因為實體鏈路在最低層級上基本上是類比的）。它也介紹了分層通訊模型：訊息→封包→位元→訊號，這構成了本書其餘部分的基礎。

數據來源

通訊技術使用戶（人類或應用程式）能夠交換訊息。 資料來源本質上可以是數位的（例如電腦產生的資料）或模擬的（例如視訊、音訊、感測器資料）。 現代系統通常會將所有數據數位化，無論其來源為何。

為什麼選擇數位化？

數位通訊的優異表現有兩個原因：
模組化：
2. 數位抽象可以透過組合模組來建構大型系統。
複雜的處理：

它允許使用演算法來提高資料品質和系統效能。

然而，物理鏈路是模擬的，需要數模和模數轉換。

為什麼模擬在許多應用中很自然

模擬表示很好地對應到物理鏈路屬性。例：

• 黑白電視：
影像亮度（灰色陰影）以電壓電平表示（0V = 黑色，1V = 白色）。

• 類比電話：
聲波轉換為電訊號。

類比訊號可以以不同的電壓/強度/波長等級發送，很容易被接收器測量。

那為什麼不採用模擬呢？

沒有任何通訊連結是沒有錯誤的。雜訊和失真會擾亂訊號，而這些錯誤會在多個傳輸階段累積（級聯效應）。這使得模擬系統難以可靠地構建，尤其是複雜的系統。數位訊號解決了這個問題。

數位訊號：將位元映射到訊號 數位訊號使用離散值來表示位，從而能夠與雜訊進行強有力的區分。

二進位訊號

使用兩個電壓：V0 代表“0”，V1 代表“1”。 V0 和 V1 必須充分分離以處理雜訊。

接收器使用閾值電壓（Vth = (V0 V1) / 2）將接收到的電壓對應到位（電壓

本課中的信號

傳輸訊號是保持特定時間的固定電壓波形。 連續訊號由離散時間樣本表示。 取樣率（每秒取樣數）由發送者和接收者商定。 取樣間隔是取樣之間的時間。

時鐘傳輸

發送方和接收方必須就時脈速率達成協議。位在時脈轉換時發送。 Samples_per_bit 是每個位元的樣本數。接收器從接收到的樣本中的轉換推斷時脈邊緣。

挑戰：

1. 時鐘同步：發送器和接收器時鐘可能不同。 解決方案：接收器根據偵測到的轉換進行自適應定時。
2. 確保頻繁轉換：時脈恢復所需。解：線路編碼（例如8b/10b）。

時鐘和資料恢復

接收方時鐘可能比發送方時鐘稍快或稍慢。 接收器根據轉換動態調整其取樣索引：

• 如果當前點和前一個點之間的中間樣本與當前樣本相同（採樣太晚）：將索引增加samples_per_bit - 1。
• 如果中途樣本不同（取樣太早）：增加samples_per_bit 1。
• 如果沒有轉換：增加samples_per_bit。

傳輸開始時交替的 0 和 1 訓練序列有助於初步校正。

8b/10b 線路編碼

8b/10b 解決 DC 平衡和頻繁轉換問題。它將 8 位元符號對應到 10 位元傳輸符號，確保：

• 0 或 1 的最大運行長度為 5 位元。
• 任何樣本中 1 和 0 計數之間的最大差異為 6。
• 特殊的 7 位元序列可實現封包邊界偵測。

編碼過程：

1. 封包資料分為位元組。
2. 每個位元組映射到一個 10 位元符號。
3. 資料包由訓練序列和用於同步的 SYNC 模式構成。

通訊抽象

一個通訊系統涉及幾個模組：Mapper（位元到訊號）、Demapper（訊號到位元）、Channel Coding（糾正錯誤）、Channel Decoding。訊息被分成資料包並透過多個鏈路傳輸。 三個關鍵抽像是封包、位元和訊號。 本書重點在於這些內容以及它們在通訊網路中的互動。

使用糾錯碼應對位錯誤

本章討論可靠數位通訊的技術，重點是添加冗餘以應對通訊通道和儲存媒體中不可避免的位元錯誤。 核心概念是通道編碼：在發送方編碼並在接收方解碼以糾正錯誤或檢測不可糾正的錯誤。 本章重點在於錯誤校正程式碼，特別是線性區塊程式碼和（後來的）卷積程式碼。

位元錯誤和 BSC

二元對稱通道 (BSC) 模型使用單一參數 ε（位元翻轉機率）來表徵位元錯誤，其中傳輸的位元以機率 ε 翻轉，獨立於其他位元。 ε 可以憑經驗估計。 大小為 S 位元的封包的封包錯誤機率 (PER)：

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

當 ε

現實世界的通道可能會出現突發錯誤，其中錯誤機率取決於歷史記錄（如果最近的位也出錯，則錯誤機率更高）。

最簡單的程式碼：重複

A 重複程式碼 將位元 b 編碼為 n 個 b 副本。 碼率為1/n。 最大似然解碼 根據收到的碼字選擇最有可能的訊息。對於 BSC，這意味著選擇與接收到的碼字具有最多共同位元的碼字。

重複碼的解碼錯誤機率（見原文公式5.3）。機率隨著碼率呈指數下降，但因開銷較高而效率低。

嵌入和漢明距離

兩個 n 位元字之間的漢明距離 (HD) 是不同位元位置的數量。對於單一糾錯 (SEC)，任何兩個有效碼字之間的 HD 必須至少為 3。具有最小漢明距離 D 的程式碼可以偵測 D-1 錯誤並修正底層（D/2 -1) 錯誤。

線性分組碼與奇偶校驗計算

線性區塊碼 (n, k) 使用訊息位上的線性函數（加權和）將 k 位元訊息對應到 n 位元碼字。 代數塊程式碼在區塊內執行此類操作。 (n,k,d)碼表示具有最小漢明距離「d」的分組碼。碼率 = k/n。

線性碼要求任兩個碼字和也是一個碼字。 全零碼字存在於任何線性碼中。線性分組碼的最小漢明距離等於最小非零碼字的權重（1的數量）。 二元線性程式碼使用模2算術（伽羅瓦域F2）。

矩形奇偶校驗 SEC 程式碼

奇偶校驗 是位的模 2 和。 偶校驗碼為每個訊息添加一個奇偶校驗位，使碼字具有偶校驗。這會偵測到單一錯誤 (HD=2)。

矩形奇偶校驗碼將 k 位元排列到 r x c 陣列中，並新增行和列奇偶校驗。碼字：訊息行奇偶校驗列奇偶校驗。長度：n = rc r c。代碼是 SEC 代碼 (HD=3)。 解碼涉及檢查行和列奇偶校驗，如果兩個奇偶校驗都指示錯誤，則修正對應的位元。

SEC 代碼需要多少個奇偶校驗位元？

任何線性代碼都可以轉換為系統代碼（訊息位後面跟著奇偶校驗位）。對於 SEC，奇偶校驗組合的數量 (2^(n-k)) 必須大於或等於可修正情況的數量 (n 1)：

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

奇偶校驗位計數至少隨訊息位元呈對數成長。

漢明碼

漢明碼是具有對數奇偶校驗位成長的高效能 SEC 代碼。 每個奇偶校驗位保護多個資料位，單一錯誤會產生獨特的奇偶校驗錯誤組合。

校正子位元 (Ei) 在接收器處以檢查奇偶校驗來計算。綜合症位的組合表示錯誤位元（如果有）。

漢明碼的構造有邏輯嗎？

漢明碼構造：

1. 將奇偶校驗位分配給 2 的冪（1、2、4、8、...）的索引。
2. 將資料位元指派給剩餘索引。
3. 資料位元di包含在pj的奇偶校驗計算中當且僅當索引(pj)有助於索引(di ) 以二進位表示形式（以位元AND 非零）。

作為二進制數處理的校正子位元（(7,4) 範例中的 E3E2E1）給出了要修正的位元的索引。

注意：這只是 Web 開發所需的資訊。對 Sysops 來說，網路及其基礎知識是兩個學期的課程。

以上是互聯網如何運作？第2部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！