Коммутатор для многопроцессорной системы в поле галуа @ (2 @ )

 

„„SU„„1057951

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН .

А 5р С 06 г 15/16

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ГЮ ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ!

ОПИСАНИЕ ИЗОБРЕТЕНИЯ .

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ в (21)3380001/18-24 (22) 28.12.81 (46) 30.11.83. Бюл. И 44

i(72) Н.М.Никитюк (71) Объединенный институт ядерных исследований (53) 681.32(088.8) (56) 1. Hurakami Н. Huitichannel

Сопчо1иtionaI Codi„nq Systems очеr

0 I rec t Sum of G a Io i s Fi e l ds . I E EE

Тг., v, IT-24, N 2, 1978.

2. Питерсон У.Коды, исправляю щие ошибки. М .,"Мир",1964, с.167-176. (54) (57) КОММУТАТОР ДЛЯ МНОГОПРОЙЕССОРНОЙ СИСТЕМЫ В ПОЛЕ ГАЛУА GF(2 ), содержащий первый дешифратор и группу триггеров, отличающийся тем,что, с целью повьвения быстродействия и упрощения койструкции, он содержит группу элементов И, блок . элементов суммы по модулю два, блок

;умножения элементов в поле Галуа

G F(2m), второй дешифратор, причем первые входы элементов И группы соединены с информационными входами коммутатора, входы первого дешифратора соединены с первой группой управляю-, щих входов коммутатора, выходы первого дешифратора соединены с вторыми входами элементов И группы, выходы которых соединены с входами блока rn элементов суммы по модулю два, выходы которого соединены с первой группой входов блока умножения элементов в поле Галуа GF(2mi, вторая группа входов которого соединена с второй груп. пой управляющих входов коммутатора,. выходы блока умножения элементов в поле Галуа йа(2 1соединени с входа- (/) ми второго дешифратора, выходы которого подключены к установочным входам триггеров группы. |

Мдй

57951

4 10

Изобретение относится к вычисли" тельной технике и может быть использовано для построения вычислительных структур, дискретных коммутаторов связи и коммутатора магистрали в многопроцессорных вычислительных системах в поле Галуа GF(2 ).

Известна многоканальная система для передачи элементов в поле Галуа

GF(2 " 1, содержащая передающие и приемные блоки и кодирующие устрой1ства, выполненные. на регистрах с ло" гической обратной связью 11 J.

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

Наиболее близким по технической сущности к предлагаемому является коммутатор для многопроцессорной системы s поле Галуа ЯР(2п31, содержащий группу триггеров, сдвиговый регистр, два сдвиговых регистра с логической обратной связью, группу элементов И и дешифратор 1 2 ).

Недостатки коммутатора - большое время коммутации сигналов и сложность управления работой коммутатора.

Цель изобретения - повышение быстродействия и упрощение устройства.

Поставленная цель достигается тем, что коммутатор для многопроцессорной системы в поле Галуа G 1-(2 1, содержащий первый дешифратор и rpynny триггеров, содержит группу элементов

И, блок щ элементов суммы по модулю два, блок умножения элементов в поле

Галуа G Р(2 ),второй дешифратор,причем первые входы элементов И группы соединены с информационными входами юммутатора, входы первого дешифратора соединены с первой группой управляющих входов коммутатора, выходы первого дешифратора соединены с вторыми входами элементов И группы, выходы которых соединены с входами блока ю элементов суммы по модулю два, выходы которого соединены с пер вой группой входов блока умножения элементов в поле Галуа QF(2п1), вторая группа входов которого соединена с второй группой управляющих входов коммутатора, выходы блока умножения элементов s поле Галуа 6Р(2п соедине ны с входами второго дешифратора выходы которого подключены к устано вочным входам триггеров группы.

Поле Галуа содержит 2 -1 различ", ных элементов, которые образуют циклическяй код. Среди 2 -1 различных элементов поля (элементов являются линейно независимыми. Путем линейной комбинации этих элементов

10 можно получить остальные элементы.

Пусть я1= 3« Все элементы поля можно получить с помощью неприводимых полиномов tv степени. Для rn = 3 та ким полиномом является x + х + 1, 15 а линейно независимыми элементами поляпри ю= Збудут: e = 100,4А010 и, а 2= 001, тогда любой элемент поля, а при rn = 3 можно представить в виде А = А У+ A eg+ Ag4; другой

2р какой-либо элемент поля В, будет отличаться от элемента А лишь значениями коэффициентов А>, А „и А, т.е. элемент В = Вца+ В с 1+ В> ><

«где коэффициенты Ав, А„, А, В, 25 В, В g в двоичной. системе счисления могут принимать значение 0 или l.

Если теперь положить, что й" является корнем полинома, то получим а +а +10.

Операции сложения и вычитания в поле Галуа равнозначны и выполняются по .модулю 2. Отсюда а = а"+

+1 110. Далее а =р- +а = 0«

+ 2 1

А5 - х4 ©1» 1+ 1+с 2 1«й =ol

6 5 1

35 С 2+О 1+ g 3ц 2+ a1+ а1+1 =401 6 О 1 3р д2+ у 1 с 100 =- ggО

О,Э о,>,О,1,1

В 1„-,.х2,2.

Таким образом получаются семь различных элементов поля Галуа

4Г(2 ). Умножение двух элементов производится путем прямого умноже-ния элементов, представленных в виде

A«B=(Aоа +А о +4 а ) (В а 8„в + х Д В y1„а„.д у „2,д В „3+

10 11 12

50 +А В с а +4 Be+A 8 ф

2 1 2 2

Так как а о = 100 = 1 - единичный элемент, а а 2+ а, то

jlss=a (A,ü,+ä„ü м,8„+л,ь )+

Или, обозначив коэффициенты при а, а1 и а в произведении А х В

3 1057 соответственно через Со, С „, C2, получим

С0 М,ю,+ „ 2+ 1 В„ i

С -A0g>+A< В А1 В «А 8„A282

2 о В2 1В.1+4 Вв+А В

Здесь, как.и выше, знак + обозначает суммирование по модулю 2. Таким

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

Это правило справедливо в поле Галуа лри любых 1п.

На фиг.l представлена структурная схема коммутатора для многопро.цессорной системы в поле Галуа GF(Z ) для т — — 3; на фиг.2 - вариант реализации- блока умножения элементов в поле Галуа GF(2 )äëÿ 1ъ = 3, Коммутатор (фи г. 1) содержит информационные входы 0-6, первый дешифратор 7, группу элементов И

8-0-8-6, группу элементов 9-0-9-2, сумма по модулю два, блок 10 умножения элементов в поле Галуа G F(Z ), первые управляющие входы коммутатора 11-1-11-3, вторые управляющие входы коммутатора 11-4-11-6, второй 30 дешифратор 12, группа триггеров

13-0-13-6, группу элементов И 14 и группу элементов 15 сумма по модулю два.

Информационные входы 0-6 пронумерованы в порядке возрастания степеней элементов поля Галуа GF(2э) в соответствии с матрицей

951 4 с выходами элементов И 8-1, 8-3, 8-4 и 8-5, а входы элемента 9-2 соединены с выходами элементов И 8-2, .8-4, 8-5 и 8-6. Эти связи определяются позициями единиц в столбцах матрицы Н, если счет вести сверху вниз. Пр1лчем при изменении числа такие связи носят нерегулярный харак. тер и их невозможно задать с помощью рекуррентных соотношений. Остается поэтому общепринятый способ задания связей с помощью матрицы H.

Блок 10 умножения элементов в поле G F(2 )содержит элементы И 14-0-, Э

14-8 и элементы 15-9-15-11 сумма по модулю два. сумма по

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

Пусть необходимо передать сигнал от входа 0 на вход 3 триггера 13-3 группы. 8 этом случае на входы 11-111-3 дешифратора 7 подается код а

= 100, который дешифрируется, при этом открывается элемент И 8-.0. Сигнал с выхода этого элемента поступает на вход схемы 9-0 сумма по модулю два. На выходах остальных элементов И будут сигналы логического нуля, поэтому на выходах элементов

9-0-9-2 сформируется код 100 а который поступает на первые входы блока 10 умножения в поле Галуа

CF(2 ).0äíoâðåìåíHo извне на управляющие входы 11-4-11-6 подается код, соответствующий элементу

a = 110. Результат умножения авxaЭ з

Э

= а подается на вход дешифратора

12, на входе 3 триггера 13-3 группы появится сигнал "1". Следует аО

100

40 а1

010

001

45 аЭ

Н =

011

50 аь

101

С помощью матрицы Н задаются связи выходов элементов 8-0-8-6 с входами элементов сумма по модулю два 9-0-9-255

Так входы элемента 9-0 связаны с выходами элементов И 8-0, 8-3, 8-5 и

8-6, входы элемента 9-1 соединены отметить, что элементы поля Галуа

GF(2 ) можно рассматривать как обычные

Э двоичные числа и тогда а = 110=3.1О (младший разряд слева). 8 результате произошла коммутация логического сигнала от входа 0 на вход 3 группы триггеров 13.

Пусть теперь необходимо передать логический сигнал от входа 6 на вход

2 триггера 13-2 группы. 8 этом случае на входы 11-1-11-3 дешифратора,7 поступает код, соответствующий элементу а з = 111, который дешифрируется, при этом открывается элемент И 8-6. Сигнал с выхода этого элемента поступает на входы элементов 9-0 и 9-2 и на вход блока умножения поступает .код 101 ал .

Одновременно на входы 11-4 - 11-6 по.ступает на код 001=а . 8 результате умножения в блоке 10 получим а а рестановка (переключение входных . разъемов ) приемного блока.

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

Таким образом, введение новых признаков и связей позволило повысить быстродействие и упростить конструкцию коммутатора.

9 1057951 ао= а а" a a" "0!0 2 ! о > после дешифрации в блоке 12 на входе

2 триггера 13-2 группы появится сиг1 нал. Таким образом на входы 11-1-11-3 поступает адрес источника информации, 5 а на входы 11-4-11-6 поступает адрес приемника информации. Причем эти адреса поступают в циклическом коде в виде элементов поля Галуа. Поскольку элементы поля Галуа представляют собой двоичные слова, то -предлагаемый коммутатор может быть также использован и в обычных цифровых вычислитель-! ных устройствах, с той лишь разницей, что потребуется пространственная пе1057951

УМ рог. 2

Составитель Логачева

Редактор С.бско Техред Т,.Фанта Корректор Г.Решетник

Заказ 9465/52 Тираж 706 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 415

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4