2.2.4. Примеры выполнения вертикальных операций.

Пример 1. Выполним операции элементарного деления количества единиц на k=4 над кодами а1 {0001010}и а2 {1110110}.

На рис. 1 а) и б) показаны схемы выполнения элементарных делений. Затемнением выделены остатки от деления.

По операндам получены упорядоченные коды: a₀₁{ 0 0 0 0 0 1 1 } и a₀₂{ 00 11111}.

Центральные k-e разряды упорядоченных кодов определяют частные q1=0 и q2=1. Справа от q1 и слева от q2 выделяются коды остатков r1{13)=ao{ 0 1 1} и r2{13}=ао{ 001}.

Пример 1. Выполним операцию вертикального сложения в СС k=2 над кодом а {1 1 0 1 0 1 1 0 1 0 1 I 0 1 0 } с. разрядностью п=15. Процесс вычислений показан на рис. 2.

Исходный параллельный код а является операндом первой операции полноразрядного деления. Код разбит на 7 сегментов, пронумерованных справа налево. Полноразрядное деление содержит 7операций элементарного деления. Операндом первого элементарного деления является первый сегмент кода а. Операнд 010 приводится к упорядоченному коду 001. Центральный бит упорядоченного кода является разрядом 0 частного, а справа от него расположен остаток 1. Второе элементарное деление определяет разряд частного 1 и слева от него остаток 1.

Операнд каждой следующей элементарной операции составляется из остатка, вычисленного предыдущим элементарным делением, и очередного сегмента кода а. Остаток последней элементарной операции является остатком полноразрядного деления. Разряды частного, вычисленные элементарными операциями, составляют (в произвольном порядке) 7-разрядный код частного первого полноразрядного деления.

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

Таким образом, 9 единиц кода а делится на 2 с получением частного, содержащего 4 единицы, и остатка 1. Далее 4 единицы кода частного 1010110 делятся на 2 с вычислением частного, содержащего 2 единицы, и остатка 0. В завершении вычислений 2 единицы частного 101 делятся на 2 с вычислением частного 1 и остатка 0. Остатки и последнее частное являются разрядами результата 1001₂ операции вертикального сложения.

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

Пример закончен.

Разряды параллельного кода могут обрабатываться одновременно несколькими элементарными операциями деления.

Пример 3.

Пусть задан параллельный код 100101011010111 и основание системы счислении k = 4:

Выполним подсчет количества и единиц этого кода в двоично-кодированной системе счисления.

Для этого выделим в нем множества из 2k-1 бит и выполним над ними элементарные операции деления на k. Выпишем полученные остатки от деления, дополним их разрядами исходного кода до множеств из 2k-l бит и выполним следующий уровень элементарных операций деления на k. После обработки всех разрядов параллельного кода и получения одного остатка следует подсчет количества единиц в разрядах этого остатка и разрядах частного в двоичной системе счисления.

В рассмотренном на рис. 3 примере в параллельном коде выделяются два множества из 2k-1 бит, над которыми выполняются две элементарные операции деления на k. В каждой из них упорядочиваются единицы, центральный, k-й бит выделяется двойной рамкой как разряд частного, справа или слева от него (соответственно при нулевом или единичном значении) выбирается остаток, помеченный затемненным полем. Остатки 111 и 001 от деления дополняются разрядом 8 параллельного кода и над полученным множеством бит выполняется следующая элементарная операция деления. Над разрядами полученного упорядоченного остатка 001 и разрядами частных, полученных во всех трех элементарных операциях, выполняется подсчет количества единиц делением на 2.

Построим схему однотактного вертикального сумматора на элементарных делителях количества единиц на kv. на 2 (рис. 4).

Устройство содержит три элементарных делителя D/k 13 количества единиц на k, два элементарных делителя D/2 4, 5 количества единиц на 2 и работает следующим образом. На входы устройства поступают разряды 115 параллельного кода. Два множества 1- 7 и 9  15 разрядов кода принимаются на входы элементарных делителей D/k 1 и 2. Они вычисляют трехразрядные остатки, которые дополняются разрядом 8 кода и поступают на входы соответствующих полей элементарного делителя D/k 3. С выхода остатка этого делителя и выходов частного всех делителей D/k выдается трехразрядный остаток и три бита частного на входы элементарных делителей D/2 4 и 5, которые (на выходах частного q и остатка r) формируют биты младшей 2, 1 и старшей 4, 3 цифр результата.

Опишем операцию упорядочения единиц в элементарном делителе D/k 3 количества единиц на k через операции доупорядочения единиц.

На входы этого делителя поступают упорядоченные остатки с выходов элементарных делителей 1 и 2, а также разряд 8 кода. Доупорядочение единиц входного кода элементарного делителя 3 выполним в две операции:

объединением трехразрядного кода с разрядом и далее второго трехразрядного кода с полученным четырехразрядным кодом.

Опишем объединение трехразрядного упорядоченного кода Аз = A {a1, a2, а3} с разрядом B1 = B{b1} в четырехразрядный упорядоченный код D4 = D{d1, d2, d3, d4} :

d1=a1 + b1;

d2=a1b1 + a2;

d3=a2b1 + a3;

d4=a3b1.

Опишем объединение трехразрядного упорядоченного кода Сз = C{c1, c2, с3} с четырехразрядным упорядоченным кодом D4 = D{d1, d2, d3, d4} в семиразрядный упорядоченный код Е₇ = E{e1, e2, e3, е4, e5, е6, e7} :

e1=c1+d1;

e2=c1d1+c2+d2;

e3=c1d2+c2d1+c3+d3;

e4=c2d2+c1d3+c3d1+d4;

e5=c2d3+c3d2+c1d4;

e6=c3d3+c2d4;

e7=c3d4;

Билет №110. Использование матричного параллелизма в архитектуре специализированных ЭВМ