痞子衡嵌入式：常用的數(shù)據(jù)差錯(cuò)控制技術(shù)（1）- 重復(fù)校驗(yàn)(Repetition Code)

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

---

　　大家好，我是痞子衡，是正經(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è)問(wèn)題，如果傳輸過(guò)程中遇到未知硬件干擾發(fā)生bit錯(cuò)誤怎么辦？

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

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

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

　　重復(fù)校驗(yàn)法的校驗(yàn)依據(jù)就是判斷重復(fù)傳輸?shù)膓組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è)X₀（X₀X₀...），q個(gè)X₁（X₁X₁...)...，q個(gè)X_n-1（X_n-1X_n-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 <stdint.h>
#include <assert.h>

/*!
 * @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ù)無(wú)錯(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 <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 = %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)樾实脑颍袠I(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)痞子衡便介紹完畢了，掌聲在哪里~~~

歡迎訂閱

文章會(huì)同時(shí)發(fā)布到我的 博客園主頁(yè)、CSDN主頁(yè)、知乎主頁(yè)、微信公眾號(hào) 平臺(tái)上。

微信搜索"痞子衡嵌入式"或者掃描下面二維碼，就可以在手機(jī)上第一時(shí)間看了哦。