терминология
- Для «линейных» кодов (CRC, кодов Хэмминга и т. Д.) Каждый бит данных всегда влияет на фиксированный набор некоторых (но не всех) битов четности. Например, если (только) бит 7 данных переворачивается при передаче, и это переворачивает биты четности 2 и 4, но не бит четности 5 - в пересчитанных битах четности, по сравнению с полученными битами четности - тогда переворачивание бит 7 данных перевернет биты четности 2 и 4, но не бит 5 четности для каждого возможного кадра битов данных полезной нагрузки.
- Все биты в полезной нагрузке, которые влияют на конкретный бит четности (такой как бит четности 5), и сам этот бит четности, как говорят, "покрыты" или "защищены" этим битом четности.
Когда приемник пересчитывает биты четности и сравнивает пересчитанные биты четности с принятыми битами четности, эта разница называется синдромом. Когда ошибок не было, синдром равен нулю.
In other words, syndrome = recalculated_parity XOR recieved_parity.
Доказательство
Доказательство того, что для обнаружения 2-битных ошибок в 2 ^ n-битном фрейме данных полезной нагрузки требуется n битов четности:
Когда во всем кадре есть только 1 ошибка,
когда приемник пересчитывает биты четности,
Есть два случая:
- Каждый пересчитанный бит четности, который не покрывает ошибочный бит, совпадает с соответствующим принятым битом четности. (Соответствующий бит в синдроме "0").
- Каждый пересчитанный бит четности, который покрывает ошибочный бит, отличается от соответствующего принятого бита четности, и обнаруживается ошибка. (Соответствующий бит в синдроме «1»).
Когда во всем кадре ровно 2 ошибки,
результирующий синдром - это XOR синдрома, вызванного каждой ошибкой в изоляции.
Когда приемник пересчитывает биты четности, есть 3 случая:
- (a) Каждый пересчитанный бит четности, который не покрывает ни один ошибочный бит, совпадает с соответствующим принятым битом четности. (Соответствующий бит в синдроме "0").
- (b) Каждый пересчитанный бит четности, который охватывает оба ошибочных бита, совпадает с соответствующим принятым битом четности. (Каждая ошибка переворачивает такой бит один раз, и оба совмещенных сброса возвращают этот бит в исходное состояние, поэтому соответствующий бит в синдроме равен «0»).
- (c) Каждый пересчитанный бит четности, который охватывает один ошибочный бит и не покрывает другой ошибочный бит, отличается от соответствующего принятого бита четности, и обнаруживается ошибка. (Соответствующий бит в синдроме «1»).
Если, гипотетически, существовал некоторый бит полезной нагрузки, такой, что его переворачивание вызывает некоторый синдром S,
и есть любой другой бит полезной нагрузки, который производит точно такой же синдром S,
тогда двухбитовая ошибка, поразившая оба этих бита, будет необнаружима.
Другими словами, эта двухбитовая ошибка дала бы синдром S xor S == zero.
Другими словами, каждая четность является либо случаем (a), либо случаем (b), ни один из которых не может обнаружить такую ошибку.
Это было бы плохо.
Таким образом, чтобы обнаружить каждую возможную двухбитовую ошибку в кадре,
мы должны спроектировать код обнаружения ошибок так, чтобы
каждая ошибка в одном бите должна вызывать другой синдром .
Другими словами, должен быть как минимум 1 бит четности типа (c) для каждого возможного случая двух ошибочных битов в кадре.
Использование n битов четности дает n синдромных битов.
С n битами синдрома существует не более 2 ^ n различных синдромов.
Таким образом, чтобы убедиться, что каждый бит в кадре (когда это единственная ошибка) дает другой синдром,
в кадре должно быть не более 2 ^ n битов.
Бьюсь об заклад, если вы разместите этот вопрос на https://math.stackexchange.com/, вы получите гораздо более короткое и элегантное доказательство: -).