Functional inversion and communication complexity

We study the relationship between the multiparty communication complexity of functions over certain communication topologies and the complexity of inverting those functions. We show that if a function ofn variables has aring-protocol or atree-protocol of communication complexity bounded by ϕ, then there is a circuit of size that computes an inverse of the function. Consequently, we prove that although invertingNC ⁰ Boolean circuits isNP-hard, planarNC ¹ Boolean circuits can be inverted inNC, and hence in polynomial time. From the ring-protocol theorem, we derive an ω(n logn) lower bound on the VLSI area required to lay out any one-way function. Our results on inverting boolean circuits can be extended to algebraic circuits over finite rings. We prove that on certain topologies no one-way function can be computed with low communication complexity. The preliminary version of this paper appeared inCRYPTO 91. This work was supported in part by National Science Foundation Grant DCR-8713489. Part of this work was done while the author was at the School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, U.S.A. Current address: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, U.S.A.     

Average interconnection delay estimation for on-FPGA communication links

A new method is presented and an analytical expression is derived for average interconnection delay estimation. This method is directly applicable to predicting the average delay for high-bandwidth communication links implemented on FPGAs. The theoretical results are compared with the measured data from the actual circuits and an average error of 4.6% is reported.     

Set reconciliation with nearly optimal communication complexity

We consider the problem of efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity, which we call the set reconciliation problem. We describe an approach to set reconciliation based on a polynomial encoding of sets. The resulting protocols exhibit tractable computational complexity and nearly optimal communication complexity when the sets being reconciled are sparse. Also, these protocols can be adapted to work over a broadcast channel, allowing many clients to reconcile with one host based on a single broadcast, even if each client is missing a different subset.     

The complexity of problems in wireless communication

Ad hoc networks become increasingly important in our life, for their advantages without relying on existing infrastructures and for their ability to be fast implemented, especially in the aspects of rescue after disasters and military. However, since every node in an ad hoc network can move freely, we are confronted with many new problems when compared with cellular networks and WiFi, such as the change of connectivity between nodes and signal interference and blockage by obstacles. Thus, it is important to understand solutions and complexities of various programming problems in ad hoc networks. In this paper, based on an existing mobility model for ad hoc networks, we study solutions and complexities of a series of problems proposed by Greenlaw, Kantabutra, and Longani, including the multiusers simultaneous communication problem (MUSCP), the longer communication problem (LCP), the obstacle removal problem (ORP) and the user communication, limited number of sources problem (UCLNSP). For MUSCP and LCP, we provide efficient algorithms to solve them and prove that they are P problems. On the other hand, for ORP and UCLNSP, by applying reduction from the set covering decision problem, we prove that they are NP-complete, and thus, they are intractable, unless \(P=NP.\)     

On the communication complexity of zero-knowledge proofs

The fact that there are zero-knowledge proofs for all languages in NP (see [15], [6], and [5]) has, potentially, enormous implications to cryptography. For cryptographers, the issue is no longer “which languages in NP have zeroknowledge proofs” but rather “which languages in NP have practical zeroknowledge proofs.” Thus, the concrete complexity of zero-knowledge proofs for different languages must be established. In this paper we study the concrete complexity of the known general methods for constructing zero-knowledge proofs. We establish that circuit-based methods, which can be applied in either the GMR or the BCC model, have the potential of producing proofs which can be used in practice. Then we introduce several techniques which greatly reduce the concrete complexity of circuit-based proofs, and we show that these techniques lead to zero-knowledge proofs of knowledge. Finally, we show how to combine the techniques of Kilian, Micali, and Ostrovsky, for designing zero-knowledge proofs with only two envelopes, with some of our techniques for reducing the number of bits which the prover must commit to. Supported in part by NSA Grant No. MDA90488-H-2006. Supported in part by NSF Grant No. CCR-8909657.     

Average outage duration of multihop communication systems with regenerative relays

Closed-form expressions for the average outage duration (AOD) of multihop regenerative communication systems over generalized fading channels are presented. Both noise-limited and interference-limited systems are studied. To show the usefulness of the presented expressions, some specific fading scenarios are considered. In addition, some numerical examples of interest comparing direct versus relayed transmission and studying the effect of increasing the number of hops and/or cochannel interferers are plotted and discussed.     

一种减少通信复杂度的RFID搜索树防碰撞算法

针对射频识别搜索树防碰撞算法中通信数据量大、识别时延长等问题,提出了一种减少通信复杂度的防碰撞算法.在标签中引入前缀长度寄存器和响应标志寄存器,在阅读器堆栈区存储前缀个数信息,阅读器通过发送前缀长度信息,对标签进行分类搜索,阅读器和标签不再发送对方已经识别的序列号,有效减少了通信数据量.仿真结果表明,与传统的二叉树搜索防碰撞算法相比,该算法可明显减少系统通信复杂度,提高标签的搜索速率.     

Low complexity carrier phase estimation for m-QAM optical communication systems

Photonic Network Communications - A low complexity carrier phase estimation (CPE) algorithm for M-ary quadrature amplitude modulation (m-QAM) optical communication systems is investigated in this...     

基于超网络理论的军事通信网络复杂性度量方法

针对军事通信网络的结构和功能特点,在建立军事通信超网络描述模型的基础上,定义了超网络邻接矩阵、节点分类连接矩阵、类型匹配指数、超网络模体、模体核和模体熵等概念;通过分析超网络模体的特点,提出使用超网络模体熵来度量网络复杂性,给出了具体的计算方法;最后以某舰艇编队通信网络为例,对比分析了已有网络结构复杂性指标和超网络模体熵所度量的网络特征,说明在网络结构确定的情况下,超网络模体熵可以度量网络的功能复杂性.     

A low complexity pilot aided channel estimation method for WCDMA communication systems

This letter deals with the performance evaluation of a pilot aided method for estimating channel parameters in wideband code division multiple access (WCDMA) communication systems. Unlike previous approaches, a successive interference cancellation algorithm is used to reduce multipath and multiuser interference caused by pilot signal replicas on the channel parameter estimation, and on the detection of the information bearing signals. Comparisons with the ideal case of perfect knowledge of the channel parameters and the classical channel parameter estimation algorithm have highlighted the good performance of the proposed approach.     

Age-based anonymity: a randomized routing approach to communication unobservability

Providing anonymous communication on networks of interconnected computers is an active area of research which aims to enhance the privacy of the users of such networks. Communication unobservability, stronger property compared to anonymity, attempts to guarantee that legitimate messages are not discernible from dummy traffic. A network with an active global adversary is one which it is assumed that all nodes in the network are potentially being monitored at all times, and also that at any time any node could be an adversary. This paper introduces a set of anonymous system design requirements for providing enhanced communication unobservability. A new anonymous networking system was designed based on these requirements to provide both sender and receiver anonymity. The proposed system has a structured peer-to-peer network architecture and a randomized routing algorithm to obfuscate the detection of communication paths and the message routing patterns. An age-based method is proposed to prevent even the first node after the sender from identifying the original sender. A simulation program was designed and implemented to test the proposed system. The effect of different parameters on the proposed algorithm is demonstrated using a simulation program.     

Gamma Gamma强海洋湍流下无线光通信系统的平均容量研究

建立了一个采用强度调制/直接检测(intensity modulation/direct detection,IM/DD)和开关键控(on-off keying,OOK)的水下无线光通信(Underwater wireless optical communication,UWOC)系统,通过采用 Gamma Gamma...     

Joint low‐complexity equalization and CFO estimation and compensation for UWA‐OFDM communication systems

Frequency synchronization has a great importance in preserving the performance of the underwater acoustic (UWA) orthogonal frequency division multiplexing (OFDM) systems. The carrier frequency offset (CFO) estimation can be blind or data‐aided. In this paper, the Zadoff‐Chu (ZC) sequences are used for OFDM synchronization in UWA communications, and they are compared with different data‐aided algorithms. We propose a low‐complexity algorithm for CFO estimation based on ZC sequences. Also, a joint equalization and CFO compensation scheme for UWA‐OFDM communication systems is presented. Simulation results demonstrate that the proposed CFO estimation algorithm allows estimation of the CFO accurately with a simple implementation in comparison with the traditional schemes. Also, the performance of the UWA‐OFDM system can be preserved in the presence of frequency offsets.     

移动通信中用于高阶调制LDPC码译码器的一种低复杂度盲信噪比估计器

