钱式搜索装置、存储装置以及钱式搜索方法

摘要

本发明提供钱式搜索装置、存储装置以及钱式搜索方法。根据实施方式，钱式搜索装置具有按每个系数进行异或运算的n个运算部。另外，具有保持高次运算部的运算结果的第1寄存器。另外，具有进行高次运算部的运算结果的异或运算的异或运算部。另外，具有保持异或运算部的运算结果的第2寄存器。运算部分别使用来自第2寄存器的第2寄存器值以降低异或运算的运算级数而进行运算。

说明书

技术领域

本发明的实施方式一般涉及钱式搜索(Chiensearch)装置、存储装置 以及钱式搜索方法。

背景技术

在使用了半导体存储器等的存储装置中，在数据的译码处理中进行纠 错处理。在纠错处理中，作为对数据的错误位置进行确定的方法具有钱式 搜索。在钱式搜索中，为了进行根的探索以确定错误位置，进行：用于将 错误位置多项式(t次以下)的常数项以外的系数分别设为α倍、α²倍、···、α^t倍的由α的幂进行的异或运算；和用于在伽罗瓦(galois) 体上对这些运算结果取和的异或运算。在钱式搜索电路中，为了在每个循 环都判定错误位置，在1个循环以内进行所有异或运算。另一方面，在钱 式搜索电路中，能够通过增大伽罗瓦体的位数和/或错误位置多项式的次数 而提高纠错能力，但同时异或运算的级数(理論和演算の段数)增多。

发明内容

本发明的实施方式提供能够减少异或运算的级数的钱式搜索装置、存 储装置以及钱式搜索方法。

根据本实施方式，钱式搜索装置基于通过错误位置多项式运算算出的 错误位置多项式的项的系数，对n(n为2以上的自然数)位并行进行钱 式搜索。具有n个运算部，它们按每个所述系数基于所设定的运算式进行 第1异或运算。另外，具有第1寄存器，其保持所述n个运算部中的进行 与钱式搜索中的最高次的α的幂的运算相当的所述第1异或运算的高次运 算部的运算结果。另外，具有异或运算部，其基于所述高次运算部的运算 结果而进行第2异或运算。另外，具有第2寄存器，其保持所述异或运算 部的运算结果。所述n个运算部分别输入来自所述第1寄存器的第1寄存 器值以及来自所述第2寄存器的第2寄存器值，对于通过使用所述第2寄 存器值能够降低所述第1异或运算的运算级数的运算使用所述第2寄存器 值。

附图说明

图1是表示第1实施方式所涉及的半导体存储装置(存储装置)的构 成例的框图。

图2是表示第1实施方式所涉及的译码部的构成例的图。

图3是表示第1实施方式所涉及的钱式搜索部(钱式搜索装置)的构 成例的图。

图4是表示在钱式搜索部(钱式搜索装置)中与错误位置多项式σ(x) 的系数σ₁相当的部分的运算内容的图。

图5是表示第1实施方式的钱式搜索方法的流程图。

具体实施方式

以下参照附图，对实施方式所涉及的钱式搜索装置、存储装置以及钱 式搜索方法进行详细说明。另外，本发明并不限定于这些实施方式。

(第1实施方式)

图1是表示第1实施方式所涉及的半导体存储装置(存储装置)1的 构成例的框图。本实施方式的半导体存储装置1包含存储器控制器(存储 器控制装置)2和半导体存储部(存储部)3。半导体存储装置1经由通信 接口而连接于主机4，作为相对于主机4的外部存储介质发挥作用。作为 主机4的例子，可列举个人计算机和/或CPU(CentralProcessingUnit， 中央处理单元)核心等。

存储部3包括例如NAND型闪存等非易失性半导体存储器。存储部3 具备的存储芯片可以是单个也可以是多个。

存储器控制器2包含内部总线20、主机I/F(接口)21、存储器I/F (存储器控制部)22、控制部23和编码/译码处理部24。编码/译码处 理部24包含编码部25和译码部(译码器)26。

主机I/F21将从主机4接收的指令、数据等向内部总线20输出。另外， 主机I/F21将经由内部总线20输入的数据、来自控制部23的响应通知(表 示指令的执行完成的通知等)等发送到主机4。主机I/F21依照例如SATA (SerialAdvancedTechnologyAttachment，串行高级技术附件)、 SAS(SerialAttachedSCSI，串行SCSI)、PCI(PeripheralComponent Interconnect，周边零件连接界面)、Express等通信接口标准。

控制部23为综合地控制半导体存储装置1的各构成要素的控制部，由 CPU核心、RAM(RandomAccessMemory，随机存取存储器)、ROM (ReadOnlyMemory，只读存储器)、DMA(DirectMemoryAccess， 直接内存访问)控制器等构成。控制部23在从主机4经由主机I/F21以及 内部总线20接受到指令的情况下，进行根据该指令的控制。例如，控制部 23根据来自主机4的指令，向存储器I/F22指示向半导体存储部3写入数 据、从半导体存储部3读取数据等。另外，控制部23向编码/译码处理部 24指示实施纠错编码处理或者译码处理。

编码/译码处理部24基于控制部23的指示，对从主机4接收的用户 数据进行纠错编码处理，向存储器I/F22输出，对从存储器I/F22输入的代 码数据进行译码处理。存储器I/F22基于控制部23的指示而进行对半导体 存储部3的读写。

另外，图1所示的半导体存储装置1的构成为一例，只要具备半导体 存储部3与对该半导体存储部3的读写进行控制的控制器、为能够与主机 4通信的构成，并不限定于图1所示的构成，可以是任何的构成。另外， 也可以代替半导体存储部3而使用半导体存储器以外的存储单元。

接下来，对向本实施方式的半导体存储部3的写入工作进行说明。首 先，控制部23若从主机4接到写入用户数据的指示，则指示编码/译码处 理部24实施编码，并且指示存储器I/F22对半导体存储部3进行写入。从 主机4发送的写入对象的用户数据被写入半导体存储装置1内的未图示的 缓存。编码/译码处理部24的编码部25对从缓存输入的用户数据进行纠 错编码，将生成的冗余数据向存储器I/F22输出。存储器I/F22将从缓存输 入的用户数据与编码部25生成的冗余数据向半导体存储部3写入。

作为纠错代码可以使用任何的代码，例如，能够使用BCH代码和/或 RS(Reed－Solomon)代码等。以下以BCH代码为例进行说明。

接下来，对从本实施方式的半导体存储部3的读取工作进行说明。控 制部23若从主机4接到读取数据的指示，则指示编码/译码处理部24实 施译码，并且指示存储器I/F22从半导体存储部3进行读取。存储器I/F22 基于来自控制部23的指示从半导体存储部3读取用户数据和与其相对应的 冗余数据，并向编码/译码处理部24输出。编码/译码处理部24的译码 部26对读取的用户数据与冗余数据进行译码处理，在判断为读取到的用户 数据有误的情况下，实施纠错。主机I/F21将纠错后的用户数据向主机4 发送。在没有错误的情况下，将读取的用户数据直接向主机4发送。

以下，对本实施方式的译码处理进行说明。图2是表示第1实施方式 所涉及的译码部26的构成例的图。译码部(译码装置)26具备错误计算 部261、错误位置多项式运算部262、钱式搜索部(错误位置计算部)263 和译码控制部264。

控制部23当经由主机I/F21从主机4获取用户数据的读取要求时，指 示存储器I/F22对读取对象的用户数据进行读取。存储器I/F22同时读取与 读取对象的用户数据相对应的冗余数据，并向译码部26发送。在译码部 26，当从存储器I/F22获取到读取对象的用户数据时，开始译码处理。

当开始译码处理时，译码控制部264对错误计算部261指示实施错误 计算，错误计算部261实施错误计算。然后，译码控制部264对错误位置 多项式运算部262进行指示，使得其使用计算完毕的错误计算结果进行错 误位置多项式运算，错误位置多项式运算部262实施错误位置多项式运算。

错误位置多项式运算是在将错误位置多项式设为σ(x)时根据错误 的值来计算σ(x)＝1+σ₁x¹+σ₂x²+…的系数σ₁，σ₂，…的处理。作 为具体的方法，具有BM法、欧几里得除法、皮尔逊法(Pearsonmethod) 等。皮尔逊法是通过矩阵计算解在系数σ与错误之间成立的联立方程式的 方法，BM法以及欧几里得除法是使用多项式逐次地计算系数σ与错误的 联立方程式的方法。另外，译码处理中的错误位置多项式的计算也可以使 用任何的方法。

