二叉树算法在单总线上的C51软件实现

2021-06-10来源: eefocus关键字:单总线  C51

引 言


单总线技术是将地址线、数据线和控制线合成一根线,并允许在该线上挂接多个单总线器件。其搜索ROM命令可以在线识别挂接在总线上器件的注册码和器件的类型,并可在线确定总线上的器件数量;但是,对于多个在线器件,毫不遗漏搜索出每个器件的注册码比较困难,在本文中,作者把多个器件注册码的数据结构抽象为一种二叉树,从而通过二叉树算法实现对在线所有的单总线器件的注册码的自动搜索,并能根据注册码自动识别器件类型和总线上的器件数量。


1 单总线技术


单总线技术搜索ROM的过程是主设备获取单总线上从器件的注册码的过程,是一种简单的三步操作过程的重复,即先读一位,其次读该位的反码,然后再写一位,选中其中的一部分器件(详见参考文献[1])。重复执行这三步操作,可获得设备注册码其余各位。


根据每两次读的数据可作如下判断:


00:总线上有器件,且它们的注册码在该位既有“1”,也有“0”;


01:总线上器件的注册码在该位是“1”;


10:总线上器件的注册码在该位是“0”;


11:总线上没有器件。


2 二叉树搜索算法


二叉树(binary tree)是n(n≥0)个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成,且左子树和右子树有严格的区分。


遍历一棵二叉树就是按某种次序系统地访问二叉树上的所有结点,并且每个结点只允许访问一次。遍历运算的关键在于访问结点的次序,应保证二叉树上每个结点均被访问且仅被访问一次(详见参考文献[2])。


3二叉树搜索算法的应用


根据多个单总线器件注册码所构成的数据结构和二叉树的特点,可认为单总线上所有器件注册码构成了一个深度为64的二叉树(相关资料见参考文献[2]),在遍历二叉树的过程中可根据读取的两次数据判断结点是左子结点、右子结点还是叶子结点,即:


00:表示既存在左子结点,也存在右子结点,该位有“0”,也有“1”;


01:表示只存在左子结点,该位为“0”;


10:表示只存在右子结点,该位为“1”。


11:表示不存在子结点,也就说明没有从器件挂接在总线上。


在遍历二叉树时,记录所走的路径和搜索到的叶子结点数,可以得到从器件的注册码和从器件数量。


第一次搜索从器件的注册码时,如果左子结点和右子结点都存在,需要记录该分叉结点的深度,并沿左子树的方向向下搜索,当搜索深度达到64时,获得一个从器件的注册码,并取出该搜索路径最后的分叉结点的深度,然后主器件执行第二次搜索过程。在该搜索过程中,如果结点的深度值小于最后一个分叉结点的深度,则发送上次搜索到的在最后一个分叉结点前的注册码的相应位;如果结点的深度值等于最后一个分叉结点的深度,则发送上次搜索到的在最后一个分叉结点处发送的数据的反码,并且删除该分叉结点的记录,如在后面的搜索中遇到分叉结点,同样需要记录分叉结点的深度。这样,每搜索到一个深度为64的叶子结点,就会得到一个从器件的注册码,一直搜索到记录中没有分叉结点为止。


图1 软件流程图


如表1所示,设有三个从器件1、2和3,主设备第一次读取的数据是“10”,可知从器件的注册码的第一位都为“0”,主设备写“0”;第二次读取的数据是“00”,可知在线从器件的注册码在该位既有“0”,也有“1”,记下该分叉结点的深度(记录的位1置“1”);主设备写“0”,搜索左子树结点,选中从器件1和从器件3(如主设备写“1”则选中从器件2),第三次读取的数据是“01”,可知选中的从器件的注册码在该位都是“1”,主设备写“1”,第四次读取的数据是“00”,从器件的注册码在该位既有“0”,也有“1”,记下该分叉结点的深度(记录的位3置“1”),主设备写“0”,选中从器件1,依次类推搜索从器件1的其余结点,当深度达到64时,即获得从器件1的注册码;从记录中找出最后一个分叉结点,即记录的位3,重新从根结点开始搜索,在分叉结点之前,每读两次数据后,发送前一个从器件(从器件1)注册码的相应位,在分叉结点2,发送前一个从器件的注册码相应位的反码“1”,选中从器件2和3,搜索右子树结点,并把记录分叉结点的相应位(记录的位3)清“0”,依次读取从器件2和3注册码的剩余位;并在记录中记录相应位,按照同样的方法,可获得从器件2的注册码,直到记录中的各位都为“0”时,搜索结束。由搜索得到数据可知,从器件1、从器件2和从器件3的注册码的前8位(家族码)分别是:28H、20H和2CH,所以它们分别是温度传感器DS18B20、模数转换芯片DS2450和单路数字电位器DS2890。


表格 1 搜索注册码





4 软件设计


流程图如图1所示,number[64 ,0 ]表示number为64 位的变量,初始化为0,存储从器件的ROM 序列号,Record 用来记录存在分支的结点位置,list[n]表示记录中的第n位,初始化为“0”,n 表示搜索到的位数。


下面是部分软件:


/**自动识别多个在线芯片序列号***/


void find_serial()


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


m=0;end=0;


reset_num(); //复位单总线


command_num(0x0F0,0x08);//发搜索命令


while (1)


