JPS6015967B2

JPS6015967B2 - 3-input series full adder capable of detecting overflow

Info

Publication number: JPS6015967B2
Application number: JP8777277A
Authority: JP
Inventors: 晃金政; 力男丸田; 淳友沢
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1977-07-20
Filing date: 1977-07-20
Publication date: 1985-04-23
Also published as: JPS5422136A

Description

【発明の詳細な説明】本発明は桁あふれ検出可能な３入力直列全加算器に関す
る。DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a three-input serial full adder capable of detecting overflow.

従来から用いられている直列全加算器は、２入力のみで
あり、従って、例えば、巡回形２次デイジタルフィルタ
を構成する場合等には、２入力列道全加算器が４個必要
である。Conventionally used serial full adders have only two inputs, and therefore, for example, when constructing a cyclic second-order digital filter, four two-input serial full adders are required.

また、従来の加算器では加算後の結果が桁あふれを起し
ているか否かを検出するには別個の付属回路が必要であ
る。本発明の目的は桁あふれ検出可能な３入力直列全加
算器を提供することにある。本発明の加算器は、講出し
専用メモリ（以下ＲＯＭと略称）と２個のフリップフロ
ップとを備え、加算すべき３種類の直列データと前記直
列データの符号ビット（以下ＭＳＢと略称）の位置を示
すタイミングパルスと前記２個のフリツプフロップの２
出力とを前記ＲＯＭの６入力とし、前記６入力のうちの
前記タイミングパルスを除いた５入力の２を法とする和
の出力と桁あふれを起したことを示す出力と桁上りを示
す２出力とを前記ＲＯＭの４出力とし、前記ＲＯＭの４
出力のうちの前記桁上りを示す２出力を前記２個のフリ
ツプフロップの２入力とするように構成したことを特徴
とする。Additionally, conventional adders require separate additional circuitry to detect whether the result after addition has overflowed. An object of the present invention is to provide a three-input serial full adder capable of detecting overflow. The adder of the present invention includes a read-only memory (hereinafter referred to as ROM) and two flip-flops, and includes three types of serial data to be added and the position of the sign bit (hereinafter referred to as MSB) of the serial data. and the timing pulse indicating 2 of the two flip-flops.
The output is the 6 inputs of the ROM, and the output is the sum of the 5 inputs modulo 2 of the 6 inputs excluding the timing pulse, the output indicating that an overflow has occurred, and the 2 outputs indicating a carry. are the 4 outputs of the ROM, and the 4 outputs of the ROM are
The present invention is characterized in that two outputs indicating the carry out of the outputs are configured as two inputs of the two flip-flops.

次に図面を参照して本発明を詳細に説明する。Next, the present invention will be explained in detail with reference to the drawings.

以下の説明では、入出力デー外ますべて２の桶数表示と
し、最小重みビット（以下はＢと略称）が時間的に最初
にくるような直列データ形式とする。図は本発明の一実
施例を示すブロック図である。In the following explanation, all input and output data will be expressed as 2 bucket numbers, and the data will be in a serial data format in which the least weighted bit (hereinafter abbreviated as B) comes first in time. The figure is a block diagram showing one embodiment of the present invention.

参照数字１０は６４ワード×４ビットのＲＯＭ、参照
数字２０および３０はフリップフロツプである。ＲＯＭ
ＩＯ‘こ書込された内容を第１表及び第２・表に示す。Reference numerals 10 are 64 word x 4 bit ROMs, and reference numerals 20 and 30 are flip-flops. ROM
The contents written to IO' are shown in Table 1 and Table 2.

第１表第２表第１表及び第２表において、×・ｙ’Ｚ’ｌｃｎ−，及
び×ｎ−，は入力ビットを示し、ｓ．ＩＣｎ，次ｎおよ
びＯＦは出力ビットを示す。Table 1 Table 2 In Tables 1 and 2, x·y'Z'lcn-, and xn-, indicate input bits, and s. ICn, next n and OF indicate output bits.

