技术摘要：
本发明呈现一种用于低密度奇偶校验码LDPC的竖直分层式有限字母表迭代解码的方法和设备，其作用于由子矩阵块组成的奇偶校验矩阵。所述迭代解码涉及在泰纳图中与构成解码块的一或多个子矩阵相关联的变量节点和校验节点之间传递消息，并且所述消息属于有限字母表。呈现本  全部
背景技术：
错误校正码通过确保数据的完整性而在通信、计算机和存储系统中发挥着重要的 作用。本发明涉及被称为低密度奇偶校验(LDPC)码的一类错误校正码及它们的迭代消息传 递解码算法。LDPC码以其在无限码字长度范围内逼近信息论通道容量的能力而备受瞩目。 它们在许多应用中是标准化的，包含无线通信、卫星通信、深空通信、光通信，以及在固态驱 动器和硬盘驱动器等存储系统中。近年来，由于快闪存储器的密度不断增加，它们在NAND快 闪存储器应用中越来越突出。所有这些应用都被认为在本发明的使用范围内。 二进制LDPC码由具有N列和M行以及其对应的泰纳图G的奇偶校验矩阵(PCM)H定 义。泰纳图G是由基数N的变量节点集合V＝{v1,v2,...,vN}和基数M的校验节点集合C＝{c1, c2,...,cM}组成的二分图，这些节点通过边线连接，其中，如果奇偶校验矩阵中的矩阵元素 等于Hi,j＝1，那么在节点ci和vj之间存在边线。H中列(或行)的权重是它含有的非零值的数 目。变量节点(或校验节点)的阶次是其等于H中对应列(或行)的权重的相邻项的数目。因 此，变量节点vj的阶次将等于奇偶校验矩阵的第j个列的权重，且校验节点ci的阶次将等于 第i行的权重。如果H中的每个列具有权重dv，那么LDPC码被视为具有固定的列权重dv，如果H 中存在至少两个具有不同权重的列，那么LDPC码具有可变列权重。类似地，如果H中每个行 具有权重dc，那么LDPC码被视为具有固定的行权重dc。奇偶校验矩阵的实例在下面的等式1 中给出。 5 CN 111615793 A 说　明　书 2/22 页 LDPC码的码字x＝(x1,x2,...,xN)通过通道发送，所述通道可以是通信通道，也可 以是存储码字的数据存储媒体。码字中的值xi是与G中的变量节点vi相关联的二进位值。通 道向量y＝(y1,y2,...,yN)是基于从通道接收到的向量计算出的向量，由于通道所引入的错 误，所以它可不同于x。例如，在二进制对称通道(BSC)的特定情况中，r＝x e，其中 表示异 或(XOR)运算，并且向量e的元素表示因为翻转x中的码字位而引入的错误，概率为α。在本公 开中被称为通道值的值yi∈Y属于通道输出字母表Y。向量y输入到迭代解码器以便恢复x。 本发明适用于BSC以及更多通用类别的具有较大通道输出字母表的通道，例如量 化加性高斯白噪声(AWGN)通道。在只具有两个可能通道输出的BSC的情况下，Y可以定义为Y ＝{±1}，其中按照惯例， 1对应于接收到的位值0，-1对应于接收到的位值1。在具有较大通 道输出字母表的情况下，如果可能通道输出的数目是偶数且等于2q，那么Y可以定义为Y＝ {±1,±2,...±q}，或者如果可能通道输出的数目是奇数且等于2q 1，那么Y＝{0,±1,± 2,...±q}。 在更一般的情况下，对于偶数基数，任何通道输出都可以定义为Y＝{±Y1 ,± Y2,...±Yq}，对于奇数基数，Y＝{0,±Y1 ,±Y2,...±Yq}，其中也可使用本发明。对于本公 开，如果通道向量y的元素只能采用两个可能值，那么解码被称为硬决策解码，并且y被称为 硬决策输入。如果向量y的元素可以采用超过两个可能值，那么解码被称为软决策解码，并 且输入被称为软决策输入。对于软决策解码，y被称为nq位软决策输入，其中在偶数基数的 情况下， 在奇数基数的情况下， 是大于x的最小整 数。 本发明的实施例可以通过使用泰纳图G来说明，其中解码涉及沿着图形边线迭代 地传递消息。此类型的解码被称为LDPC码的消息传递解码。图1示出等式1的LDPC码的泰纳 图的实例，其中圆形表示变量节点，正方形表示校验节点。解码器通过输入通道向量y初始 化，然后消息在变量节点和校验节点之间沿着图形G的边线迭代地传递。消息在每次到达节 点时更新，其方式使得特定边线上的传出消息基于所述节点的除所述特定边线的传入消息 6 CN 111615793 A 说　明　书 3/22 页 之外的所有传入消息计算。当图形中的所有节点已经以通常被称为调度的处理的特定次序 至少处理一次时，执行解码迭代。在每个迭代结束时以及在一个解码迭代的处理期间，针对 所有变量节点vi，基于它们从它们相邻的校验节点接收的消息以及通道值yi而计算位值的 估计值 位值的硬决策估计值 是使用决策函数Ψ来计算的，并且通过将它们发送到计算 向量 的校正子的验证器而用于校验解码器是否已收敛到码字。校正子被定义为 其中xT表示向量x的转置。校正子向量的元素被称为校正子位。验证器校验在给定 的校验节点处，它们相邻的变量节点的对应硬决策估计值是否形成偶数奇偶校验，并且此 类校验节点被认为是符合的，否则它被认为是不符合的。如果每个校验节点都是符合的，那 么校正子是零，并且解码器收敛到码字。迭代过程一直继续到解码器收敛到码字或达到最 大迭代次数为止。如果解码器没有收敛到码字，那么它被视为发生故障。 本发明的实施例另外涉及称为有限字母表迭代解码器(FAID)的一类迭代消息传 递解码器。在这些解码器中，消息属于由通常有限的少量层级组成的有限字母表M。对于其 中M具有奇数基数的特定说明性情况，消息字母表表示为M＝{0,±Li:1≤i≤s}，其中对于 任何i>j， 且Li>Lj。 FAID中阶次dv的变量节点的变量节点更新函数是预定义映射Φv： 在本公开中，它被称为依据节点处的除特定边线上的传入消息之外的dv-1传入消息以及通 道值yi计算所述特定边线上的传出消息的变量节点(VN)映射或VN映射。变量节点更新函数 可以设计成改进解码器的错误校正能力。阶次dv＝3的变量节点的映射Φv的实例在下表1中 提供。在此实例中，VN映射具有7个可能层级，即s＝3，我们只示出了对应于y＝-Y的VN映射， 使得表条目是Φv(-Y,m1,m2)。 表1 m1/m2 -L3 -L2 -L1 0 L1 L2 L3 -L3 -L3 -L3 -L3 -L3 -L3 -L3 -L1 -L2 -L3 -L3 -L3 -L3 -L3 -L1 L1 -L1 -L3 -L3 -L3 -L3 -L1 -L1 L1 0 -L3 -L3 -L3 -L1 0 0 L1 L1 -L3 -L3 -L1 0 0 L1 L2 L2 -L3 -L1 -L1 0 L1 L1 L3 L3 -L1 L1 L1 L1 L2 L3 L3 应注意，通道值y＝ Y的VN映射可以通过对称性从具有通道值y＝-Y的VN映射推断 出： Φv(Y,m1,m2)＝-Φv(-Y,-m1,-m2)，m1∈M，m2∈M            (3) 用于FAID的校验节点更新函数Φc类似于用于目前先进技术通常所使用的最小和 解码器的函数。假设关联到阶次dc的校验节点的边线从1标记到dc，称为边线索引，并且假设 表示阶次dc的校验节点的传入消息，使得mk表示对应于第k个边线索引的传 入消息。接着，为了计算对应于第dc个边线索引的校验节点的传出消息，Φc通过下式给出： 7 CN 111615793 A 说　明　书 4/22 页 值得注意的是，FAID和目前先进技术最小和解码器(和其变化形式)之间的主要差 异在于Φv的定义。已经表明，FAID的性能在BSC的错误平层区域中可优于传统的消息传递 解码器，并且存在具有阶次dv＝3的变量节点的代码的数值结果。另外，已经表明，具有不同 VN映射的多个FAID可用于进一步改进性能，代价是复杂性更高。 本发明的优选实施例具体集中于LDPC码，它的奇偶校验矩阵由子矩阵块构成，但 是本发明不限于此类代码。在这些优选实施例中，奇偶校验矩阵H组织成块或子矩阵，如等 式5中所定义， 其中子矩阵Hi,j(1≤i≤Mb，1≤j≤Nb)针对任何固定的j具有相等的竖直维度，并且 针对每个固定的i具有相等的水平维度。 列块被称为奇偶校验矩阵的子矩阵块的整列，列块索引j是指由子矩阵{Hi,j，1≤i ≤Mb}组成的第j个列块。类似地，行块被称为奇偶校验矩阵的子矩阵块的整行，并且行块索 引i是指由子矩阵{Hi ,j，1≤j≤Nb}组成的第i个行块。子矩阵的维度可以是任意的，并且在 子矩阵Hi,j是LxL方形矩阵的情况下，L可以是任意的。在本公开的优选实施例中，子矩阵Hi,j 是LxL方形矩阵，并且可为循环置换矩阵(CPM)、全零矩阵或循环置换矩阵的总和。此类型的 子矩阵常用于目前先进技术中，并且具有以下特殊性：它们可以由它们的第一行/列以及生 成其余行/列的程序定义。在循环置换矩阵中，每个行/列可以通过另一行/列的圆形(循环) 移位获得。其中奇偶校验矩阵组织成是循环置换矩阵的块的LDPC码被称为准循环LDPC(QC- LDPC)码。 CPM被定义为循环群组的基元的幂。例如，基元由等式6中所示的LxL矩阵P定义，其 中L＝8。 因此，CPM  Pk(k∈{0,...,L-1})具有恒等矩阵的形式，向左移位k个位置。换句话 说，Pk的第一列的非零值的行索引是k 1。索引k在本公开中将称为CPM移位值。由CPM的幂构 8 CN 111615793 A 说　明　书 5/22 页 成的奇偶校验矩阵的实例(L＝5，Mb＝3和Nb＝5)在等式7中给出。 在本公开中，如果Hi,j是全零子矩阵，那么子矩阵Hi,j被称为零子矩阵，否则它是非 零子矩阵，并且列块中所含的非零子矩阵的数目被称为列块阶次。含有零和非零子矩阵的 奇偶校验矩阵的实例在等式8中示出。 同样与本公开相关的是用于提高解码器收敛速度同时仍然维持低硬件复杂性的 分层式解码的概念。分层式LDPC解码方案通过减少实现成功解码所需要的解码迭代次数而 有效改进了收敛。分层式解码器产生从校验节点的子集到变量节点的子集的消息，然后产 生从变量节点的子集到校验节点的子集的消息。分层式解码器具有低资源使用，并且需要 较低的迭代平均次数。对于QC-LDPC码，行层通常由通过一组循环置换矩阵定义的PCM的L个 连续行构成。例如，等式5中的第i个行块定义第i个行层。类似地，列层由PCM的L个连续列构 成。例如，等式5中的第j个列块定义第j个列层。 存在两类主要的分层式解码：行或水平分层式解码和列或竖直分层式解码。在水 平分层式解码中，LDPC码的奇偶校验矩阵细分成多个行层，并且逐行层执行消息更新。在竖 直分层式解码中，奇偶校验矩阵分割成多个列层，并且逐列层执行消息计算。 层的概念可以进一步扩展到通用行层的概念，定义是： ·通用行层被定义为基矩阵的两个或更多个行层的串联，使得在通用行层的每个 列块中，存在最多一个非零子矩阵，同时它的其它块是零子矩阵。 ·完全通用行层还具有以下特性：通用行层的每个列块正好包含一个非零子矩 阵。 此定义确保对于具有最大列阶次dv的QC-LDPC码，PCM可以结构化成具有至少dv个 通用行层。为简单起见，并且在不损失一般性的情况下，在本公开中假设通用行层的数目通 常等于最大列阶次dv。在具有由通用行层组成的结构的PCM中，每个通用行层的行块可以按 9 CN 111615793 A 说　明　书 6/22 页 照任意次序组织，并且不限于只是PCM中的连续行层。另外，每个通用行层中的行块的数目 针对不同通用行层可为不同的。PCM的通用行层结构能够并行执行至少dv个子矩阵的处理， 而不具有数据存取冲突。 尽管具有上文所描述的现有技术，但是仍然非常需要可以提供错误率低得多的性 能并且能够以高得多吞吐量操作同时仍然维持低硬件成本的LDPC解码器。常规LDPC解码器 的一个主要问题是错误平层"的问题，其中解码器可能无法实现不足以用于许多存储系统 的足够低的错误率。常规方法会使用解码器，这些解码器使用大量硬件资源和功率来解决 错误平层问题，并且在需要高吞吐量时，这个问题会更严重。此外，需要解码器的硬件架构 是柔性的，使得解码器可以调谐到通道的特定条件，以实现最佳错误率性能。并且，先前文 献和公开案只关注了具有固定的列权重dv＝3的LDPC码的FAID，在错误校正方面并没有坚 固到足以用于存储应用。本发明旨在解决所有这些问题。
技术实现要素：
根据本发明，呈现一种与低密度奇偶校验(LDPC)码的迭代消息传递相关的方法和 设备。所述方法被称为竖直分层式有限字母迭代解码，它从属于通道输出字母表的通道接 收值作为输入，并作用于由子矩阵的行块和列块组成的奇偶校验矩阵，其中处理在构成多 个解码块的一或多个子矩阵上完成。在每个处理中，所述方法分别使用变量节点更新函数 和校验节点更新函数计算、更新和在代码的泰纳图中与解码块相关联的变量节点和校验节 点之间传递属于有限字母表的消息。所述处理按照任意次序从列块内的一个解码块向另一 解码块地或跨奇偶校验矩阵的不同列块地遍历整个奇偶校验矩阵。所述方法从通道接收可 构成用于硬决策解码的硬决策输入或用于软决策解码的软决策输入的值。 所述方法可使用单个或多个解码级，其中在每个解码级中，它可使用通道值或从 先前解码级生成的硬决策估计值或软决策估计值作为输入。在计算与解码块相关联的图形 的变量节点处的传出消息期间，可以在每个解码级中使用一或多个不同变量节点更新函数 来进一步提高成功解码的概率。所述方法适用于固定列权重和可变列权重的LDPC码。 在所述方法的实施例中的一个中，解码块是单个子矩阵，并且所述处理按照任意 次序从列块内的一个解码块遍历到另一解码块。此类方法被称为单子矩阵竖直分层式解 码。在另一实施例中，解码块是整个列块，其中处理遍历不同列块，并且所述方法作用于由 通用行层组成的奇偶校验矩阵，其中行层的数目至少等于奇偶校验矩阵的最大列块阶次。 此类方法被称为通用型单列竖直分层式解码。在另一实施例中，解码块含有奇偶校验矩阵 的一或多个列块，并且所述处理按照任意次序跨列块群组从一个解码块遍历到另一解码 块。此类方法被称为多列竖直分层式解码。 各个实施例呈现一种用于竖直有限字母表迭代解码器的设备，其中所述设备包 括：负责迭代地更新和在一或多个变量节点处理器和一或多个校验节点处理器之间传递消 息的模块，以及用于校验解码器是否已经收敛到码字并输出所述码字的模块。根据实施例， 所述设备另外包括用于计算校正子位的初始化模块。所述设备可基于接收到的输入而执行 硬决策解码或软决策解码，还可使用单个或多个解码级。 所述设备和它们的组件的各个实施例作为单子矩阵竖直分层式解码器、通用型单 列竖直分层式解码器和多列竖直分层式解码器的本发明的部分。所呈现的各个实施例实现 10 CN 111615793 A 说　明　书 7/22 页 解码器的极其高效的硬件实施方案，从而实现极高吞吐量及低硬件资源使用和电力使用。 本发明适用于采用LDPC码的系统和应用，例如固态驱动系统、嵌入式存储器系统和广泛的 任何采用LDPC码的存储和通信系统(包含无线和光通信)的快闪控制器。本发明中的设备还 适用于基于应用的现场可编程门阵列(FPGA)以及基于应用的专用集成电路(ASIC)。现将通 过实例和附图更详细地描述本发明的方法和设备的各个非限制性实施例和优选实施例。 附图说明 包含附图是为了提供对本发明的更深入理解，附图结合在本说明书中并且构成本 说明书的一部分，附图说明本发明的非限制性实施例，并且与描述内容一起用于阐释本发 明的原理。 图1示出具有列权重3的低密度奇偶校验码的泰纳图G的实例； 图2示出根据实施例的作用于由子矩阵组成的奇偶校验矩阵的竖直分层式有限字 母表迭代解码的方法，其中处理是在单个或多个子矩阵上进行的； 图3示出根据实施例的描述单子矩阵竖直分层式(SSVL)解码器、通用型单列竖直 分层式(SCVGL)解码器和多列竖直分层式(MCVL)解码器的顶层解码器架构的设备； 图4示出根据实施例的在列块阶次dv＝4的SCVGL解码器的情况下和在模块的输入 包括通道值时使用的初始化模块的架构； 图5示出根据实施例的在MCVL解码器的情况下使用的初始化模块的架构，其中列 块阶次dv＝4，并且解码块中所含的列块的数目W＝2； 图6示出根据实施例的在SSVL解码器的情况下的初始化模块的架构； 图7示出根据实施例的在SCVGL解码器的情况下的验证和输出模块的架构，其中列 块阶次dv＝4； 图8示出根据实施例的在MCVL解码器的情况下的验证和输出模块的架构，其中列 块阶次dv＝4，并且解码块中所含的列块的数目W＝2； 图9示出根据实施例的在SSVL解码器的情况下的验证和输出模块的架构； 图10示出根据实施例的在SCVGL解码器的情况下的解码环路的架构，其中列块阶 次dv＝4； 图11示出根据实施例的在MCVL解码器的情况下的解码环路的架构，其中列块阶次 dv＝4，并且解码块中所含的列块的数目W＝2； 图12示出根据实施例的在SSVL解码器的情况下的解码环路模块的架构； 图13示出根据实施例的用于SCVGL、MCVL和SSVL解码器的解码环路模块的变量节 点处理器的架构； 图14示出根据实施例的用于SCVGL、MCVL和SSVL解码器的变量节点单元(VNU)的架 构； 图15示出根据实施例的用于SCGVL和SSVL解码器的解码环路模块的校验节点处理 器的架构； 图16示出根据实施例的用于SCGVL和SSVL解码器的解码环路模块的校验节点处理 器的另一架构，其利用3端口存储器； 图17示出根据实施例的用于MCVL解码器的解码环路模块的校验节点处理器的架 11 CN 111615793 A 说　明　书 8/22 页 构； 图18示出根据实施例的SSVL解码器、SCVGL解码器和MCVL解码器的描述不包括初 始化模块的顶层解码器架构的设备； 图19示出根据实施例的SCVGL解码器的用于不包括初始化模块的顶层解码器架构 的解码环路模块的架构，其中列块阶次dv＝4；以及 图20示出根据实施例的SCVGL解码器、SCGVL解码器和SSVL解码器的用于不包括初 始化模块的顶层解码器架构的解码环路模块的校验节点处理器的架构。