CN1655462A

CN1655462A - 改进的迭代n维解码

Info

Publication number: CN1655462A
Application number: CN200410101781.XA
Authority: CN
Inventors: S·古奇; S·里纳尔迪; G·马凯达
Original assignee: Alcatel NV
Current assignee: Alcatel Lucent NV
Priority date: 2004-02-13
Filing date: 2004-12-22
Publication date: 2005-08-17
Anticipated expiration: 2024-12-22
Also published as: EP1569348A1; US7840867B2; CN100525117C; US20050182998A1

Abstract

公布了一种用于实现包括数据比特帧的数据结构的迭代n维解码的方法，所述方法包括步骤：接收可能错误的数据；在单个步骤中在所有的n个维中计算校正子；存储第一被计算的校正子；在第一维中处理校正子；纠正错误；以及更新已被在所述第一维中的纠正所影响的校正子；并且在直至第n维的所有可能的维中处理校正子，并且，为被处理的校正子的每一个纠正错误，并在所有的维中更新已被该纠正所影响的校正子。每次子迭代(从第二次子迭代起)所需要的时间将被逐渐减少。增加迭代的次数而不增加延迟和处理的复杂度。由于仅一个电路被用于在所有的维中以及为所有的迭代处理校正子，因此处理的复杂度也被减小。

Description

改进的迭代n维解码

技术领域

本发明涉及电信领域，并且特别涉及错误纠正的技术，所述错误可能在信号传输的过程中产生。更特别地说，本发明涉及一种改进的迭代n维FEC解码器和一种改进的用于解码信号的方法。

背景技术

如同已知的那样，前向纠错(FEC)是一种使用预定算法、将冗余与被传输的数据一起传送的技术。接收设备具有根据所述冗余来检测和纠正可能在传输期间所产生的多个比特错误的能力。与FEC一起被传送的信号因而更加“健壮(robust)”，这样允许运营商建立较长距离的连接而无需部署许多中继站。

换句话说，为了克服传输差错和分组丢失，许多电信系统使用了前向纠错(FEC)。一般来说，FEC机制所传送的额外的数据可被用于在接收端重建任何被损坏的或丢失的分组。例如，FEC已被应用于CD-ROM来补偿划痕，并且由于广播仅是单向的(即接收机不能够请求重发)，所述FEC还被用于卫星和外层空间传送。

一种已知的用于实现n维编码的解码的方法在于首先沿着第一维解码，然后沿着第二维，然后沿着第三维直至第n维。而且，为了改进错误纠正的能力，可以进行类似于上述的方法(即在第一、第二、第三、......、第n维中解码)的许多次迭代。每次迭代导致延迟或等待时间。

在某一维中解码的步骤还包括：计算校正子(syndrome)，计算错误位置和错误值；以及最后在该维中进行纠正。

所述操作沿着所述n个维被迭代。被计算的校正子的处理允许确定所出现的错误的数目及其所处位置。

换句话说，所述被计算的校正子提供能够从中得到错误的位置及其值的信息。

错误位置的计算步骤通常通过在所有可能的点(位置，钱氏搜索(CHIEN search))验证方程而被执行。一种更好的可供选择的方法在于用封闭解法进行计算。

已知的解决方案导致两个主要的缺点。第一个缺点是长延迟，其取决于为纠正错误所进行的迭代次数。如上所述，要提高错误的可纠正性，必须执行每单次迭代都导致延迟的许多次迭代。这意味着，为了提高解码器的净编码增益，必须增加迭代的次数从而增加延迟。第二个缺点是由解码器的复杂度引起的。实际上，在每个解码步骤都需要重新计算所有的校正子，所述解码步骤被认为是与其它步骤无关的单次子迭代。

发明内容

考虑到上述问题和缺点，本发明主要的目的是提供一种FEC解码器结构和解码方法，使得在进行比已知的解码器更多次数的迭代的同时减少延迟。

本发明的另一个目的是提供一种不及所述已知的解码器和方法复杂的FEC解码器结构和解码方法。

