(57)【要約】　　　（修正有）【課題】パリティ検査行列に要求される性質を満すと同時にサイクルが除去されたパリティ検査行列を生成してＬＤＰＣ復号化性能を向上させるＬＤＰＣ符号化装置及び方法を提供する。【解決手段】各行に成分値１を有する所定数の成分を含み、その他の成分は成分値０を有するパリティ検査行列Ｃを生成する部と、パリティ検査行列Ｃを入力されてこの成分のうちに四角形の各頂点の位置にあり、各成分値が１を満たす４個の成分で構成されたサイクル形成グループを探索して１つ以上存在すれば、前記サイクル形成グループの少なくとも１つの成分の成分値１と他の成分の成分値０とを交換してサイクル形成グループが除去されたパリティ検査行列Ｈを出力するパリティ検査行列調整部と、サイクル形成グループが除去されたパリティ検査行列Ｈを入力され、ｍ個のビットよりなったメッセージワードを入力されてＬＤＰＣコーディングを遂行する部とを含む。【選択図】　　　図１
2004140828.tif 000002
【特許請求の範囲】
【請求項１】
　各行に成分値１を有する所定数の成分を含み、各列に成分値１を有する所定数の成分を含み、その他の成分は成分値０を有するパリティ検査行列Ｃを生成するパリティ検査行列生成部と、
　前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて前記パリティ検査行列Ｃの成分のうちに四角形の各頂点の位置にあり、各成分値が１を満たす４個の成分で構成されたサイクル形成グループを探索し、前記サイクル形成グループが少なくとも１つ以上存在すれば、前記サイクル形成グループの少なくとも１つの成分の成分値１と他の成分の成分値０とを交換してサイクル形成グループが除去されたパリティ検査行列Ｈを出力するパリティ検査行列調整部と、
　前記パリティ検査行列調整部から前記サイクル形成グループが除去されたパリティ検査行列Ｈを入力されてｍ個のビットよりなったメッセージワードを入力されてＬＤＰＣコーディングを遂行するＬＤＰＣコーディング部とを含むことを特徴とするエラー訂正符号化装置。
【請求項２】
　前記パリティ検査行列調整部は、
　前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて多数の前記サイクル形成グループを探索して第１サイクル形成グループの各構成成分の位置情報である（ｗ１,ｘ１）、（ｗ１,ｙ１）、（ｚ１,ｘ１）及び（ｚ１,ｙ１）と第２サイクル形成グループの各構成成分の位置情報である（ｗ２,ｘ２）、（ｗ２,ｙ２）、（ｚ２,ｘ２）及び（ｚ２,ｙ２）とを出力する行列成分検査部と、
　前記行列成分検査部から前記第１サイクル形成グループの各構成成分の前記位置情報と前記第２サイクル形成グループの各構成成分の前記位置情報を入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を（ｉ,ｘ２）または（ｉ,ｙ２）のうち１つの位置に移動させ、前記Ｓｉｊの成分値１が移動した列に存在する２つの前記第２サイクル形成グループの構成成分Ｑｋｌ（ｋ＝ｗ２またはｚ２、ｌ＝ｘ２またはｙ２）のうち１つの成分値１を（ｋ,ｊ）位置に移動させて前記第１サイクル形成グループと前記第２サイクル形成グループを除去し、新しい２つのサイクル形成グループに対して前記サイクル形成グループ除去動作を繰り返して前記パリティ検査行列Ｈを生成する行列成分交換部とを含むことを特徴とする請求項１に記載のエラー訂正符号化装置。
【請求項３】
　前記パリティ検査行列調整部は、
　前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて多数の前記サイクル形成グループを探索して第１サイクル形成グループの各構成成分の位置情報である（ｗ１,ｘ１）、（ｗ１,ｙ１）、（ｚ１,ｘ１）及び（ｚ１,ｙ１）と第２サイクル形成グループの各構成成分の位置情報である（ｗ２,ｘ２）、（ｗ２,ｙ２）、（ｚ２,ｘ２）及び（ｚ２,ｙ２）とを出力する行列成分検査部と、
　前記行列成分検査部から前記第１サイクル形成グループの各構成成分の前記位置情報と前記第２サイクル形成グループの各構成成分の前記位置情報とを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を（ｗ２,ｊ）または（ｚ２,ｊ）のうち１つの位置に移動させ、前記Ｓｉｊの成分値が移動した列に存在する２つの前記第２サイクル形成グループの構成成分Ｑｋｌ（ｋ＝ｗ２またはｚ２、ｌ＝ｘ２またはｙ２）のうち１つの成分値１を（ｉ,ｌ）位置に移動させて前記第１サイクル形成グループと前記第２サイクル形成グループとを除去し、２つのサイクル形成グループについて前記サイクル形成グループ除去動作を繰り返して前記パリティ検査行列Ｈを生成する行列成分交換部とを含むことを特徴とする請求項１に記載のエラー訂正符号化装置。
【請求項４】
　前記ＬＤＰＣコーディング部は次の行列式
【数１】
2004140828.tif 000004
　を満足する前記行列Ｘの構成成分である前記パリティ情報ｘｉ（ｉ＝１,２,・・・,ｐ）を決定して前記メッセージワードｋｉ（ｉ＝１,２,・・・,ｍ）に前記パリティ情報ｘｉ（ｉ＝１,２,・・・,ｐ）が付加されたコードワードを出力することを特徴とする請求項１に記載のエラー訂正符号化装置。
【請求項５】
　前記行列成分交換部は前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させた場合に前記移動させた位置に成分値１が既に存在すれば、前記Ｓｉｊの成分値１を他の位置に移動させることを特徴とする請求項２に記載のエラー訂正符号化装置。
【請求項６】
　前記行列成分交換部は前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させた場合に前記移動させた位置に成分値１が既に存在すれば、前記第１サイクル形成グループの他の構成成分の成分値１を移動させることを特徴とする請求項２に記載のエラー訂正符号化装置。
【請求項７】
　前記行列成分交換部は前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させた場合に新しい第３サイクル形成グループが発生すれば、前記Ｓｉｊの成分値１を他の位置に移動させることを特徴とする請求項２に記載のエラー訂正符号化装置。
【請求項８】
　前記行列成分交換部は前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させた場合に新しい第３サイクル形成グループが発生すれば、前記第１サイクル形成グループの他の構成成分の成分値１を移動させることを特徴とする請求項２に記載のエラー訂正符号化装置。
【請求項９】
　前記行列成分交換部は前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させて前記第１サイクル形成グループと前記第２サイクル形成グループとを除去できなければ、前記行列成分検査部に他の一対のサイクル形成グループを要請して前記他の一対のサイクル形成グループに対して前記サイクル形成グループ除去動作を遂行することを特徴とする請求項２に記載のエラー訂正符号化装置。
【請求項１０】
　前記パリティ検査行列交換部は前記パリティ検査行列Ｃに存在するサイクル形成グループが共に除去されなければ、前記パリティ検査行列生成部に新しいパリティ検査行列Ｃを生成することを要請する信号を伝送することを特徴とする請求項２に記載のエラー訂正符号化装置。
【請求項１１】
　（ａ）各行に成分値１を有する所定数の成分を含み、各列に成分値１を有する所定数の成分を含み、その他の成分は成分値０を有するパリティ検査行列Ｃを生成するパリティ検査行列生成段階と、
　（ｂ）前記パリティ検査行列Ｃの成分中に四角形の各頂点の位置にあり、各成分値が１を満足する４個の成分で構成されたサイクル形成グループを探索し、前記サイクル形成グループが少なくとも１つ以上存在すれば、前記サイクル形成グループの少なくとも１つの成分の成分値１と他の成分の成分値０とを交換してサイクル形成グループが除去されたパリティ検査行列Ｈを生成するパリティ検査行列調整段階と、
　（ｃ）前記パリティ検査行列Ｈを入力されてｍ個のビットよりなったメッセージワードを入力されてＬＤＰＣコーディングを遂行するＬＤＰＣコーディング段階とを含むことを特徴とするエラー訂正符号化方法。
【請求項１２】
　前記（ｂ）段階は、
　（ｂ１）前記パリティ検査行列Ｃを入力されて多数の前記サイクル形成グループを探索して第１サイクル形成グループの各構成成分の位置情報である（ｗ１,ｘ１）、（ｗ１,ｙ１）、（ｚ１,ｘ１）及び（ｚ１,ｙ１）と第２サイクル形成グループの各構成成分の位置情報である（ｗ２,ｘ２）、（ｗ２,ｙ２）、（ｚ２,ｘ２）及び（ｚ２,ｙ２）とを出力する行列成分検査段階と、
　（ｂ２）前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を（ｉ,ｘ２）または（ｉ,ｙ２）のうち１つの位置に移動させ、前記Ｓｉｊの成分値１が移動した列に存在する２つの前記第２サイクル形成グループの構成成分Ｑｋｌ（ｋ＝ｗ２またはｚ２、ｌ＝ｘ２またはｙ２）のうち１つの成分値１を（ｋ,ｊ）位置に移動させて前記第１サイクル形成グループと前記第２サイクル形成グループとを除去する段階と、
　（ｂ３）前記（ｂ２）段階を遂行し続けて前記パリティ検査行列Ｈを生成する段階とを含むことを特徴とする請求項１１に記載のエラー訂正符号化方法。
【請求項１３】
　前記（ｂ）段階は、
　（ｂ１）前記パリティ検査行列Ｃを入力されて多数の前記サイクル形成グループを探索して第１サイクル形成グループの各構成成分の位置情報である（ｗ１,ｘ１）、（ｗ１,１）、（ｚ１,ｘ１）及び（ｚ１,ｙ１）と第２サイクル形成グループの各構成成分などの位置情報の（ｗ２,ｘ２）、（ｗ２,ｙ２）、（ｚ２,ｘ２）及び（ｚ２,ｙ２）とを出力する行列成分検査段階と、
　（ｂ２）前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を（ｗ２,ｊ）または（ｚ２,ｊ）のうち１つの位置に移動させ、前記Ｓｉｊの成分値が移動された行に存在する２つの前記第２サイクル形成グループの構成成分Ｑｋｌ（ｋ＝ｗ２またはｚ２、ｌ＝ｘ２またはｙ２）のうち１つの成分値１を（ｉ,ｌ）位置に移動させて前記第１サイクル形成グループと前記第２サイクル形成グループとを除去する段階と、
　（ｂ３）前記（ｂ２）段階を遂行し続けて前記パリティ検査行列Ｈを生成する段階とを含むことを特徴とする請求項１１に記載のエラー訂正符号化方法。
【請求項１４】
　前記（ｃ）段階は次の行列式
【数２】
2004140828.tif 000005
　を満足する前記行列Ｘの構成成分である前記パリティ情報ｘｉ（ｉ＝１,２,・・・,ｐ）を決定して前記メッセージワードｋｉ（ｉ＝１,２,・・・,ｍ）に前記パリティ情報ｘｉ（ｉ＝１,２,・・・,ｐ）が付加されたコードワードを生成する段階であることを特徴とする請求項１１に記載のエラー訂正符号化方法。
【請求項１５】
　前記（ｂ２）段階は、前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させた場合に前記移動させた位置に成分値１が既に存在すれば、前記Ｓｉｊの成分値１を他の位置に移動させる段階であることを特徴とする請求項１２に記載のエラー訂正符号化方法。
【請求項１６】
　前記（ｂ２）段階は、前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させた場合に前記移動させた位置に成分値１が既に存在すれば、前記第１サイクル形成グループの他の構成成分の成分値１を移動させる段階であることを特徴とする請求項１２に記載のエラー訂正符号化方法。
【請求項１７】
　前記（ｂ２）段階は、前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させた場合に新しい第３サイクル形成グループが発生すれば、前記Ｓｉｊの成分値１を他の位置に移動させる段階であることを特徴とする請求項１２に記載のエラー訂正符号化方法。
【請求項１８】
　前記（ｂ２）段階は、前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させた場合に新しい第３サイクル形成グループが発生すれば、前記第１サイクル形成グループの他の構成成分の成分値１を移動させる段階であることを特徴とする請求項１２に記載のエラー訂正符号化方法。
【請求項１９】
　前記（ｂ２）段階で、前記パリティ検査行列Ｃを入力されて前記第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を移動させて前記第１サイクル形成グループと前記第２サイクル形成グループとを除去できなければ、
　（ｂ２’）他の一対のサイクル形成グループを入力されて前記（ｂ２）段階を遂行する段階をさらに含むことを特徴とする請求項１２に記載のエラー訂正符号化方法。
【請求項２０】
　（ｂ４）前記パリティ検査行列Ｃに存在するサイクル形成グループが共に除去されなければ、新しいパリティ検査行列Ｃを生成する段階をさらに含み、
　前記（ｂ１）ないし前記（ｂ３）段階を遂行することを特徴とする請求項１２に記載のエラー訂正符号化方法。
【請求項２１】
　（ａ）各行に成分値１を有する所定個の成分を含み、各列に成分値１を有する所定個の成分を含み、その他の成分は成分値０を有するパリティ検査行列Ｃを生成するパリティ検査行列生成段階と、
　（ｂ）前記パリティ検査行列Ｃの成分のうち長方形の各頂点の位置にあり、各成分値が１を満足する４つの成分で構成されたサイクル形成グループを探索し、前記サイクル形成グループが少なくとも１つ以上存在すれば、前記サイクル形成グループの少なくとも１つの成分の成分値１と他の成分の成分値０とを交換してサイクル形成グループの除去されたパリティ検査行列Ｈを生成するパリティ検査行列調整段階と、
　（ｃ）前記パリティ検査行列Ｈを入力され、ｍ個のビットよりなるメッセージワードを入力されてＬＤＰＣコーディングを行うＬＤＰＣコーディング段階とを含むことを特徴とするエラー訂正符号化方法を実現するためのプログラムを記録したコンピュータで読み取られる記録媒体。
【請求項２２】
　１つ以上の行及び１つ以上の列を含み、各行及び各列は第１成分値を有する多数の成分と第２成分値とを有する多数の成分とを含むパリティ検査行列を生成するパリティ検査行列生成部と、
　前記パリティ検査行列の多数の成分のうち、長方形の各頂点に位置した４つの成分を含み、前記４つの成分は前記第１成分値を有するサイクル形成グループを探索して前記サイクル形成グループが少なくとも１つ以上存在すれば、前記各サイクル形成グループの少なくとも１つの成分の第１成分値を前記第２成分値に交替してサイクル形成グループの除去されたパリティ検査行列を出力するパリティ検査調整部と、
　ＬＤＰＣコーディングをするｍビットメッセージワードを入力されて前記調整されたパリティ検査行列を利用してＬＤＰＣコーディングを行うＬＤＰＣコーディング部とを含むことを特徴とするエラー訂正符号化装置。
【請求項２３】
　１つ以上の行及び１つ以上の列を含み、各行及び各列は第１成分値を有する多数の成分と第２成分値を有する多数の成分とを含むパリティ検査行列を生成する段階と、
　前記パリティ検査行列の多数の成分のうち、長方形の各頂点に位置した４つの成分を含み、前記４つの成分は前記第１成分値を有するサイクル形成グループを探索して前記サイクル形成グループが少なくとも１つ以上存在すれば、前記各サイクル形成グループの少なくとも１つの成分の第１成分値を前記第２成分値に交替してサイクル形成グループの除去されたパリティ検査行列を出力する段階と、
　ＬＤＰＣコーディングをするｍビットメッセージワードを入力されて前記調整されたパリティ検査行列を利用してＬＤＰＣコーディングを行う段階とを含むことを特徴とするエラー訂正符合化方法を実現するためのプログラムを記録したコンピュータで読み取られる記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明はエラー訂正符号化装置及びその方法に係り、特にＬＤＰＣ（Ｌｏｗ　Ｄｅｎｓｉｔｙ　ｐａｒｉｔｙ　Ｃｏｄｅ）符号化において、パリティ検査行列の成分を調整して符号化性能を向上させるエラー訂正符号化装置及び方法に関する。
【背景技術】
【０００２】
　無線通信分野または光記録再生分野などで使われるエラー訂正符号化技術の１つとしてＬＤＰＣ符号化方法がある。ＬＤＰＣ符号化は成分値１を有する成分が各行と各列に一定個数ずつ含まれ、その他の成分は成分値０を有するパリティ検査行列を利用してパリティ情報（付加情報）を生成する。ＬＤＰＣ符号化に対するより詳細な説明は非特許文献１に記述されている。
【０００３】
　パリティ検査行列の構成成分のうち同じ行に位置した２つの成分の成分値が１であり、その２つの成分が位置する各列に存在する成分値１の成分のうちに同じ行に位置する２つの成分が存在する場合をサイクル−４の状況という。図２Ａ及び図３Ａにサイクル−４の状況が２つ発生したパリティ検査行列の例が示されている。それぞれの図で成分値に〇と□とで示された各４つの成分が１つのサイクル−４である状況を発生させる。すなわち、サイクル−４の状況は成分値が１である４つの成分が長方形の４つの頂点を形成する場合であると言える。
【０００４】
　サイクルが存在するパリティ検査行列を利用してパリティ情報を生成すれば、復号時に復号に失敗するか復号性能が低下される問題点がある。
【０００５】
　またパリティ検査行列は線形独立的でなければならず、前述したように各行と各列に成分値１を有する成分が一定個数ずつ含まれ、その他の成分は成分値０を有すべき２つの性質を満足しなければならない。新しいパリティ検査行列を生成するか、パリティ検査行列の構成成分の位置を移動させることによって前述した２つの性質を満すと同時にサイクルを除去することは難しい問題点がある。
【非特許文献１】“Ｇｏｏｄｅｒｒｏｒ　ｃｏｒｒｅｃｔｉｏｎ　ｃｏｄｅｓ　ｂａｓｅｄ　ｏｎ　ｖｅｒｙ　ｓｐａｒｓｅ　ｍａｔｒｉｃｅｓ”（Ｄ.Ｊ.ＭａｃＫａｙ、ＩＥＥＥ　Ｔｒａｎｓ.　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ、ｖｏｌ.４５、ｎｏ.２、ｐｐ.３９９−４３１、１９９９）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
　したがって、本発明が解決しようとする技術的課題は、生成されたパリティ検査行列の構成成分のうちにサイクルを発生させる構成成分の位置を移動させることによって、パリティ検査行列に要求される性質を満すと同時にサイクルが除去されたパリティ検査行列を生成してＬＤＰＣ復号化性能を向上させるＬＤＰＣ符号化装置及び方法を提供するところにある。
【課題を解決するための手段】
【０００７】
　前記課題を解決するために、本発明によるエラー訂正符号化装置は、各行に成分値１を有する所定数の成分を含み、各行に成分値１を有する所定数の成分を含み、その他の成分は成分値０を有するパリティ検査行列Ｃを生成するパリティ検査行列生成部と、前記パリティ検査行列生成部から前記パリティ検査行列Ｃを入力されて前記パリティ検査行列Ｃの成分のうちに四角形の各頂点の位置にあり、各成分値が１を満す４個の成分で構成されたサイクル形成グループを探索して前記サイクル形成グループが少なくとも１つ以上存在すれば、前記サイクル形成グループの少なくとも１つの成分の成分値１と他の成分の成分値０を交換してサイクル形成グループが除去されたパリティ検査行列Ｈを出力するパリティ検査行列調整部と、前記パリティ検査行列調整部から前記サイクル形成グループの除去されたパリティ検査行列Ｈを入力されてｍ個のビットよりなったメッセージワードを入力されてＬＤＰＣコーディングを遂行するＬＤＰＣコーディング部とを含むことが望ましい。
【０００８】
　前記課題を解決するために、本発明によるエラー訂正符号化方法は、（ａ）各行に成分値１を有する所定数の成分を含み、各列に成分値１を有する所定数の成分を含み、その他の成分は成分値０を有するパリティ検査行列Ｃを生成するパリティ検査行列生成段階と、（ｂ）前記パリティ検査行列Ｃの成分のうちに四角形の各頂点の位置にあり、各成分値が１を満足する４個の成分で構成されたサイクル形成グループを探索して前記サイクル形成グループが少なくとも１つ以上存在すれば、前記サイクル形成グループの少なくとも１つの成分の成分値１と他の成分の成分値０とを交換してサイクル形成グループが除去されたパリティ検査行列Ｈを生成するパリティ検査行列調整段階と、（ｃ）前記パリティ検査行列Ｈを入力され、ｍ個のビットよりなったメッセージワードを入力されてＬＤＰＣコーディングを遂行するＬＤＰＣコーディング段階とを含むことが望ましい。
【０００９】
　本発明のさらに他の側面によれば、１つ以上の行及び１つ以上の列を含み、各行及び各列は第１成分値を有する多数の成分と第２成分とを有する多数の成分を含むパリティ検査行列を生成するパリティ検査行列生成部と、前記パリティ検査行列の多数の成分のうち、長方形の各頂点に位置した４つの成分を含み、前記４つの成分は前記第１成分値を有するサイクル形成グループを含み、前記４つの成分は前記第１成分値を有するサイクル形成グループを探索し、前記サイクル形成グループが少なくとも１つ以上存在すれば、前記各サイクル形成グループの少なくとも１つの成分の第１成分値を前記第２成分値に交替してサイクル形成グループの除去されたパリティ検査行列を出力するパリティ検査調整部と、ＬＤＰＣコーディングをするｍビットメッセージワードを入力されて前記調整されたパリティ検査行列を利用してＬＤＰＣコーディングを行うＬＤＰＣコーディング部とを含むことを特徴とするエラー訂正符号化装置が提供される。
【００１０】
　本発明のさらに他の側面によれば、１つ以上の行及び１つ以上の列を含み、各行及び各列は第１成分値を有する多数の成分と第２成分値とを有する多数の成分を含むパリティ検査行列を生成する段階と、前記パリティ検査行列の多数の成分のうち、長方形の各頂点に位置した４つの成分を含み、前記４つの成分は前記第１成分値を有するサイクル形成グループを探索して前記サイクル形成グループが少なくても１つ以上存在すれば、前記各サイクル形成グループの少なくとも１つ以上の成分の第１成分値を前記第２成分値に交替してサイクル形成グループの除去されたパリティ検査行列を出力する段階と、ＬＤＰＣコーディングをするｍビットメッセージワードを入力されて前記調整されたパリティ検査行列を利用してＬＤＰＣコーディングを行う段階とを含むことを特徴とするエラー訂正符合化方法を実現するためのプログラムを記録したコンピュータで読み取られる記録媒体が提供される。
【発明の効果】
【００１１】
　本発明によるエラー訂正符号化装置及び方法は、パリティ検査行列に存在するサイクル形成グループを構成する成分を適切に移動させることによってパリティ検査行列のカラムウエイトとローウエイトとを一定に維持して線形独立性を満たすと同時に、復号性能を低下させるサイクル形成グループを除去してＬＤＰＣ復号化性能を向上させうる。
【発明を実施するための最良の形態】
【００１２】
　以下、図面を参照して本発明による望ましい実施例を詳細に説明する。
【００１３】
　図１ないし図３Ｄを参照して本発明によるエラー訂正符号化装置の一実施例を説明する。
【００１４】
　図１は、本発明によるエラー訂正符号化装置のブロック図である。図１を参照すれば、エラー訂正符号化装置はパリティ検査行列生成部１１０、パリティ検査行列調整部１３０及びＬＤＰＣコーディング部１５０を含む。パリティ検査行列調整部１３０は行列成分検査部１３１及び行列成分交換部１３３を含む。
【００１５】
　パリティ検査行列生成部１１０は各行に成分値１を有する所定数の成分と各列に成分値１を有する所定数の成分を含み、その他の成分は成分値０を有するパリティ検査行列Ｃを生成する。パリティ検査行列Ｃはｐ×ｃサイズを有する。ｐはパリティ情報のビット数に該当する値であり、ｃはコードワードのビット数に該当する値であってｐにメッセージワードのビット数に該当する値ｍを加算した値である。
【００１６】
　パリティ検査行列Ｃは前述したように２つの性質を満足せねばならない。すなわち、カラムウエイトとローウエイトは各行と各列で常に一定でなければならない。カラムウエイトは各列に含まれた成分値が１である成分の個数をいい、ローウエイトは各行に含まれた成分値が１である成分の個数を言う。
【００１７】
　そして、パリティ検査行列Ｃは線形独立的でなければならない。線形独立性を満さなければ、復号時にパリティ検査行列Ｃを使用して行列演算を遂行できないためである。
【００１８】
　例えば、パリティ検査行列Ｃはｐが１００であってｍが９００になってｃが１０００である場合、各列に３個の成分値１を含み、各行に３０個の成分値１を含み、その他の成分は成分値０を有して生成できる。このような場合、パリティ検査行列Ｃはカラムウエイトが３であり、ローウエイトは３０である。カラムウエイトとローウエイト間の比率は前記例では１：１０である。しかし、これに限定される必要はない。
【００１９】
　パリティ検査行列調整部１３０はパリティ検査行列生成部１１０からパリティ検査行列Ｃを入力されてパリティ検査行列Ｃの成分のうち（ｗ,ｘ）、（ｗ,ｙ）、（ｚ,ｘ）及び（ｚ,ｙ）の位置にあり、各成分値が１である４個の成分で構成されたサイクル形成グループを探索する。探索結果、サイクル形成グループが少なくとも１つ以上存在すれば、サイクル形成グループの少なくとも１つの成分の成分値１と他の成分の成分値０とを交換してサイクル形成グループが除去されたパリティ検査行列Ｈを出力する。
【００２０】
　本実施例でサイクル形成グループとは、パリティ検査行列Ｃの成分のうちから成分値が１である４つの成分が長方形の４つの頂点を形成する場合、その構成成分の集合をいう。
【００２１】
　図２Ａないし図２Ｄは、パリティ検査行列調整部１３０によって成分値が調整されたパリティ検査行列Ｃの一実施例を示す図である。
【００２２】
　行列成分検査部１３１はパリティ検査行列Ｃに存在する多数のサイクル形成グループを探索して行列成分交換部１３３に２つのサイクル形成グループのそれぞれを構成する成分の位置情報を出力する。
【００２３】
　図２Ａを参照すれば、成分値に〇と□とで示された各４つの成分が１つのサイクル−４である状況を発生することが分かる。４個の成分□を第１サイクル形成グループと定義し、４個の他の成分○を第２サイクル形成グループと定義する。
【００２４】
　行列成分検査部１３１は第１サイクル形成グループを構成する各成分の位置情報である（ｗ１.ｘ１）、（ｗ１,ｙ１）、（ｚ１,ｘ１）及び（ｚ１,ｙ１）と第２サイクル形成グループを構成する各成分の位置情報である（ｗ２,ｘ２）、（ｗ２,ｙ２）、（ｚ２,ｘ２）及び（ｚ２,ｙ２）とを行列成分交換部１３３に出力する。
【００２５】
　行列成分交換部１３３は２つのサイクル形成グループの各構成成分の位置情報を入力されて少なくとも１つの成分値を移動させることによってサイクル形成グループを除去する。
【００２６】
　図２Ｂは、行列成分交換部１３３での動作を理解しやすく説明するために図２Ａに示されたパリティ検査行列Ｃで第１サイクル形成グループ、第２サイクル形成グループ及び周辺成分値を含み、その他の成分は省略された単純化したパリティ検査行列を示す。
【００２７】
　図２Ｃ及び図２Ｄに単純化したパリティ検査行列でサイクル形成グループの構成成分を移動させる一例が図示されている。
【００２８】
　図２Ｃを参照すれば、（１,３）の位置にあった第１サイクル形成グループの成分値１が（３,３）の位置に移動し、第１サイクル形成グループの成分が移動した第３行に存在する２つの第２サイクル形成グループの成分のうち（３、１）の位置にあった成分値１が列の値１は維持しつつ第１サイクル形成グループが存在した第１行に移動して（１,１）の位置に移動した場合を示す。
【００２９】
　図２Ｄは、（２,３）の位置にあった第１サイクル形成グループの成分値１が（３,３）の位置に移動し、第１サイクル形成グループの成分が移動した第３行に存在する２つの第２サイクル形成グループの成分のうち（３,１）の位置にあった成分値１が（２,１）の位置に移動する場合を示す。
【００３０】
　図２Ｃ及び図２Ｄに示されたような方式で各サイクル形成グループの構成成分の成分値１を移動させることによって２つのサイクル形成グループが除去され、パリティ検査行列について前述した２つの規則も相変らず満足する新しいパリティ検査行列Ｈが決定される。
【００３１】
　本実施例では各サイクル形成グループの構成成分の成分値１を列の値は維持し、行の値のみ変化させて垂直方向に移動したが、逆に行の値は維持して列の値のみ変化させて水平方向に移動させても同じ効果が達成できる。
【００３２】
　しかし、成分値を移動させる場合に問題が生じる場合がある。
【００３３】
　図３Ａないし図３Ｄは、サイクル形成グループの構成成分の成分値を移動させられない場合を説明するための図である。
【００３４】
　図３Ａには成分値に〇と□とで示された各４つの成分が１つのサイクル−４である状況を発生させるパリティ検査行列Ｃが示されている。□表示された４個の成分を第１サイクル形成グループといい、〇表示された４個の他の成分を第２サイクル形成グループという。第１サイクル形成グループ及び第２サイクル形成グループの構成成分ではない成分であって成分値が１の成分には△表示になっている。
【００３５】
　図３Ｂは、説明の便宜のために図３Ａに示されたパリティ検査行列Ｃで第１サイクル形成グループ、第２サイクル形成グループ及び周辺成分値を含み、その他の成分は除外された単純化したパリティ検査行列を示す。
【００３６】
　前述したように行列成分交換部１３３は図３Ｂに示された２つのサイクル形成グループに対して第１サイクル形成グループの１つの構成成分の成分値１を同じ列の上で行の値を変更するが、第２サイクル形成グループの構成成分が存在する行に移動させる。第１サイクル形成グループの構成成分が移動した行に存在する２つの第２サイクル形成グループの構成成分のうち１つをその列の値は維持したまま移動された第１サイクル形成グループの構成成分が元々存在した行に移動させる。
【００３７】
　図３Ｂを参考にすれば、（１,３）の位置にあった第１サイクル形成グループの成分値１を（１,１）の位置に移動できない。既に成分値１が存在するためである。行列成分交換部１３３はサイクル形成グループの構成成分を移動させようとする位置に既に成分値が１である他の成分が存在する場合には成分値１が存在しない他の位置に移動させる。行列成分交換部１３３は特定サイクル形成グループの構成成分が移動できる成分値１が存在しない位置がなければ、他の構成成分を移動させる。
【００３８】
　図３Ｃは、（２,３）の位置にあった第１サイクル形成グループの成分値１が（３,３）の位置に移動し、第１サイクル形成グループの成分が移動された第３行に存在する２つの第２サイクル形成グループの成分のうち（３,２）の位置にあった成分値１が（２,２）の位置に移動された場合を示す。このような場合、点線で表示されたように（１,１）、（１,５）、（２,１）及び（２,５）の位置に成分値１を有する４つの構成成分が存在して新しいサイクル形成グループが発生する。サイクル形成グループの構成成分を移動することによって新しいサイクル形成グループが発生すれば、その構成成分をその位置に移動できない。したがって、（２,３）の位置にある第１サイクル形成グループの構成成分は垂直方向に移動できない。
【００３９】
　図３Ｄは、（２,５）の位置にあった第１サイクル形成グループの成分値１が（３,５）の位置に移動し、第１サイクル形成グループの成分が移動した第３行に存在する２つの第２サイクル形成グループの成分のうち（３,２）の位置にあった成分値１が（２,２）の位置に移動した場合を示す。この場合にも点線で表示されたように（１,１）、（１,５）、（３,１）及び（３,５）の位置に成分値１を有する４つの構成成分が存在して新しいサイクル形成グループが発生する。したがって、（２,５）の位置にある第１サイクル形成グループの構成成分を（３,５）の位置に移動できない。
【００４０】
　図３Ｂに示されたサイクルが発生したパリティ検査行列はサイクル形成グループの如何なる構成成分を移動させても常に新しいサイクルが発生するか移動させようとする位置に既に成分値１が存在する。このような場合には行列成分交換部１３３は行列成分検査部１３１に新しい一対のサイクル形成グループの位置情報を要請する。入力された新しい一対のサイクル形成グループについて前述したような動作を遂行して２つのサイクル形成グループを除去する。
【００４１】
　行列成分交換部１３３はあらゆるサイクル形成グループが除去されるまで前記動作を遂行し続ける。
【００４２】
　もし、サイクル形成グループが除去されない場合、または１つのサイクル形成グループが残る場合には行列成分交換部１３３はパリティ検査行列生成部１１０に新しいパリティ検査行列を生成することを要請する信号を伝送する。
【００４３】
　ＬＤＰＣコーディング部１５０はパリティ検査行列交換部１３３からサイクル形成グループが除去されたパリティ検査行列Ｈを入力され、ｍ個のビットよりなったメッセージワードｋｉ（ｉ＝１,２・・・ｍ）を入力されてＬＤＰＣコーディングを遂行する。
【００４４】
　ＬＤＰＣコーディング部１５０は次の式を満足する行列Ｘを決定する。
【００４５】
【数３】
2004140828.tif 000003
　行列Ｘの構成成分のうちｋ１,ｋ２,・・・,ｋｍはｍビットよりなったメッセージワードであり、ｘ１,ｘ２,・・・,ｘｐはｐビットよりなったパリティ情報である。行列Ｈ及び行列Ｘの構成成分のうちｋi（ｉ＝１,２・・・,ｍ）は既知の値であるので前記式でパリティ情報ｘｉ（ｉ＝１,２,・・・,ｐ）を定められる。
【００４６】
　ＬＤＰＣコーディング部１５０はメッセージワードにパリティ情報が付加されたコードワードを出力してＬＤＰＣコーディングを遂行する。
【００４７】
　以下では、図１、図４及び図５を参照して本発明によるエラー訂正符号化方法の一実施例を説明する。
【００４８】
　図４は、図１に示された本発明によるエラー訂正符号化装置で実施されるエラー訂正符号化方法を説明するためのフローチャートである。
【００４９】
　パリティ検査行列生成部１１０は、各行に成分値１を有する所定数の成分と各列に成分値１を有する所定数の成分を含み、その他の成分は成分値０を有するパリティ検査行列Ｃを生成する（２１０段階）。
【００５０】
　パリティ検査行列調整部１３０はパリティ検査行列生成部１１０からパリティ検査行列Ｃを入力されてパリティ検査行列Ｃの成分のうち（ｗ,ｘ）、（ｗ,ｙ）、（ｚ,ｘ）及び（ｚ,ｙ）の位置にあり、各成分値が１である４個の成分で構成されたサイクル形成グループを探索する。探索結果、サイクル形成グループが少なくとも１つ以上存在すれば、サイクル形成グループの少なくとも１つの成分の成分値１と他の成分の成分値０を交換してサイクル形成グループの除去されたパリティ検査行列Ｈを出力する（２３０段階）。
【００５１】
　ＬＤＰＣコーディング部１５０はパリティ検査行列交換部１３３からサイクル形成グループが除去されたパリティ検査行列Ｈを入力され、ｍ個のビットよりなったメッセージワードｋｉ（ｉ＝１,２,・・・,ｍ）を入力されてＬＤＰＣコーディングを遂行する（２５０段階）。
【００５２】
　図５は、図４に示された２３０段階の詳細構成を示すフローチャートである。
【００５３】
　行列成分検査部１３１はパリティ検査行列生成部１１０からパリティ検査行列Ｃを入力され、パリティ検査行列Ｃに存在する多数のサイクル形成グループを探索して第１サイクル形成グループの各構成成分の位置情報である（ｗ１,ｘ１）、（ｗ１,ｙ１）、（ｚ１,ｘ１）及び（ｚ１,ｙ１）と第２サイクル形成グループの各構成成分の位置情報である（ｗ２,ｘ２）、（ｗ２,ｙ２）、（ｚ２,ｘ２）及び（ｚ２,ｙ２）を行列成分交換部１３３に出力する（２３１段階）。
【００５４】
　行列成分交換部１３３は第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１でありｊ＝ｘ１またはｙ１）の成分値１を（ｉ,ｘ２）または（ｉ,ｙ２）のうち１つの位置に水平方向に移動させ、Ｓｉｊの成分値１が移動した列に存在する２つの前記第２サイクル形成グループの構成成分Ｑｋｌ（ｋ＝ｗ２またはｚ２、ｌ＝ｘ２またはｙ２）のうち１つの成分値１を（ｋ、ｊ）位置に移動させて第１サイクル形成グループと第２サイクル形成グループとを除去する（２３３段階）。行列成分交換部１３３はサイクル形成グループの構成成分を水平方向だけではなく垂直方向に移動させることによって同じ効果が得られる。すなわち、第１サイクル形成グループの１つの構成成分Ｓｉｊ（ｉ＝ｗ１またはｚ１、ｊ＝ｘ１またはｙ１）の成分値１を（ｗ２、ｊ）または（ｚ２、ｊ）のうち１つの位置に垂直方向に移動させ、Ｓｉｊの成分値が移動した行に存在する２つの第２サイクル形成グループの構成成分Ｑｋｌ（ｋ＝ｗ２またはｚ２、ｌ＝ｘ２またはｙ２）のうち１つの成分値１を（ｉ,ｌ）位置に垂直方向に移動させて第１サイクル形成グループと第２サイクル形成グループとを除去する（２３３段階）。行列成分交換部１３３はあらゆるサイクル形成グループが除去されるまで２３１段階及び２３３段階を遂行し続ける（２３５段階）。
【００５５】
　また本発明はコンピュータで読み取られる記録媒体にコンピュータが読めるコードとして具現することが可能である。コンピュータが読み取られる記録媒体はコンピュータシステムによって読み取られるデータが貯蔵されるあらゆる種類の記録装置を含む。コンピュータが読み取られる記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ貯蔵装置などがあり、またキャリアウェーブ（例えば、インターネットを通じた伝送）の形態で具現されるものも含む。またコンピュータが読み取られる記録媒体はネットワークに連結されたコンピュータシステムに分散されて分散方式にコンピュータが読み取られるコードで貯蔵されて実行できる。
【産業上の利用可能性】
【００５６】
　本発明は、無線データ通信または光記録媒体にデータの記録または再生などで利用されるエラー訂正符合化分野に利用できる。
【図面の簡単な説明】
【００５７】
【図１】本発明によるエラー訂正符号化装置の一実施例を説明するためのブロック図である。
【図２Ａ】図１に示されたパリティ検査行列調整部によって成分値が調整されたパリティ検査行列の一実施例を示す図である。
【図２Ｂ】図１に示されたパリティ検査行列調整部によって成分値が調整されたパリティ検査行列の一実施例を示す図である。
【図２Ｃ】図１に示されたパリティ検査行列調整部によって成分値が調整されたパリティ検査行列の一実施例を示す図である。
【図２Ｄ】図１に示されたパリティ検査行列調整部によって成分値が調整されたパリティ検査行列の一実施例を示す図である。
【図３Ａ】サイクル形成グループの構成成分の成分値を移動できない場合を示す図である。
【図３Ｂ】サイクル形成グループの構成成分の成分値を移動できない場合を示す図である。
【図３Ｃ】サイクル形成グループの構成成分の成分値を移動できない場合を示す図である。
【図３Ｄ】サイクル形成グループの構成成分の成分値を移動できない場合を示す図である。
【図４】図１に示された本発明によるエラー訂正符号化装置で実施されるエラー訂正符号化方法を説明するためのフローチャートである。
【図５】図４に示された２３０段階の詳細構成を示すフローチャートである。
【符号の説明】
【００５８】
１１０　パリティ検査行列生成部
１３０　パリティ検査行列調整部
１３３　行列成分交換部
１５０　ＬＤＰＣコーディング部
【図１】
2004140828.tif 000006
【図２Ａ】
2004140828.tif 000007
【図２Ｂ】
2004140828.tif 000008
【図２Ｃ】
2004140828.tif 000009
【図２Ｄ】
2004140828.tif 000010
【図３Ａ】
2004140828.tif 000011
【図３Ｂ】
2004140828.tif 000012
【図３Ｃ】
2004140828.tif 000013
【図３Ｄ】
2004140828.tif 000014
【図４】
2004140828.tif 000015
【図５】
2004140828.tif 000016