(57)【要約】【課題】メモリバンクに対するアクセス競合を回避する２次元配列型データの行の組み合わせを検索すること。【解決手段】検索装置１００は、２次元配列型データのうちの並列に書き込まれる行の組み合わせを、メモリ内の１つのメモリバンクに割り当ててはいけないという書き込み時競合回避条件１０３を記憶する。また、検索装置１００は、２次元配列型データのうちの並列に読み出される行の組み合わせを、メモリ内の１つのメモリバンクに割り当ててはいけないという読み出し時競合回避条件１０４を記憶する。次に、検索装置１００は、書き込み時競合回避条件１０３と読み出し時競合回避条件１０４との論理和をとり、読み書き時競合回避条件１０５を作成する。そして、検索装置１００は、読み書き時競合回避条件１０５に基づいて、２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索して、１つのメモリバンクに割り当てるパターンに決定する。【選択図】図１
2015130128.tif 000002
【特許請求の範囲】
【請求項１】
メモリへの書き込み時はそれぞれ異なる行位置にある要素がそれぞれ行に沿って正方向または逆方向に連続的に書き込まれ、前記メモリからの読み出し時は行が入れ替えられた状態でそれぞれ異なる行位置にある要素がそれぞれ列に沿って正方向または逆方向に連続的に読み出される２次元配列型データにおいて、並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、前記２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索する制御部、
を有することを特徴とする検索装置。
【請求項２】
前記制御部は、前記２次元配列型データの行数と前記メモリ内のメモリバンクの上限数とから特定される前記メモリ内の各メモリバンクに割り当て可能な行数の条件を満たす、前記並列に読み書きされない行の組み合わせを検索することを特徴とする請求項１に記載の検索装置。
【請求項３】
前記制御部は、前記メモリへの書き込み時に書き込みが開始される行位置と、書き込まれる要素がある行位置の遷移方向とに基づいて、前記並列に書き込まれる行の組み合わせを特定することを特徴とする請求項１または２に記載の検索装置。
【請求項４】
前記制御部は、前記メモリからの読み出し時に読み出しが開始される行位置と、読み出される要素がある行位置の遷移方向とに基づいて、前記並列に読み出される行の組み合わせを特定することを特徴とする請求項１〜３のいずれか一つに記載の検索装置。
【請求項５】
コンピュータが、
メモリへの書き込み時はそれぞれ異なる行位置にある要素がそれぞれ行に沿って正方向または逆方向に連続的に書き込まれ、前記メモリからの読み出し時は行が入れ替えられた状態でそれぞれ異なる行位置にある要素がそれぞれ列に沿って正方向または逆方向に連続的に読み出される２次元配列型データにおいて、並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、前記２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索する、
処理を実行することを特徴とする検索方法。
【請求項６】
コンピュータに、
メモリへの書き込み時はそれぞれ異なる行位置にある要素がそれぞれ行に沿って正方向または逆方向に連続的に書き込まれ、前記メモリからの読み出し時は行が入れ替えられた状態でそれぞれ異なる行位置にある要素がそれぞれ列に沿って正方向または逆方向に連続的に読み出される２次元配列型データにおいて、並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、前記２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索する、
処理を実行されることを特徴とする検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、検索方法、および検索プログラムに関する。
【背景技術】
【０００２】
従来、ＨＳＰＡ（Ｈｉｇｈ  Ｓｐｅｅｄ  Ｐａｃｋｅｔ  Ａｃｃｅｓｓ）対応の無線通信装置の誤り訂正部において、２次元配列型データのターボ復号処理を行う際には、バースト誤りをランダム誤りに変換するためにインターリーブが行われる。インターリーブでは、処理時間を低減するために、メモリをメモリバンクに分割しておき、メモリへの２次元配列型データの書き込み処理が並列に行われ、かつ、読み出し処理が並列に行われる。
【０００３】
関連する技術としては、例えば、複数の行内並び換えパターンに基づいて複数の読出しアドレスを生成し、それぞれ２次元配列データの１または複数の行の行番号と対応付けられたメモリバンクを有するメモリから複数のデータを同時に読み出すものがある。また、メモリアドレスを生成し、行番号に対応する行の入れ替えパターン値にマトリクスの列数を乗算してアドレスオフセット値を算出し、メモリアドレスに対応する列の入れ替えパターン値にアドレスオフセット値を加算するものがある。また、任意のクロックエッジごとに、データビットのサブセットからの少なくとも２つのビットをインターリーバメモリに並列にマップする技術がある。また、マトリクス状のメモリ空間を有する第１のメモリに対し、行方向または列方向の一方の方向に沿って第１の情報を書き込み、第１のメモリから行方向または列方向の他方の方向に沿って第１の情報を読み出す技術がある。（例えば、下記特許文献１〜４を参照。）
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】国際公開第２００６／０８２９２３号
【特許文献２】特開２００１−２６７９３４号公報
【特許文献３】特表２００９−５３６００７号公報
【特許文献４】特開２００８−１１８６２８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来技術では、メモリへの書き込み処理が並列に行われる時、または読み出し処理が並列に行われる時に、メモリ内のメモリバンクに対するアクセス競合が発生する場合がある。具体的には、２次元配列型データの複数の行が１つのメモリバンクに割り当てられていると、並列に行われる複数の書き込み処理または読み出し処理が当該１つのメモリバンクに同時にアクセスしてアクセス競合が発生することがある。
【０００６】
１つの側面では、本発明は、メモリバンクに対するアクセス競合を回避する２次元配列型データの行の組み合わせを検索する検索装置、検索方法、および検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一側面によれば、メモリへの書き込み時はそれぞれ異なる行位置にある要素がそれぞれ行に沿って正方向または逆方向に連続的に書き込まれ、前記メモリからの読み出し時は行が入れ替えられた状態でそれぞれ異なる行位置にある要素がそれぞれ列に沿って正方向または逆方向に連続的に読み出される２次元配列型データにおいて、並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、前記２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索する検索装置、検索方法、および検索プログラムが提案される。
【発明の効果】
【０００８】
本発明の一態様によれば、メモリバンクに対するアクセス競合を回避する２次元配列型データの行の組み合わせを検索することができるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】図１は、実施の形態にかかる検索装置による組み合わせ検索の一例を示す説明図である。
【図２】図２は、実施の形態にかかる検索装置のハードウェア構成例を示すブロック図である。
【図３】図３は、検索装置の機能的構成例を示すブロック図である。
【図４】図４は、インターリーブパターンの一例を示す説明図である。
【図５】図５は、書き込み時競合回避条件の一例を示す説明図である。
【図６】図６は、読み出し時競合回避条件の一例を示す説明図である。
【図７】図７は、読み書き時競合回避条件の一例を示す説明図である。
【図８】図８は、組み合わせ検索の内容を示す説明図（その１）である。
【図９】図９は、組み合わせ検索の内容を示す説明図（その２）である。
【図１０】図１０は、組み合わせ検索の内容を示す説明図（その３）である。
【図１１】図１１は、検索結果の一例を示す説明図である。
【図１２】図１２は、書き込み時の競合の有無を示す説明図である。
【図１３】図１３は、読み出し時の競合の有無を示す説明図である。
【図１４】図１４は、実装に使用される設計対象メモリのメモリ容量を示す説明図である。
【図１５】図１５は、実装結果の一例を示す説明図である。
【図１６】図１６は、決定処理手順の一例を示すフローチャートである。
【図１７】図１７は、検索処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１０】
以下に添付図面を参照して、本発明にかかる検索装置、検索方法、および検索プログラムの実施の形態を詳細に説明する。
【００１１】
（組み合わせ検索の一例）
図１は、実施の形態にかかる検索装置による組み合わせ検索の一例を示す説明図である。検索装置１００は、送信側の情報処理装置１０１がターボ符号化して受信側の情報処理装置１０２がターボ復号処理する２次元配列型データの各行を受信側の情報処理装置１０２のメモリ内のメモリバンクに割り当てるパターンを決定するコンピュータである。
【００１２】
情報処理装置１０１は、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）層からのデータをターボ符号化し、変調し、Ｄ（Ｄｉｇｉｔａｌ）／Ａ（Ａｎａｌｏｇ）変換し、ＲＦ（Ｒａｄｉｏ  Ｆｒｅｑｕｅｎｃｙ）信号に載せて、受信側の情報処理装置１０２に送信するコンピュータである。ここで、ＭＡＣ層は、通信プロトコルの一種である。情報処理装置１０２は、送信側の情報処理装置１０１から受信したデータを、ＲＦ信号から取り出し、Ａ／Ｄ変換し、復調し、ターボ復号してＭＡＣ層に入力するコンピュータである。情報処理装置１０１、１０２は、携帯電話や、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）などの携帯端末である。また、情報処理装置１０１、１０２は、ターボ符号、ターボ復号を行うパーソナル・コンピュータでもよい。
【００１３】
ここで、情報処理装置１０２がターボ復号処理する際に、２次元配列型データに対してインターリーブが行われる。ターボ符号におけるインターリーブは、バースト誤りをランダム誤りに変換するために、データを並べ替えることである。
【００１４】
インターリーブにおいて、２次元配列型データは、それぞれ異なる行位置からそれぞれ行に沿って正方向または逆方向に連続的に情報処理装置１０２のメモリに書き込まれる。行に沿って正方向に書き込むとは、該当の行の先頭から書き込むことを示す。同様に、行に沿って逆方向に書き込むとは、該当の行の末尾から書き込むことを示す。例えば、ターボ復号処理による無線性能を向上させるために、２次元配列型データのうちの並列して書き込みが行われるそれぞれの区画１１０〜１１４は、偶数番目の区画であれば正方向に書き込みが行われ、奇数番目の区画であれば逆方向に書き込みが行われる。
【００１５】
ここでは、説明の簡略化のため、２次元配列型データが１０行であり、５並列で書き込み処理および読み出し処理が行われる場合を例に挙げたが、これに限らない。例えば、２次元配列型データは、５行であってもよいし、２０行であってもよい。また、５並列で書き込み処理および読み出し処理が行われなくてもよく、４並列以下で書き込み処理および読み出し処理が行われてもよいし、６並列以上で書き込み処理および読み出し処理が行われてもよい。
【００１６】
また、インターリーブにおいて、２次元配列データは、行が入れ替えられた状態でそれぞれ異なる行位置の要素からそれぞれ列に沿って正方向または逆方向に連続的に情報処理装置１０２のメモリから読み出される。行が入れ替えられる順序は、ターボ復号処理内部の素数を利用して行を無作為に入れ替えるプライムインターリーブと呼ばれる処理によって規定された順序である。列に沿って正方向に読み出すとは、先頭の行の先頭の要素を読み出し、次に、２番目の行の先頭の要素を読み出す、…というように読み出すことを示す。同様に、列に沿って逆方向に読み出すとは、末尾の行の末尾の要素を読み出し、次に、末尾から２番目の行の末尾の要素を読み出す、…というように読み出すことを示す。
【００１７】
例えば、ターボ復号処理による無線性能を向上させるために、２次元配列型データのうちの並列して読み出しが行われるそれぞれの区画１２０〜１２４は、偶数番目の区画であれば正方向に読み出しが行われ、奇数番目の区画であれば逆方向に読み出しが行われる。また、アクセス競合を抑制するために、それぞれの区画１２０〜１２４を、複数の列分のデータと、１列分のデータを並列数で分割したオフセットデータとを含む区画にして、読み出しを開始する行位置をずらしている。
【００１８】
ここで、２次元配列型データの行を入れ替えるとは、２次元配列型データの各行が割り当てられたメモリバンクを示す論理アドレスに対するアクセス順序を入れ替えることである。また、２次元配列型データの行を入れ替えるとは、２次元配列型データの各行が割り当てられたメモリバンクを示す論理アドレスが入れ替えられた状態であってもよい。
【００１９】
このように、並列に書き込み処理が行われるため、２次元配列型データのうちの並列に書き込まれる行の組み合わせを１つのメモリバンクに割り当てるように情報処理装置１０２のメモリを設計すると、情報処理装置１０２においてアクセス競合が発生してしまう。また、並列に読み出し処理が行われるため、２次元配列型データのうちの並列に読み出される行の組み合わせを１つのメモリバンクに割り当てるように情報処理装置１０２のメモリを設計すると、情報処理装置１０２においてアクセス競合が発生してしまう。以下、情報処理装置１０２のメモリを、「設計対象メモリ」と呼称する。
【００２０】
一方で、アクセス競合の回避のために、設計対象メモリを細分化し、設計対象メモリ内のメモリバンクの数を増やして、同時にアクセスされる行を同一のメモリバンクに割り当てないようにする技術がある。しかしながら、この場合、設計対象メモリを細分化するほど、設計対象メモリのビット当たりの面積効率が悪化し、情報処理装置１０２の小型化が制限されることがある。
【００２１】
このため、例えば、アクセス競合を回避しつつ、設計対象メモリの小型化を図ることができるように、２０行の２次元配列型データの各行を１０個のメモリバンクのいずれかに割り当てて、５並列で書き込み処理および読み出し処理を行う場合がある。しかしながら、アクセス競合を回避しつつ１０個より少ないメモリバンクの数にしようとする場合に、どのように各行をメモリバンクに割り当てればよいか決めるのが難しい。
【００２２】
そこで、検索装置１００は、各行をメモリバンクに割り当てるパターンを決定する際に、２次元配列型データの中から並列に読み書きされない行の組み合わせを検索し、検索した行の組み合わせを１つのメモリバンクに割り当てるパターンに決定する。
【００２３】
以下、図１を用いて、アクセス競合が発生しないパターンを決定する例を説明する。図１では、上述したように、２次元配列型データが１０行であって、５並列で書き込み処理および読み出し処理が行われる場合を例に挙げる。以下、５並列で行われる書き込み処理を、「第１〜第５の書き込み処理」と呼称する。また、５並列で行われる読み出し処理を、「第１〜第５の読み出し処理」と呼称する。ここで、第１〜第５の読み出し処理は、それぞれ複数の列分のデータとオフセットデータとを読み出し先の区画とすることにより、それぞれ異なる行位置から読み出しを開始する。
【００２４】
図１の例では、検索装置１００は、書き込み時競合回避条件１０３と、読み出し時競合回避条件１０４とに基づいて、２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索して、１つのメモリバンクに割り当てるパターンに決定する。
【００２５】
ここで、書き込み時競合回避条件１０３とは、書き込み時のアクセス競合を回避するための条件である。書き込み時競合回避条件１０３は、例えば、２次元配列型データのうちの並列に書き込まれる行の組み合わせを、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件である。図１において、書き込み時競合回避条件１０３は、具体的には、行番号が「０，３，４，７，８」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。書き込み時競合回避条件１０３の詳細については、図５で後述する。
【００２６】
また、読み出し時競合回避条件１０４とは、読み出し時のアクセス競合を回避するための条件である。読み出し時競合回避条件１０４とは、例えば、２次元配列型データのうちの並列に読み出される行の組み合わせを、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件である。図１において、読み出し時競合回避条件１０４は、具体的には、行番号が「９，６，５，２，１」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。読み出し時競合回避条件１０４の詳細については、図６で後述する。
【００２７】
検索装置１００は、例えば、書き込み時競合回避条件１０３と読み出し時競合回避条件１０４とに基づいて読み書き時競合回避条件１０５を作成する。読み書き時競合回避条件１０５とは、書き込み時競合回避条件１０３と読み出し時競合回避条件１０４とに基づいて作成される条件である。読み書き時競合回避条件１０５とは、例えば、書き込み時競合回避条件１０３と、読み出し時競合回避条件１０４との論理和により求められる条件である。
【００２８】
また、読み書き時競合回避条件１０５とは、書き込み時および読み出し時のアクセス競合を回避するための条件である。読み書き時競合回避条件１０５とは、例えば、２次元配列型データのうちの並列に書き込みまたは読み出される複数の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件である。
【００２９】
検索装置１００は、具体的には、書き込み時競合回避条件１０３から行番号が「０」の行に関する、行番号が「０，３，４，７，８」の行を１つのメモリバンクに割り当ててはいけないという条件を抽出する。また、検索装置１００は、読み出し時競合回避条件１０４から行番号が「０」の行に関する、行番号が「０，３，４，７，８」の行、および行番号が「０，５，６，１，２」の行などを１つのメモリバンクに割り当ててはいけないという条件を抽出する。
【００３０】
次に、検索装置１００は、抽出した条件から、行番号が「０」の行と共に同一のメモリバンクに割り当ててはいけない、行番号が「１，２，３，４，５，６，７，８」の行を特定する。そして、検索装置１００は、行番号が「０」の行と共に、行番号が「１，２，３，４，５，６，７，８」の行を同一のメモリバンクに割り当ててはいけないという条件を、読み書き時競合回避条件１０５に含まれる条件として作成する。読み書き時競合回避条件１０５の詳細については、図７で示す。
【００３１】
次に、検索装置１００は、読み書き時競合回避条件１０５に基づいて、２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索して、１つのメモリバンクに割り当てるパターンに決定する。具体的な検索例については、図８〜図１０で後述する。そして、検索装置１００は、決定した各パターンを含む、２次元配列型データの各行をメモリバンクに割り当てるパターンを決定する。以下、２次元配列型データの各行をメモリバンクに割り当てるパターンを、「割り当てパターン」と呼称する。
【００３２】
検索装置１００は、例えば、メモリバンクｂ０に割り当てる行として行番号が「０」の行を選択する。次に、検索装置１００は、読み書き時競合回避条件１０５から、選択した行番号が「０」の行と共に、行番号が「１，２，３，４，５，６，７，８」の行を同一のメモリバンクに割り当ててはいけないという条件を抽出する。そして、検索装置１００は、抽出した条件から、選択した行番号が「０」の行と共に、同一のメモリバンクに割り当ててもよい、行番号が「９」の行を特定する。次に、検索装置１００は、行番号が「０，９」の行の組み合わせを、メモリバンクｂ０に割り当てるパターンに決定する。同様に、検索装置１００は、行番号が「１，８」、「２，７」、「３，６」、「４，５」の行の組み合わせを、それぞれ、メモリバンクｂ１、ｂ２、ｂ３、ｂ４に割り当てるパターンに決定する。そして、検索装置１００は、決定した各パターンを含む割り当てパターン１０６を決定する。
【００３３】
これにより、検索装置１００は、検索装置１００の利用者に２次元配列型データの各行をメモリバンクに割り当てるパターンを通知することができる。検索装置１００の利用者は、２次元配列型データの各行をメモリバンクに割り当てるパターンに基づいて、情報処理装置１０２におけるターボ復号処理に使用される設計対象メモリを情報処理装置１０２に実装することができる。検索装置１００が検索したメモリバンクの割り当てパターンを実装した情報処理装置１０２は、ターボ復号処理におけるアクセス競合の発生を回避することができる。
【００３４】
また、検索装置１００は、設計対象メモリ内のメモリバンクの数が上限を超えないように、２次元配列型データの各行を設計対象メモリ内のメモリバンクに割り当てるパターンを検索してもよい。これにより、検索装置１００の利用者は、検索したパターンに基づいて情報処理装置１０２の設計対象メモリを設計することにより、情報処理装置１０２に実装する設計対象メモリ内のメモリバンクの数の増大を抑制することができる。メモリバンクの数の増大を抑制することにより、情報処理装置１０２の設計対象メモリのサイズの増大が抑制され、情報処理装置１０２の設計対象メモリに接続される配線領域のサイズの増大が抑制され、情報処理装置１０２のサイズの増大が抑制される。
【００３５】
（検索装置１００のハードウェア構成例）
図２は、実施の形態にかかる検索装置のハードウェア構成例を示すブロック図である。図２において、検索装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２０１と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）２０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２０３と、を有する。さらに、検索装置１００は、磁気ディスクドライブ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）２０４と、磁気ディスク２０５と、光ディスクドライブ２０６と、光ディスク２０７と、ディスプレイ２０８と、インターフェース（Ｉ／Ｆ：Ｉｎｔｅｒｆａｃｅ）２０９と、キーボード２１０と、マウス２１１と、を有する。また、各構成部はバス２００によってそれぞれ接続されている。
【００３６】
ここで、ＣＰＵ２０１は、検索装置１００の全体の制御を司る演算処理装置である。ＲＯＭ２０２は、ブートプログラム、および本実施の形態にかかる検索プログラムなどのプログラムを記憶する不揮発性メモリである。ＲＡＭ２０３は、ＣＰＵ２０１のワークエリアとして使用される揮発性メモリである。磁気ディスクドライブ２０４は、ＣＰＵ２０１の制御にしたがって磁気ディスク２０５に対するデータのリード／ライトを制御する制御装置である。磁気ディスク２０５は、磁気ディスクドライブ２０４の制御で書き込まれたデータを記憶する記憶媒体である。
【００３７】
光ディスクドライブ２０６は、ＣＰＵ２０１の制御にしたがって光ディスク２０７に対するデータのリード／ライトを制御する制御装置である。光ディスク２０７は、光ディスクドライブ２０６の制御で書き込まれたデータを記憶したり、光ディスク２０７に記憶されたデータをコンピュータに読み取らせたりする記憶媒体である。
【００３８】
ディスプレイ２０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する装置である。ディスプレイ２０８は、例えば、液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００３９】
Ｉ／Ｆ２０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク２１４に接続され、このネットワーク２１４を介して他の装置に接続する装置である。そして、Ｉ／Ｆ２０９は、ネットワーク２１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ２０９には、例えば、モデムやＬＡＮアダプタなどを採用することができる。
【００４０】
キーボード２１０は、文字、数字、各種指示などの入力のためのキーを有し、データの入力を行う装置である。また、キーボード２１０は、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス２１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う装置である。また、検索装置１００は、マウス２１１の代わりに、ポインティングデバイスとして同様に機能を有するものであれば、トラックボールやジョイスティックなどを有してもよい。
【００４１】
（情報処理装置１０１および情報処理装置１０２のハードウェア構成例）
次に、情報処理装置１０１および情報処理装置１０２のハードウェア構成例について説明する。
【００４２】
情報処理装置１０１および情報処理装置１０２は、例えば、図２に示したハードウェアを有する。また、情報処理装置１０１および情報処理装置１０２は、ターボ符号化、またはターボ復号を行うためのハードウェアを有する。また、情報処理装置１０１および情報処理装置１０２は、磁気ディスクドライブ２０４、磁気ディスク２０５、光ディスクドライブ２０６、光ディスク２０７の代わりに、ソリッドステートドライブと、半導体素子によって形成された半導体メモリとを有する。
【００４３】
（検索装置１００の機能的構成例）
次に、図３を用いて、検索装置１００の機能的構成例について説明する。図３は、検索装置の機能的構成例を示すブロック図である。検索装置１００は、制御部３００を含む。制御部３００は、特定部３０１と、検索部３０２と、出力部３０３と、を含む。制御部３００は、例えば、図２に示したＲＯＭ２０２、ＲＡＭ２０３、磁気ディスク２０５、光ディスク２０７などの記憶装置に記憶されたプログラムをＣＰＵ２０１に実行させることにより、制御部３００の機能を実現する。
【００４４】
特定部３０１は、メモリへの書き込み時に書き込みが開始される行位置と、書き込まれる要素がある行位置の遷移方向とに基づいて、２次元配列型データにおいて並列に書き込まれる行の組み合わせを特定する。ここで、メモリとは、２次元配列型データの各行が割り当てられるメモリバンクを有する記憶媒体であって、例えば、上述した設計対象メモリである。メモリは、複数のメモリの集合であってもよい。遷移方向とは、先頭行から最終行への方向、または最終行から先頭行への方向である。
【００４５】
２次元配列型データとは、情報処理装置１０２が送受信するデータである。２次元配列型データのそれぞれの行は、設計対象メモリ内のメモリバンクに割り当てられる。また、２次元配列型データとは、情報処理装置１０２による設計対象メモリへの書き込み時はそれぞれ異なる行位置にある要素がそれぞれ行に沿って正方向または逆方向に連続的に書き込まれるデータである。行に沿って正方向とは、行の先頭から末尾への方向である。
【００４６】
また、２次元配列型データとは、情報処理装置１０２による設計対象メモリからの読み出し時は行が入れ替えられた状態でそれぞれ異なる行位置にある要素がそれぞれ列に沿って正方向または逆方向に連続的に読み出されるデータである。行が入れ替えられた状態とは、２次元配列型データの各行が割り当てられたメモリバンクを示す論理アドレスに対するアクセス順序を入れ替えた状態である。また、行が入れ替えられた状態とは、２次元配列型データの各行が割り当てられたメモリバンクを示す論理アドレスを入れ替えた状態であってもよい。列に沿って正方向とは、列の先頭から末尾への方向である。
【００４７】
特定部３０１は、図１の例では、書き込み時競合回避条件１０３となる、行番号が「０，３，４，７，８」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を特定する。これにより、特定部３０１は、書き込み時競合回避条件１０３を特定することができる。
【００４８】
また、特定部３０１は、設計対象メモリからの読み出し時に読み出しが開始される行位置と、読み出される要素がある行位置の遷移方向とに基づいて、２次元配列型データにおいて並列に読み出される行の組み合わせを特定する。特定部３０１は、図１の例では、読み出し時競合回避条件１０４となる、行番号が「９，６，５，２，１」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を特定する。これにより、特定部３０１は、読み出し時競合回避条件１０４を特定することができる。特定結果は、例えば、ＲＡＭ２０３、磁気ディスク２０５、光ディスク２０７などの記憶領域に記憶される。
【００４９】
検索部３０２は、２次元配列型データにおいて並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索する。検索部３０２は、例えば、並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、設計対象メモリ内の各メモリバンクに割り当て可能な行数の条件を満たす、並列に読み書きされない行の組み合わせを検索する。
【００５０】
ここで、割り当て可能な行数の条件とは、２次元配列型データの行数と設計対象メモリ内のメモリバンクの上限数とから特定される条件である。以下、割り当て可能な行数の条件を、「割り当て条件」と呼称する。２次元配列型データの行数が２０であって、設計対象メモリ内のメモリバンクの上限数が１０である場合を例に挙げる。この場合、割り当て条件は、例えば、各メモリバンクに２行以上割り当てるという条件である。また、割り当て条件は、例えば、各メモリバンクに２行以上割り当て、かつ、いずれかのメモリバンクには３行以上割り当てるという条件であってもよい。
【００５１】
検索部３０２は、具体的には、書き込み時競合回避条件１０３から、行番号が「０」の行に関連する、行番号が「０，３，４，７，８」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を抽出する。また、検索部３０２は、読み出し時競合回避条件１０４から、行番号が「０」の行に関連する、「８，７，４，３，０」の行を、１つのメモリバンクに割り当ててはいけないという条件を抽出する。また、検索部３０２は、読み出し時競合回避条件１０４から、行番号が「０」の行に関連する、「５，０，１，６，７」の行を、１つのメモリバンクに割り当ててはいけないという条件を抽出する。
【００５２】
また、検索部３０２は、読み出し時競合回避条件１０４から、行番号が「０」の行に関連する、「４，１，０，７，６」の行を、１つのメモリバンクに割り当ててはいけないという条件を抽出する。また、検索部３０２は、読み出し時競合回避条件１０４から、行番号が「０」の行に関連する、「１，４，７，０，３」の行を、１つのメモリバンクに割り当ててはいけないという条件を抽出する。また、検索部３０２は、読み出し時競合回避条件１０４から、行番号が「０」の行に関連する、「０，５，６，１，２」の行を、１つのメモリバンクに割り当ててはいけないという条件を抽出する。
【００５３】
次に、検索部３０２は、抽出した条件に基づいて、読み書き時競合回避条件１０５として、行番号が「０」の行と、行番号が「１，２，３，４，５，６，７，８」の行とを、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を作成する。そして、検索装置１００は、読み書き時競合回避条件１０５に基づいて、行番号が「０，９」の行の組み合わせを、メモリバンクｂ０に割り当てるパターンに決定する。また、検索部３０２は、検索結果に基づいて、２次元配列型データの各行を設計対象メモリ内のメモリバンクに割り当てるために使用されるメモリ容量を算出してもよい。これにより、検索部３０２は、１つのメモリバンクに配置可能な、２次元配列型データのうちの行の組み合わせを検索することができる。
【００５４】
出力部３０３は、検索結果を出力する。また、出力部３０３は、検索結果と合わせて、検索部３０２によって算出されたメモリ容量を出力してもよい。出力形式としては、例えば、ディスプレイ２０８への表示、Ｉ／Ｆ２０９による外部装置への送信がある。また、出力部３０３は、メモリ容量を、ＲＡＭ２０３、磁気ディスク２０５、光ディスク２０７などの記憶領域に記憶することとしてもよい。これにより、検索装置１００の利用者は、出力部３０３から出力された検索結果に基づいて、ターボ復号処理においてアクセス競合が発生しないように、情報処理装置１０２に設計対象メモリを実装することができる。
【００５５】
（インターリーブパターン４００の一例）
次に、図４を用いて、インターリーブパターン４００の一例について説明する。
【００５６】
図４は、インターリーブパターンの一例を示す説明図である。インターリーブパターン４００は、２次元配列型データの書き込み順序、行の入れ替え順序、および読み出し順序を規定した情報である。図４において、２次元配列型データは、２０行のデータである。２次元配列型データの各行は、「０〜１９」の行番号が付与されている。
【００５７】
まず、２次元配列型データは、第１〜第５の並列書き込み処理について、各々の矢印４１１〜４１５が示す行方向に、並列に設計対象メモリ内のメモリバンクに書き込まれる。例えば、第１の並列書き込み処理について、０行目の先頭から行に沿って正方向に、０行目〜３行目までの各行が書き込まれる。すなわち、第１の並列書き込み処理について、書き込まれる行の行番号が「０→１→２→３」の順序になるように、０行目〜３行目までの各行が書き込まれる。
【００５８】
また、例えば、第２の並列書き込み処理について、７行目の末尾から行に沿って逆方向に、４行目〜７行目までの各行が書き込まれる。すなわち、第２の並列書き込み処理について、書き込まれる行の行番号が「７→６→５→４」の順序になるように、４行目〜７行目までの各行が書き込まれる。
【００５９】
同様に、第３の並列書き込み処理について、書き込まれる行の行番号が「８→９→１０→１１」の順序になるように、各行が書き込まれる。また、第４の並列書き込み処理について、書き込まれる行の行番号が「１５→１４→１３→１２」の順序になるように、各行が書き込まれる。また、第５の並列書き込み処理について、書き込まれる行の行番号が「１６→１７→１８→１９」の順序になるように、各行が書き込まれる。
【００６０】
次に、２次元配列型データはプライムインターリーブで規定された順序に従って、各行を入れ替えられる。２次元配列型データは、例えば、先頭から行番号が「０→１→２→３→…→１９」と並ぶ順序から、行番号が「１９→９→１４→４→０→２→５→７→１２→１８→１０→８→１３→１７→３→１→１６→６→１５→１１」と並ぶ順序に入れ替えられる。以下の説明では、行番号が「１９→９→１４→４→０→２→５→７→１２→１８→１０→８→１３→１７→３→１→１６→６→１５→１１」と並ぶ順序に入れ替えるパターンを「第１の入れ替えパターン」と表記する場合がある。
【００６１】
また、２次元配列型データは、例えば、先頭から行番号が「０→１→２→３→…→１９」と並ぶ順序から、行番号が「１９→９→１４→４→０→２→５→７→１２→１８→１６→１３→１７→１５→３→１→６→１１→８→１０」と並ぶ順序に入れ替えられてもよい。以下の説明では、行番号が「１９→９→１４→４→０→２→５→７→１２→１８→１６→１３→１７→１５→３→１→６→１１→８→１０」と並ぶ順序に入れ替えるパターンを「第２の入れ替えパターン」と表記する場合がある。図４の例では、第１の入れ替えパターンに従って、行の入れ替えを行う様子を示す。
【００６２】
そして、２次元配列型データは、行を入れ替えられた後に、各々の矢印４２１〜４２５が示す列方向に沿って、並列に読み出される。例えば、第１の並列読み出し処理について、０行目から列に沿って正方向に、０行目〜１９行目までの各行にある要素が読み出される。すなわち、第１の並列読み出し処理について、読み出される行の行番号が「１９→９→１４→４→０→２→５→７→１２→１８→１０→８→１３→１７→３→１→１６→６→１５→１１」の順序になるように、各行にある要素が読み出される。
【００６３】
また、例えば、第２の並列読み出し処理について、７行目から列に沿って逆方向に、０行目から１９行目までの各行にある要素が読み出される。すなわち、第２の並列読み出し処理について、読み出される行の行番号が「７→５→２→０→４→１４→９→１９→１１→１５→６→１６→１→３→１７→１３→８→１０→１８→１２」の順序になるように各行にある要素が読み出される。
【００６４】
同様に、第３の並列読み出し処理について、読み出される行の行番号が「１２→１８→１０→８→１３→１７→３→１→１６→６→１５→１１→１９→９→１４→４→０→２→５→７」の順序になるように、各行にある要素が読み出される。また、第４の並列読み出し処理について、読み出される行の行番号が「１→３→１７→１３→８→１０→１８→１２→７→５→２→０→４→１４→９→１９→１１→１５→６→１６」の順序になるように、各行にある要素が読み出される。また、第５の並列読み出し処理について、読み出される行の行番号が「１６→６→１５→１１→１９→９→１４→４→０→２→５→７→１２→１８→１０→８→１３→１７→３→１」の順序になるように、各行にある要素が読み出される。
【００６５】
ここで、２次元配列型データの各行をメモリバンクに割り当てるパターンによっては書き込み時または読み出し時においてアクセス競合が発生してしまうことがある。例えば、１６〜１９番の行を１つのメモリバンクに割り当てたとする。この場合、行を入れ替えた後の０行目にある行番号が「１９」の行を読み出す第１の並列読み出し処理と、１６行目にある行番号が「１６」の行を読み出す第５の並列読み出し処理とが同一のメモリバンクに対して同時に読み出すことになりアクセス競合が発生する。そこで、検索装置１００は、読み出し時にも書き込み時にもアクセス競合が発生しない、２次元配列型データの各行を設計対象メモリ内のメモリバンクに割り当てるパターンを決定することになる。
【００６６】
次に、図５を用いて、図４に示したインターリーブパターン４００に対応する、書き込み時競合回避条件５００の一例について説明する。
【００６７】
図５は、書き込み時競合回避条件の一例を示す説明図である。書き込み時競合回避条件５００は、図４の順序で書き込んだ場合に並列に書き込まれる行の組み合わせを設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。書き込み時競合回避条件５００は、レコード５０１−０〜３を含む。
【００６８】
書き込み時競合回避条件５００は、時刻と、行番号と、いう２つのフィールドを有する。書き込み時競合回避条件５００の時刻フィールドには、複数の書き込み処理が同期して行位置にある各要素の書き込みを開始する時刻が格納される。書き込み時競合回避条件５００の行番号フィールドには、時刻フィールドの時刻において書き込み処理が書き込みを開始する行の行番号が格納される。すなわち、時刻フィールドの列のそれぞれは、第１〜第５の並列書き込み処理のそれぞれによって書き込まれる行の行番号を示す。
【００６９】
例えば、図４の順序で書き込んだ場合、時刻「ｔｗ０」において、行番号が「０，７，８，１５，１６」の行が、第１〜第５の並列書き込み処理により、並列に書き込まれる。このため、書き込み時競合回避条件５００は、レコード５０１−０が示すように、行番号が「０，７，８，１５，１６」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。
【００７０】
また、図４の順序で書き込んだ場合、時刻「ｔｗ１」において、行番号が「１，６，９，１４，１７」の行が、第１〜第５の並列書き込み処理により、並列に書き込まれる。このため、書き込み時競合回避条件５００は、レコード５０１−１が示すように、行番号が「１，６，９，１４，１７」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。
【００７１】
同様に、書き込み時競合回避条件５００は、レコード５０１−２が示すように、時刻「ｔｗ２」において、行番号が「２，５，１０，１３，１８」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。また、書き込み時競合回避条件５００は、レコード５０１−３が示すように、時刻「ｔｗ３」において、行番号が「３，４，１１，１２，１９」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。
【００７２】
次に、図６を用いて、図４に示したインターリーブパターン４００に対応する、読み出し時競合回避条件６００の一例について説明する。
【００７３】
図６は、読み出し時競合回避条件の一例を示す説明図である。読み出し時競合回避条件６００は、図４の順序で書き込んだ場合に並列に読み出される行の組み合わせを設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。読み出し時競合回避条件６００は、レコード６０１−０〜１９を含む。
【００７４】
読み出し時競合回避条件６００は、時刻、行番号という２つのフィールドを有する。読み出し時競合回避条件６００の時刻フィールドには、複数の読み出し処理が同期して行位置にある要素の読み出しを行う時刻が格納される。読み出し時競合回避条件６００の行番号フィールドには、時刻フィールドの時刻において読み出し処理が要素を読み出す行の行番号が格納される。すなわち、時刻フィールドの列のそれぞれは、第１〜第５の並列読み出し処理のそれぞれによって読み出される行の行番号を示す。
【００７５】
例えば、図４の順序で書き込んだ場合、時刻「ｔｒ０」において、行番号が「１９，７，１２，１，１６」の行にある要素が、第１〜第５の並列読み出し処理により、並列に読み出される。このため、読み出し時競合回避条件６００は、レコード６０１−０が示すように、行番号が「１９，７，１２，１，１６」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。
【００７６】
また、図４の順序で書き込んだ場合、時刻「ｔｒ１」において、行番号が「９，５，１８，３，６」の行にある要素が、第１〜第５の並列読み出し処理により、並列に読み出される。このため、読み出し時競合回避条件６００は、レコード６０１−１が示すように、行番号が「９，５，１８，３，６」の行を、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。
【００７７】
同様に、読み出し時競合回避条件６００は、レコード６０１−３〜１９が示すように、時刻「ｔｒ３」〜「ｔｒ１９」のそれぞれに対応する行の組み合わせを、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を含む。
【００７８】
次に、図７を用いて、図５に示した書き込み時競合回避条件５００と図６に示した読み出し時競合回避条件６００とに基づいて算出される読み書き時競合回避条件７００の一例について説明する。
【００７９】
図７は、読み書き時競合回避条件の一例を示す説明図である。読み書き時競合回避条件７００は、書き込み時競合回避条件５００と読み出し時競合回避条件６００との論理和をとることにより算出される条件を含む。論理和をとることにより算出される条件は、２次元配列型データの各行と、当該行と並列に読み書きされる行とを、１つのメモリバンクに割り当ててはいけないという条件である。読み書き時競合回避条件７００は、レコード７０１−０〜１９を含む。
【００８０】
読み書き時競合回避条件７００の行番号フィールドには、２次元配列型データの行の行番号が設定される。読み書き時競合回避条件７００の共にメモリバンクに割り当てる行の行番号フィールドには、読み書き時競合回避条件７００の行番号フィールドの行と組み合わせて、共に同一のメモリバンクに割り当てる候補になる、２次元配列型データの行の行番号が設定される。
【００８１】
図７は、具体的には、読み書き時競合回避条件７００を表にした図を示す。図７の例では、読み書き時競合回避条件７００の各行は、それぞれ、２次元配列型データの各行と、当該行と並列に読み書きされる行とを、１つのメモリバンクに割り当ててはいけないという条件を示す。
【００８２】
表の要素は、表のレコードに対応する２次元配列型データの行と、表のフィールドに対応する２次元配列型データの行とを、１つのメモリバンクに割り当ててよいか否かを示す。表の要素が０である場合は、割り当ててよいことを示す。表の要素が１である場合は、割り当ててはいけないことを示す。
【００８３】
例えば、レコード７０１−０は、書き込み時競合回避条件５００の行番号が「０」の行を含むレコード５０１−０と、読み出し時競合回避条件６００の行番号が「０」の行を含むレコード６０１−３，４，８，１１，１６とを合成して作成される。より具体的には、検索装置１００は、まず、レコード７０１−０の「０」〜「１９」フィールドの要素を０に設定する。次に、検索装置１００は、レコード５０１−０を参照して、行番号が「０」と同一のメモリバンクに割り当ててはいけない、「７、８、１５、１６」に対応する、レコード７０１−０の「７」、「８」、「１５」、「１６」フィールドの要素を１に設定する。続けて、検索装置１００は、レコード６０１−３を参照して、行番号が「０」と同一のメモリバンクに割り当ててはいけない、「４、８、１３、１１」に対応する、レコード７０１−０の「４」、「８」、「１３」、「１１」フィールドの要素を１に設定する。次に、検索装置１００は、レコード４，８，１１，１６についても同様の処理を行って、レコード７０１−０を作成する。
【００８４】
例えば、レコード７０１−０は、行番号が「０」の行と、行番号が「０，４，７，８，１１，１２，１３，１５，１６，１９」の行とを、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を示す。また、例えば、レコード７０１−１は、行番号が「１」の行と、行番号が「１，４，６，７，８，９，１１，１２，１３，１４，１６，１７，１９」の行とを、設計対象メモリ内の１つのメモリバンクに割り当ててはいけないという条件を示す。
【００８５】
次に、図８〜図１０を用いて、図７に示した読み書き時競合回避条件７００に基づいた組み合わせ検索の内容について説明する。
【００８６】
図８は、組み合わせ検索の内容を示す説明図（その１）である。また、図９は、組み合わせ検索の内容を示す説明図（その２）である。また、図１０は、組み合わせ検索の内容を示す説明図（その３）である。ここで、検索装置１００は、設計対象メモリ内のいずれかのメモリバンクには３行以上割り当て、かつ、設計対象メモリ内の各メモリバンクには２行以上割り当てるという割り当て条件を満たすように、行の組み合わせを検索する。そして、検索装置１００は、設計対象メモリ内のメモリバンクに割り当てるパターンを決定する。
【００８７】
図８の（１）の処理において、検索装置１００は、設計対象メモリ内のメモリバンクに割り当てるパターンを決定するために、いずれかの行番号のレコードを選択する。選択する行番号はどれでもよい。図８の例では、検索装置１００は、行番号が「１９」である、レコード７０１−１９を選択する。次に、図８の（２）の処理において、検索装置１００は、レコードに対応する、読み書き時競合回避条件７００の「１９」フィールドを選択する。
【００８８】
続けて、図８の（３）の処理において、検索装置１００は、選択したレコード７０１−１９の各フィールドの要素のうち、要素が０となるフィールドを検索する。検索する順序はどのような順でもよい。図８の例では、検索装置１００は、選択したレコード７０１−１９の「１８」フィールドから順に、最初に要素が０になるフィールドを検索する。ここで、検索装置１００は、レコード７０１−１９において要素が０になる読み書き時競合回避条件７００の「１８」フィールドを検出する。そして、検索装置１００は、検出した読み書き時競合回避条件７００の「１８」フィールドを選択する。このとき、検索装置１００は、読み書き時競合回避条件７００の「１８」および「１９」フィールドに対応する行番号が「１８，１９」の行の組み合わせを、１つのメモリバンクに割り当ててもよい行の組み合わせとして設定する。
【００８９】
図８の（４）の処理において、検索装置１００は、読み書き時競合回避条件７００の「１８」および「１９」フィールドにおいて、共に要素が０になるレコードがあるか否かを判定する。検索装置１００は、具体的には、選択した読み書き時競合回避条件７００の「１８」および「１９」フィールドについて、ビット単位で論理和をとり、論理和が０になる要素が含まれるか否かに基づいて、共に要素が０になるレコードがあるか否かを判定する。検索装置１００は、共に要素が０になるレコードがある場合、当該レコードの行番号フィールドの行番号の行を、行番号が「１８，１９」の行の組み合わせと共に、１つのメモリバンクに割り当ててもよい行として特定する。一方で、検索装置１００は、共に要素が０になるレコードがない場合、行番号が「１８，１９」の行の組み合わせと共に１つのメモリバンクに割り当ててもよい行が存在しないと判断する。ここで、検索装置１００は、共に要素が０になるレコードがないため、読み書き時競合回避条件７００の「１８」および「１９」フィールドに対応する行番号が「１９，１８」の行が、１つのメモリバンクに割り当ててもよい行の組み合わせであると特定する。
【００９０】
図８の（５）の処理において、検索装置１００は、設計対象メモリ内のいずれかのメモリバンクには３行以上割り当てるという割り当て条件を満たすか否かを判定する。ここで、検索装置１００は、読み書き時競合回避条件７００の「１８」および「１９」フィールドに対応する行番号が「１９，１８」の行の組み合わせが、設計対象メモリ内のいずれかのメモリバンクには３行以上割り当てる割り当て条件を満たさない。したがって、検索装置１００は、行番号が「１９，１８」の行の組み合わせを、メモリバンクに割り当てるパターンとして決定しない。
【００９１】
図９の（６）の処理において、検索装置１００は、メモリバンクに割り当てるパターンとして決定しなかったため、直前に選択した読み書き時競合回避条件７００の「１８」フィールドを選択解除する。次に、検索装置１００は、選択したレコード７０１−１９の右側から、「１８」フィールドを除いて、最初に要素が０になるフィールドを検索する。ここで、検索装置１００は、レコード７０１−１９において要素が０になる読み書き時競合回避条件７００の「１７」フィールドを検出する。そして、検索装置１００は、検出した読み書き時競合回避条件７００の「１７」フィールドを選択する。このとき、検索装置１００は、読み書き時競合回避条件７００の「１７」および「１９」フィールドに対応する行番号が「１７，１９」の行の組み合わせを、１つのメモリバンクに割り当ててもよい行の組み合わせとして設定する。
【００９２】
図９の（７）の処理において、検索装置１００は、読み書き時競合回避条件７００の「１９」および「１７」フィールドにおいて、共に要素が０になるレコードがあるか否かを判定する。次に、図９の（８）の処理において、検索装置１００は、共に要素が０になるレコード７０１−５があるため、さらに、読み書き時競合回避条件７００のレコード７０１−５に対応する読み書き時競合回避条件７００の「５」フィールドを選択する。このとき、検索装置１００は、読み書き時競合回避条件７００の「１９」、「１７」、「５」フィールドに対応する行番号が「５，１７，１９」の行の組み合わせを、１つのメモリバンクに割り当ててもよい行の組み合わせとして設定し直す。
【００９３】
図９の（９）の処理において、検索装置１００は、読み書き時競合回避条件７００の「１９」、「１７」および「５」フィールドにおいて、共に要素が０になるレコードがあるか否かを判定する。ここで、検索装置１００は、共に要素が０になるレコードがないため、読み書き時競合回避条件７００の「１９」、「１７」、「５」フィールドに対応する行番号が「１９，１７，５」の行が１つのメモリバンクに割り当ててもよい行の組み合わせであると特定する。
【００９４】
図９の（１０）の処理において、検索装置１００は、設計対象メモリ内のいずれかのメモリバンクには３行以上割り当てるという割り当て条件を満たすか否かを判定する。ここで、検索装置１００は、読み書き時競合回避条件７００の「１９」、「１７」、「５」フィールドに対応する行番号が「１９，１７，５」の行の組み合わせが設計対象メモリ内のいずれかのメモリバンクには３行以上割り当てる割り当て条件を満たすと判断する。従って、検索装置１００は、行番号が「１９，１７，５」の行の組み合わせを１つのメモリバンクｂ０に割り当てるパターンとして決定する。
【００９５】
図１０の（１１）の処理において、検索装置１００は、設計対象メモリ内の別のメモリバンクに割り当てるパターンを決定するために、メモリバンクに割り当て済みの行の行番号に対応するレコードを除いたレコード群から、レコード７０１−１８を選択する。次に、図１０の（１２）の処理において、検索装置１００は、レコード７０１−１８に対応する、読み書き時競合回避条件７００の「１８」フィールドを選択する。図１０の（１３）の処理において、検索装置１００は、選択したレコード７０１−１８の右側から、メモリバンクに割り当て済みの行の行番号に対応するフィールドを除いて、最初に要素が０になるフィールドを検索する。ここで、検索装置１００は、レコード７０１−１８において要素が０になる読み書き時競合回避条件７００の「１６」フィールドを検出する。そして、検索装置１００は、検出した読み書き時競合回避条件７００の「１６」フィールドを選択する。このとき、検索装置１００は、読み書き時競合回避条件７００の「１６」および「１８」フィールドに対応する行番号が「１６，１８」の行の組み合わせを、１つのメモリバンクに割り当ててもよい行の組み合わせとして設定する。
【００９６】
図１０の（１４）の処理において、検索装置１００は、読み書き時競合回避条件７００の「１８」および「１６」フィールドにおいて、共に要素が０になるレコードがあるか否かを判定する。次に、図１０の（１５）の処理において、検索装置１００は、共に要素が０になるレコード７０１−４にあるため、さらに、レコード７０１−４に対応する読み書き時競合回避条件７００の「４」フィールドを選択する。このとき、検索装置１００は、読み書き時競合回避条件７００の「１８」、「１６」および「４」フィールドに対応する行番号が「４，１６，１８」の行の組み合わせを、１つのメモリバンクに割り当ててもよい行の組み合わせとして設定し直す。
【００９７】
図１０の（１６）の処理において、検索装置１００は、読み書き時競合回避条件７００の「１８」、「１６」および「４」フィールドにおいて、共に要素が０になるレコードがあるか否かを判定する。ここで、共に要素が０になるレコードがない。このため、検索装置１００は、読み書き時競合回避条件７００の「１８」、「１６」および「４」フィールドに対応する行番号が「１８，１６，４」の行が１つのメモリバンクに割り当ててもよい行の組み合わせであると特定する。
【００９８】
図１０の（１７）の処理において、検索装置１００は、設計対象メモリ内のいずれかのメモリバンクには３行以上割り当てるという割り当て条件を満たしているか否かを判定する。ここで、検索装置１００は、３行以上割り当てるという割当条件を満たしているため、設計対象メモリ内の各メモリバンクには２行以上割り当てるという割り当て条件を満たすか否かを判定する。ここで、検索装置１００は、読み書き時競合回避条件７００の「１８」、「１６」および「４」フィールドに対応する行番号が「１８，１６，４」の行の組み合わせが、設計対象メモリ内の各メモリバンクには２行以上割り当てる割り当て条件を満たすと判断する。従って、検索装置１００は、行番号が「１８，１６，４」の行の組み合わせを１つのメモリバンクｂ１に割り当てるパターンとして決定する。検索装置１００は、以降も同様にして、２次元配列型データの各行をメモリバンクに割り当てるパターンを決定する。
【００９９】
次に、図１１を用いて、検索結果の一例について説明する。図１１は、検索結果の一例を示す説明図である。検索装置１００は、図８〜図１０のようにパターンを検索して、２次元配列型データの行の入れ替えパターンに対応する、２次元配列型データの各行を設計対象メモリ内のメモリバンクに割り当てるパターンを決定する。
【０１００】
検索装置１００は、例えば、第１の入れ替えパターンに対応する、設計対象メモリ内のメモリバンクに２次元配列型データの各行を割り当てる第１の割り当てパターン１１０１を決定する。第１の割り当てパターン１１０１は、設計対象メモリ内のメモリバンクｂ０に行番号が「５，１７，１９」の行を割り当てるパターンを含む。また、第１の割り当てパターン１１０１は、設計対象メモリ内のメモリバンクｂ１に行番号が「４，１６，１８」の行を割り当てるパターンを含む。また、第１の割り当てパターン１１０１は、設計対象メモリ内のメモリバンクｂ２に行番号が「９，１３，１５」の行を割り当てるパターンを含む。
【０１０１】
また、第１の割り当てパターン１１０１は、設計対象メモリ内のメモリバンクｂ３に行番号が「８，１２，１４」の行を割り当てるパターンを含む。また、第１の割り当てパターン１１０１は、設計対象メモリ内のメモリバンクｂ４に行番号が「１０，１１」の行を割り当てるパターンを含む。また、第１の割り当てパターン１１０１は、設計対象メモリ内のメモリバンクｂ５に行番号が「６，７」の行を割り当てるパターンを含む。また、第１の割り当てパターン１１０１は、設計対象メモリ内のメモリバンクｂ６に行番号が「０，１，２，３」の行を割り当てるパターンを含む。
【０１０２】
検索装置１００は、例えば、第２の入れ替えパターンに対応する、設計対象メモリ内のメモリバンクに２次元配列型データの各行を割り当てる第２の割り当てパターン１１０２を決定する。第２の割り当てパターン１１０２は、設計対象メモリ内のメモリバンクｂ０に行番号が「１６，１８，１９」の行を割り当てるパターンを含む。また、第２の割り当てパターン１１０２は、設計対象メモリ内のメモリバンクｂ１に行番号が「５，１５，１７」の行を割り当てるパターンを含む。また、第２の割り当てパターン１１０２は、設計対象メモリ内のメモリバンクｂ２に行番号が「１２，１３，１４」の行を割り当てるパターンを含む。
【０１０３】
また、第２の割り当てパターン１１０２は、設計対象メモリ内のメモリバンクｂ３に行番号が「０，１，１１」の行を割り当てるパターンを含む。また、第２の割り当てパターン１１０２は、設計対象メモリ内のメモリバンクｂ４に行番号が「８，９，１０」の行を割り当てるパターンを含む。また、第２の割り当てパターン１１０２は、設計対象メモリ内のメモリバンクｂ５に行番号が「２，３，７」の行を割り当てるパターンを含む。また、第２の割り当てパターン１１０２は、設計対象メモリ内のメモリバンクｂ６に行番号が「４，６」の行を割り当てるパターンを含む。
【０１０４】
次に、図１２を用いて、図１１に示した検索結果に基づいて、各行をメモリバンクに割り当てて設計対象メモリを設計した場合における、書き込み時の競合の有無について説明する。
【０１０５】
図１２は、書き込み時の競合の有無を示す説明図である。図１２の右の表は、第１〜第５の並列書き込み処理が同期して行の各要素を書き込む時刻において行の各要素を書き込むためにアクセスするメモリバンクの識別子を示す。図１２の右の表のメモリバンクの識別子フィールドには、メモリバンクの識別子ｂ０〜ｂ６のいずれかが設定される。
【０１０６】
情報処理装置１０２は、第１の並列書き込み処理として、図４に示したように、書き込まれる行の行番号が「０→１→２→３」の順に、０行目〜３行目までの各行を書き込む。このとき、情報処理装置１０２は、第１の並列書き込み処理として、行番号が「０，１，２，３」の行がメモリバンクｂ６に割り当てられているため、メモリバンクｂ６→ｂ６→ｂ６→ｂ６の順序でアクセスすることになる。
【０１０７】
また、情報処理装置１０２は、第２の並列書き込み処理として、図４に示したように、書き込まれる行の行番号が「７→６→５→４」の順に、４行目〜７行目までの各行を書き込む。このとき、情報処理装置１０２は、第２の並列書き込み処理として、行番号が「７，６，５，４」の行がそれぞれメモリバンクｂ５，ｂ５，ｂ０，ｂ１に割り当てられているため、メモリバンクｂ５→ｂ５→ｂ０→ｂ１の順序でアクセスすることになる。
【０１０８】
同様に、情報処理装置１０２は、第３の並列書き込み処理として、メモリバンクｂ３→ｂ２→ｂ４→ｂ４の順序でアクセスすることになる。また、情報処理装置１０２は、第４の並列書き込み処理として、メモリバンクｂ２→ｂ３→ｂ２→ｂ３の順序でアクセスすることになる。また、情報処理装置１０２は、第５の並列書き込み処理として、メモリバンクｂ１→ｂ０→ｂ１→ｂ０の順序でアクセスすることになる。
【０１０９】
このように、第１〜第５の並列書き込み処理により、並列に書き込まれるため、図１２に示すように、時刻ｔｗ０では、メモリバンクｂ６，ｂ５，ｂ３，ｂ２，ｂ１が、同時にアクセスされる。したがって、時刻ｔｗ０では、アクセスされるメモリバンクが全て異なるため、競合は発生しない。同様に、時刻ｔｗ１〜ｔｗ３についても、図１２に示すように、アクセスされるメモリバンクが全て異なるため、第１〜第５の並列書き込み処理による競合は発生しない。このように、時刻ｔｗ０〜ｔｗ３において、複数の行が１つのメモリバンクに同時に書き込まれることがないため、書き込み時には競合が発生しないことがわかる。
【０１１０】
次に、図１３を用いて、図１１に示した検索結果に基づいて、各行をメモリバンクに割り当てた場合における、読み出し時の競合の有無について説明する。
【０１１１】
図１３は、読み出し時の競合の有無を示す説明図である。図１３の右の表は、第１〜第５の並列書き込み処理が同期して行の各要素を書き込む時刻において行の各要素を書き込むためにアクセスするメモリバンクの識別子を示す。図１３の右の表のメモリバンクの識別子フィールドには、メモリバンクの識別子ｂ０〜ｂ６のいずれかが設定される。
【０１１２】
情報処理装置１０２は、図４に示したように、第１の並列読み出し処理として、読み出される行の行番号が「１９→９→１４→４→０→２→５→７→１２→１８→１０→８→１３→１７→３→１→１６→６→１５→１１」の順に、各行にある要素を読み出す。このとき、情報処理装置１０２は、各行がメモリバンクｂ０〜ｂ６に割り当てられているため、メモリバンクｂ０→ｂ２→ｂ３→ｂ１→ｂ６→ｂ６→ｂ０→ｂ５→ｂ３→ｂ１→ｂ４→ｂ３→ｂ２→ｂ０→ｂ６→ｂ６→ｂ１→ｂ５→ｂ２→ｂ４の順序でアクセスする。
【０１１３】
また、情報処理装置１０２は、図４に示したように、第２の並列読み出し処理として、読み出される行の行番号が「７→５→２→０→４→１４→９→１９→１１→１５→６→１６→１→３→１７→１３→８→１０→１８→１２」の順に、各行の要素を読み出す。このとき、情報処理装置１０２は、各行がメモリバンクｂ０〜ｂ６に割り当てられているため、メモリバンクｂ５→ｂ０→ｂ６→ｂ６→ｂ１→ｂ３→ｂ２→ｂ０→ｂ４→ｂ２→ｂ５→ｂ１→ｂ６→ｂ６→ｂ０→ｂ２→ｂ３→ｂ４→ｂ１→ｂ３の順序で読み出す。
【０１１４】
同様に、情報処理装置１０２は、第３〜第５の並列読み出し処理についても、それぞれ、メモリバンクｂ３→ｂ１→ｂ４→…→ｂ５、メモリバンクｂ６→ｂ６→…→ｂ１、メモリバンクｂ１→ｂ５→…→ｂ６の順序で読み出す。
【０１１５】
このように、第１〜第５の並列読み出し処理により、並列に読み出されるため、時刻ｔｒ０では、メモリバンクｂ０，ｂ５，ｂ３，ｂ６，ｂ１が、同時にアクセスされる。したがって、時刻ｔｒ０では、アクセスされるメモリバンクが全て異なるため、競合は発生しない。また、時刻ｔｒ１では、メモリバンクｂ２，ｂ０，ｂ１，ｂ６，ｂ５が、同時にアクセスされる。したがって、時刻ｔｒ１では、アクセスされるメモリバンクが全て異なるため、競合は発生しない。
【０１１６】
同様に、時刻ｔｒ２〜ｔｒ１９についても、図１３に示すように、アクセスされるメモリバンクが全て異なるため、第１〜第５の並列読み出し処理による競合は発生しない。このように、時刻ｔｒ０〜ｔｒ１９において、１つのメモリバンクから複数の行にある要素が同時に読み出されることがないため、読み出し時にはアクセス競合が発生しないことがわかる。
【０１１７】
次に、図１４を用いて、図１１に示した検索結果に基づいて、各行をメモリバンクに割り当てた場合における、情報処理装置１０２の実装に使用される設計対象メモリのメモリ容量について説明する。
【０１１８】
図１４は、実装に使用される設計対象メモリのメモリ容量を示す説明図である。図１４に示したように、情報処理装置１０２の設計対象メモリとして、第１の割り当てパターン１１０１および第２の割り当てパターン１１０２を実現することができる設計対象メモリが使用される。
【０１１９】
例えば、第１の割り当てパターン１１０１を実現するために、３行分の行を割り当て可能な４つのメモリ領域と、２行分の行を割り当て可能な２つのメモリ領域と、４行分の行を割り当て可能な１つのメモリ領域とを含む設計対象メモリが使用されることになる。また、例えば、第２の割り当てパターン１１０２を実現するために、３行分の行を割り当て可能な６つのメモリ領域と、２行分の行を割り当て可能な１つのメモリ領域とを含む設計対象メモリが使用されることになる。
【０１２０】
ここで、第１の割り当てパターン１１０１および第２の割り当てパターン１１０２を１つの設計対象メモリで実現する場合を例に挙げる。この場合、４行分の行を割り当て可能なメモリ領域ｍ０と、３行分の行を割り当て可能なメモリ領域ｍ１〜ｍ５と、２行分の行を割り当て可能なメモリ領域ｍ６とを含む設計対象メモリが使用されることになる。
【０１２１】
ここで、第１の割り当てパターン１１０１を実現する場合、メモリバンクｂ０は、メモリ領域ｍ１を使用して実現される。また、メモリバンクｂ１は、メモリ領域ｍ２を使用して実現される。また、メモリバンクｂ２は、メモリ領域ｍ３を使用して実現される。また、メモリバンクｂ３は、メモリ領域ｍ４を使用して実現される。また、メモリバンクｂ４は、メモリ領域ｍ５のうちの２行分の領域を使用して実現される。また、メモリバンクｂ５は、メモリ領域ｍ６を使用して実現される。また、メモリバンクｂ６は、メモリ領域ｍ０を使用して実現される。
【０１２２】
一方で、第２の割り当てパターン１１０２を実現する場合、メモリバンクｂ０は、メモリ領域ｍ１を使用して実現される。また、メモリバンクｂ１は、メモリ領域ｍ２を使用して実現される。また、メモリバンクｂ２は、メモリ領域ｍ３を使用して実現される。また、メモリバンクｂ３は、メモリ領域ｍ４を使用して実現される。また、メモリバンクｂ４は、メモリ領域ｍ５を使用して実現される。また、メモリバンクｂ５は、メモリ領域ｍ０のうちの３行分の領域を使用して実現される。また、メモリバンクｂ６は、メモリ領域ｍ６を使用して実現される。
【０１２３】
このように、情報処理装置１０２は、７つのメモリバンクに分割された、２１行分のメモリ容量の設計対象メモリを使用することになる。これにより、情報処理装置１０２は、上述した１０個のメモリバンクに分割されたメモリを使用しなくても、より小型化された７つのメモリバンクに分割された設計対象メモリを使用すれば、アクセス競合を回避することができる。
【０１２４】
ここで、検索装置１００は、検索結果から自動でメモリ容量を算出してもよい。検索装置１００は、例えば、第１の割り当てパターン１１０１で使用される行数を降順に並べた第１の数列「４，３，３，３，３，２，２」を作成する。また、検索装置１００は、第２の割り当てパターン１１０２で使用される行数を降順に並べた第２の数列「３，３，３，３，３，３，２」を作成する。
【０１２５】
次に、検索装置１００は、第１の数列と第２の数列とにおいて、それぞれ同じ位置にある行数のうちの最大の行数を選択した第３の数列「４，３，３，３，３，３，２」を作成する。そして、検索装置１００は、第３の数列のそれぞれの位置にある行数分のメモリ容量を、第１の割り当てパターン１１０１および第２の割り当てパターン１１０２を１つの設計対象メモリで実現する場合のメモリ容量として算出する。
【０１２６】
一方で、図１４の例では、情報処理装置１０２は、７つのメモリバンクに分割された、２１行分のメモリ容量の設計対象メモリを使用すれば、第１の割り当てパターン１１０１および第２の割り当てパターン１１０２を実現することができる。このため、設計対象メモリのサイズが低減され、設計対象メモリに接続する配線領域のサイズも低減され、情報処理装置１０２のサイズも低減することができる。
【０１２７】
次に、図１５を用いて実装結果の一例について説明する。図１５は、実装結果の一例を示す説明図である。図１５に示すように、情報処理装置１０２は、７つのメモリバンクに分割された、２１行分のメモリ容量のメモリ１５０３を使用して、ターボ復号処理を実現する。
【０１２８】
情報処理装置１０２は、具体的には、メモリ１５０１に受信したデータを記憶する。受信したデータは、情報ビットの信頼度となる信頼度情報ビット系列であって、送信元によって符号化された情報ビット系列、および検査ビット系列である。
【０１２９】
次に、情報処理装置１０２は、演算１において、メモリ１５０１に記憶されたデータを、信頼度情報に基づいて復号する。そして、情報処理装置１０２は、インターリーブ回路１５０２において、復号した結果を検査ビットの順に並び替え、それぞれ異なる行位置からそれぞれ行に沿って正方向または逆方向に並列にメモリ１５０３に書き込む。ここで、メモリ１５０３のメモリバンクが図１２に示した検索結果に基づいて分割されているため、情報処理装置１０２はアクセス競合を発生せずに書き込むことができる。
【０１３０】
次に、情報処理装置１０２は、行変換テーブルに基づいて、メモリ１５０３に記憶されたデータの行を入れ替える。そして、情報処理装置１０２は、演算２において、メモリ１５０３に記憶されたデータを、それぞれ異なる行位置からそれぞれ列に沿って読み出し、信頼度情報に基づいて復号する。ここで、メモリ１５０３のメモリバンクが図１２に示した検索結果に基づいて分割されているため、情報処理装置１０２はアクセス競合を発生せずに読み出すことができる。
【０１３１】
次に、情報処理装置１０２は、デインターリーブ回路１５０４において、インタリーブの逆順に、復号した結果を並び換える。そして、情報処理装置１０２は、並べ替えた結果をメモリ１５０１に記憶する。以上の処理を繰り返すことにより、情報処理装置１０２は、データをターボ復号することができる。
【０１３２】
次に、図１６、図１７を用いて、検索装置１００が実行するフローチャートについて説明する。
【０１３３】
図１６は、決定処理手順の一例を示すフローチャートである。図１６において、検索装置１００は、複数のインターリーブパターン４００の中から、未選択のインターリーブパターン４００を選択する（ステップＳ１６０１）。
【０１３４】
次に、検索装置１００は、選択したインターリーブパターン４００に基づいて、書き込み時競合回避条件５００を作成する（ステップＳ１６０２）。そして、検索装置１００は、選択したインターリーブパターン４００に基づいて、読み出し時競合回避条件６００を作成する（ステップＳ１６０３）。
【０１３５】
次に、検索装置１００は、書き込み時競合回避条件５００と読み出し時競合回避条件６００とに基づいて、読み書き時競合回避条件７００を作成する（ステップＳ１６０４）。そして、検索装置１００は、検索装置１００の利用者からの操作入力により、設計対象メモリ内のメモリバンクに割り当てる行の数の割り当て条件を設定する（ステップＳ１６０５）。続けて、検索装置１００は、作成した読み書き時競合回避条件７００と、設定した割り当て条件とに基づいて、図１７に後述する検索処理を実行して、割り当てパターンを決定する（ステップＳ１６０６）。
【０１３６】
次に、検索装置１００は、検索装置１００の利用者からの操作入力に基づいて、割り当て条件を変更するか否かを判定する（ステップＳ１６０７）。検索装置１００の利用者は、例えば、決定された割り当てパターン以外の割り当てパターンをさらに検索する場合、および割り当てパターンが決定されなかった場合などに、割り当て条件を変更する操作入力を行う。
【０１３７】
割り当て条件を変更する場合（ステップＳ１６０７：Ｙｅｓ）、検索装置１００は、検索装置１００の利用者からの操作入力により、設計対象メモリ内のメモリバンクに割り当てる行の数の割り当て条件を変更する（ステップＳ１６０８）。ステップＳ１６０８の処理終了後、検索装置１００は、ステップＳ１６０５の処理に戻る。
【０１３８】
一方、割り当て条件を変更しない場合（ステップＳ１６０７：Ｎｏ）、検索装置１００は、全てのインターリーブパターン４００を選択したか否かを判断する（ステップＳ１６０９）。未選択のインターリーブパターン４００がある場合（ステップＳ１６０９：Ｎｏ）、検索装置１００は、ステップＳ１６０１の処理に戻る。
【０１３９】
一方、全てのインターリーブパターン４００を選択した場合（ステップＳ１６０９：Ｙｅｓ）、検索装置１００は、割り当てパターンからメモリ容量を算出する（ステップＳ１６１０）。次に、検索装置１００は、割り当てパターンとメモリ容量とを出力する（ステップＳ１６１１）。ステップＳ１６１１の処理終了後、検索装置１００は、決定処理を終了する。決定処理を実行することにより、検索装置１００は、インターリーブパターン４００に対応する割り当てパターンを決定することができる。
【０１４０】
次に、図１７を用いて、図１６のステップＳ１６０６に示した、検索装置１００の検索処理手順の一例について説明する。
【０１４１】
図１７は、検索処理手順の一例を示すフローチャートである。図１７において、検索装置１００は、２次元配列型データの行のうち、選択可能な最大行を選択する（ステップＳ１７０１）。次に、検索装置１００は、選択した行以外で、選択した全ての行と共に１つのメモリバンクに割り当て可能な最大行を選択する（ステップＳ１７０２）。
【０１４２】
そして、検索装置１００は、行が選択できたか否かを判断する（ステップＳ１７０３）。選択できた場合（ステップＳ１７０３：Ｙｅｓ）、検索装置１００は、選択した行以外で、選択した全ての行と共に１つのメモリバンクに割り当て可能な最大行を選択する（ステップＳ１７０４）。
【０１４３】
次に、検索装置１００は、行が選択できたか否かを判断する（ステップＳ１７０５）。行が選択できた場合（ステップＳ１７０５：Ｙｅｓ）、検索装置１００は、ステップＳ１７０２の処理に移行する。
【０１４４】
一方、選択できなかった場合（ステップＳ１７０５：Ｎｏ）、検索装置１００は、割り当て条件を満たすか否かを判断する（ステップＳ１７０６）。選択できなかった場合とは、例えば、選択した各行の行番号を含む読み書き時競合回避条件７００のフィールドにおいて、共に０が設定されたレコードが存在しない場合である。
【０１４５】
ここで、割り当て条件を満たさない場合（ステップＳ１７０６：Ｎｏ）、検索装置１００は、検索続行できるか否かを判定する（ステップＳ１７０７）。割り当て条件を満たさない場合とは、割り当て条件が１つのメモリバンクに３行以上割り当てるという条件を含む場合に、選択した行が２行しかない場合である。
【０１４６】
ここで、検索続行できない場合（ステップＳ１７０７：Ｎｏ）、検索装置１００は、検索処理を終了する。検索続行できない場合とは、すべての行が選択済みである場合である。一方、検索続行できる場合（ステップＳ１７０７：Ｙｅｓ）、検索装置１００は、直前に選択した行を選択解除する（ステップＳ１７０８）。次に、検索装置１００は、ステップＳ１７０２の処理に移行する。
【０１４７】
一方、行が選択できなかった場合（ステップＳ１７０３：Ｎｏ）、検索装置１００は、直前に選択した行の代わりに選択可能な行の候補がなくなったか否かを判定する（ステップＳ１７０９）。選択可能な行の候補がある場合（ステップＳ１７０９：Ｎｏ）、検索装置１００は、選択した行を選択不能に設定する（ステップＳ１７１０）。ステップＳ１７１０の処理終了後、検索装置１００は、ステップＳ１７０２の処理に移行する。
【０１４８】
一方、選択可能な行の候補がない場合（ステップＳ１７０９：Ｙｅｓ）、検索装置１００は、割り当て条件を満たし、かつ、検索続行できるか否かを判定する（ステップＳ１７１１）。割り当て条件を満たさない場合、または、検索続行できない場合（ステップＳ１７１１：Ｎｏ）、検索装置１００は、検索処理を終了する。検索続行できない場合とは、すべての行が選択済みである場合である。
【０１４９】
一方、割り当て条件を満たし、かつ、検索続行できる場合（ステップＳ１７１１：Ｙｅｓ）、または、ステップＳ１７０６において割り当て条件を満たす場合（ステップＳ１７０６：Ｙｅｓ）、検索装置１００は、選択した行を選択不能に設定する（ステップＳ１７１２）。次に、検索装置１００は、選択した行の組み合わせを１つのメモリバンクに割り当てるパターンに決定する（ステップＳ１７１３）。ステップＳ１７１３の処理終了後、検索装置１００は、ステップＳ１７０１の処理に戻る。検索処理を実行することにより、検索装置１００は、アクセス競合を発生させずに１つのメモリバンクに割り当てることができる２次元配列型データの行の組み合わせを検索することができる。
【０１５０】
ここで、図８〜図１０で説明した内容が、図１７に示すフローチャートのどのフローに対応するのかを説明する。ステップＳ１７０１の処理は、図８の（１）、（２）、図１０の（１１）、（１２）に相当する。また、ステップＳ１７０２，Ｓ１７０３の処理は、図８の（３）、図９の（６）、図１０の（１３）に相当する。また、ＳステップＳ１７０４，Ｓ１７０５の処理は、図８の（４）、図９の（７）、（８）、（９）、図１０の（１４）、（１５）、（１６）に相当する。また、ステップＳ１７０６の処理は、図８の（５）、図９の（１０）、図１０の（１７）に相当する。また、ステップＳ１７０９，Ｓ１７１０の処理は、図９の（６）に相当する。また、ステップＳ１７１２，Ｓ１７１３の処理は、図９の（１０）、図１０の（１７）に相当する。
【０１５１】
以上説明したように、検索装置１００によれば、書き込み時競合回避条件５００と読み出し時競合回避条件６００とに基づいて、２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索することができる。これにより、検索装置１００は、情報処理装置１０２の設計対象メモリ内の１つのメモリバンクに割り当ててもアクセス競合を発生させない、２次元配列型データの行の組み合わせを検索することができる。このため、検索装置１００の利用者は、検索結果に基づいて、ターボ復号処理においてアクセス競合を発生させないように、情報処理装置１０２の設計対象メモリを実装することができる。
【０１５２】
また、検索装置１００によれば、メモリバンクに割り当てられる行の数の割り当て条件を満たすように、２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索することができる。これにより、検索装置１００は、メモリバンクに割り当てられる行の数の割り当て条件がメモリバンクの数が抑制するように設定された際に行の組み合わせを発見した場合、２次元配列型データの各行を割り当てるメモリバンクの数の増加を抑制することができる。このため、検索装置１００の利用者は、情報処理装置１０２に実装する設計対象メモリのサイズを低減し、設計対象メモリに接続される配線領域のサイズも低減することを図ることができる。
【０１５３】
また、検索装置１００によれば、インターリーブパターン４００に基づいて書き込み時競合回避条件５００と読み出し時競合回避条件６００とを特定することができる。これにより、検索装置１００の利用者は、インターリーブパターン４００から書き込み時競合回避条件５００と読み出し時競合回避条件６００とを作成する処理を行わなくてもよくなり、作業量を低減することができる。
【０１５４】
ここで、情報処理装置１０２が携帯端末である場合、情報処理装置１０２を小型化する要望がある。しかしながら、従来では、情報処理装置１０２が、アクセス競合を回避するために、アクセス競合を調停する回路を使用しなければならず、小型化することができないことがある。一方で、情報処理装置１０２は、検索装置１００の検索結果に基づく２次元配列型データの各行が割り当て可能なメモリバンクを有する設計対象メモリが実装されるため、アクセス競合を発生させずに２次元配列型データの読み書きを行うことができる。このため、調停する回路によって、情報処理装置１０２のサイズが増大することを抑制することができる。
【０１５５】
なお、本実施の形態で説明した検索方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本検索プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本検索プログラムは、インターネット等のネットワークを介して配布してもよい。
【０１５６】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１５７】
（付記１）メモリへの書き込み時はそれぞれ異なる行位置にある要素がそれぞれ行に沿って正方向または逆方向に連続的に書き込まれ、前記メモリからの読み出し時は行が入れ替えられた状態でそれぞれ異なる行位置にある要素がそれぞれ列に沿って正方向または逆方向に連続的に読み出される２次元配列型データにおいて、並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、前記２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索する制御部、
を有することを特徴とする検索装置。
【０１５８】
（付記２）前記２次元配列型データのそれぞれの行は前記メモリ内のメモリバンクに割り当てられることを特徴とする付記１に記載の検索装置。
【０１５９】
（付記３）前記制御部は、前記２次元配列型データの行数と前記メモリ内のメモリバンクの上限数とから特定される前記メモリ内の各メモリバンクに割り当て可能な行数の条件を満たす、前記並列に読み書きされない行の組み合わせを検索することを特徴とする付記１または２に記載の検索装置。
【０１６０】
（付記４）前記制御部は、前記メモリへの書き込み時に書き込みが開始される行位置と、書き込まれる要素がある行位置の遷移方向とに基づいて、前記並列に書き込まれる行の組み合わせを特定することを特徴とする付記１〜３のいずれか一つに記載の検索装置。
【０１６１】
（付記５）前記制御部は、前記メモリからの読み出し時に読み出しが開始される行位置と、読み出される要素がある行位置の遷移方向とに基づいて、前記並列に読み出される行の組み合わせを特定することを特徴とする付記１〜４のいずれか一つに記載の検索装置。
【０１６２】
（付記６）コンピュータが、
メモリへの書き込み時はそれぞれ異なる行位置にある要素がそれぞれ行に沿って正方向または逆方向に連続的に書き込まれ、前記メモリからの読み出し時は行が入れ替えられた状態でそれぞれ異なる行位置にある要素がそれぞれ列に沿って正方向または逆方向に連続的に読み出される２次元配列型データにおいて、並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、前記２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索する、
処理を実行することを特徴とする検索方法。
【０１６３】
（付記７）コンピュータに、
メモリへの書き込み時はそれぞれ異なる行位置にある要素がそれぞれ行に沿って正方向または逆方向に連続的に書き込まれ、前記メモリからの読み出し時は行が入れ替えられた状態でそれぞれ異なる行位置にある要素がそれぞれ列に沿って正方向または逆方向に連続的に読み出される２次元配列型データにおいて、並列に書き込まれる行の組み合わせと並列に読み出される行の組み合わせとに基づいて、前記２次元配列型データのうちの並列に読み書きされない行の組み合わせを検索する、
処理を実行されることを特徴とする検索プログラム。
【符号の説明】
【０１６４】
１００  検索装置
１０１，１０２  情報処理装置
３０１  特定部
３０２  検索部
３０３  出力部
【図１】
2015130128.tif 000003
【図２】
2015130128.tif 000004
【図３】
2015130128.tif 000005
【図４】
2015130128.tif 000006
【図５】
2015130128.tif 000007
【図６】
2015130128.tif 000008
【図７】
2015130128.tif 000009
【図８】
2015130128.tif 000010
【図９】
2015130128.tif 000011
【図１０】
2015130128.tif 000012
【図１１】
2015130128.tif 000013
【図１２】
2015130128.tif 000014
【図１３】
2015130128.tif 000015
【図１４】
2015130128.tif 000016
【図１５】
2015130128.tif 000017
【図１６】
2015130128.tif 000018
【図１７】
2015130128.tif 000019