非二进制低密度奇偶校验(LDPC)码的符号翻转解码器

摘要

本发明的各实施方式总体上涉及非二进制低密度奇偶校验(LDPC)码的符号翻转解码器。具体地，提供了用于解码数据的系统和方法。解码器获取与符号有关的数据并且标识符号的多个候选值。解码器确定多个候选值的每个候选值与关联于符号的参考值之间的距离以获得多个距离，以及解码器至少部分基于多个距离确定是否更新符号的值。

说明书

相关申请的交叉引用

本申请依据35U.S.C.§119(e)要求于2012年8月28日递交的、申请号为61/694,163的美国临时申请的优先权，其以引用的方式整体并入本文中。

背景技术

本文中提供的背景技术的描述目的在于总体上给出本公开内容的上下文。本文的发明人的工作、在该背景技术章节中所描述的工作的程度以及否则不可能有资格作为递交时的现有技术的说明书的各方面，既非清楚地也非隐含地被认定为针对本公开内容的现有技术。

本公开内容总体上涉及数据解码，并且更具体地涉及用于以低密度奇偶校验(LDPC)编码器编码的数据的解码器。

LDPC码和用于解码LDPC码的解码器可以用在许多应用和设备中。例如，数据存储、卫星通信、无线通信、有线通信以及电力线通信是可以各自使用LDPC码和LDPC解码器的应用。诸如数码相机闪存存储器、卫星、移动电话以及其它移动设备的设备也可以各自使用LDPC码和LDPC解码器。

LDPC码可以用于纠正传输在噪声通信或数据存储信道中的信息中的误差。该信息可以在传输之前编码(通过LDPC编码器)并且随后在接收到的时候解码(通过LDPC解码器)。常规的硬解码LDPC技术是典型的双态系统，其中传送的码中的比特被分配到两个二进制状态中的一个。改进的解码结果可以使用诸如概率分布的软信息来获得。然而，存储和处理软信息可能是处理器和存储资源上的非常大的开销。

先前的LDPC技术典型地基于给定数量的校验是否不满足来确定是否翻转比特。例如，基于哪些比特的组合最可能减少不满足的校验节点的数量，可以选择一个或多个比特的值来翻转。

发明内容

根据本公开内容的实现方式，提供了用于解码数据的系统和方法。解码器获取与符号有关的数据并且标识所述符号的多个候选值。所述解码器确定所述多个候选值的每个候选值与关联于所述符号的参考值之间的距离以获得多个距离，并且至少部分基于所述多个距离确定是否更新所述符号的值。

所述多个距离形成距离分布，其中所述距离分布包括关联于所述多个距离中的至少一个距离的校验节点的数量。所述确定是否更新所述符号的值进一步至少部分基于阈值和关联于所述多个距离中的第一距离的校验节点的数量之间的比较。可以在所述解码的进一步迭代处修改所述阈值。

在一些实现方式中，确定是否更新所述符号的所述值包括：标识多个阈值，其中所述多个阈值中的每个阈值对应于所述多个距离中的距离，并且其中所述阈值随着所述对应的距离被修改而被修改。所述确定是否更新所述符号的所述值进一步包括比较所述多个阈值中的每个阈值与所述多个距离中的所述对应的距离。当关联于所述多个距离中的距离的校验节点的数量超出阈值时，更新所述符号的所述值。

关联于所述符号的第一数量的满足的校验节点对应于所述多个距离中的第一距离，并且关联于所述符号的第二数量的不满足的校验节点对应于所述多个距离中的第二距离。在一些实现方式中，如果基于所述参考值和所述第二距离，所述符号被更新到第二值，则所述第二数量的不满足的校验节点中的每个校验节点被改变为满足的校验节点。

在一些实现方式中，所述参考值是所述符号的初始值或所述符号的当前值。所述符号是非二进制符号，以使得在所述符号的所述多个候选值中有至少三个候选值。

附图说明

通过结合附图考虑以下详细的描述，本公开内容的以上和其它特征，包括其本质和其多种优势，将会更显而易见，其中：

图1是根据本公开内容的实施方式，采用LDPC解码的说明性的通信系统的框图；

图2A和图2B是根据本公开内容的实施方式，表示接收到的码字的符号的变量节点和用于解码接收到的码字的校验节点之间的通信的图示；

图3是根据本公开内容的实施方式，用于解码数据的过程的流程图；

图4是根据本公开内容的实施方式，用于执行解码算法的迭代的过程的流程图；

图5是根据本公开内容的实施方式，用于确定距离分布的过程的流程图；

图6是根据本公开内容的实施方式，用于改变执行解码算法的迭代中的更新规则的过程的流程图；以及

图7是根据本公开内容的实施方式，用于执行本文中所描述的任何过程的计算设备的框图。

具体实施方式

本公开内容总体上涉及在解码器执行解码。为提供本公开内容的全面理解，现在将描述某些说明性的实施方式，包括通过在多次迭代中更新符号值来解码码字的解码器。然而，本领域普通技术人员将要理解的是，本文中描述的系统和方法可以适应和修改为适于正在讨论的应用，并且本文中描述的系统和方法可以在其它合适的应用中采用，并且这样的其它附加和修改不会偏离其范围。

图1示出了根据本公开内容的一些实施方式，用于部分地基于符号翻转的LDPC解码的说明性的通信系统100。通信系统100用于从传输用户或应用程序102传输信息到接收用户或应用程序130。传输用户或应用程序102表示产生信息的对象或实体。例如，传输用户或应用程序102可以对应于计算机系统中的软件程序或对应于无线电系统中的无线通信传输器的组件。传输用户或应用程序102以数据流的形式产生信息，并且数据流可以通过已经由，例如源编码器(在图1中未示出)预编码的符号值序列来表示。由传输用户或应用程序102产生的信息可以对应于语音信息、视频信息、财务信息或可以以数字或模拟形式表示的任何其它类型的信息，并且由传输用户或应用程序102产生的数据流可以为数字数据流。

