A NEW EXPRESSION FOR WALSH FUNCTIONS-THE COMPLETION 0F RADEMACHER FUNCTIONS

(1)

Bull. Kyushu Inst. Tech.

(M, & N. S.) No. 21, 1974

By

Teiji OHTA

1. Introduction

Recently, much attention has been given to the practical application of Walsh functions to digital signal processing and transmission. This set of orthogonal functions has been identified as presently the most important non-sinusoidal functions in various digital signal-processing applications. Walsh functions were introduced by Walsh in the form of recurrence formulas [1], Paley has shown that they may be defined as products of Rademacher functions [2]. In fact, they are a completion of Rademacher functions. A number of articles on the definition of Walsh functions have been published [3]-[5]. Of particular interest is the definition by Harmuth [6], His definition is equivalent to that of Walsh. However, the introduction of the concept of sequency has contributed greatly to the practical application of Walsh functions. Historically, since Joseph Fourier introduced them, Fourier series consisting of sine and cosine functions have been a very powerful tool in representing periodic functions in terms of a simple periodic basis. As a consequence of this fact, it is natural to ask whether a square-integrable function may be expanded as a linear combination of two- valued rectangular functions which, provided they are periodic, change signs at equal distances and are anti-symmetric with respect to a point of discontinuity . This paper develops a new method for the completion of Rademacher functions by introducing RB-functions, and gives an answer to that question. RB-functions•

are obtained by shifting Rademacher funetions along the t-axis and introducing Ro(t) =1.

This paper is organized as follows. In Section 2 we first present the definit-

ions of the well-known Haar, Rademacher, and Walsh functions. We next intro- duce functions r.(r, t) which are obtained by replacing t by t-T in Rademacher functions r.(t).

The shift T enters r.(r,t) as a parameter and r.(O,t) is equal to r.(t). Further- more, R.(r, t) is obtained from r.(T, t) by imposing restriction on the value of r.

In Section 3 we define the problem and outline the method of attack. Following these introductory remarks, the proof of Theorem 1 is precisely sketched; it is the main objective of this paper. Considerable work will be done on the proof

(2)

of Theorem 1. Finding the actual expansion of Walsh functions in terms of RB- functions is the subject of Section 4 where knowledge of the points of discontinuity leads to an efficientmethod of derivingthem. The resulting expansion of the first 31 sequency-ordered Walsh functions is listed. Section 5 is devoted to the derivation of various formulas which suggest the properties of RB-functions.

Among these are 1) Fourier series representation for RB-functions and related functions, 2) orthogonality relations for these functions, and 3)theproperties of the graphs of these functions. Section 6 discusses the important properties of RB-functions. The discussion is aimed at showing the great similarity between RB-functions and trigonometric functions. The paper concludes in Section 7 with a few remarks indicating the need for future development.

2. DefinitionsandNotations

This section lists the definitions and notations of well-known Haar, Rade- macher, and Wa]sh functions which are needed hereafter in the body of the paper and gives the definitions of several new functions.

A. The Defonitions of HaaT, RademacheT, and VVal$h 17unetions

The definitions and notations of these functions are quite the same as those appearing in their original papers [1], [7], [8]. Note that all the functions are left undefined at the points of discontinuity.

1) Haar functions

x6o)(t)=1, oÅqtÅq1

( V2-n, (2k - 2)/2n'i Åq tÅq (2k - 1)/2n'i xEk'(t) == i -V2i., (2k-1)/2n+iÅqtÅq2k/2n+i

k O, OÅqtÅq (2k -- 2)/2n+i, 2k/2n+iÅqtÅq1, k== 1, 2, 3f••, 2n

n=O, 1, 2,••• (1)

2) Rademacher functions

- ,,(,)=i l• OÅqtÅq1/2

(-- 1, 1/2ÅqtÅq1

,.(t) ,,. 1"n-i(2t), OÅqtÅq 1/2

(r.-i(2t-1), 1/2 ÅqtÅq 1, n= 2, 3, 4,••• (2)

(3)

A New Expression for Walsh Functions-the Completion of Rademacher Functions 69

3) Walsh functions Åëo(t) == 1, OÅqtÅq1

,,(t):I-ll 2fi,L/i

Åë2ÅqiÅr(t)==I-ll 9fi,L/gÅr2/4ÅqtÅqi

Åës2)(t)-I.--l] 9fi,L/iÅrS/,Z,Åq,':,!/l

Åëh2le-i)(t)-I9ile-'lg2,tbu,,,,,-,,, g,Åq,`:,i(2, z-z.g•,z•,z•, •2"-2

Åëh2kÅr(,).,I9ik-'l12,th,,(,,.-,), O,/Åqi.Åq,i./2,, (,)

B. The DeLfinition of Seq2Leney-OnteTeel Walsh 17unetions in the Open interval (O, 1)

As is well-known, Walsh functions are also be defined by using parameter i, which represents the number of sign chenges in (0, 1) and i which is called sequency. Although usual sequency-ordered Walsh functions have been defined in the interval (- oo, + oo) and are assumed identically zero outside the half-

open interval [-1/2, +1/2), we need the definition of them in the open interval (O, 1) since we shall use Haar functions defined in (O, 1) in proving Theorem 1.

toal(i, t) are defined by

t toai(O, t) == Åëo(t), J' =o i-val(i,t) = i toal(1, t)= Åëi(t), 1' =1

toaZ(1', t) == ÅëÅíle'(s), 1'=2"-i+k-1 År- 2. (4)

Furthermore, ,gal(i, t) and eal(i, t) are defined by s-al(1, t) =Åëi(t)

s-al(i, t)=ÅëÅík)(t), i-- 2n-2+k/2, k is even.

eal(i, t)=Åëhk'(t), i=2nL-2+(k-1)/2, k is odd.

(4)

n=2, 3, 4,•••

k =1, 2,•••, 2n-!

i--- 1, 2, 3,•••

7' -- O, 1, 2,•••. (5)

