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

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

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

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

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


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

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

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

ссылка на оригинал статьи http://habrahabr.ru/post/272003/