"要素数kの情報ベクトルXから式A1で表わされるパリティ生成式にしたがって2を法とする演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y≡U1U2Um1UmLmLm1L2L1AXA1ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT≡0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、行列Lii=1~mは、前記行列BをLU分解した下三角行列Lの基本下三角行列であって、第i列目が前記下三角行列Lの第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列Uii=1~mは、前記行列BをLU分解した上三角行列Uの基本上三角行列であって、第i行目が前記上三角行列Uの第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、前記符号化装置は、前記パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、前記パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、前記パリティベクトルYを算出するために、前記パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部とを備え、前記行列積計算部は、前記情報ベクトルX、前記行列記憶部内の行列を表わすデータ、または前記中間結果記憶部内の中間結果を表わすデータを用いて、前記パリティ生成式に含まれる各行列乗算を実行して、前記パリティ生成式に含まれる前記複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして前記中間結果記憶部内に記憶させ、前記パリティ生成式に含まれる前記複数回の行列乗算が終了したら、前記パリティ生成式に含まれる前記複数回の行列乗算の終了後に得られるベクトルをパリティベクトルYとして出力する、符号化装置。しかしながら、非特許文献2および非特許文献3のエンコード手法では、方程式の解法に後退代入などが用いられているため、計算量が多くなる。それゆえに、本発明の目的は、従来よりも少ない計算量でパリティを計算することができる符号化装置および符号化プログラムを提供することである。本発明のある局面に係る符号化装置は、要素数kの情報ベクトルXから式A1で表わされるパリティ生成式にしたがって2を法とする演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y≡U1U2Um1UmLmLm1L2L1AXA1ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT≡0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、行列Lii=1~mは、行列BをLU分解した下三角行列Lの基本下三角行列であって、第i列目が下三角行列Lの第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列Uii=1~mは、行列BをLU分解した上三角行列Uの基本上三角行列であって、第i行目が上三角行列Uの第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化装置は、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部とを備え、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルをパリティベクトルYとして出力する。好ましくは、符号化装置は、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化装置であって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、符号化装置は、さらに、パリティ検査行列Hを行列Aと行列Bとに分解して、行列Aを表わすデータを行列記憶部に記憶させる検査行列分解部と、行列Bを下三角行列Lと上三角行列Uの積にLU分解して、下三角行列Lを表わすデータおよび上三角行列Uを表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列Uおよび下三角行列Lを表わすデータを読み出して、上三角行列Uをm個の基本上三角行列Uii=1~mの積に分解し、下三角行列Lをm個の基本下三角行列Lii=1~mの積に分解し、分解された行列Uii=1~mおよび行列Lii=1~mを表わすデータを行列記憶部に記憶させる基本行列分解部とを備える。本発明の別の局面に係る符号化装置は、要素数kの情報ベクトルXから式A2で表わされるパリティ生成式にしたがって実数演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y=-U11U21Um11Um1Lm1Lm11L21L11AXA2ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT=0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、行列Li1i=1~mは行列Liの逆行列であり、行列Liは行列BをLU分解した下三角行列Lの基本下三角行列であって、第i列目が下三角行列Lの第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列Ui1i=1~mは行列Uiの逆行列であり、行列Uiは、行列BをLU分解した上三角行列Uの基本上三角行列であって、第i行目が上三角行列Uの第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化装置は、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部と、行列積計算部から出力されるベクトルの符号を反転してパリティベクトルYとして出力する符号反転部とを備え、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルを符号反転部に出力する。好ましくは、符号化装置は、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化装置であって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、符号化装置は、さらに、パリティ検査行列Hを行列Aと行列Bとに分解して、行列Aを表わすデータを行列記憶部に記憶させる検査行列分解部と、行列Bを下三角行列Lと上三角行列Uの積にLU分解して、下三角行列Lを表わすデータおよび上三角行列Uを表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列Uおよび下三角行列Lを表わすデータを読み出して、上三角行列Uをm個の基本上三角行列Uii=1~mの積に分解し、下三角行列Lをm個の基本下三角行列Lii=1~mの積に分解し、分解された行列Uii=1~mおよび行列Lii=1~mを表わすデータを中間結果記憶部に記憶させる基本行列分解部と、中間結果記憶部から行列Uii=1~mおよび行列Lii=1~mを表わすデータを読み出して、行列Uii=1~mおよび行列Lii=1~mの非対角項の要素の符号を反転することによって、逆行列Ui1i=1~mおよび逆行列Li1i=1~mを算出し、逆行列Ui1i=1~mおよび逆行列Li1i=1~mを表わすデータを行列記憶部に記憶させる逆行列計算部とを備える。本発明の別の局面に係る符号化装置は、要素数kの情報ベクトルXから、u≧1かつv≧1のときには式A3-1、u≧1かつv=0のときには式A3-2、u=0かつv≧1のときには式A3-3で表わされるパリティ生成式にしたがって2を法とする演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXA3-1Y≡U′1U′2U′m1U′mL′mL′m1L′2L′1AXA3-2Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXA3-3ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT≡0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、u≧1かつv≧1の場合には、行列B′は、行列Bに対して、u回の行の入れ替え、およびv回の列の入れ替えを行なったものであり、行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものであり、行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものであり、u≧1かつv=0の場合には、行列B′は、行列Bに対して、u回の行の入れ替えを行なったものであり、行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものであり、u=0かつv≧1の場合には、行列B′は、行列Bに対して、v回の列の入れ替えを行なったものであり、行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものであり、行列L′ii=1~mは、行列B′をLU分解した下三角行列L′の基本下三角行列であって、第i列目が下三角行列L′の第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列U′ii=1~mは、行列B′をLU分解した上三角行列U′の基本上三角行列であって、第i行目が上三角行列U′の第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化装置は、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部とを備え、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルをパリティベクトルYとして出力する。好ましくは、符号化装置は、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化装置であって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、符号化装置は、さらに、パリティ検査行列Hを行列Aと行列Bに分解して、u=0かつv≧1のときには、行列Aを表わすデータを行列記憶部に記憶させる検査行列分解部と、u≧1かつv≧1の場合、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えおよびv回の列の入れ替えを行なった行列B′を生成し、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して行列記憶部に記憶させ、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して行列記憶部に記憶させ、u≧1かつv=0の場合、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えを行なった行列B′を生成し、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して行列記憶部に記憶させ、u=0かつv≧1の場合、行列Bのオーダリングを行ない、行列Bに対してv回の列の入れ替えを行なった行列B′を生成し、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して行列記憶部に記憶させるオーダリング部と、行列B′を下三角行列L′と上三角行列U′の積にLU分解して、下三角行列L′を表わすデータおよび上三角行列U′を表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列U′および下三角行列L′を表わすデータを読み出して、上三角行列U′をm個の基本上三角行列U′ii=1~mの積に分解し、下三角行列L′をm個の基本下三角行列L′ii=1~mの積に分解し、分解された行列U′ii=1~mおよび行列′Lii=1~mを表わすデータを行列記憶部に記憶させる基本行列分解部とを備える。本発明のある局面に係る符号化装置は、要素数kの情報ベクトルXから、u≧1かつv≧1のときには式A4-1、u≧1かつv=0のときには式A4-2、u=0かつv≧1のときには式A4-3で表わされるパリティ生成式にしたがって2を法とする演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXA4-1Y=-U′11U′21U′m11U′m1L′m1L′m11L′21L′11AXA4-2Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXA4-3ただし、パリティ検査行列Hは、HX,YT=0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、u≧1かつv≧1の場合には、行列B′は、行列Bに対して、u回の行の入れ替え、およびv回の列の入れ替えを行なったものであり、行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものであり、行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものであり、u≧1かつv=0の場合には、行列B′は、行列Bに対して、u回の行の入れ替えを行なったものであり、行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものであり、u=0かつv≧1の場合には、行列B′は、行列Bに対して、v回の列の入れ替えを行なったものであり、行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものであり、行列L′i1i=1~mは行列L′iの逆行列であり、行列L′iは、行列B′をLU分解した下三角行列L′の基本下三角行列であって、第i列目が下三角行列L′の第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列U′i1i=1~mは行列U′iの逆行列であり、行列U′iは、行列B′をLU分解した上三角行列U′の基本上三角行列であって、第i行目が上三角行列U′の第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化装置は、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部と、行列積計算部から出力されるベクトルの符号を反転してパリティベクトルYとして出力する符号反転部とを備え、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルを符号反転部に出力する含まれる複数回の行列乗算の終了後に得られるベクトルを符号反転部に出力する。好ましくは、符号化装置は、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化装置であって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、符号化装置は、さらに、パリティ検査行列Hを行列Aと行列Bに分解して、u=0かつv≧1のときには、行列Aを表わすデータを行列記憶部に記憶させる検査行列分解部と、u≧1かつv≧1の場合、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えおよびv回の列の入れ替えを行なった行列B′を生成し、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して行列記憶部に記憶させ、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して行列記憶部に記憶させ、u≧1かつv=0の場合、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えを行なった行列B′を生成し、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して行列記憶部に記憶させ、u=0かつv≧1の場合、行列Bのオーダリングを行ない、行列Bに対してv回の列の入れ替えを行なった行列B′を生成し、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して行列記憶部に記憶させるオーダリング部と、行列B′を下三角行列L′と上三角行列U′の積にLU分解して、下三角行列L′を表わすデータおよび上三角行列U′を表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列U′および下三角行列L′を表わすデータを読み出して、上三角行列U′をm個の基本上三角行列U′ii=1~mの積に分解し、下三角行列L′をm個の基本下三角行列L′ii=1~mの積に分解し、分解された行列U′ii=1~mおよび行列′Lii=1~mを表わすデータを中間結果記憶部に記憶させる基本行列分解部と、中間結果記憶部から行列U′ii=1~mおよび行列L′ii=1~mを表わすデータを読み出して、行列U′ii=1~mおよび行列L′ii=1~mの非対角項の要素の符号を反転することによって、逆行列U′i1i=1~mおよび逆行列L′i1i=1~mを算出し、逆行列U′i1i=1~mおよび逆行列L′i1i=1~mを表わすデータを行列記憶部に記憶させる逆行列計算部とを備える。本発明の別の局面に係る符号化装置は、要素数kの情報ベクトルXから、式A5に含まれる少なくとも1セットの隣接する2個以上の行列が、2個以上の行列の乗算結果である行列Cで置換されたパリティ生成式にしたがって2を法とする演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y≡U1U2Um1UmLmLm1L2L1AXA5ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT≡0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、行列Lii=1~mは、行列BをLU分解した下三角行列Lの基本下三角行列であって、第i列目が下三角行列Lの第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列Uii=1~mは、行列BをLU分解した上三角行列Uの基本上三角行列であって、第i行目が上三角行列Uの第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化装置は、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部とを備え、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルをパリティベクトルYとして出力する。好ましくは、パリティ生成式に含まれるすべての行列の非対角項の非零要素数の和は、式A5に含まれるすべての行列の非対角項の非零要素数の和以下である。好ましくは、符号化装置は、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化装置であって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、行列積計算部は、さらに、式A5に含まれる隣接する2個以上の行列の乗算を実行して、乗算結果である行列Cを表わすデータを出力し、符号化装置は、さらに、パリティ検査行列Hを行列Aと行列Bに分解して、行列Aを表わすデータを行列記憶部に記憶させる検査行列分解部と、行列Bを下三角行列Lと上三角行列Uの積にLU分解して、下三角行列Lを表わすデータおよび上三角行列Uを表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列Uおよび下三角行列Lを表わすデータを読み出して、上三角行列Uをm個の基本上三角行列Uii=1~mの積に分解し、下三角行列Lをm個の基本下三角行列Lii=1~mの積に分解し、分解された行列Uii=1~mおよび行列Lii=1~mを表わすデータを中間結果記憶部に記憶させる基本行列分解部と、乗算結果である行列Cの非零要素数と式A5に含まれる行列のうち隣接する2個以上の行列を除いた行列の非対角項の非零要素数の和が、式A5に含まれるすべての行列の非対角項の非零要素数の和以下である場合に、中間結果記憶部に記憶されている式A5に含まれる行列のうち隣接する2個以上の行列を除いた行列を表わすデータと、行列Cを表わすデータとを行列記憶部に記憶する行列乗算数削減部とを備える。本発明の別の局面に係る符号化装置は、要素数kの情報ベクトルXから、式A6に含まれる少なくとも1セットの隣接する2個以上の行列が、2個以上の行列の乗算結果である行列Cで置換されたパリティ生成式にしたがって実数演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y=-U11U21Um11Um1Lm1Lm11L21L11AXA6ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT=0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、行列Li1i=1~mは行列Liの逆行列であり、行列Liは行列BをLU分解した下三角行列Lの基本下三角行列であって、第i列目が下三角行列Lの第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列Ui1i=1~mは行列Uiの逆行列であり、行列Uiは、行列BをLU分解した上三角行列Uの基本上三角行列であって、第i行目が上三角行列Uの第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化装置は、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部と、行列積計算部から出力されるベクトルの符号を反転してパリティベクトルYとして出力する符号反転部とを備え、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルを符号反転部に出力する。好ましくは、パリティ生成式に含まれるすべての行列の非対角項の非零要素数の和は、式A6に含まれるすべての行列の非対角項の非零要素数の和以下である。好ましくは、符号化装置は、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化装置であって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、行列積計算部は、さらに、式A6に含まれる隣接する2個以上の行列の乗算を実行して、乗算結果である行列Cを表わすデータを出力し、符号化装置は、さらに、パリティ検査行列Hを行列Aと行列Bに分解して、行列Aを表わすデータを行列記憶部に記憶させる検査行列分解部と、行列Bを下三角行列Lと上三角行列Uの積にLU分解して、下三角行列Lを表わすデータおよび上三角行列Uを表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列Uおよび下三角行列Lを表わすデータを読み出して、上三角行列Uをm個の基本上三角行列Uii=1~mの積に分解し、下三角行列Lをm個の基本下三角行列Lii=1~mの積に分解し、分解された行列Uii=1~mおよび行列Lii=1~mを表わすデータを中間結果記憶部に記憶させる基本行列分解部と、中間結果記憶部から行列Uii=1~mおよび行列Lii=1~mを表わすデータを読み出して、行列Uii=1~mおよび行列Lii=1~mの非対角項の要素の符号を反転することによって、逆行列Ui1i=1~mおよび逆行列Li1i=1~mを算出し、逆行列Ui1i=1~mおよび逆行列Li1i=1~mを表わすデータを中間結果記憶部に記憶させる逆行列計算部と、乗算結果である行列Cの非零要素数と式A6に含まれる行列のうち隣接する2個以上の行列を除いた行列の非対角項の非零要素数の和が、式A6に含まれるすべての行列の非対角項の非零要素数の和以下である場合に、中間結果記憶部に記憶されている式A6に含まれる行列のうち隣接する2個以上の行列を除いた行列を表わすデータと、行列Cを表わすデータとを行列記憶部に記憶する行列乗算数削減部とを備える。本発明の別の局面に係る符号化装置は、要素数kの情報ベクトルXから、u≧1かつv≧1のときには式A7-1、u≧1かつv=0のときには式A7-2、u=0かつv≧1のときには式A7-3に含まれる少なくとも1セットの隣接する2個以上の行列が、2個以上の行列の乗算結果である行列Cで置換されたパリティ生成式にしたがって2を法とする演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXA7-1Y≡U′1U′2U′m1U′mL′mL′m1L′2L′1AXA7-2Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXA7-3ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT≡0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、u≧1かつv≧1の場合には、行列B′は、行列Bに対して、u回の行の入れ替え、およびv回の列の入れ替えを行なったものであり、行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものであり、行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものであり、u≧1かつv=0の場合には、行列B′は、行列Bに対して、u回の行の入れ替えを行なったものであり、行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものであり、u=0かつv≧1の場合には、行列B′は、行列Bに対して、v回の列の入れ替えを行なったものであり、行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものであり、行列L′ii=1~mは、行列B′をLU分解した下三角行列L′の基本下三角行列であって、第i列目が下三角行列L′の第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列U′ii=1~mは、行列B′をLU分解した上三角行列U′の基本上三角行列であって、第i行目が上三角行列U′の第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化装置は、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部とを備え、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルをパリティベクトルYとして出力する。好ましくは、パリティ生成式に含まれるすべての行列の非対角項の非零要素数の和は、式A7-1、A7-2、またはA7-3に含まれるすべての行列の非対角項の非零要素数の和以下である。好ましくは、符号化装置は、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化装置であって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、行列積計算部は、さらに、式A7-1、A7-2、またはA7-3に含まれる隣接する2個以上の行列の乗算を実行して、乗算結果である行列Cを表わすデータを出力し、符号化装置は、さらに、パリティ検査行列Hを行列Aと行列Bに分解して、行列Aおよび行列Bを表わすデータを中間結果記憶部に記憶させる検査行列分解部と、u≧1かつv≧1の場合、中間結果記憶部から行列Aおよび行列Bを表わすデータを読み出して、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えおよびv回の列の入れ替えを行なった行列B′を生成し、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して中間結果記憶部に記憶させ、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して中間結果記憶部に記憶させ、u≧1かつv=0の場合、中間結果記憶部から行列Aおよび行列Bを表わすデータを読み出して、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えを行なった行列B′を生成し、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して中間結果記憶部に記憶させ、u=0かつv≧1の場合、中間結果記憶部から行列Bを表わすデータを読み出して、行列Bのオーダリングを行ない、行列Bに対してv回の列の入れ替えを行なった行列B′を生成し、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して中間結果記憶部に記憶させるオーダリング部と、行列B′を下三角行列L′と上三角行列U′の積にLU分解して、下三角行列L′を表わすデータおよび上三角行列U′を表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列U′および下三角行列L′を表わすデータを読み出して、上三角行列U′をm個の基本上三角行列U′ii=1~mの積に分解し、下三角行列L′をm個の基本下三角行列L′ii=1~mの積に分解し、分解された行列U′ii=1~mおよび行列′Lii=1~mを表わすデータを中間結果記憶部に記憶させる基本行列分解部と、乗算結果である行列Cの非零要素数と式A7-1、A7-2、またはA7-3に含まれる行列のうち隣接する2個以上の行列を除いた行列の非対角項の非零要素数の和が、式A7-1、A7-2、またはA7-3に含まれるすべての行列の非対角項の非零要素数の和以下である場合に、中間結果記憶部に記憶されている式A7-1、A7-2、またはA7-3に含まれる行列のうち隣接する2個以上の行列を除いた行列を表わすデータと、行列Cを表わすデータとを行列記憶部に記憶する行列乗算数削減部とを備える。本発明の別の局面に係る符号化装置は、要素数kの情報ベクトルXから、u≧1かつv≧1のときには式A8-1、u≧1かつv=0のときには式A8-2、u=0かつv≧1のときには式A8-3に含まれる少なくとも1セットの隣接する2個以上の行列が、2個以上の行列の乗算結果である行列Cで置換されたパリティ生成式にしたがって実数演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化装置であって、Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXA8-1Y=-U′11U′21U′m11U′m1L′m1L′m11L′21L′11AXA8-2Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXA8-3ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT=0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、u≧1かつv≧1の場合には、行列B′は、行列Bに対して、u回の行の入れ替え、およびv回の列の入れ替えを行なったものであり、行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものであり、行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものであり、u≧1かつv=0の場合には、行列B′は、行列Bに対して、u回の行の入れ替えを行なったものであり、行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものであり、u=0かつv≧1の場合には、行列B′は、行列Bに対して、v回の列の入れ替えを行なったものであり、行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものであり、行列L′i1i=1~mは行列L′iの逆行列であり、行列L′iは、行列B′をLU分解した下三角行列L′の基本下三角行列であって、第i列目が下三角行列L′の第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列U′i1i=1~mは行列U′iの逆行列であり、行列U′iは、行列B′をLU分解した上三角行列U′の基本上三角行列であって、第i行目が上三角行列U′の第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化装置は、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部と、行列積計算部から出力されるベクトルの符号を反転してパリティベクトルYとして出力する符号反転部とを備え、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルを符号反転部に出力する。好ましくは、パリティ生成式に含まれるすべての行列の非対角項の非零要素数の和は、式A8-1、A8-2、またはA8-3に含まれるすべての行列の非対角項の非零要素数の和以下である。好ましくは、符号化装置は、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化装置であって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、行列積計算部は、さらに、式A8-1、A8-2、またはA8-3に含まれる隣接する2個以上の行列の乗算を実行して、乗算結果である行列Cを表わすデータを出力し、符号化装置は、さらに、パリティ検査行列Hを行列Aと行列Bに分解して、行列Aおよび行列Bを表わすデータを中間結果記憶部に記憶させる検査行列分解部と、u≧1かつv≧1の場合、中間結果記憶部から行列Aおよび行列Bを表わすデータを読み出して、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えおよびv回の列の入れ替えを行なった行列B′を生成し、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して中間結果記憶部に記憶させ、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して中間結果記憶部に記憶させ、u≧1かつv=0の場合、中間結果記憶部から行列Aおよび行列Bを表わすデータを読み出して、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えを行なった行列B′を生成し、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して中間結果記憶部に記憶させ、u=0かつv≧1の場合、中間結果記憶部から行列Bを表わすデータを読み出して、行列Bのオーダリングを行ない、行列Bに対してv回の列の入れ替えを行なった行列B′を生成し、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して中間結果記憶部に記憶させるオーダリング部と、行列B′を下三角行列L′と上三角行列U′の積にLU分解して、下三角行列L′を表わすデータおよび上三角行列U′を表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列U′および下三角行列L′を表わすデータを読み出して、上三角行列U′をm個の基本上三角行列U′ii=1~mの積に分解し、下三角行列L′をm個の基本下三角行列L′ii=1~mの積に分解し、分解された行列U′ii=1~mおよび行列′Lii=1~mを表わすデータを中間結果記憶部に記憶させる基本行列分解部と、中間結果記憶部から行列U′ii=1~mおよび行列L′ii=1~mを表わすデータを読み出して、行列U′ii=1~mおよび行列L′ii=1~mの非対角項の要素の符号を反転することによって、逆行列U′i1i=1~mおよび逆行列L′i1i=1~mを算出し、逆行列U′i1i=1~mおよび逆行列L′i1i=1~mを表わすデータを中間結果記憶部に記憶させる逆行列計算部と、乗算結果である行列Cの非零要素数と式A8-1、A8-2、またはA8-3に含まれる行列のうち隣接する2個以上の行列を除いた行列の非対角項の非零要素数の和が、式A8-1、A8-2、またはA8-3に含まれるすべての行列の非対角項の非零要素数の和以下である場合に、中間結果記憶部に記憶されている式A8-1、A8-2、またはA8-3に含まれる行列のうち隣接する2個以上の行列を除いた行列を表わすデータと、行列Cを表わすデータとを行列記憶部に記憶する行列乗算数削減部とを備える。好ましくは、行列積計算部は、パリティ生成式に含まれる複数回の行列乗算のうち、パリティ生成式の右側にある行列乗算から順次実行する。好ましくは、行列積計算部は、パリティ生成式に含まれる複数回の行列乗算のうち2個以上の行列乗算を並行して実行する。本発明の別の局面に係る符号化プログラムは、要素数kの情報ベクトルXから式A9で表わされるパリティ生成式にしたがって2を法とする演算を行なうことによって、要素数mのパリティベクトルYを生成する符号化プログラムであって、Y≡U1U2Um1UmLmLm1L2L1AXA9ただし、X,YTは、ベクトルX,Yの転置を表わし、パリティ検査行列Hは、HX,YT≡0を満たすm行n列の行列であり、行列Aは、パリティ検査行列Hの第1列目~第k列目からなり、行列Bは、パリティ検査行列Hの第k1列目~第n列目からなり、n=kmであり、行列Lii=1~mは、行列BをLU分解した下三角行列Lの基本下三角行列であって、第i列目が下三角行列Lの第i列目と一致し、その他の列は非対角項が0、対角項が1である行列であり、行列Uii=1~mは、行列BをLU分解した上三角行列Uの基本上三角行列であって、第i行目が上三角行列Uの第i行目と一致し、その他の行は非対角項が0、対角項が1である行列であり、符号化プログラムは、コンピュータを、パリティ生成式に含まれる複数個の行列を表わすデータを記憶する行列記憶部と、パリティ生成式に含まれる複数回の行列乗算の中間結果を表わすデータを記憶する中間結果記憶部と、パリティベクトルYを算出するために、パリティ生成式に含まれる複数回の行列乗算を実行する行列積計算部として機能させ、行列積計算部は、情報ベクトルX、行列記憶部内の行列を表わすデータ、または中間結果記憶部内の中間結果を表わすデータを用いて、パリティ生成式に含まれる各行列乗算を実行して、パリティ生成式に含まれる複数回の行列乗算が終了するまでの間は、該計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部内に記憶させ、パリティ生成式に含まれる複数回の行列乗算が終了したら、パリティ生成式に含まれる複数回の行列乗算の終了後に得られるベクトルをパリティベクトルYとして出力する。好ましくは、符号化プログラムは、パリティベクトルYを生成する前に、パリティ生成式に含まれる行列を生成する符号化プログラムであって、中間結果記憶部は、さらに、パリティ生成式に含まれる行列を生成する処理の中間結果を表わすデータを記憶し、符号化プログラムは、コンピュータを、さらに、パリティ検査行列Hを行列Aと行列Bに分解して、行列Aを表わすデータを行列記憶部に記憶させる検査行列分解部と、行列Bを下三角行列Lと上三角行列Uの積にLU分解して、下三角行列Lを表わすデータおよび上三角行列Uを表わすデータを中間結果記憶部に記憶させるLU分解部と、中間結果記憶部から上三角行列Uおよび下三角行列Lを表わすデータを読み出して、上三角行列Uをm個の基本上三角行列Uii=1~mの積に分解し、下三角行列Lをm個の基本下三角行列Lii=1~mの積に分解し、分解された行列Uii=1~mおよび行列Lii=1~mを表わすデータを行列記憶部に記憶させる基本行列分解部として機能させる。本発明によれば、従来よりも少ない計算量でパリティを計算することができる。全体構成以下、本発明に係る実施の形態について図面を参照して説明する。図1は、本発明の実施形態の通信システムの構成の一例を示す図である。図1の通信システムにおいて、送信装置1は、符号化器2と変調器3とを備え、受信装置4は、復調器6と誤り訂正復号化器7とを備える。符号化器2は、kビットの情報ビットからなる情報ベクトルXに対し、mビットのパリティビットからなるパリティベクトルYを付加して、n=kmビットのLDPC符号低密度パリティ検査符号Zを生成する。パリティベクトルYの生成のために用いられるパリティ検査行列Hm行、n列においては、行数mが冗長ビット数に対応し、列数nが符号ビット数に対応する。変調器3は、通信路7の構成に応じて、LDPC符号Zに対して、振幅変調、位相変調、コード変調、周波数変調または直行周波数分割多重変調などの変調を行なう。復調器6は、通信路7を介して受信した変調信号に対して、この通信路7における送信形態に応じて復調処理を行なうことによって、nビットの多値量子化Lを多値数とすると、L≧2されたデジタル符号を出力する。たとえば、振幅変調、位相変調、コード変調、周波数変調および直行周波数分割多重変調等の場合、復調器において、振幅復調、位相復調、コード復調、および周波数復調等の処理が行なわれる。誤り訂正復号化器5は、復調器から出力されるnビットの符号にパリティ検査行列Hを適用して、kビットの情報ビットからなる情報ベクトルXを復元する。[第1の実施形態]第1の実施形態の符号化器は、2を法とする演算を行なう。符号化アルゴリズム符号化器は、k個の情報ビットx1、x2、、xkからなる情報ベクトルXを受けて、2を法とする演算を行なうことによって、以下の式を満たすようなm個のパリティビットy1、y2、、ymからなるパリティベクトルYを生成する。HX,YT≡0B1ここで、Hはパリティ検査行列以下、検査行列とも言うであり、m行n列=kmの行列である。X,YTは、情報ベクトルとパリティベクトルからなるベクトルの転置を表わす。式B1は、2を法とする演算の場合には、次のように変形される。BY≡AXB2ここで、行列Aは、検査行列Hの第1列目~第k列目からなるm行k列の行列である。行列Bは、検査行列Hの第k1列目~第n列目からなるm行m列の行列である。行列BをLU分解すると、式B2は以下の式に変形される。LUY≡AXB3ここで、Lは下三角行列であり、Uは上三角行列である。式B3より、列ベクトルYは、以下の式で表わされる。Y≡U1L1AXB4上三角行列Uは、以下の式のように、基本上三角行列Uii=1~mの積に分解される。U≡UmUm1U2U1B5式B5より、逆行列U1は、以下の式で表わされる。U1≡U11U21Um11Um1B6下三角行列Lは、以下の式のように、基本下三角行列Lii=1~mの積に分解される。L≡L1L2Lm1LmB7式B7より、逆行列L1は、以下の式で表わされる。L1≡Lm1Lm11L21L11B8式B6および式B8によって、式B4は以下の式に変形される。Y≡U11U21Um11Um1Lm1Lm11L21L11AXB9ところで、2を法とする演算の場合には、基本上三角行列Ui、基本下三角行列Liは、以下のような性質を有する。Ui≡Ui1B10Li≡Li1B11式B10および式B11によって、式B9は以下の式に変形される。Y≡U1U2Um1UmLmLm1L2L1AXB12式B12で算出されるパリティベクトルYと、情報ベクトルXを用いて、符号化ベクトルZは、以下の式で表わされる。Z≡X,YB13ここで、符号化ベクトルZの第1ビット~第kビットは、情報ベクトルXのビットであり、符号化ベクトルZの第k1ビット~第nビットは、パリティベクトルYのビットである。構成図2は、第1の実施形態の符号化器の構成を表わす図である。図2を参照して、この符号化器2aは、検査行列分解部10と、LU分解部14と、基本行列分解部16と、中間結果記憶部12と、行列記憶部18と、行列積計算部11と、配列部20と、行列積計算制御部121とを備える。検査行列分解部10は、検査行列Hを行列A、Bに分解して、行列Aを表わすデータを行列記憶部18に記憶させ、行列Bを表わすデータを中間結果記憶部12に記憶させる。情報ベクトルXの次元をk、パリティベクトルYの次元をmとし、km=nとしたときに、検査行列Hは、m×nの行列である。検査行列分解部10は、検査行列Hから第1列目~第k列目を抜き出して、行列Aとし、第k1列目から第n列目までを抜き出して、行列Bとする。Aは、m×kの行列であり、Bは、m×mの行列である。LU分解部14は、加算器13および乗算器15を備える。LU分解部14は、Croutクラウトのアルゴリズムにしたがって、行列BをLU分解して、下三角行列Lと、上三角行列Uとを生成する。基本行列分解部16は、上三角行列Uを式B5のように、基本上三角行列Uii=1~mの積に分解する。また、基本行列分解部16は、下三角行列Lを式B7のように、基本下三角行列Lii=1~mの積に分解する。基本上三角行列Uiは、第i行が上三角行列Uの第i行であり、第i行以外の行は、対角項の要素が1で、非対角項の要素が0であるような行列である。たとえば、上三角行列Uが式1で表わされる場合には、基本上三角行列U1、U2、U3は、それぞれ、式2、式3、式4で表わされる。基本下三角行列Liは、第i列が下三角行列Lの第i列であり、第i列以外の列は、対角項の要素が1であり、非対角項の要素が0であるような行列である。たとえば、下三角行列Lが式5で表わされる場合には、基本下三角行列L1、L2、L3は、それぞれ、式6、式7、式8で表わされる。行列記憶部18は、基本上三角行列U1、U2、、Umを表わすデータ、基本下三角行列Lm、Lm1、、L1を表わすデータ、および行列Aを表わすデータを記憶する。行列積計算部11は、加算器17および乗算器19を備える。行列積計算部11は、パリティベクトルYを算出するために、式B12に含まれる2m1回の行列乗算を行列積計算制御部121に指示された順序で実行する。行列積計算部11は、入力される情報ベクトルX、行列記憶部18内の行列U1、U2、、Um、Lm、Lm1、、L1、Aを表わすデータ、および中間結果記憶部12内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行する。行列積計算部11は、式B12に含まれる2m1回の行列乗算が終了するまでの間は、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部12に記憶させる。行列積計算制御部121は、パリティベクトルYを算出するために、行列記憶部18にデータが記憶されている行列の順序が先頭からA、L1、L2、、Lm1、Lm、Um、Um1、、U2、U1の順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部11を制御する。また、行列積計算制御部121は、式B12に含まれる2m1回の行列乗算の終了後に、行列積計算部11から計算結果であるパリティベクトルYを出力させる。中間結果記憶部12は、式B12に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部12は、パリティベクトルYの生成処理時に、式B12に含まれる2m1回の行列乗算の中間結果を表わすデータを記憶する。配列部20は、kビットの情報ベクトルXと、算出されたmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力する。行列分解処理図3は、第1の実施形態の行列分解処理のフローチャートである。図3を参照して、検査行列分解部10は、検査行列Hを行列A、Bに分解する。検査行列分解部10は、行列Aを表わすデータを行列記憶部18に記憶させ、行列Bを表わすデータを中間結果記憶部12に記憶させるステップS101。次に、LU分解部14は、中間結果記憶部12から行列Bを表わすデータを読み出して、行列BをLU分解して、下三角行列Lを表わすデータと、上三角行列Uを表わすデータとを中間結果記憶部12に記憶させるステップS102。次に、基本行列分解部16は、中間結果記憶部12から上三角行列Uを表わすデータを読み出して、上三角行列Uを基本上三角行列U1、U2、、Umの積に分解して、基本上三角行列U1、U2、、Umを表わすデータを行列記憶部18に記憶させる。また、基本行列分解部16は、中間結果記憶部12から下三角行列Lを表わすデータを読み出して、下三角行列Lを基本下三角行列L1、L2、、Lmの積に分解して、基本下三角行列L1、L2、、Lmを表わすデータを行列記憶部18に記憶させるステップS103。符号化ベクトル生成処理図4は、第1の実施形態の符号化ベクトル生成処理のフローチャートである。図4を参照して、行列積計算制御部121は、行列記憶部18にデータが記憶されている行列の順序が先頭からA、L1、L2、、Lm1、Lm、Um、Um1、、U2、U1の順となるように行列間の順序を設定するステップS201。次に、行列積計算制御部121は、制御変数iを1に設定するステップS202。行列積計算制御部121は、行列積計算部11を指示して、行列記憶部18から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。行列積計算部11は、乗算結果であるベクトルを中間結果Rとし、中間結果Rを表わすデータを中間結果記憶部12に記憶させるステップS203。次に、行列積計算制御部121は、制御変数iをインクリメントするステップS204。行列積計算制御部121は、制御変数iが2m1未満の場合にはステップS205でYES、行列積計算部11を指示して、行列記憶部18から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部12に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部11は、乗算結果であるベクトルを新たな中間結果Rとし、中間結果記憶部12内の中間結果Rを表わすデータを更新するステップS206。その後、ステップS204からの処理が繰返される。制御変数iが2m1となった場合にはステップS205でNO、行列積計算制御部121は、行列積計算部11を指示して、行列記憶部18から第i順位の行列Matiを表わすデータを読み出させるとともに、中間結果記憶部12に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部11は、乗算結果であるベクトルをパリティべクトルYとして出力するステップS207。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS208。第1の実施形態の効果以上のように、第1の実施形態によれば、符号化ベクトル生成処理時において、後退代入を行わずに、式B12に従ってパリティベクトルYを算出するので、少ない計算量で情報ベクトルXの符号化を行なうことができる。特に、基本上三角行列Uiおよび基本下三角行列Liは非零要素数が少ない行列のため、式B12の演算の計算量が少ない。また、式B12の右側にある行列乗算から順次実行してパリティベクトルYを算出するので、各行列乗算の結果はベクトルとなり、中間結果を記憶するための容量を小さくすることができる。また、行列分解処理時において、行列Bの逆行列を計算するという計算量の多い演算を行なうことなく、行列BのLU分解、LU分解された上三角行列の基本上三角行列の積への分解、LU分解された下三角行列の基本下三角行列の積への分解を行なえばよいので、少ない計算量でパリティベクトルYを生成するのに必要な行列を算出することができる。[第1の実施形態の変形例1]第1の実施形態の変形例1の符号化器は、実数演算を行なう。符号化アルゴリズム符号化器は、k個の情報ビットx1、x2、、xkからなる情報ベクトルXを受けて、実数演算を行なうことによって、以下の式を満たすようなm個のパリティビットy1、y2、、ymからなるパリティベクトルYを生成する。HX,YT=0C1ここで、Hはパリティ検査行列以下、検査行列とも言うであり、m行n列=kmの行列である。X,YTは、情報ベクトルとパリティベクトルからなるベクトルの転置を表わす。式C1は、実数演算の場合には、次のように変形される。BY=-AXC2ここで、行列Aは、検査行列Hの第1列目~第k列目からなるm行k列の行列である。行列Bは、検査行列Hの第k1列目~第n列目からなるm行m列の行列である。行列BをLU分解すると、式C2は以下の式に変形される。LUY=-AXC3ここで、Lは下三角行列であり、Uは上三角行列である。式C3より、列ベクトルYは、以下の式で表わされる。Y=-U1L1AXC4上三角行列Uは、以下の式のように、基本上三角行列Uii=1~mの積に分解される。U=UmUm1U2U1C5式C5より、逆行列U1は、以下の式で表わされる。U1=U11U21Um11Um1C6ここで、Ui1は、対角項の要素が1であり、かつ非対角項の要素はUiの要素の符号を反転したものである。下三角行列Lは、以下の式のように、基本下三角行列Lii=1~mの積に分解される。L=L1L2Lm1LmC7式C7より、逆行列L1は、以下の式で表わされる。L1=Lm1Lm11L21L11C8ここで、Li1は、対角項の要素が1であり、かつ非対角項の要素はLiの要素の符号を反転したものである。式C6および式C8によって、式C4は以下の式に変形される。Y=-U11U21Um11Um1Lm1Lm11L21L11AXC9式C9で算出されるパリティベクトルYと、情報ベクトルXを用いて、符号化ベクトルZは、以下の式で表わされる。Z=X,YC10ここで、符号化ベクトルZの第1ビット~第kビットは、情報ベクトルXのビットであり、符号化ベクトルZの第k1ビット~第nビットは、パリティベクトルYのビットである。構成図5は、第1の実施形態の変形例1の符号化器の構成を表わす図である。図5を参照して、この符号化器2bは、第1の実施形態と同様の、検査行列分解部10と、LU分解部14と、基本行列分解部16と、配列部20とを備える。これらについては説明を繰返さない。また、符号化器2bは、行列記憶部28と、逆行列計算部23と、行列積計算部21と、中間結果記憶部22と、符号反転部99と、行列積計算制御部122とを備える。逆行列計算部23は、中間結果記憶部22から基本上三角行列U1、U2、、Umおよび基本下三角行列L1、L2、、Lmを表わすデータを読み出して、行列U1、U2、、Um、L1、L2、、Lmの非対角項の要素の符号を反転することによって、行列U1、U2、、Um、L1、L2、、Lmの逆行列U11、U21、、Um1、L11、L21、、Lm1を算出し、逆行列U11、U21、、Um1、L11、L21、、Lm1を表わすデータを行列記憶部28に記憶させる。たとえば、行列U4が式9で表わされる場合には、逆行列U41は、式10で表わされる。たとえば、行列L4が式11で表わされる場合には、逆行列L41は、式12で表わされる。行列記憶部28は、基本上三角行列の逆行列U11、U21、、Um1を表わすデータ、基本下三角行列の逆行列Lm1、Lm11、、L11を表わすデータ、および行列Aを表わすデータを記憶する。行列積計算部21は、加算器27および乗算器29を備える。行列積計算部21は、パリティベクトルYを算出するために、式C9に含まれる2m1回の行列乗算を行列積計算制御部122に指示された順序で実行する。行列積計算部21は、入力される情報ベクトルX、行列記憶部28内の行列U11、U21、、Um1、Lm1、Lm11、、L11、Aを表わすデータ、および中間結果記憶部22内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行する。行列積計算部21は、式C9に含まれる2m1回の行列乗算が終了するまでの間は、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部22に記憶させる。行列積計算制御部122は、パリティベクトルYを算出するために、行列記憶部28にデータが記憶されている行列の順序が先頭からA、L11、L21、、Lm11、Lm1、Um1、Um11、、U21、U11の順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部21を制御する。また、行列積計算制御部122は、式C9に含まれる2m1回の行列乗算の終了後に、行列積計算部21から計算結果であるベクトルY′=U11U21Um11Um1Lm1Lm11L21L11AXを符号反転部99へ出力させる。中間結果記憶部22は、式C9に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部22は、パリティベクトルYの生成処理時に、式C9に含まれる2m1回の行列乗算の中間結果を表わすデータを記憶する。符号反転部99は、ベクトルY′の符号を反転してつまり、ベクトルの各要素の符号を反転して、それをパリティベクトルYとして出力する。行列分解処理図6は、第1の実施形態の変形例1の行列分解処理のフローチャートである。図6を参照して、検査行列分解部10は、検査行列Hを行列A、Bに分解する。検査行列分解部10は、行列Aを表わすデータを行列記憶部28に記憶させ、行列Bを表わすデータを中間結果記憶部22に記憶させるステップS301。次に、LU分解部14は、中間結果記憶部22から行列Bを表わすデータを読み出して、行列BをLU分解して、下三角行列Lを表わすデータと、上三角行列Uを表わすデータとを中間結果記憶部22に記憶させるステップS302。次に、基本行列分解部16は、中間結果記憶部22から上三角行列Uを表わすデータを読み出して、上三角行列Uを基本上三角行列U1、U2、、Umの積に分解して、基本上三角行列U1、U2、、Umを表わすデータを中間結果記憶部22に記憶させる。また、基本行列分解部16は、中間結果記憶部22から下三角行列Lを表わすデータを読み出して、下三角行列Lを基本下三角行列L1、L2、、Lmの積に分解して、基本下三角行列L1、L2、、Lmを表わすデータを中間結果記憶部22に記憶させるステップS303。逆行列計算部23は、中間結果記憶部22から基本上三角行列U1、U2、、Umおよび基本下三角行列L1、L2、、Lmを表わすデータを読み出して、行列U1、U2、、Um、L1、L2、、Lmの非対角項の要素の符号を反転することによって、行列U1、U2、、Um、L1、L2、、Lmの逆行列U11、U21、、Um1、L11、L21、、Lm1を算出し、逆行列U11、U21、、Um1、L11、L21、、Lm1を表わすデータを行列記憶部28に記憶させるステップS304。符号化ベクトル生成処理図7は、第1の実施形態の変形例1の符号化ベクトル生成処理のフローチャートである。図7を参照して、行列積計算制御部122は、行列記憶部28にデータが記憶されている行列の順序が先頭からA、L11、L21、、Lm11、Lm1、Um1、Um11、、U21、U11の順となるように行列間の順序を設定するステップS401。次に、行列積計算制御部122は、制御変数iを1に設定するステップS402。行列積計算制御部122は、行列積計算部21を指示して、行列記憶部28から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。行列積計算部21は、乗算結果であるベクトルを中間結果Rとし、中間結果Rを表わすデータを中間結果記憶部22に記憶させるステップS403。次に、行列積計算制御部122は、制御変数iをインクリメントするステップS404。行列積計算制御部122は、制御変数iが2m1未満の場合にはステップS405でYES、行列積計算部21を指示して、行列記憶部28から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部22に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部21は、乗算結果であるベクトルを新たな中間結果Rとし、中間結果記憶部22内の中間結果Rを表わすデータを更新するステップS406。その後、ステップS404からの処理が繰返される。制御変数iが2m1となった場合にはステップS405でNO、行列積計算制御部122は、行列積計算部21を指示して、行列記憶部28から第i順位の行列Matiを表わすデータを読み出させるとともに、中間結果記憶部22に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部21は、乗算結果であるベクトルY′を符号反転部99に出力する。符号反転部99は、ベクトルY′の符号を反転したものをパリティべクトルYとして出力するステップS407。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS408。第1の実施形態の変形例1の効果以上のように、第1の実施形態の変形例1によれば、符号化ベクトル生成処理時において、後退代入を行わずに、式C9に従ってパリティベクトルYを算出するので、少ない計算量で情報ベクトルXの符号化を行なうことができる。特に、基本上三角行列の逆行列Ui1および基本下三角行列の逆行列Li1は非零要素数が少ない行列のため、式C9の演算の計算量が少ない。また、式C9の右側にある行列乗算から順次実行してパリティベクトルYを算出するので、各行列乗算の結果はベクトルとなり、中間結果を記憶するための容量を小さくすることができる。また、行列分解処理時において、行列Bの逆行列を計算するという計算量の多い演算を行なうことなく、行列BのLU分解、LU分解された上三角行列の基本上三角行列の積への分解、LU分解された下三角行列の基本下三角行列の積への分解、基本上三角行列および基本下三角行列の非対角項の符号の反転を行なえばよいので、少ない計算量でパリティベクトルYを生成するのに必要な行列を算出することができる。[第2の実施形態]第2の実施形態の符号化器は、2を法とする演算を行なう。符号化アルゴリズム符号化器は、k個の情報ビットx1、x2、、xkからなる情報ベクトルXを受けて、2を法とする演算を行なうことによって、以下の式を満たすようなm個のパリティビットy1、y2、、ymからなるパリティベクトルYを生成する。HX,YT≡0D1ここで、Hはパリティ検査行列以下、検査行列とも言うであり、m行n列=kmの行列である。X,YTは、情報ベクトルとパリティベクトルからなるベクトルの転置を表わす。式D1は、2を法とする演算の場合には、次のように変形される。BY≡AXD2ここで、行列Aは、検査行列Hの第1列目~第k列目からなるm行k列の行列である。行列Bは、検査行列Hの第k1列目~第n列目からなるm行m列の行列である。行列Bに対して、以下のようにオーダリングを行なうとする。まず、行列Bの2つの行を交換するとすると、式D2は以下のように変形される。P1BY≡P1AXD3ここで、P1は、第1回目の行の入れ替えを表わす変換行列である。i行とj行を変換する場合には、P1は、単位行列Eのi行とj行を入れ替えた行列となる。さらに、行列Bの2つの列を交換すると、式D3は以下のように変形される。P1BQ1Q11Y≡P1AXD4ここで、Q1は、第1回目の列の入れ替えを表わす変換行列である。i列とj列を変換する場合には、Q1は、単位行列Eのi列とj列を入れ替えた行列となる。以下のように新たな行列を定義する。B≡P1BQ1D5A≡P1AD6式D5および式D6により、式D4は以下の式で表わされる。BQ11Y≡AXD7さらに、行列Bの2つの行を交換するとすると、式D7は以下のように変形される。P2BQ11Y≡P2AXD8ここで、P2は、第2回目の行の入れ替えを表わす変換行列である。さらに、行列Bの2つの列を交換すると、式D8は以下のように変形される。P2BQ2Q21Q11Y≡P2AXD9ここで、Q2は、第2回目の列の入れ替えを表わす変換行列である。以下のように新たな行列を定義する。B≡P2BQ2D10A≡P2AD11式D10および式D11により、式D9は以下の式で表わされる。BQ21Q11Y≡AXD12同様にして、行列Bに対して、第u回u≧1だけ行の入れ替えおよび第vv≧1だげ列の入れ替えを行なう。第s回目1≦s≦uの行の入れ替えを表わす行列をPs、第s回目1≦s≦vの列の入れ替えを表わす行列をQsとして、以下のように新たな行列を定義する。B′≡PuP2P1BQ1Q2QvD13A≡PuP2P1AD14E≡Q1Q2QvD15式D13、式D14および式D15により、以下の式が成り立つ。B′E1Y≡AXD16行列B′をLU分解すると、式D16は以下の式に変形される。L′U′E1Y≡AXD17ここで、L′は下三角行列であり、U′は上三角行列である。式D17より、列ベクトルYは、以下の式で表わされる。Y≡EU′1L′1AXD18上三角行列U′は、以下の式のように、基本上三角行列U′ii=1~mの積に分解される。U′≡U′mU′m1U′2U′1D19式D19より、逆行列U′1は、以下の式で表わされる。U′1≡U′11U′21U′m11U′m1D20下三角行列L′は、以下の式のように、基本下三角行列L′ii=1~mの積に分解される。L′≡L′1L′2L′m1L′mD21式D21より、逆行列L′1は、以下の式で表わされる。L′1≡L′m1L′m11L′21L′11D22式D20および式D22によって、式D18は以下の式に変形される。Y≡EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXD23ところで、2を法とする演算の場合には、基本上三角行列U′i、基本下三角行列L′iは、以下のような性質を有する。U′i≡U′i1D24L′i≡L′i1D25式D24および式D25によって、式D23は以下の式に変形される。Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXD26式D26で算出されるパリティベクトルYと、情報ベクトルXを用いて、符号化ベクトルZは、以下の式で表わされる。Z≡X,YD27ここで、符号化ベクトルZの第1ビット~第kビットは、情報ベクトルXのビットであり、符号化ベクトルZの第k1ビット~第nビットは、パリティベクトルYのビットである。構成図8は、第2の実施形態の符号化器の構成を表わす図である。図8を参照して、この符号化器2cは、検査行列分解部30と、オーダリング部40と、LU分解部34と、基本行列分解部36と、中間結果記憶部32と、行列記憶部38と、行列積計算部31と、配列部20と、行列積計算制御部123とを備える。検査行列分解部30は、検査行列Hを行列A、Bに分解して、行列Aを表わすデータおよび行列Bを表わすデータを中間結果記憶部32に記憶させる。オーダリング部40は、LU分解によって得られる上三角行列、下三角行列の非零要素数が少なくなるように、行列Bに対して、第u回u≧1の行の入れ替えおよび第v回v≧1の列の入れ替えを行なって、行列B′を生成する。オーダリングの手法としては、たとえば、最小次数順序法を用いることができる。また、オーダリング部40は、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なって行列Aを生成し、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なって、行列Eを生成する。LU分解部34は、加算器33およ乗算器35を備える。LU分解部34は、Croutクラウトのアルゴリズムにしたがって、行列B′をLU分解して、下三角行列L′と、上三角行列U′とを生成する。基本行列分解部36は、上三角行列U′を式D19のように、基本上三角行列U′ii=1~mの積に分解する。また、基本行列分解部36は、下三角行列L′を式D21のように、基本下三角行列L′ii=1~mの積に分解する。行列記憶部38は、基本上三角行列U′1、U′2、、U′mを表わすデータ、基本下三角行列L′m、L′m1、、L′1を表わすデータ、および行列A、Eを表わすデータを記憶する。行列積計算部31は、加算器37および乗算器39を備える。行列積計算部31は、パリティベクトルYを算出するために、式D26に含まれる2m2回の行列乗算を行列積計算制御部123に指示された順序で実行する。行列積計算部31は、入力される情報ベクトルX、行列記憶部38内の行列U′1、U′2、、U′m、L′m、L′m1、、L′1、A、Eを表わすデータ、および中間結果記憶部32内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行する。行列積計算部31は、式D26に含まれる2m2回の行列乗算が終了するまでの間は、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部32に記憶させる。行列積計算制御部123は、パリティベクトルYを算出するために、行列記憶部38にデータが記憶されている行列の順序が先頭からA、L′1、L′2、、L′m、U′m、U′m1、、U′1、Eの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部31を制御する。また、行列積計算制御部123は、式D26に含まれる2m2回の行列乗算の終了後に、行列積計算部31から計算結果であるパリティベクトルYを出力させる。中間結果記憶部32は、式D26に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部32は、パリティベクトルYの生成処理時に、式D26に含まれる2m2回の行列乗算の中間結果を表わすデータを記憶する。配列部20は、kビットの情報ベクトルXと、算出されたmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力する。行列分解処理図9は、第2の実施形態の行列分解処理のフローチャートである。図9を参照して、検査行列分解部30は、検査行列Hを行列A、Bに分解する。検査行列分解部30は、行列Aを表わすデータおよび行列Bを表わすデータを中間結果記憶部32に記憶させるステップS501。オーダリング部40は、行列Bに対して、第u回u≧1の行の入れ替えおよび第v回v≧1の列の入れ替えを行なう。オーダリング部40は、第s回目1≦s≦uの行の入れ替えを表わす行列をPs、第s回目1≦s≦vの列の入れ替えを表わす行列をQsとして、以下のように新たな行列を生成する。B′≡PuP2P1BQ1Q2QvD13A≡PuP2P1AD14E≡Q1Q2QvD15つまり、行列B′は、行列Bに対して、u回u≧1の行の入れ替え、およびv回v≧1の列の入れ替えを行なったものである。行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものである。行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものである。オーダリング部40は、行列A、Eを表わすデータを行列記憶部38に記憶させ、行列B′を表わすデータを中間結果記憶部32に記憶させるステップS502。次に、LU分解部34は、中間結果記憶部32から行列B′を表わすデータを読み出して、行列B′をLU分解して、下三角行列L′を表わすデータと、上三角行列U′を表わすデータとを中間結果記憶部32に記憶させるステップS503。次に、基本行列分解部36は、中間結果記憶部32から上三角行列U′を表わすデータを読み出して、上三角行列U′を基本上三角行列U′1、U′2、、U′mの積に分解して、基本上三角行列U′1、U′2、、U′mを表わすデータを行列記憶部38に記憶させる。また、基本行列分解部36は、中間結果記憶部32から下三角行列L′を表わすデータを読み出して、下三角行列Lを基本下三角行列L′1、L′2、、L′mの積に分解して、基本下三角行列L′1、L′2、、L′mを表わすデータを行列記憶部38に記憶させるステップS504。符号化ベクトル生成処理図10は、第2の実施形態の符号化ベクトル生成処理のフローチャートである。図10を参照して、行列積計算制御部123は、行列記憶部38にデータが記憶されている行列の順序が先頭からA、L′1、L′2、、L′m、U′m、U′m1、、U′1、Eの順となるように行列間の順序を設定するステップS601。次に、行列積計算制御部123は、制御変数iを1に設定するステップS602。行列積計算制御部123は、行列積計算部31を指示して、行列記憶部38から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。行列積計算部31は、乗算結果であるベクトルを中間結果Rとし、中間結果Rを表わすデータを中間結果記憶部32に記憶させるステップS603。次に、行列積計算制御部123は、制御変数iをインクリメントするステップS604。行列積計算制御部123は、制御変数iが2m2未満の場合にはステップS605でYES、行列積計算部31を指示して、行列記憶部38から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部32に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部31は、乗算結果であるベクトルを新たな中間結果Rとし、中間結果記憶部32内の中間結果Rを表わすデータを更新するステップS606。その後、ステップS604からの処理が繰返される。制御変数iが2m2となった場合にはステップS605でNO、行列積計算制御部123は、行列積計算部31を指示して、行列記憶部38から第i順位の行列Matiを表わすデータを読み出させるとともに、中間結果記憶部32に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部31は、乗算結果であるベクトルをパリティべクトルYとして出力するステップS607。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS608。第2の実施形態の効果以上のように、第2の実施形態によれば、符号化ベクトル生成処理時において、後退代入を行わずに、式D26に従ってパリティベクトルYを算出するので、少ない計算量で情報ベクトルXの符号化を行なうことができる。特に、行列Bがオーダリングされるため、基本上三角行列U′iおよび基本下三角行列L′iは、第1の実施形態の基本上三角行列Uiおよび基本下三角行列Liよりもさらに非零要素数が少ない行列となり、式D26の演算の計算量を式B12よりもさらに少なくできる。また、式D26の右側にある行列乗算から順次実行してパリティベクトルYを算出するので、各行列乗算の結果はベクトルとなり、中間結果を記憶するための容量を小さくすることができる。また、行列分解処理時において、行列Bの逆行列を計算するという計算量の多い演算を行なうことなく、行列Bのオーダリングによる行列B′、A、Eの生成、行列B′のLU分解、LU分解された上三角行列の基本上三角行列の積への分解、LU分解された下三角行列の基本下三角行列の積への分解を行なえばよいので、少ない計算量でパリティベクトルYを生成するのに必要な行列を算出することができる。[第2の実施形態の変形例1]第2の実施形態の変形例1の符号化器は、実数演算を行なう。符号化アルゴリズム符号化器は、k個の情報ビットx1、x2、、xkからなる情報ベクトルXを受けて、実数演算を行なうことによって、以下の式を満たすようなm個のパリティビットy1、y2、、ymからなるパリティベクトルYを生成する。HX,YT=0E1ここで、Hはパリティ検査行列以下、検査行列とも言うであり、m行n列=kmの行列である。X,YTは、情報ベクトルとパリティベクトルからなるベクトルの転置を表わす。式E1は、実数演算の場合には、次のように変形される。BY=-AXE2ここで、行列Aは、検査行列Hの第1列目~第k列目からなるm行k列の行列である。行列Bは、検査行列Hの第k1列目~第n列目からなるm行m列の行列である。行列Bに対して、以下のようにオーダリングを行なうとする。まず、行列Bの2つの行を交換するとすると、式E2は以下のように変形される。P1BY=P1AXE3ここで、P1は、第1回目の行の入れ替えを表わす変換行列である。i行とj行を変換する場合には、P1は、単位行列Eのi行とj行を入れ替えた行列となる。さらに、行列Bの2つの列を交換すると、式E3は以下のように変形される。P1BQ1Q11Y=-P1AXE4ここで、Q1は、第1回目の列の入れ替えを表わす変換行列である。i列とj列を変換する場合には、Q1は、単位行列Eのi列とj列を入れ替えた行列となる。以下のように新たな行列を定義する。B=P1BQ1E5A=P1AE6式E5および式E6により、式E4は以下の式で表わされる。BQ11Y=-AXE7さらに、行列Bの2つの行を交換するとすると、式E7は以下のように変形される。P2BQ11Y=-P2AXE8ここで、P2は、第2回目の行の入れ替えを表わす変換行列である。さらに、行列Bの2つの列を交換すると、式E8は以下のように変形される。P2BQ2Q21Q11Y=-P2AXE9ここで、Q2は、第2回目の列の入れ替えを表わす変換行列である。以下のように新たな行列を定義する。B=P2BQ2E10A=P2AE11式E10および式E11により、式E9は以下の式で表わされる。BQ21Q11Y=-AXE12同様にして、行列Bに対して、第u回u≧1だけ行の入れ替えおよび第vv≧1だげ列の入れ替えを行なう。第s回目1≦s≦uの行の入れ替えを表わす行列をPs、第s回目1≦s≦vの列の入れ替えを表わす行列をQsとして、以下のように新たな行列を定義する。B′=PuP2P1BQ1Q2QvE13A=PuP2P1AE14E=Q1Q2QvE15式E13、式E14および式E15により、以下の式が成り立つ。B′E1Y=-AXE16行列B′をLU分解すると、式E16は以下の式に変形される。L′U′QV1Q21Q11Y=AXE17ここで、L′は下三角行列であり、U′は上三角行列である。式E17より、列ベクトルYは、以下の式で表わされる。Y=-EU′1L′1AXE18上三角行列U′は、以下の式のように、基本上三角行列U′ii=1~mの積に分解される。U′=U′mU′m1U′2U′1E19ここで、逆行列U′i1は、対角項の要素が1であり、かつ非対角項の要素はU′iの要素の符号を反転したものである。式E19より、U′1は、以下の式で表わされる。U′1=U′11U′21U′m11U′m1E20下三角行列Lは、以下の式のように、基本下三角行列Lii=1~mの積に分解される。L′=L′1L′2L′m1L′mE21ここで、逆行列L′i1は、対角項の要素が1であり、かつ非対角項の要素はL′iの要素の符号を反転したものである。式E21より、L′1は、以下の式で表わされる。L′1=L′m1L′m11L′21L′11E22式E20および式E22によって、式E18は以下の式に変形される。Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXE23式E23で算出されるパリティベクトルYと、情報ベクトルXを用いて、符号化ベクトルZは、以下の式で表わされる。Z=X,YE24ここで、符号化ベクトルZの第1ビット~第kビットは、情報ベクトルXのビットであり、符号化ベクトルZの第k1ビット~第nビットは、パリティベクトルYのビットである。構成図11は、第2の実施形態の変形例1の符号化器の構成を表わす図である。図11を参照して、この符号化器2dは、第2の実施形態と同様の、検査行列分解部30と、オーダリング部40と、LU分解部34と、基本行列分解部36と、配列部20とを備える。これらについては説明を繰返さない。また、符号化器2dは、行列記憶部48と、逆行列計算部43と、行列積計算部41と、中間結果記憶部42と、符号反転部99と、行列積計算制御部124とを備える。逆行列計算部43は、中間結果記憶部42から基本上三角行列U′1、U′2、、U′mおよび基本下三角行列L′1、L′2、、L′mを表わすデータを読み出して、行列U′1、U′2、、U′m、L′1、L′2、、L′mの非対角項の要素の符号を反転することによって、行列U′1、U′2、、U′m、L′1、L′2、、L′mの逆行列U′11、U′21、、U′m1、L′11、L′21、、L′m1を算出し、逆行列U′11、U′21、、U′m1、L′11、L′21、、L′m1を表わすデータを行列記憶部48に記憶させる。行列記憶部48は、基本上三角行列の逆行列U′11、U′21、、U′m1を表わすデータ、基本下三角行列の逆行列L′m1、L′m11、、L′11を表わすデータ、および行列A、Eを表わすデータを記憶する。行列積計算部41は、加算器47および乗算器49を備える。行列積計算部41は、パリティベクトルYを算出するために、式E23に含まれる2m2回の行列乗算を行列積計算制御部124に指示された順序で実行する。行列積計算部41は、入力される情報ベクトルX、行列記憶部48内の行列U′11、U′21、、U′m1、L′m1、L′m11、、L′11、A、Eを表わすデータ、および中間結果記憶部42内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行する。行列積計算部41は、式E23に含まれる2m2回の行列乗算が終了するまでの間は、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部42に記憶させる。行列積計算制御部124は、パリティベクトルYを算出するために、行列記憶部48にデータが記憶されている行列の順序が先頭からA、L′11、L′21、、L′m11、L′m1、U′m1、U′m11、、U′21、U′11、Eの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部41を制御する。また、行列積計算制御部124は、式E23に含まれる2m2回の行列乗算の終了後に、行列積計算部41から計算結果であるベクトルY′=EU′11U′21U′m11U′m1L′m1L′m11L′21L′11Aを符号反転部99へ出力させる。中間結果記憶部42は、式E23に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部42は、パリティベクトルYの生成処理時に、式E23に含まれる2m2回の行列乗算の中間結果を表わすデータを記憶する。符号反転部99は、ベクトルY′の符号を反転してつまり、ベクトルの各要素の符号を反転して、それをパリティベクトルYとして出力する。行列分解処理図12は、第2の実施形態の変形例1の行列分解処理のフローチャートである。図12を参照して、検査行列分解部30は、検査行列Hを行列A、Bに分解する。検査行列分解部30は、行列Aを表わすデータおよび行列Bを表わすデータを中間結果記憶部42に記憶させるステップS701。オーダリング部40は、行列Bに対して、第u回u≧1の行の入れ替えおよび第v回v≧1の列の入れ替えを行なう。オーダリング部40は、第s回目1≦s≦uの行の入れ替えを表わす行列をPs、第s回目1≦s≦vの列の入れ替えを表わす行列をQsとして、以下のように新たな行列を生成する。B′=PuP2P1BQ1Q2QvD13A=PuP2P1AD14E=Q1Q2QvD15つまり、行列B′は、行列Bに対して、u回u≧1の行の入れ替え、およびv回v≧1の列の入れ替えを行なったものである。行列Aは、行列Aに対して、行列Bに対するu回の行の入れ替えと同様の入れ替えを行なったものである。行列Eは、単位行列Eに対して、行列Bに対するv回の列の入れ替えと同様の入れ替えを行なったものである。オーダリング部40は、行列A、Eを表わすデータを行列記憶部48に記憶させ、行列B′を表わすデータを中間結果記憶部42に記憶させるステップS702。次に、LU分解部34は、中間結果記憶部42から行列B′を表わすデータを読み出して、行列B′をLU分解して、下三角行列L′を表わすデータと、上三角行列U′を表わすデータとを中間結果記憶部42に記憶させるステップS703。次に、基本行列分解部36は、中間結果記憶部42から上三角行列U′を表わすデータを読み出して、上三角行列U′を基本上三角行列U′1、U′2、、U′mの積に分解して、基本上三角行列U′1、U′2、、U′mを表わすデータを中間結果記憶部42に記憶させる。また、基本行列分解部36は、中間結果記憶部42から下三角行列L′を表わすデータを読み出して、下三角行列Lを基本下三角行列L′1、L′2、、L′mの積に分解して、基本下三角行列L′1、L′2、、L′mを表わすデータを中間結果記憶部42に記憶させるステップS704。逆行列計算部43は、中間結果記憶部42から基本上三角行列U′1、U′2、、U′mおよび基本下三角行列L′1、L′2、、L′mを表わすデータを読み出して、行列U′1、U′2、、U′m、L′1、L′2、、L′mの非対角項の要素の符号を反転することによって、行列U′1、U′2、、U′m、L′1、L′2、、L′mの逆行列U′11、U′21、、U′m1、L′11、L′21、、L′m1を算出し、逆行列U′11、U′21、、U′m1、L′11、L′21、、L′m1を表わすデータを行列記憶部48に記憶させるステップS705。符号化ベクトル生成処理図13は、第2の実施形態の変形例1の符号化ベクトル生成処理のフローチャートである。図13を参照して、行列積計算制御部124は、行列記憶部48にデータが記憶されている行列の順序が先頭からA、L′11、L′21、、L′m1、U′m1、U′m11、、U′11、Eの順となるように行列間の順序を設定するステップS801。次に、行列積計算制御部124は、制御変数iを1に設定するステップS802。行列積計算制御部124は、行列積計算部41を指示して、行列記憶部48から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。行列積計算部41は、乗算結果であるベクトルを中間結果Rとし、中間結果Rを表わすデータを中間結果記憶部42に記憶させるステップS803。次に、行列積計算制御部124は、制御変数iをインクリメントするステップS804。行列積計算制御部124は、制御変数iが2m2未満の場合にはステップS805でYES、行列積計算部41を指示して、行列記憶部48から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部42に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部41は、乗算結果であるベクトルを新たな中間結果Rとし、中間結果記憶部42内の中間結果Rを表わすデータを更新するステップS806。その後、ステップS804からの処理が繰返される。制御変数iが2m2となった場合にはステップS805でNO、行列積計算制御部124は、行列積計算部41を指示して、行列記憶部48から第i順位の行列Matiを表わすデータを読み出させるとともに、中間結果記憶部42に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部41は、乗算結果であるベクトルY′を符号反転部99に出力する。符号反転部99は、ベクトルY′の符号を反転したものをパリティべクトルYとして出力するステップ807。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS808。第2の実施形態の変形例1の効果以上のように、第2の実施形態の変形例1によれば、符号化ベクトル生成処理時において、後退代入を行わずに、式E23に従ってパリティベクトルYを算出するので、少ない計算量で情報ベクトルXの符号化を行なうことができる。特に、行列Bがオーダリングされるため、基本上三角行列の逆行列U′i1および基本下三角行列の逆行列L′i1は、第1の実施形態の変形例1の基本上三角行列の逆行列Ui1および基本下三角行列の逆行列Li1よりもさらに非零要素数が少ない行列となり、式E23の演算の計算量を式C9よりもさらに少なくできる。また、式E23の右側にある行列乗算から順次実行してパリティベクトルYを算出するので、各行列乗算の結果はベクトルとなり、中間結果を記憶するための容量を小さくすることができる。また、行列分解処理時において、行列Bの逆行列を計算するという計算量の多い演算を行なうことなく、行列Bのオーダリングによる行列B′、A、Eの生成、行列B′のLU分解、LU分解された上三角行列の基本上三角行列の積への分解、LU分解された下三角行列の基本下三角行列の積への分解、基本上三角行列および基本下三角行列の非対角項の符号の反転を行なえばよいので、少ない計算量でパリティベクトルYを生成するのに必要な行列を算出することができる。[第3の実施形態]第3の実施形態の符号化器は、2を法とする演算を行なう。符号化アルゴリズム符号化器は、k個の情報ビットx1、x2、、xkからなる情報ベクトルXを受けて、2を法とする演算を行なうことによって、以下の式を満たすようなm個のパリティビットy1、y2、、ymからなるパリティベクトルYを生成する。HX,YT=0F1ここで、Hはパリティ検査行列以下、検査行列とも言うであり、m行n列=kmの行列である。X,YTは、情報ベクトルとパリティベクトルからなるベクトルの転置を表わす。式F1は、2を法とする演算の場合には、次のように変形される。BY≡AXF2ここで、行列Aは、検査行列Hの第1列目~第k列目からなるm行k列の行列である。行列Bは、検査行列Hの第k1列目~第n列目からなるm行m列の行列である。行列BをLU分解すると、式F2は以下の式に変形される。LUY≡AXF3ここで、Lは下三角行列であり、Uは上三角行列である。式F3より、列ベクトルYは、以下の式で表わされる。Y≡U1L1AXF4上三角行列Uは、以下の式のように、基本上三角行列Uii=1~mの積に分解される。U≡UmUm1U2U1F5式F5より、逆行列U1は、以下の式で表わされる。U1≡U11U21Um11Um1F6下三角行列Lは、以下の式のように、基本下三角行列Lii=1~mの積に分解される。L≡L1L2Lm1LmF7式F7より、逆行列L1は、以下の式で表わされる。L1≡Lm1Lm11L21L11F8式F6および式F8によって、式F4は以下の式に変形される。Y≡U11U21Um11Um1Lm1Lm11L21L11AXF9ところで、2を法とする演算の場合には、基本上三角行列Ui、基本下三角行列Liは、以下のような性質を有する。Ui≡Ui1F10Li≡Li1F11式F10および式F11によって、式F9は以下の式に変形される。Y≡U1U2Um1UmLmLm1L2L1AXF12式F12は、2×m2個の行列の乗算であるが、一定の条件を満足する場合には、いくつかの行列の積を1つの行列で表わすことができるとする。以下の式のように、U1~Utのt個の行列の積を1つの行列Cで表わすことができるとする。U1U2Ut≡CF13この場合、一定の条件とは、行列U1、U2、、Utの非対角項の非零要素の個数の和が行列Cの非対角項の非零要素の個数以上であるものとする。式F13より、式F12は以下の式で表わされる。Y≡CUt1Um1UmLmLm1L2L1AXF14式F14で算出されるパリティベクトルYと、情報ベクトルXを用いて、符号化ベクトルZは、以下の式で表わされる。Z≡X,YF15ここで、符号化ベクトルZの第1ビット~第kビットは、情報ベクトルXのビットであり、符号化ベクトルZの第k1ビット~第nビットは、パリティベクトルYのビットである。構成図14は、第3の実施形態の符号化器の構成を表わす図である。図14を参照して、この符号化器2eは、第1の実施形態と同様の、検査行列分解部30と、LU分解部14と、基本行列分解部16と、配列部20とを備える。これらについては説明を繰返さない。また、符号化器2eは、中間結果記憶部52と、行列記憶部58と、行列積計算部51と、行列積計算制御部125と、行列乗算数削減部55とを備える。なお、以下では、t1<mとして説明する。中間結果記憶部52は、式F14に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部52は、パリティベクトルYの生成処理時に、式F14に含まれる2m-t2回の行列乗算の中間結果を表わすデータを記憶する。行列記憶部58は、基本上三角行列Ut1、Ut2、、Umを表わすデータ、基本下三角行列Lm、Lm1、、L1を表わすデータ、および行列Aを表わすデータを記憶する。行列積計算部51は、加算器57および乗算器59を備える。行列積計算部51は、パリティベクトルYを算出するために、式F14に含まれる2m-t2回の行列乗算を行列積計算制御部125に指示された順序で実行する。行列積計算部51は、入力される情報ベクトルX、行列記憶部58内の行列A、L1、L2、、Lm1、Lm、Um、Um1、、Ut1、Cを表わすデータ、および中間結果記憶部52内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行する。行列積計算部51は、式F14に含まれる2m-t2回の行列乗算が終了するまでの間は、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部52に記憶させる。また、行列積計算部51は、式F12に含まれる行列乗算の個数を削減する処理を実行するときに、行列乗算数削減部55から指示された行列乗算を実行する。行列乗算数削減部55は、式F12に含まれる行列乗算の個数を削減する処理を行なうときに、中間結果記憶部52にデータが記憶されている行列の順序が先頭からU1、U2、、Um1、Um、Lm、Lm1、、L2、L1、Aの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部51を制御する。行列乗算数削減部55は、各乗算において、乗算の対象となる2つの行列の非対角項の非零要素数と、乗算結果である1つの行列Cの非対角項の非零要素数とを比較し、後者と前者の差が所定の閾値aa>0以下のときは、乗算対象の2つの行列を1つの行列Cで置換する。このようにして行列Cで置換された場合は、行列Cと次の行列との乗算が行なわれる。一方、行列乗算数削減部55は、後者と前者の差が所定の閾値aを超えるときには、乗算対象の2つの行列を1つの行列Cで置換することを行なわずに、行列A、L1、L2、、Lm1、Lm、Um、Um1、、U1の非対角項の非零要素数の総和と、行列A、L1、L2、、Lm1、Lm、Um、Um1、、U1のうちの置換が行なわれた行列を除いた行列と行列Cの非対角項の非零要素数の総和とを比較し、後者の値が前者の値以下の場合には、行列A、L1、L2、、Lm1、Lm、Um、Um1、、U1のうちの置換された行列を除いた行列と行列Cとを行列記憶部58に記憶させる。第t順位までの行列が置換された場合には、行列C、Ut1、、Um1、Um、Lm、Lm1、、L2、L1、Aが行列記憶部58に記憶される。行列積計算制御部125は、パリティベクトルYを算出するために、行列記憶部58にデータが記憶されている行列の順序が先頭からA、L1、L2、、Lm1、Lm、Um、Um1、、Ut1、Cの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部51を制御する。また、行列積計算制御部125は、式F14に含まれる2m-t2回の行列乗算の終了後に、行列積計算部51から計算結果であるパリティベクトルYを出力させる。行列分解処理図15は、第3の実施形態の行列分解処理のフローチャートである。図15を参照して、まず、第1の実施形態のステップS101~ステップS103が検査行列分解部30、行列記憶部58、中間結果記憶部52、LU分解部14、および基本行列分解部16によって実行される。ただし、生成された行列U1、U2、、Um1、Um、Lm、Lm1、、L2、L1、Aは、第1の実施形態のように行列記憶部58にではなく、中間結果記憶部52に記憶される。ステップS901。次に、行列乗算数削減部55は、中間結果記憶部52にデータが記憶されている行列について、先頭からU1、U2、、Um1、Um、Lm、Lm1、、L2、L1、Aの順となるように順序を設定するステップS902。次に、行列乗算数削減部55は、制御変数tを1に設定するステップS903。次に、行列乗算数削減部55は、行列記憶部58から第t=1順位の行列U1を表わすデータを読み出して、行列U1を行列Cとして、行列Cを表わすデータを中間結果記憶部52に記憶するステップS904。行列数積削減部は、中間結果記憶部52から行列Cを表わすデータを読み出して、行列Cの非零要素数SC0をカウントし、非零要素数SC0を中間結果記憶部52に記憶させるステップS905。次に、行列乗算数削減部55は、第t1順位の行列を表わすデータを読み出して、その行列を行列matとするステップS906。次に、行列乗算数削減部55は、行列matの非対角項の非零要素数SC1をカウントし、非零要素数SC1と中間結果記憶部52内の行列Cの非零要素数SC0との和SC2を算出して、非零要素数の和SC2を中間結果記憶部52に記憶させるステップS907。次に、行列積計算部51は、行列Cと行列Matとの積C×Matを計算して、計算結果を行列DとするステップS908。次に、行列乗算数削減部55は、行列Dの非対角項の非零要素数SC3をカウントし、非零要素数SC3を中間結果記憶部52に記憶させるステップS909。行列乗算数削減部55は、中間結果記憶部52から非零要素数の和SC2および非零要素数SC3とを読み出して、SC3とSC2との差が閾値a以下であるかを判断するステップS910。行列乗算数削減部55は、SC3とSC2との差が閾値a以下である場合にはステップS910でYES、制御変数tをインクリメントしステップS911、中間結果記憶部52内の行列Cを行列Dで更新しステップS912、さらに中間結果記憶部52内の非零要素数SC0を非零要素数SC3を更新し、ステップS906からの処理が繰返させる。一方、行列乗算数削減部55は、SC3とSC2との差が閾値aを超えステップS910でNO、かつ制御変数tが2以上の場合にはステップS914でYES、行列記憶部58にデータが記憶されている行列U1、U2、、Um1、Um、Lm、Lm1、、L2、L1、Aのそれぞれについて非対角項の非零要素数をカウントし、それらの非零要素数の総和SC4を中間結果記憶部52に記憶させるステップS915。次に、行列乗算数削減部55は、行列U1、U2、、Um1、Um、Lm、Lm1、、L2、L1、Aのうちの第t1順位以降の行列のそれぞれについて非対角項の非零要素数をカウントし、それらの非零要素数の総和SC5と中間結果記憶部52内の行列Cの非零要素数SC0との総和SC6を算出して、非零要素数の総和SC6を中間結果記憶部52に記憶させるステップS916。行列乗算数削減部55は、中間結果記憶部52から非零要素数の総和SC4および非零要素数の総和SC6とを読み出して、SC6がSC4以下であるかを判断するステップS917。行列乗算数削減部55は、SC6がSC4以下である場合にはステップS917でYES、中間結果記憶部52内の行列U1、U2、、Um1、Um、Lm、Lm1、、L2、L1、Aのうちの第1順位から第t順位までの行列を除いた行列Ut1、Ut2、、Um1、Um、Lm、Lm1、、L2、L1、Aと、行列Cとを行列記憶部58に記憶させるステップS918。符号化ベクトル生成処理図16は、第3の実施形態の符号化ベクトル生成処理のフローチャートである。図16を参照して、行列積計算制御部125は、行列記憶部58にデータが記憶されている行列の順序が先頭からA、L1、L2、、Lm1、Lm、Um、Um1、、Ut1、Cの順となるように行列間の順序を設定するステップS1001。次に、行列積計算制御部125は、制御変数iを1に設定するステップS1002。行列積計算制御部125は、行列積計算部51を指示して、行列記憶部58から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。行列積計算部51は、乗算結果であるベクトルを中間結果Rとし、中間結果Rを表わすデータを中間結果記憶部52に記憶させるステップS1003。次に、行列積計算制御部125は、制御変数iをインクリメントするステップS1004。行列積計算制御部125は、制御変数iが2m-t2未満の場合にはステップS1005でYES、行列積計算部51を指示して、行列記憶部58から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部52に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部51は、乗算結果であるベクトルを新たな中間結果Rとし、中間結果記憶部52内の中間結果Rを表わすデータを更新するステップS1006。その後、ステップS1004からの処理が繰返される。制御変数iが2m-t2となった場合にはステップS1005でNO、行列積計算制御部125は、行列積計算部51を指示して、行列記憶部58から第i順位の行列Matiを表わすデータを読み出させるとともに、中間結果記憶部52に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部51は、乗算結果であるベクトルをパリティべクトルYとして出力するステップS1007。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS1008。第3の実施形態の効果以上のように、第3の実施形態によれば、符号化ベクトル生成処理時において、後退代入を行わずに、式F14に従ってパリティベクトルYを算出するので、少ない計算量で情報ベクトルXの符号化を行なうことができる。特に、基本上三角行列Uiおよび基本下三角行列Liは非零要素数が少ない行列のため、式F14の計算量は少ない。式F14では、第1の実施形態の式B12のU1~Utが1つの行列Cで表わされ、しかも行列Cの非対角項の非零要素数が行列U1~Utの非対角項の非零要素数の和以下であるため、式F14の演算は、第1の実施形態の式B12の演算よりもさらに計算量が少ない。また、式F14の右側にある行列乗算から順次実行してパリティベクトルYを算出するので、各行列乗算の結果はベクトルとなり、中間結果を記憶するための容量を小さくすることができる。また、行列分解処理時において、行列Bの逆行列を計算するという計算量の多い演算を行なうことなく、行列BのLU分解、LU分解された上三角行列の基本上三角行列の積への分解、LU分解された下三角行列の基本下三角行列の積への分解、行列乗算数の削減処理を行なえばよいので、少ない計算量でパリティベクトルYを生成するのに必要な行列を算出することができる。[第3の実施形態の変形例1]第3の実施形態の変形例1の符号化器は、実数演算を行なう。符号化アルゴリズム符号化器は、k個の情報ビットx1、x2、、xkからなる情報ベクトルXを受けて、実数演算を行なうことによって、以下の式を満たすようなm個のパリティビットy1、y2、、ymからなるパリティベクトルYを生成する。HX,YT=0G1ここで、Hはパリティ検査行列以下、検査行列とも言うであり、m行n列=kmの行列である。X,YTは、情報ベクトルとパリティベクトルからなるベクトルの転置を表わす。式G1は、実数演算の場合には、次のように変形される。BY=-AXG2ここで、行列Aは、検査行列Hの第1列目~第k列目からなるm行k列の行列である。行列Bは、検査行列Hの第k1列目~第n列目からなるm行m列の行列である。行列BをLU分解すると、式G2は以下の式に変形される。LUY=-AXG3ここで、Lは下三角行列であり、Uは上三角行列である。式G3より、列ベクトルYは、以下の式で表わされる。Y=-U1L1AXG4上三角行列Uは、以下の式のように、基本上三角行列Uii=1~mの積に分解される。U=UmUm1U2U1G5式G5より、U1は、以下の式で表わされる。U1=U11U21Um11Um1G6ここで、Ui1は、対角項の要素が1であり、かつ非対角項の要素はUiの要素の符号を反転したものである。下三角行列Lは、以下の式のように、基本下三角行列Lii=1~mの積に分解される。L=L1L2Lm1LmG7式G7より、L1は、以下の式で表わされる。L1=Lm1Lm11L21L11G8ここで、Li1は、対角項の要素が1であり、かつ非対角項の要素はLiの要素の符号を反転したものである。式G6および式G8によって、式G4は以下の式に変形される。Y=-U11U21Um11Um1Lm1Lm11L21L11AXG9式G9は、2×m2個の行列の乗算であるが、一定の条件を満足する場合には、いくつかの行列の積を1つの行列で表わすことができるとする。以下の式のように、U11~Ut1のt個の行列の積を1つの行列Cで表わすことができるとする。U11U21Ut1≡CG10この場合、一定の条件とは、行列U11、U21、、Ut1の非対角項の非零要素の個数の和が行列Cの非対角項の非零要素の個数以上であるものとする。式G10より、式G9は以下の式で表わされる。Y=-CUt11Um11Um1Lm1Lm11L21L11AXG11式G11で算出されるパリティベクトルYと、情報ベクトルXを用いて、符号化ベクトルZは、以下の式で表わされる。Z=X,YG12ここで、符号化ベクトルZの第1ビット~第kビットは、情報ベクトルXのビットであり、符号化ベクトルZの第k1ビット~第nビットは、パリティベクトルYのビットである。構成図17は、第3の実施形態の変形例1の符号化器の構成を表わす図である。図17を参照して、この符号化器2fは、第1の実施形態の変形例1と同様の、検査行列分解部30と、LU分解部14と、基本行列分解部16と、逆行列計算部23と、配列部20とを備える。これらについては説明を繰返さない。また、符号化器2fは、中間結果記憶部62と、行列記憶部68と、行列積計算部61と、行列積計算制御部126と、行列乗算数削減部65とを備える。なお、以下では、t1<mとして説明する。中間結果記憶部62は、式G11に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部62は、パリティベクトルYの生成処理時に、式G11に含まれる2m-t2回の行列乗算の中間結果を表わすデータを記憶する。行列記憶部68は、基本上三角行列の逆行列Ut11、Ut21、、Um1を表わすデータ、基本下三角行列の逆行列Lm1、Lm11、、L11を表わすデータ、および行列Aを表わすデータを記憶する。行列積計算部61は、加算器67および乗算器69を備える。行列積計算部61は、パリティベクトルYを算出するために、式G11に含まれる2m-t2回の行列乗算を行列積計算制御部126に指示された順序で実行する。行列積計算部61は、入力される情報ベクトルX、行列記憶部68内の行列A、L11、L21、、Lm11、Lm1、Um1、Um11、、Ut11、Cを表わすデータ、および中間結果記憶部62内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行する。行列積計算部61は、式G11に含まれる2m-t2回の行列乗算が終了するまでの間は、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部62に記憶させる。また、行列積計算部61は、式G9に含まれる行列乗算の個数を削減する処理を実行するときに、行列乗算数削減部65から指示された行列乗算を実行する。行列乗算数削減部65は、式G9に含まれる行列乗算の個数を削減する処理を行なうときに、中間結果記憶部62にデータが記憶されている行列の順序が先頭からU11、U21、、Um11、Um1、Lm1、Lm11、、L21、L11、Aの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部61を制御する。行列乗算数削減部65は、各乗算において、乗算の対象となる2つの行列の非対角項の非零要素数と、乗算結果である1つの行列Cの非対角項の非零要素数とを比較し、後者と前者の差が所定の閾値aa>0以下のときは、乗算対象の2つの行列を1つの行列Cで置換する。このようにして行列Cで置換された場合は、行列Cと次の行列との乗算が行なわれる。一方、行列乗算数削減部65は、後者と前者の差が所定の閾値aを超えるときには、乗算対象の2つの行列を1つの行列Cで置換することを行なわずに、行列A、L11、L21、、Lm11、Lm1、Um1、Um11、、U11の非対角項の非零要素数の総和と、行列A、L11、L21、、Lm11、Lm1、Um1、Um11、、U11のうちの置換が行なわれた行列を除いた行列と行列Cの非対角項の非零要素数の総和とを比較し、後者の値が前者の値以下の場合には、行列A、L11、L21、、Lm11、Lm1、Um1、Um11、、U11のうちの置換された行列を除いた行列と行列Cとを行列記憶部68に記憶させる。第t順位までの行列が置換された場合には、行列C、Ut11、、Um11、Um1、Lm1、Lm11、、L21、L11、Aが行列記憶部68に記憶される。行列積計算制御部126は、パリティベクトルYを算出するために、行列記憶部68にデータが記憶されている行列の順序が先頭からA、L11、L21、、Lm11、Lm1、Um1、Um11、、Ut11、Cの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部61を制御する。また、行列積計算制御部126は、式G11に含まれる2m-t2回の行列乗算の終了後に、行列積計算部61から計算結果であるベクトルY′=CUt11Um11Um1Lm1Lm11L21L11AXを符号反転部99へ出力させる。行列分解処理図18は、第3の実施形態の変形例1の行列分解処理のフローチャートである。図18を参照して、まず、第1の実施形態の変形例1のステップS201~ステップS204が検査行列分解部30、行列記憶部68、中間結果記憶部62、LU分解部14、基本行列分解部16、および逆行列計算部23によって実行される。ただし、生成された行列U11、U21、、Um11、Um1、Lm1、Lm11、、L21、L11、Aは、第1の実施形態の変形例1のように行列記憶部68にではなく、中間結果記憶部62に記憶される。ステップS1101。次に、行列乗算数削減部65は、中間結果記憶部62にデータが記憶されている行列について、先頭からU11、U21、、Um11、Um1、Lm1、Lm11、、L21、L11、Aの順となるように順序を設定するステップS1102。次に、行列乗算数削減部65は、制御変数tを1に設定するステップS1103。次に、行列乗算数削減部65は、行列記憶部68から第t=1順位の行列U11を表わすデータを読み出して、行列U11を行列Cとして、行列Cを表わすデータを中間結果記憶部62に記憶するステップS1104。行列数積削減部は、中間結果記憶部62から行列Cを表わすデータを読み出して、行列Cの非零要素数SC0をカウントし、非零要素数SC0を中間結果記憶部62に記憶させるステップS1105。次に、行列乗算数削減部65は、第t1順位の行列を表わすデータを読み出して、その行列を行列matとするステップS1106。次に、行列乗算数削減部65は、行列matの非対角項の非零要素数SC1をカウントし、非零要素数SC1と中間結果記憶部62内の行列Cの非零要素数SC0との和SC2を算出して、非零要素数の和SC2を中間結果記憶部62に記憶させるステップS1107。次に、行列積計算部61は、行列Cと行列Matとの積C×Matを計算して、計算結果を行列DとするステップS1108。次に、行列乗算数削減部65は、行列Dの非対角項の非零要素数SC3をカウントし、非零要素数SC3を中間結果記憶部62に記憶させるステップS1109。行列乗算数削減部65は、中間結果記憶部62から非零要素数の和SC2および非零要素数SC3とを読み出して、SC3とSC2との差が閾値a以下であるかを判断するステップS1110。行列乗算数削減部65は、SC3とSC2との差が閾値a以下である場合にはステップS1110でYES、制御変数tをインクリメントしステップS1111、中間結果記憶部62内の行列Cを行列Dで更新しステップS1112、さらに中間結果記憶部62内の非零要素数SC0を非零要素数SC3を更新し、ステップS1106からの処理が繰返させる。一方、行列乗算数削減部65は、SC3とSC2との差が閾値aを超えステップS1110でNO、かつ制御変数tが2以上の場合にはステップS1114でYES、行列記憶部68にデータが記憶されている行列U11、U21、、Um11、Um1、Lm1、Lm11、、L21、L11、Aのそれぞれについて非対角項の非零要素数をカウントし、それらの非零要素数の総和SC4を中間結果記憶部62に記憶させるステップS1115。次に、行列乗算数削減部65は、行列U11、U21、、Um11、Um1、Lm1、Lm11、、L21、L11、Aのうちの第t1順位以降の行列のそれぞれについて非対角項の非零要素数をカウントし、それらの非零要素数の総和SC5と中間結果記憶部62内の行列Cの非零要素数SC0との総和SC6を算出して、非零要素数の総和SC6を中間結果記憶部62に記憶させるステップS1116。行列乗算数削減部65は、中間結果記憶部62から非零要素数の総和SC4および非零要素数の総和SC6とを読み出して、SC6がSC4以下であるかを判断するステップS1117。行列乗算数削減部65は、SC6がSC4以下である場合にはステップS1117でYES、中間結果記憶部62内の行列U11、U21、、Um11、Um1、Lm1、Lm11、、L21、L11、Aのうちの第1順位から第t順位までの行列を除いた行列Ut11、Ut21、、Um11、Um1、Lm1、Lm11、、L21、L11、Aと、行列Cとを行列記憶部68に記憶させるステップS1118。符号化ベクトル生成処理図19は、第3の実施形態の変形例1の符号化ベクトル生成処理のフローチャートである。図19を参照して、行列積計算制御部126は、行列記憶部68にデータが記憶されている行列の順序が先頭からA、L11、L21、、Lm11、Lm1、Um1、Um11、、Ut11、Cの順となるように行列間の順序を設定するステップS1201。次に、行列積計算制御部126は、制御変数iを1に設定するステップS1202。行列積計算制御部126は、行列積計算部61を指示して、行列記憶部68から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。行列積計算部61は、乗算結果であるベクトルを中間結果Rとし、中間結果Rを表わすデータを中間結果記憶部62に記憶させるステップS1203。次に、行列積計算制御部126は、制御変数iをインクリメントするステップS1204。行列積計算制御部126は、制御変数iが2m-t2未満の場合にはステップS1205でYES、行列積計算部61を指示して、行列記憶部68から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部62に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部61は、乗算結果であるベクトルを新たな中間結果Rとし、中間結果記憶部62内の中間結果Rを表わすデータを更新するステップS1206。その後、ステップS1204からの処理が繰返される。制御変数iが2m-t2となった場合にはステップS1205でNO、行列積計算制御部126は、行列積計算部61を指示して、行列記憶部68から第i順位の行列Matiを表わすデータを読み出させるとともに、中間結果記憶部62に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部61は、乗算結果であるベクトルY′を符号反転部99に出力する。符号反転部99は、ベクトルY′の符号を反転したものをパリティべクトルYとして出力するステップS1207。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS1208。第3の実施形態の変形例1の効果以上のように、第3の実施形態の変形例1によれば、符号化ベクトル生成処理時において、後退代入を行わずに、式G11に従ってパリティベクトルYを算出するので、少ない計算量で情報ベクトルXの符号化を行なうことができる。特に、基本上三角行列の逆行列Ui1および基本下三角行列の逆行列Li1は非零要素数が少ない行列のため、式G11の計算量は少ない。式G11では、第1の実施形態の変形例1の式C9のU11~Ut1が1つの行列Cで表わされ、しかも行列Cの非対角項の非零要素数が行列U11~Ut1の非対角項の非零要素数の和以下であるため、式G11の演算は、第1の実施形態の変形例1の式C9の演算よりもさらに計算量が少ない。また、式G11の右側にある行列乗算から順次実行してパリティベクトルYを算出するので、各行列乗算の結果はベクトルとなり、中間結果を記憶するための容量を小さくすることができる。また、行列分解処理時において、行列Bの逆行列を計算するという計算量の多い演算を行なうことなく、行列BのLU分解、LU分解された上三角行列の基本上三角行列の積への分解、LU分解された下三角行列の基本下三角行列の積への分解、基本上三角行列および基本下三角行列の非対角項の符号の反転、行列乗算数の削減処理を行なえばよいので、少ない計算量でパリティベクトルYを生成するのに必要な行列を算出することができる。[第4の実施形態]第4の実施形態の符号化器は、2を法とする演算を行なう。符号化アルゴリズム符号化器は、k個の情報ビットx1、x2、、xkからなる情報ベクトルXを受けて、2を法とする演算を行なうことによって、以下の式を満たすようなm個のパリティビットy1、y2、、ymからなるパリティベクトルYを生成する。HX,YT≡0H1ここで、Hはパリティ検査行列以下、検査行列とも言うであり、m行n列=kmの行列である。X,YTは、情報ベクトルとパリティベクトルからなるベクトルの転置を表わす。式H1は、2を法とする演算の場合には、次のように変形される。BY≡AXH2ここで、行列Aは、検査行列Hの第1列目~第k列目からなるm行k列の行列である。行列Bは、検査行列Hの第k1列目~第n列目からなるm行m列の行列である。行列Bに対して、以下のようにオーダリングを行なうとする。まず、行列Bの2つの行を交換するとすると、式H2は以下のように変形される。P1BY≡P1AXH3ここで、P1は、第1回目の行の入れ替えを表わす変換行列である。i行とj行を変換する場合には、P1は、単位行列Eのi行とj行を入れ替えた行列となる。さらに、行列Bの2つの列を交換すると、式H3は以下のように変形される。P1BQ1Q11Y≡P1AXH4ここで、Q1は、第1回目の列の入れ替えを表わす変換行列である。i列とj列を変換する場合には、Q1は、単位行列Eのi列とj列を入れ替えた行列となる。以下のように新たな行列を定義する。B≡P1BQ1H5A≡P1AH6式H5および式H6により、式H4は以下の式で表わされる。BQ11Y≡AXH7さらに、行列Bの2つの行を交換するとすると、式H7は以下のように変形される。P2BQ11Y≡P2AXH8ここで、P2は、第2回目の行の入れ替えを表わす変換行列である。さらに、行列Bの2つの列を交換すると、式H8は以下のように変形される。P2BQ2Q21Q11Y≡P2AXH9ここで、Q2は、第2回目の列の入れ替えを表わす変換行列である。以下のように新たな行列を定義する。B≡P2BQ2H10A≡P2AH11式H10および式H11により、式H9は以下の式で表わされる。BQ21Q11Y≡AXH12同様にして、行列Bに対して、第u回u≧1だけ行の入れ替えおよび第vv≧1だげ列の入れ替えを行なう。第s回目1≦s≦uの行の入れ替えを表わす行列をPs、第s回目1≦s≦vの列の入れ替えを表わす行列をQsとして、以下のように新たな行列を定義する。B′≡PuP2P1BQ1Q2QvH13A≡PuP2P1AH14E≡Q1Q2QvH15式H13、式H14および式H15により、以下の式が成り立つ。B′E1Y≡AXH16行列B′をLU分解すると、式H16は以下の式に変形される。L′U′E1Y≡AXH17ここで、L′は下三角行列であり、U′は上三角行列である。式H17より、列ベクトルYは、以下の式で表わされる。Y≡EU′1L′1AXH18上三角行列U′は、以下の式のように、基本上三角行列U′ii=1~mの積に分解される。U′≡U′mU′m1U′2U′1H19式H19より、U′1は、以下の式で表わされる。U′1≡U′11U′21U′m11U′m1H20下三角行列L′は、以下の式のように、基本下三角行列L′ii=1~mの積に分解される。L′≡L′1L′2L′m1L′mH21式H21より、L′1は、以下の式で表わされる。L′1≡L′m1L′m11L′21L′11H22式H20および式H22によって、式H18は以下の式に変形される。Y≡EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXH23ところで、2を法とする演算の場合には、基本上三角行列U′i、基本下三角行列L′iは、以下のような性質を有する。U′i≡U′i1H24L′i≡L′i1H25式H24および式H25によって、式H23は以下の式に変形される。Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXH26式H26は、2×m3個の行列の乗算であるが、一定の条件を満足する場合には、いくつかの行列の積を1つの行列で表わすことができるとする。以下の式のように、E、U′1~U′t1のt個の行列の積を1つの行列Cで表わすことができるとする。EU′1U′2U′t1≡CH27この場合、一定の条件とは、行列E、U′1、U′2、、U′t1の非対角項の非零要素の個数の和が行列Cの非対角項の非零要素の個数以上であるものとする。式H27より、式H26は以下の式で表わされる。Y≡CU′tU′m1U′mL′mL′m1L′2L′1AXH28式H28で算出されるパリティベクトルYと、情報ベクトルXを用いて、符号化ベクトルZは、以下の式で表わされる。Z≡X,YH29ここで、符号化ベクトルZの第1ビット~第kビットは、情報ベクトルXのビットであり、符号化ベクトルZの第k1ビット~第nビットは、パリティベクトルYのビットである。構成図20は、第4の実施形態の符号化器の構成を表わす図である。図20を参照して、この符号化器2gは、第2の実施形態と同様の、検査行列分解部30と、オーダリング部40と、LU分解部34と、基本行列分解部36と、配列部20とを備える。これらについては説明を繰返さない。また、符号化器2gは、中間結果記憶部72と、行列記憶部78と、行列積計算部71と、行列積計算制御部127と、行列乗算数削減部75とを備える。なお、以下では、t<mとして説明する。中間結果記憶部72は、式H28に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部72は、パリティベクトルYの生成処理時に、式H28に含まれる2m-t3回の行列乗算の中間結果を表わすデータを記憶する。行列記憶部78は、基本上三角行列U′t、U′t1、、U′mを表わすデータ、基本下三角行列L′m、L′m1、、L′1を表わすデータ、および行列C、Aを表わすデータを記憶する。行列積計算部71は、加算器77および乗算器79を備える。行列積計算部71は、パリティベクトルYを算出するために、式H28に含まれる2m-t3回の行列乗算を行列積計算制御部127に指示された順序で実行する。行列積計算部71は、入力される情報ベクトルX、行列記憶部78内の行列A、L′1、L′2、、L′m1、L′m、U′m、U′m1、、U′t、Cを表わすデータ、および中間結果記憶部72内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行する。行列積計算部71は、式H28に含まれる2m-t3回の行列乗算が終了するまでの間は、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部72に記憶させる。また、行列積計算部71は、式H26に含まれる行列乗算の個数を削減する処理を実行するときに、行列乗算数削減部75から指示された行列乗算を実行する。行列乗算数削減部75は、式H26に含まれる行列乗算の個数を削減する処理を行なうときに、中間結果記憶部72にデータが記憶されている行列の順序が先頭からE、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部71を制御する。行列乗算数削減部75は、各乗算において、乗算の対象となる2つの行列の非対角項の非零要素数と、乗算結果である1つの行列Cの非対角項の非零要素数とを比較し、後者と前者の差が所定の閾値aa>0以下のときは、乗算対象の2つの行列を1つの行列Cで置換する。このようにして行列Cで置換された場合は、行列Cと次の行列との乗算が行なわれる。一方、行列乗算数削減部75は、後者と前者の差が所定の閾値aを超えるときには、乗算対象の2つの行列を1つの行列Cで置換することを行なわずに、行列E、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aの非対角項の非零要素数の総和と、行列E、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aのうちの置換が行なわれた行列を除いた行列と行列Cの非対角項の非零要素数の総和とを比較し、後者の値が前者の値以下の場合には、行列E、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aのうちの置換された行列を除いた行列と行列Cとを行列記憶部78に記憶させる。第t順位までの行列が置換された場合には、行列C、U′t、U′t1、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aが行列記憶部78に記憶される。行列積計算制御部127は、パリティベクトルYを算出するために、行列記憶部78にデータが記憶されている行列の順序が先頭からA、L′1、L′2、、L′m1、L′m、U′m、U′m1、、U′t、Cの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部71を制御する。また、行列積計算制御部127は、式H28に含まれる2m-t3回の行列乗算の終了後に、行列積計算部71から計算結果であるパリティベクトルYを出力させる。行列分解処理図21、第4の実施形態の行列分解処理のフローチャートである。図21を参照して、第2の実施形態のステップS501~ステップS504が検査行列分解部30、行列記憶部78、中間結果記憶部72、オーダリング部40、LU分解部34、および基本行列分解部36によって実行される。ただし、生成された行列E、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aは、第2の実施形態のように行列記憶部78にではなく、中間結果記憶部72に記憶される。ステップS1301。次に、行列乗算数削減部75は、中間結果記憶部72にデータが記憶されている行列について、先頭からE、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aの順となるように順序を設定するステップS1302。次に、行列乗算数削減部75は、制御変数tを1に設定するステップS1303。次に、行列乗算数削減部75は、行列記憶部78から第t=1順位の行列Eを表わすデータを読み出して、行列Eを行列Cとして、行列Cを表わすデータを中間結果記憶部72に記憶するステップS1304。行列数積削減部は、中間結果記憶部72から行列Cを表わすデータを読み出して、行列Cの非零要素数SC0をカウントし、非零要素数SC0を中間結果記憶部72に記憶させるステップS1305。次に、行列乗算数削減部75は、第t1順位の行列を表わすデータを読み出して、その行列を行列matとするステップS1306。次に、行列乗算数削減部75は、行列matの非対角項の非零要素数SC1をカウントし、非零要素数SC1と中間結果記憶部72内の行列Cの非零要素数SC0との和SC2を算出して、非零要素数の和SC2を中間結果記憶部72に記憶させるステップS1307。次に、行列積計算部71は、行列Cと行列Matとの積C×Matを計算して、計算結果を行列DとするステップS1308。次に、行列乗算数削減部75は、行列Dの非対角項の非零要素数SC3をカウントし、非零要素数SC3を中間結果記憶部72に記憶させるステップS1309。行列乗算数削減部75は、中間結果記憶部72から非零要素数の和SC2および非零要素数SC3とを読み出して、SC3とSC2との差が閾値a以下であるかを判断するステップS1310。行列乗算数削減部75は、SC3とSC2との差が閾値a以下である場合にはステップS1310でYES、制御変数tをインクリメントしステップS1311、中間結果記憶部72内の行列Cを行列Dで更新しステップS1312、さらに中間結果記憶部72内の非零要素数SC0を非零要素数SC3を更新し、ステップS1306からの処理が繰返させる。一方、行列乗算数削減部75は、SC3とSC2との差が閾値aを超えステップS1310でNO、かつ制御変数tが2以上の場合にはステップS1314でYES、行列記憶部78にデータが記憶されている行列E、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aのそれぞれについて非対角項の非零要素数をカウントし、それらの非零要素数の総和SC4を中間結果記憶部72に記憶させるステップS1315。次に、行列乗算数削減部75は、行列E、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aのうちの第t1順位以降の行列のそれぞれについて非対角項の非零要素数をカウントし、それらの非零要素数の総和SC5と中間結果記憶部72内の行列Cの非零要素数SC0との総和SC6を算出して、非零要素数の総和SC6を中間結果記憶部72に記憶させるステップS1316。行列乗算数削減部75は、中間結果記憶部72から非零要素数の総和SC4および非零要素数の総和SC6とを読み出して、SC6がSC4以下であるかを判断するステップS1317。行列乗算数削減部75は、SC6がSC4以下である場合にはステップS1317でYES、中間結果記憶部72内の行列E、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aのうちの第1順位から第t順位までの行列を除いた行列U′t、U′t1、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aと、行列Cとを行列記憶部78に記憶させるステップS1318。符号化ベクトル生成処理図22は、第4の実施形態の符号化ベクトル生成処理のフローチャートである。図22を参照して、行列積計算制御部127は、行列記憶部78にデータが記憶されている行列の順序が先頭からA、L′1、L′2、、L′m、U′m、U′m1、、U′t、Cの順となるように行列間の順序を設定するステップS1401。次に、行列積計算制御部127は、制御変数iを1に設定するステップS1402。行列積計算制御部127は、行列積計算部71を指示して、行列記憶部78から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。行列積計算部71は、乗算結果であるベクトルを中間結果Rとし、中間結果Rを表わすデータを中間結果記憶部72に記憶させるステップS1403。次に、行列積計算制御部127は、制御変数iをインクリメントするステップS1404。行列積計算制御部127は、制御変数iが2m-t3未満の場合にはステップS1405でYES、行列積計算部71を指示して、行列記憶部78から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部72に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部71は、乗算結果であるベクトルを新たな中間結果Rとし、中間結果記憶部72内の中間結果Rを表わすデータを更新するステップS1406。その後、ステップS1404からの処理が繰返される。制御変数iが2m-t3となった場合にはステップS1405でNO、行列積計算制御部127は、行列積計算部71を指示して、行列記憶部78から第i順位の行列Matiを表わすデータを読み出させるとともに、中間結果記憶部72に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部71は、乗算結果であるベクトルをパリティべクトルYとして出力するステップS1407。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS1408。第4の実施形態の効果以上のように、第4の実施形態によれば、符号化ベクトル生成処理時において、後退代入を行わずに、式H28に従ってパリティベクトルYを算出するので、少ない計算量で情報ベクトルXの符号化を行なうことができる。特に、行列Bがオーダリングされるため、基本上三角行列U′iおよび基本下三角行列L′iは、第3の実施形態の基本上三角行列Uiおよび基本下三角行列Liよりもさらに非零要素数が少ない行列となり、式H28の演算の計算量を式F14よりもさらに少なくできる。式H28では、第2の実施形態の式D26のE、U′1~U′t1が1つの行列Cで表わされ、しかも行列Cの非対角項の非零要素数が行列E、U′1~U′t1の非対角項の非零要素数の和以下であるため、式H28の演算は、第2の実施形態の式D26の演算よりもさらに計算量が少ない。また、式H28の右側にある行列乗算から順次実行してパリティベクトルYを算出するので、各行列乗算の結果はベクトルとなり、中間結果を記憶するための容量を小さくすることができる。また、行列分解処理時において、行列Bの逆行列を計算するという計算量の多い演算を行なうことなく、行列Bのオーダリングによる行列B′、A、Eの生成、行列B′のLU分解、LU分解された上三角行列の基本上三角行列の積への分解、LU分解された下三角行列の基本下三角行列の積への分解、行列乗算数の削減処理を行なえばよいので、少ない計算量でパリティベクトルYを生成するのに必要な行列を算出することができる。[第4の実施形態の変形例1]第4の実施形態の変形例1の符号化器は、実数演算を行なう。符号化アルゴリズム符号化器は、k個の情報ビットx1、x2、、xkからなる情報ベクトルXを受けて、実数演算を行なうことによって、以下の式を満たすようなm個のパリティビットy1、y2、、ymからなるパリティベクトルYを生成する。HX,YT=0I1ここで、Hはパリティ検査行列以下、検査行列とも言うであり、m行n列=kmの行列である。X,YTは、情報ベクトルとパリティベクトルからなるベクトルの転置を表わす。式I1は、実数演算の場合には、次のように変形される。BY=-AXI2ここで、行列Aは、検査行列Hの第1列目~第k列目からなるm行k列の行列である。行列Bは、検査行列Hの第k1列目~第n列目からなるm行m列の行列である。行列Bに対して、以下のようにオーダリングを行なうとする。まず、行列Bの2つの行を交換するとすると、式I2は以下のように変形される。P1BY=P1AXI3ここで、P1は、第1回目の行の入れ替えを表わす変換行列である。i行とj行を変換する場合には、P1は、単位行列Eのi行とj行を入れ替えた行列となる。さらに、行列Bの2つの列を交換すると、式I3は以下のように変形される。P1BQ1Q11Y=-P1AXI4ここで、Q1は、第1回目の列の入れ替えを表わす変換行列である。i列とj列を変換する場合には、Q1は、単位行列Eのi列とj列を入れ替えた行列となる。以下のように新たな行列を定義する。B=P1BQ1I5A=P1AI6式I5および式I6により、式I4は以下の式で表わされる。BQ11Y=-AXI7さらに、行列Bの2つの行を交換するとすると、式I7は以下のように変形される。P2BQ11Y=-P2AXI8ここで、P2は、第2回目の行の入れ替えを表わす変換行列である。さらに、行列Bの2つの列を交換すると、式I8は以下のように変形される。P2BQ2Q21Q11Y=-P2AXI9ここで、Q2は、第2回目の列の入れ替えを表わす変換行列である。以下のように新たな行列を定義する。B=P2BQ2I10A=P2AI11式I10および式I11により、式I9は以下の式で表わされる。BQ21Q11Y=-AXI12同様にして、行列Bに対して、第u回u≧1だけ行の入れ替えおよび第vv≧1だげ列の入れ替えを行なう。第s回目1≦s≦uの行の入れ替えを表わす行列をPs、第s回目1≦s≦vの列の入れ替えを表わす行列をQsとして、以下のように新たな行列を定義する。B′=PuP2P1BQ1Q2QvI13A=PuP2P1AI14E=Q1Q2QvI15式I13、式I14および式I15により、以下の式が成り立つ。B′E1Y=-AXI16行列B′をLU分解すると、式I16は以下の式に変形される。L′U′QV1Q21Q11Y=AXI17ここで、L′は下三角行列であり、U′は上三角行列である。式I17より、列ベクトルYは、以下の式で表わされる。Y=-EU′1L′1AXI18上三角行列U′は、以下の式のように、基本上三角行列U′ii=1~mの積に分解される。U′=U′mU′m1U′2U′1I19ここで、逆行列U′i1は、対角項の要素が1であり、かつ非対角項の要素はU′iの要素の符号を反転したものである。式I19より、U′1は、以下の式で表わされる。U′1=U′11U′21U′m11U′m1I20下三角行列Lは、以下の式のように、基本下三角行列Lii=1~mの積に分解される。L′=L′1L′2L′m1L′mI21ここで、逆行列L′i1は、対角項の要素が1であり、かつ非対角項の要素はL′iの要素の符号を反転したものである。式I21より、L′1は、以下の式で表わされる。L′1=L′m1L′m11L′21L′11I22式I20および式I22によって、式I18は以下の式に変形される。Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXI23式I23は、2×m3個の行列の乗算であるが、一定の条件を満足する場合には、いくつかの行列の積を1つの行列で表わすことができるとする。以下の式のように、E、U′11~U′t11のt個の行列の積を1つの行列Cで表わすことができるとする。EU′11U′21U′t11≡CI24この場合、一定の条件とは、行列E、U′11、U′21、、U′t11の非対角項の非零要素の個数の和が行列Cの非対角項の非零要素の個数以上であるものとする。式I24より、式I23は以下の式で表わされる。Y=-CU′t1U′m11U′m1L′m1L′m11L′21L′11AXI25式I25で算出されるパリティベクトルYと、情報ベクトルXを用いて、符号化ベクトルZは、以下の式で表わされる。Z=X,YI26ここで、符号化ベクトルZの第1ビット~第kビットは、情報ベクトルXのビットであり、符号化ベクトルZの第k1ビット~第nビットは、パリティベクトルYのビットである。構成図23は、第4の実施形態の変形例1の符号化器の構成を表わす図である。図23を参照して、この符号化器2hは、第2の実施形態の変形例1と同様の、検査行列分解部30と、オーダリング部40と、LU分解部34と、基本行列分解部36と、逆行列計算部43と、符号反転部99と、配列部20とを備える。これらについては説明を繰返さない。また、符号化器2hは、中間結果記憶部82と、行列記憶部88と、行列積計算部81と、行列積計算制御部128と、行列乗算数削減部85とを備える。なお、以下では、t<mとして説明する。中間結果記憶部82は、式I25に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部82は、パリティベクトルYの生成処理時に、式I25に含まれる2m-t3回の行列乗算の中間結果を表わすデータを記憶する。行列記憶部88は、基本上三角行列の逆行列U′t1、U′t11、、U′m1を表わすデータ、基本下三角行列の逆行列L′m1、L′m11、、L′11を表わすデータ、および行列C、Aを表わすデータを記憶する。行列積計算部81は、加算器87および乗算器89を備える。行列積計算部81は、パリティベクトルYを算出するために、式I25に含まれる2m-t3回の行列乗算を行列積計算制御部128に指示された順序で実行する。行列積計算部81は、入力される情報ベクトルX、行列記憶部88内の行列A、L′11、L′21、、L′m11、L′m1、U′m1、U′m11、、U′t1、Cを表わすデータ、および中間結果記憶部82内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行する。行列積計算部81は、式I25に含まれる2m-t3回の行列乗算が終了するまでの間は、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部82に記憶させる。また、行列積計算部81は、式I23に含まれる行列乗算の個数を削減する処理を実行するときに、行列乗算数削減部85から指示された行列乗算を実行する。行列乗算数削減部85は、式I23に含まれる行列乗算の個数を削減する処理を行なうときに、中間結果記憶部82にデータが記憶されている行列の順序が先頭からE、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部81を制御する。行列乗算数削減部85は、各乗算において、乗算の対象となる2つの行列の非対角項の非零要素数と、乗算結果である1つの行列Cの非対角項の非零要素数とを比較し、後者と前者の差が所定の閾値aa>0以下のときは、乗算対象の2つの行列を1つの行列Cで置換する。このようにして行列Cで置換された場合は、行列Cと次の行列との乗算が行なわれる。一方、行列乗算数削減部85は、後者と前者の差が所定の閾値aを超えるときには、乗算対象の2つの行列を1つの行列Cで置換することを行なわずに、行列E、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aの非対角項の非零要素数の総和と、行列E、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aのうちの置換が行なわれた行列を除いた行列と行列Cの非対角項の非零要素数の総和とを比較し、後者の値が前者の値以下の場合には、行列v、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aのうちの置換された行列を除いた行列と行列Cとを行列記憶部88に記憶させる。第t順位までの行列が置換された場合には、行列C、U′t1、U′t11、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aが行列記憶部88に記憶される。行列積計算制御部128は、パリティベクトルYを算出するために、行列記憶部88にデータが記憶されている行列の順序が先頭からA、L′11、L′21、、L′m11、L′m1、U′m1、U′m11、、U′t1、Cの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部81を制御する。また、行列積計算制御部128は、式I25に含まれる2m-t3回の行列乗算の終了後に、行列積計算部81から計算結果であるベクトルY′=CU′t1U′m11U′m1L′m1L′m11L′21L′11AXを符号反転部99へ出力させる。行列分解処理図24は、第4の実施形態の変形例1の行列分解処理のフローチャートである。図24を参照して、まず、第2の実施形態の変形例1のステップS701~ステップS705が検査行列分解部30、行列記憶部88、中間結果記憶部82、オーダリング部40、LU分解部34、基本行列分解部36、および逆行列計算部43によって実行される。ただし、生成された行列E、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aは、第2の実施形態の変形例1のように行列記憶部88にではなく、中間結果記憶部82に記憶されるステップS1501。次に、行列乗算数削減部85は、中間結果記憶部82にデータが記憶されている行列について、先頭からE、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aの順となるように順序を設定するステップS1502。次に、行列乗算数削減部85は、制御変数tを1に設定するステップS1503。次に、行列乗算数削減部85は、行列記憶部88から第t=1順位の行列Eを表わすデータを読み出して、行列Eを行列Cとして、行列Cを表わすデータを中間結果記憶部82に記憶するステップS1504。行列数積削減部は、中間結果記憶部82から行列Cを表わすデータを読み出して、行列Cの非零要素数SC0をカウントし、非零要素数SC0を中間結果記憶部82に記憶させるステップS1505。次に、行列乗算数削減部85は、第t1順位の行列を表わすデータを読み出して、その行列を行列matとするステップS1506。次に、行列乗算数削減部85は、行列matの非対角項の非零要素数SC1をカウントし、非零要素数SC1と中間結果記憶部82内の行列Cの非零要素数SC0との和SC2を算出して、非零要素数の和SC2を中間結果記憶部82に記憶させるステップS1507。次に、行列積計算部81は、行列Cと行列Matとの積C×Matを計算して、計算結果を行列DとするステップS1508。次に、行列乗算数削減部85は、行列Dの非対角項の非零要素数SC3をカウントし、非零要素数SC3を中間結果記憶部82に記憶させるステップS1509。行列乗算数削減部85は、中間結果記憶部82から非零要素数の和SC2および非零要素数SC3とを読み出して、SC3とSC2との差が閾値a以下であるかを判断するステップS1510。行列乗算数削減部85は、SC3とSC2との差が閾値a以下である場合にはステップS1510でYES、制御変数tをインクリメントしステップS1511、中間結果記憶部82内の行列Cを行列Dで更新しステップS1512、さらに中間結果記憶部82内の非零要素数SC0を非零要素数SC3を更新し、ステップS1506からの処理が繰返させる。一方、行列乗算数削減部85は、SC3とSC2との差が閾値aを超えステップS1510でNO、かつ制御変数tが2以上の場合にはステップS1514でYES、行列記憶部88にデータが記憶されている行列E、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aのそれぞれについて非対角項の非零要素数をカウントし、それらの非零要素数の総和SC4を中間結果記憶部82に記憶させるステップS1515。次に、行列乗算数削減部85は、行列E、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aのうちの第t1順位以降の行列のそれぞれについて非対角項の非零要素数をカウントし、それらの非零要素数の総和SC5と中間結果記憶部82内の行列Cの非零要素数SC0との総和SC6を算出して、非零要素数の総和SC6を中間結果記憶部82に記憶させるステップS1516。行列乗算数削減部85は、中間結果記憶部82から非零要素数の総和SC4および非零要素数の総和SC6とを読み出して、SC6がSC4以下であるかを判断するステップS1517。行列乗算数削減部85は、SC6がSC4以下である場合にはステップS1517でYES、中間結果記憶部82内の行列E、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aのうちの第1順位から第t順位までの行列を除いた行列U′t1、U′t11、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aと、行列Cとを行列記憶部88に記憶させるステップS1518。符号化ベクトル生成処理図25は、第4の実施形態の変形例1の符号化ベクトル生成処理のフローチャートである。図25を参照して、行列積計算制御部128は、行列記憶部88にデータが記憶されている行列の順序が先頭からA、L′11、L′21、、L′m1、U′m1、U′m11、、U′t1、Cの順となるように行列間の順序を設定するステップS1601。次に、行列積計算制御部128は、制御変数iを1に設定するステップS1602。行列積計算制御部128は、行列積計算部81を指示して、行列記憶部88から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。行列積計算部81は、乗算結果であるベクトルを中間結果Rとし、中間結果Rを表わすデータを中間結果記憶部82に記憶させるステップS1603。次に、行列積計算制御部128は、制御変数iをインクリメントするステップS1604。行列積計算制御部128は、制御変数iが2m-t3未満の場合にはステップS1605でYES、行列積計算部81を指示して、行列記憶部88から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部82に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部81は、乗算結果であるベクトルを新たな中間結果Rとし、中間結果記憶部82内の中間結果Rを表わすデータを更新するステップS1606。その後、ステップS1604からの処理が繰返される。制御変数iが2m-t3となった場合にはステップS1605でNO、行列積計算制御部128は、行列積計算部81を指示して、行列記憶部88から第i順位の行列Matiを表わすデータを読み出させるとともに、中間結果記憶部82に記憶されている中間結果Rを表わすデータとを読出させて、行列Matiと中間結果Rとの積Mati×Rを計算させる。行列積計算部81は、乗算結果であるベクトルY′を符号反転部99に出力する。符号反転部99は、ベクトルY′の符号を反転したものをパリティべクトルYとして出力するステップS1607。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS1608。第4の実施形態の変形例1の効果以上のように、第4の実施形態の変形例1によれば、符号化ベクトル生成処理時において、後退代入を行わずに、式I25に従ってパリティベクトルYを算出するので、少ない計算量で情報ベクトルXの符号化を行なうことができる。特に、行列Bがオーダリングされるため、基本上三角行列の逆行列U′i1および基本下三角行列の逆行列L′i1は、第3の実施形態の変形例1の基本上三角行列の逆行列Ui1および基本下三角行列の逆行列Li1よりもさらに非零要素数が少ない行列となり、式I25の演算の計算量を式G11よりもさらに少なくできる。式I25では、第2の実施形態の変形例1の式E23のE、U′11~U′t11が1つの行列Cで表わされ、しかも行列Cの非対角項の非零要素数が行列E、U′11~U′t11の非対角項の非零要素数の和以下であるため、式I25の演算は、第2の実施形態の変形例1の式E23の演算よりもさらに計算量が少ない。また、式I25の右側にある行列乗算から順次実行してパリティベクトルYを算出するので、各行列乗算の結果はベクトルとなり、中間結果を記憶するための容量を小さくすることができる。また、行列分解処理時において、行列Bの逆行列を計算するという計算量の多い演算を行なうことなく、行列Bのオーダリングによる行列B′、A、Eの生成、行列B′のLU分解、LU分解された上三角行列の基本上三角行列の積への分解、LU分解された下三角行列の基本下三角行列の積への分解、基本上三角行列および基本下三角行列の非対角項の符号の反転、行列乗算数の削減処理を行なえばよいので、少ない計算量でパリティベクトルYを生成するのに必要な行列を算出することができる。[第5の実施形態]第5の実施形態の符号化器は、2を法とする演算を行なう。この符号化器は、符号化ベクトル処理を複数の行列積計算部で並列実行するものである。符号化アルゴリズム第5の実施形態の符号化アルゴリズムは、第1の実施形態と同様である。構成図26は、第5の実施形態の符号化器の構成を表わす図である。図26を参照して、この符号化器2iは、第1の実施形態と同様の、検査行列分解部10と、LU分解部14と、基本行列分解部16と、行列記憶部18と、配列部20とを備える。符号化器は、さらに、中間結果記憶部92と、行列積計算部91と、行列積計算制御部129とを備える。行列積計算部91は、第1の行列積計算部97と、第2の行列積計算部98とを備える。第1の行列積計算部97は、加算器94および乗算器93を備える。行列積計算部91は、パリティベクトルYを算出するために、式B12に含まれる右から1番目からm1番目までのm1回の行列乗算を行列積計算制御部129に指示された順序で実行する。行列積計算部91は、入力される情報ベクトルX、行列記憶部18内の行列Lm、Lm1、、L1、Aを表わすデータ、および中間結果記憶部92内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行し、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部92に記憶させる。m1回の行列乗算が終了したときには、中間結果である列ベクトルR1=LmLm1L2L1AXが得られる。第2の行列積計算部98は、加算器96および乗算器95を備える。行列積計算部91は、パリティベクトルYを算出するために、式B12に含まれる右からm2番目から2m1番目までのm回の行列乗算を行列積計算制御部129に指示された順序で実行する。行列積計算部91は、行列記憶部18内の行列U1、U2、、Umを表わすデータ、および中間結果記憶部92内の中間結果を表わすデータのうちの2つを用いて各行列乗算を実行し、計算結果を表わすデータを中間結果を表わすデータとして中間結果記憶部92に記憶させる。m回の行列乗算が終了したときには、中間結果である行列R2=U1U2Um1Umが得られる。また、第1の行列積計算部97は、中間結果R1と中間結果R2との積R2×R1を計算し、計算結果であるベクトルをパリティべクトルYとして出力する。行列積計算制御部129は、パリティベクトルYを算出するために、行列記憶部18にデータが記憶されている行列の順序が先頭からA、L1、L2、、Lm1、Lm、Um、Um1、、U2、U1の順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部91を制御する。より具体的には、行列積計算制御部129は、第1の行列乗算器に、情報ベクトルX、第1順位~第m1順位の行列についての行列乗算をこの順序で実行させて、これらすべての行列乗算が終了後に、中間結果R1を表わすデータを第1の行列積計算部97へ出力する。また、行列積計算制御部129は、第2の行列乗算器に、第m1順位~第2m1順位の行列についての行列乗算をこの順序で実行させて、これらすべての行列乗算が終了後に、中間結果R2を表わすデータを第1の行列積計算部97へ出力する。また、行列積計算制御部129は、式B12に含まれる2m1回の行列乗算の終了後に、第1の行列積計算部97から計算結果であるパリティベクトルYを出力させる。中間結果記憶部92は、式B12に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部92は、パリティベクトルYの生成処理時に、第1の行列積計算部97および第2の行列積計算部98から出力される式B12に含まれる2m1回の行列乗算の中間結果を表わすデータを記憶する。行列分解処理第5の実施形態の行列分解処理の手順は、第1の実施形態と同様であるので、ここでは説明を繰返さない。符号化ベクトル生成処理図27は、第5の実施形態の符号化ベクトル生成処理のフローチャートである。図27を参照して、行列積計算制御部129は、行列記憶部18にデータが記憶されている行列の順序が先頭からA、L1、L2、、Lm1、Lm、Um、Um1、、U2、U1の順となるように行列間の順序を設定するステップS1701。行列積計算制御部129は、第1の行列積計算部97に対するステップS1702~S1706の処理と、第2の行列積計算部98に対するステップS1707~S1711の処理が同時に並行して実行されるように制御する。行列積計算制御部129は、制御変数iを1に設定するステップS1702。行列積計算制御部129は、第1の行列積計算部97を指示して、行列記憶部18から第i=1順位の行列Aを表わすデータを読み出させて、行列Aと、入力された情報ベクトルXとの積AXを計算させる。第1の行列積計算部97は、乗算結果であるベクトルを中間結果R1とし、中間結果R1を表わすデータを中間結果記憶部92に記憶させるステップS1703。次に、行列積計算制御部129は、制御変数iをインクリメントするステップS1704。行列積計算制御部129は、制御変数iがm1以下の場合にはステップS1705でYES、第1の行列積計算部97を指示して、行列記憶部18から第i順位の行列これをMatiとするを表わすデータを読み出させるとともに、中間結果記憶部92に記憶されている中間結果R1を表わすデータとを読出させて、行列Matiと中間結果R1との積Mati×R1を計算させる。第1の行列積計算部97は、乗算結果であるベクトルを新たな中間結果R1とし、中間結果記憶部92内の中間結果R1を表わすデータを更新するステップS1706。その後、ステップS1704からの処理が繰返される。また、行列積計算制御部129は、制御変数jをm2に設定するステップS1707。行列積計算制御部129は、第2の行列積計算部98を指示して、行列記憶部18から第j=m2順位の行列Umを表わすデータを読み出させて、行列Umを中間結果R2とし、中間結果R2を表わすデータを中間結果記憶部92に記憶させるステップS1708。次に、行列積計算制御部129は、制御変数jをインクリメントするステップS1709。行列積計算制御部129は、制御変数jが2m1以下の場合にはステップS1710でYES、第2の行列積計算部98を指示して、行列記憶部18から第j順位の行列これをMatjとするを表わすデータを読み出させるとともに、中間結果記憶部92に記憶されている中間結果R2を表わすデータとを読出させて、行列Matjと中間結果R2との積Matj×R2を計算させる。第2の行列積計算部98は、乗算結果であるベクトルを新たな中間結果R2とし、中間結果記憶部92内の中間結果R2を表わすデータを更新するステップS1711。その後、ステップS1709からの処理が繰返される。制御変数iがm1を超えた場合にはステップS1705でNO、行列積計算制御部129は、中間結果記憶部92内の中間結果R1を表わすデータを第1の行列積計算部97へ出力し、制御変数jが2m1を超えた場合にはステップS1710でNO、行列積計算制御部129は、中間結果記憶部92内の中間結果R2を表わすデータを第1の行列積計算部97へ出力する。第1の行列積計算部97は、中間結果R1と中間結果R2との積R2×R1を計算し、計算結果であるベクトルをパリティべクトルYとして出力するステップS1712。その後、配列部20は、kビットの情報ベクトルXとmビットのパリティべクトルYからなるnビットの符号化ベクトルZを生成して、出力するステップS1713。第5の実施形態の効果以上のように、第5の実施形態は、第1の実施形態と同様の効果を有する。さらに、第5の実施形態によれば、非特許文献2および非特許文献3での逐次計算による後退代入と異なり、式B12の演算が並列実行が可能なことを利用して、第1の行列積計算部による列ベクトルR1=LmLm1L2L1AXの算出処理と、第2の行列積計算部による行列R2=U1U2Um1Umの算出処理が同時に並列して実行されるので、非特許文献2および非特許文献3よりも短時間にパリティベクトルRを算出することができる。[第5の実施形態の変形例1]第1の実施形態以外の実施形態においても、2つの行列積計算部によって、パリティベクトル生成処理を並列実行するものとしてもよい。たとえば、第1の実施形態の変形例1では、第1の行列積計算部による列ベクトルR1=Lm1Lm11L21L11AXの算出処理と、第2の行列積計算部による行列R2=U11U21Um11Um1の算出処理を同時に並列して実行し、第1の行列積計算部が積R2×R1を計算するものとしてもよい。第2の実施形態では、第1の行列積計算部による列ベクトルR1=L′mL′m1L′2L′1AXの算出処理と、第2の行列積計算部による行列R2=EU′1U′2U′m1U′mの算出処理を同時に並列して実行し、第1の行列積計算部が積R2×R1を計算するものとしてもよい。第2の実施形態の変形例1では、第1の行列積計算部による列ベクトルR1=L′m1L′m11L′21L′11AXの算出処理と、第2の行列積計算部による行列R2=EU′11U′21U′m11U′m1の算出処理を同時に並列して実行し、第1の行列積計算部が積R2×R1を計算するものとしてもよい。第3の実施形態では、第1の行列積計算部による列ベクトルR1=LmLm1L2L1AXの算出処理と、第2の行列積計算部による行列R2=CUt1Um1Umの算出処理を同時に並列して実行し、第1の行列積計算部が積R2×R1を計算するものとしてもよい。第3の実施形態の変形例1では、第1の行列積計算部による列ベクトルR1=Lm1Lm11L21L11AXの算出処理と、第2の行列積計算部による行列R2=CUt11Um11Um1の算出処理を同時に並列して実行し、第1の行列積計算部が積R2×R1を計算するものとしてもよい。第4の実施形態では、第1の行列積計算部による列ベクトルR1=L′mL′m1L′2L′1AXの算出処理と、第2の行列積計算部による行列R2=CU′tU′m1U′mの算出処理を同時に並列して実行し、第1の行列積計算部が積R2×R1を計算するものとしてもよい。第4の実施形態の変形例1では、第1の行列積計算部による列ベクトルR1=L′m1L′m11L′21L′11AXの算出処理と、第2の行列積計算部による行列R2=CU′t1U′m11U′m1の算出処理を同時に並列して実行し、第1の行列積計算部が積R2×R1を計算するものとしてもよい。[第5の実施形態の変形例2]第5の実施形態および第5の実施形態の変形例1では、2個の行列積計算部を備えるものとしたが、3個以上の行列積計算部によって、パリティベクトル生成処理を並列実行するものとしてもよい。変形例本発明は、上記の実施の形態に限定されるものではなく、たとえば以下のような変形例も含まれる。1符号化器の構成本発明の実施形態では、符号化器が、パリティベクトル生成処理と、行列分解処理の両方の機能を備えるものとしたが、一方だけの機能を備えるものとしてもよい。符号化器がパリティベクトル生成処理の機能のみを備える場合には、パリティベクトルYを生成するための式B12、C9、D26、E23、F14、G11、H28、I25に含まれる行列のデータは、外部で予め計算されたものが記憶されている。たとえば、第1の実施形態では、行列U1、U2、、Um、Lm、Lm1、、L1、Aの各要素の値が予め外部で計算され、計算結果が行列記憶部に記憶されている。2記憶部に記憶されるデータ本発明の第1~第5の実施形態において、行列記憶部および中間結果記憶部に記憶される行列またはベクトルを表わすデータは、各要素の値である必要はなく、たとえば、非対角項の非零要素数つまり、1の位置を表わすものであってもよい。3行列積の計算順序本発明の実施形態では、パリティベクトルYを生成する式に含まれる行列乗算のうち、右側にある行列乗算ここでは、ベクトルと行列の乗算も行列乗算と呼ぶから順次実行するものとしたが、これに限定するものではなく、任意の順序で行列乗算を実行するものとしてもよいが、左側にある行列乗算から順次実行しない方がよい場合もある。なぜなら、左側にある行列乗算から順次実行した場合には、行列Bの逆行列が生成されることになり、行列Bを分解した意味がなくなる場合が考えられる。しかしながら、このような順序で計算する場合でも、行列Bの逆行列を計算するよりも、少ない計算量で行列分解処理を行なうことができたり、または分解された行列の非零要素数の和が、Bの逆行列の非零要素数の和よりも少ないときには、行列を記憶するための容量を少なくすることができる場合がある。4行列乗算数削減処理本発明の第3、第4の実施形態では、行列乗算数の削減処理時に、パリティベクトルYを生成する式に含まれる行列乗算のうち、左側にある行列乗算から順次実行するものとしたが、これに限定するものではなく、任意の順序で行列乗算を実行するものとしてもよい。たとえば、パリティベクトルYを生成する式においてXとの乗算を除いた右側から行列演算を実行することとしてもよい。この場合には、式F14の代わりに、次の式のようにパリティベクトルYを生成する式におけるXを除いた右側にある複数個の隣接する行列が1個の行列Cにまとめられた式が用いられる。Y≡U1Um1UmLmLm1L9CXF14-1ここで、Cは、L8Lt7L1Aである。またパリティベクトルYを生成する式の左端の行列乗算、およびXとの乗算を除く右端以外の任意の箇所の行列乗算から順次右または左の任意の方向に実行することとしてもよい。この場合には、式F14の代わりに、次の式のようにパリティベクトルYを生成する式の左端や右端Xを除く以外にある複数個の隣接する行列が1個の行列Cにまとめられた形に変形されることもある。Y≡U1U2CU9Um1UmLmLm1L2L1AXF14-2ここで、Cは、U3U4U8である。また、1つの行列に置換される複数個の隣接する行列は、1セットに限定されるものではなく、次の式のように複数個のセットであってもよい。Y≡C1U6U7U8C2U20Um1UmLmLm1L6C3XF14-3ここで、C1は、U1U2U5であり、C2は、U9U10U19であり、C3は、L5L4L1Aである。また複数の隣接する行列が1つの行列に置換されたパリティベクトルYを生成する式に含まれる行列の非対角項の非零要素数の和が、もとのパリティベクトルYを生成する式に含まれる行列の非対角項の非零要素数の和以下の条件を満足する場合に、複数の隣接する行列を1つの行列にまとめる行列乗算数削減処理を行なったが、このような条件を満たすかどうかにかかわりなく、行列乗算数削減処理を行なうこととしてもよい。つまり、第3の実施形態のステップS915~S917の処理、第3の実施形態の変形例1のステップS1115~S1117の処理、第4の実施形態のステップS1315~S1317の処理、第4の実施形態の変形例1のステップS1515~S1517の処理を省略することとしてもよい。また、本発明の実施形態では、閾値aは正の値としたが、これは単なる一例であって、閾値aは0、または負の値であってもよい。また、無条件で、一定個数の隣接する行列を1つの行列にまとめるものとしてもよい。5オーダリング本発明の実施形態では、行列Bに対して、u回u≧1の行の入れ替えと、v回v≧1の列の入れ替えを行なうオーダリングを行なったが、これに限定するものではない。たとえば、u回の行の入れ替えだけを行なうものとしてもよいつまり、v=0。この場合には、たとえば、式D26、E23、H26、H28、I23、I25は、Eが含まれない式に変形される。また、v回の列の入れ替えだけを行なうものとしてもよいつまり、u=0。この場合には、たとえば、式D26、E23、H26、H28、I23、I25は、Aが含まれない式に変形される。以下、各実施形態において上記のような変形を行なった場合の、各部の構成がどのように変形されるかについて説明する。5-1第2の実施形態5-1-Au≧1かつv≧1第2の実施形態では、u≧1かつv≧1のときには、式D26が用いられた。Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXD265-1-Bu≧1かつv=0u≧1かつv=0のときには、式D26に代えて、次の式が用いられる。Y≡U′1U′2U′m1U′mL′mL′m1L′2L′1AXD26′ここで、行列B′は、行列Bに対して、u回の行の入れ替えを行なったものである。行列L′ii=1~mは、行列B′をLU分解した下三角行列L′の基本下三角行列である。行列U′ii=1~mは、行列B′をLU分解した上三角行列U′の基本上三角行列である。オーダリング部は、中間結果記憶部から行列Aおよび行列Bを表わすデータを読み出して、行列Bのオーダリングを行ない、行列Bに対してu回の行の入れ替えを行なった行列B′を生成して中間結果記憶部に記憶させ、行列Aに対して行列Bに対するu回の行の入れ替えと同様の入れ替えを行なった行列Aを生成して行列記憶部に記憶させる。行列記憶部は、基本上三角行列U′1、U′2、、U′mを表わすデータ、基本下三角行列L′m、L′m1、、L′1を表わすデータ、および行列Aを表わすデータを記憶する。行列積計算部は、パリティベクトルYを算出するために、式D26′に含まれる2m1回の行列乗算を行列積計算制御部に指示された順序で実行する。行列積計算制御部は、パリティベクトルYを算出するために、行列記憶部にデータが記憶されている行列の順序が先頭からA、L′1、L′2、、L′m、U′m、U′m1、、U′1の順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。行列積計算制御部は、式D26′に含まれる2m1回の行列乗算の終了後に、行列積計算部から計算結果であるパリティベクトルYを出力させる。中間結果記憶部は、式D26′に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部は、パリティベクトルYの生成処理時に、式D26′に含まれる2m1回の行列乗算の中間結果を表わすデータを記憶する。5-1-Cu=0かつv≧1また、u=0かつv≧1のときには、式D26に代えて、次の式が用いられる。Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXD26ここで、行列B′は、行列Bに対して、v回の列の入れ替えを行なったものである。行列L′ii=1~mは、行列B′をLU分解した下三角行列L′の基本下三角行列である。行列U′ii=1~mは、行列B′をLU分解した上三角行列U′の基本上三角行列である。オーダリング部は、中間結果記憶部から行列Bを表わすデータを読み出して、行列Bのオーダリングを行ない、行列Bに対してv回の列の入れ替えを行なった行列B′を生成して中間結果記憶部に記憶させ、単位行列Eに対して行列Bに対するv回の列の入れ替えと同様の入れ替えを行なった行列Eを生成して行列記憶部に記憶させる。行列記憶部は、基本上三角行列U′1、U′2、、U′mを表わすデータ、基本下三角行列L′m、L′m1、、L′1を表わすデータ、および行列A、Eを表わすデータを記憶する。行列積計算部は、パリティベクトルYを算出するために、式D26に含まれる2m2回の行列乗算を行列積計算制御部に指示された順序で実行する。行列積計算制御部は、パリティベクトルYを算出するために、行列記憶部にデータが記憶されている行列の順序が先頭からA、L′1、L′2、、L′m、U′m、U′m1、、U′1、Eの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。行列積計算制御部は、式D26に含まれる2m2回の行列乗算の終了後に、行列積計算部から計算結果であるパリティベクトルYを出力させる。中間結果記憶部は、式D26に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部は、パリティベクトルYの生成処理時に、式D26に含まれる2m2回の行列乗算の中間結果を表わすデータを記憶する。5-2第2の実施形態の変形例15-2-Au≧1かつv≧1第2の実施形態の変形例1では、u≧1かつv≧1のときには、式E23が用いられた。Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXE235-2-Bu≧1かつv=0u≧1かつv=0のときには、式E23に代えて、次の式が用いられる。Y=-U′11U′21U′m11U′m1L′m1L′m11L′21L′11AXE23′ここで、行列B′は、行列Bに対して、u回の行の入れ替えを行なったものである。行列L′i1i=1~mは行列L′iの逆行列である。行列L′iは、行列B′をLU分解した下三角行列L′の基本下三角行列である。行列U′i1i=1~mは行列U′iの逆行列である。行列U′iは、行列B′をLU分解した上三角行列U′の基本上三角行列である。オーダリング部は、5-1-Bと同様である。行列記憶部は、基本上三角行列の逆行列U′11、U′21、、U′m1を表わすデータ、基本下三角行列の逆行列L′m1、L′m11、、L′11を表わすデータ、および行列Aを表わすデータを記憶する。行列積計算部は、パリティベクトルYを算出するために、式E23′に含まれる2m1回の行列乗算を行列積計算制御部に指示された順序で実行する。行列積計算制御部は、パリティベクトルYを算出するために、行列記憶部にデータが記憶されている行列の順序が先頭からA、L′11、L′21、、L′m11、L′m1、U′m1、U′m11、、U′21、U′11の順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。また、行列積計算制御部は、式E23′に含まれる2m1回の行列乗算の終了後に、行列積計算部から計算結果であるベクトルY′=U′11U′21U′m11U′m1L′m1L′m11L′21L′11Aを符号反転部へ出力させる。中間結果記憶部は、式E23′に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部は、パリティベクトルYの生成処理時に、式E23′に含まれる2m1回の行列乗算の中間結果を表わすデータを記憶する。5-2-Cu=0かつv≧1また、u=0かつv≧1のときには、式E23に代えて、次の式が用いられる。Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXE23ここで、行列B′は、行列Bに対して、v回の列の入れ替えを行なったものである。行列L′i1i=1~mは行列L′iの逆行列である。行列L′iは、行列B′をLU分解した下三角行列L′の基本下三角行列である。行列U′i1i=1~mは行列U′iの逆行列である。行列U′iは、行列B′をLU分解した上三角行列U′の基本上三角行列である。オーダリング部は、5-2-Bと同様である。行列記憶部は、基本上三角行列の逆行列U′11、U′21、、U′m1を表わすデータ、基本下三角行列の逆行列L′m1、L′m11、、L′11を表わすデータ、および行列A、Eを表わすデータを記憶する。行列積計算部は、パリティベクトルYを算出するために、式E23に含まれる2m2回の行列乗算を行列積計算制御部に指示された順序で実行する。行列積計算制御部は、パリティベクトルYを算出するために、行列記憶部にデータが記憶されている行列の順序が先頭からA、L′11、L′21、、L′m11、L′m1、U′m1、U′m11、、U′21、U′11、Eの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。また、行列積計算制御部は、式E23に含まれる2m2回の行列乗算の終了後に、行列積計算部から計算結果であるベクトルY′=EU′11U′21U′m11U′m1L′m1L′m11L′21L′11Aを符号反転部へ出力させる。中間結果記憶部は、式E23に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部は、パリティベクトルYの生成処理時に、式E23に含まれる2m2回の行列乗算の中間結果を表わすデータを記憶する。5-3第4の実施形態5-3-Au≧1かつv≧1第4の実施形態では、u≧1かつv≧1のときには、式H26が用いられ、E、U′1~U′t1のt個の行列の積を1つの行列Cで表わした場合に、式H28が得られた。Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXH26Y≡CU′tU′m1U′mL′mL′m1L′2L′1AXH285-3-Bu≧1かつv=0u≧1かつv=0のときには、式H26に代えて、式H26′が用いられ、U′1~U′tのt個の行列の積を1つの行列Cで表わした場合に、式H28が得られる。Y≡U′1U′2U′m1U′mL′mL′m1L′2L′1AXH26′Y≡CU′t1U′m1U′mL′mL′m1L′2L′1AXH28′ここで、行列B′は、行列Bに対して、u回の行の入れ替えを行なったものである。行列L′ii=1~mは、行列B′をLU分解した下三角行列L′の基本下三角行列である。行列U′ii=1~mは、行列B′をLU分解した上三角行列U′の基本上三角行列である。オーダリング部は、5-1-Bと同様である。行列記憶部は、基本上三角行列U′t1、U′t2、、U′mを表わすデータ、基本下三角行列L′m、L′m1、、L′1を表わすデータ、および行列C、Aを表わすデータを記憶する。行列積計算部は、パリティベクトルYを算出するために、式H28′に含まれる2m-t2回の行列乗算を行列積計算制御部に指示された順序で実行する。行列積計算部は、式H26′に含まれる行列乗算の個数を削減する処理を実行するときに、行列乗算数削減部から指示された行列乗算を実行する。行列乗算数削減部は、式H26′に含まれる行列乗算の個数を削減する処理を行なうときに、中間結果記憶部にデータが記憶されている行列の順序が先頭からU′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。行列積計算制御部は、パリティベクトルYを算出するために、行列記憶部にデータが記憶されている行列の順序が先頭からA、L′1、L′2、、L′m1、L′m、U′m、U′m1、、U′t1、Cの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。また、行列積計算制御部は、式H28′に含まれる2m-t2回の行列乗算の終了後に、行列積計算部から計算結果であるパリティベクトルYを出力させる。中間結果記憶部は、式H28′に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部は、パリティベクトルYの生成処理時に、式H28′に含まれる2m-t2回の行列乗算の中間結果を表わすデータを記憶する。5-3-Cu=0かつv≧1また、u=0かつv≧1のときには、式H26に代えて、式H26が用いられ、E、U′1~U′t1のt個の行列の積を1つの行列Cで表わした場合に、式H28が得られる。Y≡EU′1U′2U′m1U′mL′mL′m1L′2L′1AXH26Y≡CU′tU′m1U′mL′mL′m1L′2L′1AXH28ここで、行列B′は、行列Bに対して、v回の列の入れ替えを行なったものである。行列L′ii=1~mは、行列B′をLU分解した下三角行列L′の基本下三角行列である。行列U′ii=1~mは、行列B′をLU分解した上三角行列U′の基本上三角行列である。オーダリング部は、5-1-Cと同様である。行列記憶部は、基本上三角行列U′t、U′t1、、U′mを表わすデータ、基本下三角行列L′m、L′m1、、L′1を表わすデータ、および行列C、Aを表わすデータを記憶する。行列積計算部は、パリティベクトルYを算出するために、式H28に含まれる2m-t3回の行列乗算を行列積計算制御部に指示された順序で実行する。行列積計算部は、式H26に含まれる行列乗算の個数を削減する処理を実行するときに、行列乗算数削減部から指示された行列乗算を実行する。行列乗算数削減部は、式H26に含まれる行列乗算の個数を削減する処理を行なうときに、中間結果記憶部にデータが記憶されている行列の順序が先頭からE、U′1、U′2、、U′m1、U′m、L′m、L′m1、、L′2、L′1、Aの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。行列積計算制御部は、パリティベクトルYを算出するために、行列記憶部にデータが記憶されている行列の順序が先頭からA、L′1、L′2、、L′m1、L′m、U′m、U′m1、、U′t、Cの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。また、行列積計算制御部は、式H28に含まれる2m-t3回の行列乗算の終了後に、行列積計算部から計算結果であるパリティベクトルYを出力させる。中間結果記憶部は、式H28に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部は、パリティベクトルYの生成処理時に、式H28に含まれる2m-t3回の行列乗算の中間結果を表わすデータを記憶する。5-4第4の実施形態の変形例15-4-Au≧1かつv≧1第4の実施形態の変形例1では、u≧1かつv≧1のときには、式I23が用いられ、E、U′11~U′t11のt個の行列の積を1つの行列Cで表わした場合に、式I25が得られた。Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXI23Y=-CU′t1U′m11U′m1L′m1L′m11L′21L′11AXI255-4-Bu≧1かつv=0u≧1かつv=0のときには、式I23に代えて、式I23′が用いられ、U′11~U′t1のt個の行列の積を1つの行列Cで表わした場合に、式I25′が得られる。Y=-U′11U′21U′m11U′m1L′m1L′m11L′21L′11AXI23′Y=-CU′t11U′m11U′m1L′m1L′m11L′21L′11AXI25′ここで、行列B′は、行列Bに対して、u回の行の入れ替えを行なったものである。行列L′i1i=1~mは行列L′iの逆行列である。行列L′iは、行列B′をLU分解した下三角行列L′の基本下三角行列である。行列U′i1i=1~mは行列U′iの逆行列である。行列U′iは、行列B′をLU分解した上三角行列U′の基本上三角行列である。オーダリング部は、5-1-Bと同様である。行列記憶部は、基本上三角行列の逆行列U′t11、U′t21、、U′m1を表わすデータ、基本下三角行列の逆行列L′m1、L′m11、、L′11を表わすデータ、および行列C、Aを表わすデータを記憶する。行列積計算部は、パリティベクトルYを算出するために、式I25′に含まれる2m-t2回の行列乗算を行列積計算制御部に指示された順序で実行する。行列積計算部は、式I23′に含まれる行列乗算の個数を削減する処理を実行するときに、行列乗算数削減部から指示された行列乗算を実行する。行列乗算数削減部は、式I23′に含まれる行列乗算の個数を削減する処理を行なうときに、中間結果記憶部にデータが記憶されている行列の順序が先頭からU′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。行列積計算制御部は、パリティベクトルYを算出するために、行列記憶部にデータが記憶されている行列の順序が先頭からA、L′11、L′21、、L′m11、L′m1、U′m1、U′m11、、U′t11、Cの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。また、行列積計算制御部は、式I25′に含まれる2m-t2回の行列乗算の終了後に、行列積計算部から計算結果であるベクトルY′=CU′t11U′m11U′m1L′m1L′m11L′21L′11AXを符号反転部へ出力させる。中間結果記憶部は、式I25′に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部は、パリティベクトルYの生成処理時に、式I25′に含まれる2m-t2回の行列乗算の中間結果を表わすデータを記憶する。5-4-Cu=0かつv≧1また、u=0かつv≧1のときには、式I23に代えて、式I23が用いられ、E、U′11~U′t11のt個の行列の積を1つの行列Cで表わした場合に、式I25が得られる。Y=-EU′11U′21U′m11U′m1L′m1L′m11L′21L′11AXI23Y=-CU′t1U′m11U′m1L′m1L′m11L′21L′11AXI25ここで、行列B′は、行列Bに対して、v回の列の入れ替えを行なったものである。行列L′i1i=1~mは行列L′iの逆行列である。行列L′iは、行列B′をLU分解した下三角行列L′の基本下三角行列である。行列U′i1i=1~mは行列U′iの逆行列である。行列U′iは、行列B′をLU分解した上三角行列U′の基本上三角行列である。オーダリング部は、5-1-Cと同様である。行列記憶部は、基本上三角行列の逆行列U′t1、U′t11、、U′m1を表わすデータ、基本下三角行列の逆行列L′m1、L′m11、、L′11を表わすデータ、および行列C、Aを表わすデータを記憶する。行列積計算部は、パリティベクトルYを算出するために、式I25に含まれる2m-t3回の行列乗算を行列積計算制御部に指示された順序で実行する。行列積計算部は、式I23に含まれる行列乗算の個数を削減する処理を実行するときに、行列乗算数削減部から指示された行列乗算を実行する。行列乗算数削減部は、式I23に含まれる行列乗算の個数を削減する処理を行なうときに、中間結果記憶部にデータが記憶されている行列の順序が先頭からE、U′11、U′21、、U′m11、U′m1、L′m1、L′m11、、L′21、L′11、Aの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。行列積計算制御部は、パリティベクトルYを算出するために、行列記憶部にデータが記憶されている行列の順序が先頭からA、L′11、L′21、、L′m11、L′m1、U′m1、U′m11、、U′t1、Cの順となるように行列間の順序を設定し、この順序で行列乗算を行なうように行列積計算部を制御する。また、行列積計算制御部は、式I25に含まれる2m-t3回の行列乗算の終了後に、行列積計算部からであるベクトルY′=CU′t1U′m11U′m1L′m1L′m11L′21L′11AXを符号反転部へ出力させる。中間結果記憶部は、式I25に含まれる行列を生成する処理行列分解処理における中間結果を表わすデータを記憶する。また、中間結果記憶部は、パリティベクトルYの生成処理時に、式I25に含まれる2m-t3回の行列乗算の中間結果を表わすデータを記憶する。6パリティベクトルYを計算する過程で非対角項の非零要素数が増加しないようなオーダリング手法たとえば、行列U3、行列U4がそれぞれ式13、式14で表わされる場合には、これらの積U4×U3は、式15で表わされる。行列U4×U3の計算結果を観察すると、第4行は、U4の第4行と同じである。第3行は、U[3,4]が0の場合、U3の第3行と同じになる。また、第3行は、U[3,4]が1の場合、第i列がU[3,i]U[4,i]となる。2を法とする演算では、U[3,i]とU[4,i]のいずれもが1の場合、またはいずれもが0の場合に、U[3,i]U[4,i]の値が0となる。このことは、行列U4×U3の非対角項の非零要素数を少なくするためには、上三角行列Uの各列において、値が1である要素が隣接するように行列Bをオーダリングするのが望ましいことを示している。言い換えると、上三角行列Uの各列において、値が1である要素が隣接するように行列Bをオーダリングすることによって、パリティベクトルYを生成する式を計算するために、行列乗算を行なっても、非対角項の非零要素数が増加しないようにすることができる。また、このようなオーダリングを行なうことによって、複数個の行列を1つにまとめても非対角項の非零要素数が増加しないので、行列乗算数削減処理によって行列乗算数を効果的に削減することができる。また、行列L3、行列L4がそれぞれ式16、式17で表わされる場合には、これらの積L4×L3は、式18で表わされる。行列L4×L3の計算結果を観察すると、第4列は、L4の第4列と同じである。第3列は、L[4,3]が0の場合、L3の第3列と同じになる。また、第3列は、L[4,3]が1の場合、第i行がL[i,3]L[i,4]となる。2を法とする演算では、L[i,3]とL[i,4]のいずれもが1の場合、またはいずれもが0の場合に、L[i,3]L[i,4]の値が0となる。このことは、行列L4×L3の非対角項の非零要素数を少なくするためには、下三角行列Lの各行において、値が1である要素が隣接するように行列Bをオーダリングするのが望ましいことを示している。言い換えると、下三角行列Lの各行において、値が1である要素が隣接するように行列Bをオーダリングすることによって、パリティベクトルYを生成する式を計算するために、行列乗算を行なっても、非対角項の非零要素数が増加しないようにすることができる。また、このようなオーダリングを行なうことによって、複数個の行列を1つにまとめても非対角項の非零要素数が増加しないので、行列乗算数削減処理によって行列乗算数を効果的に削減することができる。7符号化プログラム本発明の実施形態で説明した符号化器は、専用のハードウエア装置で実現されるものに限られない。外部から符号化プログラムをメモリにインストールし、コンピュータがこの符号化プログラムをメモリから読出して実行することによって、符号化器の機能を実現することとしてもよい。この場合、第1の実施形態の機能を実行する符号化プログラムは図3と図4のフローチャートの各ステップを備え、第1の実施形態と同様の効果を有する。第1の実施形態の変形例1の機能を実行する符号化プログラムは図6と図7のフローチャートの各ステップを備え、第1の実施形態の変形例と同様の効果を有する。第2の実施形態の機能を実行する符号化プログラムは図9と図10のフローチャートの各ステップを備え、第2の実施形態と同様の効果を有する。第2の実施形態の変形例1の機能を実行する符号化プログラムは図12と図13のフローチャートの各ステップを備え、第2の実施形態の変形例1と同様の効果を有する。第3の実施形態の機能を実行する符号化プログラムは図15と図16のフローチャートの各ステップを備え、第3の実施形態と同様の効果を有する。第3の実施形態の変形例1の機能を実行する符号化プログラムは図18と図19のフローチャートの各ステップを備え、第3の実施形態の変形例1と同様の効果を有する。第4の実施形態の機能を実行する符号化プログラムは図21と図22のフローチャートの各ステップを備え、第4の実施形態と同様の効果を有する。第4の実施形態の変形例1の機能を実行する符号化プログラムは図24と図25のフローチャートの各ステップを備え、第4の実施形態の変形例1と同様の効果を有する。第5の実施形態の機能を実行する符号化プログラムは図3と図27のフローチャートの各ステップを備え、第5の実施形態と同様の効果を有する。8誤り訂正符号本発明の実施形態では、誤り訂正符号の例としてLDPCについて説明したが、これに限定するものではなく、ビタビやターボ符号などへの応用も可能である。9t1<m、t<m本発明の第3の実施形態およびその変形例1では、説明の便宜上t1<mとしたが、これには限定されない。また、同様に、本発明の第4の実施形態およびその変形例1では、説明の便宜上t<mとしたが、これには限定されない。今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。"