错误检测与纠正装置、错误检测与纠正方法、信息处理器及程序

技术领域

本发明涉及一种错误检测与纠正装置、错误检测与纠正方法、信息 处理器及程序，该程序在由计算机执行时使得计算机在错误检测与纠正 装置中实施错误检测与纠正方法。更具体而言，本发明涉及分别使用多 种编码系统的一种错误检测与纠正装置、错误检测与纠正方法及信息处 理器以及程序，该程序在由计算机执行时使得计算机在错误检测与纠正 装置中实施错误检测与纠正方法。

背景技术

当再现存储于诸如磁光记录盘、硬盘及非易失性存储器等数据记录 与再现装置中的数据时，所存储数据可因数据记录与再现装置的损坏、 热噪声等而被损坏且无法被正确读取。为了处理此类数据损坏，通常的 数据记录装置将要存储的数据编码为错误检测与纠正码(ECC)，并保持 ECC。当再现数据时，使得数据记录装置使用ECC来检测并纠正数据中 的错误。

在编码时，可使用多个编码系统以提高纠错能力。例如，提出了一 种非易失性存储器，其将多个数据编码为分组码字，将这些各个分组码 字编码为各个卷积码字，并随后保持所述卷积码字(例如，参阅第日本 未经审查的专利申请公开2010-287305号)。在非易失性存储器已对各个 分组码字执行纠错，且对分组码字之一的纠错已失败的情况下，非易失 性存储器通过对含有纠错已失败的分组码字的卷积码字进行解码来可靠 地纠正数据中的错误。

在上述技术中，纠正数据中的错误可能需要很长时间。在上述非易 失性存储器中，对其中有多个分组码字被交错的序列作为用于编码的对 象进行卷积编码。由于对如此交错的序列进行卷积编码，因而必须在对 一个分组码字进行解码之前对所有卷积码字进行解码。因此，在上述非 易失性存储器中，为了可靠地纠正数据，即使对一个分组码字的纠正已 失败，必须纠正所有卷积码字。因此，纠正数据中的错误需要很长时间， 且很难以高速度精确地纠正数据中的错误。

技术内容

本发明期望以高速度精确地纠正数据中的错误。

根据本发明的实施例，提供一种错误检测与纠正装置，其包括：第 一码错误检测部，其用于检测第二码字中的多个第一码字中的每一个是 否具有错误，所述第二码字是通过以连锁方式对所述多个第一码字进行 编码而生成的，并且是含有多个部分数据的码字；和第二码纠错部，其 用于基于与所述第二码字中的所述多个部分数据中的一个部分数据毗邻 的毗邻部分数据来纠正所述一个部分数据中的所述错误，所述一个部分 数据含有检测到所述错误的所述第一码字。

根据本发明的实施例，提供一种错误检测与纠正方法，其包括：检 测第二码字中的多个第一码字中的每一个是否具有错误，所述第二码字 是通过以连锁方式对所述多个第一码字进行编码而生成的，并且是含有 多个部分数据的码字；以及基于与所述第二码字中的所述多个部分数据 中的一个部分数据毗邻的毗邻部分数据来纠正所述一个部分数据中的所 述错误，所述一个部分数据含有检测到所述错误的所述第一码字。

根据本发明的实施例，提供一种其中嵌入有程序的非暂存性有形记 录媒介，所述计算机可读程序在由计算机执行时使得计算机实施一种方 法，所述方法包括：检测第二码字中的多个第一码字中的每一个是否具 有错误，所述第二码字是通过以连锁方式对所述多个第一码字进行编码 而生成的，并且是含有多个部分数据的码字；以及基于与所述第二码字 中的所述多个部分数据中的一个部分数据毗邻的毗邻部分数据来纠正所 述一个部分数据中的所述错误，所述一个部分数据含有检测到所述错误 的所述第一码字。

因此，达到基于所述毗邻部分数据来纠正所述错误的效果。

此外，在根据本发明实施例的错误检测与纠正装置中，为所述多个 部分数据中彼此毗邻的部分数据所共有的数据部分可为共同码字，且所 述第二码纠错部可基于为所述一个部分数据与所述毗邻部分数据所共有 的所述数据部分，纠正含有检测到所述错误的所述第一码字的所述一个 部分数据中的所述错误。因此，达到基于为彼此毗邻的所述部分数据所 共有的所述数据部分来纠正所述错误的效果。

此外，在根据本发明实施例的错误检测与纠正装置中，所述第二码 纠正部可纠正所述毗邻部分数据中的错误，且当对所述毗邻部分数据的 纠错成功时，所述第二码纠错部可基于所述毗邻部分数据来纠正由所述 第一码错误检测部检测到的所述错误。因此，达到当对所述毗邻部分数 据的纠错成功时基于所述毗邻部分数据来纠正所述错误的效果。

此外，在根据本发明实施例的错误检测与纠正装置中，当对所述毗 邻部分数据的纠错已失败时，所述第二码纠错部可纠正新毗邻部分数据 中的错误，且可判断对所述新毗邻部分数据的纠错是否成功，所述新毗 邻部分数据是与所述毗邻部分数据毗邻的部分数据。因此，达到在对所 述毗邻部分数据的纠错已失败的情况下使用与所述毗邻部分数据毗邻的 部分数据作为所述新毗邻部分数据的效果。

在根据本发明的实施例的错误检测与纠正装置中，当未检测到含于 所述毗邻部分数据中的所述第一码字中的错误时，所述第二码纠错部可 基于所述毗邻部分数据来纠正由所述第一码错误检测部检测到的所述错 误，且当检测到含于所述毗邻部分数据中的所述第一码字中的错误时， 所述第二码纠错部可判断是否在含于新毗邻部分数据中的所述第一码字 中检测到错误，所述新毗邻部分数据为与所述毗邻部分数据毗邻的部分 数据。因此，达到在含于所述毗邻部分数据中的所述第一码字中检测到 所述错误的情况下、将与所述毗邻部分数据毗邻的部分数据用作所述新 毗邻部分数据的效果。

在根据本发明的实施例的错误检测与纠正装置中，所述第二码纠错 部可在对所述毗邻部分数据的纠错已失败时纠正所述第二码字中的错 误。因此，达到在对所述毗邻部分数据的纠错已失败的情况下纠正所述 第二码字中的所述错误的效果。

在根据本发明的实施例的错误检测与纠正装置中，所述第二码纠错 部可判断基于所述毗邻部分数据所执行的对所述错误的纠正是否成功， 且当所述纠正已失败时，所述第二码纠错部可基于各自含有所述第一码 字的第三码字来纠正所述错误。因此，达到在基于所述毗邻部分数据所 执行的纠错已失败的情况下基于各自含有所述第一码字的所述第三码字 来纠正所述错误的效果。

在根据本发明的实施例的错误检测与纠正装置中，所述第二码字可 为卷积码字，且所述第二码纠错部可基于对所述毗邻部分数据所执行的 卷积运算的结果来纠正所述错误。因此，达到基于对所述毗邻部分数据 所执行的所述卷积运算的所述结果来纠正所述错误的效果。

在根据本发明的实施例的错误检测与纠正装置中，所述第二码字可 为turbo码字。因此，达到在所述turbo码字中纠正所述错误的效果。

在根据本发明的实施例的错误检测与纠正装置中，所述第二码纠错 部可纠正含有检测到所述错误的所述第一码字的所述一个部分数据与所 述毗邻部分数据的组合中的所述错误，所述组合作为一个解码单位。因 此，达到纠正含有检测到所述错误的所述第一码字的所述一个部分数据 与所述毗邻部分数据的所述组合中的所述错误的效果，所述组合作为一 个解码单位。

在根据本发明的实施例的错误检测与纠正装置中，所述多个部分数 据中的每一个可含有用于纠正所述部分数据中的每一个中的错误的第二 奇偶校验和用于纠正所述第二奇偶校验中的错误的第一奇偶校验，且所 述第二码纠错部可使用所述第一奇偶校验来纠正所述第二奇偶校验中的 所述错误，且可使用所述纠正后的第二奇偶校验来纠正所述一个部分数 据中的所述错误。因此，达到使用通过使用所述第一奇偶校验被纠正的 所述第二奇偶校验来纠正所述部分数据中的所述错误的效果。

在根据本发明的实施例的错误检测与纠正装置中，所述多个部分数 据中的每一个可含有所述多个第一码字中的两个或更多个。因此，达到 纠正含有所述多个分组码字的所述部分数据中的错误的效果。

根据本发明的实施例，提供一种信息处理器，其包括：第二编码部， 其用于通过连锁方式对多个第一码字进行编码来生成第二码字，所述第 二码字是含有多个部分数据的码字；第一码错误检测部，其用于检测所 述第二码字中的所述第一码字中的每一个是否具有错误；及第二码纠错 部，其用于基于与所述第二码字中的所述多个部分数据中的一个部分数 据毗邻的毗邻部分数据来纠正所述一个部分数据中的所述错误，所述一 个部分数据含有检测到所述错误的所述第一码字。因此，达到基于所述 毗邻部分数据来纠正所述错误的效果。

在本发明的实施例中，使得所述错误检测与纠正装置达到可以高速 度精确地纠正数据的优异效果。

应理解，上述总体说明和下述详细说明为示例性的，且旨在为所主 张的技术提供进一步的解释。

附图说明

包括附图以提供对本发明的进一步的理解，且并入本说明书并构成 本说明书的一部分。附图图示实施例，且与说明书一起用来解释本发明 的原理。

图1为图示根据第一实施例的信息处理系统的配置示例的方块图。

图2为图示根据第一实施例的存储控制器的配置示例的方块图。

图3为图示根据第一实施例的ECC处理部的配置示例的方块图。

图4为用于描述根据第一实施例的分组编码的图示。

图5为图示根据第一实施例的第二编码部的配置示例的方块图。

图6A和图6B为图示根据第一实施例的正则校验矩阵的示例的图示。

图7为图示根据第一实施例的带状矩阵的示例的图示。

图8A和图8B为描述根据第一实施例使用生成矩阵的方法的图示。

图9为用于描述根据第一实施例的第二码中的数据依赖关系的示例 的图示。

图10为图示根据第一实施例的第二码的数据结构的示例的图示。

图11为图示根据第一实施例的第二码错误检测与纠正部的配置示例 的方块图。

图12为图示根据第一实施例的第二码错误检测与纠正器的配置示例 的方块图。

图13A和图13B为图示根据第一实施例在变量节点与校验节点之间 交换消息的示例的图示。

图14为用于描述根据第一实施例纠正第二码的方法的图示。

图15为图示根据第一实施例的存储控制器的操作的示例的流程图。

图16为图示根据第一实施例的编码的示例的流程图。

图17为图示根据第一实施例的解码的示例的流程图。

图18为图示根据第一实施例的第二码错误检测与纠正的示例的流程 图。

图19为图示根据第一实施例的第一变型例的第二码的数据结构的示 例的图示。

图20为用于描述根据第一实施例的第二变型例的第二码字的数据结 构的示例的图示。

图21为用于描述根据第一实施例的第三变型例的第二码字的数据结 构的示例的图示。

图22为图示根据第一实施例的第四变型例的第二码错误检测与纠正 的示例的流程图。

图23为用于描述根据第一实施例的第五变型例纠正第二码的方法的 图示。

图24为图示根据第二实施例的第二码错误检测与纠正部的配置示例 的方块图。

图25为图示根据第二实施例的第二码错误检测与纠正的示例的流程 图。

图26为用于描述根据第二实施例纠正第二码的方法的图示。

图27为图示根据第二实施例的第一变型例的第二码错误检测与纠正 的示例的流程图。

图28为用于描述根据第二实施例的第一变型例纠正第二码的方法的 图示。

图29为图示根据第二实施例的第二变型例的第二码错误检测与纠正 的示例的流程图。

