Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Весовой коэффициент двоичных векторов и расстояние между ними

Формальное определение имеет вид:

={ x | x Î U и x Ï X }.

Пример 1.8. Если U ={1, 2, 3, 4, 5, 6, 7} и X ={3, 5, 7}, то ={1, 2, 4, 6}.

Из определения множества X следует, что X и не имеют общих элементов, т. е.

XÇ =Æ.

Кроме того, не имеется элементов множества U, которые не принадлежали бы ни X, ни , поскольку элементы, не принадлежащие X, принадлежат . Следовательно,

XÈ =U.

Другой часто встречающейся операцией над множествами является разбиение множества на систему подмножеств.

Определение 1.1.20 Разбиением непустого множества A называется совокупность подмножеств, объединение которых даёт A, причём упомянутые подмножества взаимно не пересекаются.

Если же последнее условие не выполняется, то говорят не о разбиении, а о покрытии.

Из сказанного о разбиении следует, что каждый элемент разбиваемого множества A может содержаться только в одном подмножестве разбиения.

Например, система курсов (с первого по пятый) данного факультета является разбиением множества студентов факультета; система групп данного курса является разбиением множества студентов курса.

Если N – множество натуральных чисел, а A₀ и A ₁ – множество чётных и нечётных чисел, то система { A₀, A ₁} будет разбиением множества N.

Весовой коэффициент двоичных векторов и расстояние между ними

Конечно же, понятно, что правильно декодировать можно не все ошибочные комбинации. Возможности кода для исправления ошибок в первую очередь определяются его структурой. Весовой коэффициент Хэмминга кодового слова определяется как число ненулевых элементов в . Для двоичного вектора это эквивалентно числу единиц в векторе. Например, если , то . Расстояние Хэмминга между двумя кодовыми словами и , обозначаемое как , определяется как количество элементов, которыми они отличаются.

Согласно свойствам сложения по модулю 2, можно отметить, что сумма двух двоичных векторов является другим двоичным вектором, двоичные единицы которого расположены на тех позициях, которыми эти векторы отличаются.

Таким образом, можно видеть, что расстояние Хэмминга между двумя векторами равно весовому коэффициенту Хэмминга их суммы, т.е. . Также видно, что весовой коэффициент Хэмминга кодового слова равен его расстоянию Хэмминга до нулевого вектора.