精华内容
下载资源
问答
  • 常用编码的介绍
  • Matlab仿真程序实现LDPC低密度奇偶校验码
  • 奇偶校验码

    千次阅读 2021-03-20 16:39:32
    理解「奇偶校验码」前,最好要知道一个词的概念「码距」 码距:两个合法码字对应二进制位上数字不同的个数 例子: 00 和 01 的码距为1,因为只有一个位上的数不同 00 和 11 的码距为2,因为两个位上的数都不同 ...

    理解「奇偶校验码」前,最好要知道一个词的概念「码距」

    码距:两个合法码字对应二进制位上数字不同的个数

    例子:
    00 和 01 的码距为1,因为只有一个位上的数不同
    00 和 11 的码距为2,因为两个位上的数都不同

    什么是奇偶校验码

    奇偶校验码就是用来检测数据传输过程中是否发生错误的一种检验方式,是检验码中最简单的一种

    本质

    奇校验

    信息位 + 校验位里面 1 的个数的总和为奇数个

    偶校验

    信息位 + 校验位里面 1 的个数的总和为偶数个

    信息位:就是其原来二进数数的位的个数
    校验位:由信息位进行奇校验或者偶校验后,得出来的二进制数(0 或者 1)

    定义

    设有 n 位信息位Xn, Xn-1,…,X2,X1,校验位为P,算出校验位 P 的值

    奇校验:P = Xn⊕ Xn-1⊕…⊕X2⊕X1⊕ 1

    偶校验:P = Xn⊕ Xn-1⊕…⊕X2⊕X1

    ⊕:异或(表示要进行异或操作)

    异或是怎么样的呢?

    二进制位上的数,相同为0,不同为1
    1 1 0 0 1 1
    0 1 0 1 0 1
    1 0 0 1 1 0 异或后的结果

    计算

    例子:设有 8 位二进制数为 11011010,求其校验位

     奇校验: 1⊕1⊕0⊕1⊕1⊕0⊕1⊕0 ⊕ 1 = 0
     偶校验: 1⊕1⊕0⊕1⊕1⊕0⊕1⊕0 = 1
    

    计算过程:每次得出的结果,都与下一位的二进制数异或

    奇校验过程:
    1 ⊕ 1 = 0
    0 ⊕ 0 = 0
    0 ⊕ 1 = 1
    1 ⊕ 1 = 0
    0 ⊕ 0 = 0
    0 ⊕ 1 = 1
    1 ⊕ 0 = 1
    1 ⊕ 1 = 0

    偶校验也是一样的,自己推算一下

    上面的都是书上的例子,正经人谁这么算啊???


    所以奇校验和偶校验可以这么算

    同样是上面的例子

    奇校验:计算二进位数里面 1 的个数,如果 1 的个数是奇数,那么校验位为 0 ,如果 1 的个数为偶数,那么校验位为 1

    偶校验:计算二进制数里面 1 的个数,如果 1 的个数是奇数,那么校验位 为 1,如果 1 的个数为偶数,那么校验位为 0

    其实就是加一个二进制校验位,把 1 的个数凑成奇数偶数即可

    错误检测

    校验方程,这个自己去查一下

    考试做题推崇的做法:
    1)判断传输过来的数据用的是哪种校验
    2)判断传输的数据是否满足奇校验或者偶校验的个数

    注意:奇偶校验码能判断出是否有错误,但又不是很准确


    例子:

    原始信息位:1101100,使用奇校验传输,奇校验后的数为:11101100

    传输后出现的情况:

    1)错 1 位: 11001100,检查 1 的个数,发现 1 的个数为偶数,则在传输过程中,数据发生了错误,但是并不能知道错了几个,错在哪

    2)错 2 位:11001000,检查 1 的个数,发现 1 的个数为奇数,但实际上,在传输的过程中,数据发生了改变,但是检测不出来

    3)错 3 位:10001000,检查 1 的个数,发现 1 的个数为偶数,则在传输过程中,数据发生了错误,但是并不能知道错了几个,错在哪

    展开全文
  • 常用校验码(奇偶校验码、海明校验码、CRC校验码) 一、奇偶校验码二、海明校验码三、CRC校验码   计算机系统运行时,各个部之间要进行数据交换.交换的过程中,会有发生误码的可能(即0变成1或1变成0),由于...

    转载自:https://www.cnblogs.com/VersionP1/p/7779251.html ,作者: FunnyOne 

     

    常用校验码(奇偶校验码、海明校验码、CRC校验码)

    一、奇偶校验码
    二、海明校验码
    三、CRC校验码

      计算机系统运行时,各个部之间要进行数据交换.交换的过程中,会有发生误码的可能(即0变成1或1变成0),由于计算机的储存是通过二进制代码来实现的的,误码会导致储存的内容发生改变。为确保数据在传送过程正确无误,常使用检验码. 我们常使用的检验码有三种. 分别是奇偶校验码海明校验码循环冗余校验码(CRC) 。

     

    一、奇偶校验码

     

    学习资料:常用校验码

    概念:

      奇偶校验码是奇校验码偶校验码的统称. 它们都是通过在要校验的编码上加一位校验位组成.

    校验方法:

      如果是奇校验加上校验位后,编码中1的个数为奇数个。如果是偶校验加上校验位后,编码中1的个数为偶数个

    分类:

    1. 水平奇偶校验码:对每一个数据的编码添加校验位,使信息位与校验位处于同一行

    例子:

    原编码奇校验偶校验
    00000000 10000 0
    00100010 00010 1
    11001100 11100 0
    10101010 11010 0

    当原编码在传输、储存的过程中发生了误码,1的数量就会改变,然后就能校验出该过程出现了错误。

    1. 垂直奇偶校验码:把数据分成若干组,一组数据排成一行,再加一行校验码. 针对每一行列采用奇校验 或 偶校验

    缺点:

    1. 只能检测出奇数位出错. 如果发生偶数位错误就无法检测

      设原编码为0000,传输的过程中变成了1001。如果使用奇校验,原编码是00001,传输过后会变成10011,1仍然是奇数个,无法校验;如果使用偶校验,原编码是00000,传输过后会变成10010,1仍然是偶数个,同样无法校验。

    1. 奇偶校验码无法检测出哪位出错.所以属于无法矫正错误的校验码。

      校验过程中只知道1的数量发生变化,对于哪个地方发生变化无从知道。

    二、海明校验码

    学习资料:海明校验码

    实现原理:

      它的实现原理,是在m个数据位之外加上k个校验位,从而形成一个m+k位的新的码字,使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中,当某一位出错后,就会引起相关的几个校验位的值发生变化,这不但可以发现出错,还能指出是哪一位出错,为进一步自动纠错提供了依据。

    两个码组对应位上数字的不同位的个数称为码组的距离,简称码距

    例:

    这两个二进制码中,有三个不相同的位置,所以码距为3.

    须知:

    1. 海明校验码是放在2的幂次位上的,即“1,2,4,8,16,32······”;
    2. 信息位为m的原始数据,需要加入k位的校验码,它满足m+k+1<2^k;

    例子:

    要计算原始信息位为101101100的海明校验码。

    先用m+k+1<2^k计算出校验位:9+k+1 <2^k→k=4,即校验位为4位。

    因为海明校验码是放在2的幂次位上,所以插在位置1,2,4,8中

    用到的校验码是看 当前位置由哪几个 校验码所在的位置的和

    • 例如

    校验码的位置是1,2,4,8。位置3= 1 + 2,所以位置3用到的校验码是1和2;位置7 = 1 + 2 + 4组成的,所以位置7用到的校验码是1,2和4。

    然后将校验码校验的位置记录下来:

    • 校验码1(位置1):3,5,7,9,11,13
    • 校验码2(位置2):3,6,7,10,11
    • 校验码3(位置4):5,6,7,12,13
    • 校验码4(位置8):9,10,11,12,13

    注意:后面的数字串是位置的下标,不是值,值还是0或1。

    然后做异或运算(相同时为0,不同时为1)

    • 校验码1(位置1):1 xor 0 xor 1 xor 0 xor 1 xor 0 = 1
    • 校验码2(位置2):1 xor 1 xor 1 xor 1 xor 1 = 1
    • 校验码3(位置4):0 xor 1 xor 1 xor 0 xor 0 = 0
    • 校验码4(位置8):0 xor 1 xor 1 xor 0 xor 0 = 0

    三、循环冗余校验码(CRC校验)

    学习资料:CRC的校验原理以及例子

    原理:CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而构成一个总长为n=p+r位的二进制序列;附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误,这种特定关系就会被破坏。

    实现步骤:

    双方事先约定了一个R次多项式g(x),即CRC码

    CRC码的特点:

    • 位数要少于原编码
    • 收尾为1
    • 自行决定

    例:

    原编码:1001001011

    则CRC码可以为10011,也可以为11001等

    但是:10010这种不可以,因为它的尾巴不是1,1001101011也不行,因为它的位数与原编码的一致。

    要注意的是:CRC码并非是校验码,但需要通过CRC码来获得校验码。具体校验码的话要先让原编码加上CRC码位数个0(即CRC码有的多少位,就要加上多少位0在原编码的后面)然后用新原编码除CRC码,得到的余数就是校验码

    例:

    原编码=1010001101

    CRC码设为:110101

    校验码有5位,因此

    新原编码:101000110100000

    然后用新原编码除以CRC码:

    校验码就是01110

    校验方法

    用原编码与校验码进行模2减法,获得最终原编码。此时最终原编码除以CRC码是可以整除的,由于接收方也有相同的CRC码,在数据传输的过程中不发生错误,接收方用接收到的数据除以CRC码也是可以整除的,此时为无错误。同时,不能整除,说明传输过程中数据发生了错误。

    展开全文
  • 低密度奇偶校验码的编码方法研究,李金根,郑紫微,低密度奇偶校验码具有优异的性能,是当前性能最好的信道编码之一。作为超三代通信系统信道编码强有力的竞争者,低密度奇偶校验码
  • 奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。例如,单个的奇偶校验将使码的最小距离由一增加到二。 一个二进制码字,如果它的码元有奇数个1,就称为具有奇性。例如,码字“10110101”有五...

    相关文章:

           校验码——码距   https://blog.csdn.net/weixin_44330072/article/details/106860286

           校验码——海明码及码距   https://blog.csdn.net/weixin_44330072/article/details/106695425

           校验码——CRC循环冗余校验码   https://blog.csdn.net/weixin_44330072/article/details/106859961

     

           其实校验码就是在码距的原理上产生的,码距越大校验能力,纠错能力越强,所以奇偶校验码、海明码、CRC码究其原理都是利用一系列规则提升一段码字的码距而已。

     

    一、奇偶校验码

           奇偶校验码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。例如,单个的奇偶校验将使码的最小距离由一增加到二。
           一个二进制码字,如果它的码元有奇数个1,就称为具有奇性。例如,码字“10110101”有五个1,因此,这个码字具有奇性。同样,偶性码字具有偶数个1。注意奇性检测等效于所有码元的模二加,并能够由所有码元的异或运算来确定。对于一个n位字,奇性由下式给出:

    奇性 = a_{0} ⊕ a_{1} ⊕ a_{2} ⊕ … ⊕ a_{n}

           奇偶校验可描述为:给每一个码字加一个校验位,用它来构成奇性或偶性校验。例如,在图2 中,就是这样做的。可以看出,附加码元d2,是简单地用来使每个字成为偶性的。因此,若有一个码元是错的,就可以分辨得出,因为奇偶校验将成为奇性。奇偶校验编码通过增加一位校验位来使编码中1个个数为奇数(奇校验)或者为偶数(偶校验),从而使码距变为2。因为其利用的是编码中1的个数的奇偶性作为依据,所以不能发现偶数位错误。

           再以数字0的七位ASCII码(0110000)为例,如果传送后右边第一位出错,0变成 1。接收端还认为是一个合法的代码0110001(数字1的ASCII码)。若在最左边加一位奇校验位,编码变为10110000,如果传送后右边第一位出错,则变成10110001,1的个数变成偶数,就不是合法的奇校验码了。但若有两位(假设是第1、2位)出错就变成10110011,1的个数为5,还是奇数。接收端还认为是一个合法的代码(数字3的ASCII码)。所以奇偶校验不能发现。

           奇偶校验位可由硬件电路(异或门)或软件产生:
                  偶校验位 a_{n}a_{0} ⊕ a_{1} ⊕ a_{2} ⊕ … ⊕ a_{n-1}, 奇校验位 a_{n} =NOT( a_{0} ⊕ a_{1} ⊕ a_{2} ⊕ … ⊕ a_{n-1} )。

           在一个典型系统里,在传输以前,由奇偶发生器把奇偶校验位加到每个字中。原有信息中的数字在接收机中被检测, 如果没有出现正确的奇、偶性,这个信息标定为错误的,这个系统将把错误的字抛掉或者请求重发。

           在实际工作中还经常采用纵横都加校验奇偶校验位的编码系统--分组奇偶校验码。

           现在考虑一个系统, 它传输若干个长度为m位的信息。如果把这些信息都编成每组n个信息的分组,则在这些不同的信息间,也如对单个信息一样,能够作奇偶校验。图4中n个信息的一个分组排列成矩形式样,并以横向奇偶(HP)及纵向奇偶(VP)的形式编出奇偶校验位。
           m位数字、横向奇偶位、n个码字

    a_{1}a_{2}...a_{m-1}a_{m}HP_{1}
    b_{1}b_{2}...b_{m-1}b_{m}HP_{2}
    c_{1}c_{2}...c_{m-1}c_{m}HP_{3}
    ..................
    n_{1}n_{2}...n_{m-1}n_{m}HP_{n}
    VP_{1}VP_{2}...VP_{m-1}VP_{m}HP_{n+1}

                                                                                                   纵向奇偶位
                                                                            图 4 用综横奇偶校验的分组奇偶校验码

           研究图4可知:分组奇偶校验码不仅能检测许多形式的错误。并且在给定的行或列中产生孤立的错误时,还可对该错误进行纠正。
           在初级程序员试题中(早期也出现在程序员试题中),经常有综横奇偶校验的题目。一般解法应该是这样:先找一行或一列已知数据完整的,确定出该行(或列)是奇校验还是偶校验。并假设行与列都采用同一种校验(这个假设是否正确,在全部做完后可以得到验证)。然后找只有一个未知数的行或列,根据校验性质确定该未知数,这样不断做下去,就能求出所有未知数。

    【例】2001年初级程序员试题
           由 6 个字符的 7 位 ASCII 编码排列,再加上水平垂直奇偶校验位构成下列矩阵(最后一列为水平奇偶校验位,最后一行为垂直奇偶校验位):

    字符7位ASCII码HP
    30X_{1}X_{2}00110
    Y_{1}100100X_{3}1
    +X_{4}1010110
    Y_{2}01X_{5}X_{6}1111
    D100X_{7}10X_{8}0
    =0X_{9}111X_{10}11
    VP00111X_{11}1X_{12}

           则 X_{1}X_{2}X_{3}X_{4} 处的比特分别为 __(36)__ ;
           X_{5}X_{6}X_{7}X_{8} 处的比特分别为 __(37)__ ;
           X_{9}X_{10}X_{11}X_{12} 处的比特分别为 __(38)__ ;Y_{1} 和 Y_{2} 处的字符分别为 __(39)__ 和 __(40)__ 。

    [解]

           从ASCII码左起第5列可知垂直为偶校验。则:
           从第1列可知 X_{4}=0;从第3行可知水平也是偶校验。
           从第2行可知 X_{3}=1;从第7列可知 X_{8}=0;从第8列可知 X_{12}=1;
           从第7行可知 X_{11}=1;从第6列可知 X_{10}=0;从第6行可知 X_{9}=1;从第2列可知 X_{1}=1;
           从第1行可知 X_{2}=1;从第3列可知 X_{5}=1;从第4行可知 X_{6}=0;
           从第4列(或第5行)可知 X_{7}=0;整理一下:
           (36) X_{1}X_{2}X_{3}X_{4} = 1110
           (37) X_{5}X_{6}X_{7}X_{8} = 1000
           (38) X_{9}X_{10}X_{11}X_{12} = 1011
           (39) 由字符 Y_{1} 的ASCII码1001001=49H知道,Y_{1} 即是“I”(由“D”的ASCII码是1000100=44H推得)
           (40) 由字符 Y_{2} 的ASCII码0110111=37H知道,Y_{2} 即是“7”(由“3”的ASCII码是0110011=33H推得)
           假如你能记住“0”的ASCII码是0110000=30H;“A”的ASCII码是1000001=41H,则解起来就更方便了。

           

    展开全文
  • 基于FPGA的低密度奇偶校验码编码器设计.pdf
  • 奇偶校验码是 奇校验码 和 偶校验码 的统称. 它们都是通过在要校验的编码上加一位校验位组成. 如果是 奇校验 加上校验位后,编码中1的个数为 奇数个 如果是 偶校验 加上校验位后,编码中1的个数为 偶数个 水平奇偶校验...

    奇偶校验码是 奇校验码 和 偶校验码 的统称.
    它们都是通过在要校验的编码上加一位校验位组成.
    如果是 奇校验 加上校验位后,编码中1的个数为 奇数个
    如果是 偶校验 加上校验位后,编码中1的个数为 偶数个

    水平奇偶校验是将若干字符组成一个信息块,对该信息块的字符中对应的位分别进行奇偶校验,下表给出了水平奇偶校验示例。

    在这里插入图片描述

    例:
    原编码 奇校验 偶校验
    0000 0000 1 0000 0
    0010 0010 0 0010 1
    1100 1100 1 1100 0
    1010 1010 1 1010 0
    如果发生 奇数 个位传输出错,那么编码中1的个数就会发生变化.
    从而校验出错误. 要求从新传输数据.

    目前应用的 奇偶校验码 有3种.
    水平奇偶校验码
    对每一个数据的编码添加校验位,使信息位与校验位处于同一行.

    垂直奇偶校验码
    把数据分成若干组,一组数据排成一行,再加一行校验码.
    针对每一行列采用 奇校验 或 偶校验
    例: 有32位数据10100101 00110110 11001100 10101011
    垂直奇校验 垂直偶校验
    数据 10100101 10100101
    00110110 00110110
    11001100 11001100
    10101011 10101011
    校验为00001011 11110100

    水平垂直奇偶校验码
    就是同时用水平校验和垂直校验
    例:
    奇校验 奇水平 偶校验 偶水平
    数据 10100101 1 10100101 0
    00110110 1 00110110 0
    11001100 1 11001100 0
    10101011 0 10101011 1
    校验 00001011 0 11110100 1

    然后是 海明校验码
    海明码也是利用奇偶性来校验数据的.
    它是一种多重奇偶校验检错系统,它通过在数据位之间插入k个校验位,来扩大码距,从而实现检错和纠错.

    设原来数据有n位,要加入k位校验码.怎么确定k的大小呢?
    k个校验位可以有pow(2,k) (代表2的k次方) 个编码,其中有一个代表是否出错.
    剩下pow(2,k)-1个编码则用来表示到底是哪一位出错.
    因为n个数据位和k个校验位都可能出错
    所以k满足 pow(2,k)-1 >= n+k

    设 k个校验码为 P1,P2…Pk, n个数据位为D0,D1…Dn
    产生的海明码为 H1,H2…H(n+k)

    如有8个数据位,根据pow(2,k)-1 >= n+k可以知道k最小是4
    那么得到的海明码是
    H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1
    D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1

    然后怎么知道Pi校验哪个位呢.
    自己可以列个校验关系表
    海明码 下标 校验位组
    H1(P1) 1 P1
    H2(P2) 2 P2
    H3(D0) 1+2 P1,P2
    H4(P3) 4 P3
    H5(D1) 1+4 P1,P2
    H6(D2) 2+4 P2,P3
    H7(D3) 1+2+4 P1,P2,P3
    H8(P4) 8 P4
    H9(D4) 1+8 P1,P4
    H10(D5) 2+8 P2,P4
    H11(D6) 1+2+8 P1,P2,P4
    H12(D7) 4+8 P3,P4

    从表中可以看出
    P1校验 P1,D0,D1,D3,D4,D6
    P2校验 P2,D0,D2,D3,D5,D6
    P3校验 P3,D1,D2,D3,D7
    P4校验 P4,D4,D5,D6,D7

    其实上表很有规律很容易记
    要知道海明码Hi由哪些校验组校验
    可以把i化成 二进制数 数中哪些位k是1,就有哪些Pk校验
    如H7 7=0111 所以由P1,P2,P3
    H11 11=1011 所以由P1,P2,P4
    H3 3=0011 所以由P1,P2
    那看看Pi的值怎么确定
    如果使用偶校验,则
    P1=D0 xor D1 xor D3 xor D4 xor D6
    P2=D0 xor D2 xor D3 xor D5 xor D6
    P3=D1 xor D2 xor D3 xor D7
    P4=D4 xor D5 xor D6 xor D7
    其中xor是异或运算
    奇校验的话把偶校验的值取反即可.

    那怎么校验错误呢.
    其实也很简单. 先做下面运算.
    G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6
    G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6
    G3 = P3 xor D1 xor D2 xor D3 xor D7
    G4 = P4 xor D4 xor D5 xor D6 xor D7

    如果用偶校验那么 G4G3G2G1 全为0是表示无错误(奇校验全为1)
    当不全为0表示有错 G4G3G2G1 的十进制值代表出错的位.
    如 G4G3G2G1 =1010 表示H10(D5)出错了.
    把它求反就可以纠正错误了.

    下面举一个比较完全的例子:
    设数据为01101001,试用4个校验位求其偶校验方式的海明码.
    传输后数据为011101001101,是否有错?
    P1=D0 xor D1 xor D3 xor D4 xor D6
    =1 xor 0 xor 1 xor 0 xor 1
    =1

    P2=D0 xor D2 xor D3 xor D5 xor D6
    =1 xor 0 xor 1 xor 1 xor 1
    =0

    P3=D1 xor D2 xor D3 xor D7
    =0 xor 0 xor 1 xor 0
    =1

    P4=D4 xor D5 xor D6 xor D7
    =0 xor 1 xor 1 xor 0
    =0

    所以得到的海明码为
    0 1 1 0 0 1 0 0 1 1 0 1

    传输后为011101001101
    G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6
    =1
    G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6
    =0
    G3 = P3 xor D1 xor D2 xor D3 xor D7
    =0
    G4 = P4 xor D4 xor D5 xor D6 xor D7
    =1

    所以1001代表9即H9出错了,对它求反
    011001001101 和我们算的一样.
    由此可见 海明码 不但有检错还有纠错能力

    下面说下最后一种 CRC即 循环冗余校验码
    CRC码利用生成多项式为k个数据位产生r个校验位进行编码,其编码长度为n=k+r所以又称 (n,k)码.
    CRC码广泛应用于数据通信领域和磁介质存储系统中.
    CRC理论非常复杂,一般书就给个例题,讲讲方法.
    现在简单介绍下它的原理:
    在k位信息码后接r位校验码,对于一个给定的(n,k)码
    可以证明(数学高手自己琢磨证明过程)存在一个最高次幂为 n-k=r 的多项式g(x)
    根据g(x)可以生成k位信息的校验码,g(x)被称为 生成多项式
    用C(x)=C(k-1)C(k-2)…C0表示k个信息位
    把C(x)左移r位,就是相当于 C(x)*pow(2,r)
    给校验位空出r个位来了.

    给定一个 生成多项式g(x),可以求出一个校验位表达式r(x)
    C(x)*pow(2,r) / g(x) = q(x) + r(x)/g(x)

    用C(x)*pow(2,r)去除生成多项式g(x)商为q(x)余数是r(x)
    所以有C(x)*pow(2,r) = q(x)*g(x) + r(x)

    C(x)*pow(2,r) + r(x)就是所求的n位CRC码,由上式可以看出它是生成多项式g(x)的倍式.

    所以如果用得到的n位CRC码去除g(x)如果余数是0,就证明数据正确.
    否则可以根据余数知道 出错位 .

    在CRC运算过程中,四则运算采用 mod 2运算(后面介绍),即不考虑进位和借位.
    所以上式等价于C(x)*pow(2,r) + r(x) = q(x)*g(x)
    继续前先说下基本概念吧.
    1.多项式和二进制编码
    x的最高次幂位对应二进制数的最高位.以下各位对应多项式的各幂次.
    有此幂次项为1,无为0. x的最高幂次为r时, 对应的二进制数有r+1位
    例如g(x)=pow(x,4) + pow(x,3) + x + 1
    对应二进制编码是 11011

    2.生成多项式
    是发送方和接受方的一个约定,也是一个二进制数,在整个传输过程中,这个数不会变.
    在发送方,利用 生成多项式 对信息多项式做 模2运算 生成校验码.
    在接受方利用 生成多项式 对收到的 编码多项式 做 模2运算 校验和纠错.

    生成多项式应满足:
    a.生成多项式的最高位和最低位必须为1
    b.当信息任何一位发生错误时,被生成多项式模2运算后应该使余数不为0
    c.不同位发生错误时,应该使余数不同.
    d.对余数继续做模2除,应使余数循环.

    生成多项式很复杂
    不过不用我们生成
    下面给出一些常用的生成多项式表

    N K 码距d G(x)多项式 G(x)

    7 4 3 x3+x+1 1011

    7 4 3 x3+x2+1 1101

    7 3 4 x4+x3+x2+1 11101

    7 3 4 x4+x2+x+1 10111

    15 11 3 x4+x+1 10011

    15 7 5 x8+x7+x6+x4+1 111010001

    31 26 3 x5+x2+1 100101

    31 21 5 x10+x9+x8+x6+x5+x3+1 11101101001

    63 57 3 x6+x+1 1000011

    63 51 5 x12+x10+x5+x4+x2+1 1010000110101

    1041 1024   x16+x15+x2+1 11000000000000101

    3.模2运算
    a.加减法法则
    0 +/- 0 = 0
    0 +/- 1 = 1
    1 +/- 0 = 1
    1 +/- 1 = 0
    注意:没有进位和借位

    b.乘法法则
    利用模2加求部分积之和,没有进位

    c.除法法则
    利用模2减求部分余数
    没有借位
    每商1位则部分余数减1位
    余数最高位是1就商1,不是就商0
    当部分余数的位数小于余数时,该余数就是最后余数.

    例 1110
    1011)1100000
    1011
    1110
    1011
    1010
    1011
    0010(每商1位则部分余数减1位,所以前两个0写出)
    0000
    010(当部分余数的位数小于余数时,该余数就是最后余数)
    最后商是1110余数是010

    好了说了那么多没用的理论.下面讲下CRC的实际应用

    例: 给定的生成多项式g(x)=1011, 用(7,4)CRC码对C(x)=1010进行编码.

    由题目可以知道下列的信息:
    C(x)=1010,n=7,k=4,r=3,g(x)=1011

    C(x)*pow(2,3)=1010000
    C(x)*pow(2,3) / g(x) = 1001 + 011/1011
    所以r(x)=011

    所以要求的编码为1010011

    例2: 上题中,数据传输后变为1000011,试用纠错机制纠错.
    1000011 / g(x) = 1011 + 110/1011

    不能整除,所以出错了. 因为余数是110
    查1011出错位表可以知道是第5位出错.对其求反即可.

    循环冗余校验码CRC(Cyclic Redundancy Code)采用一种多项式的编码方法。把要发送的数据位串看成是系数只能为“1”或为“0”的多项式。一个k位的数据块可以看成Xk-1到X0的k项多项式的系数序列。例如,“110001”有6位,表示多项式是“X5 + X4+ 1”。多项式的运算是模2运算。
    采用CRC码时,发方和收方必须事先约定一个生成多项式G(X),并且G(X)的最高位和最低必须是1。要计算m位数据块的M(X)的校验和,生成多项式必须比该多项式短。其基本思想是:将校验和附加在该数据块的末尾,使这个带校验和的多项式能被G(X)除尽。当接收方收到带校验和的数据块时,用G(X)去除它,如果有余数,则传输有错误。
    计算校验和的方法如下:

    在这里插入图片描述
    其中的校验位为x的最高次幂
    在这里插入图片描述

    海明码:如果是做题的时候还要看题目的顺序
    在这里插入图片描述
    比如上面的图片中的如果是H7-H1的话和H1-H7不同。

    展开全文
  • 描述了LDPC的校验矩阵的产生 编码和解码 同时包含BPSK调制解调 不同码长比可用
  • 奇偶校验码&海明码&循环冗余校验码

    千次阅读 2021-02-08 11:57:48
    文章目录一、奇偶校验码二、海明码三、循环冗余校验码 一、奇偶校验码 特点:能检错,但是不能纠错。 码距: 一个编码系统中任意两个合法编码(码字)之间不同的二进数位(bit)数叫这两个码字的码距,而整个编码...
  • 校验码(奇偶校验码)

    千次阅读 多人点赞 2020-09-21 21:05:16
    校验码(奇偶校验码) 1.奇偶校验码 通过在编码中增加一位校验位来使编码中1的个数为奇数或者偶数,校验位可以在原编码的前面或者后面加。通过加入校验位后的1个数是奇数还是偶数,可分为两种: 奇校验:1的个数为奇数...
  • 奇偶校验码算法 问题陈述: (Problem Statement:) You are getting a stream of numbers (say long type numbers), compute the parity of the numbers. Hypothetically you have to serve a huge scale like 1 ...
  • 奇偶校验码(计算机组成原理10)

    千次阅读 2020-10-05 13:00:46
    - 校验原理、奇偶校验的相关定义 - 计算机内部如何实现奇偶校验
  • 1.奇偶校验码怎么通过奇偶校验码判断数据是正确还是错误呢?(1)奇校验(1)偶校验为什么无法检查出偶数个错误?2.海明(汉明)校验码什么是海明校验码?一题搞懂海明码,在信息位 n=4 ,校验位 k=3 时,求 1010 的...
  • 奇偶校验码】 采用奇偶校验方式的校验码被称为奇偶校验码。假设奇偶校验码有n位,其中奇偶校验位占1位,信息位占n-1位。以8bit为例,奇偶校验位占1位且在最高位(在最低位也可),剩下7位为信息位。 奇校验,使得...
  • 前言:奇偶校验码是一种增加二进制代码传输距离最简单和最广泛的方法,通过增加冗余位使码字中“1”的个数恒为奇数或者偶数。
  • 1.奇偶校验码 奇校验码保证一段数据出现奇数个1。 如两个码字 00 与 01,为保证奇校验的要求,该两码字可增添为100和001。 偶校验码则保证一段数据出现偶数个1. [外链图片转存失败,源站可能有防盗链机制,建议将图片...
  • 奇偶校验码(Parity Code) Java代码实现

    千次阅读 2021-02-15 08:59:17
    文章目录校验码术语奇偶校验java代码 校验码 计算机系统运行时,为了确保数据在传递过程中正确无误,一是提高硬件电路的可靠性,二是提高代码的校验能力,包括查错与纠错。通常使用校验码的方法来检测传送的数据是否...
  • 奇偶校验码 CRC循环冗余校验码 海明码
  • 偶校验矩阵和低密度奇偶校验码的构造方法 摘要 - 低密度奇偶校验(LDPC)码是具有稀疏奇偶校验矩阵的线性分组码。 在本文中,给出了用于生成LDPC码的一些构造方法的简要描述。 这些方法通常分为两类:随机和分析。 ...
  • 1:奇偶校验码奇偶校验码是 [1] 一种增加二进制传输系统最小距离的简单和广泛采用的方法。是一种通过增加冗余位使得码字中"1"的个数恒为奇数或偶数的编码方法,它是一种检错码。在实际使用时又可分为...
  • 格雷码、奇偶校验码的Verilog描述 格雷码( Gray Code)也是一种常见的无权码。它也具有相邻性,即两个相邻代码之间仅有1位取值不同,并且0和最大数(2^n -1)之间也只有1位不同、因此它是一种循环码。格雷码的这个特点...
  • 基本概念 码距:一个编码系统中,任意2个合法码字之间的码距的最小值称为该编码系统的码距。 000和001,码距为1 根据信息论基本原理,码距d与校验码检错和纠错能力如下: ...奇偶校验码 D奇=D1⨁D2⨁D3⨁D4…⨁...
  • 奇偶校验码原来这样算!!!

    万次阅读 2020-05-01 16:25:46
    数据传输的正误 数据发出方A像数据接收方B发送一串加密过后的情书(11011),但是信息在传输过程中可能发生错误,比如某人截获并修改内容,一段美好的爱情就结束了…...奇偶校验码分两种,实现约定是采用奇校验方式还是...
  • LDPC低密度奇偶校验码

    2016-05-10 20:33:10
    低密度奇偶校验码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,592
精华内容 7,836
关键字:

奇偶校验码