【计算机网络】循环冗余校验:Cyclic Redundancy Check

1. 任务目标

利用循环冗余校验(CRC)检测错误。

循环冗余校验(英语:Cyclic redundancy check,通称 CRC)是一种根据网上数据包或计算机文件等数据产生简短固定位数校验码的一种散列函数,主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面,然后接收方进行检验确定数据是否发生变化。一般来说,循环冗余校验的值都是32位的整数。由于本函数易于用二进制的计算机硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误,因此获得广泛应用。此方法是由W. Wesley Peterson于1961年发表。

2. 需要编写的程序

crc_encoder:利用 CRC 将数据字转换为码字。

crc_decoder:在恢复数据字的同时,检测是否存在错误。

3. 详细说明(请仔细阅读并按照指示实现)

3.1. crc_encoder

(1) crc_encoder 应按以下方式运行

./crc_encoder input_file output_file generator dataword_size

要传递给程序的参数有4个,如下所示:

  • input_file:要传输的文件
  • output_file:用CRC编码的要传输的文件
  • generator:CRC的生成多项式
  • dataword_size:数据字的大小。在 crc_encoder 中,应将文件划分为数据字的大小,并将每个数据字转换为码字,单位为 bit。

如果参数数量不匹配,则输出以下消息并退出,usage:

./crc_encoder input_file output_file generator dataword_size

(2) 如果无法打开 input_file,则输出以下消息并退出:

input file open error.

(3) 如果无法打开 output_file,则输出以下消息并退出:

output file open error.

dataword_size 只支持 4 或 8。如果不是 4 或 8,则输出以下消息并退出。 

dataword size must be 4 or 8.

(5) crc_encoder 将从输入文件中读取的数据分割为 dataword 大小。

  • 举个例子,假设输入文件中只有一个字符 'A'。'A' 的 ASCII 码为 65,在二进制中表示为 01000001。因此,第一个 dataword 是 '0100',第二个 dataword 是 '0001'。

(6) 将每个 dataword 转换为 codeword。为此,执行如下的模二除法以获得余数。

  • 假设程序的参数中给定的 generator 是 '1101'。
  • 第一个 dataword 是 '0100'。
  • 由于 generator 是四位数,所以在 dataword 后面添加 '000'。
  • 使用模二除法将 '0100000' 除以 '1101'。

  • 余数为 '011',因此将其附加在 dataword 后面以生成 codeword。
  • dataword '0100' 的 codeword 是 '0100011'。
  • 其余的 dataword 也以相同的方式转换为 codeword。

(7) 使用 CRC 转换后的 codeword 必须写入输出文件。然而,一个问题是,由于 codeword 不是 8 的倍数,所以文件大小可能不会以字节为单位对齐。

  • 例如,一个由一个字符 'A' 组成的文件的内容是 8 位,但是使用 4 位的生成器将其转换为 codeword 后,总共有 14 位。由于文件是按字节写入的,因此需要将其转换为 16 位(2 字节),为此使用零填充。

填充可以放在前面或后面,这里选择放在前面。

  • 将 'A' 按照 4 位一组转换为 codeword 后得到 '01000110001101'。因此,需要添加两位填充,以使其达到 16 位,因此在前面添加两个零。结果是 '0001000110001101'。前两位不是 codeword 的位,而是填充位。

接收者需要对编码文件进行解码,为此需要知道填充位的数量。因此,将输出文件的第一个字节设置为表示填充位数量的字节。

在上述示例中,由于填充位数量为 2,因此输出文件的第一个字节为 '00000010'。

因此,一个由一个字符 'A' 组成的输入文件经过 crc_encoder 程序处理后,输出文件的内容如下。这里使用二进制表示值。

00000010 00010001 10001101 

3.2 cre_decoder

(1) crc_decoder 应按以下方式运行:

./crc_decoder input_file output_file result_file generator dataword_size 

程序的参数总共有 5 个,如下所示:

  • input_file:经过 CRC 编码的文件
  • output_file:删除 CRC 并恢复原始数据的文件
  • result_file:显示总帧数和出错帧数的文件
  • generator:CRC 的生成器
  • dataword_size:dataword 的大小,单位是 bit。

如果参数数量不匹配,则输出以下消息并退出:

usage: ./crc_decoder input_file output_file result_file generator dataword_size

(2) 如果无法打开 input_file,则输出以下消息并退出:

input file open error.

(3) 如果无法打开 output_file,则输出以下消息并退出:

output file open error.

(4) 如果无法打开 result_file,则输出以下消息并退出:

result file open error.

