MI-AAK (Aritmetika a kódy)
Cyklické kódy c doc. Ing. Alois Pluháček, CSc., 2011
Katedra číslicového návrhu Fakulta informačních technologií České vysoké učení technické v Praze
Evropský sociální fond Praha & EU: Investujeme do vaší budoucnosti
K3. Cyklické kódy • • • • • • • • • • • • • • •
mnohočleny, reprezentace slov, chyby a shluky chyb kódy generované mnohočlenem — 1. typ násobení mnohočlenů syndrom chyb dělení mnohočlenů dělitelnost a stupeň mnohočlenů a jejich kongruence detekce shluků chyb kódy generované mnohočlenem a lineární kódy kódy generované mnohočlenem — 2. typ cyklické kódy konečná tělesa kořeny mnohočlenu minimální mnohočleny Hammingovy kódy mnohočleny xi−1
MI-AAK
c A. Pluháček 2011
mnohočleny
mnohočleny nad tělesem GF(2): Příklad: C(x) = cn−1xn−1 + · · · + c1x + c0 ci ∈ GF(2) x ∈ ? ⇐ x je neznámá (doslova !) mnohočleny stupně < n: • vektorový/lineární prostor (ale bez skalárního součinu) • izomorfní s prostorem uspořádaných ntic: cn−1xn−1 + · · · + c0 ∼ (cn−1, . . . , c0) př.: n = 7 x5 +x3 +x+1 ∼ 0101011 • izomorfie — jen:
součet
&
násobení skalárem
mnohočleny: • násobení a dělení mnohočlenů — obv. postup • analogie s okruhem celých čísel — dělitelnost MI-AAK
K3 – 1
c A. Pluháček 2011
reprezentace slov a = (ak−1 , . . . , a0 ) b = (bn−1 , . . . , b0 ) .. . a b e c
∼ ∼ ∼ ∼
A(x) B(x) E(x) C(x)
příklad:
k n n n
bitů bitů bitů bitů
∼ A(x) = ak−1 xk−1 + · · · + a0 ∼ B(x) = bn−1 xn−1 + · · · + b0 .. .. . . původní informace vyslaná data — kódové slovo chyby (chybové slovo) čtená data — slovo
n=7 b = 0 1 0 1 1 0 0 ∼ B(x) = x5+x3+x2 = = 0 ·x 6+1 ·x 5+0 ·x 4+1 ·x 3+1 ·x 2+0 ·x 1+0 ·x 0 b lze tedy považovat za jinou formu zápisu B(x)
uvědomíme si: uspořádaná n-tice ∼ mnohočlen stupně ≤ n−1 < n MI-AAK
K3 – 2
c A. Pluháček 2011
chyby a shluky chyb b+e=c ∼
B(x) + E(x) = C(x)
shluk chyb E(x) E(x) = E ′ (x) · xj
&
x 6 | E ′ (x)
E ′ (x) ∼ e’ =⇒ E ′ (x) · xj ∼ e’ ⊳ j, kde ⊳ j označuje posuv o j míst vlevo E ′ (x) ∼ e’ · · · tvar shluku chyb j · · · pozice shluku chyb deg E ′ (x) + 1 · · · délka shluku chyb deg E ′ (x) označuje stupeň mnohočlenu E ′ (x) příklad: E(x) ∼ 0101100 E ′ (x) ∼ 1011 deg E ′ (x) = 3 MI-AAK
. . . shluk chyb délky 4 j =2
K3 – 3
c A. Pluháček 2011
kódy generované mnohočlenem — 1. typ B(x) = A(x) · G(x) G(x) = g r xr + · · · + g 0
—
g0 = 6 0 n = max deg B(x) + 1 k = max deg A(x) + 1 r = deg G(x)
x 6 | G(x)
generovací mnohočlen
⇐⇒
Proč? ⇒
n=k+r
deg G(x) . . . redundance (nadbytečnost) příklad: G(x) = x3+x+1 a = 1010 ⇒ A(x) = x3+x B(x) = A(x) · G(x) = x6+x3+x2+x b = 100 1110 MI-AAK
K3 – 4
c A. Pluháček 2011
násobení mnohočlenů příklad: B(x) = G(x)·A(x) = (x3+x+1) · (x3+x) 1 ·x 6 +0 ·x 5+1 ·x 4+1 ·x 3 0 ·x 5+0 ·x 4+0 ·x 3+0 ·x 2 1 ·x 4+0 ·x 3+1 ·x 2+1 ·x 1 0 ·x 3+0 ·x 2+0 ·x 1+0 ·x 0 1 ·x 6+0 ·x 5+0 ·x 4+1 ·x 3+1 ·x 2+1 ·x 1+0 ·x 0 „zkrácený zápisÿ: 1 0 1 1 · 1 0 1 0
G(x)·x3 G(x)·0 G(x)·x G(x)·0 = B(x)
(zde · neoznačuje skalární součin !!!)
1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 1 1 0 ∼ b=g·a MI-AAK
K3 – 5
c A. Pluháček 2011
násobení mnohočlenů
ii
B(x) = G(x)·A(x) G(x) = g 3 x3 + · · · + g 0 = x3+x+1
předchozí příklad: 1 0 1 1 · 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 0 1 MI-AAK
0 1 1 0 0 0 1 1 0 ∼ b
klopný obvod typu D
K3 – 6
c A. Pluháček 2011
násobení mnohočlenů
iii
B(x) = G(x)·A(x) G(x) = g 3 x3 + · · · + g 0 = x3+x+1
předchozí příklad: 1 0 1 1 · 1 0 1 0 1 0 1 1 0 0 0 1 0 0 1 0 0 1 MI-AAK
0 1 1 0 0 0 1 1 0 ∼ b
K3 – 7
c A. Pluháček 2011
syndrom chyb kód generovaný mnohočlenem: B(x) = A(x)·G(x) G(x) | B(x)
⇒ B(x) % G(x) = 0 (% označuje zbytek po dělení)
B(x) + E(x) = C(x) E(x) = 0 ⇒ C(x) % G(x) = 0 S(x) = C(x) % G(x)
!
—
syndrom chyb
S(x) = 0 ⇐⇒ C(x) ∼ kódové slovo
S(x) = = = =
C(x) % G(x) = [B(x)+E(x)] % G(x) = B(x) % G(x) + E(x) % G(x) = 0 + E(x) % G(x) = E(x) % G(x) syndrom závisí pouze na chybách
MI-AAK
K3 – 8
c A. Pluháček 2011
dělení mnohočlenů příklad: C(x) = x6+x2+x G(x) = x3+x+1
··· ···
dělenec dělitel
1 ·x 6+0 ·x 5+0 ·x 4+0 ·x 3+1 ·x 2+1 ·x 1+0 ·x 0 1 ·x 6+0 ·x 5+1 ·x 4+1 ·x 3 0 ·x 5+1 ·x 4+1 ·x 3+1 ·x 2 0 ·x 5+0 ·x 4+0 ·x 3+0 ·x 2 1 ·x 4+1 ·x 3+1 ·x 2+1 ·x 1 1 ·x 4+0 ·x 3+1 ·x 2+1 ·x 1 1 ·x 3+0 ·x 2+0 ·x 1+0 ·x 0 1 ·x 3+0 ·x 2+1 ·x 1+1 ·x 0
=⇒ 1 ·x 3 ←֓ =⇒ 0 ·x 2 ←֓ =⇒ 1 ·x 1 ←֓ =⇒ 1 ·x 0 ←֓
0 ·x 2+1 ·x 1+1 ·x 0 ⇓ zbytek C(x) % G(x) = x+1 podíl C(x) ÷ G(x) = x3+x+1 MI-AAK
K3 – 9
⇓ ⇐ c A. Pluháček 2011
dělení mnohočlenů
ii
„zkrácený zápisÿ: 1 0 0 0 1 1 0 :1 0 1 1 =1 0 1 1 1 0 1 1 ↓ | | 0 0 1 1 1 | | C(x) 0 0 0 0 ↓ | G(x) 0 1 1 1 1 | 1 0 1 1 ↓ C(x) ÷ G(x) 0 1 0 0 0 C(x) % G(x) 1 0 1 1 0 0 1 1
6543210
∼ 1000110 ∼ 1011 ∼ 1011 ∼ 011
výstup: nejprve C(x) ÷ G(x) potom C(x) % G(x) MI-AAK
K3 – 10
c A. Pluháček 2011
dělitelnost a stupeň mnohočlenů označení: P (x) ÷ Q(x) — podíl P (x) % Q(x) — zbytek P (x) % Q(x) = 0 ⇐⇒ Q(x) | P (x) 6= ⇐⇒ Q(x) 6 | P (x) deg P (x) — stupeň mnohočlenu P (x) deg 0 = −∞ (??? deg 0 = −1 ???)
deg (P (x)+Q(x)) deg (P (x) · Q(x)) deg (P (x)%Q(x)) deg (P (x)÷Q(x))
≤ max (deg P (x), deg Q(x)) = deg P (x) + deg Q(x) < deg Q(x) Q(x) = 6 0 = deg P (x) − deg Q(x) Q(x) = 6 0
Q(x) | P (x) ⇐⇒ ∃X(x) Q(x) je dělitelem P (x) MI-AAK
K3 – 11
P (x) = Q(x)·X(x)
c A. Pluháček 2011
dělitelnost a stupeň mnohočlenů
ii
nerozložitelný (ireducibilní) mnohočlen (polynom) P (x): • nemá jiné dělitele než 1 a P (x) a jejich skalární násobky • obdoba prvočísel polynom Q(x) lze rozložit na prvočinitele prvočinitel = nerozložitelný mnohočlen rozklad na prvočinitele je jednoznačný (až na skalární násobky)
příklad: x7 + 1 = (x3+x2+1) · (x3+x+1) · (x+1)
MI-AAK
K3 – 12
c A. Pluháček 2011
kongruence mnohočlenů (∃ K(x)) P (x) = Q(x) + M (x)·K(x) m P (x) ≡ Q(x) mod M (x) Mnohočleny P (x) a Q(x) jsou kongruentní modulo M (x). P (x)≡Q(x) mod M (x) ⇔ P (x)%M (x)=Q(x)%M (x) Kongruence je relace reflexivní, symetrická a tranzitivní. P (x)≡Q(x) & U (x)≡V (x) ⇓ P (x) + U (x) ≡ Q(x) + V (x) P (x) · U (x) ≡ Q(x) · V (x) ⇓ P (x) + X(x) ≡ Q(x) + X(x) P (x) · X(x) ≡ Q(x) · X(x) MI-AAK
K3 – 13
mod M (x)
c A. Pluháček 2011
detekce shluků chyb shluk chyb E(x):
E(x) = E ′ (x) · xj
&
x 6 | E ′ (x)
E ′ (x) — tvar shluku chyb L = deg E ′ (x) + 1 — délka shluku chyb detekce chyb: S(x) = E(x) % G(x) 6= 0 ? x 6 | G(x) =⇒ xj nemá vliv E ′ (x) % G(x) = 0 ? E ′ (x) 6= 0 deg E ′ (x) <
deg G(x)
=⇒ E ′ (x) % G(x) 6= 0
Lze tedy zjistit všechny shluky chyb délky L ≤ r = deg G(x) . příklad: G(x) = x16+1 =⇒ L ≤ 16 MI-AAK
K3 – 14
c A. Pluháček 2011
kódy generované mnohočlenem a lineární kódy A(x) = ak−1 xk−1 + · · · + a0 ⇒ deg A(x) < k B(x) = A(x) · G(x) = = ak−1 · G(x) · xk−1+. . . +a0 · G(x) G(x) · xk−1, . . . , G(x) — lineárně nezávislé A(x) · G(x)
—
— báze lineárního prostoru všechny lineární kombinace
Kód generovaný mnohočlenem je lineární. ? Existuje generovací matice G? ? Existuje-li, jaký má tvar?
MI-AAK
K3 – 15
c A. Pluháček 2011
kódy generované mnohočlenem a lineární kódy
ii
G(x) = g r xr + · · · + g 0 ∼ g = (g r, . . . , g 0) G(x) · xj ∼ g ⊳j aj · xj · G(x) ∼ aj · (g ⊳ j) G · · · generovací matice a = (ak−1 , . . . , a0 ), aj = 1 a ai = 0, je-li i 6= j a · G = g j , kde g j je j-tý řádek matice G
G=
MI-AAK
g r g r−1 . . . 0 g ⊳ (k−1) 0 g ⊳ (k−2) gr ... 0 = . .. .. . .. . . · · · .. g 0 0 . . . g0
K3 – 16
c A. Pluháček 2011
kódy generované mnohočlenem — 2. typ kód generovaný mnohočlenem (1. typ) B(x) = A(x) · G(x) — nebývá systematický příklad: G(x) = x3+x+1 1 0 1 1 0 0 1 0 1 1 G= 0 0 1 0 1 0 0 0 1 0
? Jak vytvořit systematický klon ? B(x) = A(x) · xr + A(x) · xr % G(x) , kde r = deg G(x)
0 0 1 1
0 0 0 1
kód generovaný mnohočlenem — 2. typ příklad: G(x) = x3+x+1 A(x) ∼ 0101 A(x) · x3 ∼ 0101 0 0 0 A(x) · x3 % G(x) ∼ 100 B(x) ∼ 0101 100 MI-AAK
K3 – 17
c A. Pluháček 2011
kódy generované mnohočlenem — 2. typ
ii
příklad: G(x) = x3+x+1 a 0 0 00 0 0 01 0 0 10 0 0 11 0 1 00 0 1 01 0 1 10 0 1 11 1 0 00 1 0 01 1 0 10 1 0 11 1 1 00 1 1 01 1 1 10 1 1 11 MI-AAK
b 1. typ 0 0 00 00 0 0 0 01 01 1 0 0 10 11 0 0 0 11 10 1 0 1 01 10 0 0 1 00 11 1 0 1 11 01 0 0 1 10 00 1 1 0 11 00 0 1 0 10 01 1 1 0 01 11 0 1 0 00 10 1 1 1 10 10 0 1 1 11 11 1 1 1 00 01 0 1 1 01 00 1
2. typ 0 00 0 0 0 0 0 00 1 0 1 1 0 01 0 1 1 0 0 01 1 1 0 1 0 10 0 1 1 1 0 10 1 1 0 0 0 11 0 0 0 1 0 11 1 0 1 0 1 00 0 1 0 1 1 00 1 1 1 0 1 01 0 0 1 1 1 01 1 0 0 0 1 10 0 0 1 0 1 10 1 0 0 1 1 11 0 1 0 0 1 11 1 1 1 1 K3 – 18
totéž osmičkově 00 01 02 03 04 05 06 07 10 11 12 13 14 15 16 17
00 01 02 03 05 04 07 06 13 12 11 10 16 17 14 15
0 3 6 5 4 7 2 1 0 3 6 5 4 7 2 1
00 01 02 03 04 05 06 07 10 11 12 13 14 15 16 17
0 3 6 5 7 4 1 2 5 6 3 0 2 1 4 7
c A. Pluháček 2011
cyklické kódy
cyklický kód : • lineární kód • cyklický posuv kódového slova → kódové slovo příklad:
b a 0 0 1 1
0 1 0 1
K1 000 011 101 110
K2 111 001 010 100
0 0 1 1
K3 000 101 010 111
0 1 1 0
α β γ δ
K1 je cyklický kód K2 není cyklický kód ⇐ není lineární K3 není cyklický kód ⇐ např. β ⊳ 1 6∈ K3
MI-AAK
K3 – 19
c A. Pluháček 2011
cyklické kódy a kódy generované mnohočlenem předpoklad:
G(x) | (xn − 1), tzn.: G(x) · H(x) = xn−1 ∃H(x)
B(x) = bn−1 xn−1 + · · · + b0 = G(x) · A(x) cyklický posuv vlevo: B ′ (x) = B(x) · x − bn−1 · xn + bn−1 = = B(x) · x − bn−1 · (xn − 1) = = A(x) · G(x) · x − bn−1 · G(x) · H(x) = = [A(x) · x + bn−1 · H(x)] · G(x) ⇓ kód (n, k) generovaný G(x) | B ′ (x) =⇒ mnohočlenem G(x) je cyklický Platí
MI-AAK
• pro 1. typ kódů generovaných mnohočlenem, ale i • pro 2. typ kódů generovaných mnohočlenem a • pro všechny jejich klony. K3 – 20
c A. Pluháček 2011
cyklické kódy a kódy generované mnohočlenem
ii
předpoklad: K — cyklický kód (tzn.: lineární kód + posuv kódového slova . . . ) kódová slova: b0, b1, . . . ∼ B 0(x), B 1(x), . . . b0 = 0 ∼ B 0(x) = 0 (∀i > 1) deg B 1(x) ≤
deg B i(x)
=⇒ (∀i > 1) deg B 1(x) 6= deg B i(x) (existuje jediný mnohočlen tohoto stupně) (jinak by existoval nenulový mnohočlen nižšího stupně) označme G(x) = B 1(x) r = deg G(x) = deg B 1(x) G(x), G(x)·x, . . . , G(x)·xn−r−1 — lineárně nezávislé ⇒ a tvoří bázi kódu generovaného mnohočlenem G(x)
=⇒
MI-AAK
Každý cyklický kód nebo nějaký jeho klon je kód generovaný nějakým mnohočlenem G(x). Mnohočlenem G(x) je mnohočlen nejnižšího stupně příslušející nenulovému kódovému slovu. K3 – 21
c A. Pluháček 2011
dva jednoduché cyklické kódy G(x) = x + 1
Æ
systematický kód
(kód 2. typu)
B(x) = G(x) · A(x) x = 1 =⇒ G(x) = G(1) = 0 =⇒ =⇒ B(x) = bn−1 + · · · + b0 = 0 =⇒ parita (sudá) G(x) = xr + 1
Æ
B(x) = 0
cyklický kód pro každé n
systematický kód
(kód 2. typu)
xr ≡ 1 mod G(x) B(x) = bn−1 xn−1 + · · · + b0 B(x) = Bj (x) · (xr )j + · · · + B0 (x) · (xr )0 B(x) ≡ Bj (x) + · · · + B0 (x) mod G(x) =⇒
„podélnáÿ parita rtic bitů (sudá) r | n ⇒ cyklický kód
MI-AAK
K3 – 22
c A. Pluháček 2011
konečná tělesa konečné těleso ≃ Galoisovo těleso GF(q) • q =p prvky: u+v u · v
, kde p je prvočíslo u a v — nezáporná celá čísla menší než p ◭ (u+v) % p ◭ (u · v) % p
• q = pm , kde p je prvočíslo a m > 1 přirozené číslo P (z) — nerozložitelný mnohočlen nad tělesem GF(p), deg P (z) = m prvky: U (z) a V (z) — mnohočleny stupně <m U (z)+V (z) — sčítání koeficientů mod p P (z)➪GF(q) U (z) · V (z) ◭ [ U (z) · V (z) ] % P (z) • Neexistuje konečné těleso s jiným počtem prvků! • Všechna konečná tělesa se stejným počtem prvků jsou vzájemně izomorfní! (méně přesně: „ jsou všechna stejnáÿ) MI-AAK
K3 – 23
c A. Pluháček 2011
konečná tělesa
ii
př.: GF(7) 3+ 6 = 2 3·6=4 atp. + 0 1 2 3 4 5 6
0 0 1 2 3 4 5 6
1 1 2 3 4 5 6 0
(protože 3 + 6 % 9 = 7 % 7 = 2) (protože 3 · 6 % 7 = 18 % 7 = 4) 2 2 3 4 5 6 0 1
3 3 4 5 6 0 1 2
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4
6 6 0 1 2 3 4 5
· 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1
22 = 4, 23 = 4·2 = 1, 24 = 1·2 = 2, 25 = 1·2 = 4, . . . 30 =1, 31 =3, 32 =2, 33 =6, 34 =4, 35 =5, 36 =1 50 =1, 51 =5, 52 =4, 53 =6, 54 =2, 55 =3, 56 =1 MI-AAK
K3 – 24
c A. Pluháček 2011
konečná tělesa
př.: GF(4) = GF(22) P (z) = z 2 + z + 1
iii
nerozložitelný mnohočlen 2. stupně nad tělesem GF(2)
prvky GF(8): 0, 1, z, z+1 (z+1) + z = 1 (z+1) + 1 = z atp. z·z = z+1 [ protože z · z % P (z) = z 2 % P (z) = z+1 ] (z+1)·z = 1 [ protože (z+1) · z % P (z) = = (z 2 +z) % P (z) = 1 ] atp. z 0 = 1,
MI-AAK
z 1 = z,
z 2 = z+1,
K3 – 25
z 3 = z 2·z=1
atd.
c A. Pluháček 2011
konečná tělesa
iv
ϑ ∈ GF(q), ϑ 6= 0 (∃i) ϑi = 1
(např. číslo u nebo mnohočlen U (z)) způsob zápisu prvku ϑ není podstatný nejmenší takové i se nazývá řád prvku ϑ
V každém konečném tělese existuje aspoň jeden prvek α řádu q − 1; takový prvek se nazývá primitivní prvek. =⇒ Každý prvek ϑ 6= 0 je nějakou mocninou prvku α. P (z) ➪ GF(pm) Je-li z primitivním prvkem tělesa, P (z) se nazývá primitivní mnohočlen. řád mnohočlenu P (z): j = ord P (z) P (z) | (z j −1) & (∀ i < j) P (z)6 | (z i−1)
deg P (z) ord P (z) = p −1 ⇐⇒ P (z) je primitivní MI-AAK
K3 – 26
c A. Pluháček 2011
konečná tělesa
v
příklad: p = 2 P (z) = (z 2 + z + 1) | (z 3+1) & P (z) 6 | (z 1+1) & P (z) 6 | (z 2+1) řád P (z) ord P (z) = 3 = p2−1 deg P (z) = 2 stupeň P (z) P (z) je primitivní mnohočlen: GF(22) = GF(4) : prvky ϑ ∈ {0, 1, z, z+1} primitivní prvek α = z
Æ
0+ϑ = ϑ z+1 = (z+1)
Æ
ϑ+ϑ = 0 (z+1)+1 = z
(z+1)+z = 1
0·ϑ = 0 1·ϑ = ϑ z·z = z 2 % P (z) = z+1 z·(z+1) = (z 2+z) % P (z) = 1 (z+1)·(z+1) = (z 2+1) % P (z) = z MI-AAK
K3 – 27
c A. Pluháček 2011
konečná tělesa
vi
příklad: GF(4) ← z 2+z+1 různé způsoby označování prvků:
+ 0 1 2 3
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0
· 0 1 2 3
0 0 0 0 0
1 0 1 2 3
mocniny primitivního prvku α: příklad použití: 3·3=α2·α2=α4=α3·α1=1·2 3·3 = 2 neboli 11·11 = 10 anebo (z+1)·(z+1) = z MI-AAK
K3 – 28
2 0 2 3 1
0 1 z z+1 3 0 3 1 2 i
00 01 10 11
0 1 2 3
αi = z i
0 1 01 1 z 10 2 z+1 11 3 1 01
1 2 3 1
c A. Pluháček 2011
kořeny mnohočlenu charakteristika tělesa χ — nejmenší takové číslo, že Pχ 1=0 i=1 GF(pm), kde p je prvočíslo =⇒ χ = p F (x)
···
mnohočlen nad tělesem GF(p), tzn. koeficienty mnohočlenu ∈ GF(p)
ξ ∈ GF(q) = GF(pm)
&
F (ξ) = 0
• ξ je kořen neboli nula mnohočlenu F (x) • ∃Y (x) F (x) = (x−ξ) · Y (x) • F (ξ) = 0 =⇒ F (ξ χ) = 0
⇔
(x−ξ) | F (x)
příklad: z 3 + z + 1 ➪ GF(8) F (x) = x3 + x2 + 1 F (z 3) = 0 ⇒ F (z 6) = 0 ⇒ ⇒ F (z 12) = F (z 5) = 0 MI-AAK
K3 – 29
c A. Pluháček 2011
minimální mnohočleny P (z) ➪ GF(q) = GF(pm) β ∈ GF(q) M β (β) = 0 F (β) = 0 ⇒
deg F (x) ≥ deg
M β (x) je minimální mnohočlen M β (x) prvku β
minimální mnohočlen • je pro daný prvek jediný (až na svoje na skalární násobky) • F (β) = 0 ⇐⇒ M β (x) | F (x) • M α(x) = P (x) — α je primitivní prvek minimální mnohočlen M β (x) prvku β=αi, bude označován též M #i(x) MI-AAK
K3 – 30
c A. Pluháček 2011
minimální mnohočleny
ii
Jak nalézt minimální mnohočlen? β ∈ GF(pm) M β (x) = ? j −1 p p , ... x −β M β (x) = (x − β) x − β j kde j > 1 je takové nejmenší číslo, že β(p ) = β γ = βp
=⇒
M γ (x) = M β (x)
př.: GF(4) = GF(22) ϑ = 3 = z + 1 ϑ2 = 2 = z ϑ4 = 3 = z + 1 ⇒ M ϑ(x) = (x − 2)(x − 3) = x2 + x + 1 κ = 2 = z ⇒ M κ (x) = M ϑ(x) = x2 + x + 1 λ=1 ⇒ M λ(x) = x + 1 µ=0 ⇒ M µ(x) = x MI-AAK
K3 – 31
c A. Pluháček 2011
Hammingovy kódy kontrolní matice H Hammingova kódu K — — všechny možné vzájemně různé nenulové sloupce, např. | | | | H = αn − 1 αn − 2 ... α 1 , | | | | kde n = 2m−1 a α je primitivní prvek tělesa GF(2m) syndrom: s = c · HT = e · HT c = (cn-1 , . . . , c0 ) ∼ C(x) = cn-1 xn-1 + · · · + c0 ➥ s = cn-1 · αn-1 + . . . + c1 · α + c0 = C(α) s = 0 ⇐⇒ α je kořenem C(x) ⇐⇒ M α(x) | C(x) M α(x) je generovacím mnohočlenem K (nebo jeho klonu)
MI-AAK
K3 – 32
c A. Pluháček 2011
Hammingovy kódy
ii
G(x) — nerozložitelný mnohočlen,
deg G(x) ≥ 2 ➥ Hammingův kód s délkou slova n = ord G(x)
příklad: G(x) = (x8+x4+x3+x2+1) | (x255+1) r = deg G(x) = 8 n = ord G(x) = 255 k = n − r = 255 − 8 = 247 G(x) generuje cyklický Hammingův kód (255, 247)
Platí i naopak: Je-li K Hammingův kód (n, k), existuje mnohočlen G(x), který generuje cyklický kód ekvivalentní kódu K nebo jeho klon. MI-AAK
K3 – 33
c A. Pluháček 2011
mnohočleny (xi−1)
|
(xj −1)
xi−1 ⇐⇒
i | j
důkaz: 1. j = q·i & y = xi ⇒ xj = y q 1 je kořenem y q −1 ⇒ y q−1 = (y−1)·(něco) 2. předp.: j = q·i + z, kde z = j % q xj −1 = xq·i·xz −1 = xq·i·xz −xz + xz −1 = = (xq·i−1)·xz + xz −1 (xi−1) | (xq·i−1) ⇒ xz −1 = 0 ⇒z =0 dva cyklické kódy: G(x) = x + 1
pro všechna n ≥ 1
G(x) = xr + 1
pro r | n (kde n je délka kódového slova)
MI-AAK
K3 – 34
c A. Pluháček 2011