(6,3)线性分组码编码分析与实现.

第5章 信道编码技术
5.1.2 差错控制编码的基本思想 差错控制编码的基本实现方法是在发送端给被传输的
信息附上一些监督码元，这些多余的码元与信息码元之间 以某种确定的规则相互关联。在接收端按照既定的规则校 验信息码元与监督码元之间的关系，一旦传输发生错误， 则信息码元与监督码元的关系就受到破坏，从而使接收端 可以发现错误，进而纠正错误。因此，各种编码和译码方 法是差错控制编码所要研究的问题。 5.1.3 差错控制方式
距应满足
dmin≥t+e+1 (e>t)
(5-3)
第5章 信道编码技术 图 5-2 纠错码纠错能力图示一
第5章 信道编码技术 图 5-3 纠错码纠错能力图示二
第5章 信道编码技术
5.2.3 奇偶监督码 奇偶监督码(又称为奇偶校验码)是一种最简单的检错
码，它的基本思想是在n－1位信息码元后面附加一位监督 码元，构成(n，n－1)的分组码，监督码元的作用是使码长 为n的码组中“1” 的个数保持为奇数或偶数。码组中“1” 的个数保持为奇数的编码称为奇数监督码，保持为偶数的 编码称为偶数监督码。
的一种改进形式，它不仅对每一行进行奇偶校验，同时对每 一列也进行奇偶校验。如表5-2所示的例子采用的是偶校验。
发送时，该码是按11001100、00100111、00011110、 11000000、01111011、00100111、01101001的顺序发送，而 在接收端将所接收的信号以列的形式排列，可得表5-2所示 的阵列。
(5-5)
奇偶监督码最小码距为2，无论是奇校验还是偶校验，
都只能检测出单个或奇数个错误，而不能检测出偶数个错
误，因此检错能力低，但编码效率随着n的增加而提高。

第6章 线性分组码 如上所述，信道编码就是给已知信息组按预定规则添加监
督码元，以构成码字。在k个信息元之后附加r(r＝n－k)个监
督码元，使每个监督元是其中某些信息元的和。例如，信息分
组长度k＝3，在每一信息组后加上4个监督元，构成(7，3)线
性分组码。设该码的码字为c6c5c4c3c2c1c0，其中c6、c5、c4为 信息元;c3、c2、c1、c0为监督元，每个码元取值为“0”或 “1”，即ci∈GF(2)。监督元可按下面方程组计算：
c3 u2 u0
c2
c1
u2 u2
u1
u1
u0
c0 u1 u0
（6－１）
第6章 线性分组码
式(6－1)为一线性方程组，它确定了由信息元得到监督 元的规则，所以称为监督方程或校验方程。由于所有码字都按 同一规则确定，因此式(6－1)称为一致监督方程或一致校验 方程，所得到的监督元称为一致监督元或一致校验元，这种编 码方法称为一致监督编码或一致校验编码。因为一致监督方程 是线性的，亦即监督元和信息元之间是线性运算关系，所以由 线性监督方程所确定的分组码是线性分组码。利用式(6－1), 每给出一个3位的信息组，就可编出一个码字，如表6－1所示。
第6章 线性分组码 图6－1 线性分组码编码器
第6章 线性分组码
n-k个附加码元是由信息码元的线性运算产生的,此码叫 做（n,k）线性分组码。如果一个(n，k)线性分组码的数域为 GF(p)，即每一个码元可能有p种取值，则信源可发出pk种不同 的消息组。为使接收端对码字惟一可译,即当从n位长的码字中 译出k位的消息时，消息组与码字之间应有一一对应的关系， 因此编码器至少要存储pk个码字才能实现消息到码字的变换 (当k比较大时，这种编码器就显得有些不切实际)。为了压缩 编码器的存储容量，通常对编码器附加一个线性约束条件，使 得线性码的校检位与信息位之间呈线性关系。对于二进制码， (n，k)线性分组码(以后简称为(n，k)码)共有2k个码字，它们 构成k维子空间的主要特征是：在加法运算下满足封闭性；在 2k个码字中只有k个是线性独立的。

码矢：一个 n 长的码字可以用矢量来表示

C = (Cn－1,Cn－2,…,C1,C0 )
所以码字又称为码矢。

( n, k ) 线性码：信息位长为 k，码长为 n 的线性码。
编码效率/编码速率/码率：R=k /n。它说明了信道的利用效率， R是衡量码性能的一个重要参数。

