JPH06149932A - 算術演算を含む論理式の表現方法 - Google Patents

算術演算を含む論理式の表現方法

Info

Publication number
JPH06149932A
JPH06149932A JP4294609A JP29460992A JPH06149932A JP H06149932 A JPH06149932 A JP H06149932A JP 4294609 A JP4294609 A JP 4294609A JP 29460992 A JP29460992 A JP 29460992A JP H06149932 A JPH06149932 A JP H06149932A
Authority
JP
Japan
Prior art keywords
logical
binary
arithmetic
integer
digit
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP4294609A
Other languages
English (en)
Other versions
JP2853790B2 (ja
Inventor
Shinichi Minato
真一 湊
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to JP4294609A priority Critical patent/JP2853790B2/ja
Publication of JPH06149932A publication Critical patent/JPH06149932A/ja
Application granted granted Critical
Publication of JP2853790B2 publication Critical patent/JP2853790B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Landscapes

  • Complex Calculations (AREA)

Abstract

(57)【要約】 【目的】 算術演算を含む論理式を簡潔に表現する。 【構成】 論理式f=2a+3bは入力変数a,bの
0,1の組合せに応じて0,3,2,5の値をとる。こ
れらの値0,3,2,5は3桁の2進数でそれぞれ00
0,011,010,101と符号化される。そして2
進数の各桁f2 ,f 1 ,f0 が入力変数a,bの値によ
って0,1のいずれの値となるかが、各桁毎に2値出力
の論理関数で表わされ、これらの論理関数は二分決定グ
ラフで表現される。

Description

【発明の詳細な説明】
【0001】
【産業上の利用分野】本発明は算術演算を含む論理式の
表現方法に関する。
【0002】
【従来の技術】論理関数を計算機上で効率よく表現、操
作する方法として「二分決定グラフ」と呼ばれるグラフ
を用いた方法が提案されている(R.E.Bryant: "Graph-B
ased Algorithms for Boolean Function Manipulatio
n", IEEE Trans.Comput., Vol.C-35, No.8, pp.677-69
1)。図5は二分決定グラフの一例を示している。入力
変数a,b,cを中間節点として表わし、入力変数a,
b,cへの論理値0,1の代入を枝で表わすことによ
り、論理関数の値が終端節点に得られる。二分決定グラ
フを用いることにより、ある論理関数の論理反転や、2
つの論理関数の論理積、論理和の演算結果を表すグラフ
を効率よく生成できる。
【0003】二分決定グラフの一応用として、複数個の
論理変数、および論理積、論理和、論理反転を表す演算
子を組合せた論理式を入力とし、その論理式の示す計算
手順にしたがって、上記の二分決定グラフの処理方法を
適用し、その論理式全体が表現している論理関数の二分
決定グラフを生成することにより、論理式の恒真性判定
や等価性判定、包含性判定を行うことが従来より行われ
ている。
【0004】
【発明が解決しようとする課題】上記の二分決定グラフ
による論理式の処理方法では、0,1の2値の論理関数
のみを扱うため、加算、減算、乗算、大小比較等の算術
演算を含む式を扱うことができない。このため、例えば
「10個の論理変数の中で、1となっている変数の個数
が5より少ない場合には1を返し、5以上の場合には0
の値を返す論理関数」は、算術加算と算術比較演算を用
いれば、 x1 +x2 +x3 +x4 +x5 +x6 +x7 +x8 +x
9 +x10<5 と、簡潔に記述することができるが、論理積、論理和、
論理反転のみでは、このように簡潔に記述することはで
きない。
【0005】本発明の目的は、算術演算を含む論理式を
簡潔に表現する、算術演算を含む論理式の表現方法を提
供することにある。
【0006】
【課題を解決するための手段】本発明の、算術演算を含
む論理式の表現方法は、複数個の論理変数と整数値定数
と所定の計算手順からなり、ある定められた範囲内の整
数値を出力とする、算術演算を含む論理式の表現方法で
あって、前記出力の整数値を適当な桁数の2進数で符号
化し、該2進数の各桁が、前記複数個の論理変数の値に
よって0,1のいずれの値となるかを、各桁毎に2値出
力の論理関数として表すことにより、前記論理式を前記
桁数個の2値論理関数の組に分解し、該複数組の2値論
理関数を、二分決定グラフと呼ばれる論理関数の表現方
法により表現する。
【0007】
【作用】本発明では、複数個の論理変数を入力とし、あ
る定められた範囲内の整数値を出力とする整数値論理関
数の出力の整数値を、適当な桁数の2進数で符号化し、
各桁が入力の値によって0,1いずれの値となるかを、
各桁毎に2値出力の論理関数として表すことにより、複
数個の2値論理関数の組に分解し、分解された各桁の論
理関数を二分決定グラフで表現する。
【0008】図4はその一例を示している。論理式f=
2a+3bは入力変数a,bの0,1の組合せに応じて
0,3,2,5の値をとる。これらの値0,3,2,5
は3桁の2進数でそれぞれ000,011,010,1
01と符号化される。そして2進数の各桁f2 ,f1
0 が入力変数a,bの値によって0,1のいずれの値
となるかが、各桁毎に2値出力の論理関数で表わされ、
これらの論理関数は二分決定グラフで表現される。例え
ばf2 の桁は入力変数aが0の場合(入力変数bは0ま
たは1)と、入力変数aが1で、入力変数bが0の場合
には0となり、入力変数aとbがともに1の場合に1と
なる。
【0009】2つの整数値論理関数の論理積、論理和演
算は、2進数の各桁毎の論理積、論理和を計算し、演算
結果を表わす整数値論理関数を複数個の2値論理関数の
組として表現する。
【0010】整数値論理関数の論理反転演算は、2進数
の各桁毎の論理反転演算を行ない、演算結果を表す整数
値論理関数を複数個の2値論理関数の組として表現す
る。
【0011】2つの整数値論理関数間の算術加算、算術
減算、算術乗算は、2進数の各桁毎の論理関数の間の論
理演算を行ない、演算結果を表わす整数値論理関数を複
数個の2値論理関数の組として表現する。
【0012】2つの整数値論理関数が等しくなる入力の
組合せに対しては1、それ以外には0を返す整数値論理
関数は、2進数各桁毎の論理関数の間の論理関数の組合
せにより計算し、複数個の2値論理関数の組として表現
する。
【0013】2つの整数値論理関数f,gについて、f
>gとなる入力の組合せに対しては1、それ以外は0を
返す整数値論理関数は、2進数各桁毎の論理関数の間の
論理演算の組合せにより計算し、複数個の2値論理関数
の組として表現する。
【0014】算術論理式中のある1個の論理変数に対し
て、該論理変数が真のときは他の変数の真偽に関係なく
整数値1を返し、該論理変数が偽のときは他の変数の真
偽に関係なく整数値0を返すような整数値論理関数は、
複数個の2値論理関数の組として表現する。
【0015】算術論理式中の整数値定数に対して、論理
変数の真偽に関係なく該整数値を返すような整数値論理
関数は、複数個の2値論理関数の組として表現する。
【0016】
【実施例】次に、本発明の実施例について図面を参照し
て説明する。
【0017】図1は本発明の、算術演算を含む論理式の
表現方法を実施する装置のブロック図である。
【0018】本装置は、算術論理式データを読み込む入
力装置1と、入力された算術論理式データを記憶する算
術論理式記憶装置2と、算術論理式データと整数値論理
関数との対応関係を記録するための対応表記憶装置3
と、整数値論理関数の各桁と二分決定グラフとの対応を
記録するための整数値論理関数記憶装置4と、二分決定
グラフを操作、格納するための二分決定グラフ処理装置
5と、計算結果を出力するための出力装置6と、算術演
算を論理演算の組合せで実行する手順を具備し、全体の
制御を行う制御装置7で構成されている。
【0019】図2は算術論理式データを表わす解析木グ
ラフの例を示す図、図3は図2の算術論理式データを計
算して、整数値論理関数を生成し、二分決定グラフとし
て表わす過程を示す図である。
【0020】まず、入力装置1から算術論理式2a+3
bのデータ「2」,「×」,「a」,「+」,「3」,
「×」,「b」が入力され、これら算術論理式データは
図2に示すような解析グラフの形式で算術論理式記憶装
置2に格納される。次に、算術論理式記憶装置2に記憶
されている算術論理式データの表す計算手順にしたがっ
て、算術論理式データ「2」,「a」,「3」,
「b」,「2a」,「3b」,「2a+3b」に対して
制御装置7に具備されている算術演算手順を適用するこ
とにより整数値論理関数が順々に生成される。すなわち
算術論理式「2」に対しては最下位から2ビット目だけ
が1の値の整数値論理関数、算術論理式「a」に対して
は最下位ビットだけが0または1の値で、残りが0の値
の整数値論理関数、算術論理式「3」に対しては最下位
と最下位から2ビット目が1の値で、残りが0の値の整
数値論理関数、算術論理式「b」に対しては最下位ビッ
トだけが0また1の値で、残りが0の値の整数値論理関
数、算術論理式「2a」に対しては最下位から2ビット
目だけが0または1の値で、残りが0の値の整数値論理
関数、算術論理式データ「3b」に対しては最下位と最
下位から2ビット目が0または1の値で、残りが0の値
の整数値論理関数が順次生成される。最後に、算術論理
式「2a」,「3b」の生成された整数値論理関数に対
してビット毎に加算の算術演算手順が適用され、最下位
ビットと最下位から2ビット目と3ビット目が0または
1の値で、残りのビットが0の値の整数値論理関数が生
成される。このようにして生成された整数値論理関数は
複数個の二分決定グラフの組として、整数値論理関数記
憶装置4に格納される。算術論理式データと整数値論理
関数の対応関係は対応表記憶装置3に記録され、必要な
ときには即座に参照できるようになっている。次に、整
数値論理関数記憶装置4に格納されている整数値論理関
数に対して二分決定グラフ処理装置5により図3に示す
ような二分決定グラフが求められ、格納される。最後
に、二分決定グラフ処理装置4に格納されている算術論
理式2a+3bの二分決定グラフを各桁毎に論理式で表
現し、出力装置6から出力することにより、算術論理式
の真偽、正負、大小等の条件判定を行うことができる。
【0021】
【発明の効果】以上説明したように本発明は、算術演算
を含む論理式を二分決定グラフを用いて表現することに
より、通信装置や情報処理装置等の設計における性能や
コストを、従来よりも容易に評価することができ、装置
の性能向上、設計時間短縮が図れ、また、数理工学的な
各種資源配分問題にも応用できる効果がある。
【図面の簡単な説明】
【図1】本発明の、算術演算を含む論理式の表現方法を
実施する装置のブロック図である。
【図2】算術論理式データを表わす解析グラフの例を示
す図である。
【図3】図2の算術論理式データを計算して、整数値論
理関数を生成し、二分決定グラフとして表わす過程を示
す図である。
【図4】複数個の二分決定グラフの組により整数値論理
関数を表現して例を示す図である。
【図5】二分決定グラフの例を示す図である。
【符号の説明】
1 入力装置 2 算術論理式記憶装置 3 対応表記憶装置 4 整数値論理関数記憶装置 5 二分決定グラフ処理装置 6 出力装置 7 制御装置

Claims (1)

    【特許請求の範囲】
  1. 【請求項1】 複数個の論理変数と整数値定数と所定の
    計算手順からなり、ある定められた範囲内の整数値を出
    力とする、算術演算を含む論理式の表現方法であって、 前記出力の整数値を適当な桁数の2進数で符号化し、 該2進数の各桁が、前記複数個の論理変数の値によって
    0,1のいずれの値となるかを、各桁毎に2値出力の論
    理関数として表すことにより、前記論理式を前記桁数個
    の2値論理関数の組に分解し、 該複数組の2値論理関数を、二分決定グラフと呼ばれる
    論理関数の表現方法により表現する、算術演算を含む論
    理式の表現方法。
JP4294609A 1992-11-02 1992-11-02 算術演算を含む論理式の表現装置 Expired - Lifetime JP2853790B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP4294609A JP2853790B2 (ja) 1992-11-02 1992-11-02 算術演算を含む論理式の表現装置

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP4294609A JP2853790B2 (ja) 1992-11-02 1992-11-02 算術演算を含む論理式の表現装置

Publications (2)

Publication Number Publication Date
JPH06149932A true JPH06149932A (ja) 1994-05-31
JP2853790B2 JP2853790B2 (ja) 1999-02-03

Family

ID=17809978

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4294609A Expired - Lifetime JP2853790B2 (ja) 1992-11-02 1992-11-02 算術演算を含む論理式の表現装置

Country Status (1)

Country Link
JP (1) JP2853790B2 (ja)

Also Published As

Publication number Publication date
JP2853790B2 (ja) 1999-02-03

Similar Documents

Publication Publication Date Title
US11521129B2 (en) Processing device, accelerator, and method for federated learning
US11106437B2 (en) Lookup table optimization for programming languages that target synchronous digital circuits
CN112199707A (zh) 一种同态加密中的数据处理方法、装置以及设备
CN112200713B (zh) 一种联邦学习中的业务数据处理方法、装置以及设备
JP2008293034A (ja) タイミング攻撃を阻止する標準化されたモジュラべき乗を計算することにより復号メカニズムを実行する方法と装置
Bernstein et al. On the correct use of the negation map in the Pollard rho method
JP7292297B2 (ja) 確率的丸めロジック
Das et al. Hybrid recursive Karatsuba multiplications on FPGAs
Kapur et al. Mechanically verifying a family of multiplier circuits
CN113467752A (zh) 用于隐私计算的除法运算装置、数据处理系统及方法
JPS6314378B2 (ja)
JP3046611B2 (ja) トートロジーチェック装置
JP5175983B2 (ja) 演算装置
CN117650872B (zh) 一种NR Polar编码的简化实现方法及计算机可读存储介质
JP2853790B2 (ja) 算術演算を含む論理式の表現装置
JP3660075B2 (ja) 除算装置
JPS58129653A (ja) 乗算方式
Aistleitner et al. On sequences with exponentially distributed gaps
CN113472540B (zh) 生成密文的方法、装置、电子设备及存储介质
CN112764713A (zh) 随机数的生成方法和装置
JP2777265B2 (ja) 高基数開平演算装置
CN116308603B (zh) 用于确定目标产品的方法、装置、存储介质及处理器
CN120373488B (zh) 基于数据流分组线性变换的Shor算法的优化方法
Kasianchuk et al. The Method of Joint Execution of the Basic Operations of the Rabin Cryptosystem.
Nikolaos Stochastic Computing Architectures for Information Processing Systems

Legal Events

Date Code Title Description
FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20071120

Year of fee payment: 9

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20081120

Year of fee payment: 10

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20091120

Year of fee payment: 11

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20101120

Year of fee payment: 12

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20101120

Year of fee payment: 12

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20111120

Year of fee payment: 13

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20111120

Year of fee payment: 13

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20121120

Year of fee payment: 14

EXPY Cancellation because of completion of term