所述以及其它目的由根据权利要求1的解码器和根据权利要求13的方法来达到。本发明的其它有利特征在各从属权利要求中被阐明。所有的权利要求应当被看作是本说明书的完整部分。

本发明是基于这样的事实：作为可由达到第四级等式的封闭方程式所解的代数编码，对于每个维都由级别≤4的代数编码来保护的n维编码而言，可以利用一种使用封闭解法计算错误值及其位置的创新的解码计算结构。所述新的计算结构不需要在每个解码步骤计算所有的校正子(在所有维中)。根据本发明，所有维中的所有校正子在开始时、解码步骤之前、基本上同时有利地被计算一次。

之后，在解码步骤期间，当比特被纠正时，所有被该纠正所影响的校正子被更新。后文将对所述解码步骤进行更深入地描述。

此外，本发明的另一个特征是从第二次迭代直至第n次迭代不处理所有的校正子，而是仅处理值不为零的校正子或者已经在前面的解码步骤期间被更新的校正子。

这样，每次子迭代(从第二次子迭代起)需要的时间将被逐渐减少。

因此，本发明有利地允许增加迭代的次数而不增加延迟和处理的复杂度。

由于仅一个电路被用于在所有的维中以及为所有的迭代处理校正子，因此处理的复杂度也被降低。

根据第一方面，本发明提供一种用于实现包括数据比特帧的数据结构的迭代n维解码的解码器，所述解码器包括：校正子计算器，用于在单个步骤中在所有n个维中计算校正子；校正子处理器，用于在1、2、...n维中处理校正子，所述校正子处理器包括用于存储校正子的存储装置；以及数据处理器，用于存储被接收的数据、根据来自所述校正子处理器的信息纠正数据并输出被纠正的数据。

所述校正子处理器通常为1、2、...、m次迭代处理校正子。

根据优选的实施例，所述校正子处理器包括响应所述校正子存储装置的错误计算器，所述错误计算器用于计算错误，并且将错误值和错误位置提供给所述数据处理器，并纠正被存储的数据的可能的错误。

此外，所述错误计算器与所述校正子处理器中新的校正子的计算器配合工作来计算新的校正子，所述新的校正子已经被在一个维中的前面的纠正改变，所述新的校正子是为所有维被计算的。

有利地，所述新的校正子计算器的输出被提供给所述校正子存储装置，用于更新被存储在其中的校正子。

可选地，所述校正子处理器还包括用于在预置的时间间隔内管理许多校正子纠正迭代的序列发生器，所述序列发生器与所述错误计算器和所述校正子存储装置配合工作。

典型地，所述校正子处理器包括校正子复用器，其用于在所述校正子计算器的输出和所述新的校正子的计算器的输出之间进行切换。

有利地，所述数据处理器包括第一存储器和第二存储器，以及在所述第一或第二存储器之间进行切换的输出复用器。

典型地，每个存储器关联于数据复用器，所述数据复用器在输入数据和所述校正子处理器的输出之间进行切换。

可能地，如果必要，消除FEC解码器块可以被提供用于进行剩余错误的纠正。

根据优选的和有利的实施例，所述解码器在两个维中操作。

有利地，所述解码器被体现在专用集成电路，ASIC中。

根据第二方面，本发明提供一种用于实现包括数据比特帧的数据结构的迭代n维解码的方法，所述方法包括下列步骤：

接收可能错误的数据；

在单个步骤中，在所有的n个维中计算校正子；

存储第一被计算的校正子；

在第一维中处理校正子；纠正错误；更新已被在所述第一维中的纠正所影响的校正子；

在直至第n维的所有可能的维中处理校正子，并且，为被处理的校正子的每一个纠正错误，并在所有的维中更新已被该纠正影响的校正子；

执行迭代过程直至设定时间帧(set time frame)的末尾，所述迭代过程包括下列步骤：

在第一维中处理不为零的校正子；纠正错误；更新已被在所述第一维中的纠正所影响的校正子；

在直至第n维的所有可能的维中处理不为零的校正子，或已经在前面的步骤期间被更新的校正子，并且，为被处理的校正子的每一个纠正错误，并在所有的维中更新已被该纠正影响的校正子，并且

