Интересное (на мой взгляд) свойство ХОR - продолжение.

Интересное свойство операции XOR.
В предыдущий раз я не совсем удачно, видимо, задал задачку. Раскрываем свои краплёные карты.
Для затравки приведу несколько заполненных таблиц, и в каждой из них отмечу некоторые ячейки.






Так вот, я утверждаю что, зная способ формирования таблиц, и зная способ выбора ячеек – можно однозначно восстановить каждую из этих таблиц. Причём ячейки для восстановления можно выбрать множеством способов.
Формируются эти таблицы по такому правилу
m[row+1] = m[row] ^ (m[row] >>1);
row – это номер строки;
^ — операция XOR;
>> — операция побитового сдвига, выдвинутый бит отбрасывается;

Каждое последующее число таблицы получается с помощью выполнения операции XOR между самим числом, и, его копией сдвинутой на один бит вправо. Для формирования такой таблицы нужно знать любую из строк.

Суть в том, что такая операция обладает периодичностью.

Для вычисления периода повторения, надо посчитать число бит до последнего не нулевого бита. Счёт нужно вести справа налево, начиная с нулевого разряда. Полученное число нужно дополнить до ближайшей, большей степени двойки. Например, если получилось число 7, то период будет равен 8. Если получилось число 38, то период будет равен 64. И так далее. Если же, при пересчёте, уже получилось число равное целой степени двойки, то, нужно взять само это число.
Также, период можно описать формулой: T = log2(n+1) где T – период, n – вес разряда двоичного числа, в котором находится последняя единица, при движении по числу справа налево. При этом если получается целая степень двойки то так и оставляем, если нет то доводим до ближайшей, большей, степени двойки.
Это справедливо для чисел с произвольным количеством разрядов.
Интересным свойством полученных, таким образом, таблиц является возможность восстановления таблицы целиком по заранее определенному способу выбора ячеек. В простом случае восстановить таблицу можно зная целиком произвольную строку, или зная целиком последний столбец.

Для примера восстановим Таблицу 1, зная только выделенные биты, зная способ выбора этих битов и зная способ формирования таблицы.


И так, у нас есть последовательность бит 10100010, составленная из содержимого выделенных ячеек. Нам известен способ выбора этих битов из таблицы, расставим их:


Дальше, зная способ формирования таблицы заполним первый столбец единичками:

В пятой строке получили последовательность бит 10. Это двухбитное число, период повторения у такого числа равен 2. Выполняя последовательно операцию для этого числа m[row+1] = m[row] ^ (m[row] >>1) заполним второй столбец:


В третьей строке получили последовательность 111, повторим действия предыдущего шага для этой строки и заполним третий столбец:

В общем уже должно быть понятно как заполнить все остальные столбцы этой таблицы.

Попробуем восстановить Таблицу 2.

Итак, у нас есть последовательность бит 11100100. И нам известен способ выбора этих бит из таблицы, расставим их в этой таблице:


Зная значения ячеек определённого столбца Coll длины N, можно в столбце (Coll – 1) восстановить (N-1) ячеек. Сделаем это. Для этого нужно помнить о том как формировались строки таблицы. Каждая последующая строка получалась с помощью операции XOR самого числа и его сдвинутой на один бит вправо копией. Проделаем это с произвольным числом:

Из этого примера можно понять как восстановить ячейку Ceil[n][n], зная значения ячеек Ceil[n+1][n] и Ceil[n+1][n+1]. Надо проделать операцию XOR между этими ячейками. Сделаем это для Таблицы 2:

Проделаем это для следующей пары:


И для ещё одной:


Таким образом восстановили часть третьего столбца.
Таким же образом восстановим части сначала второго а затем и первого столбцов:


А дальше, опять же зная способ формирования таблицы восстановим первые пять столбцов, выполняя операцию m[row+1] = m[row] ^ (m[row] >>1) для первых пяти уже известных элементов строки:



Получили в последней строке уже шесть элементов, повторим XOR со сдвинутой вправо на один бит своей копией и получим первые шесть элементов первой строки.
Дальнейший ход я думаю понятен.

Отдельным рядом тут стоит Таблица 4. Она формируется немного по-другому. Неинтересно ведь когда первый столбец всегда равен нулю или единице. Поэтому в Таблице 4 неявно присутствует девятый бит – единичный. То есть присутствует неявный первый столбец, который, целиком, состоит из единичек. Правда период повторения при этом станет равен 16. Но, зато числа, которые начинаются с нуля/нулей, тоже будут иметь период равный 16. Иначе, невозможно было бы получить таблицу, содержащую строку заполненную нулями. И само число нуль имело бы период равный нулю.
Так же можно добавить произвольное число бит перед таблицей и получить совершенно другой набор значений. Или добавить в качестве неявного первого столбца произвольное число. Период повторения значений в таблице при этом изменится. Но, если сама таблица останется квадратной, то, её всё также можно будет восстановить по выбранным, определённым способом ячейкам.

Перечислять все свойства, полученных таким образом таблиц, я думаю не хватит нескольких страниц. Да и я сам их не все знаю. В общем пока что всё.
  • -1
  • 30 октября 2015, 01:57
  • worker

Комментарии (87)

RSS свернуть / развернуть
Последние четыре элемента пятой строки являются инверсией первых четырёх элементов пятой строки, если только все эти элементы не нулевые
Тут, я так понимаю, ошибка была? Или я что-то не понял.

