Устройство для контроля оптимальных @ -кодов фибоначчи

 

УСТРОЙСТВО ДЛЯ КОНТРОЛЯ ОПТИМАЛЬНЫХ р-КОДОВ ФИБОНАЧЧИ, содержащее п-разрядный регистр, где п - количество разрядов в контролируемом коде, элемент ИЛИ, (п-р-1) блоков фиксации сбоев, каждый из которых содержит элемент И и р-входовой элемент ИЛИ, причем в каждом блоке фиксации сбоев выход элемента ИЛИ соединен с первым входом элемента И, единичный вход п-го разряда регистра является информационным входом устройства, установочный вход устройства соединен с нулевыми входами разрядов регистра, единичные выходы разрядов регистра являются группой информационных выходов устройства, единичные выходы р младших разрядов регистра соединены с соответствующими входами первой группы входов устройства, единичный выход каждого j-ro разряда регистра. (J (р+1), п), соединен с вторым входом элемента И (j-p-l)-ro блока фиксации сбоев и с К-м входом элемента ИЛИ (j-p+K-1)-ro блока фиксации сбоев, выход элемента И каждого блока фиксации сбоев соединен с соответствукмцим входом второй группы входов элемента ИЛИ, выход которого является выходом неисправности устройства , отличающееся тем, что, с целью повьшения достоверности контроля, в устройство введены первый и второй блоки индикации , (п-Зр-2)- и

(19) 111) СОЮЗ СОВЕТСНИХ

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

РЕСПУБЛИН

1 А

11 у G 06 F 11 00

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3561067/24-24 (22) 09.03.83 (46) 07.04.85. Бюл. Р 13 (72) А.В.Ткаченко (53) 681.3 (088.8) (56) 1. Стахов А;П. Введение в алгоритмическую теорию измерения.

М., "Советское радио", 1977, с. 148, рис. 38.

2. Авторское свидетельство СССР

У 817718, кл. С 06 F 11/00, 1979 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ КОНТРОЛЯ

ОПТИМАЛЬНЫХ р-КОДОВ ФИБОНАЧЧИ, содержащее и-разрядный регистр, где и — количество разрядов в контролируемом коде, элемент ИЛИ, (и-р-1) блоков фиксации сбоев, каждый из которых содержит элемент И и р-входовой элемент ИЛИ, причем в каждом блоке фиксации сбоев выход элемента ИЛИ соединен с первым входом элемента И, единичный вход п-го разряда регистра является информационным входом устройства, установочный вход устройства соединен с нулевыми входами разрядов регистра, единичные выходы разрядов регистра являются группой информационных выходов устройства, единичные выходы р младших разрядов регистра соединены с соответствующими входами первой группы входов устройства, единичный выход каждого j-го разряда регистра, (j - (р+1), n) соединен с вторым входом элемента И (j-р-1)-ro блока фиксации сбоев и с К-м входом элемента ИЛИ (j-р+К-1)-го блока фиксации сбоев, выход элемента И каждого блока фиксации сбоев соединен с соответствующим входом второй группы входов элемента ИЛИ, выход которого является выходом неисправности устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения достоверности контроля, в устройство введены первый и второй блоки индикации, (n-Зр-2)- и (2р+1)-входовых элемента И и два (р+1)-входовых элемента И, причем нулевой выход

