日韩床上生活一级视频|能看毛片的操逼网站|色悠悠网站在线观看视频|国产免费观看A淫色免费|国产av久久久久久久|免费A级视频美女网站黄|国产毛片av日韩小黄片|热久久免费国产视频|中文字幕无码色色|成人在线视频99久久久

摘要：?jiǎn)慰偩�技術(shù)是一種新技術(shù),由于所有的單總線器件均并聯(lián)在一條信號(hào)線上,其信號(hào)傳輸較慢,主要應(yīng)用于低速測(cè)控系統(tǒng)中,使系統(tǒng)線路結(jié)構(gòu),但是在線檢測(cè)這些單總線器件成為單總線技術(shù)中的一個(gè)難題,本文提出了用二叉樹(shù)算法搜索單總線器件注冊(cè)碼，并給出了C51軟件，實(shí)現(xiàn)了在線檢測(cè)單總線ROM。
關(guān)鍵詞：二叉樹(shù)算法；C51；單總線

0引言

單總線技術(shù)是將地址線、數(shù)據(jù)線和控制線合成一根線，并允許在該線上掛接多個(gè)單總線器件。其搜索ROM命令可以在線識(shí)別掛接在總線上器件的注冊(cè)碼和器件的類(lèi)型，并可在線確定總線上的器件數(shù)量；但是，對(duì)于多個(gè)在線器件，毫不遺漏搜索出每個(gè)器件的注冊(cè)碼比較困難，在本文中，作者把多個(gè)器件注冊(cè)碼的數(shù)據(jù)結(jié)構(gòu)抽象為一種二叉樹(shù)，從而通過(guò)二叉樹(shù)算法實(shí)現(xiàn)對(duì)在線所有的單總線器件的注冊(cè)碼的自動(dòng)搜索，并能根據(jù)注冊(cè)碼自動(dòng)識(shí)別器件類(lèi)型和總線上的器件數(shù)量。

1 單總線技術(shù)

單總線技術(shù)搜索ROM的過(guò)程是主設(shè)備獲取單總線上從器件的注冊(cè)碼的過(guò)程，是一種簡(jiǎn)單的三步操作過(guò)程的重復(fù)，即先讀一位，其次讀該位的反碼，然后再寫(xiě)一位，選中其中的一部分器件（詳見(jiàn)參考文獻(xiàn)[1]）。重復(fù)執(zhí)行這三步操作，可獲得設(shè)備注冊(cè)碼其余各位。

根據(jù)每?jī)纱巫x的數(shù)據(jù)可作如下判斷：

 00：總線上有器件，且它們的注冊(cè)碼在該位既有“1”，也有“0”；

01：總線上器件的注冊(cè)碼在該位是“1”；

10：總線上器件的注冊(cè)碼在該位是“0”；

11：總線上沒(méi)有器件。

2 二叉樹(shù)搜索算法

     二叉樹(shù)（binary tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，且左子樹(shù)和右子樹(shù)有嚴(yán)格的區(qū)分。

遍歷一棵二叉樹(shù)就是按某種次序系統(tǒng)地訪問(wèn)二叉樹(shù)上的所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)只允許訪問(wèn)一次。遍歷運(yùn)算的關(guān)鍵在于訪問(wèn)結(jié)點(diǎn)的次序，應(yīng)保證二叉樹(shù)上每個(gè)結(jié)點(diǎn)均被訪問(wèn)且僅被訪問(wèn)一次（詳見(jiàn)參考文獻(xiàn)[2]）。

2 二叉樹(shù)搜索算法的應(yīng)用

根據(jù)多個(gè)單總線器件注冊(cè)碼所構(gòu)成的數(shù)據(jù)結(jié)構(gòu)和二叉樹(shù)的特點(diǎn)，可認(rèn)為單總線上所有器件注冊(cè)碼構(gòu)成了一個(gè)深度為64的二叉樹(shù)（相關(guān)資料見(jiàn)參考文獻(xiàn)[2]），在遍歷二叉樹(shù)的過(guò)程中可根據(jù)讀取的兩次數(shù)據(jù)判斷結(jié)點(diǎn)是左子結(jié)點(diǎn)、右子結(jié)點(diǎn)還是葉子結(jié)點(diǎn)，即：

00： 表示既存在左子結(jié)點(diǎn)，也存在右子結(jié)點(diǎn)，該位有“0”，也有“1”；

01： 表示只存在左子結(jié)點(diǎn)，該位為“0”；

10： 表示只存在右子結(jié)點(diǎn)，該位為“1”。

11： 表示不存在子結(jié)點(diǎn)，也就說(shuō)明沒(méi)有從器件掛接在總線上。

在遍歷二叉樹(shù)時(shí)，記錄所走的路徑和搜索到的葉子結(jié)點(diǎn)數(shù),可以得到從器件的注冊(cè)碼和從器件數(shù)量。

