1-WIRE搜索算法详解（1）

美信公司（）苼产了许多1-Wire?器件产品硬件电路极致简单，而相应软件就显得复杂美信网站的《应用笔记187》介绍了单线ROM搜索算法，并提供了的源代码该算法较为复杂，而且是通用于多平台（windows\JAVA等）的API无法直接在KeilC上调试并写入单片机。本人在学习理解其算法后适当修改源代码，并作仩了详细的注释和图解代码在KeilC环境下调试通过，并在一个挂接4个DS18B20的小型1-Wire环境中测试成功顺利获取4个ROM码。现把算法分析及测试过程成文洳下其中算法部分保留了大部分AN187的内容，但作了许多修改和补充原文可参见。本文介绍的搜索算法及源代码对任何现有的或将要推絀的1-Wire器件都是有效的。

硬件连接：4个DS18B20并接MCU为笙泉MG82G516仿真芯片（其他普通51系列都可，仿真芯片可以方便调试）软件为Keil

2.笙泉THO65B+仿真器（可仿真51芯片）

4.全家福（arm开发板板仅安装芯片及供电用）

图1中，4个DS18B20并接红黄黑三线为电源、信号、地，绿色线通黄色线接逻辑分析仪。原来逻輯分析仪从单片机端采集1-Wire信号但实测中主机拉高电平（从机低电平）时，逻辑分析仪采集到一个尖刺脉冲造成分析仪识别1-Wire协议失误；後将采集线接到从机端，信号正常

图2是笙泉THO65B+仿真器，USB接口可仿真51系列，方便程序调试该仿真器芯片型号为MPC82G516，类似于STC15F2K60S2为1T单片机，片仩64KB

图3为逻辑分析仪十分小巧，支持8路信号输入最高采样速率24M，实际一般使用16MUSB接口，附送软件图4为arm开发板板，本例中主要功能仅为提供CPU插座及供电1-Wire器件连接是相当简单的。

 再给出一个用逻辑分析采集到的ROM搜索的全过程相关图片有了这个分析仪，就可以十分方便地讀出搜索到的ROM码还能通过程序执行时产生“波形”分析调试代码，也可以方便的测定延时函数的时间

的1-Wire?器件都带有一个64位的唯一注冊码，生产时通过激光刻蚀在内部只读存储器内(ROM)用于在1-Wire网络中通过1-Wire主机对其寻址。如果1-Wire网络中从机器件数量不定且ROM码未知则可采用搜索算法查找这些码。下表是64Bit

图6、通过逻輯分述仪采集到的1-Wire信号

1. 上图是逻辑分析仪在ROM搜索到1个ROM时1-Wire总线上采集到的信号，可见搜索耗时15ms；

2. 因低位先传送逻辑分析仪上显示低位在左邊；

3. 信号自左到右分别为：复位R、存在脉冲、主机发搜索命令８位、从机回复64位ROM码（包括家族码0x28、48位ROM、8位CRC码）

4. 分析软件识别出了1-Wire协议，在信号顶部标示了内容和数位阅读时相当直观。

5. 将图6中家族码的部分放大如图7

图7. 搜索过程中采集的家族码部分放大图

1.    家族码一共为8位，圖中有3通道信号最上面第1通道从1-Wire总线采集，第2通道是“1写”程序时通过转换指定单片机引脚得到（进入该程序时置位退出前复位）；苐3路为“2读”信号；均为高电平；

搜索算法采用的是二叉树型结构，搜索过程沿各分节点进行直到找到器件的ROM码即叶子为止；后续的搜索操作沿着节点上的其它路径进行，按照同样的方式直到找到上的所有器件代码本文后面提供了一个简单示例：4个ROM，每个仅取4位构造叻一棵二叉树，并在此示例上推导出搜索算法的许多细节及实现

pulse)时隙将1-Wire总线上的所有器件复位；成功地执行该操作后，发送1 个字节的搜索命令；搜索命令使1-Wire器件准备就绪、开始进行搜索操作

搜索命令分为两类：标准搜索命令(F0 hex)用来搜索连接到网络中所有器件；报警或有条件搜索命令(EC hex)只用来搜索那些处于报警状态下的器件，这种方式缩小了搜索范围可以快速查找到所需要注意的器件。本文附带代码仅使用叻标准搜索命令

搜索命令发出之后，开始实际的搜索过程首先总线上的所有从机器件同时发送ROM码(也叫注册码)中的第一位(最低有效位) (参見图1)。与所有的1-Wire通信一样无论是读取数据还是向从机器件写数据，都由1-Wire主机启动每一位操作按照1-Wire协议设置特性，当所有从机器件同时應答主机时结果相当于全部发送数据位的逻辑；从机发送其ROM码的第一位后，主机启动下一位操作、接着从机发送第一位数据的补码；从兩次读到的数据位可以对ROM码的第一位做出几种判断(参见下表)上述二次读取1-Wire总线上当前位ROM码的正码和反码的操作，本文简述为“二读”

按照搜索算法的要求“二读”后1-Wire主机必须向总线上的从机发回一个指定位，称为“一写”；如果从机器件中ROM码的当前位的值与该数据位匹配则繼续参与搜索过程；若从机器件的当前位与之不匹配，则该器件转换到休眠状态直到下一个1-Wire复位信号到来被再次唤醒。其余63位ROM码的搜索依然按照这种‘读两位’、‘写一位’的模式进行重复操作

按照这种搜索算法进行下去，最终除了一个从机器件外所有从机将进入等待狀态经过一轮检测，就可得到最后保留(未进入等待状态)器件的ROM码在后续搜索过程中，选用不同的路径(或分支)来查找其它器件的ROM码需偠注意的是本文ROM码的数据位用第1位(最低有效位)到第64 位(最高有效位)表示，而不是第0位到第63位的模式；这样设置允许将差异位置计数器初始值置为0为以后的比较提供了方便。

上述过程可简述为“二读一写”“二读”结果为“00”，主机就判定这一位是“差异位”也可称为“沖突位”“混码位”。举例来说“二读”就相当于“老师问名”，设想学生的名字就是64位ROM码老师第1问时学生反应为：“1的不吭声，0就高喊到”；第2问时学生反过来：“0的不吭声1的高喊到”，老师通过二次答复就可分辨：“不吭声+不吭声”表示一个学生也没有；“不吭聲+到”表示大家都是1“到+不吭声”表示大家都是0；而“到+到”收表示有0有1。试想如果有0有1，只要有1个喊到老师就能听到，这种合成效果就是所谓的“线与”当然这里应称为“声与”。

搜索到“差异位”时主机如何确定搜索方向（0还是1），这是本算法的核心问题這也是典型的“二叉树遍历”算法。或许有人会提出一种“笨”算法就是穷举64位组合，从000…000到111…111遍历有应答的从机就会被一个一个找絀来，这确实是一种简单的“笨”算法在许多地方很有用，但对于64位ROM来说假设一位的访问需要100us，64位则需要6.4ms穷举全部ROM码有2⁶⁴=1844亿亿，极端嘚遍历时间为37亿年这确实是一种无法实现的笨办法。

下表列出了1-Wire主机和从机的搜索过程：

从上表可以看出：如果所有总线上的器件在当前位具有相同值，那么只有一条分支路径可选；总线上没有器件响应嘚情况是一种异常状态可能是要查找的器件在搜寻过程中与1-Wire总线脱离。如果出现这种情况应中止搜索，并发出1-Wire复位信号起始新的搜索過程如果当前位既有0也有1，这种情况称为位值差异它对在后续搜索过程中查找器件起关键作用。搜索算法指定在第一轮查询中若出现差异(数据位/补码 = 0/0)则选用‘0’路径。注意：这一点是由本文档中介绍的特定算法决定的其它算法中或许首先选用‘1’路径。算法需要记錄最后一次值差异的位置以供下一次搜索使用

本文介绍的搜索算法是一个通用的程序，Maxim工程师极巧妙地设计了一些变量只要在搜索前設置这些变量的初始值，程序就能完成不同的搜索功能下文中会列出这些变量，但理解其奥秘需要花点时间比如程序对最初8位ROM中出现嘚最后一次位差异设置了一个专门的变量保持跟踪，因为64位注册码的前8位是家族码利用此变量可以在器件的搜索过程中可以按照其家族碼进行分类。运用该变量可以有选择性地跳过1-Wire器件的整个分组如需进行选择性的搜索，可参考关于高级变量搜索的详细解释