Я как-то так и думал, только не решил, что делать с заимствованием из «нулевого» столбца. Тупо брать ноль показалось неинтересным вариантом и я не стал его рассматривать.

Могу предложить более интересный, на мой вкус, вариант.
m[row+1] = ROR(m[row],1) ^ m[row] ^ ROL(m[row],2), где ROL и ROR — циклические сдвиги влево и вправо.
Т.е. ксорируем три ячейки: 1) на одну клетку выше, 2) на одну выше и левее, 3) на одну выше и на 2 правее. При вылезании на крайние столбцы — зацикливаемся.

Преимущества:
— Избавляемся от некрасивых столбцов сплошных единиц и нулей;
— Таблица получается полностью зациклена, как по строкам, так и по столбцам (если число столбцов четное, при нечетном — не уверен);
— Получаем интересный эффект, строки, идущие через половину высоты таблицы — равны, только переставлены местами первая и вторая их часть (т.е. для таблицы 8х8 строка 5 равна строке 1 с переставленными местами нибблами);
— Аналогично для столбцов. Таким образом левая верхняя четверть таблицы равна правой нижней, а правая верхняя — левой нижней;
— Свойство восстановимости по одному (любому) столбцу — имеется (для 8х8 — проверил. Полагаю, сработает и для других размеров). По более сложным паттернам — наверняка тоже, надо выбирать. По диагонали, правда, уже не выходит, мешает предыдущее свойство.

Ну и думаю можно продолжить, аналогично, на несколько страниц. Только зачем? :)

PS Забавно, в M$ офисе 2к3 нет ф-ции xor. Появилась только в 2к13.
0
  • avatar
  • ACE
  • 30 октября 2015, 05:32
Тут, я так понимаю, ошибка была? Или я что-то не понял.
\
Да ошибка. Ещё не всё свойства таких таблиц понял.
Там могут быть и нули в инверсии. Главное тут то что инвертируется столбец с номером (n/2 + 1) где n это период повторения и если при этом отсчитывать номер этого столбца(который инвертируется) от первого ненулевого бита, считая слева направо.
0
Честно говоря, силился понять, а для чего это нужно? Так и не понял. Каково применение на практике?
Например, XOR хорошо вписывается для того, чтобы восстанавливать ячейки памяти в 9-ти битных байтах, где в каждом байте 9-бит аппаратно вычисляется четность в момент записи. В самом конце массива данных хранится контрольная сумма, которая тоже формируется при каждой записи байтов в массиве. Значение контрольной суммы — тупой XOR всех значений массива. Если случается так, что какой-то бит выпадает, то он сначала локализуется по ячейке благодаря четности, а потом с помощью контрольной суммы восстанавливается исходное значение байта. Вот это круто, а что здесь?
0
Допустим шифровка. Поступает последовательность байт. Каждый из байтов сдвинут внутри своей таблицы на определённое число шагов. Для восстановления этого байта нам нужен ключ — число шагов.
Для каждого номера байтов входного потока может быть свой собственный ключ.
Для усложнения можно брать ключи разных размеров — считай выбор размера таблицы — 8х8, 8х16, 16х16, 32х32… и так далее.
Последовательность ключей и их размеров можно комбинировать. Причём можно даже и открытую часть ключа создавать.
ПС. Понятно что методов шифрования и так достаточно. И необходимости в этом большой нет в обычной-обыденной жизни. Но, а если вдруг какой-нибудь бутлоадер захочется сделать с шифрованной прошивкой. А тут пример как его можно реализовать.
0
С шифровкой согласен. Чем более запутанней алгоритм шифрования, тем он более надежен
-1
Чем более запутанней алгоритм шифрования, тем он более надежен

Это не так, скорее даже наоборот. Самый надежный шифр это шифр Вернама – который прост до безобразия и представляет собой простой XOR текста со случайным числом, которое и является ключом. Не смотря на простоту, это абсолютное оружие в мире криптографии, этот шифр неуязвим (правда число должно быть достаточно «случайным» и нельзя повторно использовать ключ, поэтому шифр и не удобен в повсеместном применении). А изобретение своих алгоритмов шифрования – это заведомо плохая идея.

Предложенный автором алгоритм (если я правильно понял его суть из описания), наверное, можно адаптировать для избыточного кодирования и последующего восстановления поврежденных данных. Хотя там тоже хватает стандартных алгоритмов: код Хемминга, Рида — Соломона
+1
Предложенный автором алгоритм (если я правильно понял его суть из описания), наверное, можно адаптировать для избыточного кодирования и последующего восстановления поврежденных данных. Хотя там тоже хватает стандартных алгоритмов: код Хемминга, Рида — Соломона
Кстати говоря возможно что и так. Обнаружил ещё одно свойство, это касается таблицы 4.
Её можно полностью восстановить зная значения только семи(а не восьми как раньше) определённых ячеек. С остальными данными пока не проверял.
0
Вот раньше применяли абсолютно не расшифруемый алгоритм — берешь второй том Войны и Мира:
55555 страница 555, 5 строка сверху, 5 символ с начала строки
44444 страница 444, 4 строка снизу, 4 символ с начала второго слова (добавили запутанность)


естественно для разных сообщений надо выбирать разные книги…
это вам не в таблицы играть :)
0
такие способы шифрования действительно применялись в прошлом веке, нужно, чтобы у двух сторон была определенная книга. И с кодом Вернама тоже согласен, однако все это не практично, особенно в современных условиях. Где шифровать нужно много и часто. Поэтому ключей на всех не напасешься… А ведь один должны сохраняться в секрете. т.е. каким-то способом однократно передаваться. По поводу картинки: Под самой нижней единичкой — бомба!))
0
Вот раньше применяли абсолютно не расшифруемый алгоритм — берешь второй том Войны и Мира:
Я бы с данным утверждением поспорил. Устойчивость алгоритма весьма посредственная по меркам сегодняшних дней. «Раньше» не было таких таких мощностей для брута. Разумеется если в качестве ключа не был использован второй том «Мёртвых душ»
0
Для восстановления этого байта нам нужен ключ — число шагов.
Для каждого номера байтов входного потока может быть свой собственный ключ.
Поздравляю, вы изобрели шифр Виженера! Незаменимое криптосредство для пионерской игры в «Зарницу» (Октябрята играют с шифром Цезаря). Но вот насчёт применимости в бутлоадере есть некоторые сомнения…
0
А почему нет(насчёт применимости).
По поводу возникшего вчера спора — да там была моя ошибка. Конечно же там должно было быть примерно равно 2*10^-100.
0
Потому что это не «шифрование» в современном смысле. Расшифровывается за час. В 2010 году модификация бутлоадера для Атмеги чтобы использовать AES128 мне заняла один день.
0
+1. Восстановление данных через XOR, так называемая технология ChipKill от IBM, повсеместно применяется во всех устройствах на NAND Flash памяти: у данных, хранящихся в ней, есть замечательное свойство гнить. Без чипкилла мы бы до сих пор дискетами и HDD пользовались.
0
угу… по твоему флешки вечны и не вечны одновременно?
Чисто для Справки — о Flash памяти: у данных, хранящихся в ней, есть замечательное свойство храниться без гниения… для примера у меня есть данные, хранящиеся более 30-ти лет в флешпамяти КР1601РР1 (К1601РР2 оказалась менее долгоживучей из-за конструктивных недостатков… золотой корпус не выдержал лихих 90-х)…
но есть техническое свойство — количество циклов перезаписи (100 000… 1 000 000 000), приводящее к деградации материала и возникновению неисправимых ошибок в основной и контрольной памятях.
Технологии Обнаружения и Исправления ошибок применяется в вычислительной технике с давних времён — как для оперативной, так и для дисковой памяти… не панацея, так как есть вероятность порчи контрольной памяти, которую опять надо проверять…
Поэтому флешевые диски при активной перезаписи менее долгогживущие по сравнению с качественными HDD…
а мифическая технология ChipKill от IBM просто закрывает доступ к ещё оставшимся истинным данным по своей воле = УбиваетЧип
0
Вы бы хоть про ChipKill почитали для начала.
Не надо мне про флэш память рассказывать. Я почти пять лет на SanDisk инженерил, а это 50% мирового рынка SD, eMMC, SSD и прочих менее известных накопителей на флэш памяти. Наверняка в Вашем смарте стоит карточка и встроенная eMMC, в прошивке которой работает и мой код. И да, в ней обязательно используется ChipKill.
+1
я сандиск разбирал, когда ты под стол пешком ходил… не видел там твоего кода :)
-1
ChipKill?… ChipLive!!!
-1
Ох уж эти изобретатели вечных двигателей с глазами горящими )) Все уже украдено до вас.
Рекомендую почитать про «полиномиальную арифметику по модулю 2», просто про «арифметику по модулю 2» и применение этой арифметики в расчете CRC.
Например: www.info-system.ru/library/algo/crc1.pdf

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

И для шифрования — ваще никак.
0
Статью Вильямса про CRC читал. Про вечные двигатели речи не было. Мне лишь показались интересными свойства получаемых таблиц.
Если сможешь подкинуть ещё ссылок на книжки и статьи по этой теме — скажу спасибо.

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

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

На это тоже ничего сказать не могу.
0
Как происходит умножение в столбик обычных чисел?
По модулю 2 точно так же, только вместо сложения — XOR

xxxxxxxx — первая строка таблицы
Желтым цветом — вторая строка
0
Я вижу что жёлтым выделено две строки. Но даже если взять какую либо одну из них всё равно не получается последующей строки из текущей.
0
Ну как же. Возьмем первую строку первой таблицы

Получилась вторая строка?
0
Для первой таблицы да. Из первой строки получилась вторая.
А теперь попробуй получить третью строку из этой же таблицы таким способом. Ведь таблица устроена так что любую строку можно сделать первой с соответствующим циклическим сдвигом остальных. Все строки при этом остаются, естественно, такими как были. Изменяются только номера этих строк.
То есть попробуй получить третью строку первой таблицы из второй, считая при этом что вторая строка является первой а третья второй.
У меня не получается сделать это твоим способом.
0
0
А здесь результат по моему не правильный. При сложении двух последних чисел должно получится
1 0110 1000 0000 0000
а не то что на картинке.
Это легко проверяется руками.
0
Ты читал про «арифметику по модулю 2» и ссылочку из первого комментария? Что там используется вместо сложения?
0
Понятно. Я складывал обычным образом. Ты прав.
0
Но, способность к «самовосстановлению» у таких таблиц всё же интересна.
0
Это потому, что во всей таблице только 8 значений и есть.
+1
Для 9 битных чисел(16 элементов в таблице) тоже сходится по способу от steel_ne.
0
По поводу вечных двигателей. Подход «а скомпонуем что-нибудь, а потом будем исследовать» — в принципе как основа индуктивного шага пойдет, но как самоцель — нет. Это сроди поиску в числе π имени бога, а заодно котировок эппла на пять лет вперед.

Когда видно, что эта операция — это просто умножение на константу, то автоматически становится понятна зависимость между строками таблиц (линейная). И найти предыдущую строку уже несложно без рассуждений о периодичности.

А если глянуть дальше в сторону периодичности — ба, да у нас же линейный конгруэнтный генератор, правда с дурацкими коэффициентами, и т.д.
0
Тоже генераторы вспомнились. Вот есть новая игрушка PCG, так она мало того что дайхард проходит со свистом, еще и позволяет вплетать свои последовательности в псевдослучайный ряд. Берёшь такой ГПСЧ, он год работает как надо, а потом вдруг человеческим голосом выдает ОЛОЛО, Я КРЕВЕДКО, ПЫШЬ ПЫШЬ РЕАЛЬНЕ МЖВЯЧНЕ РАНДОМНЕ. Причём код простейший.
0
Сейчас проверил — для первых трёх таблиц(период 8) достаточно 6 определённым образом выбранных ячеек для полного восстановления, для четвёртой таблицы (период 16) нужно знать 7 ячеек для полного восстановления таблицы.
0
Это при каких условиях на значения в первой строке?
0
Для первой из таблиц, нужно выделить ячейки, например, таким образом:

При восстановлении нужно помнить, что, в столбце с номером (N/2 + 1) нижние четыре элемента это инверсия верхних четырёх элементов. В столбце с номером N нижние четыре элемента повторяют верхние четыре элемента. N это период повторения. Обладая только этой информацией уже можно восстановить содержимое помеченных ячеек на следующем рисунке:

И так как период равен восьми, то, и первый столбец нам известен, весь первый столбец заполнен единичками:


Дальше нужно выяснить значение второго элемента шестой строки. Просто предполагаем одно из значений ноль или единица. И подставляем это значение в эту ячейку. Получаем строку из шести элементов. И вычисляем следующие строки по правилу m[i+1] = m[i]^(m[i]>>1), выдвигаемый бит при этом в седьмой столбец не заносим. Так вот если неправильно выбрать значение второго элемента шестой строки, то на одном из шагов получим противоречие с уже выясненными элементами таблицы. Значит туда надо подставить противоположное значение.
При вычислении следующих строк надо помнить о том что на третьем шаге происходит перемещение на первую строку таблицы.
По крайней мере на четырёх приведённых таблицах это сработало.
На четвёртой таблице нужно помнить что есть неявный первый столбец заполненный единичками.
0
Блин, пардон, напутал я с шестой строкой. Поторопился и напутал, только не с тем что восстановление возможно. Оно возможно с шестью элементами. Только шестая строка на втором шаге не восстанавливается. Восстанавливается седьмая строка, кроме второго бита в ней.
Сейчас перепишу.
0
В общем на втором шаге должна получиться такая таблица^

Дальнейшие рассуждения такие-же, только относящиеся к седьмой строке.
0
И, ещё, про период — у таблицы несколько частей имеют собственные периоды. Первые два столбца имеют период 2, первые 4 столбца имеют период 4, первые 8 столбцов имеют период 8 и так далее. Это нужно иметь ввиду при вычислении номера столбца с инверсиями «половинок».
0
И снова здарова, блин :).
Ещё нужно отметить как вычисленную ячейку с позицией[5][5]. Так как она является инверсией ячейки с позицией [1][5].
0
Честно говоря мне уже лень разбирать ошибки.
1. В таблице 4 в первой колонке чередуются 0 и 1. Почему? Что с чем XOR? А почему в третьей таблице в первом столбце единица?
Если мы что хотим, то и ставим в первой колонке, то тогда ой.

2. Если в таблице информации 8 бит (в чем я уже сомневаюсь в силу п.1), то при фиксации шести ячеек будет как минимум 4 таблицы с фиксированными ячейками. Например, навскидку, такая таблица тоже удовлетворяет критериям


Остальные сам найди.
0
А, пропустил пассаж про девятый бит. Ну тогда ваще жопа ) В таблице 9 бит информации и фиксируя только 8 — получим две разные таблицы для каждого набора зафиксированных бит.
Причем наборы бит нельзя брать произвольные, даже для случая «8 из 8». А то и там можно потерять информацию.
0
Да, ты частично прав. Нагородил я огород.(рука-лицо) С 6 битами для первых трёх таблиц восстановление невозможно.Также как и с 7 битами для четвёртой.
Но, первые три таблицы всё-же можно восстановить зафиксировав только 7 определенных ячеек(например на последнем столбце) — первый столбец известен. А четвёртую таблицу можно восстановить по 8 ячейкам.
0
А чего это он известен? Известен «девятый бит», который мы вдвигаем. И певый бит числа — не обязательно единица.
На пальцах — если мы возмем в последнем столбце семь бит кроме первой строки, то не узнаем ничего про последний бит числа, а если пропустим последнюю строку, то неопределенный будет первый бит.

Да, если я опять пропустил условие на то, что первый бит фиксированно 1, то таблица содержит 7 бит информации и противоречия нет, ее можно восстановить по 7 ячейкам.
Причем ячейки нельзя брать произвольно — например во второй таблице в первой строке последние три ячейки могут быть произвольные, они не влияют на отмеченные ячейки.
Это означает, что выбранные ячейки взаимозависимы и информации мы получили меньше 8 (7?) бит и всю таблицу однозначно не восстановить.
0
Пойми просто одну вещь (и смирись с ней :) магический XOR не может увеличивать количество информации. Он ее планомерно уничтожает (как впрочем и любая операция, у которой на входе 2 бита, а на выходе — 1). Но в отличии то AND, например, он симметричный. Если бы мы брали вместо XOR AND, то в некоторых ситуациях казалось бы можно было «восстановить информацию по одному биту» — если результат 1, то явно оба операнда тоже 1. Но это можно сделать в одном случае из четырех. В остальных случаях AND не несет никакой информации об операндах(!)
XOR в этом плане более симметричный — в каждом случае он отжирает всего половину информации. На входе два бита, на выходе — один. Но на входе может быть меньше двух бит информации.

Например, однобитовые переменные A B C, независимые, содержат в себе полноценный бит новой информации.
D = A XOR B — он тоже вроде бы содержит один бит, это «старая» информация, принадлежащая (A B). Если рассмотреть (A B D) — то в этой триаде содержится все те же два бита информации. XOR не может добавить. И в (A D) и в (B D) содержатся эти же два бита.
Возьмем E = A XOR B XOR C
Если рассмотреть триаду (C D E), то в ней оказывается всего два бита — С полноценный бит, а D и E — делят еще один бит, потому что они взаимосвязаны через C (E = D XOR C). И по значениям (C D E) однозначно восстановить (A B C) — не получится.
А если взять (A D E) — то тут три бита, все норм.
+2
Спасибо за подробные объяснения.
Так то я не вёл речь о сжатии данных с помощью этих таблиц. Повторюсь — мне показалось очень интересным то что сами по себе эти таблицы можно восстановить целиком, зная только содержимое определённого набора ячеек.
ПС. И всё таки во всех четырёх таблицах восстановление только лишь по шести ячейкам возможно, в других таблицах пока не проверял. Проверил на двух таблицах 16х16 — в них «самовосстановление» возможно при знании только 12 ячеек. Правда при этом сильно падает диапазон выбираемых ячеек. Но, это возможно. И повторюсь я даже «не заикаюсь» тут о том что это как то поможет сжимать данные. Сам факт «самовосстановления» интересен. И это, скорее, к жанру математических фокусов относится, а не к какой-то серьёзной теории.

За объяснения, ещё раз, спасибо.
0
И, дополню, в качестве «бреда». Сжатие было бы возможно если бы при добавлении
каждой новой восьмёрки бит к первой строке — сохранялась бы определённая закономерность, позволяющая «удалять» по два бита с каждого нового восьмибитного набора столбцов. Но, это вряд-ли возможно.
Для начала тут надо проверить, сохраняется ли закономерность, для всех возможных таблиц 8х8 (их всего 32 штуки), потом проверить для всех возможных таблиц 16х16(таких таблиц 4096) и так далее.
Ради удовлетворения своего интереса проделаю это, как будет время. Хотя и уверен что это ни к чему интересному не приведёт.
0
Восстановление по 8 битам таблицы, сгенеренной из одного байта — не сильно-то удивительная штука.
0
На самом то деле по шести ячейкам восстановление такого-же плана. Если рассуждать — то получается всего 32 шестибитных числа по которым можно восстановить соответствующие таблицы 8х8, то есть всего 32 значения. Для таблиц 16х16, если предполагать что определённая закономерность подходит к ним ко всем. То получается что во второй половине таблицы будет не больше чем 64 значения — для её «восстанавливающих» шести элементов. Но, это противоречит тому что всего есть 4096 таблиц размерностью 16х16. А «восстанавливающих» комбинаций всего 32*64 = 2048. То есть либо не во всех таблицах 16х16 соблюдается закономерность которую я увидел в двух, либо будут коллизии. Скорее всего первое.

А по шести элементам в таблицах 8х8 возможно восстановление вот так. По первой таблице:

Тут используется факт того что часть строки и часть пересекающей диагонали повторяют друг друга. Выделено красным. Зелёное — это то что известно. Привести любую другую таблицу к такому виду возможно(так чтобы пересечение было именно на четвёртой строке) — лишь бы было повторение части строки пересекающей её частью диагонали. Так как в таблицах можно циклически сдвигать элементы — потому что таблицы имеют свой «период» повторения.

Четвёртая таблица:

А тут при восстановлении надо помнить что «период» этой таблицы равен 16, то есть эта таблица всего лишь часть другой таблицы с размером 8х16.
0
На прошлой неделе у меня мысли просто перескочили с одного на другое и я перепутал
всё, а дальше уже думал что по 6 элементам восстановление таки невозможно. А всё -таки возможно.
0
Если возможно восстановление по 6 значениям — значит, либо есть ограничения на первую строку (и она содержит реально лишь 6 бит), либо недостающие два бита закодированы координатами ячеек.
0
А по шести элементам в таблицах 8х8 возможно восстановление вот так. По первой таблице:
По зеленой части первая таблица не восстанавливается. Заданному футпринту соответствуют таблицы с начальными строками 00001010, 01101100, 10100000, 11000110.
+1
Для первой таблицы просто надо знать что первый столбец полностью единичный, а второй столбец состоит из последовательности единиц и нулей. Один из элементов второго столбца восстанавливается по зеленой части, с учётом знания о совпадении строки с диагональю.
0
Т.е. второй столбец это всегда либо последовательность 10 либо 01.
0
Имеется ввиду только часть строки и часть диагонали, не полные.
0
Я уже не знаю как объяснить. Если задано информации меньше, то мы можем восстановить какую-то таблицу. И эта таблица будет удовлетворять условию a(i) = a(i) XOR a(i-1)
Но это будет одна таблица из нескольких возможных. И если я загадаю другую таблицу, с теми же фиксированными ячейками, то «алгоритм восстановления» промахнется.

