(57)【特許請求の範囲】
【請求項１】
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、qは拡大体GF(xq)の拡大次数であり、dは既約多項式f[X]から最高次項を除いた多項式f'の最高次項の次数であり、kは2以上の整数であり、mは1以上の整数であり、(m-1)(k-1)≦q-dであり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、bはb0, …, bm-1∈GF(xq)を要素とするm次ベクトルであり、Aはm行k列のファンデルモンデ行列であり、
ベクトルaと行列Aとを乗算してベクトルbを計算する行列作用装置であって、
i∈{0, …, m-1}について、次式により値biを計算する多項式乗算部と、
【数２１】
0005927323.tif 000022
i∈{0, …, m-1}について、上記値biのq次以上の部分をXqで割った多項式hiと、上記値biのq次未満の部分である多項式giとを用いて、gi-hif'を上記値biとする次数削減部と、
を含む行列作用装置。
【請求項２】
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、qは拡大体GF(xq)の拡大次数であり、dは既約多項式f[X]から最高次項を除いた多項式f'の最高次項の次数であり、kは2以上の整数であり、mは1以上の整数であり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、bはb0, …, bm-1∈GF(xq)を要素とするm次ベクトルであり、Aはm行k列のファンデルモンデ行列であり、αはq-d以下の正の整数であり、
ベクトルaと行列Aとを乗算してベクトルbを計算する行列作用装置であって、
j∈{0, …, k-1}について、a'j=aj, dj=0とするベクトル複製部と、
i∈{0, …, m-1}について、次式により値biを計算する多項式乗算部と、
【数２２】
0005927323.tif 000023
i∈{0, …, m-1}について、上記値biのq次以上の部分をXqで割った多項式hiと、上記値biのq次未満の部分である多項式giとを用いて、gi-hif'を上記値biとする次数削減部と、
i∈{0, …, m-1}, j∈{0, …, k-1}について、i≠m-1、かつ、(i+1)j-d≧q-dであれば、a'j:=a'jxα, dj:=dj+αと更新するベクトル更新部と、
を含む行列作用装置。
【請求項３】
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、qは拡大体GF(xq)の拡大次数であり、dは既約多項式f[X]から最高次項を除いた多項式f'の最高次項の次数であり、kは2以上の整数であり、mは1以上の整数であり、(m-1)(k-1)≦q-dであり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、bはb0, …, bm-1∈GF(xq)を要素とするm次ベクトルであり、Aはm行k列のファンデルモンデ行列であり、
ベクトルaと行列Aとを乗算してベクトルbを計算する行列作用方法であって、
多項式乗算部が、i∈{0, …, m-1}について、次式により値biを計算する多項式乗算ステップと、
【数２３】
0005927323.tif 000024
次数削減部が、i∈{0, …, m-1}について、上記値biのq次以上の部分をXqで割った多項式hiと、上記値biのq次未満の部分である多項式giとを用いて、gi-hif'を上記値biとする次数削減ステップと、
を含む行列作用方法。
【請求項４】
xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、qは拡大体GF(xq)の拡大次数であり、dは既約多項式f[X]から最高次項を除いた多項式f'の最高次項の次数であり、kは2以上の整数であり、mは1以上の整数であり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、bはb0, …, bm-1∈GF(xq)を要素とするm次ベクトルであり、Aはm行k列のファンデルモンデ行列であり、αはq-d以下の正の整数であり、
ベクトルaと行列Aとを乗算してベクトルbを計算する行列作用方法であって、
ベクトル複製部が、j∈{0, …, k-1}について、a'j=aj, dj=0とするベクトル複製ステップと、
多項式乗算部が、i∈{0, …, m-1}について、次式により値biを計算する多項式乗算ステップと、
【数２４】
0005927323.tif 000025
次数削減部が、i∈{0, …, m-1}について、上記値biのq次以上の部分をXqで割った多項式hiと、上記値biのq次未満の部分である多項式giとを用いて、gi-hif'を上記値biとする次数削減ステップと、
ベクトル更新部が、i∈{0, …, m-1}, j∈{0, …, k-1}について、i≠m-1、かつ、(i+1)j-d≧q-dであれば、a'j:=a'jxα, dj:=dj+αと更新するベクトル更新ステップと、
を含む行列作用方法。
【請求項５】
請求項１または２に記載の行列作用装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、符号化技術に関し、特に、符号化処理を効率的に行う技術に関する。
【背景技術】
【０００２】
従来の誤り訂正符号技術にリード・ソロモン符号（Reed-Solomon Codes）がある。リード・ソロモン符号については、例えば非特許文献１に記載されている。
【０００３】
誤り訂正符号の符号化処理は、平文の入力ベクトルaに線形変換（つまり行列）Aを乗じて出力ベクトルbを得る処理として、式（１）により表現できる。すなわち、行列Aのi番目の行は、出力ベクトルbのi番目の要素biを生成するために入力ベクトルaの各要素に乗じる係数を表す。
【０００４】
b = Aa        …（１）
誤り訂正符号の復号処理も線形変換と見ることができる。A', b'をA, bのうち復号に利用するk個の要素に対応する行だけを抜き出した行列もしくはベクトルとして、式（２）により表現できる。
【０００５】
b' = A'a        …（２）
したがって、行列Aに逆行列が存在すれば、式（３）により復号できる。
【０００６】
a = A'-1b'        …（３）
誤り訂正符号の符号化では、入力ベクトルaは式（４）で表されるk次のベクトルとする。ただし、kは2以上の整数である。
【０００７】
【数１】
0005927323.tif 000002
【０００８】
出力ベクトルbは式（５）で表されるn次のベクトルとする。ただし、nは2以上の整数であり、n≧2k-1である。
【０００９】
【数２】
0005927323.tif 000003
【００１０】
行列Aは、式（６）で表されるk行k列の単位行列とm行k列のファンデルモンデ行列（Vandermonde matrix）を縦に連結した行列である。ただし、m=n-kである。ファンデルモンデ行列とは、行または列の行列要素に等比数列の各項が順番にならんでいる特別な構成の行列である。
【００１１】
【数３】
0005927323.tif 000004
【００１２】
つまり、行列Aは式（７）のようなn行k列の行列である。
【００１３】
【数４】
0005927323.tif 000005
【００１４】
行列Aは、k行目までは単位行列であるため、出力ベクトルbのk番目までの要素b0, …, bk-1は入力ベクトルaの要素a0, …, ak-1と一致する。出力ベクトルbにおいて入力ベクトルaの要素と一致する要素をデータシェアと呼び、それ以外の要素をパリティシェアと呼ぶ。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】バァナード・スカラー著、「ディジタル通信 基本と応用」、ピアソン・エデュケーション、2006年
【発明の概要】
【発明が解決しようとする課題】
【００１６】
従来の誤り訂正符号技術では処理量が大きいという課題がある。特に、符号化処理において行われる体乗算の処理量が大きい。
【００１７】
この発明の目的は、このような点を鑑みて、符号化技術における体乗算の処理量を低減することができる行列作用技術を提供することである。
【課題を解決するための手段】
【００１８】
上記の課題を解決するために、この発明の第一の態様の行列作用装置は、xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、qは拡大体GF(xq)の拡大次数であり、dは既約多項式f[X]から最高次項を除いた多項式f'の最高次項の次数であり、kは2以上の整数であり、mは1以上の整数であり、(m-1)(k-1)≦q-dであり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、bはb0, …, bm-1∈GF(xq)を要素とするm次ベクトルであり、Aはm行k列のファンデルモンデ行列であり、ベクトルaと行列Aとを乗算してベクトルbを計算する行列作用装置であって、i∈{0, …, m-1}について、次式により値biを計算する多項式乗算部と、
【００１９】
【数５】
0005927323.tif 000006
【００２０】
i∈{0, …, m-1}について、値biのq次以上の部分をXqで割った多項式hiと、値biのq次未満の部分である多項式giとを用いて、gi-hif'を上記値biとする次数削減部と、を含む。
【００２１】
この発明の第二の態様の行列作用装置は、xは拡大体GF(xq)を生成する既約多項式f[X]の元Xであり、qは拡大体GF(xq)の拡大次数であり、dは既約多項式f[X]から最高次項を除いた多項式f'の最高次項の次数であり、kは2以上の整数であり、mは1以上の整数であり、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、bはb0, …, bm-1∈GF(xq)を要素とするm次ベクトルであり、Aはm行k列のファンデルモンデ行列であり、αはq-d以下の正の整数であり、ベクトルaと行列Aとを乗算してベクトルbを計算する行列作用装置であって、j∈{0, …, k-1}について、a'j=aj, dj=0とするベクトル複製部と、i∈{0, …, m-1}について、次式により値biを計算する多項式乗算部と、
【００２２】
【数６】
0005927323.tif 000007
【００２３】
i∈{0, …, m-1}について、値biのq次以上の部分をXqで割った多項式hiと、値biのq次未満の部分である多項式giとを用いて、gi-hif'を値biとする次数削減部と、i∈{0, …, m-1}, j∈{0, …, k-1}について、i≠m-1、かつ、(i+1)j-d≧q-dであれば、a'j:=a'jxα, dj:=dj+αと更新するベクトル更新部と、を含む。
【発明の効果】
【００２４】
この発明によれば、符号化技術における体乗算の処理量を低減することができる。
【図面の簡単な説明】
【００２５】
【図１】図１は第一実施形態に係る行列作用装置の機能構成を例示する図である。
【図２】図２は第一実施形態に係る行列作用方法の処理フローを例示する図である。
【図３】図３は第二実施形態に係る行列作用装置の機能構成を例示する図である。
【図４】図４は第二実施形態に係る行列作用方法の処理フローを例示する図である。
【発明を実施するための形態】
【００２６】
実施形態の説明に先立ち、この発明の原理について説明する。
【００２７】
前提として、以下の説明では、xは既約多項式をf[X]=X64+X4+X3+X2+X+1とする拡大体GF(264)の元Xである。xを整数表現すると2である。
【００２８】
GF(264)は多項式を、mod 2整数を係数とする64次多項式f[X]で割った（多項式としての割り算）余りの集合である。体であり四則演算を行うことができる。特殊な演算をもつビットの64次ベクトルと考えてもよい。GF(264)は64ビット整数で表現でき、項xiを2iで表現する。例えば、1+x+x3は、20+21+23=11と表現できる。
【００２９】
a, b∈GF(264)の乗算は、2つの63次多項式a, b（式（８））を掛けてから64次多項式fで割る操作である（式（９））。このとき、λ次の項の係数は式（10）となる。
【００３０】
【数７】
0005927323.tif 000008
【００３１】
式（９）において、126次多項式をmod fして63次多項式にする処理をリダクションと呼ぶ。リダクションは、式（11）の同値関係を用いて処理する。
f=x64+x4+x3+x+1=0 mod f        …（11）
【００３２】
式（11）を変形すると、式（12）に示すように64次項を4次式に落とす関係となる。
x64=x4+x3+x+1 mod f        …（12）
【００３３】
式（13）に示すように、64次以上の項もすべて60次次数を下げられる。
x64+n=xn(x4+x3+x+1) mod f        …（13）
【００３４】
126次多項式を、63次多項式gと62次多項式hを用いて、式（14）のように表すことができる。
g+x64h=g+(x4+x3+x+1)h mod f        …（14）
【００３５】
ある任意の要素aとx+1との乗算(x+1)aは、式（15）で表すことができる。
【００３６】
【数８】
0005927323.tif 000009
【００３７】
また、xnaはaの各項がn次高い項となるので、整数表現における2n倍、もしくはnビット左シフトと等価である。したがって、式（16）のように表すことができる。
【００３８】
【数９】
0005927323.tif 000010
【００３９】
hは62次多項式であるため、式（16）の
【００４０】
【数１０】
0005927323.tif 000011
【００４１】
は64次以上の多項式となり、再度次数を下げる必要がある。64次以上の部分は式（17）のようになる。
【００４２】
【数１１】
0005927323.tif 000012
【００４３】
64ビット整数内では64ビットを超えたビットは切り捨てられることを考慮すると、式（18）を計算すればよい。
【００４４】
【数１２】
0005927323.tif 000013
【００４５】
乗算の際、片方が61ビット以内のとき（より正確には両方のビット数を足して125以下のとき）、式（19）が成り立つため、リダクションを効率化できる。
【００４６】
【数１３】
0005927323.tif 000014
【００４７】
したがって、リダクションまで含めて考えると、61ビット数で1ビットだけが立っている数、つまり0≦i≦60の範囲での2iとの乗算は高速である。
【００４８】
従来の誤り訂正符号では、ファンデルモンデ行列を用いてパリティシェアを生成する。k個の入力をa0, …, ak-1∈GF(xq)とし、パリティシェアを式（20）により計算する。ただし、GF(xq)は既約多項式f[X]により生成され、拡大次数をqとする拡大体である。xは既約多項式f[X]の元であり、f[X]=Xである。
【００４９】
【数１４】
0005927323.tif 000015
【００５０】
このとき、体がサイズの大きな拡大体のときには効率化ができる。既約多項式fのうち、最高次項を除いた多項式をf'とする。多項式f'の最高次項の次数をdとする。すると、(m-1)(k-1)≦q-dを満たすとき、乗算が以下のように通常よりも簡単になる。
【００５１】
iがq未満のとき、xi=Xiである。入力aを式（21）とすると、多項式乗算の結果は、式（22）となる。
【００５２】
【数１５】
0005927323.tif 000016
【００５３】
ここで次数がq次以上となるので、f≡0⇔Xq≡-f'を用いて、fによる剰余をとる。つまり、aXiのうちq次未満の部分をg、q次以上の部分をXqで割った多項式hとおくと、aXi≡g-hf'と表される。拡大体乗算では通常、このような次数削減をg-hf'がq-1次となるまで繰り返す。このときiがq-d以下だと、aXiの次数はたかだかq-1+q-d≡2q-d-1であり、hの次数はたかだかq-d-1となる。f'がd次多項式なので、hf'の次数はたかだかq-1となり、次数削減が1回で済む。
【００５４】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００５５】
［第一実施形態］
第一実施形態の行列作用装置１は、図１に例示するように、ベクトル入力部１０、行列生成部１１、多項式乗算部１２、次数削減部１３、およびベクトル出力部１４を含む。この行列作用装置１が、図２に例示する各ステップの処理を行うことにより第一実施形態の行列作用方法が実現される。
【００５６】
行列作用装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。行列作用装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。行列作用装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。行列作用装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【００５７】
図２を参照して、第一実施形態の行列作用方法の処理手続きを説明する。
【００５８】
ステップＳ１０において、ベクトル入力部１０へ、値a0, …, ak-1∈GF(xq)を要素とするk次ベクトルa=(a0, …, ak-1)が入力される。ベクトルaは多項式乗算部１２へ送られる。ベクトルaは式（23）で定義される。
【００５９】
【数１６】
0005927323.tif 000017
【００６０】
ステップＳ１１において、行列生成部１１は、m行k列のファンデルモンデ行列Aを生成する。ここで、m, kは(m-1)(k-1)≦q-dが成り立つ値とする。行列Aは多項式乗算部１２へ送られる。行列Aは式（24）で定義される。
【００６１】
【数１７】
0005927323.tif 000018
【００６２】
つまり、行列Aは式（25）のようなm行k列の行列である。
【００６３】
【数１８】
0005927323.tif 000019
【００６４】
ステップＳ１２において、多項式乗算部１２は、i∈{0, …, m-1}について、式（26）により値biを計算する。値b0, …, bm-1は次数削減部１３へ送られる。
【００６５】
【数１９】
0005927323.tif 000020
【００６６】
ステップＳ１３において、次数削減部１３は、i∈{0, …, m-1}について、値biのq次以上の部分をXqで割った多項式hiと、値biのq次未満の部分である多項式giとを生成する。この多項式hiと多項式giとを用いて、gi-hif'を計算し、値biを更新する。更新された値b0, …, bm-1はベクトル出力部１４へ送られる。
【００６７】
ステップＳ１２とステップＳ１３の処理は、i∈{0, …, m-1}についてそれぞれ行う。これにより値b0, …, bm-1が計算される。各iに対する処理は並列に行うことができる。
【００６８】
ステップＳ１４において、ベクトル出力部１４は、値b0, …, bm-1を要素とするm次ベクトルb=(b0, …, bm-1)を出力する。
【００６９】
第一実施形態の行列作用方法では、(m-1)(k-1)≦q-dが成り立つため、すべての体乗算においてリダクションが1回で済むようになっている。そのため、リダクションを含めた乗算の処理量が低減する。
【００７０】
［第二実施形態］
第二実施形態では、(m-1)(k-1)≦q-dを満たさない場合でも体乗算の処理量を低減するように拡張する。
【００７１】
第二実施形態の行列作用装置２は、図３に例示するように、ベクトル入力部１０、行列生成部１１、多項式乗算部１２、次数削減部１３、およびベクトル出力部１４を第一実施形態と同様に含み、ベクトル複製部１５およびベクトル更新部１６をさらに含む。この行列作用装置２が、図４に例示する各ステップの処理を行うことにより第二実施形態の行列作用方法が実現される。
【００７２】
図４を参照して、第二実施形態の行列作用方法の処理手続きを説明する。以下では、上述の第一実施形態との相違点を中心に説明する。
【００７３】
ステップＳ１５において、ベクトル複製部１５は、j∈{0, …, k-1}について、a'j=ajとする。また、dj=0とする。ベクトルa'=(a'0, …, a'k-1)および値d0, …, dk-1は多項式乗算部１２へ送られる。
【００７４】
ステップＳ１１において、行列生成部１１は、m行k列のファンデルモンデ行列Aを生成する。ただし、第一実施形態とは異なり、m, kは(m-1)(k-1)≦q-dが成り立たなくともよい。行列Aは多項式乗算部１２へ送られる。
【００７５】
ステップＳ１２において、多項式乗算部１２は、i∈{0, …, m-1}について、式（27）により値biを計算する。値b0, …, bm-1は次数削減部１３へ送られる。
【００７６】
【数２０】
0005927323.tif 000021
【００７７】
ステップＳ１６において、ベクトル更新部１６は、j∈{0, …, k-1}について、i≠m-1、かつ、(i+1)j-d≧q-dであれば、a'j:=a'jxα, dj:=dj+αと更新する。ここで、αはq-d以下の正の整数である。更新されたベクトルa'=(a'0, …, a'k-1)および値d0, …, dk-1は多項式乗算部１２へ送られる。
【００７８】
第二実施形態では、第一実施形態ほどには処理量の削減はできないが、ベクトル更新部１６における更新回数が低ければ（すなわち、適切なαを設定すれば）、十分高速化に有効である。
【００７９】
［第三実施形態］
上記の実施形態において、拡大体の位数が2べきの場合は、加算は単に排他的論理和演算（XOR）となる。さらに、多項式乗算（ajxij）は、Xが整数表現で2となるため、単にijビットシフトとなる。したがって、コンピュータで処理するにあたって、特に効率的となる。
【００８０】
この発明は、ファンデルモンデ行列では乗算の右側axのxが単純な範囲に固定されていることにより有効となっている。多項式乗算におけるajXjのうち1項でも2q-d-1次を超えると次数削減が1回では収まらず、また、xijの多項式乗算がビットシフトで済むのはファンデルモンデ行列の要素がすべてxのべき乗であるからである。
【００８１】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００８２】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００８３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００８４】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００８７】
１  行列作用装置
１０  ベクトル入力部
１１  行列生成部
１２  多項式乗算部
１３  次数削減部
１４  ベクトル出力部
１５  ベクトル複製部
１６  ベクトル更新部
【要約】
【課題】体乗算の処理量を低減する。
【解決手段】行列作用装置１は、aはa0, …, ak-1∈GF(xq)を要素とするk次ベクトルであり、bはb0, …, bm-1∈GF(xq)を要素とするm次ベクトルであり、Aはm行k列のファンデルモンデ行列であり、ベクトルaと行列Aとを乗算してベクトルbを計算する。多項式乗算部１２は、値biを計算する。次数削減部１３は、値biのq次以上の部分をXqで割った多項式hiと、値biのq次未満の部分である多項式giとを用いて、gi-hif'を値biとする。
【選択図】図１【図１】
0005927323.tif 000026
【図２】
0005927323.tif 000027
【図３】
0005927323.tif 000028
【図４】
0005927323.tif 000029