(57)【要約】【課題】行列演算をハードウェアで実装する場合の回路規模を削減できる行列演算回路を提供する。【解決手段】行列演算回路は、ｍ行ｎ列の行列状に配置された１次元ＬＵＴ加法回路を備える。各１次元ＬＵＴ加法回路は、自回路が位置に対応する行列の要素ａｖｈと入力ベクトルＸの要素が取り得る値との２項演算結果を入力ベクトルＸの要素が取り得る値に対応付けて記憶するＬＵＴと、入力ベクトルＸにおける自回路が位置する列の要素の値に対応する２項演算結果をＬＵＴから読み出し、自回路と同じ行の後列の１次元ＬＵＴ加法回路の出力と読み出した２項演算結果との加法演算結果を自回路と同じ行の前列の１次元ＬＵＴ加法回路に出力する加法回路とを有する。行列演算に先立ち、各１次元ＬＵＴ加法回路の位置に対応する要素ａｖｈと入力ベクトルＸの要素が取り得る値との２項演算結果をそれぞれのＬＵＴに記憶させる。【選択図】図１
2015210725.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の要素を有する入力ベクトルＸとｍ行ｎ列の行列との行列演算を行う行列演算回路であって、
前記入力ベクトルＸの要素が取り得る値と前記行列の要素との２項演算結果を算出する２項演算テーブルと、
ｍ行ｎ列の行列状に配置され、配置された位置に対応する行列の要素と前記入力ベクトルＸの要素が取り得る値との２項演算結果と前記要素が取り得る値とを対応付けて記憶する１次元ＬＵＴと加法回路とを有する１次元ＬＵＴ加法回路と
を備え、
ｖ行目ｈ列目（１≦ｖ≦ｍ，１≦ｈ≦ｎ）に配置された前記１次元ＬＵＴ加法回路における前記加法回路は、
前記入力ベクトルＸのｈ番目の要素Ｘｈが示す値に対応付けられた２項演算結果を前記１次元ＬＵＴから読み出し、ｈ＝ｎの場合には読み出した２項演算結果をｖ行目（ｎ−１）列目に配置された前記１次元ＬＵＴ加法回路に出力し、ｈ＜ｎの場合には読み出した２項演算結果とｖ行目（ｈ＋１）列目に配置された前記１次元ＬＵＴ加法回路の出力する加法演算結果との加法演算結果をｖ行目（ｈ−１）列目に配置された前記１次元ＬＵＴ加法回路に出力し、
ｖ行目１列目に配置された前記１次元ＬＵＴ加法回路が出力する加法演算結果を行列演算結果として出力し、
行列演算が行われる前に、前記２項演算テーブルに前記行列の要素を入力するごとに、前記入力ベクトルＸの要素が取り得る値を逐次入力して得られる２項演算結果を前記行列の要素に対応する位置に配置された前記１次元ＬＵＴ加法回路が有する前記１次元ＬＵＴに記憶させる
ことを特徴とする行列演算回路。
【請求項２】
請求項１に記載の行列演算回路において、
前記２項演算テーブルは、
所定数の行に配置された前記１次元ＬＵＴ加法回路ごとに対応して設けられている
ことを特徴とする行列演算回路。
【請求項３】
請求項１又は請求項２のいずれかに記載の行列演算回路において、
前記１次元ＬＵＴ加法回路は、
前記１次元ＬＵＴとしての第１の１次元ＬＵＴ及び第２の１次元ＬＵＴと、
前記２項演算テーブルから入力される２項演算結果を前記第１の１次元ＬＵＴと前記第２の１次元ＬＵＴとのいずれか一方に記憶させ、入力される前記入力ベクトルＸの要素が示す値に対応する２項演算結果を他方から読み出す制御を行うインターリーブ制御回路と
を更に有し、
前記インターリーブ制御回路は、
行列演算が行われるごとに、２項演算結果を記憶させる１次元ＬＵＴと２項演算結果を読み出す１次元ＬＵＴとを切り替える
ことを特徴とする行列演算回路。
【請求項４】
請求項１又は請求項２のいずれかに記載の行列演算回路において、
前記１次元ＬＵＴ加法回路は、
行列演算に用いる行列の数に相当する１次元ＬＵＴを有し、
前記１次元ＬＵＴそれぞれは、前記行列演算に用いる行列に対応した２項演算結果を記憶し、
行列演算時に複数の前記１次元ＬＵＴからいずれか一つの１次元ＬＵＴを選択し、選択した１次元ＬＵＴから２項演算結果を読み出す
ことを特徴とする行列演算回路。
【請求項５】
請求項１から請求項４のいずれか一項に記載の行列演算回路において、
前記２項演算テーブルは、
前回の行列演算から前記行列の要素の値が変化した要素と前記入力ベクトルＸの要素が取り得る値との２項演算結果を、前記変化した要素に対応する位置に配置された前記１次元ＬＵＴ加法回路が有する前記１次元ＬＵＴに記憶させ、
前回の行列演算と前記行列の要素の値が変化していない要素と前記入力ベクトルＸの要素が取り得る値との２項演算結果を出力しない
ことを特徴とする行列演算回路。
【請求項６】
請求項１から請求項５のいずれか一項に記載の行列演算回路において、
前記２項演算テーブルは、
前回の行列演算から前記行列の要素の値が変化した要素の位置に対応する前記１次元ＬＵＴ加法回路を変化後の要素の値に基づいてグループ分けし、グループごとに当該グループに含まれる前記１次元ＬＵＴ加法回路が有する前記１次元ＬＵＴの２項演算結果を記憶させる
ことを特徴とする行列演算回路。
【請求項７】
ｍ行ｎ列の行列とｎ個の要素を有する入力ベクトルＸとの行列演算を行う行列演算回路であって、前記入力ベクトルＸの要素が取り得る値と前記行列の要素との２項演算結果を算出する２項演算テーブルと、ｍ行ｎ列の行列状に配置され、配置された位置に対応する行列の要素と前記入力ベクトルＸの要素が取り得る値との２項演算結果と前記要素が取り得る値とを対応付けて記憶する１次元ＬＵＴ及び加法回路を有する１次元ＬＵＴ加法回路とを備え、
ｖ行目ｈ列目（１≦ｖ≦ｍ，１≦ｈ≦ｎ）に配置された前記１次元ＬＵＴ加法回路における前記加法回路は、
前記入力ベクトルＸのｈ番目の要素Ｘｈが示す値に対応付けられた２項演算結果を前記１次元ＬＵＴから読み出し、ｈ＝ｎの場合には読み出した２項演算結果をｖ行目（ｎ−１）列目に配置された前記１次元ＬＵＴ加法回路に出力し、ｈ＜ｎの場合には読み出した２項演算結果とｖ行目（ｈ＋１）列目に配置された前記１次元ＬＵＴ加法回路の出力する加法演算結果との加法演算結果をｖ行目（ｈ−１）列目に配置された前記１次元ＬＵＴ加法回路に出力し、
ｖ行目１列目に配置された前記１次元ＬＵＴ加法回路が出力する加法演算結果を行列演算結果として出力する行列演算回路における行列演算方法であって、
行列演算が行われる前に、前記２項演算テーブルに前記行列の要素を入力するごとに、前記入力ベクトルＸの要素が取り得る値を逐次入力して得られる２項演算結果を前記行列の要素に対応する位置に配置された前記１次元ＬＵＴ加法回路が有する前記１次元ＬＵＴに記憶させるステップと、
ｈ列目に配置された前記１次元ＬＵＴ加法回路に、前記入力ベクトルの要素Ｘｈを入力して行列演算を行わせるステップと、
を有することを特徴とする行列演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列演算回路及び行列演算方法に関する。
【背景技術】
【０００２】
まず、本明細書において用いる用語について説明する。
乗法（回路）：整数では、一方の数に対して他方の数の回数だけ繰り返し和をとることにより定義できる演算。数の拡張にしたがってさらに広い範囲の数に対する乗法を定める。例えばガロア体においては原始元の指数同士の和で定義される。乗法回路は、乗法演算の結果を出力する回路のこと。
【０００３】
加法（回路）：自然数においては加法とはものの個数を加え合わせることであり、数の拡張にしたがってさらに広い範囲の数に対する加法を定める。例えばガロア体における加法は排他的論理和と等価である。加法回路は、入力に対し加法演算の結果を出力する回路のこと。
【０００４】
積和演算回路：ｚ＝ａ・ｘ＋ｂを演算する回路。
１次元ＬＵＴ：入力Ｘに対する出力Ｚの値を格納した表（テーブル）。
２次元ＬＵＴ：入力Ｘと入力Ｙとの組み合わせ（Ｘ，Ｙ）に対する出力Ｚの値を格納した表（テーブル）。例えば乗算に対しては入力Ｘと入力Ｙとが９以下の自然数である場合、掛け算九九の表が２次元ＬＵＴに相当する。
【０００５】
代数的符号においては符号化及び復号化は、行列演算で表記される（非特許文献１）。図７は、ｍ行ｎ列の行列演算回路の構成を示す図である。行列演算をハードウェアで実装する際には、図７に示すように、行と列との格子点上に積和演算回路１１０を配置する構成が用いられる。すなわち、行列演算回路では、ｍ×ｎ個の積和演算回路１１０がｍ行ｎ列の各格子点上に配置される。
【０００６】
ｈ（ｈ＝１，２，…，ｎ）列目に配置される各積和演算回路１１０には、入力Ｘ１２０｛Ｘ１，Ｘ２，…，Ｘｎ｝のうちＸｈが入力される。ｖ（ｖ＝１，２，…，ｍ）行目に配置される各積和演算回路１１０には、係数ベクトルＹ１２３｛Ｙ１，Ｙ２，…，Ｙｍ｝のうちベクトルＹｖが入力される。積和演算回路１１０は、入力されるＸｈ及びＹｖとの乗法を行う。また、また、ｖ行ｈ列目に配置される積和演算回路１１０には、ｖ行（ｈ＋１）列目に配置される積和演算回路１１０の出力が入力され、当該入力と乗法演算結果との加法を行い、加法演算結果をｖ行（ｈ−１）列目に配置される積和演算回路１１０に出力する。
【０００７】
各格子点上に配置されている積和演算回路１１０では、上述のように加法と乗法とが行われる。加法の演算は、単純であるため、論理回路（加法回路１０９）によって構成される。一方、乗法の演算は、複雑であり、すべて論理回路で構成すると回路規模や遅延が大きくなるため、ＬＵＴ（Look Up Table：ルックアップテーブル）によって構成されることがある。
【０００８】
図８は、積和演算回路１１０の構成例を示す図である。図８に示す積和演算回路１１０は、ｍ行ｎ列の行列演算装置においてｖ行目ｈ列目（１≦ｖ≦ｍ，１≦ｈ≦ｎ）に配置される積和演算回路１１０の構成例を示す図である。積和演算回路１１０には、入力Ｘ１２０のうちのｈ列の入力Ｘｈ１３０と、係数ベクトルＹ１２３のうちのｖ行目の係数ベクトルＹｖにおけるｈ列目の係数Ｙｖ［ｈ］（＝ａｖｈ）と、ｈ列演算結果入力Ｚｉｎ（ｈ）１３１とが入力される。積和演算回路１１０は、入力Ｘｈ１３０と係数ａｖｈとの乗法を行い、乗法演算結果とｈ列演算結果入力Ｚｉｎ（ｈ）１３１との加法を行い、加法演算結果をｈ行演算結果出力Ｚｏｕｔ（ｈ）１３２として出力する。
【０００９】
積和演算回路１１０は、図８に示すように、２次元ＬＵＴ１１１及び加法回路１０９を有している。２次元ＬＵＴ１１１には、ｈ列の入力Ｘｈ１３０が取り得る値と係数ａｖｈが取り得る値との組み合わせそれぞれに対する乗法演算結果がＬＵＴに記憶されている。２次元ＬＵＴ１１１は、入力される入力Ｘｈ１３０と係数ａｖｈとの組み合わせに対応する乗法演算結果をＬＵＴから読み出す。２次元ＬＵＴ１１１は、読み出した乗法演算結果１１１ａを加法回路１０９に出力する。
【００１０】
加法回路１０９は、入力されるｈ列演算結果入力Ｚｉｎ（ｈ）と、２次元ＬＵＴ１１１が出力する乗法演算結果とに対して加法演算を行う。加法回路１０９は、加法演算結果をｈ列演算結果出力Ｚｏｕｔ（ｈ）１３２としてｖ行（ｈ−１）列に配置されている積和演算回路１１０に出力する。ｖ行ｈ列に配置されている積和演算回路１１０が出力するｈ列演算結果出力Ｚｏｕｔ（ｈ）１３２は、ｖ行（ｈ−１）列に配置されている積和演算回路１１０においてｈ列演算結果入力Ｚｉｎ（ｈ）として入力される。上述の構成を有することにより、図７に示す行列演算回路は行列演算を行う。
【００１１】
また、ＬＵＴを書き換えることにより任意の演算が可能になるという理由でＬＵＴを用いることもある。しかし、ＬＵＴを用いて演算結果を取得する場合、演算の入力が取り得る値の組み合わせ数に応じて演算結果を格納する領域を確保する必要がある。例えば乗法のような２項演算では、ＬＵＴは２次元になり、一方の入力が取り得る値と他方が取り得る値とに対応した行数×列数分の演算結果を格納する領域が必要となる。二つの入力値のサイズがＳビットである場合には、ＬＵＴのサイズ（演算結果を格納する領域）が２Ｓの二乗となるため、回路規模が増加してしまうという問題があり、比較的小さな入力サイズにしか適用できなかった。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】阪田省二郎、「代数的符号理論」、電子情報通信学会  基礎・境界ソサイエティ Fundamentals Review、vol.1、no.3、一般社団法人電子情報通信学会、p.44-57
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明は、上記のような事情を鑑みてなされたもので、行列演算をハードウェアで実装する場合の回路規模を削減できる行列演算回路及び行列演算方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明の一態様は、ｎ個の要素を有する入力ベクトルＸとｍ行ｎ列の行列との行列演算を行う行列演算回路であって、前記入力ベクトルＸの要素が取り得る値と前記行列の要素との２項演算結果を算出する２項演算テーブルと、ｍ行ｎ列の行列状に配置され、配置された位置に対応する行列の要素と前記入力ベクトルＸの要素が取り得る値との２項演算結果と前記要素が取り得る値とを対応付けて記憶する１次元ＬＵＴと加法回路とを有する１次元ＬＵＴ加法回路とを備え、ｖ行目ｈ列目（１≦ｖ≦ｍ，１≦ｈ≦ｎ）に配置された前記１次元ＬＵＴ加法回路における前記加法回路は、前記入力ベクトルＸのｈ番目の要素Ｘｈが示す値に対応付けられた２項演算結果を前記１次元ＬＵＴから読み出し、ｈ＝ｎの場合には読み出した２項演算結果をｖ行目（ｎ−１）列目に配置された前記１次元ＬＵＴ加法回路に出力し、ｈ＜ｎの場合には読み出した２項演算結果とｖ行目（ｈ＋１）列目に配置された前記１次元ＬＵＴ加法回路の出力する加法演算結果との加法演算結果をｖ行目（ｈ−１）列目に配置された前記１次元ＬＵＴ加法回路に出力し、ｖ行目１列目に配置された前記１次元ＬＵＴ加法回路が出力する加法演算結果を行列演算結果として出力し、行列演算が行われる前に、前記２項演算テーブルに前記行列の要素を入力するごとに、前記入力ベクトルＸの要素が取り得る値を逐次入力して得られる２項演算結果を前記行列の要素に対応する位置に配置された前記１次元ＬＵＴ加法回路が有する前記１次元ＬＵＴに記憶させることを特徴とする行列演算回路である。
【００１５】
また、本発明の一態様は、上記に記載の行列演算回路において、前記２項演算テーブルは、所定数の行に配置された前記１次元ＬＵＴ加法回路ごとに対応して設けられていることを特徴とする。
【００１６】
また、本発明の一態様は、上記に記載の行列演算回路において、前記１次元ＬＵＴ加法回路は、前記１次元ＬＵＴとしての第１の１次元ＬＵＴ及び第２の１次元ＬＵＴと、前記２項演算テーブルから入力される２項演算結果を前記第１の１次元ＬＵＴと前記第２の１次元ＬＵＴとのいずれか一方に記憶させ、入力される前記入力ベクトルＸの要素が示す値に対応する２項演算結果を他方から読み出す制御を行うインターリーブ制御回路とを更に有し、前記インターリーブ制御回路は、行列演算が行われるごとに、２項演算結果を記憶させる１次元ＬＵＴと２項演算結果を読み出す１次元ＬＵＴとを切り替えることを特徴とする。
【００１７】
また、本発明の一態様は、上記に記載の行列演算回路において、前記１次元ＬＵＴ加法回路は、行列演算に用いる行列の数に相当する１次元ＬＵＴを有し、前記１次元ＬＵＴそれぞれは、前記行列演算に用いる行列に対応した２項演算結果を記憶し、行列演算時に複数の前記１次元ＬＵＴからいずれか一つの１次元ＬＵＴを選択し、選択した１次元ＬＵＴから２項演算結果を読み出すことを特徴とする。
【００１８】
また、本発明の一態様は、上記に記載の行列演算回路において、前記２項演算テーブルは、前回の行列演算から前記行列の要素の値が変化した要素と前記入力ベクトルＸの要素が取り得る値との２項演算結果を、前記変化した要素に対応する位置に配置された前記１次元ＬＵＴ加法回路が有する前記１次元ＬＵＴに記憶させ、前回の行列演算と前記行列の要素の値が変化していない要素と前記入力ベクトルＸの要素が取り得る値との２項演算結果を出力しないことを特徴とする。
【００１９】
また、本発明の一態様は、上記に記載の行列演算回路において、前記２項演算テーブルは、前回の行列演算から前記行列の要素の値が変化した要素の位置に対応する前記１次元ＬＵＴ加法回路を変化後の要素の値に基づいてグループ分けし、グループごとに当該グループに含まれる前記１次元ＬＵＴ加法回路が有する前記１次元ＬＵＴの２項演算結果を記憶させることを特徴とする。
【００２０】
また、本発明の一態様は、ｍ行ｎ列の行列とｎ個の要素を有する入力ベクトルＸとの行列演算を行う行列演算回路であって、前記入力ベクトルＸの要素が取り得る値と前記行列の要素との２項演算結果を算出する２項演算テーブルと、ｍ行ｎ列の行列状に配置され、配置された位置に対応する行列の要素と前記入力ベクトルＸの要素が取り得る値との２項演算結果と前記要素が取り得る値とを対応付けて記憶する１次元ＬＵＴ及び加法回路を有する１次元ＬＵＴ加法回路とを備え、ｖ行目ｈ列目（１≦ｖ≦ｍ，１≦ｈ≦ｎ）に配置された前記１次元ＬＵＴ加法回路における前記加法回路は、前記入力ベクトルＸのｈ番目の要素Ｘｈが示す値に対応付けられた２項演算結果を前記１次元ＬＵＴから読み出し、ｈ＝ｎの場合には読み出した２項演算結果をｖ行目（ｎ−１）列目に配置された前記１次元ＬＵＴ加法回路に出力し、ｈ＜ｎの場合には読み出した２項演算結果とｖ行目（ｈ＋１）列目に配置された前記１次元ＬＵＴ加法回路の出力する加法演算結果との加法演算結果をｖ行目（ｈ−１）列目に配置された前記１次元ＬＵＴ加法回路に出力し、ｖ行目１列目に配置された前記１次元ＬＵＴ加法回路が出力する加法演算結果を行列演算結果として出力する行列演算回路における行列演算方法であって、行列演算が行われる前に、前記２項演算テーブルに前記行列の要素を入力するごとに、前記入力ベクトルＸの要素が取り得る値を逐次入力して得られる２項演算結果を前記行列の要素に対応する位置に配置された前記１次元ＬＵＴ加法回路が有する前記１次元ＬＵＴに記憶させるステップと、ｈ列目に配置された前記１次元ＬＵＴ加法回路に、前記入力ベクトルの要素Ｘｈを入力して行列演算を行わせるステップと、を有することを特徴とする行列演算方法である。
【発明の効果】
【００２１】
本発明によれば、演算対象の行列のサイズに応じて行列状に配置する１次元ＬＵＴ加法回路における２項演算を１次元ＬＵＴで実装することにより、２項演算結果を得るために必要となる回路規模を削減することができ、行列演算回路全体の回路規模を削減することが可能となる。
【図面の簡単な説明】
【００２２】
【図１】第１の実施形態における行列演算回路の構成を示す図である。
【図２】第２の実施形態における行列演算回路の構成を示す図である。
【図３】第３の実施形態における１次元ＬＵＴ加算回路１０１の構成を示す図である。
【図４】第３の実施形態における１次元ＬＵＴ加算回路１０１の動作を示すタイミングチャートである。
【図５】第４の実施形態における行列演算回路の構成を示す図である。
【図６】第４の実施形態における１次元ＬＵＴ加算回路の構成を示す図である。
【図７】ｍ行ｎ列の行列演算回路の構成を示す図である。
【図８】積和演算回路１１０の構成例を示す図である。
【発明を実施するための形態】
【００２３】
本明細書に添付の図面を参照して、本発明の実施形態における行列演算回路及び行列演算方法を説明する。以下に説明する実施形態は本発明の実施の例であり、本発明は以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００２４】
（第１の実施形態）
図１は、第１の実施形態における行列演算回路の構成を示す図である。図１に示す行列演算回路は、ｍ行ｎ列の行列演算を行う回路であり、入力Ｘ１２０（＝｛Ｘ１，Ｘ２，…，Ｘｎ｝）と、係数ベクトルＹ１２３（＝｛Ｙ１，Ｙ２，…，Ｙｍ｝）とに対する行列演算を行う回路である。係数ベクトルＹ１２３におけるＹｖ（ｖ＝１，２，…，ｍ）は、ｍ行ｎ列の行列における各行の要素を含むベクトルである。また、各係数ベクトルＹｖには、ｖ行目のｈ列目における各要素ａｖｈ（ｈ＝１，２，…，ｎ）が含まれる。すなわち、係数ａｖｈは、ｍ行ｎ列の行列におけるｖ行目ｈ列目（１≦ｖ≦ｍ，１≦ｈ≦ｎ）の要素を示す。図１に示すように、行列演算回路は、ｍ行ｎ列の格子点上それぞれに配置された１次元ＬＵＴ加算回路１０１及び各行ごとに配置された２項演算テーブル１０２を備える。本実施形態における２項演算テーブル１０２は、乗法を行う回路である。
【００２５】
ｖ行ｈ列（１≦ｖ≦ｍ，１≦ｈ≦ｎ）に配置されている１次元ＬＵＴ加算回路１０１は、入力Ｘ１２０の要素Ｘｈと、ｈ列演算結果入力Ｚｉｎ（ｈ）とを入力とする。１次元ＬＵＴ加算回路１０１は、行列の要素を示す係数ａｖｈと要素Ｘｈとの乗法演算結果を取得し、乗法演算結果とｈ列演算結果入力Ｚｉｎ（ｈ）との加法を行う。１次元ＬＵＴ加算回路１０１は、加法演算結果をｈ列演算結果出力Ｚｏｕｔ（ｈ）としてｖ行（ｈ−１）列に配置されている１次元ＬＵＴ加算回路１０１に出力する。１次元ＬＵＴ加算回路１０１は、要素Ｘｈと係数ａｖｈとの乗法演算結果を得るための１次元ＬＵＴを有している。ここで、ｈ列演算結果入力Ｚｉｎ（ｈ）は、ｖ行（ｈ＋１）列に配置されている１次元ＬＵＴ加算回路１０１から出力される加法演算結果（Ｚｏｕｔ（ｈ＋１））である。
【００２６】
なお、ｖ行ｎ列に配置されている１次元ＬＵＴ加算回路１０１には、ｈ列演算結果入力Ｚｉｎ（ｈ）として「０」が入力される。ｎ列に配置されている１次元ＬＵＴ加算回路１０１は、行列の要素を示す係数ａｖｎと要素Ｘｎとの乗法演算結果を取得し、乗法演算結果と「０」とのは方演算結果をｈ列演算結果出力Ｚｏｕｔ（ｈ）としてｖ行（ｎ−１）列に配置されている１次元ＬＵＴ加算回路１０１に出力する。
【００２７】
ｖ行１列に配置されている１次元ＬＵＴ加算回路１０１が出力する加法演算結果は、行列演算回路の出力Ｚ１２２（＝｛Ｚ１，Ｚ２，…，Ｚｍ｝）の要素Ｚｖになる。
【００２８】
２項演算テーブル１０２は、入力Ｘ１２０の各要素が取り得る値ｘと、係数ベクトルＹ１２３の各要素が取り得る値との乗法（２項演算）を行い、乗法演算結果Ｍ（ｉ，Ｙｖ）（ｉ＝１，２，…，ｎ）を出力する。２項演算テーブル１０２には、行列演算回路が行列演算を行う前に、各行に対応した係数ベクトルＹ１２３の要素｛ａｖ１，ａｖ２，…，ａｖｎ｝が順に入力され、係数ベクトルＹ１２３の要素が入力されるごとに入力Ｘ１２０の要素が取り得る値すべてが逐次入力される。２項演算テーブル１０２は、係数ベクトルＹ１２３の要素と、入力Ｘ１２０の要素が取り得る値との乗法演算結果を出力する。係数ベクトルの要素ａｖｈ（ｈ＝１，２，…，ｎ）との乗法演算結果は、ｖ行ｈ列に配置されている１次元ＬＵＴ加算回路１０１に出力される。
【００２９】
各１次元ＬＵＴ加算回路１０１は、行列演算に先立ち、係数ベクトルＹ１２３の該当行の要素に対応した２項演算テーブル１０２から出力される乗法演算結果を１次元ＬＵＴに書き込んで記憶させる。すなわち、ｖ行ｈ列に配置されている１次元ＬＵＴ加算回路１０１が有する１次元ＬＵＴには、入力Ｘ１２０の要素Ｘｈの取り得る値と係数ａｖｈとの乗法演算結果が記憶されることになる。
【００３０】
ｖ行ｎ列に配置されている１次元ＬＵＴ加算回路１０１には、入力Ｘ１２０の要素Ｘｎが入力される。１次元ＬＵＴ加算回路１０１は、入力された要素Ｘｎの示す値に対応する乗法演算結果（ａｖｎ×Ｘｎ）を１次元ＬＵＴから読み出し、読み出した乗法演算結果（ａｖｎ×Ｘｎ）と「０」との加法を行う。ｖ行ｎ列に配置されている１次元ＬＵＴ加算回路１０１は、加法演算結果（ａｖｎ×Ｘｎ）をｖ行（ｎ−１）列に配置されている１次元ＬＵＴ加算回路１０１に出力する。
【００３１】
ｖ行（ｎ−１）列に配置されている１次元ＬＵＴ加算回路１０１は、前段のｖ行ｎ列に配置されている１次元ＬＵＴ加算回路１０１からの入力（ａｖｎ×Ｘｎ）と、１次元ＬＵＴから読み出した乗法演算結果（ａｖ（ｎ−１）×Ｘｎ−１）とを加算することにより、（ａｖ（ｎ−１）×Ｘｎ−１＋ａｖｎ×Ｘｎ）を算出する。ｖ行（ｎ−１）列に配置されている１次元ＬＵＴ加算回路１０１は、算出した加法演算結果（ａｖ（ｎ−１）×Ｘｎ−１＋ａｖｎ×Ｘｎ）をｖ行（ｎ−２）列に配置されている１次元ＬＵＴ加算回路１０１に出力する。
【００３２】
ｖ行に配置されている各１次元ＬＵＴ加算回路１０１が同様に乗法及び加法を行い、列数が小さい側に隣接する１次元ＬＵＴ加算回路１０１に加法演算結果を出力することが繰り返され、ｖ行１列に配置されている１次元ＬＵＴ加算回路１０１が加法演算結果として（ａｖ１×Ｘ１＋ａｖ２×Ｘ２＋…＋ａｖ（ｎ−１）×Ｘｎ−１＋ａｖｎ×Ｘｎ）を出力する。ｖ行１列に配置されている１次元ＬＵＴ加算回路１０１の出力は、行列演算回路の出力Ｚ１２２におけるｖ行の出力Ｚｖとなる。
【００３３】
各行の１次元ＬＵＴ加算回路１０１が同様に乗法及び加法を行うことにより、１列目に配置されている各１次元ＬＵＴ加算回路１０１から所望の出力Ｚ１２２｛Ｚ１，Ｚ２，…，Ｚｍ｝が出力される
【００３４】
図７に示した行列演算回路では、ｍ行ｎ列の格子点上に配置されるすべての積和演算回路１１０が２次元ＬＵＴ１１１を有していた。これに対して、第１の実施形態における行列演算回路は、ｍ行ｎ列の格子点上に配置される１次元ＬＵＴ加算回路１０１が２次元ＬＵＴを有さない構成となっている。２項演算テーブル１０２が２次元ＬＵＴを有する構成とした場合、第１の実施形態における行列演算回路が備える２次元ＬＵＴの個数は、図７の行列演算回路に対して（１／ｎ）になる。また、２項演算テーブル１０２において、入力Ｘ１２０の各要素が取り得る値と、係数ベクトルＹ１２３の各要素が取り得る値との乗法演算結果が２項演算回路で直接算出される場合、第１の実施形態における行列演算回路は２次元ＬＵＴを備えないことになる。
【００３５】
一般に複雑な２項演算を行う回路を実装する場合、並列数を増やすことで処理時間を短縮して高スループット化を行う。信号に対する符号化及び復号化をフレーム単位で行う場合には、１フレーム時間内に次のフレームに対する係数ベクトルの演算を完了すればよいので、フレーム長が長い符号化又は復号化に第１の実施形態における行列演算回路を適用するときには、並列数の少ない小さな２項演算回路で２項演算を行うことが可能になる。
【００３６】
ＯＴＮ（Optical Transport Network）のようにフレーム長が固定長の場合、次のフレームに対する係数ベクトルの転送は１フレーム時間内に完了すればよい。すなわち、１フレーム時間をＴ［ｓｅｃ］、列数をｎ、係数ベクトル転送レート［ｂｙｔｅ／ｓｅｃ］で表し、８ビットＧＦ（２８）のガロア体演算を行うとすると、１フレームあたり（列数×ガロア体の元の数（２５６＝２８））の乗法を転送することになるので、次式（１）が満たされればよいことになる。言い換えれば、次式（１）を満たすようにＢを設定する。
Ｔ≧ｎ・２５６／Ｂ  …（１）
【００３７】
（第２の実施形態）
図２は、第２の実施形態における行列演算回路の構成を示す図である。ｍ行ｎ列の行列演算を行う回路であり、入力Ｘ１２０（＝｛Ｘ１，Ｘ２，…，Ｘｎ｝）と、係数ベクトルＹ１２３（＝｛Ｙ１，Ｙ２，…，Ｙｍ｝）とに対する行列演算を行う回路である。第２の実施形態における行列演算回路は、２項演算テーブル１０２を複数の行で共有する構成を有する点が、第１の実施形態における行列演算回路と異なる。図２に示す行列演算回路は、ｍ行ｎ列の格子点上それぞれに配置された１次元ＬＵＴ加算回路１０１、２項演算テーブル１０２及び選択回路１０３を有している。
【００３８】
選択回路１０３は、係数ベクトルＹ１２３のうち、いずれの係数ベクトルＹｖ（ｖ＝１，２，…，ｍ）を２項演算テーブル１０２に出力するかを選択する。また、選択回路１０３は、各行の１次元ＬＵＴ加算回路１０１のうち、いずれの行の１次元ＬＵＴ加算回路１０１に２項演算テーブル１０２の乗法演算結果を出力するかを選択する。係数ベクトルＹｖの入力先の選択と乗法演算結果の出力先の選択とは、選択回路１０３に設けられる制御回路によって行われる。制御回路が、係数ベクトルＹｖの入力先を切り替えるとともに、２項演算テーブル１０２が出力する乗法演算結果の出力先を切り替えることにより、係数ベクトルＹｖに対応する行の１次元ＬＵＴ加算回路１０１に２項演算結果Ｍ（ｉ，Ｙｖ）が出力される。
【００３９】
選択回路１０３が２項演算テーブル１０２の入出力を行単位に逐次的に切り替えることにより、複数の行の１次元ＬＵＴ加算回路１０１に対して２項演算テーブル１０２を共有させることができ、行列演算回路における２項演算テーブルの個数を減らすことができる。すなわち、行列演算回路において２次元ＬＵＴの数を減らすことができ、行列演算回路の回路規模を減らすことができる。第２の実施形態における行列演算回路において、２次元ＬＵＴの数を最小で１個まで減らすことができる。しかし、複数の行の１次元ＬＵＴ加算回路１０１に対して２項演算テーブル１０２を共有させる際に、行列演算回路が２個以上の２項演算テーブル１０２と選択回路１０３とを備えていてもよい。
【００４０】
ＯＴＮのフレーム長は、１６３２０ｂｙｔｅである。行列演算回路における列数を８とした場合、１行あたりの係数ベクトル転送バイト数は８×２５６＝２０４８ｂｙｔｅとなる。フレームデータの転送レートと係数ベクトル転送レートとが等しいとき、１６３２０／２０４８＝７．９７であるので、７行分の２項演算テーブル１０２を行列演算回路において共有可能であることが分かる。
【００４１】
フレーム長をＬとし、係数ベクトルのバイト数をＣとし、係数ベクトルの転送レートに対するフレームデータの転送レートの比をｋとした場合、２項演算テーブル１０２を共有できる行数Ｍは、次式（２）で表される。なお、関数Ｆｌｏｏｒ（ｘ）は、床関数であり、底値（ｘの整数部分）を返す関数である。この場合、第２の実施形態における行列演算回路は、第１の実施形態における行列演算回路に対して（１／Ｍ）個の２項演算テーブル１０２を備えれば、行列演算を１フレーム時間内に１次元ＬＵＴに記憶させる乗法演算結果を算出することができる。
Ｍ＝Ｆｌｏｏｒ（ｋ・Ｌ／Ｃ）  …（２）
【００４２】
（第３の実施形態）
第３の実施形態における行列演算回路は、行列演算を行っている際にも、各１次元ＬＵＴ加算回路１０１の１次元ＬＵＴを更新できる構成を有している。図３は、第３の実施形態における１次元ＬＵＴ加算回路１０１の構成を示す図である。図３に示す１次元ＬＵＴ加算回路１０１は、ｖ行目ｈ列目に配置された１次元ＬＵＴ加算回路１０１を示している。同図に示すように、１次元ＬＵＴ加算回路１０１は、１次元ＬＵＴ１０４、１次元ＬＵＴ１０５、書込制御回路１０６、ＬＵＴ選択スイッチ１０７、インターリーブ制御回路１０８及び加法回路１０９を有している。
【００４３】
ｖ行ｈ列に配置されている１次元ＬＵＴ加算回路１０１において、１次元ＬＵＴ１０４には、入力Ｘｈ１３０が取り得る値と係数ａｖｈとの乗法演算結果Ｍ（ｉ，Ｙｖ）がＬＵＴ選択スイッチ１０７を介して書込制御回路１０６から入力される。１次元ＬＵＴ１０４は、入力Ｘｈ１３０が取り得る値ごとに当該値と係数ａｖｈとの乗法演算結果を対応付けて記憶する。１次元ＬＵＴ１０４は、入力される入力Ｘｈ１３０に対応する乗法演算結果をＬＵＴ選択スイッチ１０７に出力する。１次元ＬＵＴ１０５は、１次元ＬＵＴ１０４と同じ構成を有している。
【００４４】
書込制御回路１０６は、１次元ＬＵＴ１０４又は１次元ＬＵＴ１０５に記憶させる乗法演算結果Ｍ（ｉ，Ｙｖ）を含む情報をＬＵＴ更新情報入力１３３から検出し、検出した乗法演算結果Ｍ（ｉ，Ｙｖ）をＬＵＴ選択スイッチ１０７に出力する。また、書込制御回路１０６は、１次元ＬＵＴ１０４又は１次元ＬＵＴ１０５に記憶させる乗法演算結果Ｍ（ｉ，Ｙｖ）を含む情報をＬＵＴ更新情報入力１３３から検出すると、１次元ＬＵＴ１０４又は１次元ＬＵＴ１０５への書き込みを示す書込信号１０６ａをインターリーブ制御回路１０８に出力する。ＬＵＴ更新情報入力１３３は、２項演算テーブル１０２が出力する情報である。すなわち、１次元ＬＵＴ１０４又は１次元ＬＵＴ１０５への乗法演算結果Ｍ（ｉ，Ｙｖ）の書き込みは、２項演算テーブル１０２がＬＵＴ更新情報入力１３３を出力することに応じて行われる。
【００４５】
ＬＵＴ選択スイッチ１０７は、書込制御回路１０６から入力１０７ｂに入力される乗法演算結果Ｍ（ｉ，Ｙｖ）を、切替信号１０７ａに基づいて１次元ＬＵＴ１０４と１次元ＬＵＴ１０５とのいずれか一方に出力して記憶させる。ＬＵＴ選択スイッチ１０７は、切替信号１０７ａに基づいて、１次元ＬＵＴ１０４が出力する乗法演算結果（ａｖｈ×Ｘｈ）と、１次元ＬＵＴ１０５が出力する乗法演算結果とのいずれか一方を選択し、選択した乗法演算結果を加法回路１０９に出力する。切替信号１０７ａは、インターリーブ制御回路１０８によって生成される制御信号１０８ａである。
【００４６】
ＬＵＴ選択スイッチ１０７は、乗法演算結果Ｍ（ｉ，Ｙｖ）を１次元ＬＵＴ１０４に書き込む場合には１次元ＬＵＴ１０５から出力される乗法演算結果を加法回路１０９に出力する。ＬＵＴ選択スイッチ１０７は、乗法演算結果Ｍ（ｉ，Ｙｖ）を１次元ＬＵＴ１０５に書き込む場合には１次元ＬＵＴ１０４から出力される乗法演算結果を加法回路１０９に出力する。すなわち、ＬＵＴ選択スイッチ１０７は、一方の１次元ＬＵＴに書き込む場合、他方の１次元ＬＵＴから乗法演算結果を得るように切り替えを行う。
【００４７】
ＬＵＴ選択スイッチ１０７において、書込制御回路１０６からの入力１０７ｂ（乗法演算結果Ｍ（ｉ，Ｙｖ））は、１次元ＬＵＴ１０４への出力１０７ｄ又は次元ＬＵＴ１０５への出力１０７ｃのいずれかに接続される。１次元ＬＵＴ１０４からの入力１０７ｅと１次元ＬＵＴ１０５からの入力１０７ｆとは、いずれか一方が出力１０７ｇに接続されて加法回路１０９へ出力される。
【００４８】
図３に示されている例では、ＬＵＴ選択スイッチ１０７の入力１０７ｂは出力１０７ｃに接続されているため、書込制御回路１０６が出力する乗法演算結果Ｍ（ｉ，Ｙｖ）は、１次元ＬＵＴ１０５に書き込まれる。ＬＵＴ選択スイッチ１０７の入力１０７ｅは出力１０７ｇに接続されているため、１次元ＬＵＴ１０４が出力する乗法演算結果が加法回路１０９へ出力される。
【００４９】
インターリーブ制御回路１０８は、書込制御回路１０６が書込信号１０６ａを出力すると、次のｈ列演算結果入力Ｚｉｎ（ｈ）１３１に対するデータ列（フレーム）の先頭で１次元ＬＵＴ１０４及び１次元ＬＵＴ１０５の選択を切り替えて反転させる制御信号１０８ａを生成する。インターリーブ制御回路１０８は、生成した制御信号１０８ａを、ＬＵＴ選択スイッチ１０７の切替信号１０７ａとしてＬＵＴ選択スイッチ１０７に出力する。
【００５０】
加法回路１０９には、ｈ列演算結果入力Ｚｉｎ（ｈ）１３１と、ＬＵＴ選択スイッチ１０７の出力１０７ｇとが入力される。加法回路１０９は、ｈ列演算結果入力Ｚｉｎ（ｈ）１３１と出力１０７ｇとの加法演算結果を、ｈ列演算結果出力Ｚｏｕｔ（ｈ）１３２として出力する。
【００５１】
符号化及び復号化における行列演算は多くの場合、データ列（フレーム）単位で行われ、１つのデータ列に対して行列（係数）は固定である。例えば符号化に関しては、符号長や冗長度などのパラメータが変更されない限り、同じ符号化行列を用いる。消失訂正の復号化の場合、符号長や冗長度などのパラメータの変更の他、データ列（フレーム）単位の消失状況に応じて復号化行列を変更する。しかし、いずれの場合においても１つのデータ列（フレーム）に対しては同一の行列（係数）が用いられる。符号化及び復号化における行列演算を行う行列演算回路において、ｍ行ｎ列の格子点上に配置される積和演算回路では、１つのデータ列ごとに行う演算で係数が変わらないため、乗法などの２項演算における一方の入力を定数と見なすことができる。このような場合、２項演算における他方の入力が取り得る範囲の値に対する２項演算結果しか必要としないため、本実施形態のように一次元のＬＵＴで構成することができる。
【００５２】
図４は、第３の実施形態における１次元ＬＵＴ加算回路１０１の動作を示すタイミングチャートである。同図において、横軸は時間を示し、乗法演算結果Ｍ（ｉ，Ｙｖ）を含むＬＵＴ更新情報入力１３３、書込信号１０６ａ、出力１０７ｄ、１次元ＬＵＴ１０４におけるＬＵＴ、出力１０７ｃ、１次元ＬＵＴ１０５におけるＬＵＴ、入力Ｘｈ１３０、制御信号１０８ａ、出力１０７ｇ、ｈ行演算結果入力Ｚｉｎ（ｈ）及びｈ行演算結果出力Ｚｏｕｔ（ｈ）１３２の信号変化が示されている。
【００５３】
ＬＵＴ更新情報入力１３３は、次のフレームにおいて用いられる係数Ｙｖに対応する乗法演算結果Ｍ（ｉ，Ｙｖ）であって１次元ＬＵＴ１０４と１次元ＬＵＴ１０５とのうちのいずれかに書き込まれる乗法演算結果Ｍ（ｉ，Ｙｖ）を含む。書込制御回路１０６は、ＬＵＴ更新情報入力１３３から１次元ＬＵＴ加算回路１０１において必要な情報を検出する。検出された情報は、ＬＵＴ選択スイッチ１０７及びインターリーブ制御回路１０８によって選択された、１次元ＬＵＴ１０４及び１次元ＬＵＴ１０５のうち一方の１次元ＬＵＴに書き込まれる。現在のフレームの終端と次のフレームの先頭との間で、インターリーブ制御回路１０８は、乗法演算結果を読み出す１次元ＬＵＴと、ＬＵＴを更新する１次元ＬＵＴとを切り替える。新しいフレーム（新しいデータ列）における入力Ｘｈ１３０に対する読み出し側ＬＵＴの出力と、前列の演算結果出力Ｚｏｕｔ（ｈ−１）１３２である入力Ｚｉｎ（ｈ）１３１との加法演算結果を演算結果出力Ｚｏｕｔ（ｈ）１３２として後列の１次元ＬＵＴ加算回路１０１に送出する。最終的に１列目の演算結果出力Ｚｏｕｔ（１）１３２が行列演算結果Ｚ１２２として得られる。
【００５４】
図４に示すタイミングチャートにおいて、フレーム＃１（ｆｒａｍｅ＃１）の入力Ｘｈ１３０が入力されている期間では、１次元ＬＵＴ１０４に記憶させる乗法演算結果Ｍ（ｉ，Ｙｖ）を含むＬＵＴ更新情報入力１３３が出力１０７ｄとして出力される。この期間において、１次元ＬＵＴ１０４のＬＵＴが更新される。この期間では、１次元ＬＵＴ１０５から読み出される乗法演算結果が用いられて行列演算が行われる。
【００５５】
フレーム＃１とフレーム＃２との間の期間において、インターリーブ制御回路１０８が制御信号１０８ａの出力レベルを変更することにより、乗法演算結果を読み出す１次元ＬＵＴが１次元ＬＵＴ１０４に切り替えられるとともに、ＬＵＴ更新情報入力１３３でＬＵＴを更新する１次元ＬＵＴが１次元ＬＵＴ１０５に切り替えられる。
【００５６】
フレーム＃２の入力Ｘｈ１３０が入力されている期間では、１次元ＬＵＴ１０５に記憶させる乗法演算結果Ｍ（ｉ，Ｙｖ）を含むＬＵＴ更新情報入力１３３が出力１０７ｃとして出力される。この期間において、１次元ＬＵＴ１０５のＬＵＴが更新される。この期間では、フレーム＃１の入力Ｘｈ１３０が入力されている期間においてＬＵＴを更新した１次元ＬＵＴ１０４から読み出される乗法演算結果が用いられて行列演算が行われる。
【００５７】
フレーム＃２とフレーム＃３との間の期間において、インターリーブ制御回路１０８が制御信号１０８ａの出力レベルを変更することにより、乗法演算結果を読み出す１次元ＬＵＴが１次元ＬＵＴ１０５に切り替えられるとともに、ＬＵＴ更新情報入力１３３でＬＵＴを更新する１次元ＬＵＴが１次元ＬＵＴ１０４に切り替えられる。
【００５８】
フレーム＃３の入力Ｘｈ１３０が入力されている期間では、１次元ＬＵＴ１０４に記憶させる乗法演算結果Ｍ（ｉ，Ｙｖ）を含むＬＵＴ更新情報入力１３３が出力１０７ｄとして出力される。この期間において、１次元ＬＵＴ１０４のＬＵＴが更新される。この期間では、フレーム＃２の入力Ｘｈ１３０が入力されている期間においてＬＵＴを更新した１次元ＬＵＴ１０５から読み出される乗法演算結果が用いられて行列演算が行われる。
【００５９】
本実施形態における行列演算回路の各１次元ＬＵＴ加算回路１０１が、上述のように動作することにより、一つのデータ列（フレーム）ごとに用いる係数を示す行列（符号化行列や復号化行列）に変更が必要となる場合であっても、行列演算と行列の更新とを並行して行うことができる。
【００６０】
各演算における入力が８ビットであり８行８列の行列演算を実現する場合には、図７及び図８に示した構成の行列演算回路では各２次元ＬＵＴ１１１を構成するために６４ｋｂｙｔｅを必要とするので、６４個の２次元ＬＵＴ１１１には合計で４０９６ｋｂｙｔｅのメモリを必要とする。一方、第３の実施形態の行列演算回路では、６４個の１次元ＬＵＴ加算回路１０１それぞれの１次元ＬＵＴに２×２５６ｂｙｔｅ＝５１２ｂｙｔｅを必要とし、８個の２項演算テーブル１０２それぞれに６４ｋｂｙｔｅを必要とし、総計で５４４ｋｂｙｔｅのメモリで実現可能となる。
【００６１】
また、第２の実施形態における行列演算回路において、５１２ｂｙｔｅを必要とする６４個の１次元ＬＵＴ加算回路１０１と、６４ｋｂｙｔｅを必要とする１個の２項演算テーブル１０２とで構成する場合、総計９６ｋｂｙｔｅのメモリで実現可能となる。
【００６２】
なお、第３の実施形態における１次元ＬＵＴ加算回路１０１が、２つの１次元ＬＵＴ１０４及び１次元ＬＵＴ１０５を有する構成を説明したが、３つ以上の１次元ＬＵＴを有していてもよい。また、１次元ＬＵＴ１０４及び１次元ＬＵＴ１０５へ乗法演算結果Ｍ（ｉ，Ｙｖ）を書き込むタイミングは、ＬＵＴ更新情報入力１３３に依らずともよく、データ列（フレーム）の入力タイミングに同期した上位の装置が出力する信号に基づいて決定されてもよい。
【００６３】
（第４の実施形態）
第４の実施形態における行列演算回路は、行列演算に用いる行列の種類が比較的少数の場合に適用できる構成を有している。図５は、第４の実施形態における行列演算回路の構成を示す図である。第４の実施形態における行列演算回路は、第１から第３の実施形態における行列演算回路と同様に、ｍ行ｎ列の行列演算を行う回路である。行列演算回路は、入力Ｘ１２０（＝｛Ｘ１，Ｘ２，…，Ｘｎ｝）と、係数ベクトルＹ１２３（＝｛Ｙ１，Ｙ２，…，Ｙｍ｝）とに対する行列演算を行う。
【００６４】
第４の実施形態における行列演算回路は、１次元ＬＵＴ加算回路１０１に代えて１次元ＬＵＴ加算回路２０１を備え、ＬＵＴページ選択信号２３３が各１次元ＬＵＴ加算回路２０１に入力されている点が、第２の実施形態における行列演算回路（図２）と異なる。図５に示す行列演算回路は、ｍ行ｎ列の格子点上それぞれに配置された１次元ＬＵＴ加算回路２０１、２項演算テーブル１０２及び選択回路１０３を有している。本実施形態における１次元ＬＵＴ加算回路２０１は、１次元ＬＵＴのページ選択に対応した１次元ＬＵＴ加算回路である。ここで、ＬＵＴページ選択信号は、データ列（フレーム）の入力タイミングに同期した上位の装置が出力する信号であり、行列演算回路において演算対象となる複数の行列のうち、いずれの行列に対する演算を行うかを指示する信号である。
【００６５】
図６は、第４の実施形態における１次元ＬＵＴ加算回路２０１の構成を示す図である。図６に示す１次元ＬＵＴ加算回路２０１は、ｖ行目ｈ列目に配置された１次元ＬＵＴ加算回路２０１を示している。同図に示すように、１次元ＬＵＴ加算回路２０１は、ｋ個の１次元ＬＵＴ２０４を含む１次元ＬＵＴアレイ、書込制御回路２０６、ＬＵＴ選択回路２０７及び加法回路１０９を有している。第４の実施形態における１次元ＬＵＴ加算回路２０１は、行列演算に用いる行列の種類に相当する数の１次元ＬＵＴ２０４を有する。ここで、行列の種類とは、データ列に対する行列演算において用いる可能性がある行列であって、行列の要素の値が異なる行列の数のことである。
【００６６】
１次元ＬＵＴアレイにおける各１次元ＬＵＴ２０４は、第３の実施形態における１次元ＬＵＴ１０４及び１次元ＬＵＴ１０５と同様に、入力Ｘｈ１３０が取り得る値ごとに当該値と係数ａｖｈとの乗法演算結果Ｍ（ｉ，Ｙｖ）を対応付けて記憶する。書込制御回路２０６は、２項演算テーブル１０２から入力される乗法演算結果（２項演算結果）を、１次元ＬＵＴアレイを構成する各１次元ＬＵＴ２０４に記憶させる。
【００６７】
ＬＵＴ選択回路２０７は、複数の１次元ＬＵＴ２０４それぞれから出力される、入力Ｘｈ１３０に対応する乗法演算結果のうち、入力されるＬＵＴページ選択信号２３３に応じて一つの乗法演算結果を選択する。ＬＵＴ選択回路２０７は、選択した乗法演算結果を加法回路１０９に出力する。
【００６８】
第４の実施形態における行列演算回路では、１次元ＬＵＴ加算回路２０１それぞれにおいて複数の１次元ＬＵＴ２０４からいずれか一つをＬＵＴページ選択信号２３３に応じて選択するので、ＬＵＴページ選択信号２３３を変更することにより行列演算の対象になる行列を容易に切り替えることができる。また、各１次元ＬＵＴ加算回路２０１には、ｋ個の１次元ＬＵＴ２０４を設けているので、フレーム（データ列）に対する行列演算を行っている最中に１次元ＬＵＴ２０４に記憶させる２項演算結果を更新する必要が無くなるため、フレーム長が短い場合における行列演算への適用が可能になる。また、１次元ＬＵＴ２０４における２項演算結果の更新に要する時間に対する制限が緩和されるため、２項演算テーブル１０２の個数を減らすことが容易になる。
【００６９】
上述のように、第４の実施形態における行列演算回路によれば、行列演算に用いる各行列に対応する２項演算結果を１次元ＬＵＴ２０４それぞれに予め記憶させておくことにより、行列演算に用いる行列をフレーム（データ列）ごとに切り替えるための１次元ＬＵＴ２０４の更新に要する時間を削減することができ、短いフレーム長の符号化や復号化に用いることができるとともに、２項演算テーブル１０２の個数を減らして回路規模を削減することができる。
【００７０】
（第５の実施形態）
第５の実施形態では、ＬＵＴ更新情報入力１３３の生成について説明する。表１及び表２は、ＬＵＴ更新情報入力１３３を説明するための表である。表１は、行列演算回路において用いる２項演算の一例としての整数乗算を示す２項演算のテーブルである。なお、２項演算のテーブルで表す演算は、整数乗算以外であってもよく、ガロア体の乗算等の任意の演算であってもよい。表１に示す２項演算のテーブルでは、入力Ｘｈ１３０が取り得る値は「０」、「１」、「２」及び「３」と定められ、係数Ｙの値として「０」、「１」、「２」及び「３」が定められていることになる。２項演算テーブル１０２には、表１に示すようなテーブルが予め設けられている。
【００７１】
【表１】
2015210725.tif 000003
【００７２】
表２は、ｖ行の１次元ＬＵＴ加算回路１０１に対するＬＵＴ更新情報入力１３３の一例を示すテーブルである。ここでは、４列分の１次元ＬＵＴ加算回路１０１が行列演算回路において配置されているものとしている。表２には、フレーム＃（ｔ−１）からフレーム＃（ｔ＋１）までの３フレーム分におけるｖ行の１次元ＬＵＴ加算回路１０１に対する係数Ｙｖと２項演算結果Ｍ（ｉ，Ｙｖ）と２項演算位置情報とが示されている。ＬＵＴ更新情報入力１３３は、２項演算結果（乗法演算結果Ｍ（ｉ，Ｙｖ））と２項演算位置情報とを含む。
【００７３】
【表２】
2015210725.tif 000004
【００７４】
フレーム間で係数が変化しない場合には１次元ＬＵＴ加算回路１０１において１次元ＬＵＴ１０４又は１次元ＬＵＴ１０５を更新する必要がない。そこで、ＬＵＴ更新情報入力１３３には、更新する必要がある１次元ＬＵＴ加算回路１０１を示す２項演算位置情報が含まれている。
【００７５】
表２において、フレーム＃（ｔ−１）における係数Ｙｖ［ｈ］（＝ａｖｈ）は、１列目の１次元ＬＵＴ加算回路１０１に対して「０」、２列目の１次元ＬＵＴ加算回路１０１に対して「１」、３列目の１次元ＬＵＴ加算回路１０１に対して「２」、４列目の１次元ＬＵＴ加算回路１０１に対して「３」が割り当てられている。表２では、この係数Ｙｖの割り当てが｛０，１，２，３｝として表記されている。
【００７６】
フレーム＃ｔにおける係数Ｙｖは、１列目から４列目の１次元ＬＵＴ加算回路１０１に対して｛０，２，１，１｝が割り当てられている。フレーム＃ｔでは、１列目以外の２列目から４列目の１次元ＬＵＴ加算回路１０１に対して割り当てられる係数Ｙｖに変更が生じているので、各１次元ＬＵＴ加算回路１０１における１次元ＬＵＴ１０４又は１次元ＬＵＴ１０５を更新する必要がある。そのため、フレーム＃ｔにおける係数Ｙｖの変更に応じた２項演算結果Ｍ（ｉ，Ｙｖ）が２項演算テーブル１０２において生成される。
【００７７】
具体的には、２項演算テーブル１０２は、２項演算のテーブルにおける係数Ｙ「２」の１列｛０，２，４，６｝を、２列目の１次元ＬＵＴ加算回路１０１のＬＵＴを更新する２項演算結果Ｍ（ｉ，Ｙｖ）として出力する。また、２項演算テーブル１０２は、テーブルにおける係数Ｙ「１」の１列｛０，１，２，３｝を、３列目及び４列目の１次元ＬＵＴ加算回路１０１のＬＵＴを更新する２項演算結果Ｍ（ｉ，Ｙｖ）として出力する。
【００７８】
すなわち、２項演算テーブル１０２は、フレーム＃ｔに対する行列演算が行われる前に、２項演算結果Ｍ（ｉ，Ｙｖ）｛｛０，２，４，６｝，｛０，１，２，３｝，｛０，１，２，３｝｝と、２項演算位置情報｛２，３，４｝とを含むＬＵＴ更新情報入力１３３をｖ行の各１次元ＬＵＴ加算回路１０１に対して出力する。
【００７９】
フレーム＃（ｔ＋１）における係数Ｙｖは、１列目から４列目の１次元ＬＵＴ加算回路１０１に対して｛２，２，２，２｝が割り当てられている。フレーム＃（ｔ＋１）では、１列目、３列目及び４列目の１次元ＬＵＴ加算回路１０１に対する係数Ｙｖに変更が生じている。フレーム＃（ｔ＋１）に対する行列演算が行われる前に２項演算テーブル１０２が出力するＬＵＴ更新情報入力１３３には、２項演算位置情報は｛１，３，４｝と、２項演算結果Ｍ（ｉ，Ｙｖ）｛｛０，２，４，６｝，｛０，２，４，６｝，｛０，２，４，６｝｝とが含まれる。
【００８０】
上述のようなＬＵＴ更新情報入力１３３を生成するために、２項演算テーブル１０２は、例えば各列の１次元ＬＵＴ加算回路１０１の１次元ＬＵＴが記憶している２項演算結果Ｍ（ｉ，Ｙｖ）の係数Ｙｖ［ｈ］と、次のフレームにおいて各１次元ＬＵＴ加算回路１０１に割り当てる係数Ｙｖ［ｈ］とを比較する。２項演算テーブル１０２は、二つの係数Ｙｖ［ｈ］が一致しない場合は、当該１次元ＬＵＴ加算回路１０１を更新の対象として当該１次元ＬＵＴ加算回路１０１の列を示す値を、２項演算位置情報に加える。
【００８１】
また、２項演算テーブル１０２は、次のフレームにおいて記憶させる係数Ｙｖ［ｈ］の列の要素をテーブルから読み出して、２項演算結果Ｍ（ｉ，Ｙｖ）に加える。行ごとに配置された２項演算テーブル１０２が、それぞれの行における各１次元ＬＵＴ加算回路１０１に割り当てる係数Ｙｖ［ｈ］の比較を行うことにより、ＬＵＴ更新情報入力１３３の２項演算位置情報及び２項演算結果Ｍ（ｉ，Ｙｖ）が生成される。
【００８２】
なお、図３に示したように、１次元ＬＵＴ加算回路１０１において２つの１次元ＬＵＴ１０４及び１次元ＬＵＴ１０５が交互に用いられている場合には、２項演算テーブル１０２は、１次元ＬＵＴ加算回路１０１に割り当てた係数Ｙｖ［ｈ］の比較をする際に、１次元ＬＵＴの切り替えに合わせて比較対象の係数Ｙｖ［ｈ］を切り替える。また、ＬＵＴ更新情報入力１３３において、２項演算位置情報における列を示す値の並びと、２項演算結果Ｍ（ｉ，Ｙｖ）における各列の１次元ＬＵＴ加算回路１０１に記憶させる値の集合の並びとは、対応している。
【００８３】
また、１次元ＬＵＴ加算回路１０１における書込制御回路１０６は、２項演算テーブル１０２から入力されるＬＵＴ更新情報入力１３３の２項演算位置情報に、自回路が配置されている列を示す値が含まれているか否かを判定する。書込制御回路１０６は、自回路の列を示す値が２項演算位置情報に含まれている場合、ＬＵＴ更新情報入力１３３に含まれる２項演算結果Ｍ（ｉ，Ｙｖ）のうち、自身の列に対応する２項演算結果Ｍ（ｉ，Ｙｖ）を検出し、検出した２項演算結果Ｍ（ｉ，Ｙｖ）をＬＵＴ選択スイッチ１０７に出力する。
【００８４】
上述のように、２項演算テーブル１０２がＬＵＴ更新情報入力１３３を生成して、係数Ｙｖに変更が生じた列の１次元ＬＵＴ加算回路１０１に対する２項演算結果Ｍ（ｉ，Ｙｖ）に限定してＬＵＴ更新情報入力１３３に含めることにより、ＬＵＴ更新情報入力１３３の情報量を減らすことが可能になる。
【００８５】
なお、第２の実施形態における行列演算回路のように、２項演算テーブル１０２が複数の行の１次元ＬＵＴ加算回路１０１に対するＬＵＴ更新情報入力１３３を生成して出力する場合には、２項演算位置情報には更新の対象となる行を示す値が含まれることになる。
【００８６】
（第６の実施形態）
第６の実施形態では、第５の実施形態におけるＬＵＴ更新情報入力１３３と異なるＬＵＴ更新情報入力１３３について説明する。第６の実施形態におけるＬＵＴ更新情報入力１３３は、変更が生じた係数Ｙｖのうち同じ値が割り当てられる列（１次元ＬＵＴ加算回路１０１）が複数存在する場合、２項演算結果Ｍ（ｉ，Ｙｖ）の出力が重複することを避けるために、係数Ｙｖに対する列の集合を２項演算位置情報とする構成が第５の実施形態と異なる。表３は、第６の実施形態におけるＬＵＴ更新情報入力１３３の一例を示すテーブルである。表３に示される各列の１次元ＬＵＴ加算回路１０１に対する係数Ｙｖの割り当ては、表２に示される係数Ｙｖの割り当てと同じである。
【００８７】
【表３】
2015210725.tif 000005
【００８８】
表３のフレーム＃ｔにおいて、割り当てに変更が生じた係数Ｙｖには「２」と「１」との２種類であり、この２つの係数Ｙｖに対応する表１の列｛０，２，４，６｝と｛０，１，２，３｝とが２項演算結果Ｍ（ｉ，Ｙｖ）としてＬＵＴ更新情報入力１３３に含まれる。また、係数Ｙｖ「２」が割り当てられるのは２列目の１次元ＬＵＴ加算回路１０１であり、係数Ｙｖ「１」が割り当てられるのは３列目と４列目との１次元ＬＵＴ加算回路１０１であるので、｛｛２｝、｛３，４｝｝が２項演算位置情報としてＬＵＴ更新情報入力１３３に含まれる。すなわち、変更後の係数Ｙｖが「２」の１次元ＬＵＴ加算回路１０１のグループと、変更後の係数Ｙｖが「１」の１次元ＬＵＴ加算回路１０１のグループとに分けた２項演算位置情報｛｛２｝、｛３，４｝｝が生成されることになる。また、各グループに向けた２項演算結果Ｍ（ｉ，Ｙｖ）｛｛０，２，４，６｝、｛０，１，２，３｝｝が生成されることになる。
【００８９】
また、フレーム＃（ｔ＋１）において、割り当てに変更が生じた係数Ｙｖには「２」の１種類であり、この係数Ｙｖ「２」に対応する表１の列｛０，２，４，６｝が２項演算結果Ｍ（ｉ，Ｙｖ）としてＬＵＴ更新情報入力１３３に含まれる。また、係数Ｙｖ「２」が割り当てられるのは、１列目、３列目及び４列目の１次元ＬＵＴ加算回路１０１であるので、｛｛１，３，４｝｝が２項演算位置情報としてＬＵＴ更新情報入力１３３に含まれる。このとき、ＬＵＴ更新情報入力１３３に含まれる２項演算結果Ｍ（ｉ，Ｙｖ）は、｛｛０，２，４，６｝｝になる。
【００９０】
このように、２項演算テーブル１０２が、ＬＵＴ更新情報入力１３３に含める情報を、割り当てられる係数Ｙｖが変更した列に対する２項演算結果Ｍ（ｉ，Ｙｖ）に限定し、さらに、重複する２項演算結果Ｍ（ｉ，Ｙｖ）を同じ係数Ｙｖでまとめてグループ化して２項演算結果Ｍ（ｉ，Ｙｖ）を出力することにより、ＬＵＴ更新情報入力１３３の情報量をさらに削減することが可能になる。
【００９１】
なお、第２の実施形態における行列演算回路のように、２項演算テーブル１０２が複数の行の１次元ＬＵＴ加算回路１０１に対するＬＵＴ更新情報入力１３３を生成して出力する場合には、２項演算位置情報には更新の対象となる行を示す値が含まれることになる。
【００９２】
図７及び図８において示した行列演算回路においては、演算対象の行列のサイズ（ｍ行ｎ列）に応じて２次元ＬＵＴ１１１を行列状に配置していたため、比較的小さな入力サイズ（ビット数）にしか適用できなかった。これに対して、各実施形態において説明した行列演算回路は、フレーム単位（一つのデータ列）に対する行列の各要素に変更がなされないことを前提にして、演算対象の行列のサイズ（ｍ行ｎ列）に応じて１次元ＬＵＴ加算回路１０１を行列状に配置して、各行又は各列の１次元ＬＵＴ加算回路１０１で２項演算テーブル１０２を共有することで回路規模の削減を図ることができる。各１次元ＬＵＴ加算回路１０１におけるＬＵＴのサイズが小さくできるので、大きな入力サイズに対する２項演算（乗法演算）を行ったとしても回路規模の増加を抑えることができる。また、２項演算（乗法演算）をＬＵＴで実装するため、複雑な論理回路を用いる必要がないため行列演算回路における演算遅延を抑えることができる。
【００９３】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【産業上の利用可能性】
【００９４】
フレーム（ブロック）単位で行列演算を行う回路において回路規模の削減が不可欠な用途にも適用できる。
【符号の説明】
【００９５】
１０１，２０１…１次元ＬＵＴ加算回路
１０２…２項演算テーブル
１０３…選択回路
１０４，１０５，２０４…１次元ＬＵＴ
１０６，２０６…書込制御回路
１０６ａ，２０６ａ…書込信号
１０７…ＬＵＴ選択スイッチ
１０７ａ…切替信号
１０７ｂ，１０７ｅ，１０７ｆ…入力
１０７ｃ，１０７ｄ，１０７ｇ…出力
１０８…インターリーブ制御回路
１０８ａ…制御信号
１０９…加法回路
１１０…積和演算回路
１１１…２次元ＬＵＴ
１１１ａ…乗法演算結果
１２０…入力Ｘ
１２２…出力Ｚ
１２３…係数ベクトルＹ
１３０…入力Ｘｈ
１３１…ｈ列演算結果入力Ｚｉｎ（ｈ）
１３２…ｈ行演算結果出力Ｚｏｕｔ（ｈ）
１３３…ＬＵＴ更新情報入力
２０７…ＬＵＴ選択回路
２３３…ＬＵＴページ選択信号
【図１】
2015210725.tif 000006
【図２】
2015210725.tif 000007
【図３】
2015210725.tif 000008
【図４】
2015210725.tif 000009
【図５】
2015210725.tif 000010
【図６】
2015210725.tif 000011
【図７】
2015210725.tif 000012
【図８】
2015210725.tif 000013