講講Micrium全家桶的uC-CRC算法
前言
我們這一篇來講講Micrium全家桶的uC-CRC。該代碼庫提供了CRC算法進行錯誤檢測EDC,使用HAMMING算法實現ECC錯誤糾正。ECC算法在NAND的TFL中使用。
修改版本,去掉對uC-LIB,uC-CPU等的依賴,可以直接單獨使用,方便移植。
文件介紹
│ LICENSE │ NOTICE │ readme.md │ ├─Cfg │ └─Template │ crc_cfg.h │ ├─Ports │ ├─ARM │ │ └─IAR │ │ ecc_hamming_a.asm │ │ edc_crc_a.asm │ │ │ └─ARM-Cortex-M3 │ └─IAR │ ecc_hamming_a.asm │ edc_crc_a.asm │ └─Source crc_util.c crc_util.h ecc.h ecc_hamming.c ecc_hamming.h edc_crc.c edc_crc.h
| 文件 | 說明 |
| LICENSE/NOTICE/readme.md | LICENSE使用的APACHE-2.0 |
| crc_cfg.h | 配置文件 |
| ecc_hamming_a.asm |
使用匯編實現 Hamming_ParCalcBitWord_32 默認提供了ARM和ARM-Cortex-M3架構IAR編譯器的版本 crc_cfg.h中#defineEDC_CRC_CFG_OPTIMIZE_ASM_ENDEF_ENABLED時使用,默認不使 |
| edc_crc_a.asm |
使用匯編實現 CRC_ChkSumCalcTbl_16Bit CRC_ChkSumCalcTbl_16Bit_ref CRC_ChkSumCalcTbl_32Bit CRC_ChkSumCalcTbl_32Bit_ref 默認提供了ARM和ARM-Cortex-M3架構IAR編譯器的版本 crc_cfg.h中#defineEDC_CRC_CFG_OPTIMIZE_ASM_ENDEF_ENABLED時使用,默認不使用 |
| crc_util.c/h |
實現CRCUtil_PopCnt_32 算法來自于http://en.wikipedia.org/wiki/Hamming_weight |
| ecc_hamming.c/h | Ecc算法代碼 |
| edc_crc.c/h | Crc算法代碼 |
添加代碼到自己的工程
添加uC-CRCCfgTemplatecrc_cfg.h
uC-CRCSource下所有文件到自己的工程目錄uC-CRC下
并配置頭文件包含路徑uC-CRC
依賴
| 文件 | 內容 |
|
cpu.h cpu_core.h lib_def.h lib_mem.h |
CPU_BOOLEAN CPU_INT08U CPU_INT16U CPU_INT32U CPU_ADDR CPU_DATA CPU_SIZE_T CPU_WORD_SIZE_32 DEF_NO DEF_YES DEF_DISABLED DEF_ENABLED DEF_INVALID DEF_VALID DEF_OCTET_NBR_BITS DEF_BIT DEF_BIT_00~DEF_BIT_12 DEF_BIT_13 DEF_BIT_15 DEF_BIT_17 DEF_BIT_19 DEF_BIT_21 DEF_BIT_23 DEF_BIT_25 DEF_BIT_27 DEF_BIT_29 DEF_BIT_31 DEF_BIT_SET DEF_BIT_IS_SET CPU_SW_EXCEPTION MEM_VAL_COPY_GET_INT32U MEM_VAL_COPY_GET_INTU MEM_VAL_COPY_SET_INT32U Mem_Clr |
修改代碼
注釋掉crc_util.h下的
#include#include
改為
#include
注釋掉ecc.h下的
#include#include
注釋掉ecc_hamming.h下的
#include#include #include #include
注釋掉edc_crc.h下的
#include#include #include
注釋掉
ecc_hamming.c下的
Mem_Clr((void *)p_ecc, HAMMING_LEN_OCTET_ECC); /* Init ECC buf for err(s) (see Note #6). */
改為
memset((void *)p_ecc, 0, HAMMING_LEN_OCTET_ECC);
前面添加
#include
crc_cfg.h中實現以下依賴
/*
*********************************************************************************************************
* PORT
*
* Note(s) : (1) 以下添加依賴部分移植
*
*
*********************************************************************************************************
*/
/* ------------------ CPU WORD-ENDIAN ORDER ------------------- */
#define CPU_ENDIAN_TYPE_NONE 0u
#define CPU_ENDIAN_TYPE_BIG 1u /* Big- endian word order (see Note #1a). */
#define CPU_ENDIAN_TYPE_LITTLE 2u /* Little-endian word order (see Note #1b). */
#define CPU_CFG_ENDIAN_TYPE CPU_ENDIAN_TYPE_LITTLE
typedef unsigned char CPU_BOOLEAN; /* 8-bit boolean or logical */
typedef unsigned char CPU_INT08U; /* 8-bit unsigned integer */
typedef unsigned short CPU_INT16U; /* 16-bit unsigned integer */
typedef unsigned int CPU_INT32U; /* 32-bit unsigned integer */
typedef CPU_INT32U CPU_ADDR; /* CPU address type based on address bus size. */
typedef CPU_INT32U CPU_DATA; /* CPU data type based on data bus size. */
typedef CPU_ADDR CPU_SIZE_T; /* Defines CPU standard 'size_t' size. */
#define CPU_WORD_SIZE_32 4u /* 32-bit word size (in octets). */
/* ----------------- BOOLEAN DEFINES ------------------ */
#define DEF_NO 0u
#define DEF_YES 1u
#define DEF_DISABLED 0u
#define DEF_ENABLED 1u
#define DEF_INVALID 0u
#define DEF_VALID 1u
#define DEF_OCTET_NBR_BITS 8u
#define DEF_BIT(bit) (1uL << (bit))
/* ------------------- BIT DEFINES -------------------- */
#define DEF_BIT_00 0x01u
#define DEF_BIT_01 0x02u
#define DEF_BIT_02 0x04u
#define DEF_BIT_03 0x08u
#define DEF_BIT_04 0x10u
#define DEF_BIT_05 0x20u
#define DEF_BIT_06 0x40u
#define DEF_BIT_07 0x80u
#define DEF_BIT_08 0x0100u
#define DEF_BIT_09 0x0200u
#define DEF_BIT_10 0x0400u
#define DEF_BIT_11 0x0800u
#define DEF_BIT_12 0x1000u
#define DEF_BIT_13 0x2000u
#define DEF_BIT_15 0x8000u
#define DEF_BIT_17 0x00020000u
#define DEF_BIT_19 0x00080000u
#define DEF_BIT_21 0x00200000u
#define DEF_BIT_23 0x00800000u
#define DEF_BIT_25 0x02000000u
#define DEF_BIT_27 0x08000000u
#define DEF_BIT_29 0x20000000u
#define DEF_BIT_31 0x80000000u
#define DEF_BIT_SET(val, mask) ((val) = ((val) | (mask)))
#define DEF_BIT_IS_SET(val, mask) (((((val) & (mask)) == (mask)) && ((mask) != 0u)) ? (DEF_YES) : (DEF_NO))
#define CPU_SW_EXCEPTION(err_rtn_val) do {
;
} while (1)
#define MEM_VAL_COPY_GET_INT32U(addr_dest, addr_src) do {
CPU_INT08U *destptr = (CPU_INT08U *)(addr_dest);
CPU_INT08U *srcptr = (CPU_INT08U *)(addr_src);
(*((destptr) + 0)) = (*((srcptr) + 0));
(*((destptr) + 1)) = (*((srcptr) + 1));
(*((destptr) + 2)) = (*((srcptr) + 2));
(*((destptr) + 3)) = (*((srcptr) + 3)); } while (0)
#define MEM_VAL_COPY_GET_INTU(addr_dest, addr_src, val_size) do {
CPU_SIZE_T _i;
for (_i = 0; _i < (val_size); _i++) {
(*(((CPU_INT08U *)(addr_dest)) + _i)) = (*(((CPU_INT08U *)(addr_src)) + _i));
}
} while (0)
#define MEM_VAL_COPY_SET_INT32U(addr_dest, addr_src) MEM_VAL_COPY_GET_INT32U(addr_dest, addr_src)
測試
ECC
用戶代碼中#include ”ecc_hamming.h”
調用以下接口
Hamming_Calc
Hamming_Chk
Hamming_Correct
詳見test.c
#include#include #include "ecc_hamming.h" typedef struct { ECC_ERR err; char* str; }err_str; err_str s_err_str[]= { {ECC_ERR_NONE,"No error."}, {ECC_ERR_CORRECTABLE,"Correctable error detected in data."}, {ECC_ERR_ECC_CORRECTABLE,"Correctable error detected in ECC."}, {ECC_ERR_INVALID_ARG,"Argument passed invalid value. "}, {ECC_ERR_INVALID_LEN,"Len argument passed invalid length."}, {ECC_ERR_NULL_PTR,"Pointer argument passed NULL pointer."}, {ECC_ERR_UNCORRECTABLE,"Uncorrectable error detected in data."} }; uint8_t s_buffer[33]; uint8_t s_ecc[4]; int ecc_main(int argc, char* argv[]) { CPU_INT08U ecc[4]; ECC_ERR_LOC err_loc[2]={{0,0},{0,0}}; ECC_ERR err; for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { s_buffer[i] = i+1; } /* 打印原始數據 */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); CPU_SIZE_T len = (sizeof(s_buffer)/sizeof(s_buffer[0])); CPU_SIZE_T len_buf = (len / 32)*32; CPU_SIZE_T len_buf_ext = len % 32; CPU_INT08U* p_buf_ext = (CPU_INT08U *)s_buffer + len_buf; Hamming_Calc(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,&err); if(ECC_ERR_NONE != err) { printf("Hamming_Calc err:%d ",err); return -1; } printf("Hamming_Calc:ecc %#x %#x %#x %#x ",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]); /* * 1位數據錯誤 */ /* DATA注入錯誤 */ printf(" [DATA err test] "); s_buffer[0] ^= 0x80; /* 打印錯誤數據 */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); if(ECC_FAULT == Hamming_Chk(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,err_loc,sizeof(err_loc)/sizeof(err_loc[0]),&err)) { printf("Hamming_Chk err:%d ",err); return -2; } printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d] ",err_loc[0].LocOctet,err_loc[0].LocBit,err_loc[1].LocOctet,err_loc[1].LocBit); printf("%s",s_err_str[err].str); Hamming_Correct(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,&err); /* 打印修復后的數據 */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); printf("Hamming_Correct:ecc %#x %#x %#x %#x ",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]); printf("%s",s_err_str[err].str); /* * 1位ECC錯誤 */ /* DATA注入錯誤 */ printf(" [ECC err test] "); s_ecc[1] ^= 0x02; /* 打印錯誤數據 */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); if(ECC_FAULT == Hamming_Chk(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,err_loc,sizeof(err_loc)/sizeof(err_loc[0]),&err)) { printf("Hamming_Chk err:%d ",err); return -2; } printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d] ",err_loc[0].LocOctet,err_loc[0].LocBit,err_loc[1].LocOctet,err_loc[1].LocBit); printf("%s",s_err_str[err].str); Hamming_Correct(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,&err); /* 打印修復后的數據 */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); printf("Hamming_Correct:ecc %#x %#x %#x %#x ",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]); printf("%s",s_err_str[err].str); /* * 2位數據錯誤 */ /* DATA注入錯誤 */ printf(" [2DATA err test] "); s_buffer[2] ^= 0x04; s_buffer[5] ^= 0x10; /* 打印錯誤數據 */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); if(ECC_FAULT == Hamming_Chk(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,err_loc,sizeof(err_loc)/sizeof(err_loc[0]),&err)) { printf("Hamming_Chk err:%d ",err); return -2; } printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d] ",err_loc[0].LocOctet,err_loc[0].LocBit,err_loc[1].LocOctet,err_loc[1].LocBit); printf("%s",s_err_str[err].str); Hamming_Correct(s_buffer,len_buf,p_buf_ext,len_buf_ext,s_ecc,&err); /* 打印修復后的數據 */ for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++) { if(i % 16 == 0) { printf(" "); } printf("%#x ",s_buffer[i]); } printf(" "); printf("Hamming_Correct:ecc %#x %#x %#x %#x ",ecc[0],ecc[1],ecc[2],ecc[3]); printf("%s",s_err_str[err].str); return 0; }
測試結果如下可以看到,1位的數據錯誤校正過來了,ECC編碼本身的1位錯誤認為是不可校正錯誤,兩位數據錯誤也是不可校正錯誤
CRC
接口如下,下篇再單講
CRC_Open_16Bit CRC_WrBlock_16Bit CRC_WrOctet_16Bit CRC_Close_16Bit CRC_Open_32Bit CRC_WrBlock_32Bit CRC_WrOctet_32Bit CRC_Close_32Bit CRC_Reflect_08Bit CRC_Reflect_16Bit CRC_Reflect_32Bit CRC_ChkSumCalc_16Bit CRC_ChkSumCalc_32Bit
漢明碼
冗余位
假設有m位數據,至少要添加n位冗余位才能檢測出錯誤(只考慮只有1個bit錯誤的情況)。
m位數據,n位冗余數據錯1位的情況有m+n種,還有一種情況是無錯。
需要用n位冗余位去標志是哪一位錯了,所以要滿足2^n >= m+n+1。
奇偶校驗
奇校驗:數據和校驗位一起,1的個數為奇數
偶校驗:數據和校驗位一起,1的個數為偶數
奇偶校驗只能發現奇數個位翻轉,因為偶數個位翻轉奇偶性不變。
漢明碼
即奇偶校驗的升級,組合。
先根據2^n >= m+n+1計算需要多少個校驗位,
然后確認校驗位的位置在2^n索引位上(索引從1開始)。
比如7位數據需要4位校驗位,2^4 >= 7+4+1,一共11位,從1~11編號索引
寫為二進制
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011
將bit0是1的劃分為一組 0001 0011 0101 0111 1001 1011
即1 3 57 9 11, 將對應數據位奇校驗,放在2^0校驗位
將bit1是1的劃分為一組 0010 0011 0110 0111 1010 1011
即2 3 6 7 10 11, 將對應數據位奇校驗,放在2^1校驗位
將bit2是1的劃分為一組 0100 0101 0110 0111
即4 56 7, 將對應數據位奇校驗,放在2^2校驗位
將bit3是1的劃分為一組 0100 0101 0110 0111
即8 9 10 11, 將對應數據位奇校驗,放在2^3校驗位
糾錯,如果2^0校驗位不對bit0寫1,如果2^1校驗位不對bit1寫1,得到的二進制數就是出錯位的的索引。
比如以上如果bit5翻轉了,索引5是在2^0和2^2組的所以,是101,即索引5的數據有錯。
漢明距離
在一個碼組集合中，任意兩個碼字之間對應位上碼元取值不同的位的數目定義為這兩個碼字之間的漢明距離d。例如：(00)與(01)的距離是1，(110)和(101)的距離是2。在一個碼組集合中，任意兩個編碼之間漢明距離的最小值稱為這個碼組的最小漢明距離。最小漢明距離越大，碼組越具有抗干擾能力,即差異越大,冗余越多。即編碼只用了一部分,剩余的空著,如果出現了錯誤則肯定是變成了空著的編碼。
比如兩位的編碼實際可以編碼為00 01 10 11,但是我們只用00代表A,10代表B,
那么收到01后,我們知道出錯了,那么是哪個出錯了呢，00變為01需要變化1位,10變為01需要變化2位,所以所以我們更傾向于是00變化了一位即是A出錯了,
所以我們可以認為00和01都代表A
10 11 都代表B
這樣實際就是用冗余來提高抗干擾能力,我們粗暴的發兩次也是冗余,但是冗余太多了浪費空間,所以可以選擇不冗余這么多,這個漢明距離d就是冗余的多少,d越大冗余越大,d越小冗余越小。
l當碼組用于檢測錯誤時，設可檢測e個位的錯誤，則d ≥ e + 1
l若碼組用于糾錯，設可糾錯t個位的錯誤，則 d ≥ 2 ? t + 1
即AB之間的距離至少是1才能區分AB, 剩余的空間2t劃分一半,靠近A的一半t認為是A,靠近B的一半t認為是B。
l如果碼組用于糾正t個錯，檢測e個錯，則d ≥ e + t + 1
NAND中的硬件ECC
這里以W25N01GVZEIG芯片為例,不同芯片略有差異
一個PAGE大大小是2112字節其中用戶區域2048字節+額外區域64字節
將PAGE的用戶區域和額外區域都分成4份即Sector,
則512字節用戶區域對應16字節額外區域。
16字節額外區域如上圖
0- 1 :2字節位壞塊標記
2- 3 :2字節用戶數據II
4-7 : 4字節用戶數據I
8-D: 6字節前面Sector數據的ECC校驗值
E-F:4-D對應的10字節的ECC校驗值
問題:ECC for Sector 0本身有誤碼可以通過ECC for Spare檢測出來,但是如果ECC for Spare本身有誤碼呢?
芯片自帶的ECC校驗使能通過寄存器配置(有些型號是默認使能的)
寫數據時自動計算ECC并更新到64字節額外區域,讀數據時自動校驗ECC并進行校正,返回校正完后的正確值。
讀數據時可以讀狀態寄存器確認ECC狀態
NAND中的軟件ECC
256字節2048位,檢測1位錯誤理論上只需要12位校驗位即可,
2^12 >= 2048 + 12 + 1。
但是實際一半是糾正1位錯誤,檢測2位錯誤
所以d ≥ e + t + 1=4
漢明距離至少要是4.
NAND實際應用中是按照行列分別校驗的
按照一個字節8位x256字節
組成256x8,256行8列的矩陣
256行 16個校驗位
8列 6個校驗位
總共22位,3個字節,剩余兩個bit未用放在高位
如下所示
待辦
以上Micrium和Linux的實現實際都沒有實現檢測ECC碼自身錯誤的情況,都只能校正數據的1位錯誤,對于ECC碼本身錯誤一位認為是不可校正錯誤,這里后續可以考慮優化。
總結
以上介紹了Micrium全家桶的uC-CRC組件,并修改成無其他依賴,比較好移植使用。其中的ECC在NAND中使用,所以重點進行了介紹。不僅僅介紹代碼庫的使用,同時也分析了原理,只有理論結合實踐才能真的用好。CRC部分下次可以單獨再講講。
審核編輯：劉清
-
ECC
+關注
關注
0文章
97瀏覽量
20586 -
CRC算法
+關注
關注
0文章
15瀏覽量
8881 -
EDC
+關注
關注
0文章
8瀏覽量
3799
原文標題：Micrium全家桶之uC-CRC: 0x01 ECC
文章出處：【微信號：麥克泰技術，微信公眾號：麥克泰技術】歡迎添加關注！文章轉載請注明出處。
發布評論請先 登錄
相關推薦
Micrium全家桶之uC-FS: 0x02 NAND FTL算法原理詳解
Micrium全家桶之uC-FS: 0x01 NAND FTL
Micrium全家桶之uC-CRC: 0x02 CRC
這段CRC算法是什么意思
CRC算法原理及C語言實現
LTE系統的CRC校驗算法及DSP實現
嵌入式開發的crc算法知識精選
工商網監
評論