JPS63123232A - 単一ビットの誤り検出方法とそれを用いた算術デコ−ダ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

Ａ、産業上の利用分野 Ｂ、従来技術 Ｃ０発明が解決しようとする問題点 り８問題点を解決するための手段 Ｅ、実施例 Ｅｌ　従来のエンコーダ、デコーダ及び関連装置（第２
図） Ｃ２従来の圧縮エンコーダの詳細（第３図）Ｒ３本発明
の誤りエンコーダ（第１図）Ｒ４直列テスタ（第４、第
５及び第７図）Ｒ５本発明のデコーダ（第６図） Ｆ８発明の効果 Ａ、産業上の利用分野 本発明は半開コーディング値域〔０、１）中の数として
具体化される算術データ圧縮コード・ストリングＣ（ｓ
）中に生ずる単一ビット誤りを検出する方法に関する。

このコード・ストリームＣ（ｓ）は算術帰納関数に従っ
て計算されるものである。さらに具体的には本発明はコ
ード・チャネル中に導入される算術エンコーダもしくは
算術デコーダによって発生される単一ビット誤りを検出
する方法に関する。

Ｂ、従来技術 算術圧縮コードは従来技術として確立されているが、２
進ソースの場合については、１９８２年９月刊情報理論
についてのＩＥＥＥ論文集、第ＩＴ−２９巻、第５号ラ
ングトン及びリサネン著「簡単な一般２進ソース・コー
ドＪ　　（Ｌａｎｇｄｏｎａｎｄ　Ｒ１５ｓａｎｅｎ、
“Ａ　Ｓｉｍｐｌｅ　Ｇｅｎｅｒａｌ　ＢｉｎａｒｙＳ
ｏｕｒｃｅ　Ｃｏｄｅ”ＩＥＥＥ　Ｔｒａｎｓａｃｔｉ
ｏｎｓ　Ｏｎ　ＩｎｆｏｒｍａｔｉｏｎＴｈｅｏｒｙ、
Ｖｏｌｕｍｅ　ＩＴ−２９，Ｎｏ、５，５ｅｐｔｅ＋ａ
ｐｅｒ　１９８２）を参照することによって理解されよ
う。次の米国特許によって算術データ圧縮コードの発展
をたどることができる。米国特許第４１２２４４０号、
第４２８６２５６号、第４２９５１２５号、第４４６７
３１７号。これ等の文献は一般に演算圧縮コーディング
の理論に関し、２進アルフアベツトから引出される未コ
ード化データ・ストリームに対して操作を加えるのに有
用なエンコーダの多くの実施例を与えている。

米国特許第４４６７３１７号に開示されている様に、高
速算術データ圧縮コードは未コード化データ・ストリン
グＳに応答してこれ迄に発生したコード・ストリングＣ
（ｓ）の有効端に帰納的に被加数を加える順次過程であ
る。この特許に述べられているように、コード化過程は
ストリングの統計によって与えられるコード化パラメー
タに依存する。従来そうであったように、この特許の発
明者もモデリング過程が十分理解されたものとして、コ
ーディングの過程にのみ関心を向けている。

算術データ圧縮コーディングは半閉コーディング値域〔
０、１）に含まれる数である算術コード・ストリームＣ
（３）を発生する。一般的な場合は、ソース・ストリン
グＳはｍ進記号より成る。エンコードさるべき、Ｓ中の
次の記号ｉ　　（ｂ　（ｉ）　）に先行するＳの部分の
確率に依存する結合確率を有する。ストリングＳの終り
に向かってさらにｉが発生するにつれ、その結合確立は
減少する。算術コード化過程は利用可能なコード化値域
を相継いで細分割することによってｉの結合確率のこの
減衰を効果的に反映する。すでにエンコードされたｉに
先行するストリングＳの部分に対応する値域の部分区間
はこの値域中に位置する下界Ｃ（ｓ）及び部分区間の寸
法を決める値Ａ　（ｓ）によって決定される。従って、
ｉをエンコードするために利用可能なコーディング値域
の部分に対応する部分区間は（Ｃ（ｓ）　、　Ｃ（ｓ）
　＋Ａ　（ｓ）　）によって表わされる。

次の記号ｉがエンコードされる帰納関数の周期中に１部
分区間の大きさＡ　（ｓ）はソース記号の数と同数の部
分に細分割され、各部分の大きさは表わされるソース記
号の条件付き確率に対応するようにされる。次の記号ｉ
をエンコードするためにＣ（ｓ）に加えられる値である
被加数はソース・アルファベット中のｉに先行する記号
の条件付き確率の大きさの和である。このことは勿論、
ソース、アルファベットにはある予じめ定まった規則が
与えら九でいることを意味する。米国特許第４４６７３
１７号の２進ソース・コード構造では、この任意の規則
は、ＬＰＳ　（最小確率記号）そしてＭＰＳ　（最大確
率記号）である。

次の記号ｉをエンコードする目的のためのＡ（ｓ）の細
分割には現在の区間の大きさＡ　（ｓ）をソース・アル
ファベット中の記号と同数の部分に分割することを必要
とする。従来技術では、細分割の大きさはソース・モデ
ルよって与えられる制御パラメータｋに従って近似され
る。２進ソース・アルファベットの場合には、２つの大
きさがＡ（ｓ）の細分割から生ずる。１つはＭＰＳに割
当てられるものであり、他はＬＰＳに割当てられるもの
である。従来技術の細分割動作は次の特定の大きさを生
じ、 大きさ１：Ａ　（ｓ）　　・　（１−２ｋ）　　　（ｌ
ａ）大きさ２：Ａ　（ｓ）−ｆｆｋ　　　　　（ｌｂ）
これから次の部分区間コーディングを生じた。

ＬＰＳの場合。