传输用户或应用程序102可以分段或者在其它方面划分数据流为k个符号的固定长度的块。特别地，报文104，也称为m，表示这些块中的一个。特别地，报文104是k个符号的长度，其中每个符号可以为二进制数据或非二进制数据，诸如三进制数据、四进制数据、任何其它适合类型的数据或者及其任何适当的组合。编码器106用于编码报文104，以产生码字110。在本公开内容的一个实施方式中，编码器106是LDPC编码器。然而，基于本文中提供的公开内容和教导，应该清楚的是，编码器106可以为任何其它适当的编码器。码字110，也称为c，具有n个符号的长度，其中n＞k。编码器106使用生成器矩阵G108，为了方便标写也称为G，以产生码字110。例如，编码器106可以执行一个或多个矩阵操作来将报文104转换成码字110。在实施方式中，编码器106通过以下矩阵乘法使用生成器矩阵G108来从报文104产生码字110：

c＝Gm。

码字110可以由调制器112调制或在其它方面变换为适于在信道114上传输和/或存储的波形。例如，波形可以对应于模拟二进制相移键控(BPSK)信号、模拟相移键控(PSK)信号、模拟频移键控(FSK)信号、模拟正交振幅调制(QAM)信号或任何其它适当的模拟或数字信号。

信道114指代传输的波形在解调器116处被恢复之前通过其或在其上存储的物理介质。例如，信道114可以是表示计算机系统环境中的存储介质的存储信道或表示无线通信环境中的无线传播环境的通信信道。信道114的多种特性可以损坏在其上传输或存储的数据。例如，信道114可以是非理想的无记忆信道或有记忆信道。信道114的输出由解调器116来解调或处理，以产生接收到的码字118。解调器116可以使用频率滤波器、周期函数的乘法和积分以及/或者任何其它适当的解调技术来解调和/或处理信道114的输出。

在一些实施方式中，信道114是二进制对称信道模型。在二进制对称信道中，假设比特是独立的，每符号较小数量的误差比每符号较大数量的误差更可能发生。例如，如果已发送的符号是三比特长，并且如果即将发生误差，则三比特符号中的单个比特(并且三比特符号中的其它两个比特被正确地接收)将会比三比特符号中的两个比特更有可能具有误差。最不可能发生的误差是当接收到的三比特符号中的所有三个比特都具有误差时。在示例中，如果已发送的符号是000，最可能接收到的具有误差的符号是001、010或100，因为在这些接收到的符号的每个符号中，仅一个比特具有误差。对于接收到的符号不太可能是110、011或101，因为这些接收到的符号的每个符号要求两个比特具有误差。对于接收到的符号最不可能是111，因为该接收到的符号要求所有三个符号具有误差。初始发送的符号和接收到的符号之间的差异可以称为距离。例如，距离可以对应于符号的以误差接收的比特数。

在一些实施方式中，信道114是多进制(Q-ary)对称信道。在多进制对称信道中，所有非正确接收的符号同等可能地发生。在示例中，发送为“000”而接收为001、010、100、110、011、101或111的三比特符号的概率相同。换句话说，只要误差的数量大于0，则具有不同数量的误差比特的接收到的符号均同等可能地发生。这意味着，只要距离大于0，则具有初始传输的符号和接收到的符号之间的不同二进制距离的接收到的符号均同等可能。

在一些实施方式中，信道114是正交-脉冲振幅调制(Q-PAM)信道。在Q-PAM信道中，发生在信道上的误差的概率取决于已传输的符号和接收到的符号之间的相近度。特别地，邻近初始符号(即，已传输的符号)的符号比更远离初始符号的符号来说更可能被接收到。在示例中，可能的符号值是从0到7的整数，并且符号3被传输。在这种情况下，接收到的符号最可能是3，在其之后更可能的符号是2或4，而不是任何其它符号(即，0、1、5、6或7)。

接收到的码字118包含与码字110有关的信息，并且可以是由编码器106初始输出的码字110的被损坏或在其它方面被更改的版本。例如，接收到的码字118可以包含码字110的初步估计或噪声版本、由编码器106产生的码字的可能的值的概率分布向量或者上述这些的组合以及其它值。

检测器120用于处理接收到的码字118，以产生检测器采样122，其是初始数据报文104的估计。检测器120采样接收到的码字118中的每个符号，并且基于其值分配每个符号到二进制。在一些实施方式中，该二进制是基于概率分布来分配的。由检测器120采样的每个符号分配到两个或更多个可能的二进制或状态中的一个。

解码器124接收并且迭代地处理检测器采样122。检测器120和解码器124可以是两个分离的处理器，或者单个处理器可以用作检测器120和解码器124两者。总体而言，解码器124包括控制电路和/或解码电路，解码电路用于迭代地纠正和/或检测例如由于通过信道114传输而出现在检测器采样122中的误差。在一些实施方式中，解码器124使用奇偶校验矩阵H126和解码技术来产生解码报文128。总体而言，LDPC解码可以使用数学向量模型来描述，其中c是长度为n的二进制串，且H是奇偶校验矩阵H126，其是低密度的、稀疏的n×m矩阵，其中，如上所述，n是码字中符号的数量，m是满足m≥n-k的校验节点的数量，并且k是报文中符号的数量。只在二进制串c是码字c110时才满足该模型。奇偶校验矩阵H126不必是唯一的，并且可以选择为是计算上方便的和/或减少由解码器124的解码技术生成的误差的数量。

