WO2015178018A1

WO2015178018A1 - 端末、パケット復号方法、および、プログラムが記憶された記憶媒体

Info

Publication number: WO2015178018A1
Application number: PCT/JP2015/002518
Authority: WO
Inventors: 佑樹林; 鈴木　順; 真樹菅
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2014-05-22
Filing date: 2015-05-19
Publication date: 2015-11-26
Anticipated expiration: 2016-11-22
Also published as: US10404288B2; JPWO2015178018A1; JP6504162B2; US20170155408A1

Abstract

［課題］レートレス符号化に基づく符号化パケットからソースパケットを復号化する処理を高速化すること。［解決手段］端末は、ｎ行ｎ列の行列とｎビットのフラグを保持する記憶手段と、受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出し、抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行い、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定し、判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入する計算手段と、を備えている。

Description

端末、パケット復号方法、および、プログラムが記憶された記憶媒体

　本発明は、端末、パケット復号方法およびプログラムが記憶された記憶媒体に関し、特に、送信側の端末から逐次的に符号化パケットを受信して復号する端末、当該端末によるパケット復号方法、および、当該端末において動作するプログラムが記憶された記憶媒体に関する。

　伝送路においてパケットの喪失（ロス）が生じた場合、元のパケットを復元する方法としてＦＥＣ（Forward Error Correction）方式と呼ばれる方式が知られている。ＦＥＣ方式では、ロスの発生する伝送路において、送信端末がソースパケットに符号化パケットを付加してネットワークに送信する。受信端末において未受信のパケットが存在する場合、受信端末は符号化パケットに基づいてロスされたパケットを復元する。

　ＦＥＣ方式には、ソースパケットから冗長パケットを無限に作成し、受信端末において冗長パケットからソースパケットをデコードする「レートレス符号」（「噴水符号」ともいう。）と呼ばれる方式がある。

　レートレス符号方式において、復号の際に未知のソースパケットが存在する場合、符号化パケットから生成される行列をガウスの消去法に基づいて計算し、符号化パケットからソースパケットをデコードする方式が知られている（非特許文献１、特許文献１）。

　図８は、関連技術の端末を備えた通信システム（符号化パケット送受信システム）の構成を例示するブロック図である。図８を参照すると、送信端末１０と受信端末２０は、ネットワーク３０を介して接続されている。送信端末１０は、ソースパケット送信部１２、パケット符号化部１４、および、パケット送信部１６を備えている。一方、受信端末２０は、パケット受信部２２、パケット復号化部２４、および、ソースパケット受信部２６を備えている。

　図９は、図８の受信端末２０におけるパケット復号化部２４の構成を例示するブロック図である。図９を参照すると、パケット復号化部２４は、パケット復号計算部２８および復号判定部３６を備えている。また、パケット復号計算部２８は、ガウス消去部３２を備え、復号行列３４が記憶されている。

　かかる構成を有する関連技術の通信システムは、次のように動作する。図１０には、送信端末１０のパケット符号化部１４がパケットを符号化する様子と、受信端末２０のパケット復号化部２４がパケットを復号する様子が例示されている。

　まず、送信端末１０の動作を説明する。ソースパケット送信部１２は、生成されたＮ個のソースパケット３８をパケット符号化部１４へ送信する。パケット符号化部１４は、受信したＮ個のソースパケット３８の中からランダムにパケットを選択し、選択したパケットを排他的論理和（ＸＯＲ:exclusive OR）演算したものを符号化パケット４２として生成する。パケット符号化部１４は、符号化パケット４２を生成するときに使用したソースパケットを示す配列（図１０に示すランダム行列Ｇ）を符号化パケット４２に付加する。さらに、パケット符号化部１４は、生成した符号化パケット４２をパケット送信部１６へ送信する。パケット送信部１６は、受け取った符号化パケット４２をネットワーク３０へ送信する。よって、パケット送信部１６によって、図１０において、ランダム行列Ｇの各行および符号化パケット４２の各行ごとにそれぞれ構成されるパケットが送信される。具体的には、図１０に示す例では、ランダム行列Ｇは、６行５列である。そして、５個（Ｎ＝５）のソースパケット３８に基づいて、例えば、ランダム行列Ｇの１行目が符号化パケット４２の１行目に付加された［０，１，１，１，１，ｐ２＾ｐ３＾ｐ４＾ｐ５（ｐ２とｐ３とｐ４とｐ５とのＸＯＲ演算結果であり、例えば、１）］によって示される６ビットのパケットが送信される。同様に、例えば、ランダム行列Ｇの２～６行目および符号化パケット４２の２～６行目によって構成されるパケットが送信される。したがって、ソースパケット３８は、６ビットの６個のパケットによって送信される。

　次に、受信端末２０の動作を説明する。パケット受信部２２は、ネットワーク３０を介して受け取った符号化パケット４４をパケット復号化部２４へ送信する。パケット復号化部２４は、パケット受信毎に復号動作を行い、符号化パケット４４をＮ個のソースパケット４６へ復号することを試みる。図１０に示すように、パケット復号化部２４は、例えば、ソースパケットを示す配列を組み立てて、ガウスの消去法を用いる一般的な復号方法を用いる。パケット復号化部２４は、受信した符号化パケット４４をＮ個のソースパケット４６へ復号できた場合、Ｎ個のソースパケット４６をソースパケット受信部２６へ送信する。図１０に示す例では、パケット送信部１６によって送信された６個のパケットのうち４番目のパケットのロスが生じ、ソースパケット３８の数以上の数である５個のパケットがパケット受信部２２によって受信されている。そうすると、受信された５個のパケットによって、５個のソースパケット３８の数以上の数である５個の連立一次方程式を生成することができる。そして、ガウスの消去法によって、５個の連立一次方程式に基づいて、５個のソースパケット３８を導き出すことが可能である。

　ここで、一般的な復号方法であるガウスの消去法について説明する。図１１は、関連技術の受信端末２０における復号化（ガウスの消去法）のアルゴリズムを示すフロー図である。なお、説明の簡単化のため、各フェーズの動作例としてソースパケットの個数Ｎが５の場合の行列の計算過程（ｉ＝１）を図１２に示す。

　図１１および図１２を参照して、一般的なガウスの消去法のアルゴリズムと、アルゴリズムの説明の一例としてソースパケットの個数Ｎが５の場合の行列の計算過程（ｉ＝１）とについて説明する。

　まず、ステップＡ２において、行ベクトルのｉ番目の要素が１となるｉ行目以降の行ベクトルを選択する。このとき、選択する行ベクトルが見つからない場合（ステップＡ３のＮｏ）、ガウスの消去法の計算を終了する。図１２の動作例の場合、復号行列３４－１において、１番目の要素が１となる１行目以降の行ベクトルは５番目の行ベクトルとなるため、５番目の行ベクトルが選択される。

　次に、ステップＡ４において、選択した行ベクトルを１行目の行ベクトルと入れ替える。入れ替えた後のｉ行目の行ベクトルのｉ番目の要素を「ピボット」と呼び、行ベクトル自体を「ピボット行」と呼ぶ。図１２の動作例（ｉ＝１）の場合、ガウス消去部３２は、復号行列３４－１において、５行目の行ベクトルと１行目の行ベクトルとを入れ替える。復号行列３４－２は、行ベクトルを入れ替えた後の状態である。

　次に、ステップＡ５において、ガウス消去部３２は、ピボット行以外の行ベクトルのｉ番目の要素が１である行ベクトルとピボット行をＸＯＲ演算する。図１２の動作例（ｉ＝１）の場合、復号行列３４－２において、ピボット行以外に１番目の要素が１である行ベクトルがないため、ガウス消去部３２はＸＯＲ演算を行わない。

　ガウス消去部３２は、上記の動作をステップＡ１、Ａ７に示す通り、ｉ＝２～５について繰り返し行う。図１２に示すように、５行目まで計算が行われると、ガウスの消去法を適用した復号行列３４－Ｘは単位行列となり、符号化パケットが復号される。

　さらに、上記のｉ＝５についての動作が完了した際、送信端末１０が次のソースパケット群を符号化して送信することもある。この場合、ｉ＝１～５のステップがさらに数回繰り返されることになる。

　上述した関連技術の通信システムの場合、パケット受信毎にガウスの消去法によって復号を行う。しかし、この復号方法を使用した場合、パケット受信毎の計算量にばらつきが発生したり、Ｎ番目の符号化パケットを受信した際の計算量が多くなってしまい、次のソースパケット群に対する符号化パケットが到着するまでに計算が完了しなかったりするおそれがある。

　例えば、図１２の復号行列３４－１の場合、５番目の行ベクトルに対応する符号化パケットが到着するまで、ガウス消去部３２は、ステップＡ３においてガウスの消去法を適用することができず、計算を進めることができない。すなわち、５番目の行ベクトルに対応するパケットが到着して初めてガウス消去部３２による計算が開始されるため、ガウス消去部３２は、５番目の行ベクトルに対応するパケットが到着してから、ステップＡ４の処理とステップＡ５の処理とを５回ずつ実行することになる。