{for (n=1;n<65;n++)//读深度为64的二叉树


{k=(n-1)/8; //每8位放到数组中


j=Read_serial(0x02);//连续读两次数serial[k]=serial[k]>>1;


if(j==0x01) //第一次为1,第二次为0


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


command_num(0x01,0x01);//发送1


read_bit[n]=0;


}


if (j==0x02) //第一次为0,第二次为1


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


command_num(0x00,0x01); //发送0


read_bit[n]=0;


}


if(j==0x00) //两次都为0,记录分叉点


{if (n

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


/*发前一个已搜索器件注册码*/


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)//如有分叉点,重新搜索


{reset_num();


command_num(0x0F0,0x08);


}


else


{break;}


}


}


5 结论


在作者设计的温室控制系统的软件中,当系统每次上电时,微处理器首先应用二叉树算法搜索在线的所有单总线器件的注册码,并区分器件类型;对于撤离的或新增加的从器件,系统可以动态的获得它的注册码,实现了对从器件的动态管理。该算法适用于任何具有1-Wire 接口特性单总线器件。


关键字:单总线  C51 编辑:什么鱼 引用地址:http://news.eeworld.com.cn/mcu/ic538271.html

上一篇:交通事故现场防入侵设备设计
下一篇:最后一页

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利

推荐阅读

完美实现STM32单总线挂多个DS18B20
一般常见的STM32的关于DS18B20的例程都是检测一个传感器,代码一般都是跳过ROM检测,直接获取温度值。这种写法并不适用于单总线上挂载多个DS18B20的情况,Sandeepin的这个代码就是针对这种情况完善的单总线挂多个DS18B20检测,实现获取每个DS18B20的ID和温度。主要的DS18B20时序代码没变,增加了搜索ROM函数,获取温度时先匹配ID。核心代码如下:DS18B20.c文件代码:#include "DS18B20.h"  #include "Delay.h"  #include "stdio.h"
发表于 2020-12-03
完美实现STM32<font color='red'>单总线</font>挂多个DS18B20
单片机单总线挂2片ds18b20传感器,8位数码同时管显示
; Delay_DS18B20(80);  //精确延时,大于480us        DQ = 1;                 //拉高总线        Delay_DS18B20(14);        x = DQ;                   //稍做延时后,如果x=0则初始化成功,x=1则初始化失败
发表于 2020-11-11
教你使用一个单片机IO口控制RGB彩灯,单总线LED灯使用教程
,那就是单总线LED。简单点来说就是这种类型的灯珠内置了一个驱动电路,它控制着灯珠发出的颜色,并且有一个数据输入口,意味着我们可以往在这个灯珠里面输入数据,然后灯珠内部的电路就会驱动的灯珠发出我们想要的颜色。这个电路呢还有一个数据的输出口,也就是说它可以将接受到的数据再次发送出去,送给下一个灯珠的输入,所以这使得所有的灯珠都可以连在一起,只需要使用一个IO口控制,这就相比传统的RGB灯节省了很多的端口。这种类型的灯珠主要的核心就在它里面集成的那样一个驱动电路,这种类型的驱动电路有很多种,例如常见的WS2811,2812,SK6812等等,所以用其制作完成的灯珠一般都使用驱动电路的名字来命名。对于灯珠的大小型号呢,则有很多种
发表于 2019-11-12
教你使用一个单片机IO口控制RGB彩灯,<font color='red'>单总线</font>LED灯使用教程
DS18B20-Onewire Bus-单总线 单片机读取温度
(void){ unsigned char x=0; DQ = 1;    //DQ复位 delay(8);  //稍做延时 DQ = 0;    //单片机将DQ拉低 delay(300); //精确延时 大于 480us DQ = 1;    //拉高总线 delay(10); x=DQ;      //稍做延时后 如果x=0则初始化成功 x=1则初始化失败 delay(5);} 
发表于 2019-05-21
完美实现STM32单总线挂多个DS18B20
  一般常见的STM32的关于DS18B20的例程都是检测一个传感器,代码一般都是跳过ROM检测,直接获取温度值。这种写法并不适用于单总线上挂载多个DS18B20的情况,Sandeepin的这个代码就是针对这种情况完善的单总线挂多个DS18B20检测,实现获取每个DS18B20的ID和温度。  主要的DS18B20时序代码没变,增加了搜索ROM函数,获取温度时先匹配ID。  核心代码如下:  DS18B20.c文件代码:#include "DS18B20.h"  #include "Delay.h"  #include "stdio.h"
发表于 2018-06-07
单总线AT89C51单片机多机通讯系统设计
提出了用单总线完成单片机通讯的方法。结合系统既传输数字信号又传输模拟信号的特点,提出用消侧音电路解决模拟信号的方案,并给出了详细的技术解决方案。 传统的多机通讯系统一般需要四条线完成:1.电源线;2.地线;3.发送信号线;4.接收信号线。然而,对于主机和分机距离较远、分机台数较多的系统,采用四线制的经费投入较大,安装起来也颇困难。基于这一问题,本文结合为某医院研制的既有模拟信号(语音)又有数字信号的传输呼叫系统,提出用单总线实现多机通讯,并给出了一个完整的技术方案。1 单总线制多机通讯系统的总线设计方案本设计实现的多机呼叫系统的主要功能是:分机呼叫主机,利用单片微机向主机发送数字呼叫信息,主机响应后,显示出呼叫的分机号
发表于 2017-12-29
小广播
何立民专栏 单片机及嵌入式宝典

北京航空航天大学教授,20余年来致力于单片机与嵌入式系统推广工作。

换一换 更多 相关热搜器件
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号 Copyright © 2005-2021 EEWORLD.com.cn, Inc. All rights reserved