9.
`._.1_._n..a.
`
`-
`
`5‘
`
`..
`1.4.
`
`'
`
`._—.;
`
`19-I—l
`
`-._
`
`I
`
`‘J-t
`
`1-
`
`./£7
`
`Probeedings
`
`TI-IIRTY-SEVENTH ANNUAL ALLERTON CONFERENCE
`
`ON COMIVIUNICATION, CONTROL AND COMPUTING
`
`September 22 - 24, I999
`
`UNIV of MIC!-I.
`
`SEP 19 2000
`
`STACKS
`
`Allerton House, Monticello, Illinois
`Sponsored by the
`Coordinated Science Laboratory and the
`Department of Electrical and Computer Engineering of the
`University of Illinois at Urbana—Champaign
`
`Apple 1110
`
`Apple 1110
`
`

`
`PROCEEDINGS
`
`THIRTY-SE\’ENTH ANNUAL ALLERTON CONFERENCE
`ON COMMUNICATION. CONTROL. AND COMPUTING
`
`Bruce Hsjek
`ILS. Sreenhrns
`Conference Co-Chairs
`
`Conference Ileid
`September 22. September 23, and September 24.1999
`Alierton House
`Monticello. Illinois
`
`Sponsored by
`The Coordinated Science Laboratory
`The Department of Eleetritilldnnd Computer Engineering
`UNIVERSl1?{"tf}'F ILLINOIS
`U rhlna-Cfilinrn psign
`
`17 ”:‘£‘?. LBW
`
`In/3192-013-01 BBL
`
`