2013/7/31
2

线性分组码的编码：线性分组码的编码过程分为两步：
面 k 位为信息数字，后面 r=n－k 位为校验字，这种信息数字 在前校验数字在后的线性分组码称为线性系统分组码。
信息数字 校验数字
图6.2.1 系统码的码字结构

当生成矩阵 G 确定之后，(n,k) 线性码也就完全被确定了，只要 找到码的生成矩阵，编码问题也同样被解决了。

[ 参见下面有关（7，4）线性码例子 ]


设码字矢量为C = (C6 C5C4C3C2C1C0) 码的监督矩阵为
2013/7/31
31
6.3.4 线性分组码的编码

根据方程组可直接画出 (7,3) 码的并行编码电路和串行编码 电路，如图。
m2 m1 m0 C6 C5 C4 C3
C m
C2
C1
C0
(a)并行编码电路 （b）串行编码电路
2013/7/31
4
6.3.2 线性分组码的监督方程和监督矩阵
(1) 监督方程

编码就是给已知信息码组按预定规则添加监督码元，以构成码字。 在 k 个信息码元之后附加 r(r=n－k) 个监督码元，使每个监督元是 其中某些信息元的模2和。 举例：k=3, r=4，构成 (7,3) 线性分组码。设码字为
2013/7/31

实践教学大学计算机与通信学院2014年秋季学期计算机通信课稈设计题目：线性分组码（9 , 4）码的编译码仿真设计专业班级：_______________________________姓名：_________________________________________学号：_______________________________________指导教师：______________________________________成绩：______________________________________________摘要该系统是（9, 4）线性分组码的编码和译码的实现，它可以对输入的四位的信息码进行线性分组码编码，对于接收到的九位码字可以进行译码，从而译出四位信息码。

当接收到的九位码字中有一位发生错误时，可以纠正这一位错码；当接收到的码字有两位发生错误时，只能纠正一位错误，但同时能检测出另一位错误不能纠正。

只有特定位有两位错误时，才能纠正两位错误。

这样就译出正确的信息码组，整个过程是用MATLAB语言实现的。

关键词：编码；译码;纠错摘要 目录1. 信道编码概述2.•…1.1信道模型 ............................................................... 2•…1.2抗干扰信道编码定理及逆定理 ............................................ 3…1.3检错与纠错的基本原理 .................................................. 4•…1.4限失真编码定理 ........................................................ 5•…2. 线性分组码的编码 ........................................................... 6 _2.1生成矩阵 ............................................................... 6•…2.2校验矩阵 ............................................................... 9•…2.3伴随式与译码 ......................................................... 1.0....3. 线性分组码编码的 Matlab 仿真 ............................................... 1.2..3.1程序流程图 ............................................................ 1.2....3.2程序执行结果 ......................................................... 12....3.2线性分组码译码的 Matlab 仿真 .......................................... 1.3.3.3结果分析 .............................................................. 1.5.... 参考文献 .................................................................... .1.6..... 总结 ......................................................................... 1.7.... 致谢 ......................................................................... 1.8.... 附录目录19刖言由于计算机、卫星通信及高速数据网的飞速发展，数据的交换、处理和存储技术得到了广泛的应用，数字信号在传输中往往由于各种原因，使得在传送的数据流中产生误码，从而使接收端产生图象跳跃、不连续、出现马赛克等现象，人们对数据传输和存储系统的可靠性提出来了越来越高的要求，经过长时间的努力，通过编译码来控制差错、提高可靠性的方式在信道传输中得到了大量的使用和发展，并形成了一门新的技术叫做纠错编码技术，纠错编码按其码字结构形式和对信息序列处理方式的不同分为两大类：分组码和卷积码。

个错误
2018/10/27
12
第六章 信道编码

6.2.6 线性分组码的译码
对纠两个错误的 (n,k) 线性码，必须能纠 误图样，所以 个错

依此类推，一个纠 t 个错误的 (n,k) 线性码必须满足

对于完备码，由码的纠错能力所确定的伴随式数恰好等于可纠 的错误图样数，所以完备码的 (n－k) 个监督码元得到了充分的 利用。
t

dmin dmin t t
t
图6.2.8 以码字为中心、半径t=INT [(dmin－1)/2]的差错控制球体示意图
2018/10/27 16
第六章 信道编码
6.2.6 线性分组码的译码

