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

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

《搜索算法中英文对照外文翻译文献.docx》由会员分享，可在线阅读，更多相关《搜索算法中英文对照外文翻译文献.docx（19页珍藏版）》请在冰点文库上搜索。

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

（文档含英文原文和中文翻译）

中英文对照翻译

外文资料

1-WireSearchAlgorithm

Abstract

DallasSemiconductor's1-Wire®deviceseachhavea64-bituniqueregistrationnumberinread-only-memory（ROM）.Thatisusedtoaddressthemindividuallybya1-Wiremasterina1-Wirenetwork.IftheROMnumbersoftheslavedevicesonthe1-Wirenetworkarenotknown,thenusingasearchalgorithmcandiscoverthem.Thisdocumentexplainsthesearchalgorithmindetailandprovidesanexampleimplementationforrapidintegration.Thisalgorithmisvalidforallcurrentandfuturedevicesthatfeaturea1-Wireinterface.

Table1BitUniqueROM'Registration'Number.

MSB64-Bit'Registration'ROMNumberLSB

8-BitCRC

MSBLSB

48-BitSerialNumber

MSBLSB

8-BitFamilyCode

MSBLSB

SearchAlgorithm

ThesearchalgorithmisabinarytreesearchwherebranchesarefolloweduntiladeviceROMnumber,orleaf,isfound.Subsequentsearchesthentaketheotherbranchpathsuntilalloftheleavespresentarediscovered.

Thesearchalgorithmbeginswiththedevicesonthe1-Wirebeingresetusingtheresetandpresencepulsesequence.Ifthisissuccessfulthenthe1-bytesearchcommandissent.Thesearchcommandreadiesthe1-Wiredevicestobeginthesearch.

Therearetwotypesofsearchcommands.Thenormalsearchcommand（0F0hex）willperformasearchwithalldevicesparticipating.Thealarmorconditionalsearchcommand（0EChex）willperformasearchwithonlythedevicesthatareinsomesortofalarmstate.Thisreducesthesearchpooltoquicklyrespondtodevicesthatneedattention.

Followingthesearchcommand,theactualsearchbeginswithalloftheparticipatingdevicessimultaneouslysendingthefirstbit（leastsignificant）intheirROMnumber（alsocalledregistrationnumber）.（SeeFigure1.）Aswithall1-Wirecommunication,the1-Wiremasterstartseverybitwhetheritisdatatobereadorwrittentotheslavedevices.Duetothecharacteristicsofthe1-Wire,whenalldevicesrespondatthesametime,theresultwillbealogicalANDofthebitssent.AfterthedevicessendthefirstbitoftheirROMnumber,themasterinitiatesthenextbitandthedevicesthensendthecomplementofthefirstbit.Fromthesetwobits,informationcanbederivedaboutthefirstbitintheROMnumbersoftheparticipatingdevices.（SeeTable1.）

Table2BitSearchInformation

Bit

（true）

Bit

（complement）

InformationKnown

0

0

Thereareboth0sand1sinthecurrentbitpositionoftheparticipatingROMnumbers.Thisisadiscrepancy.

0

1

Thereareonly0sinthebitoftheparticipatingROMnumbers.

1

0

Thereareonly1sinthebitoftheparticipatingROMnumbers.

1

1

Nodevicesparticipatinginsearch.

Accordingtothesearchalgorithm,the1-Wiremastermustthensendabitbacktotheparticipatingdevices.Iftheparticipatingdevicehasthatbitvalue,itcontinuesparticipating.Ifitdoesnothavethebitvalue,itgoesintoawaitstateuntilthenext1-Wireresetisdetected.This'readtwobits'and'writeonebit'patternisthenrepeatedfortheremaining63bitsoftheROMnumber（seeTable2）.Inthiswaythesearchalgorithmforcesallbutonedevicetogointothiswaitstate.Attheendofonepass,theROMnumberofthislastdeviceisknown.Onsubsequentpassesofthesearch,adifferentpath（orbranch）istakentofindtheotherdeviceROMnumbers.NotethatthisdocumentreferstothebitpositionintheROMnumberasbit1（leastsignificant）tobit64（mostsignificant）.Thisconventionwasusedinsteadofbit0tobit63forconveniencetoallowinitializationofdiscrepancycountersto0forlatercomparisons.

OnexaminationofTable1,itisobviousthatifalloftheparticipatingdeviceshavethesamevalueinabitpositionthenthereisonlyonechoiceforthebranchpathtobetaken.Theconditionwherenodevicesareparticipatingisanatypicalsituationthatmayariseifthedevicebeingdiscoveredisremovedfromthe1-Wireduringthesearch.Ifthissituationarisesthenthesearchshouldbeterminatedandanewsearchcouldbedonestartingwitha1-Wirereset.

Table3WireMasterandSlaveSearchSequence

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.

Theconditionwherethereareboth0sand1sinthebitpositioniscalledadiscrepancyandisthekeytofindingdevicesinthesubsequentsearches.Thesearchalgorithmspecifiesthatonthefirstpass,whenthereisadiscrepancy（bit/complement=0/0）,the'0'pathistaken.Notethatthisisarbitraryforthisparticularalgorithm.Anotheralgorithmcouldbedevisedtousethe'1'pathfirst.Thebitpositionforthelastdiscrepancyisrecordedforuseinthenextsearch.Table3describesthepathsthataretakenonsubsequentsearcheswhenadiscrepancyoccurs.

