软编码和BCH编码性能

1、33信息论作业 软编码和BCH编码翻译：谭慧婷4.1 介绍 在第三章，我们熟悉了RS码和BCH码的基本概念并讨论了他们的编码过程。接下来的这章的学习，并不需要我们有很深的关于RS和BCH代数编码的知识，但是在之前章节学习的基本的编码原则在这一章不会进行赘述。另外，如果很熟悉卷积码的根本概念和Viterbi编码的基本原理，这章的学习会比较轻松。因为尽管这章是对二进制BCH进行编码，仍然需要用到Viterbi算法。正如前面章节提到的，BCH编码是由Hocquenghem以及Bose 和Chaudhuri分别于1959和1960年发现的。这些BCH编码形成了一系列的具有多检错和多纠错能力的性能卓越的

2、循环块码。在这个章节，我们将从4.2部分的关于BCH的介绍着手。他们的状态和网格图在4.2.2部分将会展示出来。用Viterbi算法构造出来的BCH码的网格编码将在4.3.2进行详细地阐释。用Berlekamp-Massey 算法和Viterbi 算法构造出来的不同的BCH码的仿真结果将在4.3.5给出。最后，在4.4部分，我们将把低复杂性Chase算法用在BCH码的软编码上。4.2 BCH码 一个BCH译码器接受K比特信息并产生N个编码比特。 码字的最小汉明距离是d，而相关的BCH码是用BCH（n,k,d)表示。表4.1列出了一些广泛使用的码生成器，例如g(x)，用来生成BCH码118.g(

3、x)的系数是用八进制表示，这是为了当他们变为二进制时，最右边的字对应g(x)的零度系数。 4.2.1 BCH译码器 因为BCH码是循环码，所以他们的译码器可以用移位寄存电路实现。这些码可以系统地，也可以非系统地译码。而系统的BCH码性能略优于非系统的BCH码。因此，本章节我们只讨论系统的BCH码。 对于系统码而言，生成多项式，g(x)如下： g(x)=g+gx+.+gx+gx生成多项式g(x)通过附加（n-k)个校验的比特到k信息比特上来生成n 字长码字。译码器采用一个有（n-k)个状态移位寄存器（如图4.1）。在简单的可信的条款中,这个码展示了他的纠错能力。因为只有特定的满足译码规则的译码序

4、列是合法的，所以毁坏的，不合法的码字能被测试和纠正。这些校验的字是根据生成多项式强加的规则，从信息数据比特中计算出来的。接下来的几步描述了译码的步骤：1） 首先的k次移位，switch 1是关闭的。这是为了使信息数据字，d(x),能够进入移位寄存器的(n-k)状态。2） 同时，为了能使数据比特d(x)直接复制到码字c(x), switch 2处于低位。3） 在k次移位之后，switch 1 打开，switch 2处于高位。4） 剩下的n-k 次移位通过将校验的比特加到码字c(x)来清空移位寄存器。 让我们来把BCH（7,4,3）作为一个展示译码过程的例子来研究下。在Table 4.1中，生成多

5、项式是：g = 13 = 1011g(x) = x+x+1 图4.2展示了具体的译码器，它是由图4.1衍生出来的。我们可以观察到图4.1中的相乘器在4.2中都没有出现了。很显然，如果生成多项式系数是1，相乘器则由图4.2中一个直接的固线连接所取代。而如果系数是0，那么没有连接。 让我们用图4.2中的移位寄存器来编译4比特的信息数据，d=1011( d(x)=x+x+1 )操作步骤如下： 这个移位寄存器必须在译码开始之前清零。在第四次移位之后，switch 1 打开，switch 2转到高位。在移位寄存器中的校验的比特会被加到码字中。码字变为c=1001011 ( c(x)=1+x+x+x ).

6、 d(x)和c(x)的二进制表示如下图4.34.2.2 状态图和网格图 让我们来学习在4.2.1部分提到的案例大纲的图4.2。因为数据比特是一次一比特地移入寄存器，校验的比特，r,r,r,表示寄存器的状态。相应的操作如下：在上面的例子中，有一些需要强调的点：1. 编码过程总是从全零状态开始，并且以全零状态结束；2. 输出比特总是在一个时钟脉冲之后；3. 对首先的k次移位而言，输出比特和输入比特一样；4. 在k次移位之后，移位寄存器的校验比特会移动到输出；5. 状态的数量增长和2的增长一致，当n-k增长时，满足指数增长； 对于BCH（7,4,3）码，n-k等于3，而编码器的状态数为2=8.通过使

