Robust and

Robustandpracticalanalog-to-digitalconversion

withexponentialprecision

¨urYılmazIngridDaubechiesandOzg¨

Abstract

Beta-encoderswitherrorcorrectionwereintroducedin[1]asanalternativetoPCMforanalog-to-digital

conversion.Theseencodershave(almost)optimalrate-distortionpropertieslikePCM;furthermoretheyarerobustwithrespecttoquantizerimperfections.Theyhad,however,theshortcomingthatthedecoderneededtoknowtheparameterβusedbytheencoder,anunpracticalconstraint.Wepresentamethodtoimplementbeta-encoderssothattheyarealsorobustwithrespecttouncertaintiesofthevalueofβ.Themethodreliesuponembeddingthevalueofβintheencodedbitstream.Weshowthatthiscanbedonewithoutaprioriknowledgeofβbythetransmittingparty.Moreoverthealgorithmstillworksifthevalueofβchanges(slowly)duringtheimplementation.

IndexTerms

Quantization,A/Dconversion,beta-expansions,beta-encoders,sigma-delta,sampling

I.INTRODUCTION

Analog-to-digital(A/D)conversionconsistsoftwosteps:samplingandquantization.Weshallassumethatf,

ˆvanishesoutsideaboundedtheanalogsignalofinterest,isabandlimitedfunction,i.e.,itsFouriertransformf

interval.Inthiscase,thestandardsamplingtheoremstatesthatwecanreconstructthesignalfromitssamplevalues

ˆiscontainedin[−Ω,Ω],thesequence{f(nπ/Ω)}n∈Zonasufficientlydensegrid.Inparticular,ifthesupportoff

