Перейти к содержанию
    

Как бы подсчитать поудобнее

Допустим, есть некая последовательность бит. Предположим, длиной N=50 бит. Известно, что некоторые биты в этом слове "заморожены", т.е. всегда при любых условиях имеют одно и то же значение. Далее известно, что существует некоторая комбинация бит этого слова, образующая совместно с "замороженными" битам кодовое слово W (длина слова W меньше длины N). Вопрос: как можно красиво (формулой или логикой) подсчитать при каких еще комбинациях "незамороженных" бит в этом слове может "выпасть" это же кодовое слово W. Иными словами - сколько раз встретится слово W в N-битном числе, если M его бит заморожены?

Изменено пользователем spectr

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Иными словами - сколько раз встретится слово W в N-битном числе, если M его бит заморожены?

 

2^N - 2^M количество возможных комбинаций "длинного ключа".

Вопрос, сколько из них совпадет с коротким ключом W?

 

Думаю, без апприорных знаний о раположении замороженных бит невозможно

подсчитать число совпадений. Можно ведь так расположить замороженные биты, что заведомо

никакая комбинация не подойдет. Например морозим первый бит длинного ключа 0, а в коротком ключе W требуем первый бит 1.

 

Или я чего не понял?

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Позиция и значения замороженных бит известны. Да, можно подобрать такое сочетание мертвых битов, при котором будет одно и только одно сочетание бит, образующее ключ W.

Изменено пользователем spectr

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Задача может быть решена простой комбинаторикой.

Для этого нужно знать пересечение множеств вашего

слова и замороженных бит. Нужен пример от ТС.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Пример (младший бит справа, в скобки взяты замороженные биты):

[0]BBBBBBBBBB[1][0]BBBBBBBBBB[1]

Допустим, паттерн выглядит так: 1101011010

Изменено пользователем spectr

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Нужно еще понимать что требуется - количество сочетаний на заданном поле

из общего числа вариантов (исходя из 20 бит: 2^20) ?

Или нужно максимальное количество вхождений слова W в посылку?

Лучше привести, например для 4х бит таблицу - что требуется получить.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Пример (младший бит справа, в скобки взяты замороженные биты):

[0]BBBBBBBBBB[1][0]BBBBBBBBBB[1]

Допустим, паттерн выглядит так: 1101011010

 

А сейчас как считаете? Предполагаю, что просто сдвигая один регистр (паттерн) относительно W и при этом сравнивая только те биты, которые одновременно и перекрываются паттерном и только в замороженных позициях. Тогда получается ответ знаем через BITS(W)-BITS(pattern) итераций. Так?

 

 

 

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...