`
`FORWORD.............._.»..._._......,_.-......_......._...............................mmmmmmmm...............................I
`
`TABLE OF CONTENTS
`
`l—A: STOCIIASTIC NETWORKS I
`Organizcrs: SJ’. Meyn and R. Srilranl
`(University of Illinois at UtbaJ1arChampaig11)
`S.P. Mcyn
`{University oflllinois al Urbana-Chanlpaignj
`
`Chair:
`
`REPRESENTATION AND EXPANSION OF (MAX. PLUS) LYAPUNOV EXPONENTS
`F. Baocelli. S. Guubert, and D. Hang
`
`I
`
`MARTINGALE PROBLEMS AND LINEAR PROGRAMS FOR SINGULAR CONTROL I l
`T.G. Kurt: and ILH. Stockbridge
`
`STATIONARY REFLECTED LEVY PROCESSES IN STOCHASTICNETWORKS 21
`'1‘. Konsaantopoulos and G. Lul
`
`ON THE IMPACT OF VARIABILITY ON THE BUFFER DYNAMICS IN I? NFI'WORKS....
`Y. loo. V. Ribeim. A. Feldnmnn. A.C. Ciilben, and W. Willinger
`
`QUEUELNO NETWORKS WITH [NTERACTING SERVICE RESOURCES
`M. Armony and N. Bamhous
`
`I-B: CODING THEORY I: DECODING AND CHANNELS
`Organizers:
`‘R. Kocticr and RJE. Blahut
`(University oflllinois at Urbaria-Chnmpaign)
`Chair. A. Vardy
`(University cIf'CaJifcrnia. San Diego)
`
`A NEW UPPER BOUND ON THE RELIABILITY FUNCTION OF THE GAU SSIAN CHANNEL
`A. Asltikhmin, A. Bars, and S. Litsyn
`
`42
`
`52
`
`RECURSIVE DECODING OF REED-MULLER
`1. Dinner
`
`LOSSLESS COMPRESSION IN CONSTRAENED
`LL. Fan. B. Marcus. and R. Rolh
`
`
`
`70
`
`I-C: IIYBRIDIDISCRETE-EVENT-DYNAMIC SYSTEMS
`Chair: R.S. Sreenivas
`(University of Illinois at Urbana-Champaign)
`
`MODELLING OF TIMED DISCRETE EVENT SYSTEMS
`R.S. Minhasand W.M.WonI1an1
`
`lNI'ERACI‘ING DISCRETE EVENT svsmus
`s. Abdelwahed and WM. wunhm
`
`STABILITY ANALYSIS FOR INTERCONNECTED HYBRID
`S. Yamamotu and T. Ushio
`
`iv
`
`
`
`ss
`
`93
`
`

`
`DECENTRALIZED SUPERVTSORY CONT OF CONCURRENT DISCRETE EVENT SYSTEMS
`WIT!-l PARTIAL
`S. Jiang and R. Kumar
`
`................. I03
`
`A NEW PROBAEILISTIC APPROACH TO CONGESTION CONTROL IN COMMUNICATION NETWOR.KS.... II3
`H.Mo|1azaviar| and]. Mirkovic
`
`S. Ayycrrgun and R.I.. Cruz
`
`I-D: ACTIVE NETWORKS
`Orgaltlzerfchair. Y. Shavitt
`(Bell Labs, Lucenl Tcchnoiogics]
`
`CHUNIC5 IN PLAN: IANGUAGE SUPPORT FOR PROGRAMS AS
`LT. Moore. M. Hicks. and S. Nettles
`
`ON THE INTERFACE OF PROGRAMMABLE NETWORK ELEMENTS
`G. Hjélmljrsson
`
`BOWMAN AND CANES: INIPLEMFNTATION OF AN ACTIVE NETWORK
`S. Menlgu. S. Bhauachnljcc. Y. Chae. M. Sanders, K. Calvert. and E. Zegura
`
`I2?
`
`137
`
`141-'
`
`DESIGN OF A FLEXIBLE OPEN PLATFORM FOR HIGH PERFORMANCE ACTIVE NETWORKS .................. .. I5?
`S. Choi, D. Decaspcr, J. Dehan, R. Keller, J. Lockwood. J. Turner. and T. Wolf
`
`K. Calvert, J. Griffincn. B. Mullins, A. Schgal. and 5. Wm
`
`ACTIVE DISTRIBUTED MANAGEMENT FOR 11’
`R. Kawamura and R. Sladlcr
`
`l—F: SPACE/ITME METHODS FOR COMMUNICATION
`Chair: D. Sarwaxt
`(Univcrsity of Illinois at Urbana-Cluunpaigrl}
`
`NEW APPROACH FOR SPACE-TIME TR.ANSM.ITTER-‘RECEIVER DESIGN
`I-l.EIGm1'Ia] and AR. I-Ialnlnons, Jr.
`
`INTERFERENCE SUPPRESSION FOR CDMA VIA A SPACE-TIME POWER
`MIN]IU'I]ZA'I'ION BASED PREPROCESSOR WITH APPLICATIONS TO
`\.\r‘.L. Myriclt. MD. Zollowski, and LS. Goldslein
`
`176
`
`I86
`
`I96
`
`SOFDWEIGHTED TRANSMIT DIVERSITY FOR WCDMA ..................................................................................... .. 20-4
`A. I-Iottineli. R. Wichn-mn, and D. Rajan
`
`MULTIUSER DETECTION TECI-INIQUES FOR COMBINED ARRAY PROCESSING
`
`AND SPACE-TIME BLOCK CODING.................................................... ..
`3. Lu and X. Wang
`
`A TRANSMIT ADAPTIVE ANTENNA SCHEME WITH FEEDBACK FOR WIRELESS
`COMMUNICATIONS ........................................................................................................................................................- 216
`‘I’. L: Pézennec, F. Boixndcm. Y. Famine. and N. \\«'hirmen
`
`

`
`II-A: CODING THEORY II: ITERATIVE DECODING ANT} TURBO CODES
`Organizers.‘ R. Kocncr and £1.15. B!ahul
`(llniversity of Illinois at Urbana-Champaign)
`Chair: R. Knelter
`(University of Illinois at Urbana—Champaign)
`
`T. Richardson and R. Urbankc
`
`EFFICIENT ENCODING OF LOW—DENSITY PARITY-CHECK CODES.................................................................. ..231
`T. Richardson and R. Urbanke
`
`BJ. Frey and D.5'.C. MacKa5_v
`
`ON QUASI—C'YC'LIC REPEAT—ACCUMLTLATE CODES ............................................................................................. "249
`R.M. Tanner
`
`THE SERIAL CONCATENATION OF RATE~1 CODES THROUGH UNIFORM RANDOM INTERLEAVERS ....26{}
`HD. Pfistcr and P.H. Siege]
`
`l'I~B: STOCHASTIC NETWORKS 1]
`Organizers:
`S.P. Mcyn and R. Srikant
`(University of Illinois a1Urbana-Champaign}
`Chair: R. Srikam
`(University of Illinois at Urba.I'ln—Cha.mpaig'n)
`
`QUEUE LENGTH ASYNTPTOTICS FOR MARKOVIAN SERVICE NETWORKS .....................................................2'?{}
`A. Mandelbaum, WA. Massey, and MJ. Reiman
`
`EXACT ASYMPTOTICS FOR I-LIMITED EXPONENTIAL POLLING MODELS ......... ..
`W. Chang, D.G. Down. and RD. Foiey
`
`...28G
`
`INVARIANT RATE FUNCTIONS FOR DISCRETE TIME QUEUES ......................................................................... ..288
`EL]. Ganesh, N. O'Connell, and B. Prabhakar
`
`LARGE DEVIATIONS AND OPTIMALITY OF THE LARGEST WEIGHTED DELAY
`FIRST DISCIPLINE ................................................................................................... .. 29?
`amanan
`AL. Stolyar and
`
`ON ESTIMATING BUFFER OVERFLOW PROBABILITIES UNDER
`MARKOV-MODULATED INFUTS. . _ .
`.. ..
`
`LC11. Paschalidis and S. Vassiiaras
`
`INDUCED BURSTINESS IN GENERALIZED PROCESSOR SHARING QUEUES WITH LONG—TAl'LED
`TRAFFIC FLOWS ...........................................................................................................................
`S. Borst, O. Boxma, and P. Jclenkovié
`
`...316
`
`THE ASYMPTOTICS OF SELECTING THE SHORTEST OF TWO. IMPROVED .................................................... .. 326
`M. Mitzcnrnacher and B. Vficking
`
`vi
`
`

