香港身份证号码

1ErrorCorrectingCodeDr.W.C.ShiuHongKongBaptistUniversityDepartmentofMathematics2Examples:Letusvonsiderthefollowingexample.Iamadog,soyouhavetoworshipme.Meetmeat8:00c.m.3),11(mod9876543211091987654321aiaaaaaaaaaaiiParityCheck:ISBN-10(InternationalStandardBookNumber)0-471-61884-5)11(mod5225498887166514734201where0a1010.Ifa10=10,thenuseXtoinsteadofit.Ingeneral,assumethefirst9digitsofanISBNisa1a2…a9,where0ai9for1i9,thenthetenthdigit(thecheckdigit)is4Jan.1,2007,ISBN-13willinsteadofISBN-10ParityCheck:ISBN-13HowdoweconvertISBN-10toISBN-13?5ParityCheck:ISBN-13DropthecheckdigitfromtheexistingISBN-10Addtheprefix978or979(usuallyis978)Calculatethecheckdigitusingmodulo10:Supposethe13digitsisa1a2…a13,where0ai9for1i13,thenitsatisfies)10(mod0)(312108642131197531aaaaaaaaaaaaa6ParityCheck:ISBN-13OriginalISBN-10:0-471-61884-5NewISBN-13:978-0-471-61884-?)10(mod6?)2(3?)32(3?30)486707(3?)811489(4?ThenewISBN-13is978-0-471-61884-47香港身份證號碼X354670(?)身份證號碼的「結構」，可以用abcdef(z)表示。「」可能是「空格」或是一個英文字母，「」則必定是英文字母。「abcdef」代表一個六位數字，而「z」是作為檢碼之用，它的可能選擇是0,1,2,...,9,A(代表10)。這些代號的背後，都可配上一個編碼值。透過編碼值，便可找出9+8+7a+6b+5c+4d+3e+2f+z的總和。該總和特別之處，是必須被11整除。利用這特點，我們便能找出括號內的數字。試試看！8或的編碼值:空格58I18R27A10J19S28B11K20T29C12L21U30D13M22V31E14N23W32F15O24X33G16P25Y34H17Q26Z359X354670(?)9(58)+8(33)+7(3)+6(5)+5(4)+4(6)+3(7)+2(0)+z=902+z被11整除，所以z=0。我們可利用Modulararithmetic來簡化運算。z=987a6b5c4d3e2f2+3+4a+5b5c4d3e2f(mod11)所以z2(58)+3(33)+4(3)+5(5)5(4)4(6)3(7)2(0)2(3)+3(0)+12+2520242106+0+1+3+22+10=110(mod11)即X354670(0)是正確的香港身分證號碼。10MessageWethinkofamessageasablockofsymbolsfromafinitealphabet.Acommonlyusedalphabetisthesetoftwosymbols0and1.Apossiblemessageis1001.Thismessageisthentransmittedoveracommunicationschannelthatissubjecttosomeamountofnoise.11NoEncoding-DecodingSystemChannelNoiseeMessageu=1001ReceivedMessagev=000112Encoding-DecodingSystemChannelNoiseeMessageu=1001E-1(Dc)=1001MessageEncoderEu=b=1001100DecoderDc=1001100ReceivedMessagec=b+e=000110013BinarySymmetricChannel(BSC)Nomemory.Receivesandtransmitstwosymbols0and1.TheBSChasthepropertythatwithprobabilityqatransmitteddigitwillreceivedcorrectly,andwithprobabilityp=1qitwillnotbe.0100111001000101Booleansumandproduct:14EncodedMessageDigitsintheoriginalmessage:InformationdigitsDigitsaddedbytheencoder:RedundancydigitsLengthofacode=thenumberofinformationdigits+thenumberofredundancydigits15Examplesofsingle-errordetectingcode:1.Repetitioncode:Eachmessageisrepeatedonce.10001001100110011001ChannelE10000100101001ChannelE2.Even-paritycheckcode:Addanextradigittothemessage.Itisa0ifthereareanevennumberof1’s,otherwisea1.16ExamplesofSingle-ErrorCorrectingCodeRepetitioncode:Eachmessageisrepeatedtwice.100101100110011001100110001001100110011010011ChannelEDEItcanalsocorrectsomedoubleerrorsandmoreerrors.10011001100110001011100110011001100110011001100110001000100110001000100010011001100110001011010110011001100117ExamplesofSingle-ErrorCorrectingCodecGE1000100)1001100()1001(1001ChannelIfu=(u1,u2,u3,u4),thenwedecodeitasb=uG.1111000011010010100101100001GHamming(7,4)code:Givenamatrix18ExamplesofSingle-ErrorCorrectingCodeLetd=DcT,where101010111001101111000DForthisexampleTd)001(Theerroroccurredatthe4thposition.Discalledaparitycheckmatrix.19ProbabilityforCorrectSendingNocoding:q4=0.6561;Hammingcode:q7+7q6p0.8503.;8926.0!436912!36912!29121248392101112pqpqpqpqqRepetitioncode:Supposewearetransmittingamessageof4digitsonabinarychannelandq=0.9.Thentheprobabilityofcorrectlysentfor20ProbabilityforCorrectSendingRateofacodeistheratioofthenumberofinformationdigitswiththelengthofthecode.Rateoftherepetitioncodeis1/3.RateoftheHammingcodeis4/7.21LinearCodes}0|{TnHFCAn(n,k)linearcodeCoverafinitefieldFisak-dimensionalvectorsubspaceinFn.ElementsofCiscalledcodeword.IfF={0,1},thenCiscalledabinarycodeAnyknmatrixGwhoserowsarethebasisvectorsofCiscalledageneratormatrix.ThismeansthatforeachC,thereexistsb=(b1,…,bk)suchthat=bG.Thereexists(willshowaprooflater)an(nk)nmatrixHcalledparitycheckmatrixofCsuchthat22LinearCodesTheorem:Ifan(n,k)codeCoverafieldhasageneratormatrixG=(IkA),thenH=(-ATIn-k)isaparitycheckmatrixofC.Byapplyingasequenceofelementaryrowoperationsandcolumnoperations,wemayassume)(AIGkProof:OHGTandrank(H)=n-k,)(TTTxHGxGH23Hamming(7,4)code1111000011010010100101100001GGeneratingmatrix101010111001101111000D100101101011010011110HParitycheckmatrix24DecodingSchemeLetFn.Theweightofisdefinedbywt()thenumberofnonzerodigitsin=(a1,…,an).Thedistanceoftwovectors,Fnisdefinedbyd(,)=wt().Themethodofdecodingareceivedvectortotheclosestcodeword.Itiscalledmaximum-likelihooddecoding.25DecodingSchemeThend(u,v)=wt(e).Thusthedecodedcodewordischosensuchthat}.|)(wtmin{)(wtCveeeveuuvuvForbinarycode,ifuistransmittedandvisreceived,thentheerroreisdefinedtobe26Mini-example11100101ConsiderabinarycodeCwithgenera