〔Ｃ（５）、ＣＣ５）十大きさ１）　　　　（２ａ）Ｍ
ＰＳの場合、 ＥＣ（Ｓ）十大きさ１、Ｃ（ｓ）十大きさ２〕（２ｂ） ＭＰＳの場合には、部分区間構造を眺めることによって
、被加数である大きさ１がＣ（ｓ）加えられて、新らし
い下界が形成されることが明らかであろう。

式（２ａ）及び（２ｂ）はコーディングのステップがス
トリングＳ中の各記号に応答して行われるという意味で
算術エンコーダの動作が順序的であることを暗に示して
いる。さらにこの手順は結果のコード・ストリング値Ｃ
（ｓ）及び現在の部分区間の大きさＡ（ｓ）が各ステッ
プ毎に前のステップの終りの夫々の値によって決定され
る値に修正されるという意味で帰納的である。

２進アルフアベツトのための従来技術の算術データ圧縮
コーディングの帰納は次のように行われる。

各ＭＰＳの場合、 ｋ Ｃ（ｓ−ＭＰＳ）＝Ｃ（ｓ）＋２　　　　　（３ａ）ｋ Ａ　（ｓ−ＭＰＳ）＝Ａ　（ｓ）−２（３ｂ）各ＬＰＳ
の場合、 Ｃ（ｓ−ＬＰＳ）＝Ｃ（ｓ）　　　　　　　（３ｃ）Ａ
　（ｓ−ＬＰＳ）＝２：ｋ　　　　　　　（３ｄ）この
従来技術では、デコーディングはコード・ストリングＣ
（ｓ）の最上位部の大きさを帰納的に調べ、現在の被加
数がコード・ストリングの残りの数値を越えるかどうか
を決定することを含む。

各検査は被加数を試験的にコード・ストリングから減算
する試行減算を含む。もし試行の結果が負ならば、減算
は無効であり、現在の記号はＬＰＳとしてデコードされ
、そうでない時は、減算結果は有効であり、記号はＭＰ
Ｓとしてデコードされる。

ストリングＳを圧縮及び伸張するためのアルゴリズムは
Ｃ（ｓ）を発生するため及びデコード・ストリングＳを
復元するための２進算術の実行を含む。よく知られてい
るように、帰納式３（ａ）−３（ｄ）に従ってエンコー
ド及びデコードに使用される手順は高エントロピー・コ
ード・ストリングを生じ、このストリングはランダム誤
りが生じたかどうかを推論する証拠を与えない０通常の
動作環境中において、エンコードされたデータ・ストリ
ームは誤リソースの影響を受けその情報内容が破壊され
ることが予想されるので、情報の完全性を保護する手段
を与えることが必要である。

算術エンコーダ、算術デコーダ及び算術コード・ストリ
ングが転送されるチャネル内で発生する可能性のある誤
りを検出する１つの手段は“ＡＮ″算術誤りコーディン
グとして提案されている。

“ＡＮ”算術誤りコーディングは第１の整数Ｎに第２の
定数の整数Ａを乗算することによって第１の整数をエン
コードし、その冗長性を増大して誤りを防止する技術で
ある。第１の整数のＡＮ表示を第２の整数で除算して調
べて、除算の結果、余りが０にならない時は、第１の整
数中の誤りが明らかになる、単一の誤りの検出を与える
ためには第２の整数Ａは１に等しくない奇数でなければ
ならない、算術圧縮コーディングで従来使用していた記
号Ａとの混同を避けるために、ＡＮ算術誤りコーディン
グで通常Ａと呼ばれている整数の乗数因子を表示するの
に記号ｎを以下使用することにする。２進数でコード・
ストリームを記述する時の２進小数点の位置については
次のようにこの分野で確率されている約束を使用するも
のとする。

（１）算術圧縮コーディングの場合には、２進小数点は
コード・ストリームの最上位ビットの左側に置＜、（２
）算術誤りコードの場合には、２進小数点はコード・ス
トリームの最下位ビットの右側に置く。

Ｃ０発明が解決しようとする問題点 本発明の目的は、算術データ圧縮コーディングによって
発生するコード・ストリング内の誤りを検出する方法及
び装置を与えることにある。

本発明の他の目的は、算術的エンコーディングの技術を
使用して上記目的の誤りを検出する方法及び装置を与え
ることにある。

Ｄ０問題点を解決するための手段 本発明によって解決される技術的困難は算術的に圧縮さ
れたコード・ストリングの２進表示中のデータの完全性
が、コーディング及びデコーディング過程中でも保護さ
れる点にある。この問題はストリングのコーディング、
転送及びデコーディングのすべての重要な点で算術的に
圧縮されたストリングの完全性を評価する事にある。デ
ータの算術圧縮を必要とするシステムのアーキテクチャ
−では、評価はコーグ及びデコーダのみならず、これ等
の間の転送チャネルを含むすべてのコード・データ・ス
トリーム経路の部分の誤りを検出するシステムの能力に
関連してしばしば表現される。

本発明はこの能力をコード・ストリングを完全に伸張す
ることなく与える。この誤り検出能力は極めて低コスト
で算術エンコード・ストリームのビットの数を１乃至２
ビツト増大するだけである。

手順及び追加の実施ハードウェアが簡単なことにより、
本発明の意義が増強され、追加のコストは相対的にわず
かである。

本発明はｍ進記号ストリングＳの帰納的機械エンコーデ
ィング中にＳの表現として圧縮２進数Ｃ（ｓ）を発生す
る間に単一ビット誤りを検出する方法として理解される
。Ｃ（ｓ）は半開区間〔０、１）中の数であり、この区
間は相継ぐエンコーディング・サイクル中に相継いで細
分割される。各部分区間はその下界Ｃ（ｓ）とコーディ
ング変数Ａ　（ｓ）によって（Ｃ（ｓ）　、　Ｃ（ｓ）
　＋Ａ　（ｓ）　）として定義される。　Ｃ（ｓ）及び
Ａ　（ｓ）は夫々Ｃ（ｓ）及びＡ　（ｓ）の算術帰納関
数として計算される。その方法は次のステップによって
表わされる。算術帰納関数をｎ（倍）だけスケーリング
（位取り）する、ｎは＋１もしくは−１に等しくない奇
数である０次にＳをｎだけスケーリングした算術帰納関
数に従って圧縮２進表現Ｃ’　　（ｓ）にする＃Ｃ’（
ｓ）をモジュロｎ関数によって余りが非０であるかどう
かをテストする。

