JP4973042B2 - データ位置変換装置およびデータ位置変換方法 - Google Patents

Description

本発明はデータの格納位置を変換するデータ位置変換装置およびデータ位置変換方法に関し、特にメモリに格納されたデータの格納位置を変換するデータ位置変換装置およびデータ位置変換方法に関する。

現在、無線通信や画像解析等、さまざまな分野でディジタル信号処理が行われている。ディジタル信号処理では、高速フーリエ変換（ＦＦＴ：Fast Fourier Transform）や逆高速フーリエ変換（ＩＦＦＴ：Inverse Fast Fourier Transform）等を用いたデータ解析処理が頻繁に行われる。ここで、ＦＦＴ等では、入力データの順序と入力データに対応する出力データの順序とが一致しないことが知られている。

具体的には、入力データの順序と入力データに対応する出力データの順序とは、ビット反転の関係にある。ビット反転とは、２進数のビット列を逆順にすることである（例えば、特許文献１参照）。例えば、データの位置を３ビットで表現可能なデータ列の場合、すなわち、位置０（０００）から位置７（１１１）までの８個のデータで構成されるデータ列の場合、位置１（００１）の入力データは位置４（１００）の出力データと対応する。このように、入力データを０，１，２，３，４，５，６，７の順に与えると、対応する出力データは０，４，２，６，１，５，３，７の順に出力される。

そこで、ディジタル信号処理の装置では、出力データが正しい順に出力されるように、ＦＦＴ等の処理の前に入力データを並べ替えることが行われている。このようなデータの並べ替えは、ＦＦＴ等の処理に使用する入力データをメモリに格納する際に行うのが一般的である。すなわち、ＦＦＴ等の前段の処理で出力されたデータをメモリに格納する際に、例えば、位置１のデータをメモリの００１番地ではなく１００番地に格納する。これにより、全ての入力データがメモリに格納された時点で、適切な順序に入力データが並んでいることになり、即座にＦＦＴ等の処理を開始することができる。また、この方法では装置構成を単純化できるという利点もある。
特開昭５９−０３３５７５号公報

しかし、上記の方法では、メモリに格納されたデータを他の用途に利用することが困難になるという問題がある。例えば、ＦＦＴを行う前に必要に応じて時系列データから統計情報を抽出したい場合があるが、データがメモリに格納された時点でＦＦＴの処理用に順序が並べ替えられているため、時系列性が失われており統計処理が困難となる。このように、上記の方法を用いて装置を構成すると、データ処理を行う順序が固定されてしまい柔軟性に欠ける。

一方、上記の問題は、入力データを元の順序で一旦メモリに格納し、ＦＦＴ等の処理を行う直前にメモリデータを並べ替えるようにすることで解決できる。しかしながら、従来、メモリに格納されたデータを並べ替える処理は複雑になり装置規模が増大してしまうという問題があった。その理由は以下の通りである。

メモリデータを並べ替えるには、ビット反転の関係にあるメモリアドレスの組を過不足なく計算する必要がある。ここで、メモリアドレスを最小値から最大値まで順にカウントアップし、それぞれのメモリアドレスの反転アドレスを順に求めると、組となるべきメモリアドレスが２回ずつ出現することになる。例えば、３ビットのメモリアドレスを０００，００１，０１０，０１１，１００，１０１，１１０，１１１とカウントアップすると、それぞれに対応する反転アドレスは０００，１００，０１０，１１０，００１，１０１，０１１，１１１と計算される。

ここで、アドレス組（００１，１００）とアドレス組（１００，００１）とが出現するが、これらは同一のアドレス組であるため、アドレス組（００１，１００）の発見時にメモリデータの入替処理を行うと、アドレス組（１００，００１）の発見時には入替処理を行ってはいけない。２回入替処理を行うと、データが元の位置に戻ってしまうからである。そして、上記の制御は単純な装置構成では実現することができず、並べ替え処理のための一時的なメモリ領域等を用意する必要がある。この問題は、ビット反転の関係にあるメモリアドレスの組を過不足なく求めることが容易でないことに起因するものである。

なお、上記の問題は、ＦＦＴ等の前に入力データに対してデータの並べ替えを行う場合だけでなく、ＦＦＴ等の後に出力データに対してデータの並べ替えを行う場合にも生じる問題である。

本発明はこのような点に鑑みてなされたものであり、処理の複雑さや装置規模を増大させることなく、ビット反転の関係にあるアドレス間でメモリに格納されたデータを入替えるデータ位置変換装置およびデータ位置変換方法を提供することを目的とする。

本発明では上記課題を解決するために、図１に示すようなデータ位置変換装置が提供される。本発明に係るデータ位置変換装置は、メモリに格納されたデータを、ビット反転の関係にある２つのメモリアドレス間で入替えるものである。データ位置変換装置１は、アドレス生成手段１ａ、アドレス変換手段１ｂ、アドレス調整手段１ｃおよびデータ入替手段１ｄを有する。アドレス生成手段１ａは、所定のビット長で表現可能な全ての基本アドレスを、値を１ずつ変化させて連続的に生成する。アドレス変換手段１ｂは、最下位ビットのみが異なる２つの基本アドレス毎に、基本アドレスを１ビット右シフトした第１のビット列と、第１のビット列を逆順にした第２のビット列とを生成する。アドレス調整手段１ｃは、第１のビット列の値が第２のビット列の値以下である場合、第１のビット列と第２のビット列との組を入替アドレスと判定し、第１のビット列の値が第２のビット列の値より大きい場合、第１のビット列と第２のビット列とをそれぞれ論理反転したビット列の組を入替アドレスと判定する。データ入替手段１ｄは、入替アドレスが判定される毎に、入替アドレスで特定されるメモリ２内の２つのデータの格納位置を入替える。

このようなデータ位置変換装置１によれば、アドレス生成手段１ａにより、所定のビット長の基本アドレスが値が１ずつ変化しながら連続的に生成される。アドレス変換手段１ｂにより、最下位ビットのみが異なる２つの基本アドレス毎に、基本アドレスを１ビット右シフトした第１のビット列と、第１のビット列を逆順にした第２のビット列とが生成される。次に、アドレス調整手段１ｃにより、第１のビット列が第２のビット列より大きい場合には２つのビット列をそれぞれ論理反転した組が入替アドレスと判定され、それ以外の場合には２つのビット列の組が入替アドレスと判定される。そして、データ入替手段１ｄにより、入替アドレスで特定されるメモリ２内の２つのデータの格納位置が入替えられる。

また、上記課題を解決するために、メモリに格納されたデータの格納位置を変換するデータ位置変換方法において、アドレス生成手段が、所定のビット長で表現可能な全ての基本アドレスを、値を１ずつ変化させて連続的に生成し、アドレス変換手段が、最下位ビットのみが異なる２つの前記基本アドレス毎に、前記基本アドレスを１ビット右シフトした第１のビット列と、前記第１のビット列を逆順にした第２のビット列とを生成し、アドレス調整手段が、前記第１のビット列の値が前記第２のビット列の値以下である場合、前記第１のビット列と前記第２のビット列との組を入替アドレスと判定し、前記第１のビット列の値が前記第２のビット列の値より大きい場合、前記第１のビット列と前記第２のビット列とをそれぞれ論理反転したビット列の組を前記入替アドレスと判定し、データ入替手段が、前記入替アドレスが判定される毎に、前記入替アドレスで特定される前記メモリ内の２つのデータの格納位置を入替える、ことを特徴とするデータ位置変換方法が提供される。

このようなデータ位置変換装置によれば、所定のビット長の基本アドレスが値が１ずつ変化しながら連続的に生成され、最下位ビットのみが異なる２つの基本アドレス毎に、基本アドレスを１ビット右シフトした第１のビット列と、第１のビット列を逆順にした第２のビット列とが生成される。次に、第１のビット列が第２のビット列より大きい場合には２つのビット列をそれぞれ論理反転した組が入替アドレスと判定され、それ以外の場合には２つのビット列の組が入替アドレスと判定される。そして、入替アドレスで特定されるメモリ内の２つのデータの格納位置が入替えられる。

本発明は、最下位ビットのみが異なる２つの基本アドレス毎に、基本アドレスを１ビット右シフトした第１のビット列と第１のビット列を逆順にした第２のビット列とを生成すると共に、第１のビット列が第２のビット列より大きい場合には２つのビット列をそれぞれ論理反転した組を入替アドレスと判定し、それ以外の場合には２つのビット列の組を入替アドレスと判定することとした。これにより、基本アドレスが一巡する間に、データを入替えるべきメモリアドレスの組が過不足なく１回ずつ生成される。したがって、一時的なメモリ領域等を用意する必要がなくなり、単純で小規模な装置構成でメモリデータの並べ替え処理を実現することができる。また、メモリデータの並べ替え処理をより高速に実行することができる。

以下、本発明の実施の形態を図面を参照して詳細に説明する。まず、本発明の概要について説明し、その後、実施の形態の具体的な内容を説明する。
図１は、データ位置変換装置の概要を示す図である。図１に示されるデータ位置変換装置は、メモリに格納されたデータを、ビット反転の関係にある２つのメモリアドレス間で入替えるものである。データ位置変換装置１は、アドレス生成手段１ａ、アドレス変換手段１ｂ、アドレス調整手段１ｃおよびデータ入替手段１ｄを有する。

アドレス生成手段１ａは、所定のビット長で表現可能な全ての基本アドレスを、値を１ずつ変化させて連続的に生成する。例えば、メモリカウンタを最小値（０）から最大値（２＾Ｎ−１：Ｎはビット長）までカウントアップするか、又は、最大値（２＾Ｎ−１）から最小値（０）までカウントダウンして一巡させることで、基本アドレスを連続的に生成する。メモリアドレスが４ビットで表現可能な場合、００００から１１１１までの１６個のアドレスが連続的に生成される。

アドレス変換手段１ｂは、最下位ビットのみが異なる２つの基本アドレス毎に、基本アドレスを１ビット右シフトした第１のビット列と、第１のビット列を逆順にした第２のビット列とを生成する。すなわち、アドレス変換手段１ｂは、アドレス生成手段１ａが生成した偶数個目と奇数個目の２つの隣り合う基本アドレス毎に、２つのビット列を生成する。

