BCH碼在物聯(lián)網(wǎng)存儲系統(tǒng)中的應(yīng)用研究

荊坤坤 汪丹丹 朱倩 紀(jì)啟國 陳芳

摘? 要：隨著物聯(lián)網(wǎng)設(shè)備對存儲容量的需求不斷擴大，Nand Flash作為主流的存儲設(shè)備在物聯(lián)網(wǎng)系統(tǒng)中應(yīng)用非常廣泛，為了保證數(shù)據(jù)的準(zhǔn)確性，選擇一種性能良好的糾錯算法至關(guān)重要。目前最為常用的是BCH碼，由于嵌入式存儲系統(tǒng)MCU沒有能夠?qū)崿F(xiàn)BCH編解碼的硬件控制器，需要用軟件來實現(xiàn)，文章通過對BCH碼算法和Nand Flash物理特性的研究，為物聯(lián)網(wǎng)應(yīng)用場景提供一種軟件編/譯碼方案，從而提高物聯(lián)網(wǎng)系統(tǒng)存儲數(shù)據(jù)的完整性和可靠性。

關(guān)鍵詞：BCH碼；Nand Flash；物聯(lián)網(wǎng)；檢錯糾錯

中圖分類號：TP274? ? 文獻標(biāo)識碼：A 文章編號：2096-4706（2023）02-0164-03

Application Research of BCH Code in IoT Storage System

JING Kunkun， WANG Dandan， ZHU Qian， JI Qiguo， CHEN Fang

（Anhui Vocational College of City Management， Hefei? 230011， China）

Abstract： With the increasing demand for storage capacity of IoT devices， Nand Flash， as a mainstream storage device， is widely used in IoT systems. In order to ensure the accuracy of data， it is very important to select an error correction algorithm with good performance. At present， the most commonly used one is BCH code. Since the embedded storage system MCU does not have a hardware controller which could achieve the BCH coding and decoding， it needs to be implemented by software. Through the research on BCH code algorithm and Nand Flash physical characteristics， this paper provides a software coding/decoding scheme for IoT application scenarios， so as to improve the integrity and reliability of the data stored in the IoT system.

Keywords： BCH code; Nand Flash; IoT; error detection and correction

0? 引? 言

近年來，物聯(lián)網(wǎng)技術(shù)快速發(fā)展，廣泛應(yīng)用在智能家居、工業(yè)控制、智慧城市、智能可穿戴等多個領(lǐng)域。隨著應(yīng)用場景日益復(fù)雜，功能逐漸多樣化，圖像、音視頻數(shù)據(jù)不斷增大，物聯(lián)網(wǎng)設(shè)備對存儲容量的需求不斷擴大，傳統(tǒng)MCU片內(nèi)Flash外和少量外部Nor Flash，已經(jīng)無法滿足需求。價格低廉、容量大的Nand Flash成為越來越受青睞的存儲方案。

然而，Nand Flash因制造工藝和設(shè)計原理的限制，存在電荷漂移、編程干擾、壞塊等問題，一旦發(fā)生Bit Flip（位翻轉(zhuǎn)），其上存儲的數(shù)據(jù)會發(fā)生錯誤，可靠性無法保障。針對這一問題，業(yè)界引入了ECC（Error Correcting Code）機制，對已經(jīng)發(fā)生錯誤的bit位進行糾正。具體實現(xiàn)上，ECC通常采用漢明碼、CRC、RS碼、BCH碼等。BCH碼相比其他編碼，檢錯/糾錯能力更強，在Nand Flash中使用更普遍。

雖然物聯(lián)網(wǎng)應(yīng)用場景對Nand Flash有強烈的需求，技術(shù)上卻存在壁壘。Nand Flash需要的BCH碼通常是由SoC上的硬件控制器處理的，而MCU沒有對應(yīng)的硬件控制器（通過SPI總線與Nand Flash傳輸數(shù)據(jù)）。該問題可借鑒某些SoC的做法來解決，即：采用軟件BCH編解碼運算。相比SoC、MCU的運算能力弱，采用軟件編解碼的方法，會導(dǎo)致讀寫性能變差，影響整個系統(tǒng)的效率，該方案停留在功能打通卻難以產(chǎn)品化的境地，亟待解決。

