减小复杂性的LDPC解码器

摘要

为了对K个信息比特被编码为N＞K个码字比特的码字的表现进行解码，在N个比特节点和N-K个校验节点之间交换消息。在计算期间，利用大于两个比特的完全消息长度表达各消息。在每个迭代中，存储交换的消息中的至少一些消息的表示。对于至少一个节点，如果存储从该节点发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的一个或多个消息的表示，并且利用所述完全消息长度存储另一个消息的表示。优选地，使用比所述完全消息长度少的比特存储的消息是从校验节点发送的消息。

说明书

技术领域

本文公开一种在不牺牲性能的情况下减小实现低密度奇偶校验(LDPC)解码所需的存储器的方法以及相关装置和系统。

背景技术

纠错码(ECC)通常用于通信和存储系统。通信信道中和存储装置中发生的各种物理现象导致破坏通信或存储的信息的噪声效果。纠错编码方案能够用于保护通信或存储的信息以避免由此引起的错误。通过在经通信信道传输或存储在存储装置之前对信息进行编码来实现这一点。编码处理通过把冗余码加入到信息来把信息比特序列i变换成码字v。随后能够使用这个冗余码以便通过解码处理从被破坏的码字v恢复该信息。ECC解码器对被破坏的码字y进行解码并恢复比特序列比特序列有高概率应该等于原始信息比特序列i。

一个常见的ECC类是线性二进制分组码的类。维度为K的长度为N的线性二进制分组码是长度为K的信息比特序列到长度为N的码字的线性映射，其中N＞K。码率定义为R＝K/N。维度为l×N的码字v的编码处理通常通过根据下面表达式把维度为l×K的信息比特序列i乘以维度为K×N的生成矩阵G来完成

v＝i·G    (1.1)

通常还定义维度为M×N的奇偶校验矩阵H，其中M＝N-K。该奇偶校验矩阵通过下面表达式与生成矩阵相关：

GH^T＝0    (1.2)

能够使用奇偶校验矩阵以便检查长度为N的二进制向量是否是有效码字。当且仅当下面表达式成立时l×N的二进制向量v是有效码字：

H·v^T＝0    (1.3)

近年来，迭代编码方案已变得非常普遍。在这些方案中，码构造为几个简单组成码的级联并且通过在简单码的组成解码器之间交换信息使用迭代解码算法而被解码。另一族的迭代解码器工作于能够使用描述校验节点和比特节点之间的相互联系的偶图定义的码。在这种情况下，解码可以被视为经偶图的边的消息的迭代传递。

一类普遍的迭代码是LDPC码。LDPC码是由稀疏奇偶校验矩阵H定义的线性二进制分组码。如图1中所示，该码也能够由具有N个比特节点的集合V、M个校验节点的集合C和把比特节点连接到校验节点的边的集合E的稀疏偶图G＝(V，C，E)定义。比特节点对应于码字比特，校验节点对应于比特的奇偶校验约束或者可替换地对应于奇偶校验矩阵H的行。一个比特节点由边连接到与该比特节点关联的校验节点。

能够使用迭代消息传递解码算法来解码LDPC码。这些算法通过经代表所述码的基本偶图的边在比特节点和校验节点之间交换消息而进行工作。解码器具有码字比特的初始估计值。初始估计值是一组可靠性度量。例如，如果数据存储在闪存中(在闪存中，用于保存数据的基本单元是单元(cell))，则每个比特的可靠性是从一组比特到被编程至闪存单元的状态的映射的函数。每个比特的可靠性还是从闪存单元读取的电压带的函数。通过施加作为有效码字的这些比特应该满足的奇偶校验约束，精炼并改进这些初始估计值(根据表达式(1.3))。这一点是通过使用经过图的边传递的消息在代表码字比特的比特节点和代表对码字比特的奇偶校验约束的校验节点之间交换信息来实现的。

在迭代解码算法中，经常使用“软”比特估计值，所述“软”比特估计值既传达比特估计值自身又传达比特估计值的可靠性。

由经过图的边传递的消息传达的比特估计值能够以多种形式表达。用于表达“软”比特估计值的常见度量是由下面表达式给出的对数似然比(LLR)：

$\mathrm{LLR}=\log \frac{\mathrm{Pr}(v=0|\mathrm{currentconstraintsandobservations})}{\mathrm{Pr}(v=1|\mathrm{currentconstraintsandobservations})}---\left(1.4\right)$

其中“current constraints and observations”是计算即将到来的消息时考虑的各种奇偶校验约束，并且观测值v对应于参与这些奇偶校验的比特的度量(例如，如果这些比特代表存储在诸如闪存的存储装置中的数据，则通常为阈值电压带的值的度量)。在不损失普遍性的情况下，在本文件的剩余部分使用LLR标记。LLR的符号提供比特估计值(即，正LLR对应于比特v＝0，负LLR对应于比特v＝1)。LLR的大小提供估计值的可靠性(即，|LLR|＝0意味着估计值完全不可靠，并且|LLR|＝∞意味着估计值完全可靠并且该比特值已知)。

通常，在解码操作期间在比特节点和校验节点之间经过图的边传递的消息是非本征的。经边e从节点n传递的非本征消息m可考虑在除边e之外的连接到节点n的边上接收的所有值(这就是为什么它被称为非本征的原因：它仅基于新的信息)。

消息传递解码算法的一个例子是置信传播(BP)算法，该算法是这个算法的族中的最好算法。基于接收或读取的符号y，假设

$P_v=\log \frac{\mathrm{Pr}(v=0|y)}{\mathrm{Pr}(v=1|y)}---\left(1.5\right)$

表示比特v的初始解码器估计值。需要注意的是，对于一些比特也可能不存在y观测值，在这种情况下，存在两种可能性：

第一种可能性：缩短的比特(shortend bits)。比特是已知的先验值并且P_v＝±∞(取决于该比特是0还是1)。

第二种可能性：收缩的比特(punctured bits)。比特是未知的先验值并且

$P_v{|}_{\mathrm{puncturedbit}}=\log \frac{\mathrm{Pr}(v=0)}{\mathrm{Pr}(v=1)}---\left(1.6\right)$

其中Pr(v＝0)是比特v为0的先验概率，Pr(v＝1)是比特v为1的先验概率。假设信息比特具有相同的为0或1的先验概率并且假设码是线性的，它采用下面表达式

$P_v{|}_{\mathrm{symctric},\mathrm{punctured}}=\log \frac{1/2}{1/2}=0---\left(1.7\right)$

假设

$Q_v=\log \frac{\mathrm{Pr}(v=0|\underset{‾}{y},H·\underset{‾}{v}=0)}{\mathrm{Pr}(v=1|\underset{‾}{y},H·\underset{‾}{v}=0)}---\left(1.8\right)$

其中比特v的最终解码器估计值，基于整个接收或读取的序列v，并假设比特v是码字的一部分(即，假设H·v^T＝0)。假设Q_vc表示从比特节点v到校验节点c的消息。假设R_cv表示从校验节点c到比特节点v的消息。BP算法使用下面的更新规则计算消息：

比特节点到校验节点的计算规则：

$Q_{\mathrm{vc}}=P_v+\underset{c^{\prime }\in N(v,G)\backslash c}{\Sigma }{R}_{c^{\prime }v}---\left(2.1\right)$

其中，N(n，G)表示图G中的节点n的邻居的集合。

校验节点到比特节点的计算规则：

其中，在群{0，1}×R⁺上完成和域中的运算(这基本上意味着这里的求和定义为大小的求和以及符号的异或(XOR))。比特v的最终解码器估计值是：

$Q_v=P_v+\underset{c^{\prime }\in N(v,G)}{\Sigma }{R}_{c^{\prime }v}---\left(2.3\right)$

在消息传递解码期间传递消息的次序称为解码调度(decodingschedule)。BP解码不意味着使用特定调度-它仅定义计算规则(2.1)、(2.2)和(2.3)。解码调度不影响码的预期纠错能力。然而，解码调度能够显著影响解码器的收敛速度和解码器的复杂性。

用于对LDPC码进行解码的标准消息传递调度是洪水式调度(flooding schedule)，其中在每次迭代中所有变量节点并且随后所有校验节点向它们的邻居传递新消息。在图2中给出基于洪水式调度的标准BP算法。

基于洪水式调度的BP算法的标准实现方式在存储器要求方面比较昂贵。需要存储总共2|V|+2|E|个消息(用于存储P_v、Q_v、Q_vc和R_cv消息)。此外，洪水式调度表现出低收敛速度并因此得到能够按照给定解码吞吐量提供所需的纠错能力的更高的解码逻辑。

更高效的串行消息传递解码调度在文献资料中是已知的。在串行消息传递调度中，串行地遍历(traverse)比特节点或校验节点，并且对于每个节点，相应消息被发送给该节点以及从该节点发出。例如，通过按一定次序串行地遍历图中的校验节点能够实现串行消息传递调度，并且对于每个校验节点c∈C发送下面的消息：

1、Q_vc，对于每个v∈N(c)(即，进入节点c的所有Q_vc消息)。

2、R_cv，对于每个v∈N(c)(即，来自节点c的所有R_cv消息)。

与洪水式调度相比，串行调度能够在图上实现更快的信息的传播，从而导致更快的收敛(大约两倍)。此外，串行调度能够在显著减小存储器要求的情况下高效地实现。通过下面的方式实现这一点：使用Q_v消息和R_cv消息以便在运行中计算Q_vc消息，由此不需要使用另外的存储器存储Q_vc消息。通过基于表达式(2.1)和(2.3)把Q_vc表达为(Q_v-R_cv)来实现这一点。另外，利用先验消息P_v初始化的同一存储器用于存储迭代更新的Q_v后验消息。因为在串行调度中仅需要使用的知识，而在洪水式调度的标准实现方式中使用数据结构和从而需要用于存储码的图结构的存储器的两倍大，所以获得存储器要求的另外的减小。这种串行调度解码算法显示在图3中。

作为总结，串行解码调度具有几项优点：

(1)与标准洪水式调度相比，串行解码调度使收敛速度加速两倍。这意味着，与基于洪水式调度的解码器相比，为了按照给定吞吐量提供给定的纠错能力，仅需要一半的解码器逻辑。

(2)串行解码调度提供了解码器的存储器高效实现方式。需要用于仅存储|V|+|E|个消息的RAM(而非如标准洪水式调度中那样存储2|V|+2|E|个消息)。与标准洪水式调度相比，需要用于存储码的图结构的ROM的一半大小。

(3)“运行中”收敛测试能够实现为在迭代期间完成的计算的一部分，从而允许在迭代期间的收敛检测和在任何点的解码终止。这能够节省解码时间和能耗。

用于实现串行消息传递解码算法的基本解码器架构和数据路径显示在图4中。这种架构包括：

1)Q-RAM：用于存储迭代更新的Q_v消息(初始化为P_v消息)的存储器。

2)R-RAM：用于存储R_cv边消息的存储器。

3)处理单元，用于实现更新消息时所涉及的计算。

4)路由层，负责把消息从存储器发送到处理单元，反之亦然。

5)存储器，用于存储码的图结构，所述图结构负责存储器寻址并控制路由层的切换。

迭代编码系统表现出称为误码平台的不希望的效应，如图5中所示，其中当负责比特误差的通信信道或存储器装置中的“噪声”变小时，在解码器的输出端的比特误码率(BER)开始以慢得多的速度减小。这种效应难以解决，尤其是在所需的解码器输出比特误码率应该非常小(～1e^-15)的存储系统中。需要注意的是，在图5中，噪声向右侧增加。

众所周知，迭代编码系统的纠错能力和误码平台随着码长增加而提高(这适用于任何ECC系统，但是尤其适用于纠错能力在短码长相当差的迭代编码系统)。不幸的是，在迭代编码系统中，解码硬件的存储器复杂性与码长成比例；因此使用长码招致高复杂性的惩罚。

可以使用次优的解码算法以在存储器要求和逻辑复杂性方面都减小解码器复杂性。然而，因此解码器在瀑布区域中或在误码平台区域中或者在这两个区域中都表现出减小的纠错能力。

