海明码编码译码python(海明码码字)

本文目录一览:

什么是海明码呀?通俗一点,但又能深刻一点!谢谢了!!!

海明码其实也不难,相对于寄偶检验码 它不仅可以检验出错误,还能修正错误!但只能是检验、修正一位错误!说一大堆理论是没什么意思,下面将通过一个例子,尽可能的用最通俗易懂的方式进行讲解!最后大家会发现海明码很神奇!!

假设要传送的数据为:1011 0011

校验流程如下:

一:确定校验位并插入到有效数据位中。

相比奇偶校验只插入一个检验码,海明码需要插入多个检验码,插入的位数与有效数据位数相关,公式如下

公式:2^r-rk+1,其中r就是要插入检验码的个数,取满足条件的最小整数,k是有效数据位数。因为我们要传送的数据是:1011 0011,显然k=8,推出r=4。也就说我们要将4个校验位插入到有效数据中,怎么插入呢?按照如下规则:

插入位置固定为2^N(N:0,1,2,3,4,5……)处,因为r=4,即只需要取4个有{2^0,2^1,2^2,2^3},对应位置即是1,2,4,8,当然了,如果r=5,那么插入位置为:1,2,4,8,16.同类可以推出其他情况,不再啰嗦。(之所以选择这样的位置插入,是为了有效的分组,保证后面的校验分组能有效的错开,不会互相干扰,这句话不需要理解,到后面就能体会!)

通过分析得到待传送的数据为:xx1x 011x 0011,4位校验位+8为有效数据位。

二、确定校验位的数值。

显然X只能取0,1,下面确定x的值:

由一可知待传送数据为:xx1x 011x 0011。

规则:以X的位置为长度,依次从待传送数据中取X个数,然后跳过X个数,再取X个数,直到待传送数据串尾,得到一个子串,然后统计子串中1的个数,如果为奇数,则x=0,为偶数,x=1(当然,反过来也行,其实这就是奇偶校验的规则,想了解奇偶校验可以参见我以前的回答的,这里不了解也行)

第1个X:位置为1,从第1个位置开始依次取1个数据,并跳过1个数据再取,直到串尾得到一个子串:

{x 1 0 1 0 1},这个串可记为第1个校验组, 因为1的个数是3个为奇数,故x=0.

第2个X:位置为2,故从第2个位置开始依次取2个数据,并跳过2个数据再取,直到串尾得到一个子串:

{x1  11  01} ,记为第2个校验组,因为1的个数为4是偶数,故x=1.

第3个X:位置是4,故从第4个位置开始依次取4个数据,并跳过4个数据再取,直到串尾得到一个子串:

{x011     1},记为第3个校验组,因为1的个数为3是奇数,故x=0.

第4个X:位置是8,故从第8个位置开始依次取8个数据,并跳过8个数据再取,直到串尾得到一个子串:

{x0011 },记为第4个校验组,……,X=1。

故得到最终的待传送的数据串为:0110 0111 0011。

这里其实就可以看到了,为什么X的位置要取2^N,这样才能保证各个校验位不会相互干扰。

经过以上一、二步骤就完整了海明码的构造过程,下面讲解校验过程:

三、根据步骤二中的构造规则,取出各校验组

发送的数据串为:0110 0111 0011。

假设接受到的数据串为:0110 0111 1011(注意和传送数据串相比,第9为出现了错误!)

规则:以X的位置为长度,依次从待传送数据中取X个数,然后跳过X个数,再取X个数,直到待传送数据串尾,得到一个子串,然后统计子串中1的个数,如果为奇数,则x=0,为偶数,x=1(规则必须和步骤二中一样)

根据二中制定的规则再次取出各个校验组。

第1个校验组:从第1个位置开始依次取1个数据,并跳过1个数据再取,直到串尾得到一个子串:{0 1 0 1 1 1}。

第2个校验组:从第2个位置开始依次取2个数据,并跳过2个数据再取,直到串尾得到一个子串:{11  11  01}

第3个校验组:从第4个位置开始依次取4个数据,并跳过4个数据再取,直到串尾得到一个子串:{0011    1}

第4个校验组:从第8个位置开始依次取8个数据,并跳过8个数据再取,直到串尾得到一个子串:{11011}.

四、根据步骤二的构造规则,确定存在错误的校验组,并通过错误校验组的交集,最终确定出错的位置。

由步骤三得到4个校验组:

1:{0 1 0 1 1 1}。  对应位置为{1 3 5 7 9 11}

2:{11  11  01}。 对应位置为{2 3 6 7 10 11}

3:{0011    1}  。对应位置为{4567    12}