`
`II-C: LEARNING ALGORITHMS IN SIGNAL PROCESSING
`Organizers: A. Singer and M. Fedcr
`{University of‘I|Iir-ois at Urha.na—ChanIpaign and Tel Aviv University)
`Chair: M. Feder
`(Tel Aviv University)
`
`UNIVERSAL FILTERING AND PREDICTION OF INDIVIDUAL SEQUENCES CORRUPTED BY NOISE
`A. Baruch and N. Me.-rhav
`
`328
`
`FAST ILLS LAGUERRE ADAPTIVE FTLTERTNG ........................................................................................................ ,. 338
`R. Mcrchod and AH. Sayed
`
`MACHINE LEARNING APPLICATIONS IN GRID COMPUTING ............................................................................ .. 348
`G. Cybenko, G. Iiang, and D. Bila:
`
`REDUNDANCY OF THE LEMPEL-ZIV CODES .......................................................................................................... ,. 358
`SA. Savari
`
`THE INFORMATION B_O‘lTLENECK METHOD ................................. ..
`N. Tishby, F.C. Pereira-. and W. Bialek
`
`368
`
`THEORY MEETS PRACTICE: UNIVERSAL SOURCE CODING WITH THE BURROWS WHEELER
`TRANSFORM .................................................................................................................................................................... .. 378
`M. Effros
`
`II-D: OPTICAL NETWORKS I
`Organizers: M. Médard and E. Modiano
`{University oflllinois at Urha.na—Champaign
`and Massachusetts Institute ofTcchJ1o1ogy)
`E. Modiano
`(Massachusetts Institute of Technology)
`
`Chair:
`
`OPTICAL SPACE COMMUNICATIONS AND NETWORKING ................................................................................... 388
`V.W.S. Chan
`
`ON THE BENEFITS OF CONFIGURABILITY IN WDM NETWORKS ........ ..
`E. Modiano and A. Narula-Tam
`
`
`
`390
`
`NONBLOCKING WDM NETWORKS WITH FIXED—'I'UNED TRANSMITTERS AND TUNABLE
`RECEIVERS .................................................................................................................................... ..
`
`T. Lin and (3. Sasaki
`
`ON NEW ARCHITECTURES FOR WDM NETWORKS
`A. San. T. Shah. and BP. Sinha
`
`ALI.—O?TICAL LABEL SWAPPING WITH WAVELENGTH CONVERSION FOR WDM-IP NETWORKS
`WITH SUBCARRLER MULTIPLEXED ADDRESSING .............................. ..
`D.J. Blumenthal
`
`vii
`
`

