logo标签列表

将Damm算法扩展到base-32

algorithmcheck-digit
13

我想使用Damm算法为具有32个字符的字母表的代码生成检查位。该算法本身很容易应用于任何进制（除了2或6）。困难在于必要的查找表，它必须是一个完全反对称的拟群，主对角线上必须是单个字符（通常为0）。

维基百科页面提供了十进制的表格，而Python实现则提供了十六进制的表格，但我还没有找到适用于32进制的示例。是否有人有适用于32进制的合适的表格？

对于我略微更有精力的人：Damm 的博士论文（德语版）在这里。相关定义是，如果对于所有x和y，（x，y）元素等于（y，x）元素当且仅当x = y，则拉丁方阵是完全反对称的。达姆提供了一个构造质数幂n的方法（除去2的情况，包括n = 32的情况），将（x，y）元素视为a * x + y，其中a既不是0也不是1，*是n元Galois场上的乘法（例5.2）。 - David Eisenstat
是的，我找到了那个，但我不会读德语，我希望有人已经根据论文编写了可运行的代码。 - cjm
Ilmari的回答（https://dev59.com/aGAg5IYBdhLWcg3wlLuh#23433934）对于原始问题是正确的（如果您正在实现Damm以更好地理解算法，则强烈建议阅读），但是一组用于所有支持的基数的DAMM的TA拟群已经在http://www.md-software.de/math/DAMM_Quasigruppen.txt上发布（很可能是在提出/回答此问题之后），这将支持更通用的实现（GF组显然仅限于2的幂）。 - archie
3个回答
13
受David Eisenstat答案（以及他引用的Damm原始论文）的启发，这里有一个简单的Python例程，用于计算/验证2 ≤ n ≤ 32的任何基础2的Damm校验和：
# reduction bitmasks for GF(2^n), 2 <= n <= 32
masks = (3, 3, 3, 5, 3, 3, 27, 3, 9, 5, 9, 27, 33, 3, 43, 9,
         9, 39, 9, 5, 3, 33, 27, 9, 27, 39, 3, 5, 3, 9, 141)

# calculate Damm checksum for base 2^n
def damm2n (digits, n):
    modulus = (1 << n)
    mask = modulus | masks[n - 2]
    checksum = 0
    for digit in digits:
        checksum ^= digit
        checksum <<= 1
        if checksum >= modulus: checksum ^= mask
    return checksum

这个程序需要一个数字列表（或者更一般的，是一个可迭代对象），假设这些数字是在0到2n-1之间的整数，每个数字有n比特位（假设比特位在2到32之间）。

该实现中使用的Damm算法的完全非对称夸群由映射(a, b) ↦ 2 ⊗ (a ⊕ b)给出，其中 ⊕ 表示有限域GF(2n)中的加法（即按位异或），⊗表示GF(2n)中的乘法，2表示在GF(2n)的通常n位表示中由比特串0...0102表示的元素。

这相当于Damm在他的论文5.2例子中给出的(a, b) ↦ (2 ⊗ a) ⊕ b映射，只是输入数字被置换了(b乘以GF(2n)中的2)，以确保对于所有a，(a, a) ↦ 0。这相当于重新排列拟群操作表的列，使对角线上全为零，并且可以通过将其附加到原始输入并检查扩展输入的新校验和是否为零来简单验证校验和。

GF(2n)乘以2的方法是将其左移一位，如果结果的第n位被设置，则使用对应于次数为n的首一不可约多项式的掩码进行异或。上面的代码中使用的特定掩码来自Gadiel Seroussi（1998年）的低权二进制不可约多项式表。如果您因某种原因需要大于232的基数的校验和，则他们的表格高达210,000。Seroussi表列出了每个约化多项式非零系数的指数，不包括常数项；上述代码中的掩码是通过丢弃最高指数（始终为n），对其他指数k求和并加1获得的。 （因此，例如，n=8的条目“8,4,3,1”产生掩码24+23+21+1=16+8+2+1=27。）

特别是，对于n = 4，上述代码的结果与Johannes Spielmann实现的base-16 Damm checksum implementation匹配。这在一般情况下并不保证，因为有许多可能的方法来实现给定基数的Damm校验和，但在这种情况下，两个实现使用的拟群恰好匹配。

附注：以下是一些 Python 代码，可以以类似于维基百科文章的格式打印查找表。 （感谢 CJM 提供初始版本。）

alphabet = '0123456789ABCDEFGHJKLMNPQRTUVWXY' # avoids easy-to-confuse characters
bits = 5

# find out which first single-digit input gives which checksum
r = [-1] * 2**bits
for i in range(2**bits): r[damm2n([i], bits)] = i

# print header
print '  |',  ' '.join(alphabet)
print '--+' + '--' * len(alphabet)

# print rest of table    
for i in range(2**bits):
    row = (alphabet[damm2n([r[i], j], bits)] for j in range(2**bits))
    print alphabet[i], '|', ' '.join(row)
为了强调你的主要观点：校验和算法的目的是定义码字，使得（i）每个k位字符串都是k+1位码字的前缀，且（ii）没有任何一个码字的邻居是码字，这里的“邻居”指的是通过替换一个数字或交换两个相邻数字而导出的字符串。当对每个数字应用相同的置换时，邻域的结构被保留。 - David Eisenstat
1
为了使 Python 3 中的表转储代码起作用，需要在每个“print”的参数周围添加括号。但是这会破坏 Python 2 的输出。 - cjm
4
总之，我们希望一个主对角线上有零的表格。Niklas和我认为，这个属性不是算法的必要部分，而仅仅是为了避免在给定x的情况下解方程x*y=0中求y，其中*是半群操作。有了主对角线上的零，我们有x=y，但没有这个条件，我们可以通过在32元素表格中查找来计算y。Damm描述的构造是有问题的，因为只有当a=-1时才具有所需的属性，但在特征2中，我们有1=-1。约束求解器Z3没有帮助。

Damm的论文（德语版）在这里。相关定义是：如果[对于所有x和y，（x，y）元素等于（y，x）元素当且仅当x = y]，则拉丁正方形是完全反对称的。Damm通过将（x，y）元素取为a * x + y来构造了质数幂n（包括n = 32的情况），其中a不为0或1，*是一个n元Galois域上的乘法（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
问题在于，在校验位算法中使用拟群时，您希望主对角线是一个常数（对于任何n，f(n,n) = 0）。可能可以重新排列表格以实现该目标。 - cjm
@cjm 这让问题变得棘手的是，在特征为2的域中（例如GF(32)），我们有-1 = 1; 否则我们可以取a = -1。 - David Eisenstat
我正在尝试弄清楚如何从论文第111页上的表推导出基数为10的表格。如果您重新排列列，使零位于对角线上，那么这将给您第一行，但我找不到其他条目更改的算法。 - cjm
这很不幸，因为有一个8x8的矩阵和直积构造。 - David Eisenstat
@cjm 我也有同样的想法，但我担心正确性证明可能不适用于涉及校验位的置换，当以这种方式计算校验位时（与解决使整个乘积为0的方程方式相反）。 - David Eisenstat
显示剩余4条评论
3
如果您有一个TA拟群，只需重新排列列，使0在主对角线上。然后，拟群（一般情况下）是WTA拟群，并可用于Damm算法。我已经对32阶进行了这样的操作，下面是结果，每个订单除2和6外都可以实现。
我认为维基百科中可以找到10阶拟群是由Damm论文的Lemma 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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接