СПОСОБ СЛОЖЕНИЯ ЧИСЕЛ В КОДЕ "1 ИЗ 4" И СУММАТОР В ЭТОМ КОДЕ Российский патент 2005 года по МПК G06F7/49 

Изобретение относится к вычислительной технике и может быть использовано для построения вычислительных систем с повышенной достоверностью выдаваемых данных.

Известен сумматор кодов “1 из N” (патент РФ №2129730, МКИ 7 G 06 F 7/50, заявлено 29.10.97, опубл. 27.04.99), содержащий N групп элементов И, две группы элементов ИЛИ, N элементов И в первой группе элементов И, N элементов ИЛИ в первой группе элементов ИЛИ, причем j-я группа элементов И (j=2, 3, ..., N) содержит N+1-j элементов И, вторая группа элементов ИЛИ содержит 2N-5 элементов ИЛИ. Способ суммирования в коде “1 из N”, реализованный в известном устройстве, заключается в формировании сигналов кода суммы логическим сложением частичных сумм, которые образуются поразрядным логическим умножением входных сигналов кодов и попарным логическим умножением сигналов поразрядного логического сложения входных сигналов кодов, при этом поразрядным операциям подвергаются одинаковые разряды.

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

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

Известен сумматор в коде “М из N” (АС СССР №1053103, МКИ 6 G 06 F 7/49, заявлено 25.06.82, опубл. 07.11.83), содержащий регистр результата, матрицу коррекции переносов, дополнительную матрицу коррекции переносов, блок коммутации, первый и второй регистры операндов, матрицу сложения, блок управления, выходную шину суммы, входную шину установки, шины первого и второго операндов, выходную шину переноса, сигнальную выходную шину, первую и вторую управляющие шины соответственно состояния и установки, выход управления результатом операции и выход управления инверсией. Способ сложения чисел в коде “М из N” заключается в том, что вводят сигналы установки в исходное состояние и управляющие сигналы, сигналы данных в коде “М из N” первого и второго операндов запоминают, вводят в матрицу сложения, выводят сигналы результата сложения в матрицу коррекции переноса и дополнительную матрицу коррекции переноса, корректируют результат операции с учетом переносов, проверяют сигналы данных результата на соответствие коду “М из N” и при соответствии сигналов данных результата сложения коду “М из N” выдают результат.

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

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

Известен сумматор в коде “М из N”, наиболее близкий к заявляемому (АС СССР №1051533, МКИ 6 G 06 F 7/49, заявлено 02.07.82, опубл. 30.10.83), содержащий регистр результата, шифратор, блок переноса, первый и второй регистры операндов, матрицу сложения, блок управления, выходную шину суммы, входную шину установки, шины первого и второго операндов, выходную шину переноса, сигнальную выходную шину, управляющий вход состояния, выход управления инверсией. Способ сложения чисел в коде “М из N” заключается в том, что вводят сигналы установки в исходное состояние и управляющие сигналы, сигналы данных в коде “М из N” первого и второго операндов запоминают, вводят в матрицу сложения, выводят сигналы результата сложения из блок, корректируют результат операции с учетом переносов, проверяют сигналы данных результата на соответствие коду “М из N” и при соответствии сигналов данных результата сложения коду “М из N” выдают результат, в противном случае выдают сигнал ошибки.

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

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

Задачей, на решение которой направлено предлагаемое техническое решение, является построение вычислительных систем с повышенной достоверностью получения результатов и равномерного распределения энергии в процессе работы при уменьшении аппаратурных затрат, что особенно важно при реализации аппаратуры системы в виде СБИС.

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