`
`II-E: COMIIIUNICATION SYSTEMS AND SERVICES
`Chain
`3. Lin
`(University of Hawaii)
`
`ON DISCRETE SUFFICIENT STATISTICS FOR ACQUISITION IN ASYNCHRONOUS
`BAND-LIMITED CDMA SYSTEMS . . .. . . . . .
`. . .. . .. . . .. . . . . . . . . . . . . . . . . . . . . .. . . ,. . . . . . . .. . . .. . . .. . . . . . . . .. . . ,. . . ,. . . . ..-424
`A. Mantrnvadi and V.\’. Vucravalli
`
`FREQUENCY SYNCHRONIZATION ALGORITHM FUR FREQUENCY HOPFING
`SYSTEM BASED ON STNGULAH VALUE DECOMPOSITION ................................................................................. "434
`A. Poutlu
`
`A SOFTWAREORJENTED STREAM CIPHER FOR CEI.-LULAR AND PERSONAL COMMUNICATIONS
`
`M.ZI1ang. A. Chan, and C. Carrol!
`
`BINARY RANK CRITERIA FOR PSK MODULATED 5?ACE-TIME
`H. El Gama] and AR. Hanunons. Jr.
`
`TURBO CODES WITH ORTHOGONAL MODUIATION EN D5-CDMA MOBILE
`RADIO SYSTEM WITH SHORT FRAME
`G. Li and ‘1'.L. Guam
`
`AN INTERACTIVE CONCATENATEIJ TURBO CODING SYSTEM
`Y. Liu. H. Tang, 5. Lin. and M.I’.C. Fossorier
`
`BI-DIRECTIONAL SOVA DECODING FOR TURBO-CODES
`J. Chen, M.P.C. Fassorier. 5. Lin. and C. Xu
`
`451
`
`IIGI
`
`....47[
`
`II-F: FADING CHANNELS AND POWER CONTROL
`Chair“.
`1). Sarwam
`(Univ:-rsity of Illinois a1 UrI:ana(.‘I|ampaign)
`
`ANALYSIS OF AN UPFDOWN POWER CONTROL ALGORITHM l'N CDMA REVERSE LINK
`
`L. Song. N. Mnndayam. and Z. Ggiic
`
`A CLASS OF DISTRIBUTED ASYNCHIRONOUS POWER CONTROL ALGORITHMS I-‘OR CELLULAR
`
`J.D. Herdlzner and E.K.P. Chung
`
`DISTRIBUTED CONNECTION ADMISSION CONTROL I-"OR POWER-CONTROLLED
`
`M. Xian. NB. Slu'ofl', and E.K.P. Chung
`
`INTERFERENCE AVOIDANCE AND DISPERSIVE CHANNELS: A NEW UOOK AT MULTICARRIER
`
`D.C. Popescu and C. Rose
`
`PERFORMANCE OF OPTIMAL CODES ON GAUSSIAN AND RAYLEIGH FADFNG CHANNELS: A
`
`S. Viallearldl. Boutms
`
`IMPROVED MARKOV MODELS FOR FADING CHANNELS: ANALYSIS AND DESIGN .................................. .. 525
`D.L. Goeckel. M_.I. Chu. and WE. Smrk
`
`vffl
`
`

`
`[II-A: CODING THEORY Ill: ADGEBRAJC AND COMBINATORIAL CODING THEORY
`Organizers: R. Koetter and RE. Blahut
`(University of Illinois at Urbaria-Champaign}
`Chair: N. Boston
`(University of Illinois at U1‘hana—Champaign)
`
`ON THE CLASSIFICATION OF EXTREMAL ADDITIVE CODES OVER GFI4) .................................................... .. 535
`P‘. Gabon-it, W.C_ Huffinan, .i,—L. Kim. and V. Pless
`
`TWO FAST ALGORITHMS IN THE SUDAN DECODING PROCEDURE
`G_—L_ Feng
`
`.... .. 545
`
`FROM VJEIGHT ENUMERATORS TO ZETA FUNCTIONS ......................................................................................... 555
`I. Duursma
`
`ALTERNATIVE APPROACHES TO THE COMPUTATION OF ERROR VALUES FOR HERMITLAN
`CODES ................................................................................................................................................................................ ..55'?
`ME. O'SulIivaJ1
`
`I.lI—B: STOCHASTIC NETWORKS III
`Organizers: S.P. Meyn and R. Srikant
`(University of Illinois at U1'bana—ChaJ'npaign]
`5.1-‘. Mcyn
`(University of Illinois at Urbana-Champaign)
`
`Chain
`
`BUFFER OVERFLOW ASYMPTOTICS IN HOL SERVICE SYSTEMS WITH l-IETEROGENEOUS
`
`C. Kotopoulos, N. Likhanuv and KR. M-azumdar
`
`SCHEDULING AND CONTROL OF MANUFACTURING SYSTEMS — A FLUID APPROACH ........................... 57'!‘
`G. Weiss
`
`MULTICLASS NETWORKS IN HEAVY TRAFFIC: ASYMPTOTIC OPTIIMALITY OF TRACKING
`
`
`C. Maglaras
`
`SCHEDULING OPEN QUEUECNG NETWORKS WITH SUFFICIENTLY FLEXIBLE RESOURCES ................... .. 597
`S. K.uma.r
`
`OPTIMALLY STABILIZING CONTROLS FOR A DETERMINISTTC NETWORKMODEL
`P. Dupuis and R. Ara:
`
`III-C: ROBUST CONTROL AND DECISION MAKENG
`Chair: C. Beck
`(University aflllinois at Urbana—Champaign)
`
`EVALUATING CUMULANT CONTROLLERS ON A BENCHMARK STRUCTURE PROTECTION
`PROBLEM [N THE PRESENCE OF CLASSIC EARTHQUAKES.....
`KD. PI‘Ii?.l1'l, MK. Sain. SR. Liberty, and B.F. Spencer. Jr.
`
`61?
`
`RISK-SENSI'I‘IVE DECISION-TI-IEORETIC TROUBLESHOOTING .........................................................................._ 62?
`MA. Shayman and E. Feméndez-Gaucherand
`
`ix
`
`

`
`H- CONTROL FOR MIXED DISTURBANCE REIECTION ........................................................................................ .. 63'?
`LC, Luo and EB. Lee
`
`SOLVTNG POLYNOMIAL SYSTEMS IN ROBUST STABILITY
`N.—P_ Kc
`
`641
`
`ROBUST, NEAR TTM'E~0PT1MAL CONTROL OF THIRD-ORDER UNCERTAIN SYSTEMS .............................. .. 651
`K,H, You arid E_B_ Lee
`
`A NEW CONVEX RELAXATION FOR ROBUST H, PERFORMANCE ANALYSIS OF
`
`L. E1 Ghanui and E. Form
`
`A NEW RESULT ON THE BELLMAN EQUATION FOR EXIT TIME CONTROL PROBLEMS
`WITI-I CRITICAL GROWTH
`M. Malisoff
`
`1]]-D: OPTICAL NETWORKS II
`Organizers: M. Médard and E. Modiano
`(University of Iliinois as: U1'ba‘rIa—Ch.fl.mpaign and
`Massachusetts Institute ofTbcI1noIogy]
`Chair: M. Médard
`(University of Iliinois at U1'ba.rIa—Champajgn)
`
`FAULT PROTECTION IN WDM MES}-I NETWORKS ................................................................................................. .. 659
`G. Eliinas
`
`A COMPARISON OF ALLOCATION POLICIES IN WAVELENGTH ROUTING NETWORKS ............................ .. 669
`Y. Zhu. G.N. Rnuskas, and H.G. Perms
`
`OPTICAL BUFFERS FOR MULTI-TERABIT IP ROUTERS
`D.I<L, Hunter. I. Andonovic, and M.C. Chia
`
`...... 6'39
`
`THE ?L—SCI-EEDULER: A M'[J'I..TIWAVELENGTH SCHEDULING SWITCH ............................................................. .. 589
`1.1‘. Lang, E.A. Varvarigus, and DJ. Elumenthal
`
`ON DIFFERENT ROUTING STRATEGIES IN TRANSPARENT ALL—OPTICA1. NETWORKS ............................ .. 699
`OK. Tonguz
`
`I.l1~E: COIIrl'M'l.TI'k'ICATION NETWORKS
`Chair: R. Cn.I.z
`[University of California. San Diego)
`
`TRANSMISSION POLICIES FOR TIME VARYING CHANNELS WITH AVERAGE DELAY
`CONSTRAINTS ................................................................................................................................................................. .. T09
`B.E. Collins and KL. Cmz
`
`FAIR ALLOCATION OF U"1'II_.ITIES IN MULTIR-ATE MULTICAST NETWORKS
`5. Sarkar and L. Tassiuias
`
`........ .. 1'13
`
`ON THE USE OF 1\«‘IU1.TIPI..E WORKING POINTS IN MULTICI-IANNEL ALOHA WITH DEADLINES ............ .. 728
`D. Ba:-on and Y. Birk
`
`

`
`SPECIFICATION AND ANALYSIS OF A RELIABLE BROADCASTING PROTOCOL
`........................................... .1. ...................................................................................738
` INMAUDE.....
`G. Denker.
`.
`.
`una- caves, J. Meseguer. P.C. Olveczky. J. Rnju, B. Smith. and C1,. Talcott
`
`MODELING AND ANALYSIS OF ACTIVE MESSAGES TN VOLATILE NETWORKS ......................................... .. 148
`C. Okino and O. Cybenko
`
`IMPLEMENTATION OF AN ACTIVE CONGESTION CONTROL SCHEME [N NARROW”BAN'D ATM
`NETWORKS ...........................................................................................................................
`S. Sheik, 1‘. Evans, A. Kulkarni. and G. 1\-‘linden
`
`CPU SCHEDULING FOR ACTIVE PROCESSING USING FEEDBACK DEFICIT ROUND
`T. WOW and D. Decasper
`
`758
`
`768
`
`I11-F: WIRELESS COMMUNICATION I: DETECTION AND ES'l’l'MATION
`Organizers: VJV. Veeravalii and U. Madhow
`(C‘omel1Univcrsity and University uflllincis at Urbana-Champaign)
`Chair. V,'V. Vccravalli
`(Cornell Ilnivemity)
`
`PRECODING FOR SCATTERING FUNCTION ESTIMATION OF MOBILE CHANNELS USING OUTPUT
`CORRELATIONS ONLY .................................... ..
`
`C. Tepadelenlioglu and GB, Giannakis
`
` TWO—STAGE HYBRID ACQUISITION OF MUI..TICARRJ.ER DLRECPSEQUENCE
`
`SPREAD-SPECTRUM SIGNALS ........................................................................... ..
`R]. Block and CW. Baum
`
`TRAINING SEOUENCBBASED I\a'l'ULTl'U5ER CHANNEL ESTIMATION FOR
`BLOCK-SYNCHRONOUS CDMA .................................................................................................................................. .. ‘I90
`G. Cairn and U. Milra
`
`SUPPRESSION OF I-HGH-DENSITY, DYNAMIC NARROWBAND INTERFERENCE IN DSICDMA
`SPREAD—S‘x“'ECTRUM SYSTEM ...................................................................................................................................... .. 800
`C. Carl.-:n1a|m, H.V. Poor, and A. Logothetis
`
`LARGE SYSTEM PERFORMANCE OF REDUCED-RANK LINEAR FILTERS ............................................. ..
`ML. Honig and W. Xian
`
`810
`
`NONLINEAR MULTIUSER RECEIVERS WITH DISTRIBUTED POWER CONTROL IN CELLULAR
`RADIO NETWORKS ......................................................................................................................................................... .. 320
`MK. Varanasi
`
`xi‘
`
`

`
`IV-A: WIRELESS COMMUNICATIONS II: SYSTEM CONSIDERATIONS IN PHYSICAL LAYER DESIGN
`Organize.-.rs:
`\f.\«". Vccravalli and U. Madhow
`(Cornell Uniwrrsity and University oflllincis at Urba.n.a-Champajgu)
`Chair: U. Nladhow
`(University oflllinois at Urbalta-Chalnpaign}
`
`THE CODING—SPR.EADI'NG TRADEOFF IN CDMA
`V.V. Vaeravnlli
`
`SPECTRAL EFFICIENCY OF RANDOMLY SPREAD DS-CDMA IN A MULTI-CELL
`BM. Zaidel, S. Shamai. and S. Verdi‘:
`
`CDMA DESIGN THROUGH ASYMPTOTIC ANALYSIS: FADING CHANNELS
`E. Bigiicri, G. Cain. G. Tm-icon. and E. Viterbn
`
`831
`
`Bill
`
`851
`
`PACKING SPHERES IN THE GRASSMANN MANIFOLD: A GEOMETRIC APPROACH TO
`
`THE NON-COHERENT MULT1-ANTENNA
`L Zheng and D.N.C. Tse
`
`.....B6l
`
`BLIND ADAPTIVE MULTIUSER DETECTION FOR DSISSMA COMMUNICATIONS WITH
`GENERALIZED RANDOM SI-‘READING IN A FREQUENCY-SELECTIVE FADTNG CHANNEL ..................
`J.H. Cho and 1.5. Lchncrl
`
`TRAFFIC AIDED MULTIUSER DETECTION FOR PACKET SWITCHING RANDOM ACCESSICDMA
`NETWORKS ................................................................................................................................................................. ..
`B. Chen and L. Tong
`
`IV-B: CODING THEORY W
`Chair: R.F.. Biahut
`(University of Illinois at Urbanu-Champaign)
`
`A. Khandekar and R. McEIiece
`
`AWGN CODING TI-IEOREM5 FOR SERIAL TURBO
`HJEI1 and RJ. McEIiwc
`
`LINEAR CODES OVER Z.»’[2"} OF CONSTANT EUCLIDEAN
`LA. Wood
`
`.
`
`.
`
`..
`
`..
`
`Y. Liu and MP. Fizz
`
`TURBO DECODING OF CONCATENATED SPACE—TI.ME CODES ................................................................... ..
`KJL munayanan
`
`SOFT OUTPUT‘ AND ITERATIVE STACK DECODTNG........
`R. Sivasankarnn and S.W. McLaughlin
`
`ALGEBRAIC.‘ GEOMETRIC CODES AND AN IMPROVEIWENTS ON THE
`
`H. Maharaj
`
`3"H
`
`381
`
`89!
`
`B93
`
`895
`
`89?
`
`899
`
`__....90l
`
`.903
`
`xii
`
`

