HK1165111B - 解码方法 - Google Patents

Description

解码方法

技术领域

本发明涉及解码由使用截尾卷积码(tail-bitting convolutional code)的卷积编码器所生成的通用码。

背景技术

近年来，当经由通信信道将信息信号从发射机向接收机通信时，该信息信号可能被与信道相关的噪声所破坏。为了防止这种噪声破坏所接收的信息，可以采用信道编码技术。通常，用于减轻信道噪声的影响的编码是通过向通信方的信息中引入冗余来实现的。由于此冗余，降低了噪声破坏所通信的信息的可能性。

卷积码是一种用于减轻信息传输中的信道噪声的影响的信道码。卷积码在本领域中是公知的，并被用作某些类型通信系统的标准。在本领域中，一种卷积码被称作截尾卷积码。

利用截尾卷积码，信息帧或信息块被编码，并以块状方式通信。术语“截尾(tail-bitting)”是指编码器以相同的编码器状态开始和结束。解码器知道编码器以相同的状态开始和结束，但并不知道该状态的值(或标识)。

在本领域中，用于卷积码的最大相似度解码器被称作维特比解码器(Viterbi Decoder)。如所公知的那样，维特比解码器通过假定接收到实际被破坏的序列，查找最有可能未被破坏的符号的序列，来解码所接收符号的序列。用于截尾卷积码的最大相似度解码器采用维特比解码，但是对于计算资源带来巨大需求。或者，如果最小化计算资源，则维特比解码的精确度降低。

发明内容

本发明意图解决一个或多个上述问题，或者至少改进这些问题。

在本发明的一个实施例中，提出一种解码方法，该解码方法解码由使用截尾卷积码的卷积编码器所生成的N个所接收的分支字符，该解码方法包括：在存储器中存储N个所接收的分支字符；对分支字符的序列连续地执行维特比更新，该序列包括第一块、第二块和第三块，该第一块包括所述N个所接收的分支字符中S个连续的分支字符，该第二块包括所述N个所接收的分支字符，该第三块包括所述N个所接收的分支字符中T个连续的分支字符，其中S和T小于N，并且所述维特比更新生成更新的路径度量；根据最佳路径度量，确定在所述第三块的结束处最有可能生成所述序列中的最终分支字符的第一编码器状态；在所述第三块的结束处，从该第一编码器状态开始，第一次执行维特比追溯过程，以确定在分支字符的所述第三块的开始处的第二编码器状态；在所述第三块的开始处，从该第二编码器状态开始，第二次执行维特比追溯过程，以确定在分支字符的所述第二块的开始处的第三编码器状态；以及如果所述第二编码器状态和所述第三编码器状态相同，则输出所导出的截尾路径。

在本发明的另一实施例中，如果所述第二编码器状态和所述第三编码器状态不相同，则所述方法还包括：用所述第三编码器状态替代所述第二编码器状态；重复所述第二次执行；以及输出所导出的截尾路径。

方便地，该连续地执行中的分支字符的序列是由存储在存储器中的N个所接收的分支字符的逻辑圆形读取而形成的。

在本发明的又一实施例中，S等于T。

方便地，所述第一块包括从具有N个所接收的分支字符的第二块的结束处开始的S个连续的分支字符。

此外，所述第三块包括从具有N个所接收的分支字符的第二块的开始处开始的T个连续的分支字符。

本发明的另一方面提出一种解码设备，用于解码由使用截尾卷积码的卷积编码器所生成的N个所接收的分支字符，该解码设备包括：存储器，存储所述N个所接收的分支字符；数据处理单元，包括：连续处理单元，该连续处理单元对分支字符的序列连续地执行维特比更新，该序列包括第一块、第二块和第三块，该第一块包括所述N个所接收的分支字符中S个连续的分支字符，该第二块包括所述N个所接收的分支字符，该第三块包括所述N个所接收的分支字符中T个连续的分支字符，其中S和T小于N，并且所述维特比更新生成更新的路径度量；确定单元，该确定单元根据最佳路径度量，确定在所述第三块的结束处最有可能生成所述序列中的最终分支字符的第一编码器状态；第一执行单元，该第一执行单元在所述第三块的结束处，从该第一编码器状态开始，执行维特比追溯过程，以确定在分支字符的所述第三块的开始处的第二编码器状态；第二执行单元，该第二执行单元在所述第三块的开始处，从该第二编码器状态开始，执行维特比追溯过程，以确定在分支字符的所述第二块的开始处的第三编码器状态；以及输出单元，如果所述第二编码器状态和所述第三编码器状态相同，则该输出单元输出所导出的截尾路径。

