計測自動制御学会東北支部 第回研究集会

資料番号ステップ加減算手法を用いた高速冗長 進除算器の構成○工藤忠道 ，恒川佳隆○
岩手大学大学院 工学研究科

キーワード

冗長 進表現

高速除算器

連絡先

〒

工藤忠道，評価
盛岡市上田，まえがき，

こののであり，乗算や除算をはじめあらゆる算術演算がこれらの繰り返しで行われる．故にディジタルシステムの性能は加算器・減算器の処理能力に依存し，従来からこれらの高速化が望まれている．
また，現在は高速性だけでなく，幾何計算や統計処理及びネットワーク通信における情報セキュリティの分野などにおいては高精度演算の要求も高まっている．例えば情報セキュリティにおける暗号化問題では，安全基準の問題から桁以上の高精度演算が要求されている．一般的な加算の高速化手法として桁上げ先見があるが，この手法を（は演算桁数）であり，高精度では演算時間の増加が問題となる．
高速性と高精度性が同時に要求される問題に対応する数体系に岩手大学 工学部

行え，演算時間は桁数に依存しない．本報告では，算術演算の中で加算・減算は最も基本となるも用いても演算時間は加減算器表現がある ．

数系では桁上げが 桁のみで各桁並列に加減算を表現の一種である冗長 進数を用いた除算の検討を行う．これまでに，内部演算に冗長 進数を用いた除算器が提案されている ．しかし，各演算の入出力を数としたシステムでの適用を目的とした除算器についてはまだ報告されていない．
本報告では，この数のシステムへの適用を考慮した，入出力に冗長 進数を用いた除算器を提案する．まず除算器の構成法として，高速性の観点から高木らが提案した高速除算用アルゴリズムに基づいて考察する ．次に，我々がこれまでに提案してきた 桁 ビットビット混合表現を用いた，符号変換器を必要としない高速加減算器の除算器への適用を試みる ．この場合，各行での演算を決定する制御信号の生成時間が影響し，本加減算器の高速性を活かせないという問題が生じる．
そこでこの加減算器を改良し， つのステップで演算を行う新たな高速冗長 進加減算器の構成法を提案する．これによりハードウェア量の増加を抑えながら，より高速な加減算器が実現できる．さ
らに，商を求める際に部分剰余の冗長性から生じる問題点を示し，これに対処するための除算器の構成法を提案する．最後に，本除算器の構成法に対して設計システム

により設計及び評価を行う ．その結果，符号変換器を使う従来の加減算器を適用した除算器に対し，倍以上の高速化が可能となることを明らかにする．
このアルゴリズムをみてわかるように，部分剰余の上位 桁を参照するだけで商の各桁を決定で高速除算アルゴリズム

きる．各行の演算を決定する制御信号である商の本章では，除算器に適用するアルゴリズムを述

各桁を生成する回路の構成においてまず，従来のべる．これまでに，冗長 進表現の特長を活かした桁 ビット表現

高速除算アルゴリズムが提案されている ．まず，て示す．論理式は以下のようになる．

を用いた場合についこのアルゴリズムに用いる変数を定義する．
入力の演算数（被除数
入力の演算数（除数
出力の商（）））

商の小数点 桁目回目に得られる部分剰余

上記の論理式に基づいた構成を図に示す．

一方，我々が提案した 桁 ビット表現を用いた場合の論理式は，以下のようになる．の 桁目
桁数除算アルゴリズムを以下に示す．

＜ステップ ＞

上記の論理式に基づいた構成を図に示す．

これらの論理式から制御信号の生成時間を単位＜ステップ ＞

ゲート遅延に基づいて算出する．なお，単位ゲー
ト遅延とは，，，ゲートをとして換算したものである ． 桁 ビット表現した
場合はとなり， ビット表現した場合は ビットの参照で各値を検出できるため，となる．

新たな高速加減算器＜ステップ ＞

本章では，我々が既に提案してきた高速加減算器の特長を活かし，加算及び減算の並列性をより高めた除算器向け高速冗長 進加減算器を提案する．

従来の高速加減算器を適用した場合
本節では，既に提案してきた高速加減算器を除算器に適用した場合について考察する．この高速加減算器を除算器に適用した場合の演算の流れを図 に示す．この図からわかるように，逐次的に制御信号の生成及び加減算を繰り返す形となっている．従って，本加減算器を除算器に適用した場合，行の遅延時間は加減算器の遅延時間信号の生成時間が加わるため，に，制御に増大する．

はを， はを示す．これらを，それぞれ ビット

で，と表記し，及びがの場合は，加算結果または減算結果が であることを示す．また，次新たな冗長 進加減算器の構成法のステップでの出力を決定するための下位桁の条

前節において，我々が既に提案してきた高速加件も求める