Заявляемый технический результат достигается тем, что в способе сложения чисел в коде “1 из 4”, заключающемся во введении сигналов установки и управляющих сигналов, сигналов данных операндов первого и второго слагаемых в коде “1 из 4”, проверке сигналов данных результата сложения на соответствие коду “1 из 4” и при несоответствии сигналов данных результата сложения коду “1 из 4” выдаче сигнала ошибки, при этом сигналы, каждого соответствующего четверичного разряда операндов первого и второго слагаемых в коде “1 из 4” и сигнал переполнения из предыдущего четверичного разряда вводят в блок кольцевого сдвига, в каждом четверичном разряде первого слагаемого осуществляют сдвиг на количество разрядов, соответствующих коду соответствующего четверичного разряда второго слагаемого, при активном сигнале переноса из предыдущего четверичного разряда проводят еще один сдвиг в соответствующем четверичном разряде операнда первого слагаемого, в случае переноса единицы из старшего разряда в младший в каждом четверичном разряде, кроме старшего четверичного разряда, выдают сигнал переноса в следующий четверичный разряд, при возникновении сигнала переноса из старшего четверичного разряда выдают сигнал переполнения.

Технический результат достигается также тем, что в сумматор в коде “1 из 4”, содержащем входы операндов первого и второго слагаемых в коде “1 из 4”, вход установки, первый и второй управляющие входы и выходы сигналов ошибки, введены n блоков кольцевого сдвига, где n - количество четверичных разрядов в операндах слагаемых, и n узлов контроля кода “1 из 4”, причем первый информационный вход i-го блока кольцевого сдвига, i=1, 2, ... n, соединен со входом i-го четверичного разряда в коде “1 из 4” операнда первого слагаемого сумматора, второй информационный вход 1-го блока кольцевого сдвига соединен со входом i-го четверичного разряда в коде “1 из 4” операнда второго слагаемого сумматора, выход переноса i-го блока кольцевого сдвига, кроме n-го, соединен со входом переноса (i+1)-го блока кольцевого сдвига, выход суммы i-го блока кольцевого сдвига в коде “1 из 4” соединен с i-м выходом сумматора и входом i-го узла контроля кода “1 из 4”, выход которого соединен с выходом признака ошибки i-го разряда сумматора, вход записи i-го блока кольцевого сдвига в коде “1 из 4” соединен со входом установки сумматора, первый и второй управляющие входы которого соединены соответственно со входами синхроимпульса сдвига и синхроимпульса переноса каждого блока кольцевого сдвига в коде “1 из 4”, выход переноса n-го блока кольцевого сдвига соединен с выходом переполнения сумматора.

Технический результат достигается также тем, что блок кольцевого сдвига содержит первый и второй регистры сдвига, узел группового переноса, два элемента И, элемент НЕ и элемент ИЛИ, причем в первом регистре сдвига код сдвигается в сторону старших разрядов, во втором регистре сдвига код сдвигается в сторону младших разрядов, первый и второй информационные входы блока кольцевого сдвига соединены с информационными входами соответственно первого и второго регистров сдвига, входы загрузки которых соединены со входом записи блока и входом установки узла группового переноса, вход признака переноса которого соединен с последовательным выходом старшего разряда и последовательным входом первого регистра сдвига, выходы разрядов которого соединены с выходом суммы блока, выход переноса которого соединен с выходом узла группового переноса, вход переноса предыдущего разряда которого соединен со входом переноса блока и первым входом первого элемента И, второй вход которого соединен со входом синхроимпульса переноса блока, вход синхроимпульса сдвига которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом элемента НЕ, вход которого соединен с последовательным выходом младшего разряда второго регистра сдвига, вход сдвига которого соединен с выходом второго элемента И и первым входом элемента ИЛИ, второй вход и выход которого соединены соответственно с выходом первого элемента И и входом сдвига первого регистра сдвига.

Возможность проведения контроля данных основана на том, что четверичный код “1 из 4” имеет в составе всегда только одну единицу (все возможные комбинации этого кода 0001=0; 0010=1; 0100=2 и 1000=3) и, таким образом, из общего числа возможных ошибочных комбинаций для 4-разрядного слова, равного 15, количество неопознанных ошибок составит только 3. Таким образом, заявляемый способ обеспечивает распознавание 80% ошибок.

Из возможных вариантов кодов “М из N” код “1 из 4” обладает наибольшей эффективностью. Во-первых, операция преобразования двоичного кода в код “М из N” и обратно, характерная для цифровых систем обработки, содержащих ряд подсистем, при М≠1 и N≠2^m, где m=1, 2, ..., требует анализа всей последовательности цифр двоичного кода, что приводит к очень большим затратам оборудования при реализации. Например, при построении такого преобразователя кода для 32-разрядного двоичного кода с использованием блока памяти потребуется от 5 до нескольких десятков мегабайт памяти. Схемотехническая реализация таких преобразователей потребует оборудования, объем которого значительно превысит объем оборудования операционных устройств.