determinesfvia󰀆nπ

).(1)f(t)=f(

ΩnInpractice,(1)isnotveryusefulbecausethe“sinckernel”decaysslowly,andthusthereconstructionisnotlocal.

However,wecanovercomethisproblembysamplingonadensergrid,inwhichcasewecanreplacethesincin(1)byakernelwithmuchfasterdecay.Inparticular,ifinsteadofthesamplesequence{f(nπ/Ω)}n∈Zthemoreclosely-spacedsamples{f(nπ/(λΩ))}n∈Z(withλ>1)areused,(1)canbereplacedby

f(t)=

1

λΩ)ϕ(t−

nπ

2

withoutlossofgenerality,onlythecaseΩ=πandM=1,anddenoteS(π,1)byS.Foranyquantizationscheme,or,equivalently,foranyencoder-decoderpair(E,D),wedefinethedistortiondby

d(S;E,D):=sup󰀎f−D(Ef)󰀎

f∈S

(3)

where󰀎·󰀎isthenormofinterest.TheperformanceofaquantizationschemeonSistypicallycharacterizedbytherelationbetweenthedistortiondandthenumberBofbitsperNyquistintervalconsumed(onaverage)bytheencoderEassociatedwiththequantizationscheme;wecallthisnumberthebitbudgetofthequantizationscheme.Atypicalwayofcomparingtheperformancesoftwoquantizationschemesistocomparethebitbudgetstheyutilizetoproduceapproximationswiththesameamountofdistortion;ifnootherconsiderationsprevail,thequantizationschemewiththesmallerbitbudgetissuperior,andispreferable.Equivalently,onemightcomparethedistortionsassociatedwithseveralquantizationschemesforthesamefixedbitbudget;inthiscase,theschemewiththesmallerdistortionisfavored.

Onewidelyusedquantizationschemeispulsecodemodulation(PCM).GivenafunctionfinS,anN-bitPCMalgorithmsimplyreplaceseachsamplevaluef(n/λ)withNbits:onebitforitssign,followedbythefirstN−1bitsofthebinaryexpansionof|f(n/λ)|.OnecanshowthatforsignalsinSthisalgorithmachievesaprecisionoforderO(2−N);i.e.,forfinS,thedistortiond(f;E,D)≤C2−Nwhen(E,D)istheencoder-decoderpairassociatedwithanN-bitPCM,andwhenthenorm󰀎·󰀎tomeasurethedistortioniseithertheL∞normonR,orthelimit,asT→∞,ofthenormalizedL2-norm(2T)−1/2󰀎·󰀎L2(−T,T).Thiscanalsoberephrasedintermsofthebit-budget:sincetheaveragenumberofbitsperNyquistintervalisB:=Nλ,wehaved(f,E,D)≤Cλ2−B/λforf∈S,whereλ>1canbechosenarbitrarily,withCλ≤C󰀄(λ−1)−1/2tendingto∞asλ→1.

Ontheotherhand,sigma-deltamodulation,anothercommonlyimplementedquantizationalgorithmforfunctionsinS,achievesaprecisionthatdecayslikeonlyaninversepolynomialinthebitbudgetB.Forexample,akth-ordersigma-deltaschemeproducesanapproximationwheretheL∞approximationerror(i.e.,distortion)isoforderO(B−k).

Despitetheirclearlyinferiorperformanceintermsofdistortionforagivenbitbudget,sigma-deltamodulatorsareoftenpreferredoverPCMforA/Dconversionofaudiosignalsinpractice.Thismustmeanthatotherfactorsaremoreimportant.Aplausibleexplanationfortheprevalenceofsigma-deltamodulatorsisgivenbytherobustnesspropertiesoftheseschemes,whenimplementedinanalogcircuits.Everyquantizationschemeforanalog-to-digitalconversionmustcontain(atleastone)nonlinear“decisionelement”that“performsthequantization”,i.e.,transformsitsrealnumberinputintoanelementofa(finite)alphabet;weshallcallthisnonlinearelementthequantizer,reservingthisnameforthisuseonly.Thesequantizersareboundtobeimprecise,i.e.,thelocationoftheir“togglepoint(s)”istypicallynotknownwithhighprecision.Underthesecircumstances,PCMperformspoorlywhereasthedistortionassociatedwithasigma-deltaschemeishardlyaffectedatall[1];moreprecisely,theerrormadebyaPCMquantizationschemewithanimprecisequantizerisboundedbelowbyastrictlypositiveconstant(directlyrelatedtothemeasureofimprecisionofthequantizer),whereastheerrormadebyakthordersigma-deltaschemestilldecayslikeB−k,andthereforecanbemadearbitrarilysmalldespitetheimprecisioninthequantizer.

Oneofseveralreasonswhysigma-deltaschemesarerobustisthattheyquantizeredundantexpansionsoftheoriginalfunction.Sinceredundantexpansionsarenotunique,anyerrorcausedbyanimprecisequantizercanbeimplicitlycorrectedlater.ThisisclearlynotthecaseforPCM,sincethebinaryexpansionofalmosteveryrealnumberisunique,andthereforeabitflipintheexpansioncannotbecorrectedbychangesintheconsecutivebits.Foradetaileddiscussionofrobustnesspropertiesofsigma-deltaschemesaswellasacomparisonwithPCM,wereferto[2],[3],[1],[4].

Itisnaturaltowonderwhetherwecanhavethebestofbothworlds.Inotherwords,canweconstructaquantizationalgorithmthatutilizesthebit-budgetefficiently,likePCM,butthatisatthesametimerobustwithrespecttounavoidableimprecisionerrorsinthe(analog)circuitimplementation,likesigma-deltamodulators?In[1]twoquantizationschemesarediscussedthatshowthattheanswertothisquestionisaffirmative:amodified,filteredsigma-deltascheme,firstproposedin[5],andaschemethatisintroducedin[1]forthefirsttime(asfarasweknow),calleda“beta-encoderwitherrorcorrection”.Thesebeta-encodersarePCM-likeinthattheyquantizeeachsamplefinelyandachieveexponentialprecisionfortheresultingapproximation;moreovertheyarerobust,likesigma-deltaschemes,becausethisfinequantizationisdoneinaredundantway.

Althoughtheencodersdiscussedin[1]arerobustagainstquantizerimperfections,theyneverthelessstillhave

3

certainrobustnessproblems,atleastfromapracticalpointofview.Bothofthemuseotherparameters(thefilterparametersfortheschemeof[5],thefactorβusedinthebeta-encoder)thatneedtobeimplementedwithhighaccuracy.Inthispaper,weshalldiscussthisissuefurtherforbeta-encoders.

Thebeta-encoderof[1],whichweoutlineinSectionII,computesa“truncatedβ-aryexpansion”foreachsamplevalue,i.e.,aseriesexpansioninabaseβ,where1<β<2,andwithbinarycoefficients.Inordertoreconstructagoodapproximationtotheoriginalsignalvaluefromthesebinarycoefficients,itiscrucialtoknowthevalueofβ,withaprecisioncomparabletoatleasttheonewehopethequantizationschemetoachieve.However,measuringtheexactvalueofβaswellasensuringthatitstaysconstantoveralongstretchoftimeisdifficult,ifnotimpossible,inananalogsetting.

Inthispaper,weshowhowthisobstaclecanbecircumvented.Wepresentanalgorithmthatencodesandtransmitsthevalueofβwithoutinfactphysicallymeasuringitsvalue.Thisisdonebyembeddingthevalueofβintheencodedbitstreamforeachsamplevalueseparately.Thusweconstructabeta-encoderthatisnotonlyrobusttoquantizerimperfections,butalsorobustwithrespecttoβ,aslongasthevalueofβremainsconstantorvariessufficientlyslowlythatitdoesnotchangebymorethanthedesiredprecisionrangeofthequantizationschemeover,say,twentysamplingintervals.

InSectionIIweoutlinethe“beta-encoderswitherrorcorrection”,introducedin[1].InSectionIIIwepresentour“beta-robust”approachandprovethatithastherobustnesspropertiesdiscussedabove.InSectionIVwepresentnumericalexamplesandconsidersomevariationstoourapproachthataddressotherrobustnessconcerns.

II.REVIEW

OFBETA-ENCODERS

Inthissection,wesummarizecertainpropertiesofbeta-encoderswitherrorcorrection.See[1]formoredetails.Westartagainfromtheobservationthatanyfunctionf∈Scanbereconstructedfromitssamplevaluesf(n/λ)via󰀆n

−1

f(t)=λf().(4)

λnwhereλ>1andϕ∈C∞,suchthatϕˆ(ξ)=1for|ξ|≤πandϕˆ(ξ)=0for|ξ|≥λπ.

Proposition1.Letf∈S,󰀴>0andconsideranyquantizationschemethatproducesqnsuchthatsup|f(n/λ)−

˜,definedasqn|≤󰀴.Thentheapproximationf

󰀆n−1˜f(t):=λqnϕ(t−

n

λ

)|≤Cϕ󰀴(6)

whereCϕ:=󰀎ϕ󰀎L1+λ−1󰀎ϕ󰀄󰀎L1

˜Proposition1shows,forexample,thatiftheqnareproducedbyanN-bitPCMalgorithm,thenthefunctionf

definedby(5)satisfies

˜󰀎L∞≤Cϕ2−N+1,󰀎f−f(7)

because,byconstruction,anN-bitPCMgeneratesqnsuchthat|f(n/λ)−qn|≤2−N+1foralln.

Next,wewillconsider,insteadoftruncatedbinaryexpansions,truncated1-bitβexpansionsofthesamplevalues.Bya1-bitβexpansionwemeananexpansionwithbinarycoefficientsandbaseβ∈(1,2).Foranyrealnumberx∈[0,1],andgiven1<β≤2,thereexistsasequence(bj)j∈N,withbj∈{0,1}suchthat

x=

∞󰀆j=1

bjβ−j.

(8)

Clearly,forβ=2,(8)correspondstothebinaryexpansionofx;for1<β<2,theexpansionissaidtobea

beta-expansion,andisnotunique;infact,forevery1<β<2andforalmosteveryxin(0,1],thesetofdifferentβexpansionsofxhasthecardinalityofthecontinuum[6].

4

Givenx∈[0,1],onewaytocomputeabinarysequence{bj}thatsatisfies(8)istoruntheiteration

ujbj

=β(uj−1−bj−1)=Q(uj)

󰀄

1u>10u≤1.

(9)(10)

withu1=βx,and

Q(u):=

ThenonlinearoperationQin(10)isanidealizedquantizer;inpracticeonehastodealwithquantizersthatonlyapproximatethisidealbehavior(seebelow).Thesamplesf(n/λ)ofafunctionf∈Swillberealnumbersin(−1,1)ratherthan(0,1);weshallhereperformasmall“sleightofhand”andconsiderthevalue-shiftedandrenormalizedfunctiong=(f+1)/2instead,whichdoestakevaluesin(0,1)only.Running(9)Ntimesforeachvalue󰀅Nsample−jg(n/λ)=[1+f(n/λ)]/2,wheref∈S,willyieldanN-bittruncatedbeta-expansion{qn:=j=1bjβ}thatwillsatisfy

|g(n/λ)−qn|f∈SwithdistortionofsizeO(β−N).

Beforedefiningthe“beta-encoderswitherrorcorrection”of[1],wewanttorepeatthekeyobservationthatisusedin[1]toconstructtheseencoders.

Proposition2.Letx∈(0,1)andb1,b2,...,bJbearbitrarysuchthatbj∈{0,1}.If

0≤x−

J󰀆j=1

bjβ−j≤

1

5

Theorem3.Let󰀴>0andx∈(0,1).Supposethatinthebeta-encodingofx,theprocedure(9)isfollowed,butthequantizerQµ(·−δ)isusedinsteadoftheidealQateachoccurrence,withthevaluesofδpossiblyvaryingfromonejtothenext,butalwayssatisfying|δ|<󰀴.Denoteby(bj)j∈Nthebitsequenceproducedbyapplyingthisencodingtothenumberx.If󰀴≤µ,andβsatisfies

1<β<

2+µ+󰀴

6

Lemma4.Letx∈(0,1)andletγ=β−1∈(1/2,1)besuchthat(14)issatisfied,with0<󰀴≤µ.Suppose|δ|<󰀴,

µµ

anddefinethesequencesb:=Eγ,δ(x)andc:=Eγ,δ(1−x).LetNbesuchthatmax{bj,cj:j=1,...,N}>0.Then,foranyγ˜thatsatisfies

N󰀆

(bj+cj)γ˜j≤2Cγ˜N,(16)0≤1−

j=1

withC=1+µ+󰀴,wehavewhere

C󰀄

=max{2C,2C/(k0

γ(k0−1))}

|γ−γ˜|≤C󰀄γN,

(17)

withk0=

log(1−γlogγ

.

Weshallprovethislemmainseveralstepsbelow.Beforeproceeding,weshowthatknowingthevalueofγwithexponentialprecisionyieldsexponentiallypreciseapproximations.

󰀅jTheorem5.Letx∈(0,1),γ∈(1/2,1)and(bj)j∈N∈{0,1}besuchthatx=∞˜issuchthatj=1bjγ.Supposeγ

|γ−γ˜|≤C1γNforsomefixedC1>0.DefineN0:=log[(1−γ)/C1]

1−(γ+η)2

2(γ+Cγ)N0−1C1γNN01

ifN≥N0+1

if1≤N≤N0.

(18)

Proof:Wewanttoestimate

wherewehaveusedthatbj∈{0,1}.Definenowfj(˜γ):=γ˜j−γj.Clearly,fj(γ)=0;moreoverthederivative

󰀄(˜γ)|=|jγ˜j−1|≤j(γ+∆)j−1forallγ−∆≤γ˜≤γ+∆,whereγ∈(1/2,1)and∆>0.Therefore,satisfies|fj

|fj(˜γ)|=|γ˜j−γj|≤∆j(γ+∆)j−1.

󰀁󰀁

󰀁󰀆󰀁󰀆NN󰀁󰀁

|x−x˜N|=󰀁bj(γj−γ˜j)󰀁|γj−γ˜j|󰀁󰀁≤

󰀁j=1󰀁j=1

(19)

(20)

Wewillnowestimatetherighthandsideof(19)separatelyforthecaseswhenNislargeandwhenNissmall:

1)Setting∆=C1γN,andsubstituting(20)in(19),weget

|x−x˜N|≤C1γ

=C1γ

NN󰀆j=1

j(γ+C1γN)j−1

(21)

N

1−(γ+C1γN)N(1+N(1−(γ+C1γN)))

(1−(γ+C1γN))2

≤C1γN

1

7

1)CombiningLemma4andTheorem5,weseethatonecanrecovertheencodednumberx∈(0,1)fromthe

