Комментарии 6
1) В разделе «Матричное кодирование» У вас неправильная формула для G и Н, (где I и P).
2) При шифровании вектор ошибок точно добавляется после кодирования, а не до? Когда вы домножите e на P^-1 там будет 100500 ошибок в кодовом слове или нет?
2) При шифровании вектор ошибок точно добавляется после кодирования, а не до? Когда вы домножите e на P^-1 там будет 100500 ошибок в кодовом слове или нет?
1) Верное замечание, уже исправил, спасибо.
2) Матрица P представляет собой матрицу перестановки. Результатом умножения вектора на неё будет являться вектор, отличный от исходного только перестановкой элементов. Умножение на обратную матрицу даст лишь обратную перестановку (т.е. исходную), но никак не увеличит количество ошибок в коде.
2) Матрица P представляет собой матрицу перестановки. Результатом умножения вектора на неё будет являться вектор, отличный от исходного только перестановкой элементов. Умножение на обратную матрицу даст лишь обратную перестановку (т.е. исходную), но никак не увеличит количество ошибок в коде.
1) Даже с исправленным не согласен… H не обязана иметь единичную матрицу в составе, если исходить из систематического вида G, то её подматрица P представляет из себя произведение двух матриц, полученных из двух подматриц H, одна транспонированная, вторая — обратная.
2) Пропустил это условие… А «любая» матрица перестановок всегда невырожденная, если нет, то каков алгоритм их выбора? И будет ли её обратная матрица тоже матрицей перестановок?
2) Пропустил это условие… А «любая» матрица перестановок всегда невырожденная, если нет, то каков алгоритм их выбора? И будет ли её обратная матрица тоже матрицей перестановок?
Для порождающей матрицей в систематическом виде будет достаточно транспонировать её чётную часть и «дописать» справа единичную матрицу, чтобы выполнилось тождество GH^T = 0. В общем виде это действительно работать не будет.
Для каждой матрицы перестановок всегда существует обратная (и да она тоже будет задавать перестановку). Существует модификация алгоритма, в которой вместо матрицы перестановки берётся случайная матрица, имеющая вес строки, допустим, w. Тогда количество ошибок, которое сможет исправить код, уже будет рассчитываться как t / w. И здесь уже существенным условием является невырожденность такой матрицы.
Для каждой матрицы перестановок всегда существует обратная (и да она тоже будет задавать перестановку). Существует модификация алгоритма, в которой вместо матрицы перестановки берётся случайная матрица, имеющая вес строки, допустим, w. Тогда количество ошибок, которое сможет исправить код, уже будет рассчитываться как t / w. И здесь уже существенным условием является невырожденность такой матрицы.
Спасибо за статью! Интересно было прочитать про применение помехоустойчивых кодов в, так сказать, новой для них области!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Криптосистема McEliece на базе LDPC кодов