Limiting negations in non-deterministic circuits

The minimum number of NOT gates in a Boolean circuit computing a Boolean function f is called the inversion complexity of f. In 1958, Markov determined the inversion complexity of every Boolean function and, in particular, proved that log₂(n+1) NOT gates are sufficient to compute any Boolean function on n variables. In this paper, we consider circuits computing non-deterministically and determine the inversion complexity of every Boolean function. In particular, we prove that one NOT gate is sufficient to compute any Boolean function in non-deterministic circuits if we can use an arbitrary number of guess inputs.     

Limiting negations in bounded-depth circuits: An extension of Markov's theorem

A theorem of Markov shows the necessary and sufficient number of negations for computing an arbitrary collection of Boolean functions. In this paper, we consider a class of bounded-depth circuits, in which each gate computes an arbitrary monotone Boolean function or its negation. We show tight bounds on the number of negations for computing an arbitrary collection of Boolean functions when such a class of circuits is under consideration.     

A lower bound method for quantum circuits

Quantum circuits, which are shallow, limited in the number of gates and additional workspace qubits, are popular for quantum computation because they form the simplest possible model similar to the classical model of a network of Boolean gates and capable of performing non-trivial computation. We give a new lower bound technique for such circuits and use it to give another proof that deterministic computation of the parity function cannot be performed by such circuits.     

Circuit Complexity of Regular Languages

We survey the current state of knowledge on the circuit complexity of regular languages and we prove that regular languages that are in AC⁰ and ACC⁰ are all computable by almost linear size circuits, extending the result of Chandra et al. (J. Comput. Syst. Sci. 30:222–234, 1985). As a consequence we obtain that in order to separate ACC⁰ from NC¹ it suffices to prove for some ε>0 an Ω(n ^1+ε ) lower bound on the size of ACC⁰ circuits computing certain NC¹-complete functions. Partially supported by grant GA ČR 201/07/P276, project No. 1M0021620808 of MŠMT ČR and Institutional Research Plan No. AV0Z10190503.     

分组密码算法SM4的低复杂度实现

针对分组密码算法SM4中加解密算法与密钥扩展算法的相似性,提出一种将加解密模块与密钥扩展模块复用的基本架构,通过对具体实现结构的分析与选择,使控制逻辑复杂度、复用模块复杂度以及系统吞吐量之间得到权衡.基于该架构设计SM4加解密IP核,在现场可编程门阵列上占用的资源仅为传统设计的55％,基于SMIC 0.18 μm数字CMOS工艺的综合结果显示,仅用0.079 mm2即可实现1 00 Mb/s的数据吞吐量.实验结果表明,该结构可以有效地降低SM4算法的实现复杂度.     

奇偶校验问题的二进神经网络学习算法

二进神经网络可以完备表达任意布尔函数,但对于孤立节点较多的奇偶校验问题却难以用简洁的网络结构实现。针对该问题,提出了一种实现奇偶校验等孤立节点较多的一类布尔函数的二进神经网络学习算法。该算法首先借助蚁群算法优化选择真节点及伪节点的访问顺序;其次结合几何学习算法,根据优化的节点访问顺序给出扩张分类超平面的步骤,从而减少隐层神经元的数目,同时给出了隐层神经元及输出元的表达形式;最后通过典型实例验证了该算法的有效性。     

Malign Distributions for Average Case Circuit Complexity

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−log log nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i.e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.     

Complexity of constructing Dixon resultant matrix

Dixon resultant is a fundamental tool of elimination theory in the study and practice of algebraic geometry. It has provided the efficient and practical solutions to some benchmark problems in a variety of application domains, such as automated reasoning, automatic control, and solid modelling. The major task of solutions is to construct the Dixon resultant matrix, the entries of which are more complicated than the entries of other resultant matrices. An existing extended recurrence formula can construct the Dixon resultant matrix fast. In this paper, we present a detailed analysis of the computational complexity of the recurrence formula for the general multivariate setting. Parallel computation can be applied to speed up the recursive procedure. Furthermore, we also generalize the computational complexity of three bivariate polynomials to the general multivariate case by using the construction of standard Dixon resultant matrix. Some experimental results are demonstrated by a range of nontrivial examples.     

A lower bound on the mod 6 degree of the OR function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z _m . In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}ⁿ, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n ^{1/ r} ) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power. received 29 September 1994     

多电平变换器拓扑结构的发展与现状

本文介绍了多电平变换器拓扑结构的发展和现状,以及实现多电平变换器的基本电路,包括二极管箝位型、飞跨电容型、级联型、通用型、直流源级联型、变压器级联型等,列出了它们的基本电路拓扑图,同时对拓扑图进行了简单的分析,总结了各种拓扑结构的特点。最后,对多电平变换器的发展方向提出了看法。     