µµ

firstNbitsofEγ,δ(x)andEγ,δ(1−x),withadistortionthatdecreasesexponentiallyasNincreases.

µµ

2)GivenN-bittruncatedbitstreamsEγ,δ(x)andEγ,δ(1−x),onewaytoestimateγ˜isdoinganexhaustivesearch.Clearlythisiscomputationallyintensive.Note,however,thatthesearchwillbedoneinthedigitaldomain,wherecomputationalconstraintsarenotheavy,andcomputationspeedishigh.

3)InSectionIV-Bweintroduceafastalgorithmthatcanreplaceexhaustivesearch;moreoveritsperformanceisasgoodasexhaustivesearch.B.ProofoftheMainLemma

Inwhatfollows,weshallpresentseveralobservationsthatleadustoaproofofLemma4attheendofthesection.

Proposition6.Letβ∈(1,2),γ:=1/β,andx∈(0,1).Supposeµ,󰀴,andδaresuchthattheconditionsof

µµ

Theorem3aresatisfied.Letb:=Eγ,δ(x)andc:=Eγ,δ(1−x).Then

0≤1−

N󰀆j=1

(bj+cj)γj≤2CγN,

(24)

whereC=1+µ+󰀴with|δ|<󰀴≤µ.

Proof:ByTheorem3,weknowthat

