1、2023-5-161线性分组码线性分组码2023-5-162主要讲授内容主要讲授内容 线性分组码的定义线性分组码的定义 线性线性 监督矩阵监督矩阵 生成矩阵生成矩阵 线性分组码的性质线性分组码的性质 线性性线性性封闭性封闭性 最小码距等于非零许用码组的最小码重最小码距等于非零许用码组的最小码重 线性分组码的构造线性分组码的构造 线性子空间构造线性子空间构造 汉明式构造汉明式构造 线性分组码的译码线性分组码的译码 最大似然译码最大似然译码 代数译码代数译码2023-5-163线性分组码定义线性分组码定义(n,k)线性分组码定义线性分组码定义 从从k维空间到维空间到n维空间的一一映射的映射空间，并
2、且这种映射维空间的一一映射的映射空间，并且这种映射满足线性性。满足线性性。F：ICK维信息空间：IN维码空间：C2023-5-164线性性线性性 若若k维空间中的信息码字维空间中的信息码字A，B，其映射结果为，其映射结果为F(A)、F(B),满足满足 F(cA+dB)=c*F(A)+d*F(B)则称则称F为线性映射。为线性映射。F的值空间就构成线性分组码的码空间。的值空间就构成线性分组码的码空间。（n,k）码的一些基本数字关系）码的一些基本数字关系 信息空间大小：信息空间大小：2k 种信息码字种信息码字 I(k-1),I(k-2),I(0)码空间大小：码空间大小：2k种许用码字种许用码字 a(
3、n-1),a(n-2),a(0)提示：经过（提示：经过（n，k）编码后，空间发生扩展）编码后，空间发生扩展2023-5-165编码中如何描述线性性编码中如何描述线性性(n,k)线性分组码的另一种定义线性分组码的另一种定义 定义：定义：满足满足HA0的所有的所有A的集合的集合C称为（称为（n，k）线性分组码，其中）线性分组码，其中H是一个是一个nk行行n列的二元域上的矩阵，称为监督矩阵（校验矩阵）。列的二元域上的矩阵，称为监督矩阵（校验矩阵）。解释解释 HA0定义了一种线性映射，且是一一对应的。定义了一种线性映射，且是一一对应的。若若A,B满足定义，则易知：满足定义，则易知：H(cA+dB)=0
4、，即，即cA+dB也属于也属于C。例例1 110 1001 10 10 101 0 1100 1H2023-5-166（n,k）码的监督矩阵）码的监督矩阵 满足满足HA0的所有需用码组的所有需用码组A可以解如下方程得：可以解如下方程得：6543210111010001101010010110010aaaaaaa2023-5-167方程的解方程的解 3个方程，个方程，7个未知数，只能得到个未知数，只能得到4个自由度（个自由度（4个信息比特）个信息比特）654265316430aaaaaaaaaaaa 6 5 4 3 2 1 06 5 4 31 0 0 0 1 1 10 1 0 0 1 1 00
5、0 1 0 1 0 10 0 0 1 0 1 1aaa aa aaaaa aAUG2023-5-168生成矩阵生成矩阵 信息码字信息码字U6543()a a a aU 生成矩阵生成矩阵G1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1G2023-5-169（7，4）码的许用码组）码的许用码组 由于由于 I 是是4维空间中的一个码字，其取值可能性为维空间中的一个码字，其取值可能性为16种种，将，将16个码字分别乘以生成矩阵个码字分别乘以生成矩阵G，则得到（，则得到（7，4）码的所有许用码组。码的所有许用码组。(0000000)(000101
6、1)(0010101)(0011110)(0100110)(0101101)(0110011)(0111000)(1000111)(1001100)(1010010)(1011001)(1100001)(1101010)(1110100)(1111111)2023-5-1610小结小结 线性（线性（n，k）码的关键参数）码的关键参数 H：监督矩阵：监督矩阵 G：生成矩阵：生成矩阵 二者知一即可知关于（二者知一即可知关于（n，k）的所有信息。）的所有信息。引申内容引申内容（n，k）码的所有码字构成）码的所有码字构成n维空间中的维空间中的k维线性子空间维线性子空间（n，k）的生成矩阵的）的生成矩阵
7、的k行即是行即是n维空间的维空间的k个基个基 以以n维空间的另外维空间的另外nk个基构成的生成矩阵所生成的线性分组个基构成的生成矩阵所生成的线性分组码（码（n，nk）称为（）称为（n，k）码的对偶码。）码的对偶码。2023-5-1611线性分组码的性质线性分组码的性质 封闭性封闭性 推论：最小码距等于最小码重（全零码除外）推论：最小码距等于最小码重（全零码除外）线性性线性性 推论：任意码字的线性和还是许用码字推论：任意码字的线性和还是许用码字2023-5-1612（n，k）码的构造）码的构造 方法方法 1、已知、已知H或或G，直接得到（，直接得到（n，k）线性分组码。）线性分组码。2、找出、找
8、出n维空间的维空间的n个基，任意选择个基，任意选择k个作为（个作为（n，k）码的生）码的生成矩阵成矩阵G。（如何找出合适的基使构成的码具有大的最小码距？）（如何找出合适的基使构成的码具有大的最小码距？）3、n维空间中任意挑选维空间中任意挑选2k个码字作为（个码字作为（n，k）码的需用码）码的需用码组，并与组，并与2k个信息码字构成一一映射。（注：此时不能保证个信息码字构成一一映射。（注：此时不能保证构造出的（构造出的（n，k）码是线性码）码是线性码）4、其它、其它 如：汉明码、循环码、如：汉明码、循环码、BCH码等代数构造方法码等代数构造方法2023-5-1613（n，k）汉明码）汉明码 汉明
9、码是一种特殊的线性分组码，满足关系汉明码是一种特殊的线性分组码，满足关系 2(n-k)-1=n 只能纠一个错只能纠一个错 最小码距为最小码距为3 汉明码的构造思路汉明码的构造思路 由于有由于有n-k个监督比特（冗余信息个监督比特（冗余信息)，因此可以组成，因此可以组成2(n-k)个图样，个图样，每个图样对应信道传输的一种传输结果。每个图样对应信道传输的一种传输结果。当码字当码字A经过信道传输后，接收到的码字为经过信道传输后，接收到的码字为RAE E称为信道错误图样称为信道错误图样 当信道只发生一个错误时，当信道只发生一个错误时，E的图样为（的图样为（10000)(01000)(00001)，共
10、，共n种种发生发生1个比特传输错误的情况。个比特传输错误的情况。使信道的错误图样与使信道的错误图样与nk个比特组成的情况一一对应，再加上无误个比特组成的情况一一对应，再加上无误传输的情况，则能纠正一个错误比特的最少监督位应满足关系传输的情况，则能纠正一个错误比特的最少监督位应满足关系 2(n-k)-1=n2023-5-1614（7，4）汉明码）汉明码 S1,S2,S3 a6,a5,a4,a3,a2,a1,a0 0 0 0 无错无错 0 0 1 a0错错 0 1 0 a1错错 1 0 0 a2错错 0 1 1 a3错错 1 0 1 a4错错 1 1 0 a5错错 1 1 1 a6错错 2023-
11、5-1615 为了构造出使为了构造出使HA0，并且满足上述关系的并且满足上述关系的H，则由上述关系可以得，则由上述关系可以得到到 H0000001=0 0 1 H0000010=0 1 0 H0000100=1 0 0 H0001000=0 1 1 H0010000=1 0 1 H0100000=1 1 0 H1000000=1 1 1H的第的第7列为列为001H的第的第6列为列为010H的第的第5列为列为100H的第的第4列为列为011H的第的第3列为列为101H的第的第2列为列为110H的第的第1列为列为1112023-5-1616（n，k）汉明码的监督矩阵）汉明码的监督矩阵 由上可知：由
12、上可知：汉明码的监督矩阵由汉明码的监督矩阵由nk行，行，n列组成，列为除全零外的其它列组成，列为除全零外的其它所有所有nk元组的组合。元组的组合。由于每列对应一个由于每列对应一个1比特错误图样，因此能纠正一个信道错误比特错误图样，因此能纠正一个信道错误 当信道发生当信道发生1个以上错误时，汉明码不能保证正确纠正错误。个以上错误时，汉明码不能保证正确纠正错误。2023-5-1617线性分组码的译码线性分组码的译码其中：其中：xk=Es或或Es (最佳接收），最佳接收），nk是均值为是均值为0，方差为，方差为N0/2的高斯随机变量的高斯随机变量kkkrxn 最大似然译码最大似然译码 设采用设采用B
13、PSK调制方式，则接收端接收到信号为调制方式，则接收端接收到信号为 译码时假设码字同步（即接收端已知码字的起始），译码时假设码字同步（即接收端已知码字的起始），则接收端以则接收端以120(.)nnr rr作为判决作为判决120(.)nnxxx的依据。的依据。2023-5-1618最大似然译码最大似然译码 最大似然译码的结果为最大似然译码的结果为 120120120120120120.120120.21.000.0argmax(.)|.argmax.|.1argmaxexp1argmaxexpkknnnnnnnnkkIIIInnnnXxxxniiXxxxinXxxxfr rrIIIfr rrxx
14、xrxNNN12001niiirxN2023-5-1619最大似然译码最大似然译码 软判决软判决1220niiidrx欧式距离欧式距离最小的码字最小的码字X对应的信息码字作为对应的信息码字作为判决结果。判决结果。硬判决（如硬判决（如BSC信道时）信道时）此时此时rk被判决成被判决成Es或或Es，因此，因此1222204 niisidrxErx与 不 相同的位置欧式距离退化成两个码字间的码距欧式距离退化成两个码字间的码距D(r,X)即可判决即可判决2023-5-1620最大似然译码示例最大似然译码示例 若若(4,2)码的许用码字为码的许用码字为(0000)(0101)(1010)(1111)，经
15、过信道传输（，经过信道传输（BPSK调制调制0-1,1-+1），接收到），接收到信号信号r=(-0.3,-0.7,1.5,0.4),则接收点与各许用码字间的则接收点与各许用码字间的欧式距离为：欧式距离为：D(r,0)=(-0.3+1)2+(-0.7+1)2+(1.5+1)2+(0.4+1)2=8.79 D(r,1)=(-0.3+1)2+(-0.7-1)2+(1.5+1)2+(0.4-1)2 =9.99 D(r,2)=(-0.3-1)2+(-0.7+1)2+(1.5-1)2+(0.4+1)2=3.99 D(r,3)=(-0.3-1)2+(-0.7-1)2+(1.5-1)2+(0.4-1)2 =5
16、.19 最大似然判决结果为最大似然判决结果为1010对应的信息码字对应的信息码字2 上例中，如果接收到的信号经过硬判决得到上例中，如果接收到的信号经过硬判决得到(-1,-1,1,1)，则，则 d(r,0)=2 d(r,1)=2,d(r,2)=2,d(r,3)=2 判决结果可以是四个码字中的任意一个。判决结果可以是四个码字中的任意一个。2023-5-1621代数译码代数译码 代数译码均是基于硬判决的译码代数译码均是基于硬判决的译码 代数译码原理代数译码原理 接收到的码字接收到的码字RAE，对，对R进行校验进行校验SHR 如果如果S0，则认为，则认为R是许用码字，从而认为信道无误。是许用码字，从而
17、认为信道无误。如果如果S0，则，则S代表错误的图样，因为代表错误的图样，因为HR=H(A+E)=HE，即，即S仅与错误仅与错误图样有关，因此根据不同的错误图样进行纠正信道错误。图样有关，因此根据不同的错误图样进行纠正信道错误。通常称通常称S=HR为校验子。为校验子。通常得到通常得到SHE求解求解E的问题是一个多解问题（即未知数比方的问题是一个多解问题（即未知数比方程组多），从最大似然译码的角度看，选择程组多），从最大似然译码的角度看，选择E的码重最小可以的码重最小可以使译码差错最低（错得最少的事件发生的概率最大）。使译码差错最低（错得最少的事件发生的概率最大）。2023-5-1622代数译码举
18、例代数译码举例 以（以（7，4）汉明码为例，如果接收到码字为）汉明码为例，如果接收到码字为R(0001010)，则，则SHRHE(001)1 110 1001 10 10 101 0 1100 1H可以根据（7，4）汉明码的错误图样对应表得到E（0000001），因此译码结果为（0001011），其对应的信息码字为00012023-5-1623陪集首译码陪集首译码 因为每个因为每个SHE的解有的解有k个自由度，因此对应每个个自由度，因此对应每个S（共有共有2(n-k)个）有个）有2k个个E 将每种将每种S对应的对应的2k个个E排成一行，并选择码重最小的排成一行，并选择码重最小的作为行首作为行首 则每种则每种S对应的行首称为陪集首对应的行首称为陪集首 译码时，当得到译码时，当得到S后将相应的陪集首作为后将相应的陪集首作为E进行纠错，进行纠错，则译码差错最低（最大似然），即则译码差错最低（最大似然），即RE作为译码结果作为译码结果2023-5-1624Thank you!