7、用图4.2中的移位寄存器，当寄存器处于特别的状态时，我们可以找到接下来的所有状态。 图4.4展示了对于BCH（7,4,3）而言，在任何译码器状态下的可能状态转换图。从当前状态发散出来的指向其他状态的分支表示了状态的转换。虚线是从数据比特逻辑0衍生出来的，而实线表示数据比特为逻辑1.从当前状态衍生出来的分支数是2，这就和可能的输入比特数目一致，即0或1。而正如之前解释的，输出比特和数据比特一致。 和状态转换图相应的状态图如图4.5。它由2=8种状态组成，而这些状态是由图4.4所示的状态转换图中所有可能的转换连接起来的。通过图4.5中的状态图，我们可以不使用图4.2中的移位寄存器而编译出数据比特，

8、d=1011.第一个数据比特是逻辑1，所以状态从000转换到110，这就和状态000衍生出来的稳固分支所展示的一样。编码器的输出和输入一样为逻辑1.在下一个时刻，当前的状态变为110，数据比特为逻辑1.这导致状态从110转换至101.接下来的数据比特，编码将一直循环并改变状态。通过在首先的k次编码过程中的状态变化，我们可以观察到一条特别的状态转换路000110101100100. 在k次循环之后，状态的变化将和从移位寄存器中移出来的校验比特一致。在我们的例子中，第k次循环的校验位是100.在接下来的循环中，校验位从左边移动到右边。最右边的校验位移出来作为输出位，而最左边的位用逻辑零补充。因此，

9、状态的转换是100010110000.整个编码过程就可以和状态转换过程000110101100100010001000相关联起来。 另一个编码过程的展示是图4.6中所示的网格图。这是通过连接图4.4中从全零状态开始的状态转换图中的连续时刻得到的。这个图展示了BCH(7,4,3）码中所有可能的2=16条道路。这个网格有2=8行（8个不同的状态）和n+1=8列。在同一行的节点表示相同的状态，而同一列的节点展示了所有可能的状态000,001,010111。相邻的列间的转换关系可能是实线也可能是虚线，这是依据编码输出是逻辑零还是逻辑一得到的。 首先，只有一个全零状态。随着新的数据位加入编码器，网格状态

10、的数量增加。在图4.6中代表与列的位置相对应的时刻的符号，能够从整数T中索引得到。一旦第一个数据比特进入编码器，T=0，在下一个时刻，会有两个可能的不同节点。第二个数据比特到达后，下一个时刻可能的节点数增加到2=4。接下来随着T的增加，可能的节点数增加到最大值2=8.在T=3时，可能的状态达到最大，这之后可能状态的数量不再变化。T=k之后，在朝向全零状态的网格图中的每个时刻，可能状态的数量会除以2，直到T=n。4.3 网格译码4.3.1 介绍 线性分组码的网格译码是首先由Wolf 18在1978年提出来的。然而，这项技术只对特定的BCH码可行，因为状态数随着n-k指数增长。原因在之前的部分中大

11、概地提到过。 4.3.2 Viterbi算法 Viterbi 算法（VA）是由Viterbi在1967年8提出来的。这个算法搜索在网格中所有可能的路径并且比较译码器当前已收的输入中的汉明距离和欧几里得距离。从接收到的序列选出的具有最小距离的路径会被选作最有可能传输的序列，相关的信息数据字会再次生成。这种方法被称为最可能序列估计，因为最可能出现的路径是从网格图中所有路径中选择的。 图4.7记录了由BCH(7，4，3)码Viterbi译码器选择出来的路径的历史。假设没有信道错误，因此译码器的输入序列和译码器的输出序列一样，即0000000.在第一个时刻，T=1，接受比特是逻辑0，将其分别和可能的从

12、节点a到a的传输比特0，以及从节点a到g的传输比特1进行比较。这两个分支的长度是他们的汉明距离，即可能的传输比特0和接收比特1的差别。他们的汉明距离分别是0和1. 现在，我们定义分支长度为从接收比特到独立分支的汉明距离，也定义第T个时刻的路径长度为从T=0到T次时刻所有分支的分支长度的和。因此，图4.7所示的在每个分支上方的路径长度，在T=1时，对于路径aa为1，对于路径ag 是0。在第二个时刻，T=2，接受的比特是0，分支长度是0（aa),1（ag),0(gd),1(gf).路径长度的平方是0（aaa），1（aag),1(agd),2(agf).在第三个时刻，T=3，接收比特是0.这时有八种