第１表はＭＳＢの位置を示すタイミングパルスが“０”
の時のＲＯＭＩＯの内容を示したものである。In Table 1, the timing pulse indicating the MSB position is “0”
This shows the contents of ROMIO at the time of .

第１表において、出力ビットｓは、２を法とする５入力
の和になっており、出力ビットｌｃｎ及びＸｎは共に桁
上りを示すビットである。In Table 1, the output bit s is the sum of 5 inputs modulo 2, and the output bits lcn and Xn are both bits indicating a carry.

３ビットの和では、桁上りを示すビットに２ビットが必
要になる。For a 3-bit sum, 2 bits are required to indicate a carry.

また、出力ビットＯＦは、桁あふれを示すビットである
が、第１表では全て“０”となっている。これは、第１
表の内容（出力ビットＯＦ）を読み出すのは常に、３入
力の和を演算する途中であるので演算が完結しておらず
、桁あふれを起したか否か判定する必要がないからであ
る。第２表はＭＳＢの位鷹を示すタイミングパルスが“
１”の時のＲＯＭＩＯの内容を示したものである。Further, the output bits OF are bits indicating overflow, but in Table 1, they are all "0". This is the first
The reason why the table contents (output bit OF) are always read is that the sum of three inputs is being calculated, so the calculation is not completed, and there is no need to determine whether an overflow has occurred. Table 2 shows that the timing pulse indicating the MSB position is “
1” shows the contents of ROMIO.

第２表において、出力ビットｓは第１表と同一の内容で
ある。また、桁上りを示す出力ビットＩＣｎおよび幻ｎ
はすべて“０”となっている。さらに桁あふれを示す出
力ビットＯＦはその値が“１”の時には、桁あふれが起
ったことを意味している。なお、第１表及び第２表にお
いて、桁上りを示す出力ビットは２ビットのＩＣｎとめ
ｎを用いて表現される。In Table 2, the output bit s has the same content as in Table 1. Also, the output bit ICn and phantom n indicating carry
are all “0”. Further, when the value of the output bit OF indicating overflow is "1", it means that overflow has occurred. Note that in Tables 1 and 2, the output bit indicating carry is expressed using 2 bits ICn and n.

第１表では、５個の入力データビットであるＸ，Ｙ，Ｚ
，ＩＣｎ‐，及び汐ｎ‐，の２を法とする和の桁上り結
果がＩＣｎとぶｎに示されている。ここでＩＣｎ‐，及
び本ｎ‐，は共に１桁上りを意味している。５個の入力
データビットにうち“１”の数が０個、１個、２個、３
個、４個、５個の場合に対応してＩＣｎ及び本ｎの値は
それぞれ“０”及び“０”，“０”及び“０”，“１”
及び“０”，“１”及び“０”，“１”及び“１”，“
１”及び“１”として、桁上りを表現している。In Table 1, the five input data bits X, Y, Z
, ICn-, and shio n-, are shown in ICn and n. Here, ICn- and Honn- both mean an increase of one digit. The number of “1”s among the five input data bits is 0, 1, 2, or 3.
The values of ICn and book n are “0”, “0”, “0”, “0”, and “1” corresponding to the case of 1 piece, 4 pieces, and 5 pieces, respectively.
and “0”, “1” and “0”, “1” and “1”, “
Carry is expressed as "1" and "1".

従って、ＩＣｎ‐，及び本ｎ‐，の組合せで１桁上りを
表現していることになる。この表現は、ＩＣｎとぶｎを
入れ換えても良いことは言うまでもない。第２表のＩＣ
ｎ及び次ｎは連続するワードを区別するように共に“０
”の値が出力される。次に図の構成について第１表およ
び第２表を参照しながら動作を説明する。Therefore, the combination of ICn- and Honn- represents an increase of one digit. It goes without saying that in this expression, ICn and n may be interchanged. IC in Table 2
n and the next n are both “0” to distinguish between consecutive words.
” is output.Next, the operation of the configuration shown in the figure will be explained with reference to Tables 1 and 2.

