序列程式設計/錯誤糾正方法
序列程式設計: 簡介和 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 位序列號（對於每個新資料包交替 1 - 0 - 1 - 0，以及 ACK1 ACK0 ACK1 ACK0 的響應）就足夠了。但是，正如我們將看到的，其他 ARQ 協議需要更大的序列號。
微妙之處：一些早期協議讓接收器在接收到不良資料包時向傳送器傳送一個 NAK（否定確認），傳送器會無限期地等待，直到收到 ACK 或 NAK。這是一個壞主意。想象一下，當（a）一些噪聲導致資料包損壞，因此接收器將 NAK 傳送回傳送器，但然後（b）一些噪聲導致 NAK 無法識別。或者，想象一個共享介質網路，其中有一個傳送器和兩個接收器。當一些噪聲弄亂了資料包的“目標”欄位時會發生什麼？
在“停等ARQ”中，傳送方和接收方只需要在同一時間將一個數據包儲存在記憶體中。
傳送方傳送一個數據包，然後傳送下一個資料包，再發送下一個資料包，而無需等待。
在傳送每個資料包時，它會將該資料包的副本放入一個“視窗”中。
每個資料包都按順序編號。（序列號必須至少足夠大，以唯一標識視窗中的每個資料包）。
... 週轉時間 ... 反彈到地球同步衛星 ...
接收方偶爾會發送一個確認訊息（“我已經收到所有編號小於等於8980的資料包”， “我已經收到所有編號小於等於8990的資料包”）。
如果接收方正在期待編號為9007的資料包，但它收到了一個 *更早* 的資料包（它已經成功接收過），它會發送（或可能重新發送）一個“我已經收到所有編號小於等於9006的資料包”訊息。
當傳送方收到“視窗”中任何資料包的確認訊息時，它會刪除該副本。
當傳送方的視窗滿了，它會等待一會兒，然後嘗試從最舊的資料包開始重新發送視窗中的資料包。
因此，當傳送方懷疑某個資料包出現錯誤時，它會從出錯的資料包開始重新發送 *所有* 資料包。這保證了接收方最終會按順序收到所有資料包。
可選地，如果接收方正在期待編號為9007的資料包，但它收到了編號為9008的資料包，它可能會發送一個針對9007的否定確認 (NAK) 訊息，並且忽略任何比它高的資料包編號，直到它收到資料包9007。
當傳送方收到“視窗”中任何資料包的NAK訊息時，它會從該資料包開始重新傳輸（並將它儲存在“視窗”中）。
在“流式ARQ”中，傳送方需要在同一時間將整個“視窗”中的資料包儲存在記憶體中。但接收方仍然只需要一次處理一個數據包，並且按順序處理它們。
（有些人認為“流式”就像一個使用“停等”協議的、大小等於“視窗”的大資料包，被分成更小的“子資料包”）。
選擇性重傳ARQ系統是一種流式ARQ。
但它不是接收方一次只處理一個數據包，並丟棄所有比它正在尋找的資料包編號高或低的資料包，而是接收方試圖將它接收到的所有資料包的副本儲存在它自己的“視窗”中，並與傳送方協商，只重新發送 *錯誤的* 資料包。
如果你只有單向通訊，你被迫使用前向糾錯，有時稱為EDAC（錯誤檢測和糾正）。
你傳送資料，然後（而不是CRC）你傳送從資料計算出來的“校驗位”。
... NASA太空探測器 ... 光碟 ...
最簡單的一種是“重複訊息”。
如果我傳送同一個資料包兩次，並且噪聲只破壞了其中一個，*並且* 接收方能夠識別出哪個被破壞了，那麼就沒有資料丟失。如果我傳送同一個資料包三次，並且噪聲破壞了其中任何一個，那麼接收方就可以做“最佳3選2”。“校驗位”是資料位的兩個副本。事實上，噪聲可能會破壞 *所有三個* 中的一些位，你仍然可以提取所有資料——將三個資料包並排排列，並對每一位執行“最佳3選2”。只要每個資料包中只有少數位被噪聲破壞，並且噪聲在每個資料包中的位置不同，就可以恢復所有資料。
... (在這裡放圖片) ...
有一些非常巧妙的FEC（漢明碼、裡德-所羅門碼），它們可以比“最佳3選2”更好地糾正各種常見的錯誤，並且只需要與資料位數量相同的“校驗位”。
傳送方經常即時流式傳輸音訊和影片。
當資料包被破壞時，接收方應該怎麼做呢？
如果它向傳送方傳送一條訊息，要求它重新發送該資料包，當回覆返回時，可能已經過了幾幀影片。使用這些資訊已經太遲了。
與其讓整部電影暫停，直到請求來回一趟，不如讓接收方在默默地接受一些訊號降級的同時，將觀眾的注意力從它身上轉移開，這樣對觀眾來說不那麼令人反感。接收方會丟棄被破壞的資料包，盡力猜測該資料包中本該有的資料，並繼續執行，就好像什麼都沒發生一樣。例如，它可能會用附近畫素的顏色填充一個空間。使用這種策略的接收方應該記錄它必須填充空白的頻率，以便使用者可以排查無法持續精確再現連線的問題。
即使他們有雙向通訊，有時人們也會使用FEC。這樣，接收方就可以糾正少量噪聲。如果資料包被破壞得太嚴重，以至於FEC無法修復，協議就會回退到ACK-NAK重傳（或“假裝從未發生過”）。
一個ACK-NAK協議的詳細描述：“XModem / YModem協議參考”，作者Chuck Forsberg，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應用程式間檔案傳輸協議”，作者Chuck Forsberg，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 簡要介紹了幾種糾錯方法：漢明碼、火碼、裡德-所羅門碼、維特比解碼等。