расстояние хемминга, подсчет числа последовательностей

[Sonic86]

Блин, не помню. Кажется в уравнении делали сначала сдвиг на $\alpha$ и получали уравнение $N(\gamma:\rho(\bar{0},\gamma)+\rho(\beta-\alpha,\gamma))=4$ и дальше перебирали все возможные значения $m=\rho(\bar{0},\gamma)$ - от $0$ до $4$-х и суммировали. Надо заново решить и тогда все вспомню

[pashabond]

Есть еще такая версия задачи:

Для $\alpha = (1111011)$,$\beta = (1111101)$ требуется найти количество $\gamma \in B^7$, для которых выполняется равенство $\rho(\alpha,\gamma)+\rho(\gamma,\beta) = 4$ , где $\rho(\delta,\varepsilon)$ - расстояние хемминга между словами $\delta$ и $\varepsilon$.

в соответствии с равенством $\rho(\alpha,\gamma)+\rho(\gamma,\beta) = 4$

Варианты ответа:
1) 8
2) 14
3) 20
4) 16
5) 48

Поскольку вектора несложные, то я попробовал подобрать все варианты исходя из того, что
$\rho(\alpha,\gamma) =2$
$\rho(\gamma,\beta) =2$

Получились комбинации:
$(0111001)$
$(1011001)$
$(1101001)$
$(1111000)$
$(0111111)$
$(1011111)$
$(1101111)$
$(1110111)$
$(1111110)$

Итого $N=46$, опечатка в вариантах ответа, как проверить?

[Sonic86]

Проверить можно тупо на компе, мощность пространства всего $128$.
Уравнение сдвигом на $\alpha$ проще преобразовать к уравнению $\rho((0000000),\gamma)+\rho((0000110),\gamma)=4$ - оно имеет столько же число решений. Далее, можно осуществить перестановку компонент вектора - число решений тоже не изменится: $\rho((0000000),\gamma)+\rho((0000011),\gamma)=4$. Теперь смотрите - все зависит только от компонент. У векторов $(0000000),(0000011)$ $5$ компонент совпадают, а $2$ компоненты разные. Значит, как бы мы не выбрали последние $2$ компоненты в $\gamma$, они дадут в расстояние вклад равный ###. Всего вариантов ### С первыми $5$-ю компонентами по-другому: если соответствующие компоненты $\gamma$ равны $0$, то вклад в расстояние ###, иначе ###. Всего вариантов ###. Выбор компонент независимый, значит числа вариантов ###. Итого ###.

pashabond в сообщении #594596 писал(а):

Итого $N=46$,

У Вас скорее всего неверно, т.к. $46=23\cdot 2$ - слишком "мало" множителей.

[pashabond]

Идею понял, видимо не хватает математической базы, чтобы понять до конца.

По поводу примера выше, где $N=46$: просто любой вектор работает в уравнении, даже в качестве проверки.

А как проверить на компе кстати?

-- 12.07.2012, 09:29 --

Спрошу даже проще: можете дать алгоритм решения, т.е. вот есть векторы, с чего начинать, кроме того что посчитать расстояние хемминга между альфа и бета?

Извиняюсь за дотошность - экзамен меньше чем через неделю, хочется во всех деталях понять.

[Sonic86]

pashabond в сообщении #594627 писал(а):

А как проверить на компе кстати?

Как обычно - можете семирной цикл написать по компонентам вектора $\gamma$ (хотя это китайский код ). Можете перебирать числа от $0$ до $127$, преобразовывать их в двоичное число длины $7$, семерка цифр определяет вектор $\gamma$ - подставляете его в $\rho(\gamma,\alpha)+\rho(\gamma,\beta)=4$ и проверяете.

pashabond в сообщении #594627 писал(а):

Идею понял, видимо не хватает математической базы, чтобы понять до конца.

Здесь достаточно уметь пользоваться числом сочетаний и свойством произведения (т.е. если $X_1$ пробегает множество $M_1$, а $X_2$ пробегает множество $M_2$ независимо от $X_1$, то число вариантов $(X_1,X_2)$ равно $|M_1|\cdot |M_2|$).

-- Чт июл 12, 2012 06:41:31 --

pashabond в сообщении #594627 писал(а):

Спрошу даже проще: можете дать алгоритм решения, т.е. вот есть векторы, с чего начинать, кроме того что посчитать расстояние хемминга между альфа и бета?

Вы алгоритм можете сами выделить из принципа перебора
Т.е. решите детально задачу, если в каком-то моменте будет непонятно - сразу скажу. Откуда число сочетаний берется и степень двойки, Вам придется понять (да я Вам его почти написал весь даже)

[s128]

подскажите каким минимум вариантов можно составить код покрывающий 9из15 для троичного алфавита?