綜上，針對上述問題，在MCU有限的資源條件下，通過技術(shù)的研究與創(chuàng)新，打破既有的Nand Flash技術(shù)壁壘，不帶來額外的成本開銷，實現(xiàn)Nand Flash存儲真正的落地，達到產(chǎn)品化標(biāo)準(zhǔn)，滿足物聯(lián)網(wǎng)應(yīng)用場景日益增長的需求，具有很大的價值與意義。

1? 整體設(shè)計

1.1? BCH編碼的基本原理

矩陣BCH碼是一種能夠檢錯糾錯的線性分組碼，憑借其較強的糾錯檢錯能力而被廣泛應(yīng)用于存儲系統(tǒng)和通信領(lǐng)域中。BCH編碼定義如下：給定任一有限域GF（q）及其擴域GF（qm），其中q是素數(shù)或者素數(shù)的冪，m為某一正整數(shù)。若任一碼元取自GF（qm）上的循環(huán)碼（n，k），其中n=2m-1，其生成多項式g（x）具有2t個連續(xù)根{a1，a2，…，a2t-1，a2t}時，t為糾正位數(shù)，則由生成多項式g（x）生成的循環(huán)碼稱為q進制BCH碼，記為（n，k，t）。最常用的BCH碼通常為二進制的BCH碼，二進制BCH碼的碼元都是由0和1構(gòu)成的，可靠性比較高，有利于數(shù)據(jù)的傳輸。

本文使用MICRON NAND devices，每頁可配置為2 KB+

64 B，并且每頁又分為4個子頁，即每個子頁為512 B+16 B，內(nèi)部存儲結(jié)構(gòu)如圖1所示。

1.2? MCU并行處理

為了提高存儲系統(tǒng)的運行速度，本設(shè)計創(chuàng)新性的提出一種思路，也即是利用IO讀寫比較耗時的特點，MCU一邊進行IO讀寫，同時對傳輸?shù)臄?shù)據(jù)進行BCH編解碼，充分利用IO讀寫的時間而不是空等待IO。傳統(tǒng)做法是整個頁的數(shù)據(jù)全部傳輸完成，再進行BCH編解碼，相比傳統(tǒng)做法，本設(shè)計并行地提升了系統(tǒng)的運行速度和性能。下面以讀操作為例來講解算法的過程，本設(shè)計是將一頁數(shù)據(jù)分成4段，目前第2段已傳輸完，正在BCH解碼，IO同時在傳輸?shù)?段，第2段BCH解碼完成后會像第1段一樣放在緩存中，這樣利用MCU并行處理的方式，大大提升了數(shù)據(jù)傳輸?shù)乃俣?，?shù)據(jù)傳輸示意圖如圖2所示。

1.3? Nand Flash存儲格式和random access的分段讀寫技術(shù)

為了實現(xiàn)MCU并行處理，系統(tǒng)設(shè)計時需要將Nand Flash一頁數(shù)據(jù)的存儲格式分成多個小段，本設(shè)計是將一頁數(shù)據(jù)分成4份，在讀寫時需要采用Nand Flash的random acces技術(shù)。傳統(tǒng)讀寫操作從頁的起始地址開始，分段讀寫需要從頁內(nèi)的某個偏移地址開始。同時，為了在IO操作時將MCU空閑出來做BCH運算，IO必須采用DMA的方式。利用DMA搬運數(shù)據(jù)，實現(xiàn)MCU多任務(wù)并發(fā)處理，使得BCH解碼和IO傳輸數(shù)據(jù)并行執(zhí)行，進而提高讀寫性能。

1.4? 依據(jù)BCH碼的糾錯檢錯能力及時預(yù)判轉(zhuǎn)移數(shù)據(jù)

BCH碼有檢錯和糾錯的能力，檢錯能力大于糾錯能力。通常，Nand Flash上存儲的數(shù)據(jù)，由于電荷漂移或?qū)懜蓴_等因素會造成數(shù)據(jù)位出現(xiàn)錯誤，隨著時間的推移，Nand Flash上存儲的數(shù)據(jù)出錯的位數(shù)會逐漸增多，當(dāng)錯誤位數(shù)超過了Nand Flash糾錯能力范圍時，BCH碼將無法把錯誤的數(shù)據(jù)位進行糾正，也即是無法將數(shù)據(jù)恢復(fù)正常。利用這一自然變化過程的特性，本文設(shè)計的算法會在MCU讀操作的BCH解碼階段，判斷錯誤位數(shù)的數(shù)量，如果快要超過糾錯能力范圍，提前將其存儲在別的物理頁上。例如：對于512字節(jié)的數(shù)據(jù)，假設(shè)BCH最大糾錯能力為1 bit。512字節(jié)剛寫入Nand存儲體中時，其出現(xiàn)的錯誤位數(shù)為0，隨著時間的推移，錯誤位數(shù)會逐漸增多，這些錯誤的數(shù)據(jù)會在讀操作時被BCH碼糾正正確。在讀操作時BCH碼發(fā)現(xiàn)有1位錯誤，如果再放置一段時間錯誤的位數(shù)可能超過BCH碼的最大糾錯位數(shù)1 bit，屆時BCH碼將無法完全糾正其錯誤的數(shù)據(jù)，從而無法保證數(shù)據(jù)的準(zhǔn)確性。