`
`IV-C: STOCHASTIC SYSTEMS AND CONTROL
`Chair: 6. Du!lerud
`(University of fllinuis at Urbarna-Chmnpaign]
`
`SINGLE-SAMPLE-PATH-BASED OPTIMIZATION OF MARKOV DECISION
`Z. Ren and RH. Krugh
`
`905
`
`TRACKING CAPABILITY ANALYSIS OF THE LMS ALGORITHM FOR FIR SYSTEMS WITH AR
`
`Y. Wei. SB. Gelfand. and LV. Krogmeicr
`
`ADAPTIVE OPTIMAI. PREDICTION FOR MIMO STOCI-IASTIC SYSTEMS USING CANONICAL FORMS
`B. Shahrrava and J.D. Aplevich
`
`925
`
`SURE ESTIMATOR PERFORMANCE IN A HARMONIC DISTORTION PROBLEM............................................. ..935
`E.E. Yllz. Y. Gun. and KJ. Olcjnicznk
`
`STOCHASTIC DIFFERENCE EQUATIONS WITH TIME DELAYS .......................................................................... .. 93'?
`A.S.C. Sinha, S.E. Lyshevski. B.R. Pidapani, and F. Kocaoglan
`
`CONTROL UNDER COMMUNICATION
`S. Tasikonda and S. Miner
`
`IVA}: SPACE-TIME PROCESSING!
`Orga11imen'Chair: A. Nehomi
`(University oflllinais at Chicago}
`
`SPACE-TIME FADING CHANNEL ESTIMATION [N UNKNOWN SPATIALLY CORRELATED NOISE............ 943
`A. Dosandiié and A. ‘Nchonli
`
`BLAST TRAINING: ESTIMATING CHANNEL CHARACTERISTICS FOR
`HIGH CAPACITY SPACEJFIME
`T.L. Mam-.tLn
`
`ANALYSIS OF THE PARALLEL INTERFERENCE CANCELER FOR DSICDMA SIGNALS 967
`R. Clnndruekaran and JJ. Shynk
`
`BEARING ESTIMATION IN A IUCEANCHANNEL
`G. Fuks. J. Goldacrg, and H. Mess:-r
`
`OPTIMAL DOWNLIINK BEAMFORMING USING SEMIDEFINITE
`M. Bcngissan and B. Oflerslen
`
`987
`
`AN OVERVIEW OF A SIMULATION ENVIRONMENT TO STUDY THE IMPACT
`OF NON-IDEAI. HARDWARE ON ARRAY997
`J. Yin. C.M.S. Sec. BJ‘. Ng, Y.K. Sin. and Y.L. Lu
`
`SIGNAL REPRESENTATIONS FOR TRANSMIT-RECEIVE ANTENNA ARRAYS
`J. Zhang. K. Ta.ntinarawnI., and AM. Sayced
`
`1006
`
`BLOCK SPACE-TIME ANTENNA PREOODINGJDEOODING FOR GENERALIZED MULTICARRIER
`COMMUNICATIONS IN UNKNOWN MULTIPATI-I ..... ..
`Z. Liu. A. Scagiionc. S. Barbarossa. and GB. Gianmlns
`
`xii!
`
`