Например, в таблице на картинке синие ячейки вообще не влияют на зеленые и могут быть выбраны произвольно. О каком восстановлении идет речь?
+2
Эта таблица всёго лишь часть таблицы 8х16. Плюс первый неявный столбец состоящий из единичек. Исходя из этого синие ячейки восстановимы. Как и вся таблица.
И тут речь не про произвольно загаданные таблицы а определённым образом сформированные.
0
Эта таблица всёго лишь часть таблицы 8х16
То есть если продолжить эту таблицу — то 17 строка будет повторением первой строки и в итоге повторится вся таблица.
0
И, кстати говоря — если, вдруг, какая либо строка полностью повторяет пересекающую
, в последнем элементе, диагональ — то восстановление будет возможным только по четырём элементам. Но, это нужно проверять. У меня пока времени нет.
0
имеется ввиду строка и диагональ целиком а не частично.
0
И, ещё, такое восстановление будет возможным даже если первые элементы соответственно в строке и диагонали отличаются.
0
Не, удержусь :), интересная «хрень» получилась. :)
0
Ведь если это возможно, то, это можно будет применить и (ЛОЛ над собой) к сжатию. :).
0
Прошло 2 часа времени. Ресурс замерший. Это чего?
Все бросились проверять идею что-ли? :)))
0
Я сам, к сожалению, пока проверить не могу. Только вечером, после работы.
0
Твои слова можно трактовать одним из двух вариантов:
1) Ты накладываешь ограничения на значения первой строки. То есть она не может принимать все 256 значений. Тогда количество возможных таблиц сокращается с 256 до 64, из них можно выбрать одну по 6 битам.
2) Ты просто ошибаешься и твой метод восстанавливает только один вариант из 4 возможных (т.е. восстановление не однозначное).

Но заданным условиям:
1) t[0] = X; t[i+1] = t[i] ^ (t[i] >> 1), i=[0..6]
2) Известны 6 зеленых ячеек
Соответствуют четыре таблицы, их сиды я привел выше.
0
Таблиц (8х8)всего 32 штуки. В силу их периодичности и того что в каждой из них не может быть одинаковых строк. Циклические комбинации строк не изменяют её содержимого — таблица при этом остаётся как бы сама собой.
А в остальном — да скорее всего то что я писал выше не сработает во всех таблицах.
0
Таблиц (8х8)всего 32 штуки.
Это автоматически обозначает:
1) В исходной строке всего 5 значащих бит
2) Для восстановления также хватит 5 бит (ячеек)
Собственно, это и отвечает на вопрос, который я задал в корне ветки: на первую строку накладываются ограничения, сокращающие число возможных ее значений 32, то есть она содержит 5 бит информации. Стоит, правда, заметить, что ты эти ограничения так и не озвучил.
0
сокращающие число возможных ее значений 32
*до 32
0
Разумеется, в случае четвертой таблицы заданию также соответствуют 4 таблицы: 00110110, 01001110, 10111110, 11000110.
P.S. Код проверки, на Lua.
-- footprint cells
fpc = {{3, 0}, {3, 1}, {3, 2}, {3, 3}, {4, 3}, {5, 3}} -- for 1st table
-- fpc = {{5, 0}, {5, 1}, {5, 2}, {5, 3}, {6, 3}, {7, 3}} -- for 4th table
-- target footprint
tfp = 15  -- for 1st table
-- tfp = 59 -- for 4th table

-- bitwise operators

w = 8 -- word width
m = 2 ^ w

function shl(a, b)
  local c = 2 ^ (w - b)
  return a % c * 2 ^ b
end

function shr(a, b)
  return math.floor(a / 2 ^ b)
end

function bit(a, b)
  return shr(a, b) % 2
end

function xor(a, b)
  local c, pow = 0, 1
  local xorl = {[0] = {[0] = 0, [1] = 1}, [1] = {[0] = 1, [1] = 0}}
  while a > 0 or b > 0 do
    c = c + xorl[a % 2][b % 2] * pow
    a = math.floor(a / 2)
    b = math.floor(b / 2)
    pow = pow * 2
  end
  return c
end

t={}

for i = 0, 255 do
  t[0] = i -- generate table
  for j = 1, 7 do
    t[j] = xor(shr(t[j-1], 1), t[j-1]) -- standard
    -- t[j] = xor(shr(t[j-1], 1) + 128, t[j-1]) -- with invisible bit 8
  end
  local fp = 0 -- calculate footprint
  for j = 1, #fpc do
    fp = shl(fp, 1) + bit(t[fpc[j][1]], fpc[j][2])
  end
  if fp == tfp then -- check footprint & print seed
    local s = ""
    for j = 7, 0, -1 do
      s = s .. bit(i, j)
    end
    print("Table seed " .. i .. " (" .. s .. ") matches footprint")      
  end