发明内容

由于消息传递解码技术的普遍性尤其是与LDPC码的关联，减小解码器的复杂性的主题是广泛研究的领域。在学术界和工业上都在努力寻找减小保存消息所需的存储量以及简化计算单元的方法，以便使这类码的解码器的实现方式的价格和功耗都保持在最小程度并且使纠错能力的退化程度最小。

多数常规LDPC解码算法以性能的退化为代价减小解码器的复杂性。这里描述了这样的一种方法：该方法用于实现最佳BP解码算法(即，没有任何性能损失)，同时减小存储器大小要求并且同时提供处理单元的简单的低复杂性固定点实现方式，从而使电路实现方式中的功耗和硬件(硅)占位面积(footprint)最小化。

本文描述的算法减小存储的消息的数量(仅保存Q_c估计值，而在运行中产生Q_vc消息)，压缩消息(例如，对于多数R_cv消息仅保存一位‘ε’[见稍后描述])，但保持置信传播算法的最佳性能。

本文提供的一个实施例是一种对码字的表现进行解码的方法，其中K个信息比特被编码为N＞K个码字比特，该方法包括：(a)通过下面的步骤更新码字比特的估计值：在包括N个比特节点和N-K个校验节点的图中，在至少一个消息交换迭代期间在比特节点和校验节点之间交换消息；(b)定义大于两个比特的完全消息长度，利用所述完全消息长度在计算期间表达各消息；(c)在每个迭代中，存储在比特节点和校验节点之间交换的消息的至少一部分的表示；其中，对于所述节点中的至少一个，如果存储在所述至少一个迭代之一期间从该节点发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供的另一实施例是一种对码字的表现进行解码的解码器，其中K个信息比特被编码为N＞K个码字比特，所述解码器包括：(a)至少一个存储器；以及(b)至少一个处理器，用于通过执行根据下面的步骤更新码字比特的估计值的算法对码字的表现进行解码：(i)在包括N个比特节点和N-K个校验节点的图中，在至少一个消息交换迭代期间在比特节点和校验节点之间交换消息，利用大于两个比特的完全消息长度在计算期间表达各消息，(ii)在所述至少一个存储器中，存储在比特节点和校验节点之间交换的消息的至少一部分的表示，其中，对于所述节点中的至少一个，如果存储在所述至少一个迭代之一期间从该节点发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供的另一实施例是一种存储器控制器，包括：(a)编码器，用于把K个信息比特编码为N＞K个码字比特的码字；(b)解码器，包括：(i)至少一个存储器；以及(ii)至少一个处理器，用于通过执行根据下面的步骤更新码字比特的估计值的算法对码字的表现进行解码：(A)在包括N个比特节点和N-K个校验节点的图中，在至少一个消息交换迭代期间在比特节点和校验节点之间交换消息，利用大于两个比特的完全消息长度在计算期间表达各消息，以及(B)在所述至少一个解码器存储器中，存储在比特节点和校验节点之间交换的消息的至少一部分的表示，其中，对于所述节点中的至少一个，如果存储在所述至少一个迭代之一期间从该节点发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供的另一实施例是一种接收器，包括：(a)解调制器，对从通信信道接收的消息进行解调制，由此提供K个信息比特被编码为N＞K个码字比特的码字的表现；(b)解码器，包括：(i)至少一个存储器；以及(ii)至少一个处理器，通过执行根据下面的步骤更新码字比特的估计值的算法对码字的表现进行解码：(A)在包括N个比特节点和N-K个校验节点的图中，在至少一个消息交换迭代期间在比特节点和校验节点之间交换消息，利用大于两个比特的完全消息长度在计算期间表达各消息，以及(B)在所述至少一个存储器中，存储在比特节点和校验节点之间交换的消息的至少一部分的表示，其中，对于所述节点中的至少一个，如果存储在所述至少一个迭代之一期间从该节点发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供的另一实施例是一种用于发送和接收消息的通信系统，包括：(a)发射器，包括：(i)编码器，用于把消息的K个信息比特编码为N＞K个码字比特的码字，(ii)调制器，用于经由通信信道按照调制信号发送所述码字；(b)接收器，包括：(i)解调制器，从通信信道接收所述调制信号并对所述调制信号进行解调制，由此提供所述码字的表现，(ii)解码器，包括：(A)至少一个存储器；以及(B)至少一个处理器，通过执行根据下面的步骤更新码字比特的估计值的算法对码字的表现进行解码：(I)在包括N个比特节点和N-K个校验节点的图中，在至少一个消息交换迭代期间在比特节点和校验节点之间交换消息，利用大于两个比特的完全消息长度在计算期间表达各消息，(II)在所述至少一个存储器中，存储在比特节点和校验节点之间交换的消息的至少一部分的表示，其中，对于所述节点中的至少一个，如果存储在所述至少一个迭代之一期间从该节点发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

存在两种常见的LDPC码的表示(representation)。一种表示使用奇偶校验矩阵，并因此在矩阵的行和列之间经由消息交换信息。另一种表示使用偶图。对于本领域技术人员而言已知的是，这些表示是等同的。以上的实施例对应于偶图表示。下面的一组实施例对应于奇偶校验矩阵表示。