　したがって、次のソースパケット群に対する符号化パケットが到着した場合、前のソースパケット群に対する符号化パケットの計算が完了するまで、次のソースパケット群に対する符号化パケットは待ち合わせを行う必要がある。

　このように符号化パケットを送受信する通信システムにおいて、ガウスの消去法の計算を高速化する方式として、例えば、特許文献１のような方式が存在する。

特開２０１２－１４２７０９号公報

MacKay, D.J.C. "Fountain codes," Published in Communications, IEE Proceedings (Volume:152 , Issue: 6)

　上記特許文献１および非特許文献１の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本願の発明者によってなされたものである。

　レートレス符号化に基づく符号化パケットを復号化する上述の関連技術によると、受信端末においてパケット受信毎に符号化パケットの復号を行う際、最後のパケットを受け取ってから復号されるまでに長い時間を要するという問題がある。その理由は、ガウスの消去法を用いた復号方法では、ソースパケットの昇順にピボット行を検索し、昇順でピボット行が見つからない場合は計算を止めてしまうからである。

　また、関連技術における符号化パケットの受信端末には、複数のソースパケット群を複数の符号化パケット群に分けて動作する場合、前のソースパケット群に対する符号化パケットの復号が完了する前に、次のソースパケット群に対する符号化パケットが到着した場合に備えて、バッファを多く設ける必要がある。その理由は、最後のパケットを受けとってから復号が完了するまでに長い時間を要するからである。

　なお、特許文献１に記載された方式は、ソースパケットとして復号できたパケットを復号行列から省くことで、以降の計算量を削減する方式である。したがって、特許文献１に記載された方式では、ガウスの消去法の計算が始まらない場合には計算量を減らすことができない。

　そこで、レートレス符号化に基づく符号化パケットからソースパケットを復号化する処理を高速化することが課題となる。本発明の目的は、かかる課題解決に寄与する端末、パケット復号方法およびプログラムが記憶された記憶媒体を提供することにある。

　本発明の第１の態様に係る端末は、ｎ行ｎ列の行列とｎビットのフラグを保持する記憶手段と、受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出し、抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行い、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定し、判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入する計算手段と、を備えている。

　本発明の第２の態様に係るパケット復号方法は、コンピュータが、ｎ行ｎ列の行列とｎビットのフラグを記憶手段に保持するステップと、受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出するステップと、抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行うステップと、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定するステップと、判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入するステップと、を含む。

　本発明の第３の態様に係るプログラムが記憶された記憶媒体には、ｎ行ｎ列の行列とｎビットのフラグを記憶手段に保持する処理と、受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出する処理と、抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行う処理と、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定する処理と、判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入する処理と、をコンピュータに実行させるためのプログラムが記憶されている。なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することもできる。

　本発明に係る端末、パケット復号方法およびプログラムが記憶された記憶媒体によると、レートレス符号化に基づく符号化パケットからソースパケットを復号化する処理を高速化することが可能となる。

一実施形態に係る端末の構成を例示するブロック図である。第１の実施形態に係る端末を備えた通信システムの構成を例示するブロック図である。第１の実施形態に係る端末におけるパケット復号化部の構成を例示するブロック図である。第１の実施形態に係る端末におけるパケット復号計算部の動作を例示するフロー図である。第１の実施形態に係る端末におけるパケット復号計算部による復号行列およびピボットフラグの計算過程（ｉ＝１）を例示する図である。第１の実施形態に係る端末におけるパケット復号計算部による復号行列およびピボットフラグの計算過程（ｉ＝２）を例示する図である。第１の実施形態に係る端末におけるパケット復号計算部による復号行列およびピボットフラグの計算過程（ｉ＝５）を例示する図である。関連技術の端末を備えた通信システムの構成を例示するブロック図である。関連技術の端末におけるパケット復号化部の構成を例示するブロック図である。関連技術の端末を備えた通信システムにおけるパケット符号化の動作を例示する図である。関連技術の端末における復号化（ガウスの消去法）のアルゴリズムを示すフロー図である。関連技術の端末におけるパケット復号化部による復号行列の計算過程（Ｎ＝５の場合）を例示する図である。

　はじめに、本発明の一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。