The recurrence formulas for the sequency-ordered Walsh functions are given by

ival(O, t) = Åëo(t) s-al(1, t)= Åëi(t) eal(1, t) == ÅëS" (t)

,gal(2L, t)=ISal(L' 2t), oÅqtÅq1/2

(s-'al(L, 2t -- 1), 1/2ÅqtÅq1 e.i(2L, t)=leai(L, t), oÅqtÅqi/2 teal(L, 2t-1), 1/2ÅqtÅq1

s.i(2L+i, t)=ljai(L, 2t), oÅqtÅqi/2 (- eal(L, 2t -- 1), 1/2 ÅqtÅq1 c-ai (2L+i, t) ,,. IS-"i(L+i, 2t), oÅqtÅq i/2 (-s-al(L+1,2t-1), 1/2ÅqtÅq1,

L=1, 2, 3,•••, (6)

It should be noted that cbal(i, t), s'al(i, t), and c-al(i, t) are equivalent to wal(i, t), sal(i, t), and cal(i, t), respectively, which are given by Harmuth, except that the former is defined in the open interval (O, 1). Therefore, to avoid con- fusion, the former has the symbol "-U on their notations.

C. The Definition of RB-ii'unctions

Although Rademacher functions are defined in the interval (O, 1) in this section-A, they are assumed to be periodic of period 1 in the interval (- oo, + oo) in the following.

DeLfinition 1: Let r.(t) be a periodic Rademacher function such that r.(t + T) = r.(t)

for any integer T, where - oo ÅqtÅq+ oo,

(5)

A New Expression for Walsh Functions-the Comp!etion of Rademacher Functions 71

Then we define r.(c, t)as

rn(r, t) =rn(t - r)

where - oo ÅqrÅq + oo, and OÅqtÅq1. The value of T will be restricted later. Thus, r.(r, t) is obtained by shifting a periodic Rademacher function along the t-axis by the quantity r, and therefore is called the shifted Rademacher function.

Definition 2: We next define the function Ro(t) as Ro(t) = 1

where OÅqtÅq1.

Since a periodical Rademacher function has the property rn(t) == -- rn(t - 1/2n),

the following relation holds for r,,(v, t).

r.(1/2't+r, t) :-r.(r, t) (7)

This leads to the following lemma.

Lemma: For given r.(T, t) with rÅqO or T;}il/2", there exists r.(Tr, t)with Os:r'Åq1/2" such that r.(T, t)=Cr.(ri, t) where Cis either +1 or -1. This lemma permits us to limit the value of r such that OsrÅq 1/2" for r.(T, t) without loss of generality.

Furthermore, we impose the restriction on the value of T.

DeLfinttion 3: For given r.(r, t), let T be either zero or odd multiples of 1/2,n and less than 1/2", and let r.(r, t) with such ris be denoted by R.(T, t) where m=1, 2, 3,•••. Then we call R.(r, t) together with Ro(t) rectangular basis functions which are written as simply RB-function. Conversely, for given m, T satisfying the above restriction and except zero are contained in R.(r, t), n == 1, 2, 3,•••, m.

3, Possibility of Expanding Walsh Functions in Terms of RB-Functions The main objective of this paper is to give an answer to the question as to whether a square-integrable funetion may be expanded in terms of rectangular functions whose values are only +1 and -1 and whose points of discontinuity are equally spaced. An example of such functions are Rademacher functions.

On the other hand, a square-integrable function can always be expanded in terms of orthogonal functions of a complete system in the sense of minimizing the mean square error, Therefore, if all of the functions of a complete set are expressible as a linear combination of a finite number of such rectangular func-

(6)

tions, the answer to the question is affirmative. In the latter half of this section, RB-functions will be recognized as such rectangular functions. During the proof of Theorem 1, considerable work will be done on the expansion of RB- functions in terms of orthogonal functions. Among many complete system, we adopt the Haar system of orthogonal functions, An advantage to this systemis that the coefficients in the expantion of RB-functions are easily obtained since the Haar functions are the same rectangular functions as RB-functions and have simpler form than Walsh functions.

The approach to the problem above consists of the following steps.

1) Expand RB-functions in terms of Haar functions.

2) The resultingexpressions are viewed as a system of simultaneous equations in Haar functions.

3) Express Haar functions as a linear combination of a finite number of RB- functions by solving the system. The solution will always exist and will be .unlque.

Since the integrands appearing in this paper are two-valued rectangular functions, integrations will be easily performed with the aid of graphs. There- fore, the process of calculations will not be shown in order to save space.

A. Expuansion of r.(r, t) in TeTms of HaaT li'unctions

We begin by showing the following two relations, which hold for r.(c, t).

a) Clearly,

j:z60'(t)r.(t, t) at == O, n== 1, 2, 3,•i-. (8)

This suggests that the expansion of r.(T, t) does not contain x60'(t).

b) Next it can be shown that

j:xJ•k'(t)r.+i(r, t) dt == O, iÅq. m-1, m=:1, 2, 3,•••, (9) This suggests that the expansion of r..i(T, t) does not contain x;•k'(t), 1' Åq- nz-1,

k == 1, 2,•••, 2j.

From these two relations, we conclude that the resulting expansion of r.(T, t) takes the following form

2i'

r.(r, t)==.Z Z C.,,•,kx;-k'(t) (10)

J= m-1 k== 1

where C.,j,k represents the expansion coefl}cients of r.(r, t) with respectto Haar functions. This result shows that xhkli(t), k =1, 2,t••, 2m-i are contained in the expansion of r.(r, t), n=1, 2,•••, m.

(7)

A New Expression for Walsh Functions-the Complction of Rademacher Functions 73

It should be noted that till now on restriction on the value of v were imposed. However, from now on, the restriction of definition 3 will be imposed.