第一次搜索從器件的注冊(cè)碼時(shí)，如果左子結(jié)點(diǎn)和右子結(jié)點(diǎn)都存在，需要記錄該分叉結(jié)點(diǎn)的深度，并沿左子樹(shù)的方向向下搜索，當(dāng)搜索深度達(dá)到64時(shí)，獲得一個(gè)從器件的注冊(cè)碼，并取出該搜索路徑最后的分叉結(jié)點(diǎn)的深度，然后主器件執(zhí)行第二次搜索過(guò)程。在該搜索過(guò)程中，如果結(jié)點(diǎn)的深度值小于最后一個(gè)分叉結(jié)點(diǎn)的深度，則發(fā)送上次搜索到的在最后一個(gè)分叉結(jié)點(diǎn)前的注冊(cè)碼的相應(yīng)位；如果結(jié)點(diǎn)的深度值等于最后一個(gè)分叉結(jié)點(diǎn)的深度，則發(fā)送上次搜索到的在最后一個(gè)分叉結(jié)點(diǎn)處發(fā)送的數(shù)據(jù)的反碼，并且刪除該分叉結(jié)點(diǎn)的記錄，如在后面的搜索中遇到分叉結(jié)點(diǎn)，同樣需要記錄分叉結(jié)點(diǎn)的深度。這樣，每搜索到一個(gè)深度為64的葉子結(jié)點(diǎn)，就會(huì)得到一個(gè)從器件的注冊(cè)碼，一直搜索到記錄中沒(méi)有分叉結(jié)點(diǎn)為止。

表格 1 搜索注冊(cè)碼

4 軟件設(shè)計(jì)

流程圖如圖1所示，number[64 ,0 ]表示number為64 位的變量，初始化為0，存儲(chǔ)從器件的ROM 序列號(hào)，Record 用來(lái)記錄存在分支的結(jié)點(diǎn)位置，list[n]表示記錄中的第n位，初始化為“0”，n 表示搜索到的位數(shù)。

下面是部分軟件：

/**自動(dòng)識(shí)別多個(gè)在線芯片序列號(hào)***/

void find_serial() 

{char n,j,m,k,record,end,ks,mm,nn;  

 m=0;end=0;

reset_num(); //復(fù)位單總線

command_num(0x0F0,0x08);//發(fā)搜索命令

while (1)

{for (n=1;n<65;n++)//讀深度為64的二叉樹(shù)

{k=(n-1)/8;    //每8位放到數(shù)組中

j=Read_serial(0x02);//連續(xù)讀兩次數(shù)serial[k]=serial[k]>>1;

 if(j==0x01)    //第一次為1，第二次為0

   {serial[k]=serial[k]|0x80;//存該位1

command_num(0x01,0x01);//發(fā)送1

    read_bit[n]=0;

    }

 if (j==0x02)  //第一次為0，第二次為1

  {serial[k]=serial[k]&0x7f; //存該位0

   command_num(0x00,0x01); //發(fā)送0 

   read_bit[n]=0;

  }

 if(j==0x00)  //兩次都為0，記錄分叉點(diǎn)

  {if (n<record) //深度是小于64

     {ks=(serial1[k]>>((n-1)%8))&0x01;

/*發(fā)前一個(gè)已搜索器件注冊(cè)碼*/

     command_num(ks,0x01);

     serial[k]=serial[k]|0x80;//存該位

     if (ks==0) {serial[k]=serial[k]&0x7f;}

     }

  else if (n>record)//深度是大于64

    {command_num(0x00,0x01);

     read_bit[n]=1;//記錄

     serial[k]=serial[k]&0x7f;

}

  else

    {ks=(n-1)/8;mm=(n-1)%8;

     nn=serial1[ks]>>mm;

if ((nn&0x01)==1)

   {serial[ks]=serial[ks]&0x7f;

    command_num(0x00,0x01);

    }

 if ((nn&0x01)==0)

   {serial[ks]=serial[ks]|0x80;

    command_num(0x01,0x01);

   }

 read_bit[n]=0;//清記錄

  }

 }

}

for(nn=0;nn<8;nn++)

  {serial1[nn]=serial[nn];}

if (n>64)

    {for (j=64;j>0;j--)//從末尾搜索記錄

      {if (read_bit[j]!=0)

{record=j;n=1;

read_bit[j]=0;

break;

}

       else

          {record=0;}//清記錄

      }

    }

   if (record!=0)//如有分叉點(diǎn)，重新搜索

    {reset_num();

     command_num(0x0F0,0x08);

    }

else

    {break;}

}

}

5 結(jié)論

參考文獻(xiàn)

[1]Dallas Semiconductor Data Books.

Dallas Semiconductor Corporation 1995

[2]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)庫(kù)結(jié)構(gòu)[M].清華大學(xué)出版社,1998