CN102455975A - 用来进行数据整形的方法以及其记忆装置及控制器 - Google Patents

Abstract

本发明涉及一种用来进行数据整形的方法，该方法应用于一闪存的控制器，该闪存包含多个区块，该方法包含有：依据原始数据与多个整形码进行一写入最佳化运作，以产生对应于一格子图的追溯信息作为旁信息；以及依据该旁信息动态地选择该些整形码中的至少一整形码，以对该原始数据进行数据整形。本发明另提供相关的记忆装置及其控制器。本发明还涉及相关的记忆装置及其控制器。通过适当地设计数据整形模块/数据重获模块，辅以相关的数据流控制，本发明能针对控制器所存取的数据来进行妥善的数据型样管理，以减少错误的发生；另外，本发明不会增加许多额外的成本，甚至比相关技术更能节省成本。

Description

用来进行数据整形的方法以及其记忆装置及控制器

技术领域

本发明涉及于闪存(Flash Memory)的存取(Access)，更具体地说，涉及一种用来进行数据整形(Data Shaping)的方法以及相关的记忆装置及其控制器。

背景技术

近年来由于闪存的技术不断地发展，各种可携式记忆装置(例如：符合SD/MMC、CF、MS、XD标准的记忆卡)或具备闪存的固态硬盘(Solid State Drive，SSD)被广泛地实施于诸多应用中。因此，这些记忆装置中的闪存的存取控制遂成为相当热门的议题。

以常用的NAND型闪存而言，其主要可区分为单阶细胞(Single LevelCell，SLC)与多阶细胞(Multiple Level Cell，MLC)两大类的闪存。单阶细胞闪存中的每个被当作记忆单元的晶体管只有两种电荷值，分别用来表示逻辑值0与逻辑值1。另外，多阶细胞闪存中的每个被当作记忆单元的晶体管的储存能力则被充分利用，采用较高的电压来驱动，以透过不同级别的电压在一个晶体管中记录两组(或以上)位信息(00、01、11、10)；理论上，多阶细胞闪存的记录密度可以达到单阶细胞闪存的记录密度的两倍，这对于曾经在发展过程中遇到瓶颈的NAND型闪存的相关产业而言，是非常好的消息。

相较于单阶细胞闪存，由于多阶细胞闪存的价格较便宜，并且在有限的空间里可提供较大的容量，故多阶细胞闪存很快地成为市面上的可携式记忆装置竞相采用的主流。然而，多阶细胞闪存的不稳定性所导致的问题也一一浮现。为了确保记忆装置对闪存的存取控制能符合相关规范，闪存的控制器通常备有某些管理机制以妥善地管理数据的存取。

依据相关技术，有了这些管理机制的记忆装置还是有不足之处。举例来说，使用者可能基于其使用习惯而不断地写入具有某些特定数据型样的数据，而这些特定数据型样特别容易造成错误(例如：写入错误、读取错误...等)；虽然在记忆装置中设置有随机函数发生器(Randomizer)来调整数据以期解决这样的问题，却由于传统的低成本设计，以致调整后的数据不够随机。另外，一旦闪存的数据储存样态有特定的限制，可能发生硬件资源不足与增加成本之间的取舍(Trade-off)的问题。因此，需要一种新颖的方法针对该控制器所存取的数据来进行妥善的数据型样管理，以减少错误的发生。

发明内容

本发明要解决的技术问题在于，针对现有技术的上述在多阶细胞闪存中不断地写入特定数据型样的数据时易造成错误的缺陷，提供一种用来进行数据整形(Data Shaping)的方法以及相关的记忆装置及其控制器，以解决上述问题。

本发明的另一目的在于提供一种用来进行数据整形的方法以及相关的记忆装置及其控制器，以抑制数据错误。

本发明的另一目的在于提供一种用来进行数据整形的方法以及相关的记忆装置及其控制器，以便在可供用来进行数据整形的整形码(ShapingCode)的数量甚多的状况下，仍可以迅速地筛选适用的整形码，且不需要实施庞大的硬件架构。

本发明解决其技术问题所采用的技术方案之一是：构造一种用来进行数据整形的方法，该方法应用于一闪存(Flash Memory)的控制器，该闪存包含多个区块，该方法包含有：依据原始数据与多个整形码进行一写入最佳化(Program Optimization)运作，以产生对应于一格子图(Trellis Diagram)的追溯(Trace Back)信息作为旁信息(Side Information)；以及依据该旁信息动态地选择该些整形码中的至少一整形码，以对该原始数据进行数据整形。

上述本发明所述的方法，其中该格子图的各级(Stage)中的每一级包含多个子路径；以及每一级的该些子路径分别代表该些整形码。

上述本发明所述的方法，其中依据该原始数据与该些整形码进行该写入最佳化运作以产生对应于该格子图的追溯信息作为该旁信息的步骤另包含：

寻找该格子图中的一最佳化路径，并产生该最佳化路径中相对于各级的各个子路径的子路径追溯信息作为该旁信息的至少一部分，其中该最佳化路径的终点为该格子图的最后一级的各个结果状态中的一最佳状态，且该旁信息包含代表该最佳状态的终点信息。

上述本发明所述的方法，其中依据该原始数据与该些整形码进行该写入最佳化运作以产生对应于该格子图的追溯信息作为该旁信息的步骤另包含：

针对该格子图的各级，进行对应于维特比(Viterbi)算法的相加、比较、与选择(Add Compare Select，ACS)运作，以产生该些级中的至少一级的各个结果状态的追溯指示器(Trace Back Indicator)并寻找该格子图的该最后一级的该些结果状态中的该最佳状态，其中该旁信息中的该子路径追溯信息包含该些追溯指示器中的至少一部分。

上述本发明所述的方法，其中该原始数据包含分别对应于该格子图的各级(Stage)的部分数据(Partial Data)；以及依据该原始数据与该些整形码进行该写入最佳化运作以产生对应于该格子图的追溯信息作为该旁信息的步骤另包含：

针对对应于一特定级的特定部分数据，计算分别对应于至少两个整形码的至少两个分支量度值(Branch Metric)；以及

累计该些级的多个分支量度值中的至少一部分，以进行该写入最佳化运作。

上述本发明所述的方法，其中依据该旁信息动态地选择该些整形码中的该至少一整形码以对该原始数据进行数据整形的步骤另包含：

针对该原始数据中关于该闪存中的一记忆单元的最高有效位进行数据整形，而非对该原始数据中关于该记忆单元的全部位进行数据整形。

上述本发明所述的方法，其中于该格子图的各级(Stage)当中，任一级内对应于特定状态转换的一子路径以及另一级内对应于相同状态转换的子路径均代表该些整形码当中的同一整形码。

上述本发明所述的方法，其中该原始数据包含分别对应于该格子图的各级(Stage)的部分数据(Partial Data)；以及依据该旁信息动态地选择该些整形码中的该至少一整形码以对该原始数据进行数据整形的步骤另包含：

针对对应于一特定级的特定部分数据，依据该旁信息中的至少一部分于该些整形码中选出一特定整形码，以进行对应于该特定部分数据的数据整形。

上述本发明所述的方法，其另包含有：

将该旁信息中的至少一部分或其代表信息储存于该闪存，以供该原始数据之重获(Recovery)之用。

上述本发明所述的方法，其另包含有：

于一读取运作期间，自该闪存取得该旁信息中的该至少一部分或其代表信息，并据以重获(Recover)该原始数据。