PQ каждого j- ãî разряда регистра соединен с (n- j+1)-м входом первого (р+1)-входового элемента И, с С: (2р+2-j)-м входом второго (р+1)-входового элемента И и с (Зр+2+ш-j)-м Я входом ш-ro (2р+1)-входового элеа (. 1; Ь=%=25, ные выходы р младших разрядов регистра и выходы элементов И блоков фиксации сбоев соединены с соответствующими входами первого блока индикации, выходы всех элементов

И устройства соединены с соответствующими входами второго блока индика« . ции и входами первой группы входов элемента ИЛИ устройства, единичные входы (n-1) младших разрядов регистра являются группой информационных,Ъ» входов устройства.

11492б1

Изобретение относится к вычислительной технике и передаче данных и может быть использовано для контроля оптимальных р-кодов Фибоначчи.

Известно устройство для контроля 5 р-го кода Фибоначчи, содержащее .

n""ðàçðÿäHûé регистр, элемент ИЛИ и (n-p) блоков фиксации сбоев (1) .

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

Наиболее близким по технической 15 сущности к предлагаемому является устройство для контроля р-кодов

Фибоначчи, содержащее и-разрядный триггерный регистр, элемент ИЛИ группу из (n-р+1) элементов ИЛИ 20 (n-р) блокав фиксации сбоев, каждый из которых содержит первый и второй элементы И, формирователь импульсов и р-входовой элемент ИЛИ, выход которого соединен с первым входом перво- 25

ro элемента И, первый вход блока фиксации сбоев соединен с входом формирователя импульсов и вторым входом первого элемента И, выход которого являЕтся первым выходом блока фик- 30 сации сбоев, выход формирователя импульсов соединен с первым входом второго элемента И, выход которого является вторым выходом блока фиксации сбоев, управляющий вход блока фикъ5 сации сбоев подключен к второму входу второго элемента И, а остальные р-входов блока фиксации сбоев связаны с соответствующими входами .элемента ИЛИ, первые выходы всех блоков фиксации сбоев совместно с выходами триггеров р младших разрядов регистра соединены с соответст вующими входами элемента ИЛИ, выход которого является контрольным выходом 4$ устройства, а выход каждого 1-го триггера регистра является информационным выходом устройства и соединен с первым входом соответствующего (i-p) -го блока фиксации сбоев, каждый

j-й вход которого соединен с (j+1)-м входом (i-р-f)-ro блока фиксации сбоев, управляющие входы всех блоков фиксации сбоев соединены с управляющим входом устройства, установочный вход которого соединен с первым вхо/ дом всех трйггеров регистра, инфор мационный вход триггера старшего

+ разряда регистра соединен с информа ционным входом устройства, остальные информационные входы устройства соединены с соответствующими первыми входами каждого элемента ИЛИ группы, второй выход каждого i-ro блока фиксации сбоев .соединен с вторым входом (i-1)-го и третьим входом (i-2)-го элемента ИЛИ группы, выход каждого элемента ИЛИ группы соединен с информационным входом соответствующего триггера регистра (2) .

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

Недостаток известного устройства — низкая достоверность контроля.

Цель изобретения — повышение достоверности контроля.

Поставленная цель достигается

f тем, что устройство для контроля оптимальных р-кодов Фибоначчи, содержащее п-разрядный триггерный регистр, где n — количество разрядов в контролируемом коде, элемент ИЛИ, (n р-1) блоков фиксации сбоев, каждый из которых содержит элемент И и р-входовой элемент ИЛИ, причем в каждом блоке фиксации сбоев выход элеменга ИЛИ соединен с первым входом элемента И, единичный вход q -ro разряда регистра является информационным входом устройства, установочный вход устройства соединен с нулевыми входами разрядов регистра, единичные выходы разрядов регистра являются группой информационных выходов устройства, единичные выходы р младших разрядов регистра соединены с соответствующими входами первой группы входов устройства, единичный выход каждого j-Fo разряда регистрами - . (р+1), и), соединен с вторым входом элемента И (j-p-t)ro блока фиксации сбоев.и с К-м входом элемента HJIH (j-р+К-1)-ro блока фиксации сбоев, выход элемента И каждого блока фиксации сбоев соединен с соответствующим входом второй группы входов элемента ИЛИ, выход которого является выходом неисправности устройства, дополнительно содержит первый и второй блоки индикации, (n-3p-2)- и (2р+1)входовых элементов И и два (р+1)1149261 i ht где (pal) ) t >K Vp (n-}-k) =Q

"=5 1 при j = (р+1), g (n)- мощность оптимального

"фибоначчиевого" р-кода разрядностью }1, индекс В обозначает номер изображаемого оптимального числа в оптимальном р-коде

Фибоиаччи.

Оптимальные "фибоначчиевые" р-коды заполняют промежуток между представлением единиц (р=0) и представлением нулей (р 0o ).

На фиг. изображена структурная схема предлагаемого устройства для р=2 и и =12, на фиг. 2 — функциональная схема блока фиксации сбоев.

Устройство (фиг.1) содержит триггеры 1. 1-1. 12 регистра, блоки 2. 12.9 фиксации сбоев, первый 3.1 и второй 3.2 трехвходовые элементы И, пятивходовые элементы И 4.1-4.42 входовых элементов И, причем нулевой выход каждого j-ro разряда регистра соединен с (n-j+1) м входом первого (р+1)-входового элемента И, с (2р+2-j)-м входом второго (р+1)входового элемента И и с (3p+2+m-j)-м входом m-ro (2р+1)-входового элемен. и:т-,Тени .... выходы р младших разрядов регистра и выходы элементов И. блоков фиксации сбоев соединены с соответствующими входами первого блока индикации, выходы всех элементов И устройства соединены с соответствующими входами второго блока индикации и входами первой группы входов элемента ИЛИ устройства, единичные входы (n-1) младших разрядов триггерного регистра являются группой информационных входов устройства.

Аналогичный алгоритм оптимальных р-кодов Фибоначчи при заданном целом р > 0 и любом целом п > 0 и

1 а В « g p(n) задается следующим рекуррентныи соотношением в "фибоначчиевой" р-системе счисления:

0»»р» Ой п е р, Ъ =1

Р.»»

F („) F}» E Р(" p-"}(n Р,})+Чр(».)}»}р» " р Vp(n- P k) 8 Е Q}»(n-}»-k); к jt1 Ке) 5

Ю

55 блок 5 индикации, элемент ИЛИ 6, блок 7 индикации, информационные входы 8 устройства, установочный вход 9 устройства, а каждый блок 2 фиксации сбоев имеет первый 10, второй 11 и третий 12 входы.

В состав каждого блока 2 фиксации сбоев (фиг.2) входят элемент ИЛИ 12 и элемент И 14.

Установочный вход 9 устройства соединен с нулевыми входами триггеров 1.1-1.12 триггерного регистра, единичные входы триггеров 1.1-1.12 триггерного регистра являются группой информационных входов 8 устройства, а единичные выходы триггеров- 1.11. 12 триггерного регистра являются выходами группы информационных выходов устройства.

Единичные выходы триггеров 1. 1, 1.2 соединены с соответствующими входами элемента ИЛИ 6 и блока 7 индикации. Единичный выход каждого

1-го триггера регистра, где J (р+1), и, соединен с вторым входом элемента И 14 (J-p-1)-го блока фиксации сбоев и с К-м входом (где

К -: f,р) элемента ИЛИ 13 (j-p+K-1)го блока фиксации сбоев, соединен с соответствующими входами блока 7 индикации и элемента ИЛИ 6, выход которого является выходом неисправности устройства. Нулевой вход каждого j-го триггера регистра соединен с (n-j+1)-м входом элемента И 3.1, с (2р+2- j ) -м входом элемента И 3. 2 и о (Зр+2+т-2)-м неоном m-го элемента И, где m - 1, (n-3p-2). Выходы элементов И 3. 1, 3.2, 4.1-4.4 соединены с соответствующими входами блока 5 индикации и элемента

ИЛИ 6. Выход элемента ИЛИ 13 соединен с первым входом элемента И 14.

Триггеры 1.1-1.12 регистра предназначены для хранения исходного кода. Для представления одного и того же диапазона чисел регистр предлагаемого устройства по сравнению с регистром известного устройства дополнительно содержит

