西电纠错码课件---第三章 线性分组码.ppt

1、第三章 线性分组码,课件下载地址 密码:111111,要求掌握的内容,线性分组码的定义及性质 码的一致校验矩阵和生成矩阵 码的伴随式、标准阵列及译码 汉明码及译码 RM码的基本原理 格雷码的基本编译码原理,3.1 线性分组码基本概念,线性空间 线性分组码定义 线性分组码的生成矩阵 线性分组码的校验矩阵 对偶码、系统码和缩短码 汉明码,一、线性空间(p38),定义1(线性空间)：如果域F上的n重元素集合V满足下述条件，称V是域F上的一个n维线性空间： 1) V 关于加法构成阿贝尔群 2) 对于V中的任意元素v和F中任意元素c(纯量或标量)，cv一定属于集合V(数乘运算) 3) 分配律成立 c(u

2、+v)=cu+cv,(c+d)v=cv+dv 4) 结合律成立 (cd)v=c(dv),加法和乘法运算均是在域F上定义的加和乘运算,Examples,1、全体n重整数,2、全体n重偶数,3、全体n重实数,6、GF(q)上的n重,4、全体n重复数,5、全体n重有理数,不是线性空间,不是线性空间,定义2(域F上的线性组合) 定义3(线性相关和线性无关),加法和乘法运算均是在域F上定义的加和乘运算,定义4(张成)：给定线性空间V和V中的一个子集S，若V中的任意一个矢量均可用S中的矢量线性组合生成，则称S张成了矢量空间V。 定义5(基底和维数)：给定线性空间V，能张成该空间的线性独立矢量的集合称为V的

3、基底，而线性独立矢量的数目称为V的维数,零空间(P48)：若V1是n维空间V的子空间，则和V1中每一个n维矢量均正交的所有矢量，构成V的另一个子空间V2，称V2为V1的零空间。 若n维空间V的子空间V1的维数为k，则V1的零空间的维数为n-k。,二、线性分组码的定义（p52）,定义3.1.1 n， k线性分组码是GF(q )上的n维线性空间Vn中的一个k维子空间Vn,k。 由于该线性子空间在加法运算下构成阿贝尔群， 所以线性分组码又称为群码。 用(cn-1， cn-2， ， c1， c0)表示n， k码的一码字， 其中每一分量ciGF(q)。,二、线性分组码的定义（p52）,如果一个线性分组码

4、的码字可分成消息部分和冗余部分，其中消息部分是k个未经处理的原始消息，冗余部分是产生的校验位，则该类码称为线性系统分组码,三、线性分组码的生成矩阵(p56),由于n,k,d线性分组码是一个k维线性空间,因此，必可找到k个线性无关的码字 ，使得C中的 任何一个码字v都可由这k个码字的线性组合，即,G称为该分组码的生成矩阵,三、线性分组码的生成矩阵(p56),一个n,k,d线性系统码的生成矩阵G具有如下形式,P矩阵,单位矩阵,三、线性分组码的生成矩阵(p56),例：7，4线性码的生成矩阵G为,三、线性分组码的生成矩阵(p56),注： 生成矩阵G中的每一行都是一个码字 任意k个线性独立的码字都可以作

5、为生成矩阵 给定一个n,k,d线性分组码，其生成矩阵可有多个,四、线性分组码的一致校验矩阵,n ， k ， d分组码的编码问题就是在n 维线性空间Vn 中， 如何找出满足一定要求的， 有2k 个矢量组成的k 维线性子空间Vn， k 。 或者说， 在满足给定条件(码的最小距离d或码率R)下， 如何从已知的k 个信息元求得r=n -k 个校验元。,相当于建立一组线性方程组， 已知k 个系数， 要求n-k 个未知数， 使得到的码恰好有所要求的最小距离d。,n-k个校验位可用k个已知的信息位表示出来,四、线性分组码的校验矩阵(P54),校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k,以校验矩