c) Let G. denote the group of RB-functions whose T are odd multiples of 1/2m, m== 1, 2, 3,•••. When r is equal to the upper bound of r, namely, 1/2n, we put r== O. In such a G., R.(r, t), n= 1, 2,-•-, nL are contained. The groups and their members are listed in Table I. In the remainder of this section, we will be principally interested in the problem of expanding RB-function in terms of Haar functions.

G, R,(O, t)

G, R,(O, t) R,(1/4, t)

G, R,(O, t) R,(1/8, t) R,(1/8, t) R,(3/8, t) G, R,(O, t) R,(1/16, t) R,(1/16, t) R,(3/16, t)

R,(1/16, t) R,(3/16, t) R,(5/16, t) R,(7/16, t) Gm Rm(O,t)

R.-i(1/2M, t)

R.-2(1/2M, t) R.-2(3/2M, t)

R,(1/2M, t) R,(3/2m, t)... R,((2m-2-1)/2m, t) R,(1/2M, t) -R,(3/2m, t)... R,((2m-i -- 1)/2m, t)

Table I. The groups and their members,

If we restrict the value of r in the above manner, then the following relation is obtained whieh holds for R.(T, t) belonging to G..

S:x;k'(t)R.(T, t) dt == O, m :1, 2, 3,•••

1'År-m k== 1, 2,'s', 2j

n=1, 2,t••, m, (11)

From this it is concluded that z;k'(t), 1' År- m, k=1, 2,•-•, 2j do not appear in the expansion of R.(r, t) belonging to G..

Combining the results a), b), and c) gives the expansion of RB-functions belonging to G. as

(8)

m-1 2j

Rn (r, t) =: . Z Z C., ., w•,kx;• k' (t), nL = 1, 2, 3,•• ny

j=n-1h=1

n=1, 2,••t, m

r= 1/2m, 3/2m,•••, (2m-n--1)/2m. (12)

d) The expansion (12) implies that x;-le'(t), iÅr-ntm-1, k=1, 2,•••, 2j are orthogonal to R.(T, t) belonging to G..i, m=2, 3, 4,t••, Therefore, xhleLi(t), k =1, 2,•••, 2m-i are contained in the expansion of R.(r, t) belonging to Gi, iÅr-m. At this stage, let us examine the orthogonality relation between xhkLi(t), k = 1, 2,•••, 2m-i and R.(T, t) belonging to G.. To compute it, arrange xhkLi(t) and R.(r, t) as shown in Table II where R.(T,t) are listed in the first column. The number of rows is 2m"i-i and there are 2i Haar functions xhkLi(t) in one row. This table is intended as a guide to computing orthogonality relation eMciently.

Rt(r, t) xhk),(t)

Ri(1/2M, t) zhi!,(t) xh2-M,-i-'i+i)(t) xh2.M,dt+i)(t) ... xhi.+im-i-2m-i-i)(t) Ri(3/2M, t) xh2!i(t) xh2-M,-`-i+2)(t) xh2-Mi`+2)(t) ... xh2-+im-L2m-e"i)(t) Ri(5/2M, t) xh3L,(t) xh2"M,"`-i+3)(t) zh2-Mft',3)(t) ... xh3i,2m-i-2m-i-i)(t) R,(2m-i/2m, t) zfu2-MiiMi)(t) xh2ntM,-i•År(t) xh3:iM"t-i)(t) ••• xh2-M,-ti)(t)

Table II. Arrangement of Ri(T, t) and xts'ic2i(t)

With the aid of Table II, we obtain the orthogonal relation as S:xhpilm-t'i+rc)(t).R,((2rct-.-i)/2m, t)at=I8;i)P'i/2(M")'2, .rc';rcrc1 (i3)

rc=1, 2,•••, 2m-i-i rci=1, 2,..., 2m-l-1 p=O, 1,•••, 2i-1, and

j:xhk!,(t)R.(O, t)(lt=:1/2(m-i)i2, k,..1, 2,..., 2m-i. Åq14)

This implies that R.(r, t) and xhk!,(t) of the same row are not orthogonal, while these of different rows are orthogonal.

(9)

e) We are now ready to derive the desired expansion for RB-functions.

Summarizing the results in a)-d), the final expansion is obtained and listed in Table III. This expansion is viewed as a system of simultaneous linear equations in which Haar functions may be regarded as unknowns. The following observations can be made with respect to the system.

G, R,(O, t) =x6i)(t)

G2 Ri(1/4, t) = -- 2-'/2x i" (t) + 2-i/2x i2) (t) R2(O, t) =2-ii2x{i)(t)+2-il2x{2)(t)

G3 Ri(1/8, t) == -- xS" (t) + xS3' (t) - 2-3i2x i" (t) + 2-3/2x {2' (t) + (1/2)x6i) (t) Ri(3/8, t) = - xS2' (t) +xS`' (t) - 2m3'2x i" (t) + 2-3i2z {2' (t) - (1/2)x6i) (t) R2(1/8, t) = - (1/2)xSi' (t) + (1/2)xS2' (t) - (1/2)xS3' (t) + (1/2)xS`' (t) R3(O, t) = (1/2)xS" (t) + (1/2)xS2' (t) + (1/2)xÅr3' (t) + (1/2)xS4) (t)

m-2 2d

G. R,(1/2m, t)=2(i-m)12{--xhiL,(t)+xh2-Mi2+i)(t)}+ .Z X C.,,,,/,.,i,kx;•k)(t)

X-O,k,-7i

R,(3/2m, t) ,.,2(i-m)/2{-xh22,(t)+xh2-Mi2+2)(t)}+Z Z C.,,,,/,m,,•,,X,(•le)(t)

1==Ok==1

Ri((2m-i- 1)/2m, t) =2(i-m)/2{-xin2-mi2) (t) +xh2-mii) (t)}

m-2 2i'

+Z Z C.,i,(2m-i.i)12m,i,kX;•k)(t) 1==Ok=1

R,(1/2m, t) = 2(i-m)12{ -- xhit,(t) + xh2-Mi3) (t) - xhL+,2 M-2) (t) +xhi-+ ,3 • 2M-3) (t)}

