链路层分组汉明码纠错计算原理Hamming Code - data link

2024-04-12 08:28
文章标签 计算 分组 原理 code 链路层 link data 纠错 hamming 汉明码

本文主要是介绍链路层分组汉明码纠错计算原理Hamming Code - data link，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.以下在接收方接收分组时候产品随即一位错误情况:

Enter the data[max:30]:10101000111
Sender: send data:  10101000111 [Hamming code count:4]
data_with position: __1_010_1000111
datar with Hamming: 001001001000111
Receiver get data:     001001001010111
Receiver: data invalid![1011]
Receiver revise data:001001001000111

B.以下是在接收方接收分组正确情况:

Enter the data[max:30]:10100101011
Sender: send data:  10100101011 [Hamming code count:4]
data_with position: __1_010_0101011
datar with Hamming: 011001000101011
Receiver get data:     011001000101011
Receiver: data valid!
 

/*Hamming code* 汉明码通过在分组中添加冗余校验码来实现差错检测和纠正* 实现原理是通过对与某个校验码对应的比特组进行奇偶校验* 其主要的步骤包括:* 1.计算冗余码个数 pow(2,r) >= d + r + 1.  * 注:r代表冗余码数量,d代表分组比特数)* 2.确定冗余码位置. * 注:汉明码校验码对应的位置值转化为二进制后类似于(0001,0010,0100..)*    即2的0次幂,2的1次幂,2的2次幂...* 3.确定冗余码值* 注:冗余码比特值是为了确保该值与同组中的比特值求异或后结果为0*    而组中的成员比特的位置选择遵循以下规则:*    同组比特位对应的二进制与对应冗余码二进制进行求或操作后依然为原值.*    例如: 比特位a对应位置是11(二进制1011) * 		    比特位b对应位置是6(二进制110）*         汉明码h位置1(二进制0001)*    a|h -> 1011 | 0001 = 1011(a位置) 则a位置与汉明码h为同组*    b|h -> 110  | 0001 = 111(非b位置) 则b位置与汉明码不为同组*  4.接收方校验和纠错*    注:接收方通过对冗余码从高位到低位的顺序对分组进行校验,*    如果某组得到结果值为1则说明该组有误,由于不同组存在交叉检验比特位情况,*    这样即能得到错误位置的二进制.*    如:汉明码有4位,则0000代表正确,如0110(高位到低位)则说明第6位比特值有误,将其取反即可* * 注:汉明码只能发现和修正一位错误，对于两位或者两位以上的错误无法正确和发现.*    所以有时候会把大的分组进行拆分，通过对拆分后的组进行对应的汉明码查错和纠错* */#include <math.h>#include <string.h>#include <stdlib.h>#include <stdio.h>#include <stdbool.h>#include <regex.h>#include <assert.h>#include <time.h>typedef int errno_t;//functions prototype//步骤1: 计算校验码个数int nHammingCode(char* data);//步骤2 步骤3:将汉明码插入数据并赋值char* insertHammingCode(int r,char* data);//步骤4:接收方查错纠错bool checkData(char* datar,int r,char** wrongIndex);//检测输入分组有效性bool valid(char* data);//接收方收到无效数据后修纠错void revise(char* datar,char* wrongIndex);//辅助方法.二进制字符串转int
int sbtoi(char* sb);//辅助函数,用于寻找下一个匹配正则的位置.无匹配返回-1
int regNextMatchIndex(regex_t* regex,char* content);int main(void){char* data = calloc(31,sizeof(char));retry:printf("Enter the data[max:30]:");scanf("%s",data);errno_t state = valid(data);if(state == false){printf("data: %s\n",data);goto retry;}int r = nHammingCode(data);printf("Sender: send data:  %s ",data);printf("[Hamming code count:%d]\n",r);char* datar = insertHammingCode(r,data);printf("datar with Hamming: %s\n",datar);//这里上分组随机产生一位错误
#define WRONG_TEST
#undef WRONG_TEST  //这里作为一个开关.注释则产生一位随即错误
#ifdef WRONG_TESTsrand(time(NULL));int wrong = rand() % (strlen(datar) - 1);datar[wrong] = (datar[wrong] == '1' ? '0' : '1');
#endifchar* wrongIndex = NULL;bool check = checkData(datar,r,&wrongIndex);if(!check){printf("Receiver: data invalid![%s]\n",wrongIndex);revise(datar,wrongIndex);}else{printf("Receiver: data valid!\n");}return 0;
}int nHammingCode(char* data){int r = 1;int d = strlen(data);for(;pow(2,r) < d + r + 1;r ++);return r;//返回冗余码个数
}char* insertHammingCode(int r,char* data){//在对应位置插入汉明冗余码并赋值char* datar = calloc(strlen(data) + r + 1,sizeof(char));memcpy(datar,data,strlen(data));int index = 0;int n = 5;//n代表index转化为字符串后的长度.这里直接设置成5位char* pattern = calloc(11 + n + 1,sizeof(char));regex_t regex;errno_t state = 0;regmatch_t matches[3];//这里已知后续正则表达式直接赋值3char* head = NULL;char* tail = NULL;for(int i = 0 ; i < r ; i ++){index = pow(2,i) - 1;//指针偏移量的位置-1memset(pattern,0,11 + n + 1);//清空pattern内存sprintf(pattern,"^(.{%d})(.*)$",index);state = regcomp(&regex,pattern,REG_EXTENDED);if(state){char* errbuf = calloc(50,sizeof(char));regerror(state,&regex,errbuf,50);fprintf(stderr,"Failed to compile Regex:%s\n""Reason: %s\n",pattern,errbuf);free(errbuf);regfree(&regex);exit(EXIT_FAILURE);}state = regexec(&regex,datar,3,matches,0);assert(state == 0);head = calloc(matches[1].rm_eo - matches[1].rm_so + 1,sizeof(char));tail = calloc(matches[2].rm_eo - matches[2].rm_so + 1,sizeof(char));memcpy(head,datar + matches[1].rm_so,matches[1].rm_eo - matches[1].rm_so);memcpy(tail,datar + matches[2].rm_so,matches[2].rm_eo - matches[2].rm_so);memcpy(datar,head,strlen(head));memcpy(datar + strlen(head),"_",1);memcpy(datar + strlen(head) + 1,tail,strlen(tail));free(head);free(tail);regfree(&regex);}printf("data_with position: %s\n",datar);//找出对应的校验码位置并用下横线标注//以下采用一种比较低效的方法对汉明校验码进行赋值int counts[r];memset(counts,0,r * sizeof(int));int indexs[r];memset(indexs,0,r * sizeof(int));for(int i = 0 ; i < r ; i ++){indexs[i] = pow(2,i);}for(int i = 0 ; i < strlen(datar) ; i ++){for(int j = 0 ; j < r ; j ++){if((i + 1) == indexs[j]){//printf("位置:%d不检测.\n",i + 1);continue;}if(((i + 1) | indexs[j]) ==  (i + 1)){//printf("校验码:%d,校验data坐标:%d 值:%c\n",j+1,i+1,datar[i]);if(datar[i] == '1'){counts[j] ++;}}}}for(int i = 0 ; i < r ; i ++){//printf("第%d个检验码,count:%d\n",i + 1,counts[i]);datar[indexs[i] - 1] = (counts[i] % 2 == 0) ? '0' : '1';}//printf("datar: %s\n",datar);return datar;
}bool checkData(char* datar,int r,char** wrongIndex){//步骤4:接收方查错纠错printf("Receiver get data:  %s\n",datar);int indexs[r];int counts[r];*wrongIndex = calloc(r,sizeof(char));memset(counts,0,sizeof(int) * r);for(int i = 0 ; i < r ; i ++){indexs[i] = pow(2,i);}for(int i = 0 ; i < strlen(datar) ; i ++){for(int j = 0 ; j < r ; j ++){if(((i + 1) | indexs[j]) == (i + 1)){//printf("校验码:%d,校验data坐标:%d 值:%c\n",j+1,i+1,datar[i]);if(datar[i] == '1'){counts[j] ++;}}}}bool reval = true;int remainder = 0;for(int i = 0 ; i < r ; i ++){//printf("第%d个检验码,count:%d\n",i + 1,counts[i]);remainder = counts[i] % 2;if(remainder){reval = false;}(*wrongIndex)[r-i - 1] = (remainder == 0 ? '0' : '1');}return reval;
}void revise(char* datar,char* wrongIndex){int index = sbtoi(wrongIndex) - 1;datar[index] = (datar[index] == '1' ? '0' : '1');printf("Receiver revise data:%s\n",datar);
}//辅助方法.二进制字符串转int
int sbtoi(char* sb){regex_t regex;char* pattern = "^[01]+$";errno_t state = regcomp(&regex,pattern,REG_EXTENDED);assert(state == 0);state = regexec(&regex,sb,0,NULL,0);if(state == REG_NOMATCH){fprintf(stderr,"Invalid bit str:%s\n",sb);exit(EXIT_FAILURE);}regfree(&regex);int reval = 0;int len = strlen(sb);pattern = "1";state = regcomp(&regex,pattern,REG_EXTENDED);assert(state == 0);int index = 0;int exponent = 0;while((index = regNextMatchIndex(&regex,sb)) != -1){exponent = len - 1 - index;reval += pow(2,exponent);}regfree(&regex);return reval;
}//辅助函数,用于寻找下一个匹配正则的位置.无匹配返回-1
int regNextMatchIndex(regex_t* regex,char* content){static int position = 0;regmatch_t matches[regex->re_nsub + 1];errno_t state = regexec(regex,content + position,regex->re_nsub + 1,matches,0);if(state == REG_NOMATCH){position = 0;return -1;}int reval = position + matches[0].rm_so;position += matches[0].rm_eo;return reval;
}bool valid(char* data){if(strlen(data) > 30){fprintf(stderr,"MAX: 30 < Len: %zd >>",strlen(data));return false;}regex_t regex;char* pattern = "^[01]+$";errno_t state = regcomp(&regex,pattern,REG_EXTENDED);if(state){char* errbuf = calloc(50,sizeof(char));regerror(state,&regex,errbuf,50);fprintf(stderr,"Failed to compile Regex:%s\n""Reason:%s\n",pattern,errbuf);free(errbuf);regfree(&regex);exit(EXIT_FAILURE);}state = regexec(&regex,data,0,NULL,0);if(state == REG_NOMATCH){fprintf(stderr,"Content Invalid. >>");return false;}return true;
}