图30为图示根据第三实施例的第二编码部的配置示例的方块图。

图31为图示根据第三实施例的第二编码器的状态转换的示例的状态 转换图。

图32为用于描述根据第三实施例生成第二码的示例的图示。

图33为图示根据第三实施例的第二码错误检测与纠正部的配置示例 的方块图。

图34A和图34B为图示根据第三实施例的第二编码部的状态转换的 网格图的示例。

图35为图示根据第四实施例的第二编码部的配置示例的方块图。

图36为图示根据第四实施例的第二码错误检测与纠正部的配置示例 的方块图。

图37为图示根据第五实施例的第二编码部的配置示例的方块图。

图38为图示根据第五实施例的第二码的数据结构的示例的图示。

图39为图示根据第五实施例的第二码错误检测与纠正部的配置示例 的方块图。

图40为图示根据第六实施例的第二编码部的配置示例的方块图。

图41为图示根据第六实施例的校验矩阵的示例的图示。

图42为图示根据第六实施例的第二码错误检测与纠正部的配置示例 的方块图。

具体实施方式

下面将阐述本发明的某些实施例。阐述将按照下列顺序给出：

1.第一实施例(其中基于毗邻部分数据执行纠错的示例)

2.第二实施例(其中基于所追溯的毗邻部分数据来执行纠错直到纠 正成功为止的示例)

3.第三实施例(其中将卷积码字用作第二码字且基于毗邻部分数据 来执行纠错的示例)

4.第四实施例(其中将turbo码字用作第二码字且基于毗邻部分数据 来执行纠错的示例)

5.第五实施例(其中基于在毗邻部分数据中所纠正的奇偶校验来执 行纠错的示例)

6.第六实施例(其中当基于毗邻部分数据所执行的纠错已失败时基 于第三码字来执行纠错的示例)

(1.第一实施例)

(信息处理系统的配置示例)

图1为图示根据第一实施例的信息处理系统的配置示例的方块图。信 息处理系统包括主机系统100和储存系统200。

主机系统100用于控制整个信息处理系统。更具体而言，主机系统100 生成命令和数据，并通过信号线109将命令和数据供应给储存系统200。 此外，主机系统100从储存系统200接收数据。命令可用于控制储存系统 200，且命令的示例可包括用于数据写入的写入命令和用于数据读取的读 取命令。

储存系统200包括存储控制器300和非易失性存储器600。存储控制器 300用于控制非易失性存储器600。当存储控制器300从主机系统100接收 写入命令和写入数据时，存储控制器300从写入数据生成错误检测与纠正 码(ECC)。更具体而言，存储控制器300将写入数据转换(即，编码) 成含有写入数据和奇偶校验的ECC。存储控制器300通过信号线309来访 问非易失性存储器600，以将编码数据写入到非易失性存储器600。

此外，当存储控制器300从主机系统100接收读取命令时，存储控制 器300通过信号线309来访问非易失性存储器600以读取编码数据。然后， 存储控制器300将编码数据转换(即，解码)成编码之前的原始数据。在 此解码中，存储控制器300基于ECC来检测并纠正数据中的错误。存储控 制器300将纠正后的数据供应给主机系统100。

非易失性存储器600用于基于存储控制器300的控制来保持数据。

(存储控制器的配置示例)

图2为图示根据第一实施例的存储控制器300的配置示例的方块图。 存储控制器300包括主机接口310、RAM(随机访问存储器)320、CPU(中 央处理器)330、ROM(只读存储器)340、非易失性存储器接口350和总 线360。存储控制器300还包括ECC处理部400。

主机接口310用于与主机系统100互换数据和命令。RAM320用于临 时保持由CPU330执行的处理中必要的数据。CPU330用于控制整个存储 控制器300。ROM340用于保持由CPU330执行的程序等等。非易失性存 储器接口350用于与非易失性存储器600互换数据和命令。总线360为用于 在主机接口310、RAM320、CPU330、ROM340、非易失性存储器接口 350和ECC处理部400之间互换数据的共同路径。

ECC处理部400用于对写入数据进行编码并对读取数据进行解码。在 对写入数据进行编码时，ECC处理部400将多个写入数据作为用于分组编 码的对象数据，通过向所述用于分组编码的对象数据中的每一者添加奇 偶校验而以预定单位将所述多个写入数据编码为分组码。下文中，将以 预定单位编码为分组码的数据中的每一个称作“第一码字”。然后，ECC 处理部400以预定单位对第一码字中的每一个以连锁方式进行编码。下文 中，将以连锁方式编码的数据称作“第二码字”。应注意，ECC处理部400 对应于本发明实施例中的“错误检测与纠正装置”的具体示例。

“以连锁方式进行编码”意指按照固定的顺序通过使用从当前编码 的数据之前的数据获得的状态和当前编码的数据而进行编码，从而对多 个数据依次进行编码。编码顺序取决于接收或生成数据的时间、其中记 录数据的地址的值等等。此外，第二码字含有用于检测并纠正第二码字 中的错误的第一码字和奇偶校验。换句话说，由ECC处理部400生成的 ECC含有第一码字和第二码字。下文中，将用于校验第一码字的奇偶校 验称作“第一奇偶校验”，且将用于校验第二码字的奇偶校验称作“第二 奇偶校验”。

ECC处理部400通过总线360来将编码后的写入数据供应给非易失性 存储器600。

当读取编码后的读取数据时，ECC处理部400使用第一奇偶校验来检 测并纠正第一码字中的错误。在对第一码字的纠错已失败的情况下，ECC 处理部400使用第二奇偶校验来纠正第二码字，以纠正纠错已失败的第一 码字中的错误。ECC处理部400通过总线360来将纠正后的第一码字供应 给主机系统100。

(ECC处理部的配置示例)

图3为图示根据第一实施例的ECC处理部400的配置示例的方块图。 ECC处理部400包括第一编码部410、第二编码部420、编码数据缓冲器460 和编码数据供应部470。ECC处理部400还包括第一码错误检测与纠正部 520、第二码错误检测与纠正部530、解码数据缓冲器570和解码数据供应 部580。

第一编码部410用于将作为用于第一编码的对象数据的多个写入数 据编码为第一码字。在此第一编码中，例如，可使用二进制BCH (Bose Chaudhuri Hocquenghem)码作为第一码。第一编码部410将通过 编码所生成的第一码字通过信号线419来供应给第二编码部420。

应注意，第一编码部410使用能够检测并纠正错误的BCH码作为第一 码；然而，第一码不仅限于BCH码，且可为具有错误检测能力的任一码。 第一码的示例包括含有不具有纠错能力的奇偶校验位的码、汉明 (hamming)码和RS(Reed-Solomon)码。此外，第一编码部410可使用 比二进制高的码作为第一码。

第二编码部420用于将第一码字编码为第二码字。更具体而言，第 二编码部420通过空间耦合LDPC编码系统来将多个第一码字编码为第二 码字。在解码时，纠正第二码字的整个或部分中的错误。下文中，将第 二码字的部分解码的部分中的每一个称作“部分数据”。

编码数据缓冲器460用于保持被编码为第二码字的数据。编码数据供 应部470用于从编码数据缓冲器460读取第二码字，且将第二码字供应给 总线360。

第一码错误检测与纠正部520用于检测并纠正第一码字中的错误。第 一码错误检测与纠正部520可例如使用硬判决解码方法来纠正错误，在所 述硬判决解码方法中，将第一码字的每一符号的值唯一性地判断为“1” 或“0”。所述符号为构成码字的最小单位，且可例如为1位。第一码错误 检测与纠正部520对第一码字进行解码，且第一码错误检测与纠正部520 将解码后的第一码字输出到第二码错误检测与纠正部530，并将解码后的 第一码字存储于解码数据缓冲器570中。此外，如果存在纠错已失败且只 可实施错误检测的第一码字，则第一码错误检测与纠正部520通过总线 360将第一码字的错误检测通知输出到CPU330。当ECC处理部400在错误 检测通知中通知CPU330已检测到错误时，CPU330读取第二奇偶校验的 部分(用于与已尝试解码的第一码字一起构成部分数据的第二奇偶校 验)，并将第二奇偶校验的部分输入到第二码错误检测与纠正部530。

应注意，第一码错误检测与纠正部520对应于本发明实施例中的“第 一码错误检测部”的具体示例。

此外，第一码错误检测与纠正部520通过硬判决解码方法来纠正第一 码中的错误；然而，可通过软判决解码方法来纠正错误，在所述软判决 解码方法中，判断每一符号的值的似然(诸如对数似然比)。例如，可使 用“Makiko Kan等人，Hardware Implementation of Soft-Decision Decoding for Reed-Solomon Code，20085th International Symposium on Turbo Codes and Related Topics)”中所述的方法。在此文献中，装置基于诸如RS码的 第一码的每一符号的似然(诸如对数似然比)，通过诸如和积算法的置信 传播方法来纠正数据中的错误。在此文献中，执行校验矩阵的对角化； 然而，当该方法应用于本发明实施例时，对角化并非必要。当也使用软 判决解码方法来纠正第一码中的错误时，提高了纠错能力。

第二码错误检测与纠正部530用于基于与第一码错误检测与纠正部 520检测到错误的纠正的对象部分数据毗邻的部分数据之一或两者来纠 正对象部分数据中的错误。部分数据A与部分数据B“毗邻”意指按照编 码顺序紧接着部分数据B之前或之后生成部分数据A。下文中，将以如此 毗邻的部分数据称作“毗邻部分数据”。当第二码错误检测与纠正部530 接收第二奇偶校验时，第二码错误检测与纠正部530生成含有由第一码错 误检测与纠正部520解码的第一码字和那个第二奇偶校验的部分数据。例 如，第二码错误检测与纠正部530可使用软判决解码方法来纠正部分数据 中的错误。稍后将详细阐述纠错的方法。第二码错误检测与纠正部530将 错误被纠正的部分数据通过信号线539输出到第一码错误检测与纠正部 520。第一码错误检测与纠正部520将部分数据中的第一码字存储于解码 数据缓冲器570中。

应注意，第二码错误检测与纠正部530对应于本发明实施例中的“第 二码纠错部”的具体示例。

解码数据缓冲器570用于保持解码后的第一码字。解码数据供应部 580用于从解码数据缓冲器570读取错误被纠正的第一码字，并将对应于 用于第一编码的对象数据的解码数据供应给总线360。

图4为用于描述根据第一实施例的第一编码的图示。如图4所图示， 第一编码部410将用于第一编码的各个对象Kf位数据编码为各个Nf位第 一码字，其中Kf为整数，且Nf为大于Kf的整数。第一码字各自含有用于 第一编码的对象Kf位数据和Nf-Kf位第一奇偶校验。因此，码字含有用于 编码的原样对象数据，并且将能够轻易地将码字分成数据和奇偶校验的 码称作“系统码”。应注意，第一码可为非系统码。

(第二编码部的配置示例)

图5为图示根据第一实施例的第二编码部420的配置示例的方块图。 第二编码部420包括第二编码对象数据生成部421和第二编码器422。

第二编码对象数据生成部421用于将来自第一编码部410的多个第一 码一起地作为第二编码对象数据供应给第二编码器422。

第二编码器422用于将用于第二编码的对象数据编码为第二码字。在 编码为第二码时，例如，可使用将数据编码为二进制空间耦合LDPC(低 密度奇偶校验)码的编码系统。稍后将参考图6A与图6B、图7和图8A与 图8B等等详细阐述编码为空间耦合LDPC码的方法。

假定第二编码器422保持生成矩阵。然而，第二编码器422可从校验 矩阵产生生成矩阵。所述校验矩阵为在对第二码执行奇偶校验的过程中 所使用的矩阵，且所述生成矩阵为用于对编码的对象数据进行编码的矩 阵。生成矩阵可通过下列表达式1从校验矩阵求出。

