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

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

Примерами могут служить последняя цифра номера кредитной карты, девятая цифра 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 
#include 

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

© Habrahabr.ru