(57)【要約】【課題】  畳み込み符号化されたデータを生成する装置及び方法を提供すること。【解決手段】  本方法は、畳み込みエンコーダを供給する。本方法は、元データを受け取り、畳み込み符号化された元データを生成する。本方法は、改訂データを受け取る。本方法は、元データと改訂データとの排他的論理和演算を行うことによってＸＯＲデータ・ストリームを生成し、畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成し、畳み込み符号化されたＸＯＲデータ・ストリームと畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。【選択図】      図１
2010536214.tif 000002
【特許請求の範囲】
【請求項１】
畳み込み符号化されたデータを生成する方法であって、
（ｍ）段を含む畳み込みエンコーダを供給するステップであって、前記（ｍ）は１以上である、ステップと、
元データを提供するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された元データを生成するステップと、
改訂データを提供するステップであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、ステップと、
前記元データと前記改訂データとの排他的論理和演算を行うことによってＸＯＲデータ・ストリームを生成するステップであって、前記ＸＯＲデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、ステップと
切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定するステップと、
前記切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、
前記畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成するステップと、
前記畳み込み符号化されたＸＯＲデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うステップと
を含む方法。
【請求項２】
前記畳み込みエンコーダを供給するステップは、３段を含む畳み込みエンコーダを供給することをさらに含む、請求項１に記載の方法。
【請求項３】
ホスト・コンピュータと通信するデータ・ストレージ・システムを供給するステップであって、前記データ・ストレージ・システムは、前記畳み込みエンコーダとデータ・ストレージ媒体とを含むステップをさらに含み、
前記元データを提供するステップは、前記ホスト・コンピュータによって前記データ・ストレージ・システムに前記元データを提供するステップをさらに含む、
請求項１又は請求項２に記載の方法。
【請求項４】
前記畳み込み符号化された元データを前記データ・ストレージ媒体に保存するステップをさらに含む、請求項３に記載の方法。
【請求項５】
前記元データは（Ｎ）ビットを含み、前記畳み込み符号化された元データは（２）（Ｎ）ビットを含む、請求項１から請求項４のいずれか１項に記載の方法。
【請求項６】
切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、第２の切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定するステップと、
第２の切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、前記ＸＯＲデータ・ストリームから前記複数の先行ゼロを削除することによって、第１の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項１から請求項５のいずれか１項に記載の方法。
【請求項７】
第２の切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、前記第１の切り捨てＸＯＲデータ・ストリームから（ｍ）個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第２の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項６に記載の方法。
【請求項８】
（ｍ）段を含む畳み込みエンコーダと、畳み込み符号化されたデータを生成するためのコンピュータ可読プログラム・コードが配置されたコンピュータ可読媒体とを含む製品であって、前記（ｍ）は１以上であり、前記コンピュータ可読プログラム・コードは、
元データを受け取ることと、
畳み込み符号化された元データを生成することと、
改訂データを受け取ることであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含むことと、
前記元データと前記改訂データとの排他的論理和演算を行うことによって、ＸＯＲデータ・ストリームを生成することであって、前記ＸＯＲデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含むことと、
切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定することと、
切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、
前記畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成することと、
前記畳み込み符号化されたＸＯＲデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップを含む、
製品。
【請求項９】
前記畳み込みエンコーダは３段を含む、請求項８に記載の製品。
【請求項１０】
前記製品は、データ・ストレージ媒体を含むデータ・ストレージ・システム内に配置され、前記コンピュータ可読プログラム・コードは、前記畳み込み符号化された元データを前記データ・ストレージ媒体に格納することを実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項８に記載の製品。
【請求項１１】
前記元データは（Ｎ）ビットを含み、前記畳み込み符号化された元データは（２）（Ｎ）ビットを含み、前記（Ｎ）は１以上である、請求項８に記載の製品。
【請求項１２】
前記コンピュータ可読プログラム・コードは、
切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、第２の切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定することと、
第２の切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、前記ＸＯＲデータ・ストリームから前記複数の先行ゼロを削除することによって、第１の切り捨てＸＯＲデータ・ストリームを形成することと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを形成することと、
前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けすることと、
前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項８に記載の製品。
【請求項１３】
前記コンピュータ可読プログラム・コードは、
第２の切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、前記第１の切り捨てＸＯＲデータ・ストリームから（ｍ）個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第２の切り捨てＸＯＲデータ・ストリームを形成することと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを形成することと、
前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けすることと、
前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うことと
を実行するための一連のコンピュータ可読プログラム・ステップをさらに含む、請求項１２に記載の製品。
【請求項１４】
プロセッサと、畳み込みエンコーダと、データ・ストレージ媒体とを含むデータ・ストレージ・システムに配置されたコンピュータ可読媒体内で符号化されたコンピュータ・プログラムであって、前記コンピュータ・プログラムは、畳み込み符号化されたデータを生成するために、前記プロセッサと共に用いることが可能であり、
前記プログラム可能なコンピュータ・プロセッサに元データを受け取らせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに畳み込み符号化された元データを生成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに改訂データを受け取らせるコンピュータ可読プログラム・コードであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに前記元データと前記改訂データとの排他的論理和演算を行わせることによって、ＸＯＲデータ・ストリームを生成させるコンピュータ可読プログラム・コードであって、前記ＸＯＲデータ・ストリームは複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定させる、コンピュータ可読プログラム・コードと、
切り捨てＸＯＲデータ・ストリームを用いない場合に、前記プログラム可能なコンピュータ・プロセッサに、
前記畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成させ、
前記畳み込み符号化されたＸＯＲデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行わせる、コンピュータ可読プログラム・コードと
を含む、コンピュータ・プログラム。
【請求項１５】
前記畳み込みエンコーダは３段を含む、請求項１４に記載のコンピュータ・プログラム。
【請求項１６】
前記プログラム可能なコンピュータ・プロセッサに前記畳み込み符号化された元データを前記ストレージ媒体に格納させる、コンピュータ可読プログラム・コードをさらに含む、請求項１４又は請求項１５に記載のコンピュータ・プログラム。
【請求項１７】
前記元データは（Ｎ）ビットを含み、前記畳み込み符号化された元データは（２）（Ｎ）ビットを含み、前記（Ｎ）は１以上である、請求項１４から請求項１６のいずれか１項に記載のコンピュータ・プログラム。
【請求項１８】
切り捨てＸＯＲデータ・ストリームが用いられる場合に、前記プログラム可能なコンピュータ・プロセッサに、第２の切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定させる、コンピュータ可読プログラム・コードと、
第２の切り捨てＸＯＲデータ・ストリームを用いない場合に、前記プログラム可能なコンピュータ・プロセッサに、前記ＸＯＲデータ・ストリームから前記複数の先行ゼロを削除することによって、第１の切り捨てＸＯＲデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込みエンコーダを用いて、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けさせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行わせる、コンピュータ可読プログラム・コードと、
をさらに含む、請求項１４から請求項１７のいずれか１項に記載のコンピュータ・プログラム。
【請求項１９】
第２の切り捨てＸＯＲデータ・ストリームが用いられる場合に、前記プログラム可能なコンピュータ・プロセッサに、前記第１の切り捨てＸＯＲデータ・ストリームから（ｍ）個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第２の切り捨てＸＯＲデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込みエンコーダを用いて、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを形成させる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けさせる、コンピュータ可読プログラム・コードと、
前記プログラム可能なコンピュータ・プロセッサに、前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和を行わせる、コンピュータ可読プログラム・コードと
をさらに含む、請求項１８に記載のコンピュータ・プログラム。
【請求項２０】
データ・ストレージ・サービス・プロバイダによって、データ・ストレージ・サービス顧客にデータ・ストレージ・サービスを提供する方法であって、
（ｍ）段を含む畳み込みエンコーダを供給するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記データ・ストレージ・サービスから元の顧客データを受け取るステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された元の顧客データを生成するステップと
を含む方法。
【請求項２１】
前記畳み込みエンコーダを供給するステップは、前記データ・ストレージ・サービス顧客によって、３段を含む畳み込みエンコーダを供給することをさらに含み、
前記データ・ストレージ・サービス顧客は、前記生成するステップを実施する、
請求項２０に記載の方法。
【請求項２２】
前記データ・ストレージ・サービス顧客によって改訂データを受け取るステップであって、前記改訂された顧客データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、ステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記元の顧客データと前記改訂された顧客データとの排他的論理和演算を行うことにより、ＸＯＲデータ・ストリームを生成するステップであって、前記ＸＯＲデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、ステップと、
前記データ・ストレージ・サービス・プロバイダによって、切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定するステップと、
切り捨てＸＯＲデータ・ストリームを用いない場合に有効となるステップであって、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化されたＸＯＲデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項２０に記載の方法。
【請求項２３】
切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、第２の切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定するステップと、
第２の切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、前記ＸＯＲデータ・ストリームから前記複数の先行ゼロを削除することによって、第１の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを形成することと、
前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項２２に記載の方法。
【請求項２４】
第２の切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、前記第１の切り捨てＸＯＲデータ・ストリームから（ｍ）個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第２の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項２３に記載の方法。
【請求項２５】
ストレージ・コントローラであって、
（ｍ）段を含む畳み込みエンコーダを含み、前記（ｍ）は１以上であり、
前記畳み込みエンコーダは、（Ｎ）ビットを含むデータを入力し、（２）（Ｎ）ビットを含む畳み込み符号化されたデータを生成し、前記（Ｎ）は１以上である、
ストレージ・コントローラ。
【請求項２６】
デコーダをさらに含み、
前記デコーダは、前記畳み込み符号化されたデータを入力し、前記（Ｎ）ビットを含むデータを生成する、請求項２５に記載のストレージ・コントローラ。
【請求項２７】
前記デコーダは、ＰＲＭＬトレリスを含む、請求項２６に記載のストレージ・コントローラ。
【請求項２８】
ストレージ・コントローラを含むデータ・ストレージ・システムであって、前記ストレージ・コントローラは、
（ｍ）段を含む畳み込みエンコーダを含み、前記（ｍ）は１以上であり、
前記畳み込みエンコーダは、（Ｎ）ビットを含むデータを入力し、（２）（Ｎ）ビットを含む畳み込み符号化されたデータを生成し、前記（Ｎ）は１以上である、
データ・ストレージ・システム。
【請求項２９】
前記ストレージ・コントローラは、
デコーダをさらに含み、
前記デコーダは、前記畳み込み符号化されたデータを入力し、前記（Ｎ）ビットを含むデータを生成する、請求項２８に記載のデータ・ストレージ・システム。
【請求項３０】
前記デコーダは、ＰＲＭＬトレリスを備える、請求項２９に記載のデータ・ストレージ・システム。
【請求項３１】
プログラム・コード手段を含むコンピュータ・プログラムであって、前記プログラム・コード手段は、前記プログラムがコンピュータ上で実行されるときに、請求項１から請求項７の全てのステップを実行するように適合されている、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、畳み込み符号化されたデータを生成するシステム、プログラム、及び方法に関する。
【背景技術】
【０００２】
データ・ストレージ・システムは、１つ又は複数のホスト・コンピュータ・システムによって提供された情報を格納するために用いられる。データ・ストレージ・システムは、ときとして、１つ又は複数のホスト・コンピュータ・システムによって提供された情報を、１つ又は複数の符号化プロトコルを用いて保存する。さらに、データ・ストレージ・システムは、ときとして、１つ又は複数のホスト・コンピュータ・システムから改訂されたデータを受け取る。データ・ストレージ・システムは、このような改訂された情報を１つ又は複数の符号化プロトコルを用いて保存する。
【発明の概要】
【０００３】
畳み込み符号化されたデータを生成する装置及び方法が提供される。本方法は、畳み込みエンコーダを供給する。本方法は、さらに、元データを受け取り、畳み込み符号化された元データを生成する。本方法は、改訂データを受け取る。本方法は、元データと改訂データとの排他的論理和演算を行うことによってＸＯＲデータ・ストリームを生成し、畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成し、畳み込み符号化されたＸＯＲデータ・ストリームと畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。
【０００４】
これより本発明の実施形態が、例示のみの目的で、添付の図面を参照して説明される。
【図面の簡単な説明】
【０００５】
【図１】データ・ストレージ・システムの１つの実施形態を示すブロック図である。
【図２】畳み込みエンコーダ回路の１つの実施形態を示す。
【図３】１ビットのバイナリ・データを２ビットの符号化データに符号化することができる畳み込み符号化アルゴリズムを表す表である。
【図４】１ビットのバイナリ・データを２ビットの符号化データに符号化することができる畳み込み符号化アルゴリズムを表す状態図を含む。
【図５】２ビットの符号化データを１ビットのバイナリ・データに復号するために用いられるＰＲＭＬトレリスを示す。
【図６】本発明の１つの実施形態による方法を示すために用いられる元データを示す。
【図７】本発明の１つの実施形態による方法を示すために用いられる改訂データを示す。
【図８】図６の元データが図２の畳み込みエンコーダ回路を用いて畳み込み符号化された後の元データを示す。
【図９】図６の元データと図７の改訂データとの排他的論理和演算を行うことによって形成されるＸＯＲデータ・ストリームを示す。
【図１０】図９のＸＯＲデータ・ストリームを図２の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化されたＸＯＲデータ・ストリームを示す。
【図１１】図８の畳み込み符号化された元データと図１０の畳み込み符号化されたＸＯＲデータ・ストリームとの排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図１２】図９のＸＯＲデータ・ストリームから先行ゼロ部分を削除することによって形成される第１の切り捨て（truncated）ＸＯＲデータ・ストリームを示す。
【図１３】図１２の第１の切り捨てＸＯＲデータ・ストリームを図２の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを示す。
【図１４】図８の畳み込み符号化された元データに索引付けされた、図１３の畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを示す。
【図１５】図８の畳み込み符号化された元データと図１４の索引付けされた畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームとの排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図１６】図１２の第１の切り捨てＸＯＲデータ・ストリームから後続ゼロ部分を削除することによって形成される、第２の切り捨てＸＯＲデータ・ストリームを示す。
【図１７】図１６の第２の切り捨てＸＯＲデータ・ストリームを図２の畳み込みエンコーダ回路を用いて畳み込み符号化することによって形成される、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを示す。
【図１８】図８の畳み込み符号化された元データに索引付けされた、図１７の畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを示す。
【図１９】図８の畳み込み符号化された元データと図１８の索引付けされた畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームとの間で排他的論理和演算を行って、畳み込み符号化された改訂データを生成するところを示す。
【図２０】本方法の第１の実施形態のステップをまとめたフロー・チャートである。
【図２１】本方法の第２の実施形態及び第３の実施形態を含む付加的なステップをまとめたフロー・チャートである。
【発明を実施するための形態】
【０００６】
本発明は、以下の説明において添付の図面を参照して好ましい実施形態で説明され、図中、同様の符号は同一又は類似の要素を表す。本明細書の全体を通じて、「１つの実施形態(one embodiment)」、「一実施形態(a embodiment)」、又は同様の言葉への言及は、その実施形態との関連で説明された特定の特徴、構造、又は特性が、本発明の少なくとも１つの実施形態に含まれることを意味する。よって、本明細書の全体を通じて、「１つの実施形態において」、「一実施形態において」という語句、及び同様の言葉の出現は、全てが同じ実施形態のことを指すこともあるが、必ずしもそうであるとは限らない。
【０００７】
説明される本発明の特徴、構造、及び特性は、１つ又は複数の実施形態において、いずれかの適切な手法で組み合わせることができる。以下の説明において、本発明の実施形態の完全な理解を与えるために、多数の具体的な詳細が列挙される。しかしながら、当業者であれば、本発明は１つ又は複数の具体的な詳細がなくても実施することができること、又は他の方法、構成要素、材料などを用いて実施することができることを認識する。他の例では、本発明の態様を不明瞭にすることを避けるため、周知の構造、材料、又は操作は図示されず、又は詳細に説明されない。
【０００８】
図１は、データ・ストレージ・システム１００を示す。図１の図示された実施形態において、システム１００は、１つ又は複数のスイッチ１２５を用いてスイッチング・ファブリック１２０が形成された、スイッチド・アクセス・ネットワークを含む。特定の実施形態において、データ・ストレージ・システム１００は、ファイバチャネル（「ＦＣ：Fibre Channel」）物理層上で動作する、小型コンピュータシステム・インターフェース（ＳＣＳＩ：Small Computer System Interface）プロトコルを用いて実装される。他の実施形態において、データ・ストレージ・システム１００は、インフィニバンド（Infiniband）、ＦＩＣＯＮ（Fibre Channel CONrctivity:ファイバチャネル接続の特殊形態）、ＴＣＰ／ＩＰ、イーサネット、ギガビット・イーサネット、又はｉＳＣＳＩなどのその他のプロトコルを用いて実装することができる。スイッチ１２５は、ホスト１０１、１０３、１０５、１０７、１０９及びコントローラ１３１の両者のアドレスを有するので、ホスト１０１、１０３、１０７及び／又は１０９はどれでも、いずれのコントローラ１３１にも互換的に接続することができるようになっている。
【０００９】
ホスト・コンピュータ１０１、１０３、１０５、１０７及び１０９は各々、Ｗｉｎｄｏｗｓ、ＡＩＸ、Ｕｎｉｘ、ＭＶＳ、ＬＩＮＵＸなどのオペレーティング・システムを含む、メインフレーム、パーソナル・コンピュータ、ワークステーション及びそれらの組み合のようなコンピュータ・システムを含む（ＷｉｎｄｏｗｓはＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎの登録商標であり、ＡＩＸはＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの登録商標であり、ＭＶＳはＩＢＭ  Ｃｏｒｐｏｒａｔｉｏｎの商標である、ＵＮＩＸは米国及びその他の国々においてＴｈｅ  Ｏｐｅｎ  Ｇｒｏｕｐを通じて独占的にライセンスされる登録商標であり、ＬＩＮＵＸはLinus Torvaldの登録商標である）。特定の実施形態において、ホスト・コンピュータ１０１、１０３、１０５、１０７及び１０９は、ストレージ管理プログラムをさらに含む。ホスト・コンピュータ１０１、１０３、１０５、１０７及び１０９内のストレージ管理プログラムは、データ・ストレージと検索システムとの間でやりとりされるデータ転送を管理する、ＩＢＭ  ＭＶＳオペレーティング・システムに実装されたＩＢＭ  ＤＦＳＭＳのような当該分野において公知のストレージ管理型プログラムの機能を含むことができる。
【００１０】
ホスト・コンピュータ１０１、１０３、１０５、１０７及び１０９は、それぞれ、Ｉ／Ｏインターフェース１１１、１１３、１１５、１１７及び１１９を用いてファブリック１２０に接続される。Ｉ／Ｏインターフェース１１１、１１３、１１５、１１７及び１１９は、任意のタイプのＩ／Ｏインターフェースとすることができ、例えば、ＦＣアービトレーテッド・ループ、ファブリック１２０へのポイント・ツー・ポイント型ＦＣ接続、又はホスト・コンピュータ１０１、１０３、１０５、１０７及び１０９とファブリック１２０にとの間で情報を直接転送するために用いられる別の形態の１つ又は複数の信号ラインである。ファブリック１２０は、例えば、２つ又はそれ以上のコンピュータ・ネットワークを接続するために用いられる１つ又は複数のＦＣスイッチ１２５を含む。特定の実施形態において、ＦＣスイッチ１２５は、従来型のルータ・スイッチである。１つの代替的な実施形態において、ホスト・コンピュータ１０１、１０３、１０５、１０７及び１０９は、スイッチを用いずにポイント・ツー・ポイント構成でストレージ・コントローラ１３１に接続される。
【００１１】
スイッチ１２５は、Ｉ／Ｏインターフェース１３５越しに、ホスト・コンピュータ１０１、１０３、１０５、１０７及び１０９をコントローラ１３１に相互接続する。Ｉ／Ｏインターフェース１３５は、任意のタイプのＩ／Ｏインターフェースとすることができ、例えば、ファイバチャネル、インフィニバンド、ギガビット・イーサネット、イーサネット、ＴＣＰ／ＩＰ、ｉＳＣＳＩ、ＳＣＳＩ  Ｉ／Ｏインターフェース、又はＦＣスイッチ１２５がコントローラ１３１との間でそれぞれ情報を転送し、その後で複数のデータ・ストレージ媒体１６０、１７０、１８０及び１９０に情報を転送するために用いられる１つ又は複数の信号ラインである。あるいは、１つの災害でデータ・ストレージ媒体１６０、１７０、１８０及び１９０のうちの１つしか損なわれないようにするために、データ・ストレージ媒体１６０、１７０、１８０及び１９０は互いに物理的に遠隔であるとともに、コントローラ１３１とも物理的に遠隔であることができる。「データ・ストレージ媒体」という用語によって、本出願人は、そのデータ・ストレージ媒体からデータを読み出し、かつ、そこにデータを書き込むために必要なハードウェア、ソフトウェア及び／又はファームウェアと組み合わされた、データ・ストレージ媒体のことを意味する。
【００１２】
特定の実施形態において、１つ又は複数のデータ・ストレージ媒体１６０、１７０、１８０及び／又は１９０は、例えば、それらに限定されるものではないが、磁気ディスク、磁気テープなどのような、磁気データ・ストレージ媒体を含む。特定の実施形態において、１つ又は複数のデータ・ストレージ媒体１６０、１７０、１８０及び／又は１９０は、例えば、それらに限定されるものではないが、ＣＤ、ＤＶＤ、ＨＤ−ＤＶＤ、ブルーレイなどのような、光ストレージ媒体を含む。特定の実施形態において、１つ又は複数のデータ・ストレージ媒体１６０、１７０、１８０及び／又は１９０は、例えば、それらに限定されるものでないが、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュＰＲＯＭ、コンパクトフラッシュ、スマートメディアなどのような、電子データ・ストレージ媒体を含む。特定の実施形態において、１つ又は複数のデータ・ストレージ媒体１６０、１７０、１８０及び／又は１９０は、ホログラフィ・データ・ストレージ媒体を含む。
【００１３】
ストレージ・アレイ１３０は、コントローラ１３１と、ストレージ媒体１６０、１７０、１８０及び１９０とを含む。コントローラ１３１とストレージ媒体１６０、１７０、１８０及び１９０とは、共通のフレーム又はボックスの中に一緒に配置されてもよい。あるいは、コントローラ１３１とストレージ媒体１６０、１７０、１８０及び１９０とは、災害からの復旧を理由として、ときとしてジオプレックスともよばれる形態で地理的に離間させてもよい。ストレージ媒体１６０、１７０、１８０及び／又は１９０は、ジオプレックス内のストレージへのアクセスを与えるために、連動して作動する分離した別個のコントローラを有することもできる。
【００１４】
コントローラ１３１は多くの異なる形態を取ることができ、埋め込みシステム、分散制御システム、パーソナル・コンピュータ、ワークステーションなどを含むことができる。図１の図示された実施形態において、ストレージ・コントローラ１３１は、プロセッサ１４０、メタデータ・コントローラ１４８、ランダム・アクセス・メモリ（ＲＡＭ）１５４、不揮発性メモリ１５０、特定回路１４２、符号化データ・インターフェース１５８及びホスト情報インターフェース１３２を含む。ホスト情報インターフェース１３２は情報１３４を保持し、この情報１３４は、ストレージ媒体１６０、１７０、１８０、１９０への書き込み動作中にエンコーダ１４６により符号化されるもの、又はストレージ媒体１６０、１７０、１８０、１９０からの読み出し動作中にデコーダ１４４によって読み取られ、復号されたもののいずれかである。特定の実施形態において、ＲＡＭ１５４は、データ・キャッシュとして用いられる。プロセッサ１４０、ＲＡＭ１５４、不揮発性メモリ１５０、特定回路１４２、メタデータ・コントローラ１４８、符号化データ・インターフェース１５８及びホスト情報インターフェース１３２は、バス１４５を介して互いに通信する。
【００１５】
あるいは、ＲＡＭ１５４及び／又は不揮発性メモリ１５０は、特定回路１４２、符号化データ・インターフェース１５８、メタデータ・コントローラ１４８及びホスト情報インターフェース１３２と共に、プロセッサ１４０内にあってもよい。プロセッサ１４０は、既製のマイクロプロセッサ、カスタム・プロセッサ、ＦＰＧＡ、ＡＳＩＣ、又は他の形態のディスクリート・ロジックを含むことができる。特定の実施形態において、ＲＡＭ１５４は、ホスト１０１、１０３、１０５、１０７及び／又は１０９によって書き込まれたデータ、又はホスト１０１、１０３、１０５、１０７及び／又は１０９のために読み出されたデータのためのキャッシュとして用いられ、計算されたデータ、スタック・データ、実行可能命令などを保持する。特定の実施形態において、ＲＡＭ１５４は、畳み込み符号化されたデータをデータ・ストレージ媒体１６０、１７０、１８０及び１９０上に格納する前に、エンコーダ１４６から受け取った畳み込み符号化されたデータ１５６を一時的に格納するために用いられる。
【００１６】
不揮発性メモリ１５０は、電気的消去可能プログラマブル消去可能読出し専用メモリ（ＥＥＰＲＯＭ：Electrically Erasable Programmable Read Only Memory）、フラッシュ・プログラマブル読出し専用メモリ（ＰＲＯＭ：Programmable Read Only Memory）、バッテリ・バックアップＲＡＭ、ハード・ディスク・ドライブ又は他の同様のデバイスなどのような、任意のタイプの不揮発性メモリを含むことができる。不揮発性メモリ１５０は、典型的には、実行可能なファームウェア及び任意の不揮発性データ、例えばメタデータ１５２を保持するために用いられる。
【００１７】
特定の実施形態において、符号化データ・インターフェース１５８は、プロセッサ１４０がデータ・ストレージ媒体１６０、１７０、１８０及び１９０と通信することを可能にする１つ又は複数の通信インターフェースを含む。ホスト情報インターフェース１３２は、プロセッサ１４０がファブリック１２０、スイッチ１２５、並びにホスト１０１、１０３、１０５、１０７及び／又は１０９と通信することを可能にする。符号化データ・インターフェース１５８及びホスト情報インターフェース１３２の例は、ＲＳ−２３２、ＵＳＢ（Universal Serial Bus（ユニバーサル・シリアルバス））、ＳＣＳＩ（SmallComputer Systems Interface（小型コンピュータシステム・インターフェース））、ファイバチャネル、ギガビット・イーサネットなどのような、シリアル・インターフェースを含む。さらに、符号化データ・インターフェース１５８及び／又はホスト情報インターフェース１３２は、無線周波数などの無線インターフェース、例えば、それに限定されるものではないがＢｌｕｅｔｏｏｔｈ、又は光通信デバイス、例えば、それに限定されるものではないが赤外周波数を用いるデバイスを含むことができる。
【００１８】
特定の実施形態において、メタデータ・コントローラ１４８は、プロセッサ１４０内で、ソフトウェア、ファームウェア、専用ロジック又はその組み合わせによって実装される。さらに、メタデータ・コントローラ１４８の全て又は一部は、例えば、ホスト１０１、１０３、１０５、１０７及び／又は１０９のうちの１つに実装されたソフトウェアの形で、コントローラ１３１の外部に常駐してもよい。メタデータ・コントローラ１４８は、畳み込み符号化されたデータとしてストレージ・デバイスに格納するために受け取った情報に関連するメタデータを管理する。特定の実施形態において、メタデータ・コントローラ１４８は、畳み込み符号化されたデータとして格納するために受け取った情報に関連するメタデータを生成し、変更し、維持し、格納し、検索し、処理することを担当する。
【００１９】
特定の実施形態において、ディストリビュータ１３６は、プロセッサ１４０内で、ソフトウェア、ファームウェア、専用ロジック又はその組み合わせによって実装される。さらに、ディストリビュータ１３６の全て又は一部は、ホスト１０１、１０３、１０５、１０７及び／又は１０９のうちの１つに実装されたソフトウェアの形で、コントローラ１３１の外部に常駐してもよい。ディストリビュータ１３６は、畳み込み符号化されたデータをＲＡＭに、及び／又は直接ストレージ媒体１６０、１７０、１８０及び／又は１９０に分散させる。ディストリビュータ１３６が畳み込み符号化されたデータを媒体１６０、１７０、１８０及び１９０のような複数のデータ・ストレージ媒体に分散させる場合、分散はメタデータ１５２に従って行われるので、分散された畳み込み符号化されたデータを後でストレージ・デバイスから読み出して、元のデータ又は改訂データに復号することができる。
【００２０】
特定回路１４２は、コントローラ１３１が、データ・ストレージ媒体１６０、１７０、１８０及び１９０、コントローラ１３１、並びにエンコーダ１４６の環境冷却のためのファン制御のような独自の機能を実行することを可能にする付加的なハードウェアを提供する。エンコーダ１４６は、例えば、それに限定されないが畳み込みエンコーダ回路２００（図２）のような、畳み込みエンコーダとして実装されることができる。特定回路１４２は、パルス幅変調（ＰＷＭ）制御、アナログ−デジタル変換（ＡＤＣ）、デジタル−アナログ変換（ＤＡＣ）、排他的論理和演算（「ＸＯＲ」）などを提供する電子機器を含むことができる。さらに、特定回路１４２の全て又は一部は、ホスト１０１、１０３、１０５、１０７及び／又は１０９のうちの１つに実装されたソフトウェア実装などの形で、コントローラ１３１の外部に常駐してもよい。
【００２１】
特定の実施形態において、エンコーダ１４６は、１データ・ビットを２データ・ビットの組に符号化する畳み込みエンコーダを含む。特定の実施形態において、エンコーダ１４６は、表３００（図３）及び状態図４００（図４）で表される畳み込み符号化アルゴリズムを含む。特定の実施形態において、デコーダ１４４は、ＰＲＭＬトレリス５００（図５）を含む。デコーダ１４４は、スタック図を構成することもできる。
【００２２】
特定の実施形態において、既存ファイルに対して、「原子（atomic)」更新と呼ばれることもある小さい書き込み更新が実行される。特定の実施形態において、その既存ファイルは、以前に畳み込み符号化されたデータを含む。本方法は、データ・セット全体を再度畳み込み符号化することなく、以前に畳み込み符号化されたデータのビットのうちの比較的小さい部分を、既に畳み込み符号化されたデータ・セット内の他の畳み込み符号化されたデータのビットに変更する。本方法は、ＲＡＩＤ３、４、又は５で用いられているような行パリティはどこにも使用しない。本方法は、ＲＡＩＤ−６で用いられているような対角線パリティをどこにも使用しない。
【００２３】
本発明に従って本方法を用いると、増分更新は、元データの変更された部分の排他的論理和（「ＸＯＲ」）を（ｍ）個の後続ゼロと組み合わせたものを含み、（ｍ）は、畳み込みエンコーダ回路２００（図２）の線形シフト・アレイの中のメモリ・ステップの数である。増分更新を畳み込み符号化し、次いで、元の畳み込み符号化されたデータとの間で排他的論理和演算を行い、更新を完了する。
【００２４】
ここで図２０を参照すると、ステップ１０１０において、本方法は、（ｍ）個のレジスタ、即ち（ｍ）レベルの遅延を含む畳み込みエンコーダを供給する。特定の実施形態において、ステップ１０１０の畳み込みエンコーダは、データ・ストレージ・システム１００（図１）のようなデータ・ストレージ・システム内に配置される。特定の実施形態において、ステップ１０１０の畳み込みエンコーダは、ストレージ・アレイ１３０（図１）のようなストレージ・アレイ内に配置される。特定の実施形態において、ステップ１０１０の畳み込みエンコーダは、ストレージ・コントローラ１３１のようなストレージ・コントローラ内に配置される。特定の実施形態において、畳み込みエンコーダは、ストレージ・コントローラ１３１のようなストレージ・コントローラ内に配置されたエンコーダ１４６（図１）のような、エンコーダ内に配置される。
【００２５】
特定の実施形態において、ステップ１０１０の畳み込みエンコーダは、エンコーダ回路２００（図２）を含む。特定の実施形態において、ステップ１０１０の畳み込みエンコーダは、表３００（図３）及び状態図４００（図４）に示される符号化アルゴリズムを実行する。
【００２６】
ここで図２を参照すると、畳み込みエンコーダ回路２００は、符号化のために、入力情報ストリームＵ（Ｊ−３）２０５を一度に１ビットずつ受け取る。エンコーダ回路２００は、レジスタ２１０、２２０及び２３０を含む３段シフト・レジスタを含む。レジスタ２１０、２２０及び２３０の初期内容は、符号化プロセスのためには、好ましくはゼロである。入力情報ストリームＵ（Ｊ−３）２０５と、レジスタ２１０、２２０及び２３０の出力とが加算器２４０によって選択的に加算されて出力Ｖ（Ｊ，１）２４５を生成し、加算器２５０によって選択的に加算されて出力Ｖ（Ｊ，２）２５５を生成する。特定の実施形態において、モジュロ−２加算器２４０及び２５０は、特定回路１４２内にＸＯＲ（排他的論理和）ゲートとして実装される。他の実施形態において、加算器２４０及び２５０は、ソフトウェア、ファームウェア、専用ロジックなどの使用により実装される。
【００２７】
ここで図３及び図４を参照すると、特定の実施形態において、ステップ１０１０の畳み込みエンコーダは、表３００及び状態図４００で表される符号化アルゴリズムを用いる。装置及び方法についてのこの記述は、この装置及び方法が、畳み込みエンコーダ回路２００、表３００及び状態図４００で表される畳み込み符号化アルゴリズムのみを使用すると限定するものと解釈されるべきではない。むしろ、他の実施形態において、本方法は異なる畳み込み符号化アルゴリズムを利用する。
【００２８】
図３及び図４の符号化アルゴリズムは、Ｓ０４１０、Ｓ１４１１、Ｓ２４１２、Ｓ３４１３、Ｓ４４１４、Ｓ５４１５、Ｓ６４１６及びＳ７４１７の８つの状態を含む。状態間の各々の遷移の結果、ホスト１０１、１０３、１０５、１０７及び／又は１０９から受け取った１ビットの元データが符号化されて、図２、図３及び図４に示されるように、２ビットの符号化データになり、それらは、特定の実施形態において、次にストレージ媒体１６０、１７０、１８０及び１９０内に格納される。
【００２９】
表３００（図３）は、初期状態３１０、宛先状態３２０、元データ３３０、及び畳み込み符号化データ３４０の４つの列を含む。表３００には、８つの状態Ｓ０、Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５、Ｓ６、及びＳ７、並びに各初期状態からの２つの可能な遷移の総計に基づいて、全部で１６個の行が存在する。表３００は、状態図４００によって生成されたものであり、ここでは、元データを符号化して符号化データを生成することを説明するために用いられる。再び図２０を参照すると、ステップ１０２０において、本方法は、元データ６００（図６）のような、元データを提供する。特定の実施形態において、ステップ１０２０の元データは、これらに限定されるものではないが、ホスト・コンピュータ１０１（図１）、１０３（図１）、１０５（図１）、１０７（図１）及び／又は１０９（図１）のような１つ又は複数のホスト・コンピュータによって提供される。ステップ１０２０は、元データを受け取ることをさらに含む。特定の実施形態において、ステップ１０２０の元データは、ストレージ・アレイ１３０（図１）のようなストレージ・アレイによって受け取られる。特定の実施形態において、ステップ１０２０の元データは、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって受け取られる。
【００３０】
ステップ１０３０において、本方法は、ステップ１０１０の畳み込みエンコーダを用いて畳み込み符号化された元データを生成する。一例として、ここで図２、図６及び図８を参照すると、ステップ１０３０において、本方法は、畳み込みエンコーダ回路２００と元データ６００とを用いて、畳み込み符号化された元データ６２０を生成する。特定の実施形態において、ステップ１０３０は、ステップ１０２０の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１０３０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１０３０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。特定の実施形態において、ステップ１０３０は、エンコーダ１４６（図１）によって行われる。
【００３１】
再び図２０を参照すると、ステップ１０４０において、本方法は、ステップ１０３０の畳み込み符号化された元データを保存する。特定の実施形態において、ステップ１０３０の畳み込み符号化された元データは、データ・ストレージ媒体１６０（図１）、１７０（図１）、１８０（図１）及び／又は１９０（図１）のうちの１つ又は複数に保存される。特定の実施形態において、ステップ１０４０は、ステップ１０２０の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１０４０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１０４０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００３２】
ステップ１０５０において、本方法は、改訂データ６１０（図７）のような、改訂されたデータを提供する。改訂データ６１０は、元データ６００（図６）内のそれぞれのビットとは異なる、変更されたビット６１５を有する。特定の実施形態において、ステップ１０５０の改訂データは、これらに限定されるものではないが、ホスト・コンピュータ１０１（図１）、１０３（図１）、１０５（図１）、１０７（図１）及び／又は１０９（図１）のような１つ又は複数のホスト・コンピュータによって提供される。ステップ１０５０は、改訂データを受け取ることをさらに含む。特定の実施形態において、ステップ１０５０の改訂データは、ストレージ・アレイ１３０（図１）のようなストレージ・アレイによって受け取られる。特定の実施形態において、ステップ１０５０の改訂データは、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって受け取られる。
【００３３】
ステップ１０６０において、本方法は、ステップ１０２０の元データとステップ１０５０の改訂データとの排他的論理和演算を行うことによって、ＸＯＲデータ・ストリームを生成する。
【００３４】
当業者であれば、「排他的論理和演算を行う（Exclusive OR'ing）」ことによって、元データが改訂データとの間で１ビットごとに排他的論理和されることを認識する。排他的論理和演算は、元データと改訂データの対応するビット位置間でのみ行われ、すなわち、ビット０は、ビット０との間でのみ排他的論理和され、ビット１は、ビット１との間でのみ排他的論理和され、以下同様である。表１は、４つの可能な排他的論理和の結果を挙げる。
【表１】
2010536214.tif 000003
【００３５】
ここで図６、図７及び図９を参照すると、ステップ１０６０において、元データ６００と改訂データ６１０との排他的論理和演算を行うことにより、ＸＯＲデータ・ストリーム７００が生成される。ＸＯＲデータ・ストリーム７００は、元データ６００と改訂データ６１０との間の対応する同一のビットの排他的論理和によって生成された複数の先行「ゼロ」を含む、部分７０２を含む。ＸＯＲデータ・ストリーム７００は、元データ６００の対応するビットと改訂データ６１０の中の変更されたビット６１５との間の排他的論理和によって生成された複数の「１」を含む、部分７０４をさらに含む。ＸＯＲデータ・ストリーム７００は、元データ６００と改訂データ６１０との間の対応する同一のビットの排他的論理和によって生成された複数の後続「ゼロ」を含む、部分７０６をさらに含む。
【００３６】
再び図２０を参照すると、ステップ１０７０において、本方法は、１つ又は複数の切り捨て（truncated）ＸＯＲデータ・ストリームを生成して用いるかどうかを決定する。特定の実施形態において、ステップ１０７０は、ステップ１０２０の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１０７０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１０７０は、ストレージ・コントローラ内に配置された、プロセッサ１４０（図１）のようなプロセッサによって行われる。
【００３７】
方法が、１つ又は複数の切り捨てＸＯＲデータ・ストリームを生成せず用いないことを選択した場合には、方法は、ステップ１０７０からステップ１０８０に移り、ここで、方法は、ＸＯＲデータ・ストリーム７００のようなステップ１０６０のＸＯＲデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ１０８０は、ステップ１０２０の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１０８０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１０８０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００３８】
一例として、ここで図２、図９及び図１０を参照すると、ＸＯＲデータ・ストリーム７００と畳み込みエンコーダ回路２００とを用いて、畳み込み符号化されたＸＯＲデータ・ストリーム７１０が生成される。畳み込み符号化されたＸＯＲデータ・ストリーム７１０は、エンコーダ回路２００を用いて部分７０２を畳み込み符号化することによって生成された部分７１２を含む。複数の先行「０」を畳み込み符号化する場合、エンコーダ回路２００は各「０」を「００」に符号化し、これはＳ０からＳ０への遷移の繰り返しを表す。
【００３９】
畳み込み符号化されたＸＯＲデータ・ストリーム７１０は、部分７０４を（ｍ）個の後続ゼロと組み合わせて畳み込み符号化することによって生成された部分７１４をさらに含み、ここで、畳み込みエンコーダ回路２００の場合、（ｍ）は３の値を有する。エンコーダ回路２００は３つのレジスタ、即ち、レジスタ２１０、２２０及び２３０を含む。その結果、畳み込みエンコーダ回路２００は、エンコーダが状態Ｓ０に戻る前に、最初の３つの後続ゼロを符号化する。その後、後続「０」の各々は、Ｓ０からＳ０への遷移の繰り返しを表す「００」に符号化される。畳み込み符号化されたＸＯＲデータ・ストリーム７１０は、部分７０６の残りの後続ゼロを畳み込みエンコーダ回路２００を用いて畳み込み符号化することによって生成された、部分７１６をさらに含む。
【００４０】
再び図２０を参照すると、ステップ１０９０において、本方法は、ステップ１０８０の畳み込み符号化されたＸＯＲデータ・ストリームとステップ１０３０の畳み込み符号化された元データとの排他的論理和演算を行う。特定の実施形態において、ステップ１０９０は、ステップ１０２０の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１０９０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１０９０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００４１】
一例として、ここで図１１を参照すると、ステップ１０９０において、本方法は、畳み込み符号化された元データ６２０と畳み込み符号化されたＸＯＲデータ・ストリーム７１０との排他的論理和演算を行い、畳み込み符号化された改訂データ７２０を生成する。この実施形態において、本方法は、ステップ１０９０において、畳み込み符号化された元データ６２０の部分６２２と畳み込み符号化されたＸＯＲデータ・ストリーム７１０の先行ゼロ部分７１２との排他的論理和演算を行い、改訂データ７２０の畳み込み符号化された部分７２２を生成する。この実施形態において、本方法は、さらに、畳み込み符号化された元データ６２０の部分６２４と畳み込み符号化されたＸＯＲデータ・ストリーム７１０の変更されたビット／（ｍ）個の後続ゼロ部分７１４との排他的論理和演算を行い、改訂データ７２０の更新された部分７２４を形成する。この実施形態において、方法は、さらに、畳み込み符号化された元データ６２０の部分６２６と畳み込み符号化されたＸＯＲデータ・ストリーム７１０の残りの後続ゼロ部分７１６との排他的論理和演算を行い、改訂データ７２０の畳み込み符号化された部分７２６を形成する。
【００４２】
他の実施形態において、本方法は、第１の切り捨てＸＯＲデータ・ストリームを利用し、この場合、方法は、ＸＯＲデータ・ストリーム７１０から先行ゼロを削除し、次いで、その第１の切り捨てＸＯＲデータ・ストリームを畳み込み符号化し、次いで、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームと元データと排他的論理和演算を行い、改訂データを生成する。さらに他の実施形態において、本方法は、第２の切り捨てＸＯＲデータ・ストリームを利用し、この場合、本方法は、第１の切り捨てＸＯＲデータ・ストリームから（ｍ）個の後続ゼロを除く全ての後続ゼロをさらに削除し、次いで、その第２の切り捨てＸＯＲデータ・ストリームを畳み込み符号化し、次いで、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームと元データとの排他的論理和演算を行い、改訂データを生成する。
【００４３】
再び図２０を参照すると、ステップ１０７０において、本方法が１つ又は複数の切り捨てＸＯＲデータ・ストリームを生成して用いることを選択した場合には、本方法は、ステップ１０７０からステップ１１１０（図２１）に移る。ステップ１１１０において、本方法は、第１の切り捨てＸＯＲデータ・ストリームを生成する。特定の実施形態において、ステップ１１１０は、ステップ１０２０（図２０）の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１１０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１１０は、ストレージ・コントローラ内に配置された、プロセッサ１４０（図１）のようなプロセッサによって行われる。
【００４４】
一例として、ここで図９及び図１２を参照すると、ＸＯＲデータ・ストリーム７００の部分７０２は、（Ｎ）個の先行ゼロを含む。ステップ１１１０において、本方法は、ＸＯＲデータ・ストリーム７００から、部分７０２を構成する（Ｎ）個の先行ゼロを削除することによって、第１の切り捨てＸＯＲデータ・ストリーム８００を生成する。第１の切り捨てＸＯＲデータ・ストリーム８００は、変更されたビット部分８０４を後続ゼロ部分８０６と組み合わせて含む。
【００４５】
再び図２１を参照すると、ステップ１１２０において、本方法は、第２の切り捨てＸＯＲデータ・ストリームを生成して用いるかどうかを決定する。特定の実施形態において、ステップ１１２０は、ステップ１０２０（図２０）の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１２０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１２０は、ストレージ・コントローラ内に配置された、プロセッサ１４０（図１）のようなプロセッサによって行われる。
【００４６】
ステップ１１２０において、本方法が、第２の切り捨てＸＯＲデータ・ストリームを生成せず用いないことを選択した場合には、本方法は、ステップ１１２０からステップ１１３０に移り、ここで、方法は第１の切り捨てＸＯＲデータ・ストリーム８００（図１２）のようなステップ１１１０の第１の切り捨てＸＯＲデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ１１３０は、ステップ１０２０（図２０）の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１３０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１３０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００４７】
一例として、ここで図２、図１２及び図１３を参照すると、第１の切り捨てＸＯＲデータ・ストリーム８００と畳み込みエンコーダ回路２００とを用いて、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリーム８１０が生成される。畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリーム８１０は、部分８０４を（ｍ）個の後続ゼロと組み合わせて畳み込み符号化することによって生成された部分８１４をさらに含み、ここで、畳み込みエンコーダ回路２００の場合、（ｍ）は３の値を有する。エンコーダ回路２００は３つのレジスタ、即ち、レジスタ２１０、２２０及び２３０を含む。その結果、畳み込みエンコーダ回路２００は、エンコーダが状態Ｓ０に戻る前に、最初の３つの後続ゼロを符号化する。その後、後続「０」の各々は、Ｓ０からＳ０への遷移の繰り返しを表す「００」に符号化される。畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリーム８１０は、部分８０６の残りの後続ゼロを畳み込みエンコーダ回路２００を用いて畳み込み符号化することによって生成された、部分８１６をさらに含む。
【００４８】
再び図２１を参照すると、ステップ１１４０において、本方法は、ステップ１１３０の畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを、ステップ１０３０（図２０）の畳み込み符号化された元データに索引付けする。ステップ１１１０において、本方法は、ステップ１０６０（図２０）のＸＯＲデータ・ストリームから、（Ｎ）個の先行ゼロを削除し、第１の切り捨てＸＯＲデータ・ストリームを生成した。ステップ１１４０において、本方法は、ステップ１１３０の畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームの第１ビットを、畳み込み符号化された元データの第［（２）（Ｎ）＋１］番目のビットに位置合わせする。
【００４９】
特定の実施形態において、ステップ１１４０は、ステップ１０２０（図２０）の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１４０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１４０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００５０】
一例として、ここで図９、図１２及び図１４を参照すると、ＸＯＲデータ・ストリーム７００は（Ｎ）個の先行ゼロを含み、ここで（Ｎ）は１３である。これらの１３個の先行ゼロは、第１の切り捨てＸＯＲデータ・ストリーム８００を生成するために削除された。ステップ１１４０において、本方法は、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリーム８１０の第１ビットを、畳み込み符号化された元データ６２０の第２７番目のビット［（２）（１３）＋１］に位置合わせする。
【００５１】
再び図２１を参照すると、本方法は、ステップ１１５０において、索引付けされたステップ１１３０の畳み込み符号化されたＸＯＲデータ・ストリームとステップ１０３０の畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。特定の実施形態において、ステップ１１５０は、ステップ１０２０の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１５０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１５０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００５２】
一例として、図１５を参照すると、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリーム８１０は、畳み込み符号化された元データ６２０の部分６２２に対応する部分を含まない。従って、ステップ１１５０において、本方法は、畳み込み符号化された改訂データ７２０の第１の部分７２２として、部分６２２をコピーする。ステップ１１５０において、さらに、本方法は、畳み込み符号化された元データ６２０の部分６２４と畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリーム８１０の部分８１４との排他的論理和演算を行って、畳み込み符号化された改訂データ７２０の畳み込み符号化された部分７２４を生成し、畳み込み符号化された元データ６２０の部分６２６と畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリーム８１０の部分８１６との排他的論理和演算を行って、畳み込み符号化された改訂データ７２０の第３の部分７２６を生成し、畳み込み符号化された改訂データ７２０の生成を完了する。
【００５３】
再び図２１を参照すると、ステップ１１２０において、本方法が、第２の切り捨てＸＯＲデータ・ストリームを生成して用いることを選択した場合には、本方法は、ステップ１１２０からステップ１１６０に移り、ここで、本方法は第２の切り捨てＸＯＲデータ・ストリームを生成する。特定の実施形態において、ステップ１１６０は、ステップ１０２０の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１６０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１６０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００５４】
一例として、ここで図１２及び図１６を参照すると、第１の切り捨てＸＯＲデータ・ストリーム８００は、変更ビット部分８０４と、（Ｐ）個の後続ゼロを含む部分８０６とを含む。ステップ１１６０において、本方法は、［（Ｐ）−（ｍ）］個の後続ゼロを削除することによって、第２の切り捨てＸＯＲデータ・ストリーム９００を生成し、ここで、（ｍ）はステップ１０１０（図２０）の畳み込みエンコーダにおいて用いられるレジスタの数に等しい。図１６の図示された実施形態において、第２の切り捨てＸＯＲデータ・ストリーム９００は、変更されたビット部分９０２を３個の後続ゼロ部分９０４と組み合わせて含む。
【００５５】
再び図２１を参照すると、本方法は、ステップ１１７０において、第２の切り捨てＸＯＲデータ・ストリーム９００（図１６）のような、ステップ１１６０の第２の切り捨てＸＯＲデータ・ストリームを畳み込み符号化する。特定の実施形態において、ステップ１１７０は、ステップ１０２０（図２０）の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１７０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１７０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００５６】
一例として、ここで図２、図１６及び図１７を参照すると、第２の切り捨てＸＯＲデータ・ストリーム９００と畳み込みエンコーダ回路２００とを用いて、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリーム９１０が生成される。畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリーム９１０は、部分９０２と９０４とを畳み込み符号化することによって生成される。
【００５７】
再び図２１を参照すると、ステップ１１８０において、本方法は、ステップ１１７０の畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを、ステップ１０３０（図２０）の畳み込み符号化された元データに索引付けする。ステップ１１１０において、本方法は、ステップ１０６０（図２０）のＸＯＲデータ・ストリームから、（Ｎ）個の先行ゼロを削除し、第１の切り捨てＸＯＲデータ・ストリームを生成した。ステップ１１８０において、本方法は、ステップ１１７０の畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームの第１ビットを、畳み込み符号化された元データの第［（２）（Ｎ）＋１］番目のビットに位置合わせする。
【００５８】
特定の実施形態において、ステップ１１８０は、ステップ１０２０（図２０）の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１８０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１８０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００５９】
一例として、ここで図９、図１２及び図１８を参照すると、ＸＯＲデータ・ストリーム７００は（Ｎ）個の先行ゼロを含み、ここで（Ｎ）は１３である。これらの１３個の先行ゼロは、第１の切り捨てＸＯＲデータ・ストリーム８００を生成するために削除された。ステップ１１８０において、本方法は、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリーム９１０の第１ビットを、畳み込み符号化された元データ６２０の第２７番目のビット［（２）（１３）＋１］に位置合わせする。
【００６０】
再び図２１を参照すると、本方法は、ステップ１１９０において、索引付けされたステップ１１８０の畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームとステップ１０３０の畳み込み符号化された元データとの排他的論理和演算を行い、畳み込み符号化された改訂データを生成する。特定の実施形態において、ステップ１１９０は、ステップ１０２０の元データを提供するホスト・コンピュータによって行われる。特定の実施形態において、ステップ１１９０は、ストレージ・コントローラ１３１（図１）のようなストレージ・コントローラによって行われる。特定の実施形態において、ステップ１１９０は、ストレージ・コントローラ内に配置されたプロセッサ１４０（図１）のような、プロセッサによって行われる。
【００６１】
一例として、図１９を参照すると、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリーム９１０は、畳み込み符号化された元データ６２０の部分６２２に対応する部分を含まず、畳み込み符号化された元データ６２０の部分６２６に対応する部分も含まない。ステップ１１９０において、本方法は、畳み込み符号化された改訂データ７２０の部分７２２として、部分６２２をコピーする。ステップ１１９０において、さらに、本方法は、畳み込み符号化された改訂データ７２０の部分７２６として、部分６２６をコピーする。ステップ１１９０において、さらに、本方法は、畳み込み符号化された元データ６２０の部分６２４と畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリーム９１０の部分との排他的論理和演算を行って、更新された部分７２４を作成し、それにより、畳み込み符号化された改訂データ７２０の生成を完了する。
【００６２】
特定の実施形態において、図２０及び図２１において列挙された個々のステップは、組み合わせることもでき、省くこともでき、又は順序を変更することもできる。例えば、本方法の第１の実施形態は、図２０のステップ１０１０、１０２０、１０３０、１０４０、１０５０、１０６０、１０８０及び１０９０を含む８つのステップを含む。本方法の第２の実施形態は、図２０のステップ１０１０、１０２０、１０３０、１０４０、１０５０、１０６０と、図２１のステップ１１１０、１１３０、１１４０及び１１５０との組み合わせを含む、１０個のステップを含む。本方法の第３の実施形態は、図２０のステップ１０１０、１０２０、１０３０、１０４０、１０５０、１０６０と、図２１のステップ１１１０、１１６０、１１７０、１１８０及び１１９０との組み合わせを含む、１１個のステップを含む。
【００６３】
８ステップの第１の実施形態は、改訂データ中で改訂されたビットと元のビットとの間の比が高い場合、即ち、元のビットのほとんど全てが改訂されている場合に最も有用である。一方、改訂されたビットと元のビットとの間の比が非常に低い場合、即ち「原子」更新の場合には、１１ステップの第３の実施形態の使用が好ましい。
【００６４】
第３の実施形態は１１個のステップを含むが、その第３の実施形態は、かなり切り捨てられたＸＯＲデータ・ストリーム、即ち、第２の切り捨てＸＯＲデータ・ストリームが畳み込み符号化されるステップ１１７０を利用するので、第３の実施形態は「原子」更新のためにそれほど多くの計算機能力及び時間を必要としない。さらに、１１ステップの第３の実施形態は、その畳み込み符号化された第２のＸＯＲデータのみが畳み込み符号化された元データと排他的論理和されるステップ１１９０を利用するので、第３の実施形態はそれほど多くの計算機能力及び時間を必要としない。
【００６５】
前述の装置及び方法の実施形態のいずれも、データ・ストレージ・サービス・プロバイダによって、１つ又は複数のデータ・ストレージ・サービス顧客にデータ・ストレージ・サービスを提供するために用いることができる。特定の実施形態において、１つ又は複数のデータ・ストレージ・サービス顧客は、ホスト・コンピュータ１０１（図１）、１０３（図１）、１０５（図１）、１０７（図１）及び／又は１０９(図１)のうちの１つ又は複数を所有し、及び／又は操作する。これらの１つ又は複数のデータ・ストレージ・サービス顧客は、１つ又は複数のホスト・コンピュータからストレージ・アレイ１３０（図１）のようなストレージ・アレイに顧客データを提供し、そのストレージ・アレイは、データ・ストレージ・サービス・プロバイダによって所有され、及び／又は操作される。
【００６６】
特定の実施形態において、本発明は、メモリ１５０（図１）に常駐する命令を含み、これらの命令は、プロセッサ１４０（図１）のようなプロセッサによって、図２０で列挙されたステップ１０２０、１０３０、１０４０、１０５０、１０６０、１０７０、１０８０及び／又は１０９０のうちの１つ又は複数のステップ、及び／又は、図２１で列挙されたステップ１１１０、１１２０、１１３０、１１４０、１１５０、１１６０、１１７０、１１８０及び／又は１１９０のうちの１つ又は複数のステップを行うために実行される。
【００６７】
他の実施形態において、本発明は、いずれかの他のコンピュータ・プログラムに常駐する命令を含み、これらの命令は、システム１００の外部又は内部のコンピュータによって、図２０で列挙されたステップ１０２０、１０３０、１０４０、１０５０、１０６０、１０７０、１０８０及び／又は１０９０のうちの１つ又は複数のステップ、及び／又は、図２１で列挙されたステップ１１１０、１１２０、１１３０、１１４０、１１５０、１１６０、１１７０、１１８０及び／又は１１９０のうちの１つ又は複数のステップを行うために実行される。どちらの場合においても、命令は、例えば、磁気情報ストレージ媒体、光情報ストレージ媒体、電子情報ストレージ媒体を含む、情報ストレージ媒体内で符号化されることができる。「電子ストレージ媒体」という用語によって、本出願人は、例えば、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュＰＲＯＭ、コンパクトフラッシュ、スマートメディアなどのようなデバイスのことを意味する。
【００６８】
本発明の好ましい実施形態を詳細に説明してきたが、当業者であれば、添付の特許請求の範囲で述べられる本発明の範囲を逸脱することなく、これらの実施形態に対する修正及び改造を想起することができることは明らかである。
【符号の説明】
【００６９】
１００：データ・ストレージ・システム
１１１、１１３、１１５、１１７、１１９、１３５：Ｉ／Ｏインターフェース
１３０：ストレージ・アレイ
１３１：コントローラ
１４５：バス
２００：畳み込みエンコーダ回路
２０５：入力情報ストリーム
２１０、２２０、２３０：シフト・レジスタ
２４０、２５０：加算器
２４５、２５５：出力
３００、４００：畳み込み符号化アルゴリズム
５００：ＰＲＭＬトレリス
６００：元データ
６１０：改訂データ
６２０：畳み込み符号化された元データ
７００：ＸＯＲデータ・ストリーム
７１０：畳み込み符号化されたＸＯＲデータ・ストリーム
７２０：畳み込み符号化された改訂データ
８００：第１の切り捨てＸＯＲデータ・ストリーム
８１０：畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリーム
９００：第２の切り捨てＸＯＲデータ・ストリーム
９１０：畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリーム
【図１】
2010536214.tif 000004
【図２】
2010536214.tif 000005
【図３】
2010536214.tif 000006
【図４】
2010536214.tif 000007
【図５】
2010536214.tif 000008
【図６】
2010536214.tif 000009
【図７】
2010536214.tif 000010
【図８】
2010536214.tif 000011
【図９】
2010536214.tif 000012
【図１０】
2010536214.tif 000013
【図１１】
2010536214.tif 000014
【図１２】
2010536214.tif 000015
【図１３】
2010536214.tif 000016
【図１４】
2010536214.tif 000017
【図１５】
2010536214.tif 000018
【図１６】
2010536214.tif 000019
【図１７】
2010536214.tif 000020
【図１８】
2010536214.tif 000021
【図１９】
2010536214.tif 000022
【図２０】
2010536214.tif 000023
【図２１】
2010536214.tif 000024
【手続補正書】
【提出日】平成22年3月8日(2010.3.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
畳み込み符号化されたデータを生成する方法であって、
（ｍ）段を含む畳み込みエンコーダを供給するステップであって、前記（ｍ）は１以上である、ステップと、
元データを提供するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された元データを生成するステップと、
改訂データを提供するステップであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、ステップと、
前記元データと前記改訂データとの排他的論理和演算を行うことによってＸＯＲデータ・ストリームを生成するステップであって、前記ＸＯＲデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、ステップと
切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定するステップと、
前記切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、
前記畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成するステップと、
前記畳み込み符号化されたＸＯＲデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うステップと
を含む方法。
【請求項２】
前記畳み込みエンコーダを供給するステップは、３段を含む畳み込みエンコーダを供給することをさらに含む、請求項１に記載の方法。
【請求項３】
ホスト・コンピュータと通信するデータ・ストレージ・システムを供給するステップであって、前記データ・ストレージ・システムは、前記畳み込みエンコーダとデータ・ストレージ媒体とを含むステップをさらに含み、
前記元データを提供するステップは、前記ホスト・コンピュータによって前記データ・ストレージ・システムに前記元データを提供するステップをさらに含む、
請求項１又は請求項２に記載の方法。
【請求項４】
前記畳み込み符号化された元データを前記データ・ストレージ媒体に保存するステップをさらに含む、請求項３に記載の方法。
【請求項５】
前記元データは（Ｎ）ビットを含み、前記畳み込み符号化された元データは（２）（Ｎ）ビットを含む、請求項１から請求項４のいずれか１項に記載の方法。
【請求項６】
切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、第２の切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定するステップと、
第２の切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、前記ＸＯＲデータ・ストリームから前記複数の先行ゼロを削除することによって、第１の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項１から請求項５のいずれか１項に記載の方法。
【請求項７】
第２の切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、前記第１の切り捨てＸＯＲデータ・ストリームから（ｍ）個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第２の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項６に記載の方法。
【請求項８】
（ｍ）段を含む畳み込みエンコーダと、畳み込み符号化されたデータを生成するためのプログラムであって、前記（ｍ）は１以上であり、前記プログラムは、
元データを受け取ることと、
畳み込み符号化された元データを生成することと、
改訂データを受け取ることであって、前記改訂データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含むことと、
前記元データと前記改訂データとの排他的論理和演算を行うことによって、ＸＯＲデータ・ストリームを生成することであって、前記ＸＯＲデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含むことと、
切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定することと、
切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、
前記畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成することと、
前記畳み込み符号化されたＸＯＲデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うことと
をコンピュータに実行させるプログラム。
【請求項９】
データ・ストレージ・サービス・プロバイダによって、データ・ストレージ・サービス顧客にデータ・ストレージ・サービスを提供する方法であって、
（ｍ）段を含む畳み込みエンコーダを供給するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記データ・ストレージ・サービスから元の顧客データを受け取るステップと、
前記畳み込みエンコーダを用いて、畳み込み符号化された元の顧客データを生成するステップと
を含む方法。
【請求項１０】
前記畳み込みエンコーダを供給するステップは、前記データ・ストレージ・サービス顧客によって、３段を含む畳み込みエンコーダを供給することをさらに含み、
前記データ・ストレージ・サービス顧客は、前記生成するステップを実施する、
請求項９に記載の方法。
【請求項１１】
前記データ・ストレージ・サービス顧客によって改訂データを受け取るステップであって、前記改訂された顧客データは、改訂されたビットのシーケンスと組み合わされた元のビットのシーケンスを含む、ステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記元の顧客データと前記改訂された顧客データとの排他的論理和演算を行うことにより、ＸＯＲデータ・ストリームを生成するステップであって、前記ＸＯＲデータ・ストリームは、複数の先行ゼロ及び複数の後続ゼロと組み合わされた複数の変更されたビットを含む、ステップと、
前記データ・ストレージ・サービス・プロバイダによって、切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定するステップと、
切り捨てＸＯＲデータ・ストリームを用いない場合に有効となるステップであって、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化されたＸＯＲデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化されたＸＯＲデータ・ストリームと前記畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項９に記載の方法。
【請求項１２】
切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、第２の切り捨てＸＯＲデータ・ストリームを用いるかどうかを決定するステップと、
第２の切り捨てＸＯＲデータ・ストリームを用いない場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、前記ＸＯＲデータ・ストリームから前記複数の先行ゼロを削除することによって、第１の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを形成することと、
前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第１の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項１０に記載の方法。
【請求項１３】
第２の切り捨てＸＯＲデータ・ストリームが用いられる場合に有効となる、前記データ・ストレージ・サービス・プロバイダによって、前記第１の切り捨てＸＯＲデータ・ストリームから（ｍ）個のゼロを除く全ての前記複数の後続ゼロを削除することによって、第２の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込みエンコーダを用いて、畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを形成するステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームを前記畳み込み符号化された元データに索引付けするステップと、
前記データ・ストレージ・サービス・プロバイダによって、前記畳み込み符号化された第２の切り捨てＸＯＲデータ・ストリームと前記索引付けされた畳み込み符号化された元データとの排他的論理和演算を行うステップと
をさらに含む、請求項１１に記載の方法。
【請求項１４】
ストレージ・コントローラであって、
（ｍ）段を含む畳み込みエンコーダを含み、前記（ｍ）は１以上であり、
前記畳み込みエンコーダは、（Ｎ）ビットを含むデータを入力し、（２）（Ｎ）ビットを含む畳み込み符号化されたデータを生成し、前記（Ｎ）は１以上である、
ストレージ・コントローラ。
【請求項１５】
デコーダをさらに含み、
前記デコーダは、前記畳み込み符号化されたデータを入力し、前記（Ｎ）ビットを含むデータを生成する、請求項１４に記載のストレージ・コントローラ。
【請求項１６】
前記デコーダは、ＰＲＭＬトレリスを含む、請求項１５に記載のストレージ・コントローラ。
【請求項１７】
ストレージ・コントローラを含むデータ・ストレージ・システムであって、前記ストレージ・コントローラは、
（ｍ）段を含む畳み込みエンコーダを含み、前記（ｍ）は１以上であり、
前記畳み込みエンコーダは、（Ｎ）ビットを含むデータを入力し、（２）（Ｎ）ビットを含む畳み込み符号化されたデータを生成し、前記（Ｎ）は１以上である、
データ・ストレージ・システム。
【請求項１８】
前記ストレージ・コントローラは、
デコーダをさらに含み、
前記デコーダは、前記畳み込み符号化されたデータを入力し、前記（Ｎ）ビットを含むデータを生成する、請求項１７に記載のデータ・ストレージ・システム。
【請求項１９】
前記デコーダは、ＰＲＭＬトレリスを備える、請求項１８に記載のデータ・ストレージ・システム。
【請求項２０】
請求項８に記憶のプログラムを実装する製品。
【国際調査報告】
2010536214.tif 000025
2010536214.tif 000026
2010536214.tif 000027
2010536214.tif 000028