Устройство для формирования контрольных разрядов логических операций

 

OnИСЛНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ш 570898

Союз Советских

Социалистических

Реолублик (61) Дополнительное к авт. свид-ву (22) Заявлено 02.06.75 (21) 2139749/24 с присоединением заявки № (23) Приоритет

Опубликовано 30.08.77. Бюллетень ¹ 32

Дата опубликования описания 14.09.77 (51) М. Кл.2 G 06Г 11/10

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДК 681.326.75 (088.8) (72) Автор изобретения

А. И. Карпухин (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ КОНТРОЛЬНЬ1Х

РАЗРЯДОВ ЛОГИЧЕСКИХ ОПЕРАЦИЙ

Изобретение относится к вычислительной технике и может быть использовано в устройствах обнаружения и исправления t-кратных ошибок логических операций.

Известно устройство для формирования контрольных разрядов некоторых логических операций кодом Рида — Маллера (1).

Однако это устройство имеет большую кодовую избыточность при реальной разрядности вычислительных машин. Например, защита от тройных ошибок результата логической операции над 16-разрядными операциями требует 112 избыточных разрядов, что равносильно 8-кратному резервированию.

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

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

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

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

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

20 группами входов третьей группы сумматоров по модулю два и с первыми входами третьей и четвертой групп элементов И. Первая группа выходов третьей группы сумматоров по модулю два через группу элементов НЕ, а

25 вторая группа выходов непосредственно соединены с первыми входами пятой группы элементов И, выходы блока управления — с вторыми входами второй, третьей, четвертой и пятой групп элементов И, выходы которых

30 подключены к входам четвертой группы сум570898 маторов по модулю два, выходы четвертой группы сумматоров по модулю два являются выходами устройства.

Принцип действия устройства заключается в следующем. 5

Пусть две двоичные последовательности

А= (а„,..., а„» 1, а„»,..., а,) в = (ь„,..., ь„,, ь„,,..., ц, и защищенные систематическим линейным кодом, имеют k контрольных и n — k = m информационных разрядов. Требуется произвести над разрядами этих последовательностей одну из 1б логических операций таким обра- 15 зом, чтобы результат логической операции также имел бы правильные контрольные разряды.

Переведем разряды двоичных последовательностей А и В вместс с контрольными разряда- 20 ми из элементов аддитивной группы поля

6Г (2) в элементы 0 = (00) и 2 = (10) для последовательности А и в элементы 0 = (00) и 1 = (01) для последовательности В аддитивной группы поля GF (2 ). Обозначим полученные последовательности буквами А и В соответственно.

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

1 (аА): а1 Ь" 4 а1 Рг 1/ a(bPç,/ аА-4 (1) где cc — управляющие сигналы.

Представим каждый член дизъюнкции (1) (за исключением управляющих сигналов а,) З5 в виде элементов поля GF (22), т. е. a;b; (=

= )00, так как если а; = b; = О, то a b; = 1.

Аналогично, a;b,(= ) 01, a,b;(= ) 10, а,b;(=)11, где 00, 01, 10, 11 EGF(22). Тог- 40 да при сложении в поле GF(2 ) соответствующих разрядов последовательностей А и В образуется последовательность, имеющая правильные контрольные разряды применяемого линейного кода. Обозначим эту последова- 45 тельность буквой С.

Однако для выполнения какой-либо логической операции из совокупности четырех членов дизыонкции (1) необходимо выбрать лишь заданные управляющими сигналами а„. 50

Обозначим:

C», C» — контрольные разряды последова(.) тельностей С и С< ), где V =

= О, 1, 2, 3, \/ ==61(22):

C „C(— информационные разряды после(,) довательностей С и С ()

1 аждой последовательности С„, соответствует своя последовательность контрольных 60 разрядов C», образованная в соответствии с проверочной матрицей применяемого линейного кода. Очевидно, что

С, = С,")+ С,")+ С."), (2) 65 где «+» — сумма в поле 61 -(2 ), так как в противном случае последовательность С1, в соответствии с доказа нным утверждением правильная, т. е. ей не соответствует последовательность С .

Если из последовательности С, содержащей все четыре элемента поля GF(2 ), выделить контрольные разряды соответствующего линейного кода по одному из элементов поля, например по элементу 3wGF(22), и составить последовательность С(), то последовательз ность С = С, + С,„(вычитание в поле

61 (2™) эквивалентно сложению) будет содержать только три элемента поля GF (2 ) . Тогда разряды последовательности С» = С» + С», равные 3, будут суммой соответствующих раз1 2 рядов последовательностей С» и С», а равные 1 и 2 — разрядами последовательностей г

С» и С» соответственно. Если разряды последовательности C» равны нулю, то соответствующие разряды последовательностей

3 2 1

С», С» и С» также равы нулю.

Для определения контрольных разрядов последовательности C() переведем разряды выделенных из С последовательностей С< ), С<2), C< ) в элементы поля GF(2). Очевидно, что полученные таким образом последовательности имеют правильные контрольные разряды применяемого систематического линейного кода.

Обозначим эти последовательности С ), где в общем случае V = О, 1, 2, 3; так как сумма четного числа единиц по модулю два равна нулю, а нечетного числа единиц — единице, контрольные разряды последовательности С() равны

