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

Сообщение отредактировал spectr - Oct 25 2011, 07:57

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

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

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

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

Сообщение отредактировал spectr - Oct 27 2011, 13:24

Задача может быть решена простой комбинаторикой.
Для этого нужно знать пересечение множеств вашего
слова и замороженных бит. Нужен пример от ТС.

Пример (младший бит справа, в скобки взяты замороженные биты):
[0]BBBBBBBBBB[1][0]BBBBBBBBBB[1]
Допустим, паттерн выглядит так: 1101011010

Сообщение отредактировал spectr - Oct 31 2011, 08:01

Нужно еще понимать что требуется - количество сочетаний на заданном поле
из общего числа вариантов (исходя из 20 бит: 2^20) ?
Или нужно максимальное количество вхождений слова W в посылку?
Лучше привести, например для 4х бит таблицу - что требуется получить.

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