[irum4 0]

Понимаю что вопрос казалось бы элементарный - google и вперед, но там такой дряни куча, что не хочеться разбираться.

Причем желательно для соотношения 12 на 8 информационных.

А также для исправления более одной ошибки.

А если кто-то уже такое реализовывал, то буду премного благодарен за исходник в любом виде.

[XBG432 0]

Попробуй почитать классику - на серваке в разделе pub/DOC/Books лежит аж три версии книги Р.Блэйхута "Теория и практика кодов контролирующих ошибки".

А по поводу "гугла" - абсолютно согласен, что там "дряни" куча, но можешь глянуть сюда:

 

http://direct.xilinx.com/bvdocs/appnotes/xapp383.pdf

http://people.bu.edu/ska/project3.pdf

 

Если требуется исправлять более одной ошибки, это уже не Хэмминг:)

например код Рида-Соломона:

 

http://sourceforge.net/projects/rstk/

http://www.4i2i.com/reed_solomon_ip_cores.htm

[MadMakc 0]

Ну а если Рид-Соломон "тяжеловат",есть ещё БЧХ.

15 бит слово,7 информационных.Правит 2 ошибки.

[irum4 0]

С Хеммингом разобрался. Реализовал.Всем спасибо.

С Ридом-Соломоном тоже все понятно, но он для моей задачи он не подходит, он позволяет исправлять несколько байтов из некой группы, а мне необходимо исправлять отдельные биты в словах.

И по ходу еще один вопрос. Для исправления одной ошибки для 8 бит необходимо 4 проверочных бита. А для обнаружения двух - нужен еще один разряд? Или можно обойтись теми же четырьмя? И если можно, то как?

[hlebn 0]

На сколько помню. Хеминг исправляет все одиночные и обнаруживает все двойные ошибки. Так что еще один бит не нужен.

Рид Соломон делает все тоже самое только еще перемежает биты так что помеха искажающая несколько соседних бит в потоке на самом деле искажает по одному биту в разных информационных байтах(словах) которые по отдельности потом можно восстановить. это так примитивно популярное объяснение принципа. если требуется передавать потоки информации по последовательному каналу то лучше использовать рида соломона.

[XBG432 0]

И по ходу еще один вопрос.  Для исправления одной ошибки для 8 бит необходимо 4 проверочных бита. А для обнаружения двух - нужен еще один разряд? Или можно обойтись теми же четырьмя? И если можно, то как?

<{POST_SNAPBACK}>

 

Постараюсь объяснить на пальцах :cheers:

Для обнаружения однократной ошибки минимальное кодовое расстояние должно быть не меньше 2.

Пример такого кода (код с проверочным битом на четность): 000-011-101-110.

При 1х ошибке получаем некодовое слово (010). Можем только сказать, что это некодовое слово, исправить нельзя, т.к. неясно в каком кодовом слове произошла 1х ошибка: в 000(010) или в 011(010).

Декодирование кодов, подобых этому, осуществляется по методу максимального правдоподобия. Т.е., если мин. расстояние у кода 3, то это означает, что он позволяет корректировать 1х ошибки и обнаруживать все 2х ошибки. В случае возникновения 3х ошибки есть вероятность получить кодовое слово, т.е. ошибка при этом замаскируется.

Код Хемминга имеет как раз мин. расстояние 3. Т.е. для обнаружения 2х ошибок добавлять ничего не надо.

Есть еще расширенный код Хэмминга, в котором к каждому слову добавляется дополнительный проверочный бит равный сумме всех информационных и остальных проверочных (бит четности всего пакета). Мин. расстояние такого кода уже 4: корректируем 1х, обнаруживаем 2х и все ошибки нечетной кратности. 2х нельзя корректировать, т.к. такие слова лежат как раз "по середине" между кодовыми словами.

А Хэмминг с 4 проверочными битами может быть использован до 11 информационных символов. Смотря для чего и где применять...

[Slavik 0]

Ключевая фраза здесь, как упоменалось выше, "минимальное кодовое расстояние". Чем больше у тебя избыточность в проверочных битах, тем выше корректирующая/контролирующая способность кода. Надо только правильным образом сформировать эти битики.