举例：对纠一个错误的 (7,4) 汉明码，
可见，(7,4)汉明码是一个完备码。

所有汉明码都是完备码（满足2n－k = 2m=n+1）。
第六章 信道编码
To choose time is to save time
2018/10/27 1
第六章 信道编码
6.2 线性分组码
一般概念 一致监督方程和一致监督矩阵 线性分组码的生成矩阵 线性分组码的编码 线性分组码的最小距离、检错和纠错能力 线性分组码的译码 线性分组码的性能 汉明码 由已知码构造新码的方法 线性分组码的码限

p(C)：发送码字C 的先验概率 p(C/R)：后验概率

若码字数为 2k，对充分随机的消息源有p(C)=1/ 2k，所以最小化的 pwe等价为最小化p(C’≠C│R )，又等价为最大化p(C’=C│R)；
3
2018/10/27
第六章 信道编码

6.2.6 线性分组码的译码

标准阵：例子(6,3)线性码
令Dj表示标准阵的第j列， vj是码字，ei是陪集首
标准阵



码字vj通过有噪信道传输，若信道引起的错误 模式是陪集首，则接收向量r在Dj中，此时接 收向量可被正确译码为vj 若错误模式没有在陪集首中出现，则译码有误 假设错误模式x在第l行而非陪集首，不妨设在 第i>1列，则x=el+vi，接收向量为r=vj+x= el+(vi+vj)=el+vs，接收向量出现在Ds中，r被译 码为vs，出现译码错误 故当且仅当错误模式是陪集首时译码是正确的， 这些陪集首称为可纠正错误模式



校正子

依据公式(3)(4)可以得到：

从上述式子看出，校正子s就是接收到的消息 位 重新计算校验位和接收到的 校验位 的向量和
校正子

上式子给出了校正子s和错误模式e的关系，若 H的表示如公式(3)所示系统形式，则有校正子 为错误模式的线性组合：
小结

找到错误模式e，利用v=r+e就可将v视为实际 传输的码字，但是错误模式e不容易找到，需 要在2k个错误模式（待证明）中找到唯一正确 的错误模式


码C称为H的零空间，H称为码的奇偶校验矩阵 矩阵H的行向量有2n-k中组合方式，构成(n,n-k)线性码Cd，这 个码是G的零空间 Cd是C的对偶码，dual code 一个线性码的奇偶校验矩阵是其对偶码的生成矩阵
奇偶校验矩阵

若(n,k)线性码的生成矩阵公式(2)所示，则其奇 偶校验矩阵为公式(3) (3)
陪集首的重量分布

令

表示重量为i的陪集首的个数，则称 为陪集首的重量分布 若陪集首的重量分布已知，当且仅当错误模式 不是陪集首时，会发生译码错误，故对转移概 率为p的BSC信道，误码率为：

⎡ x k −1 g ( x) ⎤ ⎢ k −2 ⎥ ⎢ x g ( x) ⎥ ⎥ G ( x) = ⎢ ⎢ ⎥ ⎢ xg ( x) ⎥ ⎢ g ( x) ⎥ ⎣ ⎦
6
生成矩阵G
• ( n , k ) 循环码的生成矩阵在 g(x) 确定后可以表示 为G
⎡0 0 ... 0 g 0 g1 ... g r −1 g r ⎤ ⎢ ⎥ ⎢ ⎥ ⎥ G=⎢ ⎢ ⎥ g 0 g1 ... g r − 2 g r −1 g r ... 0 ⎥ ⎢0 ⎢ g 0 g1 g 2 ... g r −1 g r 0 ... 0 ⎥ ⎣ ⎦ k ×n ⎡ x k −1 g ( x) ⎤ ⎢ k −2 ⎥ ⎢ x g ( x) ⎥ ⎥ ∼⎢ ⎢ ⎥ ⎢ ⎥ ⎢ g ( x) ⎥ ⎣ ⎦
R ( x ) C ( x ) + e( x ) e( x ) = = p ( x) + g ( x) g ( x) g ( x)
• 定义伴随多项式为 S(x) = e(x) mod g(x)
11
循环码的检纠错
• 根据伴随式的定义，若无错误传输，则 S(x) = 0 ，否 则S(x)≠0，由此可实现循环码的检错。 • 因为g(x)的次数为n－k，e(x)的次数为n－1，所以伴随 式的最高次数为n－k－1，那么S(x)共有n－k项，故有 2n-k种可能的伴随式。若满足2n-k ≥n+1，则循环码具 有纠错能力。
10
循环码的伴随多项式
• 假设发送的码多项式C(x) 和 错误图样多项式e(x) 以及 接收 端接收的码多项式R(x) 分别为
C ( x) = ∑ ci x
i =1
n
n −i
； e( x) = ∑ ei x
i =1

