Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.7. Буквенно-цифровые коды — взвешенные коды

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

Человеку свойственно делать ошибки другого рода. Типичным примером ошибок человека является перестановка соседних цифр при записи чисел: например, превращается в 76. Другой стандартной ошибкой может быть дублирование неправильной цифры в трехзначном числе, в котором две соседние цифры совпадают: например, превращается в 677. Здесь происходит простая замена одной цифры. Таковы две наиболее распространенные ошибки человека при записи чисел. В система содержащих как буквы, так и цифры, очень часто путаются цифра «нуль» и буква

Достаточно часто встречаются ситуации, в которых полный набор используемых символов состоит из букв, пробела и 10 десятичных цифр. Таким образом, исходный алфавит содержит символов. К счастью, 37 — простое число, что позволяет применять следующий метод проверки. Символы сообщения снабжаются весами начиная с проверочного символа сообщения. Затем производится редукция суммы по модулю 37 (т. е. берется остаток от деления суммы на 37) так, что проверочный символ может быть выбран таким образом, чтобы вся сумма была сравнима с по модулю 37. Заметим, что пробел, стоящий в конце в качестве проверочного символа — это не то же самое, что отсутствие символа.

Легко проверить, что любая перестановка двух соседних цифр обнаруживается так же, как и дублирование неверной цифры (что эквивалентно замене одного символа). Можно обнаружить также много других изменений. Перестановка нуля и буквы О также является заменой одного символа. Рассматриваемый код очень полезен в процессах, предусматривающих участие человека. Заметим, что длина сообщения не фиксирована и при необходимости может превышать 37 символов (хотя при этом нужны специальные предосторожности). Такое кодирование можно использовать в кредитных карточках, в списках для записи некоторых названий и т. д. Вероятность того, что случайная последовательность удовлетворяет такой проверке, равна 1/37. Таким образом, используя эту простую проверку на четность, можно выявить около 97% случаев подлога.

Для того чтобы найти взвешенную сумму наиболее простым способом, заметим, что при вычислении частичных сумм множества чисел и окончательном их суммировании получаем, что первое число входит в окончательную сумму раз, второе — раз, следующее раза и т. д. Последнее число войдет в сумму один раз. Таким образом, имеем требуемую взвешенную сумму чисел, соответствующую используемым в сообщении символам алфавита.

Для пояснения процесса «суммирования сумм» рассмотрим сообщение

Из таблицы видно, как возникает взвешенная сумма. Этот процесс иногда называется возрастающим цифрованием.

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление