(57)【要約】【課題】行列の対角化処理の高速化を図ることが可能な行列対角化方法、行列対角化装置、復号装置、およびプログラムを提供する。【解決手段】行列対角化装置１００は、行列を記憶する行列メモリ１２０と、行のインデックスを記憶する行インデックスメモリ１１０と、要探索、掃き出しを行う要探索、掃き出し回路１３０と、を含み、行インデックスメモリ１１０から順に行インデックスを読み出し、その行インデックスが指定する行を行列メモリ１２０から読み出し、当該行の対角化の対象となる列の要素を見て、要探索、掃き出しを行う機能を有し、要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する。【選択図】図２
2008140336.tif 000002
【特許請求の範囲】
【請求項１】
対角化対象列において、順に要素が零か非零かを判定する第１ステップと、
前記要素を含む行が既に要行になったことがあるかも判定する第２ステップと、
判定の結果、非零でありかつその行が未だ要行になったことがない場合には、当該要素を要、当該要素を含む行を要行とする第３ステップと、
前記要行を利用して他行を掃き出す掃き出し第４ステップと、を有し、
前記第１ステップから前記第４ステップの処理を対角化対象列毎に繰り返し、
要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する
行列対角化方法。
【請求項２】
対象となる列の要探索において、初めて見つかった非零要素を要とし、
当該要素を含む行を使って他の行に掃き出す時には、要探索の時に零か非零かの判定をしなかった要素を含む行のみに対して掃き出すことにより、対象列の各要素とも要探索か掃き出しのどちらかのみ対象とする
請求項１記載の行列対角化方法。
【請求項３】
要探索、掃き出しを列毎ではなく行毎に行う
請求項１または２記載の行列対角化方法。
【請求項４】
対角化対象列において、順に要素が零か非零かを判定し、当該要素を含む行が既に要行になったことがあるかも判定し、非零でありかつその行が未だ要行になったことがない場合には、当該要素を要、当該要素を含む行を要行とする要探索手段と、
前記要行を利用して他行を掃き出す掃き出し手段と、を有し、
前記要探索手段および前記掃き出し手段は、処理を対角化対象列毎に繰り返し、
要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する
行列対角化装置。
【請求項５】
対象となる列の要探索において、初めて見つかった非零要素を要とし、
その要素を含む行を使って他の行に掃き出す時には、要探索の時に零か非零かの判定をしなかった要素を含む行のみに対して掃き出すことにより、対象列の各要素とも要探索か掃き出しのどちらかのみ対象とする
請求項４記載の行列対角化装置。
【請求項６】
行列を記憶する行列メモリと、
行のインデックスを記憶する行インデックスメモリと、
要探索、掃き出しを行う要探索、掃き出し回路と、を含み、
行インデックスメモリから順に行インデックスを読み出し、その行インデックスが指定する行を行列メモリから読み出し、当該行の対角化の対象となる列の要素を見て、要探索、掃き出しを行う機能を有し、
要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する
行列対角化装置。
【請求項７】
対象となる列を要探索、掃き出す際、前記行インデックスメモリから行インデックスを先頭アドレスから順番に読み出し、
読み出した行が要行にならなかった場合、その行インデックスを行インデックスメモリの先頭アドレスから順に書き込み、読み出した行が要行になった場合のみ、その行インデックスを前記行インデックスメモリの最後のアドレスに書き込む
請求項６記載の行列対角化装置。
【請求項８】
前記行列メモリから読み出した行から対角化の対象となる列の要素を取り出す回路を要探索回路と掃き出し回路で共用している
請求項６記載の行列対角化装置。
【請求項９】
前記要探索、掃き出し回路は、
要探索時は、行列メモリからの入力行の対象となる列が非零だった場合は自動的にその行を要行として内部メモリに保持し、次以降の入力行の対象となる列が非零だった場合は、確保した要行でその行を掃き出す
請求項８記載の行列対角化装置。
【請求項１０】
要探索、掃き出しを列毎ではなく行毎に行う
請求項４から９のいずれか一に記載の行列対角化装置。
【請求項１１】
対角化対象列において、順に要素が零か非零かを判定し、当該要素を含む行が既に要行になったことがあるかも判定し、非零でありかつその行が未だ要行になったことがない場合には、当該要素を要、当該要素を含む行を要行とする要探索ステップと、
前記要行を利用して他行を掃き出す掃き出しステップと、を含み、
前記対角化対象列毎に繰り返すことをコンピュータに行わせる行列の対角化プログラムであって、
要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定することを含む処理をコンピュータに実行させる対角化プログラム。
【請求項１２】
対象となる列の要探索において、初めて見つかった非零要素を要とし、
その要素を含む行を使って他の行に掃き出す時には、要探索の時に零か非零かの判定をしなかった要素を含む行のみに対して掃き出すことにより、対象列の各要素とも要探索か掃き出しのどちらかのみ対象とすることを含む処理をコンピュータに実行させる
請求項１１記載の対角化プログラム。
【請求項１３】
行列を記憶する行列の配列と、
行のインデックスを記憶する行インデックスの配列と、を含み、
行インデックスの配列から順に行インデックスを読み出し、その行インデックスが指定する行を行列の配列から読み出し、その行の対角化の対象となる列の要素を見て、要探索、掃き出しを行うことを含む処理をコンピュータに実行させる
請求項１２記載の対角化プログラム。
【請求項１４】
対象となる列を要探索、掃き出す際、行インデックスの配列の先頭から行インデックスを順番に読み出し、
読み出した行が要行にならなかった場合、その行インデックスを行インデックスの配列の先頭から順に書き込み、読み出した行が要行になった場合のみ、その行インデックスを行インデックスの配列の最後に書き込むことを含む処理をコンピュータに実行させる
請求項１３記載の対角化プログラム。
【請求項１５】
要探索、掃き出しを列毎ではなく行毎に行う
請求項１１から１４のいずれか一に記載の対角化プログラム。
【請求項１６】
対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行うことにより、値が更新され、更新された値に対して、所定の繰り返し回数、ソート、対角化、信頼性伝播（ＢＰ）を行う復号装置であって、
受信語の信頼度（ＬＬＲ）の大きさに応じて列インデックスのソートを行うソート部と、
信頼度の低いシンボルに対応する列より順に、パリティ検査行列の対角化を行う行列対角化装置と、を含み、
前記行列対角化装置は、
対角化対象列において、順に要素が零か非零かを判定し、当該要素を含む行が既に要行になったことがあるかも判定し、非零でありかつその行が未だ要行になったことがない場合には、当該要素を要、当該要素を含む行を要行とする要探索手段と、
前記要行を利用して他行を掃き出す掃き出し手段と、を有し、
前記要探索手段および前記掃き出し手段は、処理を対角化対象列毎に繰り返し、
要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する
復号装置。
【請求項１７】
対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行うことにより、値が更新され、更新された値に対して、所定の繰り返し回数、ソート、対角化、信頼性伝播（ＢＰ）を行う復号装置であって、
受信語の信頼度（ＬＬＲ）の大きさに応じて列インデックスのソートを行うソート部と、
信頼度の低いシンボルに対応する列より順に、パリティ検査行列の対角化を行う行列対角化装置と、を含み、
前記行列対角化装置は、
行列を記憶する行列メモリと、
行のインデックスを記憶する行インデックスメモリと、
要探索、掃き出しを行う要探索、掃き出し回路と、を含み、
行インデックスメモリから順に行インデックスを読み出し、その行インデックスが指定する行を行列メモリから読み出し、当該行の対角化の対象となる列の要素を見て、要探索、掃き出しを行う機能を有し、
要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する
復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列の対角化方法、対角化装置、復号装置、およびプログラムに関するものである。
【背景技術】
【０００２】
行列の対角化を行う方法の一つに掃き出し法が知られている。
ここでいう対角化とは、たとえばｍ行ｎ列（ｍ≦ｎ）の行列の場合、対角化対象となるｍ列を含むｍ行ｍ列の部分行列について、行重み１、列重み１の行列に変形することを指す。
掃き出し法は、行の基本変形を繰り返すことで実現される。
【０００３】
図１は、０か１のみの要素を持つ行列の対角化のフローチャートである。
【０００４】
基本変形では、対象列を第１行から順にその要素を調べ（ＳＴ１〜ＳＴ３）、要素が零か非零かを判定し（ＳＴ４，ＳＴ６）、また、その要素を含む行が既に要行になったことがあるかも判定する（ＳＴ５，ＳＴ６）。
非零でありかつその行が未だ要行になったことがなければ、その要素を要とし、その要素を含む行を要行とする（ＳＴ７）。これを要探索という。
次に、要行を用いて他行を掃き出す。掃き出しでは、要行以外に対象列が非零となる要素を探し、その行から要行を減算する（ＳＴ８〜ＳＴ１６）。
【０００５】
以下に具体例を挙げる。ここでは例として、０か１の要素しかない４行６列の行列の第１列から第４列までを対角化する場合を考察する。
【０００６】
＜１＞次の初期行列に対して対角化を開始する。
【０００７】
【数１】
2008140336.tif 000003
【０００８】
＜２＞まず、次のように、第１列について基本変形を行う。
第１行を要探索する。この場合、第１列は零なので要にはならない。
【０００９】
【数２】
2008140336.tif 000004
【００１０】
＜３＞次に、第２行を要探索する。
この場合、第１列は零なので要にはならない。
【００１１】
【数３】
2008140336.tif 000005
【００１２】
＜４＞第３行を要探索する。
この場合、第１列は非零であり、かつ第３行はこれまで要行になったことがないため、この行を要行とする。
【００１３】
【数４】
2008140336.tif 000006
【００１４】
＜５＞次に、第３行を使って他行を掃き出す。
この場合、第４行の第１列は非零であるため、第３行を第４行に加える。
【００１５】
【数５】
2008140336.tif 000007
【００１６】
＜６＞第１行の第１列は零であるためそのままにする。
【００１７】
【数６】
2008140336.tif 000008
【００１８】
＜７＞第２行の第１列は零であるためそのままにする。
【００１９】
【数７】
2008140336.tif 000009
【００２０】
＜８＞次に、第２列について基本変形を施す。
第１行を要探索する。この場合、第２列は零なので要にはならない。
【００２１】
【数８】
2008140336.tif 000010
【００２２】
＜９＞第２行を要探索する。
この場合、第２列は零なので要にはならない。
【００２３】
【数９】
2008140336.tif 000011
【００２４】
＜１０＞第３行を要探索する。
この場合、第２列は非零であるが、第３行はすでに第１列で要行になったので、第２列で要行にはなれない。
【００２５】
【数１０】
2008140336.tif 000012
【００２６】
＜１１＞第４行を要探索する。
この場合、第２列は非零であり、かつ第４行はこれまで要行になったことがないため、この行を要行とする。
【００２７】
【数１１】
2008140336.tif 000013
【００２８】
＜１２＞第４行を使って他行を掃き出す。
この場合、第１行の第２列は零であるためそのままにする。
【００２９】
【数１２】
2008140336.tif 000014
【００３０】
＜１３＞第２行の第２列は零であるためそのままにする。
【００３１】
【数１３】
2008140336.tif 000015
【００３２】
＜１４＞第３行の第２列は非零であるので第４行を第３行に加える。
【００３３】
【数１４】
2008140336.tif 000016
【００３４】
＜１５＞第３列についても同様に基本変形を行う。
【００３５】
【数１５】
2008140336.tif 000017
【００３６】
＜１６＞第４列についても同様に基本変形を行う。
【００３７】
【数１６】
2008140336.tif 000018
【００３８】
以上で、対角化が完了する。なお、０と１以外の要素が存在する場合は、掃き出す時に、掃き出される行の対象要素を要行の対象要素で割った値と要行を掛け合わせて掃き出される行から減算すればよい。
【発明の開示】
【発明が解決しようとする課題】
【００３９】
対角化対象となる列の基本変形を行う場合、１列の基本変形に対し、要探索と掃き出しの両方の対象となる要素が発生し、最長で要探索と掃き出しの処理を各々行数分ずつ行う必要がある。
【００４０】
たとえば、上述した技術例において、第２列を基本変形するとき、第１行から第４行まで要探索を行った後に、第４行を用いて他行に掃き出す際、第１行、第２行、第３行の第２列が零か非零かを順に調べ直し掃き出す必要がある。
すなわち、上述した技術では、行列の対角化処理に時間がかかるという不利益がある。
【００４１】
本発明は、行列の対角化処理の高速化を図ることが可能な行列対角化方法、行列対角化装置、復号装置、およびプログラムを提供することにある。
【課題を解決するための手段】
【００４２】
本発明の第１の観点の行列対角化方法は、対角化対象列において、順に要素が零か非零かを判定する第１ステップと、前記要素を含む行が既に要行になったことがあるかも判定する第２ステップと、判定の結果、非零でありかつその行が未だ要行になったことがない場合には、当該要素を要、当該要素を含む行を要行とする第３ステップと、前記要行を利用して他行を掃き出す掃き出し第４ステップと、を有し、前記第１ステップから前記第４ステップの処理を対角化対象列毎に繰り返し、要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する。
【００４３】
本発明の第２の観点の行列対角化装置は、対角化対象列において、順に要素が零か非零かを判定し、当該要素を含む行が既に要行になったことがあるかも判定し、非零でありかつその行が未だ要行になったことがない場合には、当該要素を要、当該要素を含む行を要行とする要探索手段と、前記要行を利用して他行を掃き出す掃き出し手段と、を有し、前記要探索手段および前記掃き出し手段は、処理を対角化対象列毎に繰り返し、要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する。
【００４４】
本発明の第３の観点の行列対角化装置は、行列を記憶する行列メモリと、行のインデックスを記憶する行インデックスメモリと、要探索、掃き出しを行う要探索、掃き出し回路と、を含み、行インデックスメモリから順に行インデックスを読み出し、その行インデックスが指定する行を行列メモリから読み出し、当該行の対角化の対象となる列の要素を見て、要探索、掃き出しを行う機能を有し、要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する。
【００４５】
本発明の第４の観点は、対角化対象列において、順に要素が零か非零かを判定し、当該要素を含む行が既に要行になったことがあるかも判定し、非零でありかつその行が未だ要行になったことがない場合には、当該要素を要、当該要素を含む行を要行とする要探索ステップと、前記要行を利用して他行を掃き出す掃き出しステップと、を含み、前記対角化対象列毎に繰り返すことをコンピュータに行わせる行列の対角化プログラムであって、要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定することを含む処理をコンピュータに実行させる対角化プログラムである。
【００４６】
本発明の第５の観点は、対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行うことにより、値が更新され、更新された値に対して、所定の繰り返し回数、ソート、対角化、信頼性伝播（ＢＰ）を行う復号装置であって、受信語の信頼度（ＬＬＲ）の大きさに応じて列インデックスのソートを行うソート部と、信頼度の低いシンボルに対応する列より順に、パリティ検査行列の対角化を行う行列対角化装置と、を含み、前記行列対角化装置は、対角化対象列において、順に要素が零か非零かを判定し、当該要素を含む行が既に要行になったことがあるかも判定し、非零でありかつその行が未だ要行になったことがない場合には、当該要素を要、当該要素を含む行を要行とする要探索手段と、前記要行を利用して他行を掃き出す掃き出し手段と、を有し、前記要探索手段および前記掃き出し手段は、処理を対角化対象列毎に繰り返し、要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する。
【００４７】
本発明の第６の観点は、対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行うことにより、値が更新され、更新された値に対して、所定の繰り返し回数、ソート、対角化、信頼性伝播（ＢＰ）を行う復号装置であって、受信語の信頼度（ＬＬＲ）の大きさに応じて列インデックスのソートを行うソート部と、信頼度の低いシンボルに対応する列より順に、パリティ検査行列の対角化を行う行列対角化装置と、を含み、前記行列対角化装置は、行列を記憶する行列メモリと、行のインデックスを記憶する行インデックスメモリと、要探索、掃き出しを行う要探索、掃き出し回路と、を含み、行インデックスメモリから順に行インデックスを読み出し、その行インデックスが指定する行を行列メモリから読み出し、当該行の対角化の対象となる列の要素を見て、要探索、掃き出しを行う機能を有し、要探索の対象とする要素をその要素を含む行が未だ要行になっていない要素のみに限定する。
【００４８】
本発明によれば、行列の対角化を行う際、要探索の対象となる行を過去基本変形を行った列で未だ要になっていない行に限定する。
これにより、各列の各要素を要探索と掃き出しのどちらかのみ対象とすればよくなり、対角化を行う処理が高速化される。
【発明の効果】
【００４９】
本発明によれば、行列を対角化する場合、各列の要素を、要探索か掃き出しのいずれかの対象とするだけでよく、高速な対角化が可能となる。
【発明を実施するための最良の形態】
【００５０】
以下、本発明の実施形態を図面に関連付けて説明する。
【００５１】
図２は、本発明の実施形態に係る行列対角化方法を採用した行列対角化装置の基本的な構成例を示しブロック図である。
【００５２】
本実施形態に係る行列対角化装置１００は、図２に示すように、行のインデックスを記憶する行インデックスメモリ１１０と、行列を記憶する行列メモリ１２０と、要探索、掃き出し回路１３０とを有している。
【００５３】
図２の行列対角化装置１００は、行インデックスメモリ１１０から順に行インデックスを読み出し、その行インデックスが指定する行を行列メモリ１２０から読み出し、要探索、掃き出し回路１３０において、その行の対角化の対象となる列の要素を見て、要探索、掃き出しを行う。
【００５４】
行列対角化装置１００においては、対象となる列を要探索、掃き出す際、行インデックスメモリ１１０から行インデックスを先頭アドレスから順番に読み出す。
そして、読み出した行が要行にならなかった場合、その行インデックスを行インデックスメモリ１１０の先頭アドレスから順に書き込み、読み出した行が要行になった場合のみ、その行インデックスを行インデックスメモリ１１０の最後のアドレスに書き込む。
結果要探索の対象となる行が未だ要になっていない行に限定される。
これにより、各列の各要素を要探索と掃き出しのどちらかのみ対象とすればよく、対角化を行う処理が高速化される。
【００５５】
本実施形態の行列対角化装置１００は、対角化を行う際、各列の基本変形で、ある行が要行になる度にその行を行列の後段に回す。結果、対象となる列を基本変形するときに、要探索の対象となる行を未だ要になっていない行に限定できる。これにより、各列の各要素を要探索と掃き出しのどちらかのみ対象とすればよく、対角化を行う処理が高速化される。
【００５６】
以下、本実施形態に係る行列対角化方法の全体の処理を説明し、その後、図２の行列対角装置１００における要探索、掃き出し回路１３０の構成例、および装置の動作例について説明する。
【００５７】
まず、行列対角化方法の全体の処理について説明する。
【００５８】
図３は、本実施形態に係るｍ行ｎ列行列の対角化方法を説明するためのフローチャートである。
基本的に、この対角化方法は、図３に示すように、ステップＳＴ１０１〜ＳＴ１１４の処理を行う。
【００５９】
図３に示すように、各列の基本変形で要行になった行を後段に回すことにより、図１に示した一般的な行列対角化方法と異なり、対象列を基本変形する際、各要素は要探索および掃き出しのいずれかの対象になれば十分で、フローチャート上のｉ＝ｍとなれば、つまり行を第１行から第ｍ行まで各行に一度ずつアクセスすればその列の基本変形は完了し、一般的な方法のように第１行に戻って再びアクセスする必要がなく、高速な対角化が可能となる。
【００６０】
以下に具体例を挙げる。ここでは例として、０か１の要素しかない４行６列の行列の第１列から第４列までを対角化する場合を考察する。すなわち、図１および数１〜数１６に関連付けた一般的な方法との比較を容易にするために、前述と同様の対角化例を使って説明する。
【００６１】
＜１＞次の初期行列に対して対角化を開始する。
【００６２】
【数１７】
2008140336.tif 000019
【００６３】
＜２＞まず、次のように、第１列について基本変形を行う。
第１行を要探索する。この場合、第１列は零なので要にはならない。
【００６４】
【数１８】
2008140336.tif 000020
【００６５】
＜３＞次に、第２行を要探索する。
この場合、第１列は零なので要にはならない。
【００６６】
【数１９】
2008140336.tif 000021
【００６７】
＜４＞第３行を要探索する。
この場合、第１列ではじめて非零な要素であり、自動的にこの行を要行とする。
【００６８】
【数２０】
2008140336.tif 000022
【００６９】
＜５＞次に、第３行を使って他行を掃き出す。
第４行の第１列は非零であるため、第３行を第４行に加える。この場合、要探索で零か非零か判断対象になった行のうち、要になった行以外は必ず第１列が零であるので、第１行に戻って掃き出す必要はない。
【００７０】
【数２１】
2008140336.tif 000023
【００７１】
＜６＞第１列の要行を後段に回す。第３行は第４行となり、第４行は第３行となる。
【００７２】
【数２２】
2008140336.tif 000024
【００７３】
＜７＞次に、第２列について基本変形を施す。
第１行を要探索する。この場合、第２列は零なので要にはならない。
【００７４】
【数２３】
2008140336.tif 000025
【００７５】
＜８＞第２行を要探索する。
この場合、第２列は零なので要にはならない。
【００７６】
【数２４】
2008140336.tif 000026
【００７７】
＜９＞第３行を要探索する。
第２列ではじめて非零な要素であり、自動的にこの行を要行とする。
【００７８】
【数２５】
2008140336.tif 000027
【００７９】
＜１０＞第３行を使って他行を掃き出す。
この場合、第４行の第２列は非零であるため、第３行を第４行に加える。
【００８０】
【数２６】
2008140336.tif 000028
【００８１】
＜１１＞第２列の要行を後段に回す。
第３行は第４行となり、第４行は第３行となる。
【００８２】
【数２７】
2008140336.tif 000029
【００８３】
＜１２＞第３列についても同様に基本変形を行う。
【００８４】
【数２８】
2008140336.tif 000030
【００８５】
＜１３＞第３列の要行を後段に回す。
第１行は第４行となり、第２行は第１行、第３行は第２行、第４行は第３行となる。
【００８６】
【数２９】
2008140336.tif 000031
【００８７】
＜１４＞第４列についても同様に基本変形を行う。
【００８８】
【数３０】
2008140336.tif 000032
【００８９】
以上で、行列の対角化が完了する。
【００９０】
このように、たとえば第２列を基本変形する場合、第１行から順に要素を見ていくと、未だ要になっていない要素に限定して要探索できるため、初めて見つかった非零要素、この場合は第３行の要素を自動的に要とできるため、いざ掃き出しを行う場合は第３行以降の要素に限定して行えばよい。
この場合は第３行で第４行を掃き出せば、第２列についての基本変形は完了する。つまり、１列を基本変形する上で、各要素は要探索、掃き出しのいずれかのみ対象とすればよく、高速な対角化が可能となる。
【００９１】
なお、０と１以外の要素が存在する場合は、掃き出す時に、掃き出される行の対象要素を要行の対象要素で割った値と要行を掛け合わせて掃き出される行から減算すればよい。
また、行を後段に回す作業は、明示的に後段に回しているだけで、要探索を行う要素の順番を既に要になった行が後ろになるようにインデックスの順番を入れ替えて制御してもよい。
【００９２】
次に、図２の行列対角化装置の動作について図２、図４〜図９に関連付けて説明する。
【００９３】
図２は、行列対角化装置１００の初期状態を示し、行列メモリ１２０に４行６列の初期行列が入っている。行インデックスメモリ１１０には先頭アドレスから順に１，２，３，４とインクリメントした値が初期のインデックスとして入っている。
第１列を基本変形する場合、行インデックスを先頭アドレスから順に１，２，３，４と読み出す。これに従い、行列から第１，２，３，４行が順に読み出される。
読み出された行について、要探索、掃き出し回路１３０でまず要探索を行う。
第３行で初めて非零要素が見つかり、これを要行とし、一時的に要探索、掃き出し回路１３０に確保する。
【００９４】
次に読み出されてくる第４行に対して、掃き出しを行う。第１行から第４行まで要探索、掃き出しの処理が行われたら順次行列メモリ１２０に更新行が書き込まれる。
要探索、掃き出し回路１３０からは読み出した行が今回の対象列で要行になったかどうか、要行になった場合１、要行にならなかった場合０とする要フラグを行インデックスメモリ１１０に送る。
行インデックスメモリ１１０には、読み出した行のインデックスも同時に入力され、要フラグが１の場合にのみ、行インデックスを行インデックスメモリ１１０の最後のアドレスに書き込む。要フラグが０の場合は、先頭アドレスから順に行インデックスを書き込む。
【００９５】
行インデックスメモリ１１０の遷移は図４（Ａ）〜（Ｄ）に示すようになる。
第１列の基本変形が完了した場合、行インデックスメモリ１１０と行列メモリ１２０は、図５に示すようになる。
【００９６】
この状態から、第２列の基本変形を開始する。行インデックスメモリ１１０の先頭アドレスから順に行インデックスを読み出す。
第１，２，４行と読み出し、第４行が第２列について初めて非零要素となるので、これを要行とし、それ以降読み出される行、この場合は第３行を掃き出す。
このように、第１，２，４行について要探索、第３行について掃き出しを行うことによって、第２列の基本変形は完了する。
つまり、行数分の行読み出しで１列の基本変形が完了する。
【００９７】
以下、第２列基本変形後の行列対角化装置１００は図６、第３列基本変形後の行列対角化装置１００は図７、第４列基本変形後の行列対角化装置１００は図８に示すようになり、行列の対角化が完了する。
【００９８】
要探索、掃き出し回路１３０は具体的には図９のようになる。図９に示す構成は、行列が０か１の要素しか持たない場合の要探索、掃き出し回路である。
【００９９】
図９の要探索、掃き出し回路１３０は、セレクタ１３１、状態遷移保持部１３２、要行選択セレクタ１３３、要行保持部１３４、アンドゲート１３５、および掃き出し部１３６を主構成要素として有している。
【０１００】
図９の要探索、掃き出し回路１３０においては、まず対角化が開始したら、状態遷移保持部１３２において、要探索状態になる。
入力される行Ｓ１１に対し、対角化対象要素を取り出すためのセレクタ１３１を通り対角化対象列の要素Ｓ１２のみ取り出し、この対象要素が零の場合は、状態遷移保持部１３２は、要探索状態を維持し、要フラグＳ１３は０、掃き出しフラグＳ１４は０を出力する。
初めて対象要素Ｓ１２が非零要素であった場合、要フラグＳ１３は１、掃き出しフラグＳ１４は０を出力し、要行選択セレクタ１３３によって、入力行Ｓ１１が要行として要行保持部１０４に取り込まれる。また、状態遷移保持部１３２は要探索状態から掃き出し状態へ遷移する。
【０１０１】
掃き出し状態では、要フラグＳ１３は０を出力し、要行を要行保持部１３４に保持し続ける。
対象要素Ｓ１２が非零の場合、掃き出しフラグＳ１４に１を出力し、掃き出し部１３６で入力行と要行の排他的論理和が計算され、掃き出し部から行Ｓ１８が出力され行列メモリ１２０に書き込まれる。
対象要素Ｓ１２が零の場合は掃き出しフラグＳ１４に０を出力し、入力行Ｓ１１はそのままＳ１８へ出力され、再び行列メモリにその行が書き込まれる。掃き出しが完了すると、要探索状態へ戻るか、その行列の対角化が終了した場合はアイドル（ＩＤＬＥ）状態へ戻る。
【０１０２】
なお、行列が０か１以外の要素を持つ要探索、掃き出しは、要と掃き出し対象となる行の対象要素を比べ、掃き出し対象となる行の対角要素を要で割った値を、要行保持部の後段で掛け算して、掃き出すことにより実現される。
【０１０３】
以上説明したように、本実施形態によれば、行列対角化装置１００は、行インデックスメモリ１１０から順に行インデックスを読み出し、その行インデックスが指定する行を行列メモリ１２０から読み出し、要探索、掃き出し回路１３０において、その行の対角化の対象となる列の要素を見て、要探索、掃き出しを行う。具体的には、行列対角化装置１００は、対象となる列を要探索、掃き出す際、行インデックスメモリ１１０から行インデックスを先頭アドレスから順番に読み出し、読み出した行が要行にならなかった場合、その行インデックスを行インデックスメモリ１１０の先頭アドレスから順に書き込み、読み出した行が要行になった場合のみ、その行インデックスを行インデックスメモリ１１０の最後のアドレスに書き込む、結果要探索の対象となる行が未だ要になっていない行に限定されるように構成されていることから、行列を対角化する場合、各列の要素を、要探索か掃き出しのいずれかの対象とするだけでよく、高速な対角化が可能となる。
【０１０４】
なお、上述した説明では、列毎に対角化する例ついて説明したが、本発明は、列毎でなく行毎に対角化することも可能である。また、本発明は、０と１以外の要素を持つ行列でも適用できる。
【０１０５】
本発明の実施形態に係る行列対角化装置は、代数的手法を用いた誤り訂正符号技術を実現するための回路、たとえば適応的信頼性伝播（Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｎ：ＡＢＰ）復号器に応用できる。
【０１０６】
ＡＢＰ復号は、リードソロモン（Ｒｅａｄ−Ｓｏｌｏｍｏｎ：ＲＳ）符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号に対する復号法であり、ある伝送路から符号語を受信すると、その受信語をより信頼できる値に更新する。
【０１０７】
図１０は、デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた通信システムの構成例を示す図である。
【０１０８】
本通信システム２００は、ＲＳ符号化器２１０、インタリーバ２２０、は畳み込み符号器２３０、畳み込み符号の軟出力復号器２４０、デインタリーバ２５０、ＲＳ符号のＡＢＰ繰り返し復号器２６０、およびチャネル２７０を有する。
【０１０９】
本通信システム２００では、ＲＳ符号化、畳み込み符号化された送信語に対して、畳み込み符号の軟出力復号をした後にＡＢＰ復号を行っている。
ここで言う畳み込み符号の軟出力復号とは、たとえばＢＣＪＲアルゴリズムやＳＯＶＡによる復号のことである。
ＡＢＰ復号器２６０においては、ＡＢＰによる信頼性の更新後、硬判定後限界距離復号、リスト復号、もしくは、軟値をそのまま入力として軟判定リスト復号を行う。
【０１１０】
図１１は、ＭＡＰ復号が後段についたＡＢＰ復号器の構成例を示す図である。
この復号器３００は、図１１に示すように、ＡＢＰ復号部３１０、限界距離復号（ＢＤ）復号部３２０、受信信頼度（ＬＬＲ）保持部３３０、およびＭＡＰ復号部３４０を有している。
【０１１１】
復号器３００においては、ＡＢＰ復号部３１０による信頼性（ＬＬＲ）の更新後、硬判定してＢＤ復号部３２０において、限界距離復号を行い、この結果をリストに集め、最終的にＭＡＰ復号部３４０においてＭＡＰ（Ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  Ｐｒｏｂａｂｉ１１ｔｙ）復号を行う。
【０１１２】
図１２は、ＡＢＰ復号器の復号装置の構成例を示す図である。
【０１１３】
図１２のＡＢＰ復号器４００は、図１０のＡＢＰ復号器２６０や図１１のＡＢＰ復号部３１０に適用可能であり、ソート入力選択部４１０、ソート部４２０、パリティ検査行列の対角化部４３０、信頼度（ＬＬＲ）保持部４４０、および信頼性伝播（ＢＰ）部４５０を有している。
【０１１４】
ＡＢＰ復号器４００においては、入力として、受信ＬＬＲＳ４２が入力される。
列インデックスＳ４１は、入力された受信ＬＬＲの符号語の始まりからカウンタで０、１、２、３、、とカウントアップされた値を生成し利用する。
ソート入力選択部４１０で、初回は、列インデックスＳ４１とＳ４２を選択し、繰り返し二回目以降は信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）後、更新ＬＬＲＳ５０とその列インデックスＳ４９を選択する。
【０１１５】
図１２に示すように、受信語が入力されたら、まず、ソート部４２０において、その信頼度（ＬＬＲ）の大きさに応じて列インデックスのソートを行う。
次に、信頼度の低いシンボルに対応する列より順に、対角化部４３０でパリティ検査行列の対角化を行う。
最後に、対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）を行うことにより、値が更新される。
更新された値に対して、再びソート、対角化、信頼性伝播（ＢＰ）を行う。繰り返し数が予め決められており、その繰り返し数だけこれを繰り返す。
この復号器４００の対角化部４３０において、本発明の実施形態に係る対角化装置１００を適用することが可能である。
【０１１６】
なお、以上詳細に説明した行列の対角化方法は、上記手順に応じたプログラムとして形成し、ＣＰＵ等のコンピュータで実行するように構成することも可能である。
また、このようなプログラムは、半導体メモリ、磁気ディスク、光ディスク、フロッピー（登録商標）ディスク等の記録媒体、この記録媒体をセットしたコンピュータによりアクセスし上記プログラムを実行するように構成可能である。
【図面の簡単な説明】
【０１１７】
【図１】一般的な０か１のみの要素を持つ行列の対角化のフローチャートである。
【図２】本発明の実施形態に係る行列対角化方法を採用した行列対角化装置の基本的な構成例を示しブロック図である。
【図３】本実施形態に係るｍ行ｎ列行列の対角化方法を説明するためのフローチャートである。
【図４】第１列の基本変形のときの行インデックスメモリを示す図である。
【図５】第１列の基本変形が完了した対角化装置を示す図である。
【図６】第２列の基本変形が完了した対角化装置を示す図である。
【図７】第３列の基本変形が完了した対角化装置を示す図である。
【図８】第４列の基本変形が完了した対角化装置を示す図である。
【図９】本実施系形態に係る要探索、掃き出し回路の構成例を示す図である。
【図１０】本実施形態に係るＡＢＰ復号器を採用した通信システムの構成例を示す図である。
【図１１】ＭＡＰ復号が後段についたＡＢＰ復号器の構成例を示す図である。
【図１２】本実施形態に係る対角化装置を適用可能なＡＢＰ復号器の復号装置の構成例を示す図である。
【符号の説明】
【０１１８】
１００・・・行列対角化装置、１１０・・・行インデックスメモリ、１２０・・・行列メモリ、１３０・・・要探索・掃き出し回路、２００・・・通信システム、２１０・・・ＲＳ符号化器、２２０・・・インタリーバ、２３０・・・畳み込み符号器、２４０・・・畳み込み符号の軟出力復号器、２５０・・・デインタリーバ、２６０・・・ＲＳ符号のＡＢＰ繰り返し復号器、２７０・・・チャネル、３００・・・復号器、３１０・・・ＡＢＰ復号部、３２０・・・限界距離復号（ＢＤ）復号部、３３０・・・受信信頼度（ＬＬＲ）保持部、３４０・・・ＭＡＰ復号部、４００・・・ＡＢＰ復号器、４１０・・・ソート入力選択部、４２０・・・ソート部、４３０・・・パリティ検査行列の対角化部、４４０・・・信頼度（ＬＬＲ）保持部、４５０・・・信頼性伝播（ＢＰ）部。
【図１】
2008140336.tif 000033
【図２】
2008140336.tif 000034
【図３】
2008140336.tif 000035
【図４】
2008140336.tif 000036
【図５】
2008140336.tif 000037
【図６】
2008140336.tif 000038
【図７】
2008140336.tif 000039
【図８】
2008140336.tif 000040
【図９】
2008140336.tif 000041
【図１０】
2008140336.tif 000042
【図１１】
2008140336.tif 000043
【図１２】
2008140336.tif 000044