📦 定时电路设计问题：定时电路是一个VLSI 芯片的关键部件 - 免费下载

定时电路设计问题：定时电路是一个VLSI 芯片的关键部件，这里给出一个定时电路的 简单模型：一棵具有n 片树叶的完全平衡二叉树（其中，n 是2 的幂）。这颗树的每条 边e 有一个对应的长度le（le>0）。从根到一片给定树叶的距离是从根到这片树叶的路径 上的所有边的长度之和。 根产生一个时钟信号，它沿着这些边传播到树叶，信号到达一片给定树叶所用的时间是 与从根到这片树叶的距离成比例的。如果所有的树叶到根的距离都不相同，那么信号不会在同一时间到达树叶，这是定时电 路设计中的一个大问题，我们需要树叶完全同步，全都同时接受这个信号，为做到这一 点，我们将不得不增加某些边的长度，以使得所有根到树叶的路径有同样的长度，如果 我们达到这个要求，那么这棵树（带有它的新边长）将称为零倾斜的。我们的优化目标 是以某种保持所有边长之和最小的方式达到零倾斜。给出了一个增长某些边长的算法，使得得到的树有零倾斜并且总边长最小。

点击标签查看更多相关资源：