1Wire搜索算法.docx
《1Wire搜索算法.docx》由会员分享，可在线阅读，更多相关《1Wire搜索算法.docx（33页珍藏版）》请在冰点文库上搜索。
1Wire搜索算法
1-Wire搜索算法
Dec05,2003
摘要：
Maxim的1-Wire®器件都带有一个64位的唯一注册码，存储在只读存储器内（ROM），能够在1-Wire网络中通过1-Wire主机对其寻址。
如果1-Wire网络中从机器件的ROM码是未知的，则可采用搜索算法查找这些码。
本文详细说明了搜索算法的原理，并提供了一个范例，便于用户使用。
该算法对任何现有的或将要推出的1-Wire器件都是有效的。
绪论
Maxim的每片1-Wire器件都有唯一的64位注册码，它存储在只读存储器（ROM）中。
在1-Wire网络中，注册码用于1-Wire主机对从机器件进行逐一寻址。
如果1-Wire网络中从机器件的ROM码是未知的，可以通过搜索算法来找到此码。
本文不仅详细地解释了搜索算法，而且还提供了实现快速整合的例程。
该算法适用于任何具有1-Wire接口特性的现有产品及未来产品。
图1.64位唯一的ROM注册码
搜索算法
搜索算法采用的是二叉树型结构，搜索过程沿各分节点进行，直到找到器件的ROM码即叶子为止；后续的搜索操作沿着节点上的其它路径进行，按照同样的方式直到找到总线上的所有器件代码。
搜索算法首先通过复位（reset）和在线应答脉冲（presencepulse）时隙将1-Wire总线上的所有器件复位；成功地执行该操作后，发送1个字节的搜索命令；搜索命令使1-Wire器件准备就绪、开始进行搜索操作。
搜索命令分为两类：
标准搜索命令（F0hex）用来搜索连接到网络中所有器件；报警或有条件搜索命令（EChex）只用来搜索那些处于报警状态下的器件，这种方式缩小了搜索范围，可以快速查找到所需要注意的器件。
搜索命令发出之后，开始实际的搜索过程。
首先总线上的所有从机器件同时发送ROM码（也叫注册码）中的第一位（最低有效位）（参见图1）。
与所有的1-Wire通信一样，无论是读取数据还是向从机器件写数据，都由1-Wire主机启动每一位操作。
按照1-Wire的特性，当所有从机器件同时应答主机时，结果相当于全部发送数据位的逻辑AND；从机发送其ROM码的第一位后，主机启动下一位操作、接着从机发送第一位数据的补码；从两次读到的数据位可以对ROM码的第一位做出几种判断（参见表1）。
表1.检索信息位
Bit（true）
Bit（complement）
InformationKnown
0
0
Thereareboth0sand1sinthecurrentbitpositionoftheparticipatingROMnumbers.Thisisadiscrepancy.
0
1
Thereareonly0sinthebitoftheparticipatingROMnumbers.
1
0
Thereareonly1sinthebitoftheparticipatingROMnumbers.
1
1
Nodevicesparticipatinginsearch.
按照搜索算法的要求，1-Wire主机必须向总线上的从机发回一个指定位；如果从机器件中ROM码的当前位的值与该数据位匹配，则继续参与搜索过程；若从机器件的当前位与之不匹配，则该器件转换到等待状态，并保持等待状态直到下一个1-Wire复位信号到来。
其余63位ROM码的搜索依然按照这种‘读两位’、‘写一位’的模式进行重复操作（参见表2）。
按照这种搜索算法进行下去，最终除了一个从机器件外所有从机将进入等待状态，经过最后一轮检测，就可得到最后保留（未进入等待状态）器件的ROM码。
在后续搜索过程中，选用不同的路径（或分支）来查找其它器件的ROM码。
需要注意的是本文ROM码的数据位用第1位（最低有效位）到第64位（最高有效位）表示，而不是我们常用的那种第0位到第63位的模式；这样设置允许将差异位置计数器初始值置为0，为以后的比较提供了方便。
表2.1-Wire主机和从机的搜索过程
Master
Slave
1-Wireresetstimulus
Producepresencepulse
Writesearchcommand（normaloralarm）
Eachslavereadiesforsearch.
Read'AND'ofbit1
Eachslavesendsbit1ofitsROMnumber.
Read'AND'ofcomplementbit1
Eachslavesendscomplementbit1ofitsROMnumber.
Writebit1direction（accordingtoalgorithm）
Eachslavereceivesthebitwrittenbymaster,ifbitreadisnotthesameasbit1ofitsROMnumberthengointoawaitstate.
Read'AND'ofbit64
Eachslavesendsbit64ofitsROMnumber.
Read'AND'ofcomplementbit64
Eachslavesendscomplementbit64ofitsROMnumber.
Writebit64direction（accordingtoalgorithm）
Eachslavereceivesthebitwrittenbymaster,ifbitreadisnotthesameasbit64ofitsROMnumberthengointoawaitstate.
从表1可以看出：
如果所有总线上的器件在当前位具有相同值，那么只有一条分支路径可选；总线上没有器件响应的情况是一种异常状态，可能是要查找的器件在搜寻过程中与1-Wire总线脱离。
如果出现这种情况，应中止搜索，并发出1-Wire复位信号起始新的搜索过程。
如果当前位既有0也有1，这种情况称为位值差异，它对在后续搜索过程中查找器件起关键作用。
搜索算法指定在第一轮查询中若出现差异（数据位/补码=0/0），则选用‘0’路径。
注意：
这一点是由本文档中介绍的特定算法决定的，其它算法中或许首先选用‘1’路径。
记录最后一次值差异的位置以供下一次搜索使用，表3列出了出现值差异时路径的选取情况。
表3.搜索路径方向
SearchBitPositionvsLastDiscrepancy
PathTaken
=
takethe'1'path
<
takethesamepathaslasttime（fromlastROMnumberfound）
>
takethe'0'path
搜索算法计算还对最初8位过程中出现的最后一次位差异保持跟踪；64位注册码的前8位是家族码，在器件的搜索过程中可以按照其家族码进行分类。
记录家族码的最后一次差异可以用于有选择性地跳过1-Wire器件的整个分组。
如需进行选择性的搜索，可参考关于高级变量搜索的详细解释。
64位ROM码中包含8位循环冗余校验码（CRC）；CRC值用于验证是否搜索到正确的ROM码。
ROM码的排列如图1所示。
DS2480B系列串口到1-Wire线路的驱动程序在硬件中实现了部分与本文档中相同的搜索算法；详细资料请参阅DS2480B数据资料和应用笔记192，DS2480B串行接口1-Wire线驱动器的使用的详细介绍；从DS2490USB口到1-Wire桥接器硬件电路中实现了整个搜索过程。
图2列出了对一个从器件进行搜索的流程图；注意：
右侧Reference栏对在流程图中出现的符号进行了说明；在本文档的源代码附录中也将用到这些专用符号。
图2.搜索流程
图2.搜索流程，第2部分
搜索算法通过对LastDiscrepancy、LastFamilyDiscrepancy、LastDeviceFlag和ROM_NO值（参见表4）的处理，利用上述流程实现了两个不同类型的搜索操作；这两个操作是搜索1-Wire器件ROM码的基础。
First
‘FIRST’操作是搜索1-Wire总线上的第一个从机器件。
该操作是通过将LastDiscrepancy、LastFamilyDiscrepancy和LastDeviceFlag置零，然后进行搜索完成的。
最后ROM码从ROM_NO寄存器中读出。
若1-Wire总线上没有器件，复位序列就检测不到应答脉冲，搜索过程中止。
Next
‘NEXT’操作是搜索1-Wire总线上的下一个从机器件；一般情况下，此搜索操作是在‘FIRST’操作之后或上一次‘NEXT’操作之后进行；保持上次搜索后这些值的状态不变、执行又一次搜索即可实现‘NEXT’操作。
之后从ROM_NO寄存器中来读出新一个ROM码。
若前一次搜索到的是1-Wire上的最后一个器件，则返回一个无效标记FALSE，并且把状态设置成下一次调用搜索算法时将是‘FIRST’操作的状态。
图3（a,b,c）例举了三个器件的搜索过程，为便于说明，设器件的ROM码只有2位。
图3.搜索过程举例
高级变量搜索
有3种利用同一组状态变量LastDiscrepancy、LastFamilyDiscrepancy、LastDeviceFlag、ROM_NO实现的高级变量搜索算法，这几种高级搜索算法允许来指定作为搜索目标或需要跳过搜索的器件的类型（家族码）以及验证某类型的器件是否在线（参见表4）。
Verify
‘VERIFY’操作用来检验已知ROM码的器件是否连接在1-Wire总线上，通过提供ROM码并对该码进行目标搜索就可确定此器件是否在线。
首先，将ROM_NO寄存器值设置为已知的ROM码值，然后将LastDiscrepancy和LastDeviceFlag标志位分别设置为64（40h）和0；进行搜索操作，然后读ROM_NO的输出结果；如果搜索成功并且ROM_NO中存储的仍是要搜索器件的ROM码值，那么此器件就在1-Wire总线上。
TargetSetup
‘TARGETSETUP’操作就是用预置搜索状态的方式首先查找一个特殊的家族类型，每个1-Wire器件都有一个字节的家族码内嵌在ROM码中（参见图1），主机可以通过家族码来识别器件所具有的特性和功能。
若1-Wire总线上有多片器件时，通常是将搜索目标首先定位在需注意的器件类型上。
为了将一个特殊的家族作为搜索目标，需要将所希望的家族码字节放到ROM_NO寄存器的第一个字节中，并且将ROM_NO寄存器的复位状态置零，然后将LastDiscrepancy设置为64（40h）；把LastDeviceFlag和LastFamilyDiscrepancy设置为0。
在执行下一次搜索算法时就能找出所期望的产品类型的第一个器件；并将此值存入ROM_NO寄存器。
需要注意的是如果1-Wire总线上没有挂接所期望的产品类型的器件，就会找出另一类型的器件，所以每次搜索完成后，都要对ROM_NO寄存器中存储的结果进行校验。
FamilySkipSetup
‘FAMILYSKIPSETUP’操作用来设置搜索状态以便跳过搜索到的指定家族中的所有器件，此操作只有在一个搜索过程结束后才能使用。
通过把LastFamilyDiscrepancy复制到LastDiscrepancy，并清除LastDeviceFlag即可实现该操作；在下一搜索过程就会找到指定家族中的下一个器件。
如果当前家族码分组是搜索过程中的最后一组，那么搜索过程结束并将LastDeviceFlag置位。
表4.搜索变量状态的设置
LastDiscrepancy
LastFamily-Discrepancy
LastDeviceFlag
ROM_NO
FIRST
0
0
0
result
NEXT
leaveunchanged
leaveunchanged
leaveunchanged
result
VERIFY
64
0
0
setwithROMtoverify,checkifsameaftersearch
TARGETSETUP
64
0
0
setfirstbytetofamilycode,setresttozeros
FAMILYSKIPSETUP
copyfromLastFamilyDiscrepancy
0
0
leaveunchanged
结论
本文提供的搜索算法可以找出任意给定的1-Wire器件组中独一无二的ROM码，这是保证多点1-Wire总线应用的关键，已知ROM码后就可以对逐一选定的某个1-Wire器件来进行操作。
本文还对一些变量搜索算法做了详细论述，这些变量搜索算法能够查找或跳过特定类型的1-Wire器件。
附录给出了实现搜索过程和所有变量搜索算法的例程，并给出了‘C’程序代码。
附录
下面给出了搜索算法的‘C’程序代码及实现每个变量搜索算法的函数。
FamilySkipSetup和TargetSetup函数实际上并没有进行搜索操作，它们只不过是用来设置搜索寄存器，以便在下一次执行‘NEXT’操作时能跳过或找到所期望的类型。
需要注意的是低级1-Wire函数可通过调用TMEXAPI实现。
这些程序调用只是用于系统测试，也可以用特定平台调用。
关于TMEXAPI和其它一些1-WireAPI的详细资料请参考应用笔记155。
下列TMEXAPI测试程序的源代码可从Maxim网页下载。
//TMEXAPITESTBUILDDECLARATIONS
#defineTMEXUTIL
#include"ibtmexcw.h"
longsession_handle;
//ENDTMEXAPITESTBUILDDECLARATIONS
//definitions
#defineFALSE0
#defineTRUE1
//methoddeclarations
intOWFirst（）;
intOWNext（）;
intOWVerify（）;
voidOWTargetSetup（unsignedcharfamily_code）;
voidOWFamilySkipSetup（）;
intOWReset（）;
voidOWWriteByte（unsignedcharbyte_value）;
voidOWWriteBit（unsignedcharbit_value）;
unsignedcharOWReadBit（）;
intOWSearch（）;
unsignedchardocrc8（unsignedcharvalue）;
//globalsearchstate
unsignedcharROM_NO[8];
intLastDiscrepancy;
intLastFamilyDiscrepancy;
intLastDeviceFlag;
unsignedcharcrc8;
//--------------------------------------------------------------------------
//Findthe'first'devicesonthe1-Wirebus
//ReturnTRUE:
devicefound,ROMnumberinROM_NObuffer
//FALSE:
nodevicepresent
//
intOWFirst（）
{
//resetthesearchstate
LastDiscrepancy=0;
LastDeviceFlag=FALSE;
LastFamilyDiscrepancy=0;
returnOWSearch（）;
}
//--------------------------------------------------------------------------
//Findthe'next'devicesonthe1-Wirebus
//ReturnTRUE:
devicefound,ROMnumberinROM_NObuffer
//FALSE:
devicenotfound,endofsearch
//
intOWNext（）
{
//leavethesearchstatealone
returnOWSearch（）;
}
//--------------------------------------------------------------------------
//Performthe1-WireSearchAlgorithmonthe1-Wirebususingtheexisting
//searchstate.
//ReturnTRUE:
devicefound,ROMnumberinROM_NObuffer
//FALSE:
devicenotfound,endofsearch
//
intOWSearch（）
{
intid_bit_number;
intlast_zero,rom_byte_number,search_result;
intid_bit,cmp_id_bit;
unsignedcharrom_byte_mask,search_direction;
//initializeforsearch
id_bit_number=1;
last_zero=0;
rom_byte_number=0;
rom_byte_mask=1;
search_result=0;
crc8=0;
//ifthelastcallwasnotthelastone
if（!
LastDeviceFlag）
{
//1-Wirereset
if（!
OWReset（））
{
//resetthesearch
LastDiscrepancy=0;
LastDeviceFlag=FALSE;
LastFamilyDiscrepancy=0;
returnFALSE;
}
//issuethesearchcommand
OWWriteByte（0xF0）;
//looptodothesearch
do
{
//readabitanditscomplement
id_bit=OWReadBit（）;
cmp_id_bit=OWReadBit（）;
//checkfornodeviceson1-wire
if（（id_bit==1）&&（cmp_id_bit==1））
break;
else
{
//alldevicescoupledhave0or1
if（id_bit!
=cmp_id_bit）
search_direction=id_bit;//bitwritevalueforsearch
else
{
//ifthisdiscrepancyifbeforetheLastDiscrepancy
//onapreviousnextthenpickthesameaslasttime
if（id_bit_numbersearch_direction=（（ROM_NO[rom_byte_number]&rom_byte_mask）>0）;
else
//ifequaltolastpick1,ifnotthenpick0
search_direction=（id_bit_number==LastDiscrepancy）;
//if0waspickedthenrecorditspositioninLastZero
if（search_direction==0）
{
last_zero=id_bit_number;
//checkforLastdiscrepancyinfamily
if（last_zero<9）
LastFamilyDiscrepancy=last_zero;
}
}
//setorclearthebitintheROMbyterom_byte_number
//withmaskrom_byte_mask
if（search_direction==1）
ROM_NO[rom_byte_number]|=rom_byte_mask;
else
ROM_NO[rom_byte_number]&=~rom_byte_mask;
//serialnumbersearchdirectionwritebit
OWWriteBit（search_direction）;
//incrementthebytecounterid_bit_number
//andshiftthemaskrom_byte_mask
id_bit_number++;
rom_byte_mask<<=1;
//ifthemaskis0thengotonewSerialNumbyterom_byte_numberandresetmask
if（rom_byte_mask==0）
{
docrc8（ROM_NO[rom_byte_number]）;//accumulatetheCRC
rom_byte_number++;
rom_byte_mask=1;
}
}
}
while（rom_byte_number<8）;//loopuntilthroughallROMbytes0-7
//ifthesearchwassuccessfulthen
if（!
（（id_bit_number<65）||（crc8!
=0）））
{
//searchsuccessfulsosetLastDiscrepancy,LastDeviceFlag,search_result
LastDiscrepancy=last_zero;
//checkfor
升级会员 