信息论与编码原理-第8章-线性分组码.ppt

第1页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,信息论与编码原理,（第八章）线性分组码,第2页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,第8章 线性分组码,8.1 一般概念 8.2 一致监督方程和一致监督矩阵 8.3 线性分组码的生成矩阵 8.4 线性分组码的编码 8.5 线性分组码的最小距离、检错和纠错能力 8.6 线性分组码的译码 8.7 线性分组码的性能 8.8 汉明码 8.9 由已知码构造新码的方法 8.10 GSM 的信道编码总体方案 8.11 线性分组码的码限,第3页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.1 一般概念,(1) 线性分组码的编码：编码过程分为两步： 把信息序列按一定长度分成若干信息码组, 每组由 k 位组成; 编码器按照预定的线性规则（可由线性方程组规定），把信息码组变换成 n 重（nk）码字，其中 (nk) 个附加码元是由信息码元的线性运算产生的。 (2) 线性分组码的码字数：信息码组长 k 位，有 2k 个不同的信息码组，有 2k 个码字与它们一一对应。,第4页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.1 一般概念,(3) 术语 线性分组码：通过预定的线性运算将长为 k 位的信息码组变换成 n 重的码字 (nk)。由 2k 个信息码组所编成的 2k个码字集合，称为线性分组码。 码矢：一个 n 重的码字可以用矢量来表示： C=(cn1,cn1,c1,c0 ) (n,k) 线性码：信息位长为 k，码长为 n 的线性码。 编码效率/编码速率/码率/传信率：R=k /n。它说明了信道的利用效率，R 是衡量码性能的一个重要参数。,返回目录,第5页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.2 一致监督方程和一致监督矩阵,(1) 一致监督方程,(2) 举 例,(3) 一致监督矩阵,(4) 一致监督矩阵特性,第6页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.2 一致监督方程和一致监督矩阵,(1) 一致监督方程 构成码字的方法：编码是给已知信息码组按预定规则添加监督码元，构成码字。 在 k 个信息码元之后附加 r(r=nk) 个监督码元，使每个监督元是其中某些信息元的模 2 和。 举例：k=3, r=4，构成 (7,3) 线性分组码。设码字为： (c6,c5,c4,c3,c2,c1,c0) c6,c5,c4为信息元，c3,c2,c1,c0为监督元，每个码元取“0”或“1” 监督元按下面方程组计算：,第7页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.2 一致监督方程和一致监督矩阵,(1) 一致监督方程 一致监督方程/一致校验方程：确定信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。 为什么叫线性分组码？由于一致监督方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。,返回目录,第8页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.2 一致监督方程和一致监督矩阵,(2) 举例 信息码组 (101)，即c6=1, c5=0, c4=1 代入 (7.2.1) 得： c3=0, c2=0, c1=1, c0=1 由信息码组 (101) 编出的码字为 (1010011)。其它 7 个码字如表8.2.1。,返回目录,第9页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.2 一致监督方程和一致监督矩阵,(3) 一致监督矩阵 为了运算方便，将式(7.2.1)监督方程写成矩阵形式，得：,将式(8.2.2)可写成： H CT=0T 或 C HT=0 CT、HT、0T 分别表示 C、H、0 的转置矩阵。,第10页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.2 一致监督方程和一致监督矩阵,(3) 一致监督矩阵 系数矩阵 H 的后四列组成一个 (44) 阶单位子阵，用 I4 表示，H 的其余部分用 P 表示：,第11页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.2 一致监督方程和一致监督矩阵,(3) 一致监督矩阵 推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r(r=nk) 个监督元与信息元之间的关系可由下面的线性方程组确定：,返回,第12页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.2 一致监督方程和一致监督矩阵,(3) 一致监督矩阵 令上式的系数矩阵为 H，码字行阵列为 C ：,返回目录,第13页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(4) 一致监督矩阵特性 对 H 各行实行初等变换，将后面 r 列化为单位子阵，得到下面矩阵，行变换所得方程组与原方程组同解。 监督矩阵 H 的标准形式：后面 r 列是一单位子阵的监督矩阵 H。,8.2 一致监督方程和一致监督矩阵,第14页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(4) 一致监督矩阵特性 H 标准形式的特性 H 阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的模 2 和为 0。 H 的标准形式表明了相应的监督元是由哪些信息元决定的。例如 (7,3) 码的 H 阵的第一行为 (1011000)，说明第一个监督元等于第一个和第三个信息元的模 2 和，依此类推。 H 阵的 r 行代表了 r 个监督方程，由 H 所确定的码字有 r 个监督元。 为了得到确定的码，r 个监督方程（或 H 阵的 r 行）必须是线性独立的，这要求 H 阵的秩为 r。 若把 H 阵化成标准形式，只要检查单位子阵的秩，就能方便地确定 H 阵本身的秩。,8.2 一致监督方程和一致监督矩阵,参见方程,返回目录,第15页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.3 线性分组码的生成矩阵,(1) 线性码的封闭性,(2) 线性分组码的生成矩阵,(3) 生成矩阵与一致监督矩阵的关系,(4) 对偶码,第16页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(1) 线性码的封闭性 线性码的封闭性：线性码任意两个码字之和仍是一个码字。 定理7.3.1：设二元线性分组码 CI (CI 表示码字集合) 是由监督矩阵H 所定义的，若 U 和 V 为其中的任意两个码字，则 U +V 也是 CI 中的一个码字. 证明：由于 U 和 V 是码 CI 中的两个码字，故有：HU T=0T HV T=0T ，那么 H(U+V)T=H(U T+V T)=HU T+HV T=0T 即 U+V 满足监督方程，所以 U+V 一定是一个码字。 一个长为 n 的二元序列可以看作是 GF(2) (二元域) 上的 n 维线性空间中的一点。所有 2n 个矢量集合构成了GF(2)上的 n 维线性空间 Vn。把线性码放入线性空间中进行研究，将使许多问题简化而比较容易解决。 (n,k) 线性码是 n 维线性空间 Vn 中的一个 k 维子空间 Vk。,8.3 线性分组码的生成矩阵,返回目录,第17页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 线性分组码的生成矩阵 生成矩阵的来由：在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中，一定存在 k 个线性独立的码字：g1,g2, gk。码 CI 中其它任何码字 C 都可以表为这 k 个码字的一种线性组合，即：,8.3 线性分组码的生成矩阵,第18页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 线性分组码的生成矩阵 生成矩阵定义：由于矩阵 G 生成了 (n,k) 线性码，称矩阵 G 为 (n,k) 线性码的生成矩阵。,8.3 线性分组码的生成矩阵,第19页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 线性分组码的生成矩阵 生成矩阵G 的特性 G 中每一行 gi=(gi1,gi2, gin ) 都是一个码字； 对每一个信息组 m，由矩阵 G 都可以求得 (n,k) 线性码对应的码字。 (n,k) 线性码的每一个码字都是生成矩阵 G 的行矢量的线性组合，所以它的 2k 个码字构成了由 G 的行张成的 n 维空间的一个 k 维子空间 Vk。,8.3 线性分组码的生成矩阵,第20页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 线性分组码的生成矩阵 线性系统分组码 线性系统分组码的构成：通过行初等变换，将 G 化为前 k 列是单位子阵的标准形式。,8.3 线性分组码的生成矩阵,第21页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 线性分组码的生成矩阵 线性系统分组码 线性系统分组码定义：用标准生成矩阵 Gkn 编成的码字，前面 k 位为信息位，后面 r=nk 位为校验位，这种信息位在前校验位在后的线性分组码称为线性系统分组码。 当生成矩阵 G 确定之后，(n,k) 线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。,8.3 线性分组码的生成矩阵,第22页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 线性分组码的生成矩阵 举例：(7,4) 线性码的生成矩阵为：,8.3 线性分组码的生成矩阵,返回目录,第23页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(3) 生成矩阵与一致监督矩阵的关系 由于生成矩阵 G 的每一行都是一个码字，所以 G 的每行都满足： Hrn(C1n)T=(01r)T，则有：Hrn(Gkn)T=(0kr)T 或 Gkn(Hrn)T=0kr 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换。,8.3 线性分组码的生成矩阵,第24页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(3) 生成矩阵与一致监督矩阵的关系 由于生成矩阵 G 的每一行都是一个码字，所以 G 的每行都满足： Hrn(C1n)T=(01r)T，则有：Hrn(Gkn)T=(0kr)T 或 Gkn(Hrn)T=0kr 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换。,8.3 线性分组码的生成矩阵,第25页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(3) 生成矩阵与一致监督矩阵的关系 举例： 已知 (7,4) 线性系统码的监督矩阵为：,8.3 线性分组码的生成矩阵,Q,QT,返回目录,第26页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(4) 对偶码 对偶码：对一个 (n,k) 线性码CI，由于 Hrn(Gkn)T=(0kr)T，如果以G 作监督矩阵，而以 H 作生成矩阵，可构造另一个码 CId，CId是一个 (n,nk) 线性码，称码 CId 为原码的对偶码. 例如： (7,4) 线性码的对偶码是 (7,3) 码： (7,3) 码的生成矩阵 G(7,3) 是 (7,4) 码监督矩阵 H(7,4),8.3 线性分组码的生成矩阵,返回目录,第27页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(n,k) 线性码的编码：根据线性码的监督矩阵或生成矩阵将长为 k 的信息组变换成长为 n(nk) 的码字。 利用监督矩阵构造 (7,3) 线性分组码的编码电路 设码字为：C=(c6c5c4c3c2c1c0) 码的监督矩阵为：,8.4 线性分组码的编码,第28页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,利用监督矩阵构造 (7,3) 线性分组码的编码电路： 根据上面方程组可直接画出 (7,3) 码的并行编码电路和串行编码电路:,8.4 线性分组码的编码,返回目录,第29页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.5 线性分组码的最小距离、检错和纠错能力,(1) 汉明距离、汉明重量和汉明球,(2) 最小距离与检、纠错能力,(3) 线性码的最小距离与监督矩阵的关系,第30页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(1) 汉明距离、汉明重量和汉明球 汉明距离（距离）：在 (n,k) 线性码中，两个码字 U、V 之间对应码元位上符号取值不同的个数，称为码字 U、V 之间的汉明距离。 线性分组码的一个码字对应于 n 维线性空间中的一点，码字间的距离即为空间中两对应点的距离。因此，码字间的距离满足一般距离公理：,8.5 线性分组码的最小距离、检错和纠错能力,第31页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(1) 汉明距离、汉明重量和汉明球 最小距离 dmin：在 (n,k) 线性码的码字集合中，任意两个码字间距离最小值，叫做码的最小距离。若 C(i) 和 C(j) 是任意两个码字，则码的最小距离表示为： 码的最小距离是衡量码的抗干扰能力（检、纠错能力）的重要参数。码的最小距离越大，码的抗干扰能力就越强。,8.5 线性分组码的最小距离、检错和纠错能力,第32页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(1) 汉明距离、汉明重量和汉明球 汉明球：以码字 C 为中心，半径为 t 的汉明球是与 C 的汉明距离t 的向量全体 SC(t) ： 任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离 dmin。,8.5 线性分组码的最小距离、检错和纠错能力,第33页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(1) 汉明距离、汉明重量和汉明球 汉明球：,8.5 线性分组码的最小距离、检错和纠错能力,返回,第34页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(1) 汉明距离、汉明重量和汉明球 汉明重量（码字重量）W：码字中非 0 码元符号的个数，称为该码字的汉明重量。 在二元线性码中，码字重量就是码字中含“1”的个数。 最小重量 Wmin ：线性分组码 CI 中，非 0 码字重量最小值，叫做码 CI 的最小重量： Wmin =minW(V),VCI ,V0,8.5 线性分组码的最小距离、检错和纠错能力,第35页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(1) 汉明距离、汉明重量和汉明球 最小距离 与最小重量 的关系：线性分组码的最小距离等于它的最小重量。 证明： 设线性码 CI，且 UCI, VCI 又设 UV=Z 由线性码的封闭性知，ZCI 因此，d(U,V)=W(Z) 由此可推知，线性分组码的最小距离必等于非 0 码字的最小重量。,8.5 线性分组码的最小距离、检错和纠错能力,返回目录,第36页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力 检错能力：如果一个线性码能检出长度l 个码元的任何错误图样，称码的检错能力为 l。 纠错能力：如果线性码能纠正长度t 个码元的任意错误图样，称码的纠错能力为 t。 最小距离与检纠错能力的关系：线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。,8.5 线性分组码的最小距离、检错和纠错能力,第37页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力 最小距离与纠错能力：(n,k) 线性码能纠 t 个错误的充要条件是码的最小距离为： dmin2t+1 (8.5.1) 证明： 设发送的码字为 V；接收的码字为 R；U 为任意其它码字 则矢量V、R、U 间满足距离的三角不等式： d(R,V)+d(R,U)d(U,V) (8.5.2) 设信道干扰使码字中码元发生错误的实际个数为 t ，且 t t d(R,V)t t (8.5.3),8.5 线性分组码的最小距离、检错和纠错能力,第38页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力 最小距离与纠错能力：(n,k) 线性码能纠 t 个错误的充要条件是码的最小距离为： dmin2t+1 (8.5.1) 证明： 由于 d(U,V)dmin=2t+1，代入式 (7.5.2) 得： d(R,U) d(U,V)d(R,V)= 2t+1t t (8.5.4) 含义：如果接收字 R 中错误个数 t t，接收字 R 和发送字 V 间距离t ，而与其它任何码字间距离都大于 t，按最小距离译码把 R 译为 V。此时译码正确，码字中的错误被纠正。 几何意义：,8.5 线性分组码的最小距离、检错和纠错能力,参见图示,第39页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力 最小距离与检错能力：(n,k) 线性码能够发现 l 个错误的充要条件是码的最小距离为： dminl+1 (8.5.5) 证明： 设发送的码字为 V；接收的码字为 R；U 为任意其它码字 则矢量V、R、U 间满足距离的三角不等式： d(R,V)+d(R,U)d(U,V) (8.5.2) 设信道干扰使码字中码元发生错误的实际个数为 l ，且 l l d(R,V)l l (8.5.6),8.5 线性分组码的最小距离、检错和纠错能力,第40页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力 最小距离与检错能力：(n,k) 线性码能够发现 l 个错误的充要条件是码的最小距离为： dminl+1 (8.5.5) 证明： 由于 d(U,V)dmin=l+1，代入式(7.5.2) 得：d(R,U) d(U,V)d(R,V)=l+1l 0 (8.5.7) 含义：由于接收字 R 与其它任何码字 U 的距离都大于0，说明接收字 R 不会因发生 l 个错误变为其它码字，因而必能发现错误。,8.5 线性分组码的最小距离、检错和纠错能力,第41页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力 最小距离与检错能力： 几何意义：,8.5 线性分组码的最小距离、检错和纠错能力,第42页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力 最小距离与检、纠错能力：(n,k) 线性码能纠 t 个错误，并能发现 l 个错误 (lt) 的充要条件是码的最小距离为： Dmin t+l+1 (8.5.8) 证明： 因为dmin2t+1，根据最小距离与纠错能力定理，该码可纠 t 个错误。 因为dminl+1，根据最小距离与检错能力定理, 该码有检 l 个错误的能力。 纠错和检错不会发生混淆：设发送码字为 V，接收字为 R，实际错误数为 l ，且 t t (8.5.9) 不会把 R 误纠为 U。,8.5 线性分组码的最小距离、检错和纠错能力,第43页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力 最小距离与检、纠错能力： 几何意义：,8.5 线性分组码的最小距离、检错和纠错能力,第44页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(2) 最小距离与检、纠错能力,8.5 线性分组码的最小距离、检错和纠错能力,当 (n,k) 线性码的最小距离 dmin 给定后，可按实际需要灵活安排纠错的数目。 例如：对 dmin=8 的码，可用来纠 3 检 4 错，或纠 2检 5 错，或纠 1 检 6错，或者只用于检 7 个错误。,返回目录,第45页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(3) 线性码的最小距离与监督矩阵的关系 定理8.5.1：设 H 为 (n,k) 线性码的一致监督矩阵，若 H 中任意 S 列线性无关，而 H 中存在 (S+1) 列线性相关，则码的最小距离为 (S+1)。 定理8.5.2：若码的最小距离为 (S+1)，则该码的监督矩阵的任意 S 列线性无关，而必存在有相关的 (S+1)列。 定理8.5.3：在二元线性码的监督矩阵 H 中，如果任一列都不是全“0”，且任两列都不相等，则该码能纠一个错误。（S=2，dmin=3）,8.5 线性分组码的最小距离、检错和纠错能力,第46页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6 线性分组码的译码,8.6.1 伴随式和错误检测,8.6.2 纠错译码,第47页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.1 伴随式和错误检测,(1) 如何译码？ (2) 伴随式 (3) 伴随式的计算 (4) 伴随式的特性 (5) 举例 (6) 伴随式计算电路,8.6 线 性 分 组 码 的 译 码,第48页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.1 伴随式和错误检测,(1) 如何译码？ 用监督矩阵编码，也用监督矩阵译码：接收到一个字 R 后，校验 HR T=0T 是否成立： 若关系成立，则认为 R 是一个码字； 否则判为码字在传输中发生了错误； HR T 的值是否为 0 是校验码字出错与否的依据。 (2) 伴随式/监督子/校验子：S=RH T 或 S T=HR T,返回目录,8.6 线 性 分 组 码 的 译 码,第49页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.1 伴随式和错误检测,(3) 伴随式的计算 发送码字：C=(cn1,cn2,c0) 信道错误图样：E=(en1,en2,e0) ei=0，表示第 i 位无错； ei=1，表示第 i 位有错。i=n1,n2,0 接收字：R=(rn1,rn2,r0)=C+E=(cn1+en1,cn2+en2,c0 +e0) 求接收字的伴随式（接收字用监督矩阵进行检验） S T=HR T=H(C+E )T=HC T+HE T (8.6.1) HC T=0T，所以 S T=HE T 设 H=(h1,h2,hn)，（hi 表示 H 的列）。代入式(8.6.1)得： S T=h1 en1+ h2 en2+ + hn e0,返回目录,8.6 线 性 分 组 码 的 译 码,第50页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.1 伴随式和错误检测,(4) 伴随式的特性 伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定； 伴随式是错误的判别式： 若 S=0，则判为没有出错，接收字是一个码字； 若 S0，则判为有错。 不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是 H 阵中与错误码元对应列之和。,返回目录,8.6 线 性 分 组 码 的 译 码,第51页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(5) 举 例：(7,3) 码接收字 R 的伴随式计算 若接收字中没有错误： 设发送码字 C=1010011，接收码字 R1010011，R 与 C 相同： 但接收端译码器并不知道就是发送的码字 根据接收字R 计算伴随式：S T= HR T =0T 因此，译码器判接收字无错,8.6.1 伴随式和错误检测,8.6 线 性 分 组 码 的 译 码,第52页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(5) 举 例：(7,3) 码接收矢量 R 的伴随式计算 若接收字中有 1 位错误： 发送码字C=1010011，接收码字R=1110011，伴随式为： (7,3) 码是纠单个错误的码，且S T 等于H 的第二列，因此判定接收字R 的第二位是错的。 由于接收字R 中错误码元数与码的纠错能力相符，所以译码正确。,8.6.1 伴随式和错误检测,8.6 线 性 分 组 码 的 译 码,第53页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.1 伴随式和错误检测,(5) 举 例：(7,3) 码接收矢量 R 的伴随式计算 当码元错误多于 1 个时： 发送码字C=1010011，接收码字R=0011011，伴随式为： 由于S T 是第一列和第四列之和，不等于0； 但S T 与 H 阵中任何一列都不相同无法判定错误出在哪些位上，只是发现有错。,返回目录,8.6 线 性 分 组 码 的 译 码,第54页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.1 伴随式和错误检测,(6) 伴随式计算电路 伴随式的计算可用电路来实现。 (7,3) 码为例：接收字 R =(r6r5r4r3r2r1r0)，伴随式：,8.6 线 性 分 组 码 的 译 码,第55页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.1 伴随式和错误检测,(6) 伴随式计算电路 伴随式计算电路：,返回目录,8.6 线 性 分 组 码 的 译 码,第56页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(1) 最佳译码准则（最大似然译码） (2) 查表译码法 (3) 标准阵列 (4) 举例 (5) 结论,8.6 线 性 分 组 码 的 译 码,第57页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(1) 最佳译码准则（最大似然译码） 通信是一个统计过程，纠、检错能力最终要反映到差错概率上。 对于 FEC 方式，采用纠错码后的码字差错概率为 pwe： p(C)：发送码字C 的先验概率 p(C/R)：后验概率,8.6 线 性 分 组 码 的 译 码,第58页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(1) 最佳译码准则（最大似然译码） 若码字数为 2k，对充分随机的消息源有 p(C)=1/ 2k，所以最小化的 pwe等价为最小化 p(C C/R )，又等价为最大化：p(C =C/R)； 对于 BSC 信道：最大化的 p(C =C/R ) 等价于最大化的 p(R /C) ，最大化的 p(R /C) 又等价于最小化 d(R,C)，所以使差错概率最小的译码是使接收向量 R 与输出码字 C 距离最小的译码。,返回目录,8.6 线 性 分 组 码 的 译 码,第59页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(2) 查表译码法 按最小距离译码，对有 2k 个码字的 (n,k) 线性码，为了找到与接收字 R 有最小距离的码字，需将 R 分别和 2k 个码字比较，以求出最小距离。其中利用“标准阵列”译码是最典型的方法。,返回目录,8.6 线 性 分 组 码 的 译 码,第60页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 码字参数：发送码字：取自于 2k 个码字集合 C； 接收码字：可以是 2n 个 n 重中任一个矢量。 译码方法 把 2n 个 n 重矢量划分为 2k 个互不相交的子集 ，使得在每个子集中仅含一个码字； 根据码字和子集间一一对应关系，若接收矢量 Rl 落在子集 Dl 中，就把 Rl 译为子集 Dl 含有的码字 Cl； 当接收矢量 R 与实际发送码字在同一子集中时，译码就是正确的。,8.6 线 性 分 组 码 的 译 码,第61页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列构造方法 先将 2k 个码字排成一行，作为标准阵列的第一行，并将全 0 码字 C1=(000) 放在最左面的位置上； 然后在剩下的 (2n2k) 个 n 重中选取一个重量最轻的 n 重 E2 放在全 0 码字 C1 下面，再将 E2 分别和码字 相加，放在对应码字下面构成阵列第二行； 在第二次剩下的 n 重中，选取重量最轻的 n 重 E3，放在 E2 下面，并将 E3 分别加到第一行各码字上，得到第三行； ，继续这样做下去，直到全部 n 重用完为止。得到表 7.6.1 所示的给定 (n,k) 线性码的标准阵列。,8.6 线 性 分 组 码 的 译 码,第62页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列构造方法,返回,8.6 线 性 分 组 码 的 译 码,第63页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 定理8.6.1：在标准阵列的同一行中没有相同的矢量，而且 2n 个 n 重中任一个 n 重在阵列中出现一次且仅出现一次。 证明： 因为阵列中任一行都是由所选出某一 n 重矢量分别与 2k 个码字相加构成的，而 2k 个码字互不相同，它们与所选矢量的和也不可能相同，所以在同一行中没有相同的矢量； 在构造标准阵列时，是用完全部 n 重为止，因而每个 n 重必出现一次； 每个 n 重只能出现一次：,8.6 线 性 分 组 码 的 译 码,第64页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(3) 标准阵列 标准阵列的特性 定理8.6.1：在标准阵列的同一行中没有相同的矢量，而且 2n 个 n 重中任一个 n 重在阵列中出现一次且仅出现一次。 证明：,8.6.2 纠错译码,假定某一 n 重 X 出现在第 l 行第 i 列，那么 X=El+Ci； 又假设 X 出现在第 m 行第 j 列，那么 X=Em+Cj，ll) 的第一个元素; 按阵列构造规则，后面行的第一个元素是前面行中未曾出现过的元素，这就和阵列构造规则相矛盾。,每个 n 重只能出现一次的原因,8.6 线 性 分 组 码 的 译 码,第65页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 定理8.6.2（线性码纠错极限定理）：二元 (n,k) 线性码能纠 2nk 个错误图样。这 2nk 个可纠的错误图样，包括 0 矢量在内，即把无错的情况也看成一个可纠的错误图样。 证明： 陪集：标准阵列的每一行叫做码的一个陪集。 陪集首：每个陪集的第一个元素叫做陪集首。 (n,k) 线性码的标准阵列有 2k 列（和码字数量相等），2n/2k= 2nk 行，且任何两列和两行都没有相同的元素。,8.6 线 性 分 组 码 的 译 码,第66页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,(3) 标准阵列 标准阵列的特性 定理8.6.2（线性码纠错极限定理）： 证明： 每一列包含 2nk 个元素，最上面的是一个码字，其它元素是陪集首和该码字之和，例如第 j 列为： 若发送码字为 Cj，信道干扰的错误图样是陪集首，则接收矢量 R 必在 Dj 中；,8.6.2 纠错译码,见表,8.6 线 性 分 组 码 的 译 码,第67页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 定理7.6.2 (线性码纠错极限定理)： 证明： 若错误图样不是陪集首，则接收矢量 R 不在 Dj 中，则译成其它码字，造成错误译码； 当且仅当错误图样为陪集首时，译码才是正确的。 可纠正的错误图样：这 2nk 个陪集首称为可纠正的错误图样。,见表,8.6 线 性 分 组 码 的 译 码,第68页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 线性码纠错能力与监督元数目的关系：一个可纠 t 个错误的线性码必须满足： 上式中等式成立时的线性码称为完备码。即：,8.6 线 性 分 组 码 的 译 码,第69页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 线性码纠错能力与监督元数目的关系： 证明： 纠一个错误的 (n,k) 线性码，必须能纠正 个错误图样，因此： 对纠两个错误的 (n,k) 线性码，必须能纠 个错误图样，所以：,8.6 线 性 分 组 码 的 译 码,第70页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 线性码纠错能力与监督元数目的关系： 证明： 依此类推，一个纠 t 个错误的 (n,k) 线性码必须满足： 对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠的错误图样数，所以完备码的 (nk) 个监督码元得到了充分的利用。,8.6 线 性 分 组 码 的 译 码,第71页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 完备译码：(n,k) 线性码的所有 2nk 个伴随式，在译码过程中都用来纠正所有小于等于 个随机错误，以及部分大于 t 的错误图样。 限定距离译码：任一个 (n,k) 线性码，能纠正 个随机错误，如果在译码时仅纠正 t t 个错误，而当错误个数大于 t 时，译码器不进行纠错而仅指出发生了错误。,8.6 线 性 分 组 码 的 译 码,第72页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 从多维矢量空间的角度看完备码 假定围绕每一个码字 Ci 放置一个半径为 t 的球，每个球内包含了与该码字汉明距离小于等于 t 的所有接收码字 R 的集合； 在半径为 的球内的接收码字数是： 因为有 2k 个可能发送的码字，也就有 2k 个不相重叠的半径为 t 的球。包含在 2k 个球中的码字总数不会超过 2n 个可能的接收码字。,8.6 线 性 分 组 码 的 译 码,第73页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 从多维矢量空间的角度看完备码 于是一个纠 t 个差错的码必然满足不等式： 如果上式中等号成立，表示所有的接收码字都落在 2k 个球内，而球外没有一个码，这就是完备码。,8.6 线 性 分 组 码 的 译 码,第74页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 从多维矢量空间的角度看完备码,完备码特性：围绕 2k 个码字，汉明距离为 t=INT(dmin1)/2 的所有球都是不相交的，每一个接收码字都落在这些球中之一，因此接收码与发送码的距离至多为 t，这时所有重量 t 的错误图样都能用最佳（最小距离）译码器得到纠正，而所有重量t+1 的错误图样都不能纠正。,8.6 线 性 分 组 码 的 译 码,第75页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 从多维矢量空间的角度看完备码 举例：对纠一个错误的 (7,4) 汉明码： (7,4) 汉明码是一个完备码。 所有汉明码都是完备码：（满足2nk = 2r=n+1）。,8.6 线 性 分 组 码 的 译 码,第76页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 标准阵列译码 = 最小距离译码 = 最佳译码 陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首； 重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的 n 重作陪集首； 当错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码字间的距离（等于陪集首）最小； 因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码； 所以标准阵列译码法也是最佳译码法。,8.6 线 性 分 组 码 的 译 码,第77页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(3) 标准阵列 标准阵列的特性 定理7.6.3：在标准阵列中，一个陪集的所有 2k 个 n 重有相同的伴随式，不同的陪集伴随式互不相同。 证明： 设 H 为给定 (n,k) 线性码的监督矩阵，在陪集首为 El 的陪集中的任意矢量为：R=El+Ci, i=1,2,2k 其伴随式为：S=RH T=(El+Ci)H T=ElH T+CiH T =ElH T 上式表明：陪集中任意矢量的伴随式等于陪集首的伴随式。即同一陪集中所有伴随式相同。 不同陪集中，由于陪集首不同所以伴随式不同。,返回目录,8.6 线 性 分 组 码 的 译 码,第78页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(4) 举例： (6,3)码的标准阵列,返回,返回目录,8.6 线 性 分 组 码 的 译 码,第79页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(5) 结论 任意 n 重的伴随式决定于它在标准阵列中所在陪集的陪集首。 标准阵列的陪集首和伴随式是一一对应的，因而码的可纠错误图样和伴随式是一一对应的，应用此对应关系可以构成比标准阵列简单得多的译码表，从而得到 (n,k) 线性码的一般译码步骤。 (n,k) 线性码的一般译码步骤 计算接收矢量 R 的伴随式 S T=HR T ； 根据伴随式和错误图样一一对应的关系，利用伴随式译码表，由伴随式译出 R 的错误图样 E； 将接收字减错误图样，得发送码字的估值：C =RE 。,见表,8.6 线 性 分 组 码 的 译 码,第80页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(5) 结论 线性分组码一般译码器（伴随式译码法/查表译码法） 译码器如下图。这种查表译码法具有最小的译码延迟和最小的译码错误概率，原则上可用于任何 (n,k) 线性码。,8.6 线 性 分 组 码 的 译 码,第81页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(5) 结论 举例： 求 (7,4) 汉明码的编码电路和译码电路。 其系统码形式：,8.6 线 性 分 组 码 的 译 码,第82页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(5) 结论 举例： 求 (7,4) 汉明码的编码电路和译码电路。 编码电路：,8.6 线 性 分 组 码 的 译 码,第83页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(5) 结论 举例： 求 (7,4) 汉明码的编码电路和译码电路。 编码电路：,8.6 线 性 分 组 码 的 译 码,第84页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(5) 结论 举例： 求 (7,4) 汉明码的编码电路和译码电路。 译码电路：,8.6 线 性 分 组 码 的 译 码,第85页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.6.2 纠错译码,(5) 结论 举例： 求 (7,4) 汉明码的编码电路和译码电路。 译码电路：,8.6 线 性 分 组 码 的 译 码,第86页,2020/10/3,Department of Electronics and Information, NCUT Song Peng,8.7 线性分组码的性能,在通信中检、纠错码的实际性能是在统计上体现出来的。 错误概率： 不可检错误概率：pud 译码错误概率：pwe 译码失败概率：pwf 比特误码率：Pbd 差错概率的原因： 码的结构 信道特性 分析均以 BSC 信道为模型。,第87页,2020/10/3,Department of Electronics and Information, NCUT Song Pen