JP2011159174A - ロジスティック写像の演算装置 - Google Patents

Abstract

【課題】ロジステック写像の演算を高速で実行することが可能な演算装置を提供する。
【解決手段】ロジステック写像の桁数が６桁である場合に、６段、５列の加算器を備える配列型乗算器を用いてロジステック写像の漸化式を展開した「Ｘt＊notＸt＋Ｘt」の演算を実行する。この場合、第１段の各加算器に「Ｘt」のビット列であるｘ0〜ｘ5を入力することにより「Ｘt」の加算処理が実行さえる。従って、別途「Ｘt」を加算する処理を実行することなく、ロジステック写像を演算することができ、従来と対比して「Ｘt」を反転して「＋１」とする処理が不要となるので、ロジステック写像の演算速度を高速化することが可能となる。
【選択図】 図１

Description

本発明は、ロジスティック写像を演算する演算装置に係り、特に、演算速度を高速化する技術に関する。

従来より質の良い疑似乱数を生成するため、ロジスティック写像が用いられている。ロジスティック写像は、例えば、特開２０００−２５２７５１号公報（特許文献１）に記載されているように、漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」にて求められる。一般に、漸化式における入力値「Ｘt」は２進Ｎ桁の数値で示され、上記漸化式で求められる出力値「Ｘt+1」は２Ｎ桁（Ｎ＝６の場合には１２桁）の２進数となるので、上位３ビット目からＮ個のビットで示されるＮ桁の数値を出力値「Ｘt+1」としている。例えば、Ｎ＝６の場合には、２進１２桁の数値が得られるので、第４桁から第９桁までの６桁の数値を出力値「Ｘt+1」とする。この出力値「Ｘt+1」は次回の入力値「Ｘt」として用いられる。

上記の漸化式を演算する上で、右辺の「１−Ｘt」は、入力値「Ｘt」の２の補数であるから、反転してプラス１とすれば求められる。即ち、（１−Ｘt）＝（notＸt＋１）で示すことができる。

図５は、「Ｘt＝００１０１１」である場合の漸化式の演算手順を示す説明図である。上述したように（１−Ｘt）＝（notＸt＋１）であるから、（１−Ｘt）＝「１１０１０１」となる。そして、図５に示すように「Ｘt（１−Ｘt）」の演算を実行することにより、「００１００１０００１１１」を得ることができる。

また、漸化式はこれを４倍するので、演算結果の下位に「００」を付加し、更に、上位の２ビットの「００」を削除した結果、即ち、「１００１０００１１１００」が「４Ｘt（１−Ｘt）」の演算結果として得られる。この上位６桁である「１００１００」が出力値「Ｘt+1」となる。

また、上記の演算を高速に実行するために、配列型乗算器を用いることが考えられる。図６は、「Ｘt＝００１０１１」と「notＸt＋１＝１１０１０１」との乗算（２進６桁の乗算）を、６段、５列の加算器を有する配列型乗算器５１を用いて演算する手順を示す説明図である。

図６に示すように、この配列型乗算器５１は、第１段〜第６段にそれぞれ５個の加算器が設けられている。以下では、最上段を第１段、最下段を第６段とし、右端を第１列、左端を第５列として示すことにする。

上記の各加算器のうち、第６段、第１列の加算器が半加算器（ＨＡ）であり、それ以外の加算器は全て全加算器（ＦＡ）である。

全加算器（ＦＡ）は、図７（ａ）に示すように３つの入力、及び２つの出力を有しており、このうち上側からの入力をａ入力、右上からの入力をｂ入力、右側からの入力をｃ入力とする。また、下側への出力を和としてＳ（サム）出力、左下への出力を桁上がりとしてＣ（キャリー）出力とする。また、図７（ｂ）に示す如くの論理回路で示すことができる。故に、ａ入力、ｂ入力、ｃ入力に入力されるデータが全て１である場合には、Ｓ出力、Ｃ出力を共に１とし、１が２個存在する場合にはＳ出力を０、Ｃ出力を１とし、１が１個存在する場合にはＳ出力を１、Ｃ出力を０とし、１が存在しない場合（全て０の場合）にはＳ出力、Ｃ出力共に０とする。

また、半加算器（ＨＡ）は、図１２（ａ）に示すように、図７に示した全加算器（ＦＡ）のｃ入力が存在しない構成である。また、図１２（ｂ）に示す論理回路で示すことができる。従って、ａ入力、ｂ入力に入力されるデータが共に１である場合には、Ｓ出力を０、Ｃ出力を１とし、いずれか一方が１である場合にはＳ出力を１、Ｃ出力を０とし、１が存在しない場合（双方が０の場合）にはＳ出力、Ｃ出力共に０とする。

ここで、被乗算値である「Ｘt＝００１０１１」の右側の桁から左側の桁に向けて符号ｘ0〜ｘ5で示す。従って、ｘ0＝１、ｘ1＝１、ｘ2＝０、ｘ3＝１、ｘ4＝０、ｘ5＝０である。

また、乗算値である「notＸt＋１＝１１０１０１」の右側の桁から左側の桁に向けて符号ｙ0〜ｙ5で示す。従って、ｙ0＝１、ｙ1＝０、ｙ2＝１、ｙ3＝０、ｙ4＝１、ｙ5＝１である。

そして、図６に示すように、第１段、第１〜第５列の全加算器（ＦＡ）のａ入力には、「ｘm＊ｙ0」（但し、ｍ＝１〜５）の演算結果が入力される。また、「ｘ0＊ｙ0」の演算結果はＰ０として出力される。なお、図６中の括弧内の数字は演算結果の数値を示す。例えば、第２段、第１列の全加算器（ＦＡ）のｃ入力に入力される「ｘ0ｙ2(1)」の括弧内の数値である「１」は、「ｘ0＊ｙ2」の演算の結果が「１」であることを示している。更に、図６では乗算を示す記号「＊」を省略している。例えば、「ｘ0ｙ0」は「ｘ0＊ｙ0」を示す。後述する図２〜図４も同様である。

また、第１段、第１〜第５列の全加算器（ＦＡ）のｂ入力には全て「０」が入力される。更に、第１段の第１〜第５列の全加算器（ＦＡ）のｃ入力には、「ｘm-1＊ｙ1」（但し、１≦ｍ≦５）の演算結果が入力される。

一方、第２段、第１〜第４列の全加算器（ＦＡ）のａ入力には、第１段、第２〜第５列の全加算器（ＦＡ）のＳ出力が入力され、第２段、第５列の全加算器（ＦＡ）のａ入力には「ｘ5＊ｙ1」の演算結果が入力される。第２段、第１〜第５列の全加算器（ＦＡ）のｂ入力には、第１段の第１〜第５列のＣ出力が入力される。更に、第２段、第１〜第５列の全加算器のｃ入力には、「ｘm-1＊ｙ2」（但し、１≦ｍ≦５）の演算結果が入力される。

同様に、第３段、第４段、第５段における第１〜第５列の全加算器のａ、ｂ、ｃ入力に各種のデータが入力され、Ｓ出力、Ｃ出力を出力する。

更に、第６段の第１〜第４列の加算器（ＦＡ、ＨＡ）のａ入力には、第５段、第２〜第５列の全加算器のＳ出力が入力され、第６段、第５列の全加算器のａ入力には「ｘ5＊ｙ5」の演算結果が入力される。第６段、第１〜第５列の加算器（ＦＡ、ＨＡ）のｂ入力には、第５段、第１〜第５列のＣ出力が入力される。更に、第６段の第２〜第５列の全加算器（ＦＡ）のｃ入力には、第６段、第１列〜第４列の加算器（ＦＡ、ＨＡ）のＣ出力が入力される。

そして、第１段、第１列の全加算器（ＦＡ）のＳ出力をＰ１とし、第２段、第１列の全加算器（ＦＡ）のＳ出力をＰ２とし、第３段、第１列の全加算器（ＦＡ）のＳ出力をＰ３とし、第４段、第１列の全加算器（ＦＡ）のＳ出力をＰ４とし、第５段、第１列の全加算器（ＦＡ）のＳ出力をＰ５とし、第６段、第１列の半加算器（ＨＡ）のＳ出力をＰ６とし、第６段、第２列の全加算器（ＦＡ）のＳ出力をＰ７とし、第６段、第３列の全加算器（ＦＡ）のＳ出力をＰ８とし、第６段、第４列の全加算器（ＦＡ）のＳ出力をＰ９とし、第６段、第５列の全加算器（ＦＡ）のＳ出力をＰ１０とし、第６段、第５列の全加算器（ＦＡ）のＣ出力をＰ１１として、Ｐ０〜Ｐ１１からなる２進１２桁の演算結果が得られる。

そして、上述したように、上位３ビット目から６桁目までの数値を取り出して、出力値「Ｘt+1」とすることができる。図６に示す例では、Ｐ４〜Ｐ９までの６桁の数値が出力値「Ｘt+1」となる。

特開２０００−２５２７５１号公報

しかしながら、上述したロジスティック写像の演算方法では、「Ｘt」に「notＸt＋１」を乗じる構成としており、配列型乗算器を用いて乗算を実行する前に「Ｘt」を反転して「＋１」する加算処理が必要になる。