本发明解决其技术问题所采用的技术方案之二是：构造一种记忆装置，其包含有：一闪存，该闪存包含多个区块；以及一控制器，用来存取(Access)该闪存以及管理该多个区块，并且另针对该控制器本身所存取的数据来进行数据整形。另外，该控制器依据原始数据与多个整形码进行一写入最佳化运作，以产生对应于一格子图的追溯信息作为旁信息。此外，该控制器包含有至少一数据整形模块/数据重获(Recovery)模块，用来依据该旁信息动态地选择该些整形码中的至少一整形码，以对该原始数据进行数据整形。

上述本发明所述的记忆装置，其中该格子图的各级(Stage)中的每一级包含多个子路径；以及每一级的该些子路径分别代表该些整形码。

上述本发明所述的记忆装置，其中该控制器寻找该格子图中的一最佳化路径，并产生该最佳化路径中相对于各级的各个子路径的子路径追溯信息作为该旁信息的至少一部分；以及该最佳化路径的终点为该格子图的最后一级的各个结果状态中的一最佳状态，且该旁信息包含代表该最佳状态的终点信息。

上述本发明所述的记忆装置，其中针对该格子图的各级，该控制器进行对应于维特比(Viterbi)算法的相加、比较、与选择(Add Compare Select，ACS)运作，以产生该些级中的至少一级的各个结果状态的追溯指示器(TraceBack Indicator)并寻找该格子图的该最后一级的该些结果状态中的该最佳状态；以及该旁信息中的该子路径追溯信息包含该些追溯指示器中的至少一部分。

上述本发明所述的记忆装置，其中该原始数据包含分别对应于该格子图的各级(Stage)的部分数据(Partial Data)；针对对应于一特定级的特定部分数据，该控制器计算分别对应于至少两个整形码的至少两个分支量度值(Branch Metric)；以及该控制器累计该些级的多个分支量度值中的至少一部分，以进行该写入最佳化运作。

上述本发明所述的记忆装置，其中该控制器针对该原始数据中关于该闪存中的一记忆单元的最高有效位进行数据整形，而非对该原始数据中关于该记忆单元的全部位进行数据整形。

上述本发明所述的记忆装置，其中于该格子图的各级(Stage)当中，任一级内对应于特定状态转换的一子路径以及另一级内对应于相同状态转换的子路径均代表该些整形码当中的同一整形码。

上述本发明所述的记忆装置，其中该原始数据包含分别对应于该格子图的各级(Stage)的部分数据(Partial Data)；以及针对对应于一特定级的特定部分数据，该数据整形模块/数据重获模块依据该旁信息中的至少一部分于该些整形码中选出一特定整形码，以进行对应于该特定部分数据的数据整形。

上述本发明所述的记忆装置，其中该控制器将该旁信息中的至少一部分或其代表信息储存于该闪存，以供该原始数据重获用。

上述本发明所述的记忆装置，其中于一读取运作期间，该控制器自该闪存取得该旁信息中的该至少一部分或其代表信息，并且该数据整形模块/数据重获模块据以重获(Recover)该原始数据。

本发明解决其技术问题所采用的技术方案之三是：构造一种记忆装置的控制器，该控制器用来存取一闪存，该闪存包含多个区块，该控制器包含有：一只读存储器(Read Only Memory，ROM)，用来储存一程序代码；一微处理器，用来执行该程序代码以控制对该闪存的存取以及管理该多个区块，其中在该微处理器的控制下，该控制器针对该控制器本身所存取的数据来进行数据整形。另外，该控制器依据原始数据与多个整形码进行一写入最佳化运作，以产生对应于一格子图的追溯信息作为旁信息。此外，该控制器另包含有至少一数据整形模块/数据重获模块，用来依据该旁信息动态地选择该些整形码中的至少一整形码，以对该原始数据进行数据整形。

上述本发明所述的控制器，其中该格子图的各级(Stage)中的每一级包含多个子路径；以及每一级的该些子路径分别代表该些整形码。

上述本发明所述的控制器，其中该控制器寻找该格子图中的一最佳化路径，并产生该最佳化路径中相对于各级的各个子路径的子路径追溯信息作为该旁信息的至少一部分；以及该最佳化路径的终点为该格子图的最后一级的各个结果状态中的一最佳状态，且该旁信息包含代表该最佳状态的终点信息。

上述本发明所述的控制器，其中针对该格子图的各级，该控制器进行对应于维特比(Viterbi)算法的相加、比较、与选择(Add Compare Select，ACS)运作，以产生该些级中的至少一级的各个结果状态的追溯指示器(Trace BackIndicator)并寻找该格子图的该最后一级的该些结果状态中的该最佳状态；以及该旁信息中的该子路径追溯信息包含该些追溯指示器中的至少一部分。

上述本发明所述的控制器，其中该原始数据包含分别对应于该格子图的各级(Stage)的部分数据(Partial Data)；针对对应于一特定级的特定部分数据，该控制器计算分别对应于至少两个整形码的至少两个分支量度值(Branch Metric)；以及该控制器累计该些级的多个分支量度值中的至少一部分，以进行该写入最佳化运作。

上述本发明所述的控制器，其中该控制器针对该原始数据中关于该闪存中的一记忆单元的最高有效位进行数据整形，而非对该原始数据中关于该记忆单元的全部位进行数据整形。

上述本发明所述的控制器，其中于该格子图的各级(Stage)当中，任一级内对应于特定状态转换的一子路径以及另一级内对应于相同状态转换的子路径均代表该些整形码当中的同一整形码。

上述本发明所述的控制器，其中该原始数据包含分别对应于该格子图的各级(Stage)的部分数据(Partial Data)；以及针对对应于一特定级的特定部分数据，该数据整形模块/数据重获模块依据该旁信息中的至少一部分于该些整形码中选出一特定整形码，以进行对应于该特定部分数据的数据整形。

上述本发明所述的控制器，其中该控制器将该旁信息中的至少一部分或其代表信息储存于该闪存，以供该原始数据重获用。

上述本发明所述的控制器，其中于一读取运作期间，该控制器自该闪存取得该旁信息中的该至少一部分或其代表信息，并且该数据整形模块/数据重获模块据以重获(Recover)该原始数据。

实施本发明的技术方案，具有以下有益效果：通过适当地设计数据整形模块/数据重获模块，辅以相关的数据流控制，本发明能针对控制器所存取的数据来进行妥善的数据型样管理，以减少错误的发生。

另外，本发明不会增加许多额外的成本，甚至比相关技术更能节省成本。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1A为依据本发明一第一实施例的一种记忆装置的示意图；

图1B与图1C为图1A所示的记忆装置于一实施例中的实施细节；

图1D与图1E为不同的实施例中关于图1A所示的整形码(Shaping Code)产生器的实施细节；

图2为依据本发明一实施例的一种用来进行数据整形(Data Shaping)的方法的流程图；

图3A至图3C为图2所示的方法于一实施例中关于写入最佳化(ProgramOptimization)运作的实施细节，其中图3C另绘示图1A所示的数据整形模块于进行数据整形时所采用的整形码；

图4A至图4E为图2所示的方法于另一实施例中关于写入最佳化运作的实施细节；

图5绘示一实施例中关于图1A所示的闪存中的一记忆单元的位信息及其相关的各阶。

【主要组件符号说明】

具体实施方式

请参考图1A，图1A为依据本发明一第一实施例的一种记忆装置100的示意图，其中本实施例的记忆装置100尤其可为可携式记忆装置，例如：符合SD/MMC、CF、MS、XD标准的记忆卡，或通用序列总线快闪碟(UniversalSerial Bus Flash Drive，USB Flash Drive，亦称为USB Flash Disk)，即所谓的随身碟，但不以此为限。记忆装置100包含有：一闪存(Flash Memory)120；以及一控制器，用来存取闪存120，其中该控制器例如一存储器控制器110。依据本实施例，存储器控制器110包含一微处理器112、一只读存储器(Read Only Memory，ROM)112M、一控制逻辑114、一缓冲存储器116、与一接口逻辑118。另外，控制逻辑114包含至少一数据整形模块/数据重获(Recovery)模块，诸如一数据整形模块114DS，且另包含一编码器114E与一前处理器114P，其中数据整形模块114DS包含一调整单元114A、一附加单元114AP、与一整形码(Shaping Code)产生器114G。实作上，调整单元114A可为一异或(Exclusive OR，XOR)逻辑闸或一加法器。请注意，在此以可携式记忆装置为例；这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的一变化例，记忆装置100可为固态硬盘(Solid State Drive，SSD)。