第１表の入力ビットｘ，ｙ，ｚ，ＩＣｎ−・および本ｎ
‐，はそれぞれ図の入力端子２，３．４，５および６に
現われる。Input bits x, y, z, ICn- and book n of Table 1
-, appear at input terminals 2, 3, 4, 5 and 6, respectively, in the figure.

また、第１表の出力ビットｓ，ｌｃｎ，沙ｎおよびＯＦ
はそれぞれ出力１１．１３，１４および１２に対応して
いる。入力端子１には、ＭＳＢの位直を示すタイミング
パルスが入力される。今、３つの直列データｘ，ｙ，ｚ
のＢＢがそれぞれ入力端子２，３および４に入力された
時には第１表に従い出力ビットｓ，ｌｃｎ．汝ｎおよび
ＯＦが出力１１，１３，１４および１２として生じる。Also, the output bits s, lcn, san and OF in Table 1
correspond to outputs 11, 13, 14 and 12, respectively. A timing pulse indicating the MSB phase is input to the input terminal 1. Now, three serial data x, y, z
BB are input to input terminals 2, 3 and 4, respectively, output bits s, lcn. Thy n and OF result as outputs 11, 13, 14 and 12.

但し、１ビット前は直前のデータのＭＳＢであるので、
第２表に従いビットｌｃｎおよび幻ｎは共に“０”であ
るから上記時点では入力端子５．６には共に“０”が入
力される。出力ビットｌｃｎおよび松ｎに対応するＲＯ
ＭＩ０の出力１３および１４はそれぞれフリツプフロツ
プ２０および３０により１ビット遅延された後ＲＯＭＩ
Ｏの入力端子５，６に帰還される。ここで、あるビット
位置で発生した桁上げは、そのビットより１ビット上位
のビットに伝達する必要がある。すべて述べた通り、こ
こではデー外ま直列でかつＢＢが最初に光るような系列
を仮定している。したがって、第１図に示した１ビット
遅延を与えるフリッブフロツプ２０及び３０はあるビッ
ト位置で発生した桁上り情報を１ビット上位のビットに
伝達する働を行なつている。３個の直列入力データｘ，
ｙ，ｚのＭＳＢが到達するまでＲＯＭＩＯは表１の全て
の出力ビットを読み出す。However, the previous bit is the MSB of the previous data, so
According to Table 2, bits lcn and phantom n are both "0", so at the above-mentioned time point, "0" is input to both input terminals 5.6. RO corresponding to output bits lcn and pine n
Outputs 13 and 14 of MI0 are delayed by 1 bit by flip-flops 20 and 30, respectively, and then output to ROMI.
It is fed back to input terminals 5 and 6 of O. Here, a carry occurring at a certain bit position needs to be transmitted to the bit one bit higher than that bit. As mentioned above, here we assume a series in which the data is serial and the BB lights up first. Therefore, the flip-flops 20 and 30 which provide a one-bit delay shown in FIG. 1 function to transmit carry information generated at a certain bit position to the bit one bit higher. 3 serial input data x,
ROMIO reads all output bits of Table 1 until the MSB of y,z is reached.

最後に３個の直列データｘ．ｙ．ｚのＭ旧Ｂがそれぞれ
入力端子２，３および４に入力された時には、ＲＯＭＩ
Ｏ‘ま第２表の全ての出力ビットを読み出す。Finally, three pieces of serial data x. y. When M old B of z is input to input terminals 2, 3 and 4 respectively, ROMI
O' Read all output bits in Table 2.