附图说明

从参照下列附图的非限制性实例的说明中，本发明的其他特性和优势将显而易见，在附图中：

图1描述了现有技术的卷积编码器。

图2示出反映图1所示的编码器的操作的单个的状态转换网格(state-transition trellis)部分。

图3示出状态转换网格，其示出了图1的编码器的操作，假设特定的开始状态和用于编码的信息位。

图4示出包括数字信号处理器的示例性无线电接收器系统，该数字信号处理器用于解码所接收的分支字符(branchword)，其中该分支字符是由图1所示的编码器生成的。

图5示出在形成图4所示的部分无线电接收器的存储设备中存储所接收的分支字符的块的方式。

图6是示出在解码所接收的分支字符的块的期间，由图4所示的形成部分无线电接收器的数字信号处理器所执行的操作的顺序的流程图，其中该分支字符是由图1所示的编码器所生成的。

具体实施方式

为了下文说明的清楚，将使用相同的参考标号来指代在示出现有技术的图中和示出本发明的图中的相同特征和步骤。

图1描述了示例性的卷积编码器，该卷积编码器具有1/2的速率，即，对于将被编码的每个信息位，该编码器生成两个输出位(即，2位分支字符)。编码器10包括两个单个位存储器单元12和14，以及两个加法器电路16和18。存储器单元12以及加法器电路16和18接收将被编码的信息位序列s(i)。每当接收到新的信息位，存储器单元12将其内容提供给存储器单元14。可以将该编码器视为包括“上游”和“下游”路径。每个路径包括加法器电路和到信息位流的连接，以及存储器单元12和14中的一个或两个。

编码器的“上游”路径(即，包括加法器电路16的路径)的输出包括所生成的分支字符的第一位。该输出是通过将当前位和两个先前位相加而生成的。如果所得的总和是奇数，则加法器16输出逻辑1；如果所得的总和是偶数，则加法器16输出逻辑0。编码器的“下游”路径(即，包括加法器电路18的路径)的输出包括所分支字符的第二位。该输出是通过将当前位和在该当前位之前两位的那个位相加而生 成的。如果所得的总和是奇数，则加法器18输出逻辑1；如果所得的总和是偶数，则加法器18输出逻辑0。由于仅仅使用三个位来确定输出分支字符，认为该编码器的制约长度(constraint length)为3。其存储器是2。对于每个输入位的输出位越多并且制约长度越长，该编码就越有效；即，该编码相对于信道噪声就越强大。

应理解，图1所示的编码器仅仅是示例性的，在本发明的实际实施例中，编码器可以使用更多数目的存储器单元和加法器电路，来对于每个分支字符生成更多数目的位输出。

可以通过诸如图2所示的网格图(trellis diagram)来表示图1所示的传统编码器的操作。网格描述了编码器的状态如何从一个信息位时间(information bit time)变换为下一个。所述编码器状态就是在任何一个时间上的编码器存储单元的内容，其被读作状态“字(word)”。在网格的左侧和右侧，是编码器的可允许状态：00，01，10和11。在网格的左侧的状态表示编码器的当前状态。在网格的右侧的状态表示编码器的下一状态。

例如，与当前位的值无关，如果两个先前位都为0(例如，存储器单元12和14的内容都为0)，则编码器处于状态00(在网格的左侧顶角的网格节点)。如果当前位是1，则下一位的到来意味着编码器转换为状态10。即，随着下一位的到来，存储器单元14中的位被存储器单元12中的位(0)所取代，而存储器单元12中的位被当前位(1)所取代。该转换由从网格的顶端左侧的当前状态00开始并向下延伸到下一状态10的斜线所指示。第二状态从网格的左侧底部开始。该状态转换是编码器的输出分支字符的表示(在括号内)，在该情况下，11。

