Устройство для формирования остатка по модулю три

 

ОП И С Н П

ИЗОБРЕТЕНИЯ

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

Социмистииесних

Респу61тик

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

Зависимое от авт. свидетельства №

Заявлено 12.Х.1970 (№ 1489353/18-24) с присоединением заявки №

Приоритет

Опубликовано 22.V1.1973. Бюллетень № 28

Дата опубликования описания 28.XI.1973

М. Кл. G 06f 11/10

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

Совета Министров СССР по делам изобретений и открытий

УДК 681.326.75(088.8) Авторы изобретения

Л. Н. Волков, В. H. Волнянский и Ю. И. Кондратьев

Заявитель

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА

ПО МОДУЛЮ ТРИ

0 при а,=0

1 при а,=1

2 при а,=1

re.t,,a;2 —

i =21 — 1 (2)

i = 2k

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

Известны устройства, способные определять остаток от деления числа на три без выполнения операции деления. При вычислении остатка по mod 3 любого числа N в таком устройстве используется равенство и

rest,Í = rest., й, rest,а,2, (1)

i=1 где а; — весовой коэффициент i ãî разряда двоичного кода, равный 0 или 1; и — число разрядов кода, и свойство двоичного кода где A) i и целое число.

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

Цель |изобретения — упрощение устройства и повышение, надежности его работы.

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

1о Схема предлагаемого устройства для определения остатка tto mod 3 приведена на чертеже.

Устройство содержит схемы «И» 1 — б, выходы которых попарно через схемы «ИЛИ»

15 7, 8, ti 9 соединены с входами линий 10, 11 и

12 задержки. Выходы линий задержки подключены к одному из входов схем «И» 1 — б, на другие входы этих шести схем «И» поступает двоичный код, причем на схему «И» 1, 20 3, 5 непосредственно со входа 13, а на схемы

«И» 2, 4, б через схему «НЕ» 14, Предлагаемое устройство предназначено для осуществления свертки кода по mod 3, если двоичньш код поступает на устройство формирования остатка по mod 3 старшими разрядами вперед, а также восстановления остатка, если код подается младшими разрядами вперед.

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

Зо Последовательный двоичный код проходит

388265

60 на входы схем «И» 1, 3, 5,непосредственно, а на входы остальных схем «И» 2, 4, 6 — через схему «НЕ» 14. К момен ту прихода первого разряда кода с помощью сигнала установки начальных условий (с клеммы 15) на выходе линии 10 задержки формируется «1», а на выходе линий 11 и 12 задержки устанавливается «О».

Рассмотрим сначала работу устройства в первом такте, т. е. при поступлении и преобразовании в устройстве формирования остатка по тоН З,первого разряда кода.

Если,в первом разряде кода, поступившем на схему формирования остатка, был «О» то, проинвертировавшись на схеме «НЕ» 14, на вход схемы «И» 2 приходит «1». При этом формируется сигнал, соответствующий «1», .только на выходе одной схемы «И» 2, на обоих входах которой оказались «1», на выходах остальных схем «И» 1, 8 — б, сигнал отсутствует, так как по крайней мере на одном из входов этих схем «И» оказывается «О». Сигнал с выхода схемы «И» 2, пройдя через схему

«ИЛИ» 7, появляется через такт на выходе линии 10 задержки, в связи с тем, что линии

10, 11, 12 задержки осуществляют задержку сигналов, поступающих на их вход, на один такт, Таким образом, через такт, т, е. в момент поступления второго разряда кода, сиг.нал «1» с выхода линии 10 задержки вновь присутствует на .входах только двух схем «И»

2 8

Если в первом, разряде кода, предназначенном для свертки или восстановления остатка, была «1», сигнал появляется только на выходе схемы «И» 8 .и через один такт па выходе лин ии 11 задержки. В этом случае в момент прихода второго разряда, кода сигнал, сформированный на выходе линии 11 задер>кки, присутствует на входах схем «И» 1, б.

Во втором такте сигнал, соответствующий

«1», также появляется только па выходе одной схемы «И», а именно той, на обоих нходах которой оказались «1», поступившие с выхода одной из линий задержки (10 плп 11) и с входа 13 или с выхода схемы «НЕ» 14, в зависимости от наличия «О» или «1» но втором разряде кода.

Таким образом, к третьему и последующим тактам сигнал, соответствующий «1», всегда формируется только на выходе одной из трех лини11 задсржки и совпадение двух «1» при поступлении очередного разряда кода происходит только на входе одной схемы «И», Состояния на выходах 16, 17 и 18 устройства формирования остатка по mod 3 изменяются до тех пор, пока через вход 13 не пройдут все разряды кода.

Наличие «1» через такт после,поступления последнего разряда кода на одном из выходов устройства формирования остатка по mod 3 определяет величину остатка, который при свертке или восстановлении остатка кода, 5

40 имеющего нечетное кол ичество разрядов, равен соответственно 0,1,2. В случае восстановления остатка двоичного кода с четным числом разрядов выходы устройств следует считать соответствующими остаткам О, 2, 1.

Рассмотрим несколько примеров.

11усть требуется свернуть код 011, где первый справа знак соответствует старшему разряду, Остаток от деления 3 этого числа должен быть равен нулю. Действительно, после прихода перного разряда кода сигнал, соответствующий «1», появляется на выходе схемы «И» 8, после второго — а выходе схемы

«И» 1, после третьего — на выходе схемы «И»

2, следовательно, на выходе 16 устройства формирования остатка по mod 3, ч "î соответствует остатку «нуль».

11усть теперь требуется провести носстан онление остатка этого кода, т. е. код поступает младшими разрядами вперед. В этом случае после прихода .первого разряда кода сигнал, соответствующий «1», появляется на выходе схемы «И» 2, после второго — на выходе схемы «И» 8, после третьего — на выходе схемы

«И» 1, следовательно, опять на выходе 16 устройства формирования остатка по mod 3.

Рассмотрим теперь пример восстановления остатка кода, содержащего четное число разрядов, например кода 1010 (слева — младший разряд). В этом случае после прихода первого разряда, кода, т. е. единицы, сигнал появляется на выходе схемы «И» 8, после второго — на выходе, схемы «И» б, посл е третьего— на выходе схемы «И» 5, после четвертого— на выходе схемы,«И» 4. После прохождения всего кода сигнал появляется на выходе 17 устройства формирования остатка по mod 3, что для данного случая (восстановления остатка кода с четным числом разрядов) означает остаток 2.

Таким образом, полученный остаток и устройстве формирования остатка по mod 3, соответствует истинному значению остатка кода.

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

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

«И», «ИЛИ», «НЕ» и линии задержки, отличаюи1ееся тем, что, с целью у прощения устройства и повышения его надежности, выходы шести схем «И» попарно через три схемы

«ИЛИ» соединены с входами трех линий задержки, выход первой линии задержки соединен с входами второй и третьей схем «И», выход второй линии задержки — с входами первой и шестой схем «И», выход третьей лин ии задержки — с входами четвертой и пятой схем «И», другие входы всех шести схем «И» соедипсны с входом устройства, причем не= четные схемы «И» непосредственно, а четные схемы «И» через схему «НЕ».

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

Редактор И. Грузова Техред А. Камышникова Корректор О Усова

Заказ 3070 6 Изд, M 1741 Тираж 647 Подписное

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

Москва, )К-35, Раушская наб., д. 4 5

Типография, пр. Сапунова, 2