(57)【特許請求の範囲】
【請求項１】
符号長ｎ、ソースシンボル数ｋ（ｋはｎ未満）、及び列重みｗをパラメータセットとするＦｌａｔ  ＸＯＲ符号の設計方法であって、
複数のデータディスクを備える分散ストレージシステムにおいて所望のストレージ容量効率基準値及びディスク修復時の平均通信量基準値を符号選択条件として入力する符号選択条件入力手順と、
前記データディスクの総数を符号長ｎとし、符号長ｎで取り得るソースシンボル数の最大値をｋとし、前記データディスクのうち同時故障を修復可能とするデータディスク数を列重みｗとし、暫定的に前記パラメータセットの範囲を限定する範囲限定手順と、
前記範囲限定手順で限定した前記パラメータセットの範囲において、複数の符号構成法を用いてストレージ容量効率及びディスク修復時の平均通信量を算出する推定手順と、
前記推定手順で用いた前記符号構成法、並びに前記範囲限定手順で限定した前記パラメータセットの範囲の中から、前記推定手順で算出したストレージ容量効率及びディスク修復時の平均通信量の双方が前記符号選択条件入力手順で入力した前記符号選択条件を満たす符号構成法並びにパラメータセットの範囲を検出する範囲絞り込み手順と、
前記範囲絞り込み手順で検出した前記符号構成法を用いて前記範囲絞り込み手順で検出した前記パラメータセットの範囲で符号検索を行い、ストレージ容量効率が最大又はディスク修復時の平均通信量が最小となるＦｌａｔ  ＸＯＲ符号を決定する符号選択手順と、
を行うことを特徴とするＦｌａｔ  ＸＯＲ符号の設計方法。
【請求項２】
前記推定手順で用いられる符号構成法が、正則Ｆｌａｔ  ＸＯＲ符号を用いる正則構成法、非正則Ｆｌａｔ  ＸＯＲ符号を用いる規則的構成法、及び非正則Ｆｌａｔ  ＸＯＲ符号を用いるランダム構成法であることを特徴とする請求項１に記載のＦｌａｔ  ＸＯＲ符号の設計方法。
【請求項３】
符号長ｎ、ソースシンボル数ｋ（ｋはｎ未満）、及び列重みｗをパラメータセットとするＦｌａｔ  ＸＯＲ符号の設計装置であって、
複数のデータディスクを備える分散ストレージシステムにおいて所望のストレージ容量効率基準値及びディスク修復時の平均通信量基準値が符号選択条件として入力され、
前記データディスクの総数を符号長ｎとし、符号長ｎで取り得るソースシンボル数の最大値をｋとし、前記データディスクのうち同時故障を修復可能とするデータディスク数を列重みｗとし、暫定的に限定した前記パラメータセットの範囲を設定する設計条件入力部と、
前記設計条件入力部で設定された前記パラメータセットの範囲において、複数の符号構成法を用いてストレージ容量効率及びディスク修復時の平均通信量を算出する推定部と、
前記推定部が用いた前記符号構成法、並びに前記設計条件入力部に入力された前記パラメータセットの範囲の中から、前記推定部が算出したストレージ容量効率及びディスク修復時の平均通信量の双方が前記設計条件入力部に入力された前記符号選択条件を満たす符号構成法並びにパラメータセットの範囲を検出する条件限定部と、
前記条件限定部が前記符号構成法を用いて検出した前記パラメータセットの範囲で符号検索を行う符号検索部と、
前記符号検索部が行った符号検索の結果、ストレージ容量効率が最大又はディスク修復時の平均通信量が最小となるＦｌａｔ  ＸＯＲ符号を決定する符号選択部と、
を備えることを特徴とするＦｌａｔ  ＸＯＲ符号の設計装置。
【請求項４】
前記推定部は、
正則Ｆｌａｔ  ＸＯＲ符号を用いる正則構成法、非正則Ｆｌａｔ  ＸＯＲ符号を用いる規則的構成法、及び非正則Ｆｌａｔ  ＸＯＲ符号を用いるランダム構成法を前記符号構成法として用いることを特徴とする請求項３に記載のＦｌａｔ  ＸＯＲ符号の設計装置。
【請求項５】
請求項１又は２に記載のＦｌａｔ  ＸＯＲ符号の設計方法における各手順をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ストレージシステムにおいてデータを冗長化する符号化方法に関し、特に分散ストレージの設計条件に応じて複数のパラメータに基づきＦｌａｔ  ＸＯＲ符号の設計を行う方法、装置及びプログラムに関する。
【背景技術】
【０００２】
近年４Ｋ、８Ｋ映像やビッグデータ等の大容量データの利用増加および様々なデバイス・通信環境へのクラウド基盤を通じた伝送技術の発展に伴い、クラウド基盤を構成する分散ストレージの信頼性を高め効率的に容量を利用可能な消失訂正符号を用いた冗長化技術が注目されている（例えば、非特許文献１を参照。）。
【０００３】
先に発明者らは分散ストレージに非正則構成の部分行列を用いたＦｌａｔ  ＸＯＲ符号（以下、非正則Ｆｌａｔ  ＸＯＲ符号と記載する。）を適用することで、従来の複製等の技術と比較してストレージ容量の利用効率を高め、ディスク修復時に必要な通信量を削減する手法を提案している（非特許文献２を参照。）。また、符号長の大きな場合に適用可能な非正則Ｆｌａｔ  ＸＯＲの２つの構成法を提案した（非特許文献３を参照）。これらのＦｌａｔ  ＸＯＲ符号は構成法ごとに異なる特性を有するため、分散ストレージシステムにおいて最小化したいコストや実現したい信頼性レベルを考慮し、条件に応じたパラメータを設定した上で最適な冗長化手法および符号構成法を決定する必要がある（非特許文献３を参照。）。
なお、Ｆｌａｔ  ＸＯＲ符号のパリティ検査行列を構成する部分行列ＰＴにおいて行重みｐおよび列重みｗが一定であるものを「正則構成」、行重みｐ又は列重みｗに偏りを持たせたものを「非正則構成」と呼ぶ。Ｆｌａｔ  ＸＯＲ符号の生成行列Ｇおよびパリティ検査行列Ｈはｋ×ｋの単位行列Ｉｋおよびｎ−ｋ×ｎ−ｋの単位行列Ｉｎ−ｋを用いて、部分行列ＰＴに基づき式（１），式（２）で表される。
（数１）
Ｇ  ＝  ［  Ｐ  ｜  Ｉｋ  ］                                              （１）
（数２）
Ｈ  ＝  ［  ＰＴ  ｜  Ｉｎ−ｋ  ］                                        （２）
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｋ．  Ｇｒｅｅｎａｎ，  Ｘ．  Ｌｉ  ，  Ｗ．  Ｊ．Ｊ，  “Ｆｌａｔ  ＸＯＲ−ｂａｓｅｄ  ｅｒａｓｕｒｅ  ｃｏｄｅｓ  ｉｎ  ｓｔｏｒａｇｅ  ｓｙｓｔｅｍｓ：  Ｃｏｎｓｔｒｕｃｔｉｏｎｓ，  ｅｆｆｉｃｅｎｔ  ｒｅｃｏｖｅｒｙ，  ａｎｄ  ｔｒａｄｅｏｆｆｓ”，  Ｍａｓｓ  Ｓｔｏｒａｇｅ  Ｓｙｓｔｅｍｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｉｅｓ，  ２０１０  ＩＥＥＥ  ２６ｔｈ  Ｓｙｍｐｏｓｉｕｍ，  Ｉｎｃｌｉｎｅ  Ｖｉｌｌａｇｅ，  ＵＳＡ，  Ｍａｙ，  ２０１０．
【非特許文献２】吉田由唯，  外村喜秀，  白井大介，  藤井竜也，  “分散ストレージシステムのための通信量を削減するＦｌａｔ  ＸＯＲに基づく消失訂正符号の非正則構成”，  ２０１４信学ソ大（基礎・境界），  Ｔｏｋｕｓｈｉｍａ，  Ｊａｐａｎ，  Ｓｅｐｔ．  ２０１４．
【非特許文献３】吉田由唯，  仲地孝之，  白井大介，  藤井竜也，  “分散ストレージのための非正則Ｆｌａｔ  ＸＯＲ符号の構成法の評価”，  ２０１５  第３８回情報理論とその応用シンポジウム，  Ｏｋａｙａｍａ，  Ｊａｐａｎ，  Ｎｏｖ．  ２０１５．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、ストレージの信頼性や分散拠点数等の条件に基づくパラメータの組合せ数は膨大であり、全てのパラメータセットについて最適な符号を探索し評価を行うのは膨大な時間を要する。そこで、分散ストレージの設計において与えた条件に対して、各符号特性の簡易な評価を行い目的に応じた符号構成法およびパラメータの範囲を絞り込むため、正則および非正則Ｆｌａｔ  ＸＯＲ符号を用いた場合の容量効率およびディスク修復時通信量の推定手法を提案し、それらに基づく効率的なＦｌａｔ  ＸＯＲ符号の設計手順を提案する。
【０００６】
先に発明者らは、分散ストレージにおいて非正則Ｆｌａｔ  ＸＯＲ符号を用いてディスク修復時の通信量を削減する手法および非正則Ｆｌａｔ  ＸＯＲ符号の２種類の構成法を提案した（非特許文献３を参照。）。これらの符号構成法により１３０程度までの広範囲の符号長について通信量を削減する複数の非正則符号の設計が可能となった（非特許文献３を参照。）。
【０００７】
しかし、Ｆｌａｔ  ＸＯＲ符号は容量効率とディスク修復時の通信量にトレードオフ関係があり、各構成法に基づくＦｌａｔ  ＸＯＲ符号はこれらのトレードオフについて異なる符号特性を有することから、分散ストレージの利用目的に応じて適切な特性を有する符号および構成法を選択する必要がある（非特許文献３を参照。）。また、分散ストレージの設計において、ストレージに要求する信頼性や分散地点数、容量効率、平均通信量等の条件はストレージの用途に応じて様々である。これらの設計条件に応じてＦｌａｔ  ＸＯＲ符号設計時の符号長ｎ、ソースシンボル数ｋ、列重みｗ等の複数のパラメータが変化するため、パラメータの組合せ数が膨大な数となり、各パラメータセット（ｎ，ｋ，ｗ）に対して複数の構成法に基づく符号の探索および評価を行うと膨大な時間を要するという課題がある。
【０００８】
そこで、本発明は、上記課題を解決すべく、符号の探索および評価を短時間で行うことができるＦｌａｔ  ＸＯＲ符号の設計方法、設計装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明に係るＦｌａｔ  ＸＯＲ符号の設計方法、設計装置及びプログラムは、分散ストレージの利用目的に応じて符号設計パラメータおよび符号構成法の絞り込み、その後に符号探索を行うことで高速に広範囲の条件に対して符号を設計することとした。また、符号構成法の絞り込みのために、正則および非特許文献３で提案した非正則Ｆｌａｔ  ＸＯＲ符号を用いた場合に取り得る最大容量効率およびディスク修復時平均通信量を、与えたパラメータに基づき符号探索のシミュレーションを伴わずに推定することとした。
【００１０】
具体的には、本発明に係るＦｌａｔ  ＸＯＲ符号の設計方法は、符号長ｎ、ソースシンボル数ｋ（ｋはｎ未満）、及び列重みｗをパラメータセットとするＦｌａｔ  ＸＯＲ符号の設計方法であって、
複数のデータディスクを備える分散ストレージシステムにおいて所望のストレージ容量効率基準値及びディスク修復時の平均通信量基準値を符号選択条件として入力する符号選択条件入力手順と、
前記データディスクの総数を符号長ｎとし、符号長ｎで取り得るソースシンボル数の最大値をｋとし、前記データディスクのうち同時故障を修復可能とするデータディスク数を列重みｗとし、暫定的に前記パラメータセットの範囲を限定する範囲限定手順と、
前記範囲限定手順で限定した前記パラメータセットの範囲において、複数の符号構成法を用いてストレージ容量効率及びディスク修復時の平均通信量を算出する推定手順と、
前記推定手順で用いた前記符号構成法、並びに前記範囲限定手順で限定した前記パラメータセットの範囲の中から、前記推定手順で算出したストレージ容量効率及びディスク修復時の平均通信量の双方が前記符号選択条件入力手順で入力した前記符号選択条件を満たす符号構成法並びにパラメータセットの範囲を検出する範囲絞り込み手順と、
前記範囲絞り込み手順で検出した前記符号構成法を用いて前記範囲絞り込み手順で検出した前記パラメータセットの範囲で符号検索を行い、ストレージ容量効率が最大又はディスク修復時の平均通信量が最小となるＦｌａｔ  ＸＯＲ符号を決定する符号選択手順と、
を行うことを特徴とする。
【００１１】
また、本発明に係るＦｌａｔ  ＸＯＲ符号の設計装置は、符号長ｎ、ソースシンボル数ｋ（ｋはｎ未満）、及び列重みｗをパラメータセットとするＦｌａｔ  ＸＯＲ符号の設計装置であって、
複数のデータディスクを備える分散ストレージシステムにおいて所望のストレージ容量効率基準値及びディスク修復時の平均通信量基準値が符号選択条件として入力され、
前記データディスクの総数を符号長ｎとし、符号長ｎで取り得るソースシンボル数の最大値をｋとし、前記データディスクのうち同時故障を修復可能とするデータディスク数を列重みｗとし、暫定的に限定した前記パラメータセットの範囲を設定する設計条件入力部と、
前記設計条件入力部で設定された前記パラメータセットの範囲において、複数の符号構成法を用いてストレージ容量効率及びディスク修復時の平均通信量を算出する推定部と、
前記推定部が用いた前記符号構成法、並びに前記設計条件入力部に入力された前記パラメータセットの範囲の中から、前記推定部が算出したストレージ容量効率及びディスク修復時の平均通信量の双方が前記設計条件入力部に入力された前記符号選択条件を満たす符号構成法並びにパラメータセットの範囲を検出する条件限定部と、
前記条件限定部が前記符号構成法を用いて検出した前記パラメータセットの範囲で符号検索を行う符号検索部と、
前記符号検索部が行った符号検索の結果、ストレージ容量効率が最大又はディスク修復時の平均通信量が最小となるＦｌａｔ  ＸＯＲ符号を決定する符号選択部と、
を備えることを特徴とする。
【００１２】
Ｆｌａｔ  ＸＯＲ符号のパラメータセット（ｎ，ｋ，ｗ）は、分散ストレージの設計条件である程度範囲が定まる。このため、分散ストレージの設計条件に基づいて各パラメータが取り得る値の範囲と所望の容量効率およびディスク修復時の平均通信量（以下、平均通信量と記載することがある。）の基準値を予め決定しておく。そして、当該範囲の各パラメータに対して、いくつかの符号構成法で各符号の容量効率および平均通信量を推定する。そして、推定した容量効率および平均通信量から前記基準値を満たすものを検出し、その容量効率および平均通信量を推定したパラメータセットを検出する。この時点でパラメータセットは大幅に限定される。最後にこの限定されたパラメータセットの中から容量効率が最大且つ通信量が最小のパラメータセットを１つ選択する。このようにパラメータセットを段階的に絞り込むことで符号の探索および評価を短縮することができる。
【００１３】
従って、本発明は、符号の探索および評価を短時間で行うことができるＦｌａｔ  ＸＯＲ符号の設計方法及び設計装置を提供することができる。
【００１４】
本発明に係るＦｌａｔ  ＸＯＲ符号の設計方法及び設計装置は、前記推定手順で用いられる符号構成法が、正則Ｆｌａｔ  ＸＯＲ符号を用いる正則構成法、非正則Ｆｌａｔ  ＸＯＲ符号を用いる規則的構成法、及び非正則Ｆｌａｔ  ＸＯＲ符号を用いるランダム構成法であることを特徴とする。
【００１５】
本発明は、前記Ｆｌａｔ  ＸＯＲ符号の設計方法における各手順をコンピュータに実行させるためのプログラムである。本発明の設計装置はコンピュータと当該プログラムによっても実現でき、当該プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【発明の効果】
【００１６】
本発明は、符号の探索および評価を短時間で行うことができるＦｌａｔ  ＸＯＲ符号の設計方法、設計装置及びプログラムを提供することができる。
【図面の簡単な説明】
【００１７】
【図１】Ｆｌａｔ  ＸＯＲ符号に基づく分散ストレージを説明するモデル図である。
【図２】本発明に係るＦｌａｔ  ＸＯＲ符号の設計方法を説明するフローチャートである。
【図３】本発明に係るＦｌａｔ  ＸＯＲ符号の設計方法で推定したストレージのとりうる推定最大容量効率を説明する図である。
【図４】本発明に係るＦｌａｔ  ＸＯＲ符号の設計方法で推定したディスク修復時の平均通信量およびシミュレーションに基づく平均通信量を比較した図である。
【図５】本発明に係るＦｌａｔ  ＸＯＲ符号の設計装置を説明する構成図である。
【図６】全探索可能な範囲の非正則の部分行列ＰＴの構成方法を説明する図である。
【図７】規則的構成法によって構成した非正則の部分行列ＰＴの一例を示す。
【図８】ランダム構成法によって構成した非正則の部分行列ＰＴの一例を示す。
【発明を実施するための形態】
【００１８】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施例であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００１９】
図１は、Ｆｌａｔ  ＸＯＲ符号に基づく分散ストレージのモデルを説明する図である。分散ストレージを構成する全ディスク数をｎ、最大同時故障数をｗとする。符号化装置１０は、データ分割部１１と、符号化部１２と、データ分配部１３と、を備える。データ分割部１１は、保存するデータをｋ個の断片に分割する。符号化部１２は、生成行列Ｇに基づいて選択したｗ個の前記断片のＸＯＲによりｎ−ｋ個のパリティを生成する。データ分配部１３は、ｋ個の断片とｎ−ｋ個のパリティ（これらｎ個の断片を符号化した断片という）を各ディスク２０に１つずつ均等に保存する。復号装置（不図示）は、部分行列ＰＴおよび単位行列からなる非正則パリティ検査行列Ｈを用いて、複数のディスク２０に格納されているデータの修復を行う。Ｆｌａｔ  ＸＯＲ符号の生成行列Ｇおよびパリティ検査行列Ｈの構成に用いる部分行列ＰＴはＦｌａｔ  ＸＯＲ符号の設計装置３０１より提供される。
【００２０】
従来、分散ストレージにＦｌａｔ  ＸＯＲ符号を用いる場合、符号長ｎ、ソースシンボル数ｋ、列重みｗ等の複数のパラメータの組合せごとに各構成法に基づく符号を設計、探索、及び評価を行っていた。このため、符号を決定するまでには広範囲なパラメータの組合せがあり、ストレージの目的に応じた符号を設計することは容易ではなかった。なお、Ｆｌａｔ  ＸＯＲ符号の設計装置３０１では、最大同時故障数と列重みとがｗで一致している。
【００２１】
本発明は、符号探索の前に、符号長ｎ、ソースシンボル数ｋ、列重みｗからなるパラメータセットに対して各符号の取り得る最大容量効率および平均通信量の推定値を求め、分散ストレージに求める条件を満たす符号構成法およびパラメータ範囲を限定し、それらについてのみ符号探索を行うことにより幅広い条件に対する符号設計を短時間で実現可能とする。
【００２２】
探索を行う符号構成法とパラメータの範囲を絞り込むため、分散ストレージの利用目的等に応じてストレージを構成する総ディスク数（＝符号長ｎ）・信頼性（＝最大同時故障数）等の設計条件、およびストレージ容量効率・平均通信量の基準値等の符号選択条件を設定する。設計条件を満たす範囲のパラメータセットに対して、正則Ｆｌａｔ  ＸＯＲ符号および非特許文献３で提案した各構成法に基づく非正則Ｆｌａｔ  ＸＯＲ符号を用いた場合に取り得るストレージの最大容量効率およびディスク修復時の平均通信量を推定し、符号選択条件を満たす符号構成法およびパラメータセットを絞り込んだ上で符号探索を行う。
【００２３】
（具体的な実施形態）
図５は、本実施形態のＦｌａｔ  ＸＯＲ符号の設計装置３０１を説明する図である。設計装置３０１は、符号長ｎ、ソースシンボル数ｋ（ｋはｎ未満）、及び列重みｗをパラメータセットとするＦｌａｔ  ＸＯＲ符号の設計装置であって、
複数のデータディスクを備える分散ストレージシステムにおいて所望のストレージ容量効率基準値及びディスク修復時の平均通信量基準値が符号選択条件として入力され、
前記データディスクの総数を符号長ｎとし、符号長ｎで取り得るソースシンボル数の最大値をｋとし、前記データディスクのうち同時故障を修復可能とするデータディスク数を列重みｗとし、暫定的に限定した前記パラメータセットの範囲を設定する設計条件入力部５１と、
設計条件入力部５１で設定された前記パラメータセットの範囲において、複数の符号構成法を用いてストレージ容量効率及びディスク修復時の平均通信量を算出する推定部５２と、
推定部５２が用いた前記符号構成法、並びに前記設計条件入力部に入力された前記パラメータセットの範囲の中から、推定部５２が算出したストレージ容量効率及びディスク修復時の平均通信量の双方が設計条件入力部５１に入力された前記符号選択条件を満たす符号構成法並びにパラメータセットの範囲を検出する条件限定部５３と、
条件限定部５３が前記符号構成法を用いて検出した前記パラメータセットの範囲で符号検索を行う符号検索部５４と、
符号検索部５４が行った符号検索の結果、ストレージ容量効率が最大又はディスク修復時の平均通信量が最小となるＦｌａｔ  ＸＯＲ符号を決定する符号選択部５５と、
を備える。
【００２４】
推定部５２は、容量効率推定部５２ａと通信量推定部５２ｂからなる。符号選択部５５は、選択部５５ａ、符号特性評価部５５ｂ及び符号データ保持部５５ｃからなる。そして決定されたＦｌａｔ  ＸＯＲ符号が符号出力部５６から出力される。
【００２５】
さらに、細かい動作を説明していく。本実施形態では、図２に示すように、以下の手順１）〜４）によりＦｌａｔ  ＸＯＲ符号の設計を行う。
【００２６】
１）  分散ストレージの設計条件および符号選択条件の決定
ステップＳ２−１は、複数のデータディスクを備える分散ストレージシステムにおいて所望のストレージ容量効率基準値及びディスク修復時の平均通信量基準値を符号選択条件として入力する符号選択条件入力手順である。
設計者は、ストレージの信頼性やコストを考慮し、分散ストレージの設計条件としてストレージを構成する総ディスク数ｎ、および修復可能な同時故障ディスク数ｗの基準値を決定し、入力する。また、分散ストレージ構築において最小化したいコストに基づき、達成したいストレージ容量効率の基準値Ｖ（７５（％）以上など）または平均通信量の基準値（１０（ＴＢ）以下など）を決定し、入力する。
【００２７】
２）  符号探索パラメータ範囲の限定
ステップＳ２−２は、前記データディスクの総数を符号長ｎとし、符号長ｎで取り得るソースシンボル数の最大値をｋとし、前記データディスクのうち同時故障を修復可能とするデータディスク数を列重みｗとし、暫定的に前記パラメータセットの範囲を限定する範囲限定手順である。
決定したストレージの設計条件（分散ストレージを構成するディスク数ｎ、修復可能な同時故障ディスク数ｗの基準値等）に基づき、Ｆｌａｔ  ＸＯＲ符号のパラメータセット（符号長ｎ、ソースシンボル数ｋ、列重みｗ）の各パラメータが取り得る値の範囲を決定する（ステップＳ２−２）。具体的には、分散ストレージを構成するディスク数ｎとＦｌａｔ  ＸＯＲ符号の符号長ｎが一致することから、ストレージの設計条件としてディスク数ｎの範囲を与えることにより符号長ｎの範囲が一意に決定する。また、信頼性に関しては、ストレージを構成するｎディスク中任意のｗディスクまでの同時故障を修復可能とする条件において、Ｆｌａｔ  ＸＯＲ符号の列重みをｗ以上に限定する（ステップＳ２−２）。また、ソースシンボル数ｋに関しては、達成したいストレージ容量効率の基準値Ｖを用い、ｋ＝ｎ×Ｖ（％）／１００として決定する。
【００２８】
３）  パラメータセットおよび符号選択条件に基づく符号特性推定および符号構成法の決定
ステップＳ２−３及びステップＳ２−４は、前記範囲限定手順で限定した前記パラメータセットの範囲において、複数の符号構成法を用いてストレージ容量効率及びディスク修復時の平均通信量を算出する推定手順である。ステップＳ２−５は、前記推定手順で用いた前記符号構成法、並びに前記範囲限定手順で限定した前記パラメータセットの範囲の中から、前記推定手順で算出したストレージ容量効率及びディスク修復時の平均通信量の双方が前記符号選択条件入力手順で入力した前記符号選択条件を満たす符号構成法並びにパラメータセットの範囲を検出する範囲絞り込み手順である。
ステップＳ２−１及びステップＳ２−２で決定したパラメータ範囲及び符号選択条件が設計条件入力部５１に入力される。これらに基づいて、推定部５２は各符号の容量効率および平均通信量を推定し、条件限定部５３は符号選択条件を満たす符号構成法およびパラメータセットを絞り込む。
【００２９】
３−１）  パラメータセットに基づく各符号の容量効率の推定
容量効率推定部５２ａは、正則および非正則Ｆｌａｔ  ＸＯＲ符号の取り得る最大容量効率を以下の符号構成法により各パラメータセットについて推定する（ステップＳ２−３）。例えば、符号構成法は、正則Ｆｌａｔ  ＸＯＲ符号を用いる正則構成法、非正則Ｆｌａｔ  ＸＯＲ符号を用いる規則的構成法、及び非正則Ｆｌａｔ  ＸＯＲ符号を用いるランダム構成法である。条件限定部５３は、符号選択条件を満たす符号構成法および符号長ｎ、ソースシンボル数ｋ、列重みｗの範囲を決定する（ステップＳ２−５）。
【００３０】
●正則Ｆｌａｔ  ＸＯＲ符号の容量効率推定
容量効率推定部５２ａは、符号長ｎ、ソースシンボル数ｋ、列重みｗのパラメータセットに対し、正則符号を用いた場合のストレージの取り得る最大容量効率を以下の手順で推定する（ステップＳ２−３）。
【００３１】
正則Ｆｌａｔ  ＸＯＲ符号の行重みを定数Ｅとしたとき、行列内に含まれる１の総数は以下の式（３）で表すことができる。
（数３）
ｗ×ｋ                                                              （３）
また、正則行列は行重みＥが一定であることから式（４）も行列内に含まれる１の総数を表す。
（数４）
Ｅ×（ｎ−ｋ）                                                    （４）
式（３）、（４）より式（５）が成り立つ。
（数５）
ｗ×ｋ＝Ｅ×（ｎ−ｋ）                                            （５）
これより、正則符号を構成可能なｋは定数Ｅを用いて式（６）で表される。
【数６】
0006470200.tif 000002
ｎ、ｗ、ｋ、Ｅは整数値をとることから、式（６）によりｎ、ｗを与えた場合に正則Ｆｌａｔ  ＸＯＲ符号を構成可能なｋの範囲が定まる。また、行列の列数の条件より式（７）を満たす。
（数７）
ｋ≧ｎ−ｋＣｗ                                                    （７）
以上の条件を満たし符号を構成可能なｋの最大値を用いて、最大容量効率はｋ／ｎ×１００（％）と推定できる。
【００３２】
●非正則Ｆｌａｔ  ＸＯＲ符号の容量効率推定
容量効率推定部５２ａは、符号長ｎ、ソースシンボル数ｋ、列重みｗのパラメータセットに対し、規則的構成法およびランダム構成法に基づく非正則符号を用いた場合のストレージの取り得る最大容量効率を以下の手順で推定する（ステップＳ２−３）。なお、規則的構成法およびランダム構成法の詳細については後述する。
【００３３】
ａ）  規則的構成法に基づく非正則符号の最大容量効率推定
規則的構法において行重みｐ＝１として非正則符号を構成する場合（非特許文献３）、重複なく列を構成するには行列のｐ＋１行目からｎ−ｋ行目までの領域に１をｗ−１個配置する組合せおよびｐの積がｋ以上となる必要があるため、ｋは式（８）を満たす値に制限される。
（数８）
ｋ≦ｘ×ｎ−ｋ−ｘＣｗ−１                                        （８）
以上の条件を満たし符号を構成可能なｋの最大値を求め、最大容量効率をｋ／ｎ×１００（％）により推定する。
【００３４】
ｂ）  ランダム構成法に基づく非正則符号の最大容量効率推定
ランダム構成法において非正則符号を構成する場合（非特許文献３）、行列の１行目に配置した１の数をＷとすると、ｋは式（９）、（１０）を満たす必要がある。
（数９）
Ｗ≦ｎ−ｋ−１Ｃｗ−１                                            （９）
（数１０）
ｋ−Ｗ≦ｎ−ｋＣｗ                                              （１０）
また、ｋがｋ＝ｎ−ｋＣｗを満たす場合、部分行列ＰＴが必ず正則構成となるため、ｋは式（１１）の制限を受ける。
（数１１）
ｋ≠ｎ−ｋＣｗ                                                    （１１）
以上の条件から、Ｗを変えて式（９）、（１０）、（１１）を満たすｋの最大値を求め、最大容量効率をｋ／ｎ×１００（％）により推定する。
【００３５】
３−２）  パラメータセットに基づく各符号の平均通信量の推定
通信量推定部５２ｂは、正則および非正則Ｆｌａｔ  ＸＯＲ符号のディスク修復時の平均通信量を以下の方法によりパラメータセットに基づき推定する（ステップＳ２−４）。条件限定部５３は、符号選択条件を満たす符号構成法および符号長ｎ、ソースシンボル数ｋ、列重みｗの範囲を決定する（ステップＳ２−５）。
【００３６】
●正則Ｆｌａｔ  ＸＯＲ符号の平均通信量推定
通信量推定部５２ｂは、符号長ｎ、ソースシンボル数ｋ、列重みｗのパラメータセットに対し、正則符号を用いた場合の平均通信量を部分行列の平均行重みに基づき推定する（ステップＳ２−４）。正則符号の場合、各行の行重みＥが一定であり、式（１２）で表される（非特許文献３）。
【数１２】
0006470200.tif 000003
正則符号において、行列中のいずれの行を修復式として用いた場合もＥ−１ディスク分の通信量が発生するため、Ｅ−１を平均通信量の推定値とする。
【００３７】
●非正則Ｆｌａｔ  ＸＯＲ符号の平均通信量推定
通信量推定部５２ｂは、符号長ｎ、ソースシンボル数ｋ、列重みｗのパラメータセットに対し、非特許文献３で提案した非正則Ｆｌａｔ  ＸＯＲ符号の規則的構成法およびランダム構成法を用いた場合の平均通信量を以下の方法により行列の行重みに基づき推定する（ステップＳ２−４）。なお、規則的構成法およびランダム構成法の詳細については後述する。
【００３８】
ａ）  規則的構成法に基づく非正則符号の通信量推定
規則的構成法の場合、１〜ｘ行目の平均行重みはｋ／ｘ、ｘ＋１行目以降の平均行重みＥは式（１３）で表される。なお、ｘは規則的構成法において指定した行番号である。
【数１３】
0006470200.tif 000004
Ｆｌａｔ  ＸＯＲ符号の復号においてＲｅｃｏｖｅｒｙ  Ｅｑｕａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍを用いることから、行重みの大きい１〜ｘ行目の行は他の行とのＸＯＲにより行重みの小さい修復式に変えて用いられる可能性が高い。そこで、行重みの小さいｘ＋１行目以降の平均行重みＥを求め、これらの行を用いて修復を行った場合の通信量Ｅ−１を規則的構成法における通信量の推定値とする。
【００３９】
ｂ）  ランダム構成法に基づく非正則符号の通信量推定
ランダム構成法の場合、１行目の平均行重みをＷとすると、２行目以降の平均行重みＥ２は式（１４）で表される。
【数１４】
0006470200.tif 000005
全行の平均行重みＥは式（１５）で表される。規則的構成法の場合と同様にＥ−１を平均通信量の推定値とする。
【数１５】
0006470200.tif 000006
【００４０】
３−３）  符号選択条件に基づく符号構成法の決定
条件限定部５３は、上記３−１）および３−２）に基づき得た推定容量効率および平均通信量が符号選択条件を満たすＦｌａｔ  ＸＯＲ符号の構成法およびパラメータセットの範囲を決定する（ステップＳ２−５）。
【００４１】
４）  選択した構成法に基づく符号の探索
ステップＳ２−６及びステップＳ２−７は、前記範囲絞り込み手順で検出した前記符号構成法を用いて前記範囲絞り込み手順で検出した前記パラメータセットの範囲で符号検索を行い、ストレージ容量効率が最大又はディスク修復時の平均通信量が最小となるＦｌａｔ  ＸＯＲ符号を決定する符号選択手順である。
符号探索部５４は、上記３）において選択した構成法およびパラメータセットの範囲において、各符号構成法（非特許文献３）に基づき任意の回数を上限とする符号探索を行う（ステップＳ２−６）。符号特性評価部５５ｂは、符号探索部５４が探索したＦｌａｔ  ＸＯＲ符号それぞれについて容量効率、平均通信量の少なくとも一方を評価する。符号データ保持部５５ｃは、Ｆｌａｔ  ＸＯＲ符号と符号特性評価部５５ｂが評価した結果を保持する。選択部５５ａは、符号データ保持部５５ｃが保持するＦｌａｔ  ＸＯＲ符号の中から容量効率が最大または平均通信量が最小となるＦｌａｔ  ＸＯＲ符号を決定する（ステップＳ２−７）。符号出力部５６は決定されたＦｌａｔ  ＸＯＲ符号を出力する。
【００４２】
［実施例］
具体的な数値でＦｌａｔ  ＸＯＲ符号の設計装置３０１の動作を説明する。
【００４３】
（ステップＳ２−１）
容量が１（ＴＢ）のディスクｎ個で構成される分散ストレージシステムにおいて、提案法を用いて符号設計を行った。分散ストレージの設計条件として、ディスク数ｎを様々に変更し、ｎ＝２６、４２、６４、９３、１３０の場合を検討することとした。また、ストレージシステムの信頼性は３ディスクまでの同時故障を修復可能であることを条件とした。したがって符号の列重みはｗ＝３とした。
分散ストレージのコスト要因において容量効率および障害時修復通信量を重視し、符号選択条件としてストレージ容量効率８０％以上、平均通信量１０（ＴＢ）以下という基準を設定した。
【００４４】
（ステップＳ２−２）
以上の条件のパラメータセットｎ、ｗにおいて、まず正則および非正則Ｆｌａｔ  ＸＯＲ符号の各構成法においてｎを与えた場合に取り得るｋの最大値を用いることにする。
【００４５】
（ステップＳ２−３）
容量効率推定部５２ａは、規則的構成法（ｘ＝１、ｐ＝１）、規則的構成法（ｘ＝２、ｐ＝１）、ランダム構成法及び正則構成法で最大容量効率を推定する。図３は推定結果である。その結果、ｎ≧５０のランダム構成法および正則構成法、ｎ≧６４の全ての構成法で容量効率８０％以上を達成しうることがわかった。
【００４６】
（ステップＳ２−４）
通信量推定部５２ｂは、規則的構成法（ｘ＝１、ｐ＝１）、規則的構成法（ｘ＝２、ｐ＝１）、ランダム構成法及び正則構成法で正則および非正則Ｆｌａｔ  ＸＯＲ符号の平均通信量を推定する。図４は推定結果である。その結果、ｎ＝２６の非正則構成およびｎ＝４２の規則的構成法（ｘ＝１または２、ｐ＝１）、ｎ＝６４の規則的構成法（ｘ＝１、ｐ＝１）において平均通信量１０（ＴＢ）以下を達成しうることがわかった。
【００４７】
（ステップＳ２−５〜ステップＳ２−７）
以上の容量効率および平均通信量の推定結果から、ｎ＝６４の規則的構成法（ｘ＝１、ｐ＝１、ｋは最大値の場合）が符号選択条件を満たすことが分かった。したがって、当該構成法およびパラメータセットで符号探索を行い、所望条件を満たすＦｌａｔ  ＸＯＲ符号を決定した。
【００４８】
以上のようにＦｌａｔ  ＸＯＲ符号の設計装置３０１は、符号探索を行うパラメータセットおよび構成法を絞り込み、ストレージ設計条件を満たす符号の設計に要する時間を短縮した。
【００４９】
また、Ｆｌａｔ  ＸＯＲ符号の設計装置３０１が推定したディスク修復時の平均通信量の評価のため、シミュレーションにより各符号構成法に基づく符号を１００回構成した場合の平均通信量を求めてＦｌａｔ  ＸＯＲ符号の設計装置３０１の推定値との比較を行った。図４は、ｗ＝３とし、符号長ｎを様々に変えた場合の最大ソースシンボル数ｋにおけるＦｌａｔ  ＸＯＲ符号の設計装置３０１の推定通信量とシミュレーションによる平均通信量を比較した図である。図４において各マーカーは次を意味する。
Ｆｌａｔ  ＸＯＲ符号の設計装置３０１の推定通信量
○：規則的構成法（ｘ＝１、ｐ＝１）
×：規則的構成法（ｘ＝２、ｐ＝１）
+：ランダム構成法
◇：正則符号
シミュレーションによる平均通信量
□：規則的構成法（ｘ＝１、ｐ＝１）
△：規則的構成法（ｘ＝２、ｐ＝１）
▽：ランダム構成法
☆：正則符号
図４より、正則および非正則Ｆｌａｔ  ＸＯＲ符号を用いた場合の通信量推定値はシミュレーションによる平均値とほぼ一致している。
【００５０】
（部分行列構成装置）
ここで、図１の符号化部１２の動作について説明する。符号化部１２は、部分行列構成装置として機能し、非正則構成の部分行列ＰＴを構成する。本実施形態では、ストレージシステムを構成する全ディスク数を符号長に等しいｎ、データの分割数をｋ、パリティディスク数をｎ−ｋ、符号の最小距離をｗとする。ｎ−ｋ行ｋ列のゼロ行列をＺとする。
【００５１】
符号長ｎがある程度小さく、ｎ−ｋ及びｗの組み合わせからｋ種類を選ぶ全組み合わせについて全探索可能である場合、ｋ−ｎ行ｎ列のゼロ行列Ｚを作成し、Ｚの各列について探索した組み合わせに相当する行の値を１とする。そして、構成した行列の中で、任意のｆ列｛ｆ＝１，２，・・・，ｗ｝を修復可能な行列のうち、最も平均通信量の小さい行列を選択し部分行列ＰＴとすればよい。
【００５２】
図６に、当該構成法によって構成した非正則部分行列ＰＴの一例を示す。ｎ＝１６、ｋ＝１０、ｗ＝３の場合を示す。部分行列の各列について、ｎ−ｋ行からｗ行を選ぶ組合せは列内で１を配置する行の組合せとなる。ｎ−ｋ＝６、ｗ＝３の場合、各列内の１の配置パターン数は図に示すようにｎ−ｋＣｗとなり、２０通り存在する。２０通りの配置パターンからｋ列分を選択することで部分行列を構成するため、とりうる部分行列候補数は２０Ｃｋとなる。ｋ＝１０であるため、とりうる部分行列候補数は１８４７５６通りとなる。ｆ＝２とすると、その中の２つの部分行列候補である行列（１）および行列（１８４７５６）が、部分行列ＰＴとなる。
【００５３】
ところが、符号長ｎが大きい場合、ｎ−ｋ及びｗの組み合わせからｋ種類を選ぶ数が非常に大きくなるため、上記構成法を用いて部分行列ＰＴを構成することができない。符号長ｎが大きい場合、次の２つの構成方法で部分行列ＰＴを構成することになる。
【００５４】
［規則的構成法の説明］
本構成方法は、部分行列を２つの領域に分割し、列重みを割り振ることで探索範囲に制約をつけ、非正則の部分行列を構成する。具体的には、以下の手順で非正則の部分行列ＰＴを構成する。
【００５５】
符号化部１２は、ゼロ行列作成ステップを実行するゼロ行列作成部と、所定行構成ステップを実行する所定行構成部と、行列構成ステップを実行する行列構成部と、を備える。ゼロ行列作成ステップにおいてステップＳ１０１を実行し、所定行構成ステップにおいてステップＳ１０２及びＳ１０３を実行し、行列構成ステップにおいてステップＳ１０４及びＳ１０５を実行する。
【００５６】
ステップＳ１０１：
ｎ−ｋ行ｋ列のゼロ行列Ｚを作成する。例えば、ｎ＝１６、ｋ＝１０、ｗ＝３の場合、図７に示すように、ゼロ行列Ｚは６行１０列となる。
【００５７】
ステップＳ１０２：
行重みに偏りを持たせるため、１行目からｘ行目までの行重みをｐとおき、式（１６）を満たす［ｘ，ｐ］をすべて求める。
（数１６）
ｘＣｐ×ｎ−ｋ−ｘＣｗ−ｐ≧ｋ                                      （１６）
ただし、ｘ＞ｐである。
例えば、ｎ＝１６、ｋ＝１０、ｗ＝３の場合、［ｘ，ｐ］の組み合わせは［１，１］、［２，１］、［４，２］、［５，２］、［６，３］となる。［１，１］の場合は１行目、［２，１］の場合は２行目が所定行となる。
【００５８】
ステップＳ１０３：
Ｚの１行目からｘ行目までの範囲に列重みｐとなるように１を配置した行列をＺ３とする。ｘＣｐの組み合わせにより各列において１となる行を決定する。例えば、列重みがｐ＝１であるとする。
ｘ＝１のとき、Ｚ３１に示すように、１行目に「１１１１１１１１１１」が配置されている。
ｘ＝２のとき、Ｚ３２に示すように、１行目に「１０１０１０１０１０」が配置され、２行目に「０１０１０１０１０１」が配置されている。
【００５９】
ステップＳ１０４：
Ｚ３のｘ＋１行目からｎ−ｋ行目までの範囲に列重みｗ−ｐとなるように以下の方法で１を配置する。ｎ−ｋ−ｘＣｗ−ｐ≦ｋの場合、１列目からｎ−ｋ−ｘＣｗ−ｐ行目までの範囲に、ｎ−ｋ−ｘＣｗ−ｐの組み合わせにより各列において１となる行を決定した行列Ｂを置き、ｒ（ｎ−ｋ−ｘＣｗ−ｐ）＋１列目から２ｒ（ｎ−ｋ−ｘＣｗ−ｐ）列目にＢをｒ列｛ｒ＝１，２，…，ｘ−１｝循環させた行列Ｂｒを置く。Ｂｒの列数合計がｋを超える場合はランダムにｋ列を選択しＺ３の１列目からｋ列目に配置する。
例えば、列重みｐ＝１であるとすると、ｗ＝３であるため、列重みｗ−ｐは２となる。
ｘ＝１のとき、Ｚ４１に示すように、２行目から６行目までの各列に「１」を２つずつ配置する。
ｘ＝２のとき、Ｚ４２に示すように、１列目から順に、３行目から６行目までの各列に「１」を２つずつ配置する。このとき、各列に「１」を２つずつ配置する組み合わせは６列目で終了する。この場合、７列目以降は、１行目及び２行目の「１」の配置との組み合わせが１列目から６列目までと異なるように、２行目から６行目までの各列に「１」を２つずつ配置する。
【００６０】
ステップＳ１０５：
構成した行列の中で任意のｆ｛ｆ＝１，２，・・・，ｗ｝列を修復可能な行列を部分行列ＰＴとする。例えば、Ｚ４１及びＺ４２の両方が部分行列ＰＴとなる。
【００６１】
規則的構成法を用いることで非正則の部分行列ＰＴを構成することができる。なお、本実施形態では「所定行」が１行目及び２行目である例を示したが、「所定行」は２行目以降の任意の行であってもよい。
【００６２】
［ランダム構成法の説明］
符号長ｎが大きく、ステップＳ１０２において式（１６）を満たす［ｘ，ｐ］の組合せが［ｘ，ｐ］＝［ｎ−ｋ，ｗ］のみである場合等において、ｘＣｐの組合せ数が大きくなり、規則的構成法で部分行列ＰＴを構成することができない。そこで、部分行列の１行目の行重みが平均行重み以上となるように構成することで、残りｎ−ｋ−１行の探索範囲を制限し、非正則の部分行列ＰＴを構成する。具体的には、以下の手順で非正則の部分行列ＰＴを構成する。
【００６３】
符号化部１２は、ゼロ行列作成ステップを実行するゼロ行列作成部と、特定行構成ステップを実行する特定行構成部と、行列構成ステップを実行する行列構成部と、を備える。ゼロ行列作成ステップにおいてステップＳ２０１を実行し、特定行構成ステップにおいてステップＳ２０２及びＳ２０３を実行し、行列構成ステップにおいてステップＳ２０４及びＳ２０５を実行する。
【００６４】
ステップＳ２０１：
ｎ−ｋ行ｋ列のゼロ行列Ｚを作成する。例えば、ｎ＝１６、ｋ＝１０、ｗ＝３の場合、図８に示すように、ゼロ行列Ｚは６行１０列となる。
【００６５】
ステップＳ２０２：
部分行列の平均行重みＥを式（１７）により求める。
（数１７）
Ｅ＝ｗ×ｋ／（ｎ−ｋ）                                                （１７）
例えば、ｎ＝１６、ｋ＝１０、ｗ＝３の場合、Ｅ＝５となる。
【００６６】
ステップＳ２０３：
Ｚの１行目の行重みがＷ｛Ｗ＝Ｅ＋１，Ｅ＋２，・・・，ｋ｝となるように、ｋＣＷの組合せにより１行目の１となる列を配置した行列をＺ’とする。１行目に１を配置した列の集合をＡとする。
例えば、Ｅ＝５である場合、１行目の行重みＷはＷ｛６，７，８，９，１０｝となる。
１行目の行重みがＷ＝６のとき、１行目に１を配置する列の組合せをｋＣｗにより決定する。例えば、Ａ＝｛１，２，３，４，５，６｝のとき、Ｚ３６に示すように、１行目の１列目から６列目までに「１」を配置する。また、１行目の行重みがＷ＝７のとき、１行目に１を配置する列の組合せをｋＣｗにより決定する。例えば、Ａ＝｛１，２，３，７，８，９，１０｝のとき、Ｚ３７に示すように、１行目の１列目から３列目までに「１」を配置し、１行目の７列目から１０列目までに「１」を配置する。
【００６７】
ステップＳ２０４：
Ｚ’の２行目からｎ−ｋ行目までの範囲に１を配置する。Ａに含まれる列は、ｎ−ｋ−１Ｃｗ−１の組合せにより１となる行を決定する。ｎ−ｋ−１Ｃｗ−１＞Ｗの場合は、ｎ−ｋ−１及びｗ−１の組み合わせからＷ種類を選び、各列を構成する。Ａに含まれない列は、ｎ−ｋ−１Ｃｗの組合せにより１となる行を決定する（図８）。ｎ−ｋ−１Ｃｗ＞ｋ−Ｗの場合は、ｎ−ｋ−１及びｗの組み合わせからｋ−Ｗ種類を選び各列を構成する。
例えば、Ｗ＝６のとき、Ｚ４６に示すように、Ａに含まれる１列目から６列目までは５Ｃ２の組合せにより決定される行に「１」を配置し、Ａに含まれない７列目から１０列目までは５Ｃ３の組合せにより決定される行に「１」を配置する。
例えば、Ｗ＝７のとき、Ｚ４７に示すように、Ａに含まれる１列目から３列目まで及び７列目から１０列目までは５Ｃ２の組合せにより決定される行に「１」を配置し、Ａに含まれない４列目から６列目までは５Ｃ３の組合せにより決定される行に「１」を配置する。
【００６８】
ステップＳ２０５：
構成した行列の中で任意のｆ｛ｆ＝１，２，・・・，ｗ｝列を修復可能な行列を部分行列ＰＴとする。例えば、Ｚ４６及びＺ４７の両方が部分行列ＰＴとなる。構成した部分行列の中で最も平均通信量の小さい行列を選択する。
【００６９】
ランダム構成法を用いることで、非正則の部分行列ＰＴを構成することができる。なお、本実施形態では「特定の１行」が１行目である例を示したが、「特定の１行」は２行目以降の任意の行であってもよい。
【００７０】
なお、本実施形態で説明したＦｌａｔ  ＸＯＲ符号の設計装置３０１は、コンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【００７１】
（発明のポイント）
［課題］
従来Ｆｌａｔ  ＸＯＲ符号を用いる場合、符号長ｎ、ソースシンボル数ｋ、列重みｗ等の複数のパラメータの組合せごとに各構成法に基づく符号を設計・探索・評価し符号を決定するため、幅広いパラメータの組合せに対する符号設計に膨大な時間を要した。
【００７２】
［解決手段］
本発明は、符号探索の前にパラメータセットに対する各符号の最大容量効率および平均通信量の推定値を求め、基準値を満たす符号の構成法とパラメータの範囲を絞り込むことによって、幅広いパラメータの組合せに対する符号設計を短時間で実現可能とした。
【００７３】
［効果］
本発明は、符号探索の前に各パラメータセットに対する各符号の推定最大容量効率および通信量を短時間で求め、求めるストレージの条件を満たす符号の構成法およびパラメータセットを絞り込むことができるため、より幅広い条件の分散ストレージに適した効率的なＦｌａｔ  ＸＯＲ符号の設計が可能となる。
【符号の説明】
【００７４】
１０：符号化装置
１１：データ分割部
１２：符号化部
１３：データ分配部
２０：ディスク
５１：設計条件入力部
５２：推定部
５２ａ：容量効率推定部
５２ｂ：通信量推定部
５３：条件限定部
５４：符号検索部
５５：符号選択部
５５ａ：選択部
５５ｂ：符号特性評価部
５５ｃ：符号データ保持部
５６：符号出力部
３０１：Ｆｌａｔ  ＸＯＲ符号の設計装置
ｎ：符号長
ｋ：ソースシンボル数
ｗ：列重み
ｐ：行重み
ｘ：行番号
【図１】
0006470200.tif 000007
【図２】
0006470200.tif 000008
【図３】
0006470200.tif 000009
【図４】
0006470200.tif 000010
【図５】
0006470200.tif 000011
【図６】
0006470200.tif 000012
【図７】
0006470200.tif 000013
【図８】
0006470200.tif 000014