数字通信技术04-课件.ppt

1、Institute of Communications EngineeringInstitute of Communications EngineeringInstitute of Communications Engineering4.4 卷积编码卷积编码(续续)3五、软判决译码和硬判决译码五、软判决译码和硬判决译码1、信道模型、信道模型从数学上看，信道实际上是从发空间从数学上看，信道实际上是从发空间X到收空间到收空间Y一一个概率映射函数个概率映射函数4五、软判决译码和硬判决译码五、软判决译码和硬判决译码用一个离散输入码元集、用一个离散输入码元集、一个离散输出码元集，以一个离散输出码元集，以

2、及一组条件概率及一组条件概率来描述。其中来描述。其中i代表调制器代表调制器M 进制输入码元，进制输入码元，j 代表代表解调器解调器Q 进制输出码元，进制输出码元，P(j|i)代表发送代表发送 I 时收到时收到j的的概率。概率。()(11)P j|ii M,j Q x1x2xMy1y2yQ:P1|1P2|1P1|2P2|2PQ|M5五、软判决译码和硬判决译码五、软判决译码和硬判决译码离散无记忆离散无记忆信号在时刻信号在时刻 i 的输出仅与时刻的输出仅与时刻 i 的输入有关的输入有关输出与输入的数目有限输出与输入的数目有限6五、软判决译码和硬判决译码五、软判决译码和硬判决译码DMC 的一个特例，的

3、一个特例，输入输入和输出字符集只包含二进和输出字符集只包含二进制元素制元素0和和1，条件概率是，条件概率是对称的：对称的：(0|1)=(1|0)=(1|1)=(0|0)=1-PPpPPp 1-p0 0 p 11 1-p7对于对于BSC信道，解调器的输出包含离散元素信道，解调器的输出包含离散元素0和和1，因此说解调器对每个码元有一个因此说解调器对每个码元有一个硬判决硬判决(hard decision)。译码器是在解调器硬判决基础上译码的，因此译码器是在解调器硬判决基础上译码的，因此BSC信道的译码称为信道的译码称为硬判决译码硬判决译码(hard-decision decoding)。五、软判决译

4、码和硬判决译码五、软判决译码和硬判决译码8五、软判决译码和硬判决译码五、软判决译码和硬判决译码具有离散的输入字符和连续的输出字符。信道给码元具有离散的输入字符和连续的输出字符。信道给码元加上均值为加上均值为 0、方差为、方差为2的高斯分布的噪声，的高斯分布的噪声，对所有对所有的接收随机变量的接收随机变量z，其在输入码元为，其在输入码元为uk 条件下的概率条件下的概率密度函数为：密度函数为：22()1exp221,2,.,(|)kkzukMp z u9五、软判决译码和硬判决译码五、软判决译码和硬判决译码当解调器的输出包括连续字符或者该字符的量化当解调器的输出包括连续字符或者该字符的量化值（超过两

5、个电平）时，则称解调器进行值（超过两个电平）时，则称解调器进行软判决软判决(soft decision)。解调器将这些量化后的编码码元输入译码器，因解调器将这些量化后的编码码元输入译码器，因为译码器的操作是在解调器软判决基础上的，所为译码器的操作是在解调器软判决基础上的，所以这种高斯信道的译码称为以这种高斯信道的译码称为软判决译码软判决译码(soft-decision decoding)。10五、软判决译码和硬判决译码五、软判决译码和硬判决译码2、硬判决译码与软判决译码的定义、硬判决译码与软判决译码的定义对于输入为二进制码元的信道，在传输过程中受到噪对于输入为二进制码元的信道，在传输过程中受到

6、噪声的污染，成为取值连续的信号。声的污染，成为取值连续的信号。当解调器的判决输出为二电平信号时，则对应于每一当解调器的判决输出为二电平信号时，则对应于每一个二进制的输入码元，解调器输出一个相应的二进制个二进制的输入码元，解调器输出一个相应的二进制码元码元0或或1，此时我们说解调器对每个码元进行，此时我们说解调器对每个码元进行硬判硬判决决。当解调器判决时所设置的量化电平数为当解调器判决时所设置的量化电平数为L(L2)时，则时，则对应于每一个二进制的输入码元，解调器输出一组对应于每一个二进制的输入码元，解调器输出一组n比特的二进制序列，并且比特的二进制序列，并且L2n，即，即L个量化电平被编个量化