6、阵的n-k行为基底，可张成一个n-k维线性子空间,Examples,设7， 3， 4码， 若c6， c5， c4代表3个信息元， 则c3， c2， c1， c0 这 4 个校验元， 可由以下线性方程组求得：,Examples,若用矩阵形式，这些线性方程组可表示为：,称上式中的4行7列矩阵为7， 3， 4码的一致校验矩阵， 通常用H 表示， 该码的,或,线性分组码的校验矩阵是一个(n -k )n 阶矩阵。 由校验矩阵可以很快地建立码的线性方程组：,或,简写为 HCT=0T 或 CHT=0,注： 1)校验矩阵是一个(n -k )n阶的矩阵，各行之间是线性无关的，即 校验矩阵的行秩为n-k 2) 校

7、验矩阵的n-k行为基底，可张成一个n-k维线性子空间 3) 任意一个合法码字C均满足 HCT=0T 4) 交换校验矩阵的各列并不影响其纠错能力,校验矩阵也可用于编码,设7， 3， 4码， 若c6， c5， c4代表3个信息元， 则c3， c2， c1， c0 这 4 个校验元， 可由以下线性方程组求得：,假设 c6=1， c5=0， c4=1， 求c3， c2， c1， c0。 由上述线性方程组可知： c3=c6+c4=1+1=0 c2=c6+c5+c4=1+0+1=0 c1=c6+c5=1+0=1 c0=c5+c4=0+1=1 由此得到的码字为： (1010011)。,1)对于任一个n,k线

8、性分组码，存在一个k)n阶的生成矩阵G，其行空间为码C，即该线性分组码的所有的码字都可由生成矩阵获得。 2) 同时，该分组码还存在一个(n -k )n阶的校验矩阵，使得当且仅当 时，n维向量v是线性分组码的一个码字。任意一个合法码字C均满足 HCT=0T 。,小 结,校验矩阵与生成矩阵之间的关系,校验矩阵H与任意一个码字之积为零，因此有,校验矩阵H中各行张成的子空间的零空间即为生成矩阵G各行张成的子空间。,系统码的生成矩阵和校验矩阵,典型生成矩阵,典型校验矩阵,或,定理3.1.1 n ， k ， d线性分组码的最小距离等于非零码字的最小重量。,五、线性分组码的最小汉明距离,定理3.1.2 GF

9、(2)上n ， k ， d线性分组码中， 任何两个码字C1， C2之间有如下关系： w(C1+C2)=w(C1)+w(C2)-2w(C1C2) 或 d(C1， C2)w(C1)+w(C2) 式中， C1C2是两个码字的内积。,推论3.1.1 GF(2)上线性分组码任3个码字C1， C2， C3之间的汉明距离， 满足以下三角不等式 d(C1， C2)+d(C2， C3)d(C1， C3),定理3.1.3 任何n ， k ， d线性分组码， 码字的重量或全部为偶数， 或者奇数重量的码字数等于偶数重量的码字数。,定理3.1.4:n,k,d线性分组码，其校验矩阵为H，对于任意汉明重量为l的码字，存在H

10、的l个列向量，满足这l列的和等于零，反之，若存在H的l个列向量，其和为零，则该码中有汉明重量为l的码字。,证明：将校验矩阵写成如下形式,令 表示重量为l的码字， 则v中有l个非零分量，其中非零分量的位置记为,从而，H 中有l列向量的和为零，定理前半部分得证。,则有,假设 是H的l个列向量，满足,构造一个二进制向量x，它的非零分量的位置是,向量x是该码中一个汉明重量为l的码字。,推论1(p61,定理3.3.1):n,k,d线性分组码最小汉明距离等于d的充要条件是：H的任意d-1列线性无关 注：交换H矩阵的各列，不会影响码的最小距离，因此，所有列相同但排列位置不同的H所对应的分组码，在纠错能力和其

