一种反熔丝FPGA可实现的闪存坏块管理算法

莫 凡,陈晓飞,陆一波

(上海卫星工程研究所，上海 200240)

0 引 言

Nand闪存(下称“闪存”)的坏块管理算法自其被广泛应用以来一直是研究的热点。这些算法大多是针对通用的应用需求设计，一般不采用顺序存储的存储结构。这些算法往往需要较高性能的元器件实现，针对航天应用需求和空间运行环境的设计并不多[1-3]。在航天领域存在大容量数据缓冲器的应用需求，如：卫星在接收站范围外发生数据，接收站范围内接收数据。在此应用背景下，采用顺序循环存储的存储结构具有控制逻辑简单特点，对实现它的逻辑元器件的性能指标要求较低，具有高可靠低性能特点的适应空间环境的元器件较容易实现。与顺序循环存储的存储结构相对应得坏块管理算法相对有着自身的特点。本文介绍了一种航天适用的基于顺序循环存储的存储结构的坏块管理算法。本文简述了与算法相关的闪存功能，概述了顺序循环存储的存储结构，详述了该算法的原理，给出了实现元器件和仿真。

1 闪存功能简述

闪存的存储空间由块组成，块由页组成[4]。以一块型号为K9F4G08U0A三星4Gbit的闪存为例，总共4096个块，每块有2048页。闪存擦除以块为单位，擦除后块内所有位都为1。写入时，先写入闪存中的缓存，缓存以页为单位，闪存在收到确认命令后，闪存将缓存中的内容写入页中，写入的时候只能将1变为0，这一过程称作页编程。一次块擦除后，每一页的编程次数不能超过4次，块内相邻两次编程地址必须连续。一片4G 闪存有4096个块，每个块有2048个页，每页2112字节。每页分为4个扇区，同时又分为主区和冗余区。页的结构如表1所示。

表1 页结构

如表所示，每个扇区528个字节，主区512个字节，冗余区16字节。存储在每个扇区中的数据发生1bit的错误是正常现象，因此存入闪存的原始数据需要与相应的校验码一起存储。主区一般用来存储输入的原始数据，冗余区一般用来存储与主区数据对应的校验码和其他附加信息。

2 存储结构

数据存储以块为单位，0号块存储块地址指针，一次数据存储结束后，该指针指向下一次数据写入的块。除0号块以外的块用于数据存储，数据存储采用顺序循环的方式。没有坏块管理存储过程如图1所示。

图1 存储结构流程图

如图所示，接收到数据采集命令后，控制逻辑要读取存储在0号块中的写指针存入控制逻辑中的寄存器。控制逻辑总是将输入的需要存储的数据写入写指针指定的块中。数据存满一个块即将要存入下一块时，需要更新寄存器中的写指针。当写指针指向存储区域最后一个块时，更新后指向存储区域的第一个块。

3 算法原理

常见的闪存除了0号块以外的其他块，不保证无坏块。所谓的“坏块”，并非完全失效的块，大多数情况下只是部分失效或不稳定。确定某块为坏块主要有三种途径：出厂时的标记；执行擦除命令后来自于闪存的表明擦除成功与否的信号反馈；执行页编程命令后来自于闪存的页编程成功与否的信号反馈。坏块管理算法的思路如下：

(1)使用RAM作为缓存，如果块写入过程发生坏块现象，跳过该块，将原本存入该快的数据重新从RAM中读出存入循环相邻的下一个有效块中。

(2)1代表坏块，0代表有效块。考虑到闪存存储会发生1位的错误，采用三模冗余的纠错算法，任取一个字节中的三位用作坏块标记，这里取一个字节中的低3位。

有效的块在页的冗余区写入标记，坏块维持擦除后的状态不变。页编程失败，该页如果不是该块的最后一页， 跳过该块，寻找循环相邻的下一个有效块。如果该页是块中的最后一页，擦除该块，然后跳过该快，寻找循环相邻的下一个有效块。

(3)检测坏块时检测最后一页的标记。虽然概率不大，但是仍然会发生未将最后一页冗余区标志擦成1的情况。这种情况对于写入的影响不大，因为在写该块时需要先擦除，擦除失败将跳过该块。但是这对读数据影响较大，如果不作处理，坏块中的无效数据会干扰到有效块中有效数据的使用。解决办法是采用循环流水编码的方法，K9F4G08U0A共有4096个块，0号块用作记录块指针，用作循环存储的块有4095个，12比特长度即可标记。循环流水编码并不一定需要标记每一个块，循环流水编码的码长越长，没有擦除成功的坏块中的循环流水编码与有效块中的循环流水编码连续的概率就越小，这里采用长度为两个字节16位的循环流水编码。考虑到1比特的存储错误，采用三模冗余纠错，实际存三份，占用6个字节。循环流水编码、冗余码均写入每一页第一扇区的冗余区。每一扇区主区512字节，512字节的2位检测1位纠错汉明码长度为3字节。第一扇区冗余区共使用10字节。第一扇区冗余区的结构如图2所示。