例えば、２つの基本アドレス０１１０，０１１１に対して、第１のビット列００１１と第２のビット列１１００とが生成される。同様に、２つの基本アドレス１０００，１０００１に対して、第１のビット列０１００と第２のビット列００１０とが生成される。なお、１ビットの右シフト演算は、ビット列の最下位ビット（ＬＳＢ：Less Significant Bit）を削除し、最上位ビット（ＭＳＢ：Most Significant Bit）に０を挿入するビット演算である。

アドレス調整手段１ｃは、アドレス変換手段１ｂが生成した第１のビット列と第２のビット列との組毎に両者を比較する。ここで、第１のビット列の値が第２のビット列の値以下である場合、第１のビット列と第２のビット列との組を入替アドレスと判定する。一方、第１のビット列の値が第２のビット列の値より大きい場合、第１のビット列と第２のビット列とをそれぞれ論理反転したビット列の組を入替アドレスと判定する。

すなわち、アドレス変換手段１ｂが生成した第１のビット列と第２のビット列との組が、原則として、データを入替えるメモリアドレスの組と判定される。ただし、アドレス生成手段１ａがアドレスカウンタを一巡させる間に、同一のビット列の組が２つ生成される場合がある。ここで、同一のビット列の組が２回目に出現する場合は、第１のビット列の値が第２のビット列の値より大きい場合に限定される。このとき、第１のビット列と第２のビット列とをそれぞれ論理反転した（各ビットの０と１とを反転した）ビット列の組を入替アドレスとすることで、データを入替えるべきメモリアドレスの組が１回ずつ過不足なく生成されるようになる。

例えば、第１のビット列００１１と第２のビット列１１００との組に対して、入替アドレス（００１１，１１００）が生成される。一方、第１のビット列０１００と第２のビット列００１０との組に対して、入替アドレス（１０１１，１１０１）が生成される。これは、第１のビット列００１０と第２のビット列０１００との組が既に出現済みだからである。

データ入替手段１ｄは、入替アドレスが判定される毎に、入替アドレスで特定されるメモリ２内の２つのデータの格納位置を入替える。具体的には、データ入替手段１ｄは、２つのメモリアドレスを使ってデータをメモリ２からそれぞれ読み込み、その後、逆のメモリアドレスを使って読み込んだデータをメモリ２に書き戻す。

例えば、アドレス００１１にデータＤ、アドレス１１００にデータＭが格納されている場合、データ入替手段１ｄによる処理の後は、アドレス００１１にデータＭ、アドレス１１００にデータＤが格納された状態になる。同様に、アドレス１０１１にデータＬ、アドレス１１０１にデータＮが格納されている場合、データ入替手段１ｄによる処理の後は、アドレス１０１１にデータＮ、アドレス１１０１にデータＬが格納された状態になる。

これにより、基本アドレスが一巡する間に、データを入替えるべきメモリアドレスの組が過不足なく１回ずつ生成される。したがって、一時的なメモリ領域等を用意する必要がなくなり、単純で小規模な装置構成でメモリデータの並べ替え処理を実現することができる。また、メモリデータの並べ替え処理をより高速に実行することができる。

以下、本発明の実施の形態を、図面を参照して具体的に説明する。まず、本発明の第１の実施の形態について説明する。
図２は、本実施の形態のシステム構成を示す図である。本実施の形態の無線通信システムは、移動局が発信した電波を基地局が受信し、基地局がディジタル信号処理を行うものである。

本実施の形態の無線通信システムは、基地局１００、受信アンテナ１１および移動局２０で構成される。移動局２０はディジタル信号を電波に乗せて発信する。受信アンテナ１１は移動局２０が発信した電波を受信する。基地局１００は受信アンテナ１１を介してディジタル信号を取得し、その後ＦＦＴ等のデータ変換処理を行う。基地局１００は、制御部１１０、Ａ／Ｄ変換部１２０、メモリ１３０、データ位置変換部１４０およびＦＦＴ部１５０を有する。なお、ＦＦＴにより周波数成分データが出力された後の処理に関しては、説明を省略している。

制御部１１０は、基地局１００で実行される信号処理の全体を制御する。例えば、制御部１１０は、基地局１００の各構成部に対して、処理のタイミングを示す信号を送信する。Ａ／Ｄ変換部１２０は、受信アンテナ１１から取得したアナログ信号をディジタル信号に変換する。また、必要に応じてフィルタ処理等も行う。そして、Ａ／Ｄ変換部１２０は、時系列データをメモリ１３０に格納する。

メモリ１３０は、Ａ／Ｄ変換部１２０が出力したデータを保持する。メモリ１３０はデュアルポートメモリであり、メモリアドレスを２つ指定することで同時に２箇所のデータをリード／ライトできる。データ位置変換部１４０は、制御部１１０からの指示に応じて、メモリ１３０に格納されたデータを並べ替える。これは、ＦＦＴ部１５０の出力データが正しい順序になるように、入力データを予め並べ替えておく必要があるためである。ＦＦＴ部１５０は、メモリ１３０に格納されたデータを順次読み込んでＦＦＴを実行し、周波数成分データを出力する。ＦＦＴ部１５０の出力データは、図示しない後段の処理の入力データとして利用される。

