搜索算法中英文对照外文翻译文献

(文档含英文原文和中文翻译)

中英文对照翻译

外文资料

1-Wire Search Algorithm

Abstract

Dallas Semiconductor's 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 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 and future devices that feature a 1-Wire interface.

Table 1 Bit Unique ROM 'Registration' Number.

Search Algorithm

The search algorithm is a binary tree search where branches are followed until a device 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 command 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 devices 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 called 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 bits 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.)

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-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. 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 convenience 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 are 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.

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 searches. 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 recorded for use in the next search. Table 3 describes the paths that are taken on subsequent searches when a discrepancy occurs.

The search algorithm also keeps track of the last discrepancy that 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 groups 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 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.Reference

Id_bit—the first bit read in a bit search sequence. This bit is the AND of all of the id_bit_number bits of the devices that are still participating in the search.

cmp_id_bit—the 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_number—the ROM bit number 1 to 64 currently being searched.

LastDeviceFlag—flag to indicate previous search was the last device.

LastDiscrepancy—bit index that identifies from which bit the (next) search discrepancy check should start.

LastFamilyDiscrepancy—bit index that identifies the LastDiscrepancy within the first 8-bit family code of ROM number.

last_zero—bit position of the last zero written where there was a discrepancy.

ROM_NO—8-byte buffer that contains the current ROM registration number discovered.

search_direction—bit 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 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.First

The '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 1- Wire the reset sequence will not detect a presence and the search is aborted.Next

The 'NEXT' operation is to search on the 1-Wire for the next device. This search is usually performed after a 'FIRST' operation or another 'NEXT' operation. It is performed by leaving the state unchanged from the previous search and performing another search. The resulting ROM number can then be read from the ROM_NO register. If the previous search was the last device on the 1-Wire then the result will be FALSE and the condition will be set to execute a 'FIRST' with the next call of the search algorithm.

The following goes through a simple search example with three devices. For illustration, this example assumes devices with a 2-bit ROM number only.

Search Example

(for simplicity the family discrepancy register and tracking has been left out of this example)

FIRST

LastDiscrepancy = LastDeviceFlag = 0

Do 1-Wire reset and wait for presence pulse ,if no presence pulse then done

id_bit_number = 1, last_zero = 0

Send search command ,0F0 hex

Read first bit id_bit : 1 (Device A) AND 0 (Device B) AND 1 (Device C) = 0

Read complement of first bit cmp_id_bit : 0 (Device A) AND 1 (Device B) AND 0 (Device C) = 0

Since id_bit_number > LastDiscrepancy,then search_direction = 0, last_zero = 1 Send search_direction bit of 0 , both Device A and C go into wait state

Increment id_bit_number to 2

Read second bit id_bit : 0(Device B) = 0

Read complement of second bit cmp_id_bit : 1 (Device B) = 1

Since bit and complement are different then search_direction = id_bit

Send search_direction bit of 0 ,Device B is discovered with ROM_NO of ‘00’ and is now selected

LastDiscrepancy = last_zero

NEXT

Do 1-Wire reset and wait for presence pulse ,if no presence pulse then done

id_bit_number = 1, last_zero = 0

Send search command ,0F0 hex

Read first bit id_bit : 1 (Device A) AND 0 (Device B) AND 1 (Device C) = 0

Read complement of first bit cmp_id_bit : 0 (Device A) AND 1 (Device B) AND 0 (Device C) = 0

Since id_bit_number = LastDiscrepancy then search_direction = 1

Send search_direction bit of 1 , Device B goes into wait state

Increment id_bit_number to 2

Read second bit id_bit : 0(Device A) AND 1(Device C) = 0

Read complement of second bit cmp_id_bit : 1(Device A) AND 0(Device C) = 0

Since id_bit_number > LastDiscrepancy,then search_direction = 0, last_zero = 2 Send search_direction bit of 0 , Device C goes into wait state

Device A is discovered with ROM_NO of ‘01’ and is now selected

LastDiscrepancy = last_zero

NEXT

Do 1-Wire reset and wait for presence pulse ,if no presence pulse then done

id_bit_number = 1, last_zero = 0

Send search command ,0F0 hex

Read first bit id_bit : 1 (Device A) AND 0 (Device B) AND 1 (Device C) = 0

