yasuokaの日記： 対角成分が0のDamm方陣とチェックディジット

私(安岡孝一)の昨日の日記で、H. Michael Dammの「Totally anti-symmetric quasigroups for all orders n≠2,6」(Discrete Mathematics, Vol.307, No.6 (2007年3月), pp.715-729)をちょっとだけ紹介したのだが、この論文に出てくるラテン方陣は対角成分が0でないため、チェックディジットとしては少し使いにくい。そこで、対角成分が0のDamm方陣を作成する手順を、ざっとここに書いておくことにする。

k-1桁の10進数xの各桁を、上から順にx₁,x₂,x₃,…と記す時、このxに対するチェックディジットc_kを作りたい。チェックディジットとしては、1桁の打ち間違いと、隣り合う2桁の入れ替えミスを、全て検出するようなものにしたい。このc_kを求める漸化式を、c_i+1=f(c_i,x_i), c₁=0で表すと、N={0,1,2,3,4,5,6,7,8,9}上の関数fは、以下の条件を満たす必要がある。

(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

条件(1)は、1桁の打ち間違いを、検出するためのものである。条件(2)は、隣り合う2桁の入れ替えミスを、検出するためのものである。条件(3)は、チェックディジットを含めた全部の桁を読み終わった瞬間に、それが正しければc_k+1=0とするためのものである。

N={0,1,2}すなわち3進数であれば、このようなf(c,x)は、ほぼ直感的に構成できる。

        x
    | 0 1 2
  --+------
  0 | 0 1 2
c 1 | 2 0 1
  2 | 1 2 0

あるいは、N={0,1,2,3,4,5,6,7,8}すなわち9進数であれば、上の3×3方陣に対し、それ自身でCartesian積を取り

   | 00 01 02 10 11 12 20 21 22
---+---------------------------
00 | 00 01 02 10 11 12 20 21 22
01 | 02 00 01 12 10 11 22 20 21
02 | 01 02 00 11 12 10 21 22 20
10 | 20 21 22 00 01 02 10 11 12
11 | 22 20 21 02 00 01 12 10 11
12 | 21 22 20 01 02 00 11 12 10
20 | 10 11 12 20 21 22 00 01 02
21 | 12 10 11 22 20 21 02 00 01
22 | 11 12 10 21 22 20 01 02 00

ラベルを以下のように付け替えればいい。

  | 0 1 2 3 4 5 6 7 8
--+------------------
0 | 0 1 2 3 4 5 6 7 8
1 | 2 0 1 5 3 4 8 6 7
2 | 1 2 0 4 5 3 7 8 6
3 | 6 7 8 0 1 2 3 4 5
4 | 8 6 7 2 0 1 5 3 4
5 | 7 8 6 1 2 0 4 5 3
6 | 3 4 5 6 7 8 0 1 2
7 | 5 3 4 8 6 7 2 0 1
8 | 4 5 3 7 8 6 1 2 0

一方、N={0,1,2,3,4,5,6,7,8,9}すなわち10進数については、話は簡単ではない。Dammのアプローチの1つは、Sade-Lindner積というアヤシゲなものを使う。具体的には、条件(3)をf(x,x)=xに置き換えた3×3方陣と、条件(3)を外してf(x,x)=xを左上隅だけに限定した4×4方陣を、以下のように準備する。

  | 0 1 2     | x a b c
--+------   --+--------
0 | 0 2 1   x | x a b c
1 | 2 1 0   a | b c x a
2 | 1 0 2   b | c b a x
            c | a x c b

これらに対し、Sade-Lindner積を取る。Sade-Lindner積のキモがわかりやすいよう、以下では大文字のABCも使っているが、小文字のabcと同義である。

   | xx 0a 0b 0c 1a 1b 1c 2a 2b 2c
---+------------------------------
xx | xx 0a 0b 0c 1a 1b 1c 2a 2b 2c
0a | 0b 0c xx 0a 2B 2a 2c 1c 1B 1a
0b | 0c 0b 0a xx 2a 2C 2b 1b 1a 1C
0c | 0a xx 0c 0b 2c 2b 2A 1A 1c 1b
1a | 1b 2c 2B 2a 1c xx 1a 0B 0a 0c
1b | 1c 2b 2a 2C 1b 1a xx 0a 0C 0b
1c | 1a 2A 2c 2b xx 1c 1b 0c 0b 0A
2a | 2b 1B 1a 1c 0c 0B 0a 2c xx 2a
2b | 2c 1a 1C 1b 0b 0a 0C 2b 2a xx
2c | 2a 1c 1b 1A 0A 0c 0b xx 2c 2b

ラベルを以下のように付け替える。

  | 0 1 2 3 4 5 6 7 8 9
--+--------------------
0 | 0 1 2 3 4 5 6 7 8 9
1 | 2 3 0 1 8 7 9 6 5 4
2 | 3 2 1 0 7 9 8 5 4 6
3 | 1 0 3 2 9 8 7 4 6 5
4 | 5 9 8 7 6 0 4 2 1 3
5 | 6 8 7 9 5 4 0 1 3 2
6 | 4 7 9 8 0 6 5 3 2 1
7 | 8 5 4 6 3 2 1 9 0 7
8 | 9 4 6 5 2 1 3 8 7 0
9 | 7 6 5 4 1 3 2 0 9 8

Sade-Lindner積は、条件(1)と条件(2)を満たすスグレモノだが、条件(3)は満たしていない。とりあえず、f(c,2)をf(c,1)と入れ替えてみよう。

  | 0 1 2 3 4 5 6 7 8 9
--+--------------------
0 | 0 2 1 3 4 5 6 7 8 9
1 | 2 0 3 1 8 7 9 6 5 4
2 | 3 1 2 0 7 9 8 5 4 6
3 | 1 3 0 2 9 8 7 4 6 5
4 | 5 8 9 7 6 0 4 2 1 3
5 | 6 7 8 9 5 4 0 1 3 2
6 | 4 9 7 8 0 6 5 3 2 1
7 | 8 4 5 6 3 2 1 9 0 7
8 | 9 6 4 5 2 1 3 8 7 0
9 | 7 5 6 4 1 3 2 0 9 8

列の入れ替えをおこなっても、条件(1)と条件(2)は満たしている。ならば、どんどん入れ替えればいい。

  | 0 1 2 3 4 5 6 7 8 9
--+--------------------
0 | 0 2 3 1 5 6 4 8 9 7
1 | 2 0 1 3 7 9 8 5 4 6
2 | 3 1 0 2 9 8 7 4 6 5
3 | 1 3 2 0 8 7 9 6 5 4
4 | 5 8 7 9 0 4 6 1 3 2
5 | 6 7 9 8 4 0 5 3 2 1
6 | 4 9 8 7 6 5 0 2 1 3
7 | 8 4 6 5 2 1 3 0 7 9
8 | 9 6 5 4 1 3 2 7 0 8
9 | 7 5 4 6 3 2 1 9 8 0

これで、条件(1)(2)(3)を満たすc_i+1=f(c_i,x_i)が構成できたことになる。よければ、チェックディジットとして使ってみてほしい。

Sade-Lindner積の4×4方陣

[yasuoka (21275)]

実は、途中で出てくる4x4方陣に条件(3)を付与して

 |x a b c
-+-------
x|x b c a
a|b x a c
b|c a x b
c|a c b x

でやると、列の入れ替えをおこなわずに最終解へ行くのです。でも、それだと、列の入れ替えの醍醐味が説明できないし、元のDammの論文からもズレてしまうので、こんな風にしてみました。