特許ウォッチ

公開番号2025138100
公報種別公開特許公報(A)
公開日2025-09-25
出願番号2024036933
出願日2024-03-11
発明の名称データ圧縮回路、メモリシステム、および制御方法
出願人キオクシア株式会社
代理人弁理士法人スズエ国際特許事務所
主分類H03M 7/40 20060101AFI20250917BHJP(基本電子回路)
要約【課題】回路面積を削減することができるデータ圧縮回路を実現する。
【解決手段】データ圧縮回路の複数の中間マッチ候補生成回路は、対応する中間マッチ候補選択回路から受信したマッチ長に対応する距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致し、且つ受信した前記マッチ長が閾値を上回っている場合に、前記中間マッチ候補を前記マッチ長に基づいてインクリメントすることによって、中間マッチ候補を生成する。前記複数の中間マッチ候補生成回路は、受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致しない、あるいは受信した前記マッチ長が前記閾値以下である場合に、前記マッチ長を新たな中間マッチ候補として生成する。
【選択図】図6
特許請求の範囲【請求項１】
入力された第１データを圧縮するデータ圧縮回路であって、
１バイトのデータユニットをそれぞれ格納する複数のレジスタを有するバッファと、
前記複数のレジスタは、サイクルごとに前記第１データに含まれるデータユニットが順番に格納される、一つ以上の第１のレジスタを含み、
前記一つ以上の第１のレジスタと、前記第１のレジスタに格納されているデータユニットよりも格納順が前のデータユニットを格納しているレジスタとの間の距離に対応し、前記一つ以上の第１のレジスタに格納されているデータユニットと、前記格納順が前のデータユニットとが一致するか否かを判定する、マッチ判定回路を複数備え、
各々が、前記複数のマッチ判定回路のうちの一つ以上のマッチ判定回路に対応し、前記対応する一つ以上のマッチ判定回路から受信した判定結果に基づいてマッチ長を計算する、複数のマッチ長計算回路と、
各々が、前記複数のマッチ長計算回路のうちの二つ以上のマッチ長計算回路に対応し、前記対応する二つ以上のマッチ長計算回路から受信した二つ以上のマッチ長から、一つのマッチ長を選択する、複数の中間マッチ候補選択回路と、
各々が、前記複数の中間マッチ候補選択回路にそれぞれ対応し、前記対応する中間マッチ候補選択回路によって選択されたマッチ長に基づいて中間マッチ候補を生成する、複数の中間マッチ候補生成回路と、を具備し、
前記複数の中間マッチ候補生成回路のそれぞれは、前記複数のマッチ長計算回路よりも大きいビット幅でマッチ長を計算し、
前記複数の中間マッチ候補生成回路の各々は、対応する前記中間マッチ候補選択回路から受信したマッチ長に対応する距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致し、且つ受信した前記マッチ長が閾値を上回っている場合に、前記マッチ長に基づいて前記一つ前のサイクルにおいて生成された中間マッチ候補に対応するマッチ長をインクリメントすることによって、中間マッチ候補を生成し、
受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致しない、あるいは受信した前記マッチ長が前記閾値以下である場合に、前記マッチ長を新たな中間マッチ候補として生成するように構成されている、
データ圧縮回路。
続きを表示（約 3,100 文字）【請求項２】
前記複数のマッチ長計算回路のそれぞれは、前記複数の中間マッチ候補選択回路のうちのいずれか一つに対応するように構成され、
前記サイクルごとに
前記バッファの一つの第１のレジスタは、一つのデータユニットが入力され、
前記複数のマッチ長計算回路は、前記判定結果が一致を示す場合に、前記マッチ長に１を加算し、
前記判定結果が不一致を示す場合に、前記マッチ長をリセットし、
前記複数の中間マッチ候補生成回路は、受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致し、且つ受信した前記マッチ長が０より大きい場合に、前記中間マッチ候補に１を加算することによって、中間マッチ候補を生成し、
受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致しない、あるいは受信した前記マッチ長が０である場合に、前記マッチ長を新たな中間マッチ候補として生成するように構成されている、
請求項１に記載のデータ圧縮回路。
【請求項３】
前記複数の中間マッチ候補生成回路によって生成された複数の中間マッチ候補から、一つの中間マッチ候補をマッチ候補として選択する、マッチ候補選択回路を、さらに具備する、
請求項２に記載のデータ圧縮回路。
【請求項４】
前記複数のマッチ長計算回路のうち、第１距離以上の距離に対応する一つ以上の第１マッチ長計算回路それぞれが、前記複数の中間マッチ候補選択回路のいずれかに対応するように構成され、
前記複数のマッチ長計算回路のうち、前記第１距離未満の距離に対応する一つ以上の第２マッチ長計算回路は、前記中間マッチ候補生成回路と同じビット幅を使用してマッチ長を計算するように構成され、
前記データ圧縮回路は、
前記一つ以上の第２マッチ長計算回路それぞれによって計算された一つ以上のマッチ長から、一つのマッチ候補を選択するように構成された、第１マッチ候補選択回路と、
前記選択された一つのマッチ候補および前記複数の中間マッチ候補生成回路によって生成された複数の中間マッチ候補から、一つのマッチ候補を選択する、第２マッチ候補選択回路と、をさらに具備する、
請求項１に記載のデータ圧縮回路。
【請求項５】
前記バッファは、前記サイクルごとにＮ個のデータユニットが入力され、
前記Ｎは、２以上の整数であり、
前記複数の中間マッチ候補生成回路のそれぞれは、前記選択されたマッチ長と、前記マッチ長の最新端とに基づいて、前記中間マッチ候補に対応するマッチ長を生成するように構成されている、
請求項１に記載のデータ圧縮回路。
【請求項６】
前記複数の中間マッチ候補生成回路によって生成された複数の中間マッチ候補から、一つの中間マッチ候補をマッチ候補として選択する、マッチ候補選択回路を、さらに具備する、
請求項５に記載のデータ圧縮回路。
【請求項７】
前記複数の中間マッチ候補生成回路は、
受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致し、且つ受信した前記マッチ長が前記Ｎより大きい場合に、前記受信したマッチ長と前記受信したマッチ長の最新端とに基づいた値を、前記一つ前のサイクルにおいて生成された中間マッチ候補に対応するマッチ長に加算することによって、中間マッチ候補を生成し、
受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致しない、あるいは受信した前記マッチ長が前記Ｎ以下である場合に、前記受信したマッチ長を新たな中間マッチ候補として生成するように構成されている、
請求項５に記載のデータ圧縮回路。
【請求項８】
Ｍは、前記Ｎより大きく、且つ２のべき乗の値であり、
前記複数の中間マッチ候補生成回路は、
受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致し、且つ受信した前記マッチ長が前記Ｍ以上である場合に、前記受信したマッチ長と前記受信したマッチ長の最新端とに基づいた値を、前記一つ前のサイクルにおいて生成された中間マッチ候補に対応するマッチ長に加算することによって、中間マッチ候補を生成し、
受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致しない、あるいは受信した前記マッチ長が前記Ｍ未満である場合に、前記受信したマッチ長を新たな中間マッチ候補として生成するように構成されている、
請求項５に記載のデータ圧縮回路。
【請求項９】
請求項１に記載のデータ圧縮回路、およびプロセッサを含むメモリコントローラと、
前記メモリコントローラによる制御に基づいてデータを格納する不揮発性メモリと、を具備する、メモリシステムであって、
前記データ圧縮回路は、
選択されたマッチ候補に基づいて、前記第１データを加工するマッチ候補加工処理回路と、
前記加工されたデータに対して、非マッチデータを挿入する非マッチ入力データ挿入回路と、
前記非マッチデータを挿入されたデータをエントロピー符号化することによって、圧縮データを生成するエントロピー符号化回路とをさらに具備し、
前記メモリコントローラは、
前記生成された圧縮データを前記不揮発性メモリに書き込むように構成されている、
メモリシステム。
【請求項１０】
入力された第１データを圧縮するデータ圧縮回路を制御する制御方法であって、
サイクルごとに、
１バイトのデータユニットをそれぞれ格納する複数のレジスタを有するバッファに、前記第１データに含まれる一つ以上のデータユニットを順番に格納することと、
前記バッファ内の距離ごとに、前記一つ以上のデータユニットそれぞれと、前記一つ以上のデータユニットそれぞれよりも格納順が前のデータユニットとが一致するか否かを判定することと、
前記判定の結果に基づいて、前記距離ごとに、複数のマッチ長それぞれを計算することと、
前記計算された複数のマッチ長のうちの二つ以上のマッチ長からなる複数のグループから最も長いマッチ長をそれぞれ選択することと、
前記選択されたマッチ長のそれぞれが、対応する距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致し、且つ前記選択されたマッチ長が閾値を上回っている場合に、前記選択されたマッチ長に基づいて前記一つ前のサイクルにおいて生成された中間マッチ候補に対応するマッチ長をインクリメントすることによって、中間マッチ候補を生成することと、
前記選択されたマッチ長のそれぞれが、対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致しない、あるいは前記選択されたマッチ長が前記閾値以下である場合に、前記マッチ長を新たな中間マッチ候補として生成することとを具備する
制御方法。

