Opravyshlukůchyb. MI-AAK(Aritmetika a kódy)

MI-AAK (Aritmetika a kódy)

Opravy shluků chyb 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

K4. Opravy shluků chyb • prokládané kódy • Fireův kód • prodloužený Fireův kód • Meggittův dekodér • zkracování cyklických kódů • oprava shluku chyb podle Chiena

MI-AAK

c A. Pluháček 2011

prokládané kódy kód K (n, k) × m

[interleaved codes]

w

kód K ∗ (n∗ , k∗ ) = (m·n, m·k)

vzor: n = 7, k = 4, m = 3, n∗ = 21, k∗ = 12     a1 a4 a7 a10 b1 b4 b7 b10 b13 b16 b19 a a a a  ➡ b b b b b b b  2 5 8 11 2 5 8 11 14 17 20 a3 a6 a9 a12 b3 b6 b9 b12 b15 b18 b21 • Podle vzoru se a∗ = (a1 , . . . , ak∗ ) rozdělí na k m-tic. • Každá m-tice vytvoří jeden sloupec první matice. • Každý řádek druhé matice je kódovým slovem kódu K, který přísluší odpovídajícímu řádku první matice. • Seřazením m-tic bitů, které tvoří sloupce druhé matice, se získá kódové slovo b∗ = (b1 , . . . , bn∗ ) kódu K ∗ , které přísluší vektoru a∗ . MI-AAK

K4 – 1


[interleaved codes]

prokládané kódy

ii

kód K — kód SED ⇒ detekce shluku chyb do délky m kód K — kód SEC ⇒ oprava shluku chyb do délky m kód K — kód pro opravu shluku chyb do délky l ⇒ ⇒ oprava shluku chyb do délky m × l atd.   př.: kód K 1 0 0 0 1 0 1 0 1 0 0 1 1 1  G=  0 0 1 0 1 1 0  . . . kód (7,4) 0 0 0 1 0 1 1 m = 3 ⇒ kód (21,12) — oprava shluku do délky 3 a∗ = 1 1 1 0 0 1 0 0 0 1 0 0     1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 · G = 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0

b∗ = 1 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0

MI-AAK

K4 – 2


prokládané kódy

iii

kód K . . . cyklický kód (n, k) G(x) — generovací mnohočlen P P B(x) = A(x) · G(x) = aixi · g j xj i j aixi g j xj = ai g j xj +i kód K ∗ G∗ (x) = G(xm) B ′ (x) = A′ (x) · G∗ (x) = A(xm) · G(xm) aixim g j xjm = ai g j x(j +i)m př.: G(x) = x3+x+1 A(x)=x3+x2

G∗ (x) = x9+x3+1 A′ (x)=x9+x6

m=3

a = 1100 B(x) = A(x)·G(x) = = x6+x5+x4+x2 b = 1110100 MI-AAK

⇒

a’ = 001 001 000 000 B ′ (x) = A′ (x)·G∗ (x) = = x18+x15+x12+x6 b’ = 001 001 001 000 001 000 000

K4 – 3


prokládané kódy

iv

B i(x) = Ai(xm) · G(xm) · xi B(x) =

P

B i(x)

i G(x) | (xn+1)

=⇒ =⇒

pro i-tý řádek (číslováno zdola od 0) B(x) = A(x) · G(xm)

G(xm) | (xn · m+1)

Z toho plyne: Je-li kód K cyklický a G(x) je jeho generovacím mnohočlenem, je kód K ∗ zase cyklický a jeho generovacím mnohočlenem je G∗ (x) = G(xm) . př.: G(x) = x3+x+1 ... m=3 G∗ (x) = x9+x3+1 . . .

kód SEC (7,4) kód (21,12) pro opravu shluků chyb do délky 3

a∗ = 1 1 1 0 0 1 0 0 0 1 0 0 B ∗ (x) = A∗ (x) · x9 + A∗ (x) · x9 % G∗ (x) b∗ = 1 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 MI-AAK

K4 – 4


Fireův kód G(x) = P (x) · (xq +1) , kde • P (x) je nerozložitelný mnohočlen, • p = deg P (x) > 1 a • q a ord P (x) jsou nesoudělné, je generovacím mnohočlenem Fireova kódu (n, k), kde • n = ord P (x) · q , • k=n−r a • r = p + q, který umožňuje • detekci shluku chyb do délky Ld a • opravu, nemá-li shluk délku větší než Lo ≤ Ld , pokud • Ld + Lo ≤ q + 1 a • Lo ≤ p . Ld a Lo — konstantní (pro zvolenou aplikaci) MI-AAK

K4 – 5


Fireův kód

ii

př.: G(x) = (x3+x+1) · (x5+1), p = 3 ord (x3+x+1) = 7 (5 a 7 jsou nesoudělná čísla) n = 35, r = 8, k = 27 Ld = Lo = 3 (nebo Ld = 4 a Lo = 2 anebo Ld = 5 a Lo = 1)

pouze detekce (nebude-li se kód používat pro opravy): • 2 shluky chyb, jestliže – součet délek nepřesáhne q + 1, – aspoň jeden nemá délku větší než p. • 1 shluk chyb do délky r = p + q Není třeba předem volit, zda se kód použije pro detekci 1 nebo 2 shluků (a jakých). MI-AAK

