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

2024-04-12 08:28

本文主要是介绍链路层分组汉明码纠错计算原理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 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

Spring @Scheduled注解及工作原理

《Spring@Scheduled注解及工作原理》Spring的@Scheduled注解用于标记定时任务,无需额外库,需配置@EnableScheduling,设置fixedRate、fixedDe... 目录1.@Scheduled注解定义2.配置 @Scheduled2.1 开启定时任务支持2.2 创建

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源

Python并行处理实战之如何使用ProcessPoolExecutor加速计算

《Python并行处理实战之如何使用ProcessPoolExecutor加速计算》Python提供了多种并行处理的方式,其中concurrent.futures模块的ProcessPoolExecu... 目录简介完整代码示例代码解释1. 导入必要的模块2. 定义处理函数3. 主函数4. 生成数字列表5.

Python中使用uv创建环境及原理举例详解

《Python中使用uv创建环境及原理举例详解》uv是Astral团队开发的高性能Python工具,整合包管理、虚拟环境、Python版本控制等功能,:本文主要介绍Python中使用uv创建环境及... 目录一、uv工具简介核心特点:二、安装uv1. 通过pip安装2. 通过脚本安装验证安装:配置镜像源(可

Java反射实现多属性去重与分组功能

《Java反射实现多属性去重与分组功能》在Java开发中,​​List是一种非常常用的数据结构,通常我们会遇到这样的问题:如何处理​​List​​​中的相同字段?无论是去重还是分组,合理的操作可以提高... 目录一、开发环境与基础组件准备1.环境配置:2. 代码结构说明:二、基础反射工具:BeanUtils

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意