信息论与编码-第六章3

1、信息论与编码-线性分组码 上次课回顾 线性分组码信息论与编码-线性分组码上次课小结： 信道编码定理： )(RNEeeP信息论与编码-线性分组码上次课小结： 信道编码定理： 差错控制的途径： 增加码长、增加带宽、提高信噪比、噪声均化 )(RNEeeP信息论与编码-线性分组码上次课小结： 信道编码定理： 差错控制的途径： 增加码长、增加带宽、提高信噪比、噪声均化 码距与检错纠错的关系 )(RNEeeP1mindeecd信息论与编码-信道编码 最优译码与最大似然译码 信息论与编码-信道编码 最优译码与最大似然译码 最优译码： )/(max2, 2, 1RCpCiiik信息论与编码-信道编码 最优译码

2、与最大似然译码 最优译码： 最大似然译码： )/(max2, 2, 1RCpCiiik)/(max2 , 2 , 1iiiCRpCk信息论与编码-信道编码 最优译码与最大似然译码 最优译码： 最大似然译码： 当输入符号集符号概率相等时，二者等价。)/(max2, 2, 1RCpCiiik)/(max2 , 2 , 1iiiCRpCk信息论与编码-信道编码 最优译码与最大似然译码 最优译码： 最大似然译码： 当输入符号集符号概率相等时，二者等价。 汉明距离、码字重量、硬判决译码)/(max2, 2, 1RCpCiiik)/(max2 , 2 , 1iiiCRpCk信息论与编码-线性分组码一、线性

3、分组码的基本概念信息论与编码-线性分组码信息论与编码-线性分组码一、线性分组码的基本概念信息论与编码-线性分组码一、线性分组码的基本概念分组码是建立在码的代数结构基础上的，所以对分组码的讨论和分析需要一定的代数基础。信息论与编码-线性分组码一、线性分组码的基本概念分组码是建立在码的代数结构基础上的，所以对分组码的讨论和分析需要一定的代数基础。在这里我们不准备系统地学习代数知识，只介绍一些相关的内容。信息论与编码-线性分组码（1）域（Field）的概念信息论与编码-线性分组码（1）域（Field）的概念域是定义了两种代数运算的系统。信息论与编码-线性分组码（1）域（Field）的概念域是定义了两

4、种代数运算的系统。所谓代数系统，是指满足一定规律或定律的系统，系统中有一群元素构成的集合、定义了一些运算等。信息论与编码-线性分组码（1）域（Field）的概念域是定义了两种代数运算的系统。所谓代数系统，是指满足一定规律或定律的系统，系统中有一群元素构成的集合、定义了一些运算等。在域中定义的两种算术运算是：（i）加法（ii）乘法信息论与编码-信道编码（i）加法：o 集合F在加法运算下是封闭的，即如果 必有 。,FbaFba信息论与编码-信道编码（i）加法：o 集合F在加法运算下是封闭的，即如果 必有 。o 满足加法交换律，即,FbaFbaabba信息论与编码-信道编码（i）加法：o 集合F在加

5、法运算下是封闭的，即如果 必有 。o 满足加法交换律，即o 集合中一定包含一个零元素，满足,FbaFbaabbaaa0信息论与编码-信道编码（i）加法：o 集合F在加法运算下是封闭的，即如果 必有 。o 满足加法交换律，即o 集合中一定包含一个零元素，满足o 集合中每个元素都有其逆元素，元素a的逆记为-a，有a+(-a)=a-b,FbaFbaabbaaa0信息论与编码-信道编码（ii）乘法：o 集合F在乘法运算下是封闭的，即如果 ，则必有,FbaFab信息论与编码-信道编码（ii）乘法：o 集合F在乘法运算下是封闭的，即如果 ，则必有o 满足乘法结合律，即,FbaFabcabbca)()(信息

6、论与编码-信道编码（ii）乘法：o 集合F在乘法运算下是封闭的，即如果 ，则必有o 满足乘法结合律，即o 满足乘法交换律，即,FbaFabcabbca)()(baab 信息论与编码-信道编码（ii）乘法：o 集合F在乘法运算下是封闭的，即如果 ，则必有o 满足乘法结合律，即o 满足乘法交换律，即o 满足乘法分配律，即,FbaFabcabbca)()(baab bcaccba )(信息论与编码-信道编码（ii）乘法：o 集合F在乘法运算下是封闭的，即如果 ，则必有o 满足乘法结合律，即o 满足乘法交换律，即o 满足乘法分配律，即o 集合中一定有一个单位元I，对任何 有,FbaFabcabbca)