本発明は、算術的エンコーディングの方法が半開コーデ
ィング値域［０，１）上で演算が定義された帰納関数を
含むという重要な発見にもとづく。

算術誤りコーディングは整数オペランドと第２の一定整
数との順次的乗算を基本的に含むので、誤りコーディン
グ動作の挿入は帰納的算術圧縮関数の順次遂行と同期で
きる。さらに本発明の誤りコーディングは１に等しくな
いすべての奇数の集合から任意の一定整数ｎを自由に選
択できる。それは０及び１の間で有界であった圧縮コー
ディング関数が一般性を失うことなく０及びｎによって
有界なようにｎスケーリングできるからである。最後に
従来の算術エンコーダのアーキテクチュアは直列に接続
された１機能的に別個の装置に基すいているので、冗長
性を与える誤りコーディングの整数ｎはコードを形成す
るコードワード（被加数）の従来のパラメータ表現に乗
算でき、このようなパラメータ表現によってエンコーダ
の下流のすべての部分の誤りが検査できるようになる。

この点に関して１本発明は又記号ストリングＳ及びＳ中
の位置のＳの記号の条件付き確率を表わすコーディング
・パラメータに応答するタイプの算術エンコーダ中で実
施される。このようなエンコーダはＳの算術エンコード
表現Ｃ（ｓ）を発生する。Ｃ（ｓ）は半開コーディング
値域〔０、１）中の数である。エンコーダは次の記号ｉ
に先行するＳの部分のエンコーディングによって生じた
Ｃ　（ｓ）の部分の有効端を含む２進レジスタＣ１正規
化因数を計算するため２進レジスタＡ並びにＳ中のｉの
位置におけるｉの条件付き確率に基すいてＣ及びＡの内
容を数値的に調節し、Ｃ（ｓ）がＣの相継いでシフトさ
れた内容を含むようにＡの調節された内容に基づいて予
定の大きさ、方向にＣ及びＡの内容をシフトするための
演算理論装［（ＡＬＵ）を含む、このエンコーダを改良
したものは次の記号ｉのためのコーディグ変数をｎだけ
スケーリングするための装置及び単一ビット誤りを示す
非０余りを求めてモジュロｎ関数に従ってＣの内容をテ
ストするモジュロｎ関数装置を含む。

Ｅ、実施例 Ｅｌ　従来のエンコーダ、デコーダ及び関連装置第２図
は未エンコード・ソース記号ストリームＳを算術的に圧
縮するためのシステムのブロック図を示す、２通信号ソ
ース１ｏは単線１２を介して未エンコード・ソース・ス
トリームＳを統計モデリング装置１４及びエンコーダ１
５に与える。

よく知られているように、モデリング装置１４は記号ス
トリームＳの出現履歴に操作して、単一線１６上に制御
パラメータｋを与える。パラメータには記号ストリーム
中の次の記号ｉのためのＬＰＳの条件付き確率に対応す
る。見方を変えると、パラメータには現在のコーディグ
値域の細分割に使用する確率区間を示す。信号線１８上
にはストリームＳの記号を引出すソース・アルファベッ
ト中の予定の記号６ｍに次の記号ｉが等しいことを示す
表示が与えられる。２進記号ストリームに関連する従来
の算術コーディングでは、線１８上の表示はエンコード
さるべき記号が最大確率記号（ＭＰＳ）であるか最小確
率記号（Ｌ　Ｐ　Ｓ）であるかを示す。エンコーダ１５
は帰納算術関数を具体化して線１６及び１８上の入力に
応答してエンコード・ストリームＣ（ｓ）を発生する装
置である。コード化されたストリームは信号線２４を介
して、モデリング装置２８に関連して動作する算術デコ
ーダ２６に送られ、エンコード・ストリームＣ（ｓ）か
ら記号ストリームＳが抽出される。

ここでモデリング装置２８はこの装置がＬＰＳ記号確率
を推定し、及び信号線３０上にパラメータにの形の推定
値を与える点でモデリング装置１４に対比される。デコ
ーダ２６は又信号線３１上に現在解読された記号がＭＰ
ＳもしくはＬＰＳのどちらかであるかを示す表示を与え
る。デコードされた記号ストリームＳはデコーダ２６か
ら信号線３２上に出力され、信号線３４を介してモデリ
ング装置２８にフィードバックされる。

従来技術では、エンコーダ１５は信号線１６上にモデリ
ング装置１４によって与えられる確率値に応答して記号
ストリームＳ　（信号線１８上に存在する）の次の記号
ｉを求めるために帰納関数（３ａ）乃至（３ｄ）を具体
化したものである。

エンコーダの動作は２進である。従ってＣ（ｓ）及びＡ
　（ｓ）の区間表示は２進数で表現される。

米国特許第４４６７３１７号に開示されているようにＡ
　（ｓ）及びＣ（ｓ）の２進表現は被加数を現在のコー
ド・ストリングの適切な位置に加えるために位置合せが
必要である。１つの加算が終ると、コード・ストリング
Ｃ（ｓｉ）のＷ個の最下位ビットを包括する「作業端」
が再位置合せされ、コード・ストリングの完成した有効
ビットがエンコーダの作業位置の外に移動される。再正
規化と再位置合せは必要とされる算術動作を最小の補足
動作で行う手順中で達成されるもし１＝ＬＰＳの場合に
は、式（３ｄ）中の未正規化部分区間は？であり、２進
形式で表わすと０．００・・・・・・０１００である。

