使用结构化奇偶校验矩阵的低密度奇偶校验码的编码

具体实施方式

现在描述用于对结构化低密度奇偶校验(LDPC)码进行高效解码的系统，方法和软件。在下面的说明中，出于说明的目的，提出许多特定的细节以便彻底地理解本发明。然而本领域技术人员明白，即使没有这些特定细节，或者通过等价的方案，仍然可以实施本发明。在其它实例中，以模块图形式示出了众所周知的结构和设备，以避免对本发明产生不必要的干扰。

图1的图例根据本发明的实施例示出了被构造成利用低密度奇偶校验(LDPC)码的通信系统。数字通信系统100包含发送器101，其在到达接收器105的通信信道103上产生信号波形。在这个离散通信系统100中，发送器101具有产生离散的可能信息集合的信息源；每个可能信息具有相应的信号波形。这些信号波形被通信信道103衰减或改变。为了对付有噪声的信道103，使用LDPC码。

发送器101产生的LDPC码允许得到高速实现，但不导致任何性能损失。这些从发送器101输出的结构化LDPC码避免为已经易受调制方案(例如8-PSK)所产生的信道差错的损害的比特节点分配少量校验节点。

这种LDPC码具有可并行解码算法(不同于turbo码)，其有利之处是涉及例如相加，比较和表查找的简单操作。此外，精心设计的LDPC码不会表现出差错平台的任何迹象。

根据本发明的一个实施例，发送器101使用相对简单的编码技术产生基于奇偶校验矩阵(利于在解码期间进行高效的存储器访问)的LDPC码，以便与接收器105通信。发送器101使用优于串联turbo+RS(里德-索罗蒙)码的LDPC码，假定分组长度足够地大。

图2A和2B是图1的发送器中采用的示例性LDPC编码器的图例。如图2A所示，发送器200配备有LDPC编码器203，LDPC编码器203接受来自信息源201的输入，并且输出具有更高冗余度、适于接收器105上的纠错处理的编码流。信息源201根据离散字符表X产生k个信号。

LDPC码被指定有奇偶校验矩阵。另一方面，对LDPC码进行编码通常需要指定生成矩阵。即使可以使用高斯消去法由奇偶校验矩阵获得生成矩阵，然而所得到的矩阵不再是稀疏的，并且存储较大的生成矩阵会更加复杂。

通过使奇偶校验矩阵结构化，编码器203使用仅利用奇偶校验矩阵的简单编码技术根据字符表Y产生提供给调制器205的信号。具体地，通过将某部分矩阵限制为三角矩阵，对奇偶校验矩阵产生限制。下面在图6中更加全面地描述这种奇偶校验矩阵的构造。这种限制导致微小的性能损失，因此构成有吸引力的折衷。

调制器205将来自编码器203的编码消息映射成发送给发送天线207的信号波形，发送天线207通过通信信道103发射这些波形。因此，编码消息被调制和发送到发送天线207。如下所述，从发送天线207发送的信号传播到接收器。

图2B根据本发明的一个实施例示出了用于博斯-乔赫里-霍克文黑姆码(BCH)编码器和循环冗余校验(CRC)编码器的LDPC编码器。在这种情况下，LDPC编码器203和CRC编码器209与BCH编码器211一起产生的代码具有串联的外BCH码和内低密度奇偶校验(LDPC)码。此外，使用循环冗余校验(CRC)码实现检错。在示例性实施例中，CRC编码器209使用具有生成多项式(x⁵+x⁴+x³+x²+1)(x²+x+1)(x+1)的8位CRC码进行编码。

LDPC编码器203系统地将具有长度k_ldpc的信息分组 $>>i>=>>(>>i>0>>,>>i>1>>,>.>.>.>,>>i>>>k>ldpc>>->1>>>)>>>$编码成具有长度n_lpdc的码字 $>>c>=>>(>>i>0>>,>>i>1>>,>.>.>.>,>>i>>>k>ldpc>>->1>>>,>>p>0>>,>>p>1>>,>.>.>.>,>>p>>>n>ldpc>>->>k>ldpc>>->1>>>)>>.>>$码字的发送按照指定顺序从i₀开始，并且以p_{nldpc-kldpc-1}结束。

在下面的表1中提供了LDPC码参数(n_ldpc，k_ldpc)。

表1

LDPC编码器203的任务是确定具有k_ldpc个信息比特(i₀，i₁，...，i_kldpc-1)的每个分组的n_ldpc-k_ldpc个奇偶校验比特(p₀，p₁，...，p_{nldpc-kldpc-1})。该过程如下所述。首先，初始化奇偶校验比特； $>>>p>0>>=>>p>1>>=>>p>2>>=>.>.>.>=>>p>>>n>ldpc>>->>k>ldpc>>->1>>>=>0>.>>$在表3至10的第一行中指定的奇偶校验比特地址上累加第一信息比特i₀。例如，对于比率2/3(表3)，得到以下结果：

p₀    ＝p₀_i₀

p₁₀₄₉₁＝p₁₀₄₉₁_i₀