この時点では、ＭＳＢの位置を示すタイミングパルスが
入力される入力端子１は“１”となっている。仮に桁あ
ふれが起った場合には、ＲＯＭＩＯの出力１２が“１”
となり、出力端子８に出力される。またＲＯＭＩＯの出
力１１には第２表の出力ビットｓが読み出され、出力端
子７に出力される。次に桁あふれについて具体例を挙げ
て説明する。At this point, the input terminal 1 to which the timing pulse indicating the position of the MSB is input is "1". If overflow occurs, ROMIO output 12 will be “1”.
and is output to the output terminal 8. Further, the output bit s of Table 2 is read out to the output 11 of the ROMIO, and is output to the output terminal 7. Next, overflow will be explained using a specific example.

入出力データを２の橘数表示された４ビットで表わし、
例えば、次式のような加算を考える。上式においてカツ
コ内は左記の２進符号をＩＧ隼数で表わしたものである
。上式の正しい加算結果はＩＧ錘数（十１０）であるが
、２進４ビットでは表わせず、この結果出力ビットを入
力データと同じように４ビットで表示すると、１０１０
（一６）と見なされてしまう（すなわち、桁あふれを生
じる）。この例では、桁あふれを起こす場合を示したが
、もちろん３個のデータの加算結果が４ビットで表現さ
れる値の範囲内（一８〜十７）にあれば、桁あふれは発
生せず正しい加算結果が得られ′る。桁あふれを示した
か杏かを示す第２表のＯＦの値は以下のように決定すれ
ば良い。前述の例を考えると、３個のデータの和を考え
ており、各々の値は−８から十７の範囲内にあるから３
個のデータの和は−２４から十２１の範囲に存在する。
この和の値を表現するには、データ長を２ビット増加し
６ビット分用意すれば良い。この時、体述の例の演算は
以下のようになる。上式において、Ｘ．Ｙ及びＺの２進
符号は、符号ビットが２ビット分拡張されて表現されて
いる。Input/output data is represented by 4 bits represented by the number 2,
For example, consider addition as shown in the following equation. In the above formula, the part inside the box is the binary code shown on the left expressed as an IG Hayabusa number. The correct addition result of the above formula is the IG weight number (110), but it cannot be expressed in binary 4 bits, and if this result output bit is expressed in 4 bits like the input data, it becomes 1010.
(16) (that is, an overflow occurs). This example shows a case where overflow occurs, but of course, if the addition result of three pieces of data is within the range of values expressed by 4 bits (18 to 17), overflow will not occur. Correct addition results can be obtained. The value of OF in Table 2, which indicates whether an overflow occurs or not, may be determined as follows. Considering the above example, we are considering the sum of 3 data, and each value is within the range of -8 to 17, so 3
The sum of the data exists in the range of -24 to 121.
In order to express the value of this sum, it is sufficient to increase the data length by 2 bits and prepare 6 bits. At this time, the calculation in the example is as follows. In the above formula, X. The binary codes of Y and Z are expressed with the code bits extended by two bits.

