Sinusoids versus Walsh functions

In most of the applications contemplated for Walsh functions these binary waveforms would replace the more usual sinusoids, as the fast-Walsh-transform algorithm appears to make them very attractive for many kinds of signal processing. This paper begins with a brief review of the characteristics of Walsh functions and of their applications. Some old and some new interrelations are presented between sinusoids and Walsh functions, but the principal aim of the paper is to investigate the truncation and roundoff errors associated with the use of Fourier and of Walsh series. By employing simplifying approximations it is found that, for long samples of smooth signals, far more terms are required in the Walsh-series representation and greater accuracy is required of their coefficients for a given rms total error. Even for discontinuous signals the Walsh series may require substantially more terms, thus counterbalancing the computational advantage of the fast Walsh transform. This relative inefficiency of the Walsh-series representation of long waveforms may explain why it has not proven particularly effective in applications.     

Applications of Walsh functions in communications

Communication theory was founded on the system of sine-cosine functions. A more general theory has become known more recently; it replaces the sine-cosine functions by other systems of orthogonal functions, and the concept of frequency by that of sequency. Of these systems, the Walsh functions are of great practical interest since they lead to equipment that is easily implemented by semiconductor technology. Filters, multiplexing equipment, and a voice analyzer/synthesizer have been built successfully for Walsh functions. Some interesting applications of electromagnetic Walsh waves have been found theoretically.     

复制生成序列的自相关函数研究

介绍了以二进制码为复制信息,用平移复制生成序列的方法。讨论了复制生成序列的性质和复制生成序列的自相关函数的性质。依据序列的复制特性,给出了一个复制生成序列自相关函数的计算公式,并给出了自相关函数值为零的一个充要条件,及相应的数学证明。最后讨论了Paley顺序的离散Walsh函数的自相关函数。     

Variational image segmentation using boundary functions

A general variational framework for image approximation and segmentation is introduced. By using a continuous "line-process" to represent edge boundaries, it is possible to formulate a variational theory of image segmentation and approximation in which the boundary function has a simple explicit form in terms of the approximation function. At the same time, this variational framework is general enough to include the most commonly used objective functions. Application is made to Mumford-Shah type functionals as well as those considered by Geman and others. Employing arbitrary L(p) norms to measure smoothness and approximation allows the user to alternate between a least squares approach and one based on total variation, depending on the needs of a particular image. Since the optimal boundary function that minimizes the associated objective functional for a given approximation function can be found explicitly, the objective functional can be expressed in a reduced form that depends only on the approximating function. From this a partial differential equation (PDE) descent method, aimed at minimizing the objective functional, is derived. The method is fast and produces excellent results as illustrated by a number of real and synthetic image problems.     

一类密码函数的构造与分析

利用t+1个n元布尔函数(称为基函数)级联构造了一类n+t元布尔函数G(x,y),并给出了G(x,y)的Walsh循环谱和自相关系数。通过Krawtchouk多项式与Krawtchouk矩阵对G(x,y)和基函数的关系进行了研究。分析了G(x,y)的密码学性质:相关免疫性、扩散性和代数免疫性。特别地,当t=2时,分析了G(x,y)与基函数的具体关系。另外,一般化该构造方法构造了一类多输出布尔函数,给出了该类多输出布尔函数的广义Walsh循环谱,进而分析了该类多输出布尔函数的相关免疫性和代数免疫性。     

System inversion using orthogonal functions

This paper shows how to use orthogonal functions to invert singular (i.e., generalized state-space) systems. The approach is to express the inverse system itself as a singular system, and then to apply the theory of orthogonal functions to convert that differential-algebraic system to a purely algebraicgeneralized Lyapunov equation whose solution yields the input of the original system given its output. Both left and right inversion are treated.Necessary and sufficient conditions for the existence and uniqueness of the generalized Lyapunov equation are derived, and a generalizedQZ algorithm is given for its efficient solution. It is also shown that the coefficients in the Walsh function expansion may be approximately found using an FFT-type butterfly network.These results provide both an extension in theory, by investigating the properties of a new Lyapunov equation, and an extension in the implementation of system inversion, by providing a scheme which applies to generalized state-space systems and uses an unconventional approach which may prove to be a useful contribution.This research was partially supported by NSF Grant ECS-8518164. The order of authors is random and has been selected by the toss of a coin.     

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.     

Walsh-like functions and their relations