7、电平被编为为n比特的二进制序列。这种多电平的判决被称为比特的二进制序列。这种多电平的判决被称为软软判决判决。11事实上，译码器的输入就是解调器的输出。当译码事实上，译码器的输入就是解调器的输出。当译码器对解调器的硬判决输出进行译码时，称为器对解调器的硬判决输出进行译码时，称为硬判决硬判决译码译码(hard-decision decoding)(hard-decision decoding)；当译码器对解调；当译码器对解调器的软判决输出进行译码时，称为器的软判决输出进行译码时，称为软判决译码软判决译码(soft-decision decoding)(soft-decision decoding)

8、。通常，我们将信道考虑成对称信道。典型的硬判决通常，我们将信道考虑成对称信道。典型的硬判决信道就是二进制对称信道。典型的软判决对称信道信道就是二进制对称信道。典型的软判决对称信道是是2 2电平输入，电平输入，8 8电平输出的信道，即电平输出的信道，即1 1比特输入，比特输入，3 3比特输出。比特输出。五、软判决译码和硬判决译码五、软判决译码和硬判决译码12s1/s2的似然函数与硬判决的似然函数与硬判决/软判决输出的对应关系软判决输出的对应关系s1和和 s2分别对应于信道输入为分别对应于信道输入为“1”和和“0”，z为信道输出。为信道输出。五、软判决译码和硬判决译码五、软判决译码和硬判决译码13

9、五、软判决译码和硬判决译码五、软判决译码和硬判决译码在最大似然译码中，每个码元的似然函数在最大似然译码中，每个码元的似然函数p(z/si)越大，说明接收到的越大，说明接收到的z是是si的可能性越大。因此的可能性越大。因此 反反映了接收信号是映了接收信号是si的可信程度（以下简称可信的可信程度（以下简称可信度）。度）。对于软判决译码，可以用编码来表示可信度。对于软判决译码，可以用编码来表示可信度。140 1 10 1 00 0 10 0 01 0 01 0 11 1 01 1 1判决位判决位可信度可信度可信度取的是补码可信度取的是补码五、软判决译码和硬判决译码五、软判决译码和硬判决译码153、软

10、判决、软判决viterbi译码译码硬判决和软判决维特比译码的主要区别是，软判决算硬判决和软判决维特比译码的主要区别是，软判决算法不使用汉明距里，而采用欧氏距离作为距离量度。法不使用汉明距里，而采用欧氏距离作为距离量度。译码时取欧氏距离小的分支，舍弃欧氏距离大的分支。译码时取欧氏距离小的分支，舍弃欧氏距离大的分支。五、软判决译码和硬判决译码五、软判决译码和硬判决译码16硬判决译码与软判决译码硬判决译码与软判决译码五、软判决译码和硬判决译码五、软判决译码和硬判决译码17六六 卷积码卷积码viterbi译码算法的性能译码算法的性能1、译码约束度、译码约束度在在viterbi译码过程中，译码过程中，“

11、加加比比选选”的结的结果是得到了一条汉明距离累加值小的幸存路径，果是得到了一条汉明距离累加值小的幸存路径，丢弃了其它汉明距离累加值大的路径。丢弃了其它汉明距离累加值大的路径。18A丢弃路径丢弃路径幸存路径幸存路径六六 卷积码卷积码viterbi译码算法的性能译码算法的性能19六六 卷积码卷积码viterbi译码算法的性能译码算法的性能20六六 卷积码卷积码viterbi译码算法的性能译码算法的性能经过了初始状态后，网格图中每个时刻需保留的经过了初始状态后，网格图中每个时刻需保留的 幸存路径数等于网格图的状态数幸存路径数等于网格图的状态数2k(N1)。路径收敛：网格图中共有路径收敛：网格图中共有

