ВОРОТА | 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)
Следовательно, вероятность =
Тест на этот вопрос

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

• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
• ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65