Teoria informacji i kodowanie
Algebra liniowa
dr Robert Borowiec
Politechnika Wrocławska
Katedra Telekomunikacji i Teleinfomatyki
pokój 909, C-5
tel. [phone]
e-mail: [e-mail]
www: https://kursy.pwr.wroc.pl/
Slajd 2/40
Arytmetyka modularna
Kongruencja jest to przystawanie liczb a i b
według modułu m (modulo m) i jest
zapisywana w postaci:
a ºð b (mod m) lub a ºðm b,
gdy m|(a-b)
Liczba a przystaje do b wtedy, gdy m dzieli
bez reszty a-b
© Robert Borowiec
Slajd 3/40
Dzielenie z resztÄ…  operator modulo
5ØNÜ 5ØZÜ5Ø\Ü5ØQÜ 5ØZÜ = 5ØOÜ
5ØNÜ 5ØOÜ
= 5ØXÜ +
5ØZÜ 5ØZÜ
b  niepodzielna część dzielenia (reszta)
k  część całkowita dzielenia
5ØNÜ = 5ØXÜ " 5ØZÜ + 5ØOÜ
© Robert Borowiec
Slajd 4/40
Elementy algebry
" Pojęcia podstawowe
 grupa, pierścień, ciało
 arytmetyka modularna
 funkcja Eulera
" Przestrzenie wektorowe
 wielomiany pierwotne
 wielomiany minimalne