于本实施例中，只读存储器112M用来储存一程序代码112C，而微处理器112则用来执行程序代码112C以控制对闪存120的存取(Access)。于典型状况下，闪存120包含多个区块(Block)，而该控制器(例如：透过微处理器112执行程序代码112C的存储器控制器110)对闪存120进行抹除数据的运作以区块为单位来进行抹除。另外，一区块可记录特定数量的页(Page)，其中上述的控制器对闪存120进行写入数据的运作以页为单位来进行写入。

实作上，透过微处理器112执行程序代码112C的存储器控制器110可利用其本身内部的组件来进行诸多控制运作，例如：利用控制逻辑114来控制闪存120的存取运作(尤其是对至少一区块或至少一页的存取运作)、利用缓冲存储器116进行所需的缓冲处理、以及利用接口逻辑118来与一主装置(Host Device)沟通。依据本实施例，除了能存取闪存120，存储器控制器110还能妥善地管理该多个区块。

另外，存储器控制器110还可针对其本身所存取的数据(例如：数据D1)来进行数据整形(Data Shaping)。尤其是，在微处理器112的控制下，针对存储器控制器110本身所存取的数据，存储器控制器110通过利用上述的至少一数据整形模块/数据重获模块(例如：数据整形模块114DS)的运作来进行数据整形以抑制数据错误。更明确而言，该控制器(于本实施例中尤其是其内的前处理器114P)依据多个整形码与原始数据诸如数据D1进行一写入最佳化(Program Optimization)运作，以产生对应于一格子图(TrellisDiagram)的追溯(Trace Back)信息作为旁信息(Side Information)I_SIDE，而上述的至少一数据整形模块/数据重获模块(例如：数据整形模块114DS)则依据旁信息I_SIDE动态地选择该些整形码中的至少一整形码，以对该原始数据进行数据整形。

于本实施例中，前处理器114P可依据数据D1与先前数据信息I_PD(即先前数据的信息，例如闪存中前一记忆页所储存的信息)来产生旁信息I_SIDE，其中该控制器可于接收到一写入/读取命令时利用旁信息I_SIDE中的至少一部分或其代表信息来进行相关运作，而该写入/读取命令用来指示该控制器于闪存120写入/读取数据。例如：在上述的写入/读取命令代表一写入命令的状况下，该控制器可立即使用旁信息I_SIDE来进行数据整形。更明确而言，整形码产生器114G可依据旁信息I_SIDE中的至少一部分或其代表信息来产生至少一整形码，诸如相对应的一个或多个整形码114SPC，以供用来于该控制器接收到该写入命令时调整该原始数据(诸如数据D1)的多个位。另外，调整单元114A依据上述的至少一整形码，来调整数据D1以产生调整后的数据D_RND1。此外，附加单元114AP可将旁信息I_SIDE中的至少一部分或其代表信息附加于数据D_RND1，作为其附加信息I_A。如此，编码器114E可对数据D_RND1连同附加信息I_A进行编码。因此，于一写入运作期间，该控制器不但将数据储存于闪存120，亦将旁信息I_SIDE中的至少一部分或其代表信息储存于闪存120，以供该原始数据重获用。于是，在上述的写入/读取命令代表一读取命令的状况下，于一读取运作期间，该控制器可自闪存120取得旁信息I_SIDE中的该至少一部分或其代表信息，并且上述的至少一数据整形模块/数据重获模块(例如：数据整形模块114DS)可据以重获(Recover)该原始数据诸如数据D1。

请注意，依据本实施例的一特例，数据整形模块114DS可用来当作一数据重获模块，其可于一读取运作期间重获数据。尤其是，数据整形模块114DS中的调整单元114A及整形码产生器114G可于一读取运作期间用来重获数据，其中附加单元114AP可通过切换电路的路径切换被暂时地断开而不电气连接至调整单元114A。依据本实施例的另一特例，除了数据整形模块114DS，上述的至少一数据整形模块/数据重获模块可另包含一数据重获模块，其可于一读取运作期间重获数据，如此一来，存储器控制器110即可同时进行写入与读取运作。例如：该数据重获模块可通过切换电路的路径切换来利用调整单元114A及/或整形码产生器114G。又例如：数据重获模块可包含其本身的调整单元。又例如：该数据重获模块可包含其本身的整形码产生器。

依据本实施例，在上述的写入/读取命令代表该写入命令的状况下，当通过调整单元114A的数据路径代表一写入路径时，数据D1可代表该控制器欲写入闪存120的该原始数据，而数据D_RND1可代表调整后的数据，并且数据D_RND1及附加信息I_A被送予编码器114E；于是，编码器114E据以进行编码，尤其是进行错误更正码(Error Correction Code，ECC)编码以产生编码数据，并将该编码数据写入闪存120，其中该编码数据可包含奇偶校验码(ParityCode)。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的一特例，诸如上述数据整形模块114DS可用来当作数据重获模块的特例，在上述的写入/读取命令代表该读取命令的状况下，当通过调整单元114A的数据路径代表一读取路径时，该读取路径可耦接至一解码器114D(未显示于图1A中)，其中解码器114D对读取自闪存120的编码数据进行解码，尤其是进行错误更正码解码以产生解码数据，诸如数据D_RND1及附加信息I_A(即旁信息I_SIDE中的至少一部分或其代表信息)。此状况下，调整单元114A的输入与输出对调；而调整单元114A依据至少一整形码，诸如相对应的一个或多个整形码114SPC，来调整数据D_RND1以重获数据D1，以供进一步处理。

依据本实施例的一变化例，该写入最佳化运作可利用程序代码112C中的至少一程序模块来实现；如此，前处理器114P可代换为透过微处理器112执行该程序模块的存储器控制器110。

图1B与图1C为图1A所示的记忆装置100于一实施例中的实施细节。如图1B所示，在上述的写入/读取命令代表该写入命令的状况下，前处理器114P自缓冲存储器116读出先前数据信息I_PD，并依据数据D1与先前数据信息I_PD进行该写入最佳化运作以产生旁信息I_SIDE。另外，数据整形模块114DS则自缓冲存储器116读出数据D1并依据旁信息I_SIDE动态地选择该些整形码中的至少一整形码，以对数据D1进行数据整形来产生数据D_RND1。如此，数据整形模块114DS依据旁信息I_SIDE产生至少一整形码，诸如相对应的一个或多个整形码114SPC，并据以调整数据D1的多个位以产生调整后的数据D_RND1。数据整形模块114DS另将附加信息I_A附加于数据D_RND1以产生组合数据(于图1B中绘示为附加了附加信息I_A的数据D_RND1)。此外，编码器114E对该组合数据进行错误更正码编码以产生编码数据(于图1B的右上角绘示为附加了附加信息I_A与奇偶校验码P1的数据D_RND1)，并将该编码数据写入闪存120。