接下来，译码控制部264对钱式搜索部263进行指示，使得其使用错 误位置多项式运算的结果进行钱式搜索，钱式搜索部263使用系数σ₁， σ₂，…实施钱式搜索并确定错误位置、将处理结束。钱式搜索是向错误位 置多项式σ(x)依次代入值、搜索作为σ(x)＝0的值的错误定位(错 误位置)的方法。译码控制部264通过钱式搜索，在σ(x)＝0的情况下， 判定为在对应的位具有错误，通过使该位反转而实施纠错。

接下来，对本实施方式的钱式搜索部263进行说明。图3是表示第1 实施方式所涉及的钱式搜索部263(钱式搜索装置)的构成例的图。在这 里，作为一例，将错误位置多项式设为t次的σ(x)＝1+σ₁x¹+σ₂x²+…σ_tx^t。另外，在钱式搜索部263中，通过将钱式搜索电路并联化，能 够多个位同时地例如与数据总线一致地以8位为单位和/或以16位为单位 进行错误位置判定。在这里，作为一例，对以n(n为2以上的自然数) 位为单位进行的情况进行说明。

钱式搜索部263具备：t×n个运算部31－11，31－12，…，31－tn；t 个寄存器(第1寄存器)32－1，32－2，…，32－t；t个选择部33－1， 33－2，…，33－t；t个异或运算(XOR)部34－1，34－2，…，34－t； t个寄存器(第2寄存器)35－1，35－2，…，35－t；n个异或运算(XOR) 部36－0，36－1，…，36－(n－1)；n个逻辑和运算(OR)部37－0， 37－1，…，37－(n－1)；和n个错误位置判定部38－0，38－1，…， 38－(n－1)。钱式搜索的运算以如下处理为1个循环，并反复实施预定 的次数，该处理为：各运算部31－11～31－tn使用第1寄存器值以及第2 寄存器值进行异或运算后，将XOR部36－0～36－(n－1)处的异或运算、 OR部37－0～37－(n－1)处的逻辑和运算和错误位置判定部38－0～38 －(n－1)处的错误位置判定为止的处理。

运算部31－11～31－tn分别使用从对应的寄存器32－1～32－t输入 的寄存器值(第1寄存器值)以及从寄存器35－1～35－t输入的寄存器值 (第2寄存器值)，进行与对应的钱式搜索的α的幂的运算相当的异或运 算(第1异或运算)。在图3所示的钱式搜索部263，所谓对应的寄存器， 在例如运算部31－tn的情况下，在代码的末尾附加“t”的寄存器32－t以及 寄存器35－t就是对应的寄存器。在各运算部31－11～31－tn，作为α的 幂的运算，进行与乘以代码的末尾的数字所得的值的α的幂的运算相当的 异或运算。例如，在运算部31－11，通过“1×1”进行与“α¹”的幂的运算相 当的异或运算，在运算部31－tn，通过“t×n”进行与“α^tn”的幂的运算相当 的异或运算。

选择部33－1～33－t分别对寄存器32－1～32－t以及XOR部34－ 1～34－t，在运算的初次输出错误位置多项式σ(x)的常数项以外的系 数σ₁，σ₂，…σ_t，在其他的情况下(在以后的运算中)输出来自与各系数 相对应的n个运算部31－11～31－tn中、进行与最高次的α的幂的运算相 当的异或运算的运算部(高次运算部)31－1n，31－2n，…，31－tn的运 算结果。

寄存器(触发器)32－1～32－t分别从选择部33－1～33－t输入数据 并按错误位置多项式σ(x)的常数项以外的系数σ₁，σ₂，…σ_t初始化。 另外，寄存器32－1～32－t保持来自运算部(高次运算部)31－1n，31 －2n，…，31－tn的运算结果。寄存器32－1～32－t分别向与错误位置多 项式σ(x)的各系数相对应的各运算部输出所保持的寄存器值(第1寄 存器值)。

XOR部34－1～34－t分别对从选择部33－1～33－t输入的数据，作 为钱式搜索的事先运算进行异或运算(第2异或运算)。在这里，XOR部 34－1～34－t对输入的数据的m位全部进行异或运算。

