(57)【要約】課題  広範囲のＳＮ比においてパンクチャリングに基づく方法と同程度のスループットを達成し、かつ高符号化率での復号処理の計算量を改善する。解決手段  送信装置から受信装置に対して通信路上のエラーに対する誤り訂正符号を送信する通信システム通信システムにおいて、送信装置が、受信装置からの誤り訂正符号の再送要求に基づき、送信する符号語における情報ビットを複数のブロックに分割し、複数のブロックのうちの１のブロックに対して短縮符号化を行うことにより誤り訂正符号を生成し、生成した誤り訂正符号を送信する。
2009035096.tif 000002
【特許請求の範囲】
【請求項１】
送信装置から受信装置に対して通信路上のエラーに対する誤り訂正符号を送信する通信システムにおいて、
前記送信装置は、
前記受信装置からの前記誤り訂正符号の再送要求に基づき、
送信する符号語における情報ビットを複数のブロックに分割し、
前記複数のブロックのうちの１のブロックに対して短縮符号化を行うことによりパリティビットを生成し、
前記短縮符号化により生成されたパリティビットを送信する機能を有する符号化手段を備えることを特徴とする通信システム。
【請求項２】
前記符号化手段は、前記情報ビットの前記ブロックへの分割を、現在の情報ビットのブロックから一部の情報ビットを集めて第１のブロックを生成し、現在の情報ビットのブロックと前記第１のブロックとの補集合で表されるブロックを生成することによって行い、
前記第１のブロックに対して短縮符号化を行うことによりパリティビットを生成することを特徴とする請求項１に記載の通信システム。
【請求項３】
前記受信装置が、
受信した前記情報ビットの復号を、情報ビットの前記ブロックの受信値と、それまでに受信した前記誤り訂正符号の受信値と、既に復号済みの情報ビットとを用いて実行し、
前記情報ビットのブロックの復号に失敗した場合に、前記送信装置に対して再送要求を行う機能を有する復号手段を備えることを特徴とする請求項１又は請求項２に記載の通信システム。
【請求項４】
前記受信装置の前記復号手段が、
前記情報ビットのブロックの復号に失敗した場合に、前記送信装置への再送要求と共に、前記送信装置による前記情報ビットのブロックへの分割に対応して前記情報ビットのブロックへの分割を行うことを特徴とする請求項３に記載の通信システム。
【請求項５】
前記符号化手段が、
情報ビット格納手段と、
前記情報ビット格納手段から情報ビットの前記第１のブロックを取り出す情報ブロック抽出手段と
を有することを特徴とする請求項１から請求項４の何れかに記載の通信システム。
【請求項６】
前記符号化手段が、
再送要求時の前記誤り訂正符号を事前に計算し、誤り訂正符号格納手段に格納し、
再送要求があった場合に、前記誤り訂正符号格納手段から送信する前記誤り訂正符号を選択する機能を有することを特徴とする請求項１から請求項５の何れかに記載の通信システム。
【請求項７】
前記符号化手段が、
前記情報ビットのブロックと対応する誤り訂正符号検査行列成分との積である中間情報を計算する中間情報生成手段と、
前記中間情報を格納する中間情報格納手段と
を有することを特徴とする請求項１から請求項５の何れかに記載の通信システム。
【請求項８】
前記送信装置が、
前記情報ビットのブロックへの分割を予め定められた最大回数まで実行し、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しては既に送信した情報ビット又は誤り訂正符号の再送を行う
ことを特徴とする請求項１から請求項７の何れかに記載の通信システム。
【請求項９】
前記受信装置が、
前記送信装置から前記情報ビット又は誤り訂正符号を受信した場合、前記情報ビット又は誤り訂正符号の値とそれらの以前の受信値との平均化処理であるパケット合成を行う機能を有することを特徴とする請求項８に記載の通信システム。
【請求項１０】
受信装置に対して通信路上のエラーに対する誤り訂正符号を送信する送信装置において、
前記受信装置からの前記誤り訂正符号の再送要求に基づき、
送信する符号語における情報ビットを複数のブロックに分割し、
前記複数のブロックのうちの１のブロックに対して短縮符号化を行うことにより前記誤り訂正符号のパリティビットを生成し、
前記短縮符号化によって生成されたパリティビットを送信する機能を有する符号化手段を備えることを特徴とする送信装置。
【請求項１１】
前記符号化手段は、前記情報ビットの前記ブロックへの分割を、現在の情報ビットのブロックから一部の情報ビットを集めて第１のブロックを生成し、現在の情報ビットのブロックと前記第１のブロックとの補集合で表されるブロックを生成することによって行い、
前記第１のブロックに対して短縮符号化を行うことによりパリティビットを生成することを特徴とする請求項１０に記載の送信装置。
【請求項１２】
前記符号化手段が、
情報ビット格納手段と、
前記情報ビット格納手段から情報ビットの前記第１のブロックを取り出す情報ブロック抽出手段と
を有することを特徴とする請求項１０又は請求項１１に記載の送信装置。
【請求項１３】
前記符号化手段が、
再送要求時の前記パリティビットを事前に計算し、パリティビット格納手段に格納し、
再送要求があった場合に、前記パリティビット格納手段から送信する前記誤り訂正符号を選択する機能を有することを特徴とする請求項１０から請求項１２の何れかに記載の送信装置。
【請求項１４】
前記符号化手段が、
前記情報ビットのブロックと対応する誤り訂正符号検査行列成分との積である中間情報を計算する中間情報生成手段と、
前記中間情報を格納する中間情報格納手段と
を有することを特徴とする請求項１０から請求項１２の何れかに記載の送信装置。
【請求項１５】
前記送信装置が、
前記情報ビットのブロックへの分割を予め定められた最大回数まで実行し、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しては既に送信した情報ビット又はパリティビットの再送を行う
ことを特徴とする請求項１０から請求項１４の何れかに記載の送信装置。
【請求項１６】
請求項１５記載の送信装置において、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しては前記情報ビットのブロックから一部のビットを集めて構成されるブロック、もしくは送信済みのパリティビットのブロックから一部のビットを集めて構成されるブロックを送信する、
ことを特徴とする送信装置。
【請求項１７】
請求項１６記載の送信装置に対して、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しての受信データの場合にはパケット合成処理を行い、前記情報ビットのブロックの復号を第１番目の前記情報ビットのブロックから順次行う、
ことを特徴とする受信装置。
【請求項１８】
前記送信装置が、
前記情報ビットのブロックへの分割を予め定められた最大回数まで実行し、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しては前記情報ビットのブロックと送信済みの前記パリティビットに対応する短縮符号の拡大符号として生成されるパリティビットを送信する、
ことを特徴とする請求項１０から請求項１６の何れかに記載の送信装置。
【請求項１９】
請求項１８記載の送信装置に対して、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しての受信データの場合にはパケット合成処理を行い、前記情報ビットのブロックの復号を第１番目の前記情報ビットのブロックから順次行う、
ことを特徴とする受信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、送信装置から受信装置に対して通信路上のエラーに対する誤り訂正符号を送信する通信システムに関し、特に、復号処理の計算量を改善することを可能とする通信システム、送信装置、誤り訂正符号再送方法、通信プログラムに関する。
【背景技術】
【０００２】
誤り訂正符号は、符号化、復号化という処理によってデータ伝送時に混入するノイズの影響を低減する技術である。符号化は、送信するデータに冗長を付加する処理であり、符号化されたデータを符号語と呼ぶ。通信路に送出された符号語は、ノイズによる影響を受ける結果受信時には符号語の一部のビットが反転するといったエラーが発生する。復号化は、このエラーの影響を受けた受信符号語から冗長を利用してデータを復元する処理である。誤り訂正符号の利用は一方向の通信のみを利用しているため、フォワードエラーコレクション(Forward Error Correction, FEC)と呼ばれることもある。【０００３】
一方、通信路で発生するエラーに対して受信装置でエラーの検出を行い、検出結果を送信装置へフィードバックし、必要に応じて再送を行うことによって信頼性を確保する送信方式が利用されている。自動再送方式（Automatic-Repeat-reQuest : ARQ）はその代表的な方式である。【０００４】
これは送信の単位であるフレームにCyclic
Redundancy Check(CRC)等の誤り検出符号を付加しておき、受信装置で誤り検出符号によってエラーなしと判定された場合にはacknowledgment
(ACK)という信号を送信装置に送信し、送信装置は次のフレームの送信処理に移行する。【０００５】
逆に、受信装置でエラーありと判定された場合にはｒｅｑｕｅｓｔ（ＲＥＱ）という信号を送信装置に送信し、これを受信した送信装置はそのフレームを再び送信する。このｒｅｑｕｅｓｔ（ＲＥＱ）の送信とフレームの再送を、エラーなしと判定されるまで繰り返す。【０００６】
自動再送方式（ＡＲＱ）には多様なバリエーションが知られており、それらの１つは例えば非特許文献１に記載されている。【０００７】
誤り訂正符号と自動再送方式（ＡＲＱ）の組み合わせはハイブリッドＡＲＱと呼ばれており、モバイル通信をはじめとして利用されている。受信装置では送信フレームを受信したら誤り訂正符号の復号を行い、これに失敗したときには送信装置へ再送の要求（ＲＥＱ）を送る。誤り訂正符号の復号の成功、失敗の判定は復号処理の結果として検出可能な場合と上述の自動再送方式（ＡＲＱ）と同様に情報系列にエラー検出用のＣＲＣを付加しておく方法が考えられる。【０００８】
自動再送方式（ＡＲＱ）のスループットは情報ビット長に対して再送分まで含めての送信データ長との比として定義される。ハイブリッドＡＲＱ方式を考案する上ではスループットを大きくなるようにすることが設計指針の１つとなる。再送を行う必要がない場合のスループットは誤り訂正符号の符号化率に一致する。スループットを基準にした場合には逐次的にパリティビットを送信する方式が効果的であり、Incremental Redundancy (IR)方式と呼ばれている。以下、ＩＲ方式に関して図を用いて説明する。【０００９】
図２０は、誤り訂正符号の符号語の構成を示す模式図であり、パリティ部分をパリティ０から３までの４個のグループに分割している。誤り訂正符号においてパリティの一部のみを送付して符号化率を向上させる方式はパンクチャリングと呼ばれている。パリティの一部のみを送信した場合はその量に応じた訂正能力が得られることになる。図２１に、パンクチャリングに基づくＩＲ方式における送信装置の符号化手段の構成例を示しており、符号化手段は、パリティ生成手段と、生成したパリティを格納するパリティ格納手段及び制御手段を備えて構成される。【００１０】
図２２に、図１３の符号に対してのＩＲ方式に基づくハイブリッドＡＲＱの送信装置と受信装置の処理例を示す。以下この手続きを説明する。なお、以下の説明で、フレームは送信単位を表し、１個のフレームと符号語が対応しているものとする。【００１１】
送信装置は、フレーム０の情報ビットとパリティ０を送信する（ステップ１００１）。【００１２】
受信装置は、フレーム０の情報ビットとパリティ０の受信値から復号を実行する。復号に成功したので送信装置へＡＣＫを送信する（ステップ１００２）。【００１３】
送信装置は、フレーム１の情報ビットとパリティ０を送信する（ステップ１００３）。【００１４】
受信装置は、情報ビットとパリティ０の受信値から復号を実行する。復号に失敗したので送信装置へＲＥＱを送信する（ステップ１００４）。【００１５】
送信装置は、フレーム１のパリティ１を送信する（ステップ１００５）。【００１６】
受信装置は、情報ビット、パリティ０とパリティ１の受信値から復号を実行する。復号に失敗したので送信装置へＲＥＱを送信する（ステップ１００６）。【００１７】
送信装置は、フレーム１のパリティ２を送信する（ステップ１００７）。【００１８】
受信装置は、情報ビット、パリティ０、パリティ１とパリティ２の受信値から復号を実行する。復号に成功したので送信装置へＡＣＫを送信する（ステップ１００８）。【００１９】
送信装置は、フレーム３の情報ビットとパリティ０を送信する（ステップ１００９）。【００２０】
パンクチャリングに適した符号設計を行うことが効果的なＩＲ方式を実現するための一つの手段となる。このためには符号がパンクチャリングを行った場合でも、（１）重み分布が良いこと、（２）効率よく復号が可能なこと、という性質を持つ必要がある。例えば、畳込み符号に対して軟判定ヴィタビ復号を適用する場合にはパンクチャリングされたビットを適切な値（０と１が等確率となる軟判定値）に設定することによって通常のヴィタビ復号処理と全く同様に最尤復号を実現できる。パンクチャリングを想定した畳込み符号の設計については従来から多くの研究がなされており、例えば、非特許文献１の１２．５章(chapter 12.5)に述べられている。【００２１】
近年、ターボ符号や低密度パリティ(Low-Density
Parity-Check, LDPC)符号など、高い訂正能力を持つ符号の研究および実用化が進んでいる。これらの符号の復号はメッセージパッシング復号と呼ばれる、符号語ビットの信頼度情報を逐次的に計算する繰り返し復号のアルゴリズムを用いて実行される。ＬＤＰＣ符号の復号については例えば、非特許文献２に述べられている。【００２２】
ＬＤＰＣ符号のメッセージパッシング復号は行処理、列処理とよばれる処理を繰り返すことによって実行される。【００２３】
パリティ検査行列の各行は成分が非零である位置にある符号語ビットに対して一次式で表される拘束条件を与える。そのような１個の符号語ビットに注目したとき、他の符号語ビットの信頼度情報（“０”，“１”の確率）が与えられればこの拘束条件下におけるそのビットの信頼度情報を計算することができる。ＬＤＰＣ符号のメッセージパッシング復号における行処理は非零の成分に対応する各符号語ビットに対してこのような処理を行う。【００２４】
一方、列処理は、各符号語ビットにおいて、対応するパリティ検査行列の列で成分が非零である行で計算された信頼度情報とその符号語ビットの受信値をマージする処理を行う。受信値および信頼度情報が対数尤度比で与えられている場合は、このマージ処理は実数値の加算となる。ビットの硬判定はこのマージした値で行う。各行へはその行以外の行処理から得られた信頼度情報と受信値をマージした値を戻し、これを行処理の次の入力とする。【００２５】
ＬＤＰＣ符号の繰り返し復号はパリティ検査行列のすべての列、行に対応する列処理、行処理を繰り返すことによって行われる。ビットの硬判定値から計算したシンドロームがすべて“０”になる、もしくは決められた回数の繰り返し回数に達したら復号処理を終了する。【００２６】
この繰り返し復号は、局所的な拘束条件に基づいて実行されるため最適復号となる保証はないが、パリティ検査行列が低密度であり、グラフ表現したときに小さなサイクルの個数の割合が小さいという、ＬＤＰＣ符号に要求される性質を持つ場合には良い特性を得ることができる。【００２７】
ＬＤＰＣ符号も畳込み符号と同様にパンクチャリングが有効に適用可能であり、多くの研究がなされている。ハイブリッドＡＲＱ方式への適用に関しても符号を注意深く設計した場合には、広範囲なＳＮ比の通信路で優れたスループットを達成することが可能であり、例えば非特許文献３に述べられている。
【非特許文献１】S.B.Wicker,Error Control Systems for Digital Communication and Storage, Chapter 15,Prentice-Hall, Inc. 1995.
【非特許文献２】D. J. C.MacKay, “Good error correcting codes based on very sparse matrices,” IEEETransaction on Information Theory,” vol. 45, no. 2, pp.399-431, May 1999.
【非特許文献３】J. Li and K.R. Narayanan, “Rate-compatible low density parity check (RC-LDPC) codes forcapacity-approaching ARQ schemes in packet data communications,” Proceeding ofInternational Conference on Communications, Internet and InformationTechnology, Nov. 2002, pp. 789-795.
【非特許文献４】M. R. Yazdaniand A. H. Banihashemi, “On Construction of Rate-Compatible Low-DensityParity-Check Codes,” IEEE Communications Letters, vol.8, no.3, pp.159-161. March2004.
【発明の開示】
【発明が解決しようとする課題】
【００２８】
パンクチャリングの適用は復号装置からみれば、低符号化率の符号を用いてノイズが大きい受信値系列に基づいて復号を実行することと同等になる。このため、パンクチャリングの割合に応じて計算量が増加するデメリットが存在する場合がある。パンクチャリングに基づいた従来のターボ符号やＬＤＰＣ符号を用いたＩＲ方式では、最初の送信である高符号化率の場合には大規模なパンクチャリングが行われ、繰り返し復号の収束が高符号化率をターゲットに設計した符号と比較して劣化する。【００２９】
この問題に対して高符号化率の符号を最初に設計し、それをＩＲ方式に対応するよう拡張する符号設計が考えられる。ＬＤＰＣ符号の場合にはパリティ検査行列を拡大する形で低符号化率でも良い特性を達成するように符号設計を行う。このような構成法が、例えば、非特許文献４に記載されている。【００３０】
しかし、非特許文献４に開示されるこの種の方法においては、拡大の割合が大きい場合はパリティ検査行列が複雑になり、復号器処理の複雑度も大きくなる。【００３１】
さらに低符号化率をターゲットに設計した符号と比較して、低符号化率でのスループットも劣化する。【００３２】
この方法を用いて例えば符号化率０．８の符号を基に符号化率０．５までをカバーすることは困難である。非特許文献４でも、符号化率８／１３のＬＤＰＣ符号をベースにして、高符号化率の場合にはそのパンクチャリングで対応している。このとき、符号率を０．８とするためにはパリティの６０％をパンクチャする必要があり、繰り返し復号の収束も劣化する。【００３３】
（発明の目的）
本発明の目的は、広範囲のＳＮ比においてパンクチャリングに基づく方法と同程度のスループットを達成し、かつ高符号化率での復号処理の計算量を改善することができる通信システム、送信装置、誤り訂正符号再送方法、通信プログラムを提供することにある。
【課題を解決するための手段】
【００３４】
本発明の通信システムは、送信装置から受信装置に対して通信路上のエラーに対する誤り訂正符号を送信する通信システムにおいて、送信装置は、受信装置からの誤り訂正符号の再送要求に基づき、送信する符号語における情報ビットを複数のブロックに分割し、複数のブロックのうちの１のブロックに対して短縮符号化を行うことにより誤り訂正符号を生成し、生成した誤り訂正符号を送信する機能を有する符号化手段を含む。【００３５】
本発明の送信装置は、受信装置に対して通信路上のエラーに対する誤り訂正符号を送信する送信装置において、受信装置からの誤り訂正符号の再送要求に基づき、送信する符号語における情報ビットを複数のブロックに分割し、複数のブロックのうちの１のブロックに対して短縮符号化を行うことにより誤り訂正符号を生成し、生成した誤り訂正符号を送信する機能を有する符号化手段を含む。【００３６】
本発明の誤り訂正符号再送方法は、送信装置から受信装置に対して通信路上のエラーに対する誤り訂正符号を送信する通信システムの誤り訂正符合再送方法において、送信装置が、受信装置からの誤り訂正符号の再送要求に基づき、送信する符号語における情報ビットを複数のブロックに分割するステップと、複数のブロックのうちの１のブロックに対して短縮符号化を行うことにより誤り訂正符号を生成するステップと、生成した誤り訂正符号を送信するステップを有する。【００３７】
本発明の通信プログラムは、コンピュータである送信装置上で実行され、受信装置に対して通信路上のエラーに対する誤り訂正符号を送信する通信プログラムを格納するコンピュータ読み取り可能な記録媒体であって、通信プログラムが、受信装置からの誤り訂正符号の再送要求に基づき、送信する符号語における情報ビットを複数のブロックに分割する処理と、複数のブロックのうちの１のブロックに対して短縮符号化を行うことにより誤り訂正符号を生成する処理と、生成した誤り訂正符号を送信する処理を、コンピュータに実行させる。
【発明の効果】
【００３８】
本発明によれば、広範囲のＳＮ比においてパンクチャリングに基づく方法と同程度のスループットを達成し、かつ高符号化率をターゲットに設計された符号を使用するため、復号計算量をパンクチャリングによる方法よりも改善することができる。
【図面の簡単な説明】
【００３９】
【図１】本発明の第１の実施の形態よる送信装置の符号化手段における処理の内容を説明するフローチャートである。
【図２】図１の符号化手順に対する受信装置における復号手段における処理動作を示すフローチャートである。
【図３】本実施の形態による送信装置における符号化手段の第１の構成例を示すブロック図である。
【図４】本実施の形態による送信装置における符号化手段の第２の構成例を示すブロック図である。
【図５】本実施の形態による送信装置における符号化手段の第３の構成例を示すブロック図である。
【図６】本発明の第２の実施の形態よる送信済みの情報ビットとパリティの再送を含む場合の送信装置の処理を説明するフローチャートである。
【図７】本発明の第２の実施の形態よる送信済みの情報ビットとパリティの再送を含む場合の受信装置の処理を説明するフローチャートである。
【図８】本発明の第３の実施の形態よる送信済みの情報ビットとパリティの再送を含む場合の送信装置の処理を説明するフローチャートである。
【図９】本発明の第３の実施の形態よる送信済みの情報ビットとパリティの再送を含む場合の受信装置の処理を説明するフローチャートである。
【図１０】本発明の第４の実施の形態よる送信済みの情報ビットとパリティの再送を含む場合の送信装置の処理を説明するフローチャートである。
【図１１】本実施の形態に適したＬＤＰＣ符号のパリティ検査行列の構成例を示す図である。
【図１２】図１０のパリティ検査行列に対する情報ブロックへの分割の例を示す図である。
【図１３】符号化および復号に使用する、情報ブロックに対応する図１０のパリティ検査行列の成分を説明する図である。
【図１４】図１０のパリティ検査行列を用いた場合の第２の実施の形態に基づく受信装置の処理フローを復号手段の処理に基づき表している。
【図１５】図１１のパリティ検査行列に対して第３の実施の形態に基づく場合の再送ブロックの形態例を説明する図である。
【図１６】図１１のパリティ検査行列に対して第３の実施の形態に基づく場合の受信装置の処理フローを復号手段の処理に基づき表している。
【図１７】図１１のパリティ検査行列に対して、再送レベルＫ＝３における短縮符号に対する拡大符号のパリティ検査行列の構成例を示す図である。
【図１８】図１１のパリティ検査行列に対して第４の実施の形態に基づく場合の再送ブロックの形態例を説明する図である。
【図１９】本実施の形態による送信装置と受信装置のハードウェア構成を示す図である。
【図２０】符号のパンクチャリングを現す模式図である。
【図２１】パンクチャリングに基づくＩＲ方式における符号化手段の構成例を示すブロック図である。
【図２２】ＩＲ方式に基づくハイブリッドＡＲＱの送信装置と受信装置の処理内容を説明する図である。
【発明を実施するための最良の形態】
【００４０】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
（第１の実施の形態）【００４１】
図１は、本発明の実施の形態よるハイブリッドＡＲＱ方式の通信システムにおける送信処理の内容を説明するフローチャートである。【００４２】
本発明の実施の形態におけるＩＲ方式では、基本的に最初の送信時と同一の大きさのパリティビットを送信するスキームを考える。なお、本発明の実施の形態では、非特許文献１等に記載されるパンクチャリングや拡大に基づくＩＲ方式と組み合わせて適用することも可能である。【００４３】
ここで、送信回数を示すインデックスをＫとする（Ｋ＝０，１，・・・）。本実施の形態では、ある符号語に対してのＫ回目の送信要求に対して情報ビットを（Ｋ＋１）個のブロックに分割して、その１個のブロックに対してのパリティを生成し、送信する。つまり、そのブロック以外の情報ビットを「０」とする短縮符号化を行い、パリティを計算する。単なる短縮であるため、符号化におけるパリティ生成は同一の処理によって実行可能である。【００４４】
以下、図１に従って、本実施の形態における送信装置から１個の符号語を送信する場合の符号化手段の処理動作について説明する。【００４５】
最初に、符号語における情報ビット列Iを送信する（ステップ１０１）。【００４６】
次に、送信回数インデックスＫを「０」にセットし、Ｋ回目の送信における情報ビットビット列Iのブロック（情報ブロック）をＩ（ｊ，Ｋ）とする（ｊ＝０，１，・・・，Ｋ）（ステップ１０２）。ここで、Ｉ（０，０）は情報ビット列そのものである。【００４７】
情報ブロックＩ（０，Ｋ）の短縮符号化を行い、パリティＰ（Ｋ）を生成する（ステップ１０３）。【００４８】
生成したパリティＰ（Ｋ）を送信する（ステップ１０４）。【００４９】
受信装置からのフィードバックを受け取る（ステップ１０５）。ここで、受信装置からのフィードバックがＡＣＫ（確認応答）である場合には、処理を終了し、次の符号語の送信処理に移行する。【００５０】
受信装置からＲＥＱ（再送要求）を受け取った場合には、情報ブロックＩ（ｊ，Ｋ）（ｊ＝０，１，・・・，Ｋ）の一部を集めて情報ビットのブロックＩ（０，Ｋ＋１）を構成する（ステップ１０６）。【００５１】
次に、Ｉ（ｊ，Ｋ）からＩ（０，Ｋ＋１）との共通部分を除いた補集合に対して、Ｉ（ｊ，Ｋ＋１）＝Ｉ（ｊ＋１，Ｋ）＼Ｉ（０，Ｋ＋１）とインデックスをつける（ステップ１０７）。【００５２】
そして、送信回数インデックスＫをＫ＋１とし、ステップ１０３に戻る（ステップ１０８）。【００５３】
図２は、図１の符号化手順に対する受信装置における復号手段における処理動作を示すフローチャートである。【００５４】
まず、送信回数インデックスＫを「０」とし、情報ビットに対する受信値を設定し、情報ビット列を受信する（ステップ２０１、２０２）。【００５５】
パリティＰ（Ｋ）に対する受信値を設定し、パリティＰ（Ｋ）を受信する（ステップ２０３）。【００５６】
送信回数インデックスＫにおける情報ブロックのインデックスｊを「０」とする（ステップ２０４）。【００５７】
次に、情報ブロックＩ（ｊ，Ｋ）およびパリティＰ（Ｋ−ｊ）に対する受信値を用いて復号処理を実行する（ステップ２０５）。【００５８】
復号に成功した場合にはステップ２０７へ、そうでない場合にはステップ２１０へ移行する（ステップ２０６）。【００５９】
ステップ２０７では、ｊ＝Ｋであれば復号処理を終了し、そうでなければステップ２０８へ移行する。【００６０】
ｊ＝Ｋではない場合、Ｉ（ｊ，Ｋ）に対応する情報ビットが確定したとして固定する（ステップ２０８）。ＬＤＰＣ符号では、この固定処理は、受信値をビット値に合わせて十分に大きな値に設定すること、あるいは、これらの情報ビットと対応するパリティ検査行列の成分を乗じた値（ベクトル）を求めること等の方法で実行する。【００６１】
そして、ｊをｊ＋１としてステップ２０５へ戻り、次のブロックの処理に移行する（ステップ２０９）。【００６２】
ステップ２０６において、情報ブロックＩ（ｊ，Ｋ）およびパリティＰ（Ｋ−ｊ）の復号に失敗した場合には、図１のステップ１０６に対応して、Ｉ（ｊ，Ｋ）（ｊ＝０，１，・・・，Ｋ）の一部を集めて情報ビットのブロックＩ（０，Ｋ＋１）を構成する（ステップ２１０）。【００６３】
また、図１のステップ１０７に対応して、情報ビットのブロックＩ（ｊ，Ｋ＋１）を構成する（ステップ２１１）。【００６４】
Ｋ←Ｋ＋１とし（ステップ２１２）、送信装置に対してＲＥＱ（再送要求）を送信する（ステップ２１３）。その後、ステップ２０３に戻る。【００６５】
図３は、本実施の形態による送信装置における符号化手段の第１の構成例を示している。【００６６】
符号化手段１０は、情報ビット格納手段６００、情報ブロック抽出手段６０１、パリティ生成手段６０２、制御手段６０３を備える構成である。【００６７】
情報ビット格納手段６００は、再送に備えて、必要であれば複数の符号語に対応する情報ビットを格納する。【００６８】
情報ブロック抽出手段６０１は、パリティを生成する情報ビットのブロックＩ（０，Ｋ）に対応する情報ビットを情報ビット格納手段６００から読み込む。【００６９】
この情報ブロック抽出手段６０１による処理の制御は、受信装置からのフィードバック情報を判断して制御手段６０３が実行する。【００７０】
パリティ生成手段６０２は、情報ブロック抽出手段６０１からの入力に基づいて短縮符号化を行い、パリティを生成する。【００７１】
図４は、本実施の形態による符号化手段の第２の構成例を示している。【００７２】
符号化手段２０は、情報ブロック抽出手段７００と、パリティ生成手段７０１と、パリティ格納手段７０２と、制御手段７０３とを備える構成である。【００７３】
情報ブロック抽出手段７００は、Ｉ（０，Ｋ）（Ｋ＝０，１，・・・）を、事前にパリティ生成手段７０１に供給し、パリティ格納手段７０２は生成されたパリティを格納する。【００７４】
再送要求への対応は、制御手段７０３を通じて、図１３で説明した方式と同様にパリティ格納手段７０２からパリティを選択する。【００７５】
図５は、本実施の形態による符号化手段の第３の構成例を示している。【００７６】
符号化手段３０は、情報ブロック抽出手段８００と、中間情報生成手段８０１と、中間情報格納手段８０２と、パリティ生成手段８０３と、制御手段８０４とを備える構成である。【００７７】
この符号化手段３０では、情報ブロック抽出手段８００が出力するＩ（０，Ｋ）から中間情報生成手段８０１で符号化における中間情報を生成し、中間情報格納手段８０２に格納しておく。【００７８】
中間情報生成手段８０１は、例えば、Ｉ（０，Ｋ）と対応するパリティ検査行列の成分を乗じた値（ベクトル）である、中間情報を計算して生成する。この中間情報生成は、Ｉ（０，Ｋ）の順序を工夫することで効率化することができる。【００７９】
図３の符号化手段１０は、再送のたびに最初から符号化処理を実行するのに対して、図４の符号化手段２０では、再送の必要がないかもしれないパリティも最初に計算している。また、図５の符号化手段３０は、図３と図４の中間を狙った符号化手段の構成であり、パリティを最初に計算せず、パリティ生成に用いる中間情報を予め生成する。【００８０】
ここで、本実施の形態による送信装置と受信装置のハードウェア構成の説明をする。【００８１】
図１２は、本実施の形態による送信装置と受信装置のハードウェア構成を示すブロック図である。【００８２】
図１２を参照すると、本実施の形態による送信装置と受信装置は、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３０１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のメインメモリであり、データの作業領域やデータの一時退避領域に用いられる主記憶部３０２、データの送受信を行うインタフェース部３０３、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、磁気ディスク、半導体メモリ等の不揮発性メモリから構成されるハードディスク装置である補助記憶部３０４、上記各構成要素を相互に接続するシステムバス３０５等を備えている。【００８３】
本実施の形態による送信装置と受信装置は、符号化手段と復号化手段の処理動作を、内部にそのような機能を実現する通信プログラムを組み込んだ、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等のハードウェア部品からなる回路部品を実装してハードウェア的に実現することは勿論として、上記通信プログラムを、ＣＰＵ３０１で実行することにより、ソフトウェア的に実現することも可能である。【００８４】
すなわち、ＣＰＵ３０１は、補助記憶部３０４に格納されているプログラムを、主記憶部３０２にロードして実行し、符号化手段と復号化手段の処理動作をソフトウェア的に実現する。【００８５】
（第１の実施の形態による効果）
次に、本実施の形態の効果について説明する。【００８６】
本実施の形態によれば、高符号化率をターゲットに設計された符号を使用するため、その復号計算量をパンクチャリングによる方法よりも改善することができる。例えば、符号化率０．８をターゲットに設計したＬＤＰＣ符号の復号計算量は、符号化率０．５で設計したＬＤＰＣ符号をパンクチャリングによって符号化率０．８とした場合と比較して数分の１程度になる。【００８７】
本実施の形態では、短縮符号によって広範囲な符号化率対して良い特性を達成する符号を利用することが有効であるが、これもＬＤＰＣ符号を用いて実現することができる。本実施の形態では、追加のパリティを再送した場合、復号の単位となる符号長も小さくなるが、ハイブリッドＡＲＱのスループットはフレーム誤り率１／１０から１／１００程度の高い領域での符号化利得で決定されるため、この影響も小さく抑えることができる。よって、パリティ送信を複数回行う、通信路のＳＮＲが悪い領域でも背景技術で述べた方式と同程度のスループットを達成できる。【００８８】
本実施の形態では、追加のパリティ再送を行った場合には、複数の短縮符号を復号することになる。しかし、ＬＤＰＣ符号の復号器において行処理を逐次的に行う構成とすればこのオーバーヘッドを抑えることが可能で、追加のパリティを再送する場合でもトータルの復号計算量を、背景技術で述べたパンクチャリングを用いた方式と同程度とすることができる。
（第２の実施の形態）【００８９】
図１に示した送信処理では、再送要求があるたびに情報ブロックを細分化していくが、実際にはあるレベルまでの細分化を想定し、それより先は同一のブロックとパリティの再送を行う方法を用いる方が装置構成や計算量的に有利となる場合もある。【００９０】
図６を参照して、このような方法を用いた第２の実施の形態における送信処理の内容について説明する。なお、図６において、図１と同様の符号を付したステップは、図１と共通するステップであるのでそれらの詳細は省略する。【００９１】
図１で説明したと同様の処理において、受信装置からＲＥＱ（再送要求）を受け取った場合には、追加のパリティの送信回数Ｋが予め設定した最大値であるかどうかを判断する（ステップS３０１）。【００９２】
最大値ではない場合には、図１と同様にブロックを細分化して、そのパリティを生成する処理に移行する（ステップＳ１０６〜Ｓ１０８）。【００９３】
ステップＳ３０１で、送信回数インデックスＫが最大値である場合には、受信装置からのフィードバックは復号に失敗した情報ブロックＩ（ｊ，Ｋ）のインデックスｊを含む情報ＲＥＱ（ｊ）である。送信装置ではＲＥＱ（ｊ）からjを判定し（ステップＳ３０２）、対応するＩ（ｊ、Ｋ）に関する再送処理を行う（ステップＳ３０３）。【００９４】
この同一データの再送時にはパリティの大きさと異なる単位で送信することも考えられる。また、情報ビットの再送が必要になるため、図４、図５に示す符号化手段を用い場合、送信装置は複数の符号語に対する情報ビットを格納する手段を備える必要がある。【００９５】
図７は、図６の符号化手順に対する受信装置における復号手段における処理動作を示すフローチャートである。なお、図７において、図２と同様の符号を付したステップは、図２と共通のステップであるのでそれらの詳細は省略する。【００９６】
図２における処理と同様であるが、Ｉ（ｊ，Ｋ）とＰ（Ｋ−ｊ）の復号に失敗すると（Ｓ２０６）、送信回数Ｋが最大値であるかどうかを判定する（ステップＳ４０１）。【００９７】
ステップＳ４０１で、送信回数Ｋが最大値である場合には、Ｉ（ｊ，Ｋ）とＰ（Ｋ−ｊ）の再送に移行するため、ＲＥＱ（ｊ）を送信装置へ送る（ステップＳ４０２）。【００９８】
受信したＩ（ｊ，Ｋ）やＰ（Ｋ−ｊ）の値と以前に受信した値との平均化処理であるパケット合成を行い（ステップＳ４０３）、再び復号処理を実行する（ステップＳ２０５）。【００９９】
ステップＳ４０１で、最大値ではない場合には、Ｉ（ｊ，Ｋ）（ｊ＝０，１，・・・，Ｋ）の一部を集めて情報ビットのブロックＩ（０，Ｋ＋１）を構成するステップ２１０に移行する。【０１００】
（第２の実施の形態による効果）
次に、本実施の形態の効果について説明する。【０１０１】
第２の実施の形態によれば、上述した第１の実施の形態における効果に加えて、あるレベルまでブロックを細分化した場合、それより先は同一のブロックとパリティの再送を行うようにしたことから、装置構成をより簡素化できると共に、計算量をより改善することができる場合がある。
（第３の実施の形態）【０１０２】
本発明においてあるレベルまでの情報ブロックの細分化を設定した場合、第２の実施の形態とは異なり、さらなる再送要求を受けた際にはそのレベルでの複数の短縮符号に対して均等に再送ビットを送信する方法も考えられる。このことによって第２の実施の形態では必要であった、再送する短縮符号を指定するＲＥＱ（ｊ）のインデックスｊは不要となり、単なるＲＥＱで十分となる。【０１０３】
図８を参照して、このような方法を用いた第３の実施の形態における送信処理の内容について説明する。なお、図＊において、図１と同様の符号を付したステップは、図１と共通するステップであるのでそれらの詳細は省略する。【０１０４】
図１で説明したと同様の処理において、受信装置からＲＥＱ（再送要求）を受け取った場合には、追加のパリティの送信回数Ｋが予め設定した最大値であるかどうかを判断する（ステップS５０１）。【０１０５】
最大値ではない場合には、図１と同様にブロックを細分化して、そのパリティを生成する処理に移行する（ステップＳ１０６〜Ｓ１０８）。【０１０６】
ステップＳ５０１で、送信回数Ｋが最大値である場合には、Ｉ（０，Ｋ）からＩ（Ｋ，Ｋ）、もしくはＰ（０）からＰ（Ｋ）の一部のビットを抽出して構成されるブロックを再送する（ステップＳ５０２）。【０１０７】
このとき、受信装置からのフィードバックがＡＣＫであるかを判定する（ステップＳ５０３）。  受信装置からのフィードバックが、情報ＲＥＱである場合には、ステップＳ５０２の再送処理を行う。【０１０８】
第２の実施の形態と同様に、この同一データの再送時にはパリティの大きさと異なる単位で送信することも考えられる。また、情報ビットの再送が必要になるため、図４、図５に示す符号化手段を用い場合、送信装置は複数の符号語に対する情報ビットを格納する手段を備える必要がある。【０１０９】
図９は、図８の符号化手順に対する受信装置における復号手段における処理動作を示すフローチャートである。なお、図９において、図２と同様の符号を付したステップは、図２と共通のステップであるのでそれらの詳細は省略する。
【０１１０】
送信回数Ｋが最大値である場合には受信したＩ（０，Ｋ）からＩ（Ｋ，Ｋ）もしくはＰ（０）からＰ（Ｋ）の一部のビットの受信値と以前に受信した値との平均化処理であるパケット合成を行い（ステップＳ６０３）、再びＩ（０，Ｋ）からの復号処理を実行する（ステップＳ２０４、Ｓ２０５）。【０１１１】
ステップＳ６０１で、最大値ではない場合には、Ｉ（ｊ，Ｋ）（ｊ＝０，１，・・・，Ｋ）の一部を集めて情報ビットのブロックＩ（０，Ｋ＋１）を構成するステップ２１０に移行する。【０１１２】
Ｉ（ｊ，Ｋ）Ｐ（Ｋ−ｊ）をｊ＝０からＫに対して順次復号を実行する（ステップＳ２０５〜２０９）。【０１１３】
（第３の実施の形態による効果）
次に、本実施の形態の効果について説明する。【０１１４】
第３の実施の形態によれば、上述した第２の実施の形態における効果に加えて、ＲＥＱの信号で短縮符号のインデックスを付加する必要がなくなる。ただし、この実施の形態ではＩ（ｊ，Ｋ）で復号に失敗して再送要求を行った場合には既に復号に成功していると判定されているｉ＜ｊであるＩ（ｉ、Ｋ）に関しても再送を行い、パケット合成を行って再び復号を行うことになる。しかし、各短縮符号が同程度の訂正能力を持つように構成した場合で、再送するビット数が固定の場合には逆にこのような再送を行った方が効率を上げることが可能な場合もある。また、仮にＩ（ｉ、Ｋ）で誤訂正が行われた結果、復号が正しく行われたと判定された場合にはＩ（ｊ、Ｋ）は再送を何度行っても正しく復号を行うことができないため、第２の実施の形態ではこの対策が別途必要になる。一方、第３の実施の形態では必ずＩ（０，Ｋ）からＩ（Ｋ，Ｋ）までのすべての短縮符号に対してパケット合成を行い、Ｉ（０、Ｋ）から復号を再開することになるので途中で誤訂正が発生した場合でも復号をやり直すことが可能となる。
（第４の実施の形態）【０１１５】
本発明においてあるレベルまでの情報ブロックの細分化を設定した場合、第２、第３の実施の形態とは異なり、最大レベルで再送要求を受けた際には各短縮符号に対して、従来技術の説明で述べた、パリティ検査行列の拡大により送信するパリティを生成する方法も考えられる。このようなパリティ検査行列の拡大によって生成されるパリティをここでは拡大符号のパリティと呼ぶことにする。【０１１６】
図１０を参照して、このような方法を用いた第４の実施の形態における送信処理の内容について説明する。なお、図１０において、図１と同様の符号を付したステップは、図１と共通するステップであるのでそれらの詳細は省略する。【０１１７】
図１で説明したと同様の処理において、受信装置からＲＥＱ（再送要求）を受け取った場合には、追加のパリティの送信回数Ｋが予め設定した最大値であるかどうかを判断する（ステップS７０１）。【０１１８】
最大値ではない場合には、図１と同様にブロックを細分化して、そのパリティを生成する処理に移行する（ステップＳ１０６〜Ｓ１０８）。【０１１９】
ステップＳ７０１で、送信回数Ｋが最大値である場合には、Ｉ（０，Ｋ）Ｐ（Ｋ）、Ｉ（１、Ｋ）Ｐ（Ｋ−１）からＩ（Ｋ，Ｋ）Ｐ（０）に対応する各短縮符号の拡大符号のパリティから構成されるブロックを送信する（ステップＳ７０２）。【０１２０】
このとき、受信装置からのフィードバックがＡＣＫであるかを判定する（ステップＳ７０３）。  受信装置からのフィードバックが、情報ＲＥＱである場合には、ステップＳ７０２の再送処理を引き続き行う。【０１２１】
拡大符号のパリティの再送時には、第１の実施の形態における再送時のパリティの大きさと異なる単位で送信することも考えられる。【０１２２】
図１１は、図１０の符号化手順に対する受信装置における復号手段における処理動作を示すフローチャートである。なお、図１１において、図２と同様の符号を付したステップは、図２と共通のステップであるのでそれらの詳細は省略する。
【０１２３】
送信回数のインデックスＫが最大値である場合（ステップＳ８０２）、図１０の送信処理に対応してＩ（０，Ｋ）Ｐ（Ｋ）からＩ（Ｋ，Ｋ）Ｐ（０）に対応する短縮符号の拡大符号のパリティから構成されるブロックを受信する（ステップＳ８０３）。【０１２４】
ステップＳ８０２で、最大値ではない場合には、Ｉ（ｊ，Ｋ）（ｊ＝０，１，・・・，Ｋ）の一部を集めて情報ビットのブロックＩ（０，Ｋ＋１）を構成するステップ２１０に移行する。【０１２５】
Ｉ（ｊ，Ｋ）をｊ＝０からＫに対して順次復号を実行する（ステップＳ２０５〜２０９）。【０１２６】
Ｉ（ｊ，Ｋ）の復号を実行するにあたり、拡大符号のパリティを受信しているかどうかを判断する（ステップＳ８０１）。これは例えばＫとは別に再送回数を順次カウントすることによって実現することが可能である。【０１２７】
拡大符号のパリティを受信していない場合にはＩ（ｊ，Ｋ）Ｐ（Ｋ−ｊ）の復号処理を実行する（ステップＳ２０５）。拡大符号のパリティを受信している場合にはＩ（ｊ，Ｋ）Ｐ（Ｋ−ｊ）の拡大符号の復号処理を実行する（ステップＳ８０５）。【０１２８】
実際には拡大符号によるパリティの追加にも符号設計上、上限が決められている。上限に達した際には第３の実施の形態と同様に同一データの再送処理が実行することを組み合わせて対処することができる。【０１２９】
（第４の実施の形態による効果）
次に、本実施の形態の効果について説明する。【０１３０】
第４の実施の形態によれば、第３の実施の形態の効果に加えて、同一データの再送ではなく追加のパリティを送信するためにスループットを低くした分だけの符号化利得が期待でき、より少ない通信量でデータ伝送処理が可能になる。【０１３１】
（実施例）
以下、本実施の形態にＬＤＰＣ符号を適用した実施例を用いて説明する。【０１３２】
最初にＬＤＰＣ符号の符号特性閾値について説明する。【０１３３】
符号特性閾値はパリティ検査行列の次数分布で決定される、メッセージパッシング復号に起因する符号特性の限界値であり、例えば、非特許文献２及び非特許文献３でも述べられている。【０１３４】
パリティ検査行列の次数分布とは、その行、列における１の個数の分布である（バイナリ符号を仮定）。ＬＤＰＣ符号では、ターゲットの復号誤り率が高い領域での符号化利得はこの閾値で決定される。ハイブリッドＡＲＱのスループットは、フレーム復号誤り率が１／１０から１／１００のかなり高い領域で決定されるため、この符号特性閾値の良い符号を用いることが有効となる。【０１３５】
符号特性閾値の良いＬＤＰＣ符号は、パリティ検査行列の次数分布をイレギュラーにすることによって構成可能なことが知られている。【０１３６】
ただし、本実施の形態では、任意の部分の短縮符号を用いているため、パリティ検査行列において情報ビットに対応する成分の次数分布がレギュラーで、パリティに対応する成分の次数分布をイレギュラー化することによって、短縮時も含めて優れた符号特性閾値を達成するような符号構成が適している。このときＫ回目のパリティ送信における（Ｋ＋１）個の情報ブロックを同一サイズとすれば、対応する短縮符号の符号特性閾値も一致する。【０１３７】
図１２は、本実施の形態に適したＬＤＰＣ符号のパリティ検査行列Ｈの構成例を示している。【０１３８】
図１２のパリティ検査行列Ｈの各成分は同一サイズの正方行列を表していて、「０」は零行列、「１」は置換行列（各行、各列に１が１個ずつ、残りはすべて０）、「３」は各行、列に１が３個ずつある正方行列を示している。【０１３９】
情報ビットに対応するパリティ検査行列Ｈの成分は、列次数３、行次数１２のレギュラーな次数分布となっている。一方、パリティ部分は、列次数６、２、１のため、全体としてはイレギュラーなＬＤＰＣ符号となっている。【０１４０】
列次数６のブロックに対応するパリティは、パンクチャリングを行い、実際には送信しない。このため情報ビットは、１２個のブロック、送信するパリティは３個のブロックとなるので、符号化率は１２／１５＝０．８となる。【０１４１】
符号化（パリティ生成）に関しては、最初の行ブロックを用いれば、列次数６の成分に対応するパリティは、単純にバイナリ加算することによって求めることができる。列次数２の成分は、リピート・アキュムレートの構造であり、アキュムレータを用いて対応するパリティを求めることができる。列次数１の成分に対応するパリティは、次数６の成分に対応するパリティのバイナリ加算から求めることができる。【０１４２】
本発明の実施の形態におけるＩＲ方式のパリティ生成のための情報ブロックＩ（ｊ，Ｋ）の構成例として、図１２に示すパリティ検査行列Ｈに対する構成例を図１３に示す。情報ビット部分は、レギュラーかつ一様な次数分布のため、各レベルで同一の情報ブロックの大きさになるようにする。【０１４３】
パリティ検査行列Ｈの情報ビットは、１２個の情報ブロックに自然に分割でき、これをＪ（０），Ｊ（１），・・・，Ｊ（１１）で表す。また、Ｊ（ａ：ｂ）でＪ（ａ）｜｜Ｊ（ａ＋１）｜｜・・・｜｜Ｊ（ｂ）を表す（｜｜は連結を表す）。【０１４４】
図９は、Ｋ＝０，１，２，３に対する情報ブロックＩ（ｊ，Ｋ）を以下のようにとることを示している。
Ｉ（０，０）＝Ｊ（０：１１）（情報系列全体）
Ｉ（０，１）＝Ｊ（６：１１），Ｉ（１，１）＝Ｊ（０：５）
Ｉ（０，２）＝Ｊ（４：７），Ｉ（１，２）＝Ｊ（８：１１），Ｉ（２，２）＝Ｊ（０：３）
Ｉ（０，３）＝Ｊ（３）｜｜Ｊ（７）｜｜Ｊ（１１），Ｉ（１，３）＝Ｊ（４：６），Ｉ（２，３）＝Ｊ（８：１０），Ｉ（３，３）＝Ｊ（０：２）【０１４５】
Ｉ（０，Ｋ）に対応するパリティ検査行列Ｈの成分をＨ（０，Ｋ）とおく。図１４は図１２のパリティ検査行列Ｈと上記のＩ（０，Ｋ）に対応するＨ（０，Ｋ）を示す。情報部分の最後の行ブロックはオール０のため、Ｈ（０，Ｋ）には含める必要がない。【０１４６】
図５に示す符号化手段３０の中間情報生成手段８０１は、Ｈ（０，Ｋ）に情報ブロックＩ（０，Ｋ）を乗ずる処理を行う。ここで、Ｈ（０，Ｋ）は列次数３と低密度のため、乗算の計算量もＩ（０，Ｋ）の大きさに比例した値となる。パリティＰ（Ｋ）は、中間情報Ｈ（０，Ｋ）Ｉ（０，Ｋ）を用いて上述のパリティ生成手続きを用いて得ることができる。【０１４７】
図１２のパリティ検査行列Ｈに対する図６、図７の送信処理と受信処理の具体例について、図１５の状態遷移図を用いて示す。以下、図１５を説明する。【０１４８】
送信装置では、Ｉ（０，０），Ｐ（０）を送信し、受信装置の復号手段ではこれを受信し、復号を行う（ステップＳ１４００）。この復号に失敗した場合には、受信装置はＲＥＱを送信装置に送り、送信装置はＰ（１）を送信する。【０１４９】
Ｉ（０，１）＝Ｊ（６：１１）とＰ（１）の受信値から復号手段では復号処理を行う（ステップ１４０１）。本実施の形態におけるＬＤＰＣ符号の復号器は短縮符号の復号を行うため、行処理に関して逐次的な処理が可能な装置構成をとることが有効となる。【０１５０】
Ｉ（０，１）の復号が成功した場合には、Ｉ（１，１）＝Ｊ（０：５）の復号を実行する。この復号はＩ（０，０）＝Ｉ（１，１）｜｜Ｉ（０，１）のパリティＰ（０）（受信済み）を利用して実行することができる。【０１５１】
復号の完了したＩ（０，１）の扱いは２通りに分けられる。第１の方法は、Ｉ（０，１）の受信値を復号結果に基づいた十分に信頼度情報の高い値に設定し、通常と同様に復号を行う方法である。第２の方法は、符号化処理と同様に中間情報Ｈ（０，１）Ｉ（０，１）を計算し、この中間情報を行処理の拘束条件としてＩ（１，１）及びＰ（０）の受信値を用いて復号処理を実行する方法である。【０１５２】
次に第３の実施の形態における再送データのブロック生成の具体例を図１６に示す。図１６は図１５と同様に、図１２の符号に対してＫ＝３までの短縮符号化を行う方式においてのデータ再送の例を示している。４個の短縮符号の情報部分Ｉ（０，３），Ｉ（１，３），Ｉ（２，３），Ｉ（３，３）をスライスしたブロックＱ（０），Ｑ（１），Ｑ（２）を生成し、再送要求があった場合にはこれを順次送信する。情報部分の送信が終了してさらに再送要求があった場合にはパリティ部分Ｐ（０）、Ｐ（１），Ｐ（２），Ｐ（３）をスライスしたブロックを生成してこれを送信する。【０１５３】
図１２のパリティ検査行列Ｈに対する図８、図９の送信処理と受信処理の具体例について、図１７の状態遷移図を用いて示す。図１５とは異なり、Ｋ＝３での再送処理が非常に簡潔になる。【０１５４】
次に第４の実施の形態における拡大符号のパリティ生成、送信モデルを図１２の符号に対して表したものを図１８に示す。図１８でＰ（４）、Ｐ（５）、Ｐ（６）、Ｐ（７）はそれぞれＩ（０，３）Ｐ（３），Ｉ（１，３）Ｐ（２）、Ｉ（２，３）Ｐ（１），Ｉ（３，３）Ｐ（０）の拡大符号のパリティ部分を表す。ここで再送要求に対して送信するパリティビットはＰ（４），Ｐ（５），Ｐ（６），Ｐ（７）をスライスしたブロックであるＱ（０），Ｑ（１），…となる。【０１５５】
図１９は図１２の符号の短縮符号Ｉ（ｊ，３）Ｐ（３−ｊ）に対する拡大符号のパリティ検査行列の例を表している。Ｉ（ｊ，３）Ｐ（３−ｊ）はレート１／２の符号であり、それを拡大することによってレート１／４までに対応するような構成である。【０１５６】
以上好ましい実施の形態（及び実施例）を参照して本願発明を説明したが、本願発明は上記実施の形態（及び実施例）に限定されるものでない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１５７】
この出願は、２００７年９月１２日に出願された日本出願特願２００７−２３７０４２と２００７年１１月３０日に出願された日本出願特願２００７−３１０７８２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１５８】
本発明はモバイル通信などにおけるハイブリッドＡＲＱ方式として利用することができる。
【図１】
2009035096.tif 000003
【図２】
2009035096.tif 000004
【図３】
2009035096.tif 000005
【図４】
2009035096.tif 000006
【図５】
2009035096.tif 000007
【図６】
2009035096.tif 000008
【図７】
2009035096.tif 000009
【図８】
2009035096.tif 000010
【図９】
2009035096.tif 000011
【図１０】
2009035096.tif 000012
【図１１】
2009035096.tif 000013
【図１２】
2009035096.tif 000014
【図１３】
2009035096.tif 000015
【図１４】
2009035096.tif 000016
【図１５】
2009035096.tif 000017
【図１６】
2009035096.tif 000018
【図１７】
2009035096.tif 000019
【図１８】
2009035096.tif 000020
【図１９】
2009035096.tif 000021
【図２０】
2009035096.tif 000022
【図２１】
2009035096.tif 000023
【図２２】
2009035096.tif 000024
【手続補正書】
【提出日】平成20年12月22日(2008.12.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
送信装置から受信装置へのエラーに対処するために誤り訂正符号を用いる通信システムにおいて、
前記送信装置は、前記受信装置で復号に失敗した場合の再送要求に対して、誤り訂正符号の情報ビット列を分割した情報ブロック群の中の一つの情報ブロックに対して短縮符号化を行って生成したパリティビット列を送信し、
再送要求時の前記情報ブロック群への分割において、
現時点での各情報ブロックの一部の情報ビットを集めて新たな第１の情報ブロックを生成し、前記短縮符号化は第１の情報ブロックに対して行い、
現時点での各情報ブロックと前記第１の情報ブロックの捕集合から成る情報ブロックと前記第一の情報ブロックによって新たな情報ブロック群を形成する符号化手段を備える、ことを特徴とする通信システム。
【請求項２】
再送要求に対して新たに生成される情報ブロックが同一ブロック長になるように前記第１の情報ブロックを生成する、ことを特徴とする請求項１に記載の通信システム。
【請求項３】
前記受信装置が、
受信した前記情報ビットの復号を、情報ビットの前記情報ブロックの受信値と、それまでに受信した前記誤り訂正符号の受信値と、既に復号済みの情報ビット列とを用いて実行し、
前記情報ビットの情報ブロックの復号に失敗した場合に、前記送信装置に対して再送要求を行う機能を有する復号手段を備えることを特徴とする請求項１又は請求項２に記載の通信システム。
【請求項４】
前記受信装置の前記復号手段が、
前記情報ビットの情報ブロックの復号に失敗した場合に、前記送信装置への再送要求と共に、前記送信装置による前記情報ビットの情報ブロックへの分割に対応して前記情報ビットの情報ブロックへの分割を行うことを特徴とする請求項３に記載の通信システム。
【請求項５】
前記符号化手段が、
情報ビット格納手段と、
前記情報ビット格納手段から情報ビットの前記第１の情報ブロックを取り出す情報ブロック抽出手段と
を有することを特徴とする請求項１から請求項４の何れかに記載の通信システム。
【請求項６】
前記符号化手段が、
再送要求時の前記誤り訂正符号を事前に計算し、誤り訂正符号格納手段に格納し、
再送要求があった場合に、前記誤り訂正符号格納手段から送信する前記誤り訂正符号を選択する機能を有することを特徴とする請求項１から請求項５の何れかに記載の通信システム。
【請求項７】
前記符号化手段が、
前記情報ビットの情報ブロックと対応する誤り訂正符号検査行列成分との積である中間情報を計算する中間情報生成手段と、
前記中間情報を格納する中間情報格納手段と
を有することを特徴とする請求項１から請求項５の何れかに記載の通信システム。
【請求項８】
前記送信装置が、
前記情報ビットの情報ブロックへの分割を予め定められた最大回数まで実行し、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しては既に送信した情報ビット又は誤り訂正符号の再送を行う
ことを特徴とする請求項１から請求項７の何れかに記載の通信システム。
【請求項９】
前記受信装置が、
前記送信装置から前記情報ビット又は誤り訂正符号を受信した場合、前記情報ビット又は誤り訂正符号の値とそれらの以前の受信値との平均化処理であるパケット合成を行う機能を有することを特徴とする請求項８に記載の通信システム。
【請求項１０】
受信装置へのエラーに対処するために誤り訂正符号を用いる送信装置において、
前記受信装置で復号に失敗した場合の再送要求に対して、誤り訂正符号の情報ビット列を分割した情報ブロック群の中の一つの情報ブロックに対して短縮符号化を行って生成したパリティビット列を送信し、
再送要求時の前記情報ブロック群への分割において、
現時点での各情報ブロックの一部の情報ビットを集めて新たな第１の情報ブロックを生成し、前記短縮符号化は第１の情報ブロックに対して行い、
現時点での各情報ブロックと前記第１の情報ブロックの捕集合から成る情報ブロックと前記第１の情報ブロックによって新たな情報ブロック群を形成する符号化手段を備える、符号化手段を備えることを特徴とする送信装置。
【請求項１１】
再送要求に対して新たに生成される情報ブロックが同一ブロック長になるように前記第１の情報ブロックを生成する、ことを特徴とする請求項１０に記載の送信装置。
【請求項１２】
前記符号化手段が、
情報ビット格納手段と、
前記情報ビット格納手段から情報ビットの前記第１の情報ブロックを取り出す情報ブロック抽出手段と
を有することを特徴とする請求項１０又は請求項１１に記載の送信装置。
【請求項１３】
前記符号化手段が、
再送要求時の前記パリティビットを事前に計算し、パリティビット格納手段に格納し、
再送要求があった場合に、前記パリティビット格納手段から送信する前記誤り訂正符号を選択する機能を有することを特徴とする請求項１０から請求項１２の何れかに記載の送信装置。
【請求項１４】
前記符号化手段が、
前記情報ビットの情報ブロックと対応する誤り訂正符号検査行列成分との積である中間情報を計算する中間情報生成手段と、
前記中間情報を格納する中間情報格納手段と
を有することを特徴とする請求項１０から請求項１２の何れかに記載の送信装置。
【請求項１５】
前記送信装置が、
前記情報ビットの情報ブロックへの分割を予め定められた最大回数まで実行し、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しては既に送信した情報ビット又はパリティビットの再送を行う
ことを特徴とする請求項１０から請求項１４の何れかに記載の送信装置。
【請求項１６】
請求項１５記載の送信装置において、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しては前記情報ビットの情報ブロックから一部のビットを集めて構成されるブロック、もしくは送信済みのパリティビットのブロックから一部のビットを集めて構成されるブロックを送信する、
ことを特徴とする送信装置。
【請求項１７】
請求項１６記載の送信装置に対して、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しての受信データの場合にはパケット合成処理を行い、前記情報ビットの情報ブロックの復号を第１番目の前記情報ビットの情報ブロックから順次行う、
ことを特徴とする受信装置。
【請求項１８】
前記情報ビット列の情報ブロックへの分割を予め定められた最大回数の再送要求までは実行し、
前記最大回数を超えた再送要求に対しては前記情報ブロックと送信済みの前記パリティビットに対応する短縮符号に対する拡大符号としてパリティビットを生成し、
前記情報ブロックに対応する拡大符号で生成されるパリティビットを複数の情報ブロックから集めてブロックを生成し、再送要求に対して送信する、ことを特徴とする請求項１０から請求項１６の何れかに記載の送信装置。
【請求項１９】
請求項１８記載の送信装置に対して、
前記最大回数を超えた前記誤り訂正符号の再送要求に対しての受信データの場合にはパケット合成処理を行い、前記情報ビットの情報ブロックの復号を第１番目の前記情報ビットの情報ブロックから順次行う、
ことを特徴とする受信装置。
【請求項２０】
誤り訂正符号として情報部分の次数分布がレギュラーである低密度パリティ検査符号を用いる、ことを特徴とする請求項２に記載の通信システム。
【請求項２１】
誤り訂正符号として情報部分の次数分布がレギュラーである低密度パリティ検査符号を用いる、ことを特徴とする請求項１１に記載の送信装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
［図１３］符号化および復号に使用する、情報ブロックに対応する図１０のパリティ検査行列の成分を説明する図である。
［図１４］図１０のパリティ検査行列を用いた場合の第２の実施の形態に基づく受信装置の処理フローを復号手段の処理に基づき表している。
［図１５］図１１のパリティ検査行列に対して第３の実施の形態に基づく場合の再送ブロックの形態例を説明する図である。
［図１６］図１１のパリティ検査行列に対して第３の実施の形態に基づく場合の受信装置の処理フローを復号手段の処理に基づき表している。
［図１７］図１１のパリティ検査行列に対して、再送レベルＫ＝３における短縮符号に対する拡大符号のパリティ検査行列の構成例を示す図である。
［図１８］図１１のパリティ検査行列に対して第４の実施の形態に基づく場合の再送ブロックの形態例を説明する図である。
［図１９］図１２の符号の短縮符号に対する拡大符号のパリティ検査行列の例を表す図である。
［図２０］符号のパンクチャリングを現す模式図である。
［図２１］パンクチャリングに基づくＩＲ方式における符号化手段の構成例を示すブロック図である。
［図２２］ＩＲ方式に基づくハイブリッドＡＲＱの送信装置と受信装置の処理内容を説明する図である。
［発明を実施するための最良の形態］
［００４０］
次に、本発明の実施の形態について図面を参照して詳細に説明する。
（第１の実施の形態）
［００４１］
図１は、本発明の実施の形態よるハイブリッドＡＲＱ方式の通信システムにおける送信処理の内容を説明するフローチャートである。
［００４２］
本発明の実施の形態におけるＩＲ方式では、基本的に最初の送信時と同一の大きさのパリティビットを送信するスキームを考える。なお、本発明の実施の形態では、非特許文献１等に記載されるパンクチャリングや拡大に基づくＩＲ方式と組み合わせて適用することも可能である。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
［００４３］
ここで、送信回数を示すインデックスをＫとする（Ｋ＝０，１，・・・）。本実施の形態では、ある符号語に対してのＫ回目の送信要求に対して情報ビットを（Ｋ＋１）個のブロックに分割して、その１個のブロックに対してのパリティを生成し、送信する。つまり、そのブロック以外の情報ビットを「０」とする短縮符号化を行い、パリティを計算する。単なる短縮であるため、符号化におけるパリティ生成は同一の処理によって実行可能である。
［００４４］
以下、図１に従って、本実施の形態における送信装置から１個の符号語を送信する場合の符号化手段の処理動作について説明する。
［００４５］
最初に、符号語における情報ビット列Ｉを送信する（ステップ１０１）。
［００４６］
次に、送信回数インデックスＫを「０」にセットし、Ｋ回目の送信における情報ビット列Ｉのブロック（情報ブロック）をＩ（ｊ，Ｋ）とする（ｊ＝０，１，・・・，Ｋ）（ステップ１０２）。ここで、Ｉ（０，０）は情報ビット列そのものである。
［００４７］
情報ブロックＩ（０，Ｋ）の短縮符号化を行い、パリティＰ（Ｋ）を生成する（ステップ１０３）。
［００４８］
生成したパリティＰ（Ｋ）を送信する（ステップ１０４）。
［００４９］
受信装置からのフィードバックを受け取る（ステップ１０５）。ここで、受信装置からのフィードバックがＡＣＫ（確認応答）である場合には、処理を終了し、次の符号語の送信処理に移行する。
［００５０］
受信装置からＲＥＱ（再送要求）を受け取った場合には、情報ブロックＩ（ｊ，Ｋ）（ｊ＝０，１，・・・，Ｋ）の一部を集めて情報ビットのブロックＩ（０，Ｋ＋１）を構成する（ステップ１０６）。
［００５１］
次に、Ｉ（ｊ，Ｋ）からＩ（０，Ｋ＋１）との共通部分を除いた補集合に対して、Ｉ（ｊ，Ｋ＋１）←Ｉ（ｊ＋１，Ｋ）＼Ｉ（０，Ｋ＋１）とインデックスをつける（ステップ１０７）。
［００５２］
そして、送信回数インデックスＫをＫ＋１とし、ステップ１０３に戻る（ステップ１０８）。
［００５３］
図２は、図１の符号化手順に対する受信装置における復号手段における処理動作を示すフローチャートである。
［００５４］
まず、送信回数インデックスＫを「０」とし、情報ビットに対する受信値を設定し、情報ビット列を受信する（ステップ２０１、２０２）。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
［００８１］
本実施の形態による送信装置と受信装置のハードウェア構成を示す。
［００８２］
本実施の形態による送信装置と受信装置は、一般的なコンピュータ装置と同様のハードウェア構成によって実現することができ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３０１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等のメインメモリであり、データの作業領域やデータの一時退避領域に用いられる主記憶部３０２、データの送受信を行うインタフェース部３０３、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、磁気ディスク、半導体メモリ等の不揮発性メモリから構成されるハードディスク装置である補助記憶部３０４、上記各構成要素を相互に接続するシステムバス３０５等を備えている。
［００８３］
本実施の形態による送信装置と受信装置は、符号化手段と復号化手段の処理動作を、内部にそのような機能を実現する通信プログラムを組み込んだ、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）等のハードウェア部品からなる回路部品を実装してハードウェア的に実現することは勿論として、上記通信プログラムを、ＣＰＵ３０１で実行することにより、ソフトウェア的に実現することも可能である。
［００８４］
すなわち、ＣＰＵ３０１は、補助記憶部３０４に格納されているプログラムを、主記憶部３０２にロードして実行し、符号化手段と復号化手段の処理動作をソフトウェア的に実現する。
［００８５］
（第１の実施の形態による効果）
次に、本実施の形態の効果について説明する。
［００８６］
本実施の形態によれば高符号化率をターゲットに設計された符号を使用するため、その復号計算量をパンクチャリングによる方法よりも改善することができる。例えば、符号化率０．８をターゲットに設計したＬＤＰＣ符号の復号計算量は、符号化率０．５で設計したＬＤＰＣ符号をパンクチャリングによって符号化率０．８とした場合と比較して数分の１程度になる。
［００８７］
本実施の形態では、短縮符号によって広範囲な符号化率対して良い特性を達成する符号を利用することが有効であるが、これもＬＤＰＣ符号を用いて実現することができる。本実施の形態では、追加のパリティを再送した場合、復号の単位となる符号
【国際調査報告】
2009035096.tif 000025
2009035096.tif 000026
2009035096.tif 000027
2009035096.tif 000028