図８は、「notＸ0」〜「notＸ5」からなる６桁の２進数に、１を加算する演算処理を示す説明図であり、６個の半加算器１０１-1〜１０１-6を用いて逐次加算により、演算処理を行っている。この場合には、６桁分の半加算器チェーンに要する演算時間が必要になる。即ち、半加算器１０１-1による演算処理が終了した後に、半加算器１０１-2による演算処理を実行し、順次１０１-3〜１０１-6での演算を行うので、逐次型加算器を用いて加算処理するのであれば処理時間が大きくなる。また、ロジステック写像の桁数が、例えば１００桁、１０００桁と増大すると、この処理時間による遅れがより顕著となり、演算処理時間の短縮化を妨げていた。

本発明は、このような従来の課題を解決するためになされたものであり、その目的とするところは、ロジスティック写像を高速に演算することが可能なロジスティック写像の演算装置を提供することにある。

上記目的を達成するため、本願請求項１に記載の発明は、図２に示す第１実施形態、図３に示す第２実施形態及び図４に示す第３実施形態に係り、漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」で定義されるロジスティック写像Ｘt+1を演算する演算装置において、前記「Ｘt」、「Ｘt+1」はＮ桁の２進数で示され、且つ前記「Ｘt」はｘ(0)〜ｘ(N-1)のビット列で示され、少なくともＮ段、（Ｎ−１）列の加算器からなる配列型乗算器を備え、このうち第１段の（Ｎ−１）個の加算器は、少なくとも２つの入力を有する加算器であり、前記漸化式を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とした場合に、前記配列型乗算器を用いて右辺の「Ｘt＊notＸt」を演算すると共に、該配列型乗算器の第１段、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器の１つの入力に、ｘ(m)の数値を入力して加算することにより、前記展開式の「Ｘt」を加算する処理を実行することを特徴とする。

請求項２に記載の発明は、図２に示す第１実施形態に係り、漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」で定義されるロジスティック写像Ｘt+1を演算する演算装置において、前記「Ｘt」、「Ｘt+1」はＮ桁の２進数で示され、前記漸化式を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とした場合に、下記構成を備える（Ａ）配列型乗算器、及び（Ｂ）加算回路を用いて前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」で示される演算を行うことを特徴とするロジスティック写像の演算装置である。（Ａ）前記配列型乗算器は、第１列から第（Ｎ−１）列までの（Ｎ−１）個の全加算器からなる加算器群が、第１段から第Ｎ段まで設けられ、且つ、前記各全加算器は各段毎に１列ずつシフトして配置する。この前記各全加算器は、図７に示すように３つの入力ａ、ｂ、ｃ及び２つの出力Ｃ、Ｓを有し、前記各入力ａ、ｂ、ｃに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とし、３個のときに出力Ｓ、Ｃ共に「１」とする演算を行う。該配列型乗算器には、各桁がｘ(0)〜ｘ(N-1)で示される２進Ｎ桁の被乗算値（Ｘt）と、各桁がｙ(0)〜ｙ(N-1)で示される２進Ｎ桁の乗算値（notＸt）との乗算を実施する際に、第１段、第ｍ列（但し、１≦ｍ≦Ｎ−１）の全加算器のａ入力に「ｘ(m)＊ｙ(0)」の演算結果を入力し、ｂ入力にそれぞれｘ(m)を入力し、ｃ入力に「ｘ(m-1)＊ｙ(1)」の演算結果を入力する。第ｎ段、第ｍ列（但し、２≦ｎ≦Ｎ−１、１≦ｍ≦Ｎ−２）の全加算器は、ａ入力に第（ｎ−１）段、第（ｍ＋１）列の全加算器のＳ出力を入力し、ｂ入力に第（ｎ−１）段、第ｍ列の全加算器のＣ出力を入力し、ｃ入力に「ｘ（m-1）＊ｙ(n)」の演算結果を入力する。第ｎ段（但し、２≦ｎ≦Ｎ−１）、第（Ｎ−１）列の全加算器は、ａ入力に「ｘ(N-1)＊ｙ(n-1)」の演算結果を入力し、ｂ入力に第（ｎ−１）段、第（Ｎ−１）列の全加算器のＣ出力を入力し、ｃ入力に「ｘ(N-2)＊ｙ(n)」の演算結果を入力する。第Ｎ段、第ｍ列（但し、１≦ｍ≦Ｎ−２）の全加算器は、ａ入力に第（Ｎ−１）段、第（ｍ＋１）列の全加算器のＳ出力を入力し、ｂ入力に第（Ｎ−１）段、第ｍ列の全加算器のＣ出力を入力し、ｃ入力にはｍ≠１の場合に第Ｎ段、第（ｍ−１）列の全加算器のＣ出力を入力する。第Ｎ段、第（Ｎ−１）列の全加算器は、ａ入力に「ｘ(n-1)＊ｙ(n-1)」の演算結果を入力し、ｂ入力に第（Ｎ−１）段、第（Ｎ−１）列の全加算器のＣ出力を入力し、ｃ入力に第（Ｎ−２）列の全加算器のＣ出力を入力するように構成する。（Ｂ）前記加算回路は、２つの入力ａ、ｂ及び２つの出力Ｃ、Ｓを有し、前記各入力ａ、ｂに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とする演算を行う第１〜第（Ｎ−１）の半加算器（ＨＡ）を有する。前記第ｎの半加算器（ｎ＝１〜Ｎ−１）は、ａ入力に第ｎ段、第１列の全加算器のＳ出力が入力され、ｂ入力には、ｎ＝２〜Ｎ−１の場合に第（ｎ−１）の半加算器のＣ出力が入力されｎ＝１の場合に「０」が入力され、第（Ｎ−１）の半加算器のＣ出力を第Ｎ段、第１列の全加算器のｃ入力に出力し、第１〜第（Ｎ−１）の半加算器のＳ出力を、それぞれＰ（１）〜Ｐ（Ｎ−１）とし、第Ｎ段、第ｍ列（但し、ｍ＝１〜Ｎ−１）の全加算器のＳ出力を、それぞれＰ（Ｎ）〜Ｐ（２Ｎ−２）とし、前記Ｐ（１）〜Ｐ（２Ｎ−２）の各ビットから、連続したＮ桁のビットを取り出して、前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」の演算結果とする。

また、請求項２において、前記Ｐ（１）〜Ｐ（２Ｎ−２）の各ビットのうち、Ｐ（Ｎ−２）〜Ｐ（２Ｎ−３）までのＮ桁のビットを取り出して、前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」の演算結果とすることも可能である。

請求項３に記載の発明は、図３に示す第２実施形態に係り、漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」で定義されるロジスティック写像Ｘt+1を演算する演算装置において、前記「Ｘt」、「Ｘt+1」はＮ桁の２進数で示され、前記漸化式を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とした場合に、下記構成を備える（Ａ）配列型乗算器、及び（Ｂ）加算回路を用いて前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」で示される演算を行うことを特徴とするロジスティック写像の演算装置である。（Ａ）前記配列型乗算器は、第１列から第（Ｎ−１）列までの（Ｎ−１）個の全加算器からなる加算器群が、第１段から第（Ｎ−１）段まで設けられ、且つ、第Ｎ段には（Ｎ−２）個の加算器からなる加算器群が設けられ、更に、前記各段の全加算器は各段毎に１列ずつシフトして配置する。この前記各全加算器は、図７に示すように、３つの入力ａ、ｂ、ｃ及び２つの出力Ｃ、Ｓを有し、前記各入力ａ、ｂ、ｃに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とし、３個のときに出力Ｓ、Ｃ共に「１」とする演算を行う。該配列型乗算器は、各桁がｘ(0)〜ｘ(N-1)で示される２進Ｎ桁の被乗算値「Ｘt」と、各桁がｙ(0)〜ｙ(N-1)で示される２進Ｎ桁の乗算値「notＸt」との乗算を実施する際に、第１段、第ｍ列（但し、１≦ｍ≦Ｎ−１）の全加算器は、ａ入力に「ｘ(m)＊ｙ(0)」の演算結果を入力し、ｂ入力にそれぞれｘ(m)を入力し、ｃ入力に「ｘ(m-1)＊ｙ(1)」の演算結果を入力する。第ｎ段、第ｍ列（但し、２≦ｎ≦Ｎ−１、ｍ≠Ｎ−１）の全加算器は、ａ入力に第（ｎ−１）段、第（ｍ＋１）列の全加算器のＳ出力を入力し、ｂ入力に第（ｎ−１）段、第ｍ列の全加算器のＣ出力を入力し、ｃ入力に「ｘ（m-1）＊ｙ(n)」の演算結果を入力する。第ｎ段（但し、２≦ｎ≦Ｎ−１）、第（Ｎ−１）列の全加算器は、ａ入力に「ｘ(N-1)＊ｙ(n-1)」の演算結果を入力し、ｂ入力に第（ｎ−１）段、第（Ｎ−１）列の全加算器のＣ出力を入力し、ｃ入力に「ｘ(N-2)＊ｙ(n)」の演算結果を入力する。第Ｎ段、第ｍ列（但し、１≦ｍ≦Ｎ−２）の全加算器は、ａ入力に第（Ｎ−１）段、第（ｍ＋１）列の全加算器のＳ出力を入力し、ｂ入力に第（Ｎ−１）段、第ｍ列の全加算器のＣ出力を入力し、ｃ入力にはｍ≠１の場合に第Ｎ段、第（ｍ−１）列の全加算器のＣ出力を入力するように構成する。（Ｂ）前記加算回路は、（Ｎ−３）個の、第１〜第（Ｎ−３）のキャリー計算器、及び２個の、第（Ｎ−２）の半加算器、及び第（Ｎ−１）の半加算器を備え、前記半加算器は、２つの入力ａ、ｂ及び２つの出力Ｃ、Ｓを有し、前記各入力ａ、ｂに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とする演算を行う。また、前記キャリー計算器は、２つの入力ａ、ｂ及び１つの出力Ｃを有し、前記各入力ａ、ｂに含まれる「１」の個数が２個のときに出力Ｃを「１」とし、それ以外の場合に「０」とする演算を行う。第ｎのキャリー計算器（但し、ｎ＝１〜Ｎ−３）は、ａ入力に第ｎ段、第１列の全加算器のＳ出力が入力され、ｂ入力にはｎ≠１の場合に第（ｎ−１）のキャリー計算器のＣ出力が入力され、ｎ＝１の場合に「０」が入力される。前記第（Ｎ−２）の半加算器は、ａ入力に第（Ｎ−２）段、第１列の全加算器のＳ出力が入力され、ｂ入力に第（Ｎ−３）のキャリー計算器のＣ出力が入力される。前記第（Ｎ−１）の半加算器は、ａ入力に第（Ｎ−１）段、第１列の全加算器のＳ出力が入力され、ｂ入力に第（Ｎ−２）のキャリー計算器のＣ出力が入力され、且つ、Ｃ出力を第Ｎ段、第１列の全加算器のｃ入力に出力し、前記第（Ｎ−２）の半加算器のＳ出力をＰ（Ｎ−２）、第（Ｎ−１）の半加算器のＳ出力をＰ（Ｎ−１）とし、第Ｎ段、第ｍ列（但し、ｍ＝１〜Ｎ−２）の全加算器のＳ出力を、それぞれＰ（Ｎ）〜Ｐ（２Ｎ−３）とし、Ｐ（Ｎ−２）〜Ｐ（２Ｎ−３）のＮ桁のビットを前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」の演算結果とする。

また、請求項３において、図９に示すように、前記第１〜第（Ｎ−３）のキャリー計算器は２入力のＡＮＤ回路で構成することも可能である。

請求項４に記載の発明は、図４に示す第３実施形態に係り、漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」で定義されるロジスティック写像Ｘt+1を演算する演算装置において、前記「Ｘt」、「Ｘt+1」はＮ桁の２進数で示され、前記漸化式を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とした場合に、下記構成を備える（Ａ）配列型乗算器を用いて前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」で示される演算を行うことを特徴とするロジスティック写像の演算装置である。（Ａ）前記配列型乗算器は、第１列から第（Ｎ−１）列までの（Ｎ−１）個の加算器からなる加算器群が、第１段から第（Ｎ−１）段まで設けられ、且つ、第Ｎ段には（Ｎ−２）個の加算器からなる加算器群が設けられ、更に、前記各段の加算器は各段毎に１列ずつシフトして配置される。前記各加算器は３つの入力ａ、ｂ、ｃと２つの出力Ｃ、Ｓを有する全加算器、２つの入力ａ、ｂと２つの出力Ｃ、Ｓを有する半加算器、３つの入力ａ、ｂ、ｃと１つの出力Ｃを有するキャリー計算器、及び、３つの入力ａ、ｂ、ｃと１つの出力Ｓを有するサム計算器のうちのいずれかである。前記各加算器は、各入力ａ、ｂ、ｃに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とし、３個のときに出力Ｓ、Ｃ共に「１」とする演算を行う。該配列型乗算器は、各桁がｘ(0)〜ｘ(N-1)で示される２進Ｎ桁の被乗算値「Ｘt」と、各桁がｙ(0)〜ｙ(N-1)で示される２進Ｎ桁の乗算値「notＸt」との乗算を実施する際に、第１段の加算器群は、第１列が前記キャリー計算器、第２列が前記半加算器、その他の列が前記全加算器で構成される。第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器はａ入力に「ｘ(m)*ｙ(0)」の演算結果を入力し、ｂ入力にそれぞれｘ(m)を入力し、更に、第２列を除く各列の加算器のｃ入力に「ｘ(m-1)＊ｙ(1)」の演算結果を入力する。第ｎ段（但し、２≦ｎ≦Ｎ−３）の加算器群は、第１列が前記キャリー計算器、第（ｎ＋１）列が前記半加算器、その他の列が前記全加算器で構成される。第（Ｎ−１）列の加算器はａ入力に「ｘ(N-1)＊ｙ(n-1)」の演算結果を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器は、ａ入力に第（ｎ−１）段、第（ｍ＋１）列の加算器のＳ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器は、ｂ入力に、第（ｎ−１）段、第ｍ列の加算器のＣ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１、（ｎ＋１）を除く）の加算器は、ｃ入力に「ｘ(m-1)＊ｙ(n)」の演算結果を入力する。第（Ｎ−２）段の加算器群は、第（Ｎ−１）列が前記半加算器、その他の列が前記全加算器で構成される。第（Ｎ−１）列の加算器は、ａ入力に「ｘ(N-1)＊ｙ(N-3)」の演算結果を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器は、ａ入力に第（Ｎ−３）段、第（ｍ＋１）列の加算器のＳ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器は、ｂ入力に、第（Ｎ−３）段、第ｍ列の加算器のＣ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器のｃ入力に「ｘ(m-1)＊ｙ(N-2)」の演算結果を入力する。第（Ｎ−１）段の加算器群は、第（Ｎ−１）列が前記サム計算器、その他の列が前記全加算器で構成される。第（Ｎ−１）列の加算器は、ａ入力に「ｘ(N-1)*ｙ(N-2)」の演算結果を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器は、ａ入力に第（Ｎ−２）段、第（ｍ＋１）列、の加算器のＳ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器は、ｂ入力に、第（Ｎ−２）段、第ｍ列の加算器のＣ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器は、ｃ入力に「ｘ(m-1)＊ｙ(N-1)」の演算結果を入力する。第Ｎ段の加算器群は、第１列が前記半加算器、第（Ｎ−２）列が前記サム計算器、その他の列が前記全加算器で構成される。第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器は、ａ入力に第（Ｎ−１）段、第（ｍ＋１）列の加算器のＳ出力を入力し、ｂ入力に第（Ｎ−１）段、第ｍ列、の加算器のＣ出力を入力し、第ｍ列（但し、２≦ｍ≦Ｎ−２）のｃ入力に第Ｎ段、第（ｍ−１）列の加算器のＣ出力を入力するように構成される。第（Ｎ−２）段、１列の加算器のＳ出力をＰ（Ｎ−２）、第（Ｎ−１）段、１列の加算器のＳ出力をＰ（Ｎ−１）とし、且つ、第Ｎ段、第１〜第（Ｎ−２）列の加算器のＳ出力をそれぞれＰ（Ｎ）〜Ｐ（２Ｎ−３）とし、Ｐ（Ｎ−２）〜Ｐ（２Ｎ−３）のＮ桁のビットを前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」の演算結果とすることを特徴とする。

また、請求項４において、前記半加算器は、前記ｃ入力が常にゼロである全加算器で構成することも可能である。

更に、請求項４において、前記キャリー計算器は、図１０に示すように、一つの半加算器、一つのＡＮＤ回路と一つのＯＲ回路で構成することも可能である。

また、請求項４において、前記サム計算器は、図１１に示すように、３入力の排他的論理和回路で構成することも可能である。

本発明に係るロジスティック写像の演算装置では、ロジスティック写像の漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とし、配列型乗算器を用いて右辺の「Ｘt＊notＸt」を演算する。また、配列型乗算器の第１段、各列に設けられた加算器の一つの入力（例えば、ｂ入力）に「Ｘt」のビット列であるｘ0、ｘ1、ｘ2、・・・、ｘn-1（ｎは桁数）をそれぞれ入力するので実質的にＸtが加算されており、「Ｘt＊notＸt＋Ｘt」が実行されていることになる。従って、従来の演算方法と比較してロジスティックス写像の漸化式を演算する前に、予め演算する必要がある「notＸt」、即ち「Ｘt」の値を反転して「＋１」とする処理を省略できるので、演算速度を高速化することができる。