64位ROM码中还包含8位码(CRC)；CRC值用于验证是否搜索到正确的ROM码。ROM码的排列如图1所示关于CRC校验的原理，内容丰富到需要专文论述这里不详述，可参见Maxim网站楿关笔记

1-Wire搜索算法详解（2）

要理解算法，或制定算法我们需要通过一个实例来解释：

假设1-Wire挂有4个ROM如上表， 这里ROM码仅设4位编号从1到4，洏实际器件ROM位序号从1到64右图则是按“先0后1”遍历顺序所构造的二叉树，可见第一次遍历得到ROM4：0001第二次遍历得到ROM1：0011，依次类推图中打囿⊕的位置就是分叉点，即差异位（或称为混码位）

现在根据上例观察各次遍历，提炼出算法及实现细节：

1.第一次遍历时第1位Bit1时遇到苐一个差异位，按左序遍历即先0后1的顺序我们选择0（称为方向0）；Bit2不是差异位，算法根据“二读”后方便地选0；Bit3又是差异位再选择方姠0，Bit4也不是差异位遍历结果得到ROM4。这里可得出结论1：凡遇到新的差异位选择0。

2.第二次遍历按实例分析，Bit1处再选择方向0；Bit2取0；Bit3不能再選0了改选1；Bit4取1；得到ROM1。问题随即产生：问题1、Bit1为何走0此处确为差异位，但已不是首次经过不能套用结论1。问题2、Bit3处为何改走1简单汾析问题2可得出结论2：凡上次遍历时最后一个走0的差异位本次应走1。很明显“上次遍历时最后一个差异位”下的左分支已经走过，这次應该往右走了再回答问题1可以得到结论3：凡上次遍历时最后一个走0的差异位之前的差异位仍按上次遍历的老路走。这个结论比较拗口觀察实例来解释：Bit3是差异位，右分支还没走过现在我要走Bit3下边的右分支，Bit3之前当然是按上次路线来走了

3．然后是否就可以进行第三次遍历了呢？且慢有一个重要的问题还没处理。第二次遍历前那个“上次遍历时最后一个走0的差异位”应该Bit3，我们先设置一个变量LastDiscripancy来记住这个值即LastDiscripancy=3；从前面的分析我们知道，这个变量的值是决定本次遍历时算法在哪个位置改道的依据而且这个变量在本次遍历全过程中應该保持不变的，如果在该节点前或后有任意多少的差异位均按结论1（新差异位）和结论3（老差异位）来处理。也可以理解成结论2在一佽遍历中必须适用且仅适用一次这也就是每次遍历都能找出一个新的ROM的核心所在。那么第二次遍历后变量LastDiscripancy应该指向哪个节点呢？直接觀察就可发现应该指向Bit1

4．那么算法中如何实现每次遍历后变量LastDiscripancy的更新呢？要知道这个指针随着每次遍历在或上或下地移动如第一次遍曆后指向Bit3，第二次后指向Bit1第三次后指向Bit2。还有第一次开始遍历前、第四次遍历后该变量又指向哪里呢？由于实际ROM多达64位从机如果数據多的话，差异位也会随之增加所以算法再引入一个变量Last_Zero，在每次遍历前设为0即指向起始位置前，然后遍历ROM码的1-64位时该变量始终指姠最后一个走0的差异位，等到遍历完成后将该变量的值赋给LastDiscripancy即可。这样我们再观察实例的第二次遍历Last_Zero遍历前为0，Bit1时符合“走0的差异位”，于是Last_Zero=1后续Bit3尽管是差异位，但不走0所以遍历完成后，该值还是1最后交给LastDiscripancy，自己又指向0为第三次遍历作好准备。

5．第三次遍历僦变得顺理成章：LastDiscripancy=1Bit1处需运用结论2，算法改走1而且第三次遍历让Bit2成为了“最后一个走0的差异位”，第四次遍历就在此处改走1了第四次遍历搜索到最后一个rom，但还得告诉程序结束信号从而退出搜索。结束信号用什么判定4个ROM循环4次？当然不是上述表图只是举例，实际總路线上挂接多少从机是未知的答案还是利用变量LastDiscripancy来判定，开始搜索前自然有LastDiscripancy=0但一旦进入搜索程式，每次遍历后该变量总是指向ROM码中間可能的某一位（1-64）直至遍历到最后一个从机，这时必定是所有差异位均走1如果Last_Zero保持为初始值0，遍历过程中未作修改遍历完成后LastDiscripancy=Last_Zero=0。鉯此为条件可判定搜索全部完成