C mG
G是一个k*n阶矩阵，称为(n,k)码的生成矩阵。
7
1 0 G 0
0 0 1 0 0 1
p11 p 21 p k1
p12 p 22 pk 2
p1( n k ) p 2( nk ) I P k pk ( nk )
n 1
u和v之间的距离表示2个码字对应位不同的数目。
如(7,3)码的两个码字：u=0011101
v=0100111
它们之间的距离d=4
4
码的最小距离的dmin ：在（n,k）线性码字集合中， 任意两个码字间的距离最小值，是衡量抗干扰能力的 重要参数，dmin越大，抗干扰能力越强。 码字的重量W：码字中非零码元符号的个数；在二元 线性码中，码字的重量是码字中含“1”的个数。 码的最小重量Wmin：线性分组码中，非零码字重量的 最小值，称为码的最小重量，表示为：
限， 性能界限，即码的译码错误概率的上、下 限。 对码距限而言，最重要的限是汉明限，普 洛特金限和吉尔伯特－瓦尔沙莫夫限，汉 明码和普洛特金限告诉我们，在给定码长n 和码的传输速率R=k/n下，最小距离可以达 到的最大值，故它们都是上限，而吉尔伯 特一瓦尔沙莫夫限给出了码的最小距离的 下限。
HC 0
T
T
r=n-k
H
阵是n列，(n-k)行的矩阵；
为了得到确定的码，r个监督方程必须是线性
无关的，即要求H阵的秩为r。
6
2. 生成矩阵G
把方程组写成矩阵的形式为
h11 h 21 h r1
h12 h1k h 22 h 2k h r2 h rk
m 信道编码
C

线性分组码8.3.1 基本概念是一组固定长度的码组，可表示为（n, k），通常它用于前向纠错。

在分组码中，监督位被加到信息位之后，形成新的码。

在编码时，k个信息位被编为n位码组长度，而n-k个监督位的作用就是实现检错与纠错。

当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为。

对于长度为n的二进制线性分组码，它有种可能的码组，从种码组中，可以选择M=个码组（k<n）组成一种码。

这样，一个k比特信息的线性分组码可以映射到一个长度为n码组上，该码组是从M=个码组构成的码集中选出来的，这样剩下的码组就可以对这个分组码进行检错或纠错。

线性分组码是建立在代数群论基础之上的，各许用码的集合构成了代数学中的群，它们的如下：（1）任意两许用码之和（对于二进制码这个和的含义是模二和）仍为一许用码，也就是说，线性分组码具有封闭性；（2）码组间的最小码距等于非零码的最小码重。

在8.2.1节中介绍的奇偶监督码，就是一种最简单的线性分组码，由于只有一位监督位通常可以表示为（n,n-1），式（8-5）表示采用偶校验时的监督关系。

在接收端解码时，实际上就是在计算：（8-6）其中，…表示接收到的信息位，表示接收到的监督位，若S＝0，就认为无错；若S＝1就认为有错。

式（8-6）被称为监督关系式，S是校正子。

由于校正子S的取值只有“0”和“1”两种状态，因此，它只能表示有错和无错这两种信息，而不能指出错码的位置。

设想如果监督位增加一位，即变成两位，则能增加一个类似于式（8-6）的监督关系式，计算出两个校正子和，而共有4种组合：00，01，10，11，可以表示4种不同的信息。

除了用00表示无错以外，其余3种状态就可用于指示3种不同的误码图样。

同理，由r个监督方程式计算得到的校正子有r位，可以用来指示-1种误码图样。

对于一位误码来说，就可以指示-1个误码位置。

对于码组长度为n、信息码元为k位、监督码元为r＝n - k位的分组码（常记作（n，k）码），如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能，则要求：（8-7) 下面通过一个例子来说明的。

