JP4392004B2 - パケット回復のための符号化および復号化技術 - Google Patents

Description

本発明は、一般的にはデジタル通信で用いられるパケットの回復に関し、より詳細には、パケット回復のための符号化方法、復号化方法、符号器、および復号器に関する。

有線あるいは無線のネットワーク・アプリケーションにおいて、パケット回復のための符号化技術およびそれに対応する復号化技術はますます重要になってきている。その理由は、データ転送速度が高くなるにしたがって、ヘッダー/同期化パターンなどの検出エラーやネットワークスイッチに一時的に情報が集中することによって引き起こされる輻輳のために、パケット損失がより頻繁に起こる一方で、従来の再送を基本にしたパケット回復の方式が、性能とバッファ管理に与えるオーバーヘッドをより大きくしてしまうからである。

こうした問題に対して、従来技術として、インターリーブされたリード・ソロモン(RS)消失訂正符号のようなブロック符号を利用したフレーム単位で符号化を行う技術がよく知られている（非特許文献１）。しかし、この従来の技術では、与えられたフレーム内に消失パケットが存在しないときに、冗長パケットは使われることなく無駄になってしまう。この非能率さは符号長がより長くなることにより改善されるが、復号に関わる計算量も同時に大きくなってしまう。

他の従来技術として、パケット回復に特化した非組織符号を用いて、送信側と受信側で共有されたソース・ノードとチェック・ノードからなるグラフ構造にもとづいて復号を進める方法がある（非特許文献２）。この方法は、符号化率の点で効果的で、復号もほぼ線形時間で可能なので効率的であるが、符号長がある一定長さ（量）以上でないと訂正効率は良くない。また、グラフ構造がランダムなため、ハードウエアによる実装効率が高くない。したがって、応用範囲は、ソフトウエアでの符号化・復号化を使ったストリーミング・メディアやデータ配布への応用に制限されている。

さらに、他の従来技術として、(n、n-１、m)の畳み込み符号を用いたパケット回復方法がある（非特許文献３）。この方法では、ブロック符号を用いたフレーム・ベースの技術よりもよりも柔軟に消失パケット回復を行うことが出来る。しかし、この方法は、バイナリ畳み込み符号に基づくため、ビットごとの消失訂正が必要なために、シンボル単位の復号が出来ない。そのため、ハードウェアによる実装のためには、多数の復号器を並列に並べられる必要がある。

上述した従来技術では、パケット回復の効率化を進めた場合、符号長が長くなる、あるいは復号回路の実装が複雑になってしまう等の問題がある。また、冗長情報を付加しすぎると、そのことによって新たな輻輳が発生したりするので、パケット回復の効率化は非常に重要な問題である。
Nonnenmacher, E. W. Biersack, and D. Towsley, ‘’Parity-basedloss recovery for reliable multicast,'' IEEE/ACM Trans. Networking, vol. 6, pp.349.361, Aug. 1998. Luby, M. Mitzenmacher, A. Shokrollahi, and D. Spielman, ‘’Efficienterasure correcting codes,'' IEEE Trans. Inform. Theory, vol. 47, pp. 569.584,Feb. 2001. M. Arai, A. Yamaguchi, K. Iwasaki, ‘’Method to Recover InternetPacket Losses Using (n, n - 1, m) Convolutional Codes,'' IEEE Dependable Systemand Network, pp. 382-389, 2000.

本発明の目的は、適量な冗長情報を有効に活用しながら、パケットの回復率を向上させることができる新しい符号化方法およびそれに対応する復号方法、さらにはこれらの方法を実現するための新しい符号器および復号器を提供することである。

本発明では、互いに異なる複数のブロック符号を部分的にオーバーラップした形で組み合わせて構成する新たな符号化方式である、Partially-Overlapped Block (POB)符号、を開示する。また、この符号化方式に対応する復号化方法を開示する。さらに、この符号の消失訂正能力を利用した複数パケットの回復手法を開示する。本発明によれば、隣接するフレームの冗長情報をうまく再利用することによって、復号アルゴリズムの漸近的な計算量を増大させることなく、１フレームあたり付加された冗長パケットの数よりも多くのパケットの回復を可能とする。

本発明のPOB符号を生成するために、フレームを検知する手段、重なり合う部分をサブフレームとして、サブフレームごとにブロック符号を変えてパリティを生成する手段を具備する符号器を提供する。またフレームを検知する手段、重なった個数分のサブフレームを記憶する手段、サブフレームごとに異なる検査行列でシンドロームを生成する手段、パケット誤り位置および数の情報から誤り訂正するパターンを判断する手段、誤りを計算する手段、誤りを訂正して復号する手段、訂正された情報からシンドロームを再計算する手段を具備する復号器を提供する。