© Robert Borowiec
Slajd 5/40
Grupa
Grupa Q jest zbiorem elementów, w którym
jest określone pewne jednowartościowe
dwuargumentowe działanie, umownie zwane
dodawaniem "+", oraz są spełnione cztery
aksjomaty dla dowolnych a, b, cÎð Q:
© Robert Borowiec
Slajd 6/40
Grupa-aksjomaty
1) suma dowolnych elementów jest elementem grupy (zamkniętość):
a + b Îð Q; (1a)
2) wynik sumowania nie zależy od kolejności składników sumy
(łączność):
a + (b + c) = (a + b) + c; (1b)
3) istnieje element neutralny e (prawo identyczności):
a + e = e + a = a, e Îð Q; (1c)
4) istnieją elementy odwrotne (prawo odwrotności):
a + ć = e a Îð Q. (1d)
© Robert Borowiec
Slajd 7/40
Grupa cd..
Przykład 1: Zbiór wszystkich liczb rzeczywistych (łącznie z
zerem) stanowi grupę względem operacji zwyczajnego dodawania.
Przykład 2: Zbiór wszystkich liczb rzeczywistych z wyłączeniem
zera stanowi grupę względem operacji zwyczajnego mnożenia.
Grupa jest grupą przemienną lub abelową, jeśli zachodzi równość
a + b = b + a. (2)
Przykład grupy nieprzemiennej: zbiór macierzy stopnia n, których
wyrazami sÄ… dowolne liczby rzeczywiste, jest grupÄ… nieprzemiennÄ…
względem operacji mnożenia macierzowego.
© Robert Borowiec
Slajd 8/40
Pierścień
Pierścień R jest zbiorem elementów, dla
których są zdefiniowane dwa działania:
a + b - zwane umownie dodawaniem oraz
a·b - zwane umownie mnożeniem,
przy czym a, b są elementami R. Zbiór R jest
pierścieniem, jeśli są spełnione następujące
aksjomaty:
© Robert Borowiec
Slajd 9/40
Pierścień-aksjomaty
1) zbiór R jest grupą abelową ze względu na dodawanie
a + b = b + a; (3a)
2) zbiór R jest zamknięty ze względu na operację mnożenia
a·b Îð R; (3b)
3) mnożenie jest Å‚Ä…czne, to znaczy dla dowolnych a, b, c Îð R zachodzi
a ·(b · c) = (a · b) · c; (3c)
4) obowiązuje prawo rozdzielności dodawania względem mnożenia, to
znaczy
a· (b + c) = a · b + a · c. (3d)
© Robert Borowiec
Slajd 10/40
Pierścień-przykład
Zbiór liczb stanowiących klasy reszt modulo dowolna liczba
całkowita m jest pierścieniem względem operacji dodawania
modulo m i operacji mnożenia modulo m. Dla m = 4 reguły
dodawania i mnożenia są następujące:
+ 0 1 2 3 " 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 0 1 2 3
1 1 2 3 0
2 0 2 0 2
2 2 3 0 1
3 0 3 2 1
3 3 0 1 2
© Robert Borowiec
Slajd 11/40
Ciało
Ciało C jest to pierścień przemienny, w którym
istnieje element neutralny względem mnożenia ,
spełniający prawo identyczności
(4a)
µ Îð C , a ×ð µ =ð µ ×ð a =ð a,
a każdy a`"0 ma niezerowy element ma swój element
odwrotny względem mnożenia
a-ð1 Îð C, a ×ð a-ð1 =ð a-ð1 ×ð a =ð eð .
Przykładem ciała jest zbiór wszystkich liczb
rzeczywistych.
© Robert Borowiec
Slajd 12/40
Definicja -ciała skończonego
Niech q oznacza liczbę elementów ciała.
JeÅ›li qÄ…ðÄ„ð , to takie ciaÅ‚o nazywamy ciaÅ‚em
skończonym lub ciałem Galoisa i oznaczamy
symbolem CG(q). Wielkość q jest nazywana
rzędem ciała.
© Robert Borowiec
Slajd 13/40
Ciało skończone cd..
" Podstawowe ciało Galoisa-ciało proste
üðq=p, gdzie p jest liczbÄ… pierwszÄ…
üðjest zbiorem wszystkich elementów caÅ‚kowitych
od 0 do p-1
üðoperacje +, " , sÄ… operacjami modulo p
ððSºð a + b (mod p)
ððPºð a · b (mod p)
" Rozszerzone ciało Galoisa
üðq=pm, gdzie p jest liczbÄ… pierwszÄ…, a m jest liczbÄ…
naturalnÄ…
© Robert Borowiec
Slajd 14/40
Przykład ciała - CG(5)
" elementy: {0,1,2,3,4}
" operacje dodawania i mnożenia modulo 5
+ 0 1 2 3 4 " 0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
2 2 3 4 0 1 2 0 2 4 1 3
3 3 4 0 1 2 3 0 3 1 4 2
4 4 0 1 2 3 4 0 4 3 2 1
© Robert Borowiec
Slajd 15/40
CG(5) Elementy odwrotne i przeciwne
" Elementy przeciwne względem siebie w
ciele, to takie, które sumują się do zera,
(patrz tabelka dodawania CG(5)).
" Elementy odwrotne względem siebie w
ciele, to takie, których iloczyn wynosi 1,
(patrz tabelka mnożenia CG(5)).
© Robert Borowiec
Slajd 16/40
Elementy odwrotne i przeciwne w CG(5)
Element Element przeciwny Element odwrotny
a -a a-1
0 a Îð R CG(5) a Îð R CG(5)
0 0 0 Brak brak
1 -1 4 1 1
1
2 -2 3 3
2
1
3 -3 2 2
3
1
4 -4 1 4
4
a Îð R - przykÅ‚adowe odniesienie do ciaÅ‚a liczb rzeczywistych
© Robert Borowiec
Slajd 17/40
CG(5) - cd..
" Ciało CG(5) zawiera:
 element neutralny wobec dodawania  0;
 element neutralny wobec mnożenia  1.
" Każdy element ciała  oprócz zera  zawiera:
 element odwrotny wobec dodawania
 element odwrotny wobec mnożenia
" Przykład działań z wykorzystaniem elementu
odwrotnego
 odejmowanie 2-3=2+(-3)=2+2=4
 dzielenie 2/3=2·3-1=2·2=4
© Robert Borowiec
Slajd 18/40
Przykład ciała prostego- CG(2)
" Tablice dodawania i mnożenia
0  element neutralny
+ 0 1 " 0 1
względem dodawania
0 0 1 0 0 0
1  element neutralny
1 1 0 1 0 1
względem mnożenia
Dodawanie i odejmowanie w GF(2), a także mnożenie i
dzielenie są sobie równoważne, ponieważ odpowiednio
1+1=0 Þð 1=-1, 1·1-1=1 Þð 1=1-1.
1-jest elementem przeciwnym oraz odwrotnym w CG(2)
© Robert Borowiec
Slajd 19/40
Wyznaczani elementów przeciwnych i
odwrotnych
" Elementy przeciwne i odwrotne w ciałach
skończonych można wyznaczyć z tabelek
" Elementy przeciwne można również
wyznaczyć z prostego równania
a =ð p -ð a
" Elementy odwrotne wyznaczamy w oparciu
o twierdzenie Fermata
© Robert Borowiec
Slajd 20/40
Arytmetyka modularna
Zredukowany zbiór residuów mod n jest podzbiorem
residuów {1,..., n-1} względnie pierwszych z n.
Liczba 0 nigdy nie wchodzi w skład zredukowanego
zbioru residuów.
Na przykład: dla n=10 to zredukowany zbiór residuów
zawiera liczby{1, 3, 7, 9}.
Gdy p jest liczbą pierwszą to zredukowany zbiór
residuów zawiera p-1 elementów {1, ....p-1}.
© Robert Borowiec
Slajd 21/40
Funkcja Eulera
Funkcja Eulera fð(n) okreÅ›la ilość liczb naturalnych
w zbiorze {1, 2, ..., n-1} względnie pierwszych z n.
Lub inaczej określa liczbę elementów w
zredukowanym zbiorze residuów modulo n.
PrzykÅ‚ad. fð(8)=4, ponieważ w zbiorze liczb
mniejszych od 8 tylko 1, 3, 5 i 7 są względnie
pierwsze z 8.
PrzykÅ‚ad. Dla liczby pierwszej p fð(p)=p-1,
© Robert Borowiec
Slajd 22/40
Twierdzenia
Twierdzenie Fermata. Niech p będzie liczbą
pierwszą. Wówczas dla każdej liczby a spełniającej
warunek NWD(a, p)=1 zachodzi
p-ð1
a mod p =ð 1
Uogólnienie Eulera. Dla każdego a i n takich,
że NWD(a, n)=1, zachodzi równanie:
afð(ðn)ð mod n =ð 1
© Robert Borowiec
Slajd 23/40
Obliczanie odwrotności liczby
Jeżeli:
(ða ×ð x)ðmod n =ð 1
gdy NWD(a,n)=1. Rozwiązanie to ma postać:
x =ð afð(ðn)ð-ð1 mod n
Jeżeli n jest liczba pierwszą, to:
x =ð a(ðn-ð1)ð-ð1 mod n =ð an-ð2 mod n
© Robert Borowiec
Slajd 24/40
Rozszerzone ciało Galoisa
" Rozszerzone ciało Galoisa oznaczamy CG(q)
q=pm, gdzie p jest liczbÄ… pierwszÄ…, a m jest
liczbÄ… naturalnÄ…
" Ciało rozszerzone służy do pozycyjnego zapisu
liczb w oparciu o elementy ciała podstawowego
" Przykład: Ciało rozszerzone CG(4)=CG(22)
 Elementy ciała {0,1,x,x+1}
 Elementy w zapisie pozycyjnym {00,01,10,11}
 Mnożenie elementów ciała: mod p(x) (wielomian
pierwotny ciała).
 Zastosowanie operatora mod p(x) konieczne tylko
wtedy, gdy wynik wychodzi poza zakres liczbowy
© Robert Borowiec
Slajd 25/40
Przestrzenie wektorowe
Przestrzeń liniowa V rozpięta nad ciałem liczbowym
C jest to zbiór elementów, dla którego są spełnione
odpowiednie aksjomaty. Przestrzeń liniowa jest
nazywana również przestrzenią wektorową, a jej
elementy - wektorami. Elementy ciała C są
skalarami
© Robert Borowiec
Slajd 26/40
Aksjomaty przestrzeni liniowej
(1) zbiór V jest grupą abelową względem dodawania;
(2) dla dowolnego wektora v Îð V i dowolnego skalara c Îð C zachodzi
c·v Îð V; (5a)
(3) dla dowolnych wektorów v, u Îð V i dowolnego skalara c Îð C zachodzi
c ·(v + u) = c · v + c · u; (5b)
(4) dla dowolnego wektora v Îð V i dowolnych skalarów c,d Îð C zachodzi
(c + d) · v = c · v + d · v; (5c)
(5) dla dowolnego wektora v Îð V i dowolnych skalarów c,d Îð C zachodzi
(c · d) · v = c ·(d · v). (5d)
© Robert Borowiec
Slajd 27/40
Wektory liniowo niezależne
Jeżeli v1, v2, ..., vk, są wektorami w przestrzeni liniowej V
rozpiętej nad ciałem liczbowym C, to dowolną sumę o
postaci
u =ð a1v1 +ð a2v2 +ð ×ð×ð×ð +ð ak vk
,(8)
w której są elementami ciała C, nazywamy liniową
kombinacją wektorów . O zbiorze k wektorów {v1, v2, ..., vk}
mówimy, że jest liniowo niezależny jeśli dla dowolnie
wybranego zbioru skalarów {a1, a2, ..., ak} zależność
a1v1 +ð a2v2 +ð ×ð×ð×ð +ð ak vk =ð 0
(9)
zachodzi wtedy i tylko wtedy, gdy wszystkie są równe zeru,
tzn.
a1 =ð a2 =ð ×ð×ð×ð =ð ak =ð 0.
© Robert Borowiec
Slajd 28/40
Wymiar przestrzeni
Wymiar przestrzeni - największa liczba liniowo niezależnych
wektorów w przestrzeni stanowi.
LiczbÄ… stopni swobody przestrzeni  inaczej wymiar przestrzeni
Baza przestrzeni n wymiarowej - zbiór n liniowo niezależnych
wektorów.
Przykład:
(0,0,1), (0,1,0) i (1,0,0) -V3 nad CG(2)
(0,0,1), (0,1,0) i (0,1,1) -V2 nad CG(2)
© Robert Borowiec
Slajd 29/40
Przykłady przestrzeni
" Przestrzeń ciągła (rozpięta nad zbiorem
liczb rzeczywistych)
" Przestrzeń ziarnista (dyskretna) (rozpięta
nad zbiorem liczb całkowitych)
" Przestrzeń ziarnista-skończona (rozpięta
nad ciałem Galoisa)
© Robert Borowiec
Slajd 30/40
Przykład przestrzeni liniowej
© Robert Borowiec
Slajd 31/40
CiÄ…gi binarne «ð wielomiany
Niech v będzie n-pozycyjnym ciągiem binarnym
a =ð (ðan-ð1,an-ð2...,a1,a0)ð
Wprowadza się przekształcenie
n-ð1
F(ða)ðºð
åða xi
i
n -ð1 n 0
v(ðx)ð =ð vn -ð1x +ð vn -ð 2i=ðo-ð 2 +ð ×ð ×ð ×ð +ð v1x1 +ð v0 x
x
© Robert Borowiec
Slajd 32/40
CiÄ…gi binarne «ð wielomiany
a =ð (ðan-ð1, an-ð2,×ð×ð×ð, a1, a0)ð
a(ðx)ð =ð an-ð1xn-ð1 +ð an-ð2xn-ð2 +ð ×ð×ð×ð +ð a1x1 +ð a0x0
© Robert Borowiec
Slajd 33/40
Dodawanie wielomianów
Dodawanie wielomianów polega na dodawaniu ich
współczynników stojących przy tych samych
potęgach x w odpowiednim ciele.
Przykłady:
CG(5): 25ØeÜ2 + 35ØeÜ1 + 25ØeÜ0 + 25ØeÜ2 + 35ØeÜ1 + 25ØeÜ0 =
2 + 2 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ2 + 3 + 3 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ1 +
2 + 2 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ0 = 45ØeÜ2 + 5ØeÜ1 + 45ØeÜ0
CG(2): 15ØeÜ2 + 15ØeÜ1 + 15ØeÜ0 + 15ØeÜ2 + 05ØeÜ1 + 15ØeÜ0 =
1 + 1 5ØZÜ5Ø\Ü5ØQÜ 2 5ØeÜ2 + 1 + 0 5ØZÜ5Ø\Ü5ØQÜ 2 5ØeÜ1 +
1 + 1 5ØZÜ5Ø\Ü5ØQÜ 2 5ØeÜ0 = 5ØeÜ
© Robert Borowiec
Slajd 34/40
Dodawanie wielomianów-ogólnie
Mamy dwa wielomiany:
n-ð1 n-ð1
f1(ðx)ðºð f2(ðx)ðºð
åða xi åðb xi
i i
i=ðo i=ðo
Ich sumę w ciele CG(p) możemy zapisać:
n-ð1
f1(ðx)ð+ð f2(ðx)ðºð
åð(ð(ða +ð bi)ðmod p)ðxi
i
i=ðo
© Robert Borowiec
Slajd 35/40
Dodawanie wielomianów
bezpośrednio na ciągach binarnych
© Robert Borowiec
Slajd 36/40
Mnożenie wielomianów
" Przy mnożeniu wielomianów mnożymy każdy element
wielomianu z każdy
" Współczynniki wielomianów mnożymy w odpowiednim
ciele, a współczynniki przy niewiadomych dodajemy
normalnie
Przykład CG(5):
2+2
25ØeÜ2 + 35ØeÜ1 + 25ØeÜ0 " 25ØeÜ2 + 35ØeÜ1 + 25ØeÜ0 = 2 " 2 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ +
2+1 2+0 1+2
2 " 3 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ + 2 " 2 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ + 3 " 2 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ +
1+1 1+0 0+2
3 " 3 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ + 3 " 2 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ + 2 " 2 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ +
0+1 0+0
2 " 3 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ + 2 " 2 5ØZÜ5Ø\Ü5ØQÜ 5 5ØeÜ =
=45ØeÜ4 + 25ØeÜ3 + 25ØeÜ2 + 25ØeÜ1 + 4
© Robert Borowiec
Slajd 37/40
Mnożenie wielomianów
Mamy dwa wielomiany:
m-ð1 n-ð1
f1(ðx)ðºð f2(ðx)ðºð
åða xk åðb xi
k i
k =ðo i=ðo
Ich iloczyn w ciele CG(p) możemy zapisać:
f1(ðx)ð×ð f2(ðx)ðºð ×ðbi)ðmod p)ð×ð x(ði+ðk)ð
Õð(ð(ðak
i,k
© Robert Borowiec
Slajd 38/40
Mnożenie wielomianów bezpośrednio
na ciÄ…gach binarnych
© Robert Borowiec
Slajd 39/40
Dzielenie wielomianów
" Bezpośrednio na wielomianach
" Binarnie
© Robert Borowiec
Slajd 40/40
KONIEC
Dziękuję za uwagę
© Robert Borowiec