本発明の実施形態に係るロジスティック写像の演算装置の構成を示すブロックである。 本発明の第１実施形態に係るロジスティック写像の演算装置の、演算手段の構成を示すブロック図である。 本発明の第２実施形態に係るロジスティック写像の演算装置の、演算手段の構成を示すブロック図である。 本発明の第３実施形態に係るロジスティック写像の演算装置の、演算手段の構成を示すブロック図である。 従来における「Ｘt＊（notＸt＋１）」の演算手順を示す説明図である。 従来における２進数で表す２つの値を乗算する配列型乗算器を示す説明図である。 全加算器の入力、出力の関係を示す説明図である。 ６桁の全加算器を用いて「＋１」の演算を実行する手順を示す説明図である。 本発明の実施形態に係るロジスティックス写像の演算装置で用いられる２入力のキャリー計算器の論理回路を示す図である。 本発明の実施形態に係るロジスティックス写像の演算装置で用いられる３入力のキャリー計算器の論理回路を示す図である。 本発明の実施形態に係るロジスティックス写像の演算装置で用いられる３入力のサム計算器の論理回路を示す図である。 本発明の実施形態に係るロジスティックス写像の演算装置で用いられる半加算器、及び半加算器の論理回路を示す図である。 本発明の実施形態に係るロジスティックス写像の演算装置で用いられる桁上げ先見加算器の論理回路を示す図である。

以下、本発明の実施形態を図面に基づいて説明する。図１は、本発明の実施形態に係るロジスティック写像の演算装置の構成を示すブロック図である。図１に示すように、この演算装置１０は、初期値Ｘ0或いは前回の演算で求められた出力値Ｘt+1を入力値Ｘtとして入力する入力部１１と、該入力部１１に入力された入力値Ｘtを反転させたnotＸtを演算する反転演算部１２と、後述する手順で「Ｘt＊notＸt＋Ｘt」を演算する演算手段１３と、この演算手段１３で求められた演算結果の上位３ビット目からＮビット分の数値を出力値Ｘt+1として出力し、且つ、入力部１１にフィードバックするセレクタ１４と、を備えている。

そして、後述する第１〜第３実施形態では、ロジスティック写像の漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とし、配列型乗算器を用いて右辺の「Ｘt＊notＸt＋Ｘt」を演算することにより、従来方法で必要とされていた「＋１」の処理を不要として演算速度を高速化する。以下、詳細に説明する。

［第１実施形態］
図２は、本発明の第１実施形態に係るロジスティック写像の演算装置の演算手段１３の構成を示す説明図である。図２に示すように、この演算手段１３は、配列型乗算器２１と、加算回路２２を備えている。なお、本実施形態では、ロジステック写像の入力値「Ｘt」が６桁の２進数であり、「Ｘt＝００１０１１」、「notＸt＝１１０１００」である場合を例に挙げて説明する。

図２に示すように、配列型乗算器２１は、第１段〜第６段（Ｎ桁の場合には第１段〜第Ｎ段）にそれぞれ５個（Ｎ−１個）の全加算器（ＦＡ）が設けられている。以下では、最上段を第１段、最下段を第６段とし、右端を第１列、左端を第５列として示すことにする。

全加算器（ＦＡ）は、前述した図７に示したように、３つの入力、及び２つの出力を有しており、このうち上側からの入力をａ入力、右上からの入力をｂ入力、右側からの入力をｃ入力とする。また、下側への出力をＳ出力、左下への出力をＣ出力とする。そして、ａ入力、ｂ入力、ｃ入力に入力されるデータが全て１である場合には、Ｓ出力、Ｃ出力を共に１とし、１が２個存在する場合にはＳ出力を０、Ｃ出力を１とし、１が１個存在する場合にはＳ出力を１、Ｃ出力を０とし、１が存在しない場合（全て０の場合）にはＳ出力、Ｃ出力共に０とする。

ここで、第１〜第５段に設けられる加算器は、桁上げ保存加算器という。図２の最終段（第６段）では、順次桁上げ加算器が用いられているが、この加算器は桁上げ先見加算器で置き換えることができる。また、周知の技術として、桁上げ先見加算器は、順次桁上げ加算器よりも演算時間が短いことが知られている。但し、桁上げ先見加算器は桁数の２乗に比例してハードウェア量が増えるため、順次桁上げ加算器よりも演算時間の短い桁上げ先見加算器を用いる。なお、桁上げ先見加算器の詳細については後述する。

また、加算回路２２は、６個の半加算器（ＨＡ）２２-1〜２２-6を備えている。半加算器（ＨＡ）２２-1〜２２-6は、前述した全加算器（ＦＡ）と対比してｃ入力を備えていない点で相違する。そして、ａ入力、ｂ入力に入力されるデータが共に１である場合には、Ｓ出力を０、Ｃ出力を１とし、入力データのいずれか一方が１である場合にはＳ出力を１、Ｃ出力を０とし、１が存在しない場合（双方が０の場合）にはＳ出力、Ｃ出力共に０とする。

ここで、「Ｘt＝００１０１１」の右側の桁から左側の桁に向けて符号ｘ0〜ｘ5で示す。従って、ｘ0＝１、ｘ1＝１、ｘ2＝０、ｘ3＝１、ｘ4＝０、ｘ5＝０である。また、「notＸt＝１１０１００」の右側の桁から左側の桁に向けて符号ｙ0〜ｙ5で示す。従って、ｙ0＝０、ｙ1＝０、ｙ2＝１、ｙ3＝０、ｙ4＝１、ｙ5＝１である。

そして、図２に示すように、第１段の第１〜第５列の全加算器（ＦＡ）のａ入力には、「ｘm＊ｙ0」（但し、ｍ＝１〜５）の演算結果が入力される。また、「ｘ0＊ｙ0」の演算結果は半加算器（ＨＡ）２２-1のａ入力に入力される。

また、第１段の第１〜第５列の全加算器（ＦＡ）のｂ入力にはｘm（但し、１≦ｍ≦５）が入力される。更に、ｘ0は半加算器（ＨＡ）２２-1のｂ入力に入力される。

また、第１段の第１〜第５列の全加算器（ＦＡ）のｃ入力には、「ｘm-1＊ｙ1」（但し、１≦ｍ≦５）の演算結果が入力される。第１段、第１列の全加算器（ＦＡ）のＳ出力は、半加算器（ＨＡ）２２-2のａ入力に入力される。

一方、第２段、第１〜第４列の全加算器（ＦＡ）のａ入力には、第１段、第２〜第５列の全加算器（ＦＡ）のＳ出力が入力され、第２段、第５列の全加算器（ＦＡ）のａ入力には「ｘ5＊ｙ1」の演算結果が入力される。第２段、第１〜第５列の全加算器（ＦＡ）のｂ入力には、第１段、第１〜第５列の全加算器（ＦＡ）のＣ出力が入力される。更に、第２段、第１〜第５列の全加算器（ＦＡ）のｃ入力には、「ｘm-1＊ｙ2」（但し、１≦ｍ≦５）の演算結果が入力される。第２段、第１列のＳ出力は半加算器（ＨＡ）２２-3のａ入力に入力される。

同様に、第３段、第４段、第５段における第１〜第５列の全加算器（ＦＡ）のａ、ｂ、ｃ入力に各種のデータが入力され、Ｓ出力、Ｃ出力を出力する。そして、第３段、第１列の全加算器（ＦＡ）のＳ出力は、半加算器（ＨＡ）２２-4のａ入力に入力され、第４段、第１列の全加算器（ＦＡ）のＳ出力は、半加算器（ＨＡ）２２-5のａ入力に入力され、第５段、第１列の全加算器（ＦＡ）のＳ出力は、半加算器（ＨＡ）２２-6のａ入力に入力される。

半加算器（ＨＡ）２２-1のＣ出力は、隣接する半加算器（ＨＡ）２２-2のｂ入力に入力され、半加算器（ＨＡ）２２-2のＣ出力は、隣接する半加算器（ＨＡ）２２-3のｂ入力に入力され、半加算器（ＨＡ）２２-3のＣ出力は、隣接する半加算器（ＨＡ）２２-4のｂ入力に入力され、半加算器（ＨＡ）２２-4のＣ出力は、隣接する半加算器（ＨＡ）２２-5のｂ入力に入力され、半加算器（ＨＡ）２２-5のＣ出力は、隣接する半加算器（ＨＡ）２２-6のｂ入力に入力され、半加算器（ＨＡ）２２-6のＣ出力は、第６段、第１列の全加算器（ＦＡ）のｃ入力に入力される。

また、第６段、第１〜第４列の全加算器（ＦＡ）のａ入力には、第５段、第２〜第５列の全加算器（ＦＡ）のＳ出力が入力され、第６段、第５列の全加算器（ＦＡ）のａ入力には「ｘ5＊ｙ5」の演算結果が入力され、第６段、第１〜第５列の全加算器（ＦＡ）のｂ入力には、第５段、第１〜第５列の全加算器（ＦＡ）のＣ出力が入力され、第６段、第２〜第５列の全加算器（ＦＡ）のｃ入力には、第６段、第１〜第４列の全加算器（ＦＡ）のＣ出力が入力され、第６段、第１列の全加算器（ＦＡ）のｃ入力には半加算器（ＨＡ）２２-6のＣ出力が入力される。

そして、半加算器（ＨＡ）２２-1のＳ出力をＰ０、半加算器（ＨＡ）２２-2のＳ出力をＰ１、半加算器（ＨＡ）２２-3のＳ出力をＰ２、半加算器（ＨＡ）２２-4のＳ出力をＰ３、半加算器（ＨＡ）２２-5のＳ出力をＰ４、半加算器（ＨＡ）２２-6のＳ出力をＰ５とし、且つ、第６段、第１列の全加算器（ＦＡ）のＳ出力をＰ６とし、第６段、第２列の全加算器（ＦＡ）のＳ出力をＰ７とし、第６段、第３列の全加算器（ＦＡ）のＳ出力をＰ８とし、第６段、第４列の全加算器（ＦＡ）のＳ出力をＰ９とし、第６段、第５列の全加算器（ＦＡ）のＳ出力をＰ１０とし、第６段、第５列の全加算器（ＦＡ）のＣ出力をＰ１１とする。

そして、Ｐ０〜Ｐ１１のビット列で構成される２進１２桁の数値が「Ｘt」と「notＸt」との乗算結果となり、このうち、上位３ビット目から６ビット分の数値、即ちＰ４〜Ｐ９の６桁の数値を出力値「Ｘt+1」とする。また、この出力値「Ｘt+1」を図１に示した入力部１１に供給して次回の入力値とする。こうして、「Ｘt」と「notＸt」との乗算が実行されることになる。

上述した演算によれば、第１段の各全加算器（ＦＡ）のｂ入力に、「Ｘt+1」のビット列であるｘ1〜ｘ5が入力され、且つ半加算器（ＨＡ）２２-1のｂ入力にｘ0が入力されるので、実質的に「Ｘt」（ｘ0〜ｘ5）の加算処理が実行されている。換言すれば、「Ｘt＊notＸt」の演算と同時に「Ｘt」を加算する処理が実行されていることになり、「Ｘt＊notＸt」の演算を実行するための所要時間とほぼ同一の所要時間で「Ｘt＊notＸt＋Ｘt」の演算が実行可能であることが理解される。

即ち、第１実施形態に係るロジスティック写像の演算装置では、ロジスティック写像の漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とし、上述した演算手段１３により、右辺の「Ｘt＊notＸt＋Ｘt」の演算を実行しているので、従来の演算方法と対比して、「＋１」の演算（notＸt＋１）が不要となり、Ｎ桁（この例では６桁）の加算を実行するための所要時間を省略することができ、ロジスティック写像の演算速度を高速化することができる。

また、第１実施形態では、図２に示す最終段（第６段）に設けられる加算器として、順次桁上げ加算器よりも演算時間が短い桁上げ先見加算器を用いている。以下、図１３に示す回路図を参照して桁上げ先見加算器について説明する。

図１３は、６桁の桁上げ先見加算器の構成を示す回路図であり、半加算器５１と、６個の全加算器５２-1〜５２-6、及び桁上げ先見回路５３を備えている。各全加算器５２-1〜５２-6の「Ｃ入力」は、図７に示すｂ入力に相当する。

そして、桁上げ先見回路５３は、各全加算器５２-1〜５２-6のＣ入力の入力値Ｃ０〜Ｃ５を、１つのＯＲゲートと、互いに並列に設けられる１または複数個のＡＮＤゲートで構成することができる。従って、桁数が何桁であっても２段の演算でＣ入力の入力値を求めることができる。

このため、各全加算器５２-1〜５２-6では、下位の桁での演算結果を待つことなく、Ａ入力、Ｂ入力、Ｃ入力が決定されるので、ほぼ同時に演算を実行することができ、演算速度を高速化することができる。

［第２実施形態］
次に、本発明の第２実施形態について説明する。図３は、第２実施形態に係るロジスティック写像の演算装置の演算手段１３の構成を示す説明図である。図３に示すように、この演算手段１３は、前述した第１実施形態と同様に、配列型乗算器３１と、加算回路３２を備えている。

図２に示した第１実施形態と対比すると、第２実施形態では図２に示した第６段、第５列に設けた全加算器（ＦＡ）を割愛した点、及び、加算回路３２に設けられる６個の加算器のうち、右側から４個が半加算器（ＨＡ）からキャリー計算器（Ｃ）に変更された点で相違している。即ち、加算回路３２は、キャリー計算器（Ｃ）３２-1〜３２-4、及び半加算器（ＨＡ）３２-5、３２-6を備えている。

第２実施形態で使用するキャリー計算器（Ｃ）は、２入力、１出力型であり、２つの入力ａ、ｂと、１つの出力Ｃを有し、ａ入力とｂ入力の双方が１である場合にＣ出力を１とし、それ以外の場合にはＣ出力を０とする。該キャリー計算器（Ｃ）の論理回路は、図９に示すように、ＡＮＤ回路で構成することができる。

次に、図３に示した第２実施形態の演算手段１３で「Ｘt＊notＸt＋Ｘt」を演算する手順について説明する。なお、第１実施形態と同様に「Ｘt＝００１０１１」、「notＸt＝１１０１００」であるとする。

いま、「Ｘt＝００１０１１」の右側の桁から左側の桁に向けて符号ｘ0〜ｘ5で示す。従って、ｘ0＝１、ｘ1＝１、ｘ2＝０、ｘ3＝１、ｘ4＝０、ｘ5＝０である。また、「notＸt＝１１０１００」の右側の桁から左側の桁に向けて符号ｙ0〜ｙ5で示す。従って、ｙ0＝０、ｙ1＝０、ｙ2＝１、ｙ3＝０、ｙ4＝１、ｙ5＝１である。

そして、図３に示すように、第１段、第１〜第５列の全加算器（ＦＡ）のａ入力には、「ｘm＊ｙ0」（但し、ｍ＝１〜５）の演算結果が入力される。また、「ｘ0＊ｙ0」の演算結果はキャリー計算器（Ｃ）３２-1のａ入力に入力される。

また、第１段、第１〜第５列の全加算器（ＦＡ）のｂ入力には、ｘm（但し、１≦ｍ≦５）が入力される。更に、ｘ0はキャリー計算器（Ｃ）３２-1のｂ入力に入力される。

また、第１段、第１〜第５列の全加算器のｃ入力には、「ｘm-1＊ｙ1」（但し、１≦ｍ≦５）の演算結果が入力される。第１段、第１列の全加算器のＳ出力は、キャリー計算器（Ｃ）３２-2のａ入力に入力される。

一方、第２段、第１〜第４列の全加算器（ＦＡ）のａ入力には、第１段、第２〜第５列の全加算器（ＦＡ）のＳ出力が入力され、第２段、第５列の全加算器（ＦＡ）のａ入力には「ｘ5＊ｙ1」の演算結果が入力される。第２段、第１〜第５列の全加算器（ＦＡ）のｂ入力には、第１段、第１〜第５列のＣ出力が入力される。更に、第２段、第１〜第５列の全加算器（ＦＡ）のｃ入力には、「ｘm-1＊ｙ2」（但し、１≦ｍ≦５）の演算結果が入力される。第２段、第１列の全加算器（ＦＡ）のＳ出力は、キャリー計算器（Ｃ）３２-3のａ入力に入力される。

同様に、第３段、第４段、第５段における第１〜第５列の全加算器（ＦＡ）のａ、ｂ、ｃ入力に各種のデータが入力され、Ｓ出力、Ｃ出力を出力する。そして、第３段、第１列の全加算器（ＦＡ）のＳ出力は、キャリー計算器（Ｃ）３２-4のａ入力に入力され、第４段、第１列の全加算器（ＦＡ）のＳ出力は、半加算器（ＨＡ）３２-5のａ入力に入力され、第５段、第１列の全加算器（ＦＡ）のＳ出力は、半加算器（ＨＡ）３２-6のａ入力に入力される。

キャリー計算器（Ｃ）３２-1のＣ出力は、隣接するキャリー計算器（Ｃ）３２-2のｂ入力に入力され、キャリー計算器（Ｃ）３２-2のＣ出力は、隣接するキャリー計算器（Ｃ）３２-3のｂ入力に入力され、キャリー計算器（Ｃ）３２-3のＣ出力は、隣接するキャリー計算器（Ｃ）３２-4のｂ入力に入力され、キャリー計算器（Ｃ）３２-4のＣ出力は、隣接する半加算器（ＨＡ）３２-5のｂ入力に入力され、半加算器（ＨＡ）３２-5のＣ出力は、隣接する半加算器（ＨＡ）３２-6のｂ入力に入力され、半加算器（ＨＡ）３２-6のＣ出力は、第６段、第１列の全加算器（ＦＡ）のｃ入力に入力される。

また、第６段、第１〜第４列の全加算器（ＦＡ）のａ入力には、第５段、第２〜第５列の全加算器（ＦＡ）のＳ出力が入力され、第６段、第１〜第４列の全加算器（ＦＡ）のｂ入力には、第５段、第１〜第４列の全加算器（ＦＡ）のＣ出力が入力され、第６段、第２〜第４列の全加算器（ＦＡ）のｃ入力には、第６段、第１〜第３列の全加算器（ＦＡ）のＣ出力が入力され、第６段、第１列の全加算器（ＦＡ）のｃ入力には半加算器（ＨＡ）３２-6のＣ出力が入力される。

そして、半加算器（ＨＡ）３２-5のＳ出力をＰ４、半加算器（ＨＡ）３２-6のＳ出力をＰ５とし、且つ、第６段、第１列の全加算器（ＦＡ）のＳ出力をＰ６とし、第６段、第２列の全加算器（ＦＡ）のＳ出力をＰ７とし、第６段、第３列の全加算器（ＦＡ）のＳ出力をＰ８とし、第６段、第４列の全加算器（ＦＡ）のＳ出力をＰ９とする。上記の処理で得られたＰ４〜Ｐ９の２進６桁のビット列を出力値「Ｘt+1」とする。これを、第１実施形態で説明した図２と対比すると、第２実施形態ではＰ０〜Ｐ３、Ｐ１０、Ｐ１１を取得していない点で相違する。

しかし、第１実施形態で説明したように、Ｐ０〜Ｐ１１で示される２進１２桁のビット列が得られた場合に、このうち、上位３ビット目から６ビット分の数値、即ちＰ４〜Ｐ９のＮ桁の数値を出力値「Ｘt+1」とするので、Ｐ０〜Ｐ３、Ｐ１０、Ｐ１１の値は不要である。第２実施形態では、この不要となるＰ０〜Ｐ３、Ｐ１０、Ｐ１１の演算を省略することにより、第６段、第５列の全加算器（ＦＡ）を省略し、且つ、加算回路３２に設けられた６個の加算器のうちの４個をキャリー計算器（Ｃ）とすることにより、回路規模を簡素化している。

即ち、第２実施形態に係るロジステック写像の演算装置に用いられる演算手段１３では、前述した第１実施形態と同様に、従来の演算方法と対比して、「＋１」の演算（notＸt＋１）が不要となるので、Ｎ桁（この例では６桁）の加算を実行するための時間を省略できるという効果を達成し、且つ、回路規模を簡素化でき、小型軽量化、低コスト化を図ることができる。

なお、上述した第２実施形態では、加算回路３２に設けられる加算器を半加算器（ＨＡ）またはキャリー計算器（Ｃ）とする例について説明したが、全ての加算器を半加算器（ＨＡ）で代用することも可能である。即ち、図３に示したキャリー計算器（Ｃ）はＳ出力を使用しない半加算器（ＨＡ）で代用できる。このような構成とした場合でも、第１実施形態と対比して、第６段、第５列の加算器を省略している点で回路規模を小型化できるという効果を達成できる。

［第３実施形態］
次に、本発明の第３実施形態について説明する。図４は、第３実施形態に係るロジスティック写像の演算装置の演算手段１３の構成を示す説明図である。図４に示すように、この演算手段１３は、前述した第１実施形態と対比して加算回路２２を備えていない点で相違する。即ち、第３実施形態に係る演算手段１３は、配列型乗算器４１のみで構成されている。

更に、図２に示した第１実施形態の配列型乗算器２１と対比して、第３実施形態では図２に示した第６段、第５列に設けた全加算器（ＦＡ）を省略している点、第１段、第１列の全加算器（ＦＡ）をキャリー計算器（Ｃ）とした点、第２段、第１列の全加算器（ＦＡ）をキャリー計算器（Ｃ）とした点、第３段、第１列の全加算器（ＦＡ）をキャリー計算器（Ｃ）とした点で相違する。更に、第１段、第２列の全加算器（ＦＡ）を半加算器（ＨＡ）とした点、第２段、第３列の全加算器（ＦＡ）を半加算器（ＨＡ）とした点、第３段、第４列の全加算器（ＦＡ）を半加算器（ＨＡ）とした点、第５段、第５列の全加算器（ＦＡ）をサム計算器（Ｓ）とした点、及び第６段、第５列の全加算器（ＦＡ）をサム計算器（Ｓ）とした点で相違する。

ここで、第３実施形態で用いるキャリー計算器（Ｃ）は３入力型であり、３つの入力ａ、ｂ、ｃのうち、２以上の入力値が１である場合に１を出力し、それ以外の場合には０を出力する。該キャリー計算器（Ｃ）は、図１０に示すように、ＡＮＤ回路、ＯＲ回路、排他的ＯＲ回路で構成することができる。また、サム計算器（Ｓ）は３入力型であり、３つの入力ａ、ｂ、ｃのうち、１個、または３個が１である場合１を出力し、それ以外の場合には０を出力する。該サム計算器（Ｓ）は、図１１に示すように、３入力の排他的ＯＲ回路で構成することができる。

なお、図４に示す点線で囲んだ加算器（ＨＡ、ＦＡ）は、第１実施形態で説明した図２の演算手段に対して省いた加算器を示している。つまり、点線で囲んだ加算器（ＨＡ、ＦＡ）は、第３実施形態では不要な構成要素である。

次に、図４に示した第３実施形態の演算手段１３で「Ｘt＊notＸt＋Ｘt」を演算する手順について説明する。なお、第１、第２実施形態と同様に「Ｘt＝００１０１１」、「notＸt＝１１０１００」であるとする。

いま、「Ｘt＝００１０１１」の右側の桁から左側の桁に向けて符号ｘ0〜ｘ5で示す。従って、ｘ0＝１、ｘ1＝１、ｘ2＝０、ｘ3＝１、ｘ4＝０、ｘ5＝０である。また、「notＸt＝１１０１００」の右側の桁から左側の桁に向けて符号ｙ0〜ｙ5で示す。従って、ｙ0＝０、ｙ1＝０、ｙ2＝１、ｙ3＝０、ｙ4＝１、ｙ5＝１である。

そして、図４に示すように、第１段、第１〜第５列の各加算器（ＦＡ、ＨＡ、Ｃ）のａ入力には、「ｘm＊ｙ0」（但し、１≦ｍ≦５）の演算結果が入力される。また、「ｘ0＊ｙ0」の演算結果は後述する理由により不要であるから破棄する。

また、第１段、第１〜第５列の各加算器（ＦＡ、ＨＡ、Ｃ）のｂ入力にはｘm（但し、１≦ｍ≦５）が入力される。また、ｘ0は後述する理由により不要であるので破棄する。

第１段、第１〜第５列の各加算器（ＦＡ、ＨＡ、Ｃ）のｃ入力には、「ｘm-1＊ｙ1」（但し、１≦ｍ≦５）の演算結果が入力される。

一方、第２段、第１〜第４列の各加算器（ＦＡ、ＨＡ、Ｃ）のａ入力には、第１段、第２〜第５列の各加算器（ＦＡ、ＨＡ）のＳ出力が入力され、第２段、第５列の全加算器（ＦＡ）のａ入力には「ｘ5＊ｙ1」の演算結果が入力される。第２段、第１〜第５列の各加算器（ＦＡ、ＨＡ、Ｃ）のｂ入力には、第１段、第１〜第５列の各加算器（ＦＡ、ＨＡ、Ｃ）のＣ出力が入力される。更に、第２段、第１〜第５列の各加算器（ＦＡ、ＨＡ、Ｃ）のｃ入力には、「ｘm-1＊ｙ2」（但し、１≦ｍ≦５）の演算結果が入力される。

同様に、第３段、第４段、第５段における第１〜第５列の各加算器（ＦＡ、ＨＡ、Ｃ、Ｓ）の各入力に各種のデータが入力され、各出力を出力する。

また、第６段、第１〜第４列の各加算器（ＦＡ、Ｓ）のａ入力には、第５段、第２〜第５列の各加算器（ＦＡ、Ｓ）のＳ出力が入力され、第６段、第１〜第４列の各加算器（ＦＡ、Ｓ）のｂ入力には、第５段、第１〜第４列のＣ出力が入力され、第６段、第２〜第４列の各加算器（ＦＡ、Ｓ）のｃ入力には、第６段、第１〜第３列の各加算器（ＦＡ、ＨＡ）Ｃ出力が入力される。

そして、第４段、第１列の全加算器（ＦＡ）のＳ出力をＰ４、第５段、第１列の全加算器（ＦＡ）のＳ出力をＰ５とし、且つ、第６段、第１列の半加算器（ＨＡ）のＳ出力をＰ６とし、第６段、第２列の全加算器（ＦＡ）のＳ出力をＰ７とし、第６段、第３列の全加算器（ＦＡ）のＳ出力をＰ８とし、第６段、第４列のサム計算器（Ｓ）のＳ出力をＰ９とする。上記の処理で得られたＰ４〜Ｐ９の２進６桁のビット列を出力値「Ｘt+1」とする。これを、第１実施形態で説明した図２と対比すると、第３実施形態ではＰ０〜Ｐ３、Ｐ１０、Ｐ１１を取得していない点、第６段、第５列の加算器を省略している点、加算回路２２を不要としている点、いくつかの全加算器（ＦＡ）を半加算器（ＨＡ）やキャリー計算器（Ｃ）に変更している点で相違する。この構成の相違は、配列型乗算器４１をロジステック写像の演算に特化した機能としていることに起因する。以下、詳細に説明する。

ロジステック写像の演算では、上述したように「Ｘt」と「notＸt」を乗算しており、両者の同一桁の数値は互いに背反であるので（一方が１であれば他方が０であるという関係であるので）、「ｘ0＊ｙ0」、「ｘ1＊ｙ1」、「ｘ2＊ｙ2」・・・のように、同一桁どうしの乗算結果は必ず０になる。

