链路层分组汉明码纠错计算原理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。

相关文章

使用C#代码计算数学表达式实例

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长，因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如
阅读更多...
Redis主从/哨兵机制原理分析

Redis主从/哨兵机制原理分析

《Redis主从/哨兵机制原理分析》本文介绍了Redis的主从复制和哨兵机制,主从复制实现了数据的热备份和负载均衡,而哨兵机制可以监控Redis集群,实现自动故障转移,哨兵机制通过监控、下线、选举和故... 目录一、主从复制1.1 什么是主从复制1.2 主从复制的作用1.3 主从复制原理1.3.1 全量复制
阅读更多...
Redis主从复制的原理分析

Redis主从复制的原理分析

《Redis主从复制的原理分析》Redis主从复制通过将数据镜像到多个从节点,实现高可用性和扩展性,主从复制包括初次全量同步和增量同步两个阶段,为优化复制性能,可以采用AOF持久化、调整复制超时时间、... 目录Redis主从复制的原理主从复制概述配置主从复制数据同步过程复制一致性与延迟故障转移机制监控与维
阅读更多...
SpringCloud配置动态更新原理解析

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R
阅读更多...
Redis主从复制实现原理分析

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实
阅读更多...
使用C#如何创建人名或其他物体随机分组

使用C#如何创建人名或其他物体随机分组

《使用C#如何创建人名或其他物体随机分组》文章描述了一个随机分配人员到多个团队的代码示例,包括将人员列表随机化并根据组数分配到不同组,最后按组号排序显示结果... 目录C#创建人名或其他物体随机分组此示例使用以下代码将人员分配到组代码首先将lstPeople ListBox总结C#创建人名或其他物体随机分组
阅读更多...
如何用Java结合经纬度位置计算目标点的日出日落时间详解

如何用Java结合经纬度位置计算目标点的日出日落时间详解

《如何用Java结合经纬度位置计算目标点的日出日落时间详解》这篇文章主详细讲解了如何基于目标点的经纬度计算日出日落时间,提供了在线API和Java库两种计算方法,并通过实际案例展示了其应用,需要的朋友... 目录前言一、应用示例1、天安门升旗时间2、湖南省日出日落信息二、Java日出日落计算1、在线API2
阅读更多...
TP-LINK/水星和hasivo交换机怎么选? 三款网管交换机系统功能对比

TP-LINK/水星和hasivo交换机怎么选? 三款网管交换机系统功能对比

《TP-LINK/水星和hasivo交换机怎么选?三款网管交换机系统功能对比》今天选了三款都是”8+1″的2.5G网管交换机，分别是TP-LINK水星和hasivo交换机，该怎么选呢？这些交换机功... TP-LINK、水星和hasivo这三台交换机都是”8+1″的2.5G网管交换机，我手里的China编程has
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2