yasuokaの日記： 26×26のDamm方陣によるチェックディジット

昨日の日記に続いて、26×26のDamm方陣も考えてみることにした。チェックディジット関数c_i+1=f(c_i,x_i), c₁=0の条件を、再確認しておこう。

(1) f(c,x)=f(c,y) ⇔ x=y
(2) f(f(c,x),y)=f(f(c,y),x) ⇔ x=y
(3) f(c,x)=0 ⇔ c=x

26×26方陣は、Sade-Lindner積で構成することができない。条件(1)と条件(2)を満たし得る6×6方陣が、存在しないからだ。そこで、とりあえず25×25方陣を作って、それに項を1つ追加することを考える。

ただし、そのような「追加」がおこなえる方陣は、条件(3)を

(3a) f(x,x)=f(y,y) ⇔ x=y
(3b) f(f(x,x),y)=f(f(y,y),x) ⇔ x=y
(3c) f(f(x,y),x)≠f(y,y)

に置き換えておく必要がある。25=5²なので、a²－a+1=0を原始多項式とするGalois体GF(5²)での加乗算を用いて、たとえばf(c,x)=ac+(1－a)x+1で25×25方陣を構成すれば、これらの条件を簡単に満たすことができる。以下に、この25×25方陣を示す。

   | 00 01 02 03 04 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34 40 41 42 43 44
---+---------------------------------------------------------------------------
00 | 01 42 33 24 10 02 43 34 20 11 03 44 30 21 12 04 40 31 22 13 00 41 32 23 14
01 | 11 02 43 34 20 12 03 44 30 21 13 04 40 31 22 14 00 41 32 23 10 01 42 33 24
02 | 21 12 03 44 30 22 13 04 40 31 23 14 00 41 32 24 10 01 42 33 20 11 02 43 34
03 | 31 22 13 04 40 32 23 14 00 41 33 24 10 01 42 34 20 11 02 43 30 21 12 03 44
04 | 41 32 23 14 00 42 33 24 10 01 43 34 20 11 02 44 30 21 12 03 40 31 22 13 04
10 | 10 01 42 33 24 11 02 43 34 20 12 03 44 30 21 13 04 40 31 22 14 00 41 32 23
11 | 20 11 02 43 34 21 12 03 44 30 22 13 04 40 31 23 14 00 41 32 24 10 01 42 33
12 | 30 21 12 03 44 31 22 13 04 40 32 23 14 00 41 33 24 10 01 42 34 20 11 02 43
13 | 40 31 22 13 04 41 32 23 14 00 42 33 24 10 01 43 34 20 11 02 44 30 21 12 03
14 | 00 41 32 23 14 01 42 33 24 10 02 43 34 20 11 03 44 30 21 12 04 40 31 22 13
20 | 24 10 01 42 33 20 11 02 43 34 21 12 03 44 30 22 13 04 40 31 23 14 00 41 32
21 | 34 20 11 02 43 30 21 12 03 44 31 22 13 04 40 32 23 14 00 41 33 24 10 01 42
22 | 44 30 21 12 03 40 31 22 13 04 41 32 23 14 00 42 33 24 10 01 43 34 20 11 02
23 | 04 40 31 22 13 00 41 32 23 14 01 42 33 24 10 02 43 34 20 11 03 44 30 21 12
24 | 14 00 41 32 23 10 01 42 33 24 11 02 43 34 20 12 03 44 30 21 13 04 40 31 22
30 | 33 24 10 01 42 34 20 11 02 43 30 21 12 03 44 31 22 13 04 40 32 23 14 00 41
31 | 43 34 20 11 02 44 30 21 12 03 40 31 22 13 04 41 32 23 14 00 42 33 24 10 01
32 | 03 44 30 21 12 04 40 31 22 13 00 41 32 23 14 01 42 33 24 10 02 43 34 20 11
33 | 13 04 40 31 22 14 00 41 32 23 10 01 42 33 24 11 02 43 34 20 12 03 44 30 21
34 | 23 14 00 41 32 24 10 01 42 33 20 11 02 43 34 21 12 03 44 30 22 13 04 40 31
40 | 42 33 24 10 01 43 34 20 11 02 44 30 21 12 03 40 31 22 13 04 41 32 23 14 00
41 | 02 43 34 20 11 03 44 30 21 12 04 40 31 22 13 00 41 32 23 14 01 42 33 24 10
42 | 12 03 44 30 21 13 04 40 31 22 14 00 41 32 23 10 01 42 33 24 11 02 43 34 20
43 | 22 13 04 40 31 23 14 00 41 32 24 10 01 42 33 20 11 02 43 34 21 12 03 44 30
44 | 32 23 14 00 41 33 24 10 01 42 34 20 11 02 43 30 21 12 03 44 31 22 13 04 40

これを26×26方陣にするには、対角成分を追加行と追加列に追い出して、代わりに新たな項で置き換えればいい。zzを追加してみよう。

   | 00 01 02 03 04 10 11 12 13 14 20 21 22 23 24 30 31 32 33 34 40 41 42 43 44 zz
