汉明码-程序员宅基地

技术标签： 算法  

7，4汉明码及8，4扩展汉明码的实现

  (2012-12-16 15:32:02)
标签： 

fpga

 

扩展汉明码

 分类： FPGA


一、汉明码

    汉明码是 1950 年由美国贝尔实验室提出来的，是第一个设计用来纠正错误的线性分组码

，汉明码及其变型已广泛应用于数字通信和数据存储系统中作为差错控制码。

　　汉明码是一种线性分组码。线性分组码是指将信息序列划分为长度为k的序列段，在每一段后面附加r位的监督码，且监督码和信息码之间构成线性关系，即它们之间可由线性方程组来联系。这样构成的抗干扰码称为线性分组码。 

编码原理

　　设码长为n，信息位长度为k，监督位长度为r=n-k。如果需要纠正一位出错，因为长度为n的序列上每一位都可能出错，一共有n种情况，另外还有不出错的情况，所以我们必须用长度为r的监督码表示出n+1种情况。而长度为r的监督码一共可以表示2^r种情况。因此 

　　2^r >= n + 1， 即r >= log(n+1) 

　　我们以一个例子来说明汉明码。假设k=4，需要纠正一位错误，则 

　　2^r >= n + 1 = k + r + 1 = 4 + r + 1 

　　解得r >= 3。我们取r=3，则码长为3+4=7。用a6,a5,...a0表示这7个码元。用S1,S2,S3表示三个监关系式中的校正子。我们作如下规定（这个规定是任意的）： 

　　S1 S2 S3 错码的位置 

　　0  0  1   a0 

　　0  1  0   a1 

　　1  0  0   a2 

　　0  1  1   a3 

　　1  0  1   a4 

　　1  1  0   a5 

　　1  1  1   a6 

　　0  0  0   无错 

　　按照表中的规定可知，仅当一个错码位置在a2,a4,a5或a6时校正子S1为1，否则S1为0。这就意味着a2,a4,a5,a6四个码元构成偶校验关系： 

　　S1 = a6⊕a5⊕a4⊕a2 (1)式 

　　同理，可以得到： 

　　S2 = a6⊕a5⊕a3⊕a1 (2)式 

　　S3 = a6⊕a4⊕a3⊕a0 (3)式 

　　在发送信号时，信息位a6,a5,a4,a3的值取决于输入信号，是随机的。监督为a2,a1,a0应该根据信息位的取值按照监督关系决定，即监督位的取值应该使上述(1)(2)(3)式中的S1,S2,S3为0，这表示初始情况下没有错码。即 

　　S1=a6⊕a5⊕a4⊕a2 = 0 

　　S2=a6⊕a5⊕a3⊕a1 = 0 

　　S3=a6⊕a4⊕a3⊕a0 = 0 

　　由上式进行移项运算，得到： 

　　a2 = a6⊕a5⊕a4 

　　a1 = a6⊕a5⊕a3 

　　a0 = a6⊕a4⊕a3 

　　已知信息位后，根据上式即可计算出a2,a1,a0三个监督位的值。 

 

监督位计算结果

 

序

号

码   字

序

号

码   字

信 息码元

监 督 元

信 息码元

监 督 元

0

0  0  0  0

0  0  0

8

1  0  0  0

1  1  1

1

 0  0  0  1

0  1  1

9

1  0  0  1

1  0  0

2

 0  0  1  0

1  0  1

10

1  0  1  0

0  1  0

3

0  0  1  1

1  1  0

11

1  0  1  1

0  0  1

4

0  1  0  0

1  1  0

12

 1  1  0  0

0  0  1

5

0  1  0  1

1  0  1

13

 1  1  0  1

0  1  0

6

0  1  1  0

0  1  1

14

 1  1  1  0

1  0  0

7

0  1  1  1

0  0  0

15

 1  1  1  1

1  1  1

                        表3-1-1

　　接收端受到每个码组后，先按照(1)~(3)式计算出S1,S2,S3，（或查表）


然后查表可知错码情况。 

 它能纠1个错或检2个错。


纠一：

例如接收端 收到的信息是  1101100，

则可以算出 S1=1， S2=1， S3=0，   查表可知错误位置a5, ,将a5改正过后

 