这篇关于链路层分组汉明码纠错计算原理Hamming Code - data link的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/896609。

相关文章

Java编译生成多个.class文件的原理和作用

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类（常规内部类）局部内部类（方法内部类）匿名内部类二、
阅读更多...
Python中随机休眠技术原理与应用详解

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2
阅读更多...
Java的IO模型、Netty原理解析

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容：标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO（blocking I/O）NI
阅读更多...
JAVA封装多线程实现的方式及原理

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》：本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中，封装多线程的原理主要围绕着将多线程相关的操
阅读更多...
kotlin中的模块化结构组件及工作原理

kotlin中的模块化结构组件及工作原理

《kotlin中的模块化结构组件及工作原理》本文介绍了Kotlin中模块化结构组件,包括ViewModel、LiveData、Room和Navigation的工作原理和基础使用,本文通过实例代码给大家... 目录ViewModel 工作原理LiveData 工作原理Room 工作原理Navigation 工
阅读更多...
Java的volatile和sychronized底层实现原理解析

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente
阅读更多...
MySQL的隐式锁(Implicit Lock)原理实现

MySQL的隐式锁(Implicit Lock)原理实现

《MySQL的隐式锁(ImplicitLock)原理实现》MySQL的InnoDB存储引擎中隐式锁是一种自动管理的锁,用于保证事务在行级别操作时的数据一致性和安全性,本文主要介绍了MySQL的隐式锁... 目录1. 背景：什么是隐式锁？2. 隐式锁的工作原理3. 隐式锁的类型4. 隐式锁的实现与源代码分析4
阅读更多...
MySQL中Next-Key Lock底层原理实现

