序列程式設計/錯誤糾正方法
序列程式設計: 介紹和 OSI 網路模型 -- RS-232 佈線和連線 -- 典型的 RS232 硬體配置 -- 8250 UART -- DOS -- MAX232 驅動器/接收器系列 -- Windows 中的 TAPI 通訊 -- Linux 和 Unix -- Java -- Hayes 相容調變解調器和 AT 命令 -- 通用序列匯流排 (USB) -- 形成資料包 -- 錯誤糾正方法 -- 雙向通訊 -- 資料包恢復方法 -- 序列資料網路 -- 實際應用開發 -- 序列連線上的 IP
主要有三種處理錯誤的方式
- 確認或重試 (ACK-NAK)。
- "前向糾錯" (FEC)
- 假裝從未發生
每個資料包都會由接收器檢查，以確保它是“有效的”。
如果它*是*有效的，接收器（最終）會告訴傳送器它已成功接收 - 它會確認（ACK）資料包。
所有版本的 ACK-NAK 絕對需要 雙向通訊。
傳送器會計算整個資料包的校驗和或 CRC（除了頁尾），然後將其附加到資料包的末尾（在頁尾/尾部）。
典型的 CRC 是 32 位，通常是 Fletcher-32 校驗和。
旁註：請注意，校驗和或 CRC 是雜湊的形式，即不可逆地縮減資料。校驗和和 CRC 比“加密強度高”的訊息認證程式碼演算法（如 MD5 或 SHA 變體）弱。加密強度高的演算法可以比校驗和或 CRC 更好地檢測錯誤，但它們計算起來需要更多時間。
每當接收器收到資料包時，接收器都會計算完全相同的校驗和或 CRC，然後將其與頁尾/尾部中的校驗和或 CRC 進行比較。如果匹配，整個資料包（幾乎可以肯定）是有效的，因此接收器會發送 ACK。
當對資料包有任何錯誤（可能是*實際資料*或*標頭*或*校驗和位*中的錯誤 - 接收器無法判斷）存在哪怕一絲疑問時，接收器會完全丟棄它，並且（在大多數情況下）假裝從未看到它。
如果它不是有效的，傳送器 會再次傳送它。
它沒有收到 ACK。（因此資料包要麼被破壞，要麼 ACK 被破壞 - 傳送器無法判斷）。
ACK-NAK 的最簡單版本是“停等 ARQ”。
傳送器傳送一個數據包，然後等待一會兒以接收 ACK。一旦它收到 ACK，它就會立即傳送下一個資料包。如果傳送器沒有及時收到 ACK，它會從頭開始，再次傳送相同的資料包，直到收到 ACK。
接收器會等待資料包。如果資料包完全通過了所有錯誤檢測測試，接收器會向傳送器傳輸 ACK（確認）。
細微之處：如果接收器完美地接收了資料包，但 ACK 訊息延遲太長，則傳送器會發送訊息的另一個副本（“通訊回聲”）。想象一下，資料包包含訊息“從弗雷德的賬戶中扣除 11,000 美元”。當接收器收到此訊息的第二個副本時，它應該怎麼做？當然，它應該傳送 ACK（否則傳送器將不斷嘗試傳送此訊息）。以下問題中的一個或兩個都可能發生
- 延遲的第一個 ACK 可能會在傳送器傳輸訊息的第二個副本後到達傳送器，因此它會傳輸下一個資料包。然後，第二個 ACK 命中傳送器，欺騙傳送器認為“下一個資料包”已成功接收，而實際上並沒有。
- 當接收器收到兩個相同且連續的資料包，上面寫著“從弗雷德的賬戶中扣除 11,000 美元”時，這是否是兩個合法的獨立交易，因此它應該從弗雷德的賬戶中扣除 22,000 美元？還是它實際上只是一筆交易，只是有一點回聲，因此應該只從弗雷德的賬戶中扣除 11,000 美元？
這兩個問題都可以透過新增“序列號”來解決。傳送方跟蹤傳送給接收方的獨立資料包數量，並將該序列號放到每個資料包的頭部。但當重傳資料包時，會重傳相同的資料包，並使用相同的序列號。同樣，接收方在傳送通用“ACK”訊息時，會透過在ACK訊息中新增序列號來指定它正在回覆哪個特定資料包。當出現通訊回聲時，接收方會看到相同的序列號，因此會再次對該序列號進行ACK確認，但隨後會丟棄和忽略它已經接收到的多餘冗餘資料包副本。當傳送方傳送一個恰好包含相同資料的新資料包時，接收方會看到一個不同的序列號，因此會對該新序列號進行ACK確認，並從弗雷德的賬戶中再提取 11,000 美元。可憐的弗雷德。
對於停止-等待系統，一個位元的序列號（對於每個新資料包交替使用 1 - 0 - 1 - 0，並以 ACK1 ACK0 ACK1 ACK0 的方式進行響應）就足夠了。但正如我們將在後面看到的，其他 ARQ 協議需要更大的序列號。
微妙之處：一些早期的協議要求接收方在接收到錯誤資料包時向傳送方傳送一個 NAK（負確認），而傳送方會無限期地等待，直到收到 ACK 或 NAK。這是一個糟糕的主意。想象一下，當 (a) 一點噪聲導致了一個錯誤資料包，因此接收方向傳送方傳送了 NAK，但隨後 (b) 一點噪聲又讓該 NAK 變得無法識別時，會發生什麼。或者，想象一下一個共享介質網路，其中有一個傳送方和兩個接收方。當一點噪聲破壞了資料包的“目標”欄位時，會發生什麼？
使用“停止-等待 ARQ”，傳送方和接收方只需要在一次處理一個數據包。
流式 ARQ
[edit | edit source]傳送方傳送一個數據包，然後傳送下一個資料包，再發送下一個資料包，無需等待。
傳送每個資料包時，它會將該資料包的副本放入一個“視窗”。
每個資料包都進行連續編號。（序列號必須至少足夠大，以唯一地標識視窗中的每個資料包）。
… 週轉時間 … 從地球同步衛星上反彈 …
接收方偶爾會發送一個確認訊息（“我已經收到所有序號小於 8980 的資料包”，“我已經收到所有序號小於 8990 的資料包”）。
如果接收方正在等待序號為 9007 的資料包，但它收到一個序號 *更早* 的資料包（它已經成功接收過該資料包），它會發送（或者可能重新發送）一個“我已經收到所有序號小於 9006 的資料包”訊息。
當傳送方收到“視窗”中任何資料包的確認訊息時，它會刪除該副本。
當傳送方的視窗已滿時，它會等待一小段時間，然後嘗試重新發送視窗中的資料包，從最舊的資料包開始。
因此，當傳送方懷疑某些資料包有錯誤時，它會從錯誤資料包開始重新發送 *所有* 資料包。這保證接收方最終將按照順序收到所有資料包。
可選地，如果接收方正在等待序號為 9007 的資料包，但它收到序號為 9008 的資料包，它可以傳送一個 9007 的負確認 (NAK)，並在收到 9007 的資料包之前忽略任何更高序號的資料包。
當傳送方收到“視窗”中任何資料包的 NAK 時，它會從該資料包開始重新傳輸（並將其保留在視窗中）。
使用“流式 ARQ”，傳送方需要在一次處理整個視窗的資料包。但接收方仍然只需要一次處理一個數據包，並按照順序處理它們。
（有些人認為“流式”就像一個使用“停止-等待”協議的大資料包，其大小與視窗相同，被分成更小的“子資料包”）。
選擇重傳 ARQ
[edit | edit source]
選擇重傳 ARQ 系統是一種流式 ARQ。
但接收方不是隻處理一次一個資料包，並丟棄所有序號高於或低於它正在查詢的資料包的資料包，而是嘗試在自己的視窗中保留所有接收到的資料包的副本，並與傳送方協商，只嘗試重新發送有誤的資料包。
FEC
[edit | edit source]如果只有單向通訊，則必須使用前向糾錯，有時稱為 EDAC（錯誤檢測和糾正）。
傳送資料，然後（而不是 CRC）傳送“校驗位”，這些校驗位是根據資料計算出來的。
… NASA 太空探測器 … 光碟 …
最簡單的型別是“重複訊息”。
如果傳送同一個資料包兩次，並且噪聲只破壞了其中一個，*並且* 接收方可以識別出哪個資料包被破壞，那麼就不會丟失任何資料。如果傳送同一個資料包三次，並且噪聲破壞了其中任何一個，那麼接收方就可以執行“最佳 2/3”。“校驗位”是資料位的兩個副本。事實上，噪聲可能會破壞所有三個資料包的一小部分，你仍然可以提取所有資料——將三個資料包並排放置，並對每一位執行“最佳 2/3”。只要每個資料包中只有少量噪聲，並且噪聲在每個資料包中的位置不同，就可以恢復所有資料。
… （在此處新增圖片）…
有一些非常巧妙的 FEC 型別（漢明碼、裡德-所羅門碼）可以比“最佳 2/3”更好地糾正各種常見錯誤，並且只需要與資料位一樣多的“校驗位”。
假裝從未發生
[edit | edit source]傳送方通常會即時流式傳輸音訊和影片。
當資料包被破壞時，接收方應該怎麼做？
如果它向傳送方傳送一條訊息，要求它重新發送該資料包，那麼當回覆返回時，可能已經是幾個影片幀之後了。使用這些資訊已經太晚了。
與其暫停整個電影，直到請求完成往返，不如讓接收方在悄無聲息地接受一些訊號退化的情況下，將注意力從它身上轉移開，這樣觀眾的觀感不會那麼突兀。接收方會丟棄破壞的資料包，盡力猜測資料包中本來應該有的資料，然後繼續進行，就好像什麼也沒發生一樣。例如，它可能會用附近畫素的顏色填充空白區域。採用這種策略的接收方應該記錄它不得不填充空白的次數，以便使用者可以排除無法持續準確複製的連線故障。
組合
[edit | edit source]即使有雙向通訊，有時人們也會使用 FEC。這樣就可以在接收方糾正少量噪聲。如果資料包被嚴重破壞，FEC 無法修復，協議會回退到 ACK-NAK 重傳（或“假裝從未發生”）。
進一步閱讀
[edit | edit source]一個 ACK-NAK 協議的詳細描述：“XModem / YModem 協議參考”，作者：查克·福斯伯格，1988 年 10 月 14 日 https://web.archive.org/web/20070717073025/http://www.commonsoftinc.com:80/Babylon_Cpp/Documentation/Res/KYModemProtocol.htm 來自原始網站的存檔 http://www.commonsoftinc.com/Babylon_Cpp/Documentation/Res/yModem.htm
一個流式協議的詳細描述：“ZMODEM 應用程式間檔案傳輸協議”，作者：查克·福斯伯格，1988 年 10 月 14 日 https://web.archive.org/web/20061017125259/http://www.commonsoftinc.com/Babylon_Cpp/Documentation/Res/KZModem.htm 來自原始網站的存檔 http://www.commonsoftinc.com/Babylon_Cpp/Documentation/Res/zModem.htm
“資料鏈路錯誤檢測/糾正方法” http://techref.massmind.org/techref/method/errors.htm 對幾種錯誤糾正方法的簡要描述：漢明碼、火碼、裡德-所羅門碼、維特比解碼等。