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