0≤x−

N󰀆j=1

bjγj≤CγN,

(25)

and

0≤1−x−

N󰀆j=1

cjγj≤CγN

(26)

hold.Combining(25)and(26)yieldstheresult.

Notethatdj:=bj+cj∈{0,1,2}.Moreover,theindexofthefirstnon-zeroentryof{dj}∞j=1cannotbearbitrarilylarge;moreprecisely

Proposition7.Letk:=min{j:j∈Nanddj=0}.Then

log(1−γk≤.

logγ

(27)

∞󰀆j=k

Proof:Letkbeasdefinedabove.Clearly,withdj=bj+cjasabove,dj∈{0,1,2},

∞󰀆j=k

∞󰀆j=k

djγj=1.Ontheotherhand,since

djγ≤2

j

γ=

j

2γk

1−γ

≥1,(29)

whichyieldsthedesiredresult.Wenowdefine

Fn(t):=1−

n󰀆j=k

dj(γ+t)j

(30)

8

1Fn0.5Gn0−tt10−0.5−0.5−0.4−0.3−0.2−0.1t00.10.20.30.4Fig.2.AsketchofthegraphofFnalongwithGn(t)=2C(γ+t)n.Heren=5,andFnwascomputedvia(30)fromthefirstnbitsof

µ

thesequenceEγ,δ(x)withx=0.7,γ=0.75,µ=0.2,and|δ|<0.1.

on[−γ,∞)forn=k,k+1,....

Proposition8.Fnhasthefollowingproperties:(i)0≤Fn(0)≤2Cγn.

(ii)Fnismonotonicallydecreasing.Moreover,thegraphofFnisconcaveforalln∈{2,3,...}.

Proof:

(i)ThisisProposition6restated.

n󰀆

󰀄(t)<0fort>−γ.Moreover,󰀄(t)=−jdj(γ+t)j−1.Thus,sincedj≥0forallj,Fn(ii)First,notethatFn

j=k

asimilarcalculationshowsthatthesecondderivativeofFnisalsonegative.ThereforethegraphofFnis

concave.

Figure2showsasketchofthegraphofFn.Define,asshowninFigure2,t0asthepointatwhichFn(t0)=0.Similarly,lett1besuchthatF(−t1)=2C(γ−t1)n.Wewillshowthatbotht0andt1areatmostofsizeO(γn),whichwillleadustoourmainresult.

Lemma9.LetFnbeasin(30)wheren≥kisapositiveinteger.Thent0,asdefinedabove,satisfies

0≤t0≤C1γn,

(31)

withC1=

2C

withC1=

2C

Finally,weconclude

k+1k

(γ−t1)n−.t1≤

2C

2

)

9

(36)

10

1)OuralgorithmisrobustwithrespecttothequantizerimperfectionsinthesenseofTheorem3.Thatis,iftheschemedescribedin(9)isimplementedwithQµ(·−δ)insteadofQ,wecanstillestimatethevalueofγwithexponentialprecisionwithrespecttothebitrate.Infact,ourresultsintheprevioussectionarefortheseimperfectquantizers.InFigures3aand3b,weplot|γ˜N−γ|and|x˜N−x|versusN,respectively,inthecaseofaprecisebeta-encoder(δ=0)withoffsetµ=0.2.Figures4aand4b,ontheotherhand,showthesamequantities,respectively,whentheapproximationsareobtainedviaanimperfectbeta-encoderwithµ=0.2and󰀴=0.15(recallthat󰀴istheboundonδ;Figure4usedasimulationwheretheδjdidnotevenremainconstantfromonesampletothenext;theywerepickedrandomly,uniformlyin(−󰀴,󰀴)).

2)Wecanstillrecoverthevalueofγwiththesameprecisionifinsteadofxand1−x,thetransmittedbitstreamscorrespondtoxand1+ρ−xaslongas|ρ|≤󰀴0forsomesufficientlysmall󰀴0.Moreprecisely,if0≤2󰀴0≤2CγN,whereCisasinTheorem3,wecanreplace(16)inTheorem4withthemorestringentconditiononγ˜