如图1C所示，在上述的写入/读取命令代表该读取命令的状况下，存储器控制器110自闪存120所读取的编码数据(于图1C的右上角绘示为附加了附加信息I_A与奇偶校验码P1的数据D_RND1)分别被传送至解码器114D与缓冲存储器116，其中在存储器控制器110的控制下，缓冲存储器116只暂时地储存数据D_RND1与附加信息I_A而非奇偶校验码P1。读取重试控制器114RR用来于解码器114D进行解码时进行读取重试控制。另外，解码器114D对读取自闪存120的编码数据进行解码；一旦侦测到错误，就产生更正数据以更正缓冲存储器116中的数据D_RND1及/或附加信息I_A。于是，数据重获模块114DR依据附加信息I_A(即上述旁信息I_SIDE中的至少一部分或其代表信息)重获数据D1。依据本实施例，数据重获模块114DR可依据附加信息I_A产生至少一整形码，诸如相对应的一个或多个整形码114SPC，并据以调整数据D_RND1的多个位以重获数据D1，以供进一步处理。

依据本实施例的一变化例，数据整形模块114DS与数据重获模块114DR可为同一个组件，且因此可一并称为数据整形模块/数据重获模块。

图1D为一实施例中关于图1A所示的整形码产生器114G的实施细节。本实施例的整形码产生器114G包含一控制单元114C与一查对表(Look-upTable)114T，其中查对表114T储存有该多个整形码。由于该多个整形码包含上述的一个或多个整形码114SPC，故该一个或多个整形码114SPC的任一者选自于该多个整形码。

于本实施例中，控制单元114C可依据旁信息I_SIDE产生相对应的控制讯号C₁，并通过利用查对表114T来据以进行查对以产生该一个或多个整形码114SPC。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的一变化例，整形码产生器114G可直接使用旁信息I_SIDE(或附加信息I_A)的至少一部分作为控制讯号C₁，且于本变化例中并不需要设置上述的控制单元114C。依据本实施例的另一变化例，上述的控制单元114C被代换为一选择单元，用以选择旁信息I_SIDE(或附加信息I_A)的至少一部分作为控制讯号C₁。

请注意，本实施例的整形码产生器114G亦可应用于图1A至图1C所示的实施例或其变化例中的数据重获模块。

图1E为另一实施例中关于图1A所示的整形码产生器114G的实施细节，其中本实施例为图1D所示实施例的变化例。除了上述的控制单元114C与查对表114T，本实施例的整形码产生器114G另包含一随机函数发生器(Randomizer)/解随机函数发生器(Derandomizer)114R，且另包含一多工器114M，其中查对表114T储存有该多个整形码中的一部分，而随机函数发生器/解随机函数发生器114R可产生该多个整形码中的另一部分的任一整形码。

于本实施例中，控制单元114C可依据旁信息I_SIDE产生相对应的控制讯号C₀，并通过利用控制讯号C₀来选择查对表114T的输出、或随机函数发生器/解随机函数发生器114R的输出，作为整形码产生器114G的输出。例如：在控制单元114C通过利用控制讯号C₀来选择查对表114T的输出作为整形码产生器114G的输出的状况下，控制单元114C可依据旁信息I_SIDE产生相对应的控制讯号C₁，并通过利用查对表114T来进行查对以产生该一个或多个整形码114SPC的至少一部分。又例如：在控制单元114C通过利用控制讯号C₀来选择随机函数发生器/解随机函数发生器114R的输出作为整形码产生器114G的输出的状况下，控制单元114C可依据旁信息I_SIDE产生相对应的控制讯号C₂，作为随机函数发生器/解随机函数发生器114R的输入种子(Seed)，使随机函数发生器/解随机函数发生器114R据以产生至少一随机函数(RandomFunction)，其中随机函数发生器/解随机函数发生器114R输出该随机函数的序列(其可称为随机序列)，作为该一个或多个整形码114SPC的至少一部分。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的不同的变化例，整形码产生器114G可直接使用旁信息I_SIDE(或附加信息I_A)的至少一部分作为控制讯号C₀、C₁、及/或C₂，且于该些变化例中并不需要设置上述的控制单元114C。依据本实施例的其它变化例，上述的控制单元114C被代换为至少一选择单元，用以选择旁信息I_SIDE(或附加信息I_A)的至少一部分作为控制讯号C₀、C₁、及/或C₂。

请注意，本实施例的整形码产生器114G亦可应用于图1A至图1C所示的实施例或其变化例中的数据重获模块。

依据本发明的一实施例，诸如图1D与图1E所示实施例的一变化例，整形码产生器114G包含随机函数发生器/解随机函数发生器114R，其中本变化例中并不需要设置上述的查对表114T与多工器114M，也不需要产生控制讯号C₀与C₁。于本实施例中，随机函数发生器/解随机函数发生器114R可产生该多个整形码中的任一整形码，而随机函数发生器/解随机函数发生器114R输出该随机函数的序列(即该随机序列)，作为该一个或多个整形码114SPC。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的一变化例，整形码产生器114G可直接使用旁信息I_SIDE(或附加信息I_A)的至少一部分作为控制讯号C₂，且于本变化例中并不需要设置上述的控制单元114C。依据本实施例的另一变化例，上述的控制单元114C被代换为一选择单元，用以选择旁信息I_SIDE(或附加信息I_A)的至少一部分作为控制讯号C₂。

基于以上揭露的各个实施例/变化例中的架构，本发明可赋予多阶细胞(Multiple Level Cell，MLC)闪存极佳的运作效能，尤其是赋予三阶细胞闪存极佳的运作效能。存储器控制器110进行数据整形的相关细节可参考图2来进一步说明。

图2为依据本发明一实施例的一种用来进行数据整形的方法910的流程图。该方法可应用于图1A所示的记忆装置100，尤其是上述的控制器(例如：透过微处理器112执行程序代码112C的存储器控制器110)。另外，该方法可通过利用图1A所示的记忆装置100来实施，尤其是通过利用上述的控制器来实施。该方法说明如下：

步骤912：该控制器(于本实施例中尤其是其内的前处理器114P)依据原始数据(例如：数据D1)与多个整形码进行一写入最佳化运作诸如上述的写入最佳化运作，以产生对应于一格子图的追溯信息作为旁信息I_SIDE。请注意，依据本实施例的一变化例，诸如该写入最佳化运作可利用程序代码112C中的该程序模块来实现的变化例，前处理器114P可代换为透过微处理器112执行该程序模块的存储器控制器110。

步骤914：上述的至少一数据整形模块/数据重获模块(例如：数据整形模块114DS)依据旁信息I_SIDE动态地选择该些整形码中的至少一整形码，诸如上述的一个或多个整形码114SPC，以对该原始数据进行数据整形。例如：上述的数据整形的运作可实施为对该原始数据的至少一部分以及上述的至少一整形码进行异或(XOR)运算，尤其是对两者(该原始数据的该至少一部分以及上述的至少一整形码)的相对应位进行异或运算，其中这样的异或运算可称为“位异或”(Bitwise XOR)运算。

依据本实施例，该格子图包含多级(Stage)360-1、360-2、...、360-(K-1)、与360-K。该格子图的各级中的每一级诸如第k级360-k(k＝1、2、...、(K-1)、或K，其中K为正整数)包含多个子路径{P_{X1(k)，X2(k)}}。例如：X1(k)与X2(k)可为同一个整数的集合中的任意整数，尤其是非负数的整数。在此，一子路径P_{X1(k)，X2(k)}为第k级360-k当中由一开始状态S_X1(k)至一结果状态S_X2(k)的状态转换的路径，其中若存在下一级(即第(k+1)级360-(k+1))，则结果状态S_X2(k)为下一级的一开始状态。为了简明起见，上述的开始状态S_X1(k)与结果状态S_X2(k)可分别写成状态S_X(k)与S_X(k+1)。例如：在该格子图为四状态格子图的情况下，X＝0、1、2、或3。又例如：在该格子图为八状态格子图的情况下，X＝0、1、...、或7。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的不同的变化例，状态索引X的可能值的数量可为除了四与八的外的正整数，且此数量的典型值大于一。依据本实施例的其它变化例，状态索引X不必是整数。