従って、第１段、第２列の加算器、第２段、第３列の加算器、第３段、第４列の加算器、第４段、第５列の加算器はｃ入力が不要であり、半加算器（ＨＡ）としている。また、Ｐ０のデータを取得する必要がないので、ｘ0のデータを破棄し、「ｘ0＊ｙ0」の演算結果を破棄する。更に、Ｐ１〜Ｐ３のデータを取得する必要がないので、第１段、第１列の加算器のＳ出力は不要となり、この加算器をキャリー計算器（Ｃ）とすることができ、同様に、第２段、第１列の加算器、及び第３段、第１列の加算器をキャリー計算器（Ｃ）とすることができる。

更に、ロジステック写像の演算として、上位２ビットの数値（この例ではＰ１０，Ｐ１１）は共に０となることが知られているので、第５段、第５列の加算器はＣ出力が不要である。従って、この加算器をＣ出力を備えないサム計算器（Ｓ）としている。同様に、第６段、第５列の加算器もＣ出力が不要であるので、これをサム計算器（Ｓ）としている。

このようにして、第３実施形態に係るロジステック写像の演算装置に用いられる演算手段１３では、前述した第１実施形態と同様に、従来の演算方法と対比して、「＋１」の演算（notＸt＋１）が不要となるので、Ｎ桁（この例では６桁）の加算を実行するための時間を省略できるという効果を達成することができる。

また、配列型乗算器４１に設けられる各加算器の構成を簡素化することができるので、装置規模をより一層小型化することができ、省スペース化、低コスト化を図ることができる。

なお、上述した第３実施形態では、複数の加算器の一部を半加算器（ＨＡ）、キャリー計算器（Ｃ）、サム計算器（Ｓ）とする例について説明したが、これらを全加算器（ＦＡ）で代用することも可能である。例えば、半加算器（ＨＡ）はｃ入力を０とした全加算器（ＦＡ）で代用でき、キャリー計算器（Ｃ）はＳ出力を使用しない全加算器（ＦＡ）で代用でき、サム計算器（Ｓ）はＣ出力を使用しない全加算器（ＦＡ）で代用することができる。このような構成とした場合でも、第１実施形態と対比して、第６段、第５列の加算器を省略できる点、及び加算回路２２を備えない点で回路規模を小型化できるという効果を達成できる。

以上、本発明のロジステック写像の演算装置を図示の実施形態に基づいて説明したが、本発明はこれに限定されるものではなく、各部の構成は、同様の機能を有する任意の構成のものに置き換えることができる。

例えば、上述した各実施形態では、ロジステック写像の桁数を６桁としたが、これは一例を示したに過ぎず、他の桁数においても適用することが可能である。

本発明は、ロジスティック写像を高速に演算する場合に利用することができる。

１０ 演算装置
１１ 入力部
１２ 反転演算部
１３ 演算手段
１４ セレクタ
２１，３１，４１ 配列型乗算器
２２，３２ 加算回路
５１ 半加算器
５２-1〜５２-6 全加算器
５３ 桁上げ先見回路

Claims (4)

1. 漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」で定義されるロジスティック写像Ｘt+1を演算する演算装置において、
   前記「Ｘt」、「Ｘt+1」はＮ桁の２進数で示され、且つ前記「Ｘt」はｘ(0)〜ｘ(N-1)のビット列で示され、
   少なくともＮ段、（Ｎ−１）列の加算器からなる配列型乗算器を備え、このうち第１段の（Ｎ−１）個の加算器は、少なくとも２つの入力を有する加算器であり、
   前記漸化式を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とした場合に、前記配列型乗算器を用いて右辺の「Ｘt＊notＸt」を演算すると共に、該配列型乗算器の第１段、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器の１つの入力に、ｘ(m)の数値を入力して加算することにより、前記展開式の「Ｘt」を加算する処理を実行することを特徴とするロジスティック写像の演算装置。
2. 漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」で定義されるロジスティック写像Ｘt+1を演算する演算装置において、
   前記「Ｘt」、「Ｘt+1」はＮ桁の２進数で示され、前記漸化式を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とした場合に、下記構成を備える（Ａ）配列型乗算器、及び（Ｂ）加算回路を用いて前記展開した展開した漸化式の「Ｘt＊notＸt＋Ｘt」で示される演算を行うことを特徴とするロジスティック写像の演算装置、
   （Ａ）前記配列型乗算器は、
   第１列から第（Ｎ−１）列までの（Ｎ−１）個の全加算器からなる加算器群が、第１段から第Ｎ段まで設けられ、且つ、前記各全加算器は各段毎に１列ずつシフトして配置され、
   前記各全加算器は３つの入力ａ、ｂ、ｃ及び２つの出力Ｃ、Ｓを有し、前記各入力ａ、ｂ、ｃに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とし、３個のときに出力Ｓ、Ｃ共に「１」とする演算を行い、
   該配列型乗算器により、各桁がｘ(0)〜ｘ(N-1)で示される２進Ｎ桁の被乗算値（Ｘt）と、各桁がｙ(0)〜ｙ(N-1)で示される２進Ｎ桁の乗算値（notＸt）との乗算を実施する際に、
   第１段、第ｍ列（但し、１≦ｍ≦Ｎ−１）の全加算器のａ入力に「ｘ(m)＊ｙ(0)」の演算結果を入力し、ｂ入力にそれぞれｘ(m)を入力し、ｃ入力に「ｘ(m-1)＊ｙ(1)」の演算結果を入力し、
   第ｎ段、第ｍ列（但し、２≦ｎ≦Ｎ−１、１≦ｍ≦Ｎ−２）の全加算器のａ入力に第（ｎ−１）段、第（ｍ＋１）列の全加算器のＳ出力を入力し、ｂ入力に第（ｎ−１）段、第ｍ列の全加算器のＣ出力を入力し、ｃ入力に「ｘ（m-1）＊ｙ(n)」の演算結果を入力し、
   第ｎ段（但し、２≦ｎ≦Ｎ−１）、第（Ｎ−１）列の全加算器のａ入力に「ｘ(N-1)＊ｙ(n-1)」の演算結果を入力し、ｂ入力に第（ｎ−１）段、第（Ｎ−１）列の全加算器のＣ出力を入力し、ｃ入力に「ｘ(N-2)＊ｙ(n)」の演算結果を入力し、
   第Ｎ段、第ｍ列（但し、１≦ｍ≦Ｎ−２）の全加算器のａ入力に第（Ｎ−１）段、第（ｍ＋１）列の全加算器のＳ出力を入力し、ｂ入力に第（Ｎ−１）段、第ｍ列の全加算器のＣ出力を入力し、ｃ入力にはｍ≠１の場合に第Ｎ段、第（ｍ−１）列の全加算器のＣ出力を入力し、
   第Ｎ段、第（Ｎ−１）列の全加算器のａ入力に「ｘ(n-1)＊ｙ(n-1)」の演算結果を入力し、ｂ入力に第（Ｎ−１）段、第（Ｎ−１）列の全加算器のＣ出力を入力し、ｃ入力に第（Ｎ−２）列の全加算器のＣ出力を入力するように構成され、
   （Ｂ）前記加算回路は、
   ２つの入力ａ、ｂ及び２つの出力Ｃ、Ｓを有し、前記各入力ａ、ｂに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とする演算を行う第１〜第（Ｎ−１）の半加算器（ＨＡ）を有し、
   前記第ｎの半加算器（ｎ＝１〜Ｎ−１）は、ａ入力に第ｎ段、第１列の全加算器のＳ出力が入力され、ｂ入力には、ｎ＝２〜Ｎ−１の場合に第（ｎ−１）の半加算器のＣ出力が入力されｎ＝１の場合に「０」が入力され、第（Ｎ−１）の半加算器のＣ出力を第Ｎ段、第１列の全加算器のｃ入力に出力し、
   第１〜第（Ｎ−１）の半加算器のＳ出力を、それぞれＰ（１）〜Ｐ（Ｎ−１）とし、第Ｎ段、第ｍ列（但し、ｍ＝１〜Ｎ−１）の全加算器のＳ出力を、それぞれＰ（Ｎ）〜Ｐ（２Ｎ−２）とし、
   前記Ｐ（１）〜Ｐ（２Ｎ−２）の各ビットから、連続したＮ桁のビットを取り出して、前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」の演算結果とする。