输出被纠正的数据。

可能地，如果必要，进行消除FEC解码步骤来纠正剩余错误。

优选地，n等于2。

有利地，所述方法通过专用集成电路，ASIC来实现。

根据第三方面，本发明还提供一种包括如上文所述的解码器的电信设备，典型地是一种网络单元。

根据第四方面，本发明还提供一种包括计算机程序装置的计算机程序，当所述程序在计算机上运行时，所述计算机程序装置适于实现如上文所述的方法。

根据第五方面，本发明提供一种计算机可读介质，其具有被记录在其上的程序，所述计算机可读介质包括计算机程序代码装置，当所述程序在计算机上运行时，所述计算机程序代码装置适于实现如上文所述的方法。

附图说明

参考附图，读过下面通过仅示例性而非限制性的方式给出的详细描述后，本发明将会变得完全地显而易见，其中：

-图1概略地示出了用于实现二维编码的解码的已知方法；

-图2详细地示出了单次迭代；

-图3示出了根据本发明的解码器的实施例；并且

-图4示出了在二维情况下，根据本发明的方法的步骤。

具体实施方式

在开始对本发明进行描述之前，将给出校正子的定义。令C为在F＝GF(q)上的线性(n，k，d)码并令H为C的(n-k×n)奇偶校验矩阵，以使对于每个c∈Fⁿ，c∈CHc^T。字y∈Fⁿ的校正子(关于H)由S＝Hy^T定义。C的码字正好是校正子为0的Fⁿ的向量。

如上所述，一种已知的用于实现n维编码的解码的方法在于首先沿着第一维解码，然后沿着第二维，然后沿着第三维直至第n维。而且，为了改进错误纠正的能力，一般执行类似于上述的方法(即在第一、第二、第三、......、第n维中解码)的许多次(m)迭代。m次迭代的每一次导致延迟或等待时间。图1和图2示出了对于二维情况(n＝2)的所述已知的方法。迭代的每一次包括首先沿第一维(DEFEC_1)然后沿第二维(DEFEC_2)解码的子迭代步骤。子迭代步骤的每一个还包括计算编码校正子(SYND_COMP)、计算错误(ERR_CALC)和纠正错误(ERR_CORR)的步骤。

不同地，根据本发明，校正子仅在解码开始时被计算。然后，仅仅当比特被纠正时，才只需要更新和被纠正的比特相关的校正子(在所有的维中)。此外，本发明允许增加迭代的次数而不增加延迟和处理的复杂度。

所述想法为，从第二次迭代直至第n次迭代，不必处理所有的校正子，而是仅处理值不为零的校正子或者已经在前面的步骤期间被更新的校正子。这样，每次子迭代需要的时间就被减小了。

在考虑二维编码时，根据本发明的计算结构可由下列步骤加以概述。

-仅在解码的开始计算所有的校正子。

-在适当的RAM存储器中存储所述校正子。

-沿第一维处理所述校正子。所述步骤不但意味着错误计算及其随后的纠正，还意味着重新计算仅仅是涉及被纠正的比特的校正子。实际上，不得不考虑到如果错误的比特在数据中被纠正，就必须在所有的维中(在所述二维的情况下为两个维)重新计算相关的校正子。所述新的校正子不得不替换在上述RAM中的先前的校正子。

-沿第二维处理校正子。所述步骤基本上如同上文所描述的步骤。

-沿第一维处理校正子。

-沿第二维等处理校正子，直至专用于校正子处理的时间结束。

显然，由于必须在每次子迭代在所有的维中更新与被纠正的比特相关的校正子，解码步骤并不独立。

迭代的次数取决于单次子迭代需要的时间，从而取决于专用于校正子处理的时间。为此，本发明还描绘了如何减少除第一次迭代之外(在所述情况下必须考虑每个校正子)的单次子迭代需要的时间。实际上，从第二次迭代直至第n次迭代，在每次子迭代，仅处理值不为零的校正子或者已经在前面的步骤期间被更新的校正子。这样，可以在固定的时间内进行取决于错误的数目与位置的许多次迭代。

