Tribit алгоритм описание реализации

Ранее рассматривалось задача реализации Tribit алгоритма для вычисления контрольной суммы битового числа. Задача сформулирована здесь.

Описание задания было очень подробны и объемным, поэтому при его описании были даны лишь исходные коды реализующие простейший способ его реализации, без описания как же именно это происходит. Поэтому далее приведу небольшое описание сути алгоритма.

Для обработки малых пирамид при применении системы правил и усечении, генерируются индексы соответствующие каждой пирамиде. Эти индексы соответствуют номерам символов входной строки, которые соответствуют пирамиде.
Например:
во входной строке символы нумеруются 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
в пирамиде соответствующие индексы будут соответствовать ячейкам
16
15 14 13
12 11 10 09 08
07 06 05 04 03 02 01
при анализе пирамиды в ней выделяются малые пирамиды и вычисляются индекс для ячеек после чего из них извлекаются символы , анализируются и при необходимости перезаписываются.
Т.е. для малых пирамид будут соответствовать индексы порядок ячеек в малых пирамидах описан в hexic.txt. Таким образом для ячеек малых пирамид 0, 1 , 2, 3 получим следующее соответствие.
0   1   2   3
08 03 02 01
12 07 06 05
04 11 10 09
16 15 14 13

Для генерации этих индексов перебираются уровни пирамиды, начиная с основания, с шагом 2. На каждом уровне пирамиды перебираются четные числа, которые соответствуют отдельным пирамидам. Уровень начинается всегда с малой пирамиды, которая стоит на своём основании, далее малые пирамиды, стоящие на основании чередуются, с пирамидами которые стоят на вершине. Зная это чередование можно для каждой из них вычислить индексы соответствующее ячейкам 0,1,2,3 малой пирамиды.

Число элементов каждого уровня пирамиды соответствует члену арифметической прогрессии с шагом два и первым элементом равным 1. Для малой пирамиды уровня i, которая стоит на основании индекс нулевой ячейки равен сумме индекса второй ячейки и длины (i-1) уровня +1. Для пирамиды, которая стоит на вершине – он равен разности. Вычисление индексов второй и третьей ячейки, при наличии индекса 2 – ой ячейки просто. Индекс первой ячейки равен индексу второй ячейки + 1, а третей ячейки – -1.

Поскольку результат применения правил к пирамидам из 4 – х ячеек не зависят друг от друга , а система правил приводит любую последовательность из 4-х бит либо к 0000 либо 1111, то система правил была перестроена с этим учетом, т.е. после применения нового правила сразу будет известно ему будет соответствовать 0000 или 1111.
При усечение пирамиды проводиться дополнительная проверка , она состоит из одних нулей или единиц, что позволяет досрочно завершить выполнение программ.

Система новых правил, которая позволяет вычислять за один шаг, последовательности из 4 – х бит советует 0000 или 1111.

0000->0000
0001->0000
0010->0000
0011->0000
0100->0000
0101->0000
1000->0000
1001->0000
0110->1111
0111->1111
1010->1111
1011->1111
1100->1111
1101->1111
1110->1111
1111->1111

Share

Tags:

8 Responses to “Tribit алгоритм описание реализации”

  1. кабина f2000 пишет:

    красиво сделал! Благодарю!!!

  2. Аноним пишет:

    Текст оставил сложное, неоднозначное, впечатление…

  3. this stuff is good пишет:

    Наткнулся случайно на Ваш блог. Теперь стану постоянно просматривать. Надеюсь, не разочаруете и дальше

  4. это не последняя статья по данной тематике

  5. Dima пишет:

    Но Ваш алгоритм не подойдёт для пирамид размером 64, 256 или 1024

  6. Да не будет. Однако, надо оттолкнутся от того что хотим получить на выходе. Универсальный решатель для любых пирамид или решатель для пирамиды фиксированной размерности.

  7. Алексей пишет:

    Если в начале алгоритма инвентировать строку и записывать ее сверху вниз в пирамиду появятся следующие удобные свойства:
    R – строки
    Номер первого символа в строке R*R (обалдел, когда увидел)
    Номер символа в малой пирамиде R mod 4 (остаток от деления) Возможно именно для этого символы в перевернутой пирамиде пронумерованы таким образом)

  8. а для какой размерности пирамиды эти свой свойства рассматривались ?

Leave a Reply