N󰀆

󰀴0≤1−(bj+cj)˜γj≤2Cγ˜N−󰀴0,(41)

j=1

andthetheoremremainsvalid,i.e.,itfollowsthat|γ−γ˜|≤C󰀄γN.Figure5aandFigure5bshow|γ˜N−γ|

and|x˜N−x|versusN,respectively,inthiscasewithρ=γN/2.Thisobservationmeansthatifthereferencelevelcanbekeptfixedwithinaprecisionof󰀴0,thentheschemestillworksuptoN0∼log󰀴0/logγ.

3)Ifweusethepairxanda−xinsteadofxand1−xforsomea∈(0,1),ourapproachstillworks,providedthat0≤x≤aandthatweknowthevalueofa,atleastwithaprecisionof󰀴0thatsatisfies0≤2󰀴0≤2CγN,asabove.InFigures6aand6b,weplot|γ˜N−γ|and|x˜N−x|versusN,respectively,whenthealgorithmisimplementedusingthepairxanda−xwitha=0.9.

4)Ouralgorithmrequiresthatthevalueofγremainconstantduringthequantizationofthenumbersxand1−x,approximatelyoneachsamplingintervalwhenquantizingsamplesofabandlimitedfunction.Ontheotherhand,thealgorithmstillworksifγchanges,howeverdrastically,fromonesamplingintervaltoanother.Asalreadyalludedtoinpoint2)above,ourapproachhasintroducedanewrobustnessissue:typically,wecannotensurethatthereferencelevel(1inthecasewhereweencodethepairxand1−x,1+ρinpoint2))isknownwithhighprecision,whichisanewpracticalhurdle.Moregenerally,inpracticewewouldfaceasituationwherepairsofvalues(x,a−x)areencoded,whereaisnotknownwithgreatprecision.If(asisreasonable)wecanensurethattheunknownreferencelevelaremainsconstantorvariesveryslowlyonly,thenwestillcanestimateγasfollows.Supposethebeta-encodingofx,a−x,y,a−yleadstothebitsequences(bj)j∈N,(cj)j∈N,(˜bj)j∈N,(˜cj)j∈N,

∞∞󰀆󰀆j˜jγj;ifweputk=min{j∈N:dj=d˜j},˜˜ddjγ=respectively.Definedj=bj+cj,anddj=bj+˜cj.Thenthen

j=1

j=1

˜k=dk−d

∞󰀆j=1

˜k+j−dk+j)γj;(d

˜j−dj∈{−2,−1,0,1,2}clearlythisputssomeconstraintonthepossiblevaluesofγ.However,becausethedj=d

cannowtakenegativevaluesaswell,theargumentsusedintheproofsinSection3nolongerhold.WehavethereforenoguaranteethatwewillobtainanestimateforγwithprecisionofsizeO(γN)ifweknowthefirstNentriesof

˜j}.Morethesequencesb,c,˜b,c˜;similarly,wecannotputanupperbound,apriori,onk=min{j∈N:dj=d

precisely,argumentssimilartothoseinProposition6showthat

−2CγN≤

N󰀆j=k

djγj−k≤2CγN,

withCasinProposition6.Thissuggestswereplacetheconstraint(16)ofLemma4with

−2Cγ˜

N

≤

N󰀆j=k

djγ˜j−k≤2Cγ˜N

(42)

andexpectanyγ˜thatsatisfies(42)willbeanexponentiallypreciseestimateofγ.Butsinceinthiscasethe󰀅j−kisnotstrictlydecreasing,wefacetwomajordifficulties:polynomialpN(λ):=Nj=kdjλ

11

10110110~ |γ−γ| N−110−1~ | |x−xN10−310−310−51010N2030−50010N2030(a)(b)

Fig.3.Theperformanceofthealgorithmwhenimplementedusingaprecisebeta-encoderwithoffsetµ=0.2.(a)showstheerror|γ−γ˜N|

whereγ˜NwascomputedfromN-bitbeta-expansionsofx=π/10and1−xviaanexhaustivesearchalgorithm.(b)showstheapproximationerror|x−x˜N|wherex˜Nwascomputedusingtheestimatedγ˜NalongwiththeN-bitbeta-expansionofx.Inboth(a)and(b),theverticalaxesarelogarithmic,andthestraightlinesarethegraphof2CγNwithC=1+µ.

10110110~ |γ−γN|10−110−1~ ||x−xN−310−310−510−5010N2030010N2030(a)(b)

Fig.4.TheexperimentofFigure3repeated;howeverthistimeanimperfectbeta-encoderwithoffsetµ=0.2and󰀙=0.15wasused.(See

text.)

11010110−1~ |γ−γN| 10−310~ |x−xN| −110−510−3010N2030010N2030(a)(b)

Fig.5.Theperformanceofthealgorithmwhenimplementedwithx=π/10and1+ρ−x.Herethe“uncertainty’ρwastakentobeγN/2(whenthenumberofbitsusedtocomputeγ˜NisN).

12

a)Theconstraint(42)maybesatisfiedforvaluesγ˜closeto1,regardlessofwhatthevalueofγisbecausetheconstraintgetsquiteweakwhenγ˜iscloseto1,andpN(˜γ)canbesmallenoughtosatisfythisweakconstraint.Figure7ashowssamplesofsuchpN,obtainedbyencodingx,a−x,y,a−yasdescribedabovewithγ=0.700067forseveralxandythatcausetheabovementioneddifficulty.Onecouldovercometheproblemoutlinedabovebyrestrictingthevaluesofγtoanarrowerintervalthatisknownapriori.Indeed,ifweweregiventhatγ∈[0.6,0.8],then,asobservedinFigure7b,theconstraint(42)issatisfiedonlyinasmallneighborhoodofthetruevalueofγ.Anotherwayofdealingwiththisproblemistoaimdirectlyfortheroot(s)ofthepolynomialpNin(1/2,1)(insteadofsearchingforsomeγ˜thatsatisfies(42)).ThiswillbediscussedfurtherinSectionIV-B.󰀅j−kcanhaveseveralrootsintheintervalb)AnotherproblemarisesbecausethepolynomialpN(λ):=Nj=kdjλ