`
`LEAST-SQUARES 1\«IU'LTI—USER FREQUENCY-DOMAIN CHANNEL ESTIMATION
`FOR BROADBAND WIRELESS COMMUNICATION SYSTEMS ........................................................................... .. 1026
`TA. Thomas, F.W. Vook, and K.L. Baum
`
`IV-E: MANUFACTURING SYSTEMS-
`Organizerfchain
`S. Revelimis
`(Georgia Institute of Technology)
`
`A MARKOV DECISION PROCESS MODELING FOR CONTROL SWITCHING OF DISCRETE EVENT
`1036
`SYSTEMS ........................ ..
`H. Darabi and MA.
`at an
`
`SUPERVISORY CONTROL OF CONFRADICTIONS IN HIERARCI-HCAL TASK CONTROLLERS .... ..
`X. Gum and LE. Holloway
`
`1042
`
`IV-F: STOCHASTIC NETWORKS IV
`Organizers: SJ’. May-n and R. Srikant
`(University oflliinois at Urbana—Champaign)
`Chair: R. Srikant
`(University of Illinois at Urh:ma—Champaign)
`
`MULTIUSER RECEIVERS. RANDOM MATRICES AND FREE
`D.N.C. Tse
`
`I055
`
`STABILITY PROPERTIES OF INCREMENTAL REDUNDANCY [N CDMA PACKET DATA NETWORKS..... 1065
`R. Vijayakumar and ELM. Wasserman
`
`PRICING PRIORITY CLASSES IN A DIFFERENTIATED SERVICES
`P. Marbach
`
`1075
`
`COMPARING TANDEM QUEUETNG SYSTEMS AND THEIR FLUTD LIMITS .................................................... .. 1085
`E. Altman, G. Koala, and T. Jim-énez
`
`WAI'I'[NG TIME ASYMFTOTICS FOR TIME VARYTNG MIJLTISERVER QUEUES
`WITH ABANDONMENT AND RETRIALS ................................................................................................................. .. 1095
`A. Mandelbaum. W.A. Massey, M.I. Reiman, and 91.1.. Sioiyar
`
`LARGE DEVIATIONS FOR SMALL BUFFERS: AN INSENSITIVII Y RESULT
`M. Mandjes and J.H. Kim
`
`1103
`
`OVERFLOW AND LOSSES IN A NETWORK OUEUE WITH SELF-SIMILAR INPUT........................................ .. 1113
`B. Tsybakov and ND. Georganas
`
`V-A: STOCHASTIC NETWORKS V
`Organizers: S.P. Meyn and R. S:-ik-ant
`(University of Illinois a1Ur11ar1a-Chainpaign]
`Chair: S.P. Meyn
`(University uflllinnis at Urba.na—Cha.mpaign)
`
`CHOKE A STATELESS MECHANISM FOR PROVIDING QUALITY OF SERVICE
`IN THE INTERNET ........................................................................................................................................................... 1122
`R. Pan and B. Prabhakar
`
`xiv
`
`

`
`OPTIMAL ROUTING TO M PARALLEL QUEUES WITH NO BUFFERS .............................................................. .. 1132
`E. Airman. S. Bhuiai. B. Ganja]. and A. Rordijk
`
`THE EFFECT OF SCALE ON INTERNET QUALITY ................................................................................................ .. 1 [42
`M. Siler and J. Walrand
`
`STABILITY OF MULTILANE INPUT—BUFFERED SWITCHES WITH MARKO‘v'—M(JDULATED
`ARRIVAL PROCESSES .................................................................................................................................................. ..ll52
`P. Ho, D. Tse. and I. Walrand
`
`V-B: WIRELESS COMMUNICATIONS Ill: NETWORKING ISSUES
`Organizers: V.V'. Veeravalli and U. Madhuw
`(Cornell University and University of Illinois at Urbanaaifhampa-ign)
`Chain V.V. Vecravalli
`(University of Illinois at Urbana—Champaign)
`
`AD.-\P'lTVE TRANSMISSION FOR SPREADSPECTRUM COMMIJNICATIONS OVER MULTIIPATH
`CHANNELS ............................
`........................................................................................................................................ .. 1162
`MB. Purslcy and OS. Wilkins
`
`ADAPTIVE REDUNDANCY RETRANSMISSION PROTOCOLS FOR WIRELESS NETWORKS ...................... .. ll'3"l
`T. Ji and W.E. Stark
`
`RESOURCE POOL-ING AND EFFECTIVE BANDWIDTHS FDR CDMA ANTENNA ARRAYS
`S.\-". Hanly and D.N.C. T53
`
`[I81
`
`ROUUNG FOR MAXIMUM SYSTEM LIFETIME EN WIRELESS AD-HOC NETWORKS .................................. .. I19]
`I.—I-I. Chang and L. Tassiulas
`
`A SELF ORGANIZING WIRELESS SENSOR NETWORK ........................................................................................ .. 1201
`K. Sohrabi, J. Gao, V. Ailawadhi. and G. Pottie
`
`V-C: MULTIUSER DETECTION
`Chain M.K. Vamnasi
`(University of Colorado at Bouiderl
`
`BLIND ADAPTIVE NONCOI-[ERENI MULTIUSER DETECTION FOR NONLINEAR MODULATION 121]
`D. Das and MK. Va.ra.nasi
`
`LOW COMPLEXITY NON—CO§-IERENT N"EAR~OPTIMAL 1\d'UL‘ITUSER DETECTION
`FOR OVERSATURATED MA COMMUNICATION..................................................................................................... 1221
`R.E. Learned. A.S. Willsky. and BM. Buroson
`
`ADAPTIVE MULTIUSER DECISION FEEDBACK FOR ASYNCHRONOUS
`I236
`"CELLULAR DS'~C'DMA ................................................................................. ..
`R. Ratasnk, G. Woodward. and M1,. I-lnnig
`
`MULTIUSER EQUALIZATION FOR. RANDOM SPREADINGJ LIMITS OF DECURRELATION
`
`WITH AND WFTHOUT DECISION-FEEDBACK ......
`RR. Mfiller
`
`1246
`
`

`
`V-D: SPACE-TIME PROCESSING fl
`Organizcrfchair: A.Nehorai
`{University of Iilinois at Chicago)
`
`SCI-IEDUI,l'NC3 OF SWITCHED MULTIEIEAM ANTENNAS TN A Ml_JL'I‘fl'-‘LE ACCESS ENVIRONMENT ...... .. 1256
`A. Lngothetis and H.\«". Pour
`
`MULTIPLE ANTENNA DIFFERENTIAL MODULATION.....
`BM. Hochwald and W. Sweldens
`
`1266
`
`SPACE-TIME ZERO FORCTNG EQUALIZATION FOR 3G CDMA FORWARD LINK TO RESTORE
`ORTHOGONALITY OF CHANNEL CODES ............................................................................................................... .. [274
`Ml}. Zoltowski and T.P. Krauss
`
`A NOVEL SPA(.‘E—T]ME SPREADING SCHEME FOR WIRELESS CDMA SYSTEMS ................................. .. 1234
`B.M. Hochwaid. T.L. Marzetta. and CB. Papadias
`
`V-E: CODING FOR MAGNETIC CHANNELS
`0rganizeI'.v'Chairs:
`E. Kurtas
`(Ouamrurn Corporation}
`
`ED EQUALIZATION FOR PAGE-ORIENTED DATA STORAGE SYSTEMS ......................................................... .. 129-4
`E-.V.K.V. Kumar, V. Vadde, and M. Keskinoz
`
`TOWARDS SOFT OUTPUT APP DECODING FOR NONSYSTEMATIC NONLINEAR BLOCK CODES ......... .. 1304
`KB. Anim-Appiah and S.W. McLaughlin
`
`LOW DENSITY PARITY CHECK CODES FOR M.-*\GN'ETIC RECORDING .......................................................... .. I314
`J.L. Fan, A. Friedmann. E. Kurtas, and S. McLaughlin
`
`DESIGN CONSIDERATIONS FOR CONCATENATTNG CONVOLUTTONAL CODES
`WITH PARTIAL RESPONSE CHANNELS .................................................................................................................. .. 1324
`WE. Ryan
`
`TURBO CODES FOR TWO—TRACK MAGNETIC RECORDING SYSTEMS ......................................................... .. I334
`E. Kurtas and T.M_ Duman
`
`LIST OF AUTHORS ...................................................................................................................................................... .. 1344
`
`xvi
`
`