Table4SearchPathDirection

SearchBitPositionvs

LastDiscrepancy

PathTaken

=

takethe'1'path

<

takethesamepathaslasttime（fromlastROMnumberfound）

>

takethe'0'path

Thesearchalgorithmalsokeepstrackofthelastdiscrepancythatoccurswithinthefirsteightbitsofthealgorithm.Thefirsteightbitsofthe64-bitregistrationnumberisafamilycode.Asaresult,thedevicesdiscoveredduringthesearcharegroupedintofamilytypes.Thelastdiscrepancywithinthatfamilycodecanbeusedtoselectivelyskipwholegroupsof1-Wiredevices.SeethedescriptionofADVANCEDSEARCHVARIATIONSfordoingselectivesearches.The64-bitROMnumberalsocontainsan8-bitcyclic-redundancy-check（CRC）.ThisCRCvalueisverifiedtoensurethatonlycorrectROMnumbersarediscovered.SeeFigure1forthelayoutoftheROMnumber.Figure2showsaflowchartofthesearchsequence.NotetheReferencethatexplainsthetermsusedintheflowchart.Thesetermsarealsousedinthesourcecodeappendixtothisdocument.Reference

Id_bit—thefirstbitreadinabitsearchsequence.ThisbitistheANDofalloftheid_bit_numberbitsofthedevicesthatarestillparticipatinginthesearch.

cmp_id_bit—thecomplementoftheid_bit.ThisbitistheANDofthecomplementofalloftheid_bit_numberbitsofthedevicesthatarestillparticipatinginthesearch.

Id_bit_number—theROMbitnumber1to64currentlybeingsearched.

LastDeviceFlag—flagtoindicateprevioussearchwasthelastdevice.

LastDiscrepancy—bitindexthatidentifiesfromwhichbitthe（next）searchdiscrepancycheckshouldstart.

LastFamilyDiscrepancy—bitindexthatidentifiestheLastDiscrepancywithinthefirst8-bitfamilycodeofROMnumber.

last_zero—bitpositionofthelastzerowrittenwheretherewasadiscrepancy.

ROM_NO—8-bytebufferthatcontainsthecurrentROMregistrationnumberdiscovered.

search_direction—bitvalueindicatingthedirectionofthesearch.Alldeviceswiththisbitstayinthesearchandtherestgointoawaitstatefora1-Wirereset.

TherearetwobasictypesofoperationsthatcanbeperformedbyusingthesearchalgorithmbymanipulatingtheLastDiscrepancy,LastFamilyDiscrepancy,LastDeviceFlag,andROM_NOregistervalues（seeTable4）.TheseoperationsconcernbasicdiscoveryoftheROMnumbersof1-Wiredevices.First

The'FIRST'operationistosearchonthe1-Wireforthefirstdevice.ThisisperformedbysettingLastDiscrepancy,LastFamilyDiscrepancy,andLastDeviceFlagtozeroandthendoingthesearch.TheresultingROMnumbercanthenbereadfromtheROM_NOregister.Ifnodevicesarepresentonthe1-Wiretheresetsequencewillnotdetectapresenceandthesearchisaborted.Next

The'NEXT'operationistosearchonthe1-Wireforthenextdevice.Thissearchisusuallyperformedaftera'FIRST'operationoranother'NEXT'operation.Itisperformedbyleavingthestateunchangedfromtheprevioussearchandperforminganothersearch.TheresultingROMnumbercanthenbereadfromtheROM_NOregister.Iftheprevioussearchwasthelastdeviceonthe1-WirethentheresultwillbeFALSEandtheconditionwillbesettoexecutea'FIRST'withthenextcallofthesearchalgorithm.

Thefollowinggoesthroughasimplesearchexamplewiththreedevices.Forillustration,thisexampleassumesdeviceswitha2-bitROMnumberonly.

SearchExample

（forsimplicitythefamilydiscrepancyregisterandtrackinghasbeenleftoutofthisexample）

FIRST

LastDiscrepancy=LastDeviceFlag=0

Do1-Wireresetandwaitforpresencepulse,ifnopresencepulsethendone

id_bit_number=1,last_zero=0

Sendsearchcommand,0F0hex

Readfirstbitid_bit:

1（DeviceA）AND0（DeviceB）AND1（DeviceC）=0

Readcomplementoffirstbitcmp_id_bit:

0（DeviceA）AND1（DeviceB）AND0（DeviceC）=0

Sinceid_bit_number>LastDiscrepancy，thensearch_direction=0,last_zero=1

Sendsearch_directionbitof0,bothDeviceAandCgointowaitstate

Incrementid_bit_numberto2

Readsecondbitid_bit:

0（DeviceB）=0

Readcomplementofsecondbitcmp_id_bit:

1（DeviceB）=1

Sincebitandcomplementaredifferentthensearch_direction=id_bit

Sendsearch_directionbitof0,DeviceBisdiscoveredwithROM_NOof‘00’andisnowsel