另外，每一级的该些子路径分别代表该些整形码。例如：于每一级诸如第k级360-k当中，该些子路径{P_{X1(k)，X2(k)}}中的某一子路径P_{X1(k)，X2(k)}代表该些整形码中的一整形码SPC_{X1(k)，X2(k)}。尤其是，在每一级当中相关的候选整形码均为同一组整形码诸如步骤912所述的该些整形码的状况下，整形码SPC_{X1(k)， X2(k)}可改写成SPC_X1，X2，使得不论索引k的值为1、2、...、(K-1)、或K，子路径P_{X1(k)，X2(k)}总是代表该些整形码中的同一个整形码SPC_X1，X2。也就是说，在此状况下，整形码SPC_X1，X2与第k级360-k的索引k无关。如此，于该格子图的该些级当中，任一级内对应于特定状态转换的一子路径以及另一级内对应于相同状态转换的子路径均代表该些整形码当中的同一整形码。

于本实施例中，该控制器寻找该格子图中的一最佳化路径，并产生该最佳化路径中相对于各级(例如：第k级360-k)的各个子路径(例如：该些子路径{P_{X1(k)，X2(k)}})的子路径追溯信息作为旁信息I_SIDE的至少一部分，其中该最佳化路径的终点为该格子图的最后一级360-K的各个结果状态S_X(K+1)(例如：X＝0、1、2、...等)中的一最佳状态S_X0(K+1)，且旁信息I_SIDE包含代表最佳状态S_X0(K+1)的终点信息，诸如X0的二进制值。尤其是，针对该格子图的各级，该控制器进行对应于维特比(Viterbi)算法的相加、比较、与选择(Add Compare Select，ACS)运作，以产生该些级中的至少一级(例如：该些级中的全部)的各个结果状态的追溯指示器(Trace Back Indicator)并寻找该格子图的最后一级360-K的该些结果状态S_X(K+1)中的最佳状态S_X0(K+1)，其中旁信息I_SIDE中的该子路径追溯信息包含该些追溯指示器中的至少一部分。例如：该控制器可产生该格子图的各级诸如第k级360-k的各个结果状态S_X(k+1)的追溯指示器TBI_X(k)。如此，该控制器可依据该终点信息(例如：X0的二进制值)与该子路径追溯信息(例如：追溯指示器TBI_X(k)中的至少一部分)找到该最佳化路径，并据以决定该最佳化路径中对应于任一级诸如第k0级的子路径所代表的整形码，以对该原始数据中对应于第k0级的部分进行数据整形。例如：在该最佳化路径中对应于第k0级的子路径为子路径P_{X1(k0)，X2(k0)}的状况下，由于子路径P_{X1(k0)，X2(k0)}代表的候选整形码是整形码SPC_X1，X2，该控制器就通过利用整形码SPC_X1，X2，对该原始数据中对应于第k0级的部分进行数据整形。

图3A至图3C为图2所示的方法910于一实施例中关于写入最佳化运作的实施细节，其中图3C另绘示图1A所示的数据整形模块114DS于进行数据整形时所采用的整形码310，诸如整形码310-1、310-2、...、310-(K-1)、与310-K，而每一整形码310-k(k＝1、2、...、(K-1)、或K)均选自于步骤912所述的该些整形码。请注意，步骤912所述的该原始数据，诸如图3C所示的原始数据308，包含分别对应于该格子图的各级360-1、360-2、...、与360-K的部分数据(Partial Data)308-1、308-2、...、与308-K，即原始数据308中分别对应于第1级360-1、第2级360-2、...、与第K级360-K的部分。

如图3A所示，该格子图的各级中的每一级诸如第k级360-k包含8个子路径{P_0，0，P_0，1，P_1，2，P_1，3，P_2，0，P_2，1，P_3，2，P_3，3}，而这8个子路径分别为第k级360-k当中由状态{S₀(k)，S₁(k)，S₂(k)，S₃(k)}至状态{S₀(k+1)，S₁(k+1)，S₂(k+1)，S₃(k+1)}的状态转换的路径。另外，这8个子路径{P_0，0，P_0，1，P_1，2，P_1，3，P_2，0，P_2，1，P_3，2，P_3，3}分别代表8个整形码{SPC_0，0，SPC_0，1，SPC_{1， 2}，SPC_1，3，SPC_2，0，SPC_2，1，SPC_3，2，SPC_3，3}。于本实施例中，由状态S₀(k)指向状态S₀(k+1)及S₁(k+1)的路径可分别记录为0、1。相仿地，由状态S₁(k)指向状态S₂(k+1)及S₃(k+1)的路径可分别记录为0、1。另外，由状态S₃(k)指向状态S₃(k+1)及S₂(k+1)的路径可分别记录为0、1。相仿地，由状态S₂(k)指向状态S₁(k+1)及S₀(k+1)的路径可分别记录为0、1。

如图3B所示，于寻找该最佳化路径诸如图3C所示的最佳化路径390的过程中，该控制器会计算每一级诸如第k级360-k的各个结果状态S_X(k+1)的量度值(Metric)Met_X(k+1)，其中该控制器可将第1级360-1的各个开始状态S_X(1)的量度值Met_X(1)设定为同一数值，尤其是零。于本实施例中，针对对应于第k级360-k的部分数据308-k，该控制器计算分别对应于至少两个整形码的至少两个分支量度值(Branch Metric)(例如：分别对应于整形码SPC_0，0与SPC_2，0的分支量度值BM_0，0(k)与BM_2，0(k))。针对分别对应于该些级360-1、360-2、...、与360-K的部分数据308-1、308-2、...、与308-K，通过进行类似的计算，该控制器可累计该些级的多个分支量度值中的至少一部分，以进行该写入最佳化运作。

例如：在已取得第k级360-k的开始状态S₀(k)的量度值Met₀(k)与开始状态S₂(k)的量度值Met₂(k)的状况下，该控制器可先取得子路径P_0，0与P_2，0所分别代表的整形码SPC_0，0与SPC_2，0，再依据整形码SPC_0，0与SPC_2，0来计算分别对应于这两个整形码SPC_0，0与SPC_2，0(或分别对应于这两个子路径P_0，0与P_2，0)的分支量度值BM_0，0(k)与BM_2，0(k)，并且计算分别对应于这两个子路径P_0，0与P_2，0的累计值(Met₀(k)+BM_0，0(k))与(Met₂(k)+BM_2，0(k))。尤其是，该控制器可对部分数据308-k与整形码SPC_0，0进行“位异或”运算(于图3B的左上角标示为

)以产生整形数据SPD_0，0(k)，并据以计算分支量度值BM_0，0(k)。相仿地，该控制器可对部分数据308-k与整形码SPC_2，0进行“位异或”运算(于图3B的左下角标示为

)以产生整形数据SPD_2，0(k)，并据以计算分支量度值BM_2，0(k)。实作上，先前数据信息I_PD可载有先前数据的至少一部分或其代表信息，故该控制器可通过比较SPD_0，0(k)与先前数据信息I_PD中的相关部分来计算分支量度值BM_0，0(k)，并通过比较SPD_2，0(k)与先前数据信息I_PD中的相关部分来计算分支量度值BM_2，0(k)。