寄存器(触发器)35－1～35－t分别保持XOR部34－1～34－t中的 异或运算的运算结果。寄存器35－1～35－t分别向与错误位置多项式σ (x)的各系数相对应的各运算部输出所保持的寄存器值(第2寄存器值)。

XOR部36－0输入来自寄存器32－1～32－t的寄存器值，进行异或 运算并输出m位的运算结果。

XOR部36－1～36－(n－1)分别对与各数据总线相对应的运算部31 －11，…，31－1(n－1)，…，31－t1，…，31－t(n－1)的运算结果， 进而进行异或运算，输出m位的运算结果。

OR部37－0～37－(n－1)分别对XOR部36－0～36－(n－1)的 m位的运算结果进行逻辑和运算，输出“0”或者“1”的运算结果。

错误位置判定部38－0～38－(n－1)分别从OR部37－0～37－(n －1)的运算结果进行错误位置的判定。在错误位置判定部38－0～38－(n －1)，在运算结果变为“0”的情况下，判定为此时与进行了从各运算部31 －11～31－tn到错误位置判定为止的处理的次数相符的代码字的位置是错 误的。

首先，对基本的钱式搜索的运算程序进行说明。在这里，对不使用XOR 部34－1～34－t以及寄存器35－1～35－t的运算程序进行说明。在钱式 搜索部263，用σ(x)的常数项以外的系数σ₁，σ₂，…，σ_t对t个寄存器 32－1～32－t进行初始化。寄存器32－1～32－t分别保持系数σ₁，σ₂，…， σ_t，作为寄存器值向各运算部31－11，31－12，…，31－tn输出。各运算 部31－11，31－12，…，31－tn进行与钱式搜索中的α的幂的运算相当的 异或运算。

在错误位置判定部38－0～38－(n－1)，分别根据在XOR部36－0～ 36－(n－1)以及OR部37－0～37－(n－1)运算所得的结果判定是否 满足σ(α)＝0，在满足σ(α)＝0的情况下，判定为此时与进行了从各 运算部31－11～31－tn到错误位置判定的处理的次数相符的代码字的位 置是错误的。这样，在钱式搜索部263，通过具有n个错误位置判定部并 并行化，能够以n位为单位进行错误位置判定。

图4是表示在图3所示的钱式搜索部263(钱式搜索装置)中与错误 位置多项式σ(x)的系数σ1相当的部分的运算内容的图。具体地说，表 示伽罗瓦体GF(2⁸)、即在图3中设为m＝8的情况下的、到错误位置判 定为止的运算路线的例子。在运算部31－11，31－12，…，31－tn中，能 够通过对根据伽罗瓦体的原始多项式所选择的输入位彼此进行异或运算而 求出α的幂的运算结果。

在n个并列的电路构成的钱式搜索部263中，为了分别判定错误位置， 需要进行由t个α的幂进行的异或运算和用于取这些运算结果的总和的异 或运算。因此，为了在1循环内判定是否有错误位置，需要在1个循环内 将所有这些异或运算结束。

在不使用XOR部34－1以及寄存器35－1的运算处理中，到错误位 置判定为止的运算路线的长度根据求取α的幂时的异或运算级数来确定。 在该情况下，相对于向α的幂的运算输入的8位的S[7：0]，在进行较 多的异或运算的情况下运算路线变长。例如，在图4中，在为了求取L1 [7：0]中的L1[0]而对输入位S[7：0]全部进行异或运算的情况下， 经由L1[0]的运算路线变为最长的路线。

在钱式搜索部263，为了在每个循环都判定错误位置，需要在1个循 环以内进行所有的异或运算。另外，在钱式搜索部263，随着电路的工作 频率变快，异或运算变得难以集中在1个循环内。如果工作频率变快，则 在逻辑合成时使用驱动能力较高的逻辑单元进行进行逻辑合成的最佳化以 使得异或运算集中在1个循环以内，具有电路规模增加的倾向。所谓逻辑 单元为寄存器、XOR部等满足逻辑运算功能的最小的电路。

在本实施方式中，为了缩短该运算路线，对各运算部31－11～31－18， 经由寄存器35－1输入与在XOR部34－1运算所得的全部8位有关的异 或运算结果。

XOR部34－1，对于返回到寄存器32－1的L8[7：0]对全部8位 进行异或运算。寄存器35－1保持XOR部34－1中的运算结果。