本発明について図面を参照しながら以下に詳細に説明する。本発明のPOB符号では、図１に示すような符号構成を用いる。１フレームあたり、n個のシンボルがL回インターリーブされているような構成を仮定したときに、それぞれのフレームの符号語wが、冗長シンボルも含めてs個のサブフレーム(w_h)に分割できるとする。(sがnおよびrの両方を割り切ると仮定する)。言い換えれば、n/s-シンボルのサブフレームそれぞれは、r/s冗長シンボルを含むとする。

互いに異なるs個の(n、n-r/s)非バイナリ・ブロック符号は、次のパリティチェック条件を満たすように符号化される。

ここで、

H：生成行列、w：符号語、α：ガロア体の原始元、s：ブロック符号の数（サブフレーム分割数に等しい）、n:ブロックサイズ、k:情報サイズ、
ただし、k=(n-r)/s、r：パリティサイズ、j：サブフレームの番号それぞれの符号は、必ずしも現在のフレームではなく、j番目のサブフレームのシンボル集合
w_jとそれ以前のs-１個のサブフレームにあるシンボル集合、w_j-s-１、w_j-s-２、…w_j-１
の間に用いられる。iは、符号化の条件の識別のための添え字で、jr/s=<i<(j+１)r/sを満たす。h*は、h番目のサブフレームのフレーム内での相対的な位置（h*=0,1,2,…,s-1）を示す。

復号は、以下のステップで行う。あるｊ番目のサブフレームに注目する。それ以前のs-１個のサブフレームは、パケット誤りがないか、もしくは、すべて訂正されていると仮定した場合、今回提案する符号の復号化は、ブロック符号の消失訂正に類似している。シンドローム計算から始まり、消失位置の情報を頼りに消失したパケットのシンボル情報を求める。j番目のサブフレームの末端に付加されているi番目のシンドロームS_i(jr/s=<i<(j+１)r/s)は、H_iと受信データw_j-s-１,w_j-s-２,…,w_jを使うことによって計算される。

j*や*が付加された他の記号も、h*と同様に定義される。

サブフレーム jを先頭とするh サブフレームの失われたパケットの総数がp=rh/sよりも少ない場合は、失われたパケットは常に回復可能である。例えば、現在のサブフレームに続くh-１
サブフレームでパケットが失われていなければ、p個までパケットを回復することが出来る。言い換えれば、q(q=<p)パケットデータb_e０,b_e１,
…b_eq-１がロケーションe_０,e_１,…e_q-１で消失していた場合は、RS符号の消失訂正と類似している以下の線型方程式を解くことによってパケットを回復することが出来る。

一旦、現在のサブフレーム内で失われたパケットがすべて回復されれば、シンドロームは、それぞれのサブフレーム境界線で再計算される必要がある。このシンドローム再計算ステップがフレームあたりの最大訂正パケット数をｒ以上としながら、計算にかかるコストを増加させるのを防ぐことが出来る。再計算された新しいシンドロームS_i ^’は、次の式に従って計算される。

α：ガロア体の原始元、b_e０、b_e１、・・・b_eq-１：q(q=<p)個のパケット情報、
e_０,e_１,…,e_q-１:パケット内の位置

サブフレーム中の失われたパケットの総数hがpより大きいときは、失われたパケットを回復することができない。この場合、連続する（２s-１）個のサブフレームは、パケット回復操作を再スタートさせるために、正しい必要がある。復号にかかる漸近的な計算量は、ブロック符号の復号化と変わらないとしても、現実的には、サブフレームでの誤り数のパターンに応じて復号アルゴリズムを変更しなくてはならないため、復号器サイズが現実的になるように復号回路を適切に設計することは重要である。特に、フレーム中のどこに現在訂正しようとしているサブフレームがあるかによって、実際の復号の計算は影響を受ける。能率的なハードウェア実装のためには、この点を注意深く検討する必要がある。乗算器の数を削減することは、乗算の数の削減よりも、回路サイズ縮小において重要である。

図２にPOB符号の一実施例の符号構成を示す。n=１５０のシンボル・フレームは、s=３ サブフレーム(それぞれn/s=５０シンボルを含む)に分けられ、そして、(１５０,１４９)RS符号(パリティー・チェック条件が１、α、α²によってそれぞれ生成される)を３個を使ってパケット回復を行う。より具体的には、

j番目のサブフレームのデータw_jは、以下の関係を満たす。

ここで、どのパリティチェック条件を使うかを示す添え字iは、ｊ番目のサブフレームのフレーム中の相対位置j*に従って変化する。例えば、
i=j*
と変化させることが出来る。

表１に、パケット回復が出来る場合を、サブフレーム j、j+１とj+２で失われたパケットの数との対応関係で示す。フレーム中でのサブフレームの場所j*によって(位置０、１、２)、ロケーションeで消失したシンボル値b_eは、もし必要ならば他の消失場所e’、e’’を使うことで計算することができる。

