介绍一个好用的在线CRC16校验工具:
信息深圳网-CRC16在线校验工具-生成多项式x16+x12+x5+1(0x11021) ,
详情参考原链接:
http://www.infosz.com/_crcTool.php
该工具为信息深圳网www.infosz.com原创,保留所有权利!
最近看到一些很有趣的讨论,觉得还是把E2E的一些概念整理下,以便后期追索。下面的内容大多出自于AutoSAR标准和一些相关的论文,非纯原创,只是资料的搬运工加上一些自己的理解而已。
E2E protection,这里面的E是End的意思,我所理解的这个端对端,主要是数据从应用层到应用层的保护。
这个数据传递的过程可能包含三个部分。
- ECU2ECU之间通信链路的保护(以前最常见的是CAN,现在因为智能驾驶行业的兴起,通过Ethernet、OTA等方式传递的数据,也会列入到需要保护的范畴里。当然这里面可能又会涉及到另外一个庞大的话题-网络安全。)
- 从 ASW to BSW的传输保护
- 从 BSW to ASW的传输保护
如果数据只在一个ECU内部传递,那只会涉及2和3部分。
整个链路里面,典型的软件相关的故障源有:
S1: RTE错误
S2: 生成和手工代码COM错误
S3 网络堆栈错误
S4: IOC或者OS的错误
硬件相关的故障源则有:
H1: 硬件路径的失效
H2: EMC对通信网络的影响
H3: 内核通信或者区域划分时的MCU失效
来源:Specification of SW-C End-to-End Communication Protection Library 而所谓的E2E保护,就是要在发现这些错误介入引发的数据失效并作出警示。
AutoSAR标准里保护机制的算法是在E2E library中实现的,主要包含以下功能:
- 保护通过RTE交换的安全相关的数据元素
- 验证从RTE获取的安全相关的数据元素
- 指明接收到的安全相关的数据元素错误,接收方的SW-C必须做出处理
E2E保护的工作过程如下:
发送方:向传输的数据添加CRC或计数器等控制字段(所以这个CRC并不是由CAN Transceiver添加的,跟CAN message里面提到的
接收方:评估接收数据中的控制字段,对控制字段计算(例如,对接收数据的CRC计算),计算的控制字段与预期/接收内容的比较。
为什么会选择CRC这种方法,应该是考虑这种校验方式失效模式整体覆盖率较高的缘故。
这里面要说明一点,我们平时总习惯说CRC checksum,其实这是两种校验方式。
Checksum代表总和检验码,校验和。在数据处理和数据通信领域中,用于校验目的的一组数据项的和。这些数据项可以是数字或在计算检验总和过程中看作数字的其它字符串。
Checksum也有很多不同的类型,比如XOR checksum, 1's complement Checksum, 2's complement Checksum等。
而CRC即循环冗余校核,是一种根据网络数据包或电脑文件等数据产生简短固定位数校核码的快速算法,主要用来检测或校核数据传输或者保存后可能出现的错误,利用除法及余数的原理。
下述公式给出了无法检测的故障概率的计算原理。
其中,
可以看出,其中的影响因素主要是数据长度(包含校验字段的长度)n,汉明距离d,错误位的数量i以及Bit错误的概率p。
ISO26262的第5章D.2.5.6里面还提到CRC的覆盖率还跟CRC二项式本身的选择相关,并且给出了一些示例推荐。这里面2011版和2018版的描述也有些变化,以前都是直接说诊断覆盖率的,现在改成了失效模式的整体覆盖率。
这些二项式的覆盖率是通过计算机仿真得出的,一些详细的介绍可以参考[4],新的二项式也在不断被发现中。
表1:ISO26262:2018 CRC失效模式整体覆盖率说明 而在AutoSAR标准《Specification of CRC Routines》[3]中,也列明了所推荐的CRC二项式。针对8-bit CRC,推荐了1Dh和2Fh, 因为在AutoSAR中,二项式是用反向倒数表示的,所以其实2FH和0x97是代表了同一个多项式(以前没太留心过这个,正好在大群里看到博世的一位王工的发言,再去看标准,发现果然有所说明,真正是学无止境。)
[3]还推荐了16-bit CRC和32-bit CRC的二项式。一般来说为了符合功能安全的要求,ASILC的信号要考虑用16-bit CRC的二项式校验,而ASILD的信号则要用32-bit CRC的二项式校验,但是其实还是要根据校验方法的覆盖率来选择的。
E2E的使用也有一些限制,如下面所列:
- 仅考虑发送方 - 接收方(排队和非排队)通信(无客户端 - 服务器)
- 仅考虑软件组件之间的周期通信(不基于事件)
- 仅考虑ECU间通信(通过COM堆栈交换的通信)
- 仅考虑排队的发送方 - 接收方通信的非阻塞特性(不支持排队通信的阻塞特性)
另外,标准里面也说了,只用单纯应用E2E Library并不能说明已经充分满足ASILD关于安全通信的要求,还是需要用户阐明选择的校验方式能提供充分的故障检测,那可能需要分析和测试都加以应用。
参考文件
[1] Specification of Module E2E Transformer, 4.3.0
[2] Specification of SW-C End-to-End Communication Protection Library, 4.3.0
[3] Specification of CRC Routines, 4.3.0
[4] Koopman P., & Chakravarty T. 2004), Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks The International Conference on Dependable Systems and Networks, DSN-2004
作者:自为风月马前卒
链接:https://ac.nowcoder.com/discuss/179728
来源:牛客网前言
第一次当标题党真是有点不适应
现在网上讲生成函数的教程大多都是从
开始,但是我不认为这样有助于大家理解生成函数的本质。我最开始学的时候也是在这里蒙了好久,直到看到了朱全民老师的课件,才真正的理解了生成函数的本质——处理排列组合问题的有利工具,而不是简单的
的指标代换。所以这篇文章,我打算从最基本的排列组合问题写起,最后慢慢扩展到
。内容会比较基础,高端玩家可以直接看鏼爷的集训队论文。
生成函数
定义
维基百科上是这么定义的:的母函数(又称生成函数,英语:Generating function)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。
讲的通俗一点,对于某个序列
,我想找一个函数来表示它,假设是
。这时候函数第
系数就表示了序列中的第项的
个元素。同时我们也可以看到,函数中的自变量
形式幂级数。好像并没有什么意义,他的取值并不影响序列的表示,因此我们称这种函数为
用处
那么这样定义由什么好处呢?
我们仔细观察一下
,不难发现这是一个多项式函数,对于多项式我们知道他有加、减、乘、 ~~除,求逆,取ln,exp~~ 等运算。那么我们对
进行乘法运算,也就是相当于对序列进行乘法运算,那么这样干有什么意义呢?我们不妨从一个题目入手。
普通生成函数
有三种物品,分别有3,2,3个,问拿出4个进行组合(算一种)的方案数是多少
学过dp的人可能会一眼看出是背包板子题。直接设
表示当前到第
个位置,已经选了
个物品的方案数。转移的时候枚举一下当前选了几个
f[0][0] = 1; for(int i = 1; i <= 3; i++) for(int j = 0; j <= 8; j++) //当前总共要选出j个 for(int k = 0; k <= j; k++) //已经选了k个 if(j - k <= v[i]) //此时要选j-k个 f[i][j] += f[i - 1][k];
可以得到
的系数为
(从0开始编号),
最对应的一项是
。
那用生成函数怎么做呢?
我们可以对每个物品构造一个多项式函数,其中第
项的系数
表示选了
个当前物品的方案数。
那么第一个物品的生成函数为
(相同的物品选
个的方案数当然是1)
第二个物品的生成函数为
第三个为
先说结论:最终答案是
的第
项的系数
这是为什么呢?考虑两个多项式相乘的结果
,它的第
项的系数为
。这个过程是相当于是在枚举第一个物品选了几个,比如
这一项,他等于
。
再具体一点,抛开刚刚那个题目中系数等于
的限制,我们假设
,也就是说从第一个物品中选出
个有两种方案,第二个物品中选出
个有三种方案,那么
就相当于第一个物品的两种方案可以与第二个物品的三种方案任意组合来得到
种物品。(再看不懂的话建议去补一下高中组合计数qwq,这里讲的这么详细是为了给指数生成函数做铺垫)
这里建议大家去手玩一下多项式乘法,玩一下(玩的时候枚举
算他的系数)就会发现这个过程与背包的过程惊人的相似,因为事实上背包的过程就是在模拟多项式乘法。
这里为了下文(指数型生成函数)好讲解,本菜鸡直接把多项式相乘的结果写出来
其中
项可以由下面这些得到,这种形式与我们的手玩结果就非常相似了
形如
普通生成函数的表示一个序列的多项式函数,我们称之为
讲到这里你需要大概明白:生成函数的基本概念,生成函数相乘的组合意义。
接下来按道理应该讲
及其运算,但是我想先介绍一下指数生成函数的基本概念。
指数生成函数
通过刚刚的讲解我们不难看出,普通生成函数的意义在于解决组合类计数问题。但是别忘了组合的兄弟排列呀。指数生成函数就是用来解决排列类问题。
还是刚刚的题目,我们改一下限制
有三种物品,分别有3,2,3个,问拿出4个进行组合(算不同方案)的方案数是多少
这一类问题仅仅是比刚刚多了一个顺序的原因,但是难度却比刚刚大了不少(背包也可以做,只要在转移的时候乘一个组合数即可,留给大家思考)
这里先介绍一下多重集排列数
设,其中第
表示第
个物品有
个。从中选出
个进行排列的方案数为
,解释的话就是相当于任意排列之后减去同种物品之间多出来的方案
这样我们就得到了一个思路:先把所有组合得到的方案算出来,然后再对每一种方案分别计算排列数,最后加起来。
比如我们刚刚已经得到了组合的方案:
其中
这一项的排列方案就是
,
这一项的排列方案就是
。观察一下,所有方案的分子都是
,分母都是选出来的对应数量的阶乘。
于是我们引进指数型生成函数
形如
的表示序列的多项式函数,我们称之为指数生成函数。
同时我们分别构造出
这时候再计算一下
这时候如何计算选出
个物品的答案呢?简单
可能大家不禁思考,为什么这么定义函数乘起来就是排列数呢?想一想,因为我们对每个系数构造的
就相当于是多重集排列数中的分母呀
好了,如果你到这里都看懂了的话,说明你已经对生成函数有个大概的了解了。但是不知道大家是不是和我有着同样的感觉:生成函数好麻烦啊qwq。
那么有没有一套可以简化些运算的理论呢?
答案是:当然有了!(不然我问个毛线)。下面讲的内容可以会有些刺激,需要大家有一定的数学基础(其实只要高中知识就行了)
普通生成函数的推广
简单介绍
这个也不能叫推广吧,是我自己瞎起的名字。。。
在我们刚刚的运算中出现了一个常用的函数
,这个东西怎么化简呢?
结论:
可能你和当初一次见到这个式子的我一样,大概是这个表情
我们来证明一下。
是不是证的天衣无缝但是又十分扯淡?因为这玩意儿显然只有
收敛也就是
时成立。其实在这里只要在
成立就可以了,因为生成函数是形式幂级数,我们并不关心
的具体取值
有了这个我们能干什么呢?我们可以对
变形来表示更多的序列,同时我们知道了
对应序列的第
项的系数为
,那么当我们知道了某一个序列的生成函数之后我们也可以把它变成类似于
的形式从而得到通项公式。
首先介绍一些简单的变换,建议大家手玩一下下面的生成函数的推广形式,比如把"乘
"换成"乘
"
将
替换为
,
将
替换为
,
将
替换为
,
将分子乘
,
将分子乘
,
求个导,
再求一次,
问题来了,我如果知道了某一个数列的生成函数,怎么求它的通项公式呢?一般的思路就通过各种奇技淫巧往上面的几个生成函数转化。这里要提一下比较常用的**广义二项式定理**
我们来通过两个例子来具体讲一下它的用处
求斐波那契数列通项公式
非常不不要脸的抄一下自己以前的博客
首先要知道斐波那契数列的递推式
那么推导一下
设
根据递推式,我们可以这样变化,显然有
那么可以得到一个方程
整理一下
这样我们就得到了斐波那契数列的生成函数,然而并没有什么卵用,因为我们不能直接通过观察看出每一项的系数。
现在考虑一下,我们接下来可以干什么。我们已经知道了
和
所表示的序列。接下来要干的当然是把
往上面的两个式子转化。
这玩意儿下半部分是个一元二次方程,我们可以配方
(解的时候可以直接把后面的式子拆开,把这两个式子对应项联立组成方程组,
的取值是可以反过来的)
这个时候我们发现已经找到与
的联系了,我们可以把
拆成求和的形式。可以裂一下项
原式变为
,然后再解一个方程
解这个方程就没那么休闲了,这里我们选择把
当做主元对方程进行变换
这样就好处理了,只要列个二元一次方程组
解一下可以得到
带回去
那么第
项的公式为
解决组合类问题
比如这种休闲板子题
至多为
就是
这个东西可以直接广义二项式定理展开,然后交一发pypy2就过了。。
指数生成函数的推广
和上面的很类似,这里直接说结论
证明:考虑直接将
在
处泰勒展开 由泰勒展开的公式
(
的意思是求
次导数)
一些常用变换:
一道简单的题目
长度为的序列,用红黄蓝绿四种颜色染色,其中红黄只能是偶数,问方案数
这道题就比较休闲了
任意的是
,偶数的是
最后化完是
(
)相当于常数项
直接快速幂就可以求
后记
本篇讲的是关于生成函数最基础的内容,千万不要认为自己看懂了上面的内容就会生成函数了,充其量也就是了解而已。生成函数理论十分博大精深,我也只是略知皮毛。过几天可能会根据学习情况更一些生成函数与多项式运算的东西,敬请期待吧qwq
参考资料
生成函数-罗煜楚(版权原因暂不公开)
组合数学—母函数与递推——朱全民
母函数——维基百科
与作者交流:https://ac.nowcoder.com/discuss/179728
更多算法和题解:https://ac.nowcoder.com/acm/contest/discuss
介绍一个好用的在线CRC16校验工具:
信息深圳网-CRC16在线校验工具-生成多项式x16+x12+x5+1(0x11021) ,
详情参考原链接:
http://www.infosz.com/_crcTool.php
该工具为信息深圳网www.infosz.com原创,保留所有权利!
转载于:https://www.cnblogs.com/actorai/p/5357555.html
我们希望生产从初始点到目标点的一条路径,
最简单基础的方法是生成多项式轨迹
初始条件与终止条件的数目决定了我们的多项式最高次项。假设我们在[0,]时间段内规划路径,对于初始和终止的位置,速度和加速度都有一定的要求,相当于我们有6个约束条件。
我们需要五次多项式,6个参数。
下面来具体看看,
我们把未知参数提出来可以得到矩阵形式。
由此,我们就可以求解出相应的参数得到具体的轨迹了。function [xt,yt] = trajectory(t,tf) % code xa=0; ya=1; xb=0.2; ya=0.8; % initial state x0=0; x0d=0; x0dd=0; % fininal state xf=0.2; xfd=0; xfdd=0; c=[x0;x0d;x0dd;xf;xfd;xfdd]; P=[1,0,0,0,0,0; 0,1,0,0,0,0; 0,0,2,0,0,0; 1,tf,tf^2,tf^3,tf^4,tf^5; 0,1,2*tf,3*tf^2,4*tf^3,5*tf^4; 0,0,2,6*tf,12*tf^2,20*tf^3]; % as the trajectory method,we want ti calculate the parameter a=inv(P)*a; tn=t/tf; s=a(1)+a(2)*tn+a(3)*tn^2+a(4)*tn^3+a(5)*tn^4+a(6)*tn^5; % the initial position(xa,ya) and the target position(xb,yb) xt=xa+s*(xb-xa); yt=ya+s*(yb-ya);