Исправление ошибок
Mar. 26th, 2021 04:50 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
spamsinkКак мы знаем™, в номерах кредитных карточек последняя цифра - контрольная, так что любая ошибка в одной цифре будет распознана (а также и большинство ошибок перестановки соседних цифр, но это другая история). Таким образом, если в номере карточки N десятичных цифр, то теоретически валидных номеров будет 10N-1.
А что, если мы хотим не только распознавать, но и исправлять одиночные ошибки? Сколько тогда будет валидных N-значных десятичных номеров?
Рассмотрим для начала трехзначные номера. Тут мы быстро обнаружим, что валидных номеров может быть не более чем 10, потому что одна и та же цифра не может повторяться ни в одной позиции. Действительно, если номера вида ABC и ADE оба будут валидны, то мы не сможем понять, как исправить номер ABE. Или, другими словами, хэммингово расстояние между двумя валидными номерами должно быть не меньше трёх.
А сколько можно построить четырёхзначных номеров, исправляющих одиночную ошибку замены? Ровно 100 или меньше?
А что, если мы хотим не только распознавать, но и исправлять одиночные ошибки? Сколько тогда будет валидных N-значных десятичных номеров?
Рассмотрим для начала трехзначные номера. Тут мы быстро обнаружим, что валидных номеров может быть не более чем 10, потому что одна и та же цифра не может повторяться ни в одной позиции. Действительно, если номера вида ABC и ADE оба будут валидны, то мы не сможем понять, как исправить номер ABE. Или, другими словами, хэммингово расстояние между двумя валидными номерами должно быть не меньше трёх.
А сколько можно построить четырёхзначных номеров, исправляющих одиночную ошибку замены? Ровно 100 или меньше?
