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

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.