3. 漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」で定義されるロジスティック写像Ｘt+1を演算する演算装置において、
   前記「Ｘt」、「Ｘt+1」はＮ桁の２進数で示され、前記漸化式を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とした場合に、下記構成を備える（Ａ）配列型乗算器、及び（Ｂ）加算回路を用いて前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」で示される演算を行うことを特徴とするロジスティック写像の演算装置、
   （Ａ）前記配列型乗算器は、
   第１列から第（Ｎ−１）列までの（Ｎ−１）個の全加算器からなる加算器群が、第１段から第（Ｎ−１）段まで設けられ、且つ、第Ｎ段には（Ｎ−２）個の加算器からなる加算器群が設けられ、更に、前記各段の全加算器は各段毎に１列ずつシフトして配置され、
   前記各全加算器は３つの入力ａ、ｂ、ｃ及び２つの出力Ｃ、Ｓを有し、前記各入力ａ、ｂ、ｃに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とし、３個のときに出力Ｓ、Ｃ共に「１」とする演算を行い、
   該配列型乗算器により、各桁がｘ(0)〜ｘ(N-1)で示される２進Ｎ桁の被乗算値「Ｘt」と、各桁がｙ(0)〜ｙ(N-1)で示される２進Ｎ桁の乗算値「notＸt」との乗算を実施する際に、
   第１段、第ｍ列（但し、１≦ｍ≦Ｎ−１）の全加算器のａ入力に「ｘ(m)＊ｙ(0)」の演算結果を入力し、ｂ入力にそれぞれｘ(m)を入力し、ｃ入力に「ｘ(m-1)＊ｙ(1)」の演算結果を入力し、
   第ｎ段、第ｍ列（但し、２≦ｎ≦Ｎ−１、ｍ≠Ｎ−１）の全加算器のａ入力に第（ｎ−１）段、第（ｍ＋１）列の全加算器のＳ出力を入力し、ｂ入力に第（ｎ−１）段、第ｍ列の全加算器のＣ出力を入力し、ｃ入力に「ｘ（m-1）＊ｙ(n)」の演算結果を入力し、
   第ｎ段（但し、２≦ｎ≦Ｎ−１）、第（Ｎ−１）列の全加算器のａ入力に「ｘ(N-1)＊ｙ(n-1)」の演算結果を入力し、ｂ入力に第（ｎ−１）段、第（Ｎ−１）列の全加算器のＣ出力を入力し、ｃ入力に「ｘ(N-2)＊ｙ(n)」の演算結果を入力し、
   第Ｎ段、第ｍ列（但し、１≦ｍ≦Ｎ−２）の全加算器のａ入力に第（Ｎ−１）段、第（ｍ＋１）列の全加算器のＳ出力を入力し、ｂ入力に第（Ｎ−１）段、第ｍ列の全加算器のＣ出力を入力し、ｃ入力にはｍ≠１の場合に第Ｎ段、第（ｍ−１）列の全加算器のＣ出力を入力するように構成され、
   （Ｂ）前記加算回路は、
   （Ｎ−３）個の、第１〜第（Ｎ−３）のキャリー計算器、及び２個の、第（Ｎ−２）の半加算器、及び第（Ｎ−１）の半加算器を備え、
   前記半加算器は、２つの入力ａ、ｂ及び２つの出力Ｃ、Ｓを有し、前記各入力ａ、ｂに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とする演算を行い、
   前記キャリー計算器は、２つの入力ａ、ｂ及び１つの出力Ｃを有し、前記各入力ａ、ｂに含まれる「１」の個数が２個のときに出力Ｃを「１」とし、それ以外の場合に「０」とする演算を行い、
   第ｎのキャリー計算器（但し、ｎ＝１〜Ｎ−３）は、ａ入力に第ｎ段、第１列の全加算器のＳ出力が入力され、ｂ入力にはｎ≠１の場合に第（ｎ−１）のキャリー計算器のＣ出力が入力され、ｎ＝１の場合に「０」が入力され、
   前記第（Ｎ−２）の半加算器は、ａ入力に第（Ｎ−２）段、第１列の全加算器のＳ出力が入力され、ｂ入力に第（Ｎ−３）のキャリー計算器のＣ出力が入力され、
   前記第（Ｎ−１）の半加算器は、ａ入力に第（Ｎ−１）段、第１列の全加算器のＳ出力が入力され、ｂ入力に第（Ｎ−２）のキャリー計算器のＣ出力が入力され、且つ、Ｃ出力を第Ｎ段、第１列の全加算器のｃ入力に出力し、
   前記第（Ｎ−２）の半加算器のＳ出力をＰ（Ｎ−２）、第（Ｎ−１）の半加算器のＳ出力をＰ（Ｎ−１）とし、
   第Ｎ段、第ｍ列（但し、ｍ＝１〜Ｎ−２）の全加算器のＳ出力を、それぞれＰ（Ｎ）〜Ｐ（２Ｎ−３）とし、
   Ｐ（Ｎ−２）〜Ｐ（２Ｎ−３）のＮ桁のビットを前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」の演算結果とする。
4. 漸化式「Ｘt+1＝４Ｘt（１−Ｘt）」で定義されるロジスティック写像Ｘt+1を演算する演算装置において、
   前記「Ｘt」、「Ｘt+1」はＮ桁の２進数で示され、前記漸化式を展開して「Ｘt+1＝４（Ｘt＊notＸt＋Ｘt）」とした場合に、下記構成を備える（Ａ）配列型乗算器を用いて前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」で示される演算を行うことを特徴とするロジスティック写像の演算装置、
   （Ａ）前記配列型乗算器は、
   第１列から第（Ｎ−１）列までの（Ｎ−１）個の加算器からなる加算器群が、第１段から第（Ｎ−１）段まで設けられ、且つ、第Ｎ段には（Ｎ−２）個の加算器からなる加算器群が設けられ、更に、前記各段の加算器は各段毎に１列ずつシフトして配置され、
   前記各加算器は３つの入力ａ、ｂ、ｃと２つの出力Ｃ、Ｓを有する全加算器、２つの入力ａ、ｂと２つの出力Ｃ、Ｓを有する半加算器、３つの入力ａ、ｂ、ｃと１つの出力Ｃを有するキャリー計算器、及び、３つの入力ａ、ｂ、ｃと１つの出力Ｓを有するサム計算器のうちのいずれかであり、
   前記各加算器は、各入力ａ、ｂ、ｃに含まれる「１」の個数が０個のときに出力Ｓ、Ｃ共に「０」とし、１個のときに出力Ｓのみを「１」とし、２個のときに出力Ｃのみを「１」とし、３個のときに出力Ｓ、Ｃ共に「１」とする演算を行い、
   該配列型乗算器により、各桁がｘ(0)〜ｘ(N-1)で示される２進Ｎ桁の被乗算値「Ｘt」と、各桁がｙ(0)〜ｙ(N-1)で示される２進Ｎ桁の乗算値「notＸt」との乗算を実施する際に、
   第１段の加算器群は、第１列が前記キャリー計算器、第２列が前記半加算器、その他の列が前記全加算器であり、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器のａ入力に「ｘ(m)*ｙ(0)」の演算結果を入力し、ｂ入力にそれぞれｘ(m)を入力し、更に、第２列を除く各列の加算器のｃ入力に「ｘ(m-1)＊ｙ(1)」の演算結果を入力し、
   第ｎ段（但し、２≦ｎ≦Ｎ−３）の加算器群は、第１列が前記キャリー計算器、第（ｎ＋１）列が前記半加算器、その他の列が前記全加算器であり、第（Ｎ−１）列の加算器のａ入力に「ｘ(N-1)＊ｙ(n-1)」の演算結果を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器のａ入力に第（ｎ−１）段、第（ｍ＋１）列の加算器のＳ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器のｂ入力に、第（ｎ−１）段、第ｍ列の加算器のＣ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１、（ｎ＋１）を除く）の加算器のｃ入力に「ｘ(m-1)＊ｙ(n)」の演算結果を入力し、
   第（Ｎ−２）段の加算器群は、第（Ｎ−１）列が前記半加算器、その他の列が前記全加算器であり、第（Ｎ−１）列の加算器のａ入力に「ｘ(N-1)＊ｙ(N-3)」の演算結果を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器のａ入力に第（Ｎ−３）段、第（ｍ＋１）列の加算器のＳ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器のｂ入力に、第（Ｎ−３）段、第ｍ列の加算器のＣ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器のｃ入力に「ｘ(m-1)＊ｙ(N-2)」の演算結果を入力し、
   第（Ｎ−１）段の加算器群は、第（Ｎ−１）列が前記サム計算器、その他の列が前記全加算器であり、第（Ｎ−１）列の加算器のａ入力に「ｘ(N-1)*ｙ(N-2)」の演算結果を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器のａ入力に第（Ｎ−２）段、第（ｍ＋１）列、の加算器のＳ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器のｂ入力に、第（Ｎ−２）段、第ｍ列の加算器のＣ出力を入力し、第ｍ列（但し、１≦ｍ≦Ｎ−１）の加算器のｃ入力に「ｘ(m-1)＊ｙ(N-1)」の演算結果を入力し、
   第Ｎ段の加算器群は、第１列が前記半加算器、第（Ｎ−２）列が前記サム計算器、その他の列が前記全加算器であり、第ｍ列（但し、１≦ｍ≦Ｎ−２）の加算器のａ入力に第（Ｎ−１）段、第（ｍ＋１）列の加算器のＳ出力を入力し、ｂ入力に第（Ｎ−１）段、第ｍ列、の加算器のＣ出力を入力し、第ｍ列（但し、２≦ｍ≦Ｎ−２）のｃ入力に第Ｎ段、第（ｍ−１）列の加算器のＣ出力を入力するように構成され、
   第（Ｎ−２）段、１列の加算器のＳ出力をＰ（Ｎ−２）、第（Ｎ−１）段、１列の加算器のＳ出力をＰ（Ｎ−１）とし、且つ、第Ｎ段、第１〜第（Ｎ−２）列の加算器のＳ出力をそれぞれＰ（Ｎ）〜Ｐ（２Ｎ−３）とし、
   Ｐ（Ｎ−２）〜Ｐ（２Ｎ−３）のＮ桁のビットを前記展開した漸化式の「Ｘt＊notＸt＋Ｘt」の演算結果とする。

Images