(57)【要約】【課題】冗長符号化方式における符号化の組合せを早急に決定することを課題とする。【解決手段】冗長符号化装置１は、各種のコンテンツからなる複数の符号化前データを受け入れ、複数のメッセージノードと複数のパリティノードとからなるノードの集合について符号化の組合せを生成し、その符号化の組合せに基づいてメッセージノードを符号化してパリティノードのデータを生成するものである。そして、符号化の組合せを生成する処理に際しては、予め保持する固定の平均多重数および外部から入力された符号化レート（ノード構成）に基づいて平均メッセージ度数を算出し、この平均メッセージ度数を用いて当該平均メッセージ度数に対応するように符号化の組合せを生成する。【選択図】        図２
2006050482.tif 000002
【特許請求の範囲】
【請求項１】
複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する符号化処理装置であって、
前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数に基づいて、前記符号化前データそれぞれの符号化先となるパリティノードの個数平均を示す平均メッセージ度数を算出するメッセージ度数算出手段と、
前記メッセージ度数算出手段によって算出された平均メッセージ度数を用いて、当該平均メッセージ度数に対応するように前記符号化の組合せを生成する組合せ生成手段と、
を備えたことを特徴とする符号化処理装置。
【請求項２】
前記メッセージ度数算出手段は、予め保持する固定の平均多重数を用いて前記平均メッセージ度数を算出することを特徴とする請求項１に記載の符号化処理装置。
【請求項３】
前記組合せ生成手段は、各符号化前データの符号化先となるパリティノードを前記平均メッセージ度数に合わせて無作為に選択して、前記符号化の組合せを生成することを特徴とする請求項１または２に記載の符号化処理装置。
【請求項４】
前記組合せ生成手段は、前記符号化の組合せを生成した後に、前記ノードの構成変更に伴って前記平均メッセージ度数が新たに算出された場合には、既に生成されている前記符号化の組合せに対して前記ノードの構成変更を反映し、当該反映後の組合せから求まる平均メッセージ度数と前記新たに算出された平均メッセージ度数との差分が所定値以内であれば、既に生成されている前記符号化の組合せを当該反映後の組合せに更新することを特徴とする請求項１、２または３に記載の符号化処理装置。
【請求項５】
前記組合せ生成手段は、前記反映後の組合せから求まる平均メッセージ度数と前記新たに算出された平均メッセージ度数との差分が所定値以内でない場合には、当該差分が大きな符号化前データから順番に当該符号化前データの符号化先となるパリティノードを取捨選択して新たな組合せを順次生成し、当該新たな組合せから求まる平均メッセージ度数と前記新たに算出された平均メッセージ度数との差分が所定値以内になれば、既に生成されている前記符号化の組合せを当該新たな組合せに更新することを特徴とする請求項４に記載の符号化処理装置。
【請求項６】
複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する符号化処理方法であって、
前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数に基づいて、前記符号化前データそれぞれの符号化先となるパリティノードの個数平均を示す平均メッセージ度数を算出するメッセージ度数算出工程と、
前記メッセージ度数算出工程によって算出された平均メッセージ度数を用いて、当該平均メッセージ度数に対応するように前記符号化の組合せを生成する組合せ生成工程と、
を含んだことを特徴とする符号化処理方法。
【請求項７】
前記メッセージ度数算出工程は、予め保持する固定の平均多重数を用いて前記平均メッセージ度数を算出することを特徴とする請求項６に記載の符号化処理方法。
【請求項８】
前記組合せ生成工程は、各符号化前データの符号化先となるパリティノードを前記平均メッセージ度数に合わせて無作為に選択して、前記符号化の組合せを生成することを特徴とする請求項６または７に記載の符号化処理方法。
【請求項９】
複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する方法をコンピュータに実行させる符号化処理プログラムであって、
前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数に基づいて、前記符号化前データそれぞれの符号化先となるパリティノードの個数平均を示す平均メッセージ度数を算出するメッセージ度数算出手順と、
前記メッセージ度数算出手順によって算出された平均メッセージ度数を用いて、当該平均メッセージ度数に対応するように前記符号化の組合せを生成する組合せ生成手順と、
をコンピュータに実行させることを特徴とする符号化処理プログラム。
【請求項１０】
前記メッセージ度数算出手順は、予め保持する固定の平均多重数を用いて前記平均メッセージ度数を算出することを特徴とする請求項９に記載の符号化処理プログラム。
【請求項１１】
前記組合せ生成手順は、各符号化前データの符号化先となるパリティノードを前記平均メッセージ度数に合わせて無作為に選択して、前記符号化の組合せを生成することを特徴とする請求項９または１０に記載の符号化処理プログラム。
【請求項１２】
複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する符号化処理装置であって、
前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数を用いて、当該平均多重数に対応するように前記符号化の組合せを生成する組合せ生成手段を備えたことを特徴とする符号化処理装置。
【請求項１３】
複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する符号化処理方法であって、
前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数を用いて、当該平均多重数に対応するように前記符号化の組合せを生成する組合せ生成工程を含んだことを特徴とする符号化処理方法。
【請求項１４】
複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する方法をコンピュータに実行させる符号化処理プログラムであって、
前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数を用いて、当該平均多重数に対応するように前記符号化の組合せを生成する組合せ生成手順をコンピュータに実行させることを特徴とする符号化処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について符号化の組合せを生成する符号化処理装置、符号化処理方法および符号化処理プログラムに関する。
【背景技術】
【０００２】
近年、情報化技術やネットワーク通信技術の発展に伴い、処理される情報量も大幅に増加し、記憶装置や通信路におけるデータの信頼性を保つことが要求されており、物理装置の信頼性特性に依存しないかたちでデータの信頼性を高める手法として、元のデータに冗長な情報を付加して検証・復号する冗長符号化方式が従来から知られている。
【０００３】
そして、かかる冗長符号化方式としては、例えば非特許文献１に開示されるような低密度パリティ検査符号（Low-Density Parity-Check Codes、以下「ＬＤＰＣ符号」と呼ぶ。）がある。このＬＤＰＣ符号では、複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化（ＸＯＲ演算）して生成される複数のパリティノードとを符号化処理で生成する（図１参照）。
【０００４】
ここで、冗長符号化方式の符号性能（欠損したデータを他のデータから復元できる性能）は、符号化の組合せ（図１に示す「矢印」のような、各パリティノードをどの符号化前データを組み合わせて生成するかを示す対応関係）によって大きく異なるものである。このため、符号化処理に際して如何なる対応関係を用いるかが重要になるが、例えば特許文献１（特開２００３−１１５７６８号公報）にも開示されているように、符号化レート（ノード構成）に応じてパリティ検査行列を定義し、それを基にして対応関係を定める手法が一般的である。
【０００５】
これを図１に置き換えて簡単に説明すれば、適用対象の符号化レート（ノード構成）において、一通りの平均メッセージ度数（各符号化前データの符号化先となるパリティノードの個数平均）を用いて符号性能を試験した後に、適切な符号性能を発揮した平均メッセージ度数を当該ノード構成における適切な平均メッセージ度数として決定し、かかる平均メッセージ度数を基にして対応関係を定めるという手法である。
【０００６】
【特許文献１】特開２００３−１１５７６８号公報
【非特許文献１】R.G.Gallager著「Low-Density Parity-Check Codes」Cambridge,MA:MIT Press、１９６３
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、上記した従来の技術は、新たな符号化レート（ノード構成）について符号化の組合せを定めようとする場合に、適切な符号性能を発揮する平均メッセージ度数を改めて求めなければならないので、予め平均メッセージ度数が定められている場合に比較して、符号化の組合せを決定する処理の負担が大きいだけでなく、処理時間が長くなるという問題がある。特に、符号化の組合せを決定する処理時間が長くなったのでは、ノード構成の変更に早急に追従することができず、ノード構成の変更を円滑に行うことができないという問題もある。
【０００８】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、冗長符号化方式における符号化の組合せを早急に決定することが可能な符号化処理装置、符号化処理方法および符号化処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、請求項１に係る発明は、複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する符号化処理装置であって、前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数に基づいて、前記符号化前データそれぞれの符号化先となるパリティノードの個数平均を示す平均メッセージ度数を算出するメッセージ度数算出手段と、前記メッセージ度数算出手段によって算出された平均メッセージ度数を用いて、当該平均メッセージ度数に対応するように前記符号化の組合せを生成する組合せ生成手段と、を備えたことを特徴とする。
【００１０】
また、請求項２に係る発明は、上記の発明において、前記メッセージ度数算出手段は、予め保持する固定の平均多重数を用いて前記平均メッセージ度数を算出することを特徴とする。
【００１１】
また、請求項３に係る発明は、上記の発明において、前記組合せ生成手段は、各符号化前データの符号化先となるパリティノードを前記平均メッセージ度数に合わせて無作為に選択して、前記符号化の組合せを生成することを特徴とする。
【００１２】
また、請求項４に係る発明は、上記の発明において、前記組合せ生成手段は、前記符号化の組合せを生成した後に、前記ノードの構成変更に伴って前記平均メッセージ度数が新たに算出された場合には、既に生成されている前記符号化の組合せに対して前記ノードの構成変更を反映し、当該反映後の組合せから求まる平均メッセージ度数と前記新たに算出された平均メッセージ度数との差分が所定値以内であれば、既に生成されている前記符号化の組合せを当該反映後の組合せに更新することを特徴とする。
【００１３】
また、請求項５に係る発明は、上記の発明において、前記組合せ生成手段は、前記反映後の組合せから求まる平均メッセージ度数と前記新たに算出された平均メッセージ度数との差分が所定値以内でない場合には、当該差分が大きな符号化前データから順番に当該符号化前データの符号化先となるパリティノードを取捨選択して新たな組合せを順次生成し、当該新たな組合せから求まる平均メッセージ度数と前記新たに算出された平均メッセージ度数との差分が所定値以内になれば、既に生成されている前記符号化の組合せを当該新たな組合せに更新することを特徴とする。
【００１４】
また、請求項６に係る発明は、複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する符号化処理方法であって、前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数に基づいて、前記符号化前データそれぞれの符号化先となるパリティノードの個数平均を示す平均メッセージ度数を算出するメッセージ度数算出工程と、前記メッセージ度数算出工程によって算出された平均メッセージ度数を用いて、当該平均メッセージ度数に対応するように前記符号化の組合せを生成する組合せ生成工程と、を含んだことを特徴とする。
【００１５】
また、請求項７に係る発明は、上記の発明において、前記メッセージ度数算出工程は、予め保持する固定の平均多重数を用いて前記平均メッセージ度数を算出することを特徴とする。
【００１６】
また、請求項８に係る発明は、上記の発明において、前記組合せ生成工程は、各符号化前データの符号化先となるパリティノードを前記平均メッセージ度数に合わせて無作為に選択して、前記符号化の組合せを生成することを特徴とする。
【００１７】
また、請求項９に係る発明は、複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する方法をコンピュータに実行させる符号化処理プログラムであって、前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数に基づいて、前記符号化前データそれぞれの符号化先となるパリティノードの個数平均を示す平均メッセージ度数を算出するメッセージ度数算出手順と、前記メッセージ度数算出手順によって算出された平均メッセージ度数を用いて、当該平均メッセージ度数に対応するように前記符号化の組合せを生成する組合せ生成手順と、をコンピュータに実行させることを特徴とする。
【００１８】
また、請求項１０に係る発明は、上記の発明において、前記メッセージ度数算出手順は、予め保持する固定の平均多重数を用いて前記平均メッセージ度数を算出することを特徴とする。
【００１９】
また、請求項１１に係る発明は、上記の発明において、前記組合せ生成手順は、各符号化前データの符号化先となるパリティノードを前記平均メッセージ度数に合わせて無作為に選択して、前記符号化の組合せを生成することを特徴とする。
【００２０】
また、請求項１２に係る発明は、複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する符号化処理装置であって、前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数を用いて、当該平均多重数に対応するように前記符号化の組合せを生成する組合せ生成手段を備えたことを特徴とする。
【００２１】
また、請求項１３に係る発明は、複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する符号化処理方法であって、前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数を用いて、当該平均多重数に対応するように前記符号化の組合せを生成する組合せ生成工程を含んだことを特徴とする。
【００２２】
また、請求項１４に係る発明は、複数の符号化前データをそれぞれ割り当てて生成される複数のメッセージノードと当該複数の符号化前データを組み合わせて符号化して生成される複数のパリティノードとからなるノードの集合について前記符号化の組合せを生成する方法をコンピュータに実行させる符号化処理プログラムであって、前記符号化前データと前記ノードとの個数比を示す符号化レートおよび前記ノードそれぞれの生成元となる符号化前データの個数平均を示す平均多重数を用いて、当該平均多重数に対応するように前記符号化の組合せを生成する組合せ生成手順をコンピュータに実行させることを特徴とする。
【発明の効果】
【００２３】
請求項１、６または９の発明によれば、新たな符号化レート（ノード構成）について符号化の組合せを定めようとする場合に、符号化レートおよび平均多重数から適切な平均メッセージ度数を瞬時に算出するので、符号性能の試験を行って適切な平均メッセージ度数を決定する手法に比較して、処理負担が軽くなるとともに処理時間も短くなり、冗長符号化方式における符号化の組合せを早急に決定することが可能になる。さらに、符号化の組合せを決定する処理時間が短くなるので、ノード構成の変更に早急に追従することができ、ノード構成の変更を円滑に行うことが可能になる。
【００２４】
また、請求項２、７または１０の発明によれば、予め保持する固定の平均多重数を用いて平均メッセージ度数を算出するので、適切でない平均多重数が算出に用いられるおそれを除去し、適切な平均メッセージ度数を確実に算出することが可能になる。
【００２５】
また、請求項３、８または１１の発明によれば、パリティノードを平均メッセージ度数に合わせて無作為に選択することで符号化の組合せを生成するので、パリティノードの選択に係る処理が重くなることもなく、符号化の組合せを一層早急に決定することが可能になる。
【００２６】
また、請求項４の発明によれば、ノード構成に変更が生じた場合に、既に生成されている符号化の組合せに対してノード構成の変更を反映し、反映後の組合せから求まる平均メッセージ度数が適正なものであれば、かかる反映後の組合せを採用するので、符号化の組合せを新たに生成し直す手法に比較して、処理負担が軽くなるとともに処理時間も短くなり、ノード構成の変更後における符号化の組合せを早急に決定することが可能になる。これによって、ノード構成の変更に一層早急に追従することができ、ノード構成の変更を一層円滑に行うことが可能になる。
【００２７】
また、請求項５の発明によれば、反映後の組合せから求まる平均メッセージ度数が適正なものでない場合でも、差分が大きな符号化前データから順番にパリティノードを取捨選択して新たな組合せを順次生成し、平均メッセージ度数が適正なものになったところで新たな組合せを採用するので、符号化の組合せを新たに生成し直す手法に比較して、処理負担が軽くなるとともに処理時間も短くなり、ノード構成に変更後における符号化の組合せを早急に決定することが可能になる。これによって、ノード構成の変更に一層早急に追従することができ、ノード構成の変更を一層円滑に行うことが可能になる。
【００２８】
また、請求項１２、１３または１４の発明によれば、新たな符号化レート（ノード構成）について符号化の組合せを定めようとする場合に、符号化レートおよび平均多重数から符号化の組合せを決定するので、符号性能の試験を行って適切な平均メッセージ度数を決定する手法に比較して、処理負担が軽くなるとともに処理時間も短くなり、冗長符号化方式における符号化の組合せを早急に決定することが可能になる。さらに、符号化の組合せを決定する処理時間が短くなるので、ノード構成の変更に早急に追従することができ、ノード構成の変更を円滑に行うことが可能になる。
【発明を実施するための最良の形態】
【００２９】
以下に添付図面を参照して、この発明に係る符号化処理装置、符号化処理方法および符号化処理プログラムの実施例を詳細に説明する。なお、以下では、本実施例で用いる主要な用語、本実施例に係る符号化処理装置の概要および特徴、符号化処理装置の構成および処理の流れを順に説明し、最後に本実施例に対する種々の変形例を説明する。
【実施例】
【００３０】
［１：用語の説明］
まず最初に、図１を用いて、本実施例で用いる主要な用語を説明する。本実施例で用いる「冗長符号化（特許請求の範囲に記載の「符号化」に対応する。）」とは、元のデータに冗長な情報を付加して検証および復号を可能にする符号化方式のことであり、具体的には、図１に例示するように、複数の符号化前データをそれぞれ割り当てて生成される複数の「メッセージノード」と当該複数の符号化前データを組み合わせて符号化して生成される複数の「パリティノード」とを生成する。
【００３１】
また、本実施例で用いる「メッセージノード」とは、上記のように、複数の符号化前データ（図１に例示するデータＡ〜Ｍ）をそれぞれ割り当てて生成されるノード（図１に例示するメッセージノードＭ１〜Ｍｍ）のことである。また、本実施例で用いる「パリティノード」とは、上記のように、複数の符号化前データを組み合わせて符号化（例えばＸＯＲ演算）して生成されるノード（図１に例示するパリティノードＰ１〜Ｐｐ）のことである。なお、本実施例では、両者を特に区別しない場合には「ノード」と総称する。
【００３２】
また、本実施例に係る冗長符号化では、あるノードが欠損しても欠損したノードを他のノードから復元できるようにしているが、本実施例で用いる「符号性能」とは、所定確率で複数のノードが欠損したと仮定した状況から欠損したノードを復元する性能のことをいう。そして、本実施例では、より多くのノードが欠損している状況で同等の確率でノードを復元できること、また、同程度のノードが欠損している状況でより高い確率でノードを復元できることを「符号性能が高い」という。
【００３３】
また、本実施例で用いる「多重数」とは、ノードの生成元となる符号化前データの個数のことであり、例えば、図１に例示するように、メッセージノードＭ１〜Ｍｍの多重数は「１」、パリティノードＰ１の多重数は「３」、パリティノードＰ２の多重数は「２」である。そして、本実施例で用いる「平均多重数」とは、各ノードの生成元となる符号化前データの個数平均、つまり各ノードの多重数に係る平均のことである。
【００３４】
また、本実施例で用いる「メッセージ度数」とは、符号化前データの符号先となるパリティノードの個数のことであり、例えば、図１に例示するように、データＡのメッセージ度数は「３」、データＢのメッセージ度数は「２」である。そして、本実施例で用いる「平均メッセージ度数」とは、符号化前データそれぞれの符号化先となるパリティノードの個数平均、つまり各符号化前データのメッセージ度数に係る平均のことである。
【００３５】
また、本実施例で用いる「複製数」とは、符号化前データの複製先となるノードの個数、つまりメッセージ度数に一つのメッセージノード分の「１」を加えた個数のことであり、例えば、図１に例示するように、データＡの複製数は「４」、データＢの複製数は「３」である。そして、本実施例で用いる「平均複製数」とは、各符号化前データの複製数に係る平均のことである。
【００３６】
また、本実施例で用いる「符号化レート」とは、符号化前データとノード（メッセージノードおよびパリティノード）との個数比のことであり、具体的には、図１に示すように、メッセージノードの個数「Ｍ」を当該メッセージノードの個数およびパリティノードの個数「Ｐ」の合計個数「Ｍ＋Ｐ」で除算した値であり、これは上記した「平均多重数」を「平均複製数」で除算した値と一致する。なお、本実施例では、メッセージノードの個数「Ｍ」およびパリティノードの個数「Ｐ」の組合せを特に「ノード構成」という。
【００３７】
また、本実施例で用いる「対応関係（特許請求の範囲に記載の「組合せ」に対応する。）」とは、複数の符号化前データを符号化して複数のパリティノードを生成する場合における符号化の組み合わせのことであり、具体的には、図１において、各符号化前データと各ノードとを繋げる矢印によって表現される対応関係がこれに該当する。
【００３８】
［２：符号化処理装置の概要および特徴］
次に、本実施例に係る冗長符号化装置（符号化処理装置）の概要および特徴を説明する。図２は、本実施例に係る冗長符号化装置の構成を示すブロック図である。
【００３９】
同図に示す冗長符号化装置１の概要は、各種のコンテンツからなる複数の符号化前データを受け入れ、複数のメッセージノードと複数のパリティノードとからなるノードの集合について符号化の組合せ（図１参照）を生成し、その符号化の組合せに基づいてメッセージノードを符号化してパリティノードのデータを生成するというものである。そして、この冗長符号化装置１は、符号化の組合せ（メッセージノードとパリティノードとの対応関係）を生成する処理に特徴があり、冗長符号化方式における符号化の組合せを早急に決定できるようにしている。
【００４０】
これについて簡単に説明すると、冗長符号化装置１では、予め保持する固定の平均多重数および外部から入力された符号化レート（ノード構成）に基づいて、図１に例示する符号化レートの式から平均メッセージ度数を算出し、この平均メッセージ度数を用いて当該平均メッセージ度数に対応するように符号化の組合せを生成する。そして、上記で保持する平均多重数は、入力された符号化レートに応じて適切な平均メッセージ度数（符号性能を高くする平均メッセージ度数）を算出するための値（具体的には「４」）が設定されている。
【００４１】
このように、冗長符号化装置１では、新たな符号化レート（ノード構成）について符号化の組合せを定めようとする場合に、符号化レートおよび平均多重数から適切な平均メッセージ度数を瞬時に算出するので、符号性能の試験を行って適切な平均メッセージ度数を決定する手法に比較して、処理負担が軽くなるとともに処理時間も短くなり、上記したように、冗長符号化方式における符号化の組合せを早急に決定することが可能になる。さらに、符号化の組合せを決定する処理時間が短くなるので、ノード構成の変更に早急に追従することができ、ノード構成の変更を円滑に行うことが可能になる。
【００４２】
［３：符号化処理装置の構成］
次に、図２を用いて、本実施例に係る冗長符号化装置１の構成を説明する。同図に示すように、この符号化処理装置１は、記憶部２と、制御部３と、格納部４とから構成される。
【００４３】
このうち、記憶部２は、制御部３による各種処理に必要なデータおよびプログラムを保持するメモリであり、特に本発明に密接に関連するものとしては、図２に示すように、符号化レート保持部２１と、平均多重数保持部２２と、対応関係保持部２３とを備える。
【００４４】
ここで、符号化レート保持部２１は、後述する入出力部３１から入力された符号化レート（ノード構成）を保持する手段であり、例えば「メッセージノード：１０個、パリティノード：５個」のような情報を保持する。また、平均多重数保持部２２は、如何なる符号化レートに対しても適切な平均メッセージ度数を算出すると期待される平均多重数を保持する手段であり、具体的には「４」という値を保持する。また、対応関係保持部２３は、後述する対応関係生成部３２によって生成された対応関係を保持する手段であり、例えば「Ｐ１＝Ｍ１  ＸＯＲ  Ｍ２  ＸＯＲ  Ｍ３、Ｐ２＝・・・」のような情報を保持する。
【００４５】
制御部３は、各種の情報を入出力するとともに、ＯＳ（Operating System）などの制御プログラムによって種々の処理を実行する処理部であり、特に本発明に密接に関連するものとしては、図２に示すように、入出力部３１と、対応関係生成部３２と、符号化制御部３３とを備える。
【００４６】
ここで、入出力部３１は、各種の情報を入出力する手段であり、キーボード、マウス、マイク、モニタ（若しくはディスプレイ、タッチパネル）、スピーカ、記憶媒体読取部、通信制御部などを備えて構成され、例えば、ユーザから符号化レート（ノード構成）や符号化前データの入力を受け付ける。また、対応関係生成部３２は、符号化レート保持部２１に保持された符号化レートおよび平均多重数保持部２２に保持された平均多重数に基づいて符号化の組合せ（メッセージノードとパリティノードとの対応関係）を生成する手段である。なお、かかる対応関係生成処理の詳細については図３を用いて後に詳述する。また、符号化制御部３３は、対応関係保持部２３に保持された対応関係に基づいてメッセージノードを符号化（ＸＯＲ演算）することで、パリティノードのデータを生成する手段である。
【００４７】
格納部４は、各種の情報を記憶する記憶手段（データベース）であり、特に本発明に密接に関連するものとしては、図２に示すように、メッセージノード格納部４１と、パリティノード格納部４２とを備える。
【００４８】
ここで、メッセージノード格納部４１は、メッセージノードを記憶する手段であり、具体的には、入出力部３１から入力された複数の符号化前データをそれぞれ複数のメッセージノードに割り当てて記憶する。また、パリティノード格納部４２は、パリティノードを記憶する手段であり、具体的には、符号化制御部３３によって生成される複数のパリティノードのデータを記憶する。
【００４９】
なお、上述してきた符号化処理装置１は、既知のパーソナルコンピュータ、ワークステーション、携帯電話、ＰＨＳ端末、移動体通信端末またはＰＤＡなどの情報処理装置に、上記した記憶部２、制御部３および格納部４の各機能を搭載することによって実現することもできる。
【００５０】
［４：対応関係生成処理の流れ］
次に、図３を用いて、上記した冗長符号化装置１による対応関係生成処理の流れを説明する。図３は、本実施例による対応関係生成処理の流れを示すフローチャートである。なお、以下の説明では、既に、入出力部３１を介してユーザから入力された複数の符号化前データがそれぞれ複数のメッセージノードに割り当てられてメッセージノード格納部４１に格納されているものとする。
【００５１】
同図に示すように、冗長符号化装置１において、入出力部２１を介してユーザから符号化レート（ノード構成）が入力されて符号化レート保持部２１に保持されると（ステップＳ３０１肯定）、対応関係生成部３２は、符号化レート保持部２１に保持された符号化レートおよび平均多重数保持部２２に保持された平均多重数に基づいて平均メッセージ度数を算出する（ステップＳ３０２）。
【００５２】
具体的には、図１に例示した符号化レートの式を用いて平均メッセージ度数を算出するが、例えば、入力された符号化レートが「０．５」であれば、平均多重数は固定値の「４」であるので、平均複製数は「８」となり、これから「１」を減算することで、平均メッセージ度数「７」を算出する。また、例えば、入力された符号化レートが「０．７５」であれば、平均多重数は固定値の「４」であるので、平均複製数は「５．３３」となり、これから「１」を減算することで、平均メッセージ度数「４．３３（もしくは四捨五入で整数値化すれば「４」）」を算出する。
【００５３】
続いて、対応関係生成部３２は、対応関係保持部２３に既に対応関係が保持されているか否かを判定し（ステップＳ３０３）、未だ対応関係が保持されていない場合には（ステップＳ３０３否定）、上記のステップＳ３０２で算出した平均メッセージ度数を用いて対応関係を生成し、生成した対応関係を対応関係保持部２３に登録する（ステップＳ３０８およびＳ３０６）。
【００５４】
ここで、未だ対応関係がない場合における対応関係の生成を具体的に説明すると、対応関係生成部３２は、各符号化前データ（メッセージノード）の符号化先となるパリティノードを平均メッセージ度数に合わせて無作為に選択して対応関係を生成する。例えば、平均メッセージ度数が「２」であれば、図４に例示するように、各符号化前データについて２つのパリティノードを符号化先として無作為に選択して対応関係を生成し、また、例えば、平均メッセージ度数が「３」であれば、図５に例示するように、各符号化前データについて３つのパリティノードを符号化先として無作為に選択して対応関係を生成する。
【００５５】
図３の説明に戻ると、対応関係保持部２３に既に対応関係が保持されている場合には（ステップＳ３０３肯定）、対応関係生成部３２は、新たなノード構成を既にある対応関係に反映する（ステップＳ３０４）。これについて、図６から図１３を用いて以下に具体的に説明する。
【００５６】
例えば、図６に例示するような対応関係が既に対応関係保持部２３に保持されている状況で、あるメッセージノードＭｘを削除するという新たなノード構成が入力された場合には、図７に例示するように、かかるメッセージノードＭｘを削除するとともに、このメッセージノードＭｘに対応付けられていた一つ矢印を削除することで新たな対応関係を生成する。なお、複数のメッセージノードを削除するという新たなノード構成が入力された場合にも、上記と同様に、削除対象のメッセージノードに対応付けられていた矢印をそれぞれ削除する。
【００５７】
また、例えば、図８に例示するような対応関係が既に対応関係保持部２３に保持されている状況で、あるパリティノードＰｘを削除するという新たなノード構成が入力された場合には、図９に例示するように、かかるパリティノードＰｘを削除するとともに、このパリティノードＰｘに対応付けられていた複数の矢印を削除することで新たな対応関係を生成する。なお、複数のパリティノードを削除するという新たなノード構成が入力された場合にも、上記と同様に、削除対象のパリティノードに対応付けられていた矢印をそれぞれ削除する。
【００５８】
また、例えば、図１０に例示するような対応関係が既に対応関係保持部２３に保持されている状況で、あるメッセージノードＭｘ（符号化前データＸ）を追加するという新たなノード構成が入力された場合には、図１１に例示するように、かかるメッセージノードＭｘを追加するとともに、既にある対応関係の平均複製数（もしくは平均メッセージ度数）に基づいて符号化前データＸ（メッセージノードＭｘ）の符号化先となるパリティノードを無作為に選択して新たに対応関係を生成する。つまり、既にある対応関係の平均複製数が「３」であれば（平均メッセージ度数が「２」であれば）、図１１に例示するように、追加された符号化前データＸについて２つのパリティノードを符号化先として無作為に選択して新たに対応関係を生成する。なお、複数のメッセージノードを追加するという新たなノード構成が入力された場合にも、上記と同様に、既にある対応関係の平均メッセージ度数に基づいて複数の追加データそれぞれの符号化先となるパリティノードを無作為に選択して新たに対応関係を生成する。
【００５９】
また、例えば、図１２に例示するような対応関係が既に対応関係保持部２３に保持されている状況で、あるパリティノードＰｘを追加するという新たなノード構成が入力された場合には、図１３に例示するように、かかるパリティノードＰｘを追加するとともに、既にある対応関係の平均多重数に基づいてパリティノードＰｘの生成元となる符号化前データ（メッセージノード）を無作為に選択して新たに対応関係を生成する。つまり、既にある対応関係の平均多重数が「４」であれば、図１３に例示するように、追加されたパリティノードＰｘについて４つの符号化前データ（メッセージノード）を生成元として無作為に選択して新たに対応関係を生成する。なお、複数のパリティノードを追加するという新たなノード構成が入力された場合にも、上記と同様に、既にある対応関係の平均多重数に基づいて複数の追加パリティノードそれぞれの生成元となるメッセージノードを無作為に選択して新たに対応関係を生成する。
【００６０】
図３の説明に戻ると、対応関係生成部３２は、新たなノード構成を既にある対応関係に反映した後に（ステップＳ３０４）、この反映によって生成された新たな対応関係について平均メッセージ度数を求め、この平均メッセージ度数と上記のステップＳ３０２で算出した平均メッセージ度数との差分が所定値の範囲内にあるか否かを判定する（ステップＳ３０５）。なお、ここでいう「所定値の範囲」とは、反映後の対応関係が十分な符号性能を発揮するものと認めるに足りる範囲のことである。
【００６１】
そして、対応関係生成部３２は、反映後の平均メッセージ度数と上記のステップＳ３０２で算出した平均メッセージ度数との差分が所定値の範囲内にある場合には（ステップＳ３０５肯定）、上記のステップＳ３０４による反映によって生成された新たな対応関係を対応関係保持部２３に登録する（ステップＳ３０６）。
【００６２】
これとは反対に、反映後の平均メッセージ度数と上記のステップＳ３０２で算出した平均メッセージ度数との差分が所定値の範囲内にない場合には（ステップＳ３０５否定）、対応関係生成部３２は、平均メッセージ度数との差分が最も大きなメッセージ度数を有する符号化前データ（メッセージノード）について符号化先となるパリティノードを取捨選択して新たな対応関係を生成する（ステップＳ３０７）。具体的には、差分が最も大きな符号化前データを抽出し、上記のステップＳ３０２で算出した平均メッセージ度数に合わせて、この符号化前データの符号化先のパリティノードを無作為に取捨選択することで新たな対応関係を生成する。
【００６３】
これに続いて、対応関係生成部３２は、上記したステップＳ３０５の処理に戻り、ステップＳ３０７で生成された新たな対応関係について平均メッセージ度数を求め、この平均メッセージ度数と上記のステップＳ３０２で算出した平均メッセージ度数との差分が所定値の範囲内にあるか否かを判定する（ステップＳ３０５）。そして、この差分が所定値の範囲内にある場合には（ステップＳ３０５肯定）、対応関係生成部３２は、上記のステップＳ３０７によって生成された新たな対応関係を対応関係保持部２３に登録する（ステップＳ３０６）。
【００６４】
その一方、差分が所定値の範囲内にない場合には（ステップＳ３０５否定）、対応関係生成部３２は、上記したステップＳ３０７の処理に改めて戻り、現に差分が最も大きな符号化前データ（メッセージノード）について符号化先となるパリティノードを取捨選択して新たな対応関係を生成した後に、上記したステップＳ３０５の処理に戻り、かかる処理を上記した差分が所定値の範囲内になるまで繰り返す（ステップＳ３０５およびＳ３０７）。その結果、上記した差分が所定値の範囲内になれば（ステップＳ３０５肯定）、対応関係生成部３２は、上記のステップＳ３０７によって生成された新たな対応関係を対応関係保持部２３に登録する（ステップＳ３０６）。
【００６５】
上記した一連の処理を通じて、対応関係保持部２３には、適切な符号性能を発揮することができる対応関係（符号化の組合せ）が保持される。そして、符号化制御部３３は、対応関係保持部２３に保持された対応関係に基づいて、メッセージノード格納部４１に格納されたメッセージノードを符号化（ＸＯＲ演算）することで、パリティノード格納部４２に格納される符号化データ（冗長情報）を生成する。
【００６６】
［５：実施例の効果等］
上述してきたように、上記の実施例によれば、新たな符号化レート（ノード構成）について符号化の組合せを定めようとする場合に、符号化レートおよび平均多重数から適切な平均メッセージ度数を瞬時に算出するので、符号性能の試験を行って適切な平均メッセージ度数を決定する手法に比較して、処理負担が軽くなるとともに処理時間も短くなり、冗長符号化方式における符号化の組合せを早急に決定することが可能になる。さらに、符号化の組合せを決定する処理時間が短くなるので、ノード構成の変更に早急に追従することができ、ノード構成の変更を円滑に行うことが可能になる。
【００６７】
また、上記の実施例によれば、予め保持する固定の平均多重数を用いて平均メッセージ度数を算出するので、適切でない平均多重数が算出に用いられるおそれを除去し、適切な平均メッセージ度数を確実に算出することが可能になる。
【００６８】
また、上記の実施例によれば、パリティノードを平均メッセージ度数に合わせて無作為に選択することで符号化の組合せを生成するので、パリティノードの選択に係る処理が重くなることもなく、符号化の組合せを一層早急に決定することが可能になる。
【００６９】
また、上記の実施例によれば、ノード構成に変更が生じた場合に（図３のステップＳ３０３肯定）、既に生成されている符号化の組合せに対してノード構成の変更を反映し、反映後の組合せから求まる平均メッセージ度数が適正なものであれば、かかる反映後の組合せを採用するので（図３のステップＳ３０５およびＳ３０６参照）、符号化の組合せを新たに生成し直す手法に比較して、処理負担が軽くなるとともに処理時間も短くなり、ノード構成の変更後における符号化の組合せを早急に決定することが可能になる。これによって、ノード構成の変更に一層早急に追従することができ、ノード構成の変更を一層円滑に行うことが可能になる。
【００７０】
また、上記の実施例によれば、反映後の組合せから求まる平均メッセージ度数が適正なものでない場合でも（図３のステップＳ３０３否定）、差分が大きな符号化前データから順番にパリティノードを取捨選択して新たな組合せを順次生成し、平均メッセージ度数が適正なものになったところで新たな組合せを採用するので（図３のステップＳ３０７およびＳ３０５参照）、符号化の組合せを新たに生成し直す手法に比較して、処理負担が軽くなるとともに処理時間も短くなり、ノード構成に変更後における符号化の組合せを早急に決定することが可能になる。これによって、ノード構成の変更に一層早急に追従することができ、ノード構成の変更を一層円滑に行うことが可能になる。
【００７１】
［６：他の実施例］
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下に示すように、（１）〜（４）にそれぞれ区分けして他の実施例を説明する。
【００７２】
（１）平均多重数
例えば、上記の実施例では、予め保持する固定の平均多重数「４」を用いて平均メッセージ度数を算出する場合を説明したが、本発明はこれに限定されるものではなく、例えば、「３」、「３．５」、「４．５」など、概ね「３」〜「４．５」の範囲に属する数値を保持すればよく、さらに、符号性能の低下を許容するならば、上記した範囲から外れる数値を保持するようにしても構わない。
【００７３】
また、上記の実施例では、平均多重数を固定の期待値として保持する場合を説明したが、本発明はこれに限定されるものではなく、入出力部３１を介してユーザから平均多重数を受け付け、かかる平均多重数を用いて平均メッセージ度数を算出するようにしてもよい。なお、この場合には、上記した「３」〜「４．５」の範囲外では平均多重数の受け付けを拒絶するようにしてもよい。さらに、ユーザから平均多重数を受け付けるのではなく、ユーザから受け付けたノード数に応じて平均多重数を算出（例えば、ノード数の対数に固定値を乗算して平均多重数を算出）し、この平均多重数を用いて平均メッセージ度数を算出するなど、平均メッセージ度数の算出前に所定のアルゴリズムで平均多重数を算出するようにしてもよい。
【００７４】
（２）ノードの選択
また、上記の実施例では、各符号化前データの符号化先となるパリティノードを無作為に選択する場合を説明したが（図３のステップＳ３０８参照）、本発明はこれに限定されるものではなく、ランダムではない所定のアルゴリズム（例えば、所定のパリティノードに符号化先を集中させるアルゴリズムなど）によってパリティノードを選択するようにしてもよい。また、これと同様に、図３のステップＳ３０４やＳ３０７による処理においても、無作為にノードを選択するのではなく、所定のアルゴリズムによってノードを選択するようにしてもよい。
【００７５】
（３）平均多重数を用いた対応関係の生成
また、上記の実施例では、平均メッセージ度数に対応するように符号化の組合せ（各符号化前データと各ノードとを繋げる矢印によって表現される対応関係）を生成する場合を説明したが、本発明はこれに限定されるものではなく、平均多重数に対応するように符号化の組合せを生成してもよい。すなわち、平均メッセージ度数を算出することなく、各ノードの生成元となる符号化前データを平均多重数（例えば「４」）に合わせて無作為に選択して対応関係を生成するようにしてもよい。
【００７６】
このように、平均メッセージ度数を算出することなく、平均多重数から符号化の組合せを決定する場合でも、上記した実施例と同様、処理負担が軽くなるとともに処理時間も短くなり、冗長符号化方式における符号化の組合せを早急に決定することが可能になる。さらに、符号化の組合せを決定する処理時間が短くなるので、ノード構成の変更に早急に追従することができ、ノード構成の変更を円滑に行うことが可能になる。
【００７７】
（４）他の適用分野
上記の実施例では、本発明をデータの記憶方式に適用する場合を説明したが、本発明はこれに限定されるものではなく、いわゆるＬＤＰＣ符号化方式を用いた通信方式にも同様に適用することができ、さらには、図１に示したノードの組合せが成立する技術分野であれば、本発明を同様に適用することができる。
【００７８】
（５）システム構成等
また、図示した冗長符号化装置１の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、冗長符号化装置１の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、冗長符号化装置１にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００７９】
また、上記の実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００８０】
なお、本実施例で説明した各種の処理方法（特に、図３を用いて説明した対応関係生成処理方法）は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【産業上の利用可能性】
【００８１】
以上のように、本発明に係る符号化処理装置、符号化処理方法および符号化処理プログラムは、複数のメッセージノードと複数のパリティノードとからなるノードの集合について符号化の組合せを生成する場合に有用であり、特に、冗長符号化方式における符号化の組合せを早急に決定することに適する。
【図面の簡単な説明】
【００８２】
【図１】実施例で用いる用語を説明するための図である。
【図２】実施例に係る冗長符号化装置の構成を示すブロック図である。
【図３】実施例による対応関係生成処理の流れを示すフローチャートである。
【図４】対応関係の生成例を示す図である。
【図５】対応関係の生成例を示す図である。
【図６】対応関係の生成例を示す図である。
【図７】対応関係の生成例を示す図である。
【図８】対応関係の生成例を示す図である。
【図９】対応関係の生成例を示す図である。
【図１０】対応関係の生成例を示す図である。
【図１１】対応関係の生成例を示す図である。
【図１２】対応関係の生成例を示す図である。
【図１３】対応関係の生成例を示す図である。
【符号の説明】
【００８３】
１  冗長符号化装置
２  記憶部
３  制御部
４  格納部
２１  符号化レート保持部
２２  平均多重数保持部
２３  対応関係保持部
３１  入出力部
３２  対応関係生成部
３３  符号化制御部
４１  メッセージノード格納部
４２  パリティノード格納部
【図１】
2006050482.tif 000003
【図２】
2006050482.tif 000004
【図３】
2006050482.tif 000005
【図４】
2006050482.tif 000006
【図５】
2006050482.tif 000007
【図６】
2006050482.tif 000008
【図７】
2006050482.tif 000009
【図８】
2006050482.tif 000010
【図９】
2006050482.tif 000011
【図１０】
2006050482.tif 000012
【図１１】
2006050482.tif 000013
【図１２】
2006050482.tif 000014
【図１３】
2006050482.tif 000015