H of BCH

Codes correcteurs d’erreurs 2.Detinition dePanneau &. par A.Hocovencur, Les eltments deVanneau €Lsont lesnombres entiers éerits en Professeur auConseroatoire des Arte etMétiers, ‘numeration binare. Ingéntenr conselt& laSEA. "Achaque élément deYanneau elnous faisons correspondre unpolyndme ayant comme corfiients leschilfres deTélement. Lepolyndme estalors défi aur lecorps decaractéristique 2. ‘Toute opération surleséments de@Lsera faite surlespoly- Généralisant untravail deHamming, Peuteur construit descodes ndmes correspondants —aucours decesopérations tout coefl- permettant decorrger kerreurs dans une transmission deGigi) clent pair sera remplacé par O,tout coeicient impair par 1. dinaees Lerésultatseraunpolynémeauquelcorrespondra unélémentdeFanneatt et ‘Thepaper isgeneralization ofHammings work Theauthor giver "Ge Gone toutes lesopérations habitulles surlesnombresa,lng Rem sae Wocorrect errors m4tramomiion of«40% *40neTee orrs toutes lesexpressionsnary Ge calculées seloncesrégles seront suivies deVindication (¢t) Eine. Arbeit Yon Hamming verallgemcinernd, entwikel der AutorKoder dies ermoglichen belUbertragungbiaarer bitskFehler su Exemples: Korrigleren. Addition :1014111=10 (@)x suenuraca.Multiplication:101X111=11.011(€) sonoaespants eamPepsiMea gp.Pulasance:101%=10.001(&) Division:1.101—=11110411 @) . Enparticulier:p+p=0,(p+@?—p+a(t) 1.Introduction. Loraque lepolyntme serairréductible surlecorps decaracté- ristique 2,nousdirons quelenombre correspondant estirréduc- Introduisonsdansunsystéme detransmission unmot,consti- tile(i]madmet pas,dansTanneau el,d'autre diviseur queIui- tug par unnombre den chifres binaires: smémeetTunité) 8,Oyeoveeeee My On peut classer évidemment les nombres dans l'anneau et ‘Lemotreeu peutdilférer dumotinitial paruncertain nombre Parordre degrandeur, mais beaucoup plusimportant estlenom- erreurs (certains chiffres a,étant allérés en1—a). Pour esaayer bredechiffres. Ondémontre queparmi lesnombres ayant undedetecteretdecorrigercenerreurs,onnrtilsequemchiliesnombredechifresdonné,ilexistetoujoursunnombreirreducible,dumot comme support deinformation, leschifres restant appelésEtant donné unmot éerit enbinaire chifres detestdevant servir alaverification dumotapres la peleatransmission. Donner uneloidedétermination deceschiffres de inn++Ge .testenfonctiondesmchiffresd'information defagon&pouvoirNOUSSeared ‘4chaqueindice¢unnombrep,deVaneaucl) détecter —oucorriger —unnombre maximum kd'erreurs, c'est ®t##motlui-méme nous attacherons lenombre formeruncodedéteoteur —oucorrecteur —dekerreurs. T=0Py+02Pa+--++0Po(@panzexgmple leplussimpleestecodedeeclear d'une erreur. GestIaconsdération dunombre Tquirice&unchoixconve- inscecasm=n—T1,etonchoisitlechiffredetestdefagonabledesnombres p,nouspermettradecorrigerleserreurs quelenombretotaldechiffres1dumotsoitpair.Lavérifcation Wwetuaies ne Permett vas dumot consiate alors enuntest depari Hamming (Bell System Technical Journal, 1960) &donné ta Joideformation d'un code correcteur une erreur. Lenombre de3,CadedeHamming. chiffres detestestl'entier Ndéterminé parlesinégalités: &Cone ms an Logit +m) ZN <14Log +m) Nous retrouvons lecode deHamming enfaisant ‘Dans lecasgénéral d'un code correcteur dekerreurs, lenom- ant bredeconfigurations derreurs possbles est: Leschiffres detestsont leschiffres dumot indices Ha1+G44...4¢h 1,2, 2%524 (Ndéfink parlesinégalités 11). information sera portéeparleschifres Parsuitelecodetepluséconomique uliliserait unnombrede portearleschit chiffresdetest égal &I'entier immédiatement supérieur &LogsH. teMeSaOrGe++ Ge ‘Apart lecode deHamming, onn'apuconstruire detels codes. eux quenous proposons ulilisent unnombre dechiffres detest Ondétermine leschiffres detestparlacondition feat4 T=Ipaq—0 n—m=kN condition qulseriet 1ditérenee a Nagy= ta, maAN—Logit ttBay+day+2.+QM=Bay+Bay+Bay+a estdeYordre deLog,(k!), doneassez faible pourquecescodes @ Solent satisfaisants Lesecond membre estunnombre binaire conn dau plus N ‘Aprés avoir défini wnanneau dans lequel nous ferons nos chiffres. Liggalité détermine done parfallement lesvaleurs des calcul, nous exposerons lecode deHamming sous cette optique, chires detex puis Tes.principes deformation des codes qui nous conduiront Si,aprés transmission, iln'yapas d'erreur, onrelrouveraAunedlermination quasiexpérimentale etAunedétermination —T=0.systématique decescodes. Nous terminerons par unexemple de Sil yaune erreur portant par exemple sur lechiffre a, de correcteur de2erreurs, remplacé par(Ia), lenombre 'Tprendra Iavaleur: Renrintad with veretaton fren Chifires. vol. 2.om. 047-008, 1900. A nocavencnen Tay+eyosboll—ay)+oss+mmycsa(Sie rangdecettematrice(dansTanneauet)estK’<K, 1avaleurdeTseraVindiceduchiffeerronné. eatqueKK’lignesdecatematricesontdetcombinationsFreerecentootaaheehiffesd'indice@otpslnétiesdesK’lignesrestantes,SiTonsupprimecesK—K’ srpeandeeemeereurs:Portantsurleschivesdindis@etPigses"onabtiendraunematricM’denombrespulvériferontTaatpno (@) encore Iacondition (42. 7 Ceci étant, nous pourrons extraire deIamatrice Mune matriceStUyaplusdedeve ereurs, Tpourrait tremal.Leeile earfe' de gues dontTedeterminant alas dantPannen obtenu estdonecorrecteur ume erreur, détecteur dedeuxerreurs. GT", 4.00Je,MenstontoTlestcommode,pourautomatiser lecontrole,desupposerles |Onauradonenombres pdisposés enmatrice, Par exemple pour ®—7,omaura ata= . tamatrice Duiaque lesseules valeurs possibles sont 0ou1.Enanutiptiant ta |coors Ime Myrnotarial Mois denme|o1rooit Isque wi)fet 1010101 ae he Oo10110 et 010010 vi be| correspondront lesmatrices ctparsuite lesnombres p",-vérfieront encore lacondition (42). De"plus,tamatrice M”contiendra Ace moment 1amalrice goocrte| goocere |BoX'S,cestadire lamatrieunit,donePensembledes forgery) ot ooreo1o | contiendra lespulssances successiven de2! ooro100 | 0010000 | ermal - Lenombre Tshtient enfalsant suivrechaque Tignede11.sag a ane cmtienindicescorrespondants serontpriscommechiffresdetestet beraeheioryreliahaaael lacondition (41)déterminera ceschifres enfonction deschiffres 2 : information parégalité dedeux nombres binaires deK”chlfes. ° jt ‘Tout leprobléme seraméne done &construire desensembles° a fo las denombres psalisfaisant AIncondition (42). ° im Lepremier nombre estcorrect, le5chifre dasecond nombre est faux 5.Formation deproche enproche dane suite denombres p. 4.Principe d'uncodecorrecteur dekerreurs. Prenons d'abord Voyons maintenant Aquelles conditions doivent satistaire les Pah PB AP oyPeet rombres ppourquelecaleul depermette decorriger kerreurs. Puls: on‘Noussupposerons queleschiffres detestsontennombre suff- Pari = santpour que, connaissant leschifres information, oopuisse Passo ialiser Iacondition Cesnombres satisfont déja auxconditions (42). Pour prolonger co T=Eap=0 @ cette atte dans ordre. dedpcroinsants, supposons. reareié Siaprés transmission, teschiffres derang funombre p,de{chifres. Considérons Vensemble des nombres tytn GER) PyApet deleurs sommes dans Tanneau el.pargroupes de2,8, sont erronés, lenombre 7caleulé surlemot déformé prendra Ia!" "(ak—1), Tous lesnombres oblenus ontatplus 1chilfres. ae: Sif existe unnombre non content dans Vensemble ainsh forms Tapatpate+Py ctcompris entre p,et2cenombre seraprispour valeur de 1fautquelenombre ainsitrouvé soitcaractéristique desrangs ,,(gilyaplusieurs nombres onchoisira évidemment leplusthyOy)soosGyCeateedineque PeSinokprendeaPreyae2 °Det +Pat netDes#PertPart+Per(&)Onpeutainsicontinuerpas&pasjusqu'dVobtentiondes Joraquenombres p.Sip.aKchiflres, lesnombres isk fer 162528 5BEE ate de emreteedy(nd serontinclusdanslasuitedesp.Lasuiteseradonedirectement (ht oss CedyoyDs Staaetuncodeesters8ablfetablenwde nae correspondance entrelesHvaleurs delasomme Cette eondition peut encore sSerireutpat Pe a) Geh anDutPat...tpuz0 @ putpat+P« oraque12k etlavaleurdesindicesayedey+1a cependantBa atueet Teprocédéainsidéfiestassexlongaexploiter. Cependan reais pourdesvaleursraisonnables denet,ilnedépassepasles "OndevradonecholsrlesnombresptelsqueVaition,dansPOUitrvaleursTalis eeaeance.Tanne tap 2kdecesnombres donneumrsa non PONIES Ue cs nombre Kehires detest ari faraitasserdifficile. Aussiallonssnous exposer anprocédé plus Usefoisdéterminé unensemble demnombres p,ilfaudra Paral alonechoisirtesehiffres detest.Ihestcommode pourceladeremplacer **tématique derecherehe des nombresP- ensemble oblen par unautre ensemble demnombres mais contenant lesputssances suceessives de2: onsystématique desnombres p.1626.28oopBE 6.Formation syatématig Kaésignant lenombre dechiffres duplusgrand nombre pobtenu. 1.4qhéorie descongruences, siutilise dans lespreuves des Disposons pourcelalesnombres penunematrice Mdexopérations arithmétiques, vanousfournir unmode decaleul descolonnes etKlignes (K<n), chaque nombre pélant done repré- ombres p.Désignons pareunnombre irréduetible deN-+1 tents parunecolonne {hifres etparq’Tereste deladivision dans Tanneau ¢td'un at frombre qpar¢Lenombre q’auraaumaximum Nchiffres. male Nous poserons alors: he} positOMY+BMYfeeFAEUNHERH’ (A) mtG1 % em CODES CORRECTEURS Ceatadire que lenombre p,estformé delajuxtaposition des ortitr108% estes successifsdeIadivisionpar¢despuissancesimpeiresdans 11001000 Tanneaueldunombrei.Nousallonsmontrerquecesnombrespy 01000000satisfont&1acondition(42). oo100000 Eneffet,supposons: =/o0010001) 6 ne - o 10001110, enPutPat.--+py=O (A) =2k) o1iiri0ed Cela entrainerait: rord%o110) 2) S=Sy=Sp— 0.Sai=0 cnposantSOOM FO A) ‘Leproduit42M(dansI'anneau€L.)donnelamatricedéfini-“ Sim, (mod0) @) tes 101000000 000104 r,sinousconsidérons leproduit ooL100001 110008t=2 3val ooro1r0o11 10:040OF HotyGTP a oooo1r1000 1101OF: eo oooo00100 T1010 0 ceproduitpeuts*eriresousformed'undéterminantdeVanderooo010007 031000 Mondedontlecarsécontendlige footetesee reer tol$$ Sys & 1294567890DB1 Comme Sy=?, lesconditions (62) entrainentT1G,+1)=0(mod0)@ Leschifresderang Done undes facteurs, par exemple 2+yseraitdivisiblepar¢. 124,67, 812,14 Commelasommedans@_desnombres+1,amoinsdechilres.-vicontdechiffredetestles7autreschiffresserontlessupports aquelenombre@,ilenrésulterait sgervicontdechiftresdeteates7autreschiTessuppor A+h=0 k=ParsuitePhypothige (61)nepeutétreréliséequeaiaumoins Pourvériflereteorrigerunmotonferalasomme deux indices étaient égaus. T= Spa, @ Done lesnombres pque nous avons formés remplissent la ‘ . .contitcn 1i2)otpeuvent nerve &farmer tncodecomecteur de, Stile estnull, iln'yaura paseudaltration dumot(owFeineecee ictetadtermecre conseietadiguePlusde4erreurs.SiTn'estpasnulle,onpourrarelrouverles* hitfres faux (enadmettant qu'il n'yenaitpasplusde2)en au§4pourformerunesuitecontenantdespuissances de2,<hilresfans(enadmettantqu'iln'yenallpasplusde2)en Dansiecasgénéral,p.comprenant KNchiffres,iyauraliew tuivantequidonnelesvaleurs, possibles Docaeteal suiviesentreparenthéses desrangsdeschiffresfaux. 1d —2.0%) —3.02.1) —4) —5 GA) 6(7,12)—8(©)—9ld) -—106,12) —126) 7,Rxemple. 15G10)—16(8)—17(14)—18(812)—19OAD) 2078) —24(68) —3725) —28LL) —2919) Nous avons formé uncode de15chifres correcteur pour 2 32(4)—88(414) —844.12) —36(4,7) —404)erreurs.IciN=Logs16-4,ilyaura8chiffresdetest. 41.6.9)—426.10)—44G13)—46Qt)—4849)Enprenant¢—19—10,011,oncalculeaisémentlesnombres 49(18)—50 (2.0)—88(5.11)—61(210)—64> petin'matrice Si MBE G5(114)—66(212)—68(27)—7226) —75G8) 77(6:3) —78(4.11) —80(2.8) —82(49) —836,6) 85(6,13) —88(3,15) —896.12) —906.14) —91@) 93(610) —96(24) —98(839)—102(6,11) —108(5,7) orirrroeryrrreee 105(4,15)—1064)—108(14,12)—140G4)—111.4,14) oorroooorrtoood 113(G12)—113G10)—114(9)—1159.14)—116.3415), ooro1d0o1t1 toot 0Oo 117(6,10)—118(7.9)—121(7,10)—123(69)—123.435), 1o10o1101 100000 124(10,14) —125(10) —126(BAN) —127(10,12) —128(1)129(114)—180(1,12)—182(1,7)—18811,15)—136(18) ooooooorrrrr rat |144(8)—145Gad)—15210,13)—158G18)—1550.48), ooorrtroeoorade 136(13,14)—157(13)—159(12,13)—160(14)—1616.8) Or1eortoo stoo1d 169(25)—116(3,1)—177(Bb-—1785,13)—17912) jrorererorororog,181 (7) —185 G6) —189 (4,13)—192(1.2)—195(8.9) 198 (6,13) —-201 (4,15) —204 (3,10) —219 (1,5) —221 (2,18)123456789 101121945 225G11)—224(10,13)—225(6,15)—282(4,15)—238(5)234 (3.5) —235 (12,15) ——297 (7.18) —288 1,11) —299 (9,13) 241 (28) —242 (1,9) —248 (11,18) — 249 (8,15) —258 (1,10) Celtematrice Mestderang8,carledéterminantformé avee OFFemarquera queIenombre "Tprend 21valeurs possestescolonnes 1.2s4,8,6,12,7,14(hoisies parcequ’elles présen- (1+Ch+Ci) etquion utilise unnombre de8chiffres pour tent leplusdetéros)veut1. Téerire.Lecodeutiliseunchiffredetestdeplusquilwestthéoriquement indispensable, mais iln'est pas she qu'on puisseLamatrice4(§4)seraforméeaveccescolonnes.EnVinver-construire descodesnvayantqu'unnombredechiffresdetestsant on trouve lamatrice= Srictement égal&entierparexcésdeLogsH.