DS2433在即插即用设备部件认证中的应用研究与仿真

2014-04-26刘琼

长沙民政职业技术学院学报 2014年2期

关键词：二叉树搜索算法结点

刘琼

（湖南工业职业技术学院，湖南长沙 410082）

DS2433在即插即用设备部件认证中的应用研究与仿真

刘琼

（湖南工业职业技术学院，湖南长沙 410082）

即插即用设备部件的关键技术是身份识别，利用DS2433器件能让设备部件实现身份识别和自我描述。文中介绍了DS2433的结构、存储器功能命令，利用二叉树路径搜索算法设计了1-Wire总线上所插接的多个DS2433在部件即插即用中质询与响应认证过程，并通过一个具体的Proteus仿真实例，验证了系统的可行性和稳定性。

DS2433；即插即用；二叉树；认证

1.引言

在竞争激烈的嵌入式电子设备市场上必须解决的问题是确保原设备部件的质量，防止产品被非法复制，这些因素均是一个设备或系统成功与否的关键。设备上众多部件的硬件和软件知识产权的安全管理，是实现这个关键的唯一途径。因此，设备部件身份识别在系统中至关重要。设备的主机要能够识别各个重要部件，并能实时检测到新插入的部件，实时获取其合法身份信息，并在存储器中添加该部件的记录。

DS2433是一款基于1-Wire总线的4096位EEPROM，具有3引脚PR-35小体积封装形式或8引脚SOIC封装，能安装到印制电路板上或进行引线，其典型应用包括：存储校准系数、电路板标识认证以及产品升级状态等，很适合运用到即插即用系统中。它除了具有一般1-Wire器件的特性外，还有一些特殊的结构和要求。

2.DS2433的内部基本结构

DS2433内部结构如图1所示。?DS2433带有一个由工厂光刻的注册码，其中包括：48位唯一序列码、8位CRC校验码和8位家族码(23h)。它的4096位EEPROM分为16页，每页256位。它的256位暂存器作为一个附加页面，在写存储器时可用作缓冲器使用。数据先被写入暂存器中，在此对其进行校验。随后采用复制暂存器命令将数据传送到EEPROM中。64位注册码为每个器件提供了一个保证唯一的认证标识，确保每个器件的绝对可追溯性，当有多个DS2433同时挂接在1-Wire总线上并形成本地网络时，可作为设备部件的节点地址使用。数据按照1-Wire协议串行传送，仅需一条数据线和一条地线。

图1 DS2433内部结构图

3.DS2433的存储器功能命令及使用方法

3.1 Write Scratchpad[0Fh]写暂存器

Write Scratchpad命令适用于数据存储器和寄存器页中的可写地址。为了保证暂存器中的数据能够被正确复制到存储器阵列中，用户必须保证写暂存器命令中的32个数据字节开始于一个有效行边界处，发出Write Scratchpad命令后，主机(微控制器)必须首先发送2个字节的目标地址，接着发送要写入暂存器的数据。

3.2 Read Scratchpad[AAh]读暂存器

Read Scratchpad命令可以用来校验目标地址和暂存器数据的完整性。主机发送命令代码后开始读取数据。开头的两个字节是目标地址，下一个字节是结束偏移量/数据状态字节，接着是暂存器数据。

3.3 Copy Scratchpad[55h]复制暂存器

Copy Scratchpad命令用来将暂存器中的数据复制到EEPROM，发出Copy Scratchpad命令后，主机必须提供一个3字节的授权模式，该数据应该通过紧邻此条命令的前一个Read Scratchpad命令获得。该3字节模式数据必须与三个地址寄存器（依次为TA1，TA2，E/S）中的数据正确匹配。

3.4 Read Memory[F0h]读存储器

Read Memory命令通常用于从DS2433读取数据。发出命令后，主机需要提供2个字节的目标地址。在这两个字节之后，主机开始读取始于目标地址的数据。

4.DS2433的基本操作流程

DS2433的基本操作流程：初始化→ROM功能命令→存储器功能命令→数据传输。与一般的1-Wire器件类似，所有数据处理均从初始化开始，数据传输都是从低位开始。初始化过程由主机发送的复位脉冲和DS2433发送的在线应答脉冲组成。应答脉冲用于通知主机，DS2433已挂接在总线上，并已准备就绪。一旦主机检测到在线应答脉冲，就可以发出四条常用ROM功能命令中的一个。所有ROM功能命令的字长均是8位，表1是这些ROM命令的简要介绍。

表1 DS2433的ROM常用操作命令

5.二叉树搜索算法

5.1 搜索操作的基本信息

1-Wire总线器件的64位ROM注册码由8位CRC校验码、48位序列号、8位家族代码构成，这64位注册码分布于一棵二叉树同根节点到某个叶子节点的64条边上，树中每一节点的左分支对应编码0，右分支对应编码1。搜索总线上所有ROM编码的过程就是按某种算法遍历该二叉树由根节点到所有叶子节点的所有“路径”的过程。