このように、入力データの符号ビットを２ビット分拡張
して考えれば正しい結果を得ることが可能となる。また
、加算結果Ｓについて考えると、上位３ビット（ＭＳＢ
十２、ＭＳＢ十１及びＭ峠Ｂの値が異なっていることが
わかる。これは、桁あふれを起こしたことを示しており
、桁あふれを起こしていない場合には、上位３ビットは
、同一の値となる。そこで第２表に説明に戻ると第２表
は入力データのＭＳＢの位鷹で使用されるが、仮想的に
（ＭＳＢ十２）ビット目までの演算を考えることにする
と、ＭＳＢビット目から（ＭＳＢ＋２）ビット目までの
演算は、第２表の代わりに第１表の内容を読み出すこと
になる。ここで（ＭＳＢ＋１）ビット目の入力データＸ
，Ｙ．Ｚは、符号ビット則ちＭＳＢと同一の値をとる。
この時、第１表の横の欄についてみるとＩＣｎ‐，及び
次げ，のグループの“１”の数と、ＩＣｎ及び次ｎのグ
ループの“１”の数が一致していればＳの値は保持され
、桁あふれは起こさない。これに対し、前者のグループ
の“１”の数と後者のグループの“１”の数が不一致で
あれば、ＭＳＢビットのＳの値と（ＭＳＢ十１）のＳと
値とは異なり、桁あふれを起きしたことを意味する。例
えば、第１表において、Ｘ＝Ｙ＝“０”，Ｚ＝“１”，
ＩＣｍ，＝“１”，本ｎ‐，＝“０”の入力の時、ＩＣ
ｎ及び次ｎの出力はそれぞれ“１”及び“０”であるか
らＩＣｎ‐，及び次ｎ‐，のグループの“１”の数とＩ
Ｃｎ及び本ｎのグループの“１”の数は共に１個で一致
するからＭＳＢビット目のＳとくＭＳＢ十１）ビット目
のＳは一致する。これは桁あふれ造きそてし・ないこと
を意味する。従って、上記の入力に対応する第２表のＯ
Ｆの値は“０”となることがわかる。また、第１表にお
いて、×＝Ｙ＝“０”，Ｚ＝“１”，ＩＣｎ−，＝“１
”，２Ｃｎ‐，＝“１”の入力の時、ＩＣｎ及び父ｎの
出力はそれぞれ“１”及び“０”であるから、ＩＣｎ−
，及び本ｎ−，のグループの“１”の数は２個であるの
に対し、ＩＣｎ及び本ｎのグループの“１”の数は１個
であり、両グループの“１”の数は一致しない。これは
桁あふれを起こしたことを意味する。従って、上記の入
力に対応する第２表のＯＦの値は“１”となることがわ
かる。このようにして、第２表のＯＦの値は決定される
。本発明を用いて上式を演算すれば、次のようになる。In this way, if the sign bit of the input data is expanded by two bits, it is possible to obtain correct results. Also, considering the addition result S, the upper 3 bits (MSB
It can be seen that the values of 12, MSB 11, and M Pass B are different. This indicates that overflow has occurred; if overflow has not occurred, the upper three bits will have the same value. So, returning to Table 2, Table 2 is used for the MSB digit of input data, but if we hypothetically consider operations up to the (12th MSB) bit, from the MSB bit to ( In the operation up to the MSB+2) bit, the contents of the first table are read instead of the second table. Here, the (MSB+1)th bit input data
,Y. Z takes the same value as the sign bit, ie, MSB.
At this time, looking at the horizontal column of Table 1, if the number of "1" in the groups ICn-, and the next, and the number of "1" in the groups ICn and the next n match, then the number of S The value is preserved and no overflow occurs. On the other hand, if the number of "1" in the former group and the number of "1" in the latter group do not match, the value of S of the MSB bit is different from the value of S of (MSB 11), and the digit It means that an overflow has occurred. For example, in Table 1, X=Y=“0”, Z=“1”,
When inputting ICm,="1", book n-,="0", IC
Since the outputs of n and order n are "1" and "0", respectively, the number of "1"s in the group of ICn- and order n-, and I
Since the number of "1"s in the group Cn and this n match is one, the S of the MSB bit and S of the MSB 11) bit match. This means that there will be no overflowing. Therefore, O in Table 2 corresponding to the above input
It can be seen that the value of F is "0". Also, in Table 1, ×=Y=“0”, Z=“1”, ICn−,=“1
”, 2Cn-, = “1”, the outputs of ICn and father n are “1” and “0”, respectively, so ICn-
The number of "1"s in the groups of ICn and book n- is 2, while the number of "1"s in the groups of ICn and book n is 1, and the number of "1"s in both groups is It does not match. This means that an overflow has occurred. Therefore, it can be seen that the value of OF in Table 2 corresponding to the above input is "1". In this way, the values of OF in Table 2 are determined. If the above equation is calculated using the present invention, the following will be obtained.