ケースCの場合、eとe‘が同じサブフレームにあるが、e’‘は次のサブフレームにある。

図２で示された本発明での構成例をもとに、他の従来技術例と比較することにより本発明の効果を図３に示す。図３で、入力のパケット損失確率をｘ軸に、各種のパケット回復機構を使った後のパケット損失確率をｙ軸に示す。本発明の方式を、（１５０，１４７）のRS符号を用いた方式と既存の方式と比較すると、コードレートは同じにも関わらす、既存の方式では、フレームの最大限の取り戻せるパケットの数は最大3個であるが，本発明では、最大5個のパケットを回復することができる。本発明方式を、（５０，４８）のRS符号を用いた場合と比較すると、本発明方式では、冗長パケットの量が半分にもかかわらず、パケット損失割合が小さい領域では、ほぼ同等の回復能力があることが示される。

また、非特許文献２の手法と比較して、ランダムなLDPC符号ではなく、ブロック符号をベースに構成されているため、ハードウエアの実装に向いており、また、比較的短い符号長でも効果がある。一方、本発明方式を、バイナリ畳み込み符号を用いた方式と比較すると、シンボル単位で訂正が出来るため、ビット単位のパケット回復と比較してハードウエア実装効率が良い。

次に、本発明のPOB符号に対応する復号方法、符号器および復号器について説明する。最初にPOB符号方式について具体例を用いて再度説明する。図４に示してあるのは、１フレームが３つのサブフレームで構成されており、１つのブロック符号が３つのサブフレームに対してかけられている場合の図である。用いるブロック符号は３つである。フレームは複数のパケットで構成されており、図の縦がパケットの幅（ビット）である。このような構成の情報を符号化する場合に、（１）は１番目のサブフレームから同一フレームの３番目のサブフレームまでに対してブロック符号がかけられている。（２）は２番目のサブフレームから次のフレームの１番目のサブフレームまでに対して、別のブロック符号がかけられている。（３）は３番目のサブフレームから次のフレームの２番目までのサブフレームまでに対して、さらに別のブロック符号がかけられている。このように異なる３つのブロック符号を異なる範囲にかけることで、たとえば、３番目のサブフレームは（１）、（２）および（３）が部分的に重なっていることになる。

図５は図４の構成でパリティを生成した際に、（１）のパリティを３番目のサブフレームの後ろに、（２）のパリティを１番目のサブフレームの後ろに、（３）のパリティを２番目のサブフレームの後ろに付加した場合の、符号化後の構成図である。もちろん、パリティをどこに付加するかは任意である。

図６は、図５で示された符号語を復号する時の説明図である。（１）は１番目のサブフレームから３番目のサブフレームの後ろのパリティまでの範囲を示す。（２）は２番目のサブフレームから次のフレームの１番目のサブフレームの後ろのパリティまでの範囲を示す。（３）は３番目のサブフレームから次の２番目のサブフレームの後ろのパリティまでの範囲を示している。それぞれに対して、図４の対応する番号で用いたブロック符号に対応する検査行列を用いることで、それぞれのシンドロームが計算できる。従って、１つのサブフレームに対してその情報を含むシンドロームが３つ生成される。この３つのシンドロームを用いて、復号を行うことでパケット回復を行う。

通常のブロック符号の場合、（１）、（２）および（３）はすべて同じ範囲の情報に対してブロック符号をかけているが、図のように部分的に重なりながら、範囲をずらしてブロック符号をかけることで、フレーム単位での誤り訂正能力が上がる。すなわち、同一のサブフレームに対して、それを含みながら、範囲の違うブロック符号があるおかげで、続く２つのサブフレームに誤りがない場合に、最初のサブフレームは最大の誤り訂正能力を発揮できる。これは誤りがないサブフレームのパリティ情報が、続くサブフレームの誤り訂正に対して有効に使えることを意味する。このことは、訂正可能な誤りがあった場合にシンドロームを再計算することで、より強く有効になる。また、具体的な復号方法は、用いているブロック符合の復号方法と似た手法を用いることができるが、何番目のサブフレームを訂正しているか、関連するシンドロームに誤りをいくつかあるかによって場合分けを行いながら復号する必要がある。

POB符号方式においては、パケット誤り情報が別途受信あるいは検知することができるときに、非常に強力な符号方式である。パケット誤り情報とは、フレーム内におけるパケット単位での誤りがあることを示す情報であり、具体的にはパケット誤りの位置および数を表す。これらは、後述のようにパケット検出手段において、パケットを正しく認識できなかった場合にフラグとして生成されたり、あるいは、復号器の前段における別のシステムにおいて検知されたものを受信したりしてもよい。これらはパケットに同期して受信または検知できるため、パケット誤り情報を計算する手段において、パケット誤り位置の記憶およびサブフレーム内でのパケット誤りの数をカウントすることができる。

＜符号器の構成＞
本発明の符号化のフローを図７に示す。まずフレーム単位で送信されてくる信号を受信する（a）。受信した信号から情報のフレームを検出する（b）。フレームを検出したあと、所定の数に分割されたサブフレームを検出する（c）。サブフレームを構成しているパケットを検出する(ｄ)。サブフレームに関連付けられた異なるブロック符号を、用意したブロック符号の数だけパリティを並行に生成する(e)。最後に生成されたパリティと元の情報とを出力する（ｆ）。

図８に図７のフローに対応する符号器１００の構成例を示す。フレーム検知手段１０は、情報の中にフレームの先頭を示すヘッダーが含まれている場合には、それをパターンマッチングで検出し、フレームの先頭に同期したコントロール信号が別途得られる場合には、それを利用する。サブフレーム検知１２およびパケット検知手段１４も同様である。特にフレーム構造が予め決められている場合には、フレーム先頭に同期したカウンタによってサブフレームおよびパケットを検出することもできる。１つのサブフレームに対して、異なるブロック符号が複数重なって符号化されるため、使用するブロック符号の数と同じだけのパリティ生成手段が必要になる。ただし、ブロック符号の選び方には依存しないことに注意を要する。具体的な回路構成としては、選んだブロック符合で生成するパリティのビット数あるいはシンボル数だけ必要になる。図８では、これを重ねて表示している。これらは並行して処理される。パリティ生成手段としては、帰還部を持つレジスタ１６を対応するブロック符号の数だけ用意し、並列に設置する。帰還レジスタ１６への入力は、レジスタの最初からでも後ろからでもよい。帰還レジスタ１６の構成は用いるブロック符号の種類に寄って決まる。サブフレーム検知した結果がシフトレジスタの終わりのセレクタ１８に連結され、どのサブフレームの後にどのパリティを出すかが決定される。最終段のセレクタ２０は情報とパリティとを任意のフォーマットで出力するためのものである。

＜復号器の構成＞
本発明のPOB符号方式で符号化された情報を受信し、復号するための復号器は、例えば次のような構成を備える。
１．フレーム検知手段
２．サブフレーム検知手段
３．パケット検知手段
４．サブフレームで関連付けられた複数の符号化すべき受信情報ブロックごとに異なり、かつ符号化で使用したブロック符号に対応する検査行列を用いてシンドロームを計算する手段。
５．注目しているサブフレームより時間的に前のサブフレームにおいて誤り訂正が可能な場合、それに対応するシンドロームを再計算して正しいシンドロームを求める手段
６．パケット誤り情報であるパケット誤り数およびパケット誤り位置を検出・受信する手段
７．サブフレームの位置、パケット誤りの数から誤り訂正可能かどうかを判断し、誤り訂正可能な場合に、再計算されたシンドロームから、誤りを生成する手段。
８．誤り訂正が可能である場合に、生成された誤りから、正しく復号する手段。
１０．出力手段。

本発明の復号化のフローを図９に示す。図１０に図９のフローに対応する復号器２００の構成例を示す。信号を受信した後（a）、最初にフレームを検知する（b）。次にサブフレームを検知する(ｃ)。サブフレームを構成しているパケットを検知する（ｄ）。パケット誤りが検知されると、パケット誤りレジスタにパケット誤りの数と位置が格納され、サブフレーム内における誤りの数がカウントされる（３６）。これらは誤りを求める式の係数計算手段４８と誤り訂正可否判断手段５０（図１０）に入力される。一方、サブフレームに関連付けられた情報ブロックに対して、符号化で使用したブロック符号に対応する検査行列を用いてシンドロームを計算する（e）。１つのサブフレームは複数のブロック符号に含まれているため、シンドローム計算は、符号化のときのパリティ生成と同様に、使用するブロック符号と同じ数だけ必要となる。シンドローム計算は並行して行われる。符号器の構成で説明したように、POB符号方式において、使用するブロック符号の選び方には依存しないため、１つのブロック符号で用いるシンドロームは複数の場合もある。従って具体的な回路構成としては、１つのブロック符号で用いるシンドロームの数だけ必要になる。

シンドロームが計算されたあと、注目しているサブフレームを含むシンドロームのうち、時間的に前のサブフレームの誤り訂正でも用いたシンドロームは、時間的に前のサブフレームが誤り訂正可能であった場合、シンドロームの再計算（f）を行う必要がある。このようにして、注目するサブフレーム以前の情報を含んだシンドロームをすべて再計算(f)してから、そのシンドロームを用いて誤りを求める(g)。次に誤り訂正可能かどうかを判断する(i)。もし誤り訂正が不可能な場合には、誤りを含んだ情報であることを知らせるためのフラグを立てる(j)。誤り訂正可能であれば、誤りを求め、訂正復号を行う(k)。このとき訂正可能な場合には上述の通り、次のサブフレームを訂正する場合のシンドロームの再計算に、訂正するときに用いた誤りを帰還させる(ｍ)。最後に出力手段によって出力する（l）。なお誤りフラグは出力しなくてもよい。

