A Short Course at Tamkang University Taipei, Taiwan, R.O.C. March 7-9 2006 An Application of Coding Theory into Experimental Design Shigeichi Hirasawa Department of Industrial and Management Systems Engineering, School of Science and Engineering , Waseda University No.1 序論 １．Introduction No.2 1.1 Abstract 実験計画 符号理論 Experimental Design Coding Theory 直交配列 Orthogonal Arrays (OAs) Error-Correcting close relation Codes (ECCs) 直交表 L８ table of OA L8 etc. Hamming codes, BCH codes RS codes etc. ・ relations between OAs and ECCs ・ the table of OAs and Hamming codes ・ the table of OAs + allocation No.3 1.2 Outline 序論 １．Introduction 準備 ２．Preliminary ３．Relation between ECCs and OAs 結論 ４．Conclusion No.4 準備 2．Preliminary No.5 実験計画法 Experimental Design No.6 ２．１ Experimental Design (実験計画法) 2.1.1 Experimental Design Ex.) 要因A ・ Factor A (materials) A0（A company），A1（B company） 要因B ・Factor B （machines） B0（new），B1（old） a Ratio of Defective Products 要因C ・Factor C （temperatures） C0（100℃），C1（200℃） ・How the level of factors affects a ration of defective products ? ・Which is the best combination of levels ? No.7 完全配列 Complete Array experiments with all combination of levels Experiment ① Ａ ０ Ｂ ０ Ｃ ０ ② ０ ０ １ ③ ０ １ ０ ④ ０ １ １ ⑤ １ ０ ０ ⑥ １ ０ １ ⑦ １ １ ０ ⑧ １ １ １ 実験 experiment with A0,B0,C0 No.8 直交配列 Orthogonal Array (OA) : OA(M, n, s,τ) (s=2) 部分空間 subset (subspace) of complete array Experiment ① Ａ ０ Ｂ ０ Ｃ ０ ② ０ １ １ ③ １ ０ １ ④ １ １ ０ 011 001 101 111 000 100 010 110 強さ strength τ=2 every 2 columns contains each 2tuple exactly same times as row No.9 直交配列 Orthogonal Array (OA) : OA(M, n, s,τ) (s=2) 部分空間 subset (subspace) of complete array Experiment ① Ａ ０ Ｂ ０ Ｃ ０ ② ０ １ １ ③ １ ０ １ ④ １ １ ０ 011 001 101 111 000 100 010 110 強さ strength τ=2 every 2 columns contains each 2tuple exactly same times as row No.10 直交配列 Orthogonal Array (OA) : OA(M, n, s,τ) (s=2) 部分空間 subset (subspace) of complete array Experiment ① Ａ ０ Ｂ ０ Ｃ ０ ② ０ １ １ ③ １ ０ １ ④ １ １ ０ 011 001 101 111 000 100 010 110 強さ strength τ=2 every 2 columns contains each 2tuple exactly same times as row No.11 直交配列 Orthogonal Array (OA) : OA(M, n, s,τ) (s=2) 部分空間 subset (subspace) of complete array Experiment ① Ａ ０ Ｂ ０ Ｃ ０ ② ０ １ １ ③ １ ０ １ ④ １ １ ０ 011 001 101 111 000 100 010 110 強さ strength τ=2 every 2 columns contains each 2tuple exactly same times as row No.12 2.1.2 Construction Problem of OAs 因子数 the number of factors n=3 Parameters of OAs A B C ① ０ ０ ０ ② ０ １ ③ １ ０ １ 実験回数 １ the number ④ １ １ ０ 因子数 ・the number of factors n 実験回数 ・the number of runs M 強さ ・strength τ=2t of runs M=4 trade off this can treat t-th order interaction effect 強さ strength τ=2 Construction problem of OAs is to construct OAs with as few as possible number of runs, given the number of factors and strength (n,τ → min M) No.13 2.1.3 Generator Matrix (生成行列) Generator Matrix of an OA : G Ex.) orthogonal array ｛ 000 , 011 , 101 , 110 ｝ A B C A B C ０ １ １ （○，○，○） = （□，□） OA １ ０ １ each k-tuple (k=2) based on｛0,1｝2 2k=M generator matrix G To construct OAs is to construct generator matrix No.14 2.1.3 Generator Matrix (生成行列) Generator Matrix of an OA : G Ex.) orthogonal array ｛ 000 , 011 , 101 , 110 ｝ A B C A B C ０ １ １ （ ０， ０， ０ ） = （ ０，０ ） OA １ ０ １ each k-tuple (k=2) based on｛0,1｝2 2k=M generator matrix G To construct OAs is to construct generator matrix No.15 2.1.3 Generator Matrix (生成行列) Generator Matrix of an OA : G Ex.) orthogonal array ｛ 000 , 011 , 101 , 110 ｝ A B C A B C ０ １ １ （ ０， １， １ ） = （ １，０ ） OA １ ０ １ each k-tuple (k=2) based on｛0,1｝2 2k=M generator matrix G To construct OAs is to construct generator matrix No.16 2.1.3 Generator Matrix (生成行列) Generator Matrix of an OA : G Ex.) orthogonal array ｛ 000 , 011 , 101 , 110 ｝ A B C A B C ０ １ １ （ １， ０， １ ） = （ ０，１ ） OA １ ０ １ each k-tuple (k=2) based on｛0,1｝2 2k=M generator matrix G To construct OAs is to construct generator matrix No.17 2.1.3 Generator Matrix (生成行列) Generator Matrix of an OA : G Ex.) orthogonal array ｛ 000 , 011 , 101 , 110 ｝ A B C A B C ０ １ １ （ １， １， ０ ） = （ １，１ ） OA １ ０ １ each k-tuple (k=2) based on｛0,1｝2 2k=M generator matrix G To construct OAs is to construct generator matrix No.18 Parameters of OAs and Generator Matrix : G Ex.) orthogonal arrays ｛ 000 , 011 , 101 , 110 ｝ 3 ・the number of factors n=3 ・the number of runs M=4 ・strength τ=2 G= the number of factors n=3 ０ １ １ １ ０ １ 2 the number of runs M=22 any 2 columns are linearly independent strength τ=2 No.19 Parameters of OAs and Generator Matrix Ex.) orthogonal arrays ｛ 000 , 011 , 101 , 110 ｝ 3 ・the number of factors n=3 ・the number of runs M=4 G= ・strength τ=2 the number of factors n=3 ０ １ １ １ ０ １ 2 the number of runs M=22 any 2 columns are linearly independent 0 1 0 ≠ + 1 0 0 strength τ=2 No.20 Parameters of OAs and Generator Matrix Ex.) orthogonal arrays ｛ 000 , 011 , 101 , 110 ｝ 3 ・the number of factors n=3 ・the number of runs M=4 G= ・strength τ=2 the number of factors n=3 ０ １ １ １ ０ １ 2 the number of runs M=22 any 2 columns are linearly independent 0 1 0 ≠ + 1 1 0 strength τ=2 No.21 Parameters of OAs and Generator Matrix Ex.) orthogonal arrays ｛ 000 , 011 , 101 , 110 ｝ 3 ・the number of factors n=3 ・the number of runs M=4 G= ・strength τ=2 the number of factors n=3 ０ １ １ １ ０ １ 2 the number of runs M=22 any 2 columns are linearly independent 1 1 0 ≠ + 0 1 0 strength τ=2 No.22 OAs and ECCs [HSS ‘99] n G= m any τ=2t columns are linearly independent OAs with generator matrix G ECCs with parity check matrix G ・the number of factors n ・code length n ・the number of runs M=2m ・the number of information symbols k=n-m ・strength τ=2t this can treat all t-th order interaction effect ・minimum distance d=2t + 1 this can correct all t errors No.23 Coding Theory No.24 ２．２ Coding Theory （符号理論） 2.2.1 Coding Theory techniques to achieve reliable communication over noisy channel (ex. CD, cellar phones etc.) Ex.) 符号語 codewords 0 → 000 1 → 111 noise 0 000 encoder 100 channel 0 decoder No.25 誤り訂正符号 Error-Correcting Codes 部分空間 subspace of linear vector space Ex.) 011 001 ０ ０００ １ １１１ 101 111 000 符号語 codeword 100 010 110 No.26 2.2.2 Construction Problem of ECCs : (n, k, d) code the number of information symbols k=1 Parameters of ECCs 符号長 ・code length n 情報記号数 ・the number of information symbols k ０ ０００ １ １１１ trade off 最小距離 ・minimum distance d=2t + 1 this can correct t errors minimum distance d=3 this can correct 1 error Construction problem of ECCs is to construct ECCs with as many as possible number of information symbols, given the code length and minimum distance （n, d → max k） No.27 2.2.3 Parity Check Matrix Parity Check Matrix of ECCs Ex.) (3,1,3) code ｛ 000 , 111 ｝ 0 1 1 parity check matrix H = 1 0 1 codeword 0 1 1 1 0 1 0 0 0 = 0 0 0 1 1 1 0 1 1 1 1 = 0 0 HxT=0 To construct of linear codes is to construct parity check matrix No.28 Parameters of ECCs and Parity Check Matrix Ex.) code length n=3 (3,1,3) code ｛ 000 , 111 ｝ ・code length n=3 ・the number of information symbols k=1 the number of information symbols k=3 - 2 3 ０ １ １ H= １ ０ １ 2 ・minimum distance d=3 any d-1=2 columns are linearly independent minimum distance d=2 +1 No.29 OAs and ECCs [HSS ‘99] n G= m any d-1=2t columns are linearly independent OAs with generator matrix G ECCs with parity check matrix G ・the number of factors n ・code length n ・the number of runs M=2m ・the number of information symbols n-m ・strength τ=2t this can treat all t order interaction effect ・minimum distance d=2t + 1 this can correct all t errors No.30 関係 3．Relation Between OAs and ECCs No.31 3.1 OAs and ECCs G= OA with generator matrix G ECC with parity check matrix G 010 110 011 001 101 111 000 100 １ ０ １ 011 001 101 ０ １ １ 111 000 100 010 110 No.32 OAs and ECCs [HSS ‘99] n G= m any 2t columns are linearly independent OAs with generator matrix G ECCs with parity check matrix G ・the number of factors n ・code length n ・the number of runs M=2m ・the number of information symbols k=n-m ・strength τ=2t this can treat all t order interaction effect ・minimum distance d=2t + 1 this can correct all t errors No.33 直交表 Table of OAs and Hamming Codes No.34 3.2 Matrix in which any 2 columns are linearly independent ① an OA with strength τ=2，a linear code with minimum distance 0 0 1 1 ・・・ 1 1 n=7 ０ ０ ０ １ １ １ １ G= ０ １ １ ０ ０ １ １ １ ０ １ ０ １ ０ １ 3 No.35 3.2 Matrix in which any 2 columns are linearly independent ① an OA with strength τ=2，a linear code with minimum distance 0 0 1 1 ・・・ 1 1 n=7 ０ ０ ０ １ １ １ １ G= ０ １ １ ０ ０ １ １ １ ０ １ ０ １ ０ １ 0 0 1 0 + 1 0 0 ≠ 0 0 3 No.36 3.2 Matrix in which any 2 columns are linearly independent ② an OA with strength 2，a linear code with minimum distance 0 0 1 1 ・・・ 1 1 n=7 ０ ０ ０ １ １ １ １ G= ０ １ １ ０ ０ １ １ 3 １ ０ １ ０ １ ０ １ ・table of OA L8 the number of factors 7，the number of runs 8，strength 2 ・（7,4,3）Hamming code code length 7, the number of information symbols 4, minimum distance 3 No.37 3.2 Matrix in which any 2 columns are linearly independent ① an OA with strength 2，a linear code with minimum distance ０ ０ ０ ０ ０ ０ ０ １ １ １ １ １ １ １ １ G= ０ ０ ０ １ １ １ １ ０ ０ ０ ０ １ １ １ １ ０ １ １ ０ ０ １ １ ０ ０ １ １ ０ ０ １ １ 4 １ ０ １ ０ １ ０ １ ０ １ ０ １ ０ １ ０ １ ・table of OA L16 the number of factors 15，the number of runs 16，strength 2 ・（15,11,3）Hamming code code length 15, the number of information symbols 11, minimum distance 3 No.38 直交表 割付 Table of OAs + allocation No.39 3.3 Example （Allocation to L8） L8 線点図 Linear Graph 1 2 3 4 5 6 7 ① 0 0 0 0 0 0 0 ② 0 0 0 1 1 1 1 ③ 0 1 1 0 0 1 1 ④ 0 1 1 1 1 0 0 ⑤ 1 0 1 0 1 0 1 ⑥ 1 0 1 1 0 1 0 ⑦ 1 1 0 0 1 1 0 ⑧ 1 1 0 1 0 0 1 １ ３ ２ ７ ５ ６ ４ No.40 3.3 Example （Allocation to L8） L8 A B C D E 線点図 Linear Graph factor A 1 2 3 4 5 6 7 ① 0 0 0 0 0 0 0 ② 0 0 0 1 1 1 1 ③ 0 1 1 0 0 1 1 ④ 0 1 1 1 1 0 0 ⑤ 1 0 1 0 1 0 1 ⑥ 1 0 1 1 0 1 0 ⑦ 1 1 0 0 1 1 0 ⑧ 1 1 0 1 0 0 1 １ E A×B ３ ２ B ７ ５ ６ D ４ C No.41 3.4 Construction Problem（General Case） Ex.) factors A,B,C,D,E Special Case ・the number of factors n=5 ・strength τ=4 an OA with as few as possible of runs this can treat all L=2 order interaction effects（A×B,A×C,・・・,D×E） General Case ・the number of factors n=5 ・ ？ an OA with as few as possible of runs this can treat partial 2order interaction effects （A×B） No.42 3.5 Generator Matrix（General Case） Ex.) factors A,B,C,D,E Special Case（A×B,A×C,・・・,D×E） generator matrix G = A B C D E any 4 columns are linearly independent General Case（A×B） generator matrix G = A B C D E ・ any 4 columns are linearly independent ・any 3 columns which contain A, B are linearly independent No.43 3.6 Meaning of allocation Generator Matrix of L8 Projective Geometry （Linear Graph） 001 0 0 0 1 1 1 1 0 1 1 0 0 1 1 011 101 111 1 0 1 0 1 0 1 010 110 100 No.44 3.7 Meaning of allocation Generator Matrix of L8 A B C D E Projective Geometry （Linear Graph） factor A 001 A×B 0 0 0 1 1 1 1 0 1 1 0 0 1 1 011 E 111 1 0 1 0 1 0 1 010 if C, D, E are not allocated to this column, any 3 columns which contain A, B are linearly independent 101 B 110 100 D C No.45 4．Conclusion No.46 4.1 Conclusion １．Construction problems ECCs : n, d → max k OAs : n, τ → min M ２．A generator matrix of OAs is equal to a parity check matrix of ECCs. ３．Relations of each columns in construction problems of OAs are more complicate than in those of ECCs. No.47 参考文献） [Taka79] I.Takahashi, “Combinatorial Theory and its Applications (in Japanese), ” Iwanami shoten, Tokyo, 1979 [HSS99] A.S.Hedayat，N.J.A.Sloane，and J.Stufken， “ Orthogonal Arrays : Theory and Applications，” Springer， New York，1999． [SMH05] T.Saito, T.Matsushima, and S.Hirasawa, “A Note on Construction of Orthogonal Arrays with Unequal Strength from Error-Correcting Codes,” to appear in IEICE Trans. Fundamentals. [MW67] B.Masnic, and J.K.Wolf, “On Linear Unequal Error protection Codes,” IEEE Trans. Inform Theory, Vol.IT-3, No.4, pp.600-607, Oct.1967
© Copyright 2024 ExpyDoc
