CN1266555A - 乘积码的迭代解码 - Google Patents

Abstract

本发明涉及的是对从传输信道上接收到的长度为n的k维分组线性码的一个字(s)的软输入和软输出解码方法,其中的步骤为:－对用对接收到的字的各分量的恒定近似及对可靠性最差的分量的更换所得到的k元组的表格进行编码,生成接收到的编码字(s)的近似码的恒定字(u_b)一个表,－用下述两个度量之差计算输出的软字第j个分量:一方面是对最接近的生成的编码字的度量,另一方面是对具有和第j个分量的相反的分量的最接近的生成的编码字的度量,或者如果没有最不接近的生成的编码字。本发明还涉及对从传输信道上接收到的乘积码字,使用前述的软输入和软输出解码方法的一种解码方法。本方法对乘积码的字的解码迅速而有效,即使没有代数解码器。

Description

乘积码的迭代解码

本发明的目的在于乘积码的一种迭代解码方法，本发明还涉及实施这种解码方法的一种传输方法和一个传输系统。

本发明涉及的是分组的线性码的乘积码的解码，用于信道编码的传输领域。典型的传输信道包含一个二进制信源、一个编码器、一个在信道发送的调制器、一个在信道输出端的解调器，以及一个提供二进制信号的解码器。述及的信道编码的目的在于缩小达到给定的误码率所需的功率。1997年10月9日申请的号码为9712594的法国专利题为“Procédéde codage bloc par code produit applicable notamment au codage d’unecellule ATM”给出了这种信道传输和编码的基本概念的描述，详细了解这方面的描述可以参考这个文献。本发明所涉及的是信道解码领域、对于传输系统的其它部件，如根据传输媒质所使用的信源编码和调制解调就不再作为说明的目的。

使用冗余码和乘积码进行编码是传统性的。通常一个码C₁是用一个三元组(n₁、k₁、d₁)来表征，此处k₁是该码输入的比特数，n₁是该码输出的比特数，而d₁是该码的最小汉明距离。将这样一个码应用一个k元组(x₁，…，x_k)提供一个n元组(x₁，…，x_k，x_k+1，…x_n)具有n-k个冗余比特。

按照下述方法相继应用的两个码C₁和C₂称为乘积码。考察k₁·k₂个比特，形式为k₂个长度为k₁比特的字，用码C₁(n₁，k₁，d₁)应用于k₂个k₁比特的字，得到k₂个n₁比特的字。写成矩阵形式后，k₂个n₁比特的字构成n₁列，其中第j列是由k₂个字中的每一个字的第j个比特构成的。用码C₂(n₂，k₂，d₂)应用于这n₁个k₂比特的列中的每一列以得到n₁个n₂比特的字。这样的一个乘积码的应用能从k₁·k₂比特继续到n₁·n₂个比特具有n₁·n₂-k₁·k₂个冗余比特。若所有的码都是线性的，则由此得出码C₁的n₂个字行或码C₂的n₁个字列。述及的乘积码是具有参量(n₁·n₂；k₁·k₂；d₁·d₂)的码。编码的顺序并不重要，不管是如前所述的先按行编码还是先按列编码，所得的结果相同。在有关信道编码的文献中描述这样的乘积码。已经说过的法国专利，或者还有专利FR-A-2712 760的图2都对用这种乘积码的编码原理做过详细的说明。

使用这种乘积码的问题在于在解调输出处的解码。在解调输出处得到的是伴随有噪声的比特值(通常调制成±1的形式)的集合。将接收到的伴随噪声的值称为软值(valeur souple)，为实数值；将值±1称为恒定值(valcur ferme)，即对应的二进制值，用阈值判定接收值而获得。后面，将二进制字称为恒定字(mot ferme)，将实际接收到的用实数值构成的字称为软字(mot souple)。

当用乘积码的编码传输时，便在解调器的输出处得到n₁·n₂个实数值(软值)的集合 R＝{r_i，j}，解码在于根据某种性能准则决定这些软值所对应的那个乘积码C₁·C₂的字。如果述及的噪声是加性的、白的、高斯型的，则最优化的解决方案是寻找到的乘积码字使其到达接收到的软字 R的欧几里得距离为最短。这种最大似然性准则在实际上是不可能的，因为乘积k₁·k₂通常超过几百。

