JIS X 6134:1997 情報交換用データ圧縮　２進算術符号化アルゴリズム

X 6134 : 1997 (ISO/IEC 12042 : 1993)

まえがき

  この規格は,工業標準化法に基づいて,日本工業標準調査会の審議を経て,通商産業大臣が制定した日
本工業規格である。
  この規格の一部が,技術的性質をもつ特許権,出願公開後の特許出願,実用新案権,又は出願公開後の
実用新案登録出願に抵触する可能性があることに注意を喚起する。主務大臣及び日本工業標準調査会は,
このような技術的性質をもつ特許権,出願公開後の特許出願,実用新案権,又は出願公開後の実用新案登
録出願にかかわる確認について,責任はもたない。
  JIS X 6134には,次に示す附属書がある。
    附属書A(参考) 2進算術符号化アルゴリズムの例

(pdf 一覧ページ番号 )

――――― [JIS X 6134 pdf 1] ―――――

                                                     X 6134 : 1997X 6134 : 1997 (ISO/IEC 12042 : 1993)

pdf 目次

ページ

•  1. 適用範囲・・・・[1]
•  2. 引用規格・・・・[1]
•  3. 適合性・・・・[1]
•  4. 表記法・・・・[1]
•  5. アルゴリズムの識別子・・・・[1]
•  6. 用語の定義・・・・[1]
•  6.1 ブロック・・・・[2]
•  6.2 符号化ブロック・・・・[2]
•  6.3 符号列・・・・[2]
•  6.4 符号化・・・・[2]
•  6.5 入力事象・・・・[2]
•  6.6 論理データレコード・・・・[2]
•  6.7 トレーラ・・・・[2]
•  6.8 固有テーブルペア・・・・[2]
•  7. 略号・・・・[2]
•  8. 圧縮アルゴリズム・・・・[2]
•  8.1 概要・・・・[2]
•  8.2 符号生成器・・・・[2]
•  8.3 符号化ブロックの構成・・・・[2]
•  8.4 符号列・・・・[3]
•  8.5 テーブルペア・・・・[3]
•  8.6 符号化・・・・[3]
•  8.6.1 ノーマルモード・・・・[3]
•  8.6.2 ランモード・・・・[5]
•  8.7 ブロックの符号化の完了・・・・[5]
•  附属書A(参考) 2進算術符号化アルゴリズムの例・・・・[9]

(pdf 一覧ページ番号 )

――――― [JIS X 6134 pdf 2] ―――――

                                       日本工業規格(日本産業規格)                             JIS
                                                                            X 6134 : 1997
                                                                       (ISO/IEC 12042 : 1993)

情報交換用データ圧縮2進算術符号化アルゴリズム

Information technology−Data compression forinformation interchange−Binary arithmeticcoding algorithm

序文 この規格は,1993年初版として発行されたISO/IEC 12042 (Information technology−Data compression
for information interchange−Binary arithmetic coding algorithm) を翻訳し,技術的内容及び規格票の様式を変
更することなく作成した日本工業規格(日本産業規格)である。

1. 適用範囲

 この規格は,情報を表現するビット数を削減するデータ圧縮の2進算術符号化アルゴリズ
ムについて規定する。このアルゴリズムは,ロスレス圧縮の情報交換で使用する。

2. 引用規格

 次の規格は,この規格がよりどころとしている規格を含んでいる。出版時に明示された版
号が有効であるが,すべての規格は改正されるので,この規格の関係者は,次の最新のものを調査し適用
するよう推奨する。
    ISO/IEC 11576 : 1994 Information technology−Procedure for the registration of algorithms for the loseless
        compression of data
  データのロスレス圧縮アルゴリズムは,ISO/IEC 11576に従って登録する。

3. 適合性

 圧縮アルゴリズムは,この規格のすべての要求を満たすとき,この規格に適合する。

4. 表記法

 表記法は,特に指定がない限り,次による。
− 各フィールドのバイトは,バイト1を最上位として最初に配列する。各バイトのビットは,ビット1
    を最上位として最初に,ビット8を最下位として最後に配列する。
− 16進数は,丸括弧内に数字及び文字AFで表す。
− ビットは,“0”又は“1”で表す。
− 2進数表記の数字及びビットの組合せは,“0”及び“1”の列で表す。
− 2進数表記の数字及びビットの組合せは,最上位ビットを左とする。

5. アルゴリズムの識別子

 ここで規定するアルゴリズムの識別子は,“16”とする。

6. 用語の定義

 この規格で用いる用語の定義は,次による。

――――― [JIS X 6134 pdf 3] ―――――

2
X 6134 : 1997 (ISO/IEC 12042 : 1993)

6.1 ブロック

 (block)通常512バイト長(8.2参照)をもつ論理データレコード (LDR) の一部。

6.2 符号化ブロック

 (Code Block)  圧縮後トレーラを付加したブロック。

6.3 符号列

 (Code String)  符号化済みの論理データレコード。

6.4 符号化

 (encoding)  ブロック符号から符号化ブロックを生成する方法。

6.5 入力事象

 (input event)  検索中の符号生成器への入力。ランモードではバイト単位,ノーマルモー
ドではビット単位とする。

6.6 論理データレコード

 (Logical Data Record)データ圧縮器への入力データ。
6.7                    圧縮及びパッドビットを付加後のブロックへの追加データ。
      トレーラ (trailer)

6.8 固有テーブルペア

 (Unique Table Pair) ランモードだけに使用する256個のテーブルペアの最後。

