硬件中的高效可靠的时钟同步
技术领域
本发明涉及用于同步数个时钟脉冲的方法及其中所使用的包含亚稳态的电路。
背景技术
在数字电路中，亚稳态信号具有严格在逻辑0和逻辑1之间的电压，从而打破布尔逻辑的抽象。不幸的是，读取来自非同步时钟域的信号或者执行模-数转换的任何方式都引起亚稳态结果的风险；数字电路的任何物理实现均不能确定性地避免、解决或检测亚稳态(L.R.Marino.亚稳态操作的一般理论(General theory of metastable operation).IEEETransactions on Computers，30(2)：107，115，February 1981)。
传统上，唯一对策是将潜在的亚稳态信号写入同步器(像触发器一样的双稳态存储元件)内并等待。同步器使所维持的亚稳态的几率随时间推移呈指数下降，即，等待时间确定了分辨(resolve)为逻辑0或1的概率。因此，这种方法使后续的计算延迟且并不保证成功。
一种有前景的替代方案是运行容错式时钟同步算法，如Lynch和Welch所提出的算法(J.Lundelius Welch和N.A.Lynch.一种新的时钟同步容错算法(A new fault-tolerantalgorithm for clock synchronization).Information and Computation，77(1)：1{36，1988)，保留了多个始终的好处，同时不需要同步器。
Welch和Lynch的算法被广泛应用于例如时间触发协议(TTP)和FlexRay时钟同步协议。虽然TTP和FlexRay的基于软件/硬件的实现实现了1毫秒量级的精度，但是更高的操作频率最终需要纯硬件的实现。
但是，所有已知的实现使潜在的亚稳态输入在计算之前同步——一种随着工作频率增加而变得不太可靠的技术，因为可用于亚稳态分辨的时间较少。而且，亚稳态紊乱的平均故障间隔时间(MTBF)的典型边界假定输入转变是均匀分布的；这并不保证是时钟同步下的情形，因为目标是要调整时钟节拍(ticks)。无论哪种方式，同步器都无法确定性地确保稳定，并且当n个时钟在例如1GHz下采集了n(n-1)个样本时，误差最终必然会产生。
因此，本发明的目的是提供一种方法和对应的数字电路，用于在硬件中进行高效可靠的时钟同步，其不依赖于无亚稳态的输入，因而也并不会受亚稳态紊乱所引起的系统故障影响。
发明内容
这个目的通过独立的权利要求所限定的方法和电路来实现的。有利的实施例在从属权利要求中进行限定。
在另一方面，本发明提出并分析了一种不需要模拟部件的，即纯“数字”的新颖TDC设计。而且，它需要比相同精度和最大范围的延迟线TDC或Nutt插值器(interpolator)少得多的门(gate)。TDC设计支持高的测量频率。在大多数应用场景中，在启动和停止信号之间的最大时间将会支配着一次测量所需的时间。量化误差由最小时间差确定，该最小时间差是为了确保从环形振荡器中的两个连续级同时采样导致各锁存器中的最多一个锁存器的亚稳态所需要的。对于90nm的技术，这样的设计已经被用来获得大约20ps的误差。它支持对在两个远程信号之间的时间差进行多重采样(即，针对同一启动信号的多次测量)和直接测量两者。亚稳态分辨在读取了TDC之后发生。TDC输出使得测量值能够被复制到其它地方，从而给它们时间在存储器中进行分辨。可能的分辨被显示为一致且精确的精度。这意味着，从在不影响TDC的尺寸或者阻止其重新用于另一次测量的情况下可以选择分配给对测量值进行的亚稳态分辨的时间跨度的意义上说，TDC是自适应的。
附图说明
本发明的这些及其它方面将在下面关于本发明的各种实施例的详细描述中结合附图进行更详细的解释。在附图中
图1示出了根据本发明的实施例的用于同步时钟脉冲的算法(以伪代码表示)。
图2示出了在离线校准期间的已编码的TDL输出值的直方图。这些值对应于延迟线的区间(bin)尺寸。
图3示出了按顺序测量的三个节点在1小时的时段内相对于同一参考节点的时钟偏斜(skew)的长期演进。粗线表示在10秒钟内的平均时钟偏斜，以浅黄色填充的细线表示在同一间隔内的最小值和最大值。
图4示出了在图3中的任意选择的20秒的时段内的“蓝色”节点对参考节点的时钟偏斜的短期行为。
图5示出了在按顺序测量的全部节点对之间的TDEV。这些节点对的颜色与图3中的那些节点对的颜色相匹配。
图6示出了在节点与铷频标之间的ADEV。顶部(蓝色)曲线与自由运行的振荡器相比较，算法被禁用。底部(红色)曲线是算法被启用的且系统已完全同步的同一节点。在超过τ＝100s时，温度影响是不同的，因为踪迹是在天气条件不同并因而建筑物的加热模式不同的连续日子里记录的。
图7示出了在硬件中用于容错式时钟同步的关系(concern)(模拟-含亚稳态的数字-模拟)的分离。
图8示出了分接式延迟线TDC。它被读作1kon-k或1kM0n-k-1，即，最多产生一个亚稳态位并因此具有精度-1。
图9示出了高效的TC-BRGC转换。
图10的左图示出了分接式延迟线TDC体系架构。锁存器被初始化为0。右图示出了所提出的含亚稳态的TDC的体系架构。锁存器和二进制计数器被初始化为0。保持着b的寄存器经由延迟缓冲器来驱动C0和C1的递增输入。计数器C0在上升转变时递增，C1在下降转变时递增。
图11是根据本发明的实施例的分接式延迟线TDC的FPGA原型的示意性概览图。
图12示出了具有前瞻式格雷码计数器和寄存器的实现。计数器C以1来初始化。寄存器Rc具有与计数器相同的宽度，并且以0来初始化。
图13示出了具有单位锁存器的格雷码计数器变体。
图14示出了图13的格雷码计数器变体的临界窗口。
图15示出了根据本发明的实施例的用于确定给定的有效B位格雷码字符串的一元编码的方法的递归实现。
图16的左图示出了含亚稳态的(2：1)-CMUX的逻辑表，该(2：1)-CMUX的单个控制位s被用来在两个输入a和b之间进行选择。右图示出了使用与门(AND)和来自[5]的或门(3)(OR(3))的(2：1)-CMUX的实现。
图17的上图示出了(4：1)-CMUX的输出。控制位是s和t，可选择的输入是a、b、c、d。下图示出了根据本发明的实施例的使用(2：1)-CMUX的实现。
图18示出了根据本发明的实施例的2-sort(B)的递归实现。
图18a(表III)是在定理V.5(Exp.)(指数)和定理Vl.4(Poly.)(多项式)中给出的2-sort(B)的实现的成本和延迟的总结。
图18b(表IV)列出了用于n∈{4，7，10}、由2-sort(B)的实现导出的B位输入的、含亚稳态的排序网络的门和晶体管计数。
图19示出了根据本发明的另一实施例的cont(B)的递归实现。
图20示出了2-sort(B)的递归实现。为了获得控制输入(c0[1]；c0[2])，g0和h0被馈送入cont(B/2)电路(参见图19)。
图21示出了门级MUX在a＝b＝1的输入下的行为；在这种情况下，输出应当为1，不管选择位s是什么。但是，对于s＝M，标准的MUX(a)可能会变成亚稳态的。根据本发明的实施例的CMUX的实现(b)使用逻辑屏蔽并输出1。
图22示出了根据本发明的实施例的CMUX实现。CMUX-A(a)是需要10个晶体管且具有低峰值电流的保守的实现，CMUX-B(b)节省了2个晶体管，但是在s＝M且a＝b的情况下具有略有增加的峰值电流。
图23示出了根据本发明的实施例的由三个2-CMUX组装的4-CMUX。
图24示出了在使用CMUX-B时所节省的晶体管。
具体实施方式
图1示出了根据本发明的实施例的用于同步时钟脉冲的算法(以伪代码表示)。
可以运行该算法的系统被假定包含完全通过(1位)广播信道来连接的n个节点的集合V。每个节点v∈V是一个故障包含区域：单个(物理)故障(如门故障)不直接影响在含有故障部件的故障包含区域之外的部件的正确性。节点v包含本地物理时钟Hv(例如环形振荡器)、用于为节点v实现算法的逻辑的电路及其引出的链路。这意味着，通信不使用将是单个故障点的共享总线。由v进行时钟控制的任何潜在的应用逻辑将同样是其故障包含区域的一部分。因而，v的部件的任何临时的或永久的故障(在故障包含区域内)仅经由通信间接地影响其它节点。故障节点(即，其包含区域含有故障部件的节点)可以任意表现；尤其是，它可以在不同的时间仅给节点的子集发送时钟脉冲。假定，至多
在C中的节点通过广播来通信。如果v∈C在时刻tv广播，则任何其它正确节点w∈C在某个时刻twv∈[tv+d-U，tv+d]已经接收并处理了相应的脉冲，其中d为最大延迟，并且U为延迟不确定度。对于在VC中的故障发送者，这样的限制是不相关的，因为它们可能以任意方式偏离协议，即，在任意时间独立地给不同的接收者发送脉冲。
正确的节点测量相对于在同一循环(round)内的该正确节点自身的脉冲的到达时间的、其它节点的脉冲的到达时间(参见算法1)。这通过回送广播信号并使用时间-数字转换器(TDC)来确定相应的时间差来完成(参见部分III-B)。当对在满足e(|t-t|)＝G+v|t-t|的时刻t和t’到达的信号进行比较时，假定本发明的TDC的单侧最坏情况测量误差，其中G是TDC的粒度(即，其离散化误差)，并且v＜＜1是TDC的时间基准的频率相对于其标称频率的最大相对偏差。
节点v无法访问真实时间，而只能访问其本地时钟
其中v＜1是接近于1的常数，用于描述本地时钟的频率偏移不确定度。为了简单起见，在下文中设定v＝υ-1，即，节点的时钟源及其TDC具有相同的最坏情况相位漂移。假定对于所有v∈C有Hv(0)∈[0，F)，其中F由引导处理的精度确定。为了更好的可读性，真实时间以t表示，并且本地时间以τ表示，具有各自的指数。
每个节点v∈V在时刻tv(r-1)启动循环r∈N，并且在tv(r)结束循环r，其中tv(0)＝F。要完全指定该算法，需要确定τ1、τ2和TR。以下条件足以促使算法按预期工作。
τ1≥υF
τ2≥υ(F+τ1+d)
TR≥υ(τ1+F+U)+τ2+tcomp+G，
其中tcomp是计算并施加相位校正所需的时间。期望使循环长度TR保持为小的，除非试图要降低通信频率。因为满足这些不等式的任何值是可接受的，所以可以总是取整(round)到控制该逻辑的振荡器的周期时间的下一个整数倍数，即，不需要对振荡器频率进行约束。对于υ-1＜＜1，最小的可行选择会导致E≈4(U+G)的稳态偏斜。该算法能够处理高达υ-1≈1％的频率偏移而不会对E造成显著影响。
在优选的实施例中，可以对上述方法进行修改，以处理(n-f)个节点被同步但另外的节点不同步(可能在发生瞬时性故障之后)并尝试重新同步的情况。对该算法的修改是，每当节点在给定的循环内接收到少于(n-f)个信号(在收听它们的时候)时，它将会中断该循环。因而，它迅速地赶上主场(main field)。
在对τ1、τ2和TR稍微更保守的约束下，这会导致在数量恒定的循环中重新同步。但是，这要求实现(i)确保节点确实在由最大循环持续时间界定的时间内开始执行下一循环，不管其易失性存储器的内容如何，并且(ii)它不会引入其值被延续到下一循环的任何变量。
结合图1进行描述的算法在四个Cyclone IV FPGA开发板上实现。另外的开发板被设计用于装载用于FPGA的时钟振荡器以及用于节点间的同轴电缆的连接器。为了允许用子时钟周期粒度来校正脉冲位置，相位偏移使用压控晶体振荡器(VCXO)而被施加，该压控晶体振荡器(VCXO)为FPGA内的PLL提供参考频率。这些节点使用相同长度(约30cm)的同轴电缆来相互连接，每对节点及每个方向一条同轴电缆。FPGA实现了用于测量传入脉冲的时序的现有技术的TDC的四种状态，实现算法的逻辑，并且控制VCXO。另外的脉冲输出可用于测量。
由于开发板的限制，脉冲使用3：3V LVCMOS信令。所产生的反射略微增加测量结果的不确定性。而且，FPGA开发板仅提供用于地线连接的两个引脚。这导致算法的容错性能的不自主测试：在同一连接器上有许多高速信号，该设置会受到在开发板和接口板的地电位之间高达200mV的显著地弹(ground bounce)的影响；这导致节点之一在本发明的实验期间丢失几个时钟节拍。
FPGA用从接口板上的20MHz的VCXO导出的130MHz进行时钟控制。如上所述，为了实现对脉冲的相位的子周期长度(即小于7：7ns)校正，控制参考振荡器的输出频率。这使用具有SPI接口的16位的1Msps的DAC来实现。这种设计选择对本发明的实现施加了两个重要的限制。首先，振荡器的约10kHz的调制带宽对循环长度施加了下限，因为需要有足够的时间让振荡器响应已改变的控制输入。因此，选择TR＝50μs的相当大的循环长度，其中的40μs被分配用于使时钟相位偏移。
其次，振荡器的调谐(tune)范围约为10ppm，从而将每循环的相位校正限定为≈400ps。这小于FPGA的时钟周期的持续时间(≈7.7ns)，从而通过允许调整每循环的时钟周期数(整数)来阻止较大相位偏移的简单实现。幸运的是，收敛性分析表明，该算法在这种对相位校正的限制下实现了相同的稳态误差。但是，为恢复节点以重新同步所需的循环次数要大得多；对于至多10ppm的频率校正，这需要高达大约105次循环，从而对恢复时间产生以秒为量级的最坏情况限定。
来自该设置的性能关键性参数是：
●如上所述，对于TDC具有G≤160ps。
●在开发板和接口板上的线延迟的差异使用TDC来校准。这导致U≤G+40ps≤200ps的不确定度，其中40ps是在TDC之间的等效通路中的延迟变化的估计上限。
●<1.5ppm的在一对振荡器之间的频率偏差被测量。制造商列出了典型的频率偏差，包括典型的3ppm(即υ-1≈3.10-6)的初始偏差和过温范围(over temperature range)。
将这些值插入从分析中获得的界限，在没有故障的情况下，所估计的最坏情况时钟偏斜为2(G+U)+(υ-1)TR＝870ps，其中TR＝50μs是循环的标称持续时间。在有故障的情况下，该时钟偏斜变为4(G+U)+2(υ-1)TR＝1740ps。
测量通过WaveCrest DTS-2075来进行，该WaveCrest DTS-2075具有±25ps的单发精度以及校准的输入端口偏斜以实现好于2ps的精度。为了排除来自仪器的任何乱真影响，两个斯坦福研究系统(Stanford Research)SR620被用来验证这些界限。
图2示出了在离线校准期间的已编码的TDL输出值的直方图。这些值对应于延迟线的区间尺寸。
图3示出了按顺序测量的在1小时的时段内三个节点相对于同一参考节点的时钟偏移的长期演进。粗线描绘在10秒钟内的平均时钟偏斜，以浅黄色填充的细线描绘在同一间隔内的最小值和最大值。
图4示出了在图3中的任意选择的20秒的时段内的“蓝色”节点对参考节点的时钟偏斜的短期行为。在所有节点对之间的偏斜被按顺序测量，每个至少一个小时，这对应于7.2·107次循环。180ps的最大时钟偏斜在正确工作的节点之间被观察到。
为了测试在最坏情况故障下的行为，一个节点被修改，目的是要使剩余节点的偏斜最大化。该分析表明，当故障节点向已经领先的节点发送早期脉冲并且没有向滞后的节点发送时，可以达到故障的最大影响。在实施了此行为之后，可观察到最大偏斜增加到270ps。
为了验证节点在瞬时性故障状态之后重新同步，使用手动致动的开关来修改一个节点以使其退出。每隔几秒触发开关会导致相对于已正确同步的节点的时钟相位而随机分布的重启时间。在20次测量中，观察到预期的稳定化行为。根据先前的讨论，对于本发明的实现，恢复需要高达7s。
系统在长期的测量中的统计时间和频率稳定性被分析。
图5示出了在按顺序测量的全部节点对之间的TDEV。这些节点对的颜色与图3中的那些节点对的颜色相匹配。TDEV曲线图在已同步的系统的节点对之间被测量。可以看出，系统的噪声大多表现得像高达近似10s的τ的相位白噪声。
该结果显著超出了范围在10s以下的预期。虽然算法固有地抑制了异常值的影响，因为它丢掉在每个循环中的最大的和最小的测量值并随后在剩余的两者之间求平均值，但是这仅意味着相对于自由运行的振荡器(～1·10-9s@1s的TDEV)3至5倍的改进。相比之下，对于正确工作的节点，在10-12s内的组件的不确定度已经达到了1s以上。这些是相当惊人的稳定值，尤其是考虑到采用价格合理的硬件所产生的粗糙设置。
由于时钟同步系统的主要应用是用作电路的时钟源，因而绝对的频率波动同样针对斯坦福研究系统(Stanford Research)FS275的铷频标来分析。
图6示出了在节点与铷频标之间的ADEV，即，算法被停用以便测量振荡器的原始性能。顶部(蓝色)曲线与自由运行的振荡器进行比较，算法被禁用。底部(红色)曲线是算法被启用的且系统已完全同步的同一节点。在τ＞10s时的长期稳定性近似相同。这是所预期的，因为长期行为受所使用的振荡器的温度引起的频率波动支配。但是，在1s的τ以下，已同步系统的稳定性高于自由运行的节点的稳定性，因为振荡器的噪声通过节点的同步来求平均。令人惊讶的是，稳定性在短期范围内就几乎增益(gain)了一个数量级，再次显著超出预期。在超过τ＝100s时，温度影响是不同的，因为踪迹(trace)是在天气条件不同并因而建筑物的加热模式不同的连续日子里记录的。
因为每个节点使用时间-数字转换器(TDC)来测量在它自己的脉冲与所有其它节点的脉冲之间的时间差，所以在测量中的亚稳态是不可避免的。传统的方法将TDC的输出保持于同步器内，从而耗费了时间并从而对操作频率施加限制。但是，根据本发明，可以将每次测量的亚稳态限定于“在x与x+1时钟节拍之间的不确定度”。
图7示出了Lundelius Welch和Lynch的容错式时钟同步算法能够如何通过分离在电路的模拟和数字部分之间的关系在确定性的正确性保证下实现，尽管不可避免地存在亚稳态紊乱：传入的模拟时钟脉冲的到达时间使用TDC而被测量，含亚稳态的部件确保电路的数字部分在没有精度损失或者没有影响整个控制逻辑的危害的情况下处理转换的部分亚稳态成果(outcome)，并且数字的、仍然部分亚稳态的信号被转换成控制振荡器的模拟信号。
更具体地，每个时钟同步节点执行以下步骤。
步骤1：模拟-数字。在远程脉冲与本地脉冲之间的延迟用TDC来测量。该测量能够被实现，使得导致x和x+1节拍之间的差异的输出位中的至多一个变为亚稳态。
TDC能够使用分接(tap)式延迟线或Vernier延迟线TDC来实现，见图8：一行延迟元件被分接到每个两个连续的元件之间，从而驱动初始化为0的最初启动的锁存器的数据输入端口。然后被馈送入延迟线输入内的远程时钟信号的上升转变通过该线路，并随后将锁存器设置为1；本地时钟信号的上升转变被用来立刻禁用所有锁存器。之后，延迟线的锁存器含有作为一元温度计码(TC)的时间差。选择锁存器之间的传播延迟使其大于它们的设置/保持时间，确保至多一个位是亚稳态的，即，它们的状态为1＊0或1＊M0的形式。因此，该输出是精度-1的TC编码的时间差。
传统的实现会在TDC输出上使用同步器。这会延迟计算并鼓励稳定化，但不会强制它。但是，时钟同步不能等待。而且，所保证的正确性优于概率性陈述：四个节点(每个节点在1GHz下采样)每秒采集1：2_1010个传入的时钟脉冲；当为亚稳态分辨分配1ns或更小时，同步器无法提供足够小的错误概率。因此，使用含亚稳态的算术而不是同步器是强制性的。
步骤2：编码。时间差被转译成二进制反射格雷码(BRGC)，从而使存储及后续部件效率高得多。该结果是具有精度-1的至多一个亚稳态位的BRGC编码的时间差。
步骤3：排序(sort)网络。排序网络选择第(f+1)个和第(n-f)个最大的远程-本地时钟差(容许f个故障需要丢弃最小的和最大的f个值)。
这需要2-sort构件，该构件用于挑选保留了精度-1的两个精度-1的BRGC编码的输入的最小值和最大值。
步骤4：解码与数字-模拟。BRGC编码的第(f+1)个和第(n-f)个最大的远程-本地时钟差被转译回到TC编码的数字。这能够通过保留精度-1来完成，即，使得结果为1＊0或1＊M0＊的形式。
最后，两个值被用来经由数字控制式振荡器(DCO)来控制本地时钟频率。但是，DCO设计必须谨慎选择。在不同长度的逆变器链之间进行切换以修改环形振荡器的频率的设计无法被使用，因为亚稳态开关可能会正好在脉冲通过时出现。反而，其频率受诸如逆变器负载或偏置电流的改变之类的模拟效应控制的环形振荡器是优选的。虽然至多两个亚稳态控制位可以动态地改变两个逆变器的负载，但是这对总体频率改变的影响有限并且不会在环形振荡器内导致毛刺干扰。
这通过所有数字计算给出单个位的保证的端到端不确定度。
适当的编码对于设计含亚稳态的算术部件是关键的。例如，如果指示是否使x＝7增加1的控制位u是亚稳态的，并且x以二进制进行编码，则结果一定是00111和01000的亚稳态的叠加，即，作为Res(0MMMM)的任意值并因此是任意数字x∈[16]的编码——即使在分辨了亚稳态之后。在7和8之间的原始不确定度被大大地放大；好的编码应当含有由u＝M施加的不确定度。
正式地，代码是内射函数γ：[n]→Bk，Bk将自然数x∈[n]映射到其编码表示。对于y＝γ(x)，我们定义γ-1(y)：＝x，并且对于集合X，γ(X)：＝{γ(x)|x∈X}且γ-1(X)：＝{x|γ(x)∈X}。在这项工作中，我们考虑了用于输入和输出的两种编码：TC和BRGC。对于4位(一元)TC，使用un：[5]→B4，un(1)＝0001且un-1(0111)＝3；un-1(0101)不存在。与图10(a)相比，BRGC由rg(x)表示，并且高效得多，仅使用
一元格雷码和反射格雷码编码un和rg由于以下性质而被选择：在两种编码中，对于x∈[k-1]，γ(x)和γ(x+1)仅在单个位上不同。这使得它们适用于含亚稳态的操作。我们重新审视上述具有指示是否使x＝7增加1的亚稳态控制位u的示例。在BRGC中，7被编码为00100，并且8被编码为01100，所以它们的亚稳态的叠加分辨为Res(0M100)，即，仅为7或8。由于原始的不确定性为是否使x＝7增加1，因而不确定性完美地被包含，而不是如上所述那样被放大。我们以部分亚稳态码字对不确定性的量的概念进行形式化：
即，如果在x的分辨之间的最大可能差异以p为界。如果某个y∈Res(x)不是码字，则x关于γ的精度未定义，这不是本申请中的情形。
在下文中给出的算术部件大量使用BRGC。这使得它们更多地参与其中，但是在存储器方面，它们的效率是其TC对手的指数倍(exponentially more)，并且避免了由标准二进制编码引起的不确定性的放大。
图9示出了精度-1的TC编码的数据如何能够被高效地转译成精度-1的BRGC编码的数据。图9(b)描绘了将7位TC转译成3位BRGC的电路；注意，对于为2的扇入，门计数和深度是最佳的。电路能够容易地推广到n位输入，具有
时间-数字转换器(TCD)将在启动信号转变与停止信号转变之间的“模拟”时间差转换成能够用于进一步计算的数字值。
根据本发明，两个TDC设计被提出：(i)第一个是使用二进制计数器等标准部件构建的，以及(ii)允许测量值的空间最佳存储的变体：存储的B位足以对单个TDC级的延迟的2B倍的最大范围进行编码。如果若干测量值必须要存储，同时等待亚稳态的分辨，则这是特别有趣的。
图10在左侧示出了分接式延迟线TDC体系架构。锁存器被初始化为0。所提出的包含亚稳态的TDC的体系架构示于右侧。锁存器和二进制计数器被初始化为0。保持b的寄存器经由延时缓冲器来驱动C0和C1的递增输入。计数器C0在上升转变时递增，C1在下降转变时递增。
为了演示起见，在整个这部分中，根据分接式延迟线方法，我们假定停止信号同时到达所有相关部件。实际上，可以选择其它选项，并且稍后对它们进行补偿或者遵循Vernier线方法，为停止信号选择不同的延迟。在其余部分内，使用简称[n]＝{0，...，n-1}。
计数模数R。在延迟线TDC中，能够通过检查从值为1的二进制寄存器到值为0的二进制寄存器的转变来读取在停止信号到达之前已经由启动信号传递的级的数量cnt(thenumber cnt of stages)。自然地，这假设了所有寄存器均被初始化为0并且在启动信号到达时被设置为1。停止信号在此被简单地用来解除寄存器。一种自然的实现是使用锁存器，该锁存器的数据输入由延迟线元件驱动并且其负启用(negative enable)由传播停止信号的平衡树驱动。
当然，也能够通过使寄存器初始化为1并在启动信号到达时将它们设置为0来实现这点。注意，一旦信号通过整个延迟线(停止信号没有首先到达)，结果就是所有寄存器被正确地“初始化”以用于其它操作模式。因此，如果用1位计数器来代替寄存器并且使输入信号从延迟线的末端回送至其起始处，则具有R个寄存器的“线路”能够被用来对通过模数R传递的级的总数量进行计数。该“线路”因而变为具有R个级的可启动环形振荡器，每个级实际上是1位计数器。
这对以下问题进行了抽象：在任何实际的实现中，计数器无法在零时间内(inzero time)从0切换至1或者反过来。因此，在停止信号到达的时刻读取或停止它们可能导致亚稳态。这是不可避免的，不管实现如何。
但是，为了这种特定的应用，本发明提出了一种解决方案。将每个级的延迟减少到多于一个计数器(或从其中读取的值)可能由于停止信号而变为亚稳态的地步并没有好处，因为所产生的TDC的精度不会增加——只是它的尺寸变得较大而已，因为需要更多的级来覆盖R个级的相同时间窗。因此，能够安全地要求，在其期间计数器易受亚稳态影响的时间窗是不重叠的。在这种情况下，所需要的只是等待，直到至多一个亚稳态计数器(或寄存器)稳定。
在其期间停止信号的到达(相应地，计数器被复制)可能会使计数器(相应地，复本)变为亚稳态的时间间隔(漏洞时间窗)之外，计数器(相应地，它驱动的寄存器)具有稳定的输出值。
在这种情况下，计数器的值之后是稳定于0还是稳定于1是无关紧要的，因为能够简单地将这种情况解释为计数器尚未计数完成或者尚未完成操作，这取决于所产生的值。
即使亚稳态出现，它也并不意味着精度损失。对能够实现的量化误差的限定通过用来存储计数器值的元件所需要的设置/保持时间来给出。
对环形振荡器周期的数量进行计数。假定cnt mod R能够被确定，为了对cnt保持跟踪而需要完成的一切就是对环形振荡器在启动信号和停止信号之间完成的完整周期的数量cyc进行计数。
相反，需要实现计数器，使得当它从由不完整的向上计数引起的亚稳态恢复时，这意味着它“追溯(retroactively)决定”向上计数是否持续地发生。这能够按照不同的方式来完成。
在根据本发明的TDC的第一实施例中，可以使用两个冗余的二进制计数器C0和C1，它们共享相同的最低有效位b；为了进行标记，C0和C1标示没有最低有效位的计数器。在此，b还用作控制位，决定要被读取以确定测量值的计数器Cb。注意，b简单地由附接到环形振荡器的最后一级的1位计数器的值给出，即，b＝c(R-1)。当停止信号到达时，要么所有计数器(1位和二进制)被暂停，要么它们的值被复制并被存储。所产生的电路在图2中描绘。该电路的基本思路是使用存储于C0内的值(若b＝0)或者存储于C1内的值(若b＝1)，确保在c(R-1)＝b成立时，Cb不是亚稳态的。因而，只要最后的1位计数器具有值b，C1-b的值就是不相关的，并且它有时间在不相关的同时来递增并稳定化。
为了确保Cb没有变成亚稳态，考虑到b本身可能会变为亚稳态，1位计数器的漏洞窗口的概念可以以直接的方式被推广到二进制计数器C0和C1。然后进行如下：
●初始化b：＝0，C0：＝0，且C1：＝0。
●保持b和C0(相应地，C1)的计数器的漏洞窗口是不相交的：这可以通过以下方式来实现：在完整的振荡器周期结束时使最后的1位计数器递增(模2)至b，并且此后延迟Tbuf(即，在最后的1位计数器的输出与二进制计数器的递增输入之间的缓冲器的延迟)使计数器C1-b递增；参见图10。以Td来表示在环内的延迟元件的传播延迟。在二进制计数器于(R-1)Td-Tbuf的时间内完成递增的延迟约束下，C1-b在最后的1位计数器刚递增(模2)到1-b时就已经稳定。
●当读取计数器时，cyc被计算为2Cb+b。由于2Cb+b等于组合的二进制计数器(Cb；b)的值，因而可以将位b视为分别在b＝0和b＝1的情况下保持值cyc的组合的二进制计数器(C0；0)和(C1；1)的共享位。这为TDC直接返回cyc的二进制编码提供了一种有效的方法。
完整的TDC通过将以上所述的对模数R进行计数的方法与确定cyc的方法进行组合来给出。因而，该实现需要满足的约束如下。
●延迟元件的延时Td大到足以确保所有1位计数器的亚稳态的漏洞窗口相互不相交。
●在b与两个计数器C0和C1之间的缓冲器具有延迟Tbuf，该延迟Tbuf大于停止信号分别在b和C0处以及在b和C1处的不完全同步到达的时间差异。
●计数器C0和C1足够快以在同一个1位计数器的两次连续递增之间(即在(R-1)Td-Tbuf的时间内)执行向上计数。
在所提出的解决方案中，关键点是TDC允许通过为每个到达信号拍摄计数器的“快照”而将启动信号与多个“停止”信号进行比较。缺点是，TDC的所描述版本导致在为了测量而存储的位数方面的开销：如果二进制计数器具有B个位，则存储2B+R个位，但是最大的cnt值是2BR-1，在理论上只需要
在前面的部分中，对TDC进行了介绍，并且表明它能够被可靠地读取，甚至不必实际停止它：在停止信号到达时复制全部1位计数器和二进制计数器就足够了，无需暂停振荡器环。虽然仅使用像二进制计数器之类的标准部件，但是它用比理论下界所需的位更多的位来存储值。
图11是根据本发明的实施例的基于Xilinx Virtex-4芯片而实现的分接式延迟线TDC的FPGA原型的示意性概览图。
该原型使用长度为8的环，并且其1位计数器c(0)，...c(7)通过简单的D锁存器来实现，可用作在目标平台上的硬件原语。在它们的数据输入之间的所需延迟元件使用查找表(LUT)来建立：每个级必须选择8个LUT(布局后时序分析给出了4-5ns的总延迟)，以确保传播延迟大到足以用我们的逻辑分析仪(最小采样周期为4ns)来测量。二进制计数器C0和C1各自包含7个D触发器。锁存器和计数器输出被路由至FPGA输出引脚。逻辑分析仪然后被用来记录电路操作。如前所述，在b位计数器(锁存器c(7))与二进制计数器之间的延迟对于安全操作至关重要：另外的LUT确保需要的最小延迟，而位置和路线约束控制其最大延迟。
START(启动)和STOP(停止)两者从两个独立的时钟源导出，并且随后由计数器分开。界定STOP的偏斜是关键的：它必须小于在b位计数器与二进制计数器之间的延迟，以确保正确的操作。而且，所有1位计数器必须在接近的时间近似内停止，以达到良好的精度。因此，使用最大偏斜约束来控制该信号的偏斜。在最坏的情况下达到790ps的偏斜。
原型TDC在单发模式下操作：在每次测量之后，TDC被复位(res_n信号)。复位操作的时序基于START信号。逻辑分析仪在START的上升沿被触发，该上升沿指示复位周期的结束以及新测量的开始。
图12示出了根据可替代实施例的具有前瞻式格雷码计数器和寄存器的实现。计数器C以1来初始化。寄存器Rc具有与计数器相同的宽度，并且以0来初始化。
根据该可替代实施例，可以使用以格雷码来操作的计数器，在以下意义上，该计数器还需要容许在其递增端口处的潜在亚稳态：如果递增位是亚稳态的，则计数器必须保证(i)只有单个位可能会变成亚稳态，并且(ii)在给出其它位的(不变)值的情况下，亚稳态位是当前的最低有效位。
该电路能够被用来按照只需存储最佳的
对cnt modR进行编码。作为起始点，我们知道，如果在给定所有其它输入的情况下，输出值取决于可能是亚稳态的输入位，则没有电路能够(确定性地)避免输出位的亚稳态。因此，第一个重要洞见是必须使用以下这样的编码：该编码保证1位计数器中的一个的亚稳态(即，关于另外的级是否已经由停止信号的到达触发的不确定性)一定不会导致多于一个输出位的亚稳态：否则，对于没有冗余的任何编码，我们一定会损失测量的精度，因为分辨为任意值的两个或更多个位一定会引起大于1的编码值的改变。换言之，我们必须使用格雷码，对于格雷码，任何向上计数正好改变1个位。
对于两个不同的输出位o和o’，通过格雷码的定义有
作为这种方法的另一个优点，上述格雷码和电路能够被用来对在R位字符串0＊1＊中的0的数量进行编码：在一元编码1m0n和0m1n之间的切换等同于对输入取补码。通过XOR(异或)树将逆变器从所有输入传播到输出可得出：要获得互补的(complemented)一元输入编码的格雷码，对输出位的固定子集取反(negate)就足够了。
像以前一样，需要确保一元-格雷码电路的输出位的任何快照(由停止信号的到达或锁存引起的)具有以下性质：(i)位中的至多一位当前正在进行转变，并且(ii)这个位是当前的最低有效位。也就是说，输出位(存储输出位的锁存器)的漏洞窗口是不重叠的。如果这样，则能够简单地通过读取上述电路的输出位而从TDC中读取cnt modR。
将编码电路引入影响测量的额外延迟考虑进来是至关重要的。这反映在以下事实中：现在存储自启动信号起已通过的逆变器级的数量，该数量在停止信号到达时已经由编码电路的输出位寄存。因而，关键的是确保编码电路的已知的且统一的延迟，该延迟然后由施加于启动信号的相等(逻辑或物理)延迟来补偿。
为此，能够利用等频格雷码，这确保(i)所有输出位以相同(摊销)频率翻转，并且(ii)在输出位的两次连续翻转之间的最小递增数量较大。这些性质具有以下几个优点：
●用于所有输出位的XOR树的深度是相同的，因为它们取决于相同数量的输入位。
●负载和功耗在编码电路中是对称分布的。
●在异或门的两次连续信号转变之间的最小时间大于其它代码的最小时间。因为每当1位计数器递增(模2)时，一元-格雷码电路就需要改变输出，所以在TDC的低量化误差所需的短延迟元件延时Td存在时这是有用的。
对cyc进行编码并且安全地使用控制位b。附接到环形振荡器的最后一级的1位计数器的值b决定着由编码电路计算出的格雷码值的解释以及其值要被读取的计数器Cb二者。虽然格雷码的便利结构将允许通过推迟b的评估直到它稳定下来之后来绕过这个问题(不浪费存储器)，但是我们仍然必须存储两个二进制计数器的值。
这也不是必需的。可以用具有前瞻性的单个格雷码计数器来代替这两个计数器：考虑图10中的电路。C0和C1两者以及延迟缓冲器可以用通过最后的1位计数器进行递增的格雷计数器来代替。当计数器被触发时，需要：(i)它在单个振荡器周期内完成向上计数，并且(ii)它的输出是稳定的(尽管它在内部递增)，除了在递增(并从而前瞻项)被触发之后的短时间窗内。注意，这样的计数器能够通过仅满足(1)且其输出在递增时被锁定的格雷计数器来实现。
为了读取cnt mod R，可以忽略最后的1位计数器的值(该1位计数器最初保持着b)，这等同于为此目的而推迟最后一位的评估。因而，在计数器变为亚稳态的情况下，则有效地等待，直到亚稳态已经停止(这在值位于储存器内时发生)。然后，根据已稳定的计数器值来确定cyc是奇数还是偶数，即，获悉b。根据b，能够推断出如何正确地解释为cnt mod R存储的值，从而允许计算cnt。
因而，需要为了测量而存储的位的数量为
所提出的TDC能够在与单发启停转变不同的模式下操作。
两个远程信号的时间差。在这种操作模式中，本地时钟源限定时间窗[tmin；tmax]，在该时间窗期间两个相比较的信号转变必须到达；(一个或多个)TDC计数器必须足够大，使得它们在这个时间跨度内不会溢出。TDC在时刻tmin被装备。可以使用两个远程信号的或值(OR)作为启动信号，并且它们的与值(AND)作为停止信号。在tmax，可以读取保持结果的寄存器，因为我们假定这两个信号都在[tmin；tmax]期间到达。
两个信号转变到达的时间由t1；t2∈[tmin；tmax]表示。可观察到，上述过程测量|t1-t2|。因而，仍然要确定哪个信号首先到达。为此，我们使用例如第二信号的侧翼(flank)以将第一信号的当前状态采样到寄存器内。当(且仅当)t2≈t1时，这会导致亚稳态。因而，如果t1-t2是稳定的0或1，则寄存器存储t1-t2的符号，并且如果它是亚稳态的，则两个侧翼几乎同时到达。照常，可以确保符号寄存器的亚稳态排除了其它TDC寄存器为亚稳态的可能性；因而，如果它是亚稳态的，则符号并不重要(可以获得正数或负数)。
这种方法具有高度精确的优点：它避免了引起两次离散化误差，并且振荡器与其标称频率的偏差会导致仅与|t1-t2|成比例的误差。
具有多重采样的专用启动信号。所提出的TDC还允许多重采样。对于这个变体，可以假定已知一个信号侧翼会保证在时刻t0∈[tmintmax]首先到达，而k个其它侧翼在时刻t0≤t1，...，tk∈[tmin，tmax]到达。像之前一样，我们在时刻tmin装备TDC，并且可以在时刻tmax读取结果。但是，我们在时刻t0使用专用启动信号来启动振荡器，并且使用于保存TDC测量结果的寄存器的k个单独的集合附接到计数器，这k个其它信号中的每一个有一个计数器。对于每个i∈{1，...，k}，我们现在简单地使用信号i的侧翼来存储在寄存器的第i集合内的读数。
这些测量的结果能够被用来计算在信号转变中的任意两个(包括在时刻t0到达的启动信号)之间的时间差，其中由振荡器相对于标称频率的偏差引起的误差再次与信号的实际时间差成比例。但是，请注意，除非两个比较信号之一是启动信号，否则TDC的离散化误差会两次进入图片(picture)。
本地启动而不停止振荡器。在一些情况下，启动信号能够与TDC环形振荡器自身进行同步。如果TDC振荡器永不停止，这种情况就会发生，因为它被用作本地逻辑的系统时钟，或者如果它从属于(本地)系统时钟以便提高其精度(即，通过例如温度补偿来降低其相对于标称频率的偏差)，这种情况也会发生。
在这种设置下，能够通过按照与振荡器同步的方式来执行存储寄存器的复位而“在运行中(on the fly)”装备所提出的TDC。在占用了包括计数器在内的所有寄存器的复位信号之后，我们等待，直到振荡器启动新的偶数(even)周期的下一个时间，如t。然后，按照由振荡器级给定的顺序停用寄存器的(包括多位计数器的)复位信号，延迟足够大，使得当这种情况发生时，各个振荡器级(即，1位计数器)已经处于状态(被解释为)0下。注意，这是相当宽松的时序要求，因为我们具有整个振荡器周期，直到寄存器必须准备就绪以再次存储新的值。
然后，TDC被认为在它开始其下一个周期的时刻t0已经接收到启动信号。该周期是奇数周期，并且从而所有计数器处于与作为启动信号的到达时间的t0一致的状态下。
图13示出了具有单位锁存器的格雷码计数器变体。之前的实施例的格雷码计数器变体要求计数器的输出在大小与锁存器的临界窗口相似的时间窗之外的所有时刻是稳定的(受Td限定，参见图7)。对于具有小的Td的高精度TDC，这要么(a)对计数器的设计施加严格的约束(该约束可能是难以满足的)，要么(b)需要以附加的寄存器作为变通方案(workaround)的实现(见图8)。
对于这些情况，本发明提出了示于图13中的一种不同的亚稳态感知设计：添加了仅具有输出b的一个额外的(单个位)锁存器L。异或门使计数器递增输入延迟并且另外将上升和下降转变转换成脉冲，从而允许将标准的单边沿触发的触发器用于格雷码计数器实现。类似于冗余的二进制计数器解决方案，只需要锁存器L和格雷码计数器C的非重叠的临界窗口，如图14所示。
给定(稳定的)TDC读数，再次确定cyc是奇数还是偶数，——这次不是根据计数器值，而是根据明确存储于锁存器L内的b。这允许像之前一样正确地解释为了cnt mod n而存储的值。而且，它被用于解释格雷码计数器的不完整向上计数的原因：如果所存储的计数器值的奇偶性不同于b，则计数器本应当已经递增，但是已经通过停止信号来阻止了这样做。在这种情况下，对所存储的值(针对所使用的格雷码)执行向上计数。这会产生正确的值，因为计数器的亚稳态只会影响在各自的向上计数时正被改变的(唯一的)位。
自然地，b变为亚稳态的情况也可能会发生。但是，在这种情况下，延迟Tdel确保计数器没有启动与L的(不完整)转变对应的递增。因而，b的任一分辨会引起对测量结果的正确解释：如果L变稳定，就好像它没有被触发一样，则一切都很好；如果它变稳定，就好像它已经被触发一样，则相应地固定计数器值。
参照图7，上述含亚稳态的TDC的输出能够被输入排序网络内，这用于计算两个有效字符串的最大值或最小值。从具有亚稳态位的有效字符串可以稳定化成代表某个值x或x+1的二进制字符串的意义上说，所需要的是输入具有精度1。对于输出同样如此。因而，排序网络需要完全包含亚稳态，即，情况“一定不能变得更糟”。
根据排序网络的第一实施例，这可以通过以下步骤来实现：(1)确定每个输入的一元编码，(2)分别逐位地取或(OR)或者与(AND)，并且(3)确定结果的格雷码。
第三步骤是简明的，利用一元编码的每个位只会影响格雷码的单个位。因此，不需要担心包含亚稳态，并且可以使用XOR树(每个输出位一个)，从而引起各自用于maxrg和minrg的少于N个的附加门；深度小于log N。
因此，仍然要设计用于以含亚稳态的方式确定给定的有效B位格雷码字符串的一元编码的电路。
图15示出了根据本发明的实施例的用于确定给定的有效B位格雷码字符串的一元编码的方法的递归实现。为了避免通过“影响”能够正确计算的输出的位来“放大”亚稳态，它不能轻易地在代码的第一位处进行分支：如果控制逻辑变为亚稳态的，则分支可以产生不需要的亚稳态输出，这最终会不可逆地破坏输出。
这个问题可以通过以下操作来避免：考虑两个输入g和h的第一位的所有可能的稳定值(00、01、10和00)，确定各自的成果，并且然后按照安全的方式从这些结果中选择。粗略地说，如果例如h[1]＝M，则h[2：G]＝rgB-1(N/2-1)，并且这能够被用来表明递归调用对于h[1]＝0和h[1]＝1两个分支计算出相同的结果。因此，“所有”需要做的是将结果馈送入复用器内，该复用器将g[1]和h[1]用作控制位并且具有以下性质：如果在亚稳态控制位选择之间的输入是相同的，则尽管如此，输出还是稳定的。
标准复用器电路没有这个性质，所以第一步骤是设计这样的含亚稳态的复用器(CMUX)。
图16示出了根据本发明的实施例的(2：1)-CMUX(即，使用一个控制位在两个输入之间进行选择)的逻辑表和实现电路。与标准复用器的重要区别在于，它在控制位s为亚稳态的情况下输出a*b；如果s是亚稳态的，则标准复用器可以得出亚稳态的输出，即使a和b符合(agree)，即，选择实际上无关紧要。在各自长度为B的输入当中进行选择的CMUX以CMUX(B)表示(因为它只是CMUX的B个副本)。
图17示出了结合图16来描述的原理可以如何被推广到2个控制位，即，在4个输入之间的选择。
2-sort(B)实现
使用两个格雷码输入g和h的第一位作为控制位，可以将合适的输入馈送到CMUX以便递归地确定正确的输出。
图18示出根据本发明的实施例的2-sort(B)的递归实现。g[1]和h[1]分别是g和h的引导(leading)位。g[2：B]和h[2：B]是去除第一位之后剩余的字符串。
表III示出了2-sort(B)的实现的成本和延迟的总结，忽略了指数大小的解决方案的大扇出问题。对于多项式大小的解决方案，减少扇出的影响是小的：每个位具有扇出O(B)，并且在确定延迟的关键路径上不出现大的扇出。因此，就门和晶体管计数而言，该比较有利于指数大小的电路，而在延迟方面，它稍微有利于多项式大小的解决方案。这使得结果易于理解：指数大小的解决方案具有1/3-1/2倍的较小延迟，但是指数大小的解决方案即使是对于中等的B＝8也有小得多的晶体管计数。
现在考虑这两种实现在排序网络的背景下的应用，可以假定排序网络具有n个通道，即，n个字符串被排序。输入是长度为B的有效的格雷码字符串。排序网络的输出是按照由
在本发明的背景下，我们特别感兴趣的是具有n＝3f+1个通道的排序网络(对于某些f∈N)，因为这是在Lynch和Welch所提出的时钟同步中容许f个故障节点所需的节点的最少数量。
表IV示出了具有n∈{4，7，10}个B位输入的含亚稳态的排序网络的门和晶体管计数，对于这些排序网络，最佳的实现分别使用了2-sort(B)电路的5、16和29个模块。
尽管根据第一实施例(蛮力)的实现在晶体管方面成本更高，但是从格雷码到一元编码的转译以及反过来对于每个输入仅需要完成一次。这显著减少了蛮力解决方案的晶体管计数，在表IV中予以了考虑。因而，特别是对于较大的n值，多项式大小的解决方案对于大致高达4的小的B值表现较优(is outperformed)。对于B≥8，渐近性清楚地引入(kick in)，并且对于所有考虑的n值引起巨大的差距。
根据本发明的另一实施例，可以首先按照由两个控制位表示的含亚稳态的方式确定要选择哪个字符串。可能会发生这些位中的一个或两个变为亚稳态的，但是在这种情况下，格雷码的结构意味着输入字符串几乎是相同的，仅通过它们的哪些位为亚稳态来区分。使用CMUX来组合所选的字符串，确保由这两个字符串共享的稳定位在输出中没有变为亚稳态的，尽管控制位可能存在亚稳态。
图19示出了根据本发明的另一实施例的cont(B)的递归实现。
用于计算控制位的子电路执行4值比较：给定稳定的输入g、h，如果<g>＜<h>或<g>＞<h>，则它相应地返回01或10。如果g＝h，则它根据相等字符串的奇偶性而返回00或11。对于具有亚稳态字符串的输入，行为通过考虑输入的所有可能分辨而被最便利地指定，从而确定各自的输出，并且对于原始输入获得作为在*运算符下的所有选项的“叠加”的输出。例如，
●c(0111，0101)＝01，
●c(1001，1001)＝00，
●c(1M10，1111)＝10*10＝10，
●c(010M，0100)＝11*01＝M1，
●c(111M，111M)＝11*10*01*00＝MM。
a)规范：
对于B∈N，(组合)cont(B)电路被定义如下。
●输入：
●输出：c∈{0，1，M}2，
●功能：
其中，对于g’，h’∈{0，1}B
b)实现：
基本情况是微不足道的。
对于B＝1，在上述定义中给出的规范由识别电路满足，该识别电路对于输入g，h∈{0，M，1}返回输出(g，h)。
对于作为2的幂的B，该规范是递归实现的。思路是分别对输入g0、h0和g1、h1递归地使用B/2位电路，并且使用第二次调用的结果来分辨来自第一次调用的平局(tie)。在平局的情况下，保持跟踪奇偶性对于正确使用第二次调用的结果至关重要：如果g0＝h0的奇偶性为奇数，则需要对由第二次调用返回的控制位取反。
图20示出了2-sort(B)的递归实现。为了获得控制输入(c0[1]c0[2])，g0和h0被馈送入cont(B/2)电路内(参见图19)。
同样，基本情况是微不足道的。
对于B＝1，规范由针对输入g，h∈{0，M，1}返回AND(g，h)和OR(g，h)的电路满足。排序电路被实现如下。通过递归调用来确定(maxrg{g，h})0＝maxrg{g0，h0}(与minrg的情形相同)。第二次递归调用确定maxrg{g1，h1}和minrg{g1，h1}。最后，使用对cont(B/2)的调用来计算控制位，该控制位选择字符串g1、h1、maxrg{g1，h1}和minrg{g1，h1}当中的哪一个以将其选为maxrg{g，h}1。
递归构造需要在递归的每个层计算控制位。但是，用于计算控制位的电路在与排序电路相同的子字符串上递归，并且具有稍微较小的延迟。这使得便于将控制电路的递归调用的输出重新用作用于排序电路的递归调用的控制位。利用该洞见，得出高效的2-sort实现。
给定含亚稳态的2-sort实现，现在直接使用标准的技术来对多个输入进行排序。采用任何排序网络，能够插入根据本发明的含亚稳态的2-sort电路，以获得含亚稳态的排序网络。成本、延迟，以及在一阶近似下，排序网络的面积和功率随着2-sort实现的成本和延迟而线性缩放。
假定排序网络具有n个通道，即，为n个字符串。输入是长度为B的有效的格雷码字符串。排序网络的输出是按照由
图21示出了在a＝b＝1的输入下门级MUX的行为；在这种情况下，输出应当为1，不管选择位s是什么。但是，对于s＝M，标准的MUX(a)能够变成亚稳态的。根据本发明的实施例的CMUX实现(b)使用逻辑屏蔽并输出1。
更具体地，示于图21(b)中的CMUX的行为表现如下：
(1)若s＝0，则输出为a，
(2)若s＝1，则输出为b，
(3)若s＝M，但a＝b，则输出为a，并且
(4)若s＝M且a≠b，则输出是未指定的。
条件(3)反映出，即使在a和b之间的选择由于亚稳态的选择位而是不明确的，在a＝b的情况下，这也一定不会影响输出。
省略条件(3)得到标准的MUX，这样的标准MUX会无视亚稳态的(或换句话说)劣化的选择位。
因此，在图21(b)中的门级CMUX实现使用第三与门的形式的逻辑屏蔽来降低亚稳态选择位的影响。
图22示出了根据本发明的实施例的晶体管级CMUX实现。本发明提出了CMUX的两种晶体管级实现，CMUX-A和CMUX-B，分别示于图2(a)和2(b)中。这两个电路实现条件(1)-(4)并反转输出。区别在于，虽然CMUXA是需要10个晶体管的保守实现，而CMUX-B只需要8个晶体管，但是在条件(3)下，即如果s＝M且a＝b，CMUX-B具有稍高的峰值电流。
CMUX-A示于图22(a)中。简单的检查确定，如果所有输入s、a、b为逻辑0或1，即满足条件(1)和(2)，则它(直到(up to)输出信号的反转)表现得如同所期望的那样。
条件(3)同样得到满足，因为具有未限定的输入电压的晶体管产生了未限定的输出电压。对于所提出的实现，这意味着，如果在0和1之间的未限定电压M被施加于晶体管栅极，则晶体管会充当电阻未限定的电阻器。
所以，如果s＝M且a＝b＝0，则在CMUX-A的右上角存在从VCC到
总之，CMUX-A满足条件(1)-(4)。此外，由本发明的发明人执行的SPICE模拟证实了CMUX-A的正确行为。
CMUX-B同样满足条件(1)和(2)：如果所有输入s、a、b为逻辑0或1，则如果s＝0，那么CMUX-B输出
关于条件(3)，考虑s＝M且a＝b的情形。然后，具有栅极输入s或
如果a＝b＝1，则存在从GND到
总而言之，CMUX-B满足条件(1)-(4)，但是在条件(3)下具有比CMUX-A高的峰值电流。由本发明的发明人进行的SPICE模拟证实了CMUX-B的正确行为和峰值电流。
图23示出了根据本发明的实施例的由三个2-CMUX组装的4-CMUX。
它使用两个选择位来选择四个输入之一，这是条件(1)-(4)的推广。它的行为表现如下：
其中如果x≠y，则x＊y是未指定的输出电压，但是如果x＝y[4]，则x＊y＝x。
这种两级方法两次对输出取反，并因此直接产生所期望的输入。连同用于反转两个选择位的四个晶体管一起，它需要3·8+4＝28个晶体管，以根据CMUX-B来实现4-CMUX(当采用CMUX-A作为基础时，需要3·10+4＝34个)。
图24示出了在使用CMUX-B而不是图23的4-CMUX时所节省的晶体管数量。
当对2位数字进行排序时，使用CMUX-B会节省55.6％的晶体管。由于电路复杂度对B的二次方相关性，因而在增加B时，节省变得更加剧烈：当对16位数字进行排序时，使用CMUX-B节省83.9％的晶体管。