相反地，在已知的解码结构的情况下(见图1和2)，由于每次子迭代在所需要的时间方面与前一次的迭代相同，因而迭代的次数是固定的。

图3、图4中概略地示出的根据本发明的一种可能的解码器结构说明了所述方法的各个不同的步骤。虽然如图3的解码器能解码被n维编码(n＝1、2、3、...)保护的数据，但下面的描述(也见图4的框图)是特别参考二维编码被给出的，其中n＝2。

步骤100：比特帧形式的数据在输入(DATA_IN)被接收。步骤101：所述被接收的数据被提供给(1)块SYND_COMP来为所使用的编码的所有n个维计算编码校正子，并且所述被接收的数据还被发送(2、3)到数据处理器DATA_PROC。所述被计算的校正子被提供给(4)校正子处理器SYND_PROC。在所述校正子处理器中，被计算的校正子被存储(步骤102)在优选地为随机存储器的存储器SYND_RAM中。当然，所述SYND_RAM存储器包括用于n个维的所有校正子的许多个存储器。所述校正子由错误计算器ERR_CALC处理。有利地，所述ERR_CALC以封闭解法计算错误的位置与值。

在第一阶段(步骤103)中，沿着两个维中的第一维处理校正子，例如沿着水平维。所述错误计算器ERR_CALC产生关于错误值和错误位置的信息，所述信息通过11被提供到所述数据处理器来纠正数据。根据关于沿着第一维的错误值和错误位置的信息，被沿着第一维的纠正所改变的沿着两个维的校正子被更新。

在第二阶段(步骤104)中，沿着第二维处理校正子，例如沿着编码的垂直维或对角维。所述错误计算器ERR_CALC产生关于错误值和错误位置的信息，所述信息通过11被提供到所述数据处理器来纠正数据。根据关于沿着第二维的错误值和错误位置的信息，被沿着第二维的纠正所改变的沿着两个维的校正子被更新。

在第三阶段(步骤105)中，再次沿着第一维处理校正子。再一次地，根据本发明，仅处理已经在前面的步骤期间被更新的以及值不为零的校正子。所述错误计算器ERR_CALC产生关于可能地剩余错误的值和错误的位置的信息，所述信息通过11被提供到所述数据处理器来纠正数据。根据关于沿着第一维的剩余错误的值和错误的位置的信息，被沿着第一维的纠正所改变的沿着两个维的校正子被更新。

在第四阶段(步骤106)中，再次沿着第二维处理校正子。再一次地，根据本发明，仅处理已经在前面的步骤期间被更新的以及值不为零的校正子。所述错误计算器ERR_CALC产生关于可能地剩余错误的值和错误的位置的信息，所述信息通过11被提供到所述数据处理器来纠正数据。根据关于沿着第二维的剩余错误的值和错误的位置的信息，被沿着第二维的纠正所改变的沿着两个维的校正子被更新。

解码将以迭代处理继续进行，其中上述第三和第四阶段被重复直至固定时间结束(块107)。明显地，每次迭代的时间将被反复地减少。

所述校正子处理器还包括管理校正子处理的顺序的序列发生器SEQ_CER。所述序列发生器与所述错误计算器和存储校正子的所述存储器配合工作。

有利地，所述校正子处理器还包括校正子复用器SYND_MUX，其用于在所述校正子计算器SYND_COMP和新校正子的计算器N_SYND_COMP之间进行切换。

有利地，所述数据处理器DATA_PROC包括两个存储器DATA_RAM_A和DATA_RAM_B，所述两个存储器通过连线14和15被连接到各自的数据复用器MUX_DATA_A、MUX_DATA_B。所述数据复用器的每一个在数据输入和所述校正子处理器的输出之间进行切换。最后，输出复用器MUX_OUT选择两个存储器的输出16和17的其中一个。所述存储器优选地为随机存储器。根据下面的描述，存储器的数目为2的原因将变得显而易见。

