Improved Upper Bounds on Stopping Redundancy

For a linear block code with minimum distance d, its stopping redundancy is the minimum number of check nodes in a Tanner graph representation of the code, such that all nonempty stopping sets have size d or larger. We derive new upper bounds on stopping redundancy for all linear codes in general, and for maximum distance separable (MDS) codes specifically, and show how they improve upon previous results. For MDS codes, the new bounds are found by upper-bounding the stopping redundancy by a combinatorial quantity closely related to Turan numbers. (The Turan number, T(v,k,t), is the smallest number of t-subsets of a v-set, such that every k-subset of the v-set contains at least one of the t-subsets.) Asymptotically, we show that the stopping redundancy of MDS codes with length n and minimum distance d >1 is T(n,d-1,d-2)(1+O(n^-1)) for fixed d, and is at most T (n,d-1,d-2)(3+O(n^-1)) for fixed code dimension k=n-d+1. For d=3,4, we prove that the stopping redundancy of MDS codes is equal to T(n,d-1,d-2), for which exact formulas are known. For d=5, we show that the stopping redundancy of MDS codes is either T(n,4,3) or T(n,4,3)+1     

Improved Lower Bounds on Signal Parameter Estimation

An improved technique for bounding the mean-square error of signal parameter estimates is presented. The resulting bounds are independent of the bias and stronger than previously known bounds.     

Upper and Lower Bounds on Black-Box Steganography

We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver). Preliminary version appears in TCC 2005 [5].     

Lower Bounds on Correlation of Z-Complementary Code Sets

A set of binary codes is called a Z-complementary code set if the sum of the autocorrelation functions of the codes involved is zero in the zero correlation zone (ZCZ) except at zero shift. Comparing to the traditional complementary code sets, the Z-complementary code sets not only have more freedom on the code length, but also have much more mates. In this paper, lower bounds on periodic/aperiodic correlation of Z-complementary binary code sets with respect to the number of mates, family size, sequence length, the length of ZCZ, maximum periodic/aperiodic autocorrelation sidelobe inside the ZCZ and maximum periodic/aperiodic crosscorrelation value inside the ZCZ, are derived. The proposed lower bounds provide theoretical criteria for designing, optimizing and choosing Z-complementary code set in applications.     

稀疏随机矩阵的观测次数下界

压缩感知理论中的稀疏重构问题,要将一个高维信号从它的低维投影中恢复出来,通常选用稠密随机矩阵作为观测矩阵来解决这一问题。而某些稀疏随机矩阵作为观测矩阵也可以达到这一目的。稀疏随机矩阵的特点是,在编码和重构过程中都具有较低的计算复杂度,更新方便,且对存储容量的要求较低。该文基于压缩感知理论,分别对列重固定、行重固定以及一般的稀疏随机矩阵进行了研究,当这些稀疏随机矩阵满足有限等距性质时,推导了观测次数应满足的下界条件,并对三种矩阵的性能进行了分析。以二值稀疏随机矩阵为特例,进行了仿真实验。实验结果显示,结论给出的观测次数下界是比较紧的,并验证了列重固定、行重固定的稀疏随机矩阵作为观测矩阵的可行性和实用性。      

Lower Bounds for Constant Multiplication Problems

Lower bounds for problems related to realizing multiplication by constants with shifts, adders, and subtracters are presented. These lower bounds are straightforwardly calculated and have applications in proving the optimality of solutions obtained by heuristics.     

Lower Bounds on Error Probability in the Presence of Large Intersymbol Interference

A lower bound on the symbol error probability achieved by any estimator of a digital pulse-amplitude-modulated sequence in the presence of white Gaussian noise and intersymbol interference is presented. The bound reduces to the well-known single-pulse error probability bound when intersymbol interference is small, but is tighter when interference is large. For example, on the singlepole (RC) channel, the effective signal-to-noise ratio for any estimator is shown to decrease by at least 3 dB for every doubling in pulse rate T^-1asT rightarrow 0and, on the double-pole channel, by at least 9 dB, thus disproving a recent conjecture [2] on the performance of nonlinear receivers.     

一种具有最小距离下界的正则LDPC码的构造

主要提出一种新的计算规则LDPC(low-density parity-check)码的最小距离下界的方法。该方法是基于LDPC码的每个变量节点的独立树进行构造LDPC码。与随机构造的LDPC码和用PEG方法构造的方法比较,这个新的构造方法得到了更大的围长和最小距离下界。在AWGN信道中,在码长N=1 008和N=1 512时进行Matlab仿真,仿真结果表明随着信噪比的增加此方法构造的LDPC码有优异的误码率性能。     

广义Hamming重量上,下界的对偶定理

本文给出了一种广义Ｈａｍｍｉｎｇ重量上、下界的对偶定理。即若给定一个码的对偶码的广义Ｈａｍｍｉｎｇ重量上界（或者下界），可以给出该码的广义Ｈａｍｍｉｎｇ重量上界（或者下界）。Ｈ．Ｓｔｉｃｈ－ｎｏｔｈ（１９９４）曾给出了迹码（如ＢＣＨ码和Ｇｏｐｐａ码的对偶码）的广义Ｈａｍｍｉｎｇ重量一种上、下界，如果采用本文结果就可以给出迹码的对偶码的广义Ｈａｍｍｉｎｇ重量一种上、下界。因此，本文的结果是Ｈ．Ｓｔｉｃｈｎｏｔｈ的结果的有益补充     

有仲裁人认证码的信息论下界