m-2 2d

+Z Z] C.,2,,12mi,hx;•k)(t) 2=1 k== 1

R,((2m-2 - 1)/2m, t) = 2(i-m)12{-xh2mMi3) (t) +xh2-Mi2) (t) -- xh3:iM"-3) (t) +xh2-mii) (t)}

m-2 2d

+?: Z C.,2,(2m-2-1)12.,,•,kX;•k)(t) s=1 k==1

R.m2(1/2M, t) = 2(i-M)i2{ -- xhi!,(t) +xh31,(t) -- • • • +xh2-Mii-i) (t)}

m-2 2j

-tZ Z C.,.-2,,l2M,j,kx;.k)(t) ]=m-3 k=1

R.-2(3/2M, t) = 2("M)i2{-xh21i(t) +xh41i --- • • • +zh2.Mii) (t)}

m-2 2j

tZ Z C.,.-2,,/2.,,•,kx;•k)(t) 1==m-3 k=1

R.-i(1/2M, t) =2(i-m)/2{ ---xE2iLi(t) +xh2L,(t) --- •••+xSi2.Mii) (t)}

2M--2

+Z C.,..,,1/2m,.-2,kxhkL2(t)

k-1

R.(O, t)=2('-m)t2{xh'Li(t)+xin2Li(t)+•••+x h2-M,-i)(t)}

TABLE III The expansion of RB-functions in terms of Haar functions

(10)

1) The number of R.(T, t) and the number of Haar functions contained in Ci, i=1, 2,•••, m are both equal to 2m-1.

2) Thenumber of R.(T, t) and the number of xhkZ,(t),k =1,2,•••,2m-i contain ed in G. are both equal to 2m-i.

B. LineaTIndependencePropeTtyofRB-I7'zenctions

For the moment, we put aside our major problem of solving the system of simultaneous equations and consider the following linear independence property of RB-functions which has not been thoroughly studied. This property isderiv- ed as follows.

The orthogonality relations for RB-functions are

S:Ro(t)Rn(T, t) at=O (15)

and

j:Rn(r, t)Rn'(Ti, t)dt={1-4-ZV(T-r')}6nn' (16)

where 6..t represents the Kronecker's delta, IV= 2n-i, and r2Tt for n= n'.

The value of the integral for n == ni can easily be calculated with the aid of graphs since the integrand is two-valued rectangular functions. That the integral is zero for n4 n' relies on the fact that the orthogonality for Radema- cher functions is invariant to shift along the t-axis. The relations (15) and (16) are restated as follows.

1) R,(t) is orthogonal to all R.(r, t), n == 1, 2, 3,•-•.

2) When nst ni, R.(T, t) and R.t(T', t) are orthogonal independently of T and rt.

Furthermore, it is noticed that when rlT', R.(r, t) and R.(T', t) have notany common point of discontinuity. This implies that any point of discontinuity of R.(r, t) can not be generated by a linear combination of a finite number of the remaining R.(r', t), T E r'. From these properties it follows that any one of RB- functions is not expressible as a linear combination of a finite number of the remaining RB-functions. Then we may conclude that RB-functions are linearly independent.

C. Solietions of the System

We now return to our problem of solving the system of simultaneous equations in Haar functions. The Iinear independence property and the fact that the number of equations is equal to the number of unknowns ehsure the existence and the uniqueness of the solution. In other words, the system has at

(11)

least one and only one solution. The answer can be obtained by the following two methods. The first is a usual method of solving the system. The second is a straightfoward method instead of solving the system.

In the first method we proceed stepwise as follows. This corresponds to the process of solving the simultaneous equations.

Clearly,

x60'(t)=:R,(t), x6"(t)=:R,(O, t). (17)

Solving the simultaneous equations belonging to G2 gives

1

z{i)(t) =v,i2- {R,(O, t)-R,(1/4, t)}

(18) xi2)(t) = vli-{R,(O, t)+R,(1/4, t)}

Substituting (17), (18) for x6i'(t), xi"(t), and xÅí2'(t) in the simultaneous equations belonging to G, and solving them gives

zSi)(t)= (1/2){R,(O, t)-R,(1/8, t)+R,(O, t)+R,(1/4, t)-2R,(1/8, t)}

xS2)(t)=(1/2){R,(O, t)+R,(1/8, t)+R,(1/4, t)-R,(O, t)-2R,(3/8, t)}

(19)

xÅí3)(t) = (1/2){R,(O, t) -- R,(1/8, t)-R,(O, t) -R,(1/4, t) +2R,(1/8, t)}

xS4)(t)=(1/2){R,(O, t)+R,(1/8, t)-R,(1/4, t)+R,(O, t)+2R,(3/8, t)}

and generally, solving the simultaneous equations belonging to Gi, i-- 1, 2,••-, m-- 1 gives the expression for zhk'(t), n=O, 1, 2,•••, m-2, k =1, 2,`••, 2n in terms of RB-functions where m==3, 4, 5,••-. Substituting these results forcorrespond- ing xÅíle'(t) in the simultaneous equations belonging to C. and solving them gives the expression for zhk)i(t), k==1, 2,•••, 2M-i. However, the labor of solving the system increases rapidly as the number of unknowns increases. Fortunately, we can get the answer in a straightfoward and simple manner without solving the system. This is as follows.

As in the preceeding case,

x60)(t)==R,(t), x6i)(t) :R,(O, t) (20)

We start by first introducing the following recurrence formula.

R(m, m' -- 1, t) == (1/2) {R(m, m', t) + R.•-i(O, t) - .R .•-,(1/2M, t)} (2 1)

where m22. First setting R(m, m, t) == R.(O, t) and then substituting for m' the

(12)

values m, m-1,•••, 3, 2 gives

