搜索
信息论作业1软编码和BCH编码翻译：谭慧婷4.1介绍在第三章，我们熟悉了RS码和BCH码的基本概念并讨论了他们的编码过程。接下来的这章的学习，并不需要我们有很深的关于RS和BCH代数编码的知识，但是在之前章节学习的基本的编码原则在这一章不会进行赘述。另外，如果很熟悉卷积码的根本概念和Viterbi编码的基本原理，这章的学习会比较轻松。因为尽管这章是对二进制BCH进行编码，仍然需要用到Viterbi算法。正如前面章节提到的，BCH编码是由Hocquenghem以及Bose和Chaudhuri分别于1959和1960年发现的。这些BCH编码形成了一系列的具有多检错和多纠错能力的性能卓越的循环块码。在这个章节，我们将从4.2部分的关于BCH的介绍着手。他们的状态和网格图在4.2.2部分将会展示出来。用Viterbi算法构造出来的BCH码的网格编码将在4.3.2进行详细地阐释。用Berlekamp-Massey算法和Viterbi算法构造出来的不同的BCH码的仿真结果将在4.3.5给出。最后，在4.4部分，我们将把低复杂性Chase算法用在BCH码的软编码上。4.2BCH码一个BCH译码器接受K比特信息并产生N个编码比特。码字的最小汉明距离是dmin，而相关的BCH码是用BCH（n,k,dmin)表示。表4.1列出了一些广泛使用的码生成器，例如g(x)，用来生成BCH码[118].g(x)的系数是用八进制表示，这是为了当他们变为二进制时，最右边的字对应g(x)的零度系数。信息论作业24.2.1BCH译码器因为BCH码是循环码，所以他们的译码器可以用移位寄存电路实现。这些码可以系统地，也可以非系统地译码。而系统的BCH码性能略优于非系统的BCH信息论作业3码。因此，本章节我们只讨论系统的BCH码。对于系统码而言，生成多项式，g(x)如下：g(x)=g0+g1x+......+g1knx1kn+gknxkn生成多项式g(x)通过附加（n-k)个校验的比特到k信息比特上来生成n字长码字。译码器采用一个有（n-k)个状态移位寄存器（如图4.1）。在简单的可信的条款中,这个码展示了他的纠错能力。因为只有特定的满足译码规则的译码序列是合法的，所以毁坏的，不合法的码字能被测试和纠正。这些校验的字是根据生成多项式强加的规则，从信息数据比特中计算出来的。接下来的几步描述了译码的步骤：1）首先的k次移位，switch1是关闭的。这是为了使信息数据字，d(x),能够进入移位寄存器的(n-k)状态。2）同时，为了能使数据比特d(x)直接复制到码字c(x),switch2处于低位。3）在k次移位之后，switch1打开，switch2处于高位。4）剩下的n-k次移位通过将校验的比特加到码字c(x)来清空移位寄存器。让我们来把BCH（7,4,3）作为一个展示译码过程的例子来研究下。在Table4.1中，生成多项式是：g=13octal=1011bing(x)=x3+x+1图4.2展示了具体的译码器，它是由图4.1衍生出来的。我们可以观察到图4.1中的相乘器在4.2中都没有出现了。很显然，如果生成多项式系数是1，相乘器则由图4.2中一个直接的固线连接所取代。而如果系数是0，那么没有连接。信息论作业4让我们用图4.2中的移位寄存器来编译4比特的信息数据，d=1011(d(x)=x3+x2+1)操作步骤如下：这个移位寄存器必须在译码开始之前清零。在第四次移位之后，switch1打开，switch2转到高位。在移位寄存器中的校验的比特会被加到码字中。码字变为c=1001011(c(x)=1+x3+x5+x6).d(x)和c(x)的二进制表示如下图4.3信息论作业54.2.2状态图和网格图让我们来学习在4.2.1部分提到的案例大纲的图4.2。因为数据比特是一次一比特地移入寄存器，校验的比特，{r0,r1,r2},表示寄存器的状态。相应的操作如下：在上面的例子中，有一些需要强调的点：1.编码过程总是从全零状态开始，并且以全零状态结束；2.输出比特总是在一个时钟脉冲之后；3.对首先的k次移位而言，输出比特和输入比特一样；4.在k次移位之后，移位寄存器的校验比特会移动到输出；5.状态的数量增长和2kn的增长一致，当n-k增长时，满足指数增长；信息论作业6对于BCH（7,4,3）码，n-k等于3，而编码器的状态数为23=8.通过使用图4.2中的移位寄存器，当寄存器处于特别的状态时，我们可以找到接下来的所有状态。图4.4展示了对于BCH（7,4,3）而言，在任何译码器状态下的可能状态转换图。从当前状态发散出来的指向其他状态的分支表示了状态的转换。虚线是从数据比特逻辑0衍生出来的，而实线表示数据比特为逻辑1.从当前状态衍生出来的分支数是2，这就和可能的输入比特数目一致，即0或1。而正如之前解释的，输出比特和数据比特一致。和状态转换图相应的状态图如图4.5。它由2kn=8种状态组成，而这些状态是由图4.4所示的状态转换图中所有可能的转换连接起来的。通过图4.5中的状态图，我们可以不使用图4.2中的移位寄存器而编译出数据比特，d=1011.第一个数据比特是逻辑1，所以状态从000转换到110，这就和状态000衍生出来的稳固分支所展示的一样。编码器的输出和输入一样为逻辑1.在下一个时刻，当信息论作业7前的状态变为110，数据比特为逻辑1.这导致状态从110转换至101.接下来的数据比特，编码将一直循环并改变状态。通过在首先的k次编码过程中的状态变化，我们可以观察到一条特别的状态转换路000→110→101→100→100.在k次循环之后，状态的变化将和从移位寄存器中移出来的校验比特一致。在我们的例子中，第k次循环的校验位是100.在接下来的循环中，校验位从左边移动到右边。最右边的校验位移出来作为输出位，而最左边的位用逻辑零补充。因此，状态的转换是100→010→110→000.整个编码过程就可以和状态转换过程000→110→101→100→100→010→001→000相关联起来。另一个编码过程的展示是图4.6中所示的网格图。这是通过连接图4.4中从全零状态开始的状态转换图中的连续时刻得到的。这个图展示了BCH(7,4,3）码中所有可能的2k=16条道路。这个网格有2kn=8行（8个不同的状态）和n+1=8列。在同一行的节点表示相同的状态，而同一列的节点展示了所有可能的状态000,001,010…111。相邻的列间的转换关系可能是实线也可能是虚线，这是依据编码输出是逻辑零还是逻辑一得到的。首先，只有一个全零状态。随着新的数据位加入编码器，网格状态的数量增加。在图4.6中代表与列的位置相对应的时刻的符号，能够从整数T中索引得到。一旦第一个数据比特进入编码器，T=0，在下一个时刻，会有两个可能的不同节点。第二个数据比特到达后，下一个时刻可能的节点数增加到22=4。接下来随着T的增加，可能的节点数增加到最大值2kn=8.在T=3时，可能的状态达信息论作业8到最大，这之后可能状态的数量不再变化。T=k之后，在朝向全零状态的网格图中的每个时刻，可能状态的数量会除以2，直到T=n。4.3网格译码4.3.1介绍线性分组码的网格译码是首先由Wolf[18]在1978年提出来的。然而，这项技术只对特定的BCH码可行，因为状态数随着n-k指数增长。原因在之前的部分中大概地提到过。4.3.2Viterbi算法Viterbi算法（VA）是由Viterbi在1967年[8]提出来的。这个算法搜索在网格中所有可能的路径并且比较译码器当前已收的输入中的汉明距离和欧几里得距离。从接收到的序列选出的具有最小距离的路径会被选作最有可能传输的序列，相关的信息数据字会再次生成。这种方法被称为最可能序列估计，因为最可能出现的路径是从网格图中所有路径中选择的。图4.7记录了由BCH(7，4，3)码Viterbi译码器选择出来的路径的历史。假设没有信道错误，因此译码器的输入序列和译码器的输出序列一样，即0000000.在第一个时刻，T=1，接受比特是逻辑0，将其分别和可能的从节点a信息论作业9到a的传输比特0，以及从节点a到g的传输比特1进行比较。这两个分支的长度是他们的汉明距离，即可能的传输比特0和接收比特1的差别。他们的汉明距离分别是0和1.现在，我们定义分支长度为从接收比特到独立分支的汉明距离，也定义第T个时刻的路径长度为从T=0到T次时刻所有分支的分支长度的和。因此，图4.7所示的在每个分支上方的路径长度，在T=1时，对于路径a→a为1，对于路径a→g是0。在第二个时刻，T=2，接受的比特是0，分支长度是0（a→a),1（a→g),0(g→d),1(g→f).路径长度的平方是0（a→a→a），1（a→a→g),1(a→g→d),2(a→g→f).在第三个时刻，T=3，接收比特是0.这时有八种可能的分支，并且他们的分支长度分别是0（a→a→a→a),1(a→a→a→g),2（a→g→d→f),1(a→g→d→h),3(a→g→f→c),2(a→g→f→e），1（a→a→g→d),2(a→a→g→f).让α1和α2表示从初始节点α开始并且在T=4时刻回到节点α的两条路径a→a→a→a→a和a→g→d→b→a。他们相应的路径长度分别是0和3.从T=4时刻的节点α起源的任意T4的分支都会在路径α1和α2上增加相同的路径长度。这意味着路径α2的长度在T=4时更长，在接下来的T4的时刻也会更长。Viterbi译码器会选择保留最短长度的路径，也就是全零状态的序列，而舍弃路径α2。路径α1就会被作为留存项保留下来。这样的过程在T3的时刻也会在其他节点进行。路径a→g→f→c和路径a→a→g→f等不能留下来，这是因为他们的路径长度比与他们配对的合并对要长，他们就被从译码器的记忆中去掉了。因此，从时刻T=n-k到时刻T=k，只有八条路径留下来，在接下来的时刻，每一个时刻，留下来的路径数减半。有时候，两条路径会合并，也就有相同的路径长度。在T=5的时刻，路径a→a→a→g→d→b和路径a→g→f→e→c→b就在节点b汇合了。他们有相同的路径长度2。一般情况下，Viterbi译码器会随机的选择一个并舍弃另一个。但这种情况绝不会或很少会在软判决Viterbi算法或软输出Viterbi算法中出现，这也是软判决软输出通常在实际的应用中被使用的原因。信息论作业104.3.3硬判决Viterbi译码对于硬判决Viterbi译码，解调器在再生传输序列的时候只提供硬判决，即逻辑0和逻辑1.在这样的情况下，接收比特与在网格中的估计传输比特之间的汉明距离就可以以路径长度和置信度量使用。4.3.3.1正确的硬判决Viterbi译码让我们来阐释下在之前作为例子使用过的用BCH（7,4,3）码进行的硬判决原理。首先假设传输的序列是0000000。一个信道错误在第一个传输比特被引入，解调器提供的第一个接收序列是1000000译码器将解调器的输出以及图4.8中实线（逻辑1）和虚线（逻辑0）表示出来的可能的译码后的比特进行比较。当解调器的输出比特和译码比特一样时，他们的汉明距离是0.相反，如果不一致时，一个汉明距离会被加到累积路径长度上，这样的关系在相应的网格转换图可以体现。在我们贯穿网格时，上面提到的分支长度会被加起来，并且，在T=7时，这条路径拥有最短汉明距离的路径会被看成存活路径。因此译码序列是相关联的一串0和1.信息论作业11图4.8展示了拥有最短路径长度的Viterbi译码器是怎么选择存活路径的，并且正确地编译接收的序列。注意到存活路径的长度等于接收序列中的错误个数，只要译码器能够纠正所有错误即可。但如果考虑到译码器偏离无错网格路径而造成的信道错误，这个规律将不再成立。4.3.3.2不正确的硬判决译码当信道错误超过码制的纠错能力，如图4.9不正确的译码将会产生。两个信道错误被引入到接收序列的第一个和第三个位置，不正确的译码发生在第四个原始分支，造成译码序列变为1011000.这个错误判决和之前的正确判决的区分在于是否接收序列到