12、2k(N-1)条幸存路径，当条幸存路径，当对某些路径的考虑长到一定程度时，不正确的路对某些路径的考虑长到一定程度时，不正确的路径不断地淘汰，并在幸存路径的末端出现了收敛径不断地淘汰，并在幸存路径的末端出现了收敛现象。现象。讨论：讨论：当差错模式超出卷积码的纠错能力时，是否能当差错模式超出卷积码的纠错能力时，是否能出现收敛现象？出现收敛现象？21四条幸存路径四条幸存路径收敛区收敛区六六 卷积码卷积码viterbi译码算法的性能译码算法的性能22六六 卷积码卷积码viterbi译码算法的性能译码算法的性能译码深度：译码深度：显然，在收敛现象出现前的幸存路径显然，在收敛现象出现前的幸存路径都需要存储

13、。由于收敛的时间不确定，译码时通都需要存储。由于收敛的时间不确定，译码时通常设置一固定观察路径的长度常设置一固定观察路径的长度M，称译码约束度，称译码约束度或译码深度。译码深度或译码深度。译码深度M和状态数和状态数2k(N-1)决定了决定了需要存储的内容。需要存储的内容。译码深度译码深度M取得太大，需要存储的内容太多；如取得太大，需要存储的内容太多；如果取得太小，则在判决时路径还可能还没有收敛，果取得太小，则在判决时路径还可能还没有收敛，造成判决出错。译码约束度造成判决出错。译码约束度M一般通过计算机模一般通过计算机模拟确定。拟确定。236.36.310106.46.46.76.7*7.27.

14、2*5 56.56.56.86.87.257.254 46.76.77.27.27.47.43 37 76 65 5 Eb/n0译码约束度译码约束度编码约束度编码约束度 六六 卷积码卷积码viterbi译码算法的性能译码算法的性能244.44.427274.54.54.94.95.25.25 54.74.75.05.05.35.34 45.15.15.25.25.75.73 37 76 65 5 Eb/n0译码约束度译码约束度编码约束度编码约束度 六六 卷积码卷积码viterbi译码算法的性能译码算法的性能25六六 卷积码卷积码viterbi译码算法的性能译码算法的性能2、编码增益、编码增益编

15、码增益是衡量整个差错控制系统的性能指标编码增益是衡量整个差错控制系统的性能指标。编码增益与许多因素有关编码增益与许多因素有关卷积码编码增益在不同的误比特率条件下是不相卷积码编码增益在不同的误比特率条件下是不相同的，误比特率越低时，编码增益越大；同的，误比特率越低时，编码增益越大；编码约束长度越大，编码增益越高；编码约束长度越大，编码增益越高；编码效率越低，编码增益越大；编码效率越低，编码增益越大；译码约束长度越大，编码增益越高；译码约束长度越大，编码增益越高；软判决电平数越高，编码增益越高。软判决电平数越高，编码增益越高。26卷积码卷积码(n,k,N)(n,k,N)编码增益（编码增益（dBdB

16、）P Pe e=10=10-3-3P Pe e=10=10-5-5P Pe e=10=10-7-73 3，1 1，7 74.24.25.75.76.26.22 2，1 1，7 73.83.85.15.15.85.82 2，1 1，6 63.53.54.64.65.35.32 2，1 1，5 53.33.34.34.34.94.93 3，2 2，4 43.13.14.64.65.25.23 3，2 2，3 32.92.94.24.24.74.74 4，3 3，3 32.62.64.24.24.84.84 4，3 3，2 22.62.63.63.63.93.9六六 卷积码卷积码viterbi译码算