Read complement of first bit cmp_id_bit : 0 (Device A) AND 1 (Device B) AND 0 (Device C) = 0

Since id_bit_number

Send search_direction bit of 1 , Device B goes into wait state

Increment id_bit_number to 2

Read second bit id_bit : 0(Device A) AND 1(Device C) = 0

Read complement of second bit cmp_id_bit : 1(Device A) AND 0(Device C) = 0

Since id_bit_number = LastDiscrepancy,then search_direction = 1

Send search_direction bit of 1 , Device A goes into wait state

Device C is discovered with ROM_NO of ‘11’ and is now selected

LastDiscrepancy = last_zero which is 0 so LastDeviceFlag = TRUE

NEXT

LastDeviceFlag is true so return FALSE

LastDiscrepancy = LastDeviceFlag = 0

Advanced Search Variations

There are three advanced search variations using the same state information, namely LastDiscrepancy, LastFamilyDiscrepancy, LastDeviceFlag, and ROM_NO.

These variations allow specific family types to be targeted or skipped and device present verification (see Table 4).

Verify

The 'VERIFY' operation verifies if a device with a known ROM number is currently connected to the 1- Wire. It is accomplished by supplying the ROM number and doing a targeted search on that number to verify it is present. First, set the ROM_NO register to the known ROM number. Then set the LastDiscrepancy to 64 (40 hex) and the LastDeviceFlag to 0. Perform the search operation and then read the ROM_NO result. If the search was successful and the ROM_NO remains the ROM number that was being searched for, then the device is currently on the 1-Wire.

Target Setup

The 'TARGET SETUP' operation is a way to preset the search state to first find a particular family type. Each 1-Wire device has a one byte family code embedded within the ROM number (see Figure 1). This family code allows the 1-Wire master to know what operations this device is capable of. If there are multiple devices on the 1-Wire it is common practice to target a search to only the family of devices that are of interest. To target a particular family, set the desired family code byte into the first byte of the ROM_NO register and fill the rest of the ROM_NO register with zeros. Then set the LastDiscrepancy to 64 (40 hex) and both LastDeviceFlag and LastFamilyDiscrepancy to 0. When the search algorithm is next performed the first device of the desired family type will be discovered and placed in the ROM_NO register. Note that if no devices of the desired family are currently on the 1-Wire, then another type will be found, so the family code in the resulting ROM_NO must be verified after the search.

Family Skip Setup

The 'FAMILY SKIP SETUP' operation sets the search state to skip all of the devices that have the family code that was found in the previous search. This operation can only be performed after a search. It is accomplished by copying the LastFamilyDiscrepancy into the LastDiscrepancy and clearing out the LastDeviceFlag. The next search will then find devices that come after the current family code. If the current family code group was the last group in the search then the search will return with the LastDeviceFlag set.

Table5 Search Variations State Setup

Conclusion

The supplied search algorithm allows the discovery of the individually unique ROM numbers from any given group of 1-Wire devices. This is essential to any multidrop 1-Wire application. With the ROM numbers in hand, each 1-Wire device can be selected individually for operations. This document also discussed search variations to find or skip particular 1-Wire device types. See Appendix for a 'C' code example implementation of the search and all of the search variations.

中文译文

1-Wire 搜索算法

绪论

Dallas Semiconductor的每片1-Wire器件都有唯一的64位注册码它存储在只读存储器(ROM)中。在1-Wire网络中注册码用于1-Wire主机对从机器件进行逐一寻址。如果1-Wire网络中从机器件的ROM 码是未知的,可以通过搜索算法来找到此码。本文不仅详细地解释了搜索算法,而且还提供了实现快速整合的例程该算法适用于任何具有1-Wire接口特性的现有产品及未来产品。

搜索算法

搜索算法采用的是二叉树型结构,搜索过程沿各分节点进行,直到找到器件的ROM码即叶子为止;后续的搜索操作沿着节点上的其它路径进行,按照同样的方式直到找到总线上的所有器件代码。

搜索算法首先通过复位(Reset)和在线应答脉冲(Presence Pulse)时隙将1-Wire总线上的所有器件复位;成功地执行该操作后,发送1个字节的搜索命令;搜索命令使1-Wire器件准备、就绪开始进行搜索操作。

