HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, more specifically in
harmonic analysis Harmonic analysis is a branch of mathematics concerned with investigating the connections between a function and its representation in frequency. The frequency representation is found by using the Fourier transform for functions on unbounded do ...
, Walsh functions form a complete orthogonal set of
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-orie ...
s that can be used to represent any discrete function—just like
trigonometric functions In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all ...
can be used to represent any
continuous function In mathematics, a continuous function is a function such that a small variation of the argument induces a small variation of the value of the function. This implies there are no abrupt changes in value, known as '' discontinuities''. More preci ...
in
Fourier analysis In mathematics, Fourier analysis () is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph Fo ...
. They can thus be viewed as a discrete, digital counterpart of the continuous, analog system of trigonometric functions on the
unit interval In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysi ...
. But unlike the
sine and cosine In mathematics, sine and cosine are trigonometric functions of an angle. The sine and cosine of an acute angle are defined in the context of a right triangle: for the specified angle, its sine is the ratio of the length of the side opposite that ...
functions, which are continuous, Walsh functions are piecewise constant. They take the values −1 and +1 only, on sub-intervals defined by dyadic fractions. The system of Walsh functions is known as the Walsh system. It is an extension of the
Rademacher system In mathematics, in particular in functional analysis, the Rademacher system, named after Hans Rademacher, is an incomplete orthogonal system of functions on the unit interval of the following form: : \. The Rademacher system is stochastically in ...
of orthogonal functions. Walsh functions, the Walsh system, the Walsh series, and the fast Walsh–Hadamard transform are all named after the American mathematician
Joseph L. Walsh __NOTOC__ Joseph Leonard Walsh (September 21, 1895 – December 6, 1973) was an American mathematician who worked mainly in the field of analysis. The Walsh function and the Walsh–Hadamard code are named after him. The Grace–Walsh–Szeg� ...
. They find various applications in
physics Physics is the scientific study of matter, its Elementary particle, fundamental constituents, its motion and behavior through space and time, and the related entities of energy and force. "Physical science is that department of knowledge whi ...
and
engineering Engineering is the practice of using natural science, mathematics, and the engineering design process to Problem solving#Engineering, solve problems within technology, increase efficiency and productivity, and improve Systems engineering, s ...
when analyzing digital signals. Historically, various numerations of Walsh functions have been used; none of them is particularly superior to another. This articles uses the ''Walsh–Paley numeration''.


Definition

We define the sequence of Walsh functions W_k : ,1\rightarrow \, k\in\mathbb as follows. For any
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
''k'', and
real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
x \in ,1/math>, let :k_j be the ''j''th bit in the
binary representation A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method for representing numbers that uses only two symbols for the natural numbers: typically "0" (zero) and "1" (one). A ''binary number'' may also ...
of ''k'', starting with k_0 as the least significant bit, and :x_j be the ''j''th bit in the fractional binary representation of x, starting with x_1 as the most significant fractional bit. Then, by definition :W_k(x) = (-1)^ In particular, W_0(x) = 1 everywhere on the interval, since all bits of ''k'' are zero. Notice that W_ is precisely the
Rademacher function In mathematics, in particular in functional analysis, the Rademacher system, named after Hans Rademacher, is an incomplete orthogonal system of functions on the unit interval of the following form: : \. The Rademacher system is stochastically in ...
''rm''. Thus, the Rademacher system is a subsystem of the Walsh system. Moreover, every Walsh function is a product of Rademacher functions: :W_k(x) = \prod_^\infty r_j(x)^


Comparison between Walsh functions and trigonometric functions

Walsh functions and trigonometric functions are both systems that form a complete,
orthonormal In linear algebra, two vectors in an inner product space are orthonormal if they are orthogonal unit vectors. A unit vector means that the vector has a length of 1, which is also known as normalized. Orthogonal means that the vectors are all perpe ...
set of functions, an
orthonormal basis In mathematics, particularly linear algebra, an orthonormal basis for an inner product space V with finite Dimension (linear algebra), dimension is a Basis (linear algebra), basis for V whose vectors are orthonormal, that is, they are all unit vec ...
in the
Hilbert space In mathematics, a Hilbert space is a real number, real or complex number, complex inner product space that is also a complete metric space with respect to the metric induced by the inner product. It generalizes the notion of Euclidean space. The ...
L^2 ,1/math> of the
square-integrable function In mathematics, a square-integrable function, also called a quadratically integrable function or L^2 function or square-summable function, is a real- or complex-valued measurable function for which the integral of the square of the absolute value ...
s on the unit interval. Both are systems of
bounded function In mathematics, a function f defined on some set X with real or complex values is called bounded if the set of its values (its image) is bounded. In other words, there exists a real number M such that :, f(x), \le M for all x in X. A functi ...
s, unlike, say, the Haar system or the Franklin system. Both trigonometric and Walsh systems admit natural extension by periodicity from the unit interval to the
real line A number line is a graphical representation of a straight line that serves as spatial representation of numbers, usually graduated like a ruler with a particular origin (geometry), origin point representing the number zero and evenly spaced mark ...
. Furthermore, both
Fourier analysis In mathematics, Fourier analysis () is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Joseph Fo ...
on the unit interval (
Fourier series A Fourier series () is an Series expansion, expansion of a periodic function into a sum of trigonometric functions. The Fourier series is an example of a trigonometric series. By expressing a function as a sum of sines and cosines, many problems ...
) and on the real line (
Fourier transform In mathematics, the Fourier transform (FT) is an integral transform that takes a function as input then outputs another function that describes the extent to which various frequencies are present in the original function. The output of the tr ...
) have their digital counterparts defined via Walsh system, the Walsh series analogous to the Fourier series, and the
Hadamard transform The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
analogous to the Fourier transform.


Properties

The Walsh system \, k \in \mathbb_0 is an abelian multiplicative
discrete group In mathematics, a topological group ''G'' is called a discrete group if there is no limit point in it (i.e., for each element in ''G'', there is a neighborhood which only contains that element). Equivalently, the group ''G'' is discrete if and ...
isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
to \coprod_^\infty \mathbb/2\mathbb, the
Pontryagin dual In mathematics, Pontryagin duality is a duality (mathematics), duality between locally compact abelian groups that allows generalizing Fourier transform to all such groups, which include the circle group (the multiplicative group of complex numb ...
of the Cantor group \prod_^\infty \mathbb/2\mathbb. Its
identity Identity may refer to: * Identity document * Identity (philosophy) * Identity (social science) * Identity (mathematics) Arts and entertainment Film and television * ''Identity'' (1987 film), an Iranian film * ''Identity'' (2003 film), an ...
is W_0, and every element is of
order Order, ORDER or Orders may refer to: * A socio-political or established or existing order, e.g. World order, Ancien Regime, Pax Britannica * Categorization, the process in which ideas and objects are recognized, differentiated, and understood ...
two (that is, self-inverse). The Walsh system is an orthonormal basis of the Hilbert space L^2 ,1/math>. Orthonormality means :\int_0^1 W_k(x)W_l(x) dx = \delta_, and being a basis means that if, for every f \in L^2 ,1/math>, we set f_k = \int_0^1 f(x)W_k(x)dx then :\int_0^1 ( f(x) - \sum_^N f_k W_k(x) )^2 dx \;\ \xrightarrow \rightarrow\infty;\ 0 It turns out that for every f \in L^2 ,1/math>, the
series Series may refer to: People with the name * Caroline Series (born 1951), English mathematician, daughter of George Series * George Series (1920–1995), English physicist Arts, entertainment, and media Music * Series, the ordered sets used i ...
\sum_^\infty f_k W_k(x) converges to f(x) for almost every x \in ,1/math>. The Walsh system (in Walsh-Paley numeration) forms a
Schauder basis In mathematics, a Schauder basis or countable basis is similar to the usual ( Hamel) basis of a vector space; the difference is that Hamel bases use linear combinations that are finite sums, while for Schauder bases they may be infinite sums. This ...
in L^p ,1/math>,   1 < p < \infty. Note that, unlike the Haar system, and like the trigonometric system, this basis is not unconditional, nor is the system a Schauder basis in L^1 ,1/math>.


Generalizations


Walsh-Ferleger systems

Let \mathbb = \prod_^\infty \mathbb/2\mathbb be the
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact, a type of agreement used by U.S. states * Blood compact, an ancient ritual of the Philippines * Compact government, a t ...
Cantor group endowed with
Haar measure In mathematical analysis, the Haar measure assigns an "invariant volume" to subsets of locally compact topological groups, consequently defining an integral for functions on those groups. This Measure (mathematics), measure was introduced by Alfr� ...
and let \hat = \coprod_^\infty \mathbb Z / 2\mathbb Z be its discrete group of characters. Elements of \hat are readily identified with Walsh functions. Of course, the characters are defined on \mathbb D while Walsh functions are defined on the unit interval, but since there exists a modulo zero isomorphism between these
measure space A measure space is a basic object of measure theory, a branch of mathematics that studies generalized notions of volumes. It contains an underlying set, the subsets of this set that are feasible for measuring (the -algebra) and the method that ...
s, measurable functions on them are identified via
isometry In mathematics, an isometry (or congruence, or congruent transformation) is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος ''isos'' me ...
. Then basic
representation theory Representation theory is a branch of mathematics that studies abstract algebra, abstract algebraic structures by ''representing'' their element (set theory), elements as linear transformations of vector spaces, and studies Module (mathematics), ...
suggests the following broad generalization of the concept of Walsh system. For an arbitrary
Banach space In mathematics, more specifically in functional analysis, a Banach space (, ) is a complete normed vector space. Thus, a Banach space is a vector space with a metric that allows the computation of vector length and distance between vectors and ...
(X, , , \cdot, , ) let \_ \subset \operatornameX be a strongly continuous, uniformly bounded
faithful Faithful may refer to: Film and television * ''Faithful'' (1910 film), an American comedy short directed by D. W. Griffith * ''Faithful'' (1936 film), a British musical drama directed by Paul L. Stein * ''Faithful'' (1996 film), an American cr ...
action Action may refer to: * Action (philosophy), something which is done by a person * Action principles the heart of fundamental physics * Action (narrative), a literary mode * Action fiction, a type of genre fiction * Action game, a genre of video gam ...
of \mathbb D on ''X''. For every \gamma \in \hat, consider its
eigenspace In linear algebra, an eigenvector ( ) or characteristic vector is a Vector (mathematics and physics), vector that has its direction (geometry), direction unchanged (or reversed) by a given linear map, linear transformation. More precisely, an e ...
X_\gamma = \. Then ''X'' is the closed linear span of the eigenspaces: X = \overline(X_\gamma, \gamma \in \hat ). Assume that every eigenspace is one-
dimensional In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordi ...
and pick an element w_\gamma \in X_\gamma such that \, w_\gamma\, = 1. Then the system \_, or the same system in the Walsh-Paley numeration of the characters \_ is called generalized Walsh system associated with action \_. Classical Walsh system becomes a special case, namely, for :R_t: x = \sum_^\infty x_j2^ \mapsto \sum_^\infty (x_j \oplus t_j)2^ where \oplus is addition
modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...
2. In the early 1990s, Serge Ferleger and Fyodor Sukochev showed that in a broad class of Banach spaces (so called ''UMD'' spaces) generalized Walsh systems have many properties similar to the classical one: they form a Schauder basis and a uniform finite-dimensional decomposition in the space, have property of random unconditional convergence. One important example of generalized Walsh system is Fermion Walsh system in non-commutative ''L''p spaces associated with hyperfinite type II factor.


Fermion Walsh system

The Fermion Walsh system is a non-commutative, or "quantum" analog of the classical Walsh system. Unlike the latter, it consists of operators, not functions. Nevertheless, both systems share many important properties, e.g., both form an orthonormal basis in corresponding Hilbert space, or
Schauder basis In mathematics, a Schauder basis or countable basis is similar to the usual ( Hamel) basis of a vector space; the difference is that Hamel bases use linear combinations that are finite sums, while for Schauder bases they may be infinite sums. This ...
in corresponding symmetric spaces. Elements of the Fermion Walsh system are called ''Walsh operators''. The term ''Fermion'' in the name of the system is explained by the fact that the enveloping operator space, the so-called hyperfinite type II factor \mathcal R, may be viewed as the space of ''observables'' of the system of countably infinite number of distinct
spin Spin or spinning most often refers to: * Spin (physics) or particle spin, a fundamental property of elementary particles * Spin quantum number, a number which defines the value of a particle's spin * Spinning (textiles), the creation of yarn or thr ...
1/2
fermion In particle physics, a fermion is a subatomic particle that follows Fermi–Dirac statistics. Fermions have a half-integer spin (spin 1/2, spin , Spin (physics)#Higher spins, spin , etc.) and obey the Pauli exclusion principle. These particles i ...
s. Each Rademacher operator acts on one particular fermion coordinate only, and there it is a Pauli matrix. It may be identified with the observable measuring spin component of that fermion along one of the axes \ in spin space. Thus, a Walsh operator measures the spin of a subset of fermions, each along its own axis.


Vilenkin system

Fix a sequence \alpha = (\alpha_1,\alpha_2,...) of
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s with \alpha_k \geq 2, k=1,2,\dots and let \mathbb = \mathbb_\alpha = \prod_^\infty \mathbb/\alpha_k\mathbb endowed with the
product topology In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seemin ...
and the normalized Haar measure. Define A_0 = 1 and A_k = \alpha_1 \alpha_2 \dots \alpha_. Each x \in \mathbb G can be associated with the real number : \left, x\ = \sum_^ \frac \in \left ,1\right This correspondence is a module zero isomorphism between \mathbb G and the unit interval. It also defines a norm which generates the
topology Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
of \mathbb G. For k=1,2,\dots, let \rho_k: \mathbb\to\mathbb where :\rho_k(x) = \exp\left(i\frac\right) = \cos\left(\frac\right) + i \sin\left(\frac\right). The set \ is called ''generalized Rademacher system''. The Vilenkin system is the
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...
\hat = \coprod_^\infty \mathbb/\alpha_k\mathbb of (
complex Complex commonly refers to: * Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe ** Complex system, a system composed of many components which may interact with each ...
-valued) characters of \mathbb G, which are all finite products of \. For each non-negative integer n there is a unique sequence n_0, n_1, \dots such that 0 \leq n_k < \alpha_, k=0,1,2,\dots and :n = \sum_^ n_k A_k. Then \hat = where :\chi_n = \sum_^ \rho_^. In particular, if \alpha_k = 2, k=1,2..., then \mathbb G is the Cantor group and \hat = \left\ is the (real-valued) Walsh-Paley system. The Vilenkin system is a complete orthonormal system on \mathbb G and forms a
Schauder basis In mathematics, a Schauder basis or countable basis is similar to the usual ( Hamel) basis of a vector space; the difference is that Hamel bases use linear combinations that are finite sums, while for Schauder bases they may be infinite sums. This ...
in L^p(\mathbb, \mathbb)1 < p < \infty.


Nonlinear Phase Extensions

Nonlinear phase extensions of discrete Walsh-
Hadamard transform The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
were developed. It was shown that the nonlinear phase basis functions with improved cross-correlation properties significantly outperform the traditional Walsh codes in code division multiple access (CDMA) communications.A.N. Akansu and R. Poluri,
"Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications,"
IEEE Trans. Signal Process., vol. 55, no. 7, pp. 3800–3806, July 2007.


Applications

Applications of the Walsh functions can be found wherever digit representations are used, including
speech recognition Speech recognition is an interdisciplinary subfield of computer science and computational linguistics that develops methodologies and technologies that enable the recognition and translation of spoken language into text by computers. It is also ...
, medical and biological
image processing An image or picture is a visual representation. An image can be two-dimensional, such as a drawing, painting, or photograph, or three-dimensional, such as a carving or sculpture. Images may be displayed through other media, including a pr ...
, and
digital holography Digital holography is the acquisition and processing of holograms with a digital sensor array, typically a CCD camera or a similar device. Image rendering, or reconstruction of object ''data'' is performed numerically from digitized interferograms ...
. For example, the fast Walsh–Hadamard transform (FWHT) may be used in the analysis of digital
quasi-Monte Carlo method In numerical analysis, the quasi-Monte Carlo method is a method for numerical integration and solving some other problems using low-discrepancy sequences (also called quasi-random sequences or sub-random sequences) to achieve variance reduction. ...
s. In
radio astronomy Radio astronomy is a subfield of astronomy that studies Astronomical object, celestial objects using radio waves. It started in 1933, when Karl Jansky at Bell Telephone Laboratories reported radiation coming from the Milky Way. Subsequent observat ...
, Walsh functions can help reduce the effects of electrical
crosstalk In electronics, crosstalk (XT) is a phenomenon by which a signal transmitted on one circuit or channel of a transmission system creates an undesired effect in another circuit or channel. Crosstalk is usually caused by undesired capacitive, ...
between antenna signals. They are also used in passive
LCD A liquid-crystal display (LCD) is a flat-panel display or other electronically modulated optical device that uses the light-modulating properties of liquid crystals combined with polarizers to display information. Liquid crystals do not em ...
panels as X and Y binary driving waveforms where the autocorrelation between X and Y can be made minimal for
pixel In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a Raster graphics, raster image, or the smallest addressable element in a dot matrix display device. In most digital display devices, p ...
s that are off.


See also

*
Discrete Fourier transform In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced Sampling (signal processing), samples of a function (mathematics), function into a same-length sequence of equally-spaced samples of the discre ...
* Dyadic derivative *
Fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
*
Harmonic analysis Harmonic analysis is a branch of mathematics concerned with investigating the connections between a function and its representation in frequency. The frequency representation is found by using the Fourier transform for functions on unbounded do ...
*
Orthogonal functions In mathematics, orthogonal functions belong to a function space that is a vector space equipped with a bilinear form. When the function space has an interval (mathematics), interval as the domain of a function, domain, the bilinear form may be the ...
*
Walsh matrix In mathematics, a Walsh matrix is a specific square matrix of dimensions 2, where ''n'' is some particular natural number. The entries of the matrix (mathematics), matrix are either +1 or −1 and its rows as well as columns are orthogonal. Th ...
*
Parity function In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function. The parity function is notable for it ...


Notes


References

* * * * * * * *


External links

* * * * {{Authority control Special functions