次に、データ位置変換部１４０のモジュール構成について説明する。
図３は、第１の実施の形態に係るデータ位置変換部の機能を示すブロック図である。データ位置変換部１４０は、アドレス生成部１４１、ビット列操作部１４２、ビット列選択部１４３、アドレス調整部１４４およびデータ入替部１４５を有する。なお、アドレス生成部１４１は、制御部１１０と接続されている。データ入替部１４５は、メモリ１３０と接続されている。

アドレス生成部１４１は、アドレス生成開始の信号を受け取ると、Ｎビットの基本アドレスを１単位時間（クロック）毎に１つずつ、最小値から最大値まで連続的に生成する。すなわち、アドレス生成部１４１は、メモリカウンタを０から２＾Ｎ−１までカウントアップして一巡させる。例えば、メモリアドレスが４ビットの場合、００００から１１１１までの１６個のアドレスを１６クロックで生成する。

ビット列操作部１４２は、アドレス生成部１４１が生成した基本アドレス毎に、Ｎビットのビット列Ａ、Ｎビットのビット列Ｂおよび１ビットのフラグＣを生成する。次に、ビット列選択部１４３は、ビット列操作部１４２が生成したビット列Ａ、ビット列ＢおよびフラグＣから、Ｎビットのビット列Ｄおよび１ビットのフラグＥを生成する。そして、アドレス調整部１４４は、ビット列選択部１４３が生成したビット列ＤおよびフラグＥから、Ｎビットのメモリアドレスを１つ生成する。

このようにして、アドレス調整部１４４は、１クロック毎に１つのメモリアドレスを生成する。ここで、アドレス調整部１４４が生成するメモリアドレスは、２つの連続するメモリアドレス毎に入替アドレスとしての意味をもつ。すなわち、０００１と１０００のように、ビット反転の関係にあるメモリアドレスの組が、２クロック毎に生成される。

データ入替部１４５は、アドレス調整部１４４が生成した入替アドレスを用いて、メモリ１３０に格納されているデータの格納位置を入替える。具体的には、データ入替部１４５は、２つのメモリアドレスを指定して、メモリ１３０から２つのメモリデータをリードする。そして、データ入替部１４５は、互いに逆のメモリアドレスを指定して、２つのメモリデータをライトする。なお、データ入替部１４５は、メモリアドレス等を一時的に記憶するためのレジスタ１４５ａを有している。

メモリ１３０はデュアルポートメモリであるため、２つのメモリデータのリード／ライトは、それぞれ１クロックで行える。したがって、データ入替部１４５は、２クロック毎に１組のメモリデータを入替えることができる。アドレス生成部１４１がアドレスカウンタを一巡させると、メモリ１３０に格納された全てのデータの並べ替え処理が完了する。

なお、本実施の形態では、アドレス変換処理は基本アドレス毎に直列的に行い、データ入替処理は２つの基本アドレス毎に行っている。これは、回路規模を小さくするためである。ただし、アドレス変換処理を２つの基本アドレスについて並列に行うようにしてもよい。この場合、データ位置変換部１４０の処理をより高速化できる。

次に、ビット列操作部１４２、ビット列選択部１４３およびアドレス調整部１４４によって実行される、基本アドレスから入替アドレスを計算する処理について説明する。
図４は、第１の実施の形態に係る入替アドレスの決定処理の手順を示すフローチャートである。以下、図４に示す処理をステップ番号に沿って説明する。

［ステップＳ１１］ビット列操作部１４２は、アドレス生成部１４１が生成した基本アドレスを１つ取得する。
［ステップＳ１２］ビット列操作部１４２は、基本アドレスを１ビット右シフトしたビット列Ａを生成する。ここで、１ビットの右シフト演算とは、ＬＳＢを削除しＭＳＢに０を挿入することである。

［ステップＳ１３］ビット列操作部１４２は、ビット列Ａをビット反転したものに相当するビット列Ｂを生成する。具体的には、基本アドレスのＬＳＢを除いたビット列を反転させ、ＬＳＢに０を挿入したビット列Ｂを生成する。

［ステップＳ１４］ビット列操作部１４２は、基本アドレスのＬＳＢであるフラグＣを生成する。
［ステップＳ１５］ビット列選択部１４３は、ビット列操作部１４２が生成したビット列Ａ、ビット列ＢおよびフラグＣを取得する。そして、ビット列選択部１４３は、フラグＣの０／１を判断する。フラグＣが０の場合、処理がステップＳ１６へ進められる。フラグＣが１の場合、処理がステップＳ１７へ進められる。

［ステップＳ１６］ビット列選択部１４３は、ステップＳ１５で取得したビット列Ａをビット列Ｄとして出力する。
［ステップＳ１７］ビット列選択部１４３は、ステップＳ１５で取得したビット列Ｂをビット列Ｄとして出力する。

［ステップＳ１８］ビット列選択部１４３は、ステップＳ１５で取得したビット列Ａとビット列Ｂとを比較し、値の大小を判断する。ビット列Ａの値がビット列Ｂの値より大きい場合、処理がステップＳ１９へ進められる。ビット列Ａの値がビット列Ｂの値以下の場合、処理がステップＳ２０へ進められる。

［ステップＳ１９］ビット列選択部１４３は、フラグＥとして１を出力する。
［ステップＳ２０］ビット列選択部１４３は、フラグＥとして０を出力する。
［ステップＳ２１］アドレス調整部１４４は、ビット列選択部１４３が生成したビット列ＤとフラグＥとを取得する。そして、アドレス調整部１４４は、フラグＥの０／１を判断する。フラグＥが０の場合、処理がステップＳ２２へ進められる。フラグＥが１の場合、処理がステップＳ２３へ進められる。

［ステップＳ２２］アドレス調整部１４４は、入替アドレスの一方として、ビット列Ｄを出力する。
［ステップＳ２３］アドレス調整部１４４は、入替アドレスの一方として、ビット列Ｄを論理反転したビット列を出力する。ここで、論理反転とは、各ビットの０／１を反転させるビット操作である。

このようにして、ビット列操作部１４２は、基本アドレスを１ビット右シフトしたビット列Ａ、ビット列Ａをビット反転したビット列Ｂおよび基本アドレスのＬＳＢであるフラグＣを生成する。ビット列選択部１４３は、ビット列Ｄとして、フラグＣ＝０（基本アドレスが偶数番目）の場合にはビット列Ａを、フラグＣ＝１（基本アドレスが奇数番目）の場合にはビット列Ｂを選択する。また、ビット列選択部１４３は、フラグＥとして、ビット列Ａ≦ビット列Ｂの場合には０を、ビット列Ａ＞ビット列Ｂの場合には１を出力する。そして、アドレス調整部１４４は、入替アドレスの一方として、フラグＥが０（ビット列Ａ≦ビット列Ｂ）の場合にはビット列Ｄを、フラグＥが１（ビット列Ａ＞ビット列Ｂ）の場合にはビット列Ｄを論理反転したものを出力する。

図５は、第１の実施の形態に係るビット列操作の流れを示す図である。図５は、メモリアドレスが４ビットの場合について示した例である。データ位置変換部１４０により、図５のそれぞれの行毎に左側から右側へ向かってビット列の操作が進められる。

例えば、基本アドレス０１１０から、ビット列Ａ＝００１１、ビット列Ｂ＝１１００、フラグＣ＝０、ビット列Ｄ＝００１１、フラグＥ＝０が順に生成される。同様に、基本アドレス０１１１から、ビット列Ａ＝００１１、ビット列Ｂ＝１１００、フラグＣ＝１、ビット列Ｄ＝１１００、フラグＥ＝０が順に生成される。ここで、フラグＥ＝０であるため、（００１１，１１００）が入替アドレスとなる。

また、基本アドレス１０００から、ビット列Ａ＝０１００、ビット列Ｂ＝００１０、フラグＣ＝０、ビット列Ｄ＝０１００、フラグＥ＝１が順に生成される。同様に、基本アドレス１００１から、ビット列Ａ＝０１００、ビット列Ｂ＝００１０、フラグＣ＝１、ビット列Ｄ＝００１０、フラグＥ＝１が順に生成される。ここで、フラグＥ＝１であるため、（１０１１，１１０１）が入替アドレスとなる。

図５に示す通り、アドレス長が４ビットの場合、８組のメモリアドレスが入替アドレスとして生成される。このうち、２つのメモリアドレスの値が同一でない組は、（０００１，１０００）、（００１０，０１００）、（００１１，１１００）、（１０１１，１１０１），（０１０１，１０１０）、（０１１１，１１１０）の６組である。この６組が、データを入替えるべきメモリアドレスの組の全てになっている。このように、データ位置変換部１４０により、入替アドレスが過不足なく生成される。

なお、本実施の形態では、（００００，００００）と（０１１０，０１１０）のように、２つのメモリアドレスの値が同一である場合でも、入替処理を行っている。これは、比較演算を行うようにすると回路規模が増大するためである。ただし、入替アドレス生成後に比較演算を行い、２つのメモリアドレスが異なる場合のみ入替処理を行うようにしてもよい。これにより、メモリ１３０に対するリード／ライトの回数を減らすことができる。

図６は、第１の実施の形態に係る変換前後のメモリデータの状態を示す図である。図４および図５に示した流れでデータ入替処理が行われると、図６の左側に示したメモリの状態が、右側に示した状態に変化する。例えば、００１１番地のデータＤと１１００番地のデータＭとが入替えられる。同様に、１０１１番地のデータＬと１１０１番地のデータＮとが入替えられる。

このようなデータ位置変換装置を用いることで、基本アドレスが一巡する間に、データを入替えるべきメモリアドレスの組が過不足なく生成され、順次データ入替処理が実行される。したがって、一時的なメモリ領域等を用意する必要がなく、単純で小規模な回路構成でメモリデータの並べ替え処理を実現できる。また、メモリデータの並べ替え処理をより高速に実行することができる。

そして、ＦＦＴの直前にこのようなデータ並べ替え処理を実行すればよいため、メモリに格納された時系列データをＦＦＴの前に他の用途に利用することもでき、柔軟なデータ処理を行える。また、ＦＦＴの後にメモリデータを並べ替える場合にも、上記と同様の利点が得られる。