[数学式1]

G×H^T＝0…表达式1

其中“G”为生成矩阵，且“H^T”为通过反转校验矩阵H而形成的矩 阵。

第二编码器422求出通过表达式1所得到的生成矩阵和用于第二编码 的对象数据的乘积。第二编码器422将所得到的乘积作为第二码字通过信 号线429输出到编码数据缓冲器460。

应注意，只要第二码为通过连锁方式对多个数据进行编码而生成的 码，第二码就不仅限于空间耦合LDPC码。例如，可使用稍后将阐述的卷 积码或turbo码来代替空间耦合LDPC码。此外，第二编码部420可使用高 于二进制的码作为第二码。这也适用于第一实施例的稍后将阐述的变型 例。

图6A和图6B为图示根据第一实施例的正则校验矩阵H_reg的示例的图 示。在空间耦合LDPC编码系统中，第二码错误检测与纠正部530生成多 个正则校验矩阵H_reg。这些正则校验矩阵H_reg为其中各行和各列中“1”的 数目(下文中称作“权重”)为固定的校验矩阵。图6A为图示正则校验矩 阵H_reg中的权重的示例的图示。在此示例中，每一列的权重为“3”，且每 一行的权重为“6”。

第二码错误检测与纠正部530通过将正则校验矩阵H_reg对角划分两 个部分来生成上三角矩阵H_U和下三角矩阵H_L。图6B为图示划分后的正则 校验矩阵H_reg的示例的图示。下文中，将每一三角矩阵中形成直角的两条 边中的一条边称作“底边”，且将另一条边称作“毗邻边”。

在空间耦合LDPC中，可以使用从带状矩阵H_b中切出的部分矩阵H_p来执行部分解码。当在第二码错误检测与纠正部530中设定部分数据的大 小Ns时，第二码错误检测与纠正部530从带状矩阵H_b上切出具有等同于 Ns的大小的部分矩阵。例如，在部分数据的大小Ns等于两倍于三角矩阵 的底边的长度的情况下，可使用通过将四个三角矩阵彼此组合而形成的 部分矩阵作为用于对部分数据进行解码的校验矩阵。校验矩阵H_p为与部 分数据的大小Ns具有相等的列数和Ns-Ks行数的矩阵。此外，在对整个 第二码字进行解码的情况下，可使用带状矩阵H_b作为校验矩阵。带状矩 阵H_b中的列数N为第二码字的码长。

Ks为作为不具有第二奇偶校验的部分数据的数据的大小。换句话说， Ns-Ks为部分数据中的第二奇偶校验的大小。此外，部分数据的大小Ns 可设定为例如非易失性存储器600的访问单位的除数。应注意，部分数据 的大小Ns可设定为非易失性存储器600的访问单位的倍数。

图8A和图8B为用于描述根据第一实施例使用生成矩阵的方法的图 示。图8A为图示根据第一实施例的生成矩阵G的示例的图示。图8A中所 示例的生成矩阵G为基于表达式1从图7中所示例的带状校验矩阵H_b生成。 如图8A中所图示，在校验矩阵H_b中的列数和行数分别为N和N-K的情况 下，从校验矩阵H_b生成具有N列及K行的生成矩阵G。图8B图示用于从生 成矩阵和用于第二编码的对象数据求出第二码的计算表达式的示例。如 图8B中所图示，第二码字为由生成矩阵G与用于第二编码的对象数据的 乘积生成。第二码字含有用于第二编码的k位对象数据及N-K位第二奇偶 校验。因此，第二码为含有用于编码的原样对象数据的系统码。当第二 码为由系统码构成时，ECC处理部400可以在解码中轻易地仅仅分离第一 码并纠正第一码中的错误。

图9为用于描述根据第一实施例的第二码中的数据依赖关系的示例 的图示。在图9中，箭头表示依赖关系。每个部分数据为依据与其毗邻的 部分数据的状态通过图8A和图8B中所图示的矩阵运算而生成。然而，端 部处的部分数据不含有与其毗邻的第二奇偶校验；因此，端部处的部分 数据的大小小于其他部分数据的大小。应注意，在将端部处的部分大小 的大小调整为等于其他部分数据的大小的情况下，可添加与第二奇偶校 验的大小具有相等大小的假数据以取代第二奇偶校验。

例如，部分数据#1由第一码字#1构成。第二部分数据#2依赖于与其 毗邻的第二奇偶校验#1。第三部分数据#3依赖于与其毗邻的第二奇偶校 验#2。因此，除第一部分数据以外的每一个部分数据依赖于与其毗邻的 部分数据的部分(例如，第二奇偶校验)。这些部分数据的组合对应于一 个第二码字。因此，在空间耦合LDPC编码系统中，第二码字以连锁方式 生成。应注意，依赖关系不仅限于图9中所示例的关系。例如，每一个部 分数据可依赖于与其毗邻的整个部分数据或多个其他部分数据。

图10为图示根据第一实施例的非易失性存储器600中的第二码的数 据结构的示例的方块图。如图10中所图示，第二码字含有多个部分数据。 部分数据中的每一个依赖于与其毗邻的第二奇偶校验。因此，生成其中 数据的部分(即，第二奇偶校验)为彼此毗邻的部分数据所共有的码作 为第二码。

(第二码错误检测与纠正部的配置示例)

图11为图示根据第一实施例的第二码错误检测与纠正部530的配置 示例的方块图。第二码错误检测与纠正部530包括校验矩阵生成部531、 部分数据生成部532和第二码错误检测与纠正器540。

校验矩阵生成部531用于生成校验矩阵。在校验矩阵生成部531中， 设定部分数据的大小Ns。校验矩阵生成部531生成具有Ns列的校验矩阵。 校验矩阵生成部531将所生成的校验矩阵供应给第二码错误检测与纠正 器540。

部分数据生成部532用于对部分数据中包含的第一码进行解码，所述 部分数据与含有解码已经失败的第一码的部分数据毗邻。假定对毗邻部 分数据的读取由CPU330控制，且对含于所读取的部分数据中的第一码的 解码成功。接下来，部分数据生成部532将用于纠正的对象部分数据及与 该对象部分数据毗邻的部分数据输出到第二码错误检测与纠正器540。此 时，将解码成功的第一码的每一位指定为已知位，且将含有该已知位的 部分数据输出到第二码错误检测与纠正器540。

已知位意指其中错误已被纠正且纠正后的值是已知的位。如上所述， 彼此毗邻的部分数据彼此共享第二奇偶校验；因此，当纠正与用于纠正 的对象部分数据毗邻的部分数据中的错误时，也相应地纠正对象部分数 据中的第二奇偶校验中的错误。因此，部分数据生成部532可以将第一码 的每一位指定为已知位。对用于纠正的对象部分数据的纠错容易通过指 定已知位来执行。

此外，在生成部分数据时，在与该部分数据毗邻的部分数据已由第 二码错误检测与纠正器540纠正的情况下，部分数据生成部532无需再次 将纠正后的毗邻部分数据输入到第二码错误检测与纠正器540便可获取 纠正后的毗邻部分数据的第二奇偶校验。例如，考虑这样一种情况，即 对部分数据#1、#2、#3和#4中的部分数据#1和#3中的第一码字的纠错已 失败、且执行对毗邻部分数据#1和#3的部分数据#2的纠错。在存储控制 器300对部分数据#2和#1依次进行纠正、并且对部分数据#2和#1两者的纠 正成功之后存储控制器300对部分数据#3进行纠错的情况下，与部分数据 #3毗邻的部分数据#2和#4中的部分数据#2已被纠正。在此情况下，由于 对部分数据#2的纠正并非必要，因而存储控制器300可依次纠正部分数据 #4和#3，而无需再次纠正部分数据#2。部分数据生成部532可为每一部分 数据生成标志以表示是否已实施纠正，且可将该标志存储于解码数据缓 冲器570中，且可参考该标志以判断是否已实施纠正。

在由于毗邻部分数据已被纠正因而不执行对毗邻部分数据的纠正 的情况下，部分数据生成部532从所读取的第一码字及所读取的第二奇偶 校验中生成部分数据，所读取的第一码字在第一码错误检测与纠正部中 的解码已失败，并将如此生成的部分数据输出到第二码错误检测与纠正 部。

第二码错误检测与纠正器540用于使用校验矩阵来检测并纠正第二 码字中的部分数据中的错误。第二码错误检测与纠正部530可使用和积 (sum-product)算法来纠正部分数据中的错误。在使用和积算法的配置 中，第二码错误检测与纠正器540包括变量节点处理部541和校验节点处 理部543。分类为和积算法的算法可包括诸如概率域和积算法和对数域和 积算法的各种算法。变量节点处理部541和校验节点处理部543可使用例 如从这些算法中选择的对数域和积算法来纠正第二码中的错误。

应注意，变量节点处理部541和校验节点处理部543可使用除对数域 和积算法以外的任何和积算法。

此外，只要算法可以检测并纠正第二码字中的错误，第二码错误检 测与纠正器540可使用除和积算法以外的诸如位翻转算法(bit-flipping algorithm)的任何算法。此外，可使用其中和积算法的部分被简化的算 法(诸如min-sum算法)。或者，可使用“Shuhei Tanakamaru等人， Over-10×-Extended-Lifetime 76％-Reduced-Error Solid-State Drives(SSDs) with Error-Prediction LDPC Architecture and Error-Recovery Scheme， ISSCC 2012”中所述的技术。在此文献中所述的EP(错误预测)-LDPC 方法中，装置预先测量数据被重写的次数和每存储单元的数据保持时间， 且以表格形式存储数据被重写的次数和数据保持时间。然后，装置基于 这些表格来预测BER(位错误率)，然后使用BER来纠正LDPC码中的错误。

变量节点处理部541用于基于校验节点处理部543的奇偶校验的结果 来检测并纠正第二码字中的错误。此外，校验节点处理部543用于对第二 码字执行奇偶校验。第二码字中的部分数据输入到变量节点处理部541。 应注意，如稍后将阐述，在对部分数据的纠正已失败的情况下，部分数 据生成部532可将整个第二码字输入到变量节点处理部541。

更具体而言，当变量节点处理部541接收第二码字时，变量节点处理 部541基于第二码字来生成消息u_{0_i}。消息u_{0_i}为表示在纠正前的第二码字 中的第i符号(例如，位)的值为“0”或“1”的似然的实变量。此外， “i”为0～Ns-1的整数，其中Ns为第二码字的大小。然而，在第i位由部 分数据生成部532指定为已知位的情况下，消息u_{0_i}的似然设定为最大值。 变量节点处理部541基于消息u_{0_i}和校验节点处理部543的奇偶校验的结 果来生成消息v_i，并将消息v_i输出到校验节点处理部543。消息v_i为表示纠 正后的第二码字中的第i位的值的似然的实变量。在对数域和积算法中， 生成对数似然比Λ(r_i)作为消息u_{0_i}。对数似然比Λ(r_i)为码字的第i符号(例 如，位)的值为“0”的概率相对于码字的第i符号的值为“1”的概率的 比值的对数，且可通过例如下列表达式2来求出。

[数学式2]

$\Lambda \left(r_i\right)=\ln \frac{P(r_i=1|r)}{P(r_i=0|r)}$…表达式2

其中r为所接收到的第二码字，P(r_i＝1|r)为第二码字中的第i位r_i的值为 “1”的概率，且P(r_i＝0|r)为第二码字中的第i位的值为“0”的概率。

应注意，只要消息u_{0_i}为表示似然的值，消息u_{0_i}不仅限于对数似然 比。例如，可采用r_i的值为“1”或“0”的概率作为消息u_{0_i}。这也适用 于其他消息v_j和u_j。