于本实施例中，该控制器可依据至少一预定规则，来选择累计值(Met₀(k)+BM_0，0(k))与(Met₂(k)+BM_2，0(k))中的某一累计值作为结果状态S₀(k+1)的量度值Met₀(k+1)，且产生结果状态S₀(k+1)的追溯指示器TBI₀(k)并且予以暂存，其中追溯指示器TBI₀(k)的值指出该控制器所选择的累计值所对应的子路径。例如：在该预定规则指出该控制器应选择最大的累计值的状况下，则该控制器可选择这两个累计值(Met₀(k)+BM_0，0(k))与(Met₂(k)+BM_2，0(k))中的最大的累计值作为结果状态S₀(k+1)的量度值Met₀(k+1)。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的一变化例，在该预定规则指出该控制器应选择最小的累计值的状况下，则该控制器可选择这两个累计值(Met₀(k)+BM_0，0(k))与(Met₂(k)+BM_2，0(k))中的最小的累计值作为结果状态S₀(k+1)的量度值Met₀(k+1)。依据本实施例的另一变化例，在上述的至少一预定规则包含多个预定规则。

实作上，一旦该控制器选择了这两个累计值(Met₀(k)+BM_0，0(k))与(Met₂(k)+BM_2，0(k))中的某一个累计值，就舍弃另一个累计值以减少该控制器的工作量。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的一变化例，在可供选择的累计值包含至少三个累计值的状况下，一旦该控制器选择了上述的至少三个累计值中的某一个累计值，就舍弃其它累计值以减少该控制器的工作量。

依据本实施例，该控制器依据上述的至少一预定规则或其它预定规则，于最后一级360-K的各个结果状态S_X(K+1)中选出最佳状态S_X0(K+1)，尤其是通过比较最后一级的各个结果状态S_X(K+1)的量度值Met_X(K+1)，诸如Met₀(K+1)、Met₁(K+1)、Met₂(K+1)、与Met₃(K+1)，来选出最佳状态S_X0(K+1)。于是，依据该些追溯指示器TBI_X(k)的至少一部分，由最佳状态S_X0(K+1)起，该控制器可逐一找出该最佳化路径诸如图3C所示的最佳化路径390的各个子路径。例如：前处理器114P可依据图3A所示的子路径简易标示，来记录追溯指示器TBI_X(k)。此状况下，前处理器114P可将子路径追溯信息记录为10...01，且可将终点信息X0诸如二进制值00以及子路径追溯信息10...01合并记录为旁信息I_SIDE，即10...0100。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的一变化例，图3A所示的子路径简易标示可予以改变。例如：指向同一状态S_X(k+1)的两个子路径中的上方、下方子路径可分别简易地标示为0、1，而前处理器114P可依据这些子路径简易标示来记录追溯指示器TBI_X(k)。如此，在追溯指示器TBI_X(k)＝1的状况下，追溯指示器TBI_X(k)指出最佳化路径390于第k级360-k中自状态S_X(k+1)返回下方子路径；而在追溯指示器TBI_X(k)＝0的状况下，追溯指示器TBI_X(k)指出最佳化路径390于第k级360-k中自状态S_X(k+1)返回上方子路径。

以图3C所示的状况为例，在上述的最佳状态(例如最佳化路径390的终点)为状态S₀(K+1)的状况下，该控制器依据追溯指示器TBI₀(K)找到最佳化路径390中相对于第K级的子路径P_2，0(K)，再依据追溯指示器TBI₂(K-1)找到最佳化路径390中相对于第(K-1)级的子路径P_1，2(K-1)，依此类推。相仿地，该控制器依据追溯指示器TBI₂(2)找到最佳化路径390中相对于第2级的子路径P_1，2(2)，再依据追溯指示器TBI₁(1)找到最佳化路径390中相对于第1级的子路径P_0，1(1)。于是，该控制器(于本实施例中尤其是其内的前处理器114P)将最佳化路径390中相对于该格子图的各级(诸如第1级360-1、第2级360-2、...、第(K-1)级360-(K-1)、与第K级360-K)的各个子路径P_0，1(1)、P_1，2(2)、...、P_1，2(K-1)、与P_2，0(K)的子路径追溯信息传送予上述的数据整形模块/数据重获模块；如此，旁信息I_SIDE包含最佳化路径390中相对于该格子图的各级的各个子路径P_0，1(1)、P_1，2(2)、...、P_1，2(K-1)、与P_2，0(K)的子路径追溯信息。

于是，针对对应于一特定级的特定部分数据(例如：对应于第k级360-k的部分数据308-k)，上述的数据整形模块/数据重获模块(例如：数据整形模块114DS)依据旁信息I_SIDE中的至少一部分于该些整形码中选出一特定整形码，以进行对应于该特定部分数据的数据整形。以图3C所示的状况为例，上述的数据整形模块/数据重获模块依据旁信息I_SIDE中关于各个子路径P_{0， 1}(1)、P_1，2(2)、...、P_1，2(K-1)、与P_2，0(K)的子路径追溯信息，分别选出整形码SPC_0，1、SPC_1，2、...、SPC_1，2、与SPC_2，0作为图3C所示的整形码310-1、310-2、...、310-(K-1)、与310-K，以分别进行对应于部分数据308-1、308-2、...、308-(K-1)、与308-K的数据整形。

请注意，针对每一级诸如第k级360-k，在可供选择的累计值仅具有两个累计值的状况下，追溯指示器TBI_X(k)的值可为一位的信息；由于该格子图内共有K级，故旁信息I_SIDE中的子路径追溯信息可仅具有K位。另外，在状态索引X的可能值的数量是四的状况下，旁信息I_SIDE中的终点信息诸如X0的二进制值可仅具有2位。如此，于本实施例中，旁信息I_SIDE可仅具有(K+2)位，故本发明于闪存120中针对附加信息I_A所需的储存空间极小。因此，相较于任何相关技术的架构，本发明能在极度地节省储存空间的状况下，提供极佳的运作效能。

图4A至图4E为图2所示的方法910于另一实施例中关于写入最佳化运作的实施细节。请参照图4A，图4A绘示原始数据400与其部分数据400-1、400-2、400-3、400-4的关系。在此实施例中，主装置欲将数据长度为一记忆页的原始数据400写入闪存120，原始数据400被区分为部分数据400-1至400-4。

首先，请参照图4B，前处理器114P针对部分数据400-1进行处理。前处理器114P依照图3B所示的方式对部分数据400-1进行数据整形、计算与选择。前处理器114P分别将部分数据400-1与8个不同的候选整形码进行位异或运算产生8笔不同的整形数据。这8个不同的候选整形码分别对应至图3A所示的路径P_0，0、P_0，1、P_1，2、P_1，3、P_2，0、P_2，1、P_3，2、P_3，3。前处理器114P分别对8笔不同的整形数据进行计算。在一实施例中，前处理器114P可将整形数据与闪存中前一记忆页中相对应的部分数据逐位地进行比对，若相同(例如同为逻辑0或同为逻辑1)则累进一分，若不同，则不加分。在此实施例中，各个整形数据所得的分数(分支量度值)标示于图4B相对应的路径上。例如，与路径P_0，0相对应的整形码进行位异或运算所产生的整形数据得到102分(如图4B路径P_0，0上的数字所示)，即BM_0，0(0)＝102。与路径P_0，1相对应的整形码进行位异或运算所产生的整形数据得到79分，即BM_0，1(0)＝79。以此类推。

请注意到，前处理器114P在对8笔不同的整形数据进行积分计算时，亦得不参考前一记忆页中相对应的部份数据。前处理器114P得分别计算各整形数据中逻辑0或逻辑1的数目，以使整形数据中逻辑0或逻辑1数目最接近的具有最高积分、或者逻辑1较多者有较高积分、或者逻辑0较多者有较高积分。而且，针对存放在不同记忆页的整形数据，也可以有不同的积分计算规则。例如，针对错误率较低的记忆页，可使整形数据中逻辑1较多者有较高积分。而针对错误率较高的记忆页，可使整形数据中逻辑0较多者有较高积分。进行积分计算的规则可依各种不同的闪存特性而定。