解码器124所使用的迭代解码技术涉及通过基于符号的校验满足或不满足以及基于符号先前是否已经被更新、翻转或切换(toggled)来更新检测器采样122中的符号，以处理检测器采样122。总体而言，如本文中所使用的，“翻转”或“切换”符号意味着更新符号的值到与当前值不同的值。用于翻转数据比特的示例性处理规则在名称为“METHODOLOGY FOR IMPROVED BIT-FLIPPING DECODER IN1-READ AND2-READ SCENARIOS”、申请号为13/673,371的美国专利申请中进行了讨论，其据此以引用的方式整体并入本文中。

在处理之后，解码报文128中的符号的每个比特应该分配为两个二进制状态中的一个。当作为c输入到模型中时，解码报文128满足该模型。用于执行解码的适当过程关于图3-图6进行了描述。

在由解码器124进行处理之后，传送解码报文128到接收用户或应用程序130。接收用户或应用程序130可以对应于与传输用户或应用程序102相同的设备或实体，或者接收用户或应用程序130可以对应于不同的设备或实体。进一步地，接收用户或应用程序130可以或者与传输用户或应用程序102位于同一位置(co-located)或者与传输用户或应用程序102物理分离。如果解码器124纠正由信道114和通信系统100中的其它通信影响所引入的所有误差，则解码报文128是报文104的逻辑复制。否则，解码报文128可以区别于报文104，并且解码器124可以据此声明误差。

图2A和图2B是根据本公开内容的实施方式，表示示例码字的变量节点220-234和用于解码码字的校验节点200-210之间的通信的图示。

在使用如上所述的检测器120分配给变量节点220-234输入状态或值之后，由解码器124在多个变量节点组上执行变量节点的校验。解码器124使用处理规则来确定变量节点组的状态。确定的状态的指示存储在诸如校验节点200-210的校验节点处的校验子(syndrome)存储器中。奇偶校验矩阵H126(图1)标识哪些校验节点存储用于哪些变量节点的确定的状态的指示。例如，对于图2A和图2B中描绘的节点，奇偶校验矩阵H126可以如下：

$>H=\left(\begin{array}{cccccccc}2& 1& 1& 0& 3& 0& 0& 2\\ 0& 0& 0& 1& 0& 2& 1& 0\\ 1& 0& 0& 2& 1& 0& 0& 0\\ 0& 2& 3& 0& 0& 2& 0& 1\\ 0& 0& 0& 3& 2& 0& 0& 2\\ 3& 0& 1& 0& 0& 1& 2& 0\end{array}\right)$>

每行对应于校验节点中的一个，并且每列对应于变量节点中的一个。在二进制码中，奇偶校验矩阵的元素是0或1，但对于非二进制的LDPC码，奇偶校验矩阵的元素是非二进制的。奇偶校验矩阵的每行形成奇偶校验方程的系数，奇偶校验方程在非二进制域中进行计算。

解码器124参考奇偶校验矩阵H126来标识哪些变量节点应该由特定校验节点来校验。例如，对于校验节点206，解码器124确定该校验节点206存储变量节点222、224、230和234(即，第二、第三、第六和第八变量节点)的校验结果。之后，解码器124获取存储在这些变量节点中的值。上述奇偶校验矩阵H的第四行中的值是奇偶校验方程的系数，其各自与变量节点的对应的值相乘。出于说明的目的，图2A中的箭头指示已获取的值从变量节点222、224、230和234流向校验节点206，并且校验节点206可以被认为“校验”变量节点222、224、230和234。在实际中，变量节点的值由解码器124获取，其根据处理规则代表校验节点206来处理这些值。

根据接收自变量节点222、224、230和234的值，解码器124确定满足或不满足校验节点206的给定状态。满足或不满足校验节点206的指示(即，校验节点的“校验子值”)存储在校验子存储器中，其存储校验节点的校验子值或指示。

在校验节点200-210的指示或校验子值已经存储在校验子存储器中之后，变量节点220-234的值可以基于校验节点的值来更新。解码器124再次使用奇偶校验矩阵H126来确定哪些校验节点对于特定变量节点应该被访问。如图2B中所示，为了更新变量节点224，上述给定的奇偶校验矩阵H126指示应该参考校验节点200、206和210(即第一、第四和第六变量节点)。基于参考的校验节点的指示，可以更新变量节点224的状态。在本公开内容的一些实施方式中，变量节点224的状态还可以部分地基于变量节点224先前是否已经被更新、切换或翻转来确定，如有关图3-图6所描述的。

图3是根据本公开内容的实施方式，用于解码数据的过程300的高层流程图。解码器124可以通过获取与符号有关的数据(302)以及标识符号的多个候选值(304)来执行过程300。过程300进一步包括确定多个候选值的每个候选值与关联于符号的参考值之间的距离以获得多个距离(306)；以及至少部分基于多个距离确定是否更新符号的值(308)。

在302处，解码器124获取与符号有关的数据。在302处获取到的数据可以对应于符号本身的值、在解码方法先前的迭代中使用的该符号的先前值、与符号有关的其它状态变量或者及其任何适当的组合。在302处获取到的数据还可以包括与连接到符号的多个校验节点有关的数据。如结合图1所描述的，数据可以进一步包括满足或不满足校验节点的指示。例如，在302处获取到的数据可以包括奇偶校验矩阵126，并且对于给定的变量节点(如图2A和图2B中所示)，解码器124可以使用奇偶校验矩阵H126来确定哪些校验节点关联于给定的符号。根据奇偶校验矩阵H和符号的值，解码器124获取关联于每个校验节点的值，并且可以标识满足的校验节点的数量以及不满足的校验节点的数量。关联于每个校验节点的校验子值可以用于确定满足或不满足校验节点。例如，校验子值可以对应于(奇偶校验矩阵H的行和变量节点集合的符号值的)乘积的总和。如果校验子值等于零，则满足校验节点。否则，如果校验子值不为零，则不满足校验节点。

在304处，解码器124标识符号的多个候选值。候选值对应于这样的值，解码器124能够在当前迭代中更新符号到该值，并且候选值可以对应于码字中变量节点集合可以具有的值的所有可能的组合。在一些实施方式中，候选值集合仅包括值的可能的组合的子集。

