Methods of error detection

簡介：確保傳輸中的數據安全

歡迎來到電腦科學中一個至關重要的課題：確保數據從一處傳送到另一處時準確無誤！數據傳輸從來都不是百分之百可靠的；信號會減弱、干擾會發生，位元（bits）也可能會翻轉。
當你下載大型軟件更新時，你需要確保收到的檔案與伺服器發出的檔案完全一致。

本章重點在於錯誤檢測（Error Detection）——電腦用來識別損壞數據的技術，以及發現錯誤後的處理方式。這個過程對於維護數據完整性（data integrity）至關重要。

1. 為何需要檢查錯誤

數據傳輸過程中出現錯誤，主要是因為傳輸介質（電纜、無線信號）中存在干擾（interference）（例如電噪聲或信號失真）。

可能發生的錯誤類型：

當數據（以 0 和 1 表示）被發送時，信號損壞可能導致：

• 數據更改（損壞）： 0 位元可能意外變成 1，或 1 位元變成 0。這是最常見需要檢測的錯誤。
• 數據丟失： 一塊數據或整個封包可能完全遺失。
• 數據增加： 不需要的或重複的數據可能意外地添加到數據流中。

2. 檢測傳輸錯誤的方法

數據傳輸完成後，接收設備會立即進行檢查。我們需要既快速又可靠的方法。

2.1 同位檢查（Parity Check，包括同位位元組和區塊）

同位檢查是最簡單的方法之一。它檢查一組位元中的 1 的總數是偶數（even）還是奇數（odd）。

同位檢查的運作方式：

必須先約定一個規則：使用偶同位（Even Parity）或奇同位（Odd Parity）。在數據區塊（通常為 7 或 8 位元）中加入一個額外的位元，即同位位元（Parity Bit），以強制執行此規則。

操作步驟：

1. 發送端動作： 計算原始數據中 1 的個數。
2. 發送端動作： 設定同位位元（0 或 1），使整組（數據 + 同位位元）中 1 的總數符合約定的規則。
3. 接收端動作： 計算接收到的整組數據中 1 的總數。
4. 接收端動作： 如果總數符合規則，則假設數據正確。如果不符，則檢測到錯誤。

範例：使用偶同位

我們約定 1 的總數必須為偶數。

• 要發送的數據： 1 0 0 1 1 0 1 0（有四個 1，已是偶數）。
• 同位位元： 設定為 0。
• 發送出的總數： 1 0 0 1 1 0 1 0 0（仍有四個 1，總數為偶數）。

現在，想像傳輸過程中發生了一個錯誤：第三個位元從 0 翻轉為 1。

• 收到的數據： 1 0 1 1 1 0 1 0 0（有五個 1）。
• 接收端檢查： 五個 1 是奇數。系統預期應該是偶數。檢測到錯誤！

簡易同位檢查的局限性

它最大的缺陷是：如果兩個位元（或任何偶數個位元）發生翻轉，同位檢查將仍然通過！系統會誤以為損壞的數據是正確的。

同位區塊檢查（增強可靠性）

為了克服一次只檢查一個位元組的限制，數據可以分塊（以位元組組成的網格）發送。在區塊末尾增加一個額外的位元組，即同位位元組（Parity Byte），其中包含每一欄的同位位元。這稱為同位區塊檢查（Parity Block Check）。

• 系統檢查每一列（row）的同位（標準同位檢查）。
• 系統也檢查每一欄（column）的同位（使用同位位元組）。

如果檢測到錯誤，同時檢查列同位和欄同位，系統就能定位到具體翻轉的那個位元，這使得檢測甚至糾正單一錯誤變得容易得多。

---

2.2 校驗和（Checksum）

校驗和是一種更穩健的數學方法，常用於檢查大型數據塊，例如整個檔案或傳輸封包。

校驗和的運作方式：

1. 發送端計算： 將數據分成固定大小的段。這些段會通過數學方法相加（通常使用專門的加法方式）。
2. 校驗和生成： 將計算結果儲存為校驗和（Checksum）。
3. 傳輸： 將數據塊與校驗和一同發送。
4. 接收端計算： 接收端對接收到的數據段執行完全相同的數學加法。
5. 驗證： 接收端將其新計算出的校驗和與從發送端收到的校驗和進行比較。
6. 結果： 如果兩個校驗和匹配，則數據被接收。如果不同，則說明傳輸過程中發生了錯誤。

