《rfid原理及应用》第4章数据校验和防碰撞算法.ppt

《《rfid原理及应用》第4章数据校验和防碰撞算法.ppt》由会员分享，可在线阅读，更多相关《《rfid原理及应用》第4章数据校验和防碰撞算法.ppt（37页珍藏版）》请在三一办公上搜索。

1、合肥工业大学 计算机与信息学院,RFID技术基础,2,4 数据校验和防碰撞算法,在RFID系统中，数据传输的完整性存在两个方面的问题：一是外界的各种干扰可能使数据传输产生错误；二是多个应答器同时占用信道使发送数据产生碰撞。运用数据检验（差错检测）和防碰撞算法可分别解决这两个问题。,3,4 数据校验和防碰撞算法,差错 随机错误：由信道中的随机噪声干扰引起。在出现这种错误时，前后位之间的错误彼此无关。突发错误：由突发干扰引起，当前面出现错误时，后面往往也会出现错误，它们之间有相关性。混合错误,突发错误长度b=5,4,4 数据校验和防碰撞算法,差错控制在传输信息数据中增加一些冗余编码，使监督码元和信

2、息码元之间建立一种确定的关系，实现差错控制编码和差错控制解码功能。反馈重发（ARQ）、前向纠错（FEC）和混合纠错（HEC）,反馈重发发送端需要在得到接收端正确收到所发信息码元（通常以帧的形式发送）的确认信息后，才能认为发送成功。,前向纠错接收端通过纠错解码自动纠正传输中出现的差错，所以该方法不需要重传。这种方法需要采用具有很强纠错能力的编码技术,混合纠错是ARQ和FEC的结合，设计思想是对出现的错误尽量纠正，纠正不了则需要通过重发来消除差错。,5,4 数据校验和防碰撞算法,检纠错码 信息码元与监督码元,信息码元 k 监督码元r,检纠错码 许用码组与禁用码组 k=2分组为（00），（10），（

3、10），（11），（00），。如果将这样的信息组直接送入信道传输，它是没有任何抗干扰能力的，因为任意信息组中任一元素出错都会变成另一个信息组，例如信息组（00）某一位出错，将会变成（10）或（01），而它们代表着不同的信息组，因此在接收端就会判断错误。可见不管k的大小如何，若直接传输信息组是无任何抗干扰能力的。,如果在各个信息组后按一定规律人为地添上一些数字，例如上例，我们在k=2的信息组后再添上一位数字，使每一组的长度变为3，这样的各组序列我们称之为码字，码字长度记为n，本例中n=k+1，其中每个码字的前两个码元为原来的信息组，称为信息元，它主要用来携带要传输的信息内容，后一个新添的码元称为

4、监督元（或校验元），其作用是利用添加规则来监督传输是否出错。如果添监督元的规则为：新添监督元的符号（0或1）与前两个码元（信息元）符号（0或1）之和为0（即模2和为0），这样的码字共有2k=4个，即（000）、（011）、（101）、（110），它们组成了一个码字集合，其中每一个码字分别代表一个不同的信息组。而在3位二进制序列（码组）中共有8个，除以上4个作为码字外，还有4个未被选中，即这4个码组不在发送之列，我们称之为禁用码组，而被编码选中的n重即码字亦称为许用码组。对于接收端，若接收序列不在码字集合中，说明不是发送端所发出的码字，从而确定传输有错。因此这种变换后的码字就具有一定的抗干扰能力

5、。,8,4 数据校验和防碰撞算法,检纠错码的分类,9,4 数据校验和防碰撞算法,分组码 码组的监督码元仅与本码组的信息码元有关，而与其他码元组的信息码元无关 卷积码 码组的监督码元不仅与本码组的信息码元相关，而且与本码组相邻的前m个时刻输入的码组的信息码元之间也具有约束关系性能优于分组码 交织码 利用交织技术构造出来的编码,10,4 数据校验和防碰撞算法,交织码,线性分组码如前所述，我们将信源所给出的二元信息序列首先分成等长的各个信息组，每组信息位长度为k，记为M=（m k1，m k2，m 1，m 0）显然，信息组M每一位上的信息数字（称信息元）取0或l，共有2k种可能的取值。编码器根据某些规

6、则，将输入的信息组编成码长为n的二元序列，即码字记为C=（cn1，cn 2，cn k，cn k1，c 1，c 0）码字中每一位数字称为码元，取值为0或1。如果码字的各监督元与信息元关系是线性的（即用一次线性方程来描述），这样的码称为线性分组码，记为(n,k)码。,4 数据校验和防碰撞算法,例(7,3)分组码，按以下的规则（校验方程）可得到4个校验元c0 c1 c2 c3：c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4式中：c6，c5和c4是三个信息元。由此可得到(7,3)分组码的八个码字。八个信息组与八个码字的对应关系列于表4-1中。式中的加均为模2加。由此方程看到，信

