(57)【特許請求の範囲】
【請求項１】
複数の入力ポートと複数の出力ポートとを有して前記入力ポートから入力した複数の入力データの出力順序及び出力ポートを替えて出力するデータ並び替え回路に対し、前記入力データの出力順序及び並び替え方を制御する制御情報を生成するコンピュータの制御情報自動生成方法であって、
前記コンピュータの制御情報自動生成部が、
各要素に一意な値が割り当てられ、行を出力時間サイクル、列を前記入力ポートと出力ポートのポート番号とする並び替え前データ配列と、
前記並び替え前データ配列を、前記データ並び替え回路によって並び替えた後のデータの並び替え状態を示す並び替え後データ配列と、
を入力し、
前記並び替え前データ配列におけるＮ行Ｍ列の各データ要素それぞれについての並び替え後データ配列において位置する列の番号を前記データ要素の対応する行列位置に要素として保持するＮ行Ｍ列のシャッフル用ポート配列を生成し、
前記シャッフル用ポート配列における各列間の同じ行番号の要素の示す値が重ならないように、当該シャッフル用ポート配列の列ごとに行を入れ替えた行入替処理を行ってＮ行Ｍ列の第１遅延後シャッフル用ポート配列を生成すると共に、前記行入替処理と同じ行の入れ替えによって並び替え前データ配列を変更したＮ行Ｍ列の第１遅延後データ配列を生成し、前記行入替処理と同じ行の入れ替えによって前記シャッフル用ポート配列における要素を前記第１遅延後シャッフル用ポート配列の行番号が大きい方向をプラス側として移動した行数を当該要素それぞれについて当該要素の行列位置と同じ行列位置に保持したＮ行Ｍ列の行列であって、その行列の要素のうちマイナスを示す値が有る場合にはマイナスを示す値のうち最も小さい値の絶対値を全ての要素に加算した行列を示す第１遅延機構用制御情報を生成し、
前記第１遅延後シャッフル用ポート配列の各列の同一行の各要素が最も小さい行番号の要素から順に昇順に並ぶように前記第１遅延後シャッフル用ポート配列の行ごとに列を入れ替えた列入替処理を行ってＮ行Ｍ列の第１遅延後シャッフル用ポート配列を生成し、前記列入替処理と同じ列の入れ替えによって前記第１遅延後データ配列を変更したＮ行Ｍ列のシャッフル後データ配列を生成し、前記第１遅延後データ配列の各行の要素が前記列入替処理と同じ列の入れ替えによって前記シャッフル後データ配列に位置することとなった行番号をその要素の前記第１遅延後データ配列において位置する行列位置と同じ行列位置に保持するＮ行Ｍ列のシャッフル機構用制御情報を生成し、
前記シャッフル後データ配列の要素が前記並び替え後データ配列における対応する要素の行列位置に並び替えられるように行番号が大きい方向をプラス側として当該要素を列ごとに移動した行数を前記シャッフル後データ配列における当該要素の行列位置と同じ位置に保持したＮ行Ｍ列の行列であって、その行列の要素のうちマイナスを示す値が有る場合にはマイナスを示す値のうち最も小さい値の絶対値を全ての要素に加算した行列を示す第２遅延機構用制御情報を生成する
ことを特徴とする制御情報自動生成方法。
【請求項２】
前記データ並び替え回路は、
前記複数の入力ポートに入力した何れかの入力データの後段の回路への出力タイミングの遅延量を制御可能な遅延機構と、前記複数の入力ポートに入力した何れかの入力データのポート番号をシャッフルして他のポート番号の出力ポートから出力するシャッフル方法を制御可能なシャッフル機構とが直列に組み合わせによって構成され、
前記制御情報自動生成部は
前記遅延機構が並び替えの処理に用いる前記第１遅延機構用制御情報と、前記シャッフル機構が並び替えの処理に用いる前記シャッフル機構用制御情報とを生成する
ことを特徴とする請求項１に記載の制御情報自動生成方法。
【請求項３】
請求項１または２に記載の制御情報自動生成方法において生成された制御情報により、データ並び替えが制御されることを特徴とするデータ並び替え回路。
【請求項４】
複数の入力ポートと複数の出力ポートとを有して前記入力ポートから入力した複数の入力データの出力順序及び出力ポートを替えて出力するデータ並び替え回路に対し、前記入力データの出力順序及び並び替え方を制御する制御情報を生成するコンピュータであって、
各要素に一意な値が割り当てられ、行を出力時間サイクル、列を前記入力ポートと出力ポートのポート番号とする並び替え前データ配列と、
前記並び替え前データ配列を、前記データ並び替え回路によって並び替えた後のデータの並び替え状態を示す並び替え後データ配列と、
を入力し、
前記並び替え前データ配列におけるＮ行Ｍ列の各データ要素それぞれについての並び替え後データ配列において位置する列の番号を前記データ要素の対応する行列位置に要素として保持するＮ行Ｍ列のシャッフル用ポート配列を生成し、
前記シャッフル用ポート配列における各列間の同じ行番号の要素の示す値が重ならないように、当該シャッフル用ポート配列の列ごとに行を入れ替えた行入替処理を行ってＮ行Ｍ列の第１遅延後シャッフル用ポート配列を生成すると共に、前記行入替処理と同じ行の入れ替えによって並び替え前データ配列を変更したＮ行Ｍ列の第１遅延後データ配列を生成し、前記行入替処理と同じ行の入れ替えによって前記シャッフル用ポート配列における要素を前記第１遅延後シャッフル用ポート配列の行番号が大きい方向をプラス側として移動した行数を当該要素それぞれについて当該要素の行列位置と同じ行列位置に保持したＮ行Ｍ列の行列であって、その行列の要素のうちマイナスを示す値が有る場合にはマイナスを示す値のうち最も小さい値の絶対値を全ての要素に加算した行列を示す第１遅延機構用制御情報を生成し、
前記第１遅延後シャッフル用ポート配列の各列の同一行の各要素が最も小さい行番号の要素から順に昇順に並ぶように前記第１遅延後シャッフル用ポート配列の行ごとに列を入れ替えた列入替処理を行ってＮ行Ｍ列の第１遅延後シャッフル用ポート配列を生成し、前記列入替処理と同じ列の入れ替えによって前記第１遅延後データ配列を変更したＮ行Ｍ列のシャッフル後データ配列を生成し、前記第１遅延後データ配列の各行の要素が前記列入替処理と同じ列の入れ替えによって前記シャッフル後データ配列に位置することとなった行番号をその要素の前記第１遅延後データ配列において位置する行列位置と同じ行列位置に保持するＮ行Ｍ列のシャッフル機構用制御情報を生成し、
前記シャッフル後データ配列の要素が前記並び替え後データ配列における対応する要素の行列位置に並び替えられるように行番号が大きい方向をプラス側として当該要素を列ごとに移動した行数を前記シャッフル後データ配列における当該要素の行列位置と同じ位置に保持したＮ行Ｍ列の行列であって、その行列の要素のうちマイナスを示す値が有る場合にはマイナスを示す値のうち最も小さい値の絶対値を全ての要素に加算した行列を示す第２遅延機構用制御情報を生成する
ことを特徴とするコンピュータ。
【請求項５】
前記データ並び替え回路は、
遅延量を制御可能な遅延機構と、シャッフル方法を制御可能なシャッフル機構とが直列に組み合わせによって構成され、
前記遅延機構が並び替えの処理に用いる前記第１遅延機構用制御情報と、前記シャッフル機構が並び替えの処理に用いる前記シャッフル機構用制御情報とを生成する
ことを特徴とする請求項４に記載のコンピュータ。
【請求項６】
複数の入力ポートと複数の出力ポートとを有して前記入力ポートから入力した複数の入力データの出力順序及び出力ポートを替えて出力するデータ並び替え回路に対し、前記入力データの出力順序及び並び替え方を制御する制御情報を生成するコンピュータを、
各要素に一意な値が割り当てられ、行を出力時間サイクル、列を前記入力ポートと出力ポートのポート番号とする並び替え前データ配列と、前記並び替え前データ配列を、前記データ並び替え回路によって並び替えた後のデータの並び替え状態を示す並び替え後データ配列と、を入力する手段、
前記並び替え前データ配列におけるＮ行Ｍ列の各データ要素それぞれについての並び替え後データ配列において位置する列の番号を前記データ要素の対応する行列位置に要素として保持するＮ行Ｍ列のシャッフル用ポート配列を生成する手段、
前記シャッフル用ポート配列における各列間の同じ行番号の要素の示す値が重ならないように、当該シャッフル用ポート配列の列ごとに行を入れ替えた行入替処理を行ってＮ行Ｍ列の第１遅延後シャッフル用ポート配列を生成すると共に、前記行入替処理と同じ行の入れ替えによって並び替え前データ配列を変更したＮ行Ｍ列の第１遅延後データ配列を生成し、前記行入替処理と同じ行の入れ替えによって前記シャッフル用ポート配列における要素を前記第１遅延後シャッフル用ポート配列の行番号が大きい方向をプラス側として移動した行数を当該要素それぞれについて当該要素の行列位置と同じ行列位置に保持したＮ行Ｍ列の行列であって、その行列の要素のうちマイナスを示す値が有る場合にはマイナスを示す値のうち最も小さい値の絶対値を全ての要素に加算した行列を示す第１遅延機構用制御情報を生成する手段、
前記第１遅延後シャッフル用ポート配列の各列の同一行の各要素が最も小さい行番号の要素から順に昇順に並ぶように前記第１遅延後シャッフル用ポート配列の行ごとに列を入れ替えた列入替処理を行ってＮ行Ｍ列の第１遅延後シャッフル用ポート配列を生成し、前記列入替処理と同じ列の入れ替えによって前記第１遅延後データ配列を変更したＮ行Ｍ列のシャッフル後データ配列を生成し、前記第１遅延後データ配列の各行の要素が前記列入替処理と同じ列の入れ替えによって前記シャッフル後データ配列に位置することとなった行番号をその要素の前記第１遅延後データ配列において位置する行列位置と同じ行列位置に保持するＮ行Ｍ列のシャッフル機構用制御情報を生成する手段、
前記シャッフル後データ配列の要素が前記並び替え後データ配列における対応する要素の行列位置に並び替えられるように行番号が大きい方向をプラス側として当該要素を列ごとに移動した行数を前記シャッフル後データ配列における当該要素の行列位置と同じ位置に保持したＮ行Ｍ列の行列であって、その行列の要素のうちマイナスを示す値が有る場合にはマイナスを示す値のうち最も小さい値の絶対値を全ての要素に加算した行列を示す第２遅延機構用制御情報を生成する手段、
として機能させることを特徴とする制御情報自動生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、遅延機構とシャッフル機構によりデータの並び替えを行うデータ並び替え回路に対する制御情報自動生成方法、データ並び替え回路、及び制御情報自動生成プログラムに関するものである。
【背景技術】
【０００２】
ある種の信号処理アルゴリズムにおいては、演算器と、遅延機構及びシャッフル機構により構成されたデータ並び替え回路を用いることにより、効率の良い回路を設計できることが知られている。例として、ＦＦＴ（Ｆａｓｔ・Ｆｏｕｒｉｅｒ・Ｔｒａｎｓｆｏｒｍ）は、バタフライ演算器、及び回転因子乗算器間に上記データ並び替え回路を組み込むことにより、高いスループットを持ち、かつ、面積コストの小さい回路を設計することができる。
【０００３】
このような、ある特定アルゴリズム向けのデータ並び替え回路を組み込んだ回路では、遅延機構における遅延量やシャッフル機構におけるシャッフル方法が固定的であり、設計した回路を対象としたアルゴリズム以外に利用することは難しかった。そこで、データ並び替え回路において、遅延量やシャッフル方法をユーザが作成したプログラムによって変更できるようにして、様々なアルゴリズムに対応させることができるようにするデータ並び替え回路が提案されており、この一例を図２２に示す。
【０００４】
図２２に示すデータ並び替え回路２００は、データ並び替え回路と同様な構成のものである（特許文献５を参照）。このデータ並び替え回路２００は、カウンタ２０１、制御情報テーブル２０２、１段目の可変遅延回路２０３〜２０６、シャッフル回路２０７、２段目の可変遅延回路２０８〜２１１、制御情報削除器２１２〜２１５、及び制御情報結合器２１６〜２１９から構成されている。このデータ並び替え回路２００には入力データ（ＩＤ＃０〜ＩＤ＃３）とモード信号ＭＯＤＥとカウンタリセット信号ＲＳＴが入力され、出力データ（ＯＤ＃０〜ＯＤ＃３）が出力される。
【０００５】
ここで、モード信号ＭＯＤＥは、６４点ＦＦＴ用並び替えや３２点ＦＦＴ用並び替えなどの、並び替えパターンの種類（演算モード）を指定するための信号である。カウンタリセット信号ＲＳＴは並び替えパターンの開始時刻を指定するための信号である。カウンタ２０１は、カウンタリセット信号ＲＳＴによりリセットされ、その後、遅延量の単位である１サイクル毎にカウントアップする。制御情報テーブル２０２内には、カウンタ２０１の示すカウント値とモード信号ＭＯＤＥの示す演算モードとの組み合わせに対応する制御情報が格納されている。制御情報には、１段目の可変遅延回路２０３〜２０６の遅延量と、シャッフル回路２０７の制御情報と、２段目の可変遅延回路２０８〜２１１の遅延量とが含まれる。 
【０００６】
制御情報テーブル２０２から出力された制御情報は、制御情報結合器２１６〜２１９において入力データ（ＩＤ＃０〜ＩＤ＃３）と結合されて１段目の可変遅延回路２０３〜２０６へ入力される。また、制御情報は、制御情報削除器２１２〜２１５において、２段目の可変遅延回路２０８〜２１１から出力された結合データから取り除かれる。結合データから制御情報を取り除いたデータがデータ並び替え回路２００の出力データ（ＯＤ＃０〜ＯＤ＃３）となる。
【０００７】
なお、関連する離散フーリエ変換装置がある（特許文献１を参照）。この特許文献１に記載の離散フーリエ変換装置は、変換演算量を削減し演算回路を簡素化した離散フーリエ変換装置および離散フーリエ逆変換装置を提供することを目的としている。
【０００８】
また、関連する高速フーリエ変換演算回路がある（特許文献２を参照）。この特許文献２に記載の高速フーリエ変換演算回路は、高速フーリエ変換回路に関し、入力データ点数Ｎに対して、ＯＦＤＭの搬送波数Ｋ（≦Ｎ）が変更になっても、同一の回路で適応的に高速フーリエ変換が行える回路を提供することを目的としている。
【０００９】
また、関連する高速フーリエ変換を用いて短い待ち時間でアレイ処理を行う並列システムがある（特許文献３を参照）。この特許文献３に記載の並列システムは、高速フーリエ変換における待ち時間を最小化し、接続及び設計を単純化することを目的としている。
また、関連する可変サイズの高速直交変換を実施する方法および機器がある（特許文献４を参照）。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００８-０５２５０４号公報
【特許文献２】特開平１０−２８３３４１号公報
【特許文献３】特開平１１−１６１６３７号公報
【特許文献４】特表２００８-５０６１９１号公報
【特許文献５】特願２００９-２１８９１９号
【発明の概要】
【発明が解決しようとする課題】
【００１１】
図２２に示すデータ並び替え回路には、制御情報テーブル２０２を構成する制御情報を作成することが難しく、その作成には多大な時間がかかるという問題がある。
上記問題点を明らかにするために、まず図２３及び図２４を参照して、データ並び替え回路２００の動作を説明する。図２３は、図２２に示すデータ並び替え回路２００におけるデータ並び替えの様子を示す図である。図２４は、このときの制御情報テーブル２０２の内容を示す図である。図２４に示す制御情報テーブルに登録される制御情報として、１段目遅延、シャッフル、２段目遅延のそれぞれについて、ポートＩＤ＃０，ＩＤ＃１，ＩＤ＃２，ＩＤ＃３に対する値が記載されている。 
【００１２】
図２３に示すタイムチャートにおいて、最初のサイクル（サイクル０）では、カウントリセット信号が有効であるためカウンタ２０１のカウント値がリセットされる。また、最初の４サイクル間（サイクル０〜３）はモード信号が００１であるため、最初のサイクルでは、図２４に示す制御情報テーブルの最初の行の制御情報が読み出される。読み出された制御情報は、制御情報結合器２１６〜２１９において入力データと結合され、１段目の可変遅延回路２０３〜２０６に入力される。なお、図２３中では、制御情報と結合されたデータを「データ名（１段目遅延量、シャッフル制御信号、２段目遅延量）」という形式で表現する。また、このデータを結合データと呼ぶことにする。 
【００１３】
例えば、カウント値００００（サイクル０）において、入力ポート＃０に入力されるデータＡに対する１段目の遅延量は２であるため、最初のサイクルの入力データＡには２サイクル遅延の制御情報が結合され、サイクル２において１段目の可変遅延回路２０３から出力される。
同様に、カウント値０００１（サイクル１）において、入力ポート＃０に入力されるデータＣには、図２４中のカウント値０００１の入力ポート＃０に対する１段目の遅延量が４であるため、４サイクル分の遅延を示す制御情報が結合され、サイクル５において１段目の可変遅延回路２０３から出力される。なお、結合データ中の制御情報は、結合データ中のデータと共に遅延されたりシャッフルされたりする。
【００１４】
サイクル３（カウント値０００３）において、シャッフル回路２０７の入力＃０に入力される結合データＥは、シャッフル制御情報が１を示す制御情報を含んでいる。このため、サイクル３におけるシャッフル回路２０７の出力＃０には、シャッフル回路２０７の入力＃１にある結合データＢが出力される。同様に、シャッフル回路２０７の出力＃１には、シャッフル回路２０７の入力＃０にある結合データＥが出力される。 
サイクル３に２段目の可変遅延回路２０８の入力＃０に入力される結合データＢは、２段目遅延量として１を含んでいる。このため、結合データＢは次のサイクルであるサイクル４に２段目の可変遅延回路２０８から出力される。同様に、サイクル３に２段目の可変遅延回路２０９の入力＃１に入力される結合データＥの２段目遅延量は０であるので、結合データＥは同じサイクルであるサイクル３に２段目の可変遅延回路２０９から出力される。
【００１５】
ここで、上記動作を制御する制御情報を使用者が作成する場合、使用者は上記動作の様子を全て把握して、プログラムしなければならない。すなわち使用者は、サイクル毎の各可変遅延回路への入力データと制御方法、及びカウンタアップの様子を把握しなければならず、設計、実装、デバッグに多大な時間がかかる。
【００１６】
本発明の主たる課題は、データ並び替え回路において並び替えを制御する制御情報の設計、実装、デバッグに必要な時間を短縮することにある。
【課題を解決するための手段】
【００１７】
本発明は上記課題を解決するためになされたものであり、本発明の制御情報自動生成方法は、複数の入力ポートと複数の出力ポートとを有して前記入力ポートから入力した複数の入力データの出力順序及び出力ポートを替えて出力するデータ並び替え回路に対し、前記入力データの出力順序及び並び替え方を制御する制御情報を生成するコンピュータの制御情報自動生成方法であって、前記コンピュータの制御情報自動生成部が、各要素に一意な値が割り当てられ、行を出力時間サイクル、列を前記入力ポートと出力ポートのポート番号とする並び替え前データ配列と、前記並び替え前データ配列を、前記データ並び替え回路によって並び替えた後のデータの並び替え状態を示す並び替え後データ配列と、を入力し、前記並び替え前データ配列におけるＮ行Ｍ列の各データ要素それぞれについての並び替え後データ配列において位置する列の番号を前記データ要素の対応する行列位置に要素として保持するＮ行Ｍ列のシャッフル用ポート配列を生成し、前記シャッフル用ポート配列における各列間の同じ行番号の要素の示す値が重ならないように、当該シャッフル用ポート配列の列ごとに行を入れ替えた行入替処理を行ってＮ行Ｍ列の第１遅延後シャッフル用ポート配列を生成すると共に、前記行入替処理と同じ行の入れ替えによって並び替え前データ配列を変更したＮ行Ｍ列の第１遅延後データ配列を生成し、前記行入替処理と同じ行の入れ替えによって前記シャッフル用ポート配列における要素を前記第１遅延後シャッフル用ポート配列の行番号が大きい方向をプラス側として移動した行数を当該要素それぞれについて当該要素の行列位置と同じ行列位置に保持したＮ行Ｍ列の行列であって、その行列の要素のうちマイナスを示す値が有る場合にはマイナスを示す値のうち最も小さい値の絶対値を全ての要素に加算した行列を示す第１遅延機構用制御情報を生成し、前記第１遅延後シャッフル用ポート配列の各列の同一行の各要素が最も小さい行番号の要素から順に昇順に並ぶように前記第１遅延後シャッフル用ポート配列の行ごとに列を入れ替えた列入替処理を行ってＮ行Ｍ列の第１遅延後シャッフル用ポート配列を生成し、前記列入替処理と同じ列の入れ替えによって前記第１遅延後データ配列を変更したＮ行Ｍ列のシャッフル後データ配列を生成し、前記第１遅延後データ配列の各行の要素が前記列入替処理と同じ列の入れ替えによって前記シャッフル後データ配列に位置することとなった行番号をその要素の前記第１遅延後データ配列において位置する行列位置と同じ行列位置に保持するＮ行Ｍ列のシャッフル機構用制御情報を生成し、前記シャッフル後データ配列の要素が前記並び替え後データ配列における対応する要素の行列位置に並び替えられるように行番号が大きい方向をプラス側として当該要素を列ごとに移動した行数を前記シャッフル後データ配列における当該要素の行列位置と同じ位置に保持したＮ行Ｍ列の行列であって、その行列の要素のうちマイナスを示す値が有る場合にはマイナスを示す値のうち最も小さい値の絶対値を全ての要素に加算した行列を示す第２遅延機構用制御情報を生成することを特徴とする。
【発明の効果】
【００１８】
本発明の制御情報自動生成方法においては、データ並び替え回路に対する制御情報を、「並び替え前データ配列」と「並び替え後データ配列」とを基に自動的に生成するようにしたので、これにより、データ並び替え回路を制御する制御情報の設計、実装、デバッグに必要な時間を短縮することができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施形態に係わるデータ並び替え回路の構成を示す図である。
【図２】制御情報結合機構の構成例を示す図である。
【図３】第１遅延機構の構成例を示す図である。
【図４】シャッフル機構の構成例を示す図である。
【図５】制御情報分離機構の構成例を示す図である。
【図６】制御情報自動生成の手順を示すフローチャートである。
【図７】シャッフルポートサーチ手順の擬似コードを示す図である。
【図８】関数ｓｅａｒｃｈ＿ｐｏｒｔの擬似コードを示す図である。
【図９】第１遅延機構用制御情報生成手順の擬似コードを示す図である。
【図１０】関数ｉｎｉｔｉａｌｉｚｅ＿ｆｄ＿ｐｏｒｔの擬似コードを示す図である。
【図１１】関数ｄｏ＿ｆｄ＿ｓｅａｒｃｈの擬似コードを示す図である。
【図１２】関数ｍｏｄｉｆｙ＿ｄｅｌａｙ＿ａｒｒａｙの擬似コードを示す図である。
【図１３】シャッフル機構用制御情報生成手順の擬似コードを示す図である。
【図１４】第２遅延機構用制御情報生成手順の擬似コードを示す図である。
【図１５】関数ｇｅｔ＿ｓｄｕ＿ｖａｌの擬似コードを示す図である。
【図１６】実施例１における「並び替え前データ配列」と「並び替え後データ配列」を示す図である。
【図１７】シャッフルポートサーチ手順の具体例を示す図である。
【図１８】第１遅延機構用制御情報生成手順の具体例を示す図である。
【図１９】シャッフル機構用制御情報生成手順の具体例を示す図である。
【図２０】第２遅延機構用制御情報生成手順の具体例を示す図である。
【図２１】ソフトウェアにより本発明を実施する場合の例を示す図である。
【図２２】データ並び替え回路の例を示す図である。
【図２３】図２２の並び替え回路におけるデータ並び替えの様子を示すタイムチャートである。
【図２４】図２２に示すデータ並び替え回路における制御情報テーブルの内容を示す図である。
【発明を実施するための形態】
【００２０】
［第１の実施形態］
次に、本発明の実施形態について図面を参照して詳細に説明する。図１は、本発明の実施形態に係わるデータ並び替え回路１００の構成を示す図である。図１に示すデータ並び替え回路１００は、カウンタ１１０、制御情報テーブル１２０、制御情報結合機構１３０、第１遅延機構１４０、シャッフル機構１５０、第２遅延機構１６０、制御情報分離機構１７０から構成される。
【００２１】
データ並び替え回路１００には入力データ（ＩＤ＃０〜ＩＤ＃Ｍ−１）とモード信号ＭＯＤＥとカウンタリセット信号ＲＳＴが入力され、出力データ（ＯＤ＃０〜ＯＤ＃Ｍ−１）が出力される。ここで、モード信号ＭＯＤＥとカウンタリセット信号ＲＳＴについては、前述した図２２に示すモード信号ＭＯＤＥとカウンタリセット信号ＲＳＴと同様に作用する信号である。また、制御情報テーブル１２０内に格納される制御情報は、制御情報自動生成部１８０において、ユーザが作成して入力した「並び替え前データ配列」及び「並び替え後データ配列」を基に自動的に作成される。
【００２２】
ここで、「並び替え前データ配列」及び「並び替え後データ配列」はそれぞれサイズＮ×Ｍの行列（Ｎ行、Ｍ列の行列）で表される。列数Ｍは、データ並び替え回路１００の入力ＩＤ＃０〜ＩＤ＃Ｍ−１（ポート番号）に対応しており、同時刻にデータ並び替え回路１００へ入力されるデータを示している。一方、行数Ｎは、データ並び替え回路１００へ入力されるデータの入力時刻サイクルを表しており、０，１，２，・・・，Ｎ−１はそれぞれ、１サイクル目入力、２サイクル目入力、３サイクル目入力、・・・、Ｎ−１サイクル目入力を示している。また、「並び替え前データ配列」の配列内要素にはそれぞれ一意のデータが割り振られる。例として、図１に示す「並び替え前データ配列」では０〜（Ｎ−１）×（Ｍ−１）の自然数が要素内に格納される様子を示している。また、「並び替え後データ配列」の配列内各要素にも、それぞれ一意のデータが割り振られており、さらに、それぞれの要素は、「並び替え前データ配列」の要素と一対一に対応する。
【００２３】
図２は、制御情報結合機構１３０の構成例を示す図である。図２に示すように、制御情報結合機構１３０は制御情報結合器１３１をＭ段並列に並べて構成したユニットであり、入力データＩＤ＃０〜ＩＤ＃Ｍ−１と、入力制御信号（制御情報）ＩＣ＃０〜ＩＣ＃Ｍ−１をそれぞれ結合して出力する。
図３は、第１遅延機構の構成例を示す図である。図３に示すように、第１遅延機構１４０は、可変遅延回路１４１をＭ段並列に並べて構成したユニットであり、入力データ＃０〜＃Ｍ−１を、それぞれに結合された制御信号（制御情報）に従って遅延させて出力＃０〜＃Ｍ−１に出力する。ここで、可変遅延回路１４１の構成と動作は、図２２に示した可変遅延回路２０６と同様であり、重複する説明は省略する。なお、第２遅延機構１６０についても、図３に示す第１遅延機構１４０と同様な構成のものである。
【００２４】
図４は、シャッフル機構１５０の構成を示す図である。図４に示すシャッフル機構１５０は、制御情報取り出し器１５１と選択器１５２をＭ段並列に並べて構成されるものである。シャッフル機構１５０は、入力データ＃０〜＃Ｍ−１の並びを入れ替え、出力データ＃０〜＃Ｍ−１に出力する。ここで、シャッフル機構１５０の構成と動作は、図２２に示すシャッフル回路２０７と同様であり、重複する説明は省略する。
また、図５は、制御情報分離機構の構成を示す図である。制御情報分離機構１７０は、制御情報削除器１７１をＭ段並べた構成である。制御情報削除器１７１は、入力されたデータに結合された上記制御信号（制御情報）を削除して、出力する。
【００２５】
次に、制御情報テーブル１２０に格納される制御情報を自動的に生成する方法について説明する。本発明における制御情報自動生成方法は、図６に示すように、シャッフルポートサーチ手順（ステップＳ１０１）、第１遅延機構用制御情報生成手順（ステップＳ１０２）、シャッフル機構用制御情報生成手順（ステップＳ１０３）、及び第２遅延機構用制御情報生成手順（ステップＳ１０４）からなる方法である。
【００２６】
まず、シャッフルポートサーチ手順（ステップＳ１０１）について、図７、図８を参照して説明する。このシャッフルポートサーチ手順では、「並び替え前データ配列」と「並び替え後データ配列」を走査し、「並び替え前データ配列」内の各要素が、データ並び替え回路１００を通過後に、どのポートに出力されるかを分析し、それをＮ行Ｍ列の「シャッフル用ポート配列」に記録する。
図７は、シャッフルポートサーチの擬似コードｓｈｕｆｆｌｅ＿ｐｏｒｔ＿ｓｅａｒｃｈを示すものである。なお、本擬似コードでは、「並び替え前データ配列」をｄａｔａ＿ｂｅｆとし、「並び替え後データ配列」をｄａｔａ＿ａｆｔとしている。また、出力である「シャッフル用ポート配列」はｓｈｕｆｆｌｅ＿ｐｏｒｔで示している。また、図８は、図７内１０行目のｓｅａｒｃｈ＿ｐｏｒｔ関数の内容を示すものである。ここで、ｓｅａｒｃｈ＿ｐｏｒｔ関数は引数に１つのインデクスｓｒｃと配列ｄａｔａ＿ａｆｔをとり、指定されたインデクスが同じく引数で指定された配列のどの列にあるかを調べ、その列番号を返す関数である。
【００２７】
図７に示すコードにおいては、まず、６行目で示すように、入力データのＮ行において、７行目〜１４行目までの処理を繰り返す。さらに、７行目が示すように、入力データのｒｏｗ行目Ｍ列において、それぞれ８行目〜１３行目までの処理を適用する。次に、９行目において、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」のｒｏｗ行目ｃｏｌ列目の要素に指定されたインデクスを取得する。１０行目ではｓｅａｒｃｈ＿ｐｏｒｔ関数を呼び出して、９行目で取得したインデクスが「並び替え後データ配列ｄａｔａ＿ａｆｔ」のどの列に位置しているかを得る。この結果を、「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」のｒｏｗ行目ｃｏｌ列目に設定する。
【００２８】
次に、図８に示すｓｅａｒｃｈ＿ｐｏｒｔ関数について説明する。ｓｅａｒｃｈ＿ｐｏｒｔ関数では、まず、３行目で示すように、引数で与えられた「並び替え後データ配列ｄａｔａ＿ａｆｔ」のＮ行において、４行目〜１０行目までの処理を行う。さらに、４行目が示すように、「並び替え後データ配列」のｒｏｗ行目のＭ列それぞれに対し、５行目〜９行目までの処理を適用する。次に、５行目では引数で与えられたインデクスｓｒｃと、「並び替え後データ配列ｄａｔａ＿ａｆｔ」のｒｏｗ行目ｃｏｌ列目のインデクスを比較する。ここで、これらインデクスが一致していた場合は、一時変数ｒｅｓｕｌｔに列番号ｃｏｌを格納する。一致しなかった場合は処理を行わない。最後に、一時変数ｒｅｓｕｌｔを返し、処理を終了する。
【００２９】
上述したシャッフルポートサーチ手順（ステップＳ１０１）により、図７の下側の図に示すように、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」と「並び替え後データ配列ｄａｔａ＿ａｆｔ」を走査し、「並び替え前データ配列」の各要素が、データ並び替え回路１００を通過後に、どのポートに出力されるかを分析し、それをＮ行Ｍ列の「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」に記録する。
【００３０】
次に、第１遅延機構用制御情報生成手順（ステップＳ１０２）について、図９から図１２を参照して説明する。この第１遅延機構用制御情報生成手順（ステップＳ１０２）においては、図９の下側の図に示すように、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」、「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」を入力とし、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」、「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」、及び「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」を出力する。ここで、「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」は「並び替え前データ配列ｄａｔａ＿ｂｅｆ」内の各要素に対する遅延情報を配列形式で表したものである。
【００３１】
図９に示す擬似コードは、第１遅延機構用制御情報生成手順（ステップＳ１０２）を示す擬似コードｍａｋｅ＿ｆｄu＿ａｒｒａｙである。この第１遅延機構用制御情報生成手順（ステップＳ１０２）では、まず、５行目において、ｉｎｉｔｉａｌｉｚｅ＿ｆｄ＿ｐｏｒｔ関数によって、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」と「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」の初期化を行う。ここで、Ｉｎｉｔｉａｌｉｚｅ＿ｆｄ＿ｐｏｒｔ関数の処理内容を図１０に示す。
図１０に示すように、Ｉｎｉｔｉａｌｉｚｅ＿ｆｄ＿ｐｏｒｔ関数は「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」と「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」の０列目に、それぞれ「並び替え前データ配列ｄａｔａ＿ｂｅｆ」と「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」の０列目を代入することによって初期化する。
【００３２】
次に、図９の１３行目に示すとおり、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」及び「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」のＮ行と１列目からＭ−１列目に対し、ｄｏ＿ｆｄ＿ｓｅａｒｃｈ関数を呼び出し、第１遅延機構によるデータ並び替え方法の探索を行う。ここで、ｄｏ＿ｆｄ＿ｓｅａｒｃｈ関数は、現在探索を行うシャッフル用ポート配列の要素が、第１遅延後において、同じ行の他のシャッフルポートを示すデータと一致しないような位置を探索する関数である。なお、このｄｏ＿ｆｄ＿ｓｅａｒｃｈ関数の処理内容を図１１に示す。
【００３３】
図１１に示すように、ｄｏ＿ｆｄ＿ｓｅａｒｃｈ関数は、入力として、「並び替え前データ配列」の１要素と、「シャッフル用ポート配列」の１要素、及び、関数を呼び出した時点の列番号、さらに、生成途中の「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」と「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」を持つ。本関数では、４行〜１１行目までの処理が示すように、入力されたシャッフル用ポート配列の１要素をソースとして、生成途中の「第１遅延後シャッフル用ポート配列」を１行ずつ列方向に一致検索する。次に、１２行目〜１７行目が示すように、呼び出した時点の列番号まで一致しなかった場合、生成途中の「第１遅延後データ配列」と「第１遅延後シャッフル用ポート配列」の呼び出した時点の列番号及び該当行に、それぞれ入力した「並び替え前データ配列」の１要素と「シャッフル用ポート配列」の１要素を代入する。最後に、該当行を返して関数を終了する。
【００３４】
次に、図９において、ｄｏ＿ｆｄ＿ｓｅａｒｃｈ関数終了後の１６行目において、ｄｏ＿ｆｄ＿ｓｅａｒｃｈ関数より返された行番号から現在の行番号の差分を求め、「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」に登録する。
最後に、１９行目において、「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」に設定された遅延を、図１２に示すｍｏｄｉｆｙ＿ｄｅｌａｙ＿ａｒｒａｙ関数によって調整する。これは、入力引数の配列ｆｄ＿ａｒｒａｙに負の値を持つ遅延が設定されていた場合、その値をｆｄ＿ａｒｒａｙ全体に加算することによって、全要素を正もしくは０の値に修正する関数である。具体的には、図１２の４行〜１２行目までで、配列内の最小値を探索する。次に、１４行〜１９行目までで、見つかった最小値の符号を反転した値を、上記配列内の全要素に加算する処理を行う。
【００３５】
このように、第１遅延機構用制御情報生成手順（ステップＳ１０２）においては、「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」と「並び替え前データ配列ｄａｔａ＿ｂｅｆ」とを基に、同じ時間サイクルの同じポートに複数の要素が重複して出力されないように、遅延量により各要素が出力される時間サイクルを調整するための「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」を生成する。
【００３６】
次に、シャッフル機構用制御情報生成手順（ステップＳ１０３）について、図１３を参照して説明する。なお、図１３はシャッフル機構用制御情報生成の擬似コードｍａｋｅ＿ｓｈｕｆｆｌｅ＿ａｒｒａｙである。このシャッフル機構用制御情報生成手順では、図１３の下側の図に示すように、入力として「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」と「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」を持ち、「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」と「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」を出力する。
【００３７】
このシャッフル機構用制御情報生成手順では、図１３の４行〜１４行目が示すように、Ｎ行Ｍ列の各要素について、次の処理を行う。まず、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」の各要素を、それぞれに対応した「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」の要素ｄｅｓｔｐｏｒｔを読み出す。図１３では、これは７、８行目に当る。次に、読み出したデータを、「シャッフル後データ配列」のｒｏｗ行目の、ｄｅｓｔｐｏｒｔが示す列に代入する。さらに、ｄｅｓｔｐｏｒｔを「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」のｒｏｗ行目ｃｏｌ列目に代入する。
【００３８】
このように、シャッフル機構用制御情報生成手順（ステップＳ１０３）においては、「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」内に記録されたポート番号が、出力ポートに一致するように並び替えを行うと共に、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」内の各要素についても並び替えを行い、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」内の各要素に対する並び替え方法の情報により、「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」を生成する。
【００３９】
なお、本手順では上記のように制御情報の配列を生成したが、これは、対象としたアーキテクチャに従った手順に変更しても良い。例えば、未公知の先願発明（特許文献５）に開示されたデータ並び替え回路のシャッフル機構においては、入力ポート毎にどの出力ポートに出力するかを選択するような構成であってもよいし、出力ポートごとにどの入力ポートからのデータを選択するかでもよいとされている。後者の場合、本手順における「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」の生成においては、ｒｏｗ行目の、ｄｅｓｔｐｏｒｔ列目に、現在の列番号ｃｏｌを代入するようにすればよい。
【００４０】
次に、第２遅延機構用制御情報生成手順（ステップＳ１０４）について、図１４及び図１５を参照して説明する。なお、図１４は、第２遅延機構用制御情報生成手順の擬似コードｍａｋｅ＿ｓｄｕ＿ａｒｒａｙを示す図である。この第２遅延機構用制御情報生成手順では、図１４に下側の図に示すように、入力として「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」、及び「並び替え後データ配列ｄａｔａ＿ａｆｔ」を持ち、「第２遅延機構用制御情報ｓｄｕ＿ａｒｒａｙ」を出力する。
本手順では、図１４の４行〜１４行が示すように、Ｎ行Ｍ列配列の各要素に対し、次の処理を行う。まず、ｒｏｗ行ｃｏｌ列目のｓｈ＿ｄａｔａ＿ｂｅｆのデータをｄａｔａに読み出す。次に、ｄａｔａとｄａｔａ＿ａｆｔと、ｒｏｗを入力としてｇｅｔ＿ｓｄｕ＿ｖａｌ関数を実行し、ｄａｔａに対する第２遅延機構用制御情報を得て、それをｓｄｕ＿ａｒｒａｙのｒｏｗ行ｃｏｌ列目に登録する。
【００４１】
ここで、ｇｅｔ＿ｓｄｕ＿ｖａｌ関数の詳細を図１５に示す。ｇｅｔ＿ｓｄｕ＿ｖａｌ関数は、入力されたｄａｔａをキーとして、同じく入力されたデータ配列ｄａｔａ＿ａｆｔを１要素ずつ探索し、一致した時点の行番号ｒｏｗと入力されたｎｏｗ＿ｒｏｗの差分を計算することによって第２遅延機構用制御情報を求める。また、図１４の１２行目が示すように、生成された第２遅延機構用情報を、上記図１２に既に示したｍｏｄｉｆｙ＿ｄｅｌａｙ＿ａｒｒａｙ関数によって調整する。
【００４２】
このように、第２遅延機構用制御情報生成手順（ステップＳ１０４）においては、「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」と「並び替え後データ配列ｄａｔａ＿ａｆｔ」とが一致するよう遅延量によって時間サイクルを調整して並び替えを行い、その並び替え方法の情報を「第２遅延機構用制御情報ｓｄｕ＿ａｒｒａｙ」として生成する。
【００４３】
以上説明した手順により、図１に示すデータ並び替え回路１００に必要な第１遅延機構用制御情報、シャッフル用制御情報、第２遅延機構用制御情報が得られることとなる。なお、これらデータ配列の各要素は、それぞれが、並び替え前データ配列、第１遅延後データ配列、シャッフル後データ配列の各要素に一意に対応しており、各インデクスをキーとして、これら情報をメモリに配置すれば、制御用のメモリを構成することができる。ここで、制御用メモリの構成方法については、各情報に個別のテーブルを用意しても良いし、全てをまとめて１つのテーブルに配置してもよい。
【００４４】
［他の実施形態］ 
次に、本発明の他の実施形態として、図１における第１遅延機構、シャッフル機構、第２遅延機構は、それぞれ自由な組み合わせとして選ぶ構成に対する本方法による制御情報の自動生成が挙げられる。一つの例としては、第２遅延機構がない構成が考えられる。この場合の本方法による制御情報の自動生成では、第２遅延機構用制御情報生成手順（ステップＳ１０４）を行わない構成となる。
【００４５】
また、別の例としては、第１遅延機構がない構成が考えられる。この場合の本方法による制御情報の自動生成では、並び替え前データ配列と、シャッフルポートサーチにより求められたシャッフル用ポート配列を、それぞれシャッフル機構用制御情報生成手順（ステップＳ１０３）の入力である「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」と、「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」とを入力し、処理を行う。
さらに別の例としては、遅延機構のみの構成が考えられる。この場合、シャッフルポートサーチ手順、及び第１遅延機構用制御情報生成手順、シャッフル機構用制御情報生成手順をスキップし、第２遅延機構用制御情報生成手順のみを行う構成とすればよい。また、シャッフル機構のみの構成が考えられる。この場合、シャッフルポートサーチ手順とシャッフル機構用制御情報生成手順のみ行うような構成とすればよい。
【００４６】
最後に、本発明の制御情報自動生成方法は、未公知の先願発明（特許文献５）に開示された様々な実施形態に適用してよい。例えば、上記未公知の先願発明においては、制御情報テーブルの参照の方法として、モード毎にカウンタの最大値を設定するように構成し、モード毎のカウンタの最大値でカウンタの値を割った剰余を用いて制御情報テーブルを参照したり、モード毎のカウンタの最大値以下に収まるように抽出したカウンタのビット列の一部を用いて制御情報テーブルを参照したりするようにしてもよいと述べている。本発明の制御情報自動生成方法は、このうちどの方法においても、適用することができる。
【実施例１】
【００４７】
次に、具体的な実施例により本発明のデータ並び替え回路における制御情報自動生成方法について説明する。ここでは上記第１の実施形態に基づいて、実施例を説明する。さらに、説明の簡略化のために、Ｎ=４，Ｍ=４とし、「並び替え前データ配列」、及び「並び替え後データ配列」を図１６に示すように、Ａ〜Ｐのインデクスが割り当てられた配列とする。
【００４８】
まず、シャッフルポートサーチの具体的な手順を図１７を参照して説明する。図１７は、「並び替え前データ配列」と「並び替え後データ配列」から「シャッフル用ポート配列」を生成する様子を示している。なお、「並び替え後データ配列」には、行番号と列番号を付記している。例として、網掛けで示される「並び替え前データ配列」の０行０列目の要素Ａにおいては、「並び替え後データ配列」の要素Ａがある列番号は０である。そのため、シャッフル用ポート配列の０行０列目に０と記述する。一方、「並び替え前データ配列」の３行０列目の要素Ｍは、「並び替え後データ配列」では３列目に位置している。そのため、シャッフル用ポート配列の３行０列目に３と記述する。
【００４９】
次に、第１遅延機構用制御情報の生成手順の具体的な例を図１８を参照して説明する。図１８は、第１遅延機構用制御情報の生成手順における、入力の「並び替え前データ配列」と「シャッフル用ポート配列」の変化の様子、及び第１遅延後データ配列、第１遅延後シャッフル用ポート配列、第１遅延機構用制御情報の出力の様子を示している。
まず、本手順開始時点の様子を示す図１８の左上の図（Ａ）の状態においては、太い黒線で囲んで示したシャッフル用ポート配列の１列目のそれぞれの要素において、網掛けで示された０列の要素の番号と比較し、同じ番号が設定されている場合は、行をずらして配置する処理を行う。
【００５０】
具体的には、図（Ａ）のシャッフル用ポート配列０行１列目の要素は０であるが、この値を同配列０行０列目の要素と比較すると一致している。そこで、１行０列目の要素と比較すると、要素が異なるため、図（Ｂ）のシャッフル用ポート配列に示すように、同配列０行０列目の値を１行１列目に設定する。さらに、本処理では０行１列目の値を１行１列目に移動させたため、その移動に必要な遅延は１と計算される。そこで、第１遅延機構用制御情報の０行１列目の要素に１をセットする。
また、「並び替え前データ配列」の０行１列目の要素を上記移動に従って、１行１列目に移動させる。この処理を１列目の要素全てに対し繰り返す。この処理が終了すると、配列は図（Ｂ）に示される状態になる。
【００５１】
次に、２列目の処理に移る。図１８の左下の図（Ｂ）のシャッフル用ポート配列０行２列目を見ると、０がセットされている。この値と、同配列０行０列目を比較すると、同じ番号が設定されている。そこで、同配列１行０列目を見ると、異なる要素が設定されている。しかし、１行１列目を見ると同じ要素が設定されているため、１行目には設定できないことが分かる。そこで、２行目の比較を行うと、同配列２行目０列目、及び２行目１列目には、０行２列目と異なる値が設定されていることが分かる。そこで、同配列０行２列目の要素を２行２列目に設定する。さらに、この移動に必要な遅延は２と計算されるため、第１遅延機構用制御情報の０行２列目に２と設定する。また、これに従って、「並び替え前データ配列」の０行２列目の要素を２行２列目に移動させる（図（Ｃ）参照）。同様にして、３列目の処理を行うと、図（Ｄ）に示す第１遅延後シャッフル用ポート配列と、図（Ｅ）に示す第１遅延機構用制御情報が得られる。
【００５２】
このように、各点線で囲まれた状態において、太い黒線で示された要素のそれぞれにおいて、網掛け部分で示される要素と比較し、同行で同じ要素が既に設定されていない行に移動させる処理を繰り返すことにより、遅延情報を生成することができる。
【００５３】
最後に、生成された第１遅延機構用制御情報（図（Ｅ））を見ると、負の値が設定されている箇所がある。これに対し、同配列内の最小の値を探索して、その値の符号を反転した値を全要素に加算することにより、負の値をなくす処理を行う。具体的には、図（Ｅ）に示された第１遅延機構用制御情報の配列を見ると、最小の値は−３である。そこで、符号を反転した３を全要素に足すと、図（Ｆ）に示すように、負の値をなくした第１遅延機構用制御情報を生成することができる。
【００５４】
このように、第１遅延機構用制御情報生成手順では、「シャッフル用ポート配列」と「並び替え前データ配列」とを基に、同じ時間サイクルの同じポートに複数の要素が重複して出力されないように、各要素が出力される時間サイクルを遅延させて調整する第１遅延機構用制御情報を生成し、さらに、「並び替え前データ配列」を第１遅延機構によって遅延させた後の「第１遅延後データ配列」と、シャッフル用ポート配列の様子を示す「第１遅延後シャッフル用ポート配列」と、を生成して出力する。
【００５５】
次に、シャッフル機構用制御情報の生成手順の具体的な例について、図１９を参照して説明する。図１９は、シャッフル機構用制御情報生成手順における、「第１遅延後データ配列」と「第１遅延後シャッフル用ポート配列」の変化の様子と、「シャッフル後データ配列」と「シャッフル機構用制御情報」の出力の様子を示したものである。
まず、本手順開始時点の様子を示す図１９の左上の図（Ａ）の状態においては、網掛けで示された「第１遅延後シャッフル用ポート配列」の０行目を探索し、シャッフル後の配列が０，１，２，３となるように並び替える処理を行う。例として、同配列０行目１列目には、３がセットされているため、それに従い、同配列、及び第１遅延後データ配列の０行１列目の要素を０行３列目に移動する。さらに、シャッフル機構用制御情報の０行１列目に３とセットする。この処理を繰り返していくことにより、最終的に「シャッフル後データ配列」と「シャッフル機構用制御情報」を得られる。
【００５６】
このように、シャッフル機構用制御情報の生成手順では、「第１遅延後データ配列」と「第１遅延後シャッフル用ポート配列」とを基に、「第１遅延後シャッフル用ポート配列」内に記録されたポート番号が、出力ポートに一致するように並び替えを行うと共に、「第１遅延後シャッフル用ポート配列」の各要素に対応する「第１遅延後データ配列」内の各要素についても並び替えを行い「シャッフル後データ配列」を作成し、さらに、「第１遅延後データ配列」内の各要素に対する並び替えの情報をシャッフル機構用制御情報として生成する。
【００５７】
次に、第２遅延機構用制御情報の生成手順の具体的な例について、図２０を参照して説明する。図２０は、第２遅延機構用制御情報生成手順による、シャッフル後データ配列の変化の様子と、第２遅延機構用制御情報の生成の様子を示したものである。
まず、本方法開始時点の様子を示す図１９の左上の図（Ａ）の状態においては、「シャッフル後データ配列」と「並び替え後データ配列」の網掛けで示された要素を比較し、両者が同一の並び順となるように並び替え、さらに、その並び替えに必要な遅延を図２０の右上の図（Ｆ）に示した第２遅延機構用制御情報に記述する。
【００５８】
例として、図２０の左上の図（Ａ）の状態では、両配列の並びは０行目〜３行目までで、Ａ，Ｂ，Ｃ，Ｄと一致している。このため、並び替えの必要がない。そのため、図（Ｆ）の第２遅延機構用制御情報の０列目の全ての要素に０を記述する。次に、図（Ａ）からの矢印で示される図（Ｂ）の状態では、両配列の１列目同士を比較する。ここで、例えば、０行目１列目同士を見ると、「シャッフル後データ配列」の要素はＨであるのに対し、「並び替え後データ配列」の要素はＥであるため、「シャッフル後配データ列」を並び替える必要がある。さらに見ると、「シャッフル後データ配列」の要素Ｈは、「並び替え後データ配列」では３行目１列目にあることが分かる。そのため、「シャッフル後データ配列」の０行目１列目の要素Hを３行目１列目に配置しなおすために必要な遅延は３と計算され、この情報を第２遅延機構用制御情報の０行目１列目要素に記述する。
【００５９】
このように処理を繰り返すと、最終的には図（Ｆ）の第２遅延機構用制御情報に示された配列が生成される。ここで、この配列内には負の値が存在するため、これらを全て正の値、もしくは０に調整する必要がある。そこで、配列内の最小値−３の符号を反転して、配列の全要素に加算する。これにより生成される配列が、図（Ｇ）に示す、負の値がなくなるように調整した第２遅延機構用制御情報と示される配列であり、これが第２遅延機構用制御情報生成の出力となる。
【００６０】
このように、第２遅延機構用制御情報生成手順では、「シャッフル後データ配列」と「並び替え後データ配列」とを比較し、「シャッフル後データ配列」を「並び替え後データ配列」と一致するよう遅延量の調整により並び替えを行うと共に、その並び替え方法の情報を第２遅延機構制御情報として生成する。
【００６１】
以上、本発明の実施の形態と実施例について説明したが、上述のデータ並び替え回路１００内のカウンタ１１０、制御情報テーブル１２０、制御情報結合機構１３０、第１遅延機構１４０、シャッフル機構１４０、第２遅延機構１６０、制御情報分離機構１７０、及び制御情報自動生成部１８０の各処理部は専用のハードウェアにより実現されるものであってもよく、また、各処理部の一部または全部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによりその機能を実現させるものであってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、コンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。
【００６２】
例えば、図２１に示すように、ユーザが作成した制御情報自動生成プログラム１９１は、ＰＣ（パーソナルコンピュータ）１９３内のメモリ（磁気ディスク等）や外部の記録媒体１９２に蓄えられ、この制御情報自動生成プログラム１９１をＰＣ１９２内のコンピュータが読み出して実行することによって、その結果、データ並び替え回路に対する制御情報１９４を得ることができる。
【００６３】
なお、ここで、本発明と上述の実施形態との対応関係について補足して説明しておく。本発明におけるデータ並び替え回路は、データ並び替え回路１００が対応し、本発明における遅延機構は、第１遅延機構１４０及び第２遅延機構１６０が対応し、本発明におけるシャッフル機構はシャッフル機構１５０が対応する。また、本発明における制御情報自動生成部は制御情報自動生成部１８０が対応する。また、本発明における「並び替え前データ配列」は「並び替え前データ配列ｄａｔａ＿ｂｅｆ」が対応し、本発明における「並び替え後データ配列」は、「並び替え後データ配列ｄａｔａ＿ａｆｔ」が対応する。また、本発明における第１遅延機構用制御情報は、「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」が対応し、本発明における第１遅延後データ配列は、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」が対応し、本発明における第１遅延後シャッフル用ポート配列は、「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」が対応し、本発明における第２遅延機構用制御情報は、「第２遅延機構用制御情報ｓｄｕ＿ａｒｒａｙ」が対応する。また、本発明におけるシャッフル機構用制御情報は、シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」が対応し、本発明におけるシャッフル後データ配列は、「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」が対応し、本発明におけるシャッフル用ポート配列は、「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」が対応する。
【００６４】
そして、上記実施形態における制御情報自動生成方法では、入力データの出力順序及びポート間の並びを並び替えて出力するデータ並び替え回路１００に対し、入力データの出力順序及び並び替え方を制御する制御情報を生成する制御情報自動生成方法であって、各要素に一意な値が割り当てられ、行を出力時間サイクル、列をポート番号とする「並び替え前データ配列ｄａｔａ＿ｂｅｆ」と、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」を、データ並び替え回路１００によって並び替えた後のデータの並び替え状態を示す「並び替え後データ配列ｄａｔａ＿ａｆｔ」と、を入力とし、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」と「並び替え後データ配列ｄａｔａ＿ａｆｔ」とを基に、制御情報を自動で生成する。
このような制御情報自動生成方法では、データ並び替え回路１００に対する制御情報を、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」と「並び替え後データ配列ｄａｔａ＿ａｆｔ」とを基に自動的に生成する。これにより、データ並び替え回路１００を制御する制御情報の設計、実装、デバッグに必要な時間を短縮することができる。
【００６５】
また、上記実施形態の制御情報自動生成方法では、データ並び替え回路１００は、遅延量を制御可能な第１遅延機構１４０及び第２遅延機構１６０と、シャッフル方法を制御可能なシャッフル機構１５０との組み合わせによって構成され、第１遅延機構１４０及び第２遅延機構１６０と、シャッフル機構１５０のそれぞれに対して制御情報を生成する。
このような制御情報自動生成方法では、遅延量を制御可能な第１遅延機構１４０及び第２遅延機構１６０と、シャッフル方法を制御可能なシャッフル機構１５０との組み合わせによって構成されるデータ並び替え回路１００に対し、第１遅延機構１４０及び第２遅延機構１６０における遅延量の制御情報と、シャッフル機構１５０における並び替え方法の制御情報を、それぞれ生成する。
これにより、遅延機構１４０及び１６０に対する制御情報と、シャッフル機構１５０に対する制御情報を、それぞれ生成することができる。このため、データ並び替え回路１００を制御する制御情報の設計、実装、デバッグに必要な時間を短縮することができる。
【００６６】
また、上記実施形態の制御情報自動生成方法では、データ並び替え回路１００は、入力データを遅延させる第１遅延機構１４０と、第１遅延機構１４０の出力データを入力データとし、該入力データをシャッフルするシャッフル機構１５０と、シャッフル機構１５０の出力データを入力データとし、該入力データを遅延させる第２遅延機構１６０と、を備え、制御情報自動生成部１８０により、制御情報の生成手順として、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」内の各要素の並び替え後の出力ポート番号を判定するシャッフルポートサーチ手順と、入力データを遅延量により調整し、出力する時間サイクルを調整する第１遅延機構用制御情報生成手順と、第１遅延機構１４０の出力データを並び替えるシャッフル機構用制御情報生成手順と、シャッフル機構１５０の出力データを遅延量により調整し、出力する時間サイクルを調整する第２遅延機構用制御情報生成手順と、が行われる。
このような制御情報自動生成方法では、入力データ（並び替え前データ配列）を、第１遅延機構１４０と、シャッフル機構１５０と、第２遅延機構１６０とを順次に通過させて並び替えを行う際に必要となる制御情報を生成するために、シャッフルポートサーチ手順により、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」内の各要素の並び替え後の出力ポート番号を判定する。次に、第１遅延機構用制御情報生成手順により、同じ時間サイクルの同じポートに複数の要素が重複して出力されないように、遅延量により各要素が出力される時間サイクルを調整し、これと同時に第１遅延機構用制御情報を生成する。続いて、シャッフル機構用制御情報生成手順により、第１遅延機構制御情報生成手順により時間サイクルが調整された「第１遅延機構後データ配列」内の各要素を、最終的に出力されるべきポート位置に合致するように並び替え、これと同時にシャッフル機構用制御情報を生成する。続いて、第２遅延機構用制御情報生成手順により、シャッフル機構用制御情報生成手順によりシャッフルされた「シャッフル後データ配列」内の各要素と「並び替え後データ配列」内の各要素とが一致するよう遅延量によって時間サイクルを調整し、これと同時に第２遅延機構用制御情報を生成する。
これにより、第１遅延機構１４０、シャッフル機構１５０、及び第２遅延機構１６０のそれぞれに対する制御情報を、順次に自動で生成することができる。
【００６７】
また、上記実施形態の制御情報自動生成方法では、シャッフルポートサーチ手順は、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」と「並び替え後データ配列ｄａｔａ＿ａｆｔ」とを基に、並び替え前データ配列の各要素がどのポートに出力されるかを判定し、該判定結果を示す「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」を作成する。
このような制御情報自動生成方法では、シャッフルポートサーチ手順により、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」と「並び替え後データ配列ｄａｔａ＿ａｆｔ」を走査し、「並び替え前データ配列」の各要素が、データ並び替え回路１００を通過後に、どのポートに出力されるかを分析し、それをＮ行Ｍ列の「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」に記録する。
これにより、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」内の各要素が、データ並び替え回路１００を通過後に、どのポートに出力されるかを分析し、シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」を生成することができる。
【００６８】
また、上記実施形態の制御情報自動生成方法では、第１遅延機構用制御情報生成手順は、「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」と「並び替え前データ配列ｄａｔａ＿ｂｅｆ」とを基に、同じ時間サイクルの同じポートに複数の要素が重複して出力されないように、遅延量により各要素が出力される時間サイクルを調整する「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」を生成し、さらに、「並び替え前データ配列ｄａｔａ＿ｂｅｆ」を第１遅延機構１４０によって遅延させた後の「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」と、「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」における並び替え後の様子を示す「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」と、を生成する。
このような制御情報自動生成方法では、第１遅延機構用制御情報生成手順において、「シャッフル用ポート配列ｓｈｕｆｆｌｅ＿ｐｏｒｔ」と「並び替え前データ配列ｄａｔａ＿ｂｅｆ」とを基に、同じ時間サイクルの同じポートに複数の要素（並び替え前データ配列内の各要素）が重複して出力されないように、遅延量により各要素が出力される時間サイクルを調整し、これと同時に「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」を生成する。
これにより、第２遅延機構１４０に対する「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」を生成することができる。そして、この「第１遅延機構用制御情報ｆｄ＿ａｒｒａｙ」により第１遅延機構１４０を制御することで、同じ時間サイクルの同じポートに複数の要素が重複して出力されないように制御することができる。
【００６９】
また、上記実施形態の制御情報自動生成方法では、シャッフル機構用制御情報生成手順は、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」と「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」とを基に、「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」内に記録されたポート番号が、出力ポートに一致するように並び替えを行うと共に、「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」の各要素に対応する「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」内の各要素についても並び替えを行い「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」を作成し、さらに、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」内の各要素に対する並び替え方法の情報を「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」として生成する。
このような制御情報自動生成方法では、「第１遅延後シャッフル用ポート配列ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ」内に記録されたポート番号が、出力ポートに一致するように並び替えを行うと共に、これに合わせて「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」内の各要素についても並び替えを行う。そして、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」内の各要素に対する並び替え方法の情報を「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」として生成する。
これにより、シャッフル機構１５０に対する「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」を生成することができる。そして、この「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」によりシャッフル機構１５０を制御するで、「第１遅延後データ配列ｆｄ＿ｄａｔａ＿ｂｅｆ」内の各要素が出力されるべきポート位置に合致するように、並び替えを行うことができる。
【００７０】
また、上記実施形態の制御情報自動生成方法では、第２遅延機構用制御情報生成手順は、「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」と「並び替え後データ配列ｄａｔａ＿ａｆｔ」とを比較し、「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」内の各要素を「並び替え後データ配列ｄａｔａ＿ａｆｔ」内の各要素と一致するよう遅延量を調整して並び替えを行うと共に、その並び替え方法の情報を「第２遅延機構用制御情報ｓｄｕ＿ａｒｒａｙ」として生成する。
このような制御情報自動生成方法では、第２遅延機構用制御情報生成手順は、「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」内の各要素が、「並び替え後データ配列ｄａｔａ＿ａｆｔ」内の各要素と一致するように、遅延量によって時間サイクルを調整して並び替えを行い、その並び替え方法の情報を「第２遅延機構用制御情報ｓｄｕ＿ａｒｒａｙ」として生成する。
これにより、第２遅延機構１６０に対する「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」を生成することができる。そして、この「シャッフル機構用制御情報ｓｈ＿ａｒｒａｙ」により第２遅延機構１６０を制御することで、「シャッフル後データ配列ｓｈ＿ｄａｔａ＿ｂｅｆ」内の各要素を、出力されるべき時間サイクルに合致するように、並び替えることができる。
【００７１】
以上、本発明の実施の形態について説明したが、本発明のデータ並び替え回路１００及び制御情報自動生成部１８０は、上述の図示例にのみ限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることは勿論である。
【符号の説明】
【００７２】
１００・・・データ並び替え回路、１１０・・・カウンタ、
１２０・・・制御情報テーブル、１３０・・・制御情報結合機構、
１３１・・・制御情報結合器、１４０・・・第１遅延機構、１４１・・・可変遅延回路、１５０・・・シャッフル機構、１５１・・・制御情報取り出し器、１５２・・・選択器、１６０・・・第２遅延機構、１７０・・・制御情報分離機構、
１７１・・・制御情報削除器、１８０・・・制御情報自動生成部、
ＩＤ＃０〜ＩＤ＃Ｍ−１・・・入力データ、
ＩＣ＃０〜ＩＣ＃Ｍ−１・・・入力制御信号（制御情報）、
ＯＤ＃０〜ＯＤ＃Ｍ−１・・・出力データ、
ｄａｔａ＿ａｆｔ・・・並び替え後データ配列、
ｄａｔａ＿ｂｅｆ・・・並び替え前データ配列、
ｆｄ＿ａｒｒａｙ・・・第１遅延機構用制御情報、
ｆｄ＿ｄａｔａ＿ｂｅｆ・・・第１遅延後データ配列、
ｆｄ＿ｓｈｕｆｆｌｅ＿ｐｏｒｔ・・・第１遅延後シャッフル用ポート配列、
ｓｄｕ＿ａｒｒａｙ・・・第２遅延機構用制御情報、
ｓｈ＿ａｒｒａｙ・・・シャッフル機構用制御情報、
ｓｈ＿ｄａｔａ＿ｂｅｆ・・・シャッフル後データ配列、
ｓｈｕｆｆｌｅ＿ｐｏｒｔ・・・シャッフル用ポート配列
【図１】
0005556323.tif 000002
【図２】
0005556323.tif 000003
【図３】
0005556323.tif 000004
【図４】
0005556323.tif 000005
【図５】
0005556323.tif 000006
【図６】
0005556323.tif 000007
【図７】
0005556323.tif 000008
【図８】
0005556323.tif 000009
【図９】
0005556323.tif 000010
【図１０】
0005556323.tif 000011
【図１１】
0005556323.tif 000012
【図１２】
0005556323.tif 000013
【図１３】
0005556323.tif 000014
【図１４】
0005556323.tif 000015
【図１５】
0005556323.tif 000016
【図１６】
0005556323.tif 000017
【図１７】
0005556323.tif 000018
【図１８】
0005556323.tif 000019
【図１９】
0005556323.tif 000020
【図２０】
0005556323.tif 000021
【図２１】
0005556323.tif 000022
【図２２】
0005556323.tif 000023
【図２３】
0005556323.tif 000024
【図２４】
0005556323.tif 000025