如果当前位是0而不是1，则下一位的到来意味着编码器转换为相同状态00(如横跨网格的顶部的水平线所示)。网格图表示了编码器状态的所有可允许的转换。例如，根据图2所示的图，编码器不能 从状态00转换为状态11(没有连接左侧的00和右侧的11的线)。关于这一点，从状态每次只能变化一位的事实可以明了。将图2所示类型的多个网格联系起来，就形成表示在时间上的一系列编码器状态转换的网格。图3所示的网格表示由起始状态为00的编码器对信息位序列101100…的编码。该网格包括六个独立的图2所示类型的网格部分。在图3所示的例子中，输入位流导致由实线所示的状态改变，从状态00开始，10，01，10，11，01，00…。在网格的顶部示出离散的时间i。编码器输出括号内所示的分支字符：11，01，00，10，10，11…。由实线所示的跨过网格部分的每个状态转换是对应于给定当前状态和要编码的信息位的允许的转换。其他可能的允许的转换以虚线示出。

如图3所示，对于在特定的时刻、在网格中的任何给定状态，若出现到给定状态的转换，可以有两个先前状态。这从图2或图3可以明了：在网格部分右侧的状态通过两个转换路径而与网格部分的左侧的两个状态相关联。此外，给定一特定的开始状态，任何欲被编码的信息位流都将导致一穿过网格的独特路径。这两个点提供了由卷积编码器生成的分支字符的维特比解码的应用基础。

由图1所示的示例性编码器生成的码字(code word)被通过通信信道而发送给解码器。解码器的工作是确定由编码器所编码的信息位的序列。该确定是基于由解码器接收的分支字符进行的。假设理想的通信信道和得知编码器开始状态，这个工作是相对简单的。解码器采用描述了编码器的状态转换的网格，并得知开始状态，使用所接收的分支字符来判断由编码器在编码时所进行的状态转换。基于这些状态转换，可以确定导致这些转换的位序列。

通常，在现实中无法得到理想的通信信道。因此，现实的解码器必须能够处理这样一种事实：某些接收到的分支字符包含位误差。例如，尽管编码器生成分支字符00，而解码器却接收到分支字符01。因此，解码器可能误解由编码器经历的状态的序列。与现有技术中编码 器的开始状态和结束状态总是等于零的维特比编码器相反，截尾维特比编码器不总是得知编码器的开始状态和结束状态。截尾维特比编码器所得知的只是编码器的开始状态和结束状态理想地相同。然而，利用编码器的开始状态和后续状态序列的不完整的信息，解码器可能在确定编码器信息位的时候出现错误。

如本领域所公知的那样，通过使用维特比解码器，减轻了信道错误的问题。假设可能包含位误差的分支字符，维特比解码器选择穿过编码网格的最有可能的路径。维特比解码器可以从多个开始状态中的任一个来这样操作(假设该解码器不知道开始状态)。该最有可能的路径的选择是逐渐地进行的，每次一个地接收分支字符。将维特比技术应用到每个连续地接收的分支字符的结果是：维持了路径度量(path metric)，该路径度量反映了与该度量相关联的路径即是编码器所采取的路径的可能性。

作为确定由编码器采取的路径的最佳估计的一部分，生成了确定矢量，该确定矢量反映了对于每个状态(在给定的离散时间上)，到该状态的两个可能路径中的哪一个是较佳的路径。该矢量记录对于网格中的每个状态的“较佳路径”决定。没被选作较佳路径的那些路径被认为是“被裁剪了的(pruned)”。被裁剪的路径对分支字符的最终解码没有影响。在实际环境中，信道字符被噪声和干扰所破坏。为了向维特比解码器提供更多的解码信息，使用软性接收的(soft received)分支字符来计算用于路径选择的分支和路径度量。这些软性接收的分支字符是实数。在下文中，术语“分支字符”假设是软性分支字符。