4:{11011}。   对应位置为{8 9 10 11 12}

因为我们的构造规则是:统计子串中1的个数,如果为奇数,则x=0,为偶数,x=1。

所以正确的校验组中1的个数绝对是奇数!(好好琢磨,很容易就想通了,如果我们的规则是为奇数,则x=1,为偶数,x=0。那么正确的校验组中1的个数绝对是偶数),所以如果校验组1的个数不是奇数,那么这个校验组就存在问题。因而可以判断第1个和第4个校验组出现问题了。

确定了第1个和第4个校验组出现问题后,找到这两个校验组的交集即第9个位置和第11个位置是它们交集,即共同校验的位置。于是判断出现问题的位置要么就是第9个位置,要么就是第11个位置!因为在第2个校验组中有第11个位置,故第11个位置绝对没有出错,因为就可以判断是第9个位置出现错误!

到这里,应该懂了吧?但是不是觉得找出错位置有点麻烦啊?下面就给出一个具体的实现方法,理解了上面的描述,再了解下面实现的方法,立马就能确定出错误的位置:

首先:我们对各个校验组求异或。

第一个校验组:{0 1 0 1 1 1} 异或的结果为:0

第二个校验组:{11  11  01}异或的结果为:1

第三个校验组:{0011    1} 异或的结果为:1

第四个校验组:{11011}异或的结果为:0

接着:倒置拼接异或结果,得到:0110,

最后:按位取反的到:1001,。

大家有没有惊奇的发现1001的十进制数就是9,这不就是出错的位置吗?这是巧合吗?

不急再看一个例子:

传送的数据串为:  0110 0111 0011(还是我们开始的那个串)

接受到的数据串为:0110 1111 0011(和正确数据串相比,第5个位置出错了)

第一个校验组:{0 1 1 1 0 1} 异或的结果为:0

第二个校验组:{11  11  01}异或的结果为:1

第三个校验组:{0111    1} 异或的结果为:0

第四个校验组:{10011}异或的结果为:1

倒置拼接:1010  反转为:0101  对应十进制数为5!

也就是说方法是真确的!!不用怀疑!!这也就是海明码的奇妙之处!

再来看看一个例子:

传送的数据串为:  0110 0111 0011(还是我们开始的那个串)

接受到的数据串为:0110 0110 0011(和正确数据串相比,第8个位置校验位出错了)

显然这是校验位出错了,那么能不能校验出来呢?

第一个校验组:{0 1 0 1 0 1} 异或的结果为:1

第二个校验组:{11  11  01}异或的结果为:1

第三个校验组:{0011    1} 异或的结果为:1

第四个校验组:{00011}异或的结果为:0

倒置反转结果为1000 正好是8,所以也没问题。

下面我们来说下规则:(其实就是说异或与奇偶的关系,想拓展的就可以看看)

上面的例子中,我们规定: 统计子串中1的个数,如果为奇数,则x=0,为偶数,x=1。如果是按这样的规定,那么校验组中1的个数必定是奇数,正是因为如此,所以校验组中如果1的个数不是奇数那么肯定出现了错误!而如果一个串中1的个数是奇数,那么串异或的结果一定为1,其实这个规则对应的就是奇校验!反之,如果为奇数,则x=1,为偶数,x=0,那么对应的就是偶校验!

故得到以下结论:

如果采用奇检验构造海明码,那么出错校验组中的1的个数必为偶数,即异或的结果必定为0!

如果采用奇检验构造海明码,那么出错的位置是校验组异或结果倒置拼接并反转的十进制数

如果采用偶检验构造海明码,那么出错校验组中的1的个数必为奇数,即异或的结果必定为1!

如果采用偶检验构造海明码,那么出错位置是校验组异或结果直接倒置拼接的十进制数!

关于偶检验构造海明码这里就不再详细展开,如果你能用偶检验的方法在把上面的例子都做一遍,那么海明码你就已经完全弄懂了!试试吧!

关于奇偶检验码 建议还是看看,因为海明码是基于奇偶校验的改进!而且奇偶校验更简单!

海明校验码的内容以及格式?

你好、海明校验码由Richard Hamming于1950年提出、目前还被广泛采用的一种很有效的校验方法,是只要增加少数几个校验位,就能检测出二位同时出错、亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段,后者被称为自动纠错。它的实现原理,是在k个数据位之外加上r个校验位,从而形成一个k+r位的新的码字,使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中,当某一位出错后,就会引起相关的几个校验位的值发生变化,这不但可以发现出错,还能指出是哪一位出错,为进一步自动纠错提供了依据。

