特許ウォッチ

公開番号2025139943
公報種別公開特許公報(A)
公開日2025-09-29
出願番号2024039045
出願日2024-03-13
発明の名称データ圧縮装置、データ伸張装置、およびメモリシステム
出願人キオクシア株式会社
代理人弁理士法人スズエ国際特許事務所
主分類H03M 7/42 20060101AFI20250919BHJP(基本電子回路)
要約【課題】スループットを向上できるデータ圧縮装置を実現する。
【解決手段】実施形態によれば、データ圧縮装置は、全リテラル判定部と、終端シンボル追加部とを具備する。全リテラル判定部は、第1データブロックに対する辞書式圧縮により得られた第2データブロックに含まれる1つ以上のシンボルが、全てリテラルシンボルであるか否かを判定する。終端シンボル追加部は、1つ以上のシンボルが全てリテラルシンボルである場合、第2データブロックの終端にブロック終端シンボルを追加しない。終端シンボル追加部は、1つ以上のシンボルの内の少なくとも1つのシンボルがリテラルシンボルでない場合、第2データブロックの終端にブロック終端シンボルを追加する。
【選択図】図9
特許請求の範囲【請求項１】
第１データブロックに対する辞書式圧縮により得られた第２データブロックに含まれる１つ以上のシンボルが、全てリテラルシンボルであるか否かを判定する全リテラル判定部と、
前記１つ以上のシンボルが全てリテラルシンボルである場合、前記第２データブロックの終端にブロック終端シンボルを追加せず、
前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、前記第２データブロックの終端に前記ブロック終端シンボルを追加する終端シンボル追加部と、
を具備するデータ圧縮装置。
続きを表示（約 1,400 文字）【請求項２】
前記第１データブロックを辞書式圧縮して前記第２データブロックを生成する辞書式圧縮回路をさらに備え、
前記終端シンボル追加部は、
前記１つ以上のシンボルを、前記辞書式圧縮回路から１シンボルずつ取り込み、前記取り込んだシンボルが辞書式圧縮される前のデータサイズを取得し、前記取得したデータサイズの累積値を算出し、
前記算出した累積値が、前記第１データブロックのサイズ情報が示すサイズに達する場合に、前記取り込んだシンボルが前記第１データブロックの終端に対応すると判定し、前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、前記第２データブロックの終端に前記ブロック終端シンボルを追加する、
請求項１に記載のデータ圧縮装置。
【請求項３】
前記全リテラル判定部は、
前記取り込んだシンボルがリテラルシンボルであるか否かを判定し、リテラルシンボルでない場合はフラグをＦａｌｓｅに設定する、
請求項２に記載のデータ圧縮装置。
【請求項４】
前記終端シンボル追加部は、
前記取り込んだシンボルが前記第１データブロックの終端に対応すると判定する場合に、前記フラグがＦａｌｓｅであるならば、前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでないと判定する、
請求項３に記載のデータ圧縮装置。
【請求項５】
前記第２データブロックをエントロピー符号化することによって圧縮データを生成する符号化部をさらに具備する、
請求項１に記載のデータ圧縮装置。
【請求項６】
前記圧縮データは、前記１つ以上のシンボルが全てリテラルシンボルであるか否かを示す情報を含む、
請求項５に記載のデータ圧縮装置。
【請求項７】
前記圧縮データは、前記第２データブロックのサイズを示す情報を含む、
請求項５に記載のデータ圧縮装置。
【請求項８】
前記第２データブロックのシンボル毎の出現頻度に基づいて、符号化テーブルを生成する符号化テーブル生成部をさらに具備し、
前記符号化部は、前記符号化テーブルを用いて前記第２データブロックをエントロピー符号化する、
請求項５に記載のデータ圧縮装置。
【請求項９】
前記終端シンボル追加部は、
前記１つ以上のシンボルが辞書式圧縮される前のデータサイズを算出し、
前記データサイズと、前記第１データブロックのサイズを示す情報とに基づいて、前記１つ以上のシンボルの終端が前記第１データブロックの終端に対応するか否かを判定し、
前記１つ以上のシンボルの終端が前記第１データブロックの終端に対応し、且つ前記１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、前記第２データブロックの終端に前記ブロック終端シンボルを追加する、
請求項１に記載のデータ圧縮装置。
【請求項１０】
前記全リテラル判定部は、前記１つ以上のシンボルが全てリテラルシンボルであるか否かを示す情報を、前記終端シンボル追加部に出力する、
請求項９に記載のデータ圧縮装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、データを圧縮または伸張する技術に関する。
続きを表示（約 1,700 文字）【背景技術】
【０００２】
データを圧縮して圧縮データ（圧縮ストリーム）を生成する圧縮方式として、例えば、ＲＦＣ１９５１に定められたＤＥＦＬＡＴＥが知られている。ＤＥＦＬＡＴＥでは、辞書式圧縮の結果として得られたシンボル列に対するエントロピー符号化が規定されている。
【０００３】
エントロピー符号化は、符号化対象のシンボル列におけるシンボル毎の出現頻度に基づいて符号化テーブルを生成する可変長符号化方式である。符号化テーブルは、シンボルと、当該シンボルに割り当てられた符号語との対応を示す。エントロピー符号化では、出現頻度が高いシンボルには短い符号語が割り当てられ、出現頻度が低いシンボルには長い符号語が割り当てられる。よって、符号化対象の各シンボルは、符号化テーブルを用いて可変長符号に変換される。
【先行技術文献】
【特許文献】
【０００４】
米国特許出願公開第２０２２／０３７６７０１号明細書
米国特許出願公開第２０２２／００８３３８２号明細書
米国特許出願公開第２０２３／０００６６８９号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の一実施形態では、スループットを向上できるデータ圧縮装置、データ伸張装置、およびメモリシステムを提供する。
【課題を解決するための手段】
【０００６】
実施形態によれば、データ圧縮装置は、全リテラル判定部と、終端シンボル追加部とを具備する。全リテラル判定部は、第１データブロックに対する辞書式圧縮により得られた第２データブロックに含まれる１つ以上のシンボルが、全てリテラルシンボルであるか否かを判定する。終端シンボル追加部は、１つ以上のシンボルが全てリテラルシンボルである場合、第２データブロックの終端にブロック終端シンボルを追加しない。終端シンボル追加部は、１つ以上のシンボルの内の少なくとも１つのシンボルがリテラルシンボルでない場合、第２データブロックの終端にブロック終端シンボルを追加する。
【図面の簡単な説明】
【０００７】
実施形態に係るデータ圧縮装置およびデータ伸張装置を含む情報処理システムの構成の例を示すブロック図。
実施形態に係るデータ圧縮装置から出力される、あるいはデータ伸張装置に入力される、圧縮ストリームの例を示す図。
実施形態に係るデータ圧縮装置による辞書式圧縮およびエントロピー符号化において生成されるデータの例を示す図。
実施形態に係るデータ伸張装置によるエントロピー復号および辞書式伸張において生成されるデータの例を示す図。
第１比較例に係るデータ圧縮装置の構成を示すブロック図。
第１比較例に係るデータ伸張装置の構成を示すブロック図。
第２比較例に係るデータ伸張装置の構成を示すブロック図。
第２比較例に係るデータ伸張装置において実行されるブロック境界判定処理の手順を示すフローチャート。
実施形態に係るデータ圧縮装置の構成例を示すブロック図。
実施形態に係るデータ圧縮装置において実行される全リテラル判定処理の手順の例を示すフローチャート。
実施形態に係るデータ伸張装置の構成例を示すブロック図。
実施形態に係るデータ伸張装置において実行されるブロック境界判定処理の手順の例を示すフローチャート。
【発明を実施するための形態】
【０００８】
以下、実施の形態について図面を参照して説明する。
【０００９】
図１は、実施形態に係る辞書式圧縮部を含む情報処理システムの構成の例を示す。情報処理システム１は、ホストデバイス２と、メモリシステム３とを含む。
【００１０】
ホストデバイス２は、データをメモリシステム３に格納する情報処理装置である。ホストデバイス２は、例えば、大量且つ多様なデータをメモリシステム３に格納するストレージサーバ、またはパーソナルコンピュータである。以下では、ホストデバイス２を、ホスト２と称する。
（【００１１】以降は省略されています）

関連特許