サイトトップへこのカテゴリの一覧へ

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

(1) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

まえがき 

この規格は,工業標準化法に基づいて,日本工業標準調査会の審議を経て,通商産業大臣が制定した日

本工業規格である。 

この規格の一部が,技術的性質をもつ特許権,出願公開後の特許出願,実用新案権,又は出願公開後の

実用新案登録出願に抵触する可能性があることに注意を喚起する。通商産業大臣及び日本工業標準調査会

は,このような技術的性質をもつ特許権,出願公開後の特許出願,実用新案権,又は出願公開後の実用新

案登録出願にかかわる確認について,責任はもたない。 

JIS X 6136には,次に示す附属書がある。 

附属書A(参考) ALDC符号化様式 

附属書B(参考) ALDC概要 

附属書C(参考) ALDC符号化法流れ図 

附属書D(参考) 参考文献 

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

(1) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

目次 

ページ 

序文 ··································································································································· 0 

1. 適用範囲 ························································································································ 0 

2. 適合性 ··························································································································· 0 

3. 引用規格 ························································································································ 0 

4. 定義 ······························································································································ 0 

4.1 圧縮データ列 (Compressed Data Stream) ··············································································· 0 

4.2 コピーポインタ (Copy Pointer)  ························································································· 2 

4.3 カレントアドレス (Current Address)···················································································· 2 

4.4 データバイト (Data Byte) ································································································· 2 

4.5 変位領域 (Displacement Field) ···························································································· 2 

4.6 終了マーカ (End Marker) ·································································································· 2 

4.7 履歴バッファ (History Buffer)···························································································· 2 

4.8 生データ (Literal) ··········································································································· 2 

4.9 一致文字列 (Matching String)····························································································· 2 

4.10 一致数 (Match Count) ····································································································· 2 

4.11 一致数領域 (Match Count Field) ························································································ 2 

4.12 パッドビット (Pad Bits) ································································································· 2 

5. 表記法 ··························································································································· 2 

5.1 数字の表し方 ················································································································ 2 

5.2 名称 ···························································································································· 2 

6. ALDC圧縮アルゴリズム ··································································································· 2 

6.1 512−バイト履歴バッファに対する符号化記述 ····································································· 2 

6.2 圧縮データ列の概要 ······································································································· 3 

附属書A(参考) ALDC符号化様式······················································································· 5 

附属書B(参考) ALDC概要 ································································································ 7 

附属書C(参考) ALDC符号化法流れ図 ················································································· 8 

附属書D(参考) 参考文献 ································································································· 12 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

日本工業規格          JIS 

X 6136 : 1999 

(ISO/IEC 15200 : 1996) 

情報交換用データ圧縮− 

適合化無損失アルゴリズム 

(ALDC) 

Information technology−Adaptive Lossless Data Compression algorithm  

(ALDC) 

序文 この規格は,1996年に第1版として発行されたISO/IEC 15200,Information technology−Adaptive 

Lossless Data Compression algorithm (ALDC) を翻訳し,技術的内容及び規格票の様式を変更することなく作

成した日本工業規格である。 

1. 適用範囲 この規格は,データを表現するビット数を削減する無損失データ圧縮について規定する。

このアルゴリズムは,適合化無損失データ圧縮アルゴリズム (ALDC) として知られている。このアルゴリ

ズムのISO/IEC 11576による識別番号は,次のとおりとする。 

ALDC 

  512−バイト履歴バッファ :3 

ALDC 

1 024−バイト履歴バッファ :4 

ALDC 

2 048−バイト履歴バッファ :5 

備考 この規格の対応国際規格を次に示す。 

ISO/IEC 15200 : 1996 Information technology−Adaptive Lossless Data Compression algorithm 

(ALDC)  

2. 適合性 圧縮アルゴリズムは,出力データ列がこの規格の要求を満たすとき,この規格に適合する。 

3. 引用規格 次に掲げる規格は,この規格に引用されることによって,この規格の規定の一部を構成す

る。この引用規格は,その最新版を適用する。 

ISO/IEC 11576 : 1996 Information technology−Procedure for the registration of algorithms for the lossless 

compression of data 

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

4.1 

圧縮データ列 (Compressed Data Stream)  圧縮後の出力データ列。

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

4.2 