end
0
Вариант с выводом самой таблицы:
-- footprint cells
fpc = {{3, 0}, {3, 1}, {3, 2}, {3, 3}, {4, 3}, {5, 3}} -- for 1st table
-- fpc = {{5, 0}, {5, 1}, {5, 2}, {5, 3}, {6, 3}, {7, 3}} -- for 4th table
-- target footprint
tfp = 15  -- for 1st table
-- tfp = 59 -- for 4th table

-- bitwise operators

w = 8 -- word width
m = 2 ^ w

function shl(a, b)
  local c = 2 ^ (w - b)
  return a % c * 2 ^ b
end

function shr(a, b)
  return math.floor(a / 2 ^ b)
end

function bit(a, b)
  return shr(a, b) % 2
end

function xor(a, b)
  local c, pow = 0, 1
  local xorl = {[0] = {[0] = 0, [1] = 1}, [1] = {[0] = 1, [1] = 0}}
  while a > 0 or b > 0 do
    c = c + xorl[a % 2][b % 2] * pow
    a = math.floor(a / 2)
    b = math.floor(b / 2)
    pow = pow * 2
  end
  return c
end

function row2str(R)
  local s = ""
  for i = 7, 0, -1 do
      s = s .. bit(r, i)
  end
  return s
end

t={}

for i = 0, 255 do
  t[0] = i -- generate table
  for j = 1, 7 do
    t[j] = xor(shr(t[j-1], 1), t[j-1]) -- standard
    -- t[j] = xor(shr(t[j-1], 1) + 128, t[j-1]) -- with invisible bit 8
  end
  local fp = 0 -- calculate footprint
  for j = 1, #fpc do
    fp = shl(fp, 1) + bit(t[fpc[j][1]], fpc[j][2])
  end
  if fp == tfp then -- check footprint & print results
    print("Table seed " .. i .. " (" .. row2str(i) .. ") matches footprint")
    for j = 0, 7 do
      print(row2str(t[j]))
    end
    print()
  end
end
0
Собственно, это и отвечает на вопрос, который я задал в корне ветки: на первую строку накладываются ограничения, сокращающие число возможных ее значений 32, то есть она содержит 5 бит информации. Стоит, правда, заметить, что ты эти ограничения так и не озвучил.

Откровенно говоря не задумывался над тем сколько бит информации несёт в себе первая строка. Было понимание того что, если таблиц получается 32 то, чтобы получить любое число, из любой из них, нужен пятибитный номер таблицы и трёх битный индекс внутри неё.

Это автоматически обозначает:
1) В исходной строке всего 5 значащих бит
2) Для восстановления также хватит 5 бит (ячеек)
С этим согласен, опуская все объяснения. С этой точки зрения не первая строка содержит в себе пять бит информации, а вся таблица.

Разумеется, в случае четвертой таблицы заданию также соответствуют 4 таблицы: 00110110, 01001110, 10111110, 11000110.
А тут не согласен, для четвёртой таблицы при заданных условиях — восстановление единственно возможное.

Не знаю на чём можно запустить код на LUA.
0
С этой точки зрения не первая строка содержит в себе пять бит информации, а вся таблица.
Вся таблица генерится из первой строки и в принципе не может содержать информации больше, чем первая строка. Поэтому достаточно рассматривать только первую строку.
А тут не согласен, для четвёртой таблицы при заданных условиях — восстановление единственно возможное.
Огласи заданные условия. Я исходил из:
1) t[0] = X; t[i+1] = t[i] ^ ((t[i] >> 1) | 0b10000000), i=[0..6]
2) Известны 6 зеленых ячеек
Не знаю на чём можно запустить код на LUA.
Как ни странно, на Lua, версии 5.1.х (на более новых тоже должно работать).
0
Огласи заданные условия
Таблица формируется из восьми битного числа, при этом в каждой строке присутствует «неявный» первый бит равный единице.
Формируется так m[n] = A, m[n+1] = m[n]^(m[n]>>1);
при этом m[n+16] тоже окажется равным A.
Я исхожу из того что в такой таблице, в пределах одного периода, не может быть двух одинаковых чисел. При этом, всего таких таблиц получается 16 штук. И нет двух таких таблиц в которых содержалось бы одинаковое число — иначе это будет одна и та же таблица — но с циклически сдвинутыми строками(как бы по кольцу).
А по условию — нужно выбрать шесть элементов строго определённым образом. Как на рисунке выше для четвёртой таблицы поста.
Хотя в этом случае можно выбрать только четыре нижних элемента последнего столбца, при этом знать что есть частичное совпадение части пятой строки и диагонали её пересекающей. И знать какая именно часть строки совпадает с частью диагонали. На рисунке это отмечено, единственно то что угловой элемент пересечения оказался в зелёной зоне, но сути это не меняет.

Как ни странно, на Lua, версии 5.1.х (на более новых тоже должно работать).
Сейчас попробую.
0
Опять я поторопился, вот эти условия
Хотя в этом случае можно выбрать только четыре нижних элемента последнего столбца, при этом знать что есть частичное совпадение части пятой строки и диагонали её пересекающей. И знать какая именно часть строки совпадает с частью диагонали. На рисунке это отмечено, единственно то что угловой элемент пересечения оказался в зелёной зоне, но сути это не меняет.
сработают только при полном совпадении строки и диагонали её пересекающей, кроме первого бита, без учёта постоянной добавки в виде первой единички.
0
И пересечение должно быть на последнем бите.
0
Вот при указанных условиях указанному футпринту соответствуют 4 таблички.
0
— footprint cells
fpc = {{3, 0}, {3, 1}, {3, 2}, {3, 3}, {4, 3}, {5, 3}} — for 1st table
— fpc = {{5, 0}, {5, 1}, {5, 2}, {5, 3}, {6, 3}, {7, 3}} — for 4th table
Вот при указанных условиях указанному футпринту соответствуют 4 таблички.