次に、本発明の第２の実施の形態を図面を参照して詳細に説明する。前述の第１の実施の形態との相違点を中心に説明し、同様の事項については説明を省略する。第２の実施の形態のデータ位置変換装置は、メモリアドレス全体に対してデータ並べ替え処理を行うのではなく、メモリアドレスを所定の区間毎に区切ってデータ並べ替え処理を行うようにしたものである。

図７は、第２の実施の形態に係るデータ位置変換部の機能を示すブロック図である。データ位置変換部１６０は、第１の実施の形態のデータ位置変換部１４０に対応するものであり、図２に示したシステム構成のデータ位置変換部１４０と置き換えられるものである。

データ位置変換部１６０は、アドレス生成部１６１、ビット列操作部１６２、ビット列選択部１６３、アドレス調整部１６４、データ入替部１６５およびオフセット記憶部１６６を有する。ここで、アドレス生成部１６１およびデータ入替部１６５は、第１の実施の形態のアドレス生成部１４１およびデータ入替部１４５と、それぞれ同様の構成および機能を有している。

ビット列操作部１６２は、まず、アドレス生成部１６１が生成した基本アドレスの上位Ｍビットのビット列を、オフセット記憶部１６６に対して出力する。ここで、Ｍは予め設定された１以上Ｎ（メモリアドレスのビット長）未満の整数であり、オフセット部分のビット長を意味する。そして、ビット列操作部１６２は、基本アドレスの上位Ｍビットを削除したビット列を用いて、ビット列Ａ、ビット列ＢおよびフラグＣを生成する。ここで、ビット列Ａおよびビット列ＢはＮ−Ｍビットである。オフセット記憶部１６６は、ビット列操作部１６２から取得したＭビットのビット列を保持する。

ビット列選択部１６３は、ビット列操作部１６２が生成したビット列Ａ、ビット列ＢおよびフラグＣから、Ｎ−Ｍビットのビット列Ｄおよび１ビットのフラグＥを生成する。アドレス調整部１６４は、ビット列選択部１６３が生成したビット列ＤおよびフラグＥからＮ−Ｍビットのビット列を生成し、さらにオフセット記憶部１６６が保持するＭビットのビット列を上位に挿入して、Ｎビットのメモリアドレスを１つ生成する。

次に、ビット列操作部１６２、ビット列選択部１６３およびアドレス調整部１６４によって実行される、基本アドレスから入替アドレスを計算する処理について説明する。
図８は、第２の実施の形態に係る入替アドレスの決定処理の手順を示すフローチャートである。以下、図８に示す処理をステップ番号に沿って説明する。

［ステップＳ３１］ビット列操作部１６２は、アドレス生成部１６１が生成した基本アドレスを１つ取得する。
［ステップＳ３２］ビット列操作部１６２は、基本アドレスの上位Ｍビットのビット列を、オフセット記憶部１６６へ出力する。

［ステップＳ３３］ビット列操作部１６２は、基本アドレスの上位Ｍビットを除いたビット列を１ビット右シフトしてビット列Ａを生成する。
［ステップＳ３４］ビット列操作部１６２は、ビット列Ａをビット反転したものに相当するビット列Ｂを生成する。

［ステップＳ３５］ビット列操作部１６２は、基本アドレスのＬＳＢであるフラグＣを生成する。
［ステップＳ３６］ビット列選択部１６３は、ビット列操作部１６２が生成したビット列Ａ、ビット列ＢおよびフラグＣを取得する。そして、ビット列選択部１６３は、フラグＣの０／１を判断する。フラグＣが０の場合、処理がステップＳ３７へ進められる。フラグＣが１の場合、処理がステップＳ３８へ進められる。

［ステップＳ３７］ビット列選択部１６３は、ステップＳ３６で取得したビット列Ａをビット列Ｄとして出力する。
［ステップＳ３８］ビット列選択部１６３は、ステップＳ３６で取得したビット列Ｂをビット列Ｄとして出力する。

［ステップＳ３９］ビット列選択部１６３は、ステップＳ３６で取得したビット列Ａとビット列Ｂとを比較し、値の大小を判断する。ビット列Ａの値がビット列Ｂの値より大きい場合、処理がステップＳ４０へ進められる。ビット列Ａの値がビット列Ｂの値以下の場合、処理がステップＳ４１へ進められる。

［ステップＳ４０］ビット列選択部１６３は、フラグＥとして１を出力する。
［ステップＳ４１］ビット列選択部１６３は、フラグＥとして０を出力する。
［ステップＳ４２］アドレス調整部１６４は、ビット列選択部１６３が生成したビット列ＤとフラグＥとを取得する。そして、アドレス調整部１６４は、フラグＥの０／１を判断する。フラグＥが０の場合、処理がステップＳ４３へ進められる。フラグＥが１の場合、処理がステップＳ４４へ進められる。

［ステップＳ４３］アドレス調整部１６４は、ビット列Ｄを入替下位アドレスと判定する。
［ステップＳ４４］アドレス調整部１６４は、ビット列Ｄを論理反転したビット列を入替下位アドレスする。