校验节点处理部543基于消息v_i来执行奇偶校验，基于奇偶校验的结 果来生成消息u_j，并随后将消息u_j输出到变量节点处理部541，其中“i” 可为0～(Ns-Ks)-1的整数，且Ks为作为不具有第二奇偶校验的部分数据 的数据的大小。在对数域和积算法中，输出对数似然比作为消息u_j。

变量节点处理部541和校验节点处理部543相互之间交换消息直到满 足预定终止条件为止。例如，当消息交换固定次数时或当对数似然比的 绝对值超过阈值时，可判断满足终止条件。

当满足终止条件时，变量节点处理部541基于所接收到的消息u_j来求 出错误被纠正的第二码字。变量节点处理部541将纠正后的第二码字输出 到解码数据缓冲器570。

(第二码错误检测与纠正器的配置示例)

图12为图示根据第一实施例的第二码错误检测与纠正器540的配置 示例的方块图。在第二码错误检测与纠正器540中，变量节点处理部541 包括与第二码字的位数(即，校验矩阵H_p的列数)具有相等数目的变量 节点542。此外，校验节点处理部543包括与第二码字中的第二奇偶校验 的位数(即，校验矩阵H_p的行数)具有相等数目的校验节点544。然后， 校验节点544与变量节点542基于校验矩阵H_p的元素的值彼此连接。更具 体而言，当第i行与第i列中的元素的值为“1”时，第i校验节点544与第i 变量节点542彼此连接，且当元素的值为“0”时，这些节点不彼此连接。

第i变量节点542用于基于校验节点544的奇偶校验的结果来检测并 纠正第二码字中的第i符号(例如，位)中的错误。第i校验节点544执行 对应于校验矩阵H_p的第i行的奇偶校验。

更具体而言，第i变量节点542从部分数据生成部532接收第二码字的 第i位，并基于该位的值来生成消息u_{0_i}。在消息u_{0_i}为对数似然比的情况 下，当第i位的值为“1”时，小于最大值Max的预定正值设定为u_{0_i}。另 一方面，当第i位的值为“0”时，大于最小值Min的预定负值设定为u_{0_i}。 最大值Max和最小值Min分别为依赖于对数似然比的数据类型及数据大 小的最大值和最小值。例如，在例如将带符号的定点数据用于运算的情 况下，由数据表示的数值范围为对应于实数部分和虚数部分中的每一个 中的位数的范围。使用数值范围内的最大值和最小值作为最大值Max和 最小值Min。应注意，第二码错误检测与纠正器540可将带符号的浮点数 据用于运算。

然而，在第i位指定为已知位的情况下，设定使得似然最大化的值。 例如，在第i已知位的值为“1”的情况下，最大值Max可设定为u_{0_i}，且 在第i已知位的值为“0”的情况下，最小值Min设定为u_{0_i}。

在生成消息u_{0_i}之后，变量节点542将来自与其连接的校验节点544中 的每一个的消息u_j设定为初始值(例如，“0”)。然后，变量节点542通过 使用下列表达式3的计算来求出消息v_i，并将消息v_i输出到与其连接的校 验节点544之一。

[数学式3]

$v_i=u_{0\_i}+\underset{j=1}{\overset{d_v-1}{\Sigma }}{u}_j$…表达式3

其中d_v为校验矩阵H_p的列中“1”的数目(即，权重)。

当校验节点544从与其连接的变量节点542中的每一个接收消息v_i时， 校验节点544通过使用下列表达式4的计算来求出消息u_j，并将消息u_j输出 到与其连接的变量节点542之一。

[数学式4]

$\tanh \left(\frac{u_j}{2}\right)=\underset{i=1}{\overset{d_c-1}{\Pi }}\tanh \left(\frac{v_i}{2}\right)$…表达式4

其中，d_c为校验矩阵H_p的行中“1”的数目(即，权重)，tanh()为双 曲正切函数，且∏x为x的无穷乘积。

此表达式4可使用表达式5变换成表达式6。

[数学式5]

a×b＝exp(ln|a|+ln|b|)×sign(a)×sign(b)…表达式5

[数学式6]

$\left(\begin{array}{c}{u}_j={2\tanh }^{-1}\left(\underset{i=1}{\overset{d_c-1}{\Pi }}\tanh \left(\frac{v_i}{2}\right)\right)\\ ={2\tanh }^{-1}[\exp \left\{\underset{i=1}{\overset{d_c-1}{\Sigma }}\ln \left(\right|\tanh \left(\frac{v_i}{2}\right)\left|\right)\right\}\times \underset{i=1}{\overset{d_c-1}{\Pi }}\sin \mathrm{gn}\left(\tanh \left(\frac{v_i}{2}\right)\right)]\\ ={2\tanh }^{-1}\left[\exp \{-(\underset{i=1}{\overset{d_c-1}{\Sigma }}-\ln \left(\tanh \left(\frac{\left|v_i\right|}{2}\right)\right))\}\right]\times \underset{i=1}{\overset{d_c-1}{\Pi }}\mathrm{sign}\left(v_i\right)\end{array}\right)$…表达式6

在表达式5和6中，sign(x)为在x≥0时将“1”的值返回到输入值x， 且在x＜0时将“-1”的值返回到输入值x的函数。

由表达式4变换成的表达式6可使用以下表达式7中所定义的函数进 一步变换成表达式8。校验节点544可通过使用表达式8、而不是表达式4 的计算来求出消息u_j。

[数学式7]

$\phi \left(x\right)=-\ln \left\{\tanh \left(\frac{x}{2}\right)\right\}$…表达式7

[数学式8]

$u_j={\phi }^{-1}\left(\underset{i=1}{\overset{d_c-1}{\Sigma }}\phi \left(\right|v_i\left|\right)\right)\times \underset{i=1}{\overset{d_c-1}{\Pi }}\mathrm{sign}\left(v_i\right)$…表达式8

应注意，不仅可使用表达式4或表达式8而且可通过比表达式4和8更 简单的运算来求出消息u_j。例如，可预先针对消息v₁和v₂的可能值中的每 一个计算出由表达式9定义的函数R(v₁，v₂)的运算结果。然后，可预先形 成与运算结果和消息v₁和v₂的组合相关联的表格，且可如表达式10中所图 示以递归方式使用从表格读取的运算结果，从而容易地求出消息u_j。

[数学式9]

$R(v_1,v_2)={2\tanh }^{-1}\left\{\tanh \left(\frac{v_1}{2}\right)\tanh \left(\frac{v_2}{2}\right)\right\}$表达式9

[数学式10]

$u_j=R(v_1,R(v_2,R(v_3...R(v_{d_c-2},v_{d_c-1}))))$..表达式10

变量节点542和校验节点544使用表达式3和4等等生成消息v_i和u_j，并 在相互之间交换这些消息直到满足预定终止条件为止。

当满足终止条件时，变量节点542使用下列表达式11来生成消息v_i’。 变量节点542基于所生成的消息v_i’来确定第二码字的第i位的值。例如， 变量节点542可确定第i位的值在v_i’≥0的情况下为“1”且在v_i’＜0的情况下 为“0”。因此，纠正第二码字中的错误。变量节点542将在第二码字中纠 正的部分数据输出到第一码错误检测与纠正部520。

[数学式11]