変数Ａ　（ｓＬＰＳ）を１．Ｏｏ・・・・・・０に正規
化するには２：にの２進表現をに位置だけ左にシフトす
る必要がある。コード・ストリングＣ（ｓＬＰＳ）の未
正規化有効ビットは前のサイクルと変わらず、左ににビ
ット、シフトするだけでよい６次の記号ｉがＭＰＳの時
は、コーディング変数Ａ（ｓＭＰＳ）は式（３６）によ
って与えられ、未正規化コード・ストリングは式（３ａ
）によって与えられる。もし式（３６）がＡ（ｓＭＰＳ
）の値を１未満に減少する時は、左に１ビツト、シフト
することによって再正規化でき、コード・ストリングの
有効端の再位置合せを生ずる。この再位置合せでもＡ（
ｓＭＰＳ）と同じ歩調（ロック・ステップ）でＣ（ｓＭ
Ｐｓ）をシフトする必要がある。

ソース・ストリングＳが２進の場合は、帰納関数（３ａ
）−（３ｄ）に従う算術データ圧縮コーディングは次の
アルゴリズムに従い２つのレジスタＡ及びＣによって遂
行される。

〔算術コーディング・アルゴリズム〕

初期設定 Ａ←１．０００・・・・・・０　　（２進）Ｃ←ｏ、ｏ
ｏｏ・・・・・・Ｏ（２進）もし次の記号ｉ＝ＭＰｓな
らば Ａ４−Ａ−Ｅｋ Ｃ４−Ｃ＋２−に そしてもしＡ＜１ならば再正規化が次のように実行され
る。

Ａ←２Ａ Ｃ←２Ｃ もし、次の記号１＝ＬＰｓならば、 ｋ Ａ←２ そして、Ｃ及びＡはＡの内容＝１．００・・・・・・０
（２進）になる迄−斉にシフトされる。

上に明示されたエンコーデング・アルゴリズムを遂行す
るために、レジスタＡ及びＣは上述の半開コーディング
区間〔０、１）を定めるように初期設定される。次にも
し次の記号ｉ　＝　Ｍ　Ｐ　Ｓならば、モデリング装置
１４によって与えられるパラメータｋが−ｚｋに変換さ
れ、炉がＡの内容から減算され、Ｃの内容に加算される
。次にＡの内容を調べて、もし１未満ならばＡ及びＢを
ビットだけ歩調を合してシフトする。Ａ及びＣが通常の
２進レジスタであると仮定するとその内容は上位から下
位の順序位置の大きさに解釈され、シフト動作は最大の
大きさの方向にＡ及びＣの内容を通常のように直列にシ
フトする。同じようにもし次の記号１＝ＬＰＳならば、
Ａの内容は簡単に再初期設定され、他方Ｃの内容はに位
置だけ大きな方向にシフトされる。レジスタＣの高い大
きさの端から順次シフトされるビットがコード・ストリ
ングＣ（ｓ）を形成する。

Ｅ２　従来の圧縮エンコーダの詳細 第３図は従来提案されたエンコーディング・アルゴリズ
ムに従い動作する従来の算術エンコーダの実施例を示す
。従来のエンコーダでは、パラメータｋが変換装置４０
に与えられ、変換装置４０は信号線４１上に値２−ｋを
発生する。この値は信号線１８上のＭＰＳ／ＬＰＳイン
ジケータとともに通常の構成の演算論理装置ｉ！　（Ａ
ＬｔＪ）　４２及び４４に与えられる。ＡＬＵ４２及び
４４は夫々Ｃ及びＡレジスタ４６及び４８の内容に操作
を加える。ＡＬＵ４２は又入力としてレジスタ４６の内
容及び信号［４９上に、Ａレジスタ４８の内容が１未満
になった時にＡＬＵ４４からの信号を受取る。ＡＬＵ４
２はＣ（ｓｉ）の増補された値を線５２を介してレジス
タ４６中に並列にロードし、信号線５３上のシフト制御
信号に従って高い大きさの方向にレジスタ４６の内容を
シフトする。ＡＬＵ４４はレジスタ４８の内容を処理す
るのに必要な算術及び論理動作のすべてを遂行し、信号
線５５上に更新された内容を与える。次にレジスタ４８
の内容は信号線５６上のシフト制御信号に従って高い大
きさの方向にシフトされる。さらに。

ＡＬＵ４４はＭＰＳのエンコーディングによりＡレジス
タの内容の大きさの１未満になった時に信号線４９上に
表示を与える。従来技術は又レジスタ４６の内容をシフ
トすることによって発生されるコード・ストリングを処
理するためのバッファ５７を開示している。このような
処理には固定長コード・ストリング・セグメントの構成
のみならず、Ｃレジスタの内容に影響を与える算術動作
中の桁上げを処理するビット・スタッフィングを含む。

Ｅ３　本発明の誤りエンコーダ 本発明の方法は従来技術のエンコーディング処理及び機
構が値ｎだけスケーリング（桁ずらし）することによっ
て改良されるという知見にもとずいている。結果のアル
ゴリズムは、元のアルゴリズムと同じように、入力信号
の確率に従って利用可能なコーディング・スペースを相
継いで細分割することによって、ソース・ストリームＳ
を同じように圧縮する。しかしながら、従来技術のアル
ゴリズムは半開コーデング値域〔０、１）を分割するこ
とによって開始するが、新しい手順は半開コーデング値
域〔０、ｎ）で開始する。従って。

たとえば最初の記号がＬＰＳの時は、この記号には部分
区間〔０、ｎ−２’）が割合てられるが、元アルゴリズ
ムの場合はパラメータｋによって示される確率として〔
０，２−ｋ〕を求めるだけである。一般にｍ進ソース・
アルファベットの場合は、第１番目の記号をエンコーデ
ングする場合に、改良アルゴリズムはコーディグ区間（
ｎａｉ、ｎｂｉ）で終るが、元アルゴリズムは（ａｉ、
ｂｉ）を生ずる。改良アルゴリズムは、コードＣ’　　
（ｓ）を生ずるが、このＣ’　　（ｓ）は数字としてみ
た時に、未改良コードよりも正確にｎ倍大きい。これに
よって旧コードと比較してわずかにｌｏｇ、ｎビットだ
け増大したコード・ストリング長を生ずるだけである。