假设为k个数据位设置r个校验位,则校验位能表示2r个状态,可用其中的一个状态指出 “没有发生错误”,用其余的2 r -1个状态指出有错误发生在某一位,包括k个数据位和r个校验位,因此校验位的位数应满足如下关系:

2r ≥ k + r + 1 (2.7)

如要能检出与自动校正一位错,并能同时发现两位错,此时校验位的位数r和数据位的位数k应满足下述关系:

2r-1 ≥ k + r (2.8)

按上述不等式,可计算出数据位k与校验位r的对应关系,如表2.2所示。

表2.2

K值 最小的r值

3-4 4

5-10 5

11-25 6

26-56 7

57-119 8

设计海明码编码的关键技术,是合理地把每个数据位分配到r个校验组中,以确保能发现码字中任何一位出错;若要实现纠错,还要求能指出是哪一位出错,对出错位求反则得到该位的正确值。例如,当数据位为3位(用D3 D2 D1表示)时,检验位应为4位(用P4 P3 P2 P1表示)。可通过表2.3表示的关系,完成把每个数据位划分在形成不同校验位的偶校验值的逻辑表达式中。

表2.3 校验位与数据位的对应关系

在P1、P2、P3、P4竖列相应行分别填1,

在该4列的低3横行其它位置分别填0,

在最顶横行的每个尚空位置都分别填1。

若只看低3横行,右4竖列的3个bit的组合值分别为十进制的1、2、4、0,则分配 D1 D2 D3列的组合值为3 5 6,保证低3横行各竖列的编码值各不相同。

表中D3 D2 D1为三位数据位,P4 P3 P2 P1为四位校验位。其中低三位中的每一个校验位P3 P2 P1的值,都是用三个数据位中不同的几位通过偶校验运算规则计算出来的。其对应关系是:对Pi(i的取值为1~3),总是用处在Pi取值为1的行中的、用1标记出来的数据位计算该Pi的值。最高一个校验位P4,被称为总校验位,它的值,是通过对全部三个数据位和其它全部校验位(不含P4本身)执行偶校验计算求得的。

形成各校验位的值的过程叫做编码,按刚说明的规则,4个校验位所用的编码方程为:

P4 = D3 D2 D1 P3 P2 P1

P3 = D3 D2

P2 = D3 D1

P1 = D2 D1

由多个数据位和多个校验位组成的一个码字,将作为一个数据单位处理,例如被写入内存或被传送走。之后,在执行内存读操作或在数据接收端,则可以对得到的码字,通过偶校验来检查其合法性,通常称该操作过程为译码,所用的译码方程为:

S4 = P4 D3 D2 D1 P3 P2 P1

S3 = P3 D3 D2

S2 = P2 D3 D1

S1 = P1 D2 D1

译码方程和编码方程的对应关系很简单。译码方程,是用一个校验码和形成这个校验码的编码方程执行异或,实际上是又一次执行偶校验运算。通过检查四个S的结果,可以实现检错纠错的的目的。实际情况是,当译码求出来的S4、S3、S2、S1的得值与表2.3中的那一列的值相同,就说明是哪一位出错;故人们又称表2.3为出错模式表。若出错的是数据位,对其求反则实现纠错;若出错的是校验位则不必理睬。举例如下:

任何一位(含数据位、校验位)均不错,则四个S都应为0值;

任何单独一位数据位出错,四个S中会有三个为1;如D3错,则S4 S3 S2 S1为1110。

若单独一位校验位出错,四个S中会有一个或两个为1;如P1错,S4 S3 S2 S1为1001,如P4错,S4 S3 S2 S1为1000。

任何两位(含数据位、校验位)同时出错,S4一定为0,而另外三个S位一定不全为0,此时只知道是两位同时出错,但不能确定是哪两位出错,故已无法纠错。如D1、 P2出错,会使S4 S3 S2 S1为0001。请注意,S4的作用在于区分是奇数位出错还是偶数位出错,S4为1是奇数位错,为0是无错或偶数位错。这不仅为发现两位错所必需,也是为确保能发现并改正一位错所必需的。若不设置S4,某种两位出错对几个S的影响与单独另一位出错可能是一样的(不必花费精力推敲),此时若不加以区分,简单地按一位出错自动完成纠错处理反而会帮倒忙。

海明码的原理

海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位,增加r位冗余位,构成一个n=k+r位的码字,然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式: r 2^r ≥ k r 1 或 2^r ≥ n 1海明码的编码效率为: R=k/(k+r) 式中 k为信息位位数 r为增加冗余位位数

目录

1.海明码的原理

2.海明码的生成与接收

3.海明码的计算

4.海明码校验程序设计原理分析参考

编辑本段1.海明码的原理