在运算部31－11～31－18，在α的幂的运算中，对输入位S[7：0] 中的、过半数即5位以上进行异或运算所得的运算部分，通过未进行异或 运算的输入位与来自对L8[7：0]全部进行了异或运算并保持的寄存器 35－1的输出FLX的异或运算来进行。

由此，在运算部31－11～31－18中，能够将5位以上的异或运算转换 成4位以下的异或运算，能够减少异或运算的运算级数以缩短运算路线。 以下，说明该构成在逻辑上等价的情况。

在图4中，如果不使用FLX＝S[0]＾S[1]＾S[2]＾S[3]＾S [4]＾S[5]＾S[6]＾S[7],则运算部31－11中的α的幂的运算(异 或运算)能够如下表示。

L1[0]＝S[0]＾S[1]＾S[2]＾S[3]＾S[4]＾S[5]＾S [6]＾S[7]

L1[1]＝S[0]＾S[1]＾S[2]＾S[3]＾S[4]

在这里，如果使用上述的FLX，则L1[0]与FLX相同，所以变为 L1[0]＝FLX。同样，如果使用FLX则能够如以下那样转换L1[1]。

L1[1]＝FLX＾S[5]＾S[6]＾S[7]

L1[1]＝S[0]＾S[1]＾S[2]＾S[3]＾S[4]＾S[5]＾S [6]＾S[7]＾S[5]＾S[6]＾S[7] ＝S[0]＾S[1]＾S[2]＾S[3]＾S[4]

在图4中，对于其他的运算部31－12～31－18的异或运算，通过使用 FLX也同样能够减少运算级数。

即，在本实施方式中，利用如果对相同位进行2次异或运算则变为0、 所以与没有进行异或运算等价这一异或运算的性质。由此，在各运算部31 －11～31－18中，对于5位以上的运算，使用没有进行运算的3位以下的 输入和事先进行了运算后的1位，压缩至4位以下的运算。在XOR部34 －1中，作为事先运算进行8位的异或运算，但使用该运算结果的是下一 个循环，所以对进行错误位置判定的运算级数没有影响。在各运算部31－ 11～31－18中，使用的运算式是已知的，所以能够与XOR部34－1内的 运算内容相应地预先设定降低了异或运算的级数的运算式。

在图4中，具体地说，对与错误位置多项式σ(x)的系数σ1相当的 部分的运算进行了说明，但通过对与图3所示的其他的系数相当的部分的 运算也进行同样的运算，能够降低异或运算的级数。

这样，在本实施方式的钱式搜索部263中，对于能够进行基本的钱式 搜索的运算的构成，追加用于通过事先运算而缩短异或运算路线的构成。 所谓用于缩短异或运算路线的构成，是对返回到寄存器32－1～32－t的全 部m位信号分别进行异或运算的t个XOR部34－1～34－t以及分别保持 XOR部34－1～34－t的运算结果的t个寄存器35－1～35－t。

可以认为，通过用于缩短该异或运算路线的构成(电路)的追加，在 钱式搜索部263中，在图3所示的构成中电路规模增加，但在伽罗瓦体的 位数和/或错误位置多项式的次数t变大的情况下，还有电路的工作频率快 的情况下，电路规模不增加。相反地，在钱式搜索部263，也能够得到使 整体的电路规模减小的效果。其原因如下所述。

一般地说，在钱式搜索电路中，如果伽罗瓦体的位数和/或错误位置多 项式的次数t变大，则在1个循环内进行的异或运算级数增加。另外，如 果电路的工作频率快，则用于进行全部的异或运算的时间变短。其结果， 处理可能在1循环以内没有结束、发生违背定时的情况。为了消除违背定 时，有效的是在逻辑合成时使用驱动能力高的逻辑单元并缩短异或运算的 运算时间。然而，驱动能力高的逻辑单元与驱动能力低的逻辑单元相比， 栅(gate，门)规模较大。因此，越大量使用驱动能力高的逻辑单元，钱 式搜索电路整体的电路规模变得越大。