6．综上，当算法执行到一个差异位时需判断区分为三种情况：首次遇到型、上次最后走0型、上次非最後走0型。可以通过二个变量的比较来表征这三种情况即比较当前搜索的位id_bit_number和上次最后走0的位LastDiscrepancy 的大小来判别，如下表：

表3. 搜索路径方向的確定

其中变量Id_bit_number表示当前搜索位每一次遍历时从1至64步进；

变量search_direction表示当前节点经过二读及判断后确定的搜索方向，是0還是1；

其他变量说明请参见流程图中附文

图9列出了对一个从器件进行搜索的流程图；注意：流程图附文中列出了涉及到的一些关键变量，并进行了说明在本文描述内容、流程图及源代码中也将用到这些名称的变量。

1、 该流程最终被代码表达成一个函数可以执行对一个器件的搜索；

2、 当主机复位后未收到从机的存在脉冲、最后设备变量LastDeviceFlat=1、二读后均为1这三种情况，函数执行初始化变量后返回False；

3、 红色虚线框中流程是针对差异位的处理，分3种情况走不同分支该部分是本算法的精华；

4、 红色虚线框中最下面的二个绿色背景框，是对家族码嘚处理适用于多类型器件混合网络的指定处理，如单类器件组网可以跳过此部分；

5、 图中各指令框边上列出了部分变量、变量比较、變量赋值表达式，以方便后续理解代码；

上述流程图算法实际上是一个通用的函数，可实现一次从机ROM码的搜索在附录代码中即为OWSearch（）函数，执行一次该函數可以有以下几种结果：

1.复位信号发出后，未收到任何应答信号表明无器件挂接或硬件电路故障，函数返回False退出；

2.上轮搜索中程序判斷为最后一个器件本次执行函数也是返回False退出；

3.在某位“二读”时出现“11”的信号，这是执行中出现的异常函数也是返回False退出；

4.首次戓再次进入此函数，信号也正常函数将搜索到总线上的第一个器件ROM码；

在上述4种结果中，第1和第3是异常后退出第2是器件搜索完毕后结束退出。第4是首次执行搜索和再次执行搜索这二种情况可以表述后下面二个函数：First和Next，二个函数通过对LastDiscrepancy、LastFamilyDiscrepancy、LastDeviceFlag和ROM_NO值的处理利用同一流程實现了两个不同类型的搜索操作；这两个操作是搜索1-Wire器件ROM码的基础，本文附后列出了全部代码可供测试。

‘FIRST’操作是搜索1-Wire总线上的第一個从机器件该操作是通过将LastDiscrepancy、LastFamilyDiscrepancy和LastDeviceFlag置零，然后进行搜索完成的最后ROM码从ROM_NO寄存器中读出。若1-Wire总线上没有器件复位序列就检测不到应答脉沖，搜索过程中止

‘NEXT’操作是搜索1-Wire总线上的下一个从机器件；一般情况下，此搜索操作是在‘FIRST’操作之后或上一次‘NEXT’操作之后进行；保持上次搜索后这些值的状态不变、执行又一次搜索即可实现‘NEXT’操作之后从ROM_NO寄存器中来读出新一个ROM码。若前一次搜索到的是1-Wire上的最后┅个器件则返回一个无效标记FALSE，并且把状态设置成下一次调用搜索算法时将是‘FIRST’操作的状态

c)例举了三个器件的搜索过程，为简单起見该示例中的ROM码只有2位具体过程有二个图和一个表。与本文中的示例也大同小异所以本文不再列出。有兴趣的可直接阅读AN187应用笔记

囿3种利用同一组状态变量LastDiscrepancy、LastFamilyDiscrepancy、LastDeviceFlag、ROM_NO实现的高级变量搜索算法，这几种高级搜索算法允许来指定作为搜索目标或需要跳过搜索的器件的类型(家族码)以及验证某类型的器件是否在线(参见表4)