図１０の復号器２００は、図８の符号器の場合と同様に、フレーム検知手段３０、サブフレーム検知手段３２、パケット検知手段３４を有する。パケット生成手段３８は、パケットごとにシンドロームを計算する。符号化で用いたブロック符号に対応する検査行列は、線形帰還シフトレジスタで構成できる。したがって、パケット生成手段として、相異なるブロック符号の数だけシンドローム計算のための線形帰還レジスタ３８を用意する。それとは別に入力情報はバッファ４４に記憶される。複数のシンドロームはシンドローム・レジスタ４０に保存される。前のサブフレームを誤り訂正した結果を用いて、シンドロームの再計算（４２）が行われる。そして、正しいシンドロームが誤りを求める式の係数計算手段４８へと入力される。ここで、シンドローム・レジスタ４０からシンドローム再計算（４２）までのデータはシリアルで送ってもよいし、パラレルで送ってもよい。

一方、パケット検出手段３４でパケット誤りが検出された場合または、復号器の前段回路においてパケット損失の情報が受信された場合には、パケットの誤り位置を保存し（３６）、同時にサブフレーム内でのパケット誤りの数をカウントする（３６）。パケット誤り位置の情報は誤りを求める式の係数計算手段４８に入力され、再計算されたシンドローム（４２）と合わせて係数の計算が行われる。パケット誤り数は訂正可否判断手段５０に入力され、誤りが訂正可能かどうかの判断を行う。誤り訂正の可否判断は後述のように、POB符号の構成から決まる。誤り訂正が可能な場合に、誤り生成手段５２は誤りを計算する。その結果、バッファ４４の情報を訂正（５４）して出力する。このとき、誤りがあれば、誤りレジスタ５８に保存し、前述のように次のサブフレームの誤り訂正のために、セレクタ４６を経由してシンドローム再計算のためのフィードバック６０を行う。なお、図１０で、誤りレジスタ５８を除去し、シンドローム・レジスタ４０の内容を、シンドローム再計算（４２）結果をフィードバックさせることにより、更新するように構成してもよい。それにより、回路規模を削減することができる。

ここで、既出の表１のパケット回復が出来る場合についてさらに説明する。１つのサブフレームに対して重なり合う３つのパリティがあり、かつパケット誤りの位置情報がある場合には、サブフレームあたり最大で３つのパケット回復が行える。しかし、そのためには、次のサブフレーム（ｊ＋１）およびその次のサブフレーム（ｊ＋２）で誤りがないことが必須である（ケースD）。誤り訂正が可能な組み合わせはケースAからケースDであり、たとえば現在のサブフレームに誤りが１つしかない場合には、他のサブフレームの誤りの数によらず訂正は可能である。さらに、これらの４つの誤り訂正可能な場合において、現在のサブフレームがフレーム内の何番目のサブフレームかによって、誤りを生成するための係数が異なってくる。最大３つの誤りに対して、シンドロームが３つあるので、３つの連立方程式を解くことになる。この解は、ケースA〜Dに対して、解析的に解くことができる。また、現在のサブフレームがフレーム内の何番目かによって、係数が異なってくる。これらを誤り数から判断し、誤りの係数を求める。

誤りの係数を求めるには、分母の計算と分子の計算があり、特に分母の逆数を計算する回路が大きくなる。そのため、分子の計算と分母の逆数計算を共通化し、さらに分子と分母の逆数の乗算部分を共通化することで、回路規模を著しく小さくできる。その回路規模を小さくできる例を図１１に示す。またシンドロームは分子の計算にのみ関与するので、シンドロームの入力は共通化された分子の計算部分に接続されてもよい。

＜ブロック符号としてRS符号を用いた場合＞
ノンバイナリーのブロック符号としてよく用いられるリード・ソロモン符号（RS符号）をPOB符号のブロック符号として用いることができる。具体的には１つのパケットをRS符号で使用するシンボル幅に分割し、パケット幅だけインターリーブするようにRS符号をかけていく。RS符号として、複数の符号を用意し、サブフレームに関連付けられた互いに部分的に重なり合う範囲に対して、異なるRS符号をかけて、パリティを生成する。