コピーポインタ (Copy Pointer)  圧縮データ列の一部。履歴バッファに同一グループが存在するこ

とを示す二つ以上の連続するバイトのグループを表し,レングスコード領域と変位領域からなる。 

4.3 

カレントアドレス (Current Address)  データバイトを書き込む履歴バッファの位置。 

4.4 

データバイト (Data Byte)  履歴バッファに以前に記録したすべてのデータと比較し,履歴バッフ

ァに記録する入力データの現在のバイト。 

4.5 

変位領域 (Displacement Field)  履歴バッファ内の一致データ列の最初のバイトの位置を示すコピ

ーポインタの一部。 

4.6 

終了マーカ (End Marker)  圧縮データ列の終了を示す12個の“1”の連続列。 

4.7 

履歴バッファ (History Buffer)  データの圧縮及び復元に使用する入力データを貯える段階構造。 

4.8 

生データ (Literal)  履歴バッファ内に一致するバイトが存在しないデータバイト。 

4.9 

一致文字列 (Matching String)  履歴バッファ内の連続するバイトと一致する入力データの連続す

るバイト。 

4.10 一致数 (Match Count)  一致文字列のバイト数 

4.11 一致数領域 (Match Count Field)  履歴バッファ内で一致した連続するバイトの数を示すコピーポ

インタの一部。 

4.12 パッドビット (Pad Bits)  8ビットバイトを構成するために,必要に応じて圧縮データ列に挿入す

る“0”のビット。 

5. 表記法 

5.1 

数字の表し方 数字の表し方は,特に指定のない限り,次による。 

− ビットの設定は,“0”又は“1”で表す。 

− 2進数表記の数字及びビットの組合せは,“0”及び“1”の列で表し,最上位ビットを左とする。 

− その他の数字は,10進数とする。 

5.2 

名称 エンティティの名称は,規定しない。 

6. ALDC圧縮アルゴリズム ALDC符号化手順の概要は,附属書Bとし,流れ図は,附属書Cによる。 

6.1 

512−バイト履歴バッファに対する符号化記述 符号化を開始するとき,履歴バッファ内のすべての

バイトを“0”に設定する。符号化が開始されるとデータバイトを,カレントアドレス0から履歴バッファ

に順次格納する。 

符号器は,入力データを1バイトごとに処理し,処理中の現在のバイトを,データバイトとして参照す

る。符号器はデータバイトを,入力データ列から受け取り,履歴バッファのカレントアドレスに書き込み,

カレントアドレスを1増加する。カレントアドレスが512バイトの履歴バッファの最大アドレスである511

を超えたとき,カレントアドレスを“0”に設定する。 

ステップ1 

符号器は,一致するバイトを見つけるため,履歴バッファ内に既に書き込んだ各バイト

とデータバイトを比較する。 

ステップ2 

データバイトが履歴バッファ内に既に書き込んだバイトと一致しないとき,処理はステ

ップ6に進む。 

− データバイトが履歴バッファ内の1バイト以上のバイトと一致するとき,すべての

一致バイトについて,それ以前の一致バイト列からの連続であるか否かを注視する。 

− 連続でないとき,一致バイトの変位領域の値と1バイトの一致数があったことを記

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

録する。 

− 一致バイトが以前の文字列の連続であるとき,その列の一致数を1だけ増加する。 

ステップ3 

一致数が271に達したとき,対応しているバイト列をコピーポインタで識別し,コピー

ポインタを圧縮データ列に追加する。一致数領域と変位領域の記述方法は,6.2による。

次のデータバイトを読み取り,その処理はステップ1へ戻る。読み取るデータがないと

き,処理はステップ7に進む。 

参考 271の値は,実装上の理由によって選択している。 

ステップ4 

一致数が271に達しないとき,保留の一致文字列に継続するデータバイトがあるか否か

を検査する。 

− 以前のどの一致文字列にも連続せず,かつ,2バイト以上で構成する一致文字列が

あるとき,最小値をもつ変位領域の一致文字列をコピーポインタによって識別し,

コピーポインタを圧縮データ列に追加する。次のデータバイトを読み取る。読み取

るデータがないとき,ステップ7に進む。 

− 以前の一致文字に連続せず,かつ,一致が1バイトだけのとき,それ以前の1バイ

トの一致を生データとして6.2によって圧縮データ列に追加する。次のデータバイ

