香港身份证号码

1ErrorCorrectingCodeDr.W.C.ShiuHongKongBaptistUniversityDepartmentofMathematics2Examples:Letusvonsiderthefollowingexample.Iamadog,soyouhavetoworshipme.Meetmeat8:00c.m.3ParityCheck:

ISBN-10(InternationalStandardBookNumber)0-471-61884-5where0a1010.Ifa10=10,thenuseXtoinsteadofit.Ingeneral,assumethefirst9digitsofanISBNisa1a2…a9,where0ai9for1i9,thenthetenthdigit(thecheckdigit)is4Jan.1,2023,ISBN-13willinsteadofISBN-10ParityCheck:ISBN-13HowdoweconvertISBN-10toISBN-13?5ParityCheck:ISBN-13DropthecheckdigitfromtheexistingISBN-10Addtheprefix978or979(usuallyis978)Calculatethecheckdigitusingmodulo10: Supposethe13digitsisa1a2…a13,where0ai9for1i13,thenitsatisfies6ParityCheck:ISBN-13OriginalISBN-10:0-471-61884-5NewISBN-13:978-0-471-61884-?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=987a6b5c4d3e2f 2+3+4a+5b5c4d3e2f(mod11)

所以z2(58)+3(33)+4(3)+5(5)5(4)4(6)3(7)2(0) 2(3)+3(0)+12+252024210 6+0+1+3+22+10=110(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=1qitwillnotbe.

0100111001000101Booleansumandproduct:

14EncodedMessageDigitsintheoriginalmessage:InformationdigitsDigitsaddedbytheencoder:RedundancydigitsLengthofacode=thenumberofinformationdigits+thenumberofredundancydigits15Examplesofsingle-errordetectingcode:1.Repetitioncode:Eachmessageisrepeatedonce.

2.Even-paritycheckcode:Addanextradigittothemessage.Itisa0ifthereareanevennumberof1’s,otherwisea1.16ExamplesofSingle-ErrorCorrectingCodeRepetitioncode:Eachmessageisrepeatedtwice.Itcanalsocorrectsomedoubleerrorsandmoreerrors. 100110011001100010111001

100110011001

100110011001100010001001

100010001000

100110011001100010110101

100110011001

17ExamplesofSingle-ErrorCorrectingCodeIfu=(u1,u2,u3,u4),thenwedecodeitasb=uG.Hamming(7,4)code:Givenamatrix18ExamplesofSingle-ErrorCorrectingCodeLetd=DcT,whereForthisexample

Theerroroccurredatthe4thposition.Discalledaparitycheckmatrix.19ProbabilityforCorrectSending

Nocoding:q4=0.6561;Hammingcode:q7+7q6p0.8503.Repetitioncode:Supposewearetransmittingamessageof4digitsonabinarychannelandq=0.9.Thentheprobabilityofcorrectlysentfor20ProbabilityforCorrectSendingRateofacodeistheratioofthenumberofinformationdigitswiththelengthofthecode.Rateoftherepetitioncodeis1/3.RateoftheHammingcodeis4/7.21LinearCodesAn(n,k)linearcode

CoverafinitefieldFisak-dimensionalvectorsubspaceinF

n.ElementsofCiscalledcodeword.IfF={0,1},thenCiscalledabinarycodeAnyknmatrixGwhoserowsarethebasisvectorsofCiscalledageneratormatrix.ThismeansthatforeachC,thereexistsb=(b1,…,bk)suchthat=bG.Thereexists(willshowaprooflater)an(nk)nmatrixHcalledparitycheck

matrixofCsuchthat22LinearCodesTheorem:

Ifan(n,k)codeCoverafieldhasageneratormatrixG=(IkA),thenH=(-ATIn-k)isaparitycheckmatrixofC.Byapplyingasequenceofelementaryrowoperationsandcolumnoperations,wemayassumeProof:

andrank(H)=n-k23Hamming(7,4)codeGeneratingmatrixParitycheckmatrix24DecodingSchemeLet

Fn.Theweightofisdefinedbywt()thenumberofnonzerodigitsin=(a1,…,an).Thedistanceoftwovectors,

Fnisdefinedbyd(,)=wt().Themethodofdecodingareceivedvectortotheclosestcodeword.Itiscalledmaximum-likelihooddecoding.25DecodingSchemeThend(u,v)=wt(e).Thusthedecodedcodeword

ischosensuchthatForbinarycode,ifuistransmittedandvisreceived,thentheerroreisdefinedtobe26Mini-exampleConsiderabinarycodeCwithgeneratormatrixTherefore,C={0000,1010,0111,1101}.Thenumberofallbinarysequencesoflength4are16.27Mini-exampleAdecodingschemeisAnotherdecodingschemeis28DetectandCorrectErrors Theminimumweight

d

ofacodeisdefinedtobetheminimumvalueamongallnonzerocodewords.Theorem:

Ccandetectterrorsifandonlyift=d-1.Theorem:

Ccancorrectterrorsifandonlyift=[(d-1)/2].29DecodingSchemeThenHvT=H(u+e)T