本文提供的另一实施例是一种对码字的表现进行解码的方法，其中K个信息比特编码为N＞K个码字比特，该方法包括：(a)提供具有N-K行和N列的奇偶校验矩阵；(b)通过下面的步骤更新码字比特的估计值：在至少一个消息交换迭代期间在所述矩阵的行和列之间交换消息；(c)定义大于两个比特的完全消息长度，利用所述完全消息长度在计算期间表达各消息；(d)存储在行和列之间交换的消息的至少一部分的表示；其中，对于所述行或列中的至少一个，如果存储在所述至少一个迭代之一期间从该行或列发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供的另一实施例是一种对码字的表现进行解码的解码器，其中K个信息比特被编码为N＞K个码字比特，该解码器包括：(a)至少一个存储器；以及(b)至少一个处理器，用于通过执行根据下面的步骤更新码字比特的估计值的算法对码字的表现进行解码：(i)提供具有N-K行和N列的奇偶校验矩阵，(ii)在至少一个消息交换迭代期间在所述矩阵的行和列之间交换消息，利用大于两个比特的完全消息长度表达各消息，(iii)在所述至少一个存储器中，存储在行和列之间交换的消息的至少一部分的表示，其中，对于所述行或列中的至少一个，如果存储在所述至少一个迭代之一期间从该行或列发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供的另一实施例是一种存储器控制器，包括：(a)编码器，用于把K个信息比特编码为N＞K个码字比特的码字；以及(b)解码器，包括：(i)至少一个解码器存储器；以及(ii)至少一个处理器，用于通过执行根据下面的步骤更新码字比特的估计值的算法对码字的表现进行解码：(A)提供具有N-K行和N列的奇偶校验矩阵，(B)在至少一个消息交换迭代期间在所述矩阵的行和列之间交换消息，利用大于两个比特的完全消息长度在计算期间表达各消息，以及(C)在所述至少一个存储器中，存储行和列之间交换的消息的至少一部分的表示，其中，对于所述行或列中的至少一个，如果存储在所述至少一个迭代之一期间从该行或列发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供的另一实施例是一种接收器，包括：(a)解调制器，用于对从通信信道接收的消息进行解调制，由此提供K个信息比特被编码为N＞K个码字比特的码字的表现；(b)解码器，包括：(i)至少一个存储器；以及(ii)至少一个处理器，用于通过执行根据下面的步骤更新码字比特的估计值的算法对码字的表现进行解码：(A)提供具有N-K行和N列的奇偶校验矩阵，(B)在至少一个消息交换迭代期间在所述矩阵的行和列之间交换消息，利用大于两个比特的完全消息长度在计算期间表达各消息，(C)在所述至少一个存储器中，存储行和列之间交换的消息的至少一部分的表示，其中，对于所述行或列中的至少一个，如果存储在所述至少一个迭代之一期间从该行或列发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供的另一实施例是一种用于发送和接收消息的通信系统，包括：(a)发射器，包括：(i)编码器，用于把消息的K个信息比特编码为N＞K个码字比特的码字，以及(ii)调制器，用于经由通信信道按照调制信号发送所述码字；(b)接收器，包括：(i)解调制器，用于从通信信道接收调制信号并对调制信号解调制，由此提供码字的表现，以及(ii)解码器，包括：(A)至少一个存储器；以及(B)至少一个处理器，通过执行根据下面的步骤更新码字比特的估计值的算法对码字的表现进行解码：(I)提供具有N-K行和N列的奇偶校验矩阵，(II)在至少一个消息交换迭代期间在所述矩阵的行和列之间交换消息，利用大于两个比特的完全消息长度在计算期间表达各消息，(III)在所述至少一个存储器中，存储在行和列之间交换的消息的至少一部分的表示，其中，对于所述行或列中的至少一个，如果存储在所述至少一个迭代之一期间从该行或列发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。

本文提供了两种通常的对码字的表现进行解码的方法，其中K个信息比特被编码为N＞K个码字比特。所解码的仅是码字的表现(manifestation)而非实际码字，因为在应用这些方法之一进行解码之前码字可能已被噪声破坏。

根据第一种通用方法，迭代地更新码字比特的估计值。在包括N个比特节点和N-K个校验节点的图中，在一个或多个消息交换迭代中在比特节点和校验节点之间交换消息。

术语“消息长度”在本文定义为用于在存储器中存储消息的比特的数量。定义大于两个比特的完全消息长度，从而利用所述完全消息长度在计算期间表达各消息。例如，在以下描述的优选实施例中，在计算期间使用的完全消息长度为n+m+1：n个整数比特、m个小数比特和代表数的符号的1个比特。

在每个迭代中，存储在比特节点和校验节点之间交换的消息中的至少一些消息的表示。如本文中所理解，数字的“表达”是数字自身或者该数字的近似值。数字的“表示”是数字的表达或者特定于数字的信息，根据所述特定于数字的信息(可能结合不特定于该数字的其它信息)能够获得该数字。例如，在以下描述的优选实施例中，R_c不特定于任何一个消息R_cv，从而用于存储R_c的比特不计算在用于存储R_cv的表示的比特之中。用于存储R_cv的索引的比特也不计算在用于存储R_cv的表示的比特之中，因为索引比特不提供关于R_cv的值的信息。

对于所述节点中的至少一个，如果存储在一个迭代期间从该节点发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示。优选地，使用完全消息长度来存储在该迭代中从所述节点发送的另一个消息的表示。

优选地，使用至少两个比特但使用比所述完全消息长度少的比特来存储除所述另一个消息之外的在所述一个迭代期间从该节点发送的所有消息。此外，优选地，使用正好两个比特存储使用比所述完全消息长度少的比特存储的消息。例如，在以下描述的优选实施例中，除之外的所有R_cv存储为符号比特加上说明|R_cv|是|R_c|还是|R_c|+1的1个比特，而利用所述完全消息长度存储

优选地，使用比所述完全消息长度少的比特存储所述消息中的至少一个消息的表示的节点是校验节点。更优选地，存储在所述迭代(或多个迭代之一)期间从校验节点发送的所有消息的表示。对于每个校验节点，使用至少两个比特但使用比所述完全消息长度少的比特来存储从该校验节点发送的所述消息中的至少一个消息的表示并且利用所述完全消息长度存储从该校验节点发送的另一个消息的表示。

优选地，对于存储在所述迭代(或多个迭代之一)期间从该节点发送的消息的表示的每个节点，使用至少两个比特但使用比所述完全消息长度少的比特来存储从该节点发送的所述消息中的至少一个消息的表示并且利用所述完全消息长度存储从该节点发送的另一个消息的表示。

优选地，对于所述节点中的一个或多个节点，在存储从该节点发送的消息的表示的每个迭代中，使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示并且利用所述完全消息长度存储另一个消息的表示。

优选地，根据置信传播算法(例如，根据洪水式调度或根据串行调度)交换所述消息。