С другой стороны, для преобразования кода “1 из 2^m” потребуется D/m (D - разрядность двоичного кода) дешифраторов для преобразования двоичного кода и столько же шифраторов для обратного преобразования. Это связано с тем, что преобразование осуществляется поразрядно. Например, для 32-разрядного двоичного кода преобразователь кода в “1 из 2”, “1 из 4”, “1 из 8” и т.д. потребует соответственно 32 одновходовых, 16 двухвходовых, 11 трехвходовых и т.д. дешифраторов и столько же шифраторов для обратного преобразования. Такое схемотехническое решение требует минимального количества оборудования и эффективно реализуется при построении систем на кристаллах СБИС или ПЛИС.

Во-вторых, реализация схемотехнических решений для кодов “1 из 2”, “1 из 4”, “1 из 8” и т.д. также обладает различной эффективностью. Это связано, с одной стороны, с различным количеством распознаваемых ошибок и, с другой стороны, с различным превышением объема требуемого оборудования для обработки по сравнению с двоичным кодом. Поэтому для оценки эффективности использования того или иного кода “1 из 2^m”, целесообразно рассмотреть величину отношения процента обнаруживаемых ошибок к величине превышения требуемого оборудования по отношению к двоичному коду.

В общем случае количество комбинаций для кода “М из N” равно величине , тогда количество необнаруживаемых ошибок составит (одна верная комбинация). Количество всех возможных ошибочных кодов, очевидно, равно 2^N-1. Тогда доля обнаруживаемых ошибок Q определяется соотношением . Для кодов “1 из 2^m” величина , тогда .

Величина превышения требуемого оборудования К для кодов “1 из 2^m”, очевидно равна .

Тогда эффективность использования кода “1 из 2^m”

В табл.1 приведены расчетные данные для кодов “1 из 2^m” при различных значениях m.

Таблица 1Разрядность двоичного кода mСоответствующий код “1 из N”Доля обнаруж. ошибок QКоэффициент по оборудованию КЭффективность Е1“1 из 2”0,672,000,332“1 из 4”0,802,000,403“1 из 8”0,972,670,364“1 из 16”0,99984,000,255“1 из 32”≅16,400,166“1 из 64”≅110,670,09

Из данных, приведенных в табл.1 видно, что наибольшей эффективностью обладает код “1 из 4”.

Кроме того, распределение энергии при вводе, хранении и выводе данных в коде “1 из 4” всегда одинаково по всем разрядам кода данных, т.к. структурно каждый четверичный разряд содержит строго один высокий и три низких потенциала. Это свойство особенно важно при создании устройств и систем на кристаллах СБИС.

На фиг.1 представлена функциональная схема сумматора, обеспечивающего реализацию способа сложения чисел в коде “1 из 4”; на фиг.2 представлена функциональная схема блока кольцевого сдвига; на фиг.3 показан вариант реализации узла группового переноса; на фиг.4 приведены временные диаграммы управляющих сигналов.

Сумматор в коде “1 из 4” (фиг.1) содержит первый 1, второй 2, и т.д., n-й 3 блоки кольцевого сдвига, первый 4, второй 5 и т.д., n-й 6 узлы контроля кода “1 из 4”.

Каждый блок кольцевого сдвига (фиг.2) содержит первый 7 и второй 8 регистры сдвига, первый 9 и второй 10 элементы И, элемент НЕ 11, элемент ИЛИ 12 и узел группового переноса 13.

Возможный вариант реализации узла группового переноса (фиг.3) содержит триггер 14 и элемент И 15.

Сумматор, реализующий способ сложения чисел в коде “1 из 4” работает следующим образом. В табл.2 даны коды преобразования входных значений в выходные при суммировании разрядов слагаемых в коде “1 из 4” и условия возникновения переноса.