13、可能的分支，并且他们的分支长度分别是0（aaaa),1(aaag),2（agdf),1(agdh),3(agfc),2(agfe），1（aagd),2(aagf). 让和表示从初始节点开始并且在T=4时刻回到节点的两条路径aaaaa和agdba。他们相应的路径长度分别是0和3.从T=4时刻的节点起源的任意T>4的分支都会在路径和上增加相同的路径长度。这意味着路径的长度在T=4时更长，在接下来的T>4的时刻也会更长。Viterbi译码器会选择保留最短长度的路径，也就是全零状态的序列，而舍弃路径。路径就会被作为留存项保留下来。这样的过程在T>3的时刻也会在其他节点进行。路径agf

14、c和路径aagf等不能留下来，这是因为他们的路径长度比与他们配对的合并对要长，他们就被从译码器的记忆中去掉了。因此，从时刻T=n-k到时刻T=k，只有八条路径留下来，在接下来的时刻，每一个时刻，留下来的路径数减半。 有时候，两条路径会合并，也就有相同的路径长度。在T=5的时刻，路径aaagdb和路径agfecb就在节点b汇合了。他们有相同的路径长度2。一般情况下，Viterbi译码器会随机的选择一个并舍弃另一个。但这种情况绝不会或很少会在软判决Viterbi算法或软输出Viterbi算法中出现，这也是软判决软输出通常在实际的应用中被使用的原因。4.3.3 硬判决Viterbi译码 对于硬判决V

15、iterbi译码，解调器在再生传输序列的时候只提供硬判决，即逻辑0和逻辑1.在这样的情况下，接收比特与在网格中的估计传输比特之间的汉明距离就可以以路径长度和置信度量使用。4.3.3.1 正确的硬判决Viterbi译码 让我们来阐释下在之前作为例子使用过的用BCH（7,4,3）码进行的硬判决原理。首先假设传输的序列是0 0 0 0 0 0 0 。一个信道错误在第一个传输比特被引入，解调器提供的第一个接收序列是1 0 0 0 0 0 0 译码器将解调器的输出以及图4.8中实线（逻辑1）和虚线（逻辑0）表示出来的可能的译码后的比特进行比较。当解调器的输出比特和译码比特一样时，他们的汉明距离是0.相反

16、，如果不一致时，一个汉明距离会被加到累积路径长度上，这样的关系在相应的网格转换图可以体现。在我们贯穿网格时，上面提到的分支长度会被加起来，并且，在T=7时，这条路径拥有最短汉明距离的路径会被看成存活路径。因此译码序列是相关联的一串0和1.图4.8展示了拥有最短路径长度的Viterbi 译码器是怎么选择存活路径的，并且正确地编译接收的序列。注意到存活路径的长度等于接收序列中的错误个数，只要译码器能够纠正所有错误即可。但如果考虑到译码器偏离无错网格路径而造成的信道错误，这个规律将不再成立。4.3.3.2 不正确的硬判决译码 当信道错误超过码制的纠错能力，如图4.9不正确的译码将会产生。两个信道错误

17、被引入到接收序列的第一个和第三个位置，不正确的译码发生在第四个原始分支，造成译码序列变为1011000. 这个错误判决和之前的正确判决的区分在于是否接收序列到相应的正确路径的汉明距离是否小于接收序列到网格中其他路径的汉明距离。进一步观察到存活路径的长度现在不再等于发生的错误个数。 4.3.4 软判决Viterbi 译码目前为止，我们已经讨论了硬判决译码。我们现在来研究软判决译码技术。在这个方法中，解调器输出的接收信号是采样过的。采样的数值直接就是Viterbi 译码器的输入。 假设我们在传输器用BPSK，逻辑0 会以-1.0传输，逻辑1 会以+1.0传输。如果我们传输全逻辑0，传输序列会是-1

18、 -1 -1 -1 -1-1 -1。在接收器，如果我们使用上个例子用到的硬判决，和序列101000相应的解调器的软输出是+0.8，-1.2，-2.2，-0.4，-1.3，-0.9。 如图4.10展示的， 解调器的软输出是被看做一种可信度的测量指标。第一个解调器的软输出是+0.8，这暗示传输比特可能是+1，这个判决的可信度是0.8.考虑到和逻辑1相对应的路径ag，这条路径的分支长度是+0.8.但是路径aa不和接收的信号一致，因此这条路径的分支长度是-0.8，这是因为负的路径长度累加起来或者说不相似性造成的。在第二个时刻，接收到的信号时-1.2，分别对路径aaa,aag,agd,agf造成了+0.

19、4,-2.0,+2.0和-0.4的路径长度。 让和分别表示两条路径aaaaa和agdba。全部的路径长度对于和来说分别是+2.0和+0.4.Viterbi译码器会因为更强的累积可信度而选择与具有更大路径距离的路径相关的路径。因此，路径会被选择（而不是在硬判决中会被选择的路径）。因此，软判决译码的性能比硬判决更好。 4.3.5 仿真结果 下面的仿真结果是在可加高斯白噪声信道下采用简单BPSK体制产生的。 4.3.5.1 Berlekamp-Massey 算法 在这个部分，我们用BM算法来区分判断不同BCH码的性能。 图4.11,4.12,4.13,4.14展示了拥有相同码字长度的BCH码的性能。

20、 在图4.14中，我们可以看到译码率为0.95的BCH(127,120,3)码在BER为10表现的最差。译码率为0.89的BCH（127,113,5）码在BER为10的时候性能有0.75dB的改善。随着译码率的减小，属于BCH(127，k,t)系列的译码性能更好。然而，当译码率达到0.5或者更低时，这条规律不再适用。这是因为译码冗余增大不可避免的会降低每个传输比特所带的能量。例如，BCH(127，71，19)就比BCH(127，64，21)性能更好。这两条规律也适用于其他的家庭译码。 图4.15展示了从每个家庭译码中选出来的不同译码率的BCH码的性能比较。相反，图4.16提供了一系列译码率为0

21、.5的码的性能比较。从这些图中，我们可以总结出来BCH码性能随着n的增大而改善。4.3.5.2 硬判决Viterbi 译码图4.17展示了BCH（31,21,5）和BCH(15,7,5)两种码分别采用硬判决Viterbi算法和硬判决BM算法的表现。不同算法的性能相当相似。4.3.5.3 软判决Viterbi 译码图4.18展示了BCH（31,21,5）码分别采用软判决Viterbi算法和软判决BM算法的表现。我们可以看到性能在BER为10时有2dB的性能改善。4.3.6 分块编码码的结论使用BM 算法进行译码的一系列BCH码的性能我们已经通过仿真有了理解。当BER为10和10时，在AWGN信道

22、下许多BCH码的译码增益如表格4.2,4.3,4.4. 上图4.19和4.20展示了在BER分别为10和10时，译码增益与不同BCH码即不同译码率的关系。而这些关系表明了以下的这些结论。随着k和R=k/n增加，对于每一个家庭译码（n是常数），都有一个最大的译码增益。另外，这个最大增益出现在译码率为0.5到0.6的时候。比如图4.20中，码字长度为127，在译码率为0.56 是有最大译码增益4.1dB.对BCH码（n=63)而言，当译码率为0.57时，有最大增益3.5dB. 4.4 软输入代数译码 4.4.1 介绍 在这个部分，我们会研究在经典的代数译码的内容中采用软输入的好处。译码技术，我们的

23、仿真结果和相关的结论会在这个部分进行阐释，自从1960年BCH码的发现，许多的译码方法17,29,31,32,34,115都曾被推荐用于BCH的译码。而BM译码31-14被广泛看做是最受欢迎的译码技术。 然而，BM算法假设解调器的输出是二进制，这暗示着这个算法不能够直接处理从解调器出来的软输出。在4.3.5.3部分，我们已经展示了在BCH的网格译码中，如果我们用软判决Vietrbi算法而不是硬判决Viterbi算法，我们可以得到2dB的性能改善。 在1972年，Chase28发明了一种能直接应用解调器软输出的译码算法。在接收器，解调器提供接收到的信号值y,假设相应的 数据比特u是0或者1，表明

