Damm アルゴリズムを使用して、32 文字のアルファベットのコードのチェック ディジットを生成したいと考えています。アルゴリズム自体は、任意の基数 (2 または 6 を除く) に簡単に適用できます。問題は、必要なルックアップ テーブルです。これは、主対角線の下に 1 文字 (通常は 0) を持つ完全に反対称な準群でなければなりません。
ウィキペディアのページには base 10 の表があり、Python 実装にはbase-16 の表がありますが、base-32 の例は見つかりませんでした。base-32 に適したテーブルを持っている人はいますか?
以下の議論を要約すると、主対角線にゼロがあるテーブルが必要です。Niklas と私は、この性質はアルゴリズムの本質的な部分というよりは、与えられた x に対して方程式 x*y = 0 を y で解くことを単に避けるためのものであるという印象を持っています。ここで、* は準群演算です。主対角にゼロがある場合、x = y になりますが、ゼロがない場合は、32 要素のテーブルで 1 回のルックアップで y を計算できます。
ダムが記述した構成は、a = -1 の場合にのみ目的の特性を持つため、問題がありますが、特性 2 では 1 = -1 です。制約ソルバー Z3 は役に立ちませんでした。
Damm の論文 (ドイツ語) はこちら. 関連する定義は、[すべての x と y について、(x,y) 要素が (y,x) 要素 (y,x) 要素に等しい場合、x = y] の場合、ラテン方陣は完全に反対称であるということです。Damm は、(x,y) 要素を a*x + y とすることにより、2 以外の素数べき乗 n (n = 32 の場合を含む) の構成を与えます。ここで、a は 0 でも 1 でもなく、* は n の乗算です。 -元ガロア体 (Beispiel 5.2)。
以下は、n = 32 の場合のこのメソッドのインスタンス化です。
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31],
[2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13, 18, 19, 16, 17, 22, 23, 20, 21, 26, 27, 24, 25, 30, 31, 28, 29],
[4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11, 20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 24, 25, 26, 27],
[6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 8, 9, 22, 23, 20, 21, 18, 19, 16, 17, 30, 31, 28, 29, 26, 27, 24, 25],
[8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23],
[10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5, 26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 23, 20, 21],
[12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3, 28, 29, 30, 31, 24, 25, 26, 27, 20, 21, 22, 23, 16, 17, 18, 19],
[14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1, 30, 31, 28, 29, 26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17],
[16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
[18, 19, 16, 17, 22, 23, 20, 21, 26, 27, 24, 25, 30, 31, 28, 29, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13],
[20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 24, 25, 26, 27, 4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11],
[22, 23, 20, 21, 18, 19, 16, 17, 30, 31, 28, 29, 26, 27, 24, 25, 6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 8, 9],
[24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7],
[26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 23, 20, 21, 10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5],
[28, 29, 30, 31, 24, 25, 26, 27, 20, 21, 22, 23, 16, 17, 18, 19, 12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3],
[30, 31, 28, 29, 26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1],
[5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 11, 10, 21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26],
[7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 23, 22, 21, 20, 19, 18, 17, 16, 31, 30, 29, 28, 27, 26, 25, 24],
[1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30],
[3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12, 19, 18, 17, 16, 23, 22, 21, 20, 27, 26, 25, 24, 31, 30, 29, 28],
[13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2, 29, 28, 31, 30, 25, 24, 27, 26, 21, 20, 23, 22, 17, 16, 19, 18],
[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16],
[9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6, 25, 24, 27, 26, 29, 28, 31, 30, 17, 16, 19, 18, 21, 20, 23, 22],
[11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4, 27, 26, 25, 24, 31, 30, 29, 28, 19, 18, 17, 16, 23, 22, 21, 20],
[21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26, 5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 11, 10],
[23, 22, 21, 20, 19, 18, 17, 16, 31, 30, 29, 28, 27, 26, 25, 24, 7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8],
[17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30, 1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14],
[19, 18, 17, 16, 23, 22, 21, 20, 27, 26, 25, 24, 31, 30, 29, 28, 3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12],
[29, 28, 31, 30, 25, 24, 27, 26, 21, 20, 23, 22, 17, 16, 19, 18, 13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2],
[31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
[25, 24, 27, 26, 29, 28, 31, 30, 17, 16, 19, 18, 21, 20, 23, 22, 9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6],
[27, 26, 25, 24, 31, 30, 29, 28, 19, 18, 17, 16, 23, 22, 21, 20, 11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4]]
以下は、これを作成した非常にくだらない Haskell コードです。他の 2 の累乗でも機能する可能性があります。main の引数 5 は 2^5 です。
module Main where
import Data.Char
import Data.List
xs +. ys = simplify (xs ++ ys)
xs *. ys
= simplify $
do x <- xs
y <- ys
return (x + y)
simplify xs
= (reverse . map head . filter (odd . length) . group . sort) xs
subseqs [] = [[]]
subseqs (x : xs) = let xss = subseqs xs in xss ++ map (x :) xss
polys n = subseqs [n, n - 1 .. 0]
reduce [] ys = ys
reduce xs [] = []
reduce xs@(x : _) ys@(y : _)
= if x > y then ys else reduce xs (map ((y - x) +) xs +. ys)
irred [] = False
irred ys@(y : _)
= let xss = polys (y `div` 2) \\ [[0]] in
(not . any null . map (flip reduce ys)) xss
irreds n = filter irred (polys n)
ip n = (head . filter irred . map (n :)) (polys (n - 1))
eval xs = (sum . map (2 ^)) xs
timesTable n
= let ms = ip n
zs = polys (n - 1) !! 2
in
do xs <- polys (n - 1)
return $
do ys <- polys (n - 1)
return (reduce ms ((zs *. xs) +. ys))
verify t
= all ((1 ==) . length . filter id) $
zipWith (zipWith (==)) t (transpose t)
main = print $ map (map eval) $ timesTable 5
TA 準群がある場合は、0 が主対角線上にあるように列を並べ替えるだけです。次に、準群は (一般に) WTA 準群であり、Damm アルゴリズムに使用できます。オーダー 32 でこれを実行しました。以下の結果を参照してください。これは、2 と 6 を除くすべてのオーダーで可能です。
ウィキペディアにある次数 10 の準群は、ダムの命題の補題 5.2 によって構成されていると思います。これは、列を再配置した後も音声エラーを検出する必要があるためです。そのため、要素の名前を変更し、それに応じて行を再配置する必要があります。
最後に、Damm アルゴリズムの次数 32 の WTA 準群を次に示します。
00 02 04 06 08 10 12 14 16 18 20 22 24 26 28 30 03 01 07 05 11 09 15 13 19 17 23 21 27 25 31 29
02 00 06 04 10 08 14 12 18 16 22 20 26 24 30 28 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31
04 06 00 02 12 14 08 10 20 22 16 18 28 30 24 26 07 05 03 01 15 13 11 09 23 21 19 17 31 29 27 25
06 04 02 00 14 12 10 08 22 20 18 16 30 28 26 24 05 07 01 03 13 15 09 11 21 23 17 19 29 31 25 27
08 10 12 14 00 02 04 06 24 26 28 30 16 18 20 22 11 09 15 13 03 01 07 05 27 25 31 29 19 17 23 21
10 08 14 12 02 00 06 04 26 24 30 28 18 16 22 20 09 11 13 15 01 03 05 07 25 27 29 31 17 19 21 23
12 14 08 10 04 06 00 02 28 30 24 26 20 22 16 18 15 13 11 09 07 05 03 01 31 29 27 25 23 21 19 17
14 12 10 08 06 04 02 00 30 28 26 24 22 20 18 16 13 15 09 11 05 07 01 03 29 31 25 27 21 23 17 19
16 18 20 22 24 26 28 30 00 02 04 06 08 10 12 14 19 17 23 21 27 25 31 29 03 01 07 05 11 09 15 13
18 16 22 20 26 24 30 28 02 00 06 04 10 08 14 12 17 19 21 23 25 27 29 31 01 03 05 07 09 11 13 15
20 22 16 18 28 30 24 26 04 06 00 02 12 14 08 10 23 21 19 17 31 29 27 25 07 05 03 01 15 13 11 09
22 20 18 16 30 28 26 24 06 04 02 00 14 12 10 08 21 23 17 19 29 31 25 27 05 07 01 03 13 15 09 11
24 26 28 30 16 18 20 22 08 10 12 14 00 02 04 06 27 25 31 29 19 17 23 21 11 09 15 13 03 01 07 05
26 24 30 28 18 16 22 20 10 08 14 12 02 00 06 04 25 27 29 31 17 19 21 23 09 11 13 15 01 03 05 07
28 30 24 26 20 22 16 18 12 14 08 10 04 06 00 02 31 29 27 25 23 21 19 17 15 13 11 09 07 05 03 01
30 28 26 24 22 20 18 16 14 12 10 08 06 04 02 00 29 31 25 27 21 23 17 19 13 15 09 11 05 07 01 03
03 01 07 05 11 09 15 13 19 17 23 21 27 25 31 29 00 02 04 06 08 10 12 14 16 18 20 22 24 26 28 30
01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31 02 00 06 04 10 08 14 12 18 16 22 20 26 24 30 28
07 05 03 01 15 13 11 09 23 21 19 17 31 29 27 25 04 06 00 02 12 14 08 10 20 22 16 18 28 30 24 26
05 07 01 03 13 15 09 11 21 23 17 19 29 31 25 27 06 04 02 00 14 12 10 08 22 20 18 16 30 28 26 24
11 09 15 13 03 01 07 05 27 25 31 29 19 17 23 21 08 10 12 14 00 02 04 06 24 26 28 30 16 18 20 22
09 11 13 15 01 03 05 07 25 27 29 31 17 19 21 23 10 08 14 12 02 00 06 04 26 24 30 28 18 16 22 20
15 13 11 09 07 05 03 01 31 29 27 25 23 21 19 17 12 14 08 10 04 06 00 02 28 30 24 26 20 22 16 18
13 15 09 11 05 07 01 03 29 31 25 27 21 23 17 19 14 12 10 08 06 04 02 00 30 28 26 24 22 20 18 16
19 17 23 21 27 25 31 29 03 01 07 05 11 09 15 13 16 18 20 22 24 26 28 30 00 02 04 06 08 10 12 14
17 19 21 23 25 27 29 31 01 03 05 07 09 11 13 15 18 16 22 20 26 24 30 28 02 00 06 04 10 08 14 12
23 21 19 17 31 29 27 25 07 05 03 01 15 13 11 09 20 22 16 18 28 30 24 26 04 06 00 02 12 14 08 10
21 23 17 19 29 31 25 27 05 07 01 03 13 15 09 11 22 20 18 16 30 28 26 24 06 04 02 00 14 12 10 08
27 25 31 29 19 17 23 21 11 09 15 13 03 01 07 05 24 26 28 30 16 18 20 22 08 10 12 14 00 02 04 06
25 27 29 31 17 19 21 23 09 11 13 15 01 03 05 07 26 24 30 28 18 16 22 20 10 08 14 12 02 00 06 04
31 29 27 25 23 21 19 17 15 13 11 09 07 05 03 01 28 30 24 26 20 22 16 18 12 14 08 10 04 06 00 02
29 31 25 27 21 23 17 19 13 15 09 11 05 07 01 03 30 28 26 24 22 20 18 16 14 12 10 08 06 04 02 00