(57)【要約】  冗長度の動的な設定により、縮退動作時にも消失訂正が可能になるとともに、必要とする並列媒体を削減することを目的とする。並列データ符号復号化システムは、複数のレーンを用いて符号化器から復号化器へ並列データ伝送を行う。符号化器は、各レーンのシンボルの符号ベクトルＭとシンボルの有効性を示す状態ベクトルＵの要素同士の積を符号化し、符号化によって得られた送信ベクトルＹと共に前記状態ベクトルＵを送信する。復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに送受信区間での送信ベクトルの各要素が消失したか否かを示す消失ベクトルＥを用いて、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号する。
2014045906.tif 000002
【特許請求の範囲】
【請求項１】
複数のレーンを用いて符号化器から復号化器へ並列データ伝送を行う並列データ符号復号化システムであって、
前記符号化器は、各レーンのシンボルの符号ベクトルＭと前記シンボルの有効性を示す状態ベクトルＵの要素同士の積を符号化し、符号化によって得られた送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに送受信区間での前記送信ベクトルＹの各要素が消失したか否かを示す消失ベクトルＥを用いて、前記符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号する
並列データ符号復号化システム。
【請求項２】
前記符号化器と前記復号化器はＲ個のレーンで接続され、
前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、Ｒシンボルの消失訂正能力を持つ符号化率０．５のＭＤＳ（Ｍａｘｉｍｕｍ−Ｄｉｓｔａｎｃｅ−Ｓｅｐａｒａｂｌｅ）符号の生成行列Ｇを用いてパリティＳを計算し、前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、並びに前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥを用いて、式（Ｃ１）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行う
請求項１に記載の並列データ符号復号化システム。
【数８５】
2014045906.tif 000088
ただし、
【数８６】
2014045906.tif 000089
【請求項３】
前記符号化器と前記復号化器はＲ個のレーンで接続され、
前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、Ｒシンボルの消失訂正能力を持つ符号化率０．５のＭＤＳ符号の生成行列Ｇを用いてパリティＳを計算し、前記符号ベクトルＭ及び前記状態ベクトルＵ及び前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びに行列ＡＲのｕｊ＝１，ｕｊ∈Ｕに対応する行と単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＢＲ（Ｕ）を用いて、式（Ｃ２）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行う
請求項１に記載の並列データ符号復号化システム。
【数８７】
2014045906.tif 000090
ただし、
【数８８】
2014045906.tif 000091
【請求項４】
前記符号化器と前記復号化器はＲ個のレーンで接続され、
前記符号化器は、Ｒシンボルの符号ベクトルＭ、各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵ並びにＧＦ（２ｎ）の要素からなるＲ行Ｒ列のＣａｕｃｈｙ行列ＣＲ×Ｒを用いて、パリティＳを計算し、前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥを用いて、式（Ｃ３）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行う
請求項１に記載の並列データ符号復号化システム。
【数８９】
2014045906.tif 000092
ただし、
【数９０】
2014045906.tif 000093
【請求項５】
前記符号化器と前記復号化器はＲ個のレーンで接続され、
前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵ並びにＧＦ（２ｎ）の要素からなるＲ行Ｒ列のＣａｕｃｈｙ行列ＣＲ×Ｒを用いて、パリティＳを計算し、前記符号ベクトルＭ及び前記状態ベクトルＵ及び前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びにＣＲ×Ｒのｕｊ＝１，ｕｊ∈Ｕに対応する行と単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＤＲ（Ｕ）を用いて、式（Ｃ４）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行う
請求項１に記載の並列データ符号復号化システム。
【数９１】
2014045906.tif 000094
ただし、
【数９２】
2014045906.tif 000095
【請求項６】
前記符号化器と前記復号化器はＲ個のレーンで接続され、
前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰを計算し、Ｐで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ、ヴァンデルモンド行列ＶＲ（ｋ）並びにヴァンデルモンド行列ＷＲ（ｋ）を用いて、式（Ｃ５）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行う
請求項１に記載の並列データ符号復号化システム。
【数９３】
2014045906.tif 000096
ただし、
【数９４】
2014045906.tif 000097
【請求項７】
前記符号化器と前記復号化器はＲ個のレーンで接続され、
前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰを計算し、前記符号ベクトルＭ及び前記状態ベクトルＵ及び前記係数ベクトルＰで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びにヴァンデルモンド行列ＷＲ（ｋ）のｕｊ＝１，ｕｊ∈Ｕに対応する行列及びヴァンデルモンド行列ＶＲ（ｋ）のｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＺＲ（Ｕ）を用い、式（Ｃ６）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行う
請求項１に記載の並列データ符号復号化システム。
【数９５】
2014045906.tif 000098
ただし、
【数９６】
2014045906.tif 000099
【請求項８】
前記符号化器と前記復号化器はＲ個のレーンで接続され、
前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰ、ヴァンデルモンド行列ＶＲ（ｋ）、ヴァンデルモンド行列ＷＲ（ｋ）並びにパリティＳを計算し、前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥを用いて、式（Ｃ７）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行う
請求項１に記載の並列データ符号復号化システム。
【数９７】
2014045906.tif 000100
ただし、
【数９８】
2014045906.tif 000101
【請求項９】
前記符号化器と前記復号化器はＲ個のレーンで接続され、
前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰ、ヴァンデルモンド行列ＶＲ（ｋ）、ヴァンデルモンド行列ＷＲ（ｋ）並びにパリティＳを計算し、前記符号ベクトルＭ及び前記状態ベクトルＵ及び前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びに前記ヴァンデルモンド行列ＷＲ（ｋ）のｕｊ＝１，ｕｊ∈Ｕに対応する行列及び単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＺＲ’（Ｕ）を用いて、式（Ｃ８）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行う
請求項１に記載の並列データ符号復号化システム。
【数９９】
2014045906.tif 000102
ただし、
【数１００】
2014045906.tif 000103
【請求項１０】
前記複数のレーンは、Ｒ本の論理レーンからなる並列バスであり、
前記符号化器は、
前記並列バスへの入力Ｄｉｎを要素毎独立の入力ＦＩＦＯに書き込み、
各要素が１シンボルの読み出し及び読み出し停止をそれぞれ「１」及び「０」で示すＲビットの読み出し信号Ｆを生成し、前記入力ＦＩＦＯの出力を前記符号ベクトルＭとし、前記読み出し信号Ｆを前記状態ベクトルＵとして、前記送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、
演算により得られた前記部分集合Ｍｓｕｂを要素毎独立の出力ＦＩＦＯに書き込み、前記出力ＦＩＦＯから前記並列バスへの出力Ｄｏｕｔを読み出す
請求項１から請求項９のいずれか１項に記載の並列データ符号復号化システム。
【請求項１１】
前記符号化器と前記復号化器は、Ｒ本の論理レーンを用いた並列パケット伝送を行い、
前記符号化器は、
論理レーン毎に独立の入力ＦＩＦＯに書き込みを行い、
各要素が１シンボルの読み出し及び読み出し停止をそれぞれ「１」及び「０」で示すＲビットの読み出し信号Ｆを生成し、前記入力ＦＩＦＯの出力を前記符号ベクトルＭとし、前記読み出し信号Ｆを前記状態ベクトルＵとして、前記送信ベクトルＹと共に前記状態ベクトルＵを送信し、
前記復号化器は、
演算により得られた前記部分集合Ｍｓｕｂを論理レーン毎に独立の出力ＦＩＦＯに書き込み、前記出力ＦＩＦＯから論理レーン毎にパケットを読み出す
請求項１から請求項９のいずれか１項に記載の並列データ符号復号化システム。
【請求項１２】
前記符号化器は、
０≦ｒｍｉｎ≦ｒｍａｘ≦Ｒとなる冗長度の最小値ｒｍｉｎ及び最大値ｒｍａｘを設定し、
式（Ｃ１１１）に従って前記読み出し信号Ｆを生成し、前記送信ベクトルＹのうち式（Ｃ１１２）で表される個数のシンボルを選択し、前記選択されたシンボルのみを対応する論理伝送レーンに送出し、非選択シンボルを消失とみなし、
前記復号化器は、
前記非選択シンボルおよび伝送における消失シンボルに関して消失訂正を行う
請求項１０又は１１に記載の並列データ符号復号化システム。
【数１０１】
2014045906.tif 000104
【請求項１３】
前記符号化器及び前記復号化器は、
前記非選択シンボルの論理伝送レーンに対応する物理伝送レーンを低消費電力モードへ移行させ、もしくは、
前記物理伝送レーンに対する供給電力を停止し、もしくは、
前記物理伝送レーンを物理的に排除する請求項１２に記載の並列データ符号復号化システム。
【請求項１４】
前記符号化器は、
論理伝送レーン毎に前記送信ベクトルＹの要素の時系列ブロックに対して誤り訂正符号もしくは誤り検出符号を付加して論理伝送レーンに送出し、
前記復号化器は、
論理伝送レーン毎に、
前記時系列ブロックに誤りが検出されない場合は受信ブロックをそのまま前記受信ベクトルＹ’の要素として、
前記時系列ブロックに訂正可能な誤りが検出された場合は訂正後の受信ブロックを前記受信ベクトルＹ’の要素として、
前記時系列ブロックに訂正不可能な誤りが検出された場合は前記受信ブロックを消失とみなして消失訂正を行う
請求項１０から請求項１３のいずれか１項に記載の並列データ符号復号化システム。
【請求項１５】
前記並列データ符号復号化システムは、レーン毎にＯＴＵフレームを生成して外部から入力された被伝送データを並列伝送媒体に送信し、前記複数のレーンによって伝送された前記ＯＴＵフレームから前記被伝送データを抽出し、抽出された前記被伝送データを外部に出力する並列伝送システムであって、
前記複数のレーンはシンボルレーンとパリティレーンに分類され、
前記符号化器は、前記シンボルレーンについては、分割された被伝送データをＯＰＵ／ＯＤＵペイロードに格納し、ＩＴＵ−Ｔ  Ｇ．７０９に準拠したＯＴＵフレームを伝送し、前記パリティレーンについては、ＦＡＳ及びＦＥＣ以外の領域には各シンボルレーンの同一行同一列のシンボルを有効要素として前記符号化によって得られた前記送信ベクトルの対応要素を格納し、前記ＦＡＳ及びＦＥＣ領域にはＩＴＵ−Ｔ  Ｇ．７０９に準拠した値を格納して、伝送を行い、
前記復号化器は、前記複数のレーンによって伝送された前記ＯＴＵフレームのうち、正常に受信したシンボルレーンに含まれるＯＴＵフレームに対しては、前記ＯＰＵ／ＯＤＵペイロードに含まれる前記被伝送データを抽出し、抽出された前記被伝送データを外部に出力し、ＬＯＦ検出、もしくは、ＦＥＣによる誤り訂正限界の検出、もしくは、ＢＩＰによる誤り検出により、異常を検出したシンボルレーンに対しては、前記異常を検出したシンボルレーンに含まれるＯＰＵ／ＯＤＵペイロードを消失訂正により復元して前記被伝送データを抽出し、抽出された前記被伝送データを外部に出力する
請求項１ないし請求項９のいずれか１項に記載の並列データ符号復号化システム。
【請求項１６】
ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＰＳＩの値を参照する事によって前記シンボルレーンが識別される
請求項１５に記載の並列データ符号復号化システム。
【請求項１７】
前記符号化器は、各パリティレーン内の、ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＯＨの一部の領域Ａに関し、前記領域Ａに対応した送信ベクトルを同一パリティレーン内のＯＨ領域Ｂに格納し、前記領域ＡにはＩＴＵ−Ｔ  Ｇ．７０９に準拠した値を格納し、
前記復号化器は、前記異常を検出したシンボルレーンに含まれる前記ＯＰＵ／ＯＤＵペイロードを復元する際、前記領域Ａの復元に各パリティレーンにおける前記ＯＨ領域Ｂの情報を用いる
請求項１５または請求項１６に記載の並列データ符号復号化システム。
【請求項１８】
前記領域Ａは、ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＭＦＡＳおよびＰＳＩを少なくとも含み、
前記符号化器は、前記ＭＦＡＳを用いたマルチフレーム転送により、前記領域Ａ及び前記ＯＨ領域Ｂのフレーム内位置の情報を送信し、
前記復号化器は、前記異常を検出したシンボルレーンに含まれる前記ＯＰＵ／ＯＤＵペイロードを復元する際に前記フレーム内位置の情報を用いる
請求項１７に記載の並列データ符号復号化システム。
【請求項１９】
被伝送パケットをあらかじめ決められた長さを単位に分割し、もしくは、前記被伝送パケットを一定時間毎にタイムスロット単位に分割し、さらに同一タイムスロット内の前記被伝送パケットを前記符号化器の入力並列数と同数の系統に分配・分割し、分配・分割されたパケットを前記符号化器へ入力するパケット入力部と、
前記符号化器の出力に対して、論理レーン毎にレーンおよびタイムスロットを識別分離可能なカプセル化を行い、１以上の伝送媒体にカプセル化パケットを出力する符号化パケット出力部と、
カプセル化情報に基づいて、前記伝送媒体により伝送された前記カプセル化パケットを論理レーン毎に分離し、各レーンにおいて、分離されたカプセル化パケットをタイムスロット毎に整列し、分離・整列されたカプセル化パケットを前記復号化器へ入力する符号化パケット入力部と、
前記復号化器の出力から前記被伝送パケットを再構成して前記被伝送パケットを出力するパケット出力部と
をさらに備えた請求項１１から請求項１４のいずれか１項に記載の並列データ符号復号化システム。
【請求項２０】
前記パケット入力部は、パケットが存在しない論理レーンの数を最大化するように前記符号化器へ入力される前記パケットの分配を最適化する
請求項１９に記載の並列データ符号復号化システム。
【請求項２１】
前記パケット入力部は、前記被伝送パケットのパケット長が１タイムスロットのデータ長よりも大きい場合に、前記被伝送パケットを前記１タイムスロットのデータ長以下の長さを持つパケットに分割し、分割された前記パケットを複数のレーンへ分配する
請求項１９または請求項２０に記載の並列データ符号復号化システム。
【請求項２２】
前記パケット入力部は、パケットが存在しないレーンの数が少なくとも最少冗長度ｒｍｉｎとなるように、パケットを割り当てようとしているタイムスロットとは異なる他のタイムスロットに前記パケットを割り当て、
前記符号化パケット出力部は、前記符号化器から出力されるパケットのうち冗長パケットの個数を高々最大冗長度ｒｍａｘに制限する
請求項１９から請求項２１のいずれか１項に記載の並列データ符号復号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ符号化側とデータ復号化側の間が複数の物理媒体もしくは論理媒体を用いて並列接続される場合において、媒体の破損や修復不能な誤りによるデータ消失に対してロバスト性を向上させるデータ符号化及び復号化方式に関する。
また、本発明は、パケット伝送におけるパケット消失訂正を行うパケット冗長伝送システム、及びパケット冗長伝送方法に関する。【０００２】
本願は、２０１２年９月２１日に日本へ出願された特願２０１２−２０８００１号、および、２０１３年２月５日に日本へ出願された特願２０１３−０２０６６２号に基づき優先権を主張し、それらの内容をここに援用する。
【背景技術】
【０００３】
複数媒体におけるデータ消失に対するロバスト性の向上に関しては、主に２つの方向性がある。１つは特許文献１に示すように、媒体を冗長化して情報を伝達し、特定の媒体に障害が発生した場合、冗長媒体に切り替えることで瞬断することなく、情報伝達帯域を１００％維持する方法である。もう１つは特許文献２に示すように、一部の媒体に障害が発生した場合、残りの媒体での縮退動作を可能にする方法である。【０００４】
ＭＰＥＧ２（Moving Picture Experts Group Phase2）  ｏｖｅｒ  ＩＰ（Internet Protocol）のように、動画像をパケット伝送する場合、リアルタイム性の要求からＦＥＣ（forward error correction：前方誤り訂正）を用いた冗長伝送が用いられてきた（例えば、非特許文献６，７参照）。
また、ＴＣＰ（Transmission Control Protocol）では、消失パケットを再送することによって高信頼化を実現している（例えば、非特許文献８参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】日本特開２００８−１６７１２８号公報
【特許文献２】日本特開２０１１−２１１５３２号公報
【非特許文献】
【０００６】
【非特許文献１】「リードソロモン符号」、［online］，ウィキペディア、インターネット＜ｈｔｔｐ：／／ｊａ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／％Ｅ３％８３％ＡＡ％Ｅ３％８３％ＢＣ％Ｅ３％８３％８９％Ｅ３％８３％ＢＢ％Ｅ３％８２％ＢＤ％Ｅ３％８３％ＡＤ％Ｅ３％８３％Ａ２％Ｅ３％８３％Ｂ３％Ｅ７％ＡＣ％Ａ６％Ｅ５％８Ｆ％Ｂ７＞
【非特許文献２】短縮リードソロモン符号：小野竜一、他１名、「短縮Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号の誤り訂正能力」、電子情報通信学会、信学技法、ＩＴ９４−３１、ｐｐ．４９〜５４、１９９４年７月（［online］，インターネット＜ｈｔｔｐ：／／ｃｉ．ｎｉｉ．ａｃ．ｊｐ／ｎａｉｄ／１１０００３１９７４４８＞）
【非特許文献３】Ｃａｕｃｈｙリードソロモン符号：Ｊ．  Ｂｌｏｍｅｒ，  Ｍ．  Ｋａｌｆａｎｅ，  Ｒ．  Ｋａｒｐ，  Ｍ．  Ｋａｒｐｉｎｓｋｉ，  Ｍ．  Ｌｕｂｙ，  ａｎｄ  Ｄ．  Ｚｕｃｋｅｒｍａｎ：  “Ａｎ  ＸＯＲ−ｂａｓｅｄ  ｅｒａｓｕｒｅ−ｒｅｓｉｌｉｅｎｔ  ｃｏｄｉｎｇ  ｓｃｈｅｍｅ”，  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＴＲ−９５−０４８，  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｉｎｓｔｉｔｕｔｅ，  Ａｕｇｕｓｔ  １９９５．
【非特許文献４】ＭＤＳ符号：栗原正純、「ＭＤＳ符号とその復号法」、電子情報通信学会、信学技法、ＩＴ２００３−９２、ＩＳＥＣ２００３−１３２、ＷＢＳ２００３−２１０、２００４年３月（［online］，インターネット＜ｈｔｔｐ：／／ｃｉ．ｎｉｉ．ａｃ．ｊｐ／ｎａｉｄ／１１０００３１７４１６９＞）
【非特許文献５】ヴァンデルモンド行列（Vandermonde_matrix）、［online］，Wikipedia、インターネット＜ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／Ｖａｎｄｅｒｍｏｎｄｅ＿ｍａｔｒｉｘ＞
【非特許文献６】「ＨＤＴＶ  ＭＰＥＧ−２高多重伝送技術」，［online］，２００５年，日本電信電話株式会社，インターネット＜http://www.ntt.co.jp/journal/0507/files/jn200507043.pdf＞
【非特許文献７】「動画像配信のための下位互換性を考慮したパケットレベルＬＤＧＭ符号の構成と理論解析」，外村  喜秀、他５名，電子情報通信学会論文誌  ２０１０／３，  Ｖｏｌ．Ｊ９３−Ａ  Ｎｏ．３，ｐｐ．２１２−２１５，２０１０年
【非特許文献８】「SPECIFICATION OF INTERNET TRANSMISSION CONTROL PROGRAM」，［online］，１９７４年，インターネット＜http://tools.ietf.org/pdf/rfc675.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献６、７などにおいてパケット伝送に用いられているＦＥＣは、固定長ブロックに入力データが満たされた時点でＦＥＣのパリティが計算され、冗長パケットが送出される。従って、動画などの固定レートの入力に対しては一定間隔でパケットが出力されるが、変動レートもしくはバースト到着の入力に対しては過剰な遅延が発生する可能性が生じる。例えば、ブロックサイズ１００のＦＥＣの場合、９９サイズのデータが入力されても、残りの１のサイズのデータが入力されるまで冗長パケットは送出されない。従って、変動レートの場合には最大遅延時間は転送レートに反比例し、バースト入力に関しては別途タイムアウトの機構を用いないと最大遅延時間の保証はない。
また、非特許文献８に記載のようにＴＣＰで実現されている消失パケットの再送による高信頼化方法は、国際回線など長距離通信における再送遅延や輻輳制御による転送レートの低下などの事由により、リアルタイム性が要求される用途には適さない。【０００８】
本発明は、冗長度の動的な設定により、縮退動作時にも消失訂正が可能になるとともに、情報伝達に供しない帯域（物理帯域−情報帯域）を冗長化に用いることで、必要とする並列媒体を削減することを目的とする。【０００９】
また、本発明は、上記問題を解決すべく、変動レートもしくはバースト到着のパケット入力に対しても、過剰な遅延を発生させずにパケット冗長化によるパケット消失訂正を行うことができるパケット冗長伝送システム、及びパケット冗長伝送方法を提供する。
【課題を解決するための手段】
【００１０】
本発明は、複数のレーンを用いて符号化器から復号化器へ並列データ伝送を行う並列データ符号復号化システムであって、前記符号化器は、各レーンのシンボルの符号ベクトルＭと前記シンボルの有効性を示す状態ベクトルＵの要素同士の積を符号化し、符号化によって得られた送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに送受信区間での前記送信ベクトルＹの各要素が消失したか否かを示す消失ベクトルＥを用いて、前記符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号する。【００１１】
本願明細書では、ベクトルＸとベクトルＹの
【数１】
2014045906.tif 000003
をベクトルの要素同士の積と定義する。例えば、
【数２】
2014045906.tif 000004
である場合、ベクトルＸとベクトルＹの各要素同士の積のベクトルＺは、
【数３】
2014045906.tif 000005
で表される。【００１２】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器はＲ個のレーンで接続され、前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、Ｒシンボルの消失訂正能力を持つ符号化率０．５のＭＤＳ（Ｍａｘｉｍｕｍ−Ｄｉｓｔａｎｃｅ−Ｓｅｐａｒａｂｌｅ）符号の生成行列Ｇを用いてパリティＳを計算し、前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、並びに前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥを用いて、式（Ｍ１）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行ってもよい。
【数４】
2014045906.tif 000006
ただし、
【数５】
2014045906.tif 000007
【００１３】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器はＲ個のレーンで接続され、前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、Ｒシンボルの消失訂正能力を持つ符号化率０．５のＭＤＳ符号の生成行列Ｇを用いてパリティＳを計算し、前記符号ベクトルＭ及び前記状態ベクトルＵ及び前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びに行列ＡＲのｕｊ＝１，ｕｊ∈Ｕに対応する行と単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＢＲ（Ｕ）を用いて、式（Ｍ２）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行ってもよい。
【数６】
2014045906.tif 000008
ただし、
【数７】
2014045906.tif 000009
【００１４】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器はＲ個のレーンで接続され、前記符号化器は、Ｒシンボルの符号ベクトルＭ、各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵ並びにＧＦ（２ｎ）の要素からなるＲ行Ｒ列のＣａｕｃｈｙ行列ＣＲ×Ｒを用いて、パリティＳを計算し、前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥを用いて、式（Ｍ３）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行ってもよい。
【数８】
2014045906.tif 000010
ただし、
【数９】
2014045906.tif 000011
【００１５】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器はＲ個のレーンで接続され、前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵ並びにＧＦ（２ｎ）の要素からなるＲ行Ｒ列のＣａｕｃｈｙ行列ＣＲ×Ｒを用いて、パリティＳを計算し、前記符号ベクトルＭ及び前記状態ベクトルＵ及び前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びにＣＲ×Ｒのｕｊ＝１，ｕｊ∈Ｕに対応する行と単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＤＲ（Ｕ）を用いて、式（Ｍ４）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行ってもよい。
【数１０】
2014045906.tif 000012
ただし、
【数１１】
2014045906.tif 000013
【００１６】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器はＲ個のレーンで接続され、前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰを計算し、Ｐで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ、ヴァンデルモンド行列ＶＲ（ｋ）並びにヴァンデルモンド行列ＷＲ（ｋ）を用いて、式（Ｍ５）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行ってもよい。
【数１２】
2014045906.tif 000014
ただし、
【数１３】
2014045906.tif 000015
【００１７】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器はＲ個のレーンで接続され、前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰを計算し、前記符号ベクトルＭ及び前記状態ベクトルＵ及び前記係数ベクトルＰで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びにヴァンデルモンド行列ＷＲ（ｋ）のｕｊ＝１，ｕｊ∈Ｕに対応する行列及びヴァンデルモンド行列ＶＲ（ｋ）のｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＺＲ（Ｕ）を用い、式（Ｍ６）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行ってもよい。
【数１４】
2014045906.tif 000016
ただし、
【数１５】
2014045906.tif 000017
【００１８】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器はＲ個のレーンで接続され、前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰ、ヴァンデルモンド行列ＶＲ（ｋ）、ヴァンデルモンド行列ＷＲ（ｋ）並びにパリティＳを計算し、前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥを用いて、式（Ｍ７）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行ってもよい。
【数１６】
2014045906.tif 000018
ただし、
【数１７】
2014045906.tif 000019
【００１９】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器はＲ個のレーンで接続され、前記符号化器は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰ、ヴァンデルモンド行列ＶＲ（ｋ）、ヴァンデルモンド行列ＷＲ（ｋ）並びにパリティＳを計算し、前記符号ベクトルＭ及び前記状態ベクトルＵ及び前記パリティＳで定義される送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに前記送受信区間での前記送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びに前記ヴァンデルモンド行列ＷＲ（ｋ）のｕｊ＝１，ｕｊ∈Ｕに対応する行列及び単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＺＲ’（Ｕ）を用いて、式（Ｍ８）を解くことにより、前記符号ベクトルＭの有効な要素からなる前記部分集合Ｍｓｕｂを復号し、消失訂正を行ってもよい。
【数１８】
2014045906.tif 000020
ただし、
【数１９】
2014045906.tif 000021
【００２０】
本発明の並列データ符号復号化システムでは、前記複数のレーンは、Ｒ本の論理レーンからなる並列バスであり、前記符号化器は、前記並列バスへの入力Ｄｉｎを要素毎独立の入力ＦＩＦＯに書き込み、各要素が１シンボルの読み出し及び読み出し停止をそれぞれ「１」及び「０」で示すＲビットの読み出し信号Ｆを生成し、前記入力ＦＩＦＯの出力を前記符号ベクトルＭとし、前記読み出し信号Ｆを前記状態ベクトルＵとして、前記送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、演算により得られた前記部分集合Ｍｓｕｂを要素毎独立の出力ＦＩＦＯに書き込み、前記出力ＦＩＦＯから前記並列バスへの出力Ｄｏｕｔを読み出してもよい。【００２１】
本発明の並列データ符号復号化システムでは、前記符号化器と前記復号化器は、Ｒ本の論理レーンを用いた並列パケット伝送を行い、前記符号化器は、論理レーン毎に独立の入力ＦＩＦＯに書き込みを行い、各要素が１シンボルの読み出し及び読み出し停止をそれぞれ「１」及び「０」で示すＲビットの読み出し信号Ｆを生成し、前記入力ＦＩＦＯの出力を前記符号ベクトルＭとし、前記読み出し信号Ｆを前記状態ベクトルＵとして、前記送信ベクトルＹと共に前記状態ベクトルＵを送信し、前記復号化器は、演算により得られた前記部分集合Ｍｓｕｂを論理レーン毎に独立の出力ＦＩＦＯに書き込み、前記出力ＦＩＦＯから論理レーン毎にパケットを読み出してもよい。【００２２】
本発明の並列データ符号復号化システムでは、前記符号化器は、０≦ｒｍｉｎ≦ｒｍａｘ≦Ｒとなる冗長度の最小値ｒｍｉｎ及び最大値ｒｍａｘを設定し、式（Ｍ１１１）に従って前記読み出し信号Ｆを生成し、前記送信ベクトルＹのうち式（Ｍ１１２）で表される個数のシンボルを選択し、前記選択されたシンボルのみを対応する論理伝送レーンに送出し、非選択シンボルを消失とみなし、前記復号化器は、前記非選択シンボルおよび伝送における消失シンボルに関して消失訂正を行ってもよい。
【数２０】
2014045906.tif 000022
【００２３】
本発明の並列データ符号復号化システムでは、前記符号化器及び前記復号化器は、前記非選択シンボルの論理伝送レーンに対応する物理伝送レーンを低消費電力モードへ移行させ、もしくは、前記物理伝送レーンに対する供給電力を停止し、もしくは、前記物理伝送レーンを物理的に排除してもよい。【００２４】
本発明の並列データ符号復号化システムでは、論理伝送レーン毎に前記送信ベクトルＹの要素の時系列ブロックに対して誤り訂正符号もしくは誤り検出符号を付加して論理伝送レーンに送出し、前記復号化器は、論理伝送レーン毎に、前記時系列ブロックに誤りが検出されない場合は受信ブロックをそのまま前記受信ベクトルＹ’の要素として、前記時系列ブロックに訂正可能な誤りが検出された場合は訂正後の受信ブロックを前記受信ベクトルＹ’の要素として、前記時系列ブロックに訂正不可能な誤りが検出された場合は前記受信ブロックを消失とみなして消失訂正を行ってもよい。【００２５】
本発明において、前記並列データ符号復号化システムは、レーン毎にＯＴＵフレームを生成して外部から入力された被伝送データを並列伝送媒体に送信し、前記複数のレーンによって伝送された前記ＯＴＵフレームから前記被伝送データを抽出し、抽出された前記被伝送データを外部に出力する並列伝送システムであって、前記複数のレーンはシンボルレーンとパリティレーンに分類され、前記符号化器は、前記シンボルレーンについては、分割された被伝送データをＯＰＵ／ＯＤＵペイロードに格納し、ＩＴＵ−Ｔ  Ｇ．７０９に準拠したＯＴＵフレームを伝送し、前記パリティレーンについては、ＦＡＳ及びＦＥＣ以外の領域には各シンボルレーンの同一行同一列のシンボルを有効要素として前記符号化によって得られた前記送信ベクトルの対応要素を格納し、前記ＦＡＳ及びＦＥＣ領域にはＩＴＵ−Ｔ  Ｇ．７０９に準拠した値を格納して、伝送を行い、前記復号化器は、前記複数のレーンによって伝送された前記ＯＴＵフレームのうち、正常に受信したシンボルレーンに含まれるＯＴＵフレームに対しては、前記ＯＰＵ／ＯＤＵペイロードに含まれる前記被伝送データを抽出し、抽出された前記被伝送データを外部に出力し、ＬＯＦ検出、もしくは、ＦＥＣによる誤り訂正限界の検出、もしくは、ＢＩＰによる誤り検出により、異常を検出したシンボルレーンに対しては、前記異常を検出したシンボルレーンに含まれるＯＰＵ／ＯＤＵペイロードを消失訂正により復元して前記被伝送データを抽出し、抽出された前記被伝送データを外部に出力するようにしてもよい。【００２６】
本発明の並列データ符号復号化システムでは、ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＰＳＩの値を参照する事によって前記シンボルレーンが識別されるようにしてもよい。【００２７】
本発明の並列データ符号復号化システムでは、前記符号化器は、各パリティレーン内の、ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＯＨの一部の領域Ａに関し、前記領域Ａに対応した送信ベクトルを同一パリティレーン内のＯＨ領域Ｂに格納し、前記領域ＡにはＩＴＵ−Ｔ  Ｇ．７０９に準拠した値を格納し、前記復号化器は、前記異常を検出したシンボルレーンに含まれる前記ＯＰＵ／ＯＤＵペイロードを復元する際、前記領域Ａの復元に各パリティレーンにおける前記ＯＨ領域Ｂの情報を用いるようにしてもよい。【００２８】
本発明の並列データ符号復号化システムでは、前記領域Ａは、ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＭＦＡＳおよびＰＳＩを少なくとも含み、前記符号化器は、前記ＭＦＡＳを用いたマルチフレーム転送により、前記領域Ａ及び前記ＯＨ領域Ｂのフレーム内位置の情報を送信し、前記復号化器は、前記異常を検出したシンボルレーンに含まれる前記ＯＰＵ／ＯＤＵペイロードを復元する際に前記フレーム内位置の情報を用いるようにしてもよい。【００２９】
本発明の並列データ符号復号化システムでは、被伝送パケットをあらかじめ決められた長さを単位に分割し、もしくは、前記被伝送パケットを一定時間毎にタイムスロット単位に分割し、さらに同一タイムスロット内の前記被伝送パケットを前記符号化器の入力並列数と同数の系統に分配・分割し、分配・分割されたパケットを前記符号化器へ入力するパケット入力部と、前記符号化器の出力に対して、論理レーン毎にレーンおよびタイムスロットを識別分離可能なカプセル化を行い、１以上の伝送媒体にカプセル化パケットを出力する符号化パケット出力部と、カプセル化情報に基づいて、前記伝送媒体により伝送された前記カプセル化パケットを論理レーン毎に分離し、各レーンにおいて、分離されたカプセル化パケットをタイムスロット毎に整列し、分離・整列されたカプセル化パケットを前記復号化器へ入力する符号化パケット入力部と、前記復号化器の出力から前記被伝送パケットを再構成して前記被伝送パケットを出力するパケット出力部とをさらに備えるようにしてもよい。【００３０】
本発明の並列データ符号復号化システムでは、前記パケット入力部は、パケットが存在しない論理レーンの数を最大化するように前記符号化器へ入力される前記パケットの分配を最適化するようにしてもよい。【００３１】
本発明の並列データ符号復号化システムでは、前記パケット入力部は、前記被伝送パケットのパケット長が１タイムスロットのデータ長よりも大きい場合に、前記被伝送パケットを前記１タイムスロットのデータ長以下の長さを持つパケットに分割し、分割された前記パケットを複数のレーンへ分配するようにしてもよい。【００３２】
本発明の並列データ符号復号化システムでは、前記パケット入力部は、パケットが存在しないレーンの数が少なくとも最少冗長度ｒｍｉｎとなるように、パケットを割り当てようとしているタイムスロットとは異なる他のタイムスロットに前記パケットを割り当て、前記符号化パケット出力部は、前記符号化器から出力されるパケットのうち冗長パケットの個数を高々最大冗長度ｒｍａｘに制限するようにしてもよい。【００３３】
なお、上記本発明の各態様は、可能な限り組み合わせることができる。
【発明の効果】
【００３４】
本発明によれば、冗長度の動的な設定により、縮退動作時にも消失訂正が可能になる。また、情報伝達に供しない帯域（物理帯域−情報帯域）を冗長化に用いることで、必要とする並列媒体を削減することが可能になる。【００３５】
また、本発明の符号化方式はＭＤＳ符号をベースに構成されている。本方式における符号長は並列媒体数に等しく、現実的には多くても数十のオーダーであり、ＭＤＳ符号で十分計算可能な範囲である。符号長（ブロック長）が同じ場合、ＭＤＳ符号の消失訂正能力はＬＤＰＣ（Low Density Parity Check）符号の消失訂正能力よりも高い。また、ブロック内の消失数が分かった場合に訂正可能であるかどうかに関しては、ＭＤＳ符号は確定的保障であるのに対してＬＤＰＣは確率的（期待値的）保障である。したがって、ＬＤＰＣはロバスト性向上の用途には不向きである。【００３６】
また、本発明によれば、変動レートもしくはバースト到着のパケット入力に対しても、過剰な遅延を発生させずにパケット冗長化によるパケット消失訂正を行うことができる。
【図面の簡単な説明】
【００３７】
【図１】本発明の第一の実施形態に係る並列データ符号復号化システムの一例を示す。
【図２】並列データ符号器の構成の一例を示す。
【図３】並列データ復号器の構成の一例を示す。
【図４】符号化データのパケット化の一例を示す。
【図５】パケットフォーマットの一例を示す。
【図６】可変冗長符号化の一例を示す。
【図７】本発明の第五の実施形態に係る並列データ符号復号化システムの一例を示すブロック図である
【図８】本発明の第六の実施形態に係る並列データ符号復号化システムの一例を示すブロック図である。
【図９】ＯＴＮマルチレーンの送信端における符号化部の構成を示す。
【図１０】ＯＴＮマルチレーンの受信端における復号化部の構成を示す。
【図１１】符号化器におけるフレーム処理手順を示すフローチャートである。
【図１２】復号化器におけるフレーム処理手順を示すフローチャートである。
【図１３】標準のＯＴＮフレームをペイロードタイプとして定義する場合のＯＴＮフレームの一例を示す。
【図１４】パリティフレームをペイロードタイプとして定義する場合のＯＴＮフレームの一例を示す。
【図１５】本発明の第十の実施形態に係る冗長伝送システムの構成を示すブロック図である
【図１６】パケット入力部におけるタイムスロット内のパケットの分配・分割に関する方法の具体例を示す。
【図１７】パケット出力部におけるパケットの結合に関する方法の具体例を示す。
【図１８】本発明の第十二の実施形態によるパケット冗長伝送システムの機能ブロック図を示す。
【図１９】同実施形態による送信器によるパケット出力手順を説明するための図である。
【図２０】同実施形態による受信器によるパケット復号化手順を説明するための図である。
【図２１】第十四の実施形態による入力バッファへの被伝送パケットの収容例を示す図である。
【図２２】第十五の実施形態による被伝送パケットが任意長である場合のパケット冗長伝送システムの動作を説明するための図である。
【図２３】第十六の実施形態による最小冗長数ｒｍｉｎ、最大冗長数ｒｍａｘを設定したときのパケット冗長伝送システムの動作を説明するための図である。
【図２４】第十七の実施形態による最小冗長数ｒｍｉｎを入力パケットによって決定する場合の送信器の動作について説明するための図である。
【図２５】第十八の実施形態によるパケット冗長伝送システムの再送制御のシーケンス図である。
【図２６】第十九の実施形態による複数経路を用いた冗長パケット伝送を説明するための図である。
【図２７】第二十の実施形態によるパケット冗長伝送システムの接続構成を示す図である。
【発明を実施するための形態】
【００３８】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施の例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００３９】
（基本原理）
以下、本発明の第一〜第十一の実施形態の基本原理について説明する。
本発明の第一〜第十一の実施形態では並列データ伝送を例として用いるが、本発明は物理媒体としてハードディスクやメモリを用いた場合でも同様の方式が適用可能である。
【００４０】
並列データ伝送における並列レーン数をＲとした場合、任意の時刻におけるＲレーンのシンボルを１データブロックとして扱う。この時、レーン毎にシンボルの有効・無効を示す情報である状態ベクトルＵも符号化に用いる。例えば、ＯＴＮ（Optical Transport Network）においてはＰＴ（Ｐａｙｌｏａｄ  Ｔｙｐｅ）をみてＯＰＵ／ＯＤＵ（Optical Payload Unit/Optical Data Unit）がＮｕｌｌクライアントであれば無効を示し、それ以外のクライアント信号であれば有効を示すものとする。また、Ｅｔｈｅｒｎｅｔ（登録商標）においてはＰＣＳ（Physical Coding Sublayer）層においてアイドル信号であれば無効を示し、ＭＡＣ（Medium Access Control）フレームであれば有効を示すものとする。
【００４１】
本発明においては短縮リードソロモン符号（例えば、非特許文献１及び２参照。）やＣａｕｃｈｙリードソロモン符号（例えば、非特許文献３参照。）などＭＤＳ符号（例えば、非特許文献４参照。）に属するＲシンボル消失訂正可能な（２Ｒ，Ｒ）ブロック符号を用いる。すなわち、データ長とパリティ長が等しくなるような符号化を行う。また、符号化の際に無効なシンボルは既定の値（通常は０）とする。ここで、無効なシンボルは、例えば、ＩＤＬＥ又はＮＵＬＬクライアントに対応するレーンのデータである。
【００４２】
符号化率０．５における一般的な冗長伝送では組織化符号としてデータとパリティの２Ｒシンボルの情報を送信するが、本発明においてはＲシンボルの情報と状態ベクトルＵを送信するのが特徴である。
【００４３】
ここで、状態ベクトルＵは符号化されたデータと一緒に送っても、別経路で送っても構わないし、また、値が変化したときのみ送出しても構わない。
【００４４】
（１）短縮符号shortenedＲＳ（２Ｒ，Ｒ）のパリティＳをＲシンボルの情報として送信する場合
Ｒシンボルの符号ベクトルＭ、Ｍの各要素の有効（＝１）・無効（＝０）を示すＲビットの状態ベクトルをＵ、生成多項式ｇ（Ｘ）に対するリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるパリティ生成行列をＡとした場合、パリティＳは式（１）で表される。
【数２１】
2014045906.tif 000023
【数２２】
2014045906.tif 000024
なお、ｋは０以上の整数であり、ＧＦ（２ｎ）はガロア体のｎ次拡大体であり、αｉはＧＦ（２ｎ）の非零元である。
【００４５】
受信ベクトルＹ’、および送受信区間での送信ベクトルＹの各要素の消失（＝１）・受信（＝０）を示す消失ベクトルＥを用いて書き直すと、式（１）は式（２）で表される。
【数２３】
2014045906.tif 000025
【００４６】
すべての要素はガロア体であるので
【数２４】
2014045906.tif 000026
が成立する。
【００４７】
ここで、受信ベクトルＹ’は、任意の時刻に各レーンで受信した情報そのものである。受信側において既知の情報である受信ベクトルＹ’、状態ベクトルＵ、消失ベクトルＥ及びパリティ生成行列Ａから、符号ベクトルＭの有効な要素からなる部分集合
【数２５】
2014045906.tif 000027
を求めることが目的である。
【００４８】
(ｉ)｜Ｍｓｕｂ｜＋｜Ｓｓｕｂ｜＝Ｒの場合
符号ベクトルＭの部分集合Ｍｓｕｂ、伝送で消失したパリティＳの部分集合Ｓｓｕｂを用いて、符号化行列Ａ、単位行列Ｉの行を置換して整理すると、
【数２６】
2014045906.tif 000028
で表す事が出来る。ただし、Ａ’およびＩ’はＡおよびＩをそれぞれ行置換して得られた行列である。また、
【数２７】
2014045906.tif 000029
である。
【００４９】
【数２８】
2014045906.tif 000030
となる行列Ｂを求め、その逆行列Ｂ−１を用いて
【数２９】
2014045906.tif 000031
を解くことにより、部分集合Ｍｓｕｂを得る事が出来る。
【００５０】
(ｉｉ)｜Ｍｓｕｂ｜＋｜Ｓｓｕｂ｜＜Ｒの場合
【数３０】
2014045906.tif 000032
とおくと、Ｙ’の部分ベクトル
【数３１】
2014045906.tif 000033
に対応した、符号化行列Ａのｒ×ｒ部分行列Ａｓｕｂ、ｒ×ｒ単位行列Ｉｒに関して(ｉ)と同様の手順により、部分集合Ｍｓｕｂを得る事が出来る。
【００５１】
(ｉｉｉ)｜Ｍｓｕｂ｜＋｜Ｓｓｕｂ｜＞Ｒの場合
【数３２】
2014045906.tif 000034
となり、部分集合Ｍｓｕｂを得る事は出来ない。
【００５２】
上記(ｉ),(ｉｉ),(ｉｉｉ)から、符号ベクトルＭの無効な要素数は
【数３３】
2014045906.tif 000035
であるので、
【数３４】
2014045906.tif 000036
すなわち、消失した要素数が符号ベクトルＭの無効な要素数以下であれば、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復元する事が可能である。
【００５３】
（２）短縮符号shortenedＲＳ（２Ｒ，Ｒ）の剰余多項式の係数ベクトルＰをＲシンボルの情報として送信する場合
係数ベクトルＰとパリティＳにはヴァンデルモンド行列（例えば、非特許文献５参照。）Ｖを用いると、Ｓ＝ＰＶの関係がある。これを式（１）に代入すると、
【数３５】
2014045906.tif 000037
となり、受信ベクトルＹ’、消失ベクトルＥを用いて書き直すと
【数３６】
2014045906.tif 000038
となる。
【００５４】
すべての要素はガロア体であるので
【数３７】
2014045906.tif 000039
が成立する。
式（４）に関して（１）と同様の手法により符号ベクトルＭの部分集合Ｍｓｕｂを求める事が出来る。
【００５５】
（３）Ｒ×ＲのＣａｕｃｈｙリードソロモン符号を用いる場合
（１）におけるパリティ生成行列ＡをＣａｕｃｈｙ行列ＣＲ×Ｒに変更する以外、（１）と同様の手法で符号ベクトルＭの部分集合Ｍｓｕｂを求める事が出来る。
【００５６】
なお、Ｃａｕｃｈｙ行列ＣＲ×Ｒは次のように表される。
【数３８】
2014045906.tif 000040
【００５７】
（４）ＭＤＳ符号を用いる場合
Ｒシンボルの消失訂正能力を持つ符号化率０．５のＭＤＳ（ｍａｘｉｍｕｍ−ｄｉｓｔａｎｃｅ−ｓｅｐａｒａｂｌｅ）符号の生成行列をＧ＝｛ＩＲ｜ＰＲ｝とした場合、（１）におけるパリティ生成行列ＡをＭＤＳ符号生成行列のＰＲに変更する以外、（１）と同様の手法で符号ベクトルＭの部分集合Ｍｓｕｂを求める事が出来る。
【００５８】
（５）符号ベクトルＭの有効な要素と、符号ベクトルＭの無効な要素数個の短縮符号shortenedＲＳ（２Ｒ，Ｒ）のパリティＳを送信する場合
式（１）より、
【数３９】
2014045906.tif 000041
が成立する。さらに、送信ベクトルＹを用いて書き直すと、
【数４０】
2014045906.tif 000042
ここで、行列Ｄは、行列Ａのｕｊ＝１に対応する行と、行列Ｉのｕｊ＝０に対応する行から構成される。さらに受信ベクトルＹ’、消失ベクトルＥを用いて書き直すと
【数４１】
2014045906.tif 000043
となる。すべての要素はガロア体であるので
【数４２】
2014045906.tif 000044
が成立する。
【００５９】
式（５）に関して（１）と同様の手法により、消失した送信ベクトルの要素が求まる。送信ベクトルには符号ベクトルＭの有効な要素がすべて含まれるため、受信ベクトルＹ’に含まれる符号ベクトルＭ要素と合わせると、部分集合Ｍｓｕｂが得られる。
（２）、（３）において符号ベクトルＭの有効な要素を送信する場合に関しても同様の手法で符号ベクトルＭの部分集合Ｍｓｕｂを求めることが可能である。
【００６０】
本発明の第一〜第十一の実施形態において、「Ｒシンボルのパリティを送る」もしくは「有効データとパリティの組み合わせを送る」ことによって、以下の作用・効果を奏する。Ｒシンボル消失訂正可能な符号化率０．５のＭＤＳ符号は通常ＲシンボルのデータとＲシンボルのパリティを送るが、Ｒシンボル訂正可能なので伝送における消失が無ければＲシンボルのパリティのみを送っても（Ｒシンボルのデータが消失したと考えれば良い）、受信側で元のＲシンボルのデータを復元する事が可能である。元のＲシンボルのデータの中に既知のシンボルがある場合、その既知のシンボルの個数だけ伝送したパリティが消失しても、残りの未知のデータのシンボルを復元することができる。ＩＤＬＥやＮＵＬＬクライアントなどのレーンデータを０としてエンコードしてＲシンボルのパリティを送出し、また、０の位置
【数４３】
2014045906.tif 000045
を受信側に伝えることで上記の手法によりＩＤＬＥやＮＵＬＬクライアントのレーン数だけ送信パリティが消失しても、有効なデータが復元できる、即ち消失訂正が可能になる。
【００６１】
（第一の実施形態）
図１は本実施形態に係る並列データ符号化復号化方式の基本的な構成を示している。符号化器１０１で複数レーンの入力並列データ１０８の符号化を行い、並列データを入出力する並列媒体１０２への送信情報Ｙ（ｔ）１１２とする。復号化器１０３では元の入力レーンの使用状況を示すＲビットの状態ベクトルＵ（ｔ）１１０と並列媒体１０２から受信した受信情報ベクトルＹ’（ｔ）１１３、消失もしくは修正不能な誤りを示すＲビットの消失ベクトルＥ（ｔ）１１５から元の並列データを再生し、出力並列データ１０９とする。
【００６２】
ここで、消失ベクトルＥ（ｔ）１１５は、物理レベル又は論理レベルの消失である。物理レベルであれば、例えば、光パワー断による消失や、クロック同期が取れない場合の該当リンクを用いた伝送による消失である。論理レベルであれば、例えば、イーサネット（登録商標）であればＦＣＳ（Frame Check Sequence）を再計算して違っていれば該当フレームは消失となるし、ＯＴＮであればＢＩＰ（Bit Interleaved Parity）を再計算して違っていれば該当フレームは消失となるし、伝送ＦＥＣで訂正不能な誤りを検出したときに該当フレームを消失としてもよい。
【００６３】
符号化器１０１ではデフレーマ１０４によって、入力並列データ１０８における有効な入力フレームに含まれるデータからなるＲシンボルのベクトルＭ（ｔ）１１１と入力レーンの使用状況を示す状態ベクトルＵ（ｔ）１１０を生成する。ここで、ベクトルＭ（ｔ）１１１の無効な要素は０とする。並列レーン数をＲとすると、ＭＤＳ符号化演算器１０５では、リードソロモン符号やＣａｕｃｈｙリードソロモン符号などのＲシンボルの消失訂正能力を持つ符号化率０．５のＭＤＳ符号の生成行列Ｇ＝｛ＩＲ｜ＡＲ｝を用いてパリティＳ（ｔ）＝Ｍ（ｔ）ＡＲを計算し、並列媒体１０２への送信情報Ｙ（ｔ）１１２とする。
【００６４】
並列媒体１０２は伝送線路、メモリ、ハードディスクなど時系列の情報を蓄え、時系列順に情報を取り出せるものであればどのようなものでも構わない。並列媒体１０２において情報を取り出す際にレーン毎に情報の消失もしくは修復不能な誤りを示す消失ベクトルＥ（ｔ）１１５を得る機構を持つ。ここで、並列媒体１０２からの受信情報ベクトルＹ’（ｔ）１１３において、消失もしくは修復不可能な誤りがある要素は０とする。
【００６５】
ここで、Ｙ’（ｔ）１１３は、任意の時刻に各レーンで受信したＲ個のシンボルの要素からなるベクトルである。消失したレーンのシンボルは０とする。送信ベクトルＹと受信ベクトルＹ’の関係は次のようになっている。
【数４４】
2014045906.tif 000046
【００６６】
復号化器１０３ではＭＤＳ復号化演算器１０６において、ガロア体連立一次方程式
【数４５】
2014045906.tif 000047
を解くことでベクトルＭｓｕｂ（ｔ）１１４を再生する。なお、図中ではＭｓｕｂ（ｔ）はＭ’（ｔ）と記載されている。
フレーマ１０７ではベクトルＭｓｕｂ（ｔ）１１４及び状態ベクトルＵ（ｔ）１１０から、フレームを再構築して出力並列データ１０９とする。
【００６７】
（第二の実施形態）
図２及び図３はそれぞれ並列データ符号器および復号器の別の形態を示している。
図２の並列データ符号器構成において、図１の並列データ符号器との差分は、セレクタ１２１を用いて入力並列データ１０８の有効なシンボルはそのまま送信し、無効なシンボルはＭＤＳ符号化演算器１０５の出力するパリティＳ（ｔ）１２０の対応するシンボルに置換して、送信情報Ｙ（ｔ）１１２として送信することである。
【００６８】
図３の並列データ復号器構成において、図１の並列データ復号器との差分は、ＭＤＳ復号化演算器１２２において、行列ＡＲのｕｊ＝１，ｕｊ∈Ｕに対応する行と、単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＢＲを用いて、次式のガロア体連立一次方程式を解くことでベクトルＭｓｕｂ（ｔ）１１４を再生することである。
【数４６】
2014045906.tif 000048
【００６９】
第二の実施形態においては入力並列データ１０８の有効なシンボルはそのまま並列媒体１０２に蓄えられるため、情報の消失もしくは修復不可能な誤りが無い場合にはＭＤＳ復号化演算器１２２において連立一次方程式を解くことなく、ベクトルＭｓｕｂ（ｔ）１１４を再生出来ることが特徴である。
【００７０】
（第三の実施形態）
図４は第一ないし第二の実施形態における並列媒体１０２への入出力にパケットを用いる形態を示している。図５はパケットフォーマットの一例を示している。
パケット化機能部１３０では符号化された送信情報Ｙ（ｔ）１１２と入力並列データの有効無効を示す状態ベクトルＵ（ｔ）１１０が入力されると、レーン毎にパケット化を行う。ｋ番目のレーンのパケットはＵ（ｔ）１１０、Ｙ（ｔ）１１２のｋ番目の要素ｙｋ（ｔ）及び誤り検出／訂正符号１３５から構成される。このようにして生成されたパケット１３４は並列媒体１０２にＷｐ（ｔ）１３２として送信される。
【００７１】
受信側の逆パケット化機能部１３１では並列媒体１０２からＲｐ（ｔ）１３３として受信したパケットの誤り検出／訂正符号１３５による検査を行い、誤りが無い場合は受信したＲｐ（ｔ）１３３のシンボルはそのままＹ’（ｔ）１１３の要素とする。また、逆パケット化機能部１３１は、訂正可能な誤りがあった場合には訂正後のシンボルをＹ’（ｔ）１１３の要素とし、訂正不能な誤りがあった場合には修復不可能な誤りを示す消失ベクトルＥ（ｔ）１１５の該当ビットを１とし、Ｙ’（ｔ）１１３の該当シンボルを０にする。復号化器１０３は、Ｙ’（ｔ）１１３、Ｕ（ｔ）１１０、Ｅ（ｔ）１１５を用いてガロア体連立一次方程式を解くことにより、入力並列データ１０８の有効なシンボルＭｓｕｂ（ｔ）１１４を再生する事が出来る。
【００７２】
第三の実施形態においてはパケットに親和性のある並列媒体１０２への適用が容易な事と、ＭＤＳ符号化演算器１０５とＭＤＳ復号化演算器１２２間におけるＹ（ｔ）１１２、Ｕ（ｔ）１１０、Ｅ（ｔ）１１５の伝達・生成が、すべて並列媒体１０２を介して行う事が出来るのが特徴である。
【００７３】
（第四の実施形態）
図６は冗長度を動的に可変にする場合の符号化器１０１の構成を示す。
符号化器１０１ではデフレーマ１０４によって、入力並列データ１０８における有効な入力フレームに含まれるデータを抽出しＦＩＦＯ（First-In First-Out）バッファ１４０に入力する。
【００７４】
シェーパ制御回路１４１はＦＩＦＯ使用率１４３が一定値を超えず、且つ、冗長度の下限設定すなわち、伝送における訂正可能な消失シンボル数の保証値ｒｍｉｎ１４４を用いて、｜Ｕ（ｔ）｜≦Ｒ−ｒｍｉｎを満たすように読み出しシンボル数に制限をかける。例えば、次式で表されるＲビットの読み出し信号Ｆを生成する。
【数４７】
2014045906.tif 000049
ここで、レーン毎に優先度が設定されている場合には、より優先度の高いレーンの読み出し信号を１にしてもよい。
【００７５】
ポリシング制御回路１４２は冗長度の上限設定、すなわち伝送における訂正可能な消失シンボル数の制限値ｒｍａｘ１４５を用いて、
【数４８】
2014045906.tif 000050
となるように誤りを示す消失ベクトルＥ（ｔ）１１５を生成する。
【００７６】
セレクタ１２１は、各Ｅ（ｔ）１１５の要素ビットが０の場合は符号化された情報であるパリティＳ（ｔ）１２０の要素シンボルを情報ベクトルＹ（ｔ）１１２として送信し、各Ｅ（ｔ）１１５の要素ビットが１の場合は０を情報ベクトルＹ（ｔ）１１２として送信する。これにより、セレクタ１２１は、送信ベクトルＹのうち次式で表される個数のシンボルを選択することができる。
【数４９】
2014045906.tif 000051
【００７７】
復号化器（不図示）は、非選択シンボルおよび伝送における消失シンボルに関して消失訂正を行う。
【００７８】
なお、Ｅ（ｔ）１１５の要素ビットが１の情報ベクトルＹ（ｔ）１１２の要素は、並列媒体１０２に送信しなくても良いし、前記要素ビットに対応する並列媒体１０２の一部を低消費電力モードへ移行させ、もしくは供給電力を停止させ、もしくは物理的に排除しても構わない。物理的排除では、例えば、ファイバや電線を抜いたり、ＩＦ（インタフェース）カード／モジュールを抜いたりする。
【００７９】
第四の実施形態においては冗長度の下限設定ｒｍｉｎ１４４とＦＩＦＯバッファ１４０による平滑化の効果により、最小冗長度の保証を行う事が可能になり、上限設定ｒｍａｘ１４５とセレクタ１２１による情報の縮退化により転送情報量が少ない場合の過剰な冗長度を抑制し、並列媒体の使用数もしくは電力の削減効果を持つのが特徴である。本実施形態に係る発明によれば、冗長度の種類だけ回路を用意する必要がなく、故障した通信路の数がｒｍｉｎ以下の場合には全体が断になることがない。
【００８０】
（第五の実施形態）
図７は、本実施形態に係る並列データ符号復号化システムの一例を示すブロック図である。本実施形態では、図１に示すシステムにおける符号化器１０１および復号化器１０３がそれぞれＦＩＦＯ付符号化器５１０およびＦＩＦＯ付復号化器５３０で置き換えられている。本実施形態では、ＦＩＦＯ付符号化器５１０とＦＩＦＯ付復号化器５３０を結ぶ複数のレーンがＲ本の論理レーンからなる並列バスであり、デフレーマ１０４とＭＤＳ符号化演算器１０５の間に入力ＦＩＦＯ５４５が挿入され、ＭＤＳ復号化演算器１０６とフレーマ１０７の間に出力ＦＩＦＯ５６７が挿入されている。
【００８１】
並列バスへの入力Ｄｉｎは、デフレーマ１０４によって要素毎独立の入力ＦＩＦＯ５４５に書き込まれる。
【数５０】
2014045906.tif 000052
【００８２】
入力ＦＩＦＯ５４５の制御回路は、各要素が１シンボルの読み出し及び読み出し停止をそれぞれ「１」及び「０」で示すＲビットの読み出し信号Ｆを生成する。
【数５１】
2014045906.tif 000053
【００８３】
ここで、レーン毎に優先度が設定されている場合には、より優先度の高いレーンの読み出し信号を１にしてもよい。
そして、入力ＦＩＦＯ５４５の出力をＲシンボルのベクトルＭ（ｔ）１１１に用い、読み出し信号Ｆを状態ベクトルＵ（ｔ）１１０に用いる。
【００８４】
ＭＤＳ復号化演算器１０６により得られた部分集合Ｍｓｕｂは、要素毎独立の出力ＦＩＦＯ５６７に書き込まれる。
【数５２】
2014045906.tif 000054
【００８５】
そして、出力ＦＩＦＯ５６７の出力を、Ｒシンボルの並列バスへの出力Ｄｏｕｔとして読み出す。
【数５３】
2014045906.tif 000055
【００８６】
（第六の実施形態）
図８は、本実施形態に係る並列データ符号復号化システムの一例を示すブロック図である。本実施形態では、図４に示すシステムにおける符号化器１０１および復号化器１０３がそれぞれ図７に示したＦＩＦＯ付符号化器５１０およびＦＩＦＯ付復号化器５３０で置き換えられている。本実施形態では、パケット化機能部１３０と逆パケット化機能部１３１がＲ本の論理レーンを用いた並列パケット伝送を行う。
【００８７】
入力並列データ１０８は論理レーン毎に独立の入力ＦＩＦＯ５４５（図７参照）に書き込まれる。入力ＦＩＦＯ５４５は、各要素が１シンボルの読み出し及び読み出し停止をそれぞれ「１」及び「０」で示すＲビットの読み出し信号Ｆを生成する。
【数５４】
2014045906.tif 000056
【００８８】
ここで、レーン毎に優先度が設定されている場合には、より優先度の高いレーンの読み出し信号を１にしてもよい。
そして、入力ＦＩＦＯ５４５の出力をＲシンボルのベクトルＭ（ｔ）１１１に用い、読み出し信号Ｆを状態ベクトルＵ（ｔ）１１０に用いる。
【００８９】
ＭＤＳ復号化演算器１０６により得られた部分集合Ｍｓｕｂは、論理レーン毎独立の出力ＦＩＦＯ５６７に書き込まれる。
【数５５】
2014045906.tif 000057
【００９０】
そして、出力ＦＩＦＯ５６７から論理レーン毎にパケットを読み出す。
【００９１】
（第七の実施形態）
本実施形態では、符号化器１０１における符号化方法と復号化器１０３における復号化方法の具体例について説明する。
第１の方法について説明する。
符号化器１０１は、Ｒシンボルの符号ベクトルＭ及びＲビットの状態ベクトルＵの要素同士の積に対し、Ｒシンボルの消失訂正能力を持つ符号化率０．５のＭＤＳ符号の生成行列Ｇを用いてパリティＳを計算し、パリティＳで定義される送信ベクトルＹと共に状態ベクトルＵを送信する。
復号化器１０３は、受信ベクトルＹ’、状態ベクトルＵ、消失ベクトルＥを用いて、式（Ｅ１）を解くことにより、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号し、消失訂正を行う。
【数５６】
2014045906.tif 000058
ただし、
【数５７】
2014045906.tif 000059
【００９２】
第２の方法について説明する。
符号化器１０１は、Ｒシンボルの符号ベクトルＭ並びにＲビットの状態ベクトルＵの要素同士の積に対し、Ｒシンボルの消失訂正能力を持つ符号化率０．５のＭＤＳ符号の生成行列Ｇを用いてパリティＳを計算し、符号ベクトルＭ及び状態ベクトルＵ及びパリティＳで定義される送信ベクトルＹと共に状態ベクトルＵを送信する。
復号化器１０３は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、送受信区間での送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びに行列ＡＲのｕｊ＝１，ｕｊ∈Ｕに対応する行と単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＢＲ（Ｕ）を用いて、式（Ｅ２）を解くことにより、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号し、消失訂正を行う。
【数５８】
2014045906.tif 000060
ただし、
【数５９】
2014045906.tif 000061
【００９３】
第３の方法について説明する。
符号化器１０１は、Ｒシンボルの符号ベクトルＭ、各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵ並びにＧＦ（２ｎ）の要素からなるＲ行Ｒ列のＣａｕｃｈｙ行列ＣＲ×Ｒを用いて、パリティＳを計算し、パリティＳで定義される送信ベクトルＹと共に状態ベクトルＵを送信する。
復号化器１０３は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに送受信区間での送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥを用いて、式（Ｅ３）を解くことにより、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号し、消失訂正を行う。
【数６０】
2014045906.tif 000062
ただし、
【数６１】
2014045906.tif 000063
【００９４】
第４の方法について説明する。
符号化器１０１は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵ並びにＧＦ（２ｎ）の要素からなるＲ行Ｒ列のＣａｕｃｈｙ行列ＣＲ×Ｒを用いて、パリティＳを計算し、符号ベクトルＭ及び状態ベクトルＵ及びパリティＳで定義される送信ベクトルＹと共に状態ベクトルＵを送信する。
復号化器１０３は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、送受信区間での送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びにＣＲ×Ｒのｕｊ＝１，ｕｊ∈Ｕに対応する行と単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＤＲ（Ｕ）を用いて、式（Ｅ４）を解くことにより、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号し、消失訂正を行う。
【数６２】
2014045906.tif 000064
ただし、
【数６３】
2014045906.tif 000065
【００９５】
第５の方法について説明する。
符号化器１０１は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰを計算し、Ｐで定義される送信ベクトルＹと共に状態ベクトルＵを送信する。
復号化器１０３は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、送受信区間での送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ、ヴァンデルモンド行列ＶＲ（ｋ）並びにヴァンデルモンド行列ＷＲ（ｋ）を用いて、式（Ｅ５）を解くことにより、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号し、消失訂正を行う。
【数６４】
2014045906.tif 000066
ただし、
【数６５】
2014045906.tif 000067
【００９６】
第６の方法について説明する。
符号化器１０１は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰを計算し、符号ベクトルＭ及び状態ベクトルＵ及び係数ベクトルＰで定義される送信ベクトルＹと共に状態ベクトルＵを送信する。
復号化器１０３は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ、送受信区間での送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びにヴァンデルモンド行列ＷＲ（ｋ）のｕｊ＝１，ｕｊ∈Ｕに対応する行列及びヴァンデルモンド行列ＶＲ（ｋ）のｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＺＲ（Ｕ）を用い、式（Ｅ６）を解くことにより、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号し、消失訂正を行う。
【数６６】
2014045906.tif 000068
ただし、
【数６７】
2014045906.tif 000069
【００９７】
第７の方法について説明する。
符号化器１０１は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰ、ヴァンデルモンド行列ＶＲ（ｋ）、ヴァンデルモンド行列ＷＲ（ｋ）並びにパリティＳを計算し、パリティＳで定義される送信ベクトルＹと共に状態ベクトルＵを送信する。
復号化器１０３は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに送受信区間での送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥを用いて、式（Ｅ７）を解くことにより、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号し、消失訂正を行う。
【数６８】
2014045906.tif 000070
ただし、
【数６９】
2014045906.tif 000071
【００９８】
第８の方法について説明する。
符号化器１０１は、Ｒシンボルの符号ベクトルＭ並びに各要素の有効及び無効をそれぞれ符号「１」及び「０」で示すＲビットの状態ベクトルＵの要素同士の積に対し、生成多項式ｇ（Ｘ）におけるリードソロモン符号ＲＳ（Ｎ，Ｋ）；Ｒの短縮符号shortenedＲＳ（２Ｒ，Ｒ）におけるＲシンボルの剰余多項式の係数ベクトルＰ、ヴァンデルモンド行列ＶＲ（ｋ）、ヴァンデルモンド行列ＷＲ（ｋ）並びにパリティＳを計算し、符号ベクトルＭ及び状態ベクトルＵ及びパリティＳで定義される送信ベクトルＹと共に状態ベクトルＵを送信する。
復号化器１０３は、受信した受信ベクトルＹ’、受信した状態ベクトルＵ並びに送受信区間での送信ベクトルＹの各要素の消失及び受信をそれぞれ符号「１」及び「０」で示す消失ベクトルＥ並びにヴァンデルモンド行列ＷＲ（ｋ）のｕｊ＝１，ｕｊ∈Ｕに対応する行列及び単位行列Ｉのｕｊ＝０，ｕｊ∈Ｕに対応する行から構成される行列ＺＲ’（Ｕ）を用いて、式（Ｅ８）を解くことにより、符号ベクトルＭの有効な要素からなる部分集合Ｍｓｕｂを復号し、消失訂正を行う。
【数７０】
2014045906.tif 000072
ただし、
【数７１】
2014045906.tif 000073
【００９９】
（第八の実施形態）
本実施形態はＯＴＮのマルチレーン伝送に本発明の符号化方式を適用する一例を示す。図９および図１０はそれぞれ、ＯＴＮマルチレーンの送信端における符号化部および受信端における復号化部の構成を示す。本実施形態ではレーン数が６レーンの場合を示すが、２以上の任意のレーン数でも構わない。
【０１００】
図９において、ＯＴＮ対応の符号化器２００は６レーンのＯＴＮ入力２０１から被符号化フレームを入力し、６レーンのＯＴＮ出力２０２から符号化フレームを出力する。各ＯＴＮ入力２０１にはＯＴＮフレーム２１０を入力するか、もしくは、無効信号２１１とする。ＯＴＮフレーム２１０は、ＦＡＳ（Frame Alignment Signal）信号２１３、ＦＥＣ情報２１４、および、領域２１５から構成される。符号化器２００では、ＯＴＮ入力２０１にＯＴＮフレーム２１０が入力された場合には対応するＯＴＮ出力２０２からそのままＯＴＮフレーム２１０がスルーで出力される。一方、無効信号２１１のＯＴＮ入力２０１に対応するＯＴＮ出力２０２からはＯＴＮに準拠したパリティフレーム２１２が出力される。パリティフレーム２１２はＦＡＳ信号２１３、ＦＥＣ情報２１４、および、パリティ２１６から構成される。
【０１０１】
図１０において、ＯＴＮ対応の復号化器２２０は６レーンのＯＴＮ入力２２１から符号化フレームを入力し、６レーンのＯＴＮ出力２２２から元のＯＴＮフレームを出力する。各ＯＴＮ入力２２１にはＯＴＮフレーム２１０またはパリティフレーム２１２が入力されるか、もしくは、障害等の理由により正常なフレームが受信されなかった場合には無効信号２１１とする。また、ＦＥＣ情報２１４で修正できなかった情報２１７をフレーム中に含む場合には該当フレームを無効信号２１１として扱っても良い。復号化器２２０では、無効信号２１１であったレーンの情報を正常に受信したＯＴＮフレーム２１０またはパリティフレーム２１２から復号し、送信端における各ＯＴＮ入力２０１を再生し、再生された各ＯＴＮ入力２０１を出力する。
【０１０２】
図１１および図１２はそれぞれ符号化器２００および復号化器２２０におけるフレーム処理手順を示すフローチャートである。
【０１０３】
図１１を参照して符号化器２００におけるフレーム処理手順について説明する。符号化器２００は、各レーンのＯＴＮフレーム２１０もしくは無効信号２１１の入力状況の情報から、リードソロモン符号やＣａｕｃｈｙリードソロモン符号などの符号化率０．５のＭＤＳ符号を構成する符号化行列Ａを生成する（ステップＳ１）。符号化器２００は、各レーンのすべてのフレーム情報（列，行）に対して、以下の処理を実行する（ステップＳ２）。符号化器２００は、フレーム情報（列，行）内の領域がＦＡＳ信号２１３またはＦＥＣ情報２１４（ＦＡＳもしくはＦＥＣ領域）であるか否かを判断する（ステップＳ３）。符号化器２００は、ＦＡＳもしくはＦＥＣ領域（ステップＳ３の判断結果がＹｅｓ）に関しては、ＯＴＮ標準仕様に従って情報を生成する（ステップＳ４）。それ以外のフレーム情報（列，行）の領域２１５（ステップＳ３の判断結果がＮｏ）に関しては、符号化器２００は、有効なＯＴＮフレーム２１０入力のフレーム情報（列，行）もしくは０（無効信号２１１入力の場合）からなるベクトルｘと、符号化行列Ａの積を計算し、積ｘＡをパリティベクトルｐとする（ステップＳ５）。符号化器２００は、有効なＯＴＮフレーム２１０入力に対応したＯＴＮ出力２０２については元のフレーム情報（列，行）をベクトルｙとし、無効信号２１１入力に対応したＯＴＮ出力２０２についてはパリティベクトルｐをベクトルｙとする（ステップＳ５）。符号化器２００はベクトルｙをリンクに出力する（ステップＳ６）。これにより、有効なＯＴＮフレーム２１０入力に対応したＯＴＮ出力２０２には元のフレーム情報（列，行）が出力され、無効信号２１１入力に対応したＯＴＮ出力２０２にはパリティベクトルｐの要素が出力される。
【０１０４】
図１２を参照して復号化器２２０におけるフレーム処理手順について説明する。復号化器２２０は、各レーンのＯＴＮフレーム２１０またはパリティフレーム２１２、もしくは無効信号２１１の入力状況の情報から復号化行列Ｂを生成する（ステップＳ１１）。復号化器２２０は、各レーンのすべてのフレーム情報（列，行）に対して、以下の処理を実行する（ステップＳ１２）。復号化器２２０は、フレーム情報（列，行）内の領域がＦＡＳ信号２１３またはＦＥＣ情報２１４（ＦＡＳもしくはＦＥＣ領域）であるか否かを判断する（ステップＳ１３）。復号化器２２０は、ＦＡＳもしくはＦＥＣ領域（ステップＳ１３の判断結果がＹｅｓ）に関しては、ＯＴＮ標準仕様に従って情報を生成する（ステップＳ１４）。それ以外の領域（ステップＳ１３の判断結果がＮｏ）に関しては、復号化器２２０は、有効なＯＴＮフレーム２１０またはパリティフレーム２１２のフレーム情報（列，行）もしくは、０（無効信号２１１入力の場合）からなるベクトルｙと、復号化行列Ｂの積を計算し、積ｙＢを復号情報ベクトルｑとする（ステップＳ１５）。復号化器２２０は、有効なＯＴＮフレーム２１０が入力されたレーンについてはベクトルｙをベクトルｘとし、有効なＯＴＮフレーム２１０が障害により無効信号２１１入力となったレーンについては復号情報ベクトルｑをベクトルｘとする（ステップＳ１５）。復号化器２２０はベクトルｘをリンクに出力する（ステップＳ１６）。これにより、有効なＯＴＮフレーム２１０が入力されたレーンにはＯＴＮフレーム２１０がスルーで出力され、有効なＯＴＮフレーム２１０が障害により無効信号２１１入力となったレーンには復号情報ベクトルｑの要素が出力され、それ以外は無効信号２１１となる。このようにして、復号化器２２０は、送信端における各ＯＴＮ入力２０１を再生し、再生された各ＯＴＮ入力２０１を出力する。
【０１０５】
このように、本実施形態のシステムは、レーン毎にＯＴＵフレーム２１０を生成して外部から入力された被伝送データを並列伝送媒体に送信し、複数のレーンによって伝送されたＯＴＵフレーム２１０から被伝送データを抽出し、抽出された被伝送データを外部に出力する並列伝送システムである。複数のレーンはシンボルレーンとパリティレーンに分類される。
【０１０６】
符号化器２００は、シンボルレーンについては、分割された被伝送データをＯＰＵ／ＯＤＵペイロードに格納し、ＩＴＵ−Ｔ  Ｇ．７０９に準拠したＯＴＵフレームを伝送し、パリティレーンについては、ＦＡＳ（Frame Alignment Signal）信号２１３及びＦＥＣ情報２１４以外の領域には各シンボルレーンの同一行同一列のシンボルを有効要素として符号化によって得られた送信ベクトルの対応要素を格納し、ＦＡＳ信号２１３及びＦＥＣ情報２１４の領域にはＩＴＵ−Ｔ  Ｇ．７０９に準拠した値を格納して、伝送を行う。
【０１０７】
復号化器２２０は、複数のレーンによって伝送されたＯＴＵフレーム２１０のうち、正常に受信したシンボルレーンに含まれるＯＴＵフレーム２１０に対しては、ＯＰＵ／ＯＤＵペイロードに含まれる被伝送データを抽出し、抽出された被伝送データを外部に出力する。また、復号化器２２０は、ＬＯＦ（Loss-Of-Frame）検出、もしくは、ＦＥＣによる誤り訂正限界の検出、もしくは、ＢＩＰ（Bit Interleaved Parity）による誤り検出等により、異常を検出したシンボルレーンに対しては、異常を検出したシンボルレーンに含まれるＯＰＵ／ＯＤＵペイロードを消失訂正により復元して被伝送データを抽出し、抽出された被伝送データを外部に出力する。
【０１０８】
（第九の実施形態）
本実施形態は、既存のパリティフレームをペイロードタイプとして定義する場合において、ＯＴＮのマルチレーン伝送に本発明の符号化方式を適用する一例を示す。図１３および図１４はそれぞれ、標準のＯＴＮフレームおよびパリティフレームをペイロードタイプとして定義する場合のＯＴＮフレームの一例を示す。
【０１０９】
ＯＴＮフレームは４０８０×４バイトから構成される。フレームの認識にはＦＡＳ（ＯＡ１，ＯＡ２）及びＦＥＣ領域３０１が必須であり、かつ、ＦＡＳ及びＦＥＣ領域３０１は符号化により保護される必要が無い領域であるので、パリティフレームにおいても標準ＯＴＮに準拠した値をとる事とする。保護領域３０２については、第八の実施形態と同様の手順によりパリティを生成し、パリティフレームの当該領域に符号化情報を格納する。ペイロードタイプの識別およびＭＦＡＳ（Multi-Frame Alignment Signal）を用いたマルチフレーム情報を得るのに必須な保護領域３０３は、符号化により保護される必要があるが、パリティフレームにおいて符号化情報を格納する事の出来ない領域である。一方、予約領域３０４はフレームの認識に対して必須な領域ではないので、保護領域３０３に対する符号化情報を格納する格納領域３０５の情報を予約領域３０４の一部に格納する事で、有効なＯＴＮフレームに対する符号化による保護を行う事が可能になる。
【０１１０】
パリティフレームの識別は、ＰＴ（Payload Type）バイト（ＰＳＩ（Payload Structure Identifier）領域｛１５，４｝，ＭＦＡＳ＝０）を用いて行う。ＰＳＩ領域｛１５，４｝のＭＦＡＳ≠０の時のマルチフレーム転送により保護領域３０３に対する符号化情報を格納する格納領域３０５へのマッピング情報を送信しても構わない。
【０１１１】
表１は、図１４に対するマッピング情報を示す。表１の情報を、ＭＦＡＳを用いたマルチフレーム転送する事によって、外部通信手段を用いずに格納情報の設定や更新を行う事が可能になる。
【０１１２】
【表１】
2014045906.tif 000074
【０１１３】
このように、本実施形態では、ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＰＳＩの値を参照する事によってシンボルレーンが識別される。
【０１１４】
各パリティレーン内の、ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＯＨ（Ｏｖｅｒ  Ｈｅａｄ）の一部の領域である保護領域３０３に関し、保護領域３０３に対応した送信ベクトルを同一パリティレーン内のＯＨ領域である格納領域３０５に格納し、保護領域３０３にはＩＴＵ−Ｔ  Ｇ．７０９に準拠した値を格納する。また、異常を検出したシンボルレーンに含まれるＯＰＵ／ＯＤＵペイロードを復元する際、保護領域３０３の復元に各パリティレーンにおける格納領域３０５の情報を用いる。
【０１１５】
保護領域３０３は、ＩＴＵ−Ｔ  Ｇ．７０９で定義されるＭＦＡＳ（Multi-Frame Alignment Signal）、およびＰＳＩを少なくとも含む。ＭＦＡＳを用いたマルチフレーム転送により、保護領域３０３及び格納領域３０５のフレーム内位置の情報が送信され、異常を検出したシンボルレーンに含まれるＯＰＵ／ＯＤＵペイロードを復元する際にフレーム内位置の情報が用いられる。
【０１１６】
パリティを送信するレーンについてＯＴＵフレームのフォーマットと異なる形式を採用した場合、標準的なＯＴＵフレームの受信回路および同期回路が使用できないため、パリティレーン専用の受信回路および同期回路も用いたハイブリッドな実装を行うことになる。これに対して、本実施形態では、ＯＴＵフレームの認識に必要な最小限の領域がパリティレーンにおいても標準的なＯＴＵフレームに準拠するようにしている。これにより、ＯＴＵフレームの受信回路および同期回路の共用が可能となり、コンパクトなフレーマ受信回路の構成が可能となる。
【０１１７】
（第十の実施形態）
本実施形態では、伝送区間が仮想的な並列媒体により接続されている場合の冗長伝送システムについて説明する。図１５はこの冗長伝送システムの構成を示すブロック図である。図１５において、仮想並列媒体７０２は、ＶＬＡＮ（Virtual Local Area Network）やＰＰＰｏＥ（Point-to-Point Protocol over Ethernet（登録商標）），ＧＲＥ（Generic Routing Encapsulation）などのカプセル化により、物理媒体内に作成された並列論理パスを形成する。
【０１１８】
被伝送パケット７０８はパケット入力部６１０に入力されて内部のバッファに蓄積される。パケット入力部６１０は、蓄積された被伝送パケット７０８をあらかじめ決められた長さ（例えば、あらかじめ決められたバイト数）単位に分割し、もしくは、一定時間毎にタイムスロット（ＴＳ）単位に分割する。さらに、パケット入力部６１０は、同一タイムスロット内のパケットをＦＩＦＯ付符号化器５１０（第五の実施形態および第六の実施形態を参照）の並列数と同数の系統に分配・分割して、入力並列データ１０８とする。パケット化機能部１３０（第六の実施形態を参照）は、ＦＩＦＯ付符号化器５１０により符号化されたデータをパケット化して符号化パケット出力部７３０の入力（Ｗｐ（ｔ）１３２）とする。符号化パケット出力部７３０は、レーン毎にレーンおよびタイムスロットを識別分離可能な情報を含むカプセル化を行い、カプセル化されたパケッ７３２をレーン番号順に仮想並列媒体７０２へ出力する。
【０１１９】
符号化パケット入力部７３１は、カプセル化情報に含まれる識別分離情報に基づいて、仮想並列媒体７０２により伝送されたパケット７３３をレーン毎に分離し、分離されたカプセル化パケットをタイムスロット毎に整列して、逆パケット化機能部１３１への入力（Ｒｐ（ｔ）１３３）とする。逆パケット化機能部１３１およびＦＩＦＯ付復号化器５３０は、第六の実施形態で説明した復号化を行って出力並列データ１０９を生成する。パケット出力部６３０は、出力並列データ１０９から被伝送パケット７０９を再構成して被伝送パケット７０９を出力する。
【０１２０】
（第十一の実施形態）
本実施形態では、図１６および図１７を用いて、図１５におけるパケット入力部６１０におけるタイムスロット内のパケットの分配・分割に関する方法の具体例、および、パケット出力部６３０におけるパケットの結合に関する方法の具体例について説明する。
【０１２１】
図１６において、被伝送パケット７０８として、タイムスロットＴＳ１の期間に被伝送パケット７０８−ａ，被伝送パケット７０８−ｂ，被伝送パケット７０８−ｃ，被伝送パケット７０８−ｄが到着し，タイムスロットＴＳ２の期間に被伝送パケット７０８−ｅが到着した場合を想定する。
【０１２２】
パケット入力部６１０は、同一タイムスロット内のパケットをＦＩＦＯ付符号化器５１０の並列数と同数の系統に分配・分割する。図１６においては並列数を４と仮定する。タイムスロットＴＳ１において、パケット入力部６１０は、入力並列データ１０８−１として被伝送パケット７０８−ａおよび被伝送パケット７０８ｂを分配し、入力並列データ１０８−２として被伝送パケット７０８−ｃ２を分配し、入力並列データ１０８−３として被伝送パケット７０８−ｃ３を分配する。タイムスロットＴＳ２において、パケット入力部６１０は、入力並列データ１０８−１として被伝送パケット７０８−ｄおよび被伝送パケット７０８ｅを分配する。
【０１２３】
タイムスロットＴＳ１において、パケット化機能部１３０は、Ｗｐ（ｔ）１３２−１としてパケット１３２−ａ１およびパケット１３２−ｂ１を出力し、Ｗｐ（ｔ）１３２−２としてパケット１３２−ｃ２を出力し、Ｗｐ（ｔ）１３２−３としてパケット１３２−ｃ３を出力し、Ｗｐ（ｔ）１３２−４として冗長パケット１３２−ｘ４を出力する。タイムスロットＴＳ２において、パケット化機能部１３０は、Ｗｐ（ｔ）１３２−１としてパケット１３２−ｄ１およびパケット１３２−ｅ１を出力し、Ｗｐ（ｔ）１３２−２として冗長パケット１３２−ｙ２を出力し、Ｗｐ（ｔ）１３２−３として冗長パケット１３２−ｙ３を出力し、Ｗｐ（ｔ）１３２−４として冗長パケット１３２−ｙ４を出力する。
【０１２４】
［第一の分配・分割方法］
この方法では、パケット入力部６１０は、パケットが存在しないレーンの数を最大化するようにパケットの分配を最適化する。被伝送パケット７０８−ａおよび７０８−ｂのように、同一のレーンに複数のパケットが分配されても構わない（図１６の入力並列データ１０８−１を参照）。この最適化は、Ｂｉｎ  Ｐａｃｋｉｎｇ問題と等価でＮＰ困難に属するが、効率的な近似アルゴリズムが存在する。このアルゴリズムは、例えば、「Albers, S. and Mitzenmacher, M. “Average-Case Analyses of First Fit and Random Fit Bin Packing.”Random Structures Alg. 16, 240-259, 2000.」（参考文献１）に記載されている。
【０１２５】
［第二の分配・分割方法］
この方法では、パケット入力部６１０は、パケットが存在しないレーンの数が少なくとも最少冗長度ｒｍｉｎとなるように、パケットを割り当てようとしているタイムスロットとは異なる他のタイムスロットにパケットを分配する。図１６においてはｒｍｉｎ＝１を仮定している。被伝送パケット７０８−ｄをタイムスロットＴＳ１の入力並列データ１０８−４として割り当てると、パケットが存在しないレーンの数が０となるため、タイムスロットＴＳ２の入力並列データ１０８−１として被伝送パケット７０８−ｄを割り当てている。
【０１２６】
［第三の分配・分割方法］
この方法では、パケット入力部６１０は、パケットのパケット長が１レーンの１タイムスロットのデータ長より大きい場合、当該パケットを１タイムスロットのデータ長以下の長さを持つ複数のパケットに分割し、分割された複数のパケットを異なるレーンに分配する。図１６においては、被伝送パケット７０８−ｃを２つの被伝送パケット７０８−ｃ２および被伝送パケット７０８−ｃ３に分割している。
【０１２７】
上述した分配・分割方法を適宜組み合わせてもよい。これらのすべての分配・分割方法の組み合わせにおいて、各タイムスロットにおける冗長パケットの個数を高々最大冗長度ｒｍａｘに制限しても構わない。図１６においてはｒｍａｘ＝１を仮定している。同図は、この制限に従って、符号化パケット出力部７３０が、冗長パケット１３２−ｙ３および冗長パケット１３２−ｙ４を廃棄したことを示している。したがって、符号化パケット出力部７３０は、タイムスロットＴＳ１において、パケット１３２−ａ１，パケット１３２−ｂ１，パケット１３２−ｃ２，パケット１３２−ｃ３，冗長パケット１３２−ｘ４を出力し、タイムスロットＴＳ２において、パケット１３２−ｄ１，パケット１３２−ｅ１，冗長パケット１３２−ｙ２を出力する。
【０１２８】
図１７はパケットの復号の様子を示している。タイムスロットＴＳ１において、仮想並列媒体７０２からはパケット７３３−ａ１，パケット７３３−ｂ１，パケット７３３−ｃ３，冗長パケット７３３−ｘ４が出力される。タイムスロットＴＳ２において、仮想並列媒体７０２からは、冗長パケット７３３−ｙ２が出力される。ここでは、仮想並列媒体７０２において、パケット７３３−ｃ２，７３３−ｄ１，７３３−ｅ１が消失したと仮定している。
【０１２９】
符号化パケット入力部７３１は、カプセル化情報に含まれる識別分離情報に基づいて、各パケットをレーン毎に分離する。同図では、Ｒｐ（ｔ）１３３−１としてパケット１３３−ａ１およびパケット１３３−ｂ１が出力され、Ｒｐ（ｔ）１３３−３としてパケット１３３−ｃ３が出力され、Ｒｐ（ｔ）１３３−４として冗長パケット１３３−ｘ４が出力される。また、タイムスロットＴＳ２において、Ｒｐ（ｔ）１３３−２として冗長パケット１３３−ｙ２が出力される。なお、パケット７３３−ｃ２，パケット７３３−ｄ１，パケット７３３−ｅ１が消失しているため、パケット１３３−ｃ２，パケット１３３−ｄ１，パケット１３３−ｅ１は出力されない。タイムスロットＴＳ１およびタイムスロットＴＳ２においてそれぞれ冗長パケット１３３−ｘ４および冗長パケット１３３−ｙ２を受信しているため、各タイムスロットにおいて１レーン分の復元が可能である。
【０１３０】
タイムスロットＴＳ１において、ＦＩＦＯ付復号化器５３０は、出力並列データ１０９−１としてパケット１０９−ａ１およびパケット１０９−ｂ１を出力し、出力並列データ１０９−２としてパケット１０９−ｃ２を出力し、出力並列データ１０９−３としてパケット１０９−ｃ３を出力する。タイムスロットＴＳ２において、ＦＩＦＯ付復号化器５３０は、出力並列データ１０９−１としてパケット１０９−ｄ１およびパケット１０９−ｅ１を出力する。パケット１０９−ｃ２，パケット１０９−ｄ１，パケット１０９−ｅ１がＦＩＦＯ付復号化器５３０により復元されたパケットを表す。
【０１３１】
パケット出力部６３０は、第三の分配・分割方法によって分割されたパケット１０９−ｃ２およびパケット１０９−ｃ３を結合してから出力する。したがって、パケット出力部６３０は、タイムスロットＴＳ１ではパケット７０９−ａ，パケット７０９−ｂ，パケット７０９−ｃを出力し、タイムスロットＴＳ２では、パケット７０９ｄおよびパケット７０９−ｅを出力する。
【０１３２】
次に、本発明の第十二〜第二十の実施形態について説明する。本願明細書では、ベクトルＸとベクトルＹの２項演算子記号「＊」をベクトルの要素同士の積と定義する。例えば、ベクトルＸとベクトルＹが以下の式（１１）であるとする。
【０１３３】
Ｘ＝｛ｘ０，ｘ１，ｘ２，…，ｘｎ−１｝、Ｙ＝｛ｙ０，ｙ１，ｙ２，…，ｙｎ−１｝      …（１１）
【０１３４】
この場合、ベクトルＸとベクトルＹの各要素同士の積のベクトルＺは、以下の式（１２）で表される。
【０１３５】
Ｚ＝Ｘ＊Ｙ＝｛ｘ０ｙ０，ｘ１ｙ１，ｘ２ｙ２，…，ｘｎ−１ｙｎ−１｝      …（１２）
【０１３６】
［本発明の第十二〜第二十の実施形態の基本原理］
第十二〜第二十の実施形態によるパケット冗長伝送システムは、送信端である送信器及び受信端である受信器を備えて構成される。第十二〜第二十の実施形態では、データのブロックをパケットと記載する。第十二〜第二十の実施形態のパケット冗長伝送システムに用いられる符号化は、例えば、Ｃａｕｃｈｙリードソロモン符号（以下、「ＣＲＳ符号」と記載する。）、などのＭＤＳ符号（Maximum Distance Separable Code；最大距離分離符号）に属する（２Ｖ，Ｖ）ブロック符号を用いる。（２Ｖ，Ｖ）ブロック符号は、Ｖシンボルの消失訂正が可能である。すなわち、第十二〜第二十の実施形態のパケット冗長伝送システムは、データ長とパリティ長が等しくなるような符号化を行う。
【０１３７】
なお、ＣＲＳ符号は、例えば、非特許文献３に記載されている。
また、ＭＤＳ符号は、例えば、非特許文献４に記載されている。
【０１３８】
ＭＤＳ符号（２Ｖ，Ｖ）の一般的な特徴として、２Ｖ個のデータおよびパリティの中から任意に選択したＶ個の情報を用いて元のＶ個のデータを復元する事が可能である。これは、受信器において、元のＶ個のデータを未知変数、選択したＶ個の情報を既知変数とするＶ個の連立一次方程式を解くことに相当する。
【０１３９】
ここで、ＣＲＳ符号など任意のパリティ生成行列の部分行列もまたＭＤＳ符号を構成する行列を用いると、未知変数としていたデータのうちｋ個の値が別の手段により取得できた場合、残りのＶ−ｋ個の未知変数はＶ−ｋの既知変数とＶ−ｋ個の方程式を解くことで求められる。言い換えると、選択したＶ個の情報のうちｋ個が消失しても構わないと言う事である。
【０１４０】
情報伝送においては、送りたい情報がＶ−ｋ個の未知変数、実際に送出するのがデータおよびパリティから選択したＶ個の情報、受信した情報が既知変数に対応する。伝送においてｋ個の情報が消失したとしても、残りの受信情報からＶ−ｋ個の連立一次方程式を解くことにより消失情報を復元することが可能である。
【０１４１】
第十二〜第二十の実施形態の送信器は、列方向にＨ個（Ｈは１以上の整数）、行方向にＶ個（Ｖは２以上の整数）の２次元（Ｈ，Ｖ）に配置された入力バッファ及び出力バッファを有する。入力バッファ及び出力バッファは、バッファ長Ｌの固定長バッファであり、シンボル数Ｌのシンボルを記憶できる。送信器は、被伝送パケット（被伝送データ）を、列−行の順に入力バッファに時系列に設定し、パケットが入力されなかった時刻の入力バッファには無効なシンボル（通常は０）を設定する。送信器は、同一列の入力バッファの先頭からのシンボル位置が同じシンボル列の単位で符号化を行う。送信器は、データを選択するかパリティを選択するかの選択情報ＳＩにより、入力バッファに設定されているＶ個の情報シンボル及びＶ個のパリティシンボルの中からＶ個のシンボルを選択して出力バッファのシンボルに収容する。例えば、送信器は、入力バッファに設定されているシンボルを、そのシンボル位置を保持したまま、同じ２次元位置の出力バッファに設定した上で、入力バッファにおいて無効なシンボルが設定されているシンボル位置と同じシンボル位置には、符号化により生成されたパリティを設定する。送信器は、出力バッファの単位でシンボルをパケット化して送出する。
受信器は、２次元（Ｈ，Ｖ）に配置された受信バッファを有する。受信バッファは、送信器の固定長バッファと同じサイズである。受信器は、受信したパケットを受信バッファに設定する。受信器における復号化は、送信器における符号化と同様に、同一列の受信バッファの先頭からのシンボル位置が同じシンボル列の単位で行う。
【０１４２】
上述のように第十二〜第二十の実施形態の送信器は、被伝送パケットが到着しなかった時刻に対応した固定長の入力バッファには無効なシンボル（通常は０であり、既知の値として使用する。）を書込む。そして、送信器は、上述の原理を応用するために、送信パケットに、各列における有効データのシンボル位置を示すデータ有効情報Ｕｘ（ｉ）と、各列における各シンボルとして被伝送パケットのシンボルを設定したのかパリティのシンボルを設定したものであるかを示す選択情報ＳＩｘ（ｉ）とを付加して受信器に通知する（ｉ＝１，２，…，Ｌ）。
受信器は、消失パケットの検出を行い、各列において消失したパケットを示す消失パケット情報Ｅｘ（ｉ）を取得する。受信器は、受信したパケットのシンボル列、データ有効情報Ｕｘ（ｉ）、選択情報ＳＩｘ（ｉ）、消失パケット情報Ｅｘ（ｉ）、及び送信器が符号化の際に用いた行列からなるガロア体連立１次方程式を解くことにより、消失した被伝送パケットを復元する。つまり、受信器は、消失パケット情報Ｅｘ（ｉ）及びデータ有効情報Ｕｘ（ｉ）から前述の未知変数を設定し、消失パケット情報Ｅｘ（ｉ）及び受信パケットから前述の既知情報を設定し、シンボル列毎に連立一次方程式を解くことにより未知変数（被送信情報）を復元する。
【０１４３】
以下、上述した基本原理に基づく各実施形態について説明する。
【０１４４】
（第十二の実施形態）
まず、本実施形態のパケット冗長伝送システムの原理について説明する。本実施形態のパケット冗長伝送システムにおける送信器は、列(横）方向（ｘ）及び行（縦）方向（ｙ）の２次元に配置された入力バッファＢＵＦｉｎ（ｘ，ｙ）を具備している（ｘは１以上Ｈ以下の整数、ｙは１以上Ｖ以下の整数）。各入力バッファＢＵＦｉｎ（ｘ，ｙ）は、長さＬの固定長である。ここでは、入力バッファＢＵＦｉｎ（ｘ，ｙ）が、右から左の方向に列の番号が増え、上から下の方向に行の番号が増えるように２次元に配置されている場合について説明する。
【０１４５】
送信器は、被伝送パケットの到着時刻に応じて、同一列の上から下へこの受信した被伝送パケットを入力バッファＢＵＦｉｎ（ｘ，ｙ）に書込み、下端に達したら左隣の列の上端から受信した被伝送パケットを入力バッファＢＵＦｉｎ（ｘ，ｙ）に書込み、被伝送パケットが到着しなかった時刻に対応した入力バッファＢＵＦｉｎ（ｘ，ｙ）には０を書込む。送信器は、以下の式（１３）により、符号化率０．５のガロア体ＭＤＳ符号に属するパリティ生成行列Ａ、設定データＭｘ（ｋ）、データ有効情報Ｕｘ（ｋ）を用いて、各列の同一シンボルＢＵＦｉｎ（ｘ，ｙ）［ｋ］（ｋ＝｛１，２, …,Ｌ｝）単位でパリティを生成する。なお、ｋはシンボル位置を示し、ＢＵＦｉｎ（ｘ，ｙ）［ｋ］は、入力バッファＢＵＦｉｎ（ｘ，ｙ）のｋ番目のシンボルである。
【０１４６】
【数７２】
2014045906.tif 000075
【０１４７】
式（１３）において、「：＝」は、右辺により左辺を定義することを示す。Ｍｘ（ｋ）は、ｘ列の１〜Ｖ行のｋ番目のシンボル、ｍｊは、ｘ列ｊ行のｋ番目のシンボルである。Ｕｘ（ｋ）は、ｘ列の１〜Ｖ行のｋ番目のシンボルが有効であるか否かを示し、ｕｊはｘ列ｊ行のｋ番目のシンボルが有効シンボル（被伝送パケットに基づき設定したシンボル）である場合は１、無効シンボルである場合は０である。パリティＳｘ（ｋ）は、ｘ列の１〜Ｖ行のｋ番目のシンボルから生成したパリティである。Ｐａｒｉｔｙ（ｘ，ｙ）は、シンボルＢＵＦｉｎ（ｘ，ｙ）のパリティであり、１〜Ｌ番目のシンボルについて生成した各パリティＳｘ（ｋ）のｙ行目の値（シンボル）を並べたものである。
【０１４８】
送信器は、入力バッファＢＵＦｉｎ（ｘ，ｙ）と同様に列方向及び行方向の２次元に配置した出力バッファＢＵＦｏｕｔ（ｘ，ｙ）をさらに備える。送信器は、以下の出力バッファ設定アルゴリズムに示すように、１以上の被伝送パケットが存在する入力バッファＢＵＦｉｎ（ｘ，ｙ）の設定内容を示す情報を同一行、同一列の出力バッファＢＵＦｏｕｔ（ｘ，ｙ）に出力して設定し、被伝送パケットが存在しない入力バッファＢＵＦｉｎ（ｘ，ｙ）に対応した出力バッファＢＵＦｏｕｔ（ｘ，ｙ）には、該当する行（ｙ）に対応したＰａｒｉｔｙ（ｘ，ｙ）の情報を出力して設定する。なお、入力バッファＢＵＦｉｎ（ｘ，ｙ）の設定内容を示す情報は、入力バッファＢＵＦｉｎ（ｘ，ｙ）の設定内容のコピーまたは入力バッファＢＵＦｉｎ（ｘ，ｙ）の設定内容へのポインタである。同様に、Ｐａｒｉｔｙ（ｘ，ｙ）の情報は、Ｐａｒｉｔｙ（ｘ，ｙ）の値のコピーあるいはＰａｒｉｔｙ（ｘ，ｙ）の値へのポインタである。
【０１４９】
【数７３】
2014045906.tif 000076
【０１５０】
送信器は、出力バッファＢＵＦｏｕｔ（１，１）から最後の列へと行方向に設定内容を読み出し、パケットとして送信する。送信器は、最後の列（左端）に達したら次の行の先頭の列から行方向に設定内容を読み出しパケットの送出を行う。送信器は、被伝送パケットを設定したパケットを送出する際に、出力バッファ（入力バッファ）のバッファ番号（ｘ，ｙ）と、バッファ内での先頭のシンボル位置ｋｘ，ｙを付加する。また送信器は、パリティを設定したパケットを送出する際に、出力バッファのバッファ番号（ｘ，ｙ）と、各行ブロックにおけるデータ有効情報Ｕｘ（ｋ）を付加する。なお、本実施形態では、データ有効情報Ｕｘ（ｋ）が選択情報ＳＩｘ（ｋ）と同値であるため、送信器は選択情報ＳＩｘ（ｋ）を別情報としては送信していない。
【０１５１】
受信器は、受信パケットに付加情報として設定されているバッファ番号（ｘ，ｙ）に従って、当該受信パケットに設定されている被伝送パケットあるいはパリティを固定長の受信バッファＢＵＦｒｃｖ（ｘ，ｙ）に設定する。なお、被伝送パケットについては、付加情報として設定されている先頭のシンボル位置ｋｘ，ｙに従って受信バッファＢＵＦｒｃｖ（ｘ，ｙ）に設定する。
【０１５２】
受信器は、一定時間たっても受信バッファＢＵＦｒｃｖ（ｘ，ｙ）のいずれかに空きがある場合、パケットが消失したとして、消失パケット情報Ｅｘ（ｉ）のバッファ位置（ｘ，ｙ）に対応する全てのシンボルｉに１をセットする。受信器は、以下の式（１４）により、消失パケットを復元する。なお、ｋはシンボル位置を示し、ＢＵＦｒｃｖ（ｘ，ｊ）［ｋ］は、ＢＵＦｒｃｖ（ｘ，ｊ）のｋ番目のシンボルであり、消失パケット情報Ｅｘ（ｉ）は、ｘ列の１〜Ｌ行の出力バッファに対応したパケットのｋ番目のシンボルを、受信器が受信したか否かを示す。また、Ｙｘ’（ｋ）は、ｘ列の１〜Ｌ行の出力バッファＢＵＦｏｕｔから送信器が生成したパケットのうち受信器が受信したパケットに設定されている被伝送データまたはパリティのｋ番目のシンボルを示す。行列Ｄは、パリティ生成行列ＡのＵｘ（ｋ）［ｙ］＝１に対応する行と、単位行列ＩのＵｘ（ｋ）［ｙ］＝０に対応する行から構成される行列であり、ａｊｉは、パリティ生成行列Ａのｉ列ｊ行の要素である。
【０１５３】
【数７４】
2014045906.tif 000077
【０１５４】
以下に、１シンボル列に対するガロア体ＧＦ（２５６）での計算例を示す。以下では、送信器は、ブロック全体のすべての列に対して同様の計算を行う事により、消失パケットの復元を行う。なお、以下では、送信器は、８行のうち最後の７、８行目を無効なシンボルとして符号化を行い、パケットの消失により伝送中に最初の１、２行目のシンボルが消失し、受信器は、受信シンボルから消失シンボルを復号する過程を示している。また、算出対象の列全体（ｋ＝１〜Ｌ）のＵｘ（ｋ）、Ｍｘ（ｋ）、Ｓｘ（ｋ）、Ｙｘ（ｋ）、Ｅｘ（ｋ）、Ｙｘ’（ｋ）をそれぞれ、Ｕ、Ｍ、Ｓ、Ｙ、Ｅ、Ｙ’としている。
【０１５５】
送信器は、以下の式（１５）により、送出シンボルＹを生成する。
【０１５６】
【数７５】
2014045906.tif 000078
なお、αはガロア拡大体における原始元である。
【０１５７】
伝送中に最初の２行のシンボルが消失したため、受信器は、以下の式（１６）に示すように消失パケット情報Ｅ、及び受信シンボル列Ｙ’を生成する。
【０１５８】
【数７６】
2014045906.tif 000079
【０１５９】
受信器は、データ有効情報Ｕが、１〜６行のシンボルが有効（１）であり、７、８行のシンボルが無効（０）であることを示すため、行列Ｄを、以下の式（１７）に示すように設定する。
【０１６０】
【数７７】
2014045906.tif 000080
【０１６１】
受信器は、以下の式（１８）に示すように、消失した被伝送パケットのシンボルを復元する。ただし、ｙｉは、（ｉ−１）行目のパケット、ｓｉは、（ｉ−１）行目の１〜ＬシンボルのＳｘ（ｋ）である（ｉは１以上Ｖ以下の整数）。
【０１６２】
【数７８】
2014045906.tif 000081
【０１６３】
続いて、本実施形態の原理を適用したパケット冗長伝送システムの構成及び動作の例について説明する。
【０１６４】
図１８は、本発明の第十二の実施形態によるパケット冗長伝送システムの機能ブロック図を示す。同図に示すように、本実施形態によるパケット冗長伝送システムは、パケット伝送路１２１０により接続される送信器１２００及び受信器１２２０を備えて構成される。
【０１６５】
送信器１２００は、符号化器入力バッファ部１２０１、空き領域検出部１２０２、符号化部１２０３、出力パケットバッファ部１２０４、及び送信器パケット出力部１２０５を備えて構成される。
【０１６６】
符号化器入力バッファ部１２０１は、Ｈ列Ｖ行の２次元に配置された長さＬの入力バッファＢＵＦｉｎを備える。ｘ列（ｘは１以上Ｈ以下の整数）ｙ行（ｙは１以上Ｖ以下の整数）の入力バッファＢＵＦｉｎを、入力バッファＢＵＦｉｎ（ｘ，ｙ）とする。符号化器入力バッファ部１２０１は、パケット入力１１０１内の被伝送パケットを、到着時刻に応じて、２次元に配置された入力バッファＢＵＦｉｎの最初の列の最初の行から最後の行の方向へ順に設定し、最後の行に達したら、列数が一つ大きな隣の列に移り、最初の行から最後の行の方向へ順に被伝送パケットを設定することを繰り返す。ただし、符号化器入力バッファ部１２０１は、入力パケットが到着しなかった時刻に対応した入力バッファＢＵＦｉｎには、０などの無効なシンボルを書込む。符号化器入力バッファ部１２０１は、入力バッファＢＵＦｉｎの設定内容を示す入力バッファ設定１１０２を、符号化部１２０３及び出力パケットバッファ部１２０４に出力する。なお、入力バッファ設定１１０２は、入力バッファＢＵＦｉｎの設定内容のコピーでもよく、入力バッファＢＵＦｉｎの設定内容へのポインタであってもよい。
【０１６７】
空き領域検出部１２０２は、無効なシンボルが設定されているかにより空きの入力バッファＢＵＦｉｎを検出し、検出結果を符号化部１２０３に出力する。
【０１６８】
符号化部１２０３は、入力バッファ設定１１０２から各列（ｘ）単位に符号化率０．５のガロア体Ｃａｕｃｈｙ行列などのＭＤＳ符号のパリティを計算する。つまり、符号化を行う単位のブロックは、各列の全ての行の入力バッファＢＵＦｉｎである。このとき、符号化部１２０３は、空き領域検出部１２０２により空きと判断されたバッファ番号のシンボルは０とし、パリティ生成行列Ａを用いて、上述した式（１３）によりパリティを計算する。これにより、入力バッファＢＵＦｉｎの行数と同じ行数のＰａｒｉｔｙ（ｘ，ｙ）が生成される。以下、Ｐａｒｉｔｙ（ｘ，ｙ）をパリティ（ｘ，ｙ）とも記載する。
【０１６９】
出力パケットバッファ部１２０４は、入力バッファと同じくＨ列Ｖ行に２次元に配置された長さＬの出力バッファＢＵＦｏｕｔを備える。ｘ列ｙ行の出力バッファＢＵＦｏｕｔを、出力バッファＢＵＦｏｕｔ（ｘ，ｙ）とする。出力パケットバッファ部１２０４は、上述した出力バッファアルゴリズムに示すように出力バッファＢＵＦｏｕｔ（ｘ，ｙ）を設定する。すなわち、出力パケットバッファ部１２０４は、空き領域検出部１２０２において空きではないと判断されたバッファ番号の出力バッファＢＵＦｏｕｔ（ｘ，ｙ）に、入力バッファ設定１１０２における同じバッファ番号の入力バッファＢＵＦｉｎ（ｘ，ｙ）の設定内容（またはその設定内容へのポインタ）を設定する。さらに、出力パケットバッファ部１２０４は、空き領域検出部１２０２において空きと判定されたバッファ番号の出力バッファＢＵＦｏｕｔ（ｘ，ｙ）には、そのバッファ番号の行（ｙ）に対応するパリティ（ｘ，ｙ）を（またはそのパリティ（ｘ，ｙ）へのポインタを）設定する。出力パケットバッファ部１２０４は、出力バッファＢＵＦｏｕｔ（ｘ，ｙ）の設定内容を示す出力バッファ設定１１０３を送信器パケット出力部１２０５に出力する。
【０１７０】
送信器パケット出力部１２０５は、出力バッファ設定１１０３に設定されている出力バッファＢＵＦｏｕｔ（ｘ，ｙ）の設定内容を、行単位に先頭の列から順に読み出す。送信器パケット出力部１２０５は、各出力バッファＢＵＦｏｕｔ（ｘ，ｙ）から読み出した設定内容（あるいは、ポインタを読み出した場合はそのポインタが示す設定内容）をそれぞれ設定した各パケットからなる送信器出力１１０４を受信器１２２０に送信する。このとき、送信器パケット出力部１２０５は、送信するパケットが被伝送パケットである場合、その被伝送パケットが格納されていた入力バッファＢＵＦｉｎ（ｘ，ｙ）（または、出力バッファＢＵＦｏｕｔ（ｘ，ｙ））のバッファ番号（ｘ，ｙ）と、先頭のシンボル位置ｋｘ，ｙを付加する。また、パリティパケットを送出する際には、送信器パケット出力部１２０５は、パリティパケットがいずれの出力バッファＢＵＦｏｕｔ（ｘ，ｙ）の設定内容から生成されたかを示すバッファ番号（ｘ，ｙ）と、各列ブロックのデータ有効情報Ｕを付加する。なお、データ有効情報Ｕは、空き領域検出部１２０２からの出力情報に基づき設定される。また、先頭のシンボル位置が固定の場合、被伝送パケットにｋｘ，ｙを設定しなくてもよい。
【０１７１】
受信器１２２０は、パケット入力バッファ部１２２１、復号化器入力バッファ部１２２２、パケット消失検出部１２２３、復号化部１２２４、及び出力パケット選択部１２２５を備えて構成される。
【０１７２】
パケット入力バッファ部１２２１は、パケット伝送路１２１０から受信した受信器入力１１０５に含まれる各パケットに付加されている情報からバッファ番号（ｘ，ｙ）を取り出し、そのバッファ番号（ｘ，ｙ）に従ってパケットを２次元に配置した受信バッファ入力１１０６を復号化器入力バッファ部１２２２に入力する。受信したパケットが被伝送パケットである場合、パケット入力バッファ部１２２１は、先頭のシンボル位置ｋｘ，ｙをさらに復号化器入力バッファ部１２２２に入力する。
【０１７３】
復号化器入力バッファ部１２２２は、送信器１２００の入力バッファＢＵＦｉｎ及び出力バッファＢＵＦｏｕｔと同じくＨ列Ｖ行に２次元に配置された長さＬの受信バッファＢＵＦｒｃｖを備える。ｘ列ｙ行の受信バッファＢＵＦｒｃｖを、受信バッファＢＵＦｒｃｖ（ｘ，ｙ）とする。復号化器入力バッファ部１２２２は、パケット入力バッファ部１２２１から出力された受信バッファ入力１１０６の設定内容を、バッファ番号（ｘ，ｙ）で示される行及び列の位置を保持したまま受信バッファＢＵＦｒｃｖ（ｘ，ｙ）に設定する。このとき、復号化器入力バッファ部１２２２は、被伝送パケットについては、先頭のシンボル位置ｋｘ，ｙから受信バッファＢＵＦｒｃｖ（ｘ，ｙ）に設定する。復号化器入力バッファ部１２２２は、データ有効情報Ｕから被伝送パケットが設定されているバッファ番号（ｘ，ｙ）を得ると、そのバッファ番号（ｘ，ｙ）及び受信バッファＢＵＦｒｃｖ（ｘ，ｙ）から読み出した被伝送パケットを出力パケット選択部１２２５に出力する。なお、パケットが被伝送パケットであるか否かは、データ有効情報Ｕから得られる。
【０１７４】
パケット消失検出部１２２３は、受信バッファＢＵＦｒｃｖが全て設定された場合、あるいは、伝送における最大遅延分散時間等、一定時間たっても受信バッファＢＵＦｒｃｖに空きがある場合、パケット伝送路１２１０における消失パケット１１１２を復号化部１２２４に通知する。パケット消失検出部１２２３は、受信バッファＢＵＦｒｃｖにパケットが設定されていない場合、そのバッファ番号に対応したパケットは消失パケット１１１２であると判断する。パケット消失検出部１２２３は、消失パケット１１１２のバッファ番号を復号化部１２２４に出力する。また、パケット消失検出部１２２３は、消失パケット１１１２が検出された受信バッファＢＵＦｒｃｖには０を設定する。
【０１７５】
復号化部１２２４は、パケット消失検出部１２２３から消失パケット１１１２のバッファ番号の通知を受けると、式（１４）を用いて消失パケットを復元し、復元により得られた被伝送パケットと、その被伝送パケットに対応したバッファ番号を出力パケット選択部１２２５に出力する。なお、受信シンボル列Ｙ’は、受信バッファＢＵＦｒｃｖから読み出して設定され、消失パケット情報Ｅは、パケット消失検出部１２２３からの出力に基づいて設定される。
【０１７６】
出力パケット選択部１２２５は、受信バッファＢＵＦｒｃｖから読み出された被伝送パケット及びそのバッファ番号と、復号化部１２２４が復元した被伝送パケット及びそのバッファ番号を復号後出力１１０７として受信する。出力パケット選択部１２２５は、バッファ番号に従って２次元に配列した被伝送パケットを、最初の列の最初の行から最後の行の方向へ順に受信器出力１１０８として出力する。出力パケット選択部１２２５は、最後の行に達したら、列数が一つ大きな隣の列に移り、最初の行から最後の行の方向へ順に被伝送パケットを受信器出力１１０８として出力することを最後の列まで繰り返す。
【０１７７】
図１９は、本実施形態の送信器１２００によるパケット出力手順を説明するための図である。ここでは、入力バッファＢＵＦｉｎ、及び出力バッファＢＵＦｏｕｔが、列数Ｈ＝６、行数Ｖ＝４であり、右から左の方向に列の番号が大きくなり、上から下の方向に行の番号が大きくなるように２次元に配置されている場合について説明する。
【０１７８】
符号化器入力バッファ部１２０１は、パケット入力１１０１に含まれる被伝送パケット１１１０の到着時刻に応じて、入力バッファＢＵＦｉｎに、１列目の１行目から４行目まで順に被伝送パケット１１１０を設定する。符号化器入力バッファ部１２０１は、入力バッファＢＵＦｉｎの一つの列について、全ての行に被伝送パケット１１１０を設定したら、次の列に移り、１行目から４行目まで順に被伝送パケット１１１０のシンボルを設定することを最後の列まで繰り返す。このように、符号化器入力バッファ部１２０１は、到着時刻に応じて、上端から下端へ被伝送パケット１１１０を設定し、下端に達したら左隣の列の上端から下端へと被伝送パケット１１１０を設定していく。符号化器入力バッファ部１２０１は、被伝送パケット１１１０が到着しなかった時刻に対応した入力バッファＢＵＦｉｎに０を書込む。符号化器入力バッファ部１２０１は、入力バッファＢＵＦｉｎの設定内容、バッファ番号（ｘ，ｙ）、及びバッファ内での先頭のシンボル位置ｋｘ，ｙを示す入力バッファ設定１１０２を出力する。
【０１７９】
出力パケットバッファ部１２０４は、入力バッファ設定１１０２において被伝送パケット１１１０が存在する入力バッファＢＵＦｉｎ（ｘ，ｙ）の設定内容を、同一列（ｘ）同一行（ｙ）の出力バッファＢＵＦｏｕｔ（ｘ，ｙ）にコピーする。あるいは、入力バッファＢＵＦｉｎ（ｘ，ｙ）の設定内容へのポインタを設定してもよい。
【０１８０】
符号化部１２０３は、入力バッファ設定１１０２から各列（ｘ）単位にパリティを計算する。符号化部１２０３は、被伝送パケットが設定されていないバッファ位置の出力バッファＢＵＦｏｕｔ（ｘ，ｙ）に、そのバッファ位置の行（ｙ）に対応するパリティ１１１１を設定する。
【０１８１】
例えば、同図に示す入力バッファ設定１１０２の１列目では、２行目にのみ被伝送パケット１１１０が設定されており、１、３、及び４行目には被伝送パケットは設定されていない。符号化部１２０３は、入力バッファ設定１１０２の１列目からＰａｒｉｔｙ（１，１）〜（１，４）を生成し、被伝送パケットが設定されていないバッファ位置の出力バッファＢＵＦｏｕｔ（１，１）、（１，３）、（１，４）にそれぞれパリティ１１１１として、Ｐａｒｉｔｙ（１，１）、（１，３）、（１，４）を設定する。
この方法では被伝送パケットがそのまま出力されるため、本実施形態に対応していない受信器でも、消失訂正機能はないが、被伝送パケットのみの受信は可能である。
【０１８２】
送信器パケット出力部１２０５は、出力パケットバッファ部１２０４から出力バッファＢＵＦｏｕｔの設定内容を示す出力バッファ設定１１０３の入力を受けると、１行目の１列目から６列目まで順に出力バッファＢＵＦｏｕｔの設定内容からパケットを生成する。送信器パケット出力部１２０５は、全ての列についてパケットを生成すると、次の行に移り、１列目から６列目まで順に出力バッファＢＵＦｏｕｔの設定内容からパケットを生成することを繰り返す。このように、送信器パケット出力部１２０５は、右上から行方向にパケットを生成し、左端に達したら一つ下の行の先頭（右端）から行方向にパケットを生成し、生成した順に送信器出力１１０４を送出する。つまり、送信器パケット出力部１２０５は、生成したパケットをパケットインターリーブして送信器出力１１０４を送信する。
なお、送信器パケット出力部１２０５は、各パケットに当該パケットが設定されていたバッファ番号（ｘ，ｙ）を付加し、パリティ１１１１から生成したパケットには、さらにデータ有効情報Ｕを付加する。なお、本実施形態では、すべてパリティを送信するため、受信器において選択情報ＳＩｘ（ｋ）が全てパリティを選択したことを示す値であることがわかるので、送信器は選択情報を付加せずにパケットを送信している。
【０１８３】
図２０は、本実施形態の受信器１２２０によるパケット復号化手順を説明するための図である。ここでは、受信バッファＢＵＦｒｃｖが、列数Ｈ＝６、行数Ｖ＝４であり、右から左の方向に列の番号が大きくなり、上から下の方向に行の番号が大きくなるように２次元に配置されている。
【０１８４】
パケット伝送路１２１０における伝送中、図１９で送出された送信器出力１１０４のなかで消失パケット１１１２が発生し、受信器１２２０は、受信器入力１１０５を受信する。受信器１２２０のパケット入力バッファ部１２２１は、受信器入力１１０５の各パケットを、付加情報が示すバッファ番号に従って並べた受信バッファ入力１１０６を復号化器入力バッファ部１２２２に出力する。
受信器１２２０の復号化器入力バッファ部１２２２は、受信バッファ入力１１０６に含まれる受信パケットを、その受信パケットに付加されていたバッファ番号（ｘ，ｙ）の受信バッファＢＵＦｒｃｖ（ｘ，ｙ）に設定する。
【０１８５】
復号化部１２２４は、式（１４）を用いて、各列の同一シンボル毎に消失パケット１１１２を復元する。本実施形態では各列において被伝送パケット数と同数以上の任意の組み合わせのパケット（被伝送パケット、パリティパケット）を受信した場合に消失訂正が可能である。復元された被伝送パケットが、図中に○が記載されている消失訂正パケット１１１４である。一方、１つの列における受信パケットの数が当該列の被伝送パケット数未満の場合には、消失訂正ができない。消失訂正ができなかった被伝送パケットが、図中に×が記載されている消失訂正不能パケット１１１３である。
【０１８６】
出力パケット選択部１２２５は、復号後出力１１０７の入力を受け、右上から列方向のバッファ番号の被伝送パケットを受信器出力１１０８として出力し、下端に達したら一つ左の列の先頭のバッファ番号の被伝送パケットを受信器出力１１０８として出力する。このとき、出力パケット選択部１２２５は、復号後出力１１０７に被伝送パケットが含まれていないバッファ番号に対応した送出タイミングにおいては、受信器出力１１０８を出力しない。
【０１８７】
（第十三の実施形態）
第十二の実施形態では、送信器は、入力バッファＢＵＦｉｎの設定内容を同一行、同一列の出力バッファＢＵＦｏｕｔに設定しているが、本実施形態では、全てパリティ（ｘ，ｙ）を出力バッファＢＵＦｏｕｔに設定する。本実施形態のパケット冗長伝送システムの構成は、図１８に示すパケット冗長伝送システムの構成と同様である。以下、第十二の実施形態との差分を中心に説明する。
【０１８８】
第十二の実施形態と同様に、送信器１２００の符号化器入力バッファ部１２０１は、入力バッファＢＵＦｉｎに被伝送パケット１１１０または無効シンボルを設定し、空き領域検出部１２０２は、空きの入力バッファＢＵＦｉｎを検出する。符号化部１２０３は、第十二の実施形態と同様に、入力バッファ設定１１０２から各列（ｘ）単位に、符号化率０．５のガロア体Ｃａｕｃｈｙ行列などのＭＤＳ符号のパリティを計算する。
【０１８９】
本実施形態では、出力パケットバッファ部１２０４は、以下の出力バッファ設定アルゴリズムに示すように、出力バッファＢＵＦｏｕｔを設定する。
【０１９０】
【数７９】
2014045906.tif 000082
【０１９１】
つまり、符号化部１２０３は、すべての出力バッファＢＵＦｏｕｔ（ｘ，ｙ）に、該当行（ｙ）に対応するＰａｒｉｔｙ（ｘ，ｙ）をコピーするか、Ｐａｒｉｔｙ（ｘ，ｙ）へのポインタを設定する。
この方法では被伝送パケットが疑似暗号化されるため、秘匿性が高い通信が可能になる。
【０１９２】
送信器パケット出力部１２０５は、第十二の実施形態と同様に、出力バッファ設定１１０３に設定されている出力バッファＢＵＦｏｕｔの設定内容を、先頭の列から順に行単位に読み出す。送信器パケット出力部１２０５は、読み出した設定内容（あるいは、ポインタを読み出した場合はそのポインタが示す設定内容）をそれぞれ設定したパケットを受信器１２２０に送信する。ただし、本実施形態では、送信するパケットは全てパリティパケットである。送信器パケット出力部１２０５は、パケットにいずれの出力バッファＢＵＦｏｕｔの設定内容からパケットが生成されたかを示すバッファ番号（ｘ，ｙ）と、各列ブロックのデータ有効情報Ｕを付加する。
【０１９３】
受信器１２２０のパケット入力バッファ部１２２１は、受信器入力１１０５の各パケットに付加されている情報からバッファ番号（ｘ，ｙ）を取り出し、そのバッファ番号（ｘ，ｙ）に従ってパケットを２次元に配置した受信バッファ入力１１０６を復号化器入力バッファ部１２２２に入力する。復号化器入力バッファ部１２２２は、パケットに付加されているバッファ番号（ｘ，ｙ）に従って受信したパケットのパリティ部分を受信バッファＢＵＦｒｃｖ（ｘ，ｙ）に設定する。パケット消失検出部１２２３は、受信バッファＢＵＦｒｃｖが全て設定された場合、あるいは、一定時間たっても受信バッファＢＵＦｒｃｖに空きがある場合、消失パケット１１１２を復号化部１２２４に通知する。受信器入力１１０５が全てパリティパケットであることを除き、ここまでの受信器１２２０の処理は、第十二の実施形態と同様である。
【０１９４】
復号化部１２２４は、式（１９）に示すように、受信バッファＢＵＦｒｃｖに設定されているシンボル列Ｙ’、データ有効情報Ｕ、消失パケット情報Ｅ、及びパリティ生成行列Ａからなるガロア体連立１次方程式を解くことにより消失パケットを復元し、出力パケット選択部１２２５に出力する。
【０１９５】
【数８０】
2014045906.tif 000083
【０１９６】
本実施形態では、第十二の実施形態と同様に、各列について、入力バッファの該当する列について被伝送パケット数と同数以上の受信パケットを受信した場合に、消失訂正が可能である。
【０１９７】
以下に、１シンボル列に対するガロア体ＧＦ（２５６）での計算例を示す。以下では、送信器は、ブロック全体のすべての列に対して同様の計算を行う事により、消失パケットの復元を行う。なお、以下では、送信器は、８行のうち最後の７、８行を無効なシンボルとして符号化を行い、パケットの消失により伝送中に最初の２行のシンボルが消失し、受信器は、受信シンボルから消失シンボルを復号する過程を示している。また、算出対象の列全体（ｋ＝１〜Ｌ）のＵｘ（ｋ）、Ｍｘ（ｋ）、Ｓｘ（ｋ）、Ｙｘ（ｋ）、Ｅｘ（ｋ）、Ｙｘ’（ｋ）をそれぞれ、Ｕ、Ｍ、Ｓ、Ｙ、Ｅ、Ｙ’としている。
【０１９８】
送信器１２００は、以下の式（２０）により、送出シンボルＹを生成する。
【０１９９】
【数８１】
2014045906.tif 000084
【０２００】
伝送中に最初の２行のシンボルが消失したため、受信器は、以下の式（２１）に示すように消失パケット情報Ｅ、及び受信シンボル列Ｙ’を生成する。
【０２０１】
【数８２】
2014045906.tif 000085
【０２０２】
受信器は、以下の式（２２）に示すように、消失した被伝送パケットのシンボルを復元する。ただし、ｍｊは、（ｉ−１）行目の被伝送パケットである。
【０２０３】
【数８３】
2014045906.tif 000086
【０２０４】
復号化部１２２４は、復号により得られた被伝送パケットと、その被伝送パケットに対応したバッファ番号を出力パケット選択部１２２５に出力する。出力パケット選択部１２２５は、復号化部１２２４が復号した被伝送パケット及びそのバッファ番号を復号後出力１１０７として受信する。出力パケット選択部１２２５は、第十二の実施形態と同様に、バッファ番号に従って２次元に配列された被伝送パケットを、最初の列の最初の行から最後の行の方向へ順に受信器出力１１０８として出力し、最後の行に達したら、列数が一つ大きな隣の列に移り、最初の行から最後の行の方向へ順に被伝送パケットを受信器出力１１０８として出力する。出力パケット選択部１２２５は、復号後出力１１０７に被伝送パケットが含まれていないバッファ番号に対応した送出タイミングにおいては、受信器出力１１０８を出力しない。
【０２０５】
（第十四の実施形態：ショートパケット）
本実施形態では、送信器が、符号化器入力バッファ部１２０１の入力バッファＢＵＦｉｎのバッファ長Ｌより短い被伝送パケット１１１０を受信する。本実施形態のパケット冗長伝送システムの構成は、図１８に示すパケット冗長伝送システムの構成と同様である。以下、第十二の実施形態、第十三の実施形態との差分を中心に説明する。
【０２０６】
図２１は、符号化器入力バッファ部１２０１が備える入力バッファＢＵＦｉｎにバッファ長Ｌより短い被伝送パケット１１１０が収容（設定）された場合の例を示している。
図２１（ａ）は、ある列の入力バッファＢＵＦｉｎに、先頭のシンボル列から被伝送パケット１１１０を収容した場合を示しており、当該列の全ての行に被伝送パケット１１１０が設定されている。この収容状態の入力バッファＢＵＦｉｎを最適化前の符号化器入力バッファ列１３００とする。この最適化前の符号化器入力バッファ列１３００の各シンボル列の無効シンボル数１３０１は、バッファの先頭に近いほど小さい値となる。
【０２０７】
図２１（ｂ）は、最適化後の入力バッファＢＵＦｉｎの設定例を示している。符号化器入力バッファ部１２０１が、最適化前の符号化器入力バッファ列１３００に対し、各シンボル列の無効シンボル数が出来るだけ一様になるように最適化を行うと、図２１（ｂ）に示すようになる。この収容状態の入力バッファＢＵＦｉｎを最適化後の符号化器入力バッファ列１３１０とする。
【０２０８】
送信器１２００は、最適化後の符号化器入力バッファ列１３１０を用いて、各シンボル列単位で、第十二の実施形態、第十三の実施形態と同様の符号化を行う。各シンボル列の最適化後の各シンボル列の無効シンボル数１３１１は、消失訂正可能なシンボルの個数である。そのため、パケット単位で考えると、最適化前では無効シンボル数１３０１の最小値＝０、すなわち１パケットの消失も許されないことになる。一方、最適化後では無効シンボル数１３１１の最小値＝２、すなわち任意の２パケットを消失したとしても、受信器１２２０において元の４パケットを復元することが可能になる。
【０２０９】
列単位でのパケット収容の最適化は、Ｂｉｎ  Ｐａｃｋｉｎｇ問題と等価でＮＰ困難に属するが、効率的な近似アルゴリズムが存在する。このアルゴリズムは、例えば、参考文献１に記載されている。
【０２１０】
逐次的なパケット収容における、最小冗長数ｒｍｉｎを保証するアルゴリズムの１つを以下に示す。冗長数は、各列あたりのパリティが設定されている行の数である。
【０２１１】
【数８４】
2014045906.tif 000087
【０２１２】
上記のように、符号化器入力バッファ部１２０１は、同一列の入力バッファＢＵＦｉｎにおける各行の先頭からのシンボル位置が等しいＶシンボルの中に含まれる有効シンボルの最大数が小さくなるように、入力バッファＢＵＦｉｎそれぞれにおける被伝送データの設定位置を調整する。
【０２１３】
なお、上記では、伝送順に被伝送パケット１１１０を入力バッファＢＵＦｉｎに設定しているが、入力バッファＢＵＦｉｎの空き領域に設定できれば、伝送順に係らず被伝送パケット１１１０を設定してもよい。
【０２１４】
（第十五の実施形態）
本実施形態では、送信器が、任意長の被伝送パケットを受信する。本実施形態のパケット冗長伝送システムの構成は、図１８に示すパケット冗長伝送システムの構成と同様である。以下、第十二の実施形態との差分を中心に説明する。
【０２１５】
図２２は、被伝送パケットが任意長である場合のパケット冗長伝送システムの動作を説明するための図である。送信器１２００へのパケット入力１１０１には、パケット長が入力バッファＢＵＦｉｎのバッファ長Ｌを超えない被伝送パケット１１３０−１、１１３０−２、１１３０−３、及びパケット長がバッファ長Ｌを超える被伝送パケット１１３１が含まれる。
同図では、符号化器入力バッファ部１２０１が備える入力バッファＢＵＦｉｎに、任意長の被伝送パケットが収容（設定）された場合の出力バッファ設定１１０３の例を示している。同図に示すように、符号化器入力バッファ部１２０１は、バッファ長Ｌの１つの入力バッファＢＵＦｉｎに、パケット長の総和がＬを超えないように複数の被伝送パケット１１３０−１、１１３０−２を設定してもよい。この方法は、伝送効率の向上が見込まれる。
また、パケット長がバッファ長Ｌを超える場合、符号化器入力バッファ部１２０１は、被伝送パケット１１３１をフラグメント化したフラグメントパケット１１３１−１、１１３１−２を複数の入力バッファＢＵＦｉｎに設定する。この方法により、任意の長さの被伝送パケットの収容を可能にする。
【０２１６】
なお、符号化器入力バッファ部１２０１は、各入力バッファＢＵＦｉｎにおいて被伝送パケットが設定されていないシンボルの部分は、パディング情報１１３２により０でパディングする。冗長数は、同一列の同一シンボル位置における無効なシンボル（０）の行数となるので、パディングする際に、他行との間で被伝送パケット同士のシンボル位置が出来るだけ重ならないようにしても良い。
【０２１７】
送信器パケット出力部１２０５は、送信器出力１１０４として送出する各被伝送パケットに、出力バッファにおける位置を示すバッファ番号（ｘ，ｙ）と、各バッファにおける先頭からのシンボル位置を付加して送出する。またパリティ１１１１のパケットに関してもバッファ番号（ｘ，ｙ）と、各バッファにおける先頭からのシンボル位置を付加して送出する。
【０２１８】
受信器１２２０の復号化器入力バッファ部１２２２において、消失パケット１１１２が存在する場合、復号化部１２２４は、各行のシンボル毎に、式（１４）もしくは式（１９）を解くことで消失パケットの復元を行い、復元により消失訂正されたパケットである消失訂正パケット１１１４を生成する。
【０２１９】
（第十六の実施形態）
本実施形態では、最小冗長数及び最大冗長数を設定する。本実施形態のパケット冗長伝送システムの構成は、図１８に示すパケット冗長伝送システムの構成と同様である。以下、第十二の実施形態との差分を中心に説明する。
【０２２０】
図２３は、最小冗長数ｒｍｉｎ、最大冗長数ｒｍａｘを設定したときのパケット冗長伝送システムの動作を説明するための図である（０＜ｒｍｉｎ≦ｒｍａｘ＜Ｖ）。最小冗長数ｒｍｉｎは、各列あたりのパリティの行数の最小数を示し、各列においてｒｍｉｎパケットの単一バースト誤り耐性を保証する。最大冗長数ｒｍａｘは、各列あたりのパリティの行数の最大数を示し、パケットレートが低いときに過剰な冗長化を避けるために用いる。同図においては、ｒｍｉｎ＝ｒｍａｘ＝２の場合を示している。
【０２２１】
符号化器入力バッファ部１２０１が、パケット入力１１０１内の被伝送パケット１１１０を、到着時刻に応じて、２次元に配置された入力バッファＢＵＦｉｎの最初の列の最初の行から最後の行の方向へ順に設定し、最後の行に達したら、列数が一つ大きな隣の列に移り、最初の行から最後の行の方向へ順に被伝送パケット１１１０を設定することを繰り返す基本的な動作は第十二の実施形態と同様である。符号化部１２０３は、各列についてｒｍｉｎ以上ｒｍａｘ以下のパリティを計算し、出力バッファＢＵＦｏｕｔに設定する。出力パケットバッファ部１２０４は、現在入力バッファＢＵＦｉｎへの被伝送パケット１１１０の書込みを行っている列においてパリティを書込む出力バッファＢＵＦｏｕｔの数がｒｍｉｎ以下となって不足する場合、被伝送パケット１１１０を次の列の先頭の出力バッファＢＵＦｏｕｔに書込む。
【０２２２】
送信器パケット出力部１２０５は、出力バッファ設定１１０３の設定内容を、最初の行の先頭の列から順にパケット化し、一つの行を終了したら一つ下の行の先頭の列から順にパケット化し、送信器出力１１０４として生成順にパケットを送出する。ただし、送信器パケット出力部１２０５は、列あたりｒｍａｘ個を超えるパリティ１１１５は送出しない。このように送信器パケット出力部１２０５は、各列の出力バッファＢＵＦｏｕｔのパケットを、その列の被伝送パケットの数＋ｒｍａｘを超えない数だけ送信する。ここではｒｍｉｎ＝２であるので、各列あたりの受信バッファ入力１１０６における消失パケット１１１２が２個以下であれば、被伝送パケットは復元可能であり、消失訂正パケット１１１４として復元された被伝送パケットが復号後出力１１０７として出力パケット選択部１２２５へ入力される。出力パケット選択部１２２５は、第十二の実施形態と同様に受信器出力１１０８を出力する。
【０２２３】
上記のように処理することで、出力パケットバッファ部１２０４は、同一列の出力バッファＢＵＦｏｕｔにおける各行の先頭からのシンボル位置が等しいＶシンボルの中で、無効シンボルの数が最小冗長数以上となるように、出力バッファＢＵＦｏｕｔそれぞれにおける被伝送データの設定位置を調整する。
また、上記のように処理することで、送信器パケット出力部１２０５は、出力バッファＢＵＦｏｕｔの各列について生成したパケットを、同一列の入力バッファＢＵＦｉｎにおける各行の先頭からのシンボル位置が等しいＶシンボルに含まれる有効シンボルの数と最大冗長数の上限とを加算した数を超えない数だけ送信する。
【０２２４】
（第十七の実施形態）
本実施形態では、最小冗長数ｒｍｉｎを入力パケットによって決定する。本実施形態のパケット冗長伝送システムの構成は、図１８に示すパケット冗長伝送システムの構成と同様である。以下、第十二の実施形態、第十三の実施形態との差分を中心に説明する。
符号化器入力バッファ部１２０１は、各被伝送パケット１１１０に含まれる（あるいは、付加されている）冗長数の指定値を取得する。もしくは、符号化器入力バッファ部１２０１は、ヘッダ情報と冗長数との対応表を保持しており、被伝送パケット１１１０に設定されている冗長数をその対応表から取得する。入力バッファＢＵＦｉｎの列Ｃに存在する被伝送パケット１１１０について取得した冗長数の最大値をＭＡＸ（ｒｍｉｎ［Ｃ］）と表す時、符号化器入力バッファ部１２０１は、該当列Ｃの空きバッファ数≧ＭＡＸ（ｒｍｉｎ［Ｃ］）となるように、入力バッファＢＵＦｉｎに設定されている被伝送パケット１１１０の再配置を行う。
【０２２５】
図２４は、最小冗長数ｒｍｉｎを入力パケットによって決定する場合の送信器１２００の動作について説明するための図である。
同図においては、パケット入力１１０１を各被伝送パケット１１１０の冗長数指定値を考慮して再配置する動作の１例を示している。第十二の実施形態と同様に、被伝送パケット１１１０の冗長数指定値を考慮しないで入力バッファＢＵＦｉｎに設定した場合、入力バッファ設定１１０２に示すように、各列の空きバッファ数１７０１の中で、その列に設定されている被伝送パケット１１１０の冗長数指定値よりも小さい場合が存在する（例えば、２列目）。
【０２２６】
そこで、本実施形態の符号化器入力バッファ部１２０１は、入力パケットの冗長数指定値を考慮して入力バッファ設定１１０２の再配置を行った入力バッファ設定１７０２を出力する。符号化器入力バッファ部１２０１は、最初の列から順に、列の空きバッファ数がＭＡＸ（ｒｍｉｎ［Ｃ］）未満の場合には、その列の空きバッファ数がＭＡＸ（ｒｍｉｎ［Ｃ］）以上となるように、当該列に設定されている被伝送パケット１１１０を次の列に移すことを繰り返してパケットの再配置を行う。入力パケットの冗長数指定値を考慮して再配置を行った各列の空きバッファ数１７０３は、ＭＡＸ（ｒｍｉｎ［Ｃ］）以上となっている。符号化器入力バッファ部１２０１が入力バッファ設定１７０２を出力した後の動作は、符号化器入力バッファ部１２０１が入力バッファ設定１１０２を出力した後の第十二の実施形態、第十三の実施形態と同様である。
本実施形態を用いることにより、情報の重要度に応じてユーザアプリケーションがパケット単位で冗長度を選択する事が可能になるため、無駄な冗長パケットの転送を抑制できる。
【０２２７】
（第十八の実施形態）
本実施形態では、パケット冗長伝送システムは再送制御を行う。本実施形態のパケット冗長伝送システムの構成は、図１８に示すパケット冗長伝送システムの構成と同様である。以下、第十二の実施形態との差分を中心に説明する。
【０２２８】
図２５は、本実施形態のパケット冗長伝送システムの再送制御のシーケンス図である。同図においては、入力バッファＢＵＦｉｎ及び出力バッファＢＵＦｏｕｔの行数Ｖ＝６、最小冗長数ｒｍｉｎ＝最大冗長数ｒｍａｘ＝１、出力バッファ設定１１０３のある列の１行目から３行目に被伝送パケット１１１０としてそれぞれ被伝送パケットＰａ１、Ｐａ２、Ｐａ３が設定されている場合を示している。また、この列の出力バッファ設定の４行目から６行目には符号化部１２０３が算出したパリティＰａ４、Ｐａ５、Ｐａ６が設定されている。送信器パケット出力部１２０５は、被伝送パケットＰａ１、Ｐａ２、Ｐａ３と、ｒｍｉｎ及びｒｍａｘに基づく個数のパリティパケットを送信パケット１１５０として送出する。ここでは、パリティＰａ４を設定したパケットが送出されている。以下、パリティＰａ４、Ｐａ５、Ｐａ６が設定されたパケットを、パリティパケットＰａ４、Ｐａ５、Ｐａ６と記載する。
【０２２９】
受信器１２２０の復号化部１２２４は、受信器入力１１０５により、各列における受信パケット数がその列の被伝送パケット数に達した時点、つまり、その列の被伝送パケットを復号可能な数のパケットを受信した時点で復号を開始しても良い。これにより、復号化の遅延を短縮可能にする。この場合、復号化部１２２４は、該当列の未受信のパケットに対応する消失パケット情報Ｅの要素（ビット）に、消失を示す値（「１」）を設定して復号処理を行う。
【０２３０】
受信器１２２０の図示しない再送要求部は、受信器入力１１０５における各列において、最初のパケットの到着時刻１１５１からタイムアウト時刻１１５２までに受信したパケットが、該当列の被伝送パケット数に満たない場合、再送要求（ＡＲＱ（Automatic Repeat Request））パケット１１５３を送信器１２００に送信する。再送要求パケット１１５３は、受信器１２２０が受信できたパケットを示し、例えば、受信したパケットから読み出したバッファ番号を用いることができる。
【０２３１】
なお、図示しない再送要求部は、該当列の被伝送パケット数を、空き領域検出部１２０２の出力に基づいてパリティパケットＰａ４に付加されたデータ有効情報Ｕから取得する。また、最初のパケットの到着時刻１１５１からタイムアウト時刻１１５２までの時間は、ＴＣＰにおける再送タイマに相当する。
なお、再送タイマについては、例えば、V. Paxson et al. “Computing TCP'S Retransmission Timer”, November 2000 （「http://tools.ietf.org/html/rfc2988」）(参考文献２）に記載されている。
【０２３２】
送信器１２００の図示しない受信部が再送要求パケット１１５３を受け取った場合、送信器パケット出力部１２０５は、再送要求パケット１１５３が示す到着パケットのバッファ番号に対応した列について、未送信のパリティパケットＰａ５、Ｐａ６、未到着被伝送パケットＰａ１、Ｐａ３、未到着のパリティパケットＰａ４の優先順序で、（被伝送パケット数−到着パケット数＋ｒｍｉｎ）個の再送要求応答パケット１１５４を再送する。
【０２３３】
受信器１２２０の復号化部１２２４は、再送要求パケット１１５３送信前に到着したパケットＰａ２と、再送された再送要求応答パケット１１５４（パケットＰａ５、Ｐａ６、Ｐａ１）を用いて被伝送パケットを復号する。これにより、復号化により訂正しきれない消失パケット１１１２の発生への対応を可能にする。
なお、復号化部１２２４は、再送要求パケット１１５３を送出後に到着したパケットＰａ４を復号に用いても良い。また、再送処理は復号が完了するまで、複数回行っても良い。
【０２３４】
（第十九の実施形態）
本実施形態では、複数経路を用いて冗長パケット伝送を行う。本実施形態のパケット冗長伝送システムの構成は、図１８に示すパケット冗長伝送システムの構成と同様であるが、送信器１２００及び受信器１２２０は、複数経路のパケット伝送路１２１０である並列伝送路により接続される。以下、第十二の実施形態との差分を中心に説明する。
【０２３５】
図２６は、複数経路を用いた冗長パケット伝送を説明するための図である。ある列の入力バッファ設定１１０２の１、２、４行目にそれぞれ、被伝送パケットＰｂ１、Ｐｂ２、Ｐｂ４が設定されている。この場合、当該列の出力バッファ設定１１０３の１、２、４行目にはそれぞれ、被伝送パケットＰｂ１、Ｐｂ２、Ｐｂ４が設定され、３、５、６行目にはパリティＰｂ３、Ｐｂ５、Ｐｂ６が設定される。送信器パケット出力部１２０５は、当該列の出力バッファ設定１１０３の各行の設定内容のＰｂ１〜Ｐｂ６をそれぞれ設定した送信パケットを生成する。送信器パケット出力部１２０５は、各送信パケットを、送信器１２００及び受信器１２２０間の並列伝送路１１６０の中で行毎に割り当てられた経路に送出する。これにより、経路障害に対する耐性を向上させる。
【０２３６】
経路障害により伝送路で消失した消失パケット１１６１がある場合においても、受信器１２２０において、被伝送パケット数個の任意の送信パケットから元の被伝送パケットＰｂ１、Ｐｂ２、Ｐｂ３を復元する事が可能である。同図の例においては、Ｐｂ１〜Ｐｂ３がそれぞれ設定された送信パケットが消失パケット１１６１となり、Ｐｂ４〜Ｐｂ６がそれぞれ設定された送信パケットを受信器１２２０において受信した場合を示している。受信器１２２０における処理は、上述した第十二〜第十八の実施形態と同様であり、受信バッファ入力１１０６には、Ｐｂ４〜Ｐｂ６がそれぞれ設定された送信パケットが設定される。被伝送パケット数は３であるので、受信器１２２０の復号化部１２２４は、符号１１６２に示すように、受信パケットから被伝送パケットＰｂ１、Ｐｂ２を消失訂正することが可能である。
【０２３７】
なお、最小冗長数ｒｍｉｎが設定されている場合、ｒｍｉｎ本の経路障害に対して被伝送パケットの消失訂正が保証される。
なお、第十三の実施形態のように、送信器１２００は、すべての送信パケットをパリティから生成してもよい。この場合、受信器１２２０において、全ての被伝送パケットの復号演算を行う必要があるが、被伝送パケット数本の経路を盗聴しないと、いかなるパケットも復号する事ができず、秘密分散が行われていることと等価なため、経路盗聴に対する耐性が高い。
なお、秘密分散については、例えば、「秘密分散システム」、日本電信電話株式会社、２０１２年（「http://event.ecl.ntt.co.jp/forum2012/info/exhibition/pdf/C-44.pdf」）（参考文献３）に記載されている。
【０２３８】
また、行毎に割り当てた経路が固定的な割当である場合を示したが、動的に経路を変更してもよい。
【０２３９】
（第二十の実施形態）
本実施形態のパケット冗長伝送システムは、多重分離及び中継を行う。
図２７は、本実施形態によるパケット冗長伝送システムの接続構成を示している。同図に示すパケット冗長伝送システムは、冗長化非対応端末１１７０−ａ、１１７０−ｂ、１１７０−ｃ、１１７０−ｄ、１１７０−ｅ、冗長化対応端末１１７１−ｆ、多重分離装置１１７２−ｇ、１１７２−ｈ、１１７２−ｊ、及び中継装置１１７３−ｉを備える。多重分離装置１１７２−ｇは、冗長化非対応端末１１７０−ａ、１１７０−ｂ、１１７０−ｃとそれぞれ非冗長化回線１１７４によって接続され、多重分離装置１１７２−ｈ、及び中継装置１１７３−ｉとそれぞれ冗長化回線１１７５によって接続される。また、多重分離装置１１７２−ｊは、冗長化非対応端末１１７０−ｅと非冗長化回線１１７４によって接続され、冗長化対応端末１１７１−ｆ及び中継装置１１７３−ｉとそれぞれ冗長化回線１１７５によって接続される。多重分離装置１１７２ｈは、非冗長化回線１１７４によって冗長化非対応端末１１７０ｄと接続される。なお、冗長化回線１１７５とは、上述した第十二〜第十九の実施形態のうち少なくともいずれか１つのパケット冗長伝送に対応したパケットを送受する回線であり、非冗長化回線１１７４とは、いずれのパケット冗長伝送にも対応していないパケットを送受信する回線である。
【０２４０】
多重分離装置１１７２−ｇは、非冗長化回線１１７４によって接続された冗長化非対応端末１１７０−ａ、１１７０−ｂ、１１７０−ｃから受信したパケットを、パケットの宛先に応じて冗長化回線１１７５毎に分離し、あるいは、冗長化回線１１７５毎に複製する。多重分離装置１１７２−ｇは、冗長化回線１１７５毎に上述した第十二〜第十九の実施形態の送信器１２００と同様の処理を行い、生成したパケットを、多重分離装置１１７２−ｈ、中継装置１１７３−ｉがそれぞれ接続されている冗長化回線１１７５に送出する。
同様に、多重分離装置１１７２−ｊは、非冗長化回線１１７４によって接続された冗長化非対応端末１１７０−ｅから受信したパケットを、パケットの宛先に応じて冗長化回線１１７５毎に分離し、あるいは、冗長化回線１１７５毎に複製する。多重分離装置１１７２−ｊは、冗長化回線１１７５毎に上述した第十二〜第十九の実施形態の送信器１２００と同様の処理を行い、生成したパケットを、中継装置１１７３−ｉ、冗長化対応端末１１７１−ｆがそれぞれ接続されている対応する冗長化回線１１７５に送出する。
【０２４１】
逆に、多重分離装置１１７２−ｇは、冗長化回線１１７５からの受信パケットに、上述した第十二〜第十九の実施形態の受信器１２２０と同様の処理を行って消失訂正を行った後、冗長化非対応端末１１７０−ａ、１１７０−ｂ、１１７０−ｃが接続された非冗長化回線１１７４に分離または複製して送出する。また、多重分離装置１１７２−ｊは、中継装置１１７３−ｉが接続されている冗長化回線１１７５からの受信パケットに、上述した第十二〜第十九の実施形態の受信器１２２０と同様の処理を行って消失訂正を行った後、冗長化非対応端末１１７０−ｅが接続された非冗長化回線１１７４、及び冗長化対応端末１１７１−ｆが接続された冗長化回線１１７５に分離または複製して送出する。
このように、エンドポイントからの非冗長パケットを集約するネットワークノード間の伝送において、冗長化及び消失パケットの復元を行う。この方法は冗長化非対応の任意の端末の収容を可能にする。
【０２４２】
また、中継装置１１７３−ｉは、冗長化回線１１７５からの受信パケットに上述した第十二〜第十九の実施形態の受信器１２２０と同様の処理を行って消失訂正を行った後、他方の冗長化回線１１７５へパケットを出力する。このように、冗長パケットの転送経路の中間に位置するネットワークノードで消失パケットの復元を行う。この方法はエンド−エンドでの消失訂正能力を向上させる。
【０２４３】
［補足事項］
なお、上述した第十二〜第二十の実施形態における送信器１２００及び受信器１２２０の各機能部は、専用のハードウェアにより実現されるか、各機能部を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することによりその機能を実現させる。なお、ここでいう「コンピュータシステム」とは、ＯＳ（Operating System）や周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷ（World Wide Web）システムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ（Read Only Memory）、ＣＤ（Compact Disc）−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。更に「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ（Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
【０２４４】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。更に、上記プログラムは、前述した機能をコンピュータシステムに既に記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０２４５】
なお、入力バッファＢＵＦｉｎは、元の入力パケットの順序に出来るだけ則して利用するのが最適であるために、上記第十二〜第二十の実施形態では、上から下、左から右に入力バッファＢＵＦｉｎを使用する場合を例示している。しかし、一定の方向であれば下から上、右から左と順番を変えたり、上下と左右を転置したりしてもよい。
【０２４６】
また、上記第十二〜第二十の実施形態では、入力バッファＢＵＦｉｎ、出力バッファＢＵＦｏｕｔ、受信バッファＢＵＦｒｃｖのバッファ長が固定長である場合を例示しているが、可変長であってもよい。
また、送信器１２００は、データ有効情報をパリティパケットとは別に受信器１２２０に送信してもよい。
【０２４７】
上記第十二〜第二十の実施形態では、符号化部１２０３を実現する符号化エンジン、復号化部１２２４を実現する復号化エンジンが、ハードウェア、コプロセッサ、ＧＰＵ（Graphics Processing Unit）などの独立のモジュールにより実装される場合、バッファの設定内容はコピーを前提とする。つまり、入力バッファＢＵＦｉｎから出力バッファＢＵＦｏｕｔに設定内容をコピーする。しかし、各機能部が全てソフトウェアにより実現される場合、送信器１２００は、入力バッファＢＵＦｉｎの設定内容へのポインタを渡し、出力バッファＢＵＦｏｕｔには設定内容をコピーしないことを前提として動作するようにしてもよい。例えば、入力パケット情報に対しては、入力バッファＢＵＦｉｎ内での被伝送パケットの設定内容へのポインタ（バッファ番号、アドレス等）及びバッファ内での先頭シンボル位置を出力バッファＢＵＦｏｕｔに設定し、また、パリティ情報に対しては、符号化部１２０３内部のバッファへのポインタ及びバッファ内での先頭シンボル位置を出力バッファＢＵＦｏｕｔに設定してもよい。
【０２４８】
また、各列あたりのパリティパケットの最大数を示し、パケットレートが低いときに過剰な冗長化を避けるために用いる最大冗長数ｒｍａｘは、例えば、アプリケーションやＳＬＡ（service level agreement）に基づく運用上の規定に従って設定される。
【０２４９】
［効果］
以上説明したように、本発明の第十二〜第二十の実施形態は、同数の被伝送データとパリティとを合わせた中の半数のデータにより被伝送データを復号可能な符号化率０．５の符号化方式であるＭＤＳ符号の特異性に着目し、送信器は、このＭＤＳ符号により被伝送データを符号化してパリティを生成することが特徴である。送信器は、この符号化を行う際に、送信器における被伝送データの到着揺らぎに伴う符号化遅延を抑制するために、到着していないパケットに対応するデータは無効なシンボル（０）によりパディングする。このとき、送信器は、符号化の際に冗長度を落とさないために、第十五の実施形態のように、各行の被伝送データのシンボル位置の重なりが小さくなるようにパティングすることもできる。送信器は、符号化したデータ又はパリティの少なくともいずれか一方を設定したパケットをパケットインターリーブして送信する。受信器は、送信器から受信したパケットに含まれるデータ又はパリティから被伝送データを復元する。
【０２５０】
従来のＦＥＣにおいては、ＦＥＣブロックすべてに有効な情報が満たされるまで符号化が行われないため、変動レートの場合には最大遅延時間は転送レートに反比例し、バースト入力に関してはタイムアウトの機構を別に用いないと、最大遅延時間の保証はない。
しかし、上述した第十二〜第二十の実施形態によれば、入力データ／パケットの無い時刻に関しては固定長の入力バッファに無効なシンボルを挿入する事により、変動レートもしくはバースト到着のパケット入力に対しても、常に一定時間間隔で符号化を行うことができる。そのため、過剰な遅延を発生させずに、パケット冗長化によるパケット消失訂正、もしくは複数経路によるパケット伝送における経路障害に対する消失訂正が可能になる。
【０２５１】
また、従来のＦＥＣにおいては、冗長度を変更するためには符号化・復号化行列を変更しなくてはならないため、冗長度の種類分の符号化・復号化行列を収容するメモリや演算回路を必要としていた。
しかし、上述した第十二〜第二十の実施形態によれば冗長度は各列における空き領域の割合で決まるため、１種類の符号化・復号化行列、符号化回路、復号化回路しか必要としない。また、符号化回路への冗長度の設定等、外部アプリケーションから特別な制御をすることなく、冗長度を変更する事が可能である。すなわち、パケット入力１１０１へのパケットレートを小さくすれば空き領域の割合が増えるため冗長数が大きくなり、逆にパケットレートを大きくすれば空き領域の割合が減るため冗長数が小さくなる。言い換えれば、アプリケーションは送出パケットレートを変更するだけで、パケット伝送における冗長度の設定は自律的に行われると言う事である。
【０２５２】
なお、第一から第十一の実施形態の２項演算子記号と第十二から第二十の実施形態の記号＊は同じ意味である。
また、第一から第十一の実施形態の記号ＦはＦＩＦＯの読み出し信号を意味し、第十二から第二十の実施形態の記号Ｆは行列を意味する。
また、第一から第十一の実施形態では、行列Ａ，Ｂ，Ｃ，Ｄ等にはレーン数を示すサフィックスＲもしくはサフィックスＲ×Ｒを明記している。一方、第十二から第二十の実施形態では、行列Ａ，Ｂ，Ｄ，Ｆ等のサフィックス表記を記載していない（省略している）が、第一から第十一の実施形態と同様である。第一から第十一の実施形態と同様に、第十二から第二十の実施形態でサフィックスを記載してもよいし、第十二から第二十の実施形態と同様に第一から第十一の実施形態でサフィックスを省略してもよい。
【０２５３】
また、上記の各実施形態は、可能な限り組み合わせる事が出来る。
【０２５４】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【産業上の利用可能性】
【０２５５】
本発明においては、データ符号化側とデータ復号化側の間が複数の物理媒体もしくは論理媒体を用いて接続される場合における媒体の破損や修復不能な誤りによるデータ消失に対して、冗長度の動的な設定を可能にすることで、縮退動作時にも消失訂正を可能にすることや、情報伝送に供しない帯域を冗長化に用いることで、必要とする物理媒体を削減する事を可能にする。
【符号の説明】
【０２５６】
１０１  符号化器
１０２  並列媒体
１０３  復号化器
１０４  デフレーマ
１０５  ＭＤＳ符号化演算器
１０６  ＭＤＳ復号化演算器
１０７  フレーマ
１０８  入力並列データ
１０９  出力並列データ
１１０  状態ベクトルＵ（ｔ）（入力並列レーンの使用状況）
１１１  ベクトルＭ（ｔ）（有効な入力並列データ）
１１２  送信情報Ｙ（ｔ）（並列媒体への送信情報）
１１３  受信情報ベクトルＹ’（ｔ）（並列媒体からの受信情報）
１１４  ベクトルＭｓｕｂ（ｔ）（再生した並列データ）
１１５  消失ベクトルＥ（ｔ）（訂正不能な誤り情報）
１２０  パリティＳ（ｔ）（ＭＤＳ符号化演算器の出力）
１２１  セレクタ
１２２  ＭＤＳ復号化演算器
１３０  パケット化機能部
１３１  逆パケット化機能部
１３２  Ｗｐ（ｔ）（パケット化機能部出力）
１３３  Ｒｐ（ｔ）（逆パケット化機能部入力）
１３４  パケット
１３５  誤り検出／訂正符号
１４０  ＦＩＦＯバッファ
１４１  シェーパ制御回路
１４２  ポリシング制御回路
１４３  ＦＩＦＯ使用率
１４４  保証値ｒｍｉｎ（冗長度の下限）
１４５  制限値ｒｍａｘ（冗長度の上限）
１１０１  パケット入力
１１０２  入力バッファ設定
１１０３  出力バッファ設定
１１０４  送信器出力
１１０５  受信器入力
１１０６  受信バッファ入力
１１０７  復号後出力
１１０８  受信器出力
１１１０  被伝送パケット
１１１１  パリティ
１１１２  消失パケット
１１１３  消失訂正不能パケット
１１１４  消失訂正パケット
１１１５  送出しないパリティ
１１３０−１、１１３０−２、１１３０−３  パケット長がバッファ長Ｌを超えない被伝送パケット
１１３１  パケット長がバッファ長Ｌを超える被伝送パケット
１１３１−１、１１３１−２  フラグメントパケット
１１３２  パディング情報
１１５０  送信パケット
１１５１  パケット到着時刻
１１５２  タイムアウト時刻
１１５３  再送要求パケット
１１５４  再送要求応答パケット
１１６０  並列伝送路
１１６１  消失パケット
１１６２  消失訂正
１１７０−ａ、１１７０−ｂ、１１７０−ｃ、１１７０−ｄ、１１７０−ｅ  冗長化非対応端末
１１７１−ｆ  冗長化対応端末
１１７２−ｇ、１１７２−ｈ、１１７２−ｊ  多重分離装置
１１７３−ｉ  中継装置
１１７４  非冗長化回線
１１７５  冗長化回線
１２００  送信器
１２０１  符号化器入力バッファ部
１２０２  空き領域検出部
１２０３  符号化部
１２０４  出力パケットバッファ部
１２０５  送信器パケット出力部
１２１０  パケット伝送路
１２２０  受信器
１２２１  パケット入力バッファ部（受信部）
１２２２  復号化器入力バッファ部
１２２３  パケット消失検出部
１２２４  復号化部
１２２５  出力パケット選択部
１３００  最適化前の符号化器入力バッファ列
１３０１  最適化前の各シンボル列の無効シンボル数
１３１０  最適化後の符号化器入力バッファ列
１３１１  最適化後の各シンボル列の無効シンボル数
１７０１  各列の空きバッファ数
１７０２  入力パケットの冗長数指定値を考慮して再配置を行った入力バッファ設定
１７０３  入力パケットの冗長数指定値を考慮して再配置を行った各列の空きバッファ数
【図１】
2014045906.tif 000105
【図２】
2014045906.tif 000106
【図３】
2014045906.tif 000107
【図４】
2014045906.tif 000108
【図５】
2014045906.tif 000109
【図６】
2014045906.tif 000110
【図７】
2014045906.tif 000111
【図８】
2014045906.tif 000112
【図９】
2014045906.tif 000113
【図１０】
2014045906.tif 000114
【図１１】
2014045906.tif 000115
【図１２】
2014045906.tif 000116
【図１３】
2014045906.tif 000117
【図１４】
2014045906.tif 000118
【図１５】
2014045906.tif 000119
【図１６】
2014045906.tif 000120
【図１７】
2014045906.tif 000121
【図１８】
2014045906.tif 000122
【図１９】
2014045906.tif 000123
【図２０】
2014045906.tif 000124
【図２１】
2014045906.tif 000125
【図２２】
2014045906.tif 000126
【図２３】
2014045906.tif 000127
【図２４】
2014045906.tif 000128
【図２５】
2014045906.tif 000129
【図２６】
2014045906.tif 000130
【図２７】
2014045906.tif 000131
【国際調査報告】
2014045906.tif 000132
2014045906.tif 000133
2014045906.tif 000134
2014045906.tif 000135