УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ В КОДЕ "1 ИЗ 4"
APPARATUS FOR MULTIPLYING NUMBERS IN "1 OUT OF 4" CODE

Изобретение относится к вычислительной технике, в частности к устройствам обработки данных, и может быть использовано для построения вычислительных систем с повышенной достоверностью получения результата и с высоким быстродействием.
Известно устройство для умножения чисел (RU №2021633 С1, МПК G06F 7/52, заявлено 10.07.1991, опубл. 15.10.1994), содержащее n одноразрядных узлов умножения (n - разрядность множимого), две группы по n буферных регистров, n комбинационных сумматоров первой группы и (n+1) комбинационных сумматоров второй группы, (n+1) регистров промежуточного результата, n триггеров переноса, (n-1) коммутаторов и узел формирования коррекции с соответствующими связями.
Недостатком данного устройства является то, что в режиме функционирования не проводится проверка правильности выдаваемых данных, что, в свою очередь, не дает возможности повысить достоверность выдаваемых результатов.
Причины, препятствующие достижению требуемого технического результата, заключаются в отсутствии средств, обеспечивающих возможность проверки правильности выдаваемого кода данных.
Известен ускоренный умножитель на нейронах (RU №2322688 С2, МПК G06F 7/52, заявлено 03.04.2006, опубл. 20.10.2007, БИ №11), содержащий блок ввода данных, блок регистра множимого, блок регистра множителя, блок суммирования, блок дешифратора, блок хранения результата, блок управления. В умножителе происходит умножение двоичных чисел. Произведение чисел получается как сумма частичных произведений, путем анализа младших разрядов множителя, сдвига на два разряда множителя вправо и сдвига множимого влево.
Недостатком данного устройства является то, что в режиме функционирования не проводится проверка правильности выдаваемых данных, что, в свою очередь, не дает возможности повысить достоверность выдаваемых результатов.
Причины, препятствующие достижению требуемого технического результата, заключаются в отсутствии средств, обеспечивающих возможность проверки правильности выдаваемого кода данных.
Известно устройство для умножения чисел по модулю (патент РФ №2143723 С1, МПК G06F 7/52, G06F 7/72, заявлено 29.07.98, опубл. 27.12.99), содержащее первый и второй преобразователи двоичного кода по первому внутреннему модулю, первый и второй преобразователи двоичного кода по второму внутреннему модулю, с первого по шестой блоки элементов И, табличный вычислитель, преобразователи унитарного кода по первому и второму модулям и сумматор по модулю. Устройство обеспечивает умножение чисел в системе остаточных классов по двум модулям.
Недостаток данного устройства заключаются в том, что не проводится проверка правильности выдаваемых данных, что, в свою очередь, не дает возможности повысить достоверность выдаваемых результатов.
Причины, препятствующие достижению требуемого технического результата, заключаются в отсутствии средств, обеспечивающих возможность проверки правильности выдаваемого кода данных.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство для умножения чисел в коде "1 из 4" (RU №2251144 С1, МПК G06F 7/52, заявлено 28.10.2003, опубл. 27.04.2005, БИ №12), содержащее регистр тетрадного сдвига, блок частичных произведений, блок сумматоров, регистр результата в коде "1 из 4", блок контроля, входы четверичных разрядов в коде "1 из 4" первого и второго сомножителей устройства, вход записи устройства, вход синхроимпульсов устройства, вход константы 0 в коде "1 из 4" и выходы признака ошибки, при этом регистр тетрадного сдвига содержит n тетрад, где n - количество четверичных разрядов сомножителей, причем входы четверичных разрядов в коде "1 из 4" первого сомножителя устройства соединены с информационными входами соответствующих тетрад регистра тетрадного сдвига, информационные входы сдвига четверичных разрядов в коде "1 из 4" с первой по (n-1)-ю тетрад соединены соответственно с выходами четверичных разрядов в коде "1 из 4" со второй по n-ю тетрад регистра тетрадного сдвига, информационные входы сдвига четверичных разрядов n-й тетрады соединены с входом константы 0 в коде "1 из 4", блок частичных произведений содержит n узлов частичных произведений в коде "1 из 4", причем входы первой группы тетрад блока частичных произведений соединены с выходами младшей первой тетрады регистра тетрадного сдвига, причем блок сумматоров содержит (n-1) сумматор в коде "1 из 4", а регистр результата в коде " 1 из 4" содержит 2n тетрад четверичных разрядов, причем информационные входы с первой по n-ю тетрад четверичных разрядов регистра результата в коде "1 из 4" соединены с выходами старшей группы четверичных разрядов соответственно со второй по (n+1)-ю тетрад четверичных разрядов регистра результата в коде "1 из 4", выходы четверичных разрядов с (n+2)-й по 2n-ю тетрад регистра результата в коде "1 из 4" соединены соответственно с входами четверичных разрядов второго слагаемого с первого по (n-1)-й сумматоров в коде "1 из 4", при этом блок контроля содержит 2n узлов контроля кода "1 из 4", выходы которых соединены с выходами признака ошибки устройства, входы с первого по (n+1)-й узлов блока контроля кода "1 из 4" соединены с выходами четверичных разрядов соответственно с первой по (n+1)-ю тетрад четверичных разрядов регистра результата в коде "1 из 4", вход записи устройства соединен с входом установки регистра результата в коде "1 из 4" и входом записи регистра тетрадного сдвига, вход синхроимпульсов устройства соединен с синхровходами регистра результата в коде "1 из 4" и регистра тетрадного сдвига.
Недостатком данного устройства является то, что на каждом шаге вычислений значения текущей накапливаемой суммы частичных произведений устанавливаются на регистре результата через время, равное сумме времени вычисления поразрядных произведений, плюс время поразрядного суммирования и плюс время на выполнение последовательной коррекции n межразрядных переносов.
Причины, препятствующие достижению требуемого технического результата, заключаются в том, что в устройстве отсутствуют средства, обеспечивающие хранение поразрядных переносов и связи для передачи их на следующем шаге.
Техническим результатом изобретения является увеличение быстродействия устройства.
Предлагаемое устройство отличает регулярность связей узлов и связей, а также обеспечение повышенной достоверности выдаваемого результата, за счет поразрядного контроля выполнения операции умножения чисел, и равномерное распределение энергии по разрядам в процессе работы, что особенно важно при реализации аппаратуры устройства в виде СБИС.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройство для умножения чисел в коде "1 из 4", содержащее регистр тетрадного сдвига, блок частичных произведений, блок сумматоров, регистр результата в коде "1 из 4", блок контроля, входы четверичных разрядов в коде "1 из 4" первого и второго сомножителей устройства, вход записи устройства, вход синхроимпульсов устройства, вход константы 0 в коде "1 из 4" и выходы признака ошибки, при этом регистр тетрадного сдвига содержит n тетрад, где n - количество четверичных разрядов сомножителей, причем входы четверичных разрядов в коде "1 из 4" первого сомножителя устройства соединены с информационными входами соответствующих тетрад регистра тетрадного сдвига, информационные входы сдвига четверичных разрядов в коде "1 из 4" с первой по (n-1)-ю тетрад соединены соответственно с выходами четверичных разрядов в коде "1 из 4" со второй по n-ю тетрад регистра тетрадного сдвига, информационные входы сдвига четверичных разрядов n-й тетрады соединены с входом константы 0 в коде "1 из 4", блок частичных произведений содержит n узлов частичных произведений в коде "1 из 4", причем входы первой группы тетрад блока частичных произведений соединены с выходами младшей первой тетрады регистра тетрадного сдвига, причем блок сумматоров содержит (n-1) сумматор в коде "1 из 4", а регистр результата в коде "1 из 4" содержит 2n тетрад четверичных разрядов, причем информационные входы с первой по п-ю тетрад четверичных разрядов регистра результата в коде "1 из 4" соединены с выходами старшей группы четверичных разрядов соответственно со второй по (n+1)-ю тетрад четверичных разрядов регистра результата в коде "1 из 4", выходы четверичных разрядов с (n+2)-й по 2n-ю тетрад регистра результата в коде "1 из 4" соединены соответственно с входами четверичных разрядов второго слагаемого с первого по (n-1)-й сумматоров в коде "1 из 4", при этом блок контроля содержит 2n узлов контроля кода "1 из 4", выходы которых соединены с выходами признака ошибки устройства, входы с первого по (n+1)-й узлов блока контроля кода "1 из 4" соединены с выходами четверичных разрядов соответственно с первой по (n+1)-ю тетрад четверичных разрядов регистра результата в коде "1 из 4", вход записи устройства соединен с входом установки регистра результата в коде "1 из 4" и входом записи регистра тетрадного сдвига, вход синхроимпульсов устройства соединен с синхровходами регистра результата в коде "1 из 4" и регистра тетрадного сдвига, дополнительно введены регистр второго сомножителя, блок переносов произведения, первый блок сумматоров переносов, блок триггеров переноса суммы, второй блок сумматоров переносов, блок переносов результата и вход сдвига, причем регистр второго сомножителя содержит n тетрад, причем входы четверичных разрядов в коде "1 из 4" второго сомножителя устройства соединены с информационными входами соответствующих тетрад регистра второго сомножителя, а выходы регистра соединены с входами второй группы соответствующих тетрад блока частичных произведений, при этом блок переносов произведения и первый блок сумматоров переносов содержат по n узлов, причем выходы тетрад блока частичных произведений в коде " 1 из 4" соединены с входами первой группы соответствующих узлов первого блока сумматоров переносов, входы второй группы которого соединены с выходами в коде "1 из 3" соответствующих узлов блока переносов произведения, выход переноса узлов первого блока сумматоров переносов соединен с первым входом одного переноса соответствующих узлов блока переносов произведения, второй вход одного переноса и вход двух переносов узлов блока переносов произведения соединены с одноименными выходами соответствующих узлов тетрад блока частичных произведений в коде "1 из 4", выходы в коде "1 из 4" с первого по (n-1)-й узлов первого блока сумматоров переносов соединены с соответствующими входами четверичных разрядов в коде "1 из 4" первого слагаемого соответственно с первого по (n-1)-й сумматоров блока сумматоров, выходы в коде "1 из 4" n-го узла первого блока сумматоров переносов соединены с информационными входами 2n-й тетрады четверичных разрядов регистра результата в коде "1 из 4", при этом блок триггеров переноса суммы и второй блок сумматоров переносов содержат по (n-1) узлов, причем входы первой группы в коде "1 из 4" с первого по (n-1)-й узлов второго блока сумматоров переносов соединены с информационными выходами соответственно с первого по (n-1)-й сумматоров в коде "1 из 4" блока сумматоров, входы второй группы в коде "1 из 2" с первого по (n-1)-й узлов второго блока сумматоров переносов соединены с соответствующими выходами соответственно с первого по (n-1)-й узлов блока триггеров переноса суммы, выход переноса с первого по (n-1)-й узлов второго блока сумматоров переносов соединен с первым входом переноса соответствующих узлов блока триггеров переноса суммы, второй вход переноса которых соединен с выходами переносов соответственно с первого по (n-1)-й сумматоров в коде "1 из 4" блока сумматоров, блок переносов результата содержит (n-1) узлов, причем информационные входы первой группы в коде "1 из 4" с первого по (n-1)-й узлов которого соединены с информационными выходами четверичных разрядов с (n+2)-й по 2n-ю тетрад регистра результата в коде "1 из 4", первые входы переносов с первого по (n-1)-й узлов блока переносов результата соединены с прямым выходом единицы в коде "1 из 2" соответственно с первого по (n-1)-й узлов блока триггеров переноса суммы, вторые входы переносов со второго по (n-1)-й узлов блока переносов результата соединены с выходами переносов соответственно с первого по (n-2)-й узлов блока переносов результата, второй вход переносов первого узла блока переносов соединен с константой нуля, входы с (n+2)-го по 2n-й узлов блока контроля кода "1 из 4" соединены с выходами четверичных разрядов соответственно с первого по (n-1)-й узлов блока переносов результата в коде "1 из 4", вход синхроимпульсов устройства также соединен с синхровходами узлов блока переносов произведения и блока триггеров переноса суммы, вход записи устройства также соединен с входом записи регистра второго сомножителя, с входами установки узлов блока переносов произведения и блока триггеров переноса суммы, вход сдвига устройства соединен с входом сдвига с первого по (n-1)-й узлов блока переносов результата.
i
i
i
i
i
На фиг.1 представлена функциональная схема предлагаемого устройства для умножения чисел в коде "1 из 4"; на фиг.2 представлен вариант реализации узла 3 блока частичных произведений; на фиг.3 представлен вариант реализации узла 6 блока сумматора в коде "1 из 4"; на фиг.4 представлен вариант реализации узла 10 блока переноса результата; на фиг.5 представлен вариант реализации узла 4 блока переносов произведения; на фиг.6 представлен вариант реализации узла 7 блока триггеров переноса суммы; на фиг.7 приведены временные диаграммы управляющих сигналов.
1
n
1
n
1
n
1
n
1
n
1
n-1
1
n-1
1
n-1
1
2n
1
n-1
1
2n
Устройство для умножения чисел в коде "1 из 4" (фиг.1) содержит регистр тетрадного сдвига 1, регистр второго сомножителя 2, блок частичных произведений 3, блок переносов произведения 4, первый блок сумматоров переносов 5, блок сумматоров 6, блок триггеров переноса суммы 7, второй блок сумматоров переносов 8, регистр результата в коде "1 из 4" 9, блок переносов результата 10, блок контроля 11, входы четверичных разрядов в коде "1 из 4" первого В и второго А сомножителей устройства, вход записи устройства 12, вход синхроимпульсов устройства 13, вход константы 0 в коде "1 из 4" 14, вход сдвига 15 и выходы признака ошибки 16. При этом регистр тетрадного сдвига 1 содержит n тетрад четверичных разрядов в коде "1 из 4" 1…1, где n - количество четверичных разрядов сомножителей, и предназначен для первого сомножителя, осуществляет сдвиг в сторону младших разрядов потетрадно за один такт и вводом константы 0 в коде " 1 из 4" с входа 14 в старшие разряды, регистр второго сомножителя 2 содержит n тетрад четверичных разрядов в коде "1 из 4" 2…2, блок частичных произведений 3 содержит n узлов частичных произведений 3…3, блок переносов произведения 4 содержит n узлов хранения переносов в коде " 1 из 3" 4…4, первый блок сумматоров переносов 5 содержит n узлов в коде "1 из 4" 5…5, блок сумматоров 6 содержит (n-1) сумматор в коде "1 из 4" 6…6, блок триггеров переноса суммы 7 содержит (n-1) узлов хранения переносов 7…7, второй блок сумматоров переносов 8 содержит (n-1) узлов в коде "1 из 4" 8…8, регистр результата в коде "1 из 4" 9 содержит 2n тетрад четверичных разрядов 9…9, блок переносов результата 10 содержит (n-1) узлов в коде "1 из 4" 10…10, блок контроля 11 содержит 2n узлов контроля в коде "1 из 4" 11…11.
i
1
(n-1)
2
n
Входы четверичных разрядов в коде "1 из 4" первого сомножителя В устройства соединены с информационными входами соответствующих тетрад 1 регистра 1 тетрадного сдвига, информационные входы сдвига четверичных разрядов в коде "1 из 4" с первой по (n-1)-ю тетрад 1-1 соединены соответственно с выходами четверичных разрядов в коде "1 из 4" со второй по n-ю тетрад 1-1n регистра 1 тетрадного сдвига, информационные входы сдвига четверичных разрядов n-й тетрады 1 соединены с входом 14 константы 0 в коде "1 из 4".
i
Входы четверичных разрядов в коде "1 из 4" второго сомножителя А устройства соединены с информационными входами соответствующих тетрад 2 регистра 2 второго сомножителя.
i
i
i
i
Входы первой группы узлов 3 тетрад блока частичных произведений 3 соединены с выходами младшей первой тетрады 1 регистра тетрадного сдвига 1, входы второй группы узлов 3 тетрад блока частичных произведений 3 соединены с выходами соответствующих узлов 2 тетрад регистра 2 второго сомножителя.
i
i
i
i
i
i
Выходы узлов 3 тетрад блока частичных произведений 3 в коде "1 из 4" соединены с входами первой группы соответствующих узлов 5 первого блока 5 сумматоров переносов, входы второй группы которого соединены с выходами в коде "1 из 3" соответствующих узлов 4 блока переносов произведения 4, выход переноса ПМ1 узлов 5 первого блока сумматоров переносов 5 соединен с первым входом одного переноса ПМ1 соответствующих узлов 4 блока переносов произведения 4, второй вход одного переноса Р1 и вход двух переносов Р2 которых соединены с одноименными выходами соответствующих узлов 3 тетрад блока частичных произведений 3 в коде "1 из 4".
1
(n-1)
1
(n-1)
n
2n
Выходы в коде "1 из 4" с первого по (n-1)-й узлов 5-5 первого блока сумматоров переносов 5 соединены с соответствующими входами четверичных разрядов первого слагаемого соответственно с первого по (n-1)-й узлов 6-6 блока сумматоров 6 в коде "1 из 4", выходы в коде "1 из 4" n-го узла 5 первого блока сумматоров переносов 5 соединены с информационными входами 2n-й тетрады 9 четверичных разрядов регистра результата 9 в коде "1 из 4".
1
(n-1)
1
(n-1)
1
(n-1)
1
(n-1)
1
(n-1)
1
(n-1)
1
(n-1)
Входы первой группы в коде "1 из 4" с первого по (n-1)-й узлов 8-8 второго блока сумматоров переносов 8 соединены с информационными выходами соответственно с первого по (n-1)-й узлов 6-6 блока сумматоров 6 в коде "1 из 4", входы второй группы в коде "1 из 2" с первого по (n-1)-й узлов 8-8 второго блока сумматоров переносов 8 соединены с соответствующими выходами соответственно с первого по (n-1)-й узлов 7-7 блока триггеров переноса суммы 7, выход переноса ПС с первого по (n-1)-й узлов 8-8 второго блока сумматоров переносов 8 соединен с первым входом переноса ПС соответствующих узлов 7-7 блока триггеров переноса суммы 7, второй вход переноса ПS которых соединен с выходами переносов ПS соответственно с первого по (n-1)-й сумматоров 6-6 в коде "1 из 4".
1
n
2
(n+1)
(n+2)
2n
1
(n-1)
1
(n-1)
1
(n-1)
1
(n-1)
2
(n-1)
1
1
Информационные входы с первой по n-ю тетрад 9-9 четверичных разрядов регистра результата 9 в коде "1 из 4" соединены с выходами старшей группы четверичных разрядов соответственно со второй по (n+1)-ю тетрад 9-9 четверичных разрядов регистра результата 9 в коде "1 из 4", выходы четверичных разрядов с (n+2)-й по 2n-ю тетрад 9-9 регистра результата 9 в коде "1 из 4" соединены соответственно с входами четверичных разрядов второго слагаемого с первого по (n-1)-й узлов 6-6 блока сумматоров 6 в коде "1 из 4" и информационными входами первой группы в коде "1 из 4" с первого по (n-1)-й узлов 10-10 блока переносов результата 10, первые входы переносов ТП с первого по (n-1)-й узлов 10-10 блока переносов результата 10 соединены с прямым выходом ТП единицы в коде "1 из 2" соответственно с первого по (n-1)-й узлов 7-7 блока триггеров переноса суммы 7, вторые входы переносов П со второго по (n-1)-й узлов 10-10 блока переносов результата соединены с выходами переносов П соответственно с первого по (n-2)-й узлов 10-10(n-2) блока переносов результата 10, второй вход переносов П первого узла блока переносов 10 соединен с константой нуля.
1
(n+1)
2
(n+1)
(n+2)
n
1
(n-1)
Входы с первого по (n+1)-й узлов 11-11 блока 11 контроля кода "1 из 4" соединены с выходами четверичных разрядов соответственно с первой по (n+1)-ю тетрад 9-9 четверичных разрядов регистра результата 9 в коде "1 из 4", входы с (n+2)-го по 2n-й узлов 11-11 блока 11 контроля кода "1 из 4" соединены с выходами четверичных разрядов соответственно с первого по (n-1)-й узлов 10-10 блока переносов результата 10 в коде "1 из 4".
1
2n
Выходы 2n узлов 11-11 блока 11 контроля кода "1 из 4" соединены с выходами 16 признака ошибки устройства.
Вход 12 записи устройства соединен с входом установки регистра результата 9 в коде "1 из 4", входом записи регистра тетрадного сдвига 1, входом записи регистра второго сомножителя 2, с входами установки узлов блока переносов произведения 4 и блока триггеров переноса суммы 7.
Вход 13 синхроимпульсов устройства соединен с синхровходами узлов регистра результата 9 в коде "1 из 4", регистра тетрадного сдвига 1, блока переносов произведения 4 и блока триггеров переноса суммы 7.
1
(n-1)
Вход сдвига 15 устройства соединен с входом сдвига с первого по (n-1)-й узлы 10-10 блока переносов результата 10.
i
3i
2i
1i
0i
i
0i
1i
2i
3i
i
i
3i
2i
1i
0i
i
i
i
i
Возможный вариант узла частичных произведений в коде "1 из 4" 3 (фиг.2) содержит с первой по четвертую группы элементов И 17-20, группу элементов ИЛИ 21 и элемент ИЛИ 22. Группа элементов ИЛИ 21 содержит 4 элемента ИЛИ, каждая группа элементов И 17-20 содержит 4 элемента И, образуя матрицу 4×4. Первые входы одноименных элементов И с первого по четвертый каждой группы соединены между собой и соединены с соответствующими бинарными составляющими четверичного разряда сомножителя а a а а, являющиеся второй группой входов узла 3, вторые входы элементов И каждой группы с первой по четвертую соединены между собой и соединены с соответствующими бинарными составляющими четверичного разряда сомножителя b b b b, являющиеся первой группой входов узла 3. Выходы матрицы 4х4 элементов И подсоединены к входам группы элементов ИЛИ 21 и элементу ИЛИ 22 в соответствии с преобразованием входных значений сомножителей в частичные произведения и переносы, приведенным в таблице 1, а выходы группы элементов ИЛИ 21 являются группой выходов узла 3 бинарных составляющих четверичного разряда произведения с с с с, выход р1 элемента ИЛИ 22 является выходом одного переноса узла 3, выход р2 первого элемента четвертой группы элементов И 20 является выходом двух переносов узла 3.
i
i
3i
2i
1i
0i
3i
2i
1i
0i
i
i
3i
2i
1i
0i
i
i
Возможный вариант узла сумматора в коде "1 из 4" 6 (фиг.3) содержит с первой по четвертую группы элементов И 23-26, группу элементов ИЛИ 27 и элемент ИЛИ 28. Группа элементов ИЛИ 27 содержит 4 элемента ИЛИ, каждая группа элементов И 23-26 содержит 4 элемента И. Группы элементов И 23-26, аналогично узлу частичных произведений 3, образуют матрицу 4×4, но выходы матрицы соединены к входам группы элементов ИЛИ 27 и элементу ИЛИ 28 в соответствии с преобразованием входных значений слагаемых в сумму и перенос по таблице 2. Группы входов а а а а и b b b b являются группами первого и второго слагаемых узла 6 блока сумматоров 6, а выходы группы элементов ИЛИ 27 являются группой выходов узла 6 бинарных составляющих четверичного разряда суммы s s s s выход ПS элемента ИЛИ 28 является выходом переноса узла 6.
i
i
2i
1i
0i
Возможный вариант узла 5 первого блока сумматоров переносов 5 может быть реализован аналогично узлу 6 блока сумматоров 6, причем вторая группа входов включает только три бинарные составляющие b b b в коде "1 из 3", при этом образуется матрица 4×3 и исключаются 4-я группа элементов И 26 и соответствующие связи.
i
i
1i
0i
Возможный вариант узла 8 второго блока сумматоров переносов 8 может быть реализован аналогично узлу 6 блока сумматоров 6, причем вторая группа входов включает только две бинарные составляющие b b в коде "1 из 2", при этом образуется матрица 4×2 и исключаются 4-я и 3-я группы элементов И 26-25 и соответствующие связи.
i
1i
0i
i
3i
2i
1i
0i,
i
i
i-1
i-1
i-1
i
1i
0i
Возможный вариант узла 10 блока переносов результата 10 (фиг.4) содержит первую вторую группы элементов И 29-30, группу элементов ИЛИ 31, элемент ИЛИ 32, элемент ИЛИ-НЕ 33 и элемент И 34. Каждая группа элементов И 29-30 содержит 4 элемента И, образуя матрицу 4×2, выходы которой соединены с входами группы элементов ИЛИ 31, аналогично узлам блока сумматоров 6 в соответствии с таблицей 2 при двух бинарных составляющих b b в коде "1 из 2", выходы группы элементов ИЛИ 31 являются группой выходов узла 10 бинарных составляющих четверичного разряда произведения z z z z выход П является выходом переноса узла 10. Первые входы элементов ИЛИ 32 и ИЛИ-НЕ 33 соединены между собой и являются внешним вторым входом переноса П из младшего узла 10 блока переносов 10, вторые входы элементов ИЛИ 32 и ИЛИ-НЕ 33 соединены между собой и подключены к выходу элемента И 34, входы которого являются внешними первым входом переноса ТП из младшего узла 7 блока триггеров переноса суммы 7 и входом сдвига 15. Выходы элементов ИЛИ 32 и ИЛИ-НЕ 33 являются бинарными составляющими второго слагаемого b b для матрицы элементов 4х2.
i
i
i
i
i
i
i
i
i
i
i
i
0i
1i
2i
i
i
i
i
Возможный вариант узла 4 блока переносов произведения 4 (фиг.5) содержит синхронный D-триггер 35 с входом установки в единицу, два синхронных D-триггера 36-37 с входом установки в ноль, элемент ИЛИ-НЕ 38, элемент ИСКЛЮЧАЮЩЕЕ-ИЛИ 39, элемент И 40 и элемент ИЛИ 41. Входы синхронизации триггеров 35-37 соединены между собой и подключены к внешнему входу 13 синхронизации СИ, входы начальной установки триггеров 35-37 соединены между собой и подключены к внешнему входу 12 начальной записи ЗАПИСЬ. Логические элементы 38-41 преобразуют входы двух переносов Р2 и одного переноса Р1, от узла 3 частичных произведений, и вход одного переноса ПМ1, от узла 5 первого блока сумматоров переносов 5, в код "1 из 3" в соответствии с таблицей 3. Первые входы элементов ИЛИ-НЕ 38, ИСКЛЮЧАЮЩЕЕ-ИЛИ 39 и И 40 соединены между собой и подключены к внешнему входу одного переноса ПМ1, от узла 5, а их вторые входы соединены между собой и они подключены к внешнему входу одного переноса Р1, от узла 3, третий вход элемента ИЛИ-НЕ 38 соединен со вторым входом элемента ИЛИ 41 и подключены к внешнему входу двух переносов Р2, от узла 3, первый вход элемента ИЛИ 41 соединен с выходом элемента И 40. Выход элемента ИЛИ-НЕ 38 является младшим первым разрядом b составляющих в коде "1 из 3" и подключен к информационному входу D триггера 35, выход элемента ИСКЛЮЧАЮЩЕЕ-ИЛИ 39 является вторым разрядом b и подключен к информационному входу D триггера 36, выход элемента ИЛИ 41 является старшим третьим разрядом b и подключен к информационному входу D триггера 37. Выходы триггеров 37-35 являются выходами ТР2 ТР1 ТР0 узла 4 блока переносов произведения 4 в коде "1 из 3".
i
1i
0i
i
i,
i
i
i
i
Возможный вариант узла 7 блока триггеров переноса суммы 7 (фиг.6) содержит синхронный D-триггер 42 с входом установки в ноль и имеющий прямой и инверсный выходы, и элемент ИЛИ 43. Вход синхронизации триггера 42 подключен к внешнему входу 13 синхронизации СИ, вход начальной установки триггеров 42 подключен к внешнему входу 12 начальной записи ЗАПИСЬ. Выходы триггера 42 являются выходами b и b составляющих в коде "1 из 2" и являются выходами узла 7. Информационный вход D триггера 42 соединен с выходом элемента ИЛИ 43, первый вход которого соединен с внешним входом одного переноса ПС от узла 8, а второй вход соединен с внешним входом одного переноса ПS, от узла 6, которые также являются внешними входами узла 7.
Устройство для умножения чисел в коде "1 из 4" работает следующим образом.
Числа сомножителей В и А представлены в четверичной системе
n
2
1
n-1
1
B=b×4+…+b×4+b×4°,
n
2
1
n-1
1
А=a×4+…+а×4+а×4°,
1
1
n
n
где n - количество четверичных разрядов, a и b - младшие разряды, a и b - старшие разряды.
Устройство работает по алгоритму умножения с младших разрядов множителя и сдвигом накапливаемой суммы частичных произведений вправо в сторону младших разрядов
1
n
2
1
n-1
1
-1
Z=B×A=(((b×(а×4+…+а×4+a×4°)×4+
2
n
2
1
1
n-1
1
-1
+b×4×(а×4+…+а×4+а×4°))×4
+…+
n-1
n
2
1
n-1
1
-1
+b×(a×4+…+a×4+a×4°))×4+
n
n
2
1
n-1
1
-1
+b×(a×4+…+a×4+a×4°))×4,
i
i
где а и b представляются в коде "1 из 4".
Умножение и суммирование проводятся по соответствующим весам четверичных разрядов в коде "1 из 4".
i
В таблице 1 приведены коды преобразования входных значений сомножителей в выходные в узлах частичных произведений 3 при перемножении четверичных разрядов в коде "1 из 4" и условия формирования одного переноса Р1 и двух переносов Р2 в следующий четверичный разряд.
i-1
i-1
i
i-1
Очевидно, что возникновение одного P1 или двух P2 переносов из предыдущего (i-1)-го четверичного разряда не приводит к необходимости формирования дополнительного сигнала третьего переноса, так как максимальное значение кода частичного произведения при активном сигнале даже двух переносов Р2 из текущего разряда равно 0010 и, следовательно, даже два переноса P2 из предыдущего разряда дадут код результата 1000 без необходимости формирования дополнительного сигнала переноса.
i
В таблице 2 приведены коды преобразования входных значений слагаемых в выходные в сумматорах 6 при суммировании четверичных разрядов в коде "1 из 4" и условия формирования переноса П1.
i-1
i
i-1
Очевидно, что возникновение переноса П1 из предыдущего (i-1)-го четверичного разряда не приводит к необходимости формирования дополнительного сигнала переноса, так как максимальное значение кода суммы при активном сигнале переноса П1 из текущего разряда равно 0100 и, следовательно, перенос П1 из предыдущего разряда даст код результата 1000 без необходимости формирования дополнительного сигнала переноса.
i
i
i
i
i
i
i
В основу реализации алгоритма умножения положен метод сохранения переносов. При реализации алгоритма умножения переносы частичных произведений Р2, Р1 и переносы суммы частичных произведений П1, возникающие на каждом шаге вычислений, не передаются в соответствующие старшие разряды произведения и суммы, а запоминаются в блоках хранения переносов произведения 4 и переноса суммы 7 текущего i-го четверичного разряда. На следующем такте проводится сдвиг текущей суммы частичных произведений в сторону младших разрядов, который выполняется при передаче значений суммы из (i+1)-го узла регистра 9 результата в i-й узел сумматора 6, и в каждом i-м разряде проводится суммирование сдвинутой текущей суммы частичных произведений и следующего значения частичного произведения из узла 3 и соответствующих сохраненных переносов произведения из узла 4 и переносов суммы из узлов 7.
1
n-i
1
2n
После выполнения n шагов алгоритма на следующем (n+1)-м шаге частичное произведение будет равно нулю, так как на каждом шаге при сдвиге в регистр тетрадного сдвига 1 последовательно вводится константа 0 в коде "1 из 4" с входа 14. Поэтому на (n+1)-м шаге проводится суммирование текущего значения суммы частичных произведений только с сохраненными переносами произведений и сохраненными переносами суммы. Далее разрешается работа блока переносов результата 10, в котором проводится коррекция результата на значения сохраненных переносов в узлах 7…7. При этом выполняется последовательный межразрядный перенос в сторону старших разрядов. На каждом шаге вычислений проводится контроль результата в узлах 11…11 блоках контроля 11.
В начале выполнения операции умножение на вход 12 устройства подается сигнал Запись (фиг.7), по которому проводится запись операндов сомножителя В в регистр тетрадного сдвига 1 и сомножителя А в регистр второго сомножителя 2 и установка в ноль в коде "1 из 4" узлов регистра результата 9, в ноль в коде "1 из 3" узлов блока переносов произведения 4 и в ноль в коде "1 из 2" узлов блока триггеров переноса суммы 7.
i
3i
2i
1i
0i
i
3i
2i
2i
0i
i
i
i
n
1
n-1
1
2
1
1
Каждый из четверичных разрядов а сомножителя А представлен кодом "1 из 4" а а а а и заносится в i-ю тетраду регистра 2, а каждый из четверичных разрядов b сомножителя В представлен кодом "1 из 4" b b b b и заносится в i-ю тетраду регистра тетрадного сдвига 1. Выход младшей тетрады регистра 1 соединен с первой группой входов всех узлов 3 частичных произведений в коде "1 из 4" блока частичных произведений 3, на вторые группы входов которых подаются соответствующие четверичные разряды в коде "1 из 4" из регистра второго сомножителя 2. Так как узлы частичных произведений 3 блока 3 комбинационные, то через время переходного процесса только внутри каждого узла блока 3, на выходе узлов частичных произведений 3 в соответствии с алгоритмом умножения установятся значения поразрядного умножения b×a, b×a, … b×а, b×а и значения сформированных одного переноса Р1 или двух переносов Р2 в следующий четверичный разряд.
i
i
i
i
i
i+1
i
i
i
i
i
1
n
1
n-1
1
2
1
1
i
i
Значения поразрядного умножения с узлов 3 подаются на группы вторых входов соответствующих узлов 5 первого блока сумматоров переносов 5, которые также комбинационные, а на первые группы входов подаются значения нулей в коде "1 из 3" с узлов 4 установленного в ноль блока переносов произведения 4. На выходах узлов 5, через время переходного процесса только внутри каждого узла блока 5, будут установлены значения поразрядного умножения, которые поступают на группы вторых входов соответствующих узлов 6 блока сумматоров 6, а на группы первых входов значения нулей в коде "1 из 4" со следующих старших узлов 9 регистра 9 результата. На выходах узлов 6 блока сумматоров 6, который также комбинационный, через время переходного процесса только внутри каждого узла 6 блока сумматоров 6, будут установлены значения поразрядного умножения, которые поступают на группы вторых входов узлов 8 второго блока сумматоров переносов 8, а на группы первых входов которых значения нулей в коде "1 из 2" с установленного в ноль блока триггеров переноса суммы 7. В результате на выходах четверичных разрядов 8 второго блока сумматоров переносов 8, который также комбинационный, через время переходного процесса только внутри каждого узла 8 второго блока сумматоров переносов 8, будут установлены значения поразрядного умножения b×a, b×a, … b×a, b×a, а также на входах блока переносов произведения 4 и блока триггеров переноса суммы 7 будут установлены соответственно значения одного или двух переносов. Сигналы в узлах 4 блока переносов произведения 4 формируются в соответствие с таблицей 3 в коде "1 из 3". Из таблицы 3 следует, что при любых входных значениях сомножителей и возникновении двух переносов не может возникнуть дополнительного третьего переноса в следующий разряд. Сигналы в узлах 7 блока переносов суммы 7 реализуют логическую функцию ИЛИ от переносов - ПS∨ПС и значение формируется в коде "1 из 2".
По переднему фронту первого синхроимпульса СИ (фиг.7) вычисленные значения будут занесены в соответствующие разряды регистра результата 9, блока переносов произведения 4 и блока триггеров переноса суммы 7. Таким образом, будут зафиксированы значения поразрядного умножения и значения переносов произведения и суммы в следующие разряды. Кроме того, по этому же фронту сигнала СИ осуществляется сдвиг сомножителя В на один четверичный разряд в регистре тетрадного сдвига 1 и вводится константа 0 в коде "1 из 4" в старший разряд регистра 1.
2
2
n
2
n-1
2
2
2
1
i
i
i
i
i
После этого на входы первой группы блока 3 частичных произведений поступает значение следующего четверичного разряда b сомножителя В, на выходах блока 3 образуется значение поразрядного умножения b×a, b×a, … b×a, b×а и значения сформированных одного переноса Р1 или двух переносов Р2 в следующий четверичный разряд. На выходах узлов 5 первого блока сумматоров переносов 5 будут сформированы суммы частичных произведений i-го четверичного разряда в коде "1 из 4" и переносов в коде "1 из 3" i-го разряда, поступающих из узлов 4 блока переносов произведения 4, сохраненных на предыдущем шаге. Далее эта сумма складывается на сумматорах 6 первого блока сумматоров 6 со сдвинутым на один четверичный разряд в сторону младших разрядов кодом четверичного разряда накопленной частичной суммы из регистра 9. Затем эта сумма поразрядно складывается в узлах 8 разрядов второго блока сумматоров переносов 8 с сохраненным переносом суммы i-го разряда на предыдущем шаге из узлов 7 блока триггеров переноса суммы 7. Таким образом, на выходах блока 8 сумматора переносов образуются коды очередной частичной суммы с учетом переносов предыдущего шага, которые поступают на входы узлов регистра 9 результата, а также формируются переносы в следующие разряды на входах блока переносов произведения 4 и блока триггеров переноса суммы 7, которые заносятся в регистр 9 результата и блоки переносов произведения 4 и переносов суммы 7 по переднему фронту второго синхроимпульса СИ. Одновременно младший разряд частичной суммы предыдущего шага вычислений сдвигается на один четверичный разряд в регистре результата 9 в сторону младших разрядов с выхода (n+1)-го разряда в n-й разряд.
В дальнейшем процесс вычислений циклически повторяется.
После подачи n-го импульса СИ в регистре 4 результата образуется поразрядная сумма частичных произведений и поразрядная фиксация переносов произведения в блоке 4 и переносов суммы в блоке 7. Далее проводится соответственно их поразрядное суммирование в узлах первого блока сумматоров переносов 5, блока сумматоров 6 и второго блока сумматоров переносов 8, при этом на первую группу входов блока 3 частичных произведений из регистра 1 тетрадного поступает константа 0 в коде "1 из 4". При подаче (n+1)-го импульса СИ результат суммирования заносится в регистр 9 результата и блок переносов суммы 7, а в блок переносов произведения 4 заносится константа 0 в коде "1 из 4", так как будут отсутствовать переносы из блока 3 произведений и блока 5 сумматоров переносов.
1
n-1
i
2n
n+2
n-1
1
n+1
1
n+1
1
Одновременно (фиг.7) на вход 15 подается сигнал СДВИГ и проводится коррекция переносов суммы с межразрядным переносом в сторону старших разрядов, которая выполняется в узлах 10…10, блока переносов результата 10 в коде "1 из 4". Так как узлы 10 блоков переноса комбинационные, то через время переходного процесса старшие разряды z…z суммы частичных произведений будут сформированы на выходах узлов 10…10 блока переносов результата 10. Длительность сигнала СДВИГА должна быть больше времени переходного процесса в блоке 10 и времени удержания результата произведения на выходах устройства. Младшие разряды z…z полной суммы частичных произведений Z=А×В снимаются с выходов и узлов 9…9 тетрад четверичных разрядов регистра результата 9 в коде "1 из 4".
1
2n
1
n-1
i
i
На каждом шаге вычислений выходы всех 2n разрядов четверичных текущих сумм частичных произведений поступают на входы соответствующих узлов контроля кода "1 из 4" 11…11 блока контроля 11, так как при отсутствии сигнала СДВИГ узлы 10…10 передают на выход значения тетрад регистра результата 9 в коде "1 из 4". В случае появления несоответствия кода хотя бы в одном разряде z коду "1 из 4" на выходах 16 устройства будет выдан сигнал признака ошибки Ош.
i
3i
2i
1i
0i
3i
2i
1i
0i
i
i
Комбинационные узлы 3 частичных произведений в коде "1 из 4" (фиг.2) блока частичных произведений работают следующим образом. Каждая группа элементов И 17-20 содержит 4 элемента И, образуя матрицу 4×4. На первые входы элементов И с первой по четвертую групп подаются бинарные составляющие четверичного разряда сомножителя b b b b на вторые входы элементов И с первого по четвертый каждой группы подаются бинарные составляющие четверичного разряда сомножителя а а а a. На шестнадцати выходах матрицы элементов И может, очевидно, возникнуть только одна "1", остальные нули (любая другая комбинация, пройдя через логические элементы комбинационных узлов блока частичных произведений 3, первого блока сумматоров переносов 5, блок сумматоров 6, второго блока сумматоров переносов 8 и записи в регистр результата 9 в коде "1 из 4" приведет к возникновению сигнала признака ошибки на одном из выходов блока контроля 11). Выходы элементов И групп 17-20 подключены ко входам четырех группы элементов ИЛИ 21 таким образом, что на их выходах реализуется необходимый результат частичного произведения в соответствии с табл.2. При этом на выходе элемента ИЛИ 22 формируется сигнал признака одного переноса Р1 и с выхода первого элемента И четвертой группы элементов И 20 снимается сигнал признака второго переноса Р2 в следующий четверичный разряд.
i
i
i
i
i
i
i
i
i
i
Комбинационные узлы 5 первого блока сумматоров переносов 5 проводят суммирование частичного произведения текущего i-го четверичного разряда и сигналов двух Р2 и одного Р1 переносов из предыдущего (i-1)-го разряда частичных переносов, сохраненные в узлах 4 блока переносов произведения 4. При этом на выходах переноса ПМ1 узлов 5 может быть сформирован активный сигнал. Сигналы двух переносов Р2 и одного переноса Р1 из узла 3 частичных произведений в коде "1 из 4" и одного переноса из узла 5 первого блока сумматоров переносов текущего i-го разряда поступают на входы узла 4 блока переносов произведения 4. В соответствии с таблицей 3 в узлах 4 формируется значение переноса в коде "1 из 3" в следующий разряд, которое записывается в триггеры 35-37. В таблице 3 отмечено, что при любых входных значениях сомножителей и возникновении двух переносов не может возникнуть дополнительного третьего переноса в следующий разряд.
i
0i
1i
2i
3i
0i
1i
2i
3i
i
i
i
i
Комбинационные сумматоры в коде "1 из 4" 6 блока сумматоров 6 (фиг.3) реализуют преобразование по таблице 2. Каждая группа элементов И 23-26 содержит 4 элемента И, образуя матрицу 4×4. На первые входы элементов И с первой по четвертую группы И 23-26 подаются бинарные составляющие четверичного разряда слагаемого а, а, а, а, на вторые входы элементов И с первого по четвертый каждой группы И 23-26 подаются бинарные составляющие четверичного разряда второго слагаемого b, b, b, b. На шестнадцати выходах матрицы элементов И может, очевидно, возникнуть только одна "1", остальные нули (любая другая комбинация, пройдя через логические элементы сумматора 6, второго блока сумматоров переносов 8 и записи в регистр результата 9 в коде "1 из 4" приведет к возникновению сигнала признака ошибки на одном из выходов блока контроля). На первые группы входов сумматоров 6 в коде "1 из 4" подаются бинарные составляющие четверичного разряда i-й тетрады частичного произведения с узлов 5, а на вторые группы входов подаются бинарные составляющие четверичного разряда старшей (i+1)-й тетрады суммы с регистра 9 результата. Выходы элементов И групп 23-26 подключены ко входам четырех элементов ИЛИ группы 27 таким образом, что на их выходах реализуется необходимый поразрядный результат суммы частичного произведения в соответствии с таблицей 2. При этом на выходе элемента ИЛИ 28 формируется сигнал признака переноса ПS в следующий четверичный разряд.
i
i
i
i
i
i
i
i
i
i
i
i
i
Комбинационные узлы 8 второго блока сумматоров переносов 8 проводят суммирование текущей суммы частичного произведения i-го четверичного разряда и сигнала переноса ТП из предыдущего (i-1)-го разряда, сохраненные в узлах 7 блока переносов суммы 7. При этом на выходах переноса ПС узлов 8 может быть сформирован активный сигнал. Сигнал переноса ПС из узла 8 и переноса ПS из узла 6 блока сумматоров текущего i-го разряда поступают на входы узла 7 блока переносов суммы 7. В узлах 7 формируется значение переноса в коде "1 из 2", как логическая сумма ПС∨ПS, в следующий разряд, которое записывается в триггеры 42. При этом при любых входных значениях слагаемых и формировании переносов не может возникнуть дополнительно двух переносов в следующий разряд.
1
n-1
1
n+1
i
i
В результате работы устройства 2n-разрядный результат умножения Z=A×B формируется на выходах узлов 10…10 блока переносов результата 10 и узлов 9…9 тетрад четверичных разрядов регистра 9 результата в коде "1 из 4" после (n+1)-го шага сигналов СИ и при наличии сигнала СДВИГ на входе 15. На каждом шаге вычислений проводится поразрядный контроль выполнения операции и в случае появления несоответствия кода хотя бы в одном разряде z коду "1 из 4" на выходах 16 устройства будет выдан сигнал признака ошибки Ош.
Оценим быстродействие предлагаемого устройства.
i
i
i
i
В предлагаемом устройстве период синхроимпульсов СИ определяется только суммой задержек прохождения сигналами четырех последовательных блоков 3, 5, 6, 8 и времени формирования переноса в блоке 7, и не зависит от разрядности n сомножителей. Разрядность n задает количество шагов вычислений, а также учитывается только на (n+1)-м шаге при коррекции переносов в узлах блока 10.
В прототипе на каждом шаге вычислений выполняется последовательный межразрядный перенос через (n-1) узел в блоке частичных произведений или в блоке сумматоров. Поэтому период синхроимпульсов СИ в прототипе на каждом шаге прямо пропорционален количеству разрядов n и будет приблизительно равен общему времени выполнения операции умножения для предлагаемого устройства.
Таким образом, предлагаемое устройство обладает более высоким быстродействием, в сравнении с прототипом.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство для умножения чисел в коде "1 из 4" обладает регулярностью узлов и связей, обеспечивает повышенную достоверность результата умножения за счет поразрядного контроля выполнения операции, равномерное распределение энергии по разрядам в процессе работы и соответствует заявляемому техническому результату - увеличение быстродействия устройства.
Таблица 1
Четверичный код
0
1
2
3
Сомножители "1 из 4"
0001
0010
0100
1000
0
0001
=0001
=0001
=0001
=0001
1
0010
=0001
=0010
=0100
=1000
2
0100
=0001
=0100
=0001+Р1
=0100+Р1
3
1000
=0001
=1000
=0100+Р1
=0010+Р2
Таблица 2
Четверичный код
0
1
2
3
Слагаемые "1 из 4"
0001
0010
0100
1000
0
0001
=0001
=0010
=0100
=1000
1
0010
=0010
=0100
=1000
=0001+П1
2
0100
=0100
=1000
=0001+П1
=0010+П1
3
1000
=1000
=0001+П1
=0010+П1
=0100+П1
Таблица 3
Входы
Выходы
Р2
Р1
ПМ1
ТР2
ТР1
ТР0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
0
0
1
0
1
X
X
X
1
1
0
X
X
X
1
1
1
X
X
X