(57)【特許請求の範囲】
【請求項１】
情報部とパリティ部によって形成されたＩＲＡ符号のパリティ検査行列のうち、情報部では、固定サイズの単位行列あるいは単位行列の巡回シフト行列によって構成されるブロックが行方向および列方向に複数配置されており、情報部の一行に含まれる要素数の情報ビットをビット列として入力する入力部と、
前記入力部において入力したビット列に対して、ブロック中の一行に含まれる要素数単位への分割を実行するとともに、分割した要素数単位にビット列の一部分を記憶する複数の記憶部と、
前記複数の記憶部のそれぞれは、情報部に配置されたブロックの列のそれぞれと１対１で対応づけられており、前記複数の記憶部のそれぞれに記憶したビット列の一部分から、対応づけられたブロックにおける単位行列の巡回的シフト量に応じた順番の情報ビットを、情報部の行単位に順次抽出する抽出部と、
前記抽出部において順次抽出した情報ビットを加算することによって、パリティを生成する生成部と、
を備えることを特徴とする符号化装置。
【請求項２】
情報部とパリティ部によって形成されたＩＲＡ符号のパリティ検査行列のうち、情報部では、固定サイズの単位行列あるいは単位行列の巡回シフト行列によって構成されるブロックが行方向および列方向に複数配置されており、情報部の一行に含まれる要素数の情報ビットをビット列として入力するステップと、
入力したビット列に対して、ブロック中の一行に含まれる要素数単位への分割を実行するとともに、分割した要素数単位にビット列の一部分を複数の記憶部に記憶するステップと、
前記複数の記憶部のそれぞれは、情報部に配置されたブロックの列のそれぞれと１対１で対応づけられており、前記複数の記憶部のそれぞれに記憶したビット列の一部分から、対応づけられたブロックにおける単位行列の巡回的シフト量に応じた順番の情報ビットを、情報部の行単位に順次抽出するステップと、
順次抽出した情報ビットを加算することによって、パリティを生成するステップと、
を備えることを特徴とする符号化方法。
【請求項３】
情報部とパリティ部によって形成されたＩＲＡ符号のパリティ検査行列のうち、情報部では、固定サイズの単位行列あるいは単位行列の巡回シフト行列によって構成されるブロックが行方向および列方向に複数配置されており、情報部の一行に含まれる要素数の情報ビットをビット列として入力するステップと、
入力したビット列に対して、ブロック中の一行に含まれる要素数単位への分割を実行するとともに、分割した要素数単位にビット列の一部分を複数の記憶部に記憶するステップと、
前記複数の記憶部のそれぞれは、情報部に配置されたブロックの列のそれぞれと１対１で対応づけられており、前記複数の記憶部のそれぞれに記憶したビット列の一部分から、対応づけられたブロックにおける単位行列の巡回的シフト量に応じた順番の情報ビットを、情報部の行単位に順次抽出するステップと、
順次抽出した情報ビットを加算することによって、パリティを生成するステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化技術に関し、特にＬＤＰＣによる符号化を実行する符号化装置に関する。
【背景技術】
【０００２】
近年、低Ｓ／Ｎの伝送路でも強力な誤り訂正能力をもつ誤り訂正符号として、ＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅ）が注目され、多くの分野で適用されている。ＬＤＰＣでは、送信側において、疎な検査行列をもとに生成される符号化行列によって、データが符号化される。ここで、疎な検査行列とは、要素が１または０からなる行列であって、１の数が少ない行列である。一方、受信側において、検査行列をもとにして、データの復号とパリティ検査とがなされる。特に、ＢＰ（Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）法等による繰り返し復号によって復号性能が向上する。
【０００３】
このようなＬＤＰＣにおいて、符号化が容易な検査行列の使用が望まれる。そのために、ＩＲＡ（Ｉｒｒｅｇｕｌａｒ  Ｒｅｐｅａｔ  Ａｃｃｕｍｕｌａｔｅ）型準巡回符号が使用される。ＩＲＡ型準巡回符号とは、準巡回符号の検査行列とＩＲＡ符号の検査行列の両方の性質を有する検査行列をもつ線形符号である。このような符号の検査行列を使用することによって、情報ビット長のシフトレジスタに一時保管した情報ビットをクロックで巡回させながら符号化がなされる（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−２５２８２０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
準巡回符号の検査行列の部分が、複数の巡回正方行列にて生成されており、各巡回正方行列の各行における非零要素の数が異なれば、巡回正方行列の一行ごとに加算を実行する場合であっても、最大の非零要素の数に応じて加算回数が増加する。そのため、加算器の使用頻度にかかわらず、最大の非零要素の数に応じた加算器が必要になる。その結果、回路の使用効率が悪化する。一方、高速なデータ伝送に対応するために、パリティ生成の高速化が望まれる。これに対応するためには、使用効率の高い簡易な回路構成が望ましい。
【０００６】
本発明はこうした状況に鑑みてなされたものであり、その目的は、簡易な回路構成にて高速にパリティを生成する技術を提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明のある態様の符号化装置は、情報部とパリティ部によって形成されたＩＲＡ符号のパリティ検査行列のうち、情報部では、固定サイズの単位行列あるいは単位行列の巡回シフト行列によって構成されるブロックが行方向および列方向に複数配置されており、情報部の一行に含まれる要素数の情報ビットをビット列として入力する入力部と、入力部において入力したビット列に対して、ブロック中の一行に含まれる要素数単位への分割を実行するとともに、分割した要素数単位にビット列の一部分を記憶する複数の記憶部と、複数の記憶部のそれぞれは、情報部に配置されたブロックの列のそれぞれと１対１で対応づけられており、複数の記憶部のそれぞれに記憶したビット列の一部分から、対応づけられたブロックにおける単位行列の巡回的シフト量に応じた順番の情報ビットを、情報部の行単位に順次抽出する抽出部と、抽出部において順次抽出した情報ビットを加算することによって、パリティを生成する生成部と、を備える。
本発明の別の態様は、符号化方法である。この方法は、情報部とパリティ部によって形成されたＩＲＡ符号のパリティ検査行列のうち、情報部では、固定サイズの単位行列あるいは単位行列の巡回シフト行列によって構成されるブロックが行方向および列方向に複数配置されており、情報部の一行に含まれる要素数の情報ビットをビット列として入力するステップと、入力したビット列に対して、ブロック中の一行に含まれる要素数単位への分割を実行するとともに、分割した要素数単位にビット列の一部分を複数の記憶部に記憶するステップと、複数の記憶部のそれぞれは、情報部に配置されたブロックの列のそれぞれと１対１で対応づけられており、複数の記憶部のそれぞれに記憶したビット列の一部分から、対応づけられたブロックにおける単位行列の巡回的シフト量に応じた順番の情報ビットを、情報部の行単位に順次抽出するステップと、順次抽出した情報ビットを加算することによって、パリティを生成するステップと、を備える。
【００１０】
この態様によると、情報部では、固定サイズの単位行列あるいは単位行列の巡回シフト行列によって構成されるブロックが行方向および列方向に複数配置されているので、ブロックにおける単位行列の巡回的シフト量に応じた順番の情報ビットを抽出することが容易になるので、簡易な回路構成によってパリティを生成できる。
【００１１】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１２】
本発明によれば、簡易な回路構成にて高速にパリティを生成できる。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施例１に係る通信システムの構成を示す図である。
【図２】図１のＬＤＰＣ符号化部において使用される検査行列を示す図である。
【図３】図２の単位行列を示す図である。
【図４】図２の単位行列の巡回シフト行列を示す図である。
【図５】図２の検査行列の詳細を示す図である。
【図６】図１のＬＤＰＣ符号化部における演算の概要を示す図である。
【図７】図１のＬＤＰＣ符号化部から出力される符号化データを示す図である。
【図８】図１のＬＤＰＣ符号化部の構成を示す図である。
【図９】図９（ａ）−（ｅ）は、図８のメモリとレジスタにおけるビットパターンを示す図である。
【図１０】図８のアドレス生成部に記憶されたテーブルのデータ構造を示す図である。
【図１１】図８のパリティ演算生成部の回路構成例を示す図である。
【図１２】図１のＬＤＰＣ符号化部における符号化手順を示すフローチャートである。
【図１３】図１２の符号化手順を詳細に示したフローチャートである。
【図１４】本発明の実施例２に係るＬＤＰＣ符号化部の構成を示す図である。
【図１５】図１４のタイミング生成部から出力される信号を示す図である。
【図１６】図１４のシフト量テーブルのデータ構造を示す図である。
【図１７】図１７（ａ）−（ｆ）は、図１４のメモリとシフトレジスタにおけるビットパターンを示す図である。
【図１８】図１４のＬＤＰＣ符号化部における符号化手順を示すフローチャートである。
【発明を実施するための形態】
【００１４】
（実施例１）
本発明を具体的に説明する前に、まず概要を述べる。本発明の実施例１は、ＬＤＰＣ符号化を実行する送信装置と、送信装置において符号化されたデータ（以下、「符号化データ」という）に対して検査行列をもとに繰り返し復号を実行する受信装置とを含む通信システムに関する。前述のごとく、送信装置には、使用効率の高い簡易な回路構成にて高速にパリティを生成することが望まれる。これに対応するために、本実施例に係る通信システム、特に送信装置は、次のように構成される。
【００１５】
送信装置において使用される検査行列であって、かつパリティを作成するための検査行列は、情報ビットに対応した情報部と、パリティに対応したパリティ部とから構成されている。ここで、情報ビットとは、送信すべき情報に相当する。また、情報部は、次元ｐの単位行列あるいは単位行列を巡回させた巡回行列とを基本行列とし、行方向に基本行列をｊ、列方向に基本行列ｋ（ｊ、ｋは自然数）配置することによって構成されている。また、パリティ部はｐ×ｊ次の正方行列であって、行列要素に階段状に「１」を配置する。その際、ひとつの行にふたつの「１」が配置される。
【００１６】
このような検査行列を使用するために、送信装置は、情報ビットを記憶するために、ｐビット長のビットメモリをｋ個具備するとともに、各ビットメモリにｐ×ｐビットのレジスタを配置させる。ここで、レジスタは、ビットメモリの内容を基本行列の要素に対応して記憶する。また、送信装置は、レジスタの選択情報をもとに、レジスタの内容からパリティを生成する。基本行列の各行には、ひとつの「１」の要素が配置されているだけなので、レジスタの選択情報では、「１」の要素を対応した値を抽出するだけであり、各基本行列からひとつずつ抽出した値を加算することでパリティが生成されるので、使用効率の高い簡易な回路構成にてパリティが生成される。
【００１７】
図１は、本発明の実施例１に係る通信システム１００の構成を示す。通信システム１００は、送信装置１０、受信装置１２を含む。送信装置１０は、情報データ生成部２０、ＬＤＰＣ符号化部２２、変調部２４を含む。受信装置１２は、復調部２６、復号部２８、情報データ出力部３０を含む。
【００１８】
情報データ生成部２０は、送信すべきデータを取得し、情報データを生成する。例えば、ＣＲＣ（Ｃｙｃｌｉｃ  Ｒｅｄｕｎｄａｎｃｙ  Ｃｈｅｃｋ）ビットが付加される。なお、取得したデータがそのまま情報データとされてもよい。情報データは、符号化の対象となるビット列といえる。情報データ生成部２０は、情報データをＬＤＰＣ符号化部２２へ出力する。ＬＤＰＣ符号化部２２は、情報データ生成部２０から、情報データを入力する。ＬＤＰＣ符号化部２２は、ＬＤＰＣでの検査行列をもとにしたパリティを情報データに付加する。パリティを付加した情報データが、前述の符号化データに相当する。つまり、ＬＤＰＣ符号化部２２は、入力したビット列に対して、検査行列を演算することによって、ビット列を符号化する。ＬＤＰＣ符号化部２２は、符号化データを変調部２４に出力する。
【００１９】
図２は、ＬＤＰＣ符号化部２２において使用される検査行列を示す。図示のごとく、これは、情報部２３０とパリティ部２３２によって形成されたＩＲＡ符号のパリティ検査行列である。ＩＲＡ符号のパリティ検査行列のパリティ部２３２は、階段状に非零元「１」を配置させている。より具体的に説明すると、パリティ部２３２は、右端の列以外の列において、列重み２の階段状に「１」を配置する。一方、情報部２３０では、固定サイズの単位行列あるいは単位行列の巡回シフト行列α、α２等によって構成されるブロックが基本行列として規定されている。また、情報部２３０は、複数の基本行列を行方向および列方向に配置する。このような情報部２３０の構成は、アレー符号のパリティ検査行列に相当する。情報部２３０において、基本行列が配置される行数をｊとし、列数をｋとすると、図２では、ｊ＝３、ｋ＝５となっている。また、基本行列をｐ行ｐ列と示すと、パリティ部２３２は、ｐ×ｊ次の正方行列の構成と示される。ここで、ｊ、ｋ、ｐの数値は、符号化する情報ビット数に応じて任意の数値に設定される。
【００２０】
図３は、単位行列を示す。これは、図２の「Ｉ」と示された基本行列に相当する。また、Ｉは、α０に相当する。図４は、単位行列の巡回シフト行列を示す。これは、図２の「α」と示された基本行列に相当する。図示のごとく、行列αは、単位行列Ｉを１だけ右巡回させた行列に相当する。図２において、α２、α３、α４は、単位行列Ｉを２、３、４だけ右巡回させた行列に相当する。図５は、検査行列の詳細を示す。これは、図２に示された検査行列の基本行列に対して、図３、図４に示された基本行列を組み合わせた構成に相当する。前述のごとく、検査行列は、このように巡回させて生成される基本行列からなる情報部２３０と、階段状に「１」を配置したｐ×ｊ次の正方行列からなるパリティ部２３２とによって構成される。なお、情報部２３０に対応づけるべき情報データの各ビットは、「ｂ０」から「ｂ２４」と示され、生成されるパリティの各ビットは、「ｐ０」から「ｐ１４」と示される。
【００２１】
図６は、ＬＤＰＣ符号化部２２における演算の概要を示す。検査行列における「１」に対応したビットを加算することによって、パリティのビットが計算される。つまり、情報データのビットｂ０からｂ２４までの２５ビットをもとに、パリティのビットｐ０からｐ１４までの１５ビットが計算される。図７は、ＬＤＰＣ符号化部２２から出力される符号化データを示す。図示のごとく、符号化データは、ビット「ｂ０」から「ｂ（ｋｐ−１）」までの情報データと、ビット「ｐ０」から「ｐ（ｊｐ−１）」までのパリティによって構成されている。図１に戻る。
【００２２】
変調部２４は、ＬＤＰＣ符号化部２２から符号化データを入力する。変調部２４は、符号化データを変調する。変調方式として、ＰＳＫ（Ｐｈａｓｅ  Ｓｈｉｆｔ  Ｋｅｙｉｎｇ）、ＦＳＫ（Ｆｒｅｑｕｅｎｃｙ  Ｓｈｉｆｔ  Ｋｅｙｉｎｇ）等が使用される。変調部２４は、変調した符号化データを変調信号として送信する。復調部２６は、変調部２４から通信路、例えば無線伝送路を介して変調信号を受信する。復調部２６は、変調信号を復調する。復調には公知の技術が使用されればよいので、ここでは説明を省略する。復調部２６は、復調結果（以下、「復調データ」という）を復号部２８へ出力する。
【００２３】
復号部２８は、復調部２６からの復調データを入力する。復号部２８は、復調データに対して、ＬＤＣＰでの検査行列による復号処理を繰り返し実行する。復号処理として、例えば、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムが実行される。ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムは、次の手順で実行される。
１．初期化：事前値比を初期化し、最大復号繰り返し回数を設定する。
２．チェックノード処理：検査行列の行方向に対して外部値比を更新する。
３．変数ノード処理：検査行列の列方向に対して事前値比を更新する。
４．一時推定語を計算する。
さらに、チェックノード処理と変数ノード処理とが繰り返し実行される。また、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムでは、チェックノード処理において、Ｇａｌｌａｇｅｒ関数や双曲線関数が使用される。また、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムでは、伝送路ノイズの分散値から求まる通信路値を事前値として使用する。
【００２４】
ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムを簡略化した復号方法が、ｍｉｎ−ｓｕｍアルゴリズムであり、復号部２８は、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの代わりにｍｉｎ−ｓｕｍアルゴリズムを使用してもよい。ｍｉｎ−ｓｕｍアルゴリズムは、複雑な関数を用いることなく、比較演算、和演算等の簡単な処理だけでチェックノード処理を行うことが可能である。さらに、ｍｉｎ−ｓｕｍアルゴリズムは、通信路値を必要としないので、処理の簡略化、高速化のために広く用いられている。
【００２５】
復号部２８は、復号結果（以下、「復号データ」という）を情報データ出力部３０へ出力する。情報データ出力部３０は、復号部２８からの復号データを入力する。情報データ出力部３０は、復号データをもとに情報データを生成する。なお、復号データがそのまま情報データとされてもよい。情報データ出力部３０は、外符号復号部を含み、例えばＣＲＣ等の外符号を復号してもよい。
【００２６】
この構成は、ハードウエア的には、任意のコンピュータのＣＰＵ、メモリ、その他のＬＳＩで実現でき、ソフトウエア的にはメモリにロードされたプログラムなどによって実現されるが、ここではそれらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者には理解されるところである。
【００２７】
図８は、ＬＤＰＣ符号化部２２の構成を示す。ＬＤＰＣ符号化部２２は、メモリ４０と総称される第１メモリ４０ａ、第２メモリ４０ｂ、第３メモリ４０ｃ、第４メモリ４０ｄ、第５メモリ４０ｅ、レジスタ４２と総称される第１レジスタ４２ａ、第２レジスタ４２ｂ、第３レジスタ４２ｃ、第４レジスタ４２ｄ、第５レジスタ４２ｅ、パリティ演算生成部４４、タイミング制御部４６、アドレス生成部４８、符号語構成部５０を含む。
【００２８】
メモリ４０は、図２に示された検査行列における情報部２３０中の基本行列の列数ｋだけ備えられる。本実施例では、ｋ＝５であるので、第１メモリ４０ａから第５メモリ４０ｅまでの５つのメモリ４０が、情報部２３０における行方向の基本行列のそれぞれに１対１で対応するように配置される。また、各メモリ４０は、基本行列の列数に応じたサイズを有する。本実施例は、基本行列の列数は、５であるので、各メモリ４０は、５ビットのデータを記憶する。つまり、５つのメモリ４０は、情報部２３０の一行に含まれる要素数の情報ビットをビット列として入力する。ここで、情報ビットは、情報データに含まれた各ビットを示す。また、５つのメモリ４０は、入力したビット列に対して、ブロック中の一行に含まれる要素数単位への分割を実行するとともに、分割した要素数単位にビット列の一部分を記憶する。
【００２９】
レジスタ４２は、メモリ４０と１対１で接続される。そのため、第１レジスタ４２ａから第５レジスタ４２ｅが、第１メモリ４０ａから第５メモリ４０ｅのそれぞれに対応するように備えられる。図９（ａ）−（ｅ）は、メモリ４０とレジスタ４２におけるビットパターンを示す図である。図９（ａ）の上段が第１メモリ４０ａに記憶されるビットパターンを示し、下段が第１レジスタ４２ａに記憶されるビットパターンを示す。図９（ｂ）の上段が第２メモリ４０ｂに記憶されるビットパターンを示し、下段が第２レジスタ４２ｂに記憶されるビットパターンを示す。図９（ｃ）の上段が第３メモリ４０ｃに記憶されるビットパターンを示し、下段が第３レジスタ４２ｃに記憶されるビットパターンを示す。図９（ｄ）の上段が第４メモリ４０ｄに記憶されるビットパターンを示し、下段が第４レジスタ４２ｄに記憶されるビットパターンを示す。図９（ｅ）の上段が第５メモリ４０ｅに記憶されるビットパターンを示し、下段が第５レジスタ４２ｅに記憶されるビットパターンを示す。
【００３０】
図９（ａ）−（ｅ）の上段のさらに上に示された記号が、各メモリ４０に記憶される情報ビットを示す。例えば、第１メモリ４０ａには、情報ビットｂ０からｂ４の５ビットが記憶され、第２メモリ４０ｂには、ｂ５からｂ９の５ビットが記憶され、第３メモリ４０ｃには、ｂ１０からｂ１４の５ビットが記憶され、第４メモリ４０ｄには、ｂ１５からｂ１９の５ビットが記憶され、第５メモリ４０ｅには、ｂ２０からｂ２４の５ビットが記憶される。以下では、説明を明瞭にするために、各メモリ４０に記憶されるビットを先頭から順に「ｂ０」から「ｂ４」と示す。
【００３１】
図９（ａ）に示されるように、第１メモリ４０ａに接続される第１レジスタ４２ａは、５種類のビットパターンを記憶可能である。ここでは、すべてのビットパターンに対してアドレス０が付与され、アドレス０に対して、上位から第１メモリ４０ａに記憶されているビットパターンｂ０、ｂ１、ｂ２、ｂ３、ｂ４が格納される。第２メモリ４０ｂから第５メモリ４０ｅに接続される第２レジスタ４２ｂから第５レジスタ４２ｅにはそれぞれアドレス０から４が付与される。アドレス０にはｂ０、ｂ１、ｂ２、ｂ３、ｂ４が、アドレス１にはｂ１、ｂ２、ｂ３、ｂ４、ｂ０が、アドレス２にはｂ２、ｂ３、ｂ４、ｂ０、ｂ１が、アドレス３にはｂ３、ｂ４、ｂ０、ｂ１、ｂ２が、アドレス４にはｂ４、ｂ０、ｂ１、ｂ２、ｂ３が格納される。図８に戻る。
【００３２】
タイミング制御部４６は、図２に示された検査行列における情報部２３０中の基本行列の行数ｊまでカウントするようなタイミングを生成する。本実施例では、ｊ＝３であるので、タイミング制御部４６は、０、１、２というタイミングを繰り返し生成する。タイミング制御部４６は、生成したタイミングをアドレス生成部４８へ出力する。アドレス生成部４８は、タイミング制御部４６からのタイミングを入力する。アドレス生成部４８は、入力したタイミングをもとに、レジスタ４２から出力するすべきアドレスを生成する。アドレス生成部４８は、生成したアドレスをパリティ演算生成部４４へ出力する。
【００３３】
図１０は、アドレス生成部４８に記憶されたテーブルのデータ構造を示す。テーブルは、タイミング制御部出力欄２００、アドレス生成部出力欄２０２を含む。タイミング制御部出力欄２００は、タイミング制御部４６からのタイミングに対応するように、「０」から「２」を示す。アドレス生成部出力欄２０２には、各タイミングに対応したアドレスを示す。そのため、タイミング「１」の場合に、アドレス「０」、「１」、「２」、「３」、「４」が出力される。ここで、５つのアドレスは、第１レジスタ４２ａから第５レジスタ４２ｅに順に対応する。図８に戻る。
【００３４】
図１１は、パリティ演算生成部４４の回路構成例を示す。パリティ演算生成部４４は、ラッチレジスタ８０、ＥＸ−ＯＲ演算部８２と総称される第１ＥＸ−ＯＲ演算部８２ａ、第２ＥＸ−ＯＲ演算部８２ｂ、第３ＥＸ−ＯＲ演算部８２ｃ、第４ＥＸ−ＯＲ演算部８２ｄ、第５ＥＸ−ＯＲ演算部８２ｅを含む。図１１に示す通りパリティ演算生成部４４において、複数のＥＸ−ＯＲ演算部８２は、レジスタ４２にセットされたデータに対して単位行列の次元数であるｐビット分のパリティビットを同時に演算する。ラッチレジスタ８０は、パリティ演算生成部４４に最初のデータがセットされるタイミングではゼロクリアを行い、ゼロデータを出力する。パリティ演算生成部４４に２回目移行のデータがセットされるタイミングでは、その時の最上位パリティビットの演算結果をラッチ（保持）して出力する。上記処理を繰り返し行うことで高速にパリティビットの演算が可能となる。
【００３５】
具体的にはパリティ演算生成部４４は、アドレス生成部４８から、アドレスを入力し、アドレスに対応した情報ビットをレジスタ４２から抽出する。パリティ演算生成部４４は、抽出した情報ビットを加算することによって、パリティのビットを生成する。まず始めに、タイミング０の場合に、アドレスは、０００００と示されているので、すべてのレジスタ４２は、アドレス０に含まれた情報ビットを出力する。つまり、図９（ａ）−（ｅ）に示されたように、各レジスタ４２は、ｂ０、ｂ１、ｂ２、ｂ３、ｂ４を出力する。これにより次の演算がなされる。
ｐ０＝ｂ０＋ｂ０＋ｂ０＋ｂ０＋ｂ０＋０
ｐ１＝ｂ１＋ｂ１＋ｂ１＋ｂ１＋ｂ１＋ｐ０
ｐ２＝ｂ２＋ｂ２＋ｂ２＋ｂ２＋ｂ２＋ｐ１
ｐ３＝ｂ３＋ｂ３＋ｂ３＋ｂ３＋ｂ３＋ｐ２
ｐ４＝ｂ４＋ｂ４＋ｂ４＋ｂ４＋ｂ４＋ｐ３
ここで、ｐ０からｐ４はパリティのビットである。
【００３６】
続いて、タイミング１の場合に、アドレスは、０１２３４と示されているので、第１レジスタ４２ａは、アドレス０に含まれた情報ビットを出力し、第２レジスタ４２ｂは、アドレス１に含まれた情報ビットを出力し、第３レジスタ４２ｃは、アドレス２に含まれた情報ビットを出力し、第４レジスタ４２ｄは、アドレス３に含まれた情報ビットを出力し、第５レジスタ４２ｅは、アドレス４に含まれた情報ビットを出力する。これにより次の演算がなされる。
ｐ５＝ｂ０＋ｂ１＋ｂ２＋ｂ３＋ｂ４＋ｐ４
ｐ６＝ｂ１＋ｂ２＋ｂ３＋ｂ４＋ｂ０＋ｐ５
ｐ７＝ｂ２＋ｂ３＋ｂ４＋ｂ０＋ｂ１＋ｐ６
ｐ８＝ｂ３＋ｂ４＋ｂ０＋ｂ１＋ｂ２＋ｐ７
ｐ９＝ｂ４＋ｂ０＋ｂ１＋ｂ２＋ｂ３＋ｐ８
続いて、タイミング２の場合も同様の演算がなされることによって、パリティのビットｐ１０からｐ１４が生成される。これらのパリティ演算生成部４４での演算は、図６に示したとおりである。
【００３７】
つまり、パリティ演算生成部４４は、複数のレジスタ４２のそれぞれに記憶したビット列の一部分から、対応づけられた基本行列における単位行列の巡回的シフト量に応じた順番の情報ビットを、情報部２３０の行単位に順次抽出する。これに続いて、パリティ演算生成部４４は、順次抽出した情報ビットを加算することによって、パリティを生成する。パリティ演算生成部４４は、情報データおよびパリティを符号語構成部５０へ出力する。符号語構成部５０は、パリティ演算生成部４４からの情報データおよびパリティを入力する。符号語構成部５０は、図７のごとく、情報データおよびパリティを組み合わせることによって、符号語を生成する。符号語構成部５０は、符号語を符号化データとして出力する。
【００３８】
以上の構成による通信システム１００の動作を説明する。図１２は、ＬＤＰＣ符号化部２２における符号化手順を示すフローチャートである。ＬＤＰＣ符号化部２２は、単位行列と、単位行列を巡回させた巡回行列で構成された情報部を読み込む（Ｓ１０）。ＬＤＰＣ符号化部２２は、階段状に「１」を配置したパリティ部を読み込む（Ｓ１２）。メモリ４０は、情報ビットを読み込む（Ｓ１４）。パリティ演算生成部４４は、メモリ４０に蓄えられた情報ビットと、検査行列をもとにしてパリティを生成する（Ｓ１６）。符号語構成部５０は、情報ビットと、生成されたパリティから符号語を生成し（Ｓ１８）、符号語を出力する（Ｓ２０）。
【００３９】
図１３は、図１２の符号化手順を詳細に示したフローチャートである。メモリ４０は、情報ビットを記憶する（Ｓ３０）。レジスタ４２は、メモリ４０からビットパターンを記憶する（Ｓ３２）。パリティ演算生成部４４は、ｃｏｕｎｔを１に設定する（Ｓ３４）。パリティ演算生成部４４は、アドレス生成部４８からレジスタアドレスを読み込み、パリティを演算する（Ｓ３６）。ｃｏｕｎｔがｊでなければ（Ｓ３８のＮ）、パリティ演算生成部４４は、ｃｏｕｎｔに１を加算し（Ｓ４０）、ステップ３６に戻る。ｃｏｕｎｔがｊであれば（Ｓ３８のＹ）、パリティ演算生成部４４は、パリティを符号語構成部５０に出力し、符号語構成部５０は、情報データとパリティとを併せて符号語を生成する（Ｓ４２）。符号語構成部５０は、符号語を出力する（Ｓ４４）。
【００４０】
本発明の実施例によれば、検査行列は、情報部とパリティ部とによって形成されたＩＲＡ符号のパリティ検査行列であり、かつ情報部は、アレー符号のパリティ検査行列であるので、並列して情報ビットを抽出できる。また、並列して情報ビットが抽出されるので、簡易な回路構成によってパリティを生成できる。また、情報部では、固定サイズの単位行列あるいは単位行列の巡回シフト行列によって構成される基本行列が行方向および列方向に複数配置されているので、単位行列の巡回的シフト量に応じた順番の情報ビットを容易に抽出できる。また、情報ビットが容易に抽出されるので、簡易な回路構成によってパリティを生成できる。また、簡易な回路構成なので、パリティの生成を実時間で高速に生成できる。また、クロックに同期してパリティ演算を行う場合、基本行列の行数ｊ回の演算によってパリティを生成できる。また、単位行列を基本行列とした巡回行列によって情報部が構成されているので、構成を簡易にできる。
【００４１】
（実施例２）
次に、本発明の実施例２を説明する。実施例２は、実施例１と同様に、使用効率の高い簡易な回路構成にて高速にパリティを生成するための送信装置に関する。実施例１では、レジスタにおけるアドレスを制御することによって、検査行列に対応した演算を実現している。一方、実施例２では、情報ビットをビットシフトさせることによって、検査行列に対応した演算を実現する。送信装置は、情報ビットを記憶するために、ｐビット長のビットメモリをｋ個具備するとともに、各ビットメモリにｐビット長のシフトレジスタを配置させる。また、送信装置は、シフトレジスタのシフト量を制御し、シフト量に応じてビットシフトを行いながら、シフトレジスタの内容からパリティを生成する。
【００４２】
図１４は、本発明の実施例２に係るＬＤＰＣ符号化部２２の構成を示す。ＬＤＰＣ符号化部２２は、メモリ４０と総称される第１メモリ４０ａ、第２メモリ４０ｂ、第３メモリ４０ｃ、第４メモリ４０ｄ、第５メモリ４０ｅ、シフトレジスタ６０と総称される第１シフトレジスタ６０ａ、第２シフトレジスタ６０ｂ、第３シフトレジスタ６０ｃ、第４シフトレジスタ６０ｄ、第５シフトレジスタ６０ｅ、パリティ演算生成部６２、タイミング生成部６４、シフトレジスタ制御部６６、シフト量テーブル６８、符号語構成部５０を含む。
【００４３】
タイミング生成部６４は、ＬＤＰＣ符号化部２２を動作させるためのタイミングを生成する。図１５は、タイミング生成部６４から出力される信号を示す。タイミング生成部出力欄２１０には、タイミング生成部６４から出力されるタイミングを示す。図示のごとく、タイミング生成部６４は、０から６のタイミングを順に出力する。また、各タイミングにおけるＬＤＰＣ符号化部２２の処理内容は、処理内容欄２１２に示される。図１４に戻る。タイミング生成部６４は、タイミングをシフトレジスタ制御部６６へ出力する。
【００４４】
シフト量テーブル６８は、タイミング生成部６４から出力されるタイミングに対応したシフトレジスタ６０でのシフト量を記憶する。図１６は、シフト量テーブル６８のデータ構造を示す。図示のごとく、シフト量テーブル６８は、タイミング生成部出力欄２２０、シフトレジスタ番号欄２２２を含む。タイミング生成部出力欄２２０は、タイミング生成部６４から出力されるタイミングを示す。シフトレジスタ番号欄２２２は、各シフトレジスタ６０のシフト量を示す。当該テーブルは、情報部２３０における基本行列の配列に合わせて、最上段の行に設定する基本行列に対するビットシフト量として、単位行列からの巡回量を示す。その下の行に設定する基本行列に対するビットシフト量として、ひとつ上段の基本行列からの巡回量を示す。
【００４５】
例えば、図２の情報部２３０の５列目は、単位行列Ｉ、行列α４、行列α８へと遷移するが、その場合、最初は単位行列Ｉなので単位行列からの巡回量は０になる。次に、単位行列Ｉから行列α４へは巡回量は４である。同様に、行列α４から行列α８へは巡回量は４である。そのため、シフトレジスタ番号欄２２２における５列目のシフトレジスタ番号は、０、４、４になる。そのため、タイミング１の場合に、第１シフトレジスタ６０ａから第５シフトレジスタ６０ｅに対するビットシフト量が、０００００と示される。また、タイミング３の場合に、第１シフトレジスタ６０ａから第５シフトレジスタ６０ｅに対するビットシフト量が、０１２３４と示される。さらに、タイミング５の場合に、第１シフトレジスタ６０ａから第５シフトレジスタ６０ｅに対するビットシフト量が、０１２３４と示される。図１４に戻る。
【００４６】
シフトレジスタ制御部６６は、タイミング生成部６４からのタイミングに応じたシフト量をシフト量テーブル６８から抽出し、第１シフトレジスタ６０ａから第５シフトレジスタ６０ｅにシフト量を設定する。具体的に説明すると、シフトレジスタ制御部６６は、タイミング１の場合に、シフト量テーブル６８に示されたビットシフト量だけ、各シフトレジスタ６０にシフトクロックを出力し、各シフトレジスタ６０のデータをビットシフトさせる。図１６の例では基本行列は一行目がすべて単位行列であり、ビットシフト量は０となっている。タイミング３に対して、シフトレジスタ制御部６６は、第１シフトレジスタ６０ａから第５シフトレジスタ６０ｅのデータを０、１、２、３、４だけそれぞれビットシフトさせる。タイミング５に対して、シフトレジスタ制御部６６は、第１シフトレジスタ６０ａから第５シフトレジスタ６０ｅのデータを０、１、２、３、４だけそれぞれビットシフトさせる。
【００４７】
メモリ４０は、図８と同様に、第１メモリ４０ａから第５メモリ４０ｅによって構成されており、情報ビットは第１メモリ４０ａから第５メモリ４０ｅに蓄えられる。メモリ４０は、情報ビットを順次記憶する。シフトレジスタ６０は、メモリ４０と１対１で接続される。そのため、第１シフトレジスタ６０ａから第５シフトレジスタ６０ｅが、第１メモリ４０ａから第５メモリ４０ｅのそれぞれに対応するように備えられる。各シフトレジスタ６０は、シフトレジスタ制御部６６からの指示に応じて、互いに異なったビットシフト量を設定可能である。
【００４８】
図１７（ａ）−（ｆ）は、メモリ４０とシフトレジスタ６０におけるビットパターンを示す。図１７（ａ）の上段が第１メモリ４０ａに記憶されるビットパターンを示し、下段が第１シフトレジスタ６０ａにおいてシフトされるビットパターンを示す。図１７（ｂ）の上段が第２メモリ４０ｂに記憶されるビットパターンを示し、下段が第２シフトレジスタ６０ｂにおいてシフトされるビットパターンを示す。図１７（ｃ）の上段が第３メモリ４０ｃに記憶されるビットパターンを示し、下段が第３シフトレジスタ６０ｃにおいてシフトされるビットパターンを示す。図１７（ｄ）の上段が第４メモリ４０ｄに記憶されるビットパターンを示し、下段が第４シフトレジスタ６０ｄにおいてシフトされるビットパターンを示す。図１７（ｅ）の上段が第５メモリ４０ｅに記憶されるビットパターンを示し、下段が第５シフトレジスタ６０ｅにおいてシフトされるビットパターンを示す。
【００４９】
図１７（ａ）−（ｅ）の上段のさらに上に示された記号が、各メモリ４０に記憶される情報ビットを示す。例えば、第１メモリ４０ａには、情報ビットｂ０からｂ４の５ビットが記憶され、第２メモリ４０ｂには、ｂ５からｂ９の５ビットが記憶され、第３メモリ４０ｃには、ｂ１０からｂ１４の５ビットが記憶され、第４メモリ４０ｄには、ｂ１５からｂ１９の５ビットが記憶され、第５メモリ４０ｅには、ｂ２０からｂ２４の５ビットが記憶される。以下では、説明を明瞭にするために、各メモリ４０に記憶されるビットを先頭から順に「ｂ０」から「ｂ４」と示す。
【００５０】
図１７（ｆ）は、タイミング生成部６４から出力されるタイミングを示す。図１７（ａ）−（ｅ）に示されるように、第１シフトレジスタ６０ａから第５シフトレジスタ６０ｅは、タイミングに応じて、シフトレジスタ制御部６６からの指示によってビットシフトを実行する。例えば、図１７（ｂ）のごとく、第２シフトレジスタ６０ｂは、タイミング１の場合にｂ０、ｂ１、ｂ２、ｂ３、ｂ４を記憶し、タイミング３の場合に、ｂ１、ｂ２、ｂ３、ｂ４、ｂ０を記憶し、タイミング５の場合に、ｂ２、ｂ３、ｂ４、ｂ０、ｂ１を記憶する。図１４に戻る。
【００５１】
パリティ演算生成部６２は、実施例１の図１１と同様の構成を有し、タイミング生成部６４において生成されたタイミングに応じて、シフトレジスタ６０に記憶された情報ビットを抽出する。つまり、パリティ演算生成部６２も、複数のシフトレジスタ６０のそれぞれに記憶したビット列の一部分から、対応づけられた基本行列における単位行列の巡回的シフト量に応じた順番の情報ビットを、情報部２３０の行単位に順次抽出する。パリティ演算生成部６２は、抽出した情報ビットを加算することによって、パリティのビットを生成する。具体的に説明すると、タイミング２のときに、タイミング１においてビットシフトさせたシフトレジスタ６０の値が抽出される。ここで、パリティのビットｐ０からｐ４は、次のように導出される。また、右辺の加算では、前から順に、第１シフトレジスタ６０ａ、第２シフトレジスタ６０ｂ、第３シフトレジスタ６０ｃ、第４シフトレジスタ６０ｄ、第５シフトレジスタ６０ｅに対応する。
ｐ０＝ｂ０＋ｂ０＋ｂ０＋ｂ０＋ｂ０＋０
ｐ１＝ｂ１＋ｂ１＋ｂ１＋ｂ１＋ｂ１＋ｐ０
ｐ２＝ｂ２＋ｂ２＋ｂ２＋ｂ２＋ｂ２＋ｐ１
ｐ３＝ｂ３＋ｂ３＋ｂ３＋ｂ３＋ｂ３＋ｐ２
ｐ４＝ｂ４＋ｂ４＋ｂ４＋ｂ４＋ｂ４＋ｐ３
【００５２】
また、タイミング４のときに、タイミング３においてビットシフトさせたシフトレジスタ６０の値が抽出される。ここで、パリティのビットｐ５からｐ９は、次のように導出される。
ｐ５＝ｂ０＋ｂ１＋ｂ２＋ｂ３＋ｂ４＋ｐ４
ｐ６＝ｂ１＋ｂ２＋ｂ３＋ｂ４＋ｂ０＋ｐ５
ｐ７＝ｂ２＋ｂ３＋ｂ４＋ｂ０＋ｂ２＋ｐ６
ｐ８＝ｂ３＋ｂ４＋ｂ５＋ｂ１＋ｂ３＋ｐ７
ｐ９＝ｂ４＋ｂ０＋ｂ６＋ｂ２＋ｂ４＋ｐ８
【００５３】
また、タイミング６のときに、タイミング５においてビットシフトさせたシフトレジスタ６０の値が抽出される。ここで、パリティのビットｐ１０からｐ１４は、次のように導出される。
ｐ１０＝ｂ０＋ｂ２＋ｂ４＋ｂ１＋ｂ３＋ｐ９
ｐ１１＝ｂ１＋ｂ３＋ｂ０＋ｂ２＋ｂ４＋ｐ１０
ｐ１２＝ｂ２＋ｂ４＋ｂ１＋ｂ３＋ｂ０＋ｐ１１
ｐ１３＝ｂ３＋ｂ０＋ｂ２＋ｂ４＋ｂ１＋ｐ１２
ｐ１４＝ｂ４＋ｂ１＋ｂ３＋ｂ１＋ｂ２＋ｐ１３
パリティ演算生成部６２は、情報データおよびパリティを符号語構成部５０へ出力する。
【００５４】
図１８は、ＬＤＰＣ符号化部２２における符号化手順を示すフローチャートである。メモリ４０は、情報ビットを記憶する（Ｓ５０）。シフトレジスタ６０は、メモリ４０の情報ビットを記憶する（Ｓ５２）。ｃｏｕｎｔが１に設定される（Ｓ５４）。シフトレジスタ制御部６６は、シフト量テーブル６８からｋ個のシフトレジスタ６０のシフト量を読み込み、ビットシフトを実行する（Ｓ５６）。パリティ演算生成部６２は、ビットシフトを行ったシフトレジスタの出力データからパリティの演算を行う（Ｓ５８）。ｃｏｕｎｔがｊでなければ（Ｓ６０のＮ）、ｃｏｕｎｔに１が加算され（Ｓ６２）、ステップ５６に戻る。ｃｏｕｎｔがｊであれば（Ｓ６０のＹ）、パリティ演算生成部６２は、パリティを符号語構成部５０に出力し、符号語構成部５０は、情報データとパリティとを併せて符号語を生成する（Ｓ６４）。符号語構成部５０は、符号語を出力する（Ｓ６６）。
【００５５】
本発明の実施例によれば、基本行列のパターンに合わせてシフトレジスタをビットシフトさせながらパリティ演算を行うので、クロックに同期してパリティ演算を行う場合、基本行列の行数ｊに対して（ｊ×２＋１）のクロックでパリティを生成できる。また、基本行列の行数ｊに対して（ｊ×２＋１）のクロックでパリティが生成されるので、高速なパリティ演算を実現できる。また、基本行列のパターンに合わせてシフトレジスタをビットシフトさせながらパリティ演算を行うので、クロックに同期してパリティ演算を行う場合、基本行列の列数ｋ個分のシフトレジスタで構成できる。また、符号化レートが高い場合でもアレー符号の性能を保ちつつ高速にパリティを生成できる。
【００５６】
以上、本発明を実施例をもとに説明した。この実施例は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００５７】
本発明の実施例において、通信システム１００は無線通信システムを前提としているので、送信装置１０および受信装置１２は、無線通信装置に含まれる。しかしながらこれに限らず例えば、通信システム１００は有線通信システムを前提としてもよい。その際、送信装置１０および受信装置１２は、有線通信装置に含まれる。本変形例によれば、本発明をさまざまな装置に適用できる。
【符号の説明】
【００５８】
１０  送信装置、  １２  受信装置、  ２０  情報データ生成部、  ２２  ＬＤＰＣ符号化部、  ２４  変調部、  ２６  復調部、  ２８  復号部、  ３０  情報データ出力部、  ４０  メモリ、  ４２  レジスタ、  ４４  パリティ演算生成部、  ４６  タイミング制御部、  ４８  アドレス生成部、  ５０  符号語構成部、  １００  通信システム。
【図１】
0005434890.tif 000002
【図２】
0005434890.tif 000003
【図３】
0005434890.tif 000004
【図４】
0005434890.tif 000005
【図５】
0005434890.tif 000006
【図６】
0005434890.tif 000007
【図７】
0005434890.tif 000008
【図８】
0005434890.tif 000009
【図９】
0005434890.tif 000010
【図１０】
0005434890.tif 000011
【図１１】
0005434890.tif 000012
【図１２】
0005434890.tif 000013
【図１３】
0005434890.tif 000014
【図１４】
0005434890.tif 000015
【図１５】
0005434890.tif 000016
【図１６】
0005434890.tif 000017
【図１７】
0005434890.tif 000018
【図１８】
0005434890.tif 000019