p₁₆₀₄₃＝p₁₆₀₄₃_i₀

p₅₀₆  ＝p₅₀₆_i₀

p₁₂₈₂₆＝p₁₂₈₂₆_i₀

p₈₀₆₅ ＝p₈₀₆₅_i₀

p₈₂₂₆ ＝p₈₂₂₆_i₀

p₂₇₆₇ ＝p₂₇₆₇_i₀

p₂₄₀  ＝p₂₄₀_i₀

p₁₈₆₇₃＝p₁₈₆₇₃_i₀

p₉₂₇₉ ＝p₉₂₇₉_i₀

p₁₀₅₇₉＝p₁₀₅₇₉_i₀

P₂₀₉₂₈＝p₂₀₉₂₈_i₀

(所有相加均在GF(2)中)。

接着，对于下面的359个信息比特i_m，m＝1，2，...，359，在奇偶校验比特地址{x+m mod 360×q}mod(n_ldpc-k_ldpc)上累加这些比特，其中x表示对应于第一比特i₀的奇偶校验比特累加器(parity bit accumulator)的地址，q是表2中指定的编码率相关常数。继续讨论此例子，对于比率2/3，q＝60。例如，对于信息比特i₁，执行以下操作：

p₆₀   ＝p₆₀_i₁

p₁₀₅₅₁＝p₁₀₅₅₁_i₁

p₁₆₁₀₃＝p₁₆₁₀₃_i₁

p₅₆₆  ＝p₅₆₆_i₁

p₁₂₈₈₆＝p₁₂₈₈₆_i₁

p₈₁₂₅ ＝p₈₁₂₅_i₁

p₈₂₈₆ ＝p₈₂₈₆_i₁

p₂₈₂₇ ＝p₂₈₂₇_i₁

p₃₀₀  ＝p₃₀₀_i₁

p₁₈₇₃₃＝p₁₈₇₃₃_i₁

p₉₃₃₉ ＝p₉₃₃₉_i₁

p₁₀₆₃₉＝p₁₀₆₃₉_i₁

p₂₀₉₈₈＝p₂₀₉₈₈_i₁

对于第361个信息比特i₃₆₀，在表3至10的第二行中指定了奇偶校验比特累加器的地址。以类似的方式，使用公式{x+m mod360×q}mod(n_ldpc-k_ldpc)获得后面359个信息比特i_m，m＝361，362，...，719的奇偶校验比特累加器的地址，其中x表示对应于信息比特i₃₆₀的奇偶校验比特累加器的地址，即表3-10中第二行的表项。以类似的方式，对于具有360个新信息比特的每个组，表3至10中的新行被用来寻找奇偶校验比特累加器的地址。

在处理完所有的信息比特之后，获得如下所示的最终奇偶校验比特。首先，从i＝1开始执行以下操作

p_i＝p_i_p_i-1，i＝1，2，...，n_ldpc-k_ldpc-1。

p_i，i＝0，1，...，n_ldpc-k_ldpc-1的最终内容等于奇偶校验比特p_i。

表2

表3

表4

表5

表6

表7

表8

表9

表10

对于BCH编码器211，在表11中列举了BCH码参数。

表11

应当注意，在前面的表格中，n_bch＝k_ldpc。

通过相乘下面表12的列表中的第一t多项式，得到t纠错BCH编码器211的生成多项式：

表12

按照以下方式将信息比特 $>>m>=>>(>>m>>>k>bch>>->1>>>,>>m>>>k>bch>>->2>>>,>.>.>.>,>>m>1>>,>>m>0>>)>>>$BCH编码成码字 $>>c>=>>(>>m>>>k>bch>>->1>>>,>>m>>>k>bch>>->2>>>,>.>.>.>,>>m>1>>,>>m>0>>,>>d>>>n>bch>>->>k>bch>>->1>>>,>>d>>>n>bch>>->>k>bch>>->2>>>,>.>.>.>,>>d>1>>,>>d>0>>)>>.>>$信息多项式 $>>m>>(>x>)>>=>>m>>>k>bch>>->1>>>>x>>>k>bch>>->1>>>+>>m>>>k>bch>>->2>>>>x>>>k>bch>>->2>>>+>.>.>.>+>>m>1>>x>+>>m>0>>>$乘以x^nbch-kbch。接着，x^nbch-kbchm(x)除以g(x)。以 $>>d>>(>x>)>>=>>d>>>n>bch>>->>k>bch>>->1>>>>x>>>n>bch>>->>k>bch>>->1>>>+>.>.>.>+>>d>1>>x>+>>d>0>>>$为余数，码字多项式被设置如下： $>>c>>(>x>)>>=>>x>>>n>bch>>->>k>bch>>>>m>>(>x>)>>+>d>>(>x>)>>.>>$

在示例性实施例中，以上LDPC码可以用于各种数字视频应用，例如MPEG(运动图象专家组)分组传输。

