The 2006 International Seminar of E-commerce
Academic and Application Research
Tainan, Taiwan, R.O.C. March 1-2,2006
An Application of Coding Theory into
Experimental Design
- Construction Methods for Unequal Orthogonal Arrays -
Shigeichi Hirasawa
Department of Industrial and
Management Systems Engineering,
School of Science and Engineering ,
Waseda University
No.1
序論
1.Introduction
No.2
1.1 Abstract
実験計画
符号理論
Experimental Design
Coding Theory
直交配列
Orthogonal Arrays
(OAs)
Error-Correcting
close relation Codes (ECCs)
直交表 L8
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
序論
1.Introduction
準備
2.Preliminary
3.Relation between ECCs and OAs
4.Unequal Error Protection Codes and OAs
5.Examples of OAs with Unequal Strength
結論
6.Conclusion
No.4
準備
2.Preliminary
No.5
実験計画法
Experimental Design
No.6
2.1 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 ①
A
0
B
0
C
0
②
0
0
1
③
0
1
0
④
0
1
1
⑤
1
0
0
⑥
1
0
1
⑦
1
1
0
⑧
1
1
1
実験
experiment
with A0,B0,C0
No.8
直交配列
Orthogonal Array (OA) : OA(M, n, s,τ) (s=2)
部分空間
subset (subspace) of complete array
Experiment ①
A
0
B
0
C
0
②
0
1
1
③
1
0
1
④
1
1
0
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 ①
A
0
B
0
C
0
②
0
1
1
③
1
0
1
④
1
1
0
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 ①
A
0
B
0
C
0
②
0
1
1
③
1
0
1
④
1
1
0
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 ①
A
0
B
0
C
0
②
0
1
1
③
1
0
1
④
1
1
0
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
①
0
0
0
②
0
1
③
1
0
1 実験回数
1 the number
④
1
1
0
因子数
・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
0 1 1
(○,○,○) = (□,□)
OA
1 0 1
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
0 1 1
( 0, 0, 0 ) = ( 0,0 )
OA
1 0 1
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
0 1 1
( 0, 1, 1 ) = ( 1,0 )
OA
1 0 1
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
0 1 1
( 1, 0, 1 ) = ( 0,1 )
OA
1 0 1
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
0 1 1
( 1, 1, 0 ) = ( 1,1 )
OA
1 0 1
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
0 1 1
1 0 1
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
0 1 1
1 0 1
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
0 1 1
1 0 1
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
0 1 1
1 0 1
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
2.2 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
0
000
1
111
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
0
000
1
111
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
0 1 1
H=
1 0 1
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
1 0 1
011
001
101
0 1 1
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
0 0 0 1 1 1 1
G=
0 1 1 0 0 1 1
1 0 1 0 1 0 1
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
0 0 0 1 1 1 1
G=
0 1 1 0 0 1 1
1 0 1 0 1 0 1
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
0 0 0 1 1 1 1
G=
0 1 1 0 0 1 1
3
1 0 1 0 1 0 1
・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
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
G=
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
4
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
・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
1
3
2
7
5
6
4
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
1
E
A×B
3
2
B
7
5
6
D
4
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.Unequal Error Protection
Codes and OAs
No.46
4.1 Unequal Error Protection Codes
Unequal Error Protection Codes
this is used to send
numerical data
Error-Correcting Codes
error protection levels are equal in each position of a codeword
(○ , ○ , ○)
codeword
error protection level t in each position
t
t
→ minimum distance d=2t +1
t
Unequal Error Protection Codes
error protection levels are unequal in each position of a codeword
(○ , ○ , ○)
t+1 t
t
codeword
error protection level (t1,t2,t3) = (t+1, t, t)
→ separation di=2ti +1
No.47
Construction Problem of Unequal Error Protection Codes
Error-Correcting Codes
・code length n
・minimum distance d
code with as many as possible
number information symbols M
Unequal Error Protection Codes
・code length n
・minimum distance
(d1,d2,・・・,dn)
code with as many as possible
number information symbols M
No.48
Unequal Error Protection Codes and Parity Check Matrix
Error-Correcting Codes
minimum distance d
H=
1 ・・・ i ・・・ n
any d-1 columns are linearly independent
Unequal Error Protection Codes
separation
(d1 , ・・・ , di , ・・・ , dn )
H=
1 ・・・ i ・・・ n
any di-1 columns that contain i-th column are
linearly independent
No.49
4.2 Classification of OA
① OA(General Case)
② OA with unequal strength (τ1, τ2,・・・, τn)
→ this can treat all τi/2 = ti-th order interaction effect that contain i-th factor
③ OA with (equal) strength τ
→ this can treat all τ/2 = t-th order interaction effect
Ex.) (factor A,B,C)
① A×B
② A×B, A×C
③ A×B, A×C, B×C
①
②
③
No.50
4.2 Classification of OA
① OA(General Case)
② OA with unequal strength (τ1, τ2,・・・, τn)
Unequal Protection Codes
③ OA with (equal) strength τ
Error-Correcting Codes
①
Unequal Protection Codes
Error-Correcting Codes
②
③
No.51
5. Examples of OAs with
unequal strength
No.52
OAs from ECC and Unequal Error Protection Codes
OAs from BCH Codes
・number of factors 63
・number of experiments 218
・strength 6
→this can treat all 3-rd order interaction effect
OAs from Unequal Error Protection Codes
・ number of factors 63
・ number of experiments 212
・ strength (6, 6, ・・・, 6, 4, 4, ・・・, 4)
7
→this can treat partial 3-rd order interaction effect
No.53
6.Conclusion
No.54
6.1 Conclusion
1.Construction problems
ECCs : n, d → max k
OAs
: n, τ → min M
2.A generator matrix of OAs is equal to a parity
check matrix of ECCs.
3.Relations of each columns in construction
problems of OAs are more complicate than in those
of ECCs.
No.55
参考文献)
[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
ダウンロード

単語単位で系列を出力する情報源に対する ZL符号とベイズ符号の