1 1.1 1.2 one way two way (talk back) (... ) 1.3 0 C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1
( (coding theory)) 2 2.1 (convolution code) (block code), 3 3.1 Q q Q n Q n 1 Q n x, y x = (x 1 x 2... x n ), y = (y 1 y 2... y n ) n d H (x, y) = δ(x i, y i ) i=1 1 x i y i δ(x i, y i ) = 0 x i = y i d H (x, y) x, y (Hamming distance) w(x) = d H (x, 0) 2
x (weight) 0 x, y 0 B ρ (x) = {y Q n d H (x, y) ρ} x ρ (sphere) 2 δ(x i, y i ) x, y, z Q δ(x, z) = 0 δ(x, z) = 1 x z y x, z x = y, z y x y, z = y x y z δ(x, y)+δ(y, z) 1 = δ(x, z) 3.2 2 Q n C (block code) (codeword) n (code length) (minimum distance) d(c) = min{d H (x, y) x, y C} w(c) = min{w(x) x C} (minimum weight) q = Q r(c) = log q C n (information rate, rate of code) ρ(c) = max{min{d H (x, c) c C} x Q n } (covering radius) ρ x Q n C x Q n ρ {B ρ (c) c C} Q n 3.3 ECC EDC 3 s s (s error detecting code) t t (t error cerrecting code) d(c) d(c) 2s s d(c) 2t + 1 t 4 2t + 1 C Q n (perfect code) x Q n t 2t + 1 t t t eror correcting code 3
5 MDD (minimum distance decoding) 1 (repetition code) Q = {0, 1}, n 0 1 n n 1/n 5 C = {x = (00000), y = (11111)} 5 5 2e + 1 2 MDD 0, 1 MDD ( ) x, y 1 Q 5 5 5 2 = 10 30 2 2 (n ) 2 (parity check code)) Q = {0, 1} Q k 0 1 ( Q k+1 ) 1 ( ) 1 1 ( ) 2 1 EDC k/(k + 1) 1 LAN Q = {0, 1} 2 0, 1 2 ε 1, 0 2 2 n 1 > n 2 n 1 n 2 MLD(maximum likekihood decoding) ε 2 y x d H (x, y) = e x y P (x y) = ε e (1 ε) n e e MDD 4
n 2 f(x), g(x) lim x f(x)/g(x) 0 f(x) g(x) f(n) f(n) n, log n n n! MDD MLD C 4 (1) 4.1 Q ( Q = {0, 1} 2 ) Q GF (q) Q Q = q q p q = p r p Q Q Q = Q {0} Q α( ) Q = {0, 1, α, α 2, α 3,..., α q 2 } F q p F p Q = {0, 1, 2,..., p 1} p 0, 1 Q q = p r (p : prime) F q F p F p [x] r p(x) F p [x]/(p(x)) p(x) x 5
4.2 G H g 1 g 2 h H(g 1 = g 2 h) G H ( ) (1) H = {h 1 = e, h 2, h 3,..., h m } H e h 2 (2) g 2 G g 2 H g 2 H = {g 2 h 1 = g 2, g 2 h 2, g 2 h 3,..., g 2 h m } (3) g 3 G g 3 H g 2 H g 3 H = {g 3 h 1 = g 3, g 3 h 2, g 3 h 3,..., g 3 h m } (4) G (6) l G = H l G = H g 2 H g 3 g l H G/H {e, g 2, g 3,,..., g l } 5 5.1 6 Q n C q ( q = Q ) C Q n C k C (n, k) d (n, k, d) x, y C x y C x y 3 C x, y x y C d H (x, y) = d H (x y, 0) = w(x y) C k C k ( ) {x 1, x 2,..., x k } ( ) c C (c 1 c 2... c k )(c = c 1 x 1 + c 2 x 2 + + c k x k ) 6
k n G G = x 1 x 2.. x k C = {ag a Q k } G C G = (I k, P ) k P k n k P w Q k wg = (w, p) (p n k ) k (information symbols) (parity check symbols) I k 3 5 {(11111), (00000)} G = (11111) 7 {(e i 1) i = 1, 2,..., 7, e i = (0... 010... 0) } G = (I 7 1 T 7 ) 1 7 = (1111111) 1 T 7 7 8 0 1 2 0, 1 C = {(c 1 c 2... c 8 ) c 1 + c 2 + + c 8 = 0} 7 2 C 1, C 2 (equivalent) k n k G = (I k, P ) P C 1, C 2 7
8 C k (systematic) C = q k k k (separable) 9 C (n, k) C (dual code) C = {y Q k x C (< x, y >= 0)} < x, y > C (n, n k) C C = {0} C = C C (self dual) G C n k n H GH T = O (n k) H C < x, y >= xy T a, b Q k x = ag, y = bh < x, y >= ag(bh) T = agh T b T < x, y >= 0 H n k dim{bh b Q k } = n k. C = {bh b Q k }. H x C xh T = O 10 (1) y C x C < x, y >= 0 ( ) C H C (2) C H x Q n xh T x (syndrome) G = (I k P ) C H G = (I k P ) GH T = O H = ( P T I n k ) 4 H R, H P 3 H R = (1 T 4 I 4 ) H P = (11111111) 1 4 = (1111) 5.2 Q n C xh T = yh T (x y)h T = 0 x y + C 8
(1) e 0 = 0 e 1 = (10... 0) e 2 C (e 1 + C) e 3 C (e 1 + C) (e 2 + C),... C Q n (n, k) q n k ( (q = Q ) (2) 1 e 1 = (10... 0), e 2 = (010... 0),..., e n = (0... 01) C 1 2 (3) e n+1 = (110... 0), e n+2 = (0110... 0) 2 (4) C 3 q n k (5) {e 1, e 2,... e r } {s i = e i H T i = 1,..., r} (r = q n k ) s 1, s 2,..., s n H s 1 s 2. = H T s ṇ. C H 10 x C e w = x + e wh T = (x + e)h T = eh T (1) w s = wh T (2) s s = s j (3) s j e j x = w e j MDD 4 2 2 (n, k, d) C P (C) P (C) = d h w ε w (1 ε) n w w=0 9
0 d h w w ε 0 1 1 0 {e j j = 1,..., r} x i {x i + e j j = 1,..., r} e j w x i x i + e j ε w (1 ε) n w w h w h w ε w (1 ε) n w x i P (x i ) C P (C) = 2 k i=1 P (x i ) d h w ε w (1 ε) n w w=0 P (x i ) = 1/2 k C 6 11 G F q (n, k) C G k n G 2 ( ) C (projective code) G C x 1 e( e = ae j = (0... 0a0... 0)) (x + e)g T G ( j ) G G C 1 C C Q = F q k Q k 2 f 1 0 Q k Q k s 1 Q q 1 s 1 = q 1 s 1 f 2 0 s 2 s 2 = q 1 l s i s j = Ø (i j) l (q 1) = q k 1 l = (q k 1)/(q 1). 12 n = (q k 1)/(q 1) F q (n, n k) (Hamming code) 2 F q k {f 1, f 2,..., f n } F q H = (f 1, f 2,..., f n ) C ch T = O 10
1 5 3 1 ECC C H = (f 1 f 2... f n ) f j k 2 c( n ) ch T = 0 c = (c 1 c 2... c n ) c 1 f 1 + c 2 f 2 + + c n f n = 0 f j 0 0 2 c i c j 0, c k = 0(k i, j) c i f i + c j f j = 0 f i, f j 3 3 C (n, n k) n = (q k 1)/(q 1) c 1 Q n B 1 (c) = 1 + n(q 1) = 1 + (q k 1)/(q 1) (q 1) = q k C = q n k q n k q k = q n = Q n. C 1 Q n 1 ECC 5 (1) q = 2 k = 2 n = (2 2 1)/(2 1) = 3 (n, n k, 3) = (3, 1, 3) k = 3 n = (2 3 1)/(2 1) = 7 2 (n, n k, 3) = (7, 4, 3) 001 010 0001 111 011 H = 0110 011 H T = 100 1010 101 101 110 111 11
1 e j eh T H j ( ) q = 2 3 2 2 3 = 8 1 7 2 1 7 1 1 2 e = (0001 000) s = eh T = (100) 2 4. H G 1000 011 0111 100 H = 1011 010 G = 0100 101 0010 110 1101 001 0001 111 1001 110 H = 0100 111 0011 101 k = 4 n = (2 4 1)/(2 1) = 15 2 (15, 11, 3) 1 15 2 (2) q = 3 Q = {0, 1, 2} k = 3 n = (3 3 1)/(3 1) = 13 3 (n, n k, 3) = (13, 10, 3) 11111 11100 100 H = 00111 22211 010 12012 01212 001 G 10000 00000 202 01000 00000 201 00100 00000 220 00010 00000 222 00001 00000 221 G = 00000 10000 210 00000 01000 212 00000 00100 211 00000 00010 022 00000 00001 021 12
13 d (n, k, d) C H(n k n ) n k + 1 n + 1 0 H H =. 0 1... 1 1 1 H T H T =. 1 0... 0 1 (n + 1, k) C C C C n+1 C = {(c 1 c 2... c n c n+1 ) (c 1 c 2... c n ) C c j = 0} 6 d 2 (n, k, d) C C (n + 1, k, d + 1) C C d C d 1 1 d = d + 1 1 1 ECC 2 EDC j=1 6 100 11100 H = 010 01110 001 11010 111 11111 (7, 4, 3) (8, 4, 4) (7, 4, 3) (8, 4, 4) 0000000 1111111 00000000 11111111 1110100 0001011 11101000 11111111 0111010 1000101 01110100 10001011 0011101 1100010 00111010 11000101 1001110 0110001 10011100 01100011 0100111 1011000 01001110 10110001 1010011 0101100 10100110 01011001 1101001 0010110 11010010 00101101 (7, 4, 3) (8, 4, 4) 7 ( majority logic decoding) 13
14 C r < x, y (ν) >= 0 (x C, y (ν) C, 1 ν r) i (orthgonal system with respect to position i) (i) y (ν) = (y (ν) 1 y(ν) 2... y n (ν) ) y (ν) i = 1 (ν = 1, 2,..., r) (ii) j i (1 j n) y (ν) 0 ν (1 ν r) j x = (x 1 x 2... x n ) t t r/2 x e = (e 1 e 2... e n ) < x, y (ν) >=< e, y (ν) > 0 (1 ν r) x i e i = 0 e j 0 j t (ii) < x, y (ν) >=< e, y (ν) > 0 ν (1 ν r) t x i e i 0 e i y (ν) = e i 0 (1 ν r) e j 0 j t 1 < e, y (ν) >= e i + e j y (ν) 0 < x, y (ν) > 0 ν (1 ν r) r (t 1) t r/2 r (t 1) > r {ν < x, y (ν) >= 0} > {ν < x, y (ν) > 0} xi x i 2 i (1 i n) i 7 5 H 1 x 1 + x 2 + x 3 = 0 x 1 + x 4 + x 5 = 0 x 1 + x 6 + x 7 = 0 x 1 x 1 1, 1, 1 x 1 2 0 1 1 2 1 2 ( 2-EDC ) 8 (2) 15 (1) R (ring) (2) R I (ideal) RI I 8 14
(1) Z F F F[x] (2) Z n Z {0, ±n, ±2n, ±3n,... } nz (n) (3) F[x] f(x) F[x] f(x) (f(x)) 16 (1) R p R pr = {px x R} (principal ideal) (2) R R (pricipal ideal ring) (3) I ab I = (a I or b I) (prime ideal) (4) R I (maximal ideal) I S R S S = I S = R (5) (local ring) 17 Z p Z {0, 1, 2,..., p 1} a+b c (mod p), ab d (mod p) Z/pZ Z/(p) ( ) (residual (class) ring) g(x) F[x] g(x) F[x] a(x)+b(x) c(x) (mod g(x)) a(x)b(x) d(x) (mod g(x)) F[x]/(g(x)) (residual polynomial ring) 7 Z, Z/(p), F[x], F[x]/(g(x)) Z Z I p s I s = pq + r (0 r < p) q, r r = s pq I p I r = 0 s = pq 9 9.1 18 C (c 0 c 1... c n 1 ) C = (c n 1 c 0... c n 2 ) C 15
(c i c i+1... c i 1 ) C (i = 0, 1,..., n 1) 9.2 (c 0 c 1... c n 1 ) F n q c 0 + c 1 x + c 2 x 2 + + c n 1 x n 1 F q [x]/(x n 1) C C 8 F n q C C F q[x]/(x n 1) (i) C F q [x]/(x n 1) C F n q c(x) = c 0 +c 1 x+c 2 x 2 +c n 1 x n 1 C C xc(x) = c 0 x + c 1 x 2 + + c n 2 x n 1 + c n 1 x n c n 1 + c 0 x + c 1 x 2 + + c n 2 x n 1 (mod x n 1) C (c n 1 c 0 c 1... c n 2 ) C. C (2) C F n q c(x) C xc(x) C. xi c(x) C (i = 1, 2,... ) a(x) a(x)c(x) C C F q [x]/(x n 1) C g(x) 1 (generator polynomial) g(x) x n 1 x n 1 = g(x)q(x) + r(x) (0 deg(r(x)) < deg(g(x))) x n 1 r(x) C g(x) C r(x) = 0 x n 1 = f 1 (x)f 2 (x)... f t (x) n, k, q x n 1 = f 1 (x)f 2 (x)... f t (x) {f 1 (x), f 2 (x),..., f t (x)} ( ) g(x) = f i1 (x)f i2 (x)... f is (x) deg(g(x)) = n k g(x) k n (1) a = (a 0 a 1... a k 1 ) (2) a k 1 a(x) = a 0 + a 1 x + + a k 1 x k 1 (3) a(x) a(x)g(x) = c 0 + c 1 x + + c n 1 x n 1 c = (c 0 c 1... c n 1 ) 16
9 2 (7, 4) 2 x 7 1 = (x + 1)(x 3 + x 2 + 1)(x 3 + x + 1) g(x) = (x 3 + x 2 + 1) a = (a 0 a 1 a 2 a 3 ) c (a 0 + a 1 x + a 2 x 2 + a 3 x 3 )(1 + x 2 + x 3 ) = a 0 + a 1 x + (a 0 + a 2 )x 2 + + (a 2 + a 3 )x 5 + a 3 x 6 c = (a 0 a 1 (a 0 + a 2 )... (a 2 + a 3 )a 3 ) n k k 1 n k n 1 k (1) a(x) x n k x n k (2) a(x)x n k g(x) q(x), r(x) a(x)x n k = g(x)q(x) + r(x). r(x) d(x) = a(x)x n k r(x) = g(x)q(x). (3) d(x) deg(r(x)) < deg(g(x)) = n k. n k a(x)x n k n k 10 a(x)x 7 4 = (a 0 + a 1 x + a 2 x 2 + a 3 x 3 )x 3 = a 0 x 3 + a 1 x 4 + a 2 x 5 + a 3 x 6 g(x) = x 3 + x 2 + 1 r(x) = (a 0 + a 1 + a 3 )x 2 + (a 1 + a 2 + a 3 )x + (a 0 + a 1 + a 2 ) d = ((a 0 + a 1 + a 3 )(a 1 + a 2 + a 3 )(a 0 + a 1 + a 2 ) a 0 a 1 a 2 a 3 ) 4 3 ( mod 2 ) 9.3 (n, k) C g(x) = g 0 +g 1 x+ +g n k x n k a = (a 0 a 1... a k 1 ) a(x) = a 0 +a 1 x+ +a k 1 x k 1 a(x)g(x) = n 1 l=0 ( l i=0 a ig l i )x l, w = (a 0 g 0 (a 1 g 0 + a 0 g 1 )... a k 1 g n k ) w = ag g 0 g 1... g n k 0 0... 0 G = 0 g 0... g n k 1 g n k 0... 0 0 0...... 0 0 0... g 0 g 1... g n k g(x) x n 1 h(x) = h 0 + h 1 x + + h k x k h(x)g(x) = x n 1 g 0 h l + g 1 h l 1 + + g n k h l n+k = 0 (for l = 0, 1,..., n 1). 0 0... 0 h k... h 1 h 0 0 0... h k... h 1 h 0 0 H =.. h k... h 1 h 0 0... 0 (in F q [x]) 17
GH T = O w = ag wh T = O. H C w(x)h(x) = a(x)g(x)h(x) = 0 h(x) (parity check polynomial) 10 BCH Bose Ray Chaudhurui(1960) Hocquenghem(1959) BCH H = (h 1 h 2... h n ) h i H i (n k ) c = (c 1 c 2... c n ) C ch T = 0 c 1 h T 1 + c 2 h T 2 + + c n h T n = 0 H 9 (n, k, d) C H d 1 d w(c) = d x Q n with (w(x) < d) x C {h 1, h 2,..., h n } d 1 c C (with w(c) = d) c 0 H d 10 H {h 1, h 2,..., h n } d 1 d w(c) = d d 1 c = (c 1 c 2... c n ) w(x) = d 1 x C. d c i1 h T i 1 +c i2 h T i 2 + +c id h T i d = 0 c = (0,..., 0, c i1, 0..., 0, c i2,..., 0) ch T = O c C with w(c) = d Rank(H) d 1 d d 18
19 n, l 1 n β β l, β l+1,..., β l+δ 2 m l (x), m l+1 (x),..., m l+δ 2 (x) G(x) = L.C.M.(m l (x), m l+1 (x),..., m l+δ 2 (x)) F q n δ BCH (BCH code of designed distance δ) l = 1 (narrow sense)bch n = q m 1 (i.e β F q m ) BCH (primitive BCH code) 11 n δ q BCH ( 1 β ) l β l 2 ( 1 β ) l+1 β l+1 2 H =...... ( 1 β ) l+δ 2 β l+δ 2 2 (... ) β l n 1 (... ) β l+1 n 1..... (... ) β l+δ 2 n 1 w(x) v(x) w(x) v(x)g(x) (mod x n 1) w(x) = w 0 + w 1 x + w 2 x 2 + + w n 1 x n 1 w(β i ) = w 0 + w 1 β i ( + w 2 β i ) 2 ( + + wn 1 β i ) n 1 = v(β i )G(β i ) = 0 (w 0 w 1 w 2... w n 1 )(1β i ( β i) 2... ( β i ) n 1 ) T = 0 i = l, l + 1,..., l + δ 2 H (w 0 w 1... w n 1 )H T = 0 H 12 δ BCH δ 10 11 δ 1 n δ 1 0 19
( ) β l j 1 ( ) β l j 2 ( )... β l j δ 1 ( ) β l+1 j 1 ( ) β l+1 j 2 ( )... β l+1 j δ 1 D(j 1 j 2... j δ 1 ) =...... ( ) β l+δ 2 j 1 ( ) β l+δ 2 j 2 ( )... β l+δ 2 j δ 1 1 1... 1 β j 1 β j 2... β j δ 1 = β l(j 1+j 2 + +j δ 1 )...... ( ) β j 1 δ 2 ( ) β j 2 δ 2 ( )... β j δ 1 δ 2 = β l(j1+j2+ +j ( δ 1) β j s β jt) s>t 0 Vandermonde 11 F 2 6 α m 1 (x) = 1 + x + x 6 63 2 BCH (63, 45, 7) BCH G 3 (x) G 3 (x) = L.C.M.(m 1 (x), m 3 (x), m 5 (x)) = (1 + x + x 6 )(1 + x + x 2 + x 4 + x 6 )(1 + x + x 2 + x 5 + x 6 ) = 1 + x + x 2 + x 3 + x 6 + x 7 + x 9 + x 15 + x 16 + x 17 + x 18 63 2 BCH n k t G(x) 63 57 1 G 1 (x) = 1 + x + x 6 51 2 G 2 (x) = G 1 (x)(1 + x + x 2 + x 4 + x 6 ) 45 3 G 3 (x) = G 2 (x)(1 + x + x 2 + x 5 + x 6 ) 39 4 G 4 (x) = G 1 (x)g 3 (x) 36 5 G 5 (x) = G 4 (x)(1 + x 2 + x 3 ) 30 6 G 6 (x) = G 5 (x)(1 + x 2 + x 3 + x 5 + x 6 ) 24 7 G 7 (x) = G 6 (x)(1 + x + 3 +x 4 + x 6 ) 18 10 G 10 (x) = G 7 (x)(1 + x 2 + x 4 + x 5 + x 6 ) 16 11 G 11 (x) = G 10 (x)(1 + x + x 2 ) 10 13 G 13 (x) = G 11 (x)(1 + x + x 4 + x 5 + x 6 ) 7 15 G 15 (x) = G 13 (x)(1 + x + x 3 ) F 2 6 20
m(x) α, α 2, α 4, α 8, α 16, α 32 m 1 (x) = 1 + x + x 6 α 3, α 6, α 12, α 24, α 48, α 33 m 3 (x) = 1 + x + x 2 + x 4 + x 6 α 5, α 10, α 20, α 40, α 17, α 34 m 5 (x) = 1 + x + x 2 + x 5 + x 6 α 7, α 14, α 28, α 56, α 49, α 35 m 7 (x) = 1 + x 3 + x 6 α 9, α 18, α 36 m 9 (x) = 1 + x 2 + x 3 α 11, α 22, α 44, α 25, α 50, α 37 m 11 (x) = 1 + x 2 + x 3 + x 5 + x 6 α 13, α 26, α 52, α 41, α 19, α 38 m 13 (x) = 1 + x + x 3 + x 4 + x 6 α 15, α 30, α 60, α 57, α 51, α 39 m 15 (x) = 1 + x 2 + x 4 + x 5 + x 6 α 21, α 42 m 21 (x) = 1 + x + x 2 α 23, α 46, α 29, α 58, α 53, α 43 m 23 (x) = 1 + x + x 4 + x 5 + x 6 α 27, α 54, α 45 m 27 (x) = 1 + x + x 3 α 31, α 62, α 61, α 59, α 55, α 47 m 31 (x) = 1 + x 5 + x 6 11 2 BCH O(n log 2 2 n) (1) S(x) (2) S(x) σ(x) η(x) (3) σ(x) (4) σ(x) η(x) 2 q (q > 2) F q n 2t + 1 BCH (l = 1 ) β 1 n G(x) v = (v 0 v 1... v n 1 ) v(x) = v 0 + v 1 x + v 2 x 2 + + v n 1 x n 1 w = (w 0 w 1... w n 1 ) w(x) = w 0 + w 1 x + w 2 x 2 + + w n 1 x n 1 e = (e 0 e 1... e n 1 ) e(x) = e 0 + e 1 x + e 2 x 2 + + e n 1 x n 1 E = {i 1, i 2,..., i s e ij 0} (s t) σ(x) = i E (1 βi x) η(x) = i E e iβ i x j E {i} (1 βj x) 21
1. w(x) = v(x) + e(x) w(β j ) = v(β j ) + e(β j ) = c(β j )G(β) + e(β j ) = e(β j ) (j = 1, 2,..., 2t) S j = w(β j ) = e(β j ) (j = 1, 2,..., 2t) E = {i 1, i 2,..., i s } (s < t) S j = e i1 (β j ) i 1 + e i2 (β j ) i 2 + + e is (β j ) i s = e i (β j ) i i E Y l = e il X l = β i l (l = 1, 2,..., s) s S j = Y l X j l (j = 1, 2,..., 2t) l=1 S(x) = S 1 + S 2 x + S 3 x 2 + + S 2t x 2t 1 ( ) 2t = e i (β j ) i x j 1 = 2t e i (β i ) j x j 1 = j=1 i E j=1 i E 1 1 αx = (αx) j S(x) = i E j=0 e i β i 1 β i x (mod x2t ) = s l=1 s l=1 Y l X l 1 X l x (mod x2t ) 2t Y l X j l xj 1 2. E = {i 1, i 2,..., i s } σ(x) = (1 β i1 x)(1 β i2 x)... (1 β is x) = (1 X 1 x)(1 X 2 x)... (1 X s x) j=1 22
σ(x) = 0 x x = X 1 = (β i l ) 1 (l = 1, 2,..., s) σ(x) S(x) σ(x)s(x) = (1 X 1 x)(1 X 2 x)... (1 X s x) l s l=1 = (1 X 2 x)(1 X 3 x)... (1 X s x)y 1 X 1 +(1 X 1 x)(1 X 3 x)... (1 X s x)y 2 X 2 Y l X l 1 X l x (mod x2t ) =. +(1 X 1 x)(1 X 2 x)... (1 X s 1 x)y s X s (mod x 2t ) s s Y l X l (1 X j x) (mod x 2t ) l=1 l=1 j l η(x) η(x) = s Y l X l l=1 s (1 X j x) (mod x 2t ) l=1 j l σ(x)s(x) = η(x) (mod x 2t ) φ(x) σ(x)s(x) + φ(x)x 2t = η(x) S(x) x 2t σ(x), φ(x), η(x) S(x) x 2t η(x) ( ) 3. σ(x) β 1 n β, β 2,..., β n 1 Chien (Chien search) 4. 2 q > 2 13 (Forney ) e il = Y l = η(x 1 l ) σ (X 1 l ) X l = α i l Chien σ (x) σ(x) 23
s η(x) = Y l X l l=1 x = X 1 l η(x 1 l ) = Y l X l s (1 X j x) (mod x 2t ) j=1 j l s (1 X j X 1 l ) (mod x 2t ) j=1 j l Y l = X l η(x 1 l ) s (1 X j X 1 j=1 j l σ(x) x l ) (mod x 2t ) (1) σ (x) = ( X 1 )(1 X 2 x)(1 X 3 x)... (1 X s x) +(1 X 1 x)( X 2 )(1 X 3 x)... (1 X s x).. +(1 X 1 x)... (1 X s 1 x)( X s ) s s = (1 X j x) l=1 x = X 1 l σ (X 1 l X l ) = X l j=1 j l s (1 X j X 1 l ) (mod x 2t ) (2) j=1 j l (2) (1) 12 Reed Solomon BCH Reed Solomon CD DVD 20 F q (q = p r, p : prime) n = q 1 BCH Reed Solomon l = 1 n n α g(x) = d 1 i=1 (x αi ) 14 Reed Solomon (n, k, d) d = n k + 1 24
k, n g(x) n k g(x), xg(x), x 2 g(x),..., x k 1 g(x) Reed Solomon g(x) d 1 d 1 = n k 21 (n, k, d) d = n k + 1 (MDS:Maximum Distance Separable Code) MDS 12 (15, 11, 5) RS g(x) = (x α)(x α 2 )(x α 3 )(x α 4 ) = α 10 + α 3 x + α 6 x 2 + α 13 x 3 + x 4 u(x) = α 5 + αx 2 + α 3 x 10 w(x) v(x) = u(x)g(x) = 1 + α 8 x + α 7 x 3 + α 13 x 4 + α 14 x 5 + αx 6 + α 13 x 10 + α 6 x 11 + α 9 x 12 + αx 13 + α 3 x 14 u = (α 5 0α00 00000 α 3 ) v = (1α 8 0α 7 α 13 α 14 α000 α 13 α 6 α 9 αα 3 ) Q = {0, 1} F 2 4 2 α, α 2,... (0010), (0100),... RS F 2 4 ( x 4 + x + 1) 0 0 0000 1 1 0001 α x 0010 α 2 x 2 0100 α 3 x 3 1000 α 4 x 4 x + 1 0011 α 5 x 2 + x 0110 α 6 x 3 + x 2 1100 α 7 x 3 + x + 1 1011 α 8 x 2 + 1 0101 α 9 x 3 + x 1010 α 10 x 2 + x + 1 0111 α 11 x 3 + x 2 + x 1110 α 12 x 3 + x 2 + x + 1 1111 α 13 x 3 + x 2 + 1 1101 α 14 x 3 + 1 1001 25
13 2 ECC w = (1α 8 0α 11 α 13 α 14 α000 α 2 α 6 α 9 αα 3 ) w(x) = 1 + α 8 x + α 11 x 3 + α 13 x 4 + α 14 x 5 + αx 6 + α 2 x 10 + α 6 x 11 + α 9 x 12 + αx 13 + α 3 x 14 1. g(x) α, α 2, α 3, α 4 w(x) S 1 = w(α) = α 2, S 2 = w(α 2 ) = α 9, S 3 = w(α 3 ) = α 13, S 4 = w(α 4 ) = α 6, S(x) = α 2 + α 9 x + α 13 x 2 + α 6 x 3 2. x 4 S(x) σ(x)s(x) + φ(x)x 4 = η(x) η(x) = α 2 + α 4 x σ(x) = 1 + α 12 x + α 13 x 2 3. F 2 4 α, α 2,..., α 14 σ(x) 0 σ(α 5 ) = σ(α 12 ) = 0 α 5 = α 10, α 12 = α 3. w(x) x 3 x 10 4. σ(x) σ (x) = 2 α 13 x + 1 α 12 α 12 (mod 2) Y 3 = α4 (α 12 ) + α 2 α 12 = α 8 Y 10 = α4 (α 5 ) + α 2 α 12 = α 14 e(x) = α 8 x 3 + α 14 x 10 ˆv(x) = w(x) e(x) = v(x) 13 (3) 22 S v B S ( (block) ) (i) B B B = k. (ii) T S T = t T B B λ (S, B) t design( t (v, k.λ) ) S (point) λ = 1 (Steiner system) 26
t design t design incidence S = {a 1, a 2,..., a s } B = {B 1, B 2,..., B b } incidence A s b (i, j) a i B j 1, 0 j B j 1 B j s 3 B B incidence 27