畳み込み符号化されたデータを生成するシステム、プログラム及び方法
【課題】 畳み込み符号化されたデータを生成する装置及び方法を提供すること。
【解決手段】 本方法は、畳み込みエンコーダを供給する。本方法は、元データを受け取り、畳み込み符号化された元データを生成する。本方法は、改訂データを受け取る。本方法は、元データと改訂データとの排他的論理和演算を行うことによってXORデータ・ストリームを生成し、畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成し、畳み込み符号化されたXORデータ・ストリームと畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。
【解決手段】 本方法は、畳み込みエンコーダを供給する。本方法は、元データを受け取り、畳み込み符号化された元データを生成する。本方法は、改訂データを受け取る。本方法は、元データと改訂データとの排他的論理和演算を行うことによってXORデータ・ストリームを生成し、畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成し、畳み込み符号化されたXORデータ・ストリームと畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、畳み込み符号化されたデータを生成するシステム、プログラム、及び方法に関する。
【背景技術】
【0002】
データ・ストレージ・システムは、1つ又は複数のホスト・コンピュータ・システムによって提供された情報を格納するために用いられる。データ・ストレージ・システムは、ときとして、1つ又は複数のホスト・コンピュータ・システムによって提供された情報を、1つ又は複数の符号化プロトコルを用いて保存する。さらに、データ・ストレージ・システムは、ときとして、1つ又は複数のホスト・コンピュータ・システムから改訂されたデータを受け取る。データ・ストレージ・システムは、このような改訂された情報を1つ又は複数の符号化プロトコルを用いて保存する。
【発明の概要】
【0003】
畳み込み符号化されたデータを生成する装置及び方法が提供される。本方法は、畳み込みエンコーダを供給する。本方法は、さらに、元データを受け取り、畳み込み符号化された元データを生成する。本方法は、改訂データを受け取る。本方法は、元データと改訂データとの排他的論理和演算を行うことによってXORデータ・ストリームを生成し、畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成し、畳み込み符号化されたXORデータ・ストリームと畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。
【0004】
これより本発明の実施形態が、例示のみの目的で、添付の図面を参照して説明される。
【図面の簡単な説明】
【0005】
【図1】データ・ストレージ・システムの1つの実施形態を示すブロック図である。
【図2】畳み込みエンコーダ回路の1つの実施形態を示す。
【図3】1ビットのバイナリ・データを2ビットの符号化データに符号化することができる畳み込み符号化アルゴリズムを表す表である。
【図4】1ビットのバイナリ・データを2ビットの符号化データに符号化することができる畳み込み符号化アルゴリズムを表す状態図を含む。
【図5】2ビットの符号化データを1ビットのバイナリ・データに復号するために用いられるPRMLトレリスを示す。
【図6】本発明の1つの実施形態による方法を示すために用いられる元データを示す。
【図7】本発明の1つの実施形態による方法を示すために用いられる改訂データを示す。
【図8】図6の元データが図2の畳み込みエンコーダ回路を用いて畳み込み符号化された後の元データを示す。
【図9】図6の元データと図7の改訂データとの排他的論理和演算を行うことによって形成されるXORデータ・ストリームを示す。
【図10】図9のXORデータ・ストリームを図2の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化されたXORデータ・ストリームを示す。
【図11】図8の畳み込み符号化された元データと図10の畳み込み符号化されたXORデータ・ストリームとの排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図12】図9のXORデータ・ストリームから先行ゼロ部分を削除することによって形成される第1の切り捨て(truncated)XORデータ・ストリームを示す。
【図13】図12の第1の切り捨てXORデータ・ストリームを図2の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化された第1の切り捨てXORデータ・ストリームを示す。
【図14】図8の畳み込み符号化された元データに索引付けされた、図13の畳み込み符号化された第1の切り捨てXORデータ・ストリームを示す。
【図15】図8の畳み込み符号化された元データと図14の索引付けされた畳み込み符号化された第1の切り捨てXORデータ・ストリームとの排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図16】図12の第1の切り捨てXORデータ・ストリームから後続ゼロ部分を削除することによって形成される、第2の切り捨てXORデータ・ストリームを示す。
【図17】図16の第2の切り捨てXORデータ・ストリームを図2の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化された第2の切り捨てXORデータ・ストリームを示す。
【図18】図8の畳み込み符号化された元データに索引付けされた、図17の畳み込み符号化された第2の切り捨てXORデータ・ストリームを示す。
【図19】図8の畳み込み符号化された元データと図18の索引付けされた畳み込み符号化された第2の切り捨てXORデータ・ストリームとの間で排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図20】本方法の第1の実施形態のステップをまとめたフロー・チャートである。
【図21】本方法の第2の実施形態及び第3の実施形態を含む付加的なステップをまとめたフロー・チャートである。
【発明を実施するための形態】
【0006】
本発明は、以下の説明において添付の図面を参照して好ましい実施形態で説明され、図中、同様の符号は同一又は類似の要素を表す。本明細書の全体を通じて、「1つの実施形態(one embodiment)」、「一実施形態(a embodiment)」、又は同様の言葉への言及は、その実施形態との関連で説明された特定の特徴、構造、又は特性が、本発明の少なくとも1つの実施形態に含まれることを意味する。よって、本明細書の全体を通じて、「1つの実施形態において」、「一実施形態において」という語句、及び同様の言葉の出現は、全てが同じ実施形態のことを指すこともあるが、必ずしもそうであるとは限らない。
【0007】
説明される本発明の特徴、構造、及び特性は、1つ又は複数の実施形態において、いずれかの適切な手法で組み合わせることができる。以下の説明において、本発明の実施形態の完全な理解を与えるために、多数の具体的な詳細が列挙される。しかしながら、当業者であれば、本発明は1つ又は複数の具体的な詳細がなくても実施することができること、又は他の方法、構成要素、材料などを用いて実施することができることを認識する。他の例では、本発明の態様を不明瞭にすることを避けるため、周知の構造、材料、又は操作は図示されず、又は詳細に説明されない。
【0008】
図1は、データ・ストレージ・システム100を示す。図1の図示された実施形態において、システム100は、1つ又は複数のスイッチ125を用いてスイッチング・ファブリック120が形成された、スイッチド・アクセス・ネットワークを含む。特定の実施形態において、データ・ストレージ・システム100は、ファイバチャネル(「FC:Fibre Channel」)物理層上で動作する、小型コンピュータシステム・インターフェース(SCSI:Small Computer System Interface)プロトコルを用いて実装される。他の実施形態において、データ・ストレージ・システム100は、インフィニバンド(Infiniband)、FICON(Fibre Channel CONrctivity:ファイバチャネル接続の特殊形態)、TCP/IP、イーサネット、ギガビット・イーサネット、又はiSCSIなどのその他のプロトコルを用いて実装することができる。スイッチ125は、ホスト101、103、105、107、109及びコントローラ131の両者のアドレスを有するので、ホスト101、103、107及び/又は109はどれでも、いずれのコントローラ131にも互換的に接続することができるようになっている。
【0009】
ホスト・コンピュータ101、103、105、107及び109は各々、Windows、AIX、Unix、MVS、LINUXなどのオペレーティング・システムを含む、メインフレーム、パーソナル・コンピュータ、ワークステーション及びそれらの組み合のようなコンピュータ・システムを含む(WindowsはMicrosoft Corporationの登録商標であり、AIXはIBM Corporationの登録商標であり、MVSはIBM Corporationの商標である、UNIXは米国及びその他の国々においてThe Open Groupを通じて独占的にライセンスされる登録商標であり、LINUXはLinus Torvaldの登録商標である)。特定の実施形態において、ホスト・コンピュータ101、103、105、107及び109は、ストレージ管理プログラムをさらに含む。ホスト・コンピュータ101、103、105、107及び109内のストレージ管理プログラムは、データ・ストレージと検索システムとの間でやりとりされるデータ転送を管理する、IBM MVSオペレーティング・システムに実装されたIBM DFSMSのような当該分野において公知のストレージ管理型プログラムの機能を含むことができる。
【0010】
ホスト・コンピュータ101、103、105、107及び109は、それぞれ、I/Oインターフェース111、113、115、117及び119を用いてファブリック120に接続される。I/Oインターフェース111、113、115、117及び119は、任意のタイプのI/Oインターフェースとすることができ、例えば、FCアービトレーテッド・ループ、ファブリック120へのポイント・ツー・ポイント型FC接続、又はホスト・コンピュータ101、103、105、107及び109とファブリック120にとの間で情報を直接転送するために用いられる別の形態の1つ又は複数の信号ラインである。ファブリック120は、例えば、2つ又はそれ以上のコンピュータ・ネットワークを接続するために用いられる1つ又は複数のFCスイッチ125を含む。特定の実施形態において、FCスイッチ125は、従来型のルータ・スイッチである。1つの代替的な実施形態において、ホスト・コンピュータ101、103、105、107及び109は、スイッチを用いずにポイント・ツー・ポイント構成でストレージ・コントローラ131に接続される。
【0011】
スイッチ125は、I/Oインターフェース135越しに、ホスト・コンピュータ101、103、105、107及び109をコントローラ131に相互接続する。I/Oインターフェース135は、任意のタイプのI/Oインターフェースとすることができ、例えば、ファイバチャネル、インフィニバンド、ギガビット・イーサネット、イーサネット、TCP/IP、iSCSI、SCSI I/Oインターフェース、又はFCスイッチ125がコントローラ131との間でそれぞれ情報を転送し、その後で複数のデータ・ストレージ媒体160、170、180及び190に情報を転送するために用いられる1つ又は複数の信号ラインである。あるいは、1つの災害でデータ・ストレージ媒体160、170、180及び190のうちの1つしか損なわれないようにするために、データ・ストレージ媒体160、170、180及び190は互いに物理的に遠隔であるとともに、コントローラ131とも物理的に遠隔であることができる。「データ・ストレージ媒体」という用語によって、本出願人は、そのデータ・ストレージ媒体からデータを読み出し、かつ、そこにデータを書き込むために必要なハードウェア、ソフトウェア及び/又はファームウェアと組み合わされた、データ・ストレージ媒体のことを意味する。
【0012】
特定の実施形態において、1つ又は複数のデータ・ストレージ媒体160、170、180及び/又は190は、例えば、それらに限定されるものではないが、磁気ディスク、磁気テープなどのような、磁気データ・ストレージ媒体を含む。特定の実施形態において、1つ又は複数のデータ・ストレージ媒体160、170、180及び/又は190は、例えば、それらに限定されるものではないが、CD、DVD、HD−DVD、ブルーレイなどのような、光ストレージ媒体を含む。特定の実施形態において、1つ又は複数のデータ・ストレージ媒体160、170、180及び/又は190は、例えば、それらに限定されるものでないが、PROM、EPROM、EEPROM、フラッシュPROM、コンパクトフラッシュ、スマートメディアなどのような、電子データ・ストレージ媒体を含む。特定の実施形態において、1つ又は複数のデータ・ストレージ媒体160、170、180及び/又は190は、ホログラフィ・データ・ストレージ媒体を含む。
【0013】
ストレージ・アレイ130は、コントローラ131と、ストレージ媒体160、170、180及び190とを含む。コントローラ131とストレージ媒体160、170、180及び190とは、共通のフレーム又はボックスの中に一緒に配置されてもよい。あるいは、コントローラ131とストレージ媒体160、170、180及び190とは、災害からの復旧を理由として、ときとしてジオプレックスともよばれる形態で地理的に離間させてもよい。ストレージ媒体160、170、180及び/又は190は、ジオプレックス内のストレージへのアクセスを与えるために、連動して作動する分離した別個のコントローラを有することもできる。
【0014】
コントローラ131は多くの異なる形態を取ることができ、埋め込みシステム、分散制御システム、パーソナル・コンピュータ、ワークステーションなどを含むことができる。図1の図示された実施形態において、ストレージ・コントローラ131は、プロセッサ140、メタデータ・コントローラ148、ランダム・アクセス・メモリ(RAM)154、不揮発性メモリ150、特定回路142、符号化データ・インターフェース158及びホスト情報インターフェース132を含む。ホスト情報インターフェース132は情報134を保持し、この情報134は、ストレージ媒体160、170、180、190への書き込み動作中にエンコーダ146により符号化されるもの、又はストレージ媒体160、170、180、190からの読み出し動作中にデコーダ144によって読み取られ、復号されたもののいずれかである。特定の実施形態において、RAM154は、データ・キャッシュとして用いられる。プロセッサ140、RAM154、不揮発性メモリ150、特定回路142、メタデータ・コントローラ148、符号化データ・インターフェース158及びホスト情報インターフェース132は、バス145を介して互いに通信する。
【0015】
あるいは、RAM154及び/又は不揮発性メモリ150は、特定回路142、符号化データ・インターフェース158、メタデータ・コントローラ148及びホスト情報インターフェース132と共に、プロセッサ140内にあってもよい。プロセッサ140は、既製のマイクロプロセッサ、カスタム・プロセッサ、FPGA、ASIC、又は他の形態のディスクリート・ロジックを含むことができる。特定の実施形態において、RAM154は、ホスト101、103、105、107及び/又は109によって書き込まれたデータ、又はホスト101、103、105、107及び/又は109のために読み出されたデータのためのキャッシュとして用いられ、計算されたデータ、スタック・データ、実行可能命令などを保持する。特定の実施形態において、RAM154は、畳み込み符号化されたデータをデータ・ストレージ媒体160、170、180及び190上に格納する前に、エンコーダ146から受け取った畳み込み符号化されたデータ156を一時的に格納するために用いられる。
【0016】
不揮発性メモリ150は、電気的消去可能プログラマブル消去可能読出し専用メモリ(EEPROM:Electrically Erasable Programmable Read Only Memory)、フラッシュ・プログラマブル読出し専用メモリ(PROM:Programmable Read Only Memory)、バッテリ・バックアップRAM、ハード・ディスク・ドライブ又は他の同様のデバイスなどのような、任意のタイプの不揮発性メモリを含むことができる。不揮発性メモリ150は、典型的には、実行可能なファームウェア及び任意の不揮発性データ、例えばメタデータ152を保持するために用いられる。
【0017】
特定の実施形態において、符号化データ・インターフェース158は、プロセッサ140がデータ・ストレージ媒体160、170、180及び190と通信することを可能にする1つ又は複数の通信インターフェースを含む。ホスト情報インターフェース132は、プロセッサ140がファブリック120、スイッチ125、並びにホスト101、103、105、107及び/又は109と通信することを可能にする。符号化データ・インターフェース158及びホスト情報インターフェース132の例は、RS−232、USB(Universal Serial Bus(ユニバーサル・シリアルバス))、SCSI(SmallComputer Systems Interface(小型コンピュータシステム・インターフェース))、ファイバチャネル、ギガビット・イーサネットなどのような、シリアル・インターフェースを含む。さらに、符号化データ・インターフェース158及び/又はホスト情報インターフェース132は、無線周波数などの無線インターフェース、例えば、それに限定されるものではないがBluetooth、又は光通信デバイス、例えば、それに限定されるものではないが赤外周波数を用いるデバイスを含むことができる。
【0018】
特定の実施形態において、メタデータ・コントローラ148は、プロセッサ140内で、ソフトウェア、ファームウェア、専用ロジック又はその組み合わせによって実装される。さらに、メタデータ・コントローラ148の全て又は一部は、例えば、ホスト101、103、105、107及び/又は109のうちの1つに実装されたソフトウェアの形で、コントローラ131の外部に常駐してもよい。メタデータ・コントローラ148は、畳み込み符号化されたデータとしてストレージ・デバイスに格納するために受け取った情報に関連するメタデータを管理する。特定の実施形態において、メタデータ・コントローラ148は、畳み込み符号化されたデータとして格納するために受け取った情報に関連するメタデータを生成し、変更し、維持し、格納し、検索し、処理することを担当する。
【0019】
特定の実施形態において、ディストリビュータ136は、プロセッサ140内で、ソフトウェア、ファームウェア、専用ロジック又はその組み合わせによって実装される。さらに、ディストリビュータ136の全て又は一部は、ホスト101、103、105、107及び/又は109のうちの1つに実装されたソフトウェアの形で、コントローラ131の外部に常駐してもよい。ディストリビュータ136は、畳み込み符号化されたデータをRAMに、及び/又は直接ストレージ媒体160、170、180及び/又は190に分散させる。ディストリビュータ136が畳み込み符号化されたデータを媒体160、170、180及び190のような複数のデータ・ストレージ媒体に分散させる場合、分散はメタデータ152に従って行われるので、分散された畳み込み符号化されたデータを後でストレージ・デバイスから読み出して、元のデータ又は改訂データに復号することができる。
【0020】
特定回路142は、コントローラ131が、データ・ストレージ媒体160、170、180及び190、コントローラ131、並びにエンコーダ146の環境冷却のためのファン制御のような独自の機能を実行することを可能にする付加的なハードウェアを提供する。エンコーダ146は、例えば、それに限定されないが畳み込みエンコーダ回路200(図2)のような、畳み込みエンコーダとして実装されることができる。特定回路142は、パルス幅変調(PWM)制御、アナログ−デジタル変換(ADC)、デジタル−アナログ変換(DAC)、排他的論理和演算(「XOR」)などを提供する電子機器を含むことができる。さらに、特定回路142の全て又は一部は、ホスト101、103、105、107及び/又は109のうちの1つに実装されたソフトウェア実装などの形で、コントローラ131の外部に常駐してもよい。
【0021】
特定の実施形態において、エンコーダ146は、1データ・ビットを2データ・ビットの組に符号化する畳み込みエンコーダを含む。特定の実施形態において、エンコーダ146は、表300(図3)及び状態図400(図4)で表される畳み込み符号化アルゴリズムを含む。特定の実施形態において、デコーダ144は、PRMLトレリス500(図5)を含む。デコーダ144は、スタック図を構成することもできる。
【0022】
特定の実施形態において、既存ファイルに対して、「原子(atomic)」更新と呼ばれることもある小さい書き込み更新が実行される。特定の実施形態において、その既存ファイルは、以前に畳み込み符号化されたデータを含む。本方法は、データ・セット全体を再度畳み込み符号化することなく、以前に畳み込み符号化されたデータのビットのうちの比較的小さい部分を、既に畳み込み符号化されたデータ・セット内の他の畳み込み符号化されたデータのビットに変更する。本方法は、RAID3、4、又は5で用いられているような行パリティはどこにも使用しない。本方法は、RAID−6で用いられているような対角線パリティをどこにも使用しない。
【0023】
本発明に従って本方法を用いると、増分更新は、元データの変更された部分の排他的論理和(「XOR」)を(m)個の後続ゼロと組み合わせたものを含み、(m)は、畳み込みエンコーダ回路200(図2)の線形シフト・アレイの中のメモリ・ステップの数である。増分更新を畳み込み符号化し、次いで、元の畳み込み符号化されたデータとの間で排他的論理和演算を行い、更新を完了する。
【0024】
ここで図20を参照すると、ステップ1010において、本方法は、(m)個のレジスタ、即ち(m)レベルの遅延を含む畳み込みエンコーダを供給する。特定の実施形態において、ステップ1010の畳み込みエンコーダは、データ・ストレージ・システム100(図1)のようなデータ・ストレージ・システム内に配置される。特定の実施形態において、ステップ1010の畳み込みエンコーダは、ストレージ・アレイ130(図1)のようなストレージ・アレイ内に配置される。特定の実施形態において、ステップ1010の畳み込みエンコーダは、ストレージ・コントローラ131のようなストレージ・コントローラ内に配置される。特定の実施形態において、畳み込みエンコーダは、ストレージ・コントローラ131のようなストレージ・コントローラ内に配置されたエンコーダ146(図1)のような、エンコーダ内に配置される。
【0025】
特定の実施形態において、ステップ1010の畳み込みエンコーダは、エンコーダ回路200(図2)を含む。特定の実施形態において、ステップ1010の畳み込みエンコーダは、表300(図3)及び状態図400(図4)に示される符号化アルゴリズムを実行する。
【0026】
ここで図2を参照すると、畳み込みエンコーダ回路200は、符号化のために、入力情報ストリームU(J−3)205を一度に1ビットずつ受け取る。エンコーダ回路200は、レジスタ210、220及び230を含む3段シフト・レジスタを含む。レジスタ210、220及び230の初期内容は、符号化プロセスのためには、好ましくはゼロである。入力情報ストリームU(J−3)205と、レジスタ210、220及び230の出力とが加算器240によって選択的に加算されて出力V(J,1)245を生成し、加算器250によって選択的に加算されて出力V(J,2)255を生成する。特定の実施形態において、モジュロ−2加算器240及び250は、特定回路142内にXOR(排他的論理和)ゲートとして実装される。他の実施形態において、加算器240及び250は、ソフトウェア、ファームウェア、専用ロジックなどの使用により実装される。
【0027】
ここで図3及び図4を参照すると、特定の実施形態において、ステップ1010の畳み込みエンコーダは、表300及び状態図400で表される符号化アルゴリズムを用いる。装置及び方法についてのこの記述は、この装置及び方法が、畳み込みエンコーダ回路200、表300及び状態図400で表される畳み込み符号化アルゴリズムのみを使用すると限定するものと解釈されるべきではない。むしろ、他の実施形態において、本方法は異なる畳み込み符号化アルゴリズムを利用する。
【0028】
図3及び図4の符号化アルゴリズムは、S0410、S1411、S2412、S3413、S4414、S5415、S6416及びS7417の8つの状態を含む。状態間の各々の遷移の結果、ホスト101、103、105、107及び/又は109から受け取った1ビットの元データが符号化されて、図2、図3及び図4に示されるように、2ビットの符号化データになり、それらは、特定の実施形態において、次にストレージ媒体160、170、180及び190内に格納される。
【0029】
表300(図3)は、初期状態310、宛先状態320、元データ330、及び畳み込み符号化データ340の4つの列を含む。表300には、8つの状態S0、S1、S2、S3、S4、S5、S6、及びS7、並びに各初期状態からの2つの可能な遷移の総計に基づいて、全部で16個の行が存在する。表300は、状態図400によって生成されたものであり、ここでは、元データを符号化して符号化データを生成することを説明するために用いられる。再び図20を参照すると、ステップ1020において、本方法は、元データ600(図6)のような、元データを提供する。特定の実施形態において、ステップ1020の元データは、これらに限定されるものではないが、ホスト・コンピュータ101(図1)、103(図1)、105(図1)、107(図1)及び/又は109(図1)のような1つ又は複数のホスト・コンピュータによって提供される。ステップ1020は、元データを受け取ることをさらに含む。特定の実施形態において、ステップ1020の元データは、ストレージ・アレイ130(図1)のようなストレージ・アレイによって受け取られる。特定の実施形態において、ステップ1020の元データは、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって受け取られる。
【0030】
ステップ1030において、本方法は、ステップ1010の畳み込みエンコーダを用いて畳み込み符号化された元データを生成する。一例として、ここで図2、図6及び図8を参照すると、ステップ1030において、本方法は、畳み込みエンコーダ回路200と元データ600とを用いて、畳み込み符号化された元データ620を生成する。特定の実施形態において、ステップ1030は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1030は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1030は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。特定の実施形態において、ステップ1030は、エンコーダ146(図1)によって行われる。
【0031】
再び図20を参照すると、ステップ1040において、本方法は、ステップ1030の畳み込み符号化された元データを保存する。特定の実施形態において、ステップ1030の畳み込み符号化された元データは、データ・ストレージ媒体160(図1)、170(図1)、180(図1)及び/又は190(図1)のうちの1つ又は複数に保存される。特定の実施形態において、ステップ1040は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1040は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1040は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0032】
ステップ1050において、本方法は、改訂データ610(図7)のような、改訂されたデータを提供する。改訂データ610は、元データ600(図6)内のそれぞれのビットとは異なる、変更されたビット615を有する。特定の実施形態において、ステップ1050の改訂データは、これらに限定されるものではないが、ホスト・コンピュータ101(図1)、103(図1)、105(図1)、107(図1)及び/又は109(図1)のような1つ又は複数のホスト・コンピュータによって提供される。ステップ1050は、改訂データを受け取ることをさらに含む。特定の実施形態において、ステップ1050の改訂データは、ストレージ・アレイ130(図1)のようなストレージ・アレイによって受け取られる。特定の実施形態において、ステップ1050の改訂データは、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって受け取られる。
【0033】
ステップ1060において、本方法は、ステップ1020の元データとステップ1050の改訂データとの排他的論理和演算を行うことによって、XORデータ・ストリームを生成する。
【0034】
当業者であれば、「排他的論理和演算を行う(Exclusive OR'ing)」ことによって、元データが改訂データとの間で1ビットごとに排他的論理和されることを認識する。排他的論理和演算は、元データと改訂データの対応するビット位置間でのみ行われ、すなわち、ビット0は、ビット0との間でのみ排他的論理和され、ビット1は、ビット1との間でのみ排他的論理和され、以下同様である。表1は、4つの可能な排他的論理和の結果を挙げる。
【表1】
【0035】
ここで図6、図7及び図9を参照すると、ステップ1060において、元データ600と改訂データ610との排他的論理和演算を行うことにより、XORデータ・ストリーム700が生成される。XORデータ・ストリーム700は、元データ600と改訂データ610との間の対応する同一のビットの排他的論理和によって生成された複数の先行「ゼロ」を含む、部分702を含む。XORデータ・ストリーム700は、元データ600の対応するビットと改訂データ610の中の変更されたビット615との間の排他的論理和によって生成された複数の「1」を含む、部分704をさらに含む。XORデータ・ストリーム700は、元データ600と改訂データ610との間の対応する同一のビットの排他的論理和によって生成された複数の後続「ゼロ」を含む、部分706をさらに含む。
【0036】
再び図20を参照すると、ステップ1070において、本方法は、1つ又は複数の切り捨て(truncated)XORデータ・ストリームを生成して用いるかどうかを決定する。特定の実施形態において、ステップ1070は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1070は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1070は、ストレージ・コントローラ内に配置された、プロセッサ140(図1)のようなプロセッサによって行われる。
【0037】
方法が、1つ又は複数の切り捨てXORデータ・ストリームを生成せず用いないことを選択した場合には、方法は、ステップ1070からステップ1080に移り、ここで、方法は、XORデータ・ストリーム700のようなステップ1060のXORデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ1080は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1080は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1080は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0038】
一例として、ここで図2、図9及び図10を参照すると、XORデータ・ストリーム700と畳み込みエンコーダ回路200とを用いて、畳み込み符号化されたXORデータ・ストリーム710が生成される。畳み込み符号化されたXORデータ・ストリーム710は、エンコーダ回路200を用いて部分702を畳み込み符号化することによって生成された部分712を含む。複数の先行「0」を畳み込み符号化する場合、エンコーダ回路200は各「0」を「00」に符号化し、これはS0からS0への遷移の繰り返しを表す。
【0039】
畳み込み符号化されたXORデータ・ストリーム710は、部分704を(m)個の後続ゼロと組み合わせて畳み込み符号化することによって生成された部分714をさらに含み、ここで、畳み込みエンコーダ回路200の場合、(m)は3の値を有する。エンコーダ回路200は3つのレジスタ、即ち、レジスタ210、220及び230を含む。その結果、畳み込みエンコーダ回路200は、エンコーダが状態S0に戻る前に、最初の3つの後続ゼロを符号化する。その後、後続「0」の各々は、S0からS0への遷移の繰り返しを表す「00」に符号化される。畳み込み符号化されたXORデータ・ストリーム710は、部分706の残りの後続ゼロを畳み込みエンコーダ回路200を用いて畳み込み符号化することによって生成された、部分716をさらに含む。
【0040】
再び図20を参照すると、ステップ1090において、本方法は、ステップ1080の畳み込み符号化されたXORデータ・ストリームとステップ1030の畳み込み符号化された元データとの排他的論理和演算を行う。特定の実施形態において、ステップ1090は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1090は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1090は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0041】
一例として、ここで図11を参照すると、ステップ1090において、本方法は、畳み込み符号化された元データ620と畳み込み符号化されたXORデータ・ストリーム710との排他的論理和演算を行い、畳み込み符号化された改訂データ720を生成する。この実施形態において、本方法は、ステップ1090において、畳み込み符号化された元データ620の部分622と畳み込み符号化されたXORデータ・ストリーム710の先行ゼロ部分712との排他的論理和演算を行い、改訂データ720の畳み込み符号化された部分722を生成する。この実施形態において、本方法は、さらに、畳み込み符号化された元データ620の部分624と畳み込み符号化されたXORデータ・ストリーム710の変更されたビット/(m)個の後続ゼロ部分714との排他的論理和演算を行い、改訂データ720の更新された部分724を形成する。この実施形態において、方法は、さらに、畳み込み符号化された元データ620の部分626と畳み込み符号化されたXORデータ・ストリーム710の残りの後続ゼロ部分716との排他的論理和演算を行い、改訂データ720の畳み込み符号化された部分726を形成する。
【0042】
他の実施形態において、本方法は、第1の切り捨てXORデータ・ストリームを利用し、この場合、方法は、XORデータ・ストリーム710から先行ゼロを削除し、次いで、その第1の切り捨てXORデータ・ストリームを畳み込み符号化し、次いで、畳み込み符号化された第1の切り捨てXORデータ・ストリームと元データと排他的論理和演算を行い、改訂データを生成する。さらに他の実施形態において、本方法は、第2の切り捨てXORデータ・ストリームを利用し、この場合、本方法は、第1の切り捨てXORデータ・ストリームから(m)個の後続ゼロを除く全ての後続ゼロをさらに削除し、次いで、その第2の切り捨てXORデータ・ストリームを畳み込み符号化し、次いで、畳み込み符号化された第2の切り捨てXORデータ・ストリームと元データとの排他的論理和演算を行い、改訂データを生成する。
【0043】
再び図20を参照すると、ステップ1070において、本方法が1つ又は複数の切り捨てXORデータ・ストリームを生成して用いることを選択した場合には、本方法は、ステップ1070からステップ1110(図21)に移る。ステップ1110において、本方法は、第1の切り捨てXORデータ・ストリームを生成する。特定の実施形態において、ステップ1110は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1110は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1110は、ストレージ・コントローラ内に配置された、プロセッサ140(図1)のようなプロセッサによって行われる。
【0044】
一例として、ここで図9及び図12を参照すると、XORデータ・ストリーム700の部分702は、(N)個の先行ゼロを含む。ステップ1110において、本方法は、XORデータ・ストリーム700から、部分702を構成する(N)個の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリーム800を生成する。第1の切り捨てXORデータ・ストリーム800は、変更されたビット部分804を後続ゼロ部分806と組み合わせて含む。
【0045】
再び図21を参照すると、ステップ1120において、本方法は、第2の切り捨てXORデータ・ストリームを生成して用いるかどうかを決定する。特定の実施形態において、ステップ1120は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1120は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1120は、ストレージ・コントローラ内に配置された、プロセッサ140(図1)のようなプロセッサによって行われる。
【0046】
ステップ1120において、本方法が、第2の切り捨てXORデータ・ストリームを生成せず用いないことを選択した場合には、本方法は、ステップ1120からステップ1130に移り、ここで、方法は第1の切り捨てXORデータ・ストリーム800(図12)のようなステップ1110の第1の切り捨てXORデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ1130は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1130は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1130は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0047】
一例として、ここで図2、図12及び図13を参照すると、第1の切り捨てXORデータ・ストリーム800と畳み込みエンコーダ回路200とを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリーム810が生成される。畳み込み符号化された第1の切り捨てXORデータ・ストリーム810は、部分804を(m)個の後続ゼロと組み合わせて畳み込み符号化することによって生成された部分814をさらに含み、ここで、畳み込みエンコーダ回路200の場合、(m)は3の値を有する。エンコーダ回路200は3つのレジスタ、即ち、レジスタ210、220及び230を含む。その結果、畳み込みエンコーダ回路200は、エンコーダが状態S0に戻る前に、最初の3つの後続ゼロを符号化する。その後、後続「0」の各々は、S0からS0への遷移の繰り返しを表す「00」に符号化される。畳み込み符号化された第1の切り捨てXORデータ・ストリーム810は、部分806の残りの後続ゼロを畳み込みエンコーダ回路200を用いて畳み込み符号化することによって生成された、部分816をさらに含む。
【0048】
再び図21を参照すると、ステップ1140において、本方法は、ステップ1130の畳み込み符号化された第1の切り捨てXORデータ・ストリームを、ステップ1030(図20)の畳み込み符号化された元データに索引付けする。ステップ1110において、本方法は、ステップ1060(図20)のXORデータ・ストリームから、(N)個の先行ゼロを削除し、第1の切り捨てXORデータ・ストリームを生成した。ステップ1140において、本方法は、ステップ1130の畳み込み符号化された第1の切り捨てXORデータ・ストリームの第1ビットを、畳み込み符号化された元データの第[(2)(N)+1]番目のビットに位置合わせする。
【0049】
特定の実施形態において、ステップ1140は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1140は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1140は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0050】
一例として、ここで図9、図12及び図14を参照すると、XORデータ・ストリーム700は(N)個の先行ゼロを含み、ここで(N)は13である。これらの13個の先行ゼロは、第1の切り捨てXORデータ・ストリーム800を生成するために削除された。ステップ1140において、本方法は、畳み込み符号化された第1の切り捨てXORデータ・ストリーム810の第1ビットを、畳み込み符号化された元データ620の第27番目のビット[(2)(13)+1]に位置合わせする。
【0051】
再び図21を参照すると、本方法は、ステップ1150において、索引付けされたステップ1130の畳み込み符号化されたXORデータ・ストリームとステップ1030の畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。特定の実施形態において、ステップ1150は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1150は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1150は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0052】
一例として、図15を参照すると、畳み込み符号化された第1の切り捨てXORデータ・ストリーム810は、畳み込み符号化された元データ620の部分622に対応する部分を含まない。従って、ステップ1150において、本方法は、畳み込み符号化された改訂データ720の第1の部分722として、部分622をコピーする。ステップ1150において、さらに、本方法は、畳み込み符号化された元データ620の部分624と畳み込み符号化された第1の切り捨てXORデータ・ストリーム810の部分814との排他的論理和演算を行って、畳み込み符号化された改訂データ720の畳み込み符号化された部分724を生成し、畳み込み符号化された元データ620の部分626と畳み込み符号化された第1の切り捨てXORデータ・ストリーム810の部分816との排他的論理和演算を行って、畳み込み符号化された改訂データ720の第3の部分726を生成し、畳み込み符号化された改訂データ720の生成を完了する。
【0053】
再び図21を参照すると、ステップ1120において、本方法が、第2の切り捨てXORデータ・ストリームを生成して用いることを選択した場合には、本方法は、ステップ1120からステップ1160に移り、ここで、本方法は第2の切り捨てXORデータ・ストリームを生成する。特定の実施形態において、ステップ1160は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1160は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1160は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0054】
一例として、ここで図12及び図16を参照すると、第1の切り捨てXORデータ・ストリーム800は、変更ビット部分804と、(P)個の後続ゼロを含む部分806とを含む。ステップ1160において、本方法は、[(P)−(m)]個の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリーム900を生成し、ここで、(m)はステップ1010(図20)の畳み込みエンコーダにおいて用いられるレジスタの数に等しい。図16の図示された実施形態において、第2の切り捨てXORデータ・ストリーム900は、変更されたビット部分902を3個の後続ゼロ部分904と組み合わせて含む。
【0055】
再び図21を参照すると、本方法は、ステップ1170において、第2の切り捨てXORデータ・ストリーム900(図16)のような、ステップ1160の第2の切り捨てXORデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ1170は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1170は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1170は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0056】
一例として、ここで図2、図16及び図17を参照すると、第2の切り捨てXORデータ・ストリーム900と畳み込みエンコーダ回路200とを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリーム910が生成される。畳み込み符号化された第2の切り捨てXORデータ・ストリーム910は、部分902と904とを畳み込み符号化することによって生成される。
【0057】
再び図21を参照すると、ステップ1180において、本方法は、ステップ1170の畳み込み符号化された第2の切り捨てXORデータ・ストリームを、ステップ1030(図20)の畳み込み符号化された元データに索引付けする。ステップ1110において、本方法は、ステップ1060(図20)のXORデータ・ストリームから、(N)個の先行ゼロを削除し、第1の切り捨てXORデータ・ストリームを生成した。ステップ1180において、本方法は、ステップ1170の畳み込み符号化された第2の切り捨てXORデータ・ストリームの第1ビットを、畳み込み符号化された元データの第[(2)(N)+1]番目のビットに位置合わせする。
【0058】
特定の実施形態において、ステップ1180は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1180は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1180は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0059】
一例として、ここで図9、図12及び図18を参照すると、XORデータ・ストリーム700は(N)個の先行ゼロを含み、ここで(N)は13である。これらの13個の先行ゼロは、第1の切り捨てXORデータ・ストリーム800を生成するために削除された。ステップ1180において、本方法は、畳み込み符号化された第2の切り捨てXORデータ・ストリーム910の第1ビットを、畳み込み符号化された元データ620の第27番目のビット[(2)(13)+1]に位置合わせする。
【0060】
再び図21を参照すると、本方法は、ステップ1190において、索引付けされたステップ1180の畳み込み符号化された第2の切り捨てXORデータ・ストリームとステップ1030の畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。特定の実施形態において、ステップ1190は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1190は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1190は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0061】
一例として、図19を参照すると、畳み込み符号化された第2の切り捨てXORデータ・ストリーム910は、畳み込み符号化された元データ620の部分622に対応する部分を含まず、畳み込み符号化された元データ620の部分626に対応する部分も含まない。ステップ1190において、本方法は、畳み込み符号化された改訂データ720の部分722として、部分622をコピーする。ステップ1190において、さらに、本方法は、畳み込み符号化された改訂データ720の部分726として、部分626をコピーする。ステップ1190において、さらに、本方法は、畳み込み符号化された元データ620の部分624と畳み込み符号化された第2の切り捨てXORデータ・ストリーム910の部分との排他的論理和演算を行って、更新された部分724を作成し、それにより、畳み込み符号化された改訂データ720の生成を完了する。
【0062】
特定の実施形態において、図20及び図21において列挙された個々のステップは、組み合わせることもでき、省くこともでき、又は順序を変更することもできる。例えば、本方法の第1の実施形態は、図20のステップ1010、1020、1030、1040、1050、1060、1080及び1090を含む8つのステップを含む。本方法の第2の実施形態は、図20のステップ1010、1020、1030、1040、1050、1060と、図21のステップ1110、1130、1140及び1150との組み合わせを含む、10個のステップを含む。本方法の第3の実施形態は、図20のステップ1010、1020、1030、1040、1050、1060と、図21のステップ1110、1160、1170、1180及び1190との組み合わせを含む、11個のステップを含む。
【0063】
8ステップの第1の実施形態は、改訂データ中で改訂されたビットと元のビットとの間の比が高い場合、即ち、元のビットのほとんど全てが改訂されている場合に最も有用である。一方、改訂されたビットと元のビットとの間の比が非常に低い場合、即ち「原子」更新の場合には、11ステップの第3の実施形態の使用が好ましい。
【0064】
第3の実施形態は11個のステップを含むが、その第3の実施形態は、かなり切り捨てられたXORデータ・ストリーム、即ち、第2の切り捨てXORデータ・ストリームが畳み込み符号化されるステップ1170を利用するので、第3の実施形態は「原子」更新のためにそれほど多くの計算機能力及び時間を必要としない。さらに、11ステップの第3の実施形態は、その畳み込み符号化された第2のXORデータのみが畳み込み符号化された元データと排他的論理和されるステップ1190を利用するので、第3の実施形態はそれほど多くの計算機能力及び時間を必要としない。
【0065】
前述の装置及び方法の実施形態のいずれも、データ・ストレージ・サービス・プロバイダによって、1つ又は複数のデータ・ストレージ・サービス顧客にデータ・ストレージ・サービスを提供するために用いることができる。特定の実施形態において、1つ又は複数のデータ・ストレージ・サービス顧客は、ホスト・コンピュータ101(図1)、103(図1)、105(図1)、107(図1)及び/又は109(図1)のうちの1つ又は複数を所有し、及び/又は操作する。これらの1つ又は複数のデータ・ストレージ・サービス顧客は、1つ又は複数のホスト・コンピュータからストレージ・アレイ130(図1)のようなストレージ・アレイに顧客データを提供し、そのストレージ・アレイは、データ・ストレージ・サービス・プロバイダによって所有され、及び/又は操作される。
【0066】
特定の実施形態において、本発明は、メモリ150(図1)に常駐する命令を含み、これらの命令は、プロセッサ140(図1)のようなプロセッサによって、図20で列挙されたステップ1020、1030、1040、1050、1060、1070、1080及び/又は1090のうちの1つ又は複数のステップ、及び/又は、図21で列挙されたステップ1110、1120、1130、1140、1150、1160、1170、1180及び/又は1190のうちの1つ又は複数のステップを行うために実行される。
【0067】
他の実施形態において、本発明は、いずれかの他のコンピュータ・プログラムに常駐する命令を含み、これらの命令は、システム100の外部又は内部のコンピュータによって、図20で列挙されたステップ1020、1030、1040、1050、1060、1070、1080及び/又は1090のうちの1つ又は複数のステップ、及び/又は、図21で列挙されたステップ1110、1120、1130、1140、1150、1160、1170、1180及び/又は1190のうちの1つ又は複数のステップを行うために実行される。どちらの場合においても、命令は、例えば、磁気情報ストレージ媒体、光情報ストレージ媒体、電子情報ストレージ媒体を含む、情報ストレージ媒体内で符号化されることができる。「電子ストレージ媒体」という用語によって、本出願人は、例えば、PROM、EPROM、EEPROM、フラッシュPROM、コンパクトフラッシュ、スマートメディアなどのようなデバイスのことを意味する。
【0068】
本発明の好ましい実施形態を詳細に説明してきたが、当業者であれば、添付の特許請求の範囲で述べられる本発明の範囲を逸脱することなく、これらの実施形態に対する修正及び改造を想起することができることは明らかである。
【符号の説明】
【0069】
100:データ・ストレージ・システム
111、113、115、117、119、135:I/Oインターフェース
130:ストレージ・アレイ
131:コントローラ
145:バス
200:畳み込みエンコーダ回路
205:入力情報ストリーム
210、220、230:シフト・レジスタ
240、250:加算器
245、255:出力
300、400:畳み込み符号化アルゴリズム
500:PRMLトレリス
600:元データ
610:改訂データ
620:畳み込み符号化された元データ
700:XORデータ・ストリーム
710:畳み込み符号化されたXORデータ・ストリーム
720:畳み込み符号化された改訂データ
800:第1の切り捨てXORデータ・ストリーム
810:畳み込み符号化された第1の切り捨てXORデータ・ストリーム
900:第2の切り捨てXORデータ・ストリーム
910:畳み込み符号化された第2の切り捨てXORデータ・ストリーム
【技術分野】
【0001】
本発明は、畳み込み符号化されたデータを生成するシステム、プログラム、及び方法に関する。
【背景技術】
【0002】
データ・ストレージ・システムは、1つ又は複数のホスト・コンピュータ・システムによって提供された情報を格納するために用いられる。データ・ストレージ・システムは、ときとして、1つ又は複数のホスト・コンピュータ・システムによって提供された情報を、1つ又は複数の符号化プロトコルを用いて保存する。さらに、データ・ストレージ・システムは、ときとして、1つ又は複数のホスト・コンピュータ・システムから改訂されたデータを受け取る。データ・ストレージ・システムは、このような改訂された情報を1つ又は複数の符号化プロトコルを用いて保存する。
【発明の概要】
【0003】
畳み込み符号化されたデータを生成する装置及び方法が提供される。本方法は、畳み込みエンコーダを供給する。本方法は、さらに、元データを受け取り、畳み込み符号化された元データを生成する。本方法は、改訂データを受け取る。本方法は、元データと改訂データとの排他的論理和演算を行うことによってXORデータ・ストリームを生成し、畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成し、畳み込み符号化されたXORデータ・ストリームと畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。
【0004】
これより本発明の実施形態が、例示のみの目的で、添付の図面を参照して説明される。
【図面の簡単な説明】
【0005】
【図1】データ・ストレージ・システムの1つの実施形態を示すブロック図である。
【図2】畳み込みエンコーダ回路の1つの実施形態を示す。
【図3】1ビットのバイナリ・データを2ビットの符号化データに符号化することができる畳み込み符号化アルゴリズムを表す表である。
【図4】1ビットのバイナリ・データを2ビットの符号化データに符号化することができる畳み込み符号化アルゴリズムを表す状態図を含む。
【図5】2ビットの符号化データを1ビットのバイナリ・データに復号するために用いられるPRMLトレリスを示す。
【図6】本発明の1つの実施形態による方法を示すために用いられる元データを示す。
【図7】本発明の1つの実施形態による方法を示すために用いられる改訂データを示す。
【図8】図6の元データが図2の畳み込みエンコーダ回路を用いて畳み込み符号化された後の元データを示す。
【図9】図6の元データと図7の改訂データとの排他的論理和演算を行うことによって形成されるXORデータ・ストリームを示す。
【図10】図9のXORデータ・ストリームを図2の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化されたXORデータ・ストリームを示す。
【図11】図8の畳み込み符号化された元データと図10の畳み込み符号化されたXORデータ・ストリームとの排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図12】図9のXORデータ・ストリームから先行ゼロ部分を削除することによって形成される第1の切り捨て(truncated)XORデータ・ストリームを示す。
【図13】図12の第1の切り捨てXORデータ・ストリームを図2の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化された第1の切り捨てXORデータ・ストリームを示す。
【図14】図8の畳み込み符号化された元データに索引付けされた、図13の畳み込み符号化された第1の切り捨てXORデータ・ストリームを示す。
【図15】図8の畳み込み符号化された元データと図14の索引付けされた畳み込み符号化された第1の切り捨てXORデータ・ストリームとの排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図16】図12の第1の切り捨てXORデータ・ストリームから後続ゼロ部分を削除することによって形成される、第2の切り捨てXORデータ・ストリームを示す。
【図17】図16の第2の切り捨てXORデータ・ストリームを図2の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化された第2の切り捨てXORデータ・ストリームを示す。
【図18】図8の畳み込み符号化された元データに索引付けされた、図17の畳み込み符号化された第2の切り捨てXORデータ・ストリームを示す。
【図19】図8の畳み込み符号化された元データと図18の索引付けされた畳み込み符号化された第2の切り捨てXORデータ・ストリームとの間で排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図20】本方法の第1の実施形態のステップをまとめたフロー・チャートである。
【図21】本方法の第2の実施形態及び第3の実施形態を含む付加的なステップをまとめたフロー・チャートである。
【発明を実施するための形態】
【0006】
本発明は、以下の説明において添付の図面を参照して好ましい実施形態で説明され、図中、同様の符号は同一又は類似の要素を表す。本明細書の全体を通じて、「1つの実施形態(one embodiment)」、「一実施形態(a embodiment)」、又は同様の言葉への言及は、その実施形態との関連で説明された特定の特徴、構造、又は特性が、本発明の少なくとも1つの実施形態に含まれることを意味する。よって、本明細書の全体を通じて、「1つの実施形態において」、「一実施形態において」という語句、及び同様の言葉の出現は、全てが同じ実施形態のことを指すこともあるが、必ずしもそうであるとは限らない。
【0007】
説明される本発明の特徴、構造、及び特性は、1つ又は複数の実施形態において、いずれかの適切な手法で組み合わせることができる。以下の説明において、本発明の実施形態の完全な理解を与えるために、多数の具体的な詳細が列挙される。しかしながら、当業者であれば、本発明は1つ又は複数の具体的な詳細がなくても実施することができること、又は他の方法、構成要素、材料などを用いて実施することができることを認識する。他の例では、本発明の態様を不明瞭にすることを避けるため、周知の構造、材料、又は操作は図示されず、又は詳細に説明されない。
【0008】
図1は、データ・ストレージ・システム100を示す。図1の図示された実施形態において、システム100は、1つ又は複数のスイッチ125を用いてスイッチング・ファブリック120が形成された、スイッチド・アクセス・ネットワークを含む。特定の実施形態において、データ・ストレージ・システム100は、ファイバチャネル(「FC:Fibre Channel」)物理層上で動作する、小型コンピュータシステム・インターフェース(SCSI:Small Computer System Interface)プロトコルを用いて実装される。他の実施形態において、データ・ストレージ・システム100は、インフィニバンド(Infiniband)、FICON(Fibre Channel CONrctivity:ファイバチャネル接続の特殊形態)、TCP/IP、イーサネット、ギガビット・イーサネット、又はiSCSIなどのその他のプロトコルを用いて実装することができる。スイッチ125は、ホスト101、103、105、107、109及びコントローラ131の両者のアドレスを有するので、ホスト101、103、107及び/又は109はどれでも、いずれのコントローラ131にも互換的に接続することができるようになっている。
【0009】
ホスト・コンピュータ101、103、105、107及び109は各々、Windows、AIX、Unix、MVS、LINUXなどのオペレーティング・システムを含む、メインフレーム、パーソナル・コンピュータ、ワークステーション及びそれらの組み合のようなコンピュータ・システムを含む(WindowsはMicrosoft Corporationの登録商標であり、AIXはIBM Corporationの登録商標であり、MVSはIBM Corporationの商標である、UNIXは米国及びその他の国々においてThe Open Groupを通じて独占的にライセンスされる登録商標であり、LINUXはLinus Torvaldの登録商標である)。特定の実施形態において、ホスト・コンピュータ101、103、105、107及び109は、ストレージ管理プログラムをさらに含む。ホスト・コンピュータ101、103、105、107及び109内のストレージ管理プログラムは、データ・ストレージと検索システムとの間でやりとりされるデータ転送を管理する、IBM MVSオペレーティング・システムに実装されたIBM DFSMSのような当該分野において公知のストレージ管理型プログラムの機能を含むことができる。
【0010】
ホスト・コンピュータ101、103、105、107及び109は、それぞれ、I/Oインターフェース111、113、115、117及び119を用いてファブリック120に接続される。I/Oインターフェース111、113、115、117及び119は、任意のタイプのI/Oインターフェースとすることができ、例えば、FCアービトレーテッド・ループ、ファブリック120へのポイント・ツー・ポイント型FC接続、又はホスト・コンピュータ101、103、105、107及び109とファブリック120にとの間で情報を直接転送するために用いられる別の形態の1つ又は複数の信号ラインである。ファブリック120は、例えば、2つ又はそれ以上のコンピュータ・ネットワークを接続するために用いられる1つ又は複数のFCスイッチ125を含む。特定の実施形態において、FCスイッチ125は、従来型のルータ・スイッチである。1つの代替的な実施形態において、ホスト・コンピュータ101、103、105、107及び109は、スイッチを用いずにポイント・ツー・ポイント構成でストレージ・コントローラ131に接続される。
【0011】
スイッチ125は、I/Oインターフェース135越しに、ホスト・コンピュータ101、103、105、107及び109をコントローラ131に相互接続する。I/Oインターフェース135は、任意のタイプのI/Oインターフェースとすることができ、例えば、ファイバチャネル、インフィニバンド、ギガビット・イーサネット、イーサネット、TCP/IP、iSCSI、SCSI I/Oインターフェース、又はFCスイッチ125がコントローラ131との間でそれぞれ情報を転送し、その後で複数のデータ・ストレージ媒体160、170、180及び190に情報を転送するために用いられる1つ又は複数の信号ラインである。あるいは、1つの災害でデータ・ストレージ媒体160、170、180及び190のうちの1つしか損なわれないようにするために、データ・ストレージ媒体160、170、180及び190は互いに物理的に遠隔であるとともに、コントローラ131とも物理的に遠隔であることができる。「データ・ストレージ媒体」という用語によって、本出願人は、そのデータ・ストレージ媒体からデータを読み出し、かつ、そこにデータを書き込むために必要なハードウェア、ソフトウェア及び/又はファームウェアと組み合わされた、データ・ストレージ媒体のことを意味する。
【0012】
特定の実施形態において、1つ又は複数のデータ・ストレージ媒体160、170、180及び/又は190は、例えば、それらに限定されるものではないが、磁気ディスク、磁気テープなどのような、磁気データ・ストレージ媒体を含む。特定の実施形態において、1つ又は複数のデータ・ストレージ媒体160、170、180及び/又は190は、例えば、それらに限定されるものではないが、CD、DVD、HD−DVD、ブルーレイなどのような、光ストレージ媒体を含む。特定の実施形態において、1つ又は複数のデータ・ストレージ媒体160、170、180及び/又は190は、例えば、それらに限定されるものでないが、PROM、EPROM、EEPROM、フラッシュPROM、コンパクトフラッシュ、スマートメディアなどのような、電子データ・ストレージ媒体を含む。特定の実施形態において、1つ又は複数のデータ・ストレージ媒体160、170、180及び/又は190は、ホログラフィ・データ・ストレージ媒体を含む。
【0013】
ストレージ・アレイ130は、コントローラ131と、ストレージ媒体160、170、180及び190とを含む。コントローラ131とストレージ媒体160、170、180及び190とは、共通のフレーム又はボックスの中に一緒に配置されてもよい。あるいは、コントローラ131とストレージ媒体160、170、180及び190とは、災害からの復旧を理由として、ときとしてジオプレックスともよばれる形態で地理的に離間させてもよい。ストレージ媒体160、170、180及び/又は190は、ジオプレックス内のストレージへのアクセスを与えるために、連動して作動する分離した別個のコントローラを有することもできる。
【0014】
コントローラ131は多くの異なる形態を取ることができ、埋め込みシステム、分散制御システム、パーソナル・コンピュータ、ワークステーションなどを含むことができる。図1の図示された実施形態において、ストレージ・コントローラ131は、プロセッサ140、メタデータ・コントローラ148、ランダム・アクセス・メモリ(RAM)154、不揮発性メモリ150、特定回路142、符号化データ・インターフェース158及びホスト情報インターフェース132を含む。ホスト情報インターフェース132は情報134を保持し、この情報134は、ストレージ媒体160、170、180、190への書き込み動作中にエンコーダ146により符号化されるもの、又はストレージ媒体160、170、180、190からの読み出し動作中にデコーダ144によって読み取られ、復号されたもののいずれかである。特定の実施形態において、RAM154は、データ・キャッシュとして用いられる。プロセッサ140、RAM154、不揮発性メモリ150、特定回路142、メタデータ・コントローラ148、符号化データ・インターフェース158及びホスト情報インターフェース132は、バス145を介して互いに通信する。
【0015】
あるいは、RAM154及び/又は不揮発性メモリ150は、特定回路142、符号化データ・インターフェース158、メタデータ・コントローラ148及びホスト情報インターフェース132と共に、プロセッサ140内にあってもよい。プロセッサ140は、既製のマイクロプロセッサ、カスタム・プロセッサ、FPGA、ASIC、又は他の形態のディスクリート・ロジックを含むことができる。特定の実施形態において、RAM154は、ホスト101、103、105、107及び/又は109によって書き込まれたデータ、又はホスト101、103、105、107及び/又は109のために読み出されたデータのためのキャッシュとして用いられ、計算されたデータ、スタック・データ、実行可能命令などを保持する。特定の実施形態において、RAM154は、畳み込み符号化されたデータをデータ・ストレージ媒体160、170、180及び190上に格納する前に、エンコーダ146から受け取った畳み込み符号化されたデータ156を一時的に格納するために用いられる。
【0016】
不揮発性メモリ150は、電気的消去可能プログラマブル消去可能読出し専用メモリ(EEPROM:Electrically Erasable Programmable Read Only Memory)、フラッシュ・プログラマブル読出し専用メモリ(PROM:Programmable Read Only Memory)、バッテリ・バックアップRAM、ハード・ディスク・ドライブ又は他の同様のデバイスなどのような、任意のタイプの不揮発性メモリを含むことができる。不揮発性メモリ150は、典型的には、実行可能なファームウェア及び任意の不揮発性データ、例えばメタデータ152を保持するために用いられる。
【0017】
特定の実施形態において、符号化データ・インターフェース158は、プロセッサ140がデータ・ストレージ媒体160、170、180及び190と通信することを可能にする1つ又は複数の通信インターフェースを含む。ホスト情報インターフェース132は、プロセッサ140がファブリック120、スイッチ125、並びにホスト101、103、105、107及び/又は109と通信することを可能にする。符号化データ・インターフェース158及びホスト情報インターフェース132の例は、RS−232、USB(Universal Serial Bus(ユニバーサル・シリアルバス))、SCSI(SmallComputer Systems Interface(小型コンピュータシステム・インターフェース))、ファイバチャネル、ギガビット・イーサネットなどのような、シリアル・インターフェースを含む。さらに、符号化データ・インターフェース158及び/又はホスト情報インターフェース132は、無線周波数などの無線インターフェース、例えば、それに限定されるものではないがBluetooth、又は光通信デバイス、例えば、それに限定されるものではないが赤外周波数を用いるデバイスを含むことができる。
【0018】
特定の実施形態において、メタデータ・コントローラ148は、プロセッサ140内で、ソフトウェア、ファームウェア、専用ロジック又はその組み合わせによって実装される。さらに、メタデータ・コントローラ148の全て又は一部は、例えば、ホスト101、103、105、107及び/又は109のうちの1つに実装されたソフトウェアの形で、コントローラ131の外部に常駐してもよい。メタデータ・コントローラ148は、畳み込み符号化されたデータとしてストレージ・デバイスに格納するために受け取った情報に関連するメタデータを管理する。特定の実施形態において、メタデータ・コントローラ148は、畳み込み符号化されたデータとして格納するために受け取った情報に関連するメタデータを生成し、変更し、維持し、格納し、検索し、処理することを担当する。
【0019】
特定の実施形態において、ディストリビュータ136は、プロセッサ140内で、ソフトウェア、ファームウェア、専用ロジック又はその組み合わせによって実装される。さらに、ディストリビュータ136の全て又は一部は、ホスト101、103、105、107及び/又は109のうちの1つに実装されたソフトウェアの形で、コントローラ131の外部に常駐してもよい。ディストリビュータ136は、畳み込み符号化されたデータをRAMに、及び/又は直接ストレージ媒体160、170、180及び/又は190に分散させる。ディストリビュータ136が畳み込み符号化されたデータを媒体160、170、180及び190のような複数のデータ・ストレージ媒体に分散させる場合、分散はメタデータ152に従って行われるので、分散された畳み込み符号化されたデータを後でストレージ・デバイスから読み出して、元のデータ又は改訂データに復号することができる。
【0020】
特定回路142は、コントローラ131が、データ・ストレージ媒体160、170、180及び190、コントローラ131、並びにエンコーダ146の環境冷却のためのファン制御のような独自の機能を実行することを可能にする付加的なハードウェアを提供する。エンコーダ146は、例えば、それに限定されないが畳み込みエンコーダ回路200(図2)のような、畳み込みエンコーダとして実装されることができる。特定回路142は、パルス幅変調(PWM)制御、アナログ−デジタル変換(ADC)、デジタル−アナログ変換(DAC)、排他的論理和演算(「XOR」)などを提供する電子機器を含むことができる。さらに、特定回路142の全て又は一部は、ホスト101、103、105、107及び/又は109のうちの1つに実装されたソフトウェア実装などの形で、コントローラ131の外部に常駐してもよい。
【0021】
特定の実施形態において、エンコーダ146は、1データ・ビットを2データ・ビットの組に符号化する畳み込みエンコーダを含む。特定の実施形態において、エンコーダ146は、表300(図3)及び状態図400(図4)で表される畳み込み符号化アルゴリズムを含む。特定の実施形態において、デコーダ144は、PRMLトレリス500(図5)を含む。デコーダ144は、スタック図を構成することもできる。
【0022】
特定の実施形態において、既存ファイルに対して、「原子(atomic)」更新と呼ばれることもある小さい書き込み更新が実行される。特定の実施形態において、その既存ファイルは、以前に畳み込み符号化されたデータを含む。本方法は、データ・セット全体を再度畳み込み符号化することなく、以前に畳み込み符号化されたデータのビットのうちの比較的小さい部分を、既に畳み込み符号化されたデータ・セット内の他の畳み込み符号化されたデータのビットに変更する。本方法は、RAID3、4、又は5で用いられているような行パリティはどこにも使用しない。本方法は、RAID−6で用いられているような対角線パリティをどこにも使用しない。
【0023】
本発明に従って本方法を用いると、増分更新は、元データの変更された部分の排他的論理和(「XOR」)を(m)個の後続ゼロと組み合わせたものを含み、(m)は、畳み込みエンコーダ回路200(図2)の線形シフト・アレイの中のメモリ・ステップの数である。増分更新を畳み込み符号化し、次いで、元の畳み込み符号化されたデータとの間で排他的論理和演算を行い、更新を完了する。
【0024】
ここで図20を参照すると、ステップ1010において、本方法は、(m)個のレジスタ、即ち(m)レベルの遅延を含む畳み込みエンコーダを供給する。特定の実施形態において、ステップ1010の畳み込みエンコーダは、データ・ストレージ・システム100(図1)のようなデータ・ストレージ・システム内に配置される。特定の実施形態において、ステップ1010の畳み込みエンコーダは、ストレージ・アレイ130(図1)のようなストレージ・アレイ内に配置される。特定の実施形態において、ステップ1010の畳み込みエンコーダは、ストレージ・コントローラ131のようなストレージ・コントローラ内に配置される。特定の実施形態において、畳み込みエンコーダは、ストレージ・コントローラ131のようなストレージ・コントローラ内に配置されたエンコーダ146(図1)のような、エンコーダ内に配置される。
【0025】
特定の実施形態において、ステップ1010の畳み込みエンコーダは、エンコーダ回路200(図2)を含む。特定の実施形態において、ステップ1010の畳み込みエンコーダは、表300(図3)及び状態図400(図4)に示される符号化アルゴリズムを実行する。
【0026】
ここで図2を参照すると、畳み込みエンコーダ回路200は、符号化のために、入力情報ストリームU(J−3)205を一度に1ビットずつ受け取る。エンコーダ回路200は、レジスタ210、220及び230を含む3段シフト・レジスタを含む。レジスタ210、220及び230の初期内容は、符号化プロセスのためには、好ましくはゼロである。入力情報ストリームU(J−3)205と、レジスタ210、220及び230の出力とが加算器240によって選択的に加算されて出力V(J,1)245を生成し、加算器250によって選択的に加算されて出力V(J,2)255を生成する。特定の実施形態において、モジュロ−2加算器240及び250は、特定回路142内にXOR(排他的論理和)ゲートとして実装される。他の実施形態において、加算器240及び250は、ソフトウェア、ファームウェア、専用ロジックなどの使用により実装される。
【0027】
ここで図3及び図4を参照すると、特定の実施形態において、ステップ1010の畳み込みエンコーダは、表300及び状態図400で表される符号化アルゴリズムを用いる。装置及び方法についてのこの記述は、この装置及び方法が、畳み込みエンコーダ回路200、表300及び状態図400で表される畳み込み符号化アルゴリズムのみを使用すると限定するものと解釈されるべきではない。むしろ、他の実施形態において、本方法は異なる畳み込み符号化アルゴリズムを利用する。
【0028】
図3及び図4の符号化アルゴリズムは、S0410、S1411、S2412、S3413、S4414、S5415、S6416及びS7417の8つの状態を含む。状態間の各々の遷移の結果、ホスト101、103、105、107及び/又は109から受け取った1ビットの元データが符号化されて、図2、図3及び図4に示されるように、2ビットの符号化データになり、それらは、特定の実施形態において、次にストレージ媒体160、170、180及び190内に格納される。
【0029】
表300(図3)は、初期状態310、宛先状態320、元データ330、及び畳み込み符号化データ340の4つの列を含む。表300には、8つの状態S0、S1、S2、S3、S4、S5、S6、及びS7、並びに各初期状態からの2つの可能な遷移の総計に基づいて、全部で16個の行が存在する。表300は、状態図400によって生成されたものであり、ここでは、元データを符号化して符号化データを生成することを説明するために用いられる。再び図20を参照すると、ステップ1020において、本方法は、元データ600(図6)のような、元データを提供する。特定の実施形態において、ステップ1020の元データは、これらに限定されるものではないが、ホスト・コンピュータ101(図1)、103(図1)、105(図1)、107(図1)及び/又は109(図1)のような1つ又は複数のホスト・コンピュータによって提供される。ステップ1020は、元データを受け取ることをさらに含む。特定の実施形態において、ステップ1020の元データは、ストレージ・アレイ130(図1)のようなストレージ・アレイによって受け取られる。特定の実施形態において、ステップ1020の元データは、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって受け取られる。
【0030】
ステップ1030において、本方法は、ステップ1010の畳み込みエンコーダを用いて畳み込み符号化された元データを生成する。一例として、ここで図2、図6及び図8を参照すると、ステップ1030において、本方法は、畳み込みエンコーダ回路200と元データ600とを用いて、畳み込み符号化された元データ620を生成する。特定の実施形態において、ステップ1030は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1030は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1030は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。特定の実施形態において、ステップ1030は、エンコーダ146(図1)によって行われる。
【0031】
再び図20を参照すると、ステップ1040において、本方法は、ステップ1030の畳み込み符号化された元データを保存する。特定の実施形態において、ステップ1030の畳み込み符号化された元データは、データ・ストレージ媒体160(図1)、170(図1)、180(図1)及び/又は190(図1)のうちの1つ又は複数に保存される。特定の実施形態において、ステップ1040は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1040は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1040は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0032】
ステップ1050において、本方法は、改訂データ610(図7)のような、改訂されたデータを提供する。改訂データ610は、元データ600(図6)内のそれぞれのビットとは異なる、変更されたビット615を有する。特定の実施形態において、ステップ1050の改訂データは、これらに限定されるものではないが、ホスト・コンピュータ101(図1)、103(図1)、105(図1)、107(図1)及び/又は109(図1)のような1つ又は複数のホスト・コンピュータによって提供される。ステップ1050は、改訂データを受け取ることをさらに含む。特定の実施形態において、ステップ1050の改訂データは、ストレージ・アレイ130(図1)のようなストレージ・アレイによって受け取られる。特定の実施形態において、ステップ1050の改訂データは、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって受け取られる。
【0033】
ステップ1060において、本方法は、ステップ1020の元データとステップ1050の改訂データとの排他的論理和演算を行うことによって、XORデータ・ストリームを生成する。
【0034】
当業者であれば、「排他的論理和演算を行う(Exclusive OR'ing)」ことによって、元データが改訂データとの間で1ビットごとに排他的論理和されることを認識する。排他的論理和演算は、元データと改訂データの対応するビット位置間でのみ行われ、すなわち、ビット0は、ビット0との間でのみ排他的論理和され、ビット1は、ビット1との間でのみ排他的論理和され、以下同様である。表1は、4つの可能な排他的論理和の結果を挙げる。
【表1】
【0035】
ここで図6、図7及び図9を参照すると、ステップ1060において、元データ600と改訂データ610との排他的論理和演算を行うことにより、XORデータ・ストリーム700が生成される。XORデータ・ストリーム700は、元データ600と改訂データ610との間の対応する同一のビットの排他的論理和によって生成された複数の先行「ゼロ」を含む、部分702を含む。XORデータ・ストリーム700は、元データ600の対応するビットと改訂データ610の中の変更されたビット615との間の排他的論理和によって生成された複数の「1」を含む、部分704をさらに含む。XORデータ・ストリーム700は、元データ600と改訂データ610との間の対応する同一のビットの排他的論理和によって生成された複数の後続「ゼロ」を含む、部分706をさらに含む。
【0036】
再び図20を参照すると、ステップ1070において、本方法は、1つ又は複数の切り捨て(truncated)XORデータ・ストリームを生成して用いるかどうかを決定する。特定の実施形態において、ステップ1070は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1070は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1070は、ストレージ・コントローラ内に配置された、プロセッサ140(図1)のようなプロセッサによって行われる。
【0037】
方法が、1つ又は複数の切り捨てXORデータ・ストリームを生成せず用いないことを選択した場合には、方法は、ステップ1070からステップ1080に移り、ここで、方法は、XORデータ・ストリーム700のようなステップ1060のXORデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ1080は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1080は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1080は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0038】
一例として、ここで図2、図9及び図10を参照すると、XORデータ・ストリーム700と畳み込みエンコーダ回路200とを用いて、畳み込み符号化されたXORデータ・ストリーム710が生成される。畳み込み符号化されたXORデータ・ストリーム710は、エンコーダ回路200を用いて部分702を畳み込み符号化することによって生成された部分712を含む。複数の先行「0」を畳み込み符号化する場合、エンコーダ回路200は各「0」を「00」に符号化し、これはS0からS0への遷移の繰り返しを表す。
【0039】
畳み込み符号化されたXORデータ・ストリーム710は、部分704を(m)個の後続ゼロと組み合わせて畳み込み符号化することによって生成された部分714をさらに含み、ここで、畳み込みエンコーダ回路200の場合、(m)は3の値を有する。エンコーダ回路200は3つのレジスタ、即ち、レジスタ210、220及び230を含む。その結果、畳み込みエンコーダ回路200は、エンコーダが状態S0に戻る前に、最初の3つの後続ゼロを符号化する。その後、後続「0」の各々は、S0からS0への遷移の繰り返しを表す「00」に符号化される。畳み込み符号化されたXORデータ・ストリーム710は、部分706の残りの後続ゼロを畳み込みエンコーダ回路200を用いて畳み込み符号化することによって生成された、部分716をさらに含む。
【0040】
再び図20を参照すると、ステップ1090において、本方法は、ステップ1080の畳み込み符号化されたXORデータ・ストリームとステップ1030の畳み込み符号化された元データとの排他的論理和演算を行う。特定の実施形態において、ステップ1090は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1090は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1090は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0041】
一例として、ここで図11を参照すると、ステップ1090において、本方法は、畳み込み符号化された元データ620と畳み込み符号化されたXORデータ・ストリーム710との排他的論理和演算を行い、畳み込み符号化された改訂データ720を生成する。この実施形態において、本方法は、ステップ1090において、畳み込み符号化された元データ620の部分622と畳み込み符号化されたXORデータ・ストリーム710の先行ゼロ部分712との排他的論理和演算を行い、改訂データ720の畳み込み符号化された部分722を生成する。この実施形態において、本方法は、さらに、畳み込み符号化された元データ620の部分624と畳み込み符号化されたXORデータ・ストリーム710の変更されたビット/(m)個の後続ゼロ部分714との排他的論理和演算を行い、改訂データ720の更新された部分724を形成する。この実施形態において、方法は、さらに、畳み込み符号化された元データ620の部分626と畳み込み符号化されたXORデータ・ストリーム710の残りの後続ゼロ部分716との排他的論理和演算を行い、改訂データ720の畳み込み符号化された部分726を形成する。
【0042】
他の実施形態において、本方法は、第1の切り捨てXORデータ・ストリームを利用し、この場合、方法は、XORデータ・ストリーム710から先行ゼロを削除し、次いで、その第1の切り捨てXORデータ・ストリームを畳み込み符号化し、次いで、畳み込み符号化された第1の切り捨てXORデータ・ストリームと元データと排他的論理和演算を行い、改訂データを生成する。さらに他の実施形態において、本方法は、第2の切り捨てXORデータ・ストリームを利用し、この場合、本方法は、第1の切り捨てXORデータ・ストリームから(m)個の後続ゼロを除く全ての後続ゼロをさらに削除し、次いで、その第2の切り捨てXORデータ・ストリームを畳み込み符号化し、次いで、畳み込み符号化された第2の切り捨てXORデータ・ストリームと元データとの排他的論理和演算を行い、改訂データを生成する。
【0043】
再び図20を参照すると、ステップ1070において、本方法が1つ又は複数の切り捨てXORデータ・ストリームを生成して用いることを選択した場合には、本方法は、ステップ1070からステップ1110(図21)に移る。ステップ1110において、本方法は、第1の切り捨てXORデータ・ストリームを生成する。特定の実施形態において、ステップ1110は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1110は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1110は、ストレージ・コントローラ内に配置された、プロセッサ140(図1)のようなプロセッサによって行われる。
【0044】
一例として、ここで図9及び図12を参照すると、XORデータ・ストリーム700の部分702は、(N)個の先行ゼロを含む。ステップ1110において、本方法は、XORデータ・ストリーム700から、部分702を構成する(N)個の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリーム800を生成する。第1の切り捨てXORデータ・ストリーム800は、変更されたビット部分804を後続ゼロ部分806と組み合わせて含む。
【0045】
再び図21を参照すると、ステップ1120において、本方法は、第2の切り捨てXORデータ・ストリームを生成して用いるかどうかを決定する。特定の実施形態において、ステップ1120は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1120は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1120は、ストレージ・コントローラ内に配置された、プロセッサ140(図1)のようなプロセッサによって行われる。
【0046】
ステップ1120において、本方法が、第2の切り捨てXORデータ・ストリームを生成せず用いないことを選択した場合には、本方法は、ステップ1120からステップ1130に移り、ここで、方法は第1の切り捨てXORデータ・ストリーム800(図12)のようなステップ1110の第1の切り捨てXORデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ1130は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1130は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1130は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0047】
一例として、ここで図2、図12及び図13を参照すると、第1の切り捨てXORデータ・ストリーム800と畳み込みエンコーダ回路200とを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリーム810が生成される。畳み込み符号化された第1の切り捨てXORデータ・ストリーム810は、部分804を(m)個の後続ゼロと組み合わせて畳み込み符号化することによって生成された部分814をさらに含み、ここで、畳み込みエンコーダ回路200の場合、(m)は3の値を有する。エンコーダ回路200は3つのレジスタ、即ち、レジスタ210、220及び230を含む。その結果、畳み込みエンコーダ回路200は、エンコーダが状態S0に戻る前に、最初の3つの後続ゼロを符号化する。その後、後続「0」の各々は、S0からS0への遷移の繰り返しを表す「00」に符号化される。畳み込み符号化された第1の切り捨てXORデータ・ストリーム810は、部分806の残りの後続ゼロを畳み込みエンコーダ回路200を用いて畳み込み符号化することによって生成された、部分816をさらに含む。
【0048】
再び図21を参照すると、ステップ1140において、本方法は、ステップ1130の畳み込み符号化された第1の切り捨てXORデータ・ストリームを、ステップ1030(図20)の畳み込み符号化された元データに索引付けする。ステップ1110において、本方法は、ステップ1060(図20)のXORデータ・ストリームから、(N)個の先行ゼロを削除し、第1の切り捨てXORデータ・ストリームを生成した。ステップ1140において、本方法は、ステップ1130の畳み込み符号化された第1の切り捨てXORデータ・ストリームの第1ビットを、畳み込み符号化された元データの第[(2)(N)+1]番目のビットに位置合わせする。
【0049】
特定の実施形態において、ステップ1140は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1140は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1140は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0050】
一例として、ここで図9、図12及び図14を参照すると、XORデータ・ストリーム700は(N)個の先行ゼロを含み、ここで(N)は13である。これらの13個の先行ゼロは、第1の切り捨てXORデータ・ストリーム800を生成するために削除された。ステップ1140において、本方法は、畳み込み符号化された第1の切り捨てXORデータ・ストリーム810の第1ビットを、畳み込み符号化された元データ620の第27番目のビット[(2)(13)+1]に位置合わせする。
【0051】
再び図21を参照すると、本方法は、ステップ1150において、索引付けされたステップ1130の畳み込み符号化されたXORデータ・ストリームとステップ1030の畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。特定の実施形態において、ステップ1150は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1150は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1150は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0052】
一例として、図15を参照すると、畳み込み符号化された第1の切り捨てXORデータ・ストリーム810は、畳み込み符号化された元データ620の部分622に対応する部分を含まない。従って、ステップ1150において、本方法は、畳み込み符号化された改訂データ720の第1の部分722として、部分622をコピーする。ステップ1150において、さらに、本方法は、畳み込み符号化された元データ620の部分624と畳み込み符号化された第1の切り捨てXORデータ・ストリーム810の部分814との排他的論理和演算を行って、畳み込み符号化された改訂データ720の畳み込み符号化された部分724を生成し、畳み込み符号化された元データ620の部分626と畳み込み符号化された第1の切り捨てXORデータ・ストリーム810の部分816との排他的論理和演算を行って、畳み込み符号化された改訂データ720の第3の部分726を生成し、畳み込み符号化された改訂データ720の生成を完了する。
【0053】
再び図21を参照すると、ステップ1120において、本方法が、第2の切り捨てXORデータ・ストリームを生成して用いることを選択した場合には、本方法は、ステップ1120からステップ1160に移り、ここで、本方法は第2の切り捨てXORデータ・ストリームを生成する。特定の実施形態において、ステップ1160は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1160は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1160は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0054】
一例として、ここで図12及び図16を参照すると、第1の切り捨てXORデータ・ストリーム800は、変更ビット部分804と、(P)個の後続ゼロを含む部分806とを含む。ステップ1160において、本方法は、[(P)−(m)]個の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリーム900を生成し、ここで、(m)はステップ1010(図20)の畳み込みエンコーダにおいて用いられるレジスタの数に等しい。図16の図示された実施形態において、第2の切り捨てXORデータ・ストリーム900は、変更されたビット部分902を3個の後続ゼロ部分904と組み合わせて含む。
【0055】
再び図21を参照すると、本方法は、ステップ1170において、第2の切り捨てXORデータ・ストリーム900(図16)のような、ステップ1160の第2の切り捨てXORデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ1170は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1170は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1170は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0056】
一例として、ここで図2、図16及び図17を参照すると、第2の切り捨てXORデータ・ストリーム900と畳み込みエンコーダ回路200とを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリーム910が生成される。畳み込み符号化された第2の切り捨てXORデータ・ストリーム910は、部分902と904とを畳み込み符号化することによって生成される。
【0057】
再び図21を参照すると、ステップ1180において、本方法は、ステップ1170の畳み込み符号化された第2の切り捨てXORデータ・ストリームを、ステップ1030(図20)の畳み込み符号化された元データに索引付けする。ステップ1110において、本方法は、ステップ1060(図20)のXORデータ・ストリームから、(N)個の先行ゼロを削除し、第1の切り捨てXORデータ・ストリームを生成した。ステップ1180において、本方法は、ステップ1170の畳み込み符号化された第2の切り捨てXORデータ・ストリームの第1ビットを、畳み込み符号化された元データの第[(2)(N)+1]番目のビットに位置合わせする。
【0058】
特定の実施形態において、ステップ1180は、ステップ1020(図20)の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1180は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1180は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0059】
一例として、ここで図9、図12及び図18を参照すると、XORデータ・ストリーム700は(N)個の先行ゼロを含み、ここで(N)は13である。これらの13個の先行ゼロは、第1の切り捨てXORデータ・ストリーム800を生成するために削除された。ステップ1180において、本方法は、畳み込み符号化された第2の切り捨てXORデータ・ストリーム910の第1ビットを、畳み込み符号化された元データ620の第27番目のビット[(2)(13)+1]に位置合わせする。
【0060】
再び図21を参照すると、本方法は、ステップ1190において、索引付けされたステップ1180の畳み込み符号化された第2の切り捨てXORデータ・ストリームとステップ1030の畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。特定の実施形態において、ステップ1190は、ステップ1020の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ1190は、ストレージ・コントローラ131(図1)のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ1190は、ストレージ・コントローラ内に配置されたプロセッサ140(図1)のような、プロセッサによって行われる。
【0061】
一例として、図19を参照すると、畳み込み符号化された第2の切り捨てXORデータ・ストリーム910は、畳み込み符号化された元データ620の部分622に対応する部分を含まず、畳み込み符号化された元データ620の部分626に対応する部分も含まない。ステップ1190において、本方法は、畳み込み符号化された改訂データ720の部分722として、部分622をコピーする。ステップ1190において、さらに、本方法は、畳み込み符号化された改訂データ720の部分726として、部分626をコピーする。ステップ1190において、さらに、本方法は、畳み込み符号化された元データ620の部分624と畳み込み符号化された第2の切り捨てXORデータ・ストリーム910の部分との排他的論理和演算を行って、更新された部分724を作成し、それにより、畳み込み符号化された改訂データ720の生成を完了する。
【0062】
特定の実施形態において、図20及び図21において列挙された個々のステップは、組み合わせることもでき、省くこともでき、又は順序を変更することもできる。例えば、本方法の第1の実施形態は、図20のステップ1010、1020、1030、1040、1050、1060、1080及び1090を含む8つのステップを含む。本方法の第2の実施形態は、図20のステップ1010、1020、1030、1040、1050、1060と、図21のステップ1110、1130、1140及び1150との組み合わせを含む、10個のステップを含む。本方法の第3の実施形態は、図20のステップ1010、1020、1030、1040、1050、1060と、図21のステップ1110、1160、1170、1180及び1190との組み合わせを含む、11個のステップを含む。
【0063】
8ステップの第1の実施形態は、改訂データ中で改訂されたビットと元のビットとの間の比が高い場合、即ち、元のビットのほとんど全てが改訂されている場合に最も有用である。一方、改訂されたビットと元のビットとの間の比が非常に低い場合、即ち「原子」更新の場合には、11ステップの第3の実施形態の使用が好ましい。
【0064】
第3の実施形態は11個のステップを含むが、その第3の実施形態は、かなり切り捨てられたXORデータ・ストリーム、即ち、第2の切り捨てXORデータ・ストリームが畳み込み符号化されるステップ1170を利用するので、第3の実施形態は「原子」更新のためにそれほど多くの計算機能力及び時間を必要としない。さらに、11ステップの第3の実施形態は、その畳み込み符号化された第2のXORデータのみが畳み込み符号化された元データと排他的論理和されるステップ1190を利用するので、第3の実施形態はそれほど多くの計算機能力及び時間を必要としない。
【0065】
前述の装置及び方法の実施形態のいずれも、データ・ストレージ・サービス・プロバイダによって、1つ又は複数のデータ・ストレージ・サービス顧客にデータ・ストレージ・サービスを提供するために用いることができる。特定の実施形態において、1つ又は複数のデータ・ストレージ・サービス顧客は、ホスト・コンピュータ101(図1)、103(図1)、105(図1)、107(図1)及び/又は109(図1)のうちの1つ又は複数を所有し、及び/又は操作する。これらの1つ又は複数のデータ・ストレージ・サービス顧客は、1つ又は複数のホスト・コンピュータからストレージ・アレイ130(図1)のようなストレージ・アレイに顧客データを提供し、そのストレージ・アレイは、データ・ストレージ・サービス・プロバイダによって所有され、及び/又は操作される。
【0066】
特定の実施形態において、本発明は、メモリ150(図1)に常駐する命令を含み、これらの命令は、プロセッサ140(図1)のようなプロセッサによって、図20で列挙されたステップ1020、1030、1040、1050、1060、1070、1080及び/又は1090のうちの1つ又は複数のステップ、及び/又は、図21で列挙されたステップ1110、1120、1130、1140、1150、1160、1170、1180及び/又は1190のうちの1つ又は複数のステップを行うために実行される。
【0067】
他の実施形態において、本発明は、いずれかの他のコンピュータ・プログラムに常駐する命令を含み、これらの命令は、システム100の外部又は内部のコンピュータによって、図20で列挙されたステップ1020、1030、1040、1050、1060、1070、1080及び/又は1090のうちの1つ又は複数のステップ、及び/又は、図21で列挙されたステップ1110、1120、1130、1140、1150、1160、1170、1180及び/又は1190のうちの1つ又は複数のステップを行うために実行される。どちらの場合においても、命令は、例えば、磁気情報ストレージ媒体、光情報ストレージ媒体、電子情報ストレージ媒体を含む、情報ストレージ媒体内で符号化されることができる。「電子ストレージ媒体」という用語によって、本出願人は、例えば、PROM、EPROM、EEPROM、フラッシュPROM、コンパクトフラッシュ、スマートメディアなどのようなデバイスのことを意味する。
【0068】
本発明の好ましい実施形態を詳細に説明してきたが、当業者であれば、添付の特許請求の範囲で述べられる本発明の範囲を逸脱することなく、これらの実施形態に対する修正及び改造を想起することができることは明らかである。
【符号の説明】
【0069】
100:データ・ストレージ・システム
111、113、115、117、119、135:I/Oインターフェース
130:ストレージ・アレイ
131:コントローラ
145:バス
200:畳み込みエンコーダ回路
205:入力情報ストリーム
210、220、230:シフト・レジスタ
240、250:加算器
245、255:出力
300、400:畳み込み符号化アルゴリズム
500:PRMLトレリス
600:元データ
610:改訂データ
620:畳み込み符号化された元データ
700:XORデータ・ストリーム
710:畳み込み符号化されたXORデータ・ストリーム
720:畳み込み符号化された改訂データ
800:第1の切り捨てXORデータ・ストリーム
810:畳み込み符号化された第1の切り捨てXORデータ・ストリーム
900:第2の切り捨てXORデータ・ストリーム
910:畳み込み符号化された第2の切り捨てXORデータ・ストリーム
【特許請求の範囲】
【請求項1】
畳み込み符号化されたデータを生成する方法であって、
(m)段を含む畳み込みエンコーダを供給するステップであって、前記(m)は1以上である、ステップと、
元データを提供するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された元データを生成するステップと、
改訂データを提供するステップであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、ステップと、
前記元データと前記改訂データとの排他的論理和演算を行うことによってXORデータ・ストリームを生成するステップであって、前記XORデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、ステップと
切り捨てXORデータ・ストリームを用いるかどうかを決定するステップと、
前記切り捨てXORデータ・ストリームを用いない場合に有効となる、
前記畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成するステップと、
前記畳み込み符号化されたXORデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うステップと
を含む方法。
【請求項2】
前記畳み込みエンコーダを供給するステップは、3段を含む畳み込みエンコーダを供給することをさらに含む、請求項1に記載の方法。
【請求項3】
ホスト・コンピュータと通信するデータ・ストレージ・システムを供給するステップであって、前記データ・ストレージ・システムは、前記畳み込みエンコーダとデータ・ストレージ媒体とを含むステップをさらに含み、
前記元データを提供するステップは、前記ホスト・コンピュータによって前記データ・ストレージ・システムに前記元データを提供するステップをさらに含む、
請求項1又は請求項2に記載の方法。
【請求項4】
前記畳み込み符号化された元データを前記データ・ストレージ媒体に保存するステップをさらに含む、請求項3に記載の方法。
【請求項5】
前記元データは(N)ビットを含み、前記畳み込み符号化された元データは(2)(N)ビットを含む、請求項1から請求項4のいずれか1項に記載の方法。
【請求項6】
切り捨てXORデータ・ストリームが用いられる場合に有効となる、第2の切り捨てXORデータ・ストリームを用いるかどうかを決定するステップと、
第2の切り捨てXORデータ・ストリームを用いない場合に有効となる、前記XORデータ・ストリームから前記複数の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリームを形成するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリームを形成するステップと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項1から請求項5のいずれか1項に記載の方法。
【請求項7】
第2の切り捨てXORデータ・ストリームが用いられる場合に有効となる、前記第1の切り捨てXORデータ・ストリームから(m)個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリームを形成するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリームを形成するステップと、
前記畳み込み符号化された第2の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記畳み込み符号化された第2の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項6に記載の方法。
【請求項8】
(m)段を含む畳み込みエンコーダと、畳み込み符号化されたデータを生成するためのコンピュータ可読プログラム・コードが配置されたコンピュータ可読媒体とを含む製品であって、前記(m)は1以上であり、前記コンピュータ可読プログラム・コードは、
元データを受け取ることと、
畳み込み符号化された元データを生成することと、
改訂データを受け取ることであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含むことと、
前記元データと前記改訂データとの排他的論理和演算を行うことによって、XORデータ・ストリームを生成することであって、前記XORデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含むことと、
切り捨てXORデータ・ストリームを用いるかどうかを決定することと、
切り捨てXORデータ・ストリームを用いない場合に有効となる、
前記畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成することと、
前記畳み込み符号化されたXORデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップを含む、
製品。
【請求項9】
前記畳み込みエンコーダは3段を含む、請求項8に記載の製品。
【請求項10】
前記製品は、データ・ストレージ媒体を含むデータ・ストレージ・システム内に配置され、前記コンピュータ可読プログラム・コードは、前記畳み込み符号化された元データを前記データ・ストレージ媒体に格納することを実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項8に記載の製品。
【請求項11】
前記元データは(N)ビットを含み、前記畳み込み符号化された元データは(2)(N)ビットを含み、前記(N)は1以上である、請求項8に記載の製品。
【請求項12】
前記コンピュータ可読プログラム・コードは、
切り捨てXORデータ・ストリームが用いられる場合に有効となる、第2の切り捨てXORデータ・ストリームを用いるかどうかを決定することと、
第2の切り捨てXORデータ・ストリームを用いない場合に有効となる、前記XORデータ・ストリームから前記複数の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリームを形成することと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリームを形成することと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けすることと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項8に記載の製品。
【請求項13】
前記コンピュータ可読プログラム・コードは、
第2の切り捨てXORデータ・ストリームが用いられる場合に有効となる、前記第1の切り捨てXORデータ・ストリームから(m)個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリームを形成することと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリームを形成することと、
前記畳み込み符号化された第2の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けすることと、
前記畳み込み符号化された第2の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項12に記載の製品。
【請求項14】
プロセッサと、畳み込みエンコーダと、データ・ストレージ媒体とを含むデータ・ストレージ・システムに配置されたコンピュータ可読媒体内で符号化されたコンピュータ・プログラムであって、前記コンピュータ・プログラムは、畳み込み符号化されたデータを生成するために、前記プロセッサと共に用いることが可能であり、
前記プログラム可能なコンピュータ・プロセッサに元データを受け取らせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに畳み込み符号化された元データを生成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに改訂データを受け取らせるコンピュータ可読プログラム・コードであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに前記元データと前記改訂データとの排他的論理和演算を行わせることによって、XORデータ・ストリームを生成させるコンピュータ可読プログラム・コードであって、前記XORデータ・ストリームは複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに切り捨てXORデータ・ストリームを用いるかどうかを決定させる、コンピュータ可読プログラム・コードと、
切り捨てXORデータ・ストリームを用いない場合に、前記プログラム可能なコンピュータ・プロセッサに、
前記畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成させ、
前記畳み込み符号化されたXORデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行わせる、コンピュータ可読プログラム・コードと
を含む、コンピュータ・プログラム。
【請求項15】
前記畳み込みエンコーダは3段を含む、請求項14に記載のコンピュータ・プログラム。
【請求項16】
前記プログラム可能なコンピュータ・プロセッサに前記畳み込み符号化された元データを前記ストレージ媒体に格納させる、コンピュータ可読プログラム・コードをさらに含む、請求項14又は請求項15に記載のコンピュータ・プログラム。
【請求項17】
前記元データは(N)ビットを含み、前記畳み込み符号化された元データは(2)(N)ビットを含み、前記(N)は1以上である、請求項14から請求項16のいずれか1項に記載のコンピュータ・プログラム。
【請求項18】
切り捨てXORデータ・ストリームが用いられる場合に、前記プログラム可能なコンピュータ・プロセッサに、第2の切り捨てXORデータ・ストリームを用いるかどうかを決定させる、コンピュータ可読プログラム・コードと、
第2の切り捨てXORデータ・ストリームを用いない場合に、前記プログラム可能なコンピュータ・プロセッサに、前記XORデータ・ストリームから前記複数の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込みエンコーダを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第1の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けさせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第1の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行わせる、コンピュータ可読プログラム・コードと、
をさらに含む、請求項14から請求項17のいずれか1項に記載のコンピュータ・プログラム。
【請求項19】
第2の切り捨てXORデータ・ストリームが用いられる場合に、前記プログラム可能なコンピュータ・プロセッサに、前記第1の切り捨てXORデータ・ストリームから(m)個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込みエンコーダを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第2の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けさせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第2の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和を行わせる、コンピュータ可読プログラム・コードと
をさらに含む、請求項18に記載のコンピュータ・プログラム。
【請求項20】
データ・ストレージ・サービス・プロバイダによって、データ・ストレージ・サービス顧客にデータ・ストレージ・サービスを提供する方法であって、
(m)段を含む畳み込みエンコーダを供給するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記データ・ストレージ・サービスから元の顧客データを受け取るステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された元の顧客データを生成するステップと
を含む方法。
【請求項21】
前記畳み込みエンコーダを供給するステップは、前記データ・ストレージ・サービス顧客によって、3段を含む畳み込みエンコーダを供給することをさらに含み、
前記データ・ストレージ・サービス顧客は、前記生成するステップを実施する、
請求項20に記載の方法。
【請求項22】
前記データ・ストレージ・サービス顧客によって改訂データを受け取るステップであって、前記改訂された顧客データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、ステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記元の顧客データと前記改訂された顧客データとの排他的論理和演算を行うことにより、XORデータ・ストリームを生成するステップであって、前記XORデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、ステップと、
前記データ・ストレージ・サービス・プロバイダによって、切り捨てXORデータ・ストリームを用いるかどうかを決定するステップと、
切り捨てXORデータ・ストリームを用いない場合に有効となるステップであって、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化されたXORデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項20に記載の方法。
【請求項23】
切り捨てXORデータ・ストリームが用いられる場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、第2の切り捨てXORデータ・ストリームを用いるかどうかを決定するステップと、
第2の切り捨てXORデータ・ストリームを用いない場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、前記XORデータ・ストリームから前記複数の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリームを形成することと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第1の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項22に記載の方法。
【請求項24】
第2の切り捨てXORデータ・ストリームが用いられる場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、前記第1の切り捨てXORデータ・ストリームから(m)個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第2の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第2の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項23に記載の方法。
【請求項25】
ストレージ・コントローラであって、
(m)段を含む畳み込みエンコーダを含み、前記(m)は1以上であり、
前記畳み込みエンコーダは、(N)ビットを含むデータを入力し、(2)(N)ビットを含む畳み込み符号化されたデータを生成し、前記(N)は1以上である、
ストレージ・コントローラ。
【請求項26】
デコーダをさらに含み、
前記デコーダは、前記畳み込み符号化されたデータを入力し、前記(N)ビットを含むデータを生成する、請求項25に記載のストレージ・コントローラ。
【請求項27】
前記デコーダは、PRMLトレリスを含む、請求項26に記載のストレージ・コントローラ。
【請求項28】
ストレージ・コントローラを含むデータ・ストレージ・システムであって、前記ストレージ・コントローラは、
(m)段を含む畳み込みエンコーダを含み、前記(m)は1以上であり、
前記畳み込みエンコーダは、(N)ビットを含むデータを入力し、(2)(N)ビットを含む畳み込み符号化されたデータを生成し、前記(N)は1以上である、
データ・ストレージ・システム。
【請求項29】
前記ストレージ・コントローラは、
デコーダをさらに含み、
前記デコーダは、前記畳み込み符号化されたデータを入力し、前記(N)ビットを含むデータを生成する、請求項28に記載のデータ・ストレージ・システム。
【請求項30】
前記デコーダは、PRMLトレリスを備える、請求項29に記載のデータ・ストレージ・システム。
【請求項31】
プログラム・コード手段を含むコンピュータ・プログラムであって、前記プログラム・コード手段は、前記プログラムがコンピュータ上で実行されるときに、請求項1から請求項7の全てのステップを実行するように適合されている、コンピュータ・プログラム。
【請求項1】
畳み込み符号化されたデータを生成する方法であって、
(m)段を含む畳み込みエンコーダを供給するステップであって、前記(m)は1以上である、ステップと、
元データを提供するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された元データを生成するステップと、
改訂データを提供するステップであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、ステップと、
前記元データと前記改訂データとの排他的論理和演算を行うことによってXORデータ・ストリームを生成するステップであって、前記XORデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、ステップと
切り捨てXORデータ・ストリームを用いるかどうかを決定するステップと、
前記切り捨てXORデータ・ストリームを用いない場合に有効となる、
前記畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成するステップと、
前記畳み込み符号化されたXORデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うステップと
を含む方法。
【請求項2】
前記畳み込みエンコーダを供給するステップは、3段を含む畳み込みエンコーダを供給することをさらに含む、請求項1に記載の方法。
【請求項3】
ホスト・コンピュータと通信するデータ・ストレージ・システムを供給するステップであって、前記データ・ストレージ・システムは、前記畳み込みエンコーダとデータ・ストレージ媒体とを含むステップをさらに含み、
前記元データを提供するステップは、前記ホスト・コンピュータによって前記データ・ストレージ・システムに前記元データを提供するステップをさらに含む、
請求項1又は請求項2に記載の方法。
【請求項4】
前記畳み込み符号化された元データを前記データ・ストレージ媒体に保存するステップをさらに含む、請求項3に記載の方法。
【請求項5】
前記元データは(N)ビットを含み、前記畳み込み符号化された元データは(2)(N)ビットを含む、請求項1から請求項4のいずれか1項に記載の方法。
【請求項6】
切り捨てXORデータ・ストリームが用いられる場合に有効となる、第2の切り捨てXORデータ・ストリームを用いるかどうかを決定するステップと、
第2の切り捨てXORデータ・ストリームを用いない場合に有効となる、前記XORデータ・ストリームから前記複数の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリームを形成するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリームを形成するステップと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項1から請求項5のいずれか1項に記載の方法。
【請求項7】
第2の切り捨てXORデータ・ストリームが用いられる場合に有効となる、前記第1の切り捨てXORデータ・ストリームから(m)個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリームを形成するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリームを形成するステップと、
前記畳み込み符号化された第2の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記畳み込み符号化された第2の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項6に記載の方法。
【請求項8】
(m)段を含む畳み込みエンコーダと、畳み込み符号化されたデータを生成するためのコンピュータ可読プログラム・コードが配置されたコンピュータ可読媒体とを含む製品であって、前記(m)は1以上であり、前記コンピュータ可読プログラム・コードは、
元データを受け取ることと、
畳み込み符号化された元データを生成することと、
改訂データを受け取ることであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含むことと、
前記元データと前記改訂データとの排他的論理和演算を行うことによって、XORデータ・ストリームを生成することであって、前記XORデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含むことと、
切り捨てXORデータ・ストリームを用いるかどうかを決定することと、
切り捨てXORデータ・ストリームを用いない場合に有効となる、
前記畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成することと、
前記畳み込み符号化されたXORデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップを含む、
製品。
【請求項9】
前記畳み込みエンコーダは3段を含む、請求項8に記載の製品。
【請求項10】
前記製品は、データ・ストレージ媒体を含むデータ・ストレージ・システム内に配置され、前記コンピュータ可読プログラム・コードは、前記畳み込み符号化された元データを前記データ・ストレージ媒体に格納することを実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項8に記載の製品。
【請求項11】
前記元データは(N)ビットを含み、前記畳み込み符号化された元データは(2)(N)ビットを含み、前記(N)は1以上である、請求項8に記載の製品。
【請求項12】
前記コンピュータ可読プログラム・コードは、
切り捨てXORデータ・ストリームが用いられる場合に有効となる、第2の切り捨てXORデータ・ストリームを用いるかどうかを決定することと、
第2の切り捨てXORデータ・ストリームを用いない場合に有効となる、前記XORデータ・ストリームから前記複数の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリームを形成することと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリームを形成することと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けすることと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項8に記載の製品。
【請求項13】
前記コンピュータ可読プログラム・コードは、
第2の切り捨てXORデータ・ストリームが用いられる場合に有効となる、前記第1の切り捨てXORデータ・ストリームから(m)個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリームを形成することと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリームを形成することと、
前記畳み込み符号化された第2の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けすることと、
前記畳み込み符号化された第2の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項12に記載の製品。
【請求項14】
プロセッサと、畳み込みエンコーダと、データ・ストレージ媒体とを含むデータ・ストレージ・システムに配置されたコンピュータ可読媒体内で符号化されたコンピュータ・プログラムであって、前記コンピュータ・プログラムは、畳み込み符号化されたデータを生成するために、前記プロセッサと共に用いることが可能であり、
前記プログラム可能なコンピュータ・プロセッサに元データを受け取らせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに畳み込み符号化された元データを生成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに改訂データを受け取らせるコンピュータ可読プログラム・コードであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに前記元データと前記改訂データとの排他的論理和演算を行わせることによって、XORデータ・ストリームを生成させるコンピュータ可読プログラム・コードであって、前記XORデータ・ストリームは複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに切り捨てXORデータ・ストリームを用いるかどうかを決定させる、コンピュータ可読プログラム・コードと、
切り捨てXORデータ・ストリームを用いない場合に、前記プログラム可能なコンピュータ・プロセッサに、
前記畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成させ、
前記畳み込み符号化されたXORデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行わせる、コンピュータ可読プログラム・コードと
を含む、コンピュータ・プログラム。
【請求項15】
前記畳み込みエンコーダは3段を含む、請求項14に記載のコンピュータ・プログラム。
【請求項16】
前記プログラム可能なコンピュータ・プロセッサに前記畳み込み符号化された元データを前記ストレージ媒体に格納させる、コンピュータ可読プログラム・コードをさらに含む、請求項14又は請求項15に記載のコンピュータ・プログラム。
【請求項17】
前記元データは(N)ビットを含み、前記畳み込み符号化された元データは(2)(N)ビットを含み、前記(N)は1以上である、請求項14から請求項16のいずれか1項に記載のコンピュータ・プログラム。
【請求項18】
切り捨てXORデータ・ストリームが用いられる場合に、前記プログラム可能なコンピュータ・プロセッサに、第2の切り捨てXORデータ・ストリームを用いるかどうかを決定させる、コンピュータ可読プログラム・コードと、
第2の切り捨てXORデータ・ストリームを用いない場合に、前記プログラム可能なコンピュータ・プロセッサに、前記XORデータ・ストリームから前記複数の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込みエンコーダを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第1の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けさせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第1の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行わせる、コンピュータ可読プログラム・コードと、
をさらに含む、請求項14から請求項17のいずれか1項に記載のコンピュータ・プログラム。
【請求項19】
第2の切り捨てXORデータ・ストリームが用いられる場合に、前記プログラム可能なコンピュータ・プロセッサに、前記第1の切り捨てXORデータ・ストリームから(m)個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込みエンコーダを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第2の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けさせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第2の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和を行わせる、コンピュータ可読プログラム・コードと
をさらに含む、請求項18に記載のコンピュータ・プログラム。
【請求項20】
データ・ストレージ・サービス・プロバイダによって、データ・ストレージ・サービス顧客にデータ・ストレージ・サービスを提供する方法であって、
(m)段を含む畳み込みエンコーダを供給するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記データ・ストレージ・サービスから元の顧客データを受け取るステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された元の顧客データを生成するステップと
を含む方法。
【請求項21】
前記畳み込みエンコーダを供給するステップは、前記データ・ストレージ・サービス顧客によって、3段を含む畳み込みエンコーダを供給することをさらに含み、
前記データ・ストレージ・サービス顧客は、前記生成するステップを実施する、
請求項20に記載の方法。
【請求項22】
前記データ・ストレージ・サービス顧客によって改訂データを受け取るステップであって、前記改訂された顧客データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、ステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記元の顧客データと前記改訂された顧客データとの排他的論理和演算を行うことにより、XORデータ・ストリームを生成するステップであって、前記XORデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、ステップと、
前記データ・ストレージ・サービス・プロバイダによって、切り捨てXORデータ・ストリームを用いるかどうかを決定するステップと、
切り捨てXORデータ・ストリームを用いない場合に有効となるステップであって、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化されたXORデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化されたXORデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項20に記載の方法。
【請求項23】
切り捨てXORデータ・ストリームが用いられる場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、第2の切り捨てXORデータ・ストリームを用いるかどうかを決定するステップと、
第2の切り捨てXORデータ・ストリームを用いない場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、前記XORデータ・ストリームから前記複数の先行ゼロを削除することによって、第1の切り捨てXORデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化された第1の切り捨てXORデータ・ストリームを形成することと、
前記畳み込み符号化された第1の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第1の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項22に記載の方法。
【請求項24】
第2の切り捨てXORデータ・ストリームが用いられる場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、前記第1の切り捨てXORデータ・ストリームから(m)個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第2の切り捨てXORデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化された第2の切り捨てXORデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第2の切り捨てXORデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第2の切り捨てXORデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項23に記載の方法。
【請求項25】
ストレージ・コントローラであって、
(m)段を含む畳み込みエンコーダを含み、前記(m)は1以上であり、
前記畳み込みエンコーダは、(N)ビットを含むデータを入力し、(2)(N)ビットを含む畳み込み符号化されたデータを生成し、前記(N)は1以上である、
ストレージ・コントローラ。
【請求項26】
デコーダをさらに含み、
前記デコーダは、前記畳み込み符号化されたデータを入力し、前記(N)ビットを含むデータを生成する、請求項25に記載のストレージ・コントローラ。
【請求項27】
前記デコーダは、PRMLトレリスを含む、請求項26に記載のストレージ・コントローラ。
【請求項28】
ストレージ・コントローラを含むデータ・ストレージ・システムであって、前記ストレージ・コントローラは、
(m)段を含む畳み込みエンコーダを含み、前記(m)は1以上であり、
前記畳み込みエンコーダは、(N)ビットを含むデータを入力し、(2)(N)ビットを含む畳み込み符号化されたデータを生成し、前記(N)は1以上である、
データ・ストレージ・システム。
【請求項29】
前記ストレージ・コントローラは、
デコーダをさらに含み、
前記デコーダは、前記畳み込み符号化されたデータを入力し、前記(N)ビットを含むデータを生成する、請求項28に記載のデータ・ストレージ・システム。
【請求項30】
前記デコーダは、PRMLトレリスを備える、請求項29に記載のデータ・ストレージ・システム。
【請求項31】
プログラム・コード手段を含むコンピュータ・プログラムであって、前記プログラム・コード手段は、前記プログラムがコンピュータ上で実行されるときに、請求項1から請求項7の全てのステップを実行するように適合されている、コンピュータ・プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【公表番号】特表2010−536214(P2010−536214A)
【公表日】平成22年11月25日(2010.11.25)
【国際特許分類】
【出願番号】特願2010−519425(P2010−519425)
【出願日】平成20年7月28日(2008.7.28)
【国際出願番号】PCT/EP2008/059873
【国際公開番号】WO2009/019160
【国際公開日】平成21年2月12日(2009.2.12)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.イーサネット
2.コンパクトフラッシュ
3.Bluetooth
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【Fターム(参考)】
【公表日】平成22年11月25日(2010.11.25)
【国際特許分類】
【出願日】平成20年7月28日(2008.7.28)
【国際出願番号】PCT/EP2008/059873
【国際公開番号】WO2009/019160
【国際公開日】平成21年2月12日(2009.2.12)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.イーサネット
2.コンパクトフラッシュ
3.Bluetooth
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【Fターム(参考)】
[ Back to top ]