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.     

Ordering of Walsh Functions

The construction of Walsh functions is derived by means of the concepts of "symmetric copy" and "shift copy." Recursive relations based on the Kronecker product of matrices are also deduced from these concepts. There is a fourth useful ordering of the Walsh functions, called here X-ordering, in addition to the three known orderings usually referred to as Walsh-, Paley-, and Hadamardordering. An X-ordering function has the following features: lower order numbers of X-ordering correspond to even functions; higher order numbers of X-ordering correspond to odd functions; even order numbers of X-ordering correspond to lower sequencies; odd number of X-ordering correspond to higher sequencies. Finally, relations between the four orderings are given.     

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.     

Frequency Synthesis Using Walsh Functions

A new scheme for the programmable generation of either square or sine waves of a required frequency is proposed. It uses neither feedback, nor table lookup of stored values, but it derives the desired square wave from a Walsh function, fairly simple to select and to generate with digital circuits. For this purpose, the Walsh function is counted down in a binary counter, at whose output a function with clean spectrum results, whose spurious components can be bounded by a simple formula. This approach becomes the design principle for a programmable frequency synthesizer with phase-continuous output, practically instantaneous switching between frequencies, and no limit on the number of closely and evenly spaced frequencies that can be selected.     

On Representations of Walsh Functions

A new recursive formula for defining Walsh functions on the real line is presented. It leads, in a natural way, to an explicit representation of Walsh futctions. The explicit representation can be identified with. the representation of Walsh functions by the products of Rademacher functions. It can also lead to other representations of Walsh functions in a straight-forward manner. Using the new-formulation, one can prove many known properties of Walsh functions easily and systematically and gain new insight.     

Some Comments Concerning Walsh Functions

The use of explicit forms for Walsh functions removes much of the confusion surrounding these interesting functions and permits simple proofs of their properties. Thus, for example, their period is far easier to determine than Alexandridis found, but their Fourier spectra are more complex than Schreiber's approximation suggests. For wave-form analysis, certain Walsh functions--the regular symmetric square waves--are more useful than are the others.     

广义沃尔什函数的构造与生成

本文对沃尔什函数的对称复制和平移复制概念进行了推广,提出了用循环右移复制和广义平移复制方式来构造或产生广义沃尔什函数(Chrestenson函数)的方法     

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.     

Walsh Orthogonal Functions in Geometrical Feature Extraction

Walsh functions are used in designinq a feature extraction algorithm. The ?axis-symmetry? property of the Walsh functions is used to decompose geometrical patterns. An axissymmetry (a.s.)-histogram is obtained from the Walsh spectrum of a pattern by adding the squares of the spectrm coefficients that correspond to a given a.s.-number ? and plotting these against ?. Since Walsh transformation is not positionally invariant, the sequency spectrum does not specify the pattern uniquely. This disadvantage is overcome by performing a normalization on the input pattern through Fourier transformation. The a.s.-histogram is obtained from the Walsh spectrum coefficients of the Fourier-normalized rather than the original pattern. Such histogram contains implicit information about symmetries, periodicities, and discontinuities present in a figure. It is shown that a.s.-histograms result in great dimensionality reduction in the feature space, which leads to a computationally simpler classification task, and that patterns which differ only in translations or 90° rotation have equal a.s.-histograms.     

A Simple Recursive Definition for Walsh Functions

This paper presents a simple recursive definition for Walsh functions, which overcomes the shortcomings of other recursive definitions. A rule of thumb for writing down the explicit representation for Walsh functions of any order is also devised. In addition, this recursive formula is used to generate discrete Walsh functions in matrix form.     

Noise-Error Determination of Combinational Circuits by Walsh Functions

The stochastic behavior of digital combinational circuits is analyzed by the use of Walsh functions. An n-input Boolean function is represented as a Walsh series and the error caused by noise is measured in terms of a distance which is the fraction of the time that the system output due to noise-corrupted signal differs from that due to signal alone. It is shown that the error can be expressed as the sum of two parts: one part depends only on noise statistics, and the other on both signal and noise. Some interesting properties of both parts are discussed and typical examples are given.     

Application of Walsh Functions for Microprocessor-Based Transformer Protection

The paper presents the application of Walsh functions for digital differential protection of power transformers. A digital differential relay impelementing the Walsh algorithm is simulated using a personal computer. The algorithm shows good response in terms of speed and accuray.     

Dualities Between Entropy Functions and Network Codes

In communications networks, the capacity region of multisource network coding is given in terms of the set of entropy functions $Gamma ^{ast }$. More broadly, determination of $Gamma ^{ast }$ would have an impact on converse theorems for multi-terminal problems in information theory. This paper provides several new dualities between entropy functions and network codes. Given a function $ggeq 0$ defined on all subsets of $N$ random variables, we provide a construction for a network multicast problem which is “solvable” if and only if $g$ is the entropy function of a set of quasi-uniform random variables. The underlying network topology is fixed and the multicast problem depends on $g$ only through link capacities and source rates. A corresponding duality is developed for linear network codes, where the constructed multicast problem is linearly solvable if and only if $g$ is linear group characterizable. Relaxing the requirement that the domain of $g$ be subsets of random variables, we obtain a similar duality between polymatroids and the linear programming bound. These duality results provide an alternative proof of the insufficiency of linear (and abelian) network codes, and demonstrate the utility of non-Shannon inequalities to tighten outer bounds on network coding capacity regions.      

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.     

Measurement of Continuous-Time Linear System Parameters Via Walsh Functions

The parameters of a continuous-time linear system are identified by use of an integral equation representation of plant-dynamics. Walsh functions are used to express the integral functions in terms of measured periodic output data. A simple method for numerical evaluation of the integral functions using matrices is given. Emphasis is placed on reducing computational requirements and in developing compact programs so that implementation on a 16-bit microprocessor is feasible. Computer simulations and experimental results obtained with a Texas Instrument 9900 microprocessor are used to discuss truncation errors, correction factors, and estimation accuracies.