到一个状态，最多有两个路径。因此，作为现有技术，可以用单个的位来表示关于维持哪个路径和裁剪哪个路径的确定。在图1和2所示的编码器的示例性实施例中，在时间上的每个离散点上，有四个状态。因此，在每个时间上，确定四位的确定矢量，并将其保存在存储器中。一旦将维特比技术应用于所接收的分支字符，所保存的确定 矢量就提供了现有技术维特比追溯(traceback)过程的基础。是该追溯过程解码了所接收的分支字符。在Clark and Cain，in Air-correction Coding for Digital Communication，Chapter 6(1981)中记载了传统维特比解码的进一步细节，其全部内容通过引用而合并于此。

图4示出了形成无线电接收器系统的一部分的维特比解码器20的示例性实施例。解码器20连接到天线22和无线电接收器电路24，该无线电接收器电路24接收模拟无线电信号x(t)，并在离散时间c(i)上向解码器20提供数字分支字符。

解码器20包括数字信号处理器(DSP)26，该数字信号处理器26连接到只读存储器(ROM)28和随机访问存储器(RAM)30。该RAM30存储用于本发明的N个所接收的分支字符的缓冲，以及维特比更新的结果。

解码器20操作为解码从无线电通信信道所接收的分支字符。这些分支字符是由采用了截尾卷积码的编码器生成的。这种编码器可以是上述参照图1和2所述的。由于信道有噪声，因此分支字符非理想地通信。也即，所述分支字符可能包含一个或多个位误差。由解码器20执行的解码操作试图从这些分支字符中抽取通信者的信息。

解码器20采用现有技术的维特比解码技术来解码由使用截尾卷积码的卷积编码器所生成的N个所接收的分支字符的块。然而，解码器20通过对分支字符序列(该分支字符序列比由卷积编码器所生成的N个所接收的分支字符更长)连续地执行维特比更新来进行该解码。在其上连续地执行维特比更新的分支字符序列是通过将一分支字符序列添加到N个所接收的分支字符的开始，并将另一分支字符序列添加到N个所接收的分支字符的结束而构成的。

优选地，这是通过图5所示的方式进行的。如该图所示，该分支 字符的序列可以由存储在RAM 30中的N个所接收的分支字符的逻辑圆形读取而形成。可以从存储在RAM 30中的N个所接收的分支字符的块的结尾，读取包括N个所接收的分支字符之中的S个连续分支字符的第一块。相似地，可以从存储在RAM 30中的N个所接收的分支字符的块的开始，读取T个连续分支字符的块。通过首先读取第一块40(该第一块40包括N个所接收的分支字符中的S个连续分支字符)，然后读取第二块42(该第二块42由N个所接收的分支字符构成)，最后读取第三块44(该第三块44包括从N个所接收的分支字符的第二块的开始处的T个连续分支字符)，可以便于计算的方式构成在其上连续地执行维特比更新的分支字符序列。每个维特比更新都基于之前所述的那些度量而生成路径度量和确定矢量。

在维特比解码的当前情况下，解码器20采用如下的法则。如果我们开始沿着穿过图3所示的网格的路径累加分支度量(branch metric)，则将观察到如下的现象：无论何时两个路径合并为一个，仅需保留最有可能的那个路径(最佳路径或幸存路径)，这是因为对于这些路径的所有可能延伸而言，当前较佳的路径总是较佳的。对于这些路径的任何给定的延伸而言，这两个路径通过相同的分支度量延伸。这种处理由添加-比较-选择(ACS)递归来描述，对于网格中的每一步骤，递归地确定通向每个状态的具有最佳路径度量的路径。

因此，如图6所示，解码器20对以图5所示的方式从RAM 30中读取的N+S+T个分支字符的序列连续地执行维特比更新。该维特比更新生成对于每个分支字符而更新的路径度量，直至达到N+S+T个分支字符的序列的结束为止。

在这点上，解码器20根据最佳路径度量，确定最有可能已生成所述序列中的最终分支字符的第一编码器状态。然后，从该第一编码器状态开始执行维特比追溯过程，用以确定在分支字符的第三块44的开始处的第二编码器状态。从该第二编码器状态开始，从分支字符的第 二块42的结束处开始直至分支字符的第二块42的开始处，执行第二维特比追溯过程，以确定第三编码器状态。

