Note: Descriptions are shown in the official language in which they were submitted.
Field of the Invention
The invention relates to computer engineering, and
more particularly to Fibonacci code parallel adders. It can
find use in computers where multidigit numbers in the form of
a Fibonacci code are -to be summed up.
Description of the Prior Art
Known in the ar-t is a combination-type adder in which
a summation of multidigit numbers in the form of a Fibonacci
code is performed and which adder comprises one-digit binary
adders, a signal distribution unit and AND and OR gates
(cf. the U.S.S.R. Inven-tor's Certificate No. 570,896, Int.Cl.
G06 f, 7/50, 1977 granted on August 30, 1977 to A.P. Stakhov,
et al).
There is an accumulating adder comprising complement
flip-flops, an adder modulo 2, AND and OR gates, and delays,
which adder is used to sum up multidigit numbers belonging to
Fibonacci number systems (cf. the U.S.S.R. Inventor's
Certificate No. 577,528, Int.Cl. G06 f, 7/50, 1977 granted
to A.P. Stakhov, et al).
There is also a Fihonacci code parallel added (cf.
the U.S.S.R. Inventor's Certificate-No. 577,528, Int.Cl. G06
f, 7/50, 1977) comprising augend and addend registers which are
designed to store the source codewords of the augend and
addend and the codewords of the intermediate sum and carry
resulted from the addition. The outputs of the registers are
coupled to the inputs of a logic unit which performs addition
and which is a
.~ ~
t~
multidigit parallel half-adder, The logic unit comprises a
plurality of AND and OR gates which are interconnected in
accordance with the used addition algorithm. During each
cycle of the addition process relating to a given pair of
numbers, the corresponding codewords of the intermediate sum
and carry are generated. The outputs of the logic units
are coupled to the da-ta inpu-ts of the registers and the code-
words of the intermediate sum and carry are applied to these
imputs for writing. The addition process includes a number of
cycles which are repeated until the carry codeword contains
O's. The adder also comprises a Fibonacci code minimizing
unit which is coupled to the augent register, thereby providing
for a reduction of a codeword contained therein to the mini-
mal form. An end-of-addition detector used to indicate the
end of addition produces a respective signal when the carry
codeword contains O's. The adder also comprises a monitoring
unit coupled to the register outputs and designed to check
whether a Fibonacci code is reduced to the minimal form
properly. The output of the monitoring unit produces a corres-
ponding signal when the codewords contained in the registersdiffer from the minima] form.
The known Fibonacci code adders have a low operation-
al speed since they ~unction in a cynchronous mode when the
control input of the adder receives short control pulses.
During each cycle of the addition process, the intermediate
sum and
- 3 -
~7;~3
car~7 cociewords axe formed which are sbored i~ the rer,isters
an~ ~he i~termeii-~te sum codeword i5 the~ reauced to the mini
~al form~ he next c~cle de~ls ~.ith the sum~ation of the stored
codewords of the intermediate sum and cax~.y, new cod~words are
then formed, etc. The process i~ repeated until the c~rry con-
tai~s O's a~d the su~ obtained corresponds to the minimal form.
ma~imal ~umber o~ cycles ~or the described ad~er is equal to
n wher0 n is the len~th o~ the augend and aaae~d i~ the form
of a Fibonacci code~
~ he length of a single addition cycle mus t be su~`ficient
for the intermediate or final result. of ad~ition to be reduced
to the minimal forrn under the most unfavorable conditions deter~
minecl by an expression ~~ ~1 9 where ~ 1 is the time requiIed
~or a~ elementary convolutiorl involving a group o~ p + 2 bit
positions, Thus; a maximal adQition time will be TmaX =
q'he described aadition pxocess rGquires ~hat parallel
hal~-adders be availa~le ~or each pair of ide~ntical bit posi~
tion o~ the augenc~ and addend~ said half-adQe.rs eaGh compri-
si~g an adde~ modulo ~ and an ~D gateO
'~he nv~be~rs belo~gi~a~ to ~ibonacci number sy~;tems make
it possible to create such a:~ algorithIn of aaditio~ f or
p-numbers in which the auge~d and addexld are first repres~nted
in a partiall,y devolved ~orm,, ~hich means tnarl a 1 in the ith
bit position o~ thc original ,aug~nd (a(ide~d) is replaced by 1 ' s
in ths (i ~ 'I)th anQ (i p ~ 1)th bit positions according to
the krLol!Jn ~elat,ioll describi~" ~ibonacci p-numbers:
$1~
~ p(~) - yp (k 1) ~ ~p (k - p - 1) (~)
wher~ ~p (k) is th~ weight of the ~th bit position~
~ Xter -the values of the augend and addend in the partially
~evolved form are placed into the corresponding regis~ers, the
augend is reduced to the minimal ~orm and 1's from the code-
word o~ the addend are tran,s~rred into tke a.ugend register
provided the value OI` the iden~i.cal bit posi.tion of t.he augend
is 00 Thus, conventional addition is replaced in the case of
Fibonacci number sys-tams by an operation in which the augend
and addend are reduced concurrently to the mi~imal form~
~ummary of the Inventio~
~ n object of the invention is to provi.de a Fibonacci p~code
parallel adder havin~ a lo~ic uniJ capab:l3 of -transP~--rilv
1Is ~rom a cer~ain bit posibion of the addend re~ister in-to
the identical "zero" bit position oi` the au~end registerO
Another object of the invention is to provide a Fibonac-
ci p-code paral.:Lel aader havi~g a register ca~able of st~xing
and processing data o~ the code~Nords of the augend and addend
so as to allow for ~ur~her reduction of the sum code~Jord to
the minimal ~ormO
T~leXe i5 aisclosed a Fibonacci p-code parallel adder Gom
~risi~g a~ augend xegister and an addenà register having their
outputs coupled to the data inputs o~ a logic unit which is
de~igned to perf~orm addition and has its output coupled to
~ ,~ ~
respec~ive data inputs of the au~end and addend registers,
arl e~d~of adcliti.orl detector and a monitoring ~nit having
their inputs coupled -to the outputs of the augend and addend
x~iste.rs~ a Fibonacc; p-co~e min;i.~nj.zing unit c.~u~led t~ t.
au~;end regi.s~er, according to the invention, a true output
of the au~end register and a true output of the addend regis-
ter are coupled respectivel~ to the inputs of the monitoring
unit an~ the er~d-o~-addition detec~or, a complement output
oX the addend register being coupled to a respective input
o~ tlrl6 Fibonacci p-code minimizin~ ~it so as to allow -that
input to receive a corlvolu-tion enabl~e signal relating to an
~ p -~1)th blt position of the unit whi.ch has its another
input and it output coupled respectively to the true output
and to a norlnalize signal input o~ t~e augend register, the
logic uni.t complising n rewrite AND gates which are used to
transfer a 1 from an ith bit position of the addend registex
to an ith bit pOSi~iOIl OI the augend register, containing a 0
first an~ second ir~uts of an ith r~write AND gate being
coupled respectively to a co~plement output o~ the ith bit
position of` the augend re~ister and ~o a true output of the
ith bit po&ition o~;the addend reg:Lster so that the condition
of the flip flops of the ith bit positions of the augend and
~d~erld-regis-ters carl be analyzed~ arl output of the ith rewrite
Al~D gate being coupled to the set input of the ith bit posi~ion
ol th~ augend register so that a 1 can be placed in tnat bit
7~3
positiorl, a~d -to che resec input of the ith bit position of
the adder~d register9 ~ia a del~y1 whereby that position can
ch~n~ f`ro~ the 1 ~tate to the O ~'~ate, the remaining i~pu'~s
of tne rewrite AND gates bein~ joined to~echer and coupled to
~a third irlput Or the ~iborlacci p-code minimizing unit and to
a control bus of the adcier 9 which is used to deli~er a long
control signal 7 where n is the E~ibonacci p-code length and
i = 0,'l~ n ~ 1~
rl'~e ~`ibonacci p-code parallel adder of the invention of-
- fers arl incleased speeà o~ operations~ ~verl under the most
~favorable conditions where two su~mands A and B, represented
as A = O 1 1 1 1 1 . ~ . an~ B = 0 1 1 1 1 1 1 ~ . 0 9 are
addedS a maximal addition tima Tma~ is equal to (~n ~ 2) ~
ere n is the length of the summands in the minimal form of
a ~ibon~cci p-code a~d ~1 is the rewrite time which is con-
sidered to be equal to the time t.aken by a~ elementaxy convolu
tion.
~ he logic unit.is realized as n ~D gates. This provides
for les~ex cost of the equipment and greater operational-r~
bility of ~he adder~
Description of the Drawi~gs
The i~l~ention will now be descri.bed -by way of example
~ith re~ere.nce to the accompar~ying drawings in ~ihich:
~ 'igure 1 is a Dlock diagIam o~ a l~i~o~acci p-code paral-
lel adder, accoIdlrlg to -the invention;
11 ~ 7 3 1~
Fi~uxe 2 ~ho~s block aiagrams of a lo~i.c unit 9 ~egis~ers
and a ~ibonacci p code mi~imizing u~it of the adder~ ~ccordi~g
~o the inventionO
De.scriptio.~ o~ t1le I~vention
. ~`he Fibo1laoci p-code paral~el adcler (~ig. 1) comprises an
auge~d regi~ter 1 and an a~de~d register 2 whi.ch store respec-
tive the original augend ancl addend represented in a ~ibonacci
p code and applied to original code write inputs 3~0 ~ txus
output 5 of' the augend renister 1 is coupled to an i~put of a
~ibonacci p-code minimizing unit 6 which has its multidigit
y~O ~ z~ ~ ~\ 7
~output coupled to a mult:;digit ~or~lization contro:l input o~
the augend register 1, thereb~ providing ~or th,e xeductio~ o~
a Fibonacci p~code contai~ed in the register 1 to the minimal
form. Another input of the unit 6 is coupled to a complemen~
output 7 of the adde~d register 2.~ The ~ibonacci p code mini-
mizing unit b iS designed to redu~e to the minimal ~'o.rm the
codewords contai~ed i~ the augend register 1~ which actio~ de-
pe~ds on the conditlo~ of the cor~espondi~g bit positio~s of
the addend register 2. A compleme~t output 8 of the auge~d re-
gister 1 and a trueloutput 9 of the addend register 2 are coupled
~ o
to the data inputs ~ the logic u~it ~ which is operated to
tra~sfer a 1 from an ith bit positio~ o~ the addend register 2
to a~ ith bit positio~ of -the auge~d register 1~ which co~tai~s
a 0. ~ne outout of the lo~ic urlit 10 is cou.pled directly to the
data input of the augend ra~ister 1 and to the data input of
the aadend re~ister 2 via a delay u~ he latter thexef`ore
~ ~ Z~13
introduces a delay between the rewrite signals received by the
addend register 2 and the augend register 1, with the result
that the adder operates ~ithout ambiguity. A monitoring
unit 12 operates to check whether the addition is performed
properly, while and end-of-addltion detector 13 produces a
signal acknowledging that a transient in the adder is terminated
and the values of the bit positions in the addend register 2
are brought to 0 and the augend register 1 contains a sum
codeword in the minimal form. The inputs of the monitoring
unit 12 and the end-of-addition detector 13, which are imple-
mented according to the U.S.S.P~. Inventor's Certificate No.
577,528, Cl.G06 f, 7/50, 1977, referred to above, are coupled
respectively to the true outputs 5,9 o:E the registers 1, 2.
A control bus 14 of the adder, which delivers a long
control signal, is coupled to a third input of the unit 6 and
to a control input of the logic unit 10. The length of the
control signal is selected to be sufficient for the cycles
of the rewrite operation to be performed in the logic unit 10
and for the elementary convolutions to he performed in the
Fibonacci p-code minimizing unit 6. The inputs and outputs of
the units 11, 12, 13, 6, 10, 1 and 2 are multidigit ones each
- having n bit positions, where n is the length of the register
1 or 2.
Figure 2 illustrates a block diagram of a portion of
the adder of the invention in the case when n-6 and p=l, where
p is the Fibonacci number. The apparatus of convention de-
sign labelled by reference numerals 12~ 13 is not shown in the
Figure.
X
~12~ 3
'~he augend register 1 compri~es five complement ~lip-flops
151 155 in accordance wi~h code bit positions from one to
five and an ~S ~lip~,~lop whi.ch is l~s~d to place the value of
the lo~ or~ler di~it of tho cod~ i~Lto the re~iscex 1. ~ s~
,output 5i ~` a flip-flop 15i ~ an :ith bit po~iti.on o.~ the
au~end register 1, where i - 0 7 1, 2 ~ iS an
ith output o~ a true multidigit output 5 of the ~egister 1
and is coupled to the inputs of the monitoring unit 12 and
the end-of-additio~ detectox 13 (I'~igo 1)~ A pluxality of reset
inputs 80 ~ ~5 (~ig. 2) of the flip flops 150 155 constitute
the compleme~t output 8 of the auge~ld xegister 1~ ~'he latter
also comprises six rewrite 0~ gates 160 ~ 165~,~`he output of
a rewrite OR gate 16i is coupled to the set .input of a
flip flop 15i, while a plurality of the inputs of the rewrite
OR gates 160 ~ 165 constitute the ori~inal code Y~rite input 3
of the register 1c
'l~he ~ibonacci p-code mi~imizing unit 6 comprises five co~-
volution ~D ~ates 171 ~ 175 a~d a convolutioIl 0~ gate 18
which is i~serted to the low~order bit position a~d has its
inputs coupled to the outpu-ts of AN~ gates 171, 172, arLd
has its output coupled to the reset input o~ Ghe flip-flop
150 ~ the low~order bit position of the xegister 1,
~ he logic unit 10 comprises six rewrite A~D gates
190 195, while the addend re~ister 2 comprises six ~S flip-
~flops ~0~ ~ 205 YJhich have their reset inputs coupled to the
outputs of the corresponding delays 210 ~ 215 of the delay
urLit 11.
- 10 ~
,
1~ ~73~3
In the lo~ic unit 10~ a first input o~ the re~ri-te ~ID
~ate 19i is coupled to the co~plement output 8i of` the flip-flop
15i of the register 1 ancl to an input o~ the convolution AND
gate 17i of ~he ~ibo~acci p~code minimizi~g u~it 6. ~ second
input o~ the convolutio~ A~D ~ate 17i is coupled to a true
output 5i 1 ~ the flip flop 15i 1 of th.e re~ister 1 a~d to a
thi~d input o~ the convolution A~D gate 17i~1. The next i~put
o~ the convolution i~D gate 17i is coupled tO the complement
output of the flip~flop 20i o~ the addend register 2 whose true
output is coupled to an input of -the re~Jrite ~D gate 19i. The
control bus 14 o~ the adder is couyled to the remainin~ inputs
of the convolution ~ND gate~ 171 ~ 175 and the~rewrite ~ND
gates 191 195 ~he output of the convolution ~D gate 171,
with i equal to ~ and more, is coupled to the reset input of
the f~lip-flop 15i 2 ~ the re~ister 19 while the output o~ the
rewrite Ai~ gate 19i ls coupled to ~he remaini~g input o~ the
rewrite OR gate 16i and to the input of the delay 21i. ~'he
insertion of the rel~Jrite OR gate 16i into the ith bit positio~
of the au~end register 1 makes it possible to exte~d the input
o~ the flip-~lop 15i; t~is means that original da~a as ~Jell as
data ~rom the adde~d register 2 ca~ be placed into the flip-flop
15i ~ the augend r~gis~er 1~ A delay provided by the delay 21i
e~ceeds a t~ Yfro~ the re~Jrite OR gate 16i9 l~s a resul-t, the
~lip-flop 15i takes up a new s~ate so~ewhat earlier, as compa-
red to the ~lip-flop 20io
~1 27 ~ ~
The ~ibonacci p~code parallel adder operates in the fol
lowing ma~er. The ini~ial s~ate of the flip flops 150 ~ 155
of the augend register 1 and the flip-flop~ 200 ~ 205 of the
adde~d register 2 is the 0 s~ate and the control bus 14 OI ~he
Oadder receives zero potential.
Assume that two numbers A = 7 and ~ = 5 are to be added
whlch are xepresented i~ a ~ibonacci 1-code as follows.
Weight of bit
position 8 5 3 2
~o. of bit posi-
tion 5 4 3 2 ' 1 0
~ibonacci 1-code 0 1 0 1 0 0
of number i~
.
~`ibonacci 1-code o~ 0 1 0 0 0 0
number B
According to the al~orithm of the adaer 3 the numbers A~ B
in the partially devolved f`orm are applied to the ori~inal
code ~rite inputs ~4 o~ the r~gisters 1,2~
This conversion (devolution of the origi~al ~inimal codes
o~ the su~mands) is accomplished usi~g the respecti~e compo-
nents o~ tke adder circuitry. ~o this end, the adder illpU~S
correspo~ding to the bi~ positions i - 1 and i p ~ 1 receive
the orivinal ~a-ta on the condi-tion of the ith bit position.
- 12
7~
,. .
~ or example, with p - 1, th~ input bus cox~esporldir~ to
the bit position of the code with ~he wei~ht 8 is coupled.-to
the inputs of the blt positions wi.th the wei.ghts 5 and 3, with
the result that a certain Fibonacci doce represented as
~1 0 0 1 0 0 1 0 0 . . . assumes the form 0 1 1 0 1 1 0 1 1
. . . after the summa~ds are placed in the re~i~ters 1,2.
In the above-me~tioned example~ the augend (number A)
is applied to the input 3 of the au~end register 1 as
~ = O 0 1 1 1 1, whereas the addend (number ~) appears at
the input 4 OI the addend register 2 as B ~ O 0 1 1 0 O. The
codeword of the auge~d is applied, ~ia the rewrite OR gates
160 ~ 165, to the set inputs of` the flip-flops 150 ~ 155 of
the augend register 1, with the result that the flip-flops
150, 151~ 152- and 15~ of the respec~ive bit positions zeroS
one, two and three asswne the 1 state. ~`he codeword of the
a~dend is applied to the ~et inputs o~ the flip flops 200 ~
205 OI the addend register 2, wi~h the result that the flip-
-flops 202~ 203 of the bit positions two and three assume the -
1 sbate9 Thus, the adder is rea~y to perform aa~ition which
comme~ces wherl a logic 1 is applied to the control bus 14. q'his
results in`~he appeara~ce of a logic at the output of the
convolution AND ~a-te 174 of the Fibo~acci p-code minizing
u~it 6,^ since logic 1 9S are.present at the i~pu~$ of said
gate. ~nis mea~s that the convolution condition is satisfied
in ~hich the flip~flop 204 of' the addend register 2 assumes the
O state9 the flip-flop 15L~ of the au&end register 1 assumes the
- 13 -
.
~Z7;~
O state a~d the flip ~lops 15~, 152 assume the 1 staGQO A logic
1 ~rom the output of the flip-~lop 17~ is applied to the reset
input o~ -the flip-f`lop 152 ~vhich t~ls takes up th0 0 stat~, A5
a xesul~ 9 t~e complemellt ou~u~ 82 o~' the ~lip-~lop 152 produ
ces a logic 1, ~hile the true output 52 produces a lo~ic 0
which is applied to the counti~g input of the ~lip-flop 153
~hich thus assumes the 0 sGateO ~t the same time, the complement
output o~ the ~lip-flop 152 produces a logic 1 which is applie~
to a respective input o~ the ~D gate 192 so that the latter is
activated and its output produces a logic 1. ~his mea~s that
the rewrite condi-tio~ is satis~ied l?n which the flip-flop
22 of the addend register 2 assumes the 1 state and the.flip
flop 152 of the augend re~ister 1 assumes the 0 stateO This
lo~ic 1 is applied, via the second input o~' the rewrite 0~
gate 162 ~ the set input of `the flip-~lop 15~ of the augend
register 1 and that flip-flop again ass~es the 1 s~ateO A
logic 1 from the output of the rewrite A~ID ga-te 192 is applied
to the input of the,delay 212 and, after time ~21 has elapsed~
appears at the reset input oX the ~lip-flop 202 of the addend
register 2 so that the latGer assume,s the 0 stabe. As a xesult,
a 1 is ~ran~ferred ~'rom the second bit position o~ the addend
register 2 to the second bit position of the auge~d re~ister 1~
~'he del'ays ~10 ~ 215 are constructed so that the following ine-
gualit~ is sattisfied
~ 21 ~ ~ 6 ~ ~ 5 (2)
14
` l~
~273~3
where
~20 is the dela~ time i~t.roduced b~ the flip-flops
200 ~ 205;
~21 is the delay time introduced by the delays 210 - 215;
~16 is the delay time introduced by the rewrite OR gates
160 ~ 165;
r15 is the ~elay time introduced b~ the ~lip flops
150 155.
If the co~dition determined by (2) is not satisfied5 a
chasi~g effec^t migh~ occur.
Indeed7 if the fllp-flop 202 of the adde~d register 2
assumes the O state at the moment preceding that when the
~lip-~lop 152 assumes the 1 state, then the co~volution con-
dition for tbe seco~d bit position is satisfied and the
output of the convolution A~D gate 172 produces a logic 1
which is invalidO
As stated above9 the flip-~lop 153 assumes the O state
and its true output 53 produces a logic 0, with the result
that the flip-flop 15~ changes from the O to the 1 state~ ht
the same time, the compl~ent output 83 of the flip-~lop 153
pIoduce~ a logic 1 which is applied to the i~put of the re~rite
~D gate 19~e Now, the rewrite co~diGio~ ~or the third bit
position i~ ~atisfied and the output of of the rewrite AND
gate 193 produces a logic 1 which is applied, via the rewrite
OX gate 163, to the set input of the flip-flop 153 which thus
assumes the 1 state~ ~fter time ~21 has elapsed, the same
signal causes the flip-flop 203 of the addend register 2 to
assume the 0 sta~eO As a result, a 1 is transferred ~rom the
thirà bit position o~ the addend xe~ister 2 i~to the third
bi.t position of the au~end register 10
U NO~J ~ the ~lip-f`lops 200 ~ ~o5 of the addend register 2
are brought to the 0 state~ .
'rhe augend re~lsker 1 co~tains the sum codeword havi~g
a form tha-t diffcrs ~rom the mi~imal form (A + B =
0 1 1 1 1 1)o Therefore, it is necessaIy to reduce the sum
codeword to the minimal ~orm. 'l'his is done by mea~s of th~
Fibonacci p-code minimizin~ unit 6 ~/hich utiliæes the know~
technique a~alogous to that o~ a conventional adder as
follows:
0 1 1 1 1 1 ''
~ ,
1 0 0 'I 1 1
1 0 1 0 0 1
'l`he sign ~1~ denotes a convolution operation involvi~g
(i - 1)th, (i - 2)th and i-th bit positionsP
A table given below illustrates the above~described addi-
tion process~ 'l'he condition of the flip-~lops 150 ~ 155 and
200 - 205 o~ the registers 1~2 is described in relation to
the time inter~als which are selected to be equal to delays
~15~ r20 provided by one of the above~mentio~ed ~lip-flops.
~6 -
~1~73~;~
Addition stepSumma~d codeword
Original sw~nandsB = 0 1 0 0 0 0
. A ~ 0 1 0 1 0 0
-- -~
'Placing into registers 1,2 B = O 0 1 1 0 0
(partial devolutio~ of A = O 0 1 1 1 1
the codewords~
. .
Transfer of a 1 ~om re~ister 2 B _ O 0 1 1 0 0
~, .
to xe~;ister 1 A = O 0 1 0 1 1.
.
Trans~er of a 1 ~rom register 2 . B' = l
to register 1 A' = O O 0 1 1 1
Co~dition of re~isters Br'= O O O O O O
1,2 after the nu~ber A is A " = 0 1 1 1 1 1
~ I I
subject to convolutio~ and A " = A =
1ts are transf'erred from the
code~ord o~ the number B
to the codeuord o~ the ~umber
Fir~ step of convolutio~ of ~ " = O O O O O O
~he sum ... ~" A~' = 0 1 0 1 1 1
~he following steps of con- A~ = O O 0 1 0 1
volutio~ oî the number A i~ A' I = 1 0 0 0 0 0
the above-me~tioned time i~erv~ls ~1 A " - 1 0 1 0 1 0
~ 5 . _ _ _
Additio~ is complete A -~. B = A "
- 17
~ he table sho~s that the co~volution of the bit positions
a~d the txansfer o~ 1~s from the adde~d codeword to the
au~end code~ord are perfol~ed i~ steps of a ~iven succes~ion.
'l'he end of-addi.tion detector 13 produces a si~nal that
ack~owledges the end of the addition process. ~lhen a lo~ric 1
appears at its outpu~g this me~ns that the ~lip-~lops
200 ~ 205 of the addend register 2 co~tain O's snd the auge~d
register 1 contains the minimal f'orm of` the sum codeword~
The monitori~g unit 1~ is used to check -the adiition
process. Its output produces a logic 1 Ylhen the i-th bit pQSi-
tions of the registers 192 contain 1ts and the (i - 1)th and
~ 1)th bit positions o~ the registers 1,2 con-tain O's. When
such a situation occur (0 1 0 in the register 1 and 0 1 0 in
the re~ister 2), a ~ist~ke is akno~iledged.
The adàition operation is maQe more ra~id and the
qu~ntity of the required e~uipment is reduced, as new couplings
are introduced and ~h~ both summands are represented in the
f`orm diff'erin~ f'rom tne standard one. ln the adder of t~e
inve~ion, the addi~i.on is perfor.med in asynchronous way and
consists in a rumber of o~erations de~lin~ with the reductio~
of a ~ibonacci p-code of one of -the summands to the mini~al
form, the o-ther bei~g taken into consideration during the
raduc~ion. 1et the time necessary for a~ elemen-ta~y convolution,
includin~ conversion of the code . . . 0 1 1 . . . to the code
~ D 0 1 0 0 ~ 0 ~ , be ~1 In ~he ca~e of the adder of -the
i~ventiorl, the a~di~ion i~ performe~ u~aer the most unfavorable
conditio~s as to the speed o~ ppexation when the both sw~mands
. ~ 18
~lZ7;~.3
are represen-tea as ~ 0 1 0 1 0 . . O and B - 1 0 1 0 1 0
. . . .l~ the length Qf a codeword is e~ual to ~9 then the
maximal addition time '~max is equal to (2n - 2) ~1. On the
othsr ha~d, the prototype deals with a synchronous additio~,
~'he maximal number of addition cycles will be ~. The length
of an addition cycle i~ deter~ined by the time within which
the intermediate sum is subject to maximal convolutio~; said
time being equal to ~ , Then, the maximal addition time
'~'max will be e~ual to ~~ With n - 20, the operation
speed of the adder of the invention is 2,6 times that of the
known adders. The adder of the invel~tion comprises a lesser
quan~ity of components, as only one AND gate is necessa~y
for each bit position.
Since the addex of the inventio~ comprises the lo~ic -
unit 10 built around ~D gates and the augend register 1 built
around OR gates, and the addition is a ~rocess during which
the both su~nands are subject to concurrent normalization,
t~e operation speed is increased and the quantitv of the
required components o~ the adder is reducedO
. . .
~ ~. .
-= 19