24、了两种不同的特征： 1.他的极性表明了u是0（ 正y）还是1（负y）； 2.他的绝对值|y|暗示了由解调器提供的置信度量； 正如之前提到的一样，基于硬判决的BM算法只能用解调器提供的二进制比特。BCH(n,k,d)码的纠错能力t和码字间的最小汉明距离d有关。大体上而言，BCH码的纠错能力t可以被定义成每个码字能确保纠正的最大错误个数： t = d-1 其中i表示不超过i的最大整数。 图4.21展示了一个程式化的卷积代数译码的例子。图中c到c表示四个可靠的码字，他们之间最小的间隔距离是d。每个码字被一个半径为t的译码范围包围。现在我们假设有两个相同的BCH码字c和c在有噪声的信道下传递。解调器提

25、供的相关的n比特的接收矢量是z和z 正如我们可以看到的，z不在可靠码字的译码范围，因此卷积的代数译码器不能够纠正z的错误。另一方面，二进制n重接收矢量z 进入了c码字的译码范围，因此它会被译码成可靠码字c。然而，如果我们进一步考虑由解调器提供的基于软判决的置信度量指标|y|，译码器可能会在n重矢量z中纠正t个以上的错误。除此以外，接收到的n重矢量z更有可能会被归到c而不是c。这些问题在接下来的Chase 算法中都得到了解决。4.4.2 Chase 算法 图4.22展示了由信道测量信息辅助形成的译码过程的几何概略图。相应地，接收到的n重矢量z被一系列的测试模式 TP扰乱.其中TP表示一串在比特位

26、置的1被反转的二进制序列。通过加入测试模式，对接收二进制序列模2，我们就可以得到一串新的二进制序列z:z =z TP. 正如图4.22中显示的，r表示扰乱的二进制接收序列z 到原始的二进制接收序列z的最大汉明距离。 通过一系列的测试模式，扰乱的接收 二进制序列z可能会落入一些可靠BCH码字的译码范围。如果我们增加r，扰乱的接收 二进制序列z可能会落入更多可靠BCH码字的译码范围。 如果扰乱的接收 二进制序列z可能会落入可靠BCH码字c的译码范围,通过调用代数译码，一个新的错误样本e就会产生，这个模式可能是全0也有可能是全1。而实际的与接收二进制序列z相关的错误模式e是：e = e TP; 这个

27、错误模式有可能和原来的测试模式TP一样，也有可能不一样，这取决于扰乱的接收二进制序列z是否落入了可靠BCH码字的译码范围。然而，只有那些落入了可靠BCH码字的译码范围的扰乱的接收二进制序列z才会被考虑。 最大可能的译码器能够找到满足下列式子的码字：Minweight(z c) 其中m的范围包含所有可能的码字。基于相似的原则，Chase28定义了一种新的信道译码器。然而，考虑到低密度，只有少数的可靠码字能够用Chase 方法考虑，即那些被扰乱的接收二进制序列z落入的可靠BCH码字的译码范围环绕的码字。在这种情况下，我们必须很关心最小的错误模式e,其中一个错误序列的模拟权重定义为：W(e) = e

28、|y| Chase算法能够用图流程图4.23总结表示出来。每一次，算法会考虑一个n重BCH码的码字，这个码字是由n个接收比特z 和他们的软长度y组成的。图中所示的第一步，接收比特z 和他的可信度数值y被组合起来。接下来，一系列测试模式TP生成。对于每一个测试模式而言，一个新的序列z可以通过将TP 和接收序列z模二加得到。如图4.21所示，卷积的代数译码器被用来译码新序列z。如果卷积的代数译码器找到了一个非全零的错误模式e,我们就可以通过方程式4.5 找到与接收序列z相关的实际错误模式e.通过使用方程式4.7，实际错误模式的模拟权重可以被算出来。如果相应的模拟权重是最低的话，相应的TP可以在存储