誤りエンコーデングのための算術圧縮アルゴリズムは要
約すると次の通りである。

〔改良コーディング・アルゴリズム〕

初期設定 Ａ′←ｎ、ＯＯ・−・・Ｏ（２進） Ｃ′←０．００・・・・・・Ｏ（２進）もし次の記号ｉ
　＝　Ｍ　Ｐ　Ｓの場合には、Ａ′←Ａ’　　　ｎ−２
″ｋ Ｃ′←Ｃ′＋ｎ−２″に そして、もしＡ　＜　ｎならば再正規化が次のように実
行される。

Ａ′　←２Ａ’ Ｃ′　←２Ｇ’ もし次の記号１＝ＬＰｓの場合には、 Ａ′←ｎ・２−に そしてＣ′及びＡ′はＡ′の内容＝ｎ、００・・・・・
・０（２進）になる迄−斉にシフトされる。

改良アルゴリズムによって表わされる元アルゴリズムに
対する変更はエンコーディング過程で単一の誤りの検出
を可能にする。Ｃ″　（ｓ）コード・ストリームの１つ
のビットが第３図のエンコーダによって反転されたもの
と仮定する。これによって、コード・ストリングを整数
とみなした場合には、コード・ストリングＣ’　　（ｓ
）の正しい数値から＋２ｊの差が生ずる。誤りがない場
合には、Ｃ’　　（ｓ）はｎによって整除される整数Ｃ
′を表わす、即ちｃ’　＝Ｏ（モジュロｎ）である。誤
りが生ずると、ｃ’　＋２ｊ＝２ｊ　（モジュロｎ）で
あり、任意のｊについて　２ｊ≠０（モジュロｎ）であ
るから、誤りが０でない余りを得た時に検出される。こ
の分野の専門家にとっては１本発明の方法は複数の誤り
の検出を保証するものでないが、（たとえば、２ｊ＋２
”＝Ｏ（モジュロｎ））、その２八は検出される可能性
が残されていることが明らかであろう。

第３図のエンコーダは本発明に従い第１図に示したよう
に改良される。第１図で変換装置６０がパラメータｋを
受取り、パラメータ］ｋを通常の乗算回路６２に与え、
乗算回路６２はこの値をｎ−に たけスケール変換し、ｎ・２　を発生する。乗算回路６
２は変換装置６０の動作に同期する通常の乗算器でよい
。これに代って、変換装置６ｏは乗算回路６２の動作を
吸収して、直接スケール値ｎ、２”を発生できるような
複合変換装置にすることもできる。この動作は、たとえ
ば読取り専用メモリ（ＲＯＭ）の索引テーブルで実施で
きる。

スケール変換されたコーディグ変数は１対のＡＬＵ６４
及び６６に与えられる。これ等のＡＬＵは第３図の対応
するＡＬＵと同じように動作し、上述の改良アルゴリズ
ムに従い夫々参照番号６８及び７０によって示されたＣ
及びＡレジスタを制御する。ここでＣレジスタ６８の内
容について遂行されるシフト動作は未改良コーディング
・アルゴリズムによって得られるコード・ストリングＣ
（Ｓ）のｎ倍を表わすコード・ストリングＣ′（ｓ）を
発生する。バッファ７２を上述のビット・スタッフィン
グ及びバイト・アセンブリの目的のために与えて、修正
コード・ストリングＣ”　（Ｓ）を与えることができる
。誤り検査の目的の場合には、スケール変換されたコー
ド・ストリングＣ′（ｓ）が信号線７３上を直列に直列
モジュロｎ回路７４に与えられ１回路７４はスケール変
換されたコード・ストリングを検査して、非Ｏの余りを
求める。たとえば、回路７４は信号線７５上に余りＲを
発生するモジュロｎ除算回路でよい。余りＲは通常の比
較回路７６によって非０であるかどうかがテストされる
。回路７４によるモジュロｎ除算が非０余りＲ≠０を生
じた時、比較回路７６は信号線７７上に誤りＥ表示を与
える。モジュロｎ除算回路７４及び比較回路７６より成
るテスト回路は並列もしくは直列形で重複させ、任意の
予定の要所に配置してスケール変換されたコード・スト
リームＣ’　　（ｓ）の形成、伝送もしくはデコーディ
ング中に非０の余りをテストすることができる。従って
、たとえば、Ｃレジスタ６８の内容は該レジスタとＡＬ
Ｕ６４の間のフィードバック経路８０中で、又Ｃレジス
タ６８に転送される時にＡＬＵ６４の出力で並列にテス
トできる。さらに、Ａレジスタの旧及び新内容は夫々信
号線８４及び８６の各々の中に並列モジュロｎテスタを
挿入することによって誤りがテストできる。乗算回路６
２からＡ及びＣレジスタへの六方も又並列モジュロｎテ
スタによってテストできる。最後に、モジュロｎテスト
回路はバッファの出力に与えられ、Ｃ”　、（ｓ）（ｍ
ｏｄｎ）＝Ｏを保持するようにビット・スタッフィング
が適切に行われたかどうかの誤りテストが第１図のエン
コーダの出力でなされる。従って第１図のエンコーダの
動作の信頼性は乗算回路６２もしくは複合変換装置から
バッファ７２の出力に至るコード・ストリーム中の任意
の個所で単一の誤りを早期に検出することによって増強
される。

