通信原理第9章-信道编码(2)

8
dmin与码的纠错和检错能力
n
在一个码组集合中，如果码组间的最小码距满足
dmin ≥ e + 1
则该码集中的码组可以检测e位错码。
n
在一个码组集合中，如果码组间的最小码距满足
dmin ≥ 2t + 1
则该码集中的码组可以纠正t位错码。
9
dmin与码的纠错和检错能力
n
在一个码组集合中，如果码组间的最小码距满足
dmin ≥ t + e + 1
(e > t )
则该码集中的码组可以纠正t位错码，同时具有检测e 位错码的能力。
10
编码效率
n
n
要想提高码组的抗干扰能力，最根本的措施是增加监 督码元，即加大码距，但是相应地冗余信息增加，传 输效率降低。 对于分组码(n, k)来说，定义编码效率
k η= n
12
奇偶监督码(奇偶校验码)
n
(n, n - 1) 分组码
n n
奇校验码: 码组中“1”的个数保持为奇数 偶校验码: 码组中“1”的个数保持为偶数
n
n
n
最小码距为 2 ，只能检测出单个或奇数个错误，检错 能力低，但编码效率随着n的增加而提高。 在传递标准ASCII码时，通常采用(8, 7)码
例.偶校验： cn−1 + cn−2 + ! + c1 + c0 = 0, mod 2 n−1 # & c = % cn−1 , cn−2 , ! , c1 , c0 = ∑ ci ( $ ' i =1
00 01 10 11
00 0 01 1 10 1 11 0
13
差错控制
n
n
差错控制：在数字通信系统中,利用信道编码在 接收端发现差错并纠正差错，提高系统的可靠 性。 差错控制方式
n
η 越大，说明信息码元所占的比重越大，码组传输信息 的有效性越高。
11
差错控制编码的效果
n
假设在随机信道中发送“0”时的错误概率和发送“1” 时的错误概率均等于p，且p<<1.
n
在码长为n的码组中恰好发生i个错码的概率 n! n− i i i Pn ( i ) = C n p (1 − p ) ≈ pi i !( n − i ) !
n n
前向纠错(FEC) 反馈重传/检错重发/自动请求重传(ARQ)
n n n
停等重传 后退重传 选择重传
n
混合纠错(HEC): ARQ与FEC的结合
14
前向纠错(FEC)
n
发送端对信息码元进行编码处理，使发送的码元具有 纠错能力。接收端收到这些码元之后，通过译码能自 动发现并纠正传输中出现的错误。
i i 不加纠错时的误码组率： Pn = ∑ Pn ( i ) = ∑ C n p (1 − p ) i =1 i =1 n n n n n− i
n
n
纠错能力为t位时的误码组率： Pn =
i = t +1
n
∑
Pn ( i ) =
i = t +1
i i C ∑ n p (1 − p )
n− i
码组的最小距离：任意两个不同码字间汉明距离的 最小值
d min = min d ci ,c j
i≠ j
(
)
n
码组的最小重量：除全零码外码字的最小重量
Wmin = min W ( c i )
ci ≠ 0
n
定理：对于所有线性分组码，有 dmin = wmin .
证明： ∀c ∈ C , W ( c ) = d ( c,0)
6
n
按约束关系
n
n
信道编码的分类
n
按编码方式
n
n
分组码：将信息序列分成独立的若干组进行编码。编码后，每 组中的监督码元只与本组的信息码元有关，而与其他组的信息 码元无关。 n 编码后的码元序列每 n 位为一组，其中 k 个是信息码元， r 个 是附加的监督码元，r = n – k，通常记为(n, k)。 卷积码：编码后的序列也划分为码组，但监督码元不仅与本码 组的信息码元有关，还与前面几个码组有约束关系。 系统码：编码后的信息序列中包含原始信息码元(位置可能变化) 非系统码：编码后的信息序列中不包含原始信息码元 二进制码 多进制码
25
线性分组码的每个码字都是G各行矢量的线性组合。
生成矩阵
n
例. 00
01 10 11
00000 01111 10100 11011
⎡10100 ⎤ ∴ G = ⎢ ⎥ 01111 ⎣ ⎦
⎡10100 ⎤ ⎡ ⎣u1 u0 ⎤ ⎦ ⎢ 01111⎥ ⎣c4 c3 c2 c1 c0 ⎤ ⎦ = ⎡ ⎣u1 u0 ⎤ ⎦G = ⎡ ⎣ ⎦
c6 = u2 信息位 c5 = u1 c4 = u0
监督位
c3 = u2 ⊕ u0 c2 = u2 ⊕ u1 ⊕ u0 c1 = u2 ⊕ u1 c0 = u1 ⊕ u0
c = uG
!1 0 0 1 1 1 0$ # & c = ( c6 c5 c4 c3c2c1c0 ) = (u2u1u0 ) #0 1 0 0 1 1 1& # "0 0 1 1 1 0 1& %
n n
需要使用反向信道，而且实时性较差 所用的检错译码器与FEC方式中的纠错译码器相比，成本和复 杂性均低得多
16
检错重传方式
n
停等重传ARQ
17
检错重传方式
n
返回重传ARQ
18
检错重传方式
n
选择重传ARQ
19
混合纠错(HEQ)
n
发送端经过编码后发出的码组不但能够检测错误，还具 有一定的纠错能力。如果接收端收到的码组错误较少， 则自动进行纠错；如果错误太多，超出了码的纠错能力 但尚能检测时，接收端通过反向信道请求发送端重发一 遍。
n
突发差错信道(有记忆信道)
n n n
n n
混合信道：既存在随机错码又存在突发错码的信道。 对不同类型的信道，需设计不同的信道编码
n n n
纠独立随机差错码：大部分分组码和卷积码 纠突发差错码：分组码和卷积码中的几类、交织码 纠混合差错码：级联码
4
信道编码的基本原理
if c = ci ⊕ c j ⇒ d ( c i ⊕ c j ,0 ) = d ( c i ,c j ) = W ( c )
即：对应于任意一个码字的重量，都存在某两个码字的汉明 距离与之相等；对应于任意两个码字的汉明距离，也总能找 到某个码字的重量与之相等。
23
生成矩阵
n
例. 二元(7,3)线性分组码
n n n n n
合理设计基带信号 选择调制、解调方式 采用均衡技术 增大发送功率 仍然达不到要求，就需要信道编码
3
信道分类(按差错类型)
n
随机差错信道(无记忆信道)
n n n
错码随机出现，且错码之间统计独立(无记忆性) 原因 ：高斯白噪声引起(信道本身的传输特性较为理想)。 太空信道、卫星信道、同轴电缆、光缆信道、视距微波信道 错码成串出现(记忆性)，集中在很短的时间内 原因：脉冲噪声或信道传输特性不理想(衰落, ISI)引起 短波信道、移动通信信道、散射信道、明线和电缆信道
n n
n
不需要反向信道，适合于只能提供单向信道的场合。 接收端能自动纠错，不会因发送端反复重发而延误时间，系 统实时性好。 所用的纠错码纠错能力越强，纠错后的误码率就越低，译码 设备则越复杂。
Leabharlann Baidu
15
反馈重传(ARQ)
n
发送端经编码后发出能够检错的码元，接收端收到后如 果检测出错误，则通过反向信道通知发送端重发，直至 接收端确认收到正确信息为止。
n
“11010”和“01101” 的汉明距离: 4
n
最小汉明距离 ( 最小码距 ) d min ：在由多个等长码组构 成的码组集合中，任意两个码组之间距离的最小值。 它是衡量一种编码方案纠错和检错能力的重要依据。
准用 码组
000 111
dmin = 3 dmin = 1
000 001 010 100 111 011 101 110
n
生成矩阵G：一个n位的码组，可以由k个信息位组成 的信息码组u通过一个线性变换矩阵G来产生。
24
生成矩阵
n
对于(n, k) 线性分组码，假定 x 1 = ! "1000… 0# $ x =! "0100… 0# $
2
g1
g2
xk = ! "0000… 1# $
!
gk
!
∀ u=" #u1 u2 … uk $ % = ∑ ui x i
准用 码组 禁用 码组 准用 码组 禁用 码组
n
例. 重复码
A B
0 1 无检错和纠 错能力
00 11 可检测1 位错码
01 10
000 111
001 011
010 100 101 110
可检测1到2位错码， 或纠正一位错码
5
信道编码的分类
n
按信道编码的功能
n n n
检错码：只能检测错误； 纠错码：可以纠正错误； 纠删码：兼具纠错和检错能力，在发现不可纠正 的错误时，可以发出错误指示或将其删除。 线性码：信息码元与监督码元之间的约束关系是 线性的，即满足一组线性方程 非线性码：信息码元与监督码元之间的约束关系 是非线性的
i =1
n
n
c = ∑ ui g i = uG
i =1
"g % ! $ 1' # $g 2 ' = # G≡ $! ' # $ ' # $ #g k ' & # "
n
g11 g21 ! gk 1
g12 ! g1n $ & g22 … g2 n & k× n 阶矩阵，各 行线性无关 & ! " ! & gk 2 … gkn & %
7
n
按编码后是否包含原始信息码元
n n
n
根据码元取值
n n
码组的汉明距离
n n
码长：码组或码字中编码的总位数 码重：码组中非零码元的数目
n
例. “11010”: 码长为5，码重为3
n
汉明 (Hamming) 距离：两个等长码组中对应码位上具 有不同码元的位数，简称码距。
第九章 信道编码
北京邮电大学信息与通信工程学院 无线通信系统与网络实验室(WCSN)
刘丹谱
dpliu@bupt.edu.cn 62282289
第九章
n n
信道编码
信道编码的基本概念 线性分组码
2
为什么需要信道编码
n n
在数字信号的传输中，实际信道存在噪声和干扰，会 导致接收端的误判，这样就产生了差错。 可采取的办法：
26
典型生成矩阵
n
# 典型生成矩阵： G = ! " I k Q$
n
对于任意的(n, k) 线性分组码，总可通过初等行变换及列交换 将其非系统码生成矩阵变换为另一等价的系统码生成矩阵。两 等价生成矩阵生成的线性分组码的检、纠错能力相同。
n n
全零序列是线性分组码的一个码字 如果信息序列 u1映射到码字 c1， u2映射到 c2，则 u1⊕ u2 映射到码字c1⊕c2。
例. C = { 00000 10100 00 00000 01 01111 10 10100 11 11011 01111 11011 }
22
线性分组码
n
c4 = u1 c3 = u0 c2 = u1 ⊕ u0 c1 = u0 c0 = u0
⎡10100 ⎤ ! I Q# = G = ⎢ " 2 $ ⎥ 01111 ⎣ ⎦
n
系统码：信息码组以不变的形式出现在线性分组码任意k位， 通常是码组的前k位：cn-1, cn-2, …, cn-k。
n
信道编码
n
n
发送端：在待发送的信息序列中加入一些多余的码元(监督 码元)，这些监督码元和信息码元之间以某种确定的规则相互 关联，即满足一定的约束关系。 接收端：按既定的规则检验信息码元与监督码元之间的约束 关系。约束关系被破坏就意味着传输中有差错(检错)；借助 于约束关系甚至还可以纠正错误(纠错)。
1 n n− i i i 误比特率近似： Pb = ∑ iC n p (1 − p ) n i = t +1
n
−3 例n=7, p=10-3： P7 (1) ≈ 7 p = 7 ⋅ 10
P7 ( 2) ≈ 21 p2 = 2.1 ⋅ 10−5 P7 ( 3) ≈ 35 p3 = 3.5 ⋅ 10−8
n
作业：P334 9.1~9.3
20
第九章
n n
信道编码
信道编码的基本概念 线性分组码
21
线性分组码的定义
n n n
码字/组ci：(n, k)分组码输出的长度为n的序列，完全由 M=2k个二进制输入序列决定 输出码C：由M = 2k个码字ci组成： C = {c1 ,c 2 ,… ,c M } 如果(n, k)分组码中任意两个码字的线性组合仍是分组码 的一个码字，那么称该分组码是线性的。 对于二进制码， c i ,c j ∈ C ⇒ c i ⊕ c j ∈ C