29、器中保存下来。上述的步骤需要对每一个生成的TP重复。一旦完成了图4.23所示的循环，存储器就会被检查。如果里头储存了一个错误模式，二进制译码序列就会是z e.如果不包含，二进制译码序列就和接收序列z一样。4.4 代数译码的软输入 测试模式中的数字可以根据可允许的复杂性改变，同时也对可实现的效能产生改变。在后面的章节中，我们提出两个关于此算法的变种，命名为Chase 算法 1 和 Chase 算法 2。这两种算法的性质主要取决于所使用的测试模式的数目。4.4.2.1 Chase算法1 对于这个特定算法，通常考虑用一大组的TP测试模式。实际上，该算法考虑的在围绕所接收的二进制序列Z半径范围为r=d

30、-1内的整组可能的测试模式。所以我们考虑的a是二进制权重小于或等于d-1的所有可能的测试模式。   让我们在实例的辅助下来说明算法的操作。在这个实例中，我们采用了BCH(7,4,3)码，其中d=3。因此，所有的二进制权重小于或等于d-1=2的测试模式都会产生，如图4.23的步骤二。一个二进制权重小于或等于1的部分测试模式TP展示如下： 使用二进制权重等于1的TP测试模式，我们还能够生成二进制权重大于1测试模式。让我们假定使用BPSK并发送序列-1-1-1-1-1-1-1。软解调器输出y，硬判定译码二进制序列z，置信度量| y |显示于表4.5。 表4.5：软解调器输出，硬判定译码序列

31、以及置信度量示例 例如在等式4.8的第二种测试样式TP1中，被扰乱了的接收序列z为： 由于这种扰动，我们现在有从一个合法的码字中得来的一个汉明距离内的序列，即0000000序列，因此扰动接收的二进制序列Z'由代数译码器译码，译码的序列为0000000。因此，相关错误序列e'是：e'=0 0 0 0 1 0 0, 实际错误序列e是： 正如我们将在下面展示的，这是最可能出现的错误序列e，使我们能够纠正两个硬判决BM算法能达到的最大错误数，而不是一个。为了量化误差可能序列的概率，其模拟权重其后确定。实际错误序列e的模拟权重为：这个过程被其它二进制权重小于或等于d-1的测试模式

32、重复，如公式4.8。 表4.6显示与公式4.8中每个测试模式相关联的模拟权重。同时考虑所有二进制权重小于或等于d-1的测试模式，最低的模拟权重是1.4。如我们可以从表4.6看出，测试模式TP1和TP3已经产生最低模拟权重，是1.4。它可以轻易地表示出，这两个测试模式TP1和TP3的相关实际误差模式e是相同的。因此，Chase译码序列z是：计算机模拟显示，这种算法的性能和软判决Viterbi算法相似。 BCH（7,4,3）码的最小自由距离d为3,可能的测试模式数量为29，如果我们使用该算法来译码BCH（31,21,5）码，最小自由距离d变为5.因此，我们需要考虑所有二进制权重小于或等于4的测试模

33、式。在这种情况下，测试模式的数量超过36000。通常情况下，测试模式的数量与n和d相互成倍增加。4.4.2.1 Chase算法2 对于这种Chase算法的变型，可以考虑使用一组可能的较小型差错模式。只有置信度为最小d/2的位置才会被考虑。测试模式TP有许多1的任意组合位于置信度为最低d/2的位置。因此，只会有2d/ 2的可能的测试形式，包括全零模式。 对于BCH（7,4,3）码，合法的测试位置的数量为一，同时，测试模式的数量为二。计算机模拟显示，这种简化了的算法的BER性能曲线比之前说的软判定Viterbi算法的性能差四分之一dB。如果测试位置的数量为3，即有八个测试模式，那么性能将和软判定Viterbi算法相同。用同样的例子，如4.4.2.1部分，我们要寻找三个和最低置信度相关的相关最低信心措施的测试位置。这八个测试模式是：它们的相关模拟权重总结于表4.7。注意，在Chase算法2中测试模式TP3的相关错误序列e'并不考虑。计算机模拟显示，当测试位置的数量增加至接近软判定Viterbi算法（即试验位置数量为d）时，将会得到更好的结果。最后我们注意到，一个不同于Chase算法