11、他码参数上完全等价。 推论2：n,k,d线性分组码的最大可能的最小汉明距离为n-k+1 若系统码的最小距离d=n-k+1，则称此码为极大距离可分码，MDS码。,推论证明 由于校验矩阵H的n-k行是线性无关的，也就是说H的行秩为n-k，从而可推出H的列秩最大是n-k，即H最多有任意n-k列线性无关，由定理1得到n-k=d-1,有d=n-k+1,六、几个概念(P57-58),对偶码、系统码和缩短码,对偶码 设n,k,d线性分组码C的生成矩阵为G，校验矩阵为H，以H作为生成矩阵，G为对应的校验矩阵，可构造另一个n,n-k,d线性分组码C1，我们称C1为C的对偶码。,问题：C1和C的最小汉明距离之间有

12、什么关系？,如果一个码的对偶码就是它自己，则称该类码为自偶码。,易证，,因此该码为一个自偶码。,缩短码,从n,k,d线性分组码的所有码字中，把前面i位全为零的码字,挑选出来构成一个新的子集，该子集即为n,k,d的缩短码。,问题：最小汉明距离有什么变化？,Example,7,3,4码：0000000，0011101，0100111，0111010，1001110，1010011，1101001，1110100,6,2,4码：000000，011101， 100111，111010,去掉G的第一列第一行，是否就可得到缩短码的生成矩阵Gs,对系统码而言，去掉G的前i列和前i就可得到缩短码的生成矩阵G

13、s。去掉校验矩阵的前i列，可得到缩短码的校验矩阵Hs,七、汉明码(p62),参数 码长： n=2m-1 信息位长度：k=2m-1-m 最小汉明距离：d=3 校验矩阵有 m行，2m-1列，取互不相同的m重构成,GF(2)上的7,4,3汉明码 001,010,011,100,101,110,111,000 校验矩阵为：,Examples,线性分组码的定义（p52）,定义3.1.1 n， k线性分组码是GF(q )上的n维线性空间Vn中的一个k维子空间Vn,k。 由于该线性子空间在加法运算下构成阿贝尔群， 所以线性分组码又称为群码。 用(cn-1， cn-2， ， c1， c0)表示n， k码的一码

14、字， 其中每一分量ciGF(q)。,线性分组码的定义（p52）,如果一个线性分组码的码字可分成消息部分和冗余部分，其中消息部分是k个未经处理的原始消息，冗余部分是产生的校验位，则该类码称为线性系统分组码,线性分组码的生成矩阵(p56),由于n,k,d线性分组码是一个k维线性空间,因此，必可找到k个线性无关的码字 ，使得C中的 任何一个码字v都可由这k个码字的线性组合，即,G称为该分组码的生成矩阵,注： 生成矩阵G中的每一行都是一个码字 任意k个线性独立的码字都可以作为生成矩阵 给定一个n,k,d线性分组码，其生成矩阵可有多个,线性分组码的一致校验矩阵,n ， k ， d分组码的编码问题就是在n

15、 维线性空间Vn 中， 如何找出满足一定要求的， 有2k 个矢量组成的k 维线性子空间Vn， k 。 或者说， 在满足给定条件(码的最小距离d或码率R)下， 如何从已知的k 个信息元求得r=n -k 个校验元。,相当于建立一组线性方程组， 已知k 个系数， 要求n-k 个未知数， 使得到的码恰好有所要求的最小距离d。,n-k个校验位可用k个已知的信息位表示出来,线性分组码的校验矩阵(P54),校验矩阵的各行之间是线性无关的，即校验矩阵的行秩为n-k,以校验矩阵的n-k行为基底，可张成一个n-k维线性子空间,注： 1)校验矩阵是一个(n -k )n阶的矩阵，各行之间是线性无关的，即 校验矩阵的行

