Information of deterministic functions and quantum information of non probabilistic matrices A unified approach and new results

This paper provides new results on the entropy of functions on the one hand, and exhibits a unified approach to entropy of functions and quantum entropy of matrices with or without probability. The entropy of continuously differentiable functions is extended to stair-wise functions, a measure of relative information between two functions is obtained, which is fully consistent with Kullback cross-entropy, Renyi cross-entropy and Fisher information. The theory is then applied to stochastic processes to yield some concepts of random geometrical entropies defined on path space, which are related to fractal dimension in the special case when the process is a fractional Brownian. Then it shows how one can obtain Shannon entropy of random variables by combining the maximum entropy principle with Hartley entropy. Lastly quantum entropy of non probabilistic matrices (extension of Von Neumann quantum mechanical entropy) is derived as a consequence of Shannon entropy of random variables.     

A non-Shannon-type conditional inequality of information quantities

Given n discrete random variables Ω={X₁,…,X_n}, associated with any subset α of {1,2,…,n}, there is a joint entropy H(X_α) where X_α={X_i: i∈α}. This can be viewed as a function defined on 2^{1,2,…,n} taking values in [0, +∞). We call this function the entropy function of Ω. The nonnegativity of the joint entropies implies that this function is nonnegative; the nonnegativity of the conditional joint entropies implies that this function is nondecreasing; and the nonnegativity of the conditional mutual information implies that this function is two-alternative. These properties are the so-called basic information inequalities of Shannon's information measures. An entropy function can be viewed as a 2ⁿ -1-dimensional vector where the coordinates are indexed by the subsets of the ground set {1,2,…,n}. As introduced by Yeng (see ibid., vol.43, no.6, p.1923-34, 1997) Γ_n stands for the cone in IR(2ⁿ-1) consisting of all vectors which have all these properties. Let Γ_n* be the set of all 2ⁿ -1-dimensional vectors which correspond to the entropy functions of some sets of n discrete random variables. A fundamental information-theoretic problem is whether or not Γ¯_n*=Γ_n. Here Γ¯_n * stands for the closure of the set Γ_n*. We show that Γ¯_n* is a convex cone, Γ₂*=Γ₂, Γ₃*≠Γ₃, but Γ¯₃ *=Γ₃. For four random variables, we have discovered a conditional inequality which is not implied by the basic information inequalities of the same set of random variables. This lends an evidence to the plausible conjecture that Γ¯_n*≠Γ_n for n>3     

Short-time spectral and autocorrelation analysis in the Walsh domain

A short-time dyadic autocorrelation function (dacf) and a short-time Walsh energy spectrum of the first kind are defined in the Walsh-Fourier domain. The "natural" choice of the short-time functions does not lead to a Walsh-Fourier transform pair (dyadic Wiener-Khintchine theorem), and thus a second kind of short-time dacf and short-time Walsh energy spectrum are defined as the Walsh-Fourier transforms of the first kind. This leads to a meaningful and convenient Walsh transform pair between the first short-time Walsh energy spectrum and the second short-time dacf. The measurement procedures for both kinds of functions are discussed, and the mean values of these short-time functions are shown to be related to the corresponding long-time functions.     

Plateaued函数的正规性

Plateaued函数作为Bent函数和部分Bent函数的扩展,是一类能实现多个密码学准则折中的性质优良的密码函数。该文基于布尔函数与其分解函数的Walsh谱之间的关系研究了Plateaued函数的复杂性度量指标之一的正规性,根据其正规性质给出了判定给定Plateaued函数是否正规的一个较为简单的算法,并分析了已知Plateaued函数类的正规性。     

流密码中非线性组合函数的分析与设计

从互信息的观点出发，本文研究了非线性组合函数与其部分变量的组合之间的相关性，探讨了这种相关性对流密码安全性的影响。利用Ｗａｌｓｈ变换，分析了Ｂｅｎｔ函数与其部分变量之间的相关性，给出了一类与Ｂｅｎｔ函数有相同渐近谱特性的布尔函数的结构。     