K4 – 6


Fireův kód

iii

další příklady: 1. G(x) = (x4+x3+x2+x+1) · (x3+1) ord (x4+x3+x2+x+1) = 5 n = 15, r = 7, k = 8 Ld = Lo = 2 2. G(x) = (x5+x2+1) · (x9+1) ord (x5+x2+1) = 31 n = 279, r = 14, k = 265 Ld = Lo = 5 3. G(x) = (x7+x3+1) · (x16+1) ord (x7+x3+1) = 127 n = 2032, r = 23, Ld = 9, Lo = 8

MI-AAK

k = 2009

K4 – 7


prodloužený Fireův kód G(x) = P 1(x) · P 2(x) · · · · · P ν (x) · (xq+1) P 1(x), P 2(x), . . . , P ν (x) — nerozložitelné mnohočleny stupně mnohočlenů > 1 řády vzájemně nesoudělné a nesoudělné s q • n = ord P 1(x) · ord P 2(x) · · · · · ord P ν (x) · q • k=n−r • r = deg P 1(x)+deg P 2(x)+ · · · +deg P ν (x)+q příklad: P 1(x) = x11+x7+x6+x+1 P 2(x) = x12+x11+· · ·+x+1 P 3(x) = x11+x9+x7+x6+x5+x+1 Q(x) = x22+1 G(x) = P 1(x) · P 2(x) · P 3(x) · Q(x) kód (558 442, 558 386), tzn. r=56 Ld = Lo = 11 MI-AAK

K4 – 8


Meggittův dekodér cyklický kód: ∃H(x) G(x) · H(x) = xn + 1 xn = G(x) · H(x) + 1 syndrom:

S(x) = C(x) % G(x) = = E(x) % G(x)

shluk chyb:

E(x) = E ′ (x) · xj E(x) · xn−j E(x) · xn−j E(x) · xn−j S(x) · xn−j

x 6 | E ′ (x)

= E ′ (x) · xn = E ′ (x) · G(x) · H(x) + E ′ (x) ≡ E ′ (x) mod G(x) ≡ E ′ (x) mod G(x)

deg E ′ (x) ≤ deg G(x) E ′ (x) = (S(x) · xn−j ) % G(x)

MI-AAK

K4 – 9


Meggittův dekodér

ii

kód pro opravu shluků chyb do délky L oprava: S(x) = C(x) % G(x) S(x) = 0 ⇒ bez chyby a konec Pro i = 0, 1, . . . , n−1 nebo pro i = 1, 2, . . . , n se postupně určuje Y i(x) = S(x) · xi % G(x), dokud deg Y i(x) ≥ L. Je-li deg Y i(x) < L, j = (n − i) % n, D(x) = C(x) + Y i(x) · xj , jinak je shluk neopravitelný. pozn.: Y i(x) = S(x) · xi % G(x) = = Y i−1(x) · x % G(x) D(x) — opravené slovo MI-AAK

K4 – 10


Meggittův dekodér

iii

př.: G(x) = 1 0 1 1 ☛ zkrácený zápis mnohočlenu x3+x+1 cyklický Hammingův kód (7,4) opravuje „shlukyÿ chyb do délky 1 C(x) = 011 0110 S(x) = 011 0110 % 1011 = 111 = Y 0(x) deg Y 0(x) = 2 ≥ 1 Y 1(x) = 111 · 10 % 1011 = 101 deg Y 1(x) = 2 ≥ 1 Y 2(x) = 101 · 10 % 1011 = 001 deg Y 2(x) = 0 < 1 i=2 ⇒ j = 7−2 = 5 D(x) = 011 0110 + 001 · 105 = = 011 0110 + 010 0000 = = 001 0110 MI-AAK

K4 – 11


Meggittův dekodér

j = (n − i) % n

=⇒

i=0 i=1 i=2 i=n−1 i=n

iv

⇒ ⇒ ⇒ .. . ⇒ ⇒

j =0 j =n−1 j =n−2 j =1 j =0

př.: G(x) = 1 0 1 1

pozn.: Vyrovnávací paměť (dole ve schématu) lze zkrátit o 1 místo. (Uvažte jak!) MI-AAK

K4 – 12


Meggittův dekodér

v

kód pro opravu shluků chyb do délky L test:

deg Y i(x) < L

⇔

nuly v horních pozicích

př.: Fireův kod G(x) = (x2+x+1) · (x4+1) = x6+x5+x4+x2+x+1 2 n = 12, r = 6, k = 6 ord (x +x+1) = 3 ⇒ Lo = 2, Ld = 3 q =4 G(x) = 1 110 111

☛ x6+x5+x4+x2+x+1

C(x) = 110 000 000 000 C ′ (x) = 110 001 110 111 Y 0(x) = 011 101 Y 1(x) = 111 010 Y 2(x) = 000 011 i = 2,

S(x) = S ′ (x) = 011 101

deg Y 0(x) = 4 ≥ 2 deg Y 1(x) = 5 ≥ 2 deg Y 2(x) = 1 < 2

