Блог

Предположим, мы работаем с кодом исправления ошибок, который позволит исправлять все одноразрядные ошибки для слов памяти длиной 7. Мы уже подсчитали, что нам нужно 4 контрольных бита, а длина всех кодовых слов будет равна 11. Кодовые слова создаются в соответствии с алгоритмом Хэмминга, представленным в тексте. Теперь мы получаем следующее кодовое слово: 1 0 1 0 1 0 1 1 1 1 0 Предполагая даже паритет, является ли это юридическим кодовым словом? Если нет, то в соответствии с нашим кодом исправления ошибок, где ошибка?

P.s нужна небольшая помощь в решении этой проблемы с кодом Хэмминга, это вопрос из книги. Заранее спасибо 🙂

Кодовые слова создаются в соответствии с алгоритмом Хэмминга, представленным в тексте.

Это важная информация, не так ли? 🙂

Без алгоритма мы не можем быть уверены в достоверности, поэтому я дам вам общий подход.

Каждый контрольный бит обычно применяется к некоторому подмножеству битов. Допустим, семь битов b6 пройдены b0 . Четыре контрольных бита вычисляются для обеспечения четности в следующих подмножествах:

      1  0  1  0  1  0  1
ca  b6 b5    b3 b2 b1 b0  1 0 0 1 0 1     (ca = 0)
cb  b6    b4    b2    b0  1 1 1 1         (cb = 0)
cc  b6       b3       b0  1 0 1           (cc = 0)
cd     b5          b1 b0  0 0 1           (cd = 1)
  

Теперь, если вы не получили последовательность контрольных битов, соответствующую данным, вы в идеале могли бы определить, какие отдельные данные или контрольный бит необходимо изменить, чтобы их исправить. Это сработало бы только в том случае, если бы вы могли убедиться, что каждое вычисление контрольного бита было тщательно обработано для добавления максимальной дополнительной информации.

Вероятно, это ошибка в моем приведенном выше расчете, поскольку я просто вытащил его из воздуха. Но, поскольку моим намерением было просто объяснить концепцию в отсутствие вашего алгоритма, это не должно иметь значения.

Один из способов убедиться, что алгоритм работает, — это перебор:

• Получите список всех возможных одиннадцатиразрядных значений. Их всего 2048, так что это не обременительно. На данный момент отбросьте те, которые уже исправны (нас интересуют только недопустимые).
• В свою очередь, переключите каждый бит (из 11) и посмотрите, становится ли элемент действительным.
• Если никакие битовые переключатели не сделали его действительным, это не однобитовая ошибка, поэтому ее можно смело игнорировать.
• Если одноразрядное переключение сделало его действительным, то у вас достаточно информации, чтобы исправить этот случай.
• Если более чем одно битное переключение сделало его допустимым, у вас недостаточно информации для исправления этого случая.

Итог, если каждая возможность однобитовой ошибки может быть исправлена с помощью однобитового переключения (предпоследний пункт выше), код исправления идеален.

Вы также должны убедиться, что все допустимые значения станут недействительными, если будет переключен один бит, но я оставлю это упражнение, поскольку теперь у вас должно быть достаточно информации о том, как это сделать.