А здесь результат по моему не правильный. При сложении двух последних чисел должно получится
1 0110 1000 0000 0000
а не то что на картинке.
Это легко проверяется руками.
Для первой таблицы да. Из первой строки получилась вторая.
А теперь попробуй получить третью строку из этой же таблицы таким способом. Ведь таблица устроена так что любую строку можно сделать первой с соответствующим циклическим сдвигом остальных. Все строки при этом остаются, естественно, такими как были. Изменяются только номера этих строк.
То есть попробуй получить третью строку первой таблицы из второй, считая при этом что вторая строка является первой а третья второй.
У меня не получается сделать это твоим способом.
Предложенный автором алгоритм (если я правильно понял его суть из описания), наверное, можно адаптировать для избыточного кодирования и последующего восстановления поврежденных данных. Хотя там тоже хватает стандартных алгоритмов: код Хемминга, Рида — Соломона
Кстати говоря возможно что и так. Обнаружил ещё одно свойство, это касается таблицы 4.
Её можно полностью восстановить зная значения только семи(а не восьми как раньше) определённых ячеек. С остальными данными пока не проверял.
А почему нет(насчёт применимости).
По поводу возникшего вчера спора — да там была моя ошибка. Конечно же там должно было быть примерно равно 2*10^-100.
Статью Вильямса про CRC читал. Про вечные двигатели речи не было. Мне лишь показались интересными свойства получаемых таблиц.
Если сможешь подкинуть ещё ссылок на книжки и статьи по этой теме — скажу спасибо.
И эта мистическая операция «a XOR (a>>1)» превращается в обыденное умножение на 0xC0
Допустим шифровка. Поступает последовательность байт. Каждый из байтов сдвинут внутри своей таблицы на определённое число шагов. Для восстановления этого байта нам нужен ключ — число шагов.
Для каждого номера байтов входного потока может быть свой собственный ключ.
Для усложнения можно брать ключи разных размеров — считай выбор размера таблицы — 8х8, 8х16, 16х16, 32х32… и так далее.
Последовательность ключей и их размеров можно комбинировать. Причём можно даже и открытую часть ключа создавать.
ПС. Понятно что методов шифрования и так достаточно. И необходимости в этом большой нет в обычной-обыденной жизни. Но, а если вдруг какой-нибудь бутлоадер захочется сделать с шифрованной прошивкой. А тут пример как его можно реализовать.
Тут, я так понимаю, ошибка была? Или я что-то не понял.
\
Да ошибка. Ещё не всё свойства таких таблиц понял.
Там могут быть и нули в инверсии. Главное тут то что инвертируется столбец с номером (n/2 + 1) где n это период повторения и если при этом отсчитывать номер этого столбца(который инвертируется) от первого ненулевого бита, считая слева направо.
Так ведь я и написал что примерно равно 2^-100. Числа с такими порядками мало отличаются от нуля, для их практической пользы.
А теперь посчитайте энтропию для 256 чисел, зная что множество является размещением из 256, и каждое записанное число уменьшает количество оставшихся вариантов. Точно так же как каждый вытянутый шар из урны увеличивает наши шансы на угадывание (и уменьшает энтропию) остальных.
С этим согласен, только вот формуле Шеннона это никак не учтено.
В теории сложности Колмогорова уже есть учёт этих вещей. Только вот её я пролистал по диагонали.
лучше допишите статью о чудодейственном XOR. Мне действительно интересно как.
И, таки можно было бы сказать да, но всё же нет :)
Вот еще идея из того же разряда: у нас есть 256 битное число. Теория Шеннона гласит что записать его можно только на 256 битах, но если узнать что число всегда состоит из 255 нулей и одной единицы на случайной позиции, то я смогу сжать это число на 256-log2(256) бит! ДЫРА!!!!11111
в этом случае выражение энтропии по Шеннону будет выглядеть так
-255*log2(255/256) — 1*log2(1/256) = 255*0.0056466 + 1*8 = 1,439883 + 8 = 8,439883 бит для кодирования всех 256 бит.
Вот еще идея из того же разряда: у нас есть 256 битное число. Теория Шеннона гласит что записать его можно только на 256 битах
Теория Шеннона будет так гласить только в случае если число единичных и нулевых бит равно
друг другу, поэтому контрпример не подходит.
Опишите детальнее свою математику, есть подозрение что она некоим образом отличается от земной.
А тут очень просто всё — 256 байт неповторяющихся чисел даёт нам 256 факториал комбинаций из них. Общее количество чисел равно 256 в 256-ой степени. Первое разделить на второё и умножить на сто — получим проценты. Вроде как, самая что ни на есть, обычная математика.
У энтропии Шеннона есть дыра. Если взять 256 не повторяющихся восьмибитных чисел, то энтропия Шеннона говорит что сжатие невозможно. Но это не так. Я не говорю про случай когда все числа идут строго по возростанию — от 0 до 255. Или же строго по убыванию.Числа могут располагаться в произвольном порядке. Главное чтобы ни одно число не повторялось.
Если известно условие что в блоке из 256 восьмибитных чисел ни одно из них неповторяется, то, считав первые 128 чисел, вторые 128 можно будет закодировать семибитными числами.
В практическом плане это ничего не даёт, так как, число таких 256 байтных блоков с неповторяющимися числами составляет примерно 2 в степени минус 100 процента, от общего количества 256 байтных чисел.
Но, тем не менее «дыра» в формуле Шеннона есть.
Бабушкин, насколько я знаю, свой архиватор писал с помощью только одного деления двух чисел, каждое из которых должно быть длиной по несколько килобайт.
Ему бы про свойства чисел почитать перед этим. И теорему Ферма заодно доказать. :)
Объяснение будет в следующем посте. Сейчас пишу его.
Насчёт практического применения — возможно для шифрования или генерирования случайных чисел. Другого применения я тоже, пока что, не вижу.
Для меня оказались интересными многие свойства этого алгоритма, сами по себе.
1 0110 1000 0000 0000
а не то что на картинке.
Это легко проверяется руками.
А теперь попробуй получить третью строку из этой же таблицы таким способом. Ведь таблица устроена так что любую строку можно сделать первой с соответствующим циклическим сдвигом остальных. Все строки при этом остаются, естественно, такими как были. Изменяются только номера этих строк.
То есть попробуй получить третью строку первой таблицы из второй, считая при этом что вторая строка является первой а третья второй.
У меня не получается сделать это твоим способом.
Её можно полностью восстановить зная значения только семи(а не восьми как раньше) определённых ячеек. С остальными данными пока не проверял.
По поводу возникшего вчера спора — да там была моя ошибка. Конечно же там должно было быть примерно равно 2*10^-100.
Если сможешь подкинуть ещё ссылок на книжки и статьи по этой теме — скажу спасибо.
А тут не понятно. Поясни это утверждение.
На это тоже ничего сказать не могу.
Для каждого номера байтов входного потока может быть свой собственный ключ.
Для усложнения можно брать ключи разных размеров — считай выбор размера таблицы — 8х8, 8х16, 16х16, 32х32… и так далее.
Последовательность ключей и их размеров можно комбинировать. Причём можно даже и открытую часть ключа создавать.
ПС. Понятно что методов шифрования и так достаточно. И необходимости в этом большой нет в обычной-обыденной жизни. Но, а если вдруг какой-нибудь бутлоадер захочется сделать с шифрованной прошивкой. А тут пример как его можно реализовать.
Да ошибка. Ещё не всё свойства таких таблиц понял.
Там могут быть и нули в инверсии. Главное тут то что инвертируется столбец с номером (n/2 + 1) где n это период повторения и если при этом отсчитывать номер этого столбца(который инвертируется) от первого ненулевого бита, считая слева направо.
256^256 = 3,231700607131100730071487668867e+616
деление первого числа на второе даёт на степень приблизительно равную минус 100.
А в остальном, да, во второй части продолжим, если всё ещё будет интерес.
С этим согласен, только вот формуле Шеннона это никак не учтено.
В теории сложности Колмогорова уже есть учёт этих вещей. Только вот её я пролистал по диагонали.
Пишу.
в этом случае выражение энтропии по Шеннону будет выглядеть так
-255*log2(255/256) — 1*log2(1/256) = 255*0.0056466 + 1*8 = 1,439883 + 8 = 8,439883 бит для кодирования всех 256 бит.
Откуда там два факториала?
И ты сам привёл формулу Шеннона
И в ней нет противоречия самому Шеннону. :)
И? Где тут неземная математика? :)
друг другу, поэтому контрпример не подходит.
А тут очень просто всё — 256 байт неповторяющихся чисел даёт нам 256 факториал комбинаций из них. Общее количество чисел равно 256 в 256-ой степени. Первое разделить на второё и умножить на сто — получим проценты. Вроде как, самая что ни на есть, обычная математика.
Если известно условие что в блоке из 256 восьмибитных чисел ни одно из них неповторяется, то, считав первые 128 чисел, вторые 128 можно будет закодировать семибитными числами.
В практическом плане это ничего не даёт, так как, число таких 256 байтных блоков с неповторяющимися числами составляет примерно 2 в степени минус 100 процента, от общего количества 256 байтных чисел.
Но, тем не менее «дыра» в формуле Шеннона есть.
А что — решил задачку?
Ему бы про свойства чисел почитать перед этим. И теорему Ферма заодно доказать. :)
Насчёт практического применения — возможно для шифрования или генерирования случайных чисел. Другого применения я тоже, пока что, не вижу.
Для меня оказались интересными многие свойства этого алгоритма, сами по себе.