減算器を除算器に適用すると，加減算器の遅延時または．そして，加算または減算結果がになる条件を求める．これを用間に制御信号の生成時間が加わり， 行の遅延時間いることにより，次のステップでの演算を効率よが増加することを述べた．そこで，本節ではこのく行うことができる．加減算のステップ の計算規加減算器を改良し，新たな除算器向け高速冗長則を表 に示す．各変数を次のように定義すると，進加減算器の構成法を提案する．

セルの論理式は以下のようになる．

本構成法では，従来 つのステップで行われてい桁目の入力た加減算を つのステップで行う．ここで各ステッ加算時での 桁目の下位桁の条件プの演算を行うセルをそれぞれ セル， セル，加算時での 桁目の下位桁の条件が各値になる条件セルとする．本構成法では制御信号の入力は セルではなく セルで行い，加減算と制御信号の生成減算時での 桁目の下位桁の条件減算時での 桁目の下位桁の条件を同時に行う．また，各セルでそれぞれ異なる表現方法を用いることにより，各セルでの演算を効率よく行い，ハードウェア量の増加を抑える．以
下に本加減算器の各セルの構成法を示す．
ステップ では 桁 ビット表現された入力，）の結果
れぞれの各桁における加算（，及び減算（）の結果を，その範囲で同時に求める．ここでが各値になる条件
加算及び減算結果が＜加算部分＞かになる条件

＜減算部分＞＜加算・減算共通部分＞

上記の論理式に基づいた構成を図に示す．

次にステップ では セルの各信号と制御信号の入力を行い，桁上げが伝搬しないような中間桁上げまたは中間桁借り ，中間和または中間差を求める．以降，中間和・中間差の つを中間和，中間桁上げ・中間桁借りの つを中間桁上げと記述する． セルの演算時間は上式からとなり，制御信号の生成時間と同じであるため， セルの演算は制御信号の生成を待たずにに開始可能である．
加算時及び減算時の計算規則をそれぞれ表に示す，．ここで中間和に注目すると，中間和は セルで求めたから絶対値を，下位桁の条件から符号を容易に求められることがわかる．
そこで セルの出力は，中間桁上げには一般的な冗長 進表現（）を用い，中間和は従来とは異なる表現（で）を用いる．ここは中間和の符号が負になる条件を示し，は絶対値が になる条件を示す．
次に，制御信号がをのときは加算，に示す．

この論理式から遅延時間を算出すると，と表記し，のときは減算，そしてのときは演算をせず中間桁上げを ，中間和をとして出力する．以上から セルの論理式は以下のようになる．

上記の論理式に基づいた構成を図が影響してととなる．しかし，これらの値はセルの演算開始までに生成可能であるため， セルの遅延時間は実質である．

最後にステップ では セルで得られた中間桁上げ，中間和に対してを計算し，加減商を決定する際の問題
本除算器に適用する 章のアルゴリズムは，部分剰余の上位 桁（整数部 桁と小数部 桁）の符号を検出して商の各桁を生成する ．故に，このアルゴリズムを適用するには部分剰余の整数部が桁で出力される必要があるが，部分剰余に冗長進数を用いているため， 桁で出力されない場合もある．この場合，商生成の際に正しい商が選択されないため，部分剰余生成において整数部を桁で出力するための対策が必要となる．
算の結果を 桁 ビット表現で得る．

セルの計算規則を表 に示す．この計算規則に基づいたセルの論理式は以下のようになる．

部分剰余の整数部部分剰余を ，除数を とすると， 章のアルゴリズムを用いた場合，の関係が成り立つ ．

これは，例えば整数部 桁目が の場合， 桁目は必ず となることを示す．つまり整数部はとなり，と表現できる．同様に，整数部 桁目が の場合
上記の論理式に基づいた構成をに示す．

この論理式から遅延時間を算出すると，る． セルと セルの遅延時間が共には 桁目は必ず になり，となであるた部分剰余の整数部をと表現できる．従って，に，をに変換することで整数部を 桁に変換できる．

め，本提案の加減算器の演算時間は従来の高速加減算器と等しいとなる．また，本提案の加減算加減算器整数部の構成器を適用した場合の除算器の演算の流れは図 のような形になり，制御信号の生成時間は全体の演算時間に影響しない．従って，除算器 行の遅延時間は加減算器自体の遅延時間と同等となる．

本節では，前節で示した変換規則を適用した場合の加減算器整数部の構成を示す．この場合の構成は，図になる．図において，とは部分剰余の整数部の 桁を 桁に変換するため加減算器上位桁部の構成
本章では冗長 進数を用いた除算器に適用するための，加減算器上位桁の構成法を提案する．の回路である．この図では，前行の部分剰余をシフトした値を ，除数を ，生成される部分剰余をとし，除数の整数部は 桁とする．

である