得到正确的 信息应该是 1001100.

检二：

汉明码仅能纠正一位错码,如果要实现检出 2位错码的功能,可以采用扩展汉明码。扩展汉明码

是在汉明码的基础上增加了一位偶校验码, 如 ( 7 ,4)汉明码增加一位就变成 ( 8 , 4)扩展汉明码。下面

以( 8 , 4)汉明码为例说明其编译码原理。( 7 , 4)汉明码的码位排列为: a7a6a5a4a3a2a1,

其中 a7a6a5a4信息位, a3a2a1为监督位, 增加一位后的( 8 , 4)汉明码排列为: a7a6a5a4a3a2a1a0 , a0为前面 7位码的偶校验位。

扩展汉明码可以纠正 1位错码, 还可以检出 2位错码。

：解码器通过对接收到的信息位

再编码产生本地监督位和一位总体校验位, 然后再与接

收到的编码器发送来的原监督位和总体校验位进行比

较( 分别异或) ,

     通 过对产生的结果进行分析, 从而判断是否有误, 并且通过变量error 的取值来确定错误的类型。
7，4汉明码及8，4扩展汉明码的实现




FPGA verilog 的实现

(n，k)模式线性分组码的生成矩阵G和校验

矩阵H分别为，n×k和n×(n—k)维矩阵，其中，

校验矩阵H决定信息位与校验位的关系，在编码和

译码中都要用到。

 线性码的最小码距为d，也即校 验矩阵H中任意d一1列线性无关。


校验矩阵7*（7-4）

7，4汉明码及8，4扩展汉明码的实现

(7,4)码的最小码距d0=3

生成矩阵7*4

7，4汉明码及8，4扩展汉明码的实现
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/malinchong313/article/details/48129217

智能推荐

计算机组成原理 练习卷 第2章第1节数据与文字的表示方法（解析版）（正确答案版）-程序员宅基地

文章浏览阅读412次。计算机组成原理 练习卷 第2章第1节数据与文字的表示方法（解析版）（正确答案版）

WAP 中 AS 和 PSK 模式的认证_静态psk认证是什么意思-程序员宅基地

文章浏览阅读4.5k次，点赞3次，收藏15次。参考《无线网络技术–原理，安全及编程》本博文是期末复习总结，参考了学校老师还未出版的教材，仅供学习使用。PSK 模式PSK 是我们传统的连接无线路由器的认证方式，及无线路由器管理员事先设置统一的连接密码，其他接入者同这个密码进行连接。1.基本过程由 AP 生成临时值 ANonce 发给 STASTA 完成下列计算*1）.STA 生成临时值 SNonce*2）.STA ......_静态psk认证是什么意思

ANSYS_APDL——实例001-模态分析_apdl模态分析-程序员宅基地

文章浏览阅读4k次。学习APDL无从下手，怎么办，就从实例出发，一点一点了解/clear/prep7et,1,solid186mp,ex,1,2e11 !mp后面都为材料参数mp,prxy,1,0.3mp,dens,1,7800block,0,0.01, 0,0.01, 0,0.1 !创建体，基于工作平面，x1，x2，y1，y2，z1，z2lesize,1,,,3 !将编号为1的线划分为3份，lesize,2,,,3 !将编号为2的线划分3份 lesize,9,,,15 !将编号为9的线划分15份m_apdl模态分析

MySQL常用应用函数笔记-程序员宅基地

文章浏览阅读418次，点赞14次，收藏12次。MySQL常用分组拼接函数与时间函数

解决Dbeaver连接一段时间不操作后断开的问题_dbeaver自动断开连接-程序员宅基地

文章浏览阅读1.3k次。2、点击【初始化】将【连接保持】改成60s，这样数据库就不会自己断开了。1、首先右键数据库连接点击【编辑连接】_dbeaver自动断开连接

单片机项目分享 基于ESP32的在线墨水屏桌面摆件 -物联网 单片机 嵌入式-程序员宅基地

