Изучение принципов построения и исследование линейных переключательных схем (ЛПС) в устройствах умножения и деления многочленов (Лабораторная работа № 6)

ЛАБОРАТОРНАЯ РАБОТА №6

ЛИНЕЙНЕЙНЫЕПЕРЕКЛЮЧАТЕЛЬНЫЕ СХЕМЫ (ЛПС)

ЦЕЛЬ РАБОТЫ: изучение принципов построения и исследование линейных переключательных схем (ЛПС) в устройствах умножения и деления многочленов.

КРАТКИЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

ЛПС называется любая схема , содержащая конечное число сумматоров, устройств памяти и устройств умножения на константу, соединённых любым доступным способом. Умножение на 0 или 1 означает соответственно разрыв или наличие соединения обратной связи. Поэтому ЛПС, позволяющие умножать или делить двоичные многочлены, состоят только из ячеек памяти и сумматоров и представляют собой регистры сдвига с логическими обратными связями.

Данные регистры являются основными устройствами, используемыми при кодировании и декодировании циклических кодов.

1.  Умножение многочленов

На рис. 6.1 изображена одна из схем, используемая для умножения произвольного двоичного многочлена:

а (х) = а _n-1 х  ^n-1  + а _n-2  х ^n-2 +…+ а ₁ х  + а _0,   (а _i € {0, 1})

на фиксированный многочлен без нулевых членов:

h (х) =  х ^r + х ^r-1  +… + х ² + х + 1,  (h _i = 1).

Вход и выход схемы предполагаются последовательными.

На вход схемы поступают коэффициенты многочлена а (х) , начиная с коэффициентов старших разрядов, после чего следует r нулей. Произведение, равное:

а (х) h (х) = а _n-1 х ^{n + r -1} + (а _{n - 2}  + а _{n - 1}) x ^{n + r - 2} + … + (a ₀ + a ₁) x + a ₀

формируется на выходе схемы за (n + r) тактов.

Для примера разобрано построение схемы (рис. 6.2) , осуществляющей умножение любого многочлена на входе на фиксированный многочлен h (x) = x ³ + x  ² + 1. Цепь тактовых импульсов на схеме не показана.

Построение схемы отвечает следующему правилу:

- число ячеек памяти равно степени многочлена h (x);

- число сумматоров на 1 меньше числа нулевых членов многочлена;

- сумматоры устанавливаются перед ячейками регистра, соответствующими ненулевыми членами многочлена тех же степеней. Ячейка старшей степени отсутствует и сумматор на выходе схемы стоит перед отсутствующей ячейкой;

- сумматор, соответствующий младшему члену многочлена, отбрасывается, т.е. сумматор на входе ячейки П1 отсутствует;

- множимое подаётся одновременно на вход П1 и на все сумматоры.

Если коэффициент при  х ⁰  равен 0, то число сумматоров равно числу ненулевых членов h (x) и множимое подаётся на сумматоры.

Процесс умножения многочлена а (х) = x ² + x  (двоичное представление 110) на многочлен h (x) = х ³ + х ² + 1 представлен в табл. 6.1. Произведение а (х) * h (x) = x ⁵ + x ³+ x ²+ x (101110) формируется на выходе за h + r = 6 тактов. Первоначально в ячейках памяти содержатся нули.

Таблица 6.1.

2.  Деление многочленов

Структурная схема регистра сдвига с логическими обратными связями , осуществляющая деление на двоичный фиксированный многочлен степени r  без нулевых членов,  представлен на рис.6.3. Ячейки памяти в исходном состоянии должны содержать нули. Для первых r тактов работы схемы, пока первый входной сигнал не достигнет конца регистра, выходные символы равны нулю. На  (r + 1) такте появляется первый ненулевой выходной символ, который равен первому коэффициенту частного, а в регистре будет находиться остаток от деления (остаток может быть и нулевым).

На рис. 6.4. изображена схема, предназначенная для деления на многочлен g (x) = x ³ + x + 1. Поступление тактовых импульсов на схеме не показано.

Построение регистров подобной структуры отвечает следующему правилу:

- число ячеек регистра равно степени многочлена, на который производится деление;

- число сумматоров на 1 меньше числа ненулевых членов многочлена g (x);

- сумматоры ставятся перед ячейками регистра, соответствующими ненулевыми членами многочлена g(x) тех же степеней;

- ячейки памяти для члена со старшей степенью и соответствующий ей сумматор отбрасываются, т.к. при деление многочлена старшие члены делимого и делителя всегда равны 1, и складываясь по модулю два, всегда дают в результате 0.

Последовательность операций в схеме при делении многочлена а(х)= х ⁶+ х ⁵ представлена в табл. 6.2. Деление осуществляется за 7 тактов. Первоначальное состояние всех ячеек регистра – ненулевое.

Таблица 6.2.

В 1 такте единица старшего разряда делимого записывается в ячейку П1. При поступлении 2 тактового импульса(такт 2) эта единица считывается с ячейки П1 и записывается в ячейку П2. Одновременно в ячейку П1 поступает второй разряд делимого. На третьем такте все ячейки памяти будут заполнены и в цепи обратной связи (ОС) с выхода ячейки П3 появится сигнал 1. В четвёртом такте единица ОС складывается с нулевым сигналом на входе схемы и ячейка П1 переходит в состояние 1.

Одновременно единица ОС складывается во втором сумматоре с нулевым сигналом, считываемым с ячейки П1, в результате чего ячейка П2 также перейдёт в состояние 1 и т.д. На 7 такте в ячейках памяти появится остаток от деления.