図１２にRS符号をかける際の構成を示す。１つのパケットはRS符号で使用するシンボル幅に分割されている。このようなシンボル幅で、図４の（１）、（２）、（３）に示すような範囲でRS符号の計算を行い、パリティを生成する。サブフレームの分割数は任意である。またRS符号の構成も任意である。従ってパリティも複数生成しても構わない。例として図４に示されるような、サブフレームが３個に分かれ、RS符号として（n,
n-1）符号を用いると、パリティは１つ生成される。異なる３つのRS符号として、適当なガロア体の基底であるαを用いて、1、α、α²を乗じて加算する方法を取れば、３つのRS符号は互いに異なるため、POB符号を構成することができる。特に1を根に持つRS符号は１番目のサブフレームか３番目のサブフレームに対してかけ、αを根に持つRS符号を２番目のサブフレームから次のフレームの１番目のサブフレームまでに対してかけ、α²を根にもつRS符号を３番目のサブフレームから次のフレームの２番目のサブフレームまでに対してかける。

この場合の符号化方法のフローチャートを図１３に示す。その方法に対応する符号器３００の構成を図１４に示す。図１３で、信号の受信（a）、フレーム検知（b）、サブフレーム検知(ｃ)、パケット検知（d）および出力（ｆ）は図７と同じである。図１４で図８と同じ構成は同じ符号をつけてある。ブロック符号としてRS符号を用いており、かつ、適当なガロア体GF(2^m)の原始元αを用いて、1、α、α²を符号の根として持つような、互いに異なる３つのRS符号を用意する。これらをサブフレームに関連付けられたRS符号をかけるべき範囲のサブフレーム全体に対して、パリティを生成する(e)。パリティの配置の仕方は任意であり、これらを符号化結果として出力する。用いる線形帰還シフトレジスタ１６の帰還部分には1、α、α²の乗算器７０がついており、常にこの定数倍をして帰還させることで、パリティの計算がシフトレジスタ１６で行うことができる。ただし、３つのシフトレジスタの始点はサブフレームずつずれていることに注意する。従ってサブフレーム検知した結果がシフトレジスタの終わりのセレクタ１８に連結され、どのサブフレームのあとにどのパリティを出すかが決定される。最終段のセレクタ２０は情報とパリティとを任意のフォーマットで出力するためのものである。

次に復号器について説明する。３つの異なるRS符号に対応するパリティが付加された送信情報を受信し、そこからそれぞれのRS符号に対応する検査行列でシンドロームを生成する。そのフローチャートを図１５に示す。図１５は基本的に図９と同じである。今、符号の根として1、α、α²を持つような３つのRS符号を用意したので、これらのパリティから得られるシンドロームをs0、s1、s2とすると、これらおよびパケット誤り位置情報から誤りが求められる。パケットは複数のシンボルに分割されているので、１つのフレームに対して、分割しただけのシンドロームが得られる。

図１５のフローに対応する復号器４００の構成を図１６に示す。図１６の構成は基本的に図１０と同じである。RS符号を用いた場合、シンドローム計算回路は具体的に、符号の根である1、α、α²を乗算器７０として接続した帰還レジスタ３８で構成することができる。シンドロームはレジスタに格納され、前回のサブフレームの誤り訂正の結果から、シンドロームの再計算（４２）を行って誤りを求める式の係数計算手段４８へと入力される。一方でパケット誤り情報である、パケット誤り数とパケット誤り位置が受信され（３６）、パケット誤り位置情報が誤りを求める式の係数計算手段４８へと入力される。図８で示したように、再計算されたシンドロームおよびパケット誤り位置から誤りが計算でき、またパケット誤り数の情報から表１のように、誤り訂正可能のパターンが選択される。表１のケースA〜Dおよび訂正したいサブフレームの位置から誤りを求める式は具体的に求まり、その式の係数が生成される。最後に図１１に例示される最終段の乗算器７２を通して、誤りが計算される。誤りが計算されると、パケット誤り位置およびサブフレーム位置による係数を乗じて、バッファ４４の情報に加算して誤り訂正を行う。これをパケット内のシンボルについてすべて行い、復号化結果を出力する（５６）。誤りが訂正できた場合には、誤りレジスタ５８を通して、次のサブフレームの訂正のために、シンドロームを再計算する回路（４２）へ帰還させる。

＜連接符号としてのPOB符号方式の符号器および復号器＞
POB符号方式は、パケット回復に対して非常に有効な符号方式であるが、これを外符号とした連接符号とすると、さらに強力な符号方式となる。この場合、内符号は畳み込み符号など任意の符号方式が選択できるが、主にブロック符号（ハミング符号、BCH符号、RS符号など）で構成する場合が多い。図１７にPOB符号方式を外符号とした連接符号のフレーム構成図を示す。１つのパケットに対して、１つのブロック符号がかけられ、そのパリティがパケットの末尾に付加される。従って、POB符号から見ると、内符号がかけられた符号語を１つのパケットとみなせば、これまでのPOB符号方式と同じになる。従って、この場合のフローチャートおよび回路構成は、内符号であるブロック符号の符号器と復号器が付加されたものとなる。このような内符号を付加することで、パケット内のランダムエラーに対しての訂正能力向上が期待できる。さらに、パケット誤りを確実に抽出できるため、外符号であるPOB符号方式の復号器がより小さい回路規模にすることが可能となる。また、外部からパケット誤り情報を得ずに、閉じた回路構成内で網羅することが可能となる。

図１８にフローチャートを図１９にその回路構成５００を示す。図１８において、信号の受信（a)、フレーム検知（ｂ）、サブフレーム検知（ｃ）、パケット検知（ｄ）および出力（ｇ）は図７と同じだが、パリティの生成部分（e）、(f)が大きく異なる。外符号は同じように生成するが（e）、それと並列に１パケットに対する内符号のパリティを生成する(f)。図１８では並列にしているが、内符号を先に行い、外符号を後で行う直列する方法でもよい。しかし、パケットの情報部分は外符号でも内符号でもパリティ生成に用いるため、図のように並列して処理したほうが処理速度の点で有利である。また、パリティが重なる部分については、内符号を優先する。すなわち、外符号であるPOB符号のパリティが生成されてから、そのパリティに対する内符号を生成する。最後に符号化結果を出力する（ｇ）。

図１９の基本構成は図８と同じである。図１９でも図１８のフローチャートと同様に、パリティ生成部分に特徴を持つ。フローチャートの説明と同様に、外符号であるPOB符号のパリティ生成手段８０と内符号のパリティ生成手段８２は並列して処理を行う。内符号の符号器でも外符号の線形帰還レジスタ１６と同じ線形帰還レジスタ８４を用いているが、これも外符号と同様にブロック符号を用いるときに使用する。

図２０に復号器６００の構成例を示す。符号器では、内符号器と外符号器は直列あるいは並列のどちらでも構成できる。しかし、復号器では内符号の復号器９０と外符号の復号器９２を直列に構成する。内符号９０はパケット単位で情報を扱い、任意のブロック符号で符号化されているので、一般のブロック符号の復号方式が使える。ただし、パケット誤りがあり、訂正不可能な場合には、パケット誤りの位置を検出する。また、サブフレームごとに訂正不可能であったパケット誤りがいくつあったかというパケット誤りの数も検出し、これらを出力する。外符号であるPOB符号方式の復号器９２では、パケットおよびパケット誤り情報を受信し、これらを用いて復号を行う。

＜内符号の復号器＞
図２１に内符号の復号器７００を示す。内符号としてブロック符号が用いられた場合、やはり線形帰還レジスタ３８を組み合わせることで、シンドロームの計算が行える。内符号はパケット内のランダムエラーを訂正する目的で使用することが多いので、多くの場合、複数のビット誤りを訂正するためのブロック符号が用いられる。従って、複数の誤り訂正ができるためにパリティビットも複数個用意される。それに対応する数のシンドロームを計算し、シンドロームレジスタ４０に格納する。計算されたシンドロームから誤り位置多項式の係数を求め（４８）、誤りを求める。訂正可能であれば、求めた誤りからパケット内の誤りを訂正して、パケット出力する。訂正不可能であれば、訂正しないままパケットを出力し、訂正不能のフラグおよび、サブフレーム内でのパケットの位置情報を出力する。すなわち、パケット誤りフラグとパケット誤り位置の２つの情報をまとめてパケット誤り情報として、受信情報であるパケットとは別に出力する。また、図２１には、バッファレジスタ４４があるが、内符号の復号器の場合、パケットサイズだけのバッファがあればよい。内符号の復号器において、復号アルゴリズムは使用したブロック符号の一般的な方法でよい。POB符号との連接符号としての特徴は、パケット誤りのフラグ生成およびサブフレーム内での位置を抽出して出力するところにある。

＜外符号（POB符号）の復号器＞
上述したように、内符号の復号器からは誤り訂正されたパケットとパケット誤り情報とが入力される。POB符号方式で用いているブロック符号がかかる範囲内にいくつのパケット誤りがあるか、また、誤りの位置の情報が入力されるため、図１０と同じ構成で実現することができる。

本発明について、図１−図２１を例にとり説明をした。しかし、本発明はこれらの実施例に限られるものではない。本発明の趣旨を逸脱しない範囲でいかなる変形も可能であることは当業者には明らかであろう。