然而，在本实施方式的钱式搜索部263，将异或运算路线缩短，在1 个循环内进行的异或运算级数减少，所以在定时上产生余量、不需要较多 地使用驱动能力高的逻辑单元。因此，在由于使用驱动能力高的逻辑单元 而引起的电路规模的增加比由于追加了异或运算与寄存器而引起的电路规 模的增加大的情况下，在本实施方式所示的钱式搜索部263，可得到能够 减小整体的电路规模的效果。另外，钱式搜索部263即使在电路规模变大 的情况下，也是用于消除违背定时的有效构成。

在本实施方式的钱式搜索部263，与以往比较能够提高电路的工作频 率。另外，在钱式搜索部263中，在能够使用驱动能力低的逻辑单元的情 况下，能够降低消耗电流。一般地说，驱动能力低的逻辑单元自身比驱动 能力高的逻辑单元小，所以在钱式搜索部263中能够减小电路规模。

图5是表示第1实施方式的钱式搜索方法的流程图。首先，在钱式搜 索部263，寄存器(第1寄存器)32－1～32－t以及XOR部34－1～34－ t在钱式搜索的初次运算中输入错误位置多项式σ(x)的对应的各系数(步 骤S1)。寄存器(第1寄存器)32－1～32－t按输入的系数初始化(步骤 S2)。XOR部34－1～34－t按输入的系数进行异或运算(步骤S3)。

寄存器(第2寄存器)35－1～35－t分别保持XOR部34－1～34－t 内的异或运算的运算结果(步骤S4)。运算部31－11～31－tn从对应的 寄存器(第1寄存器)32－1～32－t以及寄存器(第2寄存器)35－1～35 －t输入寄存器值，进行异或运算(步骤S5)。作为高次运算部的运算部 31－1n～31－tn经由选择部33－1～33－t将运算结果向寄存器(第1寄存 器)32－1～32－t以及XOR部34－1～34－t输出(步骤S6)。寄存器(第 1寄存器)32－1～32－t保持输入的运算结果(步骤S7)。XOR部34－1～ 34－t通过输入的运算结果进行异或运算(步骤S8)。在钱式搜索部263 中，随后返回到步骤S4对同样的运算反复实施预定的次数。

根据第1实施方式，在钱式搜索部263中，在要求较快的工作频率且 高速处理的并联化了的钱式搜索电路，进行在α的幂的运算中使用的输入 位中全部输入位的异或运算的事先运算，保持该运算结果，使用保持的异 或运算的运算结果来进行钱式搜索中的与α的幂的运算相当的异或运算。 其结果，通过对适用了本实施方式的电路进行逻辑合成，能够得到下述效 果：能够将钱式搜索电路中的运算路线缩短化，能够不使处理速度下降地 减少容易产生违背定时的伽罗瓦体运算部分的、1个循环内的异或运算级 数。另外，通过异或运算级数减少，能够使用驱动能力比以往低的逻辑单 元，即使在使用驱动能力低的逻辑单元的情况下也能够抑制违背定时的产 生。另外，能够得到为了事先运算而追加的电路增加量以上的电路规模的 削减效果。

(第2实施方式)

在第1实施方式中，XOR部34－1～34－t作为异或运算的事先运算 对输入位全部进行了异或运算。然而，减少异或运算级数的方法并不限定 于此。

在XOR部34－1～34－t，作为异或运算的事先运算，也可以：在各 运算部31－11，31－12，…，31－tn的各α的幂的运算中，选择能够缩短 运算级数较长的路线的输入位的组合，对所选择的输入位进行异或运算。 例如，在图4中，XOR部34－1如果作为异或运算的事先运算而预先运算 S[1]＾S[2]＾S[3]＾S[4]，则能够缩短运算部31－11的L1[0]、 L1[1]、运算部31－12的L2[7]、运算部31－17的L7[0]的运算路 线。

根据第2实施方式，在XOR部34－1～34－t中，选择输入位的组合 以进行一部分的输入位的异或运算的事先运算。其结果，能够得到下述的 效果：比作为事先运算而对输入位的全位进行异或运算，更能够降低运算 数。

对本发明的几个实施方式进行了说明，但这些实施方式是作为例子而 提出的，并不意图限定发明的范围。这些新实施方式能够以其他的工作各 种形态实施，在不脱离发明的要旨的范围内，能够进行各种省略、置换、 变更。这些实施方式和/或其变形包含于发明的范围和/或要旨，并且包含于 技术方案所述发明与其均等的范围。