---+------------------------------------------------------------------------------
00 | zz 42 33 24 10 02 43 34 20 11 03 44 30 21 12 04 40 31 22 13 00 41 32 23 14 01
01 | 11 zz 43 34 20 12 03 44 30 21 13 04 40 31 22 14 00 41 32 23 10 01 42 33 24 02
02 | 21 12 zz 44 30 22 13 04 40 31 23 14 00 41 32 24 10 01 42 33 20 11 02 43 34 03
03 | 31 22 13 zz 40 32 23 14 00 41 33 24 10 01 42 34 20 11 02 43 30 21 12 03 44 04
04 | 41 32 23 14 zz 42 33 24 10 01 43 34 20 11 02 44 30 21 12 03 40 31 22 13 04 00
10 | 10 01 42 33 24 zz 02 43 34 20 12 03 44 30 21 13 04 40 31 22 14 00 41 32 23 11
11 | 20 11 02 43 34 21 zz 03 44 30 22 13 04 40 31 23 14 00 41 32 24 10 01 42 33 12
12 | 30 21 12 03 44 31 22 zz 04 40 32 23 14 00 41 33 24 10 01 42 34 20 11 02 43 13
13 | 40 31 22 13 04 41 32 23 zz 00 42 33 24 10 01 43 34 20 11 02 44 30 21 12 03 14
14 | 00 41 32 23 14 01 42 33 24 zz 02 43 34 20 11 03 44 30 21 12 04 40 31 22 13 10
20 | 24 10 01 42 33 20 11 02 43 34 zz 12 03 44 30 22 13 04 40 31 23 14 00 41 32 21
21 | 34 20 11 02 43 30 21 12 03 44 31 zz 13 04 40 32 23 14 00 41 33 24 10 01 42 22
22 | 44 30 21 12 03 40 31 22 13 04 41 32 zz 14 00 42 33 24 10 01 43 34 20 11 02 23
23 | 04 40 31 22 13 00 41 32 23 14 01 42 33 zz 10 02 43 34 20 11 03 44 30 21 12 24
24 | 14 00 41 32 23 10 01 42 33 24 11 02 43 34 zz 12 03 44 30 21 13 04 40 31 22 20
30 | 33 24 10 01 42 34 20 11 02 43 30 21 12 03 44 zz 22 13 04 40 32 23 14 00 41 31
31 | 43 34 20 11 02 44 30 21 12 03 40 31 22 13 04 41 zz 23 14 00 42 33 24 10 01 32
32 | 03 44 30 21 12 04 40 31 22 13 00 41 32 23 14 01 42 zz 24 10 02 43 34 20 11 33
33 | 13 04 40 31 22 14 00 41 32 23 10 01 42 33 24 11 02 43 zz 20 12 03 44 30 21 34
34 | 23 14 00 41 32 24 10 01 42 33 20 11 02 43 34 21 12 03 44 zz 22 13 04 40 31 30
40 | 42 33 24 10 01 43 34 20 11 02 44 30 21 12 03 40 31 22 13 04 zz 32 23 14 00 41
41 | 02 43 34 20 11 03 44 30 21 12 04 40 31 22 13 00 41 32 23 14 01 zz 33 24 10 42
42 | 12 03 44 30 21 13 04 40 31 22 14 00 41 32 23 10 01 42 33 24 11 02 zz 34 20 43
43 | 22 13 04 40 31 23 14 00 41 32 24 10 01 42 33 20 11 02 43 34 21 12 03 zz 30 44
44 | 32 23 14 00 41 33 24 10 01 42 34 20 11 02 43 30 21 12 03 44 31 22 13 04 zz 40
zz | 01 02 03 04 00 11 12 13 14 10 21 22 23 24 20 31 32 33 34 30 41 42 43 44 40 zz

zzを0だとみなせば、これで、条件(3)も満たしたことになる。ラベルをアルファベットに置き換えてみよう。

  | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
--+----------------------------------------------------
A | Z W S O F C X T K G D Y P L H E U Q M I A V R N J B
B | G Z X T K H D Y P L I E U Q M J A V R N F B W S O C
C | L H Z Y P M I E U Q N J A V R O F B W S K G C X T D
D | Q M I Z U R N J A V S O F B W T K G C X P L H D Y E
E | V R N J Z W S O F B X T K G C Y P L H D U Q M I E A
F | F B W S O Z C X T K H D Y P L I E U Q M J A V R N G
G | K G C X T L Z D Y P M I E U Q N J A V R O F B W S H
H | P L H D Y Q M Z E U R N J A V S O F B W T K G C X I
I | U Q M I E V R N Z A W S O F B X T K G C Y P L H D J
J | A V R N J B W S O Z C X T K G D Y P L H E U Q M I F
K | O F B W S K G C X T Z H D Y P M I E U Q N J A V R L
L | T K G C X P L H D Y Q Z I E U R N J A V S O F B W M
M | Y P L H D U Q M I E V R Z J A W S O F B X T K G C N
N | E U Q M I A V R N J B W S Z F C X T K G D Y P L H O
O | J A V R N F B W S O G C X T Z H D Y P L I E U Q M K
P | S O F B W T K G C X P L H D Y Z M I E U R N J A V Q
Q | X T K G C Y P L H D U Q M I E V Z N J A W S O F B R
R | D Y P L H E U Q M I A V R N J B W Z O F C X T K G S
S | I E U Q M J A V R N F B W S O G C X Z K H D Y P L T
T | N J A V R O F B W S K G C X T L H D Y Z M I E U Q P
U | W S O F B X T K G C Y P L H D U Q M I E Z R N J A V
V | C X T K G D Y P L H E U Q M I A V R N J B Z S O F W
W | H D Y P L I E U Q M J A V R N F B W S O G C Z T K X
X | M I E U Q N J A V R O F B W S K G C X T L H D Z P Y
Y | R N J A V S O F B W T K G C X P L H D Y Q M I E Z U
Z | B C D E A G H I J F L M N O K Q R S T P V W X Y U Z

ただ、このようなアルファベットの「チェックディジット」を構成するのなら、無理に26×26方陣にしない方がいいように、私(安岡孝一)には思える。ピリオドか何かを加えて27×27方陣にした方が、構成するのも簡単だし、氏名の区切りにも使えるので、何かと都合がいいと思うのだが、どうだろう。