大家好，我是痞子衡，是正經(jīng)搞技術(shù)的痞子。今天痞子衡給大家講的是嵌入式里數(shù)據(jù)差錯(cuò)控制技術(shù) - 重復(fù)校驗(yàn)。

在嵌入式應(yīng)用里，除了最核心的數(shù)據(jù)處理外，我們還會(huì)經(jīng)常和數(shù)據(jù)傳輸打交道。數(shù)據(jù)傳輸需要硬件傳輸接口的支持，串行接口由于占用引腳少的優(yōu)點(diǎn)目前應(yīng)用比并行接口廣泛，常用的串行接口種類非常多，比如 UART,SPI,I2C,USB 等，在使用這些接口傳輸數(shù)據(jù)時(shí)避不可免會(huì)遇到一個(gè)問題，如果傳輸過程中遇到未知硬件干擾發(fā)生 bit 錯(cuò)誤怎么辦？

痞子衡今天給大家講的就是數(shù)據(jù)傳輸過程中用于差錯(cuò)檢測(cè)的最簡(jiǎn)單的方法，即重復(fù)校驗(yàn)法。

一、重復(fù)校驗(yàn)法基本原理

1.1 校驗(yàn)依據(jù)

重復(fù)校驗(yàn)法的校驗(yàn)依據(jù)就是判斷重復(fù)傳輸?shù)?q 組 n bits 二進(jìn)制數(shù)據(jù)是否一致。

1.2 重復(fù)校驗(yàn)位

為了實(shí)現(xiàn)重復(fù)校驗(yàn)，就是不斷重復(fù)傳輸這組 n bits 原始數(shù)據(jù) q 次即可，一次校驗(yàn)的 q*n bits 數(shù)據(jù)塊中，僅有 n bits 數(shù)據(jù)是原始有效數(shù)據(jù)，校驗(yàn)位就是那些重復(fù)的(q-1)*n bits 數(shù)據(jù)。是不是覺得簡(jiǎn)單又粗暴？

1.3 校驗(yàn)方法

假設(shè)原始數(shù)據(jù)塊是 X[n-1:0]共 n bits，重復(fù)次數(shù)為 q（q 一般為奇數(shù)），按重復(fù)傳輸方式，可分為兩個(gè)子類：

按 bit 重復(fù)：發(fā)送數(shù)據(jù)序列為，q 個(gè) X0（X0X0...），q 個(gè) X1（X1X1...)...，q 個(gè) Xn-1（Xn-1Xn-1...)

按 block 重復(fù)：發(fā)送數(shù)據(jù)序列為，第 1 個(gè) X[n-1:0]，第 2 個(gè) X[n-1:0]...，第 q 個(gè) X[n-1:0]。

接受端收到數(shù)據(jù)后，逐次比較 q 個(gè)重復(fù)位，如完全一致，則認(rèn)為沒有錯(cuò)差；如不一致，則存在錯(cuò)誤 bit。如需糾錯(cuò)的話，原理也很簡(jiǎn)單，判斷 q 個(gè)重復(fù)位里哪種數(shù)據(jù)位出現(xiàn)的次數(shù)多（這里解釋了 q 為何應(yīng)是奇數(shù)）則為原始正確數(shù)據(jù)位。

1.4 C 代碼實(shí)現(xiàn)

實(shí)際中按 block 重復(fù)校驗(yàn)法應(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
#include

/*!
* @brief 處理按 block 重復(fù)的數(shù)據(jù)塊
*
* @param src， 待處理的數(shù)據(jù)塊 .
* @param dest， 處理完成的原始數(shù)據(jù) .
* @param lenInBytes， 待處理的數(shù)據(jù)塊長(zhǎng)度 .
* @param repeatTimes， 數(shù)據(jù)重復(fù)次數(shù)（假定為奇數(shù)）.
* @retval 0， 數(shù)據(jù)無錯(cuò)誤位 .
* @retval 1， 數(shù)據(jù)有錯(cuò)誤位且已糾正 .
*/
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;

// 遍歷一個(gè) block 長(zhǎng)度里每個(gè) byte
for (uint32_t i = 0; i < blockBytes; i++)
{
// 遍歷當(dāng)前 byte 的每個(gè) 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 的個(gè)數(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)錯(cuò)誤 bit 時(shí)，置位 result
if ((!result) && (bit1Count !=0) && bit1Count != repeatTimes)
{
result = 1;
}
}
// 將校驗(yàn)后的 byte 存入 dest
*(dest + i) = correctByte;
}

return result;
}

// main.c
//////////////////////////////////////////////////////////
#include "repetition_code.h"
#include
#include

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 = %d/n", result);
for (uint32_t i = 0; i < sizeof(dest); i++)
{
printf("dest[%d] = 0x%x/n", i, dest[i]);
}
return 0;
}

1.5 行業(yè)應(yīng)用

實(shí)際上本文所講的單純的重復(fù)校驗(yàn)法行業(yè)因?yàn)樾实脑?，行業(yè)里較少應(yīng)用，其改進(jìn)版的實(shí)現(xiàn) RA Codes 應(yīng)用在了 FlexRay 協(xié)議里。

二、重復(fù)校驗(yàn)法失效分析

重復(fù)校驗(yàn)實(shí)現(xiàn)非常簡(jiǎn)單，具有比較理想的檢錯(cuò)能力，但效率太低，并未得到廣泛使用。即便犧牲了效率，但重復(fù)校驗(yàn)法也存在如下 2 個(gè)缺陷，導(dǎo)致其檢錯(cuò)糾錯(cuò)并不可靠：

當(dāng)重復(fù) bit 全部發(fā)生錯(cuò)誤時(shí)，會(huì)被誤認(rèn)為沒有錯(cuò)誤 bit 發(fā)生。

當(dāng)錯(cuò)誤 bit 出現(xiàn)概率大于原始 bit 時(shí)，在糾錯(cuò)時(shí)會(huì)認(rèn)定錯(cuò)誤 bit 是原始 bit。

有沒有其他比重復(fù)校驗(yàn)法更高效的檢錯(cuò)方法？痞子衡在下篇會(huì)繼續(xù)聊。

至此，嵌入式里數(shù)據(jù)差錯(cuò)控制技術(shù)之重復(fù)校驗(yàn)痞子衡便介紹完畢了，掌聲在哪里~~~

審核編輯 黃昊宇