モジュロｎ回路７４はモジュロｎの余りをテストするよ
うに種々の方向で構成できる。たとえば、直列モジュロ
ｎ回路は直列装置として構成でき、コード・ストリーム
Ｃ’　　（ｓ）の直列表示をビット毎に除算する。これ
に代り、回路７４は並列除算器として形成及び動作され
、Ｃ及びＡレジスタの内容並びにＡＬＵ６４及び６６の
並列出力についてテスト動作が遂行できる。この場合、
この単−誤り検査方法はストリームＣ’（ｓ）の発生時
に直列に発生される多重ビット誤りを検査するのに使用
できることは明らかであろう。回路７４のビット毎の直
列テスタの例示的実施例はｎ＝３を仮定している第４図
及び第５図を参照して理解できよう。

Ｅ４　直列テスタ 第４図で、１対のセット−リセット（Ｓ−Ｒ）フリップ
−フロップ８ｏ及び８２の各々は夫々相補出力Ｑ、／Ｑ
、及びＱ、／Ｑ、を有する。フリップ−フロップ８０の
状態はゲート８３−８５の出方によって決定される。同
じように、フリップ−フロップ８２の状態はゲート８７
−８９の出力によって決定される。フリップ−フロップ
８ｏ及び８２はｎスケール変換されたコード・ストリー
ムＣ′（ｓ）の現在の記号ｃｊを直列にテストする３状
態装置である。第４図のｎ状態装置は上述のように第１
図のエンコーダでｎ＝３を仮定して３状態装置として構
成されている。フリップ−フロップの８０及び８２によ
って定められる状態は状態０＝ＯＯ（ｃｉ、Ｑ２＝１）
；状態１　＝　１０　（ｃｘ　−Ｑ、＝１）及び状態２
＝１１　（ｃ、、　Ｑ、＝１）として定義される。状態
間の遷移は第５図に状態を相互接続する矢印によって示
されている。さらに例示の目的のために、初期状態は状
態０であり、即ちフリップ−フロップ８０及び８２は最
初リセットされていて、同時にＡ及びＣレジスタの内容
は改良アルゴリズムに従って初期設定されているものと
仮定する。次にｎスケール変換されたコード・ストリー
ムがＣレジスタを相継いでシフトすることによって発生
される時、Ｃレジスタからシフトして出されるビットが
ゲート８３．８４．８７及び８８への入力として与えら
れる。フリップ−フロップ８０及び８２の結果の状態は
その出力の条件（即ち３状態装置の現在の状態）によっ
て決定される。改良コーディング・アルゴリズムからの
各完了コード・ストリングの終りに、第４図の３状態装
置の状態を検査する。もし３状態装置が状態Ｏ以外の任
意の状態にあれば、比較回路７６は誤りＥ表示を与える
６ 要するに、第４図の３状態装置はＣの余り（モジュロ３
）を決定することによってエンコーダの誤りを検出する
。ここでＣは現在のコーディング・サイクル中のエンコ
ーダの出力から得られる累続数値である。上述のアルゴ
リズムの両方はその最上位ビットが最初に形成される先
入れ先出しコードを与えるので、第４図の３状態装置は
コードの計算と同時に効率的に余りを計算する。第５図
の状態遷移図で、各状態は可能な現在の余りを示してい
る。従って、状態０にある時は余りはＯであり、状態１
では余りは１であり、他方状態２では余りは２である。

もしビット・スタッフィングがバッファ７２で行われる
時は、第４図の３状態装置はビット・ストリームＣ’　
　（ｓ）中のわずかな変更に適応するように改良できる
。しかしながら、バッファ７２中のビット・スタッフィ
ングの後に、コード・ストリームＣＩｔ　　（ｓ　）が
誤りのない時（即ちＣ”　　（ｓ）＝Ｏ，ｍｏｄｎの時
）に０の余りを有することを保証するためにはｂ個のビ
ットがｐ＝Ｑ、１．２・・・・・・Ｐ個の許容される２
進状態のうちの１つを含むようにスタッフ（ｓｔｕｆｆ
）される必要がある。ｎが奇数で＋１もしくは−１に等
しくない時は、ｂはｆｅｂ−１＝Ｐ−ｎ、即ちｎの整数
倍が成立つような正の整数でなければならない。ｂビッ
トの所与の集合が与えられた時の許容可能な状態は、Ｐ
−ｎ＜２”ｂ−１が成立つ式％式％ もし、ｎ＝３ならば、ｂ＝２のすべての正の整数倍であ
る。たとえばｂ＝２の場合には、Ｐ＝１及びｐ＝　（Ｏ
ｏ、１１）である、同じように、もしｎ　＝　５ならば
、ｂ＝４のすべての正の整数倍である。たとえばｂ＝４
の場合には、Ｐ＝３及びｐ＝　（００００，０１０１，
１０１０，１１１１）である。

第４図の３状態位置が動作する方法を明確にするために
、コード・ストリングｃ＝１０１０１１を３つで除算す
る例について考える。２進表示で表わされたコード・ス
トリングＣを３（１０進）に等価な値１１（２進）によ
って除算する通常の除算を第７図に示す。第７図に示し
たように、除算の各ステップの余りＲは第４図の３状態
装置の状態によって示されている。さらに、３状態装置
の状態は記号ストリームの現在の記号ｃｊと３状態装置
の前の状態と組合わして決定される。従って第４図の装
置は状態Ｏに初期設定され、最初のビット（Ｃ＠＝１）
で状態１に遷移する。最後の状態が状態１であるという
ことは、コード・ストリングが不完全であるか、完全な
コード・ストリング中に誤りがあることを示す。

