(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

Size: px

Start display at page:

Download "(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"

ゆずさしげまつ
5 years ago
Views:

1 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 of at least 3 vectors. H := (h 1 h n ) M(c, n; F q ) C : the code with check matrix H Hamming code d = 3, t = 1 I 1

2 (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 dependent) (H ) I 2

3 (1) 3 2 Hamming H [7, 4]- ( ) H (2) H ( GH T = O ) G (3) w(e) = 1 e F 2 7 eh T (4) x H 1 ( ) y F 2 7 yh T x H I 3

4 (systematic codes) C : a systematic code ( ) C has a generator matrix G of the form G = (I k P), where P M(k, n k; F q ). G = (I k P) : gen.matrix (P M(k, n k; F q )) H = ( P T I n k ) : check matrix GH T = O I 4

5 (systematic codes) G = (I k P), H = ( P T I n k ) ϕ G : F q k C V = F q n s = (s 1,..., s k ) sg = (s sp) s : information symbols( ) sp : check symbols( ) Thm Any linear code is equivalent to a systematic code. I 5

6 (equivalence of codes) Two codes C, C V are equivalent ( ) f Aut(V, d) : C = f(c) Equivalent codes have the same properties w.r.t. error-correction. (the dimension, the minimum distance) Good representatives of equivalent classes = standard forms of linear codes = systematic codes I 6

7 H = G = An example of a code-word : an information word s = ( ) x = sg = ( ) I 7

8 H = x = ( ) 1 y = ( ) e eh T e 1 (1 1 1) e 2 (1 1 0) e 3 (1 0 1) e 4 (0 1 1) e 5 (1 0 0) e 6 (0 1 0) e 7 (0 0 1) yh T = (1 0 1) = e 3 H T y e 3 = ( ) ( ) I 8

9 (automorphisms of a code) To construct a code with many code-words systematically, the code-words of C should be distributed as equally as possible. Use mathematical structures (symmetry) of V = T n invariant under translation ( ) linear codes ( ) I 9

10 (automorphisms of a code) To be more efficient, more symmetric!! symmetry of a code automorphisms of a code ( ) I 10

11 (linear isometry) V = (V, d) : a metric linear space ( ) f : V V : a linear isometry (, isometric linear autom.) f : a linear autom. preserving distances (d(f(x), f(y)) = f(x, y)) For d : Hamming distance, f : a linear autom. preserving weights (w(f(x)) = w(x)) I 11

12 (linear isometry) Aut(V, d) : the group consisting of all the linear isometries of V = (V, d) Aut(V, d) is generated by the following two kinds of autom s: permutations of components ( ( ) ) non-zero const. multipl ns of a component ( ) Aut(V, d) = S n F q = S n (F q ) n I 12

13 (equivalence of codes) Two codes C, C V are equivalent ( ) f Aut(V, d) : C = f(c) Equivalent codes have the same properties w.r.t. error-correction. (the dimension, the minimum distance) I 13

14 (automorphisms of a code) C : a linear code V = F q n f : C (automorphism) f Aut(V, d) s.t. f(c) = C Aut(C) := {f Aut(V, d) f(c) = C} : C (the automorphism group of C) Aut(C) Aut(V, d) = S n F q I 14

15 (automorphisms of a code) Aut(C) Aut(V, d) = S n F q In particular, when q = 2, Aut(C) Aut(V, d) = S n (linear representations of symmetric groups over finite fields) A typical case: σ = (1 2 n) Aut(C) (cyclic codes) I 15

16 (cyclic codes) A linear code C is a cyclic code ( ) σ = (1 2 n) Aut(C) ( (c 0, c 1,..., c n 1 ) C ) = (c n 1, c 0,..., c n 2 ) C I 16

17 (cyclic codes) σ = (1 2 n) S n, σ n = 1 F q [ σ ] F q [X]/(X n 1) =: R V = F q n V : a free R-module of rank 1 V = F n q R (1, 0,..., 0) 1 (c 0, c 1,..., c n 1 ) c 0 + c 1 X + + c n 1 X n 1 I 17

18 (cyclic codes) V : a free R-module of rank 1 C C : cyclic C : a sub-r-module of V under identification V R C : an ideal of R R : a commutative ring I : an ideal of R { 0 I a, b I : a + b I a I, r R : ra I I 18

19 (cyclic codes) C : a cyclic code an ideal I of R = F q [X]/(X n 1) an ideal Ĩ of F q[x] s.t. Ĩ (Xn 1) ( f R : Ĩ = (f), for F q[x] is a PID) f F q [X] s.t. f (X n 1) Classification of cyclic codes decomposition of X n 1 F q [X] I 19

20 (cyclic codes) For a decompsition X n 1 = g(x)h(x) F q [X], C := gr : a cyclic code F q [X]/(h) = {c(x) R h(x)c(x) = 0 in R} g : (generator polynomial) h : (check polynomial) How decomposes X n 1 F q [X]? Galois Theory of finite fields I 20

21 X l 1 F q [X] (irreducible decomposition) q = 2, n = l : an odd prime X 3 1 = (X + 1)(X 2 + X + 1) X 5 1 = (X + 1)(X 4 + X 3 + X 2 + X + 1) X 7 1 = (X + 1)(X 3 + X + 1)(X 3 + X 2 + 1) X 11 1 = (X + 1)(X 10 + X X + 1) X 13 1 = (X + 1)(X 12 + X X + 1) X 17 1 = (X + 1)(X 8 + X 5 + X 4 + X 3 + 1) (X 8 + X 7 + X 6 + X 4 + X 2 + X + 1) X 19 1 = (X + 1)(X 18 + X X + 1) I 21

22 X l 1 F q [X] (irreducible decomposition) X 23 1 = (X + 1) (X 11 + X 9 + X 7 + X 6 + X 5 + X + 1) (X 11 + X 10 + X 6 + X 5 + X 4 + X 2 + 1) X 29 1 = (X + 1)(X 28 + X X + 1) X 31 1 = (X + 1)(X 5 + X 2 + 1)(X 5 + X 3 + 1) (X 5 + X 3 + X 2 + X + 1) (X 5 + X 4 + X 2 + X + 1) (X 5 + X 4 + X 3 + X + 1) (X 5 + X 4 + X 3 + X 2 + 1) X 37 1 = (X + 1)(X 36 + X X + 1) I 22

23 (cyclic codes) For a decompsition X n 1 = g(x)h(x) F q [X], C = (g) : a cyclic code V = F q [X]/(X l 1) g : (generator polynomial) h : (check polynomial) n = dim Fq V = l k = dim Fq C = deg h = l deg g I 23

24 X l 1 X l 1 = g(x)h(x) F q [X] g(x) C = (g) k d t 1 V l 1 0 X 1 parity-check l X l 1 X 1 repetition 1 l l 1 X l 1 (0) 0 I 24 2

25 X l 1 X l 1 = g(x)h(x) F q [X] C = (g) : V = F q [X]/(X l 1) X l 1 ( ) I 25

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

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