Walsh-functions: digital alternatives to sinusoidal functions

              
WALSH FUNCTIONS: DIGITAL ALTERNATIVE TO SINUSOIDAL FUNCTIONS
Mister President, Members ofthis Academy, Ladies and Gentlemen:
1t is a real pleasure for me to celebrate with you my election as Corresponding Member of this
Academy. Many thanks
The mathematical concept of sinusoidal functions and its application has a long tradition as
well in science as in engineering. The modeling of planetary orbits by circles and epicycles as
known from Ptolemy are early applications in astronomy. Even Copemicus made use of
epicycles in his heliocentric model of the system of the sun. Arabic astronomy was familiar
with the sinus function and the cosinus function which has been introduced to western
astronomy by Georg von Peuberbach (''Purbachius"). They play an important part in such
models. In physics the investigations of the vibrating string led such famous scientists as
Daniel Bernoulli, Leonhard Euler and Joseph Luis Lagrange to the representation of
vibrations by series of sinusoidal functions. By his work "The Analytical Theory of Heat"
Joseph Fourier founded 1822a part ofthe theory oftrigonometric series which is known today
as the theory of "Fourier series". The final mathematical precision of the theory of Fourier
series was provided by the work of Dirichlet and Riemann. Fourier series expansions of
functions are an important too! of mathematical physics up to the present.
A further kind of application of sinusoidal functions supported the development of electrical
engineering in the ¡ 9th century. Altemating currents can be described by sinusoidal functions.
The same is true for the description of the characteristics of electrical networks in respect of
altemating currents of different frequency. It was introduced by the German mathematician
(later famous scientist in the US), Karl Rudolf Steinmetz (1865-1923), by his famous
"symbolic method" (Komplexe Wechselstromrechnung) in dealing with altemating current
phenomena. An extension of the symbolic method of Steinmetz is the "operational calculus"
as developed by Oliver Heaviside for its application in the electromagnetic theory of electrical
phenomena in a space-time continuum. Until now the Laplace transform, and as a special case
the associated Fourier transform provide a solid mathematical basis for this type of problems
in electrical engineering, control engineering and communication engineering. They allow the
mathematical treatment of problems which are related to functions and operations that deal
with electrical currents, control variables and signals and their transformation or processing in
engineering systems.
Fourier-series expansions and Fourier-integral representations are conducive for the spectral
representation of functions and operations with regard to their frequency-behavior (i.e.) with
respect to their characteristics regarding sinusoidal functions. In ali this kind of applications
87
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
and mathematical models the system of real numbers (as well as the complex number system)
play an important part. Signals and systems process "continuous" variables. In engineering
this is known as an "Analog Technology". Today, in "Digital Technology" the leading
technology in the field of electrical engineering system variables have only discrete values of
finite number. Therefore, integers and finite sets are the main mathematical objects for
modeling digital systems.
Although digital systems look back on a long history in electrical engineering (examples are
given by switching circuits of high voltage power lines and by telephone switching circuits
realized by electromagnetic relais, selectors and crossbar-switches), their actual importance is
a result of the rapid progress of semiconductor-electronics and of computer technology.
Microelectronics and microprocessors are the reason that Digital Technology has dramatically
changed the existing systems. Analog systems have been replaced by digital systems. In this
context the natural question arises, if there exists a system of functions which can perform
similarly for digital systems as sinusoidal functions for analog systems.
The system of Walsh-Functions, which is known in mathematics since 1923, can claim to be
partly useful for digital systems. This paper will try to show this. Special attention will be
given to the pioneering work of H. Harmuth. His contributions to the application of Walsh­functions
in the field of communication engineering (in that early times looking mainly for
realizations by analog technology) are considered ofbig importance until today. In addition to
such historical considerations we will also point to current modem applications of Walsh
functions in mobile telecommunication and in secure information processing.
From a mathematical point of view the fact that Walsh functions have a similar applicability
in modeling signals and systems as sinusoidal function is not so surprising.: Both systems of
functions are special cases of "character functions" of a (topological) abelian group. The
mathematical field of "Abstract Harmonic Analysis" covers man y properties of both function
systems in a more general way and provides a source for additional specific (orthogonal)
function systems of similar use for applications in science and engineering.
2. Mathematical Overview
2.1 Walsh-Functions
We begin with the definition ofthe system ofRademacher-functions (Rademacher 1922).
With r/J : [ü,l)~R we denote a function which is given by rp(x) =l for xE[ü,1/2) and
rp( x) = - 1 for x E [l / 2,1) . On the basis of the function rp we are able to define the system
<l> = ~" : n = 0,1,2, ... } ofRademacher-functions by r/Jn : [ü,l)~R with
(1)
88
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
1 -------------~
O- ----------- ---'--R(0,1)
1 --------
o --------1---------R (l, t)
- 1
1 ---~ -~ L=PL_ R(2,t)
~ 1 n nJJ n n nsi R(4,t)
-1 u u u ero u u e
1 l n Qn n n nJJ o rrn nrrn o n
-~ mru u o Lfu u u u u u u u u L
o
R(5,I)
Figure 1: Rademacher-functions if>0 to if>s
With the help of the system <P of Rademacher-functions the system 'I' = {1¡1" : n = 0,1,2,. .. } of
Walsh-functions r¡t n : (0,1)---+ R is defined by
'l'n(x) := [4'n0 (x))"" [4'.., (x))"• . [if>n, (x)J" (2)
where the integer o is represented by n = n0 2° + n1 21 + ... + n; 2; (Walsh 1923).
Walsh-functions are, as we see, finite products ofRademacher-functions. To give an example,
for n = 2° + 22 (n=5) the Walsh-function 'l's is given by 'l's = 4'0 4'2 •
21-I
')J 110101
'5S 110111
51 ll\001
:,g 111011
61 111 101
soW,9)~ wol(2i-1,9J
63 1 1 1111~::::::::~:.:::::::=::::::::::::::::~~
9-L'T'- a -11T' -
5L ! 10110
S6 111000
58 11 1010
60 11 1100
62 111 110
Figure 2: Walsh-functions r¡t n (o ~ n < 63) in sequency-order and divided into even functions cal(i,.) and odd
functions sal(i,.) on the interval (-1/2, +1/2)
89
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
lt is well known, that the Walsh-functions 'I' constitute a complete orthogonal system for the
Hilbert-space L2 [0,1). Consequently for each square-integrable function f : [0,1) ~ R we
have a Walsh-Fourier representation in the form of
00
f = "f,](n)¡t" (3)
n=O
The coefficients f (n) of (3) define a discrete function J: No~R. f is called the Walsh-
Fourier transform of f. The assignment f H f defines the Walsh-Fourier transformation
WT; WT(f) = f
The field of Abstract Harmonic Analysis establishes in mathematics a general theory for
functions defined on topological groups. In this context Walsh-functions can be identified as
character-functions of the dyadic group D which is defined by the set of 0-1 sequences
{(x1,x2 ,x3 ,. .. ): x, E {0,1}} with the addition modulo 2 (component-wise taken) as group-operation
(Fine 1949, Vilenkin 1947).
For the identification of the Walsh-functions with the character-functions of D we use the
map hin: [0,1) ~ D which maps a real number X = X¡ r 1 + Xz r 2 + X3 r 3 + ... to the binary
sequence bin(x) = (x1,x2 ,x3 ,. .. ) (dyadic rational numbers are represented by a finite sum).
2.2 Sinusoidal Functions
The system of sinusoidal functions sin 27tnx, n=l ,2,3,. .. ; cos 27t nx, n=O, 1,2,... has, as
pointed out in chapter 1, a long tradition in science and engineering. Similarly to the system
of Walsh-functions it is a complete system of orthogonal function to span the Hilbert space
L2 [0,1). Therefore each function f E L2 [0,1) can be represented by a series expansion
(Fourier serie) with coefficients f,(n),n = 1,2,. .. and fcCn),n = 0,1,2,. ...
The tupel Vs ,Je) of discrete functions defined by the coefficients is called the (real) Fourier­transform
off . The assignment f H (i,,JJ defines the (real) Fourier transformation FT ;
FT(f) = (js ,JJ. From a mathematical point of view it is desirable to use the complex
sinusoidal functions exp(j2n nx) = cos2n nx+ )sin 2n nx (j = ~) for Fourier analysis in
the classical sense. In this case the relation between classical Fourier analysis and Abstract
Harmonic Analysis is easy to establish: The complex sinusoidal functions exp(j2n nx) are
the character-functions ofthe additive group <[o,oo),+) ofnon negative real numbers.
90
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
2.3 Finite system of junctions
In a large number of applications of orthogonal functions in science and engineering it is
sufficient to use finite many functions. In the case of Walsh-functions we take as domain the
set N(n)= ~,1,2, ... ,2" - 1} of integers and define the discrete Walsh-functions
w(i,.):N(n)~{+ 1,-1} oforder n for iEN(n) by
w(i, k) := (- 1) llbin(iJ e bin(kJll (4)
where bin(i) and bin(k) denote the binary representation ofthe integers i and k, respectively
(EB is the ,,addition modulo 2" of binary numbers, jjbjj is the Hamming weight of a binary
number b ).
The set W.(·3) of discrete Walsh functions; + := + 1, - := - l.
000 001 010 011 100 101 110 111
w(O, .) + + + + + + + +
w(l, .) + + + +
w(2, .) + + + +
w(3, .) + + + +
w(4, .) + + + +
w(5, .) + + + +
w(6, .) + + + +
w(7, .) + + + +
Figure 3: Discrele Walsh-functions w(i,.) for n=3
The system W(n) ofdiscrete Walsh-functions oforder n can be identified with the character­functions
of the dyadic group D(n)=(Bº,EB), where B(n) denotes the set of binary numbers of
length n. D(n) is isomorphic to the n-fold direct product Z2 ® Z2 ®·· ·® Z2 of the cyclic
group Z2 = ({O,llEB)
The system S(n) consisting of discrete complex sinusoidal functions s(i,.) of order n are
defined by
s(i,k) := exp(j(2n / n)ik) (5)
It is known that the discrete complex sinusoidal functions of order n can be identified as
character functions of the cyclic group Zn=( {O, 1,2, ... ,n-1}, + mod n) .
Besides ofthe Walsh-functions lf. originally introduced into mathematics by Walsh (1923)
there exist also "generalized" Walsh-functions as considered by Levy (1944) and Vilenkin
(1947).
91
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Generalized discrete Walsh-functions in this sense can be identified with the character­functions
of finite abelian groups G = Z t(I) 0 Z tc2> 0 ... 0 Z t<n> (here Z te;> denotes the cyclic
group of order n). For the special cases G = Z" and G = Z2 0Z2 0 ... 0Z2 (n-fold) the
generalized discrete Walsh-functions become discrete sinusoidal functions of order n and
respectively discrete Walsh-functions of order n. By this interpretation, generalized discrete
Walsh-functions can also be considered as n-dimensional discrete sinusoidal functions of
order k(l), k(2), ... , respectively k(n). Consequently, discrete Walsh-functions w(i,.) oforder n
can then be interpreted as n-dimensional discrete sinusoidal functions s(i,.) = exp(j7Zi(.) of
order 2.
This viewpoint helps to consider generalized discrete Walsh functions and (ordinary) discrete
Walsh functions not as exotic mathematical constructions but to be closely related to the
( classical) discrete sinusoidal functions.
2.5 Fast Transform Algorithms
For the case of discrete sinusoidal functions s(i,.) of order n the development of a fast
algorithm, the "Fast Fourier Transform" algorithm FFT, to implement the Fourier
transfonnation FT is credited to Good (1958) and Cooley-Tukey (1965).
A similar effective algorithm to implement the discrete Walsh-transformation WT of order n
has been found by Whelchel (1968) ("Fast Walsh Transform" algorithm; FWT)
For the case ofthe generalized discrete Walsh functions the development ofthe corresponding
"Fast Generalized Walsh Transform" algorithm (FGWT) to implement effectively the
generalized Walsh transformation GWT has been discovered by Nicholson (1971).
The implementation ofthe FGWT is covered by,Kunz (1977) and also by Fellner (1982) .
Hellwagner (1988) investigated problems oftestability ofsystolic hardware-implementation
ofthe FGWT ; the integration ofthe FGWT into common tools for digital image processing
has been made by Hellwagner (1990) and also by Scharinger (1995).
3. Application in Coding and Signa) Processing
Discrete Walsh-function have a rather long tradition with regard to their application in the
fields of coding and signa) processing. We will give few examples:
(1) Let W(n) denote the matrix which is defined by the system W(n) of discrete Walsh
functions of order n in the following way:
92
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
For iEN(n) the i'th row of W(n) is given byw(i,.) = (w(i,O), w(i,l), ... , w(i,2" - 1)) .
W(n) is a special kind of a Hadamard-matrix. The rows define an orthogonal code
(Walsh-code) which has been applied in early space mission projects (Viterbi 1964). A
reason for a successful application was the fact that this code allows the development
of effective digital circuits for coding and decoding (Green 1958).
(2) The cancellation of the first row and the first column of the matrix W(n) results in a
matrix C which defines an orthogonal code of length 2" -1 . It can be shown that there
exist permutations P of the columns of C such that the permuted matrix M=P(C)
constitutes a cyclic orthogonal code which can be generated by a maximum length
linear feedback shiftregister MLFSR. This indicates that a relationship between
"Walsh-codes" and ''Pseudo Noise Codes" (which are cyclic codes generated by
MLFSR's) can be established.
(3) The existence ofthe Fast Walsh transformation algorithm FWT was essential for the
applications of Walsh-function in signa! processing. Pioneering work on that topic is
reported in Ahmed-Rao (1975). The concept of a wave-filter which operates in the
domain ofthe Walsh-Fouriertransform was firstly introduced by Harmuth (1964). The
accompanying description of such filters by dyadic convolution was established by
Pichler (1968). The theory of optimization of such filters (Pichler 1970) needed the
introduction of the concept of the dyadic autocorrelation function (DAKF) and the
formulation of the Wiener-Chinchin theorem for the case of Walsh-Fourier analysis.
In the context of dyadic filtering it was necessary to introduce the "sampling theorem"
of Walsh-Fourier analysis, as a true analogon to the famous sampling theorem of
Shannon (Pichler 1970).
( 4) The possibility to relate different spectral representations to each other is of special
interest in signa! processing. A transformation for discrete-time processes which
relates Fourier power-spectra into Walsh power-spectra has been investigated and
implemented by Gibbs-Gebbie (1969). Besides of the use of the existing
transformations between power spectra and the appropriate related type of
autocorrelation function (Wiener-Chinchin theorems) the transformation of such
autocorrelation functions into each other had to be developed (Gibbs-Pichler 1971 ).
(5) The comparison of Fourier spectra and Walsh spectra for certain signals is of great
significance in applied sciences. As an example we mention here (Trappl-Hom­Rappelsberger
1982).
Although the mentioned examples of signa! processing based on concepts of Walsh Harmonic
93
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Analysis <leal with applications to analog signals, they are also true for digital signals and
indicate the applicability of Walsh functions in digital signa! processing. Other specific
applications of Walsh functions in digital technology, specially, for the design of boolean
functions (switching functions) and their characterization with respect to fault detection, has
been known for a long time (Karpovsky 1976, 1985).
4. Transmission of lnformation by Orthogonal Functions: The contribution of H.
Harmuth
The successful promotion for the application of Walsh functions in communications
engineering is due to Henning F. Harmuth, as well as the contribution of important papers
during the years from 1960 to 1970 and of his book (Harmuth 1971). In the following we
want to refer to sorne of the treatises as experienced by the author during his cooperation with
H. Harmuth.
Harmuth started with discovering the Walsh functions as a useful orthogonal code and their
application in wireless communication (Harmuth 1960). This was followed by a patent of the
concept of a multi-channel transmission system with Walsh functions as carriers (Harmuth
1964). Harmuth considered mainly - with respect to the state of the art at this time - analog
transmission systems with time-continuous signals to represent information.
To develop a valid mathematical basis for such systems Harmuth contacted the Institute of
Mathematics of the University of Innsbruck, Austria, where mathematical research in Walsh
function was under way (R. Liedl, P. Weiss). The contribution of the author (Pichler 1967,
1968, 1970) helped to give a mathematical and systemstheoretical basis for the work of
Harmuth. The symposia which were organized by Harmuth in Washington D. C. (from 1969
on) roused intemational interest. They reported about applications in information technology
and inspired further research. As a result Walsh functions and their applications are today well
known in communication engineering and in signa! processing. They have found important
applications in modem digital information technology. As a conclusion we may say, that
Henning F. Harmuth established a milestone in the development ofinformation technology by
his work on the application ofWalsh functions asan altemative to sinusoidal functions.
94
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Transmitter Rece1ver
Channel no. Line Channe! no.
32
33
992
1024
T 33- T 64
LL --__¡- FG
Sync. ~· ------~
Figure 4: Block diagram of a sequency-multiplex system for 1024 analog telephony channels
(after H.F. Hannulh)
5. Current Applications
32
33
992
1024
In the following we want to discuss three examples of actual applications of Walsh-functions
in the field of coding and signal processing. They should serve to show that this system of
orthogonal functions which was introduced in mathematics more than seventy years ago is
until today of practica! importance.
5.1 Multiplexing in digital wireless communication
Cellular wireless communication systems with mobile stations are nowadays an important
component for modem digital systems for telephony and data. The concentration of the
traffic from the mobile stations to the base stations in the different cells needs a
multiplexing system. Aside from the utilization of frequency division (FDMA systems)
and time division (TDMA systems) orthogonal division, as introduced by Harmuth (1964)
is used (CDMA systems; CDMA stands for "Code Division Multiple Access"). The
specific CDMA system of Qualcomm Inc. uses for the forward link channels Walsh
functions as digital carriers (Qualcomm Inc. 1992). The concentration of channel traffic
by sequency-multiplexing for an analog telephone exchange was already suggested in
Pichler ( 1967).
95
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
WO l·Channd Pllot PN Sequenoe
Pllot Ola.nnel: AJICYs
Sync Channel ConvoluUonal º'" "'°"' 1~ Encoderand lnterlesver
1200 bp•
Repct!Uon
Pagine Channel ConvoluUonal Blocl<
ºª" Enoodttand
lnltt'le.ver
9.6 kbp.
RepeUUon
4.8 kbpi
2.4 kbpl
LoncCod<
Cencnt.or
Forwv.rd 'f't""affic Channd ConvoJuUonal Dota Encoderand """"
lnlt'r\c&VU
9.6 kbpa
RepetlUOn
.4..8. .k.b.p..a 1.2 kbpt LoncCod<
°"""''"' <!}Modulo l addtuon
Q-Channel Pllot PN Sequence
Figure 5: Sequency-multiplex system for 62 digital mobile telephony channels
(after Qualcomm Inc. 1992)
W = Walsh Symbol Number
FORWARD COMA CHANNEL
(1 .23 MHz radio channel
transmltted by base statlon)
Fon.uard CD.MA Channels Transmitted by a Base Station. In addition
to the pUot and sync channels. theforward link in each sector supports 62
channels that may be usedfor paging and traffic. Zero to seven channels
are assigned to paging. the remainder are tra.ffic channels.
Figure 6: Organization offorward channels in the COMA system of Qualcomm (1992)
5.2 Correlation-immune coupling ofpseudo-noise sequences
Secure transmission of information by digital data can be achieved by mixing the data
sequence with a random sequence (key sequence). Claude Shannon has shown that
"stream ciphering" is cryptographically absolutely secure if the key sequence is purely
96
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
random and is used only once ("one time key system"). Since the key sequence has also to
be applied for demixing at the receiver station, an effective realization of stream ciphering
has to be based on pseudo random noise generation by a finite state machine PNG
(Pseudo-Noise Generator). To achieve an high degree of security the key sequences
generated by a PNG has to approximate pure random noise in a "cryptographic best
manner".
In practice, to get a cryptographic strong PNG, n sequences of x1,x2 , ••• ,x" of weak
quality are coupled by a certain operation C (the combiner) to result in a strong key
sequence y= C(xP x2 , ••• , x"). In the case of binary sequences a (static) combiner C can
be represented by an Boolean function C:Bº---+B.
PN1
PN2
e pn
pnk
Kk
PNk
Pl'li : Pseudo Noin 0.nentor
C:Conüner
Figure 7: Architecture of a Pseudo Random Noise Generator PNG with Combiner C
The cryptological quality of a pseudo random noise sequence has to be determined by
different statistical tests. Such tests relate to certain attacks to break the system. For PNG
with an architecture according to Fig. 7 the so called correlation attack tries to identify the
individual "weak" sequences x1,x2 , .•. ,x" from observing the key sequence
y = C(x1,x2 , . .. ,x") by a "divide and conquer" method using statistical tests and computer
simulation. A PNG is robust with respect to the correlation attack if the combiner C
possesses a certain degree of "correlation immunity". For boolean combiners C the
following theorem was proved by Xiao-Massey (1985): A boolean combiner C:Bº---+B is
correlation immune of degree m if and only if the Walsh transform WT(C) of C has the
following spectral property:
WT(C)(x)=O for ali x with O ~ llxll ~ m <llxll denotes the Hamming weight of x; we identify
Bº with N(n)).
97
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Siegenthaler (1986) showed by algebraic methods how a boolean combiner C ofsufficient
high degree of correlation immunity can be constructed. Pichler (1985) established such a
construction by means of Walsh-Fourier analysis. An extension of these results for
(dynamic) combiners C realized by state machines with finite memory can be found in
Pichler (1988). As a further recent publication to the topic of Boolean combiner design
uses the Walsh transform we refer to Dobertin (1995).
5.3 Sequency-Hopping
The fundamental idea of the method of frequency hopping to achieve a secure
communication by a wireless system is, that the carrier frequency of the transmitter and
the receiver changes in time using a pseudo random pattem. lt "hops" within a certain
(broad) frequency band. The Austro-american actress and movie star Hedy Lamarr (born
Hedy Kiesler) known as the "most beautiful woman of the world", is considered together
with George Antheil ("bad boy or" music") as the inventor of frequency hopping (US
patent 2,292.387 of 1942). Following Harmuth (1971) we can replace the parameter
"frequency" by "sequency" if we use a communication system based on Walsh functions
as carrier. In this case "sequency hopping" is a method for secure information
transmission. As a further generalization "code-hopping" can be introduced, when we use
arbitrary orthogonal code sequences as carriers. A research project for the development of
a code-hopping system in combination with a direct sequence CDMA system is currently
under investigation (Pichler-Scharinger-Schütt 2000).
RF
Modulation
Sequency
5ynthesl.zer
pn
Pseudonoise
Generator
""111111111111 ¡
RF
Demodulatio
!Jls +n
COrrelatk>n
ReceiYer
pn
Pseudonoise
Generator
Figure 8: Block diagram of a digital system for secure information transmission by sequency hopping
98
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
6. Concluding Remarks
The paper tries to present a survey of the history of the development of the application of
Walsh functions in signa! processing and communication engineering. The goal was to show
that Walsh functions and the method of Walsh-Fourier transformation can be used for digital
systems in a similar way as the sinusoidal functions are used for analog systems. From a
mathematical point ofview this is not surprising: Both function systems are as we pointed out
earlier, special cases of character functions of a topological group and the existing general
method of F ourier transformation covers essential parts of the specific methods of the Walsh
transformation and respectively the Fourier transformation. An example is given by the
sampling theorem in signa! processing. Kluvanec (1965) showed the validity of this theorem
in abstract harmonic analysis, special cases of it for dyadic harmonic analysis and for real
harmonic analysis are known from Pichler (1970) and Shannon (1948).
The application of Walsh functions and related concepts in modeling systems for signa!
processing and communication were - according to the state of art - originally developed for
the case of analog information technology. Their realization used basic elements like resistors,
coils, capacitors, operation amplifiers and sampling and hold circuits. The introduction of
digital information technology, specifically the development of integrated microelectronic
circuits, microprocessors and computers, required new approaches for modeling. For the
processing of digital signals by digital systems new concepts and methods for dealing with
hardware and software had to be developed. Examples for the case of hardware are the
development of the theory of switching functions (boolean functions) and the theory of
sequential switching circuits (finite automata). The different concepts and methods for analog
signa! processing and analog information transmission which exist for Walsh functions can be
adapted to digital system by restriction to the set W(n) of discrete Walsh functions of order n.
This is analogous to the approach of adapting concepts and methods of analog signa!
processing (for example by digital filters) by the use of the system S(n) of discrete sinusoidal
functions of finite order.
The development of communication systems is in a steady competition between the
requirements stated by the customers and the architectural and technical propositions made by
the designers and engineers to realize such systems by the current existing basic technology.
In this development mathematical and systemstheoretical models are of great importance.
Walsh functions and related mathematical and systemstheoretical results can contribute to the
construction of models for modem digital communication systems.
99
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
References
Ahmed, N., K.R. Rao: Orthogonal Transforms for Digital Signal Processing. Springer Verlag
Berlin-Heidelberg-New York, 1975.
Cooley, J. W. and J. W. Tukey: An Algorithm for the Machine Calculation of Complex
Fourier Series. Math. Computation 19 (1965), pp. 297-301
Dobertin, Hans: Construction of Bent Functions and Balanced Boolean Functions with High
Nonlinearity. in: Fast Software Encryption (Bart Preneel (ed.)), Lecture Notes in
Computer Science, Vol 1008, Springer-Verlag Heidelberg, 1995, pp. 61-74.
Fellner, H.: Realisierung der allgemeinen Faltung durch die schnelle verallgemeinerte
Fouriertransformation. master thesis, Institut für Systemwissenschaften, Universitát Linz,
January 1982
Fine, N. J.: On the Walsh Functions. Trans. of the Amer. Math. Society, Vol 65, 1949, pp.
372-414.
Gibbs, J. E. and H. A. Gebbie: The application ofWalsh functions to transform-spectroscopy.
Nature, London, Vol. 224, 1969, pp. 1012-1013.
Gibbs, J. E. and F. R. Pichler: Comments on Transformation of"Fourier" Power Spectra into
"Walsh" Power Spectra. in: 1971 Proceedings Application of Walsh Functions, AD 727
000, Naval Research Lab., IEEE-EMC Group, University ofMaryland, Washington D.C.,
1971, pp. 51-54.
Good, l. J.: The interaction algorithm and practical Fourier-analysis. Joumal of the Royal
Statistical Society, Vol. B20, 1958, pp. 361-372.
Green, J. and R. San Soucie: An Error-Correcting Encoder and Decoder of High Efficiency
Proc. IRE, 46 (1958), 1741-44.
Harmuth, H.: Grundzüge einer Filtertheorie für die Máanderfunktionen A. (e) . Archiv elektr.
Übertragung 18 (1964), 544-554.
Harmuth, H. F.: Radio Communication with orthogonal time functions. Transactions AJEE.
Communications and Electronics 79, 1960, pp. 221-228.
Harmuth, H. F.: Die Orthogonalteilung als Verallgemeinerung der Zeit- und Frequenzteilung.
Archiv elektr. Übertragung, 18 (1964), 43-50.
Harmuth, H. F.: Transmission oflnformation by Orthogonal Functions. Springer-Verlag New
York, 1971 (2"d edition).
Hellwagner, H.: Systolische Architekturen für die Verallgemeinerte Diskrete Fourier­Transformation.
PhD thesis. Universitát Linz, Institut für Systemwissenschaften, Sept.
1988.
Hellwagner, H.: CAST.FOURIER - An interactive Method Bank for Generalized Spectral
Techniques. in: Computer Aided Systems Theory - Eurocast'89, Las Palmas, Feb/March
1989 (eds. F. Pichler, R. Moreno-Diaz), Lecture Notes in Computer Science 410, Springer
Verlag Heidelberg, pp. 355-366, 1990.
Karpovsky, M. G. : Finite Orthogonal Series in the Design of Digital Devices. John
Wiley&Sons, New York, 1976.
Karpovsky, M. G. (ed.): Spectral Techniques and Fault Detection. Academic Press, Orlando,
1985.
Kluvanec, l.: Sampling theorem in abstract harmonic analysis. Matematicko fyzikalny
Casopisa, Sloven. Akad. Vied. 15 (1965), pp. 43-48.
Klinz, H.: Approximation optimaler linearer Transformationen durch eine Klasse schneller,
verallgemeinerter Fourier-Transformationen. Diss. ETH. Juris Zürich, 1977.
Levy, P.: Sur une generalisation des fonctions orthogonales de M. Rademacher. Comment.
Math. Helv. 16 (1944), pp. 146-152.
Nicholson, P. J.: Algebraic Theory of Finite Fourier Transforms. J. of Comp. and Systems
Science 5 (1971), pp. 524-547.
100
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Pichler, F.: Das Sequenzvielfach, ein neues Sprechwegenetzwerk für vollelektronische
Fernsprechvermittlungsamter. XII. lnternat. Wissenschaftl. Kolloquium, Heft 7,
Nachrichtentheorie und - technik, Teil II. TH llmenau, pp. 15-20, 1967.
Pichler, F.: Synthese linearer periodisch zeitvariabler Filter mit vorgeschriebenem
Sequenzverhalten. Archiv elektr. Übertragung 22 (1968), 150-161.
Pichler, F.: Walsh-Fourier Synthese optimaler Filter. Archiv elektr. Übertragung 24 (1970),
350-360.
Pichler, F.: Walsh functions and Linear Systems Theory. Techn. Report, Department of
Electrical Engineering, University ofMaryland, Washington D.C., Appendix B-1 to B-11,
Sampling Theorem with Respect to Walsh-Fourier Analysis, April 1970
Pichler, F.: Zur Charakterisierung korrelations-immuner Schaltfunktionen mittels Walsh­Fourieranalyse.
Techn. Bericht, Institut für Systemwissenschaften, Universitat Linz, 1986
and
,,On the Walsh-Fourier Analysis of correlation-immune switching functions". in:
Abstracts ofpapers, EUROCRYPT'86, Linkoping, May 20-22, 1986, 4.5 A.
Pichler, F.: Konstruktion korrelationsimmuner Schaltfunktionen und Schaltwerke mittels
Walsh-Fourieranalyse. in: Contributions to General Algebra 6 (G. Pilz, ed.), Verlag
Holder-Pichler-Tempsky, Wien 1988. pp. 213-222.
Pichler, F., J. Scharinger, D. Schütt: Digitales Vielkanal CDMA Code-Hopping
Übertragungssystem. Technischer Bericht, lnstitut für Systemwissenschaften, Universitat
Linz, 10 pages, December 2000.
Qualcomm Inc.: An Overview ofthe Application ofCode Division Multiple Access (CDMA)
to Digital Cellular Systems and Personal Cellular Networks. Document Number EX60-
100 l O. QUALCOMM Incorporated 1992, USA.
Rademacher, H.: Einige Satze von allgemeinen Orthogonalfunktionen. Math. Annalen 87
( 1922), 122-1 38.
Scharinger J.: lntegration of various spectral transforms into KBVision. Technical report,
lnstitute of Systems Science, Johannes Kepler University Linz, Austria, 1995.
Siegenthaler, Thomas: Methoden für den Entwurf von Stream Cipher Systemen. Diss. ETH
Nr 8185, ADAG Administration Druck AG, Zürich, 1986.
Trappl, R., W. Hom and P. Rappelsberger: Fast Walsh versus Fast Fourier Transform: A
Comparison in the Analysis of Seizure EEG. in: Progress in Cybernetics and Systems
Research (R. Trappl, L. Ricciardi, G. Pask eds.), Hemisphere Publishing Corporation,
Washington D.C., 1982, pp. 97-102.
Vilenkin, N. J.: On a class of complete orthogonal systems. (in russian). lzv. AN, SSSR,
ser.matem.11 (1947, pp. 363-400.
Viterbi, A.J.: Phase-Coherent Communication over the Continuous Gaussian Channel. in:
Digital Communications with Space Applications (ed. Solomon W. Golomb), Prentice
Hall, Englewood Cliffs, N.J., 1964, chapter 7.
Walsh, J.: A closed set of orthogonal functions. Amer. J. ofMathematics 45(1923), pp. 5-24.
Whelchel, J. E. and Guinn. D. F.: The fast Fourier-Hadamard transform and its use in signa!
representation and classification. Techn. Report. PRC 68-11. Melpar Inc. Falls Church, Va
22046, 1968.
101