Ｅ５　本発明のデコーダ 従来技術に従うデコーディングは第６図及び以下説明さ
れるデコーディング・アルゴリズムによって容易に理解
されよう、スケール変換されている場合のデコーディン
グはＷピット幅のレジスタＣをコード・ストリングＣ（
ｓ）の最上位からＷビットで初期設定し、レジスタＡを
１．００・・・・・・０にセットすることによって行わ
れる。次にコード・ストリングＣ（ｓ）の各導入ビット
に対して、遂行されるデコーディング動作はコーディン
グ変数を試験的に減算することに基づく。解読される記
号はコーディング変数をコード・ストリングＣ（ｓ）に
対して算術的なテストを行った結果に依存する。２進の
場合には、従来技術に従えば該テストはｃ−ｉｋである
（ここでｋはモデリング装置によって与えられる）。も
しｃ−戸＞ｏならば、ＭＰＳがデコードされ、次にＣ及
びＡの内容がともに２−にだけ減少される。もしこの結
果、Ａの内容が１未満になると、再正規化が生じ、Ｃ（
ｓ）の最上位部がＣ中にシフトされる。もし差が０未満
ならば、ＬＰＳがデコードされ、２−ｋがＡ中に置かれ
、Ａ及びＣが一斉にＡ＝１．００・・・・・・０になる
迄シフトされ、Ｃ（ｓ）の次のに個の最上位ビットがＣ
中にシフトされる。このデコーデング・アルゴリズムは
次のように表わされる。

〔デコーデング〕

初期設定 Ａ←１．００・・・・・・Ｏ Ｃ←（Ｃ（Ｓ）の最初のＷ個の最上位ビット）もしｃ−
戸＞ｏならば、ＭＰＳがデコードされ、次の動作が行わ
れる。

ｋ ４−Ａ−２ ｋ ４−Ｃ−２ もしＡ＜１ならば、Ａ及びＣを一斉に、Ａ＝１゜０・・
・・・・０になる迄、シフトし、Ｃ（ｓ）の最上位部を
Ｃ中にシフトする。しかしもしｃ−４ｋ＜。

ならば、ＬＰＳがデコードされ、次の動作が行われる。

Ａ←２″に そしてＡ及びＣが一斉にシフトされ、Ａ＝１゜ｏｏ・・
・・・・０になる迄Ｃ（ｓ）の次のに個の最上位ビット
がＣ中にシフトされる。エンコーディング動作がスケー
ルされてＣ’（ｓ−）を発生する場合には上述のデコー
ディング・アルゴリズムは本発明に従って次のように改
良される。

〔改良デコーディング・アルゴリズム〕初期設定 Ａ’　＋ｎ　・１　、　ＯＯ−００（２進）Ｃ′←（Ｃ
’　　（３）の最初のＷ個の最上位ビット） もしＣ’−ｎ・り’＞ｏならＭＰＳがデコードされ１次
の動作が行われる。

ｋ Ａ′←Ａ’　　　ｎ・２ Ｃ″←Ｃ’−ｎ・２−に もし、Ａ’　＜ｎ　・１．００−−００　（２進）、再
正規化が実行される。

Ａ′←２Ａ’ Ｃ′←２Ｇ’ もしＣ’　−ｎ　・２：ｋ＜Ｏ，ＬＰＳデコードされ、
次の動作が行われる。

Ａ′←ｎ−２，に そしてＡ′及びＣ′が一斉にシフトされ、Ａ′＝１．０
０・・・・・・０にされ、Ｃ’　　（ｓ）の次の最上位
ビットがＣ′にシフトされる。

第６図はｎスケール変換されたコード・ストリームＣ’
　　（ｓ）を入力として受取り、これを上述の改良アル
ゴリズムに従ってデコードするデコーダ９０を示す。デ
コーダ９０はモデリング装置（図示されず）によって与
えられるｋに応答して被加数ｎ−２’を発生する組合せ
ｎスケーリング変換装置９１を含む。このｎスケール変
換された被加数は、本発明に従いＡ及びＣレジスタ９６
及び９８の内容に操作する１対のＡＬＵ９２及び９４に
与えられる。テスト論理回路１００はＣ−ｎ・ｚｋとＯ
の関係をテストし、ｉがＭＰＳであるかＬＰＳであるか
のデコーディング決定を行う。導入する修正コード・ス
トリームＣＪＦ（ｓ）に操作を加えるバッファ９９はバ
イトのディスアセンブリ、ビットのアンスタッフィング
のために与えられ、ｎスケール変換されたコード・スト
リングＣ′（ｓ）を生じる。デコーダ９ｏへのＣ’　　
（ｓ）入力はエンコーダについて上述された装置である
直列モジュロｎ回路１０２によってテストされ、比較回
路１０３によって、テストされた余りが発生できる。同
じように、Ｃ’　　（ｓ）の最上位ビットのシフト・イ
ンに応答して直列にシフト・アウトされるビットの形の
Ｃレジスタの出力も比較回路１０４に与えることができ
る。Ｃレジスタの内容について遂行される相継ぐ減算は
もしデコーダ９０が正しく動作しているならば、シフト
・アウト・ビットが０になり、比較回路１０４はデコー
ダの誤りを検出するのに使用される。さらに、ＡＬＵ９
２及び９４の並列レジスタをソースとする入力及び並列
数値出力は上述のように並列にモジュロｎテストできる
。

多重文字アルファベット・ソース・ストリームのための
算術データ圧縮コードを発生するための方法及び装置は
１９８６年、２月２４日付けの米国特許出願第８２５８
３１号に開示されている。

この米国特許出願の多重文字アルファベット算術エンコ
ーダは未エンコード・ストリング中の記号の出現カウン
トより成る統計量に基づいて依存する。この出現カウン
トはモデリング装置によって、半開コーディング値域〔
０、１）にエンコードするためのエンコーダに与えられ
る。この出現カウントは２進ソース・ストリングのため
のモデリング装置によって与えられるカウンティング・
パラメータｋに関連し、上述の方法に対応する方法でＡ
及びＣレジスタを動作させるコーディング及びデコーデ
ィング手順を支援する。従って、この分野の専門家にと
っては、２進ソース・ストリームに関連して上述した本
発明は単に半開コーディング値域を〔０、ｎ）にスケー
リングし、出現カウントをｎだけスケーリングすること
によって上述の米国特許出願に開示された場合について
も実施できることは明らかであろう。この点において。

エンコーダ及びデコーダの両方のために上述されたもの
と正確に同じ余りテストが遂行され、コード化ストリー
ム中の誤りが検出される。