在306处，解码器124确定多个候选值的每个候选值与关联于符号的参考值之间的距离以获得多个距离。候选值和参考值之间的距离是两个值之间的相近度的测度。

根据解码的规则，参考值可以具有不同的值。特别地，在本公开内容的一些实施方式中，参考值固定为符号的初始值，其对应于由检测器120检测到的码字118的接收到的部分。在其它实施方式中，参考值对应于符号的当前值，其对应于在已经执行解码算法的各种迭代后的符号的值。在其它实施方式中，参考值是符号的中间值，其对应于在已经执行解码算法的一次或多次迭代后的符号的值，但不必要是符号的当前值。总体而言，参考值可以为初始值、中间值、当前值或符号的任何其它适当的值。

无论符号的参考值是如何定义的，距离对应于候选值和参考值之间的距离。在示例中，参考值和候选值各自由4个比特表示。在这种情况下，距离对应于(全部4个比特之中的)参考值和候选值之间不同的比特的数量。这通常称为汉明(Hamming)距离，其可以在信道114是二进制信道时使用。在另外的示例中，信道114可以为多进制对称信道，其中一个符号(例如，000)和所有其它可能符号之间的距离是相同的。在另外的示例中，信道114可以为Q-PAM信道，其中一个符号值和另一符号值之间的距离被定义为值之间的差。总体而言，如在306处所确定的距离可以是符号的两个值之间的相近度的任何测度。

基于在306处形成的多个距离可以形成距离分布。距离分布结合图4和图5更详细地进行了描述，但总体而言，距离分布对应于校验节点的数量，如果符号值被更新到与参考值相距特定距离的候选值，则将满足该校验节点。

在308处，解码器124至少部分地基于多个距离确定是否更新符号的值。如结合图4和图5所描述的，解码器124可以使用距离分布来确定是否更新符号的值。作为示例，解码器124可以比较距离分布和阈值集合，并且候选值可以基于该比较来选择。例如，如果将被满足的校验节点的数量超出对应的阈值，则解码器124可以更新符号的值到对应的候选值。阈值集合可以对于不同的候选值(即，分布中的不同距离)而不同，并且该比较可以基于校验节点的数量、校验节点的百分比、校验节点的总数或者及其适当的组合。结合图4-图6更详细地描述了高层方法300。

图4是根据本公开内容的实施方式，用于执行解码算法的迭代的过程400的流程图。通过读取接收到的数据的值(402)、初始化状态存储器(404)、在硬判决存储器中存储接收到的值(408)、计算校验子并且在校验子存储器中存储它们(410)以及初始化符号计数器变量k到1(406)，解码器124可以执行过程400。过程400进一步包括标识符号k的候选值集合(412)、确定距离分布(414)以及确定是否更新符号k的当前值(416)。如果确定更新，则更新符号k(418)，可选地更新状态存储器(420)，并且解码器124确定k是否等于当前码字的长度。如果确定不更新，则增加k的值(422)，并且过程400返回到412来标识新的符号k的候选值。当已经考虑了码字中的所有符号时，解码器124确定解码是否已经收敛(426)。如果达到收敛，则解码器124成功解码数据(432)。否则，符号计数器变量k重新初始化为1(428)，可选地改变更新规则(430)，并且过程400返回到412来标识符号k的候选值。

在402处，检测器120读取接收到的码字118的值，以生成检测器采样122。在404处，解码器初始化状态存储器，其存储指示或能够用于确定变量节点先前是否已经被更新的数据。在408处，解码器通过在硬判决(HD)存储器中存储变量节点中的检测器采样122的初始值或信号来初始化HD存储器。在410处，如结合图2A中所描述的，解码器124基于存储在HD存储器中的数据计算校验子，并且，解码器124在校验子存储器中存储校验节点中的计算的校验子。在406处，解码器124初始化变量节点或符号计数器k＝1；在解码过程中，解码器124贯穿检测器采样122中的变量节点的每个变量节点进行迭代，其中每个变量节点对应于正在解码的码字的符号。如结合图2B所描述的，解码器读取存储在码字的符号k的校验节点中的校验子。如结合图3所描述的，解码器124可以处理校验子以标识满足的校验的数量、不满足的校验的数量或者两者。

在412处，解码器124标识符号k的候选值。候选值集合对应于如下值的集合，解码器124可以在当前迭代中更新符号k的值到该值。候选值集合可以称为星座图。特别地，如结合图2B所描述的，解码器124读取存储在码字的符号k的校验节点中的校验子。如结合图3的304所描述的，解码器124可以处理校验子以标识满足的校验的数量、不满足的校验的数量或者两者。候选值对应于如下值的集合，编码器124可以在当前迭代中更新符号k的值到该值。解码器124是否确定更新符号k取决于候选值集合以及关联于每个候选值的校验的数量。在示例中，一个候选值为符号的当前值。在另外的示例中，一个候选值为如检测器120所检测的符号的初始值。其它的候选值对应于符号的其它值，该符号可以被更新到该值，并且一些候选值可以对应于符号的先前值(在解码的先前迭代中所考虑的)，而一些候选值可以对应于符号的新的值(在解码的先前迭代中并未考虑的)。

在414处，解码器124确定关联于符号k的距离分布。解码器124可以执行图5中所示的过程500来确定距离分布。距离分布对应于关联于在412处被标识的每个候选值的校验节点的数量(或百分比)，作为符号的参考值和候选值之间的距离的函数。例如，每个候选值具有对应的距离值，其指示候选值和参考值之间的距离。参考值可以为在接收到时的初始符号、在可能已经更新符号值的若干先前迭代之后的符号的当前值或者中间值。距离分布中校验节点的数量对应于如果符号k的值被更新到对应的候选值则将被满足的校验节点的数量。