7. 略号

  CV           現在値 (Current Value)
  EV           予測値 (Estimated Value)
  LDR          論理データレコード (Logical Data Record)
  TP           テーブルペア (Table Pair)

8. 圧縮アルゴリズム

8.1 概要

 LDRをロスレスデータ圧縮によって1パスで符号列に変換する。適切な復元方法を用いて符
号列から元のLDRに復元する。

8.2 符号生成器

 LDRは,最後のブロックを除き512バイトのブロックに分割し,最後のブロックは,
512バイト以下とする。ブロックは,0から7の番号をもつ8個の符号生成器に符号生成器0から順番に入
力する。LDRが4096バイト以上の場合,符号生成器0に戻り,圧縮操作を繰り返す(図2参照)。

8.3 符号化ブロックの構成

 各符号生成器の出力は,1個の符号化ブロックからなる(図1参照)。
              圧縮ブロック   パッドビット   トレーラ   トレーラ   パッドバイト
                             (最終データの バイト1    バイト2     (00)
                             場合)                               (バイトカウント
                                                                   が奇数のとき)
                                      図1 符号化ブロック
  符号生成器での圧縮度は,LDRのビットパターン及び同一バイトの出現頻度に依存しており,圧縮後の
ブロックの長さは,予測できない。パッドビットは,8ビットバイトの整数倍とするために,最後に付加
し,0を設定する。符号化ブロックは,トレーラを付加し完成する。トレーラは,2個のトレーラバイトと
それに続くパッドバイトで構成する。
  トレーラバイト1 (FF) を設定する。
  トレーラバイト2
    ビット14 LDRの最後のブロックから生成した符号化ブロックの場合,“1100”を設定する。
                 他のすべての符号化ブロックの場合,“1001”を設定する。
    ビット5      符号化のバイト数が偶数の場合,“0”を設定する。
                 符号化のバイト数が奇数の場合,“1”を設定する。
    ビット68 バイトの整数倍とするために追加したパッドビット数を設定する。
  パッドビットを加えた圧縮ブロックの中のバイト数が奇数の場合,バイト数を偶数にするため (00) の

――――― [JIS X 6134 pdf 4] ―――――

                                                                                              3
                                                                X 6134 : 1997 (ISO/IEC 12042 : 1993)
パッドバイトをトレーラバイト2の後に付加する。

8.4 符号列

 符号列は,符号生成器の出力からなり,符号列の1番目は符号生成器0の出力,符号列の2
番目は符号生成器1の出力と,この順番で生成する(図2参照)。

8.5 テーブルペア

 テーブルペアは,各符号生成器の1から256までの番号を付けた256個の対のテー
ブルとする。各テーブルペア (TP) の最初の数字は,符号化する入力事象のEVを示し,“1”又は“0”の
値とする。次の数字Kは,EVと等しい入力事象の出現確率を示し,表1に示す1,2,3,4の値とする。
                                      表1 Kの確率の数値
                                         K        確率
                                         1       1 2
                                         2       2 4
                                         3       4 8
                                         4       816
  確率は,入力事象の値がEVと等しいことを示す(例えば,K=2の場合,入力事象がEVと等しい確率
は,EVと等しくない確率の24倍である。)。
  LDRの符号化開始時,すべてのEVを“0”に設定し,すべてのKの値を“1”に設定する。

8.6 符号化

 最初にデータは,バイト単位で検索しなければならない。バイトは,ブロックの最初のバ
イトから順番に取り出し,前のバイトと比較する。ブロックの最初のバイトは, (40) と比較する。
  ランモード(8.6.2参照)は,最初のバイトを取り出すと停止する。
  検索したバイトが前のバイトと相違し,モードがランモードでない場合,そのバイトをノーマルモード
でビットごとに符号化する(8.6.1参照)。
  検索したバイトが前のバイトと相違し,モードがランモードの場合,そのバイトの符号化は,8.6.2.2に
よる。
  二つのバイトが等しく,モードがランモードでない場合,ランモードを作動し,そのバイトは,ノーマ
ルモードでビットごとに符号化する。
  二つのバイトが等しく,モードがランモードの場合,そのバイトの符号化は,8.6.2.1による。

8.6.1 ノーマルモード

 バイトの最初(最上位)のビットを最初のTPのEVと比較し,その結果から8.6.1.1
の二つの動作の一つを実行する。残りのビットに対してどのTPを使用するかは,そのバイトの先に符号
化したビットの内容によって決める。
  各バイトの最初のビットは,常に最初のTPを使用する。
  2ビット目は,最初のビットが“0”か“1”かによって,2番目又は3番目のTPを使用する。
  3ビット目は,最初の2ビットの情報によって4個のTPの1個を使用する。最初の2ビットが“00”の
場合4番目のTPを使用し,その他の場合は別のTPを使用する(図3参照)。
  1バイトに255個のTPを用い,残り一つを固有TPとし,ランモードだけに使用する(8.6.2参照)。
  符号化は,次の2段階で行う。
− ビットは,8.6.1.1によって符号化する。
− KとEVの値は,8.6.1.2によって更新する。
8.6.1.1  ビットの符号化 2進数表示の二つの小数4けたの数値は,圧縮処理中のビット比較部で生成す
る。一つ目の数値は,現在値 (CV) と呼ぶ数値で,出力(符号化ブロック)の生成に使用する。
  二つ目の数値は,区間幅と呼ぶ数値で,“0.0000”から“1.1111”の範囲とする。
  各ブロックでは,CVを“0.0000”に,区間幅を“1.0000”に初期化する。

――――― [JIS X 6134 pdf 5] ―――――

次のページ PDF 6