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
(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
(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
(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
(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
(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
H = 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1 An example of a code-word : an information word s = (1 0 0 1) x = sg = (1 0 0 1 1 0 0) I 7
H = 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 x = (1 0 0 1 1 0 0) 1 y = (1 0 1 1 1 0 0) 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 = (1 0 0 1 1 0 0) (1 0 0 1) I 8
(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
(automorphisms of a code) To be more efficient, more symmetric!! symmetry of a code automorphisms of a code ( ) I 10
(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
(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
(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
(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
(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
(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
(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
(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
(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
(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
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 9 + + X + 1) X 13 1 = (X + 1)(X 12 + X 11 + + 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 17 + + X + 1) I 21
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 27 + + 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 35 + + X + 1) I 22
(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
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 1 2 0 X l 1 X 1 repetition 1 l l 1 X l 1 (0) 0 I 24 2
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