图2 第一扇区冗余区结构

图3给出了试图写入n号块的流程图，是图1中“将数据写入写指针寄存器指向的块”和“写指针寄存器以以存储空间大小为模自增1”步骤的修改和细化。

图3 坏块管理算法

如图中n+1指的是以存储空间为模的自增1运算。如图所示，最后一页页编程失败后需要块擦除，在擦除成功的情况下，能够确保坏块标记为1。回放地址时，根据设置的回放地址上限和下限，将该段地址中的数据回放。回放数据的流程图如图4所示。

图中的“自增1”和“增加到下一个块的第1页”是以存储空间为模的自增1。闪存厂商在闪存出厂前会对闪存进行检测，在坏块的第1页或第2页的冗余区第1个字节写入非零值，有效块模块处于擦除后的状态。新出厂的闪存需要先进行初始化，然后才能用来适用本文描述的算法。初始化执行的操作有：将指向第一有效块的写指针写入0号块；在有效块的最后一页的冗余区的响应位置写入有效块标记。

4 实现与仿真

4.1 选用元器件

选用适应空间环境的元器件实现，主要元器件如表2所示。

表中的第一项是一个 常见的ACTEL公司的反熔丝7.2万门的FPGA。常见的RAM型的FPGA容量动辄几百万门，但是较少有抗辐射指标，抗单粒子翻转性能远不如反熔丝型的FPGA。

4.2 选用依据

将本文的算法采用verilog硬件设计语言实现，使用Synplify综合工具综合，结果如表3和表4所示。

从表中可以看出，本算法占用A54SX72A资源不多，采用16M时钟，时序余量较大。

4.3 仿真

本算法涉及的纠错设计有三处：坏块标记、原始数据纠错。前者采用三模冗余算法，后者采用汉明码。图5给出了一处检测坏块标记的仿真波形，仿真软件采用的是modelsim。

如图所示，Ale为地址锁存信号；Cle为命令锁存信号；FlashCeBar为片选信号，低电平有效；FlashReBar为读使能信号；FlashWeBar为写使能信号；FlashIo为8位闪存数据输入输出端口，详细说明参见参考文献[4]。图中光标的停留位置为读出坏块标记的时刻，此时FlashIO上闪存送出的是0x01。有效块的标记是0x00，送出0x01是仿真了发生1位错误的情况，经三模冗余纠错并进行判断，该块为有效块，随后的一组波形是块擦除操作波形，擦除成功后该块可进入写入操作。

图4 数据回放流程图

表2 核心元器件

表3 FPGA资源使用

表4 静态时序分析

5 结 语

本文提出的算法是以块为单位基于循环顺序存储的存储结构，在这种存储结构中，时间上顺序存储的块在块存储空间上也顺序。在没有坏块的情况下，时间上相邻存储的块在存储空间上也是循环相邻的。存储结构实际上是顶层的数据结构，存储结构以下的层次是块，块中的数据结构的维护采用RAM。

大量文献研究的坏块管理算法往往针对以块为单位块与块之间的数据关系不确定的情况。一般情况下，这类坏块管理算法需要维护一张块存取表(Block Access Table, BAT)(以下称这种方法为BAT法)，BAT中不仅记录坏块信息而且记录块与块之间的数据关系。存储BAT表的存储介质往往是读写最为频繁，BAT失效意味着整个存储模块的失效，BAT如果保存在闪存中，磨损均衡和坏块管理的算法的逻辑复杂，往往需要较高性能的CPU实现。

本文描述的坏块管理算法的应用范围不局限于顶层数据结构为以块为单位循环存储的情况，主要适用范围分以下几种类型：

图5 坏块标记读取仿真

(1)顶层为连续多块组合的循环顺序存储数据结构，次顶层为非顺序存储数据结构。次顶层的数据模块实现的方式有两种：一种是将次顶层数据模块作为一个整体读入RAM中进行维护，维护完毕存入闪存；另一种是直接在闪存上进行维护。第一种方式需要足够大的内存，第二种方式增加了闪存控制逻辑的复杂度。

(2)顶层为独立数据模块，次顶层为循环顺序存储数据结构。这种方式可采用分区的方法实现。

(3)顶层为非独立且非循环顺序存储数据结构。实现方法采用类型1的次顶层实现方法。

(4)上述几种类型的嵌套。

类型1的第一种实现方法、类型2实现逻辑较为简单，适合使用本文描述的算法。类型1的第二种方法以及类型3的实现逻辑的复杂程度与非独立且非循环顺序存储的具体数据结构有关，适用BAT法还是本文描述的算法视具体数据结构而定。类型4根据嵌套的具体情况，在一定的嵌套层次中适用本文描述的算法。

航天器中存在的大规模存储应用需求主要是用来实现数据缓冲和回放，多台设备的缓冲回放可以采用类型2所对应的存储结构。另一方面，航天用的反熔丝FPGA具有防辐射指标高性能低，本文描述的算法控制逻辑简单可在反熔丝FPGA上实现的特点更好的满足了航天器安全性和可靠性的指标要求。