Работа в Интернете

Безопасный код.

   Как известно, при передаче сигнала возможны помехи. Кроме того, применяются различного вида модуляции сигнала, чтобы его «сжать». С математической точки зрения нет разницы, какую модуляцию рассматривать, поэтому возьмём амплитудную.

   Мы будем рассматривать три рода помех амплитудной модуляции:

     - помеха прибавляется к сигналу (увеличивается или уменьшается амплитуда из-за помехи),

     - помеха замещает сигнал, и амплитуда помехи сравнима с амплитудой сигнала,

     - помеха замещает сигнал, но её амплитуда гораздо меньше.

   В данной статье мы рассмотрим первый род помех. Для удобства будем считать, что все сигналы могут принимать только положительное значение и ноль. Т.к. предполагается, что амплитуда сигнала в несколько раз выше помехи, то логично, что разная амплитуда сигнала будет соответствовать какой-то цифре. Мы привыкли к десятичной системе, поэтому, давайте, с неё и начнём.

    Случай 1. Амплитуда помехи меньше единицы (но почти её достигает), т.е. она не может повлиять на сигнал ни как – сигнал всегда передаётся верно. Однако мощность сигнала со временем падает – будем полагать, что будет падать амплитуда (мы математики – нам неважно, какой параметр меняется). Соответственно, мы хотим уменьшить амплитуду сигнала в два раза, но получить абсолютно надёжный код. В данном случае помеха либо будет увеличивать сигнал на единицу, либо не повлияет на него.

    Предлагается передавать два сигнала:

     - один передаёт исходный десятичный код (по две цифре) – последовательность (а),

     - второй передаёт сумму двух соседних цифр – от 0 до 18 –последовательность (б),

   Мы видим, что длина кода увеличилась вдвое.

   Проверим его надёжность.

   Сначала проверим последовательность (б), которая содержит числа из двух цифр.

   Проверяем первую цифру.

   Если первая цифра в числе 0, то, очевидно, помехи не было – первая цифра верна.

   Если первая цифра 2, то, очевидно, была помеха – первая цифра 1.

   Если первая цифра 1,  то помеха либо была, либо её не было. Если помеха была, то в сумме цифры из последовательности (а) должны давать меньше 10, причём если они дадут и при приёме сигнала сумму меньше 10, то, очевидно, в последовательности (б) прошла помеха.

    Однако возможна ситуация – сумма цифр в последовательности (а) даёт 8 или 9. Если там прошла помеха (она может пройти два раза подряд), то сумма может давать 10 или 11. Соответственно, если в последовательности (б), также прошла помеха, то мы её не заметим. Однако мы можем посмотреть на вторую цифру в последовательности (б). У нас сомнение вызывают только числа 10 и 11. Да, но если цифры из первой последовательности нам давали 8 или 9, то во второй последовательности было число 08 или 09. Помеха не может создать из 8 или 9 цифру 0 или 1 – она может только увеличить амплитуду на единицу (будет 9 или 10).

   Вывод: мы всегда можем распознать в числах последовательности б первую цифру.

   Первая цифра может принимать 0 или 1. А у нас сигнал позволяет использовать десятичную систему счисления – у нас есть запас из цифр.

   Положим чётная цифра – соответствует 0,

   Нечётная цифра – соответствует 1.

   В этом случае число 2 (неверное) соответствует 0, но если мы опять проанализируем варианты с последовательностью а, то опять получим противоречие – ошибку мы обнаружим, т.к. сумма будет заведомо больше 10.

   Проверяем вторую цифру в последовательности (б).

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

   Будем делать так:

     - в последовательности (а) первое число чётное, второе нечётное – первой цифрой в последовательности (б) будет 0 или 1,

     - в последовательности (а) первое число нечётное, второе чётное – первой цифрой в последовательности (б) будет 2 или 3,

     - в последовательности (а) числа одинаковой чётности  – первой цифрой в последовательности (б) будет 4 или 5.

     Приоритет имеет 3-я ситуация.

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

    Итак – построенная система передаёт код абсолютно надёжно, но она в два раза длиннее исходного кода.

    Однако у нас остались не использованными ещё 4 числа в первой цифре последовательности (б). Можно ли это как-то использовать?

    Мы можем использовать вместо десятичной системы двенадцатеричную – она также надёжна, но теперь:

   - в последовательности (а) первое число чётное, второе нечётное – первой цифрой в последовательности (б) будет 0 или 1 (6 или 7),

     - в последовательности «а» первое число нечётное, второе чётное – первой цифрой в последовательности (б) будет 2 или 3 (8 или 9),

     - в последовательности «а» числа одинаковой чётности  – первой цифрой в последовательности (б) будет 4 или 5 (10 или 11).

    Выбор первой цифры в коде (б), теперь даёт возможность закодировать ещё одну последовательность в двоичном коде (из 0 и 1) – всего три цифры, т.е. 8 различных цифр за один раз.

   Если мы учтём всё в совокупности, то, как показывают расчёты, мы проигрываем в длине кода не в два раза, а всего лишь 41% (при достаточной длине кода).

   Некоторые замечания.

   Если помехи нет, то уменьшение амплитуды кода даёт нам увеличение информации, при той же длине кода:

     - двоичная система – в два раза,

     - четвертичная система – в полтора раза,

     - восьмеричная система – в 4/3 раза,

     - двенадцатеричная (как и шестнадцатеричная) – 1.25 раза.

   Случай 2. Теперь изначально у нас помеха может повредить сообщение, но не более чем на единицу. Соответственно, мы можем применить предыдущий подход – код станет чуть длиннее при той же амплитуде, но абсолютно надёжным.

   Попробуем уменьшить амплитуду в два раза.

   Ну, опять же, значение первой цифры в коде (б) (0, 1 или 2) легко определяется.

   Со второй цифрой сложнее – теперь она может измениться на 1 или 2, как и в последовательности (a).

   Будем делать так:

     - первая цифра в последовательности (а) по модулю 3 равна 0, вторая по модулю 3 равна 0; первая цифра в последовательности (б) будет 0 или 1,

      - первая цифра в последовательности (а) по модулю 3 равна 0, вторая по модулю 3 равна 1; первая цифра в последовательности (б) будет 2 или 3,

     - первая цифра в последовательности (а) по модулю 3 равна 0, вторая по модулю 3 равна 2; первая цифра в последовательности (б) будет 4 или 5,

      - первая цифра в последовательности (а) по модулю 3 равна 1, вторая по модулю 3 равна 0; первая цифра в последовательности (б) будет 6 или 7,

      - первая цифра в последовательности (а) по модулю 3 равна 1, вторая по модулю 3 равна 1; первая цифра в последовательности (б) будет 8 или 9,

      - первая цифра в последовательности (а) по модулю 3 равна 1, вторая по модулю 3 равна 2; первая цифра в последовательности (б) будет 10 или 11,

     - первая цифра в последовательности (а) по модулю 3 равна 2, вторая по модулю 3 равна 0; первая цифра в последовательности (б) будет 12 или 13,

      - первая цифра в последовательности (а) по модулю 3 равна 2, вторая по модулю 3 равна 1; первая цифра в последовательности (б) будет 14 или 15,

      - первая цифра в последовательности (а) по модулю 3 равна 2, вторая по модулю 3 равна 2; первая цифра в последовательности (б) будет 16 или 17.

   Видим, что система стала 18-ричной. Первая цифра в последовательности (б) устанавливается однозначно – либо чётная, либо нет. Вторая устанавливается при помощи выше изложенного набора.

  Можно воспользоваться другой идеей – в последовательности (б) писать произведение цифр. Если одно из чисел 0,1 или 2, то прибавляем к нему 5, а потом делаем произведение. Ошибка обнаруживается сразу. Решение единственно. Опять код в два раза длиннее, но надёжный.

   Более того, мы можем воспользоваться той же идеей, если помеха имеет амплитуду равную 3 единицам и, даже, 4-ом (при десятеричной системе счисления).  Фактически, если используется троичная надёжная система, то можно использовать десятеричную систему, и она будет более выгодной (более короткой).

   Вместо заключения (гипотезы, требующие проверки).

   В первом способе бралась последовательность заведомо верная, и мы уменьшали её амплитуду. Исходя из последней, изложенной теории, мы можем амплитуду уменьшить в 5 раз, при этом длина кода увеличится в два раза (это при 10-ричной системе счисления).

   Надо сказать, что подобную идею можно было бы применить и при сложении – брать числа из последовательности «а» по модулю 5 (в 10-ой системе счисления). Тогда сумма была бы меньше 10, и, следовательно, мы имели бы 10 запасных цифр для использования – нам бы их хватило на помехи в две единицы. Для первого случая это дало бы 50% удлинения кода.

P.S.

Мне кажется, что правильнее писать денадцатиричная система, а не двенадцатеричная система и т.п., но что поделать…

rzninternet © 2011