0
А здесь результат по моему не правильный. При сложении двух последних чисел должно получится
1 0110 1000 0000 0000
а не то что на картинке.
Это легко проверяется руками.
  • avatar
  • worker
  • 30 октября 2015, 16:23
0
Для первой таблицы да. Из первой строки получилась вторая.
А теперь попробуй получить третью строку из этой же таблицы таким способом. Ведь таблица устроена так что любую строку можно сделать первой с соответствующим циклическим сдвигом остальных. Все строки при этом остаются, естественно, такими как были. Изменяются только номера этих строк.
То есть попробуй получить третью строку первой таблицы из второй, считая при этом что вторая строка является первой а третья второй.
У меня не получается сделать это твоим способом.
  • avatar
  • worker
  • 30 октября 2015, 16:14
0
Я вижу что жёлтым выделено две строки. Но даже если взять какую либо одну из них всё равно не получается последующей строки из текущей.
  • avatar
  • worker
  • 30 октября 2015, 15:55
0
Предложенный автором алгоритм (если я правильно понял его суть из описания), наверное, можно адаптировать для избыточного кодирования и последующего восстановления поврежденных данных. Хотя там тоже хватает стандартных алгоритмов: код Хемминга, Рида — Соломона
Кстати говоря возможно что и так. Обнаружил ещё одно свойство, это касается таблицы 4.
Её можно полностью восстановить зная значения только семи(а не восьми как раньше) определённых ячеек. С остальными данными пока не проверял.
  • avatar
  • worker
  • 30 октября 2015, 15:49
0
А почему нет(насчёт применимости).
По поводу возникшего вчера спора — да там была моя ошибка. Конечно же там должно было быть примерно равно 2*10^-100.
  • avatar
  • worker
  • 30 октября 2015, 15:25
0
Статью Вильямса про CRC читал. Про вечные двигатели речи не было. Мне лишь показались интересными свойства получаемых таблиц.
Если сможешь подкинуть ещё ссылок на книжки и статьи по этой теме — скажу спасибо.

И эта мистическая операция «a XOR (a>>1)» превращается в обыденное умножение на 0xC0
А тут не понятно. Поясни это утверждение.

И для шифрования — ваще никак.

На это тоже ничего сказать не могу.
  • avatar
  • worker
  • 30 октября 2015, 15:22
0
Допустим шифровка. Поступает последовательность байт. Каждый из байтов сдвинут внутри своей таблицы на определённое число шагов. Для восстановления этого байта нам нужен ключ — число шагов.
Для каждого номера байтов входного потока может быть свой собственный ключ.
Для усложнения можно брать ключи разных размеров — считай выбор размера таблицы — 8х8, 8х16, 16х16, 32х32… и так далее.
Последовательность ключей и их размеров можно комбинировать. Причём можно даже и открытую часть ключа создавать.
ПС. Понятно что методов шифрования и так достаточно. И необходимости в этом большой нет в обычной-обыденной жизни. Но, а если вдруг какой-нибудь бутлоадер захочется сделать с шифрованной прошивкой. А тут пример как его можно реализовать.
  • avatar
  • worker
  • 30 октября 2015, 11:24
0
Тут, я так понимаю, ошибка была? Или я что-то не понял.
\
Да ошибка. Ещё не всё свойства таких таблиц понял.
Там могут быть и нули в инверсии. Главное тут то что инвертируется столбец с номером (n/2 + 1) где n это период повторения и если при этом отсчитывать номер этого столбца(который инвертируется) от первого ненулевого бита, считая слева направо.
  • avatar
  • worker
  • 30 октября 2015, 08:07
0
Даже примерно не равно. Поэтому я так удивился.
256! = 8,5781777534284265411908227168123e+506
256^256 = 3,231700607131100730071487668867e+616

деление первого числа на второе даёт на степень приблизительно равную минус 100.

А в остальном, да, во второй части продолжим, если всё ещё будет интерес.
  • avatar
  • worker
  • 29 октября 2015, 21:12
0
Второй! это не факториал, это знак неравенства…
Так ведь я и написал что примерно равно 2^-100. Числа с такими порядками мало отличаются от нуля, для их практической пользы.

