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
determinesfvianπ
).(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):=supf−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/λ)vian
−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)NtimesforeachvalueNsample−jg(n/λ)=[1+f(n/λ)]/2,wheref∈S,willyieldanN-bittruncatedbeta-expansion{qn:=j=1bjβ}thatwillsatisfy
|g(n/λ)−qn| Beforedefiningthe“beta-encoderswitherrorcorrection”of[1],wewanttorepeatthekeyobservationthatisusedin[1]toconstructtheseencoders. Proposition2.Letx∈(0,1)andb1,b2,...,bJbearbitrarysuchthatbj∈{0,1}.If 0≤x− Jj=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=1j=1 (19) (20) Wewillnowestimatetherighthandsideof(19)separatelyforthecaseswhenNislargeandwhenNissmall: 1)Setting∆=C1γN,andsubstituting(20)in(19),weget |x−x˜N|≤C1γ =C1γ NNj=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− Nj=1 (bj+cj)γj≤2CγN, (24) whereC=1+µ+with|δ|<≤µ. Proof:ByTheorem3,weknowthat 0≤x− Nj=1 bjγj≤CγN, (25) and 0≤1−x− Nj=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− nj=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(recallthatistheboundonδ;Figure4usedasimulationwheretheδjdidnotevenremainconstantfromonesampletothenext;theywerepickedrandomly,uniformlyin(−,)). 2)Wecanstillrecoverthevalueofγwiththesameprecisionifinsteadofxand1−x,thetransmittedbitstreamscorrespondtoxand1+ρ−xaslongas|ρ|≤0forsomesufficientlysmall0.Moreprecisely,if0≤20≤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.Thisobservationmeansthatifthereferencelevelcanbekeptfixedwithinaprecisionof0,thentheschemestillworksuptoN0∼log0/logγ. 3)Ifweusethepairxanda−xinsteadofxand1−xforsomea∈(0,1),ourapproachstillworks,providedthat0≤x≤aandthatweknowthevalueofa,atleastwithaprecisionof0thatsatisfies0≤20≤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≤ Nj=k djγj−k≤2CγN, withCasinProposition6.Thissuggestswereplacetheconstraint(16)ofLemma4with −2Cγ˜ N ≤ Nj=k djγ˜j−k≤2Cγ˜N (42) andexpectanyγ˜thatsatisfies(42)willbeanexponentiallypreciseestimateofγ.Butsinceinthiscasethej−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.ThismotivatesustocomputethepolynomialsI pN,icorrespondingtoseveral(xi,yi)pairsasabove,andconsiderthepolynomialPN,I:=i=1ipN,iwherewechoosei∈{−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.MoreoverwechoseisuchthattheleadingcoefficientsofpolynomialspN,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,Iistheapproximationobtainedasabovefromthethexperiment(=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γNwhereCisasdefinedinLemma4. 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(λ)+pN(λ)(γ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))NN 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).MoreoverwechoseisuchthattheleadingcoefficientofeachpolynomialpN,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. 因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- yrrf.cn 版权所有 赣ICP备2024042794号-2
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务