Контрольная цифра методом Дамма

Контрольную цифру часто добавляют к идентификаторам, которые люди могут записывать или передавать с ошибками, чтобы эти ошибки потом обнаруживать.

Примерами могут служить последняя цифра номера кредитной карты, девятая цифра VIN автомобилей, продаваемых в в США, или последняя цифра ISBN.

Алгоритм контрольной цифры ван Дамма — относительно новый и потому малоизвестный. Он опубликован 2004 году.

Алгоритм обнаруживает все ошибки в одной цифре и все одиночные перестановки соседних цифр. Он заметно проще, чем сравнимый по возможностям алгоритм Верхуффа, и не требует использования специальных символов (таких как X в 10-значном ISBN).


В основе алгоритма лежит полностью антисимметричная квазигруппа. Ниже приведён один из примеров порядка 10. До диссертации Дамма [1] считалось, что подобные квазигруппы не существуют.

Квазигруппа подобрана так, чтобы помимо прочего определять максимальное количество фонетических ошибок, характерных для английского языка (13 вместо 30 и т.п.)

Промежуточная цифра	Входная цифра
	0	1	2	3	4	5	6	7	8	9
0	0	3	1	7	5	9	8	6	4	2
1	7	0	9	2	1	5	4	8	6	3
2	4	2	0	6	8	7	1	3	5	9
3	1	7	5	0	9	8	3	4	2	6
4	6	1	2	3	0	4	5	9	7	8
5	3	6	7	4	2	0	9	5	8	1
6	5	8	6	9	7	2	0	1	3	4
7	8	9	4	5	3	6	2	0	1	7
8	9	4	3	8	6	1	7	2	0	5
9	2	5	8	1	4	3	6	7	9	0

Кроме квазигруппы алгоритм использует одну промежуточную цифру, инициализируемую нулём, и по сути состоит всего из одной операции присваивания interim_digit_ = quasigroup[interim_digit_][digit].

Пример вычисления контрольной цифры

Предположим, что нам нужно вычислить контрольную цифру для последовательности 572.

1. Инициализируем промежуточную цифру значением 0.
2. Находим цифру в колонке 5 (это первая цифра входной последовательности) и строке 0 (это значение промежуточной цифры). Там 9. Присваиваем это значение промежуточной цифре.
3. Находим цифру в колонке 7 (это вторая цифра входной последовательности) и строке 9 (это значение промежуточной цифры). Там 7. Присваиваем это значение промежуточной цифре.
4. Находим цифру в колонке 2 (это третья цифра входной последовательности) и строке 7 (это значение промежуточной цифры). Там 4. Присваиваем это значение промежуточной цифре.
5. Входная последовательность закончилась. Последнее значение промежуточной цифры (4) и есть контрольная цифра. Добавляем её в конец последовательности и получаем 5724.

Пример проверки контрольной цифры

Проверяем последовательность цифр 5724. Если ошибок нет, контрольная цифра у неё должна быть 0.

1. Инициализируем промежуточную цифру значением 0.
2. Находим цифру в колонке 5 (это первая цифра входной последовательности) и строке 0 (это значение промежуточной цифры). Там 9. Присваиваем это значение промежуточной цифре.
3. Находим цифру в колонке 7 (это вторая цифра входной последовательности) и строке 9 (это значение промежуточной цифры). Там 7. Присваиваем это значение промежуточной цифре.
4. Находим цифру в колонке 2 (это третья цифра входной последовательности) и строке 7 (это значение промежуточной цифры). Там 4. Присваиваем это значение промежуточной цифре.
5. Находим цифру в колонке 4 (это четвёртая цифра входной последовательности) и строке 4 (это значение промежуточной цифры). Там 0. Присваиваем это значение промежуточной цифре.
6. Входная последовательность закончилась. Последнее значение промежуточной цифры равно 0, как и ожидалось.

Исходный код полностью

#include <iostream>
#include <cassert>

class Damm {
  public:
    Damm() : interim_digit_(0) {}
  
    void push(int digit) {
      static const int quasigroup[10][10] = {
        {0, 3, 1, 7, 5, 9, 8, 6, 4, 2},
        {7, 0, 9, 2, 1, 5, 4, 8, 6, 3},
        {4, 2, 0, 6, 8, 7, 1, 3, 5, 9},
        {1, 7, 5, 0, 9, 8, 3, 4, 2, 6},
        {6, 1, 2, 3, 0, 4, 5, 9, 7, 8},
        {3, 6, 7, 4, 2, 0, 9, 5, 8, 1},
        {5, 8, 6, 9, 7, 2, 0, 1, 3, 4},
        {8, 9, 4, 5, 3, 6, 2, 0, 1, 7},
        {9, 4, 3, 8, 6, 1, 7, 2, 0, 5},
        {2, 5, 8, 1, 4, 3, 6, 7, 9, 0}
      };
      assert(digit >= 0);
      assert(digit <= 9);
      interim_digit_ = quasigroup[interim_digit_][digit];
    }
    
    int check_digit(void) const {
      return interim_digit_;
    }
    
    void clear(void) {
      interim_digit_ = 0;
    }
    
  private:
    int interim_digit_;
};

int main(void)
{
  Damm d;
  d.push(5);
  d.push(7);
  d.push(2);
  int check_digit = d.check_digit();
  std::cout << "Check digit (572) = " << check_digit << ", expected 4\n";
  
  d.clear();
  d.push(5);
  d.push(7);
  d.push(2);
  d.push(4);
  check_digit = d.check_digit();
  std::cout << "Check digit (5724) = " << check_digit << ", expected 0\n";
  
  return 0;
}

Ссылка на первоисточник

[1] Damm, H. Michael Total anti-symmetrische Quasigruppen PDF