ｍ進算術圧縮コーディングの場合には、この説明は又部
分区間Ａ　（ｓ）の個々の部分のための、他の一定のた
だし任意の順序をカバーすることを意味する９例えば、
条件付は確率を増大することによって順序付けられた相
継ぐ部分によって区間を細分割する代りに、相継ぐ部分
は条件付は確率を減少することによって容易に順序付け
ることができる０部分区間が（Ｃ（ｓ）、Ｃ（ｓ）　＋
Ａ）によって定義される算術コーディングの前の説明に
もかかわらず、この説明は部分区間が半開コーディング
領域（Ｃ（ｓ）　−Ａ　（ｓ）　、　Ｃ（ｓ）　）によ
って定義される複式方法をカバーするものと解釈できる
。この複式方法の場合は、Ｃ（ｓ）は上界であり、コー
ディング変数を１．０に初期設定された未スケール変換
ストリングから減算することによって誘導される。Ａス
ケール変換コード・ストリングの場合には、ストリング
は最初にＡに初期設定され、次にＡスケール変換された
減数が減算される。すべての未スケール変換もしくはＡ
スケール変換部分区間の寸法は次に従前のように計算さ
れる。伸縮は圧縮に使用したコーディング変数を試験的
に加算し、全体の区間の寸法の大きさを越えない最大の
数値（１，０もしくは誤りエンコードされている場合に
はＡ）を発見することによって達成される。

Ｆ６発明の効果 本発明に従い、算術データ圧縮コーディングによって発
生するコード・ストリング内の誤りを検出する方法及び
装置が与えられる。

【図面の簡単な説明】

第１図は本発明に従うエンコーダのブロック図である。 第２図は未コード化ソース記号ストリームＳとその算術
エンコード表示Ｃ（ｓｓ）のインターフェイス、　Ｃ（
ｓ）とデコード・ストリームＳとの逆インターフェイス
を示したブロック図である。第３図は従来の２進ソース
算術圧縮エンコーダのブロック図である。第４図はモジ
ュロ非Ｏ余りを求めて算術誤りエンコード・ストリーム
を直列にモニタする３状態装置の論理ブロック図である
。第５図は２進コード・ストリームの非０余りを求めて
モジュロをテストするための多重状態装置の状態図であ
る。第６図は本発明に従う２進ソース算術圧縮デコーダ
のブロック図である。第７図は算術誤りエンコード・デ
ータ・ストリームの誤りを検査する数値例を示した図で
ある。 １０・・・・・・信号ソース、１４．２８・・・・・・
モデリング装置、１５・・・・・・エンコーダ、２６・
・・・・・デコーダ、６０・・・・・・変換装置、６２
・・・・・・乗算回路、６４．６６・・・・・・ＡＬＵ
、６８・・・・・・Ｃレジスタ、７０・・・・・・Ａレ
ジスタ、７２・・・・・・バッファ、７４・・・・・・
モジュロｎ回路、７６・・・・・・比較回路。 第３図 第４図 ヒ　　　　　　　　　　　　　　　　　ヒ□１ □Ｆ □Ｆ □１ □ｌ □１ 第７ ベ＝Ｉ−一一−１０ １，２−ｍ−−１０１ （＝２−ｍ−−ｔｏ。 Ｒ＝１−一一一−Ｉ＋ Ｒ＝Ｏｏｌ Ｒ；１　　　　　　　　　１ 図

Claims (2)

【特許請求の範囲】
1. （１）２進記号ストリングｓ＝ｂ（１）、ｂ（２）・・
   ・・・・、ｂ（ｉ）、・・・・・・ｂ（ｎ）を帰納装置
   によってｓの表示として圧縮２進数Ｃ（ｓ）を発生する
   間に単一ビット誤りを検出する方法であって、ただしＣ
   （ｓ）は半開区間〔０、１）中の数であり、この区間は
   相継ぐエンコーディング・サイクル中に下界Ｃ（ｓ）及
   びコーディング変数Ａ（ｓ）によって定義され、該Ｃ（
   ｓ）及びＡ（ｓ）の値はＣ（ｓ）及びＡ（ｓ）の算術帰
   納関数として計算される〔Ｃ（ｓ）、Ｃ（ｓ）＋Ａ（ｓ
   ））で与えられる部分区間に相継いで細分割されるもの
   とする方法において、 （ａ）上記算術帰納関数をｎだけスケーリングし、（ｂ
   ）上記ｓを上記ｎだけスケーリングされた算術帰納に従
   って半開区間〔０、ｎ）中の圧縮兼誤りエンコードされ
   た２進表示Ｃ′（ｓ）に変換し、（ｃ）上記Ｃ′（ｓ）
   をモジュロｎ関数でテストして非０の余りを求める段階
   を有する、 単一ビットの誤り検出方法。
2. （２）算術的に圧縮された２進記号ストリングＣ′（ｓ
   ）を受取り、これから、コーディング・パラメータ（ｋ
   ）にもとずいて試行コーディング変数を発生し、試行コ
   ーディング変数を圧縮ストリングのＷ個の最上位ビット
   に対して算術的にテストし、テストの結果にもとずいて
   ストリングｓの次の記号ｂ（ｉ）をデコードすることに
   よって、２進記号ストリングＳ＝ｂ（１）、・・・・・
   ・、ｂ（ｉ）・・・・・・、ｂ（ｎ）の相継ぐ記号ｂ（
   ｉ）を発生するタイプの算術デコーダにおいて、 ただし、上記Ｃ′（ｓ）は半開区間〔０、ｎ）中の数で
   あり、（ｎは＋１もしくは−１以外の奇数である） さらに、 （ａ）上記試行コーディング変数をｎだけスケーリング
   する装置と、 （ｂ）上記ｂ（ｉ）の発生の前にＣ′（ｓ）をテストす
   るモジュロ装置を含む、 算術デコーダ。