Minimizing the Worst-Case Distortion in Channel Splitting By H. S, WHTSENHAUSEN (iterusril received Februnry 27. 186% A sequence of outputs from a stationary memoryless source is cenvosted into n code streams sent over n parallel chanaels. Any kor ower of these channels may have broken down, unbeknown 0 the earder. The receiver maps the streams from the wureiving channels into reconstruction sequence for minimum distortion. This distor. ton wild take different values depending on what subset of channels ix operative, Let Dare be the Larges! of these value, the worst case llgcortion. This paper shows Unt the infimum of Da. over all fneodinge is the same as ifthe encoder did have knowledge of the ‘reakdown situation. 1. wTRooUCTION Consider a stationary, memoryless swurce emitting at esch unit of time a random vuriable-X, with valves in measurable space 2. An tncoder enaps this souroestroam inks a code stream for trantmission ver n channels going won comman decoder, “The channel have psiive capacces =Cn a the inoqualities following by the choice ofthe intexing. Up to & of the channels ay in face ve broken down, so that situations are possible IK situations is realized ative channels form aaequency of reconstructions Xin a measurable pce (often, but nat necessarily, the aame a: 2), Performance is easuved by the ten average of w distortion function dtX,, Xa. For tiny given coding seheme, the exper distortion wl depend on the ‘breakdown situation, Here we f0CU8 On Dan the largest of the K iscortions. Dyas the expected distortion one can guarantee, subject to the assumption that no more than A of the » channels will break own, Tf the & channels withthe & highest capacities have broken down, a total capaces r=Dq co) is loft Then even ifthe encoder knew that this waa the situation, the Aisterton could not be made lower than 3p), where 8 ie Ue clastic Aistortion-rate fonction forthe given source and distortion mansu.? ‘ATorior, one has Dou Bp i {In Chia pape iis shown Usa chs bound is alee sharp, i Theorem: For €> itis possbie to achieve Pane < Bip) + € 6 by using appropriate coding with large enough block length ‘Thar, inthe problem of mininizng Dy one can do a8 well an ithe snd di knw which ofthe K breakdown situations was Ywaliza, The price paid for chia is that, ar willbe acen, one has effectively to “throw away” most of the excess over p of the capacity available in onwors situations, 1, REGROUPING OF THE CHANNELS the capacities C., > n — f ae all reduced tothe value C,» thea, by {1} and (2), the value of ois nehanged, and ifthe rsule hold ace sch reduction it holds, a forior, before Une raduction, This means thatthe extra capacity Ca 3 (Cot © can be used for other purposes, such as to reduce the distortion in ome situations below Day ‘Thus, we assume henceforth that C, — Gy xfori>nk ‘The channel coding theorem! implies that given «> 0 any channel of capacity C is equivalent—ior large enough block length and sith sppropriace channel cading—to «channel accepting binary bits a ate Ce and delivering thems with arbierarily sinall error peal, “Thus, we can assume that all channels ae binary with rates C1= G, 41960 THE BELL SYSTEM TECHNICAL JOURNAL, OCTORER 1981 =e = 1a), and that they tranamic blucks of sufficient sie “unaltered, ith probabil 1~ e, with ee: postive, abitrarily small ‘emma: For ull «> 0. i és possible to transmit sufficiently tong looks of binary bits at rate p~ e with error probability less than 6 tas lrg as no more than R channels are out of order. For che proof, let y,= Ci and for i= 2-2, Ch 0 "Then one bas @ fori = ° forizn—h By (D, then Aenumbersy ate nonnegative, Ax channel of rate Su is equivalent tof parallel channels of respective rates ys, + Woe ‘my consider the fllovng regrouping oftheee channel: Group 1 consists of ehenels of equal rate y. The Uh of these channels f par of the original chanel Group 2 consists of ~I hla of equal ate Thoy correspond tt parts of original channels 2 through n. Continuing in this fshian Group | consists of n— i+ 1 channels of equsl rate y. They ‘orrempond to parts of original channels é through Finally, group m — coset of A+ 1 channels of equal rate y », ‘orreqponding to orgivl channels ~ & ehrouxh [Note that far {2 --+.m— A, group fix missing i ~ 1 channels correspunding t0 she firs? — 1 original channels, "These missing ‘channels ean be viewed ax prrmanantly Broken down channels of an Imaginary group of n. Av up Wo & of the orginal channels may break dow, group 4, then considered is orginally made up of m channels (of rate 7), may have up to + i 1 broken down channels, This is 0 for all n~ J groups. 1a K. Now ee invoke the known fact" that n channels of equal rave, oul of which at mast & + ¢—T fre out of order can be wee! tease binary ica errr-cee rae (n= B~ e+ 1) using trancateal Reed-Solomon (18) codes! "Thus thew — hk groups viel total eor-ioo vate CHANNEL SPLITTING 1981 ‘To split a inary block among the m — ke groups und wasgn to each rou an integral number of bite—a multiple ofits Tea bloe coding Tength—rounding may be required with asymptotically negligible oases of vate. Tn addition, the assumed noiseless behavior of the channels only holds with probability (1 ~ e), As all he es involved 0 to ser an block length incre, Une lems proved, "Thus, there erst coding wehemes, valid in all X situations, which convey data from transmitter to receiver as if channel of capacity » were between them, Then (3) follows from the classical rate-distortion theory. iW, SPECIAL CASES or binary symmetric source with Hamming Aortion, thai 1X, 2) = when = ¥, 1 erwine, one haa Bip) =H ph ‘while for 0-< x Tis the faverte of the whore Ax} = 0 for z= sretion to (0,8) of hus) Forn channels of equal capacity , of which & can break down, one loge ~ (13) Togs = 31.1 tas p = tn = BYC so thatthe init of achievahiity ia given by Dna = h ML = tn = BC) (0) fin particular C= 12" (channels of total eapacty 1), then Dans = BUR ay For b= 1, fone insists that the distortion approach zero when all 2 ‘channels are up, one can achieve® distortion (2"" ~ 1/2 when ny ‘channel is down, which is of aver nf, however, one ouly cares hout maximum distortion, then one can spprosch A"'(I/a} which ia of order (vlog n} for example, n = 8 Jes) ~ 0082 and b= 1, then (2° — 1)/2 = 0.130 while 1902. THE BELL SYSTEM TECHWICAL JOUNINAL, OCTOBER 1981 REFERENCES 1G, gr Ifrmtion Thor end Rete 2 rr Mliciane a tomes e Phry of Br Caren (CHANNEL SPUTTING 1983,