16、秩为n-k 2) 校验矩阵的n-k行为基底，可张成一个n-k维线性子空间 3) 任意一个合法码字C均满足 HCT=0T 4) 交换校验矩阵的各列并不影响其纠错能力,校验矩阵也可用于编码,设7， 3， 4码， 若c6， c5， c4代表3个信息元， 则c3， c2， c1， c0 这 4 个校验元， 可由以下线性方程组求得：,假设 c6=1， c5=0， c4=1， 求c3， c2， c1， c0。 由上述线性方程组可知： c3=c6+c4=1+1=0 c2=c6+c5+c4=1+0+1=0 c1=c6+c5=1+0=1 c0=c5+c4=0+1=1 由此得到的码字为： (1010011)。,1

17、)对于任一个n,k线性分组码，存在一个k)n阶的生成矩阵G，其行空间为码C，即该线性分组码的所有的码字都可由生成矩阵获得。 2) 同时，该分组码还存在一个(n -k )n阶的校验矩阵，使得当且仅当 时，n维向量v是线性分组码的一个码字。任意一个合法码字C均满足 HCT=0T 。,校验矩阵与生成矩阵之间的关系,校验矩阵H与任意一个码字之积为零，因此有,校验矩阵H中各行张成的子空间的零空间即为生成矩阵G各行张成的子空间。,系统码的生成矩阵和校验矩阵,典型生成矩阵,典型校验矩阵,或,线性分组码的最小距离,定理3.1.4:n,k,d线性分组码，其校验矩阵为H，对于任意汉明重量为l的码字，存在H的l个列

18、向量，满足这l列的和等于零，反之，若存在H的l个列向量，其和为零，则该码中有汉明重量为l的码字。,推论1(p61,定理3.3.1):n,k,d线性分组码最小汉明距离等于d的充要条件是：H的任意d-1列线性无关 注：交换H矩阵的各列，不会影响码的最小距离，因此，所有列相同但排列位置不同的H所对应的分组码，在纠错能力和其他码参数上完全等价。,推论2：n,k,d线性分组码的最大可能的最小汉明距离为n-k+1 若系统码的最小距离d=n-k+1，则称此码为极大距离可分码，MDS码。,对偶码 设n,k,d线性分组码C的生成矩阵为G，校验矩阵为H，以H作为生成矩阵，G为对应的校验矩阵，可构造另一个n,n-k

19、,d线性分组码C1，我们称C1为C的对偶码。,缩短码,从n,k,d线性分组码的所有码字中，把前面i位全为零的码字,挑选出来构成一个新的子集，该子集即为n,k,d的缩短码。,参数 码长： n=2m-1 信息位长度：k=2m-1-m 最小汉明距离：d=3 校验矩阵有 m行，2m-1列，取互不相同的m重构成,汉 明 码,GF(2)上的7,4,3汉明码 001,010,011,100,101,110,111,000 校验矩阵为：,Examples,3.2 线性分组码的译码,伴随式 标准阵列译码 线性分组码的检错能力 线性分组码的纠错能力,设发送码字,接收序列,根据错误图样的概念，R=C+E,一、伴随式

20、(P59),令,伴随式S是校验矩阵H中某几列数据的线性组合，因而是n-k维向量，有2n-k种可能,错误图样E是n维向量，共有2n种可能，因而每2k种 错误图样对应一种伴随式。,一、伴随式(P59),Example,E2=(1100000),E3=(0010100),E1=(1000000),S1T=HE1T =(1110)T,S2T=HE2T =(1001)T,S3T=HE3T =(1001)T,7,3,4码的校验矩阵H为,基于伴随式的译码,伴随式 在一定程度上可以反应错误图样，但由于每2k种错误图样对应同一种伴随式，而真正的错误图样只有一种。,因而，译码器必须从2k个候选错误图样中，选择正确

21、的错误图样，才可以保证译码正确，否则会出现译码错误。,若是二进制对称信道(BSC)，译码器选择含非零元素最少的错误图样作为 最终的错误图样。,基于伴随式的译码,例：假设7,4线性分组码的校验矩阵为H，发送码字为v=(1001011)，接收序列为r=(1001001)。,根据接收序列r，计算伴随式为,基于伴随式的译码,因而有,又由于,基于伴随式的译码,解方程，得到16种错误图样,线性分组码的基本译码步骤 Step1: 由接收到的序列R，计算伴随式S=RHT； Step2: 若S=0，正确接收；若S不为零，寻找错误图样； Step3: 由错误图样解出码字C=R-E。,二、标准阵列译码(p63),标

22、准阵列译码基本原理,标准阵列的构成：根据许用码字将禁用码字进行分类， 分类的依据是错误图样。,n ， k ， d码的2k 个码字， 组成了n 维线性空间中的一个k 维子空间， 是n 维线性空间的一个子群。,以此子群为基础， 把整个n 维空间的2n 个元素划分陪集，其中， 2k 个码字放 在表中的第一行， 该子群的恒等元素C1(全为0码字)放在最左边，,在禁用码组中挑出一个n 重E2放在恒等元素C1的下面，并相应求出E2+C2， E2+C3， ， E2+C2k ， 分别放在对应 码字的下边构成第二行， 构成一个陪集。,再选一个未写入表中前一行的n 重E3， 用以上方法构成另一陪集成为第三行,标准

23、阵译码表,基于标准阵列的译码原理,标准阵列译码：收到的n 重R落在某一列中， 则译码器就译成相应于该列最上面的码字,问题：如何划分陪集使译码错误概率最小？即如何选择陪集首？,在pe0.5的BSC中， 产生1个错误的概率比产生2个的大， 产生2个错误的概率 比产生3个错误的概率的大 总之， 错误图样重量越小的产生的可能性越大。 因此， 译码器必须首先保证能正确纠正这种可能性出现最大的错误图样， 也就是重量最轻的错误图样。,在构造译码表时，挑选重量最轻的n 重为陪集首， 放在标准阵中的第一列， 以 全为0码字作为子群的陪集首。 这样得到的标准阵， 能得到最小的译码错误概率。,称为最小距离译码，在B

24、SC信道下，等价于最大似然译码。,例： 7， 4， 3汉明码的缩短码6， 3， 3码， 它的8个码组， 该码的标准阵表为,定义：n ， k ， d线性分组码的所有2n -k 个伴随式， 在译码过程中若都用来纠正所有小于等于t=(d-1)2个随机错误， 以及部分大于t的错误图样， 则这种译码方法称为完备译码。 否则， 称为非完备译码。 任一个n ， k ， d码， 能纠正t(d-1)2个随机错误。 如果在译码时仅纠正tt个错误， 而当错误个数大于t时， 译码器不进行纠错而仅指出发生了错误， 称这种译码方法为限定距离译码。,三、完备译码和限定距离译码,四、线性分组码的检错能力,若一个分组码的最小汉

25、明距离为dmin，该码可检测dmin -1个错误,分析：由于该码的最小汉明距离为dmin，即码中任意两个码字 之间至少dmin处不同，因此只含有dmin -1个错误的错误图样是无法 将一个码字转换为另一个码字的，伴随式不为零。,最小汉明距离为dmin的分组码可检测出所有至多含有dmin -1个 错误的错误图样。,问题：对于含有dmin或更多错误位置的错误图样，该分组码能否 检测出错误呢？,四、线性分组码的检错能力,最小汉明距离为dmin的分组码，可检测出大部分含dmin 或多于dmin 个错误的错误图样。事实上，一个(n,k)线性分组码可检测出2n-2k种长度为n的错误图样。,首先，对于n长的