在图3中，ABIL_CORR_A表示选择器。当ABIL_CORR_A被设置为1，错误在被存储在DATA_RAM_A中的数据中被纠正，新的数据DATA_IN被写入DATA_RAM_B，并且来自DATA_RAM_B的数据被发送到输出DATA_OUT。

已经清楚了本发明的操作，将按照时间间隔Δt₁、Δt₂、Δt₃、Δt₄...，进一步地解释t，其中每个时间间隔等于编码帧。Δt是专用于处理的固定时间。可被进行的迭代的次数取决于每次子迭代占用的逐渐减少的时间。

在Δt₁内：输入数据(DATA_IN)被存储在DATA_RAM_A中；所述SYND_COMP计算目前被存储在DATA_RAM_A中的数据(DATA_IN_A)的所有n个校正子。

在Δt₂内：输入数据(DATA_IN)被存储在DATA_RAM_B中；所述SYND_COMP计算目前被存储在DATA_RAM_B中的数据(DATA_IN_B)的所有n个校正子。而且，发生所述校正子的处理和目前被存储在所述DATA_RAM_A中的数据的纠正。

在Δt₃内：在前面的时间间隔(Δt₂)期间被纠正的数据从DATA_RAM_A被输出；新的数据可被存储在DATA_RAM_A中；所述SYND_COMP计算目前被存储在所述DATA_RAM_A中的新数据的所有n个校正子。而且，发生所述校正子的处理和目前被存储在所述DATA_RAM_B中的数据的纠正。

在Δt₄内，在前面的时间间隔(Δt₃)期间被纠正的数据从DATA_RAM_B被输出；新的数据可被存储在DATA_RAM_B中；所述SYND_COMP计算目前被存储在DATA_RAM_B中的新数据的所有n个校正子。而且，发生所述校正子的处理和目前被存储在所述DATA_RAM_A中的数据的纠正。

下一段时间间隔将如同Δt₃和Δt₄。因此，在数据输入和数据输出之间的延迟将等于两个编码帧。在现有技术中，所述延迟是由迭代的次数(m)乘以编码帧的长度来给出的。

从而示出和描述了一种新的解码器和一种新的方法，其实现了所寻求的所有目的与优点。但是，在考虑到公布了其优选实施例的说明书和附图之后，本发明的许多改变、修改、变化以及其它的使用和应用对于本领域的技术人员来说将变得明显。所有不脱离本发明范围的所述改变、修改、变化以及其它的使用和应用被认为是被本发明所覆盖的，本发明仅被随后的权利要求所限制。

例如，通过置换SYND_COMP和ERR_CALC，图3的安排可被有利地用于几种类型的FEC。例如，在不能够用封闭解法计算错误的值和位置的情况下，ERR_CALC应当被改变(以进行钱氏搜索)，但解码器的一般结构(如图3所示)保持基本不变。

Claims

1.一种用于实现包括数据比特帧的数据结构的迭代n维解码的解码器，所述解码器包括：校正子计算器(SYND_COMP)，用于在单个步骤中在所有的n个维中计算校正子；校正子处理器(SYND_PROC)，用于在1、2、…n维中处理所述校正子，所述校正子处理器包括用于存储所述校正子的存储装置(SYND_RAM)；以及数据处理器(SYND_PORC)，用于存储被接收的数据(DATA_RAM_A，DATA_RAM_B)、根据来自所述校正子处理器的信息(11)纠正数据并输出被纠正的数据(DATA_OUT)。

2.根据权利要求1的解码器，其中，所述校正子处理器(SYND_PORC)还包括响应(6)所述校正子存储装置(SYND_RAM)的错误计算器(ERR_CALC)，所述错误计算器用于计算错误并将错误值和错误位置提供给(11)所述数据处理器(DATA_PROC)，并纠正被存储的数据的可能的错误。

3.根据权利要求2的解码器，其中，所述错误计算器(ERR_CALC)与所述校正子处理器(SYND_PROC)中的新校正子的计算器(N_SYND_COMP)配合工作(7)，来计算已经被前面在一个维中的纠正所改变的新的校正子，所述新的校正子是为所有的维被计算的。