［ステップＳ４５］アドレス調整部１６４は、ステップＳ４３又はステップＳ４４で判定した入替下位アドレスの上位に、ステップＳ３２でオフセット記憶部１６６へ出力したビット列を付加したＮビットのビット列を、入替アドレスの一方として出力する。

このようにして、ビット列操作部１６２は、基本アドレスから上位Ｍを削除したビット列を用いてビット列Ａ、ビット列ＢおよびフラグＣを生成する。ビット列選択部１６３は、ビット列Ｄとして、フラグＣ＝０の場合にはビット列Ａを、フラグＣ＝１の場合にはビット列Ｂを選択する。また、ビット列選択部１６３は、フラグＥとして、ビット列Ａ≦ビット列Ｂの場合には０を、ビット列Ａ＞ビット列Ｂの場合には１を出力する。そして、アドレス調整部１６４は、入替アドレスの一方として、フラグＥが０の場合にはビット列Ｄに基本アドレスの上位Ｍビットを付加したものを、フラグＥが１の場合にはビット列Ｄを論理反転したビット列に基本アドレスの上位Ｍビットを付加したものを出力する。

図９は、第２の実施の形態に係るビット列操作の流れを示す図である。図９は、メモリアドレスが５ビットであり、上位１ビットをオフセット部分として用いる場合について示した例である。

図９に示す通り、基本アドレスの下位４ビットについては、第１の実施の形態と同様のビット列操作が行われる。一方、オフセット部分である上位１ビットは、ビット反転の対象とならない。すなわち、基本アドレス０００１０と０００１１とから、入替アドレス（００００１，０１０００）が生成される。同様に、基本アドレス１００１０と１００１１とから、入替アドレス（１０００１，１１０００）が生成される。

このように、オフセット部分の固定ビット長を設定することで、メモリを複数の領域に分割し、各区分内でデータの並べ替えを行うことができる。図９の例では、メモリアドレス０００００〜０１１１１と１００００〜１１１１１との２つの区分内で、それぞれデータの並べ替えが行われる。

図１０は、第２の実施の形態に係る変換前後のメモリデータの状態を示す図である。図８および図９に示した流れでデータ入替処理が行われると、図１０の左側に示したメモリの状態が、右側に示した状態に変化する。例えば、０００１１番地のデータＤ１と０１１００番地のデータＭ１とが入替えられる。同様に、１００１１番地のデータＤ２と１１１００番地のデータＭ２とが入替えられる。

このようなデータ位置変換装置を用いることで、第１の実施の形態で示したデータ位置変換装置を用いた場合と同様の効果を得られる。さらに、データ位置変換装置を用いることで、メモリアドレスを複数の区間に分割し、各区間内でデータの並べ替えを行うようにできる。したがって、扱うデータや実行するデータ処理の性質に応じて、柔軟にデータの並べ替えを制御することができる。また、このような制御を回路規模を増大させることなく容易に実現できる。

以上、本発明のデータ位置変換装置およびデータ位置変換方法を図示の実施の形態に基づいて説明したが、本発明はこれに限定されるものではなく、各部の構成は、同様の機能を有する任意の構成のものに置換することができる。また、本発明に他の任意の構成物や工程が付加されていてもよい。

また、本発明は、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
以上説明した実施の形態の主な技術的特徴は、以下の付記の通りである。

（付記１） メモリに格納されたデータの格納位置を変換するデータ位置変換装置において、
所定のビット長で表現可能な全ての基本アドレスを、値を１ずつ変化させて連続的に生成するアドレス生成手段と、
最下位ビットのみが異なる２つの前記基本アドレス毎に、前記基本アドレスを１ビット右シフトした第１のビット列と、前記第１のビット列を逆順にした第２のビット列とを生成するアドレス変換手段と、
前記第１のビット列の値が前記第２のビット列の値以下である場合、前記第１のビット列と前記第２のビット列との組を入替アドレスと判定し、前記第１のビット列の値が前記第２のビット列の値より大きい場合、前記第１のビット列と前記第２のビット列とをそれぞれ論理反転したビット列の組を前記入替アドレスと判定するアドレス調整手段と、
前記入替アドレスが判定される毎に、前記入替アドレスで特定される前記メモリ内の２つのデータの格納位置を入替えるデータ入替手段と、
を有することを特徴とするデータ位置変換装置。

（付記２） 前記アドレス変換手段は、オフセット部分を示す固定ビット長が予め指定された場合、前記基本アドレスに代えて、前記基本アドレスの上位ビットから前記固定ビット長だけ削除したビット列を用いて、前記第１のビット列と前記第２のビット列とを生成し、
前記アドレス調整手段は、前記入替アドレスと判定した１組のビット列の上位に、前記アドレス変換手段で削除した前記固定ビット長のビット列をそれぞれ付加する、
ことを特徴とする請求項１記載のデータ位置変換装置。