В этих шаблонах никак не учитывается то что часть строки должна совпадать с частью диагонали — то что отмечено красным. То есть такой шаблон(определённое расположение ячеек и их количество) нужно выбирать только в том случае если в конкретной таблице будет совпадение части строки с частью диагонали.
Сегодня проверил — такое условие срабатывает не во всех таблицах. В принципе, я такое и предполагал.
И приведённый шаблон приводит только лишь к одной единственной таблице. Если же брать только зелёную часть — тогда да, подходит ещё и к
Разумеется, в случае четвертой таблицы заданию также соответствуют 4 таблицы: 00110110, 01001110, 10111110, 11000110.

Случайно получилось так что в таблицах из примеров эти условия срабатывают. До сегодняшнего дня я не пытался проверить это программно. Всё ручками расписывал в exell-евских таблицах. Меня, что называется, «прикалывала» возможность самовосстановления.
0
Это все уже дополнительные условия — другими словами, дополнительная информация. Я же исходил только из правила, явно указанного в посте.
0
Как ни странно, на Lua, версии 5.1.х (на более новых тоже должно работать).
Не компилируется почему-то, пишет что то вроде — попытка использовать не инициализированную переменную «a», дальше список функций. Это мой вольный перевод сообщения об ошибке. Ну да ладно. Хрен с ними с этими таблицами. :).
0
По крайней мере на несколько деньков. А то хочется есть, спать и кажется что мало платят. Наверное заболел звёздной болезнью. :))))
0
Это потому, что парсер сайта код побил. В строке «function row2str(R)» r должна быть маленькая.
0
Ученым «Института праславянской цивилизации», занимающимся этрусскими письменами, дачники прислали фото камня с загадочными рунами, найденного ими у реки Ловать неподалеку от города Великие Луки

Ученые сразу поняли, что камень принадлежит докирилловской эпохе, и его древнерусский текст начертан на диалектном русском с использованием архаического греческого алфавита.
Сперва ученые выделили письмена.
Затем принялись восстанавливать сам текст. Сперва транскрипция и транслитерация:

1. ЛТС КОЛ Р
2. М ПВ: ЛТС ЛХД
3. И АЛД ЛИ.С СК БИ ОЛ
4. ЛС СН ЛЗС И ЛСК
5. ЛИЛИС СЛЕ ЛИЛИ
6. БК ЛИ
Затем чтение:

1. ЛеТоСь КОЛолись на Ра — 2. Ме ПаВетки: ЛеТоСь ЛиХоДе — 3. И на АЛоДь ЛИЕСа СеКом БИли ОЛелько
4. ЛаСу СыН ЛиЗаСе И ЛаСКаться
5. ЛИЛИСь СЛЕзы ЛИЛИсь.
6. БоК ЛИл.

Ну и в итоге окончательный перевод (в комментариях статьи подробно и со
ссылками на источники разъясняется, почему именно так и никак иначе):

1. ЛЕТОСЬ ДРАЛИСЬ на МЕ-
2. ЖЕ, ПАВЕТКИ: ЛЕТОСЬ ЛИХОДЕ-
3. И на ОПУШКЕ ЛЕСА СЕКОМ УБИЛИ, ГОРЕ МНЕ,
4. ЛАСУ. СЫН любил ЦЕЛОВАТЬСЯ И ЛАСКАТЬСЯ.
5. ЛИЛИСЬ СЛЕЗЫ, ЛИЛИСЬ.
6. БОГ ЛИЛ.

НУ А ПОТОМ,
КАК ВСЕГДА,
ВСЁ ОПОШЛИЛИ ЖИДЫ.
УВИДЕЛ ИССЛЕДОВАНИЕ КАКОЙ-ТО ЕВРЕЙ, ПЕРЕВЕРНУЛ ФОТКУ КАМНЯ ВВЕРХ НОГАМИ
И НА ЧИСТОМ ИВРИТЕ ПРОЧЕЛ:
«ПОД ЭТИМ НАДГРОБИЕМ ПОКОИТСЯ БЛАГОЧЕСТИВАЯ ХАЯ, ДОЧЬ ИЦХАКА, ПОХОРОНЕНА В
1920 ГОДУ»
.
0
в топик призывается Калобайт.
+1
Нет. Теория информации говорит, что в таблице 8 бит независимых данных, потому что вся остальная таблица однозначно генерируется по первой строке. И в одной ячейке больше одного бита информации содержаться не может, как ни выбирай ячейки.
+2
0
А это один из способов реализации кодовой модуляции. На пальцах — расширение спектра. Ведь исходная картинка была очень низкочастотной, помеха — тоже. Поэтому расширив спектр мы «вывели» часть информации из помехи.
Навскидку — CDMA так работает, размывает спектр по каналу. И кроме помехозащищенности, в одном канале можно передавать несколько сигналов одновременно.
Конкретно этот метод интересен визуальным представлением «голографического
восстановления», на пальцах без сложной матетматики.
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.