根据第二种通用方法，迭代地更新码字比特的估计值。在一个或多个消息交换迭代中，在具有N-K行和N列的奇偶校验矩阵的行和列之间交换消息。定义大于两个比特的完全消息长度，从而利用所述完全消息长度在计算期间表达各消息。在每个迭代中，存储在所述矩阵的行和列之间交换的消息中的至少一些消息的表示。对于所述行或列中的至少一个，如果存储在所述迭代之一期间从该行或列发送的消息的表示，则使用至少两个比特但使用比所述完全消息长度少的比特来存储所述消息中的至少一个消息的表示，并且利用所述完全消息长度存储另一个消息的表示。

对应于第一种通用方法或第二种通用方法的解码器包括：一个或多个存储器；和一个或多个处理器，用于通过执行实现第一通用方法或第二通用方法的算法对码字的表现进行解码，所存储的所述表示被存储在所述存储器或多个存储器中。

对应于第一通用方法或第二通用方法的存储器控制器包括：编码器，用于把K个信息比特编码为N＞K个码字比特的码字；和解码器，对应于第一通用方法。通常，该存储器控制器还包括：电路，用于把所述码字的至少一部分存储在主存储器中并从该主存储器检索所述码字(一部分)的表现。

对应于第一通用方法或第二通用方法的存储器装置包括这种存储器控制器和所述主存储器。

对应于第一通用方法或第二通用方法的接收器包括：解调制器，用于对从通信信道接收的消息进行解调制。解调制器提供K个信息比特被编码为N＞K个码字比特的码字的表现。这种接收器还包括对应于第一通用方法或第二通用方法的解码器。

对应于第一通用方法或第二通用方法的通信系统包括发射器和接收器。发射器包括：编码器，用于把消息的K个信息比特编码为N＞K个码字比特的码字；和调制器，用于经由通信信道按照调制信号发送所述码字。该接收器是对应于第一通用方法或第二通用方法的接收器。

附图说明

这里参照附图仅作为示例描述了各种实施例，其中：

图1表示稀疏奇偶校验矩阵和稀疏偶图之间的等价性；

图2显示洪水式调度置信传播算法；

图3显示校验节点串行调度置信传播算法；

图4表示串行调度消息传递解码器的基本架构和数据路径；

图5表示误码平台现象；

图6是函数的曲线图；

图7和8是定理1的图形表示；

图9显示作为‘d_c’的函数的R-RAM存储器减小；

图10显示作为‘d_c’的函数的总RAM存储器的减小；

图11表示用于实现洪水式调度置信传播算法的固定点方式的常规解码器的基本架构和数据路径；

图12表示用于实现洪水式调度置信传播算法的固定点方式的在减小的存储器要求的情况下工作的解码器的基本架构和数据路径；

图13代表图12的解码器的变量节点处理器算法；

图14表示图12的解码器的校验节点处理器算法；

图15表示用于实现串行调度置信传播算法的固定点方式的常规解码器的基本架构和数据路径；

图16表示用于实现串行调度置信传播算法的固定点方式的具有减小的存储器要求的解码器的基本架构和数据路径；

图17是其控制器包括存储器减小的解码器的闪存装置的高级示意性框图；

图18是图17的闪存装置的控制器的高级局部示意性框图；

图19是其接收器包括存储器减小的解码器的通信系统的高级示意性框图。

具体实施方式

参照附图和相应描述可以更好地理解根据本发明的LDPC解码的原理和操作。

下面是图3中表示的串行调度BP解码算法的固定点方式和关联的在存储器和逻辑方面都具有减小的复杂性的解码器的描述。

在不损失普遍性的情况下，假设由解码器使用的LLR的对数底数是2。通常的方法不限于这种情况，但底数2的LLR提供了解码器的数字电路的方便和高效的实现方式。

该方法基于这样的观测：存储在解码器存储器中的R_cv消息能够被压缩并且更简洁地表示。这种观测由下面的定理支持：

定理1：

假故$v_{\min }=\arg \underset{v}{\min }\left\{\right|Q_{\mathrm{vc}}|,v\in N\left(c\right)\}$并且

则$\forall v\ne v_{\min },\left|R_{\mathrm{cv}}\right|-\left|R_c\right|\le 1$

证明：

在底数2的LLR的特殊情况下，函数变为如下定义的函数

假设再次参照附图，能够看出图6中显示的函数满足下面的性质：

(2)单调减小

证明该定理的第一步骤在于证明下面的引理：

给定几个元素之和，如果从所述和中排除不是最大元素的一个元素，则子和(排除该非最大元素的元素之和)是原始和(所有元素之和)的至少一半。

这个引理的数学定义如下：

如果则对于每个s_j≠s^max＝max{s₁，s₂，...}，下面的表达式成立：

$-s_j+\underset{i}{\Sigma }{s}_i\ge \frac{1}{2}·\underset{i}{\Sigma }{s}_i---\left(3.4\right)$

这个表达式对于正数值s₁，s₂，...s_n，n≥2的任何集合成立并且独立于上面定义的函数

证明：把表达式(3.4)的右侧表示为除s_j之外的元素的和加上元素‘s_j’，对表达式(3.4)的左侧进行相同的处理：

$\frac{1}{2}·\underset{i}{\Sigma }{s}_i=\frac{s_j}{2}+\frac{1}{2}·\underset{i\ne j}{\Sigma }{s}_i,$$-s_j+\underset{i}{\Sigma }{s}_i=-s_j+s_j+\underset{i\ne j}{\Sigma }{s}_i---\left(3.5\right)$

根据(3.5)，足以证明：

$\frac{s_j}{2}+\frac{1}{2}·\underset{i\ne j}{\Sigma }{s}_i\le -s_j+s_i+\underset{i\ne j}{\Sigma }{s}_i\to \frac{s_j}{2}\le \frac{1}{2}·\underset{i\ne j}{\Sigma }{s}_i\to s_j\le \underset{i\ne j}{\Sigma }{s}_i---\left(3.6\right)$

因为s_j≠s^max，所以能够把表达式(3.6)的右侧表示为s^max加上所述和中的其它元素，假设s^max＝s_k，因此：