而于进行选择时，前处理器114P会对指向各结果状态的各路径积分进行比较。如前所述，开始状态S₀(0)、S₁(0)、S₂(0)、S₃(0)的量度值均预设为0(分别标示于各状态的圆圈上方)。举例来说，指向结果状态S₀(1)的路径为P_0，0与P_2，0。路径P_0，0的积分为分支量度值BM_0，0(0)加上开始状态S₀(0)的量度值Met₀(0)，即102+0＝102。路径P_2，0的积分为分支量度值BM_2，0(0)加上开始状态S₂(0)的量度值Met₂(0)，即95+0＝95。在此实施例中，前处理器114P选择积分较大者作为存活路径。例如，路径P_0，0的积分(102)大于路径P_2，0的积分(95)，故将路径P_0，0作为存活路径，并将结果状态S₀(1)的量度值Met₀(1)记录为102(标示于状态S₀(1)的圆圈上方，如图4B最右侧所示)，依此类推。

接着，请参考图4C前处理器114P针对部分数据400-2进行数据整形、计算与选择。前处理器114P针对部分数据400-2进行数据整形、计算与选择的方式类似于图4B，为求简洁，类似的部分不予赘述。结果状态S₀(1)、S₁(1)、S₂(1)、S₃(1)的量度值与各分支量度值如图4C所示。请注意到，图4B中，开始状态S₀(0)、S₁(0)、S₂(0)、S₃(0)的量度值均预设为0。而图4C中，开始状态S₀(1)、S₁(1)、S₂(1)、S₃(1)(于图4B中可称为结果状态)的量度值分别为102、80、90、105。前处理器114P在进行路径选择时，需考虑到各开始状态(例如前一级的结果状态)的量度值。举例来说，指向结果状态S₁(2)的路径为P_0，1与P_2，1。路径P_0，1的积分为分支量度值BM_0，1(1)加上开始状态S₀(1)的量度值Met₀(1)，即68+102＝170。路径P_2，1的积分为分支量度值BM_2，1(1)加上开始状态S₂(1)的量度值Met₂(1)，即63+90＝153。前处理器114P选择积分较大者作为存活路径。路径P_0，1的积分(170)大于路径P_2，1的积分(153)，故将路径P_0，1作为存活路径，并将结果状态S₁(2)的量度值Met₁(2)记录为170，依此类推。

请参考第4D图，待前处理器114P对部分数据400-1至400-4进行数据整形、计算与选择完毕后，可得到结果状态S₀(4)、S₁(4)、S₂(4)、S₃(4)的量度值分别为380、367、355、370。在此实施例中，前处理器114P选择量度值最高的结果状态S₀(4)作为最佳状态，并通过其存活路径找出最佳路径490。而在记录旁信息I_SIDE时，可依据最佳状态S₀(4)将终点信息记录为00。而记录子路径追溯信息时，可依据最佳路径490及图3A的子路径简易标示，将子路径追溯信息记录为0010。故，可将终点信息记录及子路径追溯信息合并记录为旁信息I_SIDE，即001000。图4E即为数据整形模块114DS所产生的数据D_RND1及附加信息I_A的示意图，在此实施例中，附加信息I_A即为旁信息I_SIDE，本发明并不以此为限，附加信息I_A亦得包含其它信息。

图5绘示一实施例中关于图1A所示的闪存120中的一记忆单元(cell)的位信息510及其相关的各阶{L0，L1，L2，L3，L4，L5，L6，L7}，其中位信息510包含最高有效位(Most Significant Bit)MSB、中央有效位(CentralSignificant Bit)CSB、与最低有效位(Least Significant Bit)LSB。依据本实施例，若最高有效位MSB为1且其余位CSB与LSB均为0，则该记忆单元的储存阶为第4阶L4。另外，若最高有效位MSB及其余位CSB与LSB均为0，则该记忆单元的储存阶为第0阶L0。如此，针对位信息510的各个可能的二进制值{000，001，010，011，100，101，110，111}，该记忆单元的储存阶分别为相对应的各阶{L0，L1，L2，L3，L4，L5，L6，L7}。

于本实施例中，该控制器针对该原始数据(例如：数据D1)中关于该记忆单元的某一(些)位进行数据整形，而非对该原始数据中关于该记忆单元的全部位进行数据整形。尤其是，该控制器针对该原始数据中关于该记忆单元的最高有效位MSB进行数据整形，而不对该原始数据中关于该记忆单元的其余位诸如中央有效位CSB与最低有效位LSB进行数据整形。这只是为了说明的目的而已，并非对本发明的限制。依据本实施例的一变化例，该控制器针对该原始数据中关于该记忆单元的最高有效位MSB与中央有效位CSB进行数据整形，而不对该原始数据中关于该记忆单元的其余位诸如最低有效位LSB进行数据整形。依据本实施例的另一变化例，该控制器针对该原始数据中关于该记忆单元的最高有效位MSB与次高有效位(例如：于本变化例中该次高有效位中央有效位CSB)进行数据整形，而不对该原始数据中关于该记忆单元的其余位诸如最低有效位LSB进行数据整形。亦可依据该记忆单元中各不同位出错的机率决定是否需要进行数据整形。例如，该记忆单元中，最高有效位MSB出错机率最低，相较中央有效位CSB、最低有效位LSB其仅需最低位数的错误更正码保护，故可有多余的空间储存旁信息I_SIDE，因此，仅对最高有效位MSB进行数据整形。

本发明的好处之一是，通过适当地设计上述的数据整形模块/数据重获模块，辅以相关的数据流控制(例如：图1A至图1C的数据流控制)，本发明能针对该控制器所存取的数据来进行妥善的数据型样管理，以减少错误的发生。另外，依据以上各个实施例/变化例来实施并不会增加许多额外的成本，甚至比相关技术更能节省成本。因此，基于以上揭露的内容，相关技术的问题已被解决，且整体成本不会增加太多。

以上所述仅为本发明的较佳实施例，凡依本发明申请专利范围所做的均等变化与修饰，皆应属本发明的涵盖范围。

Claims (30)

1.一种用来进行数据整形的方法，该方法应用于一闪存的控制器，该闪存包含多个区块，其特征在于，该方法包含有：

依据原始数据与多个整形码进行一写入最佳化运作，以产生对应于一格子图的追溯信息作为旁信息；以及

依据该旁信息动态地选择该些整形码中的至少一整形码，以对该原始数据进行数据整形。

2.根据权利要求1所述的方法，其特征在于，其中该格子图的各级中的每一级包含多个子路径；以及每一级的该些子路径分别代表该些整形码。

3.根据权利要求2所述的方法，其特征在于，其中依据该原始数据与该些整形码进行该写入最佳化运作以产生对应于该格子图的追溯信息作为该旁信息的步骤另包含：

寻找该格子图中的一最佳化路径，并产生该最佳化路径中相对于各级的各个子路径的子路径追溯信息作为该旁信息的至少一部分，其中该最佳化路径的终点为该格子图的最后一级的各个结果状态中的一最佳状态，且该旁信息包含代表该最佳状态的终点信息。

4.根据权利要求3所述的方法，其特征在于，其中依据该原始数据与该些整形码进行该写入最佳化运作以产生对应于该格子图的追溯信息作为该旁信息的步骤另包含：

针对该格子图的各级，进行对应于维特比算法的相加、比较、与选择运作，以产生该些级中的至少一级的各个结果状态的追溯指示器并寻找该格子图的该最后一级的该些结果状态中的该最佳状态，其中该旁信息中的该子路径追溯信息包含该些追溯指示器中的至少一部分。

5.根据权利要求1所述的方法，其特征在于，其中该原始数据包含分别对应于该格子图的各级的部分数据；以及依据该原始数据与该些整形码进行该写入最佳化运作以产生对应于该格子图的追溯信息作为该旁信息的步骤另包含：

