Составители:
Рубрика:
ции. При этом одиночная ошибка приводит к искажению любого одного
разряда двоичного вектора, двойная – любых двух разрядов и т. д. Пусть
для классификации выбрано n двоичных признаков, а предварительные
эксперименты показывают, что одиночные, двойные и даже тройные
ошибки имеют заметную величину, а ошибками большей кратности
можно пренебречь из-за их малой вероятности. Оценим размеры клас-
теров и найдем грубую оценку возможного числа кластеров при нали-
чии n признаков.
Вектор одиночной ошибки представляет собой двоичный n-разряд-
ный код, содержащий одну единицу (остальные разряды нулевые). Век-
тор двойной ошибки содержит две единицы, вектор тройной ошибки – 3
единицы. Общее число векторов одиночных, двойных и тройных оши-
бок равно:
123
nnn
CCC
++
.
Если умножить полученное значение числа векторов ошибок на воз-
можное число кластеров, то произведение должно быть существенно
меньше, чем общее количество n-разрядных векторов. Из этих рассуж-
дений получаем оценку:
()
123
2.
n
nnn
CCCK++ <
Откуда число возможных кластеров
()
123
2.
n
nnn
KCCC<++
Так, при n = 10 число кластеров K << 7 .
Аналогичные оценки используются для определения границ в теории
кодирования.
Упражнения
1. Вектор двоичных признаков содержит 12 компонент (12-разряд-
ный двоичный вектор). Одиночная ошибка искажает вектор. Сколько
различных ошибочных векторов при этом может быть получено? Для
конкретного вектора: 100111010010 выпишите все ошибочные векторы.
2. На кодовое слово длины 16 действует пакет ошибок (ошибки груп-
пируются подряд, но не превышают 5 разрядов). Подсчитайте число
возможных искажений кодового слова. Обобщите результат на n-раз-
рядное кодовое слово и на максимальный размер пакета ошибок в k
разрядов.
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »
