Бауэр Ф.Л., Гооз Г. Информатика. Том 1

Подождите немного. Документ загружается.

4.2. Двоичное кодирование

301

во внутреннем разборе

случаев

отражает

то, что в

начальной

школе

(для

десятичной системы) выражают словами „занимаем

funct*bi'/MM6e(bits

я, bits

Яйб

isc(a)

isc(b)

CO) bits:

ifS«O

then

€lse

then

binsub

(lead(a),

1ead(b))-H0)

then

binpred

(binsub

(lead

(а),

кайф))+<0>)

then

binsub

(Jead(a),

then

binsub

(lead(a),

lead(bV>

<1У

function

binsub

(a,

UtstrUg

\(a>b)

and nc(a) and

tsc(b)\)

•

h!l<.trirtft;

begin

isempty

(b)

then

binsub

•*•

pise

(last

(a)

L) and (ter

(fe)

then

binsub

postfix

(binsub

(lead(a),

lead(b)\

(last(a)-O)

and

(last(b)-l)

then

binsub

-a

binpred

(postfix(binsub

(lead

(a),

had

(b)),

0))

(/aj/(a)

and

(last(b)**O)

then

binsub

postfix

(bimub

(lead

(a),

lead

(b)),V)

(/as/ (a)

end

(to/ (6) =

then

binsub

postfix(binsub(lead(a),lead(b)),0)

ehd

Рис.

168.

единичку".

том,

как

быть

со

знаками

при

сложении

вычи-

тании

целых чисел,

см.

приложение

А.

Сравнение

на

равенство

., соотв.

.ф., для

натуральных

целых чисел

помощью вычитания может быть сведено

сравнению

с 0 в

смысле раздела 4.2.1,

стало быть

многократному простому

сравнению.

Сравнения

.^., .<., .>.,

.^. таким

же

образом

могут

быть

све-

дены

проверке знака.

Сравнение

двоично кодированных

слов

на

взаимное расположение

смыс-

ле лексикографического порядка

тоже

может быть сведено

вычитанию

про-

верке знака.

4.2.2.3.

Умножение

Осталось

ещё

объяснить,

как

выпол-

няется

двоичной арифметике умноже-

„эфиопским",

гз

v ^J

•fo

Рис.

164.

„Древнеегипет-

ским

крестьян-

методом.

ние.

„Быстрый" вариант обыкновенного

умножения (задаваемого подпрограммой

genilor

из 2.6.3 со

сложением

качестве исходной функции)

был

известен

уже в

Древнем Египте

(рис. 164).

Он

даёт

алгоритм

302 Гл. 4. Двоичные комбинационные и переключательные схемы

funct

muhmQnt

а, Ь со дЬО во)

Intl

Иа-0

then

else

odd a

then

muli((a-l)+2,b)xl+b

-lodd

then

mult(a+2,b)xl

flfi.

function mult

(a,

integer

0})

Integer

begin

a~0

then

mult

-v

else

odd(a)

then

mult« mult

{(a-1)

div

W»2+fc

not

odd

{a)

then

mu/i«

ты//(й

dlv

2,6)*2

end

После

перехода

двоичному представлению числа

получаем

funct

bmult

is(b\i9

а, Ы Ь

со be

(а)

со) Int:

Ifu-Ф

then

else

last

(a)-

then

bmttlt

(lead

(a),

last

(a)

-0

then

Jmu//

(Jead(a),b)x2

fi fl.

(йф))):/л/едег;

begin

isempty{a)

then

бши//«

eke

then б/ивЙ *

bmult(Jead(a),

b)*2+b

Dlast(<0-O

then Ьти//«

bmult(tead(a),

b)*2

function

bmu!t(a;

bltstrlng;

ft:

Integer

end

Наконец,

представляя

второй множитель

двоичном виде,

приходим

подпрограмме

funct bmmuhs(h\ts a, bits

со

isc(d)

А ис(4)

со) bits :

theh

last

(я)

-L

then

Atnairf

{binmult

{lead

{a),

{O),

U last

(a)-Q

«hen

b{nmutl(Jeai}(a),

6)+<O>

fi fl.

function

binmult

(a,

bitstring

Vi))

begm

V/seifi))

end

(йс(*))1):

fti

then

ЫптиЦ

else

then

buumdt

end

D/iu«(a)»O

then

binmult

<•

postfix

(binmult

(lead

(a),

b),

O),6)

4.2.2.4.

Операции с двоично представленными

последовательностями знаков

размеченными деревьями

Введённые

2.1.3.4

операции

для

сортов

string

(string)

lisp

(lisp)

никак

не

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

по-

Ниже Ь, как и Ып, — от binary. —

Прим.

изд. ред.

4.2. Двоичное кодирование 303

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

соответствующим образом (в

случае

принятого нами семираз-

рядного кода ISO — в семёрки).

4.2.3.

Арифметика

ограниченным

числом

разрядов

Наложим

теперь ограничение, что все рассматриваемые

•нами

натуральные числа не превосходят некоторого определён-

ного числа, скажем представимы с помощью не более чем k

двоичных разрядов и, стало быть, лежат в интервале от 0 до

— 1.

В таком

случае

рекурсивный алгоритм

binsucc

из

4.2.2.1

за-

вершается самое позднее после k воплощений; при условии-

предохранителе

length(u)

^ k его можно также задать явной

•формулой, которая получается последовательными подставка-

ми.

Если мы теперь перейдём от использовавшегося нами до

•сих пор двоичного кодирования, отвечающего обычному пред-

ставлению чисел без начальных нулей, к кодированию двоич-

ными

словами, которые дополнены „нулями" до полного &-раз-

рядного слова (см. рис. 33, прямой код), то это

будет

в точ-

ности

соответствовать определению, принятому в стандартном

алголе-68

(см. примечание к

bits

в табл. 4).

Поскольку

переход к числу, следующему за LLL ... L

==2*

—

— 1, выводит за рамки k разрядов, можно, чтобы

результат

оста-

вался в той же области, вычеркнуть „лишний" первый бит

(бит „переполнения"). Это приводит к 6-разрядному

цикличе-

скому

двоичному

счётчику;

например, для k = 4 мы получаем

подпрограмму, представленную на рис. 165

. Чтобы теперь пе-

рейти к общепринятой комбинационной схеме, рассмотрим ком-

поненты

щ =

lasl{u),

= lasl(lead(u)),

= last(lead(tead(u))),

tast{lead(lead(lead(u))))

параметра и и компоненты s

, S3, s

результата как само-

стоятельные переменные.

Из

исходной (нециклической) рекурсии

ясно,

что для пер-

вого ui, отличного от L, мы имеем s,_i = s,_

==...

= Si = О,

значением

же s,-

будет

L, a

(s,+i,

s,-+2, ...) совпадает с

(«ж, и,-4_2, ...). Таким образом, нам нужно просто в каждом:

Где

cyclesucc

— от

cycle

(цикл).

—

Прим.

изд. ред.

301 Гл. 4. Двоичные комбинационные и переключательные

схемы

разряде реализовать функцию полусумматора.

Для k = 4 по-

лучается комбинационная схема

на рис. 166, где для

единообра-

funct

cyclesuccm

(bits

е*length(u)-4

ъо) bitsl

\\\mlead(u)+(b

then

elsf

last(lead(lead(u)))~Q

then

lead

(lead

(lead(u)))

<L>

(0;

(0)

e\s1

last

(lead (lead (lead

(u))))

then

else

function

cyclesucc

(u:

bitslring

length

(и)=4));

bitslnng:

begin

then

cyclesucc

postfix

(lead

(u),V)

else

1ast(lead(u)~0

then

cyclesucc

-m

postfix

(postfix

(lead (lead

(и)),

L),

else

last

(lead (lead

(u)))

then

cyclesucc

-a

postfix

(postfix (postfix

(lead(lead

(lead(u))),L),O),O)

else

lasi(lead(tead(l(ad(u))))=O

then

cyclesucc

« postfix

(postfix (postfix

(

postfix

(empty,

L),

О), О),

else

cydesucc-e>postfix(posifix(poitfix(

postfix

(empty,

О), О), О),

С.

end

Рис.

165. Комбинационная

схема

четырёхразрядного (циклического) двоично-

го счётчика.

зия

последний разряд также представлен полусумматором,

в ко-

тором второй

вход с

постоянно установлен

на L.

Отметим,

что в

случае, когда

на счётном входе с

подаётся

вместо

L, мы

получаем тождественное отображение.

Выход пере-

носа и при

использовании данной схемы

как

циклического двоич-

ного счётчика является лишним; однако если объединить

две та-

НА

Й---Т

НА

Рис. 166.

кие

схемы вместе

так,

чтобы

выход

переноса одной

был

связан

со счётным входом другой,

то

снова получится схема цикличе-

ского двоичного счётчика. Таким образом можно сложить

схему

циклического двоичного счётчика

большим числом разрядов

из

„элементарных кирпичиков", например

из

четырёх-

или

восьми-

4.2 Двоичное

кодирование

305

Рис

167.

Четырёхразрядная комбинационная

схема

сложения.

разрядных счётчиков. Полусумматор

— это

предельный случай

одноразрядного двоичного счётчика.

Аналогичным способом может быть получена fe-разрядная

комбинационная

схема

для

операции перехода

предшествую-

щему числу, равно

как и для

сложения;

так, из

алгоритма

Ы-

nadd

(см.

4.2.2.2)

для k = 4

получается комбинационная схема

сложения,

показанная

на рис. 167.

Если дополнить

её ещё

одним полусумматором

разряде единиц

снабдить дополни-

тельным счётным входом

с (рис. 168), то мы

снова получим

„кирпичики",

из

которых можно складывать многоразрядные

НА

Лг

Ъх

НА

Рис.

168.

Четырёхразрядный „кирпичик" комбинационной схемы сложения.

Ф. Л.

Бауэр,

Г.

Гооз

306 Гл. 4. Двоичные комбинационные и переключательные схемы

комбинационные

схемы суммирования. Полный сумматор — это

предельный случай одноразрядной комбинационной схемы сум-

мирования.

случае

вычитания можно исходить из алгоритма

binsub

(см.

4.2.2.2),

однако fe-разрядную комбинационную

схему

вы-

читания

можно получить- и вычислив сначала обратный код

(двоичное дополнение со сдвигом) для вычитаемого (см. при-

ложение А), а затем произведя сложение. Для компенсации не-

обходимо добавить единицу в разряде единиц, стало быть,

вход

счёта надо установить на L („возврат" единицы, англ.: end-

around

carry').

Во

всех

этих примерах комбинационная схема получалась

как

результат

„развёртывания" рекурсии в пространстве. Они

показывают, что комбинационные схемы можно „вычислять" —

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

ректных

схем

на основе „разумных" спецификаций.

Если,

опираясь на комбинационные схемы /г-разрядного

сложения и вычитания, аналогичным образом реализовать опе-

рации

умножения или деления, то схемы получаются довольно

громоздкие. Впрочем, комбинационные схемы для умножения,

соответственно деления,

двух

восьмиразрядных или шестнадца-

тиразрядных двоичных чисел умещаются сегодня — в рамках

технологии сверхбольших интегральных

схем

— на крохотном

кристалле

(„чипе").

4.3.

Переключательные

схемы

Для переключательных функций и комбинационных

схем

существенно то, что переменные

могут

принимать различные

значения.

Изучая вопрос о том, как реализовать их с помощью

физических

устройств, мы до сих пор рассматривали комбина-

ционные

схемы лишь в статике, т. е. в состоянии покоя или

„успокоения".

Однако изменение значений переменных, кото-

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

времени,

не происходит мгновенно; представление о том, что

переключательная переменная мгновенно перепрыгивает от зна-

чения

О к значению L или обратно, является

сугубо

идеализи-

рованным.

На самом же

деле

значение параметра соответ-

ствующего сигнала изменяется не скачком. Это означает, что

лишь

по истечении некоторого определённого времени б^ досто-

верно

могут

быть определены значения на

выходе

комбина-

ционной

схемы, а в „переходный" период эти значения вообще

не

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

ализации

переключательных переменных — это задание так на-

Буквально: переносить из конца обратно (в начало). — Прим. изд. ред.

4.3.

Переключательные схемы

307

зываемых

моментов опроса, или точек отсчёта времени (см.

ниже).

Разумеется,

время

срабатывания

зависит

от

уровня

раз-

вития техники; если

пятидесятые годы

для

отдельного И-эле-

мента, реализованного

помошью релейных устройств,

оно

составляло

ещё 10~

с, то

сегодня благодаря применению тран-

зисторов

интегральных

схемах

это

время

уже

меньше

10~

с.

Для сложных комбинационных

схем

время срабатывания полу-

чается

по

существу

как

суммарное время прохождения сигнала

через отдельные элементы схемы.

Из

сказанного прежде всего

следует,

что при

фактическом

построении переключательных

схем

качестве одного

из важ-

ных факторов надо принимать

во

внимание временную

за-

держку. Однако

при

чисто функциональном описании

мы мо-

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

что в

комбинационных

схе-

мах временной задержки

нет. То

обстоятельство,

что в

течение

некоторого времени

выход

комбинационной схемы

не

определён,

обычно учитывают, вводя

временную

развёртку,

именно

фик-

сируя (равноотстоящие)

точки

отсчёта

времени.

Всякая пере-

ключательная переменная рассматривавшей лишь

точках

от-

счёта времени.

Поставленные перед необходимостью считаться

отличны-

ми

от

нуля временами переключения,

мы

„делаем

из

нужды

добродетель", переходя

духе

машинно-ориентированного

под-

хода

переменным памяти

(см.

3.6.4.3)

для

двоичных слов

символов.

4.3.1.

Переменные

памяти

для

двоичных

слов

Используя переменные памяти

для

двоичных слов, можно

повторительную рекурсию выполнять

форме простых повторе-

ний.

Классическим примером

их

применения служит

так

назы-

ваемый последовательный сумматор

(см.

4.3-2.1).

4.3.1.1.

Пример:

сложение

При

введении „переноса" итеративная версия „быстрого"

сложения

из

4.2.2.2

принимает

вид,

показанный

на рис. 169'.

Если значения переменной

включить

разбор случаев,

то

после некоторых упрощений придём

подпрограмме, представ-

ленной

на рис. 170.

Переходя

двоичному представлению,

по-

лучаем

для

^-разрядной циклической двоичной арифметики

Корректность этой программы следует

(см.

3.3.3

4) из

того,

что

выра-

жение

2 + ^Х (

+ и) при

повторениях остаётся

неизменным;

но

вначале

оно

равно 0+1Х04+В

+ 0) = А + В, а в

конце

г + t X (0 +

+ 0) = г.

То

что

окончание обеспечено, очевидно.

11*

со Л SO л В> 0 со) int:

T(var

int a, b, z, ii, t)>*,(A, B, 0,0,1);

whilea +

Ovfc+Ovfi+O

do (a, b, г, И, /) :»

if odd а л odd 6

then

((a-l)+2,(6-1)4-2,r+/x6, 1,2x0

П -lodd a л odd ft

then

(ан-2,

(ft-l)+2,2+rxfl+/.

0,2x0

D odd а л

-lodd

then

П ~iodd а л ~iodd b

then

0,2xr)

flod;

function add

(А,

В: integer

\()

var a, b,

2,ii,t:

integer:

begin

(a,-ft, z, Й, /):=(-4. B, 0,0,1);

while (a + 0) or (b + 0) or (ii + 0)

if odd (a) and odd(ft)

then (а, ft, z, tf, ():-

((a-1) div 2, (ft-1) div

2,z+/*ii,

1,2*/)

D not odd (a) and odd(ft)

then (a, ft, г. ii, t):=

(a div 2, (A-1)div2, z +

l*ii

+ t,

0,2*;)

D odd (a) and not »</</(/>)

then (o, 6, z, и. /):=

((a -1) div 2, й div 2, r +

l*ii

+ /.

0,2*/)

D not odd(a) and not odd(b)

then (a, fe, г, ii, ():=

((a div 2, b div 2, z +

/*ii,

0,2*/);

add -cz

end

Рис. 169.

funct

add&Q

соЛ>Ол£>0

со) int:

T(var

int a. ft, z, й. l):-(A, B, 0,0,1)}

while

a+Ovft+Ovw+O

do (a, ft, z, ii, 0

'•—

if oddoAOddfeAfl-l

then

D odd а л odd ft л u

••

then

(

_1)i2,

(ft-l)+2,z,

1,2x0

D —lodd а л odd ft л й

—

then

(й-т-2, (6-l)-i-2, z, 1,2x0

D -loddaAodd

Ьлц-0

then

(a*2,(*>-!)-!-2,z+f.

0,2x0

D odd а л ~iodd ft л ii ~ 1

then

((a-1)4-2, ft-r2,z, 1,2x0

И odd а л —lodd 6 л й-0

then

((a-l)4-2,6-r2,z+(.

0,2x0

D iodd а л —lodd 6 л й -1

then

function

add(A,

и:

integer

[(А а 0) and (B £ 0)|):

integer;

var a, ft,

z,B,t:

integer;

begin

(a,ft,z,

й,

0:=(Л.

В.

0,0,1);

while

(a + 0) or

(fc+0)

or (u + 0) do

if odd (a) and

odd(b)

and (w= 1)

then

(a, ft, z, ii, /);»

((a-l)div2,(ft-l)div2,

z +

1,2*0

оА/(л)

and odd(b) and (» = 0)

tnen (a, 6, z, u, I):—

((a -1) div 2, (6 -1) div 2, z, 1,2*0

D not odd (a) end o<W(ft) and (й-1)

then (a, ft, z, ii, 0:-

(a div 2, (fc-i)div.l f,

1,2*()

П not orfa"(a) and odd(b) and (ii->0)

then (a, h, z, ii, 0:-

(a div 2, (ft -1) div 2, z + /, 0,2*<)

D odd(a) and not oddlp) and (й-1)

then (a, ft, z, u, 0:=-

((a-l)div2, ft div 2, r, 1,2*0

П odd (a) and not odd(b) and (й*0)

then (a, ft, г. й, J):=

((a -1) div 2, fc div 2. г+/, 0,2*0

D not odd (a) and not odd(b) and (u -1)

then (a. ft, z, u. 0-"*

(a div 2, ft div 2, z + /, 0,2*0

D not odd(a) and not oddib) and

(й«=0)

then (a, ft, z, u, 0

(a div 2, ft div 2, z,

0,2*0;

add о:

And

Рис. 170.

•4

Ь .

jt^tt-LSu

«a "4.

funct

h'rtaddsi

(biU

A, bits

со

/«Jtf/A

(A) •*

length

(В)

со)

bits:

f(var bits

var bit fi):-

(Л,

В,

Ф,

0);

While

4=0

(a, b,

z, u)

last(a)

klast(b)

\.hu**\_

then.

(lead(a),

lead(b),

<L> + Z.

(last

(a)

= L

last

(i) ••

л u

(last

(a)

—

last

(b)

—

л й

—

then

(lead(a),

lead(b),

(0)+r,

(ta(a)-.|_

л/a»(6)»О

л6-0)

then

(lead(a),

lead(b),

<L> +

г,

О)

then

(lead(a),

lead(h),

(0>

;

Var

a. fc, Г .

r.'-'r

-J ; . ;.

;

begin

(IT,

*, г,

ii):=(A.

empty.

While

not

isempl)'(a)

(tast(a)t

then

(a,

(lead

(a),

((last

(a)

((last

(a)

((last

(a)

•then

(a,

('«"<*(«).

((/flrt(a)

((last

(a)

then

(a,

(lead(a),

(last(a)'

then

(a,

(lead

(a),

binadd

snd

й):-

and

(last(b)-

and

(«»0))

-0)

and

(last(b)

=•

and (u

L))

and

(Iast(b)-*O)

and

(u'-L))

г,й):-

lead(b),

prefix

(0,2).

•=

and

(to.«(fc)

O) and (tf-6))

0) and

(last(b)"

and (и

Oj)

and (te/(fr)<=0) and

(,«=

L))

й):-

:iead(b),prefix(L,2),

0) and

(Jas((b)

and

(#=0)

г, й):-

Uad(b).

prefix

(O.:),

O);

Рис.

171.

CO-

подпрограмму

binadd,

приведённую

на рис. 171 (см.

4.2.3;

держит

конце возможный „бит переполнения").

4.3.1.2.

Двоичные регистры и элементы задержки

Переменные

памяти

для

двоичных слов называются обычно

регистрами (задержки)

(рис. 172).

Используемые

binadd

при

построении

a, b и

построении

переменные

для

двоичных слов

с типичными „разовыми" операциями

а:—

lead(a)

и z :=

Символи-

ческое

изобра-

жение

Название

—

;

—

регистр

(общий)

нм-

регистр

сдвига

•н-

—

регистр

сдвига

а) только

заталкиванием

Столько

выталкиванием

Рис.

172. Символические изображения регистров.

310

Гл. 4 Двоичные комбинационные и переключательные схемы

Н-

г соответственно называются

регистрами

сдвига;

в пер-

вом случае имеем „выталкивание" из регистра сдвига, во вто-

ром случае — „заталкивание" в регистр. Что касается и, то это

переменная

для двоичного знака — двоичный

(тактированный^

или

управляемый

тактовыми

импульсами)

элемент

задержки

Символически

изображение

Формула

Название

я—НЕБ—

г = Da

элемент

задержки

(управляемый тактовыми ишальсами)

Рис.

173.

Символическое изображение элемента задержки.

(рис.

173). Там, где программист видит присваивание г:=а

инженеры

пишут г = Da У собственно элемента задержки „хва-

тает памяти" только до следующей точки отсчёта времени.

4.3.1.3.

Присоединение

элементов

задержки

логическим

элементам

Для соединений элементов задержки с логическими элемен-

тами справедливо несколько правил упрощения. В частности,

Рис.

174. „Протаскивание" элемента задержки через логические элементы.

справедливы закон коммутативности

законы дистрибутивности

(см.

рис. 174).

(Da) V (Db) = D(aV b)