对于保证乘积码的解码已经提出多种方案。最为直接的方案是对于接收的软字的每个比特做出恒定判定(décision ferme)，并逐个将各行解码成恒定判定，然后逐个将各列解码成恒定判定，与此同时用码C₂的解码器应用到各个列，然后用码C₂的解码器应用于各个行；这种解决办法远非最佳方案，且不能达到乘积码的理论增益，因为没有利用接收到的来自传输信道的全部信息。

专利FR-A-2712 760提出乘积码C₁·C₂的迭代解码算法，在这种算法中，多次对由接收到的乘积码的字所构成的矩阵的不同的行或列进行相继的解码。该文献提出，对于每一列或每一行，即对于接收到的赋有噪声的码C₁或C₂的每个字(接收到的软字)，用Chase修正算法进行解码，具体地说：

-生成码C₂或码C₁的恒定字的集合，经验地接近于接收到的关于相应行或相应列的软字；

-计算各个恒定字与接收到的软字之间的欧几里得距离；且

-从和相应的接收到的软字之间有最小距离的各恒定字中选择作为接收到的码字。

为了生成接近接收到的软字的码C₂(或C₁)的恒定字的集合，这个文献提出：

-将接收到的软字的可靠性最差的分量记作p分量；

-从可靠性最差的p个分量出发，建立q个测试二进制序列；

-从这些测试二进制序列和已解码的字的当前二进制值出发构成要解码的q个二进制字，述及的当前二进制值是用接收到的每个位的二进制近似在开始时初始化的。

-用Berkdlamp解码器(代数解码器)将q个二进制字解码，以得到q’个编码字，同时，如需要，同时验证所得到的q’个字都是码C₂(或C₁)的字。

按照这种算法构建q个二进制字及其解码是一种有效性很差的操作：所生成的q个字都是码C₂(或C₁)的字，但区别并不太大，在解码器输出处得到述及的不同编码字的数目q’小于所生成的字的数目q。

另外，这种方法只能用于具有代数解码器的码中，代数解码器的实施需要在Gallois体和一个复杂的结构中计算。

Juing Fang 1986年在巴黎ENST的题为“Décodage pondéré descodes linéaires en blocs”的工学博士论文中描述一种关于分组线性码的软输入的解码算法。这种算法是在最大似然性意义上的优化，而不明显地涉及码的代数结构。这可以在输出处提供具有最大似然性的恒定码字，这种算法是关于软输入和恒定输出的多种解码算法中的一种，并没有建议使用表格来生成软输出。

本发明提出一种乘积码的迭代解码方法，可以使解码更快、更有效，且可应用于各种类型的码，而不是只用于具有代数解码器的码。

乘积码的解码并非一个数学问题，而是在传输领域中的一个重要的技术问题，直接应于在传输信道的解调器的输出处对接收到的乘积码的比特或字的值的解码。

详细地说，本发明提出从传输信道接收到的k维和长度为n的分组线性码的一个字( s)的软输入和软输出的解码方法。其步骤有：

-对最大似然的k元组表编码，生成近似接收到的编码字(s)的码的恒定字(u_b)的一个表。

-一方面是对最为接近的生成的编码字的度量，另一方面是对具有第j个相反分量的最为接近的生成的编码字的度量，通过二者之差计算输出的软字的第j个分量。

在一种实施方式中，所有的最似然k元组都是用接收到的字的分量的恒定近似和对可靠性最差的分量的更换来得到的。

相当方便，k元组表中的每个k元组是用下述方法得到：

-通过一个置换(T)，对接收到的编码字的各分量的按可靠性的顺序排队；

-验证由此而得到的字的k个最可靠的分量可生成其它n-k个分量；

-为述及的k个分量中的m个可靠性最差的分量选取恒定值，m为小于k的一个整数。

-作其它k-m个分量的恒定近似；

-通过和述及码的组成相同的一个码及前述的置换的逆置换来对上面得到的恒定字编码。

亦可考虑，用下面的方法进行验证：

-将置换码应用于奇偶校验矩阵的各个列；

-验证这样置换了的奇偶校验矩阵的后n-k个列所构成的矩阵的秩。

-如验证为负数，则在验证的步骤后面接着修正置换的步骤。

在另一种实施方式中，k元组表中的每个k元组是用下面方法得到：

-通过一个置换(T)，按照可靠性的顺序将接收到的编码字的前k个分量排队。

-为可靠性最差的m个分量选取恒定值，m是小于k的一个整数；

-作其它k-m个分量的恒定近似；

-通过述及的置换的逆置换以及通过与述及的码的组成相同的一个码，对上面得到的恒定字进行编码。