在数据中间加入几个校验码,码距均匀拉大,将数据的每个二进制位分配在几个奇偶校验组里,当某一位出错,会引起几个校验位的值发生变化。

海明不等式:

校验码个数为K,2的K次方个信息,1个信息用来指出“没有错误”,其余(2^K)-1个指出错误发生在那一位,但也可能是校验位错误,故有N=(2^K)-1-K能被校验。

海明码的编码规则:

1.每个校验位Ri被分配在海明码的第2的i次方的位置上,

2.海明码的每一位(Hi)是由多个/1个校验值进行校验的,被校验码的

位置码是所有校验位的校验位位置码之和。

一个例题:

4个数据位d0,d1,d2,d3, 3个校验位r0,r1,r2,对应的位置为:

d3 d2 d1 r2 d0 r1 r0 ======b7 b6 b5 b4 b3 b2 b1

校验位的取值,就是他所能校验的数据位的异或

b1为b3,b5,b7的异或,b2为b3,b6,b7 b4为b5,b6,b7

海明v传送到接受方后,将上三式的右边(b1,b2,b4)的逻辑表达式分别

异或上左边的值就得到了校验方程,如果上题采用偶校验

G1=b1 b3 b5 b7的异或

G2=b2 b3 b6 b7的异或

G3=b4 b5 b6 b7的异或

若G1G2G3为001是第一位错

若为011是第三位错

编辑本段2.海明码的生成与接收

特注:以下的+均代表异或

方法一:

1)海明码的生成。

例1.已知:信息码为:”0010″。海明码的监督关系式为:

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

求:海明码码字。

解:1)由监督关系式知冗余码为a2a1a0。

2)冗余码与信息码合成的海明码是:”0010a2a1a0″。

设S2=S1=S0=0,由监督关系式得:

异或运算:

a2=a4+a5+a6=1

a1=a3+a5+a6=0

a0=a3+a4+a6=1

因此,海明码码字为:”0010101″

对以上这道题目的第二问的疑问:

冗余码与信息码合成的海明码是:”0010a2a1a0″。为什么a2a1a0直接加在信息码后面,而不是按照1,2,4,8位的顺序加在信息码后面【例如:001(a2)0(a1)(a0)=0011001】

2)海明码的接收。

例2.已知:海明码的监督关系式为:

S2=a2+a4+a5+a6

S1=a1+a3+a5+a6

S0=a0+a3+a4+a6

接收码字为:”0011101″(n=7)

求:发送端的信息码。

解:1)由海明码的监督关系式计算得S2S1S0=011。

2)由监督关系式可构造出下面错码位置关系表:

S2S1S0

000

001

010

100

011

101

110

111

错码位置

无错

a0

a1

a2

a3

a4

a5

a6

3)由S2S1S0=011查表得知错码位置是a3。

4)纠错–对码字的a3位取反得正确码字:”0 0 1 0 1 0 1″

5)把冗余码a2a1a0删除得发送端的信息码:”0010″

方法二:(不用查表,方便编程)

1)海明码的生成(顺序生成法)。

例3.已知:信息码为:” 1 1 0 0 1 1 0 0 ” (k=4代表冗余位数,即校验码位数)

求:海明码码字。

解:1)把冗余码A、B、C、…,顺序插入信息码中,得海明码

码字:” A B 1 C 1 0 0 D 1 1 0 0 “

码位: 1 2 3 4 5 6 7 8 9 10 11 12

其中A,B,C,D分别插于2的k次方位(k=0,1,2,3)。码位分别为1,2,4,8。

2)冗余码A,B,C,D的线性码位是:(相当于监督关系式)

监督关系式的推导:

D C B A

1 0 0 0 1

2 0 0 1 0

3 0 0 1 1

4 0 1 0 0

5 0 1 0 1

6 0 1 1 0

7 0 1 1 1

8 1 0 0 0

9 1 0 0 1

10 1 0 1 0

11 1 0 1 1

12 1 1 0 0

根据上面表格得到 A B C D

需要说明的是公式中参与计算的是表格中出现”1″的那个位 右边是数据位的二进制数,公式中的”+”表示异或

故此有如下表达式:

A-1,3,5,7,9,11;(这里的1 3 5 7 9 11均为A那一列出现1的位)

B-2,3,6,7,10,11;

C-4,5,6,7,12;(注 5=4+1;6=4+2;7=4+2+1;12=8+4)

D-8,9,10,11,12。

3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0):

A=∑(0,1,1,0,1,0)=1

B=∑(0,1,0,0,1,0)=0

C=∑(0,1,0,0,0) =1

D=∑(0,1,1,0,0) =0

4)海明码为:”1 0 1 1 1 0 0 0 1 1 0 0″