那本文設(shè)計的算法可以根據(jù)BCH碼檢錯糾錯的能力，提前預(yù)判數(shù)據(jù)的錯誤位數(shù)，在錯誤數(shù)據(jù)的位數(shù)即將超越糾錯上限時，及時將數(shù)據(jù)轉(zhuǎn)移到新的存儲單元，讓錯誤位數(shù)恢復(fù)到0，避免無法糾正數(shù)據(jù)的情況發(fā)生，從而提高系統(tǒng)讀寫數(shù)據(jù)的穩(wěn)定性。

2? 設(shè)計仿真驗證

在PC環(huán)境下，對設(shè)計的BCH碼進行基本功能的仿真和驗證。

2.1? BCH碼算法的實現(xiàn)

用代碼實現(xiàn)BCH碼的算法，由于篇幅限制，在這里只針對主要接口做簡單介紹：

（1）void bch_generate（const struct bch_def *bch，const uint8_t *chunk， size_t len， uint8_t *ecc）;

功能：此函數(shù)接口能根據(jù)需求和給定的數(shù)據(jù)，生成校驗碼。

參數(shù)：bch定義了BCH碼的細(xì)節(jié)，如糾錯能力等；chunk指針指向原始數(shù)據(jù)；len是數(shù)據(jù)長度；ecc用于存放生成的校驗碼。

（2）int bch_verify（const struct bch_def *bch，const uint8_t *chunk， size_t len， const uint8_t *ecc）;

功能：此函數(shù)接口能根據(jù)給定的數(shù)據(jù)和校驗碼，驗證數(shù)據(jù)是否發(fā)生了錯誤，該接口函數(shù)只能檢錯，不負(fù)責(zé)糾錯。

參數(shù)：bch定義了BCH碼的細(xì)節(jié)，如糾錯能力等；chunk指針指向原始數(shù)據(jù)；len是數(shù)據(jù)長度；ecc用于存放生成的校驗碼。

返回值：0代表成功，-1代表失?。ū硎居绣e誤位存在）。

（3）void bch_repair（const struct bch_def *bch，const uint8_t *chunk， size_t len， uint8_t *ecc）;

功能：此函數(shù)接口能根據(jù)給定的數(shù)據(jù)和校驗碼，將數(shù)據(jù)中存在的錯誤位進行糾正；

參數(shù)：bch定義了BCH碼的細(xì)節(jié)，如糾錯能力等；chunk指針指向原始數(shù)據(jù)；len是數(shù)據(jù)長度；ecc用于存放生成的校驗碼。

2.2? BCH碼算法的測試

根據(jù)優(yōu)化的BCH碼算法，設(shè)計針對性的測試方案，具體的流程如圖3所示。

首先，當(dāng)測試數(shù)據(jù)為全0xFF時，判斷BCH碼能否校驗通過。注意，在這里有一種特殊情況，即當(dāng)Nand Flash塊全擦除后，數(shù)據(jù)為全0xFF，此時無需生成校驗碼，數(shù)據(jù)也能正常校驗通過。

接下來，當(dāng)BCH碼能否校驗通過后，系統(tǒng)會生成隨機數(shù)據(jù)。用隨機數(shù)據(jù)再生成校驗碼，為后續(xù)對數(shù)據(jù)的檢錯和糾錯做好準(zhǔn)備。

最后，在數(shù)據(jù)的隨機位置，人為制造錯誤，通過調(diào)用BCH碼算法進行數(shù)據(jù)的檢錯和糾錯。

以上就是BCH碼檢錯和糾錯的整個流程，為了得到更精確的結(jié)果，我們在設(shè)計時進行了多次循環(huán)測試，以充分驗證功能的穩(wěn)定性。

