安卓與串口通信-校驗篇
前言
一些閒話
時隔好幾個月，終於又繼續更新安卓與串口通信系列了。
這幾個月太頹廢了，每天不是在睡覺就是虛度光陰，最近準備重新開始上進了，所以將會繼續填坑。
今天這篇文章，我們來説説串口通信常用的幾種校驗方式的原理以及給出計算代碼，當然，因為我們講的是安卓的串口通信，所以代碼將使用 kotlin 來編寫。
基礎知識
在正式開始我們今天的內容之前，我先提一個問題：什麼是數據校驗？以及為什麼要進行數據校驗？
其實如果有看過我們這系列的前面幾篇文章的話，相信這個問題不用我説你們也會知道答案。
正如我們前面文章中也介紹過的，在串口通信中，由於可能受到靜電之類的電磁干擾，會使得傳輸過程中的電平發生波動，最終導致數據出錯。
並且串口通信實際上是採用幀數據傳輸的，數據可能會被分割成很多份來傳輸，如果出現錯誤應當及時告知發送方，並讓其重傳，以保證數據的可靠性和完整性。
我們回顧一下之前的知識：在串口的一幀數據中，包含了 起始位、數據位、校驗位、停止位 四個不同的數據區塊。其中的校驗位就是用來存放我們今天要講的校驗信息的。
串口一幀數據有 5-8 位，校驗位只有 1 位，所以在一幀數據中的校驗通常使用的是奇校驗（odd parity）和偶校驗（even parity）。不過實際使用過程中大多數情況下都會選擇不設置校驗位（none parity），轉而在自己的通信協議中另外使用其他的校驗方式校驗整體的數據，而不是校驗單獨一幀的數據。
而對於整體數據的校驗，校驗方法就多得多了，常見的有以下幾種：校驗和、BCC、CRC。
常見校驗算法
奇偶校驗（Parity）
正如前言中所述，奇偶校驗通常用於一幀數據的校驗，因為它的算法很簡單，而且校驗碼也只需要一位。
奇偶校驗的原理十分簡單，就是在數據的末尾添加 1 或 0，使得這串數據（包括末尾添加的一位）的 1 的個數為奇數（奇校驗）或偶數（偶校驗）。
例如：需要傳輸數據 01101001
如果使用 奇校驗 的話，由於原數據中 1 的個數是 4 個，是偶數個，所以我們需要在末尾添加 1 使其變為 5 個 1 ，也就是奇數個 1，即帶有奇校驗的數據應該是 011010011。
而如果使用偶校驗的話同理，由於原數據中已經是偶數個 1 了，所以在末尾應該添加一個 0，即帶有偶校驗的數據應該是 011010010。
奇偶的校驗由於簡單、快速、效率高，對數據傳輸量小的場景比較適用。此外，與其他校驗方式相比，奇偶校驗的計算量較小，對於嵌入式設備和低功耗設備等資源有限的場景更為適合。
但是，奇偶校驗只能檢測單比特錯誤，不能檢測多比特錯誤，什麼意思呢？比如我們有一個數據 1110111001 在傳輸過程中受到干擾變成了 0100011000 ，此時如果使用奇偶校驗，那麼這個數據是可以校驗通過的，因為它的數據中多個比特都受到了干擾，恰好還是保持了 1 的個數為奇數個，所以使用奇偶校驗並不能校驗出這個問題來。
下面貼上一個使用 kotlin 實現的奇偶校驗代碼：
```kotlin fun evenParity(data: Byte): Byte { var numOnes = 0 var value = data.toInt() for (i in 0 until 8) { if (value and 0x01 != 0) { numOnes++ } value = value shr 1 }
return if (numOnes % 2 == 0) 0 else 1
}
fun main() { val data = 0x69.toByte() // 1101001
println("偶校驗位=${evenParity(data)}")
} ```
evenParity() 函數會輸出傳遞的 data 的校驗位，上面的代碼會輸出：
偶校驗位=1
當然，計算奇校驗位同理，只要把函數返回的地方改為 return if (numOnes % 2 == 0) 1 else 0 即可。
這裏的使用的算法也非常簡單，就是把傳入 data 的每一位從左到右依次對 1 做與運算，如果運算結果不為 0 即該位是 1， 則 1 的數量加一，然後判斷 1 的數量是否為偶數。
所以其實還有一個更簡短的方法，那就是 kotlin 其實已經給我們封裝好了計算一個 byte 中 1 的比特數的函數：
```kotlin fun evenParity(data: Byte): Byte { val numOnes = data.countOneBits()
return if (numOnes % 2 == 0) 0 else 1
}
fun main() { val data = 0x69.toByte() // 1101001
println("偶校驗位=${evenParity(data)}")
} ```
對了，一個 byte（字節）等於 8 個比特（就是八個不同的0和1）這個是基礎中的基礎，應該不用我再説了吧？哈哈哈。
ps：在實際使用中，我們還可以定義校驗位為：
- PARITY_MARK，即校驗位恆為 1
- PARITY_SPACE，即校驗位恆為 0
校驗和（Check Sum）
校驗和的算法也十分好理解，就是把要發送的所有數據依次相加，然後將得出的結果取最後一個字節作為校驗碼附在數據後面一起發送。
接收端在接收到數據和校驗碼後同樣將數據依次相加得到一個值，將這個值的最後一子節與校驗碼對比，如果一致則認為數據沒有出錯。
例如，我們要發送一串數據： 0x45 0x4C 0x32 0x55 。
則我們在計算校驗碼時直接將其相加，得到 0x118，僅截取最後一個字節，即為 0x18 。
所以實際發送的包含校驗碼的數據是： 0x45 0x4C 0x32 0x55 0x18。
不過實際在使用校驗和這個校驗算法時，通常會根據情況定義一些其他的規則。
比如，有時候我們會定義在將需要傳輸的數據全部累加之後，將得到的結果按比特取反後附加到數據後面作為校驗碼，接收端接收到數據後，將所有數據（包含校驗碼）累加，最終得到的數據全為 1 則表示數據傳輸沒有出錯。
例如，我們要發送數據： 0x45 0x4C 0x32 。
相加後得到 0xC3，二進制數據為 1100 0011。
取反後為 0011 1100，即十六進制 0x3C 。
所以實際發送的數據是 0x45 0x4C 0x32 0x3C。
接收端在接收到這個數據後，將其連同校驗碼一起累加，得到結果 0xFF 即 二進制的 1111 1111 ，所以認為數據傳輸沒有出錯。
有時候也會有規則定義為把要傳輸的數據全部按位取反後再相加，總之無論是什麼變體規則，萬變不離其宗，其基本原理都是一樣的，我們只需要在實際使用時按照廠商要求的規則編寫校驗即可。
説完這些，總結一下，校驗和的優點是計算簡單、速度快，可以快速檢測到數據傳輸中的錯誤。
缺點是無法檢測出所有的錯誤，例如兩個字節交換位置的錯誤可能會被誤認為是正常的校驗和，因此不能保證100%的可靠性。
下面貼上使用 Kotlin 實現的校驗和算法：
```kotlin fun checkSum(data: ByteArray): Char { if (data.isEmpty()) { return 0xFF.toChar() }
var res = 0x00.toChar()
for (datum in data) {
res += (datum.toInt() and 0xFF).toChar().code
}
// res = (res.code xor 0xFF).toChar() // 如果要做取反則去掉這個註釋
res = (res.code and 0xFF).toChar()
return res
}
fun main() { println(checkSum(byteArrayOf(0x45, 0x4C, 0x32, 0x55)).code.toString(16)) } ```
上述代碼輸出： 18 。
當然，這裏給出的代碼是我們説的第一種情況，直接計算所有子節的和。
如果我們想要計算的是我們説的第二種情況，即把結果按位取反的話只需要把代碼中註釋掉的地方去掉即可：
```kotlin fun checkSum(data: ByteArray): Char { if (data.isEmpty()) { return 0xFF.toChar() }
var res = 0x00.toChar()
for (datum in data) {
res += (datum.toInt() and 0xFF).toChar().code
}
res = (res.code xor 0xFF).toChar() // 如果要做取反則去掉這個註釋
res = (res.code and 0xFF).toChar()
return res
}
fun main() { println(checkSum(byteArrayOf(0x45, 0x4C, 0x32)).code.toString(16)) } ```
上述代碼輸出 3c。
BCC（Block Check Character）
BCC 校驗的原理是通過對數據塊中的每個字節進行異或操作，得到一個 BCC 值，然後將該值添加到數據塊的末尾進行傳輸，接收方計算接收到的數據後與 BCC 值比較，如果值一致則認為數據傳輸沒有出錯。
BCC 計算過程簡單説就是先定義一個初始 BCC 值 0x00 ，然後將待計算的數據第一個字節與 BCC 值做異或運算，運算之後得到新的 BCC 值，然後再用這個新的 BCC 與待計算數據的第二個字節做 BCC 運算，以此類推，直到待計算的所有數據都與 BCC 值做了異或計算，此時得到的 BCC 值即為最終的 BCC 值。
然後將這個 BCC 值附加到原始數據後面一同發送，接收端在接收到數據後，將數據部分按照上述算法計算出一個值，然後將這個值與接收到的 BCC 值對比，如果一致則認為數據傳輸正確。
對了這裏插一段，異或計算就是按照對應位上的值相同為 0 不同為 1，例如 0x45 異或 0x4C 即：
0100 0101 （0x45）
xor
0100 1100 （0x4C）
=
0000 1001 （0x9）
所以不難看出任何數與 0x00 做異或得到的還是這個數，所以我們才能把 BCC 初始值定義為 0x00。
下面我們舉個計算 BCC 的例子，我們需要計算數據 0x45 0x4C 0x32 0x55 的BCC值：
- 預設 BCC = 0x00
- 計算 BCC = 0x00 xor 0x45 = 0x45
- 計算 BCC = 0x45 xor 0x4C = 0x09
- 計算 BCC = 0x09 xor 0x32 = 0x3B
- 計算 BCC = 0x3B xor 0x55 = 0x6E
所以最終計算得出的 BCC 值為 0x6E。
BCC校驗的優點是計算簡單、速度快，並且可以檢測出數據塊中多個字節的錯誤。與其他校驗方式相比，BCC校驗的錯誤檢測能力更強，因為它可以檢測出更多類型的錯誤。缺點是不能糾正錯誤，只能檢測錯誤，而且對於較長的數據塊，BCC校驗的誤判率可能會增加。
下面貼上使用 kotlin 實現的 BCC 算法：
```kotlin fun computeBcc(data: ByteArray): Byte { var bcc: Byte = 0 for (i in data.indices) { bcc = bcc.xor(data[i]) } return bcc }
fun main() { println(computeBcc(byteArrayOf(0x45, 0x4C, 0x32, 0x55)).toString(16)) } ```
上面代碼輸出： 6e
CRC（Cyclic Redundancy Check）
CRC校驗的原理是基於多項式的除法進行計算，在計算時會將數據塊看作一個多項式，對其進行除法運算，計算得到的餘數即為 CRC 校驗碼，然後將其附加到原數據的末尾隨數據一起傳輸，接收方接收到數據後按照相同的算法對其中的數據進行計算，並用計算的到的值與接收到的 CRC 校驗碼進行對比，如果一致則認為傳輸數據沒有出錯。
而按照校驗碼的長度不同，CRC又具有不同的分類算法，例如常見的有 CRC-8 、 CRC-16、CRC-32 三種不同的分類。它們分別表示計算出來的校驗碼長度是 8 位、 16 位 、 32位 。同時它們檢測錯誤的長度也不同，例如 CRC-8 可以檢測長度小於等於 8 位的錯誤。另外，不同的算法使用的多項式也不相同。
下面我們以 CRC-16 為例子説説它的計算過程。（計算過程來自參考資料 4）
- 首先選定一個有 K 位的二進制數作為標準除數（這個二進制數由多項式得到，可以自定義，但是也有一些約定俗成的固定數值）
- 將需要計算的 m 位原始數據後面加上 K-1 位 0，得到一個長度為 m+K-1 位的新數據，然後使用模2除法除以 步驟 1 中定義的標準除數，得到一個餘數，繼續重複計算直至餘數比除數少且只少一位（不夠就補0），此時的餘數即為 CRC 校驗碼。
- 將計算出的校驗碼附在原始數據後面，即可得到需要發送的數據，長度為 m+K-1 位。
- 此時接收端接收到數據後，將其除以步驟 1 中定義的除數，如果餘數為 0 則表示數據傳輸沒有出錯。（ps：理論上應該是這樣去校驗數據 ，但是實際使用時更多的是偷懶直接重新算一遍 CRC 校驗碼，然後和接收到的校驗碼對比，🤦）
因為 CRC 的算法比較複雜，直接説可能理解起來不太直觀，推薦看一下參考資料 5 的視頻，這樣就能有一個直觀的認識。
如果我們想要使用算法實現的話，則可以通過以下步驟：
- 將數據塊看作一個二進制數，將它的最高位對齊 CRC-16 校驗碼的最高位。
- 將 CRC-16 校驗碼的每一位都與對應的數據位異或，並將結果賦給一個臨時變量 temp 。
- 如果 temp 的最高位是1，就將它右移一位並將預置值 0x8005 （這個值就是定義的標準除數）與它異或，否則直接右移一位。
- 重複執行步驟 2、3，直到所有數據位都被處理完畢。
- 處理完所有數據位後，temp 中保存的就是 CRC-16 校驗碼。
總的來説，CRC校驗的優點在於其具有高效、可靠的校驗能力，能夠檢測多種類型的數據傳輸錯誤，如位反轉、位移、插入、刪除等。
與之對應的 CRC 的計算複雜度相較上述的幾種算法更高，因此需要消耗較多的計算資源，尤其是對於一些低性能的設備或嵌入式系統而言，可能會對系統性能造成較大的影響。另外，CRC校驗值的長度比較長，例如 CRC-32 的校驗值有 32 位，這無疑會增加傳輸的開銷。
下面貼上使用 kotlin 實現的 CRC-16 代碼：
kotlin
fun calculateCRC16(data: ByteArray): Int {
val polynomial = 0x8005
var crc = 0xFFFF
for (b in data) {
crc = crc xor (b.toInt() and 0xFF)
for (i in 0 until 8) {
crc = if (crc and 0x0001 != 0) {
crc shr 1 xor polynomial
} else {
crc shr 1
}
}
}
return crc and 0xFFFF
}
注意，這裏我們使用的多項式值（標準除數）是 0x8005 ，各位在使用的時候需要換成設備廠商或者你們自己約定好的值，比如我之前接入的一塊使用 MODBUS 通信的 PLC 主板約定的值就是 0xA001 而非 0x8005。
另外，可能有些設備廠商會對 CRC 校驗碼的高低位順序有要求，例如需要保證高位在前，低位在後，則我們可以在後面額外加上幾段代碼來實現：
kotlin
val polynomial = 0x8005
var crc = 0xFFFF
for (b in data) {
crc = crc xor (b.toInt() and 0xFF)
for (i in 0 until 8) {
crc = if (crc and 0x0001 != 0) {
crc shr 1 xor polynomial
} else {
crc shr 1
}
}
}
val lowByte: Byte = (crc shr 8 and 0xFF).toByte()
val highByte: Byte = (crc and 0xFF).toByte()
return ByteArray(0).plus(highByte).plus(lowByte)
}
對了，計算 CRC-8 和 CRC-32 的算法是一樣的，只需要更改對應的初始值（crc = 0xFF 或 crc = 0xFFFFFFFF）和多項式值即可。
總結
總的來説，在串口通信中常用的校驗方式為：
- 奇偶校驗，主要用於串口一幀（1字節）數據的校驗，這意味着每字節數據都需要額外添加校驗位，所以通常使用時都會選擇無校驗。
- CRC校驗，由於CRC校驗的相對來説更加可靠，而且校驗的是整體的數據而非單比特數據，所以實際使用時通常會使用到它。
當然，這篇文章中介紹的只是幾個常見的校驗方法，還有更多校驗方法這裏沒有説到，如果有需要的話歡迎補充。
參考資料
本文正在參加「金石計劃」
- 安卓與串口通信-校驗篇
- 安卓與串口通信-實踐篇
- 為 Kotlin 的函數添加作用域限制（以 Compose 為例）
- 安卓與串口通信-基礎篇
- Compose For Desktop 實踐：使用 Compose-jb 做一個時間水印助手
- 初探 Compose for Wear OS：實現一個簡易選擇APP
- Compose太香了，不想再寫傳統 xml View？教你如何在已有View項目中混合使用Compose
- 在安卓中壓縮GIF的幾種方法(附實例代碼)
- 魔改車鑰匙實現遠程控車：（1）整體思路及控制方案實現
- 跟我一起使用 compose 做一個跨平台的黑白棋遊戲（3）狀態與遊戲控制邏輯
- 跟我一起使用 compose 做一個跨平台的黑白棋遊戲（2）界面佈局
- 以不同的形式在安卓中創建GIF動圖
- 跟我一起使用 compose 做一個跨平台的黑白棋遊戲（4）移植到compose-jb實現跨平台
- 羨慕大勞星空頂？不如跟我一起使用 Jetpack compose 繪製一個星空背景（帶流星動畫）
- 魔改車鑰匙實現遠程控車：（4）基於compose和經典藍牙編寫一個控制APP