A new discrete transform, the `Haar-Walsh transform', has been introduced. Similar to well known Walsh and non-normalised Haar transforms, the new transform assumes only +1 and -1 values, hence it is a Walsh-like function and can be used in different applications of digital signal and image processing. In particular, it is extremely well suited to the processing of two-valued binary logic signals. Besides being a discrete transform on its own, the proposed transform can also convert Haar and Walsh spectra uniquely between themselves. Besides the fast algorithm that can be implemented in the form of in-place flexible architecture, the new transform may be conveniently calculated using recursive definitions of a new type of matrix, a `generator matrix'. The latter matrix can also be used to calculate some chosen Haar-Walsh spectral coefficients which is a useful feature in applications of the new transform in logic synthesis     

性能最优化布尔函数的构造

考虑各项性能指标的相互联系,以构造综合性能最优化的函数为目标,以Bent函数为基础,综合运用离散Walsh谱和特征矩阵工具,通过级连、分裂和有条件修改函数输出序列,提出了性能最优化的函数构造法。该构造法可以根据不同需要灵活构造同时满足多个性能要求的多种函数。     

Unified algorithm to generate Walsh functions in four different orderings and its programmable hardware implementations

The paper presents an algorithm to generate Walsh functions in four different orderings: Hadamard, Harmuth, Paley and strict sequencing. By the analysis of the properties and mutual relations among these four orderings, the authors found a unified approach to generate any of the orderings from the primary set of Rademacher functions. By using these properties, the authors developed a programmable Walsh function generator for 64 outputs by both field programmable gate arrays and lookup table cascades to estimate the amount of hardware and performance. Such a programmable Walsh function generator can be used in VLSI testing, CDMA, pattern recognition, as well as image and signal processing.     

Expansion of Walsh Functions in Terms of Shifted Rademacher Functions and Its Applications to the Signal Processing and the Radiation of Electromagnetic Walsh Waves

The expressions for Walsh functions in terms of shifted Rademacher functions are applicable to the design of a directive and selective array antenna for Walsh waves which is capable of eliminating the interference caused by impulsive noises. They also are applicable to voice processing because of their shift-invariant property. The shifted Rademacher functions were previously introduced by shiftiAg horizontally the periodic Rademacher functions. It was shown that the Walsh functions could be expressed as a linear combination of a finite number of the shifted Rademacher functions. This paper develops the actual expansions of the Walsh functions in terms of the shifted Rademacher functions. The coefficients in this series take only the values of either + 1 or -1. The shifted Rademacher coefficients appearing in the expansion of a given function in tenns of shifted Rademacher functions have the advantage that the coefficients of a shifted function are available by shifting cyclically the original coefficients.     

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.     

Plateaued函数的正规性

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

Approximation to duration-limited functions by sampling sums

According to the classical sampling theorem, any band-limited function can be exactly represented by its sampling expansion. It is shown that for duration-limited functions f satisfying certain smoothness properties this representation holds approximately. No assumptions upon the Fourier transform of f are needed. Estimates for the approximation error are given.     

Relations among sequency, axis symmetry, and period of Walsh functions (Corresp.)

A parameter is defined that distinguishes the members of the set{WAL(s,m)}of Walsh functions. There is a one-to-one correspondence between sequency and axis symmetry of each Walsh function. Axis symmetry is derived from the sequency number. A procedure is introduced for obtaining the period of a Walsh function from its sequency number.     

Transforms of generalized Walsh functions

The Laplace transforms of the generalized Walsh functions are presented, and from these the Fourier transforms and z transforms are easily deduced. The Fourier series representations of those generalized functions that are periodic are also given, and the bandwidth of finite-termed approximations is determined.     

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.     

Walsh analysis of power-law systems (Corresp.)

Walsh-type signals exciting memoryless power-law systems are considered. The input is assumed to consist of a sum of weighted Walsh functions. A method is given for finding the weights of the Walsh functions in the output when the input is a finite Walsh series. It is shown that the fast Walsh transform can be used to facilitate the necessary computation.     

Recursive computation of the walsh transform for delta-modulated functions

In this paper, a very simple electronic system for the recursive computation of the Walsh Transform for delta-modulated functions is presented. The proposed method avoids the need of demodulating the function.     

Microprocessor-based sinusoidal waveform synthesis using Walsh andrelated orthogonal functions

A method is described of eliminating harmonics in a pulsewidth-modulated waveform using Walsh and related functions that substitute linear algebraic equations for the nonlinear equations required in Fourier-series harmonic elimination. A microprocessor can then be used to calculate the firing angles to cancel the unwanted harmonics. In an extension of the method, it is shown that a sine wave can be synthesized from a fixed-voltage DC supply by using a reasonable number of power electronic switches