　図１は、本発明の一実施形態の端末２１の構成を例示するブロック図である。図１を参照すると、端末２１は、記憶手段５６と計算手段６４とを備えている。記憶手段５６は、ｎ行ｎ列の行列（例えば、ｎ＝５の場合、図５ないし図７に示す復号行列５８）とｎビットのフラグ（例えば、ｎ＝５の場合、図５ないし図７に示すピボットフラグ６２）とを保持する。計算手段６４は、受信したｎビットの符号化パケットとフラグ（６２）との双方において１となる要素を抽出し、抽出した要素の要素番号に相当する行列（５８）の行ベクトルを受信した符号化パケットに対して排他的論理和（ＸＯＲ）演算する処理を、抽出したすべての要素について行う。そして、計算手段６４は、上記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定すると共に、判定した要素の要素番号に相当する行ベクトルとして、上記排他的論理和演算後の符号化パケットを行列（５８）に挿入する。

　計算手段６４は、フラグ（６２）の要素のうちの、上記判定した要素の要素番号に相当する要素を１とする（なお、当該要素のフラグがセットされていることを示すものであれば、要素を１とすることに限定されない）。なお、フラグ（６２）のすべての要素が１となった場合、復号が完了する。

　計算手段６４は、上記排他的論理和演算後の符号化パケットにおいて最初に１となる要素に相当するフラグ（６２）の要素が１である場合、上記排他的論理和演算後の符号化パケットを行列（５８）に挿入することなく破棄する。

　計算手段６４は、上記排他的論理和演算後の符号化パケットにおいて最初に１となる要素の要素番号と同一の要素番号の要素が１である行列（５８）の行ベクトルに対して、上記排他的論理和演算後の符号化パケットを排他的論理和演算したものを行列（５８）の当該行ベクトルとして格納する処理を、行列（５８）の各行ベクトルに対して行う。

　以上に述べたような端末２１によると、レートレス符号化に基づく符号化パケットからソースパケットを復号化する処理を、関連技術と比較して、高速化することが可能となる。なぜなら、関連技術のガウスの消去法のように、復号の手順においてソースパケットの昇順にピボット行を検索するのではなく、パケット受信毎にそのパケットが何番目のピボット行になるかを決定し、途中のピボット行となった場合にも計算を進めることができるからである。

＜実施形態１＞
　次に、第１の実施形態の端末を備えた通信システムについて、図面を参照して詳細に説明する。

　図２は、本実施形態の端末を受信端末２１として備えた通信システムの構成を例示するブロック図である。図２を参照すると、通信システムは、ソースパケットを符号化し、ネットワークへ送信する送信端末１０と、受信した符号化パケットをソースパケットに復号する受信端末２１とを備えている。

　送信端末１０は、ソースパケット送信部１２、パケット符号化部１４、およびパケット送信部１６を備えている。ソースパケット送信部１２は、受信端末２１に送信したいデータを伝送するネットワークのプロトコルに合わせてパケット化する。パケット符号化部１４は、ソースパケットを符号化し符号化パケットとする。パケット送信部１６は、符号化されたパケットをネットワーク３０に送信する。

　一方、受信端末２１は、パケット受信部２２、パケット復号化部５２、およびソースパケット受信部２６を備えている。パケット受信部２２は、ネットワーク３０から到来した符号化パケットを受信する。パケット復号化部５２は、符号化パケットをソースパケットに復号する。ソースパケット受信部２６は、復号されたソースパケットを受信して受信端末２１にデータとして渡す。

　パケット符号化部１４は、ソースパケット送信部１２から受信したＮ個（Ｎは任意の自然数）のソースパケットの符号化を行う。ここでは、符号化方法として、レートレス符号の一方式であるRandom Linear Fountainの動作について説明する。

　Random Linear Fountainでは、パケット符号化部１４が、到着したＮ個のソースパケットの中からランダムにパケットを選択する。また、パケット符号化部１４は、自身が選択したパケットの排他的論理和（ＸＯＲ：exclusive OR）を計算したものを符号化パケットとする。さらに、パケット符号化部１４は、自身が選択したソースパケットがＮ個のソースパケットのうちのどのソースパケットであるのかを判別できるように、符号化パケットに対してフラグを付加する。

　例えば、Ｎ＝５の場合、２，３，４，５番目のソースパケットが選択されたとき、パケット符号化部１４は、符号化パケットに対して［０，１，１，１，１］という５ビット（bit）のフラグを付すことにより、符号化パケットに含まれるソースパケットを識別可能とする。受信端末２１においてＮ個のソースパケットが復号されるまで、パケット符号化部１４は、かかる動作を無限に繰り返す。

　ここでは、受信端末２１においてＮ個のソースパケットが復号されたかどうかを送信端末１０が確認する機構について、特に限定しない。例えば、送信端末１０は、受信端末２１から復号が完了したことを知らせるフィードバック情報などから復号の完了通知を受け、符号化パケットの送信を停止する方法を用いることができる。

　図３は、本実施形態の受信端末２１におけるパケット復号化部５２の構成を例示するブロック図である。図３を参照すると、パケット復号化部５２は、パケット復号計算部５４と復号判定部７２とを備えている。パケット復号計算部５４は、パケット受信部２２から受信した符号化パケットを復号アルゴリズムによりソースパケットへ復号するための計算を行う。復号判定部７２は、パケット復号計算部５４により計算された結果を参照して、ソースパケットに復号されたか、または、符号化パケットが残っているかを判定する。

　パケット復号計算部５４は、記憶手段５６と計算手段６４とを備えている。記憶手段５６は、復号行列５８とピボットフラグ６２とを保持する。一方、計算手段６４は、復号計算部６６とピボット位置判定部６８とを備えている。

　パケット受信部２２から受信した符号化パケットは、行列の形状の復号行列５８として保存される。ピボットフラグ６２によって、復号行列５８内のピボット行にすでにパケットが入っているかどうかがフラグで示される。復号計算部６６は、パケット受信部２２から受信した符号化パケットに対する計算と、復号行列５８に基づいてソースパケットへの復号計算とを行う。ピボット位置判定部６８は、パケット受信部２２から受信した符号化パケットに対する計算結果に基づいて、計算後の符号化パケットのピボット位置を判定する。

　復号計算部６６は、復号行列５８の行ベクトルをパケット受信部２２から受信した符号化パケットに対して演算する動作と、演算後の符号化パケットをピボット位置判定部６８により復号行列５８に挿入した後に、演算後の符号化パケットを復号行列５８の行ベクトルに対して演算する動作とを行う。

　まず、復号計算部６６による動作のうちの、パケット受信部２２から受信した符号化パケットに対して復号行列５８の行ベクトルを演算する動作について説明する。復号計算部６６は、パケット受信部２２から受信した符号化パケットとピボットフラグ６２とを比較し、符号化パケットとピボットフラグ６２との双方が“１”となっている要素に対応する復号行列５８の行ベクトルを符号化パケットにＸＯＲ（exclusive OR）演算する。ここで、符号化パケットとピボットフラグ６２のｉ番目の要素に対応する行ベクトルとは、復号行列５８におけるｉ行目の行ベクトルをいう。

　例えば、受信した符号化パケットにおいて付されている前述した５ビットのフラグ（単に符号化パケットともいう）が［０，１，１，１，１］で、ピボットフラグ６２が［０，１，０，１，０］である場合、復号計算部６６は、復号行列５８の２番目と４番目との行ベクトルを受信した符号化パケットに対してＸＯＲ演算する。

　次に、復号計算部６６による動作のうちの、ピボット位置判定部６８が、ＸＯＲ演算後の符号化パケットを復号行列５８に挿入した後、ＸＯＲ演算後の符号化パケットを復号行列５８の行ベクトルに演算する動作について説明する。復号計算部６６は、挿入されたピボット行ベクトル（すなわち、上記ＸＯＲ演算後の符号化パケット）のピボットに対応する列を確認し、“１”となっている要素を持つすべての行ベクトルに対してピボット行ベクトルをＸＯＲ演算する。

　ピボット位置判定部６８は、パケット受信部２２から受信した符号化パケットに対して復号行列５８の行ベクトルを演算する復号計算部６６の動作が完了した後の符号化パケット（すなわち、上記ＸＯＲ演算後の符号化パケット）に対して、ピボットの位置の判定を行う。ピボットの位置は、判定対象の符号化パケットの要素中で初めて“１”が立っている要素（すなわち、当該符号化パケットを構成するビット列において、値が「１」であるビットのうちの最上位ビット）を指す。また、ピボット位置判定部６８は、ピボットがＸ番目の要素であった場合、まずピボットフラグのＸ番目の要素と比較し、すでにピボットフラグが立っている場合、その符号化パケットは不要であるとみなして破棄する。一方、ピボットフラグが立っていない場合、ピボット位置判定部６８はピボットフラグのＸ番目の要素を“１”とし、復号行列５８のＸ番目の行に計算後の符号化パケットを挿入する。

　復号判定部７２は、パケット復号計算部５４による計算終了後に、復号行列５８およびピボットフラグ６２を参照して、符号化パケットが復号され、Ｎ個のソースパケットが生成されたかどうかを判定する。具体的には、復号判定部７２は、ピボットフラグ６２を参照して、Ｎ個の要素のすべてが“１”となっている場合、復号が完了したものと判定する。

　次に、図２および図３に示したブロック図と、図４に示したフロー図と、図５ないし図７に示したＮ＝５の場合のパケット復号の計算過程を参照して、本実施形態の受信端末２１の動作について詳細に説明する。

　まず、パケット復号化部５２がパケット受信部２２から符号化パケットを受信すると、ステップＢ１に移行する。

　ステップＢ２では、復号計算部６６は、ピボットフラグ６２と受信した符号化パケットとを確認し、ピボットフラグ６２と受信した符号化パケットとの双方が“１”になっている要素に対応する復号行列５８の行ベクトルを符号化パケットに対してＸＯＲ演算する。ステップＢ１に示すように、復号計算部６６は、ピボットフラグの“１”の要素数に応じた回数だけ、ステップＢ２の比較と計算とを繰り返す。繰り返しが完了すると、ステップＢ３の処理から、ステップＢ４へ移行する。

　図６のｉ＝２の場合のパケット符号化の計算過程の例で説明する。受信した符号化パケットは［０，１，０，０，１］であり、ピボットフラグ６２－３は［０，１，０，０，０］である。そこで、復号計算部６６は、復号行列５８－３の２番目の行ベクトルを、受信した符号化パケットに対してＸＯＲ演算する。その結果、ＸＯＲ演算後の符号化パケットは［０，０，１，１，０］となる。

　ステップＢ４では、ピボット位置判定部６８は、ＸＯＲ演算後の符号化パケットに対してピボット位置の判定を行う。ピボット位置とは、ＸＯＲ演算後の符号化パケットの要素のうちの最初に“１”となる要素（すなわち、当該符号化パケットを構成するビット列において、値が「１」であるビットのうちの最上位ビット）である。Ｘ番目の要素が最初の“１”である場合（すなわち、当該符号化パケットを構成するビット列において、Ｘ番目のビットが、値が「１」であるビットのうちの最上位ビットである場合）、ピボット行はＸ番目となる。ただし、ピボットフラグ６２のＸ番目の要素にすでに“１”が立っている場合、ピボット位置判定部６８は、この符号化パケットを不要であるとみなして破棄し（ステップＢ５）、処理を終了する。符号化パケットが破棄されなかった場合、ステップＢ６に移行する。

　図６の場合の例で説明すると、ＸＯＲ演算後の符号化パケットは［０，０，１，１，０］であるため、初めて“１”が現れる要素は３番目となり（すなわち、当該符号化パケットを構成するビット列において、値が「１」であるビットのうちの最上位ビットは３ビット目）、ピボット位置判定部６８は、符号化パケットは３番目のピボット行となる行ベクトルであると判定する。

　ステップＢ６では、ピボット位置判定部６８は、ステップＢ４で判定されたピボット行を復号行列５８のＸ番目の行ベクトルに挿入する動作を行う。図６の場合の例で説明すると、計算後の符号化パケットは３番目のピボット行となる行ベクトルであるため、復号行列５８－４の３番目の行に挿入されている。符号化パケットが挿入されると、ステップＢ７へ移行する。

　ステップＢ７では、符号化パケットが挿入された後、復号計算部６６は、符号化パケットのピボットとなる要素と同じ列に“１”が立っている他の行ベクトルに対して、符号化パケットをＸＯＲ演算する。

　図６の場合の例で説明すると、復号行列５８－４のピボット行以外の行ベクトルとして、２行目の行ベクトルの３番目の列に“１”が立っているため、２行目の行ベクトルに対して３行目の行ベクトル（すなわち、ＸＯＲ演算後の符号化パケット）をＸＯＲ演算する。この結果、復号行列５８－５に示すように、２行目の行ベクトルは［０，１，０，０，１］となる。

　ステップＢ７が終了すると、パケット復号計算部５４の動作は完了し、復号判定部７２により、復号の判定を行う。復号判定部７２は、ピボットフラグ６２のすべての要素が“１”となったとき、復号が完了したものとみなす。

　上記の動作を復号行列５８がＮ行すべて埋まるまで繰り返し行う。図７の場合の例で説明すると、ｉ＝５番目に対応する符号化パケットが到着し、計算を行うと、復号行列５８がすべて埋まり、ソースパケットへの復号が完了する。このとき、ピボットフラグ６２－Ｙの各要素もすべて“１”となっており、復号判定部７２は、復号が完了したものと判定する。復号判定部７２により復号が完了されたと判定された後、パケット復号化部５２は、ソースパケットをソースパケット受信部２６に送信し、復号行列５８を初期化する。

　次に、本実施形態の効果について説明する。本実施形態の端末２１によると、レートレス符号化に基づく符号化パケットからソースパケットを復号化する処理を関連技術と比較して高速化することが可能となる。その理由は、関連技術で用いられるガウスの消去法のように、復号の手順として、ソースパケットの昇順にピボット行を検索する代わりに、パケット受信毎にそのパケットが何番目のピボット行になるかを決定し、途中のピボット行となった場合にも計算を進めるからである。

　また、本実施形態によると、前のソースパケット群に対する符号化パケットの復号が完了する前に、次のソースパケット群に対する符号化パケットが到着した場合のバッファが少なくなる。その理由は、前のソースパケット群に対する最後の符号化パケットを受けとってから復号が完了するまでの時間が短いからである。

　上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
［付記１］
　ｎ行ｎ列の行列とｎビットのフラグを保持する記憶手段と、
　受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出し、抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行い、前記排他的論理和演算後の符号化パケットを構成するビット列において、値が「１」であるビットのうちの最上位ビットである、最初に１となる要素を判定し、判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入する計算手段と、を備える、
　ことを特徴とする端末。
［付記２］
　前記計算手段は、前記フラグの要素のうちの、前記判定した要素の要素番号に相当する要素を１とする、
　付記１に記載の端末。
［付記３］
　前記計算手段は、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素に相当する前記フラグの要素が１である場合、前記排他的論理和演算後の符号化パケットを前記行列に挿入することなく破棄する、
　付記１または２に記載の端末。
［付記４］
　前記計算手段は、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素の要素番号と同一の要素番号の要素が１である前記行列の行ベクトルに対して、前記排他的論理和演算後の符号化パケットを排他的論理和演算したものを前記行列の当該行ベクトルとして格納する処理を、前記行列の各行ベクトルに対して行う、
　付記１ないし３のいずれか一に記載の端末。
［付記５］
　前記フラグのすべての要素が１となった場合、復号が完了したものと判定する判定手段をさらに備える、
　付記１ないし４のいずれか一に記載の端末。
［付記６］
　コンピュータが、ｎ行ｎ列の行列とｎビットのフラグを記憶手段に保持するステップと、
　受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出するステップと、
　抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行うステップと、
　前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定するステップと、
　判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入するステップと、を含む、
　ことを特徴とするパケット復号方法。
［付記７］
　前記コンピュータが、前記フラグの要素のうちの、前記判定した要素の要素番号に相当する要素を１とするステップを含む、
　付記６に記載のパケット復号方法。
［付記８］
　前記コンピュータが、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素に相当する前記フラグの要素が１である場合、前記排他的論理和演算後の符号化パケットを前記行列に挿入することなく破棄するステップを含む、
　付記６または７に記載のパケット復号方法。
［付記９］
　前記コンピュータが、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素の要素番号と同一の要素番号の要素が１である前記行列の行ベクトルに対して、前記排他的論理和演算後の符号化パケットを排他的論理和演算したものを前記行列の当該行ベクトルとして格納する処理を、前記行列の各行ベクトルに対して行うステップを含む、　付記６ないし８のいずれか一に記載のパケット復号方法。
［付記１０］
　前記コンピュータが、前記フラグのすべての要素が１となった場合、復号が完了したものと判定するステップを含む、
　付記６ないし９のいずれか一に記載のパケット復号方法。
［付記１１］
　ｎ行ｎ列の行列とｎビットのフラグを記憶手段に保持する処理と、
　受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出する処理と、
　抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行う処理と、
　前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定する処理と、
　判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入する処理と、をコンピュータに実行させる、
　ことを特徴とするプログラム。［付記１２］
　前記フラグの要素のうちの、前記判定した要素の要素番号に相当する要素を１とする処理を、前記コンピュータに実行させる、
　付記１１に記載のプログラム。
［付記１３］
　前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素に相当する前記フラグの要素が１である場合、前記排他的論理和演算後の符号化パケットを前記行列に挿入することなく破棄する処理を、前記コンピュータに実行させる、
　付記１１または１２に記載のプログラム。
［付記１４］
　前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素の要素番号と同一の要素番号の要素が１である前記行列の行ベクトルに対して、前記排他的論理和演算後の符号化パケットを排他的論理和演算したものを前記行列の当該行ベクトルとして格納する処理を、前記行列の各行ベクトルに対して行う処理を、前記コンピュータに実行させる、
　付記１１ないし１３のいずれか一に記載のプログラム。
［付記１５］
　前記フラグのすべての要素が１となった場合、復号が完了したものと判定する処理を、前記コンピュータに実行させる、
　付記１１ないし１４のいずれか一に記載のプログラム。　

　なお、上記特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。

　以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。

　この出願は、２０１４年５月２２日に出願された日本出願特願２０１４－１０５８２６を基礎とする優先権を主張し、その開示の全てをここに取り込む。

１０　　送信端末
１２　　ソースパケット送信部
１４　　パケット符号化部
１６　　パケット送信部
２０、２１　　受信端末
２２　　パケット受信部
２４、５２　　パケット復号化部
２６　　ソースパケット受信部
２８、５４　　パケット復号計算部
３０　　ネットワーク
３２　　ガウス消去部
３４、３４－１～３４－Ｘ　　ガウスの消去法による計算過程の復号行列
３６、７２　　復号判定部
３８　　符号化前のソースパケット
４２　　送信する符号化パケット
４４　　受信した符号化パケット
４６　　復号後のソースパケット
５６　　記憶手段
５８、５８－１～５８－Ｙ　　実施形態のアルゴリズムにおける復号行列
６２、６２－１～６２－Ｙ　　実施形態のアルゴリズムにおけるピボットフラグ
６４　　計算手段
６６　　復号計算部
６８　　ピボット位置判定部

Claims

　ｎ行ｎ列の行列とｎビットのフラグを保持する記憶手段と、
　受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出し、抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行い、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定し、判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入する計算手段と、を備える、
　ことを特徴とする端末。
　前記計算手段は、前記フラグの要素のうちの、前記判定した要素の要素番号に相当する要素を１とする、
　請求項１に記載の端末。
　前記計算手段は、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素に相当する前記フラグの要素が１である場合、前記排他的論理和演算後の符号化パケットを前記行列に挿入することなく破棄する、
　請求項１または２に記載の端末。
　前記計算手段は、前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素の要素番号と同一の要素番号の要素が１である前記行列の行ベクトルに対して、前記排他的論理和演算後の符号化パケットを排他的論理和演算したものを前記行列の当該行ベクトルとして格納する処理を、前記行列の各行ベクトルに対して行う、
　請求項１ないし３のいずれか１項に記載の端末。
　前記フラグのすべての要素が１となった場合、復号が完了したものと判定する判定手段をさらに備える、
　請求項１ないし４のいずれか１項に記載の端末。
　ｎ行ｎ列の行列とｎビットのフラグを記憶手段に保持し、
　受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出し、
　抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行い、
　前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定し、
　判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入する、
　ことを特徴とするパケット復号方法。
　前記フラグの要素のうちの、前記判定した要素の要素番号に相当する要素を１とする、
　請求項６に記載のパケット復号方法。
　前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素に相当する前記フラグの要素が１である場合、前記排他的論理和演算後の符号化パケットを前記行列に挿入することなく破棄する、
　請求項６または７に記載のパケット復号方法。
　前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素の要素番号と同一の要素番号の要素が１である前記行列の行ベクトルに対して、前記排他的論理和演算後の符号化パケットを排他的論理和演算したものを前記行列の当該行ベクトルとして格納する処理を、前記行列の各行ベクトルに対して行う、　請求項６ないし８のいずれか１項に記載のパケット復号方法。
　ｎ行ｎ列の行列とｎビットのフラグを記憶手段に保持する処理と、
　受信したｎビットの符号化パケットと前記フラグの双方において１となる要素を抽出する処理と、
　抽出した要素の要素番号に相当する前記行列の行ベクトルを受信した符号化パケットに対して排他的論理和演算する処理を、抽出したすべての要素について行う処理と、
　前記排他的論理和演算後の符号化パケットにおいて最初に１となる要素を判定する処理と、
　判定した要素の要素番号に相当する行ベクトルとして、前記排他的論理和演算後の符号化パケットを前記行列に挿入する処理と、をコンピュータに実行させる、
　ことを特徴とするプログラムが記憶された記憶媒体。