one way two way (talk back) (... ) C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1

Size: px

Start display at page:

Download "one way two way (talk back) (... ) C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1"

あきみたもん
5 years ago
Views:

1 one way two way (talk back) (... ) C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1

2 ( (coding theory)) (convolution code) (block code), 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

3 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) 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

4 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 MDD 0, 1 MDD ( ) x, y 1 Q = (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, 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

5 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

6 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 } 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 c k x k ) 6

7 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 = ( ) } G = (I 7 1 T 7 ) 1 7 = ( ) 1 T , 1 C = {(c 1 c 2... c 8 ) c 1 + c c 8 = 0} 7 2 C 1, C 2 (equivalent) k n k G = (I k, P ) P C 1, C 2 7

8 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 = ( ) 1 4 = (1111) 5.2 Q n C xh T = yh T (x y)h T = 0 x y + C 8

9 (1) e 0 = 0 e 1 = ( ) 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 = ( ), e 2 = ( ),..., e n = ( ) C 1 2 (3) e n+1 = ( ), e n+2 = ( ) 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 (n, k, d) C P (C) P (C) = d h w ε w (1 ε) n w w=0 9

10 0 d h w w ε {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

11 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 c n f n = 0 f j 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) H = H T =

12 1 e j eh T H j ( ) q = = e = ( ) s = eh T = (100) 2 4. H G H = G = H = k = 4 n = (2 4 1)/(2 1) = 15 2 (15, 11, 3) (2) q = 3 Q = {0, 1, 2} k = 3 n = (3 3 1)/(3 1) = 13 3 (n, n k, 3) = (13, 10, 3) H = G G =

13 13 d (n, k, d) C H(n k n ) n k + 1 n H H = H T H T = (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 ECC 2 EDC j= H = (7, 4, 3) (8, 4, 4) (7, 4, 3) (8, 4, 4) (7, 4, 3) (8, 4, 4) 7 ( majority logic decoding) 13

14 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 ( 2-EDC ) 8 (2) 15 (1) R (ring) (2) R I (ideal) RI I 8 14

15 (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 C (c 0 c 1... c n 1 ) C = (c n 1 c 0... c n 2 ) C 15

16 (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 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 c n 2 x n 1 + c n 1 x n c n 1 + c 0 x + c 1 x 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

17 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 (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 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 G = 0 g 0... g n k 1 g n k 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 g n k h l n+k = 0 (for l = 0, 1,..., n 1) h k... h 1 h h k... h 1 h 0 0 H =.. h k... h 1 h (in F q [x]) 17

18 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 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 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 (... ) β 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 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 δ δ 1 n δ

20 ( ) β 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 δ β 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 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 BCH n k t G(x) G 1 (x) = 1 + x + x 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 ) G 10 (x) = G 7 (x)(1 + x 2 + x 4 + x 5 + x 6 ) G 11 (x) = G 10 (x)(1 + x + x 2 ) 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

21 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 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 v n 1 x n 1 w = (w 0 w 1... w n 1 ) w(x) = w 0 + w 1 x + w 2 x w n 1 x n 1 e = (e 0 e 1... e n 1 ) e(x) = e 0 + e 1 x + e 2 x 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

22 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 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 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

23 σ(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

24 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

25 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α α 3 ) v = (1α 8 0α 7 α 13 α 14 α000 α 13 α 6 α 9 αα 3 ) Q = {0, 1} F α, α 2,... (0010), (0100),... RS F 2 4 ( x 4 + x + 1) α x 0010 α 2 x α 3 x α 4 x 4 x α 5 x 2 + x 0110 α 6 x 3 + x α 7 x 3 + x α 8 x α 9 x 3 + x 1010 α 10 x 2 + x α 11 x 3 + x 2 + x 1110 α 12 x 3 + x 2 + x α 13 x 3 + x α 14 x

26 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 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 σ(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

27 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

(check matrices and minimum distances) H : a check matrix of C the minimum distance d = (the minimum # of column vectors of H which are linearly depen

(check matrices and minimum distances) H : a check matrix of C the minimum distance d = (the minimum # of column vectors of H which are linearly depen Hamming (Hamming codes) c 1 # of the lines in F q c through the origin n = qc 1 q 1 Choose a direction vector h i for each line. No two vectors are colinear. A linearly dependent system of h i s consists