|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 23 May 2003 13:37:38
To : Arthur Vartanov
Subject : Re: Порождающий многочлен в БЧХ
--------------------------------------------------------------------------------
Thu May 22 2003 22:29, Arthur Vartanov wrote to Sergey Kabikov:
SK>> Предлагаю поступить проще : огласи исходную постановку задачи
AV> Позволю себе вклиниться. Когда-то давно я задавал в этой эхе
AV> аналогичный вопрос. Hо никто так и не ответил.
AV> Задача попроще. "Требуется обнаружить 2 (в идеале - 3)
AV> искаженных бита в блоке размером до 16384 бит.
Для двух - расширенный код Хэмминга. 15 проверочных бит + бит четности.
Порождающий полином, например, x^15 + x + 1.
Он будет обнаруживать все двойные ошибки и _большинство_ более кратных.
Чтобы гарантированно обнаруживать все тройные ошибки, нужен код, способный
исправлять две ошибки, например, расширенный код БЧХ, но для него согласно
границе сферической упаковки потребуется минимум 28 (для именно БЧХ - 29)
проверочных бит, что противоречит условию
AV> Избыточность - не более 16 бит.
AV> Вычислительная мощность - доступно
AV> где-то до десятка операций сложения по модулю 2 и/или
AV> сдвига на каждые 16 бит блока данных.
Боюсь, без табличного преобразования деление полинимов тебе будет нелегко
делать. Hо точные рекомендации можно дать только зная платформу.
AV> Да, количество данных выровнено на 16 бит".
может оказаться важным только при реализации на конкретной платформе.
AV> Пока все это сделано простым рабоче-крестьянским методом.
Увы, изобретаешь неудачно. Легко можно подсчитать, что в каждом шестнадцатом
случае двойная ошибка будет воспринята как отсутствие ошибок.
С уважением
Сергей
...с высоты птичьего помета (с) очепятки
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