7、()(baab bcaccba )(,FaaaI 信息论与编码-信道编码（ii）乘法：o 集合F在乘法运算下是封闭的，即如果 ，则必有o 满足乘法结合律，即o 满足乘法交换律，即o 满足乘法分配律，即o 集合中一定有一个单位元I，对任何 有o 除零元素外，集合中每一个元素都有逆元素。,FbaFabcabbca)()(baab bcaccba )(,FaaaI 信息论与编码-信道编码当域由有限个元素组成时，叫做有限域，也称为伽罗华（Galois Field）域，记为GF(q)，其中q是域中元素的个数。信息论与编码-信道编码当域由有限个元素组成时，叫做有限域，也称为伽罗华（Galois Field

8、）域，记为GF(q)，其中q是域中元素的个数。在一个GF(q)域中，加法和乘法都是模q运算。信息论与编码-信道编码当域由有限个元素组成时，叫做有限域，也称为伽罗华（Galois Field）域，记为GF(q)，其中q是域中元素的个数。在一个GF(q)域中，加法和乘法都是模q运算。例如在GF(5)中：)5(mod243),5(mod023),5(mod243信息论与编码-信道编码（2）矢量空间信息论与编码-信道编码（2）矢量空间由初等数学可知，平面上的二维矢量的全体构成一个二维的矢量空间，空间的三维矢量全体构成三维矢量空间。推广可以得到一般的n维矢量空间。nRV信息论与编码-信道编码（2）矢量空

9、间由初等数学可知，平面上的二维矢量的全体构成一个二维的矢量空间，空间的三维矢量全体构成三维矢量空间。推广可以得到一般的n维矢量空间。例如：实数域R上的n重数组全体 组成一线性空间。 nRV)2();,(21GFaaaain信息论与编码-信道编码（2）矢量空间由初等数学可知，平面上的二维矢量的全体构成一个二维的矢量空间，空间的三维矢量全体构成三维矢量空间。推广可以得到一般的n维矢量空间。例如：实数域R上的n重数组全体 组成一线性空间。 GF(2)上的n重数组全体 组成一线性空间 。);,(21RaaaainnRV)2();,(21GFaaaainnV2信息论与编码-信道编码在线性空间中，能张成该

10、空间的线性独立矢量的集合称为该空间的基底。信息论与编码-信道编码在线性空间中，能张成该空间的线性独立矢量的集合称为该空间的基底。n个n重（n个GF(q)域元素的有序排列）线性无关的矢量可以构成一个n维矢量空间。信息论与编码-信道编码在线性空间中，能张成该空间的线性独立矢量的集合称为该空间的基底。n个n重（n个GF(q)域元素的有序排列）线性无关的矢量可以构成一个n维矢量空间。取其中的k个可以张成n维空间的一个子空间。信息论与编码-信道编码在线性空间中，能张成该空间的线性独立矢量的集合称为该空间的基底。n个n重（n个GF(q)域元素的有序排列）线性无关的矢量可以构成一个n维矢量空间。取其中的k个

11、可以张成n维空间的一个子空间。例如：由（1，0，0）,（0，1，0）,（0，0，1）为基底可以张成一个三维三重空间，信息论与编码-信道编码在线性空间中，能张成该空间的线性独立矢量的集合称为该空间的基底。n个n重（n个GF(q)域元素的有序排列）线性无关的矢量可以构成一个n维矢量空间。取其中的k个可以张成n维空间的一个子空间。例如：由（1，0，0）,（0，1，0）,（0，0，1）为基底可以张成一个三维三重空间，取其中的两个为基底可以构成一个二维三重空间。信息论与编码-信道编码在线性空间中，能张成该空间的线性独立矢量的集合称为该空间的基底。n个n重（n个GF(q)域元素的有序排列）线性无关的矢量可

12、以构成一个n维矢量空间。取其中的k个可以张成n维空间的一个子空间。例如：由（1，0，0）,（0，1，0）,（0，0，1）为基底可以张成一个三维三重空间，取其中的两个为基底可以构成一个二维三重空间。以互相正交的基底张成的两个空间也正交，并互称为另一个空间的零空间。这两个空间对偶。信息论与编码-信道编码（3）线性分组码一个n，k分组码，是把信息划成k个为一段（称为信息组），通过编码器变成长为n个码元的一组，作为n，k分组码的一个码字。则共可能有 个码字。k2信息论与编码-信道编码如果这些码字集合组成一个k维线性空间，则称它是一个n，k线性分组码。信息论与编码-信道编码如果这些码字集合组成一个k维线

13、性空间，则称它是一个n，k线性分组码。因此，对于线性分组码，如果 是码字，则 必定也是码字。jiCC 、jiCC21信息论与编码-信道编码如果这些码字集合组成一个k维线性空间，则称它是一个n，k线性分组码。因此，对于线性分组码，如果 是码字，则 必定也是码字。其中 是码元字符集里的任意两个元素。jiCC 、jiCC2121、信息论与编码-信道编码如果这些码字集合组成一个k维线性空间，则称它是一个n，k线性分组码。因此，对于线性分组码，如果 是码字，则 必定也是码字。其中 是码元字符集里的任意两个元素。因为一个定义了加法的域一定有零元素，如果取 ，则得到的码字一定是全零码。jiCC 、jiCC2

14、121、021信息论与编码-信道编码如果这些码字集合组成一个k维线性空间，则称它是一个n，k线性分组码。因此，对于线性分组码，如果 是码字，则 必定也是码字。其中 是码元字符集里的任意两个元素。因为一个定义了加法的域一定有零元素，如果取 ，则得到的码字一定是全零码。因此，线性分组码一定包含全零码。jiCC 、jiCC2121、021信息论与编码-信道编码如果这些码字集合组成一个k维线性空间，则称它是一个n，k线性分组码。因此，对于线性分组码，如果 是码字，则 必定也是码字。其中 是码元字符集里的任意两个元素。因为一个定义了加法的域一定有零元素，如果取 ，则得到的码字一定是全零码。因此，线性分组

15、码一定包含全零码。因此：jiCC 、jiCC2121、021),()()(),(0kkjijiCdisCWCCWCCdisd信息论与编码-信道编码也就是说：（i）两个码字之间的距离必定等于另一个码字的重量，信息论与编码-信道编码也就是说：（i）两个码字之间的距离必定等于另一个码字的重量，所以线性分组码的最小码距 等于码集中非零码字的最小重量：mindmin0,miniCCCCWdii信息论与编码-信道编码也就是说：（i）两个码字之间的距离必定等于另一个码字的重量，所以线性分组码的最小码距 等于码集中非零码字的最小重量：（ii）研究两两码字之间的距离，可用码字与全零码的距离，或各码字自身的重量来

16、代替。mindmin0,miniCCCCWdii信息论与编码-信道编码对于n，k二进制分组码，共有 个码字，可以看成是n维n重空间S的一个子空间。k2信息论与编码-信道编码对于n，k二进制分组码，共有 个码字，可以看成是n维n重空间S的一个子空间。这个子空间是由k个基底张成的，记作码空间C，它是一个k维n重空间。k2信息论与编码-信道编码对于n，k二进制分组码，共有 个码字，可以看成是n维n重空间S的一个子空间。这个子空间是由k个基底张成的，记作码空间C，它是一个k维n重空间。n维n重空间的另外n-k个基底则张成一个n-k维的子空间，称为校验空间H。k2信息论与编码-信道编码对于n，k二进制分

17、组码，共有 个码字，可以看成是n维n重空间S的一个子空间。这个子空间是由k个基底张成的，记作码空间C，它是一个k维n重空间。n维n重空间的另外n-k个基底则张成一个n-k维的子空间，称为校验空间H。分组编码器的工作，就是要把k维k重的信息组空间的 个矢量一一对应到k维n重码空间C。k2k2信息论与编码-信道编码对于n，k二进制分组码，共有 个码字，可以看成是n维n重空间S的一个子空间。这个子空间是由k个基底张成的，记作码空间C，它是一个k维n重空间。n维n重空间的另外n-k个基底则张成一个n-k维的子空间，称为校验空间H。分组编码器的工作，就是要把k维k重的信息组空间的 个矢量一一对应到k维n

18、重码空间C。因此，编码算法就要研究两个问题：（i）如何确定码空间C，和（ii）如何映射。k2k2信息论与编码-信道编码二、生成矩阵和校验矩阵信息论与编码-信道编码二、生成矩阵和校验矩阵n，k分组码的编码问题就是要在n维线性空间中，找出满足一定要求的由 个矢量组成的k维n重线性子空间，或者说，要由k个信息码元得到n-k个冗余码元。k2信息论与编码-信道编码二、生成矩阵和校验矩阵n，k分组码的编码问题就是要在n维线性空间中，找出满足一定要求的由 个矢量组成的k维n重线性子空间，或者说，要由k个信息码元得到n-k个冗余码元。设 是一组k个信息组，可以写成矢量形式 。k2kmmm,21),(21kmm

19、mm信息论与编码-信道编码二、生成矩阵和校验矩阵n，k分组码的编码问题就是要在n维线性空间中，找出满足一定要求的由 个矢量组成的k维n重线性子空间，或者说，要由k个信息码元得到n-k个冗余码元。设 是一组k个信息组，可以写成矢量形式 。编码器输出的是k维n重码空间C的一个矢量，记为 。k2kmmm,21),(21kmmmm),(21iniiiCCCC信息论与编码-信道编码二、生成矩阵和校验矩阵n，k分组码的编码问题就是要在n维线性空间中，找出满足一定要求的由 个矢量组成的k维n重线性子空间，或者说，要由k个信息码元得到n-k个冗余码元。设 是一组k个信息组，可以写成矢量形式 。编码器输出的是k

20、维n重码空间C的一个矢量，记为 。因此有k2kmmm,21),(21kmmmm),(21iniiiCCCCnjgmgmgmCkjkjjij, 2 , 1,2211信息论与编码-信道编码对二进制分组码来说， 。上式也可以写成矩阵形式：1 , 0ijgTkiniimmmccc),(),(),(2121k21igggmGC信息论与编码-信道编码对二进制分组码来说， 。上式也可以写成矩阵形式：其中， 均为一个含有n个元素的行向量。所以有1 , 0ijgTkiniimmmccc),(),(),(2121k21igggmGCk21ggg,knknggggG1111信息论与编码-信道编码G是一个k行n列的矩

21、阵，给定任何k码元的信息比特，都可以由G利用公式 求出对应的码字，因此，G被称为码的生成矩阵。mGCi信息论与编码-信道编码G是一个k行n列的矩阵，给定任何k码元的信息比特，都可以由G利用公式 求出对应的码字，因此，G被称为码的生成矩阵。可以看出，任何码字都是G的行矢量的线性组合，即mGCik21igggCkmmm21信息论与编码-信道编码G是一个k行n列的矩阵，给定任何k码元的信息比特，都可以由G利用公式 求出对应的码字，因此，G被称为码的生成矩阵。可以看出，任何码子都是G的行矢量的线性组合，即从矢量空间的角度来说，G的k个行矢量相当于k维n重码字矢量空间的一组基底，mGCik21igggC

22、kmmm21信息论与编码-信道编码G是一个k行n列的矩阵，给定任何k码元的信息比特，都可以由G利用公式 求出对应的码字，因此，G被称为码的生成矩阵。可以看出，任何码子都是G的行矢量的线性组合，即从矢量空间的角度来说，G的k个行矢量相当于k维n重码字矢量空间的一组基底，该空间的任何矢量（码字）都可以由这组基底的线性组合得到。mGCik21igggCkmmm21信息论与编码-信道编码G是一个k行n列的矩阵，给定任何k码元的信息比特，都可以由G利用公式 求出对应的码字，因此，G被称为码的生成矩阵。可以看出，任何码子都是G的行矢量的线性组合，即从矢量空间的角度来说，G的k个行矢量相当于k维n重码字矢量

23、空间的一组基底，该空间的任何矢量（码字）都可以由这组基底的线性组合得到。并且这组基底本身也是一组码字。mGCik21igggCkmmm21信息论与编码-信道编码一般形式的G，得到的码字前k位的信息位也发生了变化，信息论与编码-信道编码一般形式的G，得到的码字前k位的信息位也发生了变化，而一般来说，我们只是希望在信息位后加上冗余比特，信息论与编码-信道编码一般形式的G，得到的码字前k位的信息位也发生了变化，而一般来说，我们只是希望在信息位后加上冗余比特，所以，可以对生成矩阵通过行运算（以及列置换）作适当的变换，变成“系统性式”，信息论与编码-信道编码一般形式的G，得到的码字前k位的信息位也发生了

24、变化，而一般来说，我们只是希望在信息位后加上冗余比特，所以，可以对生成矩阵通过行运算（以及列置换）作适当的变换，变成“系统性式”，即)()(2)( 12221212111100010001)(knkknknkkpppppppppGPIk信息论与编码-信道编码一般形式的G，得到的码字前k位的信息位也发生了变化，而一般来说，我们只是希望在信息位后加上冗余比特，所以，可以对生成矩阵通过行运算（以及列置换）作适当的变换，变成“系统性式”，即这样生成的（n，k）码是系统码。)()(2)( 12221212111100010001)(knkknknkkpppppppppGPIk信息论与编码-信道编码与码空

25、间C相对应，一定存在一个对偶空间H。信息论与编码-信道编码与码空间C相对应，一定存在一个对偶空间H。对偶空间H的基底，是n维n重矢量空间的基底中，除去张成k维码字空间C的k个基底，而剩下的n-k个基底。信息论与编码-信道编码与码空间C相对应，一定存在一个对偶空间H。对偶空间H的基底，是n维n重矢量空间的基底中，除去张成k维码字空间C的k个基底，而剩下的n-k个基底。因此，H空间和C空间一定正交。即0HCTi信息论与编码-信道编码与码空间C相对应，一定存在一个对偶空间H。对偶空间H的基底，是n维n重矢量空间的基底中，除去张成k维码字空间C的k个基底，而剩下的n-k个基底。因此，H空间和C空间一定

26、正交。即生成矩阵的每一行，都是一个码字，所以有0HCTi0GHT信息论与编码-信道编码因此)(knTIPH信息论与编码-信道编码因此H叫做码字空间C的校验矩阵，)(knTIPH信息论与编码-信道编码因此H叫做码字空间C的校验矩阵，可以利用 是否等于零矢量，来判断一个 是不是码字。)(knTIPHTiHCiC信息论与编码-信道编码例题：对一个（7，4）码，其生成矩阵为1101000011010011100101010001G（1）对于信息组(1 0 1 1 )，对应码字是什么？（2）设计一个（7，4）分组编码器原理图。（3）若接收到一个7位码r=（1 0 0 1 1 0 1），判断它是否是码字。

27、信息论与编码-信道编码解：（1）由生成矩阵可知，得到的一定是系统码。由 得mGCi421743263215mmmcmmmcmmmciiik21igggCkmmm21信息论与编码-信道编码解：（1）由生成矩阵可知，得到的一定是系统码。由 得0, 0, 0765iiicccmGCi421743263215mmmcmmmcmmmciii将信息位的值(1 0 1 1 )代入，得： 信息论与编码-信道编码解：（1）由生成矩阵可知，得到的一定是系统码。由 得0, 0, 0765iiicccmGCi421743263215mmmcmmmcmmmciii将信息位的值(1 0 1 1 )代入，得： 因此，编得的

28、码字为因此，编得的码字为)1011000(iC信息论与编码-信道编码解：（1）由生成矩阵可知，得到的一定是系统码。由 得0, 0, 0765iiicccmGCi421743263215mmmcmmmcmmmciii将信息位的值(1 0 1 1 )代入，得： 因此，编得的码字为因此，编得的码字为)1011000(iC注意:加法是模2加。信息论与编码-信道编码（2）由编码后冗余位与信息位的关系，可得编码器的原理图如图所示：1m2m3m4m7ic6ic5ic输入输出421743263215mmmcmmmcmmmciii信息论与编码-信道编码（3）要检验一个码序列R是否是码字，可以使用校验矩阵H，如果

29、 ，则一定是码字，否则一定不是码字。0TRH信息论与编码-信道编码（3）要检验一个码序列R是否是码字，可以使用校验矩阵H，如果 ，则一定是码字，否则一定不是码字。0TRH100101101011100010111)(knTIPH信息论与编码-信道编码（3）要检验一个码序列R是否是码字，可以使用校验矩阵H，如果 ，则一定是码字，否则一定不是码字。因此， 就产生三个方程，只有第一个为零，另两个不为零，所以R不是码字。0TRH100101101011100010111)(knTIPHTRH信息论与编码-信道编码（3）要检验一个码序列R是否是码字，可以使用校验矩阵H，如果 ，则一定是码字，否则一定不是

30、码字。因此， 就产生三个方程，只有第一个为零，另两个不为零，所以R不是码字。系统码的前k位为信息位，后n-k位为校验位。0TRH100101101011100010111)(knTIPHTRH信息论与编码-信道编码校验矩阵H除了可以用来检验码字外，还与码的最小距离（也就和码的检错纠错能力）有关。信息论与编码-信道编码校验矩阵H除了可以用来检验码字外，还与码的最小距离（也就和码的检错纠错能力）有关。因为其中， 是H矩阵的列向量。),()(2)(1 )(2222111211n21hhhHnknknknnnhhhhhhhhhn21hhh,信息论与编码-信道编码因此，也就是说，n个矢量 一定是线性相关

31、的。TnT2T1TihhhHCiniiccc21Thj信息论与编码-信道编码因此，也就是说，n个矢量 一定是线性相关的。如果分组码的最小距离为 ，则根据线性码的特点，码集里面一定有一个码字其重量最小为 ，即有 个非零元素。TnT2T1TihhhHCiniiccc21Thjmindmindmind信息论与编码-信道编码因此，也就是说，n个矢量 一定是线性相关的。如果分组码的最小距离为 ，则根据线性码的特点，码集里面一定有一个码字其重量最小为 ，即有 个非零元素。将其代入校验矩阵的方程，左边就有 个 项，而右边为零。TnT2T1TihhhHCiniiccc21Thjmindmindmindmind

32、Thj信息论与编码-信道编码因此，也就是说，n个矢量 一定是线性相关的。如果分组码的最小距离为 ，则根据线性码的特点，码集里面一定有一个码字其重量最小为 ，即有 个非零元素。将其代入校验矩阵的方程，左边就有 个 项，而右边为零。也就是说， 个 是线性相关的。 而TnT2T1TihhhHCiniiccc21ThjmindmindmindmindThjmindThj信息论与编码-信道编码 个 一定是线性无关的1mindThj信息论与编码-信道编码 个 一定是线性无关的（反证法：如果 个 列矢量是线性相关的，则可以把其对应的系数当成码字，而该码字的重量为 ，这与码字的最小重量为 相矛盾）。1mind

33、Thj1mindThj1mindmind信息论与编码-信道编码 个 一定是线性无关的（反证法：如果 个 列矢量是线性相关的，则可以把其对应的系数当成码字，而该码字的重量为 ，这与码字的最小重量为 相矛盾）。由于H是 的矩阵，其秩最大为n-k，也就是说，最多有n-k个列矢量线性无关。1mindThj1mindThj1mindmindnkn )(信息论与编码-信道编码 个 一定是线性无关的（反证法：如果 个 列矢量是线性相关的，则可以把其对应的系数当成码字，而该码字的重量为 ，这与码字的最小重量为 相矛盾）。由于H是 的矩阵，其秩最大为n-k，也就是说，最多有n-k个列矢量线性无关。在编码的时候，

34、我们希望 越大越好，所以1mindThj1mindThj1mindmindnkn )(mind信息论与编码-信道编码 个 一定是线性无关的（反证法：如果 个 列矢量是线性相关的，则可以把其对应的系数当成码字，而该码字的重量为 ，这与码字的最小重量为 相矛盾）。由于H是 的矩阵，其秩最大为n-k，也就是说，最多有n-k个列矢量线性无关。在编码的时候，我们希望 越大越好，所以1mindThj1mindThj1mindmindnkn )(mind1,1minminkndknd即信息论与编码-信道编码也就是说，二进制（n，k）线性码的最小码距的上界是n-k+1。称这样的码为极大最小距离码（MDC:Ma

35、ximized minimum Distance Code）。信息论与编码-信道编码三、伴随式与译码信息论与编码-信道编码三、伴随式与译码1. 伴随式本节讨论如何译码。信息论与编码-信道编码三、伴随式与译码1. 伴随式本节讨论如何译码。设发送的码字为 通过有扰信道传输，信道产生的错误图样为 ，),(110NcccC),(110NeeeE信息论与编码-信道编码三、伴随式与译码1. 伴随式本节讨论如何译码。设发送的码字为 通过有扰信道传输，信道产生的错误图样为 ，接收端译码器收到的n重矢量为 ，则R=C+E),(110NcccC),(110NeeeE),(110NrrrR信息论与编码-信道编码译码

36、器的任务就是要从收到的R中得出 ，或者由R中解出错误图样 ，从而得到 ，并使译码错误概率最小。EERCC信息论与编码-信道编码译码器的任务就是要从收到的R中得出 ，或者由R中解出错误图样 ，从而得到 ，并使译码错误概率最小。对于二进制码字，模2减与模2加等同。EERCC信息论与编码-信道编码译码器的任务就是要从收到的R中得出 ，或者由R中解出错误图样 ，从而得到 ，并使译码错误概率最小。对于二进制码字，模2减与模2加等同。对于n，k分组码C，满足 ，因此EERC0CHTTTTEHHECRH)(C信息论与编码-信道编码译码器的任务就是要从收到的R中得出 ，或者由R中解出错误图样 ，从而得到 ，并

37、使译码错误概率最小。对于二进制码字，模2减与模2加等同。对于n，k分组码C，满足 ，因此若E=0，则 ，EERC0CHTTTTEHHECRH)(0RHTC信息论与编码-信道编码译码器的任务就是要从收到的R中得出 ，或者由R中解出错误图样 ，从而得到 ，并使译码错误概率最小。对于二进制码字，模2减与模2加等同。对于n，k分组码C，满足 ，因此若E=0，则 ，若 ，并且仅与错误图样E有关，而与发送什么码字无关。EERC0CHTTTTEHHECRH)(0RHT0RH0ET则,C信息论与编码-信道编码S称为接收矢量R的伴随式（校正子）。伴随式完全由E决定，它充分反映了信道的干扰情况。TTEHRHS令信

38、息论与编码-信道编码S称为接收矢量R的伴随式（校正子）。伴随式完全由E决定，它充分反映了信道的干扰情况。译码器的主要任务就是如何从S中得到最象E的错误图样 ，从而译出 。EERCTTEHRHS令信息论与编码-信道编码S称为接收矢量R的伴随式（校正子）。伴随式完全由E决定，它充分反映了信道的干扰情况。译码器的主要任务就是如何从S中得到最象E的错误图样 ，从而译出 。如果一个n，k译码器要纠正t个错误，则要求对于错误个数 的所有可能组合的错误图样，都应该有不同的伴随式与之对应。EERCtTTEHRHS令信息论与编码-信道编码2. 标准阵列由前面的讨论可知，n，k分组码的译码步骤可归结为以下三步：信

39、息论与编码-信道编码2. 标准阵列由前面的讨论可知，n，k分组码的译码步骤可归结为以下三步：（1）由接收到的R，计算伴随式 ；TRHS 信息论与编码-信道编码2. 标准阵列由前面的讨论可知，n，k分组码的译码步骤可归结为以下三步：（1）由接收到的R，计算伴随式 ；（2）若S=0，则认为接收无误。若 ，则由 S找出错误图样 ；TRHS 0S E信息论与编码-信道编码2. 标准阵列由前面的讨论可知，n，k分组码的译码步骤可归结为以下三步：（1）由接收到的R，计算伴随式 ；（2）若S=0，则认为接收无误。若 ，则由 S找出错误图样 ；（3）由 和R找出 。TRHS 0S EEERC信息论与编码-信道

40、编码2. 标准阵列由前面的讨论可知，n，k分组码的译码步骤可归结为以下三步：（1）由接收到的R，计算伴随式 ；（2）若S=0，则认为接收无误。若 ，则由 S找出错误图样 ；（3）由 和R找出 。这里最关键的是由S找出E，只要找出的E是正确的，译出的码也是正确的。由S的定义式， ，即TRHS 0S EEERCTEHS 信息论与编码-信道编码共有n-k个方程，但有n个未知量，所以解不唯一。Tnknnknnknhhhheeesss)(11 )(112121),(),(信息论与编码-信道编码共有n-k个方程，但有n个未知量，所以解不唯一。对于二进制，少一个方程导致两个解，少两个方程导致四个解，少k个方

41、程导致有 个解.Tnknnknnknhhhheeesss)(11 )(112121),(),(k2信息论与编码-信道编码共有n-k个方程，但有n个未知量，所以解不唯一。对于二进制，少一个方程导致两个解，少两个方程导致四个解，少k个方程导致有 个解.也就是说，可以解出 个不同的错误图样，从而对应了 个码字（码字的全部可能）。Tnknnknnknhhhheeesss)(11 )(112121),(),(k2k2k2信息论与编码-信道编码共有n-k个方程，但有n个未知量，所以解不唯一。对于二进制，少一个方程导致两个解，少两个方程导致四个解，少k个方程导致有 个解.也就是说，可以解出 个不同的错误图样

42、，从而对应了 个码字（码字的全部可能）。根据最大似然译码规则，应该译成可能性最大的那个码字。Tnknnknnknhhhheeesss)(11 )(112121),(),(k2k2k2信息论与编码-信道编码对于二进制对称信道，若差错概率为p，则错一个比特的概率（ ）大于错两个比特的概率（ ），。1)1 (npp22)1 (npp信息论与编码-信道编码对于二进制对称信道，若差错概率为p，则错一个比特的概率（ ）大于错两个比特的概率（ ），。所以，应该译成所有 个差错图样中重量最小的那一个。1)1 (npp22)1 (nppk2信息论与编码-信道编码对于二进制对称信道，若差错概率为p，则错一个比特的

43、概率（ ）大于错两个比特的概率（ ），。所以，应该译成所有 个差错图样中重量最小的那一个。但如果每接收一个R就要解一次方程组，显然太麻烦了。1)1 (npp22)1 (nppk2信息论与编码-信道编码对于二进制对称信道，若差错概率为p，则错一个比特的概率（ ）大于错两个比特的概率（ ），。所以，应该译成所有 个差错图样中重量最小的那一个。但如果每接收一个R就要解一次方程组，显然太麻烦了。可以预先把不同S下的方程组解出来，并得到最大概率的那个错误图样，和错误图样对应的R，存成一个表格，译码的时候，只要根据不同的R查表，就可以得到对应的最大可能的码字。1)1 (npp22)1 (nppk2信息论与

44、编码-信道编码表5-4-1就是一个这样的表，叫做标准阵列译码表。信息论与编码-信道编码表5-4-1 标准阵列译码表11ES 22ES jjES knkn22ES00011 CE212ECEjjECE1knknECE212221CCE22CE 2CEj22CEkniCE 2ijCE iCEkn2iiCCE1kkCCE221kCE22kCEj2kknCE22信息论与编码-信道编码表5-4-1就是一个这样的表，叫做标准阵列译码表。表中有 列，每一列的头一个元素对应的是一个码字，所以共对应 个不同的码字；k2k2信息论与编码-信道编码表5-4-1就是一个这样的表，叫做标准阵列译码表。表中有 列，每一列

45、的头一个元素对应的是一个码字，所以共对应 个不同的码字；每一列的列首元素下，是 个禁用码字（即n维空间点中不是码字的那些点），k2k2kn2信息论与编码-信道编码表5-4-1就是一个这样的表，叫做标准阵列译码表。表中有 列，每一列的头一个元素对应的是一个码字，所以共对应 个不同的码字；每一列的列首元素下，是 个禁用码字（即n维空间点中不是码字的那些点），代表该列首元素（码字）在不同差错图样下偏移后所对应的空间点，正好对应了 个不同的伴随式。k2k2kn2kn2信息论与编码-信道编码表5-4-1就是一个这样的表，叫做标准阵列译码表。表中有 列，每一列的头一个元素对应的是一个码字，所以共对应 个不

46、同的码字；每一列的列首元素下，是 个禁用码字（即n维空间点中不是码字的那些点），代表该列首元素（码字）在不同差错图样下偏移后所对应的空间点，正好对应了 个不同的伴随式。全部的元素个数是 ，正好是n维矢量空间中总的点数，也就是说，每一个空间点k2k2kn2kn2nkkn222信息论与编码-信道编码都有其所对应的码字，这样，在译码的时候，当接收到一个R后，只要在标准阵列表中找到该R的位置，这一列的列首元素就是它应该译成的码字。信息论与编码-信道编码都有其所对应的码字，这样，在译码的时候，当接收到一个R后，只要在标准阵列表中找到该R的位置，这一列的列首元素就是它应该译成的码字。表中第一行对应的是 个

47、码字，相当于差错为零；第二行到第n+1行分别对应n个差错为1的差错图样；。每一行的行首元素叫做陪集首，是该行所对应的错误图样。k2信息论与编码-信道编码都有其所对应的码字，这样，在译码的时候，当接收到一个R后，只要在标准阵列表中找到该R的位置，这一列的列首元素就是它应该译成的码字。表中第一行对应的是 个码字，相当于差错为零；第二行到第n+1行分别对应n个差错为1的差错图样；。每一行的行首元素叫做陪集首，是该行所对应的错误图样。但是，错误图样数有 个，标准阵列译码表只有 行，代表 个伴随式和错误图样。那么，k2n2kn2kn2信息论与编码-信道编码怎么从 个错误图样中选择 个，作为陪集首？n2k

48、n2信息论与编码-信道编码怎么从 个错误图样中选择 个，作为陪集首？原则当然是要使得译码的错误概率最小。n2kn2信息论与编码-信道编码怎么从 个错误图样中选择 个，作为陪集首？原则当然是要使得译码的错误概率最小。前面已经说过，对BSC信道，当错误概率p0.5时，产生一个错误的概率比产生两个错误的概率要大，产生两个错误的概率比产生3个错误的概率要大，。n2kn2信息论与编码-信道编码怎么从 个错误图样中选择 个，作为陪集首？原则当然是要使得译码的错误概率最小。前面已经说过，对BSC信道，当错误概率p0.5时，产生一个错误的概率比产生两个错误的概率要大，产生两个错误的概率比产生3个错误的概率要大

49、，。总之，错误图样重量越小，产生的可能性就越大。n2kn2信息论与编码-信道编码怎么从 个错误图样中选择 个，作为陪集首？原则当然是要使得译码的错误概率最小。前面已经说过，对BSC信道，当错误概率p0.5时，产生一个错误的概率比产生两个错误的概率要大，产生两个错误的概率比产生3个错误的概率要大，。总之，错误图样重量越小，产生的可能性就越大。因此，译码器必须首先保证能正确纠正这些出现可能性比较大的错误图样，这相当于构造标准阵列译码表时，要求按照错误图样重量从轻到重的顺序挑选为陪首集。n2kn2信息论与编码-信道编码例题：某（5，2）系统线性码的生成矩阵是设收到的码是R=(10101)，请先构造该

50、码的标准阵列译码表，然后译出发码的估值C。1101111001G信息论与编码-信道编码例题：某（5，2）系统线性码的生成矩阵是设收到的码是R=(10101)，请先构造该码的标准阵列译码表，然后译出发码的估值C。解： （1）标准阵列译码表 n-k=3， ，即标准阵列译码表共有8行，每行代表一种错误图样。按照错误图样重量从轻8231101111001G信息论与编码-信道编码到重的顺序，无差错（错误图样重量为0）的有一 种，重量为1的有 种，重量为2的有 种。5151025信息论与编码-信道编码到重的顺序，无差错（错误图样重量为0）的有一 种，重量为1的有 种，重量为2的有 种。我们挑选的陪首集是1

51、种无错误（重量为0），5种有一个错误（重量为1）和重量为2的10 种里面的2种。5151025信息论与编码-信道编码到重的顺序，无差错（错误图样重量为0）的有一 种，重量为1的有 种，重量为2的有 种。我们挑选的陪首集是1种无错误（重量为0），5种有一个错误（重量为1）和重量为2的10 种里面的2种。码字共有 种，将信息组的可能组合(00)、(01)、(10)、(11)代入生成矩阵，得到四个码字为：(00000)、(10111)、(01101)、(11010)。51510254222k信息论与编码-信道编码到重的顺序，无差错（错误图样重量为0）的有一 种，重量为1的有 种，重量为2的有 种。我

52、们挑选的陪首集是1种无错误（重量为0），5种有一个错误（重量为1）和重量为2的10 种里面的2种。码字共有 种，将信息组的可能组合(00)、(01)、(10)、(11)代入生成矩阵，得到四个码字为：(00000)、(10111)、(01101)、(11010)。得到的标准阵列译码表如下图所示：51510254222k信息论与编码-信道编码标准阵列译码表 S1=000E1+C1=00000C2=10111 C3=01101 C4=11010 S2=111E2=10000 00111 11101 01010 S3=101E3=01000 11111 00101 10010 S4=100E4=001

53、00 10011 01001 11110 S5=010E5=00010 10101 01111 11000 S6=001E6=00001 10110 01100 11011 S7=011E7=00011 10100 01110 11001 S8=110E8=00110 10001 01011 11100信息论与编码-信道编码当然，上述的标准阵列译码表不是唯一的，因为从10种重量为2的错误图样中选择两种，可以是任意选的。信息论与编码-信道编码当然，上述的标准阵列译码表不是唯一的，因为从10种重量为2的错误图样中选择两种，可以是任意选的。标准阵列译码表需要把 个n重存储在译码器中。其复杂性随n的增大指数增长，当n比较大时很不实用。n2信息论与编码-信道编码当然，上述的标准阵列译码表不是唯一的，因为从10种重量为2的错误图样中选择两种，可以是任意选的。标准阵列译码表需要把 个n重存储在译码器中。其复杂性随n的增大指数增长，当n比较大时很不实用。可以把标准阵列译码表进行简化，即只存储伴随式和错误图样的对应关系，译码时先计算得到伴随式，再查表得到错误图样，从而得到译码码字。n2信息论与编码-信道编码这样码表可以简化，但译码时的计算量增加了。信息论与编码-信道编码这样码表可以简化，但译码时的计算量增加了。并且当n和k都比较大时，即使采用