4.pdf

(117 KB) Pobierz
302997660 UNPDF
W4, Baryła Justyna, 28.10.2009
Def.ElementempierwotnymciałaGF(q)(q=p m , gdziepto liczba
pierwsza) nazywamy elementarz¦duq1, tzn. elementa2GF(q)taki,
»ea;a 2 ;:::;a q1 to parami ró»ne elementy(6=0). Wtedyageneruje grup¦
multyplikatywn¡ ciałaGF(q).
Przykład. Elementk2Z p (=GF(p))jest pierwotny , NWD(k;p)=1
(czylik;ps¡ wzgl¦dnie pierwsze).
Kod liniowyCdługo±cinnad ciałemK(=GF(q))jest podprzestrzeni¡
liniow¡ w(K
n . DlaK=GF(2)kodCjest zamkni¦ty ze
wzgl¦du na dodawanie.
n kodemgenerowanymprzezS
jestC:=hSi=lin(S), czyli liniowa powłoka zbioruS. Dla ciała binarnego
Ks¡ to po prostu sumy elementów zbioruS.
Zalety kodu liniowego:
1. Istnieje prosta i szybka procedura dekodowania według najwi¦kszej
wiarogodno±ci (MLD – maximum likelihood decoding),
2. Kodowanie jest szybkie (u7!v2C),
3. Łatwo okre±la si¦ wektory bł¦dów wykrywane przez kodC,
4. Łatwo okre±la si¦ wektory bł¦dów korygowane przez kodC.
Przykład. Mamy kodC=f00000;11100;00111;11011g o długo±cin=5.
CzyCjest kodem liniowym?
Poniewa»Cjest kodem binarnym, wi¦c wystarczy tylko sprawdzi¢, »e
zbiórCjest zamkni¦ty ze wzgl¦du na dodawanie:
11100+00111=11011
11100+11011=00111
00111+11011=11100
11100+00111+11011=00000
Gdyby istniała suma słów zCnie nale»¡ca doC, to kod nie byłby liniowy.
1
n ;+;K;),CK
Def. Dla dowolnego podzbioruSK
n
ortogonalnych do ka»dego elementu zS. Mo»na łatwo udowodni¢, »eS ?
jest podprzestrzeni¡ liniow¡, a zatem jest kodem liniowym zwanymkodem
dualnymdo kodu hSi generowanego przez zbiórS.
n symbolemS ? oznaczamy zbiór wszystkich słów zK
Przykład. Dany jest kodS={0100, 0101},K=GF(2), a wtedy 1=1.
Obliczy¢S ? . (KodSnie jest kodem liniowym, poniewa»
0100+0100=0000nie nale»y do kodu):
Znajdujemy wszystkie słowav=(x;y;z;t)=xyzt(4 niewiadome, poniewa»
n=4) takie, »ev?S, tzn. zeruj¡ si¦ odpowiednie iloczyny skalarne:
v0100=y=0
v0101=y+t=0
, y=t=0
ZatemS ? =f0000;0010;1010;1000g.
KodS ? jest liniowy, gdy» jest zamkni¦ty ze wzgl¦du na dodawanie. Kod
S ? jest dualny do kodu liniowego hSi, a zatem niekoniecznie doS.
LINIOWANIEZALENOZBIORUS
Def. ZbiórSnazywa si¦liniowoniezale»nym, gdy z zerowania si¦ dowol-
nej kombinacji liniowej elementów zSwynika zerowanie si¦ współczynników
kombinacji.
Kryteriumliniowejzale»no±cizbioruS. ZbiórSjest liniowo zale»ny,
gdy jSj=1iS=f00:::0g=f0g lub jeden z elementów wSjest kombinacj¡
liniow¡ pozostałych elementów zS.
Wniosek. Je±li element zerowy02S, to zbiórSjest liniowo zale»ny.
METODAELEMENTARNYCHPRZEKSZTAŁCE
WIERSZOWYCH
Zadanie: znajd¹ rz¡d macierzy. Je±li rz¡d jest równy liczbie wierszy tej
macierzy, to wtedy wiersze s¡ liniowo niezale»ne. Rz¡d znajdujemy metod¡
przekształce« elementarnych wierszy. przekształcenia te nie zmieniaj¡ bowiem
2
Def. DlaSK
x;zdowolne:
302997660.001.png
rz¦du macierzy.
Przykład. Znajd¹ rang¦ (rz¡d) danego zbioruSwektorów (słów) oraz maksy-
malny podzbiór wSliniowo niezale»ny. NiechS=f110;011;101;111g.
Poniewa» szukamy podzbioru liniowo niezale»nego, wi¦c od zbioruSprze-
chodzimy do macierzyA T , bior¡c elementy zSjako kolumny tej macierzy.
2
1011
1101
0111
3
S7!A T =
4
5 7! WPS(A T );
tzn. przekształcamy macierzA T do wierszowej postaci schodkowej (WPS)
(ang.: REF – row echelon form):
2
1011
1101
0111
3
2
1011
0110
0111
3
2
1011
0110
0001
3
4
5 +w 1 7!
4
5 w 3 +w 2
!
4
5 =WPS(A T ):
Otrzymali±my (niezredukowan¡) WPS(A T ). Kolumny „przewodnikowe” maj¡
numery 1,2,4, tzn. przewodniki wierszy niezerowych znajduj¡ si¦ w tych
kolumnach. Zatem elementy zSo numerach 1,2,4 tworz¡ maksymalny
podzbiór liniowo niezale»ny. Rz¡d zbioruSjest równy 3. Podzbiorem tym
jest f110;011;111g.
Uwaga 1. Powy»sza metoda daje baz¦ kodu hSi generowanego przezSi
to baz¦ b¦d¡c¡ podzbiorem wS.
Uwaga 2. Baz¦ w hSi mo»na te» znale¹¢ przechodz¡c odSdo macierzy
A, której wierszami s¡ wszystkie elementy zS. Znajdujemy wtedy WPS(A),
gdzie wiersze niezerowe to szukana baza.
ROZSZERZENIEDANEGOPODZBIORULIN.
NIEZALENEGODOBAZYPRZESTRZENILINIOWEJ
Przykład. ZbiórS=f110;001g, gdzien=3, jest liniowo niezale»ny, bo dla
a;b2K, je±lia(110)+b(001)=0, toa=0ib=0. Jak zbiórSuzupełni¢
do bazy wK 3 ?
Do zbioruSdoł¡czamy baz¦ standardow¡ w przestrzeniK
n , otrzymuj¡c
110, 001, 100, 010, 001,
3
Sprawdzamy czy pierwszy element z bazy jest kombinacj¡ liniow¡ poprzedza-
j¡cych go elementów. Je±li nie jest – zostawiamy, je±li jest tak – usuwamy.
Post¦pujemy tak z nast¦pnymi elementami a» do uzyskanianelementów
bazowych.
Aby unikn¡¢ tego sprawdzania, od powi¦kszonego zbioru przechodzimy do
2
110
001
100
010
001
3
2
110
001
010
010
001
3
A=
4
5
+w 1 7!
4
5
gdzie pierwsze trzy wiersze tworz¡ baz¦ (bo ich przewodniki s¡ w ró»nych
kolumnach).
Def.Baz¡nazywamy podzbiór liniowo niezale»ny, który rozpina cał¡ prze-
strze«.
Oznacza to, »e dowolny wektor ma by¢ kombinacj¡ liniow¡ wektorów
bazowych. Nadto ró»ne kombinacje liniowe, czyli z innym układem współczyn-
ników, okre±laj¡ ró»ne wektory.
Kod liniowy wymiaruknad ciałemGF(q)maq k elementów. Mamy bowiem
kwektorów bazowych w kodzie i współczynniki mo»emy przydzieli¢ naq k
sposobów, a zatem tyle» mamy ró»nych elementów. W kodzie binarnym o
wymiarzekjest wi¦c2 k słów kodowych.
Twierdzenie.
dimC+dimC ? =n(wspólna długo±¢ tych kodów).
W algebrze liniowej twierdzeniem analogicznym jest
wymiar j¡dra + wymiar obrazu = wymiar dziedziny.
4

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin