Я когда ПО для BCH делал, плясал от структуры косетов. Для параметров кода n = 2^m - 1 и d - design distance рассчитать ее можно концептуально следующим образом:
Есть список от 1 до n.
1. Инициализируем лидера L = 1;
2. В косет записываем все (2*L*I) mod n, I = 1,2,.., пока снова не наткнемся на лидера. Вычеркиваем записанные в косет степени из списка.
3. Находим нового лидера L, как минимальное невычеркнутое целое. Если L >= d, останавливаемся. Все нужные косеты получены. Иначе переходим снова к 2.
Например для БЧХ длины 15, для первого косета минимальный полином m_1(x) = (х-a)*(x-a^2)*(x-a^4)*(x-a^8), a - генерирующий элемент поля GF(2^4). Для второго:
m_2(x) = (х-a^3)*(x-a^6)*(x-a^12)*(x-a^9)
Для остальных - аналогично. Генерирующй полином кода БЧХ (15,5,7) g(x) = m_1(x) * m_2(x)*m_3(x) - произведение минимальных полиномов косетов, включающих степени 1..d-1 генерирующего элемента.
Он автоматом получится с коэффициентами 0 и 1. g(х) имеет степень n-k. Генерирующая матрица состоит из строчек со сдвигами g(х).
Если нужна проверочная матрица, то алгоритмом Евклида находишь проверочный полином h(x) = (x^n-1)/g(x). Делится без остатка по свойствам циклических кодов, h(x) имеет степень k. Затем его reciprocal:
r(X) = (X^k)*h(x^-1). В сущности у reciprocal polynomial те же коэффициенты, что и у h(х), только в обратном порядке. Проверочная матрица формируется как сдвиги reciprocal polynomial. Она же является генерирующей матрицей дуального кода.
Для того, чтобы всё это в голове уложилось, мне помогает понимание, что циклический код - идеал в кольце полиномов по модулю (x^n-1), которое является кольцом главных идеалов. Алгебра реально упрощает жизнь. Например, из этого сразу становится интуитивно понятно, что для одной длины БЧХ коды с меньшей исправляющей способностью включают слова кодов с большей.
Из хороших книжек по кодированию, которые достаточно алгебраичны и в то же время без лишней алгебры ;), мне нравится Vera Pless, Introduction to the Theory of Error-Correcting Codes.