2.3? BCH碼算法的仿真結(jié)果分析

在仿真階段，本文將PC上很大的RAM空間（或磁盤文件）模擬成Nand Flash存儲介質(zhì)，根據(jù)上述設(shè)計的測試方案，將優(yōu)化后的BCH碼算法在PC上運行，使其滿足項目的需求。

由于物聯(lián)網(wǎng)存儲系統(tǒng)對數(shù)據(jù)的處理和響應(yīng)的時間要求很高，所以本階段的仿真實驗，我們通過對糾錯1 bit、2 bit、3 bit和4 bit所需要的糾錯時間進行對比驗證，為了得到更精確的時間，測試時每組數(shù)據(jù)進行循環(huán)測試10次，具體的每一次測試中進行20次循環(huán)測試，相當(dāng)于每組數(shù)據(jù)重復(fù)測試200次，最后取平均值，得到每糾錯1 bit、2 bit、3 bit和4 bit所需要的時間，具體的測試結(jié)果如表1所示。

通過測試，我們發(fā)現(xiàn)糾錯能力為1 bit時，所需要的糾錯時間、檢錯時間和生成校驗碼的時間都是最短的，很好的滿足物聯(lián)網(wǎng)存儲系統(tǒng)對速度的要求，同時也節(jié)省了存儲空間。

所以通過上述實驗仿真驗證，在本系統(tǒng)設(shè)計時，我們選取的糾錯位為t=1位，校驗碼的長度為：14×1=14 bit，由此可得到該系統(tǒng)中BCH碼的參數(shù)為：

（1）碼元長度：n=512×8×4+14=16 398 bit

（2）檢驗位長度：r=14×1=14 bit

（3）糾錯能力：t=1 bit

（4）信息位長度：k=n-r=16 398-14=16 384 bit

因此BCH 碼為（2 062，2 048，1），其中校檢碼長度為14 bit。這樣既節(jié)省存儲的空間，又可以降低算法的復(fù)雜度，后續(xù)在解碼過程中來提升傳輸?shù)乃俾省?/p>

3? 結(jié)? 論

本文通過研究BCH碼的原理，在算法上進行優(yōu)化，滿足物聯(lián)網(wǎng)存儲系統(tǒng)并行、高效的應(yīng)用需求，降低MCU計算負(fù)載，結(jié)合Nand Flash存儲介質(zhì)的具體特點，用軟件實現(xiàn)BCH碼的編碼和解碼過程，通過反復(fù)的仿真實驗驗證，最終選擇BCH 碼為（2062，2048，1）的結(jié)構(gòu)，力求實現(xiàn)過程中糾錯速度最快、響應(yīng)最快。下一步將PC環(huán)境下實現(xiàn)的優(yōu)化BCH碼算法移植到MCU平臺上進行實際測試，對實際出現(xiàn)的問題進行細(xì)化，以滿足實際應(yīng)用場景中的各項指標(biāo)。

參考文獻：

[1] 王莞，魏敬和，于宗光.基于BCH糾錯算法的編解碼器設(shè)計與實現(xiàn) [J].電子技術(shù)應(yīng)用，2022，48（5）：42-46.

[2] 楊舒天，任勇峰，劉東海.基于可糾錯BCH碼的HOTLink的數(shù)據(jù)傳輸方案設(shè)計 [J].電子測量技術(shù)，2021，44（3）：27-31.

[3] 陳昭林，張晉寧，沈輝.基于BCH碼的NAND Flash糾錯算法設(shè)計與實現(xiàn) [J].電子測量技術(shù)，2017，40（3）：127-132.

[4] 雷水艷，焦繼業(yè)，陳亞南.一種優(yōu)化的BCH編解碼器的設(shè)計與實現(xiàn) [J].計算機與數(shù)字工程，2019，47（9）：2335-2338.

[5] 楊修.一種BCH類型糾錯算法的設(shè)計與實現(xiàn) [D].成都：電子科技大學(xué)，2019.

作者簡介：荊坤坤（1987—），女，漢族，安徽潁上人，講師，碩士研究生，研究方向：嵌入式系統(tǒng)。

收稿日期：2022-09-02

基金項目：2020年安徽城市管理職業(yè)學(xué)院自然科學(xué)研究項目（2020zkzd01）；2021年安徽城市管理職業(yè)學(xué)院自然科學(xué)研究項目（2021zrkx09）