芯耀
61
大家好，我是痞子衡，是正經(jīng)搞技術(shù)的痞子。今天痞子衡給大家講的是嵌入式里數(shù)據(jù)差錯控制技術(shù) - 重復(fù)校驗。
在嵌入式應(yīng)用里，除了最核心的數(shù)據(jù)處理外，我們還會經(jīng)常和數(shù)據(jù)傳輸打交道。數(shù)據(jù)傳輸需要硬件傳輸接口的支持，串行接口由于占用引腳少的優(yōu)點目前應(yīng)用比并行接口廣泛，常用的串行接口種類非常多，比如 UART,SPI,I2C,USB 等，在使用這些接口傳輸數(shù)據(jù)時避不可免會遇到一個問題，如果傳輸過程中遇到未知硬件干擾發(fā)生 bit 錯誤怎么辦？
痞子衡今天給大家講的就是數(shù)據(jù)傳輸過程中用于差錯檢測的最簡單的方法，即重復(fù)校驗法。
一、重復(fù)校驗法基本原理
1.1 校驗依據(jù)
重復(fù)校驗法的校驗依據(jù)就是判斷重復(fù)傳輸?shù)?q 組 n bits 二進(jìn)制數(shù)據(jù)是否一致。
1.2 重復(fù)校驗位
為了實現(xiàn)重復(fù)校驗，就是不斷重復(fù)傳輸這組 n bits 原始數(shù)據(jù) q 次即可，一次校驗的 q*n bits 數(shù)據(jù)塊中，僅有 n bits 數(shù)據(jù)是原始有效數(shù)據(jù)，校驗位就是那些重復(fù)的(q-1)*n bits 數(shù)據(jù)。是不是覺得簡單又粗暴？
1.3 校驗方法
假設(shè)原始數(shù)據(jù)塊是 X[n-1:0]共 n bits，重復(fù)次數(shù)為 q（q 一般為奇數(shù)），按重復(fù)傳輸方式，可分為兩個子類：
按 bit 重復(fù)：發(fā)送數(shù)據(jù)序列為，q 個 X0（X0X0...），q 個 X1（X1X1...)...，q 個 Xn-1（Xn-1Xn-1...)
按 block 重復(fù)：發(fā)送數(shù)據(jù)序列為，第 1 個 X[n-1:0]，第 2 個 X[n-1:0]...，第 q 個 X[n-1:0]。
接受端收到數(shù)據(jù)后，逐次比較 q 個重復(fù)位，如完全一致，則認(rèn)為沒有錯差；如不一致，則存在錯誤 bit。如需糾錯的話，原理也很簡單，判斷 q 個重復(fù)位里哪種數(shù)據(jù)位出現(xiàn)的次數(shù)多（這里解釋了 q 為何應(yīng)是奇數(shù)）則為原始正確數(shù)據(jù)位。
1.4 C 代碼實現(xiàn)
實際中按 block 重復(fù)校驗法應(yīng)用比較多，此處示例代碼以此為例：
安裝包:codeblocks-17.12mingw-setup.exe
集成環(huán)境:CodeBlocks 17.12 rev 11256
編譯器:GNU GCC 5.1.0
調(diào)試器:GNU gdb (GDB) 7.9.1
// repetition_code.c
//////////////////////////////////////////////////////////
#include <stdint.h>
#include <assert.h>
/*!
?* @brief 處理按 block 重復(fù)的數(shù)據(jù)塊
?*
?* @param src， 待處理的數(shù)據(jù)塊 .
?* @param dest， 處理完成的原始數(shù)據(jù) .
?* @param lenInBytes， 待處理的數(shù)據(jù)塊長度 .
?* @param repeatTimes， 數(shù)據(jù)重復(fù)次數(shù)（假定為奇數(shù)）.
?* @retval 0， 數(shù)據(jù)無錯誤位 .
?* @retval 1， 數(shù)據(jù)有錯誤位且已糾正 .
?*/
uint32_t verify_correct_repetition_block(uint8_t *src,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?uint8_t *dest,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?uint32_t lenInBytes,
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?uint32_t repeatTimes)
{
? ? assert(repeatTimes % 2);
? ? assert(!(lenInBytes % repeatTimes));
? ? uint32_t result = 0;
? ? uint32_t blockBytes = lenInBytes / repeatTimes;
? ? // 遍歷一個 block 長度里每個 byte
? ? for (uint32_t i = 0; i < blockBytes; i++)
? ? {
? ? ? ? // 遍歷當(dāng)前 byte 的每個 bit
? ? ? ? uint8_t correctByte = 0;
? ? ? ? for (uint32_t j = 0; j < 8; j++)
? ? ? ? {
? ? ? ? ? ? // 遍歷當(dāng)前 byte 的所有重復(fù) byte
? ? ? ? ? ? uint32_t bit1Count = 0;
? ? ? ? ? ? for (uint32_t k = 0; k < repeatTimes; k++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? // 記錄所有重復(fù) byte 中當(dāng)前 bit 為 1 的個數(shù)
? ? ? ? ? ? ? ? uint8_t countByte = *(src + i + k * blockBytes);
? ? ? ? ? ? ? ? bit1Count += (countByte & (0x1u << j)) >> j;
? ? ? ? ? ? }
? ? ? ? ? ? // 當(dāng) bit1 出現(xiàn)半數(shù)則將當(dāng)前 bit 認(rèn)定為 1
? ? ? ? ? ? if (bit1Count > (repeatTimes / 2))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? correctByte |= 0x1u << j;
? ? ? ? ? ? }
? ? ? ? ? ? // 首次發(fā)現(xiàn)錯誤 bit 時，置位 result
? ? ? ? ? ? if ((!result) && (bit1Count !=0) && bit1Count != repeatTimes)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? result = 1;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 將校驗后的 byte 存入 dest
? ? ? ? *(dest + i) = correctByte;
? ? }
? ? return result;
}
// main.c
//////////////////////////////////////////////////////////
#include "repetition_code.h"
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
? ? uint8_t src[3][4] = {{0x32, 0x33, 0x04, 0x08},
? ? ? ? ? ? ? ? ? ? ? ? ?{0x32, 0x83, 0x04, 0xd8},
? ? ? ? ? ? ? ? ? ? ? ? ?{0x31, 0x33, 0x04, 0xe8}};
? ? uint8_t dest[4];
? ? uint32_t result = verify_correct_repetition_block((uint8_t *)src, dest, sizeof(src), sizeof(src) / sizeof(src[0]));
? ? printf("result = %dn", result);
? ? for (uint32_t i = 0; i < sizeof(dest); i++)
? ? {
? ? ? ? printf("dest[%d] = 0x%xn", i, dest[i]);
? ? }
? ? return 0;
}
1.5 行業(yè)應(yīng)用
實際上本文所講的單純的重復(fù)校驗法行業(yè)因為效率的原因，行業(yè)里較少應(yīng)用，其改進(jìn)版的實現(xiàn) RA Codes 應(yīng)用在了 FlexRay 協(xié)議里。
二、重復(fù)校驗法失效分析
重復(fù)校驗實現(xiàn)非常簡單，具有比較理想的檢錯能力，但效率太低，并未得到廣泛使用。即便犧牲了效率，但重復(fù)校驗法也存在如下 2 個缺陷，導(dǎo)致其檢錯糾錯并不可靠：
當(dāng)重復(fù) bit 全部發(fā)生錯誤時，會被誤認(rèn)為沒有錯誤 bit 發(fā)生。
當(dāng)錯誤 bit 出現(xiàn)概率大于原始 bit 時，在糾錯時會認(rèn)定錯誤 bit 是原始 bit。
有沒有其他比重復(fù)校驗法更高效的檢錯方法？痞子衡在下篇會繼續(xù)聊。
至此，嵌入式里數(shù)據(jù)差錯控制技術(shù)之重復(fù)校驗痞子衡便介紹完畢了，掌聲在哪里~~~
