信息论与编码(杜玉华)教案.ppt

定理1 若纠错码的最小距离为dmin，那么如下三个结论的任何一个结论独立成立： ① 若要发现e个独立差错，则要求最小码距 ② 若要纠正t个独立差错，则要求最小码距 ③ 若要求发现e个同时又纠正t个独立差错，则 8.3 线性分组码 定理8.1 任何最小距离dmin的线性分组码，其检错能力为（dmin-1）, 纠错能力t为 定理8.2 线性分组码的最小距离等于码集中非零码字的最小重量 dmin = min {w (C i )} C i?C 及C i ? 0 8.3 线性分组码 定理8.3 (n,k) 线性分组码最小距离等于dmin的充要条件是：校验矩阵H中有（dmin-1)列线性无关。 定理8.4 (n,k) 线性分组码的最小距离必定小于等于 (n-k+1) 8.3 线性分组码 例：(7，4)线性码 8.3 线性分组码 各列都不相同，任意2列之和不等于0，2列线性无关；任意2列之和一定等于矩阵中某一列，任意3列线性相关。所以该码的最小距离为3，小于n-k +1=4。 (n,k)线性码最小距离dmin的上边界是n-k+1。如果我们设计的(n,k)线性码的dmin达到了n-k+1，就是达到了设计性能的极点。因此，dmin=n-k+1的码称为极大最小距离码 (MDC – Maximized minimum Distance Code)。 8.3 线性分组码 定义差错图案E 二进制码中模2加与模2减是等同的，因此有E = R+C 及R = C+E 1. 伴随式S的定义 因为CHT = 0 所以RHT=(C+E) HT=CHT+EHT= EHT 8.3 线性分组码 如果收码无误：必有R=C即E=0， 则EHT= 0 RHT = 0。 如果收码有误：即E ? 0， 则RHT = EHT? 0。 在HT固定的前提下，RHT仅仅与差错图案E有关，而与发送码C无关。定义伴随式S S = (sn-k-1,…,s1,s0) = RHT = EHT 8.3 线性分组码 2. 伴随式S的意义 从物理意义上看，伴随式S并不反映发送的码字是什么，而只是反映信道对码字造成怎样的干扰。 差错图案E是n重矢量，共有2n个可能的组合，而伴随式S是(n-k)重矢量，只有2n-k个可能的组合，因此不同的差错图案可能有相同的伴随式。 8.3 线性分组码 接收端收到R后，因为已知HT，可求出S=RHT ；如果能知道对应的E，则通过C = R+E而求得C。 8.3 线性分组码 3. 差错图案E的求解 可以通过解线性方程求解E： 8.3 线性分组码 得到线性方程组： sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+ e0 h(n-k-1)0 ? s1 = en-1h1(n-1) +… + e1 h11 + e0 h10 s0 = en-1h0(n-1) +… + e1 h01 + e0 h00 8.3 线性分组码 上述方程组中有n个未知数en-1,… e1,e0 ，却只有n-k个方程，可知方程组有多解。 在有理数或实数域中，少一个方程就可能导致无限多个解，而在二元域中，少一个方程导致两个解，少两个方程四个解，以此类推，少n-( n-k) = k个方程导致每个未知数有2k个解。到底取哪一个作为附加在收码R上的差错图案E的估值呢？ 8.3 线性分组码 概率译码：把所有2k个解的重量(差错图案E中1的个数)作比较，选择其中最轻者作为E的估值。该方法概念上很简单但计算效率不高。 依据：若BSC信道的差错概率是p，则长度n的码中错误概率 ： 8.3 线性分组码 0个错 1个错 2个错 … n个错 (1-p)n p(1-p)n-1 p2(1-p)n-2 pn … 由于