在LDPC（Low Density Parity Check,低密度校验）码软迭代译码器中,需要信道信噪比以生成接收比特先验信息.同时,为了提高频谱利用率,传输符号通常采用高阶调制.本文研究的即是如何从高阶调制符号中估计出信噪比以用于LDPC译码器.本文在只适用于BPSK调制的在线信噪比估计器的基础上,推导得到一种适用于8PSK调制的低复杂度盲信噪比估计算法-8PSKM-BSNRE,这种算法的思路还可被扩展应用于其他高阶调制符号.计算机仿真结果证明,8PSKM-BSNRE在应用于LDPC码译码器时具有较好的性能.     

一种基于分布式频域线性卷积码的低计算复杂度的均衡算法

在本文中,考虑了基于分布式频域线性卷积空频码(distributed frequency-domain linear convolutivespace-frequency codes,DFLC-SFC)的协同通信系统。该协同通信系统考虑了多个载波频率偏移(multiple carrierfrequency offsets,MCFOs)的影响,同时假定中继结点到目的结点的信道是平坦衰落的。通过数学推导,该系统模型得到了简化。因此,本文最终得到了等价的限带模型,同时也分析了关于最终等价信道矩阵的限带属性。在此限带模型的基础之上,本文提出了一种应用LDHH矩阵分解的限带块最小均方误差(minimum mean square error,MMSE)均衡方法。进一步地,为了实现相应的限带操作,本文还定义了一类特殊的掩码矩阵。相比较于那些传统的MMSE均衡方法,本文所提出的均衡方法在保持较满意的系统性能的前提下,具有相对较低的计算复杂度。     

Reduce‐complexity fuzzy‐inference‐based iterative multiuser detection for wireless communication systems

In recent years, combining multiuser detection and intelligence computer scheme have received considerable attention. In this paper, adaptive fuzzy‐inference multistage matrix wiener filtering (FI‐MMWF) techniques, based on the minimum mean‐square error criterion, are proposed for ultra‐wideband (UWB) impulse radio communication systems. These FI‐MMWF‐based algorithms employ a time‐varying fuzzy‐inference‐controlled filter stage. Consequently, the proposed approaches accomplish a substantial saving in complexity without trading off the system performance and dynamic‐tracking characteristic. In addition, the fuzzy‐logic‐controlled matrix conjugate gradient algorithm is adopted to reduce the system complexity without trading off the bit‐error‐rate (BER). Simulations are conducted to evaluate the convergence and tracking behavior of the proposed MMWF algorithm, and the BER of the time‐hopping‐UWB system in a realistic UWB channel is investigated. Copyright © 2011 John Wiley & Sons, Ltd.     

2mpn周期二元序列的线性复杂度和k错线性复杂度

序列线性复杂度的稳定性是衡量其随机性好坏的一个重要指标.针对2mpn周期二元序列,利用多项式分解等工具,确定了使得序列的k错线性复杂度严格小于其线性复杂度的最小k值的上下界,其中n是正整数,m是非负整数,P是奇素数,2是模p2的原根.     

Lai-Massey结构平均差分概率和平均线性链概率的上界估计

Lai-Massey结构是由IDEA算法发展而来的一个分组密码结构,FOX系列密码算法是该密码结构的代表。该文从差分概率关于独立等概轮密钥的平均概率上界和给定起点和终点的线性链的平均概率上界两个角度出发,研究Lai-Massey 结构的差分和线性可证明安全性。该文证明了2轮Lai-Massey结构的非平凡差分对应关于独立等概的轮密钥的平均概率$ \le p{}_{\max }$;证明了当Lai-Massey 结构的F函数是正型置换时,轮数$r \ge 3$的非平凡差分对应关于独立等概的轮密钥的平均概率$ \le p_{\max }^2$。针对给定起点和终点的线性链的平均概率上界,该文也获得了类似的结论。     

二元周期序列的线性复杂率与k-错复杂度的关系

k-错复杂度是指改变序列一个周期段中k个或少于k个符号后所得序列的最小线性复杂度。该文讨论了周期为2~pq(q为奇素数,2是模q~2的本原根)的二元序列线性复杂度与k的关系,这里k是满足LC_k(S~N)相似文献