j = (n − i) % n = (12−2) % 12 = 10

E(x) = 11 · 1010 MI-AAK

☛ (x+1) · x10 K4 – 13


Meggittův dekodér

vi

C(x) lze předem vynásobit např. xr: • možnost testovat nuly v dolních pozicích; • první zbytek přísluší nejhořejším pozicím; • korekci lze zřejmým způsobem „synchronizovatÿ. př.: Fireův kod G(x) = 1 110 111

☛ x6+x5+x4+x2+x+1

1. C(x) = 110 000 000 000 S ∗(x) = C(x)·x6 % G(x) = 110 000 E(x) = 11·1010 ☛ (x+1) · x10 2. C(x) = 000 100 000 000 S ∗(x) = C(x)·x6 % G(x) S ∗(x)·x % G(x) S ∗(x)·x2 % G(x) E(x) = 01·1010-2 ☛ 1 · MI-AAK

K4 – 14

= 000 100 = 001 000 = 010 000 x8 c A. Pluháček 2011

Meggittův dekodér

vii

př.: obvod pro výpočet C(x)·x6 % (x6+x5+x4+x2+x+1)

alternativa (v tomto případě zbytečně komplikovaná) : x6 ≡ x5+x4+x2+x+1 mod x6+x5+x4+x2+x+1

2 dekodéry: 1. dekodér 2. dekodér MI-AAK

výpočet syndromu

oprava

výpočet syndromu

...

výpočet syndromu

oprava

...

K4 – 15


zkracování cyklických kódů K — kód (n, k) generovány mnohočlenem G(x) K′ — kód (ν, κ) κ
kódování — pro oba kódy stejné (až na dobu kódování) oprava shluků chyb — vychází z toho, že kód je cyklický • Lze doplnit n−ν nul. ⇒ Oprava trvá zbytečně dlouho. • Doplnění n−ν nul se pouze „předstíráÿ — C(x) se „předemÿ vynásobí xn−ν modulo G(x). MI-AAK

K4 – 16


oprava shluku chyb podle Chiena

Čínská věta o zbytcích: Jsou-li m1 , . . . , mη různá navzájem nesoudělná přirozená čísla, má soustava kongruencí x ≡ wi (mod mi), i = 1, . . . , η právě jedno řešení modulo m1 · . . . · mη . x ≡ (w 1−w 0)· m–1 0 · m0 + w0 (mod m1·m0), kde m–1 0 je takové číslo, že m–1 0 · m0 ≡ 1 (mod m1) –1 př.: m1 = 5, m0 = 3 ⇒ m–1 0 = 2 ⇒ m0 · m0 = 6 η =2

x ≡ 3 (mod 5) x ≡ 2 (mod 3) x ≡ (3 − 2) · 6 + 2 = 8 MI-AAK

K4 – 17

(mod 15) c A. Pluháček 2011


ii

modiﬁkace Čínské věty o zbytcích pro mnohočleny: Jsou-li M 1(x), . . . , M η (x) různé navzájem nesoudělné mnohočleny, má soustava kongruencí X(x) ≡ Ai(x) mod M i(x), i = 1, . . . , η právě jedno řešení modulo M 1(x) · . . . · M η(x). G(x) = G1(x) · G2(x), dříve bylo uvedeno: E ′ (x) ≡ C(x) · xn−j ⇓ E ′ (x) ≡ C(x) · xn−j E ′ (x) ≡ C(x) · xn−j MI-AAK

deg G1(x) ≤ deg G2(x) E ′ (x) = (S(x) · xn−j ) % G(x) S(x) = C(x) % G(x) mod G(x) mod G1(x) mod G2(x)

K4 – 18



E ′ (x) ≡ C(x) · xn−j ⇓ E ′ (x) ≡ C(x) · xn−j E ′ (x) ≡ C(x) · xn−j

iii

mod G(x) mod G1(x) mod G2(x)

⇓ současné dělení mnohočleny G1(x) a G2(x), dokud není zbytek stejný a nemá odpovídající stupeň

ρ=

ord G1(x)

⇒ C(x) · xi % G1(x) = C(x) · xi ± ρ % G1(x)

σ =

ord G2(x)

⇒ C(x) · xi % G2(x) = C(x) · xi ± σ % G2(x)

MI-AAK

K4 – 19



G(x) = G1(x) · G2(x),

iv

deg G1(x) ≥ deg G2(x)

postup při opravě shluku chyb do délky L: 1. Určí se u tak, aby deg (C(x) · xu % G1(x)) < L , 2. přiřadí se E ′ (x) = C(x) · xu % G1(x), 3. určí se v tak, aby deg (C(x) · xv % G2(x)) < L 4. najde se řešení soustavy kongruencí ξ ≡ u (mod ord G1(x)) a ξ ≡ v (mod ord G2(x)), 5. přiřadí se n − j = ξ.

Zobecnění na případ G(x) = G1(x) · G2(x) · . . . je zřejmé. MI-AAK

K4 – 20


Opravyshlukůchyb. MI-AAK(Aritmetika a kódy)

Recommend Documents