2)海明码的接收。

例4.已知:接收的码字为:”1 0 0 1 1 0 0 0 1 1 0 0″(k=4代表冗余位数,即校验码位数)

求:发送端的信息码。

解:1)设错误累加器(err)初值=0

2)求出冗余码的偶校验和,并按码位累加到err中:

A=∑(1,0,1,0,1,0)=1 err=err+2^0=1

B=∑(0,0,0,0,1,0)=1 err=err+2^1=3

C=∑(1,1,0,0,0) =0 err=err+0 =3

D=∑(0,1,1,0,0) =0 err=err+0 =3

由err≠0可知接收码字有错,

3)码字的错误位置就是错误累加器(err)的值3。

4)纠错–对码字的第3位值取反得正确码字:

“1 0 1 1 1 0 0 0 1 1 0 0”

5)把位于2的k次方位的冗余码删除得信息码:”1 1 0 0 1 1 0 0″

编辑本段3.海明码的计算

海明码(Hamming Code )编码的关键是使用多余的奇偶校验位来识别一位错误。

码字(Code Word) 按如下方法构建:

1、把所有2的幂次方的数据位标记为奇偶校验位(编号为1, 2, 4, 8, 16, 32, 64等的位置)

2、其他数据位用于待编码数据. (编号为3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置)

3、每个奇偶校验位的值代表了代码字中部分数据位的奇偶性,其所在位置决定了要校验和跳过的比特位顺序。

位置1:校验1位,跳过1位,校验1位,跳过1位(1,3,5,7,9,11,13,15,…)

位置2:校验2位,跳过2位,校验2位,跳过2位 (2,3,6,7,10,11,14,15,…)

位置4:校验4位,跳过4位,校验4位,跳过4位 (4,5,6,7,12,13,14,15,20,21,22,23,…)

位置8:校验8位,跳过8位,校验8位,跳过8位(8-15,24-31,40-47,…)

如果全部校验的位置中有奇数个1,把该奇偶校验位置为1;如果全部校验的位置中有偶数个1,把该奇偶校验位置为0.

举例说明:

一个字节的数据:10011010

构造数据字(Data Word),对应的校验位留空_ _ 1 _ 0 0 1 _ 1 0 1 0

计算每个校验位的奇偶性 ( ?代表要设置的比特位):

位置1检查1,3,5,7,9,11:

? _ 1 _ 0 0 1 _ 1 0 1 0. 偶数个1,因此位置1设为0,即: 0 _ 1 _ 0 0 1 _ 1 0 1 0

位置2检查2,3,6,7,10,11:

0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇数个1,因此位置2设为1,即: 0 1 1 _ 0 0 1 _ 1 0 1 0

位置4检查4,5,6,7,12:

0 1 1 ? 0 0 1 _ 1 0 1 0. 奇数个1,因此位置4设为1,即: 0 1 1 1 0 0 1 _ 1 0 1 0

位置8检查8,9,10,11,12:

0 1 1 1 0 0 1 ? 1 0 1 0. 偶数个1,因此位置8设为0,即: 0 1 1 1 0 0 1 0 1 0 1 0

因此码字为: 011100101010.

查找并纠错一位错误

上例中构建了一个码字 011100101010,假定实际接收到的数据是011100101110. 则接收方可以计算出哪一位出错并对其进行更正。方法就是验证每一个校验位。记下所有出错的校验位,可以发现校验位2和8的数据不正确. 错误校验位 2 + 8 = 10, 则位置10的数据出错。一般说来,对所有校验位进行检查, 将所有出错的校验位置相加, 得到的就是错误信息所在的位置.

编辑本段4.海明码校验程序设计原理分析参考

海明码校验是为了保证数据传输正确而提出的,本来就是一串要传送的数据,如:D7,D6,D5,D4,D3,D2,D1,D0,这里举的是八位数据,可以是n位数据。就这样传送数据,不知道接收到后是不是正确的。所以,要加入校验位数据才能检查是否出错。这里涉及到一个问题,要多少位校验数据才能查出错误呢?