如果理解了算法原理及各个变量的作用，不难理解“高级变量搜索”的三种功能本文附带玳码为简便起见，删除了这些内容读者如感兴趣可直接访问AN187应用笔记。

‘VERIFY’操作用来检验已知ROM码的器件是否连接在1-Wire总线上通过提供ROM码並对该码进行目标搜索就可确定此器件是否在线。首先将ROM_NO寄存器值设置为已知的ROM码值，然后将LastDiscrepancy和LastDeviceFlag标志位分别设置为64 (40h)和0； 进行搜索操作嘫后读ROM_NO的输出结果；如果搜索成功并且ROM_NO中存储的仍是要搜索器件的ROM码值，那么此器件就在1-Wire总线上

SETUP’操作就是用预置搜索状态的方式首先查找一个特殊的家族类型，每个1-Wire器件都有一个字节的家族码内嵌在ROM码中(参见图1)主机可以通过家族码来识别器件所具有的特性和功能。若1-Wire總线上有多片器件时通常是将搜索目标首先定位在需注意的器件类型上。为了将一个特殊的家族作为搜索目标需要将所希望的家族码芓节放到ROM_NO寄存器的第一个字节中，并且将ROM_NO寄存器的复位状态置零然后将LastDiscrepancy设置为64 (40h)；把LastDeviceFlag和LastFamilyDiscrepancy设置为0。在执行下一次搜索算法时就能找出所期望嘚产品类型的第一个器件；并将此值存入ROM_NO寄存器需要注意的是如果1-Wire总线上没有挂接所期望的产品类型的器件，就会找出另一类型的器件所以每次搜索完成后，都要对ROM_NO寄存器中存储的结果进行校验

SETUP’操作用来设置搜索状态以便跳过搜索到的指定家族中的所有器件，此操莋只有在一个搜索过程结束后才能使用通过把LastFamilyDiscrepancy复制到LastDiscrepancy，并清除LastDeviceFlag即可实现该操作；在下一搜索过程就会找到指定家族中的下一个器件如果当前家族码分组是搜索过程中的最后一组，那么搜索过程结束并将LastDeviceFlag置位

要注意的是，FamilySkipSetup和TargetSetup函数实际上并没有进行搜索操作它们只不过昰用来设置搜索寄存器，以便在下一次执行‘NEXT’操作时能跳过或找到所期望的类型表4. 搜索变量状态的设置

本文提供的搜索算法可以找出任意给定的1-Wire器件组中独一无二的ROM码，这是保证多点1-Wire总线应用的关键已知ROM码后就可以对逐一选定的某个1-Wire器件来进行操作。本文还对一些变量搜索算法做了详细论述这些变量搜索算法能够查找或跳过特定类型的1-Wire器件。

或许Maxim觉得1-Wire 器件的软件开销让人望而生畏因此设计了专用芯片DS2480B系列，可以实现串口到1-Wire线路的驱动包括与本文档中相同的搜索算法，详细资料请参阅DS2480B数据资料和应用笔记192；以及DS2490 芯片实现USB口到1-Wire桥接，也可实现了整个搜索过程；还有一款I2C桥接1-Wire的芯片使用这些芯片，无须编写复杂算法只需向芯片发送命令即可实现多种控制，其最夶优点是芯片中集成了1-Wire操作控制的硬件省却了1-Wire复杂的时序控制，因而其他编程可使用高级语言来编写甚至直接使用Maxim提供的平台软件在PC仩arm开发板1-Wire应用系统。

《详解3》中将给出了实现搜索过程的例程并给出了‘C’程序代码，需要注意的是并没有给出“复位、读写总线”等函数的C代码，而是提示我们可以调用TMEX API实现考虑到本程序在51系列平台上独立调试，代码中提供了这些函数关于TMEX API和其它一些1-Wire API的详细资料請参考。

另须注意：低级函数对时序控制有极高要求其延时代码必须确保符合读写时序，本文程序在1T单片机MPC82G516调试通过如改用其他1T单片機或12T单片机，必须对延时函数重新调试参数以获得1-Wire规定时序。另：代码在实测中也适用于“寄生供电”即不给从机连接VCC电源，代码也鈳正常工作关于“寄生供电”的详细信息，请参见其他应用笔记

1-Wire搜索算法详解（3）