2- »н 1

Блоки 2.!-2.9 фиксации сбоев, начиная со старших разрядов, предназна149261 6 блока 2 фиксации сбоев, выходов элементов И 3 и 4 и единичных выходов триггеров 1. 1 и 1.2 регистра. Информационные входы 8 устройства пред5 назначены для записи параллельным образом в триггеры !. 1-1. 12 регистра оптимального иэображения кода. Установочный вход 9 устройства необходим для установки триггеров 1.1-1.12 ре-!

О гистра в исходное нулевое состояние.

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

В исходном состоянии после подачи !

5 на установочный вход 9 устройства единичного сигнала триггеры 1. 1-1. 12 устанавливаются в нулевое состояние.

Предположим, что в регистре необходимо хранить код числа 9, представ20 ленного в оптимальной форме оптимального 2-го када Фибоначчи. Из соотношения (1) определяем, что оптимальное изображение данного числа имеет вид иэображения числа 40, представ25 ленного в известном 2-м коде Фибоначчи следующим образом:

8 7 6 5 4 3 2 1 вес разряда 41 28 19 13 9 6 4 3 2 1 1 1

2-й код

Фибоначчи 0 1 0 0

1 0 0 1 0 0 0 0

Этот код параллельным образом заносится в триггеры 1. 1-1. 12 регистра.

В результате единичный потенциал устанавливается на входах 10 блоков З

2.2, 2.5 и 2.8 фиксации сбоев, на входах 12 блоков 2.4 и 2.7 фиксации сбоев, а также на первых входах элементов И 3.1, 4.2 и 4.3, на вторых входах элементов И 3.2, 4.1, 4.3 н 4.4, на третьих входах элементов И 3.1. 3.2, 4.1 и 4.4, на четвертных входах элементов И 4.2 и

4.3, на пятых входах элементов И 4.1 и 4.3. Предположим, что под действием помехи триггер 1.12 переходит в единичное состояние и код принимает вид 110010010000. Единичный потенциал, поступая с единичного выхода триггера 1.12 на вход 10 блока 2.9 фиксации сбоев, вызывает срабатывание этого блока. Единичный потенциал с выхода блока 2.9 фиксации сбоев поступает на блок ? индикации, сигнализируя, что в группе иэ триггеров 1.10-1; 12 произошел сбой типа перехода "0" в "1", и через элемент, ИЛИ 6 устанавливается на контрольном чены для выработки сигналов, свидетельствующих о том, что для группы из (р+1) разрядов нарушено условие минимальности.

Блок 2 фиксации сбоев срабатывает при поступлении на его вход 10 и хотя бы на один из его входов 11 или

12 единичных сигналов. Элементы

И 3.1 и 3.2 предназначены для выработки сигналов, свидетельствующих о том, что для группы из (р+1) разрядов нарушено условие оптимальности, Элементы И 4.1-4.4 необходимы для выработки сигналов, свидетельствующих о том, что для группы из (2р+1) разрядов нарушено условие оптимапьности.

Блок 5 индикации фиксирует сбои типа перехода "1" в "0" и предназначен для отображения номера сработавшего элемента И 3 или 4, а блок 7 индикации фиксирует сбои типа перехода "0" в "1" и предназначен для отображения номера сработавшего блока 2 фиксации сбоев. Элемент ИЛИ 6 необходим для объединения выходов

Ф разряда 12 11 10 9 выходе устройства, сигнализируя об . искажении оптимального 2-го кода

Фибоначчи. Если в рассматриваемом ! коде под действием помехи в единичное состояние переходит триггер

1.10 и код преобразуется к виду

011010010000, то единичный потенциал с единичного выхода триггера

1.10 устанавливается на входе 10 блока 2.7 фиксации:сбоев, входе 11 блока 2.8 фиксации сбоев, входе .12 блока 2.9 фиксации сбоев.