如果发现第二编码器状态和第三编码器状态(即，如果在分支字符的第二块42上执行的维特比追溯过程的开始状态和结束状态)相同，则解码器20已经发现了最佳截尾路径。

如果发现第二编码器状态和第三编码器状态不同，则解码器20可以通过用所述第三编码器状态替代所述第二编码器状态并重复所述追溯过程，选择性地重复在分支字符的第二块42上执行的维特比追溯过程。然后输出所推导出的截尾路径。已发现，通常并不需要维特比追溯过程的进一步循环。

适当地，S和T的值是相同的，即，第一和第三块由相同数目的分支字符构成，这些分支字符形成存储于RAM 30中的N个所接收的分支字符的子集。然而，在本发明的其他实施例中，分支字符的第一和第三块可以包括不同数目的分支字符。

通过加长在其上执行维特比更新的分支字符的序列，解码由使用截尾卷积码的卷积编码器所生成的N个所接收的分支字符的上述方法有利地提供了在维特比追溯过程期间所使用的更可靠的路径度量。已发现，使用该方法，通过在N个所接收的分支字符的第二块上仅进行一次追溯过程(或最多执行两次追溯过程)，就可以发现最佳截尾路径。此外，如图5所示的构成分支字符的序列的方式非常易于计算地执行，因此利用最少的额外计算资源就可以实现上述方法的提高的精度。

尽管在上述实施例中，本发明主要是利用数字信号处理来实现的，在其他实施例中，本发明也可以主要利用硬件元件(诸如特定用途集成电路)，以硬件的方式来实现。本发明还可以主要利用计算机软件 或硬件和软件的结合来实现。

尽管参照其示例性实施例描述了本发明，但本发明并不限制于这些实施例。本领域技术人员可以理解，可以在形式和细节上进行各种变化，而不背离由权利要求书所限定的本发明的精神和范围。

本申请基于并要求2008年12月2日提交的澳大利亚临时专利申请No.2008906238的优先权，其全部公开通过引用而合并于此。

工业实用性

根据本发明，可以提供一种采用维特比解码的解码截尾卷积码的方法，其最小化对存储装置和计算资源的需求，并优化了这种解码的精确度。

Claims (6)

1.一种解码方法，该解码方法解码由使用截尾卷积码的卷积编码器所生成的N个所接收的分支字符，该解码方法包括：

在存储器中存储N个所接收的分支字符；

对分支字符的序列连续地执行维特比更新，该序列包括第一块、第二块和第三块，该第一块包括添加到所述N个所接收的分支字符的开始的S个连续的分支字符，该第二块包括所述N个所接收的分支字符，该第三块包括添加到所述N个所接收的分支字符的结束的T个连续的分支字符，其中S和T小于N，并且所述维特比更新生成更新的路径度量；

根据最佳路径度量，在所述第三块的结束处，确定最有可能生成所述序列中的最终分支字符的第一编码器状态；

在所述第三块的结束处，从该第一编码器状态开始，第一次执行维特比追溯过程，以确定在分支字符的所述第三块的开始处的第二编码器状态；

在所述第三块的开始处，从该第二编码器状态开始，第二次执行维特比追溯过程，以确定在分支字符的所述第二块的开始处的第三编码器状态；以及

如果所述第二编码器状态和所述第三编码器状态相同，则输出所导出的截尾路径。

2.根据权利要求1所述的解码方法，其中，如果所述第二编码器状态和所述第三编码器状态不相同，则该方法还包括：

用所述第三编码器状态替代所述第二编码器状态；

重复所述第二次执行；以及

输出所导出的截尾路径。

3.根据权利要求1所述的解码方法，其中，该连续地执行中的分支字符的序列是由存储在存储器中的N个所接收的分支字符的逻辑圆形读取而形成的。

4.根据权利要求1所述的解码方法，其中S等于T。

5.根据权利要求1所述的解码方法，其中所述第一块包括从具有N个所接收的分支字符的第二块的结束处开始的S个连续的分支字符。

6.根据权利要求1所述的解码方法，其中所述第三块包括从具有N个所接收的分支字符的第二块的开始处开始的T个连续的分支字符。