图3是图1的系统中的示例性接收器的图例。在接收端，接收器300包含解调器301，解调器301对从发送器200接收的信号执行解调。在接收天线303上接收这些信号以进行解调。在解调之后，接收信号被传送到解码器305，解码器305通过结合比特度量产生器307来产生信息X′，从而重构初始源信息。通过非Gray映射，比特度量产生器307在解码处理期间与解码器305来回(迭代)交换概率信息，如图10所示。可选地，如果使用Gray映射(根据本发明的一个实施例)，比特度量产生器执行一遍就足够了，其中每次LDPC解码器迭代之后进一步的比特度量产生的尝试可能产生有限的性能改进；这里参照图11更加全面地描述了这个方案。为理解本发明的优点，如图4所示，查看如何产生LDPC码是有用的。

[49]图4的图例根据本发明的实施例示出了稀疏奇偶校验矩阵的图例。LDPC码是具有稀疏奇偶校验矩阵H_(n-k)xn的长线性分组码。通常，分组长度n的范围为数千到数万比特。例如，图4示出了具有长度n＝8和比率1/2的LDPC码的奇偶校验矩阵。图5的双向图可以等价表示相同的码。

图5是图4中矩阵的LDPC码的双向图的图例。奇偶校验公式意味着，对于每个校验节点，所有相邻比特节点的累加和(在GF(伽罗瓦域)(2)上)等于零。如附图所示，比特节点占据图表的左边，并且根据预定关系与一或多个校验节点相关。例如，对应于校验节点m₁，相对于比特节点存在以下表达式n₁+n₄+n₅+n₈＝0。

回到接收器303，LDPC解码器305被认为是信息通过解码器，其中解码器305的目标是寻找比特节点的数值。为完成这个任务，比特节点和校验节点迭代地彼此通信。这个通信的性质如下所述。

从校验节点到比特节点，每个校验节点为一个相邻比特节点提供有关该比特节点的数值的估测(″评价″)，该估测基于来自其它相邻比特节点的信息。例如，在前面的例子中，如果n₄，n₅和n₈的累加和对于m₁而言″看上去象″0，则m₁向n₁指示：n₁的数值相信为0(由于n₁+n₄+n₅+n₈＝0)；否则m₁向n₁指示：n₁的数值相信为1。另外，对于软判决解码，增加可靠性测量。

从比特节点到校验节点，每个比特节点向相邻校验节点传递有关其自身数值的估测，该估测基于来自它的其它相邻校验节点的反馈。在前面的例子中，n₁只具有两个相邻校验节点m₁和m₃。如果从m₃向n₁的反馈表明n₁的数值可能为0，则n₁会通知m₁：n₁自身数值的估测为0。对于比特节点具有超过两个的相邻校验节点的情况，比特节点在向与其通信的校验节点报告判决之前，对来自它的其它相邻校验节点的反馈执行多数表决(软判决)。以上处理被重复，直到所有比特节点被认为是正确的(即满足所有奇偶校验公式)，或者直到到达迭代的预定最大数量，从而声明解码失败。

图6的图例根据本发明的实施例示出了稀疏奇偶校验矩阵的子矩阵，其中子矩阵包含限制到下三角区的奇偶校验值。如前所述的，通过限制奇偶校验矩阵的下三角区的数值，编码器203(图2A和2B)可以使用简单编码技术。根据本发明的实施例，施加于奇偶校验矩阵的限制具有以下形式：

H_(n-k)xn＝[A_(n-k)xkB_(n-k)x(n-k)]，其中B是下三角。

使用H_c^T＝0将任何信息分组i＝(i₀，i₁...，i_k-1)编码成码字c＝(i₀，i₁，...，i_k-1，p₀，p₁，...，p_n-k-1)，并且递归地对奇偶校验比特求解；例如，

a₀₀i₀+a₀₁i₁+...+a_0，k-1i_k-1+p₀＝0＝＞  求解p₀，

a₁₀i₀+a₁₁i₁+...+a_1，k-1i_k-1+b₁₀p₀+p₁＝0＝＞  求解p₁

并且类似地对p₂，p₃，...，p_n-k-1求解。

图7的图表示出了利用非限制奇偶校验矩阵(H矩阵)的码和利用具有图6的限制H矩阵的码之间的性能对比。该图表示出了两种LDPC码之间的性能比较：具有通用奇偶校验矩阵的LDPC码，和奇偶校验矩阵被限制为下三角以简化编码的LDPC码。对于这个模拟，调制方案为8-PSK。性能损失在0.1dB以内。因此，由于下三角H矩阵的限制，性能损失是微小的，而在编码技术的简化方面的效果是显著的。因此，等价于下三角或行和/或列置换后的上三角的任何奇偶校验矩阵，可以用于相同的目的。

图8A和8B的图例分别示出了均可以在图1的系统中使用的非Gray 8-PSK调制方案和Gray 8-PSK调制方案。可以在图3的接收器中使用图8A的非Gray 8-PSK方案，以提供需要极低帧消除率(FER)的系统。通过结合例如博斯-乔赫里-霍克文黑姆码(BCH)，汉明码或里德-索罗蒙(RS)码的外码而使用图8B所示的Gray 8-PSK方案，也可以满足这个要求。

