Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 78

Две n-битные двоичные строки, S1 и S2, выбираются случайным образом с одинаковой вероятностью. Вероятность того, что расстояние Хэмминга между этими строками (количество позиций битов, в которых эти две строки различаются) равна d, равно
(А) нКд / 2 н
(B) нКд / д
(С) д / 2 н
(D) 1/2 d

Ответ: (А)
Пояснение: Расстояние Хэмминга для строк S1 и S2 может быть любым значением от 0 до n.
Расстояние Хэмминга — это количество разных битов между двумя строками. Для заданной строки и расстояния d могут быть строки C (n, d), имеющие d в качестве расстояния Хэмминга, поскольку из n битов необходимо выбрать любое d.
Для любой строки S1 есть —
C (n, 0) струн с расстоянием Хэмминга 0
C (n, 1) струн с 1 расстоянием Хэмминга
C (n, 2) струны с расстоянием Хэмминга 2
,
,
C (n, n) струн с расстоянием Хэмминга
Всего строк = C (n, 0) + C (n, 1) +… + C (n, n) =
Струны с расстоянием Хэмминга d = C (n, d)
Следовательно, вероятность =
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2004 | Вопрос 78

0.00 (0%) 0 votes