Линейный двоичный код: расстояние и ближайшие слова
По независимым строкам порождающей матрицы перечислить код, проверить минимальный вес и декодировать принятое слово с явным обнаружением ничьей.
Ваш пример
Разбор примера
dmin = 2; ближайших слов: 3
- Код перечислен полностью в заявленном малом размере.
- Минимальное расстояние проверено через ненулевые веса.
- Уникальное ближайшее слово не заменяет предположение о числе ошибок канала.
Метод и условия расчёта
Перебираем все 2ᵏ линейные комбинации строк по модулю два.
Для линейного кода dmin равен минимальному весу ненулевого слова; гарантированно исправляется floor((dmin−1)/2) ошибок.
Теория к методу
Строки порождающей матрицы складываются по модулю два. Минимальный вес ненулевого кодового слова равен минимальному расстоянию кода. Он определяет гарантированный радиус исправления, а отдельное принятое слово дополнительно проверяют на ничью ближайших вариантов.
Зафиксируйте поле GF(2): сложение выполняется операцией XOR. Независимость строк проверяется именно над этим полем, а не привычным вещественным исключением. Если k строк независимы, их двоичные комбинации дают ровно 2^k различных слов. Повторение слова при разных комбинациях означает зависимость и несоответствие заявленной размерности.
Пример: Для единственной порождающей строки 111 код состоит из 000 и 111. Его расстояние равно трём, гарантируется исправление одной ошибки. Слово 101 находится на расстоянии один от 111 и два от 000.
Ближайший вариант здесь единственный: 111. В коде с порождающими строками 101 и 011 расстояние всего два; принятое 100 равноудалено от трёх кодовых слов, и честный результат должен перечислить ничью.
Вопросы по теме
Ближайшее слово обязательно было отправлено?
Нет. При числе ошибок вне гарантированного радиуса близость сама по себе не доказывает исходное слово.
Что если ближайших слов несколько?
Все такие слова перечисляются; произвольный выбор одного скрывал бы неоднозначность.
Безопасность и надёжность данных: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.