Устройство параллельного действия для
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВЙДЕТЕДЬСТВУ
Союз Советских
Социалистических.Республик
Зависимое от авт, свидетельства ¹
Заявлено 06. Ill.1968 (№ 1226070/18-24) с присоединением заявки Л
Приоритет
Опубликовано 04.VII.1969. Бюллетень № 22
Дата опубликования описания 2.XII.1969
Кл, 42m>, 7/38
МПК G 06f
УДК 681 325 5 (088.8) Комитет по делам изобретений и открытий при Совете Министров
СССР
Автор изобретения
В. Г. Захаров
Заявитель
УСТРОЙСТВО ПАРАЛЛЕЛЪНОГО ДЕЙСТВИЯ ДЛЯ
НАХОЖДЕНИЯ ОСТАТОЧНОГО ПОЛИНОМА ДВОИЧНОГО
ЧИСЛА ПО ПОРОЖДАЮЩЕМУ ПОЛИНОМУ
Предложение относится к цифровой вычислительной технике, может быть применено в схемах контроля ЦВМ и в линиях связи с параллельной передачей двоичной информации.
Известны устройства параллельного действия для нахождения остаточного полинома двоичного числа по порождающему полиному, в основу которых положена алгебра кодирования, имеющая в литературе название «циклическое кодирование».
Одним из таких устройств является устройство для нахождения остаточного полинома двоичного числа по порождающему полиному д(Х) =Хт4+Хз+Х1+Хо (код Файра). Это устройство последовательного действия построено на узлах двух типов, одним из которых является сдвиговый регистр, другим — исключающее «ИЛИ» или сумматор по mod 2. Его недостаток заключается в том, что оно практически не применимо в схемах контроля параллельных ЦВМ из-за относительно низкого быстродействия.
Предложенное устройство отличается тем, что оно выполнено на двоичных полусумматорах, расположенных по ступеням с этажами, составленными из групп полусумматоров. На каждом этаже первой ступени число полу"умматоров в группе равно числу разрядов двоичного числа, разрядные остаточные поJlHHoMbI которых по порождающему полиному составляют период. Входы и выходы полусумматоров соответствуют весам разрядных остаточных полиномов двоичного числа по порождающему полиному. Входы полусумматоров первого этажа первой ступени соединены с шинами, соответствующими разрядам исходного двоичного числа, все входы полусумматоров последующих этажей первой сту10 пени соединены с шинами, соответствующими разрядам исходного числа, и шинами, соответствующими суммам предшествующих этажей, не соединенных со входами полусумматоров других предшествующих этажей. На
15 каждом этаже второй ступени содержатся группы из полусумматоров, число которых равно порядку порождающего полинома. Входы и выходы этих полусумматоров соответствуют весам разрядных остаточных полино20 мов вида 2 по порождающему полиному (р=О, 1,2,....., к — 1). Входы полусумматоров первого этажа второй ступени в соответствии с разложением многочисленных разрядных остаточных полиномов на одночленные
25 разрядные остаточные полиномы вида 2л по порождающему полиному соединены с выходами полусумматоров последнего этажа первой ступени или с шинами разрядов исходного числа. Входы полусумм аторов последующих этажей второй ступени соединены с ши4
10 нами> соответствующими суммам полусумматоров предшествующих этажей первой, второй ступени или с шинами разрядов исходного числа, не соединенных со входами полусумматоров предшествующих этажей второй ступени B соответствии с каждым данным одночленным разрядным остаточным полиномом по порождающему полиному. Это позволяет упростить устройство и повысить его быстродействие.
Схема предложенного устройства изображена на чертеже.
Первая 1 и вторая 2 ступени состоят каждая из одного или нескольких этажей полусумматоров 3, первый 4 и второй 5 этажи первой ступени — из одной или нескольких групп по и полусумматоров, последний ее этаж 6— из одной группы, первый этаж 7 и второй этаж 8 второй ступени — из одной или нескольких групп по к полусумматоров, последний этаж 9 — из одной группы.
Устройство работает следующим образом.
Значения всех или части разрядов исходного двоичного числа в соответствии с весами разрядных остаточных полиномов по порождающему полиному поступают на входы первого этажа полусумматоров первой ступени или, при отсутствии первой ступени, на входы первого этажа полусумматоров второй ступени, но тогда с учетом разложения многочленных разрядных остаточных полиномов на одночленные вида 2Р по порождающему полиному.
Значения сумм полусумматоров первых этажей первой и второй ступеней, являющиеся результатами операций поразрядного сложения (сложения по mod 2) величин разрядов исходного двоичного числа, а также значения следующей части разрядов исходного двоичного числа поступают на входы полусумматоров следующего этажа полусумматоров первой и второй ступеней.
В свою очередь значения вновь образованных сумм и значения следующей части разрядов исходного двоичного числа поступают на входы полусумматоров следующих этажей и т. д., пока в результате поэтажных поразрядных сло?кений значений сумм и разрядов исходного двоичного числа на выходах сумм последнего этажа второй ступени устройства не появится значение остаточного полинома от данного исходного двоичного числа по порождающему полиному.
Предло>кенное устройство можно использовать в схемах контроля, параллельных ЦВМ с применением кодов Боуза-Чоуд-хури-Хокингэма, кодов Файра и других циклических кодов.
Количество оборудования, необходимое для построения предлагаемого устройства, одного порядка с количеством оборудования, необходимого для построения схем свертки Ilo четности параллельного действия.
Задачи обнаружения ошибок при параллельной передаче двоичной информации при равной мощности остаточных полиномов по порождающему полиному в алгебре циклических кодов и в алгебре классов вычетов по модулю эффективнее решается с помощью циклических кодов, к тому же применение предложенного устройства для этих целей позволяет уменьшить количество оборудования.
Предмет изобретения
Устройство параллельного действия для нахождения остаточного полинома двоичного числа по порождающему полиному, отличающееся тем, что, с целью повышения быстродействия и упрощения, оно выполнено на двоичных полусумматорах, расположенных по ступеням с этажами, составленными из групп полусумматоров, причем на каждом этаже первой ступени число полусумматоров в группе равно числу разрядов двоичного числа, разрядные остаточные полиномы которых по порождающему полиному составляют период; входы и выходы полусумматоров соответствуют весам разрядных остаточных полиномов двоичного числа по порождающему полиному; входы полусумматоров первого этажа первой ступени соединены с шинами, соответствующими разрядам исходного двоичного числа, все входы полусумматоров последующих этажей первой ступени.соединены с шинами, соответствующими разрядам исходного числа, и шинами, соответствующими суммам предшествующих этажей, не соединенных со входами полусумматоров других предшествующих этажей; на каждом этаже второй ступени содержатся группы из полусумматоров, число которых равно порядку порождающего полинома; входы и выходы этих полусумматоров соответствуют весам разрядных остаточных полиномов вида 2Р по порождающему полиному (р = О, 1, 2,....., к — 1); входы полусумматоров первого этажа второй ступени в соответствии с разложением многочленных разрядных остаточных полиномов на одночленные разрядные остаточные полиномы вида 2Р по порождающему полиному соединены с выходами полусумматоров последнего этажа первой ступени или с шинами разрядов исходного числа; входы полусумматоров последующих этажей второй ступени соединены с шинами, соответствующими суммам полусумматоров предшествующих этажей первой, второй ступени или с шинами разрядов исходного числа, не соединенных со входами полусумматоров предшествующих этажей второй ступени в соответствии с каждым данным одночленным разрядным остаточным полиномом IIQ порождающему полиному.
247624
I
1-. 1
Составитель И. H. Горелова
Редактор Т. Зенбицкая
Техрсд Т. П. Курилко Корректор С. М. Сигал
Заказ 3083,11 Тираж 480 Подписное
ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР
Москва, il(-35, Раун1ская наб., д. 4г5
Типография, пр. Сапунова, 2
1 г7
l !!
I I»
I ! ! ! !
I
l !
l
I
l !
I
1
I ! !
1
1