在这个可以使用8-PSK调制的方案下，不必在LDPC解码器305(图3)和比特度量产生器307之间进行迭代。在没有外码的情况下，如下面图9所示，使用Gray标记的LDPC解码器305表现出较早的差错平台(error floor)。

图9的图表示出了利用图8A和8B的Gray标记和非Gray标记的码之间的性能对比。差错平台源于这样的事实：假定来自LDPC解码器305的反馈正确，则对于非Gray标记而言，8-PSK比特度量的再生更加精确，因为具有已知2比特的两个8-PSK符号与非Gray标记进一步分离。这可以等价地视为以更高的信噪比(SNR)工作。因此，即使使用Gray或非Gray标记的相同LDPC码的差错渐近线具有相同的斜率(即彼此平行)，具有非Gray标记的LDPC码的差错渐近线会在任何SNR上穿过较低的FER。

另一方面，对于不需要极低FER的系统，在LDPC解码器305和8-PSK比特度量产生器307之间没有任何迭代的Gray标记可能更加适用，由于在每次LDPC解码器迭代之前再生8-PSK比特度量会导致额外的复杂度。此外，当使用Gray标记时，在每次LDPC解码器迭代之前再生8-PSK比特度量只产生非常轻微的性能改进。如上所述，没有迭代的Gray标记可以被用于需要极低FER的系统，假定实现外码。

Gray标记和非Gray标记之间的选择还取决于LDPC码的特征。通常，比特或校验节点度数(degree)越高，则越适用于Gray标记，由于对于更高的节点度数，就非Gray标记而言，从LDPC解码器305到8-PSK(或类似的更高阶调制)比特度量产生器307的初始反馈退化得更加厉害。

当8-PSK(或类似的更高阶)调制被用于二进制解码器时，发现没有″等噪声″地接收符号的3个(或更多)比特。例如，对于Gray 8-PSK标记，认为符号的第3个比特给解码器带来的噪声多于其它2比特。因此，LDPC码设计没有为8-PSK符号的″含更多噪声″的第3比特所表示的那些比特节点分配少量的边(edge)，使得那些比特没有被双倍惩罚。

图10的流程图根据本发明的实施例示出了使用非Gray映射的LDPC解码器的操作。在这个方案中，LDPC解码器和比特度量产生器逐个进行迭代。在这个例子中，使用8-PSK调制；然而相同原理也适用于其它更高级的调制方案。在这种情况下，假定解调器301输出距离向量d，向比特度量产生器307指示接收的有噪声符号点和8-PSK符号点之间的距离，因而向量分量如下所示：

$>>>d>i>>=>->>>E>s>>>N>o>>>\{>>>(>>r>x>>->>s>>i>,>x>>>)>>2>>+>>>(>>r>y>>->>s>>i>,>y>>>)>>2>>\}>->->->i>=>0,1>,>.>.>.>,>7>.>>$

8-PSK比特度量产生器307与LDPC解码器305通信以交换先验概率信息和后验概率信息，其中先验概率信息和后验概率信息分别被表示成u和a。也就是说，向量u和a分别表示编码比特的对数似然比的先验和后验概率。

8-PSK比特度量产生器307按如下方式产生每组3个比特的先验似然比。首先，获得有关编码比特的非本征信息：

e_j＝a_j-u_j          j＝0，1，2。

接着确定8-PSK符号概率p_i，i＝0，1，...，7。

^*y_j＝-f(0，e_j)     j＝0，1，2其中f(a，b)＝max(a，b)+LUT_f(a，b)，LUT_f(a，b)＝ln(1+e^-|a-b|)

^*x_j＝y_j+e_j        j＝0，1，2

^*p₀＝x₀+x₁+x₂     p4＝y₀+x₁+x₂

p₁＝x₀+x₁+y₂      p₅＝y₀+x₁+y₂

p₂＝x₀+y₁+x₂      p₆＝y₀+y₁+x₂

p₃＝x₀+y₁+y₂      p₇＝y₀+y₁+y₂

接着，比特度量产生器307按照如下方式确定编码比特的先验对数似然比以作为LDPC解码器305的输入：

u₀＝f(d₀+p₀，d₁+p₁，d₂+p₂，d₃+p₃)-f(d₄+p₄，d₅+p₅，d₆+p₆，d₇+p₇)-e₀

u₁＝f(d₀+p₀，d₁+p₁，d₄+p₄，d₅+p₅)-f(d₂+p₂，d₃+p₃，d₆+p₆，d₇+p₇)-e₁

u₂＝f(d₀+p₀，d₂+p₂，d₄+p₄，d₆+p₆)-f(d₁+p₁，d₃+p₃，d₅+p₅，d₇+p₇)-e₂

应当注意，具有超过两个的变量的函数j(.)可以被递归评估；例如f(a，b，c)＝f(f(a，b)，c)。

现在描述使用非Gray映射的LDPC解码器305的操作。在步骤1001，LDPC解码器305根据以下公式(和图12A所示的)在第一次迭代之前初始化编码比特的对数似然比v：