我们只要能检测出一位出错,则对于8位信息数据,校验位为4位。满足下列条件:2的k次方大于等于n+k+1,其中k为校验位位数,n为信息数据位位数。验证一下,2的4次方等于16,n+k+1等于8+4+1等于13。 8位信息数据与4位校验位总共有12位数据,怎么排列呢?我们先把校验位按P4,P3,P2,P1排列,用通式Pi表示校验位序列,i为校验位在校验序列中的位置。 传送的数据流用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1表示,接下来的问题是如何用D7,D6,D5,D4,D3,D2,D1,D0与P4,P3,P2,P1来表M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1了。校验位在传送的数据流中位置为2的i-1次方,则P1在M1位,P2在M2位,P3在M4位,P4在M8位。其余的用信息数据从高到低插入。 传送的数据流为D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1。 接下来,我们要弄明白如何找出错误位的问题。引进4位校验和序列S4,S3,S2,S1。S4,S3,S2,S1等于0,0,0,0表示传送的数据流正确;如S4,S3,S2,S1等于0,0,1,0则表示传送的数据流中第2位出错;如S4,S3,S2,S1等于0,0,1,1则表示传送的数据流中第3位出错;依次类推。

用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1如何表示S4,S3,S2,S1呢,简单的方法就是S1=1时,S4,S3,S2从0,0,0到1,1,1的所有的Mx异或。即S1等于M1异或M3异或M5异或M7异或M9异或M11。也就是S1等于P1异或D0异或D1异或D3异或D4异或D6。S2=1时,S4,S3,S1从0,0,0到1,1,1的所有的Mx异或。即S2等于M2异或M3异或M6异或M7异或M10异或M11。S3=1时,S4,S2,S1从0,0,0到1,1,1的所有的Mx异或。即S3等于M4异或M5异或M6异或M7异或M12。S4=1时,S3,S2,S1从0,0,0到1,1,1的所有的Mx异或。即S4等于M8异或M9异或M10异或M11异或M12。这样,对于一串码流,知道几位校验位,可以很快确定哪一位出错。而在发送端,可以根据S4,S3,S2,S1的表达式求出P4,P3,P2,P1的表达式,只要把式子右边的P4或P3或P2或P1移到左边替换掉S4或S3或S2或S1就可以了。面举例说明:用^表示异或

D7,D6,D5,D4,D3,D2,D1,D0=11010001

S4=M8^M9^M10^M11^M12=D7^D6^D5^D4^P4; P4=D7^D6^D5^D4;

S3=M4^M5^M6^M7^M12 =D7^D3^D2^D1^P3; P3=D7^D3^D2^D1;

S2=M2^M3^M6^M7^M10^M11 =D6^D5^D3^D2^D0^P2; P2=D6^D5^D3^D2^D0;

S1=M1^M3^M5^M7^M9^M11=D6^D4^D3^D1^D0^P1; P1=D6^D4^D3^D1^D0;

所以,

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

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

P2= D6^D5^D3^D2^D0=1^0^0^0^1=0 P1=D6^D4^D3^D1^D0=1^1^0^0^1=1

故,传送码流为D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1等于

110110001101

若接收端收到110110001101,则

S4=M8^M9^M10^M11^M12=1^1^0^1^1=0

S3=M4^M5^M6^M7^M12=1^0^0^0^1=0

S2=M2^M3^M6^M7^M10^M11=0^1^0^0^0^1=0

S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0

故,接收码流正确。

若M6出错,由0变为1。则

S4=M8^M9^M10^M11^M12=1^1^0^1^1=0

S3=M4^M5^M6^M7^M12=1^0^1^0^1=1

S2=M2^M3^M6^M7^M10^M11=0^1^1^0^0^1=1 S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0

即S4S3S2S1=0110,此为十进制的6,说明第六位出错,也就是M6出错。完全符合。

5.海明码的表格计算

如果对于m位的数据,增加k位冗余位,则组成位n=m+k位的纠错码。对于2^m个有效码字中的每一个,都有n个无效但可以纠错的码字。这些可纠错的码字与有效码字的距离是1,含单个错误位。这样,对于一个有效的消息总共有n+1个可识别的码字。这n+1个码字相对于其他2^m-1个有效消息的距离都大于1。这意味着总共有2^m(n+1)个有效的或是可纠错的码字。显然这个数应小于等于码字的所有的可能的个数2^n。于是我们有

2^m(n+1)2^n

因为n=m+k,我们得出

m+k+12^k

对于给定的数据位m,上式给出了k的下界,即要纠正单个错误,k必须取最小的值。海明建议了一种方案,可以达到这个下界,并能直接指出错在哪一位。首先把码字的位从1到n编号,,并把这个编号表示成二进制数,即2的幂之和。然后对2的每一个幂设置一个奇偶位。例如对于6号位,由于6=110(二进制),所以6号位参加第2位和第4位的奇偶校验,而不参加第1位奇偶校验。类似的9号位参加第1位和第8位的奇偶校验而不参加第2位和第4位的奇偶校验。海明把奇偶校验分配在1,2,4,8等位置上,其他位置放数据。下面根据海明编码的例图,举例说明编码的方法

海明编码的例

海明编码的例