Блоки 2.7 и 2.8 фиксации сбоев срабатывают и единичный потенциал с их выходов через элемент ИПИ 6 устанавливается на контрольном выходе устройства, сигнализируя об искажении оптимального 2-ro кода Фибоначчи. Одновременно единичный потенциал с выхода блока 2,7 фиксации сбоев поступает на блок 7 индикации, указывая, что в группе из триггеров

1.8-1. 10 происходит сбой типа перехода "0" и "1", а единичный потенциал с выхода блока 2.8 фиксации сбоев поступая на индикатор 7, указывает, ч1 о сбой типа перехода "0" в "1"

1149261 происходит в группе из триггеров

1.9-1. f f. Так как триггеры 1.9 и 1.10 содержатся в обоих локализованных группах триггеров, то при однократном сбое это означает, что сбой типа перехода "О" в "1" имеет место либо н триггере 1.9, либо в триггере 1.10. Пусть под действием помехи триггер 1.9 переходит в единичное состояние и код принимает вид 010110010000. В этом случае срабатывает блок 2.8 фиксации сбоен по входам 10 12 и блок 2.6 фиксации сбоев по входам 10 и 11. Единичный потенциал с ныхода блока 2.8 фиксации сбоев поступает на блок 7 индикации,сигнализируя, что в группе из триггеров 1.9 и 1.11 происходит сбой типа перехода "0" в "1", а единичный потенциал с выхода блока

2,6 фиксации сбоев, поступая на блок 7 индикации,- сигнализирует, что н группе из триггеров 1.7-1.9 происходит сбой типа перехода "0" н

"1". Так как триггер !.9 содержится н обоих локализованных группах триггеров, то это указывает, что сбой типа перехода "О" в "1" при однократной ошибке имеет место в триггере 1.9. Одновременно единичный потенциал с выходов блоков 2.6 и 2.8 фиксации сбоев через элемент ИЛИ 6 устанавливается на контрольном выходе устройства, сигнализируя об искажении оптимального 2-ro кода Фибоначчи

Если в рассмотренном коде числа

9 под действием помехи в единичное состояние переходит триггер 1.7, то срабатывает блок 2.5 фиксации сбоев по входам 10, 11 и блок 2.4 по входам 10, 12, если в единичное состояние переходит триггер 1.6, то срабатывает блок 2.5 фиксации сбоев по входам 10, 12 и блок 2.3 фиксации сбоен по входам IО, 11, если в единичное состояние переходит триггер

1,4, то срабатывает блок 2.2 фиксации сбоев по входам 10 11, если в единичное состояниепереходит триггер

1,3, то срабатывает блок 22.2 фиксации сбоев по входам 1О, 12. Если в единичное состояние переходят триггеры 1.1 или 1.2, то единичные потенциалы, сигнализирующие об искажении оптимального 2-го кода Фибоначчи, с их единичных выходов поступают на соответствующие входы элемента ходит триггер 1.5 и код преобразует4$ ся к виду 01001000000, то срабатыва50

5

ИЛИ 6 и блока 7 индикации непосредственно.. Следовательно, предлагаемое устройство обнаруживает нсе однократные сбои типа переход "О" в "1" в оптимальном р-коде Фибоначчи.

Кроме того, предлагаемое устройство позволяет также обнаружить нсе однократные сбои типа переход "1" в "О" н оптимальном р-коде Фибоначчи. Предположим, что под действием помехи триггер 1. 11 переходит в нулевое состояние. Тогда код принимает вид 000010010000, и на нулевом выходе триггера 1.11 появляется единичный потенциал, который устанавливается на втором входе элемента