発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、データ圧縮回路と、メモリシステムおよび制御方法に関する。
続きを表示（約 2,700 文字）【背景技術】
【０００２】
近年、不揮発性メモリを備えるメモリシステムが広く普及している。このようなメモリシステムにおいて、大量のデータをそのまま格納することは、大きな記憶容量を有するメモリシステムを必要とすることになる。例えば、データセンターにおいて、このようなメモリシステムを使用すると、莫大なコストが必要とされる。
【０００３】
そのため、一般的には、データを可逆圧縮することによって、メモリシステムに書き込まれるデータのサイズが削減される。
【０００４】
このデータの可逆圧縮を実行するデータ圧縮回路は、単位時間当たりに多くのデータの圧縮をすることができるとスループットが高くなる。
【先行技術文献】
【特許文献】
【０００５】
米国特許出願公開第２００７／０１４６１７３号明細書
米国特許出願公開第２０１４／０１５６７９０号明細書
米国特許第６２６８８０９号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の実施形態が解決しようとする課題は、回路面積を削減することができるデータ圧縮回路、メモリシステムおよび制御方法を提供することである。
【課題を解決するための手段】
【０００７】
実施形態によれば、データ圧縮回路は、入力された第１データを圧縮する。データ圧縮回路は、バッファと、複数のマッチ判定回路と、複数のマッチ長計算回路と、複数の中間マッチ候補選択回路と、複数の中間マッチ候補生成回路とを具備する。前記バッファは、１バイトのデータユニットをそれぞれ格納する複数のレジスタを有する。前記複数のレジスタは、サイクルごとに前記第１のデータに含まれるデータユニットが順番に格納される、一つ以上の第１のレジスタを含む。前記複数のマッチ判定回路は、前記一つ以上の第１のレジスタと、前記第１のレジスタに格納されているデータユニットよりも格納順が前のデータユニットを格納しているレジスタそれぞれとの間の距離のそれぞれに一対一で対応し、前記一つ以上の第１のレジスタに格納されているデータユニットと、前記格納順が前のデータユニットとが一致するか否かを判定する。前記複数のマッチ長計算回路は、各々が、前記複数のマッチ判定回路のうちの一つ以上のマッチ判定回路に対応し、前記対応する一つ以上のマッチ判定回路から受信した判定結果に基づいてマッチ長を計算する。前記複数の中間マッチ候補選択回路は、各々が、前記複数のマッチ長計算回路のうちの二つ以上のマッチ長計算回路に対応し、前記対応する二つ以上のマッチ長計算回路から受信した二つ以上のマッチ長から、一つのマッチ長を選択する。前記複数の中間マッチ候補生成回路は、各々が、前記複数の中間マッチ候補選択回路にそれぞれ対応し、前記対応する中間マッチ候補選択回路によって選択されたマッチ長に基づいて中間マッチ候補を生成する。前記複数の中間マッチ候補生成回路のそれぞれは、前記複数のマッチ長計算回路よりも大きいビット幅でマッチ長を計算する。前記複数の中間マッチ候補生成回路の各々は、対応する前記中間マッチ候補選択回路から受信したマッチ長に対応する距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致し、且つ受信した前記マッチ長が閾値を上回っている場合に、前記マッチ長に基づいて前記一つ前のサイクルにおいて生成された中間マッチ候補に対応するマッチ長をインクリメントすることによって、中間マッチ候補を生成する。前記複数の中間マッチ候補生成回路は、受信した前記マッチ長に対応する前記距離が一つ前のサイクルにおいて生成された中間マッチ候補に対応する距離と一致しない、あるいは受信した前記マッチ長が前記閾値以下である場合に、前記マッチ長を新たな中間マッチ候補として生成する。
【図面の簡単な説明】
【０００８】
第１実施形態に係るデータ圧縮回路を含むメモリシステムの構成例を示すブロック図。
第１実施形態に係るデータ圧縮回路およびデータ伸張回路によって実行されるデータ圧縮処理、およびデータ伸張処理を説明するための図。
第１実施形態に係るデータ圧縮回路の辞書式符号化部の構成例を示すブロック図。
比較例に係るデータ圧縮回路によって実行されるデータ圧縮処理について説明するための図。
比較例に係るデータ圧縮回路に含まれるマッチ長計算回路の構成例を示す図。
第１実施形態に係るデータ圧縮回路によって実行されるデータ圧縮処理について説明するための図。
第１実施形態に係るデータ圧縮回路に含まれる中間マッチ候補生成回路の構成例を示す図。
第１実施形態に係るデータ圧縮回路によって実行されるデータ圧縮処理の手順を示すフローチャート。
第２実施形態に係るデータ圧縮回路によって実行されるデータ圧縮処理について説明するための図。
第２実施形態に係るデータ圧縮回路によって実行されるデータ圧縮処理の手順を示すフローチャート。
第３実施形態に係るデータ圧縮回路によって実行されるデータ圧縮処理について説明するための図。
第３実施形態に係るデータ圧縮回路に含まれる、マッチ長計算回路の構成例を示す図。
第３実施形態に係るデータ圧縮回路に含まれるマッチ長計算回路における、入力データに対する出力データを示す図。
第３実施形態に係るデータ圧縮回路に含まれる中間マッチ候補生成回路の構成例を示す図。
第３実施形態に係るデータ圧縮回路によって実行されるデータ圧縮処理の手順を示すフローチャート。
【発明を実施するための形態】
【０００９】
以下、図面を参照して、各実施形態を説明する。
（第１実施形態）
図１は、第１実施形態に係るデータ圧縮回路４５１を含むメモリシステム３を含む情報処理システム１の構成例を示すブロック図である。第１実施形態に係るメモリシステム３は、不揮発性メモリを含むストレージデバイスである。
【００１０】
情報処理システム１は、ホストデバイス（ホスト）２と、メモリシステム３とを含む。ホスト２と、メモリシステム３とは、バス７を介して接続可能である。
（【００１１】以降は省略されています）

関連特許