Устройство для вычисления позиционной характеристики непозиционного кода Советский патент 1987 года по МПК H03M7/18 

113

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

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

В йепозиционном коде (модулярный код, система остаточных классов) число X представлено остатками от деле- НИН (наименыпими положительными вы- 1етами } числа X на основания р, , р , ,.,, fi. кода, которые должны удовлетворять условию взаимной попарной простоты, т.е.

(f,-, ,). (3,.п„ j Ь i).

Для обеспечения возможности определить, в какой части диапазона |-| р ,

где Р. П р. , находится число X,

id вычисляют позиционную характеристику

вида

-т--Г (2;);.

Пр, (1)

г L J целая часть.

Для различных целей требуется различный диапазон позиционной характе- ри стики. При изменении г изменяется и диапазон позиционной характеристи ки. Очевидно, что диапазон D позици . h-1

онной характеристики равен D П f j ,

Известно, что число X в позиционной

системе счисления может быть представлено как

п

II х.В.-гР

п

Где В, - базисные числа, для каждого из которых справедливо

tUiPi

В; fj Ktnodf.),

(3)

Справедливость (3) достигается выбором m, при зтом 1 f m - i j, ; г - ранг числа, при котором

1 л

,X(mod Р„).

- Позиционную характеристику /i(IXlp вычисляют последовательно как

J (ixiM .

V I р„-, J

wi ik - - -- -p T

T IJr J

1г,(1х,,;).. (4,

Для вычисления 7..(|Х1р ) подставП Г|

ляют (2) в первое выражение (А),

(Ixi; )

j i-JfiSi-ilEu.

. (5)

гг,/f .B-iniiPhniiPn-1

Так как в (5) ft- -- - - --

целое число.

fh

П-1

- целое чисВп -1

ТгГ

- целое

по и, учитывая (3), }

число, можно (5) переписать в виде

п

i/JIXlJ ) - L x..,. (6)

(1

25

Так как О ,() Р , то ливо t

,Q

х, ,((|Xi; )(тоа Р Ui

или в другой форме

(lxtp ) - L x./i,

Ph-л

Так как Р, имеет взаимопростые делители р , р , .. ,р, , следовательно, процедура, вычисления (7) может быть распараллелена, т.е.

и.(1Х1р ) возможно представить в не- гпозиционном коде по основаниям р, :р4. . Р h-1 остатками Т;;, t« ,,..

тп 1 Т

; 2 х.. ix,ii,+x(ij:

1

тг

n riPnlfj

45

Г

nfinlp,-.

(8)

Учитывая свойства e(,n), (8) можно переписать в виде

f;Hx,.M;;Hx,Hp,.,x

1 r

v 5ip -V I-Г

Fi - p.h

X.

iPu-Jlft.

Pi Fn

55

Pi

(9)

miP n-1 Pn , / J т.к. i(modj5J,. следовательно, (9) принимает вид

, i(x,-xj

(,n-l). (10)

Применив (10) к (4), на (п-г+1)-м шаге получим совокупность остатков

. ПО основаниям р, , 2 ., р , которые и определяют пози1

циониую характеристику и

)

непозиционном коде. Так как диапазон значительно меньше диапазона

li,

1 +

то

f i t

совокуп- Tif не

преобразовать ность остатков I , 7Г представляет труда, Очевино, что минимальное значение .

Пример. р| 2, pj 3, р. 5, р 7. Р5 П. Р 2310; , , 6. На первом шаге вычисля 3

ют:

5

(,) - j-l(Xi-|Xjrj)-2l; ;

п

) nlr-n rl slPls

4 l/x -X ) --I 5 S n

Ha .основании fj, шаге вычисляют

:|(x,-|x,i;-2|;

n.

n

на втором

и на третьем шаге I

i M :-f« jv

11

n

)

ись

Зная

.(|хГр

J/J и

-г

3

Гр. (2):

например, воспользовавii,() .

Выходной код

о I 2 3456789 10

Выходной код

01234012340

Пусть , , , , . Тогда на первом шаге , 77 1,, втором - , 7Г О, 7 4; на третьем - , г 1. И окончательно

j(, т.е. 4j). З( Х РН) , или 1540 j(IX| J 1925 , a так.как , то позиционная харак-. теристика вычислена верно.

, или 1540 5 TjdXl)

1925, а так как X 1901, то позиционная характеристика вычислена верно.

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

Устройство содержит коммутаторы If блоки 2 преобразования по модулю, вычитатели 3, перемножители 4, блок 5 памяти, первый 6 и второй 7 регистры, преобразователь 8 кодов и мультиплексор 9. На чертеже обозначены информационные входы 10, первые 11, второй - четвертый 12-14 управляющие входы, выходы 15 устройства, а также выходы 16 второго регистра 7.

На входы 10 подаются коды остат- ков х, X, ,, ..,х числа X.

Коммутаторы 1 служат для переключения одной из двух групп своих входов разрядностью log2 j), где р - наибольшее по величине основание (в общем случае таким основанием может быть любое основание). Если на входе 12 присутствует уровень логического нуля, то на выходах коммутаторов 1 присутствуют коды, соответствующие кодам остатков на входах 10, а если на входе 12 присутствует уровень логической единицы, то значения кодов на выходах коммутаторов 1 соответствуют кодам на выходе мультиплек- сора 9 и на выходах 16 соответственно.

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

513

Вычислитель 3 является вычислителем по модулю р. и может быть реализован любым известным образом например комбинационньм, На его выходах образуется разность между числом, код которого сформирован на выходах коммутатора 1 , и числом, код которого сформирован на выходах блока 2 преобразования по модулю.

Перемножитель 4 осуп1ествляет пере- множеиие чисел по модулю р. и может быть выполнен любым известным образом, например комбинационным.

В блоке 5 хранится (n-l)(n-r+l) констант, причем в зависимости от кода на входах 11 на выходах блока 5 одновременно формируется п-1 констант,

В табл, 1 приведена зависимость формируемых блоком 5 констант от ко- да на входах 11 (котор1з1й является адПреобразователь 8 кодов формирует из г-1 остатков, соответствующих числу НД |Х IP ), позиционный код зтого

г г Y

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

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

Рассмотрим работу устройства для случая, когда блоки 1-5, 8,9 представляют собой комбинационные устройства.

166

ресом к строкеII в Жоторой записаны п-1 констант) для примера, рассмотренного выше.

Таблица 1

В т-абл, 2 приведена зависимость формируемых блоком 5 констант от кода на входах 11 для общего случая, I Таблица2

Б исходном состоянии на входы 10 подаются коды х, х,,,,, х остатков числа X, На входах 11 присутствует код числа , который является адресом к строке, состоящей из п-1 констант,

f.

Р2

Рп Рп-;

На вход 12 подается уровень О, Содержимое регистров 6,7 безразлично.

Через коммутатор 1,i на суммирующие входы вычитателя 3,1 поступает значение кода остатка х-, Код остатка Х|л через коммутатор 1 ,п поступает

713241

на вход блока 2.1 преобразования, который преобразует его по модулю f. и подает на вычитающие входы вычита- теля , на выходах которого образуется значение ,

.

Эта величина перемножается в блоI 1 1 ке 4.1 на константу ; L , которая

хранится в первой строке блока 5, По окончании переходных процессов в перемножителях 4 на вход 13 nocTjrnaeT импульс, под действием которого в первый регистр 6 заносится содержимое f5 перемножителей 4, На этом первый шаг преобразования заканчивается. В регистр 6 по окончании первого шага занесены коды IfjJ , ,,..,Ti остатков позиционной характеристики 0

(ixlf).

Во втором шаге преобразования на вход 14 подается импульс, под действием которого во второй регистр 7 записывается содержимое первого регистра 6, т.е. на выходах 16.l-16.n-l появляются коды значений If J,, ,...

30

, // |||1 соответственно.

На входах 11 появляется код числа 1, под действием которого код на выходе мультиплексора 9 соответствует коду на выходах 16.П-1, т.е.Т, . На выходах блока 5 формируется вторая строка констант35

1

4.-Яп-1 f Рп-1 I

1 Рпh-1

Pv,-

0.

На входе 12 появляется уровень 1, под действием которого коммут торы 1 переключатся и остаются в этом

состоянии до крнпа преобразования. По окончании переходных процессов в блоках 1-4, 9 на выходах блока 4.1 (,п-2) сформирован код

;.-i(;- :i7bri;,

Значения I J,, , / . И ,

О под воздействием импульса на вхо- де 13 заносятся в первый регистр 6,

На, этом второй шаг преобразования

даканчивается, и в первом регистре

6 хранятся остатки позиционной характёристики .i(|X|p)

,

5

0

0

5

0

5

0

5

16-8

Последующие шаги преобразования- аналогичнь второму шагу.

На (п-г+1)-м шаге преобразования получаются остатки И , 77 ,..., которые определяют позиционную характеристику , (|Х/1 ).

По окончании переходных процессов в преобразователе 8 на выходах 15

сформировано значение «р (|Х1р ) в поhзиционном коде. На этом устройство

вычисление позиционной характеристики заканчивает.

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

Для работоспособности устройства- прототипа необходимо основания упорядочить как ... р, . Для предлагаемого устройства такое упорядочение не имеет значения. Но для сравнения с прототипом упорядочим основания как Р, 7f, ...70 (в прототипе, как и в предлагаемом устройстве, основания одни и те же, а изменена только их нумерация, чтобы не изменять вьшеприведенный алгоритм). Выберем минимальное значение , при котором вычисленная позиционная

характеристика Т7„(|Х1о ) имеет

нимальный. диапазон и представлена двумя остатками Ti по модулям р и р. соответственно. Следовательно, диапазон позиционной характеристики (I X IP ) равен

- -- . -, rvb

но так как р р в предлагаемом устройстве равно р. в известном уст-. ройстве, то диапазон вычисленной позиционной характеристики в предлагаемом устройстве минимум в р , раз точнее, чем в прототипе,

Пусть, например, f 3, р„ 5, , р, 11, . ,

Для известного устройства диапазон

позиционной характеристики равен ;

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

1-1 I-1 I Г

I Ч1МЗ I . 1 Г I f.

Таким образом, предлагаемое устройство по сравнению с известным поз.h

913241

воляет более точно вычислять позиционные характеристики.

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

Устройство для вычисления позиционной характеристики непоэиционного кода, содержащее регистры, п-1 блоков преобразования по модулю (п - число оснований непозиционного кода),fO выходы каждого из которых соединены с первыми входами одноименного вычи- тателя, выходы которого подключены к первым входам одноименного перемножителя, блок памяти, П- выходов кото- 15 рого соединены с вторыми входами одноименных перемножителей, одноименные входы блоков преобразования по модулю объединены, отличаю- щ е е с я тем, что, с целью повы- 20 шения точнЬсти устройства, в него введены преобразователь кодов, мультиплексор и п коммутаторов, выходы первого - (n-l)-ro коммутаторов соединены с вторыми входами одноименных 25 вычитателей, выходы перемножителей подключены к соответствующим информационным входам первого регистра, г выходов которого соединены с соответствующими входами преобразователя 30

Составитель О. Ревинский Редактор Л. Веселовская Техред л.Олийнык Корректор И, Муска

--- ------------.--.------ - -...---.- ..

Заказ 2973/57Тираж 90 Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий П3035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 416-10

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

Изобретение относится к вычислительной технике. Его использование в системах обработки информации,-г представленной в непозиционных ко- дах, позволяет повысить точность вычисления позиционной характеристики. Устройство содержит блоки 2 преобразования по модулю, вычитатели 3, перемножители 4, блок 5 памяти и регистры 6,7. Введение коммутаторов 1, преобразователя 8 кодов и мультиплексора 9 обеспечивает более подробное вычисление позиционной характеристики. 1 ил., 2 табл. /SHт (Л 00 1C 4; О5 if