精华内容
下载资源
问答
  • 线性分组码实验是《信息论》课程中一种常见的有扰信道编码。
  • 二进制数据在基带中传输的时候,通常为了能够加大信息传输的准确度,我们都会进行编码和译码,在这个实验中我们采用(5,2)线性分组码来进行编码和译码。 一个[n,k]线性分组码,是把信息划成k个码元为一段(称为...

    二进制数据在基带中传输的时候,通常为了能够加大信息传输的准确度,我们都会进行编码和译码,在这个实验中我们采用(5,2)线性分组码来进行编码和译码。

    一个[n,k]线性分组码,是把信息划成k个码元为一段(称为信息组),通过编码器变成长度为n个码元的一组,作为[n,k]线性分组码的一个码字。若每位码元的取值有q种(q为素数幂,q进制),则共有q的k次方个码字

    这个编码过程我们采用生成矩阵来实现:

    1.首先确定生成矩阵

    G=[1,0,1,1,1;

       0,1,1,0,1];%生成矩阵

    2.由C=m*G获得(n列)码字矩阵

    R=mod(m*G2;

     

              接下来是解码过程:信息论书上讲到,线性分组码的解码过程是通过接收矩阵(k,n)和校验矩阵(n,(n-k))的转置相乘,得到的伴随式S是否为0矩阵来判断是否由差错。这里我们要明白,因为校验矩阵本身就是码字矩阵的对偶空间生成的矩阵,因此如果为正确的码字,两者相乘必定为0矩阵。若是差错,则R=E+C(因为是2进制编码,故为两者码字相加),此时R*H'=E*H'。

    即译码过程为:

      1.首先通过生成矩阵确定校验矩阵

    H=[1,1,1,0,0;
    
       1,0,0,1,0;
    
       1,1,0,0,1];%校验矩阵

      2.由S=R*H'是否为0矩阵来判断是否存在差错

    S=mod(R*H',2);

    3.第三步即是通过已经发生的差错来纠正码字,这里有两种思路:

    ①通过接收到的矩阵R映射到标准译码阵列表,即书上对应的阵列表(这个部分推荐进行计算,便于进一步了解纠正错误码字的原理),第一行即为正确码字。

    ②通过S来确定差错图样,即若S=[001],则E=[00001],由C=E+R可以唯一确定原来的码字,进行纠错。

    本实验中我们采用第②种,具体实现为:

    S=4.*S(:,1)+2.*S(:,2)+S(:,3);  (1)
    
    row=find(S~=0);
    
    [a,b]=size(row);
    
    for i=1:a
    
        switch(S(row(i)))
    
            case{1}
    
                R(row(i),:)=mod(R(row(i),:)+[0,0,0,0,1],2);
    
            case{2}
    
                R(row(i),:)=mod(R(row(i),:)+[0,0,0,1,0],2);
    
            case{3}
    
                R(row(i),:)=mod(R(row(i),:)+[0,0,0,1,1],2);
    
            case{4}
    
                R(row(i),:)=mod(R(row(i),:)+[0,0,1,0,0],2);
    
            case{5}
    
                R(row(i),:)=mod(R(row(i),:)+[0,1,0,0,0],2);
    
            case{6}
    
                R(row(i),:)=mod(R(row(i),:)+[0,0,1,1,0],2);
    
            case{7}
    
                R(row(i),:)=mod(R(row(i),:)+[1,0,0,0,0],2);
    
        end
    
    end
    
    C=R;

    这里我们在式(1)中采用了将二进制码字转化为10进制的方式,通过这样,能够使用find函数唯一确定S矩阵是否出现了差错以及出现差错的位置,而不用for循环一步一步地去对比矩阵,利用了matlab的矩阵计算特性,大大简化了运算数。

    展开全文
  • 线性分组码

    千次阅读 多人点赞 2018-11-25 14:53:00
    线性分组码(我们以汉明码为例): 一些概念 信息码 就是实际上要传输的数据的有效部分。 监督码 用来监督传输的数据是否出错的部分。 校正子(syndrome,又称校验子,伴随式) 可以用来判断传输...

    线性分组码(我们以汉明码为例):       

    1. 一些概念
      1. 信息码
        1. 就是实际上要传输的数据的有效部分。
      2. 监督码
        1. 用来监督传输的数据是否出错的部分。
      3. 校正子(syndrome,又称校验子,伴随式)
        1. 可以用来判断传输的数据在哪一位发生错误。
    2. 以上概念不理解没关系,下面会举例子的。
    3. 我们来构建一个场景:
      1. 最原始的时候,我们要传输数据,比如我们想传输字符“h”,实际上我们传递的是字符h对应的二进制码(这就是信息码)。
      2. 一般情况下,我们都可以正常传输,可是呢突然有一天我们发现因为线路老化,我们本来传递的是h,结果接收端出现了字符a。虽然只是很少数的情况,但是一旦发生传输错误,就会对我们的项目造成巨大的损失。
      3. 于是我们想,能不能找一种方法,判断我们接收到的字符是否出现错误(这样一旦当我们发现接收信息出现错误的时候,我们就可以发出指令,要求发送数据端重新发送数据。
      4. 于是我们就想办法利用信息码,再在信息码的基础上添加一些冗余码(这些冗余码实际上就是监督码)的方式,按照一定的构造规则,构造了一个可以指明,接收的字符是否出错?以及如果出错,究竟是传输的这个字符的哪一位发生了错误?这样的一个序列。(就是我们说的校正子:用{Si}表示,“{}“代表他是一组数)
      5. 举例如下:
        1. 我们的信息码为a6,a5,a4,a3
        2. 我们添加的冗余码为a2,a1,a0
        3. 构造规则:
          1. 当然,构造方法有很多种,你可以自己选择自己的构造规则,上述描述的这套构造规则,是对应汉明码的
          2. 那么我们就可以找到,我们传输的数据错误的位置和校验子Si的关系。(这个关系是按照我们构造规则计算出来的,有了这个表格之后,我们只需要查表就可以知道,究竟是数据传输中哪一位发生错误了,而不需要再按照构造规则进行计算了。但一定要注意,这个表格只限于这个规则,即这个表格只限于汉明码。)
        4. 这样我们就有了一个确定传输过程是否发生错误的机制了。下面我们需要做的是,求出来我们在信息码(a6,a5,a4,a3)基础上,增添的冗余码(a2,a1,a0)。
        5. 由对应表我们看到,当校正子向量全零时,代表传输没有发生错误。那么,将这个关系,写成表达式的形式就是:
          1. 由上述方程组我们可以解出我们的冗余码。(就是监督位,下面我们将使用监督位。)
          2. 我们可以计算出监督位(汉明码):
        6. 最后将信息码与监督码按照顺序进行排列,我们就得到了完整的汉明码。
    4. 上面我们感受了一个完整的发展过程,汉明码是线性分组码的特例而已,我们再来讨论一下线性分组码。
      1. n = k + r  (单位:位)
        1. n:码长
        2. k:信息码长
        3. r:监督码长
      2. 构成线性分组码的条件(这两个式子的解释见4.c.vi)
        1. 2 ^ r – 1 >= n
        2. 或者:2 ^ r >= k + r + 1
      3. 所谓线性码,是指信息位和监督位满足一组线性代数方程的码。我们已知
        1.  使用 + 代替 异或 操作,可以的到如下线性方程
        2. 使用矩阵乘法,可将上式化为
          1. H矩阵可以分为上述两部分
          2. P为r x k阶矩阵
          3. Ir 为 r x r阶单位方阵
        3. 可记为:
          1. 其中H^T是H的转置,我们称H为监督矩阵(parity –check matrix)
          2. 只要H矩阵给定,编码时的监督码和信息码的关系就完全确定了。
          3. H的行数,等于监督码r的个数。
          4. H中每行的“1“的位置表示相应的码元之间存在监督关系。
            1. 实际上我们可以将监督关系,看作是偶校验。例如a6 a5 a4 a2,实际上a2就是为了使用偶校验,而计算出的值。也就是说,我们之前所说的S1 S2 S3,实质上都是偶校验,只是用于校验的校验位分别是a0 a1 a2而已。
            2. 这样也可以从侧面来说明监督码的个数,当监督码的个数是2个的时候,我们只能判断一个序列是否有错误。但是当监督码的个数增加时,我们就不仅能判断该序列是否发生错误,还能判断具体是哪一位发生错误。我们举例说明(汉明码本身已经是一个很好的例子了):
              1. 假设r=1,则2^2 – 1 =3也就是说,当序列的长度小于等于两位时,可以判断是哪一位出错。我们假设序列构成是 1bit信息码+2bit(偶)校验码 ,我们则我们可以构造一个规则,使得我们使用这个规则求得的校验子Si,可以指明具体是哪一位发生了错误。
              2. 我们画图来分析
              3. 分析过程如下(只考虑是一位出错,两位同时出错的概率很低。)
                1. 如果我们接收的序列中发现 ac出错而cb没出错,我们可以简单看为是a位出错
                2. 如果cb出错而ac没出错,我们可以简单看为是c位出错
                3. 如果两个都出错,我们看为c出错
              4. 上述内容可以简单解释2 ^ r – 1 >= n这个式子。
          5. 例如第一行1110100表示监督位a2是由a6 a5 a4之和决定的。
          6. H矩阵各行是线性无关的。
      4. 同样的,我们来化简监督码的关系式
        1. 可改写为下述式子
          1. 其中Q为一个k x r 阶矩阵
          2. Q = P的转置
          3. 当信息码给定后,用信息码序列乘上矩阵Q就可以得到监督码序列。
        2. 我们将Q的左边加上一个k x k 阶单位矩阵,就构成了生成矩阵G
          1. 由生成矩阵可以产生整个码组,即:
          2. 如果找到了码的生成矩阵G,则编码方式就完全确定了。
          3. 具有[Ik | Q]形式的生成矩阵称为典型生成矩阵。
          4. 由典型生成矩阵得出的码组,信息码的位置不变,监督码附加于其后,这种形式的码称为系统码。
    展开全文
  • 另外还有一种题型: 已知某线性分组码的码长为 101010,如果要想该线性码能够纠正两位随机错误,问需要多少位的监督位? 首先,我们明确这样一个性质:监督位如果有 xxx 位,那么其伴随式就会有: 2x2^{x}2x种。...

    在开始本文之前,我们先给出下面的几个名词,他们将会在后续的分析中反复出现:
    【1】生成矩阵 【2】监督矩阵 【3】许用码字 【4】最小汉明距离 【5】伴随式 【6】错误图样

    我们先重点看看接收端中,上面这些名词的关联:
    在这里插入图片描述
    首先,当我们接收到码字 y 时,我们可以通过监督矩阵计算出伴随式 S,通过伴随式,我们又可以得到错误图样,错误图样的意义就是它能够指出接收码字中哪一位出错了。从而去修改对应位置的码字。【监督矩阵的监督作用可以通过 : H ⋅ C T = 0 H\sdot C^T=0 HCT=0表现出来

    下面我们具体看看如何通过监督矩阵得到所有的伴随式,也就是过程 a:

    1. 假设我们现在计算得到了监督矩阵H: H = [ 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 ] H = \begin{bmatrix} 1 & 1&0&1&0&0&0\\ 0&1&1&0&1&0&0\\ 1&1&1&0&0&1&0\\ 1&0&1&0&0&0&1 \end{bmatrix} H=1011111001111000010000100001
      那么伴随式S就是H 矩阵各列的组合(异或运算)。比如说,我们现在选择H的第1,2列进行异或,就会得到其中一个伴随式: S = [ 0 1 0 1 ] S = \begin{bmatrix} 0&1&0&1\end{bmatrix} S=[0101];再比如说我们如果只选择H的第6列进行异或,也可以得到另一个伴随式: S = [ 0 0 1 0 ] S = \begin{bmatrix} 0&0&1&0\end{bmatrix} S=[0010]

    下面我们具体看看如何通过伴随式求出错误图样,以及如果通过错误图样反推伴随式:

    1. 如何通过伴随式求出错误图样?结果可能是不唯一的。由于我们刚刚不是选取了H的第1,2列异或得到了一个伴随式: S = [ 0 1 0 1 ] S = \begin{bmatrix} 0&1&0&1\end{bmatrix} S=[0101]吗,所以上图的 b 过程就是说你伴随式S是选取了H的哪些列计算得到了,那么错误图样 e 就是在对应的位置标记为“1”,否则标记为“0”。所以,这个伴随式对应的错误图样就是 [ 1 1 0 0 0 0 0 ] \begin{bmatrix} 1&1&0&0&0&0&0\end{bmatrix} [1100000],但是还有一种可能性: S = [ 0 1 0 1 ] S = \begin{bmatrix} 0&1&0&1\end{bmatrix} S=[0101]也可以是H矩阵的第5,7两列的组合。因此,错误图样还可能是: [ 0 0 0 0 1 0 1 ] \begin{bmatrix} 0&0&0&0&1&0&1\end{bmatrix} [0000101]

    2. 而反过来通过错误图样找S,结果就是唯一的了。比如说错误图样: [ 1 1 0 0 0 0 0 ] \begin{bmatrix} 1&1&0&0&0&0&0\end{bmatrix} [1100000],那么对应的伴随矩阵就只能是 S = [ 0 1 0 1 ] S = \begin{bmatrix} 0&1&0&1\end{bmatrix} S=[0101]

    而可纠正的错误图样,指的就是错误最少的那种情况。


    说了那么多,那么生成矩阵和监督矩阵到底怎么求呢?我们记住下面的关系: Q = [ I ∣ P ] Q = \begin{bmatrix} I|P\end{bmatrix} Q=[IP]
    H = [ P T ∣ I ] H = \begin{bmatrix} P^T|I\end{bmatrix} H=[PTI]

    上述都是系统的生成矩阵和监督矩阵,如果题目给出来的矩阵不是系统的(也就是没有单位矩阵的),那么大部分情况可以通过行的互换得出。


    求出了监督矩阵,我们就来看看最小汉明距离 d m i n d_{min} dmin 如何计算。其实 d m i n d_{min} dmin 就是看H矩阵中最少有多少列是线性相关的。还是以刚刚的H为例:
    H = [ 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 ] H = \begin{bmatrix} 1 & 1&0&1&0&0&0\\ 0&1&1&0&1&0&0\\ 1&1&1&0&0&1&0\\ 1&0&1&0&0&0&1 \end{bmatrix} H=1011111001111000010000100001

    我们发现,任意的3列都无法表示成线性关系,但是其中第5,6,7列的和恰好等于第3列,也就是说最少4列是可以表示成线性相关的,所以 d m i n = 4 d_{min} = 4 dmin=4


    我们再来看看许用码字的求法:

    我们通过 (n, k) 码的形式【即:n位的码字里面有k个信息位】那么我们就把k个信息位的所有组合都列出来,然后分别跟生成矩阵相乘,就可以得到许用码字 C C C了。

    其中,我们也可以通过生成矩阵的维度确定 n, k:生成矩阵的维度:(k, n).


    另外还有一种题型:

    已知某线性分组码的码长为 10 10 10,如果要想该线性码能够纠正两位随机错误,问需要多少位的监督位?

    首先,我们明确这样一个性质:监督位如果有 x x x 位,那么其伴随式就会有: 2 x 2^{x} 2x种。下面我们回到题目:题目说想要线性码能够纠正两位随机错误,这个随机错误其实就是通过错误图样来反应的。比如一个 ( 7 , 4 ) (7,4) (7,4) 码,如果错误图样是 [ 0001000 ] [0 0 0 1 0 0 0] [0001000],那么就可以判断是第四位出错了。

    接下来我们看一下如果是出现两位错误的时候,错误图样有多少种情况:根据排列组合的知识,从10位里面选出2位作为错误位,那么有: C 10 2 = 45 C_{10}^{2} = 45 C102=45种情况。然后只错一位的情况一共有: C 10 1 = 10 C_{10}^1=10 C101=10种。因此,错两位及以下的错误图样一共有: 45 + 10 = 55 45+10=55 45+10=55种情况。那么因此,我们所选取的监督位就应该使得线性码所产生的错误图样数比55大。由于 2 6 = 64 > 55 > 2 5 = 32 2^6=64>55>2^5=32 26=64>55>25=32,因此,监督位的个数应该是6.

    展开全文
  • 1. 线性分组码的最优软决策解码  假设[n,k,d]线性块代码C是二进制的  通道编码器将k信息位m0映射到一个码字C =(cn - 1,··,C0)  传输的波形s(t)是  s(t)的矢量表示  对于编码信号,接收机

    1. 线性分组码的最优软决策解码

                         假设[n,k,d]线性块代码C是二进制的

                        通道编码器将k信息位m0映射到一个码字C =(cn - 1,··,C0)

                    传输的波形s(t)是

                   s(t)的矢量表示

                   对于编码信号,接收机是最优的

    2  假定传输的信息是相等的。

         最优决策规则是最小距离决策规则。
         让si为对应于码字的编码信号波形si(t)的向量表示

    块的错误概率


    在软决策中,我们需要计算M距离度量。
    当M较大时,计算复杂度非常高。
    为了减少计算量,我们可以对模拟信号进行量化,对解码进行数字化处理。
















    展开全文
  • 本文档是信息论与编码课程设计题目之一,设计项目为线性分组码(6,3)。分享我们的成果,给你参考的价值,感谢你的下载!
  • 线性分组码的MATLAB实现一、线性分组码原理介绍二级目录三级目录二、线性分组码编码实例三、代码展示及运行结果四、程序自评价 一、线性分组码原理介绍 二级目录 三级目录 二、线性分组码编码实例 三、代码展示及...
  • 线性分组码实验报告(共10篇)线性分组码实验报告(共10篇) 实验二、线性分组码的编译码报告信息论与编码实验报告1、 简要总结线性分组码编译码的基本原理及步骤;分组码是一组固定长度的码组,可表示为(n , k),通常它...
  • 重庆交通大学信息科学与工程学院 综合性设计性实验报告 专 业 通信工程专业 12 级 学 ...签名 年 月 日 实验成绩 线性分组码 matlab 实现 一实验目的和要求 信道编码的目的是为了改善通信系统 传输质量按照监督码元 与
  • 纠错码专题——线性分组码(1)

    千次阅读 多人点赞 2020-04-12 02:23:53
    线性分组码包括一大类的纠错编码在内,有汉明码、循环码、LDPC码等等,之前了解这些编码也是在网上搜搜资料,看看博客这样去学习,在网上搜索资料的时候发现一个问题,例如在看很多人写的汉明码博客时,很多人都一味...
  • 编码原理个人笔记资料,参考中国地质大学在中国大学MOOC上的《信息论与编码》的网课整理
  • 实验二 线性分组码

    2011-05-29 10:46:09
    课程项目实验要求: 1、写出汉明编码基本步骤,画出程序流程图; 2、画出汉明编码输出波形图; 3、汉明码模块发端加错信号...4、汉明码模块发端错检测能力观测和错纠错性能的测量; 5、分析整理实验测试的数据;
  • 吉林建筑大学 电气与电子信息工程学院 信息理论与编码课程设计报告 设计题目 线性分组码编码的分析与实现 专业班级 电子信息工程 学生姓名 学 号 指导教师 设计时间 2014.11.24 2014.12.5 教师评语 成绩 评阅教师 ...
  • 提出一种改进的矩阵化简方法,该方法将截获到的数据横向放入分析矩阵,对化简后的矩阵求各列列重的比率,对所有列重比率求信息差熵,从而实现线性分组码码长的识别。仿真实验表明,该方法计算复杂度低,识别速度快,...
  • 线性分组码的标准阵的matlab程序

    千次阅读 2013-05-10 22:55:38
    信息论作业里有求线性分组码的标准阵的题目。手算太过繁琐,而且容易出错。在matlab里没有找到现成的函数,于是自己写了一个。 构造标准阵的步骤如下: 1.将2^k个码字排成一行,全零码字排在第一列。其余的(2^n-...
  • 文中基于信息论方法,提出了一种在汉明重模型下评估分组密码抗ASCA安全性的方法,并给出了一种抗基于汉明重模型ASCA分析的安全性指标,称为汉明重扩散度(HWE),以度量分组密码的非线性部件及轮函数对抗ASCA分析的能力....
  • 针对嵌入了FPGA密码芯片的设备在运行算法时泄露的侧信道信息进行了研究,提出一种改进分组密码S盒的组合侧信道攻击方案,该方案由差分功耗攻击、模板攻击和毛刺攻击构成。通过传统的差分功耗攻击确定S盒运行的时间...
  • 我写的一个信息论期末...作业要求输入码字,生成线性分组码,错误图样,汉明距离,并进行最短距离译码,伴随式译码,标准阵列译码。 信息源默认为15位,默认正确的码字为全零码 程序只能纠2个错,全零码包括在生成阵内
  • 利用向量值函数的输出向量对分组密码的输出密文进行控选,以直接输出非线性密钥流,并分析模型的平衡性与完全性,证明该模型的密钥流生成器具备平衡性,且其生成密钥流与控制向量统计独立。给出线性移位寄存器状态...
  • 本课件讲述了信息论的基本理论,并给出了实现编码的算法和程序,包含信源编码:哈夫曼编码,预测编码,变换编码,游程编码程序;信道编码:循环编码,线性分组码,卷积码等经典的实现程序。
  • 信息论编码与密码学

    2013-03-07 23:11:59
    信息论编码与密码学: 信源编码 信道容量和编码 线性分组码 循环码 卷积码 香农三大定理
  • 信息论引论 二 信息论和熵 三 信源编码 四 信道及其容量 五 信道编码定理 六 线性分组码 七 总结
  • 信息量和熵 信源编码 信道及其容量 信道编码 线性分组码 还有部分习题
  • 有关信息论基础ppt

    2010-07-16 09:51:34
    一. 信息论 信息论的发展以及通信系统的模型 离散信源熵,互信息以及冗余度 二....定长编码,变长编码以及最佳编码 离散信源的信息率失真函数R(D) ...线性分组码 卷积码 网格编码调制与级联码 Turbo码及其迭代译码原理
  • 分组密码算法分析

    千次阅读 2011-02-23 13:44:00
    它是今年10月份美国国家标准和技术研究所刚刚推出的分组密码算法,目前美国官方还没有正式发布此标准,但基本上已有定夺。 前言 数据加密作为一项基本技术是所有通信安全的基石。数据加密过程是由形形色色...
  • 多用户信息论(ppt) ,介绍(ppt),离散无记忆源无失真编码(ppt),率失真函数(ppt),线性分组码(ppt),信道编码定理(ppt),信道容量(ppt),信息量和熵(ppt),信息与编码理论(第1节-第23节)
  • 信息论基础笔记

    2020-08-10 18:11:06
    参考Thomas M.Cover及 Joy A. Thomas的Elements of Information Theory做了学习笔记。 一、 信息论的基本度量 ...3. 信道编码:提高通信的可靠性,线性分组码(汉明码),纠错编码  自信息(描述事件不确
  • 分组密码算法分析,改进

    千次阅读 2012-09-22 18:28:43
    序:这是我花了近2周的时间写的,可以说比较全面地介绍了各种分组密码、如DES算法、IDEA算法,其中最为宝贵的一部分是最后AES新推荐的算法Rijndael,它是今年10月份美国国家标准和技术研究所刚刚推出

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,941
精华内容 776
关键字:

信息论线性分组码