m阶Walsh谱和m次逼近

本文首先引入了一类新的m阶Walsh谱;其次讨论了其性质和实质;最后给出了求最佳m次逼近的一种方法。     

On the Application of Haar Functions

Recent interest in the application of Walsh functions suggests that Haar functions, close relatives of Walsh functions, may also be useful. In this primarily tutorial paper, Haar functions are reviewed briefly and the computational and memory requirements of the Haar transform are analyzed; applications are then discussed. It is concluded that, whereas Haar functions are unlikely to be useful in as many applications as Walsh functions may be, they seem especially well suited to data coding, edge detection, and, perhaps, multiplexing.     

Ternary Walsh Transform and Its Operations for Completely and Incompletely Specified Boolean Functions

The new ternary Walsh transform is considered in this paper. Such a ternary Walsh transform can be used in a similar manner as the standard Walsh transform for binary logic functions as shown here. It is based on the Kronecker product as well as the Galois field and new ternary operations. The same hardware implementation can be used for both forward and inverse ternary Walsh transforms based on its fast algorithms and properties. The ternary Walsh transform is suitable for processing both completely and incompletely specified Boolean functions. Its properties for the decomposition and symmetry detections of the Boolean functions are shown.     

On Defining Partition Entropy by Inequalities

Partition entropy is the numerical metric of uncertainty within a partition of a finite set, while conditional entropy measures the degree of difficulty in predicting a decision partition when a condition partition is provided. Since two direct methods exist for defining conditional entropy based on its partition entropy, the inequality postulates of monotonicity, which conditional entropy satisfies, are actually additional constraints on its entropy. Thus, in this paper partition entropy is defined as a function of probability distribution, satisfying all the inequalities of not only partition entropy itself but also its conditional counterpart. These inequality postulates formalize the intuitive understandings of uncertainty contained in partitions of finite sets. We study the relationships between these inequalities, and reduce the redundancies among them. According to two different definitions of conditional entropy from its partition entropy, the convenient and unified checking conditions for any partition entropy are presented, respectively. These properties generalize and illuminate the common nature of all partition entropies.     

Noise Analysis of Soft Errors in Combinational Digital Circuits Via Walsh Transforms

The noise produced at the output of combinational logic circuits by individual gate failures is analyzed through the use of Walsh functions. Soft errors are modeled by allowing the output of each gate in a particular realization to fail temporarily, possibly introducing an error in the single binary output. The input variables also are allowed to be stochastically driven. The output probability of error contains the Walsh transform of an extended logic function and the Walsh characteristic functions of the input variables as well as the individual gate failure variables. These results are specialized to the case where the inputs are statistically independent of the soft errors. A discussion of the transform of the extended logic function is included.     

Bandwidth requirements for Walsh functions (Corresp.)

The power-density spectrum for the Walsh function of binary orderkis calculated. The model analyzed considers the Walsh function as a random sequence modulating akth-order Rademacher function. The total number of Walsh functions of binary orderkand less is found to be aboutfrac{1}{6}of the overbound 2.4TW.     

Discrete Generalized Fresnel Functions and Transforms in an Arbitrary Discrete Basis

The idea of generalized Fresnel functions, which traces back to expressing a discrete transform as a linear convolution, is developed in this paper. The generalized discrete Fresnel functions and the generalized discrete Fresnel transforms for an arbitrary basis are considered. This problem is studied using a general algebraic approach to signal processing in an arbitrary basis. The generalized Fresnel functions for the discrete Fourier transform (DFT) are found, and it is shown that DFT of even order has two generalized Fresnel functions, while DFT of odd order has a single generalized Fresnel function. The generalized Fresnel functions for the conjunctive and Walsh transforms and the generalized Fresnel transforms induced by these functions are considered. It is shown that the generalized Fresnel transforms induced by the Walsh basis and the corresponding generalized Fresnel functions are unitary and that the generalized Fresnel transforms induced by the conjunctive basis and the corresponding generalized Fresnel functions consist of powers of the golden ratio. It is also shown that the Fresnel transforms induced by the generalized Fresnel functions for the Walsh and conjunctive transforms have fast algorithms.     