(0.5,1)(aswellasinthenarrowerintervalwhichweknow,apriori,tocontainγ).Thiswouldinturnmeanthat(42)issatisfiedinsufficientlysmallneighborhoodsofeachoftheseroots(notethatpNisapolynomial,andthussmooth).Figure8showsexamplesofsuchpNthatareobtainedbyencodingx,a−x,y,a−yasdescribedaboveforseveralxandy.(NotethattheexamplesinFigure7andFigure8,althoughtheymayseemcontrived,stemfromactualcodingsimulations–theseproblemscanoccurinpractice.)Inthiscase,clearly,computingtheroot(s)ofpNin(1/2,1)willnothelpaswehaveseveralroots.Moreover,theserootsmaybeveryclosetoeachothersothatevenifweknowapriorithatγliesinsomerestrictedinterval,thismightnotsufficetoexcludeallbutoneroot.Ontheotherhand,weknowthatoneoftherootsofpNisalwaysapproximatelyattherightγvalueindependentlyofwhat(x,y)pairisused(thisfollowsfrom(42)becausepNissmooth),anditisreasonabletoexpecttheotherroot(s)tobelocatedatdifferentpointsintheinterval(0.5,1)dependingonthe(x,y)pairthatwasusedtoobtainpN.Thismotivatesustocomputethepolynomials󰀅I

pN,icorrespondingtoseveral(xi,yi)pairsasabove,andconsiderthepolynomialPN,I:=i=1󰀴ipN,iwherewechoose󰀴i∈{−1,1}inawaythatwouldguarantee(orincreasetheprobability)thatPN,Ihasonlyonerootintheinterval(0.5,1).Inthiscasewereplacetheconstraint(42)with

−2CIγ˜N≤PN,I(˜γ)≤2CIγ˜N,

(43)

andsearchforγ˜valuesthatsatisfy(43)withthehopethat(43)issatisfiedonlyforγ˜thatapproximatesγ.

InFigures9aand9b,weshowtheplotsof|γ−γ˜N,I|vs.NwithI=2andI=20respectively.Inthesenumericalexperiments(xi,yi)pairswererandomlychosen,a=0.9wasusedintheencodingonly(i.e.,thevalueofawasunknowntothedecoder),andγ=0.700067.Moreoverwechose󰀴isuchthattheleadingcoefficientsofpolynomialspN,ihavethesamesign,andγ˜N,Iwastakentobethemedianofallthevaluesthatsatisfy(42).ThisexperimentwasdoneforI=2,I=5,I=10,andI=20,100timesineachcasewith

(󰀞)

differentsetsof(xi,yi)pairs.Figure10showstheworstcaseapproximationerror,max󰀞|γ−γ˜N,I|,versusNineachcase(I=2,3,5,10,20).Hereγ˜N,Iistheapproximationobtainedasabovefromthe󰀳thexperiment(󰀳=1,...,100).WeobservethattheworstcaseerrorcanbeverylargewhenIissmall,i.e.,whenweuseasmallnumberof(x,y)pairs(althoughinindividualexamples,onecanhaveverygoodestimatesasseeninFigure9a).Ontheotherhand,usingalargenumberof(x,y)pairsmakestheestimatessignificantlymorereliable:weobservethattheworstcaseerrordecreasesexponentiallyfastasNincreases.

Remark:Notethatrobustnessremark4)abovehastobeadaptedinthiscase:γwouldnolongerbeallowedtovaryfromonesamplingintervaltothenext,sincewewouldmostlikelyobtainourdifferentpairsfromconsecutivesamples.Somechangeofγwouldstillbeallowedwithouthurtingthealgorithmifitweresufficientlyslow.

Adifferentapproachtodeterminingγapproximatelyfromencodedsequences(bn)and(cn)isproposedinthenextsubsection.

B.Analternativetoexhaustivesearch

µµ

Inthissection,wepresentafastalgorithmtoestimateγusingthesequencesb:=Eγ,δ(x)andc:=Eγ,δ(1−x)

µ

wherex∈(0,1)andEγ,δisdefinedasbefore.First,wedefined:=b+c,andrewrite(16),theconstraintofthemainlemma,as

0≤PN(˜γ)≤2Cγ˜N(44)

󰀅jwherePN(λ):=1−Nj=1djλandN≥k=min{j:j∈Nanddj=0}.Wethenhavethefollowing.

(󰀞)

13

Proposition11.Letkbeasabove.ForN≥k,PNhasexactlyonerootγNin[γ,1].Moreover,γNsatisfies|γ−γN|≤C󰀄γNwhereC󰀄isasdefinedinLemma4.