基于像素点灰度值奇偶性的数字图像水印方案

为了验证图像的真实性和完整性,提出了一种基于像素点灰度值奇偶性的脆弱水印技术。选取一些像素点,通过判断并调整这些像素点的灰度值奇偶性达到嵌入水印图像位信息的目的。根据提取的水印图像可以验证被检测图像是否真实以及被非法窜改的位置。实验结果表明,该技术在保持较高图像质量的前提下,具有安全性好、 对窜改敏感以及能够准确确定窜改位置等优点。     

基于STM32F103RCT6无线充电电路的设计与研究

摘要：随着手机的普及、电动汽车和无线电技术的不断发展,电子产品也越来越丰富。对各种电池的充电速度和工作时间提出越来越高的要求。由于目前电池的电量工作时间较短、快速充电、远距离充电等问题不能解决,从而给人们的生活带来了极大的不便,特别限制了电动汽车工业的发展。所以针对电池的充电问题,本文设计了一款电磁谐振式无线充电器。该充电器采用STM32超低功耗单片机作为无线充电电路的主控制器,通过对发射信号频率的控制,使处于异地的输出电路工作在谐振状态,实现最大功率无线传送,接收端线圈输出再经过整流、稳压、滤波后输出+5V电压,最终经过智能控制电路给便携式设备中的锂电池充电。并通过指示灯显示电池是否正在充电、充满、电池反接和电源欠压等状态。该设计的充电设备具有使用灵活、方便、工作可靠,电能利用率高,无线充电距离远等特点,同时具有过压、过流保护,具有广泛的应用价值。     

基于RS-485的PLC与多台变频器通信的实现及应用

介绍了采用S7-200系列PLC和富士G11/P11系列变频器组成的控制系统,该系统在四色印刷机水辊交流变频调速中得到成功应用。文中说明系统的硬件组成和工作原理,详细介绍了控制系统中串行通信的程序编制方法。     

图像复杂度研究综述

图像相关复杂度的研究领域很广泛,除了计算机科学领域,还延伸到医学、认知心理学等研究领域。在以上应用领域,与图像相关的复杂度的定义有很多,包括图像复杂度、视觉复杂度、场景复杂度,其中图像复杂度又可以进一步细分为颜色复杂度、纹理复杂度和形状复杂度。文中对以上这些复杂度的应用、定义和计算方法进行了归纳总结,并依据组成论中相关复杂度的定义,提出了一种研究图像复杂度的思路,即从图像组成元素的角度来研究图像复杂度。这种图像复杂度的定义只与图像本身所包含的元素、内容有关系,与图像处理任务和算法无关。同时,这种图像复杂度的定义符合一般意义下人对图像复杂性的感受和理解。图像元素可以分为颜色、形状、纹理三大类,它们又可以进一步用一些特征来表示。根据组成论,文中给出了定义这3种特征的广义集的方法。后续研究将进一步给出图像复杂度的计算算法,并通过与人工实验的相关性分析来验证计算结果是否与人的感受相一致。     

耦合电抗器在相移并联逆变器中的设计与应用

本文首先分析了基于相移SPWM技术的并联逆变器的环流特性,提出了耦台均流电抗器的设计方法。最后,采用DSP构建数字控制系统,并在两台5KVA的电压型逆变器上进行了并联实验,实验结果验证了其正确性和有效性。     

Complexity Questionnaires of Visual Displays: A Validation Study of Two Information Complexity Questionnaires of Visual Displays

With the prevalent use of visual interfaces and the increasing demand to display more information, information complexity in human–computer interfaces becomes a major concern for designers. Complex interfaces may adversely affect the effectiveness, efficiency, and even the operational safety of a system. Previously, two questionnaires were developed by researchers at the Federal Aviation Administration to evaluate information complexity of air traffic control displays. This study adapted the questionnaires for commercial visual interfaces and validated them with two types of tasks on three travel websites. The questionnaire measures the information complexity of a visual display based on perceptual, cognitive, and action complexity in terms of three complexity factors: quantity, variety, and relation. The result demonstrates that the questionnaire that uses multiple items for measuring complexity construct has good reliability, validity, and sensitivity. Information complexity is also found to be negatively correlated with usability and positively correlated with mental workload. The contribution of the study includes validating the theoretical framework for the information complexity concept through the use of questionnaires and providing a practical tool for designers to measure information complexity of the visual display for iterative improvement. © 2011 Wiley Periodicals, Inc.     

Hardness Hypotheses, Derandomization, and Circuit Complexity

We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences:

Complexity of boolean functions in a class of canonical polarized polynomials

Relationships for the maximum of a minimal number of summands among all canonical polarized polynomials of a Boolean function are obtained. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 179–183, May–June, 2000.