(57)【特許請求の範囲】
【請求項１】
情報アルファベットにパリティアルファベットを追加してなる組織符号を送受信するシステムにおける符号化方法おいて、
K個の情報アルファベットにK0個の所定パターンのダミーアルファベットを追加してK1（=K+K0）個の第１の情報アルファベットを発生するステップ、
該K1個の第１情報アルファベットから作成されるM個のパリティアルファベットを該K1個の第１情報アルファベットに追加するとともに、K0個の前記所定パターンのダミーアルファベットを削除してN（=Ｋ＋Ｍ）個のアルファベットの組識符号を生成するステップ、
を備え、前記ダミーアルファベットの所定パターンとして移動端末に異なるパターンを割り振り、所定の移動端末の所定パターンを用いて符号化して該符号化データを該移動端末へ送信する、
ことを特徴とする符号化方法。
【請求項２】
情報アルファベットにパリティアルファベットを追加してなる組織符号を送受信するシステムにおける符号化装置おいて、
K個の情報アルファベットにK0個の所定パターンのダミーアルファベットを追加してK1（=K+K0）個の第1の情報アルファベットを発生するダミーアルファベット追加部、
該K1個の第１情報アルファベットから作成されるM個のパリティアルファベットを該K1個の第１情報アルファベットに追加するとともに、K0個の前記所定パターンのダミーアルファベットを削除してN（=Ｋ＋Ｍ）個のアルファベットの組識符号を生成する組織符号生成部、
該組識符号を移動端末に送信する送信部
を備え、前記ダミーアルファベット追加部は、前記ダミーアルファベットの所定パターンとして移動端末に異なるパターンを割り振り、所定の移動端末に応じたパターンのダミーアルファベットを前記K個の情報アルファベットに追加して前記第１の情報アルファベットを発生し、前記送信部は、該第１の情報アルファベットより前記組織符号生成部で生成された組識符号を移動端末に送信する、
ことを特徴とする符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報アルファベットにパリティアルファベットを追加してなる組織符号を送受信するシステムにおける符号化方法及び符号化装置に関する。
【背景技術】
【０００２】
・組識符号およびブロック符号
一般に、ｑ個の異なる値を有する情報アルファベット（典型例はq=2のビット）を用いる符号化は、図３５に示すようＫ個の情報アルファベット(情報ビット)を1組のブロックI1として、このブロックの可能な全てのパターン（qK通りある）に対して、Ｋより大きいＮ個の符号アルファベット(符号ビット)のブロックI2を１対１に対応させる。
このとき、情報アルファベットと符号アルファベットの組が同じで、N個の符号のうちＫ個を元の情報アルファベットにより構成されるような符号を組識符号という。残りのM=N−K個のアルファベットはパリティアルファベットと呼ばれ、通常は情報アルファベットに対して加算等の規定の処理を行って得られる。
すなわち、Nビットで構成される符号語の構成ビットのうち、Ｋビットが情報で残りのＭ（＝Ｎ−Ｋ）ビットが誤り検出や訂正のためのパリティビットである符号をブロック符号といい、符号語の始めのＫビットが情報ビットで、その後に(Ｎ−Ｋ)ビットのパリティビットが配列されているブロック符号を組識符号という。
【０００３】
送信側において、K個の情報アルファベットｕ=（ｕ0，ｕ1，．．．，ｕK-1）にK×Nの生成行列
Ｇ＝（ｇij）；ｉ＝０，．．．，K−1； ｊ＝０，．．．，Ｎ−１
を用いて、次式
ｘ＝ｕＧ (1)
によりＮ個の符号アルファベットｘ=（ｘ0，ｘ1，．．．，ｘN-1）を生成すれば、この符号アルファベットがブロック符号になり、情報アルファベットｕはブロック符号化される。
受信側では符号ベクトルｘに対しての受信データから情報アルファベットｕを推定する。このためには、ｘに対しての以下のパリティチェック関係式
ｘＨT＝０ (2)
を用いる。ここで、
Ｈ＝（ｈij）；ｉ＝０，．．．，M−1； ｊ＝０，．．．，N−1
はパリティ検査行列で、ＨTはＨの転置（行と列の入れ替え）を意味する。(1)，(2)式からＨとＧは以下の関係を満たす。
ＧＨT＝０ (3) 
これから、ＨとＧのいずれか一方が与えられると符号化規則が一意に決まる。
【０００４】
図３６は送信機においてブロック符号化し、受信機において復号する通信システムの構成図であり、送信機１はKビットよりなる情報ｕを符号化してNビットのブロック符号ｘを生成する符号部１ａと該ブロック符号を変調して送信する変調部１ｂを備えている。受信機２は伝送路３を介して受信した信号を復調する復調部２ａとＮビットの受信情報より元の送信されたＫビットの情報を復号する復号部２ｂを備えている。
符号部１はＭ（＝Ｎ−Ｋ）個のパリティビットｐを生成するパリティ生成器１ｃとＫビットの情報ｕとＭビットのパリティビットｐを合成してＮ（＝Ｋ＋Ｍ）個のブロック符号ｘを出力するＰ／Ｓ変換部１ｄを備えている。符号部１ａは(1)式に従ってブロック符号ｘを出力するもので、一例としてｘを組識符号とすれば、符号部１ａは数式的に図３７に示す生成行列Ｇで表現できる。復号部２ａは受信尤度データｙに誤まり検出訂正処理を施して元の送信されたＫビットの情報を復号して推定情報を出力する復号器２ｃを備えている。送信機１より送信されたブロック符号ｘは伝送路３の影響を受けて復号器２ｃに送信されたままの状態で入力せず、尤度データとして復号器２ｃに入力する。尤度データは符号ビットが０か1かの信頼度と符号（＋１であれば０、−1であれば１）から成る。復号器２ｃは各符号ビットに対する尤度データを基に規定の復号処理を行い、情報ビットｕの推定を行う。復号部２ａは(2)式に従って復号するもので、一例としてｘを組識符号とすると共に生成行列Ｇを図３７示す行列とすれば、復号部２ｂは図３８に示すパリティ検査行列Ｈの転置行列で表現できる。
【０００５】
・LDPC符号
LDPC符号（Low-Density Parity-Check符号）は、ブロック符号において０と異なる要素の数（ｑ＝２の場合には１の数）が全要素数に対して少ない割合の検査行列Ｈによって定義される符号の総称である。
特に、検査行列Ｈの行と列のそれぞれにおける要素の数（１の数）が一定の場合には「レギュラーLDPC符号」と呼ばれ、符号長Ｎと、列と行のそれぞれの要素数であるウェイト数（ｗc，ｗr）とで特徴付けられる。一方、検査行列Ｈの各列、各行で異なるウェイト数を許すタイプは、「イレギュラーLDPC符号」と呼び、符号長Ｎと、列と行のウェイト数分布（（λj，ρk）；ｊ＝１，．．，ｊmax；ｋ＝１，．．．，ｋmax））とにより特徴付けられる。ここで、λjはウェイト数ｊの列に属する0と異なる要素数（１の数）の全体に対する割合を示している。図３９はウェイト数分布の説明図であり、M×Nの検査行列Ｈにおいて、1の数がｊ個の列数をNjとし、検査行列Ｈにおける１の総数をＥとすれば、ウェイト数分布λjは
λj＝ｊ×Nj／Ｅ
であり、1の数がｊ個の列数の全列に対する割合ｆjは
ｆj＝Nj／Ｎ
である。たとえば、ｊ＝３，Nj＝４とすれば、λ3＝12／Ｅであり、ｆj＝４／Ｎ
である。ρkはウェイト数ｋの行に属する0と異なる要素数（１の数）の全体に対する割合を示しており、λjと同様に定義できる。なお、レギュラーLDPC符号はイレギュラーLDPC符号の特別な場合とみなすこともできる。
LDPC符号はレギュラー、イレギュラーいずれにしても符号長Ｎとウェイト数分布が決まっただけでは具体的な検査行列は一意に決まらない。換言すれば、規定のウェイト分布を満たすような具体的な「１」の配置方法（「０」と異なる要素の配置方法）は多数存在する可能性があり、それぞれが別の符号を定義することになる。そして、符号の誤り率特性は、ウェイト数分布と、該ウェイト数分布を満たす検査行列における具体的な１の配置の仕方に依存する。なお、符号器および復号器の回路規模、処理時間、処理量等は基本的にウェイト数の分布のみにより影響される。
【０００６】
・ターボ符号
ターボ符号は組織符号であり、最大事後確率復号(MAP復号: Maximum A Posteriori Probability Decoding)を採用することにより復号繰り返し回数を重ねる毎に復号結果の誤りを減少することができる。
図４０はターボ符号器及びターボ復号器を含む通信システムの構成図におけるターボ符号部1aの構成図、図４１はターボ復号部2bの構成図である。
図４０において、ｕ（＝[u1,u2,u3,..,uN]）は伝送する長さNの情報データ、ｘa，ｘb，ｘcはターボ符号部１aで情報データｕを符号化した符号化データ、ｙa，ｙb，ｙcは符号化データｘa，ｘb，ｘｃが通信路3を伝搬し、雑音やフェージングの影響を受けた受信信号、ｕ′はターボ復号部2bにおいて受信データｙa，ｙb，ｙcを復号した復号結果である。ターボ符号部1aにおいて、符号化データｘaは情報データｕそのものであり、符号化データｘbは情報データｕを符号器ENC1で畳み込み符号化したデータ、符号化データｘcは情報データｕをインタリーブ（π）して符号器ENC2で畳み込み符号化したデータである。すなわち、ターボ符号は、要素符号を２つ以上用いて合成した組織符号で、ｘaは情報ビット、ｘb，ｘcはパリティビットである。P/S変換部1dは符号化データｘa，ｘb，ｘcを直列に変換して出力する。
図４１ターボ復号部2bにおいて、第１の要素復号器DEC1は受信信号ｙa，ｙb，ｙcのうち、ｙaとｙbを使って復号を行う。要素復号器DEC1は軟判定出力の要素復号器であり、復号結果の尤度を出力する。次に、第２の要素復号器DEC2は第１の要素復号器DEC1から出力された尤度とｙcとを用いて同様の復号を行う。第２の要素復号器DEC2も軟判定出力の要素復号器であり、復号結果の尤度を出力する。この場合、ｙcは原データｕをインタリーブしたものを符号化したｘcに対応する受信信号なので、第１の要素復号器DEC1から出力される尤度は第２の要素復号器DEC2に入力する前にインタリーブ（π）する。第２の要素復号器DEC2から出力された尤度はデインタリーブ（π-1）された後、第１の要素復号器DEC1への入力としてフィードバックされる。なお、第２の要素復号器DEC2のデインタリーブ結果を"0","1"の硬判定した結果が、ターボ復号結果（復号データ)ｕ′となる。以後、上記の復号操作を所定回数繰り返し行うことにより、復号結果u′の誤り率が低減する。かかるターボ要素復号器における第１、第２の要素復号器DEC1,DEC2としてMAP要素復号器を使用することができる。
【０００７】
・パンクチャリング
情報長Ｋ、符号長Ｎ1の符号C1が与えられているとすると、符号C1の符号化率はR1=K/N1である。この符号C1を用いてR1よりも符号化率が大きな符号を構成したい場合があり、パンクチャリングが行われる。すなわち、図４２に示すように送信機はＮ1個の符号ビットのうちにN0個のビットを取り除いて符号長をN（=N1−N0）として送信する。受信機は、取り除かれたビット位置が既知であるから、各ビットが等確率となるようにデータを補完して復号処理を行って符号C1を推定する。このパンクチャリングにおいて符号化率はR=K/N（＞R1）となる。
・レペティション
情報長Ｋ、符号長N1の符号C1が与えられているとき、この符号C1を用いて符号化率がR1（＝K/N1）よりも小さい符号を構成したい場合があり、レペティションが行われる。すなわち、図４３に示すように送信機はN1個の符号のうち幾つかのアルファベットについて(パリティに限らず)1回以上繰り返したアルファベットを全部でN0個追加して、N（=N1+N0）個の符号アルファベットの符号として送信する。受信機は繰り返しアルファベットのデータについて、それぞれダイバーシチ合成し(最も簡単には加算するだけ)、符号C1についての復号を行う。
・LDPC符号のヌリング
LDPC符号のヌリング法は、符号化率R（ただし、R＜R1）を調整するために図４４に示すようにK個の情報ビットの先頭にK0個のall 0(オール０)のビットを設定して符号化および復号処理を行う（非特許文献１参照）。LDPC符号のヌリング法において符号化率はR1＝(K0+K)/N1である。符号化率R1の符号の検査行列を特徴付けるウェイト分布係数Lj(R1)は、密度発展法（Density Evolution）で与えられる(非特許文献２参照)。
ところで、符号化率R(=K/N)の符号は、Kビットの情報ビットの先頭にK0個のall 0の情報ビットを追加してK1×N1の生成行列を用いて符号化して送信し、受信側でＭ×N1検査行列の始めからK0列を除いたM×Ｎ検査行列により復号することと等価である。このことから、符号化率RのLDPC符号のM×Ｎ検査行列のN列についてのウェイト数分布Lj(R)は
【数１】
0004425282.tif 000002
となるようにする。なお、パリティ数Mが変わらないことからM=N−K=N1−K1であり、
【数２】
0004425282.tif 000003
という関係がある。なお、LDPC符号のヌリング法ではK1×N1の生成行列を用いて符号化した符号の送信の仕方については何も規定がない。
【０００８】
・フィラービット追加（コードセグメンテーション）
3GPPによる第３世代無線移動通信システムIMT-2000のW-CDMAシステムではターボ符号によってデータを符号化することが標準化されている。そこで、情報ビットサイズが40ビットに満たない場合に情報ビットを40ビットにするために、あるいは、情報ビットサイズが5114を越えるような大きなサイズの場合に、なるべく同じサイズになる複数のブロックに分割して、半端な数を合わせるために図４５に示すように先頭に0の値のビットをフィラービット(filler bit)として挿入する。そして、それぞれのブロックを符号化し、フィラービットも含めて変調して伝送する。
従って、所定ビットを付加して符号化する点で図４４と同様であるが、こちらは、符号化率があまり変化しないようなビット数となっている。
・課題
(1) 同じフォーマット（符号長Ｎ、情報長Ｋ）の符号化を行う場合、符号化法によって誤り率特性が異なる。情報通信システムにおいて、実装のための回路規模や処理量が同程度で、ビットあたりの電力が同じであれば、なるべく誤り率が小さくなるような符号化法を選択する必要がある。
特にLDPC符号に関しては、同じフォーマット（符号長Ｎ、情報長Ｋ）で特性を良くしようとすると、検査行列Ｈのウェイト分布の最適化処理が必要で、これには複雑な数値計算を行う必要がある。なお、必要な符号化率の符号で簡単に実装できる符号が必ずしも特性的に最適な符号となっているとは限らない。
(2) 情報通信システムにおいて、データ伝送に複数のフォーマット（符号長、情報長）を適応的に用いるような場合、異なるフォーマットのそれぞれにあわせた符号器を用意する必要があり、回路規模が大きくなる。レートマッチング法では、前述のように１つの符号化率に対応する符号（「母符号」と呼ぶ）のみの符号器を用意し、該符号器で符号化した符号から一部を取り除く（パンクチャリング）か、繰り返す（レペティション）ことで、異なるフォーマットに対応させ、これにより回路規模を削減する。
しかし、レートマッチング法では、符号化率が小さな符号を母符号とし、これから他の符号化率がより大きな符号を用意するためにパンクチャリングを用いるが、パンクチャリングは復号に必要な情報を削除するため特性劣化が大きくなる問題がある。逆に符号化率が大きな符号を用意してレペティションにより符号化率の小さな符号を用意する場合は、符号長が小さい符号での復号となるために特性が十分に得られない問題がある。
また、もし符号器および復号器において同じフォーマットの符号を用いることに限定するならパンクチャリング（図４２参照）では、符号化、復号処理において削除するアルファベットに対しての処理(削除、推定)を行う必要がある。一方、レペティション（図４３）では、繰り返しアルファベットのデータは伝送路を通して送信する必要がありそのためのリソースが必要になる。
(3) 上記課題(1)、(2)を解決するために従来例の「ヌリング法」を適用することが考えられる。しかし、従来のヌリング法は付加したall “0”をも伝送して復号処理をするものであるため、伝送誤りにより信頼度が低下し、復号誤りが大きくなる問題がある。
(4)また、従来のヌリング法は、all 0のパターンに限定しており、符号定義の自由度を有効に使用してない問題がある。
（5)又、ヌリング法において検査行列のウェイト分布は母符号のウェイト分布Lj(R1)から符号化率に基づいて(4)式により調整を行うものである。しかし、これは与えられた符号化率に対して最適な特性を与える分布になっていない問題がある。
(6) 従来のフィラービットを追加する方法ではフィラービットをそのまま伝送するため無駄な伝送コストが必要になる問題がある。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】T.Tian, C.Jones, and J.D.Villasenor "Rate-Compatible Low-Density Parity-Check Codes", submitted to Int. Sym， on Information Theory, 2004.
【非特許文献２】S.Chung, T. Richardson, and R. Urbanke "Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation" IEEE Trans, Inform. Theory, vol.47, pp.657-670, Feb.2001
【発明の概要】
【発明が解決しようとする課題】
【００１０】
以上より、本発明の目的は、情報ビットにダミービットを付加して符号化する符号化方法、復号方法およびそれらの装置において誤り率特性を向上することである。
本発明の別の目的は、レートマッチング法における問題を生じることなく、複数の符号化率の符号を1つの符号器によって実現することである。
本発明の別の目的は、与えられた符号化率の与えられたウェイト分布のLDPC符号に対して最適なダミービットの分布を実現することである。
本発明の別の目的は、ダミービットのビットパターンを違わせることにより異なる符号を定義し、これにより符号の自由度を大きくし、符号の最適化を実現し、あるいは複数端末の認証などの用途を実現することである。
本発明の別の目的は、ダミービットを送信側から受信側に送信しないようにして送受信機の電力消費および伝送路の使用帯域を削減することである。
本発明の別の目的は、ダミービットを送信側から受信側に送信せず、受信側で尤度を最大にしたダミービットを受信データに追加して復号することにより復号誤りを減少することである。
【課題を解決するための手段】
【００１１】
本発明は、情報アルファベットにパリティアルファベットを追加してなる組織符号を送受信するシステムにおける符号化方法および符号化装置である。
・符号化方法
本発明の符号化方法は、K個の情報アルファベットにK0個の所定パターンのダミーアルファベットを追加してK1（=K+K0）個の第１の情報アルファベットを発生するステップ、該K1個の第１情報アルファベットから作成されるM個のパリティアルファベットを該K1個の第１情報アルファベットに追加するとともに、K0個の前記所定パターンのダミーアルファベットを削除してN（=Ｋ＋Ｍ）個のアルファベットの組識符号を生成するステップを備え、前記ダミーアルファベットの所定パターンとして移動端末に異なるパターンを割り振り、所定の移動端末の所定パターンを用いて符号化して該符号化データを該移動端末へ送信する。
・符号化装置
本発明の符号化装置は、K個の情報アルファベットにK0個の所定パターンのダミーアルファベットを追加してK1（=K+K0）個の第1の情報アルファベットを発生するダミーアルファベット追加部、該K1個の第１情報アルファベットから作成されるM個のパリティアルファベットを該K1個の第１情報アルファベットに追加するとともに、K0個の前記所定パターンのダミーアルファベットを削除してN（=Ｋ＋Ｍ）個のアルファベットの組識符号を生成する組織符号生成部、該組識符号を移動端末に送信する送信部を備え、前記ダミーアルファベット追加部は、前記ダミーアルファベットの所定パターンとして移動端末に異なるパターンを割り振り、所定の移動端末に応じたパターンのダミーアルファベットを前記K個の情報アルファベットに追加して前記第１の情報アルファベットを発生し、前記送信部は、該第１の情報アルファベットより前記組織符号生成部で生成された組識符号を移動端末に送信する。
【発明の効果】
【００１２】
本発明によれば、符号化率が大きな符号を用いて、符号化率が小さい符号の符号化が可能になる。また、本発明によれば、１つの符号化率の符号を実装するだけで、複数の符号化率の符号化に対応でき、回路規模を削減することができる。また、ダミービットの自由度を利用することにより簡易に同じ符号化率の異なる符号を構成できる。
また、本発明によれば、ダミービットを削除して変調し伝送することで、送受信機の電力消費および伝送路容量の使用を削減することができる。
また、本発明によれば、ダミービットを受信側に送信せず、受信側で尤度を最大にしたダミービットを受信データに追加して復号することにより復号誤りを減少することができる。また、本発明によれば、各移動端末へのみ所定の情報を送信することができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の符号化方法の説明図である。
【図２】情報アルファベットにパリティビットを追加してなる組織符号を送受信する無線通信システムの構成図である。
【図３】本発明の生成行列Ｇ1、検査行列Ｈ1の説明図である。
【図４】タナーグラフの説明図である。
【図５】タナーグラフの別の説明図である。
【図６】検査行列Ｈの0番目の列が［１１１０００．．．０］Tである時のタナーグラフのサブグラフである。
【図７】検査行列Ｈの0番目の行が［１１１０１００．．．０］である時のタナーグラフのサブグラフである。
【図８】Sum-Product algorithm (SPA)で使用する用語の定義説明図である。
【図９】メッセージｑij(b)、ｒji(b)の説明図である。
【図１０】ダミービットの追加位置の説明図である。
【図１１】K0個のダミービットの挿入位置を等間隔とした場合の配置方法説明図である。
【図１２】ダミービット追加部の構成図である。
【図１３】第３実施例の最適なダミービット追加位置の決定法説明図である。
【図１４】第３実施例のダミービット追加位置決定処理フローである。
【図１５】第４実施例のダミービット追加位置決定処理フローである。
【図１６】第５実施例の説明図である。
【図１７】第６実施例の符号器の構成図である。
【図１８】第７実施例の復号器の構成図である。
【図１９】第７実施例の対数尤度比を用いたSum-Product algorithm (SPA)の第1の処理フローである。
【図２０】第７実施例の対数尤度比を用いたSum-Product algorithm (SPA)の第２の処理フローである。
【図２１】第８実施例のターボ符号を用いた符号化／復号方法説明図である。
【図２２】移動通信システムにおける符号器であるターボ符号器の構成図である。
【図２３】移動通信システムにおける復号部の構成図である。
【図２４】第８実施例の第１変形例の符号化／復号方法説明図である。
【図２５】第１変形例の無線通信システムは構成図である。
【図２６】第８実施例の第２変形例の符号化／復号方法説明図である。
【図２７】第2変形例の効果説明図である。
【図２８】第２変形例の無線通信システムは構成図である。
【図２９】第３変形例の符号化／復号方法説明図である。
【図３０】第３変形例の無線通信システムは構成図である。
【図３１】第4変形例の符号化／復号方法説明図である。
【図３２】第4変形例の無線通信システムは構成図である。
【図３３】第5変形例の符号化／復号方法説明図である。
【図３４】第5変形例の無線通信システムは構成図である。
【図３５】組識符号およびブロック符号説明図である。
【図３６】送信機においてブロック符号化し、受信機において復号する通信システムの構成図である。
【図３７】符号部の生成行列Ｇの説明図である。
【図３８】復号器の検査行列Ｈの説明図である。
【図３９】ウェイト数分布の説明図である。
【図４０】ターボ符号器及びターボ復号器を含む通信システムの構成図である。
【図４１】ターボ復号器の構成図である。
【図４２】パンクチャリング説明図である。
【図４３】レペティション説明図である。
【図４４】LDPC符号のヌリング法説明図である。
【図４５】フィラービット追加の説明図である。
【発明を実施するための最良の形態】
【００１４】
（Ａ）第１実施例
（ａ）符号化方法
図１は情報アルファベットにパリティアルファベットを追加してなる組織符号を送受信するシステムにおける符号化方法の説明図である。以下では説明上q=2とし、アルファベットという用語に代えてビットという言葉を用いるが、本発明はｑ＝２に限るものではない。
K個の情報ビット１００にK0個の所定パターンのダミービット２００を追加してK1（=K+K0）個の第１情報ビットにする。なお、ダミービットはオール１のパターンあるいは１と０を交互に繰返す１０１０．．．１０パターンなど特定のパターンに限らず、所定のパターンを使用することができる。このことは、以下の全ての実施例においても同様である。
ついで、該K1個の第１情報ビットを用いて作成されたM個のパリティビット３００をK1個の前記第１情報ビットに追加してN1(=K1＋M)個の第2情報ビットを発生する(組識符号化)。ついで、該第2情報ビットからK0個のダミービット２００を削除してN（=Ｋ＋Ｍ）ビットの組識符号４００を発生する。以上により符号化した組識符号を送信機より受信機に送信し、受信機において復号する。
【００１５】
（ｂ）無線通信システム
図２は情報アルファベットにパリティビットを追加してなる組織符号を送受信する無線通信システムの構成図である。送信機１０の符号化部１１は信頼度の高い伝送を行うために情報ビットｕに対して前方誤り訂正符号化（FEC：Forward Error Correction）を適用し、変調部１２は結果の符号ビットｘの変調を行い、受信機２０へ無線伝送路３０を通して送信する。受信機２０の復調部２１は受信データを復調し、符号ビットが0か1かの信頼度と硬判定符号（+1→0，−1→1）からなる尤度データｙを復号部２２に入力する。復号部２２は各符号ビットに対する尤度データをもとに規定の復号処理を行い、情報ビットｕの推定を行う。FECの符号C1としてLDPC符号を用い、符号のタイプを組織符号とする。尚、FEC符号としてターボ符号を用いることができ、第8実施例において説明する。
送信機１０の符号化部１１におけるダミービット追加部１１ａは、K個の情報ビットｕにK0個のランダムに選択した０，１のビットを、ランダムに選択した位置にダミービットとして追加して、K1=K+K0個の情報ビット
（ｕ，ａ）=（ｕ0，．．，ｕK-1，ａ0，．．，ａK0-1）
を出力する(図１参照)。符号器１１ｂはK1×N1の生成行列
Ｇ1＝（ｇ1ij）；ｉ＝０〜K1−1； ｊ＝０〜N1−1
を用いて次式
（ｕ，ａ）Ｇ1
によりＮ1（＝K+K0+M）個の情報ビットｘ1（ｕ，ａ，ｐ）を出力する。ただし、ｐはＭ個のパリティビットで、
ｐ＝（ｐ0，．．，ｐM-1）
である。
ダミービットを挿入しない時のK×Ｎの生成行列Ｇが図３（A）であるとすれば、上記のK1×N1の生成行列Ｇ1は図３（B）に示すようになり、パリティビットｐは
ｐ＝（ｕP，ａQ）
となる。また、復号において使用する検査行列Ｈ1は図３（Ｃ）に示すようになる。
ダミービット削除部１１ｃは、符号器１１ｂから出力するN1個の情報ビットｘ1（ｕ，ａ，ｐ）からK0個のダミービットａを削除してＮ個の情報ビット
ｘ=（ｕ，ｐ）＝（ｘ0，ｘ1，．．．，ｘN-1）
を生成する。変調部１２はこの情報ビットｘに変調を加えて送信する。
符号器１１ｂは以上の原理で情報ビット（ｕ，ａ，ｐ）を出力するが、実際には、パリティ生成器11b-１がK1個の情報ビット（ｕ，ａ）を入力されてM個のパリティビットｐを作成し、合成部11b-2がK1個の情報ビット（ｕ，ａ）とM個のパリティビットｐを合成してN1個の情報ビット（ｕ，ａ，ｐ）を出力する。
【００１６】
受信機２０の受信部２１は伝送路３０を通り雑音を付加されたデータを受信して復調し、各符号ビットに対しての尤度データ
ｙ＝（ｙ0，ｙ1，．．．，ｙN-1）
を復号部２２に入力する。復号部２２のダミービット尤度追加部２２ａは、送信機で付加したダミービットに対応する確率１の尤度データａを追加してN1(＝N+K0)個の尤度データとして復号器２２ｂへ入力する。復号器２２ｂはN1個の尤度データ（ｙ，ａ）に対して、LDPC復号処理あるいはターボ復号処理を行い情報ビットの推定結果を出力する。なお、LDPC復号処理の場合には、周知のSum-Product法により復号処理を行い情報ビットの推定結果を出力する。
符号化部１１は、最大符号化率R1(=(K+K0)／N1)の符号化が可能となるように実装する。K0を変更して複数の符号化率の符号を実現する場合、該符号化率のサイズに応じた符号を符号化部１１より適宜出力する。このようにすれば、レートマッチング法における問題を生じることなく、複数の符号化率の符号を1つの符号器によって実現することができる。
【００１７】
（ｃ）Sum-Product法
・タナーグラフ(Tanner graph) 
Sum-Product法を理解する上でタナーグラフが便利である。タナーグラフは,図４（A）に示すようにＭ×Ｎの検査行列の各行に対応させてM個のチェックノードｆ0，ｙ1，．．．，ｆM-1を上段に配列し、また各列に対応させてＮ個の変数ノードｃ0，ｃ1，．．．，ｃN-1を下段に配列し、ｉ行ｊ列のマトリクス交点が１の場合、チェックノードｆiと変数ノードｃj間をエッジで接続したものである。例えば、検査行列Ｈが図４(Ｂ)であるとすれば、タナーグラフは,図４（Ｃ）に示すようなる。
変数ノードｃ0，ｃ1，．．．，ｃ5には、尤度データｙ＝（ｙ0，ｙ1，．．．，ｙ5）が入力する。ｙ＝ｘとすれば、
ｘＨT=0 （6）
が成立し、図４(c)の例では図５に示すように
ｘ0＋ｘ1＋ｘ2＝０
ｘ2＋ｘ3＝０
ｘ3＋ｘ4＋ｘ5＝０
が成立する。
【００１８】
・繰り返し復号アルゴリズム
Sum-Product法は、タナーグラフに基づいて繰り返し後述の事後確率APPあるいは尤度比LRあるいは対数尤度比LLRを求めてｘを推定し、 (6)式を満足する推定値を求める手法である。なお、以下では説明上、ｘの代わりにｃを使用し、符号コードｃ＝（ｃ0，ｃ1，．．．，ｃN-1）が送信されたものとする。この場合、変数ノードの表記もｃ0，ｃ1，．．．，ｃN-1を使用しているが、コード、ノードという用語をつけて区別する。
コードｃ＝（ｃ0，ｃ1，．．．，ｃN-1）が送信されて、尤度データｙ＝（ｙ0，ｙ1，．．．，ｙN-1）が受信された時の事後確率APP、尤度比LR、対数尤度比LLRを次式
【数３】
0004425282.tif 000004
で表現する。
タナーグラフにおいて、各変数ノードｃiはチェックノードからの入力メッセージと尤度データｙiを有し、出力メッセージを隣接するチェックコードへ渡す。図６(Ａ)に示すように検査行列Ｈの0番目の列が［１１１０００．．．０］Tである時のタナーグラフのサブグラフは図６（B）に示すように、変数ノードｃ0にチェックノードｆ0，ｆ1，ｆ2が接続し、尤度データｙ0が入力する構成になる。変数ノードｃ0からチェックノードｆ2へのメッセージｍ↑02は、図６（C）に示すようにチェックノードｆ0，ｆ1から変数ノードｃ0へのメッセージと尤度データｙ0を入力とする出力メッセージである。この出力メッセージｍ↑02は、コードｃ0が０であるか1であるかの事後確率Pr(ｃ0=b｜入力メッセージ)、ｂ∈｛0,1｝、あるいは確率比、あるいは対数確率比を示している。繰り返しの半サイクルで全ノードｃi／ｆjの組合わせに対するｍ↑ijが計算される。
図７(Ａ)に示すように検査行列Ｈの0番目の行が［１１１０１００．．．０］である時のタナーグラフのサブグラフは図７（B）に示すように、チェックノードｆ0に変数ノードｃ0，ｃ1，ｃ2，ｃ4が接続する構成になる。チェックノードｆ0から変数ノードｃ4へのメッセージｍ↓04は、図７（C）に示すように変数ノードｃ0，ｃ1，ｃ2からチェックノードｆ0へのメッセージを入力とする出力メッセージである。この出力メッセージｍ↓04は、入力メッセージに対して検査式ｆ0が満たされる確率、あるいは確率比、あるいは対数確率比を示している。入力メッセージに対して検査式ｆ0が満たされる確率は
Ｐr(検査式ｆ0が満たされる｜入力メッセージ)、ｂ∈｛0,1｝
と表現される。繰り返しの他の半サイクルで全ノードｆj／ｃiの組合わせに対するｍ↓jiを計算する。
【００１９】
・事後確率を使用したSum-Product algorithm (SPA) 
始めに、以下で使用する用語の定義をする。
図８（A）に示すようにチェックノードｆjに接続する全変数ノードの集合をＶjと表現し、チェックノードｆjに接続する全変数ノードから変数ノードｃiを除外した集合をＶj|iと表現する。
また、図８（B）に示すように変数ノードｃiに接続する全チェックノードの集合をＣiと表現し、変数ノードｃiに接続する全チェックノードからチェックノードｆjを除外した集合をCi|jと表現する。
また、ノードｃiを除く全変数ノードからのメッセージをMv（〜i）と表現し、ノードｆjを除く全チェックノードからのメッセージをMc（〜j）と表現し、尤度データｙiが受信された時のコードｃiが１である事後確率をＰi＝Ｐr(ｃi=1｜ｙi)と表現し、コードｃiを含む検査式が満たされる事象をＳiと表現する。
さらに、
ｑij(b)=Pr（ｃi＝b|Si,ｙi，Mc（〜j））
とする。ただし、ｂ∈｛0,1｝である。図８(Ｃ)に示すように事後確率APPアルゴリズムの場合、ｍ↑ij＝ｑij(b)、LRアルゴリズムの場合、ｍ↑ij＝ｑij(0)／ｑij(1)、LLRアルゴリズムの場合ｍ↑ij＝log［ｑij(0)／ｑij(1)］である。
また、
ｒji(b)＝ Pr(検査式ｆjが満たされている｜ｃi＝ｂ，Mv（〜i）) 
とする。ただし、ｂ∈｛0,1｝である。図８(Ｄ)に示すように、事後確率ＡＰＰアルゴリズムの場合、ｍ↓ji＝ｒji(b)、LRアルゴリズムの場合、ｍ↓ji＝ｒji(0)／ｒji(1)、LLRアルゴリズムの場合ｍ↓ji＝log［ｒji(0)／ｒji(1)］である。
以上の定義より、図９（A）に示すメッセージｑij(b)は次式
【数４】
0004425282.tif 000005
で与えられる。K ijはｑij(0)＋ｑij(1)＝１を満たす係数である。
M個のバイナリデジットａiのシーケンスにおいて、ａiが１である確率を
Ｐr（ａi＝１）＝ｐiと表わす。そのとき、該シーケンス
0004425282.tif 000006
が偶数の1を含む確率は
【数５】
0004425282.tif 000007
である。上式とｐi→ｑij(1)であることを考慮すると、次式
【数６】
0004425282.tif 000008
が得られる(図９（B）参照)。
これはコードｃi＝０のとき、検査式ｆjが満たされるために以下で示すビット
0004425282.tif 000009
が、偶数個の１を持たなければならないからである。なお、検査式ｆjが偶数個の１を有していれば、ｆj mod 2＝０である。
また、次式
【数７】
0004425282.tif 000010
が成立する。
【００２０】
以上から、事後確率を使用するSum-Product algorithm (SPA)は以下のようになる。
ステップ１：ｉ=0,1,…,n-1のそれぞれに対して、第ｉ尤度データｙiを受信した時のコードｃiが１となる確率をＰi＝Ｐr（ｃi=1|yi）とする。そのとき、ｈij＝１の全ｉ，ｊについてｑij(0)＝１−Ｐi，ｑij(1)＝Ｐiとする。
ステップ２：(11)式、(12)式により｛ｒji(b)｝を更新する。
ステップ３：(8)式、(9)式により、｛ｑji(b)｝を更新する。
ステップ４：ｉ=0,1,…,n-1に対してＱi(0)，Ｑi(1)を次式により計算する。
【数８】
0004425282.tif 000011
ただし、係数KiはＱi(0)＋Ｑi(1)＝１が成り立つように選ばれる。
ステップ５：Ｑi(1)＞Ｑi(0)であれば、
0004425282.tif 000012
とし、Ｑi(1)＜Ｑi(0)であれば、
0004425282.tif 000013
とする。
ステップ６：最後に、次式
【数９】
0004425282.tif 000014
が成立するか、あるいは最大繰り返し回数になったかチェックし、上式が成立し、あるいは最大繰り返し回数に到達すれば処理を終了し、さもなければステップ1以降の処理を繰返す。
【００２１】
・対数尤度比を用いたSum-Product algorithm (SPA) 
以上は事後確率のSum-Product algorithm (SPA)であるが、次に対数尤度比を用いたSum-Product algorithm (SPA)を説明する。なお、
【数１０】
0004425282.tif 000015
である。また、BEC(binary erasure channel)において、Ｌ(qij)は以下により初期化する。
【数１１】
0004425282.tif 000016
更に、Ｌ(qij)を次式により、
【数１２】
0004425282.tif 000017
符号と振幅で表現する。これにより、Ｌ(ｒji)は次式
【数１３】
0004425282.tif 000018
より得られる。但し、
【数１４】
0004425282.tif 000019
である。また、Ｌ(ｑij)は次式
【数１５】
0004425282.tif 000020
より与えられ、更に、Ｌ(Ｑi)は次式
【数１６】
0004425282.tif 000021
により求まる。
【００２２】
以上から、対数ドメインにおけるSum-Product algorithm (SPA)は以下のようになる。
ステップ１：ｉ=0,1,…,n-1のそれぞれに対して、ｈij＝１の全ｉ，ｊについて(16)式にしたがってＬ(ｑij)を初期化する。
ステップ２：(17)式により、Ｌ(ｒji)を更新する。
ステップ３：(19)式によりＬ(ｑij)を更新する。
ステップ４：(20)式によりＬ(Ｑi)を求める。
ステップ５：ｉ=0,1,…,n-1に対して、Ｌ(Ｑi)＜０であれば、
0004425282.tif 000022
とし、Ｌ(Ｑi)＞０であれば、
0004425282.tif 000023
とする。
ステップ６：最後に、次式
【数１７】
0004425282.tif 000024
が成立するか、あるいは最大繰り返し回数になったかチェックし、上式が成立し、あるいは最大繰り返し回数に到達すれば処理を終了し、さもなければステップ1以降の処理を繰返す。
以上第1実施例によれば、ダミービットを追加して符号化するため、符号化率が大きくなり、ダミービットを情報ビットに含めたときの符号としては特性が悪くなるが、復号側においてダミービットに対応するビット位置に確率１に対応する尤度データを追加して復号できるため符号特性(誤り検出訂正特性)を良くできる。このことは、例えば元の符号がレギュラーLDPC符号であっても、ダミービットに対応する信頼度が無限大の尤度データを挿入することで、ダミービット位置の検査行列要素を無視することと等価になり（式（18）から）特性が良いイレギュラーLDPC符号による符号化および復号と同等の効果を与えるためである。しかも、ダミービットを伝送しないため、無駄な伝送コストがかからない利点(伝送効率が低下しない利点)が有る。
また、最小符号化率の符号化が可能となるように符号化部を実装するため、複数の符号化率の符号を1つの符号器によって実現することができる。
【００２３】
（B）第2実施例
図１においてダミービット２００は情報ビット１００にランダムに追加した場合について説明したが、具体的には以下のように追加することができる。図１０（A）は情報ビット１００の後方にダミービット２００を一括追加する例、図１０（B）は情報ビット１００の前方にダミービット２００を一括追加する例、図１０（C）は情報ビット１００にほぼ均一にダミービット２００を追加する例である。ここで、「ほぼ均一」とは、偏りが全く、または殆ど無いことをいう。ほぼ均一にダミービットを追加する方法として、例えば、３ＧＰＰのW-CDMAで規定されているレートマッチパターンアルゴリズムで位置を特定して追加する手法を用いることができる。ダミービット位置により符号特性が変化する。
特に、符号をイレギュラーLDPC符号とする場合には、ダミービットに対応する検査行列H1における列のうち、同一ウェイトの列が偏らないように選択するのが良い。そのためには各ウェイト数を検査行列H1の列に一様にあるいはランダムに分布させる。
図１１は第1実施例におけるK1（＝K0+K）個の情報ビットのうち、K0個のダミービットの挿入位置を図１０（C）に示すようにほぼ均一とした場合の配置方法説明図である。
実数の[0,1]の範囲で、各K0個のダミービットに対応する「実インデックス」ｒ(i)を
ｒ(i)＝ｉ／K0 (22)
と定義する。このとき、実際の整数インデックスｓ(i)を次式
s(i)＝［Ｋ・ｒ(i)＋０．５］ (23)
とする。ただし、［ｚ］はｚ以下の最小整数である。ｉを０，１，．．K0−1と変化させることによりK0個のダミービット位置を(23)式により求めることができる。
図１２は、図２におけるダミービット追加部１１ａの構成図であり、バッファ部11a-1はＫ個の情報ビットを一時的に記憶し、ダミービット発生部11a-2はK0個のダミービットを発生し、ダミービット位置取得部11a-3は(23)式によりK0個のダミービット位置を計算して合成部11a-4に入力する。合成部11a-4は、図１１に示すように情報ビット100のダミービット位置にK0個のダミービット200を一様に挿入して出力する。
【００２４】
（C）第３実施例
ダミービット追加位置により符号特性が変化する。このため、第３実施例では符号をLDPC符号として最適なダミービット追加位置を決定し、そこにダミービットを追加する。
さて、固定符号を追加した時の検査行列H1は図３（C）に示すようにM×N1行列になる。ただし、M=N−K、N1＝N＋K0である。ダミービットを追加しない検査行列H′は検査行列H1からＱT部分を削除したＭ×Ｎ行列になる。ダミービットを挿入して符号化する第1実施例の符号化方法は、理想的な状況を想定すると、検査行列H1からダミービットに対応する列（ＱT部分）を削除し、該削除して得られたM×Ｎの検査行列H′を用いて受信したN個の尤度データｙを復号することと特性的には変わらない。
そこで、図１３に示すように、復号に用いるN1×M検査行列H1の既知のウェイト分布を（λj，ρk）、該検査行列よりK0個の列を除いたN×Ｍ検査行列H′の最適なウェイト分布（λj′，ρk′）としたとき、N1×M検査行列H1よりK0個の列を除いたN×Ｍ検査行列のウェイト分布が前記最適なウェイト分布（λj′，ρk′）となるようなK0個の列を決定し、該決定したK0個の列に対応する位置をダミービットのK0個のビット挿入位置とする。
N×Ｍ検査行列H′の最適なウェイト分布（λj′，ρk′）は、LDPC符号の復号方法である信頼度伝播法（Belief Propagation）に基づいて与えられている、尤度分布に対しての密度発展法（Density Evolution）を適用することにより求めることができる。なお、信頼度伝播法、密度発展法は周知であり、詳細は以下の参考文献を参照されたい。
参考文献：T.J. Richardson and M.A. Shokrollahi, and R.L. Urbank 「Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes」
図１４は第３実施例のダミービット追加位置決定処理フローであり、図１２のダミービット位置取得部11a-3が行なう。
【００２５】
最初に、N×Ｍの検査行列H′の最適なウェイト分布（λj′，ρk′）を密度発展法により求める(ステップ501)。ついで、ウェイト分布が既知の（λj，ρk）であるN1×M検査行列H1からK0列を除去し(ステップ502)、K0列を除去した残りのN×Ｍ行列のウェイト分布λj′′，ρk′′を計算する(ステップ503)。
しかる後、λj′′＝λj′，ρk′′＝ρk′であるかチェックし(ステップ504)、成立しなければステップ502に戻り、除去するK0列を代えて以降の処理を繰返す。一方、λj′′＝λj′，ρk′′＝ρk′であれば、そのときのK0列を除いた位置をダミービットのビット追加位置とする(ステップ505)。
なお、ステップ504において、許容誤差Δεを定めておき|λj′′−λj′|＜Δε，|ρk′′−ρk′|＜Δεが成立したとき、そのときのK0列を除いた位置をダミービットのビット追加位置とするようにもできる。
第３実施例によれば、与えられた符号化率の与えられたウェイト分布のLDPC符号で最適なダミービット位置を求めることができる。
【００２６】
（Ｄ）第４実施例
ダミービット追加位置により符号特性が変化する。第４実施例はダミービットを挿入する位置を選択するために、最小符号間距離が大きくなるようなダミービット追加位置を決定し、そこにダミービットを追加する。これは最小符号間距離が大きいと誤り検出訂正能力が向上し、符号特性がよくなるからである。
M×N1の検査行列H1を以下のように列ベクトル表現する。
【数１８】
0004425282.tif 000025
ただし、線形ブロック符号において、最小符号間距離は符号の最小ハミングウェイト数に等しい。そして、任意のd−1個の列ベクトルが線形独立であるが、d個の列ベクトルの組で線形従属なものがあると、その最小符号間距離はdとなる。
ダミービットを挿入した符号Cは、ダミービットがall 0（オール０）と異なれば線形符号でなくなるが最小符号間距離においてはall 0パターンを挿入した符号と等価である。all 0パターンを挿入した符号は線形符号と考えることができるため、その最小符号間距離は符号の最小ハミングウェイトに等価であり、したがって、ダミービットを挿入した符号においても最小符号間距離は最小ハミングウェイトに等価となる。
【００２７】
図１５は第４実施例のダミービット追加位置決定処理フローであり、図１２のダミービット位置取得部11a-3が行なう。
元になる母符号C1の最小距離（ハミングウェイト数）がd0であるとする。N1×M検査行列H1においてd0-1個の列ベクトルは線形独立であるから、任意のd0-1個と線形従属になる列ベクトルのインデックスの組を求める(ステップ601)。
ついで、K0<k0であるかチェックし(ステップ602)、K0<k0であれば、k0個の中からK0個を選び、選んだ列ベクトル位置をダミービットのビット位置とし(ステップ603)、処理を終了する。このとき、ダミービットを挿入された符号Cの最小距離は元の符号C1と同じになる。
ステップ602において、K0≧k0であればk0個を選び次に進む。このとき残りのN1-k0の列ベクトルは、少なくとも任意のd0個のベクトルが線形独立になっているので、最小距離d1はd0+1以上になる。先ほどのk0個のベクトルを除外した、N1-k0個のベクトルのなかで、任意のd1-1個のベクトルは線形独立であるが、d1個で従属となる(k1−k0）個のベクトルの組を求める(ステップ604)。
ついで、k1＜K0であるかチェックし(ステップ605)、k1≧K0であればステップ603に飛び、k1個の中からK0個を選び、選んだ列ベクトル位置をダミービットのビット位置とし(ステップ603)、処理を終了する。
一方、ステップ605において、k1＜K0であればk0をk1で置き換え（k0＝k1、ステップ606）、以後、ステップ604以降の処理を繰り返しK0個のダミービット位置の選択が完了するまで繰り返す。
第４実施例によれば、符号特性を向上することができる。
【００２８】
（E）第５実施例
CDMA移動通信システムのような複数の移動端末が同時に同じ無線リソースにアクセスすることができる無線移動通信システムを考える。この無線移動通信システムでは、基地局から各移動端末に共通チャネルを介してステイタス情報を通信する。移動端末は、該共通チャネルを介して送信されたステイタス情報を受信し、復調処理を実行し、受信符号ビットを尤度データにして複合器に入力する。
各移動端末には、予め個別のダミービットがＩＤとして与えられている。基地局は、共通チャネルを介して個々の移動端末に対して所定のステイタス情報を通知する。その際、図１６に示すように、各移動端末向けのステイタス情報の符号化に際して第1実施例の符号化方法を適用し、ダミービットとして宛先移動端末のＩＤを用いる。各移動端末は、共通チャネルの全てのフレームの受信データから尤度データを生成して、自端末のIDとなるダミービットを追加して復号処理を行う。しかし、宛先移動端末以外の移動端末は復号に失敗し、宛先移動端末のみが復号に成功し、ステイタス情報の秘密性を維持できる。図16では、移動端末A宛の情報は移動端末Aのみが受信に成功し、移動端末B宛の情報は移動端末Bのみが受信に成功する。
第５実施例によれば、各移動端末へのみ所定の情報を送信することができる。
【００２９】
（F）第６実施例
第1実施例の送信機１０における符号器１１ｂ(図２参照)は
ｘ1＝(ｕ，ａ）Ｇ1
によりＮ1（＝K+K0+M）個の情報ビットｘ1を出力する。生成行列Ｇ1は図３(B）に示す行列であるから上式は、
【数１９】
0004425282.tif 000026
となる。ここで、
ｐ＝ｕP＋ｂ (26)
はパリティビット ベクトルであり、b=aQはダミービットに対応する部分で一定値である。そこで、b=aQを予め計算してテーブルに保持しておき、(26)式の演算に際して利用する。
図１７は第６実施例の符号器１１bの構成図であり、図２の符号器と同一部分には同一符号を付している。ダミービットパリティテーブル11b-3には、(26)式のb（=aQ）が予め計算されて記憶されている。パリティ生成器11b-1は(26)式における右辺第１項ｕPを演算し、加算器11b-4は(26)式の加算演算を行ってパリティビットpを出力する。合成部11b-2は情報ビット(u，a)にパリティビットpを挿入して情報ビットｘ1を出力する。
【００３０】
（G）第７実施例
第１実施例の受信機では、復調部２１は受信データから生成した尤度データをそのまま復号器２２に入力する。復号処理としては(17)、(19)式の２つの尤度演算をダミービットも含む全ての符号ビットに対して、繰り返し行うSum-Productアルゴリズムを適用する。(17)〜(19)式を再掲すると以下の通りである
【数２０】
0004425282.tif 000027
上式をそのまま実行すると相当の演算量になる。そこで、第７実施例では図１８に示すようにダミービットに関連する演算結果を予め求めてメモリ(ダミービットテーブル)２３に記憶しておき、復号部２２は復号に際して該保持されている演算結果を利用する。
(17)式のL(rji)において、チェックノードｆjに接続する変数ノードの集合Ｖj|iの全変数ノードがダミービット位置に対応している場合には、L(rji)はダミービットを用いて演算できるから予め計算してメモリ２３に記憶する。又、(17)式において、変数ノードｃi′がダミービット位置であれば、(16)式よりＬ(qij)＝L（ｃi）=±∞となり、φ(βi′j)＝０となるから該φ(βi′j)＝０を同様にメモリ２３に保存する。さらに、(19)式のＬ(qij)において変数ノードｃiがダミービット位置であれば、(16)式よりＬ(qij)＝L（ｃi）=±∞となるから、該Ｌ(qij)＝L（ｃi）をメモリ２３に保存しておく。
【００３１】
図１９、図２０は、第７実施例の対数尤度比を用いたSum-Product algorithm (SPA)の処理フローである。
予め必要な値（L(rji)，Ｌ(qij)，φ(βi′j)＝０等）を計算してメモリ２３に保存し、かつ、繰り返し回数I=1とする(ステップ701)。
ついで復号部２２は、ｉ=0,1,…,n-1（ただし、n=N1）のそれぞれに対して、ｈij＝１の全ｉ，ｊについて(16)式にしたがってＬ(ｑij)を初期化する（ステップ702）。
初期化が終了すれば、復号部２２は、(17)式に基づいてＬ(ｒji)を更新する(ステップ703)。すなわち、まず、ｈij＝１のｉ，ｊを選び(ステップ703a)、変数ノードの集合Ｖj|iの全変数ノードがダミービット位置に対応しているか判断し(ステップ703b)、「YES」であれば、メモリ２３に保存してある計算値Ｌ(ｒji)を使用する(ステップ703c)。しかし、「NO」であれば、Ｌ(ｒji)を計算する(ステップ703d)。この場合、変数ノードｃi′がダミービット位置であれば
φ(βi′j)＝０を使用する。ついで、復号部２２は全てのｈij＝１のｉ，ｊの組合わせに対して上記処理を終了したかチェックし(ステップ703e)、完了してなければ、ｉ，ｊの組合わせを変え(ステップ703f)、ステップ703ｂ以降の処理を繰返す。
【００３２】
以上により、全Ｌ(ｒji)の計算が完了すれば、 (19)式によりＬ(ｑij)を更新する(ステップ704)。すなわち、まず、ｈij＝１のｉ，ｊを選び(ステップ704a)、変数ノードｃiがダミービット位置に対応しているか判断し(ステップ704b)、「YES」であれば、メモリ２３に保存してある計算値Ｌ(ｑij)を使用する(ステップ704c)。しかし、「NO」であれば、Ｌ(ｑij)を計算する(ステップ704d)。
ついで、復号部２２は全てのｈij＝１のｉ，ｊの組合わせに対して上記処理を終了したかチェックし(ステップ704e)、完了してなければ、ｉ，ｊの組合わせを変え(ステップ704f)、ステップ704ｂ以降の処理を繰返す。
以上により、全Ｌ(ｑij)の計算が完了すれば、(20)式によりＬ(Ｑi)を求める(ステップ705)。そして、ｉ=0,1,…,n-1に対して、Ｌ(Ｑi)＜０であれば、
0004425282.tif 000028
とし、Ｌ(Ｑi)＞０であれば、
0004425282.tif 000029
と判定する(ステップ706)。最後に、次式
【数２１】
0004425282.tif 000030
が成立するかチェックし(ステップ707)、成立すれば復号処理を終了する。しかし、上式が成立しなければ、最大繰り返し回数になったかチェックし（I=ＩMAX）(ステップ708)、最大繰り返し回数に到達すれば復号処理を終了し、さもなければＩを歩進して(ステップ709)、ステップ703に戻り以降の処理を繰返す。
第６、第７実施例によれば、演算量を少なくでき、高速の処理が可能となる。
【００３３】
（H）第8実施例
以上の実施例では符号としてLDPC符号を用いる場合であるが、ターボ符号を用いることができる。尚、符号としてターボ符号を用いる場合も、無線通信システムは図２と同一の構成になる。
図２１はターボ符号を用いた符号化／復号方法説明図であり、ダミービット200のビット数を情報ビット100のビット数Kと等しくし、符号化率１／５で伝送する場合の例を示している。
図２および図２１を参照すると符号化に際して、送信機10の符号化部11を構成するダミービット追加部11aは、情報ビット100にダミービット200を追加する。しかる後、ターボ符号器11bにより該ダミービットが追加された情報ビットを符号化して符号率１／３のターボ符号400を発生する。すなわち、ダミービットが追加された情報ビットを用いて作成したパリティビット300を該情報ビットに付加してなるターボ符号400を発生する。ついで、ダミービット削除部11cはターボ符号400から前記ダミービット200を削除して組識符号500を生成し、伝播路30を介して該組織符号を受信機20に送信する。受信機の復調部21は該組織符号500を受信して復調し、復号部22は復調した組織符号に送信側で削除したダミービット200を尤度最大にして追加し、しかる後、ターボ復号して情報ビット100を出力する。なお、尤度最大(信頼度∞)にしてダミービットを追加する方法は、受信信号の尤度の絶対値(信頼度)を求めてその平均値を演算し、該平均値に十分大きな値の係数、例えば10を乗算した正負の値をそれぞれダミービットの“０”、”１”とすることにより行う。
【００３４】
図２２は図２の移動通信システムにおける符号器11bであるターボ符号器の構成図である。ターボ符号器は、図示しないダミービット追加部11a(図2参照)から入力する情報長K1(=2K)のダミービット付き情報ビットｕを符号化して符号化データｘa，ｘb，ｘcを直列にして出力する。
符号化データｘaは情報ビットｕそのものであり(組織ビット)、符号化データｘbは情報ビットｕを要素符号器51aで畳み込み符号化したデータ(第1のパリティビット)、符号化データｘcは情報ビットｕをインタリーブ部51bでインタリーブ（π）して要素符号器51cで畳み込み符号化したデータ(第2のパリティビット)であり、P/S変換部51ｄはターボ符号ｘa，ｘb，ｘcを直列データに変換して、図示しないダミービット削除部11c(図２参照)に入力する。
なお、図２２の要素符号器51a，51cにおいて、EORは排他的論理和回路、Dはシフトレジスタを構成するフリップフロップである。また、図２２にはトレリスト終結(trellis termination)を行うためにテールビットスイッチ51d，51eが設けられている(非特許文献3GPPTS 25.212 V5.9.0(2004-06)参照)。ターボ符号において、トレリスト終結時の要素符号器51a,51cのシフトレジスタの内容が常にオールゼロとなっていれば、ターボ復号際して後方確率演算を正しく行え、結果的に高精度の復号処理を行える。このため、情報ビットｕの入力終了後に、テールビットスイッチ51dを点線位置に切り替えて要素符号器51aの最初のEOR出力が必ず”0”となるようにする。これにより、3クロック後にシフトレジスタの内容がオール零になる。そして、3クロック分の要素符号器51aの入力と出力を、それぞれテールビットとして組織ビットxaと第1パリティビットxbに付加して出力する。ついで、テールビットスイッチ51eを点線位置に切り替えて要素符号器51cの最初のEOR出力が必ず”0”となるようにする。これにより、3クロック後にシフトレジスタの内容がオール零になる。そして、3クロック分の要素符号器51cの入力をテールビットxdとして出力すると共に、要素符号器51cの出力をテールビットとして第2パリティビットxcに付加して出力する。
【００３５】
図２３は図２の移動通信システムにおける復号部22の構成図であり、復号器としてターボ符号器を用いる場合の構成図である。
復号前処理部22aは図2のダミービット尤度追加部22aに相当し、分離部61aは直列に入力するデータを符号化データya′，yb，yc，ydに分離し、ダミービット追加部61bは送信側で削除したダミービット200を尤度最大にして組織ビットya′に追加し、得られた符号化データya，yb，yc，ydを符号器22bに入力する。ターボ復号器22bにおいて第１の要素復号器62aは、受信信号ｙa，ｙb，ｙc、ｙｄのうち、ｙaとｙbを使って復号を行う。要素復号器61aは軟出力要素復号器であり、復号結果の尤度を出力する。次に、第２の要素復号器62bは第１の要素復号器61aから出力する尤度とyc，ydとを用いて同様の復号を行い、復号結果である尤度を出力する。なお、ｙcは原データｕをインタリーブしたものを符号化したｘcに対応する受信信号なので、第１の要素復号器62aから出力される尤度をインタリーブ部62cでインタリーブ（π）して第２の要素復号器62bに入力する。デインタリーブ部62dは第２の要素復号器62bから出力する尤度をデインタリーブ（π-1）して、第１の要素復号器62aにフィードバックする。以後、上記の復号操作を所定回数繰り返し行い、第２の要素復号器62bのデインタリーブ出力を硬判定し、判定結果を復号結果として出力する。
第８実施例によれば、ダミービットを受信側に送信せず、受信側で尤度を最大にしたダミービットを受信データに追加して復号することにより復号誤りを減少することができる。また、ダミービットを削除して変調し伝送することで、送受信機の電力消費および伝送路容量の使用を削減することができる。
【００３６】
（a）第１変形例
図２４は第８実施例の第１変形例の符号化／復号方法説明図であり、ダミービット200のビット数を情報ビット100のビット数Kと等しくした場合の例を示している。図２５は第１変形例の無線通信システムの構成図であり、図２の第１実施例と同一部分には同一符号を付している。なお、以後の変形例において、11aは符号化前処理部、11cは符号化後処理部、22aは復号前処理部として説明している。
符号化に際して、送信機10の符号化部11を構成する符号化前処理部11aにおけるダミービット追加部71は情報ビット100にダミービット200を追加する。しかる後、ターボ符号器11bにより、該ダミービットが追加された情報ビットを符号化して符号率１／３のターボ符号400を発生する。ついで、符号化後処理部11cのダミービット一部削除部72はターボ符号400から前記ダミービットの一部を削除して組識符号500を生成し、変調部12を含む送信部は伝播路30を介して該組識符号500を受信機20に送信する。
受信機20の復調部21は該組織符号500を受信して復調し、復号部22の復号前処理部22aの受信ダミービット削除部73は復調した組織符号からダミービット200′を削除し、ダミービット追加部74は該ダミービット200′を削除した組織符号に送信側で追加したダミービット200を尤度最大にして追加し、しかる後、ターボ復号器22bでターボ復号して情報ビット100を出力する。
第1変形例によれば、上位により決定される物理チャネルのデータ数(送信ビットレート)に合わせて、余分の一部ダミービットを削除して送信することができる。
【００３７】
（b）第２変形例
図２６は第８実施例の第２変形例の符号化／復号方法説明図であり、ダミービット200のビット数を情報ビット100のビット数Kと等しくした場合の例を示している。また、図２７は第2変形例の効果説明図、図２８は第２変形例の無線通信システムの構成図であり、図２と同一部分には同一符号を付している。
符号化に際して、送信機10の符号化部11を構成する符号化前処理部11aにおけるダミービット追加部71は情報ビット100にダミービット200を追加する。しかる後、ターボ符号器11bにより、該ダミービットが追加された情報ビットを符号化して符号率１／３のターボ符号400を発生する。ついで、符号化後処理部11cのダミービット削除部75はターボ符号400から前記ダミービットを削除して組識符号500を生成し、レペティション処理部76は該組織符号500にレペティション処理を施してレペティションビット600を追加する。レペティション処理は、組織符号500のうちから指定の数を選び、そのコピーを作成して追加する処理である。変調部12を含む送信部は、伝播路30を介してレペティションビットが追加された組識符号700を受信機20に送信する。
受信機20の復調部21は該組織符号700を受信して復調し、復号部22の復号前処理部22aのレペティション復号部77は、レペティションビットを用いてダイバーシチ合成（レペティション復号）を行い、ダミービット追加部78は送信側で削除したダミービットを尤度最大にして追加し、しかる後、ターボ復号器22bでターボ復号して情報ビット100を出力する。
情報ビットにダミービットを追加してターボ符号化することにより符号化率R=1/3のターボ符号が得られ、該ターボ符号からダミービットを削除して送信することにより符号化率Rを1/3以下にでき、ダミービットのビット数が大きくなるほど、符号化率を小さくできる。所定のビットエラーレートBERを得るに必要なEb/Noと符号化率の関係は図27の曲線Aに示すようになる。すなわち、ダミービットを追加することにより符号化率が1/3から1/5まで小さくなるにつれて所定ビットエラーレートBERを得るに必要なEb/Noを小さくできる。換言すれば、Eb/Noを一定であれば、符号化率が1/3から1/5まで小さくなるにつれてBERを小さくすることができる。しかし、符号化率が1/5以下になると次第に特性が悪化し、符号化率が小さくなるにつれてBERが大きくなる。そこで、第2変形例では要求される符号化率が1/5より大きければ、ダミービットのみを追加する処理により特性を向上する。しかし、要求される符号化率が1/5以下の場合には、レペティション処理により繰り返しビットを付加して符号化率を要求された符号化率にする。なぜならば、レペティション処理により繰り返しビットを付加しても、図２７の曲線Bで示すように、特性が劣化しないからである。
以上より、第2変形例によれば、レペティションビットを付加することにより復号誤りの劣化を防止することができる。
【００３８】
(c)第3変形例
第3変形例は第2変形例のレペティションをパンクチュアリングに変えた例であり、図２９は第３変形例の符号化／復号方法説明図で、ダミービット200のビット数を情報ビット100のビット数Kと等しくした場合を示している。また、図３０は第３変形例の無線通信システムの構成図であり、図２と同一部分には同一符号を付している。パンクチャリングとは、符号ビットのうちから指定の数を選び、そのビットを削除する処理であり、受信側では削除位置のビットデータとして固定の値(0値尤度)を追加する。
符号化に際して、送信機10の符号化部11を構成する符号化前処理部11aにおけるダミービット追加部71は情報ビット100にダミービット200を追加する。しかる後、ターボ符号器11bにより、該ダミービットが追加された情報ビットを符号化して符号率１／３のターボ符号400を発生する。ついで、符号化後処理部11cを構成するダミービット削除部81はターボ符号400から前記ダミービットを削除して組識符号500を生成し、パンクチュアード符号部82は組織符号500にパンクチュアリング処理を施してパリティビットの所定位置、所定ビット数分のパリティビットを削除する(パンクチュアリング)。ついで、変調部12を含む送信部は伝播路30を介してパンクチュアリングされた組識符号800を受信機20に送信する。
受信機20の復調部21は該組織符号800を受信して復調し、復号部22の復号前処理部22aのパンクチュアード復号部83は、削除したパリティビット位置に尤度が０のパリティビット(0値尤度)を挿入して元の長さのパリティビット300を復元する(パンクチュアード復号)。ついで、ダミービット追加部84は送信側で削除したダミービットを尤度最大にして追加し、しかる後、ターボ復号器22bでターボ復号して情報ビット100を出力する。
第3変形例によれば、ダミービットを送信しないことにより符号化率を小さくして復号誤りを減少でき、しかも、所望の符号化率となるようにパンクチュアリングして送信することができる。
【００３９】
(d)第4変形例
第2変形例では、ターボ符号化後にレペティション処理を施して復号誤りを減少すると共に要求された符号化率を満足するようにしたが、ターボ復号前にレペティション処理を施しても同様の効果を期待することができる。そこで、第4変形例はターボ復号前にレペティション処理を施してデータ送信する。
図３１は第4変形例の符号化／復号方法説明図で、ダミービットとレペティションビットの合計ビット数と情報ビット100のビット数Kとを等しくした場合を示している。また、図３２は第4変形例の無線通信システムの構成図であり、図２と同一部分には同一符号を付している。
符号化に際して、送信機10の符号化部11を構成する符号化前処理部11aのレペティション処理部91は情報ビット100にレペティションビット150を追加し、ダミービット追加部92は該レペティションビットが追加された情報ビットにダミービット200を追加する。しかる後、ターボ符号器11bにより、レペティションビットとダミービットが追加された情報ビットを符号化して符号率１／３のターボ符号400を発生する。ついで、符号化後処理部11cのダミービット削除部93はターボ符号400から前記ダミービットを削除して組識符号500を生成し、変調部12含む送信部は伝播路30を介して該組識符号500を受信機20に送信する。
受信機20の復調部21は該組織符号500を受信して復調し、復号部22を構成する復号前処理部22aのダミービット追加部94は復調した組織符号に送信側で削除したダミービット200を尤度最大にして追加し、ターボ符号器22bはターボ復号して情報ビット100を出力する。なお、ターボ復号により情報ビット100とレペティションビット150とダミービット200が得られるから、ターボ復号後にダミービットを削除し、ついで、レペティション復号処理を施して情報ビット100を出力する。
【００４０】
(e)第5変形例
第5変形例はターボ復号前にレペティション処理を施してデータ送信する別の例であり、図３３は第5変形例の符号化／復号方法説明図で、ダミービットとレペティションビットの合計ビット数と情報ビット100のビット数Kとを等しくした場合を示している。また、図３４は第５変形例の無線通信システムの構成図であり、図２と同一部分には同一符号を付している。
符号化に際して、送信機10の符号化部11を構成する符号化前処理部11aのレペティション処理部91は情報ビット100にレペティションビット150を追加し、ダミービット追加部92は該レペティションビットが追加された情報ビットにダミービット200を追加する。しかる後、ターボ符号器11bにより、レペティションビットとダミービットが追加された情報ビットを符号化して符号率１／３のターボ符号400を発生する。ついで、符号化後処理部11cであるダミービット削除部93は、ターボ符号400から前記ダミービット200を削除し、レペティションビット削除部95はレペティションビット150を削除して組識符号500を生成し、変調部12を含む送信部は伝播路30を介して該組識符号500を受信機20に送信する。
受信機20の復調部21は該組織符号500を受信して復調し、復号部22の復号前処理部22aの0値尤度レペティションビット挿入部96は送信側で削除したレペティションビット150の位置に尤度0のレペティションビットを挿入し、ダミービット追加部94は復調した組織符号に送信側で削除したダミービット200を尤度最大にして追加する。しかる後、ターボ復号器22bはターボ復号して情報ビット100を出力する。なお、ターボ復号により情報ビット100とレペティションビット150とダミービット200が得られるから、ターボ復号後にダミービットを削除し、ついで、レペティション復号処理を施して情報ビット100を出力する。
【図１】
0004425282.tif 000031
【図２】
0004425282.tif 000032
【図３】
0004425282.tif 000033
【図４】
0004425282.tif 000034
【図５】
0004425282.tif 000035
【図６】
0004425282.tif 000036
【図７】
0004425282.tif 000037
【図８】
0004425282.tif 000038
【図９】
0004425282.tif 000039
【図１０】
0004425282.tif 000040
【図１１】
0004425282.tif 000041
【図１２】
0004425282.tif 000042
【図１３】
0004425282.tif 000043
【図１４】
0004425282.tif 000044
【図１５】
0004425282.tif 000045
【図１６】
0004425282.tif 000046
【図１７】
0004425282.tif 000047
【図１８】
0004425282.tif 000048
【図１９】
0004425282.tif 000049
【図２０】
0004425282.tif 000050
【図２１】
0004425282.tif 000051
【図２２】
0004425282.tif 000052
【図２３】
0004425282.tif 000053
【図２４】
0004425282.tif 000054
【図２５】
0004425282.tif 000055
【図２６】
0004425282.tif 000056
【図２７】
0004425282.tif 000057
【図２８】
0004425282.tif 000058
【図２９】
0004425282.tif 000059
【図３０】
0004425282.tif 000060
【図３１】
0004425282.tif 000061
【図３２】
0004425282.tif 000062
【図３３】
0004425282.tif 000063
【図３４】
0004425282.tif 000064
【図３５】
0004425282.tif 000065
【図３６】
0004425282.tif 000066
【図３７】
0004425282.tif 000067
【図３８】
0004425282.tif 000068
【図３９】
0004425282.tif 000069
【図４０】
0004425282.tif 000070
【図４１】
0004425282.tif 000071
【図４２】
0004425282.tif 000072
【図４３】
0004425282.tif 000073
【図４４】
0004425282.tif 000074
【図４５】
0004425282.tif 000075