Этот материал будет полезен тем авторам, кто решит ввести в свои произведения загадочные шифры, позволяющие главным героям умело раскрывать таинственные послания.
Сей литературный приём не отличается новизной. Так, в рассказе Эдгара По "Золотой жук" главный герой Роберт Моррис пытается прочитать записку о кладе зашифрованную шифром подстановки.
Как это делается, я сейчас попытаюсь объяснить в доступной для понимания форме.
Итак, поговорим об упомянутом выше подстановочном шифре. Простой подстановочный шифр, или моноалфавитный шифр — очень прост, даже незатейлив. В нём для каждой буквы открытого текста существует единственная сопоставленная ей буква шифр-текста. Само шифрование заключается в замене букв согласно таблице. Для расшифровки достаточно иметь ту же таблицу, либо знать алгоритм, по которой она генерируется.
Алгоритм получения разрешения кодовой комбинации циклического кода из комбинации простого кода можно легко пояснить на простом примере.
Пусть задан полином P(x) = ar−1 xr + ar−2 xr−1 + … + 1, определяющий корректирующую способность кода и число проверочных разрядов r, а также исходная комбинация простого k— элементного кода в виде многочлена Ak−1(x).
Требуется определить разрешенную кодовую комбинацию циклического кода (n, k).
Наши действия предельно просты. Во-первых, мы умножаем многочлен исходной кодовой комбинации на xr:
Ak−1(x) · xr
Затем определяем проверочные разряды, как остаток от деления полученного в предыдущем пункте произведения на порождающий полином:
Ak−1(x) · xr ⁄ Pr(x) ⇒ R(x)
И наконец, окончательно разрешенная кодовая комбинация циклического кода определится так:
An−1(x) = Ak−1(x) · xr + R(x)
Понятно, шо для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация — разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки.
Теперь зададимся вполне очевидным вопросом: «А как исправить ошибку?»
Сделать это совсем несложно, так как по виду остатка можно сделать вывод о характере ошибки и её местоположении.
Существует ещё более доступный способ исправления ошибки. Это — введение избыточности (добавляются проверочные разряды). Например, при пятиэлементном простом коде число кодовых комбинаций 25 = 32, а при избыточном кодировании с одним добавочным разрядом число кодовых комбинаций равно 26 = 64.
Вполне очевидно, что с ошибками следует бороться, чтобы не получить в результате декодирования подобный текст.
Бил у бябюшки бяран,
Был он бёйко в бярябян.
И плясали бябёчки
Под окном у бябюшки.
Иль того хуже. При невнимательном шифровании текста методом подстановки Муха-Цокотуха, например, вполне может превратиться в Муху-Сцыкотуху...
Подводя итог, хочу обратить внимание авторов на то, шо кратность ошибки — это количество разрядов пораженных помехами в кодовой комбинации. И потому важной характеристикой кода является минимальное кодовое расстояние dmin между различными парами кодовых комбинаций, определяемое как число разрядов, в которых эти комбинации отличаются друг от друга. Напомню, для простых (безызбыточных) кодов dmin = 1.
Как видите, всё очень просто…
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.
Если вы используете ВКонтакте, Facebook, Twitter, Google или Яндекс, то регистрация займет у вас несколько секунд, а никаких дополнительных логинов и паролей запоминать не потребуется.