ＬＳＢからＭＧＢまでの４ビットに対応したビットをク
ロツク０，１．２および３と名づける。クロック０の時
点では、ｘ＝“０”．ｙ＝“１”，ｚ＝“１’、ｌｃｎ
−，＝“０”および松ｎ‐，＝“０”が入力され、第１
表に従いｓ＝“０”．ｌｃｎ＝“１”，父ｎ＝“０”お
よびＯＦ＝“０”が出力される。クロツク１の時点では
、ｘ＝“１へｙ：“１”，ｚ＝“０”，ｌｃｎ−，＝
“１”および勿ｎ‐，＝“０”が入力され、第１表に従
い、ｓ＝“１”．ｌｃｎ＝‘１１’ＬＺｎ＝“０”お
よびＯＦ＝“０”が出力される。The bits corresponding to the four bits from LSB to MGB are named clocks 0, 1.2 and 3. At clock 0, x="0". y="1", z="1', lcn
-,="0" and pine n-,="0" are input, and the first
According to the table, s="0". lcn="1", father n="0" and OF="0" are output. At clock 1, x = “1” y: “1”, z = “0”, lcn-, =
“1” and n-,=“0” are input, and according to Table 1, s=“1”. lcn='11'L Zn="0" and OF="0" are output.

クロツク２の時点では、ｘ＝“１’、ｙ＝“１’、ｚ＝
‘‘１’、ｌｃｎ−，＝“１”および沙ｎ‐，＝“０”
が入力され第１表に従いｓ＝“０”，ｌｃｎ：“１”．
次ｎ＝“１”およびＯＦ＝０が出力される。最後に、ク
ロック３の時点ではＸニ“０’、ｙニ“０”，ｚニ“１
’１，１ｃｎ‐，＝“１”および幻ｎ‐，＝“１”が入
力され、第２表に従いｓ＝“１”．ｌｃｎ＝“０”，汝
ｎ＝“０”，ＯＦ＝“１”が出力され、ＯＦ＝“１”と
なるから上述の加算結果は桁あふれが起ったことを示し
ており、上式の結果と一致する。以上述べたように、本
発明によれば簡単な回路で桁あふれ検出可能な３入力直
列全加算回路を提供できる。At clock 2, x = "1', y = "1', z =
``1'', lcn-,="1" and san-,="0"
is input and according to Table 1, s=“0”, lcn: “1”.
Next n=“1” and OF=0 are output. Finally, at clock 3, X is “0”, y is “0”, and z is “1”.
'1,1cn-,="1" and phantom n-,="1" are input, and according to Table 2, s="1". Since lcn="0", thy n="0", and OF="1" are output and OF="1", the above addition result indicates that an overflow has occurred, and the above equation match the result. As described above, according to the present invention, a 3-input series full adder circuit capable of detecting overflow can be provided with a simple circuit.

[Brief explanation of the drawing]

図は本発明の一実施例を示すブロック図である。１０・・・・・・ＲＯＭ、２０，３０・・…・フリツプ
フロツプ。The figure is a block diagram showing one embodiment of the present invention. 10...ROM, 20,30...flipflop.

Claims

[Claims]

1 comprises a 6-input-4-output read-only memory and two flip-flops supplied with two of the four outputs of this memory, and three types of serial data to be added and the position of the sign bit of the serial data. The timing pulse indicating , and the two outputs of the two flip-flops are the 6 inputs of the memory, and the output of the sum modulo 2 of 5 inputs excluding the timing pulse among the 6 inputs, and the timing pulse are If it indicates that the most significant bit is being supplied, it outputs a logical value of "0" or "0", otherwise it outputs a 2-bit pattern according to the bit values of the 5 inputs. If the timing pulse indicates that a bit other than the most significant bit is supplied, the logic value is "0"; otherwise, the logic value is set to "0" only when an overflow occurs. The overflow output that outputs the value "1" is the 4 output of the memory, and the 2 outputs that indicate the carry out of the 4 outputs of the memory are the 2 outputs.
1. A three-input serial full adder capable of detecting overflow, characterized in that it is configured to have two inputs of flip-flops.