特許ウォッチ

公開番号2025035337
公報種別公開特許公報(A)
公開日2025-03-13
出願番号2023142321
出願日2023-09-01
発明の名称可変長符号化装置、およびメモリシステム
出願人キオクシア株式会社
代理人弁理士法人スズエ国際特許事務所
主分類H03M 7/42 20060101AFI20250306BHJP(基本電子回路)
要約【課題】上限値以下の符号長を有し、完全符号である符号語をシンボルに割り当てる場合に、処理時間および処理リソースを低減できる可変長符号化装置を実現する。
【解決手段】実施形態によれば、可変長符号化装置は、符号長決定部と符号長制約部を具備する。符号長決定部は、ハフマン木に基づいて、N個のシンボルにそれぞれ対応するN個の符号長を決定する。符号長制約部は、N個の符号長に、最大符号長よりも長い第1符号長が含まれる場合、第1符号長に対応する少なくとも1つの第1シンボルをN個のシンボルから選択し、最大符号長未満の第2符号長に対応する少なくとも1つの第2シンボルをN個のシンボルから選択し、第2シンボルに対応する第2符号長を、第2符号長に1を加算した符号長に変更し、第1シンボルに対応する第1符号長を、変更した第2符号長に等しい符号長に変更する。
【選択図】図18
特許請求の範囲【請求項１】
入力された複数のシンボルのシンボル毎の出現頻度に基づいて、Ｎ個のシンボルと、前記Ｎ個のシンボルにそれぞれ関連付けられたＮ個の出現頻度とを示す頻度テーブルを生成する頻度表生成部と、
前記頻度テーブルに基づいてハフマン木を生成するハフマン木生成部と、
前記ハフマン木に基づいて、前記Ｎ個のシンボルにそれぞれ対応するＮ個の符号長を決定する符号長決定部と、
前記Ｎ個の符号長に、最大符号長よりも長い第１符号長が含まれる場合、
前記第１符号長に対応する少なくとも１つの第１シンボルを前記Ｎ個のシンボルから選択し、
前記最大符号長未満の第２符号長に対応する少なくとも１つの第２シンボルを前記Ｎ個のシンボルから選択し、
前記第２シンボルに対応する前記第２符号長を、前記第２符号長に１を加算した符号長に変更し、
前記第１シンボルに対応する前記第１符号長を、前記変更した第２符号長に等しい符号長に変更する符号長制約部と、
前記Ｎ個の符号長に基づいて、前記Ｎ個のシンボルにそれぞれ割り当てるＮ個の可変長符号を決定する符号割当部と、
前記Ｎ個のシンボルにそれぞれ割り当てられた前記Ｎ個の可変長符号に基づいて、前記入力された前記複数のシンボルのそれぞれを可変長符号に変換する符号化部とを具備し、
前記Ｎは、２以上の整数であり、
前記入力された前記複数のシンボルが変換された前記可変長符号は、１ビット長から前記最大符号長までのビット長を有する、
可変長符号化装置。
続きを表示（約 4,100 文字）【請求項２】
前記Ｎ個のシンボルの内のＬ個のシンボルをＭ個のシンボル集合に分割し、
前記Ｍ個のシンボル集合をそれぞれ表すＭ個の代表シンボルを生成する代表シンボル生成部をさらに具備し、
前記ハフマン木生成部は、前記Ｎ個のシンボルから前記Ｌ個のシンボルを除いたＨ個のシンボルのそれぞれの出現頻度と、前記Ｍ個の代表シンボルのそれぞれの出現頻度とに基づいて、前記ハフマン木を生成し、
前記符号長決定部は、前記ハフマン木に基づいて、前記Ｈ個のシンボルにそれぞれ対応するＨ個の符号長と、前記Ｍ個の代表シンボルにそれぞれ対応するＭ個の符号長とを決定し、
前記符号長制約部は、
前記Ｍ個の代表シンボルの内の第１代表シンボルに対応する第３符号長が代表シンボル最大符号長よりも長く、且つ前記Ｈ個のシンボルに前記代表シンボル最大符号長以下の第４符号長に対応する第３シンボルが含まれる場合、前記第１代表シンボルが前記第４符号長に対応し、且つ前記第３シンボルが前記第３符号長に対応するように変更し、
前記Ｈ個の符号長に、前記最大符号長よりも長い前記第１符号長が含まれる場合、前記第１符号長に対応する前記少なくとも１つの第１シンボルを前記Ｈ個のシンボルから選択し、前記最大符号長未満の前記第２符号長に対応する前記少なくとも１つの第２シンボルを前記Ｈ個のシンボルから選択し、前記第２シンボルに対応する前記第２符号長を、前記第２符号長に１を加算した符号長に変更し、前記第１シンボルに対応する前記第１符号長を、前記変更した第２符号長に等しい符号長に変更し、
前記Ｌは、１以上の整数であり、
前記Ｍは、１以上の整数であり、
前記Ｈは、１以上の整数である、
請求項１に記載の可変長符号化装置。
【請求項３】
前記Ｎ個のシンボルの内のＬ個のシンボルをＭ個のシンボル集合に分割し、
前記Ｍ個のシンボル集合をそれぞれ表すＭ個の代表シンボルを生成する代表シンボル生成部をさらに具備し、
前記ハフマン木生成部は、前記Ｎ個のシンボルから前記Ｌ個のシンボルを除いたＨ個のシンボルのそれぞれの出現頻度と、前記Ｍ個の代表シンボルのそれぞれの出現頻度とに基づいて、前記ハフマン木を生成し、
前記符号長決定部は、前記ハフマン木に基づいて、前記Ｈ個のシンボルにそれぞれ対応するＨ個の符号長と、前記Ｍ個の代表シンボルにそれぞれ対応するＭ個の符号長とを決定し、
前記符号長制約部は、
前記Ｍ個の代表シンボルの内の第１代表シンボルに対応する第３符号長が代表シンボル最大符号長よりも長く、且つ前記Ｈ個のシンボルに前記代表シンボル最大符号長以下の符号長に対応するシンボルが含まれない場合、前記第３符号長に等しい第４符号長に対応する第３シンボルを前記Ｈ個のシンボルから選択し、前記第１代表シンボルに対応する前記第３符号長を１減少させた符号長に変更し、前記第３シンボルに対応する前記第４符号長をより長い符号長に変更し、
前記変更した第３符号長が前記代表シンボル最大符号長よりも長い場合、前記変更した第３符号長に１を加えた符号長に等しい第５符号長に各々が対応する２つのシンボルを、前記Ｈ個のシンボルから選択し、前記第１代表シンボルに対応する前記変更した第３符号長を１減少させた符号長にさらに変更し、前記選択した２つのシンボルの各々に対応する前記第５符号長をより長い符号長に変更し、
前記さらに変更した第３符号長が前記代表シンボル最大符号長よりも長い場合、前記さらに変更した第３符号長に２を加えた符号長に等しい第６符号長に各々が対応する４つのシンボルを、前記Ｈ個のシンボルから選択し、前記第１代表シンボルに対応する前記さらに変更した第３符号長を１減少させた符号長に変更し、前記選択した４つのシンボルの各々に対応する前記第６符号長をより長い符号長に変更し、
前記Ｈ個の符号長に、前記最大符号長よりも長い前記第１符号長が含まれる場合、前記第１符号長に対応する前記少なくとも１つの第１シンボルを前記Ｈ個のシンボルから選択し、前記最大符号長未満の前記第２符号長に対応する前記少なくとも１つの第２シンボルを前記Ｈ個のシンボルから選択し、前記第２シンボルに対応する前記第２符号長を、前記第２符号長に１を加算した符号長に変更し、前記第１シンボルに対応する前記第１符号長を、前記変更した第２符号長に等しい符号長に変更し、
前記Ｌは、１以上の整数であり、
前記Ｍは、１以上の整数であり、
前記Ｈは、１以上の整数である、
請求項１に記載の可変長符号化装置。
【請求項４】
前記Ｎ個のシンボルの内のＬ個のシンボルをＭ個のシンボル集合に分割し、
前記Ｍ個のシンボル集合をそれぞれ表すＭ個の代表シンボルを生成する代表シンボル生成部をさらに具備し、
前記ハフマン木生成部は、前記Ｎ個のシンボルから前記Ｌ個のシンボルを除いたＨ個のシンボルのそれぞれの出現頻度と、前記Ｍ個の代表シンボルのそれぞれの出現頻度とに基づいて、前記ハフマン木を生成し、
前記符号長決定部は、前記ハフマン木に基づいて、前記Ｈ個のシンボルにそれぞれ対応するＨ個の符号長と、前記Ｍ個の代表シンボルにそれぞれ対応するＭ個の符号長とを決定し、
前記符号長制約部は、
前記Ｍ個の代表シンボルの内の第１代表シンボルに対応する第３符号長が代表シンボル最大符号長よりも長く、且つ前記Ｈ個のシンボルに前記代表シンボル最大符号長以下の符号長に対応するシンボルが含まれない場合、前記ハフマン木において、ルートノードからの深さが前記代表シンボル最大符号長以下の中間ノードを選択し、前記選択した中間ノードからより深い方向へ辿って到達可能な全てのリーフノードのそれぞれに割り当てられた第３シンボルを選択し、前記第３シンボルに対応する符号長をより長い符号長に変更し、前記第１代表シンボルに対応する前記第３符号長を前記代表シンボル最大符号長に変更し、
前記Ｈ個の符号長に、前記最大符号長よりも長い前記第１符号長が含まれる場合、前記第１符号長に対応する前記少なくとも１つの第１シンボルを前記Ｈ個のシンボルから選択し、前記最大符号長未満の前記第２符号長に対応する前記少なくとも１つの第２シンボルを前記Ｈ個のシンボルから選択し、前記第２シンボルに対応する前記第２符号長を、前記第２符号長に１を加算した符号長に変更し、前記第１シンボルに対応する前記第１符号長を、前記変更した第２符号長に等しい符号長に変更し、
前記Ｌは、１以上の整数であり、
前記Ｍは、１以上の整数であり、
前記Ｈは、１以上の整数である、
請求項１に記載の可変長符号化装置。
【請求項５】
前記Ｍ個のシンボル集合は、前記第１代表シンボルで表される第１シンボル集合を含み、
前記代表シンボル最大符号長は、前記第１代表シンボルをｒとし、前記第１シンボル集合に含まれるシンボルの数をＫ（ｒ）とした場合、前記最大符号長からｆ（Ｋ（ｒ））を減算することで得られ、
前記ｆは、前記第１シンボル集合に含まれるシンボルの数Ｋ（ｒ）の関数である、
請求項２乃至請求項４のいずれか一項に記載の可変長符号化装置。
【請求項６】
前記ｆ（Ｋ（ｒ））は、
TIFF
2025035337000008.tif
8
49
で定義される、
請求項５に記載の可変長符号化装置。
【請求項７】
前記Ｎ個のシンボルの内、前記最大符号長より長い符号長に対応する全てのシンボルの符号長を、前記最大符号長に変更する符号長クリップ部と、
前記Ｎ個のシンボルの内の違反シンボルの数Ｉを計算する違反シンボル数計算部とをさらに具備し、
前記符号長制約部は、前記最大符号長に等しい符号長に対応する第４シンボルを前記Ｎ個のシンボルから選択し、前記最大符号長未満の符号長に対応する第５シンボルを前記Ｎ個のシンボルから選択し、前記第５シンボルに対応する前記符号長を１増加させ、前記第４シンボルに対応する前記符号長を、前記増加させた符号長に等しい符号長に変更する処理を、前記計算した違反シンボルの数Ｉに対応する回数、繰り返し行う、
請求項１乃至請求項４のいずれか一項に記載の可変長符号化装置。
【請求項８】
前記違反シンボル数計算部は、
TIFF
2025035337000009.tif
19
113
に従って、前記違反シンボルの数Ｉを計算し、
ＡｌｌＳｙｍｂｏｌは、前記Ｎ個のシンボルを含むシンボル集合であり、
ｓは、シンボル集合ＡｌｌＳｙｍｂｏｌの要素であるシンボルであり、
ｌ（ｓ）は、シンボルｓに対応する符号長であり、
ｃｌｉｐ（ｌ（ｓ））は、符号長ｌ（ｓ）が前記最大符号長より長い場合、前記最大符号長であり、符号長ｌ（ｓ）が前記最大符号長以下である場合、符号長ｌ（ｓ）であり、
ｌｍａｘは、前記最大符号長である、
請求項７に記載の可変長符号化装置。
【請求項９】
前記Ｌ個のシンボルは、前記Ｎ個のシンボルを出現頻度の降順にソートした場合の下位のＬ個のシンボルである、
請求項２乃至請求項４のいずれか一項に記載の可変長符号化装置。
【請求項１０】
前記Ｌ個のシンボルは、前記Ｎ個のシンボルを出現頻度の降順にソートした場合の上位のＨ個のシンボルを、前記Ｎ個のシンボルから除いたシンボルである、
請求項２乃至請求項４のいずれか一項に記載の可変長符号化装置。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、可変長符号化装置、およびメモリシステムに関する。
続きを表示（約 4,000 文字）【背景技術】
【０００２】
動的ハフマン符号化は、符号化対象のシンボルの出現頻度に基づいて動的に符号表を生成する可変長符号化方式である。符号表は、シンボルと、当該シンボルに割り当てられた符号語との対応を示す。動的ハフマン符号化では、出現頻度が大きいシンボルには短い符号語が割り当てられ、出現頻度が小さいシンボルには長い符号語が割り当てられる。シンボルに割り当てられた符号語（可変長符号）を、ハフマン符号とも称する。
【０００３】
データ圧縮規格やデータ圧縮ソフトウェア（例えば、ｇｚｉｐ）によっては、シンボルに割り当てられる符号語の長さ（符号長）が上限値を超えないように制約することが規定されている場合がある。このような場合には、シンボル毎の出現頻度を用いて符号表を生成する段階において、シンボルに割り当てられる符号語の長さが上限値以下となるように符号表を生成する必要がある。
【０００４】
さらに、データ圧縮規格やデータ圧縮ソフトウェアでは、動的ハフマン符号化においてシンボルに割り当てられる符号語が完全符号であることが規定される場合がある。動的ハフマン符号化においてシンボルに割り当てられる符号語が完全符号であるとは、その動的ハフマン符号化が、全ての中間ノードが２つの子ノードを持つハフマン木に基づくことに相当する。つまり、動的ハフマン符号化においてシンボルに割り当てられる符号語が完全符号であるとは、割り当てられる符号語の符号長に無駄がないことを意味する。
【先行技術文献】
【特許文献】
【０００５】
米国特許出願公開第２０２２／０２９４４６９号明細書
【非特許文献】
【０００６】
Ｌ．ＰｅｔｅｒＤｅｕｔｓｃｈ、“ＤＥＦＬＡＴＥＣｏｍｐｒｅｓｓｅｄＤａｔａＦｏｒｍａｔＳｐｅｃｉｆｉｃａｔｉｏｎｖｅｒｓｉｏｎ１．３”、［ｏｎｌｉｎｅ］、ＲＦＣ１９５１、１９９６年５月、［２０２３年５月２４日検索］、インターネット＜ＵＲＬ：ｈｔｔｐｓ：／／ｄｌ．ａｃｍ．ｏｒｇ／ｄｏｉ／ｐｄｆ／１０．１７４８７／ＲＦＣ１９５１＞
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明が解決しようとする課題は、上限値以下の符号長を有し、完全符号である符号語をシンボルに割り当てる場合に、処理時間および処理リソースを低減できる可変長符号化装置、およびメモリシステムを提供することである。
【課題を解決するための手段】
【０００８】
実施形態によれば、可変長符号化装置は、頻度表生成部、ハフマン木生成部、符号長決定部、符号長制約部、符号割当部、および符号化部を具備する。頻度表生成部は、入力された複数のシンボルのシンボル毎の出現頻度に基づいて、Ｎ個のシンボルと、Ｎ個のシンボルにそれぞれ関連付けられたＮ個の出現頻度とを示す頻度テーブルを生成する。ハフマン木生成部は、頻度テーブルに基づいてハフマン木を生成する。符号長決定部は、ハフマン木に基づいて、Ｎ個のシンボルにそれぞれ対応するＮ個の符号長を決定する。符号長制約部は、Ｎ個の符号長に、最大符号長よりも長い第１符号長が含まれる場合、第１符号長に対応する少なくとも１つの第１シンボルをＮ個のシンボルから選択し、最大符号長未満の第２符号長に対応する少なくとも１つの第２シンボルをＮ個のシンボルから選択し、第２シンボルに対応する第２符号長を、第２符号長に１を加算した符号長に変更し、第１シンボルに対応する第１符号長を、変更した第２符号長に等しい符号長に変更する。符号割当部は、Ｎ個の符号長に基づいて、Ｎ個のシンボルにそれぞれ割り当てるＮ個の可変長符号を決定する。符号化部は、Ｎ個のシンボルにそれぞれ割り当てられたＮ個の可変長符号に基づいて、入力された複数のシンボルのそれぞれを可変長符号に変換する。Ｎは、２以上の整数である。入力された複数のシンボルが変換された可変長符号は、１ビット長から最大符号長までのビット長を有する。
【図面の簡単な説明】
【０００９】
第１実施形態に係る可変長符号化装置を含む情報処理システムの構成の例を示すブロック図。
比較例に係る符号表生成部の構成の例を示すブロック図。
比較例に係る符号表生成部において実行されるハフマン木生成処理の手順を示すフローチャート。
比較例に係る符号表生成部において用いられる頻度テーブルの構成例を示す図。
比較例に係る符号表生成部において生成されるハフマン木の例を示す図。
比較例に係る符号表生成部において決定される符号長の例を示す図。
比較例に係る符号表生成部において実行される最大符号長制約処理の手順を示すフローチャート。
比較例に係る符号表生成部における図５のハフマン木の変形例を示す図。
比較例に係る符号表生成部における図８のハフマン木の変形例を示す図。
比較例に係る符号表生成部における図９のハフマン木の変形例を示す図。
比較例に係る符号表生成部における図１０のハフマン木の変形例を示す図。
第１実施形態に係る可変長符号化装置の構成例を示すブロック図。
第１実施形態に係る可変長符号化装置において生成された頻度テーブル（第０頻度テーブル）の例を示す図。
第１実施形態に係る可変長符号化装置においてソートされた頻度テーブル（第１頻度テーブル）の例を示す図。
第１実施形態に係る可変長符号化装置において用いられる、（Ａ）第１頻度テーブルの例と、第１頻度テーブルが分割された（Ｂ）第１部分テーブルおよび（Ｃ）第２部分テーブルの例とを示す図。
第１実施形態に係る可変長符号化装置において構築されるハフマン木の例を示す図。
第１実施形態に係る可変長符号化装置において用いられるマージシンボルの部分木の例を示す図。
第１実施形態に係る可変長符号化装置に含まれる最大符号長制約部の構成例を示すブロック図。
第１実施形態に係る可変長符号化装置において用いられる非代表シンボルと代表シンボルの例を示す図。
第１実施形態に係る可変長符号化装置において生成されるハフマン木の例を示す図。
第１実施形態に係る可変長符号化装置における図２０のハフマン木の変形例を示す図。
第１実施形態に係る可変長符号化装置における図２１のハフマン木の変形例を示す図。
第１実施形態に係る可変長符号化装置における図２２のハフマン木の変形例を示す図。
第１実施形態に係る可変長符号化装置において実行される最大符号長制約処理の手順の例を示すフローチャート。
第１実施形態に係る可変長符号化装置において実行される第１符号長変更処理の手順の例を示すフローチャート。
第１実施形態に係る可変長符号化装置において実行される、シンボルに符号ビット列を割り当てる疑似プログラムの例を示す図。
第１実施形態に係る可変長符号化装置において用いられる非代表シンボルと代表シンボルの例を示す図。
第２実施形態に係る可変長符号化装置において生成されるハフマン木の例を示す図。
第２実施形態に係る可変長符号化装置に含まれる最大符号長制約部の構成例を示すブロック図。
第２実施形態に係る可変長符号化装置において生成されるハフマン木の別の例を示す図。
第２実施形態に係る可変長符号化装置における図３０のハフマン木の変形例を示す図。
第２実施形態に係る可変長符号化装置における図３１のハフマン木の変形例を示す図。
第２実施形態に係る可変長符号化装置における図３２のハフマン木の変形例を示す図。
第２実施形態に係る可変長符号化装置における図３３のハフマン木の変形例を示す図。
第２実施形態に係る可変長符号化装置において実行される最大符号長制約処理の手順の例を示すフローチャート。
第２実施形態に係る可変長符号化装置において実行されるスワップ・符号長変更処理の手順の例を示すフローチャート。
第３実施形態に係る可変長符号化装置に含まれる最大符号長制約部の構成例を示すブロック図。
第３実施形態に係る可変長符号化装置において生成されるハフマン木の例を示す図。
第３実施形態に係る可変長符号化装置における図３８のハフマン木の変形例を示す図。
第３実施形態に係る可変長符号化装置における図３９のハフマン木の変形例を示す図。
第３実施形態に係る可変長符号化装置において実行される最大符号長制約処理の手順の例を示すフローチャート。
第３実施形態に係る可変長符号化装置において実行される第２符号長変更処理の手順の例を示すフローチャート。
第３実施形態に係る可変長符号化装置において特定のケースで想定されるハフマン木の第１のパターンを示す図。
第３実施形態に係る可変長符号化装置において特定のケースで想定されるハフマン木の第２のパターンを示す図。
第３実施形態に係る可変長符号化装置において特定のケースで想定されるハフマン木の第３のパターンを示す図。
第３実施形態に係る可変長符号化装置において特定のケースで想定されるハフマン木の第４のパターンを示す図。
【発明を実施するための形態】
【００１０】
以下、実施の形態について図面を参照して説明する。
（【００１１】以降は省略されています）

関連特許