7、息元与校验元满足线性关系，因此该(7,3)码是线性码。,4 数据校验和防碰撞算法,表4-1 按上式编出的(7,3)码字与信息组的对应关系 信 息 组 码 字0 0 0 0 0 0 0 0 0 00 0 1 0 0 1 1 1 0 10 1 0 0 1 0 0 1 1 10 1 1 0 1 1 1 0 1 01 0 0 1 0 0 1 1 1 01 0 1 1 0 1 0 0 1 11 1 0 1 1 0 1 0 0 11 1 1 1 1 1 0 1 0 0,4 数据校验和防碰撞算法,线性分组码的编码问题，就是如何从n维线性空间Vn中，挑选出一个k维子空间Vn,k，而选择的规则完全由n-k个校验

8、方程决定。由于线性分组码对模2加满足封闭性，就为其最小距离的计算带来方便，具体有如下定理。定理4.1 一个(n,k)线性分组码中非零码字的最小重量等于C中的最小距离d 0。证明 设有任两个码字C a，Cb C。根据线性分组码性质，有C a+C b=C c C。而C c的码重等于C a与C b的码距d a;b，即W(C c)=W(C a+C b)=d a;bC a和C b是C中任意两个非全零码字，所以 Wmin(C a+C b）=Wmin(C c)=d 0 证毕。由上例(7,3)码的8个码字表可见，除全零码字外，其余7个码字最小重量为Wmin=4，而其中任二码字之间的最小距离d 0也为4。,4

9、数据校验和防碰撞算法,在线性分组码中检纠错能力和码的最小距离有关，即：在一个码组内为了检测e个误码，要求最小码距应满足：d e1 在一个码组内为了纠正t个误码，要求最小码距应满足：d 2t1 在一个码组内为了纠正t个误码，同时能检测e个误码(et)，要求最小码距应满足：d et1,4 数据校验和防碰撞算法,线性分组码如前所述，我们将信源所给出的二元信息序列首先分成等长的各个信息组，每组信息位长度为k，记为M=（m k1，m k2，m 1，m 0）显然，信息组M每一位上的信息数字（称信息元）取0或l，共有2k种可能的取值。编码器根据某些规则，将输入的信息组编成码长为n的二元序列，即码字记为C=（

10、cn1，cn 2，cn k，cn k1，c 1，c 0）码字中每一位数字称为码元，取值为0或1。如果码字的各监督元与信息元关系是线性的（即用一次线性方程来描述），这样的码称为线性分组码，记为(n,k)码。,4 数据校验和防碰撞算法,例(7,3)分组码，按以下的规则（校验方程）可得到4个校验元c0 c1 c2 c3：c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4式中：c6，c5和c4是三个信息元。由此可得到(7,3)分组码的八个码字。八个信息组与八个码字的对应关系列于表4-1中。式中的加均为模2加。由此方程看到，信息元与校验元满足线性关系，因此该(7,3)码是线性码。,4

11、 数据校验和防碰撞算法,表4-1 按上式编出的(7,3)码字与信息组的对应关系 信 息 组 码 字0 0 0 0 0 0 0 0 0 00 0 1 0 0 1 1 1 0 10 1 0 0 1 0 0 1 1 10 1 1 0 1 1 1 0 1 01 0 0 1 0 0 1 1 1 01 0 1 1 0 1 0 0 1 11 1 0 1 1 0 1 0 0 11 1 1 1 1 1 0 1 0 0,4 数据校验和防碰撞算法,线性分组码的编码问题，就是如何从n维线性空间Vn中，挑选出一个k维子空间Vn,k，而选择的规则完全由n-k个校验方程决定。由于线性分组码对模2加满足封闭性，就为其最小距离

12、的计算带来方便，具体有如下定理。定理4.1 一个(n,k)线性分组码中非零码字的最小重量等于C中的最小距离d 0。证明 设有任两个码字C a，Cb C。根据线性分组码性质，有C a+C b=C c C。而C c的码重等于C a与C b的码距d a;b，即W(C c)=W(C a+C b)=d a;bC a和C b是C中任意两个非全零码字，所以 Wmin(C a+C b）=Wmin(C c)=d 0 证毕。由上例(7,3)码的8个码字表可见，除全零码字外，其余7个码字最小重量为Wmin=4，而其中任二码字之间的最小距离d 0也为4。,4 数据校验和防碰撞算法,在线性分组码中检纠错能力和码的最小距

13、离有关，即：在一个码组内为了检测e个误码，要求最小码距应满足：d e1 在一个码组内为了纠正t个误码，要求最小码距应满足：d 2t1 在一个码组内为了纠正t个误码，同时能检测e个误码(et)，要求最小码距应满足：d et1,4 数据校验和防碰撞算法,奇偶校验码奇偶校验（或称监督）码是最简单的检错码，由于容易实现，所以应用广泛且久远。它实际上是一种只有一个校验元的(n,n-1)分组码。奇偶校验码的编码规则是在需要传送的信息序列后附加1位校验码元，使加入的这一位码元和各位信息码元模2和的结果为0（偶校验）或1（奇校验）。如果某一比特位出错了，比如说第一比特位从1变成0，那么1的数目就会变成1（即1

14、的数目为奇数），于是接收机就会在比特流中检出错误。另一方面，如果有两比特出错，比如说第五比特和第六比特位出错（即收到的码是10001110）。这种情况下，1的总数是4（偶数），接收机将不能检出错误。因此可以得出结论：奇偶校验码能检出所有奇数个比特位的错误，但不能检出任何偶数个比特位出错的情况。可见其检错能力是有限的，但由于该码构造简单，易于实现，且码率很高，因此成为一种最常用的基本检错码。在信道干扰不太严重、码长不太长的情况下很有用，特别是在电报、计算机内部的数据传送和输入输出设备中，经常应用这种码。,22,4 数据校验和防碰撞算法,RFID中的差错检测 CRC码（循环冗余码）较强的检错能力，

15、硬件实现简单算法步骤,23,4 数据校验和防碰撞算法,RFID中的差错检测 CRC码（循环冗余码）较强的检错能力，硬件实现简单算法步骤 将k位信息写成k-1阶多项式M(X)；设生成多项式G(X)的阶为r；用模2除法计算XrM(X)/G(X)，获得余数多项式R(X)；用模2减法求得传送多项式T(X)，T(X)=XrM(X)-R(X)，则T(X)多项式系数序列的前k位为信息位，后r位为校验位，总位数n=k+r。,24,4 数据校验和防碰撞算法,防碰撞算法有两个或两个以上的应答器同时发送数据，那么就会出现通信冲突，产生数据相互的干扰，即碰撞。多个应答器处在多个阅读器的工作范围之内，它们之间的数据通信

16、也会引起数据干扰。采取防碰撞（冲突）协议，由防碰撞算法（Anti-collision Algorithms）和有关命令来实现。,25,4 数据校验和防碰撞算法,ALOHA算法纯ALOHA算法用于只读系统。当应答器进入射频能量场被激活以后，它就发送存储在应答器中的数据，且这些数据在一个周期性的循环中不断发送，直至应答器离开射频能量场。时隙ALOHA算法 把时间分为离散的时间段（时隙），每段时间对应一帧 动态时隙ALOHA算法阅读器在等待状态中的循环时隙段内发送请求命令，该命令使工作应答器同步，然后提供1或2个时隙给工作应答器使用，工作应答器将选择自己的传送时隙，如果在这1或2个时隙内有较多应答器

17、发生了数据碰撞，阅读器就用下一个请求命令增加可使用的时隙数（如4，8，），直至不出现碰撞为止。,信道吞吐率,S=Ge-2G,信道吞吐率,S=Ge-G,26,4 数据校验和防碰撞算法,二进制树型搜索算法,27,4 数据校验和防碰撞算法,ISO/IEC 14443标准中的防碰撞协议 TYPE A 帧有3种类型：短帧、标准帧和面向比特的防碰撞帧。命令集 REQA/WUPA命令 ATQA应答 ANTICOLLISION和SELECT命令 SAK应答 HALT命令,29,4 数据校验和防碰撞算法,PICC的状态Power-off（断电）状态 Idle（休闲）状态 Ready（就绪）状态 Active（激

18、活）状态 Halt（停止）状态,30,4 数据校验和防碰撞算法,防碰撞流程,31,4 数据校验和防碰撞算法,TYPE B的防碰撞协议REQB/WUPB命令 SLOT-MARKER命令 ATQB应答 ATTRIB命令 HLTB命令及应答,TYPE B防碰撞过程示例,33,4 数据校验和防碰撞算法,碰撞检测 检测接收到的电信号参数（如信号电压幅度、脉冲宽度等）是否发生了非正常变化，但是对于无线电射频环境，门限值较难设置；通过差错检测方法检查有无错码，虽然应用奇偶校验、CRC码检查到的传输错误不一定是数据碰撞引起，但是这种情况的出现也被认为是出现了碰撞；利用某些编码的性能，检查是否出现非正常码来判断

19、是否产生数据碰撞，如曼彻斯特码，若以2倍数据时钟频率的NRZ码表示曼彻斯特码，则出现11码就说明产生了碰撞，并且可以知道碰撞发生在哪一位。,34,4 数据校验和防碰撞算法,设计实例 MCRF250芯片非接触可编程无源RFID器件工作频率（载波）为125kHz两种工作模式：初始模式（Native）和读模式。只读数据传送，片内带有一次性可编程（OTP）的96位或128位用户存储器（支持48位或64位协议）；具有片上整流和稳压电路；低功耗；编码方式为NRZ码、曼彻斯特码和差分曼彻斯特码；调制方式为FSK、PSK和直接调制；封装方式有PDIP和SOIC两种。,35,4 数据校验和防碰撞算法,芯片内部电路由射频前端、防碰撞电路及存储器3部分组成,36,4 数据校验和防碰撞算法,FSK防碰撞阅读器设计,37,4 数据校验和防碰撞算法,防碰撞流程,