On Moments and Walsh Characteristic Functions

This correspondence treats the derivation of natural moments from their corresponding Walsh characteristic function via the dyadic derivative operator. The derivation of a result concerning Walsh transforms of dyadic derivatives of functions is also considered. However, some established ideas such as Walsh transform, dyadic stationarity, and dyadic correlation are introduced first.     

OPEC or a basic problem in source networks

The problem of determining the achievable rate region for an arbitrary source network with one "helper" is still unsolved. Csiszár and the author have shown that it reduces to the one-parameter entropy characterization problem (OPEC), treated in their monograph on information theory. For a discrete memoryless multiple source, solving the OPEC problem means finding a computable characterization of the per-letter conditional entropies of the first n outputs of each of the component sources given an arbitrary function of the first n outputs of the first component source. For sources with three components, the OPEC problem has been solved by Csiszár, Körner, and Marton. However, their result has a very asymmetric form and has not been generalized. This paper gives a substantially simpler proof of the same result in a new symmetric form. Moreover, for sources with more than three components, a new increased region of simultaneously attainable conditional entropies is derived.     

Walsh Functions and Gray Code

Gray code is a natural way of ordering binary vectors in dyadic space, hence it appears frequently in connetion with Walsh functions. In Paley's definition of Walsh functions their sequencies are arranged in Gray code. Gray code also appears in a new Walsh function generation algorithm which obtains a function by locating all its sign changes. There are certain computational advantages in using Gray code rather than sequency ordering. Examples in fast Walsh transform, dyadic convolution and digital filtering are given. Methods of Gray code to binary conversion are discussed.     

The entropy of ordered sequences and order statistics

The entropy of a sequence of random variables under order restrictions is examined. A theorem that shows the amount of entropy reduction when the sequence is ordered is presented. Upper and lower bounds to the entropy reduction and conditions under which they are achieved are derived. Some interesting properties of the entropy of the individual order statistics are also presented. It is shown that the difference between the average entropy of the individual order statistics and the entropy of a member of the original independent identically distributed (IID) population is a constant, regardless of the original distribution. Finally, the entropies of the individual order statistics are found to be symmetric about the median when the probability density function (PDF) of the original IID sequence is symmetric about its mean     

An Algorithm for Computing the Correlation Functions of Walsh Functions

An algorithm for computing the correlations of Walsh functions is presented. Given indices j and p between 0 and 2n - 1, the algorithm computes the correlation between the jth and kth Walsh-Paley function at time differences t = i2-n, i =0,1,..., 2n - 1. These values specify the correlation completely as it varies linearly between these points. A Fortran program is shown. The time required to compute a complete 2n point correlation is approximately the same as that of a 2n point fast Walsh transform.     

基于多通道体全息相关器的二维离散沃尔什变换

利用体全息相关器(VHC)可以完成多通道内积运算的特性,通过将待变换函数和二维沃尔什(Walsh)函数分别编码成输入图像和存储图像,提出了一种基于多通道体全息相关器的二维离散Walsh变换(DwT)方法.此方法可以快速、并行对输入函数做二维离散Walsh变换,并具有很大的速度提升潜力.利用散斑调制和随机交错方法可以提高运算精度.经验证,实验结果与理论值吻合.     

Design of a Walsh Function Generator

To develop a sequency-division multiplex system for telemetry at the Beijing Institute of Aeronautics and Astronautics, it was necessary to design a Walsh function generator that produces ?almost pure? Walsh functions, just as a generator for almost pure sinusoidal functions is needed for frequency-division multiplex system. In this paper, a symbol function s(n, t) is discussed, and the dyadic increment d(k, t) of the Gray code is defined. The relation between s(n, t) and d(h, t) is deduced. A method for the design of a Walsh function generator based on the symbol function s(n, t) is presented. This method has been used to design a Walsh function generator with order number up to n = 64.