最好当不存在一个最为接近的具有与第j个分量相反的分量的生成的编码字时，则输出的软字的第j个分量的计算是通过下述二个度量的差来进行：一方面是对最接近的生成的编码字的度量，另一方面是对最不接近的生成的编码字的度量。

当不存在最为接近的具有与第j个分量相反的分量的生成的编码字时，还可考虑通过为接收到的字的第j个分量加上对于接收到的字最接近的编码字第j个分量符号的一个系数来实现对输出的软字的第j个分量的计算。

相当方便，接收到的字上附加有白的、加性的、高斯型的噪声。

本发明还有一个目的在于对从传输信道接收到的k维和长度为n的分组线性的一个编码字( s)的软输出和软输入的解码方法，其步骤如下。

-在用对一个最似然的k元组表编码所生成接收到的编码字( s)的最接近的码的恒定字( u _b)一个表中选取接收到的字的最接近的编码字。

-对于接收到的字的每个第j个分量(j从1到n变化)，有：

^*用述及的最接近的编码字的第j个分量的相反的量代替接收到的字的第j个分量；

^*从在代替步骤中得到的、对最似然的k元组的一个表格进行编码所生成的编码字的近似码的恒定字的表中选取在代替步骤中得到的字的最接近的编码字；

^*通过下述两个度量之间的差计算输出的软字的第j个分量：一方面是接收到的字的最接近的编码字的度量，另一方面是在代替步骤中得到的字的最接近的编码字的度量。

在一种实施方式中，在接收到的字的最接近的编码字的选择步骤中，最似然的k元组是通过接收到的字的最可靠分量的恒定近似和通过对可靠性最差的分量的更换得到的。

最好，在选择在代替步骤中所得到的字的最接近的编码字的步骤中，所有的最似然k元组都是通过在代替步骤中得到的字的最可靠分量的恒定近似和通过最不可靠分量的更换来得到的。

在一种实施方式中，接收到的字上赋有白的、加性的和高斯型的噪声。

本发明还有一个目的在于对从传输信道上接收到的乘积码的字( R)的一种迭代解码方法。根据这种方法，其中对至少一次迭代，有一个述及的乘积编码字的行的或列的软输入和软输出解码。

在后面作为示例并参照附图的本发明的实施例的描述中将展现出本发明的另外一些特征和优越性。

-图1是在本发明中所实施的一种软输入和软输出解码方法的第一种实施方式的流程方框图。

-图2是在本发明中所实施的一种软输入和软输出解码方法的第二种实施方式的流程方框图。

-图3是在本发明中实施的一种软输入和软输出解码方法的第三种实施方式的流程方框图。

-图4是根据本发明的迭代解码算法的流程方框图。

-图5是迭代次数为4的本发明的解码器的运行示意图；

-图6和图7示出用本发明的方法得到的结果的坐标图。

为了在一种软输入和软输出的解码算法中确定最接近于接收到的软编码字的编码字的集合，本发明建议不使用解码，而使用编码。

图1示出在本发明中实施的软输入和软输出的解码方法的第一种实施方式的流程方框图。图1中示出按接收到的乘积码字的行或列对接收到的一个软字软输出解码所需的各个步骤。

在后面的叙述中，将由传输信道接收的乘积码的软字记作 R＝{r_i，j}，1≤i≤n₁，1≤j≤n₂。这个软字对应于一个乘积码C₂·C₁的二进制字或恒定字在信道上的传输，到达具有噪声的信道解码器。考虑在实数集中的软值的表示，所有的恒定值都对应于±1。在这种表示中，接收到的软值的模量是述及的值的可靠性的指示，而其符号给出接收到的恒定值。

参考图1来描述这个编码字的一行的解码。同种方法在细节上做必要的修改后用于这乘积码的字各列的解码。考察与给定的行相对应的软字 s＝{s_i，1≤i≤n₁}对于给定的j，s_i＝r_i，j。这个字是码C₁(n₁，k₁，d₁)的字伴随以误差的一个模型。这个字包含有由信源编码器提供的k₁个比特，和由码C₁生成的n₁-k₁个冗余比特。为叙述得更简单些，考察码的体系形式，其中k₁个输入分量不变地处在输出的编码字中。

在第一步1中，将接收到的分量s_i的集合按照其模量|s_i|增加的顺序，即按照可靠性的顺序排队，将相应的置换记作T。

