(57)【要約】  誤り訂正符号化装置１は、パリティ検査行列のうちの情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算部２と、パリティ検査行列のうちのパリティビット系列に対応した部分行列に対して予め定められた基本行列操作を施して予め定められた行列を算出しておく基本行列操作部３と、基本行列操作部３の算出した予め定められた行列と疎行列演算部２の算出したベクトルを掛け、パリティビット系列を算出する行列掛け算部４とを備える。
2014069464.tif 000002
【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号用の疎なパリティ検査行列を用いて、情報ビット系列からパリティビット系列を算出し符号化する誤り訂正符号化方法であって、
前記パリティ検査行列のうちの前記情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と前記情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算ステップと、
前記パリティ検査行列のうちの前記パリティビット系列に対応した部分行列に対して予め定められた基本行列操作を施した予め定められた行列に、前記疎行列演算ステップで得られた前記ベクトルを掛ける行列掛け算ステップとを備えることを特徴とする誤り訂正符号化方法。
【請求項２】
前記予め定められた行列は、前記パリティ検査行列のうちの前記パリティビット系列に対応する部分行列の逆行列であって、前記行列掛け算ステップでは、当該逆行列と前記疎行列演算ステップで得られた前記ベクトルを掛けることを特徴とする請求項１記載の誤り訂正符号化方法。
【請求項３】
前記予め定められた行列は、前記パリティ検査行列のうちの前記パリティビット系列に対応する部分行列を下三角行列に変換するための行列であって、前記行列掛け算ステップでは、当該行列と前記疎行列演算ステップで得られた前記ベクトルを掛けることを特徴とする請求項１記載の誤り訂正符号化方法。
【請求項４】
前記行列掛け算ステップで得られた前記ベクトルと前記下三角行列を用いて前記パリティビット系列を算出するパリティビット算出ステップを備えることを特徴とする請求項３記載の誤り訂正符号化方法。
【請求項５】
ＱＣ（Ｑｕａｓｉ−Ｃｙｃｌｉｃ）−ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号用の疎なパリティ検査行列を用いて、情報ビット系列からパリティビット系列を算出し符号化する誤り訂正符号化方法であって、
前記パリティ検査行列のうちの前記情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と前記情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算ステップと、
前記疎行列演算ステップで得られた前記ベクトルの要素の一部を足し合わせるベクトル要素加算ステップと、
前記パリティ検査行列のうちの前記パリティビット系列に対応する部分行列の一部を加算した行列の逆行列に、前記ベクトル要素加算ステップで得られた前記ベクトルを掛けて、前記パリティビット系列の一部を算出する第１の行列掛け算ステップと、
前記パリティ検査行列のうちの前記パリティビット系列に対応する前記部分行列の残りの部分に、前記第１の行列掛け算ステップで得られた前記パリティビット系列の一部を掛ける第２の行列掛け算ステップと、
前記ベクトル要素加算ステップで得られた前記ベクトルと前記第２の行列掛け算ステップで得られた前記ベクトルを足し合わせて、前記パリティビット系列の残りの部分を算出するパリティビット算出ステップとを備えることを特徴とする誤り訂正符号化方法。
【請求項６】
ＱＣ（Ｑｕａｓｉ−Ｃｙｃｌｉｃ）−ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号用の疎なパリティ検査行列を用いて、情報ビット系列からパリティビット系列を算出し符号化する誤り訂正符号化方法であって、
前記情報ビット系列ｄb,iは、各要素をｑ個毎にブロックに分けたとき、ｉ（１≦ｉ≦Ｋ）番目のブロックに対応するｑ個の要素からなるベクトルであり、
前記パリティビット系列ｐb,iは、各要素をｑ個毎にブロックに分けたとき、ｉ（１≦ｉ≦Ｍ）番目のブロックに対応するｑ個の要素からなるベクトルであり、
Ｍ行Ｎ列の前記パリティ検査行列は、前記情報ビット系列に対応するＭ行Ｋ列（Ｋ＝Ｎ−Ｍ）の部分行列Ｘijと、前記パリティビット系列に対応するＭ行Ｍ列のうちの１列目の部分行列Ｚjと、対角成分２行分に単位行列を含む部分行列とからなり、
下記に示す３つの式に従って、前記パリティビット系列の各要素を算出することを特徴とする誤り訂正符号化方法。
2014069464.tif 000028
2014069464.tif 000029
2014069464.tif 000030
ここで、Ｔは転置行列である。
【請求項７】
前記パリティ検査行列は、前記情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、前記パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列目以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に単位行列を含む構成であり、前記部分行列Ｘij，Ｚjおよび前記巡回置換行列Ａjの一部が巡回シフトされることを特徴とする請求項５記載の誤り訂正符号化方法。
【請求項８】
前記パリティ検査行列は、前記情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、前記パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列目以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に単位行列を含む構成であり、前記部分行列Ｘij，Ｚjおよび前記巡回置換行列Ａjの一部が巡回シフトされることを特徴とする請求項６記載の誤り訂正符号化方法。
【請求項９】
前記パリティ検査行列は、前記情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、前記パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に巡回置換行列Ｂjを含む構成であり、前記部分行列Ｘij，Ｚjおよび前記巡回置換行列Ａj，Ｂjの一部が巡回シフトされることを特徴とする請求項５記載の誤り訂正符号化方法。
【請求項１０】
前記パリティ検査行列は、前記情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、前記パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に巡回置換行列Ｂjを含む構成であり、前記部分行列Ｘij，Ｚjおよび前記巡回置換行列Ａj，Ｂjの一部が巡回シフトされることを特徴とする請求項６記載の誤り訂正符号化方法。
【請求項１１】
ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号用の疎なパリティ検査行列を用いて、情報ビット系列からパリティビット系列を算出し符号化する誤り訂正符号化装置であって、
前記パリティ検査行列のうちの前記情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と前記情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算部と、
前記パリティ検査行列のうちの前記パリティビット系列に対応した部分行列に対して予め定められた基本行列操作を施した予め定められた行列に、前記疎行列演算部で得られた前記ベクトルを掛ける行列掛け算部とを備えることを特徴とする誤り訂正符号化装置。
【請求項１２】
ＱＣ（Ｑｕａｓｉ−Ｃｙｃｌｉｃ）−ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号用の疎なパリティ検査行列を用いて、情報ビット系列からパリティビット系列を算出し符号化する誤り訂正符号化装置であって、
前記パリティ検査行列のうちの前記情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と前記情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算部と、
前記疎行列演算部で得られた前記ベクトルの要素の一部を足し合わせるベクトル要素加算部と、
前記パリティ検査行列のうちの前記パリティビット系列に対応する部分行列の一部を加算した行列の逆行列に、前記ベクトル要素加算部で得られた前記ベクトルを掛けて、前記パリティビット系列の一部を算出する第１の行列掛け算部と、
前記パリティ検査行列のうちの前記パリティビット系列に対応する前記部分行列の残りの部分に、前記第１の行列掛け算部で得られた前記パリティビット系列の一部を掛ける第２の行列掛け算部と、
前記ベクトル要素加算部で得られた前記ベクトルと前記第２の行列掛け算部で得られた前記ベクトルを足し合わせて、前記パリティビット系列の残りの部分を算出するパリティビット算出部とを備えることを特徴とする誤り訂正符号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ（低密度パリティ検査）符号（以下、ＬＤＰＣ符号と称す）に準じて符号化する誤り訂正符号化方法および誤り訂正符号化装置に関するものである。
【背景技術】
【０００２】
誤り訂正符号は、通信システムにおいて、通信路の雑音に起因して生じる誤りビットを訂正する技術である。本技術を用いた通信システムでは、送信機から情報データをそのまま送信するのではなく、送信する情報ビット系列ｄ（式１）に対し、符号化と呼ばれる処理を行ってパリティビット系列ｐ（式２）を算出し、情報ビット系列ｄとパリティビット系列ｐとを合わせた系列である符号語ｃ（式３）を送信する。【０００３】
2014069464.tif 000003
【０００４】
パリティビット系列ｐの分だけ送信ビットレートは下がるが、受信機において情報ビット系列ｄとパリティビット系列ｐの双方を用いて復号と呼ばれる処理を行うことにより、受信データ内に存在する誤りを訂正したり、検出したりできる。【０００５】
ＬＤＰＣ符号は、図１３に示すように、非零要素が少ない疎なパリティ検査行列で定義される誤り訂正符号である。ここでは、行列要素は０と１のみであるとする。パリティ検査行列の列数は符号語ｃのビット数（符号長）ｎと対応し、また、多くの場合に行数がパリティビット数ｍとなる。情報ビット系列ｄのビット数ｋは、ｋ＝ｎ−ｍである。【０００６】
ＬＤＰＣ符号の符号化を行う従来技術として、下三角行列を用いる方法が非特許文献１に開示されている。この、下三角行列を用いる方法では、まずパリティ検査行列に対して後述する基本行列操作を施し、行列右側のｍ行ｍ列（以下、ｍ×ｍ）部分行列における右上方を０にして、図１４に示すような下三角行列を得る。そして、この下三角行列を用い、後退代入によってパリティビットを算出し符号化を行う。【０００７】
ここで、基本行列操作は、（１）２つの行を入れ替える、（２）２つの列を入れ替える、（３）行ｉに対し、行ｊ（ｉ≠ｊ）をｍｏｄ２で加算する（即ち、排他的論理和を計算する）ことである。【０００８】
下三角行列を用いる従来方法の場合、パリティ検査行列に対して基本行列操作を行うことにより、行列の非零要素が増大してしまい、その結果、パリティ検査行列が疎であったとしても、下三角行列は疎な行列ではなくなってしまう。そのため、下三角行列を用いる従来方法では、非零要素の増大に伴い演算量が増大してしまう。【０００９】
他方、非特許文献１には、下三角行列を用いる方法とは別に、古くから知られている符号化方法も開示されている。この符号化方法では、上記の下三角行列に対してさらに基本行列操作を施し、図１５に示すように、行列の右側を単位行列にする。この行列の左側ｍ×ｋ部分行列をＱ２とすると、情報ビット系列ｄに対して左から行列Ｑ２を掛けることでパリティビット系列ｐを求めることができる。このときの行列Ｑ２（または、行列Ｑ２の転置行列）を生成行列と呼ぶ。【００１０】
しかし、図１５の生成行列Ｑ２に含まれる１の数は、図１４の行列Ｑ１と同等か、または行列Ｑ１より多くなる場合が多い。そのため、上記の下三角行列を用いた従来方法と同様、排他的論理和の回数が多く、演算量が大きいという問題があった。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】和田山正著、「低密度パリティ検査符号とその復号法」トリケップス、２００２年６月５日発行
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従来のＬＤＰＣ符号の符号化方法は、非零要素が多い行列を用いて符号化を行うため、演算量が多いという課題があった。また、演算量が多いことに起因して、回路実装の際の回路規模が増大するという課題があった。【００１３】
この発明は、上記のような課題を解決するためになされたもので、ＬＤＰＣ符号の符号化における演算量の削減、および実装時の回路規模削減を目的とする。
【課題を解決するための手段】
【００１４】
この発明に係る誤り訂正符号化方法は、パリティ検査行列のうちの情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算ステップと、パリティ検査行列のうちのパリティビット系列に対応した部分行列に対して予め定められた基本行列操作を施した予め定められた行列に、疎行列演算ステップで得られたベクトルを掛ける行列掛け算ステップとを備えるものである。【００１５】
この発明に係る誤り訂正符号化方法は、パリティ検査行列のうちの情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算ステップと、疎行列演算ステップで得られたベクトルの要素の一部を足し合わせるベクトル要素加算ステップと、パリティ検査行列のうちのパリティビット系列に対応する部分行列の一部を加算した行列の逆行列に、ベクトル要素加算ステップで得られたベクトルを掛けて、パリティビット系列の一部を算出する第１の行列掛け算ステップと、パリティ検査行列のうちのパリティビット系列に対応する部分行列の残りの部分に、第１の行列掛け算ステップで得られたパリティビット系列の一部を掛ける第２の行列掛け算ステップと、ベクトル要素加算ステップで得られたベクトルと第２の行列掛け算ステップで得られたベクトルを足し合わせて、パリティビット系列の残りの部分を算出するパリティビット算出ステップとを備えるものである。【００１６】
この発明に係る誤り訂正符号化方法は、情報ビット系列ｄb,iが、各要素をｑ個毎にブロックに分けたとき、ｉ（１≦ｉ≦Ｋ）番目のブロックに対応するｑ個の要素からなるベクトルであり、パリティビット系列ｐb,iは、各要素をｑ個毎にブロックに分けたとき、ｉ（１≦ｉ≦Ｍ）番目のブロックに対応するｑ個の要素からなるベクトルであり、Ｍ行Ｎ列のパリティ検査行列は、情報ビット系列に対応するＭ行Ｋ列（Ｋ＝Ｎ−Ｍ）の部分行列Ｘijと、パリティビット系列に対応するＭ行Ｍ列のうちの１列目の部分行列Ｚjと、対角成分２行分に単位行列を含む部分行列とからなり、後述する式（２４）、式（２６）および式（２７）に従って、パリティビット系列の各要素を算出するものである。【００１７】
この発明に係る誤り訂正符号化装置は、パリティ検査行列のうちの情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算部と、パリティ検査行列のうちのパリティビット系列に対応した部分行列に対して予め定められた基本行列操作を施した予め定められた行列に、疎行列演算部で得られたベクトルを掛ける行列掛け算部とを備えるものである。【００１８】
この発明に係る誤り訂正符号化装置は、パリティ検査行列のうちの情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算部と、疎行列演算部で得られたベクトルの要素の一部を足し合わせるベクトル要素加算部と、パリティ検査行列のうちのパリティビット系列に対応する部分行列の一部を加算した行列の逆行列に、ベクトル要素加算部で得られたベクトルを掛けて、パリティビット系列の一部を算出する第１の行列掛け算部と、パリティ検査行列のうちのパリティビット系列に対応する部分行列の残りの部分に、第１の行列掛け算部で得られたパリティビット系列の一部を掛ける第２の行列掛け算部と、ベクトル要素加算部で得られたベクトルと第２の行列掛け算部で得られたベクトルを足し合わせて、パリティビット系列の残りの部分を算出するパリティビット算出部とを備えるものである。
【発明の効果】
【００１９】
この発明によれば、パリティ検査行列と情報ビット系列の掛け算を２工程に分けて行うようにしたので、行列掛け算ステップでベクトルに掛け合わせる疎でない行列のサイズを従来方法よりも小さくすることができる。よって、ＬＤＰＣ符号の符号化の演算量を削減することができる。【００２０】
この発明によれば、パリティ検査行列と情報ビット系列の掛け算を複数工程に分けて行うようにしたので、行列掛け算ステップでベクトルに掛け合わせる疎でない行列のサイズを従来方法よりも小さくすることができ、また、演算の多くを疎な行列を用いて行うことができる。よって、ＱＣ（Ｑｕａｓｉ−Ｃｙｃｌｉｃ）−ＬＤＰＣ符号の符号化の演算量を削減することができる。【００２１】
この発明によれば、後述する式（２４）、式（２６）および式（２７）を用いるようにしたので、演算の多くを疎な行列を用いて行うことができ、ＱＣ−ＬＤＰＣ符号の符号化の演算量を削減することができる。【００２２】
この発明によれば、パリティ検査行列と情報ビット系列の掛け算を２工程に分けて行うようにしたので、行列掛け算ステップでベクトルに掛け合わせる疎でない行列のサイズを従来方法よりも小さくすることができる。よって、ＬＤＰＣ符号の誤り訂正符号化装置の回路規模を削減することができる。【００２３】
この発明によれば、パリティ検査行列と情報ビット系列の掛け算を複数工程に分けて行うようにしたので、行列掛け算ステップでベクトルに掛け合わせる疎でない行列のサイズを従来方法よりも小さくすることができ、また、演算の多くを疎な行列を用いて行うことができる。よって、ＱＣ−ＬＤＰＣ符号の誤り訂正符号化装置の回路規模を削減することができる。
【図面の簡単な説明】
【００２４】
【図１】この発明の実施の形態１に係る誤り訂正符号化装置の構成を示すブロック図である。
【図２】実施の形態１に係る誤り訂正符号化装置において用いるパリティ検査行列の構成を説明する図である。
【図３】実施の形態１に係る誤り訂正符号化装置の動作を示すフローチャートである。
【図４】この発明の実施の形態２に係る誤り訂正符号化装置の構成を示すブロック図である。
【図５】実施の形態２に係る誤り訂正符号化装置の動作を示すフローチャートである。
【図６】この発明の実施の形態３に用いるＱＣ−ＬＤＰＣ符号の一例を示す図である。
【図７】実施の形態３に係る誤り訂正符号化装置の構成を示すブロック図である。
【図８】実施の形態３に係る誤り訂正符号化装置の動作を示すフローチャートである。
【図９】この発明の実施の形態４に係る誤り訂正符号化装置の構成を示すブロック図である。
【図１０】図６に示すパリティ検査行列に対する基本行列操作を説明する図である。
【図１１】実施の形態４に用いるＱＣ−ＬＤＰＣ符号の一例を示す図である。
【図１２】実施の形態４に用いるＱＣ−ＬＤＰＣ符号の別の例を示す図である。
【図１３】ＬＤＰＣ符号のパリティ検査行列の構成を説明する図である。
【図１４】従来の符号化方法において用いるパリティ検査行列の構成例を説明する図である。
【図１５】従来の符号化方法において用いるパリティ検査行列の別の構成例を説明する図である。
【発明を実施するための形態】
【００２５】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１に示す誤り訂正符号化装置１は、疎行列演算部２と、基本行列操作部３と、行列掛け算部４とを備え、ＬＤＰＣ符号の符号化として、情報ビット系列ｄを入力とし、パリティ検査行列Ｈに基づいた条件を満たすパリティビット系列ｐを算出する。
【００２６】
ＬＤＰＣ符号のパリティ検査行列Ｈと符号語ｃとには、式（４）のような関係がある。
2014069464.tif 000004
ここで、行列Ｈとベクトルｃの掛け算で行う要素（ビット）同士の加算は、ｍｏｄ２の加算（排他的論理和と同じ）とする。また、Ｔは転置を表す。
【００２７】
パリティ検査行列Ｈは、式（５）および図２のように表される。このパリティ検査行列Ｈは、情報ビット系列ｄに対応するｍ×ｋ行列Ｘと、パリティビット系列ｐに対応するｍ×ｍ行列Ｙとを含み、ｍ×ｍ行列Ｙは正則行列とする。すると、式（４）の左辺は、式（６）のように変形できる。この式（６）と式（４）とから、パリティビット系列ｐは式（７）のように求められる。
【００２８】
2014069464.tif 000005
2014069464.tif 000006
2014069464.tif 000007
【００２９】
上記を踏まえ、本実施の形態１を説明する。図３は、本実施の形態１に係る誤り訂正符号化装置１の動作を示すフローチャートである。
ステップＳＴ１１では、疎行列演算部２が上式（６）に従って、情報ビット系列ｄと、パリティ検査行列Ｈのｍ×ｋ行列Ｘとの排他的論理和を演算し、ＸｄTのベクトルを得る。ここで、ｍ×ｋ行列Ｘはパリティ検査行列Ｈの部分行列であるから疎であり、１の数が少ない。そのため、本ステップＳＴ１１での排他的論理和の回数は、ｍ×ｋ回に比べて非常に小さい。
【００３０】
次のステップＳＴ１２では、行列掛け算部４が上式（４）に従って、別途算出しておいたｍ×ｍ行列Ｙの逆行列Ｙ-1を、ステップＳＴ１１の算出結果ＸｄTに掛け、Ｙ-1ＸｄTのベクトルを得る。逆行列Ｙ-1は、基本行列操作部３がパリティ検査行列Ｈのｍ×ｍ行列Ｙから予め算出しておく。この逆行列Ｙ-1はｍ×ｍ行列であり、必ずしも疎な行列ではない。そのため、本ステップＳＴ１２では約ｍ×ｍ／２回の排他的論理和を計算する必要がある。
【００３１】
本実施の形態１において、排他的論理和の回数はステップＳＴ１２の回数が支配的であり、約ｍ×ｍ／２回となる。一方、先立って説明した従来方法においては排他的論理和の回数がｍ×ｋ／２回であるので、ｍ＜ｋのときは本実施の形態１の方が演算量が小さい。なお、実際の誤り訂正符号化装置で用いられるＬＤＰＣ符号のほとんどはｍ＜ｋを満たす。
【００３２】
以上より、実施の形態１によれば、誤り訂正符号化装置１は、パリティ検査行列のうちの情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算ステップと、パリティ検査行列のうちのパリティビット系列に対応した部分行列に対して予め定められた基本行列を施した予め定められた行列（即ち、パリティ検査行列のうちのパリティビット系列に対応する部分行列の逆行列Ｙ-1）に、疎行列演算ステップで得られたベクトルを掛ける行列掛け算ステップとを実施するようにした。このため、パリティ検査行列と情報ビット系列の掛け算を２回に分けて行うことで、掛け算に用いる疎でない逆行列のサイズを従来方法よりも小さくすることができる。従って、ＬＤＰＣ符号の符号化の演算量を削減することができる。
【００３３】
なお、実施の形態１のステップＳＴ１１，ＳＴ１２それぞれの演算はビット同士の加算と乗算であるので、一例として、加算を排他的論理和（ＥＸＯＲ）ゲートで行い、乗算を論理積（ＡＮＤ）ゲートで行う回路を構成できる。つまり、誤り訂正符号化装置１において、疎行列演算部２および行列掛け算部４それぞれを、排他的論理和ゲートと論理積ゲートとからなる回路で構成する。
この回路構成の場合、掛け算に用いる疎でない逆行列Ｙ-1のサイズを従来方法よりも小さくしたことにより排他的論理和の回数を削減でき、結果、誤り訂正符号化装置１の回路規模も削減することができる。
【００３４】
また、実施の形態１では、式（３）で示したように、符号語ｃのベクトルの左側を情報ビット系列ｄとし、右側をパリティビット系列ｐとした場合の誤り訂正符号化方法を説明したが、これに限定されるものではない。例えば、符号語ｃのうちの任意の部分をパリティビット系列ｐとしてもよく、そのような場合に本実施の形態１の構成を実現するには、一例として符号語ｃの要素を並び替える処理を行ってパリティビット系列ｐをベクトル右側にし、パリティ検査行列Ｈの列もそれに合わせて並び替える処理を行う方法がある。パリティ検査行列Ｈの列を並び替えてもＬＤＰＣ符号の本質的な性質は変化しないので、このような方法が可能である。
【００３５】
また、実施の形態１では、誤り訂正符号化装置１が基本行列操作部３を備え、ＬＤＰＣ符号のパリティ検査行列に対して基本行列操作を施す構成にしたが、この基本行列操作は情報ビット系列には依存せず、パリティ検査行列のみに基づいて演算が行われるため、パリティ検査行列に対して基本行列操作を行った演算結果を予め求めておき、演算結果をメモリ等の記憶部にデータとして保持させ行列掛け算部４がそのデータを使用する構成にしたり、演算結果を行列掛け算部４に組み込んで構成しておくことが可能である。この場合には基本行列操作部３を省略できる。
【００３６】
実施の形態２．
図４は、本実施の形態２に係る誤り訂正符号化装置１の構成を示すブロック図である。本実施の形態２に係る誤り訂正符号化装置１は、疎行列演算部２と、基本行列操作部３と、行列掛け算部４と、パリティビット算出部５とを備える。なお、図４において図１と同一または相当の部分については同一の符号を付し説明を省略する。
【００３７】
上記実施の形態１では、上式（４）を上式（７）のように変形した場合の誤り訂正符号化方法を説明したが、本実施の形態２では、上式（４）を下式（８）のように変形した場合の誤り訂正符号化方法を説明する。
【００３８】
2014069464.tif 000008
【００３９】
式（８）の行列Ｔlは、ｍ×ｍ行列であり、下式（９）に示すような下三角行列である。つまり、行列Ｔlのｉ行ｊ列の要素をＴl（ｉｊ）と表すと、行列Ｔlは式（１０）および式（１１）を満たす。
なお、行列Ｔlは、式（９）、式（１０）、および式（１１）を満たすｍ×ｍ行列であればどんなものでもよい。
【００４０】
2014069464.tif 000009
なお、式（９）において行列Ｔlの左下半分は０または１である。
2014069464.tif 000010
2014069464.tif 000011
【００４１】
式（８）において、行列Ｓはｍ×ｍ行列であり、ＳＹ＝Ｔlを満たす行列である。所定の行列Ｗ＝［ＹＩ］（ただし、Ｉは単位行列とする）に対し、Ｙの部分がＴlとなるように基本行列操作を施せば、この行列Ｗは［ＴlＳ］となり、右側部分がＳとなる。つまり、この行列Ｓは、ｍ×ｍ行列Ｙを下三角行列Ｔlに変換するための行列である。
この行列Ｓは、基本行列操作部３が予め算出しておく。
【００４２】
ここで、式（８）の最下段右辺（ＳＸｄT）を、式（１２）のようにベクトルｕで表すと、パリティビット系列ｐの１番目の要素ｐ１は、式（１３）のように算出できる。また、ｐ１以外の要素は、後退代入と呼ばれる操作を用いて式（１４）のように算出できる。
【００４３】
2014069464.tif 000012
2014069464.tif 000013
2014069464.tif 000014
【００４４】
上記を踏まえ、本実施の形態２を説明する。図５は、本実施の形態２に係る誤り訂正符号化装置１の動作を示すフローチャートである。
ステップＳＴ２１では、上記実施の形態１のステップＳＴ１１と同様に、疎行列演算部２が、情報ビット系列ｄとパリティ検査行列Ｈのｍ×ｋ行列Ｘとの排他的論理和を演算し、ＸｄTのベクトルを得る。
【００４５】
ステップＳＴ２２では、行列掛け算部４が上式（１２）に従って、別途算出しておいた行列Ｓを、ステップＳＴ２１の算出結果ＸｄTに掛け、ベクトルｕを得る。ここで、行列Ｓはｍ×ｍ行列の疎ではない行列である。そのため、本ステップＳＴ２２では約ｍ×ｍ／２回の排他的論理和を計算する必要がある。
【００４６】
ステップＳＴ２３では、パリティビット算出部６が上式（１３）および上式（１４）に従って、ステップＳＴ２２で得たベクトルｕからパリティビット系列ｐの要素を順次算出する。本ステップＳＴ２３の演算量は、行列Ｔlが含む１の数に依存し、排他的論理和は約ｍ×ｍ／４回となる。
【００４７】
先立って説明した従来方法では、情報ビット系列ｄに対して行列Ｑ１を掛け、その後、式（１３）と式（１４）と同様に計算でパリティビット系列ｐを求めている。しかし、行列Ｑ１はｍ×ｋ行列の疎ではない行列である。そのため、約ｍ×ｋ／２回の排他的論理和を計算する必要があり、演算量が大きい。
【００４８】
一方、本実施の形態２では、排他的論理和の回数がステップＳＴ２１でｍ×ｍ回より非常に少ない回数、ステップＳＴ２２で約ｍ×ｍ／２回、ステップＳＴ２３で約ｍ×ｍ／４回であるため、合計約３×ｍ×ｍ／４回の排他的論理和の計算によりＬＤＰＣ符号の符号化を行うことができる。そのため、ｍ＜ｋ、かつ、ｍとｋの差が大きい場合に、従来方法の約ｍ×ｋ／２回よりも演算量を削減することができる。
【００４９】
また、本実施の形態２で見積もった演算量の値である約３×ｍ×ｍ／４は、上記実施の形態１の約ｍ×ｍ／２よりも大きい。しかし、これら演算量の実際の値は、行列Ｓ，Ｔl、および実施の形態１における逆行列Ｙ-1に依存するため、具体的な演算量は実施するパリティ検査行列Ｈによって異なる。また、パリティ検査行列Ｈによっては、本実施の形態２での演算量が上記実施の形態１での演算量よりも少なくなる。いずれにしても、従来方法の演算量よりも削減することができる。
【００５０】
以上より、実施の形態２によれば、誤り訂正符号化装置１は、パリティ検査行列のうちの情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算ステップと、パリティ検査行列のうちのパリティビット系列に対応した部分行列に対して予め定められた基本行列を施した予め定められた行列（即ち、パリティ検査行列のうちのパリティビット系列に対応する部分行列を下三角行列Ｔlに変換するための行列Ｓ）に、疎行列演算ステップで得られたベクトルを掛ける行列掛け算ステップとを実施するようにした。このため、パリティ検査行列と情報ビット系列の掛け算を２回に分けて行うことで、掛け算に用いる疎でない行列のサイズを従来方法よりも小さくすることができる。従って、ＬＤＰＣ符号の符号化の演算量を削減することができる。
【００５１】
また、実施の形態２によれば、誤り訂正符号化装置１は、行列掛け算ステップで得られたベクトルと下三角行列を用いてパリティビット系列を算出するパリティビット算出ステップを実施するようにした。このため、少ないベクトルの加算回数でパリティビット系列を算出でき、ＬＤＰＣ符号の符号化の演算量を削減できる。
【００５２】
なお、実施の形態２では、行列Ｔlを下三角行列としたが、これに限定されるものではない。その場合、ステップＳＴ２３を式（１４）のようなベクトルの加算により実施可能か否かが演算量の観点で問題となるが、ステップＳＴ２３をベクトルの加算により実施可能な行列Ｔlの構造は下三角行列に限らない。少ないベクトルの加算回数でステップＳＴ２３を構成できれば、小さな演算量でＬＤＰＣ符号の符号化を行うことができる。
このような行列Ｔlの例として、下三角行列の列もしくは行を入れ替えたような行列、または一部が下三角となっているような行列がある。また、当然ながら、行列Ｔlを単位行列とすれば、行列Ｓはｍ×ｍ行列Ｙの逆行列Ｙ-1と等しくなり、つまりは上記実施の形態１と同じ構成となる。
いずれにしても、上記で説明した基本行列操作による行列Ｓの算出方法と同様にして、基本行列操作部３が行列Ｔlから行列Ｓを算出でき、ステップＳＴ２２を実施可能である。
【００５３】
また、実施の形態２のステップＳＴ２１〜ＳＴ２３それぞれの演算はビット同士の加算と乗算であるので、上記実施の形態１と同様に、疎行列演算部２、行列掛け算部４およびパリティビット算出部５それぞれを、排他的論理和ゲートと論理積ゲートとからなる回路で構成できる。
この回路構成の場合、掛け算に用いる疎でない行列Ｓのサイズを従来方法よりも小さくしたことにより排他的論理和の回数を削減でき、結果、誤り訂正符号化装置１の回路規模も削減することができる。
【００５４】
また、実施の形態２でも上記実施の形態１と同様に、符号語ｃのベクトルの左側を情報ビット系列ｄとし、右側をパリティビット系列ｐとした場合の誤り訂正符号化方法を説明したが、これに限定されるものではない。例えば、符号語ｃのうちの任意の部分をパリティビット系列ｐとしてもよく、そのような場合に本実施の形態２の構成を実現するには、一例として符号語ｃの要素を並び替える処理を行ってパリティビット系列ｐをベクトル右側にし、パリティ検査行列Ｈの列もそれに合わせて並び替える処理を行う方法がある。パリティ検査行列Ｈの列を並び替えてもＬＤＰＣ符号の本質的な性質は変化しないので、このような方法が可能である。
【００５５】
また、実施の形態２でも上記実施の形態１と同様に、パリティ検査行列に対して基本行列操作を行った演算結果を予め求めておき、演算結果をメモリ等の記憶部にデータとして保持させ行列掛け算部４がそのデータを使用する構成にしたり、演算結果を行列掛け算部４に組み込んで構成したりして、基本行列操作部３を省略してもよい。
【００５６】
実施の形態３．
本実施の形態３では、ＱＣ−ＬＤＰＣ符号を扱う。ＱＣ−ＬＤＰＣ符号はＬＤＰＣ符号の１種であり、パリティ検査行列が巡回置換行列のブロックで構成されているＬＤＰＣ符号である。
【００５７】
式（１５）に、ＱＣ−ＬＤＰＣ符号の一例を示す。式（１５）では、パリティ検査行列Ｈの列数ｎをｎ＝Ｎｑとし、行数をｍ＝Ｍｑとする。つまり、パリティ検査行列Ｈは、Ｘij，Ｙijを縦にＭ個、横にＮ個含む構造となっている。また、Ｋ＝Ｎ−Ｍとおく。
また、式（１５）においてｉ行ｊ列（１≦ｉ≦Ｍ、１≦ｊ≦Ｋ）の要素Ｘijと、ｉ行ｊ列（１≦ｉ≦Ｍ、１≦ｊ≦Ｍ）の要素Ｙijは、それぞれｑ×ｑの正方行列であり、巡回置換行列または零行列である。巡回置換行列は、式（１６）のような、単位行列を巡回シフトした行列である。
2014069464.tif 000015
2014069464.tif 000016
【００５８】
また、図６に、本実施の形態３に用いるＱＣ−ＬＤＰＣ符号の一例を示す。
ＱＣ−ＬＤＰＣ符号のパリティ検査行列Ｈにおいて、パリティビット系列ｐに対応するＭ行Ｍ列のブロックのうち、１列目をＺjとする。
また、パリティ検査行列Ｈの部分行列で示しているＩは、ｑ×ｑの単位行列である。また、０はｑ×ｑの零行列であり、ＸijおよびＺjは巡回置換行列または零行列である。
【００５９】
さらに、本実施の形態３では、情報ビット系列ｄを式（１７）のように表し、パリティビット系列ｐを式（１８）のように表す。式（１７）および式（１８）の表記は、上記実施の形態１，２で用いた情報ビット系列ｄおよびパリティビット系列ｐを、パリティ検査行列Ｈのブロック単位で表したものである。つまり、情報ビット系列をｑ個ごとにブロックに分けたとき、ｄb,iはｉ（１≦ｉ≦Ｋ）番目のブロックに対応するｑ個の情報データからなるベクトルである。同様に、ｐb,iは、パリティビット系列をｑ個ごとにブロックに分けたときのｉ（１≦ｉ≦Ｍ）番目のブロックに対応するｑ個のパリティビットからなるベクトルである。
【００６０】
2014069464.tif 000017
2014069464.tif 000018
【００６１】
次に、本実施の形態３におけるＬＤＰＣ符号の符号化方法を式を用いて説明する。
まず、上記実施の形態１，２と同様に、上式（３）に基づいてパリティ検査行列Ｈと情報ビット系列ｄとパリティビット系列ｐとに関する方程式を定める。その際、パリティ検査行列Ｈ、情報ビット系列ｄ、およびパリティビット系列ｐとして、式（１５）、式（１７）、および式（１８）で説明したようなブロックで分けた表記を用いると、式（３）は下式（１９）のようになる。
【００６２】
2014069464.tif 000019
【００６３】
この式（１９）をブロックごとに分けて展開すると、１行目のブロックについて式（２０）、２〜Ｍ−１行目のブロックについて式（２１）、Ｍ行目のブロックについて式（２２）が得られる。そして、式（２０）、式（２２）および式（２１）を各ｊに対して全て足すと、式（２３）が得られる。
【００６４】
2014069464.tif 000020
2014069464.tif 000021
2014069464.tif 000022
2014069464.tif 000023
【００６５】
式（２３）に含まれるパリティビットのブロックはｐb,1のみであるため、式（２３）を変形することで、式（２４）を得ることができ、ｐb,1を算出することができる。
【００６６】
2014069464.tif 000024
【００６７】
さらに、式（２１）および式（２２）を一部のｊに対して適宜加算すれば、各ｊ（２≦ｊ≦Ｍ−１）に対するｐb,jを算出可能な式（２５）が得られ、この式（２５）を変形して式（２６）を得ることができる。式（２６）の右辺のｐb,1は、上式（２４）から算出した値である。なお、ｒはΣで和を求める対象（ｊ，ｊ＋１，・・・，Ｍ）を表し、式（２６）により、ｊ番目のブロックからＭ番目のブロックに対し、Σの内部（丸括弧内）のベクトルの総和を求めることになる。
【００６８】
2014069464.tif 000025
2014069464.tif 000026
【００６９】
また、式（２２）からｐb,Mを算出可能な式（２７）が得られ、式（２７）においても、式（２６）と同様に式（２４）から算出したｐb,1を用いることでｐb,Mを算出できる。
【００７０】
2014069464.tif 000027
【００７１】
上記のようにして、パリティ検査行列ＨをもつＬＤＰＣ符号のパリティビットが算出でき、ＬＤＰＣ符号の符号化を行うことができる。
【００７２】
上記を踏まえ、本実施の形態３を説明する。
図７は、本実施の形態３に係る誤り訂正符号化装置１の構成を示すブロック図である。本実施の形態３に係る誤り訂正符号化装置１は、疎行列演算部２と、基本行列操作部３と、（第１の）行列掛け算部４と、パリティビット算出部５と、ベクトル要素加算部６と、第２の行列掛け算部７とを備える。なお、図７において図１および図４と同一または相当の部分については同一の符号を付し説明を省略する。
【００７３】
図８は、本実施の形態３に係る誤り訂正符号化装置１の動作を示すフローチャートである。
ステップＳＴ３１では、表記が異なるものの、上記実施の形態１，２のステップＳＴ１１，２１と同様に、疎行列演算部２が情報ビット系列ｄb,iとパリティ検査行列Ｈの部分行列Ｘijとの排他的論理和を演算し、Ｘijｄb,iの各ｊについてｑ次元ベクトルを得る。本ステップＳＴ３１は、上式（２０）〜（２２）の第一項の算出に対応する。Ｘijは巡回置換行列であり、疎な行列であるため、本ステップＳＴ３１の演算量は小さい。
【００７４】
ステップＳＴ３２では、ベクトル要素加算部６が、ステップＳＴ３１の算出結果であるｑ次元ベクトルを、ｒ＝１からｊまで、Ｍ−１回加算する。本ステップＳＴ３２は、上式（２３）の第一項の算出に対応する。
【００７５】
ステップＳＴ３３では、行列掛け算部４が上式（２４）に従って、別途算出しておいた、Ｚjのｊ＝１からＭまでの総和の行列の逆行列を、ステップＳＴ３２の算出結果に掛け、パリティビット系列ｐb,1を得る。ここで、Ｚjの総和の逆行列は、基本行列操作部３が予め算出しておく。この逆行列は疎ではないが、ｑ×ｑ行列であり、行列サイズは小さい。そのため、本ステップＳＴ３３の演算量は小さい。
【００７６】
ステップＳＴ３４では、第２の行列掛け算部７が、ステップＳＴ３３で得たパリティビット系列ｐb,1に対する各Ｚjの掛け算と、その掛け算結果であるベクトルの和を算出する。本ステップＳＴ３４は、上式（２５）の第二項の算出に対応する。なお、Ｚjは疎であり、演算量は小さい。
【００７７】
ステップＳＴ３５では、パリティビット算出部５が上式（２６）および上式（２７）に従って、ステップＳＴ３２の算出結果とステップＳＴ３４の算出結果とを加算し、パリティビット系列ｐb,j，ｐb,Mを算出する。本ステップＳＴ３５は２つのベクトルの足し算であるため、演算量は小さい。
【００７８】
本実施の形態３においては、疎でない行列を用いる演算を少なくすることで演算量の削減を行っている。疎でない行列は、ステップＳＴ３３のＺjのｊに対する総和の逆行列であるが、この逆行列はｑ×ｑ行列でありサイズが小さい。目安として、上記実施の形態１，２および従来方法で用いる疎でない行列サイズのｍおよびｋと比べ、ｑは一般的に１／３〜１／１００と小さい。そのため、ステップＳＴ３３の演算量は、約ｑ×ｑ／２回の排他的論理和となり、従来方法に比べて、ｑ／ｍまたはｑ／ｋの２乗オーダーで演算量を削減することができる。
【００７９】
なお、ステップＳＴ３３以外のステップで最も演算量が多くなり得るのはステップＳＴ３１であるが、ステップＳＴ３１で用いる行列Ｘは疎であり、またステップＳＴ３１は上記実施の形態１，２のステップＳＴ１１，ＳＴ２１と同じ演算である。そのため、同じパリティ検査行列であれば、本実施の形態３の符号化方法は、上記実施の形態１，２の符号化方法に比べ演算量を削減することができる。
【００８０】
以上より、実施の形態３によれば、誤り訂正符号化装置１は、パリティ検査行列のうちの情報ビット系列に対応した部分行列の１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算してベクトルを算出する疎行列演算ステップと、疎行列演算ステップで得られたベクトルの要素の一部を足し合わせるベクトル要素加算ステップと、パリティ検査行列のうちのパリティビット系列に対応する部分行列の一部を加算した行列の逆行列に、ベクトル要素加算ステップで得られたベクトルを掛けて、パリティビット系列の一部を算出する（第１の）行列掛け算ステップと、パリティ検査行列のうちのパリティビット系列に対応する部分行列の残りの部分に、（第１の）行列掛け算ステップで得られたパリティビット系列の一部を掛ける第２の行列掛け算ステップと、ベクトル要素加算ステップで得られたベクトルと第２の行列掛け算ステップで得られたベクトルを足し合わせて、パリティビット系列の残りの部分を算出するパリティビット算出ステップとを実施するように構成した。このため、ＱＣ−ＬＤＰＣ符号の符号化において、演算の多くを疎な行列を用いて行うことができ、演算量を削減することができる。また、上記実施の形態１，２と同様に、掛け算に用いる疎でない逆行列のサイズを従来方法よりも小さくすることができ、これによっても演算量を削減することができる。
【００８１】
また、実施の形態３のステップＳＴ３１〜ＳＴ３５それぞれの演算はビット同士の加算と乗算であるので、上記実施の形態１，２と同様に、疎行列演算部２、行列掛け算部４、第２の行列掛け算部７、およびパリティビット算出部５それぞれを、排他的論理和ゲートと論理積ゲートとからなる回路で構成できる。
この回路構成の場合、掛け算に用いる疎でない逆行列のサイズを従来方法よりも小さくしたことにより排他的論理和の回数を削減でき、結果、誤り訂正符号化装置１の回路規模も削減することができる。
【００８２】
なお、実施の形態３でも上記実施の形態１，２と同様に、符号語ｃのベクトルの左側を情報ビット系列ｄとし、右側をパリティビット系列ｐとした場合の誤り訂正符号化方法を説明したが、これに限定されるものではない。例えば、符号語ｃのうちの任意の部分をパリティビット系列ｐとしてもよく、そのような場合に本実施の形態３の構成を実現するには、一例として符号語ｃの要素を並び替える処理を行ってパリティビット系列ｐをベクトル右側にし、パリティ検査行列Ｈの列もそれに合わせて並び替える処理を行う方法がある。パリティ検査行列Ｈの列を並び替えてもＬＤＰＣ符号の本質的な性質は変化しないので、このような方法が可能である。
【００８３】
また、実施の形態３でも上記実施の形態１，２と同様に、パリティ検査行列に対して基本行列操作を行った演算結果を予め求めておき、演算結果をメモリ等の記憶部にデータとして保持させ行列掛け算部４がそのデータを使用する構成にしたり、演算結果を行列掛け算部４に組み込んで構成したりして、基本行列操作部３を省略してもよい。
【００８４】
実施の形態４．
図９は、この発明の実施の形態４に係る誤り訂正符号化装置１の構成を示すブロック図である。本実施の形態４に係る誤り訂正符号化装置１は、疎行列演算部２と、基本行列操作部３と、行列掛け算部４と、パリティビット算出部５と、ベクトル要素加算部６と、第２の行列掛け算部７と、巡回シフト部８，９と、逆巡回シフト部１０とを備える。なお、図９において図７と同一または相当の部分については同一の符号を付し説明を省略する。
【００８５】
本実施の形態４では、上記実施の形態３で説明したパリティビット系列ｐの算出式を、基本行列操作に基づいた他の表現で説明する。
既に説明したように、上記実施の形態３を適用するＱＣ−ＬＤＰＣ符号のパリティ検査行列Ｈの一例は、図６に示す通りである。図６のパリティ検査行列Ｈは、基本行列操作部３の行う所定の基本行列操作により、単純な構造となる。図１０はその基本行列操作を説明する図であり、矢印上側のように、パリティ検査行列Ｈについて加算（１）から加算（Ｍ−１）を順番にブロック単位で行うと、矢印下側の行列となる。この基本行列操作により、単位行列Ｉの多くを消すことができ、１行目に現れるＺrのｒ＝１からＭまでの総和を除けば、下三角行列の構造となっていることがわかる。このＺrの総和は、図８のステップＳＴ３３および上式（２４）で逆行列として用いた、Ｚjの総和のｑ×ｑ行列に対応する。
【００８６】
以上を踏まえると、パリティ検査行列Ｈは、図６の構造に限定されないことは明らかである。
そこで、本実施の形態４では、一例として図１１に示すパリティ検査行列Ｈを使用する。図１１に示すパリティ検査行列Ｈは、図６のパリティ検査行列Ｈのうち、単位行列Ｉとしていた部分の一部またはすべてを巡回置換行列Ａjで置き換えた構造である。また、Ａjの一部またはすべてを零行列にしてもよい。
【００８７】
つまり、図１０に示す加算（ｊ）（１≦ｊ≦Ｍ−１）を、基本行列操作部３が単純にブロック単位に加算するのではなく、図１１の場合、まず巡回シフト部８が、加算する２つのブロック（例えば、パリティ検査行列Ｈの一番下のＭ行目のブロックと、１つ上Ｍ−１行目のブロック）のうちの下方のブロックＸij，Ｚj，Ａjを巡回シフトし、続いて基本行列操作部３が、巡回シフトした下方のブロックを上方のブロックへ加算する。これを繰り返せば、図１０の矢印下側の行列と同様の行列が得られる。
【００８８】
この場合に得られる行列は、図１０の矢印下側の行列のうち、一部の部分行列Ｘij，Ｚjを巡回シフトした構造となる。図１０に示したＩおよび０の部分は、図１０と同じままである。
【００８９】
基本行列操作部３は、巡回シフト部８によりＸij，Ｚj，Ａjが巡回シフトされたパリティ検査行列Ｈの各行を加算（ｊ）した後、１行目に現れるＺrのｒ＝１からＭまでの総和の逆行列を算出し、この逆行列を行列掛け算部４へ出力する。
【００９０】
上述のようにパリティ検査行列Ｈの部分行列を巡回シフトし基本行列操作を行うことにより、図１０の矢印下側の行列と同様の行列を得ることができるが、このときの巡回シフトに対応して、情報ビット系列ｄとパリティビット系列ｐも巡回シフトさせる必要がある。
【００９１】
具体的には、巡回シフト部９が、図８のステップＳＴ３１を実施する前に、情報ビット系列ｄを部分ベクトルｄb,i単位で巡回シフトする。他方の逆巡回シフト部１０は、図８のステップＳＴ３５を実施した後に、パリティビット系列ｐを部分ベクトルｐb,i単位で巡回シフトする。巡回シフト部９および逆巡回シフト部１０が行う巡回シフトは、巡回シフト部８が行うブロックＸij，Ｚj，Ａjの巡回シフトに対応しており、巡回シフト部８がパリティ検査行列Ｈの各Ｘijに施す巡回シフトと同様の巡回シフトを、巡回シフト部９が情報ビット系列ｄb,iに施してシフトさせる。また、巡回シフト部８がパリティ検査行列Ｈの各Ｚj，Ａjに施す巡回シフトとは逆のシフトを、逆巡回シフト部１０がパリティビット系列ｐb,iに施して元に戻す。
【００９２】
以上の処理により、本実施の形態４の誤り訂正符号化装置１においても、図８と同様の符号化方法を実施可能である。
【００９３】
以上より、実施の形態４によれば、誤り訂正符号化装置１は、パリティ検査行列として、情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列目以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に単位行列を含む構成の行列のうち、巡回シフト部８が部分行列Ｘij，Ｚjおよび巡回置換行列Ａjの一部を巡回シフトした構成の行列を使用するようにした。このため、図１１の構造のパリティ検査行列Ｈに対して、一部の部分行列を巡回シフトすることで、図８の符号化方法によりＬＤＰＣ符号の符号化を行うことができる。一部の部分行列を巡回シフトしても、行列に含まれる１の数は変わらないため、上記実施の形態３の図６に示した構造のパリティ検査行列Ｈと同様の演算量となる。従って、従来方法および上記実施の形態１，２の符号化方法に比べ演算量を削減することができる。
【００９４】
さらに、本実施の形態４に適用可能なパリティ検査行列Ｈは、図１１に限定されない。
例えば、図１２に示すように、図１１のパリティ検査行列Ｈのうち、単位行列Ｉとしていた部分の一部またはすべてを巡回置換行列Ｂjとしてもよい。また、Ｂjの一部またはすべてを零行列にしてもよい。パリティ検査行列Ｈは、行の順番を入れ替えても、パリティ検査行列およびＬＤＰＣ符号の本質的構造は変わらないからである。当然ながら、行をブロック単位で巡回シフトさせても本質的構造は変わらない。なお、図１２に示すパリティ検査行列Ｈの行において、ブロック単位で各巡回置換行列Ｂjを単位行列Ｉにした場合、図１１と同様の構造のパリティ検査行列Ｈとなる。
【００９５】
図１２の場合にも、まず巡回シフト部８が、加算する２つのブロックのうちの下方のブロックＸij，Ｚj，Ａj，Ｂjを巡回シフトし、続いて基本行列操作部３が、巡回シフトした下方のブロックを上方のブロックへ加算する。これを繰り返せば、図１０の矢印下側の行列と同様の行列が得られる。
【００９６】
この場合に得られる行列は、図１０の矢印下側の行列のうち、一部の部分行列Ｘij，Ｚj、およびＡjに置き換えたＩを巡回シフトした構造となる。基本行列操作部３は、巡回シフト部８によりＸij，Ｚj，Ａj，Ｂjが巡回シフトされたパリティ検査行列Ｈの各行を加算（ｊ）した後、１行目に現れるＺｒのｒ＝１からＭまでの総和の逆行列を算出し、この行列を行列掛け算部４へ出力する。
【００９７】
また、この場合にも、巡回シフト部９が情報ビット系列ｄを部分ベクトルｄb,i単位で巡回シフト部８と同様に巡回シフトさせると共に、逆巡回シフト部１０がパリティビット系列ｐを部分ベクトルｐb,i単位で巡回シフト部８とは逆に巡回シフトさせる。
以上の処理により、図８と同様の符号化方法を実施可能である。
【００９８】
以上より、実施の形態４によれば、誤り訂正符号化装置１は、パリティ検査行列として、情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に巡回置換行列Ｂjを含む構成の行列のうち、巡回シフト部８が部分行列Ｘij，Ｚjおよび巡回置換行列Ａj，Ｂjの一部を巡回シフトした構成の行列を使用するようにした。このため、図１２の構造のパリティ検査行列Ｈに対して、一部の部分行列を巡回シフトすることで、図８の符号化方法によりＬＤＰＣ符号の符号化を行うことができる。一部の部分行列を巡回シフトしても、行列に含まれる１の数は変わらないため、上記実施の形態３の図６に示した構造のパリティ検査行列Ｈと同様の演算量となる。従って、従来方法および上記実施の形態１，２の符号化方法に比べ演算量を削減することができる。
【００９９】
また、実施の形態４でも上記実施の形態３と同様に、図８のステップＳＴ３１〜ＳＴ３５それぞれの演算はビット同士の加算と乗算であるので、上記実施の形態３と同様に、疎行列演算部２、行列掛け算部４、第２の行列掛け算部７、およびパリティビット算出部５それぞれを、排他的論理和ゲートと論理積ゲートとからなる回路で構成できる。
この回路構成の場合、掛け算に用いる疎でない逆行列のサイズを従来方法よりも小さくしたことにより排他的論理和の回数を削減でき、結果、誤り訂正符号化装置１の回路規模も削減することができる。
【０１００】
なお、実施の形態４でも上記実施の形態１〜３と同様に、符号語ｃのベクトルの左側を情報ビット系列ｄとし、右側をパリティビット系列ｐとした場合の誤り訂正符号化方法を説明したが、これに限定されるものではない。例えば、符号語ｃのうちの任意の部分をパリティビット系列ｐとしてもよく、そのような場合に本実施の形態４の構成を実現するには、一例として符号語ｃの要素をブロック単位に並び替える処理を行ってパリティビット系列ｐをベクトル右側にし、パリティ検査行列Ｈのブロック列もそれに合わせて並び替える処理を行う方法がある。並び替え後のパリティ検査行列Ｈが図１１、図１２に例示した構造になるなら、実施の形態４は実施可能である。つまり、ブロック単位に行および列を並び替えることにより、上記で説明した実施の形態４を実施可能な構造とできるパリティ検査行列Ｈであるなら、実施の形態４は実施可能であると言える。
【０１０１】
また、実施の形態４でも上記実施の形態１〜３と同様に、パリティ検査行列に対して基本行列操作を行った演算結果を予め求めておき、演算結果をメモリ等の記憶部にデータとして保持させ行列掛け算部４がそのデータを使用する構成にしたり、演算結果を行列掛け算部４に組み込んで構成したりして、基本行列操作部３を省略してもよい。
【０１０２】
また、実施の形態４において、巡回シフトはデータの順番を入れ替える処理であるため、予め巡回シフトの規則（巡回シフト部８の出力結果）が判明していれば、パリティ検査行列に対して巡回シフトおよび基本行列操作を行った演算結果を予め求めておくことが可能であり、その場合には巡回シフト部８および基本行列操作部３を省略可能である。
さらに、予め巡回シフトの規則が判明していれば、巡回シフト部９および逆巡回シフト部１０を構成する演算器などを必要とせずに実装できる場合がある。特に回路の場合、データの順番は配線の繋ぎ方で決まるため、演算器を必要とせずに実装可能であり、回路規模を増大させることなく巡回シフト部９および逆巡回シフト部１０の機能を実現できる。
【０１０３】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【産業上の利用可能性】
【０１０４】
以上のように、この発明に係る誤り訂正符号化装置は、情報データをＬＤＰＣ符号に準じて符号化する、通信システムの送信機などに用いるのに適している。
【符号の説明】
【０１０５】
１  誤り訂正符号化装置、２  疎行列演算部、３  基本行列操作部、４  （第１の）行列掛け算部、５  パリティビット算出部、６  ベクトル要素加算部、７  第２の行列掛け算部、８，９  巡回シフト部、  １０  逆巡回シフト部。
【図１】
2014069464.tif 000031
【図２】
2014069464.tif 000032
【図３】
2014069464.tif 000033
【図４】
2014069464.tif 000034
【図５】
2014069464.tif 000035
【図６】
2014069464.tif 000036
【図７】
2014069464.tif 000037
【図８】
2014069464.tif 000038
【図９】
2014069464.tif 000039
【図１０】
2014069464.tif 000040
【図１１】
2014069464.tif 000041
【図１２】
2014069464.tif 000042
【図１３】
2014069464.tif 000043
【図１４】
2014069464.tif 000044
【図１５】
2014069464.tif 000045
【手続補正書】
【提出日】平成26年8月29日(2014.8.29)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】削除
【補正の内容】
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
この発明に係る誤り訂正符号化方法は、パリティ検査行列のうちの情報ビット系列に対応する複数の部分行列のそれぞれの１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算して複数のベクトルを算出する疎行列演算ステップと、疎行列演算ステップで得られた複数のベクトルを足し合わせたベクトルを得るベクトル要素加算ステップと、パリティ検査行列のうちのパリティビット系列に対応する複数の部分行列の一部を加算した行列の逆行列と、ベクトル要素加算ステップで得られる足し合わせたベクトルとを掛けて、パリティビット系列の一部を算出する第１の行列掛け算ステップと、第１の行列掛け算ステップで加算の対象とされた一部の部分行列と、第１の行列掛け算ステップで得られたパリティビット系列の一部とを掛けて掛け算結果のベクトルを得る第２の行列掛け算ステップと、疎行列演算ステップで得られた複数のベクトルと第２の行列掛け算ステップで得られた掛け算結果のベクトルとに基づいて、パリティビット系列の残りの部分を算出するパリティビット算出ステップとを備えるものである。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】削除
【補正の内容】
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
この発明に係る誤り訂正符号化装置は、パリティ検査行列のうちの情報ビット系列に対応する複数の部分行列のそれぞれの１の位置に基づいて、当該部分行列と情報ビット系列の排他的論理和を演算して複数のベクトルを算出する疎行列演算部と、疎行列演算部で得られた複数のベクトルを足し合わせたベクトルを得るベクトル要素加算部と、パリティ検査行列のうちのパリティビット系列に対応する複数の部分行列の一部を加算した行列の逆行列と、ベクトル要素加算部で得られる足し合わせたベクトルとを掛けて、パリティビット系列の一部を算出する第１の行列掛け算部と、第１の行列掛け算部で加算の対象とされた一部の部分行列と、第１の行列掛け算部で得られたパリティビット系列の一部とを掛けて掛け算結果のベクトルを得る第２の行列掛け算部と、疎行列演算部で得られた複数のベクトルと第２の行列掛け算部で得られた掛け算結果のベクトルとに基づいて、パリティビット系列の残りの部分を算出するパリティビット算出部とを備えるものである。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】削除
【補正の内容】
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】削除
【補正の内容】
【手続補正７】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＱＣ（Ｑｕａｓｉ−Ｃｙｃｌｉｃ）−ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号用の疎なパリティ検査行列を用いて、情報ビット系列からパリティビット系列を算出し符号化する誤り訂正符号化方法であって、
前記パリティ検査行列のうちの前記情報ビット系列に対応する複数の部分行列のそれぞれの１の位置に基づいて、当該部分行列と前記情報ビット系列の排他的論理和を演算して複数のベクトルを算出する疎行列演算ステップと、
前記疎行列演算ステップで得られた前記複数のベクトルを足し合わせたベクトルを得るベクトル要素加算ステップと、
前記パリティ検査行列のうちの前記パリティビット系列に対応する複数の部分行列の一部を加算した行列の逆行列と、前記ベクトル要素加算ステップで得られる前記足し合わせたベクトルとを掛けて、前記パリティビット系列の一部を算出する第１の行列掛け算ステップと、
前記第１の行列掛け算ステップで加算の対象とされた前記一部の部分行列と、前記第１の行列掛け算ステップで得られた前記パリティビット系列の一部とを掛けて掛け算結果のベクトルを得る第２の行列掛け算ステップと、
前記疎行列演算ステップで得られた前記複数のベクトルと前記第２の行列掛け算ステップで得られた前記掛け算結果のベクトルとに基づいて、前記パリティビット系列の残りの部分を算出するパリティビット算出ステップとを備えることを特徴とする誤り訂正符号化方法。
【請求項２】
ＱＣ（Ｑｕａｓｉ−Ｃｙｃｌｉｃ）−ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号用の疎なパリティ検査行列を用いて、情報ビット系列からパリティビット系列を算出し符号化する誤り訂正符号化方法であって、
前記情報ビット系列ｄb,iは、各要素をｑ個毎にブロックに分けたとき、ｉ（１≦ｉ≦Ｋ）番目のブロックに対応するｑ個の要素からなるベクトルであり、
前記パリティビット系列ｐb,iは、各要素をｑ個毎にブロックに分けたとき、ｉ（１≦ｉ≦Ｍ）番目のブロックに対応するｑ個の要素からなるベクトルであり、
Ｍ行Ｎ列の前記パリティ検査行列は、前記情報ビット系列に対応するＭ行Ｋ列（Ｋ＝Ｎ−Ｍ）の部分行列Ｘijと、前記パリティビット系列に対応するＭ行Ｍ列のうちの１列目の部分行列Ｚjと、対角成分２行分に単位行列を含む部分行列とからなり、
下記に示す３つの式に従って、前記パリティビット系列の各要素を算出することを特徴とする誤り訂正符号化方法。
2014069464.tif 000046
2014069464.tif 000047
2014069464.tif 000048
ここで、Ｔは転置行列である。
【請求項３】
前記パリティ検査行列は、前記情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、前記パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列目以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に単位行列を含む構成であり、前記部分行列Ｘij，Ｚjおよび前記巡回置換行列Ａjの一部が巡回シフトされることを特徴とする請求項１記載の誤り訂正符号化方法。
【請求項４】
前記パリティ検査行列は、前記情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、前記パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列目以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に単位行列を含む構成であり、前記部分行列Ｘij，Ｚjおよび前記巡回置換行列Ａjの一部が巡回シフトされることを特徴とする請求項２記載の誤り訂正符号化方法。
【請求項５】
前記パリティ検査行列は、前記情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、前記パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に巡回置換行列Ｂjを含む構成であり、前記部分行列Ｘij，Ｚjおよび前記巡回置換行列Ａj，Ｂjの一部が巡回シフトされることを特徴とする請求項１記載の誤り訂正符号化方法。
【請求項６】
前記パリティ検査行列は、前記情報ビット系列に対応した部分行列Ｘij（ｉは行、ｊは列）と、前記パリティビット系列に対応した部分行列のうちの１列目の部分行列Ｚjと、２列以降の部分行列とからなり、当該２列目以降の部分行列が、対角成分に巡回置換行列Ａjを含むと共に当該巡回置換行列Ａjそれぞれの１つ下に巡回置換行列Ｂjを含む構成であり、前記部分行列Ｘij，Ｚjおよび前記巡回置換行列Ａj，Ｂjの一部が巡回シフトされることを特徴とする請求項２記載の誤り訂正符号化方法。
【請求項７】
ＱＣ（Ｑｕａｓｉ−Ｃｙｃｌｉｃ）−ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号用の疎なパリティ検査行列を用いて、情報ビット系列からパリティビット系列を算出し符号化する誤り訂正符号化装置であって、
前記パリティ検査行列のうちの前記情報ビット系列に対応する複数の部分行列のそれぞれの１の位置に基づいて、当該部分行列と前記情報ビット系列の排他的論理和を演算して複数のベクトルを算出する疎行列演算部と、
前記疎行列演算部で得られた前記複数のベクトルを足し合わせたベクトルを得るベクトル要素加算部と、
前記パリティ検査行列のうちの前記パリティビット系列に対応する複数の部分行列の一部を加算した行列の逆行列と、前記ベクトル要素加算部で得られる前記足し合わせたベクトルとを掛けて、前記パリティビット系列の一部を算出する第１の行列掛け算部と、
前記第１の行列掛け算部で加算の対象とされた前記一部の部分行列と、前記第１の行列掛け算部で得られた前記パリティビット系列の一部とを掛けて掛け算結果のベクトルを得る第２の行列掛け算部と、
前記疎行列演算部で得られた前記複数のベクトルと前記第２の行列掛け算部で得られた前記掛け算結果のベクトルとに基づいて、前記パリティビット系列の残りの部分を算出するパリティビット算出部とを備えることを特徴とする誤り訂正符号化装置。
【国際調査報告】
2014069464.tif 000049
2014069464.tif 000050
2014069464.tif 000051
2014069464.tif 000052