线性特性：码字c的各位码元是消息m各位的线性组 合
一个（ 一个（n,k）线性分组码的码字 c可以表示为 ） 可以表示为
c=mG
其中m：长度为 的消息或 的消息或k维的消息向量 其中 ：长度为k的消息或 维的消息向量 Gk*n：k行n列的生成矩阵 列的生成矩阵 行 列的 矩阵运算采用模二加和模二乘。 矩阵运算采用模二加和模二乘。
1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 G = 0 1 0 1 1 R2 + R3 → R3 →0 1 0 1 1 R1 + R3 → R1 → 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 R1 ← → R 3 →0 1 0 1 1 = G S 0 0 1 1 1
线性分组码的性质
（1）零向量一定是一个码字，记作 θ = (0,0,L ,0) ）零向量一定是一个码字， （2）任意两码字的和仍是一个码字。 ）任意两码字的和仍是一个码字。 都可以表示为G的行向量的线性组合 （3）任意码字 都可以表示为 的行向量的线性组合。 ）任意码字c都可以表示为 的行向量的线性组合。
G的行向量是码集合中的码字（它们线性无关） 的行向量是码集合中的码字（它们线性无关） 的行向量是码集合中的码字
（4）线性分组码的最小距离等于最小非 码的码重： 码的码重： ）线性分组码的最小距离等于最小非0码的码重 码重：码字中的非0符号个数。
d min = min w(c)
c ≠θ
例：c = (0101) d = w(c)
系统码。 （1）则该码称为系统码。 ）则该码称为系统码
容易发现，若系统线性分组码的生成矩阵G 的左（右） 半部分是Ik*K的单位阵，则线性分组码的前（后）k位是 信息位，后n-k位是校验位。 若不是系统码，则可以通过简单行变换得到系统码生成 矩阵。

1. 在无失真的信源中，信源输出由 H (X ) 来度量；在有失真的信源中，信源输出由 R (D ) 来度量。

2. 要使通信系统做到传输信息有效、可靠和保密，必须首先 信源 编码， 然后_____加密____编码，再______信道_____编码，最后送入信道。

3. 带限AWGN 波形信道在平均功率受限条件下信道容量的基本公式，也就是有名的香农公式是log(1)C W SNR =+；当归一化信道容量C/W 趋近于零时，也即信道完全丧失了通信能力，此时E b /N 0为 -1.6 dB ，我们将它称作香农限，是一切编码方式所能达到的理论极限。

4. 保密系统的密钥量越小，密钥熵H (K )就越 小 ，其密文中含有的关于明文的信息量I (M ；C )就越 大 。

5. 已知n ＝7的循环码42()1g x x x x =+++，则信息位长度k 为 3 ，校验多项式 h(x)= 31x x ++ 。

6. 设输入符号表为X ＝{0，1}，输出符号表为Y ＝{0，1}。

输入信号的概率分布为p ＝(1/2，1/2)，失真函数为d (0，0) = d (1，1) = 0，d (0，1) =2，d (1，0) = 1，则D min ＝ 0 ，R (D min )＝ 1bit/symbol ，相应的编码器转移概率矩阵[p(y/x )]＝1001⎡⎤⎢⎥⎣⎦；D max ＝ 0.5 ，R (D max )＝ 0 ，相应的编码器转移概率矩阵[p(y/x )]＝1010⎡⎤⎢⎥⎣⎦。

7. 已知用户A 的RSA 公开密钥(e,n )=(3,55)，5,11p q ==,则()φn = 40 ，他的秘密密钥(d,n )＝(27,55) 。

若用户B 向用户A 发送m =2的加密消息，则该加密后的消息为 8 。

二、判断题1. 可以用克劳夫特不等式作为唯一可译码存在的判据。

（√ ）2. 线性码一定包含全零码。

（√ ）3. 算术编码是一种无失真的分组信源编码，其基本思想是将一定精度数值作为序列的 编码，是以另外一种形式实现的最佳统计匹配编码。