在第二步2中，验证s_i在置换中的象(image)T(s_i)的后k₁个分量可以找到剩下的n₁-k₁个分量；这可以用将置换T应用于码C₁的奇偶校验矩阵的各个列来进行，同时验证所得到的置换矩阵的后n₁-k₁个列都是独立的，如果后面n₁-k₁个列的独立性不成立，则修改置换T，使得当用这个转置作用到奇偶校矩阵的各列时得到独立的后面的n₁-k₁个列。这可以用更换第j列(j≤[n₁-k₁+1，n₁]，即用置换(p，n₁-k₁+j)合成T来实现，此处p是小于或等于k₁的整数。在本方法的后面直到第8步，是在这个置换空间用置换了的编码字来操作。

在第三步3中，考察置换了的接收到的字的后k₁个分量中的m个分量(m＜k₁)，例如m个最为不可靠的分量，并用给它们赋予的二进制的值来建立相应的m元组。可以用这种方法生成2^m个二进制的m元组，然而可以仅对生成的这2^m个m元组中的某一些更感兴趣，例如具有最小度量的那一些。

在第四步4中，考察在后k₁个分量中剩下的k₁-m个分量，对这些分量中的每一个进行恒定判定，就是说，给这每个软分量一个恒定值或二进制值。例如可以简单地对每个分量赋予符号。

在第五步5中，从第三步和第四步所得到的结果出发构建二进制字的集合t_b＝{t_i，1≤i≤k₁}_b，(b≤2^m)。换言之，在第5步中所得到的每个字都是在第三步中所建立的m个分量与在第四步中所得到的k₁-m个分量的集合或并置。将在置换了的字空间中和编码C₁对应的编码应用于前述分量上。

这种编码的一种方法是使用码C₁的奇偶校验矩阵H。将与各分量排队相联系的置换T应用于述及的码的奇偶校验矩阵H，然后将Gauss压缩作用于用表格T置换的矩阵H的最右边的(n₁-k₁)个列，以使将之置于系统的形式。需要指出，一般说，置换了的矩阵H的后n₁-k₁列并非独立的。在这种情况下，可以修改置换T，以使这些列都是独立的，且这还能使置换了的矩阵H系统化。第二步的验证可以和置换了的矩阵的系统化同时进行。然后相当方便地使用已经系统化的这个奇偶校验矩阵来在置换空间中进行编码。

这样就直接得到相应码的置换恒定字 u _b＝{u_i，1≤i≤n₁}_b，它与传输信道上发送的字的置换的模型的最初近似。

然后在第六步6中，可以对得到的每个编码字 u _b计算与接收的软编码字s_i间的欧几里得距离。可以在这一步中只保留这些编码字中的那些可靠性最大的字，考察刚刚计算的欧几里得距离来量度可靠性是相当容易的。用来保持编码字，或者还保留考察的编码字的数目的阈值，决定于在前面各步中所生成的编码字的总数。换言之，生成的编码字越多，能够保留的编码字的数目也越大。一方面生成大数量编码字产生了复杂性，另一方面生成编码字的总数增加时有找到很可靠的编码字的可能性增加这方面的好处，由这二者间之折衷来选取保留编码字的数量。

在步7中，用下面的方法进行软解码。对于给定序号为j的接收到的给定的分量s_j，在得到的编码字 u _b的集合中考察最接近的编码字u⁺ _j和最接近的编码字 u ^- _j， u ⁺ _j将次序为j的分量表示成等于1的一个比特， u ^- _j将序号为j的分量表示成等于-1的一个比特；就计算已解码的软字的第j个分量的值，如处于第j个位置的表征为-1的一个比特的最接近的编码字 u ^- _j的度量c_j-＝| u ^- _j- s|与处在第j个位置的表征为+1的一个比特的最接近的字 u ⁺ _j的度量c_j＝| u ⁺ _j- s|之差乘以一个归一化因子1/4。换言之，对于每个值j，计算由解码器提供的软编码字{v_i，|1≤i≤n₁}的序号为j的分量v_j，为

v_j＝(C^- _j-C⁺ _j)/4

可能根据第5步所生成的字数和在第6步所保留的字数不能在生成的编码字集中找到处在第j个位置上的表征相反比特值的两个编码字，这可能是在如序号为j的分量是以很大的可靠性接收的情况下，亦可是在如生成的或保留的编码字的数量太少的情况下。于是可将最不可靠度量-最接近接收到编码字的表中的字的度量-与最可靠度量-距接收到的编码字的最远的表中的字的度量之差作为第j个分量的软值。在这种情况下，找到两个度量中的一个的准确值，另一个度量值为近似值，或者取表中最远的编码字的度量，视作度量值的下沿。

在这种情况下，还总是可以将接收到的字的第j个分量与一个因子b的和作为第j个分量的软值，b用作最接近编码字的第j个分量的恒定判定符号；换言之，如最接近的编码字的第j个分量是正的，则加一因子b；而如最接近的编码字的第j个分量是负的，则加一因子-b；这个因子的值可根据迭代而变化。

然后可以用和步骤2中的置换相反的置换再回到接收到的字空间中去，就找到附加有每个符号的可靠性系数，即一个加权输出，的接收字的最接近编码字。

现在对步骤7中的计算作以说明。考察在白的、高斯的和加性的噪声 b情况下，噪声的各分量b_i的平均值均为零，相同的方差s²，于是可写作

s＝ e+ b这里 s如上面所说为接收到的字， e＝(e_i，1≤i≤n₁)是发射的编码字，并有e _i＝±1，b＝(b_i，1≤i≤n₁)。在这种情况下，与已解码字的每个符号c_i相关的可靠性的测量可以由似然性比的对数来确定。述及的似然性系数比的对数的定义为

L(c_i)＝log[Pr(c_i＝1/ s)/Pr(c_i＝-1/ s)]

在这种情况下，使用Bayes准则，并考虑到噪声是白的和高斯型的，可以证明，与符号c_i相关的似然性比等于

此处s_1，j和s_-1，j是编码字的两个集合，其中第j个符号分别等于+1或者-1，M( s， u)是由算法寻找的编码字 u和接收到的字 s间的度量，在我们的情况下的度量是接收到的字 s与一个编码字 u之间的欧几里得距离，欧几里得距离可以是有限精度的。如需要，这种度量可以适用于衰落信道的情况下。

因为通常编码字的数目很大，似然性比的计算就相对很复杂。当信噪比足够大时，可以只保留分子和分母中的较为大的项而将这个式子简化，于是似然性比的对数的表达式变成：

用因子

将似然性比的对数归一化，则第j个符号v_j的加权输出则用下面的方式表示 $v_j=\frac{1}{4}(\underset{{\underset{-}{u}}^{-}\∈S_{*i,j}}{\mathrm{Max}}M(\underset{-}{s},{\underset{-}{u}}^{-})-\underset{{\underset{-}{u}}^{+}\∈S_{i,j}}{\mathrm{Max}}M(\underset{-}{s},{\underset{-}{u}}^{+}))$

此处，S_ij表示在位置j处具有一个符号等于i(i＝±1)的编码字的集合。对于c_j-和c_j+仍取前面的记号，则在图1的第7步中可以找到表达式： $v_j=\frac{1}{4}(C_{j-}-C_{j+})$

参照图1描述的各个步骤可以生成接近于在传输信道上接收到的软字的编码字。图1的方法可以用找寻编码字的一个表格来从中推断出接收到的编码字的每个分量的软值。本方法的复杂性决定于在第4步中生成的编码字的数目，换言之，决定于生成的接近的编码字的个数。这个数目越大，本方法的性能就越好，然而实施也就越复杂，这个数目越小，则本方法的性能也越好，且效用也越差。编码字的数目的选取决定本方法的性能/复杂性比，要根据情况来确定。在实际中，对于一个扩展的BCH(31，21)码，从生成的50个字中保留19个最好的编码字就可以得到满意的结果。

将步骤2变化，更换的可以不是可靠性最差的那些分量，而是在组合中可靠性最差的那些分量。这样例如考察下面的各个分量及其相应的模量：

I1	I2	I3	I4	I5	I6
						0.1	0.2	0.3	0.35	0.4	0.45

例如先更换I₁，而后I₂，而后I₃，而后I₁和I₂，而后I₄，而后I₁和I₃，而后I₅，如此顺序。这样就达到了保留可靠性最差的那些分量。

图2示出在本发明中实施的软输入和软输出的解码方法的第二种实施方式的流程方框图。作为例子，在图2中，重新只考察一个行。重新参照码的系统化形式来描述本发明。考察和给定的行{s_i，1≤i≤n₁}(s_i＝r_i，j，j已知)对应的软字。这个字是码C₁(n₁，k₁，d₁)的一个字具有误差的形式。这个字包括由信源编码器所提供的k₁个比特和码C₁所生成的n₁-k₁个冗余比特。

在第一步11中，将接收到的前k₁个分量s_i按模|s_i|的增加顺序排队，即按可靠性排队。将相应的置换记作T。

在第二步12中，按照Chase算法进行，对于m个可靠性最差的分量建立恒定矢量，m＜k₁。用这种方法可以生成2^m个m元组，然而只对这2^m个m元组中的某一些，例如具有最小欧几里得度量的那些感兴趣。在k₁＝4和m＝2的情况下，所生成的所有矢量例如为00、10、01、11。

在第三步13中，考察全部k₁-m个剩下的分量，并对这每一个分量进行一个恒定判定，即对每个软分量赋予一个恒定值或二进制值。例如可以简单地赋予序号为j的分量s_j其符号值(s_j)。

在步骤14中，从步骤12和步骤13的结果出发，用在步骤12中所得到的m个分量与在步骤13中得到的k₁-m个分量的并置，重新构建二进制字的集合t_b＝{t_i，1≤i≤k₁}_b，此处b≤2^m。将编码C₁·T^-1作用于这些恒定字，此处T^-1是步骤1中的置换T的逆置换。这就直接得到码C₁的恒定字 u _b＝{u_i，1≤i≤n₁}_b，它近似于在信道上发送的字。

然后，在步骤15中，可以对每个得到的编码字 u _b计算对接收到的软编码字s_i的欧几里得距离，或者每个编码字 u _b相对于接收到的编码字s的度量。在这一步骤中可以象在前面参考图1的第6步所说的那样，只保留这些编码字中的那些可靠性最好的那些字。

在步骤16中，用在图1中的步骤7中的相同方法进行软解码。

和图1的方法相比，图2的方法可以免除校验奇偶校验矩阵的后面一些列的独立性这个步骤。和图1的方法相比，图2的方法具有弊端，即只修改前k₁个分量中的一些分量，而不是编码字的各分量的集合中的一些分量。换句话说，图1的方法可以修改的可靠性差的分量不仅是选自发送的信息，还从冗余的值中选取。这就更换编码字的分量集合中的k₁个可靠性最好的分量中的可靠性最差的那些分量，而不仅是发送字的前k₁个分量中的可靠性最差的那些分量。

图3示出在本发明中实施的一种软输入和软输出解码方法的第三种实施方式的流程方框图。在这个实施方式中按照图1中的前五步进行来获得编码字的一个表格及编码字的度量，这在图3中用步骤20来表示。在步骤21中考察最接近的编码字 c ^*，即具有最小度量的字，并将当前值j初始化作1。

在步骤22中，将接收到的编码字 s的第j个分量s_j的值更换，给它的一个值是在第21步中确定的编码字 c ^*的第j个分量的值的相反的值。且此编码字具有很大的可靠性。

在步骤23中，和在图1的前五步中一样，寻求在第j个分量中已修改过的接收到的字的接近的编码字的一个表格，并计算它的度量。

在步骤24中，考察具有最小度量的编码字 c ^’*； c ^’*的序号为j的分量和在21步中确定的编码字 c ^*的序号为j的分量相反，于是就计算输出的软字 v的序号为j的分量v_j，是在步骤21和步骤24中的字 c ^*和 c ^’*的度量之差再乘以归一化因子1/4。

在步骤25中，比较j和n，如j＝n，则结束解码，到步骤26；否则到步骤27，将j增加1再回到步骤22。

和图1和图2的方法相比，图3的方法在对于每个分量，需要寻求两个对这个分量有相反的比特值的两个编码字这个方面，给出最好的结果。然而，这个方法最为复杂，计算接近字的表格应是n₁+1遍，而不是只有一遍。

于是，图1至3的这些方法对于从传输信道接收到的乘积码的字的每个行或每个列提供一个软输出。本发明的解码方法为了迭代解码而使用这种软解码，像参照图4所说的迭代解码，图4示出这种迭代解码的一种实施方式。在一个迭代中使用从图1到图3中一个的方法或者是用这些方法的组合，从当前矩阵的各行和相应的各列出发而得到对于下面迭代的一些行和一些列。

在第一步30中，将通常的矩阵 R _i初始化作从信道上接收到的值 R，将脚码i的值初始化作0，然后进行到步骤32。

在步骤32中，对i的每一个值确定系数a_i。因而各系数构成一个实数递增序列(a_i)。作为例子，对于一个扩展BCH(31，21)乘积码，给出这些系数的值，参见图6。

然后继续到步骤34。

使用图1至3的这种或那种软输入和软输出的解码算法沿着矩阵的各行R_i进行的第一遍解码可以确定一个新的矩阵 L _i，其中每一行都是码C₁的一个字。然后继续到步骤36。

在步骤36中，将i递增1，从矩阵 L _i-1中提取本征信息，等于( L _i-1-R_i-1)，并用因子a_i加权，和接收矩阵 R相加，在继续到步骤38之前，计算一个新的矩阵 R _i＝ R+a_i( L _i-1-R_i-1)。

在步骤38中，接着使用图1至图3中的这种或那种软输入和软输出的解码算法。这种解码可以得到一个矩阵 L _i，其每一行是码C₂的一个字。步骤38对应于步骤34，在此是对于列。然后继续到步骤40。

步骤40对应于步骤36。这一步在于将i递增1，并构成一个新的矩阵 R _i＝R+a_i( L _i-1-R_i-1)。

在步骤42中将迭代次数与希望的迭代次数相比较，迭代次数等于i/2。这里指出，将包括行的解码和列的解码的整体称作迭代。假如必须进行附加的迭代，则继续到步骤34。否则继续到步骤46。

在步骤46中，对在步骤38中用对列的解码得到的矩阵 L _i-1作二进制判定。假定这样得到的矩阵对应于发射的编码字，于是只需为寻求各信息比特而提取信息子矩阵。

图5示出迭代次数等于4的解码器的运行。

本发明应用于各种类型的线性分组码中，如BCH码，包括Reed-Solomon码、Reed-Muller码、QR码、循环码等等，而不使用代数解码器和在Gallois有限体中的复杂的计算。

图6和7示出根据本发明的解码的结果。图6示出根据参照图4和图1描述的方法对扩展的BCH(31，21)乘积码解码的结果。图的纵坐标示出比特的误码率，横坐标示出信噪比Eb/No，以dB为单位。在图中所示出的结果是用限制长度(longueur de contrainte)为7的1/2卷积码(le code convolutif)，是在用本发明的解码迭代一次、二次、三次或四次以后得到的。

对于图6的模拟，计算了(图1的步骤5)J＝50个编码字，每次迭代都保留Q＝19个最好的。对于各行或各列所使用的系数(a_i)在下面表中给出：

a1	a2	a3	a4	a5	a6	a7	a8
								0.0	0.3	0.5	0.7	0.9	1	1	1

在找不到共存的编码字的情况下，使用下面的系数(b_i)

b1	b2	b3	b4	b5	b6	b7	b8
								0.2	0.3	0.6	0.8	1	1	1	1

图中示出在2dB附近处相对于1/2码的编码增益，TEB为10^-6。

图7示出对于乘积码BCH(30，19)×BCH(30，24)的相应的结果。码BCH(30，19)是从扩展的BCH(31，21)码缩短2倍得到的码。码BCH(30，24)是从扩展的BCH码(31，26)缩短2倍得到的码。相对于相同的参考码的编码增益大于2。

在本发明的所有的实施方式中，根据本发明的乘积码的迭代解码提供的性能较使用相同的迭代次数的FR-A-2712 760所提出的算法所提供的性能为好。

然而，本发明并不限于已经描述的和示出的实施例和实施方式中，亦可适用于技术人员可得到的各个变种中。这样，本发明的描述是参照一个乘积码C₁·C₂，但亦可用于其它形式的码，例如分组的三码乘积码或更多个码乘积码，亦可应于前面说过的专利申请号为n⁰9712594的专利中。这些乘积码是在异步传输方式(ATM)中分组传输编码(codage despaquets en transmission)的一种特殊应用：使用用于分组体(le corp dupaquet)的不同于码C₂的码C₁进行标题编码(codage des en-tête)，然后将码c₃作用于矩阵由C₁和C₂的编码字所构成每一行。

同样，可以将图1至3的方法用于不同于图4的其它的迭代解码算法。

还需明白，接收到的乘积码字的术语“行”或“列”的表述的使用仅仅是为了说明的方便，也需明白，在信道上接收到的值并非都是矩阵形式。可以不区分解码是从行开始还是从列开始。因此将“从传输信道的输出处接收到的一个乘积码的字”这句话可以扩展为从传输信道输出处接收到的相继的值或扩展为带有噪声的二进制值的一个序列。

另外，本发明的描述是参照系统化分组的码。本发明对于涉及到第一种和第三种实施方式，可用并非系统化形式的码C(n，k，d)，而通过乘以一个秩为k的矩阵可以方便地变成系统化形式。本发明的描述是参照二进制码做例子，但亦可用于q进制码，q≠2。

Claims (14)

1.一种对从传输信道上接收到的长度为n的k维分组线性码的一个字的软输入和软输出的解码方法，其步骤是：

对似然性最好的k元组的一个表格编码，生成接收到的编码字( s)的近似码的恒定字( u _b)的一个表格；

用下述两个度量之差计算输出的软字的第j个分量：一个是对最接近生成的编码字的度量；另一个是对具有相反的第j个分量的最接近生成的编码字的度量。

2.根据权利要求1的方法，其特征在于各似然性最好的k元组都是用对接收到的字的各分量做恒定近似和用对可靠性最差的各分量更换来得到的。

3.根据权利要求1或2的方法，其中的k元组表中的每个k元组是用下法得到：

按照一个置换(T)，将接收到的编码字的各分量按可靠性大小的顺序排队；

验证这样得到的字的可靠性最好的k个分量可以生成另外n-k个分量；

为述及的k个分量中的可靠性最差的m个分量选取恒定值，m是一个小于k的整数；

做其余k-m个分量的恒定近似；

用等于述及的码的组成的一个码，用前述置换的逆置换对这样得到的恒定字编码。

4.根据权利要求3的方法，其中的验证是用下述的步骤进行的：

将置换的码应用于奇偶校验矩阵的各列；

验证这样置换了的奇偶校验矩阵的后n-k列的恒定矩阵的秩(rang)。

5.根据权利要求3或4的方法，在其中的验证步骤中，如奇偶校验矩阵为负，则在验证步骤后面跟着修改置换的一步。

6.根据权利要求1或2的方法，其中k元组表中的每个k元组是用下列步骤得到：

通过置换(T)，按接收到的编码字的前k个分量的可靠性的顺序排队；

为m个可靠性最差的分量选取恒定值，m是一个小于k的整数；

对其余k-m个分量做恒定近似；

用等于述及的码的组成的一个码，用述及的置换的逆置换对上面得到的恒定字编码。

7.根据权利要求1至6中任一项的方法，其特征在于当具有与第j个分量相反的分量的最接近的生成的编码字不存在时，输出的软字的第j个分量是用下述两个度量差来计算的：一方面是对最接近生成的编码字的度量，另一方面是对最不接近生成的编码字的度量。

8.根据权利要求1至6中任一项的方法，其特征在于当具有与第j个分量相反的分量的最接近生成的编码字不存在时，输出的软字的第j个分量是用接收到的字的第j个分量加上带有接收到的最接近编码字的第j个分量的恒定判定的符号的一个系数而实现的。

9.根据前面各权利要求中之一的方法，其特征在于接收到的字带有白的、加性的和高斯型的噪声。

10.一种从传输信道上接收到的长度为n的k维分组线性码的一个字(s)的软输入和软输出解码方法，其步骤是：

-从对最似然的k元组表格编码生成的接收到的编码字(s)的近似码的恒定字( u _b)表中选取述及的接收到的字的最接近的编码字，

-对于述及的接收到的字的序号为j的每个分量(j在1至n间变化)，有：

^*用最接近的述及的编码字的第j个分量的逆分量来代替接收到的字的第j个分量；

^*从对最似然的k元组表编码所生成的、在代替步骤中得到的编码字的最接近的恒定字的一个表中选取在代替步骤中得到的字的最接近的编码字；

^*用下述两个度量之差计算输出的软字的第j个分量：一方面是对接收到的字的最接近的编码字的度量，而另一方面是对在代替步骤中得到的字的最接近的编码字的度量。

11.根据权利要求10的方法，其特征在于在选取接收字的最接近编码字的步骤中，所有的最似然的k元组都是用对接收到的字的可靠性最好的分量的恒定近似和用对可靠性最差的分量做更换来得到的。

12.根据权利要求10或11的方法，其特征在于，在对在代替步骤中得到的字的最接近的编码字的选取步骤中，所有的最似然的k元组都是用对在代替步骤中得到的字的最可靠的分量的恒定近似和用对最不可靠的分量更换来得到的。

13.根据权利要求10至12中任一项的方法，其特征在于接收到的字带有白的、加性的、高斯型的噪声。

14.一种从信道上接收到的一个乘积码的一个字( R)的迭代解码方法中，包括对于至少一次迭代的根据权利要求1至13中任一项的，乘积码的述及的字的行或列的软输入和软输出解码。

Images