トを読み取る。読み取るデータがないとき,処理はステップ7に進む。 

ステップ5 

一致数が271に達する一致文字列がなく,かつ,以前の一致文字列との連続が少なくと

も一つあるとき,次のデータバイトを読み取る。処理は,ステップ1に戻る。 

読み取るデータがないとき,その時点で保留の文字列はコピーポインタで識別し,圧縮

データ列に追加する。処理は,ステップ7に進む。 

ステップ6 

データバイトが履歴バッファ内のいずれのバイトとも一致しないとき,それ以前の保留

文字列に対して検査を行う。 

2バイト以上,以前に一致文字列があるとき,それらをコピーポインタで識別し,圧縮

データ列に追加する。一致しないデータバイトは,生データとして圧縮データ列に追加

する。次のデータを読み取り,処理はステップ1に戻る。 

読み取るデータがないとき,処理はステップ7に進む。 

2バイト以上の一致文字列で保留がなく,かつ,1バイト一致の保留があるとき,データ

バイトに先立つバイトは,生データとして圧縮データ列に追加する。一致を検出できな

かったデータバイトは,生データとして圧縮データ列へ追加する。次のデータバイトを

読み取り,処理はステップ1に戻る。 

読み取るデータがないとき,処理はステップ7に進む。 

ステップ7 

終了マーカを圧縮データ列に追加し,必要によってパッドビットを追加する。 

この処理によって符号化処理を終了する。 

6.2 

圧縮データ列の概要 6.1の入力データの処理によって,圧縮データ列を出力する。圧縮データ列の

構成は,次による。 

− “0”のビットを前置きした生データ 

− “1”のビットを前置きしたコピーポインタ 

− “1”のビットを前置きした終了マーカ 

− パッドビット 

すべてのデータを読み取ったとき,圧縮したデータ列は,“1”のビットを設定し,終了しなければなら

background image

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

ない。その列は終了マーカ及び必要によってパッドビットが続く。 

符号化の間に,同じ一致数の一致データ列を一つ以上検出した場合,最下位の変位領域をもったコピー

ポインタを使用しなければならない。一致数領域は,2ビット,4ビット,6ビット,8ビット又は12ビッ

トとし,表1で規定する。512バイト,1 024バイト又は2 048バイトの履歴バッファに対し,変位領域の

長さは,それぞれ9ビット,10ビット又は11ビットとする。 

表1 一致数領域 

一致数領域の設定 

バイトの数 

00 

01 

10 00 

10 11 

110 000 

110 111 

15 

1110 0000 

16 

1110 1111 

31 

1111 0000 0000 

32 

1111 1110 1110 

270 

1111 1110 1111 

271 

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

附属書A(参考) ALDC符号化様式 

この附属書(参考)は,本体に関連する事柄を補足するもので,規定の一部ではない。 

A.1 命名法 圧縮データの符号化様式は,BNF記法(バッカスナウア記法)で記述する。 

記号の定義は,次による。 

記 号 

定  義 

:= 

この記号の左側の非終端変数は,右側の表現で置き換えることができる。 

< > 

非終端変数 

[ ] 

括弧内の表現は,0回又はそれ以上の回数出現する。 

| 

論理的分離OR 

( ) 

説明文 

0,  1 

終端2進数“0”又は“1” 

A.2 ALDC_1アルゴリズム−符号化様式(512−バイト履歴バッファ) 

<圧縮データ>:=0<生データ>[0<生データ>|1<コピーポインタ>]|<終了マーカ><パッ

ド> 

<生データ>:=<b><b><b><b><b><b><b><b>(8ビットバイトデータ) 

<b>:=0|1 

<コピーポインタ>:=<一致数領域><変位領域> 

<一致数領域>:=(2,4,6,8又は12ビット) 

一致数領域の設定 

バイト中の一致数 

00 

01 

10 00 

: 

: 

: 

: 

10 11 

110 000 

: 

: 

: 

: 

110 111 

15 

1110 0000 

16 

: 

: 

: 

: 

1110 1111 

31 

1111 0000 0000 

32 

: 

: 

: 

: 

1111 1110 1110 

270 

1111 1110 1111 

271 

<変位領域>:=<b><b><b><b><b><b><b><b><b>(9ビット) 

