(57)【特許請求の範囲】
【請求項１】
少なくともインタリーブの対象となる全データ数までのカウント値を出力し、クロック信号により、順次、該カウント値のビットパターンを生成するマルチステージ・インタリーブ・パターン生成器であって、
前記カウント値が正の整数Ｋ及びＬの積であり、かつ該整数Ｋが２のべき乗の約数を有する場合のマルチステージ・インタリーブ・パターン生成器において、
前記整数Ｋの値までクロック信号の入力毎にカウントアップするＫ進カウンタと、該Ｋ進カウンタから出力されるキャリー信号を前記整数Ｌの値までカウントアップするＬ進カウンタと、該Ｋ進カウンタから出力されるビットパターンに対して上位側のビットと下位側のビットとを互いに対称的に入れ替えるマルチステージ・インタリーブ・パターン生成部と、該マルチステージ・インタリーブ・パターン生成部から出力されるビットパターンの値に前記整数Ｌを乗算する乗算器と、該乗算器の出力値とＬ進カウンタから得られるビットパターンの値とを加算する加算器とを備えたことを特徴とするマルチステージ・インタリーブ・パターン生成器。
【請求項２】
前記整数Ｌが２のべき乗の約数を有する場合のマルチステージ・インタリーブ・パターン生成器において、Ｌ進カウンタから出力される上位側のビットと下位側のビットとを互いに対称的に入れ替える第２のマルチステージ・インタリーブ・パターン生成部を備え、前記加算器は、該第２のマルチステージ・インタリーブ・パターン生成部から出力されるビットパターンの値と前記乗算器の出力値とを加算するように構成したことを特徴とする請求項１に記載のマルチステージ・インタリーブ・パターン生成器。
【請求項３】
前記Ｋ進カウンタ又はＬ進カウンタを、昇順にカウント値を生成するカウントアップ動作と降順にカウント値を生成するカウントダウン動作の機能を有する構成とし、リバース設定の有無を判定し、該カウントアップ動作とカウントダウン動作とを切替えるリバース判定部を備えたことを特徴とする請求項１又は２に記載のマルチステージ・インタリーブ・パターン生成器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ通信システム等におけるバースト誤りを回避するために必須であるマルチステージ・インタリーブ（ＭＩＬ：Ｍｕｌｔｉ−ｓｔａｇｅ  ＩｎｔｅｒＬｅａｖｉｎｇ）を行う際、又は、マルチステージ・インタリーブされたデータのデインタリーブを行う際に用いるマルチステージ・インタリーブ・パターン生成器に関する。
【０００２】
マルチステージ・インタリーブ（ＭＩＬ）は、インタリーブを多段に行うもので、１段のみの通常のインタリーブに比べて、相関する連続データを更に分散させ、連続する一かたまりのデータのバースト誤りに対する受信・再生データの誤り訂正又はその修正能力を向上させるものである。
【０００３】
マルチステージ・インタリーブ（ＭＩＬ）は、データ通信システム以外のデータの記録・再生装置等にも適用することができるが、以下では、データ通信システムに適用した場合を例に挙げて説明する。
【０００４】
マルチステージ・インタリーブ（ＭＩＬ）を行うには、送信データをシーケンシャルにメモリアドレスに書込み、書込んだ送信データを、マルチステージ・インタリーブ・パターン生成器から生成される順序パターンに従って、その順序パターンに対応したメモリアドレスから順次読出すことにより、送信データの順序を分散させて送信する。
【０００５】
受信側のマルチステージ・デインタリーブは、マルチステージ・インタリーブ・パターン生成器から生成される順序パターンに従って、その順序パターンに対応したメモリアドレスに受信データを順次書込み、書込んだ受信データをシーケンシャルにメモリアドレスから読出し、不連続な順序の受信データを元の順序に戻す処理を行う。
【０００６】
マルチステージ・インタリーブは、１段のみのインタリーブに比べて、送信データの順序入替えパターン（インタリーブパターン）が複雑となる一方、近年のＬＳＩ、パッケージボード（ＰＣＢ）プリント板等の小型化、高密度化及び低消費電力化の要求に伴い、その回路規模の縮小及びメモリ等の削減が重要な課題となっている。このため、複雑なマルチステージ・インタリーブ・パターンを効率良く生成する必要がある。
【０００７】
【従来の技術】
図１７は従来のマルチステージ・インタリーブ・パターン生成器の説明図である。従来、マルチステージ・インタリーブ・パターン生成において、マルチステージ・インタリーブ・パターンの複雑さ、膨大なデータ長及び複数のパターン種別等を考慮すると、メモリ無しでのロジック回路化は困難と考えられていた。
【０００８】
そのため、送信するデータのデータ長及び種別によって異なるマルチステージ・インタリーブ・パターンを、それぞれ個別にテーブル化し、各テーブルを記憶する複数のメモリを設け、該メモリの読出しにより、マルチステージ・インタリーブ・パターンを取り出していた。
【０００９】
従来のマルチステージ・インタリーブ・パターン生成器は、図１７に示すように、データ長及びパターン種別によって異なるマルチステージ・インタリーブ・パターンを、複数（ｎ個）  のメモリ（ＲＡＭ：Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１７−１に記憶し、各メモリ１７−１から読み出されるマルチステージ・インタリーブ・パターンを、セレクタ１７−２により選択して出力するものである。
【００１０】
それぞれ異なるマルチステージ・インタリーブ・パターンデータ（ＭＩＬデータ）は、個々のメモリ１７−１に、チップセレクト（ＣＳ）信号及び書込みアドレス信号により、書込み位置を指定して記憶される。
【００１１】
そして、チップセレクト（ＣＳ）信号により、メモリ１７−１の１つを選択するとともに、セレクタ１７−２をセレクト（ＳＥＬ）信号により制御してメモリ１７−１の出力データを選択し、選択したメモリから順次、読出しアドレスを与えて必要なマルチステージ・インタリーブ・パターンデータを読出し、種類の異なるマルチステージ・インタリーブ・パターンデータを取り出す。
【００１２】
また、別な手段として、各マルチステージ・インタリーブ・パターンテーブルを記憶するＲＡＭ等のメモリを複数使用せず、送信するデータのデータ長を基に所定の演算式により、マルチステージ・インタリーブ・パターンを算出し、算出したマルチステージ・インタリーブ・パターンを、毎回メモリに上書きして生成することができる。
【００１３】
前者の各マルチステージ・インタリーブ・パターンテーブルをメモリに記憶しておく構成は、膨大なメモリ容量が必要となり、後者の各マルチステージ・インタリーブ・パターンを演算により生成する構成は、ディジタルシグナルプロセッサ（ＤＳＰ）等によるプログラム処理が必要で、且つ、毎回演算を行うため、処理に遅延を生じる。
【００１４】
【発明が解決しようとする課題】
各マルチステージ・インタリーブ・パターンテーブルをメモリに記憶する手法は、メモリの削減ができず、ＬＳＩ、パッケージボード（ＰＣＢ）プリント板の小型化、高密度化及び低消費電力化において難点がある。
【００１５】
また、ディジタルシグナルプロセッサ（ＤＳＰ）等のプロセッサにより、各マルチステージ・インタリーブ・パターンを演算して生成する手法は処理遅延を伴い、該処理遅延は、高速化が要求されるデータ通信において、致命的な欠点となる。
【００１６】
本発明は、マルチステージ・インタリーブ・パターンの生成手段を、メモリやディジタルシグナルプロセッサ（ＤＳＰ）等のプロセッサを一切使用せず、ロジック回路のみで実現し、回路規模の小型化、高密度化、低消費電力化及び処理の高速化を可能とすることを目的とする。
【００１７】
【課題を解決するための手段】
本発明のマルチステージ・インタリーブ・パターン生成器は、（１）少なくともインタリーブの対象となる全データ数までのカウント値を出力し、クロック信号により、順次、該カウント値のビットパターンを生成するカウントアップ部と、該カウントアップ部から出力される上位側のビットと下位側のビットとを、互いに対称的に入替えるマルチステージ・インタリーブ・パターン生成部とを備えたものである。
【００１８】
また、（２）前記カウントアップ部は、８進カウンタにより構成され、前記マルチステージ・インタリーブ・パターン生成部は、該カウントアップ部から出力される最上位ビットと最下位ビットとを互いに入替えて出力する構成を有するものである。
【００１９】
また、（３）前記（１）又は（２）におけるカウントアップ部から出力されるキャリー信号により動作する２進カウンタと、前記（１）又は（２）におけるマルチステージ・インタリーブ・パターン生成部から出力されるビットパターンの更に下位側に、前記２進カウンタの出力ビットを付け加えたビットパターンを出力する合成部とを更に備えたものである。
【００２０】
また、（４）前記カウントアップ部を、１６進カウンタにより構成したものである。
また、（５）前記カウントアップ部を、２のべき乗の整数値までカウントするカウンタにより構成したものである。
【００２１】
また、（６）前記（１）におけるカウントアップ部をＫ（Ｋは任意の整数）  進カウンタとし、該Ｋ進カウンタから出力されるキャリー信号を計数するＬ（Ｌは任意の整数）  進カウンタと、前記（１）に記載のマルチステージ・インタリーブ・パターン生成部から出力されるビットパターンの値に前記整数Ｌを乗算する乗算器と、該乗算器の出力値とＬ進カウンタの出力値とを加算する加算器とを更に備えたものである。
【００２２】
また、（７）前記Ｌ進カウンタから出力される上位側のビットと下位側のビットとを互いに対称的に入替える第２のマルチステージ・インタリーブ・パターン生成部を備え、前記加算器は、該第２のマルチステージ・インタリーブ・パターン生成部から出力されるビットパターンの値と前記乗算器の出力値とを加算するように構成したものである。
【００２３】
また、（８）前記カウントアップ部を、昇順にカウント値を生成するカウントアップ動作と降順にカウント値を生成するカウントダウン動作の機能を有する構成とし、リバース設定の有無を判定し、該カウントアップ動作とカウントダウン動作とを切替えるリバース判定部を備えたものである。
【００２４】
【発明の実施の形態】
図１は、本発明のマルチステージ・インタリーブ・パターン生成器の基本構成の説明図である。同図の（Ａ）において、１−１はカウントアップ部、１−２はマルチステージ・インタリーブ・パターン生成部である。
【００２５】
カウントアップ部１−１は、マルチステージ・インタリーブを行う最小の基本構成においては、８進カウンタで構成され、初期値“０００  （０）  ”が設定され、クロック信号によりカウントアップし、順次、０００  （０），００１  （１），０１０  （２），０１１  （３），１００  （４），１０１  （５），１１０  （６），１１１  （７）  のビットパターンを出力する。
【００２６】
マルチステージ・インタリーブ・パターン生成部１−２は、カウントアップ部１−１から出力されるビットパターンの最上位ビットＭＳＢと最下位ビットＬＳＢとを入替えるＭＳＢ−ＬＳＢビット操作回路により構成される。
【００２７】
同図の（Ｂ）は、図の（Ａ）に示すカウントアップ部１−１を３つのフリップフロップＱ０，Ｑ１，Ｑ２により構成し、最下位ビットＬＳＢを出力するフリップフロップＱ０の出力ビットと、最上位ビットＭＳＢを出力するフリップフロップＱ２の出力ビットとを、マルチステージ・インタリーブ・パターン生成部１−２において互いに入替えて、マルチステージ・インタリーブ・パターンを出力するように構成した例を示している。
【００２８】
マルチステージ・インタリーブ・パターン生成部１−２から順次出力されるビットパターンは、０００  （０），１００  （４），０１０  （２），１１０  （６），００１  （１），１０１  （５），０１１  （３），１１１  （７）  となる。
【００２９】
８個のデータのマルチステージ・インタリーブを行う場合の一般的な手順は、まず、８個のデータを、縦に２個、横に４個並べた２×４個のデータ、又は縦に４個、横に２個並べた４×２個のデータとする。そして、縦又は横に並べた４個のデータを更に、縦に２個、横に２個並べて、インタリーブを行う。
【００３０】
ここで、８個のデータを、縦に２個、横に４個並べ、横に並べた４個のデータを更に、縦に２個、横に２個並べて行うマルチステージ・インタリーブを、式：８（２×４（２×２））と表す。また、８個のデータを、縦に４個、横に２個並べ、縦に並べた４個のデータを更に、縦に２個、横に２個並べて行うマルチステージ・インタリーブを、式：８（４（２×２）×２）と表す。
【００３１】
図２は式：８（２×４（２×２））及び式：８（４（２×２）×２）のマルチステージ・インタリーブの説明図である。図の（Ａ）は式：８（２×４（２×２））、図の（Ｂ）は式：８（４（２×２）×２）によるマルチステージ・インタリーブの操作手順を示している。なお、いずれの算出式の操作手順でマルチステージ・インタリーブを行っても、最終的に得られるマルチステージ・インタリーブ・パターンは同一である。
【００３２】
図２の（Ａ）において、式：８（２×４（２×２））の下線部ａの８（２×４）についてインタリーブ操作を行い、（Ａ−１）に示すように、０から７までのデータを、０から３までのデータと４から７までのデータとに分けて２次元的に配列する。
【００３３】
次に、式：８（２×４（２×２））の下線部ｂの４（２×２）について、横方向のインタリーブ操作を行うと、（Ａ−２）に示すように、０から３までのデータが、０，２，１，３の順に入替えられ、また、４から７までのデータが、４，６，５，７の順に入替えられる。
【００３４】
そして、横に並んだ０，２，１，３の順のデータと４，６，５，７の順のデータとを、縦方向の順に出力することにより、０，４，２，６，１，５，３，７の順のマルチステージ・インタリーブ・パターンが生成される。
【００３５】
図の（Ｂ）に示す式：８（４（２×２）×２）によるマルチステージ・インタリーブの操作手順の場合、（Ｂ−１）に示す８（４×２）のインタリーブを行い、縦方向に０，２，４，６及び１，３，５，７と並んだ２次元配列を生成し、次に、（Ｂ−２）に示すように縦方向のインタリーブを行うと、縦方向に０，４，２，６及び１，５，３，７と並んだ２次元配列が生成され、該配列を縦方向の順に出力することとすると、送出順序は、０，４，２，６，１，５，３，７となり、このパターンは、前述の（Ａ）のマルチステージ・インタリーブ・パターンと同一である。
【００３６】
このように、前述の図１に示したマルチステージ・インタリーブ・パターン生成器により得られるパターンは、式：８（２×４（２×２））及び式：８（４（２×２）×２）のマルチステージ・インタリーブ・パターンと同一であり、図１に示すロジック回路により、０，４，２，６，１，５，３，７のマルチステージ・インタリーブ・パターンを生成することができる。
この８パターン長のマルチステージ・インタリーブ・パターンは、マルチステージ・インタリーブ・パターンにおける最短長の基本パターンである。
【００３７】
図３は、基本パターンの２倍長のマルチステージ・インタリーブ・パターン生成器の説明図である。このパターン生成器は図の（Ａ）に示すように、前述したようなカウントアップ部３−１とマルチステージ・インタリーブ・パターン生成部３−２とからなる基本パターンの生成回路のほかに、２進カウンタ３−３と合成部３−４とを備えたものである。
【００３８】
図の（Ｂ）は、基本パターンの生成回路として、カウントアップ部３−１に、図１に示す３つのフリップフロップＱ０，Ｑ１，Ｑ２による８進カウンタを用いた構成例を示している。
【００３９】
マルチステージ・インタリーブ・パターン生成部３−２は、カウントアップ部３−１の出力ビットの最上位ビットＭＳＢと最下位ビットＬＳＢとを入替えるＭＳＢ−ＬＳＢビット操作回路で構成され、この構成は、図１に示したものと同様である。
【００４０】
２進カウンタ３−３は、カウントアップ部３−１の最上位ビットからの桁上げ信号であるキャリー信号（ＣＯ：Ｃａｒｒｙ  Ｏｕｔ  ）が入力されると“１”を出力する。合成部３−４は、マルチステージ・インタリーブ・パターン生成部３−２から出力される３ビットの出力に、２進カウンタ３−３から出力される１ビットを最下位ビットに付け加え、４ビットのビットパターンとして出力する。
【００４１】
図３の（Ｂ）に示したマルチステージ・インタリーブ・パターン生成器は、カウントアップ部３−１に８進カウンタを用いたため、１６パターン長のマルチステージ・インタリーブ・パターンを生成するが、基本パターンの生成回路としては任意のパターン長のマルチステージ・インタリーブ・パターン生成回路を用いることができる。
【００４２】
図４は、１６パターン長のマルチステージ・インタリーブ・パターンの説明図である。同図は、１６パターン長のマルチステージ・インタリーブ・パターンを、式：１６（４（２×２）×４（２×２））の算出式によるインタリーブ操作により生成する例を示している。
【００４３】
なお、１６パターン長のマルチステージ・インタリーブ・パターンは、式：１６（８（４（２×２）×２）×２）の算出式によっても、また、式：１６（２×８（４（２×２）×２））の算出式によっても、同一のパターンが生成される。
【００４４】
まず、図の（Ａ）に示す式：１６（４（２×２）×４（２×２））の下線部ａの１６（４×４）についてインタリーブ操作を行い、図の（Ｂ）に示すように、０から１５までのデータを、０から３、４から７、８から１１、１２から１５の四つずつのデータに分けて２次元的に配列する。
【００４５】
次に、式：１６（４（２×２）×４（２×２））の下線部ｂの４（２×２）についてインタリーブ操作を行い、（Ｃ）に示すように、縦方向に並んだ四つのデータに対してそれぞれ順序を入替える。
【００４６】
次に式：１６（４（２×２）×４（２×２））の下線部ｃの４（２×２）についてインタリーブ操作を行い、図の（Ｄ）に示すように、横方向に並んだ四つのデータに対してそれぞれ順序を入替える。
【００４７】
これらのインタリーブ操作によって生成されるマルチステージ・インタリーブ・パターンは、図の（Ｄ）の矢印の右側に示す２次元配列のデータを、縦方向の順に取出して並べることにより、０，８，４，１２，２，１０，６，１４，１，９，５，１３，３，１１，７，１５のパターンとなる。
【００４８】
一方、図３の（Ｂ）に示すカウントアップ部３−１及びマルチステージ・インタリーブ・パターン生成部３−２から生成されるパターンは、図４の（Ｅ）に示すパターンとなり、該マルチステージ・インタリーブ・パターン生成部３−２の出力ビットと２進カウンタ３−３の出力ビットとを合成する合成部３−４から出力される出力ビットのパターンは、図４の（Ｆ）に示すとおり、０，８，４，１２，２，１０，６，１４，１，９，５，１３，３，１１，７，１５のパターンとなり、前述の式１６：（４（２×２）×４（２×２））によるインタリーブ操作により生成されるマルチステージ・インタリーブ・パターンと合致する。
【００４９】
図５は、本発明の１６パターン長のマルチステージ・インタリーブ・パターン生成器の第２の構成例の説明図である。同図の（Ａ）において、５−１は１６進アップカウンタ、５−２はマルチステージ・インタリーブ・パターン生成部である。
【００５０】
１６進アップカウンタ５−１は、四つのフリップフロップＱ０，Ｑ１，Ｑ２，Ｑ３により構成され、この順序で低位ビットから高位ビットのビットパターンを出力するものとする。即ち、フリップフロップＱ０が最下位ビットＬＳＢを出力し、フリップフロップＱ３が最上位ビットＭＳＢを出力するものとする。
【００５１】
マルチステージ・インタリーブ・パターン生成部５−２は、１６進アップカウンタ５−１のフリップフロップＱ０の出力を最上位ビットの位置に入替え、フリップフロップＱ１の出力を最上位から２番目のビット位置に入替え、フリップフロップＱ２の出力を最下位から２番目のビット位置に入替え、フリップフロップＱ３の出力を最下位ビットの位置に入替える。
【００５２】
１６進アップカウンタ５−１から出力されるビットパターンは、図５の（Ｂ）に示すとおりとなる。１６進アップカウンタ５−１の出力ビットの入替えを行ったマルチステージ・インタリーブ・パターン生成部５−２からの出力ビットパターンは、図５の（Ｃ）に示すとおりとなり、この出力ビットパターンの順序パターンは、図４の（Ｄ）に示したマルチステージ・インタリーブ・パターンと合致する。
【００５３】
図６は、本発明の３２パターン長のマルチステージ・インタリーブ・パターン生成器の構成例の説明図である。同図の（Ａ）において、６−１は３２進アップカウンタ、６−２はマルチステージ・インタリーブ・パターン生成部である。
【００５４】
３２進アップカウンタ６−１は、五つのフリップフロップＱ０，Ｑ１，Ｑ２，Ｑ３，Ｑ４により構成され、この順序で低位ビットから高位ビットのビットパターンを出力するものとする。即ち、フリップフロップＱ０が最下位ビットＬＳＢを出力し、フリップフロップＱ４が最上位ビットＭＳＢを出力する。
【００５５】
マルチステージ・インタリーブ・パターン生成部６−２は、３２進アップカウンタ６−１のフリップフロップＱ０の出力を最上位ビットの位置に入替え、フリップフロップＱ１の出力を最上位から２番目のビット位置に入替え、フリップフロップＱ２の出力はそのまま同じビット位置とし、フリップフロップＱ３の出力を最下位から２番目のビット位置に入替え、フリップフロップＱ４の出力を最下位ビットの位置に入替える。
【００５６】
３２進アップカウンタ６−１から出力されるビットパターンは、図の（Ｂ）に示すとおりとなる。３２進アップカウンタ６−１の出力ビットの入替えを行ったマルチステージ・インタリーブ・パターン生成部６−２からの出力ビットパターンは、図６の（Ｃ）に示すとおりとなり、この出力ビットパターンの順序パターンは、０，１６，８，２４，４，２０，１２，２８，２，１８，１０，２６，６，２２，１４，３０，・・・７，２３，１５，３１となる。
【００５７】
一方、３２パターン長のマルチステージ・インタリーブ・パターンを、式：３２（４（２×２）×８（４（２×２）×２））のインタリーブ操作により、生成すると以下のようになる。
【００５８】
図７に３２パターン長のマルチステージ・インタリーブ・パターンの生成手順を示す。まず、図の（Ａ）に示す式：３２×（４（２×２）×８（４（２×２）×２））の下線部ａの３２（４×８）について、インタリーブ操作を行うと、図の（Ｂ）に示す２次元配列パターンが得られる。
【００５９】
次に、式：３２×（４（２×２）×８（４（２×２）×２））の下線部ｂの４（２×２）について縦方向のインタリーブ操作を行うと、図の（Ｃ）に示す２次元配列パターンが得られる。
【００６０】
次に、式：３２×（４（２×２）×８（４（２×２）×２））の下線部ｃの８（４（２×２）×２）について横方向のインタリーブ操作を行うと、図の（Ｄ）に示す２次元配列パターンが得られる。
【００６１】
従って、生成されるマルチステージ・インタリーブ・パターンは、０，１６，８，２４，４，２０，１２，２８，２，１８，１０，２６，６，２２，１４，３０，・・・７，２３，１５，３１となる。このパターンは、前述の図６の（Ｃ）に示すマルチステージ・インタリーブ・パターン生成部６−２から出力されるパターンと合致する。
【００６２】
なお、この３２パターン長のマルチステージ・インタリーブ・パターンは、他の算出式によって得られるマルチステージ・インタリーブ・パターンと同一となる。他の算出式として、式：３２（２×１６（４（２×２）×４（２×２）））、式：３２（１６（４（２×２）×４（２×２））×２）、式：３２（４（２×２）×８（２×４（２×２）））、式：３２（８（４（２×２）×２）×４（２×２））、式：３２（８（２×４（２×２））×４（２×２））により生成してもよい。
【００６３】
前述の３２パターン長のマルチステージ・インタリーブ・パターン生成器から類推されるように、２のべき乗のパターン長のマルチステージ・インタリーブ・パターン生成器は、以下のように構成することができる。
【００６４】
図８は、２のべき乗のパターン長のマルチステージ・インタリーブ・パターン生成器の説明図である。２ｎ＋１  進アップカウンタ８−１は、ｎ＋１個のフリップフロップＱ０，Ｑ１，・・・Ｑｎにより構成され、この順序で低位ビットから高位ビットのビットパターンを出力するものとする。即ち、フリップフロップＱ０が最下位ビットＬＳＢを出力し、フリップフロップＱｎが最上位ビットＭＳＢを出力する。
【００６５】
マルチステージ・インタリーブ・パターン生成部８−２は、２ｎ＋１  進アップカウンタ８−１のフリップフロップＱ０の出力を最上位ビットの位置に入替え、フリップフロップＱ１の出力を最上位から２番目のビット位置に入替え、以下、順番に低位側ビットと高位側ビットとを互いに対称的に入替え、中央位置のフリップフロップの出力はそのまま同じビット位置とし、フリップフロップＱ（ｎ−１）の出力を最下位から２番目のビット位置に入替え、フリップフロップＱｎの出力を最下位ビットの位置に入替える。
【００６６】
このように構成した２のべき乗のパターン長のマルチステージ・インタリーブ・パターン生成器は、前述のような算出式を基にインタリーブ操作を多段に行う手順により生成されるマルチステージ・インタリーブ・パターンと同一のパターンを生成する。
【００６７】
図９は、任意の整数の積のパターン長のマルチステージ・インタリーブ・パターン生成器の説明図である。同図において、９−１は第１のマルチステージ・インタリーブ・パターン生成器、９−２は第２のマルチステージ・インタリーブ・パターン生成器、９−３は乗算部、９−４はビット合わせ部、９−５は加算部である。
【００６８】
第１のマルチステージ・インタリーブ・パターン生成器９−１は、Ｋ個のパターン長のマルチステージ・インタリーブ・パターンを生成し、第２のマルチステージ・インタリーブ・パターン生成器９−２は、Ｌ個のパターン長のマルチステージ・インタリーブ・パターンを生成するものとする。
【００６９】
第２のマルチステージ・インタリーブ・パターン生成器９−２は、第１のマルチステージ・インタリーブ・パターン生成器９−１の動作が一通り終了した時点で出力されるキャリー信号をクロック信号として受信し、内部のカウンタを動作させる。
【００７０】
ここで、第１及び第２のマルチステージ・インタリーブ・パターン生成器９−１，９−２は、可能な限り多段にインタリーブを行うもので、１段階のみしかインタリーブを行うことができない場合は、１段のインタリーブ・パターンを生成し、整数Ｋ又はＬが約数を持たない場合、即ち、インタリーブ不能の場合は、Ｋ進又はＬ進のアップカウント値のビットパターンをそのまま出力する。
【００７１】
なお、後述するように、整数Ｋ又はＬが約数を持たないが、Ｋ又はＬがＰ×Ｑ−Ｒ（Ｐ，Ｑ，Ｒは整数）と表せる場合には、Ｐ×Ｑ個のデータが存在するものと仮定し、Ｐ×Ｑ個のデータについてマルチステージ・インタリーブ操作を行い、その結果得られるマルチステージ・インタリーブ・パターンのなかから、Ｋ又はＬ個分のマルチステージ・インタリーブ・パターンを取り出して（Ｒ個のパターンは無視又は除外して）、マルチステージ・インタリーブ・パターンを生成する構成とすることができる。
【００７２】
乗算器９−３は、第１のマルチステージ・インタリーブ・パターン生成器９−１から出力されるビットパターンの値に、第２のマルチステージ・インタリーブ・パターン生成器９−２のパターン長Ｌを乗算する。
【００７３】
ビット合わせ部９−４は、第２のマルチステージ・インタリーブ・パターン生成器９−２から出力されるビット数を、乗算部９−３から出力されるビット数に合わせるために、上位ビットに“０”を付け加えるものである。
【００７４】
加算部９−５は、乗算部９−３から出力されるビットパターン値と、ビット合わせ部９−４から出力されるビットパターン値とを加算し、その加算値のビットパターンを、マルチステージ・インタリーブ・パターンとして出力する。
【００７５】
以下、Ｋ×Ｌパターンのマルチステージ・インタリーブ・パターン生成器の具体的な構成例として、Ｋ＝４，Ｌ＝３とした１２パターン長のマルチステージ・インタリーブ・パターン発生器の構成例について説明する。
【００７６】
図１０は、１２パターン長のマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。同図において、１０−１は４進アップカウンタ、１０−２は３進アップカウンタ、１０−３はＭＳＢ−ＬＳＢ操作回路、１０−４は乗算器、１０−５はビット合わせ回路、１０−６は加算器、１０−７はカウンタロード信号生成回路である。
【００７７】
４進アップカウンタ１０−１は、２つのフリップフロップを備え、２ビットのビットパターンをＭＳＢ−ＬＳＢ操作回路１０−３に出力するとともに、キャリー信号を３進アップカウンタ１０−２に出力する。
【００７８】
ＭＳＢ−ＬＳＢ操作回路１０−３は、４進アップカウンタ１０−１から出力される最上位ビットＭＳＢと最下位ビットＬＳＢとを入替える操作を行う。乗算器１０−４は、１ビットシフト回路と加算回路（ＡＤＤ）とからなり、ＭＳＢ−ＬＳＢ操作回路１０−３から出力されるビットパターン値に“３”（“１１”）を乗算する。
【００７９】
３進アップカウンタ１０−２は、４進アップカウンタ１０−１から出力されるキャリー信号をカウントアップし、２ビットの３進カウント値をビット合わせ回路１０−５に出力する。
【００８０】
ビット合わせ回路１０−５は、３進アップカウンタ１０−２から出力されるビットパターンのビット数を、乗算器１０−４の出力ビット数に揃えるために、上位側に“０”のビットを２つ付け加える。
【００８１】
加算器１０−６は、乗算器１０−４の出力ビットパターンの値と、ビット合わせ回路１０−５の出力ビットパターンの値とを加算し、その加算値のビットパターンを、マルチステージ・インタリーブ・パターンとして出力する。
【００８２】
カウンタロード信号生成回路１０−７は、加算器１０−６から出力される１２個のビットパターンを計数し、計数終了後に、４進アップカウンタ１０−１及び３進アップカウンタ１０−２をリセットして計数動作を再開させるためのカウンタロード信号を生成する。
【００８３】
図１１は、１２パターン長のマルチステージ・インタリーブ・パターンの説明図である。１２パターン長のマルチステージ・インタリーブ・パターンを、式：１２（４（２×２）×３）のインタリーブ操作により、生成すると以下のようになる。なお、他の式によっても得られるマルチステージ・インタリーブ・パターンも同一である。
【００８４】
まず、図の（Ａ）の式：１２（４（２×２）×３）の下線部ａの１２（４×３）について、インタリーブ操作を行うと、図１１の（Ｂ）に示す２次元配列パターンが得られる。次に、式：１２（４（２×２）×３）の下線部ｂの４（２×２）について縦方向のインタリーブ操作を行うと、図１１の（Ｃ）に示す２次元配列パターンが得られる。従って、生成されるマルチステージ・インタリーブ・パターンは、０，６，３，９，１，７，４，１０，２，８，５，１１となる。
【００８５】
一方、前述の図１０に示す４進アップカウンタ１０−１及びＭＳＢ−ＬＳＢ操作回路１０−３から出力されるビットパターンは、図１１の（Ｄ）に示すとおりとなる。また、ＭＳＢ−ＬＳＢ操作回路１０−３の出力値に“３”を掛ける乗算器１０−４の出力は、図の（Ｅ）に示すとおりとなる。
【００８６】
更に、乗算器１０−４の出力値と、３進アップカウンタ１０−２のビット合わせ処理を行ったビット合わせ回路１０−５の出力値との加算を行う加算器１０−６の出力値は、図の（Ｆ）に示すとおりとなる。
【００８７】
加算器１０−６の出力値のパターンは、０，６，３，９，１，７，４，１０，２，８，５，１１となり、図１１の（Ｃ）に示す１２パターン長のマルチステージ・インタリーブ・パターンと合致する。
【００８８】
前述の１２パターン長のマルチステージ・インタリーブ・パターン生成器では、Ｋ＝４、Ｌ＝３とし、マルチステージ・インタリーブ・パターンを生成したが、一般に、整数Ｋ又はＬが更に約数を持ち、縦方向又は横方向にインタリーブが可能な場合の整数ｍ（ｍ＝Ｋ×Ｌ）のパターン長のマルチステージ・インタリーブ・パターン生成器は、以下のように構成される。
【００８９】
図１２は、このようなＫ×Ｌパターン長のマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。同図において、１２−１０はＫ進アップカウンタ、１２−１１はＭＳＢ−ＬＳＢ操作回路、１２−２０はＬ進アップカウンタ、１２−２１はＭＳＢ−ＬＳＢ操作回路、１２−３は乗算器、１２−４はビット合わせ回路、１２−５は加算器、１２−６はカウンタロード信号生成回路である。
【００９０】
Ｋ進アップカウンタ１２−１０とＭＳＢ−ＬＳＢ操作回路１２−１１とで、第１のマルチステージ・インタリーブ・パターン生成器を構成し、Ｌ進アップカウンタ１２−２０とＭＳＢ−ＬＳＢ操作回路１２−２１とで、第２のマルチステージ・インタリーブ・パターン生成器を構成している。
【００９１】
Ｌ進アップカウンタ１２−２０は、Ｋ進アップカウンタ１２−１０が出力するキャリー信号を受信してアップカウントする。ＭＳＢ−ＬＳＢ操作回路１２−１１，１２−２１は、整数Ｋ又はＬが２のべき乗であるときのみ、前述したような上位ビットと下位ビットとの入替え操作を行う。
【００９２】
乗算器１２−３は、ＭＳＢ−ＬＳＢ操作回路１２−１１から出力されるビットパターンに整数Ｌの値を乗算する。ビット合わせ回路１２−４は、ＭＳＢ−ＬＳＢ操作回路１２−２１から出力されるビットパターンのビット数を、乗算器１２−３から出力されるビットパターンのビット数に合わせるために、上位ビットに“０”を付け加える。
【００９３】
加算器１２−５は、乗算器１２−３から出力されるビットパターン値と、ビット合わせ回路１２−４から出力されるビットパターン値とを加算し、その加算値のビットパターンを、マルチステージ・インタリーブ・パターンとして出力する。
【００９４】
カウンタロード信号信号生成回路１２−６は、加算器１２−５から出力されるｍ（＝Ｋ×Ｌ）個のパターン数を計数し、計数終了後に、Ｋ進アップカウンタ１２−１０及びＬ進アップカウンタ１２−２０をリセットして計数動作を再開させるためのカウンタロード信号を生成する。
【００９５】
次に、前述したようなそれぞれが２のべき乗の約数を持つ整数の積である２０×１６パターン長のマルチステージ・インタリーブ・パターン発生器の構成例について説明する。このパターンは、２０パターン長のマルチステージ・インタリーブ・パターン発生部と、１６パターン長のマルチステージ・インタリーブ・パターン発生部との組合せにより発生させることができる。
【００９６】
２０×１６パターン長のマルチステージ・インタリーブ・パターンは、次の算出式により生成するものとする。式：３２０（２０（４（２×２）×５（３×２））×１６（４（２×２）×４（２×２）））
【００９７】
図１３は、上記の算出式による２０×１６パターン長のマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。同図において、１３−１０は２０パターン長のマルチステージ・インタリーブ・パターン発生部、１３−２０は１６パターン長のマルチステージ・インタリーブ・パターン発生部、１３−３０は乗算（×１６演算）器、１３−４０は加算器、１３−５０は出力回路である。
【００９８】
２０パターン長のマルチステージ・インタリーブ・パターン発生部１３−１０は、２０×１６のインタリーブ・パターンの縦方向である２０（４（２×２）×５（３×２））パターンについて、マルチステージ・インタリーブ・パターンを生成するもので、更に、その縦方向の４（２×２）パターンのマルチステージ・インタリーブ・パターン発生器１３−１１と、横方向の５（３×２）パターンのマルチステージ・インタリーブ・パターン発生器１３−１２と、乗算（×５演算）器１３−１３と、ビット合わせ回路１３−１４と、加算器１３−１５とにより構成される。
【００９９】
４パターン長のマルチステージ・インタリーブ・パターン発生器１３−１１は、４進カウンタとＭＳＢ−ＬＳＢビット操作回路とにより構成され、その出力結果は、０，２，１，４である。
【０１００】
５パターン長のマルチステージ・インタリーブ・パターン発生器１３−１２は、具体的回路については図１４を用いて説明するが、５パターン長のマルチステージ・インタリーブ・パターンを生成する。
【０１０１】
式：２０（４（２×２）×５（３×２））のマルチステージ・インタリーブを実際行うと、その結果は、０，１０，５，１５，２，１２，・・・であるため、４パターン長のマルチステージ・インタリーブ・パターン発生器１３−１１の出力値に対し、乗算（×５演算）器１３−１３により“５”（”１０１”  ）を乗算する。
【０１０２】
乗算（×５演算）器１３−１３は、入力ビットの上位に“０”を２ビット分付加する回路１３−１３ａと、入力ビットを２ビット分上位に移動し、その下位に“０”を２ビット分付加する回路１３−１３ｂと、それらの回路の出力を加算する加算器１３−１３ｃとにより構成され、入力ビットの値に“５”を乗算する。
【０１０３】
ビット合わせ回路１３−１４は、５パターン長のマルチステージ・インタリーブ・パターン発生器１３−１２からの３ビットの出力に、上位側に“０”を２ビット分付加し、乗算（×５演算）器１３−１３の出力ビット数に揃える。
【０１０４】
加算器１３−１５は、乗算（×５演算）器１３−１３の出力値と、ビット合わせ回路１３−１４の出力値とを加算し、加算器１３−１５から、２０パターン長のマルチステージ・インタリーブ・パターンを生成する。ここまでが式：２０（４（２×２）×５（３×２））によるマルチステージ・インタリーブ・パターンの生成処理となる。
【０１０５】
１６パターン長のマルチステージ・インタリーブ・パターン発生部１３−２０は、前述の２０×１６のインタリーブ・パターンの横方向である１６（４（２×２）×４（２×２））パターンについて、マルチステージ・インタリーブ・パターンを生成するもので、１６パターン長のマルチステージ・インタリーブ・パターン発生器１３−２１と、ビット合わせ回路１３−２２とから構成される。
【０１０６】
１６パターン長のマルチステージ・インタリーブ・パターン発生器１３−２１は、前述した実施の形態と同様に、１６進カウンタと、その上位側ビットと下位側ビットとを入替えるＭＳＢ−ＬＳＢビット操作回路とにより構成され、その出力結果は、０，８，４，１２，２，１０，・・・となる。
【０１０７】
ビット合わせ回路１３−２２は、１６パターン長のマルチステージ・インタリーブ・パターン発生器１３−２１の４ビットの出力に、上位側に“０”を５ビット分付加して９ビットの出力とし、加算器１３−４０の一方の入力に加える。
【０１０８】
式：３２０（２０（４（２×２）×５（３×２））×１６（４（２×２）×４（２×２）））のマルチステージ・インタリーブ・パターンを実際に算出すると、その結果は、０，１６０，８０，２４０，３２，１９２，・・・であるため、加算器１３−１５の出力値に対し、乗算（×１６演算）器１３−３０により、“１６”（”１００００”  ）を乗算する。
【０１０９】
乗算（×１６演算）器１３−３０は、２０パターン長のマルチステージ・インタリーブ・パターン発生部１３−１０の出力ビットを、４ビット上位に移し、その下位に“０”を４ビット分付加することにより、“１６”を乗算することができ、その乗算結果を加算器１３−４０の他方の入力に加える。
【０１１０】
加算器１３−４０は、乗算（×１６演算）器１３−３０の出力値と、ビット合わせ回路１３−２２の出力値とを加算し、加算器１３−４０から、２０×１６パターン長のマルチステージ・インタリーブ・パターンが生成される。
【０１１１】
図１４は、前述した５パターン長のマルチステージ・インタリーブ・パターン発生器１３−１２の構成例を示す。同図の（Ａ）において、１４−１は３進アップカウンタ、１４−２は２進アップカウンタ、１４−３は乗算（×２演算）器、１４−４はビット合わせ回路、１４−５は加算器、１４−６はカウンタロード信号生成回路である。
【０１１２】
３進アップカウンタ１４−１は、００  （０），０１  （１），１０  （２）のビットパターンを順次出力し、乗算（×２演算）器１４−３は、３進アップカウンタ１４−１の出力値に“２”を乗算し、０００  （０），０１０  （２），１００  （４）  のビットパターンを出力する。
【０１１３】
２進アップカウンタ１４−２は、３進アップカウンタ１４−１からキャリー信号が入力されると、“１”を出力する。ビット合わせ回路１４−４は、２進アップカウンタ１４−２の出力ビットの上位に、“０”を２ビット分付加し、０００，００１  のビットパターンを出力する。
【０１１４】
加算器１４−５は、乗算（×２演算）器１４−３の出力値とビット合わせ回路１４−４の出力値とを加算し、０００  （０），０１０  （２），１００  （４），００１  （１），０１１  （３）  のビットパターンを出力する。
【０１１５】
一方、５パターン長のインタリーブ・パターンを、式：５（３×２）により算出するものとすると、０〜４の順序パターンは、図１４の（Ｂ）に示すとおりとなり、矢印の右側の２次元配列の番号を縦方向に取り出すことにより、０，２，４，１，３のパターンが生成される。
【０１１６】
従って、図１４の（Ａ）に示すマルチステージ・インタリーブ・パターン発生器から生成されるパターンは、式：５（３×２）によるマルチステージ・インタリーブ・パターンと合致する。
【０１１７】
カウンタロード信号生成回路１４−６は、加算器１４−５から出力される５個のパターン数を計数し、計数終了後に、３進アップカウンタ１４−１及び２進アップカウンタ１４−２をリセットして計数動作を再開させるためのカウンタロード信号を生成する。
【０１１８】
図１５は、本発明のリバースパターン生成機能を有するマルチステージ・インタリーブ・パターン発生器の説明図である。このパターン発生器は図１５に示すようにカウントアップ及びカウントダウン部１５−１と、マルチステージ・インタリーブ・パターン発生部１５−２と、リバース判定部１５−３とから構成される。
【０１１９】
カウントアップ及びカウントダウン部１５−１は、カウントアップ及びカウントダウンの動作機能を備え、リバース判定部１５−３からの信号に応じてカウントアップ動作又はカウントダウン動作が切り替わり、昇順の順序パターン又は降順の順序パターンを生成する。
【０１２０】
マルチステージ・インタリーブ・パターン発生部１５−２は、カウントアップ及びカウントダウン部１５−１から出力されるビットパターンの、上位側ビットと下位側ビットとを互いに入替える操作を行う。
【０１２１】
リバース判定部１５−３は、リバース指示の設定がなされているか否かを判定し、リバース指示の設定がなされている場合に、カウントアップ及びカウントダウン部１５−１にカウントダウン動作の信号を出力する。
【０１２２】
この構成により、前述した正順のマルチステージ・インタリーブ・パターンのほかに、リバース指示の設定の設定により、順序が逆転したマルチステージ・インタリーブ・パターンを生成することができる。
【０１２３】
図１６は、８パターン長のリバースパターン生成機能を有するマルチステージ・インタリーブ・パターン発生器の構成例を示し、このマルチステージ・インタリーブ・パターン発生器は、８進のアップダウンカウンタ１６−１と、ＭＳＢ−ＬＳＢ操作回路１６−２と、リバース判定部１６−３とから構成される。
【０１２４】
８進のアップダウンカウンタ１６−１は、初期値として、アップカウント時には０００  （０）  が、ダウンカウント時には１１１  （７）  が設定される。ＭＳＢ−ＬＳＢ操作回路１６−２は、アップダウンカウンタ１６−１から出力される最上位ビットＭＳＢと、最下位ビットＬＳＢとを入替える操作を行う。
【０１２５】
アップダウンカウンタ１６−１は、ダウンカウント動作時に、１１１  （７），１１０  （６），１０１  （５），１００  （４），０１１  （３），０１０  （２），００１  （１），０００  （０）  のビットパターンを順次発生する。
【０１２６】
ＭＳＢ−ＬＳＢ操作回路１６−２は、上記のビットパターンの最上位ビットＭＳＢと最下位ビットＬＳＢとを入替え、１１１  （７），０１１  （３），１０１  （５），００１  （１），１１０  （６），０１０  （２），１００  （４），０００  （０）  のパターンを順次生成する。
【０１２７】
一方、リバースパターンのマルチステージ・インタリーブ・パターンを生成する演算式は、式：Ｒ｛８（２×４（２×２））｝と表され、ここで、Ｒ｛  ｝は、｛  ｝内の算出式により生成したマルチステージ・インタリーブ・パターンを、逆の順序に入替える操作を意味する。
【０１２８】
式：８（２×４（２×２））によるマルチステージ・インタリーブ・パターンは、図２において説明したように、０，４，２，６，１，５，３，７となる。このパターンの順序を逆にしてえられるリバースパターンは、７，３，５，１，６，２，４，０となり、ＭＳＢ−ＬＳＢ操作回路１６−２から出力されるパターンと合致する。よって、ＭＳＢ−ＬＳＢ操作回路１６−２の出力が８パターンのマルチステージ・インタリーブ・パターンのリバースパターンである。
【０１２９】
【発明の効果】
以上説明したように、本発明によれば、複雑なマルチステージ・インタリーブ・パターンを、カウンタとビット入替え操作回路等のロジック回路により生成するため、従来のように大容量のメモリを使用したり、プロセッサによる処理を行ったりすることがないので、マルチステージ・インタリーブ・パターン生成器のＬＳＩ回路、パッケージボード等の小型化、高密度化及び低消費電力化を図ることができ、また、複雑なマルチステージ・インタリーブ・パターンを高速に生成することができる。
【図面の簡単な説明】
【図１】本発明のマルチステージ・インタリーブ・パターン発生器の基本構成の説明図である。
【図２】８（２×４（２×２））及び８（４（２×２）×２）のマルチステージ・インタリーブの説明図である。
【図３】本発明の基本パターンの２倍長のマルチステージ・インタリーブ・パターン生成器の説明図である。
【図４】１６パターン長のマルチステージ・インタリーブ・パターンの説明図である。
【図５】本発明の１６パターン長のマルチステージ・インタリーブ・パターン発生器の第２の構成例の説明図である。
【図６】本発明の３２パターン長のマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。
【図７】３２パターン長のマルチステージ・インタリーブ・パターンの説明図である。
【図８】本発明の２べき乗のパターン長のマルチステージ・インタリーブ・パターン発生器の説明図である。
【図９】本発明の任意の整数の積のパターン長のマルチステージ・インタリーブ・パターン生成器の説明図である。
【図１０】本発明の１２パターン長のマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。
【図１１】１２パターン長のマルチステージ・インタリーブ・パターンの説明図である。
【図１２】本発明のＫ×Ｌパターンのマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。
【図１３】本発明の２０×１６パターン長のマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。
【図１４】本発明における５パターン長のマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。
【図１５】本発明のリバースパターン生成機能を有するマルチステージ・インタリーブ・パターン発生器の説明図である。
【図１６】本発明の８パターン長のリバースパターン生成機能を有するマルチステージ・インタリーブ・パターン発生器の構成例の説明図である。
【図１７】従来のマルチステージ・インタリーブ・パターン生成器の説明図である。
【符号の説明】
１−１  カウントアップ部
１−２  マルチステージ・インタリーブ・パターン生成部
【図１】
0003593647.tif 000002
【図２】
0003593647.tif 000003
【図３】
0003593647.tif 000004
【図４】
0003593647.tif 000005
【図５】
0003593647.tif 000006
【図６】
0003593647.tif 000007
【図７】
0003593647.tif 000008
【図８】
0003593647.tif 000009
【図９】
0003593647.tif 000010
【図１０】
0003593647.tif 000011
【図１１】
0003593647.tif 000012
【図１２】
0003593647.tif 000013
【図１３】
0003593647.tif 000014
【図１４】
0003593647.tif 000015
【図１５】
0003593647.tif 000016
【図１６】
0003593647.tif 000017
【図１７】
0003593647.tif 000018