在示例中，如果符号节点k连接到七个校验节点，并且如果有四个候选值，则距离分布可以对应于N＝[N₀ N₁ N₂ N₃]＝[2 4 0 1]，其中距离从左到右增加。距离分布中的第一值N₀对应于被满足的校验节点的数量(七个中的两个)，指示零距离，或d₀＝0。指示零距离的校验节点意味着对于符号的参考值，这些校验节点被满足，因为当距离为零时，参考值与候选值相同。当参考值是符号的初始值时，这意味着七个校验节点中的两个校验节点初始地满足于在接收到时的初始值，并且如果符号被更新回到其初始值，则该两个校验节点将被满足。当参考值是符号的当前值时，这意味着七个校验节点中的两个校验节点当前满足于符号的当前值。

在示例分布[2 4 0 1]中，七个校验节点中的五个校验节点为不满足。特别地，如果符号被更新到具有距参考值的距离d₁的候选值，则五个不满足的校验节点中的四个校验节点将被满足；如果符号被更新到具有距参考值的距离d₂的候选值，则不满足的校验节点中的零个校验节点将被满足；并且如果符号被更新到具有距参考值的距离d₃的候选值，则不满足的校验节点中的一个校验节点将被满足。

在两比特二进制的示例中，候选值为00、01、10和11。距离可以以不同比特的数量或汉明距离来测量，汉明距离可以用在如结合图1所描述的二进制信道的情况中。在这种情况下，d₀＝0、d₁＝1、d₂＝1以及d₃＝2。因此，有两个候选值具有相同的距离是可能的，但候选值中的每个候选值在距离分布中仍分配到其自身的值。换句话说，即使在示例中d₁等于d₂，但是对于d₁来说将被满足的校验节点不一定对应于对于d₂来说将被满足的相同的校验节点。因此，即使汉明距离相同，d₁和d₂在距离分布中保持为独立值。形成诸如本文中所示示例的距离分布有助于确定是否更新符号k以及确定解码器124应该更新符号k为哪些值。在一些实施方式中，距离分布不是由校验节点的数量而是由对于每个候选值将被满足的校验节点的百分比来表示。例如，除了将距离分布表示为如上述示例中的[2401]，距离分布可以由[29％57％0％14％]来表示。用于确定距离分布的过程结合图500更详细地进行描述。

在416处，解码器124确定是否更新符号k的值。特别地，解码器124考虑了在414处形成的距离分布，并且比较值N_i和阈值集合。总体而言，理想情况是更困难或更小可能的是，将符号k更新到那样的值，该值非常远离当前值或初始接收到的值。因此，解码器124将不会更新符号值到与参考值具有较大距离的候选值，除非大量的校验节点将满足于该候选值。例如，对于[2 4 0 1]的距离分布来说，解码器124可能不更新符号到第四候选值(对应于第四和最大距离)，但[0 0 0 7]的距离分布可以保证更新到第四候选值。此外，即使当前满足的校验节点N₀的数量不大，解码器124也更可能让符号值维持不变或者允许符号值返回到初始值。例如，对于[2 4 0 1]的距离分布，解码器124可以选择允许符号值维持不变或返回到初始值，即使N₀＝2不是分布中的最大值(N₁＝4是最大值)。

为确定是否更新符号k的值，解码器124比较距离分布中的值N_i和阈值集合。如果值N_i超出对应的阈值，则符号可以被更新到对应的候选值。为了确保更新到远离参考值的候选值难于更新到较接近参考值的候选值，阈值对于不同的距离可以具有不同的值。例如，阈值可以随着距离的增加而增加，以使得当非常大量的校验节点将满足于较远值时，解码器124将仅更新符号值到远离参考值的值。阈值可以表示为T_ij，其中T_ij随着i(以及距离)的增加而增加，或同等地，T_0j＜T_1j＜T_2j＜...＜T_Ij。在该方式中，做出到具有距离D的候选值的更新比到具有大于D的距离的候选值的更新来说更有可能。在一些实施方式中，T_ij随着j(迭代数量)的增加而改变。该过程结合图500更详细地进行描述。

如果解码器124确定在当前迭代中不更新符号k，则过程400行进到422，以增加符号计数器k的值并且返回到412来标识下一符号k的候选值。

否则，如果解码器124确定在当前迭代中更新符号k，则解码器124在418处更新符号k。在一些实施方式中，解码器124选择最可能的候选值。最可能的候选值可以对应于对于N_i来说具有最大值的候选值，或者具有最大数量的校验节点，该校验节点在符号被更新到该候选值的情况下将被满足。然而，就至少两个理由来说，该选择最可能的候选值的方法可能不理想。

第一，除非校验节点确切地指示这样的更新应该发生，否则更新符号到候选值可能是不理想的。例如，对于具有参考值(例如，初始值、当前值或者中间值)00的两比特符号，距离分布包括N_i的四个值，其中N₀对应于00，N₁对应于01，N₂对应于10，并且N₃对应于11。在示例中，距离分布可以包括N_i的值：[0 2 1 1]。对于四个不满足的校验节点和零个满足的校验节点，可能较理想的是维持符号不变，而不是简单地选择第二候选值以使得两个校验节点被满足。特别地，在[0 2 1 1]的示例中，四个不满足的校验节点不确切地指向特定候选值。取而代之的是，四个不满足的校验节点跨三个候选值进行分布。

第二，做出到将要求较大距离的符号的更新应该比要求较短距离的符号更新来说更不频繁。例如，[0 2 0 3]的距离分布可以指示出到第四候选值(具有最大距离)的更新将满足三个当前不满足的校验节点。然而，除非校验节点提供应该做出这样的更新的确切指示，否则更新符号到第四候选值可能是不理想的。确切指示的示例是[0 0 0 5]的距离分布。

