本文轉(zhuǎn)自公眾號,歡迎關注

Micrium全家桶之uC-CRC: 0x01 ECC (qq.com)

前言

我們這一篇來講講Micrium全家桶的uC-CRC。該代碼庫提供了CRC算法進行錯誤檢測EDC,使用HAMMING算法實現(xiàn)ECC錯誤糾正。ECC算法在NAND的TFL中使用。

下載代碼

git clone https://github.com/weston-embedded/uC-CRC.git

修改版本,去掉對uC-LIB,uC-CPU等的依賴,可以直接單獨使用,方便移植。

https://github.com/qinyunti/uC-CRC.git

文件介紹

│  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

添加代碼到自己的工程

添加uC-CRC\\Cfg\\Template\\crc_cfg.h

uC-CRC\\Source下所有文件到自己的工程目錄uC-CRC下

并配置頭文件包含路徑uC-CRC

依賴

修改代碼

注釋掉crc_util.h下的

#include < cpu.h >


#include < cpu_core.h >

改為

#include < crc_cfg.h >

注釋掉ecc.h下的

#include < cpu.h >


#include < cpu_core.h >

注釋掉ecc_hamming.h下的

#include < cpu.h >


#include < cpu_core.h >


#include < lib_def.h >


#include < lib_mem.h >

注釋掉edc_crc.h下的

#include < cpu.h >


#include < cpu_core.h >


#include < lib_def.h >

注釋掉

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 < string.h >

crc_cfg.h中實現(xiàn)以下依賴

/*
*********************************************************************************************************
*                                                 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”

調(diào)用以下接口

Hamming_Calc

Hamming_Chk

Hamming_Correct

詳見test.c

#include < stdio.h >
#include < stdint.h >
#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;
  }

  /* 打印原始數(shù)據(jù) */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");

  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\\r\\n",err);
    return -1;
  }
  printf("Hamming_Calc:ecc %#x %#x %#x %#x\\r\\n",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]);

/*
 *  1位數(shù)據(jù)錯誤
 */
  /* DATA注入錯誤 */
  printf("\\r\\n[DATA err test]\\r\\n");
  s_buffer[0] ^= 0x80;

  /* 打印錯誤數(shù)據(jù) */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");

  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\\r\\n",err);
    return -2;
  }
  printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d]\\r\\n",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);
  /* 打印修復后的數(shù)據(jù) */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");
  printf("Hamming_Correct:ecc %#x %#x %#x %#x\\r\\n",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]);
  printf("%s",s_err_str[err].str);
/*
 *  1位ECC錯誤
 */
  /* DATA注入錯誤 */
  printf("\\r\\n[ECC err test]\\r\\n");
  s_ecc[1] ^= 0x02;

  /* 打印錯誤數(shù)據(jù) */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");

  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\\r\\n",err);
    return -2;
  }
  printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d]\\r\\n",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);


  /* 打印修復后的數(shù)據(jù) */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");
  printf("Hamming_Correct:ecc %#x %#x %#x %#x\\r\\n",s_ecc[0],s_ecc[1],s_ecc[2],s_ecc[3]);
  printf("%s",s_err_str[err].str);
/*
 *  2位數(shù)據(jù)錯誤
 */
  /* DATA注入錯誤 */
  printf("\\r\\n[2DATA err test]\\r\\n");
  s_buffer[2] ^= 0x04;
  s_buffer[5] ^= 0x10;

  /* 打印錯誤數(shù)據(jù) */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");

  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\\r\\n",err);
    return -2;
  }
  printf("Hamming_Chk:loc B[%d].b[%d] B[%d].b[%d]\\r\\n",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);
  /* 打印修復后的數(shù)據(jù) */
  for(int i=0; i< sizeof(s_buffer)/sizeof(s_buffer[0]); i++)
  {
    if(i % 16 == 0)
    {
      printf("\\r\\n");
    }
    printf("%#x ",s_buffer[i]);
  }
  printf("\\r\\n");
  printf("Hamming_Correct:ecc %#x %#x %#x %#x\\r\\n",ecc[0],ecc[1],ecc[2],ecc[3]);
  printf("%s",s_err_str[err].str);
  return 0;
}

測試結(jié)果如下可以看到,1位的數(shù)據(jù)錯誤校正過來了,ECC編碼本身的1位錯誤認為是不可校正錯誤,兩位數(shù)據(jù)錯誤也是不可校正錯誤

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位數(shù)據(jù),至少要添加n位冗余位才能檢測出錯誤(只考慮只有1個bit錯誤的情況)。

m位數(shù)據(jù),n位冗余數(shù)據(jù)錯1位的情況有m+n種,還有一種情況是無錯。

需要用n位冗余位去標志是哪一位錯了,所以要滿足2^n >= m+n+1。

奇偶校驗

奇校驗:數(shù)據(jù)和校驗位一起,1的個數(shù)為奇數(shù)

偶校驗:數(shù)據(jù)和校驗位一起,1的個數(shù)為偶數(shù)

奇偶校驗只能發(fā)現(xiàn)奇數(shù)個位翻轉(zhuǎn),因為偶數(shù)個位翻轉(zhuǎn)奇偶性不變。

漢明碼

即奇偶校驗的升級,組合。

先根據(jù)2^n >= m+n+1計算需要多少個校驗位,

然后確認校驗位的位置在2^n索引位上(索引從1開始)。

比如7位數(shù)據(jù)需要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 5 7 9 11, 將對應數(shù)據(jù)位奇校驗,放在2^0校驗位

