Лабораторная работа: Программный кодер-декодер для циклических (n,k)-кодов
1101 0000000
1000110 Å
1101 1000110
В выражении (2) первый член суммы в круглых скобках умножим и разделим на порождающий многочлен и произведем умножение обоих членов на х(n-k) . Получим:
(3)
Дробь 
представим как меньшую целую часть (частное) Q 1 (х) , которое в конечном итоге нас не интересует, плюс остаток от деления R 1 (х) . С учетом этого перепишем (3).
Получим:
А (х) х(n-k) = Q 1 (х) G ( x ) х(k-ℓ) +R 1 ( x ) х(k-ℓ) +А `1 (х) х(n-k) (4)
Старшая степень многочлена 
не превосходит (ℓ-1 ), т. к. такую степень по соглашению имеет А 1 (х) , а G (x) имеет фиксированную степень (n-k) по определению (вывернутые полускобки символизируют ближайшее меньшее целое от дроби, т.е. частное). Тогда получается, что первое слагаемое в (4) имеет старшую возможную степень (n‑1 ), что соответствует вектору длины n .
Старшая степень остатка R 1 (x) не превосходит величины (n-k‑1 ), а всего второго слагаемого в (4) – величины (n-ℓ-1) . Такую же степень имеет и третье слагаемое А `1 (х) х(n-k) . Сложим эти два последних члена, сумму обозначим F 1 (х) . Перепишем (4) в следующем виде:
А (х) х(n-k) = Q 1 (х) G (x) х(k-ℓ) +F 1 (х) (5)
Рис. 1 иллюстрирует формирование последовательности F 1 в векторной интерпретации всех участвующих величин. Обратим внимание на длину последовательности F 1 , на то обстоятельство, что при суммировании векторы R 1 и A `1 «выровнены» со стороны старших разрядов, а F 1 имеет справа (n-k ) нулевых бит.
Рис. 1. Формирование последовательности F 1 при векторном представлении величин
На этом первый шаг алгоритма деления по частям закончен. Получен F 1 (х) , куда вошел первый промежуточный остаток R 1 (x), контролирующий деление первого блока из ℓ левых бит входной последовательности А (х).
Шаг 2
Очередной шаг алгоритма заключается в том, что в F 1 (х) выделяем ℓ левых бит. Этот отрезок должен быть обозначен А 2 (х). Оставшаяся правая часть F 1 (х) – это А `2 (х). В соответствии с (3), (4) находим выражение остатка R 2 (x) и последовательности F 2 (х).
Рис. 2. Формирование последовательности F 2 при векторном представлении величин
На рис. 2 проиллюстрировано получение F 2 . Предпринята попытка масштабно отобразить изменение участвующих в деле векторов. Здесь показано, что после второго шага F 2 все еще имеет справа (n-k) нулей. Это эквивалентно допущению, что деление входного вектора А на отрезки длины ℓ двумя шагами не исчерпывается.
Делимое (в его стартовом понимании) после второго шага имеет вид:
(6)
В общем случае, пока (k-iℓ)≥(n-k) вектор F i должен будет иметь справа (n-k) нулей. Это, как известно, место контрольных бит в словах циклического кодового слова. Они пока не сформированы.
Шаг s‑1
В процессе выполнения (s ‑1 ) – го шага мы оперируем векторами длины ( n - k + m 0 ) (см. рис. 3). К этому времени все отрезки длины ℓ в составе входного вектора будут исчерпаны и (если в общем случае k не делится нацело на ℓ ) у нас остаётся от входной последовательности вычисленный остаток R s -1 и «правый» отрезок A `s-1 длины m0 <ℓ.
В соответствии с выражениями (4) и (5) получим «выходной продукт» данного шага – многочлен F s -1 (х) = R s -1 ( x ) x ( k -( s -1)ℓ) + A ` s -1 (х) х( n - k ) =R s -1 ( x ) x ( m 0) + A ` s -1 (х) х( n - k ) , т. к. k =( s ‑1)ℓ+ m 0 по определению этих величин.
Рис. 3. Формирование последовательности F s -1 при векторном представлении величин