Исправление ошибок

[spamsink]

Как мы знаем™, в номерах кредитных карточек последняя цифра - контрольная, так что любая ошибка в одной цифре будет распознана (а также и большинство ошибок перестановки соседних цифр, но это другая история). Таким образом, если в номере карточки N десятичных цифр, то теоретически валидных номеров будет 10N-1.

А что, если мы хотим не только

Comments

[provokatorz]

довольно интересно эту проблему решали с номерами вагонов.

[spamsink]

Всё, что я знаю про номера вагонов, я знаю из какой-то детской книжки (не помню, про войну или нет), в которой мать ГГ работала на товарной станции контролёром, и в её обязанности входило записывать номера вагонов на ходу отъезжающего сформированного состава и сверять их с документами.

Раз там был относительно небольшой набор номеров, из которого нужно было выбирать, то это, наверное, менее сложная проблема.

[sevabashirov]

Вокруг валидного N-значного номера существует облако из 9*N невалидных с хэмминговым расстоянием 1, то есть всего в облаке 9N+1 точек и они не должны пересекаться. Для трехзначных номеров может быть максимум floor(1000;28)=35 облаков, для четырехзначных floor(10000;37)=270.

11-значный код с 2 контрольными цифрами и 9 значимыми в теории оптимален. Вопрос только, как задать формулы для этих цифр, чтобы построить полное покрытие облаками.

[sevabashirov]

Но это не единственное условие, так что для трехзначных проверка по расстоянию из поста обрубает эти 35 до 10... Как правильно экстраполировать дальше, на большее количество знаков, пока не понял.

[spamsink]

Из того, что для трехзначных номеров это соображение дает 35, хотя очевидно, что больше 10 нельзя, следует, что и для четырехзначных 270 - далеко не точная верхняя грань.

Бог с ними, с формулами. Предъявить бы хоть какой пример набора 4-хзначных номеров, близкий по мощности к 100.

[fantaseour]

Надо брать учебник по алгебраическим кодам и вспоминать, как построить.
http://iitp.ru/upload/content/790/algebcodes.pdf

Я диплом писал под руководством автора и, наверное 20+ лет назад мог бы ответить на это вопрос. Но вот память совсем удалила эту область знания к сожалению

[fantaseour]

Вот еще статья
https://habr.com/ru/post/328202/

Мозг скрипит и отказывается сейчас вникать, извините уж :)