codes.pdf

(91 KB) Pobierz
34364654 UNPDF
kilkasl0 ´ owokodach
KodCnazywamykodemliniowym, jesli dla kazdych dwoch slow kodowych ich
suma jest slowem kodowym, tj.
8a,b2Ca+b2C.
Ex.
KodC 1 ={000,111}jest kodem liniowym, bo kazda z czterech sum
000 + 000 = 000, 111 + 000 = 111
000 + 111 = 111, 111 + 111 = 000
nalezy doC 1 .
KodC 2 ={000,001,101}nie jest liniowy, bo np. 0012C 2 ,1012C 2 , ale 001+101 =
100 62C 2 .
obserwacja
Liniowy kod musi zawierac zero, gdyz jesliv2C, tov+vtez musi nalezec doC,
skoro jest liniowy. Ale wyst , epowanie slowa zerowego w kodzie nie gwarantuje jego
liniowosci.
Przewag , a kodow liniowych nad nieliniowymi jest np. to, ze latwiej znajduje si , e
odleglosci kodow, mianowicie
Twierdzenie1 Odleglosc kodu liniowego rowna si , e najmniejszej z wag Hamminga
slow niezerowych.
W przypadku kodow liniowych latwiej rozwi , azuje si , e zazwyczj zmudne problemy
ogolne, np:
•latwiej opisac zbior wzorcow bl , edow, ktore kod liniowy b , edzie wykrywal/korygowal
•dekodowanie kodow liniowych jest szybsze i zajmuje mniej miejsca niz w przypadku
dowolnych, kodow nieliniowych.
Narz , edzia do studiowania kodow liniowych pochodz , a z algebry liniowej, :(, np. li-
niowa niezaleznosc wektorow, przestrzen, podprzestrzen liniowa...
Niecha=a 1 a 2 ...a n ,b=b 1 b 2 ...b n 2 Z
n 2 . Iloczyn”skalarny”w Z
n 2 dany jest
wzorem
a·b=a 1 b 1 +a 2 b 2 +...+a n b n .
Przykladowo w Z
5 2 mamy
11001·01101 = 1·0 + 1·1 + 0·1 + 0·0 + 1·1
= 0 + 1 + 0 + 0 + 1
= 0.
Dzialania wykonujemy modulo 2.
Uwaga!.Waz . nauwaga. W j , ezyku angielskim wyst , epuje poj , ecie dot product. Dot
product dwoch wektorowu= (u 1 ,u 2 ,...,u n ) iv= (v 1 ,v 2 ,...,v n ) jest zdefiniowany
wzorem (takim jak wyzej)
u·v=u 1 v 1 +u 2 v 2 +...+u n v n .
1
Innym poj , eciem wyst , epuj , acym w angloj , ezycznej literaturze jest inner product. To
oznacza iloczyn skalarny. W niektorych przypadkach, np. dla rzeczywistych prze-
strzeni wektorowych, dot product jest przykladem inner product. Ale problem
wyst , epuje np. z Z
2 moze si , e zdarzyc, ze
wektor jest prostopadly do siebie (np. wektor (1,1)).
NiechCb , edzie kodem liniowym. Dopelnienie ortogonalneC ? nazywamykodem
dualnymdoC.C ? to dopelnienie ortogonalne przestrzeni liniowejC, w kontekscie
iloczynu ”skalarnego”, czyli dot product.
Przypomnienie
Wektorya,bnazywamyortogonalnymijeslia·b= 0. W powyzszym przykladzie
11001 i 01101 s , a wektorami ortogonalnymi w Z
2 . Mozna tez mowic o ortogonalnosci
wektora do zbioruS; tj.xjest ortogonalny do zbioruS, jesli jest ortogonalny
do kazdego wektora zS. Zbior taki oznaczamyS ? . NiechVb , edzie przestrzeni , a
liniow , a rozpi , et , a nad cialem Z 2 . JesliSjest dowolnym podzbioremV, toS ? jest
podprzestzreni , a liniow , a przestrzeniV. Mamy zatem
5
S ? ={x2V:8y2Sx·y= 0}
Ex.
NiechC= span{0100,0101}={0100,0101,0001,000}. ZnalezcC ? .
Szukamy slowapostacixyzw(wektorow z Z
xyzw·0100 = 0 =)y= 0
xyzw·0101 = 0 =)y+w= 0,
czyliy=w= 0. Pami , etamy, zex,z2{0,1}, zatem
C ? ={0000,0010,1000,1010}.
macierzgeneruj , acakodliniowy
NiechCb , edzie kodem liniowym o dlugoscini wymiarzek. Macierz , a generuj , ac , a
kodCnazywamy macierz, ktorej wiersze tworz , a baz , eC.
Gjest macierz , a wymiaruk×n(t.ze rz(G) =k).
Twierdzenie2MacierzGjest macierz , a generuj , ac , a kodCi wierszeGs , a liniowo
niezalezne (tj. i rz(G) =k).
Nie ma mowy o niczym innym tylko o liniowej niezaleznosci. Zatem szukaj , ac macie-
rzy generuj , acej wystarczy wskazac wiersze liniowo niezalezne, a to przywodzi nam
na mysl operacje elementarne na wierszach:
•zamiana miejscami dwoch wierszy
•dodanie (wielokrotnosci=1, bo to Z 2 ) innego wiersza
2
n 2 . Wlasciwie ten dot product spelnia wszystkie aksjomaty in-
ner product o p r o c z dodatniej okreslonosci. Wlasnie w Z
n
4 2 ) takich, ze
a·0100 = 0
a·0101 = 0
Ex.
Szukamy macierzy generuj , acej koduC={0000,1110,0111,1001}
2
0 0 0 0
1 1 1 0
0 1 1 1
1 0 0 1
3
2
1 1 1 0
0 0 0 0
0 1 1 1
0 1 1 1
3
2
1 1 1 0
0 1 1 1
0 0 0 0
0 0 0 0
3
A=
6 6 4
7 7 5
−!
w 4 +w 2
6 6 4
7 7 5
−!
w 3 +w 4
6 6 4
7 7 5 .
Zatem macierz generuj , aca, to
1 1 1 0
0 1 1 1
G=
,
ale tez macierz
1 0 0 1
0 1 1 1
G 1 =
.
?Dlaczego macierz generuj , aca
NiechCb , edzie kodem liniowym o dlugoscini wymiarzeki niechGb , edzie macierz , a
generuj , ac , a kodC. Ponadto, niechu- slowo o dlugoscik(zapisane jako wektor
wierszowy). Wtedyv=uGjest slowem zC, poniewazvjest liniow , a kombinacj , a
wierszy zG, ktore tworz , a baz , eC. Istotnie tak jest, bo jesliu= (a 1 ,a 2 ,...,a k ) i
jesli
2
3
g 1
g 2
.
g k
G=
6 6 6 4
7 7 7 5
,
gdzieg 1 ,g 2 ,...,g k s , a wierszami macierzyG, to wtedy
v=uG=a 1 g 1 +a 2 g 2 +...+a k g k .
Z drugiej strony, kazde slowovzCjest liniow , a kombinacj , a slow kodowych (wier-
szy macierzyG), zatemv=uG, dla pewnychu2 Z
k 2 . Nawet wi , ecej, gdyz
jesliu 1 G=u 2 G, tou 1 =u 2 ,
poniewaz kazde slowo zCjest jednoznacznie przedstawione jako kombinacja liniowa
slow z bazy, wi , ec zadne inne slowov=uGnie jest tworzone przez wi , ecej niz jedno
slowouzC.
macierzparzysto´scikoduliniowego
MacierzHnazywamy macierz , a parzystosci kodu liniowegoCjesli kolumny macierzy
Htworz , a baz , e kodu dualnegoC ? .
JesliCjest kodem liniowym o parametrach (n,k) (jego macierz generuj , aca ma
wymiark×n), to macierz parzystosciHjest wymiarun×(n−k) i rzH=n−k.
Jest to konsekwencja tego, ze dimC+ dimC ? =n.
Twierdzenie3MacierzHjest macierz , a parzystosci kodu liniowegoCi kolumny
macierzyHs , a liniowo niezalezne.
Opis kodu w terminach jej macierzy parzystosci daje nast , epuj , ace
3
w 1 $w 2
w 2 $w 4
Twierdzenie4jesliHjest macierz , a parzystosci kodu liniowego o dlugoscin, to
Csklada si , e dokladnie z tych wszystkich slowv2 Z
n 2 , dla ktorychvH= 0.
Jesli mamy macierz generuj , ac , a kod liniowyC, to mozemy znalezc macierz parzy-
stosci. W ponizszych przeksztalceniach dozwolonymi operacjami na macierzy s , a
operacje elementarne na wierszach.
Jedynkawiod , aca(leading 1) macierzy, to taka 1, ze w tym samym wierszu, na
lewo od niej nie ma innych jedynek.Kolumnawiod , acamacierzy to kolumna,
ktora zawiera jedynk , e wiod , ac , a. Mowimy, ze macierzMjest w postaciREF(row
echelon form), jesli
•wiersze zerowe, jesli s , a, s , a na ”dole”macierzy, czyli na ostatnich wierszach
•w kazdym wierszu, kazda jedynka wiod , aca jest na prawo od jedynki wiod , acej w
wierszu wyzszym (o nizszym numerze).
Ponadto, jesli kazda kolumna wiod , aca zawiera dokladnie jedn , a jedynk , e mowimy, ze
Mjest w postaciRREF(reduced row echelon form).
Kazd , a macierz mozna przedstawic w postaciREF(niejednoznacznie) lubRREF
(jednoznacznie).
Ex.
ta macierz # jest w postaciREF
2
1 0 1 1
1 0 1 0
1 1 0 1
3
2
1 0 1 1
0 0 0 1
0 1 1 0
3
2
1 0 1 1
0 1 1 0
0 0 0 1
3
2
1 0 1 0
0 1 1 0
0 0 0 1
3
M=
4
5 w 2 +w 1
−!
w 3 +w 1
4
5 w 2 $w 1
−!
4
5 w 1 +w 3
−!
4
5
w postaciRREFjest ta -
algorytmszukaniabazykodudualnego
Dany jest zbiorS. Tworzymy kod liniowyC= span(S)
1 budujemy macierzA, ktorej wierszami s , a slowa zS(mog , a byc liniowo zalezne)
2 przeksztalcamy macierzAdo postaciREF(otrzymujemyAREF)
3 macierz generuj , acaG k×n powstaje zAREFprzez wykreslenie wierszy zerowych
4 tworzymy macierzX k×(n−k) zGprzez usuni , ecie kolumn wiod , acych z macierzyG
5 macierzH n×(n−k) tworzymy nast , epuj , aco:
(i) w wierszachHodpowiadaj , acych nr kolumn wiod , acychGkladziemy wiersze ma-
cierzyX (ii) pozostalen−kwierszyHuzupelniamy wierszami macierzy iden-
tycznosciowej (n−k)×(n−k)
Kolumny macierzyHtworz , a baz , eC ? .
Ex. 1
Mamy macierz generuj , ac , aG, wymiaru 4×7 w postaciREF
2
3
1 0 1 0 0 1 0
0 0 0 1 0 1 0
0 0 0 0 1 0 0
0 0 0 0 0 0 1
G=
6 6 4
7 7 5
Macierz parzystosciHb , edzie wymiaru 7×(7−4), czyli 7×3. Kolumnami wiod , acymi
macierzyGs , a kolumny o numerach: 1,4,5,7.
I sposob.
4
Wykreslamy kolumny wiod , ace macierzyG. MacierzXma postac
2
3
0 1 1
0 0 1
0 0 0
0 0 0
X=
6 6 4
7 7 5
Wiersze macierzyXwpisujemy w macierzHna pozycje wierszy o numerach kolumn
wiod , acych (w kolorze Cyan ):
2
0 1 1
...
...
0 0 1
0 0 0
...
0 0 0
3
1
2
3
4
5
6
7
H=
6 6 6 6 6 6 6 6 4
7 7 7 7 7 7 7 7 5
Uzupelniamy j , a wierszami macierzy identycznosciowej stopnia 3. OstatecznieHma
postac
2
0 1 1
100
010
0 0 1
0 0 0
001
0 0 0
3
H=
6 6 6 6 6 6 6 6 4
7 7 7 7 7 7 7 7 5
II sposob. Permutujemy (przestawiamy) kolumny macierzyGtak, aby otrzymac z
lewej strony macierz identycznociow , a (utworz , a j , a kolumny wiod , ace). Nowo powstala
macierzG 0 wygl , ada tak:
2
3
1 0 0 0 0 1 1
0 1 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 1 0 0 0
G=
6 6 4
7 7 5
1 4 5 7 2 3 6
Pod macierz , a pozostawiono star , anumeracj , e kolumn (sprzed permutacji).
MacierzXto ta cz , esc macierzyG 0 , ktora nie tworzy macierzy jednostkowej. To ta
sama macierzX, ktor , a mielismy poprzednio. Tworzymy macierzH 0 : wpisujemy
macierzXi uzupelniamy macierz , a jednostkow , a stopnia 3:
2
3
0 1 1
0 0 1
0 0 0
0 0 0
100
010
001
1
4
5
7
2
3
6
H 0 =
6 6 6 6 6 6 6 6 4
7 7 7 7 7 7 7 7 5
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin