Decoding binary R(2 5) by hand

DeodingBinaryR(2;5)byHandPhilippeGaboritLACO,UniversitedeLimoges,87000Limoges,Franee-mail:gaboritunilim.frJon-LarkKimandVeraPlessDepartmentofMathematis,Statistis,andComputerSiene,322SEO(M/C249),UniversityofIllinois{Chiago,851S.Morgan,Chiago,IL60607-7045,USAe-mail:jlkimmath.ui.edu,plessmath.ui.eduAbstratThemainpurposeofthispaperistodeodethebinaryReed-Muller[32;16;8℄odeR(2;5)byhandbytwomethods.One,therepresentationdeodingmethod,istheanalogueofthemethodusedtodeodetheGolayode[8℄.Theotheristhesyndromedeodingmethod.Wealsodesribehowtodeodeotherdoubly-evenself-dual[32;16;8℄odesC83(or2g16)andC84(or8f4).KeywordsBinaryReed-MullerodeR(2;5),Hammingode,Represen-tationdeodingmethod,Syndromedeodingmethod.1IntrodutionItwasshown[8℄thattheextendedbinary(ternary)Golayodesanbedeodedbyhandbyprojetingtheseodesontoquaternary(ternary)odesofsmallerlength.Ithasbeenopensinethenwhetherthisideaanbeappliedtohigherlengthbinaryodes.WewillshowthatthisispossibleforthebinaryReed-Muller[32;16;8℄odebyusingthelinearHamming[8;4;4℄odeoverGF(4).WebrieyexplainhowthebinaryReed-Muller[32;16;8℄anbeonstrutedfromthelinear[8;4;4℄odeoverGF(4)whosegeneratormatrixomesfromabinaryHammingextended[8;4;4℄ode.Fromnowon,wewillallitthelinearHamming[8;4;4℄odeHoverGF(4)althoughitisnotoneofthewell-knownextendedHam-mingodesoverGF(4).ItsodewordswillbealledHammingodewords.Reentlyithasbeenshown[4,5,6℄thatthereareexatly3evenself-dualadditiveodesoflength8withminimumweight4overGF(4).Amongthesethreeevenodes,oneisthelinearHamming[8;4;4℄odeHoverGF(4).Furthermoreitwasshown[4,5℄thatthebinaryReed-Muller[32;16;8℄odeanbeobtainedfromHinthefollowingway.LetbHbethebinarylinear[32;8℄odeobtainedfromHbyreplaingeahGF(4)omponentbya4-tupleinGF(2)4asfollows:0!0000,1!0011,1!!0101,!!0110.Letd4bethe[4;1℄binarylinearodef0000;1111g.Finallylet(d84)0bethe[32;7℄binarylinearodeonsistingofallodewordsofweightsdivisibleby8fromthe[32;8℄oded84.Then(H)=bH+(d84)0+f1,wheref1isthe[32;1℄odegeneratedby100010001000,produesthebinaryReed-Muller[32;16;8℄ode.ThemainpurposeofthispaperistodeodethebinaryReed-MullerodeR(2;5)byhandbytwomethods.One,therepresentationdeodingmethod,istheanalogueofthemethodusedtodeodetheGolayode[8℄.Theotheristhesyndromedeodingmethod.WeremarkthatthesyndromedeodingmethodanalsobeappliedtodeodingtheGolayode.TheadvantageisthatthismethodispurelyalgebraianduseslittleknowledgeofthestrutureoftheHexaodeoverGF(4).Attheendwealsodesribehowtodeodeotherdoubly-evenself-dual[32;16;8℄odesC83(or2g16)andC84(or8f4)inthenotationof[2℄byusingthesyndromedeodingmethod.SineR(2;5)isa[32;16;8℄ode,itserror-orretingapabilityisatmost3.Itisalsowellknown[1℄thattheoveringradiusofR(2;5)is6.Ourdeodingshemeannotonlyorretupto3errors,butanalsodetet4,5,or6errors,andinadditiongiveaosetrepresentativeofaosetofweight4,5,or6.Therestofthispaperonsistsofthreesetions.Insetion2,weshowhowtoonstrutR(2;5)fromthelinearHamming[8;4;4℄odeoverGF(4)usingtheideaofparityofolumns.Insetion3,wegivetherepresentationdeodingandsyndromedeodingalgorithmandexplainseveralexamplesintwoways.Wealsodisusstheworstaseofthesyndromedeodingmethodandompareitwithmajority-logideodingofR(2;5).Insetion4,wedesribehowtodeodeotherdoubly-evenself-dual[32;16;8℄odesC83(or2g16)andC84(or8f4).2TheReed-MullerodeandtheHammingodeThebinaryReed-MullerodeR(2;5)isadoubly-evenself-dual[32;16;8℄ode.Itisoneoftheveextremaldoubly-evenself-dualodesoflength32[2℄.ThelinearHamming[8;4;4℄odeHoverGF(4)isanevenself-dual[8,4,4℄odewithrespettotheordinaryinnerprodutaswellastheHermitianinnerprodut.Fordeodingwewillusethisordinaryinnerprodutbeauseofitseasyalulation.WetakeH=2664111111110000111100110011010101013775(1)asageneratormatrixofH.WeindexeaholumnofHfromthelefttotherightby1to8.ThisishowwerefertotheolumnsofH,i.e.olumn6is(1;1;0;1)T.BeforewedesribehowtouseHtodeodeR(2;5),werealltheprojetionofbinaryodesintoquaternaryodesexplainedin[8℄.Considera48arraywithzerosandonesinit.LabelthefourrowswiththeelementsofGF(4);0,1,!,!.Reallthat!=!2;!2=!,and!=1+!.Ifwetaketheinnerprodutofaolumnofourarraywiththerowlabels,wegetanelementinGF(4).Inthiswaywehaveaorrespondenebetweenbinaryvetorsoflength32andquaternaryvetorsoflength8.Forexample,2letv=(1;0;1;1;0;0;0;0;1;0;0;1;0;0;1;1;0;1;0;1;0;0;1;1;0;1;0;1;0;1;1;0)bethebinaryvetoroflength32.Thenv=12345678010100000100001011!10010101!1011111010!1!1!!orrespondsto(orprojetsonto)thequaternaryvetor(1;0;!;1;!;1;!;!)oflength8.Notethatthisorrespondeneislinear,i.e.,ifbiorrespondstoqi,i=1;2,thenb1+b2orrespondstoq1+q2.Lettheparityofaolumnbeeitherevenoroddifanevenoranoddnumberofonesexistintheolumn.Denetheparityofthetoprowinasimilarfashion.Thustherstolumnofthe48arrayoftheabovevetorhasoddparity,andtheresthaveevenparity.Thetoprowhasevenparity.Lemma1.Thesetofallbinaryvetorsoflength32withthefollowingpropertiesis(uptoequivalene)thebinaryReed-Muller[32;16;8℄ode:(i)Theparityofalltheolumnsisthesame(i.e.,allevenorallodd),andtheparityofthetoprowisalwayseven.Allvetorsofthisformonstitutealinearspae.(ii)TheprojetionisinthelinearHamming[8;4;4℄odeHoverGF(4).Allvetorswiththispropertyformalinearspae.Proof.