|
| |
 |
Электронные компоненты Мануалы § 1.6. СХЕМЫ СРАВНЕНИЯ ДВОИЧНЫХ ЧИСЕЛ Пусть заданы два «-разрядных числа X и Y. Введем для них символические обозначения: X = Xt), Y = (у..... j/i), где хи Уп - старшие разряды. Соотношения между числами X к У описываются пятью функциями: F(X>Y) 0, если X Y, р Y)= О, если ХфУ 1, если X>Y, 1 1, если X = Г r:tyY-\< (Х<К)= fO, еслиХ>К, F(X > Г) - I у I F{XY) = 0, если ХЖ, 1, если X < У. (1.3) Легко заметить, что f{x > Г) = f{x < Г) и f{x < V)= /=-(Х > Г), поэтому можно рассматривать только три функции: f{x > Y), f\x = Y), f(x = К) и f (X < К). Далее не представляет труда установить, что F{X>Y) = F{X<Y).F(X==Y), F(X<Y) = - 7(Х>К)--(Х=Г), поэтому в качестве основных можно использовать либо функции f{x Ж) и (Х = Y), либо функции f{x < К) и f (X = К). Соотношения между числами в позиционных системах счисления, в которых вес любого старшего разряда больше веса любого младшего разряда, довольно просто могут быть установлены на основании последовательного сравнения их одноименных разрядов. Сравнение чисел можно производить, начиная как с младшего, так и со старшего разряда. Первый вариант сравнения чисел предпочтительнее, так как допускает более естественный способ наращивания их разрядности (от младших разрядов к старшим). Для описания схем сравнения двоичных чисел введем в рассмотрение функции- fn = fn(X. Y) = 0, если X > Г, 1, если X < Y, =ФЛА. п= р=™;;=;; (1.4) I 1, если X = У, гдеХ = (x„. xi), У = {Уп, --. У\), Хп и старшие разряды. Сравнение чисел будем производить, начиная с младшего разряда. Из соотношений (1.4) следует, что /„ф„=3. Табл. 1.1 задает функции Д и ф1 для одноразрядных двоичных чисел X и F (п = 1). Из данной таблицы следует,, что функции fi = Xiyv Фх = Xi®yi. (1.5) Таблица 1.1
Пусть теперь имеются функции fi и ф1 для младших разрядов Xi и Уи а числа двухразрядные, т. е. X = (ха, Xj) и F = (г/2, yi). Составим таблицу иетинности для функ- ций /2 и ф2, аргументами которых являются величины !и Фь Х2 И Уг (табл. 1.2). В строках с номерами i = 12, 13, 14, 15 значения функций не определены (/2 = Ф и Ф2 = Ф). так как функции Л и ф1 не могут одновременно быть равными 1 (/„ф„ = 0). Функция /2 = 1 при Х2 < У2 (старший разряд числа X меньше старшего разряда числа Y), а также при /1= 1 и Xj = у. Функция ф2 = 1 только при ф1 = 1 и Хг == У2- Из диаграмм Вейча (рис. 1.12), построенных на основании табл. 1.2, следует, что Рис. 1.12. Синтез схемы сравнения двоичных чисел h= ХУ V/i (Ч ® Уз), Фа = Фх (Ч @ У2) (1.6) (функция /а представлена не в минимальной форме). Если теперь составить таблицу истинности для функций fg и фз, аргументами которых являются величины /2. Ф21 Хз и уз, то она будет иметь такой же вид, что и табл. 1.2, а значит !з = ЧУз\/ h(x3®ys), Ч>з = к(хз®Уз)- (1-7) Из соотношений (1.5)-(1.7) следует общая рекуррентная формула fn = ХпУп V fn-3 {Хп ® Уп), Фп = Фп-1 (Хп ® Уп), (1-8) в которой необходимо задать значения fo и фо, равные О или 1. Из выражений (1.8) следует, что h = хгУг V/o (1 ® Уг), Ф1 = Фойх © «/i). Ф„ = ФоП(р®Ур). (1.9) Таблица 1.2 Поскольку значения функций (1.8) зависят не только от значений чисел Х и К, но и от значений /о и фо. то целесообразно для них ввести обозначения: fn = fniX, V/h), Фп = Фп(. Введем в рассмотрение также функцию . gni. Уffo,4>o)4niX,Y/fo) - Ч>п{Х,Г/%). (1.10) Если в соотношения (1.9) подставить значения /о = 0. фо = 1 и п = I, то получатся соотношения (1.5), т.е. fi{X,V/0) = Jt, /,, Ф1(Л:, к/1) = XI 0 уи поэтому /„(X, к/о) = F{X < У), ф„(Х, к/1) = = F(X = к), gX, к/о. 1) = F{X > к). Подставив в выражения (1.9) значения Фо = /о==1и п = I, получим f,{X, Y/l)x,y,ylc,®y,==fAX. К/0)Уф,(Х, к/1). Из соотношений (1.6) следует, что f,{X, y/l)=X2y2yih{X,Y/0)\/q,,{X, к/1)](х,@/,) = = hix, y/o)VvAX, K/i). - - поэтому , fAX, y/i) = UX, к/о)Уф„(. K/i) = F(x<K), gX, K/l,l)-f(X>K). 0 1 2 3 [ 4 ] 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |