(57)【要約】  演算処理を高速化する。  メモリ（Ｍ０〜Ｍ１５）は、排他的論理和演算を行う単位となるデータブロックを保持し、選択回路（２ａ〜２ｐ）は、選択信号を受け、メモリ（Ｍ０〜Ｍ１５）から読み出される複数のデータブロックのうち、排他的論理和演算に使用する２以上のデータブロックを選択信号に基づき選択し、ＸＯＲ回路（３ａ〜３ｏ）（排他的論理和演算回路）は、選択回路（２ａ〜２ｐ）で選択された２以上のデータブロックに基づく排他的論理和演算を行う。
2015177917.tif 000002
【特許請求の範囲】
【請求項１】
排他的論理和演算を行う単位となるデータブロックを保持する複数のメモリと、
選択信号を受け、前記複数のメモリから読み出される複数の前記データブロックのうち、排他的論理和演算に使用する２以上のデータブロックを前記選択信号に基づき選択する複数の選択回路と、
前記複数の選択回路で選択された前記２以上のデータブロックに基づく排他的論理和演算を行う１または複数の排他的論理和演算回路と、
を有することを特徴とする演算回路。
【請求項２】
前記複数の選択回路のそれぞれは論理積演算回路であり、前記論理積演算回路の、第１の入力端子には、前記複数のメモリに保持されている複数の前記データブロックの何れかが入力され、第２の入力端子には、前記選択信号が入力され、前記論理積演算回路は、前記選択信号の値に基づいて、前記第１の入力端子に入力されるデータブロックを出力するか否かを選択する、ことを特徴とする請求項１に記載の演算回路。
【請求項３】
前記複数のメモリのそれぞれと、前記複数の選択回路のそれぞれとの間には、前記データブロックを保持し、保持した前記データブロックの出力タイミングを調整するレジスタが接続されていることを特徴とする請求項１または２に記載の演算回路。
【請求項４】
前記複数の排他的論理和演算回路は、複数段に渡って接続されており、前記複数の排他的論理和演算回路の一部の出力端子には、排他論理和演算の結果を格納するメモリが接続されていること、を特徴とする請求項１乃至３の何れか一項に記載の演算回路。
【請求項５】
排他的論理和演算を行う単位となるデータブロックを保持する複数のメモリと、
選択信号を受け、前記複数のメモリから読み出される複数の前記データブロックのうち、排他的論理和演算に使用する２以上のデータブロックを前記選択信号に基づき選択する複数の選択回路と、
前記複数の選択回路で選択された前記２以上のデータブロックに基づく排他的論理和演算を行い、符号化データを生成する１または複数の排他的論理和演算回路と、
を有することを特徴とする符号化回路。
【請求項６】
排他的論理和演算を行う単位となる符号化データであるデータブロックを保持する複数のメモリと、
選択信号を受け、前記複数のメモリから読み出される複数の前記データブロックのうち、排他的論理和演算に使用する２以上のデータブロックを前記選択信号に基づき選択する複数の選択回路と、
前記複数の選択回路で選択された前記２以上のデータブロックに基づく排他的論理和演算を行い、復号データを生成する１または複数の排他的論理和演算回路と、
を有することを特徴とする復号回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算回路、符号化回路及び復号回路に関する。
【背景技術】
【０００２】
ＸＯＲ（排他的論理和）演算は、例えば、送信データに付加するパリティビットを生成する際等に行われる。
近年、ＴＣＰ（Transmission Control Protocol）／ＩＰ（Internet Protocol）を用いた通信時に発生するパケット欠落による通信速度の低下を回避するため、ＲＰＳ（Random Packet Stream）技術が提案された。ＲＰＳ技術は、データ転送時に消失したパケットを自動生成する技術である。ＲＰＳ技術では、パケット復元に用いる符号化データ（冗長データ）を生成するため、送信装置にて、一定のデータ量のデータブロック間のＸＯＲ演算が多数回行われる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１１−２３７９９７号公報
【特許文献２】特開２００１−１４７８２７号公報
【特許文献３】特開平１１−１０２３０１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、ＲＰＳ技術による符号化処理のように、複数のデータブロックの組み合わせでＸＯＲ演算を多数回繰り返す処理は、ソフトウェアで行うと処理時間がかかり、通信速度の高速化が進む状況に対応できなくなることが考えられる。【０００５】
そこで、ＸＯＲ演算をハードウェアで行うことが考えられる。しかし、単にソフトウェアをハードウェア化するだけでは、演算の高速化にはつながらない可能性がある。例えば、あるデータブロック間のＸＯＲ演算結果を一旦メモリに格納し、その結果と別のデータブロック間でＸＯＲ演算する、といった処理を繰り返すと、メモリのデータ転送速度が遅い場合、処理時間が長くなってしまう。
【課題を解決するための手段】
【０００６】
発明の一観点によれば、排他的論理和演算を行う単位となるデータブロックを保持する複数のメモリと、選択信号を受け、前記複数のメモリから読み出される複数の前記データブロックのうち、排他的論理和演算に使用する２以上のデータブロックを前記選択信号に基づき選択する複数の選択回路と、前記複数の選択回路で選択された前記２以上のデータブロックに基づく排他的論理和演算を行う１または複数の排他的論理和演算回路と、を有する演算回路が提供される。【０００７】
また、発明の一観点によれば、排他的論理和演算を行う単位となるデータブロックを保持する複数のメモリと、選択信号を受け、前記複数のメモリから読み出される複数の前記データブロックのうち、排他的論理和演算に使用する２以上のデータブロックを前記選択信号に基づき選択する複数の選択回路と、前記複数の選択回路で選択された前記２以上のデータブロックに基づく排他的論理和演算を行い、符号化データを生成する１または複数の排他的論理和演算回路と、を有する符号化回路が提供される。【０００８】
また、発明の一観点によれば、排他的論理和演算を行う単位となる符号化データであるデータブロックを保持する複数のメモリと、選択信号を受け、前記複数のメモリから読み出される複数の前記データブロックのうち、排他的論理和演算に使用する２以上のデータブロックを前記選択信号に基づき選択する複数の選択回路と、前記複数の選択回路で選択された前記２以上のデータブロックに基づく排他的論理和演算を行い、復号データを生成する１または複数の排他的論理和演算回路と、を有する復号回路が提供される。
【発明の効果】
【０００９】
開示の演算回路、符号化回路及び復号回路によれば、演算処理を高速化できる。
本発明の上記及び他の目的、特徴及び利点は本発明の例として好ましい実施の形態を表す添付の図面と関連した以下の説明により明らかになるであろう。
【図面の簡単な説明】
【００１０】
【図１】第１の実施の形態による演算回路の一例を示す図である。
【図２】ＲＰＳ符号化処理の一例を説明する図である。
【図３】情報処理装置の一例を示す図である。
【図４】ＲＰＳ符号化処理を行うＦＰＧＡの一例について説明する図である。
【図５】第２の実施の形態による符号化回路の一例を示す図である。
【図６】制御回路の一例を示す図である。
【図７】ＲＰＳ符号化行列の一例を示す図である。
【図８】ＲＰＳ符号化処理の一例の流れを示すフローチャートである。
【図９】ＲＰＳ符号化処理で得られた符号化データに対する復号処理の一例を説明する図である。
【図１０】第２の実施の形態による復号回路の一例を示す図である。
【図１１】受信符号化行列の生成例を説明する図である。
【図１２】生成された受信符号化行列の一例を示す図である。
【図１３】復号ベクトルの生成処理の一例の流れを示すフローチャートである。
【図１４】更新された受信符号化行列の一例を示す図である。
【図１５】行列ｏｐｓの一例を示す図である。
【図１６】行列ｏｐｓの列ベクトル（復号ベクトル）と、その列ベクトルにより復号されるデータブロックとの関係の一例を示す図である。
【図１７】第２の実施の形態による符号化回路の変形例を示す図である（その１）。
【図１８】第２の実施の形態による符号化回路の変形例を示す図である（その２）。
【図１９】第２の実施の形態による符号化回路の変形例を示す図である（その３）。
【図２０】符号化処理の一例の流れを説明する図である。
【発明を実施するための形態】
【００１１】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
（第１の実施の形態）
図１は、第１の実施の形態による演算回路の一例を示す図である。
【００１２】
演算回路１は、例えば、符号化処理を行う符号化回路、または復号処理を行う復号回路等である。
演算回路１は、メモリＭ０〜Ｍ１５、選択回路２ａ〜２ｐ、ＸＯＲ回路３ａ〜３ｏ、選択信号が入力される入力端子Ｐ１、ＸＯＲ演算結果が出力される出力端子Ｐ２を有する。なお、回路素子間を接続する信号線は、例えば、６４ビット幅等の複数ビットを束ねていてもよい。
【００１３】
メモリＭ０〜Ｍ１５は、例えば、ＲＡＭ（Random Access Memory）であり、ＸＯＲ演算を行う単位となる複数のデータブロックを保持する。データブロックは、例えば、符号化対象データが一定のデータサイズで分割されたものである。図１の例では、１６個のデータブロックのそれぞれが、メモリＭ０１〜Ｍ１５の何れかに保持される。また、メモリＭ０〜Ｍ１５は、それぞれ、保持したデータブロックを、選択回路２ａ〜２ｐに出力する。
【００１４】
選択回路２ａ〜２ｐは、入力端子Ｐ１から入力される選択信号を受け、その選択信号に基づき、メモリＭ０〜Ｍ１５に保持されたデータブロックをＸＯＲ演算に使用するか否かを選択する。選択回路２ａ〜２ｐとしては、ＡＮＤ回路（論理積演算回路）を用いることができる。選択回路２ａ〜２ｐは、ＡＮＤ回路に限定されないが、ＡＮＤ回路を用いることで、簡単な回路にすることができる。
【００１５】
以下では、選択回路２ａ〜２ｐはＡＮＤ回路であるものとして説明する。
選択回路２ａ〜２ｐは、メモリＭ０〜Ｍ１５が出力したデータブロックと、１６ビットの選択信号とのＡＮＤ演算を行い、その演算結果をＸＯＲ回路３ａ〜３ｈに出力する。このとき、入力端子Ｐ１から入力される１６ビットの選択信号の“１”となるビットに応じて、メモリＭ０〜Ｍ１５に保持されている複数のデータブロックの１つまたは複数が、選択回路２ａ〜２ｐから出力される。
【００１６】
図１の上側には、演算回路１がＲＰＳ技術による符号化処理（以下ＲＰＳ符号化処理と呼ぶ）を行う場合を想定して、ＲＰＳ符号化行列の一例が示されている。ＲＰＳ符号化行列は、図示しない記憶部に記憶されており、選択信号として、１６ビットの列ベクトルが入力端子Ｐ１に順番に入力される。図１のＲＰＳ符号化行列は、１６行３０列の行列である。列ベクトルにおける行は、メモリＭ０〜Ｍ１５に対応している。つまり、列ベクトルにおけるある行の値が“１”のときには、その行に対応するメモリに保持されているデータブロックがＸＯＲ演算に用いられる。
【００１７】
例えば、列番号が１７の列ベクトルが入力端子Ｐ１から入力された場合、１，３，５〜１３，１５行目に対応した、メモリＭ０，Ｍ２，Ｍ４，…，Ｍ１２，Ｍ１４に保持されているデータブロックが、選択回路２ａ，２ｃ，２ｅ，…，２ｍ，２ｏから出力される。
【００１８】
また、列番号が２５の列ベクトルが入力端子Ｐ１から入力された場合、２，４，…，１２，１４，１６行目に対応した、メモリＭ１，Ｍ３，…，Ｍ１１，Ｍ１３，Ｍ１５に保持されているデータブロックが、選択回路２ｂ，２ｄ，…，２ｌ，２ｎ，２ｐから出力される。
【００１９】
ＸＯＲ回路３ａ〜３ｏは、選択回路２ａ〜２ｐで選択されたデータブロックに基づくＸＯＲ演算を行う。ＸＯＲ演算結果は、出力端子Ｐ２から出力される。
ＸＯＲ回路３ａの２つの入力端子は、選択回路２ａ，２ｂの出力端子に接続されており、ＸＯＲ回路３ｂの２つの入力端子は、選択回路２ｃ，２ｄの出力端子に接続されている。また、ＸＯＲ回路３ｃの２つの入力端子は、選択回路２ｅ，２ｆの出力端子に接続されており、ＸＯＲ回路３ｄの２つの入力端子は、選択回路２ｇ，２ｈの出力端子に接続されている。また、ＸＯＲ回路３ｅの２つの入力端子は、選択回路２ｉ，２ｊの出力端子に接続されており、ＸＯＲ回路３ｆの２つの入力端子は、選択回路２ｋ，２ｌの出力端子に接続されている。また、ＸＯＲ回路３ｇの２つの入力端子は、選択回路２ｍ，２ｎの出力端子に接続されており、ＸＯＲ回路３ｈの２つの入力端子は、選択回路２ｏ，２ｐの出力端子に接続されている。
【００２０】
ＸＯＲ回路３ｉの２つの入力端子は、ＸＯＲ回路３ａ，３ｂの出力端子に接続されており、ＸＯＲ回路３ｊの２つの入力端子は、ＸＯＲ回路３ｃ，３ｄの出力端子に接続されている。また、ＸＯＲ回路３ｋの２つの入力端子は、ＸＯＲ回路３ｅ，３ｆの出力端子に接続されており、ＸＯＲ回路３ｌの２つの入力端子は、ＸＯＲ回路３ｇ，３ｈの出力端子に接続されている。ＸＯＲ回路３ｍの２つの入力端子は、ＸＯＲ回路３ｉ，３ｊの出力端子に接続されており、ＸＯＲ回路３ｎの２つの入力端子は、ＸＯＲ回路３ｋ，３ｌの出力端子に接続されている。ＸＯＲ回路３ｏの２つの入力端子は、ＸＯＲ回路３ｍ，３ｎの出力端子に接続されており、ＸＯＲ回路３ｏの出力端子は、出力端子Ｐ２に接続されている。
【００２１】
図１の例では、上記のようにＸＯＲ回路３ａ〜３ｏは、ツリー状（トーナメント状）に接続されている。なお、ＸＯＲ回路は２入力に限定されず、３入力以上としてもよく、例えば、１つのＸＯＲ回路で選択回路２ａ〜２ｐから出力されるデータブロックのＸＯＲ演算を行ってもよい。
【００２２】
（演算回路１の動作例）
以下、演算回路１の動作の一例を説明する。なお、以下では図１に示されているようなＲＰＳ符号化行列の列ベクトルが、選択回路２ａ〜２ｐに入力される選択信号であるものとして説明する。
【００２３】
入力端子Ｐ１には、列番号が０から２９までの列ベクトルが選択信号として順に入力される。
列番号が０〜１５までの各列ベクトルでは、ある行の値が１であり、他の行の値は０である。選択信号としてこのような列ベクトルが入力端子Ｐ１に入力されたときには、値が１の行に対応するメモリに保持されているデータブロックが、選択回路２ａ〜２ｐの何れかから出力される。その他の選択回路からは、０が出力される。
【００２４】
これにより、上記のような接続関係をもつＸＯＲ回路３ａ〜３ｏの最後段のＸＯＲ回路３ｏからは、メモリＭ０〜Ｍ１５の何れかに保持されたデータブロックそのものが出力される。
【００２５】
列番号が１６〜２９までの各列ベクトルでは、複数の行の値が１である。選択信号としてこのような列ベクトルが入力端子Ｐ１に入力されたときには、値が１の行に対応するメモリに保持されている複数のデータブロックが、選択回路２ａ〜２ｐの何れか２以上から出力される。その他の選択回路からは、０が出力される。
【００２６】
これにより、上記のような接続関係をもつＸＯＲ回路３ａ〜３ｏの最後段のＸＯＲ回路３ｏからは、選択回路２ａ〜２ｐの何れか２以上から出力される複数のデータブロックのＸＯＲ演算結果が出力される。
【００２７】
以上のように、本実施の形態による演算回路１は、一旦複数のメモリＭ０〜Ｍ１５で各データブロックを保持し、メモリＭ０〜Ｍ１５から読み出された複数のデータブロックから、選択回路２ａ〜２ｐで演算に用いるものを選びＸＯＲ回路３ａ〜３ｏに渡す。このような並列化処理により、ＲＰＳ符号化処理のように複数のデータブロック間の組み合わせで多くのＸＯＲ演算を行う際、演算処理が効率化され、高速な演算が可能になる。
【００２８】
（第２の実施の形態）
以下、ＸＯＲ演算を行う演算回路の例として、送信回路に含まれ、ＲＰＳ符号化処理を行う符号化回路、また受信回路に含まれ、ＲＰＳ符号化処理で符号化された符号化データを復号する復号回路を説明する。
【００２９】
まず、ＲＰＳ符号化処理の一例を説明する。
図２は、ＲＰＳ符号化処理の一例を説明する図である。
まず、ＲＰＳ符号化による処理では、データが、一定サイズのデータブロックに分割される。ここでは、説明のため、１６ＫＢのデータが、１ＫＢごとの１６個のデータブロックに分割されるとし、分割された端子ブロックをブロックｂ０〜ｂ１５とする。
【００３０】
次に、符号化回路は、データの分割により得られたブロックｂ０〜ｂ１５から１つまたは複数個を選択して、選択されたブロックでＸＯＲ演算を行うことで、符号化データｄ０〜ｄ１５及び冗長符号化データｅ０〜ｅ１３を生成する。
【００３１】
その後、符号化データ等に、パケットとして、そのパケットヘッダに組み合わせ情報（後述の例では、図７のＲＰＳ符号化行列の列ベクトル）が追加され、さらに通信パケットヘッダが付与された後、ＵＤＰ（User Datagram Protocol）通信により送信される。このとき、伝送経路でパケットの消失や入れ換えが生じても、受信側は、受信した符号化データ等と、受信した組み合わせ情報（後述の例では、図１２の受信符号化行列）にガウスの消去法等を適用することで、元の送信データを復号することができる。
【００３２】
次に、データ通信に用いる情報処理装置の一例を説明する。
図３は、情報処理装置の一例を示す図である。
情報処理装置４は、コンピュータ５と、コンピュータ５に装着された機能拡張ボード６を有する。コンピュータ５は、ＣＰＵ（Central Processing Unit）５Ａ、主記憶部５Ｂ、ＰＣＩｅ（PCI express）バス５Ｃを有している。機能拡張ボード６には、メモリチップ６Ａ、ＦＰＧＡ（Field-Programmable Gate Array）６Ｂ、ＬＡＮ（Local Area Network）コネクタ６Ｃが搭載されている。また、ＣＰＵ５ＡとＦＰＧＡ６Ｂは、ＰＣＩｅバス５Ｃを介して接続されている。
【００３３】
ＣＰＵ５Ａは、送信データを図示しないＨＤＤ（Hard Disk Drive）等から読み出し、主記憶部５Ｂに格納させる。また、ＦＰＧＡ６Ｂに、ＲＰＳ符号化処理の実行等を指示する。
【００３４】
主記憶部５Ｂは、送信データや、ＣＰＵ５Ａによる処理に必要な各種データを格納している。主記憶部５Ｂには、例えば、ＲＡＭが用いられる。
メモリチップ６Ａは、ＦＰＧＡ６Ｂの有するＤＭＡ（Direct Memory Access）コントローラにより、主記憶部５Ｂから転送されてきたデータを格納する。メモリチップ６Ａには、例えば、ＲＡＭが用いられる。
【００３５】
ＦＰＧＡ６Ｂは、データのＲＰＳ符号化処理等を行い、通信用のパケットを生成し、ＬＡＮコネクタ６Ｃに出力する。
ＬＡＮコネクタ６Ｃは、ＦＰＧＡ６Ｂが出力したパケットを、ネットワークを介して、図示しない受信装置等に転送する。
【００３６】
（ＦＰＧＡ６Ｂの一例）
図４は、ＲＰＳ符号化処理を行うＦＰＧＡの一例について説明する図である。
なお、図４では、送信データのＲＰＳ符号化処理以外の制御及び機能を実行する部分については図示が省略されている。
【００３７】
ＦＰＧＡ６Ｂは、ＰＣＩｅインターフェース６Ｂ１、メモリコントローラ６Ｂ２、通信処理回路６Ｂ３、制御回路７、符号化回路８を有する。
ＰＣＩｅインターフェース６Ｂ１は、Ｉ／Ｏデバイス等によるＰＣＩｅエンドポイントであり、ＰＣＩｅバス５Ｃを介して転送されてきたデータ等に対して、物理層、データリンク層における処理等を行う。
【００３８】
メモリコントローラ６Ｂ２は、メモリチップ６Ａに格納されたデータを、一定サイズのデータブロックに分割し、ＢＲＡＭ（Block RAM）ｍ０〜ｍ１５に転送するメモリインターフェースである。メモリコントローラ６Ｂ２は、例えば、図２に示したように、１６ＫＢのデータを、一定サイズ１ＫＢの１６個のブロックｂ０〜ｂ１５に分割し、ＢＲＡＭｍ０〜ｍ１５に転送する。
【００３９】
通信処理回路６Ｂ３は、符号化回路８が出力した符号化データ等に対して、ネットワーク層、データリンク層、物理層における処理等を行い、通信用のパケットを生成してＬＡＮコネクタ６Ｃに出力する。
【００４０】
制御回路７は、符号化回路８が符号化データを生成する際の制御等を行う回路である。制御回路７の回路構成については、後述する。
符号化回路８は、複数のデータブロック間のＸＯＲ演算を行うことで、符号化データを生成する回路である。図２の例では、符号化回路８は、ブロックｂ０〜ｂ１５間のＸＯＲ演算を行い、符号化データｄ０〜ｄ１５及び冗長符号化データｅ０〜ｅ１３を生成する。
【００４１】
（符号化回路８の一例）
図５は、第２の実施の形態による符号化回路の一例を示す図である。
符号化回路８は、ＢＲＡＭｍ０〜ｍ１５、レジスタ９ａ〜９ｐ、ＡＮＤ回路１０ａ〜１０ｐ、ＸＯＲ回路１１ａ〜１１ｏ、レジスタ１２ａ〜１２ｏ、入力端子Ｐ３，Ｐ４，Ｐ５、出力端子Ｐ６を有する。
【００４２】
入力端子Ｐ３には、ＢＲＡＭｍ０〜ｍ１５へのデータブロックの書き込みを可能にするＷＥ（Write Enable）信号が、制御回路７から入力される。
入力端子Ｐ４には、ＢＲＡＭｍ０〜ｍ１５がデータブロックを書き込む際の書き込みアドレス信号や、ＢＲＡＭｍ０〜ｍ１５がデータブロックを読み出してＡＮＤ回路１０ａ〜１０ｐに出力する際の読み出しアドレス信号が、制御回路７から入力される。
【００４３】
入力端子Ｐ５には、ＡＮＤ回路１０ａ〜１０ｐに、後述するＲＰＳ符号化行列の列ベクトルの各要素が、制御回路７から入力される。
符号化回路８には、メモリチップ６Ａからメモリコントローラ６Ｂ２を介して、一定サイズに分割された１６個のデータブロックが供給される。
【００４４】
ＢＲＡＭｍ０〜ｍ１５は、入力端子Ｐ３，Ｐ４を介して制御回路７から書き込みアドレス信号及びＷＥ信号が入力されると、供給された１６個のデータブロック、例えば、図２のブロックｂ０〜ｂ１５を、それぞれ１ブロックずつ書き込み格納する。また、ＢＲＡＭｍ０〜ｍ１５は、入力端子Ｐ３を介して制御回路７から読み出しアドレス信号が入力されると、それぞれ、格納したデータブロックを読み出し、例えば、６４ビットずつ、レジスタ９ａ〜９ｐに出力する。
【００４５】
レジスタ９ａ〜９ｐは、ＢＲＡＭｍ０〜ｍ１５のそれぞれと、ＡＮＤ回路１０ａ〜１０ｂのそれぞれとの間に接続されている。レジスタ９ａ〜９ｐは、ＢＲＡＭｍ０〜ｍ１５が出力したデータブロックを保持し、保持したデータブロックのＡＮＤ回路出力タイミングを調整する。例えば、レジスタ９ａ〜９ｂは、図示しないクロック信号に同期したタイミングで、ＢＲＡＭｍ０〜ｍ１５から供給されたデータブロックを保持し、出力する。ＢＲＡＭｍ０〜ｍ１５から、ＡＮＤ回路１０ａ〜１０ｐまでの距離にばらつきがある場合、ＡＮＤ回路１０ａ〜１０ｐの入力側にこのようなレジスタ９ａ〜９ｐを設けることで、ＡＮＤ回路１０ａ〜１０ｐへの入力タイミングをそろえることができる。
【００４６】
ＡＮＤ回路１０ａ〜１０ｐは、選択回路として機能する。ＡＮＤ回路１０ａ〜１０ｐは、それぞれ、ＢＲＡＭｍ０〜ｍ１５が出力したデータブロックと、入力端子Ｐ５から入力されたＲＰＳ符号化行列の各値（選択信号に相当する）とのＡＮＤ演算を行い、その演算結果をＸＯＲ回路１１ａ〜１１ｈに出力する。このとき、ＡＮＤ回路１０ａ〜１０ｐは、それぞれ、入力端子Ｐ５を介して入力された列ベクトルの値が“１”となる行に対応したＢＲＡＭｍ０〜ｍ１５に保持されているデータブロックを選択し出力する。ＲＰＳ符号化行列の列ベクトルについては後述する。
【００４７】
ＸＯＲ回路１１ａ〜１１ｏは、ＡＮＤ回路１０ａ〜１０ｐが選択し出力したデータブロック間のＸＯＲ演算を行い、その演算結果を出力端子Ｐ６に出力する。
ＸＯＲ回路１１ａの２つの入力端子は、ＡＮＤ回路１０ａ，１０ｂの出力端子に接続されており、ＸＯＲ回路１１ｂの２つの入力端子は、ＡＮＤ回路１０ｃ，１０ｄの出力端子に接続されている。また、ＸＯＲ回路１１ｃの２つの入力端子は、ＡＮＤ回路１０ｅ，１０ｆの出力端子に接続されており、ＸＯＲ回路１１ｄの２つの入力端子は、ＡＮＤ回路１０ｇ，１０ｈの出力端子に接続されている。また、ＸＯＲ回路１１ｅの２つの入力端子は、ＡＮＤ回路１０ｉ，１０ｊの出力端子に接続されており、ＸＯＲ回路１１ｆの２つの入力端子は、ＡＮＤ回路１０ｋ，１０ｌの出力端子に接続されている。また、ＸＯＲ回路１１ｇの２つの入力端子は、ＡＮＤ回路１０ｍ，１０ｎの出力端子に接続されており、ＸＯＲ回路１１ｈの２つの入力端子は、ＡＮＤ回路１０ｏ，１０ｐの出力端子に接続されている。
【００４８】
ＸＯＲ回路１１ｉの２つの入力端子は、レジスタ１２ａ，１２ｂを介してＸＯＲ回路１１ａ，１１ｂの出力端子に接続されている。ＸＯＲ回路１１ｊの２つの入力端子は、レジスタ１２ｃ，１２ｄを介してＸＯＲ回路１１ｃ，１１ｄの出力端子に接続されている。また、ＸＯＲ回路１１ｋの２つの入力端子は、レジスタ１２ｅ，１２ｆを介してＸＯＲ回路１１ｅ，１１ｆの出力端子に接続されている。また、ＸＯＲ回路１１ｌの２つの入力端子は、レジスタ１２ｇ，１２ｈを介してＸＯＲ回路１１ｇ，１１ｈの出力端子に接続されている。ＸＯＲ回路１１ｍの２つの入力端子は、レジスタ１２ｉ，１２ｊを介してＸＯＲ回路１１ｉ，１１ｊの出力端子に接続されている。ＸＯＲ回路１１ｎの２つの入力端子は、レジスタ１２ｋ，１２ｌを介してＸＯＲ回路１１ｋ，１１ｌの出力端子に接続されている。ＸＯＲ回路１１ｏの２つの入力端子は、レジスタ１２ｍ，１２ｎを介してＸＯＲ回路１１ｍ，１１ｎの出力端子に接続されており、ＸＯＲ回路１１ｏの出力端子は、レジスタ１２ｏを介して出力端子Ｐ６に接続されている。出力端子Ｐ６は、ＸＯＲ回路１１ａ〜１１ｏが行ったデータブロック間のＸＯＲ演算結果を、符号化データ（前述の符号化データと冗長符号化データを含む）として通信処理回路６Ｂ３（図４）に出力する。
【００４９】
レジスタ１２ａ〜１２ｐは、レジスタ９ａ〜９ｐと同様の機能をもち、ＸＯＲ回路１１ａ〜１１ｏ間のデータ入出力のタイミング調整を行う。
図５の例では、上記のようにＸＯＲ回路１１ａ〜１１ｏは、複数段に渡ってツリー状（トーナメント状）に接続されている。なお、ＸＯＲ回路は２入力に限定されず、３入力以上としてもよく、例えば、１つのＸＯＲ回路でＡＮＤ回路１０ａ〜１０ｐから出力されるデータブロックのＸＯＲ演算を行ってもよい。
【００５０】
（制御回路７の一例）
図６は、制御回路の一例を示す図である。
制御回路７と前述した符号化回路８との接続を説明するために、符号化回路８の一部についても図示されている。
【００５１】
なお、図６では、符号化処理の制御を行う部分以外については、図示が省略されている。
制御回路７は、メイン制御回路１３を有している。メイン制御回路１３は、加算器１４、レジスタ１５、符号化行列保持部１６、比較回路１７、レジスタ１８、加算器１９を有している。さらに、制御回路７は、レジスタ２０，２１を有する。
【００５２】
加算器１４は、例えば、１を保持するフリップフロップを有し、レジスタ１５に保持されているアドレスをインクリメント（＋１）する。
レジスタ１５は、ＢＲＡＭｍ０〜ｍ１５の書き込みアドレスや読み出しアドレスを保持し、また、保持した書き込みアドレスや読み出しアドレスを、入力端子Ｐ３を介して、ＢＲＡＭｍ０〜ｍ１５に出力する。レジスタ１５は、図示しないクロック信号に同期して、保持しているアドレスに、加算器１４により＋１加算されたアドレスを保持する。
【００５３】
符号化行列保持部１６は、例えば、複数のレジスタを有し、ＲＰＳ符号化行列を格納する。
図７は、ＲＰＳ符号化行列の一例を示す図である。
【００５４】
図７に示すＲＰＳ符号化行列は、１６行３０列の行列である。
ＲＰＳ符号化処理による符号化データは、ＲＰＳ符号化行列の列ベクトルごとに生成される。ＲＰＳ符号化行列の列番が０〜１５の列ベクトルは、図２の例では、符号化データｄ０〜ｄ１５を生成する際に用いられる列ベクトルである。また、ＲＰＳ符号化行列の列番が１６〜２９の列ベクトルは、図２の例では、冗長符号化データｅ１６〜ｅ２９を生成する際に用いられる列ベクトルである。
【００５５】
列ベクトルにおける行は、ＢＲＡＭｍ０〜ｍ１５に対応している。つまり、列ベクトルにおけるある行の値が“１”のときには、その行に対応するＢＲＡＭに保持されているデータブロックがＸＯＲ演算に用いられる。
【００５６】
図６の符号化行列保持部１６は、ＲＰＳ符号化行列の列ベクトルを、レジスタ１８から出力される列番号に応じて、レジスタ２１に出力する。初期状態の場合、レジスタ１８に保持された値は０であるので、符号化行列保持部１６は、列番号が０（ｊ＝０）の列ベクトルを、レジスタ２１に出力する。
【００５７】
比較回路１７は、加算器１４でのインクリメント回数に基づき、ＢＲＡＭｍ０〜ｍ１５に１データブロック分（例えば、１ＫＢ）の書き込みが終わったかを判定し、１データブロック分の書き込みが終わると、レジスタ１８にセット信号を出力する。
【００５８】
レジスタ１８は、ＲＰＳ符号化行列の列番号を保持する。また、レジスタ１８は、比較回路１７が出力するセット信号を受けると、図示しないクロック信号に同期して、保持している列番号に、加算器１９により＋１加算された列番号の値を保持する。
【００５９】
加算器１９は、例えば、１を保持するフリップフロップを有し、レジスタ１８に保持されている列番号をインクリメントする。
レジスタ２０は、ＢＲＡＭｍ０〜ｍ１５への書き込みが可能になると、メイン制御回路１３内の、図示しないＷＥ信号生成部で生成されるＷＥ信号を保持する。また、レジスタ２０は、保持しているＷＥ信号を、入力端子Ｐ４を介して、ＢＲＡＭｍ０〜１５に出力する。
【００６０】
レジスタ２１は、保持しているＲＰＳ符号化行列の列ベクトルの各値を、入力端子Ｐ５を介して、ＡＮＤ回路１０ａ〜１０ｐに出力する。例えば、列ベクトルの１行目の値はＡＮＤ回路１０ａへ、２行目の値はＡＮＤ回路１０ｂへと、順次、入力される。
【００６１】
なお、本実施の形態による符号化回路８は、ＦＰＧＡ６Ｂ内に含まれるものとしたが、ＡＳＩＣ（Application Specific Integrated Circuit）等で実現するようにしてもよい。
【００６２】
（ＲＰＳ符号化処理の一例）
以下、符号化回路８によるＲＰＳ符号化処理の一例を説明する。
図８は、ＲＰＳ符号化処理の一例の流れを示すフローチャートである。
【００６３】
まず、ＢＲＡＭｍ０〜ｍ１５への、データブロックの書き込みが行われる（ステップＳ１）。ステップＳ１の処理では、制御回路７がＷＥ信号をアサートし、ＢＲＡＭｍ０〜１５に書き込みアドレスを供給する。そして、ＢＲＡＭｍ０〜ｍ１５は、メモリチップ６Ａからメモリコントローラ６Ｂ２を介して一定サイズに分割された１６個のデータブロックを書き込む。
【００６４】
また、メイン制御回路１３は、列番号ｊを０に設定する（ステップＳ２）。ステップＳ２の処理では、メイン制御回路１３のレジスタ１８の初期値が０に設定される。
次に、制御回路７は、ＲＰＳ符号化行列の列番号ｊの列ベクトルの各値をＡＮＤ回路１０ａ〜１０ｐに入力する（ステップＳ３）。ステップＳ３の処理では、図６に示したようなレジスタ２１が、入力端子Ｐ５を介して、保持しているＲＰＳ符号化の列番号ｊの列ベクトルの各値を、ＡＮＤ回路１０ａ〜１０ｐに入力する。
【００６５】
例えば、列番号ｊの列ベクトルの１行目の値はＡＮＤ回路１０ａへ、２行目の値はＡＮＤ回路１０ｂへと、順次、入力される。このとき、ＡＮＤ回路１０ａ〜１０ｐは、列番号ｊの列ベクトルの各値と、ＢＲＡＭｍ０〜１５のデータブロックとのＡＮＤ演算を行い、その演算結果をＸＯＲ回路１１ａ〜１１ｈに出力する。これにより、ＡＮＤ回路１０ａ〜１０ｐは、列ベクトルの“１”となる行の値に応じて、ＢＲＡＭｍ０〜１５に保持されているデータブロックを選択しＸＯＲ回路１１ａ〜１１ｈに出力する。例えば、図７に示すＲＰＳ符号化行列の列番号が０の列ベクトル（ｊ＝０）がＡＮＤ回路１０ａ〜１０ｐに入力された場合、１行目の値のみが“１”であるため、１行目の値が入力されるＡＮＤ回路１０ａは、ＢＲＡＭｍ０のデータブロックを選択し出力する。
【００６６】
その後、符号化回路８は、ＸＯＲ演算を行う（ステップＳ４）。ステップＳ４の処理では、ＸＯＲ回路１１ａ〜１１ｈにより、ＢＲＡＭｍ０〜ｍ１５に保持されているデータブロックを用いたＸＯＲ演算が行われる。
【００６７】
列番号ｊが０〜１５までの各列ベクトルは、ある行の値が１であり、他の行の値は０である。このような列ベクトルが入力端子Ｐ５に入力されたときには、上記のような接続関係をもつＸＯＲ回路１１ａ〜１１ｏの最後段のＸＯＲ回路１１ｏからは、値が１の行に対応するＢＲＡＭに保持されているデータブロックそのものが出力される。
【００６８】
列番号が１６〜２９までの各列ベクトルは、複数の行の値が１である。このような列ベクトルが入力端子Ｐ５に入力されたとき、上記のような接続関係をもつＸＯＲ回路１１ａ〜１１ｏの最後段のＸＯＲ回路１１ｏからは、ＡＮＤ回路１０ａ〜１０ｐの何れか２以上から出力される複数のデータブロックのＸＯＲ演算結果が出力される。
【００６９】
次に、メイン制御回路１３は、列番号ｊが最大値である２９に達したか否かを判定し（ステップＳ５）、列番号ｊが２９より小さい間は、加算器１９により列番号ｊに＋１を加算させる（ステップＳ６）。ステップＳ６の後は、ステップＳ３からの処理が繰り返される。
【００７０】
また、列番号ｊが２９に達した場合、１データブロックに関するＲＰＳ符号化処理は完了する。符号化回路８が、次のデータブロックに関するＲＰＳ符号化処理を行う際には、ステップＳ１からの処理が繰り返される。
【００７１】
その後、符号化回路８から出力される符号化データ及び冗長符号化データは、通信処理回路６Ｂ３の処理等を経て、パケットとして転送される。また、このとき、符号化に用いられた列ベクトルは、そのパケットヘッダに追加され、符号化データ及び冗長符号化データと共に転送される。
【００７２】
以上のように、本実施の形態による符号化回路８は、一旦複数のＢＲＡＭｍ０〜ｍ１５で各データブロックを保持し、列ベクトルの値に基づきＡＮＤ回路１０ａ〜１０ｐで演算に用いるデータブロックを選びＸＯＲ回路１１ａ〜１１ｏでＸＯＲ演算する。このような並列化処理により、多くのＸＯＲ演算を行うＲＰＳ符号化処理等において、演算処理が効率化され、高速な演算（符号化処理）が可能になる。
【００７３】
なお、符号化回路８において、ＢＲＡＭｍ０〜ｍ１５を６４ビット×５１２ワードで使用する場合、ＢＲＡＭｍ０〜ｍ１５は、１ＫＢのデータブロックであれば、それぞれ、４個分のデータブロックを保持することが可能となる。これにより、ＢＲＡＭｍ０〜ｍ１５は、４個分のデータブロックを連続してレジスタ９ａ〜９ｐへ入力することができるので、符号化処理のスループットがより向上する。さらには、ＢＲＡＭｍ０〜ｍ１５を、書き込みと読み出しが同時実行可能なデュアルポートメモリにすることで、ＢＲＡＭへ新たなデータブロックを書き込む時間を隠ぺいすることが可能になるため、よりスループットを向上できる。
【００７４】
次に、復号処理の一例を説明する。
（復号処理の一例）
図９は、ＲＰＳ符号化処理で得られた符号化データに対する復号処理の一例を説明する図である。
【００７５】
図９では、前述した符号化回路８から、ネットワークを介して、復号回路（図１０参照）に送られてくるパケットに含まれる符号化データｄ０〜ｄ１５及び冗長符号化データｅ０〜ｅ１３を復号する様子が示されている。
【００７６】
復号回路（図１０参照）では、受信したパケットのヘッダが参照され、ヘッダから符号化に用いたデータブロックの組み合わせ情報（ＲＰＳ符号化行列の列ベクトル）が抽出される。
【００７７】
符号化データｄ０，ｄ１，ｄ３〜ｄ１５は、データブロックであるブロックｂ０，ｂ１，ｂ３〜ｂ１５に相当するので、そのまま出力される。
図９の例では、符号化データｄ２を含むパケットが消失している例が示されている。復号回路は、受信できた符号化データ及び冗長符号化データと、抽出した組み合わせ情報から、消失したパケットのブロックｂ２を生成（復号）する。例えば、ブロックｂ２は、図９に示すように、符号化データｄ０，ｄ１，ｄ３，…，ｄ１５、冗長符号化データｅ０のＸＯＲ演算により生成される。
【００７８】
このように、復号回路でも、ＸＯＲ演算が行われ、回路構成は符号化回路８と同様なものとなる。
次に、復号処理を行う際に用いる復号回路について、図１０を用いて説明する。なお、復号回路は、例えば、図３に示したＦＰＧＡ６Ｂ内に符号化回路８と共に含まれていてもよい。復号回路を制御する制御回路については、図６に示したような制御回路７と同様の回路で実現できる。
【００７９】
（復号回路の一例）
図１０は、第２の実施の形態による復号回路の一例を示す図である。
復号回路８ａは、ＢＲＡＭｎ０，ｎ１，ｎ２，ｎ３，…，ｎ２６，ｎ２７，ｎ２８，ｎ２９、レジスタｒａ０，ｒａ１，ｒａ２，ｒａ３，…，ｒａ２６，ｒａ２７，ｒａ２８，ｒａ２９を有している。さらに復号回路８ａは、ＡＮＤ回路ａ０，ａ１，ａ２，ａ３，…，ａ２６，ａ２７，ａ２８，ａ２９とＸＯＲ回路部２２、入力端子Ｐ１３〜Ｐ１５、出力端子Ｐ１６を有する。
【００８０】
入力端子Ｐ１３には、ＢＲＡＭｎ０〜ｎ２９の符号化データ等の書き込みを可能にするＷＥ信号が入力される。
入力端子Ｐ１４には、ＢＲＡＭｎ０〜ｎ２９が符号化データ等を書き込む際の書き込みアドレスや、ＢＲＡＭｎ０〜ｎ２９が符号化データ等を読み出してＡＮＤ回路ａ０〜ａ２９に出力する際の読み出しアドレスが入力される。
【００８１】
入力端子Ｐ１５には、ＡＮＤ回路ａ０〜ａ２９に供給される、後述する復号ベクトルの各値が入力される。
ＢＲＡＭｎ０〜ｎ２９は、入力端子Ｐ１３，Ｐ１４を介して、書き込みアドレス、ＷＥ信号が入力されると、受信された符号化データ等を、それぞれ、１ブロックずつ書き込み保持する。また、ＢＲＡＭｎ０〜ｎ２９は、入力端子Ｐ１３を介して読み出しアドレスが入力されると、それぞれ、保持している符号化データ等を、例えば、６４ビットずつ、レジスタｒａ０〜ｒａ２９に出力する。
【００８２】
ＢＲＡＭｎ０〜ｎ２９は、符号化回路８が出力する３０個のデータブロック（符号化データ）、すなわち符号化データｄ０〜ｄ１５と冗長符号化データｅ０〜ｅ１３に対応して、３０個ある。レジスタｒａ０〜ｒａ２９、ＡＮＤ回路ａ０〜ａ２９も同様である。
【００８３】
レジスタｒａ０〜ｒａ２９は、図５に示したレジスタ９ａ〜９ｐと同様の機能を有する。
ＡＮＤ回路ａ０〜ａ２９は、図５に示したＡＮＤ回路１０ａ〜１０ｐと同様に選択回路として機能する。ＡＮＤ回路ａ０〜ａ２９は、それぞれ、ＢＲＡＭｎ０〜ｎ２９が出力した符号化データまたは冗長符号化データと、入力端子Ｐ５から入力された復号ベクトル（選択信号として機能する）の各値とのＡＮＤ演算を行う。そして、ＡＮＤ回路ａ０〜ａ２９は、その演算結果をＸＯＲ回路部２２に出力する。このとき、ＡＮＤ回路ａ０〜ａ２９は、それぞれ、入力端子Ｐ１５を介して入力された復号ベクトル（列ベクトル）が“１”となる行に応じて、ＢＲＡＭｎ０〜ｎ２９の符号化データまたは冗長符号化データを選択し出力する。
【００８４】
ＸＯＲ回路部２２は、図示を省略しているが、例えば、図５に示した符号化回路８と同様に、複数のＸＯＲ回路とレジスタがツリー状に接続されている回路となっている。
ＸＯＲ回路部２２は、ＡＮＤ回路ａ０〜ａ２９により選択され入力された符号化データまたは冗長符号化データのＸＯＲ演算を行い、元のデータブロックを復号する。
【００８５】
出力端子Ｐ１６は、復号された元のデータブロックを出力する。
以下、復号回路８ａの動作を説明する前に、復号処理に用いる復号ベクトルの生成処理を説明する。
【００８６】
（復号ベクトルの生成処理例）
復号ベクトルは、例えば、復号回路８ａを制御する図示しない制御回路にて生成される。
【００８７】
復号ベクトルの生成にあたって、まず、以下のような受信符号化行列が生成される。
図１１は、受信符号化行列の生成例を説明する図である。
また、図１２は、生成された受信符号化行列の一例を示す図である。
【００８８】
ＲＰＳ符号化処理で符号化されたデータ（符号化データまたは冗長符号化データ）を含むパケットのヘッダには、ＲＰＳ符号化行列の列ベクトルが含まれている。
例えば、受信側の制御回路は、上記のようなパケットを受信するたびに、ヘッダから上記列ベクトルを抽出し、列番号＝０から受信順に並べていくことで、図１２に示すような受信符号化行列を生成する。
【００８９】
図１２に示す受信符号化行列（１６行１６列）は、１６個のパケットを受信した時点で生成されたものである。以下では、受信符号化行列の列ベクトルを、例えば、列番号ｃを用いて列ベクトルＤ（ｃ）と表すものとし、列ベクトルＤ（ｃ）のｕ行目の値を、要素［ｕ］と表すものとする。
【００９０】
なお、図１２に示されている「基底ベクトル」と、「基底ベクトル候補」については後述する。
上記のような受信符号化行列から、復号ベクトルが生成される。
【００９１】
復号処理は、例えば、１次の連立方程式の解法として知られているガウスの消去法に似ている。例えば、１次の連立方程式における、解の係数である行列がＡ、解である列ベクトルがＸ、定数である列ベクトルがＣであるとしたとき、１次の連立方程式は、ＡＸ＝Ｃと表せる。そして、ＡＸ＝Ｃに対し、行列Ａが単位行列Ｅとなるように、ガウスの消去法が適用され、ＥＸ＝Ｃ１、すなわち、Ｘ＝Ｃ１が求められる。
【００９２】
本実施の形態による復号処理では、受信符号化行列は行列Ａ、元のデータブロックは列ベクトルＸ、符号化データまたは冗長符号化データは列ベクトルＣで表される。
ここで、復号回路８ａのＡＮＤ回路ａ０〜ａ２９に入力される選択信号として機能する復号ベクトルは、受信符号化行列に基づき、例えば、復号回路８ａを制御する図示しない制御回路において、例えば、以下のように生成される。
【００９３】
図１３は、復号ベクトルの生成処理の一例の流れを示すフローチャートである。
まず、複数の復号ベクトルの値が代入される行列ｏｐｓの初期化が行われる（ステップＳ１０）。
【００９４】
行列ｏｐｓの初期化は、行列ｏｐｓの対角要素が１、その他の要素が０となる単位行列を算出することにより行われる。また、行列ｏｐｓは、受信符号化行列の列数と、同数の行数及び列数をもつ。
【００９５】
次に、受信符号化行列の列番号ｃが０に設定される（ステップＳ１１）。列番号ｃは、後述のステップＳ１３の処理で、基底ベクトルまたは基底ベクトル候補の列番号が代入される変数である。
【００９６】
その後、受信符号化行列に含まれる列ベクトルについて、基底ベクトル、基底ベクトル候補の決定が行われる（ステップＳ１２）。
基底ベクトルは、１となる要素を１つだけ有し、また、互いに直交するベクトルである。また、以下において、要素［ｕ］（行番号がｕの値）が１となる基底ベクトルを、要素［ｕ］の基底ベクトルという。図１２に示した受信符号化行列の例において、列番号ｃの列ベクトルをＤ［ｃ］とすると、列番号ｃが０〜１２の列ベクトルＤ（０）〜Ｄ（１２）が、それぞれ、要素［３］〜［１２］の基底ベクトルと決定される。
【００９７】
基底ベクトル候補は、受信符号化行列に要素［ｕ］の基底ベクトルが存在しない場合、要素［ｕ］が１となる列ベクトルのことである。例えば、図１２に示した受信符号化行列では、要素［０］〜［２］の基底ベクトルが存在しない。そのため、要素［０］が１となる列ベクトルＤ（１３）が要素［０］の基底ベクトル候補、要素［２］が１となる列ベクトルＤ（１４）が要素［２］の基底ベクトル候補と決定される。また、要素［１］が１となる列ベクトルＤ（１５）が要素［１］の基底ベクトル候補と決定される。
【００９８】
次に、受信符号化行列の列ベクトルを、基底ベクトルへと変換していく処理が行われる（ステップＳ１３）。
ステップＳ１３の処理では、まず、受信符号化行列において、基底ベクトル（または基底ベクトル候補）の１となる要素と同じ行番号で要素が１となる列ベクトルが検出される。そして、検出された列ベクトルの当該要素を、当該要素と基底ベクトルの当該要素とのＸＯＲ演算結果で更新する。１と１のＸＯＲ演算結果は０であるため、検出された列ベクトルの当該要素は０となる。このような処理が受信符号化行列の各基底ベクトル（または基底ベクトル候補）で繰り返されることにより、受信符号化行列の基底ベクトル候補が、基底ベクトルに変換される。
【００９９】
図１４は、更新された受信符号化行列の一例を示す図である。
ステップＳ１３の処理によって、図１２に示した基底ベクトル候補であった列ベクトルＤ（１３）〜（１５）が、図１４に示されているように要素［０］〜［１］の基底ベクトルとなっている。
【０１００】
また、上記のステップＳ１３の処理では、受信符号化行列の基底ベクトル候補を基底ベクトルに変換させていく際のＸＯＲ演算処理結果が、行列ｏｐｓの各要素に代入されていき、例えば、以下のような行列ｏｐｓが生成される。
【０１０１】
図１５は、行列ｏｐｓの一例を示す図である。
行列ｏｐｓの各要素には、受信符号化行列の基底ベクトル候補を基底ベクトルへと変換していく際の、ＸＯＲ演算結果が代入されている。以下、行列ｏｐｓの列番号ｉの列ベクトルを列ベクトルｏｐ（ｉ）と表記する。
【０１０２】
図１２に示した受信符号化行列では、列ベクトルＤ（１３）〜Ｄ（１５）を基底ベクトルに変換するために、上記のようなＸＯＲ演算による更新処理が行われる。そのＸＯＲ演算結果により、行列ｏｐｓの列ベクトルｏｐ（１３）〜（１５）は、行列の対角要素以外で、１となる要素を有している。
【０１０３】
この行列ｏｐｓの列ベクトルが復号ベクトルとして用いられる。
図１６は、行列ｏｐｓの列ベクトル（復号ベクトル）と、その列ベクトルにより復号されるデータブロックとの関係の一例を示す図である。
【０１０４】
なお、図１６では、図１５に示した行列ｏｐｓの列ベクトルｏｐ（０）〜ｏｐ（１５）のそれぞれが、便宜的に、３２ビットの２進数で表現されている。
列ベクトルｏｐ（０）〜ｏｐ（１５）の右端の要素が、ビット０であり、列ベクトルｏｐ（０）〜ｏｐ（１５）の１行目の要素に対応している。
【０１０５】
上記のように、行列ｏｐｓの列ベクトルｏｐ（０）〜ｏｐ（１５）の値は、対応する列番号の受信符号化行列の列ベクトルを基底ベクトルへと変更していく際のＸＯＲ演算結果の値となっている。
【０１０６】
このような行列ｏｐｓの列ベクトルを復号ベクトルとして用いることにより、復号回路８ａでは、符号化データまたは冗長符号化データ間で、受信符号化行列を基底ベクトルへと変換していく際のＸＯＲ演算と同様の処理が行われる。
【０１０７】
行列ｏｐｓの列ベクトルｏｐ（０）〜ｏｐ（１５）により復号できるデータブロックは、その列ベクトルｏｐ（０）〜ｏｐ（１５）と同じ列番号の更新後の受信符号化行列の基底ベクトルの１となる要素の行番号に対応する。
【０１０８】
また、ここで、受信符号化行列は、符号化行列（図７）の列ベクトルから生成されているので、受信符号化行列の１〜１６行目の各要素は、符号化行列と同様に、データブロックが格納されたＢＲＡＭｍ０〜ｍ１５に対応する。すなわち、行列ｏｐｓの列ベクトルにより復号されるデータブロックは、その列ベクトルと同じ列番号の、更新後の受信符号化行列の基底ベクトルの１となる要素の行番号に対応したＢＲＡＭに保持していたデータブロックとなる。
【０１０９】
例えば、列ベクトルｏｐ（２）を用いてデータブロックを復号する場合、更新後の受信符号化行列（図１４）において、行列ｏｐｓの列ベクトルｏｐ（２）と同じ列番号となる列ベクトルは、列ベクトルＤ（２）である。また、列ベクトルＤ（２）は、要素［５］が１の基底ベクトルであるため、受信符号化行列の行番号５に対応したＢＲＡＭｍ５に格納されたブロックｂ５が復号される。
【０１１０】
列ベクトルｏｐ（１５）を用いてデータブロックを復号する場合、更新後の受信符号化行列（図１４）において、行列ｏｐｓの列ベクトルｏｐ（１５）と同じ列番号となる列ベクトルは、列ベクトルＤ（１５）である。また、列ベクトルＤ（１５）は、要素［２］が１の基底ベクトルであるため、受信符号化行列の行番号２に対応したＢＲＡＭｍ２に格納されたブロックｂ２が復号される。
【０１１１】
なお、パケット通信において、伝送経路で、消失した符号化データが少ない場合には、予め、復号ベクトルを計算しておき、復号回路８ａを制御する図示しない制御回路内の記憶部に格納しておくこともできる。
【０１１２】
（復号回路８ａの動作）
図１０に示したような復号回路８ａは、複数のＢＲＡＭｎ０〜ｎ２９で各データブロック（符号化データ（冗長符号化データも含む））を保持し、上記のような復号ベクトルの値に基づきＡＮＤ回路ａ０〜ａ２９で演算に用いるデータブロックを選ぶ。そして、選ばれたデータブロック間でのＸＯＲ演算が、ＸＯＲ回路部２２で行われる。このような並列化処理により、多くのＸＯＲ演算を行う復号処理において、演算処理が効率化され、高速な演算が可能になる。
【０１１３】
なお、復号回路８ａにより、元のデータブロックがすべて再現（復号）された場合、復号回路８ａを含む受信側の装置は、送信側の装置に対して復号完了信号を送るようにしてもよい。例えば、パケットの欠落がない場合には、符号化データｄ０〜ｄ１５を含む複数のパケットの受信が完了すると、受信側の装置は、復号完了信号を送信側の装置に送る。送信側の装置では、復号完了信号を受信した時点で、図８に示したような符号化回路８での符号化処理を停止させる。これにより、図７に示したようなＲＰＳ符号化行列のすべての列ベクトルに関して、ＸＯＲ演算を行わなくてもよくなる。
【０１１４】
（変形例）
図１７，１８は、第２の実施の形態による符号化回路の変形例を示す図である。なお、図１７，１８は、図５に示した符号化回路８の一部に対応している。符号化回路８と同様の要素については、図５と同一の符号を付し、その説明を省略する。
【０１１５】
図１７において、ＸＯＲ回路１１ａの出力側に、ＢＲＡＭ３０が接続されている。また、レジスタ１２ａとＢＲＡＭ３０の出力側に、セレクタ３１が接続されている。
ＢＲＡＭ３０は、ＸＯＲ回路１１ａのＸＯＲ演算結果、すなわち、ＢＲＡＭｍ０〜ｍ１のデータブロック間のＸＯＲ演算結果を保持する。また、セレクタ３１は、入力される選択信号に基づき、レジスタ１２ａと、ＢＲＡＭ３０の何れかを選択し出力する。選択信号は、例えば、図４に示した制御回路７から供給される。
【０１１６】
図１８において、ＸＯＲ回路１１ｉの出力側に、ＢＲＡＭ３２が接続されている。また、レジスタ１２ｉとＢＲＡＭ３２の出力側に、セレクタ３３が接続されている。
ＢＲＡＭ３２は、ＸＯＲ回路１１ｉのＸＯＲ演算結果、すなわち、ＢＲＡＭｍ０〜ｍ３のデータブロック間のＸＯＲ演算結果を保持する。また、セレクタ３３は、入力される選択信号に基づき、レジスタ１２ｉと、ＢＲＡＭ３２の何れかを選択し出力する。選択信号は、例えば、図４に示した制御回路７から供給される。
【０１１７】
図１７，１８では、ＸＯＲ回路１１ａ，１１ｉの出力側にＢＲＡＭ３０，３２やセレクタ３１，３３を設ける例について説明したが、同様にして、他のＸＯＲ回路１１ｂ〜１１ｈ，１１ｊ〜ｎの出力側に設けることもできる。
【０１１８】
図１９は、第２の実施の形態による符号化回路の変形例を示す図である。なお、図１９に示す符号化回路８ｂは、図５に示した符号化回路８の一部にＢＲＡＭ及びセレクタを設けたものである。また、符号化回路８と同様の要素については、図５に示した要素と同一の符号を付し、その説明を省略する。
【０１１９】
図１９の符号化回路８ｂのＸＯＲ回路１１ａの出力側には、ＢＲＡＭ３０が接続されている。また、レジスタ１２ａとＢＲＡＭ３０の出力側に、セレクタ３１が接続されている。
【０１２０】
ＢＲＡＭ３０は、ＸＯＲ回路１１ａのＸＯＲ演算結果を保持し、また、セレクタ３１は、入力される信号に基づき、レジスタ１２ａと、ＢＲＡＭ３０の何れかを選択し出力する。これにより、ＢＲＡＭｍ０とＢＲＡＭｍ１に保持されているデータブロック間のＸＯＲ演算結果が、ＢＲＡＭ３０に保持されるため、再度、そのＸＯＲ演算結果を利用することができる。
【０１２１】
図１９に示す符号化回路８ｂを用いた符号化処理の流れを以下に説明する。
図２０は、符号化処理の一例の流れを説明する図である。
例えば、列番号が０の列ベクトルが入力端子Ｐ５を介して符号化回路８ｂに入力されたとき、ＢＲＡＭｍ０とＢＲＡＭｍ１に保持されているデータブロック間のＸＯＲ演算結果がＢＲＡＭ３０に保持される。図２０に示すＲＰＳ符号化行列において、列番号が０の列ベクトルによるＢＲＡＭｍ０とＢＲＡＭｍ１に保持されているデータブロック間のＸＯＲ演算と同様の演算が、列番号が２８の列ベクトルにおいても行われる。
【０１２２】
そのため、列番号が０の列ベクトルにおいてＢＲＡＭ３０に保持されたＸＯＲ演算結果を、列番号が２８の列ベクトルによる符号化データ生成の際にも利用することができる。このとき、列番号が２７の列ベクトル以降において、ＢＲＡＭｍ０〜ｍ２のデータを用いることがないので、列番号が２７の列ベクトル以降において、ＢＲＡＭｍ０〜ｍ２に、次のデータブロックを書き込むことができる。これにより、符号化処理のスループットを向上させることができる。
【０１２３】
なお、上記のような変形は、図１０に示した復号回路８ａにも同様に適用できる。
以上、ＸＯＲ演算を行う演算回路の例として、符号化回路、復号回路を説明してきたが、これらに限定されるものではない。例えば、ＲＡＩＤ（Redundant Arrays of Inexpensive Disks）６等のように、複数回のＸＯＲ演算を行う（パリティデータの算出のため）ものにも適用可能である。
【０１２４】
上記については単に本発明の原理を示すものである。さらに、多数の変形、変更が当業者にとって可能であり、本発明は上記に示し、説明した正確な構成及び応用例に限定されるものではなく、対応するすべての変形例及び均等物は、添付の請求項及びその均等物による本発明の範囲とみなされる。
【符号の説明】
【０１２５】
１  演算回路
２ａ〜２ｐ  選択回路
３ａ〜３ｏ  ＸＯＲ回路
Ｍ０〜Ｍ１５  メモリ
Ｐ１  入力端子
Ｐ２  出力端子
【図１】
2015177917.tif 000003
【図２】
2015177917.tif 000004
【図３】
2015177917.tif 000005
【図４】
2015177917.tif 000006
【図５】
2015177917.tif 000007
【図６】
2015177917.tif 000008
【図７】
2015177917.tif 000009
【図８】
2015177917.tif 000010
【図９】
2015177917.tif 000011
【図１０】
2015177917.tif 000012
【図１１】
2015177917.tif 000013
【図１２】
2015177917.tif 000014
【図１３】
2015177917.tif 000015
【図１４】
2015177917.tif 000016
【図１５】
2015177917.tif 000017
【図１６】
2015177917.tif 000018
【図１７】
2015177917.tif 000019
【図１８】
2015177917.tif 000020
【図１９】
2015177917.tif 000021
【図２０】
2015177917.tif 000022
【手続補正書】
【提出日】平成28年10月26日(2016.10.26)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
メモリＭ０〜Ｍ１５は、例えば、ＲＡＭ（Random Access Memory）であり、ＸＯＲ演算を行う単位となる複数のデータブロックを保持する。データブロックは、例えば、符号化対象データが一定のデータサイズで分割されたものである。図１の例では、１６個のデータブロックのそれぞれが、メモリＭ０〜Ｍ１５の何れかに保持される。また、メモリＭ０〜Ｍ１５は、それぞれ、保持したデータブロックを、選択回路２ａ〜２ｐに出力する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
レジスタ９ａ〜９ｐは、ＢＲＡＭｍ０〜ｍ１５のそれぞれと、ＡＮＤ回路１０ａ〜１０ｐのそれぞれとの間に接続されている。レジスタ９ａ〜９ｐは、ＢＲＡＭｍ０〜ｍ１５が出力したデータブロックを保持し、保持したデータブロックのＡＮＤ回路出力タイミングを調整する。例えば、レジスタ９ａ〜９ｐは、図示しないクロック信号に同期したタイミングで、ＢＲＡＭｍ０〜ｍ１５から供給されたデータブロックを保持し、出力する。ＢＲＡＭｍ０〜ｍ１５から、ＡＮＤ回路１０ａ〜１０ｐまでの距離にばらつきがある場合、ＡＮＤ回路１０ａ〜１０ｐの入力側にこのようなレジスタ９ａ〜９ｐを設けることで、ＡＮＤ回路１０ａ〜１０ｐへの入力タイミングをそろえることができる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
レジスタ１２ａ〜１２ｏは、レジスタ９ａ〜９ｐと同様の機能をもち、ＸＯＲ回路１１ａ〜１１ｏ間のデータ入出力のタイミング調整を行う。
図５の例では、上記のようにＸＯＲ回路１１ａ〜１１ｏは、複数段に渡ってツリー状（トーナメント状）に接続されている。なお、ＸＯＲ回路は２入力に限定されず、３入力以上としてもよく、例えば、１つのＸＯＲ回路でＡＮＤ回路１０ａ〜１０ｐから出力されるデータブロックのＸＯＲ演算を行ってもよい。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５９
【補正方法】変更
【補正の内容】
【００５９】
加算器１９は、例えば、１を保持するフリップフロップを有し、レジスタ１８に保持されている列番号をインクリメントする。
レジスタ２０は、ＢＲＡＭｍ０〜ｍ１５への書き込みが可能になると、メイン制御回路１３内の、図示しないＷＥ信号生成部で生成されるＷＥ信号を保持する。また、レジスタ２０は、保持しているＷＥ信号を、入力端子Ｐ４を介して、ＢＲＡＭｍ０〜ｍ１５に出力する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００６３
【補正方法】変更
【補正の内容】
【００６３】
まず、ＢＲＡＭｍ０〜ｍ１５への、データブロックの書き込みが行われる（ステップＳ１）。ステップＳ１の処理では、制御回路７がＷＥ信号をアサートし、ＢＲＡＭｍ０〜ｍ１５に書き込みアドレスを供給する。そして、ＢＲＡＭｍ０〜ｍ１５は、メモリチップ６Ａからメモリコントローラ６Ｂ２を介して一定サイズに分割された１６個のデータブロックを書き込む。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００６４
【補正方法】変更
【補正の内容】
【００６４】
また、メイン制御回路１３は、列番号ｊを０に設定する（ステップＳ２）。ステップＳ２の処理では、メイン制御回路１３のレジスタ１８の初期値が０に設定される。
次に、制御回路７は、ＲＰＳ符号化行列の列番号ｊの列ベクトルの各値をＡＮＤ回路１０ａ〜１０ｐに入力する（ステップＳ３）。ステップＳ３の処理では、図６に示したようなレジスタ２１が、入力端子Ｐ５を介して、保持しているＲＰＳ符号化行列の列番号ｊの列ベクトルの各値を、ＡＮＤ回路１０ａ〜１０ｐに入力する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
例えば、列番号ｊの列ベクトルの１行目の値はＡＮＤ回路１０ａへ、２行目の値はＡＮＤ回路１０ｂへと、順次、入力される。このとき、ＡＮＤ回路１０ａ〜１０ｐは、列番号ｊの列ベクトルの各値と、ＢＲＡＭｍ０〜ｍ１５のデータブロックとのＡＮＤ演算を行い、その演算結果をＸＯＲ回路１１ａ〜１１ｈに出力する。これにより、ＡＮＤ回路１０ａ〜１０ｐは、列ベクトルの“１”となる行の値に応じて、ＢＲＡＭｍ０〜ｍ１５に保持されているデータブロックを選択しＸＯＲ回路１１ａ〜１１ｈに出力する。例えば、図７に示すＲＰＳ符号化行列の列番号が０の列ベクトル（ｊ＝０）がＡＮＤ回路１０ａ〜１０ｐに入力された場合、１行目の値のみが“１”であるため、１行目の値が入力されるＡＮＤ回路１０ａは、ＢＲＡＭｍ０のデータブロックを選択し出力する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１１７
【補正方法】変更
【補正の内容】
【０１１７】
図１７，１８では、ＸＯＲ回路１１ａ，１１ｉの出力側にＢＲＡＭ３０，３２やセレクタ３１，３３を設ける例について説明したが、同様にして、他のＸＯＲ回路１１ｂ〜１１ｈ，１１ｊ〜１１ｎの出力側に設けることもできる。
【手続補正９】
【補正対象書類名】図面
【補正対象項目名】図８
【補正方法】変更
【補正の内容】
【図８】
2015177917.tif 000023
【国際調査報告】
2015177917.tif 000024
2015177917.tif 000025