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

摘? 要：隨著物聯(lián)網(wǎng)設(shè)備對存儲容量的需求不斷擴(kuò)大，Nand Flash作為主流的存儲設(shè)備在物聯(lián)網(wǎng)系統(tǒng)中應(yīng)用非常廣泛，為了保證數(shù)據(jù)的準(zhǔn)確性，選擇一種性能良好的糾錯(cuò)算法至關(guān)重要。目前最為常用的是BCH碼，由于嵌入式存儲系統(tǒng)MCU沒有能夠?qū)崿F(xiàn)BCH編解碼的硬件控制器，需要用軟件來實(shí)現(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)；檢錯(cuò)糾錯(cuò)

中圖分類號：TP274? ? 文獻(xiàn)標(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è)控制、智慧城市、智能可穿戴等多個(gè)領(lǐng)域。隨著應(yīng)用場景日益復(fù)雜，功能逐漸多樣化，圖像、音視頻數(shù)據(jù)不斷增大，物聯(lián)網(wǎng)設(shè)備對存儲容量的需求不斷擴(kuò)大，傳統(tǒng)MCU片內(nèi)Flash外和少量外部Nor Flash，已經(jīng)無法滿足需求。價(jià)格低廉、容量大的Nand Flash成為越來越受青睞的存儲方案。

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

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

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

1? 整體設(shè)計(jì)

1.1? BCH編碼的基本原理

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

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

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

1.2? MCU并行處理

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

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

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

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

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

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

2? 設(shè)計(jì)仿真驗(yàn)證

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

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

用代碼實(shí)現(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ù)，生成校驗(yàn)碼。

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

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

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

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

返回值：0代表成功，-1代表失敗（表示有錯(cuò)誤位存在）。

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

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

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

2.2? BCH碼算法的測試

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

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

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

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

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

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

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

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

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

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

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

（2）檢驗(yàn)位長度：r=14×1=14 bit

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

參考文獻(xiàn)：

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

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

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

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

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

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

收稿日期：2022-09-02

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