$s_j\le s^{\max }+\underset{i\ne j,k}{\Sigma }{s}_i---\left(3.7\right)$

表达式(3.7)成立，因为s^max自身就大于s_j自身，更不必说当把其它正数值加到s_j。

证明该定理的第二步骤在于证明：

如果a＞b≥a/2；a，b≥0，则

因为单调减小，所以很明显因此，当‘b’最小时，和之差最大。因此，对于b＝a/2，足以证明表达式(3.8)。现在假设b＝a/2，证明等同于然而这已经作为上面给出的函数的第六性质给出，因此证明了表达式(3.8)。

该定理的证明的第三步骤在于定义a＝R_c，b＝R_cv。然后，基于表达式(2.2)中的R_c和R_cv的定义，下面的表达式成立：

根据v_min的定义和的性质(见图6)，显然，

$\forall v\ne v_{\min }$

这意味着是和中的最大元素。根据第一步骤中提供的引理(表达式3.4)：

它等同于：

根据表达式(4.3)，很显然：

因为

把表达式(4.4)带入表达式(4.5)，得到：

现在，定义R：

把‘y’定义为

把定义(4.9)插入定义(4.8)，得到：

现在，把表达式(3.3)中的的性质(6)和性质(2)应用于表达式(4.10)，定义(4.8)中所定义的‘R’满足：

R≤1    (4.11)

现在把表达式(4.7)带入到定义(4.8)，并利用表达式(3.3)中的的性质(5)。结果是：

组合不等式(4.11)和(4.12)，得到：

$\forall v\ne v_{\min }:\left|R_{\mathrm{cv}}\right|-\left|R_c\right|\le R\le 1---\left(4.13\right)$

根据不等式(4.13)，显然：

$\forall v\ne v_{\min }:\left|R_{\mathrm{cv}}\right|-\left|R_c\right|\le 1---\left(4.14\right)$

利用不等式(4.14)，证明了定理1。定理1的直接优点在于：为了在一个校验节点重构所有R_cv消息，需要在存储器中保存的只是如(3.1)的定理1的陈述中所定义的R_c，对于每个v≠v_min，仅保存R_cv的一比特表达而无论|R_cv|＝|R_c|还是|R_cv|＝|R_c|+1，对于v_min，单独保存(中的‘min’表示进入校验节点的相应Q_vc^min消息是进入该校验节点的所有Q_vc消息之中的最小值Q_vc；中的‘max’表示Q_vc^min到达的边上发送的结果R_cv消息是从这个校验节点发送的所有其它R_cv消息之中从这个校验节点发送的最大值消息)。图7和图8中提供了这种观测的图形表示(定理1)。在图7中，描绘了从x域到域的变换。显然，域中的最大值明显属于Q_vc^min。

在图8中，从域回到x域，计算R_cv消息。在图中的每个边‘k’(见图1)，从变量节点向校验节点传递Q_vc-k消息。在同一边的另一方向，从校验节点向变量节点发送消息R_cv-k。在图8中，强调所有R_cv消息(除外)至多与R_c相隔距离‘1’。因此，存储器足以保存R_c、的索引(即，从校验节点发送的哪个消息中与对应的消息)和用于所有其它R_cv消息的一个比特(所述一个比特对于这些消息中的每个消息指示该消息的大小是等于|R_c|还是等于|R_c|+1)。另外，对于每个R_cv消息，需要存储符号比特。

现在，很清楚的是，随着每个校验节点保存的R_cv消息的数量的增加，存储器使用方面的节省增加。这个数量表示为d_c，校验节点度(check node degree)。

假设在BP解码算法的固定点实现方式中，使用消息的(1.n.m)均匀量化：每个消息由一个符号比特、n个整数比特和m个小数比特表示。考虑连接到d_c个变量节点的校验节点c(即，|N(c，G)|＝d_c)。根据BP解码算法的常规固定点实现方式，需要d_c·(1+n+m)比特的存储器以便存储一个校验节点的所有消息然而，在本方法中，利用在定理1中证明的性质，仅使用比特存储一个校验节点的消息如果所有校验节点具有d_c个邻居，则图4中显示的解码器R-RAM存储器的大小按照以下因子减小：

表达式4.15能够简化为：

图9显示在‘d_c’设置为从20到32的同时针对‘n’和‘m’的几个值作为‘d_c’的函数的R-RAM(按照百分比)减小的部分。

把码率表示为‘r’并且假设LDPC码具有平均节点度和平均校验度则码率为：

$r=1-\frac{\overline{d_v}}{\overline{d_c}}---\left(4.17\right)$

假设保持恒定，则当码率增加时也增加，从而本方法对高码率的码特别有益。如果码长为N_v并且独立校验节点的数量为N_c，则码率也能够表示为：

$r=1-\frac{N_c}{N_v}---\left(4.18\right)$

根据表达式(4.17)和(4.18)，可推断：

$\frac{\overline{d_v}}{\overline{d_c}}=\frac{N_c}{N_v}---\left(4.19\right)$

假设常规串行解码器在Q-RAM中为每个Q_v消息保存2+n+m比特，则组合的Q-RAM和R-RAM按照以下因子减小：

把表达式(4.19)带入表达式(4.20)，这个减小因子为：

把表达式(4.17)带回到表达式(4.21)，因此作为码率‘r’和‘d_c’的函数的减小为：

图10显示在采用n＝5，m＝0的情况下，如图9中那样对于从20到32的d_c值针对几个码率，根据表达式(4.22)的总RAM大小的减小。从图10能够看出，对于d_c较高的高速LDPC码，R-RAM减小因子更大。例如，考虑IEEE802.3an标准中定义的码率0.8413RS-LDPC。这种码具有d_c＝32。另外，假设具有(1.n.m)＝(1.5.0)的消息量化的固定点实现方式。仿真结果显示：这种量化提供了接近最佳的结果，即与等效的常规浮点BP解码器相比可忽略的退化。例如，根据本文提供的方法的R-RAM尺寸需要常规实现方式所需的R-RAM尺寸的40.63％。