`
`Irregular Turbo codes
`
`Brendan J. Frey
`Computer Science, University of Waterloo
`Electrical and Computer Engineering. University of Illinois at Urbana
`http://www.cs.uwa.terloo.ca./wfrey
`
`David J. C. MacKay
`Department of Physics, Cavendish Laboratories
`Cambridge University
`http: //wol.ra. phyxcam. ac.11k/mackay
`
`Abstract
`
`Recently-, several groups have increased the coding gain of iteratively decoded
`Gallager codes {low density parity check codes] by varying the number of parity
`check equations in which each codeword bit participates.
`in regular turbocodes.
`each “systematic hit” participates in exactly 2 trellis sections. We construct ir-
`regular turbocodes with systematic bits that participate in varying numbers of
`trellis sections. These codes can be decoded by the iterative application of the
`sum-product algorithm In low-complexity, more general form of the turbodecoding
`algorithnt}. By uiaking the original rate 1,-"2 turbocode of Barron at nl. slightly
`irregular, we obtain a coding gain of 0.25 dB at a block length of N = 131,072,
`bringing the irregular turbocode within 0.3 dB of capacity. Just like regular tur-
`bocodes. irregular turbocodes are lineru-—time encodahle.
`
`1
`
`Introduction
`
`Recent work on irregular Gallager codes (low density parity check codes) has shown that
`by making the codeword bits participate in varying numbers of parity check equations.
`significant coding gains can be achieved [I-3]. Although Gallager codes have been shown
`to perform better than turbocodes at BEES below 104 [-1]‘. until recently Gallager codes
`performed over 0.5 dB worse than turboc-odes for BERs greater than 10'”. However.
`in [3], Richardson at al. found irregular Gallager codes that perform 0.16 dB better than
`the original turbocode at BEES greater than 104 [5] for a block length of N a 131,072.
`
`'Gal]ager codes to not exhibit decoding errors. only decoding failures, at long block lengths with
`N > 5.000.
`
`241
`
`

