（电路与系统专业论文）nand+flash主控中bch编译码器的研究和asic实现.pdf

浙江大学硕士毕业论文n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 摘要 b c h 码是线性分组码的一种，具有强大的多比特随机错误纠正能力，在数 据存储领域有着广泛的应用，尤其是在以n a n df l a s h 为介质的数据存储系统中， 基于b c h 码的纠错设计至关重要。 本文在充分分析n a n df l a s h 存储结构特点及其文件系操作特性的基础上， 提出了按扇区编码和按码字存储的设计方案，为高性能b c h 编译码器的实现奠 定基础。文章从面积、速度和功耗三个方面着手，围绕b c h 编译码器的硬件设 计和实现进行了深入的分析和探讨。重点研究了b c h 译码器的结构和性能优化， 通过分析传统按页预取译码的不足，提出了分组预取译码的方法，以及适合于分 组预取译码的两级流水的b c h 译码器结构，大大提高了b c h 码的译码效率。 同时，对译码器的三个部件：伴随式计算、i b m 迭代和c h i e n 搜索电路，分别进 行了优化。最后，根据b c h 编译码器分时工作以及无错不译码的特点，提出了 动态门控时钟的低功耗设计方案，极大地降低了模块的功耗。 关键词：b c h 码，分组预取译码，低功耗，两级流水，并行 i i 浙江大学硕士毕业论文 n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 a b s t r a c t b c hc o d ei sal i n e a rb l o c kc o d e ，w i t hap o w e r m lm u l t i b i t 姗d o me 1 1 r o r c o n e c t i o nc a p a b i l i t y i ti sw i d e l ya p p l i e di nt h ef i e l do fd a t as t o m g e t h ed e s i g no f e r r o r - c o r r e c t i o nb a s e do nb c hi se s s e n t i a l ，e s p e c i a l l yf o rt h en a n df l a s hs t o m g e s y s t e m s a r e ra 1 1 a l y z i n gt h en a n df l a s hm e m o r ys t m c t u r ea n df i l es y s t e m ， t h e m e t h o do f c o d i n gb y s e c t o ra n d s t o r i n g i nc o d e w o r dw a s p r o p o s e d f b r h i 曲- p e r f o 珊a i l c ei m p l e m e n t a t i o no fb c hc o d e c a l la n a l y s i sa 1 1 d d i s c u s s i o no f i m p l e m e n t a t i o no fb c hc o d e ca u r eb a s e do nt h r e ef a c t o r s ：a r e a ，s p e e da n dp o w e r a n d m o s to fw o r ki sf o c u s e do nt h es t m c t u r ea n dp e r f o 砷a n c eo p t i m i z a t i o no ft h eb c h d e c o d e r ap r e f e t c h i n ga i l dd e c o d i n gi ng r o u pm e t h o dw a sp r o p o s e da r e ra i l a l y z i n g t i l et r a d i t i o n a lm e t h o d “p r e f e t c h i n ga i l dd e c o d i n gi np a g e ”，s ow a st h e t w o - p i p e l i n e d e c o d e rh a w a r ea r c h i t e c t l l r es u i t a b l ef o rt h en e wd e c o d i n gm e t h o d ，w h i c hg r e a t l y i n c r e a s e dt h ee m c i e n c yo fb c hd e c o d e a tt h es a m et i m e ，t h et h r e ec o m p o n e n t so f b c hd e c o d e r ：s y n d r o m ec a l c u l a t e ，i b mi t e r i a t i o n ，a 1 1 dc h i e ns e a r c hc i r c u i t ，、v e r e o p t i m i z e d a “a s t ，ad ) ，l l 锄i cc l o c kg a t i n gd e s i 印w a sp r o p o s e d ，b a s e do nt h ef a c tt h a t t h eb c hc o d e ra i l dd e c o d e rw o n t 、o r ka tt h es 锄et i m e ，a 1 1 dt h ed e c o d e rn e e d n t 、o r ki ft h e r ei sn oe n o ro c c u r s ，t or e d u c et h ep o w e rc o n s u l n p t i o no ft h em o d u l e k e y w o r d ： b c h c o d e ，p r e f e t c ha i l dd e c o d ei n 铲o u p ，l o wp o w e r ，t w o p i p e l i n e ， p a r a l l e l l l i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝望盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期：年月 日 学位论文版权使用授权书 本学位论文作者完全了解逝婆盘堂有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝鎏盘堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：年月 日 签字日期：年 月 日 浙江大学硕士毕业论文 n a n df i a s h 主控中b c h 纠错码的研究和a s i c 实现 致谢 首先，感谢我的导师沈海斌副教授。在这几年的学习和科学研究中，他给予 我的悉心指导和无私帮助。他那渊博的知识、认真负责的工作态度、刻苦专研的 工作精神给我留下了深刻的印象，一直激发我努力向上，必将对我以后的工作和 学习产生深远的影响。同时，深深感谢沈海斌老师在为人处事、工作作风上对我 的指导和教诲，使我受益匪浅。 同时，十分感谢实验室的严晓浪教授、吴晓波教授、史峥老师、何乐年教授、 罗晓华老师、张培勇老师、王国雄老师和其他老师在学习和工作期间对我的帮助， 十分感谢超大规模集成电路研究所给我提供了一个一流的学习和工作环境，十分 感谢周知名、陈超、蔡志翔、顾良、王艳芳等同学以及曹葵康、董文萧、周喜川 和陈武等师兄弟在学习、工作上的帮助。 最后，感谢我的父母、家人在生活上对我无微不至的照顾，在工作和学习上 对我的全力支持。 王杰 2 0 1 0 年1 月 浙江大学硕士毕业论文n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 1 绪论 随着数字信息时代的飞速发展，对大容量数据存储的需求呈现高速增长的趋 势。作为非易失性存储器之一的n a n df l a s h ，由于其高容量低成本的特点，逐 渐成为大容量数据存储的重要媒介之一，并得到了广泛的应用。随着n a n df l a s h 存储技术的发展，前向纠错码( f e c ：f o n a r de 玎o rc o r r e c t i o n ) 技术被引入， 用以提高存储数据的可靠性，纠错成为了n a n df l a s h 存储系统中必不可少的一 部分。 本章首先介绍了课题的背景及意义，然后简要介绍b c h 纠错码及其在 n a n df l a s h 中的应用，最后给出作者在攻读研究生阶段研究工作的内容和文章 的结构安排。 1 1 课题背景及意义 n a n df l a s h 又称铂决闪”，起源于2 0 世纪8 0 年代，是非易失性存储器的一 种。近年来，由于n a n df l a s h 高容量、低成本的特点，应用面渐广。几乎所有 的消费电子产品，如u 盘、m p 3 、m p 4 、数码相机还有手机等，都离不开n a n d f l a s h 。可以说，只要涉及到大容量数据存储的地方，就少不了n a n df l a s h 。2 0 0 7 年，随着s t a 系统地推出，r e a d yd r i v e 等硬盘加速特性地兴起，n a n df l a s h 开始进入p c 领域。而完全采用n a n df l a s h 作为存储介质的固态硬盘( s s d ) 也逐渐成为各个电子厂商的新宠，随着n a n df l a s h 容量的进一步增加和成本的 进一步降低，s s d 有望取传统硬盘( h d ) 而代之。未来n a n df l a s h 将继续在 p c 以及其他消费电子产品中扮演举足轻重的角色，所以针对n a n df 1 a s h 的相 关研究有着极其重要的意义。而n a n df l a s h 主控的设计是n a n df l a s h 相关研 究中十分重要的一个部分，它是联系n a n df l a s h 和各种电子系统的桥梁。一个 n a n df 1 a s h 主控至少包括命令处理单元、n a n df l a s h 接口和e c c 纠错系统三 个部分，其中e c c 纠错系统是保证n a n df l a s h 存储系统中数据可靠性的重要 部件。 由于n a n df l a s h 物理结构的特殊性，当数据存储到n a n df l a s h 上时，可 l 浙江大学硕士毕业论文 n a n df l 豁h 主控中b c h 纠锗码的研究和a s i c 实现 能产生个别的比特翻转，从而导致存储数据出错，所以为了提高数据的可靠性， 需要在存储之前对数据进行适当的编码，以保证当数据出错时，系统能将其纠正 回来。前向纠错( f e c ) 是存储系统中应用最多的一种纠错方式，常采用h a m m i n g 、 b c h 、r s 等线性分组码作为纠错码，来提高系统的数据可靠性。 早期的n a n df l a s h 基本都是s l c ( s i n g l el e v e lc e l l ，单层单元) 类型的， 工艺相对成熟，存储过程中数据出错的概率很小，所以采用h 锄m i n g 码作为e c c 纠错码，即可满足系统要求。后来随着n a n df l a s h 设计技术和工艺的进步， n a n df l a s h 从s l c 结构转变为m l c ( m u l t il e v e lc e l l ，多层单元) 结构，每个 存储单元上可以存储2 个甚至多个比特数据，比特位之间的影响变大，出错概率 增加，而且随着制程工艺达到3 2 l m l ，超深亚微米下的各种电荷效应进一步增加 了数据出错的可能性。所以，单比特纠错的h a m m i n g 码已经远远无法满足e c c 纠错系统的要求，取而代之的是能纠多比特错误的b c h 码和r s 码。介于n a n d f l a s h 中数据出错随机性的特点，能纠多比特随即错误的b c h 码更加适合n a n d f l a s h 的应用，主流n a n df l a s h 主控和s s d 主控设计厂商几乎都在他们的e c c 纠错系统中采用了b c h 码。 本文以n a n df l a s h 主控中的e c c 纠错系统为研究对象，着重研究b c h 码 的算法特点和a s i c 实现，从面积、速度和功耗等角度深入剖析b c h 编译码器 的结构设计和性能优化，本课题的研究对于设计拥有自主知识产权的高性能 b c h 码纠错芯片有着积极的意义。 1 2b c h 纠错码简介 b c h 码的发明人有三个：博斯( b o s e ) 、雷查德胡里( r a y c h a u d h u r i ) 和 霍昆格姆( h o c q u e n g h e m ) ，他们各自于1 9 5 9 和1 9 6 0 年分别提出了能纠正多个 随机错误的循环码的构造方法【i l ，后人因此以三人名字的首字母将其命名为b c h 码。b c h 码是迄今为止所发现的一类很好的线性纠错码。它纠错能力强，尤其 是在短和中等码长下，其性能接近于理论值，且构造方便，编码简单。 1 9 6 0 年，p e t e r s o n 从理论上解决了二进制b c h 码的译码算法，由此奠定了 b c h 码译码的理论基础。1 9 6 6 年，b e r l e k 锄p 利用迭代算法译b c h 码，从而大 大加快了b c h 码的译码速度，从实际上解决了b c h 码的译码问题。1 9 7 1 年， 2 浙江大学硕士毕业论文 n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 h e r b e r to b u r t o n 提出了无求逆的b e r l e k 锄p m a s s y 迭代算法【2 】 解决了迭代译 码算法中的求逆问题，进一步提高了b c h 码的译码效率。 b c h 码在数据存储和数据通信等领域有着广泛的应用，如以n a n df l a s h 为存储介质的固态硬盘s s d 、光纤通信系统以及d v b h 的t p s 等，都嵌入了基 于b c h 码的纠错系统，用以提高数据的可靠性。基于b c h 码的纠错系统由编 码器和译码器两部分构成，其中编码是由信息位计算得到校验和的过程，译码则 是由伴随式计算、错误位置多项式求解和c h i e n 搜索三个环节组成【1 1 。 随着n a n df l a s h 存储技术的发展，纠错成为n a n df l a s h 主控设计中必不 可少的一环。n a n df l a s h 的物理结构特性，导致其在使用过程中可能出现多比 特的随机错误，因而需要采用能纠多比特随机错误的b c h 码进行纠正。国内外 对b c h 码的研究多是面向通信领域的应用，而对于在n a n df l a s h 主控中的应 用研究较少，已有的研究3 】【4 】【5 1 中，b c h 编译码的实现方法大体上可以分为两种： 软硬件协同设计和纯硬件设计。 1 ) 软硬件协同设计方案【3 】 软硬件协同设计的核心是带特殊运算指令的嵌入式处理器，通过分析b c h 编译码算法，提取出其中的各种核心运算类型，然后将各运算部件用硬件实现， 并将其以特殊指令的方式添加到协处理器的指令集中。如此一来，所有的b c h 编译码过程就可以软硬件配合的方式实现。软硬件协同设计的方案通过核心运算 部件的复用，节省了部分硬件资源，但是嵌入式处理器核以及用于存储程序的 r o m 所带来的额外硬件开销，远比复用所节省的要多得多，所以事实上该方案 的硬件成本不降反升，另外由于采用软件的方式实现b c h 的编码和译码，编译 码速度过慢，而且容易造成c p u 负担过重，影响系统软件的执行效率，不适合 于n a n df l a s h 主控。 2 ) 纯硬件设计方案【4 】【5 】 纯硬件设计指的是b c h 的编码和译码过程全由硬件状态机控制，各个核心 运算部件也用硬件实现。根据运算部件硬件并行程度的不同，b c h 编译码器的 编译码速度千差万别。译码器的译码速度除了和运算单元的并行程度有关外，还 和译码器的结构相关。带流水结构的译码器【3 】比不带流水结构的译码器【4 1 的译码 速度要快2 到3 倍，而硬件开销却只增加了很少。所以在做b c h 编译码器设计 时，应充分考虑应用系统的需求，在硬件复杂度和时间复杂度之间进行平衡，选 浙江大学硕士毕业论文 n a n df i a s h 主控中b c h 纠错码的研究和a s i c 实现 择合适的运算部件并行程度和流水结构。 本文将在纯硬件设计方案的基础上，探讨高速率、低功耗和低硬件复杂度 的b c h 编译码器的设计实现，本课题的研究有助于丰富国内外对n a n df l a s h 主控中b c h 纠错码的应用研究，为设计高性能的硬件b c h 编译码器提供参考 和借鉴。 1 3 本文的主要研究内容和结构安排 本文以n a n df l a s h 主控中b c h 纠错码的a s i c 实现为研究对象，从数据 吞吐率、硬件复杂度以及功耗三个方面入手，研究高性能b c h 编译码器的硬件 结构设计。 在充分分析n a n df l a s h 存储结构特点以及文件系操作特性的基础上，提出 了按扇区编码和按码字存储的设计方案，按扇区编码可以满足兼容性的要求，同 时满足文件系统按扇区操作的特性；而按码字存储可以满足编译码过程按流水操 作执行的需求。根据这一方案设计的n a n df l a s h 主控的整体结构框图如图1 1 所示，包括n a n df l a s h 控制器、总线接口、寄存器配置模块、输入、输出缓存 和b c h 编译码器等6 个部分。其中，n a n df l a l s h 控制器负责解析来自总线端 的数据和命令，并按照n a n df l a s h 的接口时序要求将命令和数据传送给目标 n a n df l a s h 器件；寄存器配置模块实现对n a n df l a s h 主控中各类寄存器的配 置功能；输入输出缓存用于缓存来往n a n df l a s h 的数据，平衡b c h 编译码器 和总线m a s t e r 方的速率；b c h 编译码器是本文的研究对象，其内部结构框图如 图1 1 所示，由编码器、伴随式计算电路、无求逆b m 迭代模块、c h i e n 搜索电 路和两个单端s r a m 组成。 b c h 编码器的结构较为简单，但是设计过程比较复杂，因为传统的编码器 设计方法，需要通过一系列的矩阵运算来获取编码器的生成表达式，计算量大， 操作比较繁琐，为了简化编码器的设计，本文提出了一种新的编码器设计方法， 新方法不需要矩阵运算即可得到编码器的生成表达式，方便快捷，节省了设计时 间。 4 浙江大学硕士毕业论文 n a n df l a s h 主控中b c h 纠错码的研究和a s l c 实现 寄存器配置 l 单端r a ml n a n d。脚i ! 旧 日总 f 1 a s h 7 线 接 口 控制器 l 一 l 。l 。l l 、l l 一一 i 、| | 一”i 一 图1 1n a n df l a s h 主控整体结构图 b c h 译码器的结构设计和优化是本文研究的重点，在分析了传统按页预取 译码的不足后，提出了分组预取译码的方法，以及适合于分组预取译码的两级流 水的b c h 译码器结构，与按页预取译码相比，分组预取译码具有明显的优势。 同时，详细介绍了译码器的三个部件：伴随式计算电路、无求逆b m 迭代运算电 路和c h i e n 搜索电路的硬件结构和实现方法，并对设计进行了优化。 文章最后根据b c h 编译码器分时工作以及无错不译码的特点，提出了动态 门控时钟的低功耗设计方法，极大地降低了模块的功耗。 全文的结构安排如下。 第二章介绍b c h 纠错码的基本原理以及参数设计方法，详细地分析了 n a n df l a s h 的数据存储特点和文件系统特性，由此提出最适合于n a n df l a s h 存储系统的b c h 码参数。 第三章介绍并行b c h 编码器的设计原理和电路优化方法，首先介绍了传统 的b c h 编码器设计方法，然后提出一种新的相对简便的编码器设计方法，并经 硬件实现。 第四章介绍分组预取译码算法以及两级流水的b c h 译码器结构，并设计了 浙江大学硕士毕业论文n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 低复杂度的伴随式电路、i b m 迭代算法电路和c h i e n 搜索电路，从面积和速度两 个方面对b c h 译码器进行了优化，并给出了最终的实现结果。 第五章首先简要介绍各种低功耗设计方法，然后通过分析b c h 编译码器的 工作特点，提出了适合于b c h 编译码器的低功耗设计方案，并用p o w e rc o m p i l e r 工具对优化后的功耗进行了分析。 最后，对全文进行总结，并指出还有待于进一步研究的工作和开展下一步工 作的建议。 6 浙江大学硕士毕业论文 n a n df i a s h 主控中b c h 纠错码的研究和a s i c 实现 2 b c h 纠错码原理与设计 b c h 码是按比特处理数据的二进制码，能纠多比特的随机错误，通常可以 用生成多项式g ( x ) 的根描述。本章将在介绍b c h 码基本原理和n a n df l a s h 存储结构的基础上，探讨并设计适合于n a n df l a s h 主控应用的b c h 码。 2 1b c h 码基本原理 b c h 码的定义：给定任一有限域g f ( g ) 及其扩域g f ( g 脚) ，其中g 是素数 或素数的幂，m 为某一正整数，若码元取自g f ( g ) 上的一循环码，它的生成多 项式g ( x ) 的根合集r 中含有以下正j 个连续根： r 2 口，口”，口+ j 一2 ) 则由g ( 石) 生成的循环码称为g 进制b c h 码【1 1 。 设聊，o ) 和p f 分别是口“( f = 0 ，l ，万一2 ) 元素的最小多项式和级，则b c h 码 的生成多项式和码长分别为： g ( x ) = 三c n 彳( ，( x ) ，铂( x ) ，咯一2 ( x ) ) 以= 三聊( ，巳，e 舳) 如果生成多项式g 的根中，有一个g f ( 矿) 中的本原域元素，则疗= g 肌1 ， 称这种码长，z = g 肌一1 的b c h 码味本原b c h 码；否则，成为非本原b c h 码。g f ( g 朋) 中元素的级一定是g m 1 的因子，所以非本原b c h 码的码长也一定是g 册1 的因子。 前面介绍了q 进制b c h 码的定义，实际中，应用最多的是码元取自g f ( 2 ) 的二进制b c h 码。取朋严1 ，6 = 2 f + j ，并设是g f ( 2 m ) 的本原域元素，则由b c h 码的定义可知：若码以口，口2 ，口2 。为根，则二进制b c h 码的生成多项式为 g ( x ) = 三叫( 铂( x ) ，( x ) ，( x ) ) ( 2 1 ) 7 浙江大学硕士毕业论文 n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 式中，慨( x ) 是口f ( 1 f 2 r ) 的最小多项式，该b c h 码一定能纠t 个错误。 由于在特征为2 的g f ( 2 册) 域上，口2 的最小多项式和口的相同，所以式子2 1 也可以改写为： g ( x ) = c n 彳( ( x ) ，殇( x ) ，一l ( x ) ) ( 2 2 ) 因此，二进制b c h码以口，口3 ，口2 卜1 为根，码长为： 行= 三c m ( q ，巳，e 2 f _ 1 ) ，检验矩阵为： h = 口”一l ( 口3 ) 州 ( 口2 卜1 ) ”1 口”一2 ( 口3 ) ”2 ( 口2 卜1 ) ”2 2 1 1b c h 码编码原理 b c h 码的编码和一般的循环码的编码方法相同，都是由信息位经生成矩阵 计算得到码字的过程：c = m g ，其中c 为码字，g 为生成矩阵，m 为信息位。 由校验矩阵和码字的关系c h t = 0 ，可知g h t = o ，或者是h g t = o ，即由g 和h 的行生成的空间互为零空间，借助生成矩阵和校验矩阵的这一层关系，我们可以 推导得到生成矩阵。运用矩阵运算的方法实现b c h 码的编码是个相对繁冗的过 程，下面将从较为简单的“代数运算”的角度进行分析。 一般，( n ，k ) 循环码可以分为系统码和非系统码两种，所谓系统码，其结构 形式如图2 一l 所示，信息位和校验位分开，而非系统码不区分信息位和校验位， 工程实践中系统码应用最多，也是本节介绍的重点。 图2 1 系统码的结构形式 令信息位多项式为聊( x ) = x o + 码一+ + 一2 x 七- 2 + 一l ，假定生成多项 式为g ( x ) = 岛妒+ 品一+ + 岛廿一2 x ”七- 2 + 岛一纠x ”扣1 ，则非系统码的码字可由式子 2 4 计算得到： 口；矿 浙江大学硕士毕业论文n a n df 1 a s h 主控中b c h 纠错码的研究和a s i c 实现 c ( x ) = 肌( x ) g ( x ) = c i x o + q x l + + q 一2 一2 + c 。一l x ”一 ( 2 - 4 ) 区别于非系统码，我们令系统码的码字c ( x ) = 所( x ) + ，( x ) = g ( x ) g ( x ) ，其 中严力- 七，o ) 为校验位多项式，最高次为厂j 。由于厂( x ) = c ( x ) 一聊( x ) ，0 ) 的 最高次小于g o ) ，所以，( 力m o dg g ) = 如) 。将，( x ) = c ( x ) 一班( x p 7 两边对g ) 取 模，由于c ( x ) = g ( x ) g ( x ) ，c ( x ) m o d g ( x ) 一0 ，所以，( 工) = 一，刀( x ) x 7m o d g ( x ) 。 由此，可以知道系统码的码字表达式如下。 c ( x ) = ， ( x ) 石7 一，z ( x ) x 7m o d g ( x ) ( 2 5 ) 从式子2 5 可以看出，校验位是由一脚( x ) 对g 求模得到。又由于二进制 b c h 的码元都取自二元域g f ( 2 ) ，在二元域中减法操作等同于加法操作，因此 码字表达式也可以写成如式2 6 所示。 c ( x ) = ，竹( x ) x 7 + 聊( x ) x m o d g ( x ) ( 2 - 6 ) 从式2 6 可以看出，b c h 码的编码过程就是一次有限域的模乘运算 m ( x h m o dg ( x ) ，可以利用l f s r 电路实现。假设信息位按比特从低位逐位移入， 再假设某一时刻校验位多项式为：，；( z ) = + q x + 哆x 2 + q x 3 + + 七- l x ”七一1 。 那么下一时刻，当新的信息位m 什l 移入时，校验位多项式为： + l ( 工) = ( ，；( x ) x + ，+ 1 ) m o d g ( x ) = ( 吼+ q x + 呸x 2 + 吃x 3 + + 口n 一一l x ”一。一1 ) x m o d g ( x ) + ，吩“ = 口。一t l + ，珥+ l + ( 口o + g l 口n 县1 ) x + ( q + 9 2 q 卜k 1 ) 一+ + ( + 岛一t i q 卜k 1 ) x ”一七一1 编码器的l f s r 结构如图2 2 所示。 图2 2 利用l f s r 实现的编码器 9 浙江大学硕士毕业论文n a n df l 弱h 主控中b c h 纠错码的研究和a s i c 实现 2 1 2b c h 码译码原理 b c h 码的译码问题一直都是编码理论研究中的热点之一。自1 9 6 6 年 b e r l e k 锄p 提出迭代译码算法后，后人在b e r l e k 锄p 研究的基础上相继提出了 b e r l e k 锄p m a s s a y 迭代算法，和无求逆的b e r l e k 锄p m a s s a y 迭代算法【2 1 ，从实际 上解决了b c h 码的译码问题。由于迭代算法效率高速度快，因而得到广泛的应 用。 g 进制b c h 码的译码过程通常包括以下几步： 由接收到的系统码月( x ) 计算伴随式s ( x ) 。 根据伴随式s ( z ) 求解关键方程，求出错误位置多项式仃( x ) 和错误值多项 式国( 曲。 用c h i e n 搜索算法求解错误位置，同时求解错误值，以找出错误图样会( z ) 计算尺( 曲一会( x ) ：仑( 功，得到译码器的输出估码值字6 ( x ) ，如果e ( 功：e ( x ) 则译码正确，否则译码错误。 对于二进制b c h 码，由于信息位不是“1 ”就是“0 ”，当某一位出错时，只 要将其取反即可，因而二进制b c h 码的译码过程要简单一些。 由接收到得系统码尺( x ) 计算伴随式s ( 功。 根据伴随式s ( x ) 求解关键方程，以求出错误位置多项式盯( 功。 用c h i e n 搜索算法求解错误位置。 根据错误位置，将相应位置上的数据取反，即可得到正确的数据。 伴随式计算 假设c ( 砷是码字多项式，e ( x ) 是错误位置多项式，设e o ) = 芝q 工，其中 f1 ，若在第x 。位出错 铲 o ， 其他 接收到得码字多项式为：尺( x ) = c ( x ) + e ( 曲 每个多项式的系数都在g f ( 2 ) 上，设g ( 力的零点为届，屈，屈，厚，则有 l o 浙江大学硕士毕业论文 n a n df l 罄h 主控中b c h 纠错码的研究和a s i c 实现 尺( 局) = c ( 届) + e ( 屈) = e ( 局) 所以有r ( 局) ：e ( 屈) ：芝q ，产l ，2 ，厂。假设码c 能纠正t 个错误，c ) 是 f = o 码字多项式，假定口，口2 ，口2 是g ) 的零点，则有 c 7 ) = o ，= 1 ，2 ，2 ， 又令e 2 ，o z 刀一l ，f = l ，2 ，厅 ，= j 即错误出现在1 沈，五位。由于r ( x ) = c ( x ) + e ( x ) ，因此有r ) = e ) 。 若用极小多项式所缸) 除r ，余项为喇，令 r ( x ) = 吼( x ) ，张( x ) + ( x ) ， 七= l ，2 ，力 则有伴随式计算式：最= r ) = 咯 ) ， 七= 1 ，2 ，2 f 从前面的分析可知，求解伴随式分两个步骤： 1 ) 用相应的极小多项式肌删去除r o ) ，获得余项为吣) ； 2 ) 将口代入瓯= 咯 ) 七= l ，2 ，2 f 取出伴随式，伴随式的个数是纠错位 数的两倍。 求解错误位置多项式及关键方程 求解关键方程是b c h 译码中十分重要的一环，关于关键方程的详细推导和 论证过程，可以在很多文献【7 】中找到，这里不再详述。 现令错误位置多项式为： 仃( x ) = l + q x + 吒x 2 + 吒x 3 + + q ， 伴随式多项式： s ( _ ) c ) = l + 而x + x 2 + 邑x 3 + + ，x 2 。 则关键方程 缈( x ) = s ( x ) 仃( ) c ) = l + ( s + q ) x + ( 是+ q 而+ 吼) x 2 + ( 邑+ q + 墨+ ) x 3 + + ( 墨+ q 一l + + q ) 一+ ( 墨+ l + q 墨+ + q 岛) + 1 + = 1 + q x + 哆x 2 + 翻3 + + q 一+ q + l x 。+ 1 + 浙江大学硕士毕业论文 n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 由牛顿等式【1 】可知仃( x ) 和s ( x ) 的系数满足如下关系： 而+ q = 0 邑+ q 是+ 吒而+ 吧= 0 岛+ q & + 吒与+ 吧是+ 吼& + = 0 该步骤译码的任务就是借助牛顿等式求解出错误位置多项式的各项系数， 1 9 6 6 年b e r l e k 锄p 提出采用迭代运算求解牛顿等式，即著名的b e r l e k 锄p 迭代算 法，描述如下： s t e p l ：令一( x ) = l ，t l = o ，以l = l 1 仃o ( 石) = 1 ，o = 0 ，哦= 墨 s t e p 2 ：若妒0 ，则 仃川( 功= 仃”( x ) ，0 l = 乙 否则，求解仃”( x ) 前面的仃”( x ) ，以o ，并使m - k 达到最大。 c ，”1 ( x ) = c r 伽( x ) 一以。x ”一”c r ”( 砷 厶+ i = m a ) ( 厶，乙+ 刀一朋) 其中，不论以= o 或则以o ，都有 0 l = + 2 + + l 仃p “+ + + 2 一+ l 哎j d 式中，一“1 是多项式仃”( z ) 的一项系数。 b e r l e k 锄p 迭代算法提出后，得到了广泛的应用与研究，并在此基础上改进 演化出许多新的算法，如b e r l e k 锄p m a s s a y 算法，i n v e r s i o n l e s sb e r l e k 锄p m a s s a y 算法等。除采用b e r l e k 锄p 迭代算法求解关键方程外，还可以采用e u c l i d 迭代算 法，两者的区别在于：前者是基于自回归滤波器的综合原理求最短反馈连接多项 式仃( x ) 的代数迭代过程，而后者是基于多项式分解的求两多项式的最大公约式的 迭代过程阴，e u c l i d 迭代算法不在本文的研究范围之内，有意者可以参考文献 7 】。 c h i e n 搜索算法求解错误位置 得到错误位置多项式叮( z ) 之后，下一步的问题就是找出出错比特的所在位 置，也就是求解盯( 工) 的根。1 9 6 4 年，钱闻天提出了一个适合于工程实现的求解 浙江大学硕士毕业论文n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 错误位置多项式仃( 力根的方法一一c h i e n 搜索算法，并一直沿用至今。 设r ( 工) = o l x 州+ 一：z ”2 + + v + ，如果要检验第一位协l 是否错误，只要 确定口川是否是错误位置，也就是检验口巾- 1 ) 是否是仃( 功的根。将口巾- 1 ) = 口代入 口( 功，若口一川) 是盯( x ) 的根，则有： 仃( 口一”一1 ) = 盯( 口1 ) = l + q 口+ 口2 + 口3 + + 吼口= 0 。 所以，当得到错误位置多项式仃( x ) 后，要检验n 比特是否正确，只要计算 盯 ”) = l + q 口州+ 吒口2 + 口3 州+ + q 口7 川，如果盯 ”一) = o ，则该比特位 出错，否则该比特位正确。c h i e n 搜索算法的思想就是从位置口”1 开始检测，一 直到遍历完整个元素空间。 工程上，c h i e n 搜索的电路实现结构如图2 3 所示。 l a口2口3 口一1口 图2 3c h i e n 搜索电路图 c h i e n 搜索电路的工作流程如下： 1 ) 系数寄存器初始化，将仃( 功的t 个参数分别存入t 个寄存器中； 2 ) 在码字比特位从k l 开始依次移入之前，先计算q 口、c r 2 口2 、吒口3 q 口 的结果并保存在寄存器中，经求和器s u m 与“l ”一同求和，求和结果 取反后与移入的码字位进行异或，即完成对h 1 的纠错； 3 ) l 译码完成后，再进行一次相乘，此时保存在寄存器中的结果为仉口z 、 1 3 浙江大学硕士毕业论文 n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 吼( 口2 ) 2 、吒( 口2 ) 3 吒( 口2 ) ，并送入求和器与“l ”一起求和，对h 2 进行纠错； 4 ) 其他码元的纠错和( 2 ) 一样。 2 2b c h 码的参数设计 前面介绍了b c h 码的编码和译码的基本原理，本节将在分析n a n df l a s h 存储器特点及其应用环境的基础上，设计适合于n a n df l a s h 主控的b c h 码， 包括码长、纠错位数和存储区域划分等。 2 2 1n a n df l a s h 简介 n a n df l a s h 存储技术起源于2 0 世纪8 0 年代，属于快闪技术的一种。早期， n a n dn a s h 产品在业界没有实现互用性，缺少一个统一的厂商规范和特征标准， 这给n a n dn a s h 的应用带来极大的不便。2 0 0 6 年，i n t e l 联合s t 、m i c r o n 以及 h y l l i x 等n a n df l a s h 大厂，共同推出公开n a n df l a s h 接口标准，即o n f i1 o ， 意在统一n a n df l a s h 产品的业界标准。随后又于2 0 0 9 年推出了新的标准o n f i 2 0 ，进一步完善n a n df l a s h 的工业标准。目前o n f i 组织的成员已经扩展到6 0 多个，虽然作为n a n df l a s h 老大的s a m s u n g 以及t o s h i b a 没有加入到o n f i 组织 中来，但是这并不能阻挡n a n dn a s h 工业标准的统一步伐，而事实也证明o n f i 的n a n df l a s h 标准和s 锄s u l l g 独家定制的n a n dn a s h 标准之间有着许多的相 似之处，而差异仅表现在个别命令和性能的有所不同。 根据o n f i 标准的规定，n a n df l a s h 将采用统一的异步接口或同步接口，如 图2 4 所示，每一块n a n df l a s h 芯片将同时支持异步接口( o n f i1 o ) 和同步接 口( o 曲2 o ) 。无论是采用同步还是异步接口工作模式，大部分的信号定义是相同 的，如8 位宽的数据线i o ( d q ) 供数据、地址和命令线复用，c l e 为命令锁存 信号，a l e 为地址锁存信号，w p 为写保护信号，刚b 为空闲忙信号，c e 为片 选信号；不同的地方仅有三处：在异步接口工作模式下，有w e n 写使能信号和 砌读使能信号，这两个信号分别对应同步接口工作模式下的c l k 时钟信号和 w 瓜读写控制信号，另外同步接口还多了一个数据同步源信号d q s ，用于数据 浙江大学硕士毕业论文 n a n df l a s h 主控中b c h 纠错码的研究和a s i c 实现 的同步。根据o n f i 标准的规定，n a n df l a s h 的基本操作有：页写( p a g ep r o g r a i l l ) 、 页读( p a g er e a d ) 、块擦除( b l o c ke r a s e ) 、读状态( s t a t u sr e a d ) 、读i d 值( i dr e a d ) 和复位( n a s hr e s e t ) 等，其中数据存取相关的操作是页读、页写和块擦除三个操 作，从操作名上不难看出，n a n df l a s h 的读写操作都是以页为单位进行的，而 擦除操作是按块进行的，这种独特的操作方式是由n a n df l a s h 的结构特点决定 的。 a s y n c h r o n o u sn a n df l a s hi n t e r r f i a c e s y n c h r o n o u sn a n df l a s hi n t e r f a c e c ea l e w e nc l e r e n n a n d f l a s h r b w p i o 【7 ：o 】 c ea l e c l kc l e w 瓜 n a n d f 1 a s h r b w p d q sd q 【7 ：0 】 图2 - 4n a n df l a s h 接口 统一的n a n df l a s h 的存储结构如图2 5 所示，每个d e v i c e 由多个b 1 0 c k 组 成，b l o c k 是擦除操作的基本单元，每个b l o c k 由3 2 个页( p a g e ) 组成，p a g e 是n a n df l a s h 中最小的存储单位，每页的大小有5 1 2 b y t e s + 1 6 b ”e s 、 2 k b + 6 4 b y t e s 、4 k b + l2 8 b ”e s 和8 k b + 2 5 6 b y t e s 等多种，n a n df l a s h 读写操作 都是以页为