Theory of one-tape linear-time Turing machines

A theory of one-tape two-way one-head off-line linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines’ resources affect their computational patterns and power.     

Adaptive broadcast by fault-tolerant spanning tree switching

Adaptation is a desirable requirement in a distributed system as it helps the system to perform efficiently under different environments. For many problems, more than one protocol exists, such that one protocol performs better in one environment while the other performs better in another. In such cases, adaptive distributed systems can be designed by dynamically switching between the protocols as the environment changes. Distributed protocol switching is also important for performance enhancement, or fault-tolerance of a distributed system. In this work, we illustrate distributed protocol switching by providing a distributed algorithm for adaptive broadcast that dynamically switches from a BFS tree to a DFS tree. The proposed switching algorithm can also handle arbitrary crash failures. It ensures that switching eventually terminates in spite of failures and the desired tree (DFS tree) results as the output. We also investigate the properties that can be guaranteed on the delivery of broadcast messages under specific failure conditions. We show that under no failure, each broadcast message is eventually correctly delivered to all the nodes in spite of switching. Under arbitrary crash fault, we ensure that switching eventually terminates with the desired tree as the broadcast topology. We also investigate the specific delivery guarantees that can be provided when a single crash fault happens, both during switching and when no switching is in progress.     

Ultra‐fast‐switching flexoelectric liquid‐crystal display with high contrast

Abstract— The flexoelectro‐optic effect provides a fast‐switching mechanism (0.01–0.1 msec), suitable for use in field‐sequential‐color full‐motion‐video displays. An in‐plane electric field is applied to a short‐pitch chiral nematic liquid crystal aligned in the uniform standing helix (or Grandjean) texture. The switching mechanism is experimentally demonstrated in a single‐pixel test cell, and the display performance is investigated as a function of device parameters. A contrast ratio of 2000:1 is predicted.     

Highly efficient switched‐mode transmitter using a current mode class‐D RF amplifier

This article presents a switched‐mode transmitter architecture using a current mode class‐D (CMCD) amplifier. To achieve high average efficiency for a modulated signal the envelope of the complex baseband signal is transformed into pulses such that the CMCD amplifier is operated either at its peak efficiency or completely switched off. The CMCD amplifier has been designed based on single‐tone active harmonic load‐pull measurements to achieve a power‐added efficiency (PAE) of 61.5% with 25 W output power at 900 MHz using LDMOS FETs. Removing the losses of the demodulation filter and of the amplifier a 10% higher efficiency than in an ideal class‐B amplifier can be obtained for burst‐mode operation with a peak‐to‐average power ratio of 10 dB. © 2010 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2010.     

可靠实现煤矿双机热备系统的方法

在分析商用双机热备系统在煤矿应用的局限性基础上,提出了一种适用于中小煤矿的双机热备系统纯软件实现方法。该方法采用单/双工混合运行模式保证双机实时性能和数据一致性,采用心跳线连接和对等网络消息传递机制实现运行故障监测与传递功能,采用数据自动同步技术减少人工干预和提高系统可维护性,并采用虚拟IP地址技术实现应用层透明访问和无缝切换功能。实验与应用案例证明该方法符合相关行业安全标准并具备现实可行性。     

非抽样Contourlet变换的盲数字水印

根据非抽样Contourlet变换的特性,提出一种非抽样Contourlet变换域的盲水印算法,算法选择在具有最大能量的中高频子带中嵌入水印,在对水印进行加密后,利用密钥生成PN序列,根据水印值的不同PN序列嵌入宿主图像的方式也不同。提取水印不需要原始图像,利用NSCT变换系数与PN序列的相关性系数提取水印,实现盲提取。实验证明算法具有一定的不可见性和鲁棒性,具有很强的抗JPEG压缩的鲁棒性。     

网络心跳包序列的数据流分簇检测方法

在对网络会话进行时序分析的基础上,提出基于数据流分簇处理的心跳包序列检测方法。对数据流进行时序分簇处理,按周期性特征扩充簇集合,筛除不符合特征的簇对象,根据稳定的簇集合检测心跳包序列。实验结果表明,该方法检测率较高、误检率较低,能够实现实时检测和处理。     

Static timing analysis for modeling QoS in networks-on-chip

Networks-on-chip (NoCs) are used in a growing number of SoCs and multi-core processors. Because messages compete for the NoC’s shared resources, quality of service and resource allocation are major concerns for system designers. In particular, a model for the properties of packet delivery through the network is desirable. We present a methodology for packet-level static timing analysis in NoCs. Our methodology quickly and accurately gauges the performance parameters of a virtual-channel wormhole NoC without simulation. The network model can handle any topology, link capacities, and buffer sizes. It provides per-flow delay analysis that is orders-of-magnitude faster than simulation while being significantly more accurate than prior static modeling techniques. Using a carefully derived and reduced Markov chain, the model can statically represent the dynamic network state. Usage of the model in a placement optimization problem is shown as an example application.     

Modelling concurrency with comtraces and generalized comtraces

Comtraces (combined traces) are extensions of Mazurkiewicz traces that can model the “not later than” relationship. In this paper, we first introduce the novel notion of generalized comtraces, extensions of comtraces that can additionally model the “non-simultaneously” relationship. Then we study some basic algebraic properties and canonical representations of comtraces and generalized comtraces. Finally we analyze the relationship between generalized comtraces and generalized stratified order structures. The major technical contribution of this paper is a proof showing that generalized comtraces can be represented by generalized stratified order structures.     

Almost sure limit theorems for the maxima of some strongly dependent Gaussian sequences

We proved some almost sure limit theorems for standard strongly dependent Gaussian sequences in nonstationary cases under some mild conditions.