Таблица 2Четверичный код 0123 Слагаемые “1 из 4”000100100100100000001=0001=0010=0100=100010010-0010=0100=1000=0001+П20100=0100=1000=0001+П=0010+П31000=1000=0001+П=0010+П=0100+П

Алгоритм суммирования основан на свойстве кода “1 из 4”, которое хорошо видно из табл.2 - код суммы есть код первого слагаемого, сдвинутый по кольцу на количество разрядов, равное значению кода второго слагаемого. Очевидно, возникновение переноса из предыдущего разряда не приводит к необходимости формирования дополнительного сигнала переноса, т.к. максимальное значение кода суммы при активном сигнале переноса из текущего разряда 0100 и, следовательно, перенос из предыдущего разряда даст результат 1000 без переноса.

После подачи сигнала по входу установки сумматора (фиг.4 - сигнал Запись для блоков 1, 2, 3 кольцевого сдвига) осуществляется поразрядная загрузка кодов операндов первого Х_3iХ_2iХ_1iХ_0i; и второго Y_3iY_2iY_1iY_0i, i=1, 2, ..., n, слагаемых в регистры сдвига 7 и 8. Одновременно осуществляется установка в ноль триггера 14 (фиг.3) в узлах группового переноса 13 каждого блока кольцевого сдвига 1-3. После этого начинают поступать синхроимпульсы сдвига СИС (фиг.4), обеспечивая сдвиг в сторону старших разрядов в первом регистре сдвига 7 и в сторону старших разрядов во втором регистре сдвига 8. Сдвиг происходит до момента появления единицы в младшем разряде регистра сдвига 8, которая блокирует прохождение импульсов СИС через элемент И 10 с помощью элемента НЕ 11. Если в регистре сдвига 8 записан ноль (0001), очевидно, в регистре сдвига 7 не будет произведено ни одного сдвига и код частичной суммы будет равен значению разряда в этом регистре. Максимально возможное количество сдвигов - 3 (для кода 1000 в регистре сдвига 8).

Возникновение сигнала переноса связано с возникновением кольцевого сдвига в регистре сдвига 7 при переходе единицы из старшего в младший разряд. При этом по заднему фронту сигнала с последовательного выхода регистра сдвига 7 происходит переключение триггера 14 в узле группового переноса 13, на выход узла 13 и соответствующего блока кольцевого сдвига выдается сигнал переноса в следующий разряд Р_i.

Последним на вход блоков кольцевого сдвига 1-3 поступает синхроимпульс переноса СИП, который обеспечивает дополнительный сдвиг кода в регистрах сдвига 7 при наличие переноса из предыдущего блока кольцевого сдвига. При активном сигнале переноса P_i-1 импульс СИП пройдет через элемент И 9 и элемент ИЛИ 12 и обеспечит дополнительный сдвиг кода в регистре сдвига 7.

Для осуществления функции группового переноса выход старшего разряда регистра сдвига 7 и сигнал переноса предыдущего разряда P_i-1 поступают на вход элемента И 15. Если оба сигнала активны (логическая единица), то еще до появления импульса СИП, обеспечивающего дополнительный сдвиг в регистре сдвига 7, на выходе триггера 14 узла группового переноса 13 будет установлена единица, которая автоматически заблокирует элемент И 15 и разблокирует установочный вход триггера 14. Это обеспечивает формирование сигнала переноса в следующий разряд по всей цепи переносов еще до появления синхроимпульса переноса СИП.

Результат сложения поразрядно S_3iS_2iS_1iS_0i с выходов регистров сдвига 7 блоков кольцевого сдвига 1-3 подается на входы соответствующих узлов контроля кода “1 из 4” 4-6, в которых осуществляется проверка соответствия коду “1 из 4”. Если все коды S_3iS_2iS_1iS_0i соответствуют коду “1 из 4”, сигналы ошибки Ош_i не выдаются, с выхода сумматора может быть считан код результата сложения, в противном случае возникает активный сигнал Ош_i;, который сигнализирует о возникновении ошибки в результате операции.

Конструкция узлов контроля кода “1 из 4” известна (см. “Устройство для контроля кода “1 из n” патенты SU 1195451, МКИ 6 Н 03 М 7/22; SU 1683178, МКИ 6 Н 03 М 7/22).