17、法的性能译码算法的性能27量化比特数量化比特数EEb b/n/n0 0（dBdB）编码增益编码增益3 34.94.94.74.74 44.84.84.84.85 54.74.74.94.9 六六 卷积码卷积码viterbi译码算法的性能译码算法的性能Institute of Communications Engineering4.5 RS码码29一、数学基础一、数学基础1、有限域（加罗瓦域，、有限域（加罗瓦域，Galois Field，GF）对于任何质数对于任何质数q q，存在一个有限域，表示为，存在一个有限域，表示为GF(GF(q q)，其中包含其中包含q q个元素。个元素。可以将可以将GF

18、(GF(q q)延伸为一个含有延伸为一个含有q qm m个元素的域，称为个元素的域，称为GF(GF(q q)的扩展域，表示为的扩展域，表示为GF(GF(q qm m)，m m是一个非零的正整是一个非零的正整数。数。GF(GF(q q)是是GF(GF(q qm m)的一个子域。例如，的一个子域。例如，GF(2)GF(2)是是GF(2GF(2m m)的一个子域，类似于实数域是复数域的一个子域。的一个子域，类似于实数域是复数域的一个子域。在在GF(2GF(2m m)中，除了数字中，除了数字0 0和和1 1，还有一个特殊的元素，还有一个特殊的元素，用一个新的符号用一个新的符号 表示，表示，GF(2GF

19、(2m m)中的任何非零元素都中的任何非零元素都可以由可以由 的幂次表示。的幂次表示。30元素的无限集元素的无限集F F，就是根据元素，就是根据元素0,1,0,1,形成的，后一个形成的，后一个元素通过前一项乘以元素通过前一项乘以 而得到。而得到。为了从为了从F F中得到有限元素的集合中得到有限元素的集合GF(2m)GF(2m)，必须对，必须对F F域施加域施加一个条件，使它只能含有一个条件，使它只能含有2m2m个元素并且对乘法封闭。个元素并且对乘法封闭。元素集对乘法封闭的条件可由下面的不可约多项式表示：元素集对乘法封闭的条件可由下面的不可约多项式表示：根据这个限制条件，任何幂次根据这个限制条件

20、，任何幂次2m-1的域元素都可降阶的域元素都可降阶为如下所示的幂次小于为如下所示的幂次小于2m-1的元素。的元素。,0,1,0202jjF0)12()12(,01mm即：11)12()12(nnnmm一、数学基础一、数学基础31因此，从无限序列因此，从无限序列F F中形成的有限序列如下：中形成的有限序列如下：因此，有限域因此，有限域GF(2GF(2m m)的元素由下式给出：的元素由下式给出：,0,1,0202220212222mmmmF,1,0)2(222mmGF一、数学基础一、数学基础322、自然基底（基底元素）、自然基底（基底元素）展域展域GF(qGF(qm m)中的每一个元素都可以用次数

21、低于中的每一个元素都可以用次数低于m m的的 的多项式表示。即的多项式表示。即GF(qGF(qm m)中中m m个元素集合个元素集合1,1,2 2,m-1m-1 是线性无关的。因此称这组元素为自是线性无关的。因此称这组元素为自然基底或基底元素，也称为本原基底。然基底或基底元素，也称为本原基底。例如，例如，在在GF(2GF(23 3)中，中，1,1,2 2 就是它的自然基就是它的自然基底。这可以在后面通过求本原多项式底。这可以在后面通过求本原多项式f(x)=1+x+xf(x)=1+x+x3 3的根来说明。的根来说明。一、数学基础一、数学基础333、有限域元素的多项式表示、有限域元素的多项式表示在

22、有限域在有限域GF(2GF(2m m)中，中，2 2m m个元素中的任意一个都可以由个元素中的任意一个都可以由阶数小于或等于阶数小于或等于m-1m-1的一个多项式表示。多项式的阶的一个多项式表示。多项式的阶数是它的最高幂指数，多项式的变量数是它的最高幂指数，多项式的变量x x在在GF(2)GF(2)上。上。将将GF(2GF(2m m)中的每个非中的每个非0 0元素用多项式元素用多项式 i i(x)(x)表示，其系表示，其系数至少有一个不为数至少有一个不为0 0。对于。对于i=0,1,2,2i=0,1,2,2m-2m-2,有：有：11,22,1,0,)(mmiiiiiixxxx一、数学基础一、数

23、学基础344、有限域、有限域GF(2m)中的加法中的加法有限域中两个元素的加法定义为两个元素的多项式中有限域中两个元素的加法定义为两个元素的多项式中同幂次项系数进行模同幂次项系数进行模2加，即：加，即：5、有限域的本原多项式、有限域的本原多项式GF(q)上的一个上的一个m阶的不可约多项式阶的不可约多项式f(x)，如果，如果f(x)能能整除整除xn+1的最小正整数的最小正整数n满足满足n=2m-1，则该多项式，则该多项式是本原的。是本原的。11,1,1,1,0,0,)()()(mmjmijijijixx一、数学基础一、数学基础35一、数学基础一、数学基础6、有限域本原多项式的根、有限域本原多项式

24、的根代数基本定理证明，对于代数基本定理证明，对于GF(q)GF(q)上幂次为上幂次为m m的多项式的多项式f(x)f(x)，必然有，必然有m m个根。个根。然而，然而，GF(q)GF(q)中的元素，例如中的元素，例如 GF(2)GF(2)中的元素中的元素0 0和和1 1，不能满足多项式不能满足多项式f(x)f(x)有有m m个根的要求，即个根的要求，即f(x)mf(x)m个根个根不在不在GF(q)GF(q)中，而在其它域中。中，而在其它域中。例如，例如，GF(2)GF(2)上的本原多项式上的本原多项式f(x)=1+x+x3f(x)=1+x+x3有三个根，有三个根，这三个根位于扩展域这三个根位于

25、扩展域GF(23)GF(23)中。中。一个本原多项式的根必须有至少一个本原元素。一个本原多项式的根必须有至少一个本原元素。所谓本原元素，即该元素所在域中的所有元素都可以所谓本原元素，即该元素所在域中的所有元素都可以通过该元素幂次的不断升高来得到。通过该元素幂次的不断升高来得到。36求求f(x)=1+x+xf(x)=1+x+x3 3的根。的根。解：解：用用 来定义来定义f(x)f(x)的根，然后通过枚举找到所有的的根，然后通过枚举找到所有的根。根。令令 f(f()=0)=0，即，即1+1+3 3=0=0，则，则 3 3=1+=1+4 4=3 3=(1+1+)=)=+2 2 同理：同理：5 5=1

26、+=1+2 2 6 6=1+=1+2 2 7 7=0 0=1=1 枚举：（枚举：（1 1）f(f(0 0)=1)=1，所以，所以 0 0=1=1不是根，不是根，（2 2）f(f()=0)=0，所以，所以 是根是根 （3 3）f(f(2 2)=0)=0，所以，所以 2 2是根是根 （4 4）f(f(4 4)=0)=0，所以，所以 4 4是根是根 其余元素均不是根。其余元素均不是根。一、数学基础一、数学基础37根据上例的计算，结合基底元素的定义，可以得到多根据上例的计算，结合基底元素的定义，可以得到多项式为项式为f(x)=1+x+xf(x)=1+x+x3 3的的GF(2GF(23 3)中，基本元素

27、中，基本元素xx0 0,x,x1 1,x,x2 2 与与GF(2GF(23 3)中中8 8个元素的影射关系。见下表。个元素的影射关系。见下表。一、数学基础一、数学基础38基本元素基本元素X X0 0X X1 1X X2 2域域元元素素0 00 01 12 23 34 45 56 67 70 01 10 00 01 10 01 11 11 10 00 01 10 01 11 11 10 00 00 00 00 01 10 01 11 11 10 0一、数学基础一、数学基础39二、二、RS码码)()()(22txxxxg)2(mjGF1、RS码的定义码的定义在有限域在有限域GF(2m)(m1)中，

28、以该域元素为根的，且码中，以该域元素为根的，且码长长 为为n=2m-1的本原的本原BCH码称为码称为RS码。（比较：码。（比较：BCH码的码字取自码的码字取自GF(q)域，而其生成多项式的根则域，而其生成多项式的根则取自取自GF(qm)域）域）2、RS码的生成多项式码的生成多项式RS码中，码字取值的域与其生成多项式的根的域完码中，码字取值的域与其生成多项式的根的域完全相同，均取自全相同，均取自GF(2m)(m1)域域。因此，。因此，RS码生成码生成多项式可以由一次多项式的乘积构成。即：多项式可以由一次多项式的乘积构成。即：40 3 3、RSRS码的距离特性码的距离特性 RSRS码最有价值的特点

29、是：其最小距离码最有价值的特点是：其最小距离d dminmin比监督位比监督位个数多个数多1 1，即：如果可纠正的错误码元数为，即：如果可纠正的错误码元数为t t，则有，则有n-n-k=2tk=2t。由线性码理论可知，有。由线性码理论可知，有n-kn-k个校验位的线性分组个校验位的线性分组码所能得到的最大的最小距离是码所能得到的最大的最小距离是n-k+1n-k+1。可见，。可见，RSRS码是码是一个有最大的最小距离的线性分组码。因此，一个有最大的最小距离的线性分组码。因此，RSRS码常码常表示为（表示为（n n，k k，d dminmin），），RSRS码也常常表示为（码也常常表示为（2 2m

30、 m-1-1，2 2m m-1-2t-1-2t）。）。二、二、RS码码41设设GF(2GF(23 3),),构造一个构造一个t=2t=2的的RSRS码码因为因为GF(2GF(23 3),),所以所以m=3m=3，n=2n=23 3-1=7-1=7 又因为又因为t=2t=2，所以，所以n-k=4n-k=4，k=3k=3 因此，这是一个八进制的（因此，这是一个八进制的（7,3,57,3,5）RSRS码，生成码，生成多项式为：多项式为：在上式中，加法按照二进制域计算，即在上式中，加法按照二进制域计算，即+1=-1，并且按照并且按照mod2的规则运算。的规则运算。320334432)()()()(xx

31、xxxxxxxg二、二、RS码码42二、二、RS码码4、RS码的编码码的编码原理与原理与BCH码相同，用信息多项式乘以生成多项式码相同，用信息多项式乘以生成多项式就可以得到码字多项式。就可以得到码字多项式。编码电路编码电路BCH码的结构相似，所不同的是：反馈支码的结构相似，所不同的是：反馈支路所乘的系数不再是二进制的路所乘的系数不再是二进制的1或或0，而是，而是m进制的元进制的元素，或者说是素，或者说是m个二进制比特。个二进制比特。4333K3输出K2输入0K1x0 x1x2x3x4二、二、RS码码44二、二、RS码码5、RS码的译码码的译码RS码的译码原理也与前面所述的循环码的相同，但码的译

32、码原理也与前面所述的循环码的相同，但是具体实现则要复杂得多。而且随着是具体实现则要复杂得多。而且随着m和和t的增加，的增加，复杂度增加。因为对于二进制码，只要找到错误的位复杂度增加。因为对于二进制码，只要找到错误的位置，就可以通过取反实现纠错。而对于非二进制的置，就可以通过取反实现纠错。而对于非二进制的RS码，不但要找到错误的位置，还要知道这些位置码，不但要找到错误的位置，还要知道这些位置上的正确取值。上的正确取值。45二、二、RS码码6、RS码的纠错能力码的纠错能力码长码长n=2m-1符号符号,或或m(2m-1)比特比特信息段信息段k符号，或符号，或km比特比特监督段监督段n-k=2t符号，

33、或符号，或m(n-k)比特比特最小码距最小码距d=2t+1符号，或符号，或m(2t+1)比特比特RS码的一个码元包含码的一个码元包含m个比特，当它纠正了一个码个比特，当它纠正了一个码元的错误时，就有可能纠正了元的错误时，就有可能纠正了m个比特的突发错误。个比特的突发错误。例如：虽然例如：虽然RS(7，3)码和码和RS(15，11)码可纠正的一码可纠正的一个码组内的码元错误数均为个码组内的码元错误数均为2，但，但RS(7，3)码可纠正码可纠正的一个码组内的比特错误数为的一个码组内的比特错误数为6，而，而RS(15，11)码则码则为为8。46总结总结 本节课主要内容本节课主要内容软判决译码和硬判决译码软判决译码和硬判决译码Viterbi 译码的性能译码的性能RS码码47习题与思考题习题与思考题教材教材P169P169，4.4 4.8 4.184.4 4.8 4.18Institute of Communications Engineering 谢谢 谢！谢！