あいまいまたは不当な出力がないレンジコーディング

Question

レンジコーダーでは、有限精度の算術演算を使用すると、最初に何らかのフラッシュや微調整を適用せずに次のシンボルをエンコードすることができない場合があります。ワーキングレジスタ。

結果として、どのように調整されるかに応じて、いくつかの小さなギャップが正しいビットストリームのセットに残る可能性があります。

例えば、Wikipedia pageは、出力範囲をより多くのビットをシフトアウトできるようにすることを提案し、元の範囲の一部を未定義として残します。

デコーダでは、同じポイントに来て、入力ビットストリーム自体がエンコーダの調整に適合していなくても、エンコーダによって破棄されたはずのギャップに入ることがあります。このようなビットストリームの正しいデコードはありません。

ハフマン（これは不完全なシンボルがある可能性のあるストリームの終わりを除く）の入力設定がなくても通常定義されているようなものです。そのため、任意のビットストリームを元のビットストリームに再エンコードできるメッセージにデコードすることは可能です。

私の質問は次のとおりです。精度制限を扱うが、復号不能またはあいまいなビットストリームの可能性を生じさせないような調整を行うことは可能ですか？そのような任意のビットストリームを与えられたそれは常に元のビットストリームに再エンコードすることができるシンボルのいくつかのセットにそれをデコードすることは可能ですか？

直感的には不可能であるはずですが、私はこの問題に対して頭を打つべきではありません。しかし、私はハフマンを見て、それが私がシミュレートできるはずの特性を持っている理由を調べます。

Answer 1

質問を書く過程で、私は解決策を見つけた可能性があります。しかし、私はまだ確信していません。私はそれをここに残し、誰か（おそらく自分自身）が最終的に私が間違っている理由を教えてくれるか、他人にとって正しいかもしれないし、潜在的に有用なものになるでしょう...

範囲の出力が次のシンボルにとって小さすぎる場合、その範囲は2の大きな累乗である値に跨っており、それは最下位ビットが異なる下位境界と上限境界となる点であることを意味します。

したがって、シンボルの周波数テーブルを取り、範囲内のPOT境界とほぼ同じ場所に分割します。次に、シンボルが第1パーティションであるか第2パーティションであるかに応じて、POTにハイ境界またはロー境界を設定します。新たに解放されたビットをフラッシュし、完全なシンボルであるかのようにそのパーティションを符号化して実行する。

おそらく、それほど長持ちしない機能的に同等の方法があります。