${v_i}^{\text{'}}=u_{0\_i}+\underset{j=1}{\overset{d_v}{\Sigma }}{u}_j$…表达式11

应注意，变量节点542可通过将表达式3分成表达式11和下列表达式 12来执行表达式3的运算。在此情况下，在未满足终止条件的情况下，变 量节点542将通过表达式12求出的消息v_i输出到校验节点544。然后，当满 足终止条件时，变量节点542基于通过表达式11求出的消息v_i′来求出第二 码字中的位的值。

[数学式12]

v_i＝v_i’-u_dv…表达式12

其中u_dv为来自与变量节点542连接的第d_v校验节点544的消息。

图13A和图13B为图示根据第一实施例的变量节点542与校验节点 544之间的消息交换的示例的图示。图13A为图示当变量节点542生成消息 v_i时的消息交换的示例的图示。例如，假定第一变量节点V1连接到第一、 第三和第五校验节点U1、U3和U5。在此情况下，当变量节点V1从部分 数据生成部532接收消息u_{0_1}，且从校验节点U1和U3接收消息u₁和u₃时， 变量节点V1基于这些消息来生成消息v₁，并将消息v₁输出到校验节点U5。

图13B为图示当校验节点544生成消息u_j时的消息交换的示例的图 示。例如，假定第一校验节点U1连接到第一、第三、第五、第六、第七 和第九变量节点V1、V3、V5、V6、V7和V9。在此情况下，当校验节点 U1从变量节点V3、V5、V6、V7和V9接收消息v₃、v₅、v₆、v₇和v₉时，校 验节点U1基于这些消息来生成消息u₁，并将消息u₁输出到变量节点V1。

图14为用于描述根据第一实施例纠正第二码字的方法的图示。例如， 考虑其中纠正含有第一码字#1、#2和#3的第二码的情况。这些第一码字 中的第一码字#1具有由第一码错误检测与纠正部520可以纠正的数目的 错误，且第一码字#2具有不可纠正的数目的错误。此外，假定对应于它 们所添加的第二奇偶校验#1和#2中的每一个也具有错误。

第一码错误检测与纠正部520纠正各个第一码字#1、#2和#3中的错 误。在此纠正中，第一码错误检测与纠正部520成功地纠正具有可纠正数 目的错误的第一码字#1，但未能纠正具有不可纠正数目的错误的第一码 字#2。

在此情况下，第二码错误检测与纠正部530纠正部分数据#1和#3中的 错误，部分数据#1和#3毗邻纠正已失败的第一码字#2。通过纠正这些部 分数据来纠正部分数据#1的第二奇偶校验#1和部分数据#3的第二奇偶校 验#2中的错误。

然后，第二码错误检测与纠正部530纠正含有纠正已失败的第一码字 #2的部分数据#2中的错误。在部分数据#2中，第二奇偶校验#1和#2中的 错误已纠正；因此，第二码错误检测与纠正部530可以将第二奇偶校验#1 和#2中的位的值用作已知值来精确地纠正错误。

因此，第二码错误检测与纠正部530对部分数据执行纠错，所述部分 数据毗邻具有错误的用于纠正的对象部分数据，从而纠正所述用于纠正 的对象部分数据的第二奇偶校验中的错误。因此，与只纠正具有错误的 部分数据的情况相比，可以更精确地纠正数据中的错误。此外，第二码 错误检测与纠正部530并不是纠正第二码字的全部而是只纠正第二码字 的部分；因此，与纠正整个第二码字的情况相比，可以以更高的速度纠 正数据中的错误。此外，在纠错中没有必要将整个第二码字读取到工作 存储器；因此，与读取整个第二码字的情况下所使用的电路相比，第二 码错误检测与纠正部530可以由更小规模的电路构成。

应注意，第二码错误检测与纠正部530纠正毗邻纠正已失败的第一码 字的部分数据中的两者(部分数据#1和#3)；然而，第二码错误检测与纠正 部530可纠正部分数据中的仅一者。当纠正部分数据之一时，纠正用于纠 正的对象部分数据中的第二奇偶校验#1和第二奇偶校验#2之一中的错 误。当纠正毗邻部分数据中的仅一者时，与纠正毗邻部分数据中的两者 的情况相比，第二码错误检测与纠正部530可以更高的速度纠正数据中的 错误。

图15为图示根据第一实施例的存储控制器300的操作的流程图。例 如，操作可在存储控制器300通电时开始。

存储控制器300判断是否已从主机系统100接收到写入命令(步骤 S910)。在存储控制器300已接收到写入命令的情况下(步骤S910：是)， 存储控制器300执行编码以对写入数据进行编码(步骤S920)。存储控制 器300将编码为第二码字的写入数据写入到非易失性存储器600(步骤 S930)。在步骤S930之后，存储控制器300回到步骤S910。

在存储控制器300尚未接收到写入命令的情况下(步骤S910：否)， 存储控制器300判断是否已接收到读取命令(步骤S940)。在存储控制器 300已接收到读取命令的情况下(步骤940：是)，存储控制器300读取编 码为第一码字的读取数据(步骤S950)。然后，存储控制器300执行解码 以对编码后的读取数据进行解码(步骤S960)。在存储控制器300尚未接 收到读取命令的情况下(步骤S940：否)，或在步骤S960之后，存储控制 器300回到步骤S910。

图16为图示根据第一实施例编码的示例的流程图。存储控制器300将 作为用于第一编码的对象数据的每个写入数据编码为第一码字(步骤 S921)。存储控制器300将多个第一码字编码为第二码字(步骤S922)。在 步骤S922之后，存储控制器300终止编码。

图17为图示根据第一实施例的解码的示例的流程图。存储控制器300 纠正每个第一码字中的错误(步骤S961)。存储控制器300判断对任一个 第一码字的纠错是否已失败(步骤S962)。在对任一个第一码字中的纠错 已失败的情况下(步骤S962：是)，存储控制器300执行第二编码错误检 测与纠正，以纠正含有纠正已失败的第一码字的部分数据中的错误(步 骤S970)。在对所有第一码字的纠错成功的情况下(步骤S962：否)，或 在步骤S970之后，存储控制器300从错误被纠正的第一码中获得用于第一 编码的对象数据，并输出用于第一编码的对象数据(步骤S963)。在步骤 S963之后，存储控制器300终止解码。

图18为图示根据第一实施例的第二编码错误检测与纠正的示例的流 程图。存储控制器300获取与检测到错误的部分数据毗邻的毗邻部分数据 (步骤S971)。然后，存储控制器300纠正这些毗邻部分数据中的错误(步 骤S972)。然后，存储控制器300将纠错成功的毗邻第一码用作已知位， 从而纠正含有检测到错误的第一码字的部分数据中的错误(步骤S973)。

因此，在第一实施例中，存储控制器300将用于编码的每一个对象数 据编码为第一码字，并以连锁方式对第一码字进行编码以生成第二码字。 此外，存储控制器300可以基于第二码字中含有检测到错误的第一码字的 部分数据之前或之后的编码后的部分数据之一或两者来纠正数据中的错 误。因此，与纠正整个第二码字中的错误的情况相比，存储控制器300可 以更高的速度纠正错误。此外，与只纠正含有检测到错误的第一码字的 部分数据的情况相比，存储控制器300可以更精确地纠正错误。

(第一变型例)

在第一实施例中，如图10所示例，采用向每一个第一码字添加第二 奇偶校验的结构作为第二码的数据结构；然而，第二码的数据结构不仅 限于此。根据第一实施例的第一变型例的存储控制器300与根据第一实施 例的存储控制器的不同之处在于为每一固定数目的第一码字一起地输出 第二奇偶校验。

图19图示根据第一实施例的第一变型例的第二码的数据结构的示 例。如图19中所示例，根据第一变型例的存储控制器300为每一固定数目 的第一码字一起地输出第二奇偶校验。下文中，将含有固定数目的第二 奇偶校验的数据称作“第二奇偶块”。例如，调整第二奇偶块中的第二奇 偶的数目，以使得第二奇偶块的大小等于非易失性存储器600的访问单位 的除数或倍数。

(第二变型例)

在第一实施例中，使用为第一编码及第二编码所共有的单位来执行 编码；然而，第一编码的单位可不同于解码单位。根据第一实施例的第 二变型例的存储控制器300与根据第一实施例的存储控制器的不同之处 在于，以与第一编码的单位不同的单位对第二码字进行解码。

图20为用于描述根据第一实施例的第二变型例的第二码字的数据结 构的示例的图示。例如，在对第一码字#1～#4进行编码的情况下，在第 二变型例中，如图20中所示例，含有第一码字#1和#2的部分可为部分数 据#1，且含有第一码字#3和#4的部分可为部分数据#2。因此，使得存储 控制器300在与第一编码的单位不同的单位对第二码字进行解码。

(第三变型例)

在第一实施例中，对整个第一码字进行编码；然而，存储控制器300 可对第一码字的部分进行编码。根据第一实施例的第三变型例的存储控 制器300与根据第一实施例的存储控制器的不同之处在于，存储控制器 300对第一码字的部分进行编码。

图21为用于描述根据第一实施例的第三变型例的第二码字的数据结 构的示例的图示。如图21中所示例，根据第三变型例的存储控制器300可 对第一码字的仅部分进行编码，例如，仅仅将无第一奇偶校验的用于第 一编码的对象数据编码为部分数据。因此，可以缩减第二码字的编码长 度。第一奇偶校验未在图21中图示。

(第四变型例)

在第一实施例中，在纠正与对象部分数据毗邻的部分数据中的错误 之后，纠正用于纠正的对象部分数据中的错误；然而，存储控制器300可 纠正作为一个解码单位的这些部分数据的组合。根据第一实施例的第四 变型例的存储控制器300与根据第一实施例的存储控制器的不同之处在 于，存储控制器300一起地纠正用于纠正的对象部分数据及与其毗邻的部 分数据。更具体而言，校验矩阵生成部531将用于纠正的对象部分数据的 校验矩阵和与其毗邻的部分数据的校验矩阵相互组合，以生成列数等同 于数据的大小的校验矩阵，所述数据含有用于纠正的对象部分数据以及 与其毗邻的部分数据。校验矩阵生成部531将如此生成的校验矩阵供应给 第二码错误检测与纠正器540，且第二码错误检测与纠正器540使用校验 矩阵来纠正作为一个解码单位的用于纠正的对象部分数据以及与其毗邻 的部分数据的组合。

图22为图示根据第一实施例的第四变型例的第二编码错误检测与纠 正的示例的流程图。根据第一实施例的第四变型例的第二编码错误检测 与纠正与根据第一实施例的第二编码错误检测与纠正的不同之处在于执 行步骤S981和S982，而不是执行步骤S972和S973。在第四变型例中，存 储控制器300获取与检测到错误的第一码字毗邻的毗邻部分数据(步骤 S971)，并获取含有检测到错误的第一码字的部分数据(步骤S981)。然 后，存储控制器300一起地执行对这些所获取的部分数据的纠错(步骤 S982)。

(第五变型例)

图23为用于描述根据第一实施例的第五变型例纠正第二码的方法的 图示。例如，考虑其中纠正含有第一码字#1、#2和#3的第二码的情况。 这些第一码字中的第一码字#2具有不可纠正数目的错误。

第一码错误检测与纠正部520纠正各个第一码字#1、#2和#3中的错 误。在此纠正中，第一码错误检测与纠正部520未能纠正具有不可纠正数 目的错误的第一码字#2。

在此情况下，第二码错误检测与纠正部530一起地对纠正已失败的第 一码字#2以及与其毗邻的部分数据#1和#3进行纠正。通过纠正这些部分 数据来纠正第一码字#2中的错误。在纠正毗邻部分数据(#1和#3)且随 后纠正用于纠正的对象部分数据(#2)的方法中，在对毗邻部分数据的 纠错已失败的情况下，可使用毗邻部分数据中具有错误的第二奇偶校验 来纠正用于纠正的对象奇偶校验数据。另一方面，在第五变型例中，一 起地纠正毗邻部分数据及用于纠正的对象部分数据；因此，排除使用具 有错误的奇偶校验来执行纠错的可能性，且提高了纠错能力。

(2.第二实施例)

(第二码错误检测与纠正部的配置示例)

图24为图示根据第二实施例的第二码错误检测与纠正部530的配置 示例的方块图。在第一实施例中，第二码错误检测与纠正部530基于与用 于纠正的对象部分数据毗邻的部分数据来纠正用于纠正的对象部分数据 中的错误，而不管对与用于纠正的对象部分数据毗邻的部分数据的纠正 的结果如何。然而，在对与用于纠正的对象部分数据毗邻的部分数据的 纠正已失败的情况下，当基于纠正已失败的与用于纠正的对象部分数据 毗邻的部分数据以执行对用于纠正的对象部分数据的纠错时，对对象部 分数据的纠正失败的可能性增加。因此，在对与用于纠正的对象部分数 据毗邻的部分数据的纠正已失败的情况下，优选的是使用这样一种纠正 方法，即纠正与对象部分数据毗邻的部分数据毗邻的部分数据中的错误， 且追溯毗邻部分数据直到纠正成功为止。根据第二实施例的第二码错误 检测与纠正部530与根据第一实施例的第二码错误检测与纠正部的不同 之处在于追溯毗邻部分数据直到纠正成功为止。

更具体而言，在根据第二实施例的第二码错误检测与纠正器540中， 变量节点处理部541将表示对部分数据的纠正是否已失败的纠正结果输 出到部分数据生成部532。例如，在消息交换固定次数的情况下，当多位 之一的对数似然比的绝对值不超过阈值时，可判断纠正已失败。在基于 纠正结果对毗邻部分数据的纠正已失败的情况下，部分数据生成部532获 取与毗邻部分数据毗邻的部分数据作为新的毗邻部分数据，并将新的毗 邻部分数据输出到变量节点处理部541。应注意，在第二实施例中，如同 第一实施例一样，第二码不仅限于空间耦合LDPC码。例如，代替空间耦 合LDPC码，可使用稍后将阐述的卷积码或turbo码。此外，第二编码部420 可使用比二进制高的码作为第二码。这也适用于第二实施例的各个变型 例。

(存储控制器的操作示例)

图25为图示根据第二实施例的第二码错误检测与纠正的示例的流程 图。根据第二实施例的第二码错误检测与纠正与根据第一实施例的第二 码错误检测与纠正的不同之处在于还执行步骤S974、S975和S977。

存储控制器300纠正与检测到错误的第一码字毗邻的毗邻部分数据 (步骤S972)，并判断纠正是否成功(步骤S974)。在纠正已失败的情况 下(步骤S974：否)，存储控制器300获取与纠正已失败的毗邻部分数据 毗邻的部分数据作为新的毗邻部分数据(步骤S975)，且回到步骤S972。 另一方面，在纠正成功的情况下(步骤S974：是)，存储控制器300以与 追溯顺序相反的顺序依次纠正部分数据，并纠正检测到错误的用于纠正 的对象部分数据(步骤S977)。在步骤S977之后，存储控制器300终止第 二码错误检测与纠正。

图26为用于描述根据第二实施例纠正第二码的方法的图示。例如， 考虑纠正含有第一码字#1～#4的第二码中的错误的情况。这些第一码字 中的第一码字#2和#3各自具有由第一码错误检测与纠正部520不可纠正 的数目的错误。对应于各个第一码字生成的第二奇偶校验#1、#2和#3中 的每一个也具有错误。

第一码错误检测与纠正部520纠正各个第一码字#1～#4中的错误。在 此纠正中，第一码错误检测与纠正部520未能纠正具有不可纠正数目的错 误的第一码字#2和#3。

第二码错误检测与纠正部530纠正与纠正已失败的第一码字#2毗邻 的部分数据#1和#3中的错误。假定第二码错误检测与纠正部530成功纠正 含有无错误的第一码字#1的部分数据#1，但未能纠正含有具有错误的第 一码字#3的部分数据#3。在此情况下，第二码错误检测与纠正部530纠正 与纠正已失败的部分数据#3毗邻的部分数据#4中的错误。

当对部分数据#4的纠正成功时，第二码错误检测与纠正部530对纠正 已失败的部分数据#3中的错误进行纠正。由于第二奇偶校验#3中的错误 是通过纠正部分数据#4来纠正的，因此可以精确地纠正含有第二奇偶校 验#3的部分数据#3。在对部分数据#3的纠正成功的情况下，第二码错误 检测与纠正部530对纠正已失败的部分数据#2中的错误进行纠正。由于第 二奇偶校验#2中的错误是通过纠正部分数据#3来纠正的，因而可以精确 地纠正含有第二奇偶校验#2的部分数据#2。

因此，在第二实施例中，通过追溯部分数据直到对毗邻部分数据的 纠正成功为止，可以基于纠正成功的毗邻部分数据来纠正所检测到的错 误。因此，可以更精确地纠正数据中的错误。

(第一变型例)

在第二实施例中，不管第一码字的解码结果如何，追溯毗邻部分数 据直到纠正成功为止。然而，在对第一码字的纠正已失败的情况下，对 含有第一码字的部分数据的纠正失败的可能性高。因此，在追溯部分数 据的情况下，优选的是跳过含有纠正已失败的第一码字的部分数据。根 据第二实施例的第一变型例的存储控制器300与根据第二实施例的存储 控制器的不同之处在于存储控制器300追溯部分数据，同时跳过含有纠正 已失败的第一码字的部分数据。

图27为图示根据第二实施例的第一变型例的第二码错误检测与纠正 的示例的流程图。根据第二实施例的第一变型例的第二码错误检测与纠 正与根据第二实施例的第二码错误检测与纠正的不同之处在于还执行步 骤S976。

在对部分数据的纠错已失败的情况下(步骤S974：否)，存储控制器 300获取与纠正已失败的部分数据毗邻的部分数据(步骤S975)。然后， 存储控制器300基于错误检测块通知来判断对含于毗邻部分数据中的第 一码字的纠正是否成功(步骤S976)。在对第一码字的纠正已失败的情况 下(步骤S976：否)，存储控制器300回到步骤S975，并获取与含有纠正 已失败的第一码字的部分数据毗邻的部分数据。另一方面，在对第一码 字的纠正成功的情况下(步骤S976：是)，存储控制器300回到步骤S972。

图28为用于描述根据第二实施例的第一变型例的纠正第二码的方法 的图示。例如，考虑纠正含有第一码字#1～#4的第二码中的错误的情况。 假定第一码错误检测与纠正部520未能纠正具有不可纠正数目的错误的 第一码字#2和#3。

第二码错误检测与纠正部530基于错误检测块通知来判断对与纠正 已失败的第一码字#2毗邻的第一码字#1和#3的纠正是否成功。对第一码 字#1的纠正成功，但对第一码字#3的纠正已失败；因此，码错误检测与 纠正部530跳过纠正已失败的第一码字#3，并判断对毗邻第一码字#3的第 一码字#4的纠正是否成功。由于对第一码字#4的纠正成功，因而第二码 错误检测与纠正部530纠正含有第一码字#4的部分数据#4中的错误。

因此，通过追溯毗邻部分数据、同时跳过含有纠正已失败的第一码 字的部分数据，可以基于具有高纠正成功可能性的部分数据来纠正所检 测到的错误。因此，可以更精确地纠正数据中的错误。

(第二变型例)

在第二实施例中，当对毗邻部分数据的纠正已失败时，存储控制器 300追溯毗邻部分数据直到纠正成功为止。然而，为了可靠地纠正数据， 与对第二码字的部分进行解码相比，对整个第二码字进行解码更加优选。 第二实施例的第二变型例与第二实施例的不同之处在于，当对毗邻部分 数据的纠正已失败时，存储控制器300对整个第二码字进行解码。

图29为图示根据第二实施例的第二变型例的第二码错误检测与纠正 的示例的流程图。根据第二实施例的第二变型例的第二码错误检测与纠 正与根据第二实施例的第二码错误检测与纠正的不同之处在于还执行步 骤S974、S983和S984。

存储控制器300纠正与检测到错误的第一码字毗邻的毗邻部分数据 (步骤S972)，并判断纠正是否成功(步骤S974)。在纠正已失败的情况 下(步骤S974：否)，存储控制器300读取整个第二码字(步骤S983)，并 纠正第二码字中的错误(步骤S984)。另一方面，在纠正成功的情况下(步 骤S974：是)，存储控制器300执行步骤S973。在步骤S973或步骤S984之 后，存储控制器300终止第二码错误检测与纠正。

(3.第三实施例)

(第二编码部的配置示例)

在第一实施例中，使用LDPC作为第二码，其中数据的一部分为彼此 毗邻的部分数据所共有；然而，可使用卷积码作为第二码。根据第三实 施例的存储控制器300与根据第一实施例的存储控制器的不同之处在于 使用卷积码作为第二码。图30为图示根据第三实施例的第二编码部420的 配置示例的方块图。根据第三实施例的第二编码部420与根据第一实施例 的第二编码部的不同之处在于包括第二编码器430，而不是包括第二编码 器423。

第二编码器430用于使用卷积编码系统来将第一码字编码为第二码 字。第二编码器430例如包括半加器431、434以及寄存器432、433。

半加器431用于输出输入值的异或。构成第一码字的位之一输入到半 加器431作为用于第二编码的对象位r_m，其中“m”为0～Nf-1的整数，且 “Nf”为第一码字的码长。此外，从寄存器432和433输出的位输入到半 加器431。半加器431将位的异或输出到寄存器432和半加器434。

寄存器432用于保持来自半加器431的输出值。寄存器432响应于预定 时钟信号将所保持的值输出到寄存器433和半加器431。应注意，由寄存 器432保持的值的初始值可设定为例如“0”。

寄存器433用于保持来自寄存器432的输出值。寄存器433响应于预定 时钟信号而将值输出到半加器431和434。应注意，由寄存器433保持的值 的初始值可设定为例如“0”。

半加器434用于输出输入值的异或。从半加器431和寄存器433输出的 位输入到半加器434。半加器434输出位的异或作为第二奇偶位C_m。

第二编码器430将含有用于第二编码的对象位r_m和第二奇偶位C_m的 码字作为第二码字存储在编码数据缓冲器460中。通过卷积编码所生成的 第二码字的部分数据的大小Ns可设定为例如非易失性存储器600的访问 单位的除数。应注意，部分数据的大小Ns可设定为非易失性存储器600 的访问单位的倍数。

输出针对用于第二编码的过去对象位和用于第二编码的现在对象位 的卷积运算的结果作为现在的第二码校验位。

(第二编码部的状态转换图)

图31为图示根据第三实施例的第二编码器430的状态转换的示例的 状态转换图。第二编码器430具有包括S₀、S₁、S₁和S₁的四种状态。S₀为 由寄存器432和433保持的值为“00”的状态，且S₁为该值为“10”的状 态。此外，S₂为由寄存器432和433保持的值为“01”的状态，且S₃为该 值为“11”的状态。

寄存器432和433可例如保持“00”作为初始值；因此，第二编码器 430的初始状态可设定为S₀。应注意，初始状态可设定为除S₀以外的状态 中的任一者。

在状态S₀中，当输入具有值“0”的用于第二编码的对象位r_m时，第 二编码器430执行呈图30中所示例的配置的卷积运算，并通过计算来求出 “0”作为第二奇偶位C_m。因此，输出通过添加输入值“0”所得到的值 “00”。寄存器432和433中所保持的值仍为“00”；因此，第二编码器430 仍处于状态S₀下。另一方面，当在状态S₀下输入值“1”时，第二编码器 430输出值“11”，且转换为状态S₁。

当在状态S₁下输入值“0”时，第二编码器430输出值“01”，且转换 为状态S₃。另一方面，当在状态S₁下输入值“1”时，第二编码器430输 出值“10”，且转换为状态S₂。

当在状态S₂下输出值“0”时，第二编码器430输出值“00”，且转换 为状态S₁。另一方面，当在状态S₂下输入值“1”时，第二编码器430输 出值“11”，且转换为状态S₀。

当在状态S₃下输出值“0”时，第二编码器430输出值“01”，且转换 为状态S₂。另一方面，当在状态S₃下输入值“1”时，第二编码器430输 出值“10”，且保持在状态S₃。

因此，第二编码器430基于输入值和现在状态并根据某一规则来输出 构成第二码的位列并且执行状态转换。因此，使得第二码错误检测与纠 正部530基于第二编码器430的状态转换规则来纠正第二码中的错误。

图32为用于描述根据第三实施例生成第二码的方法的示例的图示。 当用于第二编码的第一对象位r₀输入到保持初始值“00”的第二编码器430 时，通过针对r₀和“00”的运算所生成的第一第二奇偶位C₀连同对象位r₀ 被一起输出。然后，第二编码器430的前级中的寄存器保持通过针对r₀和 值“00”的运算所生成的“r₀’”。

接下来，当输入用于第二编码的第二对象位r₁时，通过针对r₁、r₀’和 “0”的运算所生成的第二第二奇偶位C₁连同r₁被一起输出。然后，第二 编码器430的后级中的寄存器保持前级中的“r₀’”，且第二编码器430的前 级中的寄存器保持通过针对r₁等等的运算所生成的“r₁’”。

因此，基于针对前级中的数据的卷积运算的结果来判断第二码字中 每一数据的值。

(第二码错误检测与纠正部的配置示例)

图33为图示根据第三实施例的第二码错误检测与纠正部530的配置 示例的方块图。根据第三实施例的第二码错误检测与纠正部530与根据第 一实施例的第二码错误检测与纠正部的不同之处在于包括第二码错误检 测与纠正器550，而不包括校验矩阵生成部531和第二码错误检测与纠正 器540。

第二码错误检测与纠正器550用于纠正部分数据中的错误，且可使用 例如维特比(Viterbi)算法来纠正部分数据中的错误。

在维特比算法中，根据图31中所示例的状态转换规则，按时间序列 顺序布置第二编码器430的状态，且求出从连接这些状态的网格(trellis) 路径中选出的最高似然的路径。下文中，将网格路径简称为“路径”。更 具体而言，通过计算来求出每一路径中所生成的数据与从非易失性存储 器600读取的部分数据之间的汉明(hamming)距离，且选择具有最短汉 明距离(路径度量)的路径。所选路径中生成的数据作为已被纠错的数 据输出。

第二码错误检测与纠正器550基于数据的大小来对按时间序列顺序 布置的状态进行区块划分，并使用维特比算法来纠正部分数据。第二码 错误检测与纠正器550首先通过维特比算法来执行对与对象部分数据毗 邻的数据的解码，且随后使用所求出的起点或终点状态来对对象部分数 据进行解码。更具体而言，如果毗邻部分数据为用于纠正的对象部分数 据之后的部分数据，则使用毗邻部分数据的起点状态来执行对对象部分 数据的解码，且如果毗邻部分数据为用于纠正的对象部分数据之前的部 分数据，则使用毗邻部分数据的终点状态来对对象部分数据进行解码。 确定路径(网格路径)的起点或终点状态称作“终止网格”。对对象路径 的搜索因网格终止而变窄；因此，可以更精确地纠正数据中的错误。

第二码错误检测与纠正器550可使用除维特比算法以外的任何能够 纠正卷积编码数据中的错误的算法。

图34A和图34B为图示根据第三实施例的第二编码部的状态转换的 示例的网格图的示例。考虑其中从非易失性存储器600依次读取部分数据 #1～#3且对部分数据#2中所包含的第一码字的纠正已失败的情况。假定 对部分数据#1和#3中的第一码字的纠正成功。在图34A和图34B中，水平 轴表示部分数据读取时间。白圆圈标记表示第二编码器430的状态。状态 之间的虚线表示路径中的分支，且实线表示具有最高似然的路径中的分 支。

图34A图示在纠正部分数据#2之前的网格图的例子。存储控制器300 使用维特比算法来纠正与纠正已失败的部分数据#2毗邻的部分数据#1和 #3。存储控制器300基于纠正结果来求出部分数据#1的终点处的状态S₃及 部分数据#3的起点处的状态S₀。

图34B图示纠正部分数据#2时的网格图的例子。存储控制器300在纠 正部分数据#2时，将纠正部分数据#1时求出的终点S₀作为起点、并且将 纠正部分数据#3时求出的起点S₃作为终点，从而终止网格。图34B中的带 阴影的圆圈标记表示终止状态。对路径的搜索因网格终止而变窄；因此， 可以更精确地纠正数据中的错误。

因此，在第三实施例中，存储控制器300可以使用作为第二码的卷积 码来执行纠错。因此，在使用卷积编码系统的系统中，可以高速度精确 地纠正数据中的错误。

(4.第四实施例)

(第二编码部的配置示例)

在第一实施例中，使用其中数据的一部分为彼此毗邻的部分数据所 共有的LDPC码作为第二码；然而，可使用turbo码作为第二码。根据第四 实施例的存储控制器300与根据第一实施例的存储控制器的不同之处在 于使用turbo码作为第二码。

图35为图示根据第四实施例的第二编码部420的配置示例的方块图。 根据第四实施例的第二编码部420与根据第一实施例的第二编码部的不 同之处在于包括第二编码器440，而不包括第二编码对象数据生成部421 及第二编码器423。

第二编码器440包括预交错第二编码器441、延迟缓冲器442、交错器 443、后交错第二编码器444及切换器445。

预交错第二编码器441用于使用卷积编码系统来将用于第二编码的 对象数据编码为第二码字。除了预交错第二编码器441只生成第二码校验 位，预交错第二编码器441的配置可类似于例如根据第三实施例的第二编 码器430。预交错第二编码器441将所生成的第二奇偶位bC_m输出到切换器 445，其中“m”为0～Nf-1的整数，且Nf为第一码字(即，用于第二编 码的对象数据)的码长。

延迟缓冲器442用于延迟用于第二编码的对象数据到交错器443的输 出，直到预交错第二编码器441中的编码完成为止。

交错器443用于通过延迟缓冲器442来获取用于第二编码的对象数 据，并执行对用于第二编码的对象数据的交错。通过此交错增大针对突 发性错误的纠错能力。当交错完成时，交错器443控制切换器445，并开 始从预交错第二编码器441输出第二码校验位。交错器443将交错后的用 于第二编码的对象数据输出到后交错第二编码器444。

后交错第二编码器444用于将数据被交错的第二编码的对象数据编 码为第二码字。后交错第二编码器444将所生成的第二奇偶位aC_m输出到 切换器445。

切换器445基于交错器443的控制输出第二奇偶位bC_m或aC_m。切换器 445在交错之前从预交错第二编码器441输出第二奇偶位bC_m，并在交错之 后从后交错第二编码器444输出第二奇偶位aC_m。

第二编码器440将含有用于第二编码的对象位r_m和第二奇偶位bC_m及 aC_m的码输出到编码数据缓冲器460作为第二码。使用在数据的交错之前 生成的第二奇偶位bC_m来对第二码的部分或全部进行解码。另一方面，在 对第二码的部分的解码已失败的情况下，使用在数据的交错之后生成的 第二奇偶位aC_m来对整个第二码进行解码。

(第二码错误检测与纠正部的配置示例)

图36为图示根据第四实施例的第二码错误检测与纠正部530的配置 示例的方块图。根据第四实施例的第二码错误检测与纠正部530与根据第 一实施例的第二码错误检测与纠正部的不同之处在于包括第二码错误检 测与纠正器560，而不包括校验矩阵生成部531和第二码错误检测与纠正 器540。

根据第四实施例的部分数据生成部532从解码后的第一码字和第二 奇偶校验生成部分数据，并将部分数据供应给第二码错误检测与纠正器 560。

第二码错误检测与纠正器560包括预交错第二码纠正器561、交错器 562、后交错第二码纠正器563和解交错器564。

预交错第二码纠正器561用于纠正其中数据尚未交错的第二码字中 的错误。预交错第二码纠正器561可使用例如BCJR(Bahl Cocke Jelinek Raviv)算法来纠正第二码字中的错误。

在使用BCJR算法的情况下，预交错第二码纠正器561从部分数据生 成部532接收部分数据，并从解交错器564接收事前信息Le(u_k)，其中事前 信息Le(u_k)为由后交错第二码纠正器563求出的第k符号(例如，位)u_k的 对数似然比，“k”为0～Nt-1的整数，且“Ns”为用于纠正的对象数据的 大小。应注意，事前信息Le(u_k)并不是在初始状态下求出；因此，事前 信息Le(u_k)设定为预定初始值(例如，“0”)。此外，用于纠正的对象数据 可为第二码字的部分数据或整个第二码字。

预交错第二码纠正器561从所接收到的数据获得用于第二编码的对 象位r_m及在交错之前生成的第二奇偶位bC_m。然后，预交错第二码纠正 器561通过使用下列表达式13的计算来求出先前状态通过概率α_k(s)，其中 “s”为预交错第二编码器441的状态。此外，先前状态通过概率α_k(s)为 经过各个第0～第k-1状态来使第k状态变成状态“s”的概率。

[数学式13]

${\alpha }_k\left(s\right)=\underset{s^{\prime }}{\Sigma }{\gamma }_k(s^{\prime },s)·{\alpha }_{k-1}\left(s^{\prime }\right)$…表达式13

在表达式13中，γk(s′，s)为从状态“s’”转换到状态“s”的概率，且 是通过下列表达式14求出。

[数学式14]

γ_k(s，s′)＝P(u_k)·p(r_k|u_k)…表达式14

在表达式14中，P(u_k)是使用事前信息Le(u_k)通过下列表达式15求出。 此外，p(r_k|u_k)为依赖于从编码数据供应部470到第一码错误检测与纠正部 520或第二码错误检测与纠正部560的通信信道的概率，且是通过下列表 达式16求出。

[数学式15]

$P\left(u_k\right)=\left(\frac{e^{-\mathrm{Le}\left(u_k\right)/2}}{1+e^{-\mathrm{Le}\left(u_k\right)}}\right)·e^{(u_k-\frac{1}{2})\mathrm{Le}\left(u_k\right)}$…表达式15

[数学式16]

$p\left(r_k\right|u_k)=\underset{i}{\Pi }{\frac{1}{\sqrt{\pi ·N_0/\mathrm{Es}}}e}^{-\frac{\mathrm{Es}}{N_0}{(r_k-u_k)}^2}$…表达式16

在表达式18中，Es为从编码数据供应部470到第一码错误检测与纠正 部520或第二码错误检测与纠正部560的通信信道中的每一位信号的能 量，且Es的单位可为例如焦耳(J)，且N₀为通信信道的噪声功率密度且 N₀的单位可为例如瓦特/赫兹(W/Hz)。Es/N₀可将例如加性白高斯噪声 (AWGN)通信信道考虑在内而计算得出。

如果从部分数据生成部532接收到起点状态，则预交错第二码纠正器 561基于该状态终止网格。例如，在表达式14中，其中“s”对应于起点 状态的γ(s′，s)的概率被最大化。

此外，预交错第二码纠正器561通过使用下列表达式17的计算来求出 后续状态通过概率β_k(s)，其中后续状态通过概率β_k(s)为通过各个第 Ns-1～第k+1状态使第k状态变为状态“s”的概率，其中第Ns-1状态为 结束时的状态。

[数学式17]

${\beta }_k\left(s\right)=\underset{s^{\prime }}{\Sigma }{\gamma }_{k+1}(s^{\prime },s)·{\beta }_{k+1}\left(s^{\prime }\right)$…表达式17

如果从部分数据生成部532接收到终点状态，则预交错第二码纠正器 561基于该状态终止网格。例如，在表达式17中，“s’”对应于终点状态 的γ(s′，s)的概率被最大化。

然后，预交错第二码纠正器561通过使用下列表达式18的计算从表达 式13、14和17的计算结果求出对数似然比Λ(u_k)。

[数学式18]

$\Lambda \left(u_k\right)=\ln \frac{\underset{(s^{\prime },s)u_k=1}{\Sigma }{\alpha }_k\left(s^{\prime }\right)\gamma (s^{\prime },s){\beta }_k\left(s\right)}{\underset{(s^{\prime },s)u_k=0}{\Sigma }{\alpha }_k\left(s^{\prime }\right)\gamma (s^{\prime },s){\beta }_k\left(s\right)}$…表达式18

接下来，预交错第二码纠正器561判定是否满足预定终止条件，且在 满足终止条件的情况下，基于所求出的对数似然比Λ(u_k)来求出纠正后数 据的位u_k的值，且将该值输出到解码数据缓冲器570及部分数据生成部 532。例如，在预交错第二码纠正器561与后交错第二码纠正器563之间交 换信息的次数超过预定次数时或当对数似然比Λ(u_k)的绝对值超过阈值 时，可判断满足终止条件。然而，在对第二码的一部分进行解码的情况 下，不在预交错第二码纠正器561与后交错第二码纠正器563之间交换信 息；因此，当对数似然比的绝对值超过阈值时，满足终止条件。纠正后 的位u_k的值可在对数似然比Λ(u_k)为正值的情况下判断为“1”，且纠正后 的位u_k的值可在对数似然比Λ(u_k)为负值的情况下判断为“0”。

另一方面，在未满足终止条件的情况下，预交错第二码纠正器561判 定是否已接收到整个部分数据。在尚未接收到整个部分数据(即，第二码 字)且对第二码字的一部分进行解码的情况下，预先交错第二码纠正器 561生成表示纠正已失败的纠正结果，并将该纠正结果输出到部分数据生 成部532。另一方面，在已接收到整个部分数据(第二码字)的情况下，预 交错第二码纠正器561通过使用下列表达式19及20的计算来求出来自从 部分数据生成部532接收到的第二码字及对数似然比Λ(u_k)的外部信息 L(u_k)。预交错第二码纠正器561将所求出的外部信息L(u_k)连同所接收到 第二码字输出到交错器562。

[数学式19]

L(u_k)＝Λ(u_k)-L_c(u_k)-L_ch(u_k)

…表达式19

[数学式20]

$L_{\mathrm{ck}}\left(u_k\right)=\ln \frac{P\left(r_k\right|u_k=1)}{P\left(r_k\right|u_k=0)}$…表达式20

交错器562用于随机交错来自预交错第二码纠正器561的第二码字与 外部信息L(u_k)。交错器562将交错后的外部信息L(u_k)作为后交错第二码 纠正器563中的事前信息连同交错后的第二码字一起输出到后交错第二 码纠正器563。

在后交错第二码纠正器563中的解码已失败的情况下，后交错第二码 纠正器563读取整个第二码字，并执行对第二码字的解码。在读取整个第 二码字的情况下，与其中读取第二码字的一部分的情况相比需要更长的 读取时间；因此，只有在部分解码已失败的情况下才执行对整个第二码 字的读取。

后交错第二码纠正器563用于纠正其中数据被交错的第二码字中的 错误。后交错第二码纠正器563从交错器562接收事前信息及第二码字， 且从第二码字获得用于第二编码的对象位u_k及第二奇偶位aC_k。后交错第 二码纠正器563使用类似于预交错第二码纠正器561中所使用的方法的方 法基于事前信息及第二码字来求出外部信息。后交错第二码纠正器563将 外部信息及第二码字输出到解交错器564。

解交错器564用于使交错后的第二码字及交错后的外部信息返回到 交错之前的状态。解交错器564将交错之前的外部信息作为预交错第二码 纠正器561中的外部信息连同交错之前的第二码字一起输出到预交错第 二码纠正器561。

因此，在第四实施例中，可以将turbo码用作第二码来纠正数据中的 错误，在所述turbo码中通过交错数据来执行编码。因此，提高了针对突 发性错误的纠错能力。此外，在对第二码的部分的解码已失败的情况下 执行对整个第二码的解码；因此，与其中只执行部分解码的情况相比提 高了纠错能力。

(5.第二实施例)

(第二编码部的配置示例)

在第一实施例中，存储控制器300不生成针对第二奇偶校验的奇偶校 验。然而，存储控制器300可还生成针对第二奇偶校验的奇偶校验以纠正 第二奇偶校验中的错误。根据第五实施例的存储控制器300与根据第一实 施例的存储控制器的不同之处在于还生成针对第二奇偶校验的奇偶校 验。应注意，在第二～第四实施例中，可还生成针对第二奇偶校验的奇 偶校验。

图37为图示根据第五实施例的第二编码部420的配置示例的方块图。 根据第五实施例的第二编码部420与根据图30中所示例的第三实施例的 第二编码部的不同之处在于还包括奇偶校验数据缓冲器541及第一编码 器452。

奇偶校验数据缓冲器451用于保持每一第二奇偶校验作为第二奇偶 校验数据。第一编码器452用于将由奇偶校验数据缓冲器451保持的第二 奇偶校验数据编码为第一码字。第一编码器452将所生成的第一码字存储 于编码数据缓冲器460中。

图38为图示根据第五实施例的第二码的数据结构的示例的图示。第 二码含有多个第一码字。这些第一码字中的一些第一码字为用于第一编 码的编码后的对象数据，且其余第一码字为编码后的第二奇偶校验数据。 例如，第一码字#1～#8可为用于第一编码的编码后的对象数据，且第一 码字#9可为编码后的第二奇偶校验数据。第一码字#9含有第二奇偶校验 数据及第一奇偶校验#9。此第二奇偶校验数据可含有用于对第一码字 #1～#8进行纠错的第二奇偶校验#1～#9。

(第二码错误检测与纠正部的配置示例)

图39为图示根据第五实施例的第二码检测与纠正部530的配置示例 的方块图。根据第五实施例的第二码错误检测与纠正部530的配置与根据 第一实施例的第二码错误检测与纠正部的不同之处在于还包括第一码错 误检测与纠正器533。

第一码错误检测与纠正器533用于检测并纠正第二奇偶校验中的错 误。更具体而言，第一码错误检测与纠正器533检测并纠正输入的毗邻部 分数据中含有第二奇偶校验的第一码字中的错误，且从第一码字获得毗 邻部分数据的第二奇偶校验，并将第二奇偶校验供应给部分数据生成部 532。部分数据生成部532从所解码的第一码字及第二奇偶校验生成部分 数据，并将部分数据供应给第二码错误检测与纠正器550。

因此，在第五实施例中，存储控制器300可以纠正第二奇偶校验中的 错误；因此，可以更精确地纠正数据中的错误。

(6.第六实施例)

(第二编码部的配置示例)

在第一实施例中，存储控制器300将数据编码为第一码及第二码；然 而，存储控制器300可将数据编码为除第一码及第二码以外的码。根据第 六实施例的存储控制器300与根据第一实施例的存储控制器的不同之处 在于还生成除第一码及第二码以外的码。

图40为图示根据第六实施例的第二编码部420的配置示例的方块图。 根据第六实施例的第二编码部420与根据第一实施例的第二编码部的不 同之处在于还包括第三编码器423。第三编码器423用于将用于第二编码 的对象数据编码为第三码。假定第二编码器422及第三编码器423保持生 成矩阵。

不同于第二码，第三码为可以对其进行部分解码的码。在第二码为 空间耦合LDPC码的情况下，例如，可使用通常的LDPC码作为第三码。 在共同错误检测与纠正器中，可以使用空间耦合LDPC码及LDPC码来对 这些码进行解码。第三码含有多个第三码字，且当使用所有第三码字来 纠正错误时，与部分地纠正第二码的情况相比可以纠正更多的错误。因 此，当对第二码的纠错已失败时使用第三码。

第三编码器423将第三码字中的每一个存储于编码数据缓冲器460 中。根据第六实施例的第二编码器422如同第一实施例一样执行变成空间 耦合LDPC码的编码。

图41为图示根据第六实施例的校验矩阵的示例的图示。根据第六实 施例的校验矩阵含有两个部分矩阵，即校验矩阵#1和#2。校验矩阵#1是 用于纠正空间耦合LDPC码中的错误的矩阵，且是类似于根据第一实施例 的带状矩阵的带状矩阵。校验矩阵#2是用于纠正LDPC码中的错误的矩 阵，且是具有极小数目的“1”的稀疏矩阵。

图42为图示根据第六实施例的第二码错误检测与纠正部530的配置 示例的方块图。根据第六实施例的第二码错误检测与纠正部530与根据第 一实施例的第二码错误检测与纠正部的不同之处在于包括码字生成部 534，而不包括部分数据生成部532。码字生成部534依序生成毗邻部分数 据及检测到错误的部分数据，并将毗邻部分数据及部分数据供应给第二 码错误检测与纠正器540。码字生成部534从第二码错误检测与纠正器540 接收表示对检测到错误的部分数据的纠错是否成功的纠正结果。在对第 二码字的纠错已失败的情况下，码字生成部534生成所有第三码字，并将 第三码字供应给第二码错误检测与纠正器540。如上所述，由于与部分地 纠正第二码的情况相比可以通过纠正所有第三码来纠正更多的错误，因 而提高了整个码中的纠错能力。

因此，在第六实施例中，即使对部分数据的纠错已失败，与其中部 分地纠正第二码的情况相比，存储控制器300可以通过纠正所有第三码字 中的错误来纠正更多的错误。因此，提高整个码中的纠错能力。

应注意，本发明的上述实施例仅仅是用于实现本发明的示例，且在 本发明的示例性实施例的特征与随附权利要求中所列举的元件之间存在 对应关系。同样地，随附权利要求中所列举的元件与在本发明的示例性 实施例中出现的名称相同的特征之间存在对应关系。然而，本发明不仅 限于所述实施例，且在不背离本发明的范围的前提下通过对所述实施例 进行多种变化来实现本发明。

此外，上述实施例中所述的处理流程可视为具有这些流程的方法， 或者可视为使计算机执行这些流程的程序或视为保持所述程序的记录媒 体。作为记录媒体，例如，可使用CD(光盘)、MD(迷你光盘)、DVD(数 字多用途光盘)、存储卡、蓝光光盘(注册商标)或诸如此类。

应注意，本发明可具有下列配置。

(1)一种错误检测与纠正装置，其包括：

第一码错误检测部，其用于检测第二码字中的多个第一码字中的每 一个是否具有错误，所述第二码字是通过以连锁方式对所述多个第一码 字进行编码而生成的、并且是含有多个部分数据的码字；及

第二码纠错部，其用于基于与所述第二码字中的所述多个部分数据 中的一个部分数据毗邻的毗邻部分数据来纠正所述一个部分数据中的所 述错误，所述一个部分数据含有检测到所述错误的所述第一码字。

(2)如(1)所述的错误检测与纠正装置，其中，

为所述多个部分数据中彼此毗邻的部分数据所共有的数据部分为共 同码字，且

所述第二码纠错部基于为所述一个部分数据与所述毗邻部分数据所 共有的所述数据部分，纠正含有检测到所述错误的所述第一码字的所述 一个部分数据中的所述错误。

(3)如(1)所述的错误检测与纠正装置，其中，所述第二码纠错 部纠正所述毗邻部分数据中的错误，且当对所述毗邻部分数据的纠错成 功时，所述第二码纠错部基于所述毗邻部分数据来纠正由所述第一码错 误检测部检测到的所述错误。

(4)如(3)所述的错误检测与纠正装置，其中，当对所述毗邻部 分数据的纠错已失败时，所述第二码纠错部纠正新毗邻部分数据中的错 误，并判断对所述新毗邻部分数据的纠错是否成功，所述新毗邻部分数 据是与所述毗邻部分数据毗邻的部分数据。

(5)如(3)所述的错误检测与纠正装置，其中，当未检测到包含 在所述毗邻部分数据中的所述第一码字中的错误时，所述第二码纠错部 基于所述毗邻部分数据来纠正由所述第一码错误检测部检测到的所述错 误，且当检测到包含在所述毗邻部分数据中的所述第一码字中的错误时， 所述第二码纠错部判断是否在包含在新毗邻部分数据中的所述第一码字 中检测到错误，所述新毗邻部分数据是与所述毗邻部分数据毗邻的部分 数据。

(6)如(3)所述的错误检测与纠正装置，其中，在对所述毗邻部 分数据的纠错已失败时，所述第二码纠错部纠正所述第二码字中的错误。

(7)如(1)所述的错误检测与纠正装置，其中，所述第二码纠错 部判断基于所述毗邻部分数据执行的对所述错误的纠正是否成功，且当 所述纠正已失败时，所述第二码纠错部基于分别含有所述第一码字的第 三码字纠正所述错误。

(8)如(1)所述的错误检测与纠正装置，其中，

所述第二码字为卷积码字，且

所述第二码纠错部基于对所述毗邻部分数据所执行的卷积运算的结 果纠正所述错误。

(9)如(8所述的错误检测与纠正装置，其中，所述第二码字为 turbo码字。

(10)如(1)所述的错误检测与纠正装置，其中，所述第二码纠 错部纠正含有检测到所述错误的所述第一码字的所述一个部分数据与所 述毗邻部分数据的组合中的所述错误，所述组合作为一个解码单位。

(11)如(1)所述的错误检测与纠正装置，其中，

所述多个部分数据中的每一个含有用于纠正所述部分数据中的每一 个中的错误的第二奇偶校验及用于纠正所述第二奇偶校验中的错误的第 一奇偶校验，及

所述第二码纠错部使用所述第一奇偶校验来纠正所述第二奇偶校验 中的所述错误，且使用所述纠正后的第二奇偶校验来纠正所述一个部分 数据中的所述错误。

(12)如(1)所述的错误检测与纠正装置，其中，所述多个部分 数据中的每一个含有所述多个第一码字中的两个或更多个。

(13)一种信息处理器，其包括：

第二编码部，其用于通过连锁方式对多个第一码字进行编码来生成 第二码字，所述第二码字是含有多个部分数据的码字；

第一码错误检测部，其用于检测所述第二码字中的所述第一码字中 的每一个是否具有错误；及

第二码纠错部，其用于基于与所述第二码字中的所述多个部分数据 中的一个部分数据毗邻的毗邻部分数据来纠正所述一个部分数据中的所 述错误，所述一个部分数据含有检测到所述错误的所述第一码字。

(14)一种错误检测与纠正方法，其包括：

检测第二码字中的多个第一码字中的每一个是否具有错误，所述第 二码字是通过以连锁方式对所述多个第一码字进行编码而生成的，并且 是含有多个部分数据的码字；及

基于与所述第二码字中的所述多个部分数据中的一个部分数据毗邻 的毗邻部分数据来纠正所述一个部分数据中的所述错误，所述一个部分 数据含有检测到所述错误的所述第一码字。

(15)一种具有程序的非暂存性有形记录媒介，所述计算机可读程 序在由计算机执行时使得计算机实施一种方法，所述方法包括：

检测第二码字中的多个第一码字中的每一个是否具有错误，所述第 二码字是通过以连锁方式对所述多个第一码字进行编码而生成的，并且 是含有多个部分数据的码字；及

基于与所述第二码字中的所述多个部分数据中的一个部分数据毗邻 的毗邻部分数据来纠正所述一个部分数据中的所述错误，所述一个部分 数据含有检测到所述错误的所述第一码字。

所属领域的技术人员应了解，可根据设计要求或其他因素想到各种 修改、组合、子组合及改变，只要所述各种修改、组合、子组合及改变 在随附权利要求或其等效形式的范围内。

相关申请的交叉引用

本申请主张2013年2月5日提交的日本优先权专利申请JP 2013-020055的权益，其全部内容以引用方式并入本文中。