本発明のPOB符号の符号構成を示す図である。 本発明のPOB符号の一実施例の符号構成を示す図である。 本発明のPOB符号方式を用いた場合のパケットを回復効果を示す図である。 本発明のPOB符号方式についての説明図である。 図４の構成にパリティを生成した後の構成を示す図である。 図５で示された符号語を復号する場合の説明図である。 本発明の符号化のフローを示す図である。 図７のフローに対応する符号器１００の構成例を示す図である。 本発明の復号化のフローを示す図である。 図９のフローに対応する復号器２００の構成例を示す図である。 最後の乗算部分を共通化することで、回路規模は小さくできることを示す図である。 本発明のRS符号をかける際の構成を示す図である。 図１２の符号化方法のフローチャートを示す図である。 図１３のフローに対応する符号器の構成を示す図である。 RS符号の場合の復号化のフローを示す図である。 図１５のフローに対応する復号器の構成を示す図である。 POB符号方式を外符号とした連接符号のフレーム構成図を示す図である。 図１７の場合の符号方のフローを示す図である。 図１８のフローに対応する符号器の構成を示す図である。 図１７の場合の復号器の構成を示す図である。 図２０の内符号の復号器の構成を示す図である。

符号の説明

１０、３０ フレーム検知手段
１２、３２ サブフレーム検知手段
１４、３４ パケット検知手段
１６、３８、８４ 線形帰還レジスタ
１８、２０、４６、８６ セレクタ
３６ パケット誤り位置と数の検出手段
４０、４４ レジスタ
４８ 誤りを求める式の係数計算手段
５０ 訂正可否判断手段
５２ 誤り生成（計算）手段
５８ 誤りレジスタ
７２ 乗算器
８０ 外符号器
８２ 内符号器
１００、３００、５００ 符号器
２００、４００、６００ 復号器

Claims (10)

1. 複数のパケットを含むフレームを準備するステップと、
   フレームを分割して複数のサブフレームを形成するステップと、
   隣接する少なくとも２つ以上のサブフレームに対応するブロック符号を形成するステップであって、一つのサブフレームについて少なくとも２つ以上の異なるブロック符号が重複して形成されるステップと、
   を含むパケット情報を符号化する方法。
2. 複数のパケットを含む連続する複数のフレームを取得するステップと、
   少なくとも２つ以上のフレーム中の隣接する少なくとも２つ以上の領域に対応するブロック符号を形成するステップであって、フレーム中の一つの領域について少なくとも２つ以上の異なるブロック符号が重複して形成されるステップと、
   を含むパケット情報を符号化する方法。
3. 複数のパケットを含むフレームを検出するステップと、
   検出したフレーム中のサブフレームを検出するステップと、
   サブフレーム中のパケットを検出するステップと、
   サブフレームに対応する少なくとも２つ以上の異なるブロック符号を重複して形成するステップと、
   を含むパケット情報を符号化する方法。
4. 前記ブロック符号を形成するステップは、１つのブロック符号に対応するサブフレームの一つにパリティを付加することを含む、請求項１または３の方法。
5. 前記ブロック符号を形成するステップは、１つのブロック符号に対応するフレーム中の領域の一つにパリティを付加することを含む、請求項２の方法。
6. 前記ブロック符号はリード・ソロモン（RS）符号であり、前記異なるブロック符号（n、k)は、次の式を満たすように符号化される、請求項１または３のいずれかの方法。
   
   

   

   ここで、
   
   

   

   
   H :生成行列、w:符号語、
   α：ガロア体の原始元、s：ブロック符号の数（サブフレーム分割数に等しい）、
   n:ブロックサイズ、k:情報サイズ、ただし、k=(n-r)/s、r：パリティサイズ、
   j：サブフレームの番号、
   i：符号化の条件の識別のための添え字、jr/s=<i<(j+１)r/sを満たす、
   h*：h番目のサブフレームのフレーム内での相対的な位置（h*=0,1,2,…,s-1）
7. 複数のパケットを含むフレームを検出するステップと、
   検出したフレーム中のサブフレームを検出するステップと、
   サブフレーム中のパケットを検出するステップと、
   サブフレームに対応する少なくとも２つ以上の異なるブロック符号を用いてパリティを生成する外符号化ステップと、
   ブロック符号における１パケットに対応するパリティを生成する内符号化ステップと、
   を含むパケット情報を符号化する方法。
8. 複数のパケットを含むフレームを検出する手段と、
   フレーム中のサブフレームを検出する手段と、
   サブフレーム中のパケットを検出する手段と、
   サブフレームに対応するパリティを生成する手段であって、一つのサブフレームについて異なる少なくとも２つ以上のブロック符号の各々に対応するパリティを生成する手段と、
   を備える符号器。
9. 前記パリティ生成手段は、前記ブロック符号の各々に対応する線形帰還レジスタを含む、請求項８の符号器。
10. さらに、前記パリティ生成により得られる符号化結果を出力する手段を含み、当該出力手段は、前記サブフレームの各々に対応するパリティを切り替えて出力するためのセレクタを有する、請求項９の符号器。

Images