On the Construction of Minimally Redundant Reliable System Designs By BD. K, RAY-CHATIDHTRT (tanunsin sine Seeman 7,180) Siveral authors wr conideral the pueibiity of Inewasing the ve lty of ange and comply bonny Agia eyteme by antracing come esata in te atv. Ta 9 rompenin pope, Armatoug! prspoate e Ieeme for opplaing error cuttin tn apnehatn digital system. fo this paper tee evclop a general matbematial teary for generating sity secant mecractning oe for the atk ie gation Th reels tv aha! are ead “wnsnimaliy wean rls eptems.” The room of constructing mama redundent reine apne wl ote Dus dan of vce wo Gere fst Sn ma ene vk ef the stom Se compelly med An example is conatderet vm detest showing how the theater oa te 2 In eunples binary gia stom eroplang large suber of blake ui ghetsiea eqapme often ix dill a enrune safe eel ‘elility of eae single Block equipment. Aw alec tn allan the ese gues of revsility by senprosing the sei af each Boe hag: prev to no vel etter handy itm sore feelundaney ia the syser, i is wvsble to eonteuct highly eeliable Capleton, eve though ote single lore nok aa high rahe Moorea Shvimone Tigwn’ Won Newnan! Coggeen cl Anson have considenal the pwiblen of souetructing sebable syrem designe Fri paper geal anatheratral teary ts bre evel fa he ronisttsion af saintly redunciot ellesweter deigar bee ea Uvewene tied by Armstrong Ths theory lool vlan to the vary of ervor-corsvel ng lee. The rubies if consti miimelly edna sytem esi seer jae wl le foo ance whee nei ant ft rst one blk of the ysis complete ened ie ‘hi paper 596° nu wz, NAA HreUNTEAT RUSK, WARE 1 Spee thee ae. inary ie vavnbles X), Nay ==25Xy Tet By denole the set nf 2" mepace binary sequen, Beery ae of wales oF Whew Lig input vial il be egurded aes wane of By Ane Trapping of to wil beled a Bowens fein uf the m inp ashlee Xy, Xe, sym. Hoe the sake of brevity, the cllertion of put watabies willbe denotes ay. Lot Sn Pinyin finns © Sany — Fe Pies See se pt Hoole fantom of the m Kinsey wacables Xi Ney o> hm (Gur relies in canst systems whieh wil iene he pe Boole fanetins wi highilgrewut rll. Thesgtem weeebloks felted equipments each af which ean agzitesan » Boolean fare tions. For the sake of hesity. a elletion a p Donk functions, wll Ta called Loolan p-ftetion. Thus J. = (Ja yfuy "fig is Booenn prltmetion. Any Rasleun p-fonoion iw mapping of By inco By. ac ‘ork of our srwem eyathesisce « Boon ptusttion, Fig. i «oche= nati igrom for the original nonredundant system, "The books wet of unis in thw eyotem. If there i «Seu ix bleak, ‘thea some oral she p eusputs of thr block are erraeous. Ln other words, inthe ease ofa ual « Dock wil syuthesae the corresponding Boolean pplunction song's. Het Pe! vote Ue oot 2 ey pple, Chon tty Bovlear petro ‘aes vals on Vs Ua Var devote Ue rt ‘ach cy 8 an clement of Ty ‘Lat f f.). Thon f ean be regarded oe a hpi i no, We dts an of pcp se ‘ual mod 2adution. Furesanpie, ify ~ 3, ey ~ (001) snd as ~ (UCL), I c+ ae = (100). Lar ado! be oa serene of Py! given by f= nya eh and a= aad oon ah Whe ae Fa fs define to the clement fay + ay a6 fh The p-tuple Tie) wil be calle the wid clemone of V2, The might aa of the Keverion a is defined :o Ie the muster won leazeats among uve, aes For any partie value 2" ef the input veeabiee Ha?) lea veer iV, Suppose thee ate faules in t(¢< #) blogs ‘Thon ¢of ta fncions fff wll seutheizedsronely. Lece Ahn pat wil be the weston f°) fg where e = Cente sh vector in Ville weight 1. While designing « systert to syuthesine the rola fanotion (ome mighe eequce Ghat whenever the mumber 0 fanlty blocks is or Kass theourpt ie orortr, ue en adie Thi introucng moe nssdaney in the syste, hy myescing (e+ 2} {Boolean p-anctius and ailing 2 gia corrector nit vo the system. Suppese es ress. 6n6 1 ole panels wal i mapping ot Verona Ve West onaider @ gy gay “oor am function from Bato V2. Fie every value X? of Xy (in an elena of Py Suppose te Funeione and (pone the property P stated below Ror viny seesor ¢ Selpnging to," wit aCe ot exceeding ¢ sd ‘every wale A” of the ina variable Cup6XO + = 8 o ‘he fwselions ¢ and © enable vs fo sonteuct @ sytem which wil yn the Boolean palit tiai Jos ee of eur whenever tie muster af tly Blacks in the we #2 lee. ‘The n Boolean Tuesioutvs seat he emedesed ata colletion ap Bunter, functions of mnt vaviaes, ‘Therefore we ean evlly obiain the Tegal desi of wnystan which wil sethesse there np Boolean Fun tions This sgatem wll be callin Ube evilor swbayaton, Silay, che function € can be considered sn elect ofp Boal fuxetions of fp binary it varus ad therfore we ean obtain w system Which Sei acheize howe pt furl. This sprtera wil be eae the oor ect vsligatem The wp cuits of the end subsyetem wil be tar “sof tho eanretor subsystem. Now it easly een that, because fhe progeriy of the fant g etd Mbensver the mime of fant bloc the enor ule i 8 and che erator it ittiee nf erer he a tate af the sormtr sgt wel br FIN = EIR FAN XI SAN eat Naat Ne ier Fol Sl We =a) A schematic dngran Sar sho whole ester geen i Pig. 2. view of 508 ume ne, svar rmeteAT parnVKn, Na meHE “et meu py, i | L am 9 == tho abore dseuson. the ling wwe fins given Tel are weigh Dentin The tonetiont eye, 64 and C possemsing the nopestyP stated fa 1) ills riled eels stm dengn of order [ea essary e = — doe Pho Boeloan tances fey fi Definiin 22 A reliable system design a! ardor ¢ and sedimeaney 7 fr the # Boles pfunesions fy, fo, ~~ fe wil clin animadty ve tute it tho vedundarey #2 eee veliabe system design of order "iv the scane Suction is ot lise thar Inthe pret per ne lve mien el of ining ily redtaat syst ceo ee ar any a of Baer for sebitary # od p-Hyetens desigue of ligher weer wl Le given ia sales pe ‘We fuave tnd fe redundancy ras amas af the extra atnount of ounipstent shih has sv be toe Got taking te agrlees celle td Tron ne sek che set whivh has mint posible vale of the ge Aivtaney ns epi ot that ne acamaa thae the rorrestae Pulasatet dewet mae ate ern at all "Therefor, tonne be whole “leveopmient pracy Houle, Hs impel al ite he ae ff equipment nevswary forthe rant ulnystew fe anal in ome prison tothe arnt equipment ees fe the whale ap¥cem, oF That other segs I taken asa suggested in Ref hy to ens stilt of te worn ete. We have nol une sy a inmalial aeporne his roquiement. i the develapment of the thors Consider two vectors wen a Ieloaging 0 Vy" The dteare dfoya"s botieen the tivo elms of Fy ied € lela +o}. Tht Daespssua enrspasey mekzasta waa 30 = Logynon eos em ot 20 She msn of steers for which on 2 a4 = 1p p Forexanspe Ip n= shana = (01,10) id 9? — (01,1610), then ao = {Wio1.W) wl ane?) ~ 21 cam be ewily eheokes chet the ditenee Aisin) bow -atcties the tones emeitinns ol aidan fanetion, We hoe men Ms Belean pation etd i Sertion IL ea be oe ihre ae moppinge of fy ante Vy A Boolean pfunetion fy wil be led a dagenanat Buulor Saveton for any elezaeat a of Vy Tne iva eahue of the inst yards X tor wih 20) — a. We ‘hall testi that all Boolean pfusetions sppeasing i uur discussion te nondegenerate, Inthe hilowing we bavee = 2 and nF "Pheo f) A neeeesty wi sufr'srt coaitinn that there ets seliahie syste design of omer # and reducdaney » for thn & Booka Dnctions fu Jey Joi ths these exists a east A uf V2 wont tng element sich thal a) 2 2C-F eed © As a ‘Poof Neca, Suspose wow ev ai 9 welll svat Ar 0 font ther Tanetions be — tye) a the coer Fhoeson fe. Faw every walt X? of che input variable X, gf") 3 8 retro! Vy", Cowes the st Aa tei) XG Me Using the fact thot the Raakan pfuneions fe, «25 are nomen igeorate Fantions, it follows rasly that the set 8 corn nT Srecnra af yh Conder tw diinet wekom ral a of he eet TE posible euppess lla’) 2% Sineo ni?) 2) wean find vector Cot Vpteuth tinh ate = a? teddies) ££ Sine alel Sly we have bun = Cal be ane a) [Bquation (8) vovlendiess the assumption thal » nd a! are dstinet Yeetone of "Poi spect the root ef acne Siow, Buoynws le eubect of V7 comtaing # element aaa Dein the property that ne?) & BE Is aya! yw 2 as Wo ast tp tu-towne eorrespunnone Iewern the # weetore of Py and the oF sroters fl, or evere value ot the pau variates WON) = Toe gaN hts NOD fea seta of Vad shore es umreoling ‘rotara af Fy Delongingio."Thnenehefnetiong = (ecvses os.) ieee by ER = BET 3 ee AI ee HN besa ta wo WoO ee nina svstune necestoen aoesn, AREA at shore cis the wert oH elgg A and worrespcng 19 Te Sector (LX°) of Ve ectoreo function © ie deine in eh felling rmaniee. Tet y ='G1,, 74) boat asbitrary veetor of Vy" Fist We ehoeen a vector w belonging to a auch that dima) lr, toe! (lc Lat = (8,9, yo Oe che woetr of Vy" whi eorseeponde fhe. Thea we deine co) =a oy Thuy Cs manping of Fe onto Py ist tr sherk that the en oder function g ad the canrsererfunetion C defined chore ports the tomporry stated in Setion LL. ‘This eamplstes the proof of sue-aney. ‘Tieaam 2 Li shore ests a robb spam design of order fund re- tundancy » far F Bones peirtiony ee vert (Je-ve()e-vt+Q)e-n, w where a = ef rand Profs Feo Thoorea I it is ueewsney thal there existe awubeet A oh with the propery that Mog?) BBA lat Sy done the set of vesters > of Vy" with the property that Aya # tI follows cay from (7) that, For any tn dstinet vectors fend of of A, the sete S, end $," do nol nave any zomsnan eement Tot 8. denote the sot of elemnts of Vj? which huve distance from y= O12. Obviously Sais tho union ofthe (1 + 1) ate Se; Bayo 8. canenine od A oat fi + ()u=0 sori, Thre ate sh nmovesapping sts and the tote nombor of Skomigar sie ome eto ‘Oo}. eee[io(u-n+ (Qua ‘Theorem 2 follows fom (83 yet design of one ter Baolesn punetions, Theorem 2 ie wetually "ecnceabzation of felt uf Hamming Tiel nar) dene dhe axis integer » for whieh dee existe a relalenyster dep ade andl sodudaney for Fn =e Bohan spfuncions. Port ~ 1, the inoquality (6) hovers aeons Hen we ave 1 ection V we sal show tha 1 ere exits role eyo ssa a onder¢ andl redundancy for & Panes pofunetions, then mite) = Tem wet me of: Suppose me) = 2 Thon here ests teliableayste design ofr Cand redandaney rfor& = w+ Boolean punetions. Hence bay ‘Tlwonean Lthsce exit a suet fof Vy" contaiing st eloments wwith the property that aa’) 2 24 Lj mae yw ew Torney Proteus ooo ol We ase the weetor = fanart of Po Tine we have a subset dof Ve lls poses te property that el na Hea, hy Theorem 1 ve ca asin a oiable apstem design of order ¢ nun! seundaey nor P= 69-11 follows tba ni Shed Lent dame s heorem d> I fr celiahleavetea design of onder (and redundaney for Tnlean ptanetinns we bse dr =e eR Smt ry Hh te design e mivilly ronda, ‘Peni Ii poedle, sippie the ayetem isnot mixizally redundant ‘Tim then existe a ohuble sytem design of onder ¢ and muna” UZ em nena SwRI rreeNteAt SOUHNAE, MARCHE 11 Tor Bune pedis ben ig sna pain iter emi? 2) 2b} es, BY Lemme | nr Bee be EEL @-0, 9) The Foquality (10) mesos Tae igual (Hs heme the theonem “all Th thi seeton we sll wonder pseu subelas of spat di sigue hefner og deine, To define che ina ester = Sips we ne tase te tery fn el a A be sh ne Hele Ml edoaerinty 2 roving = 2° elemwnts aed ¢ denote a pinion cement af Ks binary ple ( resp tae elem Neyo dps) wll be made to PP of K and Vie vent. Aw ment a = ayy ay oy Tider am an aevector with olexieuty i Kia wight we) of a io Sal to che nmber of nos elements onion oy: Me cum of fo vectars ae = fe ug, +a) eda = fe defined toh Fal Co bit my osm Obinusly V," is 8 eter spe aver K. Conider w ayitom design fr 8 rules pfutetions Spo te ener i ti i ‘For every vove 3° of the input variable N, 68) = WM WT] or (8 i veetor belonging to "Let Am Bia iX eB. ay Depwitiow 3: A eystem disige for Bowl loa system xin ifthe subset of Vs died by (11) fo wertor Terwen 82 8 snenaary aad alfvent condition that teliale ion system sign fie © Boal fone ions eof onder #38 that hee ‘Meng soma. eeetor of the svt fined I HT ul law Geb. ‘Profs Heese of Uhre, i woul beeen to how tha Maal) 221 wal eA, aaa ay e2 p-imitions is si ob listeria BROMNDANT MULAAMLE shspi8a8 603 By detaiton afc) = ae — a) Sine A en woetor spice, bo! ‘eee element off nd shy ®— ao” ha tonal element of 1, Henee follows that (12) wl hold aad only ole) 2 2-F T foe every nan a leant "Dajte fo A nals A with lets wl be id to Fave Pe tPorpeoperty fo msl the assy ae ines depend Theor $7 A nesoaty and saivient condition for te existe of telihle linea system desig of ver Fand rekduney efor & Boolean Pimesione is ual Hiercanile x aig Mish a= (i br roe andr felts ith ermeata in F wich posses (Por Profs Slfeeney. pose the tne Wise iy pe | Mame tn Tet eno the vector spur orthogonal to the vector sper ens by the rotary verlors af Ms roan at Inst elementos Te ould Se ation to sbow thn Ue weight of ay toma ses A ea fact Ge -F Li IL posible, suppore 1 cantare s soneul erotor ith Sweight Inc haw (20-4 1. For szpliity of wring sane that the Neon = dims aes ane O.=-.D)denystn wera ya ys Ere tone ests of Kher en a, fgets Hoes Howey OF Moy) Bquation 14) imple thot the fist 2¢weetans of the wsileie I ane Tivonlyckpendest chi Te contnaditier Tie wompleti the pn slices, Novowity ean he prowed by exsely sila arguments "he wader aequsinted ih the hleatune ox eror-oorreting fnene revi wal teengaze from Tense ttt sealer ete Sigu af der for Borde efonetions exists al only if Crm egrets with mph ae afr ‘omoetng ina eat fio pees existe, Leman and Thongem 4 een above ate not new sean Hey were pee Bose” asa Zine in w eierent “orm. Wo Enve inl sr! pis fr these reat for te ke wpe In 4 sceton yo sha hoe Is fe sstreting zininelly oe dundantfiwar syetem desis fone Afar oon ptt fr say sabienry yale Cael p Tern 8 nde) = cass Poses Ln Setion IL we proved ta mo a2 ene it wil he stent show te Hl nian tt «ast Tr prowe (12) sve shall construct a mnsris M ithe eoumns and x = oF = 1)jta D sows hich has (P2)-poperty. We shall denote the elr= entaof by Oty, +n, where Othe pul elements i the rukiplseive entity. Conviler she mie AF ven be ["] a= cas) L shone isthe identity nitric with rows wl eulane ad Bf 8 8 snstrix with rensms wad # (m7) roe given below: Doo 1 an oo 0 bake 2 1 can be easily cela thot he matriy A hus (P':)-propert ie m0 hyo rows of APs Koratly dysnent, “Tis wont Une pron! of Th ebwull be observed hal Tlnorein 6 enables wb csteus wally rsndontsystom designs of onder I for any arbitrary vals of ke nde Far gv fe dwt ta integer + for whi air <e mG) ~~ bw somseruc the amas AY with eas and (7) tune dete in (16) ad he an the atom desig a trae