在Ｓｉｍｍｏｎｓ给出的有仲裁人认证码中,主要研究了五种欺骗攻击。Ｊｏｈｎｓｓｏｎ对这些欺骗成功概率的信息论下界进行了研究。本文则给出了有仲裁人认证码中的敌方和收方的ｉ（≥０）阶欺骗攻击成功概率的信息认下界,完善了关于欺骗攻击成功概率的下界的研究。     

Lower Bounds for Finite Intersymbol Interference Error Rates

Some simple lower bounds for the probability of error for band-restricted digital communication are presented. The bounds revolve two values of the complementary error function, the system SNR, the peak value, second moment, and sometimes, the fourth moment of the intersymbol interference. Contrary to other available lower bounds, no parameter searches or infinite series computations are required. The bounds hold when the system "eye" is open and in some cases when the source symbols are correlated.     

Lower Bounds for Binary Codes of Covering Radius One

Let K(n, l) denote the minimal cardinality of a binary code of length n and covering radius one. Blass and Litsyn proved a lower bound K(n, l) for in the case n equiv 5 (mod6). We give a simplification of the proof, which yields a slightly better result.     

Lower and Upper Bounds for Misclassification Probability Based on Renyi's Information

Fano's inequality has proven to be one important result in Shannon's information theory having found applications in numerous proofs of convergence. It also provides us with a lower bound on the symbol error probability in a communication channel, in terms of Shannon's definitions of entropy and mutual information. This result is also significant in that it suggests insights on how the classification performance is influenced by the amount of information transferred through the classifier. We have previously extended Fano's lower bound on the probability of error to a family of lower and upper bounds based on Renyi's definitions of entropy and mutual information. These new bounds however, despite their theoretical appeal, were practically incomputable. In this paper, we present some modifications to these bounds that will allow us to utilize them in practical situations. The significance of these new bounds is threefold: Illustrating a theoretical use of Renyi's definition of information, extending Fano's result to include an upper bound for probability of classification error, and providing insights on how the information transfer through a classifier affects its performance. The performance of the modified bounds is investigated in various numerical examples, including applications to digital communication channels that are designed to point out the major conclusions.     

bent函数和半bent函数的二阶非线性度下界

该文研究了形如f(x,y)的n+1变元bent函数和半bent函数的二阶非线性度,其中xGF(2n), yGF(2)。首先给出了f(x,y)的2n-1个导数非线性度的精确值;然后推导出了函数f(x,y)的其余2n个导数的非线性度紧下界。进而给出了f(x,y)的二阶非线性度的紧下界。通过比较可知所得下界要优于现有的一般结论。结果表明f(x,y)具有较高的二阶非线性度,可以抵抗二次函数逼近和仿射逼近攻击。     

MIMO雷达相位编码波形集相关函数下界综述

MIMO雷达波形集的互相关函数峰值越低,则正交性越好,波形分集增益越高。非循环互相关函数下界的研究有助于确定波形分集增益的极限值,对MIMO雷达波形设计与应用有重要意义。相位编码波形集是目前被研究最多的MIMO雷达波形集,对其相关函数下界的研究较为深入。本文对目前相位编码波形集相关函数各类下界的研究进行归纳总结,包括相关函数峰值旁瓣下界、相关函数积分旁瓣下界、互相关内积下界、互补序列相关函数下界四大类。相关函数峰值旁瓣下界是影响MIMO雷达波形分集增益的关键指标,其他类型的下界与相关函数峰值旁瓣下界之间存在潜在联系,这可能有助于相关函数峰值旁瓣下界的确定。不同波形数,不同码长的典型相位编码波形相关函数指标与下界的对比结果表明,目前已有下界都不够紧,尤其在波形数较多时。因此,MIMO雷达相位编码波形集相关函数下界仍是一个值得研究的开放问题。      

激光多普勒测速参数估计的Cramer-Rao下限

针对固体运动目标高速度、高加速度的特点,研究了高斯白噪声背景下激光多普勒测速同波信号的参数估计问题.通过计算参数矢量的费希尔(Fisher)信息矩阵,分析了实同波信号的多普勒频率和频率变化率估计方差的克拉末-雷奥(Cramer-Rao)下限(CRLB),推导了采样点数较大时同波信号参数方差估计的CRLB计算公式,讨论了各参数的最大似然估计(MLE).指出同波信号参数估计方差的CRLB与采样点数、信噪比及初相有关,采样点数较大时,实信号参数估计方差的CRLB为对应复信号的2倍.在不同的采样点数和信噪比下仿真表明,提高回波信号的信噪比和增加采样点数可以减小各参数估计方差的CRLB,结果与理论分析吻合.     

Random-Coding Lower Bounds for the Error Exponent of Joint Quantization and Watermarking Systems

We establish random-coding lower bounds to the error exponent of discrete and Gaussian joint quantization and private watermarking systems. In the discrete system, both the covertext and the attack channel are memoryless and have finite alphabets. In the Gaussian system, the covertext is memoryless Gaussian and the attack channel has additive memoryless Gaussian noise. In both cases, our bounds on the error exponent are positive in the interior of the achievable quantization and watermarking rate region.     

Error Rate Lower Bounds for Digital Communication with Multiple Interferences

This paper presents simple and general lower bounds for error rates in digital communication systems. The information bearing signal is taken to be impaired by additive interference and carrier phase jitter. The former is taken to be composed of two components; one component is peak-limited while the other is not. Intersymbol and cochannel interference are examples of peak-limited interference while additive thermal noise is an example of a nonpeak-limited interference. The novelty of the paper is in the generality of the results and in obtaining a simple error bound for transmission in the presence of cochannel interference and carrier phase jitter.