`
`In this paper. we show that by tweaking a turbocode so that it is irregular, we obtain a
`coding gain of 0.15 dB for a block length of N = 131. 072. For example. an N = 131.07?
`irregular turhocode achieves Eg,;’Ng ='0.=l8 dB at BER = 10“, a performance similar to
`the best irregular Gallager code publisliecl to date
`By further optimizing the degree
`profile. the perimeter and the trellis polynomials, we expect to find even better irregular
`turb0codes_ Like their regular cousins. irregular turhococies exhibit a BER flattening
`due to low-weight codewords.
`
`2
`
`Irregular turbococles
`
`In Fig. 1. we show how to View s tnrbocode so that it can he made irregular. The first
`picture shows the set of systematic bits {middle row of discs] being fed directly into
`one convolutional code [the chain at the top] and being permuted before being fed into
`another convoiutionai code (the chain at the bottom). For :1 rate I/2 turbocode, each
`constituent convolutional code should be rate 2f 3 (which may, for example, be obtained
`by puncturing a lower-rate convolntional code}.
`
`Since the order of the systeniatic bits is irrelevant, we may also introduce a perrnuter
`before the upper convolutional code. as shown in the second picture. In the third picture,
`we have simply drawn the two pcrmuters and convolntional codes side by side.
`
`For long tnrbocodcs. the values of the initial state and the final state of the convo-
`lutional chains do not significantly influence performance {e.g., see [6]). So, as shown in
`the fourth picture. we can View a turbocode as a code that copies the systematic bits.
`permntes both sets of these bits. and then feeds them into a. convolntional code. We refer
`to this mrbocode as ‘‘regular'‘. since each systernatic hit is copied exactly once.
`
`The final picture illustrates one way the above turbocode can be made irregular.
`Some of the systematic bits are “tied” together, in effect causing some systematic bits to
`be replicated more than once. Notice that too keep the rate of the overall code fixed at
`1/ 2. some extra parity bits must. he punctured.
`
`More generally. an irregular tnrbocodc has the form shown in Fig. 2, which is a type of
`“trellis-constrained code” as described in [T]. We specify‘ a degree profile. fig 6 [0, 1}.d E
`{1.2.... .D}.
`fig is the fraction of codeword bits that have degree d and D is the
`maximum degree. Each codeword bit. with degree d is repeated :1‘ times before being fed
`into the permuter. Several ciasscs of permuter lead to linear-time encodeble codes. In
`particular. if the bits in the convolutionnl code are partitioned into “systematic bits“
`and "parity bits". then by connecting each parity bit to a degree 1 codeword bit. we can
`encode in linear time.
`
`The average codeword hit degree is
`
`0
`
`J = Z d- J}
`as:
`
`(1)
`
`The overnll rate R of an irregular turbocode is related to the rate R‘ of the convolutional
`code and the average degree d by
`
`ci(1—R')=1—R.
`
`(2)
`
`So, if the average degree is increased. the rate of the convolutional code must also be
`increased to keep the overall rate constant. This can be done by puncturing the convo-
`lutional code or by designing a new. higher rate convolutional code.
`
`242
`
`

`
`Figure 1: The first 4 pictures Show that a turbocode can be viewed as a code that
`copies the systematic bits, permutes bath sets of these bits and then feeds them into
`a convoiutional code. The 5th picture shows how a. tnrbocode can be made irregular
`by "tying" some of the systematic bits together.
`i.e.. by having some systematic bits
`replicated more than once. Too keep the rate fixed, some extra parity bits must be
`punctured. Too keep the block length fixed, we must start with a. longer turbocode.
`
`3 Decoding irregular turbocodes
`
`Fig. 2 can be interpr