消息集： u0，u1， ，uk-1 ui F2 序列个数：2k
设长为n的二元码元序列集为：
c0，c1， ，cn-1 n k
序列个数：2n ≥2k
1．分组编码：
在长为n的二元序列集中 c0，c1， ，cn-1 选出与消息序列数2k相同数
目的码元序列，并使两者一一对应。
几个概念：
r c0
2．汉明距离的性质
① 自反性： a Vn (F2 )，d(a，a) 0
② 对称性： a，b Vn (F2 )，d (a，b ) d (b，a)
③ 三角不等式：a，b，c Vn (F2 ) d (a，b ) d (b，c ) d (a，c )
二．分组码的检、纠错能力与最小汉明距离之间的关系
①
收到接收字 r 后，通过计算
字 的c j 汉明距离最小，则
r与各码字 c之i 间的汉明距离，如 与r码字 最c像j ，译码器将 译r成
r。r与c某j 一码
② 极大似然译码基础：收到的字是从一个码字经错传尽可能少的位而来的 可能性较从一个码字经错传较多的位而来的可能性要大。故通过判断汉明 距离来译码，符合极大似然译码规则。
0
1 - pe
0
pe
pe
1
1 - pe
1
有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、成 串地出现，表现出错误之间有相关性，称为突发错误。下图就是这种信道的 一个模型。
1 - q1
S1
0
1 - p1
p1
p1 1
1 - p1
好好好
q1
q1 << q2
q2
S2
1 - q2
0
0
1 - p2
c1 f1 u0，u1， ，uk-1

信息论与编码理论-第7章线性分组码-习题解答-20211206 信息论与编码理论第7章线性分组码习题1. 已知一个(5, 3)线性码C的生成矩阵为：??11001?G??01101???0011? 1??（1）求系统生成矩阵；（2）列出C的信息位与系统码字的映射关系；（3）求其最小Hamming距离，并说明其检错、纠错能力；（4）求校验矩阵H；（5）列出译码表，求收到r=11101时的译码步骤与译码结果。

2．设（7, 3）线性码的生成矩阵如下?0101010?G???0010111??01101??10??（1）求系统生成矩阵；（2）求校验矩阵；（3）求最小汉明距离；（4）列出伴随式表。

3．已知一个(6, 3)线性码C的生成矩阵为：?1 0 0 1 0 1?G???0 1 0 0 1 1?.?0 0 1 1 1 0? ???（1）写出它所对应的监督矩阵H；（2）求消息M=(101)的码字；（3）若收到码字为101010，计算伴随式，并求最有可能的发送码字。

4．设(6, 3)线性码的信息元序列为x1x2x3，它满足如下监督方程组??x1?x2?x4?0?x2?x3?x5?0 ??x1?x3?x6?0（1）求校验矩阵，并校验10110是否为一个码字；（2）求生成矩阵，并由信息码元序列101生成一个码字。

1信息论与编码理论习题答案1. 已知一个(5, 3)线性码C的生成矩阵为：?1G???0??011001101?01?? 11??（1）求系统生成矩阵；（2）列出C的信息位与系统码字的映射关系；（3）求其最小Hamming距离，并说明其检错、纠错能力；（4）求校验矩阵H；（5）列出译码表，求收到r=11101时的译码步骤与译码结果。

解：（1）线性码C的生成矩阵经如下行变换：?1?0???0?1?0???01001??1?0将第2、加到第31行1101???????????0111???00011??1?0将第3加到第2行1101???????????0111???00011?1101??0111??0011?1010??0111??得到线性码C的系统生成矩阵为?10011?? GS??01010????00111??（2）码字c?(c0,c1,?,cn?1)的编码函数为生成了的8个码字如下c?f(m)?m0?10011??m1?01010??m2?00111?信息元系统码字 000 001 010 011 100 101 110 111 00000 00111 01010 01101 10011 10100 11001 11110 2信息论与编码理论(3) 最小汉明距离d=2，所以可检1个错，但不能纠错。

3.从剩下的元素中任取一个重量最轻的，按相同方式 构成第三行，依此类推…
34
伴随式译码
陪集首 陪集
伴随式
35
伴随式译码
(6,3)码的标准阵
陪集首
伴随式
36
伴随式译码
BSC下，二元线性码正确译 码的概率：
第l个陪集
首的重量
重量为i的陪 集首的数量
37
伴随式译码
译码步骤： 计算接收矢量的伴随式 由伴随式确定陪集首 将陪集首作为错误图样e
将v译为c=v-e
38
最小距离和纠错能力
Th. v属于码字集合的充要条件是v的非 零码元与H相应列的乘积之和为0。
推论：若矩阵H中任意d-1列线性无关，相应码的最小距离至少为d。
39
最小距离和纠错能力
1.最小距离与纠错能力：(n,k) 线性码能纠t个错误的充要条件是码的最小距离 为
[证明]：设码C的最小距离为dmin,以码字为中心，以 t为半径的球应不相交。反证若相交，设V为其中元 素，C1,C2来自两相交球的码字，有三角不等式。
所以码字又称为码矢。 编码速率/编码效率/码率/传信率：R=k/n。它说明了信道的利用效率，R是衡量码
性能的一个重要参数。
2
线性分组码
码字重量：码字中非0码元符号的个数，汉明重量。 在二元线性码中，码字重量是码字中含“1”的个数。
等重码: 所有码字具有相同的重量. 汉明距离：在(n,k)分组码中，两个码字 U、V 之间 对应码元位上符号取值不同的个数。 最小距离dmin：任意两个码字间距离最小值.
10
线性分组码
证明 （要证明，第一个码中任一个码字也是第二个 码中的码字；第二个码中任一个码字也是第一个码 中的码字）