按照1-Wire总线的特性，总线上的从机之间为“线与”的关系。当主机发出搜索命令后，所有从机同时发送自身ROM注册码中的最低有效位（即家族代码最低位），结果相当于全部最低有效位的逻辑与；主机读入从机发送的第n位数据的原码后，再启动下一位操作，接着从机发送第n位数据的取反值，主机再读入第n位数据的取反值；从两次读入的情况可以对ROM注册码的第n位做出判断，如表2所示。

表2 ROM编码第i位的判断情况

搜索过程中，主机必须向总线上的从机发回一个指定位a；如果从机ROM注册码的当前位的值与a匹配，则继续参与搜索过程；若从机器件的当前位与之不匹配，则该器件转换到等待状态，并保持等待状态直到下一个1-Wire复位信号到来。其余63位ROM码的搜索依然按照上述“读入两位，写出一位”的模式进行重复操作。按照这种搜索算法进行下去，最终除了一个从机器件外所有从机将进入等待状态，经过最后一轮检测，就可得到最后保留（未进入等待状态）器件的ROM注册码。在后续搜索过程中选用不同的路径来查找另外器件的ROM注册码。

5.2 基于二叉树路径搜索的ROM编码搜索算法

图2给出了参照二叉树路径搜索一条1-Wire总线所有器件64位的ROM注册码的流程，搜索过程选择“左子树优先”。下面结合表2讨论搜索算法的实现细节，搜索到的注册码保存于ROMCODE数组。

由表2可知，搜索过程中将遇到四种不同的2位组合，下面逐一进行讨论研究：

①“11”表明总线上无从机，主机执行下面的指令后直接返回：if(bit_1==1&&bit_2==1)return 1。

②“01”表明未被屏蔽器件的ROM注册码当前位均为0，这些器件余下的注册码位全部分布于左分支路径（即左子树），故置ROMCODE[n]=0，随后主机向总线写0，使为0的从机继续通信，搜索左子树，并屏蔽为1的从机。

③“10”表明未被屏蔽器件的ROM注册码当前位均为1，这些器件余下的编码位全部分布于右分支路径（即右子树），故置ROMCODE[n]=1，随后主机向总线写1，使为1的从机继续通信，搜索右子树，并屏蔽为0的从机。

上述“01”和“10”组合情况处理的示意性代码如下：if (bit_1!=bit_2){ROMCODE[n]=bit_1;Write_DQ(bit_1);}

④“00”表明未被屏蔽器件的ROM注册码当前位有0和1，是最为复杂的一种情况，因为当前位出现搜索分支，其左子树与右子树均存在。第一次搜索从器件的注册码时，如果左子树和右子树都存在，则需要记录该分叉结点的深度，并沿左子树的方向向下搜索。当搜索深度达到64时，获得一个从器件的注册码，并取出该搜索路径最后的分叉结点的深度，然后主机执行第二次搜索过程。在该搜索过程中，如果结点的深度值大于最后一个分叉结点的深度，按照“左子树优先”的原则，可认为当前位为0，并向总线写入此值，对左子树进行搜索；如果结点的深度值小于最后一个分叉结点的深度，则要根据上次搜索最后一个分叉结点注册码的相应位果是否为0来决定是否记录深度值，并向总线发送这位；如果结点的深度值等于最后一个分叉结点的深度，说明“左子树已搜索完”，则当前位为1，并向总线写入此值，对右子树进行搜索。这样，每搜索到一个深度为64的叶子结点，就会得到一个从器件的注册码，一直搜索到记录中没有分叉结点为止。

搜索算法流程图2中，ROMCODE[n]表示64位的变量存放器件的ROM注册码，Level记录当前分支结点的位置，Last_Level记录前次搜索的最后分支的结点位置，n反映二叉树当前搜索深度，也表示搜索的位序。

图2 1-Wire总线所有器件ROM注册码的搜索算法流程图

6.DS2433在即插即用设备部件认证中的仿真实例

搜索ROM注册码的技术是一个实现即插即用技术的途径，当设备每次上电时，主机能对设备部件进行动态管理。对于新增加的或更改的部件，主机可以动态地获得它的注册码，从而可以在数据库中增加此设备的记录，并进行质询与认证，判断其是否合法。对于从系统中撤离的设备，由于主机没有检测到它的注册码，所以可在数据库删除此设备的记录。此算法已经在作者主持的一项课题中得到了很好的应用，实现了在线检测设备的各部件的注册码。

根据DS2433在即插即用设备部件认证中的要求，设计了多个DS2433与微控制器连接的Proteus仿真实例，如图3所示。以激光打印为例，用一个DS2433作为硒鼓的认证模块，用另一个DS2433作为墨粉盒的认证模块，一个DS18B20作为设备温度检测模块。该仿真实例用DS2433实时存储了所有部件的注册码，完全满足即插即用系统进行校验、质询、认证的要求。通过运行测试，验证了本文提出的搜索算法及器件即插即用功能设计的可靠性与稳定性。