针对对应于一特定级的特定部分数据，计算分别对应于至少两个整形码的至少两个分支量度值；以及

累计该些级的多个分支量度值中的至少一部分，以进行该写入最佳化运作。

6.根据权利要求1所述的方法，其特征在于，其中依据该旁信息动态地选择该些整形码中的该至少一整形码以对该原始数据进行数据整形的步骤另包含：

针对该原始数据中关于该闪存中的一记忆单元的最高有效位进行数据整形，而非对该原始数据中关于该记忆单元的全部位进行数据整形。

7.根据权利要求1所述的方法，其特征在于，其中于该格子图的各级当中，任一级内对应于特定状态转换的一子路径以及另一级内对应于相同状态转换的子路径均代表该些整形码当中的同一整形码。

8.根据权利要求1所述的方法，其特征在于，其中该原始数据包含分别对应于该格子图的各级的部分数据；以及依据该旁信息动态地选择该些整形码中的该至少一整形码以对该原始数据进行数据整形的步骤另包含：

针对对应于一特定级的特定部分数据，依据该旁信息中的至少一部分于该些整形码中选出一特定整形码，以进行对应于该特定部分数据的数据整形。

9.根据权利要求1所述的方法，其特征在于，其另包含有：

将该旁信息中的至少一部分或其代表信息储存于该闪存，以供该原始数据之重获之用。

10.根据权利要求9所述的方法，其特征在于，其另包含有：

于一读取运作期间，自该闪存取得该旁信息中的该至少一部分或其代表信息，并据以重获该原始数据。

11.一种记忆装置，其特征在于，其包含有：

一闪存，该闪存包含多个区块；以及

一控制器，用来存取该闪存以及管理该多个区块，并且另针对该控制器本身所存取的数据来进行数据整形，其中该控制器依据原始数据与多个整形码进行一写入最佳化运作，以产生对应于一格子图的追溯信息作为旁信息，以及该控制器包含有：

至少一数据整形模块/数据重获模块，用来依据该旁信息动态地选择该些整形码中的至少一整形码，以对该原始数据进行数据整形。

12.根据权利要求11所述的记忆装置，其特征在于，其中该格子图的各级中的每一级包含多个子路径；以及每一级的该些子路径分别代表该些整形码。

13.根据权利要求12所述的记忆装置，其特征在于，其中该控制器寻找该格子图中的一最佳化路径，并产生该最佳化路径中相对于各级的各个子路径的子路径追溯信息作为该旁信息的至少一部分；以及该最佳化路径的终点为该格子图的最后一级的各个结果状态中的一最佳状态，且该旁信息包含代表该最佳状态的终点信息。

14.根据权利要求13所述的记忆装置，其特征在于，其中针对该格子图的各级，该控制器进行对应于维特比算法的相加、比较、与选择运作，以产生该些级中的至少一级的各个结果状态的追溯指示器并寻找该格子图的该最后一级的该些结果状态中的该最佳状态；以及该旁信息中的该子路径追溯信息包含该些追溯指示器中的至少一部分。

15.根据权利要求11所述的记忆装置，其特征在于，其中该原始数据包含分别对应于该格子图的各级的部分数据；针对对应于一特定级的特定部分数据，该控制器计算分别对应于至少两个整形码的至少两个分支量度值；以及该控制器累计该些级的多个分支量度值中的至少一部分，以进行该写入最佳化运作。

16.根据权利要求11所述的记忆装置，其特征在于，其中该控制器针对该原始数据中关于该闪存中的一记忆单元的最高有效位进行数据整形，而非对该原始数据中关于该记忆单元的全部位进行数据整形。

17.根据权利要求11所述的记忆装置，其特征在于，其中于该格子图的各级当中，任一级内对应于特定状态转换的一子路径以及另一级内对应于相同状态转换的子路径均代表该些整形码当中的同一整形码。

18.根据权利要求11所述的记忆装置，其特征在于，其中该原始数据包含分别对应于该格子图的各级的部分数据；以及针对对应于一特定级的特定部分数据，该数据整形模块/数据重获模块依据该旁信息中的至少一部分于该些整形码中选出一特定整形码，以进行对应于该特定部分数据的数据整形。

19.根据权利要求11所述的记忆装置，其特征在于，其中该控制器将该旁信息中的至少一部分或其代表信息储存于该闪存，以供该原始数据重获用。

20.根据权利要求19所述的记忆装置，其特征在于，其中于一读取运作期间，该控制器自该闪存取得该旁信息中的该至少一部分或其代表信息，并且该数据整形模块/数据重获模块据以重获该原始数据。

21.一种记忆装置的控制器，该控制器用来存取一闪存，该闪存包含多个区块，其特征在于，该控制器包含有：

一只读存储器，用来储存一程序代码；

一微处理器，用来执行该程序代码以控制对该闪存的存取以及管理该多个区块，其中在该微处理器的控制下，该控制器针对该控制器本身所存取的数据来进行数据整形，其中该控制器依据原始数据与多个整形码进行一写入最佳化运作，以产生对应于一格子图的追溯信息作为旁信息；以及

至少一数据整形模块/数据重获模块，用来依据该旁信息动态地选择该些整形码中的至少一整形码，以对该原始数据进行数据整形。

22.根据权利要求21所述的控制器，其特征在于，其中该格子图的各级中的每一级包含多个子路径；以及每一级的该些子路径分别代表该些整形码。

23.根据权利要求22所述的控制器，其特征在于，其中该控制器寻找该格子图中的一最佳化路径，并产生该最佳化路径中相对于各级的各个子路径的子路径追溯信息作为该旁信息的至少一部分；以及该最佳化路径的终点为该格子图的最后一级的各个结果状态中的一最佳状态，且该旁信息包含代表该最佳状态的终点信息。

24.根据权利要求23所述的控制器，其特征在于，其中针对该格子图的各级，该控制器进行对应于维特比算法的相加、比较、与选择运作，以产生该些级中的至少一级的各个结果状态的追溯指示器并寻找该格子图的该最后一级的该些结果状态中的该最佳状态；以及该旁信息中的该子路径追溯信息包含该些追溯指示器中的至少一部分。

25.根据权利要求21所述的控制器，其特征在于，其中该原始数据包含分别对应于该格子图的各级的部分数据；针对对应于一特定级的特定部分数据，该控制器计算分别对应于至少两个整形码的至少两个分支量度值；以及该控制器累计该些级的多个分支量度值中的至少一部分，以进行该写入最佳化运作。

26.根据权利要求21所述的控制器，其特征在于，其中该控制器针对该原始数据中关于该闪存中的一记忆单元的最高有效位进行数据整形，而非对该原始数据中关于该记忆单元的全部位进行数据整形。

27.根据权利要求21所述的控制器，其特征在于，其中于该格子图的各级当中，任一级内对应于特定状态转换的一子路径以及另一级内对应于相同状态转换的子路径均代表该些整形码当中的同一整形码。

28.根据权利要求21所述的控制器，其特征在于，其中该原始数据包含分别对应于该格子图的各级的部分数据；以及针对对应于一特定级的特定部分数据，该数据整形模块/数据重获模块依据该旁信息中的至少一部分于该些整形码中选出一特定整形码，以进行对应于该特定部分数据的数据整形。

29.根据权利要求21所述的控制器，其特征在于，其中该控制器将该旁信息中的至少一部分或其代表信息储存于该闪存，以供该原始数据重获用。

30.根据权利要求29所述的控制器，其特征在于，其中于一读取运作期间，该控制器自该闪存取得该旁信息中的该至少一部分或其代表信息，并且该数据整形模块/数据重获模块据以重获该原始数据。

Images