26、码字，共有2n-1种非零错误图样，同时(n,k)线性分组码有2k-1种非零合法码字。,因此，存在2k-1种错误图样与 2k-1种非零码字相同。如果信道中出现这2k-1种错误图样，会将传输的码字v变成另一个码字w，接收端根据w计算出伴随式为零，认为传输无错，出现漏检。共存在2k-1种漏检错误图样。,如果错误图样与非零码字不同，接收到的向量就不是一个码字，对应的伴随式就不为零，错误被检出。所有2n-1种错误图样中，有2n-1-(2k-1) =2n-2k种错误图样与该码的码字不同，因此这2n-2k 种错误图样是可检测错误图样。,五、线性分组码的纠错能力,若一个分组码的最小汉明距离为dmin，且满足,

27、则该码可纠正所有含不超过t个错误的错误图样。,设v和r分别是传输码字和接收向量，w为C中任意其他码字，则有,由于v和w都是合法码字，因此有,五、线性分组码的纠错能力,如果错误图样中的错误不超过t个，则接收向量r与传输码字v之间 的汉明距离小于r与其他任何一个码字w之间的距离。,对于BSC信道，有,若,按照最大似然译码准则，r被译码为v，即实现了纠正t个错误。,具有纠正t个错误的分组码，通常可纠正很多含有t+1或更多错误的错误图样。 事实上，一个纠t个错误的(n,k)线性分组码，总共可纠正2n-k个错误图样。,3.3 由已知码构造新码的方法,扩展码 删余码 增广码(增信删余码) 增余删信码 延长

28、码,基本原理：对n,k,d线性分组码中的每一个码字，增加一个校验元 ，满足：,称为全校验元,若d为偶数， n,k,d码变成了n+1,k,d,若d为奇数， n,k,d码变成了n+1,k,d+1,一、扩展码,新码的校验矩阵为：,校验矩阵的第一行表示,Example: 7,4,3汉明码,其扩展码变为8,4,4，校验矩阵为,二、删余码,非常重要的概念,基本原理：在原码基础上删去一个校验元，得到n-1, k码。,最小汉明距离可能比原码小1，也可能不变,问题：新码的校验矩阵与原码有何关系？,Example: 8,4,4，校验矩阵为,其删余码变为7,4,3，校验矩阵为,结论：若删掉的校验位只参与了其中一个校

29、验方程，则在原码校验矩阵中 删掉上述校验位对应的行和列，即可得到新码的校验矩阵。,思考：原码中的每个校验位都参与了多组校验方程的运算，如何确定 删余码的校验矩阵？或者，如何利用原码的参数实现新码的译码？,基本原理：在原码基础上，增加一个信息元，删去一个校验元 n,k+1,d,基本实现方法：在原码生成矩阵G的基础上，再选择一个与G中各行都不相关的n维向量，得到新矩阵Ga，该矩阵有n列，k+1行，即得到一个n,k+1,d码,三、增广码,若原码中没有全1码，可在其G矩阵上增加一组全为1的行，得到增广码的生成矩阵为：,增广码是一个n, k+1,da的线性分组码，其最小汉明距离为,是原码中码字的最大重量

30、。,例 7， 3， 4码的生成矩阵为,对它进行增广变成为7， 4， 3汉明码， 它的生成矩阵为,四、增余删信码,删去一个信息元，增加一个校验元,若n,k,d码的最小汉明距离d为奇数，则挑选所有偶数重量的码字，即可构成n,k-1,d+1增余删信码,基本实现方法：删掉原码生成矩阵G中的一行，得到新矩阵G1，该矩阵有n列，k-1行，即得到一个n,k-1,d码,五、延长码,对增广码再填加一个全校验位。n+1,k+1,图 3 - 2 汉明码的各类修正码之间的关系图,3.4 Reed-Muller码,RM码的构造方法 RM码的译码算法 大数逻辑译码,Reed-Muller码是Muller于1954年提出的

