University of Illinois at Urbana Champaign Spring

Description

University of Illinois at Urbana-Champaign Spring 2007 Math 181 Group F1 Midterm 3. Friday, April 27th. No documents allowed. Mobile phones, mp3 players, etc., are also forbidden. The one and only piece of equip- ment you may use is a basic calculator- and you won't need it. You must provide explanation for all your answers. NAME 1.Consider the following binary linear code : 0000 0001 0010 0100 1000 1100 1010 1001 0110 0101 0011 1110 1011 1101 0111 1111 0000000 0001011 0010111 0100101 1000110 1100011 1010001 1001101 0110010 0101110 0011100 1110100 1101000 1011010 1111111 0111001 (a) What is the weight of this code ? The weight of a code is the minimal number of 1's occuring in non-wero code words of the code ; hence here it is equal to 3. (b) How many errors could this code detect ? How many could it correct ? Following the formulas that we saw in class, we know that the code could detect any 3 ? 1 = 2 errors, and correct any (3 ? 1)/2 = 1 error. This means that if a single-digit error is made during transmission then nearest-neighbor decoding will recover the correct word. (c) Using nearest-neighbor decoding, decode (or explain why you cannot decode) the message 1011011.

• minimal voting


• a10 ends


• winning coalition


• digit


• look correct


• linear code


• shapley-shubik power


• code word


• error has

Sujets

• Linear code
• Code word

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 14
• Langue: English

Extrait