例如传送的消息为:1001011

我们把数据放在3,5,6,7,9,10,11等位置上,1,2,4,8则为校验位。

1

0 0 1

0 1 1

 1 2 3 4 5 6 7 8 9 10 11

根据海明编码的例,3、5、7、9、11的二进制编码的第一位为1,所以3、5、7、9、11号位参加第一位校验位,若按偶校验计算,1号位应为1

1

1

0 0 1

0 1 1

 1 2 3 4 5 6 7 8 9 10 11

类似的,3、6、7、10、11号位参加2号位校验,5、6、7号位参加4号位校验,9、10、11号位参加8号位校验,全部按偶校验计算,最终得到如下结果

1 0 1 1 0 0 1 0 0 1 1

 1 2 3 4 5 6 7 8 9 10 11

如果这个码字传输中有错误,比如说6号位出错。就会变成

√ ╳ ╳ √

1 0 1 1 0 1 1 0 0 1 1

 1 2 3 4 5 6 7 8 9 10 11

当接收端按照同样的规则计算奇偶位时,就会发现1号位和8号位的奇偶性正确而2号位和4号位的奇偶性不对,于是2+4=6,,立即可以判断错在6号位。

上例中k=4,因而m2^4-4-1=11,即数据位可以用到11位,共组成15位的码字,可检测出单个位置的错误。

海明校验码的原理是什么?

海明校验码

这是由Richard Hamming于1950年提出、目前还被广泛采用的一种很有效的校验方法,是只要增加少数几个校验位,就能检测出二位同时出错、亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段,后者被称为自动纠错。它的实现原理,是在k个数据位之外加上r个校验位,从而形成一个k+r位的新的码字,使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中,当某一位出错后,就会引起相关的几个校验位的值发生变化,这不但可以发现出错,还能指出是哪一位出错,为进一步自动纠错提供了依据。

假设为k个数据位设置r个校验位,则校验位能表示2r个状态,可用其中的一个状态指出 “没有发生错误”,用其余的2 r -1个状态指出有错误发生在某一位,包括k个数据位和r个校验位,因此校验位的位数应满足如下关系:

2r ≥ k + r + 1 (2.7)

如要能检出与自动校正一位错,并能同时发现两位错,此时校验位的位数r和数据位的位数k应满足下述关系:

2r-1 ≥ k + r (2.8)

按上述不等式,可计算出数据位k与校验位r的对应关系,如表2.2所示。

表2.2

K值 最小的r值

3-4 4

5-10 5

11-25 6

26-56 7

57-119 8

设计海明码编码的关键技术,是合理地把每个数据位分配到r个校验组中,以确保能发现码字中任何一位出错;若要实现纠错,还要求能指出是哪一位出错,对出错位求反则得到该位的正确值。例如,当数据位为3位(用D3 D2 D1表示)时,检验位应为4位(用P4 P3 P2 P1表示)。可通过表2.3表示的关系,完成把每个数据位划分在形成不同校验位的偶校验值的逻辑表达式中。

表2.3 校验位与数据位的对应关系

在P1、P2、P3、P4竖列相应行分别填1,

在该4列的低3横行其它位置分别填0,

在最顶横行的每个尚空位置都分别填1。

若只看低3横行,右4竖列的3个bit的组合值分别为十进制的1、2、4、0,则分配 D1 D2 D3列的组合值为3 5 6,保证低3横行各竖列的编码值各不相同。

表中D3 D2 D1为三位数据位,P4 P3 P2 P1为四位校验位。其中低三位中的每一个校验位P3 P2 P1的值,都是用三个数据位中不同的几位通过偶校验运算规则计算出来的。其对应关系是:对Pi(i的取值为1~3),总是用处在Pi取值为1的行中的、用1标记出来的数据位计算该Pi的值。最高一个校验位P4,被称为总校验位,它的值,是通过对全部三个数据位和其它全部校验位(不含P4本身)执行偶校验计算求得的。

形成各校验位的值的过程叫做编码,按刚说明的规则,4个校验位所用的编码方程为:

P4 = D3 D2 D1 P3 P2 P1

P3 = D3 D2

P2 = D3 D1

P1 = D2 D1

由多个数据位和多个校验位组成的一个码字,将作为一个数据单位处理,例如被写入内存或被传送走。之后,在执行内存读操作或在数据接收端,则可以对得到的码字,通过偶校验来检查其合法性,通常称该操作过程为译码,所用的译码方程为:

S4 = P4 D3 D2 D1 P3 P2 P1

S3 = P3 D3 D2

S2 = P2 D3 D1

S1 = P1 D2 D1