在本公开内容的一些实施方式中，解码器124更新符号k所到的值是基于上述距离分布中的值和阈值之间的比较来选择的值。在示例中，选择的候选值可以是距离分布中超出对应的阈值的第一值N_i。特别地，每个值N_i可以与若干迭代中的每次迭代中相应的阈值进行比较，其中迭代的数量对应于距离分布中的值的数量。选择的值可以是在迭代中考虑的超出对应的阈值的第一值。在另外的示例中，多个候选值可以具有距离分布中超出它们对应的阈值的对应的值N_i。在这种情况下，解码器124可以选择具有N_i的较大值的候选值，或者解码器124可以选择具有较小距离的候选值。用于如何解决如这样的情况(即，当距离分布中的多个值N_i超出它们对应的阈值时)的规则可以在430处选择。

在一些实施方式中，如果参考值是初始值，如果不满足的校验的数量超出阈值以及如果满足解码器的历史上的一些准则，那么解码器124可以确定更新符号的值到初始值。作为示例，如果当前符号值不同于初始接收到的符号值，则符号可以被更新回到初始值。特别地，容易地允许符号返回到初始值(例如，通过使用小的阈值)可能是理想的。例如，在[2 3 0 0]的距离分布的情况下，解码器124可以选择与参考符号的距离为零的候选值。在这种情况下，即使选择的候选值不是最可能的符号，解码器124也确定将符号的值返回到其初始值。在示例中，如果指示其将满足于初始值的校验节点的数量在某个百分比范围(＞p％)内，则选择符号的初始值。换句话说，当参考值是初始值时，这意味着标识距离分布中的第一入口何时大于连接到当前变量节点的校验节点的总数量的p％。

在418处，解码器124还更新校验子存储器，以反映已更新的符号或变量节点的值。特别地，重新计算连接到符号k的变量节点的每个校验节点的校验子，并且更新这些校验节点的值。在一些实施方式中，例如，如果状态存储器存储符号是否已经被更新的指示，则在420处更新符号k的状态存储器。

在424处，解码器124确定k是否等于码字长度，即，是否已经在检测器采样122中的每个变量节点上执行了412至422的过程并且已经到达检测器采样122的末端。如果还未到达检测器采样122的末端，则在422处增加k，并且在检测器采样中的随后的变量节点(即，随后的符号k)上执行412至422的过程。

在426处，一旦已经到达检测器采样122的末端，则这表示解码过程的迭代的结束。此时，解码器124确定解码过程是否已经收敛。在一些实施方式中，这意味着满足了所有校验节点的条件。在其它实施方式中，其中可以给出外纠错码，放宽收敛的条件，并且允许最小量的误差(例如，最小量的被擦除的变量节点或最小量的不满足的校验节点)。如果解码器124已经收敛，则在432处，确定解码器124成功了。之后解码器124输出解码报文128到接收用户或应用程序130。如果解码器124不收敛，则在428处，k被重置为1，并且在一些实施方式中，在430处，改变用于随后贯穿检测器采样122的迭代的更新规则。各种更新规则以及更新规则的改变结合图6进一步进行描述。

在一些实施方式中，如果解码器124没有收敛，则在428处重置k以及再次贯穿检测器采样122进行迭代之前，解码器124确定迭代数量j是否小于最大迭代数量j_max。如果迭代数量j小于最大迭代数量j_max，则过程继续到428，并且再次处理变量节点。如果迭代数量等于最大迭代数量j_max，则方法终止。在终止之后，解码器124可以输出解码的结果到接收用户或应用程序130。附加地或备选地，解码器124或者接收用户或应用程序130可以请求传输用户或应用程序102重传码字110。是否接受报文或请求重发报文可以基于解码器124确定解码报文128不正确的程度。

图5是根据本公开内容的实施方式，用于确定距离分布的过程500的流程图。解码器124可以将过程500作为确定距离分布(过程400的414)的一部分来执行。过程500包括标识符号的当前值(502)，标识关联于符号的当前值的校验节点(504)，以及确定满足的校验节点的数量(506)。候选迭代参数i初始化为1(508)，计算参考符号值和第i个候选值之间的距离D_i(510)，以及解码器124确定如果符号被更新到第i个候选值则将被满足的校验节点的数量N_i(512)。如果数量N_i超出阈值(514)，则符号被更新到第i个候选值(522)。否则，如果候选迭代参数i不等于候选值I的数量(516)，则增加候选迭代参数i(518)，并且过程500返回到510来计算距离D_i。否则，如果已经考虑了所有候选值，并且其校验节点的相应数量N_i没有一个超过阈值，则不更新符号值(520)。

在502处，解码器124标识符号的当前值。如果符号刚刚获取到，则符号的当前值可以对应于符号在接收到时的初始值。否则，符号的当前值可以对应于在解码的先前迭代中使用的更新后的值。

在504处，解码器124标识关联于符号的当前值的校验节点。如结合图2B所描述的，解码器124读取存储在码字的符号k的校验节点中的校验子。

在506处，解码器124确定满足的校验节点的数量。满足的校验节点的数量是连接到满足于当前值的当前符号的变量节点的校验节点的数量。特别地，满足的校验节点是这样的校验节点，对于该校验节点，在奇偶校验矩阵内对应的行和连接的变量节点的当前符号值之间的乘积的总和为零。如果该乘积的总和不为零，则这意味着校验节点是不满足的。因此，满足的校验节点的数量可以通过将奇偶矩阵H126乘以具有对应于变量节点的当前符号值集合的元素的向量并且标识具有等于零的对应的乘积元素的校验节点来确定。

在508处，候选迭代参数i被初始化为1。迭代参数i是这样的值，该值指示哪个候选值当前正在考虑中。因此，迭代参数i开始于1并且可以增加直至考虑了每个候选值。