4.根据权利要求3的解码器，其中，所述新的校正子计算器(N_SYND_COMP)的输出被提供给所述校正子存储装置(SYND_RAM)，来更新被存储在其中的所述校正子。

5.根据前面的权利要求2至4的任何一个的解码器，其中，所述校正子处理器(SYND_PROC)还包括用于在预置的时间间隔内管理许多校正子纠正迭代的序列发生器(SEQ_CER)，所述序列发生器与所述错误计算器(ERR_CALC)以及所述校正子存储装置(SYND_RAM)配合工作(9，10)。

6.根据前面的权利要求的任何一个的解码器，其中，所述校正子处理器(SYND_PROC)包括校正子复用器(SYND_MUX)，其用于在所述校正子计算器(SYND_COMP)的输出(4)和所述新校正子的计算器(N_SYND_COMP)的输出之间进行切换。

7.根据前面的权利要求的任何一个的解码器，其中，所述数据处理器(DATA_PROC)包括第一存储器(DATA_RAM_A)和第二存储器(DATA_RAM_B)，以及在所述第一或第二存储器之间进行切换的输出复用器(MUX_OUT)。

8.根据权利要求7的解码器，其中，每个所述存储器与一数据复用器(MUX_DATA_A，MUX_DATA_B)相关联，所述数据复用器在输入数据(DATA_IN)和所述校正子处理器(SYND_PROC)的输出(11)之间进行切换。

9.根据前面的权利要求的任何一个的解码器，其中，所述校正子处理器(SYND_PROC)为1、2、…、m次迭代处理所述校正子。

10.根据前面的权利要求的任何一个的解码器，其中，仅一个电路被用于在所有的维中以及为所有的迭代来处理所述校正子。

11.根据前面的权利要求的任何一个的解码器，其中，所述解码器在两个维中操作。

12.根据前面的权利要求的任何一个的解码器，其中，所述解码器被体现在专用集成电路中。

13.一种用于实现包括数据比特帧的数据结构的迭代n维解码的方法，所述方法包括下列步骤：

-接收可能错误的数据(100)；

-在单个步骤中在所有的n个维中计算校正子(101)；

-存储第一被计算的校正子(102)；

-在第一维中处理校正子(103)；纠正错误；并且更新已被在所述第一维中的纠正所影响的校正子；并且

-在直至第n维的所有可能的维中处理校正子(104)，以及，为被处理的校正子的每一个来纠正错误并在所有的维中更新已被该纠正所影响的校正子。

14.根据权利要求13的方法，其中，其还包括执行迭代过程的步骤，所述迭代过程包括下列步骤：

-在第一维中处理(105)不为零的校正子，或已经在前面的步骤期间被更新的校正子；纠正错误；更新已被在所述第一维中的纠正所影响的校正子；

-在直至第n维的所有可能的维中处理(106)不为零的校正子，或已经在前面的步骤期间被更新的校正子，以及，为被处理的校正子的每一个来纠正错误，并在所有的维中更新已被该纠正影响的校正子，并且

-输出(108)被纠正的数据。

15.根据权利要求13或14的方法，其中，为1、2、…、m次迭代处理所述校正子。

16.根据权利要求13至15的任何一个的方法，其中，仅一个电路被用于在所有的维中以及为所有的迭代处理所述校正子。

17.根据权利要求13的方法，其中，执行所述迭代过程直至设定时间帧的末尾(107)。

18.根据权利要求13至15的任何一个的方法，其中，n等于2。

19.根据权利要求13至16的任何一个的方法，其中，所述方法是通过专用集成电路来实现的。

20.一种包括根据权利要求1至12的任何一个的解码器的网络单元。

21.一种包括计算机程序装置的计算机程序，当所述程序在计算机上运行时，所述计算机程序装置适于实现根据权利要求1的方法。

22.一种计算机可读介质，其具有被记录在其上的程序，所述计算机可读介质包括计算机程序代码装置，当所述程序在计算机上运行时，所述计算机程序代码装置适于实现根据权利要求1的方法。