搜索命令分为两类标准搜索命令(0F0H)用来搜索连接到网络中所有器件;报警或有条件搜索命令(0ECH)只用来搜索那些处于报警状态下的器件,这种方式缩小了搜索范围,可以快速查找到所需要注意的器件。

搜索命令发出之后,开始实际的搜索过程。首先总线上的所有从机器件同时发送ROM 码(也叫注册码)中的第一位(最低有效位)(参见图1)。与所有的1-Wire通信一样无论是读取数据还是向从机器件写数据,都由1-Wire主机启动每一位操作。按照1-Wire的特性,当所有从机器件同时应答主机时,结果相当于全部发送数据位的逻辑AND;从机发送其ROM码的第一位后,主机启动下一位操作、接着从机发送第一位数据的补码;从两次读到的数据位可以对ROM码的第一位做出几种判断(参见表2)。

按照搜索算法的要求,1-Wire主机必须向总线上的从机发回一个指定位;如果从机器件中ROM码的当前位的值与该数据位匹配,则继续参与搜索过程;若从机器件的当前位与之不匹配,则该器件转换到等待状态,并保持等待状态直到下一个1-Wire复位信号到来。其余63位ROM 码的搜索依然按照这种‘读两位’、‘写


相关内容

  • 文件检索课题报告

    计算机与控制工程学院学 术文献检索 实 验 报 告 姓名___ __ _ 学号_ __ 成绩____________ 一.实验要求: 1.实验前要认真复习课堂所学知识,重点复习计算机检索技术.各种中外文数据库的使用方法.网络学术信息资源查询 ...


  • 论文开题报告全面整理

    开题报告.文献检索账号.文献综述.外文翻译.抄袭检测软件.论文目录,都在这了都在这了,有备无患,拿去吧!! 开题报告.文献综述.外文翻译.论文反抄袭软件.论文目录,就差论文正文了,其他都全了!! 开题报告主要包括以下几个方面: (一)论文名 ...


  • 修改重复率或抄袭率论文的经验

    修改重复率或抄袭率论文的经验: CNKI是连续的字数相同不能超过13个字,万方是连续的字数相同不能超过15个字.否则就会标注出来,算进重复率.我们学校规定是CNKI检测重复率不能超过30%.两种数据库检测重复率会有结果上的误差,一般CNKI ...


  • 2015年计算机专业毕业论文题目大全

    计算机专业毕业论文主题 基于asp 语言的测试项目 学生信息管理系统的设计与实现 基于ASP.NET 的社区人口管理系统 基于ASP.NET 的课程教学网站设计 公司会议网站 C#高校工资管理系统 C#在线点歌系统 <数据库原理> ...


  • 如何搜索外文资料

    电信技术专业学术翻译必备词汇:http://dict.cnki.net/essential/I136.htmlPDFDOCIntroductionapplicationreviewsummaryoverviewsummarizeFourie ...


  • 海南大学 文献信息检索2014-2015上学期试卷

    2014-2015第一学期 <文献信息检索与利用>考核题 姓名: 学院: 专业: 任课老师:张红霞 成绩: 一.自拟一道与本专业有关的检索课题进行检索,至少应包括三 个(含三个)以上的检索词.(温馨提示:自拟的题目不能和其他 同 ...


  • 本科毕业生论文外文文献翻译-当代西方建筑美学新思维毕业论文外文翻译-中英文对照论文翻译

    第一部部分外文文献原文部分 中文2000字 New thinking of contemporary western architectural aesthetics One of the most striking features of ...


  • 浅谈资料查阅方法

    浅谈资料查阅方法 --打开成功之门的钥匙 --通信技术研究所 首先要先声明,我也是检索新手,换个说法就是菜鸟.经过毕业设计和研一一年的学习,总算不会象以前那样懵懵懂懂,无从下手,现在也能根据自己的需要找到几篇文献.觉得还是很有必要总结一下这 ...


  • PCS流量单元最小方差控制器性能评估

    电信学院毕业设计任务书 题 目 PCS 流量单元最小方差控制器性能评估 学生姓名 班 级 学 号 题目类型 技术开发 指导教师 李二超 系主任 李炜 一.毕业设计的技术背景和设计依据 现代流程工业对控制系统的控制品质提出了严格的要求.然而, ...