$>>>v>>n>\to >>k>i>>>>=>>u>n>>,>>$n＝0，1，...，N-1，i＝1，2，...，deg(比特节点n)

这里，v_n→ki表示从比特节点n到其相邻校验节点k_i的信息，u_n表示比特n的解调器输出，N是码字长度。

在步骤1003，更新校验节点k，其中输入v产生输出w。如图12B所示，从其d_c个相邻比特节点到校验节点k的传入信息被表示成v_n1→k，v_n2→k，...，v_ndc→k。目标是计算从校验节点k回到d_c个相邻比特节点的传出信息。这些信息被表示成w_k→n1，w_k→n2，...，w_k→ndc，其中

$>>>w>>k>\to >>n>i>>>>=>g>>(>>v>>>n>1>>\to >k>>>,>>v>>>n>2>>\to >k>>>,>>.>.>.>,>>v>>>n>>i>->1>>>\to >k>>>,>>v>>>n>>i>+>1>>>\to >k>>>,>.>.>.>,>>v>>>n>dc>>\to >k>>>)>>>$

函数g()被定义如下：

g(a，b)＝sign(a)×sign(b)×{min(|a|，|b|)}+LUT_g(a，b)，

其中LUT_g(a，b)＝ln(1+e^-|a+b|)-ln(1+e^-|a-b|)。类似于函数f，具有超过两个的变量的函数g可以递归评估。

接着，解码器305在步骤1205输出后验概率信息(图12C)，使得：

$>>>a>n>>=>>u>n>>+>>\Sigma >j>>>w>>>k>j>>\to >n>>>.>>$

在步骤1007，确定是否满足所有的奇偶校验公式。如果不满足这些奇偶校验公式，则象在步骤1009中那样，解码器305重新导出8-PSK比特度量和信道输入u_n。接着象在步骤1011中那样，更新比特节点。

如图14C所示，从其d_v个相邻校验节点到比特节点n的传入信息被表示成w_k1→n，w_k2→n，...，w_kdv→n。计算从比特节点n回到d_v个相邻校验节点的传出信息；这种信息被表示成v_n→k1，v_n→k2，...，v_n→kdv，并且计算如下：

$>>>v>>n>\to >>k>i>>>>=>>u>n>>+>>\Sigma >>j>\ne >i>>>>w>>>k>j>>\to >n>>>>$

在步骤1013，解码器305输出硬判决(在满足所有奇偶校验公式的情况下)：

如果 $>>>>Hver>>c>^>>>T>>=>0>,>>$则停止

当使用非Gray标记时，以上方案是合适的。然而当实现Gray标记时，执行图11的处理。

图11的流程图根据本发明的实施例示出了图3的使用Gray映射的LDPC解码器的操作。当使用Gray标记时，只在LDPC解码器之前一次性产生比特度量会更加有利，因为在每次LDPC解码器迭代之后再生比特度量只产生微小的性能改进。象图10的步骤1001和1003那样，执行编码比特v的对数似然比的初始化，并且在步骤1101和1103更新校验节点。接着象在步骤1105中那样，更新比特节点n。此后，解码器输出后验概率信息(步骤1107)。在步骤1109，确定是否满足所有的奇偶校验公式；如果全部满足，解码器输出硬判决(步骤1111)。否则重复步骤1103-1107。

图13A的流程图根据本发明的各个实施例示出了使用正反向方案计算校验节点和比特节点之间的传出消息的处理。对于具有d_c个相邻边的校验节点，执行d_c(d_c-1)和许多g(.，.)函数的计算。然而，正反向方案将计算复杂度缩减到3(d_c-2)，其中存储d_c-1个变量。

参照图12B，从d_c个相邻比特节点到校验节点k的传入信息被表示成v_n1→k，v_n2→k，...，v_ndc→k。期望计算从校验节点k回到d_c个相邻比特节点的传出信息；这些传出信息被表示成w_k→n1，w_k→n2，...，w_k→ndc。

在计算这些传出信息的正反向方案中，正向变量f₁，f₂，...，f_dc被定义如下：

f₁＝v_1→k

f₂＝g(f₁，v_2→k)

f₃＝g(f₂，v_3→k)

.  .  .    

.  .  .

f_dc＝g(f_dc-1，v_dc→k)

在步骤1301，计算这些正向变量，并且在步骤1303存储这些正向变量。

类似地，反向变量b₁，b₂，...，b_dc被定义如下：

b_dc＝v_dc→k

b_dc-1＝g(b_dc，v_dc-1→k)

b₁＝g(b₂，v_1→k)

在步骤1305，计算这些反向变量。此后象在步骤1307中那样，根据存储的正向变量和计算的反向变量计算传出信息。传出信息被计算如下：

w_k→1＝b₂

w_k→i＝g(f_i-1，b_i+1)    i＝2，3，...，d_c-1

w_k→dc＝f_dc-1

在这个方案中，只需要存储正向变量f₂，f₃，...，f_dc。当计算反向变量b_i时，同时计算传出信息w_k→i，从而不必存储反向变量。

