УСТРОЙСТВО ПАРАЛЛЕЛЬНОГО ДЕЙСТВИЯ ДЛЯ Советский патент 1969 года по МПК G06F7/38 G06F11/08 

Предложение относится к цифровой вычислительной технике, может быть применено в схемах контроля ЦВМ и в линиях связи с параллельной передачей двоичной информации.

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

Одним из таких устройств является устройство для нахождения остаточного полинома двоичного числа по порождающему полиному d(X)Xii- -X + (код Файра). Это устройство последовательного действия построено на узлах двух типов, одним из которых является сдвиговый регистр, другим - исключающее «ИЛИ или сумматор по mod 2. Его недостаток заключается в том, чтооно практически не применимо в схемах контроля параллельных ЦВМ из-за относительно низкого быстродействия.

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

каждом этаже второй ступени содержатся группы из полусумматоров, число которых равно порядку порождающего полинома. Входы и выходы этих полусумматоров соответствуют весам разрядных остаточных полиномов вида 2Р по порождающему полиному (1 0, 1,2к-1). Входы полусумматоров первого этажа второй ступени в соответствии с разложением многочисленных разрядных остаточных полиномов на одночленные

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

Схема предложенного устройства изобрал ена на чертеже. .

Первая / и вторая 2 стуиени состоят каждая из одного или .нескольких этажей полусумматоров 3, первый 4 и второй 5 эталси первой ступени - из одной или нескольких групп по п полусумматоров, последний ее этаж 6- из одной группы, первый этаж 7 и второй этаж 8 второй ступени - из одной или нескольких групп ио к полусумматоров, последний 9 - из одной группы.

Устройство работает следующим образом .

Значения всех или части разрядов исходного двоичного числа в соответствии с весами разрядных остаточных полиномов по порождающему полиному поступают на входы первого этажа полусумматоров первой ступени или, при отсутствии Г1ервой ступени, на входы первого этажа полусумматоров второй ступени, но тогда с учетом разложения многочленных разрядных остаточных полиномовна одночленные вида 2 по иороладающему иолиному.

Значения сумм полусумматоров первых этажей первой и второй стуиеней, являющиеся результатами операций поразрядного сложения (сложения по mod 2) величин разрядов исходного двоичного числа, а также значения следующей части разрядов исходного двоичного числа поступают на входы полусумматоров следующего этажа полусумматоров первой и второй ступеней.

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

Предлолсенное устройство использовать в схемах контроля, параллельных ЦВМ с применением кодов Боуза-Чоуд-хури-Хокингэма, кодов Файра и других циклических кодов.

Количество оборудования, необходимое для построения предлагаемого устройства, одного порядка с количеством оборудования, необходимого для построения схем свертки по четности параллельного действия.

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

Предмет изобретения

Устройство параллельного действия для нахождения остаточного иолинома двоичного числа ио иороледающему иолиному, отличающееся тем, что, с целью повыщения быстродействия и упрощения, оно выполнено на

двоичиых полусумматорах, расположенных по ступеням с этажами, составленными из групп полусумматоров, причем на этаже первой стуиени число полусумматоров в группе равно числу разрядов двоичного числа,

разрядиые остаточные полиномы которых по порол дающему полиному составляют период; входы и выходы иолусумматоров соответствуют весам разрядных остаточных полиномов двоичного числа по пороладающему полиному;

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

этаже второй ступени содержатся группы из полусумматоров, число которых равио порядку порол дающего полинома; входы и выходы этих полусумматоров соответствуют весам разрядных остаточных полиномов вида 2 ио порождающему полиному (/ 0, 1,2,, к-1); входы полусумматоров первого этажа второй ступени в соответствии с разложением многочленных разрядных остаточных полиномов на одночленные разрядные остаточные полиномы вида 2 по порождающему полиному соединены с выходами полусумматоров последнего этажа первой ступени или с щинами разрядов исходного числа; входы полусумматоров последующих этажей второй ступени соединены с щииами, соответствующими суммам полусумматоров предществующих этажей первой, второй ступени или с щинами разрядов исходного числа, не соединенных со входами

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

j