И 3.1 и первом входе элемента И 4.4. одновременно. Элемент И 3.1 срабатывает, и единичный потенциал с его выхода поступает на блок 5 индикации, указывая, что в группе из триггеров 1.10-1.12 происходит сбой типа перехода "1" в "О", и через элемент ИЛИ 6 устанавливается на контрольном выходе устройства, что свидетельствует о нарушении оптимальной формы хранимого числа. Пусть под действием помехи триггер 1.8 переходит в нулевое состояние и код принимает вид 0100000l0000. Единичный потенциал с нулевого выхода триггера 1.8, поступая на третий. вход элемента И 4.4, вызывает его срабатынание. Единичный потенциал с выхода элемента

И 4.3 через элемент ИЛИ 6 устанавливается на контрольном выходе устройства, что свидетельствует о нарушении оптимальной формы представления числа, и поступает на блок 5 индикации, указывая, что в группе из триггеров 1.6-1. 10 происходит сбой типа перехода "1" н "0". Если под дейст-..— вием помехи в нулевое состояние переет элемент И 3.2. Единичный потенциал с его выхода поступает на блок

5 индикации, указывая, что в группе из триггеров 1.3-1.5 происходит сбой типа перехода " 1" в "0", и через элемент ИЛИ 6 устанавливается на контрольном выходе устройства, сигнализируя о нарушении оптимальной формы представления числа. Таким образом, предлагаемое устройство обеспечивает обнаружения всех однократных сбоев в оптимальном р-коде

Фибоначчи.

1149261

Ошибки большей кратности обнаруживаются устройством частично. Если в рассматриваемом оптимальном коде числа 9 под действием помех триггер 1.11 переходит в нулевое состояние, а триггер 1.3 одновременно — в единичное состояние, то срабатывает элемент И 3.1 и блок 2.2 фиксации сбоев по входам 10 12.

Единичный потенциал с выхода элемента И 3.1 поступает на блок 5 индикации, указывая, что в группе из триггеров 1. 10-1. 12 происходит сбой чипа перехода "!" в "0", а единичный потенциал с выхода блока

2,2 фиксации сбоев, поступая на блок 7 индикации, сигнализирует, что в группе из триггеров 1.3-1.5 происходит сбой типа перехода "0" в "1". Кроме того, данные единичные потенциалы через элемент ИЛИ 6 устанавливаются на контрольном выходе устройства, что свидетельствует о нарушении оптимальной формы хранимого числа. Однако, если под действием помех триггер 1.5 переходит в нулевое состояние, а триггер 1.3 одновременно — в единичное состояние, и код принимает вид

010010000100, то на входе 12 блока

2.4 фиксации сбоев, входе 11 блока

2.3 фиксации сбоев, входе 10 блока

2.2 фиксации сбоев. установятся нулевые потенциалы, а на выходе 12 блока 2.2 фиксации сбоев и входе

11 блока 2.1 фиксации сбоев — еди— ничные потенциалы, на третьем входе элемента И 3.2 устанавливается нулевой потенциал, а на первом входе элемента И 3.2, четвертом входе элемента И 4.1 и пятом входе элемента

И 4.2 — единичные потенциалы. В результате ни один из блоков 2 фиксации сбоев и элементов И 3.4 не

1О срабатывает, что свидетельствует о ненарушении оптимальной части формы хранимого числа.

Повышение достоверности контроля устройством определяется обнаруже15 нием всех однократных и всех асиммет" ричных ошибок (при этом обнаруживающая способность по характеру является симметричной, а по закону распределения равномерной), а также точнос20 тью диагностирования при каждом сбое типа переход "0" в "1" на один разряд.

Предложенное устройство может

25 быть использовано для построения высоконадежных электронных запоминающих устройств (например, оперативных) в системах с высокими требованиями по достоверности хранения информации (например, в АСУ, ЭВМ), а также может быть установлено в системах с высоким уровнем помех.

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

1149261

ВНИИХИ Заказ 1895!35 ТиРаж 710 Подписное

Филиал ППН "Патейт" ° r.Óàãîðîä, ул.Проектяал, 4