31、构造方法，同年Reed用 大数逻辑译码方法解决了它的译码。,一般而言， r阶RM码RM(r， m)是2m， k ， 2m-r码，其中,一、RM码的构造,最小汉明距离,信息位长度,校验位长度,例如：m=5，r=2，则有n=2m=32,对于,一、RM码的构造,式中包括2m-i+1个全零和全1交替的2i-1维向量。当m=4时，可由以下四个向量,定义GF(2)上的2m维向量为,定义两个二进制向量a和b的布尔积为,一、RM码的构造,称向量积,为l次乘积,一般而言， r阶RM码RM(r， m)的生成矩阵的行向量集合为,中共有,个行向量，。将上述集合中的,向量按行排列，就构成RM码的生成矩阵。,现以m=3为

32、例说明RM码的生成， RM(r， 3)码从以下矢量中挑选构造G矩阵的行。,V0=(11111111) V3=(00001111) V2=(00110011) V1=(01010101) V3V2=(00000011) V3V1=(00000101) V2V1=(00010001) V3V2V1=(00000001),如果码以V0， V3， V2， V1作为G矩阵的行， 则得到一个RM(1， 3)码的生成矩阵为：,二、RM码的大数逻辑译码(示例),例1：已知RM(1， 3)码的生成矩阵为，设计该码的译码算法,二、RM码的大数逻辑译码(示例),展开，各编码比特与信息比特之间的关系为,如何利用上述信

33、息比特与编码比特 之间的关系完成译码？,二、RM码的大数逻辑译码(示例),假设接收端收到的接收向量为 ，根据接收向量，有,因此，判定 等于 中的多数的值。,大数逻辑译码,二、RM码的大数逻辑译码(示例),根据接收向量，有,因此，判定 等于 中的多数的值。,二、RM码的大数逻辑译码(示例),根据接收向量，还可得到,因此，判定 等于 中的多数的值。,二、RM码的大数逻辑译码(示例),检测出a3,a2和a1之后，根据接收向量完成下述操作,在没有差错的情况下，有,若 的分量中，取值为0个数大于取值为1的个数，则判定a0=0; 反之，若 的分量中取1的个数大于取0的个数，则判定a0=1； 若相等，则判定

34、a0出错。,二、RM码的大数逻辑译码(示例),例2：已知RM(2， 4)码的生成矩阵由下面11个向量构成,假设,为待编码消息，,根据上述生成矩阵，得到相应的码字为,二、RM码的大数逻辑译码(示例),在生成矩阵的所有行中，除 ，其他每行生成向量的前四个分量之和均为零，同时其他三组四个分量之和也有同样结论，所以有如下校验和,假设接收端收到的接收向量为 ，根据接收向量，有,因此，判定 等于 中的多数的值。,大数逻辑译码,如何确定合适的校验和？,第一步,二、RM码的大数逻辑译码(示例),在没有差错的情况下，,第二步,由于分量 中，从第0个分量开始，每连续两个的分量之和为0,因此a1满足以下校验和,二、

35、RM码的大数逻辑译码(示例),根据上述校验和，按照大数准则完成对a1的译码。,第二步,若8个校验值中0的个数大于1的个数，判,若8个校验值中1的个数大于0的个数，判,如何确定上述三个比特的校验和方程？,二、RM码的大数逻辑译码(示例),检测出a4，a3,a2和a1之后，进行下述 操作,在没有差错的情况下，有,若 的分量中，取值为0个数大于取值为1的个数，则判定a0=0; 反之，若 的分量中取1的个数大于取0的个数，则判定a0=1； 若相等，则判定a0出错。,第三步,下面给出RM码的通用译码算法。,三、RM码的大数逻辑译码(通用算法),考虑r阶RM码RM(r,m)，设待编码消息为,编码的码字为,

36、三、RM码的大数逻辑译码(通用算法),第一步，对次数为r的向量积 所对应的信息比特 进行译码,译码规则是根据接收向量构造多个校验和，然后按照大数准则进行判断，并 根据这些译码信息比特，修改接收向量。,第二步，根据修改后的向量，对次数为r-1的向量积 所对应的信息比特 进行译码。,译码规则是根据接收向量构造多个校验和，然后按照大数准则进行判断，并 根据这些译码信息比特，修改接收向量。,按照上述方法逐步进行，直到完成对最后一个信息比特a0的译码。,这种方法称为r+1步大数逻辑译码算法。,四、校验和的确定算法,对于 ， ，构造下列指标集合S,令集合E为在集合 中不包含 的整数集合。,集合S中含有2r