需要注意的是，R-RAM是解码器中最大的存储器，因此，在这个例子中，根据本文提供的方法的总的解码器存储器大小应该是常规解码器的总的解码器存储器大小的大约50％-55％。此外，R-RAM存储器大小的减小也影响解码器的功耗，因为在每个时钟中在R-RAM数据总线上驱动更少的比特。

接下来，描述本文描述的解码方法和解码器的两个示例性实施例。这些实施例中的每一个举例说明该方法的不同方面。第一实施例举例说明基于洪水式调度器的解码器。第二实施例举例说明串行调度器。

为了简单并且不损失普遍性，假设解码器使用单个处理单元。另外，假设LDPC码是右正则的(right regular)，即它的奇偶校验矩阵的每一行中的1的数量(或者从它的基本偶图表示中的每个校验节点发出的边的数量)恒定并等于d_c。对于本领域技术人员而言，归纳所描述的解码器架构以支持更多处理单元和/或非正则LDPC码的是简单并且已知的。还假设消息量化是(1.n.0)，即“浮点”消息被量化为范围[-(2ⁿ-1)：2ⁿ-1]中的最接近的整数并且小数部分是0。这适用于把消息存储在存储器中，然而在处理单元中的消息更新过程期间可应用更高的分辨率。

常规解码器210的基本架构和数据路径表示在图11中。常规解码器210实现图2中描述的洪水式调度BP解码器的固定点方式。在每个解码迭代(定义为所有消息的单次更新)中，常规解码器210使用校验节点处理器218处理所有奇偶校验，然后使用变量节点处理器216处理所有变量节点(variable node)。为了支持这种处理，奇偶校验矩阵的非零元素的表示存储在矩阵ROM(M-ROM)220和222中。可替换地，解码器210能够设置为首先在每个迭代中处理所有变量节点，然后才处理所有校验节点。

假如读时钟与写时钟分开或者保存Q_vc消息的Q-RAM 214和保存R_cv消息的R-RAM 212都设置为双端口RAM，则图11中表示的架构也能够同时处理变量节点和校验节点。根据这个实施例，在d_c个连续时钟期间处理每个奇偶校验节点，并且在d_v个连续时钟期间处理每个变量节点。

因为在每个迭代期间穿过E＝N×d_v＝M×d_c个边，所以所有Q_vc和所有R_cv消息更新需要相同数量的时钟，而与更新单个校验节点所需的平均时钟数量相比，单个变量节点的更新平均需要更少的时钟(因为校验节点总是比变量节点更少)。更新消息被写回到适当的存储器：更新的Q_vc消息写回到Q-RAM 214，而更新的R_cv消息写回到R-RAM 212。

根据本文提供的方法的洪水式调度实施例的基本解码器架构和解码器数据路径表示在图12中。根据这个实施例的减小存储器的解码器230实现与解码器210中常规地实现的BP解码器的固定点方式相同的图2中描述的BP解码器的固定点方式。解码器230使用校验节点处理器240相继处理奇偶校验并使用变量节点处理器238相继处理变量节点。平均地，在d_c个连续时钟期间处理每个奇偶校验。在d_v个连续时钟期间处理每个变量节点。如常规解码器210中那样，奇偶校验矩阵的非零元素的表示存储在矩阵ROM(M-ROM)242和244中，并且Q_vc消息存储在Q-RAM 236中。

然而，R_cv消息“压缩”地存储在两个存储器中：R-RAM1 232和R-RAM2 234中。R-RAM1 232中的每个存储器地址存储两个比特，一个比特指示相应R_cv消息的符号，另一个比特指示|R_cv|＝|R_c|还是|R_cv|＝|R_c|+1。对于每个奇偶校验节点，R-RAM1 232包含d_c-1个元素，每个元素包含关于除之外与奇偶校验节点相关的R_cv消息之一的信息。R-RAM2存储器234具有M个地址，每个奇偶校验节点具有一个地址。R-RAM2234中的每个存储器地址存储与奇偶校验之一相关的|R_c|和v_min索引。因此，每个R-RAM2 234地址存储个比特。

如常规解码器210中那样，Q-RAM 236保存N×d_v个条目。每组的连续d_v个消息是从一个变量节点发送的Q_vc消息。

需要注意的是，在解码器230中，通过逐个处理奇偶校验节点的相关消息(即，按照每时钟周期一个消息的方式把消息读取到处理器中)来处理奇偶校验节点。也可以并行处理奇偶校验消息以便增加解码器的吞吐量。

图13表示解码器230的变量节点处理器算法。与图2的算法相比的主要差别在于根据存储器R-RAM1232和R-RAM2234中的R_cv消息的相应表示对R_cv消息的重构。

图14表示解码器230的校验节点处理器算法。与图2的算法相比的主要差别在于把R_cv消息存储在R-RAM1 232和R-RAM2 234中。R_cv消息以它们的“压缩”形式存储。需要注意的是，这种压缩不损失任何信息。

第二实施例举例说明基于串行调度器的解码器，其中串行调度器的计算部分保持原样，而根据本文提供的方法提供R_cv的存储和载入。

相应的常规串行调度解码器250的基本解码器架构和数据路径显示在图15中。解码器250实现图3中显示的串行调度BP解码器算法的固定点方式。解码器250一个接一个地处理奇偶校验节点(“顺序寻址”)。在d_c个连续时钟期间处理每个奇偶校验节点。在每个时钟期间，分别从Q-RAM存储器254和R-RAM存储器252读取单个Q_v消息和单个R_cv消息，并把它们发送到处理器256。串行调度器的优点之一在于：替代于保存M×d_c个消息(Q_vc)，当在运行中计算Q_vc消息时仅保存N个消息(保持Q_v)。

处理器256更新消息并把消息写回到存储器252和254。设计这个过程，从而在每个时钟中从存储器252和254读取一组新的消息/把一组新的消息写入到存储器252和254。