Proof:First,notethatPk(λ)=1−dkλkhasarootatγk:=(1/dk)1/kwhichsatisfies0<γ≤γk≤1.(Recallthat,byProposition7,kcannotbearbitrarilylarge.)Moreover,forN≥k,PN(λ)≤Pk(λ)forallλ>0(sinceeachdjisnon-negative).Thus,PN(γk)≤0forallN≥k.󰀅jOntheotherhand,foranypositiveintegerN,wehavePN(γ)≥1−∞j=1djγ=0.SincePNiscontinuouson[γ,γk],bytheintermediatevaluetheoremPnhasarootin[γ,γk]⊆[γ,1].Also,sincePNisstrictlydecreasingforN≥k,thisrootistheonlyrootofPNin[γ,1];wedenoteitbyγN.Finally,Lemma4impliesthat|γ−γN|≤C󰀄γN.

Proposition11showsthatifwecanapproximateγN,therootofPNin[γ,1],byγ˜NwithaprecisionofO(γN),then|γ−γ˜N|willalsobeoforderγN.SincePNisa’nice’polynomialinthatitisstrictlydecreasingon[0,1]withastrictlydecreasingderivative,wecancomputeγNwithanarbitraryprecisionusingNewton’smethod.Asamatteroffact,

Proposition12.LetkbeasinProposition7,andsupposeN>k.Chooseγ<γN<1,andcompute(γN)Ll=0via

(l)

PN(γN)(l+1)(l)

γN=γN−

(0)

(l)

k−1(1−γ)2.

Nk+2γ

(0)

Remark:Wehaveimplicitlyassumedthat,eventhoughγisnotknown,itisboundedabove,awayfrom1,bya

knownupperbound.Notethatthisisaveryreasonableassumptioninanypracticalsetting.(Ifdk=2,wecanof

(0)

coursetakeγN=γk;ifdk=1,γk=1however.)

󰀄(λ)<0,andP󰀄󰀄(λ)<0,sothatProof:Forλ>γNwehavePN(λ)<0,PNN

0=PN(γN)=PN(λ)+p󰀄N(λ)(γN−λ)+

1

󰀄(λ)||PN

≤λ−γN,

(l)

forallλ>γN.AneasyinductionargumentthenshowsthattheγN,computediterativelyfromthestartingpoint

(0)

γN>γNsatisfy,foralll,

󰀁

󰀁P(γ(l))󰀁NN(l)(l)(l+1)

γN−γN≥󰀁=γ−γ,(48)NN(l)󰀄󰀁PN(γN)sothat

0≤γN

(l+1)

−γN≤γN−γN.

(l)

(49)

Ontheotherhand:

1)Wehave

󰀄

PN(γN)=PN(γN)+PN(γN)(γN−γN)+

(l)

(l)

1

14

󰀄(γ)<0,implieswhich,asPNN

󰀁

P(γ(l))N󰀁󰀁󰀁N󰀁

k

dλ

(λ󰀆∞λj)

j=0

=2λk−1

k(1−λ)+1

2,

weget

1

|PN󰀄

(γ(l)N)|

≤2

(1−

γ(0)N)2

Combining(51),(52),and(53),weconclude

󰀁

󰀁󰀁PN(γ(l)N)P󰀄(γ(l))≥C(γ(l)

N−γN),

NN

whereC:=

k

󰀁󰀁P(l)

N󰀄(γN

)≤(γ(l)

N−γN)(1−C).

Corollary13.LetγN,γ(l)

N,andCbeasinProposition12.Then

γ(l)

N−γN≤(1−C)l(γ(0)

N−γN).

Therefore,forl≥

1

(53)

()

(55)

(56)

15

Thecaseofunknowna

Finally,wereturntothecasewhenthevalueofaisunknowntothedecoder.WedefinethepolynomialPN,Iasinpointb)ofSectionIV-A,andtrytoapproximateγbyfindingarootin(0.5,1).Recallthat,ourgoalindefiningPN,Iwastheexpectationthatithasasinglerootin[0.5,1],andthisrootislocatedatapproximatelytherightvalue.Clearly,thisisnotguaranteed,howeverournumericalexperimentssuggestthatPN,IindeedsatisfiesthisexpectationwhenIislarge(e.g.20inournumericalexamplesoutlinedinpointb)ofSectionIV-A.Also,notethatPN,Isatisfiestheconstraint(43)atanyofitsroots.So,computingitsroot(s)shallnotgiveusanyestimateofγthatisworseoffthantheestimatethatwewouldhaveobtainedviaexhaustivesearchusingtheconstraint(43).Motivatedbythediscussionabove,werepeatthenumericalexperimentofpointb)ofSectionIV-A,onlythistimeweestimatethevalueofγbycomputingtherootofPN,IviaNewton’smethod.InFigures12aand12b,weshowtheplotsof|γ−γ˜N,I|vs.NwithI=2andI=20respectively.Inthesenumericalexperiments{(xi,yi)}Ii=1wererandomlychosen,a=0.9wasusedintheencodingonly(i.e.,thevalueofawasunknowntothedecoder),γ=0.700067(againonlyusedintheencoding).Moreoverwechose󰀴isuchthattheleadingcoefficientofeachpolynomialpN,ihavethesamesign.Wecomputedγ˜N,IbyestimatingtherootofPN,Iviaa10stepiterationNewton’smethodwiththestartingpointγ0=0.8.ThisexperimentwasdoneforI=2,I=5,I=10,andI=20,100timesineachcasewithdifferentsetsof{(xi,yi)}Ii=1.Figure13showstheworstcaseapproximation

