• 192
`
`IEEE TRANSACTIONS ON INFOOO
`
`"t-
`' tittOii.r/voL tf-31, NQ. 2, MARCH 19.85
`-~ ... • ·, . , . -~
`
`-~ '·; ':.
`
`: . -
`
`Abstract-A model Is proposed for the situation where M users share a
`common communication resource but, because of unknown time offsets
`among their clocks, cannpt transmit their data packets In a time-sharing
`mode and, because of the. lack of a feedback link, can never detennlne
`these time offsets .and alS? can never be sure of the outcomes of their
`Individual packet transmissions. Each user is .required to make his packet
`transmissions at times detennlned by a protocol signal that Is Independent
`of the data to be sent.
`The capacity and zero-error capacity regions of this channel are de·
`termlned for both the un$ichronlzed and slot-synchronized cases; these
`four regions are shown to coincide. It Is furth~r shown that a dense set of
`rate points on the outer boundary of this region can be achieved In the
`slot-synchronized case. Sl1eciflc constructions of protocol sequences for
`achieving these points are given, and. the technique of "decimation decod·
`Ing" Is introduced for Identifying the sendet of each successfully trans(cid:173)
`mitted packet. Maximum-erasure burst-correcting codes over an alphabet
`of arbitrary size are constructed and shown to suffice for reconstructing the
`packets lost in "colllsions" when these protocol sequences are used.
`
`t
`
`INTRODUCTION
`
`sions eventually into any_ desireq :synchronism. We shall
`demonstrate that "reliaqt~.· ·i~HPW,::'.~~ss com:munications
`is indeed possible without ii''fee<lback,link.
`In Section I~,. we descril>,C, tne chatinet model tha~ will be
`used thro~~ · thl,~·.PflP.c;~;, ~~ifo~)lJ(JP!r~~~~ ·. f Q\lr differ(cid:173)
`ent capacity regions a,.nq ; ~HW~ti; ,fh~. ll1~ULre1m~t of this
`paper,· viz. that ,th~e .• fpur}regigns coin~ide. ·Section IV
`gives the rC<Iuir~: pro{,(·"Af~fir~H~~l~·:~~uajcation ·out(cid:173)
`side the capacity:~~gi()n, .i~,1slmP!:>~~iht,e:.s~µon.Y gives· a ·
`constructive. schem,e f m: 'Si~~g mt~q1Jt ·ertoHt rates on
`the outer bo.undary of _tµ~~.~~p.~9-ttr.egipn, ~4e,n. ~he·senders
`are slot-synchronize<j.'. ~~~ .. qp.,YJ;~y~s ~ SIJDllar. construc(cid:173)
`tive scheme-.for signaling witho~t 1ertor at' all rates in the
`interie>r 'of ·w~.~P#i~~~~~gt~~:J~·~w~;.riit1y;µ,~~Yiicflr~niz¥·'
`case. ~inru,1y, ~ Sectign. Y}lf\v~": ~lai:e th~· .r~ut~ 'of thi~ i
`paper m· histoncal perspec~iy~1:iµid)\Ve•make some remarks
`. abou't the 'significance 'and';prOpet_':interPtCtatiort of these'
`
`.
`
`!~u::;~~:·:~~:;r=~r~~~: resril~ •.. ·•. !/,\;:·~~~~ /' ' :~
`
`sages1 shared a .. comm.· ori comm. uni.cations resource on' a· Channel moRets g~per~Y,.~~~Y-ei.~WP14istjnctJea~ures·: J)
`·th. e_·_ "~.,_.~. h_ ffii.t ~rilil.~.'\. '~_toHabili_ • .. · ·_:. law_·. -:(or: de-. .
`s ecifiqatio. n . o.··.r:.
`~::;~~~s~:d~~lt~!~:s~s~~lat~~h~~m;~~ t~rministic'iitte)'_ib~:.tti¥'.6'r-lti:~!t:·::"·Plpµi(s)··:ve%t··ilie•·chan-
`, '"tt~ts'.b~ :¢h8Jlnet
`might be preferred but is impracticru because of the diffi- nel inp\it(s); 1:an4:·,.),~p69!.
`usage.;·T11~~fir_st:;~f.·~~.,, .. ~
`.J~#µ.O~'"fiiig11(~ell·:~~
`culty in synchronizing transmission from the sei;iders. Satel-
`pr~:insta,n~dhe.baSic
`lite_ relay system's an.''d mobile radio,· systems are instances called'the·~'ba8iq"-ch ,,
`where such s~~~~~tion .. Qf_<;t11~-~~P2.~~~!§ may be well- channet• ~()~~1·:~~~t
`~'.:~e(#i#~PrYless!ad~ }
`/eoi,l~ti,ajtl,t;on-'ch~el .·i,1
`rl
`ditive·Oaussian,;-ppise ..
`nigh iµipossible.
`. tw~d::=:fs 1:!~~:,~~/; ~~~i~~~ :~: ~=-*~~~~~~~. 1~~~~$·~
`
`.
`
`.
`
`1.
`
`1
`
`thought that "feedback" is required in such systems so that on the, 1,t1agtl1tU,~~.1:.9~·1~~r.~.iffH%~;rllt.!~~~~; ~N9!~: ~lu~L tqp J
`senders can retran~mit ·packets after being notified via chani:el ~qgel~l i~ · ·~?F(:$9t,!'.lP,l~f~Jt.~~Ri\Hb'l'~ti.~.l11t: ·the ,'\
`capacity, ·~··P:Ot;.~m,pµtll
`' .~,;•.!;p,:QS.t~aJ.'*'911 t~~ ·.;
`feedback of their loss in collisions.
`.·.
`
`~:::~a:=:~:~:::.~= :::;~~~~,~:~tYJt'f:;''.'ir:o/;;;;' ·.·
`
`·. · ..
`
`their transmissions'. ,'This viewpoint' requires us to rule out
`the presence of a feedback link, as such feedback could
`otherwise be exploit~ by the users'.to bring theirtransmis-
`
`The basic:ch.iti\11el;m94eJifor/ihe!:~o//ision c~am~el without .
`feedback (CC\y/A~~fiS,.,i.Ji,~§ifa~~J~'F.i.g.:lj.'Oµr inte~t
`to model the situation·ffi·,wfilcfrthere are M channel users,
`.~~~:~~·;i:ni.:::;.~ ;~.~::!: .~~:
`
`. . . .,,,. ::.:;;ijj,~[ :t~f~,C> : , . . · ..
`
`Information Theory. Co#ference, Oberwolfach, Germany, April 5-10,
`1982, and in part at th~ IEEE International Symposium on Information
`Theory, Les Arcs, Fran~, June 21-25, 1982.
`J. L. Massey is with~~ Institute for Signal and Information Processing,
`Swiss Federal Institute of Technology CH-8092 Zurich, Switzerland.
`P. Mathy5 was with the Swiss Federal Institute of Technology, Zurich,
`Switzerland. He is now with the Laboratory 'for Information and Decision
`Systems, Massachusetts Institute of Technology, Cambridge, MA 02139,
`USA.
`\..
`
`Pet., Exh. 1018, p. 1
`
`

`
`,t:f!~~~~t~tt~~~%W=~::
`
`. 'each.'of wliich ~ii:Sii.hlt~':~~Itd~' a u'packet .. 'ol some meed
`duration~: say· :x aecontfk tiut;othcrivise is silent. Thus the
`~nput :· sigiial '.~/( ~ >;t~e#ie~~i.;(i_ri •fig;J_ ~.be zero e;cept
`an those · intervals·' of·JengtlLT .-'second!!'' where user I is
`actually seridirig: a packet;::tfi•.~which 'intervals • we assum·e
`only that ., Xt(t> is. }titil~'..~dHa~ly r~grtizable .'nonzero
`waveform:')Ve ~~~~~.:lh~~:i.~iP.~~~epi~, Q · p.~~sible values
`thor. so~e f~ed u~t~~~~;·~6'?;.~~tJ;an~. ~~ ?ef1n_e log2 Q bits
`'ll of _information to be a· packet pf,mfon:natton. -. .
`·
`· Our intent fui'th~r :is1;fo· iil8ttei the ~ituatioi{whete there
`_· is. ~o eorrimon ~itne ~~te~~?ci; 1b~twee#·!any of 'the users or
`.'_the ·receiver. ·Tc>Ji:chie\i~ 'flii~~)ve ;iritto~tice the tirnt offsets
`81,82,·.-.·.BM::as sho~11ri) 1:ig;·J·lri.'Fig;l, , x 1(t) denotes
`user-i's. transtajtt¥'; s,i~~ .. ;a9µ(0\vn )qcal, tune .. t, while
`.· y(t) denotes : the, r~ived/. ~lgiial at ~ the receiver's . local
`·._ ~7h!' ti~~ _of~set .8, ~~k~1~,·~~~~hi~rpt~t~~--~-t~e' difference
`, ·. ~etwee~ ,_the_ time ·'.~,hq'Y11~9I}Yi!pe.i. r~ejyer's _clock .. and the
`,•~: tun.~ sh()wri ~p us~~),i.:~·ir1°?~~~~~ tpa~ ,a, sign~ from user ;,
`F: r~1ved a~,t1me ~iP~illi9ffm~y~r';s. C?lqc~,-~as~ac~uall~ sent
`'; . at time t "-8, on use~~ (:~, cl,o,c.kr,(1'1ote·;that'.Jhis s1tl1ahon is
`\; entiiely , equivlileiit".t~::i~s41Iµ#g.Jiiaf'.·· ihe ClockS':at user ;
`r_. and at th~::~eceiver:ifr~ petf¥ltY'.sypcifr~nitea~·but. that the
`~::: signa~: froin ·. ~sei';': ·1:is. iaeUiY.~::;hy:· :8jj:ti~fdie . reaching the
`;· receiver: It does ~of)i~Hi~o· 1~hifil< bf, ·8i hS the'propagation
`r~ delay for .user i's.signal.:4p'fcfvided otje:.ifWillingto·allow
`, j\~~g~tive, d~ta~9 Jh~'..}~~;,~.opi~}ri, ~~r:,~Qtie~ is 'that ·all
`:• Jt1me ·()//sets ·are,. unkno_~'.l ~lb:(dl/;· users! c an9 :•can'. never be
`;~.learned its 'the' tlsef$ if~itft•;iio;t~dback'frdrii: the channel,
`:: •. and are . also Unknown 'ih ·ad\iance'to :the receiver..
`.
`..
`~- · _ •-·. Our ! mten,t: · rie#·:· l~ i.'t6;i IJj!idet': tli~:< situation·_· ill., which
`p_ackets th~t ?verH1p '~fl~~·r~ivef;p~a.ily oi eompletely,
`are completely destfoyeO •by\ suCh "collisfon '" :Me are · re(cid:173)
`ceived>~?r-free 1#{'.~~-;-~bs~~~~ra,'.'C()llisi'on; ·A ·packet
`sent by user i·'starting at:firiieCll'i. ~Wiu ··oe · assumed to Collide
`with a packet\senfby· J~er 'f~farting; ai'time ti,' if and only
`if
`' . . '
`... -,\ .. \
`/,,:.--:. ,_\,,, •.'
`.
`.
`'
`
`· ·· · 1<t;''#'.~H@tJ'-81n~ti .
`(1)
`i.e ..... _if. an~ ;001~)~ ;~R~!·~~t~§~'.~tfi~~en_~~.;b~i~~~ receipt of
`their 1eadmg, e<1ges; i~ . less; Uii\tL the packet ouration. We
`assume that . the,,~~iyect1,$i~~l ;·jitt),::at\-ihe . .'output of the
`l~~!~t~~~:~~~~~~~w~M~;-~~w~~~d~~-
`-~~~
`ce1pt of a 1'.loa:i~lhde<i.~ pa~k~t; 2) Js · recognizable as a
`·~garble" (and. notliliik ·mor~)':~urlng receipt .of any _collided
`packets; 3) is reeo~bfo';'as.:.~~silence';, .durlng periods
`whe~ no packet (collil;le·~i~~f#ot)_ is received. (Tobe fully
`precise, we need also ~o. assume that, the receiver is able to
`recognize . the boundary bet\y~n. packets received success-
`' . runy and preeise1y: adj~~iiUctoiie arioiher.) .. : .
`.
`.. V{e coinl>Iete our ba.,Sic:~iia~~eLrnodet by (Ji~tiiigwshing
`two cases· for the po~sible'.:.:Values of; the unkriowD. time
`'\~" :_~i,:\:·;'1_:,~}~{i>t _> '<:: :·-: .. ; ,;:( · .: : · .
`of~sets,. :~~ety> .
`. 1)1 the s/ot-synch'.o?,'~f~; ~~~J~. 'Y~ch · th~. tlme offsets
`81,82, • • ·, 8M are arihtrary integer multiples of T,
`·
`.
`. . .
`'·' ' -"'.!/\(_. ' .
`.· ...
`
`193
`
`2) the unsynchronized case in which the time otfsets
`81, 82 , • • ·, 8M are arbitrary real numbers.
`We define time slot n to be the semi-open interval
`nN :S: t < (n + l)T, where local time is understood. In the
`slot-synchronized case, it user i sends a packet precisely
`within his own time slot n, then it will be received precisely
`within the receiver's time slot n + 8/T. Thus, if all users
`align their packet transmissions within time slots, collisions
`will result only when received packets completely overlap.
`In the unsynchronized case, however, the users have no
`way to avoid collisions that result from only partial over-'
`lapping.of packets.
`
`B. The Constraints on Channel Usage
`The constraints on channel usage for the CCw/oFB are
`illustrated by Fig. 2 which shows the detailed structure by
`which user i is permitted to use the basic chanriel of -Fig. 1.
`Each user has an independent information source which,
`upon demand, produces a Q-ary symbol to be transmitted
`to the destination.
`
`o-ary
`INFORMATION
`SOURCE
`
`Fig. 2. Constraint on channel usage for collision channel without
`feedback.
`
`mitted only via the contents of packets and not also via the n
`
`In actual random-access systems, "information" is trans(cid:173)
`
`timing of access attempts. To say this in another way, the
`randomness of the "information" is not used in the selec(cid:173)
`tion of transmission times. Such a prohibition has 'the ·
`desirable effect that system performance does not vary· · -
`with the statistical nature · of the information transferred.
`We wish to impose such a prohibition against the depen(cid:173)
`dence of starting times on information to be transmitted in
`our channel model. We do this by requiring that each user . ( /
`have a protocol signal generator as shown in Fig. 2 whose
`, ,
`. output is a predetermined periodic waveform. that · com'.'
`pletely specifies the · transmission times for that user •. this
`protocol signal s1(t) for user / . has period '1"1, has value
`either zero or one for all t, and takes on value one only
`over semi-open intervals whose :lengths are integer multi(cid:173)
`ples of T. The encoder for user i is required to emit
`packets whenever s1(t) - 1 and is required to be silent(i.e.,
`to emit the zero waveform) whetjever s1(t) .. 0. We assume \
`that the users may jointly choose their protocol signals and
`that their choice is known by the receiver.
`It may seem strange that we have included an "on
`demand" information source in our model, as one usually
`thinks of a random-access system as the appropriate way to
`transmit many sources each of which only infrequently has
`something to say. However, it seems desirable when possi·
`ble to decouple the channel model from the source model ·
`
`Pet., Exh. 1018, p. 2
`
`

`
`194
`
`_
`
`IEEE rmnsacnons ON lN_i‘9ltMA'1'|
`
`:
`.
`
`'1:
`
`so’ that "capacity” does not depend on the source. One ’
`might view our “on demand" source model as a kind of
`worst-case assumption that all of the sporadic sources are
`active and hence each has a nonempty queue of messages
`awaiting transmission. Capacity can thenlbe interpreted as
`the best possible performance for heavy loading of the
`system. Effectively, one makes such an "on demand" source
`assumption when one asserts, for instance, that the capac~
`ity of a time-division multiple-access system is one packet
`per slot. At bottom however, we must admit
`that our‘
`channel model
`is aimed primarily at determining how
`
`.
`
`%} muchlossresultswhenMsendersshareacommonchan- blockcode;of-“len
`
`._
`
`1
`
`nel but are prevent
`from time-sharin this channel b
`(.‘
`'
`what appears to befi.’/ilhe’mildest possible? assumption thali Ts 1)_‘b]°d,‘: »°f~“_ °'.t‘svi-‘i
`prevents such time-sharing, namelyflack of a common time..;}
`QSS 9"='u‘°’.e'r.r-.i grew.
`rem_encc_
`,
`5:5’.
`for transmission during,
`izmly “fies-Ni.‘-1;‘
`It may also seem strange that we have required dc-$13
`"eii9utput' signalfrecon-s .
`-
`
`
`
`terminisitic protocol signals (and indeed periodic oiies) to
`2) .a
`- 6-r 939’ ‘om
`
`'oi".’user.” i.’s"“'QSS_‘
`V
`5 control access in our model of a random-access _systern.
`average paeketierr
`y:at't'n'ost‘c; regardless‘ '
`l
`
`A
`~
`-1! Note, however, thatsnothing prevents user i from choosing
`,
`_ _ _
`V
`_
`_
`I
`.
`.
`.
`v
`-.
`fife ti
`‘if".13
`.' the first period of s,(I) as a realization of some appropriate
`8 ’§?T~.v. f§”'
`V
`!
`5,
`.
`I. random process. The point isthat the random process that
`'1"he-aero_7erjr'or' capa
`-
`-n,.._;i-.a4g(.s
`.
`1'
`1: controls transmission time should not depend on the infor- niied CCW/OFB s .def1ned-
`I
`l
`
`ified 'I.‘h_e,ca
`‘ rnation source; thus ,we can conveniently consider that any
`that (".539 ‘issp,
`i‘
`random experiment’ used to produce. the protocol signals
`5 has been carried out in advance of performing the random
`{experiment used tolproducethe output sequences of the
`linfonnation sources. We have required the protocol se-
`“ quences to have finite periods for analytical convenience,
`‘ but we have plac_ed,,no finite boundon these periods_so this
`is no real limitation‘ on the model.
`.
`The purpose of ihe encoder in; Fig. 2 is to code the
`output of the Q—ary source into packets for transmission so
`that the receiver will be able to reconstruct the output of
`this source from the received signal y(() with an accept-
`st;
`sn‘-,R.,’.,_'.1sv
`_
`ably small error probability. The receiver must, of course, R',.
`so reconstruct each of the M sources.
`region. Thtis;»we.Ican.
`déffia
`.
`ity (or zero-errorcapacithy)‘
`
`
`
`;
`
`’
`
`
`
`
`III. CApAcrn' REGIONS AND MAIN Rasuurs
`
`
`
`‘
`'
`
`(,,__.._____
`
`
`
`In proving coding theorems for the CCw/oFB, we shall
`always assume that the “on demand” source for each user
`is a Q-ary symmetric source (QSS), i.e., a source whose ngalct‘
`output digit is equally likely to be any of the Q possi
`e
`
`-
`
`.
`
`4
`
`.,,
`
`,-
`
`
`
`
`
`
`)i\‘ values, independent of‘its past history. The QSS has an
`
`“
`
`3I
`
`me:
`
`_.n _
`
`.
`
`‘N u]
`
`tdn.;
`
`information rate of logzQ bits per symbol or, equivalently,
`
`outer?-boiipdary ‘ii’
`one packet per symbol.
`‘
`..r‘e‘éii<‘>'r'=.'.fj<.>fr?é v
`r
`
`b°und9r'vj_‘9t "age ..
`For the CCw/OFB, it is convenient to define the duty
`multi-user."‘ch'ann'e
`_"ti'o_n‘_of'l:tl1e.’
`.
`~~
`factor p, for user i as that fraction of its period during
`
`e’ shall fde-‘lg f
`,.
`'
`caP#?=i*.Y'..(9‘rY
`xJ
`which the protocol signal .r,(t) is nonzero, i.e., the fraction
`
`.
`.,,
`"Oi?-P°int’s,9!!;
`‘I of time during which user i is actually transmitting packets.
`
`_
`_V
`‘.1
`=
`g
`,,
`..
`,
`"
`C =
`.‘:
`i__ ,,
`‘K
`‘. Of -course, 0 s p, S 1. Note that if user 1‘ is transmitting
`‘
`information from his QSS at a rate R, packets/slot, then °f'{t]::;§fli1:i“g::sbuagfifieégrsafifigigz. A
`
`he is actually transmitting iriformation at a rate R,/p,
`‘hat.me._,.§1loévaS1i-‘fiflfi
`ify;
`‘
`-
`"
`=
`packets/slot during those times that he is actively using the
`.
`-
`r
`A
`«.'
`‘-
`«-
`
`channel.
`J
`"
`"
`V
`In general, by the k‘~.‘capacity region” of any rnultiuser
`‘channel, one means the set of all joint user rates suchthat
`it is possible to communicate with arbitrarily small (posi-
`tive) error probability at any joint rate inside this set, but it
`‘I
`Kin .N»
`
`
`
`2‘
`
`
`
`Pet., Exh. 1018, p. 3
`
`Pet., Exh. 1018, p. 3
`
`

`
`The region </ is not convex for any M ~ 2, as follows
`from the M = 2 case by considel"ation of th.at portion of
`the outer boundary corresponding to probability vectors
`with .Pi= 0 for 3 ~I~ M. This is the first instance known
`to us of a capacity (or zero-error capacity) region that is
`not convex.1 As Shannon has pointed out [1], all capacity'(cid:173)
`(and zero-error capacity) regions are convex if it is possible
`to time-share the coding schemes used to approach individ-
`
`:f ..
`ual rate points of the region. The fact that</ is not convex J ~ 11
`for the M-user CCw/oFB when M ~ 2 must thus be seen (. ·,~.
`•. {'· l'·
`as a consequence of the fact that the_ lack of a common
`time reference prevents the users from tim~-sharing differ-
`~~ ~
`ent coding schemes.
`f'{ ·
`A rate vector R in a capacity (or zero-error. capacity)
`region is said to be achievable (cf. [5, p. 5]) if .R. satisfies
`
`(3)
`
`(4a)
`
`~~~t~~£f~,;:'.¥t~~R,t; , .·.·.
`
`b) f~~i~?::;~;t~i:i~~;~~gfE
`.· (4
`
`boundary.
`
`, and ea~h.such ('.';is,tieiC.t:miliep ... ~Y·a µni,que such p.
`result' is that, for the slot-synchronized CCw/oFB, the
`: 1 ... We reiiiiik·tlilif'CClndiU$ii§~~{4a) iti{cl (4b)'are·,equivalent outer boundary is everywhere dense with achievable rates.
`~to saying that'piS·.~~~~f~~h,/li&:ti'Jc~ok·.Jiitis,:.'Thoorem 1
`Theorem 2: Every open neighborhood of every point on
`·J,states, that ther~}s: a'.{,~1nipie,:tjp~7tC?.'."ori~ corresp~ndence
`·
`· ,,:d'.;ipbirits"\on.·<'the 'outer·. ~~t~~;r.!~::a~fe 0:at~~e ~~~tac~fsore~:n~n</"'th:n~u~;;
`~ between:.:·probat>ility}' ·ec·~
`.. ·boundary :of':"l~;.;ii~1:;{~-.:JJ;;;:':·
`~;;'.!'.~.1;'::;~f;._t_i{i'!/;:t;:,t, ·:
`''.: ,·: ·
`, : · .. :f'ig. ·3 sli~ws th~'~egl~t\\,. -: .. i.tH~;k,+?Z,:tjser ¢cw/oFB.
`
`~_:\.'
`
`':. \~-'.'1.'i
`1·::.'··.f,
`.-:i·i.'..; l::'f!'·.·;!1' ·,;
`
`In a random-access system, one is ·usually rnost in-
`. terested in the "symmetric case" .where all users are signal(cid:173)
`ing at the same rate. Thus, we define the symmetric capac-
`ity, Csym• of the M-user CCw/oFB to be the maxinn~m rate ti:\
`r such that R-= (r/M, r/M,- · ·, r/M) is in</, Note that
`if there is an r such that C = ( r / M, r /M,. · ., r/M) is on.
`the outer boundary of</, then C,ym = r. But, from (3) and
`(4), ·we see that the choice p = (1/M, 1/M,- ·.·,1/M)
`gives such a C. This proves all but the final part of the
`following corollary.
`Coroilary to Theorem 1: The symmetric capacity of the.-.
`M-user CCw/oFB with M ~ 2 (whether unsynchronized
`or slot-synchronized and whether for arbitrarily small posi- ·
`tive error probability or for zero-error probability) is
`
`})M-1.
`
`Csym = 1 - M
`
`(
`
`packets/slot.
`
`(5)
`
`Moreover, the rate point (C,ym/M, C,ym/M,· · ·,Csym!M)
`is achievable in the slot-synchronized case.
`.
`From (5) one calculates, for instance,
`1/2,
`M=2
`M== 3
`= 4/9 = .444,
`= .3874,
`{
`M-10
`= .3678,
`M = 100.
`
`·C
`sym
`
`Moreover, Csym ~e<:~~a~es m.o!lotoaj~!:lUY as M increases
`and
`
`1
`c,ym-+ e'
`
`asM-+oo.
`
`{6)
`
`1 The "achievable region" of Wyner's wire-tap channel [4} is not convex,
`but this is not actually a capacity region as one of the coordinates is not
`, , ,,
`an information rate.
`
`· •.. .J
`
`; ~ ... ;~4' :t{:-~Xl);\'.i,f;" t1f t'p'c~et'~/~lat'l
`Fig. 3. Capacity reglon ~hv.io-u,;;r collision chann~l without feedback.
`;
`'
`' ," -"\1,:
`-. •" • ..... :.
`:
`''.
`•-
`'
`I
`1:.'._.· .. > :-.·~:t<'!·'(::~. ~{)1_:/: -:···;·
`< .. ,
`..
`'.,
`,.
`·= .
`.
`. , C 2 = (i ~ y) 2• Thus,'" the.·, o~t~r· boundary of. </ is just the
`(",set ofall points C ='.G.Ci; C2)'such that C~ O and
`"._ ;.ff(;'~7{E{~· L ·
`F:•;-.
`.
`L .·. The region</ in Fig;t.3::is~nJ{~~~ex, hrit:it is easy to check
`
`
`
`
`
`
`
`l:• .. ·.·.'.···,·,··.,· .. \~.~: .. ~~ ... t··.h.:.:
`
`
`
`.... :=.1.::·.~n.m.·~.~.····."[o .. :: l_ •. ~:.~.lli\i ... ·.·.·.u···:.! .. lt.·:·!·i·: .• ~ .. ~.i .. t·.~:.····'.~ .. :·:·'.~~ .. :.~.·.~_~u.d. =.•.·.~.v.:._;.~ili.~.'.· .. ·~.·.· .. :m.1'oo.:.:~
`
`
`
`
`
`.. :·:
`':· <o(. ~·;in·i'th:e•)first ~tofililtiiW£1S;loonvex>p tM·eorrectness of
`.
`r.:·ws.oorijebture··has ~~~*!b~&tihy:Pps((3Ji··:o.:
`
`•',_·<.,·-·::(·: ~~~-.. .{:-~ ;. __ -
`
`,;
`
`-
`
`·.
`
`_.
`
`...I
`
`Pet., Exh. 1018, p. 4
`
`

`
`''196
`
`The quantity 1/e is, of course, the well-known maximuhl
`throughput of the sl<:1tted ALOHA algorithm {6] for in-
`finitely many identical users. Thus, (6) oould perhaps be
`
`1/ie.
`1lfi: We remark here that Csym is a1so the minimum of
`
`E[s,(t - 81) TI it - sh '_ ~1)) .... 1 = p,fl (1 - p;) .. '
`· ·
`1.,.,
`1.,. 1
`
`·
`
`,
`~;· ·:,.:.,
`
`the inequality isr~uired ~yqie·r81?hhat tlte 'satlsfacti~n.'oi .. :·:~i;~o·
`~·.'::<tet<
`(9)forsomeidoes .notensurethat.the.packetbeingsentat
`reeeiver time i by; 'user /'.W,µf'p~i:; e~p~rience .a '~· p~al.. ,; Jkthi:
`
`' " ' TMNSAcriom ON '"'°·.;.."""~O•Y,'vm.cn-31, NO. 2. """"" 1985 : it
`
`~~:;z~r~~~~E[Z~~~~ ~1E:§~;;:~~§~;!f~* 1 .; . '.: _ .. :·:,··[·' ....•.... : .•.·.•.·.·.: .. ~:·.·····,•.······~ .• -
`~i ~~t~?1~~1~~~~;~~~~~12~~i N:~::~:~:'.~::l::!~:~:~~~~~·:~'.:~: 'i,~_.···:.:: .. ::·: ...•.•. :_t···.t~.··'···,,··.-l.~_!.·;'.: .. ·: ... •.!.:.,·:
`
`~ ::
`:~•'~:
`
`some specific choice of 81, 82,·: ·';s_M such that
`IV. NONAPPROACHABILITY OF RATES, OUTSIDE t:(j'
`7; ~ NTp,fl (1 ~ p1)
`We now wish to show that rates outside the region t:(J', as
`'
`. ).,./,
`defined in Theorem 1, cannot be approached for the
`and, indeed, it was only to llrrive atthls conclusion t4at ~e
`CCw /oFB in either the slot-synchronized or unsynchro-
`the · ficiitious-~'.·proh~~!Uly . ·distrlbution ·. QI1
`· : "'·' < .. :\'':.:'.',:.:
`:.···,:· .·· .·
`' .· · ·.: ... ,
`introduced
`nized case and for either error probability criterion. From
`(2), we see that it suffices to show that points outside t:(J' 81,82 ,· ··,SM:
`cannot be approached with arbitrarily small positive error We now rCcall that, . according · tb. the model of tJie
`. H J · :.1 ,.,
`·:.-_I;
`probability in the slot•synchronized case. Thus, for the rest CCw/oFB as given in Secticm'1I,'. ih.e)sp~ifictimein.t~rv*
`of this section, WC consider only the slot-synchronized case. over which ·~he·received SiSnalis mdicating either."' idle": .or
`"collision'~ aie,d<?t~~¥\~~!fi~!}i~fi~ltJi~,B~P~~f~f~als
`Consider now any choice of protocol signals and codes
`for the users. Without loss of essential generality, we may and the time off~ets.'T4~s,-·~~~;~f ppn~tionJto~~t;h~·QSS
`assume that the period_ T1 of the protocol signal s1(t) is a of user i can affect the r~~v~ si~aJ at most during ~e .Ti
`rational multiple of the slot length T, for 1 ~ i ~ M. Thus, . seconds of the interval (t0;·t,(;1f :.f\71);"hen the teceiveris
`we can write T1 = (m 1/m}T where m 1 arid T1 are integers. receiving ·no11collid~_. P,~C~~~.frq~: }i~~t i.Itfo.JlowsJrom
`Then NT, where N = m1m2 '. .. mM is an integer multiple
`(12) that, giyen idh~re ~S. ~·~spec~nc! c~c)ice of~1182 ; ... :;811
`of each T1• Thus, for all t, .
`such that the receiv~r r~iv~ :ilonC6llided .. pl;lckets from \
`(7) user i ata.~~r~te''·
`.~f afm~~~\P.1fl}~;(t_;~pj)P~~~e~/slot. .
`s (t +NT)= s (t)
`rsuppose further that .~~r~ l~ .. ~Jn~~~JY.:~eaje,'o/~P ·i~entlfi~ '.':
`I
`I
`•
`~n ad~ance, for_bo~ us~r f.~~·~~'. rFver;·~ch ip.te~al ;;
`for 1 ~ 1 ~ M.
`.
`F~r purposes only of our pro~f. we now impose a m which user i sends a. noilqolliCle4 . packe~~: Then' \lserWr;
`fictitious probability, distribution on the time offsets has with this extra help al:.noiseiess:Q-acy}DMC to tllb · ·;
`re~iver with a capacity'~r'orie p~c~et per use tmd witb'.;'S:t <
`81, 82, .. ., SM; namel~, we specify that f.hese are indepen-
`
`, r ,
`
`.
`
`.. ".'. · ··- ·
`
`· ~. ·
`
`· . -
`
`·
`
`dent and identica~ly distributed (IID) random v~ables I most .P,nJ .. ,(1 - p1) ·useS .. ll~(:~l~t. :Thus, . . l>Y"~e itsual· '.:
`tion of the duty fact,or p1, and from the fact that s,(t) is l positive error 'probability/i:regar.4less of 14e: :values ,;
`that are equally likely to take on any of the N val~':8 coding· theorem f~r; ~· DMP,,' u~rr·: r-.~~~·sep~ !inf!)rma- ;
`0, T,2T1 · · ,(N - 1)1'. It follows from (7), from thedefm~-, tion from his QSS .at a \ rate/~/wiµi .. ~bitraruy small ' '.
`l
`·. · .· ·.· · ·. ····.:.· ... •l'·'·' '.·.··.··;·:·; .. • ... ... . · • ···
`·· :.-<:°":·::: ·,·v · .:
`·, · ; . ·-,
`,: .. "/ ~
`, s2
`nonzero only over semi-open intervals of lengths which are 81
`,. . ·,SM, unless
`R, s p,CT (1 "7:pJ):packets/~lo~;
`integer multiples of T, that
`' . ·.·. ·
`"
`·' J.,_, , · > : 1
`E(s (t - 81)) = p 1
`-: _... __ .:,:·:·:.: .. \;.;:):~,j;ij:!. ~ .. : . .'/·.·:(:'~~·~{: . .'.:·.;:.-·.
`:~.,'·;
`that .··R .= (Ri,\~2;'.; :/.{~A(), 8lllnpt ~e ap~
`,
`I
`It follows
`for every time instant t.
`At any given· time Instant t on the receiver's clock, user i preached with a~bitrariJf~m~W.P9.siUv¢· ~rror pr0bability,
`independent of 8, uriles~ <t4>: ~~ ~~~~H~d for f'!=· 1, 7, · : · ·, M.
`will be the only user' in the act of transmission if and only
`if
`To complete the p~oof ~a,t, p91:11t:S··
`.outside.t~ cannot be, .
`( 9) achieved, We _need Ortly Sh()~J~a~ .<?!~fY. ~ ~ P that .sa,tjsf~C!I
`(14) for 1 S I S M)iC$ in the. {~gioti·~ defrned m 'fPeorem
`1
`1
`1, i.e., that if R satisfies 'c14);for 1 :':d ~- lv.( for some duiy
`..
`.,.
`Moreover, the left side of (9) will otherwise be zero. Thus, factor vect?r p. ·~~~ .~ }~~P.::,~;fi~fi~ .CH): .f<>r: :~('.~,i!, ;~·;Af ~
`, . r defining 1j as the total time within an arbitrary semi-open for . some ; :probabpi~y: ~v~~~ri !R~i+.,~:\fac~,;, ~br~qtt )~ .. ; ;~
`t.n' interval, [101 t0 +NT:), Q~ the receiver's clock of length NT already proved. this"last~*l~m~J: ~!bJs "dete~~#.9~·:.9if :'
`.,~·
`the '.'acµievable thr~ughpu~;f~~on1.\~fqr:anr:.\{-~ser,sl9i.~~ ; ~'~~:
`· during which the receiver is receiving noncollided packets
`ALO~· systemJ~l (~f.:lPtp~~~~~~~~§.9D<No~~.thelt$~~.jn,. ) ,ey~
`from user i, we have
`1i s f'°+NTSi{t - s,) n f 1 - s;(t - sJ] dt;
`(10) Appendix A~ WC ~vc an;el~ifi~. '· . ·~~.rooJ~<>~::t.Ji~~.f~~~.~~::·} q~
`"*
`. l~tnf.11.a :;~~~t,;;~o,, .. esta~Hfh
`-"'''"-. ~ ..,,(., 10
`'
`J
`1 .... 1
`.
`1
`I . · ',.J (,\I __.,, \ {ti IA
`'~~·.;;~.~1<.i'.~~:
`I)~(, .. .. 1~J •\. '. ~ .
`. :.,
`(' ·\ J,, '
`.. ; ~- .
`. . ·· .. ·, ·~·""'' ' ... ~.. ..
`·'
`.
`"•~A("«< . :-,
`
`1
`
`(8)
`
`\
`
`•
`
`•
`·.· 'r. _ _
`
`.
`
`Si (I _ 8,·): n [ l _ SJ ( t _ 8'}) J = l ;
`
`4
`
`,
`
`~J.J1//
`
`,
`
`.
`
`Pet., Exh. 1018, p. 5
`
`

`
`1 s. i !:: M.
`
`"
`
`..
`
`.
`
`• ,
`
`sho~r that ~~ch p~t~l/c.1~fi't'llie ·ouler.;b~uridary <>r ~ is
`determined .liy ·1(unlque1:~t.o:t>K~!Uty ·vecfor»:p:}· ·as· stated in
`'Theore~ ·! 1., (We;.;Wij~~t'J,~~;}9J.;;Ctc~dt~·<~c . an-one ·· \iector
`c11 ... ;.."1) Witit·~.M.100JilP.6~~iitsJ ·'." ~:-:··:,.,,.,; : ·.-'''
`.· .. ' ·
`.'iemma 1: F6r 'any ~j>_1·~·(p~', Pk.-:; .P~) with o s p'
`~ 1, there)s a ,· prqbabillty .,vector p .= (p 1;p2, .. ·,pJ.i)
`. . · . ;;"i .. ~ ·
`such that.
`p;n(1 ~ PJ) !i:.P,n (i...,. p1).
`' : ( :}¥</; '.
`.·
`}¥<1
`\ 1 l'.J\~;·:···~:-~. i·";~ :_i ·
`'
`. .
`.
`.,
`'
`.
`. v. AcmilvABtLt'lY oi:.RATESc>N TH~ OUTER
`.
`. · ..
`,.;:Bc)uf.irij.Ry OF <if
`. . · .
`in this· sectio~.'. ~~.·~1Aµve ·a oonstrudive proof of
`. Theorem . 2 .. : In .. the: f?llo\virig · sectioh, . we .· sh~l . use ·the
`. results of this sectiotl'i~:Ohfaiii a simple proof of the direct
`partof. ~eoreniJ<.;<i!(·/,'.'_ ;'.:'.;, '..:
`· •
`· A. Pre/imin~ri~1 · · i(: · 1
`. Throu~~ut · tltls .~~tl~n:'we Will: oon~der. o~lY. . the slot(cid:173)
`:
`.. . synchroniZed·case; ·A,s: V;e,lir~:now dealihg With cortstructive
`'':: scheme$; we cfui··ancJ'd6·iadoptt~e' restriction-that all users
`~:.·:align their: pacJ.c~htrati~tjij~sie>hs· tofEUl .~thin iinie slots on
`!!:~ _theirl~:clocks~;'i\h~i:.ii~ii~~at~o wHhin~e sfots on the
`[:· ·. ·receiver's clocic;·=sm<llW~~Jtffi~'~cif rs·ets;\are int~ger :multiples
`L of the s~ot · le~~!~'7i'.;;1!!tiF~~·.io~s ?t.~ener~ty, we ~ke
`t-,. 1: ... . 1 so ~ t?at ~ac,~;<l~~~f~~~f~( 1S.. a,~ Pl:~ew:. ·The_ penod
`f;i;:of ·each' prot0cotsequietlee:•1s··"t5w: also ··ari: mteger . that we'
`~J/::fu~;~~ut~~~~W;~~~~~~?t~;'.~r~.::;~.}~r •. ,~e .. least
`~X: · . we can rl<>~ ::¢lf Uiv~~~J1Y..~·aesbttl>¢':'ihe' prcii?co1 ·'signal
`t s,(i> :by ilie'. ;,;.~t~.c~N~i1Uen?'4·~1.;J::t.r;-;p~~·;.•'· ; ;·.ri;.;l in the
`iiri,'mantier thai:- sd'i i~.~ilie.i,~aiiier~»ts;(tJ .. iil' ili~ ;'n'tli .tiine slot
`.. : ... · ~. 'J.'.~.ntte~.~$~.~~.·.th~t::a .. transqliuoo p~c~t
`·(:~·:·:·.,, .... :~ .. ! ... <. ' · ·.·.~ . . . -.+ .... ·.'·.1· ... '. w
`~. ,tiikes ,vhlues~inJh~~se · . ,. ·2· ~,i.• (2:,..,.. ·1}, .. and we wnte A
`~~;:: ~fh~~:}ti~t~;aii;~\t~;~f ~~~f j~mt?.~~fa~~s~: ~h
`~;,~.~ tiirie slot. by:::tiie·; tlrn(~i'~ie ~tariaom .'variable: X, (n) in the
`:~ manner thai . . . :. ,·,·:.:<·;-:~1-i{~·' ,:·'.,1;"..'.
`' . :· .. 1
`XtC;1)"" A;
`·; ·ifs;~..,; O
`1.1
`~ ;: - . ; _; ::·. ,: ,'.-. '
`~-
`;~:
`. . . . X,(n) E : (0, ~•'r ': ', Q 71},
`'_~,·
`..• 1f Sin= 1.
`~.; simitarty; we·caD: ·<l~rlSt<{ili~re&iveci signat ill th~ nd1 time
`3.<slot by the ·discretej'iirtdorti ,variable Y( n) in . the manner
`··· ;: r.:;:-,\.·:~; ( ..... .. l
`,B,i~at . . · ·.·.
`.· · .
`~\( . . Y(n) =A, '·
`if,;XJn .. '.'":·;Bi) ~A forl !:: i !:: M
`:~·::. Y(n) = Xi{n, ~ ·Bj'. ::· 1
`if ij(n - B1).;.. A for all J rF- i
`• ·~ ~ "1 t oi't ... &t ~ \ •11 , ·" t
`: Y( n) == fl.,
`otherwise, · .
`.?/where fl. denotes ll·cOlli~iort de two or inore packe~s.· In this
`r. mannet; we . obtain a'· fully discrete representation for the
`: lO: stot-synchronized CCw/oFit ,Noteihat the channel mput
`'L. alphabet . of each user oontruns . Q + • 1 ·letters . and that the
`1'~ ~hannei· output- hlphltti~f·.C8µtfilris Q + 2 ·letters. Hence(cid:173)
`JJf qrth,, w~ '.shall, so~eiUrlesspeakof ''time instant n;' rather
`~;;~an .~he:·;~th,.iiiii~(:~}p,~~~:.1~:,ij~;:C\,i.\ : :,.;;/ . : . " ;. ;·, .. . • \
`·
`{';;3f.iY't?.·. as~u~e;tdr: ·~~~ffi~~ci,'1~at ~·~:()UtJ(.u,t Jl}phabet of
`.~~the QSS of ea9h user J~'. iilS<)Jiie set .(O, 1, .. •; Q . ..,. 1 }. We
`_}~~seek then to choose ii ,pfoto&>i sequence and block code for
`
`.
`
`.
`
`•
`
`.
`
`.
`
`.
`
`I
`
`:
`
`. •
`
`• ,'
`
`•
`
`,
`
`-
`
`;
`
`;
`
`, , _•
`
`, •I
`
`I
`
`· • .. ·· .• ·
`
`.
`
`S• • \
`
`•
`
`,
`
`,
`
`,
`
`197
`
`.
`
`·r
`
`'d
`each user such that, regardless of the values o( the time
`offsets, the receiver can reconsfruct each source output
`sequence without error. Moreover, we must show that the
`joint rates R that can be so achieved are dense on the outer
`boundary of the region 'IZ defined in Theorem 1.
`
`B. Protocol Matrices and an Exa;,,p/e
`
`We deffoe the protocol matrix S as the M X N binary
`matrix whose Ith row is the protocol sequence s, of user i.
`For instance, with M = 2 users, and protocol sequenee
`periods N1 - 2 and N2 - 4 with least common multiple
`N = 4, we could choose
`
`(15)
`
`s = D ~ ~ n
`
`We shall be interested in the received sequence over a span
`of N consecutive time instants; which, with no loss of
`essential generality, we can take to be time instants
`1, 2.'· · ·; N. We write
`y ... [Y1, Y2 .... YN]
`io denote this received N-tuple. We see from (15) tl~at, in
`case the time offsets are B1 = Bi = 0,
`Y.., [fl., PA, P8 , A],,
`i.e., that slot 1 is a collision slot, that slot 4 is idle, and that
`slots 2 . and 3 contain packets. From (15), we see further
`that packet PA was sent by user 2 whereas packet P8 was
`sent by user 1.
`Suppose next that 81 = 5. This delays the perlOdic pro(cid:173)
`torol sequence of user 1 by 5 slots, so that it Will appear to
`the receiver that user 1 is actually using the . protoc0l
`sequence [O, l, 0, 1] in slots 1 through4. Similarly, if B2 = 3,
`i~ will appear to the receiver that user 2 is actually using
`the protocol sequence [1, 0, 0, l]. Thus, it will appear to the
`receiver as if the modified protocol matrix
`
`S[8) = [ ~ ~ g n
`
`(16)
`
`is actually in use. In particular, we see that
`Y = [PA, P8 , A, fl.]
`where the packets PA and P 8 are from users 2 and 1,
`respectively.
`As we have observed from this example, a time offset (or
`"delay") of B1 slots corresponds to B1 right cyclic shifts of
`the protocol sequence s1• We write s1[81] to denote the
`sequence obtained from s1 after B, right cyclic shifts and,
`as we have already done in'(l6), we write S[8] for the
`.effective protocol matrix whose ith row is s1(B1]. Note that
`S = S[O]. Because s1n = s1.,,+N for all i and n, it follows
`s1[B1 +.NJ. Thus, given N, we can and do
`that s1[81] -
`hereafter restrict ourselves to the condition
`
`(17)
`without loss of essential generality. Because of (17), we see
`that there are only NM values of 8 = [B1,B2 ,. ··,BM] to be
`eonsidered, and hence at most this many distinct effective
`protocol matrices.
`For the protocol matrix S of (15), the reader can easily
`check that all 16 choices of 8 result in an S[8] s_uch that
`
`Pet., Exh. 1018, p. 6
`
`

`
`198
`
`· p~; ~~ sam,e:nµmb~r'. of .. ~
`
`IEEE TRANSAcnONS ON 'INFORMAl, , :· ~~~\··~