例: H = ( 1 0 1 1 ) ( 0 1 0 1 )
( n-k ) × n 行列 H : 検査行列
n × k 行列 G : 生成行列
( n, k ) 線形符号 C
C = { x ∈ GF (2) n | H x = 0 } = { x | x = G y, y ∈ GF (2) k } , H G = 0
検査行列は ( I n-k, H ' ) と書ける。
よって、x = ( x 1 , ... , x n-k , x n-k+1 , ... , x n ) とし、
x ' = ( x 1 , ... , x n-k ) ,
x '' = ( x n-k+1 , ... , x n ) とすると、
0 = H x = I n-k x ' + H ' x ''
となる。
x '' , は k 次元ベクトル。全ての k 次元ベクトルを列挙すると 2 k個。
それを縦に並べる。
00:
01:
10:
11:
GF (2) n-k においては x = - x なので、
0 = I n-k x ' + H ' x '' から
x ' = H ' x ''
( x 1 , ... , x n-k ) = H ' ( x n-k+1 , ... , x n )
上で並べた k 個を x '' に入れていくと、 x ' が k 個出てくる。
x = ( x ' , x '' ) なので、符号 C が k 個求められる。
それを、表の次の列の対応した位置に並べる。
H' = ( 1 1 )
( 0 1 )
H' ( 0 0 )T = ( 0 0 )T
→ C0 = ( 0 0 0 0 )
H' ( 0 1 )T = ( 1 1 )T
→ C1 = ( 1 1 0 1 )
H' ( 1 0 )T = ( 1 0 )T
→ C2 = ( 1 0 1 0 )
H' ( 1 1 )T = ( 0 1 )T
→ C3 = ( 0 1 1 1 )
00: 0000
01: 1101
10: 1010
11: 0111
一番上の行の右に、一番左上の符号 C 0 とハミング距離が 最小 のものを並べる。
00: 0000 1000
01: 1101
10: 1010
11: 0111
表の交差した部分に、足したものを書く。
00: 0000 1000
01: 1101 0101
10: 1010 0010
11: 0111 1111
更に一行目の右に、ハミング距離が最小で、まだ現れていない符号を書く。
00: 0000 1000 0100
01: 1101 0101
10: 1010 0010
11: 0111 1111
足して埋める。
00: 0000 1000 0100
01: 1101 0101 1001
10: 1010 0010 1110
11: 0111 1111 0011
以下繰り返し。
00: 0000 1000 0100 0001
01: 1101 0101 1001 1100
10: 1010 0010 1110 1011
11: 0111 1111 0011 0110
最終的に、2 k × 2 k の表ができるはず。