Chapter 7: Boolean Entropy Decoder / 7章 2値エントロピー復号器
As discussed in the overview above, essentially the entire VP8 data stream is encoded using a boolean entropy coder.
これまで概要で検討してきたように，本質的に全てのVP8データストリームは2値エントロピー符号化器を用いて符号化されている．
An understanding of the bool_decoder is critical to the implementation of a VP8 decompressor, so we discuss in detail. It is easier to comprehend the bool_decoder in conjunction with the bool_encoder used by the compressor to write the compressed data partitions.
2値復号器の理解はVP8解凍器の実装に決定的に重要である．そこで，詳しく検討する．圧縮されたデータ区分を書き出す圧縮器で利用されている2値符号化と関連づけて2値復号器を理解することが容易である．
The bool_encoder encodes (and the bool_decoder decodes) one bool (zero-or-one boolean value) at a time. Its purpose is to losslessly compress a sequence of bools for which the probability of their being zero or one can be well-estimated (via constant or previously-coded information) at the time they are written, using identical corresponding probabilities at the time they are read.
2値符号化器（2値復号器）は一度にひとつの真偽値（0か1）を符号化（復号）する．0か1になる確率が書き出すときに十分に推定（定数，もしくは事前に符号化された情報に基づく）された2値のシーケンを歪みなしに圧縮することが目的であり，読み出されるときにも対応する同一の確率が使用される．
As the reader is probably aware, if a bool is much more likely to be zero than one (for instance), it can, on average, be faithfully encoded using much less than one bit per value. The bool_encoder exploits this. In the 1940s, Claude Shannon proved that there is a lower bound for the average datarate of a faithful encoding of a sequence of bools (whose probability distributions are known and are independent of each other) and also that there are encoding algorithms that approximate this lower bound as closely as one wishes.
読者がおそらく気がついているように，例えば2値が1よりも0でありそうな場合，平均的には，真偽値ひとつあたりは1bit以下で正確に符号化できる．2値符号化器はこれを利用する．1940年代，C. シャノンは2値シーケンスの正確な符号化に必要な平均データレートに下界が存在することを示した．さらに，この望まれる下界に限りなく近い値を近似する符号化アルゴリズムが存在することも示した．
If we encode a sequence of bools whose probability of being zero is p (and whose probability of being 1 is 1 − p), the lowest possible datarate per value is
p ⋅ log (p) + (1 − p) ⋅ log (1 − p);
taking the logarithms to the base 1 / 2 expresses the datarate in bits/value.
0である確率がp（すなわち1になる確率が1-p）である2値シーケンスを符号化する場合，実現しうる値一つごとの最低データレートは
p ⋅ log (p) + (1 − p) ⋅ log (1 − p);
である．ここで，対数は(1/2)を底とて，データレートはbits/値である．
We give two simple examples. At one extreme, if p = 1 / 2, then log (p) = log (1 − p) = 1 and the lowest possible datarate per bool is 1 / 2 + 1 / 2 = 1, that is, we cannot do any better than simply literally writing out bits. At another extreme, if p is very small, say p = 1 / 1024, then log (p) = 10, log (1 − p) is roughly .0014, and the lowest possible datarate is approximately 10 / 1024 + .0014, roughly 1/100 of a bit per bool.
二つの単純な例を与える．極端な場合，p=1/2であれば，log(p)=log(1-p)=1となり，実現しうる最低データレートは真偽値ひとつ辺り1/2+1/2=1となる．すなわち，ビット群を単純に書き出すより他によい術がない．別の極端な場合，pが非常に小さい，例えばp=1/1024であれば，log(p)=10，log(1-p)は概算で0.0014となり，実現しうる最低データレートは10/1024+0.0014で近似でき，おおよそ1/100bit/値となる．
Because most of the bools in the VP8 datastream have zero-probabilities nowhere near 1 / 2, the compression provided by the bool_encoder is critical to the performance of VP8.
VP8データスストリーム中の大部分の真偽値は1/2近辺ではなく0確率を有しているため，2値符号化器により提供される圧縮はVP8の性能に決定的に重要である．
The bool coder used by VP8 is a variant of an arithmetic coder. An excellent discussion of arithmetic coding (and other lossless compression techniques) can be found in the book Text Compression by Timothy C. Bell, John G. Cleary, and Ian H. Witten, published in 1990 by Prentice-Hall.
VP8で使用される2値符号化器は算術符号化器の一種である．算術符号化（および他の無歪み圧縮技術）の素晴らしい記述はT. C. Bell，J. G. Cleary，I. H. Witten著，Prentice-Hall 1990年出版のText Compressionという本で見られる．
7.1 Underlying Theory of Coding
7.1 符号化の基礎理論
The basic idea used by the bool coder is to consider the entire data stream (either of the partitions in our case) as the binary expansion of a single number x with 0 ≤ x < 1. The bits (or bytes) in x are of course written from high to low order and if b[j](B[j]) is the jth bit (byte) in the partition, the value x is simply the sum (starting with j = 1) of pow(2, − j) ⋅ b[j] or pow(256, − j) ⋅ B[j].
2値符号化で利用される基本的な方針は，データストリーム全体を0 ≤ x < 1の単値xの2値表現として考えることである．xのビット群（もしくはバイト群）はもちろん高次から低次へと書かれ，もし区分中のb[j]（B[j]）がj番目のビット（バイト）であれば，値xは単純に（j=1から始まる）pow(2,-j) ⋅ B[j]の総和である．
Before the first bool is coded, all values of x are possible.
最初の2値が符号化される前に，値xはあらゆる値となり得る．
The coding of each bool restricts the possible values of x in proportion to the probability of what is coded. If p1 is the probability of the first bool being zero and a zero is coded, the range of possible x is restricted to 0 ≤ x < p1. If a one is coded, the range becomes p1 ≤ x < 1.
それぞれの2値の符号化は値xの取り得る値を，符号化されるものの確率に比例した値へと限定する．p1は最初の真偽値が0になる可能性で，ゼロが符号化されるとすると，値xの取り得る範囲は0 ≤ x < p1に限定される．もし1が符号化されると，範囲はp1 ≤ x < 1となる．
The coding continues by repeating the same idea. At every stage, there is an interval a ≤ x < b of possible values of x. If p is the probability of a zero being coded at this stage and a zero is coded, the interval becomes a ≤ x < a + (p ⋅ (b − a)). If a one is coded, the possible x are restricted to a + (p ⋅ (b − a)) ≤ x < b.
符号化は同じ方針の繰り返しにより続ける．全ての段階において，値xの取り得る範囲a ≤ x < bが存在する．この段階で0に符号化される可能性をpとすると，0が符号化される場合，範囲はa ≤ x < a + (p ⋅ (b − a))になる．もし1が符号化されると，範囲はa + (p ⋅ (b − a)) ≤ x < bとなる．
Assuming only finitely many values are to be coded, after the encoder has received the last bool, it can write as its output any value x that lies in the final interval. VP8 simply writes the left endpoint of the final interval. Consequently, the output it would make if encoding were to stop at any time either increases or stays the same as each bool is encoded.
有限個の多くの値が符号化されることを想定すると，符号化器は最後の2値を受け取ったあと，最終的な範囲の中に存在する任意の値xを出力するように書き出せる．VP8は単に最終的な範囲の左側端点を書き出す．このようにして，符号化がいつでも止まることになっているならば．各々の2値が符号化されるのと同じように，作られる出力は増加するかとどまる．
Decoding parallels encoding. The decoder is presented with the number x, which has only the initial restriction 0 ≤ x < 1. To decode the first bool, the decoder is given the first probability p1. If x < p1, a zero is decoded; if x ≥ p1, a one is decoded. In either case, the new restriction on x, that is, the interval of possible x, is remembered.
復号処理は符号化処理を並列化する．復号器は数値xを提出し，数値xは0 ≤ x < 1に制限されるのみである．最初の2値を復号するために，復号器は最初の確率p1が与えられる．x < p1ならば，0が復号される．x ≥ p1ならば，1が復号される．どちらの場合も，xの新しい制限，すなわち値xの取り得る範囲は再登録される．
Decoding continues in exactly the same way: If a ≤ x < b is the current interval and we are to decode a bool with zero-probability p, we return a zero if a ≤ x < a + (p ⋅ (b − a)) and a one if a + (p ⋅ (b − a)) ≤ x < b. In either case, the new restriction is remembered in preparation for decoding the next bool.
復号処理は厳密に同じ方法で続けられる．もしa ≤ x < bが現在範囲で，2値が0になる可能性をpとして復号すると，a ≤ x < a + (p ⋅ (b − a))であれば0が，a + (p ⋅ (b − a)) ≤ x < bであれば1を返す．どちらの場合も，新しい制限は次の真偽器の復号処理のために準備として再登録される．
The process outlined above uses real numbers of infinite precision to express the probabilities and ranges. It is true that, if one could actualize this process and coded a large number of bools whose supplied probabilities matched their value distributions, the datarate achieved would approach the theoretical minimum as the number of bools encoded increased.
上記の処理の流れは確率と範囲の表現に無限精度の実数値を使用している．対応する値分布の確率値を提供している非常に多くの2値の符号化と処理が実現できるなら，達成されたデータレートは，符号化される真偽値の個数が増加するほど理論的な最小値に近づいていくだろうことは確かに正しい．
Unfortunately, computers operate at finite precision and an approximation to the theoretically perfect process described above is necessary. Such approximation increases the datarate but, at quite moderate precision and for a wide variety of data sets, this increase is negligible.
残念ながら，計算機は有限精度で演算し，理論的には上記の記述された処理を実現することの近似は必要である．このような近似はデータレートを増加させるが，極端でない精度において，かつ広い範囲のデータ集合のために，この増加は無視できる．
The only conceptual limitations are, first, that coder probabilities must be expressed at finite precision and, second, that the decoder be able to detect each individual modification to the value interval via examination of a fixed amount of input. As a practical matter, many of the implementation details stem from the fact that the coder can function using only a small “window” to incrementally read or write the arbitrarily precise number x.
概念のみの制限は，第一に符号化器確率値が有限精度で表現されるべきであること，第二に固定した入力量の検討を通して，値範囲の個別な修正を復号器が検出できるようにしなければならないことである．現実的な事柄として，任意精度の値xを順次的に読み，または書くための小さな窓のみを用いて符号化器は機能できるという事実に由来して多くの実装は記述する．
7.2 Practical Algorithm Description
7.2 実際のアルゴリズムの詳細
VP8’s bool coder works with 8-bit probabilities p. The range of such p is 0 ≤ p ≤ 255; the actual probability represented by p is p / 256. Also, the coder is designed so that decoding of a bool requires no more than an 8-bit comparison and so that the state of both the encoder and decoder can be easily represented using a small number of unsigned 16-bit integers.
VP8の2値符号化器は8ビット幅の確率値pで動作する．このpの範囲は0 ≤ p ≤ 255であり，pによって表される実際の確率はp / 256である．また，符号化器は2値の復号に8ビット以上の比較を必要とせず，かつ符号化器と復号器は16ビットの符号なし整数値による小さな数値を用いて容易に表現可能であるように，設計されている．
The details are most easily understood if we first describe the algorithm using bit-at-a-time input and output. Aside from the ability to maintain a position in this bitstream and write/read bits, the encoder also needs the ability to add 1 to the bits already output; after writing n bits, adding 1 to the existing output is the same thing as adding pow(2, − n) to x.
一度に1ビットの入力と出力を利用するアルゴリズムを最初に詳述すれば，これらの詳細は非常に簡単に理解される．このビットストリームで位置を管理できることとビットを読み書きできることを脇に置いておいて，符号化器はすでに出力されたビットに1を加算できることもまた必要である．nビットを書いた後，すでに確定した出力に1を加算することは，値xにpow(2,-n)を加算することと全く同じである．
Together with the bit position, the encoder must maintain two unsigned 8-bit numbers which we call bottom and range. Writing w for the n bits already written and S = pow(2, − n − 8) for the scale of the current bit position one byte out, we have the following constraint on all future values v of w (including the final value v = x):
w + (S ⋅ bottom) ≤ v < w + (S ⋅ (bottom + range))
Thus, appending bottom to the already-written bits w gives the left endpoint of the interval of possible values, appending bottom+range gives the right endpoint, range itself (scaled to the current output position) is the length of the interval.
ビット位置と一緒に，符号化器は下の値と範囲と呼ばれる二つの符号なし8ビット数値を管理しなければならない．すでに書かれているnビットの値をwに書き，1バイトの中の現在位置にスケール変換する係数をS = pow(2, − n − 8)として，wの全ての特徴値v（最終的な値v = xを含む）に以下の制約を与える．
w + (S ⋅ bottom) ≤ v < w + (S ⋅ (bottom + range))
したがって，下の値をすでに書かれたビットwに加算することは取り得る値の範囲の左側端点を与え，下の値＋範囲を加算することは右側端点を与え，（現在の出力位置にスケール変換された）範囲そのものは間隔の長さである．
So that our probabilistic encodings are reasonably accurate, we do not let range vary by more than a factor of two: It stays within the bounds 128 ≤ range ≤ 255.
確率値符号化が実用的な精度であるために，2倍より広い範囲で変化させない．すなわち，128 ≤ range ≤ 255という範囲内にする．
The process for encoding a boolean value val whose probability of being zero is prob/256 ― and whose probability of being one is
256 − prob/256 ― with 1 ≤ prob ≤ 255 is as follows.
2値valが0になる確率がprob/256，すなわち1になる確率は(256-prob)/256として，1 ≤ prob ≤ 255であるときvalを符号化するための処理は以下の通りである．
Using an unsigned 16-bit multiply followed by an unsigned right shift, we calculate an unsigned 8-bit split value:
split = 1 + (((range − 1) ⋅ probability >> 8)
split is approximately (prob / 256 ) ⋅ range and lies within the bounds 1 ≤ split ≤ range − 1. These bounds ensure the correctness of the decoding procedure described below.
以下のような符号なし右シフトによる符号なし16ビット乗算を用いて，符号なし8ビット分割値を算出する
split = 1 + (((range − 1) ⋅ probability >> 8)
分割値splitは大体prob/256*rangeであり，1 ≤ split ≤ range - 1の範囲内に存在する．この境界は以下に記述する復号処理の正当性を保証する．
If val is false, we leave the left interval endpoint bottom alone and reduce range, replacing it by split. If val is true, we move up the left endpoint to bottom+split , propagating any carry to the already-written value w (this is where we need the ability to add 1 to w), and reduce range to range−split .
もしvalが偽であれば，左側端点である下の値をそのままにして，範囲を狭くする，すなわち範囲を分割値で置き換える．もし，valが真ならば，左側端点を下の値＋分割値に移動させ，任意の桁上がりをすでに書き込まれた値wに伝搬させ，範囲を範囲-分割値に削減する．
Regardless of the value encoded, range has been reduced and now has the bounds 1 ≤ range ≤ 254. If range < 128, the encoder doubles it and shifts the high-order bit out of bottom to the output as it also doubles bottom, repeating this process one bit at a time until 128 ≤ range ≤ 255. Once this is completed, the encoder is ready to accept another bool, maintaining the constraints described above.
符号化された値によらず，範囲は狭められ，1 ≤ range ≤ 254の範囲になる．range < 128になれば，符号化器は範囲を2倍にして，下の値の中から外へ高次元ビットをシフトし，同様に下の値も2倍にして，128 ≤ range ≤ 255になるまでこの処理を1ビットごとに繰り返す．これが完了すると，上記に記述した制約を維持しながら，符号化器はあらたな真偽値を受理できるようになる．
After encoding the last bool, the partition may be completed by appending bottom to the bitstream.
最後の真偽値が符号化された後，下の値をビットストリームに追加することで区分は完了させられるだろう．
The decoder mimics the state of the encoder. It maintains, together with an input bit position, two unsigned 8-bit numbers, a range identical to that maintained by the encoder and a value. Decoding one bool at a time, the decoder (in effect) tracks the same left interval endpoint as does the encoder and subtracts it from the remaining input. Appending the unread portion of the bitstream to the 8-bit value gives the difference between the actual value encoded and the known left endpoint.
復号器は符号化器の状態をまねる．入力ビット位置と共に，二つの符号なし8ビット数値，すなわち符号化器によって維持されていたのと同一の範囲と値を保存する．一度に1ビットを復号するとき，復号器は同様に左側の端点を追跡するし，残りの入力からそれを減算する．ビットストリームの読めない部分を8ビット値へ追加することは，符号化された実際の値と既知の左端点に違いを与える．
The decoder is initialized by setting range = 255 and reading the first 16 input bits into value. The decoder maintains range and calculates split in exactly the same way as does the encoder.
復号器はrange = 255を設定することで初期化され，最初の16ビットを値として読み込む．復号器は範囲を保持し，符号化器が行ったのと同様の方法で分割点を計算する．