((2m-m'+2-1)/2m-m'+1, 2m-m'+2(k-1)/2mÅqtÅq R(m'm'-i'`)=i-i/2m-m(2'2.+ill.Tli,i(m/kH2-m.'iiiti)lii.+M..})i.2,T,f`Åq (22)

This can easily be proved by mathematical induction on m' with the aid of graphs.

Then xhkZi(t), m=2, 3,•••, k==1, 2,•••, 2m-i is obtained in the following manner.

Now we make two rules for RB-functions in (24), (27).

Rule 1. R.(r, t-a) means R.(T+a, t).

Rule 2. When TÅr1/2" for R.(T, t), replace R.(r, t) by R.(r', t) which is obtained by the repeated application of the formula

R.(1/2"+r, t)=:-R.(T, t) (23)

to R.(r, t) until r' satisfies the restriction of definition 3.

Let

X(nz, 1, t)-(1/2){R(m, 1, t)-R(m, 1, t- 1/2M)} (24) where

R(., 1, t)=1(2M-1)/2M-i, OÅqtÅq1/2m (2s) 1--1/2m-i, 1/2mÅqtÅq1.

R(m, 1, t) is thus viewed as a block pulse without the dc component.

Then

2(mnyi)/2X(m, 1, t)=xhiX,(t) (26)

Therefore,

2(mHi)i2X(m, 1, t-(2k-2)/2m) =xhleLi(t). (27)

Thus it has been shown that Haar functions can be expressed as a linear combination of a finite number of RB-functions. Finally, it should be noted that the

previous argument based upon the simultaneous equations is also necessary for this straightfoward method to establish the existence and the uniqueness of the results. The results of this section are summarized in the following theorem.

TheoTem 1: Every Haar function can uniquely be expressed as a linear combination of a finite number of RB-functions.

(13)

Since it is well-known that a Walsh function is expressed as a linear combination of a finite number of Haar functions in which the expansion coeflieients are either +1 or -1, the following corollary may be established.

Corollary 1: Theorem 1 is also valid for the Walsh function.

4. The Expansion of Sequency-Ordered Walsh Functions in Terms of RB-Functions

In this section we are concerned with finding the actual form of expansion of Walsh functions in terms of RB-functions. Some interesting results will be obtained. In expanding a Walsh function in terms of RB-functions, it is con- venient to deal with sequency-ordered Walsh functions instead of Åëhk'(t), and the knowledge of the points of discontinuity is a key to theexpansion. We first obtain an expression for the Walsh functions with odd sequency and then those results are applied to obtain an expression for the Walsh functions with even sequency.

a) Clearly,

iDaZ(O, t) == Ro(t). (28)

b) The expansion of s'al(2L+1, t) and baZ(2L+1, t), L=O, 1, 2,•••

1) Walsh functions with odd sequency possess the following properties.

sal(2L + 1, t) = - s-al(2L + 1, t + 1/2) (29)

c-al (2L + 1, t) = -- 6al(2L + 1, t+ 1/2)

On the other hand, only Ri(T, t) has the same property, that is,

Ri(r, t)= -- Ri(r, t+ 1/2) (30)

For R.(T, t), m2)2, this property does not hold, that is,

Rm(T, t)=Rm(T, t+1/2) (31)

Then taking into account the linear independence property of RB-functions previously derived, sal(2L+1, t) and eal(2L+1, must be expressed as a linear combination of only Ri(r, t).

2) We investigate the position of the points of discontinuity for Walsh functions with odd sequency and sign changes at these points. We write down these points of discontinuity in the open interval (O, 1), which are assumed to be known, from left to right in an increasing order.

s'al(2L + 1, t) : (l; ,, L, i, C: ,, L, 2, • • t, (l; ,, L, 2L, e ls, L, 2L+i == 1/2, (l; ,, L, i + 1/2,

(14)

C;s, L, 2L + 1/2,' '', (l;s,L,2L + 1/2