译码方程和编码方程的对应关系很简单。译码方程,是用一个校验码和形成这个校验码的编码方程执行异或,实际上是又一次执行偶校验运算。通过检查四个S的结果,可以实现检错纠错的的目的。实际情况是,当译码求出来的S4、S3、S2、S1的得值与表2.3中的那一列的值相同,就说明是哪一位出错;故人们又称表2.3为出错模式表。若出错的是数据位,对其求反则实现纠错;若出错的是校验位则不必理睬。举例如下:

任何一位(含数据位、校验位)均不错,则四个S都应为0值;

任何单独一位数据位出错,四个S中会有三个为1;如D3错,则S4 S3 S2 S1为1110。

若单独一位校验位出错,四个S中会有一个或两个为1;如P1错,S4 S3 S2 S1为1001,如P4错,S4 S3 S2 S1为1000。

任何两位(含数据位、校验位)同时出错,S4一定为0,而另外三个S位一定不全为0,此时只知道是两位同时出错,但不能确定是哪两位出错,故已无法纠错。如D1、 P2出错,会使S4 S3 S2 S1为0001。请注意,S4的作用在于区分是奇数位出错还是偶数位出错,S4为1是奇数位错,为0是无错或偶数位错。这不仅为发现两位错所必需,也是为确保能发现并改正一位错所必需的。若不设置S4,某种两位出错对几个S的影响与单独另一位出错可能是一样的(不必花费精力推敲),此时若不加以区分,简单地按一位出错自动完成纠错处理反而会帮倒忙。

;url=http%3A//www%2Etjdlgd%2Ecom/wljs/jc/%BC%C6%CB%E3%BB%FA%D4%AD%C0%ED/text/ch02/se01/part3/r2%5F1%5F3%5F2%5F2%2Ehtmb=0a=44user=baidu

Python基本编码格式

1、一般来说,声明编码格式在脚本中是必需的。2、如果Python源码文件没有声明编码格式,Python解释器会默认使用ASCII编码。但出现非ASCII编码的字符,Python解释器就会报错。

1、Python 采用代码缩进和冒号( : )来区分代码块之间的层次。2、在 Python 中,对于类定义、函数定义、流程控制语句、异常处理语句等,行尾的冒号和下一行的缩进,表示下一个代码块的开始,而缩进的结束则表示此代码块的结束。3、Python 中实现对代码的缩进,可以使用空格或者 Tab 键实现。但无论是手动敲空格,还是使用 Tab 键,通常情况下都是采用 4 个空格长度作为一个缩进量(默认情况下,一个 Tab 键就表示 4 个空格)。4、对于 Python 缩进规则,初学者可以这样理解,Python 要求属于同一作用域中的各行代码,它们的缩进量必须一致,但具体缩进量为多少,并不做硬性规定。

正确示例代码:

错误示例代码:

Python中使用 # 进行注释,我们在使用# 的时候,# 号后面要空一格在行内注释的时候,中间应该至少加两个空格

print(“你好,世界”) # 注释

** 使用的一般性原则:**

1、在二元运算符两边各空一格,算术操作符两边的空格可灵活使用,但两侧务必要保持一致2、不要在逗号、分号、冒号前面加空格,但应该在它们后面加(除非在行尾)3、函数的参数列表中,逗号之后要有空格4、函数的参数列表中,默认值等号两边不要添加空格5、左括号之后,右括号之前不要加添加空格6、参数列表, 索引或切片的左括号前不应加空格

使用的一般性原则:

1、编码格式声明、模块导入、常量和全局变量声明、顶级定义和执行代码之间空两行2、顶级定义之间空两行,方法定义之间空一行3、在函数或方法内部,可以在必要的地方空一行以增强节奏感,但应避免连续空行

1、导入总应该放在文件顶部,位于模块注释和文档字符串之后,模块全局变量和常量之前。

2、导入应该按照从最通用到最不通用的顺序分组,分组之间空一行:

3、每个 import 语句只导入一个模块,尽量避免一次导入多个模块

命名规范这一块的大家应该都比较熟悉了,但是不同的编程语言之间的明明规范也是有所区别的~

Python命名建议遵循的一般性原则:

引号使用的一般性原则:

Python跟其他几个主流编程语言的分号使用区别很大Python的代码末尾不需要加分号,而Java和C#等都需要添加

不要在行尾添加分号,也不要用分号将两条命令放在同一行,例如:

Python学习日记

原创文章,作者:FOJYC,如若转载,请注明出处:https://www.506064.com/n/127459.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
FOJYC的头像FOJYC
上一篇 2024-10-03 23:15
下一篇 2024-10-03 23:15

相关推荐

发表回复

登录后才能评论