在510处，解码器124计算参考符号值和第i个候选值之间的距离D_i。如上所述，参考符号值可以为符号的初始值、符号的当前值、符号的先前值或者任何其它适当的值。在一些实施方式中，距离D_i对应于参考符号值和候选值之间的汉明距离。如结合图1所描述的，如果信道114是二进制信道，则对于距离D_i来说使用汉明距离可以是有用的。

总体而言，距离D_i是两个符号之间的相对邻近和/或似然性的度量。在一些实施方式中，如结合图1所描述的，信道114是多进制对称信道。在这种情况下，所有可能的更新后的值(即，候选值)是同等可能的，而符号的当前值可以关联于不同的似然性。例如，如果传输的符号是三比特长并且具有值000，则七个其它可能的候选值(即，001、010、011、100、101、110和111)是各自同等可能的。在这种情况下，如果参考值是000，则D₀为零，因为参考值与候选值000相同。而且，其它七个距离(D₁、D₂、D₃、D₄、D₅、D₆和D₇)是相等的，因为它们对应的候选值均同等可能地发生。

在一些实施方式中，如结合图1所描述的，信道114是Q-PAM信道。在这种情况下，邻近的符号比较远离的符号更可能。例如，如果传输的符号是3，并且如果候选值采用从0到7之间的整数值，则相较于值0、1、5、6和7来说，接收到的符号更可能为2或4。因此，参考值和候选值之间的距离可以定义为在Q-PAM信道星座图中的距离。

本文中描述的是如何计算参考符号值和候选值之间的距离的若干示例。然而，本领域普通技术人员将理解的是，总体而言，如本文中所描述的两个值之间的距离度量可以以任何方式来计算。

在512处，解码器124确定如果符号被更新到第i个候选值则将被满足的校验节点的数量N_i。在514处，解码器124比较数量N_i和阈值。阈值可以基于参考符号值和正在考虑中的当前候选值之间的距离来确定。阈值还可以基于已经在解码过程中发生的迭代的次数来确定。

作为示例，值T_ij的集合可以针对每次迭代j而进行更新。特别地，T_ij可以随候选值i的增加(并且因此随与参考值的距离增加)而增加。此外，迭代可以划分为多层次。例如，如果j_max是将在解码过程中执行的迭代的最大数量，则j_max次迭代的集合可以划分为不同的层次，诸如迭代j＝1到j_max/2的第一层次和j＝j_max/2+1到j_max的第二层次。在示例中，T_ij对于第一层次(即，较早的迭代)可以比在第二层次中(即，稍后的迭代)更小或更大。T_ij的较小值暗示要求较宽松的条件，因为为了更新符号值到第i个候选值，N_i必须超过T_ij。在给出的示例中，仅有两层次的迭代。然而，本领域普通技术人员将理解的是，在不偏离本公开内容的范围的情况下，本文中所描述的系统和方法可以用于迭代的任何数量的层次。

如果N_i超出阈值，则过程500行进到522来更新符号值到第i个候选值。否则，过程500行进到516来确定迭代参数i是否等于候选值I的总数量。如果不等于，则在518处增加迭代参数i，并且过程500返回到510来计算下一个候选值的距离。否则，如果已经考虑了所有的候选值(即，i＝I)，并且如果没有一个候选值具有超出对应的阈值的N_i的值，则过程500行进到520并且不更新当前符号值。

图6是根据本公开内容的实施方式，用于改变执行解码算法的迭代中的更新规则的过程600的流程图。解码器124可以将过程600作为可选的改变更新规则(过程400的430)的一部分来执行。过程600包括选择符号的参考值(602)，选择是否在距离分布中考虑校验节点的数量或校验节点的百分比(604)，以及选择不同距离的阈值集合，其中阈值因增加的距离而增加(606)。

在602处，选择符号的参考值的类型。参考值的类型可以是符号在接收到时的初始值、符号的当前值(如在先前的迭代中使用过或更新过的)或者中间值。总体而言，符号的参考值的类型可以跨解码的多次迭代而保持固定，但在一些实施方式中，参考值的类型可以针对不同的迭代而被更新。

在604处，解码器124选择是否在距离分布中考虑校验节点的数量、校验节点的百分比或者两者的组合。此外，解码器124还可以选择是否考虑不满足的校验节点的总数量。根据在604处的选择，在606处选择的阈值集合可以是不同的。

在606处，解码器124选择不同距离的阈值集合，其中阈值因增加的距离而增加。例如，如上所述，T_ij因具有增加的距离i的候选值而增加。此外，T_ij可以因迭代j的增加的层次而增加或减少。根据在604处所选择的，T_ij的单位可以是校验节点的数量或者校验节点的百分比。如果解码器124确定使用校验节点的数量和校验节点的百分比两者，则可以使用不同的T_ij的值(例如，T_number_ij和T_percentage_ij)。

在一些实施方式中，阈值T_ij的值取决于变量节点的度和不满足的校验节点的数量。变量节点的度是变量节点连接到的校验节点的总数量。在示例中，具有七度的变量节点可以根据不满足的校验节点的多少来使用不同的阈值。

总体而言，过程600可以包括更新关联于执行解码迭代的任何其它过程规则。例如，解码器124可以基于解码器124的历史或在先的状态来更新符号。例如，距离可以定义在符号的当前值和符号的先前值之间(在一些在先的解码器阶段或迭代中)。可以在不同地定义的距离上生成距离分布，并且候选值可以基于距离D_i分离到不同类别中。根据候选值是否落入特定类别中，符号值可以或不可以被更新到该候选值。阈值对于不同的类别可以是不同的。

图7是根据本公开内容的实施方式的计算设备的框图700，诸如图1的系统的任何组件，用于执行本文中所描述的任何过程。这些系统的每个组件可以实现在一个或多个计算设备700上。在某些方面，这些系统的多个组件可以包括在一个计算设备700内。在某些实施方式中，组件和存储设备711可以跨若干计算设备700来实现。

