1、重庆科技学院 电气与信息工程学院1RFID技术基础技术基础利利 节节2第四章第四章 数据校验和防碰撞算法数据校验和防碰撞算法差错检测的性质和表示方法差错检测的性质和表示方法检纠错码检纠错码差错检测差错检测防碰撞算法防碰撞算法防碰撞设计案例防碰撞设计案例3第四章第四章 数据校验和防碰撞算法数据校验和防碰撞算法差错检测的性质和表示方法差错检测的性质和表示方法检纠错码检纠错码差错检测差错检测防碰撞算法防碰撞算法防碰撞设计案例防碰撞设计案例4 在阅读器与应答器的无线通信中，存在许多干扰因在阅读器与应答器的无线通信中，存在许多干扰因素，最主要的干扰因素是信道噪声和多卡操作。在素，最主要的干扰因素是信道噪
2、声和多卡操作。在RFID系统中，数据传输的完整性存在两个方面的问题：系统中，数据传输的完整性存在两个方面的问题：（1）外界的各种干扰可能使数据传输产生错误；）外界的各种干扰可能使数据传输产生错误；（2）多个应答器同时占用信道使发送数据产生碰撞。）多个应答器同时占用信道使发送数据产生碰撞。5 在阅读器与应答器的无线通信中，存在许多干扰因在阅读器与应答器的无线通信中，存在许多干扰因素，最主要的干扰因素是信道噪声和多卡操作。在素，最主要的干扰因素是信道噪声和多卡操作。在RFID系统中，数据传输的完整性存在两个方面的问题：系统中，数据传输的完整性存在两个方面的问题：（1）外界的各种干扰可能使数据传输产
3、生错误；）外界的各种干扰可能使数据传输产生错误；（2）多个应答器同时占用信道使发送数据产生碰撞。）多个应答器同时占用信道使发送数据产生碰撞。为防止各种干扰和应答器之间数据的碰撞，运用为防止各种干扰和应答器之间数据的碰撞，运用数数据检验（差错控制）据检验（差错控制）和和防碰撞算法防碰撞算法可分别解决这两个问可分别解决这两个问题。题。6 差错控制是一种保证接收数据完整、准确的方法。差错控制是一种保证接收数据完整、准确的方法。在数字通信中，差错控制利用编码方法对传输中产生在数字通信中，差错控制利用编码方法对传输中产生的差错进行控制，以提高数字消息传输的准确性。根的差错进行控制，以提高数字消息传输的准
4、确性。根据信道噪声干扰的性质，差错可以分为：据信道噪声干扰的性质，差错可以分为：1.差错控制差错控制7 差错控制是一种保证接收数据完整、准确的方法。差错控制是一种保证接收数据完整、准确的方法。在数字通信中，差错控制利用编码方法对传输中产生在数字通信中，差错控制利用编码方法对传输中产生的差错进行控制，以提高数字消息传输的准确性。根的差错进行控制，以提高数字消息传输的准确性。根据信道噪声干扰的性质，差错可以分为：据信道噪声干扰的性质，差错可以分为：随机错误随机错误：由信道中的随机噪声干扰引起。在出现：由信道中的随机噪声干扰引起。在出现这种错误时，前后位之间的错误彼此无关。这种错误时，前后位之间的错
5、误彼此无关。1.差错控制差错控制8 差错控制是一种保证接收数据完整、准确的方法。差错控制是一种保证接收数据完整、准确的方法。在数字通信中，差错控制利用编码方法对传输中产生在数字通信中，差错控制利用编码方法对传输中产生的差错进行控制，以提高数字消息传输的准确性。根的差错进行控制，以提高数字消息传输的准确性。根据信道噪声干扰的性质，差错可以分为：据信道噪声干扰的性质，差错可以分为：随机错误随机错误：由信道中的随机噪声干扰引起。在出现：由信道中的随机噪声干扰引起。在出现这种错误时，前后位之间的错误彼此无关。这种错误时，前后位之间的错误彼此无关。突发错误突发错误：由突发干扰引起，当前面出现错误时，：由
6、突发干扰引起，当前面出现错误时，后面往往也会出现错误，它们之间有相关性。后面往往也会出现错误，它们之间有相关性。1.差错控制差错控制9 差错控制是一种保证接收数据完整、准确的方法。差错控制是一种保证接收数据完整、准确的方法。在数字通信中，差错控制利用编码方法对传输中产生在数字通信中，差错控制利用编码方法对传输中产生的差错进行控制，以提高数字消息传输的准确性。根的差错进行控制，以提高数字消息传输的准确性。根据信道噪声干扰的性质，差错可以分为：据信道噪声干扰的性质，差错可以分为：随机错误随机错误：由信道中的随机噪声干扰引起。在出现：由信道中的随机噪声干扰引起。在出现这种错误时，前后位之间的错误彼此
7、无关。这种错误时，前后位之间的错误彼此无关。突发错误突发错误：由突发干扰引起，当前面出现错误时，：由突发干扰引起，当前面出现错误时，后面往往也会出现错误，它们之间有相关性。后面往往也会出现错误，它们之间有相关性。混合错误：混合错误：既包括随机错误又包括突发错误，因而既包括随机错误又包括突发错误，因而既会出现单个错误，也会出现成片错误。既会出现单个错误，也会出现成片错误。1.差错控制差错控制10 差错控制实现两部分功能：差错控制实现两部分功能：差错控制编码差错控制编码和和差错差错控制解码控制解码。其基本思想是为了使信源代码具有检错。其基本思想是为了使信源代码具有检错和纠错的能力，应当按照一定的规
8、则在信源编码的和纠错的能力，应当按照一定的规则在信源编码的基础上增加一些冗余码元基础上增加一些冗余码元(又称为又称为监督码元监督码元)，使这，使这些冗余码元与被传送信息码元之间建立一定的关系。些冗余码元与被传送信息码元之间建立一定的关系。在收信端，根据信息码元与监督码元的特定关系，在收信端，根据信息码元与监督码元的特定关系，可以实现检错或纠错。可以实现检错或纠错。2.2.差错控制的基本方式差错控制的基本方式11 信息码元与监督码元信息码元与监督码元 信息码元 k 监督码元r 因此，总码元数为因此，总码元数为n=k+rn=k+r。122.2.差错控制的基本方式差错控制的基本方式 差错控制编码可以
9、分为检错码和纠错码。检错差错控制编码可以分为检错码和纠错码。检错码能自动发现差错的编码；码能自动发现差错的编码；纠错码不仅能发现差纠错码不仅能发现差错，而且能自动纠正差错的编码。错，而且能自动纠正差错的编码。（1 1）反馈纠错（）反馈纠错（ARQARQ）（2 2）前向纠错（）前向纠错（FECFEC）（3 3）混合纠错（）混合纠错（HECHEC）13v 反馈纠错反馈纠错发送端需要在得到接收端正确收到所发发送端需要在得到接收端正确收到所发信息码元（通常以帧的形式发送）的确认信息后，信息码元（通常以帧的形式发送）的确认信息后，才能认为发送成功。才能认为发送成功。14反馈纠错反馈纠错有两种方式：有两种
10、方式：停停-等方式等方式和和连续工作方式。连续工作方式。15反馈纠错反馈纠错有两种方式：有两种方式：停停-等方式等方式和和连续工作方式。连续工作方式。J 在停在停-等方式中，必须从反馈信道获得等方式中，必须从反馈信道获得ACKACK（确认）（确认）帧或帧或NAK(NAK(检测到错误需要重发检测到错误需要重发)帧后才能发送下一组信帧后才能发送下一组信息。换句话说，收到息。换句话说，收到ACKACK帧则可发送下一帧，收到帧则可发送下一帧，收到NAKNAK帧则需要重发出现错误的该帧。帧则需要重发出现错误的该帧。16反馈纠错反馈纠错有两种方式：有两种方式：停停-等方式等方式和和连续工作方式。连续工作方
11、式。J 在停在停-等方式中，必须从反馈信道获得等方式中，必须从反馈信道获得ACKACK（确认）（确认）帧或帧或NAK(NAK(检测到错误需要重发检测到错误需要重发)帧后才能发送下一组信帧后才能发送下一组信息。换句话说，收到息。换句话说，收到ACKACK帧则可发送下一帧，收到帧则可发送下一帧，收到NAKNAK帧则需要重发出现错误的该帧。帧则需要重发出现错误的该帧。J 在连续工作方式中，可发送多帧，仅重发出现错误在连续工作方式中，可发送多帧，仅重发出现错误的有关帧，或重发出现错误的帧及其以后（按帧序号的有关帧，或重发出现错误的帧及其以后（按帧序号的顺序）发送的帧，通常采用滑动窗口协议以确定重的顺序
12、）发送的帧，通常采用滑动窗口协议以确定重发策略。发策略。17总结：连续工作方式比停总结：连续工作方式比停-等方式的传输效率高。等方式的传输效率高。18总结：连续工作方式比停总结：连续工作方式比停-等方式的传输效率高。等方式的传输效率高。ARQ ARQ方式对编码的纠错能力要求不高，仅需要有方式对编码的纠错能力要求不高，仅需要有较高的检错能力较高的检错能力。19v 反馈纠错反馈纠错发送端需要在得到接收端正确收到所发发送端需要在得到接收端正确收到所发信息码元（通常以帧的形式发送）的确认信息后，信息码元（通常以帧的形式发送）的确认信息后，才能认为发送成功。才能认为发送成功。v 前向纠错前向纠错接收端通
13、过纠错解码自动纠正传输中出现接收端通过纠错解码自动纠正传输中出现的差错，所以该方法不需要重传。这种方法需要采用的差错，所以该方法不需要重传。这种方法需要采用具有很强纠错能力的编码技术。其典型应用是数字电具有很强纠错能力的编码技术。其典型应用是数字电视的地面广播。视的地面广播。20v 混合纠错混合纠错是是ARQARQ和和FECFEC的结合，设计思想是对出现的的结合，设计思想是对出现的错误尽量纠正，纠正不了则需要通过重发来消除差错。错误尽量纠正，纠正不了则需要通过重发来消除差错。v 反馈纠错反馈纠错发送端需要在得到接收端正确收到所发发送端需要在得到接收端正确收到所发信息码元（通常以帧的形式发送）的
14、确认信息后，信息码元（通常以帧的形式发送）的确认信息后，才能认为发送成功。才能认为发送成功。v 前向纠错前向纠错接收端通过纠错解码自动纠正传输中出现接收端通过纠错解码自动纠正传输中出现的差错，所以该方法不需要重传。这种方法需要采用的差错，所以该方法不需要重传。这种方法需要采用具有很强纠错能力的编码技术。其典型应用是数字电具有很强纠错能力的编码技术。其典型应用是数字电视的地面广播。视的地面广播。213.3.差错的衡量指标差错的衡量指标 误码率误码率（Bit Error RatioBit Error Ratio，BERBER）是衡量在规定时）是衡量在规定时间内数据传输精确性的指标。间内数据传输精确
15、性的指标。22正确比特流00111000 接收比特流01100100 异或错误图样 01011100 突发错误长度突发错误长度b=5 b=5 3.3.差错的衡量指标差错的衡量指标 误码率误码率（Bit Error RatioBit Error Ratio，BERBER）是衡量在规定时）是衡量在规定时间内数据传输精确性的指标。间内数据传输精确性的指标。突发错误的误码影响可用突发错误的误码影响可用突发错误长度突发错误长度来表征。当来表征。当产生某突发错误时，错误图样中最前面一个的产生某突发错误时，错误图样中最前面一个的1 1和最后和最后出现出现1 1的间隔长度。的间隔长度。23第四章第四章 数据校
16、验和防碰撞算法数据校验和防碰撞算法差错检测的性质和表示方法差错检测的性质和表示方法检纠错码检纠错码差错检测差错检测防碰撞算法防碰撞算法防碰撞设计案例防碰撞设计案例24分组码分组码卷积码卷积码交织码交织码检纠错码检纠错码25分组码分组码卷积码卷积码交织码交织码检纠错码检纠错码26分组码分组码：若一个码组的监督码元仅与本码组的信息码：若一个码组的监督码元仅与本码组的信息码元有关，而与其他码元组的信息码元无关，则这类码元有关，而与其他码元组的信息码元无关，则这类码成为分组码。成为分组码。若信息码元与监督码元之间的检验关系可用线性若信息码元与监督码元之间的检验关系可用线性方程组表示，则成为线性码。反之
17、，若不存在线性关方程组表示，则成为线性码。反之，若不存在线性关系，则称为非线性码。系，则称为非线性码。符合循环性的线性码成为循环码，循环码易于用符合循环性的线性码成为循环码，循环码易于用简单的反馈移位寄存器实现。常用的循环码有循环冗简单的反馈移位寄存器实现。常用的循环码有循环冗余检验码（余检验码（CRCCRC）、里德）、里德-所罗门（所罗门（Reed-Solomon,RSReed-Solomon,RS）码及码及BCHBCH码。码。非循环码非循环码不满足循环性，常用的不满足循环性，常用的奇偶检验码奇偶检验码、汉、汉明码等。明码等。27 循环码具有循环性，即循环码中任意一个码组循环码具有循环性，即
18、循环码中任意一个码组循环一位循环一位(将最右端的码移至最左端将最右端的码移至最左端)以后，仍以后，仍为该码中的一个码组。为该码中的一个码组。如一个（如一个（7,37,3）码：）码：0000000 1001110 0000000 1001110 0011101 1010011 0011101 1010011 0100111 1101001 0100111 1101001 0111010 1110100 0111010 111010028分组码分组码卷积码卷积码交织码交织码检纠错码检纠错码29卷积码卷积码：若码组的监督码元不仅与本码组的信息码元：若码组的监督码元不仅与本码组的信息码元相关，而且与本
19、码组相邻的前相关，而且与本码组相邻的前m m个时刻输入的码组的信个时刻输入的码组的信息码元之间也具有约束关系，则成为卷积码。息码元之间也具有约束关系，则成为卷积码。卷积码的纠错能力随卷积码的纠错能力随m m的增加而提高。在编码效率与设的增加而提高。在编码效率与设备复杂性相同的前提下，卷积码的性能优于分组码，备复杂性相同的前提下，卷积码的性能优于分组码，至少不低于分组码。至少不低于分组码。30分组码分组码卷积码卷积码交织码交织码检纠错码检纠错码31交织码交织码：如果采用交织技术，把突发错误分散成随机：如果采用交织技术，把突发错误分散成随机的、独立的错误，那么用纠正所及错误的码来纠正突的、独立的错
20、误，那么用纠正所及错误的码来纠正突发错误就会获得较好的效果。利用交织技术构造出来发错误就会获得较好的效果。利用交织技术构造出来的编码称为交织编码。的编码称为交织编码。32例：33(1)(1)许用码组与禁用码组许用码组与禁用码组 若码组中的码元数为若码组中的码元数为n n，在二元码的情况下，总，在二元码的情况下，总码组数为码组数为2 2n n个。其中，被传输的信息码组为个。其中，被传输的信息码组为2 2k k个，称个，称为许用码组；其余的为许用码组；其余的2 2n n-2-2k k个码组不予传送，称为禁用个码组不予传送，称为禁用码组。码组。发端的编码任务是寻求某种规则，从总码组中选发端的编码任务
21、是寻求某种规则，从总码组中选出许用码组；而收端解码的任务则是利用相应的规则，出许用码组；而收端解码的任务则是利用相应的规则，判断及校正收到的码字符合许用码组。判断及校正收到的码字符合许用码组。（例：（例：3 3位二进制码组表示天气）位二进制码组表示天气）34（2 2）汉明距离）汉明距离 汉明距离（码距）是指每两个码组间的距离。即汉明距离（码距）是指每两个码组间的距离。即两码组对应位取值不同的个数（异或后两码组对应位取值不同的个数（异或后1 1的个数）。的个数）。例如：例如：000000和和111111之间的汉明距离为之间的汉明距离为3 3。35（3 3）编码的效率）编码的效率 编码效率越高，信
22、道中用来传送信息码元的有编码效率越高，信道中用来传送信息码元的有效利用率就越高。编码效率的计算公式为效利用率就越高。编码效率的计算公式为（4 4）码重）码重 在分组编码后，每个码组中码元为在分组编码后，每个码组中码元为“1 1”的数目的数目称为码的重量。称为码的重量。36第四章第四章 数据校验和防碰撞算法数据校验和防碰撞算法差错检测的性质和表示方法差错检测的性质和表示方法检纠错码检纠错码差错检测差错检测防碰撞算法防碰撞算法防碰撞设计案例防碰撞设计案例37 目前，目前，RFIDRFID中的差错检测主要采用奇偶检验中的差错检测主要采用奇偶检验码和循环冗余检验（码和循环冗余检验（CRCCRC）码，他
23、们都属于线性）码，他们都属于线性分组码。分组码。38 目前，目前，RFIDRFID中的差错检测主要采用奇偶检验中的差错检测主要采用奇偶检验码和循环冗余检验（码和循环冗余检验（CRCCRC）码，他们都属于）码，他们都属于线性线性分组码分组码。391 1.奇偶校验码奇偶校验码 检验码中最简单，奇偶校验码无论信息位有多少，监检验码中最简单，奇偶校验码无论信息位有多少，监督码元只有一位。在数据后面加上一个奇偶位的编码。督码元只有一位。在数据后面加上一个奇偶位的编码。奇偶检验位值的选取原则是使码字内奇偶检验位值的选取原则是使码字内1 1的数目为奇数的数目为奇数或偶数。或偶数。40（1 1）偶检验）偶检验
24、 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为1 1，反之为，反之为0.0.41（1 1）偶检验）偶检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为1 1，反之为，反之为0.0.（2 2）奇检验）奇检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为0 0，反之为，反之为1 1。42（1 1）偶检验）偶检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为1 1，反之为
25、，反之为0.0.（2 2）奇检验）奇检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为0 0，反之为，反之为1 1。例：例：1011010110110101以偶检验方式传送：以偶检验方式传送：以奇检验方式传送：以奇检验方式传送：43（1 1）偶检验）偶检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为1 1，反之为，反之为0.0.（2 2）奇检验）奇检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为0 0，反之为，反之为1
26、 1。例：例：1011010110110101以偶检验方式传送：以偶检验方式传送：101101011101101011以奇检验方式传送：以奇检验方式传送：10110101010110101044（1 1）偶检验）偶检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为1 1，反之为，反之为0.0.（2 2）奇检验）奇检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为0 0，反之为，反之为1 1。奇奇偶偶为零！奇奇偶偶为零！45（1 1）偶检验）偶检验 若字节的数据位中若字节的数据位中
27、1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为1 1，反之为，反之为0.0.（2 2）奇检验）奇检验 若字节的数据位中若字节的数据位中1 1的个数为奇数，则奇偶检验位的个数为奇数，则奇偶检验位的值为的值为0 0，反之为，反之为1 1。例：例：1011010110110101以偶检验方式传送：以偶检验方式传送：101101011101101011以奇检验方式传送：以奇检验方式传送：101101010101101010 奇偶检验码的汉明距离为奇偶检验码的汉明距离为2 2，只能检测单比特差错，只能检测单比特差错，检测错误的能力低。检测错误的能力低。463.3.行列监督码行列监
28、督码 行列监督码是二维的奇偶校验码。行列监督码的基行列监督码是二维的奇偶校验码。行列监督码的基本原理与奇偶校验码相似，不同的是每个码元要受到纵本原理与奇偶校验码相似，不同的是每个码元要受到纵和横的两次监督。和横的两次监督。47 循环冗余校验（循环冗余校验（Cyclic Redundancy CheckCyclic Redundancy Check，CRCCRC）是是RFIDRFID常用的一种差错校验方法。较强的检错能力，常用的一种差错校验方法。较强的检错能力，硬件实现简单。硬件实现简单。4.4.CRC校验校验48（1 1）生成）生成CRCCRC码的原则码的原则（2 2）CRCCRC码的校验方法
29、码的校验方法（3 3）常用的）常用的CRCCRC生成多项式生成多项式4.4.CRC校验校验49（1 1）生成）生成CRCCRC码的原则码的原则（2 2）CRCCRC码的校验方法码的校验方法（3 3）常用的）常用的CRCCRC生成多项式生成多项式4.4.CRC校验校验50 任意一个由二进制位串组成的代码都可以和一个系任意一个由二进制位串组成的代码都可以和一个系数仅为数仅为0 0和和1 1取值的多项式一一对应，即把一个长度为取值的多项式一一对应，即把一个长度为n n的代码可以表示为：的代码可以表示为：51 任意一个由二进制位串组成的代码都可以和一个系任意一个由二进制位串组成的代码都可以和一个系数仅
30、为数仅为0 0和和1 1取值的多项式一一对应，即把一个长度为取值的多项式一一对应，即把一个长度为n n的代码可以表示为：的代码可以表示为：例：例：1100101110010152 任意一个由二进制位串组成的代码都可以和一个系任意一个由二进制位串组成的代码都可以和一个系数仅为数仅为0 0和和1 1取值的多项式一一对应，即把一个长度为取值的多项式一一对应，即把一个长度为n n的代码可以表示为：的代码可以表示为：例：例：1100101110010153（1 1）生成）生成CRCCRC码的原则码的原则（2 2）CRCCRC码的校验方法码的校验方法（3 3）常用的）常用的CRCCRC生成多项式生成多项式
31、4.4.CRC校验校验54 CRC CRC码是基于多项式的编码技术。在计算码是基于多项式的编码技术。在计算CRCCRC码时，码时，发送方和接收方必须采用一个共同的生成多项式发送方和接收方必须采用一个共同的生成多项式g(x)g(x)，g(x)g(x)的阶为的阶为r,g(x)r,g(x)的最高、最低系数必须为的最高、最低系数必须为1 1。CRC CRC编码过程是编码过程是检验字段挂在原信息多项式后一起检验字段挂在原信息多项式后一起发送发送，发送发通过制定的，发送发通过制定的g(x)产生产生CRC码字，接收方则码字，接收方则通过该通过该g(x)来验证收到的来验证收到的CRC码字。码字。55 算法步骤
32、：算法步骤：将将k k位信息写成位信息写成k-1k-1阶多项式阶多项式M(X)M(X)；设生成多项式设生成多项式G(X)G(X)的阶为的阶为r r；用模用模2 2除法计算除法计算X Xr rM(X)/G(X)M(X)/G(X)，获得余数多项式，获得余数多项式R(X)R(X)；用模用模2 2减法求得传送多项式减法求得传送多项式T(X)T(X)，T(X)=XT(X)=Xr rM(X)-R(X)M(X)-R(X)，则则T(X)T(X)多项式系数序列的前多项式系数序列的前k k位为信息位，后位为信息位，后r r位为校位为校验位，总位数验位，总位数n=k+rn=k+r。561)1)若信息字段代码为若信息
33、字段代码为10110011011001，对应，对应m(x)=xm(x)=x6 6+x+x4 4+x+x3 3+1;+1;2)2)假设生成多项式为假设生成多项式为g(x)g(x)为为11001 11001，对应，对应g(x)=xg(x)=x4 4+x+x3 3+1+1；3 3）x x4 4m(x)=xm(x)=x1010+x+x8 8+x+x7 7+x+x4 4，对应的代码记为，对应的代码记为1011001000010110010000；4 4）采用多项式除法）采用多项式除法x x4 4m(x)/g(x)m(x)/g(x)，得余数为，得余数为10101010，即校验字段为即校验字段为101010
34、10；5 5）发送方发出的传输字段为）发送方发出的传输字段为1011001101010110011010，前，前7 7位为信息字段，后位为信息字段，后4 4位为校验字段；位为校验字段；6 6）接收方使用相同的生成码进行校验，接收到的多项式如果能够）接收方使用相同的生成码进行校验，接收到的多项式如果能够除尽，则正确。除尽，则正确。57练习：练习：M(X)M(X)系数序列：系数序列：1111011111110111 G(X)G(X)系数序列为：系数序列为：10011100115859（1 1）生成）生成CRCCRC码的原则码的原则（2 2）CRCCRC码的校验方法码的校验方法（3 3）常用的）常用
35、的CRCCRC生成多项式生成多项式4.4.CRC校验校验60选用的生成多项式不同，产生的循环码组也不同。选用的生成多项式不同，产生的循环码组也不同。CRC-12：CRC-16：CRC-32：CRC-CCITT：可检验可检验4KB长数据帧的数据完整性长数据帧的数据完整性61第四章第四章 数据校验和防碰撞算法数据校验和防碰撞算法差错检测的性质和表示方法差错检测的性质和表示方法检纠错码检纠错码差错检测差错检测防碰撞算法防碰撞算法防碰撞设计案例防碰撞设计案例62 在在RFID系统中，阅读器的作用范围经常有多个应系统中，阅读器的作用范围经常有多个应答器答器同时发送数据，那么就会出现通信冲突，产生数据同时
36、发送数据，那么就会出现通信冲突，产生数据相互的干扰相互的干扰，导致数据传输经常发生碰撞问题，因此需，导致数据传输经常发生碰撞问题，因此需要对防碰撞进行研究。要对防碰撞进行研究。采取防碰撞（冲突）协议，由防碰撞算法（采取防碰撞（冲突）协议，由防碰撞算法（Anti-Anti-collision Algorithmscollision Algorithms）和有关命令来实现。）和有关命令来实现。63RFID系统中存在的通信形式一般有系统中存在的通信形式一般有3种：种：1）无线广播无线广播。在一个阅读器的阅读范围存在多个应。在一个阅读器的阅读范围存在多个应答器，阅读器发出的数据流同时被多个应答器接收。
37、答器，阅读器发出的数据流同时被多个应答器接收。2）多路存取多路存取。在阅读器的作用范围内有多个应答器。在阅读器的作用范围内有多个应答器同时传输数据给阅读器。同时传输数据给阅读器。3）多个阅读器多个阅读器同时给同时给多个应答器多个应答器发送数据。发送数据。6465RFID系统中存在的通信形式一般有系统中存在的通信形式一般有3种：种：1）无线广播无线广播。在一个阅读器的阅读范围存在多个应。在一个阅读器的阅读范围存在多个应答器，阅读器发出的数据流同时被多个应答器接收。答器，阅读器发出的数据流同时被多个应答器接收。2）多路存取多路存取。在阅读器的作用范围内有多个应答器。在阅读器的作用范围内有多个应答器
38、同时传输数据给阅读器。同时传输数据给阅读器。3）多个阅读器多个阅读器同时给同时给多个应答器多个应答器发送数据。发送数据。66RFID系统中存在的通信形式一般有系统中存在的通信形式一般有3种：种：1）无线广播无线广播。在一个阅读器的阅读范围存在多个应。在一个阅读器的阅读范围存在多个应答器，阅读器发出的数据流同时被多个应答器接收。答器，阅读器发出的数据流同时被多个应答器接收。2）多路存取多路存取。在阅读器的作用范围内有多个应答。在阅读器的作用范围内有多个应答器同时传输数据给阅读器。器同时传输数据给阅读器。3）多个阅读器多个阅读器同时给同时给多个应答器多个应答器发送数据。发送数据。67SDMA:RF
39、ID系统利用天线空间分离的技术分别读取应系统利用天线空间分离的技术分别读取应答器的数据。答器的数据。FDMA:RFID系统把不同载波频率的传输通道分别提供系统把不同载波频率的传输通道分别提供给应答器用户。给应答器用户。TDMA:RFID系统把整个可供使用的通路容量按照时间系统把整个可供使用的通路容量按照时间不同分配给多个用户分别读取数据。不同分配给多个用户分别读取数据。68在在RFID系统中分为系统中分为应答器控制应答器控制和和阅读器控制阅读器控制。应。应答器控制的工作时非同步的，它对阅读器的数据没有控答器控制的工作时非同步的，它对阅读器的数据没有控制。阅读器控制时所有的应答器同时由阅读器控制
40、和检制。阅读器控制时所有的应答器同时由阅读器控制和检测。通过一定的算法，在阅读器的作用范围内从所有应测。通过一定的算法，在阅读器的作用范围内从所有应答器中选择其中一个进行通信。答器中选择其中一个进行通信。69现有的现有的RFID防碰撞算法都是基于防碰撞算法都是基于TDMA算法算法，可，可划分为划分为ALOHA防碰撞防碰撞算法和基于算法和基于二进制搜索二进制搜索（Binary Search，BS）算法两大类。）算法两大类。ALOHA防碰撞算法有防碰撞算法有ALOHA算法、时隙算法、时隙ALOHA算法算法；BS防碰撞算法有防碰撞算法有二进制搜二进制搜索算法索算法、二进制树型搜索算法二进制树型搜索算
41、法等。等。70 ALOHA ALOHA是是19681968年美国夏威夷大学一项研究计年美国夏威夷大学一项研究计划的名字，划的名字，ALOHA ALOHA网络是世界上最早的无线电网络是世界上最早的无线电计算机通信网络。计算机通信网络。ALOHAALOHA采用的是一种随机接入采用的是一种随机接入的信道访问方式。的信道访问方式。1.1.纯纯ALOHAALOHA算法算法71 阅读器检测接收到的信号，并判断有无碰撞。一阅读器检测接收到的信号，并判断有无碰撞。一旦发生碰撞，阅读器就发送命令让应答器停止发送旦发生碰撞，阅读器就发送命令让应答器停止发送，随机等待一段时间后再重新发送以减少碰撞。，随机等待一段时
42、间后再重新发送以减少碰撞。如果连续多次发生碰撞，则将导致阅读器出现错如果连续多次发生碰撞，则将导致阅读器出现错误判断，认为这个应答器不在自己的作用范围内。误判断，认为这个应答器不在自己的作用范围内。1.1.纯纯ALOHAALOHA算法算法72 纯纯ALOHAALOHA算法比较适合于阅读器只负责接收算法比较适合于阅读器只负责接收应答器发射的信号，而应答器只负责向阅读器发应答器发射的信号，而应答器只负责向阅读器发射信号的情况射信号的情况。当应答器进入射频能量场被激活。当应答器进入射频能量场被激活以后，它就发送存储在应答器中的数据，且这些以后，它就发送存储在应答器中的数据，且这些数据在一个周期性的循
43、环中不断发送，直至应答数据在一个周期性的循环中不断发送，直至应答器离开射频能量场。器离开射频能量场。1.1.纯纯ALOHAALOHA算法算法73 把时间分为离散的时间段（时隙），每段时间对把时间分为离散的时间段（时隙），每段时间对应一帧，并且应一帧，并且每个时隙长度要大于应答器回复的数据每个时隙长度要大于应答器回复的数据长度长度，应答器只能在每个时隙内发送数据应答器只能在每个时隙内发送数据。每个时隙存在每个时隙存在3 3种情况：种情况：1 1）无应答器响应：在此时隙内没有应答器发送。）无应答器响应：在此时隙内没有应答器发送。2 2）一个应答器响应：在此时隙内只有一个应答器发送，）一个应答器响应
44、：在此时隙内只有一个应答器发送，应答器能够被正确识别。应答器能够被正确识别。3 3）多个应答器响应：在此时隙内有多个应答器发送，）多个应答器响应：在此时隙内有多个应答器发送，产生碰撞。产生碰撞。2.2.时隙时隙ALOHAALOHA算法算法74 时隙时隙ALOHAALOHA算法中，应答器或成功发送或完全算法中，应答器或成功发送或完全碰撞，避免了纯碰撞，避免了纯ALOHAALOHA算法中的部分碰撞，提高了算法中的部分碰撞，提高了信道的利用率。但这种方法需要一个同步时钟以使信道的利用率。但这种方法需要一个同步时钟以使阅读器阅读区域内的所有应答器的时隙同步。阅读器阅读区域内的所有应答器的时隙同步。2.
45、2.时隙时隙ALOHAALOHA算法算法75 ALOHA ALOHA算法的一种扩展算法算法的一种扩展算法Framed Slotted Framed Slotted ALOHA(FSA)ALOHA(FSA)算法。把算法。把N N个时隙组成一帧，应答器在个时隙组成一帧，应答器在每个帧内随机选择一个时隙发送数据，适于传输每个帧内随机选择一个时隙发送数据，适于传输信息量较大的场合。信息量较大的场合。3.3.帧时隙帧时隙ALOHAALOHA算法算法76现有的现有的RFID防碰撞算法都是基于防碰撞算法都是基于TDMA算法，可算法，可划分为划分为ALOHA防碰撞算法和基于二进制搜索防碰撞算法和基于二进制搜索
46、（Binary Search，BS）算法两大类。）算法两大类。ALOHA防碰撞算法有防碰撞算法有ALOHA算法、时隙算法、时隙ALOHA算法；算法；BS防碰撞算法有防碰撞算法有等。等。77 只有应答器序列号与阅读器查询的前缀相符的只有应答器序列号与阅读器查询的前缀相符的标签才响应阅读器的命令而发送其序列号。当只有标签才响应阅读器的命令而发送其序列号。当只有一个标签响应的时候，阅读器可以成功识别标签，一个标签响应的时候，阅读器可以成功识别标签，但当有多个标签响应的时候，阅读器就把下一次循但当有多个标签响应的时候，阅读器就把下一次循环中的查询前缀增加一个比特环中的查询前缀增加一个比特0 0，通过不
47、断早呢更，通过不断早呢更加前缀，阅读器就能识别所有的标签。加前缀，阅读器就能识别所有的标签。4.4.二进制搜索算法二进制搜索算法78 设阅读器范围内有设阅读器范围内有4 4个标签，个标签，A:10100111A:10100111，B:10110101B:10110101，C:1C:101011110101111，D:10111101.D:10111101.1)1)要求区域内所有标签应答，发现碰撞要求区域内所有标签应答，发现碰撞101101？1 1？1 1，D1D1，D3D3，D D4 4位发生碰撞，将碰撞最高位位发生碰撞，将碰撞最高位D4D4置置0 0，高于，高于D4D4位不变化，低于位不变化
48、，低于D4D4位位置置1 1，可得下一次命令参数，可得下一次命令参数10101111.10101111.2 2）发送）发送1010111110101111，标签，标签A A和和C C应答，解码数据为应答，解码数据为10101010？111111，D3D3位位发生碰撞，将发生碰撞，将D3D3位置位置0 0，D0D1D2D0D1D2置置1 1，得到，得到10100111.10100111.3 3）重复步骤直到有唯一标签。）重复步骤直到有唯一标签。79 将这些信息包随机地分为两个分支。遵循将这些信息包随机地分为两个分支。遵循“先入后先入后出出”的原则，将所有第一个分支的信息都成功传输后，的原则，将所
49、有第一个分支的信息都成功传输后，再来传输第二个分支。再来传输第二个分支。5.5.二进制树型搜索算法二进制树型搜索算法解决碰撞的时解决碰撞的时间间隔间间隔(CRI)=1180 当碰撞正在进行时，新加入这个系统的信当碰撞正在进行时，新加入这个系统的信息包禁止传输信息，直到该系统的碰撞问题得息包禁止传输信息，直到该系统的碰撞问题得以解决，并且所有信息包成功发送完后，才能以解决，并且所有信息包成功发送完后，才能进行新的信息包的传输。进行新的信息包的传输。5.5.二进制树型搜索算法二进制树型搜索算法81第四章第四章 数据校验和防碰撞算法数据校验和防碰撞算法差错检测的性质和表示方法差错检测的性质和表示方法
50、检纠错码检纠错码差错检测差错检测防碰撞算法防碰撞算法防碰撞设计案例防碰撞设计案例82 MCRF250 MCRF250芯片是非接触可编程无源芯片是非接触可编程无源RFIDRFID器件，工作频器件，工作频率（载波）为率（载波）为125kHz125kHz。有两种工作模式：初始模式（。有两种工作模式：初始模式（NatNativeive）和读模式。）和读模式。初始模式指芯片具有一个未被编程的存储阵列，调制初始模式指芯片具有一个未被编程的存储阵列，调制方式为方式为FSKFSK，数据码为，数据码为NRZ.NRZ.读模式值在接触和非接触方式编程后永久工作模式，读模式值在接触和非接触方式编程后永久工作模式，配置