如下面讨论的，通过并行方案可以进一步增强计算负载。

图13B的流程图根据本发明的各个实施例示出了使用并行方案计算校验节点和比特节点之间的传出消息的处理。对于具有来自d_c个相邻比特节点的输入v_n1→k，v_n2→k，...，v_ndc→k的校验节点k，象在步骤1311中那样计算以下参数：

$>>>\gamma >k>>=>g>>(>>v>>>n>1>>\to >k>>>,>>v>>>n>2>>\to >k>>>,>.>.>.>,>>v>>>n>dc>>\to >k>>>)>>>$

应当注意，g(.，.)函数也可以被表示成以下形式：

$>>g>>(>a>,>b>)>>=>ln>>>1>+>>e>>a>+>b>>>>>>e>a>>+>>e>b>>>>>$

[821通过使用g(.，.)函数的回归性质，得到以下表达式：

$>>>\gamma >k>>=>ln>>>1>+>>e>>g>>(>>v>>>n>1>>\to >k>>>,>>.>.>.>,>>v>>>n>>i>->1>>>\to >k>>>,>>v>>>n>>i>+>1>>>\to >k>>>,>>.>.>.>,>>v>>>n>dc>>\to >k>>>)>>+>>v>>>n>i>>\to >k>>>>>>>e>>g>>(>>v>>>n>1>>\to >k>>>,>>.>.>.>,>>v>>>n>>i>->1>>>\to >k>>>,>>v>>>n>>i>+>1>>>\to >k>>>,>>.>.>.>,>>v>>>n>dc>>\to >k>>>)>>+>>e>>v>>>n>i>>\to >k>>>>>>>=>ln>>>1>+>>e>>>w>>k>\to >>n>i>>>>+>>v>>>n>i>>\to >k>>>>>>>>e>>w>>k>\to >>n>i>>>>>+>>e>>v>>>n>i>>\to >k>>>>>>>$

因此，可以按照下面的方式对w_k→ni求解：

$>>>w>>k>\to >>n>i>>>>=>ln>>>>e>>>v>>>n>i>>\to >k>>>+>>\gamma >k>>>>->1>>>>e>>>v>>>n>i>>\to >k>>>->>\gamma >k>>>>->1>>>->>\gamma >k>>>$

使用表示函数ln|e^x-1|的查找表LUT_x可以获得以上公式的ln(.)项(步骤1313)。不同于其它查找表LUT_f或LUT_g，表LUT_x需要的表项的数量最好与量化等级的数量一样多。一旦获得γ_k，可以在步骤1315使用以上公式并行地针对所有n_i计算w_k→ni。

γ_k的计算延迟为log₂(d_c)会更加有利。

图14A-14C的图表示出了根据本发明的各个实施例产生的LDPC码的模拟结果。尤其是，图14A-14C示出了具有更高阶调制和编码率3/4(QPSK，1.485比特/符号)，2/3(8-PSK，1.980比特/符号)和5/6(8-PSK，2.474比特/符号)的LDPC码的性能。

存在两个通用方案以实现校验节点和比特节点之间的互连：(1)完全并行方案和(2)部分并行方案。在完全并行体系结构中，物理实现所有节点及其互连。这个体系结构的优点是速度。

然而在实现所有节点及其连接时，完全并行体系结构会导致更大的复杂度。因此，对于完全并行体系结构，需要使用更小的分组长度以降低复杂度。在这种情况下，对于相同的时钟频率，会导致成比例的吞吐率降低，和FER-Es/No性能的某种退化。

实现LDPC码的第二个方案是只物理实现全部节点的一个子集，并且只使用这些有限数量的″物理″节点来处理码的所有″功能″节点。尽管可以使LDPC解码器的操作非常简单，并且能够并行执行，然而进一步的设计问题是如何在″随机″分布的比特节点和校验节点之间建立通信。根据本发明的一个实施例，解码器305(图3)通过以结构化方式访问存储器来解决这个问题，从而实现表面上随机的码。参照图15A和15B说明这个方案。

图15A和15B的图例根据本发明的实施例分别示出了存储器的上边和下边，所述存储器被组织成支持结构化访问，以实现LDPC编码中的随机性。通过聚焦于奇偶校验矩阵的生成，可以实现结构化访问而无需破坏真正随机码的性能。通常，可以通过校验节点与比特节点的连接规定奇偶校验矩阵。例如，比特节点可以被分成具有固定尺寸的组，出于图解的目的，该尺寸为392。另外，假定连接到度数3的第一比特节点的校验节点被编号为例如a，b和c，则连接到第二比特节点的校验节点被编号为a+p，b+p和c+p，连接到第三比特节点的校验节点被编号为a+2p，b+2p和c+2p等等；其中p＝(校验节点的编号)/392。对于具有392个比特节点的下一个组，连接到第一比特节点的校验节点不同于a，b，c，使得通过适用选择p，所有校验节点具有相同的度数。在自由常数(free constants)上执行随机搜索，使得所得到的LDPC码没有cycle-4和cycle-6。由于本发明的奇偶校验矩阵的结构特征，可以存储边信息，以允许在解码期间并行访问一组相关边值。

换言之，本发明的方案利于在校验节点和比特节点处理期间进行存储器访问。双向图中边的数值可以被存储在例如随机访问存储器(RAM)的存储介质中。应当注意，对于校验节点和比特节点处理期间的真正随机LDPC码，需要以随机方式逐个访问边的数值。然而这种常规访问方案对于高数据速率应用而言速度过慢。以这样的方式组织图15A和15B的RAM，其中可以在一个时钟周期内获取较大的相关边的组；因此，根据预定方案或结构，这些数值在存储器中被放置在″一起″。可以发现，实际上，即使具有真正随机码，对于一组校验节点(和分别地，比特节点)而言，相关边可以在RAM中放置在彼此之后，但是与一组比特节点(分别地，校验节点)相邻的相关边会随机散布在RAM中。因此，本发明所说的″一起″源于奇偶校验矩阵本身的设计。也就是说，校验矩阵设计保证一组比特节点和校验节点的相关边在RAM中同时放置在一起。

如图15A和15B所示，每个框包含边的数值，为多个比特(例如6个)。根据本发明的一个实施例，边RAM被分成两个部分：上边RAM1501(图15A)和下边RAM 1503(图15B)。下边RAM 1503包含例如度数2的比特节点和校验节点之间的边。上边RAM 1503包含例如度数大于2的比特节点和校验节点之间的边。因此，对于每个校验节点，2个相邻边被存储在下边RAM 1503中，其余边被存储在上边RAM 1501中。例如，表14指定了各个编码率下上边RAM 1501和下边RAM 1503的尺寸：

表14

根据表14，具有尺寸576×392的边RAM足以存储所有编码率1/2，2/3，3/4和5/6的边度量。

如上所述，在这个示例性情况下，一次选择一组392个比特节点和392个校验节点进行处理。对于392个校验节点的处理，从上边RAM1501访问q＝d_c-2个连续行，并且从下边RAM 1503访问2个连续行。d_c的数值取决于具体的码，例如针对上述的码，对于比率1/2，d_c＝7；对于比率2/3，d_c＝10；对于比率3/4，d_c＝16；对于比率5/6，d_c＝22。当然，可以针对其它的码采用其它的d_c数值。在这种情况下，q+2为每个校验节点的度数。

对于比特节点处理，如果392个比特节点的组具有度数2，其边位于下边RAM 1503的2个连续行中。如果比特节点具有度数d＞2，其边位于上边RAM 1501的d个行中。这d个行的地址可以被存储在例如只读存储器(ROM)的非易失存储器中。这些行中的一个内的边对应于392个比特节点的第一边，另一个行内的边对应于392个比特节点的第二边，等等。此外，对于每个行，属于392个节点的组中的第一比特节点的边的列索引也可以被存储在ROM中。对应于第二，第三比特节点等等的边以″回绕″方式跟随在开始列索引之后。例如，如果行中第j个边属于第一比特节点，则第(j+1)个边属于第二比特节点，第(j+2)个边属于第三比特节点，...，而第(j-1)个边属于第392个比特节点。

通过图15A和15B示出的组织，在LDPC编码期间大大增强了存储器访问的速度。

图16图解了一种计算机系统，通过该计算机系统可以实现基于本发明的实施例。计算机系统1600包含总线1601或用于传送信息的其它通信机构，和连接到总线1601以处理信息的处理器1603。计算机系统1600也包含例如随机访问存储器(RAM)的主存储器1605或其它动态存储设备，其连接到总线1601以存储信息和将由处理器1603执行指令。主存储器1605也可以被用来在处理器1603执行的指令的执行期间存储临时变量或其它中间信息。计算机系统1600还包含只读存储器(ROM)1607或其它静态存储设备，其连接到总线1601以存储处理器1603的静态信息和指令。例如磁盘或光盘的存储设备1609还被连接到总线1601以存储信息和指令。

计算机系统1600可以通过总线1601连接到显示器1611，例如阴极射线管(CRT)，液晶显示器，有效矩阵显示器或等离子体显示器以向计算机用户显示信息。输入设备1613，例如包含字符和其它按键的键盘被连接到总线1601，以向处理器1603传送信息和命令选择。另一种用户输入设备是光标控制器1615，例如鼠标，轨迹球或光标方向键，用于向处理器1603传送方向信息和命令选择，并且用于控制光标在显示器1611上的移动。

根据本发明的一个实施例，计算机系统1600响应处理器1603执行主存储器1605中包含的指令序列而提供LDPC码的生成。可以从例如存储设备1609的另一个计算机可读介质将这种指令读取到主存储器1605中。主存储器1605中包含的指令序列的执行导致处理器1603执行这里描述的处理步骤。多处理结构中的一或多个处理器也可以被用来执行主存储器1605中包含的指令。在可选实施例中，可以使用硬连线电路取代软件指令或与之结合，以实现本发明的实施例。于是，本发明的实施例不局限于硬件电路和软件的任何特定组合。

计算机系统1600还包含连接到总线1601的通信接口1617。通信接口1617提供连接到网络链路1619的双向数据通信，所述网络链路1619连接到局域网1621。例如，通信接口1617可以是数字用户线路(DSL)卡或调制解调器，综合业务数字网络(ISDN)卡，电缆调制解调器或电话调制解调器，用于提供针对相应类型的电话线的数据通信连接。作为另一个例子，通信接口1617可以是局域网(LAN)卡(例如Ethemet^TM或异步传送模式(ATM)网络的局域网(LAN)卡)，用于提供针对兼容LAN的数据通信连接。也可以实现无线链路。在任何这种实现中，通信接口1617发送和接收电气，电磁或光学信号，这些信号传递表示各种信息的数字数据流。此外，通信接口1617可以包含外设接口设备，例如通用串行总线(USB)接口，PCMCIA(个人计算机存储器卡国际协会)接口等等。

网络链路1619通常通过一或多个网络提供到其它数据设备的数据通信。例如，网络链路1619可以提供通过局域网1621到主计算机1623的连接，主计算机1623具有到网络1625(例如广域网(WAN)或全球分组数据通信网络，现在通常被称作″因特网″)或到服务提供商操作的数据设备的连接。局域网1621和网络1625使用电气，电磁或光学信号传送信息和指令。通过各个网络传送的信号，和通过通信接口1617在网络链路1619上传送的信号是传递信息和指令的载波的示例性形式，其中通信接口1617与计算机系统1600之间传送数字数据。

计算机系统1600可以通过网络，网络链路1619和通信接口1617发送信息和接收包含程序代码的数据。在因特网例子中，服务器(未示出)可以通过网络1625，局域网1621和通信接口1617发送所请求的代码，所述的代码属于用来实现本发明的实施例的应用程序。处理器1603可以执行发送的代码(同时被接收)，并且/或者在存储设备169或其它非易失存储器中存储此代码，以便以后执行。通过这种方式，计算机系统1600可以获得载波形式的应用代码。

这里使用的术语″计算机可读介质″是指参与向处理器1603提供指令以便执行的任何介质。这种介质可以采用许多形式，包含但不局限于非易失介质，易失介质和传输介质。非易失介质包含例如光盘或磁盘，例如存储设备1609。易失介质包含动态存储器，例如主存储器1605。传输介质包含同轴电缆，铜线和光纤，包含有包括总线1601的导线。传输介质也可以具有声波，光波或电磁波，例如在射频(RF)和红外(IR)数据通信期间产生的波的形式。计算机可读介质的常见形式包含例如软盘，柔性盘(flexible disk)，硬盘，磁带，任何其他磁介质，CD-ROM，CDRW，DVD，任何其他光学介质，打孔卡，纸带，光学标记卡片，任何其他具有孔图案或其它光学可识别标记的物理介质，RAM，PROM和EPROM，快擦写EPROM，任何其他存储器芯片或盒，载波，或任何其他计算机可以读取的介质。

各种形式的计算机可读介质可以用来向处理器提供指令以便执行。例如，最初可以在远程计算机的磁盘上携带用于执行至少部分本发明的指令。在这种情况下，远程计算机将指令加载到主存储器中，使用调制解调器并通过电话线发送指令。本地计算机系统的调制解调器接收电话线上的数据，使用红外发送器将数据转换成红外信号，并且将红外信号发送到便携计算设备，例如个人数字助理(PDA)和膝上型电脑。便携计算设备上的红外探测器接收红外信号传递的信息和指令，并且将数据放在总线上。总线将数据传送到主存储器，而处理器从主存储器检索和执行指令。可选地，在被处理器执行之前或之后，主存储器接收的指令可以被存储在存储设备上。

因此，本发明的各个实施例提供了用于对结构化低密度奇偶校验(LDPC)码进行编码的方案。通过将奇偶校验矩阵的部分限制为下三角，并且/或者满足其它要求以简化解码器的比特节点和校验节点之间的通信，提供LDPC码的结构。访问存储表示结构化奇偶校验矩阵的信息的存储器。信息被组织成表格形式，其中每个行表示数值1在奇偶校验矩阵的列组的第一列内的存在。各个行对应于奇偶校验矩阵的各个列组，其中根据预定操作(例如循环移位，相加等等)导出每个组内的后续列。LDPC编码信号基于所存储的表示奇偶校验矩阵的信息。根据本发明的一个实施例，利用博斯-乔赫里-霍克文黑姆码(BCH)编码器，发送器使用BCH码对输入信号进行编码，其中对应于输入信号的输出LDPC编码信号表示具有外BCH码和内LDPC码的码。此外，提供循环冗余校验(CRC)编码器以便根据CRC码对输入信号进行编码。以上方案有利的是，以上方案降低了复杂度，但没有牺牲性能。

虽然已经结合若干实施例和实现描述了本发明，然而本发明不限于，但是覆盖了在所附权利要求书的范围内的各种明显的修改和等价方案。