【手続補正書】
【提出日】平成18年3月23日(2006.3.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
LDPC(Low Density Parity Check)符号の復号装置であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組合せで表される場合において、
前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算手段と、
前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算手段と
を備えることを特徴とする復号装置。
【請求項２】
請求項１に記載の復号装置であって、
前記第１の演算手段は、チェックノードの演算を行うP個のチェックノード計算器を有し、
前記第２の演算手段は、バリアブルノードの演算を行うP個のバリアブルノード計算器を有する
ことを特徴とする復号装置。
【請求項３】
請求項１に記載の復号装置であって、
前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるP個の枝に対応するメッセージデータを同時に読み書きするメッセージ記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項４】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、チェックノードの演算時に読み出される枝に対応するメッセージデータを、検査行列の１を行方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項５】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、バリアブルノード演算時に読み出される枝に対応するメッセージデータを、検査行列の１を列方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項６】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、前記検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応するメッセージを、同一のアドレスに格納する
ことを特徴とする復号装置。
【請求項７】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、行数／P個のFIFOと、列数／P個のFIFOとで構成され、
前記行数／P個のFIFOと列数／P個のFIFOは、それぞれ、前記検査行列の行と列の重みに対応するワード数を有する
ことを特徴とする復号装置。
【請求項８】
請求項３に記載の復号装置であって、
前記メッセージ記憶手段は、RAM(Random Access Memory)で構成され、
前記RAMは、前記メッセージデータを、読み出される順番に詰めて格納し、格納位置順に読み出す
ことを特徴とする復号装置。
【請求項９】
請求項１に記載の復号装置であって、
LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項１０】
請求項９に記載の復号装置であって、
前記受信情報記憶手段は、前記受信情報を、前記バリアブルノードの演算に必要となる順番に読み出すことができるように格納する
ことを特徴とする復号装置。
【請求項１１】
請求項１に記載の復号装置であって、
前記P個のチェックノードの演算、または前記P個のバリアブルノードの演算の結果得られるメッセージを並べ替える並べ替え手段をさらに備える
ことを特徴とする復号装置。
【請求項１２】
請求項１に記載の復号装置であって、
前記第１の演算手段と前記第２の演算手段は、P個の枝に対応するメッセージを求める
ことを特徴とする復号装置。
【請求項１３】
請求項１に記載の復号装置であって、
前記第１の演算手段は、前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部とを行い、
前記第２の演算手段は、前記P個のバリアブルノードの演算の他の一部を行う
ことを特徴とする復号装置。
【請求項１４】
請求項１３に記載の復号装置であって、
前記第１の演算手段は、前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うP個の計算器を有し、
前記第２の演算手段は、前記P個のバリアブルノードの演算の他の一部を行うP個の計算器を有する
ことを特徴とする復号装置。
【請求項１５】
請求項１３に記載の復号装置であって、
前記第１の演算手段が前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項１６】
請求項１５に記載の復号装置であって、
前記第１の復号途中記憶手段は、前記P個のバリアブルノードの演算の他の一部を行う時に読み出される枝に対応する前記第１の復号途中結果を、検査行列の１を行方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項１７】
請求項１５に記載の復号装置であって、
前記第１の復号途中結果記憶手段は、前記検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応する前記第１の復号途中結果を、同一のアドレスに格納する
ことを特徴とする復号装置。
【請求項１８】
請求項１３に記載の復号装置であって、
前記第２の演算手段が前記P個のバリアブルノードの演算の他の一部を行うことにより得られるP個の枝に対応する前記第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項１９】
請求項１３に記載の復号装置であって、
LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項２０】
請求項１３に記載の復号装置であって、
前記第１の演算手段が前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うことにより得られる第１の復号途中結果、または前記第２の演算手段が前記P個のバリアブルノードの演算の他の一部を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段をさらに備える
ことを特徴とする復号装置。
【請求項２１】
請求項２０に記載の復号装置であって、
前記並べ替え手段は、バレルシフタで構成される
ことを特徴とする復号装置。
【請求項２２】
請求項１に記載の復号装置であって、
前記第１の演算手段は、前記P個のチェックノードの演算の一部を行い、
前記第２の演算手段は、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算とを行う
ことを特徴とする復号装置。
【請求項２３】
請求項２２に記載の復号装置であって、
前記第１の演算手段は、前記P個のチェックノードの演算の一部を行うP個の計算器を有し、
前記第２の演算手段は、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うP個の計算器を有する
ことを特徴とする復号装置。
【請求項２４】
請求項２２に記載の復号装置であって、
前記第１の演算手段が前記P個のチェックノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項２５】
請求項２２に記載の復号装置であって、
前記第２の演算手段が前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うことにより得られるP個の枝に対応する第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項２６】
請求項２５に記載の復号装置であって、
前記第２の復号途中結果記憶手段は、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行う時に読み出される枝に対応する前記第２の復号途中結果を、検査行列の１を列方向に詰めるように格納する
ことを特徴とする復号装置。
【請求項２７】
請求項２５に記載の復号装置であって、
前記第２の復号途中結果記憶手段は、前記検査行列を表す構成行列のうちの、重みが２以上の構成行列について、その構成行列を、重みが１の単位行列、準単位行列、またはシフト行列の和の形で表現したときの、その重みが１の単位行列、準単位行列、またはシフト行列に属するP個の枝に対応する前記第２の復号途中結果を、同一のアドレスに格納する
ことを特徴とする復号装置。
【請求項２８】
請求項２２に記載の復号装置であって、
LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段をさらに備える
ことを特徴とする復号装置。
【請求項２９】
請求項２２に記載の復号装置であって、
前記第１の演算手段が前記P個のチェックノードの演算の一部を行うことにより得られる第１の復号途中結果、または前記第２の演算が前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段をさらに備える
ことを特徴とする復号装置。
【請求項３０】
LDPC(Low Density Parity Check)符号の復号装置の復号方法であって、
P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組合せで表される場合において、
前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算ステップと、
前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算ステップと
を含むことを特徴とする復号方法。
【請求項３１】
LDPC(Low Density Parity Check)符号の復号をコンピュータに行わせるプログラムであって、
前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算ステップと、
前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算ステップと
を含むことを特徴とするプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０１２９
【補正方法】削除
【補正の内容】
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０１３５
【補正方法】削除
【補正の内容】
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１３６
【補正方法】削除
【補正の内容】
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１３７
【補正方法】削除
【補正の内容】
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１４１
【補正方法】削除
【補正の内容】
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１４９
【補正方法】削除
【補正の内容】
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１５０
【補正方法】削除
【補正の内容】
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１５１
【補正方法】削除
【補正の内容】
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１５４
【補正方法】削除
【補正の内容】
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１５６
【補正方法】削除
【補正の内容】
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１６８
【補正方法】変更
【補正の内容】
【０１６８】
請求項１４に記載の復号装置は、請求項１３に記載の復号装置であって、前記第１の演算手段は、前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うP個の計算器（例えば、計算器４１２1）を有し、前記第２の演算手段は、前記P個のバリアブルノードの演算の他の一部を行うP個の計算器（例えば、計算器４１５1）を有することを特徴とする。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１６９
【補正方法】変更
【補正の内容】
【０１６９】
請求項１５に記載の復号装置は、請求項１３に記載の復号装置であって、前記第１の演算手段が前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段（例えば、図１８の復号途中結果格納用メモリ４１３）をさらに備えることを特徴とする。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１７０
【補正方法】削除
【補正の内容】
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１７１
【補正方法】変更
【補正の内容】
【０１７１】
請求項１８に記載の復号装置は、請求項１３に記載の復号装置であって、前記第２の演算手段が前記P個のバリアブルノードの演算の他の一部を行うことにより得られるP個の枝に対応する前記第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段（例えば、図１８の復号途中結果格納用メモリ４１０）をさらに備えることを特徴とする。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１７２
【補正方法】変更
【補正の内容】
【０１７２】
請求項１９に記載の復号装置は、請求項１３に記載の復号装置であって、LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段（例えば、図１８の受信用メモリ４１６）をさらに備えることを特徴とする。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０１７３
【補正方法】変更
【補正の内容】
【０１７３】
請求項２０に記載の復号装置は、請求項１３に記載の復号装置であって、前記第１の演算手段が前記P個のチェックノードの演算と前記P個のバリアブルノードの演算の一部を行うことにより得られる第１の復号途中結果、または前記第２の演算手段が前記P個のバリアブルノードの演算の他の一部を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段（例えば、図１８のサイクリックシフト回路４１１または４１４）をさらに備えることを特徴とする。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０１７４
【補正方法】変更
【補正の内容】
【０１７４】
請求項２３に記載の復号装置は、請求項２２に記載の復号装置であって、前記第１の演算手段は、前記P個のチェックノードの演算の一部を行うP個の計算器（例えば、図２６の計算器６１２1）を有し、前記第２の演算手段は、前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うP個の計算器（例えば、図２６の計算器６１５1）を有することを特徴とする。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】０１７５
【補正方法】変更
【補正の内容】
【０１７５】
請求項２４に記載の復号装置は、請求項２２に記載の復号装置であって、前記第１の演算手段が前記P個のチェックノードの演算の一部を行うことにより得られるP個の枝に対応する第１の復号途中結果を同時に読み書きする第１の復号途中結果記憶手段（例えば、図２６の復号途中結果格納用メモリ６１３）をさらに備えることを特徴とする。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】０１７６
【補正方法】変更
【補正の内容】
【０１７６】
請求項２５に記載の復号装置は、請求項２２に記載の復号装置であって、前記第２の演算手段が前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うことにより得られるP個の枝に対応する第２の復号途中結果を同時に読み書きする第２の復号途中結果記憶手段（例えば、図２６の復号途中結果格納用メモリ６１０）をさらに備えることを特徴とする。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】０１７７
【補正方法】削除
【補正の内容】
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】０１７８
【補正方法】変更
【補正の内容】
【０１７８】
請求項２８に記載の復号装置は、請求項２２に記載の復号装置であって、LDPC符号の受信情報を格納するとともに、P個の前記受信情報を同時に読み出す受信情報記憶手段（例えば、図２６の受信用メモリ６１６）をさらに備えることを特徴とする。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】０１７９
【補正方法】変更
【補正の内容】
【０１７９】
請求項２９に記載の復号装置は、請求項２２に記載の復号装置であって、前記第１の演算手段が前記P個のチェックノードの演算の一部を行うことにより得られる第１の復号途中結果、または前記第２の演算が前記P個のチェックノードの演算の他の一部と、前記P個のバリアブルノードの演算を行うことにより得られる第２の復号途中結果を並べ替える並べ替え手段（例えば、図２６のサイクリックシフト回路６１１または６１４）をさらに備えることを特徴とする。
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】０１８０
【補正方法】変更
【補正の内容】
【０１８０】
請求項３０に記載の復号方法は、LDPC(Low Density Parity Check)符号の復号装置の復号方法であって、P×Pの単位行列、その単位行列のコンポーネントである１のうちの１個以上が０になった行列である準単位行列、前記単位行列もしくは準単位行列をサイクリックシフトした行列であるシフト行列、前記単位行列、準単位行列、もしくはシフト行列のうちの複数の和である和行列、またはP×Pの０行列を構成行列として、前記LDPC符号の検査行列が、複数の前記構成行列の組合せで表される場合において、前記LDPC符号の復号のためのP個のチェックノードの演算を同時に行う第１の演算ステップ（例えば、図１７のステップＳ３６）と、前記LDPC符号の復号のためのP個のバリアブルノードの演算を同時に行う第２の演算ステップ（例えば、図１７のステップＳ３１）とを含むことを特徴とする。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】０１８１
【補正方法】変更
【補正の内容】
【０１８１】
請求項３１に記載のプログラムの各ステップの具体例も、請求項３０に記載の復号方法の各ステップの発明の実施の形態における具体例と同様である。
【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】０２６７
【補正方法】変更
【補正の内容】
【０２６７】
なお、ここでは、式（７）と式（８）にしたがう第１の演算結果を、復号途中結果ujと記載するが、この復号途中結果ujは、式（７）のチェックノード演算結果ｕjに等しい。
【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】０２７９
【補正方法】変更
【補正の内容】
【０２７９】
計算器４１２1乃至４１２5は、それぞれ復号途中結果D411と復号途中結果D413を用いて、式（７）と式（８）にしたがって第１の演算を行い、復号途中結果D412（uj）を求める。計算部４１２は、計算器４１２1乃至４１２5による演算の結果得られる検査行列の５つの１に対応する５つの復号途中結果D412を復号途中結果格納用メモリ４１３に供給する。
【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】０３６０
【補正方法】変更
【補正の内容】
【０３６０】
ステップＳ５４の処理後は、ステップＳ５５に進み、計算部４１２は、第１の演算を行い、その演算結果である復号途中結果D412を復号途中結果格納用メモリ４１３に供給する。