文章浏览阅读916次，点赞21次，收藏20次。 这两年开始毕业设计和毕业答辩的要求和难度不断提升，传统的毕设题目缺少创新和亮点，往往达不到毕业答辩的要求，这两年不断有学弟学妹告诉学长自己做的项目系统达不到老师的要求。为了大家能够顺利以及最少的精力通过毕设，学长分享优质毕业设计项目，今天要分享的是基于STM32自行车智能无线防盗报警器学长这里给一个题目综合评分(每项满分5分)难度系数：3分工作量：4分创新点：4分。

随便推点

自习室预约小程序有哪些功能？_自习室小程序-程序员宅基地

文章浏览阅读1.5k次。有了自习室小程序，要查看附近有哪些自习室，直接在微信打开附近的小程序，周边自习室一览无遗；想要查看附近有哪些自习室，打开附近的小程序，立即锁定最近的自习室，即使你的店在最偏僻的角落，只要附近有人，用户打开小程序就能看到你的自习室。微信小程序的活跃用户非常的多，自习室门店利用所开发的小程序，帮助店铺获得更多的客源。自习室预约服务就是用户在使用小程序在线订场服务，在小程序中，可以直观的看到自习室的预约情况、预约费用，然后在线缴付订金。还可以邀请小伙伴一起组队，只需要几分钟就能完成整个预约过程。..._自习室小程序

如何完整卸载wxpython_wxpython学习笔记-程序员宅基地

文章浏览阅读442次。一、简介wxPython是Python编程语言的一个GUI工具箱。他使得Python程序员能够轻松的创建具有健壮、功能强大的图形用户界面的程序。它是Python语言对流行的wxWidgets跨平台GUI工具库的绑定。而wxWidgets是用C++语言写成的。和Python语言与wxWidgets GUI工具库一样，wxPython是开源软件。这意味着任何人都可以免费地使用它并且可以查看和修改它的源..._如何卸载wxauto库

3、apache-kylin-3.1.3-bin-hadoop3基本操作(创建model和cube、数据查詢)-程序员宅基地

文章浏览阅读2.5w次。本文简单的介绍了kylin的基本使用示例，也给出了hive和kylin的使用比较。本文中第一个示例详细的介绍了kylin的使用步骤，以及与hive的使用简单对比；第二个示例单独的使用kylin来实现，仅仅给出了最后一个示例的hive执行时间的对比。本文依赖hive环境好用、kylin环境好用。本文部分数据来源于互联网。_apache-kylin-3.1.3-bin-hadoop3基本操作(创建model和cube、数据查詢

sentinel 限流算法，方式 漏桶，令牌桶 限流，降级，熔断_sentinel 限流原理 令牌桶 漏桶-程序员宅基地

文章浏览阅读690次，点赞6次，收藏3次。Sentinel 是阿里巴巴开源的一个流量控制、熔断降级组件，主要用于微服务架构中的服务保护。Sentinel 提供了多种限流算法和策略，其中与限流相关的算法包括漏桶算法和令牌桶算法。同时，Sentinel 还支持降级和熔断机制，以应对系统的不同压力情况。_sentinel 限流原理 令牌桶 漏桶

【UAV】基于李亚普诺夫的跟踪和动态编队控制实现水下勘探的先进AUV控制方法附matlab代码-程序员宅基地

文章浏览阅读1.2k次，点赞38次，收藏22次。随着海洋科学研究和资源开发的不断深入，水下自主航行器（AUV）作为一种重要的海洋装备，在海洋勘探、水下作业和科学研究等领域发挥着越来越重要的作用。AUV 的控制技术是实现其自主航行和完成任务的关键，而基于李亚普诺夫的跟踪和动态编队控制方法是 AUV 控制领域的研究热点之一。基于李亚普诺夫的跟踪和动态编队控制方法是 AUV 控制领域的研究热点之一，具有鲁棒性强、易于实现等优点，在水下勘探中具有广泛的应用前景。

ELK之elasticsearch导致CPU居高不下系统慢解决办法-程序员宅基地

文章浏览阅读1.4k次。　　参考：http://zoufeng.net/2018/07/16/cpu-of-elasticsearch-high-search-slow/　　elasticsearch主机CPU居高不下100%左右并且一直维持高CPU利用水平　　修改配置文件/etc/elasticsearch/jvm.options　　-Xms1g-Xmx1g改成..._线上elk导致cpu

推荐文章

热门文章

相关标签