類比： 想像一個大快遞箱（數據塊）。發送者在外面貼了一張總重量標籤（校驗和）。如果接收者稱量內容物的重量後，總重與標籤不符，他們就知道運輸過程中有人添加或拿走了東西。

重點提示： 在檢測數據塊內的多個錯誤方面，校驗和比簡單的同位檢查更有效。

---

2.3 回聲檢查（Echo Check）

回聲檢查是一種非常直接的方法，即接收設備將收到的數據直接傳回給發送端進行確認。

操作步驟：

1. 發送端傳輸數據。
2. 接收端立即將數據傳回（即「回聲」）。
3. 發送端將收到的回聲數據與其發出的原始數據進行比較。
4. 如果兩者完全相同，則假設傳輸正確。

缺點： 主要風險是錯誤可能發生在回聲過程（回程）中。發送端會將損壞的接收數據與完美的原始數據進行比較，並正確地發現不匹配，但它無法確定傳輸究竟在哪裡失敗（是在去程還是在回程）。

---

3. 檢查數位（Check Digits，檢測數據輸入錯誤）

雖然同位檢查和校驗和處理的是傳輸錯誤，但檢查數位（Check Digit）是一種特殊技術，主要用於檢測人類在輸入或掃描長參考編號時犯的錯誤（數據輸入錯誤）。

什麼是檢查數位？

檢查數位是附加在代碼編號末尾的一個額外數字。這個數字是利用編號中其餘數字通過數學計算得出的。它起到了安全驗證的作用。

檢查數位的使用場景：

• 國際標準書號（ISBN）： 最後一位數字就是檢查數位。
• 條碼（UPC/EAN）： 條碼線條下方顯示的最後一位數字即為檢查數位。

驗證過程：

當號碼被輸入（或掃描）時：

1. 電腦獲取代碼的主體數位。
2. 它應用特定的計算演算法（通常涉及將每個數字乘以不同的權重）。
3. 它計算出檢查數位「應該是」多少。
4. 它將計算出的檢查數位與實際輸入的檢查數位（代碼的最後一位）進行比較。

如果輸入的號碼有錯誤，例如轉置錯誤（transposition error）（交換了相鄰的數字，例如輸入 1234 而不是 1243）或單一數字錯誤，計算通常會失敗，該號碼將被拒絕。

鼓勵： 不用擔心需要背誦 ISBN 的具體計算方法，只需了解其目的（檢測數據輸入/轉置錯誤）以及何時使用（用於代碼，而非一般數據檔案）即可。

4. 自動重複請求（ARQ）

一旦通過同位檢查或校驗和等方法檢測到錯誤，系統就需要修復它。由於錯誤檢測方法通常無法糾正損壞的數據，最簡單的解決方案是要求發送端再次傳輸該封包。這就是自動重複請求（Automatic Repeat Query, ARQ）協議的工作。

ARQ 使用兩種主要機制來確保可靠交付：

4.1 確認訊息（ACK 和 NACK）

接收端發送一個信號回給發送端，以確認所收封包的狀態：

• 正面確認（ACK）： 如果封包接收正確（例如校驗和匹配），接收端會發送 ACK。發送端隨後可以繼續發送下一個封包。
• 負面確認（NACK）： 如果收到了封包，但檢測到錯誤（例如校驗和失敗），接收端會發送 NACK。此信號告訴發送端：「我收到了封包 5，但它已損壞，請重新發送。」

4.2 超時（Timeout）

如果數據封包完全丟失，且接收端什麼都沒有發回怎麼辦？

超時（timeout）機制處理這種情況：

1. 當發送端傳輸封包時，會啟動一個計時器。
2. 計時器設定為一段合理的時間，稱為超時。
3. 如果發送端在計時器歸零前沒有收到 ACK 或 NACK，它會假設原始封包（或確認訊息）已丟失。
4. 發送端隨後會自動重新發送該封包。

重點提示： ARQ 結合了確認訊息和超時機制，即使發生錯誤，也能保證數據傳輸的可靠性。