OCR серийный номер CRC, алгоритм проверки

Question

Я хочу прочитать серийный номер с переменной длиной и базой-36, закодированный с использованием оптического распознавания символов. Так как могут возникнуть ошибки, может быть добавлен один символ для проверки избыточности цикла или в качестве контрольной суммы. Один закодированный на основе символов 36 может содержать 36 различных чисел в качестве контрольной суммы.

Серийный номер примера: СПГ TZ746B8 + один контрольный символ (основание-36)

На данный момент я попытался различные алгоритмы, такие как Luhn Mod N (36) алгоритма.

CRC

CRC наиболее часто используется для битовых ошибок при обнаружении сетевых передач, где самая высокая вероятность того, что один бит изменения. В теме распознавания серийного номера OCR более вероятной ошибкой распознавания является ложное распознавание символа «8» Ascii (двоичный 00111000) вместо символа «B» (двоичный код 01000010), приводит к более чем одной ошибке с одним битом , В CRC в качестве параметра для обнаружения ошибок используется значение Хэмминга (HD). Внутри ранее описанного полинома 0x05 для разделения CRC используется HD около 3-4, что приводит к необнаруженной ошибке, если больше бит изменяется. HD Source

Какой полином был бы лучшим или какой алгоритм контрольной суммы можно было бы использовать? В настоящий момент я достигаю наилучших результатов с использованием реализации CRC с повышением и 0x05 в качестве полиномиального деления для 5-битного CRC (для 36 символов требуется 6 бит, но последний бит не используется полностью. Для тестирования я использую только полные 5 бит = 31 разные символы). Список полиномов Wiki Polynomials

ключевые слова

Каких ключевых слов можно использовать, чтобы найти информацию в Интернете о теме обнаружения ошибок в системах оптического распознавания символов? Где можно найти статистику наиболее вероятных ошибок распознавания с помощью OCR? (Как и Е/3, B/8, ошибка.)

Проблема в использовании CRC

36 различных числа потребностей 7 бит, в результате чего не все 7 бит используются. 7 бит могут содержать до 63 номеров. Поэтому я должен по модулю (%) получить результат CRC или использовать только 6-битный многочлен. Исходя из этого, моя точность результатов падает, когда я использую модуль. Причина этого заключается в том, что большее количество бит может содержать более разные контрольные суммы, и поэтому происходит меньшее количество столкновений.

Кроме того, у меня есть проблема, что с помощью специальных символов OCR, таких как N/M, 3/E, B78, можно легко распознать ложь. Поскольку мое требование состоит в том, чтобы распознать все символы до 100%, исправлена ​​контрольная сумма или алгоритм CRC, чтобы предотвратить ложное распознавание без обнаружения.

Дальнейшая проблема заключается в том, что разные серийные номера, например серийный номер «S95I» и «5951», приводят к одной и той же контрольной сумме «GP». Поскольку OCR подвержено ошибкам распознавания ошибок 5/S, такая контрольная сумма не должна возникать.

Другие примеры для той же контрольной суммы символов.

Nr.1 - Nr.2 - Checksum 1 and 2 
BSHB - 85H8 - KA - KA 
BSJ8 - 85JB - IC - IC 
BSJ8 - 85JB - IC - IC 
BSQ8 - 85QB - KC - KC 
BSQ8 - 85QB - KC - KC 
BSSB - 85S8 - IA - IA 
BS1B - 8518 - ES - ES 
BS38 - 853B - GQ - GQ 
BB7I - 8871 - E0 - E0 
BB7I - 8871 - E0 - E0 
B930 - 89EO - BI - BI 
9331 - 9EEI - EQ - EQ 
9EEI - 9331 - EQ - EQ 

В моей реализации я использую алгоритм подталкивания CRC, который можно найти здесь Boost CRC:

string data = "S95I"; 
boost::crc_optimal<11, 0x571> crc; 
crc.process_bytes(data.data(), data.size()); 
stringstream checksum; 
checksum << (int)crc() % 1296; 
string resultCheck = checksum.str(); 

Я хотел бы знать, если есть другие алгоритмы с более низкой возможностью столкновений или другими возможностями для реализации контрольных сумм.

Если у вас есть какие-либо вопросы, или я не объяснил, что я недостаточно хорошо, пожалуйста, не стесняйтесь отвечать. Я постараюсь ответить как можно скорее.

Большое спасибо, Кристофа

Answer 1

У вас нет достаточного количества символов в вашей проверки значения. Далеко и далеко лучшее, что вы можете сделать, чтобы уменьшить столкновения, - это добавить еще контрольных символов. У вас должно быть не менее четырех.

я смог уменьшить количество столкновений на 20% в случае четырех символов с использованием Флетчера-производный чек вместо CRC, таким образом:

unsigned long check(char *seq, size_t len) 
{ 
    unsigned ch; 
    unsigned long sum = 1, val = 0; 

    while (len) { 
     ch = seq[--len]; 
     if (ch <= '9') 
      ch -= '0'; 
     else 
      ch -= 'A' - 10; 
     sum += ch; 
     val += sum; 
    } 
    return (sum % 36) + 36 * (val % 36); 
} 

Далее я уменьшил число столкновений с фактор примерно шесть смещая чек только различать символы, вероятно, есть ошибки распознавания, таким образом:

unsigned long check(char *seq, size_t len) 
{ 
    unsigned ch; 
    unsigned long sum = 1, val = 0; 
    static char incl[256] = { 
     ['0'] = 1, ['1'] = 2, ['3'] = 3, ['5'] = 4, ['8'] = 5, ['M'] = 6, 
     ['B'] = 7, ['E'] = 8, ['I'] = 9, ['N'] = 10, ['O'] = 11, ['S'] = 12 
    }; 

    while (len) { 
     ch = incl[(int)(seq[--len])]; 
     sum += ch; 
     val += sum; 
    } 
    return (sum % 36) + 36 * (val % 36); 
}