Лекции по Теоретическим основам цифровой связи   

6. Канальное кодирование: часть 1

6.7.4. Логическая схема для реализации полиномиального деления

Выше показывалось, что при циклическом сдвиге полинома кодового слова и кодировании полинома сообщения применяется операция деления полиномов друг на друга. Такие операции легко реализуются в схеме деления (регистр сдвига с обратной связью). Итак, пусть даны два полинома V(Х) и g(X), где

и

,

причем . Схема деления, приведенная на рис. 6.16, выполняет полиномиальное деление V(X) на g(X), определяя, таким образом, частное и остаточное слагаемое.

В исходном состоянии разряды регистра содержат нули. Коэффициенты V(X) поступают и продвигаются по регистру сдвига по одному за такт; начиная с коэффициентов более высокого порядка. После р-го сдвига частное на выходе равно ; это слагаемое наивысшего порядка в частном. Далее для каждого коэффициента частного , из делимого нужно вычитать полином . Это вычитание обеспечивает обратная связь, отображенная на рис. 6.16. Разность крайних слева р слагаемых остается в делимом, а слагаемое обратной связи формируется при каждом сдвиге схемы и отображается в виде содержимого регистра. При каждом сдвиге регистра разность смещается на один разряд; слагаемое наивысшего порядка (которое по построению схемы равно нулю) удаляется, в то время как следующий значащий коэффициент в V(Х) перемещается на его место. После всех сдвигов регистра, на выход последовательно выдается частное, а остаток остается в регистре.

Рис.6.16. Логическая схема для реализации полиномиального деления

Пример 6.9. Схема полиномиального деления

Используя схему деления, показанную на рис. 6.16, разделите на ; Найдите частное и остаточное слагаемое. Сравните реализацию схемы и действия, происходящие при прямом делении полиномов.

Решение

схема деления должна выполнить следующее действие.

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

Рис. 6.17. Схема деления для примера 6.9.

Входная очередь Номер сдвига Содержимое регистра Выход и обратная связь

0001011

0

000

-

000101

1

100

0

00010

2

110

0

0001

3

011

0

000

4

011

1

00

5

111

1

0

6

101

1

-

7

100

1

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

Прямое деление полиномов дает результат, показанный ниже.

X6 + X5 + X3 |X3 + X + 1

обратная связь после 4-го сдвига → X6 + X4 + X3 X3+X2+X+1

обратная связь после 4-го сдвига → X5 + X4 ↑ ↑ ↑ ↑

обратная связь после 5-го сдвига → X5+ X3 + X2 4 5 6 7

регистр после 5-го сдвига → X4 + X3 + X2

обратная связь после 6-го сдвига→ X4 + X2 + X

регистр после 6-го сдвига → X3 + X

обратная связь после 7-го сдвига → X3 + X + 1

регистр после 7-го сдвига → 1

(остаток)



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.