Линейные переключательные схемы

КОДИРУЮЩИЕ УСТРОЙСТВА

5.1.1. Устройство умножения. Устройства умножения реализуют на полусумматорах (М2) и D-триггерах, которые можно рассматривать как элементы задержки на один такт времени [11].

Пусть задан некоторый фиксированный полином g(x)=g_kx^k+g_l-1x^l-1+…+g₁x+g₀, а также существует произвольный полином p(x)=p_l-1x^l-1+p_l-2x^l-2+…+p₁x+p₀. Схема устройства умножения p(x)g(x)представлена на рис.5.1.

Рис.5.1

При реализации конкретной схемы для умножения на фиксированный полином выполняется правило. Если коэффициент g_i=1, то между элементами D_i-1 и D_i находится полусумматор М2, а если g_i=0, то выход элемента D_i-1 непосредственно связан со входом элемента D_i.

При работе устройства умножения коэффициенты полинома p(x) поступают, начиная со старшего разряда по тактам синхронизации. В исходном состоянии все элементы памяти (D-триггера) находятся в нулевом состоянии.

Пример. Пусть p(x)=x²+x+1, а g(x)=x+1. Устройство умножения на g(x) приведено на рис.5.2. В табл.5.3 приведены временные диаграммы, поясняющие работу устройства умножения.

Рис.5.2

Таблица 5.3

Если умножать p(x)g(x) в алгебраической форме, то получим p(x)g(x)=(x²+x+1)(x+1)=х³+1. Этот же результат получен и в устройстве умножения и показан на временных диаграммах (см. табл.5.1).

5.1.2. Устройство деления. Пусть задан фиксированный полином g(x)и произвольный полином p(x). Старшая степень полинома g(x) есть deg[g(x)]=k, а старшая степень полинома p(x) - deg[p(x)]=l-1. Полином p(x) -делимое, а полином g(x) - делитель. Устройство деления p(x)/g(x)представлено на рис.5.3.

Рис.5.3

Структура схемы предусматривает, что если g_i=1, то между элементами D_i-1 и D_i находится полусумматор М2, а если g_i=0, то выход элемента D_i-1 непосредственно связан со входом элемента D_i.

При работе устройства в течение первых k тактов происходит заполнение элементов памяти, т.к. l-1>k. Следовательно, до k–го такта обратная связь не работает, и в схеме осуществляется обычный сдвиг. Начиная с (k+1)-го такта, на выходе устройства начинают появляться элементы частного от деления, и вступает в работу обратная связь. После l тактов на выходе устройства будет сформирован последний элемент частного, а в элементах D_i будет записан остаток от деления.

Пример. Пусть p(x)=x²+x+1, а g(x)=x+1. Устройство умножения на g(x) приведено на рис.5.2. В табл.5.1 приведены временные диаграммы, поясняющие работу устройства умножения.

Пример. Пусть p(x)=x⁴+x³+х+1, а g(x)=х²+x+1. Устройство деления на g(x) приведено на рис.5.4. В табл.5.4 приведены временные диаграммы, поясняющие работу устройства умножения.

Рис.5.4

Таблица 5.4

При делении p(x) на g(x) остаток равен нулю, а частное от деления равно х²+1.

5.1.3. Устройство одновременного умножения и деления. Пусть v(x) - фиксированный полином, deg[v(x)]=k, g(x) - фиксированный полином, deg[g(x)]=k, p(x) - произвольный полином, deg[p(x)]=l-1. Устройство осуществляет операцию p(x)v(x)/g(x). Схема устройствапредставлена на рис.5.5.

Рис.5.5

Если на вход подать полином p(x), то через l тактов на выходе получим последний коэффициент частного от деления p(x)v(x)/g(x), а в элементах D_i будет зафиксирован остаток от деления.