1 0 0 1 1 1 0 G 0 1 0 0 1 1 1 0 0 1 1 1 0 1
若已知信息组m=(011)，则相应的码字为
1 0 0 1 1 1 0 0 1 10 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1
r=n -k 个校验元。
第6章信道编码
这相当于建立一线性方程组，已知k个系数，要求n-k 个未知数，使得到的码恰好有所要求的最小距离d。
上例中的(7,3,4)码，若c6,c5,c4 代表3个信息元，则c3,c2, c1,c0 这 4 个校验元， 可由以下线性方程组求得： 1·c3=1·c6+0·c5+1·c4 1·c2=1·c6+1·c5+1·c4 1·c1=1·c6+1·c5+0·c4 1·0=0·6+1·5+1·4 c c c c c6 +c4+c3 =0 =0 +c1 =0 +c0 =0 c6+c5+c4 +c2 c6+c5 c5+c4
第6章信道编码
[定理] (n,k,d)线性分组码的最小距离等于非零码字的最小 重量。
d min (Ci )
Ci[ n ,k ]
[定理] GF(2)上(n,k,d)线性分组码中，任何两个码字C1, C2
之间有如下关系： w(C1+C2)=w(C1)+w(C2)-2w(C1·C2)
或
d(C1, C2)≤w(C1)+w(C2)
式中， C1· 2是两个码字的内积。 C
第6章信道编码
[推论] GF(2)上线性分组码任3个码字C1, C2, C3之间的汉明

MATLAB第六次预习报告研五队李振坤S201301104线性分组码1. 基本概念●系统码：编码后，信息码元本身不变，只在信息码元后加入监督码元。

●线性码：监督码元和信息码元成线性关系的码型。

●分组码：将信息码分组，并为每组信息码附加若干监督码的编码。

分组码一般用表示，为实际传送的码长，是信息码长，是监督码长。

●线性分组码：分组码的信息码元和监督码元，由一些线性代数方程联系起来。

分组是指编、译码过程是按分组进行的，而线性是指分组码中的监督码元按线性方程生成的。

【注】线性分组码的编码问题，就是要建立一组线性方程组，已知k个系数（即信息码），要求n－k个未知数（即监督码）。

2. 线性分组码的主要性质（1）封闭性封闭性是指码中任意两许用码组之和(逐位模2和)仍为一许用码组，这就是说，若A1和A2为码中的两个许用码组，则A1+A2仍为其中的一个许用码组。

（2）码的最小距离等于非零码的最小重量因为线性分组码具有封闭性，因而两个码组之间的距离（模2减）必是另一码组的重量。

为此，码的最小距离也就是码的最小重量，当然，除全“0”码组外。

3. 汉明码汉明码是用于纠正单个错误的线性分组码，其特点为：（1）最小码距（2）纠错能力【注】（3）监督码长（4）总码长（）（5）信息码长（）（6）编码效率（当r很大时，R趋向于1，效率高）因此，当r＝3，4，5，6……时，分别有（7，4）、（15，11），（31，26），（63，57）等汉明码。

4. （7，4）汉明码在（7，4）汉明码中，码组为，其中为4个信息元，为3个监督码元。

监督码元与信息元之间的关系为：（9－4）生成矩阵G：编码时使用，用于产生整个码组，包括信息码和监督码。

改写为其中称为生成矩阵，它的各行是线性无关的。

为阶单位矩阵；为阶矩阵。

由生成矩阵可以产生整个码组，码组C是系统码（即信息码保持不变，监督码附加其后）。

【注】（1）上述生成矩阵为典型形式，保证能产生系统码。