（付記３） メモリに格納されたデータの格納位置を変換するデータ位置変換方法において、
アドレス生成手段が、所定のビット長で表現可能な全ての基本アドレスを、値を１ずつ変化させて連続的に生成し、
アドレス変換手段が、最下位ビットのみが異なる２つの前記基本アドレス毎に、前記基本アドレスを１ビット右シフトした第１のビット列と、前記第１のビット列を逆順にした第２のビット列とを生成し、
アドレス調整手段が、前記第１のビット列の値が前記第２のビット列の値以下である場合、前記第１のビット列と前記第２のビット列との組を入替アドレスと判定し、前記第１のビット列の値が前記第２のビット列の値より大きい場合、前記第１のビット列と前記第２のビット列とをそれぞれ論理反転したビット列の組を前記入替アドレスと判定し、
データ入替手段が、前記入替アドレスが判定される毎に、前記入替アドレスで特定される前記メモリ内の２つのデータの格納位置を入替える、
ことを特徴とするデータ位置変換方法。

（付記４） メモリに格納されたデータの格納位置を変換するデータ位置変換プログラムにおいて、
コンピュータを、
所定のビット長で表現可能な全ての基本アドレスを、値を１ずつ変化させて連続的に生成するアドレス生成手段、
最下位ビットのみが異なる２つの前記基本アドレス毎に、前記基本アドレスを１ビット右シフトした第１のビット列と、前記第１のビット列を逆順にした第２のビット列とを生成するアドレス変換手段、
前記第１のビット列の値が前記第２のビット列の値以下である場合、前記第１のビット列と前記第２のビット列との組を入替アドレスと判定し、前記第１のビット列の値が前記第２のビット列の値より大きい場合、前記第１のビット列と前記第２のビット列とをそれぞれ論理反転したビット列の組を前記入替アドレスと判定するアドレス調整手段、
前記入替アドレスが判定される毎に、前記入替アドレスで特定される前記メモリ内の２つのデータの格納位置を入替えるデータ入替手段、
として機能させることを特徴とするデータ位置変換プログラム。

データ位置変換装置の概要を示す図である。 本実施の形態のシステム構成を示す図である。 第１の実施の形態に係るデータ位置変換部の機能を示すブロック図である。 第１の実施の形態に係る入替アドレスの決定処理の手順を示すフローチャートである。 第１の実施の形態に係るビット列操作の流れを示す図である。 第１の実施の形態に係る変換前後のメモリデータの状態を示す図である。 第２の実施の形態に係るデータ位置変換部の機能を示すブロック図である。 第２の実施の形態に係る入替アドレスの決定処理の手順を示すフローチャートである。 第２の実施の形態に係るビット列操作の流れを示す図である。 第２の実施の形態に係る変換前後のメモリデータの状態を示す図である。

符号の説明

１ データ位置変換装置
１ａ アドレス生成手段
１ｂ アドレス変換手段
１ｃ アドレス調整手段
１ｄ データ入替手段
２ メモリ

Claims (3)

1. メモリに格納されたデータの格納位置を変換するデータ位置変換装置において、
   所定のビット長で表現可能な全ての基本アドレスを、値を１ずつ変化させて連続的に生成するアドレス生成手段と、
   最下位ビットのみが異なる２つの前記基本アドレス毎に、前記基本アドレスを１ビット右シフトした第１のビット列と、前記第１のビット列を逆順にした第２のビット列とを生成するアドレス変換手段と、
   前記第１のビット列の値が前記第２のビット列の値以下である場合、前記第１のビット列と前記第２のビット列との組を入替アドレスと判定し、前記第１のビット列の値が前記第２のビット列の値より大きい場合、前記第１のビット列と前記第２のビット列とをそれぞれ論理反転したビット列の組を前記入替アドレスと判定するアドレス調整手段と、
   前記入替アドレスが判定される毎に、前記入替アドレスで特定される前記メモリ内の２つのデータの格納位置を入替えるデータ入替手段と、
   を有することを特徴とするデータ位置変換装置。
2. 前記アドレス変換手段は、オフセット部分を示す固定ビット長が予め設定された場合、前記基本アドレスに代えて、前記基本アドレスの上位ビットから前記固定ビット長だけ削除したビット列を用いて、前記第１のビット列と前記第２のビット列とを生成し、
   前記アドレス調整手段は、前記入替アドレスと判定した１組のビット列の上位に、前記アドレス変換手段で削除した前記固定ビット長のビット列をそれぞれ付加する、
   ことを特徴とする請求項１記載のデータ位置変換装置。
3. メモリに格納されたデータの格納位置を変換するデータ位置変換方法において、
   アドレス生成手段が、所定のビット長で表現可能な全ての基本アドレスを、値を１ずつ変化させて連続的に生成し、
   アドレス変換手段が、最下位ビットのみが異なる２つの前記基本アドレス毎に、前記基本アドレスを１ビット右シフトした第１のビット列と、前記第１のビット列を逆順にした第２のビット列とを生成し、
   アドレス調整手段が、前記第１のビット列の値が前記第２のビット列の値以下である場合、前記第１のビット列と前記第２のビット列との組を入替アドレスと判定し、前記第１のビット列の値が前記第２のビット列の値より大きい場合、前記第１のビット列と前記第２のビット列とをそれぞれ論理反転したビット列の組を前記入替アドレスと判定し、
   データ入替手段が、前記入替アドレスが判定される毎に、前記入替アドレスで特定される前記メモリ内の２つのデータの格納位置を入替える、
   ことを特徴とするデータ位置変換方法。

Images