BCH碼在物聯網存儲系統中的應用研究

荊坤坤 汪丹丹 朱倩 紀啟國 陳芳

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

關鍵詞：BCH碼；Nand Flash；物聯網；檢錯糾錯

中圖分類號：TP274? ? 文獻標識碼：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? 引? 言

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

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

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

綜上，針對上述問題，在MCU有限的資源條件下，通過技術的研究與創新，打破既有的Nand Flash技術壁壘，不帶來額外的成本開銷，實現Nand Flash存儲真正的落地，達到產品化標準，滿足物聯網應用場景日益增長的需求，具有很大的價值與意義。

1? 整體設計

1.1? BCH編碼的基本原理

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

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

64 B，并且每頁又分為4個子頁，即每個子頁為512 B+16 B，內部存儲結構如圖1所示。

1.2? MCU并行處理

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

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

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

1.4? 依據BCH碼的糾錯檢錯能力及時預判轉移數據

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

那本文設計的算法可以根據BCH碼檢錯糾錯的能力，提前預判數據的錯誤位數，在錯誤數據的位數即將超越糾錯上限時，及時將數據轉移到新的存儲單元，讓錯誤位數恢復到0，避免無法糾正數據的情況發生，從而提高系統讀寫數據的穩定性。

2? 設計仿真驗證

在PC環境下，對設計的BCH碼進行基本功能的仿真和驗證。

2.1? BCH碼算法的實現

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

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

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

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

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

功能：此函數接口能根據給定的數據和校驗碼，驗證數據是否發生了錯誤，該接口函數只能檢錯，不負責糾錯。

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

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

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

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

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

2.2? BCH碼算法的測試

根據優化的BCH碼算法，設計針對性的測試方案，具體的流程如圖3所示。

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

接下來，當BCH碼能否校驗通過后，系統會生成隨機數據。用隨機數據再生成校驗碼，為后續對數據的檢錯和糾錯做好準備。

最后，在數據的隨機位置，人為制造錯誤，通過調用BCH碼算法進行數據的檢錯和糾錯。

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

2.3? BCH碼算法的仿真結果分析

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

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

通過測試，我們發現糾錯能力為1 bit時，所需要的糾錯時間、檢錯時間和生成校驗碼的時間都是最短的，很好的滿足物聯網存儲系統對速度的要求，同時也節省了存儲空間。

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

（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。這樣既節省存儲的空間，又可以降低算法的復雜度，后續在解碼過程中來提升傳輸的速率。

3? 結? 論

本文通過研究BCH碼的原理，在算法上進行優化，滿足物聯網存儲系統并行、高效的應用需求，降低MCU計算負載，結合Nand Flash存儲介質的具體特點，用軟件實現BCH碼的編碼和解碼過程，通過反復的仿真實驗驗證，最終選擇BCH 碼為（2062，2048，1）的結構，力求實現過程中糾錯速度最快、響應最快。下一步將PC環境下實現的優化BCH碼算法移植到MCU平臺上進行實際測試，對實際出現的問題進行細化，以滿足實際應用場景中的各項指標。

參考文獻：

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

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

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

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

[5] 楊修.一種BCH類型糾錯算法的設計與實現 [D].成都：電子科技大學，2019.

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

收稿日期：2022-09-02

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