Вычислительный код Хэмминга

Question

Я немного запутался по поводу вычисления кода Хэмминга.В статье Википедии написано:

Бит 1 четности охватывает все позиции битов, для которых установлен младший значащий бит: бит 1 ( сам бит четности ), 3, 5, 7, 9 и т. Д.

Как можно получить четность битов, содержащих это значение?

Правильно ли я понимаю, что согласностатья над первым битом четности должна быть рассчитана следующим образом:

parity_bit_1 = parity_bit_1 xor data_1 xor data_2 xor data_4 xor data_5 xor data_7 ...

Однако в некоторых других источниках (например, в ответе joel.neely на этот вопрос ) говорят, что он рассчитывается следующим образом:

parity_bit_1 = data_1 xor data_3 xor data_5 xor data_7 xor data_9 ...

Итак, как это сделать?

Answer 1

Я думаю Расчет кода Хэмминга статья будет полезна.

Answer 2

Что это означает: для каждого k следующее значение равно нулю: исключая или всех битов, в индексе которых установлен бит k.(Ваши биты имеют индексы 1,2, ..., 2 ^ n-1.)

Фактические данные поступают в битах, индексы которых имеют более одного установленного бита.

Затем выможет вычислять требуемые значения битов индекса степени 2, используя ограничения четности: каждое ограничение включает в себя ровно один бит, индекс которого является степенью 2, и каждый бит, индекс которого является степенью 2, появляется ровно в одном ограничении.

Так, например, рассмотрим случай n = 3.У вас есть 2 ^ 3-1 = 7 бит кода;3 из них - биты четности, с индексами 1,2,4.Другие, с индексами 3,5,6,7, представляют собой данные, которые вас интересуют.

Вы выбираете, что входит в биты 1,2,4, чтобы гарантировать, что бит 1 XOR бит 3 XOR бит 5 XORбит7 = 0 и бит2 XOR бит3 XOR бит6 XOR бит7 = 0 и бит4 XOR бит5 XOR бит6 XOR бит7 = 0.

Так, например, если ваше сообщение 0110, вы отправите?,?, 0,?, 1,1,0.Первый ?имеет? + 0 + 1 + 0 = 0 и, следовательно, должно быть 1. Второе?имеет? + 0 + 1 + 0 = 0 и, следовательно, также должно быть 1. Третье?имеет? + 1 + 1 + 0 = 0 и, следовательно, должно быть 0. Так что вы отправляете это 1100110.