А теперь посчитайте энтропию для 256 чисел, зная что множество является размещением из 256, и каждое записанное число уменьшает количество оставшихся вариантов. Точно так же как каждый вытянутый шар из урны увеличивает наши шансы на угадывание (и уменьшает энтропию) остальных.
С этим согласен, только вот формуле Шеннона это никак не учтено.
В теории сложности Колмогорова уже есть учёт этих вещей. Только вот её я пролистал по диагонали.

лучше допишите статью о чудодейственном XOR. Мне действительно интересно как.
Пишу.
  • avatar
  • worker
  • 29 октября 2015, 20:57
0
И, таки можно было бы сказать да, но всё же нет :)
Вот еще идея из того же разряда: у нас есть 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 бит.
  • avatar
  • worker
  • 29 октября 2015, 20:34
0
Единственно что непонятно в формуле
256!/256^256 != 2^-100.
Откуда там два факториала?
  • avatar
  • worker
  • 29 октября 2015, 20:22
0
Единичное число несжимаемо вообще.
Разговор шёл о 256 битах, а не о единичном числе/бите.
И ты сам привёл формулу Шеннона
256-log2(256)
И в ней нет противоречия самому Шеннону. :)

256!/256^256 != 2^-100.
И? Где тут неземная математика? :)
  • avatar
  • worker
  • 29 октября 2015, 20:21
0
Вот еще идея из того же разряда: у нас есть 256 битное число. Теория Шеннона гласит что записать его можно только на 256 битах
Теория Шеннона будет так гласить только в случае если число единичных и нулевых бит равно
друг другу, поэтому контрпример не подходит.

Опишите детальнее свою математику, есть подозрение что она некоим образом отличается от земной.
А тут очень просто всё — 256 байт неповторяющихся чисел даёт нам 256 факториал комбинаций из них. Общее количество чисел равно 256 в 256-ой степени. Первое разделить на второё и умножить на сто — получим проценты. Вроде как, самая что ни на есть, обычная математика.
  • avatar
  • worker
  • 29 октября 2015, 19:30
0
У энтропии Шеннона есть дыра. Если взять 256 не повторяющихся восьмибитных чисел, то энтропия Шеннона говорит что сжатие невозможно. Но это не так. Я не говорю про случай когда все числа идут строго по возростанию — от 0 до 255. Или же строго по убыванию.Числа могут располагаться в произвольном порядке. Главное чтобы ни одно число не повторялось.
Если известно условие что в блоке из 256 восьмибитных чисел ни одно из них неповторяется, то, считав первые 128 чисел, вторые 128 можно будет закодировать семибитными числами.
В практическом плане это ничего не даёт, так как, число таких 256 байтных блоков с неповторяющимися числами составляет примерно 2 в степени минус 100 процента, от общего количества 256 байтных чисел.
Но, тем не менее «дыра» в формуле Шеннона есть.
  • avatar
  • worker
  • 29 октября 2015, 19:13
0
Самая главная подсказка это операция XOR.
  • avatar
  • worker
  • 29 октября 2015, 16:39
0
Ну, так, я вот почему то подумал что задачка очень простая, оказалось что не так. Поэтому и написал условия-подсказки.
А что — решил задачку?
  • avatar
  • worker
  • 29 октября 2015, 16:25
0
Бабушкин, насколько я знаю, свой архиватор писал с помощью только одного деления двух чисел, каждое из которых должно быть длиной по несколько килобайт.
Ему бы про свойства чисел почитать перед этим. И теорему Ферма заодно доказать. :)
  • avatar
  • worker
  • 29 октября 2015, 16:23
0
Объяснение будет в следующем посте. Сейчас пишу его.
Насчёт практического применения — возможно для шифрования или генерирования случайных чисел. Другого применения я тоже, пока что, не вижу.
Для меня оказались интересными многие свойства этого алгоритма, сами по себе.
  • avatar
  • worker
  • 29 октября 2015, 15:09
0
Мне эта задачка показалась очень простой. Дополнительные свойства таблицы я добавил в пост.
  • avatar
  • worker
  • 29 октября 2015, 14:34