將bit1是1的劃分為一組 0010 0011 0110 0111 1010 1011

即2 3 6 7 10 11, 將對應數(shù)據(jù)位奇校驗,放在2^1校驗位

將bit2是1的劃分為一組 0100 0101 0110 0111

即4 5 6 7, 將對應數(shù)據(jù)位奇校驗,放在2^2校驗位

將bit3是1的劃分為一組 0100 0101 0110 0111

即8 9 10 11, 將對應數(shù)據(jù)位奇校驗,放在2^3校驗位

糾錯,如果2^0校驗位不對bit0寫1,如果2^1校驗位不對bit1寫1,得到的二進制數(shù)就是出錯位的的索引。

比如以上如果bit5翻轉(zhuǎn)了,索引5是在2^0和2^2組的所以,是101,即索引5的數(shù)據(jù)有錯。

漢明距離

在一個碼組集合中，任意兩個碼字之間對應位上碼元取值不同的位的數(shù)目定義為這兩個碼字之間的漢明距離d。例如：(00)與(01)的距離是1，(110)和(101)的距離是2。在一個碼組集合中，任意兩個編碼之間漢明距離的最小值稱為這個碼組的最小漢明距離。最小漢明距離越大，碼組越具有抗干擾能力,即差異越大,冗余越多。即編碼只用了一部分,剩余的空著,如果出現(xiàn)了錯誤則肯定是變成了空著的編碼。

比如兩位的編碼實際可以編碼為00 01 10 11,但是我們只用00代表A,10代表B,

那么收到01后,我們知道出錯了,那么是哪個出錯了呢，00變?yōu)?1需要變化1位,10變?yōu)?1需要變化2位,所以所以我們更傾向于是00變化了一位即是A出錯了,

所以我們可以認為00和01都代表A

10 11 都代表B

這樣實際就是用冗余來提高抗干擾能力,我們粗暴的發(fā)兩次也是冗余,但是冗余太多了浪費空間,所以可以選擇不冗余這么多,這個漢明距離d就是冗余的多少,d越大冗余越大,d越小冗余越小。

l當碼組用于檢測錯誤時，設可檢測e個位的錯誤，則d ≥ e + 1

l若碼組用于糾錯，設可糾錯t個位的錯誤，則 d ≥ 2 ? t + 1

即AB之間的距離至少是1才能區(qū)分AB, 剩余的空間2t劃分一半,靠近A的一半t認為是A,靠近B的一半t認為是B。

l如果碼組用于糾正t個錯，檢測e個錯，則d ≥ e + t + 1

NAND中的硬件ECC

這里以W25N01GVZEIG芯片為例,不同芯片略有差異

一個PAGE大大小是2112字節(jié)其中用戶區(qū)域2048字節(jié)+額外區(qū)域64字節(jié)

將PAGE的用戶區(qū)域和額外區(qū)域都分成4份即Sector,

則512字節(jié)用戶區(qū)域?qū)?6字節(jié)額外區(qū)域。

16字節(jié)額外區(qū)域如上圖

0- 1 :2字節(jié)位壞塊標記

2- 3 :2字節(jié)用戶數(shù)據(jù)II

4-7 : 4字節(jié)用戶數(shù)據(jù)I

8-D: 6字節(jié)前面Sector數(shù)據(jù)的ECC校驗值

E-F:4-D對應的10字節(jié)的ECC校驗值

問題:ECC for Sector 0本身有誤碼可以通過ECC for Spare檢測出來,但是如果ECC for Spare本身有誤碼呢?

芯片自帶的ECC校驗使能通過寄存器配置(有些型號是默認使能的)

寫數(shù)據(jù)時自動計算ECC并更新到64字節(jié)額外區(qū)域,讀數(shù)據(jù)時自動校驗ECC并進行校正,返回校正完后的正確值。

讀數(shù)據(jù)時可以讀狀態(tài)寄存器確認ECC狀態(tài)

NAND中的軟件ECC

256字節(jié)2048位,檢測1位錯誤理論上只需要12位校驗位即可,

2^12 >= 2048 + 12 + 1。

但是實際一半是糾正1位錯誤,檢測2位錯誤

所以d ≥ e + t + 1=4

漢明距離至少要是4.

NAND實際應用中是按照行列分別校驗的

按照一個字節(jié)8位x256字節(jié)

組成256x8,256行8列的矩陣

256行 16個校驗位

8列 6個校驗位

總共22位,3個字節(jié),剩余兩個bit未用放在高位

如下所示

參考

tn2963_ecc_in_slc_nand.pdf

samsung_ecc_algorithm_for_256b.pdf

Linux中的實現(xiàn)

參考以下鏈接,不再詳述

http://lxr.linux.no/linux+v2.6.27/drivers/mtd/nand/nand_ecc.c#L103

https://www.kernel.org/doc/html/latest/driver-api/mtd/nand_ecc.html

待辦

以上Micrium和Linux的實現(xiàn)實際都沒有實現(xiàn)檢測ECC碼自身錯誤的情況,都只能校正數(shù)據(jù)的1位錯誤,對于ECC碼本身錯誤一位認為是不可校正錯誤,這里后續(xù)可以考慮優(yōu)化。

總結(jié)

以上介紹了Micrium全家桶的uC-CRC組件,并修改成無其他依賴,比較好移植使用。其中的ECC在NAND中使用,所以重點進行了介紹。不僅僅介紹代碼庫的使用,同時也分析了原理,只有理論結(jié)合實踐才能真的用好。CRC部分下次可以單獨再講講。

審核編輯：湯梓紅