Walsh Function

Author

Eric W. Weisstein
February 22, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/SpecialFunctions/WalshFunction.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/WalshFunction.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Initialization

<<LinearAlgebra`MatrixManipulation`

Code

HadamardQ[m_List?MatrixQ]:=Module[{n=Length[m]},m.Transpose[m]-n IdentityMatrix[n]==ZeroMatrix[n]
]

ThueMorse[n_]:=Nest[Flatten[#/.{0->{0,1},1->{1,0}}]&,{0},n]

WalshArray[s_]:=With[{f=Identity,g=Reverse},
Nest[Apply[Join,f[{Map[Flatten[Map[{#,#}&,#]]&,#],Map[Flatten[Map[{#,-#}&,#]]&,g[#]]}]]&,{{1}},s]
]

Orderings

With[{s=5},
Show[GraphicsArray[Function[{f,g,t},
RasterGraphics[Nest[Apply[Join,f[{Map[Flatten[Map[{#,#}&,#]]&,#],Map[Flatten[Map[{#,-#}&,#]]&,g[#]]}]]&,{{1}},s],
PlotLabel->TraditionalForm[t]]]@@@{
{Identity,Reverse,"sequency"},
{Transpose,Identity,"natural (or Hadamard)"},
{Identity,Identity,"dyadic (or Paley)"}
}
]
]]

Sequency Ordering

WalshFunction[s_,k_]:=WalshArray[s][[k]]

Walsh[{n_,k_},y_]:=Module[{x=Mod[y,2^n]},
2Plus@@Flatten[MapIndexed[(-1)^(#2-1) UnitStep[x-#1]&,Drop[FoldList[Plus,0,Length/@Split[WalshFunction[n,k]]],-1]
]]-1
]

Cal[n_,k_]:=WalshFunction[n,2k+1]
Cal[{n_,k_},x_]:=Walsh[{n,2k+1},x]

Sal[n_,k_]:=WalshFunction[n,2k]
Sal[{n_,k_},x_]:=Walsh[{n,2k},x]

WalshPlot[n_,p_:4,opts___]:=Module[{k,x,dx=.1,dy=.1,l=2^n},
Partition[
Table[
Plot[Evaluate[Walsh[{n,k},x]],{x,-dx,l+dx},
opts,
PlotStyle->Red,
PlotRange->{Automatic,{-1-dy,1+dy}},
Ticks->{Range[0,l],{-1,0,1}},
PlotLabel->TraditionalForm[W[n,k]],
DisplayFunction->Identity],
{k,l}],
p,p,{1,1},{}]
]

Show[GraphicsArray[Flatten[
Table[WalshPlot[n],{n,3}],1]]]

n = 1

With[{n=1},
Table[WalshOnes[n,k],{k,2^n}]
]//ColumnForm

n = 2

With[{n=2},
Table[WalshOnes[n,k],{k,2^n}]
]//ColumnForm

n = 3

With[{n=3},
Table[WalshOnes[n,k],{k,2^n}]
]//ColumnForm

Cal/Sal

Table[Cal[3,k],{k,0,3}]//ColumnForm

Table[Sal[3,k],{k,4}]//ColumnForm

Walsh Arrays are Hadamard Matrices

HadamardQ/@Table[WalshArray[n],{n,8}]

Thue Sequence

WalshArray[0]/.-1->0

WalshArray[1]/.-1->0

WalshArray[2]/.-1->0

Table[2/3 (1 + 4^( -( Floor[s/2] +1/2))) 2^s,{s,0,19}]

Table[Ceiling[2^k/3],{k,20}]

Table[(2^(n+1)+3+(-1)^n)/6,{n,20}]

ThueMorse[5]

Join[{0},Flatten[Table[WalshFunction[s-1,Ceiling[2^s/3]],{s,5}]]/.-1->0]