kk˜N,Iistheapproximationobtained,aserror,maxk|γ−γ˜N,I|,versusNineachcase(I=2,3,5,10,20).Hereγ

above,fromthekthexperiment(k=1,...,100).WeobservethattheworstcaseerrorcanbeverylargewhenIissmall,i.e.,whenweuseasmallnumberof(x,y)pairs(althoughinindividualexamples,onecanhaveverygoodestimates).Ontheotherhand,usingalargenumberof(x,y)pairsmakestheestimatessignificantlymorereliablesothattheworstcaseerrordecreasesexponentiallyfastasNincreases.

REFERENCES

[1]I.Daubechies,R.DeVore,C.G¨unt¨urk,andV.Vaishampayan,“A/Dconversionwithimperfectquantizers,”IEEETransactionson

InformationTheory,submitted.

[2]I.DaubechiesandR.DeVore,“Approximatingabandlimitedfunctionusingverycoarselyquantizeddata:Afamilyofstablesigma-delta

modulatorsofarbitraryorder,”Ann.ofMath.,vol.158,no.2,pp.679–710,September2003.[3]C.G¨unt¨urk,J.Lagarias,andV.Vaishampayan,“Ontherobustnessofsingleloopsigma-deltamodulation,”IEEETransactionson

InformationTheory,vol.12,no.1,pp.63–79,January2001.

¨Yılmaz,“Stabilityanalysisforseveralsigma-deltamethodsofcoarsequantizationofbandlimitedfunctions,”Constructive[4]O.

Approximation,vol.18,pp.599–623,2002.[5]C.S.G¨unt¨urk,“One-bitSigma-Deltaquantizationwithexponentialaccuracy,”CommunicationsonPureandAppliedMathematics,

vol.56,no.11,pp.1608–1630,2003.

[6]N.Sidorov,“Almosteverynumberhasacontinuumofbeta-expansions,”Amer.Math.Monthly,vol.110,pp.838–842,2003.

16

10110110N−110−1|γ−~ γ| ~ |x−x| N10−310−310−5051015N20253010−5051015N202530(a)(b)

Fig.6.Theperformanceofthealgorithmwhenimplementedwithx=π/10anda−xwitha=0.9.Herethevalueofawasknownbythedecoder.

10.80.60.4p0.2(x) 300−0.2−0.4−0.6−0.80.60.7λ 0.80.90.10.05p(x) 300−0.05−0.10.60.650.7λ 0.750.8(a)(b)

Fig.7.(a)Thegraphofp30(λ)forseveral(x,y)pairs.Thedashedcurvesaregraphsof±2Cλn,correspondingtotheconstraintof(42).Weobservethat(42)issatisfiedforvaluesγ˜closeto1aswellasclosetothetrueγ.(b)Azoomed-inversionof(a)toλ∈[0.6,0.8].Inthisintervalandforthese(x,y)pairs,(42)issatisfiedinonlyasmallneighborhoodofthetrueγvalue(γ=0.700067inthiscase).

17

0.080.04p(x) 030−0.040.60.650.7λ 0.750.8Fig.8.Thegraphofp30(λ)forseveralother(x,y)pairs.Thedashedcurvesaregraphsof±2Cλ30,correspondingtotheconstraintof(42).Weobservethatforthesepairs,p30hasmultiplerootsin[0.6,0.8]insmallneighborhoodsofwhich(42)issatisfied.

10−1I=2 10−1I=20 10−210−2 ||γ−~γN,2~|γ−γ N,2010−310−3|10−410−410−510−510−6051015N20253010−6051015N202530(a)(b)

Fig.9.Theplotof|γ−γ˜N,I|whereγ=0.700067andγ˜N,Iwasestimatedasdescribedinpointb)ofSectionIV-A.In(a)I=2,andin(b)I=20.Inbothcases,theexperimentwasrepeated100timeswithdifferent{(xi,yi)}Ii=1;eachgraphshowstheresultsfor3typicalexperiments;dashedcurvesshowtheworstcaseerroramongthe100experiments.

10−110−2|γ−~γ|N,I10−3I=210−4I=5I=10I=2010−5101520N2530Fig.10.Theworstcaseerror|γ−γ˜N,I|forI=2,5,10,20,among100numericalexperimentsconductedineachcase.

18

01010−5 ||γ−~γN10−1010−1510−2002040N6080100Fig.11.100experiments,conductedwithrandomlychosenxandplottedtogether.Hereγ=0.700067,andthedashedlineisthetheoretical

upperbound.γ˜NwascomputedbyestimatingtherootofPNviaNewton’smethodwith10steps.

551010100100~|γ−γ N,20|~ |γ−γ|10−510−5N,210−1010−1010−1510−1510−2002040N608010010−2002040N6080100(a)(b)

Fig.12.100experimentsinthecaseofunknownawithγ=0.700067.γ˜N,IwascomputedbyestimatingtherootofPN,Itowhicha10stepNewton’smethodalgorithmconverges.In(a)wesetI=2,andin(b)I=20.Thedashedcurvesinboth(a)and(b)aretheworstcaseerrorsamong100experimentsforeachcase.

105100~|γ−γN,I|10−510−10I=210−15I=5I=10I=2010−2002040N6080100Fig.13.Theworstcaseerroramong100experimentswithunknownainthecasesI=2andI=20.