(5) 如果 dataword_size 不是 4 或 8,则输出以下消息并退出:

dataword size must be 4 or 8.

(6) 首先,crc_decoder 读取输入文件的第一个字节以确定填充的大小。

(7) 然后,crc_decoder 从第二个字节中移除填充。

(8) 接下来,将剩余的位数按照 codeword 的大小进行划分。

  • 例如,如果输入文件是 '00000010 00010001 10001101',则从第一个字节得知填充大小为 2 位。然后,忽略第二个字节的前两位 '00',然后将剩余位数划分为 codeword。这样就得到了两个 codeword,'0100011' 和 '0001101'。

(9) 对于每个 codeword,使用生成器进行模二除法,以确定是否存在错误。记录总的 codeword 数量和出现错误的 codeword 数量。

(10) 无论 codeword 是否存在错误,都将其恢复为 dataword 并写入输出文件。

(11) 在结果文件中记录总的 codeword 数量和出现错误的 codeword 数量。例如,如果总的 codeword 数量为 23 个,其中有 5 个出现错误,则结果文件应该写入一行,如下所示:

23 5
  • 首个填充字节和填充位不包含在总的 codeword 数量或有错误的 codeword 数量中。

3.3. linksim

linksim 是以二进制格式提供的程序,而不是作为作业要求实现的程序。

要运行 linksim,执行以下操作:

./linksim inputfile outputfile error_ratio(0-1) seed_num

input file 是经过介质传输之前的文件,而 output file 是经过介质传输后的文件。

error_ratio 表示每个比特的错误率。例如,如果 error_ratio 为 0.1,则表示每个比特出现错误的概率为 10%。error_ratio 的取值范围应为 0 到 1 之间。

seed_num 是随机数生成器的种子值。如果将其设置为相同的值,则随机数的序列相同;如果设置为不同的值,则序列不同。

3.4 运行顺序

已经完成了 crc_encoder 和 crc_decoder 的实现后,接下来可以这样测试。

假设数据存储在名为 datastream.tx 的文件中。

>> ./crc_encoder datastream.tx codedstream.tx 1101 4
>> ./linksim codedstream.tx codedstream.rx 0.0 1001
>> ./crc_decoder codedstream.rx datastream.rx result.txt 1101 4 

由于在此处将 linksim 的错误率设为 0,因此如果程序没有错误,datastream.tx 和 datastream.rx 应完全匹配。

对于 result.txt,由于没有错误,第二个数字应为 0,而第一个数字在 dataword 大小为 4 时应为初始输入文件大小的两倍,在 dataword 大小为 8 时应为初始输入文件大小。

在上述示例中,如果 datastream.tx 为 42 字节,则 result.txt 应如下所示:

84 23

表达的意思是:共发送了 84 个码字,其中 23 个被检测出错误。


💬 crc_encoder:

#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <list>
#include <fstream>
#include <stdlib.h>
#include <cstring>
using namespace std;
#define ARGC_5 5// Most Significant Bit
int GetMSB(int nums) {if (0 == nums) {      // 检查x是否为0,避免对0取对数return 0;}// MSB = ⌈ log_2(x) ⌉int ret = static_cast<int> (ceil(log2(nums)));return ret;
}int main(int argc, char *argv[]) {int gen_sz = 0;string init_gen;int generator = 0;int data_word_sz = 0;int len = 0;int i = 0;int j = 0;int sz = 0;if (ARGC_5 != argc) {printf("usage: ./crc_encoder input_file output_file generator data_word_sz");exit(0);}ifstream readFile;readFile.open(argv[1]);string input_file = "";string line;// input_file 打开失败if (!readFile.is_open()) { cerr << "input file open error." << endl;exit(0);}else {for (std::string line; getline(readFile, line); input_file += line, input_file += "\n");input_file = input_file.substr(0, input_file.length() - 1);readFile.close();}// output_file 打开失败ofstream outfile(argv[2], ios::out | ios::binary);if (!outfile) {cerr << "output file open error." << endl;exit(0);}// data_word_sz大小不是4也不是8的情况string ds = argv[4];if (ds != "4" && ds != "8") {cerr << "dataword size must be 4 or 8." << endl;exit(0);}gen_sz = strlen(argv[3]);init_gen = argv[3];generator = (bitset<32>(init_gen)).to_ulong();data_word_sz = atoi(argv[4]);len = input_file.length();vector<string> bits_in_str; string plus_for_divide = "";i = 0;while (i < GetMSB(generator) - 1) {plus_for_divide += '0';i++;}i = 0;while (i < len) {bitset<8> bit(input_file[i]);string bit_string = bit.to_string();int j = 0;while (j < 8) {bits_in_str.push_back(bit_string.substr(j, data_word_sz) + plus_for_divide);j += data_word_sz;}i++;}string all_generator = (bitset<8>(generator)).to_string();string real_generator;i = 0;int gen_sz = all_generator.size();while (i <= gen_sz) {if ('1' != all_generator[i]) {i++;}else {real_generator = all_generator.substr(i, all_generator.size() - i);break;}}vector<string> fc;i = 0;int bitsz =  bits_in_str.size();while (i < bitsz) {string a = bits_in_str[i];bitset<16> data = bitset<16>(a);bitset<16> __div = bitset<16>(generator);string baoliu = "";__div = __div << (16 - GetMSB(generator));data = data << (16 - (data_word_sz + GetMSB(generator) - 1));string strdata = data.to_string();j = 0;while (j < data_word_sz) {if (strdata[j] != '1') {__div = __div >> 1;j++;}else {data = data ^ __div;strdata = data.to_string();}}baoliu = data.to_string();baoliu = baoliu.substr(data_word_sz, GetMSB(generator) - 1);a = a.substr(0, data_word_sz) + baoliu;fc.push_back(a);i++;}int padding_size = 0;int sum = (data_word_sz + GetMSB(generator) - 1) * fc.size();padding_size = 16 - (sum % 16);string zero_padding;i = 0;while (i < padding_size) {zero_padding += '0';i++;}bitset<8> bit_padding_size(padding_size);bitset<8> bit_zero_padding(zero_padding);string fc_string = "";i = 0;int fc_sz = fc.size();while (i < fc_sz) {string a = fc[i];fc_string += a;i++;}string final_output = bit_padding_size.to_string() + zero_padding + fc_string;size_t ui = 0;int fo = final_output.length();while (ui < fo) {string byte_str = final_output.substr(ui, 8);bitset<8> byte(byte_str);unsigned char c = static_cast<unsigned char>(byte.to_ulong());outfile.write(reinterpret_cast<const char*>(&c), sizeof(c));ui += 8;}outfile.close();return (0);
}

💬 crc_decoder:

#include <iostream>
#include <vector>
#include <cmath>
#include <list>
#include <fstream>
#include <stdlib.h>
#include <cstring>
#include <string>
#include <bitset>
#define ARGC_6 6
using namespace std;// time 21:33
int GetMSB(int nums);
int main(int argc, char*argv[]) {char byte = 0;int gen_sz = 0;string init_gen;int generator = 0;int dataword_size = 0;int all_num = 0;int fail_num = 0;int i = 0;int j = 0;int k = 0;int zero_sz = 0;int sz = 0;// processCRC(argv[1], argv[2], argv[3], argv[4], argv[5]);if (ARGC_6 != argc) {printf("usage: ./crc_decoder input_file output_file result_file generator dataword_size");exit(0);}string input_string;byte = 0;ifstream input_file;input_file.open(argv[1], ios::binary);string line;if (!input_file.is_open() ) {cerr << "input file open error." << endl;exit(0);}else {for (char byte; input_file.get(byte);) {bitset<8> bits(byte);input_string += bits.to_string();}input_file.close();}ofstream outfile;outfile.open(argv[2]);if (!outfile) {cerr << "output file open error." << endl;exit(0);}ofstream resultfile;resultfile.open(argv[3]);if (!resultfile) {cerr << "result file open error." << endl;exit(0);}string a4 = argv[5];if (a4 != "4" && a4 != "8") {cerr << "dataword size must be 4 or 8." << endl;exit(0);}gen_sz = strlen(argv[4]);init_gen = argv[4];generator = (bitset<32>(init_gen)).to_ulong();dataword_size = atoi(argv[5]);all_num = 0;fail_num = 0;bitset<8> bit_zero_sz(input_string.substr(0, 8));zero_sz = (bitset<8> (input_string.substr(0, 8)) ).to_ulong();k = dataword_size + GetMSB(generator) - 1;vector<string> re_word;all_num = (input_string.length() - 8 - zero_sz) / 7;i = 0;int max_it = (input_string.length() - 8 - zero_sz) / (dataword_size + GetMSB(generator) - 1);while (i < max_it) {string substr = input_string.substr(8 + zero_sz + i * k, dataword_size);re_word.push_back(substr);string x = input_string.substr(8 + zero_sz + i * k, k);bitset<16> bit_str(x);bitset<16> div(generator);bit_str = bit_str << 16 - k;div = div << 16 - GetMSB(generator);string strdata = bit_str.to_string();j = 0;while (j < dataword_size) {if (strdata[j] != '1') {div = div >> 1;++j;}else {bit_str = bit_str ^ div;strdata = bit_str.to_string();}}if (0 == bit_str.to_ulong()) {i += 1;}else {fail_num++;}}string reborn = "";i = 0;sz = re_word.size();while (i < sz) {string a = re_word[i];reborn += a;i++;}string end_str = "";j = 0;sz = reborn.length();while (j < sz) {bitset<8> y(reborn.substr(j, 8));char z = char(y.to_ulong());end_str += char((bitset<8>(reborn.substr(j, 8)).to_ulong()));j += 8;}outfile << end_str << endl;resultfile << all_num << " " << fail_num << endl;return( 0);
}int GetMSB(int nums) {if (0 == nums) {return 0;}// MSB = ⌈ log_2(x) ⌉int ret = static_cast<int> (ceil(log2(nums)));return ret;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2024年5月6日优雅草蜻蜓API大数据服务中心v2.0.3更新

v2.0.3更新 2024年5月6日优雅草蜻蜓API大数据服务中心v2.0.3更新-修复改版后搜索框漏掉的bug-增加搜索框 提示&#xff1a;优雅草大数据中心已经 上线137天 稳定运行 1181555 次 累积调用 目前大数据中心用户呈现增长趋势&#xff0c;目标2024年11月底突破1亿次调用&#xf…

社工库信息查询

此网站需要注册账号&#xff0c;新用户注册送3点券&#xff0c;每日签到可获得1.5点券。也可通过充值来查 我这里有方法可以利用缺陷来无限获取点券查人

交通数据三维可视化呈现与可视化分析系统开发(附程序源码)

目录 01 系统介绍 02 功能介绍 文件管理功能 模型研究 可视化分析功能 今天分享一套“交通数据三维可视化呈现与可视化分析系统”&#xff0c;并开放程序源代码下载&#xff0c;内容涉及开源空间数据库的使用、三维引擎的二次开发、矢量和栅格数据管理、交通流量分析模型框…

AI图书推荐:使用FastAPI框架构建AI服务

《使用FastAPI构建生成式AI服务》&#xff08;Building Generative AI Services with FastAPI (Early Release) &#xff09;是一本由Ali Parandeh编写的书籍&#xff0c;计划于2025年3月首次出版&#xff0c;该书以实践为导向&#xff0c;指导读者如何开发具备丰富上下文信息的…

【nodejs 命令行交互神器 - inquirer.js】

需求 大家在开发时&#xff0c;有时需要从命令行读取用户的输入&#xff0c;或者让用户选择。在nodejs中&#xff0c;这个怎么实现? 原生实现 ❌ process.stdin.setEncoding(utf8);process.stdin.on(readable, () > {let chunk;// 使用循环确保我们读取所有的可用输入wh…

C语言(指针)1

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸各位能阅读我的文章&#xff0c;诚请评论指点&#xff0c;关注收藏&#xff0c;欢迎欢迎~~ &#x1f4a5;个人主页&#xff1a;小羊在奋斗 &#x1f4a5;所属专栏&#xff1a;C语言 本系列文章为个人学习笔记&#x…

前端笔记-day03

文章目录 01-初始CSS02-CSS引入方式03-标签选择器04-类选择器05-id选择器06-通配符选择器07-画盒子08-字体大小09-文字粗细10-字体倾斜11-行高12-行高垂直居中13-字体族14-font复合属性15-文本缩进16-文本对齐方式17-图片对齐方式18-文本修饰线19-文字颜色20-调试工具21-综合案…

容器监控与日志管理

前言&#xff1a;本博客仅作记录学习使用&#xff0c;部分图片出自网络&#xff0c;如有侵犯您的权益&#xff0c;请联系删除 一、Docker监控工具 二、容器日志工具docker logs 三、第三方日志工具 四、容器日志驱动 五、示例 5.1、查看容器中运行的进程的信息 5.2、查看…

SOCKET编程(4):SOCKET实战

SOCKET实战 Writen()、Readn()函数 send()函数存在需要发送的字符数len小于函数返回的已发送的字符数(ssize_t)的问题 recv()函数存在需要接收的字符数len小于函数返回的已接收的字符数(ssize_t)的问题 解决上述问题通过Writen()、Readn()函数实现 //buff是数据存储地址&a…

在Leaflet中点对象使用SVG和Canvas两种模式的对比

目录 前言 一、关于SVG和Canvas 1、SVG知识 2、Canvas知识 3、优缺点 二、SVG和Canvas在Leaflet的使用 1、相关类图 2、Leaflet的默认展示方式 三、SVG和Canvas实例及性能对比 1、SVG模式及性能对比 2、Canvas优化 总结 前言 众所周知&#xff0c;在Leaflet当中&#…

用于视频识别的快慢网络

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 摘要Abstract文献阅读&#xff1a;用于视频识别的快慢网络1、文献摘要2、提出方法2.1、SlowFast模型2.2、SlowFast 提出思想 3、相关方法3.1、时空间卷积3.2、基于光…

深入解析RedisSearch:全文搜索的新维度

码到三十五 &#xff1a; 个人主页 在当今的数据时代&#xff0c;信息的检索与快速定位变得尤为关键。Redis&#xff0c;作为一个高性能的内存数据库&#xff0c;已经在缓存和消息系统中占据了重要地位。然而&#xff0c;Redis并不直接支持复杂的搜索功能。为了填补这一空白&am…

零代码平台助力中国石化江苏油田实现高效评价体系

概述&#xff1a; 中国石化集团江苏石油勘探局有限公司面临着评价体系依赖人工处理数据、计算繁琐且容易出错的挑战。为解决这一问题&#xff0c;他们决定借助零代码平台明道云开发江苏油田高质量发展经济指标评价系统。该系统旨在实现原始数据批量导入与在线管理、权重及评分…

Redis单机安装

1.编译 cd redis安装目录 makemake install2.修改配置文件redis.conf #端口修改 port 6379 #后台进程启动 yes daemonize yes # daemonize no #注释掉 为了可以远程连接 #bind 127.0.0.1 #设置密码 requirepass pwd3.启动 ./redis-server ../redis.conf查看进程 [rootlocal…

【Linux】从零开始认识动静态库 -动态库

送给大家一句话&#xff1a; 我不要你风生虎啸&#xff0c; 我愿你老来无事饱加餐。 – 梁实秋 《我把活着欢喜过了》 ଘ(੭ˊᵕˋ)੭* ੈ✩‧₊˚ଘ(੭ˊᵕˋ)੭* ੈ✩‧₊˚ଘ(੭ˊᵕˋ)੭* ੈ✩‧₊˚ ଘ(੭ˊᵕˋ)੭* ੈ✩‧₊˚ଘ(੭ˊᵕˋ)੭* ੈ✩‧₊˚ଘ(੭ˊᵕˋ)੭…

【小红书采集软件】根据关键词批量爬取小红书笔记正文、笔记链接、发布时间、转评赞藏等

一、背景介绍 1.1 爬取目标 熟悉我的小伙伴可能了解&#xff0c;我之前开发过2款软件&#xff1a; 【GUI软件】小红书搜索结果批量采集&#xff0c;支持多个关键词同时抓取&#xff01; 【GUI软件】小红书详情数据批量采集&#xff0c;含笔记内容、转评赞藏等&#xff0c;支…

用大于meilisearch-java-0.7.0.jar的报错的解决

Elasticsearch 做为老牌搜索引擎&#xff0c;功能基本满足&#xff0c;但复杂&#xff0c;重量级&#xff0c;适合大数据量。 MeiliSearch 设计目标针对数据在 500GB 左右的搜索需求&#xff0c;极快&#xff0c;单文件&#xff0c;超轻量。 所以&#xff0c;对于中小型项目来说…

数组元素翻倍C++

编写一个 C 程序&#xff0c;实现一个功能&#xff0c;即将数组中的每个元素值翻倍。程序应定义一个函数 doubleArray&#xff0c;该函数接收一个整数数组的指针和数组的大小&#xff0c;然后将数组中的每个元素都翻倍。 代码 #include <iostream>void doubleArray(int…

Rust使用HashSet对Vec类型的元素进行去重

在Rust语言中&#xff0c;对Vec类型的元素进行去重&#xff0c;一种常见的方法是使用一个HashSet来帮助我们快速检查元素是否已经存在。以下是使用HashSet对Vec进行去重的示例代码&#xff1a; use std::collections::HashSet;fn main() {let vec_numbers vec![1, 2, 2, 3, 4…

Softing工业推出的edgeConnector将Allen-Bradley控制器集成到工业边缘应用中

2024年4月17日&#xff08;哈尔&#xff09;&#xff0c;Softing宣布扩展其基于Docker的edgeConnector产品系列&#xff0c;推出了新软件模块edgeConnector Allen Bradley PLC&#xff0c;可方便用户访问来自ControlLogix和CompactLogix控制器数据。 &#xff08;edgeConnector…