《1Wire 搜索算法中英文翻译资料.doc》由会员分享，可在线阅读，更多相关《1Wire 搜索算法中英文翻译资料.doc（15页珍藏版）》请在三一办公上搜索。
1、1-Wire 搜索算法Dallas Semiconductor的每片1-Wire器件都有唯一的64位注册码它存储在只读存储器(ROM)中。在1-Wire网络中注册码用于1-Wire主机对从机器件进行逐一寻址。如果1-Wire网络中从机器件的ROM 码是未知的，可以通过搜索算法来找到此码。本文不仅详细地解释了搜索算法，而且还提供了实现快速整合的例程该算法适用于任何具有1-Wire接口特性的现有产品及未来产品。表1 64 位唯一的ROM 注册码MSB 64位ROM注册码 LSB8位CRC校验码MSB LSB48位序列号MSB LSB8位家族码MSB LSB搜索算法搜索算法采用的是二叉树型结构，搜索
2、过程沿各分节点进行，直到找到器件的ROM码即叶子为止；后续的搜索操作沿着节点上的其它路径进行，按照同样的方式直到找到总线上的所有器件代码。搜索算法首先通过复位(Reset)和在线应答脉冲(Presence Pulse)时隙将1-Wire总线上的所有器件复位；成功地执行该操作后，发送1个字节的搜索命令；搜索命令使1-Wire器件准备、就绪开始进行搜索操作。搜索命令分为两类标准搜索命令(0F0H)用来搜索连接到网络中所有器件；报警或有条件搜索命令(0ECH)只用来搜索那些处于报警状态下的器件，这种方式缩小了搜索范围，可以快速查找到所需要注意的器件。搜索命令发出之后，开始实际的搜索过程。首先总线上的
3、所有从机器件同时发送ROM 码(也叫注册码)中的第一位(最低有效位)(参见图1)。与所有的1-Wire通信一样无论是读取数据还是向从机器件写数据，都由1-Wire主机启动每一位操作。按照1-Wire的特性，当所有从机器件同时应答主机时，结果相当于全部发送数据位的逻辑AND；从机发送其ROM码的第一位后，主机启动下一位操作、接着从机发送第一位数据的补码；从两次读到的数据位可以对ROM码的第一位做出几种判断(参见表2)。按照搜索算法的要求，1-Wire主机必须向总线上的从机发回一个指定位；如果从机器件中ROM码的当前位的值与该数据位匹配，则继续参与搜索过程；若从机器件的当前位与之不匹配，则该器件转
4、换到等待状态，并保持等待状态直到下一个1-Wire复位信号到来。其余63位ROM 码的搜索依然按照这种读两位、写一位的模式进行重复操作(参见表3)。表2 检索信息位位(实际值)位(补码)结论00从机ROM码中的当前位既有0，也有1；即存在差异01从机ROM码中的当前位均为0。10从机ROM码中的当前位均为1。11总线上没有从机器件响应。按照这种搜索算法进行下去，最终除了一个从机器件外所有从机将进入等待状态，经过最后一轮检测，就可得到最后保留(未进入等待状态)器件的ROM码。在后续搜索过程中，选用不同的路径(或分支)来查找其它器件的ROM码。需要注意的是本文ROM码的数据位用第1位(最低有效位)
5、到第64位(最高有效位)表示，而不是我们常用的那种第0位到第63位的模式；这样设置允许将差异位置记数器初始值置为0，为以后的比较提供了方便。表3 1-Wire 主机和从机的搜索过程主机从机1-Wire 发出复位信号产生在线应答脉冲。写搜索命令 (标准或报警)从机准备搜索。读第1 位的AND从机发送ROM 码的第1 位。读第1 位补码的AND从机发送ROM 码的第1 位的补码。写第1 位指定位(依照算法)从机接收主机的指定位若所读的位与ROM码的第1 位不匹配，则进入等待状态。 读第64 位的AND从机发送ROM 码的第64 位。读第64 位补码的AND从机发送ROM 码的第64 位的补码。写第
6、64 位指定位(依照算法)从机接收主机的指定位若所读的位与ROM码的第64 位不匹配，则进入等待状态。从表4 可以看出：如果所有总线上的器件在当前位具有相同值，那么只有一条分支路径可选；总线上没有器件响应的情况是一种异常状态，可能是要查找的器件在搜寻过程中与1-Wire 总线脱离。如果当前位既有0也有1，这种情况称为位值差异，它对在后续搜索过程中查找器件起关键作用。搜索算法指定在第一轮查询中若出现差异(数据位/补码 = 0/0), 则选用0路径。注意：这一点是由本文档中介绍的特定算法决定的，其它算法中或许首先选用1路径。记录最后一次值差异的位置以供下一次搜索使用，表3列出了出现值差异时路径的选
7、取情况。表4 搜索路径方向搜索位所在位置和最后一次值差异所在位置的比较路径选取=采用路径1采用路径 0搜索算法计算还对最初8位过程中出现的最后一次位差异保持跟踪；64位注册码的前8位是家族码，在器件的搜索过程中可以按照其家族码进行分类。记录家族码的最后一次差异可以用于有选择性地跳过1-Wire器件的整个分组。如需进行选择性地搜索，可参考关于高级变量搜索的详细解释。64位ROM码中包含8位循环冗余校验码(CRC)；CRC值用于验证是否搜索到正确的ROM码注释对实例中出现的符号进行了说明；在本文档的源代码附录中也将用到这些专用符号。注释：id_bit在位搜索中第一次读取的值，该位是搜索过程中所有应
8、答器件的id_bit_number 位的逻辑ANDcmp_id_bitid_bit 位的补码，该位是搜索过程中所有应答器件的id_bit_number位的补码的逻辑ANDid_bit_number记录当前搜索是1到64位ROM码中哪一位的量LastDeviceFlag指明前一次搜索到的已是最后一个器件的标志位LastDiscrepancy 位指针指明下次搜索从哪个值差异位开始LastFamilyDiscrepancy位指针。用来指明LastDiscrepancy是否是在ROM码中前8位家族码内和其位置last_zero上次被写入0的值差异位的位置ROM_NO记录当前正在查找的ROM，注册码的8
9、字节缓冲器search_direction位变量其值用来指明搜索方向具有此数据位规定值的所有器件继续响应搜索操作其它器件转入等待状态直到下一次1-Wire复位搜索算法通过对LastDiscrepancy、LastFamilyDiscrepancy、LastDeviceFlag 和ROM_NO 值(参见表4)的处理利用上述流程实现了两个不同类型的搜索操作；这两个操作是搜索1-Wire 器件ROM 码的基础。FIRSTFIRST操作是搜索1-Wire总线上的第一个从机器件。该操作是通过将LastDiscrepancy、LastFamilyDiscrepancy和LastDeviceFlag置零，然
10、后进行搜索完成的。最后ROM码从ROM_NO寄存器中读出。若1-Wire总线上没有器件，复位序列就检测不到应答脉冲，搜索过程中止。NEXTNEXT操作是搜索1-Wire总线上的下一个从机器件；一般情况下此搜索操作是在FIRST操作之后或上一次NEXT操作之后进行；保持上次搜索后这些值的状态不变、执行又一次搜索即可实现NEXT操作。之后从ROM_NO寄存器中来读出新一个ROM码。若前一次搜索到的是1-Wire上的最后一个器件，则返回一个无效标记FALSE，并且把状态设置成下一次调用搜索算法时将是FIRST操作的状态。以下例举了三个器件的搜索过程，为便于说明，设器件的ROM码只有2位。搜索实例 (
11、为了简化本例中省去了家族码值差异位的记录和跟踪)FIRSTu LastDiscrepancy = LastDeviceFlag = 0u 执行1-Wire复位操作并等待在线应答脉冲，若无在线应答脉冲则结束u id_bit_number = 1, last_zero = 0u 发送搜索命令, 0F0Hu 读第一个数据位id_bit: 1 (器件 A) AND 0 (器件 B) AND 1 (器件 C) = 0u 读第一个数据位的补码 cmp_id_bit: 0 (器件 A) AND 1 (器件 B) AND 0 (器件 C) = 0u 由于id_bit_number LastDiscrepanc
12、y，设置 search_direction = 0, last_zero = 1u 发送当前值为0的search_direction 数据位, 使器件A与器件C转换到等待状态u id_bit_number 值增到2u 读第二个数据位id_bit: 0 (器件 B) = 0u 读第二个数据位的补码cmp_id_bit: 1 (器件 B) = 1u 由于数据位与其补码不同设置，search_direction = id_bitu 发送当前值为0的search_direction数据位，查找到器件B的ROM_NO值为00、 并且是当前选择u LastDiscrepancy = last_zeroNE
13、XTu 1-Wire主机执行复位操作并等待在线应答脉冲，若无在线应答脉冲则结束u id_bit_number = 1, last_zero = 0u 发送搜索命令,0F0Hu 读第一个数据位id_bit: 1 (器件 A) AND 0 (器件 B) AND 1 (器件 C) = 0u 读第一个数据位的补码cmp_id_bit: 0 (器件 A) AND 1 (器件 B) AND 0 (器件 C) = 0u 由于id_bit_number = LastDiscrepancy，设置search_direction = 1u 发送当前值为1的search_direction 数据位, 使器件B转换到
14、等待状态u id_bit_number值增值到2u 读第二个数据位id_bit: 0 (器件 A) AND 1 (器件 C) = 0u 读第二个数据位的补码cmp_id_bit: 1 (器件 A) AND 0 (器件 C) = 0u 由于id_bit_number LastDiscrepancy，设置search_direction = 0, last_zero = 2u 发送当前值为0的search_direction 数据位, 使器件C转换到等待状态u 查找到器件A的ROM_NO 值为01、并且是当前选择u LastDiscrepancy = last_zeroNEXTu 执行1-Wire
15、复位操作并等待在线应答脉冲，若无在线应答脉冲则结束u id_bit_number = 1, last_zero = 0u 发送搜索命令,0F0Hu 读第一个数据位id_bit: 1 (器件 A) AND 0 (器件 B) AND 1 (器件 C) = 0u 读第一个数据位的补码cmp_id_bit: 0 (器件 A) AND 1 (器件 B) AND 0 (器件 C) = 0u 由于id_bit_number LastDiscrepancy，设置search_direction = ROM_NO(第一位)= 1u 发送当前值为1 的search_direction 数据位, 使器件B转换到等待
16、状态u id_bit_number值增值2u 读第二个数据位id_bit: 0 (器件 A) AND 1 (器件 C) = 0u 读第二个数据位的补码cmp_id_bit: 1 (器件 A) AND 0 (器件 C) = 0u 由于id_bit_number = LastDiscrepancy，设置search_direction = 1u 发送当前值为1的search_direction 数据位,使器件A转换到等待状态u 查找到器件C的ROM_NO值为11、并且是当前选择u LastDiscrepancy = last_zero 值为0，所以设置 LastDeviceFlag = TRUEu
17、 NEXTu LastDeviceFlag值为TRUE，所以返回FALSEu LastDiscrepancy = LastDeviceFlag = 0高级变量搜索有3种利用同一组状态变量LastDiscrepancy、LastFamilyDiscrepancy、LastDeviceFlag、 ROM_NO实现的高级变化搜索可以得到三种高级变量搜索算法，这几种高级搜索算法允许来指定作为搜索目标的器件的类型(家族码)或者是指定需要跳过或验证某类型的器件是否在线(参见表4)。VERIFYVERIFY 操作用来检验已知ROM码的器件是否连接在1-Wire总线上，通过提供ROM码并对该码进行目标搜索就可
18、确定此器件是否在线。首先将ROM_NO寄存器值设置为已知的ROM码值，然后将LastDiscrepancy和LastDeviceFlag标志位分别设置为64(40H)和0；进行搜索操作，然后读ROM_NO的输出结果；如果搜索成功并且ROM_NO中存储的仍是要搜索器件的ROM码值，那么此器件就在1-Wire总线上。TARGET SETUPTARGET SETUP操作就是用预置搜索状态的方式首先查找一个特殊的家族类型，每个1-Wire器件都有一个字节的家族码内嵌在ROM码中(参见图1)，主机可以通过家族码来识别器件所具有的特性和功能。若1-Wire总线上有多片器件时，通常是将搜索目标首先定位在需注
19、意的器件类型上，为了将一个特殊的家族作为搜索目标，需要将所希望的家族码字节放到ROM_NO寄存器的第一个字节中，并且将ROM_NO寄存器的复位状态置零，然后将LastDiscrepancy设置为64(40H)；把LastDeviceFlag和LastFamilyDiscrepancy设置为0。在执行下一次搜索算法时就能找出所期望的产品类型的第一个器件；并将此值存入ROM_NO寄存器。需要注意的是如果1-Wire总线上没有挂接所期望的产品类型的器件，就会找出另一类型的器件，所以每次搜索完成后，都要对ROM_NO寄存器中存储的结果进行校验。FAMILY SKIP SETUPFAMILY SKIP
20、SETUP操作用来设置搜索状态以便跳过搜索到的指定家族中的所有器件，此操作只有在一个搜索过程结束后才能使用。通过把LastFamilyDiscrepancy复制到LastDiscrepancy，并清除LastDeviceFlag即可实现该操作；在下一搜索过程就会找到指定家族中的下一个器件。如果当前家族码分组是搜索过程中的最后一组，那么搜索过程结束并将LastDeviceFlag 置位。表4 搜索变量状态的设置 LastDiscrepancyLastFamily-DiscrepancyLastDeviceFlagROM_NOFIRST000结果NEXT.不变不变不变结果VERIFY64随意0设置
21、 ROM 校验,搜索完后检查结果是否正确TARGETSETUP6400将第一个字节设置为家族码复位状态置零FAMILYSKIPSETUP复制LastFamilyDiscre-pancy不变0不变1-Wire Search AlgorithmAbstractDallas Semiconductors 1-Wire devices each have a 64-bit unique registration number in read-only-memory (ROM).That is used to address them individually by a 1-Wire master in
22、 a 1-Wire network. If the ROM numbers of the slave devices on the 1-Wire network are not known, then using a search algorithm can discover them. This document explains the search algorithm in detail and provides an example implementation for rapid integration. This algorithm is valid for all current
23、 and future devices that feature a 1-Wire interface.Table 1 Bit Unique ROM Registration Number.MSB 64-Bit Registration ROM Number LSB8-Bit CRCMSB LSB48-Bit Serial NumberMSB LSB8-Bit Family CodeMSB LSBSearch AlgorithmThe search algorithm is a binary tree search where branches are followed until a dev
24、ice ROM number, or leaf, is found. Subsequent searches then take the other branch paths until all of the leaves present are discovered.The search algorithm begins with the devices on the 1-Wire being reset using the reset and presence pulse sequence. If this is successful then the 1-byte search comm
25、and is sent. The search command readies the 1-Wire devices to begin the search.There are two types of search commands. The normal search command (0F0 hex) will perform a search with all devices participating. The alarm or conditional search command (0EC hex) will perform a search with only the devic
26、es that are in some sort of alarm state. This reduces the search pool to quickly respond to devices that need attention.Following the search command, the actual search begins with all of the participating devices simultaneously sending the first bit (least significant) in their ROM number (also call
27、ed registration number). (See Figure 1.) As with all 1-Wire communication, the 1-Wire master starts every bit whether it is data to be read or written to the slave devices. Due to the characteristics of the 1-Wire, when all devices respond at the same time, the result will be a logical AND of the bi
28、ts sent. After the devices send the first bit of their ROM number, the master initiates the next bit and the devices then send the complement of the first bit. From these two bits, information can be derived about the first bit in the ROM numbers of the participating devices. (See Table 1.)Table 2 B
29、it Search InformationBit(true)Bit(complement)Information Known00There are both 0s and 1s in the current bit position of the participating ROM numbers. This is a discrepancy.01There are only 0s in the bit of the participating ROM numbers.10There are only 1s in the bit of the participating ROM numbers
30、.11No devices participating in search.According to the search algorithm, the 1-Wire master must then send a bit back to the participating devices. If the participating device has that bit value, it continues participating. If it does not have the bit value, it goes into a wait state until the next 1
31、-Wire reset is detected. This read two bits and write one bit pattern is then repeated for the remaining 63 bits of the ROM number (see Table 2). In this way the search algorithm forces all but one device to go into this wait state. At the end of one pass, the ROM number of this last device is known
32、. On subsequent passes of the search, a different path (or branch) is taken to find the other device ROM numbers. Note that this document refers to the bit position in the ROM number as bit 1 (least significant) to bit 64 (most significant). This convention was used instead of bit 0 to bit 63 for co
33、nvenience to allow initialization of discrepancy counters to 0 for later comparisons.On examination of Table 1, it is obvious that if all of the participating devices have the same value in a bit position then there is only one choice for the branch path to be taken. The condition where no devices a
34、re participating is an atypical situation that may arise if the device being discovered is removed from the 1- Wire during the search. If this situation arises then the search should be terminated and a new search could be done starting with a 1-Wire reset. Table 3 Wire Master and Slave Search Seque
35、nceMasterSlave1-Wire reset stimulusProduce presence pulse.Write search command (normal or alarm)Each slave readies for search.Read AND of bit 1Each slave sends bit 1 of its ROM number.Read AND of complement bit 1Each slave sends complement bit 1 of its ROM number.Write bit 1 direction (according to
36、algorithm)Each slave receives the bit written by Master, if bit read is not the same as bit 1 of its ROM number then go into a wait state.Read AND of bit 64Each slave sends bit 64 of its ROM number.Read AND of complement bit 64Each slave sends complement bit 64 of its ROM number.Write bit 64 directi
37、on (according to algorithm)Each slave receives the bit written by master, if bit read is not the same as bit 64 of its ROM number then go into a wait state.The condition where there are both 0s and 1s in the bit position is called a discrepancy and is the key to finding devices in the subsequent sea
38、rches. The search algorithm specifies that on the first pass, when there is a discrepancy (bit/complement = 0/0), the 0 path is taken. Note that this is arbitrary for this particular algorithm. Another algorithm could be devised to use the 1 path first. The bit position for the last discrepancy is r
39、ecorded for use in the next search. Table 3 describes the paths that are taken on subsequent searches when a discrepancy occurs.Table 4 Search Path DirectionSearch Bit Position vsLast DiscrepancyPath Taken=take the 1 pathtake the 0 pathThe search algorithm also keeps track of the last discrepancy th
40、at occurs within the first eight bits of the algorithm. The first eight bits of the 64-bit registration number is a family code. As a result, the devices discovered during the search are grouped into family types. The last discrepancy within that family code can be used to selectively skip whole gro
41、ups of 1-Wire devices. See the description of ADVANCED SEARCH VARIATIONS for doing selective searches. The 64-bit ROM number also contains an 8-bit cyclic-redundancy-check (CRC). This CRC value is verified to ensure that only correct ROM numbers are discovered. See Figure 1 for the layout of the ROM
42、 number.Figure 2 shows a flow chart of the search sequence. Note the Reference that explains the terms used in the flow chart. These terms are also used in the source code appendix to this document.ReferenceId_bitthe first bit read in a bit search sequence. This bit is the AND of all of the id_bit_n
43、umber bits of the devices that are still participating in the search.cmp_id_bitthe complement of the id_bit .This bit is the AND of the complement of all of the id_bit_number bits of the devices that are still participating in the search.Id_bit_numberthe ROM bit number 1 to 64 currently being search
44、ed.LastDeviceFlagflag to indicate previous search was the last device.LastDiscrepancybit index that identifies from which bit the (next) search discrepancy check should start.LastFamilyDiscrepancybit index that identifies the LastDiscrepancy within the first 8-bit family code of ROM number.last_zero
45、bit position of the last zero written where there was a discrepancy.ROM_NO8-byte buffer that contains the current ROM registration number discovered.search_directionbit value indicating the direction of the search. All devices with this bit stay in the search and the rest go into a wait state for a
46、1-Wire reset.There are two basic types of operations that can be performed by using the search algorithm by manipulating the LastDiscrepancy, LastFamilyDiscrepancy, LastDeviceFlag, and ROM_NO register values (see Table 4). These operations concern basic discovery of the ROM numbers of 1-Wire devices.FirstThe FIRST operation is to search on the 1-Wire for the first device. This is performed by setting LastDiscrepancy, LastFamilyDiscrepancy, and LastDeviceFlag to zero and then doing the search. The resulting ROM number can then be read from the ROM_NO register. If no devices are present on the