Таким образом, предложенный способ обеспечивает значительное снижение объема оборудования при повышенной достоверности обработки за счет поразрядного контроля выполнения операции. При этом обеспечивается обнаружение 80% ошибок.

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

1. Способ сложения чисел в коде “1 из 4”, заключающийся во введении сигналов установки и управляющих сигналов, сигналов данных операндов первого и второго слагаемых в коде “1 из 4”, проверке сигналов данных результата сложения на соответствие коду “1 из 4” и при несоответствии сигналов данных результата сложения коду “1 из 4” выдаче сигнала ошибки, отличающийся тем, что сигналы каждого соответствующего четверичного разряда операндов первого и второго слагаемых в коде “1 из 4” и сигнал переполнения из предыдущего четверичного разряда вводят в блок кольцевого сдвига, в каждом четверичном разряде первого слагаемого осуществляют сдвиг на количество разрядов, соответствующих коду соответствующего четверичного разряда второго слагаемого, при активном сигнале переноса из предыдущего четверичного разряда проводят еще один сдвиг в соответствующем четверичном разряде операнда первого слагаемого, в случае переноса единицы из старшего разряда в младший в каждом четверичном разряде, кроме старшего четверичного разряда, выдают сигнал переноса в следующий четверичный разряд, при возникновении сигнала переноса из старшего четверичного разряда выдают сигнал переполнения.2. Сумматор в коде “1 из 4”, содержащий входы операндов первого и второго слагаемых в коде “1 из 4”, вход установки, первый и второй управляющие входы и выходы сигналов ошибки, отличающийся тем, что в него введены n блоков кольцевого сдвига, где n - количество четверичных разрядов в операндах слагаемых, и n узлов контроля кода “1 из 4”, причем первый информационный вход i-го блока кольцевого сдвига, i=1, 2, ...n, соединен со входом i-го четверичного разряда в коде “1 из 4” операнда первого слагаемого сумматора, второй информационный вход i-го блока кольцевого сдвига соединен со входом i-го четверичного разряда в коде “1 из 4” операнда второго слагаемого сумматора, выход переноса i-го блока кольцевого сдвига, кроме n-го, соединен со входом переноса (i+1)-го блока кольцевого сдвига, выход суммы i-го блока кольцевого сдвига в коде “1 из 4” соединен с i-м выходом сумматора и входом i-го узла контроля кода “1 из 4”, выход которого соединен с выходом признака ошибки i-го разряда сумматора, вход записи i-го блока кольцевого сдвига в коде “1 из 4” соединен со входом установки сумматора, первый и второй управляющие входы которого соединены соответственно со входами синхроимпульса сдвига и синхроимпульса переноса каждого блока кольцевого сдвига в коде “1 из 4”, выход переноса n-го блока кольцевого сдвига соединен с выходом переполнения сумматора.3. Сумматор по п.2, отличающийся тем, что блок кольцевого сдвига содержит первый и второй регистры сдвига, узел группового переноса, два элемента И, элемент НЕ и элемент ИЛИ, причем в первом регистре сдвига код сдвигается в сторону старших разрядов, во втором регистре сдвига код сдвигается в сторону младших разрядов, первый и второй информационные входы блока кольцевого сдвига соединены с информационными входами соответственно первого и второго регистров сдвига, входы загрузки которых соединены со входом записи блока и входом установки узла группового переноса, вход признака переноса которого соединен с последовательным выходом старшего разряда и последовательным входом первого регистра сдвига, выходы разрядов которого соединены с выходом суммы блока, выход переноса которого соединен с выходом узла группового переноса, вход переноса предыдущего разряда которого соединен со входом переноса блока и первым входом первого элемента И, второй вход которого соединен со входом синхроимпульса переноса блока, вход синхроимпульса сдвига которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом элемента НЕ, вход которого соединен с последовательным выходом младшего разряда второго регистра сдвига, вход сдвига которого соединен с выходом второго элемента И и первым входом элемента ИЛИ, второй вход и выход которого соединены соответственно с выходом первого элемента И и входом сдвига первого регистра сдвига.