Расширение алгоритма Дамма до базы-32

Question

Расширение алгоритма Дамма до базы-32

Я хотел бы использовать алгоритм Дамма для генерации контрольных цифр для кодов с 32-символьным алфавитом. Сам алгоритм легко применим к любой базе (кроме 2 или 6). Трудность заключается в необходимой справочной таблице, которая должна быть полностью антисимметричной квазигруппой с одним символом (обычно 0) по главной диагонали.

Страница Википедии дает таблицу для базы 10, а реализация Python дает таблицу для базы 16, но я не нашел пример базы 32. У кого-нибудь есть подходящий стол для базы-32?

13

algorithm check-digit

Источник

user8355 02 май '14 в 15:23

3 ответа

Решение

Подводя итог обсуждению ниже: нам нужна таблица с нулями на главной диагонали. У нас с Никласом сложилось впечатление, что вместо того, чтобы быть неотъемлемой частью алгоритма, это свойство просто позволяет избежать решения уравнения x*y = 0 в y для заданного x, где * - операция квазигруппы. С нулями на главной диагонали у нас есть x = y, но без, мы можем вычислить y с помощью одного поиска в таблице из 32 элементов.

Конструкция, которую описывает Дамм, проблематична, потому что она обладает желаемым свойством тогда и только тогда, когда a = -1, но в характеристике 2 мы имеем 1 = -1. Решатель ограничений Z3 не помог.

Дамм диссертации (на немецком языке) здесь. Соответствующее определение состоит в том, что латинский квадрат является полностью антисимметричным тогда и только тогда, когда [для всех x и y элемент (x,y) равен элементу (y,x) тогда и только тогда, когда x = y]. Дамм дает конструкцию для простой степени n, отличную от 2 (включая случай n = 32), принимая элемент (x,y) за *x + y, где 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, который это сделал. Это может работать для других сил двух. Аргумент 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

4

Источник

user2144669 02 май '14 в 16:06

Если у вас есть квазигруппа ТА, вы можете просто переставить столбцы таким образом, чтобы 0 находились на главной диагонали. Тогда квазигруппа является (в общем случае) квазигруппой WTA и может использоваться для алгоритма Дамма. Я сделал это для заказа 32, смотрите результат ниже, и это возможно для каждого заказа, кроме 2 и 6.

Я думаю, что квазигруппа порядка 10, которую можно найти в Википедии, построена по лемме 5.2 тезисов Дамма. Это связано с тем, что он все равно должен обнаруживать фонетические ошибки после перестановки столбцов, поэтому элементы необходимо переименовывать и соответствующим образом переставлять строки.

Наконец, вот WTA квазигруппа порядка 32 для алгоритма Дамма:

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

3

Источник

user3625116 11 май '14 в 08:52

Другие вопросы по тегам algorithm check-digit

user411022 02 май '14 в 17:41 2014-05-02 17:41 · Accepted Answer · 2014-05-02 17:41

Вдохновленный ответом Дэвида Эйзенстата (и оригинальной диссертацией Дамма, которую он цитирует), вот простая подпрограмма Python для вычисления / проверки контрольной суммы Дамма для любой базы 2 ⁿ для 2 ≤ n ≤ 32:

# 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 до 2 ⁿ -1 включительно, и число n битов на цифру (предполагается, что оно находится в диапазоне 2 до 32 включительно).

Полностью асимметричная квазигруппа, используемая этой реализацией алгоритма Дамма, задается отображением (a, b) ↦ 2 ⊗ (a ⊕ b), где ⊕ обозначает сложение в конечном поле GF (2 ⁿ) (которое является просто побитовым XOR), ⊗ обозначает умножение в GF (2 ⁿ), а 2 обозначает элемент, представленный цепочкой битов 0... 010 ₂ в обычном n- битном представлении GF (2 ⁿ).

Это эквивалентно карте (a, b) ↦ (2 ⊗ a) given b, данной Даммом в Примере 5.2 его диссертации, за исключением того, что входные цифры переставлены с помощью b (умножая их на 2 в GF (2 ⁿ)) чтобы убедиться, что (a, a) ↦ 0 для всех a. Это эквивалентно перестановке столбцов таблицы операций квазигруппы, так что диагональ - все нули, и позволяет проверить контрольную сумму, просто добавив ее к исходному входу и проверив, что новая контрольная сумма расширенного ввода равна нулю.

Умножение GF (2 ⁿ) на 2 реализуется с помощью обычного трюка сдвига влево на единицу, и, если установлен n-й бит результата, XOR с помощью битовой маски, соответствующей моническому неприводимому полиному порядка n. Конкретные использованные битовые маски взяты из Таблицы бинарных неприводимых полиномов с малым весом Гадиеля Серусси (1998). Если вам (по какой-то причине) нужны контрольные суммы для баз, которые больше 2 ³², их таблица возрастет до 2 ¹⁰⁰⁰⁰. В таблице Серусси перечислены показатели ненулевых коэффициентов каждого полинома редукции, исключая постоянный член; битовые маски в приведенном выше коде получают путем отбрасывания наивысшего показателя степени (который всегда равен n), суммирования вместе 2 ^k для других показателей степени k и сложения 1. (Таким образом, например, запись "8,4,3,1" для n = 8 получается маска 2 ⁴ + 2 ³ + 2 ¹ + 1 = 16 + 8 + 2 + 1 = 27.)

В частности, приведенный выше код дает при n = 4 результаты, совпадающие с реализацией контрольной суммы Дамма по основанию 16, которую Иоганнес Шпильманн. В общем, это не гарантируется, поскольку существует много возможных способов реализации контрольной суммы Дамма для данной базы, но в этом случае квазигруппы, используемые двумя реализациями, совпадают.

Ps. Вот код 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)