С,) =-С<,)-::C„, C„„, (3) где и = 0,15 — десятичная форма записи двоичного числа (01, а2, С(з O4) °

Так как соответствующие разряды последовательности С„, не пересекаются, (v)

<;) (о) (1) (2) <з)

Z — С я /С а \/С n, /С а4 где г=(+), если число единиц в i-й строке проверочной матрицы четное;

« = (), если число единиц нечетное.

Очевидно, что полученные последовательности С(), С(), С(2), С< ) имеют правильные контрольные разряды и у суммы в поле

GF (2) (т, е. по модулю два) любых из них правильные контрольные разряды. Таким образом, можно сформировать 1б последовательностей, компоненты которых соответствуют 1б логическим функциям двух переменных а< и b;. Любую из этих последовательностей можно получить из выражения

Z< » =. C<0) с: — C< ), () С< ) г (+) С(з)л (4) 570898

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

1) каждым двум разрядам а;, <), е=ОР(2) входных последовательностей А = (а„,..., a» i,+r, а„ i„..., ar), В = (b„,, b»r,+ь

b» !„ ..., br) ставится в соответствие компонента С;wGF (2 ) последовательности С= (C„,..., C — i,iü C — i„....,,Cl);

2) из последовательности С выделяется последовательность С,», по которои форми(3) руются контрольные разряды С<, <з)

3) производится сложение последовательностей С), и Сд в поле GF(2 ) и формируются

<з) последовательности С> и С» (1) (2).

4 ) разряды последовательностей С<,, С<, <з) р)

1 и C

5) над разрядами последовательностей (0) (1)

Cr, C>< ), С ), С< ) производится операция (4).

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

На чертеже представлена блок-схема предлагаемого устройства.

Устройство содержит регистры 1 и 2 операндов, регистры 3 и 4 контрольных разрядов, входы которых являются входами 5, 6, 7 и 8 устройства соответственно группы 9 — 12 сумматоров по модулю два, группы 13 — 17 элементов И, блок 18 формирования контрольных разрядов операций логического сложения, группу 19 элементов НЕ и блок 20 управления.

Выходы регистров 1 и 2 соединены с входами группы 13 элементов И, выходы которой подключены к входам блока 18 формирования контрольных разрядов операций логического сложения, выходы блока 18 — с первыми входами групп 9, 10 и 11 сумматоров по модулю два и с первыми входами группы 14 элементов И. Выходы регистров 3 и 4 подключены к вторым входам групп 9 и 10 сумматоров по модул<о два, выходы которых связаны с вторыми и тр тьими входами группы

11 сумматоров по модулю два и с первыми входами групп 15 и 16 элементов И.

Выходы группы 11 сумматоров по модулю два, которым соответствуют строки матрицы применяемого систематического линейного кода с нечетным числом единиц, через группу 19 элементов НЕ, а остальные непосредственно соединены с первыми входами группы 17 элементов И, а выходы блока 20 управления — с

65 вторыми входами групп 14 — 17 элементов И

Выходы групп 14 — 17 элементов И подключены к входам группы 12 сумматоров по модулю два, выходы которой являются выходами

21 устройства.

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

Сигналы с регистров 1 и 2 поступают на гру ппу 13 элементов И, где фор миру)отся

<з) функции С< = а

r,õoäû группы 11 сумматоров, а с выходов группы 11, которым соответствуют строки матрицы применяемого систематического линейного кода с нечетным числом единиц, через групп 19 элементов НЕ, а с остальных— непосредственно, сигналы, являющиеся контрольными для последовательности С<"), поступают на одни входы группы 17 элементов И.

Сигналы с выходов блока 18 и групп 9 и 10 подаются на первые входы групп 14, 15, 16 элементов И соответственно. На вторые входы групп 14 — 17 поступают сигналы с выходов блока 20 управления, а с выходов групп 14—

17 — на входы группы 12 сумматоров по модулю два, в которой формируются контрольiIbie разряды результата заданной управляющими сигналами логической операции.

Если l (или менее) ошибок произошло при формировании функции C„= а;Ь;, то они

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

Перевод входных двоичных последовательностей, защищенных систематическим линейным кодом, в последовательность с компонентами из поля GF(2 ) позволяет выделить в ней элементы С< = a b; и затем применить

<з) единый алгоритм для определения контрольных разрядов IIoooH логической операции.

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

Формула изобретения

Устройство для формирования контрольных разрядов логических операций, содержащее два регистра операндов и два регистра конт570898

Составитель В. Крылова

Техред И. Карандашова

Корректор Е. Хмелева

Редактор И. Грузова

Заказ 1979/4 Изд. М 707 Тираж 818

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

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

Подписное

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

10 групп элементов И, выходы которых соединены с входами четвертой группы сумматоров по модулю два, выходы четвертой группы сумматоров по модулю два являются выходами устройства.

15 Источники информации, принятые во внимание при экспертизе

1. К. Ргас111ап and КеИу, Error Control

Technigens for logic Processors «1ЕЕЕ Trans

CompUt», vol С-21, 1972.

20 2. Путинцев Н. Д. Аппаратный контроль управляющих цифровых вычислительных машин. М., Сов. радио, 1966, с. 162 — 171.