0000 0000000 0110 0110010
0001 0001011 0101 0101110
0010 0010111 0011 0011100
0100 0100101 1110 1110100
1000 1000110 1101 1101000
1100 1100011 1011 1011010
1010 1010001 0111 0111001
1001 1001101 1111 1111111
3−1 = 2
(3 − 1)/2 = 1
1011011 1011010
a +a +a a +a +a1 2 3 3 4 5
a +a2 4
52 = 32 32
01010 a +a +a = 1 a +a +a = 1 a +a = 21 2 3 3 4 5 2 4
01010110 11000 11000001
linearbinarywingfollogetsastothein1.Consider,vnotNAMEitanswers.yyour(a)l?altheforMathexplanationiovide(atpr010,mustdeoumentYfit.ordsdto(a)rWhatois11000.theridawseighetnearestofwhicthissocohaddet?OneThebinarywy-ceighetTheofaraycouoydecoisaretheoneminimallowenWumordsbore27th.rMidtermofUrbana-Champ1'smayococcuringord,inhasnon-wberocociso1)dedecowifordsedofthatthedecoco11.dea;vhencetringsheretheitkiseequalpietoand3.r(b)alsoHoplayers,wwmandeyoulderrorsvcouldithiswcoedeindetecter.?phones,Hostrings,wouldmantoydecouldds.idotdecorrect01010?er.F,ollodowing,t3.heGroupformSpringulasandthatofwiseasadwwinbutctlaaneighsors,thewde,ehknoyouwdistancethat;theonecodesdeascouldonedetectreceivan1011ymeaningeineis'tdedwon10you2.errors,createsancodforcorrecte-digitansybndusingaparitalculator-heccsumsasicquip-bofacerror.nlyThisomeansonethatbidden.ifoaandsingle-digiteerretc.,o.rHoismanmadecoiswusew,ythehaonecocomputewfioucoereSimilarlygivthethededeordfulldeAnsw:Thered.mp3e-digitMobilewvobinarydso.w(c)haUsingeneacomputercoewsrt-neigh(b)briteorwndecocoding,wdecofordeand(orAnswexplainFwhalyoneycumentsouNocannotAprildecyoFde),theF1message18110110120071.aignAnswter.aTheIllinoimessageduringUniversitytransmissionthensonearest-neighcorrespbdingordedeordcosding.will,recocovwerfortheiscorrect.11 0
0
0 1
1
Both the left−hand circle and the bottom circle 1 10
are incorrect; so one switches the number that belongs
0 to both of them and not to the other circle, guessing that 0 0
the original message was 1100011, which is decoded
1 as 1100.
The message is again incorrect; since two circles
10 0 out of three look correct, one guesses that the
erroneous digit is the one that belongs only to 0
1 0 the third circle. Thus the guess is that the message
received was 1100011, which is decoded as 1100.1
a a +a +a +...+a 010 1 2 3 1
0
a 6+1+8+2+0+1+3+0+9+a = 29+a10 10 10
0 a = 110
6 + 1 + 8 + 0 + 1 + 1 + 4 + 0 + 5 + 2 = 28
a4
28+a 0 a = 24 4
{A,B} {A,C,D} {B,C,D}
correctissee:aordawhdeocoatthecorrectwhetherarey,satheretime,andhv(eacthe1100001oneends5.withAnswaoterandto.v(a)toFind,theelongsccoalitionshecwkappdigitumforthatthehZIP+4decobdewing61820-1309.ListAnswtheer.hThethec:hecisk-digitthe1000011er.dehmyustherebwitheonesucblohofthatedecohasto,dwhomethominimaldiagramtner,entellsVathewithUseso(b)suc1.and100110uisis1001theforotingord:45,43,7,5,1]wwinningdeRecallcowinningtheinthathobtainscriticalneofohereendsnine-digitwithedaer.e,hec,Dummso?odictatorneoterhaselongveocoalition,abnoguresimilarl.v(b)etoIsertohevekingntheumvboerne61801-1405-2novpalidhere.?dummIfisnot,escainnotingyequivousacborrthenesumctustheyerrorw?endsIfay,outhatknohaswinthatcothethefonurtmherdigit61821-1405-2.isConsiderincorrect,follocanvysystemou[54correct(a)theminimalerrorcoalitions.?er.Answthater.minimalThecoalitionssumthoseiswhicequaleactovisthe;not).listthatsucorcoalitions(b)isthereZIP+4dictatoraV,taddrAnswwithk-digitetoandocerUsingthater.Answ.1.Is100astring?theodeeencostovdpmethowdiagram?ennyVoterstheAnswUseA(a)isnvthatwhicvbdosmatter),evhereroterwinnngissodummisvdictatorzero;;ywaeoterdon'tvhapvweisneoughwhinfobrtomaerytcioncoalition,tofromrecolistvminimalerotingtheabcorrectvnoumcanbthater.oneIf,thishoowerevFinallyer,awyeoterknoonewdotnothearataRecallv(tcoalition4.his'sthealensametonyi3.g,his/herwhicotehesn'tdosoesn'tveEndawithyaoter.{A,B} {A,C} {B,C}
{A,B} {A,C} {B,C}
52 = 32
5 = 5.4/2 = 102
5
= 102
5
= 103
2.20 = 40
thesearetheer.tcanAoneandt,toalen;,hequivconareonessystemscomputegwandthenminimalotiAvthem,ohweigh;otes.in2theindexsecondAsystemlthehominimaltherewinningosecoalitionswinningareeagainthetaliwhether?cideadein,areovTorer.nAnswoandosed(explain)v?ptAnswalenmanequive.wSoformtheoterstcoweighoformvmotingpsystemsCha,vcoalitionseust20hweumsameinmiisndescribigivma!)lwinningwinningicoalitions,iswhicwhichA,impliesathatmoretheytoalessrextraetheseequivarealenaret.AOne3could(b)alsoephrasewthingsAdierenTtlyho,winningnoticingcritical,thatvintbyothofsystems+at-2motionare,passesmanexactlytionswhenA+3tvvoTvcoalitionoterskind,vcotewyamongesthere;tionsththem.usaretheatcontheditkind.ionvforcriticalacoalitions,motionptoindexpassoiserthetionssamewhicinAbcriticaloth(systems,eanddon'tthiseislisttheAnswsameTheascoalitionssawhyingcthatAthecriticalsthoseystemsharetainequivhaalenet.w7.tAthanwequaleigh8,tedstrictlyvthaoti5nvgSosystemcoalitihasnsvtheethatmemcompbofers.and(a)orHootherwoters.manComputeyh(distinct)Banzhafcoalitionsoaerrofe.thereer.?oAnswiner.wThereyarecoalitions,1,1]is1w:ha[2edistinctcouncoalitions.ho(b)manHocoawitionsmantheyA(distinct)2coalitionseighavrthereeandtherewinywhicalihofexactlyformtwwt-2ootersvare.otersovaoteofYESrst?oneAnswuster.hoTheretareoCeopleand5rstso:10,9,2]are[11:systemscoali-otingofvSimilarlythethereAreCwinningtheinkiofhsvcondeThisoierallorderisaccouninforwinningthesoinBanzhafsystemoforgeteroneoftoistheblolocoalitionswh(don'tcthattneedsatdoublevnisbcoof6.coalitionssucwhhccoalitions.a8.otConsiderrthecriticalvnotingtosystemt[8the:5,2,2,2,2,2].cking(a)inWhatiahrhesametheoterwinningcritical),24
For each permutation a circle indicates the pivotal voter.
A B C D B A C D C A B D D A B C
A B D C B A D C C A D B D A C B
A C B D B C A D C B A D D B A C
A C D B B C D A C B D A D B C A
A D B C B D A C C D A B D C A B
A D C B B D C A C D B A D C B A
Decimal digit 1 2 3 4 5 6 7 8 9 0
Bar code
5 5 5 84 3 8 8 6 ?
a 5+5+4+3+5+8+8+6+a +8 = 52+a9 9 9
0 a = 89
ting,oneobtainsthatv,notAsucandcBlongarevbgivothvpivAnswotalunreadableinan8bp9thermoutations,tedandythatZIP+4CpandTheDtheareofbnotothtablepivnootaleinco4mpforermeutations.[DividingendsbobtainyrecthethetotaldenutationsumTherebAnswerdeofbpdigitermsequeutations,aonedoobtainsondthatinthebShapley-ShAssumingubikerrorpmade,ostillwtheer:indexvofbthisthatsystemerisubik[8/24,8/24,4/24t,04oting/24]=[1/3,1/3,1/6,1/6].w10.aRecallwtGivhouatoforerpracticalcorrectpucor?ptooses,ermZIP+4arecoer.desoter.(alonger.withcotheirisccorrecthececausek-digit)9thareisprin(thetednceusingshortbarndcobarsdes,eswithcorrespCountow.ything.theromawogete).thethatZIP+4otherdehasaseeneenwbarcancorecodeerandcorrectdigitsde:theelodigitbhbleustaeththeeacinindexdonewisphShapley-Shwhichonsider,eIs:5,5,3,2],the1cosystemdevbeighelothewwithcorrecten?soIfenot,thatcanthe9.follFothiswingecorrespthatondencecorrectbcoetww55435-88688.