<パッド>:=8ビットの境界を維持するために必要な“0”に設定するビット数 

<終了マーカ>:=1111 1111 1111 

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

A.3 ALDC_2アルゴリズム−符号化様式(1 024−バイト履歴バッファ) 

(変位領域が10ビットであることを除いてALDC_1の定義と同一) 

〈変位領域〉:=<b><b><b><b><b><b><b><b><b><b>(10ビット) 

A.4 ALDC_4アルゴリズム−符号化様式(2 048−バイト履歴バッファ) 

(変位領域が11ビットであることを除いてALDC_1の定義と同一) 

〈変位領域〉:=<b><b><b><b><b><b><b><b><b><b><b>(11ビット) 

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

附属書B(参考) ALDC概要 

この附属書(参考)は,本体に関連する事柄を補足するもので,規定の一部ではない。 

ALDCアルゴリズムは,8ビットデータバイトの入力を受け,圧縮形式でデータを表現するビット列を

出力する。ALDCアルゴリズムは,データ圧縮アルゴリズムLempel−Ziv1 (LZ1) の一つの手法である。 

LZ1アルゴリズムは,データを貯える段階構造をもつ履歴バッファを使用して圧縮を行う。履歴バッフ

ァは,入力データの格納及び入力データと同一履歴バッファ内の以前のすべてのデータとの比較を行う。

LZ1の符号化過程と復元化過程では,このデータ構造を同一の既知状態に初期化し,同一方法で更新する。

その結果,二つの履歴が同一になり,圧縮データ列に履歴情報を含む必要がない。 

入力データは,履歴バッファに入る。履歴バッファ内に以前に格納した他のすべてのバイトと各々の入

力バイトを比較する。以前の一致文字列の続きの一致を見つけることによって,圧縮を行う。符号化過程

の最初に履歴バッファは,空になる。履歴バッファ内でいずれの一致も見つけられない場合,圧縮データ

列は,生データだけとする。バイトは,2バイト以上の一致がおきるまで,生データとして符号化する。

履歴バッファにデータが蓄積すると,入力データを履歴バッファに存在するデータ列のコピーポインタと

して符号化表現する可能性が増加する。これが,LZ1アルゴリズムでデータを圧縮する原理となる。 

background image

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

附属書C(参考) ALDC符号化法流れ図 

この附属書(参考)は,本体に関連する事柄を補足するもので,規定の一部ではない。 

background image

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

background image

10 

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

background image

11 

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

12 

X 6136 : 1999 (ISO/IEC 15200 : 1996) 

2019年7月1日の法改正により名称が変わりました。まえがきを除き,本規格中の「日本工業規格」を「日本産業規格」に読み替えてください。 

附属書D(参考) 参考文献 

この附属書(参考)は,本体に関連する参考文献を記載するもので,規定の一部ではない。 

J. Ziv and A. Lempel, “A universal algorithm for sequential data compression”, IEEE Trans. Inform. Theory,  

vol. IT-23, no.3, pp.337-343, 1997.  

磁気テープJIS原案作成委員会 構成表 

氏名 

所属 

(委員長) 

大 石 完 一 

パルステック工業株式会社 

(幹事) 

富 田 正 典 

日本システムインテグレーション株式会社 

(幹事) 

徳 永 賢 次 

イメーション株式会社 

平 川   卓 

富士写真フイルム株式会社 

村 上 恒 夫 

日本システムハウス株式会社 

荒 木   学 

日本ユニシス株式会社 

樋 口 重 光 

株式会社日立製作所 

安 藤 晴 夫 

日立マクセル株式会社 

竹 内   正 

株式会社トリム 

船 越 正 次 

TDK株式会社 

金 子   悟 

富士通株式会社 

堀 川 憲 一 

ソニー株式会社 

藤 原 圭 介 

ソニー株式会社 

川 田 道 孝 

日本電気株式会社 

岸 野 忠 信 

財団法人日本規格協会 

永 松 荘 一 

通商産業省機械情報産業局 

兼 松 明 男 

通商産業省工業技術院標準部 

(オブザーバー) 

橋 本 繁 晴 

財団法人日本規格協会 

(オブザーバー) 

中 島 敏 明 

財団法人日本電子部品信頼性センター 

(事務局) 

長谷川 久 子 

社団法人日本電子工業振興協会