37、-l个小于2m的非负整数。,构造以下整数集合,四、校验和的确定算法,利用前述三个集合构造校验和的方法如下,假设刚好完成第l步译码，译出的信息比特为 ，修改后的接收向量为,式中 是第l步一码中所用到的修改后的接收向量,对于任意整数 ，构造下面的整数集合,用于译码信息比特 的校验和为,四、校验和的确定算法,例2：已知RM(2， 4)码的生成矩阵由下面11个向量构成,假设,为消息比特，求它们的校验和。,四、校验和的确定算法,计算a12的校验和,用于构造a12的校验和的集合为,四、校验和的确定算法,用于构造a12的校验和的集合为,所以，a12的校验和方程为,四、校验和的确定算法,计算a13的校验和,用

38、于构造a12的校验和的集合为,四、校验和的确定算法,用于构造a13的校验和的集合为,所以，a13的校验和方程为,采用相同的方法，可以构造 的校验和。,完成第一步译码后，修改接收向量为,根据上述修改后的接收向量，完成第二步译码。,四、校验和的确定算法,计算a3的校验和,用于构造a3的校验和的集合为,四、校验和的确定算法,所以，a3的校验和方程为,采用相同的方法，可以构造 的校验和。,完成第二步译码后，修改接收向量为,根据上述修改后的接收向量，完成a0的译码。,用于构造a3的校验和的集合为,五、RM码的其他构造方法,方法一、直积(Kronecker)构造法,的直积记为 ，是将矩阵A中的每个元素ai

39、j用矩阵aij B代替得到,令GF(2)上的二阶矩阵为,的二次直积定义为,五、RM码的其他构造方法,的三次直积定义为,五、RM码的其他构造方法,码长为n=2m的r阶RM码RM(r,m)，其生成矩阵由 中重量大于等于2m-r的行向量构成,由,码长为8的1阶RM码RM(1,3)，其生成矩阵由 重量大于等于23-1=4的 行向量构成。,五、RM码的其他构造方法,得到其生成矩阵为,五、RM码的其他构造方法,二、 构造法,令Ci是生成矩阵为最小汉明距离为Gi和di的二进制(n,ki)线性码，i=1,2,假设d2d1可构造如下码长为2n的线性码,C为一个(2n,k1+k2)的线性码，其生成矩阵为,该码的最

40、小汉明距离为,设u和v为GF(2)上的两个n维向量，可构造如下向量,五、RM码的其他构造方法,二、 构造法,事实上，可以按照上述方法递归构造更长码长的RM码。,对于 ，r阶RM码的另一构造法为,五、RM码的其他构造方法,递归方法,大作业一,试编写程序,仿真RM(1,3)和RM(2,4)在高斯信道下的译码性能，并 与单独BPSK调制在高斯信道的性能进行比较，分析上述两个码带 来的编码增益为多少？,要求: (1)RM采用大数逻辑译码算法； (2)调制方式为BPSK调制； (3) 画出误比特性能随信噪比变化的曲线（0-9dB）； (4)编程工具：C或Matlab。,注意：编码码率与信噪比之间的关系。

41、,产生信息序列,编码,通过信道,译码,与信息序列比较，判断是否有错,计算误比特率,中止,Yes,Gaussian Noise Program(1),long Seed = 17; double UniformRand() double uRand; / generate a uniformly distributed random number Seed = (Seed * 1029 + 221591L) % 1048576L; / make 0.0 = uRand = 1.0 uRand = (double)Seed / 1048576.0; return uRand; ,Gaussian Noise Program(2),double GaussNoise(double sigma) / sigma - standard deviation of Gaussian noise int num; / total n