特許ウォッチ

公開番号2025010382
公報種別公開特許公報(A)
公開日2025-01-20
出願番号2024192855,2023105981
出願日2024-11-01,2020-12-16
発明の名称受信したデータを処理する装置
出願人日立ヴァンタラ株式会社
代理人藤央弁理士法人
主分類H03M 7/40 20060101AFI20250109BHJP(基本電子回路)
要約【課題】レンジ符号の復号を高速化する。
【解決手段】装置は、レンジ符号に基づき圧縮された入力コードの一部又は全部を伸張して、Nビット列を復号する伸張回路を含む。Nは1より大きい整数、Kは1からNの各整数を表す。入力コードの第Kビットのビット値は、第Kビットより前のビットのビット履歴に基づき復号されるものである。伸張回路は、Nビット列のビットの候補ビット値について、第Kビットより前のビットの取りうる複数通りのビット履歴に基づき複数の候補ビット値をそれぞれ算出することを、複数のビットに対して行う。
【選択図】図8
特許請求の範囲【請求項１】
受信したデータを処理する装置であって、
レンジ符号に基づき圧縮された入力コードの一部又は全部を伸張して、Ｎビット列を復号する伸張回路を含み、
前記Ｎは１より大きい整数、Ｋは１からＮの各整数を表し、
前記入力コードの第Ｋビットのビット値は、前記第Ｋビットより前のビットのビット履歴に基づき復号されるものであり、
前記伸張回路は、
前記Ｎビット列のビットの候補ビット値について、前記第Ｋビットより前のビットの取りうる複数通りのビット履歴に基づき複数の候補ビット値をそれぞれ算出することを、複数のビットに対して行う、装置。
続きを表示（約 1,600 文字）【請求項２】
請求項１に記載の装置であって、
前記第Ｋビットの正解ビット値を、前記複数の候補ビット値から、前記第Ｋビットより前の正解ビット履歴に基づき選択することを繰り返して、前記Ｎビット列を復号する、装置。
【請求項３】
請求項１に記載の装置であって、
前記複数の候補ビット値をそれぞれ算出することを、前記複数のビットに対して並列に行う、装置。
【請求項４】
請求項１に記載の装置であって、
前記複数の候補ビット値をそれぞれ算出することを、前記複数のビットに対して３つ以上並列に行い、
前記第Ｋビットの候補ビット値を１つ算出し、第Ｋ＋１ビットの候補ビット値を２つ算出し、第Ｋ＋２ビットの候補ビット値を４つ算出する、装置。
【請求項５】
請求項１に記載の装置であって、
前記伸張回路は、
前記ビット履歴に応じて現れるビット値の確率値を格納し、
格納されている前記確率値において、復号された前記Ｎビット列を構成する正解ビットが基づくビット履歴に対応する確率値を選択して更新する、装置。
【請求項６】
請求項１に記載の装置であって、
前記Ｎビット列における第Ｋビットの候補ビット値の算出は、２＾（Ｋ－１）通りのビット履歴それぞれの確率値による分割対象レンジに対する乗算を実行して二つの区画に分割し、前記入力コードにおける前記第Ｋビットの前記二つの区画のうちサブコードにより特定される区画から２＾（Ｋ－１）通りそれぞれの候補ビット値を決定する、装置。
【請求項７】
請求項１に記載の装置であって、
前記伸張回路は、
前記入力コード全体から復号するビット数が、予め設定された最大値よりも大きい場合、前記入力コードの一部からのビット列の復号を、複数サイクル実行する、装置。
【請求項８】
請求項７に記載の装置であって、
前記複数サイクルにおける第２サイクル以降のサイクルにおいて、前記第Ｋビットの候補ビット値それぞれを決定するための分割対象レンジは、直前のサイクルにおける前記第Ｋビットの正解ビット値に対する区画である、装置。
【請求項９】
ストレージシステムであって、
ホストからの要求を受信するインタフェースと、
前記ホストからのコマンドに応じて記憶ドライブへのデータの書き込み及び前記記憶ドライブからのデータの読み出しを実行するコントローラと、を含み、
前記コントローラは、レンジ符号に基づき圧縮された入力コードの一部又は全部を伸張して、Ｎビット列を復号する伸張回路を含み、
前記Ｎは１より大きい整数、Ｋは１からＮの各整数を表し、
前記入力コードの第Ｋビットのビット値は、前記第Ｋビットより前のビットのビット履歴に基づき復号されるものであり、
前記伸張回路は、
前記Ｎビット列のビットの候補ビット値について、前記第Ｋビットより前のビットの取りうる複数通りのビット履歴に基づき複数の候補ビット値をそれぞれ算出することを、複数のビットに対して行い、
前記コントローラは、前記ホストからのリードコマンドに応じて前記記憶ドライブから転送された前記入力コードを前記伸張回路によって復号してリードデータを生成し、
前記リードデータを、前記インタフェースを介して前記ホストに返す、ストレージシステム。
【請求項１０】
請求項９に記載のストレージシステムであって、
前記伸張回路は、
前記第Ｋビットの正解ビット値を、前記複数の候補ビット値から、前記第Ｋビットより前の正解ビット履歴に基づき選択することを繰り返して、前記Ｎビット列を復号する、ストレージシステム。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、レンジ符号に基づき圧縮された入力コードを復号する技術に関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
大量のデータを蓄積・管理するための情報機器であるストレージシステムは、より多くのデータを格納すれば容量当たりのコストを低減することができる。そのため、ストレージシステムには、書き込まれたデータを圧縮してからディスクドライブに格納する機能を搭載するものがある。
【０００３】
例えば、近年、ストレージシステムの記憶媒体として、ＨＤＤ（ＨａｒｄＤｉｓｋＤｒｉｖｅ）に加えて又は代えて、不揮発性半導体メモリであるＮＡＮＤ型フラッシュメモリを搭載したＳＳＤ（ＳｏｌｉｄＳｔａｔｅＤｒｉｖｅ）が採用されるようになってきた。ＳＳＤはデータアクセスにおいてＨＤＤのような物理的なヘッドシーク機構を持たないため、頭出し遅延（レイテンシ）が少なく、ランダムなデータリードにおいて優れた応答性能を有する。
【０００４】
そのため、高速なランダムリードが求められるデータベース等のアプリケーションでは、ストレージシステムの記憶媒体としてＨＤＤからＳＳＤへの置き換えが進んでいる。ただし、ＳＳＤのビットコストは、フラッシュメモリセルの高集積化に伴って年々安くなってきてはいるが、依然ＨＤＤのビットコストに比べて３倍程度と高いままである。
【０００５】
そこで、ＳＳＤを記憶媒体とするストレージシステムは、可逆圧縮技術を導入し、ＳＳＤへ格納されるデータサイズを減らす機能を持つものが多い。それによって、システムの記憶容量を仮想的に大きく見せることができ、容量当たりのコストを低下させて、ＨＤＤを記憶媒体とするストレージシステムのそれに近づけることができる。
【０００６】
ストレージシステムにホストから圧縮データに対する読み出し要求がきた場合、圧縮データを伸張し、元の平文データに戻してからホストに返す。その際のリード応答時間が、非圧縮データに対する読み出しの場合と比べて著しく悪化しないように、圧縮データの伸張処理はできるだけ高速に行うことが好ましい。
【０００７】
ストレージシステムのデータ圧縮機能に採用する圧縮アルゴリズムは、高い圧縮率を持つものほど、容量当たりのコストを低減することができる。ＬＺＭＡアルゴリズムは、高い圧縮率を持つことで知られる可逆データ圧縮アルゴリズムである。このアルゴリズムは、スライド辞書型圧縮にレンジ符号と呼ばれる算術符号を組み合わせたものである。
【０００８】
レンジ符号処理では、１ビットを入力（符号化時）又は出力（復号時）するたびに乗算を行う必要がある。よって、レンジ符号処理のビットレートは非常に遅い。レンジ符号処理での乗算に用いる値のためにテーブルを参照するが、参照するためのインデックスは、入力（符号化時）又は出力（復号時）のビット履歴によって決まる。レンジ符号処理での乗算を複数ビット並列で行うことができれば、その性能は向上し、ＬＺＭＡアルゴリズムの処理性能は向上する。
【０００９】
レンジ符号の符号化処理（圧縮時）については、非特許文献１のように、ビット履歴をあらかじめ準備しておき、テーブル参照を並列化し、複数ビットについて乗算を並列に行って高速化する公知技術がある。並列度をＮとすると、符号化性能はＮ倍に向上する。これによって、ＬＺＭＡの圧縮処理は高速化が可能である。
【先行技術文献】
【非特許文献】
【００１０】
“A Parallel Adaptive Range Coding Compressor: Algorithm, FPGA Prototype, Evaluation”, Ivan Shcherbakov and Norbert Wehn, Data Compression Conference, 2012.
【発明の概要】
【発明が解決しようとする課題】
（【００１１】以降は省略されています）

関連特許