计算设备700包括至少一个通信接口单元708、输入/输出控制器710、系统存储器703以及一个或多个数据存储设备711。系统存储器703包括至少一个随机存取存储器(RAM702)和至少一个只读存储器(ROM704)。所有这些元件与中央处理单元(CPU706)进行通信以便于计算设备700的操作。计算设备700可以以许多不同的方式来配置。例如，计算设备700可以是常规的单机计算机，或者备选地，计算设备700的功能可以跨多个计算机系统和架构进行分布。在图7中，计算设备700通过网络718或局部网络链接到其它服务器或系统。

计算设备700可以配置在分布式架构中，其中数据库和处理器居于单独的单元或位置。一些单元执行主要的处理功能并且在最低限度包含通用控制器或处理器以及系统存储器703。在分布式架构的实施方式中，这些单元的每个单元可以通过通信接口单元708附接到通信集线器或端口(未示出)，该通信集线器或端口充当与其它服务器、客户端或用户计算机和其它有关设备的主要通信链路。该通信集线器或端口自身可以具有最小的处理能力，主要充当通信路由器。多种通信协议可以是系统的一部分，包括但不限于：以太网、SAP、SAS^TM、ATP、BLUETOOTH^TM、GSM和TCP/IP。

CPU706包括处理器，诸如一个或多个常规的微处理器和一个或多个补充的协同处理器，补充的协同处理器诸如用于从CPU706卸载工作量的数学协同处理器。CPU706与通信接口单元708和输入/输出控制器701进行通信，通过该通信接口单元708和输入/输出控制器701，CPU706与诸如其它服务器、用户终端或设备之类的其它设备进行通信。通信接口单元708和输入/输出控制器710可以包括多个通信信道，用于与例如其它处理器、服务器或客户终端进行同时通信。

CPU706还与数据存储设备711进行通信。数据存储设备711可以包括磁、光或半导体存储器的合适的组合，并且可以包括，例如RAM702、ROM704、闪存驱动器、诸如激光盘之类的光盘或者硬盘或驱动器。CPU706和数据存储设备711各自可以，例如，整个地位于单个计算机或其它计算设备内；或者由通信介质(诸如USB端口、串行端口电缆、同轴电缆、以太网电缆、电话线、射频收发器或其它类似的无线或有线介质或前述的组合)相互连接。例如，CPU706可以通过通信接口单元708连接到数据存储设备711。CPU706可以被配置为执行一个或多个特定处理功能。

数据存储设备711可以存储，例如，(i)计算设备700的操作系统712；(ii)一个或多个应用程序714(例如，计算机程序代码或计算机程序产品)，适应于根据本文描述的系统和方法，并且特别地根据关于CPU706详细描述的过程来引导CPU706；或者(iii)(多个)数据库716，其适应于存储可以被利用来存储程序所要求的信息的信息。

操作系统712和应用程序714例如可以以压缩的、未编译的和加密的格式来存储，并且可以包括计算机程序代码。程序的指令可以从计算机可读介质(诸如从ROM704或从RAM702)而不是数据存储设备711读入处理器的主存储器中。当程序中指令序列的执行引起CPU706来执行本文中所描述的过程步骤时，硬连线电路可以用于替代或组合用于本公开内容的过程的实施方式的软件指令。因此，所描述的系统和方法不限于硬件和软件的任何特定组合。

可以提供适当的计算机程序代码用于执行如本文中所描述的与解码码字有关的一个或多个功能。程序还可以包括程序要素，诸如操作系统712、数据库管理系统和“设备驱动器”，其允许处理器通过输入/输出控制器710与计算机外围设备(例如，视频显示器、键盘、计算机鼠标等等)接口。

如本文中所使用的术语“计算机可读介质”指代任何非瞬时介质，其提供或参与提供指令到计算设备700的处理器(或者本文中所描述的设备的任何其它处理器)来执行。这样的介质可以有许多形式，包括但不限于非易失性介质和易失性介质。非易失性介质包括，例如，光盘、磁盘或光磁盘，或者诸如闪存之类的集成电路存储器。易失性介质包括动态随机存取存储器(DRAM)，其典型地组成主存储器。计算机可读介质的常用形式包括，例如，软盘、软磁盘、硬盘、磁带、任何其它磁介质、CD-ROM、DVD、任何其它光介质、穿孔卡片、纸带(paper tape)、具有孔模式的任何其它物理介质、RAM、PROM、EPROM或EEPROM(电可擦除可编程只读存储器)、FLASH-EEPROM、任何其它存储器芯片或盒或者计算机可以从中读取的任何其它非瞬时介质。

计算机可读介质的各种形式可以涉及携带一个或多个指令的一个或多个序列到CPU706(或者本文中所描述的设备的任何其它处理器)来执行。例如，指令可以初始地负荷在远程计算机(未示出)的磁盘上。远程计算机可以加载指令到其动态存储器中并且通过以太网连接、电缆线或者甚至使用调制解调器的电话线来发送指令。本地于计算设备700(例如，服务器)的通信设备可以在相应的通信线路上接收数据并且将数据放置在处理器的系统总线上。系统总线携带数据到主存储器，处理器从中获取并且执行指令。由主存储器接收到的指令可以可选地在由处理器执行之前或之后存储在存储器中。此外，指令可以通过通信端口被接收为电信号、电磁信号或光信号，这些信号是携带各种类型的信息的无线通信或数据流的示例性形式。

虽然已经在本文中示出和描述了本公开内容的各种实施方式，但是对于本领域技术人员来说将显而易见的是，这样的实施方式仅通过示例来提供。在不偏离本公开内容的情况下，本领域技术人员现在将发现多种变化、改变和替换。应当理解的是，在实践本公开内容时，可以采用本文中所描述的本公开内容的实施方式的各种替代选择。意图在于下列权利要求限定本公开内容的范围，并且从而覆盖这些权利要求的范围内的方法和结构以及它们的等同。