根据本文提供的方法的串行调度实施例的减小存储器的解码器270的基本架构和数据路径表示在图16中。解码器270实现与解码器250中常规地实现的串行调度BP解码器的固定点方式相同的图3中描述的串行调度BP解码器的固定点方式。解码器270相继地处理奇偶校验(“顺序寻址”)。在d_c个连续时钟期间处理每个奇偶校验。在每个时钟期间，从Q-RAM存储器276读取单个Q_v消息。然而，R_cv消息“压缩”地存储在两个存储器中：R-RAM1 272和R-RAM2 274。R-RAM1 272中的每个存储器地址存储两个比特，一个比特指示R_cv消息的符号，一个比特指示|R_cv|＝|R_c|还是|R_cv|＝|R_c|+1。对于每个奇偶校验节点，R-RAM1272包含d_c-1个地址，每个地址包含关于除之外与奇偶校验相关的R_cv消息之一的信息。R-RAM2存储器274具有M个地址，一个地址用于每个奇偶校验节点。R-RAM2274中的每个存储器地址存储与奇偶校验节点之一相关的|R_c|和v_min索引。因此，每个R-RAM2274地址存储个比特。

在图16的实施例中，通过逐个处理奇偶校验的相关消息(即，按照每时钟周期一个消息的方式把消息读取到处理器中)来处理奇偶校验。也可以并行处理这些消息以便增加解码器的吞吐量。还可以逐个处理变量节点并在每个时钟重构相应的R_cv消息，由此实现变量节点串行调度器来替代校验节点串行调度器。然而，在这种情况下使用校验节点串行调度器是更加高效的，因为为了重构d_c消息仅读取R-RAM2274一次，而在变量节点串行调度器的情况下，由于在变量节点串行调度器中每个R_cv与不同校验节点相关并因此具有不同组的R_c、和V_min值，所以对于每个重构的R_cv消息，需要独立地读取R-RAM2274。然而，仍然可以如图16中所示使用存储R_cv消息的压缩形式。

图17是闪存装置的高级示意性框图。包括按矩阵排列的多个存储器单元的存储器单元阵列1由列控制电路2、行控制电路3、c-source控制电路4和c-p-well控制电路5控制。列控制电路2连接到存储器单元阵列1的比特线(BL)以读取存储在阵列1的存储器单元中的数据，在写操作期间确定阵列1的存储器单元的状态并控制比特线(BL)的电位以开始写或者禁止写。行控制电路3连接到字线(WL)以选择字线(WL)之一，施加读电压，结合由列控制电路2控制的比特线电位施加写电压，并结合形成阵列1的存储器单元的p型区域的电压施加擦除电压。c-source控制电路4控制连接到阵列1的存储器单元的公共源线。c-p-well控制电路5控制c-p-well电压。

存储在阵列1的存储器单元中的数据由列控制电路2读出并经I/O数据线和数据输入/输出缓冲器6输出到外部I/O线。将要存储在存储器单元中的程序数据经外部I/O线输入到数据输入/输出缓冲器6，并被传送到列控制电路2。外部I/O线连接到控制器20。

用于控制闪存装置的命令数据输入到命令接口，所述命令接口连接到与控制器20连接的外部控制线。命令数据通知闪存请求哪些操作。输入命令传送到状态机8，所述状态机8控制列控制电路2、行控制电路3、c-source控制电路4、c-p-well控制电路5和数据输入/输出缓冲器6。状态机8能够输出闪存的状态数据，诸如就绪(READY)/繁忙(BUSY)或完成(PASS)/失败(FAIL)。

控制器20连接到主机系统(诸如，个人计算机、数字照相机、个人数字助手)或者能够与主机系统连接。该主机发出命令，诸如分别把数据存储到存储器阵列1或从存储器阵列1读取数据以及提供或接收这种数据。控制器20把这种命令转换成能够由命令电路7解释并执行的命令信号。控制器20也通常包含用于把用户数据写到存储器阵列或从存储器阵列读取用户数据的缓冲存储器。典型存储器装置包括：一个集成电路芯片21，包含控制器20；一个或多个集成电路芯片22，每个集成电路芯片22包含存储器阵列和相关的控制、输入/输出和状态机电路。当然，趋势是把这种装置的存储器阵列和控制器电路一起集成在一个或多个集成电路芯片上。存储器装置可以作为主机系统的一部分嵌入，或者可以被包括在可移动地可插入在主机系统的配合槽中的存储卡中。这种卡可包括整个存储器装置，或者控制器和存储器阵列以及相关的外围电路可以在不同的卡中提供。

图18是图17的一部分的放大图，示出了所述控制器20包括：编码器52，用于把从主机接收的用户数据编码为一个或多个码字；电路54，用于指示图17的命令电路7把码字(或者如果码字的任何比特是收缩比特则仅把其非收缩比特)存储在图17的存储器单元阵列1中，并指示图17的命令电路7从图23的存储器单元阵列1检索存储的码字(或者在收缩比特情况下其存储的部分)；和减小存储器的解码器270，用于对由电路54检索的码字的表现进行解码。可替换地，控制器20能够包括减小存储器的解码器230来替代减小存储器的解码器270，。

虽然本文公开的方法和解码器主要用于数据存储系统，但这些方法和解码器也适用于通信系统，特别地，适用于依赖通过强烈衰减某些频率的介质的波传播的通信系统。这种通信固有地缓慢并且存在噪声。这种通信的一个例子是海岸站和水下潜艇之间的极低频无线电波通信。

图19是通信系统100的高级示意性框图，通信系统100包括发射器110、信道103和接收器112。发射器110包括编码器101和调制器102。接收器112包括解调制器104和减小存储器的解码器270。编码器101接收消息并产生相应码字。调制器102对产生的码字进行数字调制(诸如，BPSK、QPSK、多值QAM或OFDM)，并经信道103把获得的调制信号发送给接收器112。在接收器112，解调制器104从信道103接收调制信号并对接收的调制信号进行数字解调制(诸如，BPSK、QPSK或多值QAM)。解码器270如上所述对获得的原始码字的表现进行解码。可替换地，接收器112能够包括解码器230来替代解码器270，。

已描述了用于存储闪存的控制元数据的方法以及使用该方法的装置和系统的有限数量的实施例。应该理解，可以进行这些方法、装置和系统的许多变化、修改和其它应用。