《通信》课件信道编码（二）
信道编码（二）线性分组码G主要讲授内容n线性分组码的定义n线性n监督矩阵n生成矩阵n线性分组码的性质n线性性封闭性n最小码距等于非零许用码组的最小码重n线性分组码的构造n线性子空间构造n汉明式构造n线性分组码的译码n最大似然译码n代数译码线性分组码定义n(n,k)线性分组码定义n从k维空间到n维空间的一一映射的映射空间，并且这种映射满足线性性。F：ICK维信息空间：IN维码空间：C线性性n若k维空间中的信息码字A，B，其映射结果为F(A)、F(B),满足nF(cA+dB)=c*F(A)+d*F(B)则称F为线性映射。nF的值空间就构成线性分组码的码空间。n（n,k）码的一些基本数字关系n信息空间大小：2k 种信息码字 I(k-1),I(k-2),I(0)n码空间大小：2k种许用码字 a(n-1),a(n-2),a(0)n提示：经过（n，k）编码后，空间发生扩展编码中如何描述线性性n(n,k)线性分组码的另一种定义n定义：满足HA0的所有A的集合C称为（n，k）线性分组码，其中H是一个nk行n列的二元域上的矩阵，称为监督矩阵（校验矩阵）。n解释HA0定义了一种线性映射，且是一一对应的。若A,B满足定义，则易知：H(cA+dB)=0，即cA+dB也属于C。n例（n,k）码的监督矩阵n满足HA0的所有许用码组A可以解如下方程得：方程的解n3个方程，7个未知数，只能得到4个自由度（4个信息比特）生成矩阵n信息码字U生成矩阵生成矩阵G（7，4）码的许用码组n由于 I 是4维空间中的一个码字，其取值可能性为16种，将16个码字分别乘以生成矩阵G，则得到（7，4）码的所有许用码组。(0000000)(0001011)(0010101)(0011110)(0100110)(0101101)(0110011)(0111000)(1000111)(1001100)(1010010)(1011001)(1100001)(1101010)(1110100)(1111111)小结n线性（n，k）码的关键参数nH：监督矩阵nG：生成矩阵n二者知一即可知关于（n，k）的所有信息。n引申内容n（n，k）码的所有码字构成n维空间中的k维线性子空间n（n，k）的生成矩阵的k行即是n维空间的k个基n以n维空间的另外nk个基构成的生成矩阵所生成的线性分组码（n，nk）称为（n，k）码的对偶码。线性分组码的性质n封闭性n推论：最小码距等于最小码重（全零码除外）n线性性n推论：任意码字的线性和还是许用码字（n，k）码的构造n方法n1、已知H或G，直接得到（n，k）线性分组码。n2、找出n维空间的n个基，任意选择k个作为（n，k）码的生成矩阵G。（如何找出合适的基使构成的码具有大的最小码距？）n3、n维空间中任意挑选2k个码字作为（n，k）码的需用码组，并与2k个信息码字构成一一映射。（注：此时不能保证构造出的（n，k）码是线性码）n4、其它如：汉明码、循环码、BCH码等代数构造方法（n，k）汉明码n汉明码是一种特殊的线性分组码，满足关系n2(n-k)-1=nn只能纠一个错n最小码距为3n汉明码的构造思路n由于有n-k个监督比特（冗余信息)，因此可以组成2(n-k)个图样，每个图样对应信道传输的一种传输结果。n当码字A经过信道传输后，接收到的码字为RAEnE称为信道错误图样当信道只发生一个错误时，E的图样为（10000)(01000)(00001)，共n种发生1个比特传输错误的情况。n使信道的错误图样与nk个比特组成的情况一一对应，再加上无误传输的情况，则能纠正一个错误比特的最少监督位应满足关系2(n-k)-1=n（7，4）汉明码nS1,S2,S3 a6,a5,a4,a3,a2,a1,a0n0 0 0 无错n0 0 1 a0错n0 1 0 a1错n1 0 0 a2错n0 1 1 a3错n1 0 1 a4错n1 1 0 a5错n1 1 1 a6错 n为了构造出使HA0，并且满足上述关系的H，则由上述关系可以得到nH0000001=0 0 1nH0000010=0 1 0nH0000100=1 0 0 nH0001000=0 1 1nH0010000=1 0 1nH0100000=1 1 0nH1000000=1 1 1H的第的第7列为列为001H的第的第6列为列为010H的第的第5列为列为100H的第的第4列为列为011H的第的第3列为列为101H的第的第2列为列为110H的第的第1列为列为111（n，k）汉明码的监督矩阵n由上可知：n汉明码的监督矩阵由nk行，n列组成，列为除全零外的其它所有nk元组的组合。n由于每列对应一个1比特错误图样，因此能纠正一个信道错误n当信道发生1个以上错误时，汉明码不能保证正确纠正错误。线性分组码的译码其中：xk=Es或Es (最佳接收），nk是均值为0，方差为N0/2的高斯随机变量最大似然译码最大似然译码设采用设采用BPSK调制方式，则接收端接收到信号为调制方式，则接收端接收到信号为译码时假设码字同步（即接收端已知码字的起始），译码时假设码字同步（即接收端已知码字的起始），则接收端以则接收端以作为判决作为判决的依据。的依据。最大似然译码n最大似然译码的结果为最大似然译码n软判决欧式距离欧式距离最小的码字最小的码字X对应的信息码字作为对应的信息码字作为判决结果。判决结果。硬判决（如硬判决（如BSC信道时）信道时）此时此时rk被判决成被判决成Es或或Es，因此，因此欧式距离退化成两个码字间的码距欧式距离退化成两个码字间的码距D(r,X)即可判决即可判决最大似然译码示例n若(4,2)码的许用码字为(0000)(0101)(1010)(1111)，经过信道传输（BPSK调制0-1,1-+1），接收到信号r=(-0.3,-0.7,1.5,0.4),则接收点与各许用码字间的欧式距离为：nD(r,0)=(-0.3+1)2+(-0.7+1)2+(1.5+1)2+(0.4+1)2=8.79nD(r,1)=(-0.3+1)2+(-0.7-1)2+(1.5+1)2+(0.4-1)2 =9.99nD(r,2)=(-0.3-1)2+(-0.7+1)2+(1.5-1)2+(0.4+1)2=3.99nD(r,3)=(-0.3-1)2+(-0.7-1)2+(1.5-1)2+(0.4-1)2 =5.19n最大似然判决结果为1010对应的信息码字2n上例中，如果接收到的信号经过硬判决得到(-1,-1,1,1)，则nd(r,0)=2 d(r,1)=2,d(r,2)=2,d(r,3)=2n判决结果可以是四个码字中的任意一个。代数译码n代数译码均是基于硬判决的译码n代数译码原理n接收到的码字RAE，对R进行校验SHR如果S0，则认为R是许用码字，从而认为信道无误。如果S0，则S代表错误的图样，因为HR=H(A+E)=HE，即S仅与错误图样有关，因此根据不同的错误图样进行纠正信道错误。通常称S=HR为校验子。n通常得到SHE求解E的问题是一个多解问题（即未知数比方程组多），从最大似然译码的角度看，选择E的码重最小可以使译码差错最低（错得最少的事件发生的概率最大）。代数译码举例n以（7，4）汉明码为例，如果接收到码字为R(0001010)，则SHRHE(001)可以根据（7，4）汉明码的错误图样对应表得到E（0000001），因此译码结果为（0001011），其对应的信息码字为0001陪集首译码*n因为每个SHE的解有k个自由度，因此对应每个S（共有2(n-k)个）有2k个En将每种S对应的2k个E排成一行，并选择码重最小的作为行首n则每种S对应的行首称为陪集首n译码时，当得到S后将相应的陪集首作为E进行纠错，则译码差错最低（最大似然），即RE作为译码结果
