Binary_Error_Correcting_Codes-ln.pdf
(
158 KB
)
Pobierz
584788540 UNPDF
BinaryErrorCorrectingCodes
1BasicconceptsofErrorcorrectingCodes
Incommunicationsystem,werepresentaninformationasasequenceof0
an1(binaryform).Foraconvenience,letB={0,1}.Thenwedefine
B
2
,B
3
,...,B
n
asfollows:
B
2
={00,01,10,11},
B
3
={000,001,010,100,011,101,110,11},
.
.
.
B
n
={b
1
b
2
...b
n
|b
i
2B}
Asymbolb
1
b
2
...b
n
2B
n
iscalledaword.Wealwaysdenote0and1for
00...0and11...1,respectively.
Wedefinebinaryoperations+,·:B×B!Basfollows:
+01
·01
001
000
110
101
Clearly,(B,+)isanabeliangroup.
Exercise1.1.Letb
1
b
2
...b
n
,c
1
c
2
...c
n
2B
n
andforeachi=1,2,...,n,let
d
i
=b
i
+c
i
asabovetable.Defineabinaryoperation+:B
n
×B
n
!B
n
by
(b
1
b
2
...b
n
,c
1
c
2
...c
n
)7!d
1
d
2
...d
n
.
1
i)verifythat(B
n
,+)isanabeliangroup,
ii)foreachb
1
b
2
...b
n
2B
n
,determineitsinverse.
Thefollowingdiagramprovidesaroughideaofgeneralinformationtrans-
mittedsystem.
Noise
e
Messageword
Codeword Recievedword
Messageword
Encoding
-
Transmission
-
Decoding
w E(w) r D(r)
Fig.1:Thecommunicationchannel
Fromabovefigure,wegiveconceptsofabinary(n,m)codeasfollows:
Definition1.1.Letk,n2
N
besuchthatm<n.Abinary(n,m)code(or
code)composeof:
1.aninjectivefunctionE:B
m
!B
n
,calledanencodingfunction,
2.afunctionD:B
n
!B
m
suchthatD(E(w))=wforallw2B
m
,
calledadecodingfunction.
WecallasetMB
m
asetofmassage,w2Mamessageword,C:=E(M)
acode,c2Cacodeword,r2Dom(D)areceivedword.
2
-
Ingeneral,M6=B
m
.WLOG,weassumeforaconveniencethatM=B
m
.
ThenacodeC:=E(M)=E(B
m
)and|C|=2
m
.
Definition1.2.LetCB
n
beacodeandc2C.Ifawordrisreceived
(fromc)ande2B
n
issuchthatr=c+e,wecalleanerror(orerror
pattern).
Example1.1(Evenparity-checkcode).Wedefine
E:B
m
!B
m+1
byb
1
b
2
...b
m
7!b
1
b
2
...b
m
b
m+1
where
8
>
<
0ifthenumberof1s
0
inb
1
b
2
...b
m
iseven
b
m+1
=
>
:
1ifthenumberof1s
0
inb
1
b
2
...b
m
isodd
and
D:B
m+1
!B
m
by
8
>
<
b
1
b
2
...b
m
ifthenumberof1s
0
inb
1
b
2
...b
m
iseven
b
1
b
2
...b
m
b
m+1
7!
>
:
00...0 ifthenumberof1s
0
inb
1
b
2
...b
m
isodd
Thenevenparity-checkcodeisan(m+1,m)code.
Forexample,B
3
isencodedasfollow:
messageword000001010100011101110111
codeword 00000011 0110
3
Thefollowingreceivedwordsaredecodedasinthetable:
receivedword111001010110000110101101
messageword000 101
Example1.2(Triple-repetitioncode).Triple-repetitioncodeis(3m,m)
codesuchthatanencodingfunction
E:B
m
!B
3m
isdefinedby
b
1
b
2
...b
m
7!b
1
b
2
...b
m
b
1
b
2
...b
m
b
1
b
2
...b
m
andadecodingfunction
D:B
3m
!B
m
isdefinedby
x
1
x
2
...x
m
y
1
y
2
...y
m
z
1
z
2
...z
m
7!b
1
b
2
...b
m
where
8
>
<
0if0occursinx
i
y
i
z
i
atleasttwice
b
i
7!
>
:
1 if1occursinx
i
y
i
z
i
atleasttwice
4
Forexample,B
3
isencodedasfollow:
message 000 001 010 100 011 101 110 111
codeword000000000 010010010
Thefollowingreceivedwordsaredecodedasinthetable:
receivedword101101101010111110011101110001101001111000,101
messageword 101
Moreover,n−repetitioncodeisdefinedsimilarly.
NearestNeighborDecoding:ForacodeC,ifawordrisreceived,itis
decodedasthecodewordinCclosesttoit.
CompleteNearestNeighborDecoding:Ifmorethanonecandidateappears,
choosearbitrarily.
IncompleteNearestNeighborDecoding:Ifmorethanonecandidateappears,
requestaretransmission.
Tomeasureadistancebetweenanytwocodewords,weintroducethe
Hammingdistanceasfollow:
Definition1.3.Letu=u
1
u
2
...u
n
,v=v
1
v
2
...v
n
2B
n
.Thedistance
d(u,v)ofuandvisdefinedby
d(u,v)=|{i2{1,2,...,n}|u
i
6=u
i
}|.
Theweightw(u)ofuisdefinedby
w(u)=|{i2{1,2,...,n}|u
i
6=0}|
5
Plik z chomika:
Kuya
Inne pliki z tego folderu:
Advanced_Complexity_Theory-Sudan.pdf
(1379 KB)
Binary_Error_Correcting_Codes-ln.pdf
(158 KB)
Computation_Complexity-Lovasz.pdf
(976 KB)
Computational_Complexity_A_Modern_Approach-Arora-Barak.pdf
(4146 KB)
Elementary_Recursion_Theory_and_its_Applications_to_Formal_Systems-Kripke.pdf
(694 KB)
Inne foldery tego chomika:
algebra
analysis
calculus
complex
discrete
Zgłoś jeśli
naruszono regulamin