ため，図より上位には桁上げは生じず，整数部 桁目以降は となる．図の構成では，セルの演算終了後に変換を行うため，演算時間が増加する．
そこで，図時に行うのようにセルの演算と変換を同セルを提案し，演算時間を削減する．

セルの構成
本節では，前節で示したセルの構成について述べる．まず，変数を以下のように定義する．

上記の論理式に基づく
この式よりとなり，セルの構成を図 に示す．

セルの遅延時間を算出するとセルの遅延時間と同じである．

前行の部分剰余の最上位桁
図 の セルからの中間桁上げ
図 の セルの中間和が負である条件

除算器の構成法

図 の セルの中間和が か である条件
下位桁からの中間桁上げ

本章では，除算器の構成について示す．構成はが である条件

図 のようになる．この図は演算対象となる被除部分剰余の整数部数 ，除数 及び商 が共に 桁の場合である．

セルの出力を求める論理式を以下に示す．

はじめに，各中間桁上げが になる条件を求める．

ここで， セルは商の各桁を求めるセルで，前行の部分剰余の上位 桁から求める．また， セルは小数部の各桁の部分剰余の生成を，セルは整数部の部分剰余を生成するセルである．

整数部の変換規則に基づいて式で表される．

求めると，以下の従来の加減算器適用時の構成
本節では，従来の冗長 進加減算器を除算器に適用した場合の構成法について述べる．
この場合の セルの構成は，図となる．なお，このセルで用いられる冗長 進加算器は，従来の 桁 ビット表現による冗長 進加算器である ．
また， セルの構成は 桁 ビット表現を用いているので，図となる．

用いることにより，セルと同じ遅延時間で整数部の変換も行うことができる．このため，従来の構成と比較して高速に演算を行える．

性能評価
本章では，除算器に対して性能評価を行う．

論理的評価
本節では，単位ゲート遅延に基づく評価を行う．
従来の加減算器を適用した場合は，冗長 進加算セルとセルの遅延時間を比較した場合，加算器の遅延時間と符号変換器，変換回路の遅延時間の和となるセルのほうが大きい．また，演算器の遅延時間がであるため，除算器 行の遅延時間は節の考察からとなる ．

一方，本提案の加減算器を適用した場合の遅延の流れが図 となり，除算器 行あたりではこの時間は，節から加減算器自体の遅延時間にセルの遅延時間に セルの遅延時間が加わる．

等しいことがわかる．従って，本提案の除算器は，従来の加減算器を適用した除算器と比較して，約本提案の加減算器適用時の構成倍の高速化が得られることになる．

本節では，本提案の高速加減算器を除算器に適評価用した場合の構成法について述べる．
この場合の セルの構成は，図てセルの構成は，図となる．そしとなる．本構成は 桁ビット表現を用いているため， セルの構成は図

本節では，設計システムを用いて評価を行う ．評価対象を消費電力，面積，ゲート数，最大遅延時間とし，桁数を桁からとなる．この図を見てわかるように本加減算桁まで変えて評価を行った．この結果を表 に示す．

器は符号変換器を必要としない．また，制御信号

なお，実用部品として用いたセルライブラリの設の入力は セルで行うため，これにより制御信号

計ルールはの生成と加減算が同時に行える．さらにテクノロジ社）であり，電源電圧はセルをスタンダードセル（とした．

この結果を見てわかるように，本提案の加減算器

参考文献を適用した除算器は，従来のものと比較してハードウェア量を約倍に抑えつつ，倍以上の高速化が得られていることがわかる．

高木直史 矢島脩三 冗長 進表現を利用した

あとがき

向き高速除算器，電子情報通信学会論文
本報告では，冗長 進数に基づく高速除算器の構

誌，，成法を提案した．まず除算器の構成法として，高速性の観点から高木らが提案した除算アルゴリズムの考察を行った．次に，我々が提案してきた 桁ビットビット混合表現を用いた高速加減算器を日野杉充希，恒川佳隆，三浦守

桁 ビットビット混合表現を用いた高速冗長 進加減算器，電気学会論文誌，改良した，新たな除算器向け高速加減算器を提案した．さらに，部分剰余の数表現の冗長性によりデータ通信株式会社

商が正しく選択されない場合があることを示し，これに対応した除算器の構成法を提案した．
そして，論理的評価と設計システムを用いた設計及び評価を行った．その結果，本加減算器を適用した除算器は，ハードウェア量を約倍に抑えつつ，倍以上の高速化が可能となることを明らかにした．
今後の課題としては本加減算器の除算器以外への適用や，本除算器を実際にシステムに適用した場合の検討が挙げられる．

恒川佳隆，日野杉充希，齊藤正人，虻川勝己，
三浦守

桁 ビット

ビット混合型高性能冗長進加算器とその乗算器への応用，電気学会論文誌，，