eal(2L+1, t): (:,,L,i, C,,L,2,•••, C,,L,2L+b el;,,L,i+1/2, (I:,,L,2+1/2, '''' (:I'c,L,2L+i+ 1/2

The sign change of s-al(2L+1, t), L21 at t =C,,L,j and that at t =4,,L,i+1/2 are opposite where 7'=1, 2,•••, 2L. The sign change of c'al(2L+1, t), L;}iO at t==

C;,,L,j and that at t== C;,,L,i+1/2 are also opposite where i=1, 2,•••, 2L+1.

3) s-al(2L+1, t),L20 and 6al(2L+1, t),L20 make a sign change from

+1 to -1 at t== C,,L,i and at t =C,,L,i, respectively.

4) Ri(r, t) makes sign changes from -1 to +1 at t=T, and from +1 to -1 at t=T+1/2.

However, Ri(r', t), r'#T is continuous at t==r and t=:T+1/2. Combining these results 1)-4), it is coneluded that only Ri(T, t) can generate the points of discontinuity of sinal(2L+1, t) and bal(2L+1, t) at t==r, and the coefficients of Ri(T, t) in the expansion of s-al(2L+1, t) and c-al(2L+1, t) must be either +1 or

-- 1. Consequently, the expansion of sal(2L+1, t) and c'al(2L+1, t) are 2L

s-al(2L + 1, t) = Z (- l)"Ri(C,,L,j, t) + Ri(O, t) j'-1

(32) 2L+1

c-al(2L+1, t) = ZI (-1)'Ri(Cc,L,j, t)•

1=1

c) The expansion of s-al(2L, t) and jal(2L, t), L=1, 2, 3,•••

We must first notice that even sequeney 2L can be written in the form of 2v-i(2Z+1), Z==O, 1, 2,•••, v=2, 3, 4,•••. Then the expansion of s-al(2Z+1, t) and bal(2Z+1, t) are obtained by substituting Z for L in (32). Therefore, repeated application of the formulas for s-al(2L, t) and jal(2L, t) in (6) and the

formula

R..,(,/2,t)=IRn(r,2`), OÅqtÅq1/2 (33)

IR.(r,2t-1), 1/2ÅqtÅq1

to s-al(2Z+1, t) and c-al(2Z+1, t) y-1 times gives the final results.

2x

sal(2 "-i (2 Z + 1), t) = .Z (- 1)j'R. (C,,, .•/2"-i, t) + R. (O, t)

1= 1

(34) 2X+1

bal(2" nt'(2Z + 1), t) == l ( -- 1)]'R. (C,,,,i/2"-', t)

1=1

where C,,,,i/2"-i, i--- 1, 2,•••, 2Z is the first 2Z of the points of discontinuity of

s-al(2v-i(2Z+1), t) in the open interval (O, 1) arranged in an increasing order, and 4,,,,j/2"", i=1, 2,•••, 2Z+1 is the first 2Z+1 of the points of discontinuity

(15)

A New Expression for Walsh Functions-the Completion of Rademacher Functions 81 of 6al(2"-i(2Z+1),t) in the open interval (0,1) arranged in an increasing

order.

For example, consider s-al(6, t).

From (32)

s-al(3, t) == R,(O, t)-R,(1/8, t)+Ri(3/8, t).

From (6)

,-.i(6, t) .,, IS-ai(3, 2t), oÅqtÅqi/2

Ls-al(3,2t-1), 1/2ÅqtÅq1

.,,I:l(,gl2,l)--su,iS,`lE5i13,18kl:',År,P;,t-Åq,i/,2,,,.,.,.

Applying (33) to the above result leads to the final form.

s'al(6, t)=R,(O, t)-R,(1/16, t)+R,(3/16, t), OÅqtÅq1.

d) Combining the results in a), b), and c), the following theorem is obtained which gives a general form of the expansion of Walsh functions in terms of RB-functions.

TheoTem 2: Walsh functions can be expressed as a linear combination of a finite number of RB-functions as

toal(O, t) == Ro(t)

2X

shl(2"--i(2Z+1), t) =Z (-1)]'R,(C,,,,,,j, t)+R,(O, t) 7'-1

jal(2"-i(2z+1), t) =2Nt'(-1)iR,(C,,,,x., t), (35) 1'-1

v== 1, 2, 3,•••, Z=- O, 1, 2,•••

whereC,,,,,,j, 7'=1,2,•••,2Z is the first 2Z of the points of.disconPinuity of :,al(2"-i(2Z+1), t) in the open interval (O, 1) arranged m an mcreasmg order, and C,,,,x,j, i=1, 2,•••, 2Z+1 is the first 2Z+1 of the points of discontinuity of oal(2"mi(2Z+1), t) in the open interval (0, 1) arranged in an increasing order.

Thus the expansion has been accomplished. As a consequence of Theorem 2, we have the following corollary.

CoTotlao'y 2: sal(2"m'(2Z+1), t) and bal(2"-'(2Z+1), t) consist only of

(16)

R,(T, t) and the number of R.(T, t) is 2Z+1, v==1, 2, 3,•••,Z=O, 1, 2,•••. The results for the first thirty-two sequency-ordered Walsh functions are listed in Table IV.

ival(O, t)=Ro(t)

s-al(1, t)=Ri(O, t)

c"al(1, t) =: -Ri(1/4, t)

s-al(2, t) = R2(O, t) 6al(2, t)= -R2(1/8, t)

sal(3, t) = -R,(1/8, t)+Ri(3/8, t)+Ri(O, t) 6al(3, t) = -Ri(1/8, t)+Ri(2/8, t) -- Ri(3/8, t) sal(4, t) == R,(O, t)

eal(4, t) = -R,(1/16, t)

s-al(5, t) == --Ri(1/16, t)+Ri(3/16, t) --Ri(5/16, t)+Ri(7/16, t)+Ri(O, t)

c-al(5, t) = --Ri(1/16, t)+R,(3/16, t)-Ri(4/16, t)+R,(5/16, t)-Ri(7/16, t) sal(6, t)=: ---R,(1/16, t)+R2(3/16, t)+R2(O, t)

bal(6, t)=-R2(1/16, t)+R2(2/16, t)-R2(3/16, t)

sal(7, t)= -R,(1/16, t)+R,(2/16, t)-R,(3/16, t)+R,(5/16, t)-Ri(6/16, t)

+R,(7/16, t)+R,(O, t)

oal(7, t) = -R,(1/16, t)+R,(2/16, t) --R,(3/16, t)+R,(4/16, t) --R,(5/16, t)

+R,(6/16, t)-R,(7/16, t)

sal(8, t)=R,(O, t) jal(8, t) == -R4(1/32, t)

s-al(9, t) == -Ri(1/32, t)+Ri(3/32, t)-Ri(5/32, t)+R,(7/32, t)-Ri(9/32, t) +R,(11/32, t) --R,(13/32, t)+R,(15/32, t)+R,(O, t)

Ual(9, t)= --R,(1/32, t)+Ri(3/32, t)-R,(5/32, t)+Ri(7/32, t)-Ri(8/32, t) +R,(9/32, t)-.R,(11/32, t)+R,(13/32, t)-R,(15/32, t)

s-al(10, t) == -R2(1/32, t)+R2(3/32, t) ---R2(5/32, t)+R2(7/32, t)+R2(O, t) 6al(10, t)= --R2(1/32, t)+R2(3/32, t)-R,(4/32, t)+R,(5/32, t)-R2(7/32, t)

s"al(11, t)= -Ri(1/32, t)+R,(3/32, t)-R,(4/32, t)+R,(5/32, t)-Ri(7/32, t)

+R,(9/32, t)-R,(11/32, t)+R,(12/32, t)-R,(13/32, t) +R,(15/32, t)+R,(O, t)

c-al(11, t) == -Ri(1/32, t)+Ri(3/32, t) --R,(4/32, t)+Ri(5/32, t) --Ri(7/32, t) +.R,(8/32, t)-R,(9/32, t)+R,(11/32, t)-R,(12/32, t)

+R,(13/32, t)-R,(15/32, t)

s-al(12, t) == -R3(1/32, t)+R3(3/32, t)+R3(O, t)

c-al(12, t)=: --R3(1/32, t)+R,(2/32, t)-R3(3/32, t)

(17)

A New Expression for Walsh Functions•-the Completion of Rademacher Functions 83

,gal(13, t) = -R,(1/32, t)+R,(2/32, t)-R,(3/32, t)+R,(5/32, t)-Ri(6/32, t) +R,(7/32, t)-R,(9/32, t)+R,(10/32, t)-R,(11/32, t)

+R,(13/32, t)-R,(14/32, t)+R,(15/32, t)+R,(O, t)

jal(13, t)= --R,(1/32, t)+R,(2/32, t)-R,(3/32, t)+R,(5/32, t)-Ri(6/32, t) +R,(7/32, t) ---R,(8/32, t)+R,(9/32, t)-R,(10/32, t)

+R,(11/32, t)-R,(13/32, t)+R,(14/32, t)-R,(15/32, t)

s-al(1 4, t) = - R2(1/32, t) + R, (2/32, t) - R2(3/32, t) + R2(5/32, t) - R2(6/32, t)

+R,(7/32, t)+R,(O, t)

6al(14, t)= --R,(1/32, t)+R,(2/32, t)-R,(3/32, t)+R,(4/32, t)-R2(5/32, t) +R,(6/32, t) -R,(7/32, t)

s""al(15, t) = -R,(1/32, t)+R,(2/32, t)-R,(3/32, t)+Ri(4/32, t) --R,(5/32, t)

+R,(6/32, t) --- R,(7/32, t)+R,(9/32, t) --- R,(10/32, t) +R,(11/32, t)-R,(12/32, t) +R,(13/32, t)-R,(14/32, t) +R,(15/32, t)+R,(O, t)

bal(15, t) = ---R,(1/32, t)+R,(2/32, t) ---R,(3/32, t)+Ri(4/32, t) •-Ri(5/32, t) +R,(6/32, t)-R,(7/32, t)+R,(8/32, t) --•R,(9/32, t)

+R,(10/32, t) ---R,(11/32, t)+R,(12/32, t) -R,(13/32, t) +R,(14/32, t) --R,(15/32, t)

,gal(16, t)=R,(O, t)

Table IV Expansion of sequency-ordered Walsh functions in terms of RB-functions

5. Properties of Shifted Rademaeher Functions r.(T, t)

This section is devoted to the derivation of various formulas which give information about the prorerties of r.(r, t).

A. I7TourierSeTiesRepTesentionfoTr.(T,t) After simple calculations, we obtain

r.(r, t) = 2 (4/z) (2z --- 1)-isin {2nN(2z - 1) (t - r)}, N= 2"-' (36)

z=1

n=1, 2, 3,••'•

We decompose r.(r, t) into the following two functions r,.(r, t) and r,.(r, t).

In the notations r,.(T, t) and r,.(T, t), the letters s and c allude to the sine and cosine functions, respectively. The reason for this will be given in Section 7.

rn(r, t)=rsn(T, t)-rcn(r, t)

eo

r,.(r,t) = Z] (4/n)(2x - 1)"'cos2nlV(2z - 1)T•sin2rrN(2z -- 1)t

z=1

(18)

ee

== Z (4/z)(2z -- 1)"i(1/2){sin2zN(2x- 1)(t +r) 2=1

+sin2zAr(2z -- 1)(t - T)}

= (1/2){r.( -- r, t) +r.(r, t)}

(37) co

r,.(r, t)=Z (4/z)(2x-1)-'sin2zAi(2z-1)r•cos2zN(2x-1)t 2==1

= Åí (4/z)(2x •-- 1) -'(1/2){sin2nN(2x - 1)(t + r) 2=1

--- sin2nlV(2z -- 1)(t - T)}

=(1/2){r.(-r, t)-r.(r, t)}

The graphs of these three functions for n=1 are illustrated in Fig, 1. Note that r,.(r, t) and r,.(T, t) take only the values +1, O, and -1.

B. Shifting FoTmulas with Respect to r

r.((2Ar)-!+r, t) == -r.(T, t) r,.((41V)-i +r, t) = -- r,.((4N)-i -- r, t) r,.((2.ZV')-'Å}T, t) = -r,.(r, t) r,.((4Ar)-i+T, t) == r,.((4N)"-T, t) r,.((2N)-iÅ}r, t)=: i r,.(r, t)

(38)

rn(-T', t)=rsn(T, t)+rcn(T, t) rs,t(-rv t)=rsn(T) t)

rcn(-r, t)=-rcn(r, t)

From (38), it follows that for given r,.(r, t) and r,.(r, t) with T:sgO or r2(1/4Ai), there exists r,.(T', t) and r,.(T', t) with Os;r'Åq(1/41V) such that rsn(z', t)= Cr,.(T', t) and r,.(T', t) == Cr,.(z", t), respectively, where C is either +1 or -- 1.

C. OTthogonality Relation for Ro(t), r,.(r, t), ana r,.(f, t)

This section lists formulas which give information about the orthogonality properties of new functions appearing in this paper, These functions have such a particular property that computing orthogonal relation is essentially the same as computing autocorrelation and selfcorrelation.

S:Ro(t)r.(r, t) at = o

(19)

1

o

-1 1

o

-1

1

o

-1

o

1

o

-1 1

o

-1 1

o

-1 1

o

-1

o

1

o

.-1 1

o

-1

rsl( r, t )

10 le

•r,1(r,t) ^rl(r,t)

o o

e

11111

iili

1

111

o

T

10

- 10

10 10

10 10 10

IL 16

1SL

16

IA 16

-¹⁶5 .z 16

-

¹⁶8

91•i6'

-12¹⁶ 151 rs

-16¹⁶

Fig. 1. The graphs of r,i(T, t), r,i(r, t), and ri(r, t) for various values of T.

slRo(t)r,.(r, t)at =O

s:Ro(t)r,.(r, t) at = O

(20)

jirsn(r, t)r,.'(T', t)dt =O, n=n' or n# n'

r=r' or r#rt j:Rg(t)at =i

j:r.(T, t)r.t (r', t) dt = {1 --- 4-ZV(r - T')}6..,, r l}r vt, T- T' Åq (1/2Ai)

S:r,.(r, t)r,.,(T', t)at =(1-4.ZVTr)6..,, Of{;r+T'fE{(1/2.ZV-), T;}iiT' S:r,.(r, t)r, .• (T', t) dt=4AIT '6..•, O sl r+T' s; (1/2 Ar), r ;?: T'

j:r?.(t, t) (it+j:rZ.(r, t) (it ==i (39)

D. Shifting l7ToTmulas with Respect to t

The following relations are analogous to those of trigonometric functions.

Skew-symmetricity with respect to t = (1/2) r.(O, t)= -r.(O, 1-t)

(40) rsn(T, t) = -rsn(re 1-t)

Symmetricity with respect to t =(1/2)

r,n(r, t)=r,.(T, 1-t) (41)

Periodicity

r.(T, t+1/2") == --r.(T, t) r,.(T, t+1/2n) = -r,.(T, t) r,.(r, t+ 1/2") = -r,.(T, t)

...,(o, ,) ,,. g"(O' 2')' OÅqtÅq 1/2 (42) Åqr.(O,2t-1), 1/2ÅqtÅq1

6. Similarities between RB-Functions and Trigonometric Functions The following observations can be made with respect to RB-functions.

a) Expanding a given square-integrable function f(t) in terms of Walsh functions and then replacing each Walsh function by RB-functions gives

(21)

S(t) =aoRo(t)+Za.,.R.(r, t). (43)

n, 7

Coefficients ao, a.,. are obtained from the Fourier coefficients of f(t) with respect to Walsh functions. We call this series the RB-series. On the other hand, f(t) can also be expanded in trigonometrie Fourier series which consists of a const- ant term and sin2znt with phase angle e. as

S[f]-a6/2+S a. sin(2znt+e.). (44)

n==O

Comparing the two series, we see that Ro(t), R.(O, t), and T correspond to 1/2, sin2znt, and e., respeetively. That fact shows that there exists a good corre- spondence between RB-series and trigonometric Fourier series.

b) sin(2znt+e.) is decomposed into sin2znt and cos2znt. R.(T, t) is also decomposed into R,.(r, t) and R,.(r, t) whose sign changes are analogous to those of sin2znt and cos2znt, respectively, as stated in Section V-D. More- over, we note a somewhat surprising fact that R,.(r, t) and R,.(T, t) obtained by decomposing rectangular function R.(T, t) in the same way as in trigonometric functions also become the same rectangular functions. Fig. 1 shows how RB-functions possess these properties.

c) When RB-functions are assumed to be periodic by the condition Rn(T, t+ 1)=Rn(T, t), '-- oo ÅqtÅq + oo

they make sign changes at equal distances and are asymmetric with respect to their points of discontinuity. This property is analogous to that of trigonometric functions.

d) The fact that in two-valued RB-functions R.(T, t) which are suitable for expressing binary phenomena, Ai =2"-i take the binary numbers 1, 2, 4, 8, -••, whereas in trigonometric Fourier series which is suitable for expressing natural phenomena,n in (44) takes the natural numbers 1, 2, 3, t•• is interesting. Con- , sidering the properties a) - d), we finally wish to remark RB-series may be regarded as a rectangular Fourier series.

e) Though trigonometric functions are orthogonal, RB-functions are not orthogonal.

7 Conclutions

It has been shown that Walsh functions can be expressed as a linear combination of a finite number of RB-functions introduced in this paper. It is interesting to note that the expresion coeMcients take only the values either + 1 or -1. This result is viewed as the completion of Rademacher functions. The

(22)

result that the type and the number of RB-functions appearing in the expansion of Walsh functions are closely related to the sequency of Walsh functions seems to be important. RB-functions are not orthogonal. One result for orthonor- malization of RB-functions leads to Walsh functions. RB-functions have an advantage that they can easily be generated by using shift registers. The method for it has not been stated in this paper. Details of this technique together with experimental results will be reported on at later date. On the other hand, the theorems obtained may be useful in studying the properties of Walsh functions.

A practical application of RB-functions has not been developed. The author wishes to invite suggestions and communications from anyone interested in this subject.

References

[ 1 ] J. L. WALsH, "A closed set of normal orthogonal functions," Am. J. Math., vol. 45, 1923, pp, 5-

24.

[2 ] R. E. A. C. PALEy, "A remarkable series of orthogonal functions," Proc, London Math. Soc., vol.

34, 1932, pp. 241-264.

[3] N.J. FiNE, "The generalized Walsh functiong.," Trans. Amer. Math. Soc., vol. 69, 1950, pp. 66-

77.

[4] K, W. HENDERsoN, "Some notes on the Walsh functions," IEEE Trans. Electron. ComPut. (Cor- resp.), vol. EC-13, Feb. 1964, pp. 50-52.

[5] H. BuTiN, "A compactdefinition of Walsh functions," ILEEE Trans. Electron. Comput. (Short notes), vol, C-21, June 1972, pp. 590-592.

[6] H. F. HARMuTH, "A generalized concept of frequency and some applications," IEEE Trans.

Inform. TheorJ, voL IT-14, May 1968, pp. 375-382.

[7] A. HAAR, "Zur Theorieder orthogonalen Functionensysteme," Math. Ann., vol. 69, 1910, pp.

331-371.

[8] H.A. RADEMAcHER, "Einige Satze Uber Reihen von allgemeinen Orthogonalenfunctionen,"

Math. Ann., vol. 87, 1922, pp. 112-138.

Depuartment of EleetTonics Kyushu

institute of Technology ¹