(57)【要約】      （修正有）【課題】最短の符号付２進表現を算出する手段を提供すること。【解決手段】入力値に対する最短の符号付２進表現を算出させるためのプログラムにおいて、ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリ内のメモリテーブル先頭に格納し、ΔXおよび∇Xを読み出し、∇Xを前記メモリテーブルから削除し、前記ΔXの２進表現における非零最下位ビット2を求、算術演算ΔX'=ΔX-2および集合演算∇X' を計算し、前記ΔX'が０の場合、入力値に対する最短の符号付２進表現として前記∇X'を出力し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記メモリテーブルの最後尾に格納し、算術演算ΔX''=および集合演算∇X''を計算し、前記ΔX''が０の場合、入力値に対する最短の符号付２進表現として前記∇X''を出力し、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記メモリテーブルの最後尾に格納する。【選択図】図３
2008176243.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに入力値に対する最短の符号付２進表現を算出させるためのプログラムにおいて、
ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリ内のデータテーブル先頭に格納し、
前記メモリ内のデータテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記データテーブルから削除する第１のステップと、
前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、
算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、
前記ΔX'が０の場合、入力値に対する最短の符号付２進表現として前記∇X'を出力し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記データテーブルの最後尾に格納する第４のステップと、
算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第５のステップと、
前記ΔX''が０の場合、入力値に対する最短の符号付２進表現として前記∇X''を出力し、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記データテーブルの最後尾に格納して第１のステップに進む第６のステップと、
を含む処理を前記コンピュータに実行させるためのプログラム。
【請求項２】
コンピュータに入力値に対する所定の要素数以下の符号付２進表現を算出させるためのプログラムにおいて、
ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリテーブル先頭に格納し、
前記メモリテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記メモリテーブルから削除する第１のステップと、
前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、
算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、
前記∇X'の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第４のステップと、
前記ΔX'が０の場合、前記∇X'を出力用テーブルに格納し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記メモリテーブルの最後尾に格納する第５のステップと、
算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第６のステップと、
前記∇X''の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第７のステップと、
前記ΔX''が０の場合、前記∇X''を前記出力用テーブルに格納して第１のステップに戻り、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記データテーブルの最後尾に格納して第１のステップに戻る第８のステップと、
を含む処理を前記コンピュータに実行させるためのプログラム。
【請求項３】
２のべき乗の集合で表される前記∇X'および前記∇X''を前記∇X'および前記∇X'に含まれる要素のうち、正の値の要素の合計を∇X+とし、負の値の要素の合計の絶対値を∇X-として、前記∇X'および前記∇X''の要素を∇X+と∇X-の組で格納することを特徴とする請求項１または２記載のプログラム
【請求項４】
前記所定の要素数をZとしたときに、2Z個の前記ΔXおよび前記∇Xの組を格納可能とするように前記メモリテーブルの容量を確保することを特徴とする請求項２記載のプログラム。
【請求項５】
前記所定の要素数を前記入力値ΔXの最短の符号付２進表現のハミングウェイトHW(ΔX)とあらかじめ定められたキャリー値cとを加算した値とし、前記入力値が2nを法とする自然数であるときに、
(n+1)/2以下の最大の自然数をmとしたとき、最大で2m+c個の前記ΔXおよび前記∇Xの組を格納可能とするように前記メモリテーブルの容量を確保することを特徴とする請求項２記載のプログラム。
【請求項６】
入力値に対する最短の符号付２進表現を算出する方法おいて、
ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリ内のデータテーブル先頭に格納し、
前記メモリ内のデータテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記データテーブルから削除する第１のステップと、
前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、
算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、
前記ΔX'が０の場合、入力値に対する最短の符号付２進表現として前記∇X'を出力し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記データテーブルの最後尾に格納する第４のステップと、
算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第５のステップと、
前記ΔX''が０の場合、入力値に対する最短の符号付２進表現として前記∇X''を出力し、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記データテーブルの最後尾に格納して第１のステップに進む第６のステップと、
を含む符号付２進表現算出方法。
【請求項７】
入力値に対する所定の要素数以下の符号付２進表現を算出する方法において、
ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリテーブル先頭に格納し、
前記メモリテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記メモリテーブルから削除する第１のステップと、
前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、
算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、
前記∇X'の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第４のステップと、
前記ΔX'が０の場合、前記∇X'を出力用テーブルに格納し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記メモリテーブルの最後尾に格納する第５のステップと、
算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第６のステップと、
前記∇X''の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第７のステップと、
前記ΔX''が０の場合、前記∇X''を前記出力用テーブルに格納して第１のステップに戻り、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記データテーブルの最後尾に格納して第１のステップに戻る第８のステップと、
を含む符号付２進表現算出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号付２進表現の算出プログラムおよび算出方法に関する。
【背景技術】
【０００２】
現在、標準的に用いられているＭＤ５やＳＨＡ−１等のハッシュ関数の安全性を評価する場合、与えられた変数XおよびX'の算術差分ΔX=X'-Xを最小の項数で表現したものやその項数を使用している。
【０００３】
例えば、ΔX=0xdb=219の場合、ビット単位に分割して表すと
ΔX=27+26+24+23+21+20=(0,…,0,1,1,0,1,1,0,1,1)
となり、非ゼロ要素の個数は６である。
【０００４】
また、符号付の表現で表すと、
+28-25-22-20=0x100-0x25=(0,…,0,+1,0,0,0,0,0,0,0,0,-1,0,0,-1,0,-1)
となり、非ゼロ要素の個数は４である。
【０００５】
以下において、ΔXを符号付ビット表現に変換したものを∇Xと表し、符号付き２進表現と呼ぶ。∇Xの表現において含まれる非ゼロ要素の個数をHW(∇X)と表し、∇Xのハミングウェイトと呼ぶ。
【０００６】
与えられたΔXから得られる全ての∇Xの表現の中で、非ゼロ要素の個数が最も少ない表現を∇Xの最短表現と呼び、該∇Xの最短表現に含まれる非ゼロ要素の個数をHW(ΔX)と表し、ΔXのハミングウェイトと呼ぶ。与えられたΔXから得られる∇Xの表現は一意的ではないが、HW(ΔX)の値は、ΔXから一意的に決まる。
【０００７】
HW(ΔX)を求める方法としては、以下のような方法が用いられていた。
与えられたΔX=X'-XをX'=X+ΔXと変形し、任意に与えたXからX'を計算し、XとX'の２進表示の第i桁目Xi',Xiより、∇Xの第i桁目∇Xiを
∇Xi＝Xi'- Xi∈｛0,1,-1｝
として求める。上記手順を全てのXについて行うことで、ΔXに対する∇Xの全ての表現を得ることが出来る。よって、全てのHW(∇X)の値が得られるため、その最小値であるHW(ΔX)が求めることが出来る。
【０００８】
特許文献１には、加算演算において、符号付２進表現を算出する技術が記載されている。
【特許文献１】特開２００１−５６４１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、従来の方法では、HW(ΔX)を得るために全てのXを試す必要があり、計算量が非常に大きくなるという問題があった。例えば、Xが32ビットの自然数（232を法とした自然数）の場合、HW(ΔX)を求めるためには、232回の試行が必要となり、計算上のボトルネックとなっていた。
【００１０】
本発明の課題は、効率的な符号付２進数表現の算出プログラムおよび算出方法を提供することである。
【課題を解決するための手段】
【００１１】
本発明は、上記課題を解決するため、下記のような構成を採用した。
すなわち、本発明の一態様によれば、本発明のプログラムは、コンピュータに入力値に対する最短の符号付２進表現を算出させるためのプログラムにおいて、ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリ内のデータテーブル先頭に格納し、前記メモリ内のデータテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記データテーブルから削除する第１のステップと、前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、前記ΔX'が０の場合、入力値に対する最短の符号付２進表現として前記∇X'を出力し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記データテーブルの最後尾に格納する第４のステップと、算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第５のステップと、前記ΔX''が０の場合、入力値に対する最短の符号付２進表現として前記∇X''を出力し、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記データテーブルの最後尾に格納して第１のステップに進む第６のステップと、を含むことを特徴とする。
【００１２】
本発明の一態様によれば、本発明のプログラムは、コンピュータに入力値に対する所定の要素数以下の符号付２進表現を算出させるためのプログラムにおいて、ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリテーブル先頭に格納し、前記メモリテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記メモリテーブルから削除する第１のステップと、前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、前記∇X'の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第４のステップと、前記ΔX'が０の場合、前記∇X'を出力用テーブルに格納し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記メモリテーブルの最後尾に格納する第５のステップと、算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第６のステップと、前記∇X''の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第７のステップと、前記ΔX''が０の場合、前記∇X''を前記出力用テーブルに格納して第１のステップに戻り、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記データテーブルの最後尾に格納して第１のステップに戻る第８のステップと、を含むことを特徴とする。
【００１３】
また、本発明のプログラムは、２のべき乗の集合で表される前記∇X'および前記∇X''を前記∇X'および前記∇X'に含まれる要素のうち、正の値の要素の合計を∇X+とし、負の値の要素の合計の絶対値を∇X-として、前記∇X'および前記∇X''の要素を∇X+と∇X-の組で格納することが望ましい。
【００１４】
また、本発明のプログラムは、前記所定の要素数をZとしたときに、2Z個の前記ΔXおよび前記∇Xの組を格納可能とするように前記メモリテーブルの容量を確保することが望ましい。
【００１５】
また、本発明のプログラムは、前記所定の要素数を前記入力値ΔXの最短の符号付２進表現のハミングウェイトHW(ΔX)とあらかじめ定められたキャリー値cとを加算した値とし、前記入力値が2nを法とする自然数であるときに、(n+1)/2以下の最大の自然数をmとしたとき、最大で2m+c個の前記ΔXおよび前記∇Xの組を格納可能とするように前記メモリテーブルの容量を確保することが望ましい。
【発明の効果】
【００１６】
本発明によれば、符号付２進表現の最短表現を効率良く求めることが出来る。
【発明を実施するための最良の形態】
【００１７】
以下、図面を用いて本発明の実施の形態を説明する。
本発明の第１の実施の形態に係る演算装置は、与えられた自然数ΔXの最短の符号付２進表現およびそのハミングウェイトを求める装置である。なお、実施の形態で用いられる変数は３２ビットの変数であり、演算装置は232を法とした算術演算を行うものとする。
【００１８】
図１は、本発明の第１の実施の形態に係る演算装置の機能ブロック図である。
演算装置１００の初期設定手段１０１は、演算の対象となる入力値ΔX（自然数）を受信し、符号付２進表現の要素の集合∇Xをφ（空集合）とし、ΔXおよび∇Xを組としてメモリ１０７内のメモリテーブル１０８の先頭に格納する。
【００１９】
読み出し削除手段１０２は、メモリテーブル１０８の先頭のΔXおよび∇Xを読み出し、該データをメモリテーブル１０８から削除する。
非零最下位ビット算出手段１０３は、ΔXの２進表現において、非零の最下位ビット2iを求める。
【００２０】
演算手段１０４は、読み出し削除手段１０２で読み出したΔX、∇Xおよび非零最下位ビット算出手段１０３で求めた非零最下位ビット2iに基づいて、ΔX'=ΔX-2i、∇X'=(+2i)∪∇X、ΔX''=ΔX+2i、および∇X''=(-2i)∪∇Xを計算する。
【００２１】
判定手段１０５は、ΔX'およびΔX''が０であるかを判定する。
出力手段１０６は、判定手段１０５の判定結果に基づき、ΔX'、∇X'、ΔX''、および∇X''をメモリテーブル１０８のデータの最後尾に格納する。または与えられたΔXの最短の符号付２進表現∇XおよびΔXのハミングウェイトHW(ΔX)として、∇X'および∇X'の要素の個数若しくは∇X''および∇X''の要素の個数を出力する。
【００２２】
図２は、本発明の第１の実施の形態に係るメモリテーブルのデータ構造の例を示す図である。
メモリテーブル１０８はメモリ１０７内に在り、ΔXと∇Xとが関連付けられて格納されている。
【００２３】
一般に、入力値ΔXの符号付２進表現におけるハミングウェイトの最小値HW(ΔX)がhであることがあらかじめ分かっているときは、最短の符号付２進表現の計算にはメモリ空間として、2h個のΔXと∇Xの組を格納出来る容量があればよいことが理論的に示される。故に、HW(ΔX)の値が分かっているときは、2hw(ΔX)個のΔXと∇Xの組を格納出来るようにメモリ空間を確保することで、無駄なメモリを確保することを避けることが出来る。
【００２４】
また、一般に入力値ΔXの値が2nを法とした算術値のみを扱う場合、HW(ΔX)の最大値は、(n+1)/2以下の最大の自然数となる。(n+1)/2以下の最大の自然数をmとすると、最短の符号付２進表現の計算にはメモリ空間として、2m個のΔXと∇Xの組を格納出来る容量があればよい。よって、入力値ΔXの値が2nを法とした算術値のみを扱う場合、(n+1)/2以下の最大の自然数をmとすると、最短の符号付２進表現の計算にはメモリ空間として、最大で2m個のΔXと∇Xの組を格納出来る容量することで無駄なメモリの確保を避けることが出来る。
【００２５】
従って、第１の実施の形態ではΔXは32ビットであるため、HW(ΔX)の最大値は16となる。よって図２のメモリテーブル１０８は216=65526個のΔXと∇Xの組を格納できるようになっている。
【００２６】
メモリテーブル１０８において、最左列はΔＸ、２列目から最右列までは∇Ｘが記述さ
れる。また、メモリテーブルのi行目の要素はM[i]と表され、i行目の要素のうちΔXはM[i]1、i行目の要素のうち∇XはM[i]2と表される。
【００２７】
図２において、メモリテーブルＭの２行目には、ΔXとして0xdc、∇Xとして{-20}が記述されている。すなわち、M[2]=[0xdc,{-20}]、M[2]1=0xdc、M[2]1={-20}である。
図３は、本発明の第１の実施の形態に係る演算装置の処理のフローチャートである。
【００２８】
ステップＳ３０１において、初期設定手段１０１は、最短の符号付２進表現の算出の対象となる入力値ΔＸ（自然数）を受信し、符号付２進表現の要素の集合∇Xをφ（空集合）とし、ΔXおよび∇Xを組としてメモリ１０７内のメモリテーブル１０８の先頭に格納する。
【００２９】
ステップＳ３０２において、読み出し削除手段１０２は、メモリテーブル１０８の先頭の要素ΔXおよび∇Xを読み出し、読み出したΔXおよび∇Xをメモリテーブル１０８から削除する。例えば、メモリテーブル１０８の内容が図２の状態であった場合、１行目の要素が空のため、メモリテーブル１０８の先頭は２行目となり、ΔXとして0xdc、∇Xとして{-20}が読み出され、削除される。
【００３０】
ステップＳ３０３において、非零最下位ビット算出手段１０３は、読み出したΔXの２進表現において、非零の最下位ビットの値2iを求める。すなわち、ΔXをべき乗の集合として表したときの最小の要素である。例えば、ΔXが0xdcの場合、２進表現で表すと+27+26+24+23+22となるので、非零最下位ビットは22となる。
【００３１】
ステップＳ３０４において、演算手段１０４は、ΔX'=ΔX-2iおよび∇X'=∇X∪(+2i)を計算する。
ステップＳ３０５において、判定手段１０５は、ΔX'が０であるか判定し、０であればステップＳ３０６に進み、０でなければステップＳ３０７に進む。
【００３２】
ステップＳ３０６において、出力手段１０６は、入力値ΔXのハミングウェイトHW(ΔX)として∇X'の要素数、入力値ΔXの最短の符号付２進表現∇Xとして∇X'を出力する。
ステップＳ３０７において、出力手段１０６は、ステップＳ３０４で計算したΔX'および∇X'をメモリテーブル１０８の最後尾に格納する。例えば、メモリテーブル１０８の内容が図２の状態であった場合、メモリテーブル１０８は３行目まで使用されているので、ΔX'および∇X'はメモリテーブル１０８の最後尾、すなわち４行目に格納される。
【００３３】
ステップＳ３０８において、演算手段１０４は、ΔX''=ΔX+2iおよび∇X''=∇X∪(-2i)を計算する。
ステップＳ３０９において、判定手段１０５は、ΔX''が０であるか判定し、０であればステップＳ３１０に進み、０でなければステップＳ３１１に進む。
【００３４】
ステップＳ３１０において、出力手段１０６は、入力値ΔXのハミングウェイトHW(ΔX)として∇X''の要素数、入力値ΔXの最短の２進表現∇Xとして∇X''を出力する。
ステップＳ３１１において、出力手段１０６は、ステップＳ３０８で計算したΔX''および∇X''をメモリテーブル１０８の最後尾に格納し、ステップＳ３０２に戻る。
【００３５】
本発明の第１の実施の形態によれば、効率的に入力値ΔXに対する最短の符号付２進表現を得ることが出来る。
次に具体的な数値を用いた場合の例を図３の処理と対応させて説明する。
【００３６】
ここでは、入力値ΔX=0xdb=219の最短の符号付２進表現およびハミングウェイトを求め
る場合を説明する。ΔXを通常の２進表現で表した場合、ΔX=(0,…,0,1,1,0,1,1,0,1,1)である。
【００３７】
・初期設定
初期設定として、ΔXと∇Xをメモリテーブルの先頭M[1]に格納する（ステップＳ３０１）。ここで∇X=φである。
よって、M[1]=[ΔX=0xdb=(0,…,0,1,1,0,1,1,0,1,1),∇X=φ={}]となる。
【００３８】
・演算開始
１．∇X'、∇X''の要素数が１のループ
(a)メモリテーブルの先頭のデータを読み出すと（ステップＳ３０２）、ΔX = M[1]1=0xdb,∇X=M[1]2=φである。
(b)読み出したM[1]を消去する（ステップＳ３０２）。
(c)ΔXの非零最下位ビットを算出すると20となる（ステップＳ３０３）。
ΔX'および∇X'を計算すると（ステップＳ３０４）、
ｉ．ΔX'=ΔX-20=(0,…,0,1,1,0,1,1,0,1,0)=0xda,∇X'={+20}となる。
ΔX'が０であるか判定すると（ステップＳ３０４）、ΔX'=0xda≠0のため、ΔX'および∇X'をデータテーブルの最後尾に格納する（ステップＳ３０７）。
ii．メモリテーブルの最後尾はM[2]であるため、M[2]=[0xda,{+20}]となる。
そして、ΔX''および∇X''を計算すると（ステップＳ３０８）、
iii．ΔX''=ΔX+20=(0,…,0,1,1,0,1,1,1,0,0)=0xdc,∇X''={-20}となる。
ΔX''が０であるか判定すると（ステップＳ３０９）、ΔX''=0xdc≠0のため、ΔX''および∇X''をデータテーブルの最後尾に格納する（ステップＳ３１１）。
iv．メモリテーブルの最後尾はM[3]であるため、M[3]=[0xdc,{-20}]となる。
そして、メモリテーブルの先頭のデータを読み出す処理（ステップＳ３０２）に戻る。
以下、同様の処理を繰り返す。以下の説明において、同様の処理を行うことから簡単のため、重複する説明は省略し、読み出したΔXの値やメモリテーブルに格納する内容等のみを記載する。
【００３９】
２．∇X'、∇X''の要素数が２のループ
(a)ΔX=M[2]1=0xda,∇X=M[2]2={+20}
(b)M[2]を消去
(c)ΔXの非零最下位ビット=21
ｉ．ΔX'=ΔX-21=(0,…,0,1,1,0,1,1,0,0,0)=0xd8,∇X'={+21+20}
ii．M[4]=[0xd8,{+21+20}]
iii．ΔX''=ΔX+21=(0,…,0,1,1,0,1,1,1,0,0)= 0xdc,∇X''={-21+20}
iv．M[5] = [0xdc,{-21+20}]
(d)ΔX=M[3]1=0xdc,∇X=M[3]2={-20}
(e)M[3]を消去
(f)ΔXの非零最下位ビット=22
ｉ．ΔX'=ΔX-22=(0,…,0,1,1,0,1,1,0,0,0)=0xd8,∇X'={+21-20}
ii．M[6]=[0xd8,{+22-20}]
iii．ΔX''=ΔX+22=(0,…,0,1,1,1,0,0,0,0,0)= 0xe0,∇X''={-21-20}
iv．M[7]=[0xe0,{-22-20}]
【００４０】
３．∇X'、∇X''の要素数が３のループ
(a)ΔX=M[4]1=0xd8,∇X=M[4]2={+21+20}
(b)M[4]を消去
(c)ΔXの非零最下位ビット=23
ｉ．ΔX'=ΔX-23=(0,… ,0,1,1,0,1,0,0,0,0)=0xd0,∇X'={+23+21+20}
ii．M[8]=[0xd0,{+23+21+20}]
iii．ΔX''=ΔX+23=(0,…,0,1,1,1,0,0,0,0,0)=0xe0,∇X''={-23+21+20}
iv．M[9]=[0xe0,{-23+21+20}]
(d)ΔX=M[5]1=0xdc,∇X=M[5]2={-21+20}
(e)M[5]を消去
(f)ΔXの非零最下位ビット=22
ｉ．ΔX'=ΔX-22=(0,… ,0,1,1,0,1,1,0,0,0)= 0xd8,∇X'={+22-21+20}
ii．M[10]=[0xd8,{+22-21+20}]
iii．ΔX''=ΔX+22=(0,… ,0,1,1,1,0,0,0,0,0)= 0xe0,∇X''={-22-21+20}
iv．M[11]=[0xe0,{-22-21+20}]
(g)ΔX=M[6]1=0xd8,∇X=M[6]2={+22-20}
(h)M[6]を消去
(i)ΔXの非零最下位ビット=23
ｉ．ΔX'=ΔX-23=(0,…,0,1,1,0,1,0,0,0,0)=0xd0,∇X'={+23+22-20}
ii．M[12]=[0xd0,{+23+22-20}]
iii．ΔX''=ΔX+23=(0,…,0,1,1,1,0,0,0,0,0)= 0xe0,∇X''={-23+22-20}
iv．M[13]=[0xe0,{-23+22-20}]
(j)ΔX=M[7]1=0xe0,∇X=M[7]2={-22-20}
(k)M[7]を消去
(l)ΔXの非零最下位ビット= 25
ｉ．ΔX'=ΔX-25=(0,…,0,1,1,0,0,0,0,0,0)=0xc0,∇X'={+25-22-20}
ii．M[14]=[0xc0,{+25-22-20}]
iii．ΔX''=ΔX+25=(0,…,1,0,0,0,0,0,0,0,0)=0x100,∇X''={-25-22-20}
iv．M[15]=[0x100,{-25-22-20}]
【００４１】
４．∇X'、∇X''の要素数が４のループ
(a)ΔX=M[8]1=0xd0,∇X=M[8]2={+23+21+20}
(b)M[8]を消去
(c)ΔXの非零最下位ビット=24
ｉ．ΔX'=ΔX-24=(0,…,0,1,1,0,0,0,0,0,0)=0xc0,∇X'={+24+23+21+20}
ii．M[16]=[0xc0,{+24+23+21+20}]
iii．ΔX''=ΔX+24=(0,…,0,1,1,1,0,0,0,0,0)=0xe0,∇X''={-24+23+21+20}
iv．M[17]=[0xe0,{-24+23+21+20}]
(d)ΔX=M[9]1= 0xe0,∇X=M[9]2={-23+21+20}
(e)M[9]を消去
(f)ΔXの非零最下位ビット=25
ｉ．ΔX'=ΔX-25=(0,…,0,1,1,0,0,0,0,0,0)=0xc0,∇X'={+25-23+21+20}
ii．M[18]=[0xc0,{+25-23+21+20}]
iii．ΔX''=ΔX+25=(0,…,0,1,0,0,0,0,0,0,0,0)=0x100,∇X''={-25-23+21+20}
iv．M[19]=0x100,{-25-23+21+20}]
(g)ΔX=M[10]1=0xd8,∇X=M[10]2={+22-21+20}
(h)M[10]を消去
(i)ΔXの非零最下位ビット=23
ｉ．ΔX'=ΔX-23=(0,…,0,1,1,0,1,0,0,0,0)=0xd0,∇X'={+23+22-21+20}
ii．M[20]=[0xd0,{+23+22-21+20}]
iii．ΔX''=ΔX+23=(0,…,0,1,1,1,0,0,0,0,0)=0xe0,∇X''={-23+22-21+20}
iv．M[21]=[0xe0,{-23+22-21+20}]
(j)ΔX=M[11]1=0xe0,∇X=M[11]2={-22-21+20}
(k)M[11]を消去
(l)ΔXの非零最下位ビット= 25
ｉ．ΔX'=ΔX-25=(0,…,0,1,1,0,0,0,0,0,0)=0xd0,∇X'={+25-22-21+20}
ii．M[22]=[0xd0,{+25-22-21+20}]
iii．ΔX''=ΔX+25=(0,…,0,1,0,0,0,0,0,0,0,0)=0x100,∇X''={-25-22-21+20}
iv．M[23]=[0x100,{-25-22-21+20}] (m)ΔX=M[12]1=0xd0,∇X=M[12]2={+23+22-20}
(n)M[12]を消去
(o)ΔXの非零最下位ビット=24
ｉ．ΔX'=ΔX-24=(0,…,0,1,1,0,0,0,0,0,0)=0xc0,∇X'={+24+23+22-20}
ii．M[24]=[0xc0,{+24+23+22-20}]
iii．ΔX''=ΔX+24=(0,…,0,1,1,1,0,0,0,0,0)=0xe0,∇X''={-24+23+22-20}
iv．M[25]=[0xe0,{-24+23+22-20}]
(p)ΔX=M[13]1=0xe0,∇X=M[13]2={-23+22-20}
(q)M[13]を消去
(r)ΔXの非零最下位ビット=25
ｉ．ΔX'=ΔX-25=(0,…,0,1,1,0,0,0,0,0,0)=0xc0,∇X'={+25-23+22-20}
ii．M[26]=[0xc0,{+25-23+22-20}]
iii．ΔX''=ΔX+25=(0,…,0,1,0,0,0,0,0,0,0,0)=0x100,∇X''={-25-23+22-20}
iv．M[27]=[0x100,{-25-23+22-20}] (s)ΔX=M[14]1=0xc0,∇X=M[14]0={+25-22-20}
(t)M[14]を消去
(u)ΔXの非零最下位ビット= 26
ｉ．ΔX'=ΔX-26=(0,…,0,1,0,0,0,0,0,0,0)=0x80,∇X'={+26+25-22-20}
ii．M[28]=[0x80,{+26+25-22-20}]
iii．ΔX''=ΔX+26=(0,…,0,1,0,0,0,0,0,0,0,0)= 0x100,∇X''={-26+25-22-20}
iv．M[29]=[0x100,{-26+25-22-20}]
(v)ΔX=M[15]1=0x100,∇X=M[7]0={-25-22-20}
(w)M[15]を消去
(x)ΔXの非零最下位ビット= 28
ｉ．ΔX'=ΔX-28=(0,…,0,0,0,0,0,0,0,0,0)=0x0,∇X'={+28-25-22-20}
ΔX'が０であるか判定すると（ステップＳ３０４）、ΔX'=0x0=0のため、ループを抜ける。
【００４２】
５．出力
∇X'の要素数として4および∇X'={+28-25-22-20}を出力する（ステップＳ３０６）。
ここで、∇X'の要素数はΔXのハミングウェイトHW(ΔX)、∇X'はΔXの最短の符号付２進表現∇Xに該当する。よって、入力値ΔXのハミングウェイトとしてHW(ΔX)=HW(+28-25-22-20)=4、入力値ΔXの最短の符号付２進表現∇Xとして∇X = {+28-25-22-20}が得られる。
【００４３】
上記方法によれば、符号付２進数表現の最短表現を効率良く求めることが出来る。
そして、上記方法を利用して符号付２進数表現の最短表現を用いるハッシュ関数の安全性の評価を効率良く行うことが出来る。
【００４４】
ハッシュ関数の安全性の評価を行う際には、最短の２進表現だけでなく、所定の要素数以下の２進表現の全てが必要となる場合がある。次に所定の要素数以下の２進表現の全てを算出する演算装置について説明する。
【００４５】
図４は、本発明の第２の実施の形態に係る演算装置の機能ブロック図である。
演算装置４００は、入力値ΔX（自然数）の所定の要素数以下の符号付２進表現を算出する。所定の要素数としては、演算装置４００に入力されるキャリー値c（自然数）とΔXのハミングウェイトHW(ΔX)を加算したものを用いる。
【００４６】
初期設定手段４０１は、演算の対象となる入力値ΔXおよびキャリー値cを受信し、符号付２進表現の要素の集合∇Xをφ（空集合）とし、ΔXおよび∇Xを組としてメモリ１０６内のメモリテーブル４０８の先頭に格納する。
【００４７】
読み出し削除手段４０２は、メモリテーブル４０８の先頭のΔXおよび∇Xを読み出し、該データをメモリ４０６から削除する。
非零最下位ビット算出手段４０３は、ΔXの２進表現において、非零の最下位ビット2iを求める。
【００４８】
演算手段４０４は、読み出し削除手段４０２で読み出したΔX、∇Xおよび非零最下位ビット算出手段４０３で求めた最下位ビット2iに基づいて、ΔX'=ΔX-2i、∇X'=(+2i)∪∇X、ΔX''=ΔX+2i、および∇X''=(-2i)∪∇Xを計算する。
【００４９】
判定手段４０５は、∇X'および∇X''の要素数が所定の値を超えているかを判定する。
出力手段４０６は、判定手段４０５の判定結果に基づき、∇X'または∇X''を出力用テーブルに格納する。またはΔX'、∇X'、ΔX''、および∇X''をメモリテーブル４０８の最後尾に格納する。または入力値ΔXの所定の要素数以下の符号付２進表現として、出力用テーブルの内容を出力する。
【００５０】
第２の実施の形態において、演算時にメモリテーブル４０８がどのくらいの要素を格納できれば良いかが問題となるが、所定の要素数Z以下の符号付２進表現を求めるときには、メモリテーブル４０８は、2Z個のΔXと∇Xの組を格納できる容量があればよいことが理論的に示される。よって、所定の要素数ZをHW(ΔX)+cとしたときに、HW(ΔX)があらかじめ分かっているときには、2HW(ΔX)+c個のΔXと∇Xの組を格納出来るようにメモリ空間を確保することで、無駄なメモリの確保を避けることが出来る。
【００５１】
また上述のように、一般に入力値ΔXの値が2nを法とした算術値のみを扱う場合、HW(ΔX)の最大値Yは、(n+1)/2以下の最大の自然数となる。(n+1)/2以下の最大の自然数をmとすると、最短の符号付２進表現の計算にはメモリ空間として、2m個のΔXと∇Xの組を格納出来る容量があればよい。よって、入力値ΔXの値が2nを法とした算術値のみを扱う場合、(n+1)/2以下の最大の自然数をmとし、所定の要素数を入力値ΔXの最短の符号付２進表現のハミングウェイトHW(ΔX)とあらかじめ定められたキャリー値cとを加算した値とした場合、所定の要素数以下の符号付２進表現の計算にはメモリ空間として、最大で2m+c個のΔXと∇Xの組を格納出来る容量があればよい。最大で2m+c個のΔXと∇Xの組を格納出来るようにメモリ空間を確保することで、無駄なメモリの確保を避けることが出来る。
【００５２】
図５は、本発明の第２の実施の形態に係る演算装置の処理のフローチャートである。
ステップＳ５０１において、初期設定手段４０１は、所定の要素数以下の符号付２進表現の算出の対象となる入力値ΔＸ（自然数）およびキャリー値cを受信し、符号付２進表現の要素の集合∇Xをφ（空集合）とし、ΔXおよび∇Xを組としてメモリ４０７内のメモリテーブル４０８の先頭に格納する。また、第２の実施の形態においては、入力値ΔXのハミングウェイトHW(ΔX)としたとき、所定の要素数をHW(ΔX)+cとする。
【００５３】
ステップＳ５０２において、読み出し削除手段４０２は、メモリテーブル４０８の先頭の要素ΔXおよび∇Xを読み出し、読み出したΔXおよび∇Xをメモリテーブル４０８から削除する。
【００５４】
ステップＳ５０３において、非零最下位ビット算出手段４０３は、読み出したΔXの２進表現において、非零の最下位ビットの値2iを求める。すなわち、ΔXをべき乗の集合として表したときの最小の要素である。例えば、ΔXが0xdcの場合、２進表現で表すと+27+2
6+24+23+22となるので、非零最下位ビットは22となる。
【００５５】
ステップＳ５０４において、演算手段４０４は、ΔX'=ΔX-2iおよび∇X'=∇X∪(+2i)を計算する。
ステップＳ５０５において、ΔXのハミングウェイトHW(ΔX)が設定済みかつ∇X'の要素数が所定の値（第２の実施の形態においてはHW(ΔX)+c）を超えているか判定し、ハミングウェイトHW(ΔX)が設定済みかつ∇X'の要素数がHW(ΔX)+cを超えている場合、ステップＳ５０６に進み、そうでなければステップＳ５０７に進む。
【００５６】
ステップＳ５０６において、出力手段４０６は、出力用テーブル４０９の内容を出力する。該出力テーブルの内容が入力値ΔXの所定の要素数以下の符号付２進表現となる。
ステップＳ５０７において、判定手段４０５は、ΔX'が０であるか判定し、０であればステップＳ５０８に進み、０でなければステップＳ５１１に進む。
【００５７】
ステップＳ５０８において、判定手段４０５は、ΔX'またはΔX''が初めて０になったか判定を判定し、初めてであればステップＳ５０９に進み、初めてでなければステップＳ５１０に進む。
【００５８】
ステップＳ５０９において、出力手段４０６は、∇X'の要素数を入力値ΔXのハミングウェイトHW(ΔX)として設定する。
ステップＳ５１０において、出力手段４０６は、∇X'を出力用テーブル４０９に格納し、ステップＳ５１２に進む。
【００５９】
ステップＳ５１１において、出力手段４０６は、ステップＳ５０４で計算したΔX'および∇X'をメモリテーブル４０８の最後尾に格納する。
ステップＳ５１２において、演算手段４０４は、ΔX''=ΔX+2iおよび∇X''=∇X∪(-2i)を計算する。
【００６０】
ステップＳ５１３において、ΔXのハミングウェイトHW(ΔX)が設定済みかつ∇X''の要素数が所定の値（第２の実施の形態においてはHW(ΔX)+c）を超えているか判定し、ハミングウェイトHW(ΔX)が設定済みかつ∇X''の要素数がHW(ΔX)+cを超えている場合、ステップＳ５０６に進み、そうでなければステップＳ５１４に進む。
【００６１】
ステップＳ５１４において、判定手段４０５は、ΔX''が０であるか判定し、０であればステップＳ５１５に進み、０でなければステップＳ５１８に進む。
ステップＳ５１４において、判定手段４０５は、ΔX'またはΔX''が初めて０になったか判定を判定し、初めてであればステップＳ５１６に進み、初めてでなければステップＳ５１７に進む。
【００６２】
ステップＳ５１６において、出力手段４０６は、∇X''の要素数を入力値ΔXのハミングウェイトHW(ΔX)として設定する。
ステップＳ５１７において、出力手段４０６は、∇X''を出力用テーブル４０９に格納し、ステップＳ５０２に戻る。
【００６３】
ステップＳ５１８において、出力手段４０６は、ステップＳ５１２で計算したΔX''および∇X''をメモリテーブル４０８の最後尾に格納する。
本発明の第２の実施の形態によれば、効率的に入力値ΔXに対する所定の要素数以下の符号付２進表現の全てを得ることが出来る。
【００６４】
次に具体的な数値を用いた場合の例を図５の処理と対応させて説明する。
ここでは、入力値ΔX=0x78=120、キャリー値cを1とし、要素数がHW(ΔX)+c以下の符号付２進表現全てを求める場合を説明する。ΔXを通常の２進表現で表した場合、ΔX=(0,…,0,0,1,1,1,1,0,0,0)である。
【００６５】
・初期設定
初期設定として、入力値ΔX=0x78およびキャリー値c=1を受信し、ΔXと∇Xをメモリテーブルの先頭M[1]に格納する（ステップＳ５０１）。ここで∇X=φである。
よって、M[1]=[ΔX=0x78= (0,…,0,0,1,1,1,1,0,0,0),∇X=φ={}]となる。
【００６６】
・演算開始
１．∇X'、∇X''の要素数が１のループ
(a) メモリテーブルの先頭のデータを読み出すと（ステップＳ５０２）、ΔX=M[1]1=0x78,∇X=M[1]2=φである。
(b)読み出したM[1]を消去する（ステップＳ５０２）。
(c)ΔXの非零最下位ビットを算出すると23となる（ステップＳ５０３）。
ΔX'および∇X'を計算すると（ステップＳ5０４）、
ｉ．ΔX'=ΔX-23=(0,…,0,0,1,1,1,0,0,0,0)=0x70, ∇X'={+23}となる。
ΔXのハミングウェイトHW(ΔX)が設定済みかつ∇X'の要素数がHW(ΔX)+cを超えているかを判定すると（ステップＳ５０５）、ハミングウェイトHW(ΔX)が設定されていないので、次にΔX'が０であるか判定すると（ステップＳ５０７）、ΔX'=0x70≠0のため、ΔX'および∇X'をメモリテーブルの最後尾に格納する（ステップＳ５１１）。
ii．メモリテーブルの最後尾はM[2]であるため、M[2] =[0x70,{+23}]となる。
そして、ΔX''および∇X''を計算すると（ステップＳ５１２）
iii．ΔX''=ΔX+23=(0,…,0,1,0,0,0,0,0,0,0)=0x80, ∇X''={-23}となる。
ΔXのハミングウェイトHW(ΔX)が設定済みかつ∇X''の要素数がHW(ΔX)+cを超えているかを判定すると（ステップＳ５０５）、ハミングウェイトHW(ΔX)が設定されていないので、次にΔX''が０であるか判定すると（ステップＳ５１４）、ΔX'=0x70≠0のため、ΔX'および∇X'をメモリテーブルの最後尾に格納する（ステップＳ５１８）。
iv．メモリテーブルの最後尾はM[3]であるため、M[3]=[0x80,{-23}]となる。
そして、メモリテーブルの先頭のデータを読み出す処理（ステップＳ３０２）に戻る。
【００６７】
以下、同様の処理を繰り返す。以下の説明において、同様の処理を行うことから簡単のため、重複する説明は省略し、読み出したΔXの値やメモリテーブルに格納する内容等のみを記載する。
【００６８】
２．∇X'、∇X''の要素数が２のループ
(a)ΔX=M[2]1=0x70,∇X=M[2]2={+23}
(b)M[2]を消去
(c)ΔXの最下位ビット= 24
ｉ．ΔX'=ΔX-24=(0,…,0,0,1,1,0,0,0,0,0)=0x60,∇X'={+24+23}
ii．M[4]=[0x60,{+24+23}]
iii．ΔX''=ΔX+24=(0,…,0,1,0,0,0,0,0,0,0)=0x80,∇X''={-24+23}
iv．M[5]=[0x80,{-24+23}]
(d)ΔX=M[3]1=0x80,∇X=M[3]2={-23}
(e)M[3]を消去
(f)ΔXの最下位ビット=27
ｉ．ΔX'=ΔX-27=(0,…,0,0,0,0,0,0,0,0,0)=0x0,∇X'={+27-23}
ΔX'が０であるか判定すると（ステップＳ５０７）、ΔX'=0x0=0のため、ΔX'またはΔ
X''が初めて０になったか判定を判定する（ステップＳ５０８）。ΔX'またはΔX''は初めて０になったので、∇X'の要素数を入力値ΔXのハミングウェイトHW(ΔX)として設定する（ステップＳ５０９）。ここでは、∇X'={+27-23}なので∇X'の要素数は２である。よって、入力値ΔXのハミングウェイトHW(ΔX)は２となる。
ii．∇X'={+27-23}を出力用テーブルに格納する（ステップＳ５１０）。
iii．ΔX''=ΔX+27=(0,…,1,0,0,0,0,0,0,0,0)=0x100,∇X''={-27-23}
iv．M[6]=[0x100,{-27-23}]
【００６９】
３．∇X'、∇X''の要素数が３のループ
(a)ΔX=M[4]1=0x60,∇X=M[4]2={+24+23}
(b)M[4]を消去
(c)ΔXの最下位ビット=25
ｉ．ΔX'=ΔX-25=(0,…,0,0,1,0,0,0,0,0,0)=0x40,∇X'={+25+24+23}
ii．M[7]=[0x40,{+25+24+23}]
iii．ΔX''=ΔX+25=(0,…,0,1,0,0,0,0,0,0,0)=0x80,∇X''={+25-24+23}
iv．M[8]=[0x80,{+25-24+23}]
(d)ΔX=M[5]1=0x80,∇X=M[5]2={-24+23}
(e)M[5]を消去
(f)ΔXの最下位ビット=27
ｉ．ΔX'=ΔX-27=(0,…,0,0,0,0,0,0,0,0,0)=0x0,∇X'={+27-24+23}
ii．∇X'={+27-24+23}を出力用テーブルに格納する。
【００７０】
iii．ΔX''=ΔX+27=(0,…,1,0,0,0,0,0,0,0,0)=0x100,∇X''={-27-24+23}
iv．M[11]=[0x100,{-27-24+23}]
(j)ΔX=M[6]1=0x100,∇X=M[6]2={-27-23}
(k)M[6]を消去
(h)ΔXの最下位ビット=28
ｉ．ΔX'=ΔX-28=(0,…,0,0,0,0,0,0,0,0,0)=0x0,∇X'={+28-27-23}
ii．∇X'={+28-27-23}を出力用テーブルに格納する。
【００７１】
iii．ΔX''=ΔX+27=(0,…,0,1,0,0,0,0,0,0,0,0,0)=0x200,∇X''={-28-27-23}
iv．M[10]=[0x200,{ -28-27-23}
【００７２】
４．∇X'、∇X''の要素数が４のループ
(a)ΔX=M[7]1=0x40,∇X=M[7]2={+25+24+23}
(b)M[7]を消去
(c)ΔXの最下位ビット=26
ｉ．ΔX'=ΔX-26=(0,…,0,0,0,0,0,0,0,0,0)=0x0,∇X'={+26+25+24+23}
ΔXのハミングウェイトHW(ΔX)が設定済みかつ∇X'の要素数がHW(ΔX)+cを超えているかを判定すると（ステップＳ５０５）、ハミングウェイトHW(ΔX)は既に設定されており、また∇X'の要素数は4であり、HW(ΔX)+c=3であることから∇X'の要素数＞HW(ΔX)+cなので処理のループを抜ける。
【００７３】
５．出力
出力用テーブルに格納された３個の符号付2進表現{+27-23},{+27-24+23}, {+28-27-23}を出力する（ステップＳ５０６）。このように、所定数（本例においてはHW(ΔX)+c）以下の要素数の符号付２進表現の全てを得ることが出来る。
【００７４】
本発明の実施の形態において、∇Xは符号付の２のべき乗値の集合として表現していたが、これらの集合をメモリ空間上に格納するためには、要素の個数だけメモリが必要となる。そこで、∇Xに含まれる要素のうち正の値を全て合計したものを∇X+、負の値を合計したものの絶対値を∇X-として、∇Xを自然数∇X+と自然数∇X-の組として格納すること
で、メモリを節約することが出来る。
【００７５】
例えば、∇X={28-25-22-20}の場合、∇X+は∇Xの正の値の要素の合計+28=0x100となり、∇X-は負の値の要素の合計の絶対値|-25-22-20|=0x23となる。
２のべき乗値の集合の場合、∇X={28-25-22-20}を表すのに４つの要素を格納する領域が必要であったが、∇Xを∇X+と∇X-とすることで２つの要素を格納する領域を確保するだけでよい。
【００７６】
本発明の実施の形態において、処理の中でΔXの非零最下位ビットを求めている。ΔXの非零最下位ビットの求め方として、単純に最下位ビットから順に探索する方法もあるが、ΔXと-ΔXの論理積を計算することで簡単に求めることが出来る。例えばΔX=0xd8=(0,…0,1,1,0,1,1,0,0,0)とすると、-ΔX=0xffffff28=(1,…,1,0,0,1,0,1,0,0,0)となり、論理積を計算すると(ΔX)&(-ΔX)=0xd8&0xffffff28=0x8が得られ、これがΔXの非零最下位ビットとなる。このようにΔXと-ΔXの論理積を計算することでΔXの非零最下位ビットを簡単に求めることが可能となる。
【００７７】
以上、本発明の実施の形態を、図面を参照しながら説明してきたが、本発明が適用される演算装置は、その機能が実行されるのであれば、上述の実施の形態に限定されることなく、単体の装置であっても、複数の装置からなるシステムあるいは統合装置であっても、ＬＡＮ、ＷＡＮ等のネットワークを介して処理が行なわれるシステムであってもよい。
【００７８】
また、バスに接続されたＣＰＵ、ＲＯＭやＲＡＭのメモリ、入力装置、出力装置、外部記録装置、媒体駆動装置、ネットワーク接続装置で構成されるシステムでも実現できる。すなわち、前述してきた実施の形態のシステムを実現するソフトェアのプログラムコードを記録したＲＯＭやＲＡＭのメモリ、外部記録装置、可搬記録媒体を、演算装置に供給し、その演算装置のコンピュータがプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。
【００７９】
この場合、可搬記録媒体等から読み出されたプログラムコード自体が本発明の新規な機能を実現することになり、そのプログラムコードを記録した可搬記録媒体等は本発明を構成することになる。
【００８０】
プログラムコードを供給するための可搬記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、磁気テープ、不揮発性のメモリーカード、ＲＯＭカード、電子メールやパソコン通信等のネットワーク接続装置（言い換えれば、通信回線）を介して記録した種々の記録媒体などを用いることができる。
【００８１】
また、コンピュータ（情報処理装置）がメモリ上に読み出したプログラムコードを実行することによって、前述した実施の形態の機能が実現される他、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施の形態の機能が実現される。
【００８２】
さらに、可搬型記録媒体から読み出されたプログラムコードやプログラム（データ）提供者から提供されたプログラム（データ）が、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施の形態の機能が実現され得る。
すなわち、本発明は、以上に述べた実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の構成または形状を取ることができる。
【００８３】
（付記１）
コンピュータに入力値に対する最短の符号付２進表現を算出させるためのプログラムにおいて、
ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリ内のデータテーブル先頭に格納し、
前記メモリ内のデータテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記データテーブルから削除する第１のステップと、
前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、
算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、
前記ΔX'が０の場合、入力値に対する最短の符号付２進表現として前記∇X'を出力し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記データテーブルの最後尾に格納する第４のステップと、
算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第５のステップと、
前記ΔX''が０の場合、入力値に対する最短の符号付２進表現として前記∇X''を出力し、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記データテーブルの最後尾に格納して第１のステップに進む第６のステップと、
を含む処理を前記コンピュータに実行させるためのプログラム。
（付記２）
あらかじめ設定された値hwに基づき、2hw個の前記ΔXおよび前記∇Xの組を格納可能とするように前記メモリテーブルの容量を確保することを特徴とする付記１記載のプログラム。
（付記３）
コンピュータに入力値に対する所定の要素数以下の符号付２進表現を算出させるためのプログラムにおいて、
ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリテーブル先頭に格納し、
前記メモリテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記メモリテーブルから削除する第１のステップと、
前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、
算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、
前記∇X'の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第４のステップと、
前記ΔX'が０の場合、前記∇X'を出力用テーブルに格納し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記メモリテーブルの最後尾に格納する第５のステップと、
算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第６のステップと、
前記∇X''の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第７のステップと、
前記ΔX''が０の場合、前記∇X''を前記出力用テーブルに格納して第１のステップに戻り、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記データテーブルの最後尾に格納して第１のステップに戻る第８のステップと、
を含む処理を前記コンピュータに実行させるためのプログラム。
（付記４）
前記所定の要素数は、前記入力値ΔXの最短の符号付２進表現のハミングウェイトとあらかじめ定められたキャリー値とを加算した値であることを特徴とする請求項３記載のプログラム。
（付記５）
２のべき乗の集合で表される前記∇X'および前記∇X''を前記∇X'および前記∇X'に含まれる要素のうち、正の値の要素の合計を∇X+とし、負の値の要素の合計の絶対値を∇X-として、前記∇X'および前記∇X''の要素を∇X+と∇X-の組で格納することを特徴とする付記１または３記載のプログラム。
（付記６）
前記所定の要素数をZとしたときに、2Z個の前記ΔXおよび前記∇Xの組を格納可能とするように前記メモリテーブルの容量を確保することを特徴とする付記３記載のプログラム。
（付記７）
前記所定の要素数を前記入力値ΔXの最短の符号付２進表現のハミングウェイトHW(ΔX)とあらかじめ定められたキャリー値cとを加算した値とし、前記入力値が2nを法とする自然数であるときに、
(n+1)/2以下の最大の自然数をmとしたとき、最大で2m+c個の前記ΔXおよび前記∇Xの組を格納可能とするように前記メモリテーブルの容量を確保することを特徴とする請求項２記載のプログラム。
（付記８）
入力値に対する最短の符号付２進表現を算出する方法おいて、
ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリ内のデータテーブル先頭に格納し、
前記メモリ内のデータテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記データテーブルから削除する第１のステップと、
前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、
算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、
前記ΔX'が０の場合、入力値に対する最短の符号付２進表現として前記∇X'を出力し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記データテーブルの最後尾に格納する第４のステップと、
算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第５のステップと、
前記ΔX''が０の場合、入力値に対する最短の符号付２進表現として前記∇X''を出力し、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記メモリテーブルの最後尾に格納して第１のステップに進む第６のステップと、
を含む符号付２進表現算出方法。
（付記９）
入力値に対する所定の要素数以下の符号付２進表現を算出する方法において、
ΔXを前記入力値、符号付２進表現の要素を示す∇Xを空集合としてそれらを関連付けてメモリテーブル先頭に格納し、
前記メモリテーブルの先頭からΔXおよび∇Xを読み出し、該ΔXおよび該∇Xを前記メモリテーブルから削除する第１のステップと、
前記ΔXの２進表現における非零最下位ビット2iを求める第２のステップと、
算術演算ΔX'=ΔX-2iおよび集合演算∇X' =(+2i)∪∇Xを計算する第３のステップと、
前記∇X'の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第４のステップと、
前記ΔX'が０の場合、前記∇X'を出力用テーブルに格納し、前記ΔX'が０でない場合、前記ΔX'および∇X'を関連付けて前記メモリテーブルの最後尾に格納する第５のステップと、
算術演算ΔX''=ΔX+2iおよび集合演算∇X'' =(-2i)∪∇Xを計算する第６のステップと、
前記∇X''の要素数が前記所定の要素数を超えているか判定し、超えていれば処理を終了する第７のステップと、
前記ΔX''が０の場合、前記∇X''を前記出力用テーブルに格納して第１のステップに戻り、前記ΔX''が０でない場合、前記ΔX''および∇X''を関連付けて前記メモリテーブルの最後尾に格納して第１のステップに戻る第８のステップと、
を含む符号付２進表現算出方法。
【図面の簡単な説明】
【００８４】
【図１】本発明の第１の実施の形態に係る演算装置の機能ブロック図である。
【図２】本発明の第１の実施の形態に係るメモリテーブルのデータ構造の例を示す図である。
【図３】本発明の第１の実施の形態に係る演算装置の処理のフローチャートである。
【図４】本発明の第２の実施の形態に係る演算装置の機能ブロック図である
【図５】本発明の第２の実施の形態に係る演算装置の処理のフローチャートである。
【符号の説明】
【００８５】
１００    演算装置
１０１    初期設定手段
１０２    読み出し削除手段
１０３    非零最下位ビット算出手段
１０４    演算手段
１０５    判定手段
１０６    出力手段
１０７    メモリ
１０８    メモリテーブル
４００    演算装置
４０１    初期設定手段
４０２    読み出し削除手段
４０３    非零最下位ビット算出手段
４０４    演算手段
４０５    判定手段
４０６    出力手段
４０７    メモリ
４０８    メモリテーブル
４０９    出力用テーブル
【図１】
2008176243.tif 000003
【図２】
2008176243.tif 000004
【図３】
2008176243.tif 000005
【図４】
2008176243.tif 000006
【図５】
2008176243.tif 000007