MySQL中Next-Key Lock底层原理实现

《MySQL中Next-KeyLock底层原理实现》Next-KeyLock是MySQLInnoDB存储引擎中的一种锁机制,结合记录锁和间隙锁,用于高效并发控制并避免幻读,本文主要介绍了MySQL中... 目录一、Next-Key Lock 的定义与作用二、底层原理三、源代码解析四、总结Next-Key L
阅读更多...
HTML5 data-*自定义数据属性的示例代码

HTML5 data-*自定义数据属性的示例代码

《HTML5data-*自定义数据属性的示例代码》HTML5的自定义数据属性（data-*）提供了一种标准化的方法在HTML元素上存储额外信息,可以通过JavaScript访问、修改和在CSS中使用... 目录引言基本概念使用自定义数据属性1. 在 html 中定义2. 通过 JavaScript 访问3.
阅读更多...
Spring Cloud Hystrix原理与注意事项小结

Spring Cloud Hystrix原理与注意事项小结

《SpringCloudHystrix原理与注意事项小结》本文介绍了Hystrix的基本概念、工作原理以及其在实际开发中的应用